.\"	$NetBSD: psref.9,v 1.5 2016/04/27 08:18:40 ozaki-r 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 April 27, 2016
.Dt PSREF 9
.Os
.\"""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""
.Sh NAME
.Nm psref
.Nd passive references
.\"""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""
.Sh SYNOPSIS
.In sys/psref.h
.\"
.Ft struct psref_class *
.Fn psref_class_create "const char *name" "int ipl"
.Ft void
.Fn psref_class_destroy "struct psref_class *class"
.\"
.Ft void
.Fn psref_target_init "struct psref_target *target" "struct psref_class *class"
.Ft void
.Fn psref_target_destroy "struct psref_target *target" "struct psref_class *class"
.\"
.Ft void
.Fn psref_acquire "struct psref *ref" "const struct psref_target *target" "struct psref_class *class"
.Ft void
.Fn psref_release "struct psref *ref" "const struct psref_target *target" "struct psref_class *class"
.Ft void
.Fn psref_copy "struct psref *pto" "const struct psref *pfrom" "struct psref_class *class"
.\"
.Pp
.Fd "#ifdef DIAGNOSTIC"
.Ft bool
.Fn psref_held "const struct psref_target *target" "struct psref_class *class"
.Fd "#endif"
.\"""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""
.Sh DESCRIPTION
The
.Nm
abstraction allows CPUs to cheaply acquire and release
.Em passive references
to a resource, which guarantee the resource will not be destroyed
until the reference is released.
Acquiring and releasing passive references requires no interprocessor
synchronization, except when the resource is pending destruction.
.\"
.Pp
Passive references are an intermediate between
.Xr pserialize 9
and reference counting:
.Bl -hyphen
.It
.Xr pserialize 9
read sections require no interprocessor synchronization, but must be
of short duration, and may not sleep.
A
.Xr pserialize 9
read section blocks soft interrupts on the local CPU until it is
complete.
.It
Reference counting requires interprocessor synchronization via
.Xr atomic_ops 3
or
.Xr mutex 9 .
However, with reference counting, a reference may be held for arbitrary
durations, may be transferred between owners across CPUs and threads,
and may be held by a caller that sleeps.
.El
.\"
.Pp
Passive references share some properties of both: passive references
avoid interprocessor synchronization, and do not block soft interrupts,
but can be held by a caller that sleeps.
However, a caller holding a passive reference may not transfer it from
one LWP to another, and the caller's LWP must be bound to a single CPU
while it holds any passive references.
.Pp
Thus, passive references are useful for incrementally parallelizing
resources whose operations may sleep, such as in the network stack,
before comprehensively removing sleeps from the code paths involved.
.\"
.Pp
Resources to which callers may hold passive references are called
.Em targets ,
and must contain an embedded
.Vt struct psref_target
object, initialized with
.Fn psref_target_init .
.Pp
When a caller wants to guarantee that a resource will not be destroyed
until it is done, it must allocate storage for a
.Vt struct psref
object, find the
.Vt struct psref_target
for the resource it seeks, and use
.Fn psref_acquire
to acquire a passive reference.
When a caller is done with the resource, it must release the resource
with
.Fn psref_release .
.Pp
When a resource is about to go away, its passive reference target must
be passed to
.Fn psref_target_destroy
to wait until all extant passive references are released; then the
resource itself may be freed.
.\"
.Pp
.Vt struct psref_target
and
.Vt struct psref
objects must be allocated by the caller, but they should be treated as
opaque and should not be inspected or copied.
.\"
.Pp
Passive reference targets are grouped into
.Em classes ,
represented by an opaque
.Vt struct psref_class
object, e.g. the class of all network routes, or the class of all file
systems mount points, which may be needed at different interrupt
priority levels.
.\"""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""
.Sh FUNCTIONS
.Bl -tag -width abcd
.It Fn psref_class_create name ipl
Create a passive reference class with the given name and interrupt
priority level, and return an opaque pointer describing it.
The name must be at most eight characters long, and will be shown in
utilities such as
.Xr ps 1
for threads that are waiting to destroy passive reference targets.
On failure, return
.Dv NULL
instead.
.\""""""""""""""""
.It Fn psref_class_destroy class
Destroy a passive reference class created with
.Fn psref_class_create .
There must be no more passive references in this class.
.\""""""""""""""""
.It Fn psref_target_init target class
Initialize a passive reference target in a
.Vt struct psref_target
object allocated by the caller in the given class.
.Pp
The caller must issue a
.Xr membar_producer 3
after calling
.Fn psref_target_init
and before publishing a pointer to the target so that other CPUs can
see it, e.g. by inserting it into a
.Xr pslist 9 .
.\""""""""""""""""
.It Fn psref_target_destroy target class
Wait for all extant passive references to
.Fa target
on all CPUs to be released, and then destroy it.
The passive reference target
.Fa target
must have been initialized with
.Fn psref_target_init
in the same
.Fa class .
May sleep.
.Pp
The caller must guarantee that no new references to
.Fa target
will be acquired once it calls
.Fn psref_target_destroy ,
e.g. by removing the target from a
.Xr pslist 9
and calling
.Xr pserialize_perform 9
to wait for
.Xr pserialize 9
readers to complete.
.Pp
No further use of the target is allowed unless it is reinitialized with
.Fn psref_target_init .
Multiple concurrent calls to
.Fn psref_target_destroy
are not allowed.
.\""""""""""""""""
.It Fn psref_acquire ref target class
Acquire a passive reference to
.Fa target ,
storing per-CPU bookkeeping in
.Fa ref .
The class of
.Fa target
must be
.Fa class .
.Pp
The caller must ensure by some other mechanism than passive references
that the target will not be destroyed before the call to
.Fn psref_acquire ;
typically this will be via a
.Xr pserialize 9
read section.
.Pp
The caller's LWP must be bound to a CPU.
.\""""""""""""""""
.It Fn psref_release ref target class
Release the passive reference
.Fa ref ,
which must have been acquired to point at
.Fa target
in the class
.Fa class ,
waking a thread calling
.Fn psref_target_destroy
if any.
.Pp
Further use of the resource represented by
.Fa target
is not allowed, unless it is re-acquired in the same way that it was
originally acquired.
.\""""""""""""""""
.It Fn psref_copy pto pfrom class
Copy the passive reference
.Fa pfrom
to
.Fa pto ,
which must be to a target in
.Fa class .
The resource represented by the target of the passive references will
not be destroyed before both references are released.
.\""""""""""""""""
.It Fn psref_held target class
Return true if the current CPU holds a passive reference to
.Fa target
in the passive reference class
.Fa class ,
or false if not.
.Pp
This does not answer about other CPUs \(em it does not tell you whether
.Em any
CPU holds a passive reference to
.Fa target .
.Pp
This may be used only in assertions, e.g. with
.Xr KASSERT 9 ,
not for making run-time decisions.
This should be used only for positive assertions, as in
.Li KASSERT(psref_held( Ns Fa target Ns Li , Fa class Ns Li )) ,
not for negative assertions, as in
.Li KASSERT(!psref_held( Ns Fa target Ns Li , Fa class Ns Li )) ,
unless you are sure you can prove that no caller holds a reference
either.
.El
.\"""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""
.Sh EXAMPLES
.Bd -literal
struct frotz {
	int			f_key;
	...
	struct pslist_entry	f_entry;
	struct psref_target	f_target;
};

static struct {
	kmutex_t		lock;
	struct pslist_head	list;
} frobbotzim __cacheline_aligned;

static pserialize_t		frobbotzim_psz __read_mostly;
static struct psref_class	*frobbotzim_prc __read_mostly;

void
publish_as_frotz(uint64_t key, ...)
{
	struct frotz *f;

	f = kmem_alloc(sizeof(*f), KM_SLEEP);
	f->f_key = key;
	f->f_... = ...;
	PSLIST_ENTRY_INIT(f, f_entry);
	psref_target_init(&f->f_target, frobbotzim_prc);

	mutex_enter(&frobbotzim.lock);
	PSLIST_WRITER_INSERT_HEAD(&frobbotzim.list, f, f_entry);
	mutex_exit(&frobbotzim.lock);
}

int
use_frotz(int key, int op)
{
	struct frotz *f;
	struct psref ref;

	/* Acquire a passive reference.  */
	if ((f = lookup_frotz(key, &ref)) == NULL)
		return ENOENT;

	/* Do something that may sleep.  */
	do_stuff_with_frotz(f, op);

	/* Release passive reference, possibly waking destroy_frotz.  */
	psref_release(&ref, &f->f_psref, frobbotzim_prc);

	return 0;
}

struct frotz *
lookup_frotz(int key, struct psref *ref)
{
	struct frotz *f;
	int s;

	/* Look up a frotz in a pserialized list.  */
	s = pserialize_read_enter();
	PSLIST_READER_FOREACH(f, &frobbotzim.list, struct frotz, f_next) {
		/* f is stable until pserialize_read_exit.  */
		if (f->f_key == key) {
			/* Acquire a passive reference.  */
			psref_acquire(ref, &f->f_target, frobbotzim_prc);
			/* f is now stable until psref_release.  */
			break;
		}
	}
	pserialize_read_exit(s);

	return f;
}

void
destroy_frotz(int key)
{
	struct frotz *f;

	/* Look up and delete a frotz.  */
	mutex_enter(&frobbotzim.lock);
	PSLIST_WRITER_FOREACH(f, &frobbotzim.list, struct frotz, f_entry) {
		if (f->f_key == key) {
			/*
			 * Unlink the frotz from the list to stop new
			 * pserialize read sections from seeing it.
			 */
			PSLIST_WRITER_REMOVE(f, f_entry);

			/*
			 * Wait until extant pserialize read sections
			 * have completed.
			 */
			pserialize_perform(frobbotzim_psz);
			break;
		}
	}
	mutex_exit(&frobbotzim.lock);

	if (f != NULL) {
		/* Wait for all readers to drain before freeing.  */
		psref_target_destroy(&f->f_target, frobbotzim_prc);
		PSLIST_ENTRY_DESTROY(f, f_entry);
		kmem_free(f, sizeof(*f));
	}
}
.Ed
.\"""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""
.Sh CODE REFERENCES
The
.Nm
abstraction is implemented in
.Pa sys/kern/subr_psref.c .
.\"""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""
.Sh SEE ALSO
.Xr pserialize 9 ,
.Xr pslist 9
.\"""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""
.Sh HISTORY
The
.Nm
data structure first appeared in
.Nx 8.0 .
.\"""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""
.Sh AUTHORS
.An Taylor R Campbell Aq Mt riastradh@NetBSD.org