Problem with lifetimes in Rc<RefCell<T>>

I'm trying to get nth node of LinkedList and getting this error. Please explain what is wrong with my code?
image
The error:
temporary value dropped while borrowed

creates a temporary which is freed while still in use

note: consider using a let binding to create a longer lived valuerustc(E0716)

linked_list.rs(31, 26): creates a temporary which is freed while still in use

linked_list.rs(31, 44): temporary value is freed at the end of this statement

linked_list.rs(31, 44): ... and the borrow might be used here, when that temporary is dropped and runs the destructor for type std::cell::Ref<'_, linked_list::Node<T>>

The return value of borrow() is a type known as Ref, and this type has a destructor. You cannot access anything behind the RefCell after the destructor runs, but since you don't store the Ref, it is immediately dropped.

If next is an Rc, you could clone it.

Ahh yes. That make sense. But coping Rc in this case seems like an overhead. Is there a way to get &T from Ref (maybe using unsafe code)

No.

Ok yes technically there is Ref::leak but it doesn't solve the problem at hand.

Fixed it like this. Thanks for help
image

As written this nth_node is unsound (not merely unsafe, "unsound" is worse). If any other NodeRefs exist and might be borrowed mutably, this code has undefined behavior. If you're relying on the caller to not do that, nth_node should be an unsafe fn to document that it relies on invariants that can't be checked by the compiler.

Have you read Learning Rust With Entirely Too Many Linked Lists?

1 Like

The correct solution is to clone the Rc. If anyone has a mutable borrow of any node in the list, your code triggers undefined behavior.

2 Likes

Yes, I did read it, just trying to implement it myself. Could you please give an example where it will produce UB? From what i can see, just cloning nth node is enough. P.s. i'm new to system programming langs like rust.

Could you please give me an example of UB. Is it related to multi threaded scenarios? Also, it did clone Rc, but only nth node is clone as it is the only node returned.

No, it's not. Parallelism is not required for shared mutability to trigger UB. Consider this piece of perfectly single-threaded code:

let mut values: Vec<u32> = vec![1, 2, 3, 4];
let first_ptr = &values[0] as *const _;
values.extend(5..16);
println!("{}", unsafe { *first_ptr });

This is called "iterator invalidation" in other languages. What happens here is that the first_ptr pointer refers to the first element of the vector. However, when a new value is pushed to the vector, it may reallocate its internal buffer, invalidating the pointer.

So the problem is that someone can still observe the vector by holding a pointer into it while it is being mutated. Normally, if you only use regular &T references, the borrow checker catches this problem at compile time. However, *const T and *mut T pointers are not borrow checked (and as such, they are unsafe to dereference) – therefore it's possible to perform such an invalid operation with them in unsafe code.


As a side note, please don't post code as an image. Post it as text, which is what it is. Posting code as an image prevents it from being copied and tried out, and it's also inaccessible to blind people using screen reader software.

1 Like

The UB happens because mutable references are guaranteed to be exclusive. I can you show an example that fails in miri if you post it as text instead of an image.

In your example first_ptr is used after mutation. In my code pointers only used inside nth_node() method, and returned node is cloned, it is like abstraction over unsafe code, unsafe is only affect current method, or am I missing something?

use std::rc::Rc;
use std::cell::RefCell;
use std::fmt;

pub struct List<T> {
    head: Link<T>,
    size: usize,
}

struct Node<T> {
    value: Rc<T>,
    next: Link<T>,
}

type NodeRef<T> = Rc<RefCell<Node<T>>>;

type Link<T> = Option<NodeRef<T>>;


impl<T> List<T> {
    pub fn new () -> List<T> {
        List { head: None, size: 0 }
    }

    fn new_node_ref(value: T, next: Link<T>) -> NodeRef<T> {
        Rc::new(RefCell::new(Node { value: Rc::new(value), next }))
    }

    fn incorrect_index_message(index: usize) -> String {
        format!("Incorrect index - {}", index)
    }

