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