git.oblomov.eu Git - linux-2.6/blob - fs/reiserfs/fix_node.c

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