[PATCH v3] xen: common: rbtree: ported updates from

[PATCH v3] xen: common: rbtree: ported updates from

[Praveen Kumar]

Hi All,

The patch imports the changes and updates of the rbtree implementaiton
from Linux tree. But since, the only current implementation is with tmem.c,
which am not much aware off much and therefore, was unable to test the changes
thoroughly. Having said that, I do have plans of adding futher code changes
which will be using rb-tree more in credit2 scheduler and that will help in
further testing the same.

I have not imported augmented, rcu and patches which added new rbtree
functionality, as there was no specific requirement for current planned
implementation.

Below are the categorized Linux commit versions which are not imported :

Augmented rbtree :
14b94af0b251a2c80885b60538166fb7d04a642e
9d9e6f9703bbd642f3f2f807e6aaa642a4cbcec9
9c079add0d0f45220f4bb37febf0621137ec2d38
3cb7a56344ca45ee56d71c5f8fe9f922306bff1f

Add postorder iteration functions:
9dee5c51516d2c3fff22633c1272c5652e68075a

RCU related implementation :
d72da4a4d973d8a0a0d3c97e7cdebf287fbe3a99
c1adf20052d80f776849fa2c1acb472cdeb7786c
ce093a04543c403d52c1a5788d8cb92e47453aba

Use of designated initializers :
f231aebfc4cae2f6ed27a46a31e2630909513d77

Please share your inputs. Thanks in advance.

Regards,

~Praveen.



_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xen.org
https://lists.xen.org/xen-devel

[PATCH 01/20] rbtree: add const qualifier to some functions

[Praveen Kumar]

The 'rb_first()', 'rb_last()', 'rb_next()' and 'rb_prev()' calls
take a pointer to an RB node or RB root. They do not change the
pointed objects, so add a 'const' qualifier in order to make life
of the users of these functions easier.

Indeed, if I have my own constant pointer &const struct my_type *p,
and I call 'rb_next(&p->rb)', I get a GCC warning:

warning: passing argument 1 of ‘rb_next’ discards qualifiers from pointer target
type

Signed-off-by: Artem Bityutskiy <Artem.Bityutskiy@nokia.com>
Signed-off-by: David Woodhouse <David.Woodhouse@intel.com>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
[Linux commit f4b477c47332367d35686bd2b808c2156b96d7c7]

Ported to Xen.

Signed-off-by: Praveen Kumar <kpraveen.lkml@gmail.com>
---
 xen/common/rbtree.c      | 12 ++++++------
 xen/include/xen/rbtree.h |  8 ++++----
 2 files changed, 10 insertions(+), 10 deletions(-)

diff --git a/xen/common/rbtree.c b/xen/common/rbtree.c
index 3328960d56..d86b5f25c0 100644
--- a/xen/common/rbtree.c
+++ b/xen/common/rbtree.c
@@ -291,7 +291,7 @@ EXPORT_SYMBOL(rb_erase);
 /*
  * This function returns the first node (in sort order) of the tree.
  */
-struct rb_node *rb_first(struct rb_root *root)
+struct rb_node *rb_first(const struct rb_root *root)
 {
     struct rb_node *n;
 
@@ -304,7 +304,7 @@ struct rb_node *rb_first(struct rb_root *root)
 }
 EXPORT_SYMBOL(rb_first);
 
-struct rb_node *rb_last(struct rb_root *root)
+struct rb_node *rb_last(const struct rb_root *root)
 {
     struct rb_node *n;
 
@@ -317,7 +317,7 @@ struct rb_node *rb_last(struct rb_root *root)
 }
 EXPORT_SYMBOL(rb_last);
 
-struct rb_node *rb_next(struct rb_node *node)
+struct rb_node *rb_next(const struct rb_node *node)
 {
     struct rb_node *parent;
 
@@ -330,7 +330,7 @@ struct rb_node *rb_next(struct rb_node *node)
         node = node->rb_right; 
         while (node->rb_left)
             node=node->rb_left;
-        return node;
+        return (struct rb_node *)node;
     }
 
     /* No right-hand children.  Everything down and left is
@@ -346,7 +346,7 @@ struct rb_node *rb_next(struct rb_node *node)
 }
 EXPORT_SYMBOL(rb_next);
 
-struct rb_node *rb_prev(struct rb_node *node)
+struct rb_node *rb_prev(const struct rb_node *node)
 {
     struct rb_node *parent;
 
@@ -359,7 +359,7 @@ struct rb_node *rb_prev(struct rb_node *node)
         node = node->rb_left; 
         while (node->rb_right)
             node=node->rb_right;
-        return node;
+        return (struct rb_node *)node;
     }
 
     /* No left-hand children. Go up till we find an ancestor which
diff --git a/xen/include/xen/rbtree.h b/xen/include/xen/rbtree.h
index f93c4d5823..3eb527eb37 100644
--- a/xen/include/xen/rbtree.h
+++ b/xen/include/xen/rbtree.h
@@ -60,10 +60,10 @@ extern void rb_insert_color(struct rb_node *, struct rb_root *);
 extern void rb_erase(struct rb_node *, struct rb_root *);
 
 /* Find logical next and previous nodes in a tree */
