1 /* SPDX-License-Identifier: GPL-2.0-only */ 2 /* 3 * Copyright 2023 Red Hat 4 */ 5 6 #ifndef VDO_FUNNEL_QUEUE_H 7 #define VDO_FUNNEL_QUEUE_H 8 9 #include <linux/atomic.h> 10 #include <linux/cache.h> 11 12 /* 13 * A funnel queue is a simple (almost) lock-free queue that accepts entries from multiple threads 14 * (multi-producer) and delivers them to a single thread (single-consumer). "Funnel" is an attempt 15 * to evoke the image of requests from more than one producer being "funneled down" to a single 16 * consumer. 17 * 18 * This is an unsynchronized but thread-safe data structure when used as intended. There is no 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 22 * of allowing the very simple enqueue operation to be inlined. 23 * 24 * The implementation requires that a funnel_queue_entry structure (a link pointer) is embedded in 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 28 * entry pointer returned by vdo_funnel_queue_poll(). 29 * 30 * Callers are wholly responsible for allocating and freeing the entries. Entries may be freed as 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 33 * alignment, but no other dynamic allocation is used. 34 * 35 * The algorithm is not actually 100% lock-free. There is a single point in vdo_funnel_queue_put() 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. 39 * 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 42 * signal the presence of new entries. 43 */ 44 45 /* This queue link structure must be embedded in client entries. */ 46 struct funnel_queue_entry { 47 /* The next (newer) entry in the queue. */ 48 struct funnel_queue_entry *next; 49 }; 50 51 /* 52 * The dynamically allocated queue structure, which is allocated on a cache line boundary so the 53 * producer and consumer fields in the structure will land on separate cache lines. This should be 54 * consider opaque but it is exposed here so vdo_funnel_queue_put() can be inlined. 55 */ 56 struct __aligned(L1_CACHE_BYTES) funnel_queue { 57 /* 58 * The producers' end of the queue, an atomically exchanged pointer that will never be 59 * NULL. 60 */ 61 struct funnel_queue_entry *newest; 62 63 /* The consumer's end of the queue, which is owned by the consumer and never NULL. */ 64 struct funnel_queue_entry *oldest __aligned(L1_CACHE_BYTES); 65 66 /* A dummy entry used to provide the non-NULL invariants above. */ 67 struct funnel_queue_entry stub; 68 }; 69 70 int __must_check vdo_make_funnel_queue(struct funnel_queue **queue_ptr); 71 72 void vdo_free_funnel_queue(struct funnel_queue *queue); 73 74 /* 75 * Put an entry on the end of the queue. 76 * 77 * The entry pointer must be to the struct funnel_queue_entry embedded in the caller's data 78 * structure. The caller must be able to derive the address of the start of their data structure 79 * from the pointer that passed in here, so every entry in the queue must have the struct 80 * funnel_queue_entry at the same offset within the client's structure. 81 */ 82 static inline void vdo_funnel_queue_put(struct funnel_queue *queue, 83 struct funnel_queue_entry *entry) 84 { 85 struct funnel_queue_entry *previous; 86 87 /* 88 * Barrier requirements: All stores relating to the entry ("next" pointer, containing data 89 * structure fields) must happen before the previous->next store making it visible to the 90 * consumer. Also, the entry's "next" field initialization to NULL must happen before any 91 * other producer threads can see the entry (the xchg) and try to update the "next" field. 92 * 93 * xchg implements a full barrier. 94 */ 95 WRITE_ONCE(entry->next, NULL); 96 previous = xchg(&queue->newest, entry); 97 /* 98 * Preemptions between these two statements hide the rest of the queue from the consumer, 99 * preventing consumption until the following assignment runs. 100 */ 101 WRITE_ONCE(previous->next, entry); 102 } 103 104 struct funnel_queue_entry *__must_check vdo_funnel_queue_poll(struct funnel_queue *queue); 105 106 bool __must_check vdo_is_funnel_queue_empty(struct funnel_queue *queue); 107 108 bool __must_check vdo_is_funnel_queue_idle(struct funnel_queue *queue); 109 110 #endif /* VDO_FUNNEL_QUEUE_H */ 111