[PATCH 00/13] rbtree updates

[PATCH 00/13] rbtree updates

[Michel Lespinasse]

I recently started looking at the rbtree code (with an eye towards
improving the augmented rbtree support, but I haven't gotten there
yet). I noticed a lot of possible speed improvements, which I am now
proposing in this patch set.

Patches 1-4 are preparatory: remove internal functions from rbtree.h
so that users won't be tempted to use them instead of the documented
APIs, clean up some incorrect usages I've noticed (in particular, with
the recently added fs/proc/proc_sysctl.c rbtree usage), reference the
documentation so that people have one less excuse to miss it, etc.

Patch 5 is a small module I wrote to check the rbtree performance.
It creates 100 nodes with random keys and repeatedly inserts and erases
them from an rbtree. Additionally, it has code to check for rbtree
invariants after each insert or erase operation.

Patches 6-13 is where the rbtree optimizations are done, and they touch
only that one file, lib/rbtree.c . I am getting good results out of these -
in my small benchmark doing rbtree insertion (including search) and erase,
I'm seeing a 30% runtime reduction on Sandybridge E5, which is more than
I initially thought would be possible. (the results aren't as impressive
on my two other test hosts though, AMD barcelona and Intel Westmere, where
I am seeing 14% runtime reduction only). The code size - both source
(ommiting comments) and compiled - is also shorter after these changes.
However, I do admit that the updated code is more arduous to read - one
big reason for that is the removal of the tree rotation helpers, which
added some overhead but also made it easier to reason about things locally.
Overall, I believe this is an acceptable compromise, given that this code
doesn't get modified very often, and that I have good tests for it.

For those people who want to really understand the code, I can only
recommend keeping around a copy of the cormen/leiserson/rivest book, as
the original algorithm seems to be inspired by it and having the rbtrees
drawn up really helps.

This patchset is against v3.4 - I had actually done most of the development
against v3.3 but the rbtree code doesn't change very often so I didn't have
to update it much, save for dealing with the recent rbtree additions in
fs/proc/proc_sysctl.c

My proposal would be to use this as a base to add on the augmented rbtree
support enhancements, which I'd like to do next. Then this could all go in
-mm tree so that various augmented rbtree uses that have been discussed
(such as finding gaps between vmas) can use this.

Michel Lespinasse (13):
  rbtree: reference Documentation/rbtree.txt for usage instructions
  rbtree: empty nodes have no color
  rbtree: fix incorrect rbtree node insertion in fs/proc/proc_sysctl.c
  rbtree: move some implementation details from rbtree.h to rbtree.c
  rbtree: performance and correctness test
  rbtree: break out of rb_insert_color loop after tree rotation
  rbtree: adjust root color in rb_insert_color() only when necessary
  rbtree: optimize tree rotations in rb_insert_color()
  rbtree: optimize color flips and parent fetching in rb_insert_color()
  rbtree: adjust node color in __rb_erase_color() only when necessary
  rbtree: optimize case selection logic in __rb_erase_color()
  rbtree: optimize tree rotations in __rb_erase_color()
  rbtree: optimize color flips in __rb_erase_color()

 fs/proc/proc_sysctl.c      |    5 +-
 include/linux/rbtree.h     |   98 +------------
 include/linux/timerqueue.h |    2 +-
 lib/rbtree.c               |  349 +++++++++++++++++++++++++-------------------
 tests/rbtree_test.c        |  135 +++++++++++++++++
 5 files changed, 340 insertions(+), 249 deletions(-)
 create mode 100644 tests/rbtree_test.c

-- 
1.7.7.3

[PATCH 00/13] rbtree updates

[Michel Lespinasse]

I recently started looking at the rbtree code (with an eye towards
improving the augmented rbtree support, but I haven't gotten there
yet). I noticed a lot of possible speed improvements, which I am now
proposing in this patch set.

Patches 1-4 are preparatory: remove internal functions from rbtree.h
so that users won't be tempted to use them instead of the documented
APIs, clean up some incorrect usages I've noticed (in particular, with
the recently added fs/proc/proc_sysctl.c rbtree usage), reference the
documentation so that people have one less excuse to miss it, etc.

Patch 5 is a small module I wrote to check the rbtree performance.
It creates 100 nodes with random keys and repeatedly inserts and erases
them from an rbtree. Additionally, it has code to check for rbtree
invariants after each insert or erase operation.

Patches 6-13 is where the rbtree optimizations are done, and they touch
only that one file, lib/rbtree.c . I am getting good results out of these -
in my small benchmark doing rbtree insertion (including search) and erase,
I'm seeing a 30% runtime reduction on Sandybridge E5, which is more than
I initially thought would be possible. (the results aren't as impressive
on my two other test hosts though, AMD barcelona and Intel Westmere, where
I am seeing 14% runtime reduction only). The code size - both source
(ommiting comments) and compiled - is also shorter after these changes.
However, I do admit that the updated code is more arduous to read - one
big reason for that is the removal of the tree rotation helpers, which
added some overhead but also made it easier to reason about things locally.
Overall, I believe this is an acceptable compromise, given that this code
doesn't get modified very often, and that I have good tests for it.

For those people who want to really understand the code, I can only
recommend keeping around a copy of the cormen/leiserson/rivest book, as
the original algorithm seems to be inspired by it and having the rbtrees
drawn up really helps.

This patchset is against v3.4 - I had actually done most of the development
against v3.3 but the rbtree code doesn't change very often so I didn't have
to update it much, save for dealing with the recent rbtree additions in
fs/proc/proc_sysctl.c

My proposal would be to use this as a base to add on the augmented rbtree
support enhancements, which I'd like to do next. Then this could all go in
-mm tree so that various augmented rbtree uses that have been discussed
(such as finding gaps between vmas) can use this.

Michel Lespinasse (13):
  rbtree: reference Documentation/rbtree.txt for usage instructions
  rbtree: empty nodes have no color
  rbtree: fix incorrect rbtree node insertion in fs/proc/proc_sysctl.c
  rbtree: move some implementation details from rbtree.h to rbtree.c
  rbtree: performance and correctness test
  rbtree: break out of rb_insert_color loop after tree rotation
  rbtree: adjust root color in rb_insert_color() only when necessary
  rbtree: optimize tree rotations in rb_insert_color()
  rbtree: optimize color flips and parent fetching in rb_insert_color()
  rbtree: adjust node color in __rb_erase_color() only when necessary
  rbtree: optimize case selection logic in __rb_erase_color()
  rbtree: optimize tree rotations in __rb_erase_color()
  rbtree: optimize color flips in __rb_erase_color()

 fs/proc/proc_sysctl.c      |    5 +-
 include/linux/rbtree.h     |   98 +------------
 include/linux/timerqueue.h |    2 +-
 lib/rbtree.c               |  349 +++++++++++++++++++++++++-------------------
 tests/rbtree_test.c        |  135 +++++++++++++++++
 5 files changed, 340 insertions(+), 249 deletions(-)
 create mode 100644 tests/rbtree_test.c

-- 
1.7.7.3

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

[PATCH 01/13] rbtree: reference Documentation/rbtree.txt for usage instructions

[Michel Lespinasse]

include/linux/rbtree.h included some basic usage instructions, while
Documentation/rbtree.txt had some more complete and easier to follow
instructions.  Replacing the former with a reference to the latter.

Signed-off-by: Michel Lespinasse <walken@google.com>
---
 include/linux/rbtree.h |   67 +-----------------------------------------------
 1 files changed, 1 insertions(+), 66 deletions(-)

diff --git a/include/linux/rbtree.h b/include/linux/rbtree.h
index 033b507..e6a8077 100644
--- a/include/linux/rbtree.h
+++ b/include/linux/rbtree.h
@@ -23,72 +23,7 @@
   I know it's not the cleaner way,  but in C (not in C++) to get
   performances and genericity...
 
-  Some example of insert and search follows here. The search is a plain
-  normal search over an ordered tree. The insert instead must be implemented
-  in two steps: First, the code must insert the element in order as a red leaf
-  in the tree, and then the support library function rb_insert_color() must
-  be called. Such function will do the not trivial work to rebalance the
-  rbtree, if necessary.
-
------------------------------------------------------------------------
-static inline struct page * rb_search_page_cache(struct inode * inode,
-						 unsigned long offset)
-{
-	struct rb_node * n = inode->i_rb_page_cache.rb_node;
-	struct page * page;
-
-	while (n)
-	{
-		page = rb_entry(n, struct page, rb_page_cache);
-
-		if (offset < page->offset)
-			n = n->rb_left;
-		else if (offset > page->offset)
-			n = n->rb_right;
-		else
-			return page;
-	}
-	return NULL;
-}
-
-static inline struct page * __rb_insert_page_cache(struct inode * inode,
-						   unsigned long offset,
-						   struct rb_node * node)
-{
-	struct rb_node ** p = &inode->i_rb_page_cache.rb_node;
-	struct rb_node * parent = NULL;
-	struct page * page;
-
-	while (*p)
-	{
-		parent = *p;
-		page = rb_entry(parent, struct page, rb_page_cache);
-
-		if (offset < page->offset)
-			p = &(*p)->rb_left;
-		else if (offset > page->offset)
-			p = &(*p)->rb_right;
-		else
-			return page;
-	}
-
-	rb_link_node(node, parent, p);
-
-	return NULL;
-}
-
-static inline struct page * rb_insert_page_cache(struct inode * inode,
-						 unsigned long offset,
-						 struct rb_node * node)
-{
-	struct page * ret;
-	if ((ret = __rb_insert_page_cache(inode, offset, node)))
-		goto out;
-	rb_insert_color(node, &inode->i_rb_page_cache);
- out:
-	return ret;
-}
------------------------------------------------------------------------
+  See Documentation/rbtree.txt for documentation and samples.
 */
 
 #ifndef	_LINUX_RBTREE_H
-- 
1.7.7.3

[PATCH 01/13] rbtree: reference Documentation/rbtree.txt for usage instructions

[Michel Lespinasse]

include/linux/rbtree.h included some basic usage instructions, while
Documentation/rbtree.txt had some more complete and easier to follow
instructions.  Replacing the former with a reference to the latter.

Signed-off-by: Michel Lespinasse <walken@google.com>
---
 include/linux/rbtree.h |   67 +-----------------------------------------------
 1 files changed, 1 insertions(+), 66 deletions(-)

diff --git a/include/linux/rbtree.h b/include/linux/rbtree.h
index 033b507..e6a8077 100644
--- a/include/linux/rbtree.h
+++ b/include/linux/rbtree.h
@@ -23,72 +23,7 @@
   I know it's not the cleaner way,  but in C (not in C++) to get
   performances and genericity...
 
-  Some example of insert and search follows here. The search is a plain
-  normal search over an ordered tree. The insert instead must be implemented
-  in two steps: First, the code must insert the element in order as a red leaf
-  in the tree, and then the support library function rb_insert_color() must
-  be called. Such function will do the not trivial work to rebalance the
-  rbtree, if necessary.
-
------------------------------------------------------------------------
-static inline struct page * rb_search_page_cache(struct inode * inode,
-						 unsigned long offset)
-{
-	struct rb_node * n = inode->i_rb_page_cache.rb_node;
-	struct page * page;
-
-	while (n)
-	{
-		page = rb_entry(n, struct page, rb_page_cache);
-
-		if (offset < page->offset)
-			n = n->rb_left;
-		else if (offset > page->offset)
-			n = n->rb_right;
-		else
-			return page;
-	}
-	return NULL;
-}
-
-static inline struct page * __rb_insert_page_cache(struct inode * inode,
-						   unsigned long offset,
-						   struct rb_node * node)
-{
-	struct rb_node ** p = &inode->i_rb_page_cache.rb_node;
-	struct rb_node * parent = NULL;
-	struct page * page;
-
-	while (*p)
-	{
-		parent = *p;
-		page = rb_entry(parent, struct page, rb_page_cache);
-
-		if (offset < page->offset)
-			p = &(*p)->rb_left;
-		else if (offset > page->offset)
-			p = &(*p)->rb_right;
-		else
-			return page;
-	}
-
-	rb_link_node(node, parent, p);
-
-	return NULL;
-}
-
-static inline struct page * rb_insert_page_cache(struct inode * inode,
-						 unsigned long offset,
-						 struct rb_node * node)
-{
-	struct page * ret;
-	if ((ret = __rb_insert_page_cache(inode, offset, node)))
-		goto out;
-	rb_insert_color(node, &inode->i_rb_page_cache);
- out:
-	return ret;
-}
------------------------------------------------------------------------
+  See Documentation/rbtree.txt for documentation and samples.
 */
 
 #ifndef	_LINUX_RBTREE_H
-- 
1.7.7.3

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

[PATCH 02/13] rbtree: empty nodes have no color

[Michel Lespinasse]

Empty nodes have no color.  We can make use of this property to
simplify the code emitted by the RB_EMPTY_NODE and RB_CLEAR_NODE
macros.  Also, we can get rid of the rb_init_node function which had
been introduced by commit 88d19cf37952a7e1e38b2bf87a00f0e857e63180
to avoid some issue with the empty node's color not being initialized.

I'm not sure what the RB_EMPTY_NODE checks in rb_prev() / rb_next()
are doing there, though. axboe introduced them in commit 10fd48f2376d.
The way I see it, the 'empty node' abstraction is only used by rbtree
users to flag nodes that they haven't inserted in any rbtree, so asking
the predecessor or successor of such nodes doesn't make any sense.

One final rb_init_node() caller was recently added in sysctl code
to implement faster sysctl name lookups. This code doesn't make use
of RB_EMPTY_NODE at all, and from what I could see it only called
rb_init_node() under the mistaken assumption that such initialization
was required before node insertion.

Signed-off-by: Michel Lespinasse <walken@google.com>
---
 fs/proc/proc_sysctl.c      |    4 +---
 include/linux/rbtree.h     |   15 +++++----------
 include/linux/timerqueue.h |    2 +-
 lib/rbtree.c               |    4 ++--
 4 files changed, 9 insertions(+), 16 deletions(-)

diff --git a/fs/proc/proc_sysctl.c b/fs/proc/proc_sysctl.c
index 21d836f..33aea86 100644
--- a/fs/proc/proc_sysctl.c
+++ b/fs/proc/proc_sysctl.c
@@ -168,10 +168,8 @@ static void init_header(struct ctl_table_header *head,
 	head->node = node;
 	if (node) {
 		struct ctl_table *entry;
-		for (entry = table; entry->procname; entry++, node++) {
-			rb_init_node(&node->node);
+		for (entry = table; entry->procname; entry++, node++)
 			node->header = head;
-		}
 	}
 }
 
diff --git a/include/linux/rbtree.h b/include/linux/rbtree.h
index e6a8077..2049087 100644
--- a/include/linux/rbtree.h
+++ b/include/linux/rbtree.h
@@ -67,17 +67,12 @@ static inline void rb_set_color(struct rb_node *rb, int color)
 #define RB_ROOT	(struct rb_root) { NULL, }
 #define	rb_entry(ptr, type, member) container_of(ptr, type, member)
 
-#define RB_EMPTY_ROOT(root)	((root)->rb_node == NULL)
-#define RB_EMPTY_NODE(node)	(rb_parent(node) == node)
-#define RB_CLEAR_NODE(node)	(rb_set_parent(node, node))
+#define RB_EMPTY_ROOT(root)  ((root)->rb_node == NULL)
+
+/* 'empty' nodes are nodes that are known not to be inserted in an rbree */
+#define RB_EMPTY_NODE(node)  ((node)->rb_parent_color == (unsigned long)(node))
+#define RB_CLEAR_NODE(node)  ((node)->rb_parent_color = (unsigned long)(node))
 
-static inline void rb_init_node(struct rb_node *rb)
-{
-	rb->rb_parent_color = 0;
-	rb->rb_right = NULL;
-	rb->rb_left = NULL;
-	RB_CLEAR_NODE(rb);
-}
 
 extern void rb_insert_color(struct rb_node *, struct rb_root *);
 extern void rb_erase(struct rb_node *, struct rb_root *);
diff --git a/include/linux/timerqueue.h b/include/linux/timerqueue.h
index 5088727..a520fd7 100644
--- a/include/linux/timerqueue.h
+++ b/include/linux/timerqueue.h
@@ -39,7 +39,7 @@ struct timerqueue_node *timerqueue_getnext(struct timerqueue_head *head)
 
 static inline void timerqueue_init(struct timerqueue_node *node)
 {
-	rb_init_node(&node->node);
+	RB_CLEAR_NODE(&node->node);
 }
 
 static inline void timerqueue_init_head(struct timerqueue_head *head)
