.\"	$NetBSD: pslist.9,v 1.18 2017/07/03 21:28:48 wiz Exp $
.\"
.\" Copyright (c) 2016 The NetBSD Foundation, Inc.
.\" All rights reserved.
.\"
.\" This code is derived from software contributed to The NetBSD Foundation
.\" by Taylor R. Campbell.
.\"
.\" Redistribution and use in source and binary forms, with or without
.\" modification, are permitted provided that the following conditions
.\" are met:
.\" 1. Redistributions of source code must retain the above copyright
.\"    notice, this list of conditions and the following disclaimer.
.\" 2. Redistributions in binary form must reproduce the above copyright
.\"    notice, this list of conditions and the following disclaimer in the
.\"    documentation and/or other materials provided with the distribution.
.\"
.\" THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
.\" ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
.\" TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
.\" PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
.\" BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
.\" CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
.\" SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
.\" INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
.\" CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
.\" ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
.\" POSSIBILITY OF SUCH DAMAGE.
.\"
.Dd July 7, 2016
.Dt PSLIST 9
.Os
.\"""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""
.Sh NAME
.Nm pslist
.Nd pserialize-safe linked lists
.\"""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""
.Sh SYNOPSIS
.In sys/pslist.h
.\" Exclusive operations
.Vt struct pslist_head head No = Dv PSLIST_INITIALIZER ;
.Vt struct pslist_entry entry No = Dv PSLIST_ENTRY_INITIALIZER ;
.Ft void
.Fn PSLIST_INIT "struct pslist_head *head"
.Ft void
.Fn PSLIST_DESTROY "struct pslist_head *head"
.Ft void
.Fn PSLIST_ENTRY_INIT "TYPE *element" "PSLIST_ENTRY NAME"
.Ft void
.Fn PSLIST_ENTRY_DESTROY "TYPE *element" "PSLIST_ENTRY NAME"
.\" Writer operations
.Ft void
.Fn PSLIST_WRITER_INSERT_HEAD "struct pslist_head *head" "TYPE *new" "PSLIST_ENTRY NAME"
.Ft void
.Fn PSLIST_WRITER_INSERT_BEFORE "TYPE *element" "TYPE *new" "PSLIST_ENTRY NAME"
.Ft void
.Fn PSLIST_WRITER_INSERT_AFTER "TYPE *element" "TYPE *new" "PSLIST_ENTRY NAME"
.Ft void
.Fn PSLIST_WRITER_REMOVE "TYPE *element" "PSLIST_ENTRY NAME"
.Ft TYPE *
.Fn PSLIST_WRITER_FIRST "const struct pslist *head" "TYPE" "PSLIST_ENTRY NAME"
.Ft TYPE *
.Fn PSLIST_WRITER_NEXT "const TYPE *element" "TYPE" "PSLIST_ENTRY NAME"
.Fn PSLIST_WRITER_FOREACH "const TYPE *element" "const struct pslist_head *head" "TYPE" "PSLIST_ENTRY NAME"
.\" Reader operations
.Ft TYPE *
.Fn PSLIST_READER_FIRST "const struct pslist *head" "TYPE" "PSLIST_ENTRY NAME"
.Ft TYPE *
.Fn PSLIST_READER_NEXT "const TYPE *element" "TYPE" "PSLIST_ENTRY NAME"
.Fn PSLIST_READER_FOREACH "const TYPE *element" "const struct pslist_head *head" "TYPE" "PSLIST_ENTRY NAME"
.\"""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""
.Sh DESCRIPTION
The
.Nm
data structure is a linked list like
.Nm list
in
.Xr 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.
.\"
.Pp
The head of a linked list is represented by a
.Vt 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
.Dv PSLIST_INITIALIZER
or
.Fn PSLIST_INIT
before it may be used.
When initialized, a list head represents an empty list.
A list should be empty and destroyed with
.Fn PSLIST_DESTROY
before the
.Vt struct pslist_head
object's memory is reused.
.\"
.Pp
Each entry in a linked list is represented by a
.Vt struct pslist_entry
object, also opaque, and embedded as a member in a caller-allocated
structure called an
.Em element .
A
.Vt struct pslist_entry
object must be initialized with
.Dv PSLIST_ENTRY_INITIALIZER
or
.Fn PSLIST_ENTRY_INIT
before it may be used.
.\"
.Pp
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
.Xr pserialize_perform 9 ,
for all extant parallel readers to finish, before destroying the list
entry with
.Fn PSLIST_ENTRY_DESTROY
and then freeing or reusing its memory.
.\"""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""
.Sh EXCLUSIVE OPERATIONS
The following operations may be performed on list heads and entries
when the caller has exclusive access to them \(em no parallel writers or
readers may have access to the same objects.
.\""""""""""""""""
.Bl -tag -width abcd
.It Dv PSLIST_INITIALIZER
Constant initializer for a
.Vt struct pslist_head
object.
.\""""""""""""""""
.It Fn PSLIST_INIT head
Initialize the list headed by
.Fa head
to be empty.
.\""""""""""""""""
.It Fn PSLIST_DESTROY head
Destroy the list headed by
.Fa head ,
which must be empty.
.Pp
This has an effect only with the
.Dv DIAGNOSTIC
option, so it is not strictly necessary, but it can help to detect bugs
early; see
.Xr KASSERT 9 .
.\""""""""""""""""
.It Dv PSLIST_ENTRY_INITIALIZER
Constant initializer for an unassociated
.Vt struct pslist_entry
object.
.\""""""""""""""""
.It Fn PSLIST_ENTRY_INIT element NAME
Initialize the
.Vt struct pslist_entry
object
.Fa element Ns Li -> Ns Fa NAME .
.\""""""""""""""""
.It Fn PSLIST_ENTRY_DESTROY element NAME
Destroy the
.Vt struct pslist_entry
object
.Fa element Ns Li -> Ns Fa NAME .
Either
.Fa 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.
.El
.\"""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""
.Sh WRITER OPERATIONS
The following operations may be performed on list heads and entries
when the caller has exclusive
.Em write
access to them \(em parallel readers for the same objects are allowed,
but no parallel writers.
.\""""""""""""""""
.Bl -tag -width abcd
.It Fn PSLIST_WRITER_INSERT_HEAD head element NAME
Insert the element
.Fa element
at the beginning of the list headed by
.Fa head ,
before any existing elements in the list.
.Pp
The object
.Fa element Ns Li -> Ns Fa NAME
must be a
.Vt struct pslist_entry
object which has been initialized but not inserted.
.\""""""""""""""""
.It Fn PSLIST_WRITER_INSERT_BEFORE element new NAME
Insert the element
.Fa new
into a list before the element
.Fa element .
.Pp
The object
.Fa element Ns Li -> Ns Fa NAME
must be a
.Vt struct pslist_entry
object which has been inserted into a list.
The object
.Fa new Ns Li -> Ns Fa NAME
must be a
.Vt struct pslist_entry
.\""""""""""""""""
.It Fn PSLIST_WRITER_INSERT_AFTER element new NAME
Insert the element
.Fa new
into a list after the element
.Fa element .
.Pp
The object
.Fa element Ns Li -> Ns Fa NAME
must be a
.Vt struct pslist_entry
object which has been inserted into a list.
The object
.Fa new Ns Li -> Ns Fa NAME
must be a
.Vt struct pslist_entry
.\""""""""""""""""
.It Fn PSLIST_WRITER_REMOVE element NAME
Remove the element
.Fa element
from the list into which it has been inserted.
.Pp
The object
.Fa element Ns Li -> Ns Fa NAME
must be a
.Vt struct pslist_entry
object which has been inserted into a list.
.\""""""""""""""""
.It Fn PSLIST_WRITER_FIRST head type NAME
Return a pointer to the first element
.Fa o
of type
.Fa type
with a
.Vt struct pslist_entry
member
.Fa o Ns Li -> Ns Fa NAME ,
or
.Dv NULL
if the list is empty.
.\""""""""""""""""
.It Fn PSLIST_WRITER_NEXT element type NAME
Return a pointer to the next element
.Fa o
of type
.Fa type
with a
.Vt struct pslist_entry
member
.Fa o Ns Li -> Ns Fa NAME
after
.Fa element
in a list, or
.Dv NULL
if there are no elements after
.Fa element .
.\""""""""""""""""
.It Fn PSLIST_WRITER_FOREACH element head type NAME
Loop header for iterating over each element
.Fa element
of type
.Fa type
with
.Vt struct pslist_entry
member
.Fa element Ns Li -> Ns Fa NAME
starting at the list head
.Fa head .
.Pp
The caller must not modify the list while iterating over it.
.El
.\"""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""
.Sh READER OPERATIONS
The following operations may be performed on list heads and entries
when the caller is in a passively serialized read section \(em see
.Xr pserialize 9 .
.Bl -tag -width abcd
.\""""""""""""""""
.It Fn PSLIST_READER_FIRST head type NAME
Return a pointer to the first element
.Fa o
of type
.Fa type
with a
.Vt struct pslist_entry
member
.Fa o Ns Li -> Ns Fa NAME ,
or
.Dv NULL
if the list is empty.
.\""""""""""""""""
.It Fn PSLIST_READER_NEXT element type NAME
Return a pointer to the next element
.Fa o
of type
.Fa type
with a
.Vt struct pslist_entry
member
.Fa o Ns Li -> Ns Fa NAME
after
.Fa element
in a list, or
.Dv NULL
if there are no elements after
.Fa element .
.\""""""""""""""""
.It Fn PSLIST_READER_FOREACH element head type NAME
Loop header for iterating over each element
.Fa element
of type
.Fa type
with
.Vt struct pslist_entry
member
.Fa element Ns Li -> Ns Fa NAME
starting at the list head
.Fa head .
.El
.Sh EXAMPLES
Example frotz structure and global state:
.Bd -literal
	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;
.Ed
.Pp
Initialize the global state:
.Bd -literal
	mutex_init(&frobnitzem.lock, MUTEX_DEFAULT, IPL_NONE);
	frobnitzem.psz = pserialize_create();
	PSLIST_INIT(&frobnitzem.list);
	pool_init(&frobnitzem.pool, sizeof(struct frotz), ...);
.Ed
.Pp
Create and publish a frotz:
.Bd -literal
	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);
.Ed
.Pp
Look up a frotz and return its associated datum:
.Bd -literal
	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;
.Ed
.Pp
Remove a frotz and wait for readers to finish using it before reusing
the memory allocated for it:
.Bd -literal
	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);
.Ed
.\"""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""
.Sh CODE REFERENCES
The
.Nm
data structure is implemented by static inlines and macros in
.Pa sys/sys/pslist.h .
.\"""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""
.Sh SEE ALSO
.Xr queue 3 ,
.Xr pserialize 9 ,
.Xr psref 9
.\"""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""
.Sh HISTORY
The
.Nm
data structure first appeared in
.Nx 8.0 .
.\"""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""
.Sh AUTHORS
.An Taylor R Campbell Aq Mt riastradh@NetBSD.org