Implement MessageQueue without locks

[brson]

MessageQueue is the way schedulers communicate with each other. It is a multiple-producer, single-consumer unbounded queue.

[brson]

@Thiez is working on this

[msullivan]

How's this going?

[Thiez]

I've had https://github.com/Thiez/rust/blob/ll-message-queue/src/libstd/rt/message_queue.rs lying around for a while now. It is a Michael-Scott lockless queue as described here http://www.cs.rochester.edu/~scott/papers/1996_PODC_queues.pdf . However, since Rust does not (at this time) have an intrinsic for double-word compare-and-swap, my version is considerably more vulnerable to the ABA-problem and thus I am hesitant to declare this queue complete.
Adding a DWCAS intrinsic is not a good option as it is not supported on all the architectures we target. I think the best option would be to have a ABA-safe atomic pointer type defined in the library (it would help with the implementation of other datastructures as well). I suspect such a thing could be implemented for each target architecture with some #[cfg(target_arch = <sometarget>)] annotations; using LLVM would be tricky as it has no IR instruction that captures the semantics of of LL/SC (on architectures such as ARM).
I have no MIPS or multicore ARM devices lying around so I would not be able to test such a pointer.

To summarize, the basic algorithm is implemented and appears to work (without leaking memory, or so valgrind tells me) but it's going to fail randomly (but rarely) when at least two threads are writing and one thread is reading.
Currently there's manual malloc/free in the code but now that ~ has lost the headers the malloc could be replaced by a normal ~ followed by a transmute (and transmute back to ~ to delete).

Suggestions are welcome.

[plokhotnyuk]

I used lock-free MPSC queue that was described by Dmitriy Vyukov (http://www.1024cores.net/home/lock-free-algorithms/queues/non-intrusive-mpsc-node-based-queue) to implement one of fastest and lightweight actor for JVM: https://github.com/plokhotnyuk/actors/blob/master/src/test/scala/com/github/plokhotnyuk/actors/Actor2.scala

[brson]

The biggest place where we need to reduce lock contention is the global sleeper list #6838. Its lock is just getting hammered constantly. There are lots of ways we might fix this but an obvious one to replace it with a lock-free queue.

[Thiez]

@plokhotnyuk thanks for that link, implementing it in rust was incredibly easy https://github.com/Thiez/rust/blob/better-message-queue/src/libstd/rt/message_queue.rs
@brson did you have a good benchmark for message-passing lying around?

[alexcrichton]

Closed by #9710