fs/reiser4/tree_walk.c

   1 /* Copyright 2001, 2002, 2003 by Hans Reiser, licensing governed by
   2  * reiser4/README */
   3
   4 /* Routines and macros to:
   5
   6    get_left_neighbor()
   7
   8    get_right_neighbor()
   9
  10    get_parent()
  11
  12    get_first_child()
  13
  14    get_last_child()
  15
  16    various routines to walk the whole tree and do things to it like
  17    repack it, or move it to tertiary storage.  Please make them as
  18    generic as is reasonable.
  19
  20 */
  21
  22 #include "forward.h"
  23 #include "debug.h"
  24 #include "dformat.h"
  25 #include "coord.h"
  26 #include "plugin/item/item.h"
  27 #include "jnode.h"
  28 #include "znode.h"
  29 #include "tree_walk.h"
  30 #include "tree.h"
  31 #include "super.h"
  32
  33 /* These macros are used internally in tree_walk.c in attempt to make
  34    lock_neighbor() code usable to build lock_parent(), lock_right_neighbor,
  35    lock_left_neighbor */
  36 #define GET_NODE_BY_PTR_OFFSET(node, off) (*(znode**)(((unsigned long)(node)) + (off)))
  37 #define FIELD_OFFSET(name)  offsetof(znode, name)
  38 #define PARENT_PTR_OFFSET FIELD_OFFSET(in_parent.node)
  39 #define LEFT_PTR_OFFSET   FIELD_OFFSET(left)
  40 #define RIGHT_PTR_OFFSET  FIELD_OFFSET(right)
  41
  42 /* This is the generic procedure to get and lock `generic' neighbor (left or
  43     right neighbor or parent). It implements common algorithm for all cases of
  44     getting lock on neighbor node, only znode structure field is different in
  45     each case. This is parameterized by ptr_offset argument, which is byte
  46     offset for the pointer to the desired neighbor within the current node's
  47     znode structure. This function should be called with the tree lock held */
  48 static int lock_neighbor(
  49                                 /* resulting lock handle */
  50                                 lock_handle * result,
  51                                 /* znode to lock */
  52                                 znode * node,
  53                                 /* pointer to neighbor (or parent) znode field offset, in bytes from
  54                                    the base address of znode structure  */
  55                                 int ptr_offset,
  56                                 /* lock mode for longterm_lock_znode call */
  57                                 znode_lock_mode mode,
  58                                 /* lock request for longterm_lock_znode call */
  59                                 znode_lock_request req,
  60                                 /* GN_* flags */
  61                                 int flags, int rlocked)
  62 {
  63         reiser4_tree *tree = znode_get_tree(node);
  64         znode *neighbor;
  65         int ret;
  66
  67         assert("umka-236", node != NULL);
  68         assert("umka-237", tree != NULL);
  69         assert_rw_locked(&(tree->tree_lock));
  70
  71         if (flags & GN_TRY_LOCK)
  72                 req |= ZNODE_LOCK_NONBLOCK;
  73         if (flags & GN_SAME_ATOM)
  74                 req |= ZNODE_LOCK_DONT_FUSE;
  75
  76         /* get neighbor's address by using of sibling link, quit while loop
  77            (and return) if link is not available. */
  78         while (1) {
  79                 neighbor = GET_NODE_BY_PTR_OFFSET(node, ptr_offset);
  80
  81                 /* return -E_NO_NEIGHBOR if parent or side pointer is NULL or if
  82                  * node pointed by it is not connected.
  83                  *
  84                  * However, GN_ALLOW_NOT_CONNECTED option masks "connected"
  85                  * check and allows passing reference to not connected znode to
  86                  * subsequent longterm_lock_znode() call.  This kills possible
  87                  * busy loop if we are trying to get longterm lock on locked but
  88                  * not yet connected parent node. */
  89                 if (neighbor == NULL || !((flags & GN_ALLOW_NOT_CONNECTED)
  90                                           || znode_is_connected(neighbor))) {
  91                         return RETERR(-E_NO_NEIGHBOR);
  92                 }
  93
  94                 /* protect it from deletion. */
  95                 zref(neighbor);
  96
  97                 rlocked ? read_unlock_tree(tree) : write_unlock_tree(tree);
  98
  99                 ret = longterm_lock_znode(result, neighbor, mode, req);
 100
 101                 /* The lock handle obtains its own reference, release the one from above. */
 102                 zput(neighbor);
 103
 104                 rlocked ? read_lock_tree(tree) : write_lock_tree(tree);
 105
 106                 /* restart if node we got reference to is being
 107                    invalidated. we should not get reference to this node
 108                    again. */
 109                 if (ret == -EINVAL)
 110                         continue;
 111                 if (ret)
 112                         return ret;
 113
 114                 /* check if neighbor link still points to just locked znode;
 115                    the link could have been changed while the process slept. */
 116                 if (neighbor == GET_NODE_BY_PTR_OFFSET(node, ptr_offset))
 117                         return 0;
 118
 119                 /* znode was locked by mistake; unlock it and restart locking
 120                    process from beginning. */
 121                 rlocked ? read_unlock_tree(tree) : write_unlock_tree(tree);
 122                 longterm_unlock_znode(result);
 123                 rlocked ? read_lock_tree(tree) : write_lock_tree(tree);
 124         }
 125 }
 126
 127 /* get parent node with longterm lock, accepts GN* flags. */
 128 int reiser4_get_parent_flags(lock_handle * lh /* resulting lock handle */ ,
 129                              znode * node /* child node */ ,
 130                              znode_lock_mode mode
 131                              /* type of lock: read or write */ ,
 132                              int flags /* GN_* flags */ )
 133 {
 134         int result;
 135
 136         read_lock_tree(znode_get_tree(node));
 137         result = lock_neighbor(lh, node, PARENT_PTR_OFFSET, mode,
 138                                ZNODE_LOCK_HIPRI, flags, 1);
 139         read_unlock_tree(znode_get_tree(node));
 140         return result;
 141 }
 142
 143 /* wrapper function to lock right or left neighbor depending on GN_GO_LEFT
 144    bit in @flags parameter  */
 145 /* Audited by: umka (2002.06.14) */
 146 static inline int
 147 lock_side_neighbor(lock_handle * result,
 148                    znode * node, znode_lock_mode mode, int flags, int rlocked)
 149 {
 150         int ret;
 151         int ptr_offset;
 152         znode_lock_request req;
 153
 154         if (flags & GN_GO_LEFT) {
 155                 ptr_offset = LEFT_PTR_OFFSET;
 156                 req = ZNODE_LOCK_LOPRI;
 157         } else {
 158                 ptr_offset = RIGHT_PTR_OFFSET;
 159                 req = ZNODE_LOCK_HIPRI;
 160         }
 161
 162         ret =
 163             lock_neighbor(result, node, ptr_offset, mode, req, flags, rlocked);
 164
 165         if (ret == -E_NO_NEIGHBOR)      /* if we walk left or right -E_NO_NEIGHBOR does not
 166                                          * guarantee that neighbor is absent in the
 167                                          * tree; in this case we return -ENOENT --
 168                                          * means neighbor at least not found in
 169                                          * cache */
 170                 return RETERR(-ENOENT);
 171
 172         return ret;
 173 }
 174
 175 #if REISER4_DEBUG
 176
 177 int check_sibling_list(znode * node)
 178 {
 179         znode *scan;
 180         znode *next;
 181
 182         assert("nikita-3283", LOCK_CNT_GTZ(write_locked_tree));
 183
 184         if (node == NULL)
 185                 return 1;
 186
 187         if (ZF_ISSET(node, JNODE_RIP))
 188                 return 1;
 189
 190         assert("nikita-3270", node != NULL);
 191         assert_rw_write_locked(&(znode_get_tree(node)->tree_lock));
 192
 193         for (scan = node; znode_is_left_connected(scan); scan = next) {
 194                 next = scan->left;
 195                 if (next != NULL && !ZF_ISSET(next, JNODE_RIP)) {
 196                         assert("nikita-3271", znode_is_right_connected(next));
 197                         assert("nikita-3272", next->right == scan);
 198                 } else
 199                         break;
 200         }
 201         for (scan = node; znode_is_right_connected(scan); scan = next) {
 202                 next = scan->right;
 203                 if (next != NULL && !ZF_ISSET(next, JNODE_RIP)) {
 204                         assert("nikita-3273", znode_is_left_connected(next));
 205                         assert("nikita-3274", next->left == scan);
 206                 } else
 207                         break;
 208         }
 209         return 1;
 210 }
 211
 212 #endif
 213
 214 /* Znode sibling pointers maintenence. */
 215
 216 /* Znode sibling pointers are established between any neighbored nodes which are
 217    in cache.  There are two znode state bits (JNODE_LEFT_CONNECTED,
 218    JNODE_RIGHT_CONNECTED), if left or right sibling pointer contains actual
 219    value (even NULL), corresponded JNODE_*_CONNECTED bit is set.
 220
 221    Reiser4 tree operations which may allocate new znodes (CBK, tree balancing)
 222    take care about searching (hash table lookup may be required) of znode
 223    neighbors, establishing sibling pointers between them and setting
 224    JNODE_*_CONNECTED state bits. */
 225
 226 /* adjusting of sibling pointers and `connected' states for two
 227    neighbors; works if one neighbor is NULL (was not found). */
 228
 229 /* FIXME-VS: this is unstatic-ed to use in tree.c in prepare_twig_cut */
 230 void link_left_and_right(znode * left, znode * right)
 231 {
 232         assert("nikita-3275", check_sibling_list(left));
 233         assert("nikita-3275", check_sibling_list(right));
 234
 235         if (left != NULL) {
 236                 if (left->right == NULL) {
 237                         left->right = right;
 238                         ZF_SET(left, JNODE_RIGHT_CONNECTED);
 239
 240                         ON_DEBUG(left->right_version =
 241                                  atomic_inc_return(&delim_key_version);
 242                             );
 243
 244                 } else if (ZF_ISSET(left->right, JNODE_HEARD_BANSHEE)
 245                            && left->right != right) {
 246
 247                         ON_DEBUG(left->right->left_version =
 248                                  atomic_inc_return(&delim_key_version);
 249                                  left->right_version =
 250                                  atomic_inc_return(&delim_key_version););
 251
 252                         left->right->left = NULL;
 253                         left->right = right;
 254                         ZF_SET(left, JNODE_RIGHT_CONNECTED);
 255                 } else
 256                         /*
 257                          * there is a race condition in renew_sibling_link()
 258                          * and assertions below check that it is only one
 259                          * there. Thread T1 calls renew_sibling_link() without
 260                          * GN_NO_ALLOC flag. zlook() doesn't find neighbor
 261                          * node, but before T1 gets to the
 262                          * link_left_and_right(), another thread T2 creates
 263                          * neighbor node and connects it. check for
 264                          * left->right == NULL above protects T1 from
 265                          * overwriting correct left->right pointer installed
 266                          * by T2.
 267                          */
 268                         assert("nikita-3302",
 269                                right == NULL || left->right == right);
 270         }
 271         if (right != NULL) {
 272                 if (right->left == NULL) {
 273                         right->left = left;
 274                         ZF_SET(right, JNODE_LEFT_CONNECTED);
 275
 276                         ON_DEBUG(right->left_version =
 277                                  atomic_inc_return(&delim_key_version);
 278                             );
 279
 280                 } else if (ZF_ISSET(right->left, JNODE_HEARD_BANSHEE)
 281                            && right->left != left) {
 282
 283                         ON_DEBUG(right->left->right_version =
 284                                  atomic_inc_return(&delim_key_version);
 285                                  right->left_version =
 286                                  atomic_inc_return(&delim_key_version););
 287
 288                         right->left->right = NULL;
 289                         right->left = left;
 290                         ZF_SET(right, JNODE_LEFT_CONNECTED);
 291
 292                 } else
 293                         assert("nikita-3303",
 294                                left == NULL || right->left == left);
 295         }
 296         assert("nikita-3275", check_sibling_list(left));
 297         assert("nikita-3275", check_sibling_list(right));
 298 }
 299
 300 /* Audited by: umka (2002.06.14) */
 301 static void link_znodes(znode * first, znode * second, int to_left)
 302 {
 303         if (to_left)
 304                 link_left_and_right(second, first);
 305         else
 306                 link_left_and_right(first, second);
 307 }
 308
 309 /* getting of next (to left or to right, depend on gn_to_left bit in flags)
 310    coord's unit position in horizontal direction, even across node
 311    boundary. Should be called under tree lock, it protects nonexistence of
 312    sibling link on parent level, if lock_side_neighbor() fails with
 313    -ENOENT. */
 314 static int far_next_coord(coord_t * coord, lock_handle * handle, int flags)
 315 {
 316         int ret;
 317         znode *node;
 318         reiser4_tree *tree;
 319
 320         assert("umka-243", coord != NULL);
 321         assert("umka-244", handle != NULL);
 322         assert("zam-1069", handle->node == NULL);
 323
 324         ret =
 325             (flags & GN_GO_LEFT) ? coord_prev_unit(coord) :
 326             coord_next_unit(coord);
 327         if (!ret)
 328                 return 0;
 329
 330         ret =
 331             lock_side_neighbor(handle, coord->node, ZNODE_READ_LOCK, flags, 0);
 332         if (ret)
 333                 return ret;
 334
 335         node = handle->node;
 336         tree = znode_get_tree(node);
 337         write_unlock_tree(tree);
 338
 339         coord_init_zero(coord);
 340
 341         /* We avoid synchronous read here if it is specified by flag. */
 342         if ((flags & GN_ASYNC) && znode_page(handle->node) == NULL) {
 343                 ret = jstartio(ZJNODE(handle->node));
 344                 if (!ret)
 345                         ret = -E_REPEAT;
 346                 goto error_locked;
 347         }
 348
 349         /* corresponded zrelse() should be called by the clients of
 350            far_next_coord(), in place when this node gets unlocked. */
 351         ret = zload(handle->node);
 352         if (ret)
 353                 goto error_locked;
 354
 355         if (flags & GN_GO_LEFT)
 356                 coord_init_last_unit(coord, node);
 357         else
 358                 coord_init_first_unit(coord, node);
 359
 360         if (0) {
 361               error_locked:
 362                 longterm_unlock_znode(handle);
 363         }
 364         write_lock_tree(tree);
 365         return ret;
 366 }
 367
 368 /* Very significant function which performs a step in horizontal direction
 369    when sibling pointer is not available.  Actually, it is only function which
 370    does it.
 371    Note: this function does not restore locking status at exit,
 372    caller should does care about proper unlocking and zrelsing */
 373 static int
 374 renew_sibling_link(coord_t * coord, lock_handle * handle, znode * child,
 375                    tree_level level, int flags, int *nr_locked)
 376 {
 377         int ret;
 378         int to_left = flags & GN_GO_LEFT;
 379         reiser4_block_nr da;
 380         /* parent of the neighbor node; we set it to parent until not sharing
 381            of one parent between child and neighbor node is detected */
 382         znode *side_parent = coord->node;
 383         reiser4_tree *tree = znode_get_tree(child);
 384         znode *neighbor = NULL;
 385
 386         assert("umka-245", coord != NULL);
 387         assert("umka-246", handle != NULL);
 388         assert("umka-247", child != NULL);
 389         assert("umka-303", tree != NULL);
 390
 391         init_lh(handle);
 392         write_lock_tree(tree);
 393         ret = far_next_coord(coord, handle, flags);
 394
 395         if (ret) {
 396                 if (ret != -ENOENT) {
 397                         write_unlock_tree(tree);
 398                         return ret;
 399                 }
 400         } else {
 401                 item_plugin *iplug;
 402
 403                 if (handle->node != NULL) {
 404                         (*nr_locked)++;
 405                         side_parent = handle->node;
 406                 }
 407
 408                 /* does coord object points to internal item? We do not
 409                    support sibling pointers between znode for formatted and
 410                    unformatted nodes and return -E_NO_NEIGHBOR in that case. */
 411                 iplug = item_plugin_by_coord(coord);
 412                 if (!item_is_internal(coord)) {
 413                         link_znodes(child, NULL, to_left);
 414                         write_unlock_tree(tree);
 415                         /* we know there can't be formatted neighbor */
 416                         return RETERR(-E_NO_NEIGHBOR);
 417                 }
 418                 write_unlock_tree(tree);
 419
 420                 iplug->s.internal.down_link(coord, NULL, &da);
 421
 422                 if (flags & GN_NO_ALLOC) {
 423                         neighbor = zlook(tree, &da);
 424                 } else {
 425                         neighbor =
 426                             zget(tree, &da, side_parent, level,
 427                                  reiser4_ctx_gfp_mask_get());
 428                 }
 429
 430                 if (IS_ERR(neighbor)) {
 431                         ret = PTR_ERR(neighbor);
 432                         return ret;
 433                 }
 434
 435                 if (neighbor)
 436                         /* update delimiting keys */
 437                         set_child_delimiting_keys(coord->node, coord, neighbor);
 438
 439                 write_lock_tree(tree);
 440         }
 441
 442         if (likely(neighbor == NULL ||
 443                    (znode_get_level(child) == znode_get_level(neighbor)
 444                     && child != neighbor)))
 445                 link_znodes(child, neighbor, to_left);
 446         else {
 447                 warning("nikita-3532",
 448                         "Sibling nodes on the different levels: %i != %i\n",
 449                         znode_get_level(child), znode_get_level(neighbor));
 450                 ret = RETERR(-EIO);
 451         }
 452
 453         write_unlock_tree(tree);
 454
 455         /* if GN_NO_ALLOC isn't set we keep reference to neighbor znode */
 456         if (neighbor != NULL && (flags & GN_NO_ALLOC))
 457                 /* atomic_dec(&ZJNODE(neighbor)->x_count); */
 458                 zput(neighbor);
 459
 460         return ret;
 461 }
 462
 463 /* This function is for establishing of one side relation. */
 464 /* Audited by: umka (2002.06.14) */
 465 static int connect_one_side(coord_t * coord, znode * node, int flags)
 466 {
 467         coord_t local;
 468         lock_handle handle;
 469         int nr_locked;
 470         int ret;
 471
 472         assert("umka-248", coord != NULL);
 473         assert("umka-249", node != NULL);
 474
 475         coord_dup_nocheck(&local, coord);
 476
 477         init_lh(&handle);
 478
 479         ret =
 480             renew_sibling_link(&local, &handle, node, znode_get_level(node),
 481                                flags | GN_NO_ALLOC, &nr_locked);
 482
 483         if (handle.node != NULL) {
 484                 /* complementary operations for zload() and lock() in far_next_coord() */
 485                 zrelse(handle.node);
 486                 longterm_unlock_znode(&handle);
 487         }
 488
 489         /* we catch error codes which are not interesting for us because we
 490            run renew_sibling_link() only for znode connection. */
 491         if (ret == -ENOENT || ret == -E_NO_NEIGHBOR)
 492                 return 0;
 493
 494         return ret;
 495 }
 496
 497 /* if @child is not in `connected' state, performs hash searches for left and
 498    right neighbor nodes and establishes horizontal sibling links */
 499 /* Audited by: umka (2002.06.14), umka (2002.06.15) */
 500 int connect_znode(coord_t * parent_coord, znode * child)
 501 {
 502         reiser4_tree *tree = znode_get_tree(child);
 503         int ret = 0;
 504
 505         assert("zam-330", parent_coord != NULL);
 506         assert("zam-331", child != NULL);
 507         assert("zam-332", parent_coord->node != NULL);
 508         assert("umka-305", tree != NULL);
 509
 510         /* it is trivial to `connect' root znode because it can't have
 511            neighbors */
 512         if (znode_above_root(parent_coord->node)) {
 513                 child->left = NULL;
 514                 child->right = NULL;
 515                 ZF_SET(child, JNODE_LEFT_CONNECTED);
 516                 ZF_SET(child, JNODE_RIGHT_CONNECTED);
 517
 518                 ON_DEBUG(child->left_version =
 519                          atomic_inc_return(&delim_key_version);
 520                          child->right_version =
 521                          atomic_inc_return(&delim_key_version););
 522
 523                 return 0;
 524         }
 525
 526         /* load parent node */
 527         coord_clear_iplug(parent_coord);
 528         ret = zload(parent_coord->node);
 529
 530         if (ret != 0)
 531                 return ret;
 532
 533         /* protect `connected' state check by tree_lock */
 534         read_lock_tree(tree);
 535
 536         if (!znode_is_right_connected(child)) {
 537                 read_unlock_tree(tree);
 538                 /* connect right (default is right) */
 539                 ret = connect_one_side(parent_coord, child, GN_NO_ALLOC);
 540                 if (ret)
 541                         goto zrelse_and_ret;
 542
 543                 read_lock_tree(tree);
 544         }
 545
 546         ret = znode_is_left_connected(child);
 547
 548         read_unlock_tree(tree);
 549
 550         if (!ret) {
 551                 ret =
 552                     connect_one_side(parent_coord, child,
 553                                      GN_NO_ALLOC | GN_GO_LEFT);
 554         } else
 555                 ret = 0;
 556
 557       zrelse_and_ret:
 558         zrelse(parent_coord->node);
 559
 560         return ret;
 561 }
 562
 563 /* this function is like renew_sibling_link() but allocates neighbor node if
 564    it doesn't exist and `connects' it. It may require making two steps in
 565    horizontal direction, first one for neighbor node finding/allocation,
 566    second one is for finding neighbor of neighbor to connect freshly allocated
 567    znode. */
 568 /* Audited by: umka (2002.06.14), umka (2002.06.15) */
 569 static int
 570 renew_neighbor(coord_t * coord, znode * node, tree_level level, int flags)
 571 {
 572         coord_t local;
 573         lock_handle empty[2];
 574         reiser4_tree *tree = znode_get_tree(node);
 575         znode *neighbor = NULL;
 576         int nr_locked = 0;
 577         int ret;
 578
 579         assert("umka-250", coord != NULL);
 580         assert("umka-251", node != NULL);
 581         assert("umka-307", tree != NULL);
 582         assert("umka-308", level <= tree->height);
 583
 584         /* umka (2002.06.14)
 585            Here probably should be a check for given "level" validness.
 586            Something like assert("xxx-yyy", level < REAL_MAX_ZTREE_HEIGHT);
 587          */
 588
 589         coord_dup(&local, coord);
 590
 591         ret =
 592             renew_sibling_link(&local, &empty[0], node, level,
 593                                flags & ~GN_NO_ALLOC, &nr_locked);
 594         if (ret)
 595                 goto out;
 596
 597         /* tree lock is not needed here because we keep parent node(s) locked
 598            and reference to neighbor znode incremented */
 599         neighbor = (flags & GN_GO_LEFT) ? node->left : node->right;
 600
 601         read_lock_tree(tree);
 602         ret = znode_is_connected(neighbor);
 603         read_unlock_tree(tree);
 604         if (ret) {
 605                 ret = 0;
 606                 goto out;
 607         }
 608
 609         ret =
 610             renew_sibling_link(&local, &empty[nr_locked], neighbor, level,
 611                                flags | GN_NO_ALLOC, &nr_locked);
 612         /* second renew_sibling_link() call is used for znode connection only,
 613            so we can live with these errors */
 614         if (-ENOENT == ret || -E_NO_NEIGHBOR == ret)
 615                 ret = 0;
 616
 617       out:
 618
 619         for (--nr_locked; nr_locked >= 0; --nr_locked) {
 620                 zrelse(empty[nr_locked].node);
 621                 longterm_unlock_znode(&empty[nr_locked]);
 622         }
 623
 624         if (neighbor != NULL)
 625                 /* decrement znode reference counter without actually
 626                    releasing it. */
 627                 atomic_dec(&ZJNODE(neighbor)->x_count);
 628
 629         return ret;
 630 }
 631
 632 /*
 633    reiser4_get_neighbor() -- lock node's neighbor.
 634
 635    reiser4_get_neighbor() locks node's neighbor (left or right one, depends on
 636    given parameter) using sibling link to it. If sibling link is not available
 637    (i.e. neighbor znode is not in cache) and flags allow read blocks, we go one
 638    level up for information about neighbor's disk address. We lock node's
 639    parent, if it is common parent for both 'node' and its neighbor, neighbor's
 640    disk address is in next (to left or to right) down link from link that points
 641    to original node. If not, we need to lock parent's neighbor, read its content
 642    and take first(last) downlink with neighbor's disk address.  That locking
 643    could be done by using sibling link and lock_neighbor() function, if sibling
 644    link exists. In another case we have to go level up again until we find
 645    common parent or valid sibling link. Then go down
 646    allocating/connecting/locking/reading nodes until neighbor of first one is
 647    locked.
 648
 649    @neighbor:  result lock handle,
 650    @node: a node which we lock neighbor of,
 651    @lock_mode: lock mode {LM_READ, LM_WRITE},
 652    @flags: logical OR of {GN_*} (see description above) subset.
 653
 654    @return: 0 if success, negative value if lock was impossible due to an error
 655    or lack of neighbor node.
 656 */
 657
 658 /* Audited by: umka (2002.06.14), umka (2002.06.15) */
 659 int
 660 reiser4_get_neighbor(lock_handle * neighbor, znode * node,
 661                      znode_lock_mode lock_mode, int flags)
 662 {
 663         reiser4_tree *tree = znode_get_tree(node);
 664         lock_handle path[REAL_MAX_ZTREE_HEIGHT];
 665
 666         coord_t coord;
 667
 668         tree_level base_level;
 669         tree_level h = 0;
 670         int ret;
 671
 672         assert("umka-252", tree != NULL);
 673         assert("umka-253", neighbor != NULL);
 674         assert("umka-254", node != NULL);
 675
 676         base_level = znode_get_level(node);
 677
 678         assert("umka-310", base_level <= tree->height);
 679
 680         coord_init_zero(&coord);
 681
 682       again:
 683         /* first, we try to use simple lock_neighbor() which requires sibling
 684            link existence */
 685         read_lock_tree(tree);
 686         ret = lock_side_neighbor(neighbor, node, lock_mode, flags, 1);
 687         read_unlock_tree(tree);
 688         if (!ret) {
 689                 /* load znode content if it was specified */
 690                 if (flags & GN_LOAD_NEIGHBOR) {
 691                         ret = zload(node);
 692                         if (ret)
 693                                 longterm_unlock_znode(neighbor);
 694                 }
 695                 return ret;
 696         }
 697
 698         /* only -ENOENT means we may look upward and try to connect
 699            @node with its neighbor (if @flags allow us to do it) */
 700         if (ret != -ENOENT || !(flags & GN_CAN_USE_UPPER_LEVELS))
 701                 return ret;
 702
 703         /* before establishing of sibling link we lock parent node; it is
 704            required by renew_neighbor() to work.  */
 705         init_lh(&path[0]);
 706         ret = reiser4_get_parent(&path[0], node, ZNODE_READ_LOCK);
 707         if (ret)
 708                 return ret;
 709         if (znode_above_root(path[0].node)) {
 710                 longterm_unlock_znode(&path[0]);
 711                 return RETERR(-E_NO_NEIGHBOR);
 712         }
 713
 714         while (1) {
 715                 znode *child = (h == 0) ? node : path[h - 1].node;
 716                 znode *parent = path[h].node;
 717
 718                 ret = zload(parent);
 719                 if (ret)
 720                         break;
 721
 722                 ret = find_child_ptr(parent, child, &coord);
 723
 724                 if (ret) {
 725                         zrelse(parent);
 726                         break;
 727                 }
 728
 729                 /* try to establish missing sibling link */
 730                 ret = renew_neighbor(&coord, child, h + base_level, flags);
 731
 732                 zrelse(parent);
 733
 734                 switch (ret) {
 735                 case 0:
 736                         /* unlocking of parent znode prevents simple
 737                            deadlock situation */
 738                         done_lh(&path[h]);
 739
 740                         /* depend on tree level we stay on we repeat first
 741                            locking attempt ...  */
 742                         if (h == 0)
 743                                 goto again;
 744
 745                         /* ... or repeat establishing of sibling link at
 746                            one level below. */
 747                         --h;
 748                         break;
 749
 750                 case -ENOENT:
 751                         /* sibling link is not available -- we go
 752                            upward. */
 753                         init_lh(&path[h + 1]);
 754                         ret =
 755                             reiser4_get_parent(&path[h + 1], parent,
 756                                                ZNODE_READ_LOCK);
 757                         if (ret)
 758                                 goto fail;
 759                         ++h;
 760                         if (znode_above_root(path[h].node)) {
 761                                 ret = RETERR(-E_NO_NEIGHBOR);
 762                                 goto fail;
 763                         }
 764                         break;
 765
 766                 case -E_DEADLOCK:
 767                         /* there was lock request from hi-pri locker. if
 768                            it is possible we unlock last parent node and
 769                            re-lock it again. */
 770                         for (; reiser4_check_deadlock(); h--) {
 771                                 done_lh(&path[h]);
 772                                 if (h == 0)
 773                                         goto fail;
 774                         }
 775
 776                         break;
 777
 778                 default:        /* other errors. */
 779                         goto fail;
 780                 }
 781         }
 782       fail:
 783         ON_DEBUG(check_lock_node_data(node));
 784         ON_DEBUG(check_lock_data());
 785
 786         /* unlock path */
 787         do {
 788                 /* FIXME-Zam: when we get here from case -E_DEADLOCK's goto
 789                    fail; path[0] is already done_lh-ed, therefore
 790                    longterm_unlock_znode(&path[h]); is not applicable */
 791                 done_lh(&path[h]);
 792                 --h;
 793         } while (h + 1 != 0);
 794
 795         return ret;
 796 }
 797
 798 /* remove node from sibling list */
 799 /* Audited by: umka (2002.06.14) */
 800 void sibling_list_remove(znode * node)
 801 {
 802         reiser4_tree *tree;
 803
 804         tree = znode_get_tree(node);
 805         assert("umka-255", node != NULL);
 806         assert_rw_write_locked(&(tree->tree_lock));
 807         assert("nikita-3275", check_sibling_list(node));
 808
 809         write_lock_dk(tree);
 810         if (znode_is_right_connected(node) && node->right != NULL &&
 811             znode_is_left_connected(node) && node->left != NULL) {
 812                 assert("zam-32245",
 813                        keyeq(znode_get_rd_key(node),
 814                              znode_get_ld_key(node->right)));
 815                 znode_set_rd_key(node->left, znode_get_ld_key(node->right));
 816         }
 817         write_unlock_dk(tree);
 818
 819         if (znode_is_right_connected(node) && node->right != NULL) {
 820                 assert("zam-322", znode_is_left_connected(node->right));
 821                 node->right->left = node->left;
 822                 ON_DEBUG(node->right->left_version =
 823                          atomic_inc_return(&delim_key_version);
 824                     );
 825         }
 826         if (znode_is_left_connected(node) && node->left != NULL) {
 827                 assert("zam-323", znode_is_right_connected(node->left));
 828                 node->left->right = node->right;
 829                 ON_DEBUG(node->left->right_version =
 830                          atomic_inc_return(&delim_key_version);
 831                     );
 832         }
 833
 834         ZF_CLR(node, JNODE_LEFT_CONNECTED);
 835         ZF_CLR(node, JNODE_RIGHT_CONNECTED);
 836         ON_DEBUG(node->left = node->right = NULL;
 837                  node->left_version = atomic_inc_return(&delim_key_version);
 838                  node->right_version = atomic_inc_return(&delim_key_version););
 839         assert("nikita-3276", check_sibling_list(node));
 840 }
 841
 842 /* disconnect node from sibling list */
 843 void sibling_list_drop(znode * node)
 844 {
 845         znode *right;
 846         znode *left;
 847
 848         assert("nikita-2464", node != NULL);
 849         assert("nikita-3277", check_sibling_list(node));
 850
 851         right = node->right;
 852         if (right != NULL) {
 853                 assert("nikita-2465", znode_is_left_connected(right));
 854                 right->left = NULL;
 855                 ON_DEBUG(right->left_version =
 856                          atomic_inc_return(&delim_key_version);
 857                     );
 858         }
 859         left = node->left;
 860         if (left != NULL) {
 861                 assert("zam-323", znode_is_right_connected(left));
 862                 left->right = NULL;
 863                 ON_DEBUG(left->right_version =
 864                          atomic_inc_return(&delim_key_version);
 865                     );
 866         }
 867         ZF_CLR(node, JNODE_LEFT_CONNECTED);
 868         ZF_CLR(node, JNODE_RIGHT_CONNECTED);
 869         ON_DEBUG(node->left = node->right = NULL;
 870                  node->left_version = atomic_inc_return(&delim_key_version);
 871                  node->right_version = atomic_inc_return(&delim_key_version););
 872 }
 873
 874 /* Insert new node into sibling list. Regular balancing inserts new node
 875    after (at right side) existing and locked node (@before), except one case
 876    of adding new tree root node. @before should be NULL in that case. */
 877 void sibling_list_insert_nolock(znode * new, znode * before)
 878 {
 879         assert("zam-334", new != NULL);
 880         assert("nikita-3298", !znode_is_left_connected(new));
 881         assert("nikita-3299", !znode_is_right_connected(new));
 882         assert("nikita-3300", new->left == NULL);
 883         assert("nikita-3301", new->right == NULL);
 884         assert("nikita-3278", check_sibling_list(new));
 885         assert("nikita-3279", check_sibling_list(before));
 886
 887         if (before != NULL) {
 888                 assert("zam-333", znode_is_connected(before));
 889                 new->right = before->right;
 890                 new->left = before;
 891                 ON_DEBUG(new->right_version =
 892                          atomic_inc_return(&delim_key_version);
 893                          new->left_version =
 894                          atomic_inc_return(&delim_key_version););
 895                 if (before->right != NULL) {
 896                         before->right->left = new;
 897                         ON_DEBUG(before->right->left_version =
 898                                  atomic_inc_return(&delim_key_version);
 899                             );
 900                 }
 901                 before->right = new;
 902                 ON_DEBUG(before->right_version =
 903                          atomic_inc_return(&delim_key_version);
 904                     );
 905         } else {
 906                 new->right = NULL;
 907                 new->left = NULL;
 908                 ON_DEBUG(new->right_version =
 909                          atomic_inc_return(&delim_key_version);
 910                          new->left_version =
 911                          atomic_inc_return(&delim_key_version););
 912         }
 913         ZF_SET(new, JNODE_LEFT_CONNECTED);
 914         ZF_SET(new, JNODE_RIGHT_CONNECTED);
 915         assert("nikita-3280", check_sibling_list(new));
 916         assert("nikita-3281", check_sibling_list(before));
 917 }
 918
 919 /*
 920    Local variables:
 921    c-indentation-style: "K&R"
 922    mode-name: "LC"
 923    c-basic-offset: 8
 924    tab-width: 8
 925    fill-column: 80
 926    End:
 927 */