Index: sys/compat/linuxkpi/common/include/linux/rbtree.h
===================================================================
--- sys/compat/linuxkpi/common/include/linux/rbtree.h
+++ sys/compat/linuxkpi/common/include/linux/rbtree.h
@@ -41,8 +41,8 @@
 struct rb_node {
 	RB_ENTRY(rb_node)	__entry;
 };
-#define	rb_left		__entry.rbe_left
-#define	rb_right	__entry.rbe_right
+#define	rb_left		__entry.rbe_link[RB_RED_L]
+#define	rb_right	__entry.rbe_link[RB_RED_R]
 
 /*
  * We provide a false structure that has the same bit pattern as tree.h
@@ -134,10 +134,10 @@
 
 	RB_SWAP_CHILD((struct linux_root *)root, rb_parent(victim),
 	    victim, new, __entry);
-	if (victim->rb_left)
-		RB_SET_PARENT(victim->rb_left, new, __entry);
-	if (victim->rb_right)
-		RB_SET_PARENT(victim->rb_right, new, __entry);
+	if (RB_LEFT(victim, __entry))
+		RB_SET_PARENT(RB_LEFT(victim, __entry), new, __entry);
+	if (RB_RIGHT(victim, __entry))
+		RB_SET_PARENT(RB_RIGHT(victim, __entry), new, __entry);
 	*new = *victim;
 }
 
Index: sys/sys/tree.h
===================================================================
--- sys/sys/tree.h
+++ sys/sys/tree.h
@@ -318,13 +318,9 @@
 
 #define RB_ENTRY(type)							\
 struct {								\
-	struct type *rbe_left;		/* left element */		\
-	struct type *rbe_right;		/* right element */		\
-	struct type *rbe_parent;	/* parent element */		\
+	struct type *rbe_link[3];					\
 }
-
-#define RB_LEFT(elm, field)		(elm)->field.rbe_left
-#define RB_RIGHT(elm, field)		(elm)->field.rbe_right
+#define RB_LINK(elm, dir, field)	(elm)->field.rbe_link[dir]
 
 /*
  * With the expectation that any object of struct type has an
@@ -333,23 +329,25 @@
  * always zero, this implementation sets those bits to indicate
  * that the left or right child of the tree node is "red".
  */
-#define RB_UP(elm, field)		(elm)->field.rbe_parent
+#define RB_UP(elm, field)		RB_LINK(elm, 0, field)
 #define RB_BITS(elm, field)		(*(__uintptr_t *)&RB_UP(elm, field))
 #define RB_RED_L			((__uintptr_t)1)
 #define RB_RED_R			((__uintptr_t)2)
-#define RB_RED_MASK			((__uintptr_t)3)
+#define RB_RED_LR			((__uintptr_t)3)
+#define RB_LEFT(elm, field)		RB_LINK(elm, RB_RED_L, field)
+#define RB_RIGHT(elm, field)		RB_LINK(elm, RB_RED_R, field)
 #define RB_FLIP_LEFT(elm, field)	(RB_BITS(elm, field) ^= RB_RED_L)
 #define RB_FLIP_RIGHT(elm, field)	(RB_BITS(elm, field) ^= RB_RED_R)
-#define RB_FLIP_ALL(elm, field)		(RB_BITS(elm, field) ^= RB_RED_MASK)
+#define RB_FLIP_ALL(elm, field)		(RB_BITS(elm, field) ^= RB_RED_LR)
 #define _RB_PARENT_ONLY(elm)		(__typeof(elm))			\
-					((__uintptr_t)elm & ~RB_RED_MASK)
+					((__uintptr_t)elm & ~RB_RED_LR)
 #define RB_PARENT(elm, field)		_RB_PARENT_ONLY(RB_UP(elm, field))
 #define RB_ROOT(head)			(head)->rbh_root
 #define RB_EMPTY(head)			(RB_ROOT(head) == NULL)
 
 #define RB_SET_PARENT(dst, src, field) do {				\
 	RB_BITS(dst, field) = (__uintptr_t)src |			\
-	    (RB_BITS(dst, field) & RB_RED_MASK);			\
+	    (RB_BITS(dst, field) & RB_RED_LR);				\
 } while (/*CONSTCOND*/ 0)
 
 #define RB_SET(elm, parent, field) do {					\
