.\"     $NetBSD: pcq.9,v 1.8.14.1 2023/07/30 12:13:02 martin Exp $
.\"
.\" Copyright (c) 2010 The NetBSD Foundation, Inc.
.\" All rights reserved.
.\"
.\" This code is derived from software contributed to The NetBSD Foundation
.\" by Matt Thomas.
.\"
.\" Redistribution and use in source and binary forms, with or without
.\" modification, are permitted provided that the following conditions
.\" are met:
.\" 1. Redistributions of source code must retain the above copyright
.\"    notice, this list of conditions and the following disclaimer.
.\" 2. Redistributions in binary form must reproduce the above copyright
.\"    notice, this list of conditions and the following disclaimer in the
.\"    documentation and/or other materials provided with the distribution.
.\"
.\" THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
.\" ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
.\" TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
.\" PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
.\" BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
.\" CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
.\" SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
.\" INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
.\" CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
.\" ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
.\" POSSIBILITY OF SUCH DAMAGE.
.\"
.Dd January 22, 2012
.Dt PCQ 9
.Os
.Sh NAME
.Nm pcq
.Nd producer/consumer queue
.Sh SYNOPSIS
.In sys/pcq.h
.Ft pcq_t *
.Fn pcq_create "size_t maxlen" "km_flags_t kmflags"
.Ft void
.Fn pcq_destroy "pcq_t *pcq"
.Ft void *
.Fn pcq_get "pcq_t *pcq"
.Ft size_t
.Fn pcq_maxitems "pcq_t *pcq"
.Ft void *
.Fn pcq_peek "pcq_t *pcq"
.Ft bool
.Fn pcq_put "pcq_t *pcq" "void *item"
.Sh DESCRIPTION
The machine-independent
.Nm
interface provides lockless producer/consumer queues.
A queue
.Po
.Vt pcq_t
.Pc
allows multiple writers
.Pq producers ,
but only a single reader
.Pq consumer .
The consumer is expected to be protected by a lock that covers
the structure that the
.Vt pcq_t
is embedded into
.Po
e.g., socket lock, ifnet hwlock
.Pc .
These queues operate in a first-in, first-out
.Pq FIFO
manner.
The act of inserting or removing an item from a
.Vt pcq_t
does not modify the item in any way.
.Nm
does not prevent an item from being inserted multiple times into a single
.Vt pcq_t .
.Sh FUNCTIONS
.Bl -tag -width compact
.It Fn pcq_create "maxlen" "kmflags"
Create a queue that can store at most
.Fa maxlen
items at one time.
.Fa kmflags
should be either
.Dv KM_SLEEP ,
if
.Fn pcq_create
is allowed to sleep until resources are available, or
.Dv KM_NOSLEEP
if it should return
.Dv NULL
immediately, if resources are unavailable.
.It Fn pcq_destroy "pcq"
Free the resources held by
.Fa pcq .
.It Fn pcq_get "pcq"
Remove the next item to be consumed from the queue and return it.
If the queue is empty,
return
.Dv NULL .
The caller must prevent concurrent gets from occurring.
.It Fn pcq_maxitems "pcq"
Return the maximum number of items that the queue can store at
any one time.
.It Fn pcq_peek "pcq"
Return the next item to be consumed from the queue but do not remove
it from the queue.
If the queue is empty,
return
.Dv NULL .
.It Fn pcq_put "pcq" "item"
Place an item at the end of the queue.
If there is no room in the queue for the item, return
.Dv false ;
otherwise, return
.Dv true .
The item must not have the value of
.Dv NULL .
.El
.Ss Memory ordering
Any memory operations sequenced before
.Fn pcq_put
of an item in one thread happen before all memory operations with data
dependencies on the item returned by
.Fn pcq_get
or
.Fn pcq_peek
in another thread.
For example:
.Bd -literal -offset indent
int mumble;

/* producer */
mumble = 42;			// A
foo->x = 123;			// B
refcnt = foo->refcnt;		// C
pcq_put(pcq, foo);
KASSERT(refcnt == 0);

/* consumer */
foo = pcq_get(pcq);
if (foo == NULL)
	return;
atomic_inc_uint(&foo->refcnt);	// D
x = foo->x;			// E
if (x == 123)
	KASSERT(mumble == 42);	// F
.Ed
.Pp
In this example, memory operations B and C happen-before D and E.
However, no ordering is guaranteed for A or F relative to any other
memory operations, because the memory location of
.Fa mumble
is independent of the pointer
.Fa foo
returned by
.Fn pcq_get .
.Pp
If you must guarantee A happens before F, then on the consumer side,
after
.Fn pcq_get
or
.Fn pcq_peek ,
you can call
.Fn membar_acquire
to turn it into an acquire operation instead of a consume operation;
.Fn pcq_put
serves as the matching release operation.
.Po
This is a little dicey.
Perhaps there should be separate
.Fn pcq_peek_acq
and
.Fn pcq_get_acq
operations if this semantics is necessary.
.Pc
.Sh CODE REFERENCES
The
.Nm
interface is implemented within the file
.Pa sys/kern/subr_pcq.c .
.\" .Sh EXAMPLES
.Sh SEE ALSO
.Xr atomic_ops 3 ,
.Xr queue 3
.Sh HISTORY
The
.Nm
interface first appeared in
.Nx 6.0 .
.\" .Sh CAVEATS
.\" .Sh BUGS
.\" .Sh SECURITY CONSIDERATIONS