From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from psmtp.com (na3sys010amx168.postini.com [74.125.245.168]) by kanga.kvack.org (Postfix) with SMTP id DF62E6B0044 for ; Thu, 2 Aug 2012 18:34:31 -0400 (EDT) Received: by yenr5 with SMTP id r5so78993yen.14 for ; Thu, 02 Aug 2012 15:34:31 -0700 (PDT) From: Michel Lespinasse Subject: [PATCH v2 0/9] faster augmented rbtree interface Date: Thu, 2 Aug 2012 15:34:09 -0700 Message-Id: <1343946858-8170-1-git-send-email-walken@google.com> Sender: owner-linux-mm@kvack.org List-ID: To: riel@redhat.com, peterz@infradead.org, daniel.santos@pobox.com, aarcange@redhat.com, dwmw2@infradead.org, akpm@linux-foundation.org Cc: linux-mm@kvack.org, linux-kernel@vger.kernel.org, torvalds@linux-foundation.org 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(-) -- 1.7.7.3 -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to majordomo@kvack.org. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: email@kvack.org From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from psmtp.com (na3sys010amx161.postini.com [74.125.245.161]) by kanga.kvack.org (Postfix) with SMTP id 2A3756B005A for ; Thu, 2 Aug 2012 18:34:33 -0400 (EDT) Received: by yenr5 with SMTP id r5so79023yen.14 for ; Thu, 02 Aug 2012 15:34:32 -0700 (PDT) From: Michel Lespinasse Subject: [PATCH v2 1/9] rbtree test: fix sparse warning about 64-bit constant Date: Thu, 2 Aug 2012 15:34:10 -0700 Message-Id: <1343946858-8170-2-git-send-email-walken@google.com> In-Reply-To: <1343946858-8170-1-git-send-email-walken@google.com> References: <1343946858-8170-1-git-send-email-walken@google.com> Sender: owner-linux-mm@kvack.org List-ID: To: riel@redhat.com, peterz@infradead.org, daniel.santos@pobox.com, aarcange@redhat.com, dwmw2@infradead.org, akpm@linux-foundation.org Cc: linux-mm@kvack.org, linux-kernel@vger.kernel.org, torvalds@linux-foundation.org Just a small fix to make sparse happy. Signed-off-by: Michel Lespinasse Reported-by: Fengguang Wu --- lib/rbtree_test.c | 2 +- 1 files changed, 1 insertions(+), 1 deletions(-) diff --git a/lib/rbtree_test.c b/lib/rbtree_test.c index 19dfca9..fd09465 100644 --- a/lib/rbtree_test.c +++ b/lib/rbtree_test.c @@ -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(); -- 1.7.7.3 -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to majordomo@kvack.org. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: email@kvack.org From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from psmtp.com (na3sys010amx168.postini.com [74.125.245.168]) by kanga.kvack.org (Postfix) with SMTP id 226846B005D for ; Thu, 2 Aug 2012 18:34:35 -0400 (EDT) Received: by mail-yx0-f169.google.com with SMTP id r5so78993yen.14 for ; Thu, 02 Aug 2012 15:34:34 -0700 (PDT) From: Michel Lespinasse Subject: [PATCH v2 2/9] rbtree: optimize fetching of sibling node Date: Thu, 2 Aug 2012 15:34:11 -0700 Message-Id: <1343946858-8170-3-git-send-email-walken@google.com> In-Reply-To: <1343946858-8170-1-git-send-email-walken@google.com> References: <1343946858-8170-1-git-send-email-walken@google.com> Sender: owner-linux-mm@kvack.org List-ID: To: riel@redhat.com, peterz@infradead.org, daniel.santos@pobox.com, aarcange@redhat.com, dwmw2@infradead.org, akpm@linux-foundation.org Cc: linux-mm@kvack.org, linux-kernel@vger.kernel.org, torvalds@linux-foundation.org When looking to fetch a node's sibling, we went through a sequence of: - check if node is the parent's left child - if it is, then fetch the parent's right child This can be replaced with: - fetch the parent's right child as an assumed sibling - check that node is NOT the fetched child This avoids fetching the parent's left child when node is actually that child. Saves a bit on code size, though it doesn't seem to make a large difference in speed. Signed-off-by: Michel Lespinasse --- lib/rbtree.c | 21 +++++++++++++-------- 1 files changed, 13 insertions(+), 8 deletions(-) diff --git a/lib/rbtree.c b/lib/rbtree.c index 0892670..61cdd0e 100644 --- a/lib/rbtree.c +++ b/lib/rbtree.c @@ -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 -- 1.7.7.3 -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to majordomo@kvack.org. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: email@kvack.org From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from psmtp.com (na3sys010amx204.postini.com [74.125.245.204]) by kanga.kvack.org (Postfix) with SMTP id 6CCF96B0062 for ; Thu, 2 Aug 2012 18:34:37 -0400 (EDT) Received: by yhr47 with SMTP id 47so71180yhr.14 for ; Thu, 02 Aug 2012 15:34:36 -0700 (PDT) From: Michel Lespinasse Subject: [PATCH v2 3/9] rbtree: add __rb_change_child() helper function Date: Thu, 2 Aug 2012 15:34:12 -0700 Message-Id: <1343946858-8170-4-git-send-email-walken@google.com> In-Reply-To: <1343946858-8170-1-git-send-email-walken@google.com> References: <1343946858-8170-1-git-send-email-walken@google.com> Sender: owner-linux-mm@kvack.org List-ID: To: riel@redhat.com, peterz@infradead.org, daniel.santos@pobox.com, aarcange@redhat.com, dwmw2@infradead.org, akpm@linux-foundation.org Cc: linux-mm@kvack.org, linux-kernel@vger.kernel.org, torvalds@linux-foundation.org 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 --- lib/rbtree.c | 46 +++++++++++++++++----------------------------- 1 files changed, 17 insertions(+), 29 deletions(-) diff --git a/lib/rbtree.c b/lib/rbtree.c index 61cdd0e..de89a61 100644 --- a/lib/rbtree.c +++ b/lib/rbtree.c @@ -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) -- 1.7.7.3 -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to majordomo@kvack.org. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: email@kvack.org From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from psmtp.com (na3sys010amx185.postini.com [74.125.245.185]) by kanga.kvack.org (Postfix) with SMTP id 477C56B0062 for ; Thu, 2 Aug 2012 18:34:38 -0400 (EDT) Received: by yhr47 with SMTP id 47so71191yhr.14 for ; Thu, 02 Aug 2012 15:34:37 -0700 (PDT) From: Michel Lespinasse Subject: [PATCH v2 4/9] rbtree: place easiest case first in rb_erase() Date: Thu, 2 Aug 2012 15:34:13 -0700 Message-Id: <1343946858-8170-5-git-send-email-walken@google.com> In-Reply-To: <1343946858-8170-1-git-send-email-walken@google.com> References: <1343946858-8170-1-git-send-email-walken@google.com> Sender: owner-linux-mm@kvack.org List-ID: To: riel@redhat.com, peterz@infradead.org, daniel.santos@pobox.com, aarcange@redhat.com, dwmw2@infradead.org, akpm@linux-foundation.org Cc: linux-mm@kvack.org, linux-kernel@vger.kernel.org, torvalds@linux-foundation.org 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 --- lib/rbtree.c | 35 ++++++++++++++++++----------------- 1 files changed, 18 insertions(+), 17 deletions(-) diff --git a/lib/rbtree.c b/lib/rbtree.c index de89a61..bde1b5c 100644 --- a/lib/rbtree.c +++ b/lib/rbtree.c @@ -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); } -- 1.7.7.3 -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to majordomo@kvack.org. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: email@kvack.org From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from psmtp.com (na3sys010amx175.postini.com [74.125.245.175]) by kanga.kvack.org (Postfix) with SMTP id CF9846B006E for ; Thu, 2 Aug 2012 18:34:39 -0400 (EDT) Received: by ggm4 with SMTP id 4so79762ggm.14 for ; Thu, 02 Aug 2012 15:34:38 -0700 (PDT) From: Michel Lespinasse Subject: [PATCH v2 5/9] rbtree: handle 1-child recoloring in rb_erase() instead of rb_erase_color() Date: Thu, 2 Aug 2012 15:34:14 -0700 Message-Id: <1343946858-8170-6-git-send-email-walken@google.com> In-Reply-To: <1343946858-8170-1-git-send-email-walken@google.com> References: <1343946858-8170-1-git-send-email-walken@google.com> Sender: owner-linux-mm@kvack.org List-ID: To: riel@redhat.com, peterz@infradead.org, daniel.santos@pobox.com, aarcange@redhat.com, dwmw2@infradead.org, akpm@linux-foundation.org Cc: linux-mm@kvack.org, linux-kernel@vger.kernel.org, torvalds@linux-foundation.org An interesting observation for rb_erase() is that when a node has exactly one child, the node must be black and the child must be red. An interesting consequence is that removing such a node can be done by simply replacing it with its child and making the child black, which we can do efficiently in rb_erase(). __rb_erase_color() then only needs to handle the no-childs case and can be modified accordingly. Signed-off-by: Michel Lespinasse --- lib/rbtree.c | 105 ++++++++++++++++++++++++++++++++++------------------------ 1 files changed, 62 insertions(+), 43 deletions(-) diff --git a/lib/rbtree.c b/lib/rbtree.c index bde1b5c..80b0925 100644 --- a/lib/rbtree.c +++ b/lib/rbtree.c @@ -2,7 +2,8 @@ Red Black Trees (C) 1999 Andrea Arcangeli (C) 2002 David Woodhouse - + (C) 2012 Michel Lespinasse + 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); -- 1.7.7.3 -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to majordomo@kvack.org. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: email@kvack.org From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from psmtp.com (na3sys010amx163.postini.com [74.125.245.163]) by kanga.kvack.org (Postfix) with SMTP id 77F806B006E for ; Thu, 2 Aug 2012 18:34:41 -0400 (EDT) Received: by ghrr18 with SMTP id r18so77012ghr.14 for ; Thu, 02 Aug 2012 15:34:40 -0700 (PDT) From: Michel Lespinasse Subject: [PATCH v2 6/9] rbtree: low level optimizations in rb_erase() Date: Thu, 2 Aug 2012 15:34:15 -0700 Message-Id: <1343946858-8170-7-git-send-email-walken@google.com> In-Reply-To: <1343946858-8170-1-git-send-email-walken@google.com> References: <1343946858-8170-1-git-send-email-walken@google.com> Sender: owner-linux-mm@kvack.org List-ID: To: riel@redhat.com, peterz@infradead.org, daniel.santos@pobox.com, aarcange@redhat.com, dwmw2@infradead.org, akpm@linux-foundation.org Cc: linux-mm@kvack.org, linux-kernel@vger.kernel.org, torvalds@linux-foundation.org Various minor optimizations in rb_erase(): - Avoid multiple loading of node->__rb_parent_color when computing parent and color information (possibly not in close sequence, as there might be further branches in the algorithm) - In the 1-child subcase of case 1, copy the __rb_parent_color field from the erased node to the child instead of recomputing it from the desired parent and color - When searching for the erased node's successor, differentiate between cases 2 and 3 based on whether any left links were followed. This avoids a condition later down. - In case 3, keep a pointer to the erased node's right child so we don't have to refetch it later to adjust its parent. - In the no-childs subcase of cases 2 and 3, place the rebalance assigment last so that the compiler can remove the following if(rebalance) test. Also, added some comments to illustrate cases 2 and 3. Signed-off-by: Michel Lespinasse --- lib/rbtree.c | 97 +++++++++++++++++++++++++++++++++++++-------------------- 1 files changed, 63 insertions(+), 34 deletions(-) diff --git a/lib/rbtree.c b/lib/rbtree.c index 80b0925..12d9147 100644 --- a/lib/rbtree.c +++ b/lib/rbtree.c @@ -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) -- 1.7.7.3 -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to majordomo@kvack.org. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: email@kvack.org From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from psmtp.com (na3sys010amx161.postini.com [74.125.245.161]) by kanga.kvack.org (Postfix) with SMTP id 272C26B0071 for ; Thu, 2 Aug 2012 18:34:43 -0400 (EDT) Received: by mail-yx0-f169.google.com with SMTP id r5so79023yen.14 for ; Thu, 02 Aug 2012 15:34:42 -0700 (PDT) From: Michel Lespinasse Subject: [PATCH v2 7/9] rbtree: augmented rbtree test Date: Thu, 2 Aug 2012 15:34:16 -0700 Message-Id: <1343946858-8170-8-git-send-email-walken@google.com> In-Reply-To: <1343946858-8170-1-git-send-email-walken@google.com> References: <1343946858-8170-1-git-send-email-walken@google.com> Sender: owner-linux-mm@kvack.org List-ID: To: riel@redhat.com, peterz@infradead.org, daniel.santos@pobox.com, aarcange@redhat.com, dwmw2@infradead.org, akpm@linux-foundation.org Cc: linux-mm@kvack.org, linux-kernel@vger.kernel.org, torvalds@linux-foundation.org Small test to measure the performance of augmented rbtrees. Signed-off-by: Michel Lespinasse --- lib/rbtree_test.c | 103 +++++++++++++++++++++++++++++++++++++++++++++++++++- 1 files changed, 101 insertions(+), 2 deletions(-) diff --git a/lib/rbtree_test.c b/lib/rbtree_test.c index fd09465..66e41d4 100644 --- a/lib/rbtree_test.c +++ b/lib/rbtree_test.c @@ -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 */ } -- 1.7.7.3 -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to majordomo@kvack.org. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: email@kvack.org From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from psmtp.com (na3sys010amx163.postini.com [74.125.245.163]) by kanga.kvack.org (Postfix) with SMTP id 434196B0072 for ; Thu, 2 Aug 2012 18:34:44 -0400 (EDT) Received: by mail-gh0-f169.google.com with SMTP id r18so77012ghr.14 for ; Thu, 02 Aug 2012 15:34:43 -0700 (PDT) From: Michel Lespinasse Subject: [PATCH v2 8/9] rbtree: faster augmented rbtree manipulation Date: Thu, 2 Aug 2012 15:34:17 -0700 Message-Id: <1343946858-8170-9-git-send-email-walken@google.com> In-Reply-To: <1343946858-8170-1-git-send-email-walken@google.com> References: <1343946858-8170-1-git-send-email-walken@google.com> Sender: owner-linux-mm@kvack.org List-ID: To: riel@redhat.com, peterz@infradead.org, daniel.santos@pobox.com, aarcange@redhat.com, dwmw2@infradead.org, akpm@linux-foundation.org Cc: linux-mm@kvack.org, linux-kernel@vger.kernel.org, torvalds@linux-foundation.org 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. 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(). Signed-off-by: Michel Lespinasse --- 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(-) diff --git a/Documentation/rbtree.txt b/Documentation/rbtree.txt index 8d32d85..0a0b6dc 100644 --- a/Documentation/rbtree.txt +++ b/Documentation/rbtree.txt @@ -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); +} diff --git a/include/linux/rbtree.h b/include/linux/rbtree.h index bf836a2..c902eb9 100644 --- a/include/linux/rbtree.h +++ b/include/linux/rbtree.h @@ -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, diff --git a/lib/rbtree.c b/lib/rbtree.c index 12d9147..11c11e9 100644 --- a/lib/rbtree.c +++ b/lib/rbtree.c @@ -105,7 +105,9 @@ __rb_rotate_set_parents(struct rb_node *old, struct rb_node *new, __rb_change_child(old, new, parent, root); } -void rb_insert_color(struct rb_node *node, struct rb_root *root) +static __always_inline void +__rb_insert(struct rb_node *node, struct rb_root *root, + void (*augment_rotate)(struct rb_node *old, struct rb_node *new)) { struct rb_node *parent = rb_red_parent(node), *gparent, *tmp; @@ -169,6 +171,7 @@ 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); + augment_rotate(parent, node); parent = node; tmp = node->rb_right; } @@ -187,6 +190,7 @@ void rb_insert_color(struct rb_node *node, struct rb_root *root) if (tmp) rb_set_parent_color(tmp, gparent, RB_BLACK); __rb_rotate_set_parents(gparent, parent, root, RB_RED); + augment_rotate(gparent, parent); break; } else { tmp = gparent->rb_left; @@ -209,6 +213,7 @@ 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); + augment_rotate(parent, node); parent = node; tmp = node->rb_left; } @@ -219,13 +224,15 @@ void rb_insert_color(struct rb_node *node, struct rb_root *root) if (tmp) rb_set_parent_color(tmp, gparent, RB_BLACK); __rb_rotate_set_parents(gparent, parent, root, RB_RED); + augment_rotate(gparent, parent); break; } } } -EXPORT_SYMBOL(rb_insert_color); -static void __rb_erase_color(struct rb_node *parent, struct rb_root *root) +static __always_inline void +__rb_erase_color(struct rb_node *parent, struct rb_root *root, + const struct rb_augment_callbacks *augment) { struct rb_node *node = NULL, *sibling, *tmp1, *tmp2; @@ -254,6 +261,7 @@ static void __rb_erase_color(struct rb_node *parent, struct rb_root *root) rb_set_parent_color(tmp1, parent, RB_BLACK); __rb_rotate_set_parents(parent, sibling, root, RB_RED); + augment->rotate(parent, sibling); sibling = tmp1; } tmp1 = sibling->rb_right; @@ -305,6 +313,7 @@ static void __rb_erase_color(struct rb_node *parent, struct rb_root *root) if (tmp1) rb_set_parent_color(tmp1, sibling, RB_BLACK); + augment->rotate(sibling, tmp2); tmp1 = sibling; sibling = tmp2; } @@ -327,6 +336,7 @@ static void __rb_erase_color(struct rb_node *parent, struct rb_root *root) rb_set_parent(tmp2, parent); __rb_rotate_set_parents(parent, sibling, root, RB_BLACK); + augment->rotate(parent, sibling); break; } else { sibling = parent->rb_left; @@ -337,6 +347,7 @@ static void __rb_erase_color(struct rb_node *parent, struct rb_root *root) rb_set_parent_color(tmp1, parent, RB_BLACK); __rb_rotate_set_parents(parent, sibling, root, RB_RED); + augment->rotate(parent, sibling); sibling = tmp1; } tmp1 = sibling->rb_left; @@ -363,6 +374,7 @@ static void __rb_erase_color(struct rb_node *parent, struct rb_root *root) if (tmp1) rb_set_parent_color(tmp1, sibling, RB_BLACK); + augment->rotate(sibling, tmp2); tmp1 = sibling; sibling = tmp2; } @@ -374,12 +386,15 @@ static void __rb_erase_color(struct rb_node *parent, struct rb_root *root) rb_set_parent(tmp2, parent); __rb_rotate_set_parents(parent, sibling, root, RB_BLACK); + augment->rotate(parent, sibling); break; } } } -void rb_erase(struct rb_node *node, struct rb_root *root) +static __always_inline void +__rb_erase(struct rb_node *node, struct rb_root *root, + const struct rb_augment_callbacks *augment) { struct rb_node *child = node->rb_right, *tmp = node->rb_left; struct rb_node *parent, *rebalance; @@ -401,12 +416,14 @@ void rb_erase(struct rb_node *node, struct rb_root *root) rebalance = NULL; } else rebalance = __rb_is_black(pc) ? parent : NULL; + tmp = parent; } else if (!child) { /* Still case 1, but this time the child is node->rb_left */ tmp->__rb_parent_color = pc = node->__rb_parent_color; parent = __rb_parent(pc); __rb_change_child(node, tmp, parent, root); rebalance = NULL; + tmp = parent; } else { struct rb_node *successor = child, *child2; tmp = child->rb_left; @@ -420,8 +437,9 @@ void rb_erase(struct rb_node *node, struct rb_root *root) * \ * (c) */ - parent = child; - child2 = child->rb_right; + parent = successor; + child2 = successor->rb_right; + augment->copy(node, successor); } else { /* Case 3: node's successor is leftmost under its * right child subtree @@ -444,6 +462,8 @@ void rb_erase(struct rb_node *node, struct rb_root *root) parent->rb_left = child2 = successor->rb_right; successor->rb_right = child; rb_set_parent(child, successor); + augment->copy(node, successor); + augment->propagate(parent, successor); } successor->rb_left = tmp = node->rb_left; @@ -461,13 +481,62 @@ void rb_erase(struct rb_node *node, struct rb_root *root) successor->__rb_parent_color = pc; rebalance = __rb_is_black(pc2) ? parent : NULL; } + tmp = successor; } + augment->propagate(tmp, NULL); if (rebalance) - __rb_erase_color(rebalance, root); + __rb_erase_color(rebalance, root, augment); +} + +/* + * Non-augmented rbtree manipulation functions. + * + * We use dummy augmented callbacks here, and have the compiler optimize them + * out of the rb_insert_color() and rb_erase() function definitions. + */ + +static inline void dummy_propagate(struct rb_node *node, struct rb_node *stop) {} +static inline void dummy_copy(struct rb_node *old, struct rb_node *new) {} +static inline void dummy_rotate(struct rb_node *old, struct rb_node *new) {} + +static const struct rb_augment_callbacks dummy_callbacks = { + dummy_propagate, dummy_copy, dummy_rotate +}; + +void rb_insert_color(struct rb_node *node, struct rb_root *root) +{ + __rb_insert(node, root, dummy_rotate); +} +EXPORT_SYMBOL(rb_insert_color); + +void rb_erase(struct rb_node *node, struct rb_root *root) +{ + __rb_erase(node, root, &dummy_callbacks); } EXPORT_SYMBOL(rb_erase); +/* + * Augmented rbtree manipulation functions. + * + * This instantiates the same __always_inline functions as in the non-augmented + * case, but this time with user-defined callbacks. + */ + +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); + static void rb_augment_path(struct rb_node *node, rb_augment_f func, void *data) { struct rb_node *parent; diff --git a/lib/rbtree_test.c b/lib/rbtree_test.c index 66e41d4..e28345d 100644 --- a/lib/rbtree_test.c +++ b/lib/rbtree_test.c @@ -61,35 +61,65 @@ static inline u32 augment_recompute(struct test_node *node) return max; } -static void augment_callback(struct rb_node *rb, void *unused) +static void augment_propagate(struct rb_node *rb, struct rb_node *stop) { - struct test_node *node = rb_entry(rb, struct test_node, rb); - node->augmented = augment_recompute(node); + 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 +}; + static void insert_augmented(struct test_node *node, struct rb_root *root) { - struct rb_node **new = &root->rb_node, *parent = NULL; + struct rb_node **new = &root->rb_node, *rb_parent = NULL; u32 key = node->key; + u32 val = node->val; + struct test_node *parent; while (*new) { - parent = *new; - if (key < rb_entry(parent, struct test_node, rb)->key) - new = &parent->rb_left; + rb_parent = *new; + parent = rb_entry(rb_parent, struct test_node, rb); + if (parent->augmented < val) + parent->augmented = val; + if (key < parent->key) + new = &parent->rb.rb_left; else - new = &parent->rb_right; + new = &parent->rb.rb_right; } - rb_link_node(&node->rb, parent, new); - rb_insert_color(&node->rb, root); - rb_augment_insert(&node->rb, augment_callback, NULL); + node->augmented = val; + rb_link_node(&node->rb, rb_parent, new); + rb_insert_augmented(&node->rb, root, &augment_callbacks); } 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); + rb_erase_augmented(&node->rb, root, &augment_callbacks); } static void init(void) -- 1.7.7.3 -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to majordomo@kvack.org. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: email@kvack.org From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from psmtp.com (na3sys010amx204.postini.com [74.125.245.204]) by kanga.kvack.org (Postfix) with SMTP id A6F1E6B0073 for ; Thu, 2 Aug 2012 18:34:45 -0400 (EDT) Received: by mail-yw0-f41.google.com with SMTP id 47so71180yhr.14 for ; Thu, 02 Aug 2012 15:34:45 -0700 (PDT) From: Michel Lespinasse Subject: [PATCH v2 9/9] rbtree: remove prior augmented rbtree implementation Date: Thu, 2 Aug 2012 15:34:18 -0700 Message-Id: <1343946858-8170-10-git-send-email-walken@google.com> In-Reply-To: <1343946858-8170-1-git-send-email-walken@google.com> References: <1343946858-8170-1-git-send-email-walken@google.com> Sender: owner-linux-mm@kvack.org List-ID: To: riel@redhat.com, peterz@infradead.org, daniel.santos@pobox.com, aarcange@redhat.com, dwmw2@infradead.org, akpm@linux-foundation.org Cc: linux-mm@kvack.org, linux-kernel@vger.kernel.org, torvalds@linux-foundation.org convert arch/x86/mm/pat_rbtree.c to the proposed augmented rbtree api and remove the old augmented rbtree implementation. Signed-off-by: Michel Lespinasse --- arch/x86/mm/pat_rbtree.c | 65 +++++++++++++++++++++++++++++------------ include/linux/rbtree.h | 8 ----- lib/rbtree.c | 71 ---------------------------------------------- 3 files changed, 46 insertions(+), 98 deletions(-) diff --git a/arch/x86/mm/pat_rbtree.c b/arch/x86/mm/pat_rbtree.c index 8acaddd..7e1515b 100644 --- a/arch/x86/mm/pat_rbtree.c +++ b/arch/x86/mm/pat_rbtree.c @@ -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; } diff --git a/include/linux/rbtree.h b/include/linux/rbtree.h index c902eb9..4ace31b 100644 --- a/include/linux/rbtree.h +++ b/include/linux/rbtree.h @@ -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 *); diff --git a/lib/rbtree.c b/lib/rbtree.c index 11c11e9..e45eed1 100644 --- a/lib/rbtree.c +++ b/lib/rbtree.c @@ -537,77 +537,6 @@ void rb_erase_augmented(struct rb_node *node, struct rb_root *root, } EXPORT_SYMBOL(rb_erase_augmented); -static void rb_augment_path(struct rb_node *node, rb_augment_f func, void *data) -{ - struct rb_node *parent; - -up: - func(node, data); - parent = rb_parent(node); - if (!parent) - return; - - if (node == parent->rb_left && parent->rb_right) - func(parent->rb_right, data); - else if (parent->rb_left) - func(parent->rb_left, data); - - node = parent; - goto up; -} - -/* - * after inserting @node into the tree, update the tree to account for - * both the new entry and any damage done by rebalance - */ -void rb_augment_insert(struct rb_node *node, rb_augment_f func, void *data) -{ - if (node->rb_left) - node = node->rb_left; - else if (node->rb_right) - node = node->rb_right; - - rb_augment_path(node, func, data); -} -EXPORT_SYMBOL(rb_augment_insert); - -/* - * before removing the node, find the deepest node on the rebalance path - * that will still be there after @node gets removed - */ -struct rb_node *rb_augment_erase_begin(struct rb_node *node) -{ - struct rb_node *deepest; - - if (!node->rb_right && !node->rb_left) - deepest = rb_parent(node); - else if (!node->rb_right) - deepest = node->rb_left; - else if (!node->rb_left) - deepest = node->rb_right; - else { - deepest = rb_next(node); - if (deepest->rb_right) - deepest = deepest->rb_right; - else if (rb_parent(deepest) != node) - deepest = rb_parent(deepest); - } - - return deepest; -} -EXPORT_SYMBOL(rb_augment_erase_begin); - -/* - * after removal, update the tree to account for the removed entry - * and any rebalance damage. - */ -void rb_augment_erase_end(struct rb_node *node, rb_augment_f func, void *data) -{ - if (node) - rb_augment_path(node, func, data); -} -EXPORT_SYMBOL(rb_augment_erase_end); - /* * This function returns the first node (in sort order) of the tree. */ -- 1.7.7.3 -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to majordomo@kvack.org. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: email@kvack.org From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from psmtp.com (na3sys010amx181.postini.com [74.125.245.181]) by kanga.kvack.org (Postfix) with SMTP id D8C7C6B0068 for ; Thu, 2 Aug 2012 18:41:14 -0400 (EDT) Message-ID: <1343947273.10710.4.camel@joe2Laptop> Subject: Re: [PATCH v2 9/9] rbtree: remove prior augmented rbtree implementation From: Joe Perches Date: Thu, 02 Aug 2012 15:41:13 -0700 In-Reply-To: <1343946858-8170-10-git-send-email-walken@google.com> References: <1343946858-8170-1-git-send-email-walken@google.com> <1343946858-8170-10-git-send-email-walken@google.com> Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: 7bit Mime-Version: 1.0 Sender: owner-linux-mm@kvack.org List-ID: To: Michel Lespinasse Cc: riel@redhat.com, peterz@infradead.org, daniel.santos@pobox.com, aarcange@redhat.com, dwmw2@infradead.org, akpm@linux-foundation.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org, torvalds@linux-foundation.org On Thu, 2012-08-02 at 15:34 -0700, Michel Lespinasse wrote: > convert arch/x86/mm/pat_rbtree.c to the proposed augmented rbtree api > and remove the old augmented rbtree implementation. style trivia: > +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); 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 majordomo@kvack.org. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: email@kvack.org From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from psmtp.com (na3sys010amx187.postini.com [74.125.245.187]) by kanga.kvack.org (Postfix) with SMTP id 1025F6B0044 for ; Sun, 5 Aug 2012 16:47:43 -0400 (EDT) Message-ID: <501EDBCD.6030208@redhat.com> Date: Sun, 05 Aug 2012 16:47:09 -0400 From: Rik van Riel MIME-Version: 1.0 Subject: Re: [PATCH v2 1/9] rbtree test: fix sparse warning about 64-bit constant References: <1343946858-8170-1-git-send-email-walken@google.com> <1343946858-8170-2-git-send-email-walken@google.com> In-Reply-To: <1343946858-8170-2-git-send-email-walken@google.com> Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit Sender: owner-linux-mm@kvack.org List-ID: To: Michel Lespinasse Cc: peterz@infradead.org, daniel.santos@pobox.com, aarcange@redhat.com, dwmw2@infradead.org, akpm@linux-foundation.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org, torvalds@linux-foundation.org On 08/02/2012 06:34 PM, Michel Lespinasse wrote: > Just a small fix to make sparse happy. > > Signed-off-by: Michel Lespinasse > Reported-by: Fengguang Wu Acked-by: Rik van Riel -- All rights reversed -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to majordomo@kvack.org. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: email@kvack.org From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from psmtp.com (na3sys010amx170.postini.com [74.125.245.170]) by kanga.kvack.org (Postfix) with SMTP id F0D7D6B0044 for ; Sun, 5 Aug 2012 19:21:03 -0400 (EDT) Message-ID: <501EFFC2.6090700@redhat.com> Date: Sun, 05 Aug 2012 19:20:34 -0400 From: Rik van Riel MIME-Version: 1.0 Subject: Re: [PATCH v2 2/9] rbtree: optimize fetching of sibling node References: <1343946858-8170-1-git-send-email-walken@google.com> <1343946858-8170-3-git-send-email-walken@google.com> In-Reply-To: <1343946858-8170-3-git-send-email-walken@google.com> Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit Sender: owner-linux-mm@kvack.org List-ID: To: Michel Lespinasse Cc: peterz@infradead.org, daniel.santos@pobox.com, aarcange@redhat.com, dwmw2@infradead.org, akpm@linux-foundation.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org, torvalds@linux-foundation.org On 08/02/2012 06:34 PM, Michel Lespinasse wrote: > When looking to fetch a node's sibling, we went through a sequence of: > - check if node is the parent's left child > - if it is, then fetch the parent's right child > > This can be replaced with: > - fetch the parent's right child as an assumed sibling > - check that node is NOT the fetched child > > This avoids fetching the parent's left child when node is actually > that child. Saves a bit on code size, though it doesn't seem to make > a large difference in speed. > > Signed-off-by: Michel Lespinasse Acked-by: Rik van Riel -- All rights reversed -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to majordomo@kvack.org. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: email@kvack.org From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from psmtp.com (na3sys010amx177.postini.com [74.125.245.177]) by kanga.kvack.org (Postfix) with SMTP id 6D2616B005A for ; Sun, 5 Aug 2012 21:01:09 -0400 (EDT) Message-ID: <501F171F.50001@redhat.com> Date: Sun, 05 Aug 2012 21:00:15 -0400 From: Rik van Riel MIME-Version: 1.0 Subject: Re: [PATCH v2 3/9] rbtree: add __rb_change_child() helper function References: <1343946858-8170-1-git-send-email-walken@google.com> <1343946858-8170-4-git-send-email-walken@google.com> In-Reply-To: <1343946858-8170-4-git-send-email-walken@google.com> Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit Sender: owner-linux-mm@kvack.org List-ID: To: Michel Lespinasse Cc: peterz@infradead.org, daniel.santos@pobox.com, aarcange@redhat.com, dwmw2@infradead.org, akpm@linux-foundation.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org, torvalds@linux-foundation.org On 08/02/2012 06:34 PM, Michel Lespinasse wrote: > 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 Reviewed-by: Rik van Riel -- All rights reversed -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to majordomo@kvack.org. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: email@kvack.org From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from psmtp.com (na3sys010amx169.postini.com [74.125.245.169]) by kanga.kvack.org (Postfix) with SMTP id 48A826B0044 for ; Sun, 5 Aug 2012 21:13:36 -0400 (EDT) Message-ID: <501F1A24.60505@redhat.com> Date: Sun, 05 Aug 2012 21:13:08 -0400 From: Rik van Riel MIME-Version: 1.0 Subject: Re: [PATCH v2 4/9] rbtree: place easiest case first in rb_erase() References: <1343946858-8170-1-git-send-email-walken@google.com> <1343946858-8170-5-git-send-email-walken@google.com> In-Reply-To: <1343946858-8170-5-git-send-email-walken@google.com> Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit Sender: owner-linux-mm@kvack.org List-ID: To: Michel Lespinasse Cc: peterz@infradead.org, daniel.santos@pobox.com, aarcange@redhat.com, dwmw2@infradead.org, akpm@linux-foundation.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org, torvalds@linux-foundation.org On 08/02/2012 06:34 PM, Michel Lespinasse wrote: > 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 Reviewed-by: Rik van Riel -- All rights reversed -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to majordomo@kvack.org. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: email@kvack.org From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from psmtp.com (na3sys010amx174.postini.com [74.125.245.174]) by kanga.kvack.org (Postfix) with SMTP id AA9236B0044 for ; Sun, 5 Aug 2012 21:28:01 -0400 (EDT) Message-ID: <501F1D86.7020409@redhat.com> Date: Sun, 05 Aug 2012 21:27:34 -0400 From: Rik van Riel MIME-Version: 1.0 Subject: Re: [PATCH v2 5/9] rbtree: handle 1-child recoloring in rb_erase() instead of rb_erase_color() References: <1343946858-8170-1-git-send-email-walken@google.com> <1343946858-8170-6-git-send-email-walken@google.com> In-Reply-To: <1343946858-8170-6-git-send-email-walken@google.com> Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit Sender: owner-linux-mm@kvack.org List-ID: To: Michel Lespinasse Cc: peterz@infradead.org, daniel.santos@pobox.com, aarcange@redhat.com, dwmw2@infradead.org, akpm@linux-foundation.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org, torvalds@linux-foundation.org On 08/02/2012 06:34 PM, Michel Lespinasse wrote: > An interesting observation for rb_erase() is that when a node has > exactly one child, the node must be black and the child must be red. > An interesting consequence is that removing such a node can be done by > simply replacing it with its child and making the child black, > which we can do efficiently in rb_erase(). __rb_erase_color() then > only needs to handle the no-childs case and can be modified accordingly. > > Signed-off-by: Michel Lespinasse Acked-by: Rik van Riel -- All rights reversed -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to majordomo@kvack.org. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: email@kvack.org From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from psmtp.com (na3sys010amx201.postini.com [74.125.245.201]) by kanga.kvack.org (Postfix) with SMTP id 6BF5E6B005A for ; Sun, 5 Aug 2012 22:12:36 -0400 (EDT) Message-ID: <501F27D0.6020803@redhat.com> Date: Sun, 05 Aug 2012 22:11:28 -0400 From: Rik van Riel MIME-Version: 1.0 Subject: Re: [PATCH v2 7/9] rbtree: augmented rbtree test References: <1343946858-8170-1-git-send-email-walken@google.com> <1343946858-8170-8-git-send-email-walken@google.com> In-Reply-To: <1343946858-8170-8-git-send-email-walken@google.com> Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit Sender: owner-linux-mm@kvack.org List-ID: To: Michel Lespinasse Cc: peterz@infradead.org, daniel.santos@pobox.com, aarcange@redhat.com, dwmw2@infradead.org, akpm@linux-foundation.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org, torvalds@linux-foundation.org On 08/02/2012 06:34 PM, Michel Lespinasse wrote: > Small test to measure the performance of augmented rbtrees. > > Signed-off-by: Michel Lespinasse Acked-by: Rik van Riel -- All rights reversed -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to majordomo@kvack.org. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: email@kvack.org From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from psmtp.com (na3sys010amx124.postini.com [74.125.245.124]) by kanga.kvack.org (Postfix) with SMTP id B6FA56B0044 for ; Sun, 5 Aug 2012 22:13:00 -0400 (EDT) Message-ID: <501F2812.70303@redhat.com> Date: Sun, 05 Aug 2012 22:12:34 -0400 From: Rik van Riel MIME-Version: 1.0 Subject: Re: [PATCH v2 8/9] rbtree: faster augmented rbtree manipulation References: <1343946858-8170-1-git-send-email-walken@google.com> <1343946858-8170-9-git-send-email-walken@google.com> In-Reply-To: <1343946858-8170-9-git-send-email-walken@google.com> Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit Sender: owner-linux-mm@kvack.org List-ID: To: Michel Lespinasse Cc: peterz@infradead.org, daniel.santos@pobox.com, aarcange@redhat.com, dwmw2@infradead.org, akpm@linux-foundation.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org, torvalds@linux-foundation.org On 08/02/2012 06:34 PM, Michel Lespinasse wrote: > 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. > > 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(). > > Signed-off-by: Michel Lespinasse Acked-by: Rik van Riel -- All rights reversed -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to majordomo@kvack.org. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: email@kvack.org From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from psmtp.com (na3sys010amx171.postini.com [74.125.245.171]) by kanga.kvack.org (Postfix) with SMTP id 3C8746B005D for ; Sun, 5 Aug 2012 22:13:26 -0400 (EDT) Message-ID: <501F282C.6010600@redhat.com> Date: Sun, 05 Aug 2012 22:13:00 -0400 From: Rik van Riel MIME-Version: 1.0 Subject: Re: [PATCH v2 9/9] rbtree: remove prior augmented rbtree implementation References: <1343946858-8170-1-git-send-email-walken@google.com> <1343946858-8170-10-git-send-email-walken@google.com> In-Reply-To: <1343946858-8170-10-git-send-email-walken@google.com> Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit Sender: owner-linux-mm@kvack.org List-ID: To: Michel Lespinasse Cc: peterz@infradead.org, daniel.santos@pobox.com, aarcange@redhat.com, dwmw2@infradead.org, akpm@linux-foundation.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org, torvalds@linux-foundation.org On 08/02/2012 06:34 PM, Michel Lespinasse wrote: > convert arch/x86/mm/pat_rbtree.c to the proposed augmented rbtree api > and remove the old augmented rbtree implementation. > > Signed-off-by: Michel Lespinasse Acked-by: Rik van Riel -- All rights reversed -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to majordomo@kvack.org. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: email@kvack.org From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from psmtp.com (na3sys010amx107.postini.com [74.125.245.107]) by kanga.kvack.org (Postfix) with SMTP id 234536B0044 for ; Sun, 5 Aug 2012 22:15:35 -0400 (EDT) Message-ID: <501F20BC.2030107@redhat.com> Date: Sun, 05 Aug 2012 21:41:16 -0400 From: Rik van Riel MIME-Version: 1.0 Subject: Re: [PATCH v2 6/9] rbtree: low level optimizations in rb_erase() References: <1343946858-8170-1-git-send-email-walken@google.com> <1343946858-8170-7-git-send-email-walken@google.com> In-Reply-To: <1343946858-8170-7-git-send-email-walken@google.com> Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit Sender: owner-linux-mm@kvack.org List-ID: To: Michel Lespinasse Cc: peterz@infradead.org, daniel.santos@pobox.com, aarcange@redhat.com, dwmw2@infradead.org, akpm@linux-foundation.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org, torvalds@linux-foundation.org On 08/02/2012 06:34 PM, Michel Lespinasse wrote: > Various minor optimizations in rb_erase(): > - Avoid multiple loading of node->__rb_parent_color when computing parent > and color information (possibly not in close sequence, as there might > be further branches in the algorithm) > - In the 1-child subcase of case 1, copy the __rb_parent_color field from > the erased node to the child instead of recomputing it from the desired > parent and color > - When searching for the erased node's successor, differentiate between > cases 2 and 3 based on whether any left links were followed. This avoids > a condition later down. > - In case 3, keep a pointer to the erased node's right child so we don't > have to refetch it later to adjust its parent. > - In the no-childs subcase of cases 2 and 3, place the rebalance assigment > last so that the compiler can remove the following if(rebalance) test. > > Also, added some comments to illustrate cases 2 and 3. > > Signed-off-by: Michel Lespinasse Acked-by: Rik van Riel -- All rights reversed -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to majordomo@kvack.org. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: email@kvack.org From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from psmtp.com (na3sys010amx179.postini.com [74.125.245.179]) by kanga.kvack.org (Postfix) with SMTP id 588926B0044 for ; Mon, 6 Aug 2012 10:18:00 -0400 (EDT) Message-ID: <1344262669.27828.55.camel@twins> Subject: Re: [PATCH v2 8/9] rbtree: faster augmented rbtree manipulation From: Peter Zijlstra Date: Mon, 06 Aug 2012 16:17:49 +0200 In-Reply-To: <1343946858-8170-9-git-send-email-walken@google.com> References: <1343946858-8170-1-git-send-email-walken@google.com> <1343946858-8170-9-git-send-email-walken@google.com> Content-Type: text/plain; charset="ISO-8859-1" Content-Transfer-Encoding: quoted-printable Mime-Version: 1.0 Sender: owner-linux-mm@kvack.org List-ID: To: Michel Lespinasse Cc: riel@redhat.com, daniel.santos@pobox.com, aarcange@redhat.com, dwmw2@infradead.org, akpm@linux-foundation.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org, torvalds@linux-foundation.org On Thu, 2012-08-02 at 15:34 -0700, Michel Lespinasse wrote: > +static void augment_propagate(struct rb_node *rb, struct rb_node *stop) > +{ > + while (rb !=3D stop) { > + struct interval_tree_node *node =3D > + rb_entry(rb, struct interval_tree_node, rb); > + unsigned long subtree_last =3D compute_subtree_last(node)= ; > + if (node->__subtree_last =3D=3D subtree_last) > + break; > + node->__subtree_last =3D subtree_last; > + rb =3D rb_parent(&node->rb); > + } > +} > + > +static void augment_copy(struct rb_node *rb_old, struct rb_node *rb_new) > +{ > + struct interval_tree_node *old =3D > + rb_entry(rb_old, struct interval_tree_node, rb); > + struct interval_tree_node *new =3D > + rb_entry(rb_new, struct interval_tree_node, rb); > + > + new->__subtree_last =3D old->__subtree_last; > +} > + > +static void augment_rotate(struct rb_node *rb_old, struct rb_node *rb_ne= w) > +{ > + struct interval_tree_node *old =3D > + rb_entry(rb_old, struct interval_tree_node, rb); > + struct interval_tree_node *new =3D > + rb_entry(rb_new, struct interval_tree_node, rb); > + > + new->__subtree_last =3D old->__subtree_last; > + old->__subtree_last =3D compute_subtree_last(old); > +}=20 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 majordomo@kvack.org. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: email@kvack.org From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from psmtp.com (na3sys010amx193.postini.com [74.125.245.193]) by kanga.kvack.org (Postfix) with SMTP id 7BA796B005A for ; Mon, 6 Aug 2012 10:21:09 -0400 (EDT) Message-ID: <1344262863.27828.56.camel@twins> Subject: Re: [PATCH v2 6/9] rbtree: low level optimizations in rb_erase() From: Peter Zijlstra Date: Mon, 06 Aug 2012 16:21:03 +0200 In-Reply-To: <1343946858-8170-7-git-send-email-walken@google.com> References: <1343946858-8170-1-git-send-email-walken@google.com> <1343946858-8170-7-git-send-email-walken@google.com> Content-Type: text/plain; charset="ISO-8859-1" Content-Transfer-Encoding: quoted-printable Mime-Version: 1.0 Sender: owner-linux-mm@kvack.org List-ID: To: Michel Lespinasse Cc: riel@redhat.com, daniel.santos@pobox.com, aarcange@redhat.com, dwmw2@infradead.org, akpm@linux-foundation.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org, torvalds@linux-foundation.org On Thu, 2012-08-02 at 15:34 -0700, Michel Lespinasse wrote: > + /* > + * 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 majordomo@kvack.org. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: email@kvack.org From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from psmtp.com (na3sys010amx159.postini.com [74.125.245.159]) by kanga.kvack.org (Postfix) with SMTP id 1FBF46B005A for ; Mon, 6 Aug 2012 10:22:23 -0400 (EDT) Message-ID: <1344262930.27828.57.camel@twins> Subject: Re: [PATCH v2 3/9] rbtree: add __rb_change_child() helper function From: Peter Zijlstra Date: Mon, 06 Aug 2012 16:22:10 +0200 In-Reply-To: <1343946858-8170-4-git-send-email-walken@google.com> References: <1343946858-8170-1-git-send-email-walken@google.com> <1343946858-8170-4-git-send-email-walken@google.com> Content-Type: text/plain; charset="ISO-8859-1" Content-Transfer-Encoding: quoted-printable Mime-Version: 1.0 Sender: owner-linux-mm@kvack.org List-ID: To: Michel Lespinasse Cc: riel@redhat.com, daniel.santos@pobox.com, aarcange@redhat.com, dwmw2@infradead.org, akpm@linux-foundation.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org, torvalds@linux-foundation.org On Thu, 2012-08-02 at 15:34 -0700, Michel Lespinasse wrote: > +static inline void I would make that __always_inline, just to make sure GCC doesn't go creative on us. > +__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 =3D=3D old) > + parent->rb_left =3D new; > + else > + parent->rb_right =3D new; > + } else > + root->rb_node =3D new; > +}=20 -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to majordomo@kvack.org. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: email@kvack.org From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from psmtp.com (na3sys010amx176.postini.com [74.125.245.176]) by kanga.kvack.org (Postfix) with SMTP id 28E846B005A for ; Mon, 6 Aug 2012 10:23:42 -0400 (EDT) Message-ID: <1344263015.27828.58.camel@twins> Subject: Re: [PATCH v2 2/9] rbtree: optimize fetching of sibling node From: Peter Zijlstra Date: Mon, 06 Aug 2012 16:23:35 +0200 In-Reply-To: <1343946858-8170-3-git-send-email-walken@google.com> References: <1343946858-8170-1-git-send-email-walken@google.com> <1343946858-8170-3-git-send-email-walken@google.com> Content-Type: text/plain; charset="ISO-8859-1" Content-Transfer-Encoding: quoted-printable Mime-Version: 1.0 Sender: owner-linux-mm@kvack.org List-ID: To: Michel Lespinasse Cc: riel@redhat.com, daniel.santos@pobox.com, aarcange@redhat.com, dwmw2@infradead.org, akpm@linux-foundation.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org, torvalds@linux-foundation.org On Thu, 2012-08-02 at 15:34 -0700, Michel Lespinasse wrote: > + tmp =3D gparent->rb_right; > + if (parent !=3D tmp) { /* parent =3D=3D gparent->rb_left */ > + tmp =3D parent->rb_right; > + if (node =3D=3D tmp) { > + tmp =3D parent->rb_left; > + if (node =3D=3D tmp) { > + sibling =3D parent->rb_right; > + if (node !=3D sibling) { /* node =3D=3D 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 majordomo@kvack.org. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: email@kvack.org From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from psmtp.com (na3sys010amx115.postini.com [74.125.245.115]) by kanga.kvack.org (Postfix) with SMTP id E82956B0044 for ; Mon, 6 Aug 2012 10:25:49 -0400 (EDT) Message-ID: <1344263140.27828.59.camel@twins> Subject: Re: [PATCH v2 8/9] rbtree: faster augmented rbtree manipulation From: Peter Zijlstra Date: Mon, 06 Aug 2012 16:25:40 +0200 In-Reply-To: <1343946858-8170-9-git-send-email-walken@google.com> References: <1343946858-8170-1-git-send-email-walken@google.com> <1343946858-8170-9-git-send-email-walken@google.com> Content-Type: text/plain; charset="ISO-8859-1" Content-Transfer-Encoding: quoted-printable Mime-Version: 1.0 Sender: owner-linux-mm@kvack.org List-ID: To: Michel Lespinasse Cc: riel@redhat.com, daniel.santos@pobox.com, aarcange@redhat.com, dwmw2@infradead.org, akpm@linux-foundation.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org, torvalds@linux-foundation.org On Thu, 2012-08-02 at 15:34 -0700, Michel Lespinasse wrote: > +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); > +};=20 Should we make that const pointers? Daniel? -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to majordomo@kvack.org. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: email@kvack.org From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from psmtp.com (na3sys010amx177.postini.com [74.125.245.177]) by kanga.kvack.org (Postfix) with SMTP id 9275D6B0044 for ; Mon, 6 Aug 2012 10:29:34 -0400 (EDT) Message-ID: <1344263368.27828.60.camel@twins> Subject: Re: [PATCH v2 8/9] rbtree: faster augmented rbtree manipulation From: Peter Zijlstra Date: Mon, 06 Aug 2012 16:29:28 +0200 In-Reply-To: <1343946858-8170-9-git-send-email-walken@google.com> References: <1343946858-8170-1-git-send-email-walken@google.com> <1343946858-8170-9-git-send-email-walken@google.com> Content-Type: text/plain; charset="ISO-8859-1" Content-Transfer-Encoding: quoted-printable Mime-Version: 1.0 Sender: owner-linux-mm@kvack.org List-ID: To: Michel Lespinasse Cc: riel@redhat.com, daniel.santos@pobox.com, aarcange@redhat.com, dwmw2@infradead.org, akpm@linux-foundation.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org, torvalds@linux-foundation.org On Thu, 2012-08-02 at 15:34 -0700, Michel Lespinasse wrote: > +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);=20 =46rom 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 majordomo@kvack.org. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: email@kvack.org From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from psmtp.com (na3sys010amx169.postini.com [74.125.245.169]) by kanga.kvack.org (Postfix) with SMTP id 0D39D6B0044 for ; Mon, 6 Aug 2012 11:39:04 -0400 (EDT) Message-ID: <1344267537.27828.93.camel@twins> Subject: Re: [PATCH v2 8/9] rbtree: faster augmented rbtree manipulation From: Peter Zijlstra Date: Mon, 06 Aug 2012 17:38:57 +0200 In-Reply-To: <1344262669.27828.55.camel@twins> References: <1343946858-8170-1-git-send-email-walken@google.com> <1343946858-8170-9-git-send-email-walken@google.com> <1344262669.27828.55.camel@twins> Content-Type: text/plain; charset="ISO-8859-1" Content-Transfer-Encoding: quoted-printable Mime-Version: 1.0 Sender: owner-linux-mm@kvack.org List-ID: To: Michel Lespinasse Cc: riel@redhat.com, daniel.santos@pobox.com, aarcange@redhat.com, dwmw2@infradead.org, akpm@linux-foundation.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org, torvalds@linux-foundation.org On Mon, 2012-08-06 at 16:17 +0200, Peter Zijlstra wrote: > 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 =3D _update, \ .offset =3D offsetof(_type, _aug_member) - \ offsetof(_type, _rb_member), \ .size =3D sizeof(((_type *)NULL)->_aug_member), \ } static __always_inline void=20 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); }=20 static __always_inline void=20 augment_propagate(struct rb_node *rb, struct rb_node *stop, const struct rb_augment_callback *ac) { while (rb !=3D stop) { if (!ac->update(rb)) break; rb =3D 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 majordomo@kvack.org. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: email@kvack.org From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from psmtp.com (na3sys010amx178.postini.com [74.125.245.178]) by kanga.kvack.org (Postfix) with SMTP id 79D426B004D for ; Mon, 6 Aug 2012 16:46:14 -0400 (EDT) Received: by yhr47 with SMTP id 47so3585522yhr.14 for ; Mon, 06 Aug 2012 13:46:13 -0700 (PDT) MIME-Version: 1.0 In-Reply-To: <1344263015.27828.58.camel@twins> References: <1343946858-8170-1-git-send-email-walken@google.com> <1343946858-8170-3-git-send-email-walken@google.com> <1344263015.27828.58.camel@twins> Date: Mon, 6 Aug 2012 13:46:12 -0700 Message-ID: Subject: Re: [PATCH v2 2/9] rbtree: optimize fetching of sibling node From: Michel Lespinasse Content-Type: text/plain; charset=ISO-8859-1 Sender: owner-linux-mm@kvack.org List-ID: To: Peter Zijlstra Cc: riel@redhat.com, daniel.santos@pobox.com, aarcange@redhat.com, dwmw2@infradead.org, akpm@linux-foundation.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org, torvalds@linux-foundation.org On Mon, Aug 6, 2012 at 7:23 AM, Peter Zijlstra wrote: > On Thu, 2012-08-02 at 15:34 -0700, Michel Lespinasse wrote: > >> + 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? 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. -- Michel "Walken" Lespinasse A program is never fully debugged until the last user dies. -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to majordomo@kvack.org. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: email@kvack.org From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from psmtp.com (na3sys010amx181.postini.com [74.125.245.181]) by kanga.kvack.org (Postfix) with SMTP id 351346B0062 for ; Mon, 6 Aug 2012 16:50:04 -0400 (EDT) Received: by ggnf4 with SMTP id f4so876363ggn.14 for ; Mon, 06 Aug 2012 13:50:03 -0700 (PDT) MIME-Version: 1.0 In-Reply-To: <1344262863.27828.56.camel@twins> References: <1343946858-8170-1-git-send-email-walken@google.com> <1343946858-8170-7-git-send-email-walken@google.com> <1344262863.27828.56.camel@twins> Date: Mon, 6 Aug 2012 13:50:02 -0700 Message-ID: Subject: Re: [PATCH v2 6/9] rbtree: low level optimizations in rb_erase() From: Michel Lespinasse Content-Type: text/plain; charset=ISO-8859-1 Sender: owner-linux-mm@kvack.org List-ID: To: Peter Zijlstra Cc: riel@redhat.com, daniel.santos@pobox.com, aarcange@redhat.com, dwmw2@infradead.org, akpm@linux-foundation.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org, torvalds@linux-foundation.org On Mon, Aug 6, 2012 at 7:21 AM, Peter Zijlstra wrote: > On Thu, 2012-08-02 at 15:34 -0700, Michel Lespinasse wrote: >> + /* Case 3: node's successor is leftmost under its >> + * right child subtree > > Hmm? Would 'leftmost under node's right child subtree' make more sense ? -- Michel "Walken" Lespinasse A program is never fully debugged until the last user dies. -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to majordomo@kvack.org. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: email@kvack.org From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from psmtp.com (na3sys010amx193.postini.com [74.125.245.193]) by kanga.kvack.org (Postfix) with SMTP id D9CEF6B0069 for ; Mon, 6 Aug 2012 16:58:27 -0400 (EDT) Message-ID: <1344286699.27828.115.camel@twins> Subject: Re: [PATCH v2 6/9] rbtree: low level optimizations in rb_erase() From: Peter Zijlstra Date: Mon, 06 Aug 2012 22:58:19 +0200 In-Reply-To: References: <1343946858-8170-1-git-send-email-walken@google.com> <1343946858-8170-7-git-send-email-walken@google.com> <1344262863.27828.56.camel@twins> Content-Type: text/plain; charset="ISO-8859-1" Content-Transfer-Encoding: quoted-printable Mime-Version: 1.0 Sender: owner-linux-mm@kvack.org List-ID: To: Michel Lespinasse Cc: riel@redhat.com, daniel.santos@pobox.com, aarcange@redhat.com, dwmw2@infradead.org, akpm@linux-foundation.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org, torvalds@linux-foundation.org On Mon, 2012-08-06 at 13:50 -0700, Michel Lespinasse wrote: > On Mon, Aug 6, 2012 at 7:21 AM, Peter Zijlstra wro= te: > > On Thu, 2012-08-02 at 15:34 -0700, Michel Lespinasse wrote: > >> + /* Case 3: node's successor is leftmost under = its > >> + * right child subtree > > > > Hmm? >=20 > 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 majordomo@kvack.org. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: email@kvack.org From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from psmtp.com (na3sys010amx178.postini.com [74.125.245.178]) by kanga.kvack.org (Postfix) with SMTP id 9B51C6B0071 for ; Mon, 6 Aug 2012 17:20:15 -0400 (EDT) Received: by ggnf4 with SMTP id f4so910584ggn.14 for ; Mon, 06 Aug 2012 14:20:14 -0700 (PDT) MIME-Version: 1.0 In-Reply-To: <1344286699.27828.115.camel@twins> References: <1343946858-8170-1-git-send-email-walken@google.com> <1343946858-8170-7-git-send-email-walken@google.com> <1344262863.27828.56.camel@twins> <1344286699.27828.115.camel@twins> Date: Mon, 6 Aug 2012 14:20:14 -0700 Message-ID: Subject: Re: [PATCH v2 6/9] rbtree: low level optimizations in rb_erase() From: Michel Lespinasse Content-Type: text/plain; charset=ISO-8859-1 Sender: owner-linux-mm@kvack.org List-ID: To: Peter Zijlstra Cc: riel@redhat.com, daniel.santos@pobox.com, aarcange@redhat.com, dwmw2@infradead.org, akpm@linux-foundation.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org, torvalds@linux-foundation.org On Mon, Aug 6, 2012 at 1:58 PM, Peter Zijlstra wrote: > On Mon, 2012-08-06 at 13:50 -0700, Michel Lespinasse wrote: >> On Mon, Aug 6, 2012 at 7:21 AM, Peter Zijlstra wrote: >> > On Thu, 2012-08-02 at 15:34 -0700, Michel Lespinasse wrote: >> >> + /* 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: .... Gah, failed to notice that. Sending new patch (just the comment changed) as a reply. -- Michel "Walken" Lespinasse A program is never fully debugged until the last user dies. -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to majordomo@kvack.org. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: email@kvack.org From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from psmtp.com (na3sys010amx172.postini.com [74.125.245.172]) by kanga.kvack.org (Postfix) with SMTP id 8DD7B6B0074 for ; Mon, 6 Aug 2012 17:21:55 -0400 (EDT) Received: by pbbjt11 with SMTP id jt11so3116623pbb.14 for ; Mon, 06 Aug 2012 14:21:54 -0700 (PDT) Date: Mon, 6 Aug 2012 14:21:51 -0700 From: Michel Lespinasse Subject: Re: [PATCH v2 6/9] rbtree: low level optimizations in rb_erase() Message-ID: <20120806212151.GA26876@google.com> References: <1343946858-8170-1-git-send-email-walken@google.com> <1343946858-8170-7-git-send-email-walken@google.com> <1344262863.27828.56.camel@twins> <1344286699.27828.115.camel@twins> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: Sender: owner-linux-mm@kvack.org List-ID: To: Peter Zijlstra Cc: riel@redhat.com, daniel.santos@pobox.com, aarcange@redhat.com, dwmw2@infradead.org, akpm@linux-foundation.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org, torvalds@linux-foundation.org Various minor optimizations in rb_erase(): - Avoid multiple loading of node->__rb_parent_color when computing parent and color information (possibly not in close sequence, as there might be further branches in the algorithm) - In the 1-child subcase of case 1, copy the __rb_parent_color field from the erased node to the child instead of recomputing it from the desired parent and color - When searching for the erased node's successor, differentiate between cases 2 and 3 based on whether any left links were followed. This avoids a condition later down. - In case 3, keep a pointer to the erased node's right child so we don't have to refetch it later to adjust its parent. - In the no-childs subcase of cases 2 and 3, place the rebalance assigment last so that the compiler can remove the following if(rebalance) test. Also, added some comments to illustrate cases 2 and 3. Signed-off-by: Michel Lespinasse --- lib/rbtree.c | 98 ++++++++++++++++++++++++++++++++++++++-------------------- 1 files changed, 64 insertions(+), 34 deletions(-) diff --git a/lib/rbtree.c b/lib/rbtree.c index 80b0925..938061e 100644 --- a/lib/rbtree.c +++ b/lib/rbtree.c @@ -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) -- 1.7.7.3 -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to majordomo@kvack.org. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: email@kvack.org From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from psmtp.com (na3sys010amx173.postini.com [74.125.245.173]) by kanga.kvack.org (Postfix) with SMTP id 5FD836B0069 for ; Mon, 6 Aug 2012 17:34:28 -0400 (EDT) Received: by ggnf4 with SMTP id f4so925028ggn.14 for ; Mon, 06 Aug 2012 14:34:27 -0700 (PDT) MIME-Version: 1.0 In-Reply-To: <1344263140.27828.59.camel@twins> References: <1343946858-8170-1-git-send-email-walken@google.com> <1343946858-8170-9-git-send-email-walken@google.com> <1344263140.27828.59.camel@twins> Date: Mon, 6 Aug 2012 14:34:26 -0700 Message-ID: Subject: Re: [PATCH v2 8/9] rbtree: faster augmented rbtree manipulation From: Michel Lespinasse Content-Type: text/plain; charset=ISO-8859-1 Sender: owner-linux-mm@kvack.org List-ID: To: Peter Zijlstra Cc: riel@redhat.com, daniel.santos@pobox.com, aarcange@redhat.com, dwmw2@infradead.org, akpm@linux-foundation.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org, torvalds@linux-foundation.org On Mon, Aug 6, 2012 at 7:25 AM, Peter Zijlstra wrote: > On Thu, 2012-08-02 at 15:34 -0700, Michel Lespinasse wrote: >> +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. -- Michel "Walken" Lespinasse A program is never fully debugged until the last user dies. -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to majordomo@kvack.org. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: email@kvack.org From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from psmtp.com (na3sys010amx164.postini.com [74.125.245.164]) by kanga.kvack.org (Postfix) with SMTP id 91CA16B0069 for ; Mon, 6 Aug 2012 17:36:31 -0400 (EDT) Message-ID: <1344288982.27828.116.camel@twins> Subject: Re: [PATCH v2 8/9] rbtree: faster augmented rbtree manipulation From: Peter Zijlstra Date: Mon, 06 Aug 2012 23:36:22 +0200 In-Reply-To: References: <1343946858-8170-1-git-send-email-walken@google.com> <1343946858-8170-9-git-send-email-walken@google.com> <1344263140.27828.59.camel@twins> Content-Type: text/plain; charset="ISO-8859-1" Content-Transfer-Encoding: quoted-printable Mime-Version: 1.0 Sender: owner-linux-mm@kvack.org List-ID: To: Michel Lespinasse Cc: riel@redhat.com, daniel.santos@pobox.com, aarcange@redhat.com, dwmw2@infradead.org, akpm@linux-foundation.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org, torvalds@linux-foundation.org On Mon, 2012-08-06 at 14:34 -0700, Michel Lespinasse wrote: > On Mon, Aug 6, 2012 at 7:25 AM, Peter Zijlstra wro= te: > > On Thu, 2012-08-02 at 15:34 -0700, Michel Lespinasse wrote: > >> +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? >=20 > 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 majordomo@kvack.org. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: email@kvack.org From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from psmtp.com (na3sys010amx121.postini.com [74.125.245.121]) by kanga.kvack.org (Postfix) with SMTP id A567C6B0069 for ; Mon, 6 Aug 2012 17:38:35 -0400 (EDT) Received: by yenr5 with SMTP id r5so3640224yen.14 for ; Mon, 06 Aug 2012 14:38:34 -0700 (PDT) MIME-Version: 1.0 In-Reply-To: <1344263368.27828.60.camel@twins> References: <1343946858-8170-1-git-send-email-walken@google.com> <1343946858-8170-9-git-send-email-walken@google.com> <1344263368.27828.60.camel@twins> Date: Mon, 6 Aug 2012 14:38:33 -0700 Message-ID: Subject: Re: [PATCH v2 8/9] rbtree: faster augmented rbtree manipulation From: Michel Lespinasse Content-Type: text/plain; charset=ISO-8859-1 Sender: owner-linux-mm@kvack.org List-ID: To: Peter Zijlstra Cc: riel@redhat.com, daniel.santos@pobox.com, aarcange@redhat.com, dwmw2@infradead.org, akpm@linux-foundation.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org, torvalds@linux-foundation.org On Mon, Aug 6, 2012 at 7:29 AM, Peter Zijlstra wrote: > On Thu, 2012-08-02 at 15:34 -0700, Michel Lespinasse wrote: >> +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. 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. -- Michel "Walken" Lespinasse A program is never fully debugged until the last user dies. -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to majordomo@kvack.org. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: email@kvack.org From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from psmtp.com (na3sys010amx146.postini.com [74.125.245.146]) by kanga.kvack.org (Postfix) with SMTP id C60FD6B0044 for ; Mon, 6 Aug 2012 17:55:46 -0400 (EDT) Received: by ggnf4 with SMTP id f4so945033ggn.14 for ; Mon, 06 Aug 2012 14:55:45 -0700 (PDT) MIME-Version: 1.0 In-Reply-To: <1344267537.27828.93.camel@twins> References: <1343946858-8170-1-git-send-email-walken@google.com> <1343946858-8170-9-git-send-email-walken@google.com> <1344262669.27828.55.camel@twins> <1344267537.27828.93.camel@twins> Date: Mon, 6 Aug 2012 14:55:45 -0700 Message-ID: Subject: Re: [PATCH v2 8/9] rbtree: faster augmented rbtree manipulation From: Michel Lespinasse Content-Type: text/plain; charset=ISO-8859-1 Sender: owner-linux-mm@kvack.org List-ID: To: Peter Zijlstra Cc: riel@redhat.com, daniel.santos@pobox.com, aarcange@redhat.com, dwmw2@infradead.org, akpm@linux-foundation.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org, torvalds@linux-foundation.org On Mon, Aug 6, 2012 at 8:38 AM, Peter Zijlstra wrote: > On Mon, 2012-08-06 at 16:17 +0200, Peter Zijlstra wrote: > >> 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) > 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); > } 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. -- Michel "Walken" Lespinasse A program is never fully debugged until the last user dies. -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to majordomo@kvack.org. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: email@kvack.org From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from psmtp.com (na3sys010amx107.postini.com [74.125.245.107]) by kanga.kvack.org (Postfix) with SMTP id 47D0F6B0044 for ; Mon, 6 Aug 2012 20:04:20 -0400 (EDT) Received: by ghrr18 with SMTP id r18so1385305ghr.14 for ; Mon, 06 Aug 2012 17:04:19 -0700 (PDT) MIME-Version: 1.0 In-Reply-To: <1344262930.27828.57.camel@twins> References: <1343946858-8170-1-git-send-email-walken@google.com> <1343946858-8170-4-git-send-email-walken@google.com> <1344262930.27828.57.camel@twins> Date: Mon, 6 Aug 2012 17:04:18 -0700 Message-ID: Subject: Re: [PATCH v2 3/9] rbtree: add __rb_change_child() helper function From: Michel Lespinasse Content-Type: text/plain; charset=ISO-8859-1 Sender: owner-linux-mm@kvack.org List-ID: To: Peter Zijlstra Cc: riel@redhat.com, daniel.santos@pobox.com, aarcange@redhat.com, dwmw2@infradead.org, akpm@linux-foundation.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org, torvalds@linux-foundation.org On Mon, Aug 6, 2012 at 7:22 AM, Peter Zijlstra wrote: > On Thu, 2012-08-02 at 15:34 -0700, Michel Lespinasse wrote: >> +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...) -- Michel "Walken" Lespinasse A program is never fully debugged until the last user dies. -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to majordomo@kvack.org. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: email@kvack.org From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from psmtp.com (na3sys010amx105.postini.com [74.125.245.105]) by kanga.kvack.org (Postfix) with SMTP id 11E526B0044 for ; Tue, 7 Aug 2012 03:12:16 -0400 (EDT) Received: by pbbjt11 with SMTP id jt11so3931195pbb.14 for ; Tue, 07 Aug 2012 00:12:15 -0700 (PDT) Date: Tue, 7 Aug 2012 00:12:11 -0700 From: Michel Lespinasse Subject: [PATCH] rbtree: add RB_DECLARE_CALLBACKS() macro Message-ID: <20120807071211.GA1278@google.com> References: <1343946858-8170-1-git-send-email-walken@google.com> <1343946858-8170-9-git-send-email-walken@google.com> <1344262669.27828.55.camel@twins> <1344267537.27828.93.camel@twins> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: Sender: owner-linux-mm@kvack.org List-ID: To: Peter Zijlstra Cc: riel@redhat.com, daniel.santos@pobox.com, aarcange@redhat.com, dwmw2@infradead.org, akpm@linux-foundation.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org, torvalds@linux-foundation.org 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 ? Signed-off-by: Michel Lespinasse --- arch/x86/mm/pat_rbtree.c | 37 ++----------------------------------- include/linux/rbtree.h | 30 ++++++++++++++++++++++++++++++ lib/rbtree_test.c | 34 ++-------------------------------- 3 files changed, 34 insertions(+), 67 deletions(-) diff --git a/arch/x86/mm/pat_rbtree.c b/arch/x86/mm/pat_rbtree.c index 7e1515b..4d11695 100644 --- a/arch/x86/mm/pat_rbtree.c +++ b/arch/x86/mm/pat_rbtree.c @@ -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, diff --git a/include/linux/rbtree.h b/include/linux/rbtree.h index 4ace31b..8d1e83b 100644 --- a/include/linux/rbtree.h +++ b/include/linux/rbtree.h @@ -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 *); diff --git a/lib/rbtree_test.c b/lib/rbtree_test.c index e28345d..b20e999 100644 --- a/lib/rbtree_test.c +++ b/lib/rbtree_test.c @@ -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) { -- 1.7.7.3 -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to majordomo@kvack.org. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: email@kvack.org From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1753910Ab2HBWeu (ORCPT ); Thu, 2 Aug 2012 18:34:50 -0400 Received: from mail-yx0-f174.google.com ([209.85.213.174]:62801 "EHLO mail-yx0-f174.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1753740Ab2HBWeb (ORCPT ); Thu, 2 Aug 2012 18:34:31 -0400 From: Michel Lespinasse To: riel@redhat.com, peterz@infradead.org, daniel.santos@pobox.com, aarcange@redhat.com, dwmw2@infradead.org, akpm@linux-foundation.org Cc: linux-mm@kvack.org, linux-kernel@vger.kernel.org, torvalds@linux-foundation.org Subject: [PATCH v2 0/9] faster augmented rbtree interface Date: Thu, 2 Aug 2012 15:34:09 -0700 Message-Id: <1343946858-8170-1-git-send-email-walken@google.com> X-Mailer: git-send-email 1.7.7.3 Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org 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(-) -- 1.7.7.3 From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1754027Ab2HBWfh (ORCPT ); Thu, 2 Aug 2012 18:35:37 -0400 Received: from mail-yx0-f174.google.com ([209.85.213.174]:62801 "EHLO mail-yx0-f174.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1753776Ab2HBWeg (ORCPT ); Thu, 2 Aug 2012 18:34:36 -0400 From: Michel Lespinasse To: riel@redhat.com, peterz@infradead.org, daniel.santos@pobox.com, aarcange@redhat.com, dwmw2@infradead.org, akpm@linux-foundation.org Cc: linux-mm@kvack.org, linux-kernel@vger.kernel.org, torvalds@linux-foundation.org Subject: [PATCH v2 3/9] rbtree: add __rb_change_child() helper function Date: Thu, 2 Aug 2012 15:34:12 -0700 Message-Id: <1343946858-8170-4-git-send-email-walken@google.com> X-Mailer: git-send-email 1.7.7.3 In-Reply-To: <1343946858-8170-1-git-send-email-walken@google.com> References: <1343946858-8170-1-git-send-email-walken@google.com> Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org 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 --- lib/rbtree.c | 46 +++++++++++++++++----------------------------- 1 files changed, 17 insertions(+), 29 deletions(-) diff --git a/lib/rbtree.c b/lib/rbtree.c index 61cdd0e..de89a61 100644 --- a/lib/rbtree.c +++ b/lib/rbtree.c @@ -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) -- 1.7.7.3 From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1754061Ab2HBWfl (ORCPT ); Thu, 2 Aug 2012 18:35:41 -0400 Received: from mail-gg0-f174.google.com ([209.85.161.174]:57050 "EHLO mail-gg0-f174.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1753785Ab2HBWeh (ORCPT ); Thu, 2 Aug 2012 18:34:37 -0400 From: Michel Lespinasse To: riel@redhat.com, peterz@infradead.org, daniel.santos@pobox.com, aarcange@redhat.com, dwmw2@infradead.org, akpm@linux-foundation.org Cc: linux-mm@kvack.org, linux-kernel@vger.kernel.org, torvalds@linux-foundation.org Subject: [PATCH v2 4/9] rbtree: place easiest case first in rb_erase() Date: Thu, 2 Aug 2012 15:34:13 -0700 Message-Id: <1343946858-8170-5-git-send-email-walken@google.com> X-Mailer: git-send-email 1.7.7.3 In-Reply-To: <1343946858-8170-1-git-send-email-walken@google.com> References: <1343946858-8170-1-git-send-email-walken@google.com> Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org 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 --- lib/rbtree.c | 35 ++++++++++++++++++----------------- 1 files changed, 18 insertions(+), 17 deletions(-) diff --git a/lib/rbtree.c b/lib/rbtree.c index de89a61..bde1b5c 100644 --- a/lib/rbtree.c +++ b/lib/rbtree.c @@ -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); } -- 1.7.7.3 From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1754091Ab2HBWfv (ORCPT ); Thu, 2 Aug 2012 18:35:51 -0400 Received: from mail-gh0-f174.google.com ([209.85.160.174]:58692 "EHLO mail-gh0-f174.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1753793Ab2HBWek (ORCPT ); Thu, 2 Aug 2012 18:34:40 -0400 From: Michel Lespinasse To: riel@redhat.com, peterz@infradead.org, daniel.santos@pobox.com, aarcange@redhat.com, dwmw2@infradead.org, akpm@linux-foundation.org Cc: linux-mm@kvack.org, linux-kernel@vger.kernel.org, torvalds@linux-foundation.org Subject: [PATCH v2 6/9] rbtree: low level optimizations in rb_erase() Date: Thu, 2 Aug 2012 15:34:15 -0700 Message-Id: <1343946858-8170-7-git-send-email-walken@google.com> X-Mailer: git-send-email 1.7.7.3 In-Reply-To: <1343946858-8170-1-git-send-email-walken@google.com> References: <1343946858-8170-1-git-send-email-walken@google.com> Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Various minor optimizations in rb_erase(): - Avoid multiple loading of node->__rb_parent_color when computing parent and color information (possibly not in close sequence, as there might be further branches in the algorithm) - In the 1-child subcase of case 1, copy the __rb_parent_color field from the erased node to the child instead of recomputing it from the desired parent and color - When searching for the erased node's successor, differentiate between cases 2 and 3 based on whether any left links were followed. This avoids a condition later down. - In case 3, keep a pointer to the erased node's right child so we don't have to refetch it later to adjust its parent. - In the no-childs subcase of cases 2 and 3, place the rebalance assigment last so that the compiler can remove the following if(rebalance) test. Also, added some comments to illustrate cases 2 and 3. Signed-off-by: Michel Lespinasse --- lib/rbtree.c | 97 +++++++++++++++++++++++++++++++++++++-------------------- 1 files changed, 63 insertions(+), 34 deletions(-) diff --git a/lib/rbtree.c b/lib/rbtree.c index 80b0925..12d9147 100644 --- a/lib/rbtree.c +++ b/lib/rbtree.c @@ -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) -- 1.7.7.3 From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1753982Ab2HBWf6 (ORCPT ); Thu, 2 Aug 2012 18:35:58 -0400 Received: from mail-yx0-f174.google.com ([209.85.213.174]:54385 "EHLO mail-yx0-f174.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1753842Ab2HBWep (ORCPT ); Thu, 2 Aug 2012 18:34:45 -0400 From: Michel Lespinasse To: riel@redhat.com, peterz@infradead.org, daniel.santos@pobox.com, aarcange@redhat.com, dwmw2@infradead.org, akpm@linux-foundation.org Cc: linux-mm@kvack.org, linux-kernel@vger.kernel.org, torvalds@linux-foundation.org Subject: [PATCH v2 9/9] rbtree: remove prior augmented rbtree implementation Date: Thu, 2 Aug 2012 15:34:18 -0700 Message-Id: <1343946858-8170-10-git-send-email-walken@google.com> X-Mailer: git-send-email 1.7.7.3 In-Reply-To: <1343946858-8170-1-git-send-email-walken@google.com> References: <1343946858-8170-1-git-send-email-walken@google.com> Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org convert arch/x86/mm/pat_rbtree.c to the proposed augmented rbtree api and remove the old augmented rbtree implementation. Signed-off-by: Michel Lespinasse --- arch/x86/mm/pat_rbtree.c | 65 +++++++++++++++++++++++++++++------------ include/linux/rbtree.h | 8 ----- lib/rbtree.c | 71 ---------------------------------------------- 3 files changed, 46 insertions(+), 98 deletions(-) diff --git a/arch/x86/mm/pat_rbtree.c b/arch/x86/mm/pat_rbtree.c index 8acaddd..7e1515b 100644 --- a/arch/x86/mm/pat_rbtree.c +++ b/arch/x86/mm/pat_rbtree.c @@ -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; } diff --git a/include/linux/rbtree.h b/include/linux/rbtree.h index c902eb9..4ace31b 100644 --- a/include/linux/rbtree.h +++ b/include/linux/rbtree.h @@ -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 *); diff --git a/lib/rbtree.c b/lib/rbtree.c index 11c11e9..e45eed1 100644 --- a/lib/rbtree.c +++ b/lib/rbtree.c @@ -537,77 +537,6 @@ void rb_erase_augmented(struct rb_node *node, struct rb_root *root, } EXPORT_SYMBOL(rb_erase_augmented); -static void rb_augment_path(struct rb_node *node, rb_augment_f func, void *data) -{ - struct rb_node *parent; - -up: - func(node, data); - parent = rb_parent(node); - if (!parent) - return; - - if (node == parent->rb_left && parent->rb_right) - func(parent->rb_right, data); - else if (parent->rb_left) - func(parent->rb_left, data); - - node = parent; - goto up; -} - -/* - * after inserting @node into the tree, update the tree to account for - * both the new entry and any damage done by rebalance - */ -void rb_augment_insert(struct rb_node *node, rb_augment_f func, void *data) -{ - if (node->rb_left) - node = node->rb_left; - else if (node->rb_right) - node = node->rb_right; - - rb_augment_path(node, func, data); -} -EXPORT_SYMBOL(rb_augment_insert); - -/* - * before removing the node, find the deepest node on the rebalance path - * that will still be there after @node gets removed - */ -struct rb_node *rb_augment_erase_begin(struct rb_node *node) -{ - struct rb_node *deepest; - - if (!node->rb_right && !node->rb_left) - deepest = rb_parent(node); - else if (!node->rb_right) - deepest = node->rb_left; - else if (!node->rb_left) - deepest = node->rb_right; - else { - deepest = rb_next(node); - if (deepest->rb_right) - deepest = deepest->rb_right; - else if (rb_parent(deepest) != node) - deepest = rb_parent(deepest); - } - - return deepest; -} -EXPORT_SYMBOL(rb_augment_erase_begin); - -/* - * after removal, update the tree to account for the removed entry - * and any rebalance damage. - */ -void rb_augment_erase_end(struct rb_node *node, rb_augment_f func, void *data) -{ - if (node) - rb_augment_path(node, func, data); -} -EXPORT_SYMBOL(rb_augment_erase_end); - /* * This function returns the first node (in sort order) of the tree. */ -- 1.7.7.3 From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1754034Ab2HBWfs (ORCPT ); Thu, 2 Aug 2012 18:35:48 -0400 Received: from mail-gg0-f174.google.com ([209.85.161.174]:57050 "EHLO mail-gg0-f174.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1753787Ab2HBWej (ORCPT ); Thu, 2 Aug 2012 18:34:39 -0400 From: Michel Lespinasse To: riel@redhat.com, peterz@infradead.org, daniel.santos@pobox.com, aarcange@redhat.com, dwmw2@infradead.org, akpm@linux-foundation.org Cc: linux-mm@kvack.org, linux-kernel@vger.kernel.org, torvalds@linux-foundation.org Subject: [PATCH v2 5/9] rbtree: handle 1-child recoloring in rb_erase() instead of rb_erase_color() Date: Thu, 2 Aug 2012 15:34:14 -0700 Message-Id: <1343946858-8170-6-git-send-email-walken@google.com> X-Mailer: git-send-email 1.7.7.3 In-Reply-To: <1343946858-8170-1-git-send-email-walken@google.com> References: <1343946858-8170-1-git-send-email-walken@google.com> Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org An interesting observation for rb_erase() is that when a node has exactly one child, the node must be black and the child must be red. An interesting consequence is that removing such a node can be done by simply replacing it with its child and making the child black, which we can do efficiently in rb_erase(). __rb_erase_color() then only needs to handle the no-childs case and can be modified accordingly. Signed-off-by: Michel Lespinasse --- lib/rbtree.c | 105 ++++++++++++++++++++++++++++++++++------------------------ 1 files changed, 62 insertions(+), 43 deletions(-) diff --git a/lib/rbtree.c b/lib/rbtree.c index bde1b5c..80b0925 100644 --- a/lib/rbtree.c +++ b/lib/rbtree.c @@ -2,7 +2,8 @@ Red Black Trees (C) 1999 Andrea Arcangeli (C) 2002 David Woodhouse - + (C) 2012 Michel Lespinasse + 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); -- 1.7.7.3 From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1753876Ab2HBWfz (ORCPT ); Thu, 2 Aug 2012 18:35:55 -0400 Received: from mail-yw0-f46.google.com ([209.85.213.46]:32783 "EHLO mail-yw0-f46.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1753803Ab2HBWen (ORCPT ); Thu, 2 Aug 2012 18:34:43 -0400 From: Michel Lespinasse To: riel@redhat.com, peterz@infradead.org, daniel.santos@pobox.com, aarcange@redhat.com, dwmw2@infradead.org, akpm@linux-foundation.org Cc: linux-mm@kvack.org, linux-kernel@vger.kernel.org, torvalds@linux-foundation.org Subject: [PATCH v2 7/9] rbtree: augmented rbtree test Date: Thu, 2 Aug 2012 15:34:16 -0700 Message-Id: <1343946858-8170-8-git-send-email-walken@google.com> X-Mailer: git-send-email 1.7.7.3 In-Reply-To: <1343946858-8170-1-git-send-email-walken@google.com> References: <1343946858-8170-1-git-send-email-walken@google.com> Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Small test to measure the performance of augmented rbtrees. Signed-off-by: Michel Lespinasse --- lib/rbtree_test.c | 103 +++++++++++++++++++++++++++++++++++++++++++++++++++- 1 files changed, 101 insertions(+), 2 deletions(-) diff --git a/lib/rbtree_test.c b/lib/rbtree_test.c index fd09465..66e41d4 100644 --- a/lib/rbtree_test.c +++ b/lib/rbtree_test.c @@ -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 */ } -- 1.7.7.3 From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1752968Ab2HBWgC (ORCPT ); Thu, 2 Aug 2012 18:36:02 -0400 Received: from mail-yx0-f174.google.com ([209.85.213.174]:62801 "EHLO mail-yx0-f174.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1753834Ab2HBWeo (ORCPT ); Thu, 2 Aug 2012 18:34:44 -0400 From: Michel Lespinasse To: riel@redhat.com, peterz@infradead.org, daniel.santos@pobox.com, aarcange@redhat.com, dwmw2@infradead.org, akpm@linux-foundation.org Cc: linux-mm@kvack.org, linux-kernel@vger.kernel.org, torvalds@linux-foundation.org Subject: [PATCH v2 8/9] rbtree: faster augmented rbtree manipulation Date: Thu, 2 Aug 2012 15:34:17 -0700 Message-Id: <1343946858-8170-9-git-send-email-walken@google.com> X-Mailer: git-send-email 1.7.7.3 In-Reply-To: <1343946858-8170-1-git-send-email-walken@google.com> References: <1343946858-8170-1-git-send-email-walken@google.com> Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org 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. 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(). Signed-off-by: Michel Lespinasse --- 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(-) diff --git a/Documentation/rbtree.txt b/Documentation/rbtree.txt index 8d32d85..0a0b6dc 100644 --- a/Documentation/rbtree.txt +++ b/Documentation/rbtree.txt @@ -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); +} diff --git a/include/linux/rbtree.h b/include/linux/rbtree.h index bf836a2..c902eb9 100644 --- a/include/linux/rbtree.h +++ b/include/linux/rbtree.h @@ -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, diff --git a/lib/rbtree.c b/lib/rbtree.c index 12d9147..11c11e9 100644 --- a/lib/rbtree.c +++ b/lib/rbtree.c @@ -105,7 +105,9 @@ __rb_rotate_set_parents(struct rb_node *old, struct rb_node *new, __rb_change_child(old, new, parent, root); } -void rb_insert_color(struct rb_node *node, struct rb_root *root) +static __always_inline void +__rb_insert(struct rb_node *node, struct rb_root *root, + void (*augment_rotate)(struct rb_node *old, struct rb_node *new)) { struct rb_node *parent = rb_red_parent(node), *gparent, *tmp; @@ -169,6 +171,7 @@ 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); + augment_rotate(parent, node); parent = node; tmp = node->rb_right; } @@ -187,6 +190,7 @@ void rb_insert_color(struct rb_node *node, struct rb_root *root) if (tmp) rb_set_parent_color(tmp, gparent, RB_BLACK); __rb_rotate_set_parents(gparent, parent, root, RB_RED); + augment_rotate(gparent, parent); break; } else { tmp = gparent->rb_left; @@ -209,6 +213,7 @@ 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); + augment_rotate(parent, node); parent = node; tmp = node->rb_left; } @@ -219,13 +224,15 @@ void rb_insert_color(struct rb_node *node, struct rb_root *root) if (tmp) rb_set_parent_color(tmp, gparent, RB_BLACK); __rb_rotate_set_parents(gparent, parent, root, RB_RED); + augment_rotate(gparent, parent); break; } } } -EXPORT_SYMBOL(rb_insert_color); -static void __rb_erase_color(struct rb_node *parent, struct rb_root *root) +static __always_inline void +__rb_erase_color(struct rb_node *parent, struct rb_root *root, + const struct rb_augment_callbacks *augment) { struct rb_node *node = NULL, *sibling, *tmp1, *tmp2; @@ -254,6 +261,7 @@ static void __rb_erase_color(struct rb_node *parent, struct rb_root *root) rb_set_parent_color(tmp1, parent, RB_BLACK); __rb_rotate_set_parents(parent, sibling, root, RB_RED); + augment->rotate(parent, sibling); sibling = tmp1; } tmp1 = sibling->rb_right; @@ -305,6 +313,7 @@ static void __rb_erase_color(struct rb_node *parent, struct rb_root *root) if (tmp1) rb_set_parent_color(tmp1, sibling, RB_BLACK); + augment->rotate(sibling, tmp2); tmp1 = sibling; sibling = tmp2; } @@ -327,6 +336,7 @@ static void __rb_erase_color(struct rb_node *parent, struct rb_root *root) rb_set_parent(tmp2, parent); __rb_rotate_set_parents(parent, sibling, root, RB_BLACK); + augment->rotate(parent, sibling); break; } else { sibling = parent->rb_left; @@ -337,6 +347,7 @@ static void __rb_erase_color(struct rb_node *parent, struct rb_root *root) rb_set_parent_color(tmp1, parent, RB_BLACK); __rb_rotate_set_parents(parent, sibling, root, RB_RED); + augment->rotate(parent, sibling); sibling = tmp1; } tmp1 = sibling->rb_left; @@ -363,6 +374,7 @@ static void __rb_erase_color(struct rb_node *parent, struct rb_root *root) if (tmp1) rb_set_parent_color(tmp1, sibling, RB_BLACK); + augment->rotate(sibling, tmp2); tmp1 = sibling; sibling = tmp2; } @@ -374,12 +386,15 @@ static void __rb_erase_color(struct rb_node *parent, struct rb_root *root) rb_set_parent(tmp2, parent); __rb_rotate_set_parents(parent, sibling, root, RB_BLACK); + augment->rotate(parent, sibling); break; } } } -void rb_erase(struct rb_node *node, struct rb_root *root) +static __always_inline void +__rb_erase(struct rb_node *node, struct rb_root *root, + const struct rb_augment_callbacks *augment) { struct rb_node *child = node->rb_right, *tmp = node->rb_left; struct rb_node *parent, *rebalance; @@ -401,12 +416,14 @@ void rb_erase(struct rb_node *node, struct rb_root *root) rebalance = NULL; } else rebalance = __rb_is_black(pc) ? parent : NULL; + tmp = parent; } else if (!child) { /* Still case 1, but this time the child is node->rb_left */ tmp->__rb_parent_color = pc = node->__rb_parent_color; parent = __rb_parent(pc); __rb_change_child(node, tmp, parent, root); rebalance = NULL; + tmp = parent; } else { struct rb_node *successor = child, *child2; tmp = child->rb_left; @@ -420,8 +437,9 @@ void rb_erase(struct rb_node *node, struct rb_root *root) * \ * (c) */ - parent = child; - child2 = child->rb_right; + parent = successor; + child2 = successor->rb_right; + augment->copy(node, successor); } else { /* Case 3: node's successor is leftmost under its * right child subtree @@ -444,6 +462,8 @@ void rb_erase(struct rb_node *node, struct rb_root *root) parent->rb_left = child2 = successor->rb_right; successor->rb_right = child; rb_set_parent(child, successor); + augment->copy(node, successor); + augment->propagate(parent, successor); } successor->rb_left = tmp = node->rb_left; @@ -461,13 +481,62 @@ void rb_erase(struct rb_node *node, struct rb_root *root) successor->__rb_parent_color = pc; rebalance = __rb_is_black(pc2) ? parent : NULL; } + tmp = successor; } + augment->propagate(tmp, NULL); if (rebalance) - __rb_erase_color(rebalance, root); + __rb_erase_color(rebalance, root, augment); +} + +/* + * Non-augmented rbtree manipulation functions. + * + * We use dummy augmented callbacks here, and have the compiler optimize them + * out of the rb_insert_color() and rb_erase() function definitions. + */ + +static inline void dummy_propagate(struct rb_node *node, struct rb_node *stop) {} +static inline void dummy_copy(struct rb_node *old, struct rb_node *new) {} +static inline void dummy_rotate(struct rb_node *old, struct rb_node *new) {} + +static const struct rb_augment_callbacks dummy_callbacks = { + dummy_propagate, dummy_copy, dummy_rotate +}; + +void rb_insert_color(struct rb_node *node, struct rb_root *root) +{ + __rb_insert(node, root, dummy_rotate); +} +EXPORT_SYMBOL(rb_insert_color); + +void rb_erase(struct rb_node *node, struct rb_root *root) +{ + __rb_erase(node, root, &dummy_callbacks); } EXPORT_SYMBOL(rb_erase); +/* + * Augmented rbtree manipulation functions. + * + * This instantiates the same __always_inline functions as in the non-augmented + * case, but this time with user-defined callbacks. + */ + +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); + static void rb_augment_path(struct rb_node *node, rb_augment_f func, void *data) { struct rb_node *parent; diff --git a/lib/rbtree_test.c b/lib/rbtree_test.c index 66e41d4..e28345d 100644 --- a/lib/rbtree_test.c +++ b/lib/rbtree_test.c @@ -61,35 +61,65 @@ static inline u32 augment_recompute(struct test_node *node) return max; } -static void augment_callback(struct rb_node *rb, void *unused) +static void augment_propagate(struct rb_node *rb, struct rb_node *stop) { - struct test_node *node = rb_entry(rb, struct test_node, rb); - node->augmented = augment_recompute(node); + 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 +}; + static void insert_augmented(struct test_node *node, struct rb_root *root) { - struct rb_node **new = &root->rb_node, *parent = NULL; + struct rb_node **new = &root->rb_node, *rb_parent = NULL; u32 key = node->key; + u32 val = node->val; + struct test_node *parent; while (*new) { - parent = *new; - if (key < rb_entry(parent, struct test_node, rb)->key) - new = &parent->rb_left; + rb_parent = *new; + parent = rb_entry(rb_parent, struct test_node, rb); + if (parent->augmented < val) + parent->augmented = val; + if (key < parent->key) + new = &parent->rb.rb_left; else - new = &parent->rb_right; + new = &parent->rb.rb_right; } - rb_link_node(&node->rb, parent, new); - rb_insert_color(&node->rb, root); - rb_augment_insert(&node->rb, augment_callback, NULL); + node->augmented = val; + rb_link_node(&node->rb, rb_parent, new); + rb_insert_augmented(&node->rb, root, &augment_callbacks); } 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); + rb_erase_augmented(&node->rb, root, &augment_callbacks); } static void init(void) -- 1.7.7.3 From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1754004Ab2HBWff (ORCPT ); Thu, 2 Aug 2012 18:35:35 -0400 Received: from mail-yx0-f174.google.com ([209.85.213.174]:62801 "EHLO mail-yx0-f174.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1753773Ab2HBWef (ORCPT ); Thu, 2 Aug 2012 18:34:35 -0400 From: Michel Lespinasse To: riel@redhat.com, peterz@infradead.org, daniel.santos@pobox.com, aarcange@redhat.com, dwmw2@infradead.org, akpm@linux-foundation.org Cc: linux-mm@kvack.org, linux-kernel@vger.kernel.org, torvalds@linux-foundation.org Subject: [PATCH v2 2/9] rbtree: optimize fetching of sibling node Date: Thu, 2 Aug 2012 15:34:11 -0700 Message-Id: <1343946858-8170-3-git-send-email-walken@google.com> X-Mailer: git-send-email 1.7.7.3 In-Reply-To: <1343946858-8170-1-git-send-email-walken@google.com> References: <1343946858-8170-1-git-send-email-walken@google.com> Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org When looking to fetch a node's sibling, we went through a sequence of: - check if node is the parent's left child - if it is, then fetch the parent's right child This can be replaced with: - fetch the parent's right child as an assumed sibling - check that node is NOT the fetched child This avoids fetching the parent's left child when node is actually that child. Saves a bit on code size, though it doesn't seem to make a large difference in speed. Signed-off-by: Michel Lespinasse --- lib/rbtree.c | 21 +++++++++++++-------- 1 files changed, 13 insertions(+), 8 deletions(-) diff --git a/lib/rbtree.c b/lib/rbtree.c index 0892670..61cdd0e 100644 --- a/lib/rbtree.c +++ b/lib/rbtree.c @@ -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 -- 1.7.7.3 From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1753959Ab2HBWfb (ORCPT ); Thu, 2 Aug 2012 18:35:31 -0400 Received: from mail-gh0-f174.google.com ([209.85.160.174]:58692 "EHLO mail-gh0-f174.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1753757Ab2HBWec (ORCPT ); Thu, 2 Aug 2012 18:34:32 -0400 From: Michel Lespinasse To: riel@redhat.com, peterz@infradead.org, daniel.santos@pobox.com, aarcange@redhat.com, dwmw2@infradead.org, akpm@linux-foundation.org Cc: linux-mm@kvack.org, linux-kernel@vger.kernel.org, torvalds@linux-foundation.org Subject: [PATCH v2 1/9] rbtree test: fix sparse warning about 64-bit constant Date: Thu, 2 Aug 2012 15:34:10 -0700 Message-Id: <1343946858-8170-2-git-send-email-walken@google.com> X-Mailer: git-send-email 1.7.7.3 In-Reply-To: <1343946858-8170-1-git-send-email-walken@google.com> References: <1343946858-8170-1-git-send-email-walken@google.com> Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Just a small fix to make sparse happy. Signed-off-by: Michel Lespinasse Reported-by: Fengguang Wu --- lib/rbtree_test.c | 2 +- 1 files changed, 1 insertions(+), 1 deletions(-) diff --git a/lib/rbtree_test.c b/lib/rbtree_test.c index 19dfca9..fd09465 100644 --- a/lib/rbtree_test.c +++ b/lib/rbtree_test.c @@ -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(); -- 1.7.7.3 From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1753955Ab2HBWlU (ORCPT ); Thu, 2 Aug 2012 18:41:20 -0400 Received: from perches-mx.perches.com ([206.117.179.246]:47816 "EHLO labridge.com" rhost-flags-OK-OK-OK-FAIL) by vger.kernel.org with ESMTP id S1752599Ab2HBWlO (ORCPT ); Thu, 2 Aug 2012 18:41:14 -0400 Message-ID: <1343947273.10710.4.camel@joe2Laptop> Subject: Re: [PATCH v2 9/9] rbtree: remove prior augmented rbtree implementation From: Joe Perches To: Michel Lespinasse Cc: riel@redhat.com, peterz@infradead.org, daniel.santos@pobox.com, aarcange@redhat.com, dwmw2@infradead.org, akpm@linux-foundation.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org, torvalds@linux-foundation.org Date: Thu, 02 Aug 2012 15:41:13 -0700 In-Reply-To: <1343946858-8170-10-git-send-email-walken@google.com> References: <1343946858-8170-1-git-send-email-walken@google.com> <1343946858-8170-10-git-send-email-walken@google.com> Content-Type: text/plain; charset="UTF-8" X-Mailer: Evolution 3.2.2- Content-Transfer-Encoding: 7bit Mime-Version: 1.0 Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org On Thu, 2012-08-02 at 15:34 -0700, Michel Lespinasse wrote: > convert arch/x86/mm/pat_rbtree.c to the proposed augmented rbtree api > and remove the old augmented rbtree implementation. style trivia: > +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); I think this reads better as: u64 max_end = data->end; u64 child_max_end = get_subtree_max_end(node->rb.rb_right); From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1755018Ab2HEUrr (ORCPT ); Sun, 5 Aug 2012 16:47:47 -0400 Received: from mx1.redhat.com ([209.132.183.28]:1311 "EHLO mx1.redhat.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1754948Ab2HEUrq (ORCPT ); Sun, 5 Aug 2012 16:47:46 -0400 Message-ID: <501EDBCD.6030208@redhat.com> Date: Sun, 05 Aug 2012 16:47:09 -0400 From: Rik van Riel User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:12.0) Gecko/20120430 Thunderbird/12.0.1 MIME-Version: 1.0 To: Michel Lespinasse CC: peterz@infradead.org, daniel.santos@pobox.com, aarcange@redhat.com, dwmw2@infradead.org, akpm@linux-foundation.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org, torvalds@linux-foundation.org Subject: Re: [PATCH v2 1/9] rbtree test: fix sparse warning about 64-bit constant References: <1343946858-8170-1-git-send-email-walken@google.com> <1343946858-8170-2-git-send-email-walken@google.com> In-Reply-To: <1343946858-8170-2-git-send-email-walken@google.com> Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org On 08/02/2012 06:34 PM, Michel Lespinasse wrote: > Just a small fix to make sparse happy. > > Signed-off-by: Michel Lespinasse > Reported-by: Fengguang Wu Acked-by: Rik van Riel -- All rights reversed From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1755365Ab2HEXVJ (ORCPT ); Sun, 5 Aug 2012 19:21:09 -0400 Received: from mx1.redhat.com ([209.132.183.28]:18121 "EHLO mx1.redhat.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1755183Ab2HEXVH (ORCPT ); Sun, 5 Aug 2012 19:21:07 -0400 Message-ID: <501EFFC2.6090700@redhat.com> Date: Sun, 05 Aug 2012 19:20:34 -0400 From: Rik van Riel User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:12.0) Gecko/20120430 Thunderbird/12.0.1 MIME-Version: 1.0 To: Michel Lespinasse CC: peterz@infradead.org, daniel.santos@pobox.com, aarcange@redhat.com, dwmw2@infradead.org, akpm@linux-foundation.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org, torvalds@linux-foundation.org Subject: Re: [PATCH v2 2/9] rbtree: optimize fetching of sibling node References: <1343946858-8170-1-git-send-email-walken@google.com> <1343946858-8170-3-git-send-email-walken@google.com> In-Reply-To: <1343946858-8170-3-git-send-email-walken@google.com> Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org On 08/02/2012 06:34 PM, Michel Lespinasse wrote: > When looking to fetch a node's sibling, we went through a sequence of: > - check if node is the parent's left child > - if it is, then fetch the parent's right child > > This can be replaced with: > - fetch the parent's right child as an assumed sibling > - check that node is NOT the fetched child > > This avoids fetching the parent's left child when node is actually > that child. Saves a bit on code size, though it doesn't seem to make > a large difference in speed. > > Signed-off-by: Michel Lespinasse Acked-by: Rik van Riel -- All rights reversed From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1755188Ab2HFBBj (ORCPT ); Sun, 5 Aug 2012 21:01:39 -0400 Received: from mx1.redhat.com ([209.132.183.28]:37500 "EHLO mx1.redhat.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1755084Ab2HFBBM (ORCPT ); Sun, 5 Aug 2012 21:01:12 -0400 Message-ID: <501F171F.50001@redhat.com> Date: Sun, 05 Aug 2012 21:00:15 -0400 From: Rik van Riel User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:12.0) Gecko/20120430 Thunderbird/12.0.1 MIME-Version: 1.0 To: Michel Lespinasse CC: peterz@infradead.org, daniel.santos@pobox.com, aarcange@redhat.com, dwmw2@infradead.org, akpm@linux-foundation.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org, torvalds@linux-foundation.org Subject: Re: [PATCH v2 3/9] rbtree: add __rb_change_child() helper function References: <1343946858-8170-1-git-send-email-walken@google.com> <1343946858-8170-4-git-send-email-walken@google.com> In-Reply-To: <1343946858-8170-4-git-send-email-walken@google.com> Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org On 08/02/2012 06:34 PM, Michel Lespinasse wrote: > 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 Reviewed-by: Rik van Riel -- All rights reversed From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1755312Ab2HFBNk (ORCPT ); Sun, 5 Aug 2012 21:13:40 -0400 Received: from mx1.redhat.com ([209.132.183.28]:23856 "EHLO mx1.redhat.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1755133Ab2HFBNj (ORCPT ); Sun, 5 Aug 2012 21:13:39 -0400 Message-ID: <501F1A24.60505@redhat.com> Date: Sun, 05 Aug 2012 21:13:08 -0400 From: Rik van Riel User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:12.0) Gecko/20120430 Thunderbird/12.0.1 MIME-Version: 1.0 To: Michel Lespinasse CC: peterz@infradead.org, daniel.santos@pobox.com, aarcange@redhat.com, dwmw2@infradead.org, akpm@linux-foundation.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org, torvalds@linux-foundation.org Subject: Re: [PATCH v2 4/9] rbtree: place easiest case first in rb_erase() References: <1343946858-8170-1-git-send-email-walken@google.com> <1343946858-8170-5-git-send-email-walken@google.com> In-Reply-To: <1343946858-8170-5-git-send-email-walken@google.com> Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org On 08/02/2012 06:34 PM, Michel Lespinasse wrote: > 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 Reviewed-by: Rik van Riel -- All rights reversed From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1755338Ab2HFB2H (ORCPT ); Sun, 5 Aug 2012 21:28:07 -0400 Received: from mx1.redhat.com ([209.132.183.28]:7561 "EHLO mx1.redhat.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1755133Ab2HFB2E (ORCPT ); Sun, 5 Aug 2012 21:28:04 -0400 Message-ID: <501F1D86.7020409@redhat.com> Date: Sun, 05 Aug 2012 21:27:34 -0400 From: Rik van Riel User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:12.0) Gecko/20120430 Thunderbird/12.0.1 MIME-Version: 1.0 To: Michel Lespinasse CC: peterz@infradead.org, daniel.santos@pobox.com, aarcange@redhat.com, dwmw2@infradead.org, akpm@linux-foundation.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org, torvalds@linux-foundation.org Subject: Re: [PATCH v2 5/9] rbtree: handle 1-child recoloring in rb_erase() instead of rb_erase_color() References: <1343946858-8170-1-git-send-email-walken@google.com> <1343946858-8170-6-git-send-email-walken@google.com> In-Reply-To: <1343946858-8170-6-git-send-email-walken@google.com> Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org On 08/02/2012 06:34 PM, Michel Lespinasse wrote: > An interesting observation for rb_erase() is that when a node has > exactly one child, the node must be black and the child must be red. > An interesting consequence is that removing such a node can be done by > simply replacing it with its child and making the child black, > which we can do efficiently in rb_erase(). __rb_erase_color() then > only needs to handle the no-childs case and can be modified accordingly. > > Signed-off-by: Michel Lespinasse Acked-by: Rik van Riel -- All rights reversed From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1755500Ab2HFCMk (ORCPT ); Sun, 5 Aug 2012 22:12:40 -0400 Received: from mx1.redhat.com ([209.132.183.28]:40003 "EHLO mx1.redhat.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1755452Ab2HFCMj (ORCPT ); Sun, 5 Aug 2012 22:12:39 -0400 Message-ID: <501F27D0.6020803@redhat.com> Date: Sun, 05 Aug 2012 22:11:28 -0400 From: Rik van Riel User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:12.0) Gecko/20120430 Thunderbird/12.0.1 MIME-Version: 1.0 To: Michel Lespinasse CC: peterz@infradead.org, daniel.santos@pobox.com, aarcange@redhat.com, dwmw2@infradead.org, akpm@linux-foundation.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org, torvalds@linux-foundation.org Subject: Re: [PATCH v2 7/9] rbtree: augmented rbtree test References: <1343946858-8170-1-git-send-email-walken@google.com> <1343946858-8170-8-git-send-email-walken@google.com> In-Reply-To: <1343946858-8170-8-git-send-email-walken@google.com> Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org On 08/02/2012 06:34 PM, Michel Lespinasse wrote: > Small test to measure the performance of augmented rbtrees. > > Signed-off-by: Michel Lespinasse Acked-by: Rik van Riel -- All rights reversed From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1755525Ab2HFCNF (ORCPT ); Sun, 5 Aug 2012 22:13:05 -0400 Received: from mx1.redhat.com ([209.132.183.28]:5087 "EHLO mx1.redhat.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1755452Ab2HFCND (ORCPT ); Sun, 5 Aug 2012 22:13:03 -0400 Message-ID: <501F2812.70303@redhat.com> Date: Sun, 05 Aug 2012 22:12:34 -0400 From: Rik van Riel User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:12.0) Gecko/20120430 Thunderbird/12.0.1 MIME-Version: 1.0 To: Michel Lespinasse CC: peterz@infradead.org, daniel.santos@pobox.com, aarcange@redhat.com, dwmw2@infradead.org, akpm@linux-foundation.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org, torvalds@linux-foundation.org Subject: Re: [PATCH v2 8/9] rbtree: faster augmented rbtree manipulation References: <1343946858-8170-1-git-send-email-walken@google.com> <1343946858-8170-9-git-send-email-walken@google.com> In-Reply-To: <1343946858-8170-9-git-send-email-walken@google.com> Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org On 08/02/2012 06:34 PM, Michel Lespinasse wrote: > 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. > > 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(). > > Signed-off-by: Michel Lespinasse Acked-by: Rik van Riel -- All rights reversed From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1755558Ab2HFCNa (ORCPT ); Sun, 5 Aug 2012 22:13:30 -0400 Received: from mx1.redhat.com ([209.132.183.28]:37785 "EHLO mx1.redhat.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1755452Ab2HFCN3 (ORCPT ); Sun, 5 Aug 2012 22:13:29 -0400 Message-ID: <501F282C.6010600@redhat.com> Date: Sun, 05 Aug 2012 22:13:00 -0400 From: Rik van Riel User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:12.0) Gecko/20120430 Thunderbird/12.0.1 MIME-Version: 1.0 To: Michel Lespinasse CC: peterz@infradead.org, daniel.santos@pobox.com, aarcange@redhat.com, dwmw2@infradead.org, akpm@linux-foundation.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org, torvalds@linux-foundation.org Subject: Re: [PATCH v2 9/9] rbtree: remove prior augmented rbtree implementation References: <1343946858-8170-1-git-send-email-walken@google.com> <1343946858-8170-10-git-send-email-walken@google.com> In-Reply-To: <1343946858-8170-10-git-send-email-walken@google.com> Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org On 08/02/2012 06:34 PM, Michel Lespinasse wrote: > convert arch/x86/mm/pat_rbtree.c to the proposed augmented rbtree api > and remove the old augmented rbtree implementation. > > Signed-off-by: Michel Lespinasse Acked-by: Rik van Riel -- All rights reversed From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1755561Ab2HFCPj (ORCPT ); Sun, 5 Aug 2012 22:15:39 -0400 Received: from mx1.redhat.com ([209.132.183.28]:38985 "EHLO mx1.redhat.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1755457Ab2HFCPi (ORCPT ); Sun, 5 Aug 2012 22:15:38 -0400 Message-ID: <501F20BC.2030107@redhat.com> Date: Sun, 05 Aug 2012 21:41:16 -0400 From: Rik van Riel User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:12.0) Gecko/20120430 Thunderbird/12.0.1 MIME-Version: 1.0 To: Michel Lespinasse CC: peterz@infradead.org, daniel.santos@pobox.com, aarcange@redhat.com, dwmw2@infradead.org, akpm@linux-foundation.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org, torvalds@linux-foundation.org Subject: Re: [PATCH v2 6/9] rbtree: low level optimizations in rb_erase() References: <1343946858-8170-1-git-send-email-walken@google.com> <1343946858-8170-7-git-send-email-walken@google.com> In-Reply-To: <1343946858-8170-7-git-send-email-walken@google.com> Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org On 08/02/2012 06:34 PM, Michel Lespinasse wrote: > Various minor optimizations in rb_erase(): > - Avoid multiple loading of node->__rb_parent_color when computing parent > and color information (possibly not in close sequence, as there might > be further branches in the algorithm) > - In the 1-child subcase of case 1, copy the __rb_parent_color field from > the erased node to the child instead of recomputing it from the desired > parent and color > - When searching for the erased node's successor, differentiate between > cases 2 and 3 based on whether any left links were followed. This avoids > a condition later down. > - In case 3, keep a pointer to the erased node's right child so we don't > have to refetch it later to adjust its parent. > - In the no-childs subcase of cases 2 and 3, place the rebalance assigment > last so that the compiler can remove the following if(rebalance) test. > > Also, added some comments to illustrate cases 2 and 3. > > Signed-off-by: Michel Lespinasse Acked-by: Rik van Riel -- All rights reversed From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1756466Ab2HFOSG (ORCPT ); Mon, 6 Aug 2012 10:18:06 -0400 Received: from casper.infradead.org ([85.118.1.10]:57765 "EHLO casper.infradead.org" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1756287Ab2HFOSE convert rfc822-to-8bit (ORCPT ); Mon, 6 Aug 2012 10:18:04 -0400 Message-ID: <1344262669.27828.55.camel@twins> Subject: Re: [PATCH v2 8/9] rbtree: faster augmented rbtree manipulation From: Peter Zijlstra To: Michel Lespinasse Cc: riel@redhat.com, daniel.santos@pobox.com, aarcange@redhat.com, dwmw2@infradead.org, akpm@linux-foundation.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org, torvalds@linux-foundation.org Date: Mon, 06 Aug 2012 16:17:49 +0200 In-Reply-To: <1343946858-8170-9-git-send-email-walken@google.com> References: <1343946858-8170-1-git-send-email-walken@google.com> <1343946858-8170-9-git-send-email-walken@google.com> Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7BIT X-Mailer: Evolution 3.2.2- Mime-Version: 1.0 Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org On Thu, 2012-08-02 at 15:34 -0700, Michel Lespinasse wrote: > +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); > +} 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? From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1756487Ab2HFOVN (ORCPT ); Mon, 6 Aug 2012 10:21:13 -0400 Received: from casper.infradead.org ([85.118.1.10]:57882 "EHLO casper.infradead.org" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1756235Ab2HFOVM convert rfc822-to-8bit (ORCPT ); Mon, 6 Aug 2012 10:21:12 -0400 Message-ID: <1344262863.27828.56.camel@twins> Subject: Re: [PATCH v2 6/9] rbtree: low level optimizations in rb_erase() From: Peter Zijlstra To: Michel Lespinasse Cc: riel@redhat.com, daniel.santos@pobox.com, aarcange@redhat.com, dwmw2@infradead.org, akpm@linux-foundation.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org, torvalds@linux-foundation.org Date: Mon, 06 Aug 2012 16:21:03 +0200 In-Reply-To: <1343946858-8170-7-git-send-email-walken@google.com> References: <1343946858-8170-1-git-send-email-walken@google.com> <1343946858-8170-7-git-send-email-walken@google.com> Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7BIT X-Mailer: Evolution 3.2.2- Mime-Version: 1.0 Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org On Thu, 2012-08-02 at 15:34 -0700, Michel Lespinasse wrote: > + /* > + * Case 2: node's successor is its right child > + /* Case 3: node's successor is leftmost under its > + * right child subtree Hmm? From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1756505Ab2HFOW1 (ORCPT ); Mon, 6 Aug 2012 10:22:27 -0400 Received: from merlin.infradead.org ([205.233.59.134]:37148 "EHLO merlin.infradead.org" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1756467Ab2HFOW0 convert rfc822-to-8bit (ORCPT ); Mon, 6 Aug 2012 10:22:26 -0400 Message-ID: <1344262930.27828.57.camel@twins> Subject: Re: [PATCH v2 3/9] rbtree: add __rb_change_child() helper function From: Peter Zijlstra To: Michel Lespinasse Cc: riel@redhat.com, daniel.santos@pobox.com, aarcange@redhat.com, dwmw2@infradead.org, akpm@linux-foundation.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org, torvalds@linux-foundation.org Date: Mon, 06 Aug 2012 16:22:10 +0200 In-Reply-To: <1343946858-8170-4-git-send-email-walken@google.com> References: <1343946858-8170-1-git-send-email-walken@google.com> <1343946858-8170-4-git-send-email-walken@google.com> Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7BIT X-Mailer: Evolution 3.2.2- Mime-Version: 1.0 Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org On Thu, 2012-08-02 at 15:34 -0700, Michel Lespinasse wrote: > +static inline void I would make that __always_inline, just to make sure GCC doesn't go creative on us. > +__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; > +} From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1756571Ab2HFOYr (ORCPT ); Mon, 6 Aug 2012 10:24:47 -0400 Received: from casper.infradead.org ([85.118.1.10]:58027 "EHLO casper.infradead.org" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1756534Ab2HFOXo convert rfc822-to-8bit (ORCPT ); Mon, 6 Aug 2012 10:23:44 -0400 Message-ID: <1344263015.27828.58.camel@twins> Subject: Re: [PATCH v2 2/9] rbtree: optimize fetching of sibling node From: Peter Zijlstra To: Michel Lespinasse Cc: riel@redhat.com, daniel.santos@pobox.com, aarcange@redhat.com, dwmw2@infradead.org, akpm@linux-foundation.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org, torvalds@linux-foundation.org Date: Mon, 06 Aug 2012 16:23:35 +0200 In-Reply-To: <1343946858-8170-3-git-send-email-walken@google.com> References: <1343946858-8170-1-git-send-email-walken@google.com> <1343946858-8170-3-git-send-email-walken@google.com> Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7BIT X-Mailer: Evolution 3.2.2- Mime-Version: 1.0 Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org On Thu, 2012-08-02 at 15:34 -0700, Michel Lespinasse wrote: > + 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? From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S932079Ab2HFOZy (ORCPT ); Mon, 6 Aug 2012 10:25:54 -0400 Received: from merlin.infradead.org ([205.233.59.134]:43269 "EHLO merlin.infradead.org" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1756493Ab2HFOZx convert rfc822-to-8bit (ORCPT ); Mon, 6 Aug 2012 10:25:53 -0400 Message-ID: <1344263140.27828.59.camel@twins> Subject: Re: [PATCH v2 8/9] rbtree: faster augmented rbtree manipulation From: Peter Zijlstra To: Michel Lespinasse Cc: riel@redhat.com, daniel.santos@pobox.com, aarcange@redhat.com, dwmw2@infradead.org, akpm@linux-foundation.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org, torvalds@linux-foundation.org Date: Mon, 06 Aug 2012 16:25:40 +0200 In-Reply-To: <1343946858-8170-9-git-send-email-walken@google.com> References: <1343946858-8170-1-git-send-email-walken@google.com> <1343946858-8170-9-git-send-email-walken@google.com> Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7BIT X-Mailer: Evolution 3.2.2- Mime-Version: 1.0 Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org On Thu, 2012-08-02 at 15:34 -0700, Michel Lespinasse wrote: > +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? From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1756565Ab2HFO3i (ORCPT ); Mon, 6 Aug 2012 10:29:38 -0400 Received: from casper.infradead.org ([85.118.1.10]:58350 "EHLO casper.infradead.org" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1756493Ab2HFO3h convert rfc822-to-8bit (ORCPT ); Mon, 6 Aug 2012 10:29:37 -0400 Message-ID: <1344263368.27828.60.camel@twins> Subject: Re: [PATCH v2 8/9] rbtree: faster augmented rbtree manipulation From: Peter Zijlstra To: Michel Lespinasse Cc: riel@redhat.com, daniel.santos@pobox.com, aarcange@redhat.com, dwmw2@infradead.org, akpm@linux-foundation.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org, torvalds@linux-foundation.org Date: Mon, 06 Aug 2012 16:29:28 +0200 In-Reply-To: <1343946858-8170-9-git-send-email-walken@google.com> References: <1343946858-8170-1-git-send-email-walken@google.com> <1343946858-8170-9-git-send-email-walken@google.com> Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7BIT X-Mailer: Evolution 3.2.2- Mime-Version: 1.0 Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org On Thu, 2012-08-02 at 15:34 -0700, Michel Lespinasse wrote: > +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. From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1756672Ab2HFPjL (ORCPT ); Mon, 6 Aug 2012 11:39:11 -0400 Received: from casper.infradead.org ([85.118.1.10]:60109 "EHLO casper.infradead.org" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1755546Ab2HFPjJ convert rfc822-to-8bit (ORCPT ); Mon, 6 Aug 2012 11:39:09 -0400 Message-ID: <1344267537.27828.93.camel@twins> Subject: Re: [PATCH v2 8/9] rbtree: faster augmented rbtree manipulation From: Peter Zijlstra To: Michel Lespinasse Cc: riel@redhat.com, daniel.santos@pobox.com, aarcange@redhat.com, dwmw2@infradead.org, akpm@linux-foundation.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org, torvalds@linux-foundation.org Date: Mon, 06 Aug 2012 17:38:57 +0200 In-Reply-To: <1344262669.27828.55.camel@twins> References: <1343946858-8170-1-git-send-email-walken@google.com> <1343946858-8170-9-git-send-email-walken@google.com> <1344262669.27828.55.camel@twins> Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7BIT X-Mailer: Evolution 3.2.2- Mime-Version: 1.0 Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org On Mon, 2012-08-06 at 16:17 +0200, Peter Zijlstra wrote: > 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); } From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S932206Ab2HFUqP (ORCPT ); Mon, 6 Aug 2012 16:46:15 -0400 Received: from mail-gh0-f174.google.com ([209.85.160.174]:42022 "EHLO mail-gh0-f174.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1756689Ab2HFUqO (ORCPT ); Mon, 6 Aug 2012 16:46:14 -0400 MIME-Version: 1.0 In-Reply-To: <1344263015.27828.58.camel@twins> References: <1343946858-8170-1-git-send-email-walken@google.com> <1343946858-8170-3-git-send-email-walken@google.com> <1344263015.27828.58.camel@twins> Date: Mon, 6 Aug 2012 13:46:12 -0700 Message-ID: Subject: Re: [PATCH v2 2/9] rbtree: optimize fetching of sibling node From: Michel Lespinasse To: Peter Zijlstra Cc: riel@redhat.com, daniel.santos@pobox.com, aarcange@redhat.com, dwmw2@infradead.org, akpm@linux-foundation.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org, torvalds@linux-foundation.org Content-Type: text/plain; charset=ISO-8859-1 X-System-Of-Record: true Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org On Mon, Aug 6, 2012 at 7:23 AM, Peter Zijlstra wrote: > On Thu, 2012-08-02 at 15:34 -0700, Michel Lespinasse wrote: > >> + 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? 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. -- Michel "Walken" Lespinasse A program is never fully debugged until the last user dies. From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S932252Ab2HFUuN (ORCPT ); Mon, 6 Aug 2012 16:50:13 -0400 Received: from mail-gh0-f174.google.com ([209.85.160.174]:61394 "EHLO mail-gh0-f174.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S932163Ab2HFUuL (ORCPT ); Mon, 6 Aug 2012 16:50:11 -0400 MIME-Version: 1.0 In-Reply-To: <1344262863.27828.56.camel@twins> References: <1343946858-8170-1-git-send-email-walken@google.com> <1343946858-8170-7-git-send-email-walken@google.com> <1344262863.27828.56.camel@twins> Date: Mon, 6 Aug 2012 13:50:02 -0700 Message-ID: Subject: Re: [PATCH v2 6/9] rbtree: low level optimizations in rb_erase() From: Michel Lespinasse To: Peter Zijlstra Cc: riel@redhat.com, daniel.santos@pobox.com, aarcange@redhat.com, dwmw2@infradead.org, akpm@linux-foundation.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org, torvalds@linux-foundation.org Content-Type: text/plain; charset=ISO-8859-1 X-System-Of-Record: true Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org On Mon, Aug 6, 2012 at 7:21 AM, Peter Zijlstra wrote: > On Thu, 2012-08-02 at 15:34 -0700, Michel Lespinasse wrote: >> + /* Case 3: node's successor is leftmost under its >> + * right child subtree > > Hmm? Would 'leftmost under node's right child subtree' make more sense ? -- Michel "Walken" Lespinasse A program is never fully debugged until the last user dies. From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S932280Ab2HFU6e (ORCPT ); Mon, 6 Aug 2012 16:58:34 -0400 Received: from casper.infradead.org ([85.118.1.10]:37070 "EHLO casper.infradead.org" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1756604Ab2HFU6d convert rfc822-to-8bit (ORCPT ); Mon, 6 Aug 2012 16:58:33 -0400 Message-ID: <1344286699.27828.115.camel@twins> Subject: Re: [PATCH v2 6/9] rbtree: low level optimizations in rb_erase() From: Peter Zijlstra To: Michel Lespinasse Cc: riel@redhat.com, daniel.santos@pobox.com, aarcange@redhat.com, dwmw2@infradead.org, akpm@linux-foundation.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org, torvalds@linux-foundation.org Date: Mon, 06 Aug 2012 22:58:19 +0200 In-Reply-To: References: <1343946858-8170-1-git-send-email-walken@google.com> <1343946858-8170-7-git-send-email-walken@google.com> <1344262863.27828.56.camel@twins> Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7BIT X-Mailer: Evolution 3.2.2- Mime-Version: 1.0 Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org On Mon, 2012-08-06 at 13:50 -0700, Michel Lespinasse wrote: > On Mon, Aug 6, 2012 at 7:21 AM, Peter Zijlstra wrote: > > On Thu, 2012-08-02 at 15:34 -0700, Michel Lespinasse wrote: > >> + /* 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: .... From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1753880Ab2HFVUR (ORCPT ); Mon, 6 Aug 2012 17:20:17 -0400 Received: from mail-yx0-f174.google.com ([209.85.213.174]:59793 "EHLO mail-yx0-f174.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1751186Ab2HFVUP (ORCPT ); Mon, 6 Aug 2012 17:20:15 -0400 MIME-Version: 1.0 In-Reply-To: <1344286699.27828.115.camel@twins> References: <1343946858-8170-1-git-send-email-walken@google.com> <1343946858-8170-7-git-send-email-walken@google.com> <1344262863.27828.56.camel@twins> <1344286699.27828.115.camel@twins> Date: Mon, 6 Aug 2012 14:20:14 -0700 Message-ID: Subject: Re: [PATCH v2 6/9] rbtree: low level optimizations in rb_erase() From: Michel Lespinasse To: Peter Zijlstra Cc: riel@redhat.com, daniel.santos@pobox.com, aarcange@redhat.com, dwmw2@infradead.org, akpm@linux-foundation.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org, torvalds@linux-foundation.org Content-Type: text/plain; charset=ISO-8859-1 X-System-Of-Record: true Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org On Mon, Aug 6, 2012 at 1:58 PM, Peter Zijlstra wrote: > On Mon, 2012-08-06 at 13:50 -0700, Michel Lespinasse wrote: >> On Mon, Aug 6, 2012 at 7:21 AM, Peter Zijlstra wrote: >> > On Thu, 2012-08-02 at 15:34 -0700, Michel Lespinasse wrote: >> >> + /* 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: .... Gah, failed to notice that. Sending new patch (just the comment changed) as a reply. -- Michel "Walken" Lespinasse A program is never fully debugged until the last user dies. From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1756219Ab2HFVV5 (ORCPT ); Mon, 6 Aug 2012 17:21:57 -0400 Received: from mail-pb0-f46.google.com ([209.85.160.46]:62473 "EHLO mail-pb0-f46.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1756112Ab2HFVVz (ORCPT ); Mon, 6 Aug 2012 17:21:55 -0400 Date: Mon, 6 Aug 2012 14:21:51 -0700 From: Michel Lespinasse To: Peter Zijlstra Cc: riel@redhat.com, daniel.santos@pobox.com, aarcange@redhat.com, dwmw2@infradead.org, akpm@linux-foundation.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org, torvalds@linux-foundation.org Subject: Re: [PATCH v2 6/9] rbtree: low level optimizations in rb_erase() Message-ID: <20120806212151.GA26876@google.com> References: <1343946858-8170-1-git-send-email-walken@google.com> <1343946858-8170-7-git-send-email-walken@google.com> <1344262863.27828.56.camel@twins> <1344286699.27828.115.camel@twins> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: User-Agent: Mutt/1.5.20 (2009-06-14) Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Various minor optimizations in rb_erase(): - Avoid multiple loading of node->__rb_parent_color when computing parent and color information (possibly not in close sequence, as there might be further branches in the algorithm) - In the 1-child subcase of case 1, copy the __rb_parent_color field from the erased node to the child instead of recomputing it from the desired parent and color - When searching for the erased node's successor, differentiate between cases 2 and 3 based on whether any left links were followed. This avoids a condition later down. - In case 3, keep a pointer to the erased node's right child so we don't have to refetch it later to adjust its parent. - In the no-childs subcase of cases 2 and 3, place the rebalance assigment last so that the compiler can remove the following if(rebalance) test. Also, added some comments to illustrate cases 2 and 3. Signed-off-by: Michel Lespinasse --- lib/rbtree.c | 98 ++++++++++++++++++++++++++++++++++++++-------------------- 1 files changed, 64 insertions(+), 34 deletions(-) diff --git a/lib/rbtree.c b/lib/rbtree.c index 80b0925..938061e 100644 --- a/lib/rbtree.c +++ b/lib/rbtree.c @@ -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) -- 1.7.7.3 From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1756290Ab2HFVe3 (ORCPT ); Mon, 6 Aug 2012 17:34:29 -0400 Received: from mail-gh0-f174.google.com ([209.85.160.174]:49368 "EHLO mail-gh0-f174.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1753898Ab2HFVe2 (ORCPT ); Mon, 6 Aug 2012 17:34:28 -0400 MIME-Version: 1.0 In-Reply-To: <1344263140.27828.59.camel@twins> References: <1343946858-8170-1-git-send-email-walken@google.com> <1343946858-8170-9-git-send-email-walken@google.com> <1344263140.27828.59.camel@twins> Date: Mon, 6 Aug 2012 14:34:26 -0700 Message-ID: Subject: Re: [PATCH v2 8/9] rbtree: faster augmented rbtree manipulation From: Michel Lespinasse To: Peter Zijlstra Cc: riel@redhat.com, daniel.santos@pobox.com, aarcange@redhat.com, dwmw2@infradead.org, akpm@linux-foundation.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org, torvalds@linux-foundation.org Content-Type: text/plain; charset=ISO-8859-1 X-System-Of-Record: true Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org On Mon, Aug 6, 2012 at 7:25 AM, Peter Zijlstra wrote: > On Thu, 2012-08-02 at 15:34 -0700, Michel Lespinasse wrote: >> +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. -- Michel "Walken" Lespinasse A program is never fully debugged until the last user dies. From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1755818Ab2HFVgf (ORCPT ); Mon, 6 Aug 2012 17:36:35 -0400 Received: from casper.infradead.org ([85.118.1.10]:37591 "EHLO casper.infradead.org" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1753617Ab2HFVge convert rfc822-to-8bit (ORCPT ); Mon, 6 Aug 2012 17:36:34 -0400 Message-ID: <1344288982.27828.116.camel@twins> Subject: Re: [PATCH v2 8/9] rbtree: faster augmented rbtree manipulation From: Peter Zijlstra To: Michel Lespinasse Cc: riel@redhat.com, daniel.santos@pobox.com, aarcange@redhat.com, dwmw2@infradead.org, akpm@linux-foundation.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org, torvalds@linux-foundation.org Date: Mon, 06 Aug 2012 23:36:22 +0200 In-Reply-To: References: <1343946858-8170-1-git-send-email-walken@google.com> <1343946858-8170-9-git-send-email-walken@google.com> <1344263140.27828.59.camel@twins> Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7BIT X-Mailer: Evolution 3.2.2- Mime-Version: 1.0 Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org On Mon, 2012-08-06 at 14:34 -0700, Michel Lespinasse wrote: > On Mon, Aug 6, 2012 at 7:25 AM, Peter Zijlstra wrote: > > On Thu, 2012-08-02 at 15:34 -0700, Michel Lespinasse wrote: > >> +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. IIRC Daniel found it allowed some older GCC to inline more if the function pointer itself was constant. From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1755966Ab2HFVig (ORCPT ); Mon, 6 Aug 2012 17:38:36 -0400 Received: from mail-yx0-f174.google.com ([209.85.213.174]:60544 "EHLO mail-yx0-f174.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1753396Ab2HFVif (ORCPT ); Mon, 6 Aug 2012 17:38:35 -0400 MIME-Version: 1.0 In-Reply-To: <1344263368.27828.60.camel@twins> References: <1343946858-8170-1-git-send-email-walken@google.com> <1343946858-8170-9-git-send-email-walken@google.com> <1344263368.27828.60.camel@twins> Date: Mon, 6 Aug 2012 14:38:33 -0700 Message-ID: Subject: Re: [PATCH v2 8/9] rbtree: faster augmented rbtree manipulation From: Michel Lespinasse To: Peter Zijlstra Cc: riel@redhat.com, daniel.santos@pobox.com, aarcange@redhat.com, dwmw2@infradead.org, akpm@linux-foundation.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org, torvalds@linux-foundation.org Content-Type: text/plain; charset=ISO-8859-1 X-System-Of-Record: true Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org On Mon, Aug 6, 2012 at 7:29 AM, Peter Zijlstra wrote: > On Thu, 2012-08-02 at 15:34 -0700, Michel Lespinasse wrote: >> +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. 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. -- Michel "Walken" Lespinasse A program is never fully debugged until the last user dies. From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1755969Ab2HFV4U (ORCPT ); Mon, 6 Aug 2012 17:56:20 -0400 Received: from mail-yw0-f46.google.com ([209.85.213.46]:34803 "EHLO mail-yw0-f46.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1753617Ab2HFVzq (ORCPT ); Mon, 6 Aug 2012 17:55:46 -0400 MIME-Version: 1.0 In-Reply-To: <1344267537.27828.93.camel@twins> References: <1343946858-8170-1-git-send-email-walken@google.com> <1343946858-8170-9-git-send-email-walken@google.com> <1344262669.27828.55.camel@twins> <1344267537.27828.93.camel@twins> Date: Mon, 6 Aug 2012 14:55:45 -0700 Message-ID: Subject: Re: [PATCH v2 8/9] rbtree: faster augmented rbtree manipulation From: Michel Lespinasse To: Peter Zijlstra Cc: riel@redhat.com, daniel.santos@pobox.com, aarcange@redhat.com, dwmw2@infradead.org, akpm@linux-foundation.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org, torvalds@linux-foundation.org Content-Type: text/plain; charset=ISO-8859-1 X-System-Of-Record: true Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org On Mon, Aug 6, 2012 at 8:38 AM, Peter Zijlstra wrote: > On Mon, 2012-08-06 at 16:17 +0200, Peter Zijlstra wrote: > >> 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) > 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); > } 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. -- Michel "Walken" Lespinasse A program is never fully debugged until the last user dies. From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1757007Ab2HGAEV (ORCPT ); Mon, 6 Aug 2012 20:04:21 -0400 Received: from mail-gh0-f174.google.com ([209.85.160.174]:36659 "EHLO mail-gh0-f174.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1756161Ab2HGAEU (ORCPT ); Mon, 6 Aug 2012 20:04:20 -0400 MIME-Version: 1.0 In-Reply-To: <1344262930.27828.57.camel@twins> References: <1343946858-8170-1-git-send-email-walken@google.com> <1343946858-8170-4-git-send-email-walken@google.com> <1344262930.27828.57.camel@twins> Date: Mon, 6 Aug 2012 17:04:18 -0700 Message-ID: Subject: Re: [PATCH v2 3/9] rbtree: add __rb_change_child() helper function From: Michel Lespinasse To: Peter Zijlstra Cc: riel@redhat.com, daniel.santos@pobox.com, aarcange@redhat.com, dwmw2@infradead.org, akpm@linux-foundation.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org, torvalds@linux-foundation.org Content-Type: text/plain; charset=ISO-8859-1 X-System-Of-Record: true Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org On Mon, Aug 6, 2012 at 7:22 AM, Peter Zijlstra wrote: > On Thu, 2012-08-02 at 15:34 -0700, Michel Lespinasse wrote: >> +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...) -- Michel "Walken" Lespinasse A program is never fully debugged until the last user dies. From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1752026Ab2HGHMR (ORCPT ); Tue, 7 Aug 2012 03:12:17 -0400 Received: from mail-pb0-f46.google.com ([209.85.160.46]:64303 "EHLO mail-pb0-f46.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1750752Ab2HGHMP (ORCPT ); Tue, 7 Aug 2012 03:12:15 -0400 Date: Tue, 7 Aug 2012 00:12:11 -0700 From: Michel Lespinasse To: Peter Zijlstra Cc: riel@redhat.com, daniel.santos@pobox.com, aarcange@redhat.com, dwmw2@infradead.org, akpm@linux-foundation.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org, torvalds@linux-foundation.org Subject: [PATCH] rbtree: add RB_DECLARE_CALLBACKS() macro Message-ID: <20120807071211.GA1278@google.com> References: <1343946858-8170-1-git-send-email-walken@google.com> <1343946858-8170-9-git-send-email-walken@google.com> <1344262669.27828.55.camel@twins> <1344267537.27828.93.camel@twins> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: User-Agent: Mutt/1.5.20 (2009-06-14) Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org 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 ? Signed-off-by: Michel Lespinasse --- arch/x86/mm/pat_rbtree.c | 37 ++----------------------------------- include/linux/rbtree.h | 30 ++++++++++++++++++++++++++++++ lib/rbtree_test.c | 34 ++-------------------------------- 3 files changed, 34 insertions(+), 67 deletions(-) diff --git a/arch/x86/mm/pat_rbtree.c b/arch/x86/mm/pat_rbtree.c index 7e1515b..4d11695 100644 --- a/arch/x86/mm/pat_rbtree.c +++ b/arch/x86/mm/pat_rbtree.c @@ -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, diff --git a/include/linux/rbtree.h b/include/linux/rbtree.h index 4ace31b..8d1e83b 100644 --- a/include/linux/rbtree.h +++ b/include/linux/rbtree.h @@ -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 *); diff --git a/lib/rbtree_test.c b/lib/rbtree_test.c index e28345d..b20e999 100644 --- a/lib/rbtree_test.c +++ b/lib/rbtree_test.c @@ -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) { -- 1.7.7.3