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