diff --git a/lib/rbtree.c b/lib/rbtree.c
index d417556..fe43c8c 100644
--- a/lib/rbtree.c
+++ b/lib/rbtree.c
@@ -387,7 +387,7 @@ struct rb_node *rb_next(const struct rb_node *node)
 {
 	struct rb_node *parent;
 
-	if (rb_parent(node) == node)
+	if (RB_EMPTY_NODE(node))
 		return NULL;
 
 	/* If we have a right-hand child, go down and then left as far
@@ -416,7 +416,7 @@ struct rb_node *rb_prev(const struct rb_node *node)
 {
 	struct rb_node *parent;
 
-	if (rb_parent(node) == node)
+	if (RB_EMPTY_NODE(node))
 		return NULL;
 
 	/* If we have a left-hand child, go down and then right as far
-- 
1.7.7.3

[PATCH 02/13] rbtree: empty nodes have no color

[Michel Lespinasse]

Empty nodes have no color.  We can make use of this property to
simplify the code emitted by the RB_EMPTY_NODE and RB_CLEAR_NODE
macros.  Also, we can get rid of the rb_init_node function which had
been introduced by commit 88d19cf37952a7e1e38b2bf87a00f0e857e63180
to avoid some issue with the empty node's color not being initialized.

I'm not sure what the RB_EMPTY_NODE checks in rb_prev() / rb_next()
are doing there, though. axboe introduced them in commit 10fd48f2376d.
The way I see it, the 'empty node' abstraction is only used by rbtree
users to flag nodes that they haven't inserted in any rbtree, so asking
the predecessor or successor of such nodes doesn't make any sense.

One final rb_init_node() caller was recently added in sysctl code
to implement faster sysctl name lookups. This code doesn't make use
of RB_EMPTY_NODE at all, and from what I could see it only called
rb_init_node() under the mistaken assumption that such initialization
was required before node insertion.

Signed-off-by: Michel Lespinasse <walken@google.com>
---
 fs/proc/proc_sysctl.c      |    4 +---
 include/linux/rbtree.h     |   15 +++++----------
 include/linux/timerqueue.h |    2 +-
 lib/rbtree.c               |    4 ++--
 4 files changed, 9 insertions(+), 16 deletions(-)

diff --git a/fs/proc/proc_sysctl.c b/fs/proc/proc_sysctl.c
index 21d836f..33aea86 100644
--- a/fs/proc/proc_sysctl.c
+++ b/fs/proc/proc_sysctl.c
@@ -168,10 +168,8 @@ static void init_header(struct ctl_table_header *head,
 	head->node = node;
 	if (node) {
 		struct ctl_table *entry;
-		for (entry = table; entry->procname; entry++, node++) {
-			rb_init_node(&node->node);
+		for (entry = table; entry->procname; entry++, node++)
 			node->header = head;
-		}
 	}
 }
 
diff --git a/include/linux/rbtree.h b/include/linux/rbtree.h
index e6a8077..2049087 100644
--- a/include/linux/rbtree.h
+++ b/include/linux/rbtree.h
@@ -67,17 +67,12 @@ static inline void rb_set_color(struct rb_node *rb, int color)
 #define RB_ROOT	(struct rb_root) { NULL, }
 #define	rb_entry(ptr, type, member) container_of(ptr, type, member)
 
-#define RB_EMPTY_ROOT(root)	((root)->rb_node == NULL)
-#define RB_EMPTY_NODE(node)	(rb_parent(node) == node)
-#define RB_CLEAR_NODE(node)	(rb_set_parent(node, node))
+#define RB_EMPTY_ROOT(root)  ((root)->rb_node == NULL)
+
+/* 'empty' nodes are nodes that are known not to be inserted in an rbree */
+#define RB_EMPTY_NODE(node)  ((node)->rb_parent_color == (unsigned long)(node))
+#define RB_CLEAR_NODE(node)  ((node)->rb_parent_color = (unsigned long)(node))
 
-static inline void rb_init_node(struct rb_node *rb)
-{
-	rb->rb_parent_color = 0;
-	rb->rb_right = NULL;
-	rb->rb_left = NULL;
-	RB_CLEAR_NODE(rb);
-}
 
 extern void rb_insert_color(struct rb_node *, struct rb_root *);
 extern void rb_erase(struct rb_node *, struct rb_root *);
diff --git a/include/linux/timerqueue.h b/include/linux/timerqueue.h
index 5088727..a520fd7 100644
--- a/include/linux/timerqueue.h
+++ b/include/linux/timerqueue.h
@@ -39,7 +39,7 @@ struct timerqueue_node *timerqueue_getnext(struct timerqueue_head *head)
 
 static inline void timerqueue_init(struct timerqueue_node *node)
 {
-	rb_init_node(&node->node);
+	RB_CLEAR_NODE(&node->node);
 }
 
 static inline void timerqueue_init_head(struct timerqueue_head *head)
diff --git a/lib/rbtree.c b/lib/rbtree.c
index d417556..fe43c8c 100644
--- a/lib/rbtree.c
+++ b/lib/rbtree.c
@@ -387,7 +387,7 @@ struct rb_node *rb_next(const struct rb_node *node)
 {
 	struct rb_node *parent;
 
-	if (rb_parent(node) == node)
+	if (RB_EMPTY_NODE(node))
 		return NULL;
 
 	/* If we have a right-hand child, go down and then left as far
@@ -416,7 +416,7 @@ struct rb_node *rb_prev(const struct rb_node *node)
 {
 	struct rb_node *parent;
 
-	if (rb_parent(node) == node)
+	if (RB_EMPTY_NODE(node))
 		return NULL;
 
 	/* If we have a left-hand child, go down and then right as far
-- 
1.7.7.3

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

[PATCH 03/13] rbtree: fix incorrect rbtree node insertion in fs/proc/proc_sysctl.c

[Michel Lespinasse]

The recently added code to use rbtrees in sysctl did not follow the proper
rbtree interface on insertion - it was calling rb_link_node() which
inserts a new node into the binary tree, but missed the call to
rb_insert_color() which properly balances the rbtree and establishes all
expected rbtree invariants.

I found out about this only because faulty commit also used rb_init_node(),
which I am removing within this patchset. But I think it's an easy mistake
to make, and it makes me wonder if we should change the rbtree API so that
insertions would be done with a single rb_insert() call (even if its
implementation could still inline the rb_link_node() part and call
a private __rb_insert_color function to do the rebalancing).

Signed-off-by: Michel Lespinasse <walken@google.com>
---
 fs/proc/proc_sysctl.c |    1 +
 1 files changed, 1 insertions(+), 0 deletions(-)

diff --git a/fs/proc/proc_sysctl.c b/fs/proc/proc_sysctl.c
index 33aea86..77602c1a 100644
--- a/fs/proc/proc_sysctl.c
+++ b/fs/proc/proc_sysctl.c
@@ -142,6 +142,7 @@ static int insert_entry(struct ctl_table_header *head, struct ctl_table *entry)
 	}
 
 	rb_link_node(node, parent, p);
+	rb_insert_color(node, &head->parent->root);
 	return 0;
 }
 
-- 
1.7.7.3

[PATCH 03/13] rbtree: fix incorrect rbtree node insertion in fs/proc/proc_sysctl.c

[Michel Lespinasse]

The recently added code to use rbtrees in sysctl did not follow the proper
rbtree interface on insertion - it was calling rb_link_node() which
inserts a new node into the binary tree, but missed the call to
rb_insert_color() which properly balances the rbtree and establishes all
expected rbtree invariants.

I found out about this only because faulty commit also used rb_init_node(),
which I am removing within this patchset. But I think it's an easy mistake
to make, and it makes me wonder if we should change the rbtree API so that
insertions would be done with a single rb_insert() call (even if its
implementation could still inline the rb_link_node() part and call
a private __rb_insert_color function to do the rebalancing).

Signed-off-by: Michel Lespinasse <walken@google.com>
---
 fs/proc/proc_sysctl.c |    1 +
 1 files changed, 1 insertions(+), 0 deletions(-)

diff --git a/fs/proc/proc_sysctl.c b/fs/proc/proc_sysctl.c
index 33aea86..77602c1a 100644
--- a/fs/proc/proc_sysctl.c
+++ b/fs/proc/proc_sysctl.c
@@ -142,6 +142,7 @@ static int insert_entry(struct ctl_table_header *head, struct ctl_table *entry)
 	}
 
 	rb_link_node(node, parent, p);
+	rb_insert_color(node, &head->parent->root);
 	return 0;
 }
 
-- 
1.7.7.3

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

[PATCH 04/13] rbtree: move some implementation details from rbtree.h to rbtree.c

[Michel Lespinasse]

rbtree users must use the documented APIs to manipulate the tree
structure.  Low-level helpers to manipulate node colors and parenthood
are not part of that API, so move them to lib/rbtree.c

Signed-off-by: Michel Lespinasse <walken@google.com>
---
 include/linux/rbtree.h |   16 ----------------
 lib/rbtree.c           |   18 ++++++++++++++++++
 2 files changed, 18 insertions(+), 16 deletions(-)

diff --git a/include/linux/rbtree.h b/include/linux/rbtree.h
index 2049087..a06c044 100644
--- a/include/linux/rbtree.h
+++ b/include/linux/rbtree.h
@@ -35,8 +35,6 @@
 struct rb_node
 {
 	unsigned long  rb_parent_color;
-#define	RB_RED		0
-#define	RB_BLACK	1
 	struct rb_node *rb_right;
 	struct rb_node *rb_left;
 } __attribute__((aligned(sizeof(long))));
@@ -49,20 +47,6 @@ struct rb_root
 
 
 #define rb_parent(r)   ((struct rb_node *)((r)->rb_parent_color & ~3))
-#define rb_color(r)   ((r)->rb_parent_color & 1)
-#define rb_is_red(r)   (!rb_color(r))
-#define rb_is_black(r) rb_color(r)
-#define rb_set_red(r)  do { (r)->rb_parent_color &= ~1; } while (0)
-#define rb_set_black(r)  do { (r)->rb_parent_color |= 1; } while (0)
-
-static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p)
-{
-	rb->rb_parent_color = (rb->rb_parent_color & 3) | (unsigned long)p;
-}
-static inline void rb_set_color(struct rb_node *rb, int color)
-{
-	rb->rb_parent_color = (rb->rb_parent_color & ~1) | color;
-}
 
 #define RB_ROOT	(struct rb_root) { NULL, }
 #define	rb_entry(ptr, type, member) container_of(ptr, type, member)
diff --git a/lib/rbtree.c b/lib/rbtree.c
index fe43c8c..d0ec339 100644
--- a/lib/rbtree.c
+++ b/lib/rbtree.c
@@ -23,6 +23,24 @@
 #include <linux/rbtree.h>
 #include <linux/export.h>
 
+#define	RB_RED		0
+#define	RB_BLACK	1
+
+#define rb_color(r)   ((r)->rb_parent_color & 1)
+#define rb_is_red(r)   (!rb_color(r))
+#define rb_is_black(r) rb_color(r)
+#define rb_set_red(r)  do { (r)->rb_parent_color &= ~1; } while (0)
+#define rb_set_black(r)  do { (r)->rb_parent_color |= 1; } while (0)
+
+static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p)
+{
+	rb->rb_parent_color = (rb->rb_parent_color & 3) | (unsigned long)p;
+}
+static inline void rb_set_color(struct rb_node *rb, int color)
+{
+	rb->rb_parent_color = (rb->rb_parent_color & ~1) | color;
+}
+
 static void __rb_rotate_left(struct rb_node *node, struct rb_root *root)
 {
 	struct rb_node *right = node->rb_right;
-- 
1.7.7.3

[PATCH 04/13] rbtree: move some implementation details from rbtree.h to rbtree.c

[Michel Lespinasse]

rbtree users must use the documented APIs to manipulate the tree
structure.  Low-level helpers to manipulate node colors and parenthood
are not part of that API, so move them to lib/rbtree.c

Signed-off-by: Michel Lespinasse <walken@google.com>
---
 include/linux/rbtree.h |   16 ----------------
 lib/rbtree.c           |   18 ++++++++++++++++++
 2 files changed, 18 insertions(+), 16 deletions(-)

diff --git a/include/linux/rbtree.h b/include/linux/rbtree.h
index 2049087..a06c044 100644
--- a/include/linux/rbtree.h
+++ b/include/linux/rbtree.h
@@ -35,8 +35,6 @@
 struct rb_node
 {
 	unsigned long  rb_parent_color;
-#define	RB_RED		0
-#define	RB_BLACK	1
 	struct rb_node *rb_right;
 	struct rb_node *rb_left;
 } __attribute__((aligned(sizeof(long))));
@@ -49,20 +47,6 @@ struct rb_root
 
 
 #define rb_parent(r)   ((struct rb_node *)((r)->rb_parent_color & ~3))
-#define rb_color(r)   ((r)->rb_parent_color & 1)
-#define rb_is_red(r)   (!rb_color(r))
-#define rb_is_black(r) rb_color(r)
-#define rb_set_red(r)  do { (r)->rb_parent_color &= ~1; } while (0)
-#define rb_set_black(r)  do { (r)->rb_parent_color |= 1; } while (0)
-
-static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p)
-{
-	rb->rb_parent_color = (rb->rb_parent_color & 3) | (unsigned long)p;
-}
-static inline void rb_set_color(struct rb_node *rb, int color)
-{
-	rb->rb_parent_color = (rb->rb_parent_color & ~1) | color;
-}
 
 #define RB_ROOT	(struct rb_root) { NULL, }
 #define	rb_entry(ptr, type, member) container_of(ptr, type, member)
diff --git a/lib/rbtree.c b/lib/rbtree.c
index fe43c8c..d0ec339 100644
--- a/lib/rbtree.c
+++ b/lib/rbtree.c
@@ -23,6 +23,24 @@
 #include <linux/rbtree.h>
 #include <linux/export.h>
 
+#define	RB_RED		0
+#define	RB_BLACK	1
+
+#define rb_color(r)   ((r)->rb_parent_color & 1)
+#define rb_is_red(r)   (!rb_color(r))
+#define rb_is_black(r) rb_color(r)
+#define rb_set_red(r)  do { (r)->rb_parent_color &= ~1; } while (0)
+#define rb_set_black(r)  do { (r)->rb_parent_color |= 1; } while (0)
+
+static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p)
+{
+	rb->rb_parent_color = (rb->rb_parent_color & 3) | (unsigned long)p;
+}
+static inline void rb_set_color(struct rb_node *rb, int color)
+{
+	rb->rb_parent_color = (rb->rb_parent_color & ~1) | color;
+}
+
 static void __rb_rotate_left(struct rb_node *node, struct rb_root *root)
 {
 	struct rb_node *right = node->rb_right;
-- 
1.7.7.3

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

[PATCH 05/13] rbtree: performance and correctness test

[Michel Lespinasse]

This small module helps measure the performance of rbtree insert and erase.

Additionally, we run a few correctness tests to check that the rbtrees have
all desired properties:
- contains the right number of nodes in the order desired,
- never two consecutive red nodes on any path,
- all paths to leaf nodes have the same number of black nodes,
- root node is black

Signed-off-by: Michel Lespinasse <walken@google.com>
---
 tests/rbtree_test.c |  135 +++++++++++++++++++++++++++++++++++++++++++++++++++
 1 files changed, 135 insertions(+), 0 deletions(-)
 create mode 100644 tests/rbtree_test.c

diff --git a/tests/rbtree_test.c b/tests/rbtree_test.c
new file mode 100644
index 0000000..2e3944d
--- /dev/null
+++ b/tests/rbtree_test.c
@@ -0,0 +1,135 @@
+#include <linux/module.h>
+#include <linux/rbtree.h>
+#include <linux/random.h>
+#include <asm/timex.h>
+
+#define NODES       100
+#define PERF_LOOPS  100000
+#define CHECK_LOOPS 100
+
+struct test_node {
+	struct rb_node rb;
+	u32 key;
+};
+
+static struct rb_root root = RB_ROOT;
+static struct test_node nodes[NODES];
+
+static struct rnd_state rnd;
+
+static void insert(struct test_node *node, struct rb_root *root)
+{
+	struct rb_node **new = &root->rb_node, *parent = NULL;
+
+	while (*new) {
+		parent = *new;
+		if (node->key < rb_entry(parent, struct test_node, rb)->key)
+			new = &parent->rb_left;
+		else
+			new = &parent->rb_right;
+	}
+
+	rb_link_node(&node->rb, parent, new);
+	rb_insert_color(&node->rb, root);
+}
+
+static inline void erase(struct test_node *node, struct rb_root *root)
+{
+	rb_erase(&node->rb, root);
+}
+
+static void init(void)
+{
+	int i;
+	for (i = 0; i < NODES; i++)
+		nodes[i].key = prandom32(&rnd);
+}
+
+static bool is_red(struct rb_node *rb)
+{
+	return rb->rb_parent_color == (unsigned long)rb_parent(rb);
+}
+
+static int black_path_count(struct rb_node *rb)
+{
+	int count;
+	for (count = 0; rb; rb = rb_parent(rb))
+		count += !is_red(rb);
+	return count;
+}
+
+static void check(int nr_nodes)
+{
+	struct rb_node *rb;
+	int count = 0;
+	int blacks;
+	u32 prev_key = 0;
+
+	for (rb = rb_first(&root); rb; rb = rb_next(rb)) {
+		struct test_node *node = rb_entry(rb, struct test_node, rb);
+		WARN_ON_ONCE(node->key < prev_key);
+		WARN_ON_ONCE(is_red(rb) &&
+			     (!rb_parent(rb) || is_red(rb_parent(rb))));
+		if (!count)
+			blacks = black_path_count(rb);
+		else
+			WARN_ON_ONCE((!rb->rb_left || !rb->rb_right) &&
+				     blacks != black_path_count(rb));
+		prev_key = node->key;
+		count++;
+	}
+	WARN_ON_ONCE(count != nr_nodes);
+}
+
+static int rbtree_test_init(void)
+{
+	int i, j;
+	cycles_t time1, time2, time;
+
+	printk(KERN_ALERT "rbtree testing");
+
+	prandom32_seed(&rnd, 3141592653589793238);
+	init();
+
+	time1 = get_cycles();
+
+	for (i = 0; i < PERF_LOOPS; i++) {
+		for (j = 0; j < NODES; j++)
+			insert(nodes + j, &root);
+		for (j = 0; j < NODES; j++)
+			erase(nodes + j, &root);
+	}
+
+	time2 = get_cycles();
+	time = time2 - time1;
+
+	time = div_u64(time, PERF_LOOPS);
+	printk(" -> %llu cycles\n", time);
+
+	for (i = 0; i < CHECK_LOOPS; i++) {
+		init();
+		for (j = 0; j < NODES; j++) {
+			check(j);
+			insert(nodes + j, &root);
+		}
+		for (j = 0; j < NODES; j++) {
+			check(NODES - j);
+			erase(nodes + j, &root);
+		}
+		check(0);
+	}
+
+	return -EAGAIN; /* Fail will directly unload the module */
+}
+
+static void rbtree_test_exit(void)
+{
+	printk(KERN_ALERT "test exit\n");
+}
+
+module_init(rbtree_test_init)
+module_exit(rbtree_test_exit)
+
+MODULE_LICENSE("GPL");
+MODULE_AUTHOR("Michel Lespinasse");
+MODULE_DESCRIPTION("Red Black Tree test");
-- 
1.7.7.3

[PATCH 05/13] rbtree: performance and correctness test

[Michel Lespinasse]

This small module helps measure the performance of rbtree insert and erase.

Additionally, we run a few correctness tests to check that the rbtrees have
all desired properties:
- contains the right number of nodes in the order desired,
- never two consecutive red nodes on any path,
- all paths to leaf nodes have the same number of black nodes,
- root node is black

Signed-off-by: Michel Lespinasse <walken@google.com>
---
 tests/rbtree_test.c |  135 +++++++++++++++++++++++++++++++++++++++++++++++++++
 1 files changed, 135 insertions(+), 0 deletions(-)
 create mode 100644 tests/rbtree_test.c

diff --git a/tests/rbtree_test.c b/tests/rbtree_test.c
new file mode 100644
index 0000000..2e3944d
--- /dev/null
+++ b/tests/rbtree_test.c
@@ -0,0 +1,135 @@
+#include <linux/module.h>
+#include <linux/rbtree.h>
+#include <linux/random.h>
+#include <asm/timex.h>
+
+#define NODES       100
+#define PERF_LOOPS  100000
+#define CHECK_LOOPS 100
+
+struct test_node {
+	struct rb_node rb;
+	u32 key;
+};
+
+static struct rb_root root = RB_ROOT;
+static struct test_node nodes[NODES];
+
+static struct rnd_state rnd;
+
+static void insert(struct test_node *node, struct rb_root *root)
+{
+	struct rb_node **new = &root->rb_node, *parent = NULL;
+
+	while (*new) {
+		parent = *new;
+		if (node->key < rb_entry(parent, struct test_node, rb)->key)
+			new = &parent->rb_left;
+		else
+			new = &parent->rb_right;
+	}
+
+	rb_link_node(&node->rb, parent, new);
+	rb_insert_color(&node->rb, root);
+}
+
+static inline void erase(struct test_node *node, struct rb_root *root)
+{
+	rb_erase(&node->rb, root);
+}
+
+static void init(void)
+{
+	int i;
+	for (i = 0; i < NODES; i++)
+		nodes[i].key = prandom32(&rnd);
+}
+
+static bool is_red(struct rb_node *rb)
+{
+	return rb->rb_parent_color == (unsigned long)rb_parent(rb);
+}
+
+static int black_path_count(struct rb_node *rb)
+{
+	int count;
+	for (count = 0; rb; rb = rb_parent(rb))
+		count += !is_red(rb);
+	return count;
+}
+
+static void check(int nr_nodes)
+{
+	struct rb_node *rb;
+	int count = 0;
+	int blacks;
+	u32 prev_key = 0;
+
+	for (rb = rb_first(&root); rb; rb = rb_next(rb)) {
+		struct test_node *node = rb_entry(rb, struct test_node, rb);
+		WARN_ON_ONCE(node->key < prev_key);
+		WARN_ON_ONCE(is_red(rb) &&
+			     (!rb_parent(rb) || is_red(rb_parent(rb))));
+		if (!count)
+			blacks = black_path_count(rb);
+		else
+			WARN_ON_ONCE((!rb->rb_left || !rb->rb_right) &&
+				     blacks != black_path_count(rb));
+		prev_key = node->key;
+		count++;
+	}
+	WARN_ON_ONCE(count != nr_nodes);
+}
+
+static int rbtree_test_init(void)
+{
+	int i, j;
+	cycles_t time1, time2, time;
+
+	printk(KERN_ALERT "rbtree testing");
+
+	prandom32_seed(&rnd, 3141592653589793238);
+	init();
+
+	time1 = get_cycles();
+
+	for (i = 0; i < PERF_LOOPS; i++) {
+		for (j = 0; j < NODES; j++)
+			insert(nodes + j, &root);
+		for (j = 0; j < NODES; j++)
+			erase(nodes + j, &root);
+	}
+
+	time2 = get_cycles();
+	time = time2 - time1;
+
+	time = div_u64(time, PERF_LOOPS);
+	printk(" -> %llu cycles\n", time);
+
+	for (i = 0; i < CHECK_LOOPS; i++) {
+		init();
+		for (j = 0; j < NODES; j++) {
+			check(j);
+			insert(nodes + j, &root);
+		}
+		for (j = 0; j < NODES; j++) {
+			check(NODES - j);
+			erase(nodes + j, &root);
+		}
+		check(0);
+	}
+
+	return -EAGAIN; /* Fail will directly unload the module */
+}
+
+static void rbtree_test_exit(void)
+{
+	printk(KERN_ALERT "test exit\n");
+}
+
+module_init(rbtree_test_init)
+module_exit(rbtree_test_exit)
+
+MODULE_LICENSE("GPL");
+MODULE_AUTHOR("Michel Lespinasse");
+MODULE_DESCRIPTION("Red Black Tree test");
-- 
1.7.7.3

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

[PATCH 06/13] rbtree: break out of rb_insert_color loop after tree rotation

[Michel Lespinasse]

It is a well known property of rbtrees that insertion never requires
more than two tree rotations.  In our implementation, after one loop
iteration identified one or two necessary tree rotations, we would iterate
and look for more.  However at that point the node's parent would always
be black, which would cause us to exit the loop.

We can make the code flow more obvious by just adding a break statement
after the tree rotations, where we know we are done.  Additionally, in the
cases where two tree rotations are necessary, we don't have to update the
'node' pointer as it wouldn't be used until the next loop iteration, which
we now avoid due to this break statement.

Signed-off-by: Michel Lespinasse <walken@google.com>
---
 lib/rbtree.c |   14 ++++----------
 1 files changed, 4 insertions(+), 10 deletions(-)

diff --git a/lib/rbtree.c b/lib/rbtree.c
index d0ec339..19bee6c 100644
--- a/lib/rbtree.c
+++ b/lib/rbtree.c
@@ -109,18 +109,15 @@ void rb_insert_color(struct rb_node *node, struct rb_root *root)
 				}
 			}
 
-			if (parent->rb_right == node)
-			{
-				register struct rb_node *tmp;
+			if (parent->rb_right == node) {
 				__rb_rotate_left(parent, root);
-				tmp = parent;
 				parent = node;
-				node = tmp;
 			}
 
 			rb_set_black(parent);
 			rb_set_red(gparent);
 			__rb_rotate_right(gparent, root);
+			break;
 		} else {
 			{
 				register struct rb_node *uncle = gparent->rb_left;
@@ -134,18 +131,15 @@ void rb_insert_color(struct rb_node *node, struct rb_root *root)
 				}
 			}
 
-			if (parent->rb_left == node)
-			{
-				register struct rb_node *tmp;
+			if (parent->rb_left == node) {
 				__rb_rotate_right(parent, root);
-				tmp = parent;
 				parent = node;
-				node = tmp;
 			}
 
 			rb_set_black(parent);
 			rb_set_red(gparent);
 			__rb_rotate_left(gparent, root);
+			break;
 		}
 	}
 
-- 
1.7.7.3

[PATCH 06/13] rbtree: break out of rb_insert_color loop after tree rotation

[Michel Lespinasse]

It is a well known property of rbtrees that insertion never requires
more than two tree rotations.  In our implementation, after one loop
iteration identified one or two necessary tree rotations, we would iterate
and look for more.  However at that point the node's parent would always
be black, which would cause us to exit the loop.

We can make the code flow more obvious by just adding a break statement
after the tree rotations, where we know we are done.  Additionally, in the
cases where two tree rotations are necessary, we don't have to update the
'node' pointer as it wouldn't be used until the next loop iteration, which
we now avoid due to this break statement.

