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 *p_s_tb)
 753 {
 754         int n_counter;
 755
 756         pathrelse(p_s_tb->tb_path);
 757
 758         for (n_counter = 0; n_counter < MAX_HEIGHT; n_counter++) {
 759                 brelse(p_s_tb->L[n_counter]);
 760                 brelse(p_s_tb->R[n_counter]);
 761                 brelse(p_s_tb->FL[n_counter]);
 762                 brelse(p_s_tb->FR[n_counter]);
 763                 brelse(p_s_tb->CFL[n_counter]);
 764                 brelse(p_s_tb->CFR[n_counter]);
 765
 766                 p_s_tb->L[n_counter] = NULL;
 767                 p_s_tb->R[n_counter] = NULL;
 768                 p_s_tb->FL[n_counter] = NULL;
 769                 p_s_tb->FR[n_counter] = NULL;
 770                 p_s_tb->CFL[n_counter] = NULL;
 771                 p_s_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 *p_s_tb, int n_h)
 782 {
 783         struct buffer_head *p_s_new_bh,
 784             *p_s_Sh = PATH_H_PBUFFER(p_s_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 = p_s_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 = p_s_tb->cur_blknum;
 807              n_counter < n_h; n_counter++)
 808                 n_number_of_freeblk -=
 809                     (p_s_tb->blknum[n_counter]) ? (p_s_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) ? (p_s_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(p_s_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(p_s_tb->FEB[p_s_tb->cur_blknum],
 842                        "PAP-8141: busy slot for new buffer");
 843
 844                 set_buffer_journal_new(p_s_new_bh);
 845                 p_s_tb->FEB[p_s_tb->cur_blknum++] = p_s_new_bh;
 846         }
 847
 848         if (n_retval == CARRY_ON && FILESYSTEM_CHANGED_TB(p_s_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 *p_s_tb, int n_h)
 900 {
 901         struct buffer_head *p_s_father, *left;
 902         struct super_block *sb = p_s_tb->tb_sb;
 903         b_blocknr_t n_left_neighbor_blocknr;
 904         int n_left_neighbor_position;
 905
 906         if (!p_s_tb->FL[n_h])   /* Father of the left neighbor does not exist. */
 907                 return 0;
 908
 909         /* Calculate father of the node to be balanced. */
 910         p_s_father = PATH_H_PBUFFER(p_s_tb->tb_path, n_h + 1);
 911
 912         RFALSE(!p_s_father ||
 913                !B_IS_IN_TREE(p_s_father) ||
 914                !B_IS_IN_TREE(p_s_tb->FL[n_h]) ||
 915                !buffer_uptodate(p_s_father) ||
 916                !buffer_uptodate(p_s_tb->FL[n_h]),
 917                "vs-8165: F[h] (%b) or FL[h] (%b) is invalid",
 918                p_s_father, p_s_tb->FL[n_h]);
 919
 920         /* Get position of the pointer to the left neighbor into the left father. */
 921         n_left_neighbor_position = (p_s_father == p_s_tb->FL[n_h]) ?
 922             p_s_tb->lkey[n_h] : B_NR_ITEMS(p_s_tb->FL[n_h]);
 923         /* Get left neighbor block number. */
 924         n_left_neighbor_blocknr =
 925             B_N_CHILD_NUM(p_s_tb->FL[n_h], n_left_neighbor_position);
 926         /* Look for the left neighbor in the cache. */
 927         if ((left = sb_find_get_block(sb, n_left_neighbor_blocknr))) {
 928
 929                 RFALSE(buffer_uptodate(left) && !B_IS_IN_TREE(left),
 930                        "vs-8170: left neighbor (%b %z) is not in the tree",
 931                        left, left);
 932                 put_bh(left);
 933                 return 1;
 934         }
 935
 936         return 0;
 937 }
 938
 939 #define LEFT_PARENTS  'l'
 940 #define RIGHT_PARENTS 'r'
 941
 942 static void decrement_key(struct cpu_key *p_s_key)
 943 {
 944         // call item specific function for this key
 945         item_ops[cpu_key_k_type(p_s_key)]->decrement_key(p_s_key);
 946 }
 947
 948 /* Calculate far left/right parent of the left/right neighbor of the current node, that
 949  * is calculate the left/right (FL[h]/FR[h]) neighbor of the parent F[h].
 950  * Calculate left/right common parent of the current node and L[h]/R[h].
 951  * Calculate left/right delimiting key position.
 952  * Returns:     PATH_INCORRECT   - path in the tree is not correct;
 953                 SCHEDULE_OCCURRED - schedule occurred while the function worked;
 954  *              CARRY_ON         - schedule didn't occur while the function worked;
 955  */
 956 static int get_far_parent(struct tree_balance *p_s_tb,
 957                           int n_h,
 958                           struct buffer_head **pp_s_father,
 959                           struct buffer_head **pp_s_com_father, char c_lr_par)
 960 {
 961         struct buffer_head *p_s_parent;
 962         INITIALIZE_PATH(s_path_to_neighbor_father);
 963         struct treepath *p_s_path = p_s_tb->tb_path;
 964         struct cpu_key s_lr_father_key;
 965         int n_counter,
 966             n_position = INT_MAX,
 967             n_first_last_position = 0,
 968             n_path_offset = PATH_H_PATH_OFFSET(p_s_path, n_h);
 969
 970         /* Starting from F[n_h] go upwards in the tree, and look for the common
 971            ancestor of F[n_h], and its neighbor l/r, that should be obtained. */
 972
 973         n_counter = n_path_offset;
 974
 975         RFALSE(n_counter < FIRST_PATH_ELEMENT_OFFSET,
 976                "PAP-8180: invalid path length");
 977
 978         for (; n_counter > FIRST_PATH_ELEMENT_OFFSET; n_counter--) {
 979                 /* Check whether parent of the current buffer in the path is really parent in the tree. */
 980                 if (!B_IS_IN_TREE
 981                     (p_s_parent = PATH_OFFSET_PBUFFER(p_s_path, n_counter - 1)))
 982                         return REPEAT_SEARCH;
 983                 /* Check whether position in the parent is correct. */
 984                 if ((n_position =
 985                      PATH_OFFSET_POSITION(p_s_path,
 986                                           n_counter - 1)) >
 987                     B_NR_ITEMS(p_s_parent))
 988                         return REPEAT_SEARCH;
 989                 /* Check whether parent at the path really points to the child. */
 990                 if (B_N_CHILD_NUM(p_s_parent, n_position) !=
 991                     PATH_OFFSET_PBUFFER(p_s_path, n_counter)->b_blocknr)
 992                         return REPEAT_SEARCH;
 993                 /* Return delimiting key if position in the parent is not equal to first/last one. */
 994                 if (c_lr_par == RIGHT_PARENTS)
 995                         n_first_last_position = B_NR_ITEMS(p_s_parent);
 996                 if (n_position != n_first_last_position) {
 997                         *pp_s_com_father = p_s_parent;
 998                         get_bh(*pp_s_com_father);
 999                         /*(*pp_s_com_father = p_s_parent)->b_count++; */
1000                         break;
1001                 }
1002         }
1003
1004         /* if we are in the root of the tree, then there is no common father */
1005         if (n_counter == FIRST_PATH_ELEMENT_OFFSET) {
1006                 /* Check whether first buffer in the path is the root of the tree. */
1007                 if (PATH_OFFSET_PBUFFER
1008                     (p_s_tb->tb_path,
1009                      FIRST_PATH_ELEMENT_OFFSET)->b_blocknr ==
1010                     SB_ROOT_BLOCK(p_s_tb->tb_sb)) {
1011                         *pp_s_father = *pp_s_com_father = NULL;
1012                         return CARRY_ON;
1013                 }
1014                 return REPEAT_SEARCH;
1015         }
1016
1017         RFALSE(B_LEVEL(*pp_s_com_father) <= DISK_LEAF_NODE_LEVEL,
1018                "PAP-8185: (%b %z) level too small",
1019                *pp_s_com_father, *pp_s_com_father);
1020
1021         /* Check whether the common parent is locked. */
1022
1023         if (buffer_locked(*pp_s_com_father)) {
1024                 __wait_on_buffer(*pp_s_com_father);
1025                 if (FILESYSTEM_CHANGED_TB(p_s_tb)) {
1026                         brelse(*pp_s_com_father);
1027                         return REPEAT_SEARCH;
1028                 }
1029         }
1030
1031         /* So, we got common parent of the current node and its left/right neighbor.
1032            Now we are geting the parent of the left/right neighbor. */
1033
1034         /* Form key to get parent of the left/right neighbor. */
1035         le_key2cpu_key(&s_lr_father_key,
1036                        B_N_PDELIM_KEY(*pp_s_com_father,
1037                                       (c_lr_par ==
1038                                        LEFT_PARENTS) ? (p_s_tb->lkey[n_h - 1] =
1039                                                         n_position -
1040                                                         1) : (p_s_tb->rkey[n_h -
1041                                                                            1] =
1042                                                               n_position)));
1043
1044         if (c_lr_par == LEFT_PARENTS)
1045                 decrement_key(&s_lr_father_key);
1046
1047         if (search_by_key
1048             (p_s_tb->tb_sb, &s_lr_father_key, &s_path_to_neighbor_father,
1049              n_h + 1) == IO_ERROR)
1050                 // path is released
1051                 return IO_ERROR;
1052
1053         if (FILESYSTEM_CHANGED_TB(p_s_tb)) {
1054                 pathrelse(&s_path_to_neighbor_father);
1055                 brelse(*pp_s_com_father);
1056                 return REPEAT_SEARCH;
1057         }
1058
1059         *pp_s_father = PATH_PLAST_BUFFER(&s_path_to_neighbor_father);
1060
1061         RFALSE(B_LEVEL(*pp_s_father) != n_h + 1,
1062                "PAP-8190: (%b %z) level too small", *pp_s_father, *pp_s_father);
1063         RFALSE(s_path_to_neighbor_father.path_length <
1064                FIRST_PATH_ELEMENT_OFFSET, "PAP-8192: path length is too small");
1065
1066         s_path_to_neighbor_father.path_length--;
1067         pathrelse(&s_path_to_neighbor_father);
1068         return CARRY_ON;
1069 }
1070
1071 /* Get parents of neighbors of node in the path(S[n_path_offset]) and common parents of
1072  * S[n_path_offset] and L[n_path_offset]/R[n_path_offset]: F[n_path_offset], FL[n_path_offset],
1073  * FR[n_path_offset], CFL[n_path_offset], CFR[n_path_offset].
1074  * Calculate numbers of left and right delimiting keys position: lkey[n_path_offset], rkey[n_path_offset].
1075  * Returns:     SCHEDULE_OCCURRED - schedule occurred while the function worked;
1076  *              CARRY_ON - schedule didn't occur while the function worked;
1077  */
1078 static int get_parents(struct tree_balance *p_s_tb, int n_h)
1079 {
1080         struct treepath *p_s_path = p_s_tb->tb_path;
1081         int n_position,
1082             n_ret_value,
1083             n_path_offset = PATH_H_PATH_OFFSET(p_s_tb->tb_path, n_h);
1084         struct buffer_head *p_s_curf, *p_s_curcf;
1085
1086         /* Current node is the root of the tree or will be root of the tree */
1087         if (n_path_offset <= FIRST_PATH_ELEMENT_OFFSET) {
1088                 /* The root can not have parents.
1089                    Release nodes which previously were obtained as parents of the current node neighbors. */
1090                 brelse(p_s_tb->FL[n_h]);
1091                 brelse(p_s_tb->CFL[n_h]);
1092                 brelse(p_s_tb->FR[n_h]);
1093                 brelse(p_s_tb->CFR[n_h]);
1094                 p_s_tb->FL[n_h] = p_s_tb->CFL[n_h] = p_s_tb->FR[n_h] =
1095                     p_s_tb->CFR[n_h] = NULL;
1096                 return CARRY_ON;
1097         }
1098
1099         /* Get parent FL[n_path_offset] of L[n_path_offset]. */
1100         if ((n_position = PATH_OFFSET_POSITION(p_s_path, n_path_offset - 1))) {
1101                 /* Current node is not the first child of its parent. */
1102                 /*(p_s_curf = p_s_curcf = PATH_OFFSET_PBUFFER(p_s_path, n_path_offset - 1))->b_count += 2; */
1103                 p_s_curf = p_s_curcf =
1104                     PATH_OFFSET_PBUFFER(p_s_path, n_path_offset - 1);
1105                 get_bh(p_s_curf);
1106                 get_bh(p_s_curf);
1107                 p_s_tb->lkey[n_h] = n_position - 1;
1108         } else {
1109                 /* Calculate current parent of L[n_path_offset], which is the left neighbor of the current node.
1110                    Calculate current common parent of L[n_path_offset] and the current node. Note that
1111                    CFL[n_path_offset] not equal FL[n_path_offset] and CFL[n_path_offset] not equal F[n_path_offset].
1112                    Calculate lkey[n_path_offset]. */
1113                 if ((n_ret_value = get_far_parent(p_s_tb, n_h + 1, &p_s_curf,
1114                                                   &p_s_curcf,
1115                                                   LEFT_PARENTS)) != CARRY_ON)
1116                         return n_ret_value;
1117         }
1118
1119         brelse(p_s_tb->FL[n_h]);
1120         p_s_tb->FL[n_h] = p_s_curf;     /* New initialization of FL[n_h]. */
1121         brelse(p_s_tb->CFL[n_h]);
1122         p_s_tb->CFL[n_h] = p_s_curcf;   /* New initialization of CFL[n_h]. */
1123
1124         RFALSE((p_s_curf && !B_IS_IN_TREE(p_s_curf)) ||
1125                (p_s_curcf && !B_IS_IN_TREE(p_s_curcf)),
1126                "PAP-8195: FL (%b) or CFL (%b) is invalid", p_s_curf, p_s_curcf);
1127
1128 /* Get parent FR[n_h] of R[n_h]. */
1129
1130 /* Current node is the last child of F[n_h]. FR[n_h] != F[n_h]. */
1131         if (n_position == B_NR_ITEMS(PATH_H_PBUFFER(p_s_path, n_h + 1))) {
1132 /* Calculate current parent of R[n_h], which is the right neighbor of F[n_h].
1133    Calculate current common parent of R[n_h] and current node. Note that CFR[n_h]
1134    not equal FR[n_path_offset] and CFR[n_h] not equal F[n_h]. */
1135                 if ((n_ret_value =
1136                      get_far_parent(p_s_tb, n_h + 1, &p_s_curf, &p_s_curcf,
1137                                     RIGHT_PARENTS)) != CARRY_ON)
1138                         return n_ret_value;
1139         } else {
1140 /* Current node is not the last child of its parent F[n_h]. */
1141                 /*(p_s_curf = p_s_curcf = PATH_OFFSET_PBUFFER(p_s_path, n_path_offset - 1))->b_count += 2; */
1142                 p_s_curf = p_s_curcf =
1143                     PATH_OFFSET_PBUFFER(p_s_path, n_path_offset - 1);
1144                 get_bh(p_s_curf);
1145                 get_bh(p_s_curf);
1146                 p_s_tb->rkey[n_h] = n_position;
1147         }
1148
1149         brelse(p_s_tb->FR[n_h]);
1150         p_s_tb->FR[n_h] = p_s_curf;     /* New initialization of FR[n_path_offset]. */
1151
1152         brelse(p_s_tb->CFR[n_h]);
1153         p_s_tb->CFR[n_h] = p_s_curcf;   /* New initialization of CFR[n_path_offset]. */
1154
1155         RFALSE((p_s_curf && !B_IS_IN_TREE(p_s_curf)) ||
1156                (p_s_curcf && !B_IS_IN_TREE(p_s_curcf)),
1157                "PAP-8205: FR (%b) or CFR (%b) is invalid", p_s_curf, p_s_curcf);
1158
1159         return CARRY_ON;
1160 }
1161
1162 /* it is possible to remove node as result of shiftings to
1163    neighbors even when we insert or paste item. */
1164 static inline int can_node_be_removed(int mode, int lfree, int sfree, int rfree,
1165                                       struct tree_balance *tb, int h)
1166 {
1167         struct buffer_head *Sh = PATH_H_PBUFFER(tb->tb_path, h);
1168         int levbytes = tb->insert_size[h];
1169         struct item_head *ih;
1170         struct reiserfs_key *r_key = NULL;
1171
1172         ih = B_N_PITEM_HEAD(Sh, 0);
1173         if (tb->CFR[h])
1174                 r_key = B_N_PDELIM_KEY(tb->CFR[h], tb->rkey[h]);
1175
1176         if (lfree + rfree + sfree < MAX_CHILD_SIZE(Sh) + levbytes
1177             /* shifting may merge items which might save space */
1178             -
1179             ((!h
1180               && op_is_left_mergeable(&(ih->ih_key), Sh->b_size)) ? IH_SIZE : 0)
1181             -
1182             ((!h && r_key
1183               && op_is_left_mergeable(r_key, Sh->b_size)) ? IH_SIZE : 0)
1184             + ((h) ? KEY_SIZE : 0)) {
1185                 /* node can not be removed */
1186                 if (sfree >= levbytes) {        /* new item fits into node S[h] without any shifting */
1187                         if (!h)
1188                                 tb->s0num =
1189                                     B_NR_ITEMS(Sh) +
1190                                     ((mode == M_INSERT) ? 1 : 0);
1191                         set_parameters(tb, h, 0, 0, 1, NULL, -1, -1);
1192                         return NO_BALANCING_NEEDED;
1193                 }
1194         }
1195         PROC_INFO_INC(tb->tb_sb, can_node_be_removed[h]);
1196         return !NO_BALANCING_NEEDED;
1197 }
1198
1199 /* Check whether current node S[h] is balanced when increasing its size by
1200  * Inserting or Pasting.
1201  * Calculate parameters for balancing for current level h.
1202  * Parameters:
1203  *      tb      tree_balance structure;
1204  *      h       current level of the node;
1205  *      inum    item number in S[h];
1206  *      mode    i - insert, p - paste;
1207  * Returns:     1 - schedule occurred;
1208  *              0 - balancing for higher levels needed;
1209  *             -1 - no balancing for higher levels needed;
1210  *             -2 - no disk space.
1211  */
1212 /* ip means Inserting or Pasting */
1213 static int ip_check_balance(struct tree_balance *tb, int h)
1214 {
1215         struct virtual_node *vn = tb->tb_vn;
1216         int levbytes,           /* Number of bytes that must be inserted into (value
1217                                    is negative if bytes are deleted) buffer which
1218                                    contains node being balanced.  The mnemonic is
1219                                    that the attempted change in node space used level
1220                                    is levbytes bytes. */
1221          n_ret_value;
1222
1223         int lfree, sfree, rfree /* free space in L, S and R */ ;
1224
1225         /* nver is short for number of vertixes, and lnver is the number if
1226            we shift to the left, rnver is the number if we shift to the
1227            right, and lrnver is the number if we shift in both directions.
1228            The goal is to minimize first the number of vertixes, and second,
1229            the number of vertixes whose contents are changed by shifting,
1230            and third the number of uncached vertixes whose contents are
1231            changed by shifting and must be read from disk.  */
1232         int nver, lnver, rnver, lrnver;
1233
1234         /* used at leaf level only, S0 = S[0] is the node being balanced,
1235            sInum [ I = 0,1,2 ] is the number of items that will
1236            remain in node SI after balancing.  S1 and S2 are new
1237            nodes that might be created. */
1238
1239         /* we perform 8 calls to get_num_ver().  For each call we calculate five parameters.
1240            where 4th parameter is s1bytes and 5th - s2bytes
1241          */
1242         short snum012[40] = { 0, };     /* s0num, s1num, s2num for 8 cases
1243                                            0,1 - do not shift and do not shift but bottle
1244                                            2 - shift only whole item to left
1245                                            3 - shift to left and bottle as much as possible
1246                                            4,5 - shift to right (whole items and as much as possible
1247                                            6,7 - shift to both directions (whole items and as much as possible)
1248                                          */
1249
1250         /* Sh is the node whose balance is currently being checked */
1251         struct buffer_head *Sh;
1252
1253         Sh = PATH_H_PBUFFER(tb->tb_path, h);
1254         levbytes = tb->insert_size[h];
1255
1256         /* Calculate balance parameters for creating new root. */
1257         if (!Sh) {
1258                 if (!h)
1259                         reiserfs_panic(tb->tb_sb, "vs-8210",
1260                                        "S[0] can not be 0");
1261                 switch (n_ret_value = get_empty_nodes(tb, h)) {
1262                 case CARRY_ON:
1263                         set_parameters(tb, h, 0, 0, 1, NULL, -1, -1);
1264                         return NO_BALANCING_NEEDED;     /* no balancing for higher levels needed */
1265
1266                 case NO_DISK_SPACE:
1267                 case REPEAT_SEARCH:
1268                         return n_ret_value;
1269                 default:
1270                         reiserfs_panic(tb->tb_sb, "vs-8215", "incorrect "
1271                                        "return value of get_empty_nodes");
1272                 }
1273         }
1274
1275         if ((n_ret_value = get_parents(tb, h)) != CARRY_ON)     /* get parents of S[h] neighbors. */
1276                 return n_ret_value;
1277
1278         sfree = B_FREE_SPACE(Sh);
1279
1280         /* get free space of neighbors */
1281         rfree = get_rfree(tb, h);
1282         lfree = get_lfree(tb, h);
1283
1284         if (can_node_be_removed(vn->vn_mode, lfree, sfree, rfree, tb, h) ==
1285             NO_BALANCING_NEEDED)
1286                 /* and new item fits into node S[h] without any shifting */
1287                 return NO_BALANCING_NEEDED;
1288
1289         create_virtual_node(tb, h);
1290
1291         /*
1292            determine maximal number of items we can shift to the left neighbor (in tb structure)
1293            and the maximal number of bytes that can flow to the left neighbor
1294            from the left most liquid item that cannot be shifted from S[0] entirely (returned value)
1295          */
1296         check_left(tb, h, lfree);
1297
1298         /*
1299            determine maximal number of items we can shift to the right neighbor (in tb structure)
1300            and the maximal number of bytes that can flow to the right neighbor
1301            from the right most liquid item that cannot be shifted from S[0] entirely (returned value)
1302          */
1303         check_right(tb, h, rfree);
1304
1305         /* all contents of internal node S[h] can be moved into its
1306            neighbors, S[h] will be removed after balancing */
1307         if (h && (tb->rnum[h] + tb->lnum[h] >= vn->vn_nr_item + 1)) {
1308                 int to_r;
1309
1310                 /* Since we are working on internal nodes, and our internal
1311                    nodes have fixed size entries, then we can balance by the
1312                    number of items rather than the space they consume.  In this
1313                    routine we set the left node equal to the right node,
1314                    allowing a difference of less than or equal to 1 child
1315                    pointer. */
1316                 to_r =
1317                     ((MAX_NR_KEY(Sh) << 1) + 2 - tb->lnum[h] - tb->rnum[h] +
1318                      vn->vn_nr_item + 1) / 2 - (MAX_NR_KEY(Sh) + 1 -
1319                                                 tb->rnum[h]);
1320                 set_parameters(tb, h, vn->vn_nr_item + 1 - to_r, to_r, 0, NULL,
1321                                -1, -1);
1322                 return CARRY_ON;
1323         }
1324
1325         /* this checks balance condition, that any two neighboring nodes can not fit in one node */
1326         RFALSE(h &&
1327                (tb->lnum[h] >= vn->vn_nr_item + 1 ||
1328                 tb->rnum[h] >= vn->vn_nr_item + 1),
1329                "vs-8220: tree is not balanced on internal level");
1330         RFALSE(!h && ((tb->lnum[h] >= vn->vn_nr_item && (tb->lbytes == -1)) ||
1331                       (tb->rnum[h] >= vn->vn_nr_item && (tb->rbytes == -1))),
1332                "vs-8225: tree is not balanced on leaf level");
1333
1334         /* all contents of S[0] can be moved into its neighbors
1335            S[0] will be removed after balancing. */
1336         if (!h && is_leaf_removable(tb))
1337                 return CARRY_ON;
1338
1339         /* why do we perform this check here rather than earlier??
1340            Answer: we can win 1 node in some cases above. Moreover we
1341            checked it above, when we checked, that S[0] is not removable
1342            in principle */
1343         if (sfree >= levbytes) {        /* new item fits into node S[h] without any shifting */
1344                 if (!h)
1345                         tb->s0num = vn->vn_nr_item;
1346                 set_parameters(tb, h, 0, 0, 1, NULL, -1, -1);
1347                 return NO_BALANCING_NEEDED;
1348         }
1349
1350         {
1351                 int lpar, rpar, nset, lset, rset, lrset;
1352                 /*
1353                  * regular overflowing of the node
1354                  */
1355
1356                 /* get_num_ver works in 2 modes (FLOW & NO_FLOW)
1357                    lpar, rpar - number of items we can shift to left/right neighbor (including splitting item)
1358                    nset, lset, rset, lrset - shows, whether flowing items give better packing
1359                  */
1360 #define FLOW 1
1361 #define NO_FLOW 0               /* do not any splitting */
1362
1363                 /* we choose one the following */
1364 #define NOTHING_SHIFT_NO_FLOW   0
1365 #define NOTHING_SHIFT_FLOW      5
1366 #define LEFT_SHIFT_NO_FLOW      10
1367 #define LEFT_SHIFT_FLOW         15
1368 #define RIGHT_SHIFT_NO_FLOW     20
1369 #define RIGHT_SHIFT_FLOW        25
1370 #define LR_SHIFT_NO_FLOW        30
1371 #define LR_SHIFT_FLOW           35
1372
1373                 lpar = tb->lnum[h];
1374                 rpar = tb->rnum[h];
1375
1376                 /* calculate number of blocks S[h] must be split into when
1377                    nothing is shifted to the neighbors,
1378                    as well as number of items in each part of the split node (s012 numbers),
1379                    and number of bytes (s1bytes) of the shared drop which flow to S1 if any */
1380                 nset = NOTHING_SHIFT_NO_FLOW;
1381                 nver = get_num_ver(vn->vn_mode, tb, h,
1382                                    0, -1, h ? vn->vn_nr_item : 0, -1,
1383                                    snum012, NO_FLOW);
1384
1385                 if (!h) {
1386                         int nver1;
1387
1388                         /* note, that in this case we try to bottle between S[0] and S1 (S1 - the first new node) */
1389                         nver1 = get_num_ver(vn->vn_mode, tb, h,
1390                                             0, -1, 0, -1,
1391                                             snum012 + NOTHING_SHIFT_FLOW, FLOW);
1392                         if (nver > nver1)
1393                                 nset = NOTHING_SHIFT_FLOW, nver = nver1;
1394                 }
1395
1396                 /* calculate number of blocks S[h] must be split into when
1397                    l_shift_num first items and l_shift_bytes of the right most
1398                    liquid item to be shifted are shifted to the left neighbor,
1399                    as well as number of items in each part of the splitted node (s012 numbers),
1400                    and number of bytes (s1bytes) of the shared drop which flow to S1 if any
1401                  */
1402                 lset = LEFT_SHIFT_NO_FLOW;
1403                 lnver = get_num_ver(vn->vn_mode, tb, h,
1404                                     lpar - ((h || tb->lbytes == -1) ? 0 : 1),
1405                                     -1, h ? vn->vn_nr_item : 0, -1,
1406                                     snum012 + LEFT_SHIFT_NO_FLOW, NO_FLOW);
1407                 if (!h) {
1408                         int lnver1;
1409
1410                         lnver1 = get_num_ver(vn->vn_mode, tb, h,
1411                                              lpar -
1412                                              ((tb->lbytes != -1) ? 1 : 0),
1413                                              tb->lbytes, 0, -1,
1414                                              snum012 + LEFT_SHIFT_FLOW, FLOW);
1415                         if (lnver > lnver1)
1416                                 lset = LEFT_SHIFT_FLOW, lnver = lnver1;
1417                 }
1418
1419                 /* calculate number of blocks S[h] must be split into when
1420                    r_shift_num first items and r_shift_bytes of the left most
1421                    liquid item to be shifted are shifted to the right neighbor,
1422                    as well as number of items in each part of the splitted node (s012 numbers),
1423                    and number of bytes (s1bytes) of the shared drop which flow to S1 if any
1424                  */
1425                 rset = RIGHT_SHIFT_NO_FLOW;
1426                 rnver = get_num_ver(vn->vn_mode, tb, h,
1427                                     0, -1,
1428                                     h ? (vn->vn_nr_item - rpar) : (rpar -
1429                                                                    ((tb->
1430                                                                      rbytes !=
1431                                                                      -1) ? 1 :
1432                                                                     0)), -1,
1433                                     snum012 + RIGHT_SHIFT_NO_FLOW, NO_FLOW);
1434                 if (!h) {
1435                         int rnver1;
1436
1437                         rnver1 = get_num_ver(vn->vn_mode, tb, h,
1438                                              0, -1,
1439                                              (rpar -
1440                                               ((tb->rbytes != -1) ? 1 : 0)),
1441                                              tb->rbytes,
1442                                              snum012 + RIGHT_SHIFT_FLOW, FLOW);
1443
1444                         if (rnver > rnver1)
1445                                 rset = RIGHT_SHIFT_FLOW, rnver = rnver1;
1446                 }
1447
1448                 /* calculate number of blocks S[h] must be split into when
1449                    items are shifted in both directions,
1450                    as well as number of items in each part of the splitted node (s012 numbers),
1451                    and number of bytes (s1bytes) of the shared drop which flow to S1 if any
1452                  */
1453                 lrset = LR_SHIFT_NO_FLOW;
1454                 lrnver = get_num_ver(vn->vn_mode, tb, h,
1455                                      lpar - ((h || tb->lbytes == -1) ? 0 : 1),
1456                                      -1,
1457                                      h ? (vn->vn_nr_item - rpar) : (rpar -
1458                                                                     ((tb->
1459                                                                       rbytes !=
1460                                                                       -1) ? 1 :
1461                                                                      0)), -1,
1462                                      snum012 + LR_SHIFT_NO_FLOW, NO_FLOW);
1463                 if (!h) {
1464                         int lrnver1;
1465
1466                         lrnver1 = get_num_ver(vn->vn_mode, tb, h,
1467                                               lpar -
1468                                               ((tb->lbytes != -1) ? 1 : 0),
1469                                               tb->lbytes,
1470                                               (rpar -
1471                                                ((tb->rbytes != -1) ? 1 : 0)),
1472                                               tb->rbytes,
1473                                               snum012 + LR_SHIFT_FLOW, FLOW);
1474                         if (lrnver > lrnver1)
1475                                 lrset = LR_SHIFT_FLOW, lrnver = lrnver1;
1476                 }
1477
1478                 /* Our general shifting strategy is:
1479                    1) to minimized number of new nodes;
1480                    2) to minimized number of neighbors involved in shifting;
1481                    3) to minimized number of disk reads; */
1482
1483                 /* we can win TWO or ONE nodes by shifting in both directions */
1484                 if (lrnver < lnver && lrnver < rnver) {
1485                         RFALSE(h &&
1486                                (tb->lnum[h] != 1 ||
1487                                 tb->rnum[h] != 1 ||
1488                                 lrnver != 1 || rnver != 2 || lnver != 2
1489                                 || h != 1), "vs-8230: bad h");
1490                         if (lrset == LR_SHIFT_FLOW)
1491                                 set_parameters(tb, h, tb->lnum[h], tb->rnum[h],
1492                                                lrnver, snum012 + lrset,
1493                                                tb->lbytes, tb->rbytes);
1494                         else
1495                                 set_parameters(tb, h,
1496                                                tb->lnum[h] -
1497                                                ((tb->lbytes == -1) ? 0 : 1),
1498                                                tb->rnum[h] -
1499                                                ((tb->rbytes == -1) ? 0 : 1),
1500                                                lrnver, snum012 + lrset, -1, -1);
1501
1502                         return CARRY_ON;
1503                 }
1504
1505                 /* if shifting doesn't lead to better packing then don't shift */
1506                 if (nver == lrnver) {
1507                         set_parameters(tb, h, 0, 0, nver, snum012 + nset, -1,
1508                                        -1);
1509                         return CARRY_ON;
1510                 }
1511
1512                 /* now we know that for better packing shifting in only one
1513                    direction either to the left or to the right is required */
1514
1515                 /*  if shifting to the left is better than shifting to the right */
1516                 if (lnver < rnver) {
1517                         SET_PAR_SHIFT_LEFT;
1518                         return CARRY_ON;
1519                 }
1520
1521                 /* if shifting to the right is better than shifting to the left */
1522                 if (lnver > rnver) {
1523                         SET_PAR_SHIFT_RIGHT;
1524                         return CARRY_ON;
1525                 }
1526
1527                 /* now shifting in either direction gives the same number
1528                    of nodes and we can make use of the cached neighbors */
1529                 if (is_left_neighbor_in_cache(tb, h)) {
1530                         SET_PAR_SHIFT_LEFT;
1531                         return CARRY_ON;
1532                 }
1533
1534                 /* shift to the right independently on whether the right neighbor in cache or not */
1535                 SET_PAR_SHIFT_RIGHT;
1536                 return CARRY_ON;
1537         }
1538 }
1539
1540 /* Check whether current node S[h] is balanced when Decreasing its size by
1541  * Deleting or Cutting for INTERNAL node of S+tree.
1542  * Calculate parameters for balancing for current level h.
1543  * Parameters:
1544  *      tb      tree_balance structure;
1545  *      h       current level of the node;
1546  *      inum    item number in S[h];
1547  *      mode    i - insert, p - paste;
1548  * Returns:     1 - schedule occurred;
1549  *              0 - balancing for higher levels needed;
1550  *             -1 - no balancing for higher levels needed;
1551  *             -2 - no disk space.
1552  *
1553  * Note: Items of internal nodes have fixed size, so the balance condition for
1554  * the internal part of S+tree is as for the B-trees.
1555  */
1556 static int dc_check_balance_internal(struct tree_balance *tb, int h)
1557 {
1558         struct virtual_node *vn = tb->tb_vn;
1559
1560         /* Sh is the node whose balance is currently being checked,
1561            and Fh is its father.  */
1562         struct buffer_head *Sh, *Fh;
1563         int maxsize, n_ret_value;
1564         int lfree, rfree /* free space in L and R */ ;
1565
1566         Sh = PATH_H_PBUFFER(tb->tb_path, h);
1567         Fh = PATH_H_PPARENT(tb->tb_path, h);
1568
1569         maxsize = MAX_CHILD_SIZE(Sh);
1570
1571 /*   using tb->insert_size[h], which is negative in this case, create_virtual_node calculates: */
1572 /*   new_nr_item = number of items node would have if operation is */
1573 /*      performed without balancing (new_nr_item); */
1574         create_virtual_node(tb, h);
1575
1576         if (!Fh) {              /* S[h] is the root. */
1577                 if (vn->vn_nr_item > 0) {
1578                         set_parameters(tb, h, 0, 0, 1, NULL, -1, -1);
1579                         return NO_BALANCING_NEEDED;     /* no balancing for higher levels needed */
1580                 }
1581                 /* new_nr_item == 0.
1582                  * Current root will be deleted resulting in
1583                  * decrementing the tree height. */
1584                 set_parameters(tb, h, 0, 0, 0, NULL, -1, -1);
1585                 return CARRY_ON;
1586         }
1587
1588         if ((n_ret_value = get_parents(tb, h)) != CARRY_ON)
1589                 return n_ret_value;
1590
1591         /* get free space of neighbors */
1592         rfree = get_rfree(tb, h);
1593         lfree = get_lfree(tb, h);
1594
1595         /* determine maximal number of items we can fit into neighbors */
1596         check_left(tb, h, lfree);
1597         check_right(tb, h, rfree);
1598
1599         if (vn->vn_nr_item >= MIN_NR_KEY(Sh)) { /* Balance condition for the internal node is valid.
1600                                                  * In this case we balance only if it leads to better packing. */
1601                 if (vn->vn_nr_item == MIN_NR_KEY(Sh)) { /* Here we join S[h] with one of its neighbors,
1602                                                          * which is impossible with greater values of new_nr_item. */
1603                         if (tb->lnum[h] >= vn->vn_nr_item + 1) {
1604                                 /* All contents of S[h] can be moved to L[h]. */
1605                                 int n;
1606                                 int order_L;
1607
1608                                 order_L =
1609                                     ((n =
1610                                       PATH_H_B_ITEM_ORDER(tb->tb_path,
1611                                                           h)) ==
1612                                      0) ? B_NR_ITEMS(tb->FL[h]) : n - 1;
1613                                 n = dc_size(B_N_CHILD(tb->FL[h], order_L)) /
1614                                     (DC_SIZE + KEY_SIZE);
1615                                 set_parameters(tb, h, -n - 1, 0, 0, NULL, -1,
1616                                                -1);
1617                                 return CARRY_ON;
1618                         }
1619
1620                         if (tb->rnum[h] >= vn->vn_nr_item + 1) {
1621                                 /* All contents of S[h] can be moved to R[h]. */
1622                                 int n;
1623                                 int order_R;
1624
1625                                 order_R =
1626                                     ((n =
1627                                       PATH_H_B_ITEM_ORDER(tb->tb_path,
1628                                                           h)) ==
1629                                      B_NR_ITEMS(Fh)) ? 0 : n + 1;
1630                                 n = dc_size(B_N_CHILD(tb->FR[h], order_R)) /
1631                                     (DC_SIZE + KEY_SIZE);
1632                                 set_parameters(tb, h, 0, -n - 1, 0, NULL, -1,
1633                                                -1);
1634                                 return CARRY_ON;
1635                         }
1636                 }
1637
1638                 if (tb->rnum[h] + tb->lnum[h] >= vn->vn_nr_item + 1) {
1639                         /* All contents of S[h] can be moved to the neighbors (L[h] & R[h]). */
1640                         int to_r;
1641
1642                         to_r =
1643                             ((MAX_NR_KEY(Sh) << 1) + 2 - tb->lnum[h] -
1644                              tb->rnum[h] + vn->vn_nr_item + 1) / 2 -
1645                             (MAX_NR_KEY(Sh) + 1 - tb->rnum[h]);
1646                         set_parameters(tb, h, vn->vn_nr_item + 1 - to_r, to_r,
1647                                        0, NULL, -1, -1);
1648                         return CARRY_ON;
1649                 }
1650
1651                 /* Balancing does not lead to better packing. */
1652                 set_parameters(tb, h, 0, 0, 1, NULL, -1, -1);
1653                 return NO_BALANCING_NEEDED;
1654         }
1655
1656         /* Current node contain insufficient number of items. Balancing is required. */
1657         /* Check whether we can merge S[h] with left neighbor. */
1658         if (tb->lnum[h] >= vn->vn_nr_item + 1)
1659                 if (is_left_neighbor_in_cache(tb, h)
1660                     || tb->rnum[h] < vn->vn_nr_item + 1 || !tb->FR[h]) {
1661                         int n;
1662                         int order_L;
1663
1664                         order_L =
1665                             ((n =
1666                               PATH_H_B_ITEM_ORDER(tb->tb_path,
1667                                                   h)) ==
1668                              0) ? B_NR_ITEMS(tb->FL[h]) : n - 1;
1669                         n = dc_size(B_N_CHILD(tb->FL[h], order_L)) / (DC_SIZE +
1670                                                                       KEY_SIZE);
1671                         set_parameters(tb, h, -n - 1, 0, 0, NULL, -1, -1);
1672                         return CARRY_ON;
1673                 }
1674
1675         /* Check whether we can merge S[h] with right neighbor. */
1676         if (tb->rnum[h] >= vn->vn_nr_item + 1) {
1677                 int n;
1678                 int order_R;
1679
1680                 order_R =
1681                     ((n =
1682                       PATH_H_B_ITEM_ORDER(tb->tb_path,
1683                                           h)) == B_NR_ITEMS(Fh)) ? 0 : (n + 1);
1684                 n = dc_size(B_N_CHILD(tb->FR[h], order_R)) / (DC_SIZE +
1685                                                               KEY_SIZE);
1686                 set_parameters(tb, h, 0, -n - 1, 0, NULL, -1, -1);
1687                 return CARRY_ON;
1688         }
1689
1690         /* All contents of S[h] can be moved to the neighbors (L[h] & R[h]). */
1691         if (tb->rnum[h] + tb->lnum[h] >= vn->vn_nr_item + 1) {
1692                 int to_r;
1693
1694                 to_r =
1695                     ((MAX_NR_KEY(Sh) << 1) + 2 - tb->lnum[h] - tb->rnum[h] +
1696                      vn->vn_nr_item + 1) / 2 - (MAX_NR_KEY(Sh) + 1 -
1697                                                 tb->rnum[h]);
1698                 set_parameters(tb, h, vn->vn_nr_item + 1 - to_r, to_r, 0, NULL,
1699                                -1, -1);
1700                 return CARRY_ON;
1701         }
1702
1703         /* For internal nodes try to borrow item from a neighbor */
1704         RFALSE(!tb->FL[h] && !tb->FR[h], "vs-8235: trying to borrow for root");
1705
1706         /* Borrow one or two items from caching neighbor */
1707         if (is_left_neighbor_in_cache(tb, h) || !tb->FR[h]) {
1708                 int from_l;
1709
1710                 from_l =
1711                     (MAX_NR_KEY(Sh) + 1 - tb->lnum[h] + vn->vn_nr_item +
1712                      1) / 2 - (vn->vn_nr_item + 1);
1713                 set_parameters(tb, h, -from_l, 0, 1, NULL, -1, -1);
1714                 return CARRY_ON;
1715         }
1716
1717         set_parameters(tb, h, 0,
1718                        -((MAX_NR_KEY(Sh) + 1 - tb->rnum[h] + vn->vn_nr_item +
1719                           1) / 2 - (vn->vn_nr_item + 1)), 1, NULL, -1, -1);
1720         return CARRY_ON;
1721 }
1722
1723 /* Check whether current node S[h] is balanced when Decreasing its size by
1724  * Deleting or Truncating for LEAF node of S+tree.
1725  * Calculate parameters for balancing for current level h.
1726  * Parameters:
1727  *      tb      tree_balance structure;
1728  *      h       current level of the node;
1729  *      inum    item number in S[h];
1730  *      mode    i - insert, p - paste;
1731  * Returns:     1 - schedule occurred;
1732  *              0 - balancing for higher levels needed;
1733  *             -1 - no balancing for higher levels needed;
1734  *             -2 - no disk space.
1735  */
1736 static int dc_check_balance_leaf(struct tree_balance *tb, int h)
1737 {
1738         struct virtual_node *vn = tb->tb_vn;
1739
1740         /* Number of bytes that must be deleted from
1741            (value is negative if bytes are deleted) buffer which
1742            contains node being balanced.  The mnemonic is that the
1743            attempted change in node space used level is levbytes bytes. */
1744         int levbytes;
1745         /* the maximal item size */
1746         int maxsize, n_ret_value;
1747         /* S0 is the node whose balance is currently being checked,
1748            and F0 is its father.  */
1749         struct buffer_head *S0, *F0;
1750         int lfree, rfree /* free space in L and R */ ;
1751
1752         S0 = PATH_H_PBUFFER(tb->tb_path, 0);
1753         F0 = PATH_H_PPARENT(tb->tb_path, 0);
1754
1755         levbytes = tb->insert_size[h];
1756
1757         maxsize = MAX_CHILD_SIZE(S0);   /* maximal possible size of an item */
1758
1759         if (!F0) {              /* S[0] is the root now. */
1760
1761                 RFALSE(-levbytes >= maxsize - B_FREE_SPACE(S0),
1762                        "vs-8240: attempt to create empty buffer tree");
1763
1764                 set_parameters(tb, h, 0, 0, 1, NULL, -1, -1);
1765                 return NO_BALANCING_NEEDED;
1766         }
1767
1768         if ((n_ret_value = get_parents(tb, h)) != CARRY_ON)
1769                 return n_ret_value;
1770
1771         /* get free space of neighbors */
1772         rfree = get_rfree(tb, h);
1773         lfree = get_lfree(tb, h);
1774
1775         create_virtual_node(tb, h);
1776
1777         /* if 3 leaves can be merge to one, set parameters and return */
1778         if (are_leaves_removable(tb, lfree, rfree))
1779                 return CARRY_ON;
1780
1781         /* determine maximal number of items we can shift to the left/right  neighbor
1782            and the maximal number of bytes that can flow to the left/right neighbor
1783            from the left/right most liquid item that cannot be shifted from S[0] entirely
1784          */
1785         check_left(tb, h, lfree);
1786         check_right(tb, h, rfree);
1787
1788         /* check whether we can merge S with left neighbor. */
1789         if (tb->lnum[0] >= vn->vn_nr_item && tb->lbytes == -1)
1790                 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 */
1791                     !tb->FR[h]) {
1792
1793                         RFALSE(!tb->FL[h],
1794                                "vs-8245: dc_check_balance_leaf: FL[h] must exist");
1795
1796                         /* set parameter to merge S[0] with its left neighbor */
1797                         set_parameters(tb, h, -1, 0, 0, NULL, -1, -1);
1798                         return CARRY_ON;
1799                 }
1800
1801         /* check whether we can merge S[0] with right neighbor. */
1802         if (tb->rnum[0] >= vn->vn_nr_item && tb->rbytes == -1) {
1803                 set_parameters(tb, h, 0, -1, 0, NULL, -1, -1);
1804                 return CARRY_ON;
1805         }
1806
1807         /* All contents of S[0] can be moved to the neighbors (L[0] & R[0]). Set parameters and return */
1808         if (is_leaf_removable(tb))
1809                 return CARRY_ON;
1810
1811         /* Balancing is not required. */
1812         tb->s0num = vn->vn_nr_item;
1813         set_parameters(tb, h, 0, 0, 1, NULL, -1, -1);
1814         return NO_BALANCING_NEEDED;
1815 }
1816
1817 /* Check whether current node S[h] is balanced when Decreasing its size by
1818  * Deleting or Cutting.
1819  * Calculate parameters for balancing for current level h.
1820  * Parameters:
1821  *      tb      tree_balance structure;
1822  *      h       current level of the node;
1823  *      inum    item number in S[h];
1824  *      mode    d - delete, c - cut.
1825  * Returns:     1 - schedule occurred;
1826  *              0 - balancing for higher levels needed;
1827  *             -1 - no balancing for higher levels needed;
1828  *             -2 - no disk space.
1829  */
1830 static int dc_check_balance(struct tree_balance *tb, int h)
1831 {
1832         RFALSE(!(PATH_H_PBUFFER(tb->tb_path, h)),
1833                "vs-8250: S is not initialized");
1834
1835         if (h)
1836                 return dc_check_balance_internal(tb, h);
1837         else
1838                 return dc_check_balance_leaf(tb, h);
1839 }
1840
1841 /* Check whether current node S[h] is balanced.
1842  * Calculate parameters for balancing for current level h.
1843  * Parameters:
1844  *
1845  *      tb      tree_balance structure:
1846  *
1847  *              tb is a large structure that must be read about in the header file
1848  *              at the same time as this procedure if the reader is to successfully
1849  *              understand this procedure
1850  *
1851  *      h       current level of the node;
1852  *      inum    item number in S[h];
1853  *      mode    i - insert, p - paste, d - delete, c - cut.
1854  * Returns:     1 - schedule occurred;
1855  *              0 - balancing for higher levels needed;
1856  *             -1 - no balancing for higher levels needed;
1857  *             -2 - no disk space.
1858  */
1859 static int check_balance(int mode,
1860                          struct tree_balance *tb,
1861                          int h,
1862                          int inum,
1863                          int pos_in_item,
1864                          struct item_head *ins_ih, const void *data)
1865 {
1866         struct virtual_node *vn;
1867
1868         vn = tb->tb_vn = (struct virtual_node *)(tb->vn_buf);
1869         vn->vn_free_ptr = (char *)(tb->tb_vn + 1);
1870         vn->vn_mode = mode;
1871         vn->vn_affected_item_num = inum;
1872         vn->vn_pos_in_item = pos_in_item;
1873         vn->vn_ins_ih = ins_ih;
1874         vn->vn_data = data;
1875
1876         RFALSE(mode == M_INSERT && !vn->vn_ins_ih,
1877                "vs-8255: ins_ih can not be 0 in insert mode");
1878
1879         if (tb->insert_size[h] > 0)
1880                 /* Calculate balance parameters when size of node is increasing. */
1881                 return ip_check_balance(tb, h);
1882
1883         /* Calculate balance parameters when  size of node is decreasing. */
1884         return dc_check_balance(tb, h);
1885 }
1886
1887 /* Check whether parent at the path is the really parent of the current node.*/
1888 static int get_direct_parent(struct tree_balance *p_s_tb, int n_h)
1889 {
1890         struct buffer_head *p_s_bh;
1891         struct treepath *p_s_path = p_s_tb->tb_path;
1892         int n_position,
1893             n_path_offset = PATH_H_PATH_OFFSET(p_s_tb->tb_path, n_h);
1894
1895         /* We are in the root or in the new root. */
1896         if (n_path_offset <= FIRST_PATH_ELEMENT_OFFSET) {
1897
1898                 RFALSE(n_path_offset < FIRST_PATH_ELEMENT_OFFSET - 1,
1899                        "PAP-8260: invalid offset in the path");
1900
1901                 if (PATH_OFFSET_PBUFFER(p_s_path, FIRST_PATH_ELEMENT_OFFSET)->
1902                     b_blocknr == SB_ROOT_BLOCK(p_s_tb->tb_sb)) {
1903                         /* Root is not changed. */
1904                         PATH_OFFSET_PBUFFER(p_s_path, n_path_offset - 1) = NULL;
1905                         PATH_OFFSET_POSITION(p_s_path, n_path_offset - 1) = 0;
1906                         return CARRY_ON;
1907                 }
1908                 return REPEAT_SEARCH;   /* Root is changed and we must recalculate the path. */
1909         }
1910
1911         if (!B_IS_IN_TREE
1912             (p_s_bh = PATH_OFFSET_PBUFFER(p_s_path, n_path_offset - 1)))
1913                 return REPEAT_SEARCH;   /* Parent in the path is not in the tree. */
1914
1915         if ((n_position =
1916              PATH_OFFSET_POSITION(p_s_path,
1917                                   n_path_offset - 1)) > B_NR_ITEMS(p_s_bh))
1918                 return REPEAT_SEARCH;
1919
1920         if (B_N_CHILD_NUM(p_s_bh, n_position) !=
1921             PATH_OFFSET_PBUFFER(p_s_path, n_path_offset)->b_blocknr)
1922                 /* Parent in the path is not parent of the current node in the tree. */
1923                 return REPEAT_SEARCH;
1924
1925         if (buffer_locked(p_s_bh)) {
1926                 __wait_on_buffer(p_s_bh);
1927                 if (FILESYSTEM_CHANGED_TB(p_s_tb))
1928                         return REPEAT_SEARCH;
1929         }
1930
1931         return CARRY_ON;        /* Parent in the path is unlocked and really parent of the current node.  */
1932 }
1933
1934 /* Using lnum[n_h] and rnum[n_h] we should determine what neighbors
1935  * of S[n_h] we
1936  * need in order to balance S[n_h], and get them if necessary.
1937  * Returns:     SCHEDULE_OCCURRED - schedule occurred while the function worked;
1938  *              CARRY_ON - schedule didn't occur while the function worked;
1939  */
1940 static int get_neighbors(struct tree_balance *p_s_tb, int n_h)
1941 {
1942         int n_child_position,
1943             n_path_offset = PATH_H_PATH_OFFSET(p_s_tb->tb_path, n_h + 1);
1944         unsigned long n_son_number;
1945         struct super_block *sb = p_s_tb->tb_sb;
1946         struct buffer_head *p_s_bh;
1947
1948         PROC_INFO_INC(sb, get_neighbors[n_h]);
1949
1950         if (p_s_tb->lnum[n_h]) {
1951                 /* We need left neighbor to balance S[n_h]. */
1952                 PROC_INFO_INC(sb, need_l_neighbor[n_h]);
1953                 p_s_bh = PATH_OFFSET_PBUFFER(p_s_tb->tb_path, n_path_offset);
1954
1955                 RFALSE(p_s_bh == p_s_tb->FL[n_h] &&
1956                        !PATH_OFFSET_POSITION(p_s_tb->tb_path, n_path_offset),
1957                        "PAP-8270: invalid position in the parent");
1958
1959                 n_child_position =
1960                     (p_s_bh ==
1961                      p_s_tb->FL[n_h]) ? p_s_tb->lkey[n_h] : B_NR_ITEMS(p_s_tb->
1962                                                                        FL[n_h]);
1963                 n_son_number = B_N_CHILD_NUM(p_s_tb->FL[n_h], n_child_position);
1964                 p_s_bh = sb_bread(sb, n_son_number);
1965                 if (!p_s_bh)
1966                         return IO_ERROR;
1967                 if (FILESYSTEM_CHANGED_TB(p_s_tb)) {
1968                         brelse(p_s_bh);
1969                         PROC_INFO_INC(sb, get_neighbors_restart[n_h]);
1970                         return REPEAT_SEARCH;
1971                 }
1972
1973                 RFALSE(!B_IS_IN_TREE(p_s_tb->FL[n_h]) ||
1974                        n_child_position > B_NR_ITEMS(p_s_tb->FL[n_h]) ||
1975                        B_N_CHILD_NUM(p_s_tb->FL[n_h], n_child_position) !=
1976                        p_s_bh->b_blocknr, "PAP-8275: invalid parent");
1977                 RFALSE(!B_IS_IN_TREE(p_s_bh), "PAP-8280: invalid child");
1978                 RFALSE(!n_h &&
1979                        B_FREE_SPACE(p_s_bh) !=
1980                        MAX_CHILD_SIZE(p_s_bh) -
1981                        dc_size(B_N_CHILD(p_s_tb->FL[0], n_child_position)),
1982                        "PAP-8290: invalid child size of left neighbor");
1983
1984                 brelse(p_s_tb->L[n_h]);
1985                 p_s_tb->L[n_h] = p_s_bh;
1986         }
1987
1988         if (p_s_tb->rnum[n_h]) {        /* We need right neighbor to balance S[n_path_offset]. */
1989                 PROC_INFO_INC(sb, need_r_neighbor[n_h]);
1990                 p_s_bh = PATH_OFFSET_PBUFFER(p_s_tb->tb_path, n_path_offset);
1991
1992                 RFALSE(p_s_bh == p_s_tb->FR[n_h] &&
1993                        PATH_OFFSET_POSITION(p_s_tb->tb_path,
1994                                             n_path_offset) >=
1995                        B_NR_ITEMS(p_s_bh),
1996                        "PAP-8295: invalid position in the parent");
1997
1998                 n_child_position =
1999                     (p_s_bh == p_s_tb->FR[n_h]) ? p_s_tb->rkey[n_h] + 1 : 0;
2000                 n_son_number = B_N_CHILD_NUM(p_s_tb->FR[n_h], n_child_position);
2001                 p_s_bh = sb_bread(sb, n_son_number);
2002                 if (!p_s_bh)
2003                         return IO_ERROR;
2004                 if (FILESYSTEM_CHANGED_TB(p_s_tb)) {
2005                         brelse(p_s_bh);
2006                         PROC_INFO_INC(sb, get_neighbors_restart[n_h]);
2007                         return REPEAT_SEARCH;
2008                 }
2009                 brelse(p_s_tb->R[n_h]);
2010                 p_s_tb->R[n_h] = p_s_bh;
2011
2012                 RFALSE(!n_h
2013                        && B_FREE_SPACE(p_s_bh) !=
2014                        MAX_CHILD_SIZE(p_s_bh) -
2015                        dc_size(B_N_CHILD(p_s_tb->FR[0], n_child_position)),
2016                        "PAP-8300: invalid child size of right neighbor (%d != %d - %d)",
2017                        B_FREE_SPACE(p_s_bh), MAX_CHILD_SIZE(p_s_bh),
2018                        dc_size(B_N_CHILD(p_s_tb->FR[0], n_child_position)));
2019
2020         }
2021         return CARRY_ON;
2022 }
2023
2024 static int get_virtual_node_size(struct super_block *sb, struct buffer_head *bh)
2025 {
2026         int max_num_of_items;
2027         int max_num_of_entries;
2028         unsigned long blocksize = sb->s_blocksize;
2029
2030 #define MIN_NAME_LEN 1
2031
2032         max_num_of_items = (blocksize - BLKH_SIZE) / (IH_SIZE + MIN_ITEM_LEN);
2033         max_num_of_entries = (blocksize - BLKH_SIZE - IH_SIZE) /
2034             (DEH_SIZE + MIN_NAME_LEN);
2035
2036         return sizeof(struct virtual_node) +
2037             max(max_num_of_items * sizeof(struct virtual_item),
2038                 sizeof(struct virtual_item) + sizeof(struct direntry_uarea) +
2039                 (max_num_of_entries - 1) * sizeof(__u16));
2040 }
2041
2042 /* maybe we should fail balancing we are going to perform when kmalloc
2043    fails several times. But now it will loop until kmalloc gets
2044    required memory */
2045 static int get_mem_for_virtual_node(struct tree_balance *tb)
2046 {
2047         int check_fs = 0;
2048         int size;
2049         char *buf;
2050
2051         size = get_virtual_node_size(tb->tb_sb, PATH_PLAST_BUFFER(tb->tb_path));
2052
2053         if (size > tb->vn_buf_size) {
2054                 /* we have to allocate more memory for virtual node */
2055                 if (tb->vn_buf) {
2056                         /* free memory allocated before */
2057                         kfree(tb->vn_buf);
2058                         /* this is not needed if kfree is atomic */
2059                         check_fs = 1;
2060                 }
2061
2062                 /* virtual node requires now more memory */
2063                 tb->vn_buf_size = size;
2064
2065                 /* get memory for virtual item */
2066                 buf = kmalloc(size, GFP_ATOMIC | __GFP_NOWARN);
2067                 if (!buf) {
2068                         /* getting memory with GFP_KERNEL priority may involve
2069                            balancing now (due to indirect_to_direct conversion on
2070                            dcache shrinking). So, release path and collected
2071                            resources here */
2072                         free_buffers_in_tb(tb);
2073                         buf = kmalloc(size, GFP_NOFS);
2074                         if (!buf) {
2075                                 tb->vn_buf_size = 0;
2076                         }
2077                         tb->vn_buf = buf;
2078                         schedule();
2079                         return REPEAT_SEARCH;
2080                 }
2081
2082                 tb->vn_buf = buf;
2083         }
2084
2085         if (check_fs && FILESYSTEM_CHANGED_TB(tb))
2086                 return REPEAT_SEARCH;
2087
2088         return CARRY_ON;
2089 }
2090
2091 #ifdef CONFIG_REISERFS_CHECK
2092 static void tb_buffer_sanity_check(struct super_block *sb,
2093                                    struct buffer_head *p_s_bh,
2094                                    const char *descr, int level)
2095 {
2096         if (p_s_bh) {
2097                 if (atomic_read(&(p_s_bh->b_count)) <= 0) {
2098
2099                         reiserfs_panic(sb, "jmacd-1", "negative or zero "
2100                                        "reference counter for buffer %s[%d] "
2101                                        "(%b)", descr, level, p_s_bh);
2102                 }
2103
2104                 if (!buffer_uptodate(p_s_bh)) {
2105                         reiserfs_panic(sb, "jmacd-2", "buffer is not up "
2106                                        "to date %s[%d] (%b)",
2107                                        descr, level, p_s_bh);
2108                 }
2109
2110                 if (!B_IS_IN_TREE(p_s_bh)) {
2111                         reiserfs_panic(sb, "jmacd-3", "buffer is not "
2112                                        "in tree %s[%d] (%b)",
2113                                        descr, level, p_s_bh);
2114                 }
2115
2116                 if (p_s_bh->b_bdev != sb->s_bdev) {
2117                         reiserfs_panic(sb, "jmacd-4", "buffer has wrong "
2118                                        "device %s[%d] (%b)",
2119                                        descr, level, p_s_bh);
2120                 }
2121
2122                 if (p_s_bh->b_size != sb->s_blocksize) {
2123                         reiserfs_panic(sb, "jmacd-5", "buffer has wrong "
2124                                        "blocksize %s[%d] (%b)",
2125                                        descr, level, p_s_bh);
2126                 }
2127
2128                 if (p_s_bh->b_blocknr > SB_BLOCK_COUNT(sb)) {
2129                         reiserfs_panic(sb, "jmacd-6", "buffer block "
2130                                        "number too high %s[%d] (%b)",
2131                                        descr, level, p_s_bh);
2132                 }
2133         }
2134 }
2135 #else
2136 static void tb_buffer_sanity_check(struct super_block *sb,
2137                                    struct buffer_head *p_s_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 *p_s_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 = p_s_tb->tb_path->path_length;
2161                      !locked && i > ILLEGAL_PATH_ELEMENT_OFFSET; i--) {
2162                         if (PATH_OFFSET_PBUFFER(p_s_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(p_s_tb->tb_path) ==
2168                                     PATH_OFFSET_PBUFFER(p_s_tb->tb_path, i)) {
2169                                         tb_buffer_sanity_check(p_s_tb->tb_sb,
2170                                                                PATH_OFFSET_PBUFFER
2171                                                                (p_s_tb->tb_path,
2172                                                                 i), "S",
2173                                                                p_s_tb->tb_path->
2174                                                                path_length - i);
2175                                 }
2176 #endif
2177                                 if (!clear_all_dirty_bits(p_s_tb->tb_sb,
2178                                                           PATH_OFFSET_PBUFFER
2179                                                           (p_s_tb->tb_path,
2180                                                            i))) {
2181                                         locked =
2182                                             PATH_OFFSET_PBUFFER(p_s_tb->tb_path,
2183                                                                 i);
2184                                 }
2185                         }
2186                 }
2187
2188                 for (i = 0; !locked && i < MAX_HEIGHT && p_s_tb->insert_size[i];
2189                      i++) {
2190
2191                         if (p_s_tb->lnum[i]) {
2192
2193                                 if (p_s_tb->L[i]) {
2194                                         tb_buffer_sanity_check(p_s_tb->tb_sb,
2195                                                                p_s_tb->L[i],
2196                                                                "L", i);
2197                                         if (!clear_all_dirty_bits
2198                                             (p_s_tb->tb_sb, p_s_tb->L[i]))
2199                                                 locked = p_s_tb->L[i];
2200                                 }
2201
2202                                 if (!locked && p_s_tb->FL[i]) {
2203                                         tb_buffer_sanity_check(p_s_tb->tb_sb,
2204                                                                p_s_tb->FL[i],
2205                                                                "FL", i);
2206                                         if (!clear_all_dirty_bits
2207                                             (p_s_tb->tb_sb, p_s_tb->FL[i]))
2208                                                 locked = p_s_tb->FL[i];
2209                                 }
2210
2211                                 if (!locked && p_s_tb->CFL[i]) {
2212                                         tb_buffer_sanity_check(p_s_tb->tb_sb,
2213                                                                p_s_tb->CFL[i],
2214                                                                "CFL", i);
2215                                         if (!clear_all_dirty_bits
2216                                             (p_s_tb->tb_sb, p_s_tb->CFL[i]))
2217                                                 locked = p_s_tb->CFL[i];
2218                                 }
2219
2220                         }
2221
2222                         if (!locked && (p_s_tb->rnum[i])) {
2223
2224                                 if (p_s_tb->R[i]) {
2225                                         tb_buffer_sanity_check(p_s_tb->tb_sb,
2226                                                                p_s_tb->R[i],
2227                                                                "R", i);
2228                                         if (!clear_all_dirty_bits
2229                                             (p_s_tb->tb_sb, p_s_tb->R[i]))
2230                                                 locked = p_s_tb->R[i];
2231                                 }
2232
2233                                 if (!locked && p_s_tb->FR[i]) {
2234                                         tb_buffer_sanity_check(p_s_tb->tb_sb,
2235                                                                p_s_tb->FR[i],
2236                                                                "FR", i);
2237                                         if (!clear_all_dirty_bits
2238                                             (p_s_tb->tb_sb, p_s_tb->FR[i]))
2239                                                 locked = p_s_tb->FR[i];
2240                                 }
2241
2242                                 if (!locked && p_s_tb->CFR[i]) {
2243                                         tb_buffer_sanity_check(p_s_tb->tb_sb,
2244                                                                p_s_tb->CFR[i],
2245                                                                "CFR", i);
2246                                         if (!clear_all_dirty_bits
2247                                             (p_s_tb->tb_sb, p_s_tb->CFR[i]))
2248                                                 locked = p_s_tb->CFR[i];
2249                                 }
2250                         }
2251                 }
2252                 /* as far as I can tell, this is not required.  The FEB list seems
2253                  ** to be full of newly allocated nodes, which will never be locked,
2254                  ** dirty, or anything else.
2255                  ** To be safe, I'm putting in the checks and waits in.  For the moment,
2256                  ** they are needed to keep the code in journal.c from complaining
2257                  ** about the buffer.  That code is inside CONFIG_REISERFS_CHECK as well.
2258                  ** --clm
2259                  */
2260                 for (i = 0; !locked && i < MAX_FEB_SIZE; i++) {
2261                         if (p_s_tb->FEB[i]) {
2262                                 if (!clear_all_dirty_bits
2263                                     (p_s_tb->tb_sb, p_s_tb->FEB[i]))
2264                                         locked = p_s_tb->FEB[i];
2265                         }
2266                 }
2267
2268                 if (locked) {
2269 #ifdef CONFIG_REISERFS_CHECK
2270                         repeat_counter++;
2271                         if ((repeat_counter % 10000) == 0) {
2272                                 reiserfs_warning(p_s_tb->tb_sb, "reiserfs-8200",
2273                                                  "too many iterations waiting "
2274                                                  "for buffer to unlock "
2275                                                  "(%b)", locked);
2276
2277                                 /* Don't loop forever.  Try to recover from possible error. */
2278
2279                                 return (FILESYSTEM_CHANGED_TB(p_s_tb)) ?
2280                                     REPEAT_SEARCH : CARRY_ON;
2281                         }
2282 #endif
2283                         __wait_on_buffer(locked);
2284                         if (FILESYSTEM_CHANGED_TB(p_s_tb)) {
2285                                 return REPEAT_SEARCH;
2286                         }
2287                 }
2288
2289         } while (locked);
2290
2291         return CARRY_ON;
2292 }
2293
2294 /* Prepare for balancing, that is
2295  *      get all necessary parents, and neighbors;
2296  *      analyze what and where should be moved;
2297  *      get sufficient number of new nodes;
2298  * Balancing will start only after all resources will be collected at a time.
2299  *
2300  * When ported to SMP kernels, only at the last moment after all needed nodes
2301  * are collected in cache, will the resources be locked using the usual
2302  * textbook ordered lock acquisition algorithms.  Note that ensuring that
2303  * this code neither write locks what it does not need to write lock nor locks out of order
2304  * will be a pain in the butt that could have been avoided.  Grumble grumble. -Hans
2305  *
2306  * fix is meant in the sense of render unchanging
2307  *
2308  * Latency might be improved by first gathering a list of what buffers are needed
2309  * and then getting as many of them in parallel as possible? -Hans
2310  *
2311  * Parameters:
2312  *      op_mode i - insert, d - delete, c - cut (truncate), p - paste (append)
2313  *      tb      tree_balance structure;
2314  *      inum    item number in S[h];
2315  *      pos_in_item - comment this if you can
2316  *      ins_ih & ins_sd are used when inserting
2317  * Returns:     1 - schedule occurred while the function worked;
2318  *              0 - schedule didn't occur while the function worked;
2319  *             -1 - if no_disk_space
2320  */
2321
2322 int fix_nodes(int n_op_mode, struct tree_balance *p_s_tb, struct item_head *p_s_ins_ih, // item head of item being inserted
2323               const void *data  // inserted item or data to be pasted
2324     )
2325 {
2326         int n_ret_value, n_h, n_item_num = PATH_LAST_POSITION(p_s_tb->tb_path);
2327         int n_pos_in_item;
2328
2329         /* we set wait_tb_buffers_run when we have to restore any dirty bits cleared
2330          ** during wait_tb_buffers_run
2331          */
2332         int wait_tb_buffers_run = 0;
2333         struct buffer_head *p_s_tbS0 = PATH_PLAST_BUFFER(p_s_tb->tb_path);
2334
2335         ++REISERFS_SB(p_s_tb->tb_sb)->s_fix_nodes;
2336
2337         n_pos_in_item = p_s_tb->tb_path->pos_in_item;
2338
2339         p_s_tb->fs_gen = get_generation(p_s_tb->tb_sb);
2340
2341         /* we prepare and log the super here so it will already be in the
2342          ** transaction when do_balance needs to change it.
2343          ** This way do_balance won't have to schedule when trying to prepare
2344          ** the super for logging
2345          */
2346         reiserfs_prepare_for_journal(p_s_tb->tb_sb,
2347                                      SB_BUFFER_WITH_SB(p_s_tb->tb_sb), 1);
2348         journal_mark_dirty(p_s_tb->transaction_handle, p_s_tb->tb_sb,
2349                            SB_BUFFER_WITH_SB(p_s_tb->tb_sb));
2350         if (FILESYSTEM_CHANGED_TB(p_s_tb))
2351                 return REPEAT_SEARCH;
2352
2353         /* if it possible in indirect_to_direct conversion */
2354         if (buffer_locked(p_s_tbS0)) {
2355                 __wait_on_buffer(p_s_tbS0);
2356                 if (FILESYSTEM_CHANGED_TB(p_s_tb))
2357                         return REPEAT_SEARCH;
2358         }
2359 #ifdef CONFIG_REISERFS_CHECK
2360         if (cur_tb) {
2361                 print_cur_tb("fix_nodes");
2362                 reiserfs_panic(p_s_tb->tb_sb, "PAP-8305",
2363                                "there is pending do_balance");
2364         }
2365
2366         if (!buffer_uptodate(p_s_tbS0) || !B_IS_IN_TREE(p_s_tbS0)) {
2367                 reiserfs_panic(p_s_tb->tb_sb, "PAP-8320", "S[0] (%b %z) is "
2368                                "not uptodate at the beginning of fix_nodes "
2369                                "or not in tree (mode %c)",
2370                                p_s_tbS0, p_s_tbS0, n_op_mode);
2371         }
2372
2373         /* Check parameters. */
2374         switch (n_op_mode) {
2375         case M_INSERT:
2376                 if (n_item_num <= 0 || n_item_num > B_NR_ITEMS(p_s_tbS0))
2377                         reiserfs_panic(p_s_tb->tb_sb, "PAP-8330", "Incorrect "
2378                                        "item number %d (in S0 - %d) in case "
2379                                        "of insert", n_item_num,
2380                                        B_NR_ITEMS(p_s_tbS0));
2381                 break;
2382         case M_PASTE:
2383         case M_DELETE:
2384         case M_CUT:
2385                 if (n_item_num < 0 || n_item_num >= B_NR_ITEMS(p_s_tbS0)) {
2386                         print_block(p_s_tbS0, 0, -1, -1);
2387                         reiserfs_panic(p_s_tb->tb_sb, "PAP-8335", "Incorrect "
2388                                        "item number(%d); mode = %c "
2389                                        "insert_size = %d",
2390                                        n_item_num, n_op_mode,
2391                                        p_s_tb->insert_size[0]);
2392                 }
2393                 break;
2394         default:
2395                 reiserfs_panic(p_s_tb->tb_sb, "PAP-8340", "Incorrect mode "
2396                                "of operation");
2397         }
2398 #endif
2399
2400         if (get_mem_for_virtual_node(p_s_tb) == REPEAT_SEARCH)
2401                 // FIXME: maybe -ENOMEM when tb->vn_buf == 0? Now just repeat
2402                 return REPEAT_SEARCH;
2403
2404         /* Starting from the leaf level; for all levels n_h of the tree. */
2405         for (n_h = 0; n_h < MAX_HEIGHT && p_s_tb->insert_size[n_h]; n_h++) {
2406                 if ((n_ret_value = get_direct_parent(p_s_tb, n_h)) != CARRY_ON) {
2407                         goto repeat;
2408                 }
2409
2410                 if ((n_ret_value =
2411                      check_balance(n_op_mode, p_s_tb, n_h, n_item_num,
2412                                    n_pos_in_item, p_s_ins_ih,
2413                                    data)) != CARRY_ON) {
2414                         if (n_ret_value == NO_BALANCING_NEEDED) {
2415                                 /* No balancing for higher levels needed. */
2416                                 if ((n_ret_value =
2417                                      get_neighbors(p_s_tb, n_h)) != CARRY_ON) {
2418                                         goto repeat;
2419                                 }
2420                                 if (n_h != MAX_HEIGHT - 1)
2421                                         p_s_tb->insert_size[n_h + 1] = 0;
2422                                 /* ok, analysis and resource gathering are complete */
2423                                 break;
2424                         }
2425                         goto repeat;
2426                 }
2427
2428                 if ((n_ret_value = get_neighbors(p_s_tb, n_h)) != CARRY_ON) {
2429                         goto repeat;
2430                 }
2431
2432                 if ((n_ret_value = get_empty_nodes(p_s_tb, n_h)) != CARRY_ON) {
2433                         goto repeat;    /* No disk space, or schedule occurred and
2434                                            analysis may be invalid and needs to be redone. */
2435                 }
2436
2437                 if (!PATH_H_PBUFFER(p_s_tb->tb_path, n_h)) {
2438                         /* We have a positive insert size but no nodes exist on this
2439                            level, this means that we are creating a new root. */
2440
2441                         RFALSE(p_s_tb->blknum[n_h] != 1,
2442                                "PAP-8350: creating new empty root");
2443
2444                         if (n_h < MAX_HEIGHT - 1)
2445                                 p_s_tb->insert_size[n_h + 1] = 0;
2446                 } else if (!PATH_H_PBUFFER(p_s_tb->tb_path, n_h + 1)) {
2447                         if (p_s_tb->blknum[n_h] > 1) {
2448                                 /* The tree needs to be grown, so this node S[n_h]
2449                                    which is the root node is split into two nodes,
2450                                    and a new node (S[n_h+1]) will be created to
2451                                    become the root node.  */
2452
2453                                 RFALSE(n_h == MAX_HEIGHT - 1,
2454                                        "PAP-8355: attempt to create too high of a tree");
2455
2456                                 p_s_tb->insert_size[n_h + 1] =
2457                                     (DC_SIZE +
2458                                      KEY_SIZE) * (p_s_tb->blknum[n_h] - 1) +
2459                                     DC_SIZE;
2460                         } else if (n_h < MAX_HEIGHT - 1)
2461                                 p_s_tb->insert_size[n_h + 1] = 0;
2462                 } else
2463                         p_s_tb->insert_size[n_h + 1] =
2464                             (DC_SIZE + KEY_SIZE) * (p_s_tb->blknum[n_h] - 1);
2465         }
2466
2467         if ((n_ret_value = wait_tb_buffers_until_unlocked(p_s_tb)) == CARRY_ON) {
2468                 if (FILESYSTEM_CHANGED_TB(p_s_tb)) {
2469                         wait_tb_buffers_run = 1;
2470                         n_ret_value = REPEAT_SEARCH;
2471                         goto repeat;
2472                 } else {
2473                         return CARRY_ON;
2474                 }
2475         } else {
2476                 wait_tb_buffers_run = 1;
2477                 goto repeat;
2478         }
2479
2480       repeat:
2481         // fix_nodes was unable to perform its calculation due to
2482         // filesystem got changed under us, lack of free disk space or i/o
2483         // failure. If the first is the case - the search will be
2484         // repeated. For now - free all resources acquired so far except
2485         // for the new allocated nodes
2486         {
2487                 int i;
2488
2489                 /* Release path buffers. */
2490                 if (wait_tb_buffers_run) {
2491                         pathrelse_and_restore(p_s_tb->tb_sb, p_s_tb->tb_path);
2492                 } else {
2493                         pathrelse(p_s_tb->tb_path);
2494                 }
2495                 /* brelse all resources collected for balancing */
2496                 for (i = 0; i < MAX_HEIGHT; i++) {
2497                         if (wait_tb_buffers_run) {
2498                                 reiserfs_restore_prepared_buffer(p_s_tb->tb_sb,
2499                                                                  p_s_tb->L[i]);
2500                                 reiserfs_restore_prepared_buffer(p_s_tb->tb_sb,
2501                                                                  p_s_tb->R[i]);
2502                                 reiserfs_restore_prepared_buffer(p_s_tb->tb_sb,
2503                                                                  p_s_tb->FL[i]);
2504                                 reiserfs_restore_prepared_buffer(p_s_tb->tb_sb,
2505                                                                  p_s_tb->FR[i]);
2506                                 reiserfs_restore_prepared_buffer(p_s_tb->tb_sb,
2507                                                                  p_s_tb->
2508                                                                  CFL[i]);
2509                                 reiserfs_restore_prepared_buffer(p_s_tb->tb_sb,
2510                                                                  p_s_tb->
2511                                                                  CFR[i]);
2512                         }
2513
2514                         brelse(p_s_tb->L[i]);
2515                         brelse(p_s_tb->R[i]);
2516                         brelse(p_s_tb->FL[i]);
2517                         brelse(p_s_tb->FR[i]);
2518                         brelse(p_s_tb->CFL[i]);
2519                         brelse(p_s_tb->CFR[i]);
2520
2521                         p_s_tb->L[i] = NULL;
2522                         p_s_tb->R[i] = NULL;
2523                         p_s_tb->FL[i] = NULL;
2524                         p_s_tb->FR[i] = NULL;
2525                         p_s_tb->CFL[i] = NULL;
2526                         p_s_tb->CFR[i] = NULL;
2527                 }
2528
2529                 if (wait_tb_buffers_run) {
2530                         for (i = 0; i < MAX_FEB_SIZE; i++) {
2531                                 if (p_s_tb->FEB[i]) {
2532                                         reiserfs_restore_prepared_buffer
2533                                             (p_s_tb->tb_sb, p_s_tb->FEB[i]);
2534                                 }
2535                         }
2536                 }
2537                 return n_ret_value;
2538         }
2539
2540 }
2541
2542 /* Anatoly will probably forgive me renaming p_s_tb to tb. I just
2543    wanted to make lines shorter */
2544 void unfix_nodes(struct tree_balance *tb)
2545 {
2546         int i;
2547
2548         /* Release path buffers. */
2549         pathrelse_and_restore(tb->tb_sb, tb->tb_path);
2550
2551         /* brelse all resources collected for balancing */
2552         for (i = 0; i < MAX_HEIGHT; i++) {
2553                 reiserfs_restore_prepared_buffer(tb->tb_sb, tb->L[i]);
2554                 reiserfs_restore_prepared_buffer(tb->tb_sb, tb->R[i]);
2555                 reiserfs_restore_prepared_buffer(tb->tb_sb, tb->FL[i]);
2556                 reiserfs_restore_prepared_buffer(tb->tb_sb, tb->FR[i]);
2557                 reiserfs_restore_prepared_buffer(tb->tb_sb, tb->CFL[i]);
2558                 reiserfs_restore_prepared_buffer(tb->tb_sb, tb->CFR[i]);
2559
2560                 brelse(tb->L[i]);
2561                 brelse(tb->R[i]);
2562                 brelse(tb->FL[i]);
2563                 brelse(tb->FR[i]);
2564                 brelse(tb->CFL[i]);
2565                 brelse(tb->CFR[i]);
2566         }
2567
2568         /* deal with list of allocated (used and unused) nodes */
2569         for (i = 0; i < MAX_FEB_SIZE; i++) {
2570                 if (tb->FEB[i]) {
2571                         b_blocknr_t blocknr = tb->FEB[i]->b_blocknr;
2572                         /* de-allocated block which was not used by balancing and
2573                            bforget about buffer for it */
2574                         brelse(tb->FEB[i]);
2575                         reiserfs_free_block(tb->transaction_handle, NULL,
2576                                             blocknr, 0);
2577                 }
2578                 if (tb->used[i]) {
2579                         /* release used as new nodes including a new root */
2580                         brelse(tb->used[i]);
2581                 }
2582         }
2583
2584         kfree(tb->vn_buf);
2585
2586 }