drivers/staging/lustre/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 /*
  27  * This file is part of Lustre, http://www.lustre.org/
  28  * Lustre is a trademark of Sun Microsystems, Inc.
  29  *
  30  * lustre/ldlm/interval_tree.c
  31  *
  32  * Interval tree library used by ldlm extent lock code
  33  *
  34  * Author: Huang Wei <huangwei@clusterfs.com>
  35  * Author: Jay Xiong <jinshan.xiong@sun.com>
  36  */
  37 #include <lustre_dlm.h>
  38 #include <obd_support.h>
  39 #include <interval_tree.h>
  40
  41 enum {
  42         INTERVAL_RED = 0,
  43         INTERVAL_BLACK = 1
  44 };
  45
  46 static inline int node_is_left_child(struct interval_node *node)
  47 {
  48         return node == node->in_parent->in_left;
  49 }
  50
  51 static inline int node_is_right_child(struct interval_node *node)
  52 {
  53         return node == node->in_parent->in_right;
  54 }
  55
  56 static inline int node_is_red(struct interval_node *node)
  57 {
  58         return node->in_color == INTERVAL_RED;
  59 }
  60
  61 static inline int node_is_black(struct interval_node *node)
  62 {
  63         return node->in_color == INTERVAL_BLACK;
  64 }
  65
  66 static inline int extent_compare(struct interval_node_extent *e1,
  67                                  struct interval_node_extent *e2)
  68 {
  69         int rc;
  70
  71         if (e1->start == e2->start) {
  72                 if (e1->end < e2->end)
  73                         rc = -1;
  74                 else if (e1->end > e2->end)
  75                         rc = 1;
  76                 else
  77                         rc = 0;
  78         } else {
  79                 if (e1->start < e2->start)
  80                         rc = -1;
  81                 else
  82                         rc = 1;
  83         }
  84         return rc;
  85 }
  86
  87 static inline int extent_equal(struct interval_node_extent *e1,
  88                                struct interval_node_extent *e2)
  89 {
  90         return (e1->start == e2->start) && (e1->end == e2->end);
  91 }
  92
  93 static inline int extent_overlapped(struct interval_node_extent *e1,
  94                                     struct interval_node_extent *e2)
  95 {
  96         return (e1->start <= e2->end) && (e2->start <= e1->end);
  97 }
  98
  99 static inline int node_equal(struct interval_node *n1, struct interval_node *n2)
 100 {
 101         return extent_equal(&n1->in_extent, &n2->in_extent);
 102 }
 103
 104 static struct interval_node *interval_first(struct interval_node *node)
 105 {
 106         if (!node)
 107                 return NULL;
 108         while (node->in_left)
 109                 node = node->in_left;
 110         return node;
 111 }
 112
 113 static struct interval_node *interval_last(struct interval_node *node)
 114 {
 115         if (!node)
 116                 return NULL;
 117         while (node->in_right)
 118                 node = node->in_right;
 119         return node;
 120 }
 121
 122 static struct interval_node *interval_next(struct interval_node *node)
 123 {
 124         if (!node)
 125                 return NULL;
 126         if (node->in_right)
 127                 return interval_first(node->in_right);
 128         while (node->in_parent && node_is_right_child(node))
 129                 node = node->in_parent;
 130         return node->in_parent;
 131 }
 132
 133 static struct interval_node *interval_prev(struct interval_node *node)
 134 {
 135         if (!node)
 136                 return NULL;
 137
 138         if (node->in_left)
 139                 return interval_last(node->in_left);
 140
 141         while (node->in_parent && node_is_left_child(node))
 142                 node = node->in_parent;
 143
 144         return node->in_parent;
 145 }
 146
 147 enum interval_iter interval_iterate_reverse(struct interval_node *root,
 148                                             interval_callback_t func,
 149                                             void *data)
 150 {
 151         enum interval_iter rc = INTERVAL_ITER_CONT;
 152         struct interval_node *node;
 153
 154         for (node = interval_last(root); node; node = interval_prev(node)) {
 155                 rc = func(node, data);
 156                 if (rc == INTERVAL_ITER_STOP)
 157                         break;
 158         }
 159
 160         return rc;
 161 }
 162 EXPORT_SYMBOL(interval_iterate_reverse);
 163
 164 static void __rotate_change_maxhigh(struct interval_node *node,
 165                                     struct interval_node *rotate)
 166 {
 167         __u64 left_max, right_max;
 168
 169         rotate->in_max_high = node->in_max_high;
 170         left_max = node->in_left ? node->in_left->in_max_high : 0;
 171         right_max = node->in_right ? node->in_right->in_max_high : 0;
 172         node->in_max_high  = max(interval_high(node),
 173                                  max(left_max, right_max));
 174 }
 175
 176 /* The left rotation "pivots" around the link from node to node->right, and
 177  * - node will be linked to node->right's left child, and
 178  * - node->right's left child will be linked to node's right child.
 179  */
 180 static void __rotate_left(struct interval_node *node,
 181                           struct interval_node **root)
 182 {
 183         struct interval_node *right = node->in_right;
 184         struct interval_node *parent = node->in_parent;
 185
 186         node->in_right = right->in_left;
 187         if (node->in_right)
 188                 right->in_left->in_parent = node;
 189
 190         right->in_left = node;
 191         right->in_parent = parent;
 192         if (parent) {
 193                 if (node_is_left_child(node))
 194                         parent->in_left = right;
 195                 else
 196                         parent->in_right = right;
 197         } else {
 198                 *root = right;
 199         }
 200         node->in_parent = right;
 201
 202         /* update max_high for node and right */
 203         __rotate_change_maxhigh(node, right);
 204 }
 205
 206 /* The right rotation "pivots" around the link from node to node->left, and
 207  * - node will be linked to node->left's right child, and
 208  * - node->left's right child will be linked to node's left child.
 209  */
 210 static void __rotate_right(struct interval_node *node,
 211                            struct interval_node **root)
 212 {
 213         struct interval_node *left = node->in_left;
 214         struct interval_node *parent = node->in_parent;
 215
 216         node->in_left = left->in_right;
 217         if (node->in_left)
 218                 left->in_right->in_parent = node;
 219         left->in_right = node;
 220
 221         left->in_parent = parent;
 222         if (parent) {
 223                 if (node_is_right_child(node))
 224                         parent->in_right = left;
 225                 else
 226                         parent->in_left = left;
 227         } else {
 228                 *root = left;
 229         }
 230         node->in_parent = left;
 231
 232         /* update max_high for node and left */
 233         __rotate_change_maxhigh(node, left);
 234 }
 235
 236 #define interval_swap(a, b) do {                        \
 237         struct interval_node *c = a; a = b; b = c;      \
 238 } while (0)
 239
 240 /*
 241  * Operations INSERT and DELETE, when run on a tree with n keys,
 242  * take O(logN) time.Because they modify the tree, the result
 243  * may violate the red-black properties.To restore these properties,
 244  * we must change the colors of some of the nodes in the tree
 245  * and also change the pointer structure.
 246  */
 247 static void interval_insert_color(struct interval_node *node,
 248                                   struct interval_node **root)
 249 {
 250         struct interval_node *parent, *gparent;
 251
 252         while ((parent = node->in_parent) && node_is_red(parent)) {
 253                 gparent = parent->in_parent;
 254                 /* Parent is RED, so gparent must not be NULL */
 255                 if (node_is_left_child(parent)) {
 256                         struct interval_node *uncle;
 257
 258                         uncle = gparent->in_right;
 259                         if (uncle && node_is_red(uncle)) {
 260                                 uncle->in_color = INTERVAL_BLACK;
 261                                 parent->in_color = INTERVAL_BLACK;
 262                                 gparent->in_color = INTERVAL_RED;
 263                                 node = gparent;
 264                                 continue;
 265                         }
 266
 267                         if (parent->in_right == node) {
 268                                 __rotate_left(parent, root);
 269                                 interval_swap(node, parent);
 270                         }
 271
 272                         parent->in_color = INTERVAL_BLACK;
 273                         gparent->in_color = INTERVAL_RED;
 274                         __rotate_right(gparent, root);
 275                 } else {
 276                         struct interval_node *uncle;
 277
 278                         uncle = gparent->in_left;
 279                         if (uncle && node_is_red(uncle)) {
 280                                 uncle->in_color = INTERVAL_BLACK;
 281                                 parent->in_color = INTERVAL_BLACK;
 282                                 gparent->in_color = INTERVAL_RED;
 283                                 node = gparent;
 284                                 continue;
 285                         }
 286
 287                         if (node_is_left_child(node)) {
 288                                 __rotate_right(parent, root);
 289                                 interval_swap(node, parent);
 290                         }
 291
 292                         parent->in_color = INTERVAL_BLACK;
 293                         gparent->in_color = INTERVAL_RED;
 294                         __rotate_left(gparent, root);
 295                 }
 296         }
 297
 298         (*root)->in_color = INTERVAL_BLACK;
 299 }
 300
 301 struct interval_node *interval_insert(struct interval_node *node,
 302                                       struct interval_node **root)
 303
 304 {
 305         struct interval_node **p, *parent = NULL;
 306
 307         LASSERT(!interval_is_intree(node));
 308         p = root;
 309         while (*p) {
 310                 parent = *p;
 311                 if (node_equal(parent, node))
 312                         return parent;
 313
 314                 /* max_high field must be updated after each iteration */
 315                 if (parent->in_max_high < interval_high(node))
 316                         parent->in_max_high = interval_high(node);
 317
 318                 if (extent_compare(&node->in_extent, &parent->in_extent) < 0)
 319                         p = &parent->in_left;
 320                 else
 321                         p = &parent->in_right;
 322         }
 323
 324         /* link node into the tree */
 325         node->in_parent = parent;
 326         node->in_color = INTERVAL_RED;
 327         node->in_left = NULL;
 328         node->in_right = NULL;
 329         *p = node;
 330
 331         interval_insert_color(node, root);
 332         node->in_intree = 1;
 333
 334         return NULL;
 335 }
 336 EXPORT_SYMBOL(interval_insert);
 337
 338 static inline int node_is_black_or_0(struct interval_node *node)
 339 {
 340         return !node || node_is_black(node);
 341 }
 342
 343 static void interval_erase_color(struct interval_node *node,
 344                                  struct interval_node *parent,
 345                                  struct interval_node **root)
 346 {
 347         struct interval_node *tmp;
 348
 349         while (node_is_black_or_0(node) && node != *root) {
 350                 if (parent->in_left == node) {
 351                         tmp = parent->in_right;
 352                         if (node_is_red(tmp)) {
 353                                 tmp->in_color = INTERVAL_BLACK;
 354                                 parent->in_color = INTERVAL_RED;
 355                                 __rotate_left(parent, root);
 356                                 tmp = parent->in_right;
 357                         }
 358                         if (node_is_black_or_0(tmp->in_left) &&
 359                             node_is_black_or_0(tmp->in_right)) {
 360                                 tmp->in_color = INTERVAL_RED;
 361                                 node = parent;
 362                                 parent = node->in_parent;
 363                         } else {
 364                                 if (node_is_black_or_0(tmp->in_right)) {
 365                                         struct interval_node *o_left;
 366
 367                                         o_left = tmp->in_left;
 368                                         if (o_left)
 369                                                 o_left->in_color = INTERVAL_BLACK;
 370                                         tmp->in_color = INTERVAL_RED;
 371                                         __rotate_right(tmp, root);
 372                                         tmp = parent->in_right;
 373                                 }
 374                                 tmp->in_color = parent->in_color;
 375                                 parent->in_color = INTERVAL_BLACK;
 376                                 if (tmp->in_right)
 377                                         tmp->in_right->in_color = INTERVAL_BLACK;
 378                                 __rotate_left(parent, root);
 379                                 node = *root;
 380                                 break;
 381                         }
 382                 } else {
 383                         tmp = parent->in_left;
 384                         if (node_is_red(tmp)) {
 385                                 tmp->in_color = INTERVAL_BLACK;
 386                                 parent->in_color = INTERVAL_RED;
 387                                 __rotate_right(parent, root);
 388                                 tmp = parent->in_left;
 389                         }
 390                         if (node_is_black_or_0(tmp->in_left) &&
 391                             node_is_black_or_0(tmp->in_right)) {
 392                                 tmp->in_color = INTERVAL_RED;
 393                                 node = parent;
 394                                 parent = node->in_parent;
 395                         } else {
 396                                 if (node_is_black_or_0(tmp->in_left)) {
 397                                         struct interval_node *o_right;
 398
 399                                         o_right = tmp->in_right;
 400                                         if (o_right)
 401                                                 o_right->in_color = INTERVAL_BLACK;
 402                                         tmp->in_color = INTERVAL_RED;
 403                                         __rotate_left(tmp, root);
 404                                         tmp = parent->in_left;
 405                                 }
 406                                 tmp->in_color = parent->in_color;
 407                                 parent->in_color = INTERVAL_BLACK;
 408                                 if (tmp->in_left)
 409                                         tmp->in_left->in_color = INTERVAL_BLACK;
 410                                 __rotate_right(parent, root);
 411                                 node = *root;
 412                                 break;
 413                         }
 414                 }
 415         }
 416         if (node)
 417                 node->in_color = INTERVAL_BLACK;
 418 }
 419
 420 /*
 421  * if the @max_high value of @node is changed, this function traverse  a path
 422  * from node  up to the root to update max_high for the whole tree.
 423  */
 424 static void update_maxhigh(struct interval_node *node,
 425                            __u64  old_maxhigh)
 426 {
 427         __u64 left_max, right_max;
 428
 429         while (node) {
 430                 left_max = node->in_left ? node->in_left->in_max_high : 0;
 431                 right_max = node->in_right ? node->in_right->in_max_high : 0;
 432                 node->in_max_high = max(interval_high(node),
 433                                         max(left_max, right_max));
 434
 435                 if (node->in_max_high >= old_maxhigh)
 436                         break;
 437                 node = node->in_parent;
 438         }
 439 }
 440
 441 void interval_erase(struct interval_node *node,
 442                     struct interval_node **root)
 443 {
 444         struct interval_node *child, *parent;
 445         int color;
 446
 447         LASSERT(interval_is_intree(node));
 448         node->in_intree = 0;
 449         if (!node->in_left) {
 450                 child = node->in_right;
 451         } else if (!node->in_right) {
 452                 child = node->in_left;
 453         } else { /* Both left and right child are not NULL */
 454                 struct interval_node *old = node;
 455
 456                 node = interval_next(node);
 457                 child = node->in_right;
 458                 parent = node->in_parent;
 459                 color = node->in_color;
 460
 461                 if (child)
 462                         child->in_parent = parent;
 463                 if (parent == old)
 464                         parent->in_right = child;
 465                 else
 466                         parent->in_left = child;
 467
 468                 node->in_color = old->in_color;
 469                 node->in_right = old->in_right;
 470                 node->in_left = old->in_left;
 471                 node->in_parent = old->in_parent;
 472
 473                 if (old->in_parent) {
 474                         if (node_is_left_child(old))
 475                                 old->in_parent->in_left = node;
 476                         else
 477                                 old->in_parent->in_right = node;
 478                 } else {
 479                         *root = node;
 480                 }
 481
 482                 old->in_left->in_parent = node;
 483                 if (old->in_right)
 484                         old->in_right->in_parent = node;
 485                 update_maxhigh(child ? : parent, node->in_max_high);
 486                 update_maxhigh(node, old->in_max_high);
 487                 if (parent == old)
 488                         parent = node;
 489                 goto color;
 490         }
 491         parent = node->in_parent;
 492         color = node->in_color;
 493
 494         if (child)
 495                 child->in_parent = parent;
 496         if (parent) {
 497                 if (node_is_left_child(node))
 498                         parent->in_left = child;
 499                 else
 500                         parent->in_right = child;
 501         } else {
 502                 *root = child;
 503         }
 504
 505         update_maxhigh(child ? : parent, node->in_max_high);
 506
 507 color:
 508         if (color == INTERVAL_BLACK)
 509                 interval_erase_color(child, parent, root);
 510 }
 511 EXPORT_SYMBOL(interval_erase);
 512
 513 static inline int interval_may_overlap(struct interval_node *node,
 514                                        struct interval_node_extent *ext)
 515 {
 516         return (ext->start <= node->in_max_high &&
 517                 ext->end >= interval_low(node));
 518 }
 519
 520 /*
 521  * This function finds all intervals that overlap interval ext,
 522  * and calls func to handle resulted intervals one by one.
 523  * in lustre, this function will find all conflicting locks in
 524  * the granted queue and add these locks to the ast work list.
 525  *
 526  * {
 527  *      if (!node)
 528  *              return 0;
 529  *      if (ext->end < interval_low(node)) {
 530  *              interval_search(node->in_left, ext, func, data);
 531  *      } else if (interval_may_overlap(node, ext)) {
 532  *              if (extent_overlapped(ext, &node->in_extent))
 533  *                      func(node, data);
 534  *              interval_search(node->in_left, ext, func, data);
 535  *              interval_search(node->in_right, ext, func, data);
 536  *      }
 537  *      return 0;
 538  * }
 539  *
 540  */
 541 enum interval_iter interval_search(struct interval_node *node,
 542                                    struct interval_node_extent *ext,
 543                                    interval_callback_t func,
 544                                    void *data)
 545 {
 546         enum interval_iter rc = INTERVAL_ITER_CONT;
 547         struct interval_node *parent;
 548
 549         LASSERT(ext);
 550         LASSERT(func);
 551
 552         while (node) {
 553                 if (ext->end < interval_low(node)) {
 554                         if (node->in_left) {
 555                                 node = node->in_left;
 556                                 continue;
 557                         }
 558                 } else if (interval_may_overlap(node, ext)) {
 559                         if (extent_overlapped(ext, &node->in_extent)) {
 560                                 rc = func(node, data);
 561                                 if (rc == INTERVAL_ITER_STOP)
 562                                         break;
 563                         }
 564
 565                         if (node->in_left) {
 566                                 node = node->in_left;
 567                                 continue;
 568                         }
 569                         if (node->in_right) {
 570                                 node = node->in_right;
 571                                 continue;
 572                         }
 573                 }
 574
 575                 parent = node->in_parent;
 576                 while (parent) {
 577                         if (node_is_left_child(node) &&
 578                             parent->in_right) {
 579                                 /*
 580                                  * If we ever got the left, it means that the
 581                                  * parent met ext->end<interval_low(parent), or
 582                                  * may_overlap(parent). If the former is true,
 583                                  * we needn't go back. So stop early and check
 584                                  * may_overlap(parent) after this loop.
 585                                  */
 586                                 node = parent->in_right;
 587                                 break;
 588                         }
 589                         node = parent;
 590                         parent = parent->in_parent;
 591                 }
 592                 if (!parent || !interval_may_overlap(parent, ext))
 593                         break;
 594         }
 595
 596         return rc;
 597 }
 598 EXPORT_SYMBOL(interval_search);