1 /* -*- mode: c; c-basic-offset: 8; indent-tabs-mode: nil; -*-
2 * vim:expandtab:shiftwidth=8:tabstop=8:
4 * Interval tree library used by ldlm extent lock code
6 * Copyright (c) 2007 Cluster File Systems, Inc.
7 * Author: Huang Wei <huangwei@clusterfs.com>
8 * Author: Jay Xiong <jinshan.xiong@sun.com>
10 * This file is part of the Lustre file system, http://www.lustre.org
11 * Lustre is a trademark of Cluster File Systems, Inc.
13 * You may have signed or agreed to another license before downloading
14 * this software. If so, you are bound by the terms and conditions
15 * of that agreement, and the following does not apply to you. See the
16 * LICENSE file included with this distribution for more information.
18 * If you did not agree to a different license, then this copy of Lustre
19 * is open source software; you can redistribute it and/or modify it
20 * under the terms of version 2 of the GNU General Public License as
21 * published by the Free Software Foundation.
23 * In either case, Lustre is distributed in the hope that it will be
24 * useful, but WITHOUT ANY WARRANTY; without even the implied warranty
25 * of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
26 * license text for more details.
29 # include <lustre_dlm.h>
31 # include <liblustre.h>
32 # include <libcfs/kp30.h>
34 #include <obd_support.h>
35 #include <interval_tree.h>
42 static inline int node_is_left_child(struct interval_node *node)
44 LASSERT(node->in_parent != NULL);
45 return node == node->in_parent->in_left;
48 static inline int node_is_right_child(struct interval_node *node)
50 LASSERT(node->in_parent != NULL);
51 return node == node->in_parent->in_right;
54 static inline int node_is_red(struct interval_node *node)
56 return node->in_color == INTERVAL_RED;
59 static inline int node_is_black(struct interval_node *node)
61 return node->in_color == INTERVAL_BLACK;
64 static inline int extent_compare(struct interval_node_extent *e1,
65 struct interval_node_extent *e2)
68 if (e1->start == e2->start) {
69 if (e1->end < e2->end)
71 else if (e1->end > e2->end)
76 if (e1->start < e2->start)
84 static inline int extent_equal(struct interval_node_extent *e1,
85 struct interval_node_extent *e2)
87 return (e1->start == e2->start) && (e1->end == e2->end);
90 static inline int extent_overlapped(struct interval_node_extent *e1,
91 struct interval_node_extent *e2)
93 return (e1->start <= e2->end) && (e2->start <= e1->end);
96 static inline int node_compare(struct interval_node *n1,
97 struct interval_node *n2)
99 return extent_compare(&n1->in_extent, &n2->in_extent);
102 static inline int node_equal(struct interval_node *n1,
103 struct interval_node *n2)
105 return extent_equal(&n1->in_extent, &n2->in_extent);
108 static inline __u64 max_u64(__u64 x, __u64 y)
110 return x > y ? x : y;
113 static inline __u64 min_u64(__u64 x, __u64 y)
115 return x < y ? x : y;
118 #define interval_for_each(node, root) \
119 for (node = interval_first(root); node != NULL; \
120 node = interval_next(node))
122 #define interval_for_each_reverse(node, root) \
123 for (node = interval_last(root); node != NULL; \
124 node = interval_prev(node))
126 static struct interval_node *interval_first(struct interval_node *node)
132 while (node->in_left)
133 node = node->in_left;
137 static struct interval_node *interval_last(struct interval_node *node)
143 while (node->in_right)
144 node = node->in_right;
148 static struct interval_node *interval_next(struct interval_node *node)
155 RETURN(interval_first(node->in_right));
156 while (node->in_parent && node_is_right_child(node))
157 node = node->in_parent;
158 RETURN(node->in_parent);
161 static struct interval_node *interval_prev(struct interval_node *node)
169 RETURN(interval_last(node->in_left));
171 while (node->in_parent && node_is_left_child(node))
172 node = node->in_parent;
174 RETURN(node->in_parent);
177 enum interval_iter interval_iterate(struct interval_node *root,
178 interval_callback_t func,
181 struct interval_node *node;
182 enum interval_iter rc = INTERVAL_ITER_CONT;
185 interval_for_each(node, root) {
186 rc = func(node, data);
187 if (rc == INTERVAL_ITER_STOP)
193 EXPORT_SYMBOL(interval_iterate);
195 enum interval_iter interval_iterate_reverse(struct interval_node *root,
196 interval_callback_t func,
199 struct interval_node *node;
200 enum interval_iter rc = INTERVAL_ITER_CONT;
203 interval_for_each_reverse(node, root) {
204 rc = func(node, data);
205 if (rc == INTERVAL_ITER_STOP)
211 EXPORT_SYMBOL(interval_iterate_reverse);
213 /* try to find a node with same interval in the tree,
214 * if found, return the pointer to the node, otherwise return NULL*/
215 struct interval_node *interval_find(struct interval_node *root,
216 struct interval_node_extent *ex)
218 struct interval_node *walk = root;
223 rc = extent_compare(ex, &walk->in_extent);
227 walk = walk->in_left;
229 walk = walk->in_right;
234 EXPORT_SYMBOL(interval_find);
236 static void __rotate_change_maxhigh(struct interval_node *node,
237 struct interval_node *rotate)
239 __u64 left_max, right_max;
241 rotate->in_max_high = node->in_max_high;
242 left_max = node->in_left ? node->in_left->in_max_high : 0;
243 right_max = node->in_right ? node->in_right->in_max_high : 0;
244 node->in_max_high = max_u64(interval_high(node),
245 max_u64(left_max,right_max));
248 /* The left rotation "pivots" around the link from node to node->right, and
249 * - node will be linked to node->right's left child, and
250 * - node->right's left child will be linked to node's right child. */
251 static void __rotate_left(struct interval_node *node,
252 struct interval_node **root)
254 struct interval_node *right = node->in_right;
255 struct interval_node *parent = node->in_parent;
257 node->in_right = right->in_left;
259 right->in_left->in_parent = node;
261 right->in_left = node;
262 right->in_parent = parent;
264 if (node_is_left_child(node))
265 parent->in_left = right;
267 parent->in_right = right;
271 node->in_parent = right;
273 /* update max_high for node and right */
274 __rotate_change_maxhigh(node, right);
277 /* The right rotation "pivots" around the link from node to node->left, and
278 * - node will be linked to node->left's right child, and
279 * - node->left's right child will be linked to node's left child. */
280 static void __rotate_right(struct interval_node *node,
281 struct interval_node **root)
283 struct interval_node *left = node->in_left;
284 struct interval_node *parent = node->in_parent;
286 node->in_left = left->in_right;
288 left->in_right->in_parent = node;
289 left->in_right = node;
291 left->in_parent = parent;
293 if (node_is_right_child(node))
294 parent->in_right = left;
296 parent->in_left = left;
300 node->in_parent = left;
302 /* update max_high for node and left */
303 __rotate_change_maxhigh(node, left);
306 #define interval_swap(a, b) do { \
307 struct interval_node *c = a; a = b; b = c; \
311 * Operations INSERT and DELETE, when run on a tree with n keys,
312 * take O(logN) time.Because they modify the tree, the result
313 * may violate the red-black properties.To restore these properties,
314 * we must change the colors of some of the nodes in the tree
315 * and also change the pointer structure.
317 static void interval_insert_color(struct interval_node *node,
318 struct interval_node **root)
320 struct interval_node *parent, *gparent;
323 while ((parent = node->in_parent) && node_is_red(parent)) {
324 gparent = parent->in_parent;
325 /* Parent is RED, so gparent must not be NULL */
326 if (node_is_left_child(parent)) {
327 struct interval_node *uncle;
328 uncle = gparent->in_right;
329 if (uncle && node_is_red(uncle)) {
330 uncle->in_color = INTERVAL_BLACK;
331 parent->in_color = INTERVAL_BLACK;
332 gparent->in_color = INTERVAL_RED;
337 if (parent->in_right == node) {
338 __rotate_left(parent, root);
339 interval_swap(node, parent);
342 parent->in_color = INTERVAL_BLACK;
343 gparent->in_color = INTERVAL_RED;
344 __rotate_right(gparent, root);
346 struct interval_node *uncle;
347 uncle = gparent->in_left;
348 if (uncle && node_is_red(uncle)) {
349 uncle->in_color = INTERVAL_BLACK;
350 parent->in_color = INTERVAL_BLACK;
351 gparent->in_color = INTERVAL_RED;
356 if (node_is_left_child(node)) {
357 __rotate_right(parent, root);
358 interval_swap(node, parent);
361 parent->in_color = INTERVAL_BLACK;
362 gparent->in_color = INTERVAL_RED;
363 __rotate_left(gparent, root);
367 (*root)->in_color = INTERVAL_BLACK;
371 struct interval_node *interval_insert(struct interval_node *node,
372 struct interval_node **root)
375 struct interval_node **p, *parent = NULL;
381 if (node_equal(parent, node))
384 /* max_high field must be updated after each iteration */
385 if (parent->in_max_high < interval_high(node))
386 parent->in_max_high = interval_high(node);
388 if (node_compare(node, parent) < 0)
389 p = &parent->in_left;
391 p = &parent->in_right;
394 /* link node into the tree */
395 node->in_parent = parent;
396 node->in_color = INTERVAL_RED;
397 node->in_left = node->in_right = NULL;
400 interval_insert_color(node, root);
404 EXPORT_SYMBOL(interval_insert);
406 static inline int node_is_black_or_0(struct interval_node *node)
408 return !node || node_is_black(node);
411 static void interval_erase_color(struct interval_node *node,
412 struct interval_node *parent,
413 struct interval_node **root)
415 struct interval_node *tmp;
418 while (node_is_black_or_0(node) && node != *root) {
419 if (parent->in_left == node) {
420 tmp = parent->in_right;
421 if (node_is_red(tmp)) {
422 tmp->in_color = INTERVAL_BLACK;
423 parent->in_color = INTERVAL_RED;
424 __rotate_left(parent, root);
425 tmp = parent->in_right;
427 if (node_is_black_or_0(tmp->in_left) &&
428 node_is_black_or_0(tmp->in_right)) {
429 tmp->in_color = INTERVAL_RED;
431 parent = node->in_parent;
433 if (node_is_black_or_0(tmp->in_right)) {
434 struct interval_node *o_left;
435 if ((o_left = tmp->in_left))
436 o_left->in_color = INTERVAL_BLACK;
437 tmp->in_color = INTERVAL_RED;
438 __rotate_right(tmp, root);
439 tmp = parent->in_right;
441 tmp->in_color = parent->in_color;
442 parent->in_color = INTERVAL_BLACK;
444 tmp->in_right->in_color = INTERVAL_BLACK;
445 __rotate_left(parent, root);
450 tmp = parent->in_left;
451 if (node_is_red(tmp)) {
452 tmp->in_color = INTERVAL_BLACK;
453 parent->in_color = INTERVAL_RED;
454 __rotate_right(parent, root);
455 tmp = parent->in_left;
457 if (node_is_black_or_0(tmp->in_left) &&
458 node_is_black_or_0(tmp->in_right)) {
459 tmp->in_color = INTERVAL_RED;
461 parent = node->in_parent;
463 if (node_is_black_or_0(tmp->in_left)) {
464 struct interval_node *o_right;
465 if ((o_right = tmp->in_right))
466 o_right->in_color = INTERVAL_BLACK;
467 tmp->in_color = INTERVAL_RED;
468 __rotate_left(tmp, root);
469 tmp = parent->in_left;
471 tmp->in_color = parent->in_color;
472 parent->in_color = INTERVAL_BLACK;
474 tmp->in_left->in_color = INTERVAL_BLACK;
475 __rotate_right(parent, root);
482 node->in_color = INTERVAL_BLACK;
487 * if the @max_high value of @node is changed, this function traverse a path
488 * from node up to the root to update max_high for the whole tree.
490 static void update_maxhigh(struct interval_node *node,
493 __u64 left_max, right_max;
497 left_max = node->in_left ? node->in_left->in_max_high : 0;
498 right_max = node->in_right ? node->in_right->in_max_high : 0;
499 node->in_max_high = max_u64(interval_high(node),
500 max_u64(left_max, right_max));
502 if (node->in_max_high >= old_maxhigh)
504 node = node->in_parent;
509 void interval_erase(struct interval_node *node,
510 struct interval_node **root)
512 struct interval_node *child, *parent;
516 if (!node->in_left) {
517 child = node->in_right;
518 } else if (!node->in_right) {
519 child = node->in_left;
520 } else { /* Both left and right child are not NULL */
521 struct interval_node *old = node;
523 node = interval_next(node);
524 child = node->in_right;
525 parent = node->in_parent;
526 color = node->in_color;
529 child->in_parent = parent;
531 parent->in_right = child;
534 parent->in_left = child;
537 node->in_color = old->in_color;
538 node->in_right = old->in_right;
539 node->in_left = old->in_left;
540 node->in_parent = old->in_parent;
542 if (old->in_parent) {
543 if (node_is_left_child(old))
544 old->in_parent->in_left = node;
546 old->in_parent->in_right = node;
551 old->in_left->in_parent = node;
553 old->in_right->in_parent = node;
554 update_maxhigh(child, node->in_max_high);
555 update_maxhigh(node, old->in_max_high);
558 parent = node->in_parent;
559 color = node->in_color;
562 child->in_parent = parent;
564 if (node_is_left_child(node))
565 parent->in_left = child;
567 parent->in_right = child;
572 update_maxhigh(child, node->in_max_high);
575 if (color == INTERVAL_BLACK)
576 interval_erase_color(child, parent, root);
579 EXPORT_SYMBOL(interval_erase);
581 static inline int interval_may_overlap(struct interval_node *node,
582 struct interval_node_extent *ext)
584 return (ext->start <= node->in_max_high &&
585 ext->end >= interval_low(node));
589 * This function finds all intervals that overlap interval ext,
590 * and calls func to handle resulted intervals one by one.
591 * in lustre, this function will find all conflicting locks in
592 * the granted queue and add these locks to the ast work list.
597 * if (ext->end < interval_low(node)) {
598 * interval_search(node->in_left, ext, func, data);
599 * } else if (interval_may_overlap(node, ext)) {
600 * if (extent_overlapped(ext, &node->in_extent))
602 * interval_search(node->in_left, ext, func, data);
603 * interval_search(node->in_right, ext, func, data);
609 enum interval_iter interval_search(struct interval_node *node,
610 struct interval_node_extent *ext,
611 interval_callback_t func,
614 struct interval_node *parent;
615 enum interval_iter rc = INTERVAL_ITER_CONT;
617 LASSERT(ext != NULL);
618 LASSERT(func != NULL);
621 if (ext->end < interval_low(node)) {
623 node = node->in_left;
626 } else if (interval_may_overlap(node, ext)) {
627 if (extent_overlapped(ext, &node->in_extent)) {
628 rc = func(node, data);
629 if (rc == INTERVAL_ITER_STOP)
634 node = node->in_left;
637 if (node->in_right) {
638 node = node->in_right;
643 parent = node->in_parent;
645 if (node_is_left_child(node) &&
647 /* If we ever got the left, it means that the
648 * parent met ext->end<interval_low(parent), or
649 * may_overlap(parent). If the former is true,
650 * we needn't go back. So stop early and check
651 * may_overlap(parent) after this loop. */
652 node = parent->in_right;
656 parent = parent->in_parent;
658 if (parent == NULL || !interval_may_overlap(parent, ext))
664 EXPORT_SYMBOL(interval_search);
666 static enum interval_iter interval_overlap_cb(struct interval_node *n,
670 return INTERVAL_ITER_STOP;
673 int interval_is_overlapped(struct interval_node *root,
674 struct interval_node_extent *ext)
677 (void)interval_search(root, ext, interval_overlap_cb, &has);
680 EXPORT_SYMBOL(interval_is_overlapped);
682 /* Don't expand to low. Expanding downwards is expensive, and meaningless to
683 * some extents, because programs seldom do IO backward.
685 * The recursive algorithm of expanding low:
687 * struct interval_node *tmp;
688 * static __u64 res = 0;
692 * if (root->in_max_high < low) {
693 * res = max_u64(root->in_max_high + 1, res);
695 * } else if (low < interval_low(root)) {
696 * interval_expand_low(root->in_left, low);
700 * if (interval_high(root) < low)
701 * res = max_u64(interval_high(root) + 1, res);
702 * interval_expand_low(root->in_left, low);
703 * interval_expand_low(root->in_right, low);
708 * It's much easy to eliminate the recursion, see interval_search for
711 static inline __u64 interval_expand_low(struct interval_node *root, __u64 low)
713 /* we only concern the empty tree right now. */
719 static inline __u64 interval_expand_high(struct interval_node *node, __u64 high)
723 while (node != NULL) {
724 if (node->in_max_high < high)
727 if (interval_low(node) > high) {
728 result = interval_low(node) - 1;
729 node = node->in_left;
731 node = node->in_right;
738 /* expanding the extent based on @ext. */
739 void interval_expand(struct interval_node *root,
740 struct interval_node_extent *ext,
741 struct interval_node_extent *limiter)
743 /* The assertion of interval_is_overlapped is expensive because we may
744 * travel many nodes to find the overlapped node. */
745 LASSERT(interval_is_overlapped(root, ext) == 0);
746 if (!limiter || limiter->start < ext->start)
747 ext->start = interval_expand_low(root, ext->start);
748 if (!limiter || limiter->end > ext->end)
749 ext->end = interval_expand_high(root, ext->end);
750 LASSERT(interval_is_overlapped(root, ext) == 0);
752 EXPORT_SYMBOL(interval_expand);