aboutsummaryrefslogtreecommitdiffstats
path: root/lib/rbtree.c
diff options
context:
space:
mode:
authorPeter Zijlstra <peterz@infradead.org>2010-05-29 09:31:43 -0400
committerIngo Molnar <mingo@elte.hu>2010-07-05 08:43:50 -0400
commitb945d6b2554d550fe95caadc61e521c0ad71fb9c (patch)
tree0b76cdb978bead82188de40cae6d24bd88d71b7d /lib/rbtree.c
parentd596043d71ff0d7b3d0bead19b1d68c55f003093 (diff)
rbtree: Undo augmented trees performance damage and regression
Reimplement augmented RB-trees without sprinkling extra branches all over the RB-tree code (which lives in the scheduler hot path). This approach is 'borrowed' from Fabio's BFQ implementation and relies on traversing the rebalance path after the RB-tree-op to correct the heap property for insertion/removal and make up for the damage done by the tree rotations. For insertion the rebalance path is trivially that from the new node upwards to the root, for removal it is that from the deepest node in the path from the to be removed node that will still be around after the removal. [ This patch also fixes a video driver regression reported by Ali Gholami Rudi - the memtype->subtree_max_end was updated incorrectly. ] Acked-by: Suresh Siddha <suresh.b.siddha@intel.com> Acked-by: Venkatesh Pallipadi <venki@google.com> Signed-off-by: Peter Zijlstra <a.p.zijlstra@chello.nl> Tested-by: Ali Gholami Rudi <ali@rudi.ir> Cc: Fabio Checconi <fabio@gandalf.sssup.it> Cc: "H. Peter Anvin" <hpa@zytor.com> Cc: Andrew Morton <akpm@linux-foundation.org> Cc: Linus Torvalds <torvalds@linux-foundation.org> LKML-Reference: <1275414172.27810.27961.camel@twins> Signed-off-by: Ingo Molnar <mingo@elte.hu>
Diffstat (limited to 'lib/rbtree.c')
-rw-r--r--lib/rbtree.c116
1 files changed, 72 insertions, 44 deletions
diff --git a/lib/rbtree.c b/lib/rbtree.c
index 15e10b1afdd2..4693f79195d3 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)
44 else 44 else
45 root->rb_node = right; 45 root->rb_node = right;
46 rb_set_parent(node, right); 46 rb_set_parent(node, right);
47
48 if (root->augment_cb) {
49 root->augment_cb(node);
50 root->augment_cb(right);
51 }
52} 47}
53 48
54static void __rb_rotate_right(struct rb_node *node, struct rb_root *root) 49static 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)
72 else 67 else
73 root->rb_node = left; 68 root->rb_node = left;
74 rb_set_parent(node, left); 69 rb_set_parent(node, left);
75
76 if (root->augment_cb) {
77 root->augment_cb(node);
78 root->augment_cb(left);
79 }
80} 70}
81 71
82void rb_insert_color(struct rb_node *node, struct rb_root *root) 72void rb_insert_color(struct rb_node *node, struct rb_root *root)
83{ 73{
84 struct rb_node *parent, *gparent; 74 struct rb_node *parent, *gparent;
85 75
86 if (root->augment_cb)
87 root->augment_cb(node);
88
89 while ((parent = rb_parent(node)) && rb_is_red(parent)) 76 while ((parent = rb_parent(node)) && rb_is_red(parent))
90 { 77 {
91 gparent = rb_parent(parent); 78 gparent = rb_parent(parent);
@@ -240,15 +227,12 @@ void rb_erase(struct rb_node *node, struct rb_root *root)
240 else 227 else
241 { 228 {
242 struct rb_node *old = node, *left; 229 struct rb_node *old = node, *left;
243 int old_parent_cb = 0;
244 int successor_parent_cb = 0;
245 230
246 node = node->rb_right; 231 node = node->rb_right;
247 while ((left = node->rb_left) != NULL) 232 while ((left = node->rb_left) != NULL)
248 node = left; 233 node = left;
249 234
250 if (rb_parent(old)) { 235 if (rb_parent(old)) {
251 old_parent_cb = 1;
252 if (rb_parent(old)->rb_left == old) 236 if (rb_parent(old)->rb_left == old)
253 rb_parent(old)->rb_left = node; 237 rb_parent(old)->rb_left = node;
254 else 238 else
@@ -263,10 +247,8 @@ void rb_erase(struct rb_node *node, struct rb_root *root)
263 if (parent == old) { 247 if (parent == old) {
264 parent = node; 248 parent = node;
265 } else { 249 } else {
266 successor_parent_cb = 1;
267 if (child) 250 if (child)
268 rb_set_parent(child, parent); 251 rb_set_parent(child, parent);
269
270 parent->rb_left = child; 252 parent->rb_left = child;
271 253
272 node->rb_right = old->rb_right; 254 node->rb_right = old->rb_right;
@@ -277,24 +259,6 @@ void rb_erase(struct rb_node *node, struct rb_root *root)
277 node->rb_left = old->rb_left; 259 node->rb_left = old->rb_left;
278 rb_set_parent(old->rb_left, node); 260 rb_set_parent(old->rb_left, node);
279 261
280 if (root->augment_cb) {
281 /*
282 * Here, three different nodes can have new children.
283 * The parent of the successor node that was selected
284 * to replace the node to be erased.
285 * The node that is getting erased and is now replaced
286 * by its successor.
287 * The parent of the node getting erased-replaced.
288 */
289 if (successor_parent_cb)
290 root->augment_cb(parent);
291
292 root->augment_cb(node);
293
294 if (old_parent_cb)
295 root->augment_cb(rb_parent(old));
296 }
297
298 goto color; 262 goto color;
299 } 263 }
300 264
@@ -303,19 +267,15 @@ void rb_erase(struct rb_node *node, struct rb_root *root)
303 267
304 if (child) 268 if (child)
305 rb_set_parent(child, parent); 269 rb_set_parent(child, parent);
306 270 if (parent)
307 if (parent) { 271 {
308 if (parent->rb_left == node) 272 if (parent->rb_left == node)
309 parent->rb_left = child; 273 parent->rb_left = child;
310 else 274 else
311 parent->rb_right = child; 275 parent->rb_right = child;
312
313 if (root->augment_cb)
314 root->augment_cb(parent);
315
316 } else {
317 root->rb_node = child;
318 } 276 }
277 else
278 root->rb_node = child;
319 279
320 color: 280 color:
321 if (color == RB_BLACK) 281 if (color == RB_BLACK)
@@ -323,6 +283,74 @@ void rb_erase(struct rb_node *node, struct rb_root *root)
323} 283}
324EXPORT_SYMBOL(rb_erase); 284EXPORT_SYMBOL(rb_erase);
325 285
286static void rb_augment_path(struct rb_node *node, rb_augment_f func, void *data)
287{
288 struct rb_node *parent;
289
290up:
291 func(node, data);
292 parent = rb_parent(node);
293 if (!parent)
294 return;
295
296 if (node == parent->rb_left && parent->rb_right)
297 func(parent->rb_right, data);
298 else if (parent->rb_left)
299 func(parent->rb_left, data);
300
301 node = parent;
302 goto up;
303}
304
305/*
306 * after inserting @node into the tree, update the tree to account for
307 * both the new entry and any damage done by rebalance
308 */
309void rb_augment_insert(struct rb_node *node, rb_augment_f func, void *data)
310{
311 if (node->rb_left)
312 node = node->rb_left;
313 else if (node->rb_right)
314 node = node->rb_right;
315
316 rb_augment_path(node, func, data);
317}
318
319/*
320 * before removing the node, find the deepest node on the rebalance path
321 * that will still be there after @node gets removed
322 */
323struct rb_node *rb_augment_erase_begin(struct rb_node *node)
324{
325 struct rb_node *deepest;
326
327 if (!node->rb_right && !node->rb_left)
328 deepest = rb_parent(node);
329 else if (!node->rb_right)
330 deepest = node->rb_left;
331 else if (!node->rb_left)
332 deepest = node->rb_right;
333 else {
334 deepest = rb_next(node);
335 if (deepest->rb_right)
336 deepest = deepest->rb_right;
337 else if (rb_parent(deepest) != node)
338 deepest = rb_parent(deepest);
339 }
340
341 return deepest;
342}
343
344/*
345 * after removal, update the tree to account for the removed entry
346 * and any rebalance damage.
347 */
348void rb_augment_erase_end(struct rb_node *node, rb_augment_f func, void *data)
349{
350 if (node)
351 rb_augment_path(node, func, data);
352}
353
326/* 354/*
327 * This function returns the first node (in sort order) of the tree. 355 * This function returns the first node (in sort order) of the tree.
328 */ 356 */