1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
|
.\" $NetBSD: pcq.9,v 1.9 2023/02/23 03:03:23 riastradh 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
|
