[PATCH] Shrink rbtree

[PATCH] Shrink rbtree

[David Woodhouse]

Our rbtree implementation uses a whole integer for colour information.
In fact, because of alignment constraints on a 64-bit machine it'll be a
whole 64 bits there. We only need a single bit, though -- and we know
the pointers are always going to be aligned. So let's just use the
lowest bit of the parent pointer instead. This shrinks the rb_node from
4 machine-words to 3.

This doesn't change the documented mode of using rbtrees -- users
weren't encouraged to use the parent pointers directly anyway. But we
add new accessor macros rb_parent(), rb_is_red() etc. and a few places
do need changing to use them.

Some users were just abusing the colour to mark a node as being
off-tree, and I've switched those to use same method for that as
eventpoll.c does -- setting the parent pointer to point to itself.

There's also an obvious optimisation to rb_erase() which jumped out at
me while I was passing.

Full patch below -- individual changes are in a git tree at
git://git.infradead.org/~dwmw2/rbtree-2.6 or viewable by gitweb at
http://git.infradead.org/?p=users/dwmw2/rbtree-2.6.git

    [RBTREE] Merge colour and parent fields of struct rb_node.
    [RBTREE] Remove dead code in rb_erase()
    [RBTREE] Update JFFS2 to use rb_parent() accessor macro.
    [RBTREE] Update eventpoll.c to use rb_parent() accessor macro.
    [RBTREE] Update key.c to use rb_parent() accessor macro.
    [RBTREE] Update ext3 to use rb_parent() accessor macro.
    [RBTREE] Change rbtree off-tree marking in I/O schedulers.
    [RBTREE] Add accessor macros for colour and parent fields of rb_node

Another pair of eyes on the 'remove dead code in rb_erase()' bit in
particular would be appreciated. That's
http://git.infradead.org/?p=users/dwmw2/rbtree-2.6.git;a=commitdiff;h=1975e59375756da4ff4e6e7d12f67485e813ace0

diff --git a/block/as-iosched.c b/block/as-iosched.c
index e25a5d7..ed336ab 100644
--- a/block/as-iosched.c
+++ b/block/as-iosched.c
@@ -353,10 +353,9 @@ static struct request *as_find_arq_hash(
 /*
  * rb tree support functions
  */
-#define RB_NONE		(2)
 #define RB_EMPTY(root)	((root)->rb_node == NULL)
-#define ON_RB(node)	((node)->rb_color != RB_NONE)
-#define RB_CLEAR(node)	((node)->rb_color = RB_NONE)
+#define ON_RB(node)	(rb_parent(node) != node)
+#define RB_CLEAR(node)	(rb_set_parent(node, node))
 #define rb_entry_arq(node)	rb_entry((node), struct as_rq, rb_node)
 #define ARQ_RB_ROOT(ad, arq)	(&(ad)->sort_list[(arq)->is_sync])
 #define rq_rb_key(rq)		(rq)->sector
diff --git a/block/cfq-iosched.c b/block/cfq-iosched.c
index 2540dfa..01c416b 100644
--- a/block/cfq-iosched.c
+++ b/block/cfq-iosched.c
@@ -60,14 +60,9 @@ #define RQ_DATA(rq)		(rq)->elevator_priv
 /*
  * rb-tree defines
  */
-#define RB_NONE			(2)
 #define RB_EMPTY(node)		((node)->rb_node == NULL)
-#define RB_CLEAR_COLOR(node)	(node)->rb_color = RB_NONE
 #define RB_CLEAR(node)		do {	\
-	(node)->rb_parent = NULL;	\
-	RB_CLEAR_COLOR((node));		\
-	(node)->rb_right = NULL;	\
-	(node)->rb_left = NULL;		\
+		memset(node, 0, sizeof(*node)); \
 } while (0)
 #define RB_CLEAR_ROOT(root)	((root)->rb_node = NULL)
 #define rb_entry_crq(node)	rb_entry((node), struct cfq_rq, rb_node)
