add RBT_POISON and RBT_CHECK so you can poison the pointers in RBT_ENTRYs

this seems like a better way forward than simply removing the
poisoning that uvm does.

3 files changed, 69 insertions, 5 deletions

diff --git a/share/man/man9/RBT_INIT.9 b/share/man/man9/RBT_INIT.9
index 250a3cf8944..9bc87091882 100644
--- a/share/man/man9/RBT_INIT.9
+++ b/share/man/man9/RBT_INIT.9
@@ -1,4 +1,4 @@
-.\"	$OpenBSD: RBT_INIT.9,v 1.4 2016/09/15 04:55:18 dlg Exp $
+.\"	$OpenBSD: RBT_INIT.9,v 1.5 2016/09/15 06:07:22 dlg Exp $
 .\"
 .\" * Copyright 2002 Niels Provos <provos@citi.umich.edu>
 .\" * All rights reserved.
@@ -64,7 +64,9 @@
 .Nm RBT_FOREACH ,
 .Nm RBT_FOREACH_SAFE ,
 .Nm RBT_FOREACH_REVERSE ,
-.Nm RBT_FOREACH_REVERSE_SAFE
+.Nm RBT_FOREACH_REVERSE_SAFE ,
+.Nm RBT_POISON ,
+.Nm RBT_CHECK
 .Nd Kernel red-black trees
 .Sh SYNOPSIS
 .In sys/tree.h
@@ -134,6 +136,10 @@
 .Fa "struct NAME *rbt"
 .Fa "NEXTVARNAME"
 .Fc
+.Ft void
+.Fn RBT_POISON "NAME" "struct TYPE *elm" "unsigned long poison"
+.Ft int
+.Fn RBT_CHECK "NAME" "struct TYPE *elm" "unsigned long poison"
 .Sh DESCRIPTION
 The red-black tree API provides data structures and operations for
 storing structures in red-black trees.
@@ -381,6 +387,22 @@ to each element in turn.
 may be removed from the tree during iteration because a reference to the next
 element is held in
 .Fa NEXTVARNAME .
+.Ss Red-Black Tree Element Poisoning
+.Fn RBT_POISON
+is used to poison the pointers in the RBT_ENTRY structure inside
+.Fa elm
+which has been removed from a red-black tree of type
+.Fa NAME
+with the
+.Fa poison
+value.
+.Pp
+.Fn RBT_CHECK
+is used to verify that the pointers in the RBT_ENTRY structure inside
+.Fa elm
+are set to the
+.Fa poison
+value.
 .Sh CONTEXT
 .Fn RBT_INIT ,
 .Fn RBT_INSERT ,
@@ -399,8 +421,10 @@ element is held in
 .Fn RBT_FOREACH ,
 .Fn RBT_FOREACH_REVERSE ,
 .Fn RBT_FOREACH_SAFE ,
+.Fn RBT_FOREACH_SAFE_REVERSE ,
+.Fn RBT_POISON ,
 and
-.Fn RBT_FOREACH_SAFE_REVERSE
+.Fn RBT_CHECK
 can be called during autoconf, from process context, or from interrupt
 context.
 .Pp
@@ -490,6 +514,12 @@ returns a reference to the parent element of
 or
 .Dv NULL
 if it is the root of the tree.
+.Pp
+.Fn RBT_CHECK
+returns non-zero if the RBT_ENTRY in the red-black tree element contains the
+.Fa poison
+value,
+otherwise 0.
 .Sh SEE ALSO
 .Xr RB_INIT 3
 .Sh HISTORY
diff --git a/sys/kern/subr_tree.c b/sys/kern/subr_tree.c
index 930b94a9dad..89d82588e77 100644
--- a/sys/kern/subr_tree.c
+++ b/sys/kern/subr_tree.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: subr_tree.c,v 1.3 2016/09/15 05:31:24 dlg Exp $ */
+/*	$OpenBSD: subr_tree.c,v 1.4 2016/09/15 06:07:22 dlg Exp $ */
 
 /*
  * Copyright 2002 Niels Provos <provos@citi.umich.edu>
@@ -592,3 +592,21 @@ _rb_parent(const struct rb_type *t, void *node)
 	return (rbe == NULL ? NULL : rb_e2n(t, rbe));
 }
 
+void
+_rb_poison(const struct rb_type *t, void *node, unsigned long poison)
+{
+	struct rb_entry *rbe = rb_n2e(t, node);
+
+	RBE_PARENT(rbe) = RBE_LEFT(rbe) = RBE_RIGHT(rbe) =
+	    (struct rb_entry *)poison;
+}
+
+int
+_rb_check(const struct rb_type *t, void *node, unsigned long poison)
+{
+	struct rb_entry *rbe = rb_n2e(t, node);
+
+	return ((unsigned long)RBE_PARENT(rbe) == poison &&
+	    (unsigned long)RBE_LEFT(rbe) == poison &&
+	    (unsigned long)RBE_RIGHT(rbe) == poison);
+}
diff --git a/sys/sys/tree.h b/sys/sys/tree.h
index 34d97739544..e8e729c8a0d 100644
--- a/sys/sys/tree.h
+++ b/sys/sys/tree.h
@@ -1,4 +1,4 @@
-/*	$OpenBSD: tree.h,v 1.23 2016/09/15 05:21:09 dlg Exp $	*/
+/*	$OpenBSD: tree.h,v 1.24 2016/09/15 06:07:22 dlg Exp $	*/
 /*
  * Copyright 2002 Niels Provos <provos@citi.umich.edu>
  * All rights reserved.
@@ -815,6 +815,8 @@ void	*_rb_left(const struct rb_type *, void *);
 void	*_rb_right(const struct rb_type *, void *);
 void	*_rb_parent(const struct rb_type *, void *);
 void	*_rb_color(const struct rb_type *, void *);
+void	 _rb_poison(const struct rb_type *, void *, unsigned long);
+int	 _rb_check(const struct rb_type *, void *, unsigned long);
 
 #define RBT_INITIALIZER(_head)	{ { NULL } }
 
@@ -903,6 +905,18 @@ static inline struct _type *						\
 _name##_RBT_PARENT(struct _type *elm)					\
 {									\
 	return _rb_parent(_name##_RBT_TYPE, elm);			\
+}									\
+									\
+static inline void							\
+_name##_RBT_POISON(struct _type *elm, unsigned long poison)		\
+{									\
+	return _rb_poison(_name##_RBT_TYPE, elm, poison);		\
+}									\
+									\
+static inline int							\
+_name##_RBT_CHECK(struct _type *elm, unsigned long poison)		\
+{									\
+	return _rb_check(_name##_RBT_TYPE, elm, poison);		\
 }
 
 #define RBT_GENERATE_INTERNAL(_name, _type, _field, _cmp, _aug)		\
@@ -945,6 +959,8 @@ RBT_GENERATE_INTERNAL(_name, _type, _field, _cmp, _name##_RBT_AUGMENT)
 #define RBT_LEFT(_name, _elm)		_name##_RBT_LEFT(_elm)
 #define RBT_RIGHT(_name, _elm)		_name##_RBT_RIGHT(_elm)
 #define RBT_PARENT(_name, _elm)		_name##_RBT_PARENT(_elm)
+#define RBT_POISON(_name, _elm, _p)	_name##_RBT_POISON(_elm, _p)
+#define RBT_CHECK(_name, _elm, _p)	_name##_RBT_CHECK(_elm, _p)
 
 #define RBT_FOREACH(_e, _name, _head)					\
 	for ((_e) = RBT_MIN(_name, (_head));				\