首页 / 技术问答 / Rust问答列表 / 问答详情

带有不安全 rust 的链表泄漏内存

我的链表具有以下内存布局:

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

虚拟 node 在插入时缓慢初始化，prev和next指针指向自身.插入后，prev和next指针将充当tail和head指针.

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 .卢比

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

使用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);
    }
}

输出目标:

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 │ __ __ __ __ __ __ __ __                         │ ░░░░░░░░
}

我有14个内存泄漏，但单独运行test_node个 case 不会泄漏任何内存.通过进一步调试，我可以确保NodePtr::dealloc确实正常运行("deallocation"按预期打印了5次.请注意，此方法不会取消分配虚拟 node ，我会在Drop impl中手动取消分配虚拟 node ).代码逻辑似乎工作正常.这可能是某种微妙的未定义行为吗？

推荐答案

这是您的内存泄漏:

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

NodePtr::dummy()分配一个 node ，返回原始指针，并且从不销毁它.这里的问题是它的编写方式always无条件地运行dummy().

这是修复方法:

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

我是怎么找到的

当查看RUSTFLAGS=-Zsanitizer=address cargo +nightly test的输出时，我意识到泄漏的内存总是在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

然后，我将使用量降到了最低限度.我意识到它已经发生在一个单一的push_front():

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

然后，我在所有分配和解除分配中添加了println()个:

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

当运行前面显示的main()时，我看到了以下输出:

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

分配0x603000000070和0x6030000000a0似乎很好，这是dummy元素和第一个 node .各自的交易额似乎也相匹配，dealloc: 0x6030000000a0和drop: 0x603000000070.但还有三笔不应该存在的拨款，0x6030000000d0、0x603000000100和0x603000000130.

所以我接下来要做的是使用VSCode和惊人的rust-analyzer插件在raw_alloc()中设置一个断点.我在调试中运行，dummy元素达到第一个raw_alloc()，然后第一个 node 元素达到第二个，然后第三个.我看了看第三个的调用堆栈，发现:

  • 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

然后我想，'why does 100 get called again in 101?'；就在那时，我注意到了get_or_insert().

我希望此分析有助于提高您自己的调试技能:)

Rust相关问答推荐

在一个tauri协议处理程序中调用一个rectuc函数的推荐技术是什么？

定义采用更高级类型泛型的性状

Rust类似功能是C++命名空间吗？

无法从流中读取Redis请求

如何计算迭代器适配器链中过滤的元素的数量

对于已经被认为是未定义行为的相同数据，纯粹存在`&；[u32]`和`&；mut[u32]`吗？

为什么'；t std：：cell：：ref使用引用而不是非空？

在IntoIter上调用.by_ref().Take().rev()时会发生什么情况

如何go 除多余的(0..)在迭代中，当它不被使用时？

无符号整数的Rust带符号差

解析程序无法在Cargo 发布中 Select 依赖版本

装箱特性如何影响传递给它的参数的生命周期 ？(举一个非常具体的例子)

信号量释放后 Rust 输出挂起线程

可选包装枚举的反序列化

通过写入 std：：io：：stdout() 输出不可见

如何正确使用git2：：Remote：：push？

`tokio：：pin` 如何改变变量的类型？

在 RefCell 上borrow

基于名称是否存在的条件编译

您不能borrow 对只读值的可变引用

实用课程推荐
相关教程推荐
休闲君评测 |  TOOLFK工具网 |  古诗文网 |  良许Linux教程网 |  Python之禅 |  红色石头 |  入党申请书 | 

© 2020 Hi LearnFk 意见反馈 免责声明 关于我们 桂ICP备11002319号-3 友链&广告位+QQ: 1963612630