I recently needed a statically-sized circular buffer with (de)-serialization support. Upon closer inspection, I saw that there was no crate which is no_std and supports (de)-serializtion. This crate tries to fill that gap.
The underlying datastructure is an array [core::mem::MaybeUninit<T>; N] and the structure stores sizes and current start to monitor current events. It implements .iter() and into_iter() methods.
Documentation
Example
use circ_buffer::RingBuffer;
let mut ring_buffer = RingBuffer::<_, 5>::new();
ring_buffer.push("Aurea prima");
ring_buffer.push("sata est");
ring_buffer.push("aetas, quae");
ring_buffer.push("vindice nullo");
ring_buffer.push("sponte sua,");
ring_buffer.push("sine lege fidem");
ring_buffer.push("rectumque colebat.");
let elements: Vec<_> = ring_buffer.into_iter().collect();
assert_eq!(elements[0], "aetas, quae");
assert_eq!(elements[1], "vindice nullo");
assert_eq!(elements[2], "sponte sua,");
assert_eq!(elements[3], "sine lege fidem");
assert_eq!(elements[4], "rectumque colebat.");
Remark: I use std::vec::Vec for testing purposes only.
Since this is a platform-neutral library with unsafe code, it's a great candidate for testing with Miri to check for soundness bugs. I suggest adding cargo +nightly miri test to your CI actions.
Your Cargo.toml hasn't got a package.repository URL, so there's no visible place to report bugs and follow the development.
Thanks so much for the quick feedback. I was not even expecting that. I have tried to incorporate your suggestions.
I have gotten only a short glimpse of what miri is and does and have not had the time to really study its advantages. But I have found their MWE for github actions and added it to the test suite.
I have added a repository link.
This is really interesting. My use-case was not concerned with any security/safety in mind. I simply needed something static and fast. I have now migrated from the bare array [MaybeUninit<T>; N] to a new struct which just holds this array. I then implemented the Drop trait for this struct. In this way, I can reuse this approach for the Iterator as well and ensure zeroeing every time.
What you may be missing is that MaybeUninit<T> does not drop T when the MaybeUninit is dropped. It has methods for explicitly dropping T when you know it is initialized, which you have to call if you don't want to leak T.
I see. Sorry as you might have guessed I do not come from the embedded world and am not too familiar with many of the day-to-day problems encountered in these scenarios. Would this work or does this still not drop the individual values because MaybeUninit does not drop anything?
impl<T, const N: usize> Drop for ItemStorage<T, N> {
fn drop(&mut self) {
unsafe {
core::ptr::drop_in_place(core::ptr::slice_from_raw_parts_mut(
self.0.as_mut_ptr(),
N,
));
}
}
}
I used the same approach which the Drop impl of the std::vec::Vec uses (see mod.rs - source).
Dropping the Vec array will drop everything contained in the array. You don't need unsafe code to do that. But when the MaybeUinit is dropped during this process (because it is contained in the array), MaybeUninit will not drop the T that it contains, because that T may not be initialized. Only you know whether it is initialized, so you must explicitly drop it.
You have to explicitly drop the T in each MaybeUninit<T> that you know is initialized by, for example, calling assume_init_drop on each one. The only unsafe call you need is the one to assume_init_drop.
Below is code that explicitly drops all of the elements. But all of them may not be initialized, so this needs to be modified to only drop the elements you know are initialized. I assume you have start and end indexes or something similar for your ring buffer, so you can change this to only drop those which are initialized.
struct ItemStorage<T, const N: usize>([MaybeUninit<T>; N]);
// THIS MUST BE CHANGED TO AVOID UB, SEE ABOVE
impl<T, const N: usize> Drop for ItemStorage<T, N> {
fn drop(&mut self) {
for elem in self.0.as_mut() {
unsafe { elem.assume_init_drop() }
}
}
}
Okay. Thanks for your patience with this topic. I was just about to post my version which looked very similar although a bit more unwieldy. Is dropping uninitialized memory considered unsafe? I would believe so.
Be sure to run your tests under Miri as it will find many (but not all) such problems. Don't wait for your CI runs, also run it during your dev cycle. When writing unsafe code we can't just rely on code review, we need tools because we've explicitly disabled many of the compiler's safeguards. Miri is not difficult to run, although it is very slow. Let us know if you have problems running Miri, many people here can help.
I think I know why. What was happening is that the initialized elements were not dropped, which means any memory they allocate will leak. But if your test only stores elements that don't allocate memory (e.g., a byte buffer or simple struct with primitive fields), then there is no leak so Miri doesn't detect one. If you change your test to store something in the ring buffer that allocates, like a String, then it should detect a leak.
Oh, but this is no_std! Are you already enabling std or at least alloc in your tests, so you can add String elements to your ring buffer?
I should have added this earlier: For Miri to be useful you have to write pretty exhaustive tests. Luckily this pays off in other ways as well.
Of course it's also possible to test this without Miri by explicitly checking in your test that drop is called by using a type with a Drop implementation that has a side effect.
struct S(i32);
static COUNTER: AtomicI32 = AtomicI32::new(0);
impl Drop for S {
fn drop(&mut self) {
COUNTER.fetch_add(1, Ordering::Relaxed);
}
}
If you add a few S to your ring buffer and then drop the ring buffer, the counter should contain the number of items you added.
Another way you can see Miri fail is if you use the implementation I provided that drops all elements, and Miri should complain that you're dropping uninitialized elements.
This is not really security of safety. It's just that not dropping values can leak memory, which ultimately can make your program use more and more memory until it runs out of it.
Note that this will assume all the MaybeUninits to be initialized, which may not be the case. Assuming an uninitialized MaybeUninit to be initialized is UB in most cases.
IMO this ItemStorage is useless, since it's the circular buffer that knows which items are initialized or not.
push also seems to not drop old values when overwritten.
Since you're using MIRI, write a couple of tests where you push a bunch of Boxws or Vecs in a circular buffer (in particular 1 and N + 1 should suffice). MIRI should complain that you're not dropping them, and will also complain if you're dropping non-initialized slots as well.
Another issue is that iter is calling assume_init_ref on all items, even those that might not be initialized, which is UB, though I'm not sure if MIRI will catch this.
Yep you are completely right but in my current version this is different to the code comments here. I only drop values which have been initialized which is made sure by keeping track of the size and start of the RingBuffer.
In general, I have reworked the structure such that the core logic rests inside the ItemStorage struct. This way I can implement drop but reuse its functionality for the iterator again.
impl<T, const N: usize> Drop for ItemStorage<T, N> {
fn drop(&mut self) {
for n in self.first..(self.first + self.size) % N {
match self.items.get_mut(n) {
Some(e) => unsafe { e.assume_init_drop() },
None => (),
}
}
}
}
This is the automated test which I am running to make sure that all variables are dropped correctly.
#[test]
fn test_drop_valid() {
#[allow(unused)]
struct S(i32);
static COUNTER: std::sync::atomic::AtomicI32 = std::sync::atomic::AtomicI32::new(0);
impl Drop for S {
fn drop(&mut self) {
COUNTER.fetch_add(1, std::sync::atomic::Ordering::Relaxed);
}
}
let mut circ_buffer = RingBuffer::<_, 234>::new();
circ_buffer.push(S(5));
circ_buffer.push(S(2));
circ_buffer.push(S(11));
circ_buffer.push(S(87));
drop(circ_buffer);
assert_eq!(COUNTER.load(std::sync::atomic::Ordering::Relaxed), 4);
}
Running this test with the incorrect implementation will be caught by Miri as discussed earlier. This test is in the CI under .github/workflows/test.yml.
I have just veryfied this. I am looking at possible fixes at the moment. Thanks for the valuable feedback!
Is calling MaybeUninit::new(MaybeUninit::assume_init_ref(x)) considered UB or unsound? In my understanding this procedure will be optimized away by the compiler in its entirety and leave the referencing operation for all items. I am eager to learn about this.
This test does not cover the case where it "circles" back to the start. Try repeating the same test with a RingBuffer of size 3. This should also catch the issue with push.
My bad, that's what happens when you read comments while half asleep...
Yes. MaybeUninit::assume_init_ref(x) is always UB when called on an unitialized MaybeUninit, it doesn't matter what you do with it after that. Wrapping it in a MaybeUninit
Optimizations are always optional, and they aren't even your friends here: doing MaybeUninit::assume_init_ref(x) is telling the compiler that x will surely be initialized and can optimize the code accordingly. Of course this assumption is wrong, and thus the resulting optimizations can also be wrong.
Even semantically this is wrong, because you went from what's essentially a &MaybeUninit<T> (meaning the reference itself is initialized, but what it points to is not) to a MaybeUninit<&T> (meaning the reference may not be initialized, but if it is then what it points to is initialized; moreover the code is such that the references are always initialized, and so what they point to must also be initialized, but it isn't!).
A simple fix would be to only call MaybeUninit::assume_init_refs on those elements that are initialized, leaving the others with MaybeUninit::uninit(). However a better fix would be to just have two separate iterators with different logic for how to yield an element. This will also avoid having to iterate over all the elements in the buffer just to create the iterator, which is potentially pretty expensive.
