md/dm-vdo/funnel-queue.h

13  * A funnel queue is a simple (almost) lock-free queue that accepts entries from multiple threads
19  * mechanism to ensure that only one thread is consuming from the queue. If more than one thread
20  * attempts to consume from the queue, the resulting behavior is undefined. Clients must not
21  * directly access or manipulate the internals of the queue, which are only exposed for the purpose
25  * the queue entries, and pointers to those structures are used exclusively by the queue. No macros
26  * are defined to template the queue, so the offset of the funnel_queue_entry in the records placed
27  * in the queue must all be the same so the client can derive their structure pointer from the
31  * soon as they are returned since this queue is not susceptible to the "ABA problem" present in
32  * many lock-free data structures. The queue is dynamically allocated to ensure cache-line
36  * at which a preempted producer will prevent the consumers from seeing items added to the queue by
37  * later producers, and only if the queue is short enough or the consumer fast enough for it to
38  * reach what was the end of the queue at the time of the preemption.
40  * The consumer function, vdo_funnel_queue_poll(), will return NULL when the queue is empty. To
41  * wait for data to consume, spin (if safe) or combine the queue with a struct event_count to
45 /* This queue link structure must be embedded in client entries. */
47 	/* The next (newer) entry in the queue. */
52  * The dynamically allocated queue structure, which is allocated on a cache line boundary so the
58 	 * The producers' end of the queue, an atomically exchanged pointer that will never be
63 	/* The consumer's end of the queue, which is owned by the consumer and never NULL. */
72 void vdo_free_funnel_queue(struct funnel_queue *queue);
75  * Put an entry on the end of the queue.
79  * from the pointer that passed in here, so every entry in the queue must have the struct
82 static inline void vdo_funnel_queue_put(struct funnel_queue *queue,
96 	previous = xchg(&queue->newest, entry);
98 	 * Preemptions between these two statements hide the rest of the queue from the consumer,
104 struct funnel_queue_entry *__must_check vdo_funnel_queue_poll(struct funnel_queue *queue);
106 bool __must_check vdo_is_funnel_queue_empty(struct funnel_queue *queue);
108 bool __must_check vdo_is_funnel_queue_idle(struct funnel_queue *queue);