Implementation of thread-safe queue - Miri failure

help
1

Hey all :slight_smile:

Playground Link

I tried implementing a thread-safe queue based on a singly linked list. I'm using two Mutexes protecting the head Box and a *mut Node<T> . Based on my understanding the raw ptr is needed, because otherwise the data structure would be self referential.
The queue always keeps one empty dummy node, which means that it is empty when head and tail point to the same memory. The comparison is done via std::ptr::eq.
The code works fine as far as i can tell, but Miri complains about the head.as_ref() call in line 52 with the following (abbreviated) error:

error: Undefined Behavior: trying to reborrow for SharedReadOnly, but parent tag <4267> does not have an appropriate item in the borrow stack
    --> /playground/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/alloc/src/boxed.rs:1088:9
     |
1088 |         &**self
     |         ^^^^^^^ trying to reborrow for SharedReadOnly, but parent tag <4267> does not have an appropriate item in the borrow stack
     |
     = help: this indicates a potential bug in the program: it performed an invalid operation, but the rules it violated are still experimental
     = help: see https://github.com/rust-lang/unsafe-code-guidelines/blob/master/wip/stacked-borrows.md for further information
             
     = note: inside `<std::boxed::Box<Node<i32>> as std::convert::AsRef<Node<i32>>>::as_ref` at /playground/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/alloc/src/boxed.rs:1088:9
note: inside `TsQueue::<i32>::dequeue` at src/main.rs:52:20
    --> src/main.rs:52:20
     |
52   |         if ptr::eq(head.as_ref(), self.get_tail_ptr()) {
     |                    ^^^^^^^^^^^^^

I'd be very happy if someone could explain if I'm indeed violating the Stacked Borrows model. I must admit i haven't understood it completely yet (it's quite hot here :sweat_smile:)
I tried reproducing the issue with a minimal example here but was unable to, thus the full version.

2

I'm pretty sure the issue is that dummy.as_mut() as *mut Node<T> creates a mutable reference to the node, asserting that you have exclusive access.

1 Like
3

Note that you can also do the same thing in safe Rust with a sufficient amount of extra Arc and Mutex. (I wouldn’t be surprised if there was a more lightweight approach to safe-Rust queues than my adaptation of your code.)

1 Like
4

When creating the raw pointer I have exclusive access to the node, so that should be fine. All accesses to the tail ptr are guarded by the Mutex and due to the dummy node all accesses to node.next and node.data should be synchronized.

@steffahn Thanks for the safe implementation :slight_smile: I tried adapting it so that the Mutexes around node.data and node.next are not needed but was unsuccessful. I'm trying to translate a thread safe queue implementation from C++ to Rust and a liberal use of Mutexes would defeat the point. Getting my hands dirty with some unsafe Rust is part of the goal :slight_smile:

I trimmed down the example a little bit to this. Maybe this makes it a little bit easier to understand why this code violates Stacked Borrows. I tried reading some of the material by @RalfJung but it's not an easy topic.

5

Well, one straightforward step, back into unsafe Rust, would be to replace them with UnsafeCell.

1 Like
7

It isn't that simple. When you return from TsQueue::new, you are moving a box after you obtained the raw pointer, but when you then later do (**tail).data on that raw pointer, that expression involves going through a mutable pointer, thus asserting that not only do you have exclusive access, you've had so since you got the raw pointer, which invalidates the pointer that was "created" during the move. Hence it fails when it tries to access the memory through head, as head was invalidated by the assertion of exclusive access.

By creating your own box and obtaining the pointer directly through the ptr field, the UB goes away because the tail pointer isn't derived from the head pointer in a weird way.

struct MyBox<T> {
    ptr: *mut T,
}
impl<T> MyBox<T> {
    fn new(t: T) -> Self {
        Self {
            ptr: Box::into_raw(Box::new(t)),
        }
    }
}
impl<T> Drop for MyBox<T> {
    fn drop(&mut self) {
        unsafe {
            Box::from_raw(self.ptr);
        }
    }
}

playground

This is a bit hand-wavy but that's because I don't understand what the move really does in the eyes of stacked borrows.

2 Likes
8

Sure enough, with a bit of dedication, one can also replace all the Arc with *mut and miri is happy. On top of that, the potential for stack overflow on drop is eliminated (though that could previously have been fixed too, even in the safe version, for example by letting TsQueue just dequeue itself in a loop on drop).

1 Like
9

which itself is only an approximation to how LLVM may analyse the code to infer constraints on code motion, redundant expression elimination, etc. IIUC, use of unsafe_cell, or types built on unsafe_cell, is the only reliable way in Rust to suppress such potential hyper-optimization.

10

Thank you all so much! :blush:

I guess I thought that the goal of the aliasing rules was mainly to prevent data races, but it seems they are stricter than that. The Nomicon is also a bit unclear on the interaction between aliasing of raw pointers and references, understandable considering it's still being figured out.

The version I now ended up with is this one.
The UnsafeCell's in the Node struct are not really needed. They are accessed through Mutexes using UnsafeCell internally anyway. I also changed the *mut Node<T> to NonNull<Node<T>>. As I understand it, this should reduce the size of the node.next value to the size of a *mut Node<T>.

But I think I'll work through the Stacked Borrows blog posts since I feel I still haven't completely grasped why my initial version was UB.

Again, thanks to all of you :blush:

1 Like
11

Now you can do a performance comparison between this version and the safe-Rust version I did above. (Also consider using parking_lot Mutexes for both as they could be faster.)

1 Like
12

That's actually a really good suggestion. But I assume I'll have to look into how to properly benchmark multi-threaded code first. Maybe the criterion docs have some pointers.
Fuzzing the Queue could also be interesting :slight_smile:
Thanks for the parking_lot mention. I looked at the Readme and considering the features, these Mutexes seem much better suited.

13

I forgot about those:

unsafe impl<T: Send> Send for TsQueue<T> {}
unsafe impl<T: Sync> Sync for TsQueue<T> {}

I think they’re wrong! You can send a T through a reference od TsQueue, so Sync for TsQueue needs Send on T. My best guess is that the constrants like Mutex has (needing just T: Send for both) should be the correct ones.

Edit: Little test confirms that the safe-Rust implementation indeed has these impls:

impl<T: Send> Send for TsQueue<T>
impl<T: Send> Sync for TsQueue<T>

without any need for an explicit unsafe impl either.

14

Another safe version, this one’s particularly concise (using parking_lot and no empty lines):

pub struct Queue<T> {
    head: Mutex<Arc<Mutex<Option<Node<T>>>>>,
    tail: Mutex<Arc<Mutex<Option<Node<T>>>>>,
}
struct Node<T>(T, Arc<Mutex<Option<Node<T>>>>);
impl<T> Queue<T> {
    pub fn new() -> Self {
        let r = Arc::new(Mutex::new(None));
        Queue {
            head: Mutex::new(r.clone()),
            tail: Mutex::new(r),
        }
    }
    pub fn enqueue(&self, x: T) {
        let mut tail = self.tail.lock();
        let r = Arc::new(Mutex::new(None));
        *tail.lock() = Some(Node(x, r.clone()));
        *tail = r;
    }
    pub fn dequeue(&self) -> Option<T> {
        let mut head = self.head.lock();
        let Node(x, next) = head.lock().take()?;
        *head = next;
        Some(x)
    }
}

(playground)

15

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.