[PATCH 029/124] staging: lustre: ldlm: restore some of the interval functionality

[James Simmons <jsimmons@infradead.org>]

Earlier a bunch of interval handling got removed since it wasn't
used by the upstream client. Now some of it is needed again for
the client code so this patch restores what is needed.

Signed-off-by: James Simmons <jsimmons@infradead.org>
---
 .../staging/lustre/lustre/include/interval_tree.h  |   26 +++++
 drivers/staging/lustre/lustre/ldlm/interval_tree.c |  100 +++++++++++++++++++-
 2 files changed, 125 insertions(+), 1 deletions(-)

diff --git a/drivers/staging/lustre/lustre/include/interval_tree.h b/drivers/staging/lustre/lustre/include/interval_tree.h
index 4a15228..5d387d3 100644
--- a/drivers/staging/lustre/lustre/include/interval_tree.h
+++ b/drivers/staging/lustre/lustre/include/interval_tree.h
@@ -63,6 +63,11 @@ static inline int interval_is_intree(struct interval_node *node)
 	return node->in_intree == 1;
 }
 
+static inline __u64 interval_low(struct interval_node *node)
+{
+	return node->in_extent.start;
+}
+
 static inline __u64 interval_high(struct interval_node *node)
 {
 	return node->in_extent.end;
@@ -77,8 +82,29 @@ static inline void interval_set(struct interval_node *node,
 	node->in_max_high = end;
 }
 
+/*
+ * Rules to write an interval callback.
+ *  - the callback returns INTERVAL_ITER_STOP when it thinks the iteration
+ *    should be stopped. It will then cause the iteration function to return
+ *    immediately with return value INTERVAL_ITER_STOP.
+ *  - callbacks for interval_iterate and interval_iterate_reverse: Every
+ *    nodes in the tree will be set to @node before the callback being called
+ *  - callback for interval_search: Only overlapped node will be set to @node
+ *    before the callback being called.
+ */
+typedef enum interval_iter (*interval_callback_t)(struct interval_node *node,
+						  void *args);
+
 struct interval_node *interval_insert(struct interval_node *node,
 				      struct interval_node **root);
 void interval_erase(struct interval_node *node, struct interval_node **root);
 
+/*
+ * Search the extents in the tree and call @func for each overlapped
+ * extents.
+ */
+enum interval_iter interval_search(struct interval_node *root,
+				   struct interval_node_extent *ex,
+				   interval_callback_t func, void *data);
+
 #endif
diff --git a/drivers/staging/lustre/lustre/ldlm/interval_tree.c b/drivers/staging/lustre/lustre/ldlm/interval_tree.c
index f4a70eb..e134ecd 100644
--- a/drivers/staging/lustre/lustre/ldlm/interval_tree.c
+++ b/drivers/staging/lustre/lustre/ldlm/interval_tree.c
@@ -90,6 +90,17 @@ static inline int extent_equal(struct interval_node_extent *e1,
 	return (e1->start == e2->start) && (e1->end == e2->end);
 }
 
+static inline int extent_overlapped(struct interval_node_extent *e1,
+				    struct interval_node_extent *e2)
+{
+	return (e1->start <= e2->end) && (e2->start <= e1->end);
+}
+
+static inline int node_equal(struct interval_node *n1, struct interval_node *n2)
+{
+	return extent_equal(&n1->in_extent, &n2->in_extent);
+}
+
 static inline __u64 max_u64(__u64 x, __u64 y)
 {
 	return x > y ? x : y;
@@ -262,7 +273,7 @@ struct interval_node *interval_insert(struct interval_node *node,
 	p = root;
 	while (*p) {
 		parent = *p;
-		if (extent_equal(&parent->in_extent, &node->in_extent))
+		if (node_equal(parent, node))
 			return parent;
 
 		/* max_high field must be updated after each iteration */
@@ -463,3 +474,90 @@ color:
 		interval_erase_color(child, parent, root);
 }
 EXPORT_SYMBOL(interval_erase);
+
+static inline int interval_may_overlap(struct interval_node *node,
+				       struct interval_node_extent *ext)
+{
+	return (ext->start <= node->in_max_high &&
+		ext->end >= interval_low(node));
+}
+
+/*
+ * This function finds all intervals that overlap interval ext,
+ * and calls func to handle resulted intervals one by one.
+ * in lustre, this function will find all conflicting locks in
+ * the granted queue and add these locks to the ast work list.
+ *
+ * {
+ *	if (!node)
+ *		return 0;
+ *	if (ext->end < interval_low(node)) {
+ *		interval_search(node->in_left, ext, func, data);
+ *	} else if (interval_may_overlap(node, ext)) {
+ *		if (extent_overlapped(ext, &node->in_extent))
+ *			func(node, data);
+ *		interval_search(node->in_left, ext, func, data);
+ *		interval_search(node->in_right, ext, func, data);
+ *	}
+ *	return 0;
+ * }
+ *
+ */
+enum interval_iter interval_search(struct interval_node *node,
+				   struct interval_node_extent *ext,
+				   interval_callback_t func,
+				   void *data)
+{
+	enum interval_iter rc = INTERVAL_ITER_CONT;
+	struct interval_node *parent;
+
+	LASSERT(ext);
+	LASSERT(func);
+
+	while (node) {
+		if (ext->end < interval_low(node)) {
+			if (node->in_left) {
+				node = node->in_left;
+				continue;
+			}
+		} else if (interval_may_overlap(node, ext)) {
+			if (extent_overlapped(ext, &node->in_extent)) {
+				rc = func(node, data);
+				if (rc == INTERVAL_ITER_STOP)
+					break;
+			}
+
+			if (node->in_left) {
+				node = node->in_left;
+				continue;
+			}
+			if (node->in_right) {
+				node = node->in_right;
+				continue;
+			}
+		}
+
+		parent = node->in_parent;
+		while (parent) {
+			if (node_is_left_child(node) &&
+			    parent->in_right) {
+				/*
+				 * If we ever got the left, it means that the
+				 * parent met ext->end<interval_low(parent), or
+				 * may_overlap(parent). If the former is true,
+				 * we needn't go back. So stop early and check
+				 * may_overlap(parent) after this loop.
+				 */
+				node = parent->in_right;
+				break;
+			}
+			node = parent;
+			parent = parent->in_parent;
+		}
+		if (!parent || !interval_may_overlap(parent, ext))
+			break;
+	}
+
+	return rc;
+}
+EXPORT_SYMBOL(interval_search);
-- 
1.7.1