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