Document that SegQueue is not completely lock free

[matklad]

SegQueue is not completely lock-free. It effectively contains a spin-lock inside. While this shouldn't affect performance in most cases, it can cause pathological behavior with priority inversion (see this post for details). I am not expert enough to judge if this the right trade-off or not, but I think this warrants a note in the docs

Note that my understanding is very superficial and based on

• https://github.com/crossbeam-rs/crossbeam/pull/279#issuecomment-450490718
• http://www.1024cores.net/home/lock-free-algorithms/queues/bounded-mpmc-queue

and very cursory look at the source code.

[SUPERCILEX]

I believe this is a non-issue. As far as I understand, the problem from your blog post is that CAS is used to wait on a single, shared state transition that can take a very long time (everybody gets stuck in the Self::ACTIVE state).

SegQueue has 3 CAS instructions which don't (ish) exhibit the shared state transition issue:

• https://github.com/crossbeam-rs/crossbeam/blob/b11f1a83e6362589979a4c58c79895cc936b09fb/crossbeam-queue/src/seg_queue.rs#L223-L224 The latest tail is immediately reloaded.
• https://github.com/crossbeam-rs/crossbeam/blob/b11f1a83e6362589979a4c58c79895cc936b09fb/crossbeam-queue/src/seg_queue.rs#L196-L201 This spot could get into the priority inversion you mentioned, but I don't think it can stay there for long given that the threads will yield to the scheduler (the snooze call). Also, the code that performs the state transition makes no syscalls and executes the minimal set of instructions (the allocation happens outside the critical section): https://github.com/crossbeam-rs/crossbeam/blob/b11f1a83e6362589979a4c58c79895cc936b09fb/crossbeam-queue/src/seg_queue.rs#L240-L245 Pragmatically, I don't see priority inversion ever being an issue for inserts.
• https://github.com/crossbeam-rs/crossbeam/blob/b11f1a83e6362589979a4c58c79895cc936b09fb/crossbeam-queue/src/seg_queue.rs#L332-L340 Pop gets a bit dicer: it waits on a concurrent write to finish by potentially yielding to the scheduler. This could result in cascading yields: the push gets stalled for whatever reason which blocks the pop's transition to the next block which prevents all other pops from advancing. That said, I'm not sure how you could do any better and I don't think it's all that common: it means there's only one item in the queue (that you happen to be adding at the block boundary) and everybody is fighting to pop it. Since crossbeam is mostly intended for use in schedulers, I would argue this scenario is the scheduler's fault and can be easily avoided by not having more active threads than there are tasks.

Overall my main concern is pop, but I think any substantive issues can be avoided by not spamming pop when the queue is near-empty.

[ibraheemdev]

It is not lock-free in terms of progress, I think that should be documented whether or not the implementation decides it's an issue.

[bsilver8192]

I use crossbeam with SCHED_FIFO. This means the higher-priority thread will never yield to the lower-priority one, so hitting this kind of priority inversion is a full-on deadlock. I don't actually use SegQueue, and this means I can't. That's not necessarily a bad design decision, but I do think it should be documented clearly.

I tried something similar to my test program in #821 which shows that similar behavior in channels is really bad, and it agrees that these are hit less often in SigQueue.

I pushed a modification of the sigqueue benchmark demonstrating the deadlock to https://github.com/bsilver8192/crossbeam/tree/sigqueue-deadlock. taskset 1 cargo run --manifest-path crossbeam-channel/benchmarks/Cargo.toml --bin segqueue spins forever on my computer (it might succeed occasionally). Some notes on running it:

• DO NOT do this on a computer with fewer than 3 cores, it will hang everything
• I've only tried on Linux
• You will need to give it permission to use the realtime scheduler. sudo prlimit --rtprio=5 -p $$ works to give most shells that permission, and then any processes you start will inherit it.