159 lines · c
1// SPDX-License-Identifier: GPL-2.0-only2/*3 * Light-weight single-linked queue.4 *5 * Entries are enqueued to the head of an llist, with no blocking.6 * This can happen in any context.7 *8 * Entries are dequeued using a spinlock to protect against multiple9 * access. The llist is staged in reverse order, and refreshed10 * from the llist when it exhausts.11 *12 * This is particularly suitable when work items are queued in BH or13 * IRQ context, and where work items are handled one at a time by14 * dedicated threads.15 */16#include <linux/rcupdate.h>17#include <linux/lwq.h>18 19struct llist_node *__lwq_dequeue(struct lwq *q)20{21 struct llist_node *this;22 23 if (lwq_empty(q))24 return NULL;25 spin_lock(&q->lock);26 this = q->ready;27 if (!this && !llist_empty(&q->new)) {28 /* ensure queue doesn't appear transiently lwq_empty */29 smp_store_release(&q->ready, (void *)1);30 this = llist_reverse_order(llist_del_all(&q->new));31 if (!this)32 q->ready = NULL;33 }34 if (this)35 q->ready = llist_next(this);36 spin_unlock(&q->lock);37 return this;38}39EXPORT_SYMBOL_GPL(__lwq_dequeue);40 41/**42 * lwq_dequeue_all - dequeue all currently enqueued objects43 * @q: the queue to dequeue from44 *45 * Remove and return a linked list of llist_nodes of all the objects that were46 * in the queue. The first on the list will be the object that was least47 * recently enqueued.48 */49struct llist_node *lwq_dequeue_all(struct lwq *q)50{51 struct llist_node *r, *t, **ep;52 53 if (lwq_empty(q))54 return NULL;55 56 spin_lock(&q->lock);57 r = q->ready;58 q->ready = NULL;59 t = llist_del_all(&q->new);60 spin_unlock(&q->lock);61 ep = &r;62 while (*ep)63 ep = &(*ep)->next;64 *ep = llist_reverse_order(t);65 return r;66}67EXPORT_SYMBOL_GPL(lwq_dequeue_all);68 69#if IS_ENABLED(CONFIG_LWQ_TEST)70 71#include <linux/module.h>72#include <linux/slab.h>73#include <linux/wait_bit.h>74#include <linux/kthread.h>75#include <linux/delay.h>76struct tnode {77 struct lwq_node n;78 int i;79 int c;80};81 82static int lwq_exercise(void *qv)83{84 struct lwq *q = qv;85 int cnt;86 struct tnode *t;87 88 for (cnt = 0; cnt < 10000; cnt++) {89 wait_var_event(q, (t = lwq_dequeue(q, struct tnode, n)) != NULL);90 t->c++;91 if (lwq_enqueue(&t->n, q))92 wake_up_var(q);93 }94 while (!kthread_should_stop())95 schedule_timeout_idle(1);96 return 0;97}98 99static int lwq_test(void)100{101 int i;102 struct lwq q;103 struct llist_node *l, **t1, *t2;104 struct tnode *t;105 struct task_struct *threads[8];106 107 printk(KERN_INFO "testing lwq....\n");108 lwq_init(&q);109 printk(KERN_INFO " lwq: run some threads\n");110 for (i = 0; i < ARRAY_SIZE(threads); i++)111 threads[i] = kthread_run(lwq_exercise, &q, "lwq-test-%d", i);112 for (i = 0; i < 100; i++) {113 t = kmalloc(sizeof(*t), GFP_KERNEL);114 if (!t)115 break;116 t->i = i;117 t->c = 0;118 if (lwq_enqueue(&t->n, &q))119 wake_up_var(&q);120 }121 /* wait for threads to exit */122 for (i = 0; i < ARRAY_SIZE(threads); i++)123 if (!IS_ERR_OR_NULL(threads[i]))124 kthread_stop(threads[i]);125 printk(KERN_INFO " lwq: dequeue first 50:");126 for (i = 0; i < 50 ; i++) {127 if (i && (i % 10) == 0) {128 printk(KERN_CONT "\n");129 printk(KERN_INFO " lwq: ... ");130 }131 t = lwq_dequeue(&q, struct tnode, n);132 if (t)133 printk(KERN_CONT " %d(%d)", t->i, t->c);134 kfree(t);135 }136 printk(KERN_CONT "\n");137 l = lwq_dequeue_all(&q);138 printk(KERN_INFO " lwq: delete the multiples of 3 (test lwq_for_each_safe())\n");139 lwq_for_each_safe(t, t1, t2, &l, n) {140 if ((t->i % 3) == 0) {141 t->i = -1;142 kfree(t);143 t = NULL;144 }145 }146 if (l)147 lwq_enqueue_batch(l, &q);148 printk(KERN_INFO " lwq: dequeue remaining:");149 while ((t = lwq_dequeue(&q, struct tnode, n)) != NULL) {150 printk(KERN_CONT " %d", t->i);151 kfree(t);152 }153 printk(KERN_CONT "\n");154 return 0;155}156 157module_init(lwq_test);158#endif /* CONFIG_LWQ_TEST*/159