introduce srp, which according to the manpage i wrote is short for

"shared reference pointers".

srp allows concurrent access to a data structure by multiple cpus
while avoiding interlocking cpu opcodes. it manages its own reference
counts and the garbage collection of those data structure to avoid
use after frees.

internally srp is a twisted version of hazard pointers, which are
a relative of RCU.

jmatthew wrote the bulk of a hazard pointer implementation and
changed bpf to use it to allow mpsafe access to bpfilters. however,
at s2k15 we were trying to apply it to other data structures but
the memory overhead of every hazard pointer would have blown out
significantly in several uses cases. a bulk of our time at s2k15
was spent reworking hazard pointers into srp.

this diff adds the srp api and adds the necessary metadata to struct
cpuinfo on our MP architectures. srp on uniprocessor platforms has
alternate code that is optimised because it knows there'll be no
concurrent access to data by multiple cpus.

srp is made available to the system via param.h, so it should be
available everywhere in the kernel.

the docs likely need improvement cos im too close to the implementation.

ok mpi@

2 files changed, 175 insertions, 2 deletions

diff --git a/share/man/man9/Makefile b/share/man/man9/Makefile
index 2386f36713f..c3e899f1072 100644
--- a/share/man/man9/Makefile
+++ b/share/man/man9/Makefile
@@ -1,4 +1,4 @@
-#	$OpenBSD: Makefile,v 1.234 2015/06/17 06:24:46 mpi Exp $
+#	$OpenBSD: Makefile,v 1.235 2015/07/02 01:33:59 dlg Exp $
 #	$NetBSD: Makefile,v 1.4 1996/01/09 03:23:01 thorpej Exp $
 
 #	Makefile for section 9 (kernel function and variable) manual pages.
@@ -29,7 +29,7 @@ MAN=	aml_evalnode.9 atomic_add_int.9 atomic_cas_uint.9 \
 	radio.9 arc4random.9 rasops.9 ratecheck.9 resettodr.9 rssadapt.9 \
 	route.9 rt_ifa_add.9 rt_timer_add.9 rtalloc.9 rtable_add.9 \
 	rtlabel_id2name.9 rtrequest1.9 rwlock.9 SipHash24.9 sensor_attach.9 \
-	tsleep.9 spl.9 startuphook_establish.9 \
+	tsleep.9 spl.9 srp_enter.9 startuphook_establish.9 \
 	socreate.9 sosplice.9 style.9 syscall.9 systrace.9 sysctl_int.9 \
 	task_add.9 tc_init.9 time.9 timeout.9 tvtohz.9 uiomove.9 uvm.9 \
 	usbd_close_pipe.9 usbd_open_pipe.9 usbd_transfer.9 \
@@ -362,6 +362,11 @@ MLINKS+=spl.9 spl0.9 spl.9 splassert.9 spl.9 splbio.9 spl.9 splclock.9 \
 	spl.9 splsoftnet.9 spl.9 splsofttty.9 \
 	spl.9 splstatclock.9 spl.9 spltty.9 spl.9 splvm.9 spl.9 splx.9
 MLINKS+=startuphook_establish.9 startuphook_disestablish.9
+MLINKS+=srp_enter.9 srp_init.9 srp_enter.9 srp_gc_init.9 \
+	srp_enter.9 srp_update.9 srp_enter.9 srp_update_locked.9 \
+	srp_enter.9 srp_leave.9 srp_enter.9 srp_get_locked.9 \
+	srp_enter.9 srp_finalize.9 \
+	srp_enter.9 SRP_INITIALIZER.9 srp_enter.9 SRP_GC_INITIALIZER.9
 MLINKS+=sysctl_int.9 sysctl_int_arr.9 sysctl_int.9 sysctl_quad.9 \
 	sysctl_int.9 sysctl_string.9 sysctl_int.9 sysctl_tstring.9 \
 	sysctl_int.9 sysctl_rdint.9 sysctl_int.9 sysctl_rdquad.9 \