@@ -563,7 +558,6 @@ static inline void cfq_del_crq_rb(struct
 	cfq_update_next_crq(crq);
 
 	rb_erase(&crq->rb_node, &cfqq->sort_list);
-	RB_CLEAR_COLOR(&crq->rb_node);
 
 	if (cfq_cfqq_on_rr(cfqq) && RB_EMPTY(&cfqq->sort_list))
 		cfq_del_cfqq_rr(cfqd, cfqq);
diff --git a/block/deadline-iosched.c b/block/deadline-iosched.c
index 399fa1e..06962d8 100644
--- a/block/deadline-iosched.c
+++ b/block/deadline-iosched.c
@@ -165,10 +165,9 @@ deadline_find_drq_hash(struct deadline_d
 /*
  * rb tree support functions
  */
-#define RB_NONE		(2)
 #define RB_EMPTY(root)	((root)->rb_node == NULL)
-#define ON_RB(node)	((node)->rb_color != RB_NONE)
-#define RB_CLEAR(node)	((node)->rb_color = RB_NONE)
+#define ON_RB(node)	(rb_parent(node) != node)
+#define RB_CLEAR(node)	(rb_set_parent(node, node))
 #define rb_entry_drq(node)	rb_entry((node), struct deadline_rq, rb_node)
 #define DRQ_RB_ROOT(dd, drq)	(&(dd)->sort_list[rq_data_dir((drq)->request)])
 #define rq_rb_key(rq)		(rq)->sector
diff --git a/fs/eventpoll.c b/fs/eventpoll.c
index 1b4491c..2695337 100644
--- a/fs/eventpoll.c
+++ b/fs/eventpoll.c
@@ -337,20 +337,20 @@ static inline int ep_cmp_ffd(struct epol
 /* Special initialization for the rb-tree node to detect linkage */
 static inline void ep_rb_initnode(struct rb_node *n)
 {
-	n->rb_parent = n;
+	rb_set_parent(n, n);
 }
 
 /* Removes a node from the rb-tree and marks it for a fast is-linked check */
 static inline void ep_rb_erase(struct rb_node *n, struct rb_root *r)
 {
 	rb_erase(n, r);
-	n->rb_parent = n;
+	rb_set_parent(n, n);
 }
 
 /* Fast check to verify that the item is linked to the main rb-tree */
 static inline int ep_rb_linked(struct rb_node *n)
 {
-	return n->rb_parent != n;
+	return rb_parent(n) != n;
 }
 
 /*
diff --git a/fs/ext3/dir.c b/fs/ext3/dir.c
index f37528e..fbb0d4e 100644
--- a/fs/ext3/dir.c
+++ b/fs/ext3/dir.c
@@ -284,7 +284,7 @@ static void free_rb_tree_fname(struct rb
 		 * beginning of the loop and try to free the parent
 		 * node.
 		 */
-		parent = n->rb_parent;
+		parent = rb_parent(n);
 		fname = rb_entry(n, struct fname, rb_hash);
 		while (fname) {
 			struct fname * old = fname;
diff --git a/fs/jffs2/nodelist.h b/fs/jffs2/nodelist.h
index 23a67bb..131b67b 100644
--- a/fs/jffs2/nodelist.h
+++ b/fs/jffs2/nodelist.h
@@ -299,7 +299,6 @@ static inline struct jffs2_node_frag *fr
 	return rb_entry(node, struct jffs2_node_frag, rb);
 }
 
-#define rb_parent(rb) ((rb)->rb_parent)
 #define frag_next(frag) rb_entry(rb_next(&(frag)->rb), struct jffs2_node_frag, rb)
 #define frag_prev(frag) rb_entry(rb_prev(&(frag)->rb), struct jffs2_node_frag, rb)
 #define frag_parent(frag) rb_entry(rb_parent(&(frag)->rb), struct jffs2_node_frag, rb)
diff --git a/fs/jffs2/readinode.c b/fs/jffs2/readinode.c
index f169564..6f4a7d8 100644
--- a/fs/jffs2/readinode.c
+++ b/fs/jffs2/readinode.c
@@ -66,7 +66,7 @@ static void jffs2_free_tmp_dnode_info_li
 			jffs2_free_full_dnode(tn->fn);
 			jffs2_free_tmp_dnode_info(tn);
 
-			this = this->rb_parent;
+			this = rb_parent(this);
 			if (!this)
 				break;
 
@@ -679,12 +679,12 @@ static int jffs2_do_read_inode_internal(
 			jffs2_mark_node_obsolete(c, fn->raw);
 
 		BUG_ON(rb->rb_left);
-		if (rb->rb_parent && rb->rb_parent->rb_left == rb) {
+		if (rb_parent(rb) && rb_parent(rb)->rb_left == rb) {
 			/* We were then left-hand child of our parent. We need
 			 * to move our own right-hand child into our place. */
 			repl_rb = rb->rb_right;
 			if (repl_rb)
-				repl_rb->rb_parent = rb->rb_parent;
+				rb_set_parent(repl_rb, rb_parent(rb));
 		} else
 			repl_rb = NULL;
 
@@ -692,14 +692,14 @@ static int jffs2_do_read_inode_internal(
 
 		/* Remove the spent tn from the tree; don't bother rebalancing
 		 * but put our right-hand child in our own place. */
-		if (tn->rb.rb_parent) {
-			if (tn->rb.rb_parent->rb_left == &tn->rb)
-				tn->rb.rb_parent->rb_left = repl_rb;
-			else if (tn->rb.rb_parent->rb_right == &tn->rb)
-				tn->rb.rb_parent->rb_right = repl_rb;
+		if (rb_parent(&tn->rb)) {
+			if (rb_parent(&tn->rb)->rb_left == &tn->rb)
+				rb_parent(&tn->rb)->rb_left = repl_rb;
+			else if (rb_parent(&tn->rb)->rb_right == &tn->rb)
+				rb_parent(&tn->rb)->rb_right = repl_rb;
 			else BUG();
 		} else if (tn->rb.rb_right)
-			tn->rb.rb_right->rb_parent = NULL;
+			rb_set_parent(tn->rb.rb_right, NULL);
 
 		jffs2_free_tmp_dnode_info(tn);
 		if (ret) {
diff --git a/include/linux/rbtree.h b/include/linux/rbtree.h
index 4b7cc4f..748be50 100644
--- a/include/linux/rbtree.h
+++ b/include/linux/rbtree.h
@@ -99,8 +99,7 @@ #include <linux/stddef.h>
 
 struct rb_node
 {
-	struct rb_node *rb_parent;
-	int rb_color;
+	unsigned long  rb_parent_colour;
 #define	RB_RED		0
 #define	RB_BLACK	1
 	struct rb_node *rb_right;
@@ -112,6 +111,23 @@ struct rb_root
 	struct rb_node *rb_node;
 };
 
+
+#define rb_parent(r)   ((struct rb_node *)((r)->rb_parent_colour & ~3))
+#define rb_colour(r)   ((r)->rb_parent_colour & 1)
+#define rb_is_red(r)   (!rb_colour(r))
+#define rb_is_black(r) rb_colour(r)
+#define rb_set_red(r)  do { (r)->rb_parent_colour &= ~1; } while (0)
+#define rb_set_black(r)  do { (r)->rb_parent_colour |= 1; } while (0)
+
+static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p)
+{
+	rb->rb_parent_colour = (rb->rb_parent_colour & 3) | (unsigned long)p;
+}
+static inline void rb_set_colour(struct rb_node *rb, int colour)
+{
+	rb->rb_parent_colour = (rb->rb_parent_colour & ~1) | colour;
+}
+
 #define RB_ROOT	(struct rb_root) { NULL, }
 #define	rb_entry(ptr, type, member) container_of(ptr, type, member)
 
@@ -131,8 +147,7 @@ extern void rb_replace_node(struct rb_no
 static inline void rb_link_node(struct rb_node * node, struct rb_node * parent,
 				struct rb_node ** rb_link)
 {
-	node->rb_parent = parent;
-	node->rb_color = RB_RED;
+	node->rb_parent_colour = (unsigned long )parent;
 	node->rb_left = node->rb_right = NULL;
 
 	*rb_link = node;
diff --git a/lib/rbtree.c b/lib/rbtree.c
index 14b791a..4a7173c 100644
--- a/lib/rbtree.c
+++ b/lib/rbtree.c
@@ -26,60 +26,66 @@ #include <linux/module.h>
 static void __rb_rotate_left(struct rb_node *node, struct rb_root *root)
 {
 	struct rb_node *right = node->rb_right;
+	struct rb_node *parent = rb_parent(node);
 
 	if ((node->rb_right = right->rb_left))
-		right->rb_left->rb_parent = node;
+		rb_set_parent(right->rb_left, node);
 	right->rb_left = node;
 
-	if ((right->rb_parent = node->rb_parent))
+	rb_set_parent(right, parent);
+
+	if (parent)
 	{
-		if (node == node->rb_parent->rb_left)
-			node->rb_parent->rb_left = right;
+		if (node == parent->rb_left)
+			parent->rb_left = right;
 		else
-			node->rb_parent->rb_right = right;
+			parent->rb_right = right;
 	}
 	else
 		root->rb_node = right;
-	node->rb_parent = right;
+	rb_set_parent(node, right);
 }
 
 static void __rb_rotate_right(struct rb_node *node, struct rb_root *root)
 {
 	struct rb_node *left = node->rb_left;
+	struct rb_node *parent = rb_parent(node);
 
 	if ((node->rb_left = left->rb_right))
-		left->rb_right->rb_parent = node;
+		rb_set_parent(left->rb_right, node);
 	left->rb_right = node;
 
-	if ((left->rb_parent = node->rb_parent))
+	rb_set_parent(left, parent);
+
+	if (parent)
 	{
-		if (node == node->rb_parent->rb_right)
-			node->rb_parent->rb_right = left;
+		if (node == parent->rb_right)
+			parent->rb_right = left;
 		else
-			node->rb_parent->rb_left = left;
+			parent->rb_left = left;
 	}
 	else
 		root->rb_node = left;
-	node->rb_parent = left;
+	rb_set_parent(node, left);
 }
 
 void rb_insert_color(struct rb_node *node, struct rb_root *root)
 {
 	struct rb_node *parent, *gparent;
 
-	while ((parent = node->rb_parent) && parent->rb_color == RB_RED)
+	while ((parent = rb_parent(node)) && rb_is_red(parent))
 	{
-		gparent = parent->rb_parent;
+		gparent = rb_parent(parent);
 
 		if (parent == gparent->rb_left)
 		{
 			{
 				register struct rb_node *uncle = gparent->rb_right;
-				if (uncle && uncle->rb_color == RB_RED)
+				if (uncle && rb_is_red(uncle))
 				{
-					uncle->rb_color = RB_BLACK;
-					parent->rb_color = RB_BLACK;
-					gparent->rb_color = RB_RED;
+					rb_set_black(uncle);
+					rb_set_black(parent);
+					rb_set_red(gparent);
 					node = gparent;
 					continue;
 				}
@@ -94,17 +100,17 @@ void rb_insert_color(struct rb_node *nod
 				node = tmp;
 			}
 
-			parent->rb_color = RB_BLACK;
-			gparent->rb_color = RB_RED;
+			rb_set_black(parent);
+			rb_set_red(gparent);
 			__rb_rotate_right(gparent, root);
 		} else {
 			{
 				register struct rb_node *uncle = gparent->rb_left;
-				if (uncle && uncle->rb_color == RB_RED)
+				if (uncle && rb_is_red(uncle))
 				{
-					uncle->rb_color = RB_BLACK;
-					parent->rb_color = RB_BLACK;
-					gparent->rb_color = RB_RED;
+					rb_set_black(uncle);
+					rb_set_black(parent);
+					rb_set_red(gparent);
 					node = gparent;
 					continue;
 				}
@@ -119,13 +125,13 @@ void rb_insert_color(struct rb_node *nod
 				node = tmp;
 			}
 
-			parent->rb_color = RB_BLACK;
-			gparent->rb_color = RB_RED;
+			rb_set_black(parent);
+			rb_set_red(gparent);
 			__rb_rotate_left(gparent, root);
 		}
 	}
 
-	root->rb_node->rb_color = RB_BLACK;
+	rb_set_black(root->rb_node);
 }
 EXPORT_SYMBOL(rb_insert_color);
 
@@ -134,43 +140,40 @@ static void __rb_erase_color(struct rb_n
 {
 	struct rb_node *other;
 
-	while ((!node || node->rb_color == RB_BLACK) && node != root->rb_node)
+	while ((!node || rb_is_black(node)) && node != root->rb_node)
 	{
 		if (parent->rb_left == node)
 		{
 			other = parent->rb_right;
-			if (other->rb_color == RB_RED)
+			if (rb_is_red(other))
 			{
-				other->rb_color = RB_BLACK;
-				parent->rb_color = RB_RED;
+				rb_set_black(other);
+				rb_set_red(parent);
 				__rb_rotate_left(parent, root);
 				other = parent->rb_right;
 			}
-			if ((!other->rb_left ||
-			     other->rb_left->rb_color == RB_BLACK)
-			    && (!other->rb_right ||
-				other->rb_right->rb_color == RB_BLACK))
+			if ((!other->rb_left || rb_is_black(other->rb_left)) &&
+			    (!other->rb_right || rb_is_black(other->rb_right)))
 			{
-				other->rb_color = RB_RED;
+				rb_set_red(other);
 				node = parent;
-				parent = node->rb_parent;
+				parent = rb_parent(node);
 			}
 			else
 			{
-				if (!other->rb_right ||
-				    other->rb_right->rb_color == RB_BLACK)
+				if (!other->rb_right || rb_is_black(other->rb_right))
 				{
-					register struct rb_node *o_left;
+					struct rb_node *o_left;
 					if ((o_left = other->rb_left))
-						o_left->rb_color = RB_BLACK;
-					other->rb_color = RB_RED;
+						rb_set_black(o_left);
+					rb_set_red(other);
 					__rb_rotate_right(other, root);
 					other = parent->rb_right;
 				}
-				other->rb_color = parent->rb_color;
-				parent->rb_color = RB_BLACK;
+				rb_set_colour(other, rb_colour(parent));
+				rb_set_black(parent);
 				if (other->rb_right)
-					other->rb_right->rb_color = RB_BLACK;
+					rb_set_black(other->rb_right);
 				__rb_rotate_left(parent, root);
 				node = root->rb_node;
 				break;
@@ -179,38 +182,35 @@ static void __rb_erase_color(struct rb_n
 		else
 		{
 			other = parent->rb_left;
-			if (other->rb_color == RB_RED)
+			if (rb_is_red(other))
 			{
-				other->rb_color = RB_BLACK;
-				parent->rb_color = RB_RED;
+				rb_set_black(other);
+				rb_set_red(parent);
 				__rb_rotate_right(parent, root);
 				other = parent->rb_left;
 			}
-			if ((!other->rb_left ||
-			     other->rb_left->rb_color == RB_BLACK)
-			    && (!other->rb_right ||
-				other->rb_right->rb_color == RB_BLACK))
+			if ((!other->rb_left || rb_is_black(other->rb_left)) &&
+			    (!other->rb_right || rb_is_black(other->rb_right)))
 			{
-				other->rb_color = RB_RED;
+				rb_set_red(other);
 				node = parent;
-				parent = node->rb_parent;
+				parent = rb_parent(node);
 			}
 			else
 			{
-				if (!other->rb_left ||
-				    other->rb_left->rb_color == RB_BLACK)
+				if (!other->rb_left || rb_is_black(other->rb_left))
 				{
 					register struct rb_node *o_right;
 					if ((o_right = other->rb_right))
-						o_right->rb_color = RB_BLACK;
-					other->rb_color = RB_RED;
+						rb_set_black(o_right);
+					rb_set_red(other);
 					__rb_rotate_left(other, root);
 					other = parent->rb_left;
 				}
-				other->rb_color = parent->rb_color;
-				parent->rb_color = RB_BLACK;
+				rb_set_colour(other, rb_colour(parent));
+				rb_set_black(parent);
 				if (other->rb_left)
-					other->rb_left->rb_color = RB_BLACK;
+					rb_set_black(other->rb_left);
 				__rb_rotate_right(parent, root);
 				node = root->rb_node;
 				break;
@@ -218,7 +218,7 @@ static void __rb_erase_color(struct rb_n
 		}
 	}
 	if (node)
-		node->rb_color = RB_BLACK;
+		rb_set_black(node);
 }
 
 void rb_erase(struct rb_node *node, struct rb_root *root)
@@ -238,48 +238,41 @@ void rb_erase(struct rb_node *node, stru
 		while ((left = node->rb_left) != NULL)
 			node = left;
 		child = node->rb_right;
-		parent = node->rb_parent;
-		color = node->rb_color;
+		parent = rb_parent(node);
+		color = rb_colour(node);
 
 		if (child)
-			child->rb_parent = parent;
-		if (parent)
-		{
-			if (parent->rb_left == node)
-				parent->rb_left = child;
-			else
-				parent->rb_right = child;
-		}
-		else
-			root->rb_node = child;
-
-		if (node->rb_parent == old)
+			rb_set_parent(child, parent);
+		if (parent == old) {
+			parent->rb_right = child;
 			parent = node;
-		node->rb_parent = old->rb_parent;
-		node->rb_color = old->rb_color;
+		} else
+			parent->rb_left = child;
+
+		node->rb_parent_colour = old->rb_parent_colour;
 		node->rb_right = old->rb_right;
 		node->rb_left = old->rb_left;
 
-		if (old->rb_parent)
+		if (rb_parent(old))
 		{
-			if (old->rb_parent->rb_left == old)
-				old->rb_parent->rb_left = node;
+			if (rb_parent(old)->rb_left == old)
+				rb_parent(old)->rb_left = node;
 			else
-				old->rb_parent->rb_right = node;
+				rb_parent(old)->rb_right = node;
 		} else
 			root->rb_node = node;
 
-		old->rb_left->rb_parent = node;
+		rb_set_parent(old->rb_left, node);
 		if (old->rb_right)
-			old->rb_right->rb_parent = node;
+			rb_set_parent(old->rb_right, node);
 		goto color;
 	}
 
-	parent = node->rb_parent;
-	color = node->rb_color;
+	parent = rb_parent(node);
+	color = rb_colour(node);
 
 	if (child)
-		child->rb_parent = parent;
+		rb_set_parent(child, parent);
 	if (parent)
 	{
 		if (parent->rb_left == node)
@@ -327,6 +320,8 @@ EXPORT_SYMBOL(rb_last);
 
 struct rb_node *rb_next(struct rb_node *node)
 {
+	struct rb_node *parent;
+
 	/* If we have a right-hand child, go down and then left as far
 	   as we can. */
 	if (node->rb_right) {
@@ -342,15 +337,17 @@ struct rb_node *rb_next(struct rb_node *
 	   ancestor is a right-hand child of its parent, keep going
 	   up. First time it's a left-hand child of its parent, said
 	   parent is our 'next' node. */
-	while (node->rb_parent && node == node->rb_parent->rb_right)
-		node = node->rb_parent;
+	while ((parent = rb_parent(node)) && node == parent->rb_right)
+		node = parent;
 
-	return node->rb_parent;
+	return parent;
 }
 EXPORT_SYMBOL(rb_next);
 
 struct rb_node *rb_prev(struct rb_node *node)
 {
+	struct rb_node *parent;
+
 	/* If we have a left-hand child, go down and then right as far
 	   as we can. */
 	if (node->rb_left) {
@@ -362,17 +359,17 @@ struct rb_node *rb_prev(struct rb_node *
 
 	/* No left-hand children. Go up till we find an ancestor which
 	   is a right-hand child of its parent */
-	while (node->rb_parent && node == node->rb_parent->rb_left)
-		node = node->rb_parent;
+	while ((parent = rb_parent(node)) && node == parent->rb_left)
+		node = parent;
 
-	return node->rb_parent;
+	return parent;
 }
 EXPORT_SYMBOL(rb_prev);
 
 void rb_replace_node(struct rb_node *victim, struct rb_node *new,
 		     struct rb_root *root)
 {
-	struct rb_node *parent = victim->rb_parent;
+	struct rb_node *parent = rb_parent(victim);
 
 	/* Set the surrounding nodes to point to the replacement */
 	if (parent) {
@@ -384,9 +381,9 @@ void rb_replace_node(struct rb_node *vic
 		root->rb_node = new;
 	}
 	if (victim->rb_left)
-		victim->rb_left->rb_parent = new;
+		rb_set_parent(victim->rb_left, new);
 	if (victim->rb_right)
-		victim->rb_right->rb_parent = new;
+		rb_set_parent(victim->rb_right, new);
 
 	/* Copy the pointers/colour from the victim to the replacement */
 	*new = *victim;
diff --git a/security/keys/key.c b/security/keys/key.c
index b6061fa..3fdc49c 100644
--- a/security/keys/key.c
+++ b/security/keys/key.c
@@ -211,12 +211,12 @@ static inline void key_alloc_serial(stru
 			key->serial = 2;
 		key_serial_next = key->serial + 1;
 
-		if (!parent->rb_parent)
+		if (!rb_parent(parent))
 			p = &key_serial_tree.rb_node;
-		else if (parent->rb_parent->rb_left == parent)
-			p = &parent->rb_parent->rb_left;
+		else if (rb_parent(parent)->rb_left == parent)
+			p = &(rb_parent(parent)->rb_left);
 		else
-			p = &parent->rb_parent->rb_right;
+			p = &(rb_parent(parent)->rb_right);
 
 		parent = rb_next(parent);
 		if (!parent)


-- 
dwmw2

Re: [PATCH] Shrink rbtree

[Nick Piggin]

Hi David,

Doesn't seem like a bad idea...

David Woodhouse wrote:
> Our rbtree implementation uses a whole integer for colour information.
> In fact, because of alignment constraints on a 64-bit machine it'll be a
> whole 64 bits there. We only need a single bit, though -- and we know
> the pointers are always going to be aligned. So let's just use the

How do we know the pointers are always going to be aligned? IIRC
struct address_space needed to be explicitly aligned when doing
this trick in page->mapping because some platform byte aligned it.

Nick

-- 
SUSE Labs, Novell Inc.
Send instant messages to your online friends http://au.messenger.yahoo.com 

Re: [PATCH] Shrink rbtree

[David Woodhouse]

On Fri, 2006-04-21 at 23:06 +1000, Nick Piggin wrote:
> How do we know the pointers are always going to be aligned? IIRC
> struct address_space needed to be explicitly aligned when doing
> this trick in page->mapping because some platform byte aligned it.

Really? I've been doing this kind of trick with the jffs2_raw_node_ref
for years. We always allocate sufficiently aligned objects.

-- 
dwmw2

Re: [PATCH] Shrink rbtree

[Hugh Dickins]

On Fri, 21 Apr 2006, David Woodhouse wrote:
> On Fri, 2006-04-21 at 23:06 +1000, Nick Piggin wrote:
> > How do we know the pointers are always going to be aligned? IIRC
> > struct address_space needed to be explicitly aligned when doing
> > this trick in page->mapping because some platform byte aligned it.
> 
> Really? I've been doing this kind of trick with the jffs2_raw_node_ref
> for years. We always allocate sufficiently aligned objects.

} __attribute__((aligned(sizeof(long))));
	/*
	 * On most architectures that alignment is already the case; but
	 * must be enforced here for CRIS, to let the least signficant bit
	 * of struct page's "mapping" pointer be used for PAGE_MAPPING_ANON.
	 */

You can often get away with it - I notice we never added the same
alignment to struct anon_vma, which in theory needed it just as much.
Some accident of how structures are packed into slabs on CRIS, I suppose.

Hugh

Re: [PATCH] Shrink rbtree

[David Woodhouse]

On Fri, 2006-04-21 at 21:57 +0100, Hugh Dickins wrote:
> 
> } __attribute__((aligned(sizeof(long))));
>         /*
>          * On most architectures that alignment is already the case; but
>          * must be enforced here for CRIS, to let the least signficant bit
>          * of struct page's "mapping" pointer be used for PAGE_MAPPING_ANON.
>          */
> 
> You can often get away with it - I notice we never added the same
> alignment to struct anon_vma, which in theory needed it just as much.
> Some accident of how structures are packed into slabs on CRIS, I suppose.

That sounds very strange to me, but it's harmless enough to add the
explicit alignment.

-- 
dwmw2

Re: [PATCH] Shrink rbtree

[Hugh Dickins]

On Fri, 21 Apr 2006, David Woodhouse wrote:
> On Fri, 2006-04-21 at 21:57 +0100, Hugh Dickins wrote:
> > 
> > You can often get away with it - I notice we never added the same
> > alignment to struct anon_vma, which in theory needed it just as much.
> > Some accident of how structures are packed into slabs on CRIS, I suppose.
> 
> That sounds very strange to me, but it's harmless enough to add the
> explicit alignment.

It's occurred to me that the unusual thing about struct address_space
is that it does _not_ have a slab cache of its own: it's for years been
part of the struct inode itself; and I guess that exposes it to an
alignment issue which slab objects themselves avoid.  But still a
good idea to add the explicit alignment as doc.

Hugh

Re: [PATCH] Shrink rbtree

[Zach Brown]

> the pointers are always going to be aligned. So let's just use the
> lowest bit of the parent pointer instead. This shrinks the rb_node from
> 4 machine-words to 3.

We've seen this patch before, haven't we? :)  I still like it.

> Another pair of eyes on the 'remove dead code in rb_erase()' bit in
> particular would be appreciated.

I'll trade you some eyes for a description beyond the four words
obvious, remove, dead, and code.

>  struct rb_node
>  {
> -	struct rb_node *rb_parent;
> -	int rb_color;
> +	unsigned long  rb_parent_colour;

How about some kerneldoc comments?

>  #define	RB_RED		0
>  #define	RB_BLACK	1

> +#define rb_colour(r)   ((r)->rb_parent_colour & 1)

This creates a pretty strong bond between the two.. maybe a
RB_COLOUR_MASK and use that and the _RED/_BLACK defines instead of the
raw constants?

> +#define rb_is_red(r)   (!rb_colour(r))
> +#define rb_is_black(r) rb_colour(r)
> +#define rb_set_red(r)  do { (r)->rb_parent_colour &= ~1; } while (0)
> +#define rb_set_black(r)  do { (r)->rb_parent_colour |= 1; } while (0)
> +
> +static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p)
> +{

	BUG_ON((unsigned long)p & 3);

> +	rb->rb_parent_colour = (rb->rb_parent_colour & 3) | (unsigned long)p;
> +}
> +static inline void rb_set_colour(struct rb_node *rb, int colour)
> +{
> +	rb->rb_parent_colour = (rb->rb_parent_colour & ~1) | colour;
> +}
> +
>  #define RB_ROOT	(struct rb_root) { NULL, }
>  #define	rb_entry(ptr, type, member) container_of(ptr, type, member)
>  
> @@ -131,8 +147,7 @@ extern void rb_replace_node(struct rb_no
>  static inline void rb_link_node(struct rb_node * node, struct rb_node * parent,
>  				struct rb_node ** rb_link)
>  {
> -	node->rb_parent = parent;
> -	node->rb_color = RB_RED;
> +	node->rb_parent_colour = (unsigned long )parent;

use rb_set_parent(node, parent) and get the assertion.

- z

Re: [PATCH] Shrink rbtree

[David Woodhouse]

On Fri, 2006-04-21 at 11:24 -0700, Zach Brown wrote:
> > the pointers are always going to be aligned. So let's just use the
> > lowest bit of the parent pointer instead. This shrinks the rb_node from
> > 4 machine-words to 3.
> 
> We've seen this patch before, haven't we? :)  I still like it.

Maybe. I thought I'd actually done it once before, but I couldn't
actually find it when I went looking. It should save about 40KiB of RAM
on my Nokia 770, because I should get 145 jffs2_node_frag objects in
each slab page instead of only 127 -- so yes, I like it too :)

> > Another pair of eyes on the 'remove dead code in rb_erase()' bit in
> > particular would be appreciated.
> 
> I'll trade you some eyes for a description beyond the four words
> obvious, remove, dead, and code.

Plenty more words in the git commit. They don't make much sense without
the patch right below them, and you can see them in juxtaposition at 
http://git.infradead.org/?p=users/dwmw2/rbtree-2.6.git;a=commitdiff;h=1975e59375756da4ff4e6e7d12f67485e813ace0

> >  #define	RB_RED		0
> >  #define	RB_BLACK	1
> 
> > +#define rb_colour(r)   ((r)->rb_parent_colour & 1)
> 
> This creates a pretty strong bond between the two.. maybe a
> RB_COLOUR_MASK and use that and the _RED/_BLACK defines instead of the
> raw constants?

I think it's be better just to drop the RB_RED and RB_BLACK definitions.

> > +static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p)
> > +{
> 
> 	BUG_ON((unsigned long)p & 3);

Yeah, I suppose we could.
> > @@ -131,8 +147,7 @@ extern void rb_replace_node(struct rb_no
> >  static inline void rb_link_node(struct rb_node * node, struct rb_node * parent,
> >  				struct rb_node ** rb_link)
> >  {
> > -	node->rb_parent = parent;
> > -	node->rb_color = RB_RED;
> > +	node->rb_parent_colour = (unsigned long )parent;
> 
> use rb_set_parent(node, parent) and get the assertion.

Que?

-- 
dwmw2

Re: [PATCH] Shrink rbtree

[Zach Brown]

> Maybe. I thought I'd actually done it once before, but I couldn't
> actually find it when I went looking.

Yeah, that's what I remember too.

> Plenty more words in the git commit.

Ah!  of course, thanks.

> They don't make much sense without
> the patch right below them, and you can see them in juxtaposition at 
> http://git.infradead.org/?p=users/dwmw2/rbtree-2.6.git;a=commitdiff;h=1975e59375756da4ff4e6e7d12f67485e813ace0

Indeed, that reasoning looks sound.  First the if (parent) .. else {}
falls away, then the parent left/right relationship is folded into the
test with old.  Looks good.

> I think it's be better just to drop the RB_RED and RB_BLACK definitions.

I'd agree, I figured you'd left them for a reason.

>>> +static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p)
>>> +{
>> 	BUG_ON((unsigned long)p & 3);
> 
> Yeah, I suppose we could.

>>> +	node->rb_parent_colour = (unsigned long )parent;
>> use rb_set_parent(node, parent) and get the assertion.
> 
> Que?

I meant that if we add the BUG_ON() to rb_set_parent() then we might as
well reuse it here..

- z

Re: [PATCH] Shrink rbtree

[Andrew Morton]

David Woodhouse <dwmw2@infradead.org> wrote:
>
> git://git.infradead.org/~dwmw2/rbtree-2.6

include/linux/hrtimer.h: In function `hrtimer_active':
include/linux/hrtimer.h:130: structure has no member named `rb_parent'

Might I cast aspersions upon the quality of your testing?



#define HRTIMER_INACTIVE	((void *)1UL)

...

static inline int hrtimer_active(const struct hrtimer *timer)
{
	return rb_parent(timer->node) != HRTIMER_INACTIVE;
}


So we have somewhat-competing hackery here.

Testing this...

--- devel/include/linux/hrtimer.h~git-rbtree-hrtimer-fix	2006-04-21 18:03:44.000000000 -0700
+++ devel-akpm/include/linux/hrtimer.h	2006-04-21 18:08:02.000000000 -0700
@@ -34,7 +34,7 @@ enum hrtimer_restart {
 	HRTIMER_RESTART,
 };
 
-#define HRTIMER_INACTIVE	((void *)1UL)
+#define HRTIMER_INACTIVE	((void *)-2)
 
 struct hrtimer_base;
 
@@ -127,7 +127,7 @@ extern ktime_t hrtimer_get_next_event(vo
 
 static inline int hrtimer_active(const struct hrtimer *timer)
 {
-	return timer->node.rb_parent != HRTIMER_INACTIVE;
+	return rb_parent(&timer->node) != HRTIMER_INACTIVE;
 }
 
 /* Forward a hrtimer so it expires after now: */
_

Re: [PATCH] Shrink rbtree

[Andrew Morton]

Andrew Morton <akpm@osdl.org> wrote:
>
> -#define HRTIMER_INACTIVE	((void *)1UL)
>  +#define HRTIMER_INACTIVE	((void *)-2)

I don't think that's going to work either.   Let me try -4..

Re: [PATCH] Shrink rbtree

[Andrew Morton]

Andrew Morton <akpm@osdl.org> wrote:
>
> Andrew Morton <akpm@osdl.org> wrote:
>  >
>  > -#define HRTIMER_INACTIVE	((void *)1UL)
>  >  +#define HRTIMER_INACTIVE	((void *)-2)
> 
>  I don't think that's going to work either.   Let me try -4..

hrtimer.c has problems too.  I think I'll return your patch for some
warranty repairs ;)

Re: [PATCH] Shrink rbtree

[David Woodhouse]

On Fri, 2006-04-21 at 18:09 -0700, Andrew Morton wrote:
> #define HRTIMER_INACTIVE        ((void *)1UL) 

Ah. That's newer than the kernel I tested on. Your patch isn't going to
make kernel/hrtimer.c compile though, surely? Let's do it the same way
everyone else marks off-tree nodes -- by setting its parent pointer to
point to itself....

diff --git a/include/linux/hrtimer.h b/include/linux/hrtimer.h
index 306acf1..7d2a1b9 100644
--- a/include/linux/hrtimer.h
+++ b/include/linux/hrtimer.h
@@ -127,7 +127,7 @@ #endif
 
 static inline int hrtimer_active(const struct hrtimer *timer)
 {
-	return timer->node.rb_parent != HRTIMER_INACTIVE;
+	return rb_parent(&timer->node) != &timer->node;
 }
 
 /* Forward a hrtimer so it expires after now: */
diff --git a/kernel/hrtimer.c b/kernel/hrtimer.c
index d2a7296..04ab27d 100644
--- a/kernel/hrtimer.c
+++ b/kernel/hrtimer.c
@@ -393,7 +393,7 @@ static void __remove_hrtimer(struct hrti
 	if (base->first == &timer->node)
 		base->first = rb_next(&timer->node);
 	rb_erase(&timer->node, &base->active);
-	timer->node.rb_parent = HRTIMER_INACTIVE;
+	rb_set_parent(&timer->node, &timer->node);
 }
 
 /*
@@ -578,7 +578,7 @@ void hrtimer_init(struct hrtimer *timer,
 		clock_id = CLOCK_MONOTONIC;
 
 	timer->base = &bases[clock_id];
-	timer->node.rb_parent = HRTIMER_INACTIVE;
+	rb_set_parent(&timer->node, &timer->node);
 }
 
 /**

-- 
dwmw2

Re: [PATCH] Shrink rbtree

[Ingo Oeser]

Hi David,

On Saturday, 22. April 2006 03:29, David Woodhouse wrote:
> On Fri, 2006-04-21 at 18:09 -0700, Andrew Morton wrote:
> > #define HRTIMER_INACTIVE        ((void *)1UL) 
> 
> Ah. That's newer than the kernel I tested on. Your patch isn't going to
> make kernel/hrtimer.c compile though, surely? Let's do it the same way
> everyone else marks off-tree nodes -- by setting its parent pointer to
> point to itself....

Yes, but please make it a common helper, since there is a real need
for it and code has to agree on the dirty hacks it uses :-)

static inline int rb_in_tree(const struct rb_node *node)
{
	return rb_parent(node) != node;
}

static inline void rb_set_off_tree(struct rb_node *node)
{
	rb_set_parent(node, node);
}


This is trivial, but gives semantics to those strange operations.


Regards

Ingo Oeser

Re: [PATCH] Shrink rbtree

[David Woodhouse]

On Sat, 2006-04-22 at 14:29 +0200, Ingo Oeser wrote:
> Yes, but please make it a common helper, since there is a real need
> for it and code has to agree on the dirty hacks it uses :-)

Is there a real need for it? It's all just paranoid debugging checks,
isn't it? If there's a _real_ need for marking an object as being
inactive because it can be reached through some means other than the
rbtree, then that arguably lives in the higher-level object itself, not
its rb_node.

I'm reluctant to 'bless' this practice, because we'll then get asked to
set it to 'inactive' every time we take a node off the tree, to have a
BUG_ON() which checks it in certain places, etc.... it's mostly
pointless AFAICT.

-- 
dwmw2

Re: [PATCH] Shrink rbtree

[Ingo Oeser]

Hio David,

On Saturday, 22. April 2006 15:38, David Woodhouse wrote:
> I'm reluctant to 'bless' this practice, because we'll then get asked to
> set it to 'inactive' every time we take a node off the tree, to have a
> BUG_ON() which checks it in certain places, etc.... it's mostly
> pointless AFAICT.

I understand your point. Can we agree on just doing this for functions which
are handed off-tree and on-tree nodes and have to care for locking reasons?

It is ok for functions to enforce their API with BUG_ON(). But this part should
not be generalized, since this part really depends on the user.

Each rbtree user having its own private hackery for this is wasted developer
resources IMHO. 

So please either provide common helpers or just delete the potential users
if you think this is not needed.

I'm happy either way.


Regards

Ingo Oeser

Re: [PATCH] Shrink rbtree

[Steven Rostedt]

I'm just adding Thomas Gleixner and Roman Zippel to the CC field since
the part in question came from a debate to get rid of a state field in
hrtimer.

http://marc.theaimsgroup.com/?l=linux-kernel&m=114215996918851&w=2

-- Steve

On Fri, 2006-04-21 at 18:09 -0700, Andrew Morton wrote:
> David Woodhouse <dwmw2@infradead.org> wrote:
> >
> > git://git.infradead.org/~dwmw2/rbtree-2.6
> 
> include/linux/hrtimer.h: In function `hrtimer_active':
> include/linux/hrtimer.h:130: structure has no member named `rb_parent'
> 
> Might I cast aspersions upon the quality of your testing?
> 
> 
> 
> #define HRTIMER_INACTIVE	((void *)1UL)
> 
> ...
> 
> static inline int hrtimer_active(const struct hrtimer *timer)
> {
> 	return rb_parent(timer->node) != HRTIMER_INACTIVE;
> }
> 
> 
> So we have somewhat-competing hackery here.
> 
> Testing this...
> 
> --- devel/include/linux/hrtimer.h~git-rbtree-hrtimer-fix	2006-04-21 18:03:44.000000000 -0700
> +++ devel-akpm/include/linux/hrtimer.h	2006-04-21 18:08:02.000000000 -0700
> @@ -34,7 +34,7 @@ enum hrtimer_restart {
>  	HRTIMER_RESTART,
>  };
>  
> -#define HRTIMER_INACTIVE	((void *)1UL)
> +#define HRTIMER_INACTIVE	((void *)-2)
>  
>  struct hrtimer_base;
>  
> @@ -127,7 +127,7 @@ extern ktime_t hrtimer_get_next_event(vo
>  
>  static inline int hrtimer_active(const struct hrtimer *timer)
>  {
> -	return timer->node.rb_parent != HRTIMER_INACTIVE;
> +	return rb_parent(&timer->node) != HRTIMER_INACTIVE;
>  }
>  
>  /* Forward a hrtimer so it expires after now: */
> _
> 
> -
> To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
> Please read the FAQ at  http://www.tux.org/lkml/

Re: [PATCH] Shrink rbtree

[Thomas Gleixner]

On Sun, 2006-04-23 at 12:36 -0400, Steven Rostedt wrote:
> I'm just adding Thomas Gleixner and Roman Zippel to the CC field since
> the part in question came from a debate to get rid of a state field in
> hrtimer.
> 
> http://marc.theaimsgroup.com/?l=linux-kernel&m=114215996918851&w=2

David found a way to solve it already.

	tglx