@@ -382,31 +380,20 @@
 } while (/*CONSTCOND*/ 0)
 
 /*
- * RB_ROTATE macros partially restructure the tree to improve
- * balance. The ROTATE_RIGHT case is just a reflection of the
- * ROTATE_LEFT case.  Initially, tmp is a right child of elm.  After
- * rotation, elm is a left child of tmp, and the subtree that
- * represented the items between them, which formerly hung to the left
- * of tmp now hangs to the right of elm.  The parent-child
- * relationship between elm and its former parent is not changed;
- * where this macro once updated those fields, that is now left to the
- * caller of RB_ROTATE to clean up, so that a pair of rotations does
- * not twice update the same pair of pointer fields with distinct
- * values.
+ * RB_ROTATE macro partially restructures the tree to improve balance. In the
+ * case when dir is RB_RED_L, tmp is a right child of elm.  After rotation, elm
+ * is a left child of tmp, and the subtree that represented the items between
+ * them, which formerly hung to the left of tmp now hangs to the right of elm.
+ * The parent-child relationship between elm and its former parent is not
+ * changed; where this macro once updated those fields, that is now left to the
+ * caller of RB_ROTATE to clean up, so that a pair of rotations does not twice
+ * update the same pair of pointer fields with distinct values.
  */
-#define RB_ROTATE_LEFT(elm, tmp, field) do {				\
-	if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field)) != NULL) {	\
-		RB_SET_PARENT(RB_RIGHT(elm, field), elm, field);	\
-	}								\
-	RB_LEFT(tmp, field) = (elm);					\
-	RB_SET_PARENT(elm, tmp, field);					\
-} while (/*CONSTCOND*/ 0)
-
-#define RB_ROTATE_RIGHT(elm, tmp, field) do {				\
-	if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field)) != NULL) {	\
-		RB_SET_PARENT(RB_LEFT(elm, field), elm, field);		\
-	}								\
-	RB_RIGHT(tmp, field) = (elm);					\
+#define RB_ROTATE(elm, tmp, dir, field) do {				\
+	if ((RB_LINK(elm, dir ^ RB_RED_LR, field) =			\
+	    RB_LINK(tmp, dir, field)) != NULL)				\
+		RB_SET_PARENT(RB_LINK(tmp, dir, field), elm, field);	\
+	RB_LINK(tmp, dir, field) = (elm);				\
 	RB_SET_PARENT(elm, tmp, field);					\
 } while (/*CONSTCOND*/ 0)
 
@@ -483,68 +470,39 @@
 	 * one.								\
 	 */								\
 	struct type *child, *gpar = RB_UP(elm, field), *parent;		\
