wfcqueue: implement mutex-free splice
authorMathieu Desnoyers <mathieu.desnoyers@efficios.com>
Tue, 20 Nov 2012 02:45:04 +0000 (21:45 -0500)
committerMathieu Desnoyers <mathieu.desnoyers@efficios.com>
Wed, 5 Dec 2012 10:48:00 +0000 (05:48 -0500)
commitf878b49ebb78010f4f9466d3512a7e88787812b2
tree53b66f22b898201c2d06f470f06f353eacc3611f
parent6d5729f73aabf7cf8f25c198aa97fb5c0f76d078
wfcqueue: implement mutex-free splice

A carefully crafted splice operation does not need to use an external
mutex to synchronize against other splice operations.

The trick is atomically exchange the head next pointer with
NULL. If the pointer we replaced was NULL, it means the queue was
possibly empty. If head next was not NULL, by setting head to NULL, we
ensure that concurrent splice operations are going to see an empty
queue, even if concurrent enqueue operations move tail further. This
means that as long as we are within splice, after setting head to NULL,
but before moving tail back to head, concurrent splice operations will
always see an empty queue, therefore acting as mutual exclusion.

If exchange returns a NULL head, we confirm that it was indeed empty by
checking if the tail pointer points to the head node, busy-waiting if
necessary.

Then the last step is to move the tail pointer to head. At that point,
enqueuers are going to start enqueuing at head again, and other splice
operations will be able to proceed.

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
urcu/static/wfcqueue.h
urcu/wfcqueue.h
wfcqueue.c
This page took 0.025378 seconds and 4 git commands to generate.