File:  [NetBSD Developer Wiki] / wikisrc / projects / project / atomic_fifo_lifo_queues.mdwn
Revision 1.2: download - view: text, annotated - select for diffs
Tue Jan 3 20:51:24 2017 UTC (3 years, 2 months ago) by riastradh
Branches: MAIN
CVS tags: HEAD
Remove preapproved funding designations.

Per discussion between board and core, these stale designations will
be replaced by something we hope to be more lively and maintained.

    1: [[!template id=project
    3: title="Lockless, atomic FIFO/LIFO queues"
    5: contact="""
    6: [tech-kern](,
    7: [board](,
    8: [core](
    9: """
   11: category="kernel"
   12: difficulty="hard"
   14: description="""
   15: This project proposal is a subtask of [[smp_networking]].
   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
   30: `atomic_qinit`.
   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
   39:   `offsetof`.
   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`.
   65: """
   66: ]]
   68: [[!tag smp_networking]]

CVSweb for NetBSD wikisrc <> software: FreeBSD-CVSweb