Index: sys/sys/tree.h
===================================================================
--- sys/sys/tree.h
+++ sys/sys/tree.h
@@ -416,6 +416,7 @@
 #define	RB_PROTOTYPE_STATIC(name, type, field, cmp)			\
 	RB_PROTOTYPE_INTERNAL(name, type, field, cmp, __unused static)
 #define RB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr)		\
+	RB_PROTOTYPE_RANK(name, type, attr)				\
 	RB_PROTOTYPE_INSERT_COLOR(name, type, attr);			\
 	RB_PROTOTYPE_REMOVE_COLOR(name, type, attr);			\
 	RB_PROTOTYPE_INSERT(name, type, attr);				\
@@ -426,6 +427,12 @@
 	RB_PROTOTYPE_PREV(name, type, attr);				\
 	RB_PROTOTYPE_MINMAX(name, type, attr);				\
 	RB_PROTOTYPE_REINSERT(name, type, attr);
+#ifdef DIAGNOSTIC
+#define RB_PROTOTYPE_RANK(name, type, attr)				\
+	attr int name##_RB_RANK(struct type *);
+#else
+#define RB_PROTOTYPE_RANK(name, type, attr)
+#endif
 #define RB_PROTOTYPE_INSERT_COLOR(name, type, attr)			\
 	attr void name##_RB_INSERT_COLOR(struct name *, struct type *)
 #define RB_PROTOTYPE_REMOVE_COLOR(name, type, attr)			\
@@ -456,6 +463,7 @@
 #define	RB_GENERATE_STATIC(name, type, field, cmp)			\
 	RB_GENERATE_INTERNAL(name, type, field, cmp, __unused static)
 #define RB_GENERATE_INTERNAL(name, type, field, cmp, attr)		\
+	RB_GENERATE_RANK(name, type, field, attr)			\
 	RB_GENERATE_INSERT_COLOR(name, type, field, attr)		\
 	RB_GENERATE_REMOVE_COLOR(name, type, field, attr)		\
 	RB_GENERATE_INSERT(name, type, field, cmp, attr)		\
@@ -467,6 +475,31 @@
 	RB_GENERATE_MINMAX(name, type, field, attr)			\
 	RB_GENERATE_REINSERT(name, type, field, cmp, attr)
 
+#ifdef DIAGNOSTIC
+#define RB_GENERATE_RANK(name, type, field, attr)			\
+attr int								\
+name##_RB_RANK(struct type *elm)					\
+{									\
+	struct type *left, *right;					\
+	int left_rank, right_rank;					\
+	__uintptr bits;							\
+									\
+	if (elm == NULL)						\
+		return (0);						\
+	bits = RB_BITS(elm, field);					\
+	left = RB_LEFT(elm, field);					\
+	left_rank = ((bits & RB_RED_L) ? 2 : 1) + name##RB_RANK(left);	\
+	right = RB_RIGHT(elm, field);					\
+	right_rank = ((bits & RB_RED_R) ? 2 : 1) + name##RB_RANK(right); \
+	if (left_rank != right_rank ||					\
+	    (left_rank == 2 && left == NULL && right == NULL))		\
+		return (-1);						\
+	return (left_rank);						\
+}
+#else
+#define RB_GENERATE_RANK(name, type, field, attr)
+#endif
+
 #define RB_GENERATE_INSERT_COLOR(name, type, field, attr)		\
 attr void								\
 name##_RB_INSERT_COLOR(struct name *head, struct type *elm)		\
Index: tests/sys/sys/Makefile
===================================================================
--- tests/sys/sys/Makefile
+++ tests/sys/sys/Makefile
@@ -16,4 +16,5 @@
 CFLAGS.bitstring_test=	-fno-strict-overflow
 .endif
 
+CFLAGS.rb_test= -DDIAGNOSTIC
 .include <bsd.test.mk>
Index: tests/sys/sys/rb_test.c
===================================================================
--- tests/sys/sys/rb_test.c
+++ tests/sys/sys/rb_test.c
@@ -54,37 +54,47 @@
 RB_GENERATE(tree, node, node, compare);
 
 #define ITER 150
-#define MIN 5
-#define MAX 5000
 
 ATF_TC_WITHOUT_HEAD(rb_test);
 ATF_TC_BODY(rb_test, tc)
 {
-	struct node *tmp, *ins;
-	int i, max, min;
+	struct node *tmp, *ins, store[ITER];
+	int i, j, k, max, min;
 
-	max = min = 42; /* pacify gcc */
+	min = ITER;
+	max = -1;
 
 	RB_INIT(&root);
 
+	/* Initialize keys */
+	for (i = 0; i < ITER; i++)
+		store[i].key = i;
+
+	/* Randomly shuffle keys */
+	for (i = 0; i < ITER; i++) {
+		j = i + arc4random_uniform(ITER - i);
+		k = store[j].key;
+		store[j].key = store[i].key;
+		store[i].key = k;
+	}
+
 	for (i = 0; i < ITER; i++) {
-		tmp = malloc(sizeof(struct node));
-		ATF_REQUIRE_MSG(tmp != NULL, "malloc failed");
-		do {
-			tmp->key = arc4random_uniform(MAX-MIN);
-			tmp->key += MIN;
-		} while (RB_FIND(tree, &root, tmp) != NULL);
-		if (i == 0)
-			max = min = tmp->key;
-		else {
-			if (tmp->key > max)
-				max = tmp->key;
-			if (tmp->key < min)
-				min = tmp->key;
+		for (j = 0; j < i; ++j) {
+			tmp = &store[j];
+			ATF_REQUIRE_EQ(tmp, RB_FIND(tree, &root, tmp));
 		}
+		tmp = &store[i];
+		if (tmp->key > max)
+			max = tmp->key;
+		if (tmp->key < min)
+			min = tmp->key;
 		ATF_REQUIRE_EQ(NULL, RB_INSERT(tree, &root, tmp));
 	}
 
+#ifdef DIAGNOSTIC
+	tmp = RB_ROOT(&root);
+	ATF_REQUIRE_MSG(RB_RANK(tree, tmp) >= 0, "RB rank balance error");
+#endif
 	ins = RB_MIN(tree, &root);
 	ATF_REQUIRE_MSG(ins != NULL, "RB_MIN error");
 	ATF_CHECK_EQ(min, ins->key);
@@ -99,7 +109,6 @@
 		tmp = RB_ROOT(&root);
 		ATF_REQUIRE_MSG(tmp != NULL, "RB_ROOT error");
 		ATF_CHECK_EQ(tmp, RB_REMOVE(tree, &root, tmp));
-		free(tmp);
 	}
 }