Whamcloud - gitweb
LU-6245 tests: remove it_test
[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.gnu.org/licenses/gpl-2.0.html
19  *
20  * GPL HEADER END
21  */
22 /*
23  * Copyright (c) 2008, 2010, Oracle and/or its affiliates. All rights reserved.
24  * Use is subject to license terms.
25  *
26  * Copyright (c) 2014, Intel Corporation.
27  */
28 /*
29  * This file is part of Lustre, http://www.lustre.org/
30  * Lustre is a trademark of Sun Microsystems, Inc.
31  *
32  * lustre/ldlm/interval_tree.c
33  *
34  * Interval tree library used by ldlm extent lock code
35  *
36  * Author: Huang Wei <huangwei@clusterfs.com>
37  * Author: Jay Xiong <jinshan.xiong@sun.com>
38  */
39
40 #include <lustre_dlm.h>
41 #include <interval_tree.h>
42
43 enum {
44         INTERVAL_RED = 0,
45         INTERVAL_BLACK = 1
46 };
47
48 static inline int node_is_left_child(struct interval_node *node)
49 {
50         LASSERT(node->in_parent != NULL);
51         return node == node->in_parent->in_left;
52 }
53
54 static inline int node_is_right_child(struct interval_node *node)
55 {
56         LASSERT(node->in_parent != NULL);
57         return node == node->in_parent->in_right;
58 }
59
60 static inline int node_is_red(struct interval_node *node)
61 {
62         return node->in_color == INTERVAL_RED;
63 }
64
65 static inline int node_is_black(struct interval_node *node)
66 {
67         return node->in_color == INTERVAL_BLACK;
68 }
69
70 static inline int extent_compare(struct interval_node_extent *e1,
71                                  struct interval_node_extent *e2)
72 {
73         int rc;
74         if (e1->start == e2->start) {
75                 if (e1->end < e2->end)
76                         rc = -1;
77                 else if (e1->end > e2->end)
78                         rc = 1;
79                 else
80                         rc = 0;
81         } else {
82                 if (e1->start < e2->start)
83                         rc = -1;
84                 else
85                         rc = 1;
86         }
87         return rc;
88 }
89
90 static inline int extent_equal(struct interval_node_extent *e1,
91                                struct interval_node_extent *e2)
92 {
93         return (e1->start == e2->start) && (e1->end == e2->end);
94 }
95
96 static inline int extent_overlapped(struct interval_node_extent *e1,
97                                     struct interval_node_extent *e2)
98 {
99         return (e1->start <= e2->end) && (e2->start <= e1->end);
100 }
101
102 static inline int node_compare(struct interval_node *n1,
103                                struct interval_node *n2)
104 {
105         return extent_compare(&n1->in_extent, &n2->in_extent);
106 }
107
108 int node_equal(struct interval_node *n1, struct interval_node *n2)
109 {
110         return extent_equal(&n1->in_extent, &n2->in_extent);
111 }
112
113 static inline __u64 max_u64(__u64 x, __u64 y)
114 {
115         return x > y ? x : y;
116 }
117
118 static inline __u64 min_u64(__u64 x, __u64 y)
119 {
120         return x < y ? x : y;
121 }
122
123 #define interval_for_each(node, root)                   \
124 for (node = interval_first(root); node != NULL;         \
125      node = interval_next(node))
126
127 #define interval_for_each_reverse(node, root)           \
128 for (node = interval_last(root); node != NULL;          \
129      node = interval_prev(node))
130
131 static struct interval_node *interval_first(struct interval_node *node)
132 {
133         ENTRY;
134
135         if (!node)
136                 RETURN(NULL);
137         while (node->in_left)
138                 node = node->in_left;
139         RETURN(node);
140 }
141
142 static struct interval_node *interval_last(struct interval_node *node)
143 {
144         ENTRY;
145
146         if (!node)
147                 RETURN(NULL);
148         while (node->in_right)
149                 node = node->in_right;
150         RETURN(node);
151 }
152
153 static struct interval_node *interval_next(struct interval_node *node)
154 {
155         ENTRY;
156
157         if (!node)
158                 RETURN(NULL);
159         if (node->in_right)
160                 RETURN(interval_first(node->in_right));
161         while (node->in_parent && node_is_right_child(node))
162                 node = node->in_parent;
163         RETURN(node->in_parent);
164 }
165
166 static struct interval_node *interval_prev(struct interval_node *node)
167 {
168         ENTRY;
169
170         if (!node)
171                 RETURN(NULL);
172
173         if (node->in_left)
174                 RETURN(interval_last(node->in_left));
175
176         while (node->in_parent && node_is_left_child(node))
177                 node = node->in_parent;
178
179         RETURN(node->in_parent);
180 }
181
182 enum interval_iter interval_iterate(struct interval_node *root,
183                                     interval_callback_t func,
184                                     void *data)
185 {
186         struct interval_node *node;
187         enum interval_iter rc = INTERVAL_ITER_CONT;
188         ENTRY;
189         
190         interval_for_each(node, root) {
191                 rc = func(node, data);
192                 if (rc == INTERVAL_ITER_STOP)
193                         break;
194         }
195
196         RETURN(rc);
197 }
198 EXPORT_SYMBOL(interval_iterate);
199
200 enum interval_iter interval_iterate_reverse(struct interval_node *root,
201                                             interval_callback_t func,
202                                             void *data)
203 {
204         struct interval_node *node;
205         enum interval_iter rc = INTERVAL_ITER_CONT;
206         ENTRY;
207         
208         interval_for_each_reverse(node, root) {
209                 rc = func(node, data);
210                 if (rc == INTERVAL_ITER_STOP)
211                         break;
212         }
213
214         RETURN(rc);
215 }
216 EXPORT_SYMBOL(interval_iterate_reverse);
217
218 /* try to find a node with same interval in the tree,
219  * if found, return the pointer to the node, otherwise return NULL*/
220 struct interval_node *interval_find(struct interval_node *root,
221                                     struct interval_node_extent *ex)
222 {
223         struct interval_node *walk = root;
224         int rc;
225         ENTRY;
226
227         while (walk) {
228                 rc = extent_compare(ex, &walk->in_extent);
229                 if (rc == 0)
230                         break;
231                 else if (rc < 0)
232                         walk = walk->in_left;
233                 else
234                         walk = walk->in_right;
235         }
236
237         RETURN(walk);
238 }
239 EXPORT_SYMBOL(interval_find);
240
241 static void __rotate_change_maxhigh(struct interval_node *node,
242                                     struct interval_node *rotate)
243 {
244         __u64 left_max, right_max;
245
246         rotate->in_max_high = node->in_max_high;
247         left_max = node->in_left ? node->in_left->in_max_high : 0;
248         right_max = node->in_right ? node->in_right->in_max_high : 0;
249         node->in_max_high  = max_u64(interval_high(node),
250                                      max_u64(left_max,right_max));
251 }
252
253 /* The left rotation "pivots" around the link from node to node->right, and
254  * - node will be linked to node->right's left child, and
255  * - node->right's left child will be linked to node's right child.  */
256 static void __rotate_left(struct interval_node *node,
257                           struct interval_node **root)
258 {
259         struct interval_node *right = node->in_right;
260         struct interval_node *parent = node->in_parent;
261
262         node->in_right = right->in_left;
263         if (node->in_right)
264                 right->in_left->in_parent = node;
265
266         right->in_left = node;
267         right->in_parent = parent;
268         if (parent) {
269                 if (node_is_left_child(node))
270                         parent->in_left = right;
271                 else
272                         parent->in_right = right;
273         } else {
274                 *root = right;
275         }
276         node->in_parent = right;
277
278         /* update max_high for node and right */
279         __rotate_change_maxhigh(node, right);
280 }
281
282 /* The right rotation "pivots" around the link from node to node->left, and
283  * - node will be linked to node->left's right child, and
284  * - node->left's right child will be linked to node's left child.  */
285 static void __rotate_right(struct interval_node *node,
286                            struct interval_node **root)
287 {
288         struct interval_node *left = node->in_left;
289         struct interval_node *parent = node->in_parent;
290
291         node->in_left = left->in_right;
292         if (node->in_left)
293                 left->in_right->in_parent = node;
294         left->in_right = node;
295
296         left->in_parent = parent;
297         if (parent) {
298                 if (node_is_right_child(node))
299                         parent->in_right = left;
300                 else
301                         parent->in_left = left;
302         } else {
303                 *root = left;
304         }
305         node->in_parent = left;
306
307         /* update max_high for node and left */
308         __rotate_change_maxhigh(node, left);
309 }
310
311 #define interval_swap(a, b) do {                        \
312         struct interval_node *c = a; a = b; b = c;      \
313 } while (0)
314
315 /*
316  * Operations INSERT and DELETE, when run on a tree with n keys, 
317  * take O(logN) time.Because they modify the tree, the result 
318  * may violate the red-black properties.To restore these properties, 
319  * we must change the colors of some of the nodes in the tree 
320  * and also change the pointer structure.
321  */
322 static void interval_insert_color(struct interval_node *node,
323                                   struct interval_node **root)
324 {
325         struct interval_node *parent, *gparent;
326         ENTRY;
327
328         while ((parent = node->in_parent) && node_is_red(parent)) {
329                 gparent = parent->in_parent;
330                 /* Parent is RED, so gparent must not be NULL */
331                 if (node_is_left_child(parent)) {
332                         struct interval_node *uncle;
333                         uncle = gparent->in_right;
334                         if (uncle && node_is_red(uncle)) {
335                                 uncle->in_color = INTERVAL_BLACK;
336                                 parent->in_color = INTERVAL_BLACK;
337                                 gparent->in_color = INTERVAL_RED;
338                                 node = gparent;
339                                 continue;
340                         }
341
342                         if (parent->in_right == node) {
343                                 __rotate_left(parent, root);
344                                 interval_swap(node, parent);
345                         }
346
347                         parent->in_color = INTERVAL_BLACK;
348                         gparent->in_color = INTERVAL_RED;
349                         __rotate_right(gparent, root);
350                 } else {
351                         struct interval_node *uncle;
352                         uncle = gparent->in_left;
353                         if (uncle && node_is_red(uncle)) {
354                                 uncle->in_color = INTERVAL_BLACK;
355                                 parent->in_color = INTERVAL_BLACK;
356                                 gparent->in_color = INTERVAL_RED;
357                                 node = gparent;
358                                 continue;
359                         }
360
361                         if (node_is_left_child(node)) {
362                                 __rotate_right(parent, root);
363                                 interval_swap(node, parent);
364                         }
365
366                         parent->in_color = INTERVAL_BLACK;
367                         gparent->in_color = INTERVAL_RED;
368                         __rotate_left(gparent, root);
369                 }
370         }
371
372         (*root)->in_color = INTERVAL_BLACK;
373         EXIT;
374 }
375
376 struct interval_node *interval_insert(struct interval_node *node,
377                                       struct interval_node **root)
378                      
379 {
380         struct interval_node **p, *parent = NULL;
381         ENTRY;
382
383         LASSERT(!interval_is_intree(node));
384         p = root;
385         while (*p) {
386                 parent = *p;
387                 if (node_equal(parent, node))
388                         RETURN(parent);
389
390                 /* max_high field must be updated after each iteration */
391                 if (parent->in_max_high < interval_high(node))
392                         parent->in_max_high = interval_high(node);
393
394                 if (node_compare(node, parent) < 0)
395                         p = &parent->in_left;
396                 else 
397                         p = &parent->in_right;
398         }
399
400         /* link node into the tree */
401         node->in_parent = parent;
402         node->in_color = INTERVAL_RED;
403         node->in_left = node->in_right = NULL;
404         *p = node;
405
406         interval_insert_color(node, root);
407         node->in_intree = 1;
408
409         RETURN(NULL);
410 }
411 EXPORT_SYMBOL(interval_insert);
412
413 static inline int node_is_black_or_0(struct interval_node *node)
414 {
415         return !node || node_is_black(node);
416 }
417
418 static void interval_erase_color(struct interval_node *node,
419                                  struct interval_node *parent,
420                                  struct interval_node **root)
421 {
422         struct interval_node *tmp;
423         ENTRY;
424
425         while (node_is_black_or_0(node) && node != *root) {
426                 if (parent->in_left == node) {
427                         tmp = parent->in_right;
428                         if (node_is_red(tmp)) {
429                                 tmp->in_color = INTERVAL_BLACK;
430                                 parent->in_color = INTERVAL_RED;
431                                 __rotate_left(parent, root);
432                                 tmp = parent->in_right;
433                         }
434                         if (node_is_black_or_0(tmp->in_left) &&
435                             node_is_black_or_0(tmp->in_right)) {
436                                 tmp->in_color = INTERVAL_RED;
437                                 node = parent;
438                                 parent = node->in_parent;
439                         } else {
440                                 if (node_is_black_or_0(tmp->in_right)) {
441                                         struct interval_node *o_left;
442                                         if ((o_left = tmp->in_left))
443                                              o_left->in_color = INTERVAL_BLACK;
444                                         tmp->in_color = INTERVAL_RED;
445                                         __rotate_right(tmp, root);
446                                         tmp = parent->in_right;
447                                 }
448                                 tmp->in_color = parent->in_color;
449                                 parent->in_color = INTERVAL_BLACK;
450                                 if (tmp->in_right)
451                                     tmp->in_right->in_color = INTERVAL_BLACK;
452                                 __rotate_left(parent, root);
453                                 node = *root;
454                                 break;
455                         }
456                 } else {
457                         tmp = parent->in_left;
458                         if (node_is_red(tmp)) {
459                                 tmp->in_color = INTERVAL_BLACK;
460                                 parent->in_color = INTERVAL_RED;
461                                 __rotate_right(parent, root);
462                                 tmp = parent->in_left;
463                         }
464                         if (node_is_black_or_0(tmp->in_left) &&
465                             node_is_black_or_0(tmp->in_right)) {
466                                 tmp->in_color = INTERVAL_RED;
467                                 node = parent;
468                                 parent = node->in_parent;
469                         } else {
470                                 if (node_is_black_or_0(tmp->in_left)) {
471                                         struct interval_node *o_right;
472                                         if ((o_right = tmp->in_right))
473                                             o_right->in_color = INTERVAL_BLACK;
474                                         tmp->in_color = INTERVAL_RED;
475                                         __rotate_left(tmp, root);
476                                         tmp = parent->in_left;
477                                 }
478                                 tmp->in_color = parent->in_color;
479                                 parent->in_color = INTERVAL_BLACK;
480                                 if (tmp->in_left)
481                                         tmp->in_left->in_color = INTERVAL_BLACK;
482                                 __rotate_right(parent, root);
483                                 node = *root;
484                                 break;
485                         }
486                 }
487         }
488         if (node)
489                 node->in_color = INTERVAL_BLACK;
490         EXIT;
491 }
492
493 /* 
494  * if the @max_high value of @node is changed, this function traverse  a path 
495  * from node  up to the root to update max_high for the whole tree.
496  */
497 static void update_maxhigh(struct interval_node *node,
498                            __u64  old_maxhigh)
499 {
500         __u64 left_max, right_max;
501         ENTRY;
502
503         while (node) {
504                 left_max = node->in_left ? node->in_left->in_max_high : 0;
505                 right_max = node->in_right ? node->in_right->in_max_high : 0;
506                 node->in_max_high = max_u64(interval_high(node),
507                                             max_u64(left_max, right_max));
508
509                 if (node->in_max_high >= old_maxhigh)
510                         break;
511                 node = node->in_parent;
512         }
513         EXIT;
514 }
515
516 void interval_erase(struct interval_node *node,
517                     struct interval_node **root)
518 {
519         struct interval_node *child, *parent;
520         int color;
521         ENTRY;
522
523         LASSERT(interval_is_intree(node));
524         node->in_intree = 0;
525         if (!node->in_left) {
526                 child = node->in_right;
527         } else if (!node->in_right) {
528                 child = node->in_left;
529         } else { /* Both left and right child are not NULL */
530                 struct interval_node *old = node;
531
532                 node = interval_next(node);
533                 child = node->in_right;
534                 parent = node->in_parent;
535                 color = node->in_color;
536
537                 if (child)
538                         child->in_parent = parent;
539                 if (parent == old)
540                         parent->in_right = child;
541                 else
542                         parent->in_left = child;
543
544                 node->in_color = old->in_color;
545                 node->in_right = old->in_right;
546                 node->in_left = old->in_left;
547                 node->in_parent = old->in_parent;
548
549                 if (old->in_parent) {
550                         if (node_is_left_child(old))
551                                 old->in_parent->in_left = node;
552                         else
553                                 old->in_parent->in_right = node;
554                 } else {
555                         *root = node;
556                 }
557
558                 old->in_left->in_parent = node;
559                 if (old->in_right)
560                         old->in_right->in_parent = node;
561                 update_maxhigh(child ? : parent, node->in_max_high);
562                 update_maxhigh(node, old->in_max_high);
563                 if (parent == old)
564                          parent = node;
565                 goto color;
566         }
567         parent = node->in_parent;
568         color = node->in_color;
569
570         if (child)
571                 child->in_parent = parent;
572         if (parent) {
573                 if (node_is_left_child(node))
574                         parent->in_left = child;
575                 else
576                         parent->in_right = child;
577         } else {
578                 *root = child;
579         }
580
581         update_maxhigh(child ? : parent, node->in_max_high);
582
583 color:
584         if (color == INTERVAL_BLACK)
585                 interval_erase_color(child, parent, root);
586         EXIT;
587 }
588 EXPORT_SYMBOL(interval_erase);
589
590 static inline int interval_may_overlap(struct interval_node *node,
591                                           struct interval_node_extent *ext)
592 {
593         return (ext->start <= node->in_max_high &&
594                 ext->end >= interval_low(node));
595 }
596
597 /*
598  * This function finds all intervals that overlap interval ext,
599  * and calls func to handle resulted intervals one by one.
600  * in lustre, this function will find all conflicting locks in
601  * the granted queue and add these locks to the ast work list.
602  *
603  * {
604  *       if (node == NULL)
605  *               return 0;
606  *       if (ext->end < interval_low(node)) {
607  *               interval_search(node->in_left, ext, func, data);
608  *       } else if (interval_may_overlap(node, ext)) {
609  *               if (extent_overlapped(ext, &node->in_extent))
610  *                       func(node, data);
611  *               interval_search(node->in_left, ext, func, data);
612  *               interval_search(node->in_right, ext, func, data);
613  *       }
614  *       return 0;
615  * }
616  *
617  */
618 enum interval_iter interval_search(struct interval_node *node,
619                                    struct interval_node_extent *ext,
620                                    interval_callback_t func,
621                                    void *data)
622 {
623         struct interval_node *parent;
624         enum interval_iter rc = INTERVAL_ITER_CONT;
625
626         ENTRY;
627
628         LASSERT(ext != NULL);
629         LASSERT(func != NULL);
630
631         while (node) {
632                 if (ext->end < interval_low(node)) {
633                         if (node->in_left) {
634                                 node = node->in_left;
635                                 continue;
636                         }
637                 } else if (interval_may_overlap(node, ext)) {
638                         if (extent_overlapped(ext, &node->in_extent)) {
639                                 rc = func(node, data);
640                                 if (rc == INTERVAL_ITER_STOP)
641                                         break;
642                         }
643
644                         if (node->in_left) {
645                                 node = node->in_left;
646                                 continue;
647                         }
648                         if (node->in_right) {
649                                 node = node->in_right;
650                                 continue;
651                         }
652                 }
653
654                 parent = node->in_parent;
655                 while (parent) {
656                         if (node_is_left_child(node) &&
657                             parent->in_right) {
658                                 /* If we ever got the left, it means that the
659                                  * parent met ext->end<interval_low(parent), or
660                                  * may_overlap(parent). If the former is true,
661                                  * we needn't go back. So stop early and check
662                                  * may_overlap(parent) after this loop.  */
663                                 node = parent->in_right;
664                                 break;
665                         }
666                         node = parent;
667                         parent = parent->in_parent;
668                 }
669                 if (parent == NULL || !interval_may_overlap(parent, ext))
670                         break;
671         }
672
673         RETURN(rc);
674 }
675 EXPORT_SYMBOL(interval_search);
676
677 static enum interval_iter interval_overlap_cb(struct interval_node *n,
678                                               void *args)
679 {
680         *(int *)args = 1;
681         return INTERVAL_ITER_STOP;
682 }
683
684 int interval_is_overlapped(struct interval_node *root,
685                            struct interval_node_extent *ext)
686 {
687         int has = 0;
688         (void)interval_search(root, ext, interval_overlap_cb, &has);
689         return has;
690 }
691 EXPORT_SYMBOL(interval_is_overlapped);
692
693 /* Don't expand to low. Expanding downwards is expensive, and meaningless to
694  * some extents, because programs seldom do IO backward.
695  *
696  * The recursive algorithm of expanding low:
697  * expand_low {
698  *        struct interval_node *tmp;
699  *        static __u64 res = 0;
700  *
701  *        if (root == NULL)
702  *                return res;
703  *        if (root->in_max_high < low) {
704  *                res = max_u64(root->in_max_high + 1, res);
705  *                return res;
706  *        } else if (low < interval_low(root)) {
707  *                interval_expand_low(root->in_left, low);
708  *                return res;
709  *        }
710  *
711  *        if (interval_high(root) < low)
712  *                res = max_u64(interval_high(root) + 1, res);
713  *        interval_expand_low(root->in_left, low);
714  *        interval_expand_low(root->in_right, low);
715  *
716  *        return res;
717  * }
718  *
719  * It's much easy to eliminate the recursion, see interval_search for 
720  * an example. -jay
721  */
722 static inline __u64 interval_expand_low(struct interval_node *root, __u64 low)
723 {
724         /* we only concern the empty tree right now. */
725         if (root == NULL)
726                 return 0;
727         return low;
728 }
729
730 static inline __u64 interval_expand_high(struct interval_node *node, __u64 high)
731 {
732         __u64 result = ~0;
733
734         while (node != NULL) {
735                 if (node->in_max_high < high)
736                         break;
737                         
738                 if (interval_low(node) > high) {
739                         result = interval_low(node) - 1;
740                         node = node->in_left;
741                 } else {
742                         node = node->in_right;
743                 }
744         }
745
746         return result;
747 }
748
749 /* expanding the extent based on @ext. */
750 void interval_expand(struct interval_node *root,
751                      struct interval_node_extent *ext,
752                      struct interval_node_extent *limiter)
753 {
754         /* The assertion of interval_is_overlapped is expensive because we may
755          * travel many nodes to find the overlapped node. */
756         LASSERT(interval_is_overlapped(root, ext) == 0);
757         if (!limiter || limiter->start < ext->start)
758                 ext->start = interval_expand_low(root, ext->start);
759         if (!limiter || limiter->end > ext->end)
760                 ext->end = interval_expand_high(root, ext->end);
761         LASSERT(interval_is_overlapped(root, ext) == 0);
762 }