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