CODEWITHSUNDEEP
data-structuresrustlinked-listunsafe
charlieh_7
charlieh_7

Reputation: 334

Linked-list with unsafe rust leaks memory

My linked list has this memory layout:

[dummy] -> (prev, ?DUMMY?, next) <-> (prev, A, next) <-> (prev, B, next)
            ^                                                         ^
            +---------------------------------------------------------+

The dummy node is lazily initialized upon insertion, with prev and next pointer pointing towards itself. After insertion, the prev and next pointer will act as the tail and head pointer.

use std::marker::PhantomData;

use self::node::NodePtr;

mod node;

#[derive(Debug)]
pub struct LinkedList<T> {
    dummy: Option<NodePtr<T>>,
    len: usize,
    _phantom: PhantomData<T>,
}

impl<T> Default for LinkedList<T> {
    fn default() -> Self {
        Self {
            dummy: None,
            len: 0,
            _phantom: PhantomData,
        }
    }
}

impl<T> LinkedList<T> {
    pub fn new() -> Self {
        Default::default()
    }

    pub(crate) fn inner(&mut self) -> NodePtr<T> {
        *self.dummy.get_or_insert(NodePtr::dummy())
    }

    pub fn len(&self) -> usize {
        self.len
    }

    pub fn is_empty(&self) -> bool {
        self.len() == 0
    }

    pub fn push_front(&mut self, elem: T) {
        let dummy = self.inner();
        let head = dummy.next();
        let new_head = NodePtr::alloc(dummy, elem, head);
        head.set_prev(new_head);
        dummy.set_next(new_head);

        self.len += 1;
    }

    pub fn pop_front(&mut self) -> Option<T> {
        let dummy = self.inner();
        unsafe { dummy.next().dealloc() }.map(|(_, elem, new_head)| {
            dummy.set_next(new_head);
            new_head.set_prev(dummy);

            self.len -= 1;
            elem
        })
    }
}

impl<T> Drop for LinkedList<T> {
    fn drop(&mut self) {
        while self.pop_front().is_some() {}
        let dummy = self.dummy.take().unwrap();
        unsafe {
            let _ = Box::from_raw(dummy.as_ptr());
        }
    }
}

node.rs

use std::{
    fmt::Debug,
    mem::MaybeUninit,
    ops::Not,
    ptr::{self, NonNull},
};

#[derive(Debug)]
pub struct Node<T> {
    prev: NodePtr<T>,
    next: NodePtr<T>,
    elem: MaybeUninit<T>,
}

pub struct NodePtr<T> {
    ptr: NonNull<Node<T>>,
}

impl<T> Debug for NodePtr<T> {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        f.debug_struct("NodePtr").field("ptr", &self.ptr).finish()
    }
}

impl<T> Clone for NodePtr<T> {
    fn clone(&self) -> Self {
        Self { ptr: self.ptr }
    }
}

impl<T> Copy for NodePtr<T> {}

impl<T> PartialEq for NodePtr<T> {
    fn eq(&self, other: &Self) -> bool {
        ptr::eq(self.as_ptr(), other.as_ptr())
    }
}

impl<T> Eq for NodePtr<T> {}

impl<T> NodePtr<T> {
    pub unsafe fn dangling() -> Self {
        Self {
            ptr: NonNull::dangling(),
        }
    }

    pub unsafe fn raw_alloc(prev: Self, elem: MaybeUninit<T>, next: Self) -> Self {
        let ptr = Box::into_raw(Box::new(Node { prev, next, elem }));
        let ptr = NonNull::new_unchecked(ptr);
        Self { ptr }
    }

    pub fn alloc(prev: Self, elem: T, next: Self) -> Self {
        unsafe { Self::raw_alloc(prev, MaybeUninit::new(elem), next) }
    }

    pub fn dummy() -> Self {
        unsafe {
            let dangling = Self::dangling();

            let dummy = Self::raw_alloc(dangling, MaybeUninit::uninit(), dangling);
            dummy.set_prev(dummy);
            dummy.set_next(dummy);

            dummy
        }
    }

