Where did I go wrong with my unsafe doubly linked list?

Question

use std::{mem, ptr};

pub struct DList<T> {
    dummy: DNode<T>,
}

struct DNode<T> {
    data: T,
    next: *mut DNode<T>,
    prev: *mut DNode<T>,
}

impl<T> DList<T> {
    pub fn new() -> DList<T> {
        unsafe {
            let mut dummy = DNode {
                data: mem::zeroed(),
                next: ptr::null_mut(),
                prev: ptr::null_mut(),
            };
            dummy.prev = &mut dummy;
            dummy.next = &mut dummy;
            DList { dummy }
        }
    }

    pub fn push_front(&mut self, data: T) {
        let mut new_node = DNode {
            data,
            next: ptr::null_mut(),
            prev: ptr::null_mut(),
        };
        let old_front = self.dummy.next;
        new_node.prev = &mut self.dummy;
        self.dummy.next = &mut new_node;
        new_node.next = old_front;
        unsafe {
            (*old_front).prev = &mut new_node;
        }
    }

    pub fn pop_front(&mut self) -> T {
        let front = self.dummy.next;
        let new_front = unsafe { (*front).next };
        self.dummy.next = new_front;
        unsafe {
            (*new_front).prev = &mut self.dummy;
            front.read().data
        }
    }
}

I tried to implement a circular doubly linked list with unsafe rust. I design my data structure with pointers and decided to have a dummy node for convenience.

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

    #[test]
    fn test_push_front_pop_front() {
        let mut dlist = DList::new();
        dlist.push_front(1);
        dlist.push_front(2);
        dlist.push_front(3);
        assert_eq!(dlist.pop_front(), 3);
        assert_eq!(dlist.pop_front(), 2);
        assert_eq!(dlist.pop_front(), 1);
    }
}

But when testing it, the doubly linked list does not pop the elements in the correct way. It always pops the last element added to it, which in this case is 3. I expected it to pop 3, 2 ,1, but it keeps popping 3.

I wonder if I'm using unsafe rust in a wrong way.

Anyone trying to write a linked list in rust should read this: rust-unofficial.github.io/too-many-lists I dunno what is wrong, but this here is unsound: data: mem::zeroed(). You can use zeroed for MaybeUninit<T> but not for T. It's not the problem in your specific test, though, since 0 is valid for i32. — drewtato
– drewtato, Commented Jan 12, 2024 at 6:02
And remember to read the Rustonomicon: doc.rust-lang.org/nomicon You can't just write unsafe code and expect it to work. The rules are not obvious (otherwise we wouldn't need unsafe) and it is hard to detect when they've been broken. — drewtato
– drewtato, Commented Jan 12, 2024 at 6:06
Your code has quite a lot of UB, including two dangling pointers and an undefined data just in the construction of the dummy node. There is a tool that helps catch some of these bugs that is called miri, and you can try it here on your code to see some of the errors it reports. As general guidelines, remember that even though raw pointers don't have the usual rules for borrows enforced by the compiler, similar rules still apply but you have to ensure they hold. — jthulhu
– jthulhu, Commented Jan 12, 2024 at 7:48

Jmb · Accepted Answer · 2024-01-12 07:48:56Z

3

This:

pub fn push_front(&mut self, data: T) {
    let mut new_node = DNode {
        data,
        next: ptr::null_mut(),
        prev: ptr::null_mut(),
    };
    let old_front = self.dummy.next;
    new_node.prev = &mut self.dummy;
    self.dummy.next = &mut new_node;
    new_node.next = old_front;
    unsafe {
        (*old_front).prev = &mut new_node;
    }
}

is horribly broken: it's pushing a reference to a local variable in your linked list (new_node), but that local variable is destroyed as soon as the function returns, leaving you with a dangling pointer. In this simple program, the memory is only reused the next time you call push_front, where the new item winds up with the same address as the others, which is why pop_front always sees the same value. In a more complicated example you would see seemingly random values, depending on what other functions you would have called.

A bit of advice: don't do linked lists, they are extremely hard to get right and they offer no benefits on modern computers. In safe Rust, at least the compiler keeps you from shooting yourself in the foot with them, but in unsafe Rust or most other languages you will only end up with faulty, hard to debug code.

answered Jan 12, 2024 at 7:48

Jmb

24.1k2 gold badges39 silver badges70 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

user4815162342 Over a year ago

In case it's not obvious, the correct way to allocate new_node would be somehing like Box::into_raw(Box::new(Dnode { ... })). pop_front() should use the matching Box::from_raw().

Collectives™ on Stack Overflow

Where did I go wrong with my unsafe doubly linked list?

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related