.\" $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