1.\" $NetBSD: pcq.9,v 1.9 2023/02/23 03:03:23 riastradh Exp $ 2.\" 3.\" Copyright (c) 2010 The NetBSD Foundation, Inc. 4.\" All rights reserved. 5.\" 6.\" This code is derived from software contributed to The NetBSD Foundation 7.\" by Matt Thomas. 8.\" 9.\" Redistribution and use in source and binary forms, with or without 10.\" modification, are permitted provided that the following conditions 11.\" are met: 12.\" 1. Redistributions of source code must retain the above copyright 13.\" notice, this list of conditions and the following disclaimer. 14.\" 2. Redistributions in binary form must reproduce the above copyright 15.\" notice, this list of conditions and the following disclaimer in the 16.\" documentation and/or other materials provided with the distribution. 17.\" 18.\" THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS 19.\" ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED 20.\" TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 21.\" PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS 22.\" BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 23.\" CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 24.\" SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 25.\" INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 26.\" CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 27.\" ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 28.\" POSSIBILITY OF SUCH DAMAGE. 29.\" 30.Dd January 22, 2012 31.Dt PCQ 9 32.Os 33.Sh NAME 34.Nm pcq 35.Nd producer/consumer queue 36.Sh SYNOPSIS 37.In sys/pcq.h 38.Ft pcq_t * 39.Fn pcq_create "size_t maxlen" "km_flags_t kmflags" 40.Ft void 41.Fn pcq_destroy "pcq_t *pcq" 42.Ft void * 43.Fn pcq_get "pcq_t *pcq" 44.Ft size_t 45.Fn pcq_maxitems "pcq_t *pcq" 46.Ft void * 47.Fn pcq_peek "pcq_t *pcq" 48.Ft bool 49.Fn pcq_put "pcq_t *pcq" "void *item" 50.Sh DESCRIPTION 51The machine-independent 52.Nm 53interface provides lockless producer/consumer queues. 54A queue 55.Po 56.Vt pcq_t 57.Pc 58allows multiple writers 59.Pq producers , 60but only a single reader 61.Pq consumer . 62The consumer is expected to be protected by a lock that covers 63the structure that the 64.Vt pcq_t 65is embedded into 66.Po 67e.g., socket lock, ifnet hwlock 68.Pc . 69These queues operate in a first-in, first-out 70.Pq FIFO 71manner. 72The act of inserting or removing an item from a 73.Vt pcq_t 74does not modify the item in any way. 75.Nm 76does not prevent an item from being inserted multiple times into a single 77.Vt pcq_t . 78.Sh FUNCTIONS 79.Bl -tag -width compact 80.It Fn pcq_create "maxlen" "kmflags" 81Create a queue that can store at most 82.Fa maxlen 83items at one time. 84.Fa kmflags 85should be either 86.Dv KM_SLEEP , 87if 88.Fn pcq_create 89is allowed to sleep until resources are available, or 90.Dv KM_NOSLEEP 91if it should return 92.Dv NULL 93immediately, if resources are unavailable. 94.It Fn pcq_destroy "pcq" 95Free the resources held by 96.Fa pcq . 97.It Fn pcq_get "pcq" 98Remove the next item to be consumed from the queue and return it. 99If the queue is empty, 100return 101.Dv NULL . 102The caller must prevent concurrent gets from occurring. 103.It Fn pcq_maxitems "pcq" 104Return the maximum number of items that the queue can store at 105any one time. 106.It Fn pcq_peek "pcq" 107Return the next item to be consumed from the queue but do not remove 108it from the queue. 109If the queue is empty, 110return 111.Dv NULL . 112.It Fn pcq_put "pcq" "item" 113Place an item at the end of the queue. 114If there is no room in the queue for the item, return 115.Dv false ; 116otherwise, return 117.Dv true . 118The item must not have the value of 119.Dv NULL . 120.El 121.Ss Memory ordering 122Any memory operations sequenced before 123.Fn pcq_put 124of an item in one thread happen before all memory operations with data 125dependencies on the item returned by 126.Fn pcq_get 127or 128.Fn pcq_peek 129in another thread. 130For example: 131.Bd -literal -offset indent 132int mumble; 133 134/* producer */ 135mumble = 42; // A 136foo->x = 123; // B 137refcnt = foo->refcnt; // C 138pcq_put(pcq, foo); 139KASSERT(refcnt == 0); 140 141/* consumer */ 142foo = pcq_get(pcq); 143if (foo == NULL) 144 return; 145atomic_inc_uint(&foo->refcnt); // D 146x = foo->x; // E 147if (x == 123) 148 KASSERT(mumble == 42); // F 149.Ed 150.Pp 151In this example, memory operations B and C happen-before D and E. 152However, no ordering is guaranteed for A or F relative to any other 153memory operations, because the memory location of 154.Fa mumble 155is independent of the pointer 156.Fa foo 157returned by 158.Fn pcq_get . 159.Pp 160If you must guarantee A happens before F, then on the consumer side, 161after 162.Fn pcq_get 163or 164.Fn pcq_peek , 165you can call 166.Fn membar_acquire 167to turn it into an acquire operation instead of a consume operation; 168.Fn pcq_put 169serves as the matching release operation. 170.Po 171This is a little dicey. 172Perhaps there should be separate 173.Fn pcq_peek_acq 174and 175.Fn pcq_get_acq 176operations if this semantics is necessary. 177.Pc 178.Sh CODE REFERENCES 179The 180.Nm 181interface is implemented within the file 182.Pa sys/kern/subr_pcq.c . 183.\" .Sh EXAMPLES 184.Sh SEE ALSO 185.Xr atomic_ops 3 , 186.Xr queue 3 187.Sh HISTORY 188The 189.Nm 190interface first appeared in 191.Nx 6.0 . 192.\" .Sh CAVEATS 193.\" .Sh BUGS 194.\" .Sh SECURITY CONSIDERATIONS 195