6 #include "funnel-queue.h"
15 	struct funnel_queue *queue;  in vdo_make_funnel_queue()  local
17 	result = vdo_allocate(1, struct funnel_queue, "funnel queue", &queue);  in vdo_make_funnel_queue()
22 	 * Initialize the stub entry and put it in the queue, establishing the invariant that  in vdo_make_funnel_queue()
23 	 * queue->newest and queue->oldest are never null.  in vdo_make_funnel_queue()
25 	queue->stub.next = NULL;  in vdo_make_funnel_queue()
26 	queue->newest = &queue->stub;  in vdo_make_funnel_queue()
27 	queue->oldest = &queue->stub;  in vdo_make_funnel_queue()
29 	*queue_ptr = queue;  in vdo_make_funnel_queue()
33 void vdo_free_funnel_queue(struct funnel_queue *queue)  in vdo_free_funnel_queue()  argument
35 	vdo_free(queue);  in vdo_free_funnel_queue()
38 static struct funnel_queue_entry *get_oldest(struct funnel_queue *queue)  in get_oldest()  argument
45 	struct funnel_queue_entry *oldest = queue->oldest;  in get_oldest()
48 	if (oldest == &queue->stub) {  in get_oldest()
50 		 * When the oldest entry is the stub and it has no successor, the queue is  in get_oldest()
57 		 * breaking the queue invariants.  in get_oldest()
60 		queue->oldest = oldest;  in get_oldest()
66 	 * stub entry back on the queue first.  in get_oldest()
69 		struct funnel_queue_entry *newest = READ_ONCE(queue->newest);  in get_oldest()
73 			 * Another thread has already swung queue->newest atomically, but not yet  in get_oldest()
74 			 * assigned previous->next. The queue is really still empty.  in get_oldest()
80 		 * Put the stub entry back on the queue, ensuring a successor will eventually be  in get_oldest()
83 		vdo_funnel_queue_put(queue, &queue->stub);  in get_oldest()
89 			 * We lost a race with a producer who swapped queue->newest before we did,  in get_oldest()
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)  in vdo_funnel_queue_poll()  argument
105 	struct funnel_queue_entry *oldest = get_oldest(queue);  in vdo_funnel_queue_poll()
112 	 * so no locking, atomic operations, or fences are needed; queue->oldest is owned by the  in vdo_funnel_queue_poll()
116 	queue->oldest = READ_ONCE(oldest->next);  in vdo_funnel_queue_poll()
119 	 * fetched the entry pointer we stored in "queue->oldest", this also ensures that on entry  in vdo_funnel_queue_poll()
127 	uds_prefetch_address(queue->oldest, true);  in vdo_funnel_queue_poll()
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)  in vdo_is_funnel_queue_empty()  argument
139 	return get_oldest(queue) == NULL;  in vdo_is_funnel_queue_empty()
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)  in vdo_is_funnel_queue_idle()  argument
154 	if (queue->oldest != &queue->stub)  in vdo_is_funnel_queue_idle()
166 	if (READ_ONCE(queue->newest) != &queue->stub)  in vdo_is_funnel_queue_idle()