mattieu baptiste reported a problem with bpf+srps where the per cpu

hazard pointers were becoming corrupt and therefore panics.

the problem turned out to be that bridge_input calls if_input on
behalf of a hardware interface which then calls bpf_mtap at splsoftnet,
while the actual hardware nic calls if_input and bpf_mtap at splnet.
the hardware interrupts ran in the middle of the bpf calls bridge
runs at softnet. this means the same srps are being entered and
left on the same cpu at different ipls, which led to races because
of the order of operations on the per cpu hazard pointers.

after a lot of experimentation, jmatthew@ figured out how to deal
with this problem without introducing per cpu critical sections
(ie, splhigh) calls in srp_enter and srp_leave, and without introducing
atomic operations.

the solution is to iterate forward through the array of hazard
pointers in srp_enter, and backward in srp_leave to clear. if you
guarantee that you leave srps in the reverse order to entering them,
then you can use the same set of SRPs at different IPLs on the same
CPU.

the ordering requirement is a problem if we want to build linked
data structures out of srps because you need to hold a ref to the
current element containing the next srp to use it, before giving
up the current ref. we're adding srp_follow() to support taking the
next ref and giving up the current one while preserving the structure
of the hazard pointer list. srp_follow() does this by reusing the
hazard pointer for the current reference for the next ref.

both mattieu baptiste and jmatthew@ have been hitting this pretty
hard with a tweaked version of srp+bpf that uses srp_follow instead
of interleaved srp_enter/srp_leave sequences. neither can reproduce
the panics anymore.

thanks to mattieu for the report and tests
ok jmatthew@

4 files changed, 101 insertions, 30 deletions

diff --git a/share/man/man9/Makefile b/share/man/man9/Makefile
index 3f31bfa1c34..47ee2f46a23 100644
--- a/share/man/man9/Makefile
+++ b/share/man/man9/Makefile
@@ -1,4 +1,4 @@
-#	$OpenBSD: Makefile,v 1.238 2015/08/14 05:25:29 dlg Exp $
+#	$OpenBSD: Makefile,v 1.239 2015/09/01 03:47:58 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.
@@ -366,8 +366,8 @@ MLINKS+=spl.9 spl0.9 spl.9 splassert.9 spl.9 splbio.9 spl.9 splclock.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_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+=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 \
diff --git a/share/man/man9/srp_enter.9 b/share/man/man9/srp_enter.9
index 7b91369b131..e19708ec3ac 100644
--- a/share/man/man9/srp_enter.9
+++ b/share/man/man9/srp_enter.9
@@ -1,4 +1,4 @@
-.\"	$OpenBSD: srp_enter.9,v 1.3 2015/08/14 05:18:50 dlg Exp $
+.\"	$OpenBSD: srp_enter.9,v 1.4 2015/09/01 03:47:58 dlg Exp $
 .\"
 .\" Copyright (c) 2015 David Gwynne <dlg@openbsd.org>
 .\"
@@ -14,7 +14,7 @@
 .\" ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
 .\" OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 .\"
-.Dd $Mdocdate: August 14 2015 $
+.Dd $Mdocdate: September 1 2015 $
 .Dt SRP_ENTER 9
 .Os
 .Sh NAME
@@ -23,6 +23,7 @@
 .Nm srp_update ,
 .Nm srp_update_locked ,
 .Nm srp_enter ,
+.Nm srp_follow ,
 .Nm srp_leave ,
 .Nm srp_get_locked ,
 .Nm srp_finalize ,
@@ -45,6 +46,8 @@
 .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_follow" "struct srp *p" "void *v" "struct srp *n"
 .Ft void
 .Fn "srp_leave" "struct srp *p" "void *v"
 .Ft void *
@@ -100,8 +103,38 @@ are already serialised by the caller.
 .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 .
+and guarantees it will remain available for use until it is released with a
+call to
+.Fn srp_leave
+or
+.Fn srp_follow .
+.Pp
+.Fn srp_follow
+returns a pointer to the data structure referenced by the srp struct
+.Fa n
+that exists within the structure referenced by
+.Fa v
+via
+.Fa p ,
+while releasing the reference to
+.Fa v
+and making it available for garbage collection.
+It is equivalent to a call to
+.Fn srp_enter
+using
+.Fa n
+as an argument
+followed by a call to
+.Fn srp_leave
+with
+.Fa p
+and
+.Fa v
+as arguments.
+.Fn srp_follow
+is necessary to correctly order the taking and releasing of SRP
+critical sections in situations such as following a chain of data
+structures linked with SRPs.
 .Pp
 .Fn srp_leave
 releases the reference to
@@ -147,17 +180,30 @@ and
 .Fn srp_finalize
 can be called during autoconf, or from process context.
 .Pp
-.Fn srp_enter
+.Fn srp_enter ,
+.Fn srp_follow ,
 and
 .Fn srp_leave
 can be called during autoconf, from process context, or from interrupt context.
 Calling
+.Fn srp_follow
+or
 .Fn srp_leave
 from a different context or on a different CPU to the preceding
 .Fn srp_enter
