faster augmented rbtree interface
Subsystems (5)
v2 cover faster augmented rbtree interface
These are my proposed changes for a faster augmented rbtree interface. They are implemented on top of a previous patch series that is already in Andrew's -mm tree, and I feel they are ready to join it.
Patch 1 is a trivial fix for a sparse warning.
Patch 2 is a small optimization I already sent as part of my previous RFC. Rik had ACKed it.
Patches 3-4 are small cleanups, mainly intended to make the code more readable.
Patches 5-6 are new, based on something George Spelvin observed in my previous RFC. It turns out that in rb_erase(), recoloring is trivial for nodes that have exactly 1 child. We can shave a few cycles by handling it locally, and changing rb_erase_color() to only deal with the no-childs case.
Patch 7 adds a performance test for the augmented rbtree support.
Patch 8 introduces my proposed API for augmented rbtree support. rb_insert_augmented() and rb_erase_augmented() are augmented versions of rb_insert_color() and rb_erase(). They take an additional argument (struct rb_augment_callbacks) to specify callbacks to be used to maintain the augmented rbtree information. users have to specify 3 callbacks through that structure. Non-augmented rbtree support is provided by inlining dummy callbacks, so that the non-augmented case is not affected (either in speed or in compiled size) by the new augmented rbtree API. For augmented rbtree users, no inlining takes place at this point (I may propose this later, but feel this shouldn't go with the initial proposal).
Patch 9 removes the old augmented rbtree interface and converts its only user to the new interface.
Overall, this series improves non-augmented rbtree speed by ~5%. For augmented rbtree users, the new interface is ~2.5 times faster than the old.
Michel Lespinasse (9):
rbtree test: fix sparse warning about 64-bit constant
rbtree: optimize fetching of sibling node
rbtree: add __rb_change_child() helper function
rbtree: place easiest case first in rb_erase()
rbtree: handle 1-child recoloring in rb_erase() instead of
rb_erase_color()
rbtree: low level optimizations in rb_erase()
rbtree: augmented rbtree test
rbtree: faster augmented rbtree manipulation
rbtree: remove prior augmented rbtree implementation
Documentation/rbtree.txt | 190 ++++++++++++++++++++---- arch/x86/mm/pat_rbtree.c | 65 ++++++--- include/linux/rbtree.h | 23 ++- lib/rbtree.c | 370 +++++++++++++++++++++++++--------------------- lib/rbtree_test.c | 135 ++++++++++++++++- 5 files changed, 557 insertions(+), 226 deletions(-)
Signature · 7 lines
1.7.7.3 -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
PATCH v2 1/9 rbtree test: fix sparse warning about 64-bit constant
Just a small fix to make sparse happy.
--- lib/rbtree_test.c | 2 +- 1 files changed, 1 insertions(+), 1 deletions(-)
lib/rbtree_test.c +1 -1
@@ -88,7 +88,7 @@ static int rbtree_test_init(void)printk (KERN_ALERT "rbtree testing" ); -prandom32_seed (&rnd,3141592653589793238 ); +prandom32_seed (&rnd,3141592653589793238ULL );init (); time1 =get_cycles ();
Signature · 7 lines
1.7.7.3 -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
Re: [PATCH v2 1/9] rbtree test: fix sparse warning about 64-bit constant
Quoted 4 lines · Michel Lespinasse
Just a small fix to make sparse happy.
Signed-off-by Michel Lespinasse<[email protected]>Reported-by Fengguang Wu<[email protected]>
Signature · 7 lines
All rights reversed -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
PATCH v2 2/9 rbtree: optimize fetching of sibling node
In reply to Michel LespinasseWhen 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.
--- lib/rbtree.c | 21 +++++++++++++-------- 1 files changed, 13 insertions(+), 8 deletions(-)
lib/rbtree.c +13 -8
@@ -107,8 +107,8 @@ 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; + tmp = gparent->rb_right; +if (parent != tmp) {/* parent == gparent->rb_left */ if (tmp &&rb_is_red (tmp)) {/* * Case 1 - color flips
@@ -131,7 +131,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 *
@@ -151,6 +152,7 @@ void rb_insert_color(struct rb_node *node, struct rb_root *root) RB_BLACK);rb_set_parent_color (parent, node,RB_RED ); parent = node; + tmp = node->rb_right; }/*
@@ -162,7 +164,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 );
@@ -180,7 +182,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; node->rb_right = parent;
@@ -189,10 +192,11 @@ void rb_insert_color(struct rb_node *node, struct rb_root *root) 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 );
@@ -223,8 +227,9 @@ 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
Signature · 7 lines
1.7.7.3 -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
Re: [PATCH v2 2/9] rbtree: optimize fetching of sibling node
Quoted 8 lines · Michel Lespinasse
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 childThis can be replaced with:
- fetch the parent's right child as an assumed sibling
- check that node is NOT the fetched child
Quoted 5 lines
This avoids fetching the parent's left child when node is actually that child. Saves a bit on code size, though it doesn't seem to make a large difference in speed.
Signed-off-by Michel Lespinasse<[email protected]>
Signature · 7 lines
All rights reversed -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
Peter Zijlstra
maintainerRe: [PATCH v2 2/9] rbtree: optimize fetching of sibling node
In reply to Michel LespinasseReview
Quoted 11 lines · Michel Lespinasse
(quoted diff) +8
-0+ tmp = gparent->rb_right; + if (parent != tmp) { /* parent == gparent->rb_left */ + tmp = parent->rb_right; + if (node == tmp) { + tmp = parent->rb_left; + if (node == tmp) { + sibling = parent->rb_right; + if (node != sibling) { /* node == parent->rb_left */
Half of them got a comment, the other half didn't.. is there any particular reason for that?
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
Re: [PATCH v2 2/9] rbtree: optimize fetching of sibling node
Quoted 8 lines · Peter Zijlstra
Quoted 5 lines · Michel Lespinasse
lib/rbtree.c +4
-0+ tmp = gparent->rb_right; +if (parent != tmp) {/* parent == gparent->rb_left */ + tmp = parent->rb_right; +if (node == tmp) {
Quoted 8 lines
Review
Quoted 5 lines
(quoted diff) +4
-0+ tmp = parent->rb_left; + if (node == tmp) { + sibling = parent->rb_right; + if (node != sibling) { /* node == parent->rb_left */Half of them got a comment, the other half didn't.. is there any particular reason for that?
I felt that the equality tests didn't need explanation. But the tests where I test for inequality with the supposed sibling didn't seem quite so obvious to me, so I commented them.
Signature · 8 lines
Michel "Walken" Lespinasse A program is never fully debugged until the last user dies. -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
PATCH v2 3/9 rbtree: add __rb_change_child() helper function
In reply to Michel LespinasseAdd __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.
--- lib/rbtree.c | 46 +++++++++++++++++----------------------------- 1 files changed, 17 insertions(+), 29 deletions(-)
lib/rbtree.c +17 -29
@@ -66,6 +66,19 @@ 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
@@ -78,13 +91,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)
@@ -375,13 +382,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);
@@ -410,13 +411,7 @@ 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 )
@@ -591,14 +586,7 @@ void rb_replace_node(struct rb_node *victim, struct rb_node *new,struct rb_node *parent =rb_parent (victim);/* Set the surrounding nodes to point to the replacement */ -if (parent) { -if (victim == parent->rb_left) - parent->rb_left = new; -else - parent->rb_right = new; - }else { - root->rb_node = new; - } +__rb_change_child (victim, new, parent, root);if (victim->rb_left)rb_set_parent (victim->rb_left, new);if (victim->rb_right)
Signature · 7 lines
1.7.7.3 -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
Re: [PATCH v2 3/9] rbtree: add __rb_change_child() helper function
Quoted 6 lines · Michel Lespinasse
Add
__rb_change_child()as an inline helper function to replace code that would otherwise be duplicated 4 times in the source.No changes to binary size or speed.
Signed-off-by Michel Lespinasse<[email protected]>
Signature · 7 lines
All rights reversed -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
Peter Zijlstra
maintainerRe: [PATCH v2 3/9] rbtree: add __rb_change_child() helper function
In reply to Michel LespinasseQuoted 1 line · Michel Lespinasse
+static inline void
I would make that __always_inline, just to make sure GCC doesn't go creative on us.
lib/rbtree.c static inline struct rb_node *rb_red_parent(struct rb_node *red) · line 80
Quoted 11 lines
lib/rbtree.c +11
-0+__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; +}
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
Re: [PATCH v2 3/9] rbtree: add __rb_change_child() helper function
Quoted 5 lines · Peter Zijlstra
Quoted 1 line · Michel Lespinasse
+static inline void
I would make that
__always_inline, just to make sure GCC doesn't go creative on us.
How strongly do you care ? I'm not sure it makes sense to change it unless we also change every other inline function in that file. I'd rather not do that until we hear of gcc actually breaking things.
(BTW, did you know that sometimes gcc generates different code when you change from inline to always_inline, even though things were already inlined before ? I really hate dealing with gcc crap like that, makes me want to forget about inline functions and just do it all with preprocessor abuse...)
Signature · 8 lines
Michel "Walken" Lespinasse A program is never fully debugged until the last user dies. -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
PATCH v2 4/9 rbtree: place easiest case first in rb_erase()
In reply to Michel LespinasseIn rb_erase, move the easy case (node to erase has no more than 1 child) first. I feel the code reads easier that way.
--- lib/rbtree.c | 35 ++++++++++++++++++----------------- 1 files changed, 18 insertions(+), 17 deletions(-)
lib/rbtree.c +18 -17
@@ -368,17 +368,28 @@ static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,void rb_erase (struct rb_node *node,struct rb_root *root) { -struct rb_node *child, *parent; +struct rb_node *child = node->rb_right, *tmp = node->rb_left; +struct rb_node *parent;int color; -if (!node->rb_left) - child = node->rb_right; -else if (!node->rb_right) - child = node->rb_left; -else { +if (!tmp) { + case1: +/* Case 1: node to erase has no more than 1 child (easy!) */ + + parent =rb_parent (node); + color =rb_color (node); + +if (child) +rb_set_parent (child, parent); +__rb_change_child (node, child, parent, root); + }else if (!child) { +/* Still case 1, but this time the child is node->rb_left */ + child = tmp; + goto case1; + }else {struct rb_node *old = node, *left; - node = node->rb_right; + node = child;while ((left = node->rb_left) !=NULL ) node = left;
@@ -402,18 +413,8 @@ void rb_erase(struct rb_node *node, struct rb_root *root) node->__rb_parent_color = old->__rb_parent_color; 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); }
Signature · 7 lines
1.7.7.3 -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
Re: [PATCH v2 4/9] rbtree: place easiest case first in rb_erase()
Quoted 4 lines · Michel Lespinasse
In
rb_erase, move the easy case (node to erase has no more than 1 child) first. I feel the code reads easier that way.Signed-off-by Michel Lespinasse<[email protected]>
Signature · 7 lines
All rights reversed -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
PATCH v2 5/9 rbtree: handle 1-child recoloring in rb_erase() instead of rb_erase_color()
In reply to Michel LespinasseAn 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.
--- lib/rbtree.c | 105 ++++++++++++++++++++++++++++++++++------------------------ 1 files changed, 62 insertions(+), 43 deletions(-)
lib/rbtree.c +62 -43
@@ -2,7 +2,8 @@ Red Black Trees (C) 1999 Andrea Arcangeli <[email protected]> (C) 2002 David Woodhouse <[email protected]> - + (C) 2012 Michel Lespinasse <[email protected]> + 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 the Free Software Foundation; either version 2 of the License, or
@@ -50,6 +51,11 @@#define rb_is_red (r) (!rb_color(r))#define rb_is_black (r) rb_color(r) +static inline void rb_set_black (struct rb_node *rb) +{ + rb->__rb_parent_color |=RB_BLACK ; +} +static inline void rb_set_parent (struct rb_node *rb,struct rb_node *p) { rb->__rb_parent_color =rb_color (rb) | (unsigned long )p;
@@ -214,27 +220,18 @@ 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 */ if (rb_is_red (sibling)) {
@@ -268,17 +265,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
@@ -339,9 +341,15 @@ 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;
@@ -369,23 +377,31 @@ static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,void rb_erase (struct rb_node *node,struct rb_root *root) {struct rb_node *child = node->rb_right, *tmp = node->rb_left; -struct rb_node *parent; -int color; +struct rb_node *parent, *rebalance;if (!tmp) { - case1: -/* Case 1: node to erase has no more than 1 child (easy!) */ +/* +* Case 1: node to erase has no more than 1 child (easy!) +* +* Note that if there is one child it must be red due to 5) +* and node must be black due to 4). We adjust colors locally +* so as to bypass __rb_erase_color() later on. +*/ parent =rb_parent (node); - color =rb_color (node); - -if (child) -rb_set_parent (child, parent);__rb_change_child (node, child, parent, root); +if (child) { +rb_set_parent_color (child, parent,RB_BLACK ); + rebalance =NULL ; + }else { + rebalance =rb_is_black (node) ? parent :NULL ; + } }else if (!child) {/* Still case 1, but this time the child is node->rb_left */ - child = tmp; - goto case1; + parent =rb_parent (node); +__rb_change_child (node, tmp, parent, root); +rb_set_parent_color (tmp, parent,RB_BLACK ); + rebalance =NULL ; }else {struct rb_node *old = node, *left;
@@ -397,26 +413,29 @@ 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);
Signature · 7 lines
1.7.7.3 -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
Re: [PATCH v2 5/9] rbtree: handle 1-child recoloring in rb_erase() instead of rb_erase_color()
Quoted 8 lines · Michel Lespinasse
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 inrb_erase().__rb_erase_color()then only needs to handle the no-childs case and can be modified accordingly.Signed-off-by Michel Lespinasse<[email protected]>
Signature · 7 lines
All rights reversed -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
PATCH v2 6/9 rbtree: low level optimizations in rb_erase()
In reply to Michel LespinasseVarious 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.
--- lib/rbtree.c | 97 +++++++++++++++++++++++++++++++++++++-------------------- 1 files changed, 63 insertions(+), 34 deletions(-)
lib/rbtree.c +63 -34
@@ -47,9 +47,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) {
@@ -378,6 +383,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) {/*
@@ -387,51 +393,74 @@ void rb_erase(struct rb_node *node, struct rb_root *root)* 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); + 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 its +* 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)
Signature · 7 lines
1.7.7.3 -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
Re: [PATCH v2 6/9] rbtree: low level optimizations in rb_erase()
Quoted 15 lines · Michel Lespinasse
Various minor optimizations in
rb_erase():
- Avoid multiple loading ofnode->__rb_parent_colorwhen 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_colorfield 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.
Quoted 3 lines
Also, added some comments to illustrate cases 2 and 3.
Signed-off-by Michel Lespinasse<[email protected]>
Signature · 7 lines
All rights reversed -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
Peter Zijlstra
maintainerRe: [PATCH v2 6/9] rbtree: low level optimizations in rb_erase()
In reply to Michel Lespinasselib/rbtree.c void rb_erase(struct rb_node *node, struct rb_root *root)
Quoted 7 lines · Michel Lespinasse
lib/rbtree.c +4
-0+/* +* Case 2: node's successor is its right child +/* Case 3: node's successor is leftmost under its +* right child subtree
Hmm?
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
Re: [PATCH v2 6/9] rbtree: low level optimizations in rb_erase()
Quoted 5 lines · Peter Zijlstra
lib/rbtree.c void rb_erase(struct rb_node *node, struct rb_root *root) · line 427
Quoted 2 lines · Michel Lespinasse
lib/rbtree.c +2
-0+/* Case 3: node's successor is leftmost under its +* right child subtree Hmm?
Would 'leftmost under node's right child subtree' make more sense ?
Signature · 8 lines
Michel "Walken" Lespinasse A program is never fully debugged until the last user dies. -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
Peter Zijlstra
maintainerRe: [PATCH v2 6/9] rbtree: low level optimizations in rb_erase()
Quoted 8 lines · Michel Lespinasse
Quoted 5 lines · Peter Zijlstra
lib/rbtree.c void rb_erase(struct rb_node *node, struct rb_root *root) · line 427
Quoted 2 lines · Michel Lespinasse
lib/rbtree.c +2
-0+/* Case 3: node's successor is leftmost under its +* right child subtree Hmm?
Would 'leftmost under node's right child subtree' make more sense ?
Nah, its the comment style discrepancy..
/*
* Case 3: ....
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
Re: [PATCH v2 6/9] rbtree: low level optimizations in rb_erase()
Quoted 6 lines · Peter Zijlstra
Quoted 5 lines · Michel Lespinasse
Quoted 4 lines · Peter Zijlstra
Quoted 2 lines · Michel Lespinasse
lib/rbtree.c +2
-0+/* Case 3: node's successor is leftmost under its +* right child subtree
Quoted 8 lines
Quoted 3 lines
Quoted 1 line
Hmm?
Would 'leftmost under node's right child subtree' make more sense ?
Nah, its the comment style discrepancy..
/*
* Case 3: ....
Gah, failed to notice that. Sending new patch (just the comment changed) as a reply.
Signature · 8 lines
Michel "Walken" Lespinasse A program is never fully debugged until the last user dies. -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
Re: [PATCH v2 6/9] rbtree: low level optimizations in rb_erase()
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.
--- lib/rbtree.c | 98 ++++++++++++++++++++++++++++++++++++++-------------------- 1 files changed, 64 insertions(+), 34 deletions(-)
lib/rbtree.c +64 -34
@@ -47,9 +47,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) {
@@ -378,6 +383,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) {/*
@@ -387,51 +393,75 @@ void rb_erase(struct rb_node *node, struct rb_root *root)* 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); + 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)
Signature · 7 lines
1.7.7.3 -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
PATCH v2 7/9 rbtree: augmented rbtree test
In reply to Michel LespinasseSmall test to measure the performance of augmented rbtrees.
--- lib/rbtree_test.c | 103 +++++++++++++++++++++++++++++++++++++++++++++++++++- 1 files changed, 101 insertions(+), 2 deletions(-)
lib/rbtree_test.c +101 -2
@@ -10,6 +10,10 @@struct test_node {struct rb_node rb;u32 key; + +/* following fields used for testing augmented rbtree functionality */ +u32 val; +u32 augmented; };static struct rb_root root =RB_ROOT ;
@@ -20,10 +24,11 @@ static struct rnd_state rnd;static void insert (struct test_node *node,struct rb_root *root) {struct rb_node **new = &root->rb_node, *parent =NULL ; +u32 key = node->key;while (*new) { parent = *new; - if (node->key < rb_entry(parent, struct test_node, rb)->key) + if (key < rb_entry(parent, struct test_node, rb)->key) new = &parent->rb_left;else new = &parent->rb_right;
@@ -38,11 +43,62 @@ static inline void erase(struct test_node *node, struct rb_root *root)rb_erase (&node->rb, root); } +static inline u32 augment_recompute (struct test_node *node) +{ +u32 max = node->val, child_augmented; +if (node->rb.rb_left) { + child_augmented = rb_entry(node->rb.rb_left, struct test_node, + rb)->augmented; +if (max < child_augmented) + max = child_augmented; + } +if (node->rb.rb_right) { + child_augmented = rb_entry(node->rb.rb_right, struct test_node, + rb)->augmented; +if (max < child_augmented) + max = child_augmented; + } +return max; +} + +static void augment_callback (struct rb_node *rb,void *unused) +{ + struct test_node *node = rb_entry(rb, struct test_node, rb); + node->augmented =augment_recompute (node); +} + +static void insert_augmented (struct test_node *node,struct rb_root *root) +{ +struct rb_node **new = &root->rb_node, *parent =NULL ; +u32 key = node->key; + +while (*new) { + parent = *new; + if (key < rb_entry(parent, struct test_node, rb)->key) + new = &parent->rb_left; +else + new = &parent->rb_right; + } + +rb_link_node (&node->rb, parent, new); +rb_insert_color (&node->rb, root); +rb_augment_insert (&node->rb, augment_callback,NULL ); +} + +static void erase_augmented (struct test_node *node,struct rb_root *root) +{ +struct rb_node *deepest =rb_augment_erase_begin (&node->rb); +rb_erase (&node->rb, root); +rb_augment_erase_end (deepest, augment_callback,NULL ); +} +static void init (void ) {int i; -for (i =0 ; i <NODES ; i++) +for (i =0 ; i <NODES ; i++) { nodes[i].key =prandom32 (&rnd); + nodes[i].val =prandom32 (&rnd); + } }static bool is_red (struct rb_node *rb)
@@ -81,6 +137,17 @@ static void check(int nr_nodes)WARN_ON_ONCE (count != nr_nodes); } +static void check_augmented (int nr_nodes) +{ +struct rb_node *rb; + +check (nr_nodes); +for (rb =rb_first (&root); rb; rb =rb_next (rb)) { + struct test_node *node = rb_entry(rb, struct test_node, rb); +WARN_ON_ONCE (node->augmented !=augment_recompute (node)); + } +} +static int rbtree_test_init (void ) {int i, j;
@@ -119,6 +186,38 @@ static int rbtree_test_init(void)check (0 ); } +printk (KERN_ALERT "augmented rbtree testing" ); + +init (); + + time1 =get_cycles (); + +for (i =0 ; i <PERF_LOOPS ; i++) { +for (j =0 ; j <NODES ; j++) +insert_augmented (nodes + j, &root); +for (j =0 ; j <NODES ; j++) +erase_augmented (nodes + j, &root); + } + + time2 =get_cycles (); + time = time2 - time1; + + time =div_u64 (time,PERF_LOOPS ); +printk (" -> %llu cycles\n" , (unsigned long long )time); + +for (i =0 ; i <CHECK_LOOPS ; i++) { +init (); +for (j =0 ; j <NODES ; j++) { +check_augmented (j); +insert_augmented (nodes + j, &root); + } +for (j =0 ; j <NODES ; j++) { +check_augmented (NODES - j); +erase_augmented (nodes + j, &root); + } +check_augmented (0 ); + } +return -EAGAIN ;/* Fail will directly unload the module */ }
Signature · 7 lines
1.7.7.3 -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
Re: [PATCH v2 7/9] rbtree: augmented rbtree test
Quoted 3 lines · Michel Lespinasse
Small test to measure the performance of augmented rbtrees.
Signed-off-by Michel Lespinasse<[email protected]>
Signature · 7 lines
All rights reversed -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
PATCH v2 8/9 rbtree: faster augmented rbtree manipulation
In reply to Michel LespinasseIntroduce new augmented rbtree APIs that allow minimal recalculation of augmented node information.
A new callback is added to the rbtree insertion and erase rebalancing functions, to be called on each tree rotations. Such rotations preserve the subtree's root augmented value, but require recalculation of the one child that was previously located at the subtree root.
In the insertion case, the handcoded search phase must be updated to maintain the augmented information on insertion, and then the rbtree coloring/rebalancing algorithms keep it up to date.
In the erase case, things are more complicated since it is library code that manipulates the rbtree in order to remove internal nodes. This requires a couple additional callbacks to copy a subtree's augmented value when a new root is stitched in, and to recompute augmented values down the ancestry path when a node is removed from the tree.
In order to preserve maximum speed for the non-augmented case, we provide two versions of each tree manipulation function. rb_insert_augmented() is the augmented equivalent of rb_insert_color(), and rb_erase_augmented() is the augmented equivalent of rb_erase().
--- Documentation/rbtree.txt | 190 ++++++++++++++++++++++++++++++++++++++-------- include/linux/rbtree.h | 19 +++++ lib/rbtree.c | 83 ++++++++++++++++++-- lib/rbtree_test.c | 58 +++++++++++---- 4 files changed, 296 insertions(+), 54 deletions(-)
Documentation/rbtree.txt +157 -33
@@ -193,24 +193,42 @@ Example: Support for Augmented rbtrees ----------------------------- -Augmented rbtree is an rbtree with "some" additional data stored in each node. -This data can be used to augment some new functionality to rbtree. -Augmented rbtree is an optional feature built on top of basic rbtree -infrastructure. An rbtree user who wants this feature will have to call the -augmentation functions with the user provided augmentation callback -when inserting and erasing nodes. +Augmented rbtree is an rbtree with "some" additional data stored in +each node, where the additional data for node N must be a function of +the contents of all nodes in the subtree rooted at N. This data can +be used to augment some new functionality to rbtree. Augmented rbtree +is an optional feature built on top of basic rbtree infrastructure. +An rbtree user who wants this feature will have to call the augmentation +functions with the user provided augmentation callback when inserting +and erasing nodes. -On insertion, the user must call rb_augment_insert() once the new node is in -place. This will cause the augmentation function callback to be called for -each node between the new node and the root which has been affected by the -insertion. +On insertion, the user must update the augmented information on the path +leading to the inserted node, then call rb_link_node() as usual and +rb_augment_inserted() instead of the usual rb_insert_color() call. +If rb_augment_inserted() rebalances the rbtree, it will callback into +a user provided function to update the augmented information on the +affected subtrees. -When erasing a node, the user must call rb_augment_erase_begin() first to -retrieve the deepest node on the rebalance path. Then, after erasing the -original node, the user must call rb_augment_erase_end() with the deepest -node found earlier. This will cause the augmentation function to be called -for each affected node between the deepest node and the root. +When erasing a node, the user must call rb_erase_augmented() instead of +rb_erase(). rb_erase_augmented() calls back into user provided functions +to updated the augmented information on affected subtrees. +In both cases, the callbacks are provided through struct rb_augment_callbacks. +3 callbacks must be defined: + +- A propagation callback, which updates the augmented value for a given + node and its ancestors, up to a given stop point (or NULL to update + all the way to the root). + +- A copy callback, which copies the augmented value for a given subtree + to a newly assigned subtree root. + +- A tree rotation callback, which copies the augmented value for a given + subtree to a newly assigned subtree root AND recomputes the augmented + information for the former subtree root. + + +Sample usage: Interval tree is an example of augmented rb tree. Reference - "Introduction to Algorithms" by Cormen, Leiserson, Rivest and Stein.
@@ -230,26 +248,132 @@ and its immediate children. And this will be used in O(log n) lookup for lowest match (lowest start address among all possible matches) with something like: -find_lowest_match(lo, hi, node) +struct interval_tree_node * +interval_tree_first_match(struct rb_root *root, + unsigned long start, unsigned long last) { - lowest_match = NULL; - while (node) { - if (max_hi(node->left) > lo) { - // Lowest overlap if any must be on left side - node = node->left; - } else if (overlap(lo, hi, node)) { - lowest_match = node; - break; - } else if (lo > node->lo) { - // Lowest overlap if any must be on right side - node = node->right; - } else { - break; + struct interval_tree_node *node; + + if (!root->rb_node) + return NULL; + node = rb_entry(root->rb_node, struct interval_tree_node, rb); + + while (true) { + if (node->rb.rb_left) { + struct interval_tree_node *left = + rb_entry(node->rb.rb_left, + struct interval_tree_node, rb); + if (left->__subtree_last >= start) { + /* + * Some nodes in left subtree satisfy Cond2. + * Iterate to find the leftmost such node N. + * If it also satisfies Cond1, that's the match + * we are looking for. Otherwise, there is no + * matching interval as nodes to the right of N + * can't satisfy Cond1 either. + */ + node = left; + continue; + } } + if (node->start <= last) { /* Cond1 */ + if (node->last >= start) /* Cond2 */ + return node; /* node is leftmost match */ + if (node->rb.rb_right) { + node = rb_entry(node->rb.rb_right, + struct interval_tree_node, rb); + if (node->__subtree_last >= start) + continue; + } + } + return NULL; /* No match */ + } +} + +Insertion/removal are defined using the following augmented callbacks: + +static inline unsigned long +compute_subtree_last(struct interval_tree_node *node) +{ + unsigned long max = node->last, subtree_last; + if (node->rb.rb_left) { + subtree_last = rb_entry(node->rb.rb_left, + struct interval_tree_node, rb)->__subtree_last; + if (max < subtree_last) + max = subtree_last; + } + if (node->rb.rb_right) { + subtree_last = rb_entry(node->rb.rb_right, + struct interval_tree_node, rb)->__subtree_last; + if (max < subtree_last) + max = subtree_last; + } + return max; +} + +static void augment_propagate(struct rb_node *rb, struct rb_node *stop) +{ + while (rb != stop) { + struct interval_tree_node *node = + rb_entry(rb, struct interval_tree_node, rb); + unsigned long subtree_last = compute_subtree_last(node); + if (node->__subtree_last == subtree_last) + break; + node->__subtree_last = subtree_last; + rb = rb_parent(&node->rb); + } +} + +static void augment_copy(struct rb_node *rb_old, struct rb_node *rb_new) +{ + struct interval_tree_node *old = + rb_entry(rb_old, struct interval_tree_node, rb); + struct interval_tree_node *new = + rb_entry(rb_new, struct interval_tree_node, rb); + + new->__subtree_last = old->__subtree_last; +} + +static void augment_rotate(struct rb_node *rb_old, struct rb_node *rb_new) +{ + struct interval_tree_node *old = + rb_entry(rb_old, struct interval_tree_node, rb); + struct interval_tree_node *new = + rb_entry(rb_new, struct interval_tree_node, rb); + + new->__subtree_last = old->__subtree_last; + old->__subtree_last = compute_subtree_last(old); +} + +static const struct rb_augment_callbacks augment_callbacks = { + augment_propagate, augment_copy, augment_rotate +}; + +void interval_tree_insert(struct interval_tree_node *node, + struct rb_root *root) +{ + struct rb_node **link = &root->rb_node, *rb_parent = NULL; + unsigned long start = node->start, last = node->last; + struct interval_tree_node *parent; + + while (*link) { + rb_parent = *link; + parent = rb_entry(rb_parent, struct interval_tree_node, rb); + if (parent->__subtree_last < last) + parent->__subtree_last = last; + if (start < parent->start) + link = &parent->rb.rb_left; + else + link = &parent->rb.rb_right; } - return lowest_match; + + node->__subtree_last = last; + rb_link_node(&node->rb, rb_parent, link); + rb_insert_augmented(&node->rb, root, &augment_callbacks); } -Finding exact match will be to first find lowest match and then to follow -successor nodes looking for exact match, until the start of a node is beyond -the hi value we are looking for. +void interval_tree_remove(struct interval_tree_node *node, + struct rb_root *root) +{ + rb_erase_augmented(&node->rb, root, &augment_callbacks); +}
include/linux/rbtree.h +19 -0
@@ -61,6 +61,25 @@ struct rb_root {extern void rb_insert_color (struct rb_node *,struct rb_root *);extern void rb_erase (struct rb_node *,struct rb_root *); + +struct rb_augment_callbacks { +void (*propagate)(struct rb_node *node,struct rb_node *stop); +void (*copy)(struct rb_node *old,struct rb_node *new); +void (*rotate)(struct rb_node *old,struct rb_node *new); +}; + +extern void __rb_insert_augmented (struct rb_node *node,struct rb_root *root, +void (*augment_rotate)(struct rb_node *old,struct rb_node *new)); +extern void rb_erase_augmented (struct rb_node *node,struct rb_root *root, +const struct rb_augment_callbacks *augment); +static inline void +rb_insert_augmented (struct rb_node *node,struct rb_root *root, +const struct rb_augment_callbacks *augment) +{ +__rb_insert_augmented (node, root, augment->rotate); +} + +typedef void (*rb_augment_f )(struct rb_node *node,void *data); extern void rb_augment_insert(struct rb_node *node,
lib/rbtree.c +76 -7
195 lines not on this page · raw message
lib/rbtree_test.c +44 -14
79 lines not on this page · raw message
Signature · 7 lines
1.7.7.3 -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
Re: [PATCH v2 8/9] rbtree: faster augmented rbtree manipulation
Quoted 19 lines · Michel Lespinasse
Introduce new augmented rbtree APIs that allow minimal recalculation of augmented node information.
A new callback is added to the rbtree insertion and erase rebalancing functions, to be called on each tree rotations. Such rotations preserve the subtree's root augmented value, but require recalculation of the one child that was previously located at the subtree root.
In the insertion case, the handcoded search phase must be updated to maintain the augmented information on insertion, and then the rbtree coloring/rebalancing algorithms keep it up to date.
In the erase case, things are more complicated since it is library code that manipulates the rbtree in order to remove internal nodes. This requires a couple additional callbacks to copy a subtree's augmented value when a new root is stitched in, and to recompute augmented values down the ancestry path when a node is removed from the tree.
Quoted 6 lines
In order to preserve maximum speed for the non-augmented case, we provide two versions of each tree manipulation function.
rb_insert_augmented()is the augmented equivalent ofrb_insert_color(), andrb_erase_augmented()is the augmented equivalent ofrb_erase().Signed-off-by Michel Lespinasse<[email protected]>
Signature · 7 lines
All rights reversed -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
Peter Zijlstra
maintainerRe: [PATCH v2 8/9] rbtree: faster augmented rbtree manipulation
In reply to Michel LespinasseQuoted 23 lines · Michel Lespinasse
Documentation/rbtree.txt +23
-0+static void augment_propagate(struct rb_node *rb, struct rb_node *stop) +{ + while (rb != stop) { + struct interval_tree_node *node = + rb_entry(rb, struct interval_tree_node, rb); + unsigned long subtree_last = compute_subtree_last(node); + if (node->__subtree_last == subtree_last) + break; + node->__subtree_last = subtree_last; + rb = rb_parent(&node->rb); + } +} + +static void augment_copy(struct rb_node *rb_old, struct rb_node *rb_new) +{ + struct interval_tree_node *old = + rb_entry(rb_old, struct interval_tree_node, rb); + struct interval_tree_node *new = + rb_entry(rb_new, struct interval_tree_node, rb); + + new->__subtree_last = old->__subtree_last; +} +
Documentation/rbtree.txt and its immediate children. And this will be used in O(log n) lookup · line 346
Quoted 10 lines
Documentation/rbtree.txt +10
-0+static void augment_rotate(struct rb_node *rb_old, struct rb_node *rb_new) +{ + struct interval_tree_node *old = + rb_entry(rb_old, struct interval_tree_node, rb); + struct interval_tree_node *new = + rb_entry(rb_new, struct interval_tree_node, rb); + + new->__subtree_last = old->__subtree_last; + old->__subtree_last = compute_subtree_last(old); +}
I still don't get why we need the 3 callbacks when both propagate and rotate are simple variants of the original callback (compute_subtree_last, in this instance).
Why would every user need to replicate the propagate and rotate boilerplate?
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
Peter Zijlstra
maintainerRe: [PATCH v2 8/9] rbtree: faster augmented rbtree manipulation
Quoted 2 lines · Peter Zijlstra
Why would every user need to replicate the propagate and rotate boilerplate?
So I don't have a tree near that any of this applies to (hence no actual patch), but why can't we have something like:
struct rb_augment_callback {
const bool (*update)(struct rb_node *node);
const int offset;
const int size;
};#define RB_AUGMENT_CALLBACK(_update, _type, _rb_member, _aug_member) \
(struct rb_augment_callback){ \
.update = _update, \
.offset = offsetof(_type, _aug_member) - \
offsetof(_type, _rb_member), \
.size = sizeof(((_type *)NULL)->_aug_member), \
}static __always_inline void augment_copy(struct rb_node *dst, struct rb_node *src,
const rb_augment_callback *ac)
{
memcpy((void *)dst + ac->offset,
(void *)src + ac->offset,
ac->size);
} static __always_inline void augment_propagate(struct rb_node *rb, struct rb_node *stop,
const struct rb_augment_callback *ac)
{
while (rb != stop) {
if (!ac->update(rb))
break;
rb = rb_parent(rb);
}
}static __always_inline void augment_rotate(struct rb_node *old, struct rb_node *new.
const struct rb_augment_callback *ac)
{
augment_copy(new, old, ac);
(void)ac->update(old);
}--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
Re: [PATCH v2 8/9] rbtree: faster augmented rbtree manipulation
Quoted 7 lines · Peter Zijlstra
Quoted 2 lines · Peter Zijlstra
Why would every user need to replicate the propagate and rotate boilerplate?
So I don't have a tree near that any of this applies to (hence no actual patch)
All right, here are instructions to get a tree this will apply to :) 1- fetch linux-next tree
2- check out next-20120806
3- revert e406c4110c968b7691c4ccfadcd866a74a72fa5b (was sent as previous RFC version of this series, didn't realize it had made it into -mm)
4- apply patches 1 and 3-9 of this series (patch 2 was also sent as previous RFC version and made it into -mm)
Quoted 36 lines
but why can't we have something like:
struct rb_augment_callback { const bool (*update)(struct rb_node *node); const int offset; const int size; };#define RB_AUGMENT_CALLBACK(_update, _type, _rb_member, _aug_member) \ (struct rb_augment_callback){ \ .update = _update, \ .offset = offsetof(_type, _aug_member) - \ offsetof(_type, _rb_member), \ .size = sizeof(((_type *)NULL)->_aug_member), \}
static
__always_inlinevoid augment_copy(structrb_node*dst, structrb_node*src,
constrb_augment_callback*ac){ memcpy((void *)dst + ac->offset, (void *)src + ac->offset, ac->size); }static
__always_inlinevoid augment_propagate(structrb_node*rb, structrb_node*stop,
const structrb_augment_callback*ac){ while (rb != stop) { if (!ac->update(rb)) break; rb = rb_parent(rb); } }
Quoted 7 lines
static
__always_inlinevoid augment_rotate(structrb_node*old, structrb_node*new.
const structrb_augment_callback*ac){ augment_copy(new, old, ac); (void)ac->update(old); }
I don't think this would work well, because ac->offset and ac->size wouldn't be known at the point where they are needed, so the memcpy wouldn't be nicely optimized into a fetch and store of the desired size.
However, I wouldn't have a problem with declaring all 3 callbacks (and the struct holding them) using a preprocessor macro as you propose. Would that seem fine with you ? I can send an add-on patch to do that.
Signature · 8 lines
Michel "Walken" Lespinasse A program is never fully debugged until the last user dies. -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
PATCH 1/1 rbtree: add RB_DECLARE_CALLBACKS() macro
This proposed patch goes after 9/9 of my previous submission and makes it easier to define the augmented rbtree callbacks.
Peter, does this fix the concern you raised over patch 8/9 ?
--- arch/x86/mm/pat_rbtree.c | 37 ++----------------------------------- include/linux/rbtree.h | 30 ++++++++++++++++++++++++++++++ lib/rbtree_test.c | 34 ++-------------------------------- 3 files changed, 34 insertions(+), 67 deletions(-)
arch/x86/mm/pat_rbtree.c +2 -35
@@ -69,41 +69,8 @@ static u64 compute_subtree_max_end(struct memtype *data)return max_end; } -/* Update 'subtree_max_end' for node and its parents */ -static void memtype_rb_propagate_cb (struct rb_node *node,struct rb_node *stop) -{ -while (node != stop) { - struct memtype *data = container_of(node, struct memtype, rb); -u64 subtree_max_end =compute_subtree_max_end (data); -if (data->subtree_max_end == subtree_max_end) -break ; - data->subtree_max_end = subtree_max_end; - node =rb_parent (&data->rb); - } -} - -static void memtype_rb_copy_cb (struct rb_node *old,struct rb_node *new) -{ - struct memtype *old_data = container_of(old, struct memtype, rb); - struct memtype *new_data = container_of(new, struct memtype, rb); - - new_data->subtree_max_end = old_data->subtree_max_end; -} - -/* Update 'subtree_max_end' after tree rotation. old and new are the -* former and current subtree roots */ -static void memtype_rb_rotate_cb (struct rb_node *old,struct rb_node *new) -{ - struct memtype *old_data = container_of(old, struct memtype, rb); - struct memtype *new_data = container_of(new, struct memtype, rb); - - new_data->subtree_max_end = old_data->subtree_max_end; - old_data->subtree_max_end =compute_subtree_max_end (old_data); -} - -static const struct rb_augment_callbacks memtype_rb_augment_cb = { - memtype_rb_propagate_cb, memtype_rb_copy_cb, memtype_rb_rotate_cb -}; +RB_DECLARE_CALLBACKS(static, memtype_rb_augment_cb, struct memtype, rb, + u64, subtree_max_end, compute_subtree_max_end) /* Find the first (lowest start addr) overlapping range from rb tree */ static struct memtype *memtype_rb_lowest_match(struct rb_root *root,
include/linux/rbtree.h +30 -0
@@ -79,6 +79,36 @@ rb_insert_augmented(struct rb_node *node, struct rb_root *root,__rb_insert_augmented (node, root, augment->rotate); } +#define RB_DECLARE_CALLBACKS (rbstatic, rbname, rbstruct, rbfield, \ + rbtype, rbaugmented, rbcompute) \ +static void rbname ## _propagate(struct rb_node *rb, struct rb_node *stop) \ +{ \ + while (rb != stop) { \ + rbstruct *node = rb_entry(rb, rbstruct, rbfield); \ + rbtype augmented = rbcompute(node); \ + if (node->rbaugmented == augmented) \ + break; \ + node->rbaugmented = augmented; \ + rb = rb_parent(&node->rbfield); \ + } \ +} \ +static void rbname ## _copy(struct rb_node *rb_old, struct rb_node *rb_new) \ +{ \ + rbstruct *old = rb_entry(rb_old, rbstruct, rbfield); \ + rbstruct *new = rb_entry(rb_new, rbstruct, rbfield); \ + new->rbaugmented = old->rbaugmented; \ +} \ +static void rbname ## _rotate(struct rb_node *rb_old, struct rb_node *rb_new) \ +{ \ + rbstruct *old = rb_entry(rb_old, rbstruct, rbfield); \ + rbstruct *new = rb_entry(rb_new, rbstruct, rbfield); \ + new->rbaugmented = old->rbaugmented; \ + old->rbaugmented = rbcompute(old); \ +} \ +rbstatic const struct rb_augment_callbacks rbname = { \ + rbname ## _propagate, rbname ## _copy, rbname ## _rotate \ +}; +/* Find logical next and previous nodes in a tree */ extern struct rb_node *rb_next (const struct rb_node *);
lib/rbtree_test.c +2 -32
@@ -61,38 +61,8 @@ static inline u32 augment_recompute(struct test_node *node)return max; } -static void augment_propagate (struct rb_node *rb,struct rb_node *stop) -{ -while (rb != stop) { - struct test_node *node = rb_entry(rb, struct test_node, rb); -u32 augmented =augment_recompute (node); -if (node->augmented == augmented) -break ; - node->augmented = augmented; - rb =rb_parent (&node->rb); - } -} - -static void augment_copy (struct rb_node *rb_old,struct rb_node *rb_new) -{ - struct test_node *old = rb_entry(rb_old, struct test_node, rb); - struct test_node *new = rb_entry(rb_new, struct test_node, rb); - new->augmented = old->augmented; -} - -static void augment_rotate (struct rb_node *rb_old,struct rb_node *rb_new) -{ - struct test_node *old = rb_entry(rb_old, struct test_node, rb); - struct test_node *new = rb_entry(rb_new, struct test_node, rb); - -/* Rotation doesn't change subtree's augmented value */ - new->augmented = old->augmented; - old->augmented =augment_recompute (old); -} - -static const struct rb_augment_callbacks augment_callbacks = { - augment_propagate, augment_copy, augment_rotate -}; +RB_DECLARE_CALLBACKS(static, augment_callbacks, struct test_node, rb, + u32, augmented, augment_recompute)static void insert_augmented (struct test_node *node,struct rb_root *root) {
Signature · 7 lines
1.7.7.3 -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
Peter Zijlstra
maintainerRe: [PATCH v2 8/9] rbtree: faster augmented rbtree manipulation
In reply to Michel Lespinasseinclude/linux/rbtree.h struct rb_root { · line 69
Quoted 5 lines · Michel Lespinasse
include/linux/rbtree.h +5
-0+struct rb_augment_callbacks { +void (*propagate)(struct rb_node *node,struct rb_node *stop); +void (*copy)(struct rb_node *old,struct rb_node *new); +void (*rotate)(struct rb_node *old,struct rb_node *new); +};
Should we make that const pointers? Daniel?
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
Re: [PATCH v2 8/9] rbtree: faster augmented rbtree manipulation
Quoted 8 lines · Peter Zijlstra
include/linux/rbtree.h struct rb_root { · line 69
Quoted 5 lines · Michel Lespinasse
include/linux/rbtree.h +5
-0+struct rb_augment_callbacks { +void (*propagate)(struct rb_node *node,struct rb_node *stop); +void (*copy)(struct rb_node *old,struct rb_node *new); +void (*rotate)(struct rb_node *old,struct rb_node *new); +};Should we make that const pointers? Daniel?
I don't think it would hurt, but note that each function taking this as an argument takes it as a const struct rb_augment_callbacks *, so I doubt the extra consts would help either.
Signature · 8 lines
Michel "Walken" Lespinasse A program is never fully debugged until the last user dies. -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
Peter Zijlstra
maintainerRe: [PATCH v2 8/9] rbtree: faster augmented rbtree manipulation
Quoted 10 lines · Michel Lespinasse
Quoted 8 lines · Peter Zijlstra
include/linux/rbtree.h struct rb_root { · line 69
Quoted 5 lines · Michel Lespinasse
include/linux/rbtree.h +5
-0+struct rb_augment_callbacks { +void (*propagate)(struct rb_node *node,struct rb_node *stop); +void (*copy)(struct rb_node *old,struct rb_node *new); +void (*rotate)(struct rb_node *old,struct rb_node *new); +};Should we make that const pointers? Daniel?
Quoted 3 lines
I don't think it would hurt, but note that each function taking this as an argument takes it as a const struct
rb_augment_callbacks*, so I doubt the extra consts would help either.
IIRC Daniel found it allowed some older GCC to inline more if the function pointer itself was constant.
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
Peter Zijlstra
maintainerRe: [PATCH v2 8/9] rbtree: faster augmented rbtree manipulation
In reply to Michel Lespinasselib/rbtree.c void rb_erase(struct rb_node *node, struct rb_root *root) · line 538
Quoted 13 lines · Michel Lespinasse
lib/rbtree.c +13
-0+void __rb_insert_augmented (struct rb_node *node,struct rb_root *root, +void (*augment_rotate)(struct rb_node *old,struct rb_node *new)) +{ +__rb_insert (node, root, augment_rotate); +} +EXPORT_SYMBOL (__rb_insert_augmented); + +void rb_erase_augmented (struct rb_node *node,struct rb_root *root, +const struct rb_augment_callbacks *augment) +{ +__rb_erase (node, root, augment); +} +EXPORT_SYMBOL (rb_erase_augmented);
From a symmetry POV I'd say have both take the rb_augment_callbacks thing. The two taking different arguments is confusing at best.
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
Re: [PATCH v2 8/9] rbtree: faster augmented rbtree manipulation
Quoted 17 lines · Peter Zijlstra
lib/rbtree.c void rb_erase(struct rb_node *node, struct rb_root *root) · line 538
Quoted 13 lines · Michel Lespinasse
lib/rbtree.c +13
-0+void __rb_insert_augmented (struct rb_node *node,struct rb_root *root, +void (*augment_rotate)(struct rb_node *old,struct rb_node *new)) +{ +__rb_insert (node, root, augment_rotate); +} +EXPORT_SYMBOL (__rb_insert_augmented); + +void rb_erase_augmented (struct rb_node *node,struct rb_root *root, +const struct rb_augment_callbacks *augment) +{ +__rb_erase (node, root, augment); +} +EXPORT_SYMBOL (rb_erase_augmented);From a symmetry POV I'd say have both take the
rb_augment_callbacksthing. The two taking different arguments is confusing at best.
The idea there is that from the user's point of view, both take the struct rb_augment_callbacks. Note that include/linux/rbtree.h has this:
static inline void
rb_insert_augmented(struct rb_node *node, struct rb_root *root,
const struct rb_augment_callbacks *augment)
{
__rb_insert_augmented(node, root, augment->rotate);
}Now the reason why the actual implementation takes the function pointer directly (and not the struct) is that the expected case is that the call site will have the struct declared as a const, so the compiler will be able to optimize out the dereference and directly pass out the function pointer as a constant.
Signature · 8 lines
Michel "Walken" Lespinasse A program is never fully debugged until the last user dies. -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
PATCH v2 9/9 rbtree: remove prior augmented rbtree implementation
In reply to Michel Lespinasseconvert arch/x86/mm/pat_rbtree.c to the proposed augmented rbtree api and remove the old augmented rbtree implementation.
--- arch/x86/mm/pat_rbtree.c | 65 +++++++++++++++++++++++++++++------------ include/linux/rbtree.h | 8 ----- lib/rbtree.c | 71 ---------------------------------------------- 3 files changed, 46 insertions(+), 98 deletions(-)
arch/x86/mm/pat_rbtree.c +46 -19
@@ -54,29 +54,57 @@ static u64 get_subtree_max_end(struct rb_node *node)return ret; } -/* Update 'subtree_max_end' for a node, based on node and its children */ -static void memtype_rb_augment_cb (struct rb_node *node,void *__unused) +static u64 compute_subtree_max_end (struct memtype *data) { -struct memtype *data; -u64 max_end, child_max_end; - -if (!node) -return ; - - data = container_of(node, struct memtype, rb); - max_end = data->end; +u64 max_end = data->end, child_max_end; - child_max_end =get_subtree_max_end (node->rb_right); + child_max_end =get_subtree_max_end (data->rb.rb_right);if (child_max_end > max_end) max_end = child_max_end; - child_max_end =get_subtree_max_end (node->rb_left); + child_max_end =get_subtree_max_end (data->rb.rb_left);if (child_max_end > max_end) max_end = child_max_end; - data->subtree_max_end = max_end; +return max_end; +} + +/* Update 'subtree_max_end' for node and its parents */ +static void memtype_rb_propagate_cb (struct rb_node *node,struct rb_node *stop) +{ +while (node != stop) { + struct memtype *data = container_of(node, struct memtype, rb); +u64 subtree_max_end =compute_subtree_max_end (data); +if (data->subtree_max_end == subtree_max_end) +break ; + data->subtree_max_end = subtree_max_end; + node =rb_parent (&data->rb); + } +} + +static void memtype_rb_copy_cb (struct rb_node *old,struct rb_node *new) +{ + struct memtype *old_data = container_of(old, struct memtype, rb); + struct memtype *new_data = container_of(new, struct memtype, rb); + + new_data->subtree_max_end = old_data->subtree_max_end; } +/* Update 'subtree_max_end' after tree rotation. old and new are the +* former and current subtree roots */ +static void memtype_rb_rotate_cb (struct rb_node *old,struct rb_node *new) +{ + struct memtype *old_data = container_of(old, struct memtype, rb); + struct memtype *new_data = container_of(new, struct memtype, rb); + + new_data->subtree_max_end = old_data->subtree_max_end; + old_data->subtree_max_end =compute_subtree_max_end (old_data); +} + +static const struct rb_augment_callbacks memtype_rb_augment_cb = { + memtype_rb_propagate_cb, memtype_rb_copy_cb, memtype_rb_rotate_cb +}; +/* Find the first (lowest start addr) overlapping range from rb tree */ static struct memtype *memtype_rb_lowest_match (struct rb_root *root,u64 start,u64 end)
@@ -179,15 +207,17 @@ static void memtype_rb_insert(struct rb_root *root, struct memtype *newdata) struct memtype *data = container_of(*node, struct memtype, rb); parent = *node; +if (data->subtree_max_end < newdata->end) + data->subtree_max_end = newdata->end;if (newdata->start <= data->start) node = &((*node)->rb_left);else if (newdata->start > data->start) node = &((*node)->rb_right); } + newdata->subtree_max_end = newdata->end;rb_link_node (&newdata->rb, parent, node); -rb_insert_color (&newdata->rb, root); -rb_augment_insert (&newdata->rb, memtype_rb_augment_cb,NULL ); +rb_insert_augmented (&newdata->rb, root, &memtype_rb_augment_cb); }int rbt_memtype_check_insert (struct memtype *new,unsigned long *ret_type)
@@ -209,16 +239,13 @@ int rbt_memtype_check_insert(struct memtype *new, unsigned long *ret_type)struct memtype *rbt_memtype_erase (u64 start,u64 end) { -struct rb_node *deepest;struct memtype *data; data =memtype_rb_exact_match (&memtype_rbroot, start, end);if (!data) goto out; - deepest =rb_augment_erase_begin (&data->rb); -rb_erase (&data->rb, &memtype_rbroot); -rb_augment_erase_end (deepest, memtype_rb_augment_cb,NULL ); +rb_erase_augmented (&data->rb, &memtype_rbroot, &memtype_rb_augment_cb); out:return data; }
include/linux/rbtree.h +0 -8
@@ -80,14 +80,6 @@ rb_insert_augmented(struct rb_node *node, struct rb_root *root, } -typedef void (*rb_augment_f )(struct rb_node *node,void *data); - -extern void rb_augment_insert (struct rb_node *node, -rb_augment_f func,void *data); -extern struct rb_node *rb_augment_erase_begin (struct rb_node *node); -extern void rb_augment_erase_end (struct rb_node *node, -rb_augment_f func,void *data); -/* Find logical next and previous nodes in a tree */ extern struct rb_node *rb_next (const struct rb_node *);extern struct rb_node *rb_prev (const struct rb_node *);
lib/rbtree.c +0 -71
77 lines not on this page · raw message
Signature · 7 lines
1.7.7.3 -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
Re: [PATCH v2 9/9] rbtree: remove prior augmented rbtree implementation
Quoted 2 lines · Michel Lespinasse
convert
arch/x86/mm/pat_rbtree.cto the proposed augmented rbtree api and remove the old augmented rbtree implementation.
style trivia:
Quoted 4 lines
arch/x86/mm/pat_rbtree.c +1
-2+static u64 compute_subtree_max_end (struct memtype *data) { -struct memtype *data; -u64 max_end, child_max_end;
arch/x86/mm/pat_rbtree.c static u64 get_subtree_max_end(struct rb_node *node) · line 61
Quoted 10 lines
arch/x86/mm/pat_rbtree.c +2
-7- -if (!node) -return ; - - data = container_of(node, struct memtype, rb); - max_end = data->end; +u64 max_end = data->end, child_max_end; - child_max_end =get_subtree_max_end (node->rb_right); + child_max_end =get_subtree_max_end (data->rb.rb_right);
I think this reads better as:
u64 max_end = data->end; u64 child_max_end = get_subtree_max_end(node->rb.rb_right);
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
Re: [PATCH v2 9/9] rbtree: remove prior augmented rbtree implementation
In reply to Michel LespinasseQuoted 4 lines · Michel Lespinasse
convert
arch/x86/mm/pat_rbtree.cto the proposed augmented rbtree api and remove the old augmented rbtree implementation.Signed-off-by Michel Lespinasse<[email protected]>
Signature · 7 lines
All rights reversed -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: <a href=mailto:"[email protected]"> [email protected] </a>