[Xen-devel[PATCH Resend v2] xen: common: rbtree: ported updates from linux tree

[Xen-devel[PATCH Resend v2] xen: common: rbtree: ported updates from linux tree

[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 and rcu rbtree functionality to the xen tree,
as there was no specific requirement for current planned implementation.

Please share your inputs. Thanks in advance.

From Praveen Kumar <kpraveen.lkml@gmail.com> # This line is ignored.
From: Praveen Kumar <kpraveen.lkml@gmail.com>
Subject: 
In-Reply-To: 


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

[Resend][PATCH 01/17] 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.

commit 16c047add3ceaf0ab882e3e094d1ec904d02312d from linux tree

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 3328960d56..9826909a2a 100644
--- a/xen/common/rbtree.c
+++ b/xen/common/rbtree.c
@@ -236,6 +236,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);
@@ -252,15 +262,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: [Resend][PATCH 01/17] rb_tree: reorganize code in rb_erase() for additional changes

[Dario Faggioli]

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

On Thu, 2017-06-01 at 02:50 +0530, Praveen Kumar wrote:
> First, move some code around in order to make the next change more
> obvious.
> 
> commit 16c047add3ceaf0ab882e3e094d1ec904d02312d from linux tree
> 
> Signed-off-by: Praveen Kumar <kpraveen.lkml@gmail.com>
>
Mmm... actually, I am not absolutely sure of what's the formal process
that we follow in this case is, but I think that:
*) it is legally required (or at least preferable) that, at least the 
   Signed-off-by, of the original authors of the patches are reported 
   here;
*) legally required or not, I think it's very useful to have them, and 
   not only the S-o-b, but also the Acks, and all the other tags (like 
   you had in the first posting of this series). You probably should 
   add your own Signed-off-by, at the bottom of the list (this, you 
   didn't do it in first posting of the series)

I appreciate that you probably removed the tags to prevent git-send-
email to use the enclosed email address and spam everyone, but I'm sure
there is a way of telling git-send-email itself, to avoid doing that,
even if you leave the tags and the emails in the patches' changelogs
(something like a command line options, or similar.. I don't use it, so
I can't tell).

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: [Resend][PATCH 01/17] rb_tree: reorganize code in rb_erase() for additional changes

[Andrew Cooper]

On 31/05/2017 23:40, Dario Faggioli wrote:
> On Thu, 2017-06-01 at 02:50 +0530, Praveen Kumar wrote:
>> First, move some code around in order to make the next change more
>> obvious.
>>
>> commit 16c047add3ceaf0ab882e3e094d1ec904d02312d from linux tree
>>
>> Signed-off-by: Praveen Kumar <kpraveen.lkml@gmail.com>
>>
> Mmm... actually, I am not absolutely sure of what's the formal process
> that we follow in this case is, but I think that:
> *) it is legally required (or at least preferable) that, at least the 
>    Signed-off-by, of the original authors of the patches are reported 
>    here;
> *) legally required or not, I think it's very useful to have them, and 
>    not only the S-o-b, but also the Acks, and all the other tags (like 
>    you had in the first posting of this series). You probably should 
>    add your own Signed-off-by, at the bottom of the list (this, you 
>    didn't do it in first posting of the series)
>
> I appreciate that you probably removed the tags to prevent git-send-
> email to use the enclosed email address and spam everyone, but I'm sure
> there is a way of telling git-send-email itself, to avoid doing that,
> even if you leave the tags and the emails in the patches' changelogs
> (something like a command line options, or similar.. I don't use it, so
> I can't tell).

As an example, see

http://xenbits.xen.org/gitweb/?p=xen.git;a=commitdiff;h=b01c2fb5834aea0328db55c310caa34173021d3d

The way I prepare series like this for email is to use `git format-patch
staging --cover-letter` to render the entire series as patch files in
the local directory,  edit each patch to put suitable Cc: lines beside
the From: header, then `git send-email --dry-run *.patch
--suppress-cc=all` to check what it will actually send.  The Cc's in the
header section are included, but no automatic Cc's are generated from
content in the body.

~Andrew

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

Re: [Resend][PATCH 01/17] rb_tree: reorganize code in rb_erase() for additional changes

[Dario Faggioli]

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

On Wed, 2017-05-31 at 23:56 +0100, Andrew Cooper wrote:
> As an example, see
> 
> http://xenbits.xen.org/gitweb/?p=xen.git;a=commitdiff;h=b01c2fb5834ae
> a0328db55c310caa34173021d3d
> 
Nice, I especially like how the changelog looks, i.e.:
 - original Linux patch description description
 - Linux's Signed-off-by, Reviewed-by, Acked-by, etc.
 - ref to Linux commit id
 - a line with "Ported to Xen."
 - author of the port's Signed-off-by
 - (Reviewed-by, Acked-by, etc. coming from xen-devel)

Praveen, I suggest using the same pattern (if you also like it, of
course :-D).

Using patch 1 as an example, that would mean the following:

  Subject: [PATCH 01/17] rb_tree: reorganize code in rb_erase() for additional changes

  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>
  ---

> The way I prepare series like this for email is to use `git format-
> patch
> staging --cover-letter` to render the entire series as patch files in
> the local directory,  edit each patch to put suitable Cc: lines
> beside
> the From: header, then `git send-email --dry-run *.patch
> --suppress-cc=all` to check what it will actually send.  The Cc's in
> the
> header section are included, but no automatic Cc's are generated from
> content in the body.
> 
Cool to know, thanks.

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: [Resend][PATCH 01/17] rb_tree: reorganize code in rb_erase() for additional changes

[Praveen Kumar]

On Thu, 2017-06-01 at 10:01 +0200, Dario Faggioli wrote:
> On Wed, 2017-05-31 at 23:56 +0100, Andrew Cooper wrote:
> > 
> > As an example, see
> > 
> > http://xenbits.xen.org/gitweb/?p=xen.git;a=commitdiff;h=b01c2fb5834
> > ae
> > a0328db55c310caa34173021d3d
> > 
> Nice, I especially like how the changelog looks, i.e.:
>  - original Linux patch description description
>  - Linux's Signed-off-by, Reviewed-by, Acked-by, etc.
>  - ref to Linux commit id
>  - a line with "Ported to Xen."
>  - author of the port's Signed-off-by
>  - (Reviewed-by, Acked-by, etc. coming from xen-devel)
> 
> Praveen, I suggest using the same pattern (if you also like it, of
> course :-D).
> 
Thanks Andrew for sharing the information.

Yes, liked it too. Will incorporate the changes and share updated
patch. Will try to do dry-run as suggested.

> Using patch 1 as an example, that would mean the following:
> 
>   Subject: [PATCH 01/17] rb_tree: reorganize code in rb_erase()
> for additional changes
> 
>   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>
>   ---
> 
> > 
> > The way I prepare series like this for email is to use `git format-
> > patch
> > staging --cover-letter` to render the entire series as patch files
> > in
> > the local directory,  edit each patch to put suitable Cc: lines
> > beside
> > the From: header, then `git send-email --dry-run *.patch
> > --suppress-cc=all` to check what it will actually send.  The Cc's
> > in
> > the
> > header section are included, but no automatic Cc's are generated
> > from
> > content in the body.
> > 
> Cool to know, thanks.
> 
Sure, I too was bit confused by replacing Signed-off-by. As suggested
by Andrew, I will rework on the patches. Thanks again.

Regards,

~Praveen.

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

Re: [Resend][PATCH 01/17] rb_tree: reorganize code in rb_erase() for additional changes

[Jan Beulich]

>>> On 31.05.17 at 23:20, <kpraveen.lkml@gmail.com> wrote:
> First, move some code around in order to make the next change more obvious.
> 
> commit 16c047add3ceaf0ab882e3e094d1ec904d02312d from linux tree
> 
> Signed-off-by: Praveen Kumar <kpraveen.lkml@gmail.com>

You've completely lost all original authorship - this is a no-go. You'll
need to introduce a From: tag and retain at least the S-o-b-s of
people having actively contributed to the change. Considering the
original commit message, that's at least Peter and Andrew. If in
doubt, keep all of them. You'd add yours below the ones you keep.
Also please reproduce the full commit message (i.e. here also
including Andrew's remark in square brackets).

I guess the same will apply to the rest of the series, and since
actually reviewing the content (when it comes from another, pre-
reviewed source) is pretty pointless, I'll drop the entire series for
now, in expectation of a v2.

Jan


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

[Resend][PATCH 02/17] 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.

commit 4c60117811171d867d4f27f17ea07d7419d45dae from linux tree

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 9826909a2a..3df599c3cb 100644
--- a/xen/common/rbtree.c
+++ b/xen/common/rbtree.c
@@ -250,13 +250,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

[Resend][PATCH 03/17] 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.

commit 4b324126e0c6c3a5080ca3ec0981e8766ed6f1ee from linux tree

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 3df599c3cb..0695edd9f9 100644
--- a/xen/common/rbtree.c
+++ b/xen/common/rbtree.c
@@ -256,15 +256,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

[Resend][PATCH 04/17] 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.

commit 4c199a93a2d36b277a9fd209a0f2793f8460a215 from linux tree.

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 0695edd9f9..81fb746b35 100644
--- a/xen/common/rbtree.c
+++ b/xen/common/rbtree.c
@@ -323,7 +323,7 @@ struct rb_node *rb_next(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
@@ -352,7 +352,7 @@ struct rb_node *rb_prev(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 f93c4d5823..29071a7e4a 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: [Resend][PATCH 04/17] rbtree: empty nodes have no color

[Dario Faggioli]

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

On Thu, 2017-06-01 at 02:50 +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.
> 
Mmm... you have significantly cut the changelog. I appreciate that some
of the removed text speaks about a function being removed, which we
don't have in our tree. However:

 - the central part of the changelog, does not speak about 
   rb_init_node() being removed, and so you can keep it;

 - leave a mark in the changelog itself (like a one liner, surrounded
   by '[' ']') about the fact that you alrered the original changelog.

> commit 4c199a93a2d36b277a9fd209a0f2793f8460a215 from linux tree.
> 
> Signed-off-by: Praveen Kumar <kpraveen.lkml@gmail.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

Re: [Resend][PATCH 04/17] rbtree: empty nodes have no color

[Jan Beulich]

>>> On 12.06.17 at 18:42, <dario.faggioli@citrix.com> wrote:
> On Thu, 2017-06-01 at 02:50 +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.
>> 
> Mmm... you have significantly cut the changelog. I appreciate that some
> of the removed text speaks about a function being removed, which we
> don't have in our tree. However:
> 
>  - the central part of the changelog, does not speak about 
>    rb_init_node() being removed, and so you can keep it;
> 
>  - leave a mark in the changelog itself (like a one liner, surrounded
>    by '[' ']') about the fact that you alrered the original changelog.

Even better would imo be to keep the description as is and
add, between the original S-o-b-s (and other tags) and yours,
the changes done to the original commit to fit our tree and
purposes.

Jan


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

[Resend][PATCH 05/17] 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

commit bf7ad8eeab995710c766df49c9c69a8592ca0216 from linux tree

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 81fb746b35..1d48ac7c78 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;
@@ -261,7 +279,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 29071a7e4a..107f1b12f2 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

[Resend][PATCH 06/17] 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.

commit 1f0528653e41ec230c60f5738820e8a544731399 from linux tree

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

diff --git a/xen/common/rbtree.c b/xen/common/rbtree.c
index 1d48ac7c78..bead370436 100644
--- a/xen/common/rbtree.c
+++ b/xen/common/rbtree.c
@@ -110,11 +110,8 @@ 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);
@@ -135,11 +132,8 @@ 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);
-- 
2.12.0


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

Re: [Resend][PATCH 06/17] rbtree: break out of rb_insert_color loop after tree rotation

[Dario Faggioli]

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

On Thu, 2017-06-01 at 02:50 +0530, Praveen Kumar wrote:
> --- a/xen/common/rbtree.c
> +++ b/xen/common/rbtree.c
> @@ -110,11 +110,8 @@ 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);
> @@ -135,11 +132,8 @@ 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);
>
It looks to me like something went wrong while you applied/prepared the
patch.

In fact, I can see the removed lines are the same, between the patch
itself and the original Linux comment, but you are not adding any code
(while the original Linux commit does!)

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

[Resend][PATCH 07/17] 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.

commit 6d58452dc066db61acdff7b84671db1b11a3de1c from linux tree

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 bead370436..ccf905e35c 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)
@@ -141,8 +156,6 @@ void rb_insert_color(struct rb_node *node, struct rb_root *root)
             __rb_rotate_left(gparent, root);
         }
     }
