Merge branch 'x86-fixes-for-linus' of git://git.kernel.org/pub/scm/linux/kernel/git/tip/linux-2.6-tip

* 'x86-fixes-for-linus' of git://git.kernel.org/pub/scm/linux/kernel/git/tip/linux-2.6-tip:
  rbtree: Undo augmented trees performance damage and regression
  x86, Calgary: Limit the max PHB number to 256

1 files changed, 72 insertions, 44 deletions

diff --git a/lib/rbtree.c b/lib/rbtree.c
index 15e10b1afdd..4693f79195d 100644
--- a/lib/rbtree.c
+++ b/lib/rbtree.c
@@ -44,11 +44,6 @@ static void __rb_rotate_left(struct rb_node *node, struct rb_root *root)
         else
                 root->rb_node = right;
         rb_set_parent(node, right);
-
-        if (root->augment_cb) {
-                root->augment_cb(node);
-                root->augment_cb(right);
-        }
 }
 
 static void __rb_rotate_right(struct rb_node *node, struct rb_root *root)
@@ -72,20 +67,12 @@ static void __rb_rotate_right(struct rb_node *node, struct rb_root *root)
         else
                 root->rb_node = left;
         rb_set_parent(node, left);
-
-        if (root->augment_cb) {
-                root->augment_cb(node);
-                root->augment_cb(left);
-        }
 }
 
 void rb_insert_color(struct rb_node *node, struct rb_root *root)
 {
         struct rb_node *parent, *gparent;
 
-        if (root->augment_cb)
-                root->augment_cb(node);
-
         while ((parent = rb_parent(node)) && rb_is_red(parent))
         {
                 gparent = rb_parent(parent);
@@ -240,15 +227,12 @@ void rb_erase(struct rb_node *node, struct rb_root *root)
         else
         {
                 struct rb_node *old = node, *left;
-                int old_parent_cb = 0;
-                int successor_parent_cb = 0;
 
                 node = node->rb_right;
                 while ((left = node->rb_left) != NULL)
                         node = left;
 
                 if (rb_parent(old)) {
-                        old_parent_cb = 1;
                         if (rb_parent(old)->rb_left == old)
                                 rb_parent(old)->rb_left = node;
                         else
@@ -263,10 +247,8 @@ void rb_erase(struct rb_node *node, struct rb_root *root)
                 if (parent == old) {
                         parent = node;
                 } else {
-                        successor_parent_cb = 1;
                         if (child)
                                 rb_set_parent(child, parent);
-
                         parent->rb_left = child;
 
                         node->rb_right = old->rb_right;
@@ -277,24 +259,6 @@ void rb_erase(struct rb_node *node, struct rb_root *root)
                 node->rb_left = old->rb_left;
                 rb_set_parent(old->rb_left, node);
 
-                if (root->augment_cb) {
-                        /*
-                         * Here, three different nodes can have new children.
-                         * The parent of the successor node that was selected
-                         * to replace the node to be erased.
-                         * The node that is getting erased and is now replaced
-                         * by its successor.
-                         * The parent of the node getting erased-replaced.
-                         */
-                        if (successor_parent_cb)
-                                root->augment_cb(parent);
-
-                        root->augment_cb(node);
-
-                        if (old_parent_cb)
-                                root->augment_cb(rb_parent(old));
-                }
-
                 goto color;
         }
 
@@ -303,19 +267,15 @@ void rb_erase(struct rb_node *node, struct rb_root *root)
 
         if (child)
                 rb_set_parent(child, parent);
-
-        if (parent) {
+        if (parent)
+        {
                 if (parent->rb_left == node)
                         parent->rb_left = child;
                 else
                         parent->rb_right = child;
-
-                if (root->augment_cb)
-                        root->augment_cb(parent);
-
-        } else {
-                root->rb_node = child;
         }
+        else
+                root->rb_node = child;
 
  color:
         if (color == RB_BLACK)
@@ -323,6 +283,74 @@ void rb_erase(struct rb_node *node, struct rb_root *root)
 }
 EXPORT_SYMBOL(rb_erase);
 
+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);
+}
+
+/*
+ * 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;
+}
+
+/*
+ * 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);
+}
+
 /*
  * This function returns the first node (in sort order) of the tree.
  */