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 ++++++++++++++++++++++++++++++++++++++++++ sys/kern/kern_srp.c | 16 ++- sys/sys/srp.h | 107 ++++++++++++++++++- 4 files changed, 365 insertions(+), 4 deletions(-) create mode 100644 share/man/man9/srpl_rc_init.9 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 . diff --git a/sys/kern/kern_srp.c b/sys/kern/kern_srp.c index 02e607945d3..e56d8c96e54 100644 --- a/sys/kern/kern_srp.c +++ b/sys/kern/kern_srp.c @@ -1,4 +1,4 @@ -/* $OpenBSD: kern_srp.c,v 1.2 2015/09/01 03:47:58 dlg Exp $ */ +/* $OpenBSD: kern_srp.c,v 1.3 2015/09/09 11:21:51 dlg Exp $ */ /* * Copyright (c) 2014 Jonathan Matthew @@ -26,6 +26,14 @@ void srp_v_gc_start(struct srp_gc *, struct srp *, void *); +void +srpl_rc_init(struct srpl_rc *rc, void (*ref)(void *, void *), + void (*unref)(void *, void *), void *cookie) +{ + rc->srpl_ref = ref; + srp_gc_init(&rc->srpl_gc, unref, cookie); +} + void srp_gc_init(struct srp_gc *srp_gc, void (*dtor)(void *, void *), void *cookie) { @@ -40,6 +48,12 @@ srp_init(struct srp *srp) srp->ref = NULL; } +void srpl_refs_init(struct srpl_rc *, void (*)(void *, void *), + void (*)(void *, void *), void *); + +#define SRPL_RC_INITIALIZER(_r, _u, _c) { _r, SRP_GC_INITIALIZER(_u, _c) } + + void srp_update_locked(struct srp_gc *srp_gc, struct srp *srp, void *nv) { diff --git a/sys/sys/srp.h b/sys/sys/srp.h index 101c84246cb..62916b8928e 100644 --- a/sys/sys/srp.h +++ b/sys/sys/srp.h @@ -1,4 +1,4 @@ -/* $OpenBSD: srp.h,v 1.2 2015/09/01 03:47:58 dlg Exp $ */ +/* $OpenBSD: srp.h,v 1.3 2015/09/09 11:21:51 dlg Exp $ */ /* * Copyright (c) 2014 Jonathan Matthew @@ -63,4 +63,109 @@ void srp_leave(struct srp *, void *); #endif /* _KERNEL */ +/* + * singly linked list built by following srps + */ + +struct srpl_rc { + void (*srpl_ref)(void *, void *); + struct srp_gc srpl_gc; +}; +#define srpl_cookie srpl_gc.srp_gc_cookie + +struct srpl { + struct srp sl_head; +}; + +struct srpl_entry { + struct srp se_next; +}; + +struct srpl_iter { + struct srp * si_ref; +}; + +#ifdef _KERNEL + +void srpl_rc_init(struct srpl_rc *, void (*)(void *, void *), + void (*)(void *, void *), void *); + +#define SRPL_RC_INITIALIZER(_r, _u, _c) { _r, SRP_GC_INITIALIZER(_u, _c) } + +#define SRPL_INIT(_sl) srp_init(&(_sl)->sl_head) + +static inline void * +_srpl_enter(struct srpl *sl, struct srpl_iter *si) +{ + si->si_ref = &sl->sl_head; + return (srp_enter(si->si_ref)); +} + +static inline void * +_srpl_next(struct srpl_iter *si, void *elm, struct srp *nref) +{ + void *n; + + n = srp_follow(si->si_ref, elm, nref); + si->si_ref = nref; + + return (n); +} + +#define SRPL_ENTER(_sl, _si) _srpl_enter(_sl, _si) + +#define SRPL_NEXT(_si, _e, _ENTRY) \ + _srpl_next(_si, _e, &(_e)->_ENTRY.se_next) + +#define SRPL_FOREACH(_c, _sl, _si, _ENTRY) \ + for ((_c) = SRPL_ENTER(_sl, _si); \ + (_c) != NULL; \ + (_c) = SRPL_NEXT(_si, _c, _ENTRY)) + +#define SRPL_LEAVE(_si, _c) srp_leave((_si)->si_ref, (_c)) + +#define SRPL_EMPTY_LOCKED(_sl) (SRPL_FIRST_LOCKED(_sl) == NULL) +#define SRPL_FIRST_LOCKED(_sl) srp_get_locked(&(_sl)->sl_head) + +#define SRPL_NEXT_LOCKED(_e, _ENTRY) \ + srp_get_locked(&(_e)->_ENTRY.se_next) + +#define SRPL_FOREACH_LOCKED(_c, _sl, _ENTRY) \ + for ((_c) = SRPL_FIRST_LOCKED(_sl); \ + (_c) != NULL; \ + (_c) = SRPL_NEXT_LOCKED((_c), _ENTRY)) + +#define SRPL_INSERT_HEAD_LOCKED(_rc, _sl, _e, _ENTRY) do { \ + void *head; \ + \ + srp_init(&(_e)->_ENTRY.se_next); \ + \ + head = SRPL_FIRST_LOCKED(_sl); \ + if (head != NULL) { \ + (_rc)->srpl_ref(&(_rc)->srpl_cookie, head); \ + srp_update_locked(&(_rc)->srpl_gc, \ + &(_e)->_ENTRY.se_next, head); \ + } \ + \ + (_rc)->srpl_ref(&(_rc)->srpl_cookie, _e); \ + srp_update_locked(&(_rc)->srpl_gc, &(_sl)->sl_head, (_e)); \ +} while (0) + +#define SRPL_REMOVE_LOCKED(_rc, _sl, _e, _type, _ENTRY) do { \ + struct srp *ref; \ + struct _type *c, *n; \ + \ + ref = &(_sl)->sl_head; \ + while ((c = srp_get_locked(ref)) != (_e)) \ + ref = &c->_ENTRY.se_next; \ + \ + n = SRPL_NEXT_LOCKED(c, _ENTRY); \ + if (n != NULL) \ + (_rc)->srpl_ref(&(_rc)->srpl_cookie, n); \ + srp_update_locked(&(_rc)->srpl_gc, ref, n); \ + srp_update_locked(&(_rc)->srpl_gc, &c->_ENTRY.se_next, NULL); \ +} while (0) + +#endif /* _KERNEL */ + #endif /* _SYS_SRP_H_ */ -- cgit v1.2.3