-
-    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

[Resend][PATCH 08/17] 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.

commit 5bc9188aa207dafd47eab57df7c4fe5b3d3f636a from linux tree

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

diff --git a/xen/common/rbtree.c b/xen/common/rbtree.c
index ccf905e35c..8db7a5b4ca 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,61 +150,108 @@ 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

[Resend][PATCH 09/17] 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.

commit d6ff1273928ebf15466a85b7e1810cd00e72998b from linux tree

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 8db7a5b4ca..736e2a55aa 100644
--- a/xen/common/rbtree.c
+++ b/xen/common/rbtree.c
@@ -262,10 +262,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))
             {
@@ -297,7 +311,6 @@ static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,
                 if (other->rb_right)
                     rb_set_black(other->rb_right);
                 __rb_rotate_left(parent, root);
-                node = root->rb_node;
                 break;
             }
         }
@@ -334,13 +347,10 @@ static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,
                 if (other->rb_left)
                     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

[Resend][PATCH 10/17] 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.

commit e125d1471a4f8f1bf7ea9a83deb8d23cb40bd712 from linux tree

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

diff --git a/xen/common/rbtree.c b/xen/common/rbtree.c
index 736e2a55aa..1e4cb1ed2c 100644
--- a/xen/common/rbtree.c
+++ b/xen/common/rbtree.c
@@ -288,31 +288,26 @@ 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))
                 {
-                    struct rb_node *o_left;
-                    if ((o_left = other->rb_left))
-                        rb_set_black(o_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);
-                if (other->rb_right)
-                    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
         {
@@ -324,31 +319,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))
                 {
-                    register struct rb_node *o_right;
-                    if ((o_right = other->rb_right))
-                        rb_set_black(o_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);
-                if (other->rb_left)
-                    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

[Resend][PATCH 11/17] 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.

commit 6280d2356fd8ad0936a63c10dc1e6accf48d0c61 from linux tree

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

diff --git a/xen/common/rbtree.c b/xen/common/rbtree.c
index 1e4cb1ed2c..253861d889 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
@@ -260,7 +209,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)
     {
@@ -275,68 +224,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))
-            {
-                rb_set_black(other);
-                rb_set_red(parent);
-                __rb_rotate_left(parent, root);
-                other = parent->rb_right;
+            sibling = parent->rb_right;
+            if (rb_is_red(sibling)) {
+                /*
+                 * Case 1 - left rotate at parent
+                 *
+                 *     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

[Resend][PATCH 12/17] 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.

commit 59633abf34e2f44b8e772a2c12a92132aa7c2220 from Linux tree

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

diff --git a/xen/common/rbtree.c b/xen/common/rbtree.c
index 253861d889..b65f00ca1f 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);
@@ -183,7 +184,8 @@ void rb_insert_color(struct rb_node *node, struct rb_root *root)
                 continue;
             }
 
-            if (parent->rb_left == node)
+            tmp = parent->rb_left;
+            if (node == tmp)
             {
                 /* Case 2 - right rotate at parent */
                 parent->rb_left = tmp = node->rb_right;
@@ -192,10 +194,11 @@ void rb_insert_color(struct rb_node *node, struct rb_root *root)
                     rb_set_parent_color(tmp, parent, RB_BLACK);
                 rb_set_parent_color(parent, node, RB_RED);
                 parent = node;
+                tmp = node->rb_left;
             }
 
             /* Case 3 - left rotate at gparent */
-            gparent->rb_right = tmp = parent->rb_left;
+            gparent->rb_right = tmp;    /* == parent->rb_left */
             parent->rb_left = gparent;
             if (tmp)
                 rb_set_parent_color(tmp, gparent, RB_BLACK);
@@ -228,8 +231,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)) {
                 /*
                  * Case 1 - left rotate at parent
-- 
2.12.0


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

[Resend][PATCH 13/17] 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.

commit 7abc704ae399fcb9c51ca200b0456f8a975a8011 from Linux tree

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

diff --git a/xen/common/rbtree.c b/xen/common/rbtree.c
index b65f00ca1f..3b54c04bea 100644
--- a/xen/common/rbtree.c
+++ b/xen/common/rbtree.c
@@ -65,6 +65,22 @@ 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)
+{
+    if (parent)
+    {
+        if (parent->rb_left == old)
+            parent->rb_left = new;
+        else
+            parent->rb_right = new;
+    } else
+        root->rb_node = new;
+}
+
+
+
 /*
  * Helper function for rotations:
  * - old's parent and color get assigned to new
@@ -77,13 +93,7 @@ __rb_rotate_set_parents(struct rb_node *old, struct rb_node *new,
     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;
+    __rb_change_child(old, new, parent, root);
 }
 
 void rb_insert_color(struct rb_node *node, struct rb_root *root)
@@ -381,14 +391,7 @@ void rb_erase(struct rb_node *node, struct rb_root *root)
         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);
@@ -418,15 +421,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;
+
+    __rb_change_child(node, child, parent, root);
 
  color:
     if (color == RB_BLACK)
@@ -523,14 +519,8 @@ 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

Re: [Resend][PATCH 13/17] rbtree: add __rb_change_child() helper function

[Dario Faggioli]

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

On Thu, 2017-06-01 at 02:50 +0530, Praveen Kumar wrote:
> @@ -65,6 +65,22 @@ 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)
> +{
> +    if (parent)
> +    {
> +        if (parent->rb_left == old)
> +            parent->rb_left = new;
> +        else
> +            parent->rb_right = new;
> +    } else
> +        root->rb_node = new;
> +}
> +
> +
> +
>
why all these blank lines? They're not there in the original Linux
commit, AFAICT.

>  /*
>   * Helper function for rotations:
>   * - old's parent and color get assigned to ne
> 
> @@ -418,15 +421,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;
> +
>
Same for this one here.

> +    __rb_change_child(node, child, parent, root);
>  
>   color:
>      if (color == RB_BLACK)
> @@ -523,14 +519,8 @@ 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);
> +
>
And here too.

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

[Resend][PATCH 14/17] 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.

commit 60670b8034d6e2ba860af79c9379b7788d09db73 from Linux tree

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

diff --git a/xen/common/rbtree.c b/xen/common/rbtree.c
index 3b54c04bea..69c7496c65 100644
--- a/xen/common/rbtree.c
+++ b/xen/common/rbtree.c
@@ -376,18 +376,29 @@ 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;
 
@@ -412,19 +423,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

Re: [Resend][PATCH 14/17] rbtree: place easiest case first in rb_erase()

[Dario Faggioli]

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

On Thu, 2017-06-01 at 02:50 +0530, Praveen Kumar wrote:
> --- a/xen/common/rbtree.c
> +++ b/xen/common/rbtree.c
> @@ -376,18 +376,29 @@ 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)
>      {
>
In the original Linux commit, this is:

 if (!tmp) {

I know that putting the '{' on new line is more Xen-ish, but since the
file is going to end up in a mixed style anyway, I think it's better to
import the commit as is (as much as possible) rather than make this
micro-adjustment (which, in future, may make importing new Linux
commits difficult).

> +    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;
>  
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

[Resend][PATCH 15/17] 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.

commit 46b6135a7402ac23c5b25f2bd79b03bab8f98278 from Linux tree

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 69c7496c65..6e37e960ab 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,12 @@
 #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;
@@ -219,29 +226,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 */
         {
@@ -277,17 +274,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
@@ -349,9 +351,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;
@@ -377,24 +386,33 @@ 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;
 
@@ -406,27 +424,31 @@ void rb_erase(struct rb_node *node, struct rb_root *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

[Resend][PATCH 16/17] 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.

commit 4f035ad67f4633c233cb3642711d49b4efc9c82d from Linux tree

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

diff --git a/xen/common/rbtree.c b/xen/common/rbtree.c
index 6e37e960ab..83b4892f54 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)
 {
@@ -387,6 +392,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)
     {
@@ -398,53 +404,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

[Resend][PATCH 17/17] rbtree: add postorder iteration functions

[Praveen Kumar]

Postorder iteration yields all of a node's children prior to yielding the
node itself, and this particular implementation also avoids examining the
leaf links in a node after that node has been yielded.

In what I expect will be its most common usage, postorder iteration allows
the deletion of every node in an rbtree without modifying the rbtree nodes
(no _requirement_ that they be nulled) while avoiding referencing child
nodes after they have been "deleted" (most commonly, freed).

I have only updated zswap to use this functionality at this point, but
numerous bits of code (most notably in the filesystem drivers) use a hand
rolled postorder iteration that NULLs child links as it traverses the
tree.  Each of those instances could be replaced with this common
implementation.

1 & 2 add rbtree postorder iteration functions.
3 adds testing of the iteration to the rbtree runtime tests
4 allows building the rbtree runtime tests as builtins
5 updates zswap.

This patch:

Add postorder iteration functions for rbtree.  These are useful for safely
freeing an entire rbtree without modifying the tree at all.

commit 9dee5c51516d2c3fff22633c1272c5652e68075a from Linux tree

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

diff --git a/xen/common/rbtree.c b/xen/common/rbtree.c
index 83b4892f54..3c994dcc0c 100644
--- a/xen/common/rbtree.c
+++ b/xen/common/rbtree.c
@@ -584,3 +584,48 @@ void rb_replace_node(struct rb_node *victim, struct rb_node *new,
     *new = *victim;
 }
 EXPORT_SYMBOL(rb_replace_node);
+
+static struct rb_node *rb_left_deepest_node(const struct rb_node *node)
+{
+    for (;;)
+    { 
+        if (node->rb_left)
+            node = node->rb_left;
+        else if (node->rb_right)
+            node = node->rb_right;
+        else
+            return (struct rb_node *)node;
+    }
+}
+
+struct rb_node *rb_next_postorder(const struct rb_node *node)
+{
+    const struct rb_node *parent;
+    if (!node)
+        return NULL;
+    parent = rb_parent(node);
+
+    /* If we're sitting on node, we've already seen our children */
+    if (parent && node == parent->rb_left && parent->rb_right)
+    {
+        /* If we are the parent's left node, go to the parent's right
+         * node then all the way down to the left
+         */
+        return rb_left_deepest_node(parent->rb_right);
+    } else
+        /* Otherwise we are the parent's right node, and the parent
+         * should be next
+         */
+        return (struct rb_node *)parent;
+}
+EXPORT_SYMBOL(rb_next_postorder);
+
+struct rb_node *rb_first_postorder(const struct rb_root *root)
+{
+    if (!root->rb_node)
+        return NULL;
+
+    return rb_left_deepest_node(root->rb_node);
+}
+EXPORT_SYMBOL(rb_first_postorder);
+
diff --git a/xen/include/xen/rbtree.h b/xen/include/xen/rbtree.h
index 107f1b12f2..24650a5cd8 100644
--- a/xen/include/xen/rbtree.h
+++ b/xen/include/xen/rbtree.h
@@ -66,4 +66,8 @@ static inline void rb_link_node(struct rb_node * node, struct rb_node * parent,
     *rb_link = node;
 }
 
+/* Postorder iteration - always visit the parent after its children */
+extern struct rb_node *rb_first_postorder(const struct rb_root *);
+extern struct rb_node *rb_next_postorder(const struct rb_node *);
+
 #endif /* __RBTREE_H__ */
-- 
2.12.0


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

Re: [Xen-devel[PATCH Resend v2] xen: common: rbtree: ported updates from linux tree

[Dario Faggioli]

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

On Thu, 2017-06-01 at 02:50 +0530, Praveen Kumar wrote:
> Hi All,
> 
Hi,

> The patch imports the changes and updates of the rbtree
> implementaiton
> from Linux tree. 
>
Thanks Praveen for doing this.

This series is much better than the previous single and giant patch.
:-)

> 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.
>
That is fine, I think, for now. We'll test this properly when you'll
have the "usage in Credit2" part.
> 
> I have not imported augmented and rcu rbtree functionality to the xen
> tree,
> as there was no specific requirement for current planned
> implementation.
> 
That's something I agree with, and you did the right thing saying it
here in the cover letter. Another thing I would like to know, though,
is whether there are other commits that, for one reason or another, you
either decided to skip, or could not port, or if this series bring us
basically on par with Linux's rb-trees.

> From Praveen Kumar <kpraveen.lkml@gmail.com> # This line is ignored.
> From: Praveen Kumar <kpraveen.lkml@gmail.com>
> Subject: 
> In-Reply-To: 
> 
This are a bit strange lines. No big deal, just saying.

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: [Xen-devel[PATCH Resend v2] xen: common: rbtree: ported updates from linux tree

[Jan Beulich]

>>> On 31.05.17 at 23:20, <kpraveen.lkml@gmail.com> wrote:
> 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 and rcu rbtree functionality to the xen tree,
> as there was no specific requirement for current planned implementation.
> 
> Please share your inputs. Thanks in advance.

Bug fixes and improvements to existing code are clearly welcome
and need no further rationale provided here. Having looked only
over the titles so far I see two patches which look to add new
functionality (13 and 17). As I hope you've left the original patch
descriptions intact, a reason for why we want/need these should
likely be provided here.

Jan


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

Re: [Xen-devel[PATCH Resend v2] xen: common: rbtree: ported updates from linux tree

[Dario Faggioli]

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

On Thu, 2017-06-01 at 01:26 -0600, Jan Beulich wrote:
> > > > On 31.05.17 at 23:20, <kpraveen.lkml@gmail.com> wrote:
> > I have not imported augmented and rcu rbtree functionality to the
> > xen tree,
> > as there was no specific requirement for current planned
> > implementation.
> > 
> Bug fixes and improvements to existing code are clearly welcome
> and need no further rationale provided here. Having looked only
> over the titles so far I see two patches which look to add new
> functionality (13 and 17). 
>
I also have only quickly skimmed through the series for now.

Indeed 17 adds stuff which I suspect we may not need, and in any case,
I don't think it belongs in this series.

If you really need those iterators when actually using rb-tree, you'll
add the patch at that time.

13, despite its own (poor, I agree) subject line, is actually doing
some decent refactoring of the code, so I'd keep it:
<<Add __rb_change_child() as an inline helper function to replace code 
that would otherwise be duplicated 4 times in the source.>>

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: [Xen-devel[PATCH Resend v2] xen: common: rbtree: ported updates from linux tree

[Praveen Kumar]

On Thu, 2017-06-01 at 09:43 +0200, Dario Faggioli wrote:
> On Thu, 2017-06-01 at 01:26 -0600, Jan Beulich wrote:
> > 
> > > 
> > > > 
> > > > > 
> > > > > On 31.05.17 at 23:20, <kpraveen.lkml@gmail.com> wrote:
> > > I have not imported augmented and rcu rbtree functionality to the
> > > xen tree,
> > > as there was no specific requirement for current planned
> > > implementation.
> > > 
> > Bug fixes and improvements to existing code are clearly welcome
> > and need no further rationale provided here. Having looked only
> > over the titles so far I see two patches which look to add new
> > functionality (13 and 17). 
> > 
> I also have only quickly skimmed through the series for now.
> 
> Indeed 17 adds stuff which I suspect we may not need, and in any
> case,
> I don't think it belongs in this series.
> 
> If you really need those iterators when actually using rb-tree,
> you'll
> add the patch at that time.
> 
> 13, despite its own (poor, I agree) subject line, is actually doing
> some decent refactoring of the code, so I'd keep it:
> <<Add __rb_change_child() as an inline helper function to replace
> code 
> that would otherwise be duplicated 4 times in the source.>>
> 

Dario,

For the commits not ported from Linux tree, I will share the
information in updated patch ( in similar way what I did by adding a
cover letter ).

Also, as suggested Will remove the patch 17 for now, and validate
others too.

Thanks once again for providing your comment.

Regards,

~Praveen.

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

Re: [Xen-devel[PATCH Resend v2] xen: common: rbtree: ported updates from linux tree

[Praveen Kumar]

On Thu, 2017-06-01 at 01:26 -0600, Jan Beulich wrote:
> > 
> > > 
> > > > 
> > > > On 31.05.17 at 23:20, <kpraveen.lkml@gmail.com> wrote:
> > 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 and rcu rbtree functionality to the
> > xen tree,
> > as there was no specific requirement for current planned
> > implementation.
> > 
> > Please share your inputs. Thanks in advance.
> 
> Bug fixes and improvements to existing code are clearly welcome
> and need no further rationale provided here. Having looked only
> over the titles so far I see two patches which look to add new
> functionality (13 and 17). As I hope you've left the original patch
> descriptions intact, a reason for why we want/need these should
> likely be provided here.
> 

Sure Jan, I will take care of the same in my updated patch. Thanks for
your comment.
> 

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

Re: [Xen-devel[PATCH Resend v2] xen: common: rbtree: ported updates from linux tree

[Dario Faggioli]

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

On Thu, 2017-06-01 at 02:50 +0530, Praveen Kumar wrote:
> I have not imported augmented and rcu rbtree functionality to the xen
> tree,
> as there was no specific requirement for current planned
> implementation.
> 
> Please share your inputs. Thanks in advance.
> 
So, I'm having another look at this series.

Apart from the already mentioned authorship suppression problem, and
apart from the comments I've made on the single patches of the series,
I think the following (Linux) commits should also be considered (or a
reason for not doing that, being stated in the cover letter):

 f4b477c47332367d35686bd2b808c2156b96d7c7 rbtree: add const qualifier to some functions
 55a63998b8967615a15e2211ba0ff3a84a565824 lib/rbtree.c: optimize rb_erase()
 7ce6ff9e5de99e7b72019c7de82fb438fe1dc5a0 rbtree: coding style adjustments [*]
 1b9c53e849aa65776d4f611d99aa09f856518dad lib/rbtree.c: fix typo in comment of __rb_insert()
 ce093a04543c403d52c1a5788d8cb92e47453aba lib/rbtree.c: fix typo in comment of ____rb_erase_color [**]

[*] Either all, or just some honks of it. At least, the changes to the
style of the comments are valuable, as they make them consistent with
our style too. The others, I'm not sure, but I'd be tempted to say
let's take it all, to make backport of other patches easier...

[**] not sure about this, maybe you can give it a try, and see if it
applies, or can be adapted easily (if the typo is actually present, of
course).

d72da4a4d973d8a0a0d3c97e7cdebf287fbe3a99 ("rbtree: Make lockless
searches non-fatal") looks interesting, but I think we can leave it out
for now. But, please, mention it (and the fact you're not porting it
because we think we don't need it) in the cover letter.

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