    pub fn prev(self) -> Self {
        unsafe { (*self.as_ptr()).prev }
    }

    pub fn set_prev(self, ptr: Self) {
        unsafe {
            (*self.as_ptr()).prev = ptr;
        }
    }

    pub fn next(self) -> Self {
        unsafe { (*self.as_ptr()).next }
    }

    pub fn set_next(self, ptr: Self) {
        unsafe {
            (*self.as_ptr()).next = ptr;
        }
    }

    pub fn is_dummy(self) -> bool {
        self.prev() == self.next() && self.prev() == self
    }

    pub fn as_ptr(self) -> *mut Node<T> {
        self.ptr.as_ptr()
    }

    pub unsafe fn as_ref<'a>(self) -> &'a Node<T> {
        self.ptr.as_ref()
    }

    pub unsafe fn as_mut<'a>(mut self) -> &'a mut Node<T> {
        self.ptr.as_mut()
    }

    pub fn get_raw(self) -> Option<NonNull<T>> {
        self.is_dummy()
            .not()
            .then(|| unsafe { NonNull::new_unchecked((*self.as_ptr()).elem.as_mut_ptr()) })
    }

    pub unsafe fn get<'a>(self) -> Option<&'a T> {
        self.get_raw().map(|ptr| ptr.as_ref())
    }

    pub unsafe fn get_mut<'a>(self) -> Option<&'a mut T> {
        self.get_raw().map(|mut ptr| ptr.as_mut())
    }

    pub unsafe fn dealloc(self) -> Option<(Self, T, Self)> {
        self.is_dummy().not().then(|| {
            // println!("Deallocating...");
            let Node { prev, next, elem } = *Box::from_raw(self.as_ptr());
            (prev, elem.assume_init(), next)
        })
    }
}

Running the test cases with miri:

#[cfg(test)]
mod test {
    use super::{node::NodePtr, LinkedList};

    #[test]
    fn test_node() {
        let dummy = NodePtr::dummy();
        let node = NodePtr::alloc(dummy, 100, dummy);

        dummy.set_next(node);
        dummy.set_prev(node);

        let (_, elem, _) = unsafe { node.dealloc() }.unwrap();
        unsafe {
            Box::from_raw(dummy.as_ptr());
        }
        assert_eq!(elem, 100);
    }

    #[test]
    fn test_basic_front() {
        let mut list = LinkedList::new();

        // Try to break an empty list
        assert_eq!(list.len(), 0);
        assert_eq!(list.pop_front(), None);
        assert_eq!(list.len(), 0);

        // Try to break a one item list
        list.push_front(10);
        assert_eq!(list.len(), 1);
        assert_eq!(list.pop_front(), Some(10));
        assert_eq!(list.len(), 0);
        assert_eq!(list.pop_front(), None);
        assert_eq!(list.len(), 0);

        // Mess around
        list.push_front(10);
        assert_eq!(list.len(), 1);
        list.push_front(20);
        assert_eq!(list.len(), 2);
        list.push_front(30);
        assert_eq!(list.len(), 3);
        assert_eq!(list.pop_front(), Some(30));
        assert_eq!(list.len(), 2);
        list.push_front(40);
        assert_eq!(list.len(), 3);
        assert_eq!(list.pop_front(), Some(40));
        assert_eq!(list.len(), 2);
        assert_eq!(list.pop_front(), Some(20));
        assert_eq!(list.len(), 1);
        assert_eq!(list.pop_front(), Some(10));
        assert_eq!(list.len(), 0);
        assert_eq!(list.pop_front(), None);
        assert_eq!(list.len(), 0);
        assert_eq!(list.pop_front(), None);
        assert_eq!(list.len(), 0);
    }
}

miri output:

