md/dm-vdo/funnel-queue.c

6 #include "funnel-queue.h"
15 	struct funnel_queue *queue;
17 	result = vdo_allocate(1, struct funnel_queue, "funnel queue", &queue);
22 	 * Initialize the stub entry and put it in the queue, establishing the invariant that
23 	 * queue->newest and queue->oldest are never null.
25 	queue->stub.next = NULL;
26 	queue->newest = &queue->stub;
27 	queue->oldest = &queue->stub;
29 	*queue_ptr = queue;
33 void vdo_free_funnel_queue(struct funnel_queue *queue)
35 	vdo_free(queue);
38 static struct funnel_queue_entry *get_oldest(struct funnel_queue *queue)
45 	struct funnel_queue_entry *oldest = queue->oldest;
48 	if (oldest == &queue->stub) {
50 		 * When the oldest entry is the stub and it has no successor, the queue is
57 		 * breaking the queue invariants.
60 		queue->oldest = oldest;
66 	 * stub entry back on the queue first.
69 		struct funnel_queue_entry *newest = READ_ONCE(queue->newest);
73 			 * Another thread has already swung queue->newest atomically, but not yet
74 			 * assigned previous->next. The queue is really still empty.
80 		 * Put the stub entry back on the queue, ensuring a successor will eventually be
83 		vdo_funnel_queue_put(queue, &queue->stub);
89 			 * We lost a race with a producer who swapped queue->newest before we did,
100  * Poll a queue, removing the oldest entry if the queue is not empty. This function must only be
103 struct funnel_queue_entry *vdo_funnel_queue_poll(struct funnel_queue *queue)
105 	struct funnel_queue_entry *oldest = get_oldest(queue);
112 	 * so no locking, atomic operations, or fences are needed; queue->oldest is owned by the
116 	queue->oldest = READ_ONCE(oldest->next);
119 	 * fetched the entry pointer we stored in "queue->oldest", this also ensures that on entry
127 	uds_prefetch_address(queue->oldest, true);
133  * Check whether the funnel queue is empty or not. If the queue is in a transition state with one
135  * queue as empty.
137 bool vdo_is_funnel_queue_empty(struct funnel_queue *queue)
139 	return get_oldest(queue) == NULL;
143  * Check whether the funnel queue is idle or not. If the queue has entries available to be
144  * retrieved, it is not idle. If the queue is in a transition state with one or more entries being
146  * the vdo_funnel_queue_poll() function, but the queue will not be considered idle.
148 bool vdo_is_funnel_queue_idle(struct funnel_queue *queue)
154 	if (queue->oldest != &queue->stub)
166 	if (READ_ONCE(queue->newest) != &queue->stub)