- * Lock-free RCU queue using reference counting. Enqueue and dequeue operations
- * hold a RCU read lock to deal with cmpxchg ABA problem. This implementation
- * keeps a dummy head node to ensure we can always update the queue locklessly.
- * Given that this is a queue, the dummy head node must always advance as we
- * dequeue entries. Therefore, we keep a reference count on each entry we are
- * dequeueing, so they can be kept as dummy head node until the next dequeue, at
- * which point their reference count will be decremented.
+ * Lock-free RCU queue. Enqueue and dequeue operations hold a RCU read
+ * lock to deal with cmpxchg ABA problem. This queue is *not* circular:
+ * head points to the oldest node, tail points to the newest node.
+ * Dummy nodes are kept to ensure enqueue and dequeue can always proceed
+ * concurrently. Keeping a separate head and tail helps with large
+ * queues: enqueue and dequeue can proceed concurrently without
+ * wrestling for exclusive access to the same variables.
+ *
+ * We keep two dummy nodes in the queue to distinguish between empty queue
+ * state and intermediate state while a dummy node dequeue/requeue is
+ * being performed. Dequeue retry if it detects that it would be
+ * dequeueing the last node (it means a dummy node dequeue-requeue is in
+ * progress). This ensures that there is always at least one node in
+ * the queue. In a situation where the two dummy nodes are being
+ * requeued (they therefore don't appear in the queue at a given
+ * moment), we are certain that there is at least one non-dummy node in
+ * the queue (ensured by the test for NULL next node upon dequeue).
+ *
+ * In the dequeue operation, we internally reallocate the dummy nodes
+ * upon dequeue/requeue and use call_rcu to free them after a grace
+ * period.