// SPDX-License-Identifier: GPL-2.0-only
/*
 * Light-weight single-linked queue.
 *
 * Entries are enqueued to the head of an llist, with no blocking.
 * This can happen in any context.
 *
 * Entries are dequeued using a spinlock to protect against multiple
 * access.  The llist is staged in reverse order, and refreshed
 * from the llist when it exhausts.
 *
 * This is particularly suitable when work items are queued in BH or
 * IRQ context, and where work items are handled one at a time by
 * dedicated threads.
 */
#include <linux/rcupdate.h>
#include <linux/lwq.h>

struct llist_node *__lwq_dequeue(struct lwq *q)
{
        struct llist_node *this;

        if (lwq_empty(q))
                return NULL;
        spin_lock(&q->lock);
        this = q->ready;
        if (!this && !llist_empty(&q->new)) {
                /* ensure queue doesn't appear transiently lwq_empty */
                smp_store_release(&q->ready, (void *)1);
                this = llist_reverse_order(llist_del_all(&q->new));
                if (!this)
                        q->ready = NULL;
        }
        if (this)
                q->ready = llist_next(this);
        spin_unlock(&q->lock);
        return this;
}
EXPORT_SYMBOL_GPL(__lwq_dequeue);

/**
 * lwq_dequeue_all - dequeue all currently enqueued objects
 * @q:  the queue to dequeue from
 *
 * Remove and return a linked list of llist_nodes of all the objects that were
 * in the queue. The first on the list will be the object that was least
 * recently enqueued.
 */
struct llist_node *lwq_dequeue_all(struct lwq *q)
{
        struct llist_node *r, *t, **ep;

        if (lwq_empty(q))
                return NULL;

        spin_lock(&q->lock);
        r = q->ready;
        q->ready = NULL;
        t = llist_del_all(&q->new);
        spin_unlock(&q->lock);
        ep = &r;
        while (*ep)
                ep = &(*ep)->next;
        *ep = llist_reverse_order(t);
        return r;
}
EXPORT_SYMBOL_GPL(lwq_dequeue_all);

#if IS_ENABLED(CONFIG_LWQ_TEST)

#include <linux/module.h>
#include <linux/slab.h>
#include <linux/wait_bit.h>
#include <linux/kthread.h>
#include <linux/delay.h>
struct tnode {
        struct lwq_node n;
        int i;
        int c;
};

static int lwq_exercise(void *qv)
{
        struct lwq *q = qv;
        int cnt;
        struct tnode *t;

        for (cnt = 0; cnt < 10000; cnt++) {
                wait_var_event(q, (t = lwq_dequeue(q, struct tnode, n)) != NULL);
                t->c++;
                if (lwq_enqueue(&t->n, q))
                        wake_up_var(q);
        }
        while (!kthread_should_stop())
                schedule_timeout_idle(1);
        return 0;
}

static int lwq_test(void)
{
        int i;
        struct lwq q;
        struct llist_node *l, **t1, *t2;
        struct tnode *t;
        struct task_struct *threads[8];

        printk(KERN_INFO "testing lwq....\n");
        lwq_init(&q);
        printk(KERN_INFO " lwq: run some threads\n");
        for (i = 0; i < ARRAY_SIZE(threads); i++)
                threads[i] = kthread_run(lwq_exercise, &q, "lwq-test-%d", i);
        for (i = 0; i < 100; i++) {
                t = kmalloc_obj(*t);
                if (!t)
                        break;
                t->i = i;
                t->c = 0;
                if (lwq_enqueue(&t->n, &q))
                        wake_up_var(&q);
        }
        /* wait for threads to exit */
        for (i = 0; i < ARRAY_SIZE(threads); i++)
                if (!IS_ERR_OR_NULL(threads[i]))
                        kthread_stop(threads[i]);
        printk(KERN_INFO " lwq: dequeue first 50:");
        for (i = 0; i < 50 ; i++) {
                if (i && (i % 10) == 0) {
                        printk(KERN_CONT "\n");
                        printk(KERN_INFO " lwq: ... ");
                }
                t = lwq_dequeue(&q, struct tnode, n);
                if (t)
                        printk(KERN_CONT " %d(%d)", t->i, t->c);
                kfree(t);
        }
        printk(KERN_CONT "\n");
        l = lwq_dequeue_all(&q);
        printk(KERN_INFO " lwq: delete the multiples of 3 (test lwq_for_each_safe())\n");
        lwq_for_each_safe(t, t1, t2, &l, n) {
                if ((t->i % 3) == 0) {
                        t->i = -1;
                        kfree(t);
                        t = NULL;
                }
        }
        if (l)
                lwq_enqueue_batch(l, &q);
        printk(KERN_INFO " lwq: dequeue remaining:");
        while ((t = lwq_dequeue(&q, struct tnode, n)) != NULL) {
                printk(KERN_CONT " %d", t->i);
                kfree(t);
        }
        printk(KERN_CONT "\n");
        return 0;
}

module_init(lwq_test);
#endif /* CONFIG_LWQ_TEST*/