UB in lockfree crate?

help
1

I have question for the lockfree crate. More precicisly for the lockfree::channel::mpsc::Sender::send() method.
The crate uses a linked list to implement a lockfree channel. The linked list is built up of Nodes that have a minimum alignement of 2. The crate uses this fact to communicate if the Receiver has been disconnected by setting the lowest bit of the pointer to the back Node to 1 (Which it normally can't be since it has an even alignement.) You can see this in the following snippet of the Sender::send() method:

impl<T> Sender<T> {
    /// Sends a message and if the receiver disconnected, an error is returned.
    pub fn send(&self, message: T) -> Result<(), NoRecv<T>> {
        // First we create a node with our message.
        let alloc = OwnedAlloc::new(Node {
            message: Some(message),
            next: AtomicPtr::new(null_mut()),
        });
        let node = alloc.into_raw();

        // We first load the back because we need to check it. This is safe
        // because we only store nodes allocated via `OwnedAlloc`. Also, the
        // shared back is only deallocated when both sides disconnected.
        let mut loaded = unsafe { self.inner.back.as_ref().ptr.load(Relaxed) };

        loop {
            // If the lower bit is marked, it means the receiver disconnected.
            if loaded as usize & 1 == 1 {
                // This is safe because we are only recreating the owned
                // allocation for the node we just created. We did not share the
                // node.
                let mut alloc = unsafe { OwnedAlloc::from_raw(node) };
                let message = alloc.message.take().unwrap();
                break Err(NoRecv { message });
            }
        /// Rest skipped for brevity
        }
    }

I wanted to know if depending on this representation of the pointer as an even unsized integer is UB?

1 Like
2

I don't think so. The reference says that the pointer-to-integer cast produces the address, which must be even if the type is aligned to 2 bytes.

To nitpick: the cast itself is certainly not UB, as it doesn't do anything inherently unsafe by itself.

1 Like
3

That's fine. Casting a pointer with as usize exposes the provenance - essentially, once you use as usize you are legally allowed to convert a usize containing pointer to an exposed object back to a pointer.

In the future, Rust may provide methods that allow bitwise operations on raw pointers without exposing their provenance (which can prevent certain optimizations), such as addr, but these aren't currently stabilised.

AtomicPtr is allowed to store an unaligned pointer.

4

What you're legally allowed to do isn't yet settled, like the link says.

The exact form of provenance in Rust is unclear. It is also unclear whether provenance applies to more than just pointers, i.e., one could imagine integers having provenance as well (so that pointer provenance can be preserved when pointers are cast to an integer and back). In the following, we give some examples if what provenance could look like.

1 Like
5

Ok, but they also tinker with the pointer by setting the 1's bit to 1. So it doesn't point to a valid memory address anymore. Isn't that UB?

For example in the drop code of Receiver:

            // This is safe because we only store nodes allocated via
            // `OwnedAlloc`. Also, the shared back is only deallocated when both
            // sides have disconnected.
            let res = unsafe {
                // Let's try to mark the back. Needs to be a CAS because the
                // back might change the back to some other pointer it
                // meanwhile.
                self.back.as_ref().ptr.compare_exchange(
                    ptr,
                    (ptr as usize | 1) as *mut _,
                    Relaxed,
                    Relaxed,
                )
            };
6

No. The reference explicitly states that raw pointers are allowed to be unaligned as long as they are not dereferenced.

2 Likes
7

Looks like there might be different UB in the lockfree crate though. E.g.

git clone https://gitlab.com/bzim/lockfree.git ; cd lockfree ; RUSTFLAGS="-Winvalid_atomic_ordering" cargo +nightly miri test channel::mpsc::test::correct_numbers

test channel::mpsc::test::correct_numbers ... error: Undefined Behavior: Data race detected between (1) Read on thread `<unnamed>` and (2) Write on thread `channel::mpsc::` at alloc99337. (2) just happened here
   --> src/channel/mpsc.rs:175:33
    |
175 |         let mut node = unsafe { &mut *self.front.as_ptr() };
    |                                 ^^^^^^^^^^^^^^^^^^^^^^^^^ Data race detected between (1) Read on thread `<unnamed>` and (2) Write on thread `channel::mpsc::` at alloc99337. (2) just happened here
    |
help: and (1) occurred earlier here
   --> src/channel/mpsc.rs:100:25
    |
100 |                         prev.as_ref().next.swap(node.as_ptr(), Release)
    |                         ^^^^^^^^^^^^^
    = help: this indicates a bug in the program: it performed an invalid operation, and caused Undefined Behavior
    = help: see https://doc.rust-lang.org/nightly/reference/behavior-considered-undefined.html for further information
    = note: BACKTRACE (of the first span):
    = note: inside `channel::mpsc::Receiver::<usize>::recv` at src/channel/mpsc.rs:175:33: 175:58
note: inside `channel::mpsc::test::correct_numbers`
   --> src/channel/mpsc.rs:473:19
    |
473 |             match receiver.recv() {
    |                   ^^^^^^^^^^^^^^^
note: inside closure
   --> src/channel/mpsc.rs:451:26
    |
450 |     #[test]
    |     ------- in this procedural macro expansion
451 |     fn correct_numbers() {
    |                          ^
    = note: this error originates in the attribute macro `test` (in Nightly builds, run with -Z macro-backtrace for more info)

Or, unrelated, there’s also issues like this one, and apparently a general lack of maintenance.

4 Likes
8

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.