Return to atomic_fifo_lifo_queues.mdwn CVS log

Up to [NetBSD Developer Wiki] / wikisrc / projects / project

Annotation of wikisrc/projects/project/atomic_fifo_lifo_queues.mdwn, revision 1.2

1.1       jmmv        1: [[!template id=project
                      2: 
                      3: title="Lockless, atomic FIFO/LIFO queues"
                      4: 
                      5: contact="""
                      6: [tech-kern](mailto:tech-kern@NetBSD.org),
                      7: [board](mailto:board@NetBSD.org),
                      8: [core](mailto:core@NetBSD.org)
                      9: """
                     10: 
                     11: category="kernel"
                     12: difficulty="hard"
                     13: 
                     14: description="""
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.
                     24: 
                     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.
                     27: 
                     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`.
                     31: 
                     32: The proposed interface looks like this:
                     33: 
                     34: * `void atomic_qinit(atomic_queue_t *q, size_t offset);`
                     35: 
                     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`.
                     40: 
                     41: * `void *atomic_qpeek(atomic_queue_t *q);`
                     42: 
                     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.
                     47: 
                     48: * `void *atomic_qpop(atomic_queue_t *q);`
                     49: 
                     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.
                     57: 
                     58: * `void atomic_qpush_fifo(atomic_queue_t *q, void *item);`
                     59: 
                     60:   Places `item` at the tail of the `atomic_queue_t` queue at `q`.
                     61: 
                     62: * `void atomic_qpush_lifo(atomic_queue_t *q, void *item);`
                     63: 
                     64:   Places `item` at the head of the `atomic_queue_t` queue at `q`.
                     65: """
                     66: ]]
                     67: 
                     68: [[!tag smp_networking]]