The following memory was leaked: alloc86121 (Rust heap, size: 24, align: 8) {
    0x00 │ ╾0x1f2da8[a86121]<205762> (8 ptr bytes)╼ ╾0x1f2da8[a86121]<205762> (8 ptr bytes)╼ │ ╾──────╼╾──────╼
    0x10 │ __ __ __ __ __ __ __ __                         │ ░░░░░░░░
}
alloc86346 (Rust heap, size: 24, align: 8) {
    0x00 │ ╾0x1f3ef0[a86346]<206225> (8 ptr bytes)╼ ╾0x1f3ef0[a86346]<206225> (8 ptr bytes)╼ │ ╾──────╼╾──────╼
    0x10 │ __ __ __ __ __ __ __ __                         │ ░░░░░░░░
}
alloc86565 (Rust heap, size: 24, align: 8) {
    0x00 │ ╾0x1f4ff8[a86565]<206712> (8 ptr bytes)╼ ╾0x1f4ff8[a86565]<206712> (8 ptr bytes)╼ │ ╾──────╼╾──────╼
    0x10 │ __ __ __ __ __ __ __ __                         │ ░░░░░░░░
}
alloc86723 (Rust heap, size: 24, align: 8) {
    0x00 │ ╾0x1f5c58[a86723]<207063> (8 ptr bytes)╼ ╾0x1f5c58[a86723]<207063> (8 ptr bytes)╼ │ ╾──────╼╾──────╼
    0x10 │ __ __ __ __ __ __ __ __                         │ ░░░░░░░░
}
alloc86946 (Rust heap, size: 24, align: 8) {
    0x00 │ ╾0x1f6da8[a86946]<207524> (8 ptr bytes)╼ ╾0x1f6da8[a86946]<207524> (8 ptr bytes)╼ │ ╾──────╼╾──────╼
    0x10 │ __ __ __ __ __ __ __ __                         │ ░░░░░░░░
}
alloc87169 (Rust heap, size: 24, align: 8) {
    0x00 │ ╾0x1f7f60[a87169]<207985> (8 ptr bytes)╼ ╾0x1f7f60[a87169]<207985> (8 ptr bytes)╼ │ ╾──────╼╾──────╼
    0x10 │ __ __ __ __ __ __ __ __                         │ ░░░░░░░░
}
alloc87393 (Rust heap, size: 24, align: 8) {
    0x00 │ ╾0x1f9100[a87393]<208448> (8 ptr bytes)╼ ╾0x1f9100[a87393]<208448> (8 ptr bytes)╼ │ ╾──────╼╾──────╼
    0x10 │ __ __ __ __ __ __ __ __                         │ ░░░░░░░░
}
alloc87599 (Rust heap, size: 24, align: 8) {
    0x00 │ ╾0x1fa1b0[a87599]<208910> (8 ptr bytes)╼ ╾0x1fa1b0[a87599]<208910> (8 ptr bytes)╼ │ ╾──────╼╾──────╼
    0x10 │ __ __ __ __ __ __ __ __                         │ ░░░░░░░░
}
alloc87823 (Rust heap, size: 24, align: 8) {
    0x00 │ ╾0x1fb2f8[a87823]<209373> (8 ptr bytes)╼ ╾0x1fb2f8[a87823]<209373> (8 ptr bytes)╼ │ ╾──────╼╾──────╼
    0x10 │ __ __ __ __ __ __ __ __                         │ ░░░░░░░░
}
alloc88030 (Rust heap, size: 24, align: 8) {
    0x00 │ ╾0x1fc3a8[a88030]<209837> (8 ptr bytes)╼ ╾0x1fc3a8[a88030]<209837> (8 ptr bytes)╼ │ ╾──────╼╾──────╼
    0x10 │ __ __ __ __ __ __ __ __                         │ ░░░░░░░░
}
alloc88237 (Rust heap, size: 24, align: 8) {
    0x00 │ ╾0x1fd3a8[a88237]<210301> (8 ptr bytes)╼ ╾0x1fd3a8[a88237]<210301> (8 ptr bytes)╼ │ ╾──────╼╾──────╼
    0x10 │ __ __ __ __ __ __ __ __                         │ ░░░░░░░░
}
alloc88454 (Rust heap, size: 24, align: 8) {
    0x00 │ ╾0x1fe4e8[a88454]<210788> (8 ptr bytes)╼ ╾0x1fe4e8[a88454]<210788> (8 ptr bytes)╼ │ ╾──────╼╾──────╼
    0x10 │ __ __ __ __ __ __ __ __                         │ ░░░░░░░░
}
alloc88613 (Rust heap, size: 24, align: 8) {
    0x00 │ ╾0x1ff160[a88613]<211141> (8 ptr bytes)╼ ╾0x1ff160[a88613]<211141> (8 ptr bytes)╼ │ ╾──────╼╾──────╼
    0x10 │ __ __ __ __ __ __ __ __                         │ ░░░░░░░░
}
alloc88773 (Rust heap, size: 24, align: 8) {
    0x00 │ ╾0x1ffe18[a88773]<211496> (8 ptr bytes)╼ ╾0x1ffe18[a88773]<211496> (8 ptr bytes)╼ │ ╾──────╼╾──────╼
    0x10 │ __ __ __ __ __ __ __ __                         │ ░░░░░░░░
}

