GrowLock: a fixed-capacity vector which allows concurrent reads and exclusive writes

code review
1

Some days ago someone in this forum asked this:

so I tried to implement this structure myself. It still isn't finished but the core functionalities are all there, so I'd be glad if someone could tell me their opinion about my code.
note that I didn't test it yet so maybe there's some unsoundness.

repository: GitHub - CieriA/growlock-rs: Rust library implementing a contiguous array type that can have simultaneously any number of readers and one writer.

2 Likes
2

I have been working on an extremely complex concurrent data structure myself for 3-4 weeks now :'D I will definitely take a look and leave a review! :slight_smile:

1 Like
3

Just to have it mentioned there, spin locks in general are not really good as in OS context you can waste resources or deadlock as OS doesn't know you are taking a lock in bare metal context it's even worse.

3 Likes
4

Edit: I looked on the docs and Mutex does not use a spinlock, so I will change the github description. (GrowLock uses Mutex so it isn't a spinlock)

5

By the way I wrote a rough design of how to implement such data structure: How to split a global vector so left is constant and right is mutable? - #12 by Ddystopia

2 Likes
6

I took a look at your implementation. I think the Drop implementation for RawAtomicVec may not be enough. You should probably implement Drop for AtomicVec too. I think it's currently causing a memory leak, for types that allocate to heap (like String).

When drop(atomic_vec) is called, it basically goes on to call drop(raw_atomic_vec) -> which clears the whole buffer it wrote to (this works if you are only using Copy types). BUT if you push a String or something that allocates to heap BEFORE being pushed to AtomicVec, that memory allocated by that heap allocator will not be freed, because drop will never get called on them. You have to implement Drop for AtomicVec with drop_in_place on each of its elements to properly free the memory.

EDIT: When drop is called, on AtomicVec, the auto generated drop will go field by field to drop each of its fields, and the first one to get dropped will be buf -> which leads to direct drop(raw_atomic_vec), Also, you can't know the len of the AtomicVec from RawAtomicVec, so the ordering wouldn't really matter anyway.

pub struct AtomicVec<T, A: Allocator = Global> {
    buf: RawAtomicVec<T, A>,
    len: AtomicUsize,
    mutex: Mutex<()>,
}

/// Just a simple way to check this in your case.
struct DropCounter<'a> {
    counter: &'a AtomicUsize,
}

impl Drop for DropCounter<'_> {
    fn drop(&mut self) {
        // When the DropCounter is dropped, the counter is incremented
        self.counter.fetch_add(1, Ordering::SeqCst);
    }
}

#[test]
fn elements_are_dropped() {
    let drop_count = AtomicUsize::new(0);
    {
        let vec: AtomicVec<DropCounter<'_>> = AtomicVec::new(5);
        let guard = vec.lock().unwrap();

        guard.push(DropCounter {
            counter: &drop_count,
        });

        guard.push(DropCounter {
            counter: &drop_count,
        });

        guard.push(DropCounter {
            counter: &drop_count,
        });

        // `vec` will be auto dropped as it goes out of scope here
    }; // drop_count should get incremented thrice.

    // You will get 0, because none of pushed elements will call drop() 
    assert_eq!(drop_count.load(Ordering::SeqCst), 3);
}
1 Like
7

Thanks for your review! I think I fixed this problem. I also added this test to check it, and it works. In the commit you looked at I forgot to add a Drop impl for GrowLock that drops the initialized elements, but now I added it.
test:

#[test]
fn initialized_drop() {
    use std::sync::atomic::{AtomicUsize, Ordering};
    static COUNTER: AtomicUsize = AtomicUsize::new(0);
    struct AddOnDrop;
    impl Drop for AddOnDrop {
        fn drop(&mut self) {
            COUNTER.fetch_add(1, Ordering::Relaxed);
        }
    }

    {
        let vec = GrowLock::new(200);
        let mut guard = vec.lock().unwrap();
        for _ in 0..100 {
            guard.push(AddOnDrop);
        }
        // here `vec` is dropped
    }
    assert_eq!(COUNTER.load(Ordering::Relaxed), 100);
}

drop impl:

impl<T, A: Allocator> Drop for GrowLock<T, A> {
    fn drop(&mut self) {
        // if T::IS_ZST capacity() returns usize::MAX
        if self.capacity() == 0 {
            return;
        }
        // SAFETY: all elements are correctly aligned.
        //  see AtomicVec::as_slice for safety.
        unsafe {
            ptr::drop_in_place(ptr::slice_from_raw_parts_mut(
                self.as_mut_ptr(),
                self.len(),
            ));
        }
    }
}
1 Like
8

Apart from that, it mostly seemed okay to me. I actually couldn't think of any immediate unsoundness related to the FIXME tags you left, they may constrain probable future additions? With writers being Release and readers being Acquire... I think they only access disjoint index ranges with push and as_slice. You could use a SAFETY note instead on these, because if you somehow end up mutating elements at indices < len you will have a correctness issue.

Also, you can add these small micro optimizations if you want :'D I learned some interesting optimization tricks recently:

// This would skip types that are `Copy` as they can't implement `Drop`
// Skipping the drop_in_place call
if !std::mem::needs_drop::<T>() {
  return;
}

// You don't really have to call len(), because you atomically load inside it.
// It should be safe to just to this,
let len = *self.len.get_mut();
unsafe {
    ptr::drop_in_place(ptr::slice_from_raw_parts_mut(
    self.as_mut_ptr(),
    len,
  ));
}

EDIT: You should also take a look into how you have handled Drop for RawAtomicVec too, it MAY have issues in some edge cases, I am just guessing, but I usually mess up Layout related stuff, so I may just be paranoid here :'D

1 Like
9

Thank you. I'll test RawGrowLock's Drop to see if it really can fail.

1 Like