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