From 7a742d08a46de9bfb7d89b31af1fd40e9e03134c Mon Sep 17 00:00:00 2001 From: James Simmons Date: Sun, 18 Sep 2016 16:37:28 -0400 Subject: [PATCH] staging: lustre: ldlm: restore some of the interval functionality 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 Signed-off-by: Greg Kroah-Hartman --- .../lustre/lustre/include/interval_tree.h | 26 +++++ .../lustre/lustre/ldlm/interval_tree.c | 100 +++++++++++++++++- 2 files changed, 125 insertions(+), 1 deletion(-) diff --git a/drivers/staging/lustre/lustre/include/interval_tree.h b/drivers/staging/lustre/lustre/include/interval_tree.h index 4a15228b5570..5d387d372547 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 f4a70ebddeaf..e134ecd21bb2 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->endin_right; + break; + } + node = parent; + parent = parent->in_parent; + } + if (!parent || !interval_may_overlap(parent, ext)) + break; + } + + return rc; +} +EXPORT_SYMBOL(interval_search); -- 2.39.5