pslist(9)
- NetBSD Manual Pages
PSLIST(9) NetBSD Kernel Developer's Manual PSLIST(9)
NAME
pslist -- pserialize-safe linked lists
SYNOPSIS
#include <sys/pslist.h>
struct pslist_head head = PSLIST_INITIALIZER;
struct pslist_entry entry = PSLIST_ENTRY_INITIALIZER;
void
PSLIST_INIT(struct pslist_head *head);
void
PSLIST_DESTROY(struct pslist_head *head);
void
PSLIST_ENTRY_INIT(TYPE *element, PSLIST_ENTRY NAME);
void
PSLIST_ENTRY_DESTROY(TYPE *element, PSLIST_ENTRY NAME);
void
PSLIST_WRITER_INSERT_HEAD(struct pslist_head *head, TYPE *new,
PSLIST_ENTRY NAME);
void
PSLIST_WRITER_INSERT_BEFORE(TYPE *element, TYPE *new, PSLIST_ENTRY NAME);
void
PSLIST_WRITER_INSERT_AFTER(TYPE *element, TYPE *new, PSLIST_ENTRY NAME);
void
PSLIST_WRITER_REMOVE(TYPE *element, PSLIST_ENTRY NAME);
TYPE *
PSLIST_WRITER_FIRST(const struct pslist *head, TYPE, PSLIST_ENTRY NAME);
TYPE *
PSLIST_WRITER_NEXT(const TYPE *element, TYPE, PSLIST_ENTRY NAME);
PSLIST_WRITER_FOREACH(const TYPE *element,
const struct pslist_head *head, TYPE, PSLIST_ENTRY NAME);
TYPE *
PSLIST_READER_FIRST(const struct pslist *head, TYPE, PSLIST_ENTRY NAME);
TYPE *
PSLIST_READER_NEXT(const TYPE *element, TYPE, PSLIST_ENTRY NAME);
PSLIST_READER_FOREACH(const TYPE *element,
const struct pslist_head *head, TYPE, PSLIST_ENTRY NAME);
DESCRIPTION
The pslist data structure is a linked list like list in queue(3). It is
augmented with memory barriers so that any number of readers can safely
run in parallel with at most one writer, without needing any interproces-
sor synchronization such as locks or atomics on the reader side.
The head of a linked list is represented by a struct pslist_head object
allocated by the caller, e.g. by embedding it in another struct, which
should be otherwise treated as opaque. A linked list head must be ini-
tialized with PSLIST_INITIALIZER or PSLIST_INIT() before it may be used.
When initialized, a list head represents an empty list. A list should be
empty and destroyed with PSLIST_DESTROY() before the struct pslist_head
object's memory is reused.
Each entry in a linked list is represented by a struct pslist_entry
object, also opaque, and embedded as a member in a caller-allocated
structure called an element. A struct pslist_entry object must be ini-
tialized with PSLIST_ENTRY_INITIALIZER or PSLIST_ENTRY_INIT() before it
may be used.
When initialized, a list entry is unassociated. Inserting an entry asso-
ciates it with a particular list. Removing it partially disassociates it
from that list and prevents new readers from finding it in the list, but
allows extant parallel readers to continue reading the next entry. The
caller must then wait, e.g. with pserialize_perform(9), for all extant
parallel readers to finish, before destroying the list entry with
PSLIST_ENTRY_DESTROY() and then freeing or reusing its memory.
EXCLUSIVE OPERATIONS
The following operations may be performed on list heads and entries when
the caller has exclusive access to them -- no parallel writers or readers
may have access to the same objects.
PSLIST_INITIALIZER
Constant initializer for a struct pslist_head object.
PSLIST_INIT(head)
Initialize the list headed by head to be empty.
PSLIST_DESTROY(head)
Destroy the list headed by head, which must be empty.
This has an effect only with the DIAGNOSTIC option, so it is not
strictly necessary, but it can help to detect bugs early; see
KASSERT(9).
PSLIST_ENTRY_INITIALIZER
Constant initializer for an unassociated struct pslist_entry
object.
PSLIST_ENTRY_INIT(element, NAME)
Initialize the struct pslist_entry object element->NAME.
PSLIST_ENTRY_DESTROY(element, NAME)
Destroy the struct pslist_entry object element->NAME. Either
element must never have been inserted into a list, or it must have
been inserted and removed, and the caller must have waited for all
parallel readers to finish reading it first.
WRITER OPERATIONS
The following operations may be performed on list heads and entries when
the caller has exclusive write access to them -- parallel readers for the
same objects are allowed, but no parallel writers.
PSLIST_WRITER_INSERT_HEAD(head, element, NAME)
Insert the element element at the beginning of the list headed by
head, before any existing elements in the list.
The object element->NAME must be a struct pslist_entry object which
has been initialized but not inserted.
PSLIST_WRITER_INSERT_BEFORE(element, new, NAME)
Insert the element new into a list before the element element.
The object element->NAME must be a struct pslist_entry object which
has been inserted into a list. The object new->NAME must be a
struct pslist_entry
PSLIST_WRITER_INSERT_AFTER(element, new, NAME)
Insert the element new into a list after the element element.
The object element->NAME must be a struct pslist_entry object which
has been inserted into a list. The object new->NAME must be a
struct pslist_entry
PSLIST_WRITER_REMOVE(element, NAME)
Remove the element element from the list into which it has been
inserted.
The object element->NAME must be a struct pslist_entry object which
has been inserted into a list.
PSLIST_WRITER_FIRST(head, type, NAME)
Return a pointer to the first element o of type type with a struct
pslist_entry member o->NAME, or NULL if the list is empty.
PSLIST_WRITER_NEXT(element, type, NAME)
Return a pointer to the next element o of type type with a struct
pslist_entry member o->NAME after element in a list, or NULL if
there are no elements after element.
PSLIST_WRITER_FOREACH(element, head, type, NAME)
Loop header for iterating over each element element of type type
with struct pslist_entry member element->NAME starting at the list
head head.
The caller must not modify the list while iterating over it.
READER OPERATIONS
The following operations may be performed on list heads and entries when
the caller is in a passively serialized read section -- see
pserialize(9).
PSLIST_READER_FIRST(head, type, NAME)
Return a pointer to the first element o of type type with a struct
pslist_entry member o->NAME, or NULL if the list is empty.
PSLIST_READER_NEXT(element, type, NAME)
Return a pointer to the next element o of type type with a struct
pslist_entry member o->NAME after element in a list, or NULL if
there are no elements after element.
PSLIST_READER_FOREACH(element, head, type, NAME)
Loop header for iterating over each element element of type type
with struct pslist_entry member element->NAME starting at the list
head head.
EXAMPLES
Example frotz structure and global state:
struct frotz {
uint64_t f_key;
uint64_t f_datum;
struct pslist_entry f_entry;
};
static struct {
kmutex_t lock;
pserialize_t psz;
struct pslist_head list;
struct pool pool;
} frobnitzem __cacheline_aligned;
Initialize the global state:
mutex_init(&frobnitzem.lock, MUTEX_DEFAULT, IPL_NONE);
frobnitzem.psz = pserialize_create();
PSLIST_INIT(&frobnitzem.list);
pool_init(&frobnitzem.pool, sizeof(struct frotz), ...);
Create and publish a frotz:
uint64_t key = ...;
uint64_t datum = ...;
struct frotz *f = pool_get(&frobnitzem.pool, PR_WAITOK);
/* Initialize f. */
f->f_key = key;
f->f_datum = datum;
PSLIST_ENTRY_INIT(f, f_entry);
/* Publish it. */
mutex_enter(&frobnitzem.lock);
PSLIST_WRITER_INSERT_HEAD(&frobnitzem.list, f, f_entry);
mutex_exit(&frobnitzem.lock);
Look up a frotz and return its associated datum:
uint64_t key = ...;
struct frotz *f;
int error = ENOENT;
int s;
s = pserialize_read_enter();
PSLIST_READER_FOREACH(f, &frobnitzem.list, struct frotz, f_entry) {
if (f->f_key == key) {
*datump = f->f_datum;
error = 0;
break;
}
}
pserialize_read_exit(s);
return error;
Remove a frotz and wait for readers to finish using it before reusing the
memory allocated for it:
struct frotz *f = ...;
mutex_enter(&frobnitzem.lock);
PSLIST_WRITER_REMOVE(f, f_entry);
pserialize_perform(&frobnitzem.psz);
mutex_exit(&frobnitzem.lock);
PSLIST_ENTRY_DESTROY(f, f_entry);
pool_put(&frobnitzem.pool, f);
CODE REFERENCES
The pslist data structure is implemented by static inlines and macros in
sys/sys/pslist.h.
SEE ALSO
queue(3), pserialize(9), psref(9)
HISTORY
The pslist data structure first appeared in NetBSD 8.0.
AUTHORS
Taylor R Campbell <riastradh@NetBSD.org>
NetBSD 9.1 July 7, 2016 NetBSD 9.1
Powered by man-cgi (2024-03-20).
Maintained for NetBSD
by Kimmo Suominen.
Based on man-cgi by Panagiotis Christias.