diff --git a/sys/compat/linuxkpi/common/include/linux/rbtree.h b/sys/compat/linuxkpi/common/include/linux/rbtree.h
--- a/sys/compat/linuxkpi/common/include/linux/rbtree.h
+++ b/sys/compat/linuxkpi/common/include/linux/rbtree.h
@@ -74,8 +74,11 @@
 #define RB_EMPTY_NODE(node)     (RB_PARENT(node, __entry) == node)
 #define RB_CLEAR_NODE(node)     RB_SET_PARENT(node, node, __entry)
 
-#define	rb_insert_color(node, root)					\
-	linux_root_RB_INSERT_COLOR((struct linux_root *)(root), (node))
+#define rb_insert_color(node, root) do {				\
+	if (rb_parent(node))						\
+		linux_root_RB_INSERT_COLOR((struct linux_root *)(root), \
+		    rb_parent(node), (node));				\
+} while (0)
 #define	rb_erase(node, root)						\
 	linux_root_RB_REMOVE((struct linux_root *)(root), (node))
 #define	rb_next(node)	RB_NEXT(linux_root, NULL, (node))
@@ -145,7 +148,9 @@
 rb_insert_color_cached(struct rb_node *node, struct rb_root_cached *root,
     bool leftmost)
 {
-	linux_root_RB_INSERT_COLOR((struct linux_root *)&root->rb_root, node);
+	if (rb_parent(node))
+		linux_root_RB_INSERT_COLOR((struct linux_root *)&root->rb_root,
+		    rb_parent(node), node);
 	if (leftmost)
 		root->rb_leftmost = node;
 }
diff --git a/sys/sys/tree.h b/sys/sys/tree.h
--- a/sys/sys/tree.h
+++ b/sys/sys/tree.h
@@ -426,7 +426,8 @@
 #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 *)
+	attr void name##_RB_INSERT_COLOR(struct name *,			\
+	    struct type *, struct type *)
 #define RB_PROTOTYPE_REMOVE_COLOR(name, type, attr)			\
 	attr void name##_RB_REMOVE_COLOR(struct name *,			\
 	    struct type *, struct type *)
@@ -495,7 +496,8 @@
 
 #define RB_GENERATE_INSERT_COLOR(name, type, field, attr)		\
 attr void								\
-name##_RB_INSERT_COLOR(struct name *head, struct type *elm)		\
+name##_RB_INSERT_COLOR(struct name *head,				\
+    struct type *parent, struct type *elm)				\
 {									\
 	/*								\
 	 * Initially, elm is a leaf.  Either its parent was previously	\
@@ -507,12 +509,11 @@
 	 * uninitialized 'child', and a later iteration can only happen \
 	 * when a value has been assigned to 'child' in the previous    \
 	 * one.								\
-	 */							\
-	struct type *child, *child_up, *gpar, *parent;			\
+	 */								\
+	struct type *child, *child_up, *gpar;				\
 	__uintptr_t elmdir, sibdir;					\
 									\
-	gpar = _RB_UP(elm, field);					\
-	while ((parent = gpar) != NULL) {				\
+	do {								\
 		/* the rank of the tree rooted at elm grew */		\
 		gpar = _RB_UP(parent, field);				\
 		elmdir = RB_RIGHT(parent, field) == elm ? _RB_R : _RB_L; \
@@ -588,7 +589,7 @@
 			RB_AUGMENT(elm);				\
 		RB_AUGMENT(parent);					\
 		break;							\
-	}								\
+	} while ((parent = gpar) != NULL);				\
 }
 
 #ifndef RB_STRICT_HST
@@ -778,7 +779,8 @@
 	}								\
 	RB_SET(elm, parent, field);					\
 	*tmpp = elm;							\
-	name##_RB_INSERT_COLOR(head, elm);				\
+	if (parent != NULL)						\
+		name##_RB_INSERT_COLOR(head, parent, elm);		\
 	RB_UPDATE_AUGMENT(elm, field);					\
 	return (NULL);							\
 }