I would appreciate any donations. Wishlist or send e-mail type donations to maekawa AT daemon-systems.org.

Thank you.


PSLIST(9)                  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
     interprocessor 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
     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.

     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.

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 8.0                       July 7, 2016                       NetBSD 8.0