fs/reiserfs/fix_node.c

   1 /*
   2  * Copyright 2000 by Hans Reiser, licensing governed by reiserfs/README
   3  */
   4
   5 /**
   6  ** old_item_num
   7  ** old_entry_num
   8  ** set_entry_sizes
   9  ** create_virtual_node
  10  ** check_left
  11  ** check_right
  12  ** directory_part_size
  13  ** get_num_ver
  14  ** set_parameters
  15  ** is_leaf_removable
  16  ** are_leaves_removable
  17  ** get_empty_nodes
  18  ** get_lfree
  19  ** get_rfree
  20  ** is_left_neighbor_in_cache
  21  ** decrement_key
  22  ** get_far_parent
  23  ** get_parents
  24  ** can_node_be_removed
  25  ** ip_check_balance
  26  ** dc_check_balance_internal
  27  ** dc_check_balance_leaf
  28  ** dc_check_balance
  29  ** check_balance
  30  ** get_direct_parent
  31  ** get_neighbors
  32  ** fix_nodes
  33  **
  34  **
  35  **/
  36
  37 #include <linux/time.h>
  38 #include <linux/string.h>
  39 #include <linux/reiserfs_fs.h>
  40 #include <linux/buffer_head.h>
  41
  42 /* To make any changes in the tree we find a node, that contains item
  43    to be changed/deleted or position in the node we insert a new item
  44    to. We call this node S. To do balancing we need to decide what we
  45    will shift to left/right neighbor, or to a new node, where new item
  46    will be etc. To make this analysis simpler we build virtual
  47    node. Virtual node is an array of items, that will replace items of
  48    node S. (For instance if we are going to delete an item, virtual
  49    node does not contain it). Virtual node keeps information about
  50    item sizes and types, mergeability of first and last items, sizes
  51    of all entries in directory item. We use this array of items when
  52    calculating what we can shift to neighbors and how many nodes we
  53    have to have if we do not any shiftings, if we shift to left/right
  54    neighbor or to both. */
  55
  56 /* taking item number in virtual node, returns number of item, that it has in source buffer */
  57 static inline int old_item_num(int new_num, int affected_item_num, int mode)
  58 {
  59         if (mode == M_PASTE || mode == M_CUT || new_num < affected_item_num)
  60                 return new_num;
  61
  62         if (mode == M_INSERT) {
  63
  64                 RFALSE(new_num == 0,
  65                        "vs-8005: for INSERT mode and item number of inserted item");
  66
  67                 return new_num - 1;
  68         }
  69
  70         RFALSE(mode != M_DELETE,
  71                "vs-8010: old_item_num: mode must be M_DELETE (mode = \'%c\'",
  72                mode);
  73         /* delete mode */
  74         return new_num + 1;
  75 }
  76
  77 static void create_virtual_node(struct tree_balance *tb, int h)
  78 {
  79         struct item_head *ih;
  80         struct virtual_node *vn = tb->tb_vn;
  81         int new_num;
  82         struct buffer_head *Sh; /* this comes from tb->S[h] */
  83
  84         Sh = PATH_H_PBUFFER(tb->tb_path, h);
  85
  86         /* size of changed node */
  87         vn->vn_size =
  88             MAX_CHILD_SIZE(Sh) - B_FREE_SPACE(Sh) + tb->insert_size[h];
  89
  90         /* for internal nodes array if virtual items is not created */
  91         if (h) {
  92                 vn->vn_nr_item = (vn->vn_size - DC_SIZE) / (DC_SIZE + KEY_SIZE);
  93                 return;
  94         }
  95
  96         /* number of items in virtual node  */
  97         vn->vn_nr_item =
  98             B_NR_ITEMS(Sh) + ((vn->vn_mode == M_INSERT) ? 1 : 0) -
  99             ((vn->vn_mode == M_DELETE) ? 1 : 0);
 100
 101         /* first virtual item */
 102         vn->vn_vi = (struct virtual_item *)(tb->tb_vn + 1);
 103         memset(vn->vn_vi, 0, vn->vn_nr_item * sizeof(struct virtual_item));
 104         vn->vn_free_ptr += vn->vn_nr_item * sizeof(struct virtual_item);
 105
 106         /* first item in the node */
 107         ih = B_N_PITEM_HEAD(Sh, 0);
 108
 109         /* define the mergeability for 0-th item (if it is not being deleted) */
 110         if (op_is_left_mergeable(&(ih->ih_key), Sh->b_size)
 111             && (vn->vn_mode != M_DELETE || vn->vn_affected_item_num))
 112                 vn->vn_vi[0].vi_type |= VI_TYPE_LEFT_MERGEABLE;
 113
 114         /* go through all items those remain in the virtual node (except for the new (inserted) one) */
 115         for (new_num = 0; new_num < vn->vn_nr_item; new_num++) {
 116                 int j;
 117                 struct virtual_item *vi = vn->vn_vi + new_num;
 118                 int is_affected =
 119                     ((new_num != vn->vn_affected_item_num) ? 0 : 1);
 120
 121                 if (is_affected && vn->vn_mode == M_INSERT)
 122                         continue;
 123
 124                 /* get item number in source node */
 125                 j = old_item_num(new_num, vn->vn_affected_item_num,
 126                                  vn->vn_mode);
 127
 128                 vi->vi_item_len += ih_item_len(ih + j) + IH_SIZE;
 129                 vi->vi_ih = ih + j;
 130                 vi->vi_item = B_I_PITEM(Sh, ih + j);
 131                 vi->vi_uarea = vn->vn_free_ptr;
 132
 133                 // FIXME: there is no check, that item operation did not
 134                 // consume too much memory
 135                 vn->vn_free_ptr +=
 136                     op_create_vi(vn, vi, is_affected, tb->insert_size[0]);
 137                 if (tb->vn_buf + tb->vn_buf_size < vn->vn_free_ptr)
 138                         reiserfs_panic(tb->tb_sb, "vs-8030",
 139                                        "virtual node space consumed");
 140
 141                 if (!is_affected)
 142                         /* this is not being changed */
 143                         continue;
 144
 145                 if (vn->vn_mode == M_PASTE || vn->vn_mode == M_CUT) {
 146                         vn->vn_vi[new_num].vi_item_len += tb->insert_size[0];
 147                         vi->vi_new_data = vn->vn_data;  // pointer to data which is going to be pasted
 148                 }
 149         }
 150
 151         /* virtual inserted item is not defined yet */
 152         if (vn->vn_mode == M_INSERT) {
 153                 struct virtual_item *vi = vn->vn_vi + vn->vn_affected_item_num;
 154
 155                 RFALSE(vn->vn_ins_ih == NULL,
 156                        "vs-8040: item header of inserted item is not specified");
 157                 vi->vi_item_len = tb->insert_size[0];
 158                 vi->vi_ih = vn->vn_ins_ih;
 159                 vi->vi_item = vn->vn_data;
 160                 vi->vi_uarea = vn->vn_free_ptr;
 161
 162                 op_create_vi(vn, vi, 0 /*not pasted or cut */ ,
 163                              tb->insert_size[0]);
 164         }
 165
 166         /* set right merge flag we take right delimiting key and check whether it is a mergeable item */
 167         if (tb->CFR[0]) {
 168                 struct reiserfs_key *key;
 169
 170                 key = B_N_PDELIM_KEY(tb->CFR[0], tb->rkey[0]);
 171                 if (op_is_left_mergeable(key, Sh->b_size)
 172                     && (vn->vn_mode != M_DELETE
 173                         || vn->vn_affected_item_num != B_NR_ITEMS(Sh) - 1))
 174                         vn->vn_vi[vn->vn_nr_item - 1].vi_type |=
 175                             VI_TYPE_RIGHT_MERGEABLE;
 176
 177 #ifdef CONFIG_REISERFS_CHECK
 178                 if (op_is_left_mergeable(key, Sh->b_size) &&
 179                     !(vn->vn_mode != M_DELETE
 180                       || vn->vn_affected_item_num != B_NR_ITEMS(Sh) - 1)) {
 181                         /* we delete last item and it could be merged with right neighbor's first item */
 182                         if (!
 183                             (B_NR_ITEMS(Sh) == 1
 184                              && is_direntry_le_ih(B_N_PITEM_HEAD(Sh, 0))
 185                              && I_ENTRY_COUNT(B_N_PITEM_HEAD(Sh, 0)) == 1)) {
 186                                 /* node contains more than 1 item, or item is not directory item, or this item contains more than 1 entry */
 187                                 print_block(Sh, 0, -1, -1);
 188                                 reiserfs_panic(tb->tb_sb, "vs-8045",
 189                                                "rdkey %k, affected item==%d "
 190                                                "(mode==%c) Must be %c",
 191                                                key, vn->vn_affected_item_num,
 192                                                vn->vn_mode, M_DELETE);
 193                         }
 194                 }
 195 #endif
 196
 197         }
 198 }
 199
 200 /* using virtual node check, how many items can be shifted to left
 201    neighbor */
 202 static void check_left(struct tree_balance *tb, int h, int cur_free)
 203 {
 204         int i;
 205         struct virtual_node *vn = tb->tb_vn;
 206         struct virtual_item *vi;
 207         int d_size, ih_size;
 208
 209         RFALSE(cur_free < 0, "vs-8050: cur_free (%d) < 0", cur_free);
 210
 211         /* internal level */
 212         if (h > 0) {
 213                 tb->lnum[h] = cur_free / (DC_SIZE + KEY_SIZE);
 214                 return;
 215         }
 216
 217         /* leaf level */
 218
 219         if (!cur_free || !vn->vn_nr_item) {
 220                 /* no free space or nothing to move */
 221                 tb->lnum[h] = 0;
 222                 tb->lbytes = -1;
 223                 return;
 224         }
 225
 226         RFALSE(!PATH_H_PPARENT(tb->tb_path, 0),
 227                "vs-8055: parent does not exist or invalid");
 228
 229         vi = vn->vn_vi;
 230         if ((unsigned int)cur_free >=
 231             (vn->vn_size -
 232              ((vi->vi_type & VI_TYPE_LEFT_MERGEABLE) ? IH_SIZE : 0))) {
 233                 /* all contents of S[0] fits into L[0] */
 234
 235                 RFALSE(vn->vn_mode == M_INSERT || vn->vn_mode == M_PASTE,
 236                        "vs-8055: invalid mode or balance condition failed");
 237
 238                 tb->lnum[0] = vn->vn_nr_item;
 239                 tb->lbytes = -1;
 240                 return;
 241         }
 242
 243         d_size = 0, ih_size = IH_SIZE;
 244
 245         /* first item may be merge with last item in left neighbor */
 246         if (vi->vi_type & VI_TYPE_LEFT_MERGEABLE)
 247                 d_size = -((int)IH_SIZE), ih_size = 0;
 248
 249         tb->lnum[0] = 0;
 250         for (i = 0; i < vn->vn_nr_item;
 251              i++, ih_size = IH_SIZE, d_size = 0, vi++) {
 252                 d_size += vi->vi_item_len;
 253                 if (cur_free >= d_size) {
 254                         /* the item can be shifted entirely */
 255                         cur_free -= d_size;
 256                         tb->lnum[0]++;
 257                         continue;
 258                 }
 259
 260                 /* the item cannot be shifted entirely, try to split it */
 261                 /* check whether L[0] can hold ih and at least one byte of the item body */
 262                 if (cur_free <= ih_size) {
 263                         /* cannot shift even a part of the current item */
 264                         tb->lbytes = -1;
 265                         return;
 266                 }
 267                 cur_free -= ih_size;
 268
 269                 tb->lbytes = op_check_left(vi, cur_free, 0, 0);
 270                 if (tb->lbytes != -1)
 271                         /* count partially shifted item */
 272                         tb->lnum[0]++;
 273
 274                 break;
 275         }
 276
 277         return;
 278 }
 279
 280 /* using virtual node check, how many items can be shifted to right
 281    neighbor */
 282 static void check_right(struct tree_balance *tb, int h, int cur_free)
 283 {
 284         int i;
 285         struct virtual_node *vn = tb->tb_vn;
 286         struct virtual_item *vi;
 287         int d_size, ih_size;
 288
 289         RFALSE(cur_free < 0, "vs-8070: cur_free < 0");
 290
 291         /* internal level */
 292         if (h > 0) {
 293                 tb->rnum[h] = cur_free / (DC_SIZE + KEY_SIZE);
 294                 return;
 295         }
 296
 297         /* leaf level */
 298
 299         if (!cur_free || !vn->vn_nr_item) {
 300                 /* no free space  */
 301                 tb->rnum[h] = 0;
 302                 tb->rbytes = -1;
 303                 return;
 304         }
 305
 306         RFALSE(!PATH_H_PPARENT(tb->tb_path, 0),
 307                "vs-8075: parent does not exist or invalid");
 308
 309         vi = vn->vn_vi + vn->vn_nr_item - 1;
 310         if ((unsigned int)cur_free >=
 311             (vn->vn_size -
 312              ((vi->vi_type & VI_TYPE_RIGHT_MERGEABLE) ? IH_SIZE : 0))) {
 313                 /* all contents of S[0] fits into R[0] */
 314
 315                 RFALSE(vn->vn_mode == M_INSERT || vn->vn_mode == M_PASTE,
 316                        "vs-8080: invalid mode or balance condition failed");
 317
 318                 tb->rnum[h] = vn->vn_nr_item;
 319                 tb->rbytes = -1;
 320                 return;
 321         }
 322
 323         d_size = 0, ih_size = IH_SIZE;
 324
 325         /* last item may be merge with first item in right neighbor */
 326         if (vi->vi_type & VI_TYPE_RIGHT_MERGEABLE)
 327                 d_size = -(int)IH_SIZE, ih_size = 0;
 328
 329         tb->rnum[0] = 0;
 330         for (i = vn->vn_nr_item - 1; i >= 0;
 331              i--, d_size = 0, ih_size = IH_SIZE, vi--) {
 332                 d_size += vi->vi_item_len;
 333                 if (cur_free >= d_size) {
 334                         /* the item can be shifted entirely */
 335                         cur_free -= d_size;
 336                         tb->rnum[0]++;
 337                         continue;
 338                 }
 339
 340                 /* check whether R[0] can hold ih and at least one byte of the item body */
 341                 if (cur_free <= ih_size) {      /* cannot shift even a part of the current item */
 342                         tb->rbytes = -1;
 343                         return;
 344                 }
 345
 346                 /* R[0] can hold the header of the item and at least one byte of its body */
 347                 cur_free -= ih_size;    /* cur_free is still > 0 */
 348
 349                 tb->rbytes = op_check_right(vi, cur_free);
 350                 if (tb->rbytes != -1)
 351                         /* count partially shifted item */
 352                         tb->rnum[0]++;
 353
 354                 break;
 355         }
 356
 357         return;
 358 }
 359
 360 /*
 361  * from - number of items, which are shifted to left neighbor entirely
 362  * to - number of item, which are shifted to right neighbor entirely
 363  * from_bytes - number of bytes of boundary item (or directory entries) which are shifted to left neighbor
 364  * to_bytes - number of bytes of boundary item (or directory entries) which are shifted to right neighbor */
 365 static int get_num_ver(int mode, struct tree_balance *tb, int h,
 366                        int from, int from_bytes,
 367                        int to, int to_bytes, short *snum012, int flow)
 368 {
 369         int i;
 370         int cur_free;
 371         //    int bytes;
 372         int units;
 373         struct virtual_node *vn = tb->tb_vn;
 374         //    struct virtual_item * vi;
 375
 376         int total_node_size, max_node_size, current_item_size;
 377         int needed_nodes;
 378         int start_item,         /* position of item we start filling node from */
 379          end_item,              /* position of item we finish filling node by */
 380          start_bytes,           /* number of first bytes (entries for directory) of start_item-th item
 381                                    we do not include into node that is being filled */
 382          end_bytes;             /* number of last bytes (entries for directory) of end_item-th item
 383                                    we do node include into node that is being filled */
 384         int split_item_positions[2];    /* these are positions in virtual item of
 385                                            items, that are split between S[0] and
 386                                            S1new and S1new and S2new */
 387
 388         split_item_positions[0] = -1;
 389         split_item_positions[1] = -1;
 390
 391         /* We only create additional nodes if we are in insert or paste mode
 392            or we are in replace mode at the internal level. If h is 0 and
 393            the mode is M_REPLACE then in fix_nodes we change the mode to
 394            paste or insert before we get here in the code.  */
 395         RFALSE(tb->insert_size[h] < 0 || (mode != M_INSERT && mode != M_PASTE),
 396                "vs-8100: insert_size < 0 in overflow");
 397
 398         max_node_size = MAX_CHILD_SIZE(PATH_H_PBUFFER(tb->tb_path, h));
 399
 400         /* snum012 [0-2] - number of items, that lay
 401            to S[0], first new node and second new node */
 402         snum012[3] = -1;        /* s1bytes */
 403         snum012[4] = -1;        /* s2bytes */
 404
 405         /* internal level */
 406         if (h > 0) {
 407                 i = ((to - from) * (KEY_SIZE + DC_SIZE) + DC_SIZE);
 408                 if (i == max_node_size)
 409                         return 1;
 410                 return (i / max_node_size + 1);
 411         }
 412
 413         /* leaf level */
 414         needed_nodes = 1;
 415         total_node_size = 0;
 416         cur_free = max_node_size;
 417
 418         // start from 'from'-th item
 419         start_item = from;
 420         // skip its first 'start_bytes' units
 421         start_bytes = ((from_bytes != -1) ? from_bytes : 0);
 422
 423         // last included item is the 'end_item'-th one
 424         end_item = vn->vn_nr_item - to - 1;
 425         // do not count last 'end_bytes' units of 'end_item'-th item
 426         end_bytes = (to_bytes != -1) ? to_bytes : 0;
 427
 428         /* go through all item beginning from the start_item-th item and ending by
 429            the end_item-th item. Do not count first 'start_bytes' units of
 430            'start_item'-th item and last 'end_bytes' of 'end_item'-th item */
 431
 432         for (i = start_item; i <= end_item; i++) {
 433                 struct virtual_item *vi = vn->vn_vi + i;
 434                 int skip_from_end = ((i == end_item) ? end_bytes : 0);
 435
 436                 RFALSE(needed_nodes > 3, "vs-8105: too many nodes are needed");
 437
 438                 /* get size of current item */
 439                 current_item_size = vi->vi_item_len;
 440
 441                 /* do not take in calculation head part (from_bytes) of from-th item */
 442                 current_item_size -=
 443                     op_part_size(vi, 0 /*from start */ , start_bytes);
 444
 445                 /* do not take in calculation tail part of last item */
 446                 current_item_size -=
 447                     op_part_size(vi, 1 /*from end */ , skip_from_end);
 448
 449                 /* if item fits into current node entierly */
 450                 if (total_node_size + current_item_size <= max_node_size) {
 451                         snum012[needed_nodes - 1]++;
 452                         total_node_size += current_item_size;
 453                         start_bytes = 0;
 454                         continue;
 455                 }
 456
 457                 if (current_item_size > max_node_size) {
 458                         /* virtual item length is longer, than max size of item in
 459                            a node. It is impossible for direct item */
 460                         RFALSE(is_direct_le_ih(vi->vi_ih),
 461                                "vs-8110: "
 462                                "direct item length is %d. It can not be longer than %d",
 463                                current_item_size, max_node_size);
 464                         /* we will try to split it */
 465                         flow = 1;
 466                 }
 467
 468                 if (!flow) {
 469                         /* as we do not split items, take new node and continue */
 470                         needed_nodes++;
 471                         i--;
 472                         total_node_size = 0;
 473                         continue;
 474                 }
 475                 // calculate number of item units which fit into node being
 476                 // filled
 477                 {
 478                         int free_space;
 479
 480                         free_space = max_node_size - total_node_size - IH_SIZE;
 481                         units =
 482                             op_check_left(vi, free_space, start_bytes,
 483                                           skip_from_end);
 484                         if (units == -1) {
 485                                 /* nothing fits into current node, take new node and continue */
 486                                 needed_nodes++, i--, total_node_size = 0;
 487                                 continue;
 488                         }
 489                 }
 490
 491                 /* something fits into the current node */
 492                 //if (snum012[3] != -1 || needed_nodes != 1)
 493                 //  reiserfs_panic (tb->tb_sb, "vs-8115: get_num_ver: too many nodes required");
 494                 //snum012[needed_nodes - 1 + 3] = op_unit_num (vi) - start_bytes - units;
 495                 start_bytes += units;
 496                 snum012[needed_nodes - 1 + 3] = units;
 497
 498                 if (needed_nodes > 2)
 499                         reiserfs_warning(tb->tb_sb, "vs-8111",
 500                                          "split_item_position is out of range");
 501                 snum012[needed_nodes - 1]++;
 502                 split_item_positions[needed_nodes - 1] = i;
 503                 needed_nodes++;
 504                 /* continue from the same item with start_bytes != -1 */
 505                 start_item = i;
 506                 i--;
 507                 total_node_size = 0;
 508         }
 509
 510         // sum012[4] (if it is not -1) contains number of units of which
 511         // are to be in S1new, snum012[3] - to be in S0. They are supposed
 512         // to be S1bytes and S2bytes correspondingly, so recalculate
 513         if (snum012[4] > 0) {
 514                 int split_item_num;
 515                 int bytes_to_r, bytes_to_l;
 516                 int bytes_to_S1new;
 517
 518                 split_item_num = split_item_positions[1];
 519                 bytes_to_l =
 520                     ((from == split_item_num
 521                       && from_bytes != -1) ? from_bytes : 0);
 522                 bytes_to_r =
 523                     ((end_item == split_item_num
 524                       && end_bytes != -1) ? end_bytes : 0);
 525                 bytes_to_S1new =
 526                     ((split_item_positions[0] ==
 527                       split_item_positions[1]) ? snum012[3] : 0);
 528
 529                 // s2bytes
 530                 snum012[4] =
 531                     op_unit_num(&vn->vn_vi[split_item_num]) - snum012[4] -
 532                     bytes_to_r - bytes_to_l - bytes_to_S1new;
 533
 534                 if (vn->vn_vi[split_item_num].vi_index != TYPE_DIRENTRY &&
 535                     vn->vn_vi[split_item_num].vi_index != TYPE_INDIRECT)
 536                         reiserfs_warning(tb->tb_sb, "vs-8115",
 537                                          "not directory or indirect item");
 538         }
 539
 540         /* now we know S2bytes, calculate S1bytes */
 541         if (snum012[3] > 0) {
 542                 int split_item_num;
 543                 int bytes_to_r, bytes_to_l;
 544                 int bytes_to_S2new;
 545
 546                 split_item_num = split_item_positions[0];
 547                 bytes_to_l =
 548                     ((from == split_item_num
 549                       && from_bytes != -1) ? from_bytes : 0);
 550                 bytes_to_r =
 551                     ((end_item == split_item_num
 552                       && end_bytes != -1) ? end_bytes : 0);
 553                 bytes_to_S2new =
 554                     ((split_item_positions[0] == split_item_positions[1]
 555                       && snum012[4] != -1) ? snum012[4] : 0);
 556
 557                 // s1bytes
 558                 snum012[3] =
 559                     op_unit_num(&vn->vn_vi[split_item_num]) - snum012[3] -
 560                     bytes_to_r - bytes_to_l - bytes_to_S2new;
 561         }
 562
 563         return needed_nodes;
 564 }
 565
 566 #ifdef CONFIG_REISERFS_CHECK
 567 extern struct tree_balance *cur_tb;
 568 #endif
 569
 570 /* Set parameters for balancing.
 571  * Performs write of results of analysis of balancing into structure tb,
 572  * where it will later be used by the functions that actually do the balancing.
 573  * Parameters:
 574  *      tb      tree_balance structure;
 575  *      h       current level of the node;
 576  *      lnum    number of items from S[h] that must be shifted to L[h];
 577  *      rnum    number of items from S[h] that must be shifted to R[h];
 578  *      blk_num number of blocks that S[h] will be splitted into;
 579  *      s012    number of items that fall into splitted nodes.
 580  *      lbytes  number of bytes which flow to the left neighbor from the item that is not
 581  *              not shifted entirely
 582  *      rbytes  number of bytes which flow to the right neighbor from the item that is not
 583  *              not shifted entirely
 584  *      s1bytes number of bytes which flow to the first  new node when S[0] splits (this number is contained in s012 array)
 585  */
 586
 587 static void set_parameters(struct tree_balance *tb, int h, int lnum,
 588                            int rnum, int blk_num, short *s012, int lb, int rb)
 589 {
 590
 591         tb->lnum[h] = lnum;
 592         tb->rnum[h] = rnum;
 593         tb->blknum[h] = blk_num;
 594
 595         if (h == 0) {           /* only for leaf level */
 596                 if (s012 != NULL) {
 597                         tb->s0num = *s012++,
 598                             tb->s1num = *s012++, tb->s2num = *s012++;
 599                         tb->s1bytes = *s012++;
 600                         tb->s2bytes = *s012;
 601                 }
 602                 tb->lbytes = lb;
 603                 tb->rbytes = rb;
 604         }
 605         PROC_INFO_ADD(tb->tb_sb, lnum[h], lnum);
 606         PROC_INFO_ADD(tb->tb_sb, rnum[h], rnum);
 607
 608         PROC_INFO_ADD(tb->tb_sb, lbytes[h], lb);
 609         PROC_INFO_ADD(tb->tb_sb, rbytes[h], rb);
 610 }
 611
 612 /* check, does node disappear if we shift tb->lnum[0] items to left
 613    neighbor and tb->rnum[0] to the right one. */
 614 static int is_leaf_removable(struct tree_balance *tb)
 615 {
 616         struct virtual_node *vn = tb->tb_vn;
 617         int to_left, to_right;
 618         int size;
 619         int remain_items;
 620
 621         /* number of items, that will be shifted to left (right) neighbor
 622            entirely */
 623         to_left = tb->lnum[0] - ((tb->lbytes != -1) ? 1 : 0);
 624         to_right = tb->rnum[0] - ((tb->rbytes != -1) ? 1 : 0);
 625         remain_items = vn->vn_nr_item;
 626
 627         /* how many items remain in S[0] after shiftings to neighbors */
 628         remain_items -= (to_left + to_right);
 629
 630         if (remain_items < 1) {
 631                 /* all content of node can be shifted to neighbors */
 632                 set_parameters(tb, 0, to_left, vn->vn_nr_item - to_left, 0,
 633                                NULL, -1, -1);
 634                 return 1;
 635         }
 636
 637         if (remain_items > 1 || tb->lbytes == -1 || tb->rbytes == -1)
 638                 /* S[0] is not removable */
 639                 return 0;
 640
 641         /* check, whether we can divide 1 remaining item between neighbors */
 642
 643         /* get size of remaining item (in item units) */
 644         size = op_unit_num(&(vn->vn_vi[to_left]));
 645
 646         if (tb->lbytes + tb->rbytes >= size) {
 647                 set_parameters(tb, 0, to_left + 1, to_right + 1, 0, NULL,
 648                                tb->lbytes, -1);
 649                 return 1;
 650         }
 651
 652         return 0;
 653 }
 654
 655 /* check whether L, S, R can be joined in one node */
 656 static int are_leaves_removable(struct tree_balance *tb, int lfree, int rfree)
 657 {
 658         struct virtual_node *vn = tb->tb_vn;
 659         int ih_size;
 660         struct buffer_head *S0;
 661
 662         S0 = PATH_H_PBUFFER(tb->tb_path, 0);
 663
 664         ih_size = 0;
 665         if (vn->vn_nr_item) {
 666                 if (vn->vn_vi[0].vi_type & VI_TYPE_LEFT_MERGEABLE)
 667                         ih_size += IH_SIZE;
 668
 669                 if (vn->vn_vi[vn->vn_nr_item - 1].
 670                     vi_type & VI_TYPE_RIGHT_MERGEABLE)
 671                         ih_size += IH_SIZE;
 672         } else {
 673                 /* there was only one item and it will be deleted */
 674                 struct item_head *ih;
 675
 676                 RFALSE(B_NR_ITEMS(S0) != 1,
 677                        "vs-8125: item number must be 1: it is %d",
 678                        B_NR_ITEMS(S0));
 679
 680                 ih = B_N_PITEM_HEAD(S0, 0);
 681                 if (tb->CFR[0]
 682                     && !comp_short_le_keys(&(ih->ih_key),
 683                                            B_N_PDELIM_KEY(tb->CFR[0],
 684                                                           tb->rkey[0])))
 685                         if (is_direntry_le_ih(ih)) {
 686                                 /* Directory must be in correct state here: that is
 687                                    somewhere at the left side should exist first directory
 688                                    item. But the item being deleted can not be that first
 689                                    one because its right neighbor is item of the same
 690                                    directory. (But first item always gets deleted in last
 691                                    turn). So, neighbors of deleted item can be merged, so
 692                                    we can save ih_size */
 693                                 ih_size = IH_SIZE;
 694
 695                                 /* we might check that left neighbor exists and is of the
 696                                    same directory */
 697                                 RFALSE(le_ih_k_offset(ih) == DOT_OFFSET,
 698                                        "vs-8130: first directory item can not be removed until directory is not empty");
 699                         }
 700
 701         }
 702
 703         if (MAX_CHILD_SIZE(S0) + vn->vn_size <= rfree + lfree + ih_size) {
 704                 set_parameters(tb, 0, -1, -1, -1, NULL, -1, -1);
 705                 PROC_INFO_INC(tb->tb_sb, leaves_removable);
 706                 return 1;
 707         }
 708         return 0;
 709
 710 }
 711
 712 /* when we do not split item, lnum and rnum are numbers of entire items */
 713 #define SET_PAR_SHIFT_LEFT \
 714 if (h)\
 715 {\
 716    int to_l;\
 717    \
 718    to_l = (MAX_NR_KEY(Sh)+1 - lpar + vn->vn_nr_item + 1) / 2 -\
 719               (MAX_NR_KEY(Sh) + 1 - lpar);\
 720               \
 721               set_parameters (tb, h, to_l, 0, lnver, NULL, -1, -1);\
 722 }\
 723 else \
 724 {\
 725    if (lset==LEFT_SHIFT_FLOW)\
 726      set_parameters (tb, h, lpar, 0, lnver, snum012+lset,\
 727                      tb->lbytes, -1);\
 728    else\
 729      set_parameters (tb, h, lpar - (tb->lbytes!=-1), 0, lnver, snum012+lset,\
 730                      -1, -1);\
 731 }
 732
 733 #define SET_PAR_SHIFT_RIGHT \
 734 if (h)\
 735 {\
 736    int to_r;\
 737    \
 738    to_r = (MAX_NR_KEY(Sh)+1 - rpar + vn->vn_nr_item + 1) / 2 - (MAX_NR_KEY(Sh) + 1 - rpar);\
 739    \
 740    set_parameters (tb, h, 0, to_r, rnver, NULL, -1, -1);\
 741 }\
 742 else \
 743 {\
 744    if (rset==RIGHT_SHIFT_FLOW)\
 745      set_parameters (tb, h, 0, rpar, rnver, snum012+rset,\
 746                   -1, tb->rbytes);\
 747    else\
 748      set_parameters (tb, h, 0, rpar - (tb->rbytes!=-1), rnver, snum012+rset,\
 749                   -1, -1);\
 750 }
 751
 752 static void free_buffers_in_tb(struct tree_balance *tb)
 753 {
 754         int n_counter;
 755
 756         pathrelse(tb->tb_path);
 757
 758         for (n_counter = 0; n_counter < MAX_HEIGHT; n_counter++) {
 759                 brelse(tb->L[n_counter]);
 760                 brelse(tb->R[n_counter]);
 761                 brelse(tb->FL[n_counter]);
 762                 brelse(tb->FR[n_counter]);
 763                 brelse(tb->CFL[n_counter]);
 764                 brelse(tb->CFR[n_counter]);
 765
 766                 tb->L[n_counter] = NULL;
 767                 tb->R[n_counter] = NULL;
 768                 tb->FL[n_counter] = NULL;
 769                 tb->FR[n_counter] = NULL;
 770                 tb->CFL[n_counter] = NULL;
 771                 tb->CFR[n_counter] = NULL;
 772         }
 773 }
 774
 775 /* Get new buffers for storing new nodes that are created while balancing.
 776  * Returns:     SCHEDULE_OCCURRED - schedule occurred while the function worked;
 777  *              CARRY_ON - schedule didn't occur while the function worked;
 778  *              NO_DISK_SPACE - no disk space.
 779  */
 780 /* The function is NOT SCHEDULE-SAFE! */
 781 static int get_empty_nodes(struct tree_balance *tb, int n_h)
 782 {
 783         struct buffer_head *p_s_new_bh,
 784             *p_s_Sh = PATH_H_PBUFFER(tb->tb_path, n_h);
 785         b_blocknr_t *p_n_blocknr, a_n_blocknrs[MAX_AMOUNT_NEEDED] = { 0, };
 786         int n_counter, n_number_of_freeblk, n_amount_needed,    /* number of needed empty blocks */
 787          n_retval = CARRY_ON;
 788         struct super_block *sb = tb->tb_sb;
 789
 790         /* number_of_freeblk is the number of empty blocks which have been
 791            acquired for use by the balancing algorithm minus the number of
 792            empty blocks used in the previous levels of the analysis,
 793            number_of_freeblk = tb->cur_blknum can be non-zero if a schedule occurs
 794            after empty blocks are acquired, and the balancing analysis is
 795            then restarted, amount_needed is the number needed by this level
 796            (n_h) of the balancing analysis.
 797
 798            Note that for systems with many processes writing, it would be
 799            more layout optimal to calculate the total number needed by all
 800            levels and then to run reiserfs_new_blocks to get all of them at once.  */
 801
 802         /* Initiate number_of_freeblk to the amount acquired prior to the restart of
 803            the analysis or 0 if not restarted, then subtract the amount needed
 804            by all of the levels of the tree below n_h. */
 805         /* blknum includes S[n_h], so we subtract 1 in this calculation */
 806         for (n_counter = 0, n_number_of_freeblk = tb->cur_blknum;
 807              n_counter < n_h; n_counter++)
 808                 n_number_of_freeblk -=
 809                     (tb->blknum[n_counter]) ? (tb->blknum[n_counter] -
 810                                                    1) : 0;
 811
 812         /* Allocate missing empty blocks. */
 813         /* if p_s_Sh == 0  then we are getting a new root */
 814         n_amount_needed = (p_s_Sh) ? (tb->blknum[n_h] - 1) : 1;
 815         /*  Amount_needed = the amount that we need more than the amount that we have. */
 816         if (n_amount_needed > n_number_of_freeblk)
 817                 n_amount_needed -= n_number_of_freeblk;
 818         else                    /* If we have enough already then there is nothing to do. */
 819                 return CARRY_ON;
 820
 821         /* No need to check quota - is not allocated for blocks used for formatted nodes */
 822         if (reiserfs_new_form_blocknrs(tb, a_n_blocknrs,
 823                                        n_amount_needed) == NO_DISK_SPACE)
 824                 return NO_DISK_SPACE;
 825
 826         /* for each blocknumber we just got, get a buffer and stick it on FEB */
 827         for (p_n_blocknr = a_n_blocknrs, n_counter = 0;
 828              n_counter < n_amount_needed; p_n_blocknr++, n_counter++) {
 829
 830                 RFALSE(!*p_n_blocknr,
 831                        "PAP-8135: reiserfs_new_blocknrs failed when got new blocks");
 832
 833                 p_s_new_bh = sb_getblk(sb, *p_n_blocknr);
 834                 RFALSE(buffer_dirty(p_s_new_bh) ||
 835                        buffer_journaled(p_s_new_bh) ||
 836                        buffer_journal_dirty(p_s_new_bh),
 837                        "PAP-8140: journlaled or dirty buffer %b for the new block",
 838                        p_s_new_bh);
 839
 840                 /* Put empty buffers into the array. */
 841                 RFALSE(tb->FEB[tb->cur_blknum],
 842                        "PAP-8141: busy slot for new buffer");
 843
 844                 set_buffer_journal_new(p_s_new_bh);
 845                 tb->FEB[tb->cur_blknum++] = p_s_new_bh;
 846         }
 847
 848         if (n_retval == CARRY_ON && FILESYSTEM_CHANGED_TB(tb))
 849                 n_retval = REPEAT_SEARCH;
 850
 851         return n_retval;
 852 }
 853
 854 /* Get free space of the left neighbor, which is stored in the parent
 855  * node of the left neighbor.  */
 856 static int get_lfree(struct tree_balance *tb, int h)
 857 {
 858         struct buffer_head *l, *f;
 859         int order;
 860
 861         if ((f = PATH_H_PPARENT(tb->tb_path, h)) == NULL ||
 862             (l = tb->FL[h]) == NULL)
 863                 return 0;
 864
 865         if (f == l)
 866                 order = PATH_H_B_ITEM_ORDER(tb->tb_path, h) - 1;
 867         else {
 868                 order = B_NR_ITEMS(l);
 869                 f = l;
 870         }
 871
 872         return (MAX_CHILD_SIZE(f) - dc_size(B_N_CHILD(f, order)));
 873 }
 874
 875 /* Get free space of the right neighbor,
 876  * which is stored in the parent node of the right neighbor.
 877  */
 878 static int get_rfree(struct tree_balance *tb, int h)
 879 {
 880         struct buffer_head *r, *f;
 881         int order;
 882
 883         if ((f = PATH_H_PPARENT(tb->tb_path, h)) == NULL ||
 884             (r = tb->FR[h]) == NULL)
 885                 return 0;
 886
 887         if (f == r)
 888                 order = PATH_H_B_ITEM_ORDER(tb->tb_path, h) + 1;
 889         else {
 890                 order = 0;
 891                 f = r;
 892         }
 893
 894         return (MAX_CHILD_SIZE(f) - dc_size(B_N_CHILD(f, order)));
 895
 896 }
 897
 898 /* Check whether left neighbor is in memory. */
 899 static int is_left_neighbor_in_cache(struct tree_balance *tb, int n_h)
 900 {
 901         struct buffer_head *p_s_father, *left;
 902         struct super_block *sb = tb->tb_sb;
 903         b_blocknr_t n_left_neighbor_blocknr;
 904         int n_left_neighbor_position;
 905
 906         /* Father of the left neighbor does not exist. */
 907         if (!tb->FL[n_h])
 908                 return 0;
 909
 910         /* Calculate father of the node to be balanced. */
 911         p_s_father = PATH_H_PBUFFER(tb->tb_path, n_h + 1);
 912
 913         RFALSE(!p_s_father ||
 914                !B_IS_IN_TREE(p_s_father) ||
 915                !B_IS_IN_TREE(tb->FL[n_h]) ||
 916                !buffer_uptodate(p_s_father) ||
 917                !buffer_uptodate(tb->FL[n_h]),
 918                "vs-8165: F[h] (%b) or FL[h] (%b) is invalid",
 919                p_s_father, tb->FL[n_h]);
 920
 921         /* Get position of the pointer to the left neighbor into the left father. */
 922         n_left_neighbor_position = (p_s_father == tb->FL[n_h]) ?
 923             tb->lkey[n_h] : B_NR_ITEMS(tb->FL[n_h]);
 924         /* Get left neighbor block number. */
 925         n_left_neighbor_blocknr =
 926             B_N_CHILD_NUM(tb->FL[n_h], n_left_neighbor_position);
 927         /* Look for the left neighbor in the cache. */
 928         if ((left = sb_find_get_block(sb, n_left_neighbor_blocknr))) {
 929
 930                 RFALSE(buffer_uptodate(left) && !B_IS_IN_TREE(left),
 931                        "vs-8170: left neighbor (%b %z) is not in the tree",
 932                        left, left);
 933                 put_bh(left);
 934                 return 1;
 935         }
 936
 937         return 0;
 938 }
 939
 940 #define LEFT_PARENTS  'l'
 941 #define RIGHT_PARENTS 'r'
 942
 943 static void decrement_key(struct cpu_key *p_s_key)
 944 {
 945         // call item specific function for this key
 946         item_ops[cpu_key_k_type(p_s_key)]->decrement_key(p_s_key);
 947 }
 948
 949 /* Calculate far left/right parent of the left/right neighbor of the current node, that
 950  * is calculate the left/right (FL[h]/FR[h]) neighbor of the parent F[h].
 951  * Calculate left/right common parent of the current node and L[h]/R[h].
 952  * Calculate left/right delimiting key position.
 953  * Returns:     PATH_INCORRECT   - path in the tree is not correct;
 954                 SCHEDULE_OCCURRED - schedule occurred while the function worked;
 955  *              CARRY_ON         - schedule didn't occur while the function worked;
 956  */
 957 static int get_far_parent(struct tree_balance *tb,
 958                           int n_h,
 959                           struct buffer_head **pp_s_father,
 960                           struct buffer_head **pp_s_com_father, char c_lr_par)
 961 {
 962         struct buffer_head *p_s_parent;
 963         INITIALIZE_PATH(s_path_to_neighbor_father);
 964         struct treepath *p_s_path = tb->tb_path;
 965         struct cpu_key s_lr_father_key;
 966         int n_counter,
 967             n_position = INT_MAX,
 968             n_first_last_position = 0,
 969             n_path_offset = PATH_H_PATH_OFFSET(p_s_path, n_h);
 970
 971         /* Starting from F[n_h] go upwards in the tree, and look for the common
 972            ancestor of F[n_h], and its neighbor l/r, that should be obtained. */
 973
 974         n_counter = n_path_offset;
 975
 976         RFALSE(n_counter < FIRST_PATH_ELEMENT_OFFSET,
 977                "PAP-8180: invalid path length");
 978
 979         for (; n_counter > FIRST_PATH_ELEMENT_OFFSET; n_counter--) {
 980                 /* Check whether parent of the current buffer in the path is really parent in the tree. */
 981                 if (!B_IS_IN_TREE
 982                     (p_s_parent = PATH_OFFSET_PBUFFER(p_s_path, n_counter - 1)))
 983                         return REPEAT_SEARCH;
 984                 /* Check whether position in the parent is correct. */
 985                 if ((n_position =
 986                      PATH_OFFSET_POSITION(p_s_path,
 987                                           n_counter - 1)) >
 988                     B_NR_ITEMS(p_s_parent))
 989                         return REPEAT_SEARCH;
 990                 /* Check whether parent at the path really points to the child. */
 991                 if (B_N_CHILD_NUM(p_s_parent, n_position) !=
 992                     PATH_OFFSET_PBUFFER(p_s_path, n_counter)->b_blocknr)
 993                         return REPEAT_SEARCH;
 994                 /* Return delimiting key if position in the parent is not equal to first/last one. */
 995                 if (c_lr_par == RIGHT_PARENTS)
 996                         n_first_last_position = B_NR_ITEMS(p_s_parent);
 997                 if (n_position != n_first_last_position) {
 998                         *pp_s_com_father = p_s_parent;
 999                         get_bh(*pp_s_com_father);
1000                         /*(*pp_s_com_father = p_s_parent)->b_count++; */
1001                         break;
1002                 }
1003         }
1004
1005         /* if we are in the root of the tree, then there is no common father */
1006         if (n_counter == FIRST_PATH_ELEMENT_OFFSET) {
1007                 /* Check whether first buffer in the path is the root of the tree. */
1008                 if (PATH_OFFSET_PBUFFER
1009                     (tb->tb_path,
1010                      FIRST_PATH_ELEMENT_OFFSET)->b_blocknr ==
1011                     SB_ROOT_BLOCK(tb->tb_sb)) {
1012                         *pp_s_father = *pp_s_com_father = NULL;
1013                         return CARRY_ON;
1014                 }
1015                 return REPEAT_SEARCH;
1016         }
1017
1018         RFALSE(B_LEVEL(*pp_s_com_father) <= DISK_LEAF_NODE_LEVEL,
1019                "PAP-8185: (%b %z) level too small",
1020                *pp_s_com_father, *pp_s_com_father);
1021
1022         /* Check whether the common parent is locked. */
1023
1024         if (buffer_locked(*pp_s_com_father)) {
1025                 __wait_on_buffer(*pp_s_com_father);
1026                 if (FILESYSTEM_CHANGED_TB(tb)) {
1027                         brelse(*pp_s_com_father);
1028                         return REPEAT_SEARCH;
1029                 }
1030         }
1031
1032         /* So, we got common parent of the current node and its left/right neighbor.
1033            Now we are geting the parent of the left/right neighbor. */
1034
1035         /* Form key to get parent of the left/right neighbor. */
1036         le_key2cpu_key(&s_lr_father_key,
1037                        B_N_PDELIM_KEY(*pp_s_com_father,
1038                                       (c_lr_par ==
1039                                        LEFT_PARENTS) ? (tb->lkey[n_h - 1] =
1040                                                         n_position -
1041                                                         1) : (tb->rkey[n_h -
1042                                                                            1] =
1043                                                               n_position)));
1044
1045         if (c_lr_par == LEFT_PARENTS)
1046                 decrement_key(&s_lr_father_key);
1047
1048         if (search_by_key
1049             (tb->tb_sb, &s_lr_father_key, &s_path_to_neighbor_father,
1050              n_h + 1) == IO_ERROR)
1051                 // path is released
1052                 return IO_ERROR;
1053
1054         if (FILESYSTEM_CHANGED_TB(tb)) {
1055                 pathrelse(&s_path_to_neighbor_father);
1056                 brelse(*pp_s_com_father);
1057                 return REPEAT_SEARCH;
1058         }
1059
1060         *pp_s_father = PATH_PLAST_BUFFER(&s_path_to_neighbor_father);
1061
1062         RFALSE(B_LEVEL(*pp_s_father) != n_h + 1,
1063                "PAP-8190: (%b %z) level too small", *pp_s_father, *pp_s_father);
1064         RFALSE(s_path_to_neighbor_father.path_length <
1065                FIRST_PATH_ELEMENT_OFFSET, "PAP-8192: path length is too small");
1066
1067         s_path_to_neighbor_father.path_length--;
1068         pathrelse(&s_path_to_neighbor_father);
1069         return CARRY_ON;
1070 }
1071
1072 /* Get parents of neighbors of node in the path(S[n_path_offset]) and common parents of
1073  * S[n_path_offset] and L[n_path_offset]/R[n_path_offset]: F[n_path_offset], FL[n_path_offset],
1074  * FR[n_path_offset], CFL[n_path_offset], CFR[n_path_offset].
1075  * Calculate numbers of left and right delimiting keys position: lkey[n_path_offset], rkey[n_path_offset].
1076  * Returns:     SCHEDULE_OCCURRED - schedule occurred while the function worked;
1077  *              CARRY_ON - schedule didn't occur while the function worked;
1078  */
1079 static int get_parents(struct tree_balance *tb, int n_h)
1080 {
1081         struct treepath *p_s_path = tb->tb_path;
1082         int n_position,
1083             n_ret_value,
1084             n_path_offset = PATH_H_PATH_OFFSET(tb->tb_path, n_h);
1085         struct buffer_head *p_s_curf, *p_s_curcf;
1086
1087         /* Current node is the root of the tree or will be root of the tree */
1088         if (n_path_offset <= FIRST_PATH_ELEMENT_OFFSET) {
1089                 /* The root can not have parents.
1090                    Release nodes which previously were obtained as parents of the current node neighbors. */
1091                 brelse(tb->FL[n_h]);
1092                 brelse(tb->CFL[n_h]);
1093                 brelse(tb->FR[n_h]);
1094                 brelse(tb->CFR[n_h]);
1095                 tb->FL[n_h] = NULL;
1096                 tb->CFL[n_h] = NULL;
1097                 tb->FR[n_h] = NULL;
1098                 tb->CFR[n_h] = NULL;
1099                 return CARRY_ON;
1100         }
1101
1102         /* Get parent FL[n_path_offset] of L[n_path_offset]. */
1103         if ((n_position = PATH_OFFSET_POSITION(p_s_path, n_path_offset - 1))) {
1104                 /* Current node is not the first child of its parent. */
1105                 /*(p_s_curf = p_s_curcf = PATH_OFFSET_PBUFFER(p_s_path, n_path_offset - 1))->b_count += 2; */
1106                 p_s_curf = p_s_curcf =
1107                     PATH_OFFSET_PBUFFER(p_s_path, n_path_offset - 1);
1108                 get_bh(p_s_curf);
1109                 get_bh(p_s_curf);
1110                 tb->lkey[n_h] = n_position - 1;
1111         } else {
1112                 /* Calculate current parent of L[n_path_offset], which is the left neighbor of the current node.
1113                    Calculate current common parent of L[n_path_offset] and the current node. Note that
1114                    CFL[n_path_offset] not equal FL[n_path_offset] and CFL[n_path_offset] not equal F[n_path_offset].
1115                    Calculate lkey[n_path_offset]. */
1116                 if ((n_ret_value = get_far_parent(tb, n_h + 1, &p_s_curf,
1117                                                   &p_s_curcf,
1118                                                   LEFT_PARENTS)) != CARRY_ON)
1119                         return n_ret_value;
1120         }
1121
1122         brelse(tb->FL[n_h]);
1123         tb->FL[n_h] = p_s_curf; /* New initialization of FL[n_h]. */
1124         brelse(tb->CFL[n_h]);
1125         tb->CFL[n_h] = p_s_curcf;       /* New initialization of CFL[n_h]. */
1126
1127         RFALSE((p_s_curf && !B_IS_IN_TREE(p_s_curf)) ||
1128                (p_s_curcf && !B_IS_IN_TREE(p_s_curcf)),
1129                "PAP-8195: FL (%b) or CFL (%b) is invalid", p_s_curf, p_s_curcf);
1130
1131 /* Get parent FR[n_h] of R[n_h]. */
1132
1133 /* Current node is the last child of F[n_h]. FR[n_h] != F[n_h]. */
1134         if (n_position == B_NR_ITEMS(PATH_H_PBUFFER(p_s_path, n_h + 1))) {
1135 /* Calculate current parent of R[n_h], which is the right neighbor of F[n_h].
1136    Calculate current common parent of R[n_h] and current node. Note that CFR[n_h]
1137    not equal FR[n_path_offset] and CFR[n_h] not equal F[n_h]. */
1138                 if ((n_ret_value =
1139                      get_far_parent(tb, n_h + 1, &p_s_curf, &p_s_curcf,
1140                                     RIGHT_PARENTS)) != CARRY_ON)
1141                         return n_ret_value;
1142         } else {
1143 /* Current node is not the last child of its parent F[n_h]. */
1144                 /*(p_s_curf = p_s_curcf = PATH_OFFSET_PBUFFER(p_s_path, n_path_offset - 1))->b_count += 2; */
1145                 p_s_curf = p_s_curcf =
1146                     PATH_OFFSET_PBUFFER(p_s_path, n_path_offset - 1);
1147                 get_bh(p_s_curf);
1148                 get_bh(p_s_curf);
1149                 tb->rkey[n_h] = n_position;
1150         }
1151
1152         brelse(tb->FR[n_h]);
1153         /* New initialization of FR[n_path_offset]. */
1154         tb->FR[n_h] = p_s_curf;
1155
1156         brelse(tb->CFR[n_h]);
1157         /* New initialization of CFR[n_path_offset]. */
1158         tb->CFR[n_h] = p_s_curcf;
1159
1160         RFALSE((p_s_curf && !B_IS_IN_TREE(p_s_curf)) ||
1161                (p_s_curcf && !B_IS_IN_TREE(p_s_curcf)),
1162                "PAP-8205: FR (%b) or CFR (%b) is invalid", p_s_curf, p_s_curcf);
1163
1164         return CARRY_ON;
1165 }
1166
1167 /* it is possible to remove node as result of shiftings to
1168    neighbors even when we insert or paste item. */
1169 static inline int can_node_be_removed(int mode, int lfree, int sfree, int rfree,
1170                                       struct tree_balance *tb, int h)
1171 {
1172         struct buffer_head *Sh = PATH_H_PBUFFER(tb->tb_path, h);
1173         int levbytes = tb->insert_size[h];
1174         struct item_head *ih;
1175         struct reiserfs_key *r_key = NULL;
1176
1177         ih = B_N_PITEM_HEAD(Sh, 0);
1178         if (tb->CFR[h])
1179                 r_key = B_N_PDELIM_KEY(tb->CFR[h], tb->rkey[h]);
1180
1181         if (lfree + rfree + sfree < MAX_CHILD_SIZE(Sh) + levbytes
1182             /* shifting may merge items which might save space */
1183             -
1184             ((!h
1185               && op_is_left_mergeable(&(ih->ih_key), Sh->b_size)) ? IH_SIZE : 0)
1186             -
1187             ((!h && r_key
1188               && op_is_left_mergeable(r_key, Sh->b_size)) ? IH_SIZE : 0)
1189             + ((h) ? KEY_SIZE : 0)) {
1190                 /* node can not be removed */
1191                 if (sfree >= levbytes) {        /* new item fits into node S[h] without any shifting */
1192                         if (!h)
1193                                 tb->s0num =
1194                                     B_NR_ITEMS(Sh) +
1195                                     ((mode == M_INSERT) ? 1 : 0);
1196                         set_parameters(tb, h, 0, 0, 1, NULL, -1, -1);
1197                         return NO_BALANCING_NEEDED;
1198                 }
1199         }
1200         PROC_INFO_INC(tb->tb_sb, can_node_be_removed[h]);
1201         return !NO_BALANCING_NEEDED;
1202 }
1203
1204 /* Check whether current node S[h] is balanced when increasing its size by
1205  * Inserting or Pasting.
1206  * Calculate parameters for balancing for current level h.
1207  * Parameters:
1208  *      tb      tree_balance structure;
1209  *      h       current level of the node;
1210  *      inum    item number in S[h];
1211  *      mode    i - insert, p - paste;
1212  * Returns:     1 - schedule occurred;
1213  *              0 - balancing for higher levels needed;
1214  *             -1 - no balancing for higher levels needed;
1215  *             -2 - no disk space.
1216  */
1217 /* ip means Inserting or Pasting */
1218 static int ip_check_balance(struct tree_balance *tb, int h)
1219 {
1220         struct virtual_node *vn = tb->tb_vn;
1221         int levbytes,           /* Number of bytes that must be inserted into (value
1222                                    is negative if bytes are deleted) buffer which
1223                                    contains node being balanced.  The mnemonic is
1224                                    that the attempted change in node space used level
1225                                    is levbytes bytes. */
1226          n_ret_value;
1227
1228         int lfree, sfree, rfree /* free space in L, S and R */ ;
1229
1230         /* nver is short for number of vertixes, and lnver is the number if
1231            we shift to the left, rnver is the number if we shift to the
1232            right, and lrnver is the number if we shift in both directions.
1233            The goal is to minimize first the number of vertixes, and second,
1234            the number of vertixes whose contents are changed by shifting,
1235            and third the number of uncached vertixes whose contents are
1236            changed by shifting and must be read from disk.  */
1237         int nver, lnver, rnver, lrnver;
1238
1239         /* used at leaf level only, S0 = S[0] is the node being balanced,
1240            sInum [ I = 0,1,2 ] is the number of items that will
1241            remain in node SI after balancing.  S1 and S2 are new
1242            nodes that might be created. */
1243
1244         /* we perform 8 calls to get_num_ver().  For each call we calculate five parameters.
1245            where 4th parameter is s1bytes and 5th - s2bytes
1246          */
1247         short snum012[40] = { 0, };     /* s0num, s1num, s2num for 8 cases
1248                                            0,1 - do not shift and do not shift but bottle
1249                                            2 - shift only whole item to left
1250                                            3 - shift to left and bottle as much as possible
1251                                            4,5 - shift to right (whole items and as much as possible
1252                                            6,7 - shift to both directions (whole items and as much as possible)
1253                                          */
1254
1255         /* Sh is the node whose balance is currently being checked */
1256         struct buffer_head *Sh;
1257
1258         Sh = PATH_H_PBUFFER(tb->tb_path, h);
1259         levbytes = tb->insert_size[h];
1260
1261         /* Calculate balance parameters for creating new root. */
1262         if (!Sh) {
1263                 if (!h)
1264                         reiserfs_panic(tb->tb_sb, "vs-8210",
1265                                        "S[0] can not be 0");
1266                 switch (n_ret_value = get_empty_nodes(tb, h)) {
1267                 case CARRY_ON:
1268                         set_parameters(tb, h, 0, 0, 1, NULL, -1, -1);
1269                         return NO_BALANCING_NEEDED;     /* no balancing for higher levels needed */
1270
1271                 case NO_DISK_SPACE:
1272                 case REPEAT_SEARCH:
1273                         return n_ret_value;
1274                 default:
1275                         reiserfs_panic(tb->tb_sb, "vs-8215", "incorrect "
1276                                        "return value of get_empty_nodes");
1277                 }
1278         }
1279
1280         if ((n_ret_value = get_parents(tb, h)) != CARRY_ON)     /* get parents of S[h] neighbors. */
1281                 return n_ret_value;
1282
1283         sfree = B_FREE_SPACE(Sh);
1284
1285         /* get free space of neighbors */
1286         rfree = get_rfree(tb, h);
1287         lfree = get_lfree(tb, h);
1288
1289         if (can_node_be_removed(vn->vn_mode, lfree, sfree, rfree, tb, h) ==
1290             NO_BALANCING_NEEDED)
1291                 /* and new item fits into node S[h] without any shifting */
1292                 return NO_BALANCING_NEEDED;
1293
1294         create_virtual_node(tb, h);
1295
1296         /*
1297            determine maximal number of items we can shift to the left neighbor (in tb structure)
1298            and the maximal number of bytes that can flow to the left neighbor
1299            from the left most liquid item that cannot be shifted from S[0] entirely (returned value)
1300          */
1301         check_left(tb, h, lfree);
1302
1303         /*
1304            determine maximal number of items we can shift to the right neighbor (in tb structure)
1305            and the maximal number of bytes that can flow to the right neighbor
1306            from the right most liquid item that cannot be shifted from S[0] entirely (returned value)
1307          */
1308         check_right(tb, h, rfree);
1309
1310         /* all contents of internal node S[h] can be moved into its
1311            neighbors, S[h] will be removed after balancing */
1312         if (h && (tb->rnum[h] + tb->lnum[h] >= vn->vn_nr_item + 1)) {
1313                 int to_r;
1314
1315                 /* Since we are working on internal nodes, and our internal
1316                    nodes have fixed size entries, then we can balance by the
1317                    number of items rather than the space they consume.  In this
1318                    routine we set the left node equal to the right node,
1319                    allowing a difference of less than or equal to 1 child
1320                    pointer. */
1321                 to_r =
1322                     ((MAX_NR_KEY(Sh) << 1) + 2 - tb->lnum[h] - tb->rnum[h] +
1323                      vn->vn_nr_item + 1) / 2 - (MAX_NR_KEY(Sh) + 1 -
1324                                                 tb->rnum[h]);
1325                 set_parameters(tb, h, vn->vn_nr_item + 1 - to_r, to_r, 0, NULL,
1326                                -1, -1);
1327                 return CARRY_ON;
1328         }
1329
1330         /* this checks balance condition, that any two neighboring nodes can not fit in one node */
1331         RFALSE(h &&
1332                (tb->lnum[h] >= vn->vn_nr_item + 1 ||
1333                 tb->rnum[h] >= vn->vn_nr_item + 1),
1334                "vs-8220: tree is not balanced on internal level");
1335         RFALSE(!h && ((tb->lnum[h] >= vn->vn_nr_item && (tb->lbytes == -1)) ||
1336                       (tb->rnum[h] >= vn->vn_nr_item && (tb->rbytes == -1))),
1337                "vs-8225: tree is not balanced on leaf level");
1338
1339         /* all contents of S[0] can be moved into its neighbors
1340            S[0] will be removed after balancing. */
1341         if (!h && is_leaf_removable(tb))
1342                 return CARRY_ON;
1343
1344         /* why do we perform this check here rather than earlier??
1345            Answer: we can win 1 node in some cases above. Moreover we
1346            checked it above, when we checked, that S[0] is not removable
1347            in principle */
1348         if (sfree >= levbytes) {        /* new item fits into node S[h] without any shifting */
1349                 if (!h)
1350                         tb->s0num = vn->vn_nr_item;
1351                 set_parameters(tb, h, 0, 0, 1, NULL, -1, -1);
1352                 return NO_BALANCING_NEEDED;
1353         }
1354
1355         {
1356                 int lpar, rpar, nset, lset, rset, lrset;
1357                 /*
1358                  * regular overflowing of the node
1359                  */
1360
1361                 /* get_num_ver works in 2 modes (FLOW & NO_FLOW)
1362                    lpar, rpar - number of items we can shift to left/right neighbor (including splitting item)
1363                    nset, lset, rset, lrset - shows, whether flowing items give better packing
1364                  */
1365 #define FLOW 1
1366 #define NO_FLOW 0               /* do not any splitting */
1367
1368                 /* we choose one the following */
1369 #define NOTHING_SHIFT_NO_FLOW   0
1370 #define NOTHING_SHIFT_FLOW      5
1371 #define LEFT_SHIFT_NO_FLOW      10
1372 #define LEFT_SHIFT_FLOW         15
1373 #define RIGHT_SHIFT_NO_FLOW     20
1374 #define RIGHT_SHIFT_FLOW        25
1375 #define LR_SHIFT_NO_FLOW        30
1376 #define LR_SHIFT_FLOW           35
1377
1378                 lpar = tb->lnum[h];
1379                 rpar = tb->rnum[h];
1380
1381                 /* calculate number of blocks S[h] must be split into when
1382                    nothing is shifted to the neighbors,
1383                    as well as number of items in each part of the split node (s012 numbers),
1384                    and number of bytes (s1bytes) of the shared drop which flow to S1 if any */
1385                 nset = NOTHING_SHIFT_NO_FLOW;
1386                 nver = get_num_ver(vn->vn_mode, tb, h,
1387                                    0, -1, h ? vn->vn_nr_item : 0, -1,
1388                                    snum012, NO_FLOW);
1389
1390                 if (!h) {
1391                         int nver1;
1392
1393                         /* note, that in this case we try to bottle between S[0] and S1 (S1 - the first new node) */
1394                         nver1 = get_num_ver(vn->vn_mode, tb, h,
1395                                             0, -1, 0, -1,
1396                                             snum012 + NOTHING_SHIFT_FLOW, FLOW);
1397                         if (nver > nver1)
1398                                 nset = NOTHING_SHIFT_FLOW, nver = nver1;
1399                 }
1400
1401                 /* calculate number of blocks S[h] must be split into when
1402                    l_shift_num first items and l_shift_bytes of the right most
1403                    liquid item to be shifted are shifted to the left neighbor,
1404                    as well as number of items in each part of the splitted node (s012 numbers),
1405                    and number of bytes (s1bytes) of the shared drop which flow to S1 if any
1406                  */
1407                 lset = LEFT_SHIFT_NO_FLOW;
1408                 lnver = get_num_ver(vn->vn_mode, tb, h,
1409                                     lpar - ((h || tb->lbytes == -1) ? 0 : 1),
1410                                     -1, h ? vn->vn_nr_item : 0, -1,
1411                                     snum012 + LEFT_SHIFT_NO_FLOW, NO_FLOW);
1412                 if (!h) {
1413                         int lnver1;
1414
1415                         lnver1 = get_num_ver(vn->vn_mode, tb, h,
1416                                              lpar -
1417                                              ((tb->lbytes != -1) ? 1 : 0),
1418                                              tb->lbytes, 0, -1,
1419                                              snum012 + LEFT_SHIFT_FLOW, FLOW);
1420                         if (lnver > lnver1)
1421                                 lset = LEFT_SHIFT_FLOW, lnver = lnver1;
1422                 }
1423
1424                 /* calculate number of blocks S[h] must be split into when
1425                    r_shift_num first items and r_shift_bytes of the left most
1426                    liquid item to be shifted are shifted to the right neighbor,
1427                    as well as number of items in each part of the splitted node (s012 numbers),
1428                    and number of bytes (s1bytes) of the shared drop which flow to S1 if any
1429                  */
1430                 rset = RIGHT_SHIFT_NO_FLOW;
1431                 rnver = get_num_ver(vn->vn_mode, tb, h,
1432                                     0, -1,
1433                                     h ? (vn->vn_nr_item - rpar) : (rpar -
1434                                                                    ((tb->
1435                                                                      rbytes !=
1436                                                                      -1) ? 1 :
1437                                                                     0)), -1,
1438                                     snum012 + RIGHT_SHIFT_NO_FLOW, NO_FLOW);
1439                 if (!h) {
1440                         int rnver1;
1441
1442                         rnver1 = get_num_ver(vn->vn_mode, tb, h,
1443                                              0, -1,
1444                                              (rpar -
1445                                               ((tb->rbytes != -1) ? 1 : 0)),
1446                                              tb->rbytes,
1447                                              snum012 + RIGHT_SHIFT_FLOW, FLOW);
1448
1449                         if (rnver > rnver1)
1450                                 rset = RIGHT_SHIFT_FLOW, rnver = rnver1;
1451                 }
1452
1453                 /* calculate number of blocks S[h] must be split into when
1454                    items are shifted in both directions,
1455                    as well as number of items in each part of the splitted node (s012 numbers),
1456                    and number of bytes (s1bytes) of the shared drop which flow to S1 if any
1457                  */
1458                 lrset = LR_SHIFT_NO_FLOW;
1459                 lrnver = get_num_ver(vn->vn_mode, tb, h,
1460                                      lpar - ((h || tb->lbytes == -1) ? 0 : 1),
1461                                      -1,
1462                                      h ? (vn->vn_nr_item - rpar) : (rpar -
1463                                                                     ((tb->
1464                                                                       rbytes !=
1465                                                                       -1) ? 1 :
1466                                                                      0)), -1,
1467                                      snum012 + LR_SHIFT_NO_FLOW, NO_FLOW);
1468                 if (!h) {
1469                         int lrnver1;
1470
1471                         lrnver1 = get_num_ver(vn->vn_mode, tb, h,
1472                                               lpar -
1473                                               ((tb->lbytes != -1) ? 1 : 0),
1474                                               tb->lbytes,
1475                                               (rpar -
1476                                                ((tb->rbytes != -1) ? 1 : 0)),
1477                                               tb->rbytes,
1478                                               snum012 + LR_SHIFT_FLOW, FLOW);
1479                         if (lrnver > lrnver1)
1480                                 lrset = LR_SHIFT_FLOW, lrnver = lrnver1;
1481                 }
1482
1483                 /* Our general shifting strategy is:
1484                    1) to minimized number of new nodes;
1485                    2) to minimized number of neighbors involved in shifting;
1486                    3) to minimized number of disk reads; */
1487
1488                 /* we can win TWO or ONE nodes by shifting in both directions */
1489                 if (lrnver < lnver && lrnver < rnver) {
1490                         RFALSE(h &&
1491                                (tb->lnum[h] != 1 ||
1492                                 tb->rnum[h] != 1 ||
1493                                 lrnver != 1 || rnver != 2 || lnver != 2
1494                                 || h != 1), "vs-8230: bad h");
1495                         if (lrset == LR_SHIFT_FLOW)
1496                                 set_parameters(tb, h, tb->lnum[h], tb->rnum[h],
1497                                                lrnver, snum012 + lrset,
1498                                                tb->lbytes, tb->rbytes);
1499                         else
1500                                 set_parameters(tb, h,
1501                                                tb->lnum[h] -
1502                                                ((tb->lbytes == -1) ? 0 : 1),
1503                                                tb->rnum[h] -
1504                                                ((tb->rbytes == -1) ? 0 : 1),
1505                                                lrnver, snum012 + lrset, -1, -1);
1506
1507                         return CARRY_ON;
1508                 }
1509
1510                 /* if shifting doesn't lead to better packing then don't shift */
1511                 if (nver == lrnver) {
1512                         set_parameters(tb, h, 0, 0, nver, snum012 + nset, -1,
1513                                        -1);
1514                         return CARRY_ON;
1515                 }
1516
1517                 /* now we know that for better packing shifting in only one
1518                    direction either to the left or to the right is required */
1519
1520                 /*  if shifting to the left is better than shifting to the right */
1521                 if (lnver < rnver) {
1522                         SET_PAR_SHIFT_LEFT;
1523                         return CARRY_ON;
1524                 }
1525
1526                 /* if shifting to the right is better than shifting to the left */
1527                 if (lnver > rnver) {
1528                         SET_PAR_SHIFT_RIGHT;
1529                         return CARRY_ON;
1530                 }
1531
1532                 /* now shifting in either direction gives the same number
1533                    of nodes and we can make use of the cached neighbors */
1534                 if (is_left_neighbor_in_cache(tb, h)) {
1535                         SET_PAR_SHIFT_LEFT;
1536                         return CARRY_ON;
1537                 }
1538
1539                 /* shift to the right independently on whether the right neighbor in cache or not */
1540                 SET_PAR_SHIFT_RIGHT;
1541                 return CARRY_ON;
1542         }
1543 }
1544
1545 /* Check whether current node S[h] is balanced when Decreasing its size by
1546  * Deleting or Cutting for INTERNAL node of S+tree.
1547  * Calculate parameters for balancing for current level h.
1548  * Parameters:
1549  *      tb      tree_balance structure;
1550  *      h       current level of the node;
1551  *      inum    item number in S[h];
1552  *      mode    i - insert, p - paste;
1553  * Returns:     1 - schedule occurred;
1554  *              0 - balancing for higher levels needed;
1555  *             -1 - no balancing for higher levels needed;
1556  *             -2 - no disk space.
1557  *
1558  * Note: Items of internal nodes have fixed size, so the balance condition for
1559  * the internal part of S+tree is as for the B-trees.
1560  */
1561 static int dc_check_balance_internal(struct tree_balance *tb, int h)
1562 {
1563         struct virtual_node *vn = tb->tb_vn;
1564
1565         /* Sh is the node whose balance is currently being checked,
1566            and Fh is its father.  */
1567         struct buffer_head *Sh, *Fh;
1568         int maxsize, n_ret_value;
1569         int lfree, rfree /* free space in L and R */ ;
1570
1571         Sh = PATH_H_PBUFFER(tb->tb_path, h);
1572         Fh = PATH_H_PPARENT(tb->tb_path, h);
1573
1574         maxsize = MAX_CHILD_SIZE(Sh);
1575
1576 /*   using tb->insert_size[h], which is negative in this case, create_virtual_node calculates: */
1577 /*   new_nr_item = number of items node would have if operation is */
1578 /*      performed without balancing (new_nr_item); */
1579         create_virtual_node(tb, h);
1580
1581         if (!Fh) {              /* S[h] is the root. */
1582                 if (vn->vn_nr_item > 0) {
1583                         set_parameters(tb, h, 0, 0, 1, NULL, -1, -1);
1584                         return NO_BALANCING_NEEDED;     /* no balancing for higher levels needed */
1585                 }
1586                 /* new_nr_item == 0.
1587                  * Current root will be deleted resulting in
1588                  * decrementing the tree height. */
1589                 set_parameters(tb, h, 0, 0, 0, NULL, -1, -1);
1590                 return CARRY_ON;
1591         }
1592
1593         if ((n_ret_value = get_parents(tb, h)) != CARRY_ON)
1594                 return n_ret_value;
1595
1596         /* get free space of neighbors */
1597         rfree = get_rfree(tb, h);
1598         lfree = get_lfree(tb, h);
1599
1600         /* determine maximal number of items we can fit into neighbors */
1601         check_left(tb, h, lfree);
1602         check_right(tb, h, rfree);
1603
1604         if (vn->vn_nr_item >= MIN_NR_KEY(Sh)) { /* Balance condition for the internal node is valid.
1605                                                  * In this case we balance only if it leads to better packing. */
1606                 if (vn->vn_nr_item == MIN_NR_KEY(Sh)) { /* Here we join S[h] with one of its neighbors,
1607                                                          * which is impossible with greater values of new_nr_item. */
1608                         if (tb->lnum[h] >= vn->vn_nr_item + 1) {
1609                                 /* All contents of S[h] can be moved to L[h]. */
1610                                 int n;
1611                                 int order_L;
1612
1613                                 order_L =
1614                                     ((n =
1615                                       PATH_H_B_ITEM_ORDER(tb->tb_path,
1616                                                           h)) ==
1617                                      0) ? B_NR_ITEMS(tb->FL[h]) : n - 1;
1618                                 n = dc_size(B_N_CHILD(tb->FL[h], order_L)) /
1619                                     (DC_SIZE + KEY_SIZE);
1620                                 set_parameters(tb, h, -n - 1, 0, 0, NULL, -1,
1621                                                -1);
1622                                 return CARRY_ON;
1623                         }
1624
1625                         if (tb->rnum[h] >= vn->vn_nr_item + 1) {
1626                                 /* All contents of S[h] can be moved to R[h]. */
1627                                 int n;
1628                                 int order_R;
1629
1630                                 order_R =
1631                                     ((n =
1632                                       PATH_H_B_ITEM_ORDER(tb->tb_path,
1633                                                           h)) ==
1634                                      B_NR_ITEMS(Fh)) ? 0 : n + 1;
1635                                 n = dc_size(B_N_CHILD(tb->FR[h], order_R)) /
1636                                     (DC_SIZE + KEY_SIZE);
1637                                 set_parameters(tb, h, 0, -n - 1, 0, NULL, -1,
1638                                                -1);
1639                                 return CARRY_ON;
1640                         }
1641                 }
1642
1643                 if (tb->rnum[h] + tb->lnum[h] >= vn->vn_nr_item + 1) {
1644                         /* All contents of S[h] can be moved to the neighbors (L[h] & R[h]). */
1645                         int to_r;
1646
1647                         to_r =
1648                             ((MAX_NR_KEY(Sh) << 1) + 2 - tb->lnum[h] -
1649                              tb->rnum[h] + vn->vn_nr_item + 1) / 2 -
1650                             (MAX_NR_KEY(Sh) + 1 - tb->rnum[h]);
1651                         set_parameters(tb, h, vn->vn_nr_item + 1 - to_r, to_r,
1652                                        0, NULL, -1, -1);
1653                         return CARRY_ON;
1654                 }
1655
1656                 /* Balancing does not lead to better packing. */
1657                 set_parameters(tb, h, 0, 0, 1, NULL, -1, -1);
1658                 return NO_BALANCING_NEEDED;
1659         }
1660
1661         /* Current node contain insufficient number of items. Balancing is required. */
1662         /* Check whether we can merge S[h] with left neighbor. */
1663         if (tb->lnum[h] >= vn->vn_nr_item + 1)
1664                 if (is_left_neighbor_in_cache(tb, h)
1665                     || tb->rnum[h] < vn->vn_nr_item + 1 || !tb->FR[h]) {
1666                         int n;
1667                         int order_L;
1668
1669                         order_L =
1670                             ((n =
1671                               PATH_H_B_ITEM_ORDER(tb->tb_path,
1672                                                   h)) ==
1673                              0) ? B_NR_ITEMS(tb->FL[h]) : n - 1;
1674                         n = dc_size(B_N_CHILD(tb->FL[h], order_L)) / (DC_SIZE +
1675                                                                       KEY_SIZE);
1676                         set_parameters(tb, h, -n - 1, 0, 0, NULL, -1, -1);
1677                         return CARRY_ON;
1678                 }
1679
1680         /* Check whether we can merge S[h] with right neighbor. */
1681         if (tb->rnum[h] >= vn->vn_nr_item + 1) {
1682                 int n;
1683                 int order_R;
1684
1685                 order_R =
1686                     ((n =
1687                       PATH_H_B_ITEM_ORDER(tb->tb_path,
1688                                           h)) == B_NR_ITEMS(Fh)) ? 0 : (n + 1);
1689                 n = dc_size(B_N_CHILD(tb->FR[h], order_R)) / (DC_SIZE +
1690                                                               KEY_SIZE);
1691                 set_parameters(tb, h, 0, -n - 1, 0, NULL, -1, -1);
1692                 return CARRY_ON;
1693         }
1694
1695         /* All contents of S[h] can be moved to the neighbors (L[h] & R[h]). */
1696         if (tb->rnum[h] + tb->lnum[h] >= vn->vn_nr_item + 1) {
1697                 int to_r;
1698
1699                 to_r =
1700                     ((MAX_NR_KEY(Sh) << 1) + 2 - tb->lnum[h] - tb->rnum[h] +
1701                      vn->vn_nr_item + 1) / 2 - (MAX_NR_KEY(Sh) + 1 -
1702                                                 tb->rnum[h]);
1703                 set_parameters(tb, h, vn->vn_nr_item + 1 - to_r, to_r, 0, NULL,
1704                                -1, -1);
1705                 return CARRY_ON;
1706         }
1707
1708         /* For internal nodes try to borrow item from a neighbor */
1709         RFALSE(!tb->FL[h] && !tb->FR[h], "vs-8235: trying to borrow for root");
1710
1711         /* Borrow one or two items from caching neighbor */
1712         if (is_left_neighbor_in_cache(tb, h) || !tb->FR[h]) {
1713                 int from_l;
1714
1715                 from_l =
1716                     (MAX_NR_KEY(Sh) + 1 - tb->lnum[h] + vn->vn_nr_item +
1717                      1) / 2 - (vn->vn_nr_item + 1);
1718                 set_parameters(tb, h, -from_l, 0, 1, NULL, -1, -1);
1719                 return CARRY_ON;
1720         }
1721
1722         set_parameters(tb, h, 0,
1723                        -((MAX_NR_KEY(Sh) + 1 - tb->rnum[h] + vn->vn_nr_item +
1724                           1) / 2 - (vn->vn_nr_item + 1)), 1, NULL, -1, -1);
1725         return CARRY_ON;
1726 }
1727
1728 /* Check whether current node S[h] is balanced when Decreasing its size by
1729  * Deleting or Truncating for LEAF node of S+tree.
1730  * Calculate parameters for balancing for current level h.
1731  * Parameters:
1732  *      tb      tree_balance structure;
1733  *      h       current level of the node;
1734  *      inum    item number in S[h];
1735  *      mode    i - insert, p - paste;
1736  * Returns:     1 - schedule occurred;
1737  *              0 - balancing for higher levels needed;
1738  *             -1 - no balancing for higher levels needed;
1739  *             -2 - no disk space.
1740  */
1741 static int dc_check_balance_leaf(struct tree_balance *tb, int h)
1742 {
1743         struct virtual_node *vn = tb->tb_vn;
1744
1745         /* Number of bytes that must be deleted from
1746            (value is negative if bytes are deleted) buffer which
1747            contains node being balanced.  The mnemonic is that the
1748            attempted change in node space used level is levbytes bytes. */
1749         int levbytes;
1750         /* the maximal item size */
1751         int maxsize, n_ret_value;
1752         /* S0 is the node whose balance is currently being checked,
1753            and F0 is its father.  */
1754         struct buffer_head *S0, *F0;
1755         int lfree, rfree /* free space in L and R */ ;
1756
1757         S0 = PATH_H_PBUFFER(tb->tb_path, 0);
1758         F0 = PATH_H_PPARENT(tb->tb_path, 0);
1759
1760         levbytes = tb->insert_size[h];
1761
1762         maxsize = MAX_CHILD_SIZE(S0);   /* maximal possible size of an item */
1763
1764         if (!F0) {              /* S[0] is the root now. */
1765
1766                 RFALSE(-levbytes >= maxsize - B_FREE_SPACE(S0),
1767                        "vs-8240: attempt to create empty buffer tree");
1768
1769                 set_parameters(tb, h, 0, 0, 1, NULL, -1, -1);
1770                 return NO_BALANCING_NEEDED;
1771         }
1772
1773         if ((n_ret_value = get_parents(tb, h)) != CARRY_ON)
1774                 return n_ret_value;
1775
1776         /* get free space of neighbors */
1777         rfree = get_rfree(tb, h);
1778         lfree = get_lfree(tb, h);
1779
1780         create_virtual_node(tb, h);
1781
1782         /* if 3 leaves can be merge to one, set parameters and return */
1783         if (are_leaves_removable(tb, lfree, rfree))
1784                 return CARRY_ON;
1785
1786         /* determine maximal number of items we can shift to the left/right  neighbor
1787            and the maximal number of bytes that can flow to the left/right neighbor
1788            from the left/right most liquid item that cannot be shifted from S[0] entirely
1789          */
1790         check_left(tb, h, lfree);
1791         check_right(tb, h, rfree);
1792
1793         /* check whether we can merge S with left neighbor. */
1794         if (tb->lnum[0] >= vn->vn_nr_item && tb->lbytes == -1)
1795                 if (is_left_neighbor_in_cache(tb, h) || ((tb->rnum[0] - ((tb->rbytes == -1) ? 0 : 1)) < vn->vn_nr_item) ||      /* S can not be merged with R */
1796                     !tb->FR[h]) {
1797
1798                         RFALSE(!tb->FL[h],
1799                                "vs-8245: dc_check_balance_leaf: FL[h] must exist");
1800
1801                         /* set parameter to merge S[0] with its left neighbor */
1802                         set_parameters(tb, h, -1, 0, 0, NULL, -1, -1);
1803                         return CARRY_ON;
1804                 }
1805
1806         /* check whether we can merge S[0] with right neighbor. */
1807         if (tb->rnum[0] >= vn->vn_nr_item && tb->rbytes == -1) {
1808                 set_parameters(tb, h, 0, -1, 0, NULL, -1, -1);
1809                 return CARRY_ON;
1810         }
1811
1812         /* All contents of S[0] can be moved to the neighbors (L[0] & R[0]). Set parameters and return */
1813         if (is_leaf_removable(tb))
1814                 return CARRY_ON;
1815
1816         /* Balancing is not required. */
1817         tb->s0num = vn->vn_nr_item;
1818         set_parameters(tb, h, 0, 0, 1, NULL, -1, -1);
1819         return NO_BALANCING_NEEDED;
1820 }
1821
1822 /* Check whether current node S[h] is balanced when Decreasing its size by
1823  * Deleting or Cutting.
1824  * Calculate parameters for balancing for current level h.
1825  * Parameters:
1826  *      tb      tree_balance structure;
1827  *      h       current level of the node;
1828  *      inum    item number in S[h];
1829  *      mode    d - delete, c - cut.
1830  * Returns:     1 - schedule occurred;
1831  *              0 - balancing for higher levels needed;
1832  *             -1 - no balancing for higher levels needed;
1833  *             -2 - no disk space.
1834  */
1835 static int dc_check_balance(struct tree_balance *tb, int h)
1836 {
1837         RFALSE(!(PATH_H_PBUFFER(tb->tb_path, h)),
1838                "vs-8250: S is not initialized");
1839
1840         if (h)
1841                 return dc_check_balance_internal(tb, h);
1842         else
1843                 return dc_check_balance_leaf(tb, h);
1844 }
1845
1846 /* Check whether current node S[h] is balanced.
1847  * Calculate parameters for balancing for current level h.
1848  * Parameters:
1849  *
1850  *      tb      tree_balance structure:
1851  *
1852  *              tb is a large structure that must be read about in the header file
1853  *              at the same time as this procedure if the reader is to successfully
1854  *              understand this procedure
1855  *
1856  *      h       current level of the node;
1857  *      inum    item number in S[h];
1858  *      mode    i - insert, p - paste, d - delete, c - cut.
1859  * Returns:     1 - schedule occurred;
1860  *              0 - balancing for higher levels needed;
1861  *             -1 - no balancing for higher levels needed;
1862  *             -2 - no disk space.
1863  */
1864 static int check_balance(int mode,
1865                          struct tree_balance *tb,
1866                          int h,
1867                          int inum,
1868                          int pos_in_item,
1869                          struct item_head *ins_ih, const void *data)
1870 {
1871         struct virtual_node *vn;
1872
1873         vn = tb->tb_vn = (struct virtual_node *)(tb->vn_buf);
1874         vn->vn_free_ptr = (char *)(tb->tb_vn + 1);
1875         vn->vn_mode = mode;
1876         vn->vn_affected_item_num = inum;
1877         vn->vn_pos_in_item = pos_in_item;
1878         vn->vn_ins_ih = ins_ih;
1879         vn->vn_data = data;
1880
1881         RFALSE(mode == M_INSERT && !vn->vn_ins_ih,
1882                "vs-8255: ins_ih can not be 0 in insert mode");
1883
1884         if (tb->insert_size[h] > 0)
1885                 /* Calculate balance parameters when size of node is increasing. */
1886                 return ip_check_balance(tb, h);
1887
1888         /* Calculate balance parameters when  size of node is decreasing. */
1889         return dc_check_balance(tb, h);
1890 }
1891
1892 /* Check whether parent at the path is the really parent of the current node.*/
1893 static int get_direct_parent(struct tree_balance *tb, int n_h)
1894 {
1895         struct buffer_head *bh;
1896         struct treepath *p_s_path = tb->tb_path;
1897         int n_position,
1898             n_path_offset = PATH_H_PATH_OFFSET(tb->tb_path, n_h);
1899
1900         /* We are in the root or in the new root. */
1901         if (n_path_offset <= FIRST_PATH_ELEMENT_OFFSET) {
1902
1903                 RFALSE(n_path_offset < FIRST_PATH_ELEMENT_OFFSET - 1,
1904                        "PAP-8260: invalid offset in the path");
1905
1906                 if (PATH_OFFSET_PBUFFER(p_s_path, FIRST_PATH_ELEMENT_OFFSET)->
1907                     b_blocknr == SB_ROOT_BLOCK(tb->tb_sb)) {
1908                         /* Root is not changed. */
1909                         PATH_OFFSET_PBUFFER(p_s_path, n_path_offset - 1) = NULL;
1910                         PATH_OFFSET_POSITION(p_s_path, n_path_offset - 1) = 0;
1911                         return CARRY_ON;
1912                 }
1913                 return REPEAT_SEARCH;   /* Root is changed and we must recalculate the path. */
1914         }
1915
1916         if (!B_IS_IN_TREE
1917             (bh = PATH_OFFSET_PBUFFER(p_s_path, n_path_offset - 1)))
1918                 return REPEAT_SEARCH;   /* Parent in the path is not in the tree. */
1919
1920         if ((n_position =
1921              PATH_OFFSET_POSITION(p_s_path,
1922                                   n_path_offset - 1)) > B_NR_ITEMS(bh))
1923                 return REPEAT_SEARCH;
1924
1925         if (B_N_CHILD_NUM(bh, n_position) !=
1926             PATH_OFFSET_PBUFFER(p_s_path, n_path_offset)->b_blocknr)
1927                 /* Parent in the path is not parent of the current node in the tree. */
1928                 return REPEAT_SEARCH;
1929
1930         if (buffer_locked(bh)) {
1931                 __wait_on_buffer(bh);
1932                 if (FILESYSTEM_CHANGED_TB(tb))
1933                         return REPEAT_SEARCH;
1934         }
1935
1936         return CARRY_ON;        /* Parent in the path is unlocked and really parent of the current node.  */
1937 }
1938
1939 /* Using lnum[n_h] and rnum[n_h] we should determine what neighbors
1940  * of S[n_h] we
1941  * need in order to balance S[n_h], and get them if necessary.
1942  * Returns:     SCHEDULE_OCCURRED - schedule occurred while the function worked;
1943  *              CARRY_ON - schedule didn't occur while the function worked;
1944  */
1945 static int get_neighbors(struct tree_balance *tb, int n_h)
1946 {
1947         int n_child_position,
1948             n_path_offset = PATH_H_PATH_OFFSET(tb->tb_path, n_h + 1);
1949         unsigned long n_son_number;
1950         struct super_block *sb = tb->tb_sb;
1951         struct buffer_head *bh;
1952
1953         PROC_INFO_INC(sb, get_neighbors[n_h]);
1954
1955         if (tb->lnum[n_h]) {
1956                 /* We need left neighbor to balance S[n_h]. */
1957                 PROC_INFO_INC(sb, need_l_neighbor[n_h]);
1958                 bh = PATH_OFFSET_PBUFFER(tb->tb_path, n_path_offset);
1959
1960                 RFALSE(bh == tb->FL[n_h] &&
1961                        !PATH_OFFSET_POSITION(tb->tb_path, n_path_offset),
1962                        "PAP-8270: invalid position in the parent");
1963
1964                 n_child_position =
1965                     (bh ==
1966                      tb->FL[n_h]) ? tb->lkey[n_h] : B_NR_ITEMS(tb->
1967                                                                        FL[n_h]);
1968                 n_son_number = B_N_CHILD_NUM(tb->FL[n_h], n_child_position);
1969                 bh = sb_bread(sb, n_son_number);
1970                 if (!bh)
1971                         return IO_ERROR;
1972                 if (FILESYSTEM_CHANGED_TB(tb)) {
1973                         brelse(bh);
1974                         PROC_INFO_INC(sb, get_neighbors_restart[n_h]);
1975                         return REPEAT_SEARCH;
1976                 }
1977
1978                 RFALSE(!B_IS_IN_TREE(tb->FL[n_h]) ||
1979                        n_child_position > B_NR_ITEMS(tb->FL[n_h]) ||
1980                        B_N_CHILD_NUM(tb->FL[n_h], n_child_position) !=
1981                        bh->b_blocknr, "PAP-8275: invalid parent");
1982                 RFALSE(!B_IS_IN_TREE(bh), "PAP-8280: invalid child");
1983                 RFALSE(!n_h &&
1984                        B_FREE_SPACE(bh) !=
1985                        MAX_CHILD_SIZE(bh) -
1986                        dc_size(B_N_CHILD(tb->FL[0], n_child_position)),
1987                        "PAP-8290: invalid child size of left neighbor");
1988
1989                 brelse(tb->L[n_h]);
1990                 tb->L[n_h] = bh;
1991         }
1992
1993         /* We need right neighbor to balance S[n_path_offset]. */
1994         if (tb->rnum[n_h]) {
1995                 PROC_INFO_INC(sb, need_r_neighbor[n_h]);
1996                 bh = PATH_OFFSET_PBUFFER(tb->tb_path, n_path_offset);
1997
1998                 RFALSE(bh == tb->FR[n_h] &&
1999                        PATH_OFFSET_POSITION(tb->tb_path,
2000                                             n_path_offset) >=
2001                        B_NR_ITEMS(bh),
2002                        "PAP-8295: invalid position in the parent");
2003
2004                 n_child_position =
2005                     (bh == tb->FR[n_h]) ? tb->rkey[n_h] + 1 : 0;
2006                 n_son_number = B_N_CHILD_NUM(tb->FR[n_h], n_child_position);
2007                 bh = sb_bread(sb, n_son_number);
2008                 if (!bh)
2009                         return IO_ERROR;
2010                 if (FILESYSTEM_CHANGED_TB(tb)) {
2011                         brelse(bh);
2012                         PROC_INFO_INC(sb, get_neighbors_restart[n_h]);
2013                         return REPEAT_SEARCH;
2014                 }
2015                 brelse(tb->R[n_h]);
2016                 tb->R[n_h] = bh;
2017
2018                 RFALSE(!n_h
2019                        && B_FREE_SPACE(bh) !=
2020                        MAX_CHILD_SIZE(bh) -
2021                        dc_size(B_N_CHILD(tb->FR[0], n_child_position)),
2022                        "PAP-8300: invalid child size of right neighbor (%d != %d - %d)",
2023                        B_FREE_SPACE(bh), MAX_CHILD_SIZE(bh),
2024                        dc_size(B_N_CHILD(tb->FR[0], n_child_position)));
2025
2026         }
2027         return CARRY_ON;
2028 }
2029
2030 static int get_virtual_node_size(struct super_block *sb, struct buffer_head *bh)
2031 {
2032         int max_num_of_items;
2033         int max_num_of_entries;
2034         unsigned long blocksize = sb->s_blocksize;
2035
2036 #define MIN_NAME_LEN 1
2037
2038         max_num_of_items = (blocksize - BLKH_SIZE) / (IH_SIZE + MIN_ITEM_LEN);
2039         max_num_of_entries = (blocksize - BLKH_SIZE - IH_SIZE) /
2040             (DEH_SIZE + MIN_NAME_LEN);
2041
2042         return sizeof(struct virtual_node) +
2043             max(max_num_of_items * sizeof(struct virtual_item),
2044                 sizeof(struct virtual_item) + sizeof(struct direntry_uarea) +
2045                 (max_num_of_entries - 1) * sizeof(__u16));
2046 }
2047
2048 /* maybe we should fail balancing we are going to perform when kmalloc
2049    fails several times. But now it will loop until kmalloc gets
2050    required memory */
2051 static int get_mem_for_virtual_node(struct tree_balance *tb)
2052 {
2053         int check_fs = 0;
2054         int size;
2055         char *buf;
2056
2057         size = get_virtual_node_size(tb->tb_sb, PATH_PLAST_BUFFER(tb->tb_path));
2058
2059         if (size > tb->vn_buf_size) {
2060                 /* we have to allocate more memory for virtual node */
2061                 if (tb->vn_buf) {
2062                         /* free memory allocated before */
2063                         kfree(tb->vn_buf);
2064                         /* this is not needed if kfree is atomic */
2065                         check_fs = 1;
2066                 }
2067
2068                 /* virtual node requires now more memory */
2069                 tb->vn_buf_size = size;
2070
2071                 /* get memory for virtual item */
2072                 buf = kmalloc(size, GFP_ATOMIC | __GFP_NOWARN);
2073                 if (!buf) {
2074                         /* getting memory with GFP_KERNEL priority may involve
2075                            balancing now (due to indirect_to_direct conversion on
2076                            dcache shrinking). So, release path and collected
2077                            resources here */
2078                         free_buffers_in_tb(tb);
2079                         buf = kmalloc(size, GFP_NOFS);
2080                         if (!buf) {
2081                                 tb->vn_buf_size = 0;
2082                         }
2083                         tb->vn_buf = buf;
2084                         schedule();
2085                         return REPEAT_SEARCH;
2086                 }
2087
2088                 tb->vn_buf = buf;
2089         }
2090
2091         if (check_fs && FILESYSTEM_CHANGED_TB(tb))
2092                 return REPEAT_SEARCH;
2093
2094         return CARRY_ON;
2095 }
2096
2097 #ifdef CONFIG_REISERFS_CHECK
2098 static void tb_buffer_sanity_check(struct super_block *sb,
2099                                    struct buffer_head *bh,
2100                                    const char *descr, int level)
2101 {
2102         if (bh) {
2103                 if (atomic_read(&(bh->b_count)) <= 0)
2104
2105                         reiserfs_panic(sb, "jmacd-1", "negative or zero "
2106                                        "reference counter for buffer %s[%d] "
2107                                        "(%b)", descr, level, bh);
2108
2109                 if (!buffer_uptodate(bh))
2110                         reiserfs_panic(sb, "jmacd-2", "buffer is not up "
2111                                        "to date %s[%d] (%b)",
2112                                        descr, level, bh);
2113
2114                 if (!B_IS_IN_TREE(bh))
2115                         reiserfs_panic(sb, "jmacd-3", "buffer is not "
2116                                        "in tree %s[%d] (%b)",
2117                                        descr, level, bh);
2118
2119                 if (bh->b_bdev != sb->s_bdev)
2120                         reiserfs_panic(sb, "jmacd-4", "buffer has wrong "
2121                                        "device %s[%d] (%b)",
2122                                        descr, level, bh);
2123
2124                 if (bh->b_size != sb->s_blocksize)
2125                         reiserfs_panic(sb, "jmacd-5", "buffer has wrong "
2126                                        "blocksize %s[%d] (%b)",
2127                                        descr, level, bh);
2128
2129                 if (bh->b_blocknr > SB_BLOCK_COUNT(sb))
2130                         reiserfs_panic(sb, "jmacd-6", "buffer block "
2131                                        "number too high %s[%d] (%b)",
2132                                        descr, level, bh);
2133         }
2134 }
2135 #else
2136 static void tb_buffer_sanity_check(struct super_block *sb,
2137                                    struct buffer_head *bh,
2138                                    const char *descr, int level)
2139 {;
2140 }
2141 #endif
2142
2143 static int clear_all_dirty_bits(struct super_block *s, struct buffer_head *bh)
2144 {
2145         return reiserfs_prepare_for_journal(s, bh, 0);
2146 }
2147
2148 static int wait_tb_buffers_until_unlocked(struct tree_balance *tb)
2149 {
2150         struct buffer_head *locked;
2151 #ifdef CONFIG_REISERFS_CHECK
2152         int repeat_counter = 0;
2153 #endif
2154         int i;
2155
2156         do {
2157
2158                 locked = NULL;
2159
2160                 for (i = tb->tb_path->path_length;
2161                      !locked && i > ILLEGAL_PATH_ELEMENT_OFFSET; i--) {
2162                         if (PATH_OFFSET_PBUFFER(tb->tb_path, i)) {
2163                                 /* if I understand correctly, we can only be sure the last buffer
2164                                  ** in the path is in the tree --clm
2165                                  */
2166 #ifdef CONFIG_REISERFS_CHECK
2167                                 if (PATH_PLAST_BUFFER(tb->tb_path) ==
2168                                     PATH_OFFSET_PBUFFER(tb->tb_path, i))
2169                                         tb_buffer_sanity_check(tb->tb_sb,
2170                                                                PATH_OFFSET_PBUFFER
2171                                                                (tb->tb_path,
2172                                                                 i), "S",
2173                                                                tb->tb_path->
2174                                                                path_length - i);
2175 #endif
2176                                 if (!clear_all_dirty_bits(tb->tb_sb,
2177                                                           PATH_OFFSET_PBUFFER
2178                                                           (tb->tb_path,
2179                                                            i))) {
2180                                         locked =
2181                                             PATH_OFFSET_PBUFFER(tb->tb_path,
2182                                                                 i);
2183                                 }
2184                         }
2185                 }
2186
2187                 for (i = 0; !locked && i < MAX_HEIGHT && tb->insert_size[i];
2188                      i++) {
2189
2190                         if (tb->lnum[i]) {
2191
2192                                 if (tb->L[i]) {
2193                                         tb_buffer_sanity_check(tb->tb_sb,
2194                                                                tb->L[i],
2195                                                                "L", i);
2196                                         if (!clear_all_dirty_bits
2197                                             (tb->tb_sb, tb->L[i]))
2198                                                 locked = tb->L[i];
2199                                 }
2200
2201                                 if (!locked && tb->FL[i]) {
2202                                         tb_buffer_sanity_check(tb->tb_sb,
2203                                                                tb->FL[i],
2204                                                                "FL", i);
2205                                         if (!clear_all_dirty_bits
2206                                             (tb->tb_sb, tb->FL[i]))
2207                                                 locked = tb->FL[i];
2208                                 }
2209
2210                                 if (!locked && tb->CFL[i]) {
2211                                         tb_buffer_sanity_check(tb->tb_sb,
2212                                                                tb->CFL[i],
2213                                                                "CFL", i);
2214                                         if (!clear_all_dirty_bits
2215                                             (tb->tb_sb, tb->CFL[i]))
2216                                                 locked = tb->CFL[i];
2217                                 }
2218
2219                         }
2220
2221                         if (!locked && (tb->rnum[i])) {
2222
2223                                 if (tb->R[i]) {
2224                                         tb_buffer_sanity_check(tb->tb_sb,
2225                                                                tb->R[i],
2226                                                                "R", i);
2227                                         if (!clear_all_dirty_bits
2228                                             (tb->tb_sb, tb->R[i]))
2229                                                 locked = tb->R[i];
2230                                 }
2231
2232                                 if (!locked && tb->FR[i]) {
2233                                         tb_buffer_sanity_check(tb->tb_sb,
2234                                                                tb->FR[i],
2235                                                                "FR", i);
2236                                         if (!clear_all_dirty_bits
2237                                             (tb->tb_sb, tb->FR[i]))
2238                                                 locked = tb->FR[i];
2239                                 }
2240
2241                                 if (!locked && tb->CFR[i]) {
2242                                         tb_buffer_sanity_check(tb->tb_sb,
2243                                                                tb->CFR[i],
2244                                                                "CFR", i);
2245                                         if (!clear_all_dirty_bits
2246                                             (tb->tb_sb, tb->CFR[i]))
2247                                                 locked = tb->CFR[i];
2248                                 }
2249                         }
2250                 }
2251                 /* as far as I can tell, this is not required.  The FEB list seems
2252                  ** to be full of newly allocated nodes, which will never be locked,
2253                  ** dirty, or anything else.
2254                  ** To be safe, I'm putting in the checks and waits in.  For the moment,
2255                  ** they are needed to keep the code in journal.c from complaining
2256                  ** about the buffer.  That code is inside CONFIG_REISERFS_CHECK as well.
2257                  ** --clm
2258                  */
2259                 for (i = 0; !locked && i < MAX_FEB_SIZE; i++) {
2260                         if (tb->FEB[i]) {
2261                                 if (!clear_all_dirty_bits
2262                                     (tb->tb_sb, tb->FEB[i]))
2263                                         locked = tb->FEB[i];
2264                         }
2265                 }
2266
2267                 if (locked) {
2268 #ifdef CONFIG_REISERFS_CHECK
2269                         repeat_counter++;
2270                         if ((repeat_counter % 10000) == 0) {
2271                                 reiserfs_warning(tb->tb_sb, "reiserfs-8200",
2272                                                  "too many iterations waiting "
2273                                                  "for buffer to unlock "
2274                                                  "(%b)", locked);
2275
2276                                 /* Don't loop forever.  Try to recover from possible error. */
2277
2278                                 return (FILESYSTEM_CHANGED_TB(tb)) ?
2279                                     REPEAT_SEARCH : CARRY_ON;
2280                         }
2281 #endif
2282                         __wait_on_buffer(locked);
2283                         if (FILESYSTEM_CHANGED_TB(tb))
2284                                 return REPEAT_SEARCH;
2285                 }
2286
2287         } while (locked);
2288
2289         return CARRY_ON;
2290 }
2291
2292 /* Prepare for balancing, that is
2293  *      get all necessary parents, and neighbors;
2294  *      analyze what and where should be moved;
2295  *      get sufficient number of new nodes;
2296  * Balancing will start only after all resources will be collected at a time.
2297  *
2298  * When ported to SMP kernels, only at the last moment after all needed nodes
2299  * are collected in cache, will the resources be locked using the usual
2300  * textbook ordered lock acquisition algorithms.  Note that ensuring that
2301  * this code neither write locks what it does not need to write lock nor locks out of order
2302  * will be a pain in the butt that could have been avoided.  Grumble grumble. -Hans
2303  *
2304  * fix is meant in the sense of render unchanging
2305  *
2306  * Latency might be improved by first gathering a list of what buffers are needed
2307  * and then getting as many of them in parallel as possible? -Hans
2308  *
2309  * Parameters:
2310  *      op_mode i - insert, d - delete, c - cut (truncate), p - paste (append)
2311  *      tb      tree_balance structure;
2312  *      inum    item number in S[h];
2313  *      pos_in_item - comment this if you can
2314  *      ins_ih  item head of item being inserted
2315  *      data    inserted item or data to be pasted
2316  * Returns:     1 - schedule occurred while the function worked;
2317  *              0 - schedule didn't occur while the function worked;
2318  *             -1 - if no_disk_space
2319  */
2320
2321 int fix_nodes(int n_op_mode, struct tree_balance *tb,
2322               struct item_head *p_s_ins_ih, const void *data)
2323 {
2324         int n_ret_value, n_h, n_item_num = PATH_LAST_POSITION(tb->tb_path);
2325         int n_pos_in_item;
2326
2327         /* we set wait_tb_buffers_run when we have to restore any dirty bits cleared
2328          ** during wait_tb_buffers_run
2329          */
2330         int wait_tb_buffers_run = 0;
2331         struct buffer_head *tbS0 = PATH_PLAST_BUFFER(tb->tb_path);
2332
2333         ++REISERFS_SB(tb->tb_sb)->s_fix_nodes;
2334
2335         n_pos_in_item = tb->tb_path->pos_in_item;
2336
2337         tb->fs_gen = get_generation(tb->tb_sb);
2338
2339         /* we prepare and log the super here so it will already be in the
2340          ** transaction when do_balance needs to change it.
2341          ** This way do_balance won't have to schedule when trying to prepare
2342          ** the super for logging
2343          */
2344         reiserfs_prepare_for_journal(tb->tb_sb,
2345                                      SB_BUFFER_WITH_SB(tb->tb_sb), 1);
2346         journal_mark_dirty(tb->transaction_handle, tb->tb_sb,
2347                            SB_BUFFER_WITH_SB(tb->tb_sb));
2348         if (FILESYSTEM_CHANGED_TB(tb))
2349                 return REPEAT_SEARCH;
2350
2351         /* if it possible in indirect_to_direct conversion */
2352         if (buffer_locked(tbS0)) {
2353                 __wait_on_buffer(tbS0);
2354                 if (FILESYSTEM_CHANGED_TB(tb))
2355                         return REPEAT_SEARCH;
2356         }
2357 #ifdef CONFIG_REISERFS_CHECK
2358         if (cur_tb) {
2359                 print_cur_tb("fix_nodes");
2360                 reiserfs_panic(tb->tb_sb, "PAP-8305",
2361                                "there is pending do_balance");
2362         }
2363
2364         if (!buffer_uptodate(tbS0) || !B_IS_IN_TREE(tbS0))
2365                 reiserfs_panic(tb->tb_sb, "PAP-8320", "S[0] (%b %z) is "
2366                                "not uptodate at the beginning of fix_nodes "
2367                                "or not in tree (mode %c)",
2368                                tbS0, tbS0, n_op_mode);
2369
2370         /* Check parameters. */
2371         switch (n_op_mode) {
2372         case M_INSERT:
2373                 if (n_item_num <= 0 || n_item_num > B_NR_ITEMS(tbS0))
2374                         reiserfs_panic(tb->tb_sb, "PAP-8330", "Incorrect "
2375                                        "item number %d (in S0 - %d) in case "
2376                                        "of insert", n_item_num,
2377                                        B_NR_ITEMS(tbS0));
2378                 break;
2379         case M_PASTE:
2380         case M_DELETE:
2381         case M_CUT:
2382                 if (n_item_num < 0 || n_item_num >= B_NR_ITEMS(tbS0)) {
2383                         print_block(tbS0, 0, -1, -1);
2384                         reiserfs_panic(tb->tb_sb, "PAP-8335", "Incorrect "
2385                                        "item number(%d); mode = %c "
2386                                        "insert_size = %d",
2387                                        n_item_num, n_op_mode,
2388                                        tb->insert_size[0]);
2389                 }
2390                 break;
2391         default:
2392                 reiserfs_panic(tb->tb_sb, "PAP-8340", "Incorrect mode "
2393                                "of operation");
2394         }
2395 #endif
2396
2397         if (get_mem_for_virtual_node(tb) == REPEAT_SEARCH)
2398                 // FIXME: maybe -ENOMEM when tb->vn_buf == 0? Now just repeat
2399                 return REPEAT_SEARCH;
2400
2401         /* Starting from the leaf level; for all levels n_h of the tree. */
2402         for (n_h = 0; n_h < MAX_HEIGHT && tb->insert_size[n_h]; n_h++) {
2403                 n_ret_value = get_direct_parent(tb, n_h);
2404                 if (n_ret_value != CARRY_ON)
2405                         goto repeat;
2406
2407                 n_ret_value = check_balance(n_op_mode, tb, n_h, n_item_num,
2408                                             n_pos_in_item, p_s_ins_ih, data);
2409                 if (n_ret_value != CARRY_ON) {
2410                         if (n_ret_value == NO_BALANCING_NEEDED) {
2411                                 /* No balancing for higher levels needed. */
2412                                 n_ret_value = get_neighbors(tb, n_h);
2413                                 if (n_ret_value != CARRY_ON)
2414                                         goto repeat;
2415                                 if (n_h != MAX_HEIGHT - 1)
2416                                         tb->insert_size[n_h + 1] = 0;
2417                                 /* ok, analysis and resource gathering are complete */
2418                                 break;
2419                         }
2420                         goto repeat;
2421                 }
2422
2423                 n_ret_value = get_neighbors(tb, n_h);
2424                 if (n_ret_value != CARRY_ON)
2425                         goto repeat;
2426
2427                 /* No disk space, or schedule occurred and analysis may be
2428                  * invalid and needs to be redone. */
2429                 n_ret_value = get_empty_nodes(tb, n_h);
2430                 if (n_ret_value != CARRY_ON)
2431                         goto repeat;
2432
2433                 if (!PATH_H_PBUFFER(tb->tb_path, n_h)) {
2434                         /* We have a positive insert size but no nodes exist on this
2435                            level, this means that we are creating a new root. */
2436
2437                         RFALSE(tb->blknum[n_h] != 1,
2438                                "PAP-8350: creating new empty root");
2439
2440                         if (n_h < MAX_HEIGHT - 1)
2441                                 tb->insert_size[n_h + 1] = 0;
2442                 } else if (!PATH_H_PBUFFER(tb->tb_path, n_h + 1)) {
2443                         if (tb->blknum[n_h] > 1) {
2444                                 /* The tree needs to be grown, so this node S[n_h]
2445                                    which is the root node is split into two nodes,
2446                                    and a new node (S[n_h+1]) will be created to
2447                                    become the root node.  */
2448
2449                                 RFALSE(n_h == MAX_HEIGHT - 1,
2450                                        "PAP-8355: attempt to create too high of a tree");
2451
2452                                 tb->insert_size[n_h + 1] =
2453                                     (DC_SIZE +
2454                                      KEY_SIZE) * (tb->blknum[n_h] - 1) +
2455                                     DC_SIZE;
2456                         } else if (n_h < MAX_HEIGHT - 1)
2457                                 tb->insert_size[n_h + 1] = 0;
2458                 } else
2459                         tb->insert_size[n_h + 1] =
2460                             (DC_SIZE + KEY_SIZE) * (tb->blknum[n_h] - 1);
2461         }
2462
2463         n_ret_value = wait_tb_buffers_until_unlocked(tb);
2464         if (n_ret_value == CARRY_ON) {
2465                 if (FILESYSTEM_CHANGED_TB(tb)) {
2466                         wait_tb_buffers_run = 1;
2467                         n_ret_value = REPEAT_SEARCH;
2468                         goto repeat;
2469                 } else {
2470                         return CARRY_ON;
2471                 }
2472         } else {
2473                 wait_tb_buffers_run = 1;
2474                 goto repeat;
2475         }
2476
2477       repeat:
2478         // fix_nodes was unable to perform its calculation due to
2479         // filesystem got changed under us, lack of free disk space or i/o
2480         // failure. If the first is the case - the search will be
2481         // repeated. For now - free all resources acquired so far except
2482         // for the new allocated nodes
2483         {
2484                 int i;
2485
2486                 /* Release path buffers. */
2487                 if (wait_tb_buffers_run) {
2488                         pathrelse_and_restore(tb->tb_sb, tb->tb_path);
2489                 } else {
2490                         pathrelse(tb->tb_path);
2491                 }
2492                 /* brelse all resources collected for balancing */
2493                 for (i = 0; i < MAX_HEIGHT; i++) {
2494                         if (wait_tb_buffers_run) {
2495                                 reiserfs_restore_prepared_buffer(tb->tb_sb,
2496                                                                  tb->L[i]);
2497                                 reiserfs_restore_prepared_buffer(tb->tb_sb,
2498                                                                  tb->R[i]);
2499                                 reiserfs_restore_prepared_buffer(tb->tb_sb,
2500                                                                  tb->FL[i]);
2501                                 reiserfs_restore_prepared_buffer(tb->tb_sb,
2502                                                                  tb->FR[i]);
2503                                 reiserfs_restore_prepared_buffer(tb->tb_sb,
2504                                                                  tb->
2505                                                                  CFL[i]);
2506                                 reiserfs_restore_prepared_buffer(tb->tb_sb,
2507                                                                  tb->
2508                                                                  CFR[i]);
2509                         }
2510
2511                         brelse(tb->L[i]);
2512                         brelse(tb->R[i]);
2513                         brelse(tb->FL[i]);
2514                         brelse(tb->FR[i]);
2515                         brelse(tb->CFL[i]);
2516                         brelse(tb->CFR[i]);
2517
2518                         tb->L[i] = NULL;
2519                         tb->R[i] = NULL;
2520                         tb->FL[i] = NULL;
2521                         tb->FR[i] = NULL;
2522                         tb->CFL[i] = NULL;
2523                         tb->CFR[i] = NULL;
2524                 }
2525
2526                 if (wait_tb_buffers_run) {
2527                         for (i = 0; i < MAX_FEB_SIZE; i++) {
2528                                 if (tb->FEB[i])
2529                                         reiserfs_restore_prepared_buffer
2530                                             (tb->tb_sb, tb->FEB[i]);
2531                         }
2532                 }
2533                 return n_ret_value;
2534         }
2535
2536 }
2537
2538 /* Anatoly will probably forgive me renaming tb to tb. I just
2539    wanted to make lines shorter */
2540 void unfix_nodes(struct tree_balance *tb)
2541 {
2542         int i;
2543
2544         /* Release path buffers. */
2545         pathrelse_and_restore(tb->tb_sb, tb->tb_path);
2546
2547         /* brelse all resources collected for balancing */
2548         for (i = 0; i < MAX_HEIGHT; i++) {
2549                 reiserfs_restore_prepared_buffer(tb->tb_sb, tb->L[i]);
2550                 reiserfs_restore_prepared_buffer(tb->tb_sb, tb->R[i]);
2551                 reiserfs_restore_prepared_buffer(tb->tb_sb, tb->FL[i]);
2552                 reiserfs_restore_prepared_buffer(tb->tb_sb, tb->FR[i]);
2553                 reiserfs_restore_prepared_buffer(tb->tb_sb, tb->CFL[i]);
2554                 reiserfs_restore_prepared_buffer(tb->tb_sb, tb->CFR[i]);
2555
2556                 brelse(tb->L[i]);
2557                 brelse(tb->R[i]);
2558                 brelse(tb->FL[i]);
2559                 brelse(tb->FR[i]);
2560                 brelse(tb->CFL[i]);
2561                 brelse(tb->CFR[i]);
2562         }
2563
2564         /* deal with list of allocated (used and unused) nodes */
2565         for (i = 0; i < MAX_FEB_SIZE; i++) {
2566                 if (tb->FEB[i]) {
2567                         b_blocknr_t blocknr = tb->FEB[i]->b_blocknr;
2568                         /* de-allocated block which was not used by balancing and
2569                            bforget about buffer for it */
2570                         brelse(tb->FEB[i]);
2571                         reiserfs_free_block(tb->transaction_handle, NULL,
2572                                             blocknr, 0);
2573                 }
2574                 if (tb->used[i]) {
2575                         /* release used as new nodes including a new root */
2576                         brelse(tb->used[i]);
2577                 }
2578         }
2579
2580         kfree(tb->vn_buf);
2581
2582 }