linux/fs/reiserfs/fix_node.c
<<
>>
Prefs
   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 "reiserfs.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 */
  58static 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
  78static 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 */
 203static 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 */
 283static 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 */
 366static 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
 585static 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. */
 612static 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 */
 654static 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 \
 712if (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}\
 721else \
 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 \
 732if (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}\
 740else \
 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
 750static 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! */
 779static 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.  */
 854static 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 */
 876static 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. */
 897static 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
 941static 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 */
 955static 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 */
1081static 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. */
1170static 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 */
1219static 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 */
1562static 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 */
1742static 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 */
1836static 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 */
1865static 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.*/
1894static 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 */
1948static 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
2037static 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 */
2058static 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
2105static 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
2143static 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
2150static 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
2155static 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
2330int 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 */
2551void 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}
2594