Signed-off-by: Michel Lespinasse <walken@google.com>
---
 lib/rbtree.c |   14 ++++----------
 1 files changed, 4 insertions(+), 10 deletions(-)

diff --git a/lib/rbtree.c b/lib/rbtree.c
index d0ec339..19bee6c 100644
--- a/lib/rbtree.c
+++ b/lib/rbtree.c
@@ -109,18 +109,15 @@ void rb_insert_color(struct rb_node *node, struct rb_root *root)
 				}
 			}
 
-			if (parent->rb_right == node)
-			{
-				register struct rb_node *tmp;
+			if (parent->rb_right == node) {
 				__rb_rotate_left(parent, root);
-				tmp = parent;
 				parent = node;
-				node = tmp;
 			}
 
 			rb_set_black(parent);
 			rb_set_red(gparent);
 			__rb_rotate_right(gparent, root);
+			break;
 		} else {
 			{
 				register struct rb_node *uncle = gparent->rb_left;
@@ -134,18 +131,15 @@ void rb_insert_color(struct rb_node *node, struct rb_root *root)
 				}
 			}
 
-			if (parent->rb_left == node)
-			{
-				register struct rb_node *tmp;
+			if (parent->rb_left == node) {
 				__rb_rotate_right(parent, root);
-				tmp = parent;
 				parent = node;
-				node = tmp;
 			}
 
 			rb_set_black(parent);
 			rb_set_red(gparent);
 			__rb_rotate_left(gparent, root);
+			break;
 		}
 	}
 
-- 
1.7.7.3

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

[PATCH 07/13] rbtree: adjust root color in rb_insert_color() only when necessary

[Michel Lespinasse]

The root node of an rbtree must always be black. However, rb_insert_color()
only needs to maintain this invariant when it has been broken - that is,
when it exits the loop due to the current (red) node being the root.
In all other cases (exiting after tree rotations, or exiting due to
an existing black parent) the invariant is already satisfied, so there
is no need to adjust the root node color.

Signed-off-by: Michel Lespinasse <walken@google.com>
---
 lib/rbtree.c |   19 +++++++++++++++----
 1 files changed, 15 insertions(+), 4 deletions(-)

diff --git a/lib/rbtree.c b/lib/rbtree.c
index 19bee6c..0d9d184 100644
--- a/lib/rbtree.c
+++ b/lib/rbtree.c
@@ -91,8 +91,21 @@ void rb_insert_color(struct rb_node *node, struct rb_root *root)
 {
 	struct rb_node *parent, *gparent;
 
-	while ((parent = rb_parent(node)) && rb_is_red(parent))
-	{
+	while (true) {
+		/*
+		 * Loop invariant: node is red
+		 *
+		 * If there is a black parent, we are done.
+		 * Otherwise, take some corrective action as we don't
+		 * want a red root or two consecutive red nodes.
+		 */
+		parent = rb_parent(node);
+		if (!parent) {
+			rb_set_black(node);
+			break;
+		} else if (rb_is_black(parent))
+			break;
+
 		gparent = rb_parent(parent);
 
 		if (parent == gparent->rb_left)
@@ -142,8 +155,6 @@ void rb_insert_color(struct rb_node *node, struct rb_root *root)
 			break;
 		}
 	}
-
-	rb_set_black(root->rb_node);
 }
 EXPORT_SYMBOL(rb_insert_color);
 
-- 
1.7.7.3

[PATCH 07/13] rbtree: adjust root color in rb_insert_color() only when necessary

[Michel Lespinasse]

The root node of an rbtree must always be black. However, rb_insert_color()
only needs to maintain this invariant when it has been broken - that is,
when it exits the loop due to the current (red) node being the root.
In all other cases (exiting after tree rotations, or exiting due to
an existing black parent) the invariant is already satisfied, so there
is no need to adjust the root node color.

Signed-off-by: Michel Lespinasse <walken@google.com>
---
 lib/rbtree.c |   19 +++++++++++++++----
 1 files changed, 15 insertions(+), 4 deletions(-)

diff --git a/lib/rbtree.c b/lib/rbtree.c
index 19bee6c..0d9d184 100644
--- a/lib/rbtree.c
+++ b/lib/rbtree.c
@@ -91,8 +91,21 @@ void rb_insert_color(struct rb_node *node, struct rb_root *root)
 {
 	struct rb_node *parent, *gparent;
 
-	while ((parent = rb_parent(node)) && rb_is_red(parent))
-	{
+	while (true) {
+		/*
+		 * Loop invariant: node is red
+		 *
+		 * If there is a black parent, we are done.
+		 * Otherwise, take some corrective action as we don't
+		 * want a red root or two consecutive red nodes.
+		 */
+		parent = rb_parent(node);
+		if (!parent) {
+			rb_set_black(node);
+			break;
+		} else if (rb_is_black(parent))
+			break;
+
 		gparent = rb_parent(parent);
 
 		if (parent == gparent->rb_left)
@@ -142,8 +155,6 @@ void rb_insert_color(struct rb_node *node, struct rb_root *root)
 			break;
 		}
 	}
-
-	rb_set_black(root->rb_node);
 }
 EXPORT_SYMBOL(rb_insert_color);
 
-- 
1.7.7.3

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

[PATCH 08/13] rbtree: optimize tree rotations in rb_insert_color()

[Michel Lespinasse]

In rb_insert_color(), we can do better than calling __rb_rotate_left()
and __rb_rotate_right() to handle tree rotations: we already have
pointers to all relevant nodes, and know their colors (either because
we want to adjust it, or because we've tested it, or we can deduce it
as black due to the node proximity to a known red node). So we can
generate more efficient code by making use of the node pointers
we already have, and setting both the parent and color attributes for
nodes all at once. Also in case 2, some node attributes don't have to
be set because we know another tree rotation (case 3) will always follow
and override them.

Signed-off-by: Michel Lespinasse <walken@google.com>
---
 lib/rbtree.c |  102 ++++++++++++++++++++++++++++++++++++++++-----------------
 1 files changed, 71 insertions(+), 31 deletions(-)

diff --git a/lib/rbtree.c b/lib/rbtree.c
index 0d9d184..f668886 100644
--- a/lib/rbtree.c
+++ b/lib/rbtree.c
@@ -41,6 +41,12 @@ static inline void rb_set_color(struct rb_node *rb, int color)
 	rb->rb_parent_color = (rb->rb_parent_color & ~1) | color;
 }
 
+static inline void rb_set_parent_color(struct rb_node *rb,
+				       struct rb_node *p, int color)
+{
+	rb->rb_parent_color = (unsigned long)p | color;
+}
+
 static void __rb_rotate_left(struct rb_node *node, struct rb_root *root)
 {
 	struct rb_node *right = node->rb_right;
@@ -87,9 +93,30 @@ static void __rb_rotate_right(struct rb_node *node, struct rb_root *root)
 	rb_set_parent(node, left);
 }
 
+/*
+ * Helper function for rotations:
+ * - old's parent and color get assigned to new
+ * - old gets assigned new as a parent and 'color' as a color.
+ */
+static inline void
+__rb_rotate_set_parents(struct rb_node *old, struct rb_node *new,
+			struct rb_root *root, int color)
+{
+	struct rb_node *parent = rb_parent(old);
+	new->rb_parent_color = old->rb_parent_color;
+	rb_set_parent_color(old, new, color);
+	if (parent) {
+		if (parent->rb_left == old)
+			parent->rb_left = new;
+		else
+			parent->rb_right = new;
+	} else
+		root->rb_node = new;
+}
+
 void rb_insert_color(struct rb_node *node, struct rb_root *root)
 {
-	struct rb_node *parent, *gparent;
+	struct rb_node *parent, *gparent, *tmp;
 
 	while (true) {
 		/*
@@ -108,50 +135,63 @@ void rb_insert_color(struct rb_node *node, struct rb_root *root)
 
 		gparent = rb_parent(parent);
 
-		if (parent == gparent->rb_left)
-		{
-			{
-				register struct rb_node *uncle = gparent->rb_right;
-				if (uncle && rb_is_red(uncle))
-				{
-					rb_set_black(uncle);
-					rb_set_black(parent);
-					rb_set_red(gparent);
-					node = gparent;
-					continue;
-				}
+		if (parent == gparent->rb_left) {
+			tmp = gparent->rb_right;
+			if (tmp && rb_is_red(tmp)) {
+				/* Case 1 - color flips */
+				rb_set_black(tmp);
+				rb_set_black(parent);
+				rb_set_red(gparent);
+				node = gparent;
+				continue;
 			}
 
 			if (parent->rb_right == node) {
-				__rb_rotate_left(parent, root);
+				/* Case 2 - left rotate at parent */
+				parent->rb_right = tmp = node->rb_left;
+				node->rb_left = parent;
+				if (tmp)
+					rb_set_parent_color(tmp, parent,
+							    RB_BLACK);
+				rb_set_parent_color(parent, node, RB_RED);
 				parent = node;
 			}
 
-			rb_set_black(parent);
-			rb_set_red(gparent);
-			__rb_rotate_right(gparent, root);
+			/* Case 3 - right rotate at gparent */
+			gparent->rb_left = tmp = parent->rb_right;
+			parent->rb_right = gparent;
+			if (tmp)
+				rb_set_parent_color(tmp, gparent, RB_BLACK);
+			__rb_rotate_set_parents(gparent, parent, root, RB_RED);
 			break;
 		} else {
-			{
-				register struct rb_node *uncle = gparent->rb_left;
-				if (uncle && rb_is_red(uncle))
-				{
-					rb_set_black(uncle);
-					rb_set_black(parent);
-					rb_set_red(gparent);
-					node = gparent;
-					continue;
-				}
+			tmp = gparent->rb_left;
+			if (tmp && rb_is_red(tmp)) {
+				/* Case 1 - color flips */
+				rb_set_black(tmp);
+				rb_set_black(parent);
+				rb_set_red(gparent);
+				node = gparent;
+				continue;
 			}
 
 			if (parent->rb_left == node) {
-				__rb_rotate_right(parent, root);
+				/* Case 2 - right rotate at parent */
+				parent->rb_left = tmp = node->rb_right;
+				node->rb_right = parent;
+				if (tmp)
+					rb_set_parent_color(tmp, parent,
+							    RB_BLACK);
+				rb_set_parent_color(parent, node, RB_RED);
 				parent = node;
 			}
 
-			rb_set_black(parent);
-			rb_set_red(gparent);
-			__rb_rotate_left(gparent, root);
+			/* Case 3 - left rotate at gparent */
+			gparent->rb_right = tmp = parent->rb_left;
+			parent->rb_left = gparent;
+			if (tmp)
+				rb_set_parent_color(tmp, gparent, RB_BLACK);
+			__rb_rotate_set_parents(gparent, parent, root, RB_RED);
 			break;
 		}
 	}
-- 
1.7.7.3

[PATCH 08/13] rbtree: optimize tree rotations in rb_insert_color()

[Michel Lespinasse]

In rb_insert_color(), we can do better than calling __rb_rotate_left()
and __rb_rotate_right() to handle tree rotations: we already have
pointers to all relevant nodes, and know their colors (either because
we want to adjust it, or because we've tested it, or we can deduce it
as black due to the node proximity to a known red node). So we can
generate more efficient code by making use of the node pointers
we already have, and setting both the parent and color attributes for
nodes all at once. Also in case 2, some node attributes don't have to
be set because we know another tree rotation (case 3) will always follow
and override them.

Signed-off-by: Michel Lespinasse <walken@google.com>
---
 lib/rbtree.c |  102 ++++++++++++++++++++++++++++++++++++++++-----------------
 1 files changed, 71 insertions(+), 31 deletions(-)

diff --git a/lib/rbtree.c b/lib/rbtree.c
index 0d9d184..f668886 100644
--- a/lib/rbtree.c
+++ b/lib/rbtree.c
@@ -41,6 +41,12 @@ static inline void rb_set_color(struct rb_node *rb, int color)
 	rb->rb_parent_color = (rb->rb_parent_color & ~1) | color;
 }
 
+static inline void rb_set_parent_color(struct rb_node *rb,
+				       struct rb_node *p, int color)
+{
+	rb->rb_parent_color = (unsigned long)p | color;
+}
+
 static void __rb_rotate_left(struct rb_node *node, struct rb_root *root)
 {
 	struct rb_node *right = node->rb_right;
@@ -87,9 +93,30 @@ static void __rb_rotate_right(struct rb_node *node, struct rb_root *root)
 	rb_set_parent(node, left);
 }
 
+/*
+ * Helper function for rotations:
+ * - old's parent and color get assigned to new
+ * - old gets assigned new as a parent and 'color' as a color.
+ */
+static inline void
+__rb_rotate_set_parents(struct rb_node *old, struct rb_node *new,
+			struct rb_root *root, int color)
+{
+	struct rb_node *parent = rb_parent(old);
+	new->rb_parent_color = old->rb_parent_color;
+	rb_set_parent_color(old, new, color);
+	if (parent) {
+		if (parent->rb_left == old)
+			parent->rb_left = new;
+		else
+			parent->rb_right = new;
+	} else
+		root->rb_node = new;
+}
+
 void rb_insert_color(struct rb_node *node, struct rb_root *root)
 {
-	struct rb_node *parent, *gparent;
+	struct rb_node *parent, *gparent, *tmp;
 
 	while (true) {
 		/*
@@ -108,50 +135,63 @@ void rb_insert_color(struct rb_node *node, struct rb_root *root)
 
 		gparent = rb_parent(parent);
 
-		if (parent == gparent->rb_left)
-		{
-			{
-				register struct rb_node *uncle = gparent->rb_right;
-				if (uncle && rb_is_red(uncle))
-				{
-					rb_set_black(uncle);
-					rb_set_black(parent);
-					rb_set_red(gparent);
-					node = gparent;
-					continue;
-				}
+		if (parent == gparent->rb_left) {
+			tmp = gparent->rb_right;
+			if (tmp && rb_is_red(tmp)) {
+				/* Case 1 - color flips */
+				rb_set_black(tmp);
+				rb_set_black(parent);
+				rb_set_red(gparent);
+				node = gparent;
+				continue;
 			}
 
 			if (parent->rb_right == node) {
-				__rb_rotate_left(parent, root);
+				/* Case 2 - left rotate at parent */
+				parent->rb_right = tmp = node->rb_left;
+				node->rb_left = parent;
+				if (tmp)
+					rb_set_parent_color(tmp, parent,
+							    RB_BLACK);
+				rb_set_parent_color(parent, node, RB_RED);
 				parent = node;
 			}
 
-			rb_set_black(parent);
-			rb_set_red(gparent);
-			__rb_rotate_right(gparent, root);
+			/* Case 3 - right rotate at gparent */
+			gparent->rb_left = tmp = parent->rb_right;
+			parent->rb_right = gparent;
+			if (tmp)
+				rb_set_parent_color(tmp, gparent, RB_BLACK);
+			__rb_rotate_set_parents(gparent, parent, root, RB_RED);
 			break;
 		} else {
-			{
-				register struct rb_node *uncle = gparent->rb_left;
-				if (uncle && rb_is_red(uncle))
-				{
-					rb_set_black(uncle);
-					rb_set_black(parent);
-					rb_set_red(gparent);
-					node = gparent;
-					continue;
-				}
+			tmp = gparent->rb_left;
+			if (tmp && rb_is_red(tmp)) {
+				/* Case 1 - color flips */
+				rb_set_black(tmp);
+				rb_set_black(parent);
+				rb_set_red(gparent);
+				node = gparent;
+				continue;
 			}
 
 			if (parent->rb_left == node) {
-				__rb_rotate_right(parent, root);
+				/* Case 2 - right rotate at parent */
+				parent->rb_left = tmp = node->rb_right;
+				node->rb_right = parent;
+				if (tmp)
+					rb_set_parent_color(tmp, parent,
+							    RB_BLACK);
+				rb_set_parent_color(parent, node, RB_RED);
 				parent = node;
 			}
 
-			rb_set_black(parent);
-			rb_set_red(gparent);
-			__rb_rotate_left(gparent, root);
+			/* Case 3 - left rotate at gparent */
+			gparent->rb_right = tmp = parent->rb_left;
+			parent->rb_left = gparent;
+			if (tmp)
+				rb_set_parent_color(tmp, gparent, RB_BLACK);
+			__rb_rotate_set_parents(gparent, parent, root, RB_RED);
 			break;
 		}
 	}
-- 
1.7.7.3

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

[PATCH 09/13] rbtree: optimize color flips and parent fetching in rb_insert_color()

[Michel Lespinasse]

- Use the newly introduced rb_set_parent_color() function to flip the color
  of nodes whose parent is already known.
- Optimize rb_parent() when the node is known to be red - there is no need
  to mask out the color in that case.
- Flipping gparent's color to red requires us to fetch its rb_parent_color
  field, so we can reuse it as the parent value for the next loop iteration.

Signed-off-by: Michel Lespinasse <walken@google.com>
---
 lib/rbtree.c |   26 ++++++++++++++++----------
 1 files changed, 16 insertions(+), 10 deletions(-)

diff --git a/lib/rbtree.c b/lib/rbtree.c
index f668886..56369d8 100644
--- a/lib/rbtree.c
+++ b/lib/rbtree.c
@@ -47,6 +47,11 @@ static inline void rb_set_parent_color(struct rb_node *rb,
 	rb->rb_parent_color = (unsigned long)p | color;
 }
 