    pub fn push(&mut self, value: T) {
        let new_node = Self::new_node_ref(value, None);
        if self.size == 0 {
            self.head = Some(new_node);
        } else {
            let last_node = self.nth_node(self.size - 1);
            last_node.borrow_mut().next = Some(new_node);
        }
        self.size += 1;
    }

    pub fn pop(&mut self) -> Option<Rc<T>> {
        let mut result: Option<Rc<T>> = None;
        if self.size == 1 {
            let value = self.head.take().unwrap().borrow().value.clone();
            result = Some(value);
        } else if self.size > 1 {
            let pre_last_node = self.nth_node(self.size - 2);
            result = Some(pre_last_node.borrow().next.as_ref().unwrap().borrow().value.clone());
            pre_last_node.borrow_mut().next = None;
        }
        self.size -= 1;
        return result
    }

    fn nth_node(&self, index: usize) -> NodeRef<T> {
        let mut next_node = &self.head;
        let mut next_index = 0;
        while let Some(node) = next_node {
            if next_index == index {
                return node.clone()
            }
            let node_ref = unsafe { &*node.as_ptr() };
            next_node = &node_ref.next;
            next_index += 1;
        }
        panic!(Self::incorrect_index_message(index));
    }

    fn assert_index(self, index: usize) {
        if index < 0 || index >= self.size {
            panic!("Incorrect index - {}", index);
        }
    }
}

impl<T> fmt::Display for List<T> where T: fmt::Display {
    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
        let mut debug_list = formatter.debug_list();
        let mut next_node = &self.head;
        while let Some(node) = next_node {
            debug_list.entry(&format!("{}", node.borrow().value));
            let node_ref = unsafe { &*node.as_ptr() };
            next_node = &node_ref.next;
        }
        debug_list.finish()
    }
}

Can you please fix that? Consider reading this.

Ok, that's better)

1 Like

Consider the following playground:

fn main() {
    let mut list = List::new();
    list.push(10);
    list.push(20);
    list.push(30);
    
    let ref1 = list.nth_node(1);
    let brw = &mut *ref1.borrow_mut();
    
    list.nth_node(2);
    
    println!("{}", brw.value);
}

playground

Open the playground and choose miri under the tools dropdown. It will detect that your code triggers undefined behavior.

2 Likes

Cloning an Rc is relatively cheap. It doesn't allocate any additional memory on the heap, which is what makes certain clone operations expensive, e.g. cloning a String. All it does is copy the pointer it contains, dereferences it to get the internal RcBox struct, which contains the value of type T and the strong and weak count of type usize. The strong count gets incremented when the Rc is cloned and decremented when the Rc is dropped. Only if the strong count reaches zero will the value T be dropped and only when both strong and weak count are zero will the RcBox be dropped, as well as the Box it's in, deallocating memory on the heap.

In general, if you opted in to use Rc, then you should never shy away from cloning it. You only pay the cost for allocation and deallocation of the RcBox once.

To understand why this could go wrong, consider something like this:

let mut some_other_value = ...;
std::mem::swap(&mut brw.next, some_other_value);
let node2 = list.nth_node(2);
std::mem::swap(&mut brw.next, some_other_value);

Then it would not be unreasonable for the compiler to make the following optimization:

  1. We know that brw is a mutable borrow, so it has exclusive access to the next field for the duration of the mutable reference.
  2. The some_other_value is a local variable, which we also have exclusive access to.
  3. Since we have exclusive access to them, the nth_node call cannot observe their value.
  4. Swapping two values twice has no effect, so the two swaps can be optimized out.

Of course, this optimization would be "invalid" because we read the value of brw.next inside the call to list.nth_node, but the compiler may make the optimization because, by creating a mutable reference, we have promised the compiler that we really have exclusive access. If that promise is wrong, any miscompilation is our fault.

In practice, this particular optimization is turned off due to a bug in LLVM, but once they fix that bug, they might enable it, and it would not be considered a breaking change to suddenly start applying it to your code, silently breaking it in the future.

Thanks for detailed explanation. I think I understand it.