Annotation of wikisrc/projects/project/atomic_fifo_lifo_queues.mdwn, revision 1.2
1.1 jmmv 1: [[!template id=project
3: title="Lockless, atomic FIFO/LIFO queues"
1.2 ! riastrad 15: This project proposal is a subtask of [[smp_networking]].
1.1 jmmv 16:
17: The goal of this project is to implement lockless and atomic FIFO/LIFO
18: queues in the kernel. The routines to be implemented allow for commonly
19: typed items to be locklessly inserted at either the head or tail of a queue
20: for either last-in, first-out (LIFO) or first-in, first-out (FIFO)
21: behavior, respectively. However, a queue is not instrinsicly LIFO or FIFO.
22: Its behavior is determined solely by which method each item was pushed onto
23: the queue.
25: It is only possible for an item to removed from the head of queue. This
26: removal is also performed in a lockless manner.
28: All items in the queue must share a `atomic_queue_link_t` member at the
29: same offset from the beginning of item. This offset is passed to
32: The proposed interface looks like this:
34: * `void atomic_qinit(atomic_queue_t *q, size_t offset);`
36: Initializes the atomic_queue_t queue at `q`. `offset` is the offset to
37: the `atomic_queue_link_t` inside the data structure where the pointer to
38: the next item in this queue will be placed. It should be obtained using
41: * `void *atomic_qpeek(atomic_queue_t *q);`
43: Returns a pointer to the item at the head of the supplied queue `q`. If
44: there was no item because the queue was empty, `NULL` is returned. No
45: item is removed from the queue. Given this is an unlocked operation, it
46: should only be used as a hint as whether the queue is empty or not.
48: * `void *atomic_qpop(atomic_queue_t *q);`
50: Removes the item (if present) at the head of the supplied queue `q` and
51: returns a pointer to it. If there was no item to remove because the
52: queue was empty, `NULL` is returned. Because this routine uses atomic
53: Compare-And-Store operations, the returned item should stay accessible
54: for some indeterminate time so that other interrupted or concurrent
55: callers to this function with this `q` can continue to deference it
56: without trapping.
58: * `void atomic_qpush_fifo(atomic_queue_t *q, void *item);`
60: Places `item` at the tail of the `atomic_queue_t` queue at `q`.
62: * `void atomic_qpush_lifo(atomic_queue_t *q, void *item);`
64: Places `item` at the head of the `atomic_queue_t` queue at `q`.
68: [[!tag smp_networking]]
CVSweb for NetBSD wikisrc <wikimaster@NetBSD.org> software: FreeBSD-CVSweb