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