Unsafe queue implementation

Question

I try to create an unsafe, but more performant ArrayQueue implementation. After I added test cases, one of them produces a segmentation fault. Here is my simple minimal implementation:

use std::mem;

pub struct ArrayQueue<T> {
    buff: Vec<T>,
    head: usize,
    size: usize,
}

impl<T> ArrayQueue<T> {
    pub fn new(size: usize) -> Self {
        let mut buff = Vec::with_capacity(size);

        unsafe {
            buff.set_len(size);
        }

        ArrayQueue {
            buff: buff,
            head: 0,
            size: 0,
        }
    }

    pub fn add(&mut self, elem: T) {
        let idx = (self.head + self.size) % self.buff.len();
        *unsafe { self.buff.get_unchecked_mut(idx) } = elem;
        self.size += 1;
    }

    pub fn remove(&mut self) -> T {
        let idx = self.head;

        self.size -= 1;
        self.head = (self.head + 1) % self.buff.len();
        mem::replace(unsafe { self.buff.get_unchecked_mut(idx) }, unsafe {
            mem::uninitialized()
        })
    }
}

impl<T> Drop for ArrayQueue<T> {
    fn drop(&mut self) {
        let mut idx = self.head;

        for _ in 0..self.size {
            // Drop only valid elements of the queue
            drop(unsafe { self.buff.get_unchecked_mut(idx) });
            idx = (idx + 1) % self.buff.len();
        }

        unsafe {
            // Prevent deallocation of vector elements
            // This still dallocates vector's internal buffer
            self.buff.set_len(0);
        }
    }
}

#[cfg(test)]
mod test {
    use super::ArrayQueue;

    #[test]
    fn test0() {
        let mut x = ArrayQueue::new(10);
        x.add(String::from("K"));
        assert_eq!(x.remove(), String::from("K"));
    }

    #[test]
    fn test1() {
        let mut x: ArrayQueue<Box<String>> = ArrayQueue::new(10);
        x.add(Box::new(String::from("K")));
        assert_eq!(x.remove(), Box::new(String::from("K")));
    }
}

I believe I am doing proper dropping to prevent any memory leaks.

I've attached two test cases where one works, but the other results in a crash due to invalid memory reference.

It crashes inside the add method (*unsafe {self.buff.get_unchecked_mut(idx)} = elem;) and I suspect that happens because I am somehow trying to write to an invalid memory location.
I've specifically used heap allocated objects for vector elements in test but to my surprise String works properly while Box doesn't.

I would like to understand if it's possible to make an unsafe implementation like this and why it's currently failing?

Edit

I've fixed the issue by replacing *unsafe {self.buff.get_unchecked_mut(idx)} = elem; with unsafe {std::ptr::write(self.buff.get_unchecked_mut(idx), elem)};

Now I would like to understand why this works and previous version doesn't

I think this is a duplicate of https://stackoverflow.com/questions/31360993 or https://stackoverflow.com/questions/55741517. TL;DR - you are dropping values which hasn't been initialized. You are setting the length to a number, but the values in that range are uninitialzed memory. — hellow, May 21 '19 at 11:29
no, I don't think there is any problem with calling drop on uninitialized memory here. As far as I can see, problem emerges in the `add` method when assigning value to the uninitialized memory — Marin Veršić, May 21 '19 at 11:38
That's the problem with this unsafe code. You are dropping the element when you assign the new values to the index. If you do `buff.resize_with(size, T::default);` instead of `set_len` it won't crash anymore https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=ae87d9ffce5c41e4a0f2f02d0bf93b09 — hellow, May 21 '19 at 11:47
thanks, but if previous value is getting dropped when assigning new value, how come it works for `test0` where there is also a heap allocated object (string)? I understand I can use default values, I was specifically trying to avoid it — Marin Veršić, May 21 '19 at 11:50
Pure luck. As said, you are accessing uninitialized memory which is undefined behavior. Don't do it ;) You could use `mem::forget` to not call the destructor of the element you are trying to swap. All in all, don't do it. The initialization is a one-time-cost, which is not the costly thing. You are defeating the safe purpose of Rust for nothing IMHO. — hellow, May 21 '19 at 11:53
it's not a production implementation :), I was doing this to get a better grasp of rust. I understand the issue now as you explained. I believe I've fixed it, I've edited the question. I am still a little interested why this doesn't happen with the string. Maybe rusts uses small-string-optimization and creates a stack allocated string? — Marin Veršić, May 21 '19 at 11:59
It doesn't happen with the `String` because this is Undefined Behaviour. You can't predict what will happen or when. It could break on a different operating system or different CPU architecture or in a future Rust compiler. — Peter Hall, May 21 '19 at 12:02

Brent Kerby · Accepted Answer · 2019-05-21T14:01:57.627

2

When you run *unsafe { self.buff.get_unchecked_mut(idx) } = elem; to replace an uninitialized Box or String, it will run drop on this uninitialized Box or String. Box and String both contain a pointer to the part of the heap where their data is supposed to be stored, and when they are dropped, it will deallocate the memory at this location.

By dropping an uninitialized Box or String, it will be deallocating memory at an arbitrary location as the uninitialized pointer could be anything. It is undefined behavior to deallocate memory which has not been allocated.

edited May 21 '19 at 14:01

answered May 21 '19 at 13:59

Brent Kerby

1,397
8
14

thanks, I didn't realize there is a move of old value involved when assigning new value to a pointer. It all makes sense and, as I said in the edit section of my question, by running `unsafe {std::ptr::write(self.buff.get_unchecked_mut(idx), elem)};` old value is not moved and consequently it isn't dropped and everything works – Marin Veršić May 22 '19 at 06:51

Unsafe queue implementation

1 Answers1