+static inline struct rb_node *rb_red_parent(struct rb_node *red)
+{
+	return (struct rb_node *)red->rb_parent_color;
+}
+
 static void __rb_rotate_left(struct rb_node *node, struct rb_root *root)
 {
 	struct rb_node *right = node->rb_right;
@@ -116,7 +121,7 @@ __rb_rotate_set_parents(struct rb_node *old, struct rb_node *new,
 
 void rb_insert_color(struct rb_node *node, struct rb_root *root)
 {
-	struct rb_node *parent, *gparent, *tmp;
+	struct rb_node *parent = rb_red_parent(node), *gparent, *tmp;
 
 	while (true) {
 		/*
@@ -126,23 +131,23 @@ void rb_insert_color(struct rb_node *node, struct rb_root *root)
 		 * Otherwise, take some corrective action as we don't
 		 * want a red root or two consecutive red nodes.
 		 */
-		parent = rb_parent(node);
 		if (!parent) {
-			rb_set_black(node);
+			rb_set_parent_color(node, NULL, RB_BLACK);
 			break;
 		} else if (rb_is_black(parent))
 			break;
 
-		gparent = rb_parent(parent);
+		gparent = rb_red_parent(parent);
 
 		if (parent == gparent->rb_left) {
 			tmp = gparent->rb_right;
 			if (tmp && rb_is_red(tmp)) {
 				/* Case 1 - color flips */
-				rb_set_black(tmp);
-				rb_set_black(parent);
-				rb_set_red(gparent);
+				rb_set_parent_color(tmp, gparent, RB_BLACK);
+				rb_set_parent_color(parent, gparent, RB_BLACK);
 				node = gparent;
+				parent = rb_parent(node);
+				rb_set_parent_color(node, parent, RB_RED);
 				continue;
 			}
 
@@ -168,10 +173,11 @@ void rb_insert_color(struct rb_node *node, struct rb_root *root)
 			tmp = gparent->rb_left;
 			if (tmp && rb_is_red(tmp)) {
 				/* Case 1 - color flips */
-				rb_set_black(tmp);
-				rb_set_black(parent);
-				rb_set_red(gparent);
+				rb_set_parent_color(tmp, gparent, RB_BLACK);
+				rb_set_parent_color(parent, gparent, RB_BLACK);
 				node = gparent;
+				parent = rb_parent(node);
+				rb_set_parent_color(node, parent, RB_RED);
 				continue;
 			}
 
-- 
1.7.7.3

[PATCH 09/13] rbtree: optimize color flips and parent fetching in rb_insert_color()

[Michel Lespinasse]

- Use the newly introduced rb_set_parent_color() function to flip the color
  of nodes whose parent is already known.
- Optimize rb_parent() when the node is known to be red - there is no need
  to mask out the color in that case.
- Flipping gparent's color to red requires us to fetch its rb_parent_color
  field, so we can reuse it as the parent value for the next loop iteration.

Signed-off-by: Michel Lespinasse <walken@google.com>
---
 lib/rbtree.c |   26 ++++++++++++++++----------
 1 files changed, 16 insertions(+), 10 deletions(-)

diff --git a/lib/rbtree.c b/lib/rbtree.c
index f668886..56369d8 100644
--- a/lib/rbtree.c
+++ b/lib/rbtree.c
@@ -47,6 +47,11 @@ static inline void rb_set_parent_color(struct rb_node *rb,
 	rb->rb_parent_color = (unsigned long)p | color;
 }
 
+static inline struct rb_node *rb_red_parent(struct rb_node *red)
+{
+	return (struct rb_node *)red->rb_parent_color;
+}
+
 static void __rb_rotate_left(struct rb_node *node, struct rb_root *root)
 {
 	struct rb_node *right = node->rb_right;
@@ -116,7 +121,7 @@ __rb_rotate_set_parents(struct rb_node *old, struct rb_node *new,
 
 void rb_insert_color(struct rb_node *node, struct rb_root *root)
 {
-	struct rb_node *parent, *gparent, *tmp;
+	struct rb_node *parent = rb_red_parent(node), *gparent, *tmp;
 
 	while (true) {
 		/*
@@ -126,23 +131,23 @@ void rb_insert_color(struct rb_node *node, struct rb_root *root)
 		 * Otherwise, take some corrective action as we don't
 		 * want a red root or two consecutive red nodes.
 		 */
-		parent = rb_parent(node);
 		if (!parent) {
-			rb_set_black(node);
+			rb_set_parent_color(node, NULL, RB_BLACK);
 			break;
 		} else if (rb_is_black(parent))
 			break;
 
-		gparent = rb_parent(parent);
+		gparent = rb_red_parent(parent);
 
 		if (parent == gparent->rb_left) {
 			tmp = gparent->rb_right;
 			if (tmp && rb_is_red(tmp)) {
 				/* Case 1 - color flips */
-				rb_set_black(tmp);
-				rb_set_black(parent);
-				rb_set_red(gparent);
+				rb_set_parent_color(tmp, gparent, RB_BLACK);
+				rb_set_parent_color(parent, gparent, RB_BLACK);
 				node = gparent;
+				parent = rb_parent(node);
+				rb_set_parent_color(node, parent, RB_RED);
 				continue;
 			}
 
@@ -168,10 +173,11 @@ void rb_insert_color(struct rb_node *node, struct rb_root *root)
 			tmp = gparent->rb_left;
 			if (tmp && rb_is_red(tmp)) {
 				/* Case 1 - color flips */
-				rb_set_black(tmp);
-				rb_set_black(parent);
-				rb_set_red(gparent);
+				rb_set_parent_color(tmp, gparent, RB_BLACK);
+				rb_set_parent_color(parent, gparent, RB_BLACK);
 				node = gparent;
+				parent = rb_parent(node);
+				rb_set_parent_color(node, parent, RB_RED);
 				continue;
 			}
 
-- 
1.7.7.3

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

[PATCH 10/13] rbtree: adjust node color in __rb_erase_color() only when necessary

[Michel Lespinasse]

In __rb_erase_color(), we were always setting a node to black after
exiting the main loop. And in one case, after fixing up the tree to
satisfy all rbtree invariants, we were setting the current node to root
just to guarantee a loop exit, at which point the root would be set to
black. However this is not necessary, as the root of an rbtree is already
known to be black. The only case where the color flip is required is when
we exit the loop due to the current node being red, and it's easiest to
just do the flip at that point instead of doing it after the loop.

Signed-off-by: Michel Lespinasse <walken@google.com>
---
 lib/rbtree.c |   28 +++++++++++++++++-----------
 1 files changed, 17 insertions(+), 11 deletions(-)

diff --git a/lib/rbtree.c b/lib/rbtree.c
index 56369d8..44cbbd5 100644
--- a/lib/rbtree.c
+++ b/lib/rbtree.c
@@ -209,10 +209,22 @@ static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,
 {
 	struct rb_node *other;
 
-	while ((!node || rb_is_black(node)) && node != root->rb_node)
-	{
-		if (parent->rb_left == node)
-		{
+	while (true) {
+		/*
+		 * Loop invariant: all leaf paths going through node have a
+		 * black node count that is 1 lower than other leaf paths.
+		 *
+		 * If node is red, we can flip it to black to adjust.
+		 * If node is the root, all leaf paths go through it.
+		 * Otherwise, we need to adjust the tree through color flips
+		 * and tree rotations as per one of the 4 cases below.
+		 */
+		if (node && rb_is_red(node)) {
+			rb_set_black(node);
+			break;
+		} else if (!parent) {
+			break;
+		} else if (parent->rb_left == node) {
 			other = parent->rb_right;
 			if (rb_is_red(other))
 			{
@@ -241,12 +253,9 @@ static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,
 				rb_set_black(parent);
 				rb_set_black(other->rb_right);
 				__rb_rotate_left(parent, root);
-				node = root->rb_node;
 				break;
 			}
-		}
-		else
-		{
+		} else {
 			other = parent->rb_left;
 			if (rb_is_red(other))
 			{
@@ -275,13 +284,10 @@ static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,
 				rb_set_black(parent);
 				rb_set_black(other->rb_left);
 				__rb_rotate_right(parent, root);
-				node = root->rb_node;
 				break;
 			}
 		}
 	}
-	if (node)
-		rb_set_black(node);
 }
 
 void rb_erase(struct rb_node *node, struct rb_root *root)
-- 
1.7.7.3

[PATCH 10/13] rbtree: adjust node color in __rb_erase_color() only when necessary

[Michel Lespinasse]

In __rb_erase_color(), we were always setting a node to black after
exiting the main loop. And in one case, after fixing up the tree to
satisfy all rbtree invariants, we were setting the current node to root
just to guarantee a loop exit, at which point the root would be set to
black. However this is not necessary, as the root of an rbtree is already
known to be black. The only case where the color flip is required is when
we exit the loop due to the current node being red, and it's easiest to
just do the flip at that point instead of doing it after the loop.

Signed-off-by: Michel Lespinasse <walken@google.com>
---
 lib/rbtree.c |   28 +++++++++++++++++-----------
 1 files changed, 17 insertions(+), 11 deletions(-)

diff --git a/lib/rbtree.c b/lib/rbtree.c
index 56369d8..44cbbd5 100644
--- a/lib/rbtree.c
+++ b/lib/rbtree.c
@@ -209,10 +209,22 @@ static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,
 {
 	struct rb_node *other;
 
-	while ((!node || rb_is_black(node)) && node != root->rb_node)
-	{
-		if (parent->rb_left == node)
-		{
+	while (true) {
+		/*
+		 * Loop invariant: all leaf paths going through node have a
+		 * black node count that is 1 lower than other leaf paths.
+		 *
+		 * If node is red, we can flip it to black to adjust.
+		 * If node is the root, all leaf paths go through it.
+		 * Otherwise, we need to adjust the tree through color flips
+		 * and tree rotations as per one of the 4 cases below.
+		 */
+		if (node && rb_is_red(node)) {
+			rb_set_black(node);
+			break;
+		} else if (!parent) {
+			break;
+		} else if (parent->rb_left == node) {
 			other = parent->rb_right;
 			if (rb_is_red(other))
 			{
@@ -241,12 +253,9 @@ static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,
 				rb_set_black(parent);
 				rb_set_black(other->rb_right);
 				__rb_rotate_left(parent, root);
-				node = root->rb_node;
 				break;
 			}
-		}
-		else
-		{
+		} else {
 			other = parent->rb_left;
 			if (rb_is_red(other))
 			{
@@ -275,13 +284,10 @@ static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,
 				rb_set_black(parent);
 				rb_set_black(other->rb_left);
 				__rb_rotate_right(parent, root);
-				node = root->rb_node;
 				break;
 			}
 		}
 	}
-	if (node)
-		rb_set_black(node);
 }
 
 void rb_erase(struct rb_node *node, struct rb_root *root)
-- 
1.7.7.3

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

[PATCH 11/13] rbtree: optimize case selection logic in __rb_erase_color()

[Michel Lespinasse]

In __rb_erase_color(), we have to select one of 3 cases depending on the
color on the 'other' node children. If both children are black, we flip
a few node colors and iterate. Otherwise, we do either one or two
tree rotations, depending on the color of the 'other' child opposite
to 'node', and then we are done.

The corresponding logic had duplicate checks for the color of the 'other'
child opposite to 'node'. It was checking it first to determine if both
children are black, and then to determine how many tree rotations are
required. Rearrange the logic to avoid that extra check.

Signed-off-by: Michel Lespinasse <walken@google.com>
---
 lib/rbtree.c |   68 +++++++++++++++++++++++++--------------------------------
 1 files changed, 30 insertions(+), 38 deletions(-)

diff --git a/lib/rbtree.c b/lib/rbtree.c
index 44cbbd5..597c1b9 100644
--- a/lib/rbtree.c
+++ b/lib/rbtree.c
@@ -233,28 +233,24 @@ static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,
 				__rb_rotate_left(parent, root);
 				other = parent->rb_right;
 			}
-			if ((!other->rb_left || rb_is_black(other->rb_left)) &&
-			    (!other->rb_right || rb_is_black(other->rb_right)))
-			{
-				rb_set_red(other);
-				node = parent;
-				parent = rb_parent(node);
-			}
-			else
-			{
-				if (!other->rb_right || rb_is_black(other->rb_right))
-				{
-					rb_set_black(other->rb_left);
+			if (!other->rb_right || rb_is_black(other->rb_right)) {
+				if (!other->rb_left ||
+				    rb_is_black(other->rb_left)) {
 					rb_set_red(other);
-					__rb_rotate_right(other, root);
-					other = parent->rb_right;
+					node = parent;
+					parent = rb_parent(node);
+					continue;
 				}
-				rb_set_color(other, rb_color(parent));
-				rb_set_black(parent);
-				rb_set_black(other->rb_right);
-				__rb_rotate_left(parent, root);
-				break;
+				rb_set_black(other->rb_left);
+				rb_set_red(other);
+				__rb_rotate_right(other, root);
+				other = parent->rb_right;
 			}
+			rb_set_color(other, rb_color(parent));
+			rb_set_black(parent);
+			rb_set_black(other->rb_right);
+			__rb_rotate_left(parent, root);
+			break;
 		} else {
 			other = parent->rb_left;
 			if (rb_is_red(other))
@@ -264,28 +260,24 @@ static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,
 				__rb_rotate_right(parent, root);
 				other = parent->rb_left;
 			}
-			if ((!other->rb_left || rb_is_black(other->rb_left)) &&
-			    (!other->rb_right || rb_is_black(other->rb_right)))
-			{
-				rb_set_red(other);
-				node = parent;
-				parent = rb_parent(node);
-			}
-			else
-			{
-				if (!other->rb_left || rb_is_black(other->rb_left))
-				{
-					rb_set_black(other->rb_right);
+			if (!other->rb_left || rb_is_black(other->rb_left)) {
+				if (!other->rb_right ||
+				    rb_is_black(other->rb_right)) {
 					rb_set_red(other);
-					__rb_rotate_left(other, root);
-					other = parent->rb_left;
+					node = parent;
+					parent = rb_parent(node);
+					continue;
 				}
-				rb_set_color(other, rb_color(parent));
-				rb_set_black(parent);
-				rb_set_black(other->rb_left);
-				__rb_rotate_right(parent, root);
-				break;
+				rb_set_black(other->rb_right);
+				rb_set_red(other);
+				__rb_rotate_left(other, root);
+				other = parent->rb_left;
 			}
+			rb_set_color(other, rb_color(parent));
+			rb_set_black(parent);
+			rb_set_black(other->rb_left);
+			__rb_rotate_right(parent, root);
+			break;
 		}
 	}
 }
-- 
1.7.7.3

[PATCH 11/13] rbtree: optimize case selection logic in __rb_erase_color()

[Michel Lespinasse]

In __rb_erase_color(), we have to select one of 3 cases depending on the
color on the 'other' node children. If both children are black, we flip
a few node colors and iterate. Otherwise, we do either one or two
tree rotations, depending on the color of the 'other' child opposite
to 'node', and then we are done.

The corresponding logic had duplicate checks for the color of the 'other'
child opposite to 'node'. It was checking it first to determine if both
children are black, and then to determine how many tree rotations are
required. Rearrange the logic to avoid that extra check.

Signed-off-by: Michel Lespinasse <walken@google.com>
---
 lib/rbtree.c |   68 +++++++++++++++++++++++++--------------------------------
 1 files changed, 30 insertions(+), 38 deletions(-)

diff --git a/lib/rbtree.c b/lib/rbtree.c
index 44cbbd5..597c1b9 100644
--- a/lib/rbtree.c
+++ b/lib/rbtree.c
@@ -233,28 +233,24 @@ static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,
 				__rb_rotate_left(parent, root);
 				other = parent->rb_right;
 			}
-			if ((!other->rb_left || rb_is_black(other->rb_left)) &&
-			    (!other->rb_right || rb_is_black(other->rb_right)))
-			{
-				rb_set_red(other);
-				node = parent;
-				parent = rb_parent(node);
-			}
-			else
-			{
-				if (!other->rb_right || rb_is_black(other->rb_right))
-				{
-					rb_set_black(other->rb_left);
+			if (!other->rb_right || rb_is_black(other->rb_right)) {
+				if (!other->rb_left ||
+				    rb_is_black(other->rb_left)) {
 					rb_set_red(other);
-					__rb_rotate_right(other, root);
-					other = parent->rb_right;
+					node = parent;
+					parent = rb_parent(node);
+					continue;
 				}
-				rb_set_color(other, rb_color(parent));
-				rb_set_black(parent);
-				rb_set_black(other->rb_right);
-				__rb_rotate_left(parent, root);
-				break;
+				rb_set_black(other->rb_left);
+				rb_set_red(other);
+				__rb_rotate_right(other, root);
+				other = parent->rb_right;
 			}
+			rb_set_color(other, rb_color(parent));
+			rb_set_black(parent);
+			rb_set_black(other->rb_right);
+			__rb_rotate_left(parent, root);
+			break;
 		} else {
 			other = parent->rb_left;
 			if (rb_is_red(other))
@@ -264,28 +260,24 @@ static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,
 				__rb_rotate_right(parent, root);
 				other = parent->rb_left;
 			}
-			if ((!other->rb_left || rb_is_black(other->rb_left)) &&
-			    (!other->rb_right || rb_is_black(other->rb_right)))
-			{
-				rb_set_red(other);
-				node = parent;
-				parent = rb_parent(node);
-			}
-			else
-			{
-				if (!other->rb_left || rb_is_black(other->rb_left))
-				{
-					rb_set_black(other->rb_right);
+			if (!other->rb_left || rb_is_black(other->rb_left)) {
+				if (!other->rb_right ||
+				    rb_is_black(other->rb_right)) {
 					rb_set_red(other);
-					__rb_rotate_left(other, root);
-					other = parent->rb_left;
+					node = parent;
+					parent = rb_parent(node);
+					continue;
 				}
-				rb_set_color(other, rb_color(parent));
-				rb_set_black(parent);
-				rb_set_black(other->rb_left);
-				__rb_rotate_right(parent, root);
-				break;
+				rb_set_black(other->rb_right);
+				rb_set_red(other);
+				__rb_rotate_left(other, root);
+				other = parent->rb_left;
 			}
+			rb_set_color(other, rb_color(parent));
+			rb_set_black(parent);
+			rb_set_black(other->rb_left);
+			__rb_rotate_right(parent, root);
+			break;
 		}
 	}
 }
-- 
1.7.7.3

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

[PATCH 12/13] rbtree: optimize tree rotations in __rb_erase_color()

[Michel Lespinasse]

In __rb_erase_color(), we often already have pointers to the nodes
being rotated and/or know what their colors must be, so we can
generate more efficient code than the generic __rb_rotate_left()
and __rb_rotate_right() functions.

Signed-off-by: Michel Lespinasse <walken@google.com>
---
 lib/rbtree.c |  154 ++++++++++++++++++++++++---------------------------------
 1 files changed, 65 insertions(+), 89 deletions(-)

diff --git a/lib/rbtree.c b/lib/rbtree.c
index 597c1b9..c956248 100644
--- a/lib/rbtree.c
+++ b/lib/rbtree.c
@@ -36,10 +36,6 @@ static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p)
 {
 	rb->rb_parent_color = (rb->rb_parent_color & 3) | (unsigned long)p;
 }
-static inline void rb_set_color(struct rb_node *rb, int color)
-{
-	rb->rb_parent_color = (rb->rb_parent_color & ~1) | color;
-}
 
 static inline void rb_set_parent_color(struct rb_node *rb,
 				       struct rb_node *p, int color)
@@ -52,52 +48,6 @@ static inline struct rb_node *rb_red_parent(struct rb_node *red)
 	return (struct rb_node *)red->rb_parent_color;
 }
 
-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))
-		rb_set_parent(right->rb_left, node);
-	right->rb_left = node;
-
-	rb_set_parent(right, parent);
-
-	if (parent)
-	{
-		if (node == parent->rb_left)
-			parent->rb_left = right;
-		else
-			parent->rb_right = right;
-	}
-	else
-		root->rb_node = 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))
-		rb_set_parent(left->rb_right, node);
-	left->rb_right = node;
-
-	rb_set_parent(left, parent);
-
-	if (parent)
-	{
-		if (node == parent->rb_right)
-			parent->rb_right = left;
-		else
-			parent->rb_left = left;
-	}
-	else
-		root->rb_node = left;
-	rb_set_parent(node, left);
-}
-
 /*
  * Helper function for rotations:
  * - old's parent and color get assigned to new
@@ -207,7 +157,7 @@ EXPORT_SYMBOL(rb_insert_color);
 static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,
 			     struct rb_root *root)
 {
-	struct rb_node *other;
+	struct rb_node *sibling, *tmp1, *tmp2;
 
 	while (true) {
 		/*
@@ -225,58 +175,84 @@ static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,
 		} else if (!parent) {
 			break;
 		} else if (parent->rb_left == node) {
-			other = parent->rb_right;
-			if (rb_is_red(other))
-			{
-				rb_set_black(other);
-				rb_set_red(parent);
-				__rb_rotate_left(parent, root);
-				other = parent->rb_right;
+			sibling = parent->rb_right;
+			if (rb_is_red(sibling)) {
+				/* Case 1 - left rotate at parent */
+				parent->rb_right = tmp1 = sibling->rb_left;
+				sibling->rb_left = parent;
+				rb_set_parent_color(tmp1, parent, RB_BLACK);
+				__rb_rotate_set_parents(parent, sibling, root,
+							RB_RED);
+				sibling = tmp1;
 			}
-			if (!other->rb_right || rb_is_black(other->rb_right)) {
-				if (!other->rb_left ||
-				    rb_is_black(other->rb_left)) {
-					rb_set_red(other);
+			tmp1 = sibling->rb_right;
+			if (!tmp1 || rb_is_black(tmp1)) {
+				tmp2 = sibling->rb_left;
+				if (!tmp2 || rb_is_black(tmp2)) {
+					/* Case 2 - sibling color flip */
+					rb_set_red(sibling);
 					node = parent;
 					parent = rb_parent(node);
 					continue;
 				}
-				rb_set_black(other->rb_left);
-				rb_set_red(other);
-				__rb_rotate_right(other, root);
-				other = parent->rb_right;
+				/* Case 3 - right rotate at sibling */
+				sibling->rb_left = tmp1 = tmp2->rb_right;
+				tmp2->rb_right = sibling;
+				parent->rb_right = tmp2;
+				if (tmp1)
+					rb_set_parent_color(tmp1, sibling,
+							    RB_BLACK);
+				tmp1 = sibling;
+				sibling = tmp2;
 			}
-			rb_set_color(other, rb_color(parent));
-			rb_set_black(parent);
-			rb_set_black(other->rb_right);
-			__rb_rotate_left(parent, root);
+			/* Case 4 - left rotate at parent + color flips */
+			parent->rb_right = tmp2 = sibling->rb_left;
+			sibling->rb_left = parent;
+			rb_set_parent_color(tmp1, sibling, RB_BLACK);
+			if (tmp2)
+				rb_set_parent(tmp2, parent);
+			__rb_rotate_set_parents(parent, sibling, root,
+						RB_BLACK);
 			break;
 		} else {
-			other = parent->rb_left;
-			if (rb_is_red(other))
-			{
-				rb_set_black(other);
-				rb_set_red(parent);
-				__rb_rotate_right(parent, root);
-				other = parent->rb_left;
+			sibling = parent->rb_left;
+			if (rb_is_red(sibling)) {
+				/* Case 1 - right rotate at parent */
+				parent->rb_left = tmp1 = sibling->rb_right;
+				sibling->rb_right = parent;
+				rb_set_parent_color(tmp1, parent, RB_BLACK);
+				__rb_rotate_set_parents(parent, sibling, root,
+							RB_RED);
+				sibling = tmp1;
 			}
-			if (!other->rb_left || rb_is_black(other->rb_left)) {
-				if (!other->rb_right ||
-				    rb_is_black(other->rb_right)) {
-					rb_set_red(other);
+			tmp1 = sibling->rb_left;
+			if (!tmp1 || rb_is_black(tmp1)) {
+				tmp2 = sibling->rb_right;
+				if (!tmp2 || rb_is_black(tmp2)) {
+					/* Case 2 - sibling color flip */
+					rb_set_red(sibling);
 					node = parent;
 					parent = rb_parent(node);
 					continue;
 				}
-				rb_set_black(other->rb_right);
-				rb_set_red(other);
-				__rb_rotate_left(other, root);
-				other = parent->rb_left;
+				/* Case 3 - right rotate at sibling */
+				sibling->rb_right = tmp1 = tmp2->rb_left;
+				tmp2->rb_left = sibling;
+				parent->rb_left = tmp2;
+				if (tmp1)
+					rb_set_parent_color(tmp1, sibling,
+							    RB_BLACK);
+				tmp1 = sibling;
+				sibling = tmp2;
 			}
-			rb_set_color(other, rb_color(parent));
-			rb_set_black(parent);
-			rb_set_black(other->rb_left);
-			__rb_rotate_right(parent, root);
+			/* Case 4 - left rotate at parent + color flips */
+			parent->rb_left = tmp2 = sibling->rb_right;
+			sibling->rb_right = parent;
+			rb_set_parent_color(tmp1, sibling, RB_BLACK);
+			if (tmp2)
+				rb_set_parent(tmp2, parent);
+			__rb_rotate_set_parents(parent, sibling, root,
+						RB_BLACK);
 			break;
 		}
 	}
-- 
1.7.7.3

[PATCH 12/13] rbtree: optimize tree rotations in __rb_erase_color()

[Michel Lespinasse]

In __rb_erase_color(), we often already have pointers to the nodes
being rotated and/or know what their colors must be, so we can
generate more efficient code than the generic __rb_rotate_left()
and __rb_rotate_right() functions.

Signed-off-by: Michel Lespinasse <walken@google.com>
---
 lib/rbtree.c |  154 ++++++++++++++++++++++++---------------------------------
 1 files changed, 65 insertions(+), 89 deletions(-)

diff --git a/lib/rbtree.c b/lib/rbtree.c
index 597c1b9..c956248 100644
--- a/lib/rbtree.c
+++ b/lib/rbtree.c
@@ -36,10 +36,6 @@ static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p)
 {
 	rb->rb_parent_color = (rb->rb_parent_color & 3) | (unsigned long)p;
 }
-static inline void rb_set_color(struct rb_node *rb, int color)
-{
-	rb->rb_parent_color = (rb->rb_parent_color & ~1) | color;
-}
 
 static inline void rb_set_parent_color(struct rb_node *rb,
 				       struct rb_node *p, int color)
@@ -52,52 +48,6 @@ static inline struct rb_node *rb_red_parent(struct rb_node *red)
 	return (struct rb_node *)red->rb_parent_color;
 }
 
-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))
-		rb_set_parent(right->rb_left, node);
-	right->rb_left = node;
-
-	rb_set_parent(right, parent);
-
-	if (parent)
-	{
-		if (node == parent->rb_left)
-			parent->rb_left = right;
-		else
-			parent->rb_right = right;
-	}
-	else
-		root->rb_node = 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))
-		rb_set_parent(left->rb_right, node);
-	left->rb_right = node;
-
-	rb_set_parent(left, parent);
-
-	if (parent)
-	{
-		if (node == parent->rb_right)
-			parent->rb_right = left;
-		else
-			parent->rb_left = left;
-	}
-	else
-		root->rb_node = left;
-	rb_set_parent(node, left);
-}
-
 /*
  * Helper function for rotations:
  * - old's parent and color get assigned to new
@@ -207,7 +157,7 @@ EXPORT_SYMBOL(rb_insert_color);
 static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,
 			     struct rb_root *root)
 {
-	struct rb_node *other;
+	struct rb_node *sibling, *tmp1, *tmp2;
 
 	while (true) {
 		/*
@@ -225,58 +175,84 @@ static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,
 		} else if (!parent) {
 			break;
 		} else if (parent->rb_left == node) {
-			other = parent->rb_right;
-			if (rb_is_red(other))
-			{
-				rb_set_black(other);
-				rb_set_red(parent);
-				__rb_rotate_left(parent, root);
-				other = parent->rb_right;
+			sibling = parent->rb_right;
+			if (rb_is_red(sibling)) {
+				/* Case 1 - left rotate at parent */
+				parent->rb_right = tmp1 = sibling->rb_left;
+				sibling->rb_left = parent;
+				rb_set_parent_color(tmp1, parent, RB_BLACK);
+				__rb_rotate_set_parents(parent, sibling, root,
+							RB_RED);
+				sibling = tmp1;
 			}
