1.\" $NetBSD: pslist.9,v 1.19 2021/11/06 23:29:03 riastradh Exp $ 2.\" 3.\" Copyright (c) 2016 The NetBSD Foundation, Inc. 4.\" All rights reserved. 5.\" 6.\" This code is derived from software contributed to The NetBSD Foundation 7.\" by Taylor R. Campbell. 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 July 7, 2016 31.Dt PSLIST 9 32.Os 33.\""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""" 34.Sh NAME 35.Nm pslist 36.Nd pserialize-safe linked lists 37.\""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""" 38.Sh SYNOPSIS 39.In sys/pslist.h 40.\" Exclusive operations 41.Vt struct pslist_head head No = Dv PSLIST_INITIALIZER ; 42.Vt struct pslist_entry entry No = Dv PSLIST_ENTRY_INITIALIZER ; 43.Ft void 44.Fn PSLIST_INIT "struct pslist_head *head" 45.Ft void 46.Fn PSLIST_DESTROY "struct pslist_head *head" 47.Ft void 48.Fn PSLIST_ENTRY_INIT "TYPE *element" "PSLIST_ENTRY NAME" 49.Ft void 50.Fn PSLIST_ENTRY_DESTROY "TYPE *element" "PSLIST_ENTRY NAME" 51.\" Writer operations 52.Ft void 53.Fn PSLIST_WRITER_INSERT_HEAD "struct pslist_head *head" "TYPE *new" "PSLIST_ENTRY NAME" 54.Ft void 55.Fn PSLIST_WRITER_INSERT_BEFORE "TYPE *element" "TYPE *new" "PSLIST_ENTRY NAME" 56.Ft void 57.Fn PSLIST_WRITER_INSERT_AFTER "TYPE *element" "TYPE *new" "PSLIST_ENTRY NAME" 58.Ft void 59.Fn PSLIST_WRITER_REMOVE "TYPE *element" "PSLIST_ENTRY NAME" 60.Ft TYPE * 61.Fn PSLIST_WRITER_FIRST "const struct pslist *head" "TYPE" "PSLIST_ENTRY NAME" 62.Ft TYPE * 63.Fn PSLIST_WRITER_NEXT "const TYPE *element" "TYPE" "PSLIST_ENTRY NAME" 64.Fn PSLIST_WRITER_FOREACH "const TYPE *element" "const struct pslist_head *head" "TYPE" "PSLIST_ENTRY NAME" 65.\" Reader operations 66.Ft TYPE * 67.Fn PSLIST_READER_FIRST "const struct pslist *head" "TYPE" "PSLIST_ENTRY NAME" 68.Ft TYPE * 69.Fn PSLIST_READER_NEXT "const TYPE *element" "TYPE" "PSLIST_ENTRY NAME" 70.Fn PSLIST_READER_FOREACH "const TYPE *element" "const struct pslist_head *head" "TYPE" "PSLIST_ENTRY NAME" 71.\""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""" 72.Sh DESCRIPTION 73The 74.Nm 75data structure is a linked list like 76.Nm list 77in 78.Xr queue 3 . 79It is augmented with memory barriers so that any number of readers can 80safely run in parallel with at most one writer, without needing any 81interprocessor synchronization such as locks or atomics on the reader 82side. 83.\" 84.Pp 85The head of a linked list is represented by a 86.Vt struct pslist_head 87object allocated by the caller, e.g. by embedding it in another 88struct, which should be otherwise treated as opaque. 89A linked list head must be initialized with 90.Dv PSLIST_INITIALIZER 91or 92.Fn PSLIST_INIT 93before it may be used. 94When initialized, a list head represents an empty list. 95A list should be empty and destroyed with 96.Fn PSLIST_DESTROY 97before the 98.Vt struct pslist_head 99object's memory is reused. 100.\" 101.Pp 102Each entry in a linked list is represented by a 103.Vt struct pslist_entry 104object, also opaque, and embedded as a member in a caller-allocated 105structure called an 106.Em element . 107A 108.Vt struct pslist_entry 109object must be initialized with 110.Dv PSLIST_ENTRY_INITIALIZER 111or 112.Fn PSLIST_ENTRY_INIT 113before it may be used. 114.\" 115.Pp 116When initialized, a list entry is unassociated. 117Inserting an entry associates it with a particular list. 118Removing it 119partially disassociates it from that list and prevents new readers from 120finding it in the list, but allows extant parallel readers to continue 121reading the next entry. 122The caller must then wait, e.g. with 123.Xr pserialize_perform 9 , 124for all extant parallel readers to finish, before destroying the list 125entry with 126.Fn PSLIST_ENTRY_DESTROY 127and then freeing or reusing its memory. 128.\""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""" 129.Sh EXCLUSIVE OPERATIONS 130The following operations may be performed on list heads and entries 131when the caller has exclusive access to them \(em no parallel writers or 132readers may have access to the same objects. 133.\"""""""""""""""" 134.Bl -tag -width abcd 135.It Dv PSLIST_INITIALIZER 136Constant initializer for a 137.Vt struct pslist_head 138object. 139.\"""""""""""""""" 140.It Fn PSLIST_INIT head 141Initialize the list headed by 142.Fa head 143to be empty. 144.\"""""""""""""""" 145.It Fn PSLIST_DESTROY head 146Destroy the list headed by 147.Fa head , 148which must be empty. 149.Pp 150This has an effect only with the 151.Dv DIAGNOSTIC 152option, so it is not strictly necessary, but it can help to detect bugs 153early; see 154.Xr KASSERT 9 . 155.\"""""""""""""""" 156.It Dv PSLIST_ENTRY_INITIALIZER 157Constant initializer for an unassociated 158.Vt struct pslist_entry 159object. 160.\"""""""""""""""" 161.It Fn PSLIST_ENTRY_INIT element NAME 162Initialize the 163.Vt struct pslist_entry 164object 165.Fa element Ns Li -> Ns Fa NAME . 166.\"""""""""""""""" 167.It Fn PSLIST_ENTRY_DESTROY element NAME 168Destroy the 169.Vt struct pslist_entry 170object 171.Fa element Ns Li -> Ns Fa NAME . 172Either 173.Fa element 174must never have been inserted into a list, or it must have been 175inserted and removed, and the caller must have waited for all parallel 176readers to finish reading it first. 177.El 178.\""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""" 179.Sh WRITER OPERATIONS 180The following operations may be performed on list heads and entries 181when the caller has exclusive 182.Em write 183access to them \(em parallel readers for the same objects are allowed, 184but no parallel writers. 185.\"""""""""""""""" 186.Bl -tag -width abcd 187.It Fn PSLIST_WRITER_INSERT_HEAD head element NAME 188Insert the element 189.Fa element 190at the beginning of the list headed by 191.Fa head , 192before any existing elements in the list. 193.Pp 194The object 195.Fa element Ns Li -> Ns Fa NAME 196must be a 197.Vt struct pslist_entry 198object which has been initialized but not inserted. 199.\"""""""""""""""" 200.It Fn PSLIST_WRITER_INSERT_BEFORE element new NAME 201Insert the element 202.Fa new 203into a list before the element 204.Fa element . 205.Pp 206The object 207.Fa element Ns Li -> Ns Fa NAME 208must be a 209.Vt struct pslist_entry 210object which has been inserted into a list. 211The object 212.Fa new Ns Li -> Ns Fa NAME 213must be a 214.Vt struct pslist_entry 215.\"""""""""""""""" 216.It Fn PSLIST_WRITER_INSERT_AFTER element new NAME 217Insert the element 218.Fa new 219into a list after the element 220.Fa element . 221.Pp 222The object 223.Fa element Ns Li -> Ns Fa NAME 224must be a 225.Vt struct pslist_entry 226object which has been inserted into a list. 227The object 228.Fa new Ns Li -> Ns Fa NAME 229must be a 230.Vt struct pslist_entry 231.\"""""""""""""""" 232.It Fn PSLIST_WRITER_REMOVE element NAME 233Remove the element 234.Fa element 235from the list into which it has been inserted. 236.Pp 237The object 238.Fa element Ns Li -> Ns Fa NAME 239must be a 240.Vt struct pslist_entry 241object which has been inserted into a list. 242.\"""""""""""""""" 243.It Fn PSLIST_WRITER_FIRST head type NAME 244Return a pointer to the first element 245.Fa o 246of type 247.Fa type 248with a 249.Vt struct pslist_entry 250member 251.Fa o Ns Li -> Ns Fa NAME , 252or 253.Dv NULL 254if the list is empty. 255.\"""""""""""""""" 256.It Fn PSLIST_WRITER_NEXT element type NAME 257Return a pointer to the next element 258.Fa o 259of type 260.Fa type 261with a 262.Vt struct pslist_entry 263member 264.Fa o Ns Li -> Ns Fa NAME 265after 266.Fa element 267in a list, or 268.Dv NULL 269if there are no elements after 270.Fa element . 271.\"""""""""""""""" 272.It Fn PSLIST_WRITER_FOREACH element head type NAME 273Loop header for iterating over each element 274.Fa element 275of type 276.Fa type 277with 278.Vt struct pslist_entry 279member 280.Fa element Ns Li -> Ns Fa NAME 281starting at the list head 282.Fa head . 283.Pp 284The caller must not modify the list while iterating over it. 285.El 286.\""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""" 287.Sh READER OPERATIONS 288The following operations may be performed on list heads and entries 289when the caller is in a passively serialized read section \(em see 290.Xr pserialize 9 . 291.Bl -tag -width abcd 292.\"""""""""""""""" 293.It Fn PSLIST_READER_FIRST head type NAME 294Return a pointer to the first element 295.Fa o 296of type 297.Fa type 298with a 299.Vt struct pslist_entry 300member 301.Fa o Ns Li -> Ns Fa NAME , 302or 303.Dv NULL 304if the list is empty. 305.\"""""""""""""""" 306.It Fn PSLIST_READER_NEXT element type NAME 307Return a pointer to the next element 308.Fa o 309of type 310.Fa type 311with a 312.Vt struct pslist_entry 313member 314.Fa o Ns Li -> Ns Fa NAME 315after 316.Fa element 317in a list, or 318.Dv NULL 319if there are no elements after 320.Fa element . 321.\"""""""""""""""" 322.It Fn PSLIST_READER_FOREACH element head type NAME 323Loop header for iterating over each element 324.Fa element 325of type 326.Fa type 327with 328.Vt struct pslist_entry 329member 330.Fa element Ns Li -> Ns Fa NAME 331starting at the list head 332.Fa head . 333.El 334.Sh EXAMPLES 335Example frotz structure and global state: 336.Bd -literal 337 struct frotz { 338 uint64_t f_key; 339 uint64_t f_datum; 340 struct pslist_entry f_entry; 341 }; 342 343 static struct { 344 kmutex_t lock; 345 pserialize_t psz; 346 struct pslist_head list; 347 struct pool pool; 348 } frobnitzem __cacheline_aligned; 349.Ed 350.Pp 351Initialize the global state: 352.Bd -literal 353 mutex_init(&frobnitzem.lock, MUTEX_DEFAULT, IPL_NONE); 354 frobnitzem.psz = pserialize_create(); 355 PSLIST_INIT(&frobnitzem.list); 356 pool_init(&frobnitzem.pool, sizeof(struct frotz), ...); 357.Ed 358.Pp 359Create and publish a frotz: 360.Bd -literal 361 uint64_t key = ...; 362 uint64_t datum = ...; 363 364 struct frotz *f = pool_get(&frobnitzem.pool, PR_WAITOK); 365 366 /* Initialize f. */ 367 f->f_key = key; 368 f->f_datum = datum; 369 PSLIST_ENTRY_INIT(f, f_entry); 370 371 /* Publish it. */ 372 mutex_enter(&frobnitzem.lock); 373 PSLIST_WRITER_INSERT_HEAD(&frobnitzem.list, f, f_entry); 374 mutex_exit(&frobnitzem.lock); 375.Ed 376.Pp 377Look up a frotz and return its associated datum: 378.Bd -literal 379 uint64_t key = ...; 380 struct frotz *f; 381 int error = ENOENT; 382 int s; 383 384 s = pserialize_read_enter(); 385 PSLIST_READER_FOREACH(f, &frobnitzem.list, struct frotz, f_entry) { 386 if (f->f_key == key) { 387 *datump = f->f_datum; 388 error = 0; 389 break; 390 } 391 } 392 pserialize_read_exit(s); 393 return error; 394.Ed 395.Pp 396Remove a frotz and wait for readers to finish using it before reusing 397the memory allocated for it: 398.Bd -literal 399 struct frotz *f = ...; 400 401 mutex_enter(&frobnitzem.lock); 402 PSLIST_WRITER_REMOVE(f, f_entry); 403 mutex_exit(&frobnitzem.lock); 404 405 pserialize_perform(&frobnitzem.psz); 406 407 PSLIST_ENTRY_DESTROY(f, f_entry); 408 pool_put(&frobnitzem.pool, f); 409.Ed 410.\""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""" 411.Sh CODE REFERENCES 412The 413.Nm 414data structure is implemented by static inlines and macros in 415.Pa sys/sys/pslist.h . 416.\""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""" 417.Sh SEE ALSO 418.Xr queue 3 , 419.Xr pserialize 9 , 420.Xr psref 9 421.\""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""" 422.Sh HISTORY 423The 424.Nm 425data structure first appeared in 426.Nx 8.0 . 427.\""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""" 428.Sh AUTHORS 429.An Taylor R Campbell Aq Mt riastradh@NetBSD.org 430