1 // SPDX-License-Identifier: GPL-2.0-only
6 #include "funnel-queue.h"
9 #include "memory-alloc.h"
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()
45 	struct funnel_queue_entry *oldest = queue->oldest;  in get_oldest()
46 	struct funnel_queue_entry *next = READ_ONCE(oldest->next);  in get_oldest()
48 	if (oldest == &queue->stub) {  in get_oldest()
51 		 * logically empty.  in get_oldest()
60 		queue->oldest = oldest;  in get_oldest()
61 		next = READ_ONCE(oldest->next);  in get_oldest()
65 	 * We have a non-stub candidate to dequeue. If it lacks a successor, we'll need to put the  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()
83 		vdo_funnel_queue_put(queue, &queue->stub);  in get_oldest()
86 		next = READ_ONCE(oldest->next);  in get_oldest()
89 			 * We lost a race with a producer who swapped queue->newest before we did,  in get_oldest()
90 			 * but who hasn't yet updated previous->next. Try again later.  in get_oldest()
100  * Poll a queue, removing the oldest entry if the queue is not empty. This function must only be
112 	 * so no locking, atomic operations, or fences are needed; queue->oldest is owned by the  in vdo_funnel_queue_poll()
113 	 * consumer and oldest->next is never used by a producer thread after it is swung from NULL  in vdo_funnel_queue_poll()
114 	 * to non-NULL.  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()
124 	 * If "oldest" is a very light-weight work item, we'll be looking for the next one very  in vdo_funnel_queue_poll()
127 	uds_prefetch_address(queue->oldest, true);  in vdo_funnel_queue_poll()
128 	WRITE_ONCE(oldest->next, NULL);  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.
154 	if (queue->oldest != &queue->stub)  in vdo_is_funnel_queue_idle()
159 	 * retrievable entry in the list, or the list is officially empty but in the intermediate  in vdo_is_funnel_queue_idle()
166 	if (READ_ONCE(queue->newest) != &queue->stub)  in vdo_is_funnel_queue_idle()