I got 14 memory leaks but running the test_node case alone doesn't leak any memory. With some further debugging, I can assure that NodePtr::dealloc does run properly ("Deallocating" got printed for 5 times as expected. Note that this method won't be deallocating the dummy node, and I would deallocate the dummy node manually in the Drop impl). The code logic seems to work correctly. Could it be some kind of subtle undefined behavior?

Upvotes: 2

Views: 357

Answers (1)

Finomnis
Finomnis

Reputation: 22728

Here is your memory leak:

pub(crate) fn inner(&mut self) -> NodePtr<T> {
    *self.dummy.get_or_insert(NodePtr::dummy())
}

NodePtr::dummy() allocates a node, returns the raw pointer and never destroys it. The problem here is that the way it is written it always runs dummy() unconditionally.

This is the fix:

pub(crate) fn inner(&mut self) -> NodePtr<T> {
    *self.dummy.get_or_insert_with(|| NodePtr::dummy())
}

How I found it

When looking at the output of RUSTFLAGS=-Zsanitizer=address cargo +nightly test I realized that the leaked memory always gets initialized in NodePtr::raw_alloc():

Direct leak of 24 byte(s) in 1 object(s) allocated from:
    #0 0x55c80616ed8e in malloc /rustc/llvm/src/llvm-project/compiler-rt/lib/asan/asan_malloc_linux.cpp:69:3
    #1 0x55c8061a27f9 in alloc::alloc::alloc::ha05f706f7dab9e22 /rustc/06754d8852bea286a3a76d373ccd17e66afb5a8b/library/alloc/src/alloc.rs:171:73
    #2 0x55c8061a27f9 in alloc::alloc::Global::alloc_impl::h5cfa6b00beb3203a /rustc/06754d8852bea286a3a76d373ccd17e66afb5a8b/library/alloc/src/alloc.rs:171:73
    #3 0x55c8061a1e3d in _$LT$alloc..alloc..Global$u20$as$u20$core..alloc..Allocator$GT$::allocate::h6ea44ef9df335707 /rustc/06754d8852bea286a3a76d373ccd17e66afb5a8b/library/alloc/src/alloc.rs:320:11
    #4 0x55c8061a1e3d in alloc::alloc::exchange_malloc::h91c76b5bf53597fd /rustc/06754d8852bea286a3a76d373ccd17e66afb5a8b/library/alloc/src/alloc.rs:320:11
    #5 0x55c80619d43f in alloc::boxed::Box$LT$T$GT$::new::hba6cd0555301746a /rustc/06754d8852bea286a3a76d373ccd17e66afb5a8b/library/alloc/src/boxed.rs:215:9
    #6 0x55c80619d43f in rust_tmp::node::NodePtr$LT$T$GT$::raw_alloc::hc476ac99ddaa5b56 /home/martin/work/rust-tmp/src/node.rs:49:33
    #7 0x55c80619d72b in rust_tmp::node::NodePtr$LT$T$GT$::dummy::h8b4ac6a33651e5fd /home/martin/work/rust-tmp/src/node.rs:62:25
    #8 0x55c806199a04 in rust_tmp::test::test_basic_front::hbb4f6a4888143b15 /home/martin/work/rust-tmp/src/lib.rs:104:20
    #9 0x55c80619fbe9 in rust_tmp::test::test_basic_front::_$u7b$$u7b$closure$u7d$$u7d$::h970eafca0aaa30ba /home/martin/work/rust-tmp/src/lib.rs:93:5
    #10 0x55c8061d94b2 in core::ops::function::FnOnce::call_once::ha04ab83b16462938 /rustc/06754d8852bea286a3a76d373ccd17e66afb5a8b/library/core/src/ops/function.rs:248:5
    #11 0x55c8061d94b2 in test::__rust_begin_short_backtrace::h994ad9d2e6435f98 /rustc/06754d8852bea286a3a76d373ccd17e66afb5a8b/library/test/src/lib.rs:572:5

