Module Name: src
Committed By: riastradh
Date: Sat Apr 9 06:21:17 UTC 2016
Modified Files:
src/distrib/sets/lists/comp: mi
src/share/man/man9: Makefile pslist.9
src/sys/kern: files.kern
Added Files:
src/share/man/man9: psref.9
src/sys/kern: subr_psref.c
src/sys/sys: psref.h
Log Message:
Add passive references, intermediate between pserialize and refcount.
Discussed on tech-kern:
https://mail-index.netbsd.org/tech-kern/2016/01/24/msg020069.html
API is still experimental and likely to change. (Obvious changes:
either remove extra arguments everywhere, or shrink psref_target to a
single bit, at the expense of possibly valuable diagnostic checks.)
Should do some real testing before we use this in anger!
To generate a diff of this commit:
cvs rdiff -u -r1.2027 -r1.2028 src/distrib/sets/lists/comp/mi
cvs rdiff -u -r1.394 -r1.395 src/share/man/man9/Makefile
cvs rdiff -u -r1.2 -r1.3 src/share/man/man9/pslist.9
cvs rdiff -u -r0 -r1.1 src/share/man/man9/psref.9
cvs rdiff -u -r1.10 -r1.11 src/sys/kern/files.kern
cvs rdiff -u -r0 -r1.1 src/sys/kern/subr_psref.c
cvs rdiff -u -r0 -r1.1 src/sys/sys/psref.h
Please note that diffs are not public domain; they are subject to the
copyright notices on the relevant files.
Modified files:
Index: src/distrib/sets/lists/comp/mi
diff -u src/distrib/sets/lists/comp/mi:1.2027 src/distrib/sets/lists/comp/mi:1.2028
--- src/distrib/sets/lists/comp/mi:1.2027 Sat Apr 9 04:39:46 2016
+++ src/distrib/sets/lists/comp/mi Sat Apr 9 06:21:16 2016
@@ -1,4 +1,4 @@
-# $NetBSD: mi,v 1.2027 2016/04/09 04:39:46 riastradh Exp $
+# $NetBSD: mi,v 1.2028 2016/04/09 06:21:16 riastradh Exp $
#
# Note: don't delete entries from here - mark them as "obsolete" instead.
./etc/mtree/set.comp comp-sys-root
@@ -10688,6 +10688,15 @@
./usr/share/man/cat9/pserialize_read_exit.0 comp-sys-catman .cat
./usr/share/man/cat9/psignal.0 comp-sys-catman .cat
./usr/share/man/cat9/pslist.0 comp-sys-catman .cat
+./usr/share/man/cat9/psref.0 comp-sys-catman .cat
+./usr/share/man/cat9/psref_acquire.0 comp-sys-catman .cat
+./usr/share/man/cat9/psref_class_create.0 comp-sys-catman .cat
+./usr/share/man/cat9/psref_class_destroy.0 comp-sys-catman .cat
+./usr/share/man/cat9/psref_copy.0 comp-sys-catman .cat
+./usr/share/man/cat9/psref_held.0 comp-sys-catman .cat
+./usr/share/man/cat9/psref_release.0 comp-sys-catman .cat
+./usr/share/man/cat9/psref_target_destroy.0 comp-sys-catman .cat
+./usr/share/man/cat9/psref_target_init.0 comp-sys-catman .cat
./usr/share/man/cat9/ptoa.0 comp-sys-catman .cat
./usr/share/man/cat9/putiobuf.0 comp-sys-catman .cat
./usr/share/man/cat9/putter.0 comp-sys-catman .cat
@@ -17728,6 +17737,15 @@
./usr/share/man/html9/pserialize_read_exit.html comp-sys-htmlman html
./usr/share/man/html9/psignal.html comp-sys-htmlman html
./usr/share/man/html9/pslist.html comp-sys-htmlman html
+./usr/share/man/html9/psref.html comp-sys-catman html
+./usr/share/man/html9/psref_acquire.html comp-sys-catman html
+./usr/share/man/html9/psref_class_create.html comp-sys-catman html
+./usr/share/man/html9/psref_class_destroy.html comp-sys-catman html
+./usr/share/man/html9/psref_copy.html comp-sys-catman html
+./usr/share/man/html9/psref_held.html comp-sys-catman html
+./usr/share/man/html9/psref_release.html comp-sys-catman html
+./usr/share/man/html9/psref_target_destroy.html comp-sys-catman html
+./usr/share/man/html9/psref_target_init.html comp-sys-catman html
./usr/share/man/html9/ptoa.html comp-sys-htmlman html
./usr/share/man/html9/putiobuf.html comp-sys-htmlman html
./usr/share/man/html9/putter.html comp-sys-htmlman html
@@ -24950,6 +24968,15 @@
./usr/share/man/man9/pserialize_read_exit.9 comp-sys-man .man
./usr/share/man/man9/psignal.9 comp-sys-man .man
./usr/share/man/man9/pslist.9 comp-sys-man .man
+./usr/share/man/man9/psref.9 comp-sys-man .man
+./usr/share/man/man9/psref_acquire.9 comp-sys-man .man
+./usr/share/man/man9/psref_class_create.9 comp-sys-man .man
+./usr/share/man/man9/psref_class_destroy.9 comp-sys-man .man
+./usr/share/man/man9/psref_copy.9 comp-sys-man .man
+./usr/share/man/man9/psref_held.9 comp-sys-man .man
+./usr/share/man/man9/psref_release.9 comp-sys-man .man
+./usr/share/man/man9/psref_target_destroy.9 comp-sys-man .man
+./usr/share/man/man9/psref_target_init.9 comp-sys-man .man
./usr/share/man/man9/ptoa.9 comp-sys-man .man
./usr/share/man/man9/putiobuf.9 comp-sys-man .man
./usr/share/man/man9/putter.9 comp-sys-man .man
Index: src/share/man/man9/Makefile
diff -u src/share/man/man9/Makefile:1.394 src/share/man/man9/Makefile:1.395
--- src/share/man/man9/Makefile:1.394 Sat Apr 9 04:39:46 2016
+++ src/share/man/man9/Makefile Sat Apr 9 06:21:16 2016
@@ -1,4 +1,4 @@
-# $NetBSD: Makefile,v 1.394 2016/04/09 04:39:46 riastradh Exp $
+# $NetBSD: Makefile,v 1.395 2016/04/09 06:21:16 riastradh Exp $
# Makefile for section 9 (kernel function and variable) manual pages.
@@ -43,7 +43,7 @@ MAN= accept_filter.9 accf_data.9 accf_ht
pci_msi.9 pckbport.9 pcmcia.9 pcq.9 pcu.9 \
percpu.9 pfil.9 physio.9 pmap.9 pmatch.9 pmc.9 pmf.9 pool.9 \
pool_cache.9 powerhook_establish.9 ppi.9 ppsratecheck.9 preempt.9 \
- proc_find.9 pserialize.9 pslist.9 putter.9 \
+ proc_find.9 pserialize.9 pslist.9 psref.9 putter.9 \
radio.9 ras.9 rasops.9 ratecheck.9 resettodr.9 rnd.9 rndsink.9 \
roundup.9 rssadapt.9 rt_timer.9 rwlock.9 RUN_ONCE.9 STACK.9 \
scanc.9 \
@@ -721,6 +721,14 @@ MLINKS+=pslist.9 PSLIST_DESTROY.9 \
pslist.9 PSLIST_WRITER_INSERT_HEAD.9 \
pslist.9 PSLIST_WRITER_NEXT.9 \
pslist.9 PSLIST_WRITER_REMOVE.9
+MLINKS+=psref.9 psref_acquire.9 \
+ psref.9 psref_class_create.9 \
+ psref.9 psref_class_destroy.9 \
+ psref.9 psref_copy.9 \
+ psref.9 psref_held.9 \
+ psref.9 psref_release.9 \
+ psref.9 psref_target_destroy.9 \
+ psref.9 psref_target_init.9
MLINKS+=ras.9 ras_lookup.9 \
ras.9 ras_fork.9 \
ras.9 ras_purgeall.9
Index: src/share/man/man9/pslist.9
diff -u src/share/man/man9/pslist.9:1.2 src/share/man/man9/pslist.9:1.3
--- src/share/man/man9/pslist.9:1.2 Sat Apr 9 05:16:23 2016
+++ src/share/man/man9/pslist.9 Sat Apr 9 06:21:16 2016
@@ -1,4 +1,4 @@
-.\" $NetBSD: pslist.9,v 1.2 2016/04/09 05:16:23 riastradh Exp $
+.\" $NetBSD: pslist.9,v 1.3 2016/04/09 06:21:16 riastradh Exp $
.\"
.\" Copyright (c) 2016 The NetBSD Foundation, Inc.
.\" All rights reserved.
@@ -420,7 +420,8 @@ data structure is implemented by static
.\"""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""
.Sh SEE ALSO
.Xr queue 3 ,
-.Xr pserialize 9
+.Xr pserialize 9 ,
+.Xr psref 9
.\"""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""
.Sh HISTORY
The
Index: src/sys/kern/files.kern
diff -u src/sys/kern/files.kern:1.10 src/sys/kern/files.kern:1.11
--- src/sys/kern/files.kern:1.10 Thu Dec 3 02:51:00 2015
+++ src/sys/kern/files.kern Sat Apr 9 06:21:16 2016
@@ -1,4 +1,4 @@
-# $NetBSD: files.kern,v 1.10 2015/12/03 02:51:00 pgoyette Exp $
+# $NetBSD: files.kern,v 1.11 2016/04/09 06:21:16 riastradh Exp $
#
# kernel sources
@@ -125,6 +125,7 @@ file kern/subr_pool.c kern
file kern/subr_prf.c kern
file kern/subr_prof.c kern
file kern/subr_pserialize.c kern
+file kern/subr_psref.c kern
file kern/subr_specificdata.c kern
file kern/subr_tftproot.c tftproot
file kern/subr_time.c kern
Added files:
Index: src/share/man/man9/psref.9
diff -u /dev/null src/share/man/man9/psref.9:1.1
--- /dev/null Sat Apr 9 06:21:17 2016
+++ src/share/man/man9/psref.9 Sat Apr 9 06:21:16 2016
@@ -0,0 +1,405 @@
+.\" $NetBSD: psref.9,v 1.1 2016/04/09 06:21:16 riastradh 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 8, 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 references to a resource,
+called
+.Em passive references ,
+guaranteeing it will not be destroyed until all CPUs release their
+references to it, without using interprocessor synchronization on the
+reader side.
+.\"
+.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 9
+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
+require no interprocessor synchronization to acquire or release, 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 -- 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 [email protected]
Index: src/sys/kern/subr_psref.c
diff -u /dev/null src/sys/kern/subr_psref.c:1.1
--- /dev/null Sat Apr 9 06:21:17 2016
+++ src/sys/kern/subr_psref.c Sat Apr 9 06:21:16 2016
@@ -0,0 +1,482 @@
+/* $NetBSD: subr_psref.c,v 1.1 2016/04/09 06:21:16 riastradh 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.
+ */
+
+/*
+ * Passive references
+ *
+ * Passive references are references to objects that guarantee the
+ * object will not be destroyed until the reference is released.
+ *
+ * Passive references require no interprocessor synchronization to
+ * acquire or release. However, destroying the target of passive
+ * references requires expensive interprocessor synchronization --
+ * xcalls to determine on which CPUs the object is still in use.
+ *
+ * Passive references may be held only on a single CPU and by a
+ * single LWP. They require the caller to allocate a little stack
+ * space, a struct psref object. Sleeping while a passive
+ * reference is held is allowed, provided that the owner's LWP is
+ * bound to a CPU -- e.g., the owner is a softint or a bound
+ * kthread. However, sleeping should be kept to a short duration,
+ * e.g. sleeping on an adaptive lock.
+ *
+ * Passive references serve as an intermediate stage between
+ * reference counting and passive serialization (pserialize(9)):
+ *
+ * - If you need references to transfer from CPU to CPU or LWP to
+ * LWP, or if you need long-term references, you must use
+ * reference counting, e.g. with atomic operations or locks,
+ * which incurs interprocessor synchronization for every use --
+ * cheaper than an xcall, but not scalable.
+ *
+ * - If all users *guarantee* that they will not sleep, then it is
+ * not necessary to use passive references: you may as well just
+ * use the even cheaper pserialize(9), because you have
+ * satisfied the requirements of a pserialize read section.
+ */
+
+#include <sys/cdefs.h>
+__KERNEL_RCSID(0, "$NetBSD: subr_psref.c,v 1.1 2016/04/09 06:21:16 riastradh Exp $");
+
+#include <sys/types.h>
+#include <sys/condvar.h>
+#include <sys/cpu.h>
+#include <sys/intr.h>
+#include <sys/kmem.h>
+#include <sys/lwp.h>
+#include <sys/mutex.h>
+#include <sys/percpu.h>
+#include <sys/psref.h>
+#include <sys/queue.h>
+#include <sys/xcall.h>
+
+LIST_HEAD(psref_head, psref);
+
+/*
+ * struct psref_class
+ *
+ * Private global state for a class of passive reference targets.
+ * Opaque to callers.
+ */
+struct psref_class {
+ kmutex_t prc_lock;
+ kcondvar_t prc_cv;
+ struct percpu *prc_percpu; /* struct psref_cpu */
+ ipl_cookie_t prc_iplcookie;
+};
+
+/*
+ * struct psref_cpu
+ *
+ * Private per-CPU state for a class of passive reference targets.
+ * Not exposed by the API.
+ */
+struct psref_cpu {
+ struct psref_head pcpu_head;
+};
+
+/*
+ * psref_class_create(name, ipl)
+ *
+ * Create a new passive reference class, with the given wchan name
+ * and ipl.
+ */
+struct psref_class *
+psref_class_create(const char *name, int ipl)
+{
+ struct psref_class *class;
+
+ ASSERT_SLEEPABLE();
+
+ class = kmem_alloc(sizeof(*class), KM_SLEEP);
+ if (class == NULL)
+ goto fail0;
+
+ class->prc_percpu = percpu_alloc(sizeof(struct psref_cpu));
+ if (class->prc_percpu == NULL)
+ goto fail1;
+
+ mutex_init(&class->prc_lock, MUTEX_DEFAULT, ipl);
+ cv_init(&class->prc_cv, name);
+ class->prc_iplcookie = makeiplcookie(ipl);
+
+ return class;
+
+fail1: kmem_free(class, sizeof(*class));
+fail0: return NULL;
+}
+
+#ifdef DIAGNOSTIC
+static void
+psref_cpu_drained_p(void *p, void *cookie, struct cpu_info *ci __unused)
+{
+ const struct psref_cpu *pcpu = p;
+ bool *retp = cookie;
+
+ if (!LIST_EMPTY(&pcpu->pcpu_head))
+ *retp = false;
+}
+
+static bool
+psref_class_drained_p(const struct psref_class *prc)
+{
+ bool ret = true;
+
+ percpu_foreach(prc->prc_percpu, &psref_cpu_drained_p, &ret);
+
+ return ret;
+}
+#endif /* DIAGNOSTIC */
+
+/*
+ * psref_class_destroy(class)
+ *
+ * Destroy a passive reference class and free memory associated
+ * with it. All targets in this class must have been drained and
+ * destroyed already.
+ */
+void
+psref_class_destroy(struct psref_class *class)
+{
+
+ KASSERT(psref_class_drained_p(class));
+
+ cv_destroy(&class->prc_cv);
+ mutex_destroy(&class->prc_lock);
+ percpu_free(class->prc_percpu, sizeof(struct psref_cpu));
+ kmem_free(class, sizeof(*class));
+}
+
+/*
+ * psref_target_init(target, class)
+ *
+ * Initialize a passive reference target in the specified class.
+ * The caller is responsible for issuing a membar_producer after
+ * psref_target_init and before exposing a pointer to the target
+ * to other CPUs.
+ */
+void
+psref_target_init(struct psref_target *target,
+ struct psref_class *class)
+{
+
+ target->prt_class = class;
+ target->prt_draining = false;
+}
+
+/*
+ * psref_acquire(psref, target, class)
+ *
+ * Acquire a passive reference to the specified target, which must
+ * be in the specified class.
+ *
+ * The caller must guarantee that the target will not be destroyed
+ * before psref_acquire returns.
+ *
+ * The caller must additionally guarantee that it will not switch
+ * CPUs before releasing the passive reference, either by
+ * disabling kpreemption and avoiding sleeps, or by being in a
+ * softint or in an LWP bound to a CPU.
+ */
+void
+psref_acquire(struct psref *psref, const struct psref_target *target,
+ struct psref_class *class)
+{
+ struct psref_cpu *pcpu;
+ int s;
+
+ KASSERTMSG((kpreempt_disabled() || cpu_softintr_p() ||
+ ISSET(curlwp->l_pflag, LP_BOUND)),
+ "passive references are CPU-local,"
+ " but preemption is enabled and the caller is not"
+ " in a softint or CPU-bound LWP");
+ KASSERTMSG((target->prt_class == class),
+ "mismatched psref target class: %p (ref) != %p (expected)",
+ target->prt_class, class);
+ KASSERTMSG(!target->prt_draining, "psref target already destroyed: %p",
+ target);
+
+ /* Block interrupts and acquire the current CPU's reference list. */
+ s = splraiseipl(class->prc_iplcookie);
+ pcpu = percpu_getref(class->prc_percpu);
+
+ /* Record our reference. */
+ LIST_INSERT_HEAD(&pcpu->pcpu_head, psref, psref_entry);
+ psref->psref_target = target;
+ psref->psref_lwp = curlwp;
+ psref->psref_cpu = curcpu();
+
+ /* Release the CPU list and restore interrupts. */
+ percpu_putref(class->prc_percpu);
+ splx(s);
+}
+
+/*
+ * psref_release(psref, target, class)
+ *
+ * Release a passive reference to the specified target, which must
+ * be in the specified class.
+ *
+ * The caller must not have switched CPUs or LWPs since acquiring
+ * the passive reference.
+ */
+void
+psref_release(struct psref *psref, const struct psref_target *target,
+ struct psref_class *class)
+{
+ int s;
+
+ KASSERTMSG((kpreempt_disabled() || cpu_softintr_p() ||
+ ISSET(curlwp->l_pflag, LP_BOUND)),
+ "passive references are CPU-local,"
+ " but preemption is enabled and the caller is not"
+ " in a softint or CPU-bound LWP");
+ KASSERTMSG((target->prt_class == class),
+ "mismatched psref target class: %p (ref) != %p (expected)",
+ target->prt_class, class);
+
+ /* Make sure the psref looks sensible. */
+ KASSERTMSG((psref->psref_target == target),
+ "passive reference target mismatch: %p (ref) != %p (expected)",
+ psref->psref_target, target);
+ KASSERTMSG((psref->psref_lwp == curlwp),
+ "passive reference transferred from lwp %p to lwp %p",
+ psref->psref_lwp, curlwp);
+ KASSERTMSG((psref->psref_cpu == curcpu()),
+ "passive reference transferred from CPU %u to CPU %u",
+ cpu_index(psref->psref_cpu), cpu_index(curcpu()));
+
+ /*
+ * Block interrupts and remove the psref from the current CPU's
+ * list. No need to percpu_getref or get the head of the list,
+ * and the caller guarantees that we are bound to a CPU anyway
+ * (as does blocking interrupts).
+ */
+ s = splraiseipl(class->prc_iplcookie);
+ LIST_REMOVE(psref, psref_entry);
+ splx(s);
+
+ /* If someone is waiting for users to drain, notify 'em. */
+ if (__predict_false(target->prt_draining))
+ cv_broadcast(&class->prc_cv);
+}
+
+/*
+ * psref_copy(pto, pfrom, class)
+ *
+ * Copy a passive reference from pfrom, which must be in the
+ * specified class, to pto. Both pfrom and pto must later be
+ * released with psref_release.
+ *
+ * The caller must not have switched CPUs or LWPs since acquiring
+ * pfrom, and must not switch CPUs or LWPs before releasing both
+ * pfrom and pto.
+ */
+void
+psref_copy(struct psref *pto, const struct psref *pfrom,
+ struct psref_class *class)
+{
+ struct psref_cpu *pcpu;
+ int s;
+
+ KASSERTMSG((kpreempt_disabled() || cpu_softintr_p() ||
+ ISSET(curlwp->l_pflag, LP_BOUND)),
+ "passive references are CPU-local,"
+ " but preemption is enabled and the caller is not"
+ " in a softint or CPU-bound LWP");
+ KASSERTMSG((pto != pfrom),
+ "can't copy passive reference to itself: %p",
+ pto);
+
+ /* Make sure the pfrom reference looks sensible. */
+ KASSERTMSG((pfrom->psref_lwp == curlwp),
+ "passive reference transferred from lwp %p to lwp %p",
+ pfrom->psref_lwp, curlwp);
+ KASSERTMSG((pfrom->psref_cpu == curcpu()),
+ "passive reference transferred from CPU %u to CPU %u",
+ cpu_index(pfrom->psref_cpu), cpu_index(curcpu()));
+ KASSERTMSG((pfrom->psref_target->prt_class == class),
+ "mismatched psref target class: %p (ref) != %p (expected)",
+ pfrom->psref_target->prt_class, class);
+
+ /* Block interrupts and acquire the current CPU's reference list. */
+ s = splraiseipl(class->prc_iplcookie);
+ pcpu = percpu_getref(class->prc_percpu);
+
+ /* Record the new reference. */
+ LIST_INSERT_HEAD(&pcpu->pcpu_head, pto, psref_entry);
+ pto->psref_target = pfrom->psref_target;
+ pto->psref_lwp = curlwp;
+ pto->psref_cpu = curcpu();
+
+ /* Release the CPU list and restore interrupts. */
+ percpu_putref(class->prc_percpu);
+ splx(s);
+}
+
+/*
+ * struct psreffed
+ *
+ * Global state for draining a psref target.
+ */
+struct psreffed {
+ struct psref_class *class;
+ struct psref_target *target;
+ bool ret;
+};
+
+static void
+psreffed_p_xc(void *cookie0, void *cookie1 __unused)
+{
+ struct psreffed *P = cookie0;
+
+ /*
+ * If we hold a psref to the target, then answer true.
+ *
+ * This is the only dynamic decision that may be made with
+ * psref_held.
+ *
+ * No need to lock anything here: every write transitions from
+ * false to true, so there can be no conflicting writes. No
+ * need for a memory barrier here because P->ret is read only
+ * after xc_wait, which has already issued any necessary memory
+ * barriers.
+ */
+ if (psref_held(P->target, P->class))
+ P->ret = true;
+}
+
+static bool
+psreffed_p(struct psref_target *target, struct psref_class *class)
+{
+ struct psreffed P = {
+ .class = class,
+ .target = target,
+ .ret = false,
+ };
+
+ /* Ask all CPUs to say whether they hold a psref to the target. */
+ xc_wait(xc_broadcast(0, &psreffed_p_xc, &P, NULL));
+
+ return P.ret;
+}
+
+/*
+ * psref_target_destroy(target, class)
+ *
+ * Destroy a passive reference target. Waits for all existing
+ * references to drain. Caller must guarantee no new references
+ * will be acquired once it calls psref_target_destroy, e.g. by
+ * removing the target from a global list first. May sleep.
+ */
+void
+psref_target_destroy(struct psref_target *target, struct psref_class *class)
+{
+
+ ASSERT_SLEEPABLE();
+
+ KASSERTMSG((target->prt_class == class),
+ "mismatched psref target class: %p (ref) != %p (expected)",
+ target->prt_class, class);
+
+ /* Request psref_release to notify us when done. */
+ KASSERTMSG(!target->prt_draining, "psref target already destroyed: %p",
+ target);
+ target->prt_draining = true;
+
+ /* Wait until there are no more references on any CPU. */
+ while (psreffed_p(target, class)) {
+ /*
+ * This enter/wait/exit business looks wrong, but it is
+ * both necessary, because psreffed_p performs a
+ * low-priority xcall and hence cannot run while a
+ * mutex is locked, and OK, because the wait is timed
+ * -- explicit wakeups are only an optimization.
+ */
+ mutex_enter(&class->prc_lock);
+ (void)cv_timedwait(&class->prc_cv, &class->prc_lock, 1);
+ mutex_exit(&class->prc_lock);
+ }
+
+ /* No more references. Cause subsequent psref_acquire to kassert. */
+ target->prt_class = NULL;
+}
+
+/*
+ * psref_held(target, class)
+ *
+ * True if the current CPU holds a passive reference to target,
+ * false otherwise. May be used only inside assertions.
+ */
+bool
+psref_held(const struct psref_target *target, struct psref_class *class)
+{
+ const struct psref_cpu *pcpu;
+ const struct psref *psref;
+ int s;
+ bool held = false;
+
+ KASSERTMSG((kpreempt_disabled() || cpu_softintr_p() ||
+ ISSET(curlwp->l_pflag, LP_BOUND)),
+ "passive references are CPU-local,"
+ " but preemption is enabled and the caller is not"
+ " in a softint or CPU-bound LWP");
+ KASSERTMSG((target->prt_class == class),
+ "mismatched psref target class: %p (ref) != %p (expected)",
+ target->prt_class, class);
+
+ /* Block interrupts and acquire the current CPU's reference list. */
+ s = splraiseipl(class->prc_iplcookie);
+ pcpu = percpu_getref(class->prc_percpu);
+
+ /* Search through all the references on this CPU. */
+ LIST_FOREACH(psref, &pcpu->pcpu_head, psref_entry) {
+ /* Sanity-check the reference. */
+ KASSERTMSG((psref->psref_lwp == curlwp),
+ "passive reference transferred from lwp %p to lwp %p",
+ psref->psref_lwp, curlwp);
+ KASSERTMSG((psref->psref_cpu == curcpu()),
+ "passive reference transferred from CPU %u to CPU %u",
+ cpu_index(psref->psref_cpu), cpu_index(curcpu()));
+
+ /* If it matches, stop here and answer yes. */
+ if (psref->psref_target == target) {
+ held = true;
+ break;
+ }
+ }
+
+ /* Release the CPU list and restore interrupts. */
+ percpu_putref(class->prc_percpu);
+ splx(s);
+
+ return held;
+}
Index: src/sys/sys/psref.h
diff -u /dev/null src/sys/sys/psref.h:1.1
--- /dev/null Sat Apr 9 06:21:17 2016
+++ src/sys/sys/psref.h Sat Apr 9 06:21:16 2016
@@ -0,0 +1,95 @@
+/* $NetBSD: psref.h,v 1.1 2016/04/09 06:21:16 riastradh 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.
+ */
+
+#ifndef _SYS_PSREF_H
+#define _SYS_PSREF_H
+
+#include <sys/types.h>
+#include <sys/queue.h>
+
+struct cpu_info;
+struct lwp;
+
+struct psref;
+struct psref_class;
+struct psref_target;
+
+/*
+ * struct psref_target
+ *
+ * Bookkeeping for an object to which users can acquire passive
+ * references. This is compact so that it can easily be embedded
+ * into many multitudes of objects, e.g. IP packet flows.
+ *
+ * prt_draining is false on initialization, and may be written
+ * only once, to make it true, when someone has prevented new
+ * references from being created and wants to drain the target in
+ * order to destroy it.
+ */
+struct psref_target {
+ struct psref_class *prt_class;
+ bool prt_draining;
+};
+
+/*
+ * struct psref
+ *
+ * Bookkeeping for a single passive reference. There should only
+ * be a few of these per CPU in the system at once, no matter how
+ * many targets are stored, so these are a bit larger than struct
+ * psref_target. The contents of struct psref may be read and
+ * written only on the local CPU.
+ */
+struct psref {
+ LIST_ENTRY(psref) psref_entry;
+ const struct psref_target *psref_target;
+ struct lwp *psref_lwp;
+ struct cpu_info *psref_cpu;
+};
+
+struct psref_class *
+ psref_class_create(const char *, int);
+void psref_class_destroy(struct psref_class *);
+
+void psref_target_init(struct psref_target *, struct psref_class *);
+void psref_target_destroy(struct psref_target *, struct psref_class *);
+
+void psref_acquire(struct psref *, const struct psref_target *,
+ struct psref_class *);
+void psref_release(struct psref *, const struct psref_target *,
+ struct psref_class *);
+void psref_copy(struct psref *, const struct psref *,
+ struct psref_class *);
+
+/* For use only in assertions. */
+bool psref_held(const struct psref_target *, struct psref_class *);
+
+#endif /* _SYS_PSREF_H */
