Return to atomic_pcq.mdwn CVS log

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

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

1.1     ! jmmv        1: [[!template id=project
        !             2: 
        !             3: title="Lockless, atomic producer/consumer 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 lockess and atomic
        !            20: producer/consumer queues (PCQs) in the kernel.  A PCQ allows multiple
        !            21: writers (producers) but only a single reader (consumer).  Compare-And-Store
        !            22: operations are used to allow lockless updates.  The consumer is expected to
        !            23: be protected by a mutex that covers the structure that the PCQ is embedded
        !            24: into (e.g. socket lock, ifnet hwlock).  These queues operate in a First-In,
        !            25: First-Out (FIFO) manner.  The act of inserting or removing an item from a
        !            26: PCQ does not modify the item in any way.  A PCQ does not prevent an item
        !            27: being inserted multiple times into a single PCQ.
        !            28: 
        !            29: Since this structure is not specific to networking it has to be accessed
        !            30: via `<sys/pcq.h>` and the code has to live in `kern/subr_pcq.c`.
        !            31: 
        !            32: The proposed interface looks like this:
        !            33: 
        !            34: * `bool pcq_put(pcq_t *pcq, void *item);`
        !            35: 
        !            36:   Places item at the end of the queue.  If there is no room in the queue
        !            37:   for the item, false is returned; otherwise true is returned.  The item
        !            38:   must not have the value `NULL`.
        !            39: 
        !            40: * `void *pcq_peek(pcq_t *pcq);`
        !            41: 
        !            42:   Returns the next item to be consumed from the queue but does not remove
        !            43:   it from the queue.  If the queue is empty, `NULL` is returned.
        !            44: 
        !            45: * `void *pcq_get(pcq_t *pcq);`
        !            46: 
        !            47:   Removes the next item to be consumed from the queue and returns it.  If
        !            48:   the queue is empty, `NULL` is returned.
        !            49: 
        !            50: * `size_t pcq_maxitems(pcq_t *pcq);`
        !            51: 
        !            52:   Returns the maximum number of items that the queue can store at any one
        !            53:   time.
        !            54: 
        !            55: * `pcq_t *pcq_create(size_t maxlen, km_flags_t kmflags);`
        !            56: 
        !            57: * `void pcq_destroy(pcq_t *pcq);`
        !            58: """
        !            59: ]]
        !            60: 
        !            61: [[!tag smp_networking]]