File:  [NetBSD Developer Wiki] / wikisrc / projects / project / atomic_pcq.mdwn
Revision 1.2: download - view: text, annotated - select for diffs
Mon Nov 28 22:51:22 2011 UTC (3 years, 8 months ago) by jmmv
Branches: MAIN
CVS tags: HEAD
Mark atomic_pcq as done; matt@ had implemented this already three years ago.
Also avoid showing completed projects in the smp_networking list.

Reported by private mail.

[[!template id=project

title="Lockless, atomic producer/consumer queues"


funded="The NetBSD Foundation"

This project proposal is a subtask of [[smp_networking]] and is elegible
for funding independently.

The goal of this project is to implement lockess and atomic
producer/consumer queues (PCQs) in the kernel.  A PCQ allows multiple
writers (producers) but only a single reader (consumer).  Compare-And-Store
operations are used to allow lockless updates.  The consumer is expected to
be protected by a mutex that covers the structure that the PCQ is embedded
into (e.g. socket lock, ifnet hwlock).  These queues operate in a First-In,
First-Out (FIFO) manner.  The act of inserting or removing an item from a
PCQ does not modify the item in any way.  A PCQ does not prevent an item
being inserted multiple times into a single PCQ.

Since this structure is not specific to networking it has to be accessed
via `<sys/pcq.h>` and the code has to live in `kern/subr_pcq.c`.

The proposed interface looks like this:

* `bool pcq_put(pcq_t *pcq, void *item);`

  Places item at the end of the queue.  If there is no room in the queue
  for the item, false is returned; otherwise true is returned.  The item
  must not have the value `NULL`.

* `void *pcq_peek(pcq_t *pcq);`

  Returns the next item to be consumed from the queue but does not remove
  it from the queue.  If the queue is empty, `NULL` is returned.

* `void *pcq_get(pcq_t *pcq);`

  Removes the next item to be consumed from the queue and returns it.  If
  the queue is empty, `NULL` is returned.

* `size_t pcq_maxitems(pcq_t *pcq);`

  Returns the maximum number of items that the queue can store at any one

* `pcq_t *pcq_create(size_t maxlen, km_flags_t kmflags);`

* `void pcq_destroy(pcq_t *pcq);`

done_by="""Matt Thomas"""

[[!tag smp_networking]]

CVSweb for NetBSD wikisrc <> software: FreeBSD-CVSweb