From 3c552130ca2aa2c373edf2db7e3ca05076decb63 Mon Sep 17 00:00:00 2001 From: David Gwynne Date: Wed, 9 Sep 2015 11:21:52 +0000 Subject: implement a singly linked list built with SRPs. this allows us to build lists of things that can be followed by multiple cpus. ok mpi@ claudio@ --- share/man/man9/Makefile | 14 ++- share/man/man9/srpl_rc_init.9 | 232 ++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 244 insertions(+), 2 deletions(-) create mode 100644 share/man/man9/srpl_rc_init.9 (limited to 'share') diff --git a/share/man/man9/Makefile b/share/man/man9/Makefile index 67f2460b8d1..fc4469b4ea6 100644 --- a/share/man/man9/Makefile +++ b/share/man/man9/Makefile @@ -1,4 +1,4 @@ -# $OpenBSD: Makefile,v 1.240 2015/09/01 12:50:03 mpi Exp $ +# $OpenBSD: Makefile,v 1.241 2015/09/09 11:21:51 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 \ - spl.9 srp_enter.9 startuphook_establish.9 \ + spl.9 srp_enter.9 srpl_rc_init.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 tsleep.9 tvtohz.9 \ uiomove.9 uvm.9 usbd_close_pipe.9 usbd_open_pipe.9 usbd_transfer.9 \ @@ -369,6 +369,16 @@ MLINKS+=srp_enter.9 srp_init.9 srp_enter.9 srp_gc_init.9 \ srp_enter.9 srp_follow.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+=srpl_rc_init.9 SRPL_HEAD_INIT.9 srpl_rc_init.9 SRPL_HEAD_INIT.9 \ + srpl_rc_init.9 SRPL_ENTRY_INIT.9 srpl_rc_init.9 SRPL_ENTER.9 \ + srpl_rc_init.9 SRPL_NEXT.9 srpl_rc_init.9 SRPL_FOREACH.9 \ + srpl_rc_init.9 SRPL_LEAVE.9 srpl_rc_init.9 SRPL_EMPTY_LOCKED.9 \ + srpl_rc_init.9 SRPL_FIRST_LOCKED.9 srpl_rc_init.9 SRPL_NEXT_LOCKED.9 \ + srpl_rc_init.9 SRPL_FOREACH_LOCKED.9 \ + srpl_rc_init.9 SRPL_INSERT_HEAD_LOCKED.9 \ + srpl_rc_init.9 SRPL_REMOVE_LOCKED.9 \ + srpl_rc_init.9 SRPL_RC_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/srpl_rc_init.9 b/share/man/man9/srpl_rc_init.9 new file mode 100644 index 00000000000..77a7726c003 --- /dev/null +++ b/share/man/man9/srpl_rc_init.9 @@ -0,0 +1,232 @@ +.\" $OpenBSD: srpl_rc_init.9,v 1.1 2015/09/09 11:21:51 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: September 9 2015 $ +.Dt SRPL_RC_INIT 9 +.Os +.Sh NAME +.Nm srpl_rc_init , +.Nm SRPL_INIT , +.Nm SRPL_ENTER , +.Nm SRPL_NEXT , +.Nm SRPL_FOREACH , +.Nm SRPL_LEAVE , +.Nm SRPL_EMPTY_LOCKED , +.Nm SRPL_FIRST_LOCKED , +.Nm SRPL_NEXT_LOCKED , +.Nm SRPL_FOREACH_LOCKED , +.Nm SRPL_INSERT_HEAD_LOCKED , +.Nm SRPL_REMOVE_LOCKED , +.Nm SRPL_RC_INITIALIZER , +.Nd singly-linked shared reference pointer list +.Sh SYNOPSIS +.In sys/srp.h +.Vt struct srpl; +.Vt struct srpl_entry; +.Vt struct srpl_iter; +.Vt struct srpl_rc; +.Ft void +.Fo "srpl_rc_init" +.Fa "struct srpl_rc *rc" +.Fa "void (*ref)(void *, void *)" +.Fa "void (*unref)(void *, void *)" +.Fa "void *ctx" +.Fc +.Fn "SRPL_INIT" "struct srpl_head *sl" +.Ft void * +.Fn "SRPL_ENTER" "struct srpl *sl" "struct srpl_iter *si" +.Ft void * +.Fn "SRPL_NEXT" "struct srpl_iter *si" "struct TYPE *listelm" "FIELDNAME" +.Fo "SRPL_FOREACH" +.Fa "VARNAME" +.Fa "struct srpl *sl" +.Fa "struct srpl_iter *si" +.Fa "FIELDNAME" +.Fc +.Fn "SRPL_LEAVE" "struct srpl_iter *si" "struct TYPE *listelm" +.Fn "SRPL_EMPTY_LOCKED" "struct srpl *sl" +.Ft void * +.Fn "SRPL_FIRST_LOCKED" "struct srpl *sl" +.Ft void * +.Fn "SRPL_NEXT_LOCKED" "struct TYPE *listelm" "FIELDNAME" +.Fn "SRPL_FOREACH_LOCKED" "VARNAME" "struct srpl *sl" "FIELDNAME" +.Fo "SRPL_INSERT_HEAD_LOCKED" +.Fa "struct srpl_rc *rc" +.Fa "struct srpl *sl" +.Fa "struct TYPE *elm" +.Fa "FIELDNAME" +.Fc +.Fo "SRPL_REMOVE_LOCKED" +.Fa "struct srpl_rc *rc" +.Fa "struct srpl *sl" +.Fa "struct TYPE *listelm" +.Fa "TYPE" +.Fa "FIELDNAME" +.Fc +.Sh DESCRIPTION +The +srpl +macros build a linked list on top of shared reference pointers. +This allows concurrent traversal of a linked list and access to the +items on the list. +.Pp +SRP lists are a generic type represented by a +.Vt struct srpl . +The elements inserted into the list must be structures that contain a +.Vt struct srpl_entry +field. +Further, the elements must also support reference counting as +insertion and removal operations can cause items to be temporarily +referenced by multiple SRPs within the list at the same time. +.Pp +.Fn srpl_rc_init +initialises the SRP list refcounts +.Fa rc +structure so it can be used to manage the reference counts on +elements in the list. +The insertion or removal of an element in an SRP list will increment +the reference counts on elements within the list via calls to +.Fa ref . +. +As these references are released by the SRP infrastructure, the +reference counts will be decremented by calls to +.Fa unref . +.Fa unref +is also responsible for freeing the element when the reference count +reaches 0. +Both +.Fa ref +and +.Fa unref +will be called with +.Fa ctx +as their first argument and a pointer to the element as their second +argument. +.Pp +.Fn SRPL_INIT +initialises the SRP list +.Fa sl +to an empty state. +.Pp +.Fn SRPL_ENTER +begins iterating over elements in the SRP list +.Fa sl . +Local state necessary for iterating over the list is stored in the +SRP list iterator structure +.Fa si . +Every call to +.Fn SRPL_ENTER +must have a corresponding call to +.Fn SRPL_LEAVE +to release references to the list and its elements. +.Pp +.Fn SRPL_NEXT +accesses the element in the SRP list after +.Fa listelm . +.Pp +.Fn SRPL_FOREACH +creates a loop for traversing the list. +Every call to +.Fn SRPL_FOREACH +must have a corresponding call to +.Fn SRPL_LEAVE +to release references to the list and its elements. +.Pp +.Fn SRPL_LEAVE +releases references to the list and its elements held by previous +calls to +.Fn SRPL_ENTER +or +.Fn SRPL_FOREACH . +.Pp +.Fn SRPL_EMPTY_LOCKED +tests whether the SRP list +.Fa sl +is empty. +.Pp +.Fn SRPL_FIRST_LOCKED +accesses the first element in the SRP list +.Fa sl . +.Pp +.Fn SRPL_NEXT_LOCKED +accesses the next element in the SRP list after +.Fa listelm . +.Pp +.Fn SRPL_FOREACH_LOCKED +creates a loop for traversing the elements in the SRP list +.Fa sl . +.Pp +.Fn SRPL_INSERT_HEAD_LOCKED +inserts +.Fa elm +into the SRP list +.Fa sl . +Reference counts are adjusted on the list items using the functions +specified by +.Fa rc . +.Fn SRPL_REMOVE_LOCKED +iterates over the SRP list +.Fa sl +until it finds +.Fa listelm +and then removes it. +Reference counts are adjusted on the list items using the functions +specified by +.Fa rc . +.Pp +An srpl_rc declaration can be initialised with the +.Fn SRPL_RC_INITIALIZER +macro. +.Sh CONTEXT +.Fn SRPL_INIT , +.Fn SRPL_ENTER , +.Fn SRPL_NEXT , +.Fn SRPL_FOREACH , +and +.Fn SRPL_LEAVE +may be called during autoconf, from process context, or from interrupt +context. +.Pp +.Fn srpl_rc_init , +.Fn SRPL_EMPTY_LOCKED , +.Fn SRPL_FIRST_LOCKED , +.Fn SRPL_NEXT_LOCKED , +.Fn SRPL_FOREACH_LOCKED , +.Fn SRPL_INSERT_HEAD_LOCKED , +and +.Fn SRPL_REMOVE_LOCKED +may be called during autoconf or from process context. +An appropriate lock must be held that prevents concurrent modifications +to the list. +.Sh RETURN VALUES +.Fn SRPL_ENTER , +.Fn SRPL_NEXT , +.Fn SRPL_FIRST_LOCKED , +and +.Fn SRPL_NEXT_LOCKED +return a pointer to elements in the SRP list, or +.Dv NULL +if there are no more elements. +.Pp +.Fn SRPL_EMPTY_LOCKED +returns non-zero when the list is empty, otherwise 0. +.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 list API first appeared in +.Ox 5.9 . -- cgit v1.2.3