-call will lead to undefined behaviour.
-.Sh RETURN VALUES
+or
+.Fn srp_follow
+calls will lead to undefined behaviour.
+.Pp
+SRP critical sections must be released with
+.Fn srp_leave
+in the opposite order in which they were taken with
 .Fn srp_enter
+unless a critical section is exchanged with
+.Fn srp_follow .
+.Sh RETURN VALUES
+.Fn srp_enter ,
+.Fn srp_follow ,
 and
 .Fn srp_get_locked
 returns a pointer to the data referenced by the srp structure
diff --git a/sys/kern/kern_srp.c b/sys/kern/kern_srp.c
index dcd08742558..02e607945d3 100644
--- a/sys/kern/kern_srp.c
+++ b/sys/kern/kern_srp.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: kern_srp.c,v 1.1 2015/07/02 01:34:00 dlg Exp $ */
+/*	$OpenBSD: kern_srp.c,v 1.2 2015/09/01 03:47:58 dlg Exp $ */
 
 /*
  * Copyright (c) 2014 Jonathan Matthew <jmatthew@openbsd.org>
@@ -187,24 +187,12 @@ srp_finalize(struct srp_gc *srp_gc)
 	}
 }
 
-void *
-srp_enter(struct srp *srp)
+static inline void *
+srp_v(struct srp_hazard *hzrd, struct srp *srp)
 {
-	struct cpu_info *ci = curcpu();
-	struct srp_hazard *hzrd;
 	void *v;
-	u_int i;
-
-	for (i = 0; i < nitems(ci->ci_srp_hazards); i++) {
-		hzrd = &ci->ci_srp_hazards[i];
-		if (hzrd->sh_p == NULL)
-			break;
-	}
-	if (__predict_false(i == nitems(ci->ci_srp_hazards)))
-		panic("%s: not enough srp hazard records", __func__);
 
 	hzrd->sh_p = srp;
-	membar_producer();
 
 	/*
 	 * ensure we update this cpu's hazard pointer to a value that's still
@@ -220,8 +208,8 @@ srp_enter(struct srp *srp)
 	return (v);
 }
 
-void
-srp_leave(struct srp *srp, void *v)
+void *
+srp_enter(struct srp *srp)
 {
 	struct cpu_info *ci = curcpu();
 	struct srp_hazard *hzrd;
@@ -229,9 +217,44 @@ srp_leave(struct srp *srp, void *v)
 
 	for (i = 0; i < nitems(ci->ci_srp_hazards); i++) {
 		hzrd = &ci->ci_srp_hazards[i];
-		if (hzrd->sh_p == srp) {
+		if (hzrd->sh_p == NULL)
+			return (srp_v(hzrd, srp));
+	}
+
+	panic("%s: not enough srp hazard records", __func__);
+
+	/* NOTREACHED */
+	return (NULL);
+}
+
+void *
+srp_follow(struct srp *srp, void *v, struct srp *next)
+{
+	struct cpu_info *ci = curcpu();
+	struct srp_hazard *hzrd;
+
+	hzrd = ci->ci_srp_hazards + nitems(ci->ci_srp_hazards);
+	while (hzrd-- != ci->ci_srp_hazards) {
+		if (hzrd->sh_p == srp && hzrd->sh_v == v)
+			return (srp_v(hzrd, next));
+	}
+
+	panic("%s: unexpected ref %p via %p", __func__, v, srp);
+
+	/* NOTREACHED */
+	return (NULL);
+}
+
+void
+srp_leave(struct srp *srp, void *v)
+{
+	struct cpu_info *ci = curcpu();
+	struct srp_hazard *hzrd;
+
+	hzrd = ci->ci_srp_hazards + nitems(ci->ci_srp_hazards);
+	while (hzrd-- != ci->ci_srp_hazards) {
+		if (hzrd->sh_p == srp && hzrd->sh_v == v) {
 			hzrd->sh_p = NULL;
-			hzrd->sh_v = NULL;
 			return;
 		}
 	}
diff --git a/sys/sys/srp.h b/sys/sys/srp.h
index c990c00e61b..101c84246cb 100644
--- a/sys/sys/srp.h
+++ b/sys/sys/srp.h
@@ -1,4 +1,4 @@
-/*	$OpenBSD: srp.h,v 1.1 2015/07/02 01:34:00 dlg Exp $ */
+/*	$OpenBSD: srp.h,v 1.2 2015/09/01 03:47:58 dlg Exp $ */
 
 /*
  * Copyright (c) 2014 Jonathan Matthew <jmatthew@openbsd.org>
@@ -52,10 +52,12 @@ void		 srp_init(struct srp *);
 #ifdef MULTIPROCESSOR
 void		 srp_update(struct srp_gc *, struct srp *, void *);
 void		*srp_enter(struct srp *);
+void		*srp_follow(struct srp *, void *, struct srp *);
 void		 srp_leave(struct srp *, void *);
 #else /* MULTIPROCESSOR */
 #define srp_update(_gc, _srp, _v)	srp_update_locked((_gc), (_srp), (_v))
 #define srp_enter(_srp)			((_srp)->ref)
+#define srp_follow(_srp, _v, _next)	((_next)->ref)
 #define srp_leave(_srp, _v)		do { } while (0)
 #endif /* MULTIPROCESSOR */