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  * 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
  75         if (e1->start == e2->start) {
  76                 if (e1->end < e2->end)
  77                         rc = -1;
  78                 else if (e1->end > e2->end)
  79                         rc = 1;
  80                 else
  81                         rc = 0;
  82         } else {
  83                 if (e1->start < e2->start)
  84                         rc = -1;
  85                 else
  86                         rc = 1;
  87         }
  88         return rc;
  89 }
  90
  91 static inline int extent_equal(struct interval_node_extent *e1,
  92                                struct interval_node_extent *e2)
  93 {
  94         return (e1->start == e2->start) && (e1->end == e2->end);
  95 }
  96
  97 static inline int extent_overlapped(struct interval_node_extent *e1,
  98                                     struct interval_node_extent *e2)
  99 {
 100         return (e1->start <= e2->end) && (e2->start <= e1->end);
 101 }
 102
 103 static inline int node_compare(struct interval_node *n1,
 104                                struct interval_node *n2)
 105 {
 106         return extent_compare(&n1->in_extent, &n2->in_extent);
 107 }
 108
 109 int node_equal(struct interval_node *n1, struct interval_node *n2)
 110 {
 111         return extent_equal(&n1->in_extent, &n2->in_extent);
 112 }
 113
 114 #define interval_for_each(node, root)                   \
 115 for (node = interval_first(root); node != NULL;         \
 116         node = interval_next(node))
 117
 118 #define interval_for_each_reverse(node, root)           \
 119 for (node = interval_last(root); node != NULL;          \
 120         node = interval_prev(node))
 121
 122 static struct interval_node *interval_first(struct interval_node *node)
 123 {
 124         ENTRY;
 125
 126         if (!node)
 127                 RETURN(NULL);
 128         while (node->in_left)
 129                 node = node->in_left;
 130         RETURN(node);
 131 }
 132
 133 static struct interval_node *interval_last(struct interval_node *node)
 134 {
 135         ENTRY;
 136
 137         if (!node)
 138                 RETURN(NULL);
 139         while (node->in_right)
 140                 node = node->in_right;
 141         RETURN(node);
 142 }
 143
 144 static struct interval_node *interval_next(struct interval_node *node)
 145 {
 146         ENTRY;
 147
 148         if (!node)
 149                 RETURN(NULL);
 150         if (node->in_right)
 151                 RETURN(interval_first(node->in_right));
 152         while (node->in_parent && node_is_right_child(node))
 153                 node = node->in_parent;
 154         RETURN(node->in_parent);
 155 }
 156
 157 static struct interval_node *interval_prev(struct interval_node *node)
 158 {
 159         ENTRY;
 160
 161         if (!node)
 162                 RETURN(NULL);
 163
 164         if (node->in_left)
 165                 RETURN(interval_last(node->in_left));
 166
 167         while (node->in_parent && node_is_left_child(node))
 168                 node = node->in_parent;
 169
 170         RETURN(node->in_parent);
 171 }
 172
 173 enum interval_iter interval_iterate(struct interval_node *root,
 174                                     interval_callback_t func,
 175                                     void *data)
 176 {
 177         struct interval_node *node;
 178         enum interval_iter rc = INTERVAL_ITER_CONT;
 179
 180         ENTRY;
 181
 182         interval_for_each(node, root) {
 183                 rc = func(node, data);
 184                 if (rc == INTERVAL_ITER_STOP)
 185                         break;
 186         }
 187
 188         RETURN(rc);
 189 }
 190 EXPORT_SYMBOL(interval_iterate);
 191
 192 enum interval_iter interval_iterate_reverse(struct interval_node *root,
 193                                             interval_callback_t func,
 194                                             void *data)
 195 {
 196         struct interval_node *node;
 197         enum interval_iter rc = INTERVAL_ITER_CONT;
 198
 199         ENTRY;
 200
 201         interval_for_each_reverse(node, root) {
 202                 rc = func(node, data);
 203                 if (rc == INTERVAL_ITER_STOP)
 204                         break;
 205         }
 206
 207         RETURN(rc);
 208 }
 209 EXPORT_SYMBOL(interval_iterate_reverse);
 210
 211 /* try to find a node with same interval in the tree,
 212  * if found, return the pointer to the node, otherwise return NULL
 213  */
 214 struct interval_node *interval_find(struct interval_node *root,
 215                                     struct interval_node_extent *ex)
 216 {
 217         struct interval_node *walk = root;
 218         int rc;
 219
 220         ENTRY;
 221
 222         while (walk) {
 223                 rc = extent_compare(ex, &walk->in_extent);
 224                 if (rc == 0)
 225                         break;
 226                 else if (rc < 0)
 227                         walk = walk->in_left;
 228                 else
 229                         walk = walk->in_right;
 230         }
 231
 232         RETURN(walk);
 233 }
 234 EXPORT_SYMBOL(interval_find);
 235
 236 static void __rotate_change_maxhigh(struct interval_node *node,
 237                                     struct interval_node *rotate)
 238 {
 239         __u64 left_max, right_max;
 240
 241         rotate->in_max_high = node->in_max_high;
 242         left_max = node->in_left ? node->in_left->in_max_high : 0;
 243         right_max = node->in_right ? node->in_right->in_max_high : 0;
 244         node->in_max_high  = max3(interval_high(node),
 245                                   left_max, right_max);
 246 }
 247
 248 /* The left rotation "pivots" around the link from node to node->right, and
 249  * - node will be linked to node->right's left child, and
 250  * - node->right's left child will be linked to node's right child.
 251  */
 252 static void __rotate_left(struct interval_node *node,
 253                           struct interval_node **root)
 254 {
 255         struct interval_node *right = node->in_right;
 256         struct interval_node *parent = node->in_parent;
 257
 258         node->in_right = right->in_left;
 259         if (node->in_right)
 260                 right->in_left->in_parent = node;
 261
 262         right->in_left = node;
 263         right->in_parent = parent;
 264         if (parent) {
 265                 if (node_is_left_child(node))
 266                         parent->in_left = right;
 267                 else
 268                         parent->in_right = right;
 269         } else {
 270                 *root = right;
 271         }
 272         node->in_parent = right;
 273
 274         /* update max_high for node and right */
 275         __rotate_change_maxhigh(node, right);
 276 }
 277
 278 /* The right rotation "pivots" around the link from node to node->left, and
 279  * - node will be linked to node->left's right child, and
 280  * - node->left's right child will be linked to node's left child.
 281  */
 282 static void __rotate_right(struct interval_node *node,
 283                            struct interval_node **root)
 284 {
 285         struct interval_node *left = node->in_left;
 286         struct interval_node *parent = node->in_parent;
 287
 288         node->in_left = left->in_right;
 289         if (node->in_left)
 290                 left->in_right->in_parent = node;
 291         left->in_right = node;
 292
 293         left->in_parent = parent;
 294         if (parent) {
 295                 if (node_is_right_child(node))
 296                         parent->in_right = left;
 297                 else
 298                         parent->in_left = left;
 299         } else {
 300                 *root = left;
 301         }
 302         node->in_parent = left;
 303
 304         /* update max_high for node and left */
 305         __rotate_change_maxhigh(node, left);
 306 }
 307
 308 #define interval_swap(a, b) do {                        \
 309         struct interval_node *c = a; a = b; b = c;      \
 310 } while (0)
 311
 312 /*
 313  * Operations INSERT and DELETE, when run on a tree with n keys,
 314  * take O(logN) time.Because they modify the tree, the result
 315  * may violate the red-black properties.To restore these properties,
 316  * we must change the colors of some of the nodes in the tree
 317  * and also change the pointer structure.
 318  */
 319 static void interval_insert_color(struct interval_node *node,
 320                                   struct interval_node **root)
 321 {
 322         struct interval_node *parent, *gparent;
 323
 324         ENTRY;
 325
 326         while ((parent = node->in_parent) && node_is_red(parent)) {
 327                 gparent = parent->in_parent;
 328                 /* Parent is RED, so gparent must not be NULL */
 329                 if (node_is_left_child(parent)) {
 330                         struct interval_node *uncle;
 331
 332                         uncle = gparent->in_right;
 333                         if (uncle && node_is_red(uncle)) {
 334                                 uncle->in_color = INTERVAL_BLACK;
 335                                 parent->in_color = INTERVAL_BLACK;
 336                                 gparent->in_color = INTERVAL_RED;
 337                                 node = gparent;
 338                                 continue;
 339                         }
 340
 341                         if (parent->in_right == node) {
 342                                 __rotate_left(parent, root);
 343                                 interval_swap(node, parent);
 344                         }
 345
 346                         parent->in_color = INTERVAL_BLACK;
 347                         gparent->in_color = INTERVAL_RED;
 348                         __rotate_right(gparent, root);
 349                 } else {
 350                         struct interval_node *uncle;
 351
 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         struct interval_node **p, *parent = NULL;
 380
 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
 424         ENTRY;
 425
 426         while (node_is_black_or_0(node) && node != *root) {
 427                 if (parent->in_left == node) {
 428                         tmp = parent->in_right;
 429                         if (node_is_red(tmp)) {
 430                                 tmp->in_color = INTERVAL_BLACK;
 431                                 parent->in_color = INTERVAL_RED;
 432                                 __rotate_left(parent, root);
 433                                 tmp = parent->in_right;
 434                         }
 435                         if (node_is_black_or_0(tmp->in_left) &&
 436                             node_is_black_or_0(tmp->in_right)) {
 437                                 tmp->in_color = INTERVAL_RED;
 438                                 node = parent;
 439                                 parent = node->in_parent;
 440                         } else {
 441                                 if (node_is_black_or_0(tmp->in_right)) {
 442                                         struct interval_node *o_left;
 443
 444                                         if ((o_left = tmp->in_left))
 445                                                 o_left->in_color =
 446                                                         INTERVAL_BLACK;
 447                                         tmp->in_color = INTERVAL_RED;
 448                                         __rotate_right(tmp, root);
 449                                         tmp = parent->in_right;
 450                                 }
 451                                 tmp->in_color = parent->in_color;
 452                                 parent->in_color = INTERVAL_BLACK;
 453                                 if (tmp->in_right)
 454                                         tmp->in_right->in_color =
 455                                                 INTERVAL_BLACK;
 456                                 __rotate_left(parent, root);
 457                                 node = *root;
 458                                 break;
 459                         }
 460                 } else {
 461                         tmp = parent->in_left;
 462                         if (node_is_red(tmp)) {
 463                                 tmp->in_color = INTERVAL_BLACK;
 464                                 parent->in_color = INTERVAL_RED;
 465                                 __rotate_right(parent, root);
 466                                 tmp = parent->in_left;
 467                         }
 468                         if (node_is_black_or_0(tmp->in_left) &&
 469                             node_is_black_or_0(tmp->in_right)) {
 470                                 tmp->in_color = INTERVAL_RED;
 471                                 node = parent;
 472                                 parent = node->in_parent;
 473                         } else {
 474                                 if (node_is_black_or_0(tmp->in_left)) {
 475                                         struct interval_node *o_right;
 476
 477                                         if ((o_right = tmp->in_right))
 478                                                 o_right->in_color =
 479                                                         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
 508         ENTRY;
 509
 510         while (node) {
 511                 left_max = node->in_left ? node->in_left->in_max_high : 0;
 512                 right_max = node->in_right ? node->in_right->in_max_high : 0;
 513                 node->in_max_high = max3(interval_high(node),
 514                                          left_max, right_max);
 515
 516                 if (node->in_max_high >= old_maxhigh)
 517                         break;
 518                 node = node->in_parent;
 519         }
 520         EXIT;
 521 }
 522
 523 void interval_erase(struct interval_node *node,
 524                     struct interval_node **root)
 525 {
 526         struct interval_node *child, *parent;
 527         int color;
 528
 529         ENTRY;
 530
 531         LASSERT(interval_is_intree(node));
 532         node->in_intree = 0;
 533         if (!node->in_left) {
 534                 child = node->in_right;
 535         } else if (!node->in_right) {
 536                 child = node->in_left;
 537         } else { /* Both left and right child are not NULL */
 538                 struct interval_node *old = node;
 539
 540                 node = interval_next(node);
 541                 child = node->in_right;
 542                 parent = node->in_parent;
 543                 color = node->in_color;
 544
 545                 if (child)
 546                         child->in_parent = parent;
 547                 if (parent == old)
 548                         parent->in_right = child;
 549                 else
 550                         parent->in_left = child;
 551
 552                 node->in_color = old->in_color;
 553                 node->in_right = old->in_right;
 554                 node->in_left = old->in_left;
 555                 node->in_parent = old->in_parent;
 556
 557                 if (old->in_parent) {
 558                         if (node_is_left_child(old))
 559                                 old->in_parent->in_left = node;
 560                         else
 561                                 old->in_parent->in_right = node;
 562                 } else {
 563                         *root = node;
 564                 }
 565
 566                 old->in_left->in_parent = node;
 567                 if (old->in_right)
 568                         old->in_right->in_parent = node;
 569                 update_maxhigh(child ? : parent, node->in_max_high);
 570                 update_maxhigh(node, old->in_max_high);
 571                 if (parent == old)
 572                         parent = node;
 573                 goto color;
 574         }
 575         parent = node->in_parent;
 576         color = node->in_color;
 577
 578         if (child)
 579                 child->in_parent = parent;
 580         if (parent) {
 581                 if (node_is_left_child(node))
 582                         parent->in_left = child;
 583                 else
 584                         parent->in_right = child;
 585         } else {
 586                 *root = child;
 587         }
 588
 589         update_maxhigh(child ? : parent, node->in_max_high);
 590
 591 color:
 592         if (color == INTERVAL_BLACK)
 593                 interval_erase_color(child, parent, root);
 594         EXIT;
 595 }
 596 EXPORT_SYMBOL(interval_erase);
 597
 598 static inline int interval_may_overlap(struct interval_node *node,
 599                                        struct interval_node_extent *ext)
 600 {
 601         return (ext->start <= node->in_max_high &&
 602                 ext->end >= interval_low(node));
 603 }
 604
 605 /*
 606  * This function finds all intervals that overlap interval ext,
 607  * and calls func to handle resulted intervals one by one.
 608  * in lustre, this function will find all conflicting locks in
 609  * the granted queue and add these locks to the ast work list.
 610  *
 611  * {
 612  *       if (node == NULL)
 613  *               return 0;
 614  *       if (ext->end < interval_low(node)) {
 615  *               interval_search(node->in_left, ext, func, data);
 616  *       } else if (interval_may_overlap(node, ext)) {
 617  *               if (extent_overlapped(ext, &node->in_extent))
 618  *                       func(node, data);
 619  *               interval_search(node->in_left, ext, func, data);
 620  *               interval_search(node->in_right, ext, func, data);
 621  *       }
 622  *       return 0;
 623  * }
 624  *
 625  */
 626 enum interval_iter interval_search(struct interval_node *node,
 627                                    struct interval_node_extent *ext,
 628                                    interval_callback_t func,
 629                                    void *data)
 630 {
 631         struct interval_node *parent;
 632         enum interval_iter rc = INTERVAL_ITER_CONT;
 633
 634         ENTRY;
 635
 636         LASSERT(ext != NULL);
 637         LASSERT(func != NULL);
 638
 639         while (node) {
 640                 if (ext->end < interval_low(node)) {
 641                         if (node->in_left) {
 642                                 node = node->in_left;
 643                                 continue;
 644                         }
 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)
 649                                         break;
 650                         }
 651
 652                         if (node->in_left) {
 653                                 node = node->in_left;
 654                                 continue;
 655                         }
 656                         if (node->in_right) {
 657                                 node = node->in_right;
 658                                 continue;
 659                         }
 660                 }
 661
 662                 parent = node->in_parent;
 663                 while (parent) {
 664                         if (node_is_left_child(node) &&
 665                             parent->in_right) {
 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                                  */
 672                                 node = parent->in_right;
 673                                 break;
 674                         }
 675                         node = parent;
 676                         parent = parent->in_parent;
 677                 }
 678                 if (parent == NULL || !interval_may_overlap(parent, ext))
 679                         break;
 680         }
 681
 682         RETURN(rc);
 683 }
 684 EXPORT_SYMBOL(interval_search);
 685
 686 static enum interval_iter interval_overlap_cb(struct interval_node *n,
 687                                               void *args)
 688 {
 689         *(int *)args = 1;
 690         return INTERVAL_ITER_STOP;
 691 }
 692
 693 int interval_is_overlapped(struct interval_node *root,
 694                            struct interval_node_extent *ext)
 695 {
 696         int has = 0;
 697         (void)interval_search(root, ext, interval_overlap_cb, &has);
 698         return has;
 699 }
 700 EXPORT_SYMBOL(interval_is_overlapped);
 701
 702 /* Don't expand to low. Expanding downwards is expensive, and meaningless to
 703  * some extents, because programs seldom do IO backward.
 704  *
 705  * The recursive algorithm of expanding low:
 706  * expand_low {
 707  *        struct interval_node *tmp;
 708  *        static __u64 res = 0;
 709  *
 710  *        if (root == NULL)
 711  *                return res;
 712  *        if (root->in_max_high < low) {
 713  *                res = max(root->in_max_high + 1, res);
 714  *                return res;
 715  *        } else if (low < interval_low(root)) {
 716  *                interval_expand_low(root->in_left, low);
 717  *                return res;
 718  *        }
 719  *
 720  *        if (interval_high(root) < low)
 721  *                res = max(interval_high(root) + 1, res);
 722  *        interval_expand_low(root->in_left, low);
 723  *        interval_expand_low(root->in_right, low);
 724  *
 725  *        return res;
 726  * }
 727  *
 728  * It's much easy to eliminate the recursion, see interval_search for
 729  * an example. -jay
 730  */
 731 static inline __u64 interval_expand_low(struct interval_node *root, __u64 low)
 732 {
 733         /* we only concern the empty tree right now. */
 734         if (root == NULL)
 735                 return 0;
 736         return low;
 737 }
 738
 739 static inline __u64 interval_expand_high(struct interval_node *node, __u64 high)
 740 {
 741         __u64 result = ~0;
 742
 743         while (node != NULL) {
 744                 if (node->in_max_high < high)
 745                         break;
 746
 747                 if (interval_low(node) > high) {
 748                         result = interval_low(node) - 1;
 749                         node = node->in_left;
 750                 } else {
 751                         node = node->in_right;
 752                 }
 753         }
 754
 755         return result;
 756 }
 757
 758 /* expanding the extent based on @ext. */
 759 void interval_expand(struct interval_node *root,
 760                      struct interval_node_extent *ext,
 761                      struct interval_node_extent *limiter)
 762 {
 763         /* The assertion of interval_is_overlapped is expensive because we may
 764          * travel many nodes to find the overlapped node.
 765          */
 766         LASSERT(interval_is_overlapped(root, ext) == 0);
 767         if (!limiter || limiter->start < ext->start)
 768                 ext->start = interval_expand_low(root, ext->start);
 769         if (!limiter || limiter->end > ext->end)
 770                 ext->end = interval_expand_high(root, ext->end);
 771         LASSERT(interval_is_overlapped(root, ext) == 0);
 772 }
 773 EXPORT_SYMBOL(interval_expand);