Whamcloud - gitweb
LU-2675 lustre: remove linux/obd_support.h
[fs/lustre-release.git] / lustre / ldlm / interval_tree.c
1 /*
2  * GPL HEADER START
3  *
4  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
5  *
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.
9  *
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).
15  *
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
19  *
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
22  * have any questions.
23  *
24  * GPL HEADER END
25  */
26 /*
27  * Copyright (c) 2008, 2010, Oracle and/or its affiliates. All rights reserved.
28  * Use is subject to license terms.
29  */
30 /*
31  * This file is part of Lustre, http://www.lustre.org/
32  * Lustre is a trademark of Sun Microsystems, Inc.
33  *
34  * lustre/ldlm/interval_tree.c
35  *
36  * Interval tree library used by ldlm extent lock code
37  *
38  * Author: Huang Wei <huangwei@clusterfs.com>
39  * Author: Jay Xiong <jinshan.xiong@sun.com>
40  */
41 #ifdef __KERNEL__
42 # include <lustre_dlm.h>
43 #else
44 # include <libcfs/libcfs.h>
45 #endif
46 #include <interval_tree.h>
47
48 enum {
49         INTERVAL_RED = 0,
50         INTERVAL_BLACK = 1
51 };
52
53 static inline int node_is_left_child(struct interval_node *node)
54 {
55         LASSERT(node->in_parent != NULL);
56         return node == node->in_parent->in_left;
57 }
58
59 static inline int node_is_right_child(struct interval_node *node)
60 {
61         LASSERT(node->in_parent != NULL);
62         return node == node->in_parent->in_right;
63 }
64
65 static inline int node_is_red(struct interval_node *node)
66 {
67         return node->in_color == INTERVAL_RED;
68 }
69
70 static inline int node_is_black(struct interval_node *node)
71 {
72         return node->in_color == INTERVAL_BLACK;
73 }
74
75 static inline int extent_compare(struct interval_node_extent *e1,
76                                  struct interval_node_extent *e2)
77 {
78         int rc;
79         if (e1->start == e2->start) {
80                 if (e1->end < e2->end)
81                         rc = -1;
82                 else if (e1->end > e2->end)
83                         rc = 1;
84                 else
85                         rc = 0;
86         } else {
87                 if (e1->start < e2->start)
88                         rc = -1;
89                 else
90                         rc = 1;
91         }
92         return rc;
93 }
94
95 static inline int extent_equal(struct interval_node_extent *e1,
96                                struct interval_node_extent *e2)
97 {
98         return (e1->start == e2->start) && (e1->end == e2->end);
99 }
100
101 static inline int extent_overlapped(struct interval_node_extent *e1,
102                                     struct interval_node_extent *e2)
103 {
104         return (e1->start <= e2->end) && (e2->start <= e1->end);
105 }
106
107 static inline int node_compare(struct interval_node *n1,
108                                struct interval_node *n2)
109 {
110         return extent_compare(&n1->in_extent, &n2->in_extent);
111 }
112
113 int node_equal(struct interval_node *n1, struct interval_node *n2)
114 {
115         return extent_equal(&n1->in_extent, &n2->in_extent);
116 }
117 EXPORT_SYMBOL(node_equal);
118
119 static inline __u64 max_u64(__u64 x, __u64 y)
120 {
121         return x > y ? x : y;
122 }
123
124 static inline __u64 min_u64(__u64 x, __u64 y)
125 {
126         return x < y ? x : y;
127 }
128
129 #define interval_for_each(node, root)                   \
130 for (node = interval_first(root); node != NULL;         \
131      node = interval_next(node))
132
133 #define interval_for_each_reverse(node, root)           \
134 for (node = interval_last(root); node != NULL;          \
135      node = interval_prev(node))
136
137 static struct interval_node *interval_first(struct interval_node *node)
138 {
139         ENTRY;
140
141         if (!node)
142                 RETURN(NULL);
143         while (node->in_left)
144                 node = node->in_left;
145         RETURN(node);
146 }
147
148 static struct interval_node *interval_last(struct interval_node *node)
149 {
150         ENTRY;
151
152         if (!node)
153                 RETURN(NULL);
154         while (node->in_right)
155                 node = node->in_right;
156         RETURN(node);
157 }
158
159 static struct interval_node *interval_next(struct interval_node *node)
160 {
161         ENTRY;
162
163         if (!node)
164                 RETURN(NULL);
165         if (node->in_right)
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);
170 }
171
172 static struct interval_node *interval_prev(struct interval_node *node)
173 {
174         ENTRY;
175
176         if (!node)
177                 RETURN(NULL);
178
179         if (node->in_left)
180                 RETURN(interval_last(node->in_left));
181
182         while (node->in_parent && node_is_left_child(node))
183                 node = node->in_parent;
184
185         RETURN(node->in_parent);
186 }
187
188 enum interval_iter interval_iterate(struct interval_node *root,
189                                     interval_callback_t func,
190                                     void *data)
191 {
192         struct interval_node *node;
193         enum interval_iter rc = INTERVAL_ITER_CONT;
194         ENTRY;
195         
196         interval_for_each(node, root) {
197                 rc = func(node, data);
198                 if (rc == INTERVAL_ITER_STOP)
199                         break;
200         }
201
202         RETURN(rc);
203 }
204 EXPORT_SYMBOL(interval_iterate);
205
206 enum interval_iter interval_iterate_reverse(struct interval_node *root,
207                                             interval_callback_t func,
208                                             void *data)
209 {
210         struct interval_node *node;
211         enum interval_iter rc = INTERVAL_ITER_CONT;
212         ENTRY;
213         
214         interval_for_each_reverse(node, root) {
215                 rc = func(node, data);
216                 if (rc == INTERVAL_ITER_STOP)
217                         break;
218         }
219
220         RETURN(rc);
221 }
222 EXPORT_SYMBOL(interval_iterate_reverse);
223
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)
228 {
229         struct interval_node *walk = root;
230         int rc;
231         ENTRY;
232
233         while (walk) {
234                 rc = extent_compare(ex, &walk->in_extent);
235                 if (rc == 0)
236                         break;
237                 else if (rc < 0)
238                         walk = walk->in_left;
239                 else
240                         walk = walk->in_right;
241         }
242
243         RETURN(walk);
244 }
245 EXPORT_SYMBOL(interval_find);
246
247 static void __rotate_change_maxhigh(struct interval_node *node,
248                                     struct interval_node *rotate)
249 {
250         __u64 left_max, right_max;
251
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));
257 }
258
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)
264 {
265         struct interval_node *right = node->in_right;
266         struct interval_node *parent = node->in_parent;
267
268         node->in_right = right->in_left;
269         if (node->in_right)
270                 right->in_left->in_parent = node;
271
272         right->in_left = node;
273         right->in_parent = parent;
274         if (parent) {
275                 if (node_is_left_child(node))
276                         parent->in_left = right;
277                 else
278                         parent->in_right = right;
279         } else {
280                 *root = right;
281         }
282         node->in_parent = right;
283
284         /* update max_high for node and right */
285         __rotate_change_maxhigh(node, right);
286 }
287
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)
293 {
294         struct interval_node *left = node->in_left;
295         struct interval_node *parent = node->in_parent;
296
297         node->in_left = left->in_right;
298         if (node->in_left)
299                 left->in_right->in_parent = node;
300         left->in_right = node;
301
302         left->in_parent = parent;
303         if (parent) {
304                 if (node_is_right_child(node))
305                         parent->in_right = left;
306                 else
307                         parent->in_left = left;
308         } else {
309                 *root = left;
310         }
311         node->in_parent = left;
312
313         /* update max_high for node and left */
314         __rotate_change_maxhigh(node, left);
315 }
316
317 #define interval_swap(a, b) do {                        \
318         struct interval_node *c = a; a = b; b = c;      \
319 } while (0)
320
321 /*
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.
327  */
328 static void interval_insert_color(struct interval_node *node,
329                                   struct interval_node **root)
330 {
331         struct interval_node *parent, *gparent;
332         ENTRY;
333
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;
344                                 node = gparent;
345                                 continue;
346                         }
347
348                         if (parent->in_right == node) {
349                                 __rotate_left(parent, root);
350                                 interval_swap(node, parent);
351                         }
352
353                         parent->in_color = INTERVAL_BLACK;
354                         gparent->in_color = INTERVAL_RED;
355                         __rotate_right(gparent, root);
356                 } else {
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;
363                                 node = gparent;
364                                 continue;
365                         }
366
367                         if (node_is_left_child(node)) {
368                                 __rotate_right(parent, root);
369                                 interval_swap(node, parent);
370                         }
371
372                         parent->in_color = INTERVAL_BLACK;
373                         gparent->in_color = INTERVAL_RED;
374                         __rotate_left(gparent, root);
375                 }
376         }
377
378         (*root)->in_color = INTERVAL_BLACK;
379         EXIT;
380 }
381
382 struct interval_node *interval_insert(struct interval_node *node,
383                                       struct interval_node **root)
384                      
385 {
386         struct interval_node **p, *parent = NULL;
387         ENTRY;
388
389         LASSERT(!interval_is_intree(node));
390         p = root;
391         while (*p) {
392                 parent = *p;
393                 if (node_equal(parent, node))
394                         RETURN(parent);
395
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);
399
400                 if (node_compare(node, parent) < 0)
401                         p = &parent->in_left;
402                 else 
403                         p = &parent->in_right;
404         }
405
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;
410         *p = node;
411
412         interval_insert_color(node, root);
413         node->in_intree = 1;
414
415         RETURN(NULL);
416 }
417 EXPORT_SYMBOL(interval_insert);
418
419 static inline int node_is_black_or_0(struct interval_node *node)
420 {
421         return !node || node_is_black(node);
422 }
423
424 static void interval_erase_color(struct interval_node *node,
425                                  struct interval_node *parent,
426                                  struct interval_node **root)
427 {
428         struct interval_node *tmp;
429         ENTRY;
430
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;
439                         }
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;
443                                 node = parent;
444                                 parent = node->in_parent;
445                         } else {
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;
453                                 }
454                                 tmp->in_color = parent->in_color;
455                                 parent->in_color = INTERVAL_BLACK;
456                                 if (tmp->in_right)
457                                     tmp->in_right->in_color = INTERVAL_BLACK;
458                                 __rotate_left(parent, root);
459                                 node = *root;
460                                 break;
461                         }
462                 } else {
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;
469                         }
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;
473                                 node = parent;
474                                 parent = node->in_parent;
475                         } else {
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;
483                                 }
484                                 tmp->in_color = parent->in_color;
485                                 parent->in_color = INTERVAL_BLACK;
486                                 if (tmp->in_left)
487                                         tmp->in_left->in_color = INTERVAL_BLACK;
488                                 __rotate_right(parent, root);
489                                 node = *root;
490                                 break;
491                         }
492                 }
493         }
494         if (node)
495                 node->in_color = INTERVAL_BLACK;
496         EXIT;
497 }
498
499 /* 
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.
502  */
503 static void update_maxhigh(struct interval_node *node,
504                            __u64  old_maxhigh)
505 {
506         __u64 left_max, right_max;
507         ENTRY;
508
509         while (node) {
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));
514
515                 if (node->in_max_high >= old_maxhigh)
516                         break;
517                 node = node->in_parent;
518         }
519         EXIT;
520 }
521
522 void interval_erase(struct interval_node *node,
523                     struct interval_node **root)
524 {
525         struct interval_node *child, *parent;
526         int color;
527         ENTRY;
528
529         LASSERT(interval_is_intree(node));
530         node->in_intree = 0;
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;
537
538                 node = interval_next(node);
539                 child = node->in_right;
540                 parent = node->in_parent;
541                 color = node->in_color;
542
543                 if (child)
544                         child->in_parent = parent;
545                 if (parent == old)
546                         parent->in_right = child;
547                 else
548                         parent->in_left = child;
549
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;
554
555                 if (old->in_parent) {
556                         if (node_is_left_child(old))
557                                 old->in_parent->in_left = node;
558                         else
559                                 old->in_parent->in_right = node;
560                 } else {
561                         *root = node;
562                 }
563
564                 old->in_left->in_parent = node;
565                 if (old->in_right)
566                         old->in_right->in_parent = node;
567                 update_maxhigh(child ? : parent, node->in_max_high);
568                 update_maxhigh(node, old->in_max_high);
569                 if (parent == old)
570                          parent = node;
571                 goto color;
572         }
573         parent = node->in_parent;
574         color = node->in_color;
575
576         if (child)
577                 child->in_parent = parent;
578         if (parent) {
579                 if (node_is_left_child(node))
580                         parent->in_left = child;
581                 else
582                         parent->in_right = child;
583         } else {
584                 *root = child;
585         }
586
587         update_maxhigh(child ? : parent, node->in_max_high);
588
589 color:
590         if (color == INTERVAL_BLACK)
591                 interval_erase_color(child, parent, root);
592         EXIT;
593 }
594 EXPORT_SYMBOL(interval_erase);
595
596 static inline int interval_may_overlap(struct interval_node *node,
597                                           struct interval_node_extent *ext)
598 {
599         return (ext->start <= node->in_max_high &&
600                 ext->end >= interval_low(node));
601 }
602
603 /*
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.
608  *
609  * {
610  *       if (node == NULL)
611  *               return 0;
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))
616  *                       func(node, data);
617  *               interval_search(node->in_left, ext, func, data);
618  *               interval_search(node->in_right, ext, func, data);
619  *       }
620  *       return 0;
621  * }
622  *
623  */
624 enum interval_iter interval_search(struct interval_node *node,
625                                    struct interval_node_extent *ext,
626                                    interval_callback_t func,
627                                    void *data)
628 {
629         struct interval_node *parent;
630         enum interval_iter rc = INTERVAL_ITER_CONT;
631
632         ENTRY;
633
634         LASSERT(ext != NULL);
635         LASSERT(func != NULL);
636
637         while (node) {
638                 if (ext->end < interval_low(node)) {
639                         if (node->in_left) {
640                                 node = node->in_left;
641                                 continue;
642                         }
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)
647                                         break;
648                         }
649
650                         if (node->in_left) {
651                                 node = node->in_left;
652                                 continue;
653                         }
654                         if (node->in_right) {
655                                 node = node->in_right;
656                                 continue;
657                         }
658                 }
659
660                 parent = node->in_parent;
661                 while (parent) {
662                         if (node_is_left_child(node) &&
663                             parent->in_right) {
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;
670                                 break;
671                         }
672                         node = parent;
673                         parent = parent->in_parent;
674                 }
675                 if (parent == NULL || !interval_may_overlap(parent, ext))
676                         break;
677         }
678
679         RETURN(rc);
680 }
681 EXPORT_SYMBOL(interval_search);
682
683 static enum interval_iter interval_overlap_cb(struct interval_node *n,
684                                               void *args)
685 {
686         *(int *)args = 1;
687         return INTERVAL_ITER_STOP;
688 }
689
690 int interval_is_overlapped(struct interval_node *root,
691                            struct interval_node_extent *ext)
692 {
693         int has = 0;
694         (void)interval_search(root, ext, interval_overlap_cb, &has);
695         return has;
696 }
697 EXPORT_SYMBOL(interval_is_overlapped);
698
699 /* Don't expand to low. Expanding downwards is expensive, and meaningless to
700  * some extents, because programs seldom do IO backward.
701  *
702  * The recursive algorithm of expanding low:
703  * expand_low {
704  *        struct interval_node *tmp;
705  *        static __u64 res = 0;
706  *
707  *        if (root == NULL)
708  *                return res;
709  *        if (root->in_max_high < low) {
710  *                res = max_u64(root->in_max_high + 1, res);
711  *                return res;
712  *        } else if (low < interval_low(root)) {
713  *                interval_expand_low(root->in_left, low);
714  *                return res;
715  *        }
716  *
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);
721  *
722  *        return res;
723  * }
724  *
725  * It's much easy to eliminate the recursion, see interval_search for 
726  * an example. -jay
727  */
728 static inline __u64 interval_expand_low(struct interval_node *root, __u64 low)
729 {
730         /* we only concern the empty tree right now. */
731         if (root == NULL)
732                 return 0;
733         return low;
734 }
735
736 static inline __u64 interval_expand_high(struct interval_node *node, __u64 high)
737 {
738         __u64 result = ~0;
739
740         while (node != NULL) {
741                 if (node->in_max_high < high)
742                         break;
743                         
744                 if (interval_low(node) > high) {
745                         result = interval_low(node) - 1;
746                         node = node->in_left;
747                 } else {
748                         node = node->in_right;
749                 }
750         }
751
752         return result;
753 }
754
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)
759 {
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);
768 }
769 EXPORT_SYMBOL(interval_expand);