-extern struct rb_node *rb_next(struct rb_node *);
-extern struct rb_node *rb_prev(struct rb_node *);
-extern struct rb_node *rb_first(struct rb_root *);
-extern struct rb_node *rb_last(struct rb_root *);
+extern struct rb_node *rb_next(const struct rb_node *);
+extern struct rb_node *rb_prev(const struct rb_node *);
+extern struct rb_node *rb_first(const struct rb_root *);
+extern struct rb_node *rb_last(const struct rb_root *);
 
 /* Fast replacement of a single node without remove/rebalance/add/rebalance */
 extern void rb_replace_node(struct rb_node *victim, struct rb_node *new, 
-- 
2.12.0


_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xen.org
https://lists.xen.org/xen-devel

Re: [PATCH 01/20] rbtree: add const qualifier to some functions

[Jan Beulich]

>>> On 17.06.17 at 11:32, <kpraveen.lkml@gmail.com> wrote:
> The 'rb_first()', 'rb_last()', 'rb_next()' and 'rb_prev()' calls
> take a pointer to an RB node or RB root. They do not change the
> pointed objects, so add a 'const' qualifier in order to make life
> of the users of these functions easier.
> 
> Indeed, if I have my own constant pointer &const struct my_type *p,
> and I call 'rb_next(&p->rb)', I get a GCC warning:
> 
> warning: passing argument 1 of ‘rb_next’ discards qualifiers from pointer target
> type
> 
> Signed-off-by: Artem Bityutskiy <Artem.Bityutskiy@nokia.com>
> Signed-off-by: David Woodhouse <David.Woodhouse@intel.com>
> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
> [Linux commit f4b477c47332367d35686bd2b808c2156b96d7c7]
> 
> Ported to Xen.
> 
> Signed-off-by: Praveen Kumar <kpraveen.lkml@gmail.com>

This looks okay now from a content pov, but I still have a question
and a remark.

Question: Who's the original author? According to the Linux commit,
it's Artem, but without an explicit From: tag I think anyone trying to
"git am" you mail would put you in as the author. With this taken
care of (which the committer may be willing to do)
Acked-by: Jan Beulich <jbeulich@suse.com>

Remark: You've sent v3 of the series. This patch has no version
indicator at all, and most other patches say v2. This is all quite
inconsistent, and prevents easily identifying the various pieces
belonging together when not using a threaded view. If you add
new patches to a series, don't start them at v1. Instead in the
brief revision info (after the first --- marker) simply say "New in
v3."

Jan

_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xen.org
https://lists.xen.org/xen-devel

Re: [PATCH 01/20] rbtree: add const qualifier to some functions

[Praveen Kumar]

Hi Jan,

On Mon, Jun 19, 2017 at 7:19 PM, Jan Beulich <JBeulich@suse.com> wrote:
>>>> On 17.06.17 at 11:32, <kpraveen.lkml@gmail.com> wrote:
>> The 'rb_first()', 'rb_last()', 'rb_next()' and 'rb_prev()' calls
>> take a pointer to an RB node or RB root. They do not change the
>> pointed objects, so add a 'const' qualifier in order to make life
>> of the users of these functions easier.
>>
>> Indeed, if I have my own constant pointer &const struct my_type *p,
>> and I call 'rb_next(&p->rb)', I get a GCC warning:
>>
>> warning: passing argument 1 of ‘rb_next’ discards qualifiers from pointer target
>> type
>>
>> Signed-off-by: Artem Bityutskiy <Artem.Bityutskiy@nokia.com>
>> Signed-off-by: David Woodhouse <David.Woodhouse@intel.com>
>> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
>> [Linux commit f4b477c47332367d35686bd2b808c2156b96d7c7]
>>
>> Ported to Xen.
>>
>> Signed-off-by: Praveen Kumar <kpraveen.lkml@gmail.com>
>
> This looks okay now from a content pov, but I still have a question
> and a remark.
>
> Question: Who's the original author? According to the Linux commit,
> it's Artem, but without an explicit From: tag I think anyone trying to
> "git am" you mail would put you in as the author. With this taken
> care of (which the committer may be willing to do)
> Acked-by: Jan Beulich <jbeulich@suse.com>
>

Thanks for your input.
Pardon me, I am new to the forum. The Ack you added is only for this patch.

Also, do you want me to add 'From' and resend ?
To be precise in below order  :

Signed-off-by: Artem Bityutskiy <Artem.Bityutskiy@nokia.com>
Signed-off-by: David Woodhouse <David.Woodhouse@intel.com>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
[Linux commit f4b477c47332367d35686bd2b808c2156b96d7c7]

Ported to Xen.

From: Artem Bityutskiy <Artem.Bityutskiy@nokia.com>
Signed-off-by: Praveen Kumar <kpraveen.lkml@gmail.com>

Please do correct me if my understanding is wrong. Thanks.

> Remark: You've sent v3 of the series. This patch has no version
> indicator at all, and most other patches say v2. This is all quite
> inconsistent, and prevents easily identifying the various pieces
> belonging together when not using a threaded view. If you add
> new patches to a series, don't start them at v1. Instead in the
> brief revision info (after the first --- marker) simply say "New in
> v3."
>

Sure, my mistake. I was not aware of the same. I will take care in
future patches.
Thanks for your input.

Regards,

~Praveen.

_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xen.org
https://lists.xen.org/xen-devel

Re: [PATCH 01/20] rbtree: add const qualifier to some functions

[Jan Beulich]

>>> On 19.06.17 at 16:09, <kpraveen.lkml@gmail.com> wrote:
> On Mon, Jun 19, 2017 at 7:19 PM, Jan Beulich <JBeulich@suse.com> wrote:
>>>>> On 17.06.17 at 11:32, <kpraveen.lkml@gmail.com> wrote:
>>> The 'rb_first()', 'rb_last()', 'rb_next()' and 'rb_prev()' calls
>>> take a pointer to an RB node or RB root. They do not change the
>>> pointed objects, so add a 'const' qualifier in order to make life
>>> of the users of these functions easier.
>>>
>>> Indeed, if I have my own constant pointer &const struct my_type *p,
>>> and I call 'rb_next(&p->rb)', I get a GCC warning:
>>>
>>> warning: passing argument 1 of ‘rb_next’ discards qualifiers from pointer target
>>> type
>>>
>>> Signed-off-by: Artem Bityutskiy <Artem.Bityutskiy@nokia.com>
>>> Signed-off-by: David Woodhouse <David.Woodhouse@intel.com>
>>> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
>>> [Linux commit f4b477c47332367d35686bd2b808c2156b96d7c7]
>>>
>>> Ported to Xen.
>>>
>>> Signed-off-by: Praveen Kumar <kpraveen.lkml@gmail.com>
>>
>> This looks okay now from a content pov, but I still have a question
>> and a remark.
>>
>> Question: Who's the original author? According to the Linux commit,
>> it's Artem, but without an explicit From: tag I think anyone trying to
>> "git am" you mail would put you in as the author. With this taken
>> care of (which the committer may be willing to do)
>> Acked-by: Jan Beulich <jbeulich@suse.com>
>>
> 
> Thanks for your input.
> Pardon me, I am new to the forum. The Ack you added is only for this patch.

Yes.

> Also, do you want me to add 'From' and resend ?

As said, I think the committer may be able to take care of this. So
re-sending just because of this is likely not required.

> To be precise in below order  :
> 
> Signed-off-by: Artem Bityutskiy <Artem.Bityutskiy@nokia.com>
> Signed-off-by: David Woodhouse <David.Woodhouse@intel.com>
> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
> [Linux commit f4b477c47332367d35686bd2b808c2156b96d7c7]
> 
> Ported to Xen.
> 
> From: Artem Bityutskiy <Artem.Bityutskiy@nokia.com>
> Signed-off-by: Praveen Kumar <kpraveen.lkml@gmail.com>

Normally From: would go first (before the description text) I think.

Jan

_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xen.org
https://lists.xen.org/xen-devel

Re: [PATCH 01/20] rbtree: add const qualifier to some functions

[Dario Faggioli]

[-- Attachment #1.1: Type: text/plain, Size: 1378 bytes --]

On Sat, 2017-06-17 at 15:02 +0530, Praveen Kumar wrote:
> The 'rb_first()', 'rb_last()', 'rb_next()' and 'rb_prev()' calls
> take a pointer to an RB node or RB root. They do not change the
> pointed objects, so add a 'const' qualifier in order to make life
> of the users of these functions easier.
> 
> Indeed, if I have my own constant pointer &const struct my_type *p,
> and I call 'rb_next(&p->rb)', I get a GCC warning:
> 
> warning: passing argument 1 of ‘rb_next’ discards qualifiers from
> pointer target
> type
> 
> Signed-off-by: Artem Bityutskiy <Artem.Bityutskiy@nokia.com>
> Signed-off-by: David Woodhouse <David.Woodhouse@intel.com>
> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
> [Linux commit f4b477c47332367d35686bd2b808c2156b96d7c7]
> 
> Ported to Xen.
> 
> Signed-off-by: Praveen Kumar <kpraveen.lkml@gmail.com>
>
With authorship (the From: field) fixed as Jan suggested,

Reviewed-by: Dario Faggioli <dario.faggioli@citrix.com>

(The remark on the authorship applies of course to all the patches,
even if I don't explicitly state it again).

Dario
-- 
<<This happens because I choose it to happen!>> (Raistlin Majere)
-----------------------------------------------------------------
Dario Faggioli, Ph.D, http://about.me/dario.faggioli
Senior Software Engineer, Citrix Systems R&D Ltd., Cambridge (UK)

[-- Attachment #1.2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 819 bytes --]

[-- Attachment #2: Type: text/plain, Size: 127 bytes --]

_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xen.org
https://lists.xen.org/xen-devel

[PATCH 02/20] lib/rbtree.c: optimize rb_erase()

[Praveen Kumar]

Tfour 4 redundant if-conditions in function __rb_erase_color() in
lib/rbtree.c are removed.

In pseudo-source-code, the structure of the code is as follows:

if ((!A || B) && (!C || D)) {
.
.
.
} else {
		if (!C || D) {//if this is true, it implies: (A == true) && (B == false)
				if (A) {//hence this always evaluates to 'true'...
						.
				}
				.
				//at this point, C always becomes true, because of:
				__rb_rotate_right/left();
				//and:
				other = parent->rb_right/left;
		}
		.
		.
		if (C) {//...and this too !
				.
		}
}

Signed-off-by: Wolfram Strepp <wstrepp@gmx.de>
Acked-by: Peter Zijlstra <a.p.zijlstra@chello.nl>
Cc: Andrea Arcangeli <andrea@qumranet.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
[Linux commit 55a63998b8967615a15e2211ba0ff3a84a565824]

Ported to Xen.

Signed-off-by: Praveen Kumar <kpraveen.lkml@gmail.com>
---
 xen/common/rbtree.c | 14 ++++----------
 1 file changed, 4 insertions(+), 10 deletions(-)

diff --git a/xen/common/rbtree.c b/xen/common/rbtree.c
index d86b5f25c0..70cb15f1fe 100644
--- a/xen/common/rbtree.c
+++ b/xen/common/rbtree.c
@@ -162,17 +162,14 @@ static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,
             {
                 if (!other->rb_right || rb_is_black(other->rb_right))
                 {
-                    struct rb_node *o_left;
-                    if ((o_left = other->rb_left))
-                        rb_set_black(o_left);
+                    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);
-                if (other->rb_right)
-                    rb_set_black(other->rb_right);
+                rb_set_black(other->rb_right);
                 __rb_rotate_left(parent, root);
                 node = root->rb_node;
                 break;
@@ -199,17 +196,14 @@ static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,
             {
                 if (!other->rb_left || rb_is_black(other->rb_left))
                 {
-                    register struct rb_node *o_right;
-                    if ((o_right = other->rb_right))
-                        rb_set_black(o_right);
+                    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);
-                if (other->rb_left)
-                    rb_set_black(other->rb_left);
+                rb_set_black(other->rb_left);
                 __rb_rotate_right(parent, root);
                 node = root->rb_node;
                 break;
-- 
2.12.0


_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xen.org
https://lists.xen.org/xen-devel

Re: [PATCH 02/20] lib/rbtree.c: optimize rb_erase()

[Dario Faggioli]

[-- Attachment #1.1: Type: text/plain, Size: 1431 bytes --]

On Sat, 2017-06-17 at 15:02 +0530, Praveen Kumar wrote:
> Tfour 4 redundant if-conditions in function __rb_erase_color() in
> lib/rbtree.c are removed.
> 
> In pseudo-source-code, the structure of the code is as follows:
> 
> if ((!A || B) && (!C || D)) {
> .
> .
> .
> } else {
> 		if (!C || D) {//if this is true, it implies: (A ==
> true) && (B == false)
> 				if (A) {//hence this always evaluates
> to 'true'...
> 						.
> 				}
> 				.
> 				//at this point, C always becomes true,
> because of:
> 				__rb_rotate_right/left();
> 				//and:
> 				other = parent->rb_right/left;
> 		}
> 		.
> 		.
> 		if (C) {//...and this too !
> 				.
> 		}
> }
> 
> Signed-off-by: Wolfram Strepp <wstrepp@gmx.de>
> Acked-by: Peter Zijlstra <a.p.zijlstra@chello.nl>
> Cc: Andrea Arcangeli <andrea@qumranet.com>
> Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
> [Linux commit 55a63998b8967615a15e2211ba0ff3a84a565824]
> 
> Ported to Xen.
> 
> Signed-off-by: Praveen Kumar <kpraveen.lkml@gmail.com>
>
Reviewed-by: Dario Faggioli <dario.faggioli@citrix.com>

Dario
-- 
<<This happens because I choose it to happen!>> (Raistlin Majere)
-----------------------------------------------------------------
Dario Faggioli, Ph.D, http://about.me/dario.faggioli
Senior Software Engineer, Citrix Systems R&D Ltd., Cambridge (UK)

[-- Attachment #1.2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 819 bytes --]

[-- Attachment #2: Type: text/plain, Size: 127 bytes --]

_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xen.org
https://lists.xen.org/xen-devel

[PATCH v2 03/20] rb_tree: reorganize code in rb_erase() for additional changes

[Praveen Kumar]

First, move some code around in order to make the next change more obvious.

[akpm@linux-foundation.org: coding-style fixes]
Signed-off-by: Peter Zijlstra <a.p.zijlstra@chello.nl>
Signed-off-by: Wolfram Strepp <wstrepp@gmx.de>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
[Linux commit 16c047add3ceaf0ab882e3e094d1ec904d02312d]

Ported to Xen.

Signed-off-by: Praveen Kumar <kpraveen.lkml@gmail.com>
---
 xen/common/rbtree.c | 19 ++++++++++---------
 1 file changed, 10 insertions(+), 9 deletions(-)

diff --git a/xen/common/rbtree.c b/xen/common/rbtree.c
index 70cb15f1fe..4b85fd492b 100644
--- a/xen/common/rbtree.c
+++ b/xen/common/rbtree.c
@@ -230,6 +230,16 @@ void rb_erase(struct rb_node *node, struct rb_root *root)
         node = node->rb_right;
         while ((left = node->rb_left) != NULL)
             node = left;
+
+        if (rb_parent(old))
+        {
+            if (rb_parent(old)->rb_left == old)
+                rb_parent(old)->rb_left = node;
+            else
+                rb_parent(old)->rb_right = node;
+        } else
+            root->rb_node = node;
+
         child = node->rb_right;
         parent = rb_parent(node);
         color = rb_color(node);
@@ -246,15 +256,6 @@ void rb_erase(struct rb_node *node, struct rb_root *root)
         node->rb_right = old->rb_right;
         node->rb_left = old->rb_left;
 
-        if (rb_parent(old))
-        {
-            if (rb_parent(old)->rb_left == old)
-                rb_parent(old)->rb_left = node;
-            else
-                rb_parent(old)->rb_right = node;
-        } else
-            root->rb_node = node;
-
         rb_set_parent(old->rb_left, node);
         if (old->rb_right)
             rb_set_parent(old->rb_right, node);
-- 
2.12.0


_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xen.org
https://lists.xen.org/xen-devel

Re: [PATCH v2 03/20] rb_tree: reorganize code in rb_erase() for additional changes

[Dario Faggioli]

[-- Attachment #1.1: Type: text/plain, Size: 907 bytes --]

On Sat, 2017-06-17 at 15:02 +0530, Praveen Kumar wrote:
> First, move some code around in order to make the next change more
> obvious.
> 
> [akpm@linux-foundation.org: coding-style fixes]
> Signed-off-by: Peter Zijlstra <a.p.zijlstra@chello.nl>
> Signed-off-by: Wolfram Strepp <wstrepp@gmx.de>
> Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
> [Linux commit 16c047add3ceaf0ab882e3e094d1ec904d02312d]
> 
> Ported to Xen.
> 
> Signed-off-by: Praveen Kumar <kpraveen.lkml@gmail.com>
>
Reviewed-by: Dario Faggioli <dario.faggioli@citrix.com>

Regards,
Dario
-- 
<<This happens because I choose it to happen!>> (Raistlin Majere)
-----------------------------------------------------------------
Dario Faggioli, Ph.D, http://about.me/dario.faggioli
Senior Software Engineer, Citrix Systems R&D Ltd., Cambridge (UK)

[-- Attachment #1.2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 819 bytes --]

[-- Attachment #2: Type: text/plain, Size: 127 bytes --]

_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xen.org
https://lists.xen.org/xen-devel

[PATCH v2 04/20] rb_tree: make clear distinction between two different cases in rb_erase()

[Praveen Kumar]

There are two cases when a node, having 2 childs, is erased:
'normal case': the successor is not the right-hand-child of the node to be
erased
'special case': the successor is the right-hand child of the node to be erased

Here some ascii-art, with following symbols (referring to the code):
O: node to be deleted
N: the successor of O
P: parent of N
C: child of N
L: some other node

normal case:

                   O                         N
                  / \                       / \
                 /   \                     /   \
                L     \                   L     \
               / \     P      ---->      / \     P
                      / \                       / \
                     /                         /
                    N                         C
                     \                       / \
                      \
                       C
                      / \

special case:
                  O|P                        N
                  / \                       / \
                 /   \                     /   \
                L     \                   L     \
               / \     N      ---->      /       C
                        \                       / \
                         \
                          C
                         / \

Notice that for the special case we don't have to reconnect C to N.

Signed-off-by: Wolfram Strepp <wstrepp@gmx.de>
Signed-off-by: Peter Zijlstra <a.p.zijlstra@chello.nl>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
[Linux commit 4c60117811171d867d4f27f17ea07d7419d45dae]

Ported to Xen.

Signed-off-by: Praveen Kumar <kpraveen.lkml@gmail.com>
---
 xen/common/rbtree.c | 8 ++++----
 1 file changed, 4 insertions(+), 4 deletions(-)

diff --git a/xen/common/rbtree.c b/xen/common/rbtree.c
index 4b85fd492b..90db00a5e8 100644
--- a/xen/common/rbtree.c
+++ b/xen/common/rbtree.c
@@ -244,13 +244,13 @@ void rb_erase(struct rb_node *node, struct rb_root *root)
         parent = rb_parent(node);
         color = rb_color(node);
 
-        if (child)
-            rb_set_parent(child, parent);
         if (parent == old) {
-            parent->rb_right = child;
             parent = node;
-        } else
+        } else {
+            if (child)
+                rb_set_parent(child, parent);
             parent->rb_left = child;
+        }
 
         node->rb_parent_color = old->rb_parent_color;
         node->rb_right = old->rb_right;
-- 
2.12.0


_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xen.org
https://lists.xen.org/xen-devel

Re: [PATCH v2 04/20] rb_tree: make clear distinction between two different cases in rb_erase()

[Dario Faggioli]

[-- Attachment #1.1: Type: text/plain, Size: 3010 bytes --]

On Sat, 2017-06-17 at 15:02 +0530, Praveen Kumar wrote:
> There are two cases when a node, having 2 childs, is erased:
> 'normal case': the successor is not the right-hand-child of the node
> to be
> erased
> 'special case': the successor is the right-hand child of the node to
> be erased
> 
> Here some ascii-art, with following symbols (referring to the code):
> O: node to be deleted
> N: the successor of O
> P: parent of N
> C: child of N
> L: some other node
> 
> normal case:
> 
>                    O                         N
>                   / \                       / \
>                  /   \                     /   \
>                 L     \                   L     \
>                / \     P      ---->      / \     P
>                       / \                       / \
>                      /                         /
>                     N                         C
>                      \                       / \
>                       \
>                        C
>                       / \
> 
> special case:
>                   O|P                        N
>                   / \                       / \
>                  /   \                     /   \
>                 L     \                   L     \
>                / \     N      ---->      /       C
>                         \                       / \
>                          \
>                           C
>                          / \
> 
> Notice that for the special case we don't have to reconnect C to N.
> 
> Signed-off-by: Wolfram Strepp <wstrepp@gmx.de>
> Signed-off-by: Peter Zijlstra <a.p.zijlstra@chello.nl>
> Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
> [Linux commit 4c60117811171d867d4f27f17ea07d7419d45dae]
> 
> Ported to Xen.
> 
> Signed-off-by: Praveen Kumar <kpraveen.lkml@gmail.com>
>
Reviewed-by: Dario Faggioli <dario.faggioli@citrix.com>

Regards,
Dario
-- 
<<This happens because I choose it to happen!>> (Raistlin Majere)
-----------------------------------------------------------------
Dario Faggioli, Ph.D, http://about.me/dario.faggioli
Senior Software Engineer, Citrix Systems R&D Ltd., Cambridge (UK)

[-- Attachment #1.2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 819 bytes --]

[-- Attachment #2: Type: text/plain, Size: 127 bytes --]

_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xen.org
https://lists.xen.org/xen-devel

[PATCH v2 05/20] rb_tree: remove redundant if()-condition in rb_erase()

[Praveen Kumar]

Furthermore, notice that the initial checks:

            if (!node->rb_left)
                    child = node->rb_right;
            else if (!node->rb_right)
                    child = node->rb_left;
            else
            {
                    ...
            }
guarantee that old->rb_right is set in the final else branch, therefore
we can omit checking that again.

Signed-off-by: Wolfram Strepp <wstrepp@gmx.de>
Signed-off-by: Peter Zijlstra <a.p.zijlstra@chello.nl>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
[Linux commit 4b324126e0c6c3a5080ca3ec0981e8766ed6f1ee]

Ported to Xen.

Signed-off-by: Praveen Kumar <kpraveen.lkml@gmail.com>
---
 xen/common/rbtree.c | 7 ++++---
 1 file changed, 4 insertions(+), 3 deletions(-)

diff --git a/xen/common/rbtree.c b/xen/common/rbtree.c
index 90db00a5e8..9d3c5fab95 100644
--- a/xen/common/rbtree.c
+++ b/xen/common/rbtree.c
@@ -250,15 +250,16 @@ void rb_erase(struct rb_node *node, struct rb_root *root)
             if (child)
                 rb_set_parent(child, parent);
             parent->rb_left = child;
+
+            node->rb_right = old->rb_right;
+            rb_set_parent(old->rb_right, node);
         }
 
         node->rb_parent_color = old->rb_parent_color;
-        node->rb_right = old->rb_right;
         node->rb_left = old->rb_left;
 
         rb_set_parent(old->rb_left, node);
-        if (old->rb_right)
-            rb_set_parent(old->rb_right, node);
+
         goto color;
     }
 
-- 
2.12.0


_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xen.org
https://lists.xen.org/xen-devel

Re: [PATCH v2 05/20] rb_tree: remove redundant if()-condition in rb_erase()

[Dario Faggioli]

[-- Attachment #1.1: Type: text/plain, Size: 2568 bytes --]

On Sat, 2017-06-17 at 15:02 +0530, Praveen Kumar wrote:
> Furthermore, notice that the initial checks:
> 
>             if (!node->rb_left)
>                     child = node->rb_right;
>             else if (!node->rb_right)
>                     child = node->rb_left;
>             else
>             {
>                     ...
>             }
> guarantee that old->rb_right is set in the final else branch,
> therefore
> we can omit checking that again.
> 
> Signed-off-by: Wolfram Strepp <wstrepp@gmx.de>
> Signed-off-by: Peter Zijlstra <a.p.zijlstra@chello.nl>
> Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
> [Linux commit 4b324126e0c6c3a5080ca3ec0981e8766ed6f1ee]
> 
And yet, the actual patch is slightly different. As in...

> --- a/xen/common/rbtree.c
> +++ b/xen/common/rbtree.c
> @@ -250,15 +250,16 @@ void rb_erase(struct rb_node *node, struct
> rb_root *root)
>              if (child)
>                  rb_set_parent(child, parent);
>              parent->rb_left = child;
> +
> +            node->rb_right = old->rb_right;
> +            rb_set_parent(old->rb_right, node);
>          }
>  
>          node->rb_parent_color = old->rb_parent_color;
> -        node->rb_right = old->rb_right;
>          node->rb_left = old->rb_left;
>  
...In the Linux commit, this blank line is removed too.

>          rb_set_parent(old->rb_left, node);
> -        if (old->rb_right)
> -            rb_set_parent(old->rb_right, node);
> +
>          goto color;
>      }
>  
I don't think this is too big of a deal per se, I'd I'd leave to
maintainers and committers to decide whether something like this is
enough for asking a resend, or whether it can be fixed upon commit or
even left as it is.

For sure, we know that these patches really needs to be, as much as
possible, 1:1 copies of Linux's ones, even in the smallest detail. And
the reason is to make the life of someone wanting to do another round
of import, in future, as easy as possible.

Regards,
Dario
-- 
<<This happens because I choose it to happen!>> (Raistlin Majere)
-----------------------------------------------------------------
Dario Faggioli, Ph.D, http://about.me/dario.faggioli
Senior Software Engineer, Citrix Systems R&D Ltd., Cambridge (UK)

[-- Attachment #1.2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 819 bytes --]

[-- Attachment #2: Type: text/plain, Size: 127 bytes --]

_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xen.org
https://lists.xen.org/xen-devel

Re: [PATCH v2 05/20] rb_tree: remove redundant if()-condition in rb_erase()

[Jan Beulich]

>>> On 19.06.17 at 18:53, <dario.faggioli@citrix.com> wrote:
> On Sat, 2017-06-17 at 15:02 +0530, Praveen Kumar wrote:
>> --- a/xen/common/rbtree.c
>> +++ b/xen/common/rbtree.c
>> @@ -250,15 +250,16 @@ void rb_erase(struct rb_node *node, struct
>> rb_root *root)
>>              if (child)
>>                  rb_set_parent(child, parent);
>>              parent->rb_left = child;
>> +
>> +            node->rb_right = old->rb_right;
>> +            rb_set_parent(old->rb_right, node);
>>          }
>>  
>>          node->rb_parent_color = old->rb_parent_color;
>> -        node->rb_right = old->rb_right;
>>          node->rb_left = old->rb_left;
>>  
> ...In the Linux commit, this blank line is removed too.
> 
>>          rb_set_parent(old->rb_left, node);
>> -        if (old->rb_right)
>> -            rb_set_parent(old->rb_right, node);
>> +
>>          goto color;
>>      }
>>  
> I don't think this is too big of a deal per se, I'd I'd leave to
> maintainers and committers to decide whether something like this is
> enough for asking a resend, or whether it can be fixed upon commit or
> even left as it is.
> 
> For sure, we know that these patches really needs to be, as much as
> possible, 1:1 copies of Linux's ones, even in the smallest detail. And
> the reason is to make the life of someone wanting to do another round
> of import, in future, as easy as possible.

Yes, and it is for this very reason that I'd like to see a resend. Else
there's the risk that fixing this up upon commit causes subsequent
patches to also not apply. The committer, if doing any edits at all,
should not be required to spend meaningful amounts of extra time
on applying a patch (or series).

Jan


_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xen.org
https://lists.xen.org/xen-devel

[PATCH v2 06/20] rbtree: empty nodes have no color

[Praveen Kumar]

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 88d19cf37952 ("timers: Add rb_init_node() to allow for stack
allocated rb nodes") 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
("rbtree: fixed reversed RB_EMPTY_NODE and rb_next/prev").  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.

[sfr@canb.auug.org.au: fix net/ceph/osd_client.c build]
Signed-off-by: Michel Lespinasse <walken@google.com>
Cc: Andrea Arcangeli <aarcange@redhat.com>
Acked-by: David Woodhouse <David.Woodhouse@intel.com>
Cc: Rik van Riel <riel@redhat.com>
Cc: Peter Zijlstra <a.p.zijlstra@chello.nl>
Cc: Daniel Santos <daniel.santos@pobox.com>
Cc: Jens Axboe <axboe@kernel.dk>
Cc: "Eric W. Biederman" <ebiederm@xmission.com>
Cc: John Stultz <john.stultz@linaro.org>
Signed-off-by: Stephen Rothwell <sfr@canb.auug.org.au>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
[Linux commit 4c199a93a2d36b277a9fd209a0f2793f8460a215]

Ported rbtree.h and rbtree.c changes which are relevant to Xen.

Signed-off-by: Praveen Kumar <kpraveen.lkml@gmail.com>
---
 xen/common/rbtree.c      | 4 ++--
 xen/include/xen/rbtree.h | 9 ++++++---
 2 files changed, 8 insertions(+), 5 deletions(-)

diff --git a/xen/common/rbtree.c b/xen/common/rbtree.c
index 9d3c5fab95..2561dbc7d9 100644
--- a/xen/common/rbtree.c
+++ b/xen/common/rbtree.c
@@ -317,7 +317,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
@@ -346,7 +346,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
diff --git a/xen/include/xen/rbtree.h b/xen/include/xen/rbtree.h
index 3eb527eb37..f74b68ce62 100644
--- a/xen/include/xen/rbtree.h
+++ b/xen/include/xen/rbtree.h
@@ -52,9 +52,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))
+
 
 extern void rb_insert_color(struct rb_node *, struct rb_root *);
 extern void rb_erase(struct rb_node *, struct rb_root *);
-- 
2.12.0


_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xen.org
https://lists.xen.org/xen-devel

Re: [PATCH v2 06/20] rbtree: empty nodes have no color

[Dario Faggioli]

[-- Attachment #1.1: Type: text/plain, Size: 3782 bytes --]

On Sat, 2017-06-17 at 15:02 +0530, Praveen Kumar 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 88d19cf37952 ("timers: Add rb_init_node() to allow for stack
> allocated rb nodes") 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
> ("rbtree: fixed reversed RB_EMPTY_NODE and rb_next/prev").  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.
> 
> [sfr@canb.auug.org.au: fix net/ceph/osd_client.c build]
> Signed-off-by: Michel Lespinasse <walken@google.com>
> Cc: Andrea Arcangeli <aarcange@redhat.com>
> Acked-by: David Woodhouse <David.Woodhouse@intel.com>
> Cc: Rik van Riel <riel@redhat.com>
> Cc: Peter Zijlstra <a.p.zijlstra@chello.nl>
> Cc: Daniel Santos <daniel.santos@pobox.com>
> Cc: Jens Axboe <axboe@kernel.dk>
> Cc: "Eric W. Biederman" <ebiederm@xmission.com>
> Cc: John Stultz <john.stultz@linaro.org>
> Signed-off-by: Stephen Rothwell <sfr@canb.auug.org.au>
> Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
> [Linux commit 4c199a93a2d36b277a9fd209a0f2793f8460a215]
> 
> Ported rbtree.h and rbtree.c changes which are relevant to Xen.
> 
> Signed-off-by: Praveen Kumar <kpraveen.lkml@gmail.com>
>
I was about to say:

Reviewed-by: Dario Faggioli <dario.faggioli@citrix.com>

Although...

> diff --git a/xen/include/xen/rbtree.h b/xen/include/xen/rbtree.h
> index 3eb527eb37..f74b68ce62 100644
> --- a/xen/include/xen/rbtree.h
> +++ b/xen/include/xen/rbtree.h
> @@ -52,9 +52,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))
> +
> 
...There's again divergence between this patch and Linux's commit (in
this case, there is one blank line added, which is not in Linux patch).

I'm again uncertain about the severity of this, and about the best
course of action, but please, try to avoid things like this... When
reviewing patches like this, it's very hard to spot the differences,
and these only add noise, and make it even harder :-/

Regards,
Dario
-- 
<<This happens because I choose it to happen!>> (Raistlin Majere)
-----------------------------------------------------------------
Dario Faggioli, Ph.D, http://about.me/dario.faggioli
Senior Software Engineer, Citrix Systems R&D Ltd., Cambridge (UK)

[-- Attachment #1.2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 819 bytes --]

[-- Attachment #2: Type: text/plain, Size: 127 bytes --]

_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xen.org
https://lists.xen.org/xen-devel

[PATCH v2 07/20] rbtree: move some implementation details from rbtree.h to rbtree.c

[Praveen Kumar]

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>
Cc: Andrea Arcangeli <aarcange@redhat.com>
Acked-by: David Woodhouse <David.Woodhouse@intel.com>
Cc: Rik van Riel <riel@redhat.com>
Cc: Peter Zijlstra <a.p.zijlstra@chello.nl>
Cc: Daniel Santos <daniel.santos@pobox.com>
Cc: Jens Axboe <axboe@kernel.dk>
Cc: "Eric W. Biederman" <ebiederm@xmission.com>
Signed-off-by: David Woodhouse <David.Woodhouse@intel.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
[Linux commit bf7ad8eeab995710c766df49c9c69a8592ca0216]

Ported to Xen.

Signed-off-by: Praveen Kumar <kpraveen.lkml@gmail.com>
---
 xen/common/rbtree.c      | 20 +++++++++++++++++++-
 xen/include/xen/rbtree.h | 29 +++++++----------------------
 2 files changed, 26 insertions(+), 23 deletions(-)

diff --git a/xen/common/rbtree.c b/xen/common/rbtree.c
index 2561dbc7d9..49f73e2461 100644
--- a/xen/common/rbtree.c
+++ b/xen/common/rbtree.c
@@ -22,6 +22,24 @@
 #include <xen/types.h>
 #include <xen/rbtree.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_color(rb) | (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;
@@ -255,7 +273,7 @@ void rb_erase(struct rb_node *node, struct rb_root *root)
             rb_set_parent(old->rb_right, node);
         }
 
-        node->rb_parent_color = old->rb_parent_color;
+        node->__rb_parent_color = old->__rb_parent_color;
         node->rb_left = old->rb_left;
 
         rb_set_parent(old->rb_left, node);
diff --git a/xen/include/xen/rbtree.h b/xen/include/xen/rbtree.h
index f74b68ce62..89df40afd0 100644
--- a/xen/include/xen/rbtree.h
+++ b/xen/include/xen/rbtree.h
@@ -21,9 +21,7 @@
 
 struct rb_node
 {
-    unsigned long  rb_parent_color;
-#define RB_RED  0
-#define RB_BLACK 1
+    unsigned long  __rb_parent_color;
     struct rb_node *rb_right;
     struct rb_node *rb_left;
 };
@@ -33,21 +31,7 @@ struct rb_root
     struct rb_node *rb_node;
 };
 
-#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_parent(r)   ((struct rb_node *)((r)->__rb_parent_color & ~3))
 
 #define RB_ROOT (struct rb_root) { NULL, }
 #define rb_entry(ptr, type, member) container_of(ptr, type, member)
@@ -55,9 +39,10 @@ static inline void rb_set_color(struct rb_node *rb, int color)
 #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))
-
+#define RB_EMPTY_NODE(node)  \
+    ((node)->__rb_parent_color == (unsigned long)(node))
+#define RB_CLEAR_NODE(node)  \
+    ((node)->__rb_parent_color = (unsigned long)(node))
 
 extern void rb_insert_color(struct rb_node *, struct rb_root *);
 extern void rb_erase(struct rb_node *, struct rb_root *);
@@ -75,7 +60,7 @@ extern void rb_replace_node(struct rb_node *victim, struct rb_node *new,
 static inline void rb_link_node(struct rb_node * node, struct rb_node * parent,
                                 struct rb_node ** rb_link)
 {
-    node->rb_parent_color = (unsigned long )parent;
+    node->__rb_parent_color = (unsigned long )parent;
     node->rb_left = node->rb_right = NULL;
 
     *rb_link = node;
-- 
2.12.0


_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xen.org
https://lists.xen.org/xen-devel

Re: [PATCH v2 07/20] rbtree: move some implementation details from rbtree.h to rbtree.c

[Dario Faggioli]

[-- Attachment #1.1: Type: text/plain, Size: 869 bytes --]

On Sat, 2017-06-17 at 15:02 +0530, Praveen Kumar wrote:
> --- a/xen/include/xen/rbtree.h
> +++ b/xen/include/xen/rbtree.h
> @@ -21,9 +21,7 @@
>  
>  struct rb_node
>  {
>
The Linux commit converts this into:

struct rb_node {

and..

> -    unsigned long  rb_parent_color;
> -#define RB_RED  0
> -#define RB_BLACK 1
> +    unsigned long  __rb_parent_color;
>      struct rb_node *rb_right;
>      struct rb_node *rb_left;
>  };
> @@ -33,21 +31,7 @@ struct rb_root
>
...this struct here into:

struct rb_root {

The rest looks ok to me.

Regards,
Dario
-- 
<<This happens because I choose it to happen!>> (Raistlin Majere)
-----------------------------------------------------------------
Dario Faggioli, Ph.D, http://about.me/dario.faggioli
Senior Software Engineer, Citrix Systems R&D Ltd., Cambridge (UK)

[-- Attachment #1.2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 819 bytes --]

[-- Attachment #2: Type: text/plain, Size: 127 bytes --]

_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xen.org
https://lists.xen.org/xen-devel

[PATCH v2 08/20] rbtree: break out of rb_insert_color loop after tree rotation

[Praveen Kumar]

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>
Cc: Andrea Arcangeli <aarcange@redhat.com>
Acked-by: David Woodhouse <David.Woodhouse@intel.com>
Cc: Rik van Riel <riel@redhat.com>
Cc: Peter Zijlstra <a.p.zijlstra@chello.nl>
Cc: Daniel Santos <daniel.santos@pobox.com>
Cc: Jens Axboe <axboe@kernel.dk>
Cc: "Eric W. Biederman" <ebiederm@xmission.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
[Linux commit 1f0528653e41ec230c60f5738820e8a544731399]

Ported to Xen.

Signed-off-by: Praveen Kumar <kpraveen.lkml@gmail.com>
---
 xen/common/rbtree.c | 8 ++------
 1 file changed, 2 insertions(+), 6 deletions(-)

diff --git a/xen/common/rbtree.c b/xen/common/rbtree.c
index 49f73e2461..25902c0659 100644
--- a/xen/common/rbtree.c
+++ b/xen/common/rbtree.c
@@ -110,16 +110,14 @@ void rb_insert_color(struct rb_node *node, struct rb_root *root)
 
             if (parent->rb_right == node)
             {
-                register struct rb_node *tmp;
                 __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;
@@ -135,16 +133,14 @@ void rb_insert_color(struct rb_node *node, struct rb_root *root)
 
             if (parent->rb_left == node)
             {
-                register struct rb_node *tmp;
                 __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;
         }
     }
 
-- 
2.12.0


_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xen.org
https://lists.xen.org/xen-devel

Re: [PATCH v2 08/20] rbtree: break out of rb_insert_color loop after tree rotation

[Dario Faggioli]

[-- Attachment #1.1: Type: text/plain, Size: 2459 bytes --]

On Sat, 2017-06-17 at 15:02 +0530, Praveen Kumar wrote:
> 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>
> Cc: Andrea Arcangeli <aarcange@redhat.com>
> Acked-by: David Woodhouse <David.Woodhouse@intel.com>
> Cc: Rik van Riel <riel@redhat.com>
> Cc: Peter Zijlstra <a.p.zijlstra@chello.nl>
> Cc: Daniel Santos <daniel.santos@pobox.com>
> Cc: Jens Axboe <axboe@kernel.dk>
> Cc: "Eric W. Biederman" <ebiederm@xmission.com>
> Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
> [Linux commit 1f0528653e41ec230c60f5738820e8a544731399]
> 
> Ported to Xen.
> 
> Signed-off-by: Praveen Kumar <kpraveen.lkml@gmail.com>
>
Now the patch has all the hunks. There's again some difference in '{'
placement, though, between this patch and the Linux commit.

More specifically, in the Linux commit, this:
> --- a/xen/common/rbtree.c
> +++ b/xen/common/rbtree.c
> @@ -110,16 +110,14 @@ void rb_insert_color(struct rb_node *node,
> struct rb_root *root)
>  
>              if (parent->rb_right == node)
>              {
>
Becomes:

  if (parent->rb_right == node) {

I appreciate that you may not be applying this specific modification
because the Xen style is different. But I actually think you should, as
this file is going to end up being mixed style anyway, so I'd
prioritize staying identical to Linux's commit.

Regards,
Dario
-- 
<<This happens because I choose it to happen!>> (Raistlin Majere)
-----------------------------------------------------------------
Dario Faggioli, Ph.D, http://about.me/dario.faggioli
Senior Software Engineer, Citrix Systems R&D Ltd., Cambridge (UK)

[-- Attachment #1.2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 819 bytes --]

[-- Attachment #2: Type: text/plain, Size: 127 bytes --]

_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xen.org
https://lists.xen.org/xen-devel

[PATCH v2 09/20] rbtree: adjust root color in rb_insert_color() only when necessary

[Praveen Kumar]

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>
Cc: Andrea Arcangeli <aarcange@redhat.com>
Acked-by: David Woodhouse <David.Woodhouse@intel.com>
Cc: Rik van Riel <riel@redhat.com>
Cc: Peter Zijlstra <a.p.zijlstra@chello.nl>
Cc: Daniel Santos <daniel.santos@pobox.com>
Cc: Jens Axboe <axboe@kernel.dk>
Cc: "Eric W. Biederman" <ebiederm@xmission.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
[Linux commit 6d58452dc066db61acdff7b84671db1b11a3de1c]

Ported to Xen.

Signed-off-by: Praveen Kumar <kpraveen.lkml@gmail.com>
---
 xen/common/rbtree.c | 19 ++++++++++++++++---
 1 file changed, 16 insertions(+), 3 deletions(-)

diff --git a/xen/common/rbtree.c b/xen/common/rbtree.c
index 25902c0659..fff8e22526 100644
--- a/xen/common/rbtree.c
+++ b/xen/common/rbtree.c
@@ -90,8 +90,23 @@ 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)
@@ -143,8 +158,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);
 
-- 
2.12.0


_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xen.org
https://lists.xen.org/xen-devel

Re: [PATCH v2 09/20] rbtree: adjust root color in rb_insert_color() only when necessary

[Dario Faggioli]

[-- Attachment #1.1: Type: text/plain, Size: 914 bytes --]

On Sat, 2017-06-17 at 15:02 +0530, Praveen Kumar wrote:
> --- a/xen/common/rbtree.c
> +++ b/xen/common/rbtree.c
> @@ -90,8 +90,23 @@ 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)
>      {
>
And here we are again. (I.e., in the cited Linux's commit, this is
being turned into 'while (true) {`.

So, I think we should gather others' opinion about how to deal with
these aspects of this series. So, I'll stop my review for now, and
chase feedback.

Regards,
Dario
-- 
<<This happens because I choose it to happen!>> (Raistlin Majere)
-----------------------------------------------------------------
Dario Faggioli, Ph.D, http://about.me/dario.faggioli
Senior Software Engineer, Citrix Systems R&D Ltd., Cambridge (UK)

[-- Attachment #1.2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 819 bytes --]

[-- Attachment #2: Type: text/plain, Size: 127 bytes --]

_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xen.org
https://lists.xen.org/xen-devel

Re: [PATCH v2 09/20] rbtree: adjust root color in rb_insert_color() only when necessary

[Jan Beulich]

>>> On 19.06.17 at 19:13, <dario.faggioli@citrix.com> wrote:
> On Sat, 2017-06-17 at 15:02 +0530, Praveen Kumar wrote:
>> --- a/xen/common/rbtree.c
>> +++ b/xen/common/rbtree.c
>> @@ -90,8 +90,23 @@ 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)
>>      {
>>
> And here we are again. (I.e., in the cited Linux's commit, this is
> being turned into 'while (true) {`.
> 
> So, I think we should gather others' opinion about how to deal with
> these aspects of this series. So, I'll stop my review for now, and
> chase feedback.

I fully second your opinion here. I even wonder whether we
shouldn't convert the file back to be fully Linux style first thing,
so that Linux changes can be applied (mostly) as is, specifically
without having to convert tabs to spaces.

Jan


_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xen.org
https://lists.xen.org/xen-devel

Re: [PATCH v2 09/20] rbtree: adjust root color in rb_insert_color() only when necessary

[Dario Faggioli]

[-- Attachment #1.1: Type: text/plain, Size: 1730 bytes --]

On Tue, 2017-06-20 at 01:26 -0600, Jan Beulich wrote:
> > > > On 19.06.17 at 19:13, <dario.faggioli@citrix.com> wrote:
> > And here we are again. (I.e., in the cited Linux's commit, this is
> > being turned into 'while (true) {`.
> > 
> > So, I think we should gather others' opinion about how to deal with
> > these aspects of this series. So, I'll stop my review for now, and
> > chase feedback.
> 
> I fully second your opinion here. I even wonder whether we
> shouldn't convert the file back to be fully Linux style first thing,
> so that Linux changes can be applied (mostly) as is, specifically
> without having to convert tabs to spaces.
> 
That indeed would be good!

Praveen, this would mean having a patch, at the beginning of the
series, which converts the coding style of the files to Linux one.

Basically, that would mean using tabs for indentation, and undoing any
style change that may have been done in our tree, to make the file
adopt the Xen style.

In practise, the idea is ending up with something that is basically
identical to what was in Linux, before all the patches you are porting
were committed (and without the additional parts and features that we
don't need, of course).

At this point, even generating and applying the patches that you are
porting, in this very series, would be really easy, and less error
prone (as it can be almost entirely automated).

Are you up for this?

Thanks and Regards,
Dario
-- 
<<This happens because I choose it to happen!>> (Raistlin Majere)
-----------------------------------------------------------------
Dario Faggioli, Ph.D, http://about.me/dario.faggioli
Senior Software Engineer, Citrix Systems R&D Ltd., Cambridge (UK)

[-- Attachment #1.2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 819 bytes --]

[-- Attachment #2: Type: text/plain, Size: 127 bytes --]

_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xen.org
https://lists.xen.org/xen-devel

Re: [PATCH v2 09/20] rbtree: adjust root color in rb_insert_color() only when necessary

[Praveen Kumar]

Hi Dario and Jan,

Sorry, I missed this update.

On Tue, Jun 20, 2017 at 7:24 PM, Dario Faggioli <dario.faggioli@citrix.
com> wrote:
> 
> On Tue, 2017-06-20 at 01:26 -0600, Jan Beulich wrote:
> > 
> > > 
> > > > 
> > > > > 
> > > > > On 19.06.17 at 19:13, <dario.faggioli@citrix.com> wrote:
> > > And here we are again. (I.e., in the cited Linux's commit, this
> > > is
> > > being turned into 'while (true) {`.
> > > 
> > > So, I think we should gather others' opinion about how to deal
> > > with
> > > these aspects of this series. So, I'll stop my review for now,
> > > and
> > > chase feedback.
> > 
> > I fully second your opinion here. I even wonder whether we
> > shouldn't convert the file back to be fully Linux style first
> > thing,
> > so that Linux changes can be applied (mostly) as is, specifically
> > without having to convert tabs to spaces.
> > 
> That indeed would be good!
> 
> Praveen, this would mean having a patch, at the beginning of the
> series, which converts the coding style of the files to Linux one.
> 
> Basically, that would mean using tabs for indentation, and undoing
> any
> style change that may have been done in our tree, to make the file
> adopt the Xen style.
> 
> In practise, the idea is ending up with something that is basically
> identical to what was in Linux, before all the patches you are
> porting
> were committed (and without the additional parts and features that we
> don't need, of course).
> 
> At this point, even generating and applying the patches that you are
> porting, in this very series, would be really easy, and less error
> prone (as it can be almost entirely automated).
> 
> Are you up for this?

Sounds good. Let me work on the same. Will re-send the updated patch
series having first indentation changes followed by series of changes
in Linux code base ( as sent already )

> 
> 
> Thanks and Regards,
> Dario
> --
> <<This happens because I choose it to happen!>> (Raistlin Majere)
> -----------------------------------------------------------------
> Dario Faggioli, Ph.D, http://about.me/dario.faggioli
> Senior Software Engineer, Citrix Systems R&D Ltd., Cambridge (UK)

_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xen.org
https://lists.xen.org/xen-devel

Re: [PATCH v2 09/20] rbtree: adjust root color in rb_insert_color() only when necessary

[Dario Faggioli]

[-- Attachment #1.1: Type: text/plain, Size: 1374 bytes --]

On Tue, 2017-06-27 at 21:05 +0530, Praveen Kumar wrote:
> Hi Dario and Jan,
> 
> Sorry, I missed this update.
> 
No problem.

> On Tue, Jun 20, 2017 at 7:24 PM, Dario Faggioli
> <dario.faggioli@citrix.com> wrote:
> > In practise, the idea is ending up with something that is basically
> > identical to what was in Linux, before all the patches you are
> > porting
> > were committed (and without the additional parts and features that
> > we
> > don't need, of course).
> > 
> > At this point, even generating and applying the patches that you
> > are
> > porting, in this very series, would be really easy, and less error
> > prone (as it can be almost entirely automated).
> > 
> > Are you up for this?
> 
> Sounds good. Let me work on the same. Will re-send the updated patch
> series having first indentation changes followed by series of changes
> in Linux code base ( as sent already )
> 
Great. Make sure you update your git tree, as some of your patches have
already been committed (which means, of course, you don't have to
include them in the series any longer! :-))

Dario
-- 
<<This happens because I choose it to happen!>> (Raistlin Majere)
-----------------------------------------------------------------
Dario Faggioli, Ph.D, http://about.me/dario.faggioli
Senior Software Engineer, Citrix Systems R&D Ltd., Cambridge (UK)

[-- Attachment #1.2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 819 bytes --]

[-- Attachment #2: Type: text/plain, Size: 127 bytes --]

_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xen.org
https://lists.xen.org/xen-devel

[PATCH v2 10/20] rbtree: low level optimizations in rb_insert_color()

[Praveen Kumar]

- 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.
- Do not use __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>
Cc: Andrea Arcangeli <aarcange@redhat.com>
Acked-by: David Woodhouse <David.Woodhouse@intel.com>
Cc: Rik van Riel <riel@redhat.com>
Cc: Peter Zijlstra <a.p.zijlstra@chello.nl>
Cc: Daniel Santos <daniel.santos@pobox.com>
Cc: Jens Axboe <axboe@kernel.dk>
Cc: "Eric W. Biederman" <ebiederm@xmission.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
[Linux commit 5bc9188aa207dafd47eab57df7c4fe5b3d3f636a]

Ported to Xen.

Signed-off-by: Praveen Kumar <kpraveen.lkml@gmail.com>
---
 xen/common/rbtree.c | 159 +++++++++++++++++++++++++++++++++++++++++-----------
 1 file changed, 127 insertions(+), 32 deletions(-)

diff --git a/xen/common/rbtree.c b/xen/common/rbtree.c
index fff8e22526..d44fa22df5 100644
--- a/xen/common/rbtree.c
+++ b/xen/common/rbtree.c
@@ -22,6 +22,25 @@
 #include <xen/types.h>
 #include <xen/rbtree.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 root to 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
 
@@ -40,6 +59,17 @@ 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 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;
@@ -86,9 +116,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 = rb_red_parent(node), *gparent, *tmp;
 
     while (true)
     {
@@ -99,62 +150,106 @@ 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))
             {
-                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;
-                }
+                /*
+                 * 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;
+                parent = rb_parent(node);
+                rb_set_parent_color(node, parent, RB_RED);
+                continue;
             }
 
             if (parent->rb_right == node)
             {
-                __rb_rotate_left(parent, root);
+                /*
+                 * 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(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
+             *
+             *        G           P
+             *       / \         / \
+             *      p   U  -->  n   g
+             *     /                 \
+             *    n                   U
+             */
+            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 {
+            tmp = gparent->rb_left;
+            if (tmp && rb_is_red(tmp))
             {
-                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;
-                }
+                /* Case 1 - color flips */
+                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;
             }
 
             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;
         }
     }
-- 
2.12.0


_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xen.org
https://lists.xen.org/xen-devel

[PATCH v2 11/20] rbtree: adjust node color in __rb_erase_color() only when necessary

[Praveen Kumar]

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.

[adrian.hunter@intel.com: perf tools: fix build for another rbtree.c change]
Signed-off-by: Michel Lespinasse <walken@google.com>
Cc: Andrea Arcangeli <aarcange@redhat.com>
Acked-by: David Woodhouse <David.Woodhouse@intel.com>
Cc: Rik van Riel <riel@redhat.com>
Cc: Peter Zijlstra <a.p.zijlstra@chello.nl>
Cc: Daniel Santos <daniel.santos@pobox.com>
Cc: Jens Axboe <axboe@kernel.dk>
Cc: "Eric W. Biederman" <ebiederm@xmission.com>
Signed-off-by: Adrian Hunter <adrian.hunter@intel.com>
Cc: Alexander Shishkin <alexander.shishkin@intel.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
[Linux commit d6ff1273928ebf15466a85b7e1810cd00e72998b]

Ported only rbtree.c to Xen.

Signed-off-by: Praveen Kumar <kpraveen.lkml@gmail.com>
---
 xen/common/rbtree.c | 22 ++++++++++++++++------
 1 file changed, 16 insertions(+), 6 deletions(-)

diff --git a/xen/common/rbtree.c b/xen/common/rbtree.c
index d44fa22df5..2d5da9ea28 100644
--- a/xen/common/rbtree.c
+++ b/xen/common/rbtree.c
@@ -261,10 +261,24 @@ 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)
+    while (true)
     {
-        if (parent->rb_left == node)
+        /*
+         * 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))
             {
@@ -293,7 +307,6 @@ 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;
             }
         }
@@ -327,13 +340,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)
-- 
2.12.0


_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xen.org
https://lists.xen.org/xen-devel

[PATCH v2 12/20] rbtree: optimize case selection logic in __rb_erase_color()

[Praveen Kumar]

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>
Cc: Andrea Arcangeli <aarcange@redhat.com>
Acked-by: David Woodhouse <David.Woodhouse@intel.com>
Cc: Rik van Riel <riel@redhat.com>
Cc: Peter Zijlstra <a.p.zijlstra@chello.nl>
Cc: Daniel Santos <daniel.santos@pobox.com>
Cc: Jens Axboe <axboe@kernel.dk>
Cc: "Eric W. Biederman" <ebiederm@xmission.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
[Linux commit e125d1471a4f8f1bf7ea9a83deb8d23cb40bd712]

Ported to Xen.

Signed-off-by: Praveen Kumar <kpraveen.lkml@gmail.com>
---
 xen/common/rbtree.c | 62 ++++++++++++++++++++++++-----------------------------
 1 file changed, 28 insertions(+), 34 deletions(-)

diff --git a/xen/common/rbtree.c b/xen/common/rbtree.c
index 2d5da9ea28..a365670369 100644
--- a/xen/common/rbtree.c
+++ b/xen/common/rbtree.c
@@ -287,28 +287,25 @@ 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)))
+            if (!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))
+                if (!other->rb_left || rb_is_black(other->rb_left))
                 {
-                    rb_set_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
         {
@@ -320,28 +317,25 @@ 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)))
+            if (!other->rb_left || rb_is_black(other->rb_left))
             {
-                rb_set_red(other);
-                node = parent;
-                parent = rb_parent(node);
-            }
-            else
-            {
-                if (!other->rb_left || rb_is_black(other->rb_left))
+                if (!other->rb_right || rb_is_black(other->rb_right))
                 {
-                    rb_set_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;
         }
     }
 }
-- 
2.12.0


_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xen.org
https://lists.xen.org/xen-devel

[PATCH v2 13/20] rbtree: low level optimizations in __rb_erase_color()

[Praveen Kumar]

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.

Also 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>
Cc: Andrea Arcangeli <aarcange@redhat.com>
Acked-by: David Woodhouse <David.Woodhouse@intel.com>
Cc: Rik van Riel <riel@redhat.com>
Cc: Peter Zijlstra <a.p.zijlstra@chello.nl>
Cc: Daniel Santos <daniel.santos@pobox.com>
Cc: Jens Axboe <axboe@kernel.dk>
Cc: "Eric W. Biederman" <ebiederm@xmission.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
[Linux commit 6280d2356fd8ad0936a63c10dc1e6accf48d0c61]

Ported to Xen.

Signed-off-by: Praveen Kumar <kpraveen.lkml@gmail.com>
---
 xen/common/rbtree.c | 196 ++++++++++++++++++++++++++++------------------------
 1 file changed, 107 insertions(+), 89 deletions(-)

diff --git a/xen/common/rbtree.c b/xen/common/rbtree.c
index a365670369..1fe059a568 100644
--- a/xen/common/rbtree.c
+++ b/xen/common/rbtree.c
@@ -38,7 +38,8 @@
  *  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 within
+ *  parentheses and have some accompanying text comment.
  */
 
 #define    RB_RED    0
@@ -47,17 +48,11 @@
 #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_color(rb) | (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)
@@ -70,52 +65,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
@@ -259,7 +208,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)
     {
@@ -274,67 +223,136 @@ static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,
          */
         if (node && rb_is_red(node))
         {
-            rb_set_black(node);
+            rb_set_parent_color(node, parent, RB_BLACK);
             break;
         } else if (!parent) {
             break;
         } else if (parent->rb_left == node) {
-            other = parent->rb_right;
-            if (rb_is_red(other))
+            sibling = parent->rb_right;
+            if (rb_is_red(sibling))
             {
-                rb_set_black(other);
-                rb_set_red(parent);
-                __rb_rotate_left(parent, root);
-                other = parent->rb_right;
+                /*
+                 * 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);
+                sibling = tmp1;
             }
-            if (!other->rb_right || rb_is_black(other->rb_right))
+            tmp1 = sibling->rb_right;
+            if (!tmp1 || rb_is_black(tmp1))
             {
-                if (!other->rb_left || rb_is_black(other->rb_left))
+                tmp2 = sibling->rb_left;
+                if (!tmp2 || rb_is_black(tmp2))
                 {
-                    rb_set_red(other);
+                    /*
+                     * 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.
+                     */
+                    rb_set_parent_color(sibling, parent, RB_RED);
                     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
+                 * (p could be either color here)
+                 *
+                 *   (p)           (p)
+                 *   / \           / \
+                 *  N   S    -->  N   Sl
+                 *     / \             \
+                 *    sl  Sr            s
+                 *                       \
+                 *                        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);
+                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
+             * (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)
+             */
+            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))
+            sibling = parent->rb_left;
+            if (rb_is_red(sibling))
             {
-                rb_set_black(other);
-                rb_set_red(parent);
-                __rb_rotate_right(parent, root);
-                other = parent->rb_left;
+                /* 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))
+            tmp1 = sibling->rb_left;
+            if (!tmp1 || rb_is_black(tmp1))
             {
-                if (!other->rb_right || rb_is_black(other->rb_right))
+                tmp2 = sibling->rb_right;
+                if (!tmp2 || rb_is_black(tmp2))
                 {
-                    rb_set_red(other);
+                    /* Case 2 - sibling color flip */
+                    rb_set_parent_color(sibling, parent, RB_RED);
                     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;
         }
     }
-- 
2.12.0


_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xen.org
https://lists.xen.org/xen-devel

[PATCH v2 14/20] rbtree: coding style adjustments

[Praveen Kumar]

Set comment and indentation style to be consistent with linux coding style
and the rest of the file, as suggested by Peter Zijlstra

Signed-off-by: Michel Lespinasse <walken@google.com>
Cc: Andrea Arcangeli <aarcange@redhat.com>
Acked-by: David Woodhouse <David.Woodhouse@intel.com>
Cc: Rik van Riel <riel@redhat.com>
Cc: Peter Zijlstra <a.p.zijlstra@chello.nl>
Cc: Daniel Santos <daniel.santos@pobox.com>
Cc: Jens Axboe <axboe@kernel.dk>
Cc: "Eric W. Biederman" <ebiederm@xmission.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
[Linux commit 7ce6ff9e5de99e7b72019c7de82fb438fe1dc5a0]

Ported to Xen.

Signed-off-by: Praveen Kumar <kpraveen.lkml@gmail.com>
---
 xen/common/rbtree.c | 44 ++++++++++++++++++++++++--------------------
 1 file changed, 24 insertions(+), 20 deletions(-)

diff --git a/xen/common/rbtree.c b/xen/common/rbtree.c
index 1fe059a568..1cbe9a53d7 100644
--- a/xen/common/rbtree.c
+++ b/xen/common/rbtree.c
@@ -367,16 +367,14 @@ void rb_erase(struct rb_node *node, struct rb_root *root)
         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;
         while ((left = node->rb_left) != NULL)
             node = left;
 
-        if (rb_parent(old))
-        {
+        if (rb_parent(old)) {
             if (rb_parent(old)->rb_left == old)
                 rb_parent(old)->rb_left = node;
             else
@@ -412,14 +410,12 @@ void rb_erase(struct rb_node *node, struct rb_root *root)
 
     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:
@@ -464,8 +460,10 @@ struct rb_node *rb_next(const struct rb_node *node)
     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)
@@ -473,12 +471,14 @@ struct rb_node *rb_next(const struct rb_node *node)
         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;
 
@@ -493,8 +493,10 @@ struct rb_node *rb_prev(const struct rb_node *node)
     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)
@@ -502,8 +504,10 @@ struct rb_node *rb_prev(const struct rb_node *node)
         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;
 
-- 
2.12.0


_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xen.org
https://lists.xen.org/xen-devel

[PATCH v2 15/20] rbtree: optimize fetching of sibling node

[Praveen Kumar]

When looking to fetch a node's sibling, we went through a sequence of:
- check if node is the parent's left child
- if it is, then fetch the parent's right child

This can be replaced with:
- fetch the parent's right child as an assumed sibling
- check that node is NOT the fetched child

This avoids fetching the parent's left child when node is actually
that child. Saves a bit on code size, though it doesn't seem to make
a large difference in speed.

Signed-off-by: Michel Lespinasse <walken@google.com>
Cc: Andrea Arcangeli <aarcange@redhat.com>
Cc: David Woodhouse <David.Woodhouse@intel.com>
Acked-by: Rik van Riel <riel@redhat.com>
Cc: Peter Zijlstra <a.p.zijlstra@chello.nl>
Cc: Daniel Santos <daniel.santos@pobox.com>
Cc: Jens Axboe <axboe@kernel.dk>
Cc: "Eric W. Biederman" <ebiederm@xmission.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
[Linux commit 59633abf34e2f44b8e772a2c12a92132aa7c2220]

Ported to Xen.

Signed-off-by: Praveen Kumar <kpraveen.lkml@gmail.com>
---
 xen/common/rbtree.c | 15 +++++++++------
 1 file changed, 9 insertions(+), 6 deletions(-)

diff --git a/xen/common/rbtree.c b/xen/common/rbtree.c
index 1cbe9a53d7..8c28ab1967 100644
--- a/xen/common/rbtree.c
+++ b/xen/common/rbtree.c
@@ -108,9 +108,9 @@ void rb_insert_color(struct rb_node *node, struct rb_root *root)
 
         gparent = rb_red_parent(parent);
 
-        if (parent == gparent->rb_left)
+        tmp = gparent->rb_right;
+        if (parent != tmp)    /* parent == gparent->rb_left */
         {
-            tmp = gparent->rb_right;
             if (tmp && rb_is_red(tmp))
             {
                 /*
@@ -134,7 +134,8 @@ void rb_insert_color(struct rb_node *node, struct rb_root *root)
                 continue;
             }
 
-            if (parent->rb_right == node)
+            tmp = parent->rb_right;
+            if (node == tmp)
             {
                 /*
                  * Case 2 - left rotate at parent
@@ -164,7 +165,7 @@ void rb_insert_color(struct rb_node *node, struct rb_root *root)
              *     /                 \
              *    n                   U
              */
-            gparent->rb_left = tmp = parent->rb_right;
+            gparent->rb_left = tmp;    /* == parent->rb_right */
             parent->rb_right = gparent;
             if (tmp)
                 rb_set_parent_color(tmp, gparent, RB_BLACK);
@@ -227,8 +228,10 @@ static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,
             break;
         } else if (!parent) {
             break;
-        } else if (parent->rb_left == node) {
-            sibling = parent->rb_right;
+        }
+        sibling = parent->rb_right;
+        if ( node != sibling)    /* node == parent->rb_left */
+        {
             if (rb_is_red(sibling))
             {
                 /*
-- 
2.12.0


_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xen.org
https://lists.xen.org/xen-devel

[PATCH v2 16/20] rbtree: add __rb_change_child() helper function

[Praveen Kumar]

Add __rb_change_child() as an inline helper function to replace code that
would otherwise be duplicated 4 times in the source.

No changes to binary size or speed.

Signed-off-by: Michel Lespinasse <walken@google.com>
Reviewed-by: Rik van Riel <riel@redhat.com>
Cc: Peter Zijlstra <a.p.zijlstra@chello.nl>
Cc: Andrea Arcangeli <aarcange@redhat.com>
Cc: David Woodhouse <dwmw2@infradead.org>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
[Linux commit 7abc704ae399fcb9c51ca200b0456f8a975a8011]

Ported to Xen.

Signed-off-by: Praveen Kumar <kpraveen.lkml@gmail.com>
---
 xen/common/rbtree.c | 37 +++++++++++--------------------------
 1 file changed, 11 insertions(+), 26 deletions(-)

diff --git a/xen/common/rbtree.c b/xen/common/rbtree.c
index 8c28ab1967..2063536548 100644
--- a/xen/common/rbtree.c
+++ b/xen/common/rbtree.c
@@ -65,6 +65,13 @@ static inline struct rb_node *rb_red_parent(struct rb_node *red)
     return (struct rb_node *)red->__rb_parent_color;
 }
 
+static inline void
+__rb_change_child(struct rb_node *old, struct rb_node *new,
+                 struct rb_node *parent, struct rb_root *root)
+{
+    __rb_change_child(old, new, parent, root);
+}
+
 /*
  * Helper function for rotations:
  * - old's parent and color get assigned to new
@@ -376,15 +383,7 @@ void rb_erase(struct rb_node *node, struct rb_root *root)
         node = node->rb_right;
         while ((left = node->rb_left) != NULL)
             node = left;
-
-        if (rb_parent(old)) {
-            if (rb_parent(old)->rb_left == old)
-                rb_parent(old)->rb_left = node;
-            else
-                rb_parent(old)->rb_right = node;
-        } else
-            root->rb_node = node;
-
+        __rb_change_child(old, node, rb_parent(old), root);
         child = node->rb_right;
         parent = rb_parent(node);
         color = rb_color(node);
@@ -413,15 +412,8 @@ void rb_erase(struct rb_node *node, struct rb_root *root)
 
     if (child)
         rb_set_parent(child, parent);
-    if (parent) {
-        if (parent->rb_left == node)
-            parent->rb_left = child;
-        else
-            parent->rb_right = child;
-    } else
-        root->rb_node = child;
-
- color:
+    __rb_change_child(node, child, parent, root);
+color:
     if (color == RB_BLACK)
         __rb_erase_color(child, parent, root);
 }
@@ -524,14 +516,7 @@ void rb_replace_node(struct rb_node *victim, struct rb_node *new,
     struct rb_node *parent = rb_parent(victim);
 
     /* Set the surrounding nodes to point to the replacement */
-    if (parent) {
-        if (victim == parent->rb_left)
-            parent->rb_left = new;
-        else
-            parent->rb_right = new;
-    } else {
-        root->rb_node = new;
-    }
+    __rb_change_child(victim, new, parent, root);
     if (victim->rb_left)
         rb_set_parent(victim->rb_left, new);
     if (victim->rb_right)
-- 
2.12.0


_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xen.org
https://lists.xen.org/xen-devel

[PATCH v2 17/20] rbtree: place easiest case first in rb_erase()

[Praveen Kumar]

In rb_erase, move the easy case (node to erase has no more than
1 child) first. I feel the code reads easier that way.

Signed-off-by: Michel Lespinasse <walken@google.com>
Reviewed-by: Rik van Riel <riel@redhat.com>
Cc: Peter Zijlstra <a.p.zijlstra@chello.nl>
Cc: Andrea Arcangeli <aarcange@redhat.com>
Cc: David Woodhouse <dwmw2@infradead.org>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
[Linux commit 60670b8034d6e2ba860af79c9379b7788d09db73]

Ported to Xen.

Signed-off-by: Praveen Kumar <kpraveen.lkml@gmail.com>
---
 xen/common/rbtree.c | 34 ++++++++++++++++++----------------
 1 file changed, 18 insertions(+), 16 deletions(-)

diff --git a/xen/common/rbtree.c b/xen/common/rbtree.c
index 2063536548..149c861ac6 100644
--- a/xen/common/rbtree.c
+++ b/xen/common/rbtree.c
@@ -370,17 +370,28 @@ static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,
 
 void rb_erase(struct rb_node *node, struct rb_root *root)
 {
-    struct rb_node *child, *parent;
+    struct rb_node *child = node->rb_right, *tmp = node->rb_left;
+    struct rb_node *parent;
     int color;
 
-    if (!node->rb_left)
-        child = node->rb_right;
-    else if (!node->rb_right)
-        child = node->rb_left;
-    else {
+	if (!tmp) {
+    case1:
+        /* Case 1: node to erase has no more than 1 child (easy!) */
+
+        parent = rb_parent(node);
+        color = rb_color(node);
+
+        if (child)
+            rb_set_parent(child, parent);
+        __rb_change_child(node, child, parent, root);
+    } else if (!child) {
+        /* Still case 1, but this time the child is node->rb_left */
+        child = tmp;
+        goto case1;
+    } else {
         struct rb_node *old = node, *left;
 
-        node = node->rb_right;
+        node = child;
         while ((left = node->rb_left) != NULL)
             node = left;
         __rb_change_child(old, node, rb_parent(old), root);
@@ -403,17 +414,8 @@ void rb_erase(struct rb_node *node, struct rb_root *root)
         node->rb_left = old->rb_left;
 
         rb_set_parent(old->rb_left, node);
-
-        goto color;
     }
 
-    parent = rb_parent(node);
-    color = rb_color(node);
-
-    if (child)
-        rb_set_parent(child, parent);
-    __rb_change_child(node, child, parent, root);
-color:
     if (color == RB_BLACK)
         __rb_erase_color(child, parent, root);
 }
-- 
2.12.0


_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xen.org
https://lists.xen.org/xen-devel

[PATCH v2 18/20] rbtree: handle 1-child recoloring in rb_erase() instead of rb_erase_color()

[Praveen Kumar]

An interesting observation for rb_erase() is that when a node has
exactly one child, the node must be black and the child must be red.
An interesting consequence is that removing such a node can be done by
simply replacing it with its child and making the child black,
which we can do efficiently in rb_erase(). __rb_erase_color() then
only needs to handle the no-childs case and can be modified accordingly.

Signed-off-by: Michel Lespinasse <walken@google.com>
Acked-by: Rik van Riel <riel@redhat.com>
Cc: Peter Zijlstra <a.p.zijlstra@chello.nl>
Cc: Andrea Arcangeli <aarcange@redhat.com>
Cc: David Woodhouse <dwmw2@infradead.org>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
[Linux commit 46b6135a7402ac23c5b25f2bd79b03bab8f98278]

Ported to Xen.

Signed-off-by: Praveen Kumar <kpraveen.lkml@gmail.com>
---
 xen/common/rbtree.c | 110 +++++++++++++++++++++++++++++++---------------------
 1 file changed, 66 insertions(+), 44 deletions(-)

diff --git a/xen/common/rbtree.c b/xen/common/rbtree.c
index 149c861ac6..dfe566a5af 100644
--- a/xen/common/rbtree.c
+++ b/xen/common/rbtree.c
@@ -2,6 +2,7 @@
   Red Black Trees
   (C) 1999  Andrea Arcangeli <andrea@suse.de>
   (C) 2002  David Woodhouse <dwmw2@infradead.org>
+  (C) 2012  Michel Lespinasse <walken@google.com>
   
   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
@@ -49,6 +50,11 @@
 #define rb_is_red(r)    (!rb_color(r))
 #define rb_is_black(r)  rb_color(r)
 
+static inline void rb_set_black(struct rb_node *rb)
+{
+    rb->__rb_parent_color |= RB_BLACK;
+}
+
 static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p)
 {
     rb->__rb_parent_color = rb_color(rb) | (unsigned long)p;
@@ -213,29 +219,19 @@ void rb_insert_color(struct rb_node *node, struct rb_root *root)
 }
 EXPORT_SYMBOL(rb_insert_color);
 
-static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,
-                             struct rb_root *root)
+static void __rb_erase_color(struct rb_node *parent, struct rb_root *root)
 {
-    struct rb_node *sibling, *tmp1, *tmp2;
+    struct rb_node *node = NULL, *sibling, *tmp1, *tmp2;
 
     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.
+         * Loop invariants:
+         * - node is black (or NULL on first iteration)
+         * - node is not the root (parent is not NULL)
+         * - All leaf paths going through parent and node have a
+         *   black node count that is 1 lower than other leaf paths.
          */
-        if (node && rb_is_red(node))
-        {
-            rb_set_parent_color(node, parent, RB_BLACK);
-            break;
-        } else if (!parent) {
-            break;
-        }
         sibling = parent->rb_right;
         if ( node != sibling)    /* node == parent->rb_left */
         {
@@ -272,16 +268,22 @@ static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,
                      *      / \           / \
                      *     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.
+                     * This leaves us violating 5) which
+                     * can be fixed by flipping p to black
+                     * if it was red, or by recursing at p.
+                     * p is red when coming from Case 1.
                      */
                     rb_set_parent_color(sibling, parent, RB_RED);
-                    node = parent;
-                    parent = rb_parent(node);
-                    continue;
+                    if (rb_is_red(parent))
+                        rb_set_black(parent);
+                    else
+                    {
+                        node = parent;
+                        parent = rb_parent(node);
+                        if (parent)
+                            continue;
+                    }
+                    break;
                 }
                 /*
                  * Case 3 - right rotate at sibling
@@ -343,9 +345,16 @@ static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,
                 {
                     /* Case 2 - sibling color flip */
                     rb_set_parent_color(sibling, parent, RB_RED);
-                    node = parent;
-                    parent = rb_parent(node);
-                    continue;
+                    if (rb_is_red(parent))
+                        rb_set_black(parent);
+                    else
+                    {
+                        node = parent;
+                        parent = rb_parent(node);
+                        if (parent)
+                            continue;
+                    }
+                    break;
                 }
                 /* Case 3 - right rotate at sibling */
                 sibling->rb_right = tmp1 = tmp2->rb_left;
@@ -371,23 +380,32 @@ static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,
 void rb_erase(struct rb_node *node, struct rb_root *root)
 {
     struct rb_node *child = node->rb_right, *tmp = node->rb_left;
-    struct rb_node *parent;
-    int color;
-
+    struct rb_node *parent, *rebalance;
+ 
 	if (!tmp) {
-    case1:
-        /* Case 1: node to erase has no more than 1 child (easy!) */
+        /*
+         * Case 1: node to erase has no more than 1 child (easy!)
+         *
+         * Note that if there is one child it must be red due to 5)
+         * and node must be black due to 4). We adjust colors locally
+         * so as to bypass __rb_erase_color() later on.
+         */
 
         parent = rb_parent(node);
-        color = rb_color(node);
-
-        if (child)
-            rb_set_parent(child, parent);
         __rb_change_child(node, child, parent, root);
+        if (child)
+        {
+            rb_set_parent_color(child, parent, RB_BLACK);
+            rebalance = NULL;
+        } else {
+            rebalance = rb_is_black(node) ? parent : NULL;
+        }
     } else if (!child) {
         /* Still case 1, but this time the child is node->rb_left */
-        child = tmp;
-        goto case1;
+        parent = rb_parent(node);
+        __rb_change_child(node, tmp, parent, root);
+        rb_set_parent_color(tmp, parent, RB_BLACK);
+        rebalance = NULL;
     } else {
         struct rb_node *old = node, *left;
 
@@ -397,27 +415,31 @@ void rb_erase(struct rb_node *node, struct rb_root *root)
         __rb_change_child(old, node, rb_parent(old), root);
         child = node->rb_right;
         parent = rb_parent(node);
-        color = rb_color(node);
 
         if (parent == old) {
             parent = node;
         } else {
-            if (child)
-                rb_set_parent(child, parent);
             parent->rb_left = child;
 
             node->rb_right = old->rb_right;
             rb_set_parent(old->rb_right, node);
         }
 
+        if (child) {
+            rb_set_parent_color(child, parent, RB_BLACK);
+            rebalance = NULL;
+        } else {
+            rebalance = rb_is_black(node) ? parent : NULL;
+        }
+
         node->__rb_parent_color = old->__rb_parent_color;
         node->rb_left = old->rb_left;
 
         rb_set_parent(old->rb_left, node);
     }
 
-    if (color == RB_BLACK)
-        __rb_erase_color(child, parent, root);
+    if (rebalance)
+        __rb_erase_color(rebalance, root);
 }
 EXPORT_SYMBOL(rb_erase);
 
-- 
2.12.0


_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xen.org
https://lists.xen.org/xen-devel

[PATCH v2 19/20] rbtree: low level optimizations in rb_erase()

[Praveen Kumar]

Various minor optimizations in rb_erase():
- Avoid multiple loading of node->__rb_parent_color when computing parent
  and color information (possibly not in close sequence, as there might
  be further branches in the algorithm)
- In the 1-child subcase of case 1, copy the __rb_parent_color field from
  the erased node to the child instead of recomputing it from the desired
  parent and color
- When searching for the erased node's successor, differentiate between
  cases 2 and 3 based on whether any left links were followed. This avoids
  a condition later down.
- In case 3, keep a pointer to the erased node's right child so we don't
  have to refetch it later to adjust its parent.
- In the no-childs subcase of cases 2 and 3, place the rebalance assigment
  last so that the compiler can remove the following if(rebalance) test.

Also, added some comments to illustrate cases 2 and 3.

Signed-off-by: Michel Lespinasse <walken@google.com>
Acked-by: Rik van Riel <riel@redhat.com>
Cc: Peter Zijlstra <a.p.zijlstra@chello.nl>
Cc: Andrea Arcangeli <aarcange@redhat.com>
Cc: David Woodhouse <dwmw2@infradead.org>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
[Linux commit 4f035ad67f4633c233cb3642711d49b4efc9c82d]

Ported to Xen.

Signed-off-by: Praveen Kumar <kpraveen.lkml@gmail.com>
---
 xen/common/rbtree.c | 100 +++++++++++++++++++++++++++++++++++-----------------
 1 file changed, 67 insertions(+), 33 deletions(-)

diff --git a/xen/common/rbtree.c b/xen/common/rbtree.c
index dfe566a5af..68e505bede 100644
--- a/xen/common/rbtree.c
+++ b/xen/common/rbtree.c
@@ -46,9 +46,14 @@
 #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_parent(pc)    ((struct rb_node *)(pc & ~3))
+
+#define __rb_color(pc)     ((pc) & 1)
+#define __rb_is_black(pc)  __rb_color(pc)
+#define __rb_is_red(pc)    (!__rb_color(pc))
+#define rb_color(rb)       __rb_color((rb)->__rb_parent_color)
+#define rb_is_red(rb)      __rb_is_red((rb)->__rb_parent_color)
+#define rb_is_black(rb)    __rb_is_black((rb)->__rb_parent_color)
 
 static inline void rb_set_black(struct rb_node *rb)
 {
@@ -381,6 +386,7 @@ void rb_erase(struct rb_node *node, struct rb_root *root)
 {
     struct rb_node *child = node->rb_right, *tmp = node->rb_left;
     struct rb_node *parent, *rebalance;
+    unsigned long pc;
  
 	if (!tmp) {
         /*
@@ -391,51 +397,79 @@ void rb_erase(struct rb_node *node, struct rb_root *root)
          * so as to bypass __rb_erase_color() later on.
          */
 
-        parent = rb_parent(node);
+        pc = node->__rb_parent_color;
+        parent = __rb_parent(pc);
         __rb_change_child(node, child, parent, root);
         if (child)
         {
-            rb_set_parent_color(child, parent, RB_BLACK);
+            child->__rb_parent_color = pc;
             rebalance = NULL;
-        } else {
-            rebalance = rb_is_black(node) ? parent : NULL;
-        }
+        } else
+            rebalance = __rb_is_black(pc) ? parent : NULL;
     } else if (!child) {
         /* Still case 1, but this time the child is node->rb_left */
-        parent = rb_parent(node);
+        tmp->__rb_parent_color = pc = node->__rb_parent_color;
+        parent = __rb_parent(pc);
         __rb_change_child(node, tmp, parent, root);
-        rb_set_parent_color(tmp, parent, RB_BLACK);
         rebalance = NULL;
     } else {
-        struct rb_node *old = node, *left;
-
-        node = child;
-        while ((left = node->rb_left) != NULL)
-            node = left;
-        __rb_change_child(old, node, rb_parent(old), root);
-        child = node->rb_right;
-        parent = rb_parent(node);
-
-        if (parent == old) {
-            parent = node;
+        struct rb_node *successor = child, *child2;
+        tmp = child->rb_left;
+        if (!tmp)
+        {
+            /*
+             * Case 2: node's successor is its right child
+             *
+             *    (n)          (s)
+             *    / \          / \
+             *  (x) (s)  ->  (x) (c)
+             *        \
+             *        (c)
+             */
+            parent = child;
+            child2 = child->rb_right;
         } else {
-            parent->rb_left = child;
-
-            node->rb_right = old->rb_right;
-            rb_set_parent(old->rb_right, node);
+            /*
+             * Case 3: node's successor is leftmost under
+             * node's right child subtree
+             *
+             *    (n)          (s)
+             *    / \          / \
+             *  (x) (y)  ->  (x) (y)
+             *      /            /
+             *    (p)          (p)
+             *    /            /
+             *  (s)          (c)
+             *    \
+             *    (c)
+             */
+            do
+            {
+                parent = successor;
+                successor = tmp;
+                tmp = tmp->rb_left;
+            } while (tmp);
+            parent->rb_left = child2 = successor->rb_right;
+            successor->rb_right = child;
+            rb_set_parent(child, successor);
         }
 
-        if (child) {
-            rb_set_parent_color(child, parent, RB_BLACK);
+        successor->rb_left = tmp = node->rb_left;
+        rb_set_parent(tmp, successor);
+
+        pc = node->__rb_parent_color;
+        tmp = __rb_parent(pc);
+        __rb_change_child(node, successor, tmp, root);
+        if (child2)
+        {
+            successor->__rb_parent_color = pc;
+            rb_set_parent_color(child2, parent, RB_BLACK);
             rebalance = NULL;
         } else {
-            rebalance = rb_is_black(node) ? parent : NULL;
+            unsigned long pc2 = successor->__rb_parent_color;
+            successor->__rb_parent_color = pc;
+            rebalance = __rb_is_black(pc2) ? parent : NULL;
         }
-
-        node->__rb_parent_color = old->__rb_parent_color;
-        node->rb_left = old->rb_left;
-
-        rb_set_parent(old->rb_left, node);
     }
 
     if (rebalance)
-- 
2.12.0


_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xen.org
https://lists.xen.org/xen-devel

[PATCH 20/20] lib/rbtree.c: fix typo in comment of __rb_insert()

[Praveen Kumar]

In case 1, it passes down the BLACK color from G to p and u, and maintains
the color of n.  By doing so, it maintains the black height of the sub-tree.

While in the comment, it marks the color of n to BLACK.  This is a typo
and not consistents with the code.

This patch fixs this typo in comment.

Signed-off-by: Wei Yang <weiyang@linux.vnet.ibm.com>
Acked-by: Michel Lespinasse <walken@google.com>
Cc: Xiao Guangrong <xiaoguangrong@linux.vnet.ibm.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
[Linux commit 1b9c53e849aa65776d4f611d99aa09f856518dad]

Ported to Xen for rb_insert_color API.

Signed-off-by: Praveen Kumar <kpraveen.lkml@gmail.com>
---
 xen/common/rbtree.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/xen/common/rbtree.c b/xen/common/rbtree.c
index 68e505bede..4fe5354785 100644
--- a/xen/common/rbtree.c
+++ b/xen/common/rbtree.c
@@ -138,7 +138,7 @@ void rb_insert_color(struct rb_node *node, struct rb_root *root)
                  *      / \          / \
                  *     p   u  -->   P   U
                  *    /            /
-                 *   n            N
+                 *   n            n
                  *
                  * However, since g's parent might be red, and
                  * 4) does not allow this, we need to recurse
-- 
2.12.0


_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xen.org
https://lists.xen.org/xen-devel