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);