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@

4 files changed, 365 insertions, 4 deletions

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 <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: 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 <jmatthew@openbsd.org>
@@ -27,6 +27,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)
 {
 	srp_gc->srp_gc_dtor = dtor;
@@ -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 <jmatthew@openbsd.org>
@@ -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_ */