PSLIST(9)

🌸 NAME 🌸

Okay bestie, welcome to PSLIST(9) from the Kernel Developer's Manual — this is all about pslist, aka pserialize-safe linked lists. Buckle up, it's giving kernel data structure main character energy 💅✨

✨ 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 🦋

Okay so the pslist data structure is a linked list like list in queue(3). It's augmented with memory barriers so that any number of readers can safely run in parallel with at most one writer, without needing any interprocessor synchronization such as locks or atomics on the reader side. No cap, that's the whole point 🫶

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 initialized 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. Empty list vibe check: passed ✅

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 initialized with PSLIST_ENTRY_INITIALIZER or PSLIST_ENTRY_INIT() before it may be used.

When initialized, a list entry is unassociated. Inserting an entry associates 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.

Bestie, this is the important part 😭 Do not free or reuse that entry's memory until all extant parallel readers are done. Wait with something like pserialize_perform(9) first, then destroy, then free/reuse. Periodt.

💖 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. This is the "you own it, bestie" zone 👑

• 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. One writer at a time, fr fr ✍️

• 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). Readers, assemble 🫶

• 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);
mutex_exit(&frobnitzem.lock);

pserialize_perform(&frobnitzem.psz);

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 💜

Go peek at: queue(3), pserialize(9), psref(9) — iconic cross-references, iykyk 🌟

👑 HISTORY 👑

The pslist data structure first appeared in NetBSD 8.0.

🍓 AUTHORS 🍓

Taylor R Campbell <riastradh@NetBSD.org> 💌

---

Source/version + date sign-off from the page footer: Debian 🌸 July 7, 2016 🌸 PSLIST(9) — mwah, bestie 💋