1 /* -*- mode: c; c-basic-offset: 8; indent-tabs-mode: nil; -*-
2 * vim:expandtab:shiftwidth=8:tabstop=8:
6 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
8 * This program is free software; you can redistribute it and/or modify
9 * it under the terms of the GNU General Public License version 2 only,
10 * as published by the Free Software Foundation.
12 * This program is distributed in the hope that it will be useful, but
13 * WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 * General Public License version 2 for more details (a copy is included
16 * in the LICENSE file that accompanied this code).
18 * You should have received a copy of the GNU General Public License
19 * version 2 along with this program; If not, see
20 * http://www.sun.com/software/products/lustre/docs/GPLv2.pdf
22 * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
23 * CA 95054 USA or visit www.sun.com if you need additional information or
29 * Copyright 2008 Sun Microsystems, Inc. All rights reserved
30 * Use is subject to license terms.
33 * This file is part of Lustre, http://www.lustre.org/
34 * Lustre is a trademark of Sun Microsystems, Inc.
36 * lustre/ldlm/interval_tree.c
38 * Interval tree library used by ldlm extent lock code
40 * Author: Huang Wei <huangwei@clusterfs.com>
41 * Author: Jay Xiong <jinshan.xiong@sun.com>
44 # include <lustre_dlm.h>
46 # include <liblustre.h>
48 #include <obd_support.h>
49 #include <interval_tree.h>
56 static inline int node_is_left_child(struct interval_node *node)
58 LASSERT(node->in_parent != NULL);
59 return node == node->in_parent->in_left;
62 static inline int node_is_right_child(struct interval_node *node)
64 LASSERT(node->in_parent != NULL);
65 return node == node->in_parent->in_right;
68 static inline int node_is_red(struct interval_node *node)
70 return node->in_color == INTERVAL_RED;
73 static inline int node_is_black(struct interval_node *node)
75 return node->in_color == INTERVAL_BLACK;
78 static inline int extent_compare(struct interval_node_extent *e1,
79 struct interval_node_extent *e2)
82 if (e1->start == e2->start) {
83 if (e1->end < e2->end)
85 else if (e1->end > e2->end)
90 if (e1->start < e2->start)
98 static inline int extent_equal(struct interval_node_extent *e1,
99 struct interval_node_extent *e2)
101 return (e1->start == e2->start) && (e1->end == e2->end);
104 static inline int extent_overlapped(struct interval_node_extent *e1,
105 struct interval_node_extent *e2)
107 return (e1->start <= e2->end) && (e2->start <= e1->end);
110 static inline int node_compare(struct interval_node *n1,
111 struct interval_node *n2)
113 return extent_compare(&n1->in_extent, &n2->in_extent);
116 static inline int node_equal(struct interval_node *n1,
117 struct interval_node *n2)
119 return extent_equal(&n1->in_extent, &n2->in_extent);
122 static inline __u64 max_u64(__u64 x, __u64 y)
124 return x > y ? x : y;
127 static inline __u64 min_u64(__u64 x, __u64 y)
129 return x < y ? x : y;
132 #define interval_for_each(node, root) \
133 for (node = interval_first(root); node != NULL; \
134 node = interval_next(node))
136 #define interval_for_each_reverse(node, root) \
137 for (node = interval_last(root); node != NULL; \
138 node = interval_prev(node))
140 static struct interval_node *interval_first(struct interval_node *node)
146 while (node->in_left)
147 node = node->in_left;
151 static struct interval_node *interval_last(struct interval_node *node)
157 while (node->in_right)
158 node = node->in_right;
162 static struct interval_node *interval_next(struct interval_node *node)
169 RETURN(interval_first(node->in_right));
170 while (node->in_parent && node_is_right_child(node))
171 node = node->in_parent;
172 RETURN(node->in_parent);
175 static struct interval_node *interval_prev(struct interval_node *node)
183 RETURN(interval_last(node->in_left));
185 while (node->in_parent && node_is_left_child(node))
186 node = node->in_parent;
188 RETURN(node->in_parent);
191 enum interval_iter interval_iterate(struct interval_node *root,
192 interval_callback_t func,
195 struct interval_node *node;
196 enum interval_iter rc = INTERVAL_ITER_CONT;
199 interval_for_each(node, root) {
200 rc = func(node, data);
201 if (rc == INTERVAL_ITER_STOP)
207 EXPORT_SYMBOL(interval_iterate);
209 enum interval_iter interval_iterate_reverse(struct interval_node *root,
210 interval_callback_t func,
213 struct interval_node *node;
214 enum interval_iter rc = INTERVAL_ITER_CONT;
217 interval_for_each_reverse(node, root) {
218 rc = func(node, data);
219 if (rc == INTERVAL_ITER_STOP)
225 EXPORT_SYMBOL(interval_iterate_reverse);
227 /* try to find a node with same interval in the tree,
228 * if found, return the pointer to the node, otherwise return NULL*/
229 struct interval_node *interval_find(struct interval_node *root,
230 struct interval_node_extent *ex)
232 struct interval_node *walk = root;
237 rc = extent_compare(ex, &walk->in_extent);
241 walk = walk->in_left;
243 walk = walk->in_right;
248 EXPORT_SYMBOL(interval_find);
250 static void __rotate_change_maxhigh(struct interval_node *node,
251 struct interval_node *rotate)
253 __u64 left_max, right_max;
255 rotate->in_max_high = node->in_max_high;
256 left_max = node->in_left ? node->in_left->in_max_high : 0;
257 right_max = node->in_right ? node->in_right->in_max_high : 0;
258 node->in_max_high = max_u64(interval_high(node),
259 max_u64(left_max,right_max));
262 /* The left rotation "pivots" around the link from node to node->right, and
263 * - node will be linked to node->right's left child, and
264 * - node->right's left child will be linked to node's right child. */
265 static void __rotate_left(struct interval_node *node,
266 struct interval_node **root)
268 struct interval_node *right = node->in_right;
269 struct interval_node *parent = node->in_parent;
271 node->in_right = right->in_left;
273 right->in_left->in_parent = node;
275 right->in_left = node;
276 right->in_parent = parent;
278 if (node_is_left_child(node))
279 parent->in_left = right;
281 parent->in_right = right;
285 node->in_parent = right;
287 /* update max_high for node and right */
288 __rotate_change_maxhigh(node, right);
291 /* The right rotation "pivots" around the link from node to node->left, and
292 * - node will be linked to node->left's right child, and
293 * - node->left's right child will be linked to node's left child. */
294 static void __rotate_right(struct interval_node *node,
295 struct interval_node **root)
297 struct interval_node *left = node->in_left;
298 struct interval_node *parent = node->in_parent;
300 node->in_left = left->in_right;
302 left->in_right->in_parent = node;
303 left->in_right = node;
305 left->in_parent = parent;
307 if (node_is_right_child(node))
308 parent->in_right = left;
310 parent->in_left = left;
314 node->in_parent = left;
316 /* update max_high for node and left */
317 __rotate_change_maxhigh(node, left);
320 #define interval_swap(a, b) do { \
321 struct interval_node *c = a; a = b; b = c; \
325 * Operations INSERT and DELETE, when run on a tree with n keys,
326 * take O(logN) time.Because they modify the tree, the result
327 * may violate the red-black properties.To restore these properties,
328 * we must change the colors of some of the nodes in the tree
329 * and also change the pointer structure.
331 static void interval_insert_color(struct interval_node *node,
332 struct interval_node **root)
334 struct interval_node *parent, *gparent;
337 while ((parent = node->in_parent) && node_is_red(parent)) {
338 gparent = parent->in_parent;
339 /* Parent is RED, so gparent must not be NULL */
340 if (node_is_left_child(parent)) {
341 struct interval_node *uncle;
342 uncle = gparent->in_right;
343 if (uncle && node_is_red(uncle)) {
344 uncle->in_color = INTERVAL_BLACK;
345 parent->in_color = INTERVAL_BLACK;
346 gparent->in_color = INTERVAL_RED;
351 if (parent->in_right == node) {
352 __rotate_left(parent, root);
353 interval_swap(node, parent);
356 parent->in_color = INTERVAL_BLACK;
357 gparent->in_color = INTERVAL_RED;
358 __rotate_right(gparent, root);
360 struct interval_node *uncle;
361 uncle = gparent->in_left;
362 if (uncle && node_is_red(uncle)) {
363 uncle->in_color = INTERVAL_BLACK;
364 parent->in_color = INTERVAL_BLACK;
365 gparent->in_color = INTERVAL_RED;
370 if (node_is_left_child(node)) {
371 __rotate_right(parent, root);
372 interval_swap(node, parent);
375 parent->in_color = INTERVAL_BLACK;
376 gparent->in_color = INTERVAL_RED;
377 __rotate_left(gparent, root);
381 (*root)->in_color = INTERVAL_BLACK;
385 struct interval_node *interval_insert(struct interval_node *node,
386 struct interval_node **root)
389 struct interval_node **p, *parent = NULL;
392 LASSERT(!interval_is_intree(node));
396 if (node_equal(parent, node))
399 /* max_high field must be updated after each iteration */
400 if (parent->in_max_high < interval_high(node))
401 parent->in_max_high = interval_high(node);
403 if (node_compare(node, parent) < 0)
404 p = &parent->in_left;
406 p = &parent->in_right;
409 /* link node into the tree */
410 node->in_parent = parent;
411 node->in_color = INTERVAL_RED;
412 node->in_left = node->in_right = NULL;
415 interval_insert_color(node, root);
420 EXPORT_SYMBOL(interval_insert);
422 static inline int node_is_black_or_0(struct interval_node *node)
424 return !node || node_is_black(node);
427 static void interval_erase_color(struct interval_node *node,
428 struct interval_node *parent,
429 struct interval_node **root)
431 struct interval_node *tmp;
434 while (node_is_black_or_0(node) && node != *root) {
435 if (parent->in_left == node) {
436 tmp = parent->in_right;
437 if (node_is_red(tmp)) {
438 tmp->in_color = INTERVAL_BLACK;
439 parent->in_color = INTERVAL_RED;
440 __rotate_left(parent, root);
441 tmp = parent->in_right;
443 if (node_is_black_or_0(tmp->in_left) &&
444 node_is_black_or_0(tmp->in_right)) {
445 tmp->in_color = INTERVAL_RED;
447 parent = node->in_parent;
449 if (node_is_black_or_0(tmp->in_right)) {
450 struct interval_node *o_left;
451 if ((o_left = tmp->in_left))
452 o_left->in_color = INTERVAL_BLACK;
453 tmp->in_color = INTERVAL_RED;
454 __rotate_right(tmp, root);
455 tmp = parent->in_right;
457 tmp->in_color = parent->in_color;
458 parent->in_color = INTERVAL_BLACK;
460 tmp->in_right->in_color = INTERVAL_BLACK;
461 __rotate_left(parent, root);
466 tmp = parent->in_left;
467 if (node_is_red(tmp)) {
468 tmp->in_color = INTERVAL_BLACK;
469 parent->in_color = INTERVAL_RED;
470 __rotate_right(parent, root);
471 tmp = parent->in_left;
473 if (node_is_black_or_0(tmp->in_left) &&
474 node_is_black_or_0(tmp->in_right)) {
475 tmp->in_color = INTERVAL_RED;
477 parent = node->in_parent;
479 if (node_is_black_or_0(tmp->in_left)) {
480 struct interval_node *o_right;
481 if ((o_right = tmp->in_right))
482 o_right->in_color = INTERVAL_BLACK;
483 tmp->in_color = INTERVAL_RED;
484 __rotate_left(tmp, root);
485 tmp = parent->in_left;
487 tmp->in_color = parent->in_color;
488 parent->in_color = INTERVAL_BLACK;
490 tmp->in_left->in_color = INTERVAL_BLACK;
491 __rotate_right(parent, root);
498 node->in_color = INTERVAL_BLACK;
503 * if the @max_high value of @node is changed, this function traverse a path
504 * from node up to the root to update max_high for the whole tree.
506 static void update_maxhigh(struct interval_node *node,
509 __u64 left_max, right_max;
513 left_max = node->in_left ? node->in_left->in_max_high : 0;
514 right_max = node->in_right ? node->in_right->in_max_high : 0;
515 node->in_max_high = max_u64(interval_high(node),
516 max_u64(left_max, right_max));
518 if (node->in_max_high >= old_maxhigh)
520 node = node->in_parent;
525 void interval_erase(struct interval_node *node,
526 struct interval_node **root)
528 struct interval_node *child, *parent;
532 LASSERT(interval_is_intree(node));
534 if (!node->in_left) {
535 child = node->in_right;
536 } else if (!node->in_right) {
537 child = node->in_left;
538 } else { /* Both left and right child are not NULL */
539 struct interval_node *old = node;
541 node = interval_next(node);
542 child = node->in_right;
543 parent = node->in_parent;
544 color = node->in_color;
547 child->in_parent = parent;
549 parent->in_right = child;
551 parent->in_left = child;
553 node->in_color = old->in_color;
554 node->in_right = old->in_right;
555 node->in_left = old->in_left;
556 node->in_parent = old->in_parent;
558 if (old->in_parent) {
559 if (node_is_left_child(old))
560 old->in_parent->in_left = node;
562 old->in_parent->in_right = node;
567 old->in_left->in_parent = node;
569 old->in_right->in_parent = node;
570 update_maxhigh(child ? : parent, node->in_max_high);
571 update_maxhigh(node, old->in_max_high);
576 parent = node->in_parent;
577 color = node->in_color;
580 child->in_parent = parent;
582 if (node_is_left_child(node))
583 parent->in_left = child;
585 parent->in_right = child;
590 update_maxhigh(child ? : parent, node->in_max_high);
593 if (color == INTERVAL_BLACK)
594 interval_erase_color(child, parent, root);
597 EXPORT_SYMBOL(interval_erase);
599 static inline int interval_may_overlap(struct interval_node *node,
600 struct interval_node_extent *ext)
602 return (ext->start <= node->in_max_high &&
603 ext->end >= interval_low(node));
607 * This function finds all intervals that overlap interval ext,
608 * and calls func to handle resulted intervals one by one.
609 * in lustre, this function will find all conflicting locks in
610 * the granted queue and add these locks to the ast work list.
615 * if (ext->end < interval_low(node)) {
616 * interval_search(node->in_left, ext, func, data);
617 * } else if (interval_may_overlap(node, ext)) {
618 * if (extent_overlapped(ext, &node->in_extent))
620 * interval_search(node->in_left, ext, func, data);
621 * interval_search(node->in_right, ext, func, data);
627 enum interval_iter interval_search(struct interval_node *node,
628 struct interval_node_extent *ext,
629 interval_callback_t func,
632 struct interval_node *parent;
633 enum interval_iter rc = INTERVAL_ITER_CONT;
635 LASSERT(ext != NULL);
636 LASSERT(func != NULL);
639 if (ext->end < interval_low(node)) {
641 node = node->in_left;
644 } else if (interval_may_overlap(node, ext)) {
645 if (extent_overlapped(ext, &node->in_extent)) {
646 rc = func(node, data);
647 if (rc == INTERVAL_ITER_STOP)
652 node = node->in_left;
655 if (node->in_right) {
656 node = node->in_right;
661 parent = node->in_parent;
663 if (node_is_left_child(node) &&
665 /* If we ever got the left, it means that the
666 * parent met ext->end<interval_low(parent), or
667 * may_overlap(parent). If the former is true,
668 * we needn't go back. So stop early and check
669 * may_overlap(parent) after this loop. */
670 node = parent->in_right;
674 parent = parent->in_parent;
676 if (parent == NULL || !interval_may_overlap(parent, ext))
682 EXPORT_SYMBOL(interval_search);
684 static enum interval_iter interval_overlap_cb(struct interval_node *n,
688 return INTERVAL_ITER_STOP;
691 int interval_is_overlapped(struct interval_node *root,
692 struct interval_node_extent *ext)
695 (void)interval_search(root, ext, interval_overlap_cb, &has);
698 EXPORT_SYMBOL(interval_is_overlapped);
700 /* Don't expand to low. Expanding downwards is expensive, and meaningless to
701 * some extents, because programs seldom do IO backward.
703 * The recursive algorithm of expanding low:
705 * struct interval_node *tmp;
706 * static __u64 res = 0;
710 * if (root->in_max_high < low) {
711 * res = max_u64(root->in_max_high + 1, res);
713 * } else if (low < interval_low(root)) {
714 * interval_expand_low(root->in_left, low);
718 * if (interval_high(root) < low)
719 * res = max_u64(interval_high(root) + 1, res);
720 * interval_expand_low(root->in_left, low);
721 * interval_expand_low(root->in_right, low);
726 * It's much easy to eliminate the recursion, see interval_search for
729 static inline __u64 interval_expand_low(struct interval_node *root, __u64 low)
731 /* we only concern the empty tree right now. */
737 static inline __u64 interval_expand_high(struct interval_node *node, __u64 high)
741 while (node != NULL) {
742 if (node->in_max_high < high)
745 if (interval_low(node) > high) {
746 result = interval_low(node) - 1;
747 node = node->in_left;
749 node = node->in_right;
756 /* expanding the extent based on @ext. */
757 void interval_expand(struct interval_node *root,
758 struct interval_node_extent *ext,
759 struct interval_node_extent *limiter)
761 /* The assertion of interval_is_overlapped is expensive because we may
762 * travel many nodes to find the overlapped node. */
763 LASSERT(interval_is_overlapped(root, ext) == 0);
764 if (!limiter || limiter->start < ext->start)
765 ext->start = interval_expand_low(root, ext->start);
766 if (!limiter || limiter->end > ext->end)
767 ext->end = interval_expand_high(root, ext->end);
768 LASSERT(interval_is_overlapped(root, ext) == 0);
770 EXPORT_SYMBOL(interval_expand);