Encountered invalid memory reference while removing nodes

#[derive(Debug)]
struct Node<T> {
    data: T,
    next: Mutex<*mut Node<T>>,
}

#[derive(Debug)]
pub struct List<T> {
    head: Mutex<*mut Node<T>>,
}

every node in this List is Box::into_rawed. I encountered an invalid memory reference error message while concurrently calling this function.

    fn remove(&self, key: &T) -> bool {
        let mut head = &self.head;

        if !self.contains(key) {
            return false;
        }

        while let Ok(mut guard) = head.lock() {
            if guard.is_null() {
                return false;
            }
            if unsafe { &(**guard).data } == key {
                let droppable = *guard;
                *guard = *unsafe { &(**guard).next }.lock().unwrap();
                drop(unsafe { Box::from_raw(droppable) });
                return true;
            }
            head = unsafe { &(**guard).next };
        }
        false
    }

I don't understand what's wrong here....I think I am dropping correctly as well?

Hint: what're the safety preconditions for this line, given head is used in the next iteration of loop?

Use of each single Mutex data structure still must obey the borrow rules. (Don't focus your attention on data inside.)

oh, the guard is gone and in the next iteration I am still accessing next as if I had the guard?

Yes, and note that your node can be removed by the other thread.

Say, 1->2->3->4->5, T1 removes 5, T2 removes 2.

T1 pauses at head:2 with no locks held, T2 removes 2, T1 resumes from freed memory.

oops, this is more complicated than I thought...I have to rethink on how we're supposed to drop the guards so that I could synchronize with the next Acquire....I'll share what I came up with after finding a solution :slight_smile: thank you for pointing this out!

fn main() {
    struct Node<T> {
        data: T,
        next: std::sync::Mutex<*mut Node<T>>,
    }

    pub struct List<T> {
        head: std::sync::Mutex<*mut Node<T>>,
    }

    let f = List {
        head: std::sync::Mutex::new(Box::into_raw(Box::new(Node {
            data: 0usize,
            next: std::sync::Mutex::new(Box::into_raw(Box::new(Node {
                data: 1usize,
                next: std::sync::Mutex::new(std::ptr::null_mut()),
            }))),
        }))),
    };

    let lock = f.head.lock().unwrap();
    let next = unsafe { &(**lock).next };
    drop(lock);
    let _ub_test = next.lock().unwrap();
    println!("{}", unsafe { &(**_ub_test).data })
}

this is UB, right?

not according to miri

why do you think it should be UB, because you keep using the data after the lock has been released ?

it is not UB because the &Node in next is completely seperate from the *mut Node<T> it was created from, so it's fine to use after the lock has been closed, as long as you don't add any other code trying to do similar things in parralel.

ofc if you had other threads trying to do the same thing,then you could indeed get UB really quick

indeed!

yeah, I just realized this now....thanks a lot!

What if you use a single mutex for the entire list instead of one mutex per node, then a thread deleting a node just results in other threads blocking until the node is deleted.

If you lock a node and someone wants to delete the previous one, they shouldn't delete your Mutex. So, you probably want to transpose Mutex and pointer, for *mut Mutex<Node>... I don't remember if that would be enough to implement the list competely.