X-Git-Url: http://review.tizen.org/git/?a=blobdiff_plain;f=drivers%2Fblock%2Fdrbd%2Fdrbd_interval.c;h=89c497c630b4ee60839571aabf59c9ad553fb229;hb=986836503e49ccf7e84b813715d344964ec93566;hp=0e53f102e68ab33574bf4f8c9304f404a809707a;hpb=328e0f125bf41f4f33f684db22015f92cb44fe56;p=platform%2Fadaptation%2Frenesas_rcar%2Frenesas_kernel.git

diff --git a/drivers/block/drbd/drbd_interval.c b/drivers/block/drbd/drbd_interval.c
index 0e53f10..89c497c 100644
--- a/drivers/block/drbd/drbd_interval.c
+++ b/drivers/block/drbd/drbd_interval.c
@@ -1,3 +1,5 @@
+#include <asm/bug.h>
+#include <linux/rbtree_augmented.h>
 #include "drbd_interval.h"
 
 /**
@@ -11,32 +13,65 @@ sector_t interval_end(struct rb_node *node)
 }
 
 /**
- * update_interval_end  -  recompute end of @node
+ * compute_subtree_last  -  compute end of @node
  *
  * The end of an interval is the highest (start + (size >> 9)) value of this
  * node and of its children.  Called for @node and its parents whenever the end
  * may have changed.
  */
-static void
-update_interval_end(struct rb_node *node, void *__unused)
+static inline sector_t
+compute_subtree_last(struct drbd_interval *node)
 {
-	struct drbd_interval *this = rb_entry(node, struct drbd_interval, rb);
-	sector_t end;
+	sector_t max = node->sector + (node->size >> 9);
 
-	end = this->sector + (this->size >> 9);
-	if (node->rb_left) {
-		sector_t left = interval_end(node->rb_left);
-		if (left > end)
-			end = left;
+	if (node->rb.rb_left) {
+		sector_t left = interval_end(node->rb.rb_left);
+		if (left > max)
+			max = left;
+	}
+	if (node->rb.rb_right) {
+		sector_t right = interval_end(node->rb.rb_right);
+		if (right > max)
+			max = right;
 	}
-	if (node->rb_right) {
-		sector_t right = interval_end(node->rb_right);
-		if (right > end)
-			end = right;
+	return max;
+}
+
+static void augment_propagate(struct rb_node *rb, struct rb_node *stop)
+{
+	while (rb != stop) {
+		struct drbd_interval *node = rb_entry(rb, struct drbd_interval, rb);
+		sector_t subtree_last = compute_subtree_last(node);
+		if (node->end == subtree_last)
+			break;
+		node->end = subtree_last;
+		rb = rb_parent(&node->rb);
 	}
-	this->end = end;
 }
 
+static void augment_copy(struct rb_node *rb_old, struct rb_node *rb_new)
+{
+	struct drbd_interval *old = rb_entry(rb_old, struct drbd_interval, rb);
+	struct drbd_interval *new = rb_entry(rb_new, struct drbd_interval, rb);
+
+	new->end = old->end;
+}
+
+static void augment_rotate(struct rb_node *rb_old, struct rb_node *rb_new)
+{
+	struct drbd_interval *old = rb_entry(rb_old, struct drbd_interval, rb);
+	struct drbd_interval *new = rb_entry(rb_new, struct drbd_interval, rb);
+
+	new->end = old->end;
+	old->end = compute_subtree_last(old);
+}
+
+static const struct rb_augment_callbacks augment_callbacks = {
+	augment_propagate,
+	augment_copy,
+	augment_rotate,
+};
+
 /**
  * drbd_insert_interval  -  insert a new interval into a tree
  */
@@ -65,8 +100,7 @@ drbd_insert_interval(struct rb_root *root, struct drbd_interval *this)
 	}
 
 	rb_link_node(&this->rb, parent, new);
-	rb_insert_color(&this->rb, root);
-	rb_augment_insert(&this->rb, update_interval_end, NULL);
+	rb_insert_augmented(&this->rb, root, &augment_callbacks);
 	return true;
 }
 
@@ -110,11 +144,7 @@ drbd_contains_interval(struct rb_root *root, sector_t sector,
 void
 drbd_remove_interval(struct rb_root *root, struct drbd_interval *this)
 {
-	struct rb_node *deepest;
-
-	deepest = rb_augment_erase_begin(&this->rb);
-	rb_erase(&this->rb, root);
-	rb_augment_erase_end(deepest, update_interval_end, NULL);
+	rb_erase_augmented(&this->rb, root, &augment_callbacks);
 }
 
 /**