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>
47 # include <libcfs/kp30.h>
49 #include <obd_support.h>
50 #include <interval_tree.h>
57 static inline int node_is_left_child(struct interval_node *node)
59 LASSERT(node->in_parent != NULL);
60 return node == node->in_parent->in_left;
63 static inline int node_is_right_child(struct interval_node *node)
65 LASSERT(node->in_parent != NULL);
66 return node == node->in_parent->in_right;
69 static inline int node_is_red(struct interval_node *node)
71 return node->in_color == INTERVAL_RED;
74 static inline int node_is_black(struct interval_node *node)
76 return node->in_color == INTERVAL_BLACK;
79 static inline int extent_compare(struct interval_node_extent *e1,
80 struct interval_node_extent *e2)
83 if (e1->start == e2->start) {
84 if (e1->end < e2->end)
86 else if (e1->end > e2->end)
91 if (e1->start < e2->start)
99 static inline int extent_equal(struct interval_node_extent *e1,
100 struct interval_node_extent *e2)
102 return (e1->start == e2->start) && (e1->end == e2->end);
105 static inline int extent_overlapped(struct interval_node_extent *e1,
106 struct interval_node_extent *e2)
108 return (e1->start <= e2->end) && (e2->start <= e1->end);
111 static inline int node_compare(struct interval_node *n1,
112 struct interval_node *n2)
114 return extent_compare(&n1->in_extent, &n2->in_extent);
117 static inline int node_equal(struct interval_node *n1,
118 struct interval_node *n2)
120 return extent_equal(&n1->in_extent, &n2->in_extent);
123 static inline __u64 max_u64(__u64 x, __u64 y)
125 return x > y ? x : y;
128 static inline __u64 min_u64(__u64 x, __u64 y)
130 return x < y ? x : y;
133 #define interval_for_each(node, root) \
134 for (node = interval_first(root); node != NULL; \
135 node = interval_next(node))
137 #define interval_for_each_reverse(node, root) \
138 for (node = interval_last(root); node != NULL; \
139 node = interval_prev(node))
141 static struct interval_node *interval_first(struct interval_node *node)
147 while (node->in_left)
148 node = node->in_left;
152 static struct interval_node *interval_last(struct interval_node *node)
158 while (node->in_right)
159 node = node->in_right;
163 static struct interval_node *interval_next(struct interval_node *node)
170 RETURN(interval_first(node->in_right));
171 while (node->in_parent && node_is_right_child(node))
172 node = node->in_parent;
173 RETURN(node->in_parent);
176 static struct interval_node *interval_prev(struct interval_node *node)
184 RETURN(interval_last(node->in_left));
186 while (node->in_parent && node_is_left_child(node))
187 node = node->in_parent;
189 RETURN(node->in_parent);
192 enum interval_iter interval_iterate(struct interval_node *root,
193 interval_callback_t func,
196 struct interval_node *node;
197 enum interval_iter rc = INTERVAL_ITER_CONT;
200 interval_for_each(node, root) {
201 rc = func(node, data);
202 if (rc == INTERVAL_ITER_STOP)
208 EXPORT_SYMBOL(interval_iterate);
210 enum interval_iter interval_iterate_reverse(struct interval_node *root,
211 interval_callback_t func,
214 struct interval_node *node;
215 enum interval_iter rc = INTERVAL_ITER_CONT;
218 interval_for_each_reverse(node, root) {
219 rc = func(node, data);
220 if (rc == INTERVAL_ITER_STOP)
226 EXPORT_SYMBOL(interval_iterate_reverse);
228 /* try to find a node with same interval in the tree,
229 * if found, return the pointer to the node, otherwise return NULL*/
230 struct interval_node *interval_find(struct interval_node *root,
231 struct interval_node_extent *ex)
233 struct interval_node *walk = root;
238 rc = extent_compare(ex, &walk->in_extent);
242 walk = walk->in_left;
244 walk = walk->in_right;
249 EXPORT_SYMBOL(interval_find);
251 static void __rotate_change_maxhigh(struct interval_node *node,
252 struct interval_node *rotate)
254 __u64 left_max, right_max;
256 rotate->in_max_high = node->in_max_high;
257 left_max = node->in_left ? node->in_left->in_max_high : 0;
258 right_max = node->in_right ? node->in_right->in_max_high : 0;
259 node->in_max_high = max_u64(interval_high(node),
260 max_u64(left_max,right_max));
263 /* The left rotation "pivots" around the link from node to node->right, and
264 * - node will be linked to node->right's left child, and
265 * - node->right's left child will be linked to node's right child. */
266 static void __rotate_left(struct interval_node *node,
267 struct interval_node **root)
269 struct interval_node *right = node->in_right;
270 struct interval_node *parent = node->in_parent;
272 node->in_right = right->in_left;
274 right->in_left->in_parent = node;
276 right->in_left = node;
277 right->in_parent = parent;
279 if (node_is_left_child(node))
280 parent->in_left = right;
282 parent->in_right = right;
286 node->in_parent = right;
288 /* update max_high for node and right */
289 __rotate_change_maxhigh(node, right);
292 /* The right rotation "pivots" around the link from node to node->left, and
293 * - node will be linked to node->left's right child, and
294 * - node->left's right child will be linked to node's left child. */
295 static void __rotate_right(struct interval_node *node,
296 struct interval_node **root)
298 struct interval_node *left = node->in_left;
299 struct interval_node *parent = node->in_parent;
301 node->in_left = left->in_right;
303 left->in_right->in_parent = node;
304 left->in_right = node;
306 left->in_parent = parent;
308 if (node_is_right_child(node))
309 parent->in_right = left;
311 parent->in_left = left;
315 node->in_parent = left;
317 /* update max_high for node and left */
318 __rotate_change_maxhigh(node, left);
321 #define interval_swap(a, b) do { \
322 struct interval_node *c = a; a = b; b = c; \
326 * Operations INSERT and DELETE, when run on a tree with n keys,
327 * take O(logN) time.Because they modify the tree, the result
328 * may violate the red-black properties.To restore these properties,
329 * we must change the colors of some of the nodes in the tree
330 * and also change the pointer structure.
332 static void interval_insert_color(struct interval_node *node,
333 struct interval_node **root)
335 struct interval_node *parent, *gparent;
338 while ((parent = node->in_parent) && node_is_red(parent)) {
339 gparent = parent->in_parent;
340 /* Parent is RED, so gparent must not be NULL */
341 if (node_is_left_child(parent)) {
342 struct interval_node *uncle;
343 uncle = gparent->in_right;
344 if (uncle && node_is_red(uncle)) {
345 uncle->in_color = INTERVAL_BLACK;
346 parent->in_color = INTERVAL_BLACK;
347 gparent->in_color = INTERVAL_RED;
352 if (parent->in_right == node) {
353 __rotate_left(parent, root);
354 interval_swap(node, parent);
357 parent->in_color = INTERVAL_BLACK;
358 gparent->in_color = INTERVAL_RED;
359 __rotate_right(gparent, root);
361 struct interval_node *uncle;
362 uncle = gparent->in_left;
363 if (uncle && node_is_red(uncle)) {
364 uncle->in_color = INTERVAL_BLACK;
365 parent->in_color = INTERVAL_BLACK;
366 gparent->in_color = INTERVAL_RED;
371 if (node_is_left_child(node)) {
372 __rotate_right(parent, root);
373 interval_swap(node, parent);
376 parent->in_color = INTERVAL_BLACK;
377 gparent->in_color = INTERVAL_RED;
378 __rotate_left(gparent, root);
382 (*root)->in_color = INTERVAL_BLACK;
386 struct interval_node *interval_insert(struct interval_node *node,
387 struct interval_node **root)
390 struct interval_node **p, *parent = NULL;
393 LASSERT(!interval_is_intree(node));
397 if (node_equal(parent, node))
400 /* max_high field must be updated after each iteration */
401 if (parent->in_max_high < interval_high(node))
402 parent->in_max_high = interval_high(node);
404 if (node_compare(node, parent) < 0)
405 p = &parent->in_left;
407 p = &parent->in_right;
410 /* link node into the tree */
411 node->in_parent = parent;
412 node->in_color = INTERVAL_RED;
413 node->in_left = node->in_right = NULL;
416 interval_insert_color(node, root);
421 EXPORT_SYMBOL(interval_insert);
423 static inline int node_is_black_or_0(struct interval_node *node)
425 return !node || node_is_black(node);
428 static void interval_erase_color(struct interval_node *node,
429 struct interval_node *parent,
430 struct interval_node **root)
432 struct interval_node *tmp;
435 while (node_is_black_or_0(node) && node != *root) {
436 if (parent->in_left == node) {
437 tmp = parent->in_right;
438 if (node_is_red(tmp)) {
439 tmp->in_color = INTERVAL_BLACK;
440 parent->in_color = INTERVAL_RED;
441 __rotate_left(parent, root);
442 tmp = parent->in_right;
444 if (node_is_black_or_0(tmp->in_left) &&
445 node_is_black_or_0(tmp->in_right)) {
446 tmp->in_color = INTERVAL_RED;
448 parent = node->in_parent;
450 if (node_is_black_or_0(tmp->in_right)) {
451 struct interval_node *o_left;
452 if ((o_left = tmp->in_left))
453 o_left->in_color = INTERVAL_BLACK;
454 tmp->in_color = INTERVAL_RED;
455 __rotate_right(tmp, root);
456 tmp = parent->in_right;
458 tmp->in_color = parent->in_color;
459 parent->in_color = INTERVAL_BLACK;
461 tmp->in_right->in_color = INTERVAL_BLACK;
462 __rotate_left(parent, root);
467 tmp = parent->in_left;
468 if (node_is_red(tmp)) {
469 tmp->in_color = INTERVAL_BLACK;
470 parent->in_color = INTERVAL_RED;
471 __rotate_right(parent, root);
472 tmp = parent->in_left;
474 if (node_is_black_or_0(tmp->in_left) &&
475 node_is_black_or_0(tmp->in_right)) {
476 tmp->in_color = INTERVAL_RED;
478 parent = node->in_parent;
480 if (node_is_black_or_0(tmp->in_left)) {
481 struct interval_node *o_right;
482 if ((o_right = tmp->in_right))
483 o_right->in_color = INTERVAL_BLACK;
484 tmp->in_color = INTERVAL_RED;
485 __rotate_left(tmp, root);
486 tmp = parent->in_left;
488 tmp->in_color = parent->in_color;
489 parent->in_color = INTERVAL_BLACK;
491 tmp->in_left->in_color = INTERVAL_BLACK;
492 __rotate_right(parent, root);
499 node->in_color = INTERVAL_BLACK;
504 * if the @max_high value of @node is changed, this function traverse a path
505 * from node up to the root to update max_high for the whole tree.
507 static void update_maxhigh(struct interval_node *node,
510 __u64 left_max, right_max;
514 left_max = node->in_left ? node->in_left->in_max_high : 0;
515 right_max = node->in_right ? node->in_right->in_max_high : 0;
516 node->in_max_high = max_u64(interval_high(node),
517 max_u64(left_max, right_max));
519 if (node->in_max_high >= old_maxhigh)
521 node = node->in_parent;
526 void interval_erase(struct interval_node *node,
527 struct interval_node **root)
529 struct interval_node *child, *parent;
533 LASSERT(interval_is_intree(node));
535 if (!node->in_left) {
536 child = node->in_right;
537 } else if (!node->in_right) {
538 child = node->in_left;
539 } else { /* Both left and right child are not NULL */
540 struct interval_node *old = node;
542 node = interval_next(node);
543 child = node->in_right;
544 parent = node->in_parent;
545 color = node->in_color;
548 child->in_parent = parent;
550 parent->in_right = child;
553 parent->in_left = child;
556 node->in_color = old->in_color;
557 node->in_right = old->in_right;
558 node->in_left = old->in_left;
559 node->in_parent = old->in_parent;
561 if (old->in_parent) {
562 if (node_is_left_child(old))
563 old->in_parent->in_left = node;
565 old->in_parent->in_right = node;
570 old->in_left->in_parent = node;
572 old->in_right->in_parent = node;
573 update_maxhigh(child, node->in_max_high);
574 update_maxhigh(node, old->in_max_high);
577 parent = node->in_parent;
578 color = node->in_color;
581 child->in_parent = parent;
583 if (node_is_left_child(node))
584 parent->in_left = child;
586 parent->in_right = child;
591 update_maxhigh(child, node->in_max_high);
594 if (color == INTERVAL_BLACK)
595 interval_erase_color(child, parent, root);
598 EXPORT_SYMBOL(interval_erase);
600 static inline int interval_may_overlap(struct interval_node *node,
601 struct interval_node_extent *ext)
603 return (ext->start <= node->in_max_high &&
604 ext->end >= interval_low(node));
608 * This function finds all intervals that overlap interval ext,
609 * and calls func to handle resulted intervals one by one.
610 * in lustre, this function will find all conflicting locks in
611 * the granted queue and add these locks to the ast work list.
616 * if (ext->end < interval_low(node)) {
617 * interval_search(node->in_left, ext, func, data);
618 * } else if (interval_may_overlap(node, ext)) {
619 * if (extent_overlapped(ext, &node->in_extent))
621 * interval_search(node->in_left, ext, func, data);
622 * interval_search(node->in_right, ext, func, data);
628 enum interval_iter interval_search(struct interval_node *node,
629 struct interval_node_extent *ext,
630 interval_callback_t func,
633 struct interval_node *parent;
634 enum interval_iter rc = INTERVAL_ITER_CONT;
636 LASSERT(ext != NULL);
637 LASSERT(func != NULL);
640 if (ext->end < interval_low(node)) {
642 node = node->in_left;
645 } else if (interval_may_overlap(node, ext)) {
646 if (extent_overlapped(ext, &node->in_extent)) {
647 rc = func(node, data);
648 if (rc == INTERVAL_ITER_STOP)
653 node = node->in_left;
656 if (node->in_right) {
657 node = node->in_right;
662 parent = node->in_parent;
664 if (node_is_left_child(node) &&
666 /* If we ever got the left, it means that the
667 * parent met ext->end<interval_low(parent), or
668 * may_overlap(parent). If the former is true,
669 * we needn't go back. So stop early and check
670 * may_overlap(parent) after this loop. */
671 node = parent->in_right;
675 parent = parent->in_parent;
677 if (parent == NULL || !interval_may_overlap(parent, ext))
683 EXPORT_SYMBOL(interval_search);
685 static enum interval_iter interval_overlap_cb(struct interval_node *n,
689 return INTERVAL_ITER_STOP;
692 int interval_is_overlapped(struct interval_node *root,
693 struct interval_node_extent *ext)
696 (void)interval_search(root, ext, interval_overlap_cb, &has);
699 EXPORT_SYMBOL(interval_is_overlapped);
701 /* Don't expand to low. Expanding downwards is expensive, and meaningless to
702 * some extents, because programs seldom do IO backward.
704 * The recursive algorithm of expanding low:
706 * struct interval_node *tmp;
707 * static __u64 res = 0;
711 * if (root->in_max_high < low) {
712 * res = max_u64(root->in_max_high + 1, res);
714 * } else if (low < interval_low(root)) {
715 * interval_expand_low(root->in_left, low);
719 * if (interval_high(root) < low)
720 * res = max_u64(interval_high(root) + 1, res);
721 * interval_expand_low(root->in_left, low);
722 * interval_expand_low(root->in_right, low);
727 * It's much easy to eliminate the recursion, see interval_search for
730 static inline __u64 interval_expand_low(struct interval_node *root, __u64 low)
732 /* we only concern the empty tree right now. */
738 static inline __u64 interval_expand_high(struct interval_node *node, __u64 high)
742 while (node != NULL) {
743 if (node->in_max_high < high)
746 if (interval_low(node) > high) {
747 result = interval_low(node) - 1;
748 node = node->in_left;
750 node = node->in_right;
757 /* expanding the extent based on @ext. */
758 void interval_expand(struct interval_node *root,
759 struct interval_node_extent *ext,
760 struct interval_node_extent *limiter)
762 /* The assertion of interval_is_overlapped is expensive because we may
763 * travel many nodes to find the overlapped node. */
764 LASSERT(interval_is_overlapped(root, ext) == 0);
765 if (!limiter || limiter->start < ext->start)
766 ext->start = interval_expand_low(root, ext->start);
767 if (!limiter || limiter->end > ext->end)
768 ext->end = interval_expand_high(root, ext->end);
769 LASSERT(interval_is_overlapped(root, ext) == 0);
771 EXPORT_SYMBOL(interval_expand);