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

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: funded="The NetBSD Foundation"
        !            14: 
        !            15: description="""
        !            16: This project proposal is a subtask of [[smp_networking]] and is elegible
        !            17: for funding independently.
        !            18: 
        !            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.
        !            26: 
        !            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.
        !            29: 
        !            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`.
        !            33: 
        !            34: The proposed interface looks like this:
        !            35: 
        !            36: * `void atomic_qinit(atomic_queue_t *q, size_t offset);`
        !            37: 
        !            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`.
        !            42: 
        !            43: * `void *atomic_qpeek(atomic_queue_t *q);`
        !            44: 
        !            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.
        !            49: 
        !            50: * `void *atomic_qpop(atomic_queue_t *q);`
        !            51: 
        !            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.
        !            59: 
        !            60: * `void atomic_qpush_fifo(atomic_queue_t *q, void *item);`
        !            61: 
        !            62:   Places `item` at the tail of the `atomic_queue_t` queue at `q`.
        !            63: 
        !            64: * `void atomic_qpush_lifo(atomic_queue_t *q, void *item);`
        !            65: 
        !            66:   Places `item` at the head of the `atomic_queue_t` queue at `q`.
        !            67: """
        !            68: ]]
        !            69: 
        !            70: [[!tag smp_networking]]

CVSweb for NetBSD wikisrc <wikimaster@NetBSD.org> software: FreeBSD-CVSweb