xref: /linux/lib/lwq.c (revision 0ea5c948cb64bab5bc7a5516774eb8536f05aa0d)
1 // SPDX-License-Identifier: GPL-2.0-only
2 /*
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 multiple
9  * access.  The llist is staged in reverse order, and refreshed
10  * from the llist when it exhausts.
11  *
12  * This is particularly suitable when work items are queued in BH or
13  * IRQ context, and where work items are handled one at a time by
14  * dedicated threads.
15  */
16 #include <linux/rcupdate.h>
17 #include <linux/lwq.h>
18 
__lwq_dequeue(struct lwq * q)19 struct 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 }
39 EXPORT_SYMBOL_GPL(__lwq_dequeue);
40 
41 /**
42  * lwq_dequeue_all - dequeue all currently enqueued objects
43  * @q:	the queue to dequeue from
44  *
45  * Remove and return a linked list of llist_nodes of all the objects that were
46  * in the queue. The first on the list will be the object that was least
47  * recently enqueued.
48  */
lwq_dequeue_all(struct lwq * q)49 struct 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 }
67 EXPORT_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>
76 struct tnode {
77 	struct lwq_node n;
78 	int i;
79 	int c;
80 };
81 
lwq_exercise(void * qv)82 static 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 
lwq_test(void)99 static 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 
157 module_init(lwq_test);
158 #endif /* CONFIG_LWQ_TEST*/
159