Calling `fast_clear` causes a memory leak when using `Rc<T>`, even if `force_unlink` is called on each linked object.

[icmccorm]

Miri found memory leaks in the following tests:

• xor_linked_list::tests::test_force_unlink
• linked_list::tests::test_force_unlink
• singly_linked_list::tests::test_fast_clear
• rbtree::tests::test_fast_clear

All assertions pass. Each test has a similar structure; here's a minimal example using LinkedList that recreates the issue:

let mut l = LinkedList::new(ObjAdapter1::new());
      
let a = make_obj(1);

l.cursor_mut().insert_before(a.clone());

l.fast_clear();

unsafe {
    a.link1.force_unlink();
}

When executing this, Miri detects that a is leaked and provides the following output:

The following memory was leaked: alloc94446 (Rust heap, size: 56, align: 8) {
    0x00 │ 01 00 00 00 00 00 00 00 01 00 00 00 00 00 00 00 │ ................
    0x10 │ 01 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 │ ................
    0x20 │ 01 00 00 00 00 00 00 00 01 00 00 00 00 00 00 00 │ ................
    0x30 │ 01 00 00 00 __ __ __ __                         │ ....░░░░
}

I originally thought this was due to unwrapping the clone in insert_before(...). To test this, I switched to using a modified ObjAdapter3 with Weak instead of Rc, and passed Rc::downgrade(&a) as a parameter to insert_before instead of making a clone. However, this did not correct the issue.

Given the descriptions of both force_unlink and fast_clear, I'm guessing that there are always going to be some precautions necessary to avoid memory leaks here. Could you confirm if this is a bug, and if not, what additional steps a user would need to take to avoid this type of leak when using these methods? Thanks!

[Amanieu]

I think this is not so much a bug as poor API design. force_unlink was originally designed to be used with UnsafeRef where the lifetimes of objects are manually managed: you could fast_clear a list and then re-use the existing objects in another list by force_unlinking them.

This was never designed to work with proper pointer types such as Box or Rc.

[icmccorm]

Gotcha! To clarify my thought process here:

I'm new to working with Rc, so I had thought that you could get around this with a change to using Weak, but from the docs:

Since a Weak reference does not count towards ownership, it will not prevent the value stored in the allocation from being dropped... Note however that a Weak reference does prevent the allocation itself (the backing store) from being deallocated.

And, sure enough, the same kind of leak will happen with a pretty minimal example:

use std::{rc::{Rc, Weak}};
fn main() {
    let a = Rc::new(Box::new(1));
    Weak::into_raw(Rc::downgrade(&a));
}

The pull request above eliminates the leak by switching away from Rc to UnsafeRef for the these test cases.