-			if (!other->rb_right || rb_is_black(other->rb_right)) {
-				if (!other->rb_left ||
-				    rb_is_black(other->rb_left)) {
-					rb_set_red(other);
+			tmp1 = sibling->rb_right;
+			if (!tmp1 || rb_is_black(tmp1)) {
+				tmp2 = sibling->rb_left;
+				if (!tmp2 || rb_is_black(tmp2)) {
+					/* Case 2 - sibling color flip */
+					rb_set_red(sibling);
 					node = parent;
 					parent = rb_parent(node);
 					continue;
 				}
-				rb_set_black(other->rb_left);
-				rb_set_red(other);
-				__rb_rotate_right(other, root);
-				other = parent->rb_right;
+				/* Case 3 - right rotate at sibling */
+				sibling->rb_left = tmp1 = tmp2->rb_right;
+				tmp2->rb_right = sibling;
+				parent->rb_right = tmp2;
+				if (tmp1)
+					rb_set_parent_color(tmp1, sibling,
+							    RB_BLACK);
+				tmp1 = sibling;
+				sibling = tmp2;
 			}
-			rb_set_color(other, rb_color(parent));
-			rb_set_black(parent);
-			rb_set_black(other->rb_right);
-			__rb_rotate_left(parent, root);
+			/* Case 4 - left rotate at parent + color flips */
+			parent->rb_right = tmp2 = sibling->rb_left;
+			sibling->rb_left = parent;
+			rb_set_parent_color(tmp1, sibling, RB_BLACK);
+			if (tmp2)
+				rb_set_parent(tmp2, parent);
+			__rb_rotate_set_parents(parent, sibling, root,
+						RB_BLACK);
 			break;
 		} else {
-			other = parent->rb_left;
-			if (rb_is_red(other))
-			{
-				rb_set_black(other);
-				rb_set_red(parent);
-				__rb_rotate_right(parent, root);
-				other = parent->rb_left;
+			sibling = parent->rb_left;
+			if (rb_is_red(sibling)) {
+				/* Case 1 - right rotate at parent */
+				parent->rb_left = tmp1 = sibling->rb_right;
+				sibling->rb_right = parent;
+				rb_set_parent_color(tmp1, parent, RB_BLACK);
+				__rb_rotate_set_parents(parent, sibling, root,
+							RB_RED);
+				sibling = tmp1;
 			}
-			if (!other->rb_left || rb_is_black(other->rb_left)) {
-				if (!other->rb_right ||
-				    rb_is_black(other->rb_right)) {
-					rb_set_red(other);
+			tmp1 = sibling->rb_left;
+			if (!tmp1 || rb_is_black(tmp1)) {
+				tmp2 = sibling->rb_right;
+				if (!tmp2 || rb_is_black(tmp2)) {
+					/* Case 2 - sibling color flip */
+					rb_set_red(sibling);
 					node = parent;
 					parent = rb_parent(node);
 					continue;
 				}
-				rb_set_black(other->rb_right);
-				rb_set_red(other);
-				__rb_rotate_left(other, root);
-				other = parent->rb_left;
+				/* Case 3 - right rotate at sibling */
+				sibling->rb_right = tmp1 = tmp2->rb_left;
+				tmp2->rb_left = sibling;
+				parent->rb_left = tmp2;
+				if (tmp1)
+					rb_set_parent_color(tmp1, sibling,
+							    RB_BLACK);
+				tmp1 = sibling;
+				sibling = tmp2;
 			}
-			rb_set_color(other, rb_color(parent));
-			rb_set_black(parent);
-			rb_set_black(other->rb_left);
-			__rb_rotate_right(parent, root);
+			/* Case 4 - left rotate at parent + color flips */
+			parent->rb_left = tmp2 = sibling->rb_right;
+			sibling->rb_right = parent;
+			rb_set_parent_color(tmp1, sibling, RB_BLACK);
+			if (tmp2)
+				rb_set_parent(tmp2, parent);
+			__rb_rotate_set_parents(parent, sibling, root,
+						RB_BLACK);
 			break;
 		}
 	}
-- 
1.7.7.3

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

[PATCH 13/13] rbtree: optimize color flips in __rb_erase_color()

[Michel Lespinasse]

In __rb_erase_color(), when the current node is red or when flipping
the sibling's color, the parent is already known so we can use the
more efficient rb_set_parent_color() function to set the desired color.

Signed-off-by: Michel Lespinasse <walken@google.com>
---
 lib/rbtree.c |   10 +++++-----
 1 files changed, 5 insertions(+), 5 deletions(-)

diff --git a/lib/rbtree.c b/lib/rbtree.c
index c956248..f8c1a75 100644
--- a/lib/rbtree.c
+++ b/lib/rbtree.c
@@ -29,8 +29,6 @@
 #define rb_color(r)   ((r)->rb_parent_color & 1)
 #define rb_is_red(r)   (!rb_color(r))
 #define rb_is_black(r) rb_color(r)
-#define rb_set_red(r)  do { (r)->rb_parent_color &= ~1; } while (0)
-#define rb_set_black(r)  do { (r)->rb_parent_color |= 1; } while (0)
 
 static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p)
 {
@@ -170,7 +168,7 @@ static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,
 		 * and tree rotations as per one of the 4 cases below.
 		 */
 		if (node && rb_is_red(node)) {
-			rb_set_black(node);
+			rb_set_parent_color(node, parent, RB_BLACK);
 			break;
 		} else if (!parent) {
 			break;
@@ -190,7 +188,8 @@ static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,
 				tmp2 = sibling->rb_left;
 				if (!tmp2 || rb_is_black(tmp2)) {
 					/* Case 2 - sibling color flip */
-					rb_set_red(sibling);
+					rb_set_parent_color(sibling, parent,
+							    RB_RED);
 					node = parent;
 					parent = rb_parent(node);
 					continue;
@@ -230,7 +229,8 @@ static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,
 				tmp2 = sibling->rb_right;
 				if (!tmp2 || rb_is_black(tmp2)) {
 					/* Case 2 - sibling color flip */
-					rb_set_red(sibling);
+					rb_set_parent_color(sibling, parent,
+							    RB_RED);
 					node = parent;
 					parent = rb_parent(node);
 					continue;
-- 
1.7.7.3

[PATCH 13/13] rbtree: optimize color flips in __rb_erase_color()

[Michel Lespinasse]

In __rb_erase_color(), when the current node is red or when flipping
the sibling's color, the parent is already known so we can use the
more efficient rb_set_parent_color() function to set the desired color.

Signed-off-by: Michel Lespinasse <walken@google.com>
---
 lib/rbtree.c |   10 +++++-----
 1 files changed, 5 insertions(+), 5 deletions(-)

diff --git a/lib/rbtree.c b/lib/rbtree.c
index c956248..f8c1a75 100644
--- a/lib/rbtree.c
+++ b/lib/rbtree.c
@@ -29,8 +29,6 @@
 #define rb_color(r)   ((r)->rb_parent_color & 1)
 #define rb_is_red(r)   (!rb_color(r))
 #define rb_is_black(r) rb_color(r)
-#define rb_set_red(r)  do { (r)->rb_parent_color &= ~1; } while (0)
-#define rb_set_black(r)  do { (r)->rb_parent_color |= 1; } while (0)
 
 static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p)
 {
@@ -170,7 +168,7 @@ static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,
 		 * and tree rotations as per one of the 4 cases below.
 		 */
 		if (node && rb_is_red(node)) {
-			rb_set_black(node);
+			rb_set_parent_color(node, parent, RB_BLACK);
 			break;
 		} else if (!parent) {
 			break;
@@ -190,7 +188,8 @@ static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,
 				tmp2 = sibling->rb_left;
 				if (!tmp2 || rb_is_black(tmp2)) {
 					/* Case 2 - sibling color flip */
-					rb_set_red(sibling);
+					rb_set_parent_color(sibling, parent,
+							    RB_RED);
 					node = parent;
 					parent = rb_parent(node);
 					continue;
@@ -230,7 +229,8 @@ static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,
 				tmp2 = sibling->rb_right;
 				if (!tmp2 || rb_is_black(tmp2)) {
 					/* Case 2 - sibling color flip */
-					rb_set_red(sibling);
+					rb_set_parent_color(sibling, parent,
+							    RB_RED);
 					node = parent;
 					parent = rb_parent(node);
 					continue;
-- 
1.7.7.3

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [PATCH 01/13] rbtree: reference Documentation/rbtree.txt for usage instructions

[Rik van Riel]

On 07/09/2012 07:35 PM, Michel Lespinasse wrote:
> include/linux/rbtree.h included some basic usage instructions, while
> Documentation/rbtree.txt had some more complete and easier to follow
> instructions.  Replacing the former with a reference to the latter.
>
> Signed-off-by: Michel Lespinasse<walken@google.com>

Acked-by: Rik van Riel <riel@redhat.com>

-- 
All rights reversed

Re: [PATCH 01/13] rbtree: reference Documentation/rbtree.txt for usage instructions

[Rik van Riel]

On 07/09/2012 07:35 PM, Michel Lespinasse wrote:
> include/linux/rbtree.h included some basic usage instructions, while
> Documentation/rbtree.txt had some more complete and easier to follow
> instructions.  Replacing the former with a reference to the latter.
>
> Signed-off-by: Michel Lespinasse<walken@google.com>

Acked-by: Rik van Riel <riel@redhat.com>

-- 
All rights reversed

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [PATCH 02/13] rbtree: empty nodes have no color

[Daniel Santos]

On 07/09/2012 06:35 PM, Michel Lespinasse wrote:
> Empty nodes have no color.  We can make use of this property to
> simplify the code emitted by the RB_EMPTY_NODE and RB_CLEAR_NODE
> macros.  Also, we can get rid of the rb_init_node function which had
> been introduced by commit 88d19cf37952a7e1e38b2bf87a00f0e857e63180
> to avoid some issue with the empty node's color not being initialized.
Oh sweet, very glad to see this.  I'm addressing a fairly large scope of
things in my patches and I didn't want to address this yet, so I'm glad
somebody has. :)  I *hoped* that gcc would figure out some of the
excesses of rb_init_node and and just set rb_parent_color directly to
the node address, but better to have actually fixed.  As far as
RB_EMPTY_NODE, I am using that in my test code (which I haven't posted
yet) since I'm testing the actual integrity of a tree and a set of
objects after performing insertions & such on it.  I'm also using it in
some new CONFIG_RBTREE_DEBUG-enabled code.
> I'm not sure what the RB_EMPTY_NODE checks in rb_prev() / rb_next()
> are doing there, though. axboe introduced them in commit 10fd48f2376d.
> The way I see it, the 'empty node' abstraction is only used by rbtree
> users to flag nodes that they haven't inserted in any rbtree, so asking
> the predecessor or successor of such nodes doesn't make any sense.
>
> One final rb_init_node() caller was recently added in sysctl code
> to implement faster sysctl name lookups. This code doesn't make use
> of RB_EMPTY_NODE at all, and from what I could see it only called
> rb_init_node() under the mistaken assumption that such initialization
> was required before node insertion.
That was one of the problems with rb_init_node().  Not being documented,
one would assume it's needed unless you study the code more closely.

BTW, the current revision of my patches adds some doc comments to struct
rb_node since the actual function of rb_parent_color isn't very clear
without a lot of study.

/**
 * struct rb_node
 * @rb_parent_color: Contains the color in the lower 2 bits (although
only bit
 *              zero is currently used) and the address of the parent in
 *              the rest (lower 2 bits of address should always be zero on
 *              any arch supported).  If the node is initialized and not a
 *              member of any tree, the parent point to its self.  If the
 *              node belongs to a tree, but is the root element, the
 *              parent will be NULL.  Otherwise, parent will always
 *              point to the parent node in the tree.
 * @rb_right:        Pointer to the right element.
 * @rb_left:         Pointer to the left element.
 */

That said, there's an extra bit in the rb_parent_color that can be used
for some future purpose.

Daniel

Re: [PATCH 02/13] rbtree: empty nodes have no color

[Daniel Santos]

On 07/09/2012 06:35 PM, Michel Lespinasse wrote:
> Empty nodes have no color.  We can make use of this property to
> simplify the code emitted by the RB_EMPTY_NODE and RB_CLEAR_NODE
> macros.  Also, we can get rid of the rb_init_node function which had
> been introduced by commit 88d19cf37952a7e1e38b2bf87a00f0e857e63180
> to avoid some issue with the empty node's color not being initialized.
Oh sweet, very glad to see this.  I'm addressing a fairly large scope of
things in my patches and I didn't want to address this yet, so I'm glad
somebody has. :)  I *hoped* that gcc would figure out some of the
excesses of rb_init_node and and just set rb_parent_color directly to
the node address, but better to have actually fixed.  As far as
RB_EMPTY_NODE, I am using that in my test code (which I haven't posted
yet) since I'm testing the actual integrity of a tree and a set of
objects after performing insertions & such on it.  I'm also using it in
some new CONFIG_RBTREE_DEBUG-enabled code.
> I'm not sure what the RB_EMPTY_NODE checks in rb_prev() / rb_next()
> are doing there, though. axboe introduced them in commit 10fd48f2376d.
> The way I see it, the 'empty node' abstraction is only used by rbtree
> users to flag nodes that they haven't inserted in any rbtree, so asking
> the predecessor or successor of such nodes doesn't make any sense.
>
> One final rb_init_node() caller was recently added in sysctl code
> to implement faster sysctl name lookups. This code doesn't make use
> of RB_EMPTY_NODE at all, and from what I could see it only called
> rb_init_node() under the mistaken assumption that such initialization
> was required before node insertion.
That was one of the problems with rb_init_node().  Not being documented,
one would assume it's needed unless you study the code more closely.

BTW, the current revision of my patches adds some doc comments to struct
rb_node since the actual function of rb_parent_color isn't very clear
without a lot of study.

/**
 * struct rb_node
 * @rb_parent_color: Contains the color in the lower 2 bits (although
only bit
 *              zero is currently used) and the address of the parent in
 *              the rest (lower 2 bits of address should always be zero on
 *              any arch supported).  If the node is initialized and not a
 *              member of any tree, the parent point to its self.  If the
 *              node belongs to a tree, but is the root element, the
 *              parent will be NULL.  Otherwise, parent will always
 *              point to the parent node in the tree.
 * @rb_right:        Pointer to the right element.
 * @rb_left:         Pointer to the left element.
 */

That said, there's an extra bit in the rb_parent_color that can be used
for some future purpose.

Daniel

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [PATCH 04/13] rbtree: move some implementation details from rbtree.h to rbtree.c

[Michal Nazarewicz]

On Tue, 10 Jul 2012 01:35:14 +0200, Michel Lespinasse <walken@google.com> wrote:

> rbtree users must use the documented APIs to manipulate the tree
> structure.  Low-level helpers to manipulate node colors and parenthood
> are not part of that API, so move them to lib/rbtree.c
>
> Signed-off-by: Michel Lespinasse <walken@google.com>
> ---
>  include/linux/rbtree.h |   16 ----------------
>  lib/rbtree.c           |   18 ++++++++++++++++++
>  2 files changed, 18 insertions(+), 16 deletions(-)
>
> diff --git a/include/linux/rbtree.h b/include/linux/rbtree.h
> index 2049087..a06c044 100644
> --- a/include/linux/rbtree.h
> +++ b/include/linux/rbtree.h
> @@ -35,8 +35,6 @@
>  struct rb_node
>  {
>  	unsigned long  rb_parent_color;
> -#define	RB_RED		0
> -#define	RB_BLACK	1
>  	struct rb_node *rb_right;
>  	struct rb_node *rb_left;
>  } __attribute__((aligned(sizeof(long))));
> @@ -49,20 +47,6 @@ struct rb_root
> #define rb_parent(r)   ((struct rb_node *)((r)->rb_parent_color & ~3))
> -#define rb_color(r)   ((r)->rb_parent_color & 1)
> -#define rb_is_red(r)   (!rb_color(r))
> -#define rb_is_black(r) rb_color(r)
> -#define rb_set_red(r)  do { (r)->rb_parent_color &= ~1; } while (0)
> -#define rb_set_black(r)  do { (r)->rb_parent_color |= 1; } while (0)
> -
> -static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p)
> -{
> -	rb->rb_parent_color = (rb->rb_parent_color & 3) | (unsigned long)p;
> -}
> -static inline void rb_set_color(struct rb_node *rb, int color)
> -{
> -	rb->rb_parent_color = (rb->rb_parent_color & ~1) | color;
> -}
> #define RB_ROOT	(struct rb_root) { NULL, }
>  #define	rb_entry(ptr, type, member) container_of(ptr, type, member)
> diff --git a/lib/rbtree.c b/lib/rbtree.c
> index fe43c8c..d0ec339 100644
> --- a/lib/rbtree.c
> +++ b/lib/rbtree.c
> @@ -23,6 +23,24 @@
>  #include <linux/rbtree.h>
>  #include <linux/export.h>
>+#define	RB_RED		0
> +#define	RB_BLACK	1

Interestingly, those are almost never used. RB_BLACK is used only once.
Should we get rid of those instead?  Or change the code (like rb_is_red())
to use them?

> +
> +#define rb_color(r)   ((r)->rb_parent_color & 1)
> +#define rb_is_red(r)   (!rb_color(r))
> +#define rb_is_black(r) rb_color(r)
> +#define rb_set_red(r)  do { (r)->rb_parent_color &= ~1; } while (0)
> +#define rb_set_black(r)  do { (r)->rb_parent_color |= 1; } while (0)
> +
> +static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p)
> +{
> +	rb->rb_parent_color = (rb->rb_parent_color & 3) | (unsigned long)p;
> +}
> +static inline void rb_set_color(struct rb_node *rb, int color)
> +{
> +	rb->rb_parent_color = (rb->rb_parent_color & ~1) | color;
> +}
> +
>  static void __rb_rotate_left(struct rb_node *node, struct rb_root *root)
>  {
>  	struct rb_node *right = node->rb_right;


-- 
Best regards,                                         _     _
.o. | Liege of Serenely Enlightened Majesty of      o' \,=./ `o
..o | Computer Science,  Michał “mina86” Nazarewicz    (o o)
ooo +----<email/xmpp: mpn@google.com>--------------ooO--(_)--Ooo--

Re: [PATCH 04/13] rbtree: move some implementation details from rbtree.h to rbtree.c

[Michal Nazarewicz]

On Tue, 10 Jul 2012 01:35:14 +0200, Michel Lespinasse <walken@google.com> wrote:

> rbtree users must use the documented APIs to manipulate the tree
> structure.  Low-level helpers to manipulate node colors and parenthood
> are not part of that API, so move them to lib/rbtree.c
>
> Signed-off-by: Michel Lespinasse <walken@google.com>
> ---
>  include/linux/rbtree.h |   16 ----------------
>  lib/rbtree.c           |   18 ++++++++++++++++++
>  2 files changed, 18 insertions(+), 16 deletions(-)
>
> diff --git a/include/linux/rbtree.h b/include/linux/rbtree.h
> index 2049087..a06c044 100644
> --- a/include/linux/rbtree.h
> +++ b/include/linux/rbtree.h
> @@ -35,8 +35,6 @@
>  struct rb_node
>  {
>  	unsigned long  rb_parent_color;
> -#define	RB_RED		0
> -#define	RB_BLACK	1
>  	struct rb_node *rb_right;
>  	struct rb_node *rb_left;
>  } __attribute__((aligned(sizeof(long))));
> @@ -49,20 +47,6 @@ struct rb_root
> #define rb_parent(r)   ((struct rb_node *)((r)->rb_parent_color & ~3))
> -#define rb_color(r)   ((r)->rb_parent_color & 1)
> -#define rb_is_red(r)   (!rb_color(r))
> -#define rb_is_black(r) rb_color(r)
> -#define rb_set_red(r)  do { (r)->rb_parent_color &= ~1; } while (0)
> -#define rb_set_black(r)  do { (r)->rb_parent_color |= 1; } while (0)
> -
> -static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p)
> -{
> -	rb->rb_parent_color = (rb->rb_parent_color & 3) | (unsigned long)p;
> -}
> -static inline void rb_set_color(struct rb_node *rb, int color)
> -{
> -	rb->rb_parent_color = (rb->rb_parent_color & ~1) | color;
> -}
> #define RB_ROOT	(struct rb_root) { NULL, }
>  #define	rb_entry(ptr, type, member) container_of(ptr, type, member)
> diff --git a/lib/rbtree.c b/lib/rbtree.c
> index fe43c8c..d0ec339 100644
> --- a/lib/rbtree.c
> +++ b/lib/rbtree.c
> @@ -23,6 +23,24 @@
>  #include <linux/rbtree.h>
>  #include <linux/export.h>
>+#define	RB_RED		0
> +#define	RB_BLACK	1

Interestingly, those are almost never used. RB_BLACK is used only once.
Should we get rid of those instead?  Or change the code (like rb_is_red())
to use them?

> +
> +#define rb_color(r)   ((r)->rb_parent_color & 1)
> +#define rb_is_red(r)   (!rb_color(r))
> +#define rb_is_black(r) rb_color(r)
> +#define rb_set_red(r)  do { (r)->rb_parent_color &= ~1; } while (0)
> +#define rb_set_black(r)  do { (r)->rb_parent_color |= 1; } while (0)
> +
> +static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p)
> +{
> +	rb->rb_parent_color = (rb->rb_parent_color & 3) | (unsigned long)p;
> +}
> +static inline void rb_set_color(struct rb_node *rb, int color)
> +{
> +	rb->rb_parent_color = (rb->rb_parent_color & ~1) | color;
> +}
> +
>  static void __rb_rotate_left(struct rb_node *node, struct rb_root *root)
>  {
>  	struct rb_node *right = node->rb_right;


-- 
Best regards,                                         _     _
.o. | Liege of Serenely Enlightened Majesty of      o' \,=./ `o
..o | Computer Science,  Michał “mina86” Nazarewicz    (o o)
ooo +----<email/xmpp: mpn@google.com>--------------ooO--(_)--Ooo--

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [PATCH 05/13] rbtree: performance and correctness test

[Michal Nazarewicz]

On Tue, 10 Jul 2012 01:35:15 +0200, Michel Lespinasse <walken@google.com> wrote:

> This small module helps measure the performance of rbtree insert and erase.
>
> Additionally, we run a few correctness tests to check that the rbtrees have
> all desired properties:
> - contains the right number of nodes in the order desired,
> - never two consecutive red nodes on any path,
> - all paths to leaf nodes have the same number of black nodes,
> - root node is black
>
> Signed-off-by: Michel Lespinasse <walken@google.com>
> ---
>  tests/rbtree_test.c |  135 +++++++++++++++++++++++++++++++++++++++++++++++++++
>  1 files changed, 135 insertions(+), 0 deletions(-)
>  create mode 100644 tests/rbtree_test.c
>
> diff --git a/tests/rbtree_test.c b/tests/rbtree_test.c
> new file mode 100644
> index 0000000..2e3944d
> --- /dev/null
> +++ b/tests/rbtree_test.c
> @@ -0,0 +1,135 @@
> +#include <linux/module.h>
> +#include <linux/rbtree.h>
> +#include <linux/random.h>
> +#include <asm/timex.h>
> +
> +#define NODES       100
> +#define PERF_LOOPS  100000
> +#define CHECK_LOOPS 100
> +
> +struct test_node {
> +	struct rb_node rb;
> +	u32 key;
> +};
> +
> +static struct rb_root root = RB_ROOT;
> +static struct test_node nodes[NODES];
> +
> +static struct rnd_state rnd;
> +
> +static void insert(struct test_node *node, struct rb_root *root)
> +{
> +	struct rb_node **new = &root->rb_node, *parent = NULL;
> +
> +	while (*new) {
> +		parent = *new;
> +		if (node->key < rb_entry(parent, struct test_node, rb)->key)
> +			new = &parent->rb_left;
> +		else
> +			new = &parent->rb_right;
> +	}
> +
> +	rb_link_node(&node->rb, parent, new);
> +	rb_insert_color(&node->rb, root);
> +}
> +
> +static inline void erase(struct test_node *node, struct rb_root *root)
> +{
> +	rb_erase(&node->rb, root);
> +}
> +
> +static void init(void)
> +{
> +	int i;
> +	for (i = 0; i < NODES; i++)

s/NODES/ARRAY_SIZE(nodes)/ perhaps?  Same goes for the rest of the code.

> +		nodes[i].key = prandom32(&rnd);
> +}
> +
> +static bool is_red(struct rb_node *rb)
> +{
> +	return rb->rb_parent_color == (unsigned long)rb_parent(rb);

Why not !(rb->rb_parent_color & 1) which to me seems more intuitive.

> +}
> +
> +static int black_path_count(struct rb_node *rb)
> +{
> +	int count;
> +	for (count = 0; rb; rb = rb_parent(rb))
> +		count += !is_red(rb);
> +	return count;
> +}
> +
> +static void check(int nr_nodes)
> +{
> +	struct rb_node *rb;
> +	int count = 0;
> +	int blacks;
> +	u32 prev_key = 0;
> +
> +	for (rb = rb_first(&root); rb; rb = rb_next(rb)) {
> +		struct test_node *node = rb_entry(rb, struct test_node, rb);
> +		WARN_ON_ONCE(node->key < prev_key);

What if for some reason we generate node with key equal zero or two keys
with the same value?  It may not be the case for current code, but someone
might change it in the future.  I think <= is safer here.

> +		WARN_ON_ONCE(is_red(rb) &&
> +			     (!rb_parent(rb) || is_red(rb_parent(rb))));
> +		if (!count)
> +			blacks = black_path_count(rb);
> +		else
> +			WARN_ON_ONCE((!rb->rb_left || !rb->rb_right) &&
> +				     blacks != black_path_count(rb));
> +		prev_key = node->key;
> +		count++;
> +	}
> +	WARN_ON_ONCE(count != nr_nodes);
> +}
> +
> +static int rbtree_test_init(void)
> +{
> +	int i, j;
> +	cycles_t time1, time2, time;
> +
> +	printk(KERN_ALERT "rbtree testing");
> +
> +	prandom32_seed(&rnd, 3141592653589793238);
> +	init();
> +
> +	time1 = get_cycles();
> +
> +	for (i = 0; i < PERF_LOOPS; i++) {
> +		for (j = 0; j < NODES; j++)
> +			insert(nodes + j, &root);
> +		for (j = 0; j < NODES; j++)
> +			erase(nodes + j, &root);
> +	}
> +
> +	time2 = get_cycles();
> +	time = time2 - time1;
> +
> +	time = div_u64(time, PERF_LOOPS);
> +	printk(" -> %llu cycles\n", time);
> +
> +	for (i = 0; i < CHECK_LOOPS; i++) {
> +		init();

Is this init() needed?

> +		for (j = 0; j < NODES; j++) {
> +			check(j);
> +			insert(nodes + j, &root);
> +		}
> +		for (j = 0; j < NODES; j++) {
> +			check(NODES - j);
> +			erase(nodes + j, &root);
> +		}
> +		check(0);
> +	}
> +
> +	return -EAGAIN; /* Fail will directly unload the module */
> +}

-- 
Best regards,                                         _     _
.o. | Liege of Serenely Enlightened Majesty of      o' \,=./ `o
..o | Computer Science,  Michał “mina86” Nazarewicz    (o o)
ooo +----<email/xmpp: mpn@google.com>--------------ooO--(_)--Ooo--

Re: [PATCH 05/13] rbtree: performance and correctness test

[Michal Nazarewicz]

On Tue, 10 Jul 2012 01:35:15 +0200, Michel Lespinasse <walken@google.com> wrote:

> This small module helps measure the performance of rbtree insert and erase.
>
> Additionally, we run a few correctness tests to check that the rbtrees have
> all desired properties:
> - contains the right number of nodes in the order desired,
> - never two consecutive red nodes on any path,
> - all paths to leaf nodes have the same number of black nodes,
> - root node is black
>
> Signed-off-by: Michel Lespinasse <walken@google.com>
> ---
>  tests/rbtree_test.c |  135 +++++++++++++++++++++++++++++++++++++++++++++++++++
>  1 files changed, 135 insertions(+), 0 deletions(-)
>  create mode 100644 tests/rbtree_test.c
>
> diff --git a/tests/rbtree_test.c b/tests/rbtree_test.c
> new file mode 100644
> index 0000000..2e3944d
> --- /dev/null
> +++ b/tests/rbtree_test.c
> @@ -0,0 +1,135 @@
> +#include <linux/module.h>
> +#include <linux/rbtree.h>
> +#include <linux/random.h>
> +#include <asm/timex.h>
> +
> +#define NODES       100
> +#define PERF_LOOPS  100000
> +#define CHECK_LOOPS 100
> +
> +struct test_node {
> +	struct rb_node rb;
> +	u32 key;
> +};
> +
> +static struct rb_root root = RB_ROOT;
> +static struct test_node nodes[NODES];
> +
> +static struct rnd_state rnd;
> +
> +static void insert(struct test_node *node, struct rb_root *root)
> +{
> +	struct rb_node **new = &root->rb_node, *parent = NULL;
> +
> +	while (*new) {
> +		parent = *new;
> +		if (node->key < rb_entry(parent, struct test_node, rb)->key)
> +			new = &parent->rb_left;
> +		else
> +			new = &parent->rb_right;
> +	}
> +
> +	rb_link_node(&node->rb, parent, new);
> +	rb_insert_color(&node->rb, root);
> +}
> +
> +static inline void erase(struct test_node *node, struct rb_root *root)
> +{
> +	rb_erase(&node->rb, root);
> +}
> +
> +static void init(void)
> +{
> +	int i;
> +	for (i = 0; i < NODES; i++)

s/NODES/ARRAY_SIZE(nodes)/ perhaps?  Same goes for the rest of the code.

> +		nodes[i].key = prandom32(&rnd);
> +}
> +
> +static bool is_red(struct rb_node *rb)
> +{
> +	return rb->rb_parent_color == (unsigned long)rb_parent(rb);

Why not !(rb->rb_parent_color & 1) which to me seems more intuitive.

> +}
> +
> +static int black_path_count(struct rb_node *rb)
> +{
> +	int count;
> +	for (count = 0; rb; rb = rb_parent(rb))
> +		count += !is_red(rb);
> +	return count;
> +}
> +
> +static void check(int nr_nodes)
> +{
> +	struct rb_node *rb;
> +	int count = 0;
> +	int blacks;
> +	u32 prev_key = 0;
> +
> +	for (rb = rb_first(&root); rb; rb = rb_next(rb)) {
> +		struct test_node *node = rb_entry(rb, struct test_node, rb);
> +		WARN_ON_ONCE(node->key < prev_key);

What if for some reason we generate node with key equal zero or two keys
with the same value?  It may not be the case for current code, but someone
might change it in the future.  I think <= is safer here.

> +		WARN_ON_ONCE(is_red(rb) &&
> +			     (!rb_parent(rb) || is_red(rb_parent(rb))));
> +		if (!count)
> +			blacks = black_path_count(rb);
> +		else
> +			WARN_ON_ONCE((!rb->rb_left || !rb->rb_right) &&
> +				     blacks != black_path_count(rb));
> +		prev_key = node->key;
> +		count++;
> +	}
> +	WARN_ON_ONCE(count != nr_nodes);
> +}
> +
> +static int rbtree_test_init(void)
> +{
> +	int i, j;
> +	cycles_t time1, time2, time;
> +
> +	printk(KERN_ALERT "rbtree testing");
> +
> +	prandom32_seed(&rnd, 3141592653589793238);
> +	init();
> +
> +	time1 = get_cycles();
> +
> +	for (i = 0; i < PERF_LOOPS; i++) {
> +		for (j = 0; j < NODES; j++)
> +			insert(nodes + j, &root);
> +		for (j = 0; j < NODES; j++)
> +			erase(nodes + j, &root);
> +	}
> +
> +	time2 = get_cycles();
> +	time = time2 - time1;
> +
> +	time = div_u64(time, PERF_LOOPS);
> +	printk(" -> %llu cycles\n", time);
> +
> +	for (i = 0; i < CHECK_LOOPS; i++) {
> +		init();

Is this init() needed?

> +		for (j = 0; j < NODES; j++) {
> +			check(j);
> +			insert(nodes + j, &root);
> +		}
> +		for (j = 0; j < NODES; j++) {
> +			check(NODES - j);
> +			erase(nodes + j, &root);
> +		}
> +		check(0);
> +	}
> +
> +	return -EAGAIN; /* Fail will directly unload the module */
> +}

-- 
Best regards,                                         _     _
.o. | Liege of Serenely Enlightened Majesty of      o' \,=./ `o
..o | Computer Science,  Michał “mina86” Nazarewicz    (o o)
ooo +----<email/xmpp: mpn@google.com>--------------ooO--(_)--Ooo--

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [PATCH 02/13] rbtree: empty nodes have no color

[Michel Lespinasse]

On Tue, Jul 10, 2012 at 3:59 AM, Daniel Santos <danielfsantos@att.net> wrote:
>> One final rb_init_node() caller was recently added in sysctl code
>> to implement faster sysctl name lookups. This code doesn't make use
>> of RB_EMPTY_NODE at all, and from what I could see it only called
>> rb_init_node() under the mistaken assumption that such initialization
>> was required before node insertion.
> That was one of the problems with rb_init_node().  Not being documented,
> one would assume it's needed unless you study the code more closely.

Agree, the name made it sound like it was required, while it wasn't.

Looking at the code history, it's pretty clear that the function was
introduced for the wrong reasons...

> BTW, the current revision of my patches adds some doc comments to struct
> rb_node since the actual function of rb_parent_color isn't very clear
> without a lot of study.
>
> /**
>  * struct rb_node
>  * @rb_parent_color: Contains the color in the lower 2 bits (although
> only bit
>  *              zero is currently used) and the address of the parent in
>  *              the rest (lower 2 bits of address should always be zero on
>  *              any arch supported).  If the node is initialized and not a
>  *              member of any tree, the parent point to its self.  If the
>  *              node belongs to a tree, but is the root element, the
>  *              parent will be NULL.  Otherwise, parent will always
>  *              point to the parent node in the tree.
>  * @rb_right:        Pointer to the right element.
>  * @rb_left:         Pointer to the left element.
>  */
>
> That said, there's an extra bit in the rb_parent_color that can be used
> for some future purpose.

My preference would be for such comments to go into lib/rbtree.c, NOT
include/lib/rbtree.h . The reason being that we really don't want
rbtree users to start depending on rbtree internals - it's best if
they just stick to using the documented APIs :)

-- 
Michel "Walken" Lespinasse
A program is never fully debugged until the last user dies.

Re: [PATCH 02/13] rbtree: empty nodes have no color

[Michel Lespinasse]

On Tue, Jul 10, 2012 at 3:59 AM, Daniel Santos <danielfsantos@att.net> wrote:
>> One final rb_init_node() caller was recently added in sysctl code
>> to implement faster sysctl name lookups. This code doesn't make use
>> of RB_EMPTY_NODE at all, and from what I could see it only called
>> rb_init_node() under the mistaken assumption that such initialization
>> was required before node insertion.
> That was one of the problems with rb_init_node().  Not being documented,
> one would assume it's needed unless you study the code more closely.

Agree, the name made it sound like it was required, while it wasn't.

Looking at the code history, it's pretty clear that the function was
introduced for the wrong reasons...

> BTW, the current revision of my patches adds some doc comments to struct
> rb_node since the actual function of rb_parent_color isn't very clear
> without a lot of study.
>
> /**
>  * struct rb_node
>  * @rb_parent_color: Contains the color in the lower 2 bits (although
> only bit
>  *              zero is currently used) and the address of the parent in
>  *              the rest (lower 2 bits of address should always be zero on
>  *              any arch supported).  If the node is initialized and not a
>  *              member of any tree, the parent point to its self.  If the
>  *              node belongs to a tree, but is the root element, the
>  *              parent will be NULL.  Otherwise, parent will always
>  *              point to the parent node in the tree.
>  * @rb_right:        Pointer to the right element.
>  * @rb_left:         Pointer to the left element.
>  */
>
> That said, there's an extra bit in the rb_parent_color that can be used
> for some future purpose.

My preference would be for such comments to go into lib/rbtree.c, NOT
include/lib/rbtree.h . The reason being that we really don't want
rbtree users to start depending on rbtree internals - it's best if
they just stick to using the documented APIs :)

-- 
Michel "Walken" Lespinasse
A program is never fully debugged until the last user dies.

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [PATCH 04/13] rbtree: move some implementation details from rbtree.h to rbtree.c

[Michel Lespinasse]

On Tue, Jul 10, 2012 at 5:19 AM, Michal Nazarewicz <mina86@mina86.com> wrote:
> On Tue, 10 Jul 2012 01:35:14 +0200, Michel Lespinasse <walken@google.com> wrote:
>> +#define        RB_RED          0
>> +#define        RB_BLACK        1
>
> Interestingly, those are almost never used. RB_BLACK is used only once.
> Should we get rid of those instead?  Or change the code (like rb_is_red())
> to use them?

I'm actually making heavier use of RB_RED / RB_BLACK later on in the patch set.
But agree, rb_is_red() / rb_is_black() could use these too.

-- 
Michel "Walken" Lespinasse
A program is never fully debugged until the last user dies.

Re: [PATCH 04/13] rbtree: move some implementation details from rbtree.h to rbtree.c

[Michel Lespinasse]

On Tue, Jul 10, 2012 at 5:19 AM, Michal Nazarewicz <mina86@mina86.com> wrote:
> On Tue, 10 Jul 2012 01:35:14 +0200, Michel Lespinasse <walken@google.com> wrote:
>> +#define        RB_RED          0
>> +#define        RB_BLACK        1
>
> Interestingly, those are almost never used. RB_BLACK is used only once.
> Should we get rid of those instead?  Or change the code (like rb_is_red())
> to use them?

I'm actually making heavier use of RB_RED / RB_BLACK later on in the patch set.
But agree, rb_is_red() / rb_is_black() could use these too.

-- 
Michel "Walken" Lespinasse
A program is never fully debugged until the last user dies.

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [PATCH 05/13] rbtree: performance and correctness test

[Michel Lespinasse]

On Tue, Jul 10, 2012 at 5:27 AM, Michal Nazarewicz <mina86@mina86.com> wrote:
> On Tue, 10 Jul 2012 01:35:15 +0200, Michel Lespinasse <walken@google.com> wrote:
>> +       for (i = 0; i < CHECK_LOOPS; i++) {
>> +               init();
>
> Is this init() needed?

So, the reasoning here is that we first have timed loops, where we
don't init between every iteration because it's not needed. Then we
have checked loops, where we init nodes between every iteration so
that they'll have new contents, and then check the rbtree invariants
after each insertion or erase. The init isn't required in the checked
loop either, but it should improve the test coverage a little. It'd be
pointless to run the checked loop more than once if we didn't init...

-- 
Michel "Walken" Lespinasse
A program is never fully debugged until the last user dies.

Re: [PATCH 05/13] rbtree: performance and correctness test

[Michel Lespinasse]

On Tue, Jul 10, 2012 at 5:27 AM, Michal Nazarewicz <mina86@mina86.com> wrote:
> On Tue, 10 Jul 2012 01:35:15 +0200, Michel Lespinasse <walken@google.com> wrote:
>> +       for (i = 0; i < CHECK_LOOPS; i++) {
>> +               init();
>
> Is this init() needed?

So, the reasoning here is that we first have timed loops, where we
don't init between every iteration because it's not needed. Then we
have checked loops, where we init nodes between every iteration so
that they'll have new contents, and then check the rbtree invariants
after each insertion or erase. The init isn't required in the checked
loop either, but it should improve the test coverage a little. It'd be
pointless to run the checked loop more than once if we didn't init...

-- 
Michel "Walken" Lespinasse
A program is never fully debugged until the last user dies.

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [PATCH 05/13] rbtree: performance and correctness test

[Michel Lespinasse]

On Tue, Jul 10, 2012 at 5:27 AM, Michal Nazarewicz <mina86@mina86.com> wrote:
> On Tue, 10 Jul 2012 01:35:15 +0200, Michel Lespinasse <walken@google.com> wrote:
>> +       u32 prev_key = 0;
>> +
>> +       for (rb = rb_first(&root); rb; rb = rb_next(rb)) {
>> +               struct test_node *node = rb_entry(rb, struct test_node,
>> rb);
>> +               WARN_ON_ONCE(node->key < prev_key);
>
> What if for some reason we generate node with key equal zero or two keys
> with the same value?  It may not be the case for current code, but someone
> might change it in the future.  I think <= is safer here.

No, it's not illegal for two nodes to have the same key; the second
one to be inserted will just get placed after the first one. The
rbtree library doesn't care either way as it's not even aware of the
key values :)

-- 
Michel "Walken" Lespinasse
A program is never fully debugged until the last user dies.

Re: [PATCH 05/13] rbtree: performance and correctness test

[Michel Lespinasse]

On Tue, Jul 10, 2012 at 5:27 AM, Michal Nazarewicz <mina86@mina86.com> wrote:
> On Tue, 10 Jul 2012 01:35:15 +0200, Michel Lespinasse <walken@google.com> wrote:
>> +       u32 prev_key = 0;
>> +
>> +       for (rb = rb_first(&root); rb; rb = rb_next(rb)) {
>> +               struct test_node *node = rb_entry(rb, struct test_node,
>> rb);
>> +               WARN_ON_ONCE(node->key < prev_key);
>
> What if for some reason we generate node with key equal zero or two keys
> with the same value?  It may not be the case for current code, but someone
> might change it in the future.  I think <= is safer here.

No, it's not illegal for two nodes to have the same key; the second
one to be inserted will just get placed after the first one. The
rbtree library doesn't care either way as it's not even aware of the
key values :)

-- 
Michel "Walken" Lespinasse
A program is never fully debugged until the last user dies.

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [PATCH 00/13] rbtree updates

[Peter Zijlstra]

Looks nice.. How about something like the below on top.. I couldn't
immediately find a sane reason for the grand-parent to always be red in
the insertion case.

---
--- a/lib/rbtree.c
+++ b/lib/rbtree.c
@@ -23,6 +23,25 @@
 #include <linux/rbtree.h>
 #include <linux/export.h>
 
+/*
+ * red-black trees properties:  http://en.wikipedia.org/wiki/Rbtree
+ *
+ *  1) A node is either red or black
+ *  2) The root is black
+ *  3) All leaves (NULL) are black
+ *  4) Both children of every red node are black
+ *  5) Every simple path from a given node to any of its descendant leaves
+ *     contains the same number of black nodes.
+ *
+ *  4 and 5 give the O(log n) guarantee, since 4 implies you cannot have two
+ *  consecutive red nodes in a path and every red node is therefore followed by
+ *  a black. So if B is the number of black nodes on every simple path (as per
+ *  5), then the longest possible path due to 4 is 2B.
+ *
+ *  We shall indicate color with case, where black nodes are uppercase and red
+ *  nodes will be lowercase.
+ */
+
 #define	RB_RED		0
 #define	RB_BLACK	1
 
@@ -85,12 +104,27 @@ void rb_insert_color(struct rb_node *nod
 		} else if (rb_is_black(parent))
 			break;
 
+		/*
+		 * XXX
+		 */
 		gparent = rb_red_parent(parent);
 
 		if (parent == gparent->rb_left) {
 			tmp = gparent->rb_right;
 			if (tmp && rb_is_red(tmp)) {
-				/* Case 1 - color flips */
+				/* 
+				 * Case 1 - color flips
+				 *
+				 *       G            g
+				 *      / \          / \
+				 *     p   u  -->   P   U
+				 *    /            /
+				 *   n            N
+				 *
+				 * However, since g's parent might be red, and
+				 * 4) does not allow this, we need to recurse
+				 * at g.
+				 */
 				rb_set_parent_color(tmp, gparent, RB_BLACK);
 				rb_set_parent_color(parent, gparent, RB_BLACK);
 				node = gparent;
@@ -100,17 +134,35 @@ void rb_insert_color(struct rb_node *nod
 			}
 
 			if (parent->rb_right == node) {
-				/* Case 2 - left rotate at parent */
+				/* 
+				 * Case 2 - left rotate at parent
+				 *
+				 *      G             G
+				 *     / \           / \
+				 *    p   U  -->    n   U
+				 *     \           /
+				 *      n         p
+				 *
+				 * This still leaves us in violation of 4), the
+				 * continuation into Case 3 will fix that.
+				 */
 				parent->rb_right = tmp = node->rb_left;
 				node->rb_left = parent;
 				if (tmp)
-					rb_set_parent_color(tmp, parent,
-							    RB_BLACK);
+					rb_set_parent_color(tmp, parent, RB_BLACK);
 				rb_set_parent_color(parent, node, RB_RED);
 				parent = node;
 			}
 
-			/* Case 3 - right rotate at gparent */
+			/* 
+			 * Case 3 - right rotate at gparent
+			 *
+			 *        G           P
+			 *       / \         / \
+			 *      p   U  -->  n   g
+			 *     /                 \
+			 *    n                   U
+			 */
 			gparent->rb_left = tmp = parent->rb_right;
 			parent->rb_right = gparent;
 			if (tmp)
@@ -134,8 +186,7 @@ void rb_insert_color(struct rb_node *nod
 				parent->rb_left = tmp = node->rb_right;
 				node->rb_right = parent;
 				if (tmp)
-					rb_set_parent_color(tmp, parent,
-							    RB_BLACK);
+					rb_set_parent_color(tmp, parent, RB_BLACK);
 				rb_set_parent_color(parent, node, RB_RED);
 				parent = node;
 			}
@@ -175,43 +226,75 @@ static void __rb_erase_color(struct rb_n
 		} else if (parent->rb_left == node) {
 			sibling = parent->rb_right;
 			if (rb_is_red(sibling)) {
-				/* Case 1 - left rotate at parent */
+				/* 
+				 * Case 1 - left rotate at parent
+				 *
+				 *     P               S
+				 *    / \             / \
+				 *   N   s    -->    p   Sr
+				 *      / \         / \
+				 *     Sl  Sr      N   Sl
+				 */
 				parent->rb_right = tmp1 = sibling->rb_left;
 				sibling->rb_left = parent;
 				rb_set_parent_color(tmp1, parent, RB_BLACK);
-				__rb_rotate_set_parents(parent, sibling, root,
-							RB_RED);
+				__rb_rotate_set_parents(parent, sibling, root, RB_RED);
 				sibling = tmp1;
 			}
 			tmp1 = sibling->rb_right;
 			if (!tmp1 || rb_is_black(tmp1)) {
 				tmp2 = sibling->rb_left;
 				if (!tmp2 || rb_is_black(tmp2)) {
-					/* Case 2 - sibling color flip */
-					rb_set_parent_color(sibling, parent,
-							    RB_RED);
+					/* 
+					 * Case 2 - sibling color flip
+					 *
+					 *     P             P
+					 *    / \           / \
+					 *   N   S    -->  N   s
+					 *      / \           / \
+					 *     Sl  Sr        Sl  Sr
+					 *
+					 * This leaves us violating 5), recurse at p.
+					 */
+					rb_set_parent_color(sibling, parent, RB_RED);
 					node = parent;
 					parent = rb_parent(node);
 					continue;
 				}
-				/* Case 3 - right rotate at sibling */
+				/* 
+				 * Case 3 - right rotate at sibling 
+				 *
+				 *    P             P
+				 *   / \           / \
+				 *  N   S    -->  N   sl
+				 *     / \           / \
+				 *    sl  Sr        1   S
+				 *   / \               / \
+				 *  1   2             2   Sr
+				 */
 				sibling->rb_left = tmp1 = tmp2->rb_right;
 				tmp2->rb_right = sibling;
 				parent->rb_right = tmp2;
 				if (tmp1)
-					rb_set_parent_color(tmp1, sibling,
-							    RB_BLACK);
+					rb_set_parent_color(tmp1, sibling, RB_BLACK);
 				tmp1 = sibling;
 				sibling = tmp2;
 			}
-			/* Case 4 - left rotate at parent + color flips */
+			/* 
+			 * Case 4 - left rotate at parent + color flips 
+			 *
+			 *       P               S
+			 *      / \             / \
+			 *     N   S     -->   P   Sr
+			 *        / \         / \
+			 *       Sl  Sr      N   Sl
+			 */
 			parent->rb_right = tmp2 = sibling->rb_left;
 			sibling->rb_left = parent;
 			rb_set_parent_color(tmp1, sibling, RB_BLACK);
 			if (tmp2)
 				rb_set_parent(tmp2, parent);
-			__rb_rotate_set_parents(parent, sibling, root,
-						RB_BLACK);
+			__rb_rotate_set_parents(parent, sibling, root, RB_BLACK);
 			break;
 		} else {
 			sibling = parent->rb_left;
@@ -220,8 +303,7 @@ static void __rb_erase_color(struct rb_n
 				parent->rb_left = tmp1 = sibling->rb_right;
 				sibling->rb_right = parent;
 				rb_set_parent_color(tmp1, parent, RB_BLACK);
-				__rb_rotate_set_parents(parent, sibling, root,
-							RB_RED);
+				__rb_rotate_set_parents(parent, sibling, root, RB_RED);
 				sibling = tmp1;
 			}
 			tmp1 = sibling->rb_left;
@@ -229,8 +311,7 @@ static void __rb_erase_color(struct rb_n
 				tmp2 = sibling->rb_right;
 				if (!tmp2 || rb_is_black(tmp2)) {
 					/* Case 2 - sibling color flip */
-					rb_set_parent_color(sibling, parent,
-							    RB_RED);
+					rb_set_parent_color(sibling, parent, RB_RED);
 					node = parent;
 					parent = rb_parent(node);
 					continue;
@@ -240,8 +321,7 @@ static void __rb_erase_color(struct rb_n
 				tmp2->rb_left = sibling;
 				parent->rb_left = tmp2;
 				if (tmp1)
-					rb_set_parent_color(tmp1, sibling,
-							    RB_BLACK);
+					rb_set_parent_color(tmp1, sibling, RB_BLACK);
 				tmp1 = sibling;
 				sibling = tmp2;
 			}
@@ -251,8 +331,7 @@ static void __rb_erase_color(struct rb_n
 			rb_set_parent_color(tmp1, sibling, RB_BLACK);
 			if (tmp2)
 				rb_set_parent(tmp2, parent);
-			__rb_rotate_set_parents(parent, sibling, root,
-						RB_BLACK);
+			__rb_rotate_set_parents(parent, sibling, root, RB_BLACK);
 			break;
 		}
 	}
@@ -267,8 +346,7 @@ void rb_erase(struct rb_node *node, stru
 		child = node->rb_right;
 	else if (!node->rb_right)
 		child = node->rb_left;
-	else
-	{
+	else {
 		struct rb_node *old = node, *left;
 
 		node = node->rb_right;
@@ -310,17 +388,15 @@ void rb_erase(struct rb_node *node, stru
 
 	if (child)
 		rb_set_parent(child, parent);
-	if (parent)
-	{
+	if (parent) {
 		if (parent->rb_left == node)
 			parent->rb_left = child;
 		else
 			parent->rb_right = child;
-	}
-	else
+	} else
 		root->rb_node = child;
 
- color:
+color:
 	if (color == RB_BLACK)
 		__rb_erase_color(child, parent, root);
 }
@@ -433,8 +509,10 @@ struct rb_node *rb_next(const struct rb_
 	if (RB_EMPTY_NODE(node))
 		return NULL;
 
-	/* If we have a right-hand child, go down and then left as far
-	   as we can. */
+	/* 
+	 * If we have a right-hand child, go down and then left as far as we
+	 * can. 
+	 */
 	if (node->rb_right) {
 		node = node->rb_right; 
 		while (node->rb_left)
@@ -442,12 +520,13 @@ struct rb_node *rb_next(const struct rb_
 		return (struct rb_node *)node;
 	}
 
-	/* No right-hand children.  Everything down and left is
-	   smaller than us, so any 'next' node must be in the general
-	   direction of our parent. Go up the tree; any time the
-	   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. */
+	/* 
+	 * No right-hand children. Everything down and left is smaller than
+	 * us, so any 'next' node must be in the general direction of our
+	 * parent. Go up the tree; any time the 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 ((parent = rb_parent(node)) && node == parent->rb_right)
 		node = parent;
 
@@ -462,8 +541,10 @@ struct rb_node *rb_prev(const struct rb_
 	if (RB_EMPTY_NODE(node))
 		return NULL;
 
-	/* If we have a left-hand child, go down and then right as far
-	   as we can. */
+	/* 
+	 * If we have a left-hand child, go down and then right as far as we
+	 * can. 
+	 */
 	if (node->rb_left) {
 		node = node->rb_left; 
 		while (node->rb_right)
@@ -471,8 +552,10 @@ struct rb_node *rb_prev(const struct rb_
 		return (struct rb_node *)node;
 	}
 
-	/* No left-hand children. Go up till we find an ancestor which
-	   is a right-hand child of its parent */
+	/*
+	 * No left-hand children. Go up till we find an ancestor which is a
+	 * right-hand child of its parent 
+	 */
 	while ((parent = rb_parent(node)) && node == parent->rb_left)
 		node = parent;
 

Re: [PATCH 00/13] rbtree updates

[Peter Zijlstra]

Looks nice.. How about something like the below on top.. I couldn't
immediately find a sane reason for the grand-parent to always be red in
the insertion case.

---
--- a/lib/rbtree.c
+++ b/lib/rbtree.c
@@ -23,6 +23,25 @@
 #include <linux/rbtree.h>
 #include <linux/export.h>
 
+/*
+ * red-black trees properties:  http://en.wikipedia.org/wiki/Rbtree
+ *
+ *  1) A node is either red or black
+ *  2) The root is black
+ *  3) All leaves (NULL) are black
+ *  4) Both children of every red node are black
+ *  5) Every simple path from a given node to any of its descendant leaves
+ *     contains the same number of black nodes.
+ *
+ *  4 and 5 give the O(log n) guarantee, since 4 implies you cannot have two
+ *  consecutive red nodes in a path and every red node is therefore followed by
+ *  a black. So if B is the number of black nodes on every simple path (as per
+ *  5), then the longest possible path due to 4 is 2B.
+ *
+ *  We shall indicate color with case, where black nodes are uppercase and red
+ *  nodes will be lowercase.
+ */
+
 #define	RB_RED		0
 #define	RB_BLACK	1
 
@@ -85,12 +104,27 @@ void rb_insert_color(struct rb_node *nod
 		} else if (rb_is_black(parent))
 			break;
 
+		/*
+		 * XXX
+		 */
 		gparent = rb_red_parent(parent);
 
 		if (parent == gparent->rb_left) {
 			tmp = gparent->rb_right;
 			if (tmp && rb_is_red(tmp)) {
-				/* Case 1 - color flips */
+				/* 
+				 * Case 1 - color flips
+				 *
+				 *       G            g
+				 *      / \          / \
+				 *     p   u  -->   P   U
+				 *    /            /
+				 *   n            N
+				 *
+				 * However, since g's parent might be red, and
+				 * 4) does not allow this, we need to recurse
+				 * at g.
+				 */
 				rb_set_parent_color(tmp, gparent, RB_BLACK);
 				rb_set_parent_color(parent, gparent, RB_BLACK);
 				node = gparent;
@@ -100,17 +134,35 @@ void rb_insert_color(struct rb_node *nod
 			}
 
 			if (parent->rb_right == node) {
-				/* Case 2 - left rotate at parent */
+				/* 
+				 * Case 2 - left rotate at parent
+				 *
+				 *      G             G
+				 *     / \           / \
+				 *    p   U  -->    n   U
+				 *     \           /
+				 *      n         p
+				 *
+				 * This still leaves us in violation of 4), the
+				 * continuation into Case 3 will fix that.
+				 */
 				parent->rb_right = tmp = node->rb_left;
 				node->rb_left = parent;
 				if (tmp)
-					rb_set_parent_color(tmp, parent,
-							    RB_BLACK);
+					rb_set_parent_color(tmp, parent, RB_BLACK);
 				rb_set_parent_color(parent, node, RB_RED);
 				parent = node;
 			}
 
-			/* Case 3 - right rotate at gparent */
+			/* 
+			 * Case 3 - right rotate at gparent
+			 *
+			 *        G           P
+			 *       / \         / \
+			 *      p   U  -->  n   g
+			 *     /                 \
+			 *    n                   U
+			 */
 			gparent->rb_left = tmp = parent->rb_right;
 			parent->rb_right = gparent;
 			if (tmp)
@@ -134,8 +186,7 @@ void rb_insert_color(struct rb_node *nod
 				parent->rb_left = tmp = node->rb_right;
 				node->rb_right = parent;
 				if (tmp)
-					rb_set_parent_color(tmp, parent,
-							    RB_BLACK);
+					rb_set_parent_color(tmp, parent, RB_BLACK);
 				rb_set_parent_color(parent, node, RB_RED);
 				parent = node;
 			}
@@ -175,43 +226,75 @@ static void __rb_erase_color(struct rb_n
 		} else if (parent->rb_left == node) {
 			sibling = parent->rb_right;
 			if (rb_is_red(sibling)) {
-				/* Case 1 - left rotate at parent */
+				/* 
+				 * Case 1 - left rotate at parent
+				 *
+				 *     P               S
+				 *    / \             / \
+				 *   N   s    -->    p   Sr
+				 *      / \         / \
+				 *     Sl  Sr      N   Sl
+				 */
 				parent->rb_right = tmp1 = sibling->rb_left;
 				sibling->rb_left = parent;
 				rb_set_parent_color(tmp1, parent, RB_BLACK);
-				__rb_rotate_set_parents(parent, sibling, root,
-							RB_RED);
+				__rb_rotate_set_parents(parent, sibling, root, RB_RED);
 				sibling = tmp1;
 			}
 			tmp1 = sibling->rb_right;
 			if (!tmp1 || rb_is_black(tmp1)) {
 				tmp2 = sibling->rb_left;
 				if (!tmp2 || rb_is_black(tmp2)) {
-					/* Case 2 - sibling color flip */
-					rb_set_parent_color(sibling, parent,
-							    RB_RED);
+					/* 
+					 * Case 2 - sibling color flip
+					 *
+					 *     P             P
+					 *    / \           / \
+					 *   N   S    -->  N   s
+					 *      / \           / \
+					 *     Sl  Sr        Sl  Sr
+					 *
+					 * This leaves us violating 5), recurse at p.
+					 */
+					rb_set_parent_color(sibling, parent, RB_RED);
 					node = parent;
 					parent = rb_parent(node);
 					continue;
 				}
-				/* Case 3 - right rotate at sibling */
+				/* 
+				 * Case 3 - right rotate at sibling 
+				 *
+				 *    P             P
+				 *   / \           / \
+				 *  N   S    -->  N   sl
+				 *     / \           / \
+				 *    sl  Sr        1   S
+				 *   / \               / \
+				 *  1   2             2   Sr
+				 */
 				sibling->rb_left = tmp1 = tmp2->rb_right;
 				tmp2->rb_right = sibling;
 				parent->rb_right = tmp2;
 				if (tmp1)
-					rb_set_parent_color(tmp1, sibling,
-							    RB_BLACK);
+					rb_set_parent_color(tmp1, sibling, RB_BLACK);
 				tmp1 = sibling;
 				sibling = tmp2;
 			}
-			/* Case 4 - left rotate at parent + color flips */
+			/* 
+			 * Case 4 - left rotate at parent + color flips 
+			 *
+			 *       P               S
+			 *      / \             / \
+			 *     N   S     -->   P   Sr
+			 *        / \         / \
+			 *       Sl  Sr      N   Sl
+			 */
 			parent->rb_right = tmp2 = sibling->rb_left;
 			sibling->rb_left = parent;
 			rb_set_parent_color(tmp1, sibling, RB_BLACK);
 			if (tmp2)
 				rb_set_parent(tmp2, parent);
-			__rb_rotate_set_parents(parent, sibling, root,
-						RB_BLACK);
+			__rb_rotate_set_parents(parent, sibling, root, RB_BLACK);
 			break;
 		} else {
 			sibling = parent->rb_left;
@@ -220,8 +303,7 @@ static void __rb_erase_color(struct rb_n
 				parent->rb_left = tmp1 = sibling->rb_right;
 				sibling->rb_right = parent;
 				rb_set_parent_color(tmp1, parent, RB_BLACK);
-				__rb_rotate_set_parents(parent, sibling, root,
-							RB_RED);
+				__rb_rotate_set_parents(parent, sibling, root, RB_RED);
 				sibling = tmp1;
 			}
 			tmp1 = sibling->rb_left;
@@ -229,8 +311,7 @@ static void __rb_erase_color(struct rb_n
 				tmp2 = sibling->rb_right;
 				if (!tmp2 || rb_is_black(tmp2)) {
 					/* Case 2 - sibling color flip */
-					rb_set_parent_color(sibling, parent,
-							    RB_RED);
+					rb_set_parent_color(sibling, parent, RB_RED);
 					node = parent;
 					parent = rb_parent(node);
 					continue;
@@ -240,8 +321,7 @@ static void __rb_erase_color(struct rb_n
 				tmp2->rb_left = sibling;
 				parent->rb_left = tmp2;
 				if (tmp1)
-					rb_set_parent_color(tmp1, sibling,
-							    RB_BLACK);
+					rb_set_parent_color(tmp1, sibling, RB_BLACK);
 				tmp1 = sibling;
 				sibling = tmp2;
 			}
@@ -251,8 +331,7 @@ static void __rb_erase_color(struct rb_n
 			rb_set_parent_color(tmp1, sibling, RB_BLACK);
 			if (tmp2)
 				rb_set_parent(tmp2, parent);
-			__rb_rotate_set_parents(parent, sibling, root,
-						RB_BLACK);
+			__rb_rotate_set_parents(parent, sibling, root, RB_BLACK);
 			break;
 		}
 	}
@@ -267,8 +346,7 @@ void rb_erase(struct rb_node *node, stru
 		child = node->rb_right;
 	else if (!node->rb_right)
 		child = node->rb_left;
-	else
-	{
+	else {
 		struct rb_node *old = node, *left;
 
 		node = node->rb_right;
@@ -310,17 +388,15 @@ void rb_erase(struct rb_node *node, stru
 
 	if (child)
 		rb_set_parent(child, parent);
-	if (parent)
-	{
+	if (parent) {
 		if (parent->rb_left == node)
 			parent->rb_left = child;
 		else
 			parent->rb_right = child;
-	}
-	else
+	} else
 		root->rb_node = child;
 
- color:
+color:
 	if (color == RB_BLACK)
 		__rb_erase_color(child, parent, root);
 }
@@ -433,8 +509,10 @@ struct rb_node *rb_next(const struct rb_
 	if (RB_EMPTY_NODE(node))
 		return NULL;
 
-	/* If we have a right-hand child, go down and then left as far
-	   as we can. */
+	/* 
+	 * If we have a right-hand child, go down and then left as far as we
+	 * can. 
+	 */
 	if (node->rb_right) {
 		node = node->rb_right; 
 		while (node->rb_left)
@@ -442,12 +520,13 @@ struct rb_node *rb_next(const struct rb_
 		return (struct rb_node *)node;
 	}
 
-	/* No right-hand children.  Everything down and left is
-	   smaller than us, so any 'next' node must be in the general
-	   direction of our parent. Go up the tree; any time the
-	   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. */
+	/* 
+	 * No right-hand children. Everything down and left is smaller than
+	 * us, so any 'next' node must be in the general direction of our
+	 * parent. Go up the tree; any time the 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 ((parent = rb_parent(node)) && node == parent->rb_right)
 		node = parent;
 
@@ -462,8 +541,10 @@ struct rb_node *rb_prev(const struct rb_
 	if (RB_EMPTY_NODE(node))
 		return NULL;
 
-	/* If we have a left-hand child, go down and then right as far
-	   as we can. */
+	/* 
+	 * If we have a left-hand child, go down and then right as far as we
+	 * can. 
+	 */
 	if (node->rb_left) {
 		node = node->rb_left; 
 		while (node->rb_right)
@@ -471,8 +552,10 @@ struct rb_node *rb_prev(const struct rb_
 		return (struct rb_node *)node;
 	}
 
-	/* No left-hand children. Go up till we find an ancestor which
-	   is a right-hand child of its parent */
+	/*
+	 * No left-hand children. Go up till we find an ancestor which is a
+	 * right-hand child of its parent 
+	 */
 	while ((parent = rb_parent(node)) && node == parent->rb_left)
 		node = parent;
 

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [PATCH 04/13] rbtree: move some implementation details from rbtree.h to rbtree.c

[Michal Nazarewicz]

On Wed, 11 Jul 2012 01:12:54 +0200, Michel Lespinasse <walken@google.com> wrote:

> On Tue, Jul 10, 2012 at 5:19 AM, Michal Nazarewicz <mina86@mina86.com> wrote:
>> On Tue, 10 Jul 2012 01:35:14 +0200, Michel Lespinasse <walken@google.com> wrote:
>>> +#define        RB_RED          0
>>> +#define        RB_BLACK        1
>>
>> Interestingly, those are almost never used. RB_BLACK is used only once.
>> Should we get rid of those instead?  Or change the code (like rb_is_red())
>> to use them?
>
> I'm actually making heavier use of RB_RED / RB_BLACK later on in the patch set.

Yeah, I've just noticed.  Disregard my comment.

> But agree, rb_is_red() / rb_is_black() could use these too.

-- 
Best regards,                                         _     _
.o. | Liege of Serenely Enlightened Majesty of      o' \,=./ `o
..o | Computer Science,  Michał “mina86” Nazarewicz    (o o)
ooo +----<email/xmpp: mpn@google.com>--------------ooO--(_)--Ooo--

Re: [PATCH 04/13] rbtree: move some implementation details from rbtree.h to rbtree.c

[Michal Nazarewicz]

On Wed, 11 Jul 2012 01:12:54 +0200, Michel Lespinasse <walken@google.com> wrote:

> On Tue, Jul 10, 2012 at 5:19 AM, Michal Nazarewicz <mina86@mina86.com> wrote:
>> On Tue, 10 Jul 2012 01:35:14 +0200, Michel Lespinasse <walken@google.com> wrote:
>>> +#define        RB_RED          0
>>> +#define        RB_BLACK        1
>>
>> Interestingly, those are almost never used. RB_BLACK is used only once.
>> Should we get rid of those instead?  Or change the code (like rb_is_red())
>> to use them?
>
> I'm actually making heavier use of RB_RED / RB_BLACK later on in the patch set.

Yeah, I've just noticed.  Disregard my comment.

> But agree, rb_is_red() / rb_is_black() could use these too.

-- 
Best regards,                                         _     _
.o. | Liege of Serenely Enlightened Majesty of      o' \,=./ `o
..o | Computer Science,  Michał “mina86” Nazarewicz    (o o)
ooo +----<email/xmpp: mpn@google.com>--------------ooO--(_)--Ooo--

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [PATCH 05/13] rbtree: performance and correctness test

[Daniel Santos]

On 07/11/2012 01:14 AM, Michel Lespinasse wrote:
> On Tue, Jul 10, 2012 at 5:27 AM, Michal Nazarewicz <mina86@mina86.com> wrote:
>> On Tue, 10 Jul 2012 01:35:15 +0200, Michel Lespinasse <walken@google.com> wrote:
>>> +       u32 prev_key = 0;
>>> +
>>> +       for (rb = rb_first(&root); rb; rb = rb_next(rb)) {
>>> +               struct test_node *node = rb_entry(rb, struct test_node,
>>> rb);
>>> +               WARN_ON_ONCE(node->key < prev_key);
>> What if for some reason we generate node with key equal zero or two keys
>> with the same value?  It may not be the case for current code, but someone
>> might change it in the future.  I think <= is safer here.
> No, it's not illegal for two nodes to have the same key; the second
> one to be inserted will just get placed after the first one. The
> rbtree library doesn't care either way as it's not even aware of the
> key values :)
Right.  This is strictly a function of your insert function. In my
generic rbtree patch set, there is a concept of unique or non-unique
keys, but this doesn't exist in the rbtree library its self.

Re: [PATCH 05/13] rbtree: performance and correctness test

[Daniel Santos]

On 07/11/2012 01:14 AM, Michel Lespinasse wrote:
> On Tue, Jul 10, 2012 at 5:27 AM, Michal Nazarewicz <mina86@mina86.com> wrote:
>> On Tue, 10 Jul 2012 01:35:15 +0200, Michel Lespinasse <walken@google.com> wrote:
>>> +       u32 prev_key = 0;
>>> +
>>> +       for (rb = rb_first(&root); rb; rb = rb_next(rb)) {
>>> +               struct test_node *node = rb_entry(rb, struct test_node,
>>> rb);
>>> +               WARN_ON_ONCE(node->key < prev_key);
>> What if for some reason we generate node with key equal zero or two keys
>> with the same value?  It may not be the case for current code, but someone
>> might change it in the future.  I think <= is safer here.
> No, it's not illegal for two nodes to have the same key; the second
> one to be inserted will just get placed after the first one. The
> rbtree library doesn't care either way as it's not even aware of the
> key values :)
Right.  This is strictly a function of your insert function. In my
generic rbtree patch set, there is a concept of unique or non-unique
keys, but this doesn't exist in the rbtree library its self.

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [PATCH 00/13] rbtree updates

[Michel Lespinasse]

On Wed, Jul 11, 2012 at 6:23 AM, Peter Zijlstra <peterz@infradead.org> wrote:
> Looks nice.. How about something like the below on top.. I couldn't
> immediately find a sane reason for the grand-parent to always be red in
> the insertion case.

Do you mean the case you marked XXX ? it is actually parent that is
red, which we know because we tested that a few lines earlier.

> @@ -85,12 +104,27 @@ void rb_insert_color(struct rb_node *nod
>                 } else if (rb_is_black(parent))
>                         break;
>
> +               /*
> +                * XXX
> +                */
>                 gparent = rb_red_parent(parent);

See :)

>                 if (parent == gparent->rb_left) {
>                         tmp = gparent->rb_right;
>                         if (tmp && rb_is_red(tmp)) {
> -                               /* Case 1 - color flips */
> +                               /*
> +                                * Case 1 - color flips
> +                                *
> +                                *       G            g
> +                                *      / \          / \
> +                                *     p   u  -->   P   U
> +                                *    /            /
> +                                *   n            N
> +                                *
> +                                * However, since g's parent might be red, and
> +                                * 4) does not allow this, we need to recurse
> +                                * at g.
> +                                */

I like these diagrams - I initially didn't think they'd work well, given the need for colors etc, but I now see that it's workable.

In __rb_erase_color(), some of the cases are more complicated than you drew however, because some node colors aren't known.
This is what I ended up with:

  *  5), then the longest possible path due to 4 is 2B.
  *
  *  We shall indicate color with case, where black nodes are uppercase and red
- *  nodes will be lowercase.
+ *  nodes will be lowercase. Unknown color nodes shall be drawn as red with
+ *  some accompanying text comment.
  */

+                                       /*
+                                        * Case 2 - sibling color flip
+                                        * (p could be either color here)
+                                        *
+                                        *     p             p
+                                        *    / \           / \
+                                        *   N   S    -->  N   s
+                                        *      / \           / \
+                                        *     Sl  Sr        Sl  Sr
+                                        *
+                                        * This leaves us violating 5), so
+                                        * recurse at p. If p is red, the
+                                        * recursion will just flip it to black
+                                        * and exit. If coming from Case 1,
+                                        * p is known to be red.
+                                        */

+                               /*
+                                * Case 3 - right rotate at sibling
+                                * (p could be either color here)
+                                *
+                                *    p             p
+                                *   / \           / \
+                                *  N   S    -->  N   Sl
+                                *     / \             \
+                                *    sl  Sr            s
+                                *                       \
+                                *                        Sr
+                                */

+                       /*
+                        * Case 4 - left rotate at parent + color flips
+                        * (p and sl could be either color here.
+                        *  After rotation, p becomes black, s acquires
+                        *  p's color, and sl keeps its color)
+                        *
+                        *       p               s
+                        *      / \             / \
+                        *     N   S     -->   P   Sr
+                        *        / \         / \
+                        *       sl  sr      N   sl
+                        */

-- 
Michel "Walken" Lespinasse
A program is never fully debugged until the last user dies.

Re: [PATCH 00/13] rbtree updates

[Michel Lespinasse]

On Wed, Jul 11, 2012 at 6:23 AM, Peter Zijlstra <peterz@infradead.org> wrote:
> Looks nice.. How about something like the below on top.. I couldn't
> immediately find a sane reason for the grand-parent to always be red in
> the insertion case.

Do you mean the case you marked XXX ? it is actually parent that is
red, which we know because we tested that a few lines earlier.

> @@ -85,12 +104,27 @@ void rb_insert_color(struct rb_node *nod
>                 } else if (rb_is_black(parent))
>                         break;
>
> +               /*
> +                * XXX
> +                */
>                 gparent = rb_red_parent(parent);

See :)

>                 if (parent == gparent->rb_left) {
>                         tmp = gparent->rb_right;
>                         if (tmp && rb_is_red(tmp)) {
> -                               /* Case 1 - color flips */
> +                               /*
> +                                * Case 1 - color flips
> +                                *
> +                                *       G            g
> +                                *      / \          / \
> +                                *     p   u  -->   P   U
> +                                *    /            /
> +                                *   n            N
> +                                *
> +                                * However, since g's parent might be red, and
> +                                * 4) does not allow this, we need to recurse
> +                                * at g.
> +                                */

I like these diagrams - I initially didn't think they'd work well, given the need for colors etc, but I now see that it's workable.

In __rb_erase_color(), some of the cases are more complicated than you drew however, because some node colors aren't known.
This is what I ended up with:

  *  5), then the longest possible path due to 4 is 2B.
  *
  *  We shall indicate color with case, where black nodes are uppercase and red
- *  nodes will be lowercase.
+ *  nodes will be lowercase. Unknown color nodes shall be drawn as red with
+ *  some accompanying text comment.
  */

+                                       /*
+                                        * Case 2 - sibling color flip
+                                        * (p could be either color here)
+                                        *
+                                        *     p             p
+                                        *    / \           / \
+                                        *   N   S    -->  N   s
+                                        *      / \           / \
+                                        *     Sl  Sr        Sl  Sr
+                                        *
+                                        * This leaves us violating 5), so
+                                        * recurse at p. If p is red, the
+                                        * recursion will just flip it to black
+                                        * and exit. If coming from Case 1,
+                                        * p is known to be red.
+                                        */

+                               /*
+                                * Case 3 - right rotate at sibling
+                                * (p could be either color here)
+                                *
+                                *    p             p
+                                *   / \           / \
+                                *  N   S    -->  N   Sl
+                                *     / \             \
+                                *    sl  Sr            s
+                                *                       \
+                                *                        Sr
+                                */

+                       /*
+                        * Case 4 - left rotate at parent + color flips
+                        * (p and sl could be either color here.
+                        *  After rotation, p becomes black, s acquires
+                        *  p's color, and sl keeps its color)
+                        *
+                        *       p               s
+                        *      / \             / \
+                        *     N   S     -->   P   Sr
+                        *        / \         / \
+                        *       sl  sr      N   sl
+                        */

-- 
Michel "Walken" Lespinasse
A program is never fully debugged until the last user dies.

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [PATCH 00/13] rbtree updates

[Peter Zijlstra]

On Wed, 2012-07-11 at 18:12 -0700, Michel Lespinasse wrote:
> Do you mean the case you marked XXX ? it is actually parent that is
> red, which we know because we tested that a few lines earlier.
> 
> > @@ -85,12 +104,27 @@ void rb_insert_color(struct rb_node *nod
> >                 } else if (rb_is_black(parent))
> >                         break;
> >
> > +               /*
> > +                * XXX
> > +                */
> >                 gparent = rb_red_parent(parent);
> 
> See :) 

D'0h, I got confused and thought the red was for the parent's parent,
not parent.

Quite.. ignore that then.

Re: [PATCH 00/13] rbtree updates

[Peter Zijlstra]

On Wed, 2012-07-11 at 18:12 -0700, Michel Lespinasse wrote:
> Do you mean the case you marked XXX ? it is actually parent that is
> red, which we know because we tested that a few lines earlier.
> 
> > @@ -85,12 +104,27 @@ void rb_insert_color(struct rb_node *nod
> >                 } else if (rb_is_black(parent))
> >                         break;
> >
> > +               /*
> > +                * XXX
> > +                */
> >                 gparent = rb_red_parent(parent);
> 
> See :) 

D'0h, I got confused and thought the red was for the parent's parent,
not parent.

Quite.. ignore that then.

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [PATCH 00/13] rbtree updates

[Peter Zijlstra]

On Wed, 2012-07-11 at 18:12 -0700, Michel Lespinasse wrote:
> 
> In __rb_erase_color(), some of the cases are more complicated than you drew however, because some node colors aren't known.

Right, the wikipedia article draws them blank, I couldn't come up with a
3rd case, although maybe we can annotate them like (P) to mean blank..


> This is what I ended up with:
> 
>   *  5), then the longest possible path due to 4 is 2B.
>   *
>   *  We shall indicate color with case, where black nodes are uppercase and red
> - *  nodes will be lowercase.
> + *  nodes will be lowercase. Unknown color nodes shall be drawn as red with
> + *  some accompanying text comment.
>   */
> 
> +                                       /*
> +                                        * Case 2 - sibling color flip
> +                                        * (p could be either color here)
> +                                        *
> +                                        *     p             p
> +                                        *    / \           / \
> +                                        *   N   S    -->  N   s
> +                                        *      / \           / \
> +                                        *     Sl  Sr        Sl  Sr
> +                                        *
> +                                        * This leaves us violating 5), so
> +                                        * recurse at p. If p is red, the
> +                                        * recursion will just flip it to black
> +                                        * and exit. If coming from Case 1,
> +                                        * p is known to be red.
> +                                        */
> 
> +                               /*
> +                                * Case 3 - right rotate at sibling
> +                                * (p could be either color here)
> +                                *
> +                                *    p             p
> +                                *   / \           / \
> +                                *  N   S    -->  N   Sl
> +                                *     / \             \
> +                                *    sl  Sr            s
> +                                *                       \
> +                                *                        Sr
> +                                */
> 
> +                       /*
> +                        * Case 4 - left rotate at parent + color flips
> +                        * (p and sl could be either color here.
> +                        *  After rotation, p becomes black, s acquires
> +                        *  p's color, and sl keeps its color)
> +                        *
> +                        *       p               s
> +                        *      / \             / \
> +                        *     N   S     -->   P   Sr
> +                        *        / \         / \
> +                        *       sl  sr      N   sl
> +                        */ 


Yes, very nice.. someday when I'm bored I might expand the comments with
the reason why we're doing the given operation.

Also, I was sorely tempted to rename your tmp1,tmp2 variables to sl and
sr.

Re: [PATCH 00/13] rbtree updates

[Peter Zijlstra]

On Wed, 2012-07-11 at 18:12 -0700, Michel Lespinasse wrote:
> 
> In __rb_erase_color(), some of the cases are more complicated than you drew however, because some node colors aren't known.

Right, the wikipedia article draws them blank, I couldn't come up with a
3rd case, although maybe we can annotate them like (P) to mean blank..


> This is what I ended up with:
> 
>   *  5), then the longest possible path due to 4 is 2B.
>   *
>   *  We shall indicate color with case, where black nodes are uppercase and red
> - *  nodes will be lowercase.
> + *  nodes will be lowercase. Unknown color nodes shall be drawn as red with
> + *  some accompanying text comment.
>   */
> 
> +                                       /*
> +                                        * Case 2 - sibling color flip
> +                                        * (p could be either color here)
> +                                        *
> +                                        *     p             p
> +                                        *    / \           / \
> +                                        *   N   S    -->  N   s
> +                                        *      / \           / \
> +                                        *     Sl  Sr        Sl  Sr
> +                                        *
> +                                        * This leaves us violating 5), so
> +                                        * recurse at p. If p is red, the
> +                                        * recursion will just flip it to black
> +                                        * and exit. If coming from Case 1,
> +                                        * p is known to be red.
> +                                        */
> 
> +                               /*
> +                                * Case 3 - right rotate at sibling
> +                                * (p could be either color here)
> +                                *
> +                                *    p             p
> +                                *   / \           / \
> +                                *  N   S    -->  N   Sl
> +                                *     / \             \
> +                                *    sl  Sr            s
> +                                *                       \
> +                                *                        Sr
> +                                */
> 
> +                       /*
> +                        * Case 4 - left rotate at parent + color flips
> +                        * (p and sl could be either color here.
> +                        *  After rotation, p becomes black, s acquires
> +                        *  p's color, and sl keeps its color)
> +                        *
> +                        *       p               s
> +                        *      / \             / \
> +                        *     N   S     -->   P   Sr
> +                        *        / \         / \
> +                        *       sl  sr      N   sl
> +                        */ 


Yes, very nice.. someday when I'm bored I might expand the comments with
the reason why we're doing the given operation.

Also, I was sorely tempted to rename your tmp1,tmp2 variables to sl and
sr.

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [PATCH 00/13] rbtree updates

[Michel Lespinasse]

On Thu, Jul 12, 2012 at 7:12 AM, Peter Zijlstra <peterz@infradead.org> wrote:
> On Wed, 2012-07-11 at 18:12 -0700, Michel Lespinasse wrote:
>>
>> In __rb_erase_color(), some of the cases are more complicated than you drew however, because some node colors aren't known.
>
> Right, the wikipedia article draws them blank, I couldn't come up with a
> 3rd case, although maybe we can annotate them like (P) to mean blank..

Ah, good idea, I adopted that :)

> Yes, very nice.. someday when I'm bored I might expand the comments with
> the reason why we're doing the given operation.

There is a brief comment at the start of the loop that indicates which
rbtree invariants might be violated at that point; so someone could
deduce that we're trying to either fix these or move towards the root
until they get fixed. But yeah, this is never explicitly explained.

> Also, I was sorely tempted to rename your tmp1,tmp2 variables to sl and
> sr.

This could be done, but you'd *still* need one extra temporary, so
you'd end up with sl, sr and tmp. Which is fine, I guess, but I
preferred to have one less variable around.

-- 
Michel "Walken" Lespinasse
A program is never fully debugged until the last user dies.

Re: [PATCH 00/13] rbtree updates

[Michel Lespinasse]

On Thu, Jul 12, 2012 at 7:12 AM, Peter Zijlstra <peterz@infradead.org> wrote:
> On Wed, 2012-07-11 at 18:12 -0700, Michel Lespinasse wrote:
>>
>> In __rb_erase_color(), some of the cases are more complicated than you drew however, because some node colors aren't known.
>
> Right, the wikipedia article draws them blank, I couldn't come up with a
> 3rd case, although maybe we can annotate them like (P) to mean blank..

Ah, good idea, I adopted that :)

> Yes, very nice.. someday when I'm bored I might expand the comments with
> the reason why we're doing the given operation.

There is a brief comment at the start of the loop that indicates which
rbtree invariants might be violated at that point; so someone could
deduce that we're trying to either fix these or move towards the root
until they get fixed. But yeah, this is never explicitly explained.

> Also, I was sorely tempted to rename your tmp1,tmp2 variables to sl and
> sr.

This could be done, but you'd *still* need one extra temporary, so
you'd end up with sl, sr and tmp. Which is fine, I guess, but I
preferred to have one less variable around.

-- 
Michel "Walken" Lespinasse
A program is never fully debugged until the last user dies.

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>