1.\" $OpenBSD: SMR_LIST_INIT.9,v 1.8 2022/01/16 05:38:58 jsg Exp $ 2.\" 3.\" Copyright (c) 2019 Visa Hankala 4.\" 5.\" Permission to use, copy, modify, and distribute this software for any 6.\" purpose with or without fee is hereby granted, provided that the above 7.\" copyright notice and this permission notice appear in all copies. 8.\" 9.\" THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES 10.\" WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF 11.\" MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR 12.\" ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES 13.\" WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN 14.\" ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF 15.\" OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. 16.\" 17.Dd $Mdocdate: January 16 2022 $ 18.Dt SMR_LIST_INIT 9 19.Os 20.Sh NAME 21.Nm SMR_SLIST_ENTRY , 22.Nm SMR_SLIST_HEAD , 23.Nm SMR_SLIST_HEAD_INITIALIZER , 24.Nm SMR_SLIST_INIT , 25.Nm SMR_SLIST_FIRST , 26.Nm SMR_SLIST_NEXT , 27.Nm SMR_SLIST_FOREACH , 28.Nm SMR_SLIST_FIRST_LOCKED , 29.Nm SMR_SLIST_NEXT_LOCKED , 30.Nm SMR_SLIST_EMPTY_LOCKED , 31.Nm SMR_SLIST_FOREACH_LOCKED , 32.Nm SMR_SLIST_FOREACH_SAFE_LOCKED , 33.Nm SMR_SLIST_INSERT_HEAD_LOCKED , 34.Nm SMR_SLIST_INSERT_AFTER_LOCKED , 35.Nm SMR_SLIST_REMOVE_HEAD_LOCKED , 36.Nm SMR_SLIST_REMOVE_AFTER_LOCKED , 37.Nm SMR_SLIST_REMOVE_LOCKED , 38.Nm SMR_LIST_ENTRY , 39.Nm SMR_LIST_HEAD , 40.Nm SMR_LIST_HEAD_INITIALIZER , 41.Nm SMR_LIST_INIT , 42.Nm SMR_LIST_FIRST , 43.Nm SMR_LIST_NEXT , 44.Nm SMR_LIST_FOREACH , 45.Nm SMR_LIST_FIRST_LOCKED , 46.Nm SMR_LIST_NEXT_LOCKED , 47.Nm SMR_LIST_EMPTY_LOCKED , 48.Nm SMR_LIST_FOREACH_LOCKED , 49.Nm SMR_LIST_FOREACH_SAFE_LOCKED , 50.Nm SMR_LIST_INSERT_HEAD_LOCKED , 51.Nm SMR_LIST_INSERT_AFTER_LOCKED , 52.Nm SMR_LIST_INSERT_BEFORE_LOCKED , 53.Nm SMR_LIST_REMOVE_LOCKED , 54.Nm SMR_TAILQ_ENTRY , 55.Nm SMR_TAILQ_HEAD , 56.Nm SMR_TAILQ_HEAD_INITIALIZER , 57.Nm SMR_TAILQ_INIT , 58.Nm SMR_TAILQ_FIRST , 59.Nm SMR_TAILQ_NEXT , 60.Nm SMR_TAILQ_FOREACH , 61.Nm SMR_TAILQ_FIRST_LOCKED , 62.Nm SMR_TAILQ_NEXT_LOCKED , 63.Nm SMR_TAILQ_LAST_LOCKED , 64.Nm SMR_TAILQ_EMPTY_LOCKED , 65.Nm SMR_TAILQ_FOREACH_LOCKED , 66.Nm SMR_TAILQ_FOREACH_SAFE_LOCKED , 67.Nm SMR_TAILQ_INSERT_HEAD_LOCKED , 68.Nm SMR_TAILQ_INSERT_TAIL_LOCKED , 69.Nm SMR_TAILQ_INSERT_AFTER_LOCKED , 70.Nm SMR_TAILQ_INSERT_BEFORE_LOCKED , 71.Nm SMR_TAILQ_REMOVE_LOCKED 72.Nd SMR list macros 73.Sh SYNOPSIS 74.In sys/smr.h 75.Fn SMR_SLIST_ENTRY "TYPE" 76.Ft void 77.Fn SMR_SLIST_INIT "SMR_SLIST_HEAD *head" 78.Ft TYPE * 79.Fn SMR_SLIST_FIRST "SMR_SLIST_HEAD *head" 80.Ft TYPE * 81.Fn SMR_SLIST_NEXT "TYPE *elm" "FIELDNAME" 82.Fn SMR_SLIST_FOREACH "VARNAME" "SMR_SLIST_HEAD *head" "FIELDNAME" 83.Ft TYPE * 84.Fn SMR_SLIST_FIRST_LOCKED "SMR_SLIST_HEAD *head" 85.Ft TYPE * 86.Fn SMR_SLIST_NEXT_LOCKED "TYPE *elm" "FIELDNAME" 87.Ft int 88.Fn SMR_SLIST_EMPTY_LOCKED "SMR_SLIST_HEAD *head" 89.Fn SMR_SLIST_FOREACH_LOCKED "VARNAME" "SMR_SLIST_HEAD *head" "FIELDNAME" 90.Fn SMR_SLIST_FOREACH_SAFE_LOCKED "VARNAME" "SMR_LIST_HEAD *head" "FIELDNAME" "TEMP_VARNAME" 91.Ft void 92.Fn SMR_SLIST_INSERT_HEAD_LOCKED "SMR_SLIST_HEAD *head" "struct TYPE *elm" "FIELDNAME" 93.Ft void 94.Fn SMR_SLIST_INSERT_AFTER_LOCKED "struct TYPE *listelm" "struct TYPE *elm" "FIELDNAME" 95.Ft void 96.Fn SMR_SLIST_REMOVE_HEAD_LOCKED "SMR_SLIST_HEAD *head" "FIELDNAME" 97.Ft void 98.Fn SMR_SLIST_REMOVE_AFTER_LOCKED "struct TYPE *elm" "FIELDNAME" 99.Ft void 100.Fn SMR_SLIST_REMOVE_LOCKED "SMR_SLIST_HEAD *head" "struct TYPE *elm" "TYPE" "FIELDNAME" 101.Fn SMR_LIST_ENTRY "TYPE" 102.Ft void 103.Fn SMR_LIST_INIT "SMR_LIST_HEAD *head" 104.Ft TYPE * 105.Fn SMR_LIST_FIRST "SMR_LIST_HEAD *head" 106.Ft TYPE * 107.Fn SMR_LIST_NEXT "TYPE *elm" "FIELDNAME" 108.Ft TYPE * 109.Fn SMR_LIST_FIRST_LOCKED "SMR_LIST_HEAD *head" 110.Ft TYPE * 111.Fn SMR_LIST_NEXT_LOCKED "TYPE *elm" "FIELDNAME" 112.Ft int 113.Fn SMR_LIST_EMPTY_LOCKED "SMR_LIST_HEAD *head" 114.Fn SMR_LIST_FOREACH "VARNAME" "SMR_LIST_HEAD *head" "FIELDNAME" 115.Fn SMR_LIST_FOREACH_LOCKED "VARNAME" "SMR_LIST_HEAD *head" "FIELDNAME" 116.Fn SMR_LIST_FOREACH_SAFE_LOCKED "VARNAME" "SMR_LIST_HEAD *head" "FIELDNAME" "TEMP_VARNAME" 117.Ft void 118.Fn SMR_LIST_INSERT_HEAD_LOCKED "SMR_LIST_HEAD *head" "struct TYPE *elm" "FIELDNAME" 119.Ft void 120.Fn SMR_LIST_INSERT_AFTER_LOCKED "struct TYPE *listelm" "struct TYPE *elm" "FIELDNAME" 121.Ft void 122.Fn SMR_LIST_INSERT_BEFORE_LOCKED "struct TYPE *listelm" "struct TYPE *elm" "FIELDNAME" 123.Ft void 124.Fn SMR_LIST_REMOVE_LOCKED "struct TYPE *elm" "FIELDNAME" 125.Fn SMR_TAILQ_ENTRY "TYPE" 126.Ft void 127.Fn SMR_TAILQ_INIT "SMR_TAILQ_HEAD *head" 128.Ft TYPE * 129.Fn SMR_TAILQ_FIRST "SMR_TAILQ_HEAD *head" 130.Ft TYPE * 131.Fn SMR_TAILQ_NEXT "TYPE *elm" "FIELDNAME" 132.Ft TYPE * 133.Fn SMR_TAILQ_FIRST_LOCKED "SMR_TAILQ_HEAD *head" 134.Ft TYPE * 135.Fn SMR_TAILQ_NEXT_LOCKED "TYPE *elm" "FIELDNAME" 136.Ft TYPE * 137.Fn SMR_TAILQ_LAST_LOCKED "SMR_TAILQ_HEAD *head" 138.Fn SMR_TAILQ_FOREACH "VARNAME" "SMR_TAILQ_HEAD *head" "FIELDNAME" 139.Fn SMR_TAILQ_FOREACH_LOCKED "VARNAME" "SMR_TAILQ_HEAD *head" "FIELDNAME" 140.Fn SMR_TAILQ_FOREACH_SAFE_LOCKED "VARNAME" "SMR_TAILQ_HEAD *head" "FIELDNAME" "TEMP_VARNAME" 141.Ft void 142.Fn SMR_TAILQ_INSERT_HEAD_LOCKED "SMR_TAILQ_HEAD *head" "struct TYPE *elm" "FIELDNAME" 143.Ft void 144.Fn SMR_TAILQ_INSERT_TAIL_LOCKED "SMR_TAILQ_HEAD *head" "struct TYPE *elm" "FIELDNAME" 145.Ft void 146.Fn SMR_TAILQ_INSERT_AFTER_LOCKED "struct TYPE *listelm" "struct TYPE *elm" "FIELDNAME" 147.Ft void 148.Fn SMR_TAILQ_INSERT_BEFORE_LOCKED "struct TYPE *listelm" "struct TYPE *elm" "FIELDNAME" 149.Ft void 150.Fn SMR_TAILQ_REMOVE_LOCKED "struct TYPE *elm" "FIELDNAME" 151.Sh DESCRIPTION 152The SMR list macros define and operate on singly-linked lists, 153lists and tail queues 154that can be used with the safe memory reclamation mechanism. 155A data structure built with these macros can be accessed concurrently 156by multiple readers and a single writer. 157.Pp 158Readers have to access the data structure inside SMR read-side critical 159section. 160The critical section is entered using 161.Xr smr_read_enter 9 , 162and left using 163.Xr smr_read_leave 9 . 164.Pp 165Writers must ensure exclusive write access. 166That can be done using a lock, such as 167.Xr mutex 9 168or 169.Xr rwlock 9 . 170The mutual exclusion of writers does not need to apply to readers. 171.Pp 172When an element has been removed from the data structure, the element 173must not be deleted or re-inserted before all reader references to it have 174disappeared. 175The writer has to use either 176.Xr smr_barrier 9 177or 178.Xr smr_call 9 179to ensure that the element can no longer be accessed by readers. 180.Ss Singly-Linked Lists 181The 182.Fn SMR_SLIST_ENTRY 183macro declares a structure that connects the elements in the list. 184.Pp 185.Fn SMR_SLIST_INIT 186initializes the list 187.Fa head 188to an empty state. 189.Pp 190.Fn SMR_SLIST_FIRST 191and 192.Fn SMR_SLIST_FIRST_LOCKED 193return the first element on the list 194.Fa head , 195or NULL if the list is empty. 196.Pp 197.Fn SMR_SLIST_NEXT 198and 199.Fn SMR_SLIST_NEXT_LOCKED 200return the successor of the element 201.Fa elm , 202or NULL if there are no more elements on the list. 203.Pp 204.Fn SMR_SLIST_EMPTY_LOCKED 205returns true if the list 206.Fa head 207is empty. 208.Pp 209.Fn SMR_SLIST_FOREACH 210and 211.Fn SMR_SLIST_FOREACH_LOCKED 212traverse the list 213.Fa head 214in forward direction. 215.Pp 216.Fn SMR_SLIST_FOREACH_SAFE_LOCKED 217traverses the list 218.Fa head 219in forward direction. 220It is permitted to remove the element referenced by variable 221.Fa VARNAME 222from the list and defer its freeing using 223.Xr smr_call 9 . 224.Pp 225.Fn SMR_SLIST_INSERT_HEAD_LOCKED 226inserts the new element 227.Fa elm 228at the head of the list. 229.Pp 230.Fn SMR_SLIST_INSERT_AFTER_LOCKED 231inserts the new element 232.Fa elm 233after the element 234.Fa listelm . 235.Pp 236.Fn SMR_SLIST_REMOVE_HEAD_LOCKED 237removes the first element of the list 238.Fa head . 239.Pp 240.Fn SMR_SLIST_REMOVE_AFTER_LOCKED 241removes the list element immediately following 242.Fa elm . 243.Pp 244.Fn SMR_SLIST_REMOVE_LOCKED 245removes the list element 246.Fa elm 247from the list 248.Fa head . 249.Ss Linked Lists 250The 251.Fn SMR_LIST_ENTRY 252macro declares a structure that connects the elements in the list. 253.Pp 254.Fn SMR_LIST_INIT 255initializes the list 256.Fa head 257to an empty state. 258.Pp 259.Fn SMR_LIST_FIRST 260and 261.Fn SMR_LIST_FIRST_LOCKED 262return the first element on the list 263.Fa head , 264or NULL if the list is empty. 265.Pp 266.Fn SMR_LIST_NEXT 267and 268.Fn SMR_LIST_NEXT_LOCKED 269return the successor of the element 270.Fa elm , 271or NULL if there are no more elements on the list. 272.Pp 273.Fn SMR_LIST_EMPTY_LOCKED 274returns true if the list 275.Fa head 276is empty. 277.Pp 278.Fn SMR_LIST_FOREACH 279and 280.Fn SMR_LIST_FOREACH_LOCKED 281traverse the list 282.Fa head 283in forward direction. 284.Pp 285.Fn SMR_LIST_FOREACH_SAFE_LOCKED 286traverses the list 287.Fa head 288in forward direction. 289It is permitted to remove the element referenced by variable 290.Fa VARNAME 291from the list and defer its freeing using 292.Xr smr_call 9 . 293.Pp 294.Fn SMR_LIST_INSERT_HEAD_LOCKED 295inserts the new element 296.Fa elm 297at the head of the list. 298.Pp 299.Fn SMR_LIST_INSERT_AFTER_LOCKED 300inserts the new element 301.Fa elm 302after the element 303.Fa listelm . 304.Pp 305.Fn SMR_LIST_INSERT_BEFORE_LOCKED 306inserts the new element 307.Fa elm 308before the element 309.Fa listelm . 310.Pp 311.Fn SMR_LIST_REMOVE_LOCKED 312removes the element 313.Fa elm 314from the list 315.Fa head . 316.Ss Tail Queues 317The 318.Fn SMR_TAILQ_ENTRY 319macro declares a structure that connects the elements in 320the tail queue. 321.Pp 322.Fn SMR_TAILQ_INIT 323initializes the tail queue 324.Fa head 325to an empty state. 326.Pp 327.Fn SMR_TAILQ_FIRST 328and 329.Fn SMR_TAILQ_FIRST_LOCKED 330return the first element in the queue 331.Fa head , 332or NULL if the queue is empty. 333.Pp 334.Fn SMR_TAILQ_NEXT 335and 336.Fn SMR_TAILQ_NEXT_LOCKED 337return the successor of the element 338.Fa elm , 339or NULL if there are no more elements in the queue. 340.Pp 341.Fn SMR_TAILQ_EMPTY_LOCKED 342returns true if the queue 343.Fa head 344is empty. 345.Pp 346.Fn SMR_TAILQ_FOREACH 347and 348.Fn SMR_TAILQ_FOREACH_LOCKED 349traverse the queue 350.Fa head 351in forward direction. 352.Pp 353.Fn SMR_TAILQ_FOREACH_SAFE_LOCKED 354traverses the queue 355.Fa head 356in forward direction. 357It is permitted to remove the element referenced by variable 358.Fa VARNAME 359from the queue and defer its freeing using 360.Xr smr_call 9 . 361.Pp 362.Fn SMR_TAILQ_INSERT_HEAD_LOCKED 363inserts the new element 364.Fa elm 365at the head of the queue. 366.Pp 367.Fn SMR_TAILQ_INSERT_TAIL_LOCKED 368inserts the new element 369.Fa elm 370at the tail of the queue. 371.Pp 372.Fn SMR_TAILQ_INSERT_AFTER_LOCKED 373inserts the new element 374.Fa elm 375after the element 376.Fa listelm . 377.Pp 378.Fn SMR_TAILQ_INSERT_BEFORE_LOCKED 379inserts the new element 380.Fa elm 381before the element 382.Fa listelm . 383.Pp 384.Fn SMR_TAILQ_REMOVE_LOCKED 385removes the element 386.Fa elm 387from the queue 388.Fa head . 389.Sh CONTEXT 390All SMR list macros can be used during autoconf, from process context, 391or from interrupt context. 392.Pp 393.Nm SMR_SLIST_FIRST , 394.Nm SMR_SLIST_NEXT , 395.Nm SMR_SLIST_FOREACH , 396.Nm SMR_LIST_FIRST , 397.Nm SMR_LIST_NEXT , 398.Nm SMR_LIST_FOREACH , 399.Nm SMR_TAILQ_FIRST , 400.Nm SMR_TAILQ_NEXT 401and 402.Nm SMR_TAILQ_FOREACH 403can be used from SMR read-side critical section. 404.Pp 405.Nm SMR_SLIST_INIT , 406.Nm SMR_SLIST_FIRST_LOCKED , 407.Nm SMR_SLIST_NEXT_LOCKED , 408.Nm SMR_SLIST_EMPTY_LOCKED , 409.Nm SMR_SLIST_FOREACH_LOCKED , 410.Nm SMR_SLIST_FOREACH_SAFE_LOCKED , 411.Nm SMR_SLIST_INSERT_HEAD_LOCKED , 412.Nm SMR_SLIST_INSERT_AFTER_LOCKED , 413.Nm SMR_SLIST_REMOVE_HEAD_LOCKED , 414.Nm SMR_SLIST_REMOVE_AFTER_LOCKED , 415.Nm SMR_SLIST_REMOVE_LOCKED , 416.Nm SMR_LIST_INIT , 417.Nm SMR_LIST_FIRST_LOCKED , 418.Nm SMR_LIST_NEXT_LOCKED , 419.Nm SMR_LIST_EMPTY_LOCKED , 420.Nm SMR_LIST_FOREACH_LOCKED , 421.Nm SMR_LIST_FOREACH_SAFE_LOCKED , 422.Nm SMR_LIST_INSERT_HEAD_LOCKED , 423.Nm SMR_LIST_INSERT_AFTER_LOCKED , 424.Nm SMR_LIST_INSERT_BEFORE_LOCKED , 425.Nm SMR_LIST_REMOVE_LOCKED , 426.Nm SMR_TAILQ_INIT , 427.Nm SMR_TAILQ_FIRST_LOCKED , 428.Nm SMR_TAILQ_NEXT_LOCKED , 429.Nm SMR_TAILQ_EMPTY_LOCKED , 430.Nm SMR_TAILQ_FOREACH_LOCKED , 431.Nm SMR_TAILQ_FOREACH_SAFE_LOCKED , 432.Nm SMR_TAILQ_INSERT_HEAD_LOCKED , 433.Nm SMR_TAILQ_INSERT_TAIL_LOCKED , 434.Nm SMR_TAILQ_INSERT_AFTER_LOCKED , 435.Nm SMR_TAILQ_INSERT_BEFORE_LOCKED , 436and 437.Nm SMR_TAILQ_REMOVE_LOCKED 438can be used from writer context. 439.Sh SEE ALSO 440.Xr queue 3 , 441.Xr smr_call 9 , 442.Xr SMR_PTR_GET 9 443.Sh HISTORY 444The SMR list macros first appeared in 445.Ox 6.5 . 446