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

• Optimize unbounded channels #279 (comment)
• 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:

• crossbeam/crossbeam-queue/src/seg_queue.rs

  Lines 223 to 224 in b11f1a8

  	tail = self.tail.index.load(Ordering::Acquire);
  	block = self.tail.block.load(Ordering::Acquire);

  The latest tail is immediately reloaded.

• crossbeam/crossbeam-queue/src/seg_queue.rs

  Lines 196 to 201 in b11f1a8

  	if offset == BLOCK_CAP {
  	backoff.snooze();
  	tail = self.tail.index.load(Ordering::Acquire);
  	block = self.tail.block.load(Ordering::Acquire);
  	continue;
  	}

  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):

  crossbeam/crossbeam-queue/src/seg_queue.rs

  Lines 240 to 245 in b11f1a8

  	if offset + 1 == BLOCK_CAP {
  	let next_block = Box::into_raw(next_block.unwrap());
  	let next_index = new_tail.wrapping_add(1 << SHIFT);
  	self.tail.block.store(next_block, Ordering::Release);
  	self.tail.index.store(next_index, Ordering::Release);

  Pragmatically, I don't see priority inversion ever being an issue for inserts.

• crossbeam/crossbeam-queue/src/seg_queue.rs

  Lines 332 to 340 in b11f1a8

  	if offset + 1 == BLOCK_CAP {
  	let next = (*block).wait_next();
  	let mut next_index = (new_head & !HAS_NEXT).wrapping_add(1 << SHIFT);
  	if !(*next).next.load(Ordering::Relaxed).is_null() {
  	next_index |= HAS_NEXT;
  	}
  	self.head.block.store(next, Ordering::Release);
  	self.head.index.store(next_index, Ordering::Release);

  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.