File:  [NetBSD Developer Wiki] / wikisrc / projects / project / atomic_fifo_lifo_queues.mdwn
Revision 1.1: download - view: text, annotated - select for diffs
Thu Nov 10 03:06:51 2011 UTC (8 years, 4 months ago) by jmmv
Branches: MAIN
CVS tags: HEAD
Add a specific proposal for the SMP networking project.

This proposal is built on top of several individual, smaller projects, all
of which are related to achieve the goals of SMP support and modularity on
the network stack.  Keep in mind that this is just that: a proposal.
Applicants could still come up with their own ideas.

The text of all these new pages is mostly a copy/paste of the original
document written by matt@ (see
I have done some minor edits (hopefully not changing any of the technical
details) and added some preliminary texts to the pages.  (I was unable to
parse some of the sentences though, so they remain "as is"...)

    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"
   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 <> software: FreeBSD-CVSweb