From 2277e32f451a4f2c2df9aa238a1ebc6e7d6e6993 Mon Sep 17 00:00:00 2001 From: David Gwynne Date: Thu, 2 Jul 2015 01:34:01 +0000 Subject: 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@ --- share/man/man9/Makefile | 9 ++- share/man/man9/srp_enter.9 | 168 +++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 175 insertions(+), 2 deletions(-) create mode 100644 share/man/man9/srp_enter.9 (limited to 'share/man') 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 +.\" +.\" 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 . -- cgit v1.2.3