-	__uintptr_t red;						\
+	__uintptr_t dir, red;						\
 									\
 	while ((parent = gpar) != NULL) {				\
 		red = RB_BITS(parent, field);				\
 		gpar = RB_UP(parent, field);				\
-		if (RB_LEFT(parent, field) == elm) {			\
-			if (red & RB_RED_L) {				\
-				RB_FLIP_LEFT(parent, field);		\
-				return;					\
-			}						\
-			RB_FLIP_RIGHT(parent, field);			\
-			if ((red & RB_RED_MASK) == 0) {			\
-				child = elm;				\
-				elm = parent;				\
-				continue;				\
-			}						\
-			red = RB_BITS(elm, field);			\
-			if (red & RB_RED_R)				\
-				child = elm;				\
-			else {						\
-				/* coverity[uninit_use] */		\
-				RB_ROTATE_LEFT(elm, child, field);	\
-				red = RB_BITS(child, field);		\
-				if (red & RB_RED_R)			\
-					RB_FLIP_LEFT(parent, field);	\
-				if (red & RB_RED_L)			\
-					RB_FLIP_ALL(elm, field);	\
-				else					\
-					RB_FLIP_LEFT(elm, field);	\
-				if ((red & RB_RED_MASK) == 0)		\
-					elm = child;			\
-			}						\
-			RB_ROTATE_RIGHT(parent, child, field);		\
-		} else {						\
-			if (red & RB_RED_R) {				\
-				RB_FLIP_RIGHT(parent, field);		\
-				return;					\
-			}						\
-			RB_FLIP_LEFT(parent, field);			\
-			if ((red & RB_RED_MASK) == 0) {			\
-				child = elm;				\
-				elm = parent;				\
-				continue;				\
-			}						\
-			red = RB_BITS(elm, field);			\
-			if (red & RB_RED_L)				\
-				child = elm;				\
-			else {						\
-				/* coverity[uninit_use] */		\
-				RB_ROTATE_RIGHT(elm, child, field);	\
-				red = RB_BITS(child, field);		\
-				if (red & RB_RED_L)			\
-					RB_FLIP_RIGHT(parent, field);	\
-				if (red & RB_RED_R)			\
-					RB_FLIP_ALL(elm, field);	\
-				else					\
-					RB_FLIP_RIGHT(elm, field);	\
-				if ((red & RB_RED_MASK) == 0)		\
-					elm = child;			\
-			}						\
-			RB_ROTATE_LEFT(parent, child, field);		\
+		dir = RB_LEFT(parent, field) == elm ?			\
+		    RB_RED_L : RB_RED_R;				\
+		if (red & dir) {					\
+			RB_BITS(parent, field) ^= dir;			\
+			return;						\
 		}							\
+		RB_BITS(parent, field) ^= dir ^ RB_RED_LR;		\
+		if ((red & RB_RED_LR) == 0) {				\
+			child = elm;					\
+			elm = parent;					\
+			continue;					\
+		}							\
+		red = RB_BITS(elm, field);				\
+		if (red & dir) {					\
+			/* coverity[uninit_use] */			\
+			RB_ROTATE(elm, child, dir, field);		\
+			red = RB_BITS(child, field);			\
+			if (red & (dir ^ RB_RED_LR))			\
+				RB_BITS(parent, field) ^= dir;		\
+			if (red & dir)					\
+				RB_FLIP_ALL(elm, field);		\
+			else						\
+				RB_BITS(elm, field) ^= dir;		\
+			if ((red & RB_RED_LR) == 0)			\
+				elm = child;				\
+		} else							\
+			child = elm;					\
+		RB_ROTATE(parent, child, dir ^ RB_RED_LR, field);	\
 		gpar = _RB_PARENT_ONLY(gpar);				\
 		RB_UP(child, field) = gpar;				\
 		RB_SWAP_CHILD(head, gpar, parent, child, field);	\
@@ -572,11 +530,12 @@
     struct type *parent, struct type *elm)				\
 {									\
 	struct type *gpar, *sib;					\
-	__uintptr_t red;						\
+	__uintptr_t dir, red;						\
 									\
-	if (RB_LEFT(parent, field) == elm &&				\
-	    RB_RIGHT(parent, field) == elm) {				\
-		RB_BITS(parent, field) &= ~RB_RED_MASK;			\
+	if (elm == NULL &&						\
+	    RB_LEFT(parent, field) == NULL &&				\
+	    RB_RIGHT(parent, field) == NULL) {				\
+		RB_BITS(parent, field) &= ~RB_RED_LR;			\
 		elm = parent;						\
 		parent = RB_PARENT(elm, field);				\
 		if (parent == NULL)					\
@@ -585,106 +544,52 @@
 	do {								\
 		red = RB_BITS(parent, field);				\
 		gpar = RB_UP(parent, field);				\
-		if (RB_LEFT(parent, field) == elm) {			\
-			if (~red & RB_RED_L) {				\
-				RB_FLIP_LEFT(parent, field);		\
-				return;					\
-			}						\
-			if ((~red & RB_RED_MASK) == 0) {		\
-				RB_FLIP_RIGHT(parent, field);		\
-				elm = parent;				\
-				continue;				\
-			}						\
-			sib = RB_RIGHT(parent, field);			\
-			red = RB_BITS(sib, field);			\
-			switch (red & RB_RED_MASK) {			\
-			case RB_RED_MASK:				\
-				RB_FLIP_ALL(sib, field);		\
-				elm = parent;				\
-				continue;				\
-			case RB_RED_R:					\
-				elm = RB_LEFT(sib, field);		\
-				RB_ROTATE_RIGHT(sib, elm, field);	\
-				red = RB_BITS(elm, field);		\
-				if (red & RB_RED_L)			\
-					RB_FLIP_ALL(parent, field);	\
-				else					\
-					RB_FLIP_LEFT(parent, field);	\
-				if (red & RB_RED_R)			\
-					RB_FLIP_ALL(sib, field);	\
-				else					\
-					RB_FLIP_RIGHT(sib, field);	\
-				RB_BITS(elm, field) |= RB_RED_MASK;	\
-				break;					\
-			case RB_RED_L:					\
-				if (RB_STRICT_HST && elm != NULL) {	\
-					RB_FLIP_RIGHT(parent, field);	\
-					RB_FLIP_ALL(sib, field);	\
-					elm = sib;			\
-					break;				\
-				}					\
-				RB_FLIP_LEFT(parent, field);		\
-				/* FALLTHROUGH */			\
-			default:					\
-				RB_FLIP_RIGHT(sib, field);		\
-				elm = sib;				\
-				break;					\
-			}						\
-			RB_ROTATE_LEFT(parent, elm, field);		\
+		dir = RB_LEFT(parent, field) == elm ?			\
+		    RB_RED_L : RB_RED_R;				\
+		if (~red & dir) {					\
+			RB_BITS(parent, field) ^= dir;			\
+			return;						\
+		}							\
+		if ((~red & RB_RED_LR) == 0) {				\
+			RB_BITS(parent, field) ^= dir ^ RB_RED_LR;	\
+			continue;					\
+		}							\
+		sib = RB_LINK(parent, dir ^ RB_RED_LR, field);		\
+		red = RB_BITS(sib, field);				\
+		if ((~red & RB_RED_LR) == 0) {				\
+			RB_FLIP_ALL(sib, field);			\
+			continue;					\
+		}							\
+		if (red & (dir ^ RB_RED_LR)) {				\
+			elm = RB_LINK(sib, dir, field);			\
+			RB_ROTATE(sib, elm, dir ^ RB_RED_LR, field);	\
+			red = RB_BITS(elm, field);			\
+			RB_BITS(parent, field) ^=			\
+			    (red & dir) ? RB_RED_LR : dir;		\
+			RB_BITS(sib, field) ^= RB_RED_LR ^		\
+				((red & (dir ^ RB_RED_LR)) ? 0 : dir);	\
+			RB_BITS(elm, field) |= RB_RED_LR;		\
 		} else {						\
-			if (~red & RB_RED_R) {				\
-				RB_FLIP_RIGHT(parent, field);		\
-				return;					\
-			}						\
-			if ((~red & RB_RED_MASK) == 0) {		\
-				RB_FLIP_LEFT(parent, field);		\
-				elm = parent;				\
-				continue;				\
-			}						\
-			sib = RB_LEFT(parent, field);			\
-			red = RB_BITS(sib, field);			\
-			switch (red & RB_RED_MASK) {			\
-			case RB_RED_MASK:				\
+			if ((red & dir) &&				\
+			    RB_STRICT_HST && elm != NULL) {		\
+				RB_BITS(parent, field) ^= dir ^ RB_RED_LR; \
 				RB_FLIP_ALL(sib, field);		\
-				elm = parent;				\
-				continue;				\
-			case RB_RED_L:					\
-				elm = RB_RIGHT(sib, field);		\
-				RB_ROTATE_LEFT(sib, elm, field);	\
-				red = RB_BITS(elm, field);		\
-				if (red & RB_RED_R)			\
-					RB_FLIP_ALL(parent, field);	\
-				else					\
-					RB_FLIP_RIGHT(parent, field);	\
-				if (red & RB_RED_L)			\
-					RB_FLIP_ALL(sib, field);	\
-				else					\
-					RB_FLIP_LEFT(sib, field);	\
-				RB_BITS(elm, field) |= RB_RED_MASK;	\
-				break;					\
-			case RB_RED_R:					\
-				if (RB_STRICT_HST && elm != NULL) {	\
-					RB_FLIP_LEFT(parent, field);	\
-					RB_FLIP_ALL(sib, field);	\
-					elm = sib;			\
-					break;				\
-				}					\
-				RB_FLIP_RIGHT(parent, field);		\
-				/* FALLTHROUGH */			\
-			default:					\
-				RB_FLIP_LEFT(sib, field);		\
-				elm = sib;				\
-				break;					\
-			}						\
-			RB_ROTATE_RIGHT(parent, elm, field);		\
+			} else if (red & dir) {				\
+				RB_BITS(parent, field) ^= dir;		\
+				RB_BITS(sib, field) ^= dir ^ RB_RED_LR; \
+			} else						\
+				RB_BITS(sib, field) ^= dir ^ RB_RED_LR; \
+			elm = sib;					\
 		}							\
+		RB_ROTATE(parent, elm, dir, field);			\
 		gpar = _RB_PARENT_ONLY(gpar);				\
 		RB_SET_PARENT(elm, gpar, field);			\
 		RB_SWAP_CHILD(head, gpar, parent, elm, field);		\
 		if (sib != elm)						\
 			RB_AUGMENT(sib);				\
 		break;							\
-	} while ((parent = _RB_PARENT_ONLY(gpar)) != NULL);		\
+	} while (elm = parent,						\
+	    (parent = _RB_PARENT_ONLY(gpar)) != NULL);			\
 }
 
 #define RB_GENERATE_REMOVE(name, type, field, attr)			\