The patch titled
Subject: rbtree: adjust node color in __rb_erase_color() only when necessary
has been added to the -mm tree. Its filename is
rbtree-adjust-node-color-in-__rb_erase_color-only-when-necessary.patch
Before you just go and hit "reply", please:
a) Consider who else should be cc'ed
b) Prefer to cc a suitable mailing list as well
c) Ideally: find the original patch on the mailing list and do a
reply-to-all to that, adding suitable additional cc's
*** Remember to use Documentation/SubmitChecklist when testing your code ***
The -mm tree is included into linux-next and is updated
there every 3-4 working days
------------------------------------------------------
From: Michel Lespinasse <walken@xxxxxxxxxx>
Subject: rbtree: adjust node color in __rb_erase_color() only when necessary
In __rb_erase_color(), we were always setting a node to black after
exiting the main loop. And in one case, after fixing up the tree to
satisfy all rbtree invariants, we were setting the current node to root
just to guarantee a loop exit, at which point the root would be set to
black. However this is not necessary, as the root of an rbtree is already
known to be black. The only case where the color flip is required is when
we exit the loop due to the current node being red, and it's easiest to
just do the flip at that point instead of doing it after the loop.
Signed-off-by: Michel Lespinasse <walken@xxxxxxxxxx>
Cc: Andrea Arcangeli <aarcange@xxxxxxxxxx>
Cc: David Woodhouse <dwmw2@xxxxxxxxxxxxx>
Cc: Rik van Riel <riel@xxxxxxxxxx>
Cc: Peter Zijlstra <a.p.zijlstra@xxxxxxxxx>
Cc: Daniel Santos <daniel.santos@xxxxxxxxx>
Cc: Jens Axboe <axboe@xxxxxxxxx>
Cc: "Eric W. Biederman" <ebiederm@xxxxxxxxxxxx>
Signed-off-by: Andrew Morton <akpm@xxxxxxxxxxxxxxxxxxxx>
---
lib/rbtree.c | 28 +++++++++++++++++-----------
1 file changed, 17 insertions(+), 11 deletions(-)
diff -puN lib/rbtree.c~rbtree-adjust-node-color-in-__rb_erase_color-only-when-necessary lib/rbtree.c
--- a/lib/rbtree.c~rbtree-adjust-node-color-in-__rb_erase_color-only-when-necessary
+++ a/lib/rbtree.c
@@ -259,10 +259,22 @@ static void __rb_erase_color(struct rb_n
{
struct rb_node *other;
- while ((!node || rb_is_black(node)) && node != root->rb_node)
- {
- if (parent->rb_left == node)
- {
+ while (true) {
+ /*
+ * Loop invariant: all leaf paths going through node have a
+ * black node count that is 1 lower than other leaf paths.
+ *
+ * If node is red, we can flip it to black to adjust.
+ * If node is the root, all leaf paths go through it.
+ * Otherwise, we need to adjust the tree through color flips
+ * and tree rotations as per one of the 4 cases below.
+ */
+ if (node && rb_is_red(node)) {
+ rb_set_black(node);
+ break;
+ } else if (!parent) {
+ break;
+ } else if (parent->rb_left == node) {
other = parent->rb_right;
if (rb_is_red(other))
{
@@ -291,12 +303,9 @@ static void __rb_erase_color(struct rb_n
rb_set_black(parent);
rb_set_black(other->rb_right);
__rb_rotate_left(parent, root);
- node = root->rb_node;
break;
}
- }
- else
- {
+ } else {
other = parent->rb_left;
if (rb_is_red(other))
{
@@ -325,13 +334,10 @@ static void __rb_erase_color(struct rb_n
rb_set_black(parent);
rb_set_black(other->rb_left);
__rb_rotate_right(parent, root);
- node = root->rb_node;
break;
}
}
}
- if (node)
- rb_set_black(node);
}
void rb_erase(struct rb_node *node, struct rb_root *root)
_
Subject: Subject: rbtree: adjust node color in __rb_erase_color() only when necessary
Patches currently in -mm which might be from walken@xxxxxxxxxx are
slab-do-not-call-compound_head-in-page_get_cache.patch
rbtree-reference-documentation-rbtreetxt-for-usage-instructions.patch
rbtree-empty-nodes-have-no-color.patch
rbtree-fix-incorrect-rbtree-node-insertion-in-fs-proc-proc_sysctlc.patch
rbtree-move-some-implementation-details-from-rbtreeh-to-rbtreec.patch
rbtree-performance-and-correctness-test.patch
rbtree-break-out-of-rb_insert_color-loop-after-tree-rotation.patch
rbtree-adjust-root-color-in-rb_insert_color-only-when-necessary.patch
rbtree-low-level-optimizations-in-rb_insert_color.patch
rbtree-adjust-node-color-in-__rb_erase_color-only-when-necessary.patch
rbtree-optimize-case-selection-logic-in-__rb_erase_color.patch
rbtree-low-level-optimizations-in-__rb_erase_color.patch
rbtree-coding-style-adjustments.patch
--
To unsubscribe from this list: send the line "unsubscribe mm-commits" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
