1 /* SPDX-License-Identifier: GPL-2.0-only */ 2 3 #ifndef LWQ_H 4 #define LWQ_H 5 /* 6 * Light-weight single-linked queue built from llist 7 * 8 * Entries can be enqueued from any context with no locking. 9 * Entries can be dequeued from process context with integrated locking. 10 * 11 * This is particularly suitable when work items are queued in 12 * BH or IRQ context, and where work items are handled one at a time 13 * by dedicated threads. 14 */ 15 #include <linux/container_of.h> 16 #include <linux/spinlock.h> 17 #include <linux/llist.h> 18 19 struct lwq_node { 20 struct llist_node node; 21 }; 22 23 struct lwq { 24 spinlock_t lock; 25 struct llist_node *ready; /* entries to be dequeued */ 26 struct llist_head new; /* entries being enqueued */ 27 }; 28 29 /** 30 * lwq_init - initialise a lwq 31 * @q: the lwq object 32 */ 33 static inline void lwq_init(struct lwq *q) 34 { 35 spin_lock_init(&q->lock); 36 q->ready = NULL; 37 init_llist_head(&q->new); 38 } 39 40 /** 41 * lwq_empty - test if lwq contains any entry 42 * @q: the lwq object 43 * 44 * This empty test contains an acquire barrier so that if a wakeup 45 * is sent when lwq_dequeue returns true, it is safe to go to sleep after 46 * a test on lwq_empty(). 47 */ 48 static inline bool lwq_empty(struct lwq *q) 49 { 50 /* acquire ensures ordering wrt lwq_enqueue() */ 51 return smp_load_acquire(&q->ready) == NULL && llist_empty(&q->new); 52 } 53 54 struct llist_node *__lwq_dequeue(struct lwq *q); 55 /** 56 * lwq_dequeue - dequeue first (oldest) entry from lwq 57 * @q: the queue to dequeue from 58 * @type: the type of object to return 59 * @member: them member in returned object which is an lwq_node. 60 * 61 * Remove a single object from the lwq and return it. This will take 62 * a spinlock and so must always be called in the same context, typcially 63 * process contet. 64 */ 65 #define lwq_dequeue(q, type, member) \ 66 ({ struct llist_node *_n = __lwq_dequeue(q); \ 67 _n ? container_of(_n, type, member.node) : NULL; }) 68 69 struct llist_node *lwq_dequeue_all(struct lwq *q); 70 71 /** 72 * lwq_for_each_safe - iterate over detached queue allowing deletion 73 * @_n: iterator variable 74 * @_t1: temporary struct llist_node ** 75 * @_t2: temporary struct llist_node * 76 * @_l: address of llist_node pointer from lwq_dequeue_all() 77 * @_member: member in _n where lwq_node is found. 78 * 79 * Iterate over members in a dequeued list. If the iterator variable 80 * is set to NULL, the iterator removes that entry from the queue. 81 */ 82 #define lwq_for_each_safe(_n, _t1, _t2, _l, _member) \ 83 for (_t1 = (_l); \ 84 *(_t1) ? (_n = container_of(*(_t1), typeof(*(_n)), _member.node),\ 85 _t2 = ((*_t1)->next), \ 86 true) \ 87 : false; \ 88 (_n) ? (_t1 = &(_n)->_member.node.next, 0) \ 89 : ((*(_t1) = (_t2)), 0)) 90 91 /** 92 * lwq_enqueue - add a new item to the end of the queue 93 * @n - the lwq_node embedded in the item to be added 94 * @q - the lwq to append to. 95 * 96 * No locking is needed to append to the queue so this can 97 * be called from any context. 98 * Return %true is the list may have previously been empty. 99 */ 100 static inline bool lwq_enqueue(struct lwq_node *n, struct lwq *q) 101 { 102 /* acquire enqures ordering wrt lwq_dequeue */ 103 return llist_add(&n->node, &q->new) && 104 smp_load_acquire(&q->ready) == NULL; 105 } 106 107 /** 108 * lwq_enqueue_batch - add a list of new items to the end of the queue 109 * @n - the lwq_node embedded in the first item to be added 110 * @q - the lwq to append to. 111 * 112 * No locking is needed to append to the queue so this can 113 * be called from any context. 114 * Return %true is the list may have previously been empty. 115 */ 116 static inline bool lwq_enqueue_batch(struct llist_node *n, struct lwq *q) 117 { 118 struct llist_node *e = n; 119 120 /* acquire enqures ordering wrt lwq_dequeue */ 121 return llist_add_batch(llist_reverse_order(n), e, &q->new) && 122 smp_load_acquire(&q->ready) == NULL; 123 } 124 #endif /* LWQ_H */ 125