Then, I reduced the usage down to a minimum. I realized it already happens with a single push_front():

fn main() {
    let mut list = LinkedList::new();
    list.push_front(10);
    dbg!(list.pop_front());
    dbg!(list.pop_front());
}

I then added println()s to all allocations and deallocations:

    pub unsafe fn raw_alloc(prev: Self, elem: MaybeUninit<T>, next: Self) -> Self {
        let ptr = Box::into_raw(Box::new(Node { prev, next, elem }));
        println!("raw_alloc: {:p}", ptr);
        let ptr = NonNull::new_unchecked(ptr);
        Self { ptr }
    }

    // ...

    pub unsafe fn dealloc(self) -> Option<(Self, T, Self)> {
        self.is_dummy().not().then(|| {
            let ptr = self.as_ptr();
            println!("dealloc: {:p}", ptr);
            let Node { prev, next, elem } = *Box::from_raw(ptr);
            (prev, elem.assume_init(), next)
        })
    }

impl<T> Drop for LinkedList<T> {
    fn drop(&mut self) {
        while self.pop_front().is_some() {}
        let dummy = self.dummy.take().unwrap();
        unsafe {
            let ptr = dummy.as_ptr();
            println!("drop: {:p}", ptr);
            let _ = Box::from_raw(ptr);
        }
    }
}

I saw the following output, when running the main() shown earlier:

raw_alloc: 0x603000000070
raw_alloc: 0x6030000000a0
raw_alloc: 0x6030000000d0
dealloc: 0x6030000000a0
[src/main.rs:78] list.pop_front() = Some(
    10,
)
raw_alloc: 0x603000000100
[src/main.rs:79] list.pop_front() = None
raw_alloc: 0x603000000130
drop: 0x603000000070

The allocations 0x603000000070 and 0x6030000000a0 seem fine, that's the dummy element and the first node. The respective deallocations also seem to match, dealloc: 0x6030000000a0 and drop: 0x603000000070. But there are three more allocations that shouldn't be there, 0x6030000000d0, 0x603000000100 and 0x603000000130.

So what I did next is to set a breakpoint in raw_alloc() using VSCode and the amazing rust-analyzer plugin. I ran in debug, hit the first raw_alloc() for the dummy element, then the second for the first node element, and then the third. I looked at the callstack of the third, and saw:

  • rust_tmp::node::NodePtr<T>::raw_alloc
  • rust_tmp::node::NodePtr<T>::dummy
  • rust_tmp::LinkedList<T>::inner
  • rust_tmp::LinkedList<T>::pop_front
  • rust_tmp::main

I then thought, 'why does dummy() get called again in inner()?'; and that's when I noticed the get_or_insert().

I hope this analysis helps to improve your own debugging skills :)

Upvotes: 2

Related Questions