Небезопасная реализация очереди

Я пытаюсь создать небезопасную, но более производительную ArrayQueue реализацию. После того, как я добавил тестовые примеры, один из них выдает ошибку сегментации. Вот моя простая минимальная реализация:

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")));
    }
}

Я считаю, что делаю правильное отключение, чтобы предотвратить утечку памяти.

Я приложил два тестовых примера, один из которых работает, но другой приводит к сбою из-за недопустимой ссылки на память.

Он дает сбой внутри метода add (*unsafe {self.buff.get_unchecked_mut(idx)} = elem;), и я подозреваю, что это происходит из-за того, что я каким-то образом пытаюсь выполнить запись в недопустимую область памяти.
Я специально использовал объекты, выделенные кучей, для векторных элементов в тесте, но, к моему удивлению, String работает правильно а Box - нет.

Я хотел бы понять, можно ли сделать такую ​​небезопасную реализацию и почему в настоящее время она не работает?

Изменить


Я решил проблему, заменив *unsafe {self.buff.get_unchecked_mut(idx)} = elem; на unsafe {std::ptr::write(self.buff.get_unchecked_mut(idx), elem)};.

Теперь я хотел бы понять, почему это работает, а предыдущая версия - нет.


person Marin Veršić    schedule 21.05.2019    source источник
comment
Я думаю, что это дубликат stackoverflow.com/questions/31360993 или stackoverflow.com/questions/55741517. TL; DR - вы сбрасываете значения, которые не были инициализированы. Вы устанавливаете длину как число, но значения в этом диапазоне являются неинициализированной памятью.   -  person hellow    schedule 21.05.2019
comment
нет, я не думаю, что здесь есть проблема с вызовом drop для неинициализированной памяти. Насколько я понимаю, проблема возникает в методе add при присвоении значения неинициализированной памяти.   -  person Marin Veršić    schedule 21.05.2019
comment
В этом проблема этого небезопасного кода. Вы отбрасываете элемент, когда назначаете новые значения индексу. Если вы сделаете buff.resize_with(size, T::default); вместо set_len, сбой больше не будет.   -  person hellow    schedule 21.05.2019
comment
спасибо, но если предыдущее значение теряется при присвоении нового значения, почему это работает для test0, где также есть объект (строка), выделенный кучей? Я понимаю, что могу использовать значения по умолчанию, я специально пытался этого избежать   -  person Marin Veršić    schedule 21.05.2019
comment
Чистое везение. Как уже говорилось, вы получаете доступ к неинициализированной памяти, что является неопределенным поведением. Не делайте этого;) Вы можете использовать mem::forget, чтобы не вызывать деструктор элемента, который вы пытаетесь поменять местами. В общем, не делай этого. Инициализация - это единовременные затраты, которые не являются дорогостоящими. ИМХО, вы зря уничтожаете безопасную цель Rust.   -  person hellow    schedule 21.05.2019
comment
это не производственная реализация :), я делал это, чтобы лучше понять ржавчину. Теперь я понимаю проблему, как вы объяснили. Кажется, исправил, вопрос отредактировал. Меня все еще немного интересует, почему этого не происходит со строкой. Может быть, rusts использует оптимизацию небольших строк и создает строку, выделенную стеком?   -  person Marin Veršić    schedule 21.05.2019
comment
Этого не происходит с String, потому что это неопределенное поведение. Вы не можете предсказать, что и когда произойдет. Он может сломаться в другой операционной системе, другой архитектуре процессора или в будущем компиляторе Rust.   -  person Peter Hall    schedule 21.05.2019


Ответы (1)


Когда вы запускаете *unsafe { self.buff.get_unchecked_mut(idx) } = elem; для замены неинициализированного Box или String, он будет запускать drop на этом неинициализированном Box или String. Box и String оба содержат указатель на часть кучи, где предполагается хранить их данные, и когда они удаляются, он освобождает память в этом месте.

Отбрасывая неинициализированный Box или String, он освобождает память в произвольном месте, поскольку неинициализированный указатель может быть любым. Освобождение памяти, которая не была выделена, является неопределенным.

person Brent Kerby    schedule 21.05.2019
comment
спасибо, я не осознавал, что при присвоении нового значения указателю происходит перемещение старого значения. Все это имеет смысл, и, как я сказал в разделе редактирования своего вопроса, при запуске unsafe {std::ptr::write(self.buff.get_unchecked_mut(idx), elem)}; старое значение не перемещается, и, следовательно, оно не удаляется, и все работает - person Marin Veršić; 22.05.2019