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