mpmc: too many branches

[0xllx0]

In heapless we have an issue with our mpmc implementation that we are trying to test using loom.

However, when testing we get the "exceeded maximum number of branches error":

test mpmc::tests_loom::loom_issue_583_enqueue ... FAILED

failures:

---- mpmc::tests_loom::loom_issue_583_enqueue stdout ----

thread 'mpmc::tests_loom::loom_issue_583_enqueue' panicked at /home/user/.cargo/registry/src/index.crates.io-1949cf8c6b5b557f/loom-0.7.2/src/rt/path.rs:247:13:
Model exceeded maximum number of branches. This is often caused by an algorithm requiring the processor to make progress, e.g. spin locks.


failures:
    mpmc::tests_loom::loom_issue_583_enqueue

The main enqueue implementation:

unsafe fn enqueue<T>(
    buffer: *mut Cell<T>,
    enqueue_pos: &AtomicTargetSize,
    mask: UintSize,
    item: T,
) -> Result<(), T> {
    let mut pos = enqueue_pos.load(Ordering::Relaxed);

    let mut cell;
    loop {
        cell = buffer.add(usize::from(pos & mask));
        let seq = (*cell).sequence.load(Ordering::Acquire);
        let dif = (seq as IntSize).wrapping_sub(pos as IntSize);

        match dif.cmp(&0) {
            core::cmp::Ordering::Equal => {
                if enqueue_pos
                    .compare_exchange_weak(
                        pos,
                        pos.wrapping_add(1),
                        Ordering::Relaxed,
                        Ordering::Relaxed,
                    )
                    .is_ok()
                {
                    break;
                }
            }
            core::cmp::Ordering::Less => {
                return Err(item);
            }
            core::cmp::Ordering::Greater => {
                pos = enqueue_pos.load(Ordering::Relaxed);
            }
        }
    }

    (*cell).data.as_mut_ptr().write(item);
    (*cell)
        .sequence
        .store(pos.wrapping_add(1), Ordering::Release);
    Ok(())
}

And the test:

fn loom_issue_583_enqueue() {
    loom::model(|| {
        let q0 = loom::sync::Arc::new(Queue::<u8, N>::new());
        for i in 0..N {
            q0.enqueue(i as u8).unwrap();
        }
        let model_thread = || {
            let q0 = q0.clone();
            move || {
                for k in 0..N + 2 {
                    let Some(i) = q0.dequeue() else {
                        panic!("Test failed at dequeue");
                    };
                    if q0.enqueue(k as u8).is_err() {
                        panic!("Test failed at enqueue: {i}");
                    }
                }
            }
        };

        let h1 = loom::thread::spawn(model_thread());
        let h2 = loom::thread::spawn(model_thread());
        h1.join().unwrap();
        h2.join().unwrap();
    });
}

We've tried putting bounds on the main loop, adding the loom::thread::yield_now hint to the loop, and setting the max branches to u16::MAX. Nothing has worked so far.

This same error has also come up in some alternative implementations we're working on, that are also loop-based.

Are there workarounds for this issue?

Here are links to our current work:

• mpmc: Document #583 and add corresponding loom test rust-embedded/heapless#620
• fix: resolve MPMC queue contention rust-embedded/heapless#619