diff --git a/share/man/man9/srp_enter.9 b/share/man/man9/srp_enter.9
new file mode 100644
index 00000000000..604629a91f1
--- /dev/null
+++ b/share/man/man9/srp_enter.9
@@ -0,0 +1,168 @@
+.\"	$OpenBSD: srp_enter.9,v 1.1 2015/07/02 01:33:59 dlg Exp $
+.\"
+.\" Copyright (c) 2015 David Gwynne <dlg@openbsd.org>
+.\"
+.\" Permission to use, copy, modify, and distribute this software for any
+.\" purpose with or without fee is hereby granted, provided that the above
+.\" copyright notice and this permission notice appear in all copies.
+.\"
+.\" THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+.\" WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+.\" MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+.\" ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+.\" WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+.\" ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+.\" OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+.\"
+.Dd $Mdocdate: July 2 2015 $
+.Dt SRP_ENTER 9
+.Os
+.Sh NAME
+.Nm srp_init ,
+.Nm srp_gc_init ,
+.Nm srp_update ,
+.Nm srp_update_locked ,
+.Nm srp_enter ,
+.Nm srp_leave ,
+.Nm srp_get_locked ,
+.Nm srp_finalize ,
+.Nm SRP_INITIALIZER ,
+.Nm SRP_GC_INITIALIZER
+.Nd shared reference pointers
+.Sh SYNOPSIS
+.In sys/srp.h
+.Ft void
+.Fn "srp_init" "struct srp *p"
+.Ft void
+.Fo "srp_gc_init"
+.Fa "struct srp_gc *gc"
+.Fa "void (*dtor)(void *, void *)"
+.Fa "void *ctx"
+.Fc
+.Ft void
+.Fn "srp_update" "struct srp_gc *gc" "struct srp *p" "void *v"
+.Ft void
+.Fn "srp_update_locked" "struct srp_gc *gc" "struct srp *p" "void *v"
+.Ft void *
+.Fn "srp_enter" "struct srp *p"
+.Ft void
+.Fn "srp_leave" "struct srp *p" "void *v"
+.Ft void *
+.Fn "srp_get_locked" "struct srp *p"
+.Ft void
+.Fn "srp_finalize" "struct srp_gc *gc"
+.Fn "SRP_INITIALIZER"
+.Fo "SRP_GC_INITIALIZER"
+.Fa "void (*dtor)(void *, void *)"
+.Fa "void *ctx"
+.Fc
+.Sh DESCRIPTION
+The
+srp
+API provides concurrent lock free access to data structures and guarantees the
+data isn't destroyed while it is in use.
+.Pp
+.Fn srp_init
+initialises the srp structure
+.Fa p
+to an empty state.
+.Pp
+.Fn srp_gc_init
+initialises the srp_gc structure
+.Fa gc
+so it can be used as a garbage collector for data that gets referenced by srp
+structures.
+An update to an srp structure will cause the old data to be destroyed when it
+is no longer referenced by any CPU in the system.
+The old data will be destroyed by the garbage collector by a call to
+.Fa dtor
+with
+.Fa ctx
+as the first argument and the pointer to the data as the second argument.
+.Pp
+.Fn srp_update
+and
+.Fn srp_update_locked
+replace the data referenced by the srp struct
+.Fa p
+with the data referenced by
+.Fa v .
+When the original data is no longer in use it will be destroyed by the garbage
+collector
+.Fa gc .
+.Fn srp_update
+uses atomic CPU operations to change the references.
+.Fn srp_update_locked
+may be used if modifications to
+.Fa p
+are already serialised by the caller.
+.Pp
+.Fn srp_enter
+returns a pointer to a data structure referenced by the srp struct
+.Fa p
+and guarantees it will remain available for use until a call to
+.Fn srp_leave .
+.Pp
+.Fn srp_leave
+releases the reference to
+.Fa v
+by the srp struct
+.Fa p
+and makes it available for garbage collection.
+.Pp
+.Fn srp_get_locked
+provides access to the data referenced by the srp
+.Fa p
+if the caller has excluded updates to
+.Fa p .
+.Pp
+.Fn srp_finalize
+sleeps until all references to data by srp structures using the
+garbage collector
+.Fa gc
+have completed.
+That in turn means the
+.Fa gc
+structure will no longer be referenced and can itself be destroyed.
+.Pp
+A srp structure declaraction can be initialised with the
+.Fn SRP_INITIALIZER
+macro.
+.Pp
+A srp_gc structure declaraction can be initialised with the
+.Fn SRP_GC_INITIALIZER
+macro.
+Data will be destroyed by the garbage collector by a call to
+.Fa dtor
+with
+.Fa ctx
+as the first argument and the pointer to the data as the second argument.
+.Sh CONTEXT
+.Fn srp_init ,
+.Fn srp_gc_init ,
+.Fn srp_update ,
+.Fn srp_update_locked ,
+.Fn srp_update_get_locked ,
+and
+.Fn srp_finalize
+can be called during autoconf, or from process context.
+.Pp
+.Fn srp_enter
+and
+.Fn srp_leave
+can be called during autoconf, from process context, or from interrupt context.
+.Sh RETURN VALUES
+.Fn srp_enter
+and
+.Fn srp_get_locked
+returns a pointer to the data referenced by the srp structure
+.Fa p
+or
+.Dv NULL .
+.Sh HISTORY
+The srp API was originally written by
+.An Jonathan Matthew Aq Mt jmatthew@openbsd.org
+and
+.An David Gwynne Aq Mt dlg@openbsd.org .
+The srp API first appeared in
+.Ox 5.8 .