4 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
6 * This program is free software; you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License version 2 only,
8 * as published by the Free Software Foundation.
10 * This program is distributed in the hope that it will be useful, but
11 * WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 * General Public License version 2 for more details (a copy is included
14 * in the LICENSE file that accompanied this code).
16 * You should have received a copy of the GNU General Public License
17 * version 2 along with this program; If not, see
18 * http://www.sun.com/software/products/lustre/docs/GPLv2.pdf
20 * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
21 * CA 95054 USA or visit www.sun.com if you need additional information or
27 * Copyright (c) 2008, 2010, Oracle and/or its affiliates. All rights reserved.
28 * Use is subject to license terms.
31 * This file is part of Lustre, http://www.lustre.org/
32 * Lustre is a trademark of Sun Microsystems, Inc.
34 * lustre/ldlm/interval_tree.c
36 * Interval tree library used by ldlm extent lock code
38 * Author: Huang Wei <huangwei@clusterfs.com>
39 * Author: Jay Xiong <jinshan.xiong@sun.com>
42 # include <lustre_dlm.h>
44 # include <libcfs/libcfs.h>
46 #include <interval_tree.h>
53 static inline int node_is_left_child(struct interval_node *node)
55 LASSERT(node->in_parent != NULL);
56 return node == node->in_parent->in_left;
59 static inline int node_is_right_child(struct interval_node *node)
61 LASSERT(node->in_parent != NULL);
62 return node == node->in_parent->in_right;
65 static inline int node_is_red(struct interval_node *node)
67 return node->in_color == INTERVAL_RED;
70 static inline int node_is_black(struct interval_node *node)
72 return node->in_color == INTERVAL_BLACK;
75 static inline int extent_compare(struct interval_node_extent *e1,
76 struct interval_node_extent *e2)
79 if (e1->start == e2->start) {
80 if (e1->end < e2->end)
82 else if (e1->end > e2->end)
87 if (e1->start < e2->start)
95 static inline int extent_equal(struct interval_node_extent *e1,
96 struct interval_node_extent *e2)
98 return (e1->start == e2->start) && (e1->end == e2->end);
101 static inline int extent_overlapped(struct interval_node_extent *e1,
102 struct interval_node_extent *e2)
104 return (e1->start <= e2->end) && (e2->start <= e1->end);
107 static inline int node_compare(struct interval_node *n1,
108 struct interval_node *n2)
110 return extent_compare(&n1->in_extent, &n2->in_extent);
113 int node_equal(struct interval_node *n1, struct interval_node *n2)
115 return extent_equal(&n1->in_extent, &n2->in_extent);
117 EXPORT_SYMBOL(node_equal);
119 static inline __u64 max_u64(__u64 x, __u64 y)
121 return x > y ? x : y;
124 static inline __u64 min_u64(__u64 x, __u64 y)
126 return x < y ? x : y;
129 #define interval_for_each(node, root) \
130 for (node = interval_first(root); node != NULL; \
131 node = interval_next(node))
133 #define interval_for_each_reverse(node, root) \
134 for (node = interval_last(root); node != NULL; \
135 node = interval_prev(node))
137 static struct interval_node *interval_first(struct interval_node *node)
143 while (node->in_left)
144 node = node->in_left;
148 static struct interval_node *interval_last(struct interval_node *node)
154 while (node->in_right)
155 node = node->in_right;
159 static struct interval_node *interval_next(struct interval_node *node)
166 RETURN(interval_first(node->in_right));
167 while (node->in_parent && node_is_right_child(node))
168 node = node->in_parent;
169 RETURN(node->in_parent);
172 static struct interval_node *interval_prev(struct interval_node *node)
180 RETURN(interval_last(node->in_left));
182 while (node->in_parent && node_is_left_child(node))
183 node = node->in_parent;
185 RETURN(node->in_parent);
188 enum interval_iter interval_iterate(struct interval_node *root,
189 interval_callback_t func,
192 struct interval_node *node;
193 enum interval_iter rc = INTERVAL_ITER_CONT;
196 interval_for_each(node, root) {
197 rc = func(node, data);
198 if (rc == INTERVAL_ITER_STOP)
204 EXPORT_SYMBOL(interval_iterate);
206 enum interval_iter interval_iterate_reverse(struct interval_node *root,
207 interval_callback_t func,
210 struct interval_node *node;
211 enum interval_iter rc = INTERVAL_ITER_CONT;
214 interval_for_each_reverse(node, root) {
215 rc = func(node, data);
216 if (rc == INTERVAL_ITER_STOP)
222 EXPORT_SYMBOL(interval_iterate_reverse);
224 /* try to find a node with same interval in the tree,
225 * if found, return the pointer to the node, otherwise return NULL*/
226 struct interval_node *interval_find(struct interval_node *root,
227 struct interval_node_extent *ex)
229 struct interval_node *walk = root;
234 rc = extent_compare(ex, &walk->in_extent);
238 walk = walk->in_left;
240 walk = walk->in_right;
245 EXPORT_SYMBOL(interval_find);
247 static void __rotate_change_maxhigh(struct interval_node *node,
248 struct interval_node *rotate)
250 __u64 left_max, right_max;
252 rotate->in_max_high = node->in_max_high;
253 left_max = node->in_left ? node->in_left->in_max_high : 0;
254 right_max = node->in_right ? node->in_right->in_max_high : 0;
255 node->in_max_high = max_u64(interval_high(node),
256 max_u64(left_max,right_max));
259 /* The left rotation "pivots" around the link from node to node->right, and
260 * - node will be linked to node->right's left child, and
261 * - node->right's left child will be linked to node's right child. */
262 static void __rotate_left(struct interval_node *node,
263 struct interval_node **root)
265 struct interval_node *right = node->in_right;
266 struct interval_node *parent = node->in_parent;
268 node->in_right = right->in_left;
270 right->in_left->in_parent = node;
272 right->in_left = node;
273 right->in_parent = parent;
275 if (node_is_left_child(node))
276 parent->in_left = right;
278 parent->in_right = right;
282 node->in_parent = right;
284 /* update max_high for node and right */
285 __rotate_change_maxhigh(node, right);
288 /* The right rotation "pivots" around the link from node to node->left, and
289 * - node will be linked to node->left's right child, and
290 * - node->left's right child will be linked to node's left child. */
291 static void __rotate_right(struct interval_node *node,
292 struct interval_node **root)
294 struct interval_node *left = node->in_left;
295 struct interval_node *parent = node->in_parent;
297 node->in_left = left->in_right;
299 left->in_right->in_parent = node;
300 left->in_right = node;
302 left->in_parent = parent;
304 if (node_is_right_child(node))
305 parent->in_right = left;
307 parent->in_left = left;
311 node->in_parent = left;
313 /* update max_high for node and left */
314 __rotate_change_maxhigh(node, left);
317 #define interval_swap(a, b) do { \
318 struct interval_node *c = a; a = b; b = c; \
322 * Operations INSERT and DELETE, when run on a tree with n keys,
323 * take O(logN) time.Because they modify the tree, the result
324 * may violate the red-black properties.To restore these properties,
325 * we must change the colors of some of the nodes in the tree
326 * and also change the pointer structure.
328 static void interval_insert_color(struct interval_node *node,
329 struct interval_node **root)
331 struct interval_node *parent, *gparent;
334 while ((parent = node->in_parent) && node_is_red(parent)) {
335 gparent = parent->in_parent;
336 /* Parent is RED, so gparent must not be NULL */
337 if (node_is_left_child(parent)) {
338 struct interval_node *uncle;
339 uncle = gparent->in_right;
340 if (uncle && node_is_red(uncle)) {
341 uncle->in_color = INTERVAL_BLACK;
342 parent->in_color = INTERVAL_BLACK;
343 gparent->in_color = INTERVAL_RED;
348 if (parent->in_right == node) {
349 __rotate_left(parent, root);
350 interval_swap(node, parent);
353 parent->in_color = INTERVAL_BLACK;
354 gparent->in_color = INTERVAL_RED;
355 __rotate_right(gparent, root);
357 struct interval_node *uncle;
358 uncle = gparent->in_left;
359 if (uncle && node_is_red(uncle)) {
360 uncle->in_color = INTERVAL_BLACK;
361 parent->in_color = INTERVAL_BLACK;
362 gparent->in_color = INTERVAL_RED;
367 if (node_is_left_child(node)) {
368 __rotate_right(parent, root);
369 interval_swap(node, parent);
372 parent->in_color = INTERVAL_BLACK;
373 gparent->in_color = INTERVAL_RED;
374 __rotate_left(gparent, root);
378 (*root)->in_color = INTERVAL_BLACK;
382 struct interval_node *interval_insert(struct interval_node *node,
383 struct interval_node **root)
386 struct interval_node **p, *parent = NULL;
389 LASSERT(!interval_is_intree(node));
393 if (node_equal(parent, node))
396 /* max_high field must be updated after each iteration */
397 if (parent->in_max_high < interval_high(node))
398 parent->in_max_high = interval_high(node);
400 if (node_compare(node, parent) < 0)
401 p = &parent->in_left;
403 p = &parent->in_right;
406 /* link node into the tree */
407 node->in_parent = parent;
408 node->in_color = INTERVAL_RED;
409 node->in_left = node->in_right = NULL;
412 interval_insert_color(node, root);
417 EXPORT_SYMBOL(interval_insert);
419 static inline int node_is_black_or_0(struct interval_node *node)
421 return !node || node_is_black(node);
424 static void interval_erase_color(struct interval_node *node,
425 struct interval_node *parent,
426 struct interval_node **root)
428 struct interval_node *tmp;
431 while (node_is_black_or_0(node) && node != *root) {
432 if (parent->in_left == node) {
433 tmp = parent->in_right;
434 if (node_is_red(tmp)) {
435 tmp->in_color = INTERVAL_BLACK;
436 parent->in_color = INTERVAL_RED;
437 __rotate_left(parent, root);
438 tmp = parent->in_right;
440 if (node_is_black_or_0(tmp->in_left) &&
441 node_is_black_or_0(tmp->in_right)) {
442 tmp->in_color = INTERVAL_RED;
444 parent = node->in_parent;
446 if (node_is_black_or_0(tmp->in_right)) {
447 struct interval_node *o_left;
448 if ((o_left = tmp->in_left))
449 o_left->in_color = INTERVAL_BLACK;
450 tmp->in_color = INTERVAL_RED;
451 __rotate_right(tmp, root);
452 tmp = parent->in_right;
454 tmp->in_color = parent->in_color;
455 parent->in_color = INTERVAL_BLACK;
457 tmp->in_right->in_color = INTERVAL_BLACK;
458 __rotate_left(parent, root);
463 tmp = parent->in_left;
464 if (node_is_red(tmp)) {
465 tmp->in_color = INTERVAL_BLACK;
466 parent->in_color = INTERVAL_RED;
467 __rotate_right(parent, root);
468 tmp = parent->in_left;
470 if (node_is_black_or_0(tmp->in_left) &&
471 node_is_black_or_0(tmp->in_right)) {
472 tmp->in_color = INTERVAL_RED;
474 parent = node->in_parent;
476 if (node_is_black_or_0(tmp->in_left)) {
477 struct interval_node *o_right;
478 if ((o_right = tmp->in_right))
479 o_right->in_color = INTERVAL_BLACK;
480 tmp->in_color = INTERVAL_RED;
481 __rotate_left(tmp, root);
482 tmp = parent->in_left;
484 tmp->in_color = parent->in_color;
485 parent->in_color = INTERVAL_BLACK;
487 tmp->in_left->in_color = INTERVAL_BLACK;
488 __rotate_right(parent, root);
495 node->in_color = INTERVAL_BLACK;
500 * if the @max_high value of @node is changed, this function traverse a path
501 * from node up to the root to update max_high for the whole tree.
503 static void update_maxhigh(struct interval_node *node,
506 __u64 left_max, right_max;
510 left_max = node->in_left ? node->in_left->in_max_high : 0;
511 right_max = node->in_right ? node->in_right->in_max_high : 0;
512 node->in_max_high = max_u64(interval_high(node),
513 max_u64(left_max, right_max));
515 if (node->in_max_high >= old_maxhigh)
517 node = node->in_parent;
522 void interval_erase(struct interval_node *node,
523 struct interval_node **root)
525 struct interval_node *child, *parent;
529 LASSERT(interval_is_intree(node));
531 if (!node->in_left) {
532 child = node->in_right;
533 } else if (!node->in_right) {
534 child = node->in_left;
535 } else { /* Both left and right child are not NULL */
536 struct interval_node *old = node;
538 node = interval_next(node);
539 child = node->in_right;
540 parent = node->in_parent;
541 color = node->in_color;
544 child->in_parent = parent;
546 parent->in_right = child;
548 parent->in_left = child;
550 node->in_color = old->in_color;
551 node->in_right = old->in_right;
552 node->in_left = old->in_left;
553 node->in_parent = old->in_parent;
555 if (old->in_parent) {
556 if (node_is_left_child(old))
557 old->in_parent->in_left = node;
559 old->in_parent->in_right = node;
564 old->in_left->in_parent = node;
566 old->in_right->in_parent = node;
567 update_maxhigh(child ? : parent, node->in_max_high);
568 update_maxhigh(node, old->in_max_high);
573 parent = node->in_parent;
574 color = node->in_color;
577 child->in_parent = parent;
579 if (node_is_left_child(node))
580 parent->in_left = child;
582 parent->in_right = child;
587 update_maxhigh(child ? : parent, node->in_max_high);
590 if (color == INTERVAL_BLACK)
591 interval_erase_color(child, parent, root);
594 EXPORT_SYMBOL(interval_erase);
596 static inline int interval_may_overlap(struct interval_node *node,
597 struct interval_node_extent *ext)
599 return (ext->start <= node->in_max_high &&
600 ext->end >= interval_low(node));
604 * This function finds all intervals that overlap interval ext,
605 * and calls func to handle resulted intervals one by one.
606 * in lustre, this function will find all conflicting locks in
607 * the granted queue and add these locks to the ast work list.
612 * if (ext->end < interval_low(node)) {
613 * interval_search(node->in_left, ext, func, data);
614 * } else if (interval_may_overlap(node, ext)) {
615 * if (extent_overlapped(ext, &node->in_extent))
617 * interval_search(node->in_left, ext, func, data);
618 * interval_search(node->in_right, ext, func, data);
624 enum interval_iter interval_search(struct interval_node *node,
625 struct interval_node_extent *ext,
626 interval_callback_t func,
629 struct interval_node *parent;
630 enum interval_iter rc = INTERVAL_ITER_CONT;
634 LASSERT(ext != NULL);
635 LASSERT(func != NULL);
638 if (ext->end < interval_low(node)) {
640 node = node->in_left;
643 } else if (interval_may_overlap(node, ext)) {
644 if (extent_overlapped(ext, &node->in_extent)) {
645 rc = func(node, data);
646 if (rc == INTERVAL_ITER_STOP)
651 node = node->in_left;
654 if (node->in_right) {
655 node = node->in_right;
660 parent = node->in_parent;
662 if (node_is_left_child(node) &&
664 /* If we ever got the left, it means that the
665 * parent met ext->end<interval_low(parent), or
666 * may_overlap(parent). If the former is true,
667 * we needn't go back. So stop early and check
668 * may_overlap(parent) after this loop. */
669 node = parent->in_right;
673 parent = parent->in_parent;
675 if (parent == NULL || !interval_may_overlap(parent, ext))
681 EXPORT_SYMBOL(interval_search);
683 static enum interval_iter interval_overlap_cb(struct interval_node *n,
687 return INTERVAL_ITER_STOP;
690 int interval_is_overlapped(struct interval_node *root,
691 struct interval_node_extent *ext)
694 (void)interval_search(root, ext, interval_overlap_cb, &has);
697 EXPORT_SYMBOL(interval_is_overlapped);
699 /* Don't expand to low. Expanding downwards is expensive, and meaningless to
700 * some extents, because programs seldom do IO backward.
702 * The recursive algorithm of expanding low:
704 * struct interval_node *tmp;
705 * static __u64 res = 0;
709 * if (root->in_max_high < low) {
710 * res = max_u64(root->in_max_high + 1, res);
712 * } else if (low < interval_low(root)) {
713 * interval_expand_low(root->in_left, low);
717 * if (interval_high(root) < low)
718 * res = max_u64(interval_high(root) + 1, res);
719 * interval_expand_low(root->in_left, low);
720 * interval_expand_low(root->in_right, low);
725 * It's much easy to eliminate the recursion, see interval_search for
728 static inline __u64 interval_expand_low(struct interval_node *root, __u64 low)
730 /* we only concern the empty tree right now. */
736 static inline __u64 interval_expand_high(struct interval_node *node, __u64 high)
740 while (node != NULL) {
741 if (node->in_max_high < high)
744 if (interval_low(node) > high) {
745 result = interval_low(node) - 1;
746 node = node->in_left;
748 node = node->in_right;
755 /* expanding the extent based on @ext. */
756 void interval_expand(struct interval_node *root,
757 struct interval_node_extent *ext,
758 struct interval_node_extent *limiter)
760 /* The assertion of interval_is_overlapped is expensive because we may
761 * travel many nodes to find the overlapped node. */
762 LASSERT(interval_is_overlapped(root, ext) == 0);
763 if (!limiter || limiter->start < ext->start)
764 ext->start = interval_expand_low(root, ext->start);
765 if (!limiter || limiter->end > ext->end)
766 ext->end = interval_expand_high(root, ext->end);
767 LASSERT(interval_is_overlapped(root, ext) == 0);
769 EXPORT_SYMBOL(interval_expand);