mirror of
https://git.kernel.org/pub/scm/linux/kernel/git/stable/linux.git
synced 2024-12-28 16:56:26 +00:00
de9e82c355
lwq is a FIFO single-linked queue that only requires a spinlock for dequeueing, which happens in process context. Enqueueing is atomic with no spinlock and can happen in any context. This is particularly useful when work items are queued from BH or IRQ context, and when they are handled one at a time by dedicated threads. Avoiding any locking when enqueueing means there is no need to disable BH or interrupts, which is generally best avoided (particularly when there are any RT tasks on the machine). This solution is superior to using "list_head" links because we need half as many pointers in the data structures, and because list_head lists would need locking to add items to the queue. This solution is superior to a bespoke solution as all locking and container_of casting is integrated, so the interface is simple. Despite the similar name, this solution meets a distinctly different need to kfifo. kfifo provides a fixed sized circular buffer to which data can be added at one end and removed at the other, and does not provide any locking. lwq does not have any size limit and works with data structures (objects?) rather than data (bytes). A unit test for basic functionality, which runs at boot time, is included. Signed-off-by: NeilBrown <neilb@suse.de> Cc: Andrew Morton <akpm@linux-foundation.org> Cc: "Liam R. Howlett" <Liam.Howlett@oracle.com> Cc: Kees Cook <keescook@chromium.org> Cc: Greg Kroah-Hartman <gregkh@linuxfoundation.org> Cc: David Gow <davidgow@google.com> Cc: linux-kernel@vger.kernel.org Message-Id: <20230911111333.4d1a872330e924a00acb905b@linux-foundation.org> Signed-off-by: Chuck Lever <chuck.lever@oracle.com>
125 lines
3.7 KiB
C
125 lines
3.7 KiB
C
/* SPDX-License-Identifier: GPL-2.0-only */
|
|
|
|
#ifndef LWQ_H
|
|
#define LWQ_H
|
|
/*
|
|
* Light-weight single-linked queue built from llist
|
|
*
|
|
* Entries can be enqueued from any context with no locking.
|
|
* Entries can be dequeued from process context with integrated locking.
|
|
*
|
|
* 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/container_of.h>
|
|
#include <linux/spinlock.h>
|
|
#include <linux/llist.h>
|
|
|
|
struct lwq_node {
|
|
struct llist_node node;
|
|
};
|
|
|
|
struct lwq {
|
|
spinlock_t lock;
|
|
struct llist_node *ready; /* entries to be dequeued */
|
|
struct llist_head new; /* entries being enqueued */
|
|
};
|
|
|
|
/**
|
|
* lwq_init - initialise a lwq
|
|
* @q: the lwq object
|
|
*/
|
|
static inline void lwq_init(struct lwq *q)
|
|
{
|
|
spin_lock_init(&q->lock);
|
|
q->ready = NULL;
|
|
init_llist_head(&q->new);
|
|
}
|
|
|
|
/**
|
|
* lwq_empty - test if lwq contains any entry
|
|
* @q: the lwq object
|
|
*
|
|
* This empty test contains an acquire barrier so that if a wakeup
|
|
* is sent when lwq_dequeue returns true, it is safe to go to sleep after
|
|
* a test on lwq_empty().
|
|
*/
|
|
static inline bool lwq_empty(struct lwq *q)
|
|
{
|
|
/* acquire ensures ordering wrt lwq_enqueue() */
|
|
return smp_load_acquire(&q->ready) == NULL && llist_empty(&q->new);
|
|
}
|
|
|
|
struct llist_node *__lwq_dequeue(struct lwq *q);
|
|
/**
|
|
* lwq_dequeue - dequeue first (oldest) entry from lwq
|
|
* @q: the queue to dequeue from
|
|
* @type: the type of object to return
|
|
* @member: them member in returned object which is an lwq_node.
|
|
*
|
|
* Remove a single object from the lwq and return it. This will take
|
|
* a spinlock and so must always be called in the same context, typcially
|
|
* process contet.
|
|
*/
|
|
#define lwq_dequeue(q, type, member) \
|
|
({ struct llist_node *_n = __lwq_dequeue(q); \
|
|
_n ? container_of(_n, type, member.node) : NULL; })
|
|
|
|
struct llist_node *lwq_dequeue_all(struct lwq *q);
|
|
|
|
/**
|
|
* lwq_for_each_safe - iterate over detached queue allowing deletion
|
|
* @_n: iterator variable
|
|
* @_t1: temporary struct llist_node **
|
|
* @_t2: temporary struct llist_node *
|
|
* @_l: address of llist_node pointer from lwq_dequeue_all()
|
|
* @_member: member in _n where lwq_node is found.
|
|
*
|
|
* Iterate over members in a dequeued list. If the iterator variable
|
|
* is set to NULL, the iterator removes that entry from the queue.
|
|
*/
|
|
#define lwq_for_each_safe(_n, _t1, _t2, _l, _member) \
|
|
for (_t1 = (_l); \
|
|
*(_t1) ? (_n = container_of(*(_t1), typeof(*(_n)), _member.node),\
|
|
_t2 = ((*_t1)->next), \
|
|
true) \
|
|
: false; \
|
|
(_n) ? (_t1 = &(_n)->_member.node.next, 0) \
|
|
: ((*(_t1) = (_t2)), 0))
|
|
|
|
/**
|
|
* lwq_enqueue - add a new item to the end of the queue
|
|
* @n - the lwq_node embedded in the item to be added
|
|
* @q - the lwq to append to.
|
|
*
|
|
* No locking is needed to append to the queue so this can
|
|
* be called from any context.
|
|
* Return %true is the list may have previously been empty.
|
|
*/
|
|
static inline bool lwq_enqueue(struct lwq_node *n, struct lwq *q)
|
|
{
|
|
/* acquire enqures ordering wrt lwq_dequeue */
|
|
return llist_add(&n->node, &q->new) &&
|
|
smp_load_acquire(&q->ready) == NULL;
|
|
}
|
|
|
|
/**
|
|
* lwq_enqueue_batch - add a list of new items to the end of the queue
|
|
* @n - the lwq_node embedded in the first item to be added
|
|
* @q - the lwq to append to.
|
|
*
|
|
* No locking is needed to append to the queue so this can
|
|
* be called from any context.
|
|
* Return %true is the list may have previously been empty.
|
|
*/
|
|
static inline bool lwq_enqueue_batch(struct llist_node *n, struct lwq *q)
|
|
{
|
|
struct llist_node *e = n;
|
|
|
|
/* acquire enqures ordering wrt lwq_dequeue */
|
|
return llist_add_batch(llist_reverse_order(n), e, &q->new) &&
|
|
smp_load_acquire(&q->ready) == NULL;
|
|
}
|
|
#endif /* LWQ_H */
|