File:  [NetBSD Developer Wiki] / wikisrc / projects / project / atomic_pcq.mdwn
Revision 1.1: download - view: text, annotated - select for diffs
Thu Nov 10 03:06:51 2011 UTC (9 years, 2 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"...)

[[!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);`

[[!tag smp_networking]]

CVSweb for NetBSD wikisrc <> software: FreeBSD-CVSweb