linux/fs/reiserfs/do_balan.c
<<
>>
Prefs
   1/*
   2 * Copyright 2000 by Hans Reiser, licensing governed by reiserfs/README
   3 */
   4
   5/* Now we have all buffers that must be used in balancing of the tree   */
   6/* Further calculations can not cause schedule(), and thus the buffer   */
   7/* tree will be stable until the balancing will be finished             */
   8/* balance the tree according to the analysis made before,              */
   9/* and using buffers obtained after all above.                          */
  10
  11/**
  12 ** balance_leaf_when_delete
  13 ** balance_leaf
  14 ** do_balance
  15 **
  16 **/
  17
  18#include <asm/uaccess.h>
  19#include <linux/time.h>
  20#include "reiserfs.h"
  21#include <linux/buffer_head.h>
  22#include <linux/kernel.h>
  23
  24static inline void buffer_info_init_left(struct tree_balance *tb,
  25                                         struct buffer_info *bi)
  26{
  27        bi->tb          = tb;
  28        bi->bi_bh       = tb->L[0];
  29        bi->bi_parent   = tb->FL[0];
  30        bi->bi_position = get_left_neighbor_position(tb, 0);
  31}
  32
  33static inline void buffer_info_init_right(struct tree_balance *tb,
  34                                          struct buffer_info *bi)
  35{
  36        bi->tb          = tb;
  37        bi->bi_bh       = tb->R[0];
  38        bi->bi_parent   = tb->FR[0];
  39        bi->bi_position = get_right_neighbor_position(tb, 0);
  40}
  41
  42static inline void buffer_info_init_tbS0(struct tree_balance *tb,
  43                                         struct buffer_info *bi)
  44{
  45        bi->tb          = tb;
  46        bi->bi_bh        = PATH_PLAST_BUFFER(tb->tb_path);
  47        bi->bi_parent   = PATH_H_PPARENT(tb->tb_path, 0);
  48        bi->bi_position = PATH_H_POSITION(tb->tb_path, 1);
  49}
  50
  51static inline void buffer_info_init_bh(struct tree_balance *tb,
  52                                       struct buffer_info *bi,
  53                                       struct buffer_head *bh)
  54{
  55        bi->tb          = tb;
  56        bi->bi_bh       = bh;
  57        bi->bi_parent   = NULL;
  58        bi->bi_position = 0;
  59}
  60
  61inline void do_balance_mark_leaf_dirty(struct tree_balance *tb,
  62                                       struct buffer_head *bh, int flag)
  63{
  64        journal_mark_dirty(tb->transaction_handle,
  65                           tb->transaction_handle->t_super, bh);
  66}
  67
  68#define do_balance_mark_internal_dirty do_balance_mark_leaf_dirty
  69#define do_balance_mark_sb_dirty do_balance_mark_leaf_dirty
  70
  71/* summary:
  72 if deleting something ( tb->insert_size[0] < 0 )
  73   return(balance_leaf_when_delete()); (flag d handled here)
  74 else
  75   if lnum is larger than 0 we put items into the left node
  76   if rnum is larger than 0 we put items into the right node
  77   if snum1 is larger than 0 we put items into the new node s1
  78   if snum2 is larger than 0 we put items into the new node s2
  79Note that all *num* count new items being created.
  80
  81It would be easier to read balance_leaf() if each of these summary
  82lines was a separate procedure rather than being inlined.  I think
  83that there are many passages here and in balance_leaf_when_delete() in
  84which two calls to one procedure can replace two passages, and it
  85might save cache space and improve software maintenance costs to do so.
  86
  87Vladimir made the perceptive comment that we should offload most of
  88the decision making in this function into fix_nodes/check_balance, and
  89then create some sort of structure in tb that says what actions should
  90be performed by do_balance.
  91
  92-Hans */
  93
  94/* Balance leaf node in case of delete or cut: insert_size[0] < 0
  95 *
  96 * lnum, rnum can have values >= -1
  97 *      -1 means that the neighbor must be joined with S
  98 *       0 means that nothing should be done with the neighbor
  99 *      >0 means to shift entirely or partly the specified number of items to the neighbor
 100 */
 101static int balance_leaf_when_delete(struct tree_balance *tb, int flag)
 102{
 103        struct buffer_head *tbS0 = PATH_PLAST_BUFFER(tb->tb_path);
 104        int item_pos = PATH_LAST_POSITION(tb->tb_path);
 105        int pos_in_item = tb->tb_path->pos_in_item;
 106        struct buffer_info bi;
 107        int n;
 108        struct item_head *ih;
 109
 110        RFALSE(tb->FR[0] && B_LEVEL(tb->FR[0]) != DISK_LEAF_NODE_LEVEL + 1,
 111               "vs- 12000: level: wrong FR %z", tb->FR[0]);
 112        RFALSE(tb->blknum[0] > 1,
 113               "PAP-12005: tb->blknum == %d, can not be > 1", tb->blknum[0]);
 114        RFALSE(!tb->blknum[0] && !PATH_H_PPARENT(tb->tb_path, 0),
 115               "PAP-12010: tree can not be empty");
 116
 117        ih = B_N_PITEM_HEAD(tbS0, item_pos);
 118        buffer_info_init_tbS0(tb, &bi);
 119
 120        /* Delete or truncate the item */
 121
 122        switch (flag) {
 123        case M_DELETE:          /* delete item in S[0] */
 124
 125                RFALSE(ih_item_len(ih) + IH_SIZE != -tb->insert_size[0],
 126                       "vs-12013: mode Delete, insert size %d, ih to be deleted %h",
 127                       -tb->insert_size[0], ih);
 128
 129                leaf_delete_items(&bi, 0, item_pos, 1, -1);
 130
 131                if (!item_pos && tb->CFL[0]) {
 132                        if (B_NR_ITEMS(tbS0)) {
 133                                replace_key(tb, tb->CFL[0], tb->lkey[0], tbS0,
 134                                            0);
 135                        } else {
 136                                if (!PATH_H_POSITION(tb->tb_path, 1))
 137                                        replace_key(tb, tb->CFL[0], tb->lkey[0],
 138                                                    PATH_H_PPARENT(tb->tb_path,
 139                                                                   0), 0);
 140                        }
 141                }
 142
 143                RFALSE(!item_pos && !tb->CFL[0],
 144                       "PAP-12020: tb->CFL[0]==%p, tb->L[0]==%p", tb->CFL[0],
 145                       tb->L[0]);
 146
 147                break;
 148
 149        case M_CUT:{            /* cut item in S[0] */
 150                        if (is_direntry_le_ih(ih)) {
 151
 152                                /* UFS unlink semantics are such that you can only delete one directory entry at a time. */
 153                                /* when we cut a directory tb->insert_size[0] means number of entries to be cut (always 1) */
 154                                tb->insert_size[0] = -1;
 155                                leaf_cut_from_buffer(&bi, item_pos, pos_in_item,
 156                                                     -tb->insert_size[0]);
 157
 158                                RFALSE(!item_pos && !pos_in_item && !tb->CFL[0],
 159                                       "PAP-12030: can not change delimiting key. CFL[0]=%p",
 160                                       tb->CFL[0]);
 161
 162                                if (!item_pos && !pos_in_item && tb->CFL[0]) {
 163                                        replace_key(tb, tb->CFL[0], tb->lkey[0],
 164                                                    tbS0, 0);
 165                                }
 166                        } else {
 167                                leaf_cut_from_buffer(&bi, item_pos, pos_in_item,
 168                                                     -tb->insert_size[0]);
 169
 170                                RFALSE(!ih_item_len(ih),
 171                                       "PAP-12035: cut must leave non-zero dynamic length of item");
 172                        }
 173                        break;
 174                }
 175
 176        default:
 177                print_cur_tb("12040");
 178                reiserfs_panic(tb->tb_sb, "PAP-12040",
 179                               "unexpected mode: %s(%d)",
 180                               (flag ==
 181                                M_PASTE) ? "PASTE" : ((flag ==
 182                                                       M_INSERT) ? "INSERT" :
 183                                                      "UNKNOWN"), flag);
 184        }
 185
 186        /* the rule is that no shifting occurs unless by shifting a node can be freed */
 187        n = B_NR_ITEMS(tbS0);
 188        if (tb->lnum[0]) {      /* L[0] takes part in balancing */
 189                if (tb->lnum[0] == -1) {        /* L[0] must be joined with S[0] */
 190                        if (tb->rnum[0] == -1) {        /* R[0] must be also joined with S[0] */
 191                                if (tb->FR[0] == PATH_H_PPARENT(tb->tb_path, 0)) {
 192                                        /* all contents of all the 3 buffers will be in L[0] */
 193                                        if (PATH_H_POSITION(tb->tb_path, 1) == 0
 194                                            && 1 < B_NR_ITEMS(tb->FR[0]))
 195                                                replace_key(tb, tb->CFL[0],
 196                                                            tb->lkey[0],
 197                                                            tb->FR[0], 1);
 198
 199                                        leaf_move_items(LEAF_FROM_S_TO_L, tb, n,
 200                                                        -1, NULL);
 201                                        leaf_move_items(LEAF_FROM_R_TO_L, tb,
 202                                                        B_NR_ITEMS(tb->R[0]),
 203                                                        -1, NULL);
 204
 205                                        reiserfs_invalidate_buffer(tb, tbS0);
 206                                        reiserfs_invalidate_buffer(tb,
 207                                                                   tb->R[0]);
 208
 209                                        return 0;
 210                                }
 211                                /* all contents of all the 3 buffers will be in R[0] */
 212                                leaf_move_items(LEAF_FROM_S_TO_R, tb, n, -1,
 213                                                NULL);
 214                                leaf_move_items(LEAF_FROM_L_TO_R, tb,
 215                                                B_NR_ITEMS(tb->L[0]), -1, NULL);
 216
 217                                /* right_delimiting_key is correct in R[0] */
 218                                replace_key(tb, tb->CFR[0], tb->rkey[0],
 219                                            tb->R[0], 0);
 220
 221                                reiserfs_invalidate_buffer(tb, tbS0);
 222                                reiserfs_invalidate_buffer(tb, tb->L[0]);
 223
 224                                return -1;
 225                        }
 226
 227                        RFALSE(tb->rnum[0] != 0,
 228                               "PAP-12045: rnum must be 0 (%d)", tb->rnum[0]);
 229                        /* all contents of L[0] and S[0] will be in L[0] */
 230                        leaf_shift_left(tb, n, -1);
 231
 232                        reiserfs_invalidate_buffer(tb, tbS0);
 233
 234                        return 0;
 235                }
 236                /* a part of contents of S[0] will be in L[0] and the rest part of S[0] will be in R[0] */
 237
 238                RFALSE((tb->lnum[0] + tb->rnum[0] < n) ||
 239                       (tb->lnum[0] + tb->rnum[0] > n + 1),
 240                       "PAP-12050: rnum(%d) and lnum(%d) and item number(%d) in S[0] are not consistent",
 241                       tb->rnum[0], tb->lnum[0], n);
 242                RFALSE((tb->lnum[0] + tb->rnum[0] == n) &&
 243                       (tb->lbytes != -1 || tb->rbytes != -1),
 244                       "PAP-12055: bad rbytes (%d)/lbytes (%d) parameters when items are not split",
 245                       tb->rbytes, tb->lbytes);
 246                RFALSE((tb->lnum[0] + tb->rnum[0] == n + 1) &&
 247                       (tb->lbytes < 1 || tb->rbytes != -1),
 248                       "PAP-12060: bad rbytes (%d)/lbytes (%d) parameters when items are split",
 249                       tb->rbytes, tb->lbytes);
 250
 251                leaf_shift_left(tb, tb->lnum[0], tb->lbytes);
 252                leaf_shift_right(tb, tb->rnum[0], tb->rbytes);
 253
 254                reiserfs_invalidate_buffer(tb, tbS0);
 255
 256                return 0;
 257        }
 258
 259        if (tb->rnum[0] == -1) {
 260                /* all contents of R[0] and S[0] will be in R[0] */
 261                leaf_shift_right(tb, n, -1);
 262                reiserfs_invalidate_buffer(tb, tbS0);
 263                return 0;
 264        }
 265
 266        RFALSE(tb->rnum[0],
 267               "PAP-12065: bad rnum parameter must be 0 (%d)", tb->rnum[0]);
 268        return 0;
 269}
 270
 271static int balance_leaf(struct tree_balance *tb, struct item_head *ih,  /* item header of inserted item (this is on little endian) */
 272                        const char *body,       /* body  of inserted item or bytes to paste */
 273                        int flag,       /* i - insert, d - delete, c - cut, p - paste
 274                                           (see comment to do_balance) */
 275                        struct item_head *insert_key,   /* in our processing of one level we sometimes determine what
 276                                                           must be inserted into the next higher level.  This insertion
 277                                                           consists of a key or two keys and their corresponding
 278                                                           pointers */
 279                        struct buffer_head **insert_ptr /* inserted node-ptrs for the next level */
 280    )
 281{
 282        struct buffer_head *tbS0 = PATH_PLAST_BUFFER(tb->tb_path);
 283        int item_pos = PATH_LAST_POSITION(tb->tb_path); /*  index into the array of item headers in S[0]
 284                                                           of the affected item */
 285        struct buffer_info bi;
 286        struct buffer_head *S_new[2];   /* new nodes allocated to hold what could not fit into S */
 287        int snum[2];            /* number of items that will be placed
 288                                   into S_new (includes partially shifted
 289                                   items) */
 290        int sbytes[2];          /* if an item is partially shifted into S_new then
 291                                   if it is a directory item
 292                                   it is the number of entries from the item that are shifted into S_new
 293                                   else
 294                                   it is the number of bytes from the item that are shifted into S_new
 295                                 */
 296        int n, i;
 297        int ret_val;
 298        int pos_in_item;
 299        int zeros_num;
 300
 301        PROC_INFO_INC(tb->tb_sb, balance_at[0]);
 302
 303        /* Make balance in case insert_size[0] < 0 */
 304        if (tb->insert_size[0] < 0)
 305                return balance_leaf_when_delete(tb, flag);
 306
 307        zeros_num = 0;
 308        if (flag == M_INSERT && !body)
 309                zeros_num = ih_item_len(ih);
 310
 311        pos_in_item = tb->tb_path->pos_in_item;
 312        /* for indirect item pos_in_item is measured in unformatted node
 313           pointers. Recalculate to bytes */
 314        if (flag != M_INSERT
 315            && is_indirect_le_ih(B_N_PITEM_HEAD(tbS0, item_pos)))
 316                pos_in_item *= UNFM_P_SIZE;
 317
 318        if (tb->lnum[0] > 0) {
 319                /* Shift lnum[0] items from S[0] to the left neighbor L[0] */
 320                if (item_pos < tb->lnum[0]) {
 321                        /* new item or it part falls to L[0], shift it too */
 322                        n = B_NR_ITEMS(tb->L[0]);
 323
 324                        switch (flag) {
 325                        case M_INSERT:  /* insert item into L[0] */
 326
 327                                if (item_pos == tb->lnum[0] - 1
 328                                    && tb->lbytes != -1) {
 329                                        /* part of new item falls into L[0] */
 330                                        int new_item_len;
 331                                        int version;
 332
 333                                        ret_val =
 334                                            leaf_shift_left(tb, tb->lnum[0] - 1,
 335                                                            -1);
 336
 337                                        /* Calculate item length to insert to S[0] */
 338                                        new_item_len =
 339                                            ih_item_len(ih) - tb->lbytes;
 340                                        /* Calculate and check item length to insert to L[0] */
 341                                        put_ih_item_len(ih,
 342                                                        ih_item_len(ih) -
 343                                                        new_item_len);
 344
 345                                        RFALSE(ih_item_len(ih) <= 0,
 346                                               "PAP-12080: there is nothing to insert into L[0]: ih_item_len=%d",
 347                                               ih_item_len(ih));
 348
 349                                        /* Insert new item into L[0] */
 350                                        buffer_info_init_left(tb, &bi);
 351                                        leaf_insert_into_buf(&bi,
 352                                                             n + item_pos -
 353                                                             ret_val, ih, body,
 354                                                             zeros_num >
 355                                                             ih_item_len(ih) ?
 356                                                             ih_item_len(ih) :
 357                                                             zeros_num);
 358
 359                                        version = ih_version(ih);
 360
 361                                        /* Calculate key component, item length and body to insert into S[0] */
 362                                        set_le_ih_k_offset(ih,
 363                                                           le_ih_k_offset(ih) +
 364                                                           (tb->
 365                                                            lbytes <<
 366                                                            (is_indirect_le_ih
 367                                                             (ih) ? tb->tb_sb->
 368                                                             s_blocksize_bits -
 369                                                             UNFM_P_SHIFT :
 370                                                             0)));
 371
 372                                        put_ih_item_len(ih, new_item_len);
 373                                        if (tb->lbytes > zeros_num) {
 374                                                body +=
 375                                                    (tb->lbytes - zeros_num);
 376                                                zeros_num = 0;
 377                                        } else
 378                                                zeros_num -= tb->lbytes;
 379
 380                                        RFALSE(ih_item_len(ih) <= 0,
 381                                               "PAP-12085: there is nothing to insert into S[0]: ih_item_len=%d",
 382                                               ih_item_len(ih));
 383                                } else {
 384                                        /* new item in whole falls into L[0] */
 385                                        /* Shift lnum[0]-1 items to L[0] */
 386                                        ret_val =
 387                                            leaf_shift_left(tb, tb->lnum[0] - 1,
 388                                                            tb->lbytes);
 389                                        /* Insert new item into L[0] */
 390                                        buffer_info_init_left(tb, &bi);
 391                                        leaf_insert_into_buf(&bi,
 392                                                             n + item_pos -
 393                                                             ret_val, ih, body,
 394                                                             zeros_num);
 395                                        tb->insert_size[0] = 0;
 396                                        zeros_num = 0;
 397                                }
 398                                break;
 399
 400                        case M_PASTE:   /* append item in L[0] */
 401
 402                                if (item_pos == tb->lnum[0] - 1
 403                                    && tb->lbytes != -1) {
 404                                        /* we must shift the part of the appended item */
 405                                        if (is_direntry_le_ih
 406                                            (B_N_PITEM_HEAD(tbS0, item_pos))) {
 407
 408                                                RFALSE(zeros_num,
 409                                                       "PAP-12090: invalid parameter in case of a directory");
 410                                                /* directory item */
 411                                                if (tb->lbytes > pos_in_item) {
 412                                                        /* new directory entry falls into L[0] */
 413                                                        struct item_head
 414                                                            *pasted;
 415                                                        int l_pos_in_item =
 416                                                            pos_in_item;
 417
 418                                                        /* Shift lnum[0] - 1 items in whole. Shift lbytes - 1 entries from given directory item */
 419                                                        ret_val =
 420                                                            leaf_shift_left(tb,
 421                                                                            tb->
 422                                                                            lnum
 423                                                                            [0],
 424                                                                            tb->
 425                                                                            lbytes
 426                                                                            -
 427                                                                            1);
 428                                                        if (ret_val
 429                                                            && !item_pos) {
 430                                                                pasted =
 431                                                                    B_N_PITEM_HEAD
 432                                                                    (tb->L[0],
 433                                                                     B_NR_ITEMS
 434                                                                     (tb->
 435                                                                      L[0]) -
 436                                                                     1);
 437                                                                l_pos_in_item +=
 438                                                                    I_ENTRY_COUNT
 439                                                                    (pasted) -
 440                                                                    (tb->
 441                                                                     lbytes -
 442                                                                     1);
 443                                                        }
 444
 445                                                        /* Append given directory entry to directory item */
 446                                                        buffer_info_init_left(tb, &bi);
 447                                                        leaf_paste_in_buffer
 448                                                            (&bi,
 449                                                             n + item_pos -
 450                                                             ret_val,
 451                                                             l_pos_in_item,
 452                                                             tb->insert_size[0],
 453                                                             body, zeros_num);
 454
 455                                                        /* previous string prepared space for pasting new entry, following string pastes this entry */
 456
 457                                                        /* when we have merge directory item, pos_in_item has been changed too */
 458
 459                                                        /* paste new directory entry. 1 is entry number */
 460                                                        leaf_paste_entries(&bi,
 461                                                                           n +
 462                                                                           item_pos
 463                                                                           -
 464                                                                           ret_val,
 465                                                                           l_pos_in_item,
 466                                                                           1,
 467                                                                           (struct
 468                                                                            reiserfs_de_head
 469                                                                            *)
 470                                                                           body,
 471                                                                           body
 472                                                                           +
 473                                                                           DEH_SIZE,
 474                                                                           tb->
 475                                                                           insert_size
 476                                                                           [0]
 477                                                            );
 478                                                        tb->insert_size[0] = 0;
 479                                                } else {
 480                                                        /* new directory item doesn't fall into L[0] */
 481                                                        /* Shift lnum[0]-1 items in whole. Shift lbytes directory entries from directory item number lnum[0] */
 482                                                        leaf_shift_left(tb,
 483                                                                        tb->
 484                                                                        lnum[0],
 485                                                                        tb->
 486                                                                        lbytes);
 487                                                }
 488                                                /* Calculate new position to append in item body */
 489                                                pos_in_item -= tb->lbytes;
 490                                        } else {
 491                                                /* regular object */
 492                                                RFALSE(tb->lbytes <= 0,
 493                                                       "PAP-12095: there is nothing to shift to L[0]. lbytes=%d",
 494                                                       tb->lbytes);
 495                                                RFALSE(pos_in_item !=
 496                                                       ih_item_len
 497                                                       (B_N_PITEM_HEAD
 498                                                        (tbS0, item_pos)),
 499                                                       "PAP-12100: incorrect position to paste: item_len=%d, pos_in_item=%d",
 500                                                       ih_item_len
 501                                                       (B_N_PITEM_HEAD
 502                                                        (tbS0, item_pos)),
 503                                                       pos_in_item);
 504
 505                                                if (tb->lbytes >= pos_in_item) {
 506                                                        /* appended item will be in L[0] in whole */
 507                                                        int l_n;
 508
 509                                                        /* this bytes number must be appended to the last item of L[h] */
 510                                                        l_n =
 511                                                            tb->lbytes -
 512                                                            pos_in_item;
 513
 514                                                        /* Calculate new insert_size[0] */
 515                                                        tb->insert_size[0] -=
 516                                                            l_n;
 517
 518                                                        RFALSE(tb->
 519                                                               insert_size[0] <=
 520                                                               0,
 521                                                               "PAP-12105: there is nothing to paste into L[0]. insert_size=%d",
 522                                                               tb->
 523                                                               insert_size[0]);
 524                                                        ret_val =
 525                                                            leaf_shift_left(tb,
 526                                                                            tb->
 527                                                                            lnum
 528                                                                            [0],
 529                                                                            ih_item_len
 530                                                                            (B_N_PITEM_HEAD
 531                                                                             (tbS0,
 532                                                                              item_pos)));
 533                                                        /* Append to body of item in L[0] */
 534                                                        buffer_info_init_left(tb, &bi);
 535                                                        leaf_paste_in_buffer
 536                                                            (&bi,
 537                                                             n + item_pos -
 538                                                             ret_val,
 539                                                             ih_item_len
 540                                                             (B_N_PITEM_HEAD
 541                                                              (tb->L[0],
 542                                                               n + item_pos -
 543                                                               ret_val)), l_n,
 544                                                             body,
 545                                                             zeros_num >
 546                                                             l_n ? l_n :
 547                                                             zeros_num);
 548                                                        /* 0-th item in S0 can be only of DIRECT type when l_n != 0 */
 549                                                        {
 550                                                                int version;
 551                                                                int temp_l =
 552                                                                    l_n;
 553
 554                                                                RFALSE
 555                                                                    (ih_item_len
 556                                                                     (B_N_PITEM_HEAD
 557                                                                      (tbS0,
 558                                                                       0)),
 559                                                                     "PAP-12106: item length must be 0");
 560                                                                RFALSE
 561                                                                    (comp_short_le_keys
 562                                                                     (B_N_PKEY
 563                                                                      (tbS0, 0),
 564                                                                      B_N_PKEY
 565                                                                      (tb->L[0],
 566                                                                       n +
 567                                                                       item_pos
 568                                                                       -
 569                                                                       ret_val)),
 570                                                                     "PAP-12107: items must be of the same file");
 571                                                                if (is_indirect_le_ih(B_N_PITEM_HEAD(tb->L[0], n + item_pos - ret_val))) {
 572                                                                        temp_l =
 573                                                                            l_n
 574                                                                            <<
 575                                                                            (tb->
 576                                                                             tb_sb->
 577                                                                             s_blocksize_bits
 578                                                                             -
 579                                                                             UNFM_P_SHIFT);
 580                                                                }
 581                                                                /* update key of first item in S0 */
 582                                                                version =
 583                                                                    ih_version
 584                                                                    (B_N_PITEM_HEAD
 585                                                                     (tbS0, 0));
 586                                                                set_le_key_k_offset
 587                                                                    (version,
 588                                                                     B_N_PKEY
 589                                                                     (tbS0, 0),
 590                                                                     le_key_k_offset
 591                                                                     (version,
 592                                                                      B_N_PKEY
 593                                                                      (tbS0,
 594                                                                       0)) +
 595                                                                     temp_l);
 596                                                                /* update left delimiting key */
 597                                                                set_le_key_k_offset
 598                                                                    (version,
 599                                                                     B_N_PDELIM_KEY
 600                                                                     (tb->
 601                                                                      CFL[0],
 602                                                                      tb->
 603                                                                      lkey[0]),
 604                                                                     le_key_k_offset
 605                                                                     (version,
 606                                                                      B_N_PDELIM_KEY
 607                                                                      (tb->
 608                                                                       CFL[0],
 609                                                                       tb->
 610                                                                       lkey[0]))
 611                                                                     + temp_l);
 612                                                        }
 613
 614                                                        /* Calculate new body, position in item and insert_size[0] */
 615                                                        if (l_n > zeros_num) {
 616                                                                body +=
 617                                                                    (l_n -
 618                                                                     zeros_num);
 619                                                                zeros_num = 0;
 620                                                        } else
 621                                                                zeros_num -=
 622                                                                    l_n;
 623                                                        pos_in_item = 0;
 624
 625                                                        RFALSE
 626                                                            (comp_short_le_keys
 627                                                             (B_N_PKEY(tbS0, 0),
 628                                                              B_N_PKEY(tb->L[0],
 629                                                                       B_NR_ITEMS
 630                                                                       (tb->
 631                                                                        L[0]) -
 632                                                                       1))
 633                                                             ||
 634                                                             !op_is_left_mergeable
 635                                                             (B_N_PKEY(tbS0, 0),
 636                                                              tbS0->b_size)
 637                                                             ||
 638                                                             !op_is_left_mergeable
 639                                                             (B_N_PDELIM_KEY
 640                                                              (tb->CFL[0],
 641                                                               tb->lkey[0]),
 642                                                              tbS0->b_size),
 643                                                             "PAP-12120: item must be merge-able with left neighboring item");
 644                                                } else {        /* only part of the appended item will be in L[0] */
 645
 646                                                        /* Calculate position in item for append in S[0] */
 647                                                        pos_in_item -=
 648                                                            tb->lbytes;
 649
 650                                                        RFALSE(pos_in_item <= 0,
 651                                                               "PAP-12125: no place for paste. pos_in_item=%d",
 652                                                               pos_in_item);
 653
 654                                                        /* Shift lnum[0] - 1 items in whole. Shift lbytes - 1 byte from item number lnum[0] */
 655                                                        leaf_shift_left(tb,
 656                                                                        tb->
 657                                                                        lnum[0],
 658                                                                        tb->
 659                                                                        lbytes);
 660                                                }
 661                                        }
 662                                } else {        /* appended item will be in L[0] in whole */
 663
 664                                        struct item_head *pasted;
 665
 666                                        if (!item_pos && op_is_left_mergeable(B_N_PKEY(tbS0, 0), tbS0->b_size)) {       /* if we paste into first item of S[0] and it is left mergable */
 667                                                /* then increment pos_in_item by the size of the last item in L[0] */
 668                                                pasted =
 669                                                    B_N_PITEM_HEAD(tb->L[0],
 670                                                                   n - 1);
 671                                                if (is_direntry_le_ih(pasted))
 672                                                        pos_in_item +=
 673                                                            ih_entry_count
 674                                                            (pasted);
 675                                                else
 676                                                        pos_in_item +=
 677                                                            ih_item_len(pasted);
 678                                        }
 679
 680                                        /* Shift lnum[0] - 1 items in whole. Shift lbytes - 1 byte from item number lnum[0] */
 681                                        ret_val =
 682                                            leaf_shift_left(tb, tb->lnum[0],
 683                                                            tb->lbytes);
 684                                        /* Append to body of item in L[0] */
 685                                        buffer_info_init_left(tb, &bi);
 686                                        leaf_paste_in_buffer(&bi,
 687                                                             n + item_pos -
 688                                                             ret_val,
 689                                                             pos_in_item,
 690                                                             tb->insert_size[0],
 691                                                             body, zeros_num);
 692
 693                                        /* if appended item is directory, paste entry */
 694                                        pasted =
 695                                            B_N_PITEM_HEAD(tb->L[0],
 696                                                           n + item_pos -
 697                                                           ret_val);
 698                                        if (is_direntry_le_ih(pasted))
 699                                                leaf_paste_entries(&bi,
 700                                                                   n +
 701                                                                   item_pos -
 702                                                                   ret_val,
 703                                                                   pos_in_item,
 704                                                                   1,
 705                                                                   (struct
 706                                                                    reiserfs_de_head
 707                                                                    *)body,
 708                                                                   body +
 709                                                                   DEH_SIZE,
 710                                                                   tb->
 711                                                                   insert_size
 712                                                                   [0]
 713                                                    );
 714                                        /* if appended item is indirect item, put unformatted node into un list */
 715                                        if (is_indirect_le_ih(pasted))
 716                                                set_ih_free_space(pasted, 0);
 717                                        tb->insert_size[0] = 0;
 718                                        zeros_num = 0;
 719                                }
 720                                break;
 721                        default:        /* cases d and t */
 722                                reiserfs_panic(tb->tb_sb, "PAP-12130",
 723                                               "lnum > 0: unexpected mode: "
 724                                               " %s(%d)",
 725                                               (flag ==
 726                                                M_DELETE) ? "DELETE" : ((flag ==
 727                                                                         M_CUT)
 728                                                                        ? "CUT"
 729                                                                        :
 730                                                                        "UNKNOWN"),
 731                                               flag);
 732                        }
 733                } else {
 734                        /* new item doesn't fall into L[0] */
 735                        leaf_shift_left(tb, tb->lnum[0], tb->lbytes);
 736                }
 737        }
 738
 739        /* tb->lnum[0] > 0 */
 740        /* Calculate new item position */
 741        item_pos -= (tb->lnum[0] - ((tb->lbytes != -1) ? 1 : 0));
 742
 743        if (tb->rnum[0] > 0) {
 744                /* shift rnum[0] items from S[0] to the right neighbor R[0] */
 745                n = B_NR_ITEMS(tbS0);
 746                switch (flag) {
 747
 748                case M_INSERT:  /* insert item */
 749                        if (n - tb->rnum[0] < item_pos) {       /* new item or its part falls to R[0] */
 750                                if (item_pos == n - tb->rnum[0] + 1 && tb->rbytes != -1) {      /* part of new item falls into R[0] */
 751                                        loff_t old_key_comp, old_len,
 752                                            r_zeros_number;
 753                                        const char *r_body;
 754                                        int version;
 755                                        loff_t offset;
 756
 757                                        leaf_shift_right(tb, tb->rnum[0] - 1,
 758                                                         -1);
 759
 760                                        version = ih_version(ih);
 761                                        /* Remember key component and item length */
 762                                        old_key_comp = le_ih_k_offset(ih);
 763                                        old_len = ih_item_len(ih);
 764
 765                                        /* Calculate key component and item length to insert into R[0] */
 766                                        offset =
 767                                            le_ih_k_offset(ih) +
 768                                            ((old_len -
 769                                              tb->
 770                                              rbytes) << (is_indirect_le_ih(ih)
 771                                                          ? tb->tb_sb->
 772                                                          s_blocksize_bits -
 773                                                          UNFM_P_SHIFT : 0));
 774                                        set_le_ih_k_offset(ih, offset);
 775                                        put_ih_item_len(ih, tb->rbytes);
 776                                        /* Insert part of the item into R[0] */
 777                                        buffer_info_init_right(tb, &bi);
 778                                        if ((old_len - tb->rbytes) > zeros_num) {
 779                                                r_zeros_number = 0;
 780                                                r_body =
 781                                                    body + (old_len -
 782                                                            tb->rbytes) -
 783                                                    zeros_num;
 784                                        } else {
 785                                                r_body = body;
 786                                                r_zeros_number =
 787                                                    zeros_num - (old_len -
 788                                                                 tb->rbytes);
 789                                                zeros_num -= r_zeros_number;
 790                                        }
 791
 792                                        leaf_insert_into_buf(&bi, 0, ih, r_body,
 793                                                             r_zeros_number);
 794
 795                                        /* Replace right delimiting key by first key in R[0] */
 796                                        replace_key(tb, tb->CFR[0], tb->rkey[0],
 797                                                    tb->R[0], 0);
 798
 799                                        /* Calculate key component and item length to insert into S[0] */
 800                                        set_le_ih_k_offset(ih, old_key_comp);
 801                                        put_ih_item_len(ih,
 802                                                        old_len - tb->rbytes);
 803
 804                                        tb->insert_size[0] -= tb->rbytes;
 805
 806                                } else {        /* whole new item falls into R[0] */
 807
 808                                        /* Shift rnum[0]-1 items to R[0] */
 809                                        ret_val =
 810                                            leaf_shift_right(tb,
 811                                                             tb->rnum[0] - 1,
 812                                                             tb->rbytes);
 813                                        /* Insert new item into R[0] */
 814                                        buffer_info_init_right(tb, &bi);
 815                                        leaf_insert_into_buf(&bi,
 816                                                             item_pos - n +
 817                                                             tb->rnum[0] - 1,
 818                                                             ih, body,
 819                                                             zeros_num);
 820
 821                                        if (item_pos - n + tb->rnum[0] - 1 == 0) {
 822                                                replace_key(tb, tb->CFR[0],
 823                                                            tb->rkey[0],
 824                                                            tb->R[0], 0);
 825
 826                                        }
 827                                        zeros_num = tb->insert_size[0] = 0;
 828                                }
 829                        } else {        /* new item or part of it doesn't fall into R[0] */
 830
 831                                leaf_shift_right(tb, tb->rnum[0], tb->rbytes);
 832                        }
 833                        break;
 834
 835                case M_PASTE:   /* append item */
 836
 837                        if (n - tb->rnum[0] <= item_pos) {      /* pasted item or part of it falls to R[0] */
 838                                if (item_pos == n - tb->rnum[0] && tb->rbytes != -1) {  /* we must shift the part of the appended item */
 839                                        if (is_direntry_le_ih(B_N_PITEM_HEAD(tbS0, item_pos))) {        /* we append to directory item */
 840                                                int entry_count;
 841
 842                                                RFALSE(zeros_num,
 843                                                       "PAP-12145: invalid parameter in case of a directory");
 844                                                entry_count =
 845                                                    I_ENTRY_COUNT(B_N_PITEM_HEAD
 846                                                                  (tbS0,
 847                                                                   item_pos));
 848                                                if (entry_count - tb->rbytes <
 849                                                    pos_in_item)
 850                                                        /* new directory entry falls into R[0] */
 851                                                {
 852                                                        int paste_entry_position;
 853
 854                                                        RFALSE(tb->rbytes - 1 >=
 855                                                               entry_count
 856                                                               || !tb->
 857                                                               insert_size[0],
 858                                                               "PAP-12150: no enough of entries to shift to R[0]: rbytes=%d, entry_count=%d",
 859                                                               tb->rbytes,
 860                                                               entry_count);
 861                                                        /* Shift rnum[0]-1 items in whole. Shift rbytes-1 directory entries from directory item number rnum[0] */
 862                                                        leaf_shift_right(tb,
 863                                                                         tb->
 864                                                                         rnum
 865                                                                         [0],
 866                                                                         tb->
 867                                                                         rbytes
 868                                                                         - 1);
 869                                                        /* Paste given directory entry to directory item */
 870                                                        paste_entry_position =
 871                                                            pos_in_item -
 872                                                            entry_count +
 873                                                            tb->rbytes - 1;
 874                                                        buffer_info_init_right(tb, &bi);
 875                                                        leaf_paste_in_buffer
 876                                                            (&bi, 0,
 877                                                             paste_entry_position,
 878                                                             tb->insert_size[0],
 879                                                             body, zeros_num);
 880                                                        /* paste entry */
 881                                                        leaf_paste_entries(&bi,
 882                                                                           0,
 883                                                                           paste_entry_position,
 884                                                                           1,
 885                                                                           (struct
 886                                                                            reiserfs_de_head
 887                                                                            *)
 888                                                                           body,
 889                                                                           body
 890                                                                           +
 891                                                                           DEH_SIZE,
 892                                                                           tb->
 893                                                                           insert_size
 894                                                                           [0]
 895                                                            );
 896
 897                                                        if (paste_entry_position
 898                                                            == 0) {
 899                                                                /* change delimiting keys */
 900                                                                replace_key(tb,
 901                                                                            tb->
 902                                                                            CFR
 903                                                                            [0],
 904                                                                            tb->
 905                                                                            rkey
 906                                                                            [0],
 907                                                                            tb->
 908                                                                            R
 909                                                                            [0],
 910                                                                            0);
 911                                                        }
 912
 913                                                        tb->insert_size[0] = 0;
 914                                                        pos_in_item++;
 915                                                } else {        /* new directory entry doesn't fall into R[0] */
 916
 917                                                        leaf_shift_right(tb,
 918                                                                         tb->
 919                                                                         rnum
 920                                                                         [0],
 921                                                                         tb->
 922                                                                         rbytes);
 923                                                }
 924                                        } else {        /* regular object */
 925
 926                                                int n_shift, n_rem,
 927                                                    r_zeros_number;
 928                                                const char *r_body;
 929
 930                                                /* Calculate number of bytes which must be shifted from appended item */
 931                                                if ((n_shift =
 932                                                     tb->rbytes -
 933                                                     tb->insert_size[0]) < 0)
 934                                                        n_shift = 0;
 935
 936                                                RFALSE(pos_in_item !=
 937                                                       ih_item_len
 938                                                       (B_N_PITEM_HEAD
 939                                                        (tbS0, item_pos)),
 940                                                       "PAP-12155: invalid position to paste. ih_item_len=%d, pos_in_item=%d",
 941                                                       pos_in_item,
 942                                                       ih_item_len
 943                                                       (B_N_PITEM_HEAD
 944                                                        (tbS0, item_pos)));
 945
 946                                                leaf_shift_right(tb,
 947                                                                 tb->rnum[0],
 948                                                                 n_shift);
 949                                                /* Calculate number of bytes which must remain in body after appending to R[0] */
 950                                                if ((n_rem =
 951                                                     tb->insert_size[0] -
 952                                                     tb->rbytes) < 0)
 953                                                        n_rem = 0;
 954
 955                                                {
 956                                                        int version;
 957                                                        unsigned long temp_rem =
 958                                                            n_rem;
 959
 960                                                        version =
 961                                                            ih_version
 962                                                            (B_N_PITEM_HEAD
 963                                                             (tb->R[0], 0));
 964                                                        if (is_indirect_le_key
 965                                                            (version,
 966                                                             B_N_PKEY(tb->R[0],
 967                                                                      0))) {
 968                                                                temp_rem =
 969                                                                    n_rem <<
 970                                                                    (tb->tb_sb->
 971                                                                     s_blocksize_bits
 972                                                                     -
 973                                                                     UNFM_P_SHIFT);
 974                                                        }
 975                                                        set_le_key_k_offset
 976                                                            (version,
 977                                                             B_N_PKEY(tb->R[0],
 978                                                                      0),
 979                                                             le_key_k_offset
 980                                                             (version,
 981                                                              B_N_PKEY(tb->R[0],
 982                                                                       0)) +
 983                                                             temp_rem);
 984                                                        set_le_key_k_offset
 985                                                            (version,
 986                                                             B_N_PDELIM_KEY(tb->
 987                                                                            CFR
 988                                                                            [0],
 989                                                                            tb->
 990                                                                            rkey
 991                                                                            [0]),
 992                                                             le_key_k_offset
 993                                                             (version,
 994                                                              B_N_PDELIM_KEY
 995                                                              (tb->CFR[0],
 996                                                               tb->rkey[0])) +
 997                                                             temp_rem);
 998                                                }
 999/*                k_offset (B_N_PKEY(tb->R[0],0)) += n_rem;
1000                  k_offset (B_N_PDELIM_KEY(tb->CFR[0],tb->rkey[0])) += n_rem;*/
1001                                                do_balance_mark_internal_dirty
1002                                                    (tb, tb->CFR[0], 0);
1003
1004                                                /* Append part of body into R[0] */
1005                                                buffer_info_init_right(tb, &bi);
1006                                                if (n_rem > zeros_num) {
1007                                                        r_zeros_number = 0;
1008                                                        r_body =
1009                                                            body + n_rem -
1010                                                            zeros_num;
1011                                                } else {
1012                                                        r_body = body;
1013                                                        r_zeros_number =
1014                                                            zeros_num - n_rem;
1015                                                        zeros_num -=
1016                                                            r_zeros_number;
1017                                                }
1018
1019                                                leaf_paste_in_buffer(&bi, 0,
1020                                                                     n_shift,
1021                                                                     tb->
1022                                                                     insert_size
1023                                                                     [0] -
1024                                                                     n_rem,
1025                                                                     r_body,
1026                                                                     r_zeros_number);
1027
1028                                                if (is_indirect_le_ih
1029                                                    (B_N_PITEM_HEAD
1030                                                     (tb->R[0], 0))) {
1031#if 0
1032                                                        RFALSE(n_rem,
1033                                                               "PAP-12160: paste more than one unformatted node pointer");
1034#endif
1035                                                        set_ih_free_space
1036                                                            (B_N_PITEM_HEAD
1037                                                             (tb->R[0], 0), 0);
1038                                                }
1039                                                tb->insert_size[0] = n_rem;
1040                                                if (!n_rem)
1041                                                        pos_in_item++;
1042                                        }
1043                                } else {        /* pasted item in whole falls into R[0] */
1044
1045                                        struct item_head *pasted;
1046
1047                                        ret_val =
1048                                            leaf_shift_right(tb, tb->rnum[0],
1049                                                             tb->rbytes);
1050                                        /* append item in R[0] */
1051                                        if (pos_in_item >= 0) {
1052                                                buffer_info_init_right(tb, &bi);
1053                                                leaf_paste_in_buffer(&bi,
1054                                                                     item_pos -
1055                                                                     n +
1056                                                                     tb->
1057                                                                     rnum[0],
1058                                                                     pos_in_item,
1059                                                                     tb->
1060                                                                     insert_size
1061                                                                     [0], body,
1062                                                                     zeros_num);
1063                                        }
1064
1065                                        /* paste new entry, if item is directory item */
1066                                        pasted =
1067                                            B_N_PITEM_HEAD(tb->R[0],
1068                                                           item_pos - n +
1069                                                           tb->rnum[0]);
1070                                        if (is_direntry_le_ih(pasted)
1071                                            && pos_in_item >= 0) {
1072                                                leaf_paste_entries(&bi,
1073                                                                   item_pos -
1074                                                                   n +
1075                                                                   tb->rnum[0],
1076                                                                   pos_in_item,
1077                                                                   1,
1078                                                                   (struct
1079                                                                    reiserfs_de_head
1080                                                                    *)body,
1081                                                                   body +
1082                                                                   DEH_SIZE,
1083                                                                   tb->
1084                                                                   insert_size
1085                                                                   [0]
1086                                                    );
1087                                                if (!pos_in_item) {
1088
1089                                                        RFALSE(item_pos - n +
1090                                                               tb->rnum[0],
1091                                                               "PAP-12165: directory item must be first item of node when pasting is in 0th position");
1092
1093                                                        /* update delimiting keys */
1094                                                        replace_key(tb,
1095                                                                    tb->CFR[0],
1096                                                                    tb->rkey[0],
1097                                                                    tb->R[0],
1098                                                                    0);
1099                                                }
1100                                        }
1101
1102                                        if (is_indirect_le_ih(pasted))
1103                                                set_ih_free_space(pasted, 0);
1104                                        zeros_num = tb->insert_size[0] = 0;
1105                                }
1106                        } else {        /* new item doesn't fall into R[0] */
1107
1108                                leaf_shift_right(tb, tb->rnum[0], tb->rbytes);
1109                        }
1110                        break;
1111                default:        /* cases d and t */
1112                        reiserfs_panic(tb->tb_sb, "PAP-12175",
1113                                       "rnum > 0: unexpected mode: %s(%d)",
1114                                       (flag ==
1115                                        M_DELETE) ? "DELETE" : ((flag ==
1116                                                                 M_CUT) ? "CUT"
1117                                                                : "UNKNOWN"),
1118                                       flag);
1119                }
1120
1121        }
1122
1123        /* tb->rnum[0] > 0 */
1124        RFALSE(tb->blknum[0] > 3,
1125               "PAP-12180: blknum can not be %d. It must be <= 3",
1126               tb->blknum[0]);
1127        RFALSE(tb->blknum[0] < 0,
1128               "PAP-12185: blknum can not be %d. It must be >= 0",
1129               tb->blknum[0]);
1130
1131        /* if while adding to a node we discover that it is possible to split
1132           it in two, and merge the left part into the left neighbor and the
1133           right part into the right neighbor, eliminating the node */
1134        if (tb->blknum[0] == 0) {       /* node S[0] is empty now */
1135
1136                RFALSE(!tb->lnum[0] || !tb->rnum[0],
1137                       "PAP-12190: lnum and rnum must not be zero");
1138                /* if insertion was done before 0-th position in R[0], right
1139                   delimiting key of the tb->L[0]'s and left delimiting key are
1140                   not set correctly */
1141                if (tb->CFL[0]) {
1142                        if (!tb->CFR[0])
1143                                reiserfs_panic(tb->tb_sb, "vs-12195",
1144                                               "CFR not initialized");
1145                        copy_key(B_N_PDELIM_KEY(tb->CFL[0], tb->lkey[0]),
1146                                 B_N_PDELIM_KEY(tb->CFR[0], tb->rkey[0]));
1147                        do_balance_mark_internal_dirty(tb, tb->CFL[0], 0);
1148                }
1149
1150                reiserfs_invalidate_buffer(tb, tbS0);
1151                return 0;
1152        }
1153
1154        /* Fill new nodes that appear in place of S[0] */
1155
1156        /* I am told that this copying is because we need an array to enable
1157           the looping code. -Hans */
1158        snum[0] = tb->s1num, snum[1] = tb->s2num;
1159        sbytes[0] = tb->s1bytes;
1160        sbytes[1] = tb->s2bytes;
1161        for (i = tb->blknum[0] - 2; i >= 0; i--) {
1162
1163                RFALSE(!snum[i], "PAP-12200: snum[%d] == %d. Must be > 0", i,
1164                       snum[i]);
1165
1166                /* here we shift from S to S_new nodes */
1167
1168                S_new[i] = get_FEB(tb);
1169
1170                /* initialized block type and tree level */
1171                set_blkh_level(B_BLK_HEAD(S_new[i]), DISK_LEAF_NODE_LEVEL);
1172
1173                n = B_NR_ITEMS(tbS0);
1174
1175                switch (flag) {
1176                case M_INSERT:  /* insert item */
1177
1178                        if (n - snum[i] < item_pos) {   /* new item or it's part falls to first new node S_new[i] */
1179                                if (item_pos == n - snum[i] + 1 && sbytes[i] != -1) {   /* part of new item falls into S_new[i] */
1180                                        int old_key_comp, old_len,
1181                                            r_zeros_number;
1182                                        const char *r_body;
1183                                        int version;
1184
1185                                        /* Move snum[i]-1 items from S[0] to S_new[i] */
1186                                        leaf_move_items(LEAF_FROM_S_TO_SNEW, tb,
1187                                                        snum[i] - 1, -1,
1188                                                        S_new[i]);
1189                                        /* Remember key component and item length */
1190                                        version = ih_version(ih);
1191                                        old_key_comp = le_ih_k_offset(ih);
1192                                        old_len = ih_item_len(ih);
1193
1194                                        /* Calculate key component and item length to insert into S_new[i] */
1195                                        set_le_ih_k_offset(ih,
1196                                                           le_ih_k_offset(ih) +
1197                                                           ((old_len -
1198                                                             sbytes[i]) <<
1199                                                            (is_indirect_le_ih
1200                                                             (ih) ? tb->tb_sb->
1201                                                             s_blocksize_bits -
1202                                                             UNFM_P_SHIFT :
1203                                                             0)));
1204
1205                                        put_ih_item_len(ih, sbytes[i]);
1206
1207                                        /* Insert part of the item into S_new[i] before 0-th item */
1208                                        buffer_info_init_bh(tb, &bi, S_new[i]);
1209
1210                                        if ((old_len - sbytes[i]) > zeros_num) {
1211                                                r_zeros_number = 0;
1212                                                r_body =
1213                                                    body + (old_len -
1214                                                            sbytes[i]) -
1215                                                    zeros_num;
1216                                        } else {
1217                                                r_body = body;
1218                                                r_zeros_number =
1219                                                    zeros_num - (old_len -
1220                                                                 sbytes[i]);
1221                                                zeros_num -= r_zeros_number;
1222                                        }
1223
1224                                        leaf_insert_into_buf(&bi, 0, ih, r_body,
1225                                                             r_zeros_number);
1226
1227                                        /* Calculate key component and item length to insert into S[i] */
1228                                        set_le_ih_k_offset(ih, old_key_comp);
1229                                        put_ih_item_len(ih,
1230                                                        old_len - sbytes[i]);
1231                                        tb->insert_size[0] -= sbytes[i];
1232                                } else {        /* whole new item falls into S_new[i] */
1233
1234                                        /* Shift snum[0] - 1 items to S_new[i] (sbytes[i] of split item) */
1235                                        leaf_move_items(LEAF_FROM_S_TO_SNEW, tb,
1236                                                        snum[i] - 1, sbytes[i],
1237                                                        S_new[i]);
1238
1239                                        /* Insert new item into S_new[i] */
1240                                        buffer_info_init_bh(tb, &bi, S_new[i]);
1241                                        leaf_insert_into_buf(&bi,
1242                                                             item_pos - n +
1243                                                             snum[i] - 1, ih,
1244                                                             body, zeros_num);
1245
1246                                        zeros_num = tb->insert_size[0] = 0;
1247                                }
1248                        }
1249
1250                        else {  /* new item or it part don't falls into S_new[i] */
1251
1252                                leaf_move_items(LEAF_FROM_S_TO_SNEW, tb,
1253                                                snum[i], sbytes[i], S_new[i]);
1254                        }
1255                        break;
1256
1257                case M_PASTE:   /* append item */
1258
1259                        if (n - snum[i] <= item_pos) {  /* pasted item or part if it falls to S_new[i] */
1260                                if (item_pos == n - snum[i] && sbytes[i] != -1) {       /* we must shift part of the appended item */
1261                                        struct item_head *aux_ih;
1262
1263                                        RFALSE(ih, "PAP-12210: ih must be 0");
1264
1265                                        aux_ih = B_N_PITEM_HEAD(tbS0, item_pos);
1266                                        if (is_direntry_le_ih(aux_ih)) {
1267                                                /* we append to directory item */
1268
1269                                                int entry_count;
1270
1271                                                entry_count =
1272                                                    ih_entry_count(aux_ih);
1273
1274                                                if (entry_count - sbytes[i] <
1275                                                    pos_in_item
1276                                                    && pos_in_item <=
1277                                                    entry_count) {
1278                                                        /* new directory entry falls into S_new[i] */
1279
1280                                                        RFALSE(!tb->
1281                                                               insert_size[0],
1282                                                               "PAP-12215: insert_size is already 0");
1283                                                        RFALSE(sbytes[i] - 1 >=
1284                                                               entry_count,
1285                                                               "PAP-12220: there are no so much entries (%d), only %d",
1286                                                               sbytes[i] - 1,
1287                                                               entry_count);
1288
1289                                                        /* Shift snum[i]-1 items in whole. Shift sbytes[i] directory entries from directory item number snum[i] */
1290                                                        leaf_move_items
1291                                                            (LEAF_FROM_S_TO_SNEW,
1292                                                             tb, snum[i],
1293                                                             sbytes[i] - 1,
1294                                                             S_new[i]);
1295                                                        /* Paste given directory entry to directory item */
1296                                                        buffer_info_init_bh(tb, &bi, S_new[i]);
1297                                                        leaf_paste_in_buffer
1298                                                            (&bi, 0,
1299                                                             pos_in_item -
1300                                                             entry_count +
1301                                                             sbytes[i] - 1,
1302                                                             tb->insert_size[0],
1303                                                             body, zeros_num);
1304                                                        /* paste new directory entry */
1305                                                        leaf_paste_entries(&bi,
1306                                                                           0,
1307                                                                           pos_in_item
1308                                                                           -
1309                                                                           entry_count
1310                                                                           +
1311                                                                           sbytes
1312                                                                           [i] -
1313                                                                           1, 1,
1314                                                                           (struct
1315                                                                            reiserfs_de_head
1316                                                                            *)
1317                                                                           body,
1318                                                                           body
1319                                                                           +
1320                                                                           DEH_SIZE,
1321                                                                           tb->
1322                                                                           insert_size
1323                                                                           [0]
1324                                                            );
1325                                                        tb->insert_size[0] = 0;
1326                                                        pos_in_item++;
1327                                                } else {        /* new directory entry doesn't fall into S_new[i] */
1328                                                        leaf_move_items
1329                                                            (LEAF_FROM_S_TO_SNEW,
1330                                                             tb, snum[i],
1331                                                             sbytes[i],
1332                                                             S_new[i]);
1333                                                }
1334                                        } else {        /* regular object */
1335
1336                                                int n_shift, n_rem,
1337                                                    r_zeros_number;
1338                                                const char *r_body;
1339
1340                                                RFALSE(pos_in_item !=
1341                                                       ih_item_len
1342                                                       (B_N_PITEM_HEAD
1343                                                        (tbS0, item_pos))
1344                                                       || tb->insert_size[0] <=
1345                                                       0,
1346                                                       "PAP-12225: item too short or insert_size <= 0");
1347
1348                                                /* Calculate number of bytes which must be shifted from appended item */
1349                                                n_shift =
1350                                                    sbytes[i] -
1351                                                    tb->insert_size[0];
1352                                                if (n_shift < 0)
1353                                                        n_shift = 0;
1354                                                leaf_move_items
1355                                                    (LEAF_FROM_S_TO_SNEW, tb,
1356                                                     snum[i], n_shift,
1357                                                     S_new[i]);
1358
1359                                                /* Calculate number of bytes which must remain in body after append to S_new[i] */
1360                                                n_rem =
1361                                                    tb->insert_size[0] -
1362                                                    sbytes[i];
1363                                                if (n_rem < 0)
1364                                                        n_rem = 0;
1365                                                /* Append part of body into S_new[0] */
1366                                                buffer_info_init_bh(tb, &bi, S_new[i]);
1367                                                if (n_rem > zeros_num) {
1368                                                        r_zeros_number = 0;
1369                                                        r_body =
1370                                                            body + n_rem -
1371                                                            zeros_num;
1372                                                } else {
1373                                                        r_body = body;
1374                                                        r_zeros_number =
1375                                                            zeros_num - n_rem;
1376                                                        zeros_num -=
1377                                                            r_zeros_number;
1378                                                }
1379
1380                                                leaf_paste_in_buffer(&bi, 0,
1381                                                                     n_shift,
1382                                                                     tb->
1383                                                                     insert_size
1384                                                                     [0] -
1385                                                                     n_rem,
1386                                                                     r_body,
1387                                                                     r_zeros_number);
1388                                                {
1389                                                        struct item_head *tmp;
1390
1391                                                        tmp =
1392                                                            B_N_PITEM_HEAD(S_new
1393                                                                           [i],
1394                                                                           0);
1395                                                        if (is_indirect_le_ih
1396                                                            (tmp)) {
1397                                                                set_ih_free_space
1398                                                                    (tmp, 0);
1399                                                                set_le_ih_k_offset
1400                                                                    (tmp,
1401                                                                     le_ih_k_offset
1402                                                                     (tmp) +
1403                                                                     (n_rem <<
1404                                                                      (tb->
1405                                                                       tb_sb->
1406                                                                       s_blocksize_bits
1407                                                                       -
1408                                                                       UNFM_P_SHIFT)));
1409                                                        } else {
1410                                                                set_le_ih_k_offset
1411                                                                    (tmp,
1412                                                                     le_ih_k_offset
1413                                                                     (tmp) +
1414                                                                     n_rem);
1415                                                        }
1416                                                }
1417
1418                                                tb->insert_size[0] = n_rem;
1419                                                if (!n_rem)
1420                                                        pos_in_item++;
1421                                        }
1422                                } else
1423                                        /* item falls wholly into S_new[i] */
1424                                {
1425                                        int leaf_mi;
1426                                        struct item_head *pasted;
1427
1428#ifdef CONFIG_REISERFS_CHECK
1429                                        struct item_head *ih_check =
1430                                            B_N_PITEM_HEAD(tbS0, item_pos);
1431
1432                                        if (!is_direntry_le_ih(ih_check)
1433                                            && (pos_in_item != ih_item_len(ih_check)
1434                                                || tb->insert_size[0] <= 0))
1435                                                reiserfs_panic(tb->tb_sb,
1436                                                             "PAP-12235",
1437                                                             "pos_in_item "
1438                                                             "must be equal "
1439                                                             "to ih_item_len");
1440#endif                          /* CONFIG_REISERFS_CHECK */
1441
1442                                        leaf_mi =
1443                                            leaf_move_items(LEAF_FROM_S_TO_SNEW,
1444                                                            tb, snum[i],
1445                                                            sbytes[i],
1446                                                            S_new[i]);
1447
1448                                        RFALSE(leaf_mi,
1449                                               "PAP-12240: unexpected value returned by leaf_move_items (%d)",
1450                                               leaf_mi);
1451
1452                                        /* paste into item */
1453                                        buffer_info_init_bh(tb, &bi, S_new[i]);
1454                                        leaf_paste_in_buffer(&bi,
1455                                                             item_pos - n +
1456                                                             snum[i],
1457                                                             pos_in_item,
1458                                                             tb->insert_size[0],
1459                                                             body, zeros_num);
1460
1461                                        pasted =
1462                                            B_N_PITEM_HEAD(S_new[i],
1463                                                           item_pos - n +
1464                                                           snum[i]);
1465                                        if (is_direntry_le_ih(pasted)) {
1466                                                leaf_paste_entries(&bi,
1467                                                                   item_pos -
1468                                                                   n + snum[i],
1469                                                                   pos_in_item,
1470                                                                   1,
1471                                                                   (struct
1472                                                                    reiserfs_de_head
1473                                                                    *)body,
1474                                                                   body +
1475                                                                   DEH_SIZE,
1476                                                                   tb->
1477                                                                   insert_size
1478                                                                   [0]
1479                                                    );
1480                                        }
1481
1482                                        /* if we paste to indirect item update ih_free_space */
1483                                        if (is_indirect_le_ih(pasted))
1484                                                set_ih_free_space(pasted, 0);
1485                                        zeros_num = tb->insert_size[0] = 0;
1486                                }
1487                        }
1488
1489                        else {  /* pasted item doesn't fall into S_new[i] */
1490
1491                                leaf_move_items(LEAF_FROM_S_TO_SNEW, tb,
1492                                                snum[i], sbytes[i], S_new[i]);
1493                        }
1494                        break;
1495                default:        /* cases d and t */
1496                        reiserfs_panic(tb->tb_sb, "PAP-12245",
1497                                       "blknum > 2: unexpected mode: %s(%d)",
1498                                       (flag ==
1499                                        M_DELETE) ? "DELETE" : ((flag ==
1500                                                                 M_CUT) ? "CUT"
1501                                                                : "UNKNOWN"),
1502                                       flag);
1503                }
1504
1505                memcpy(insert_key + i, B_N_PKEY(S_new[i], 0), KEY_SIZE);
1506                insert_ptr[i] = S_new[i];
1507
1508                RFALSE(!buffer_journaled(S_new[i])
1509                       || buffer_journal_dirty(S_new[i])
1510                       || buffer_dirty(S_new[i]), "PAP-12247: S_new[%d] : (%b)",
1511                       i, S_new[i]);
1512        }
1513
1514        /* if the affected item was not wholly shifted then we perform all necessary operations on that part or whole of the
1515           affected item which remains in S */
1516        if (0 <= item_pos && item_pos < tb->s0num) {    /* if we must insert or append into buffer S[0] */
1517
1518                switch (flag) {
1519                case M_INSERT:  /* insert item into S[0] */
1520                        buffer_info_init_tbS0(tb, &bi);
1521                        leaf_insert_into_buf(&bi, item_pos, ih, body,
1522                                             zeros_num);
1523
1524                        /* If we insert the first key change the delimiting key */
1525                        if (item_pos == 0) {
1526                                if (tb->CFL[0]) /* can be 0 in reiserfsck */
1527                                        replace_key(tb, tb->CFL[0], tb->lkey[0],
1528                                                    tbS0, 0);
1529
1530                        }
1531                        break;
1532
1533                case M_PASTE:{  /* append item in S[0] */
1534                                struct item_head *pasted;
1535
1536                                pasted = B_N_PITEM_HEAD(tbS0, item_pos);
1537                                /* when directory, may be new entry already pasted */
1538                                if (is_direntry_le_ih(pasted)) {
1539                                        if (pos_in_item >= 0 &&
1540                                            pos_in_item <=
1541                                            ih_entry_count(pasted)) {
1542
1543                                                RFALSE(!tb->insert_size[0],
1544                                                       "PAP-12260: insert_size is 0 already");
1545
1546                                                /* prepare space */
1547                                                buffer_info_init_tbS0(tb, &bi);
1548                                                leaf_paste_in_buffer(&bi,
1549                                                                     item_pos,
1550                                                                     pos_in_item,
1551                                                                     tb->
1552                                                                     insert_size
1553                                                                     [0], body,
1554                                                                     zeros_num);
1555
1556                                                /* paste entry */
1557                                                leaf_paste_entries(&bi,
1558                                                                   item_pos,
1559                                                                   pos_in_item,
1560                                                                   1,
1561                                                                   (struct
1562                                                                    reiserfs_de_head
1563                                                                    *)body,
1564                                                                   body +
1565                                                                   DEH_SIZE,
1566                                                                   tb->
1567                                                                   insert_size
1568                                                                   [0]
1569                                                    );
1570                                                if (!item_pos && !pos_in_item) {
1571                                                        RFALSE(!tb->CFL[0]
1572                                                               || !tb->L[0],
1573                                                               "PAP-12270: CFL[0]/L[0] must be specified");
1574                                                        if (tb->CFL[0]) {
1575                                                                replace_key(tb,
1576                                                                            tb->
1577                                                                            CFL
1578                                                                            [0],
1579                                                                            tb->
1580                                                                            lkey
1581                                                                            [0],
1582                                                                            tbS0,
1583                                                                            0);
1584
1585                                                        }
1586                                                }
1587                                                tb->insert_size[0] = 0;
1588                                        }
1589                                } else {        /* regular object */
1590                                        if (pos_in_item == ih_item_len(pasted)) {
1591
1592                                                RFALSE(tb->insert_size[0] <= 0,
1593                                                       "PAP-12275: insert size must not be %d",
1594                                                       tb->insert_size[0]);
1595                                                buffer_info_init_tbS0(tb, &bi);
1596                                                leaf_paste_in_buffer(&bi,
1597                                                                     item_pos,
1598                                                                     pos_in_item,
1599                                                                     tb->
1600                                                                     insert_size
1601                                                                     [0], body,
1602                                                                     zeros_num);
1603
1604                                                if (is_indirect_le_ih(pasted)) {
1605#if 0
1606                                                        RFALSE(tb->
1607                                                               insert_size[0] !=
1608                                                               UNFM_P_SIZE,
1609                                                               "PAP-12280: insert_size for indirect item must be %d, not %d",
1610                                                               UNFM_P_SIZE,
1611                                                               tb->
1612                                                               insert_size[0]);
1613#endif
1614                                                        set_ih_free_space
1615                                                            (pasted, 0);
1616                                                }
1617                                                tb->insert_size[0] = 0;
1618                                        }
1619#ifdef CONFIG_REISERFS_CHECK
1620                                        else {
1621                                                if (tb->insert_size[0]) {
1622                                                        print_cur_tb("12285");
1623                                                        reiserfs_panic(tb->
1624                                                                       tb_sb,
1625                                                            "PAP-12285",
1626                                                            "insert_size "
1627                                                            "must be 0 "
1628                                                            "(%d)",
1629                                                            tb->insert_size[0]);
1630                                                }
1631                                        }
1632#endif                          /* CONFIG_REISERFS_CHECK */
1633
1634                                }
1635                        }       /* case M_PASTE: */
1636                }
1637        }
1638#ifdef CONFIG_REISERFS_CHECK
1639        if (flag == M_PASTE && tb->insert_size[0]) {
1640                print_cur_tb("12290");
1641                reiserfs_panic(tb->tb_sb,
1642                               "PAP-12290", "insert_size is still not 0 (%d)",
1643                               tb->insert_size[0]);
1644        }
1645#endif                          /* CONFIG_REISERFS_CHECK */
1646        return 0;
1647}                               /* Leaf level of the tree is balanced (end of balance_leaf) */
1648
1649/* Make empty node */
1650void make_empty_node(struct buffer_info *bi)
1651{
1652        struct block_head *blkh;
1653
1654        RFALSE(bi->bi_bh == NULL, "PAP-12295: pointer to the buffer is NULL");
1655
1656        blkh = B_BLK_HEAD(bi->bi_bh);
1657        set_blkh_nr_item(blkh, 0);
1658        set_blkh_free_space(blkh, MAX_CHILD_SIZE(bi->bi_bh));
1659
1660        if (bi->bi_parent)
1661                B_N_CHILD(bi->bi_parent, bi->bi_position)->dc_size = 0; /* Endian safe if 0 */
1662}
1663
1664/* Get first empty buffer */
1665struct buffer_head *get_FEB(struct tree_balance *tb)
1666{
1667        int i;
1668        struct buffer_info bi;
1669
1670        for (i = 0; i < MAX_FEB_SIZE; i++)
1671                if (tb->FEB[i] != NULL)
1672                        break;
1673
1674        if (i == MAX_FEB_SIZE)
1675                reiserfs_panic(tb->tb_sb, "vs-12300", "FEB list is empty");
1676
1677        buffer_info_init_bh(tb, &bi, tb->FEB[i]);
1678        make_empty_node(&bi);
1679        set_buffer_uptodate(tb->FEB[i]);
1680        tb->used[i] = tb->FEB[i];
1681        tb->FEB[i] = NULL;
1682
1683        return tb->used[i];
1684}
1685
1686/* This is now used because reiserfs_free_block has to be able to
1687** schedule.
1688*/
1689static void store_thrown(struct tree_balance *tb, struct buffer_head *bh)
1690{
1691        int i;
1692
1693        if (buffer_dirty(bh))
1694                reiserfs_warning(tb->tb_sb, "reiserfs-12320",
1695                                 "called with dirty buffer");
1696        for (i = 0; i < ARRAY_SIZE(tb->thrown); i++)
1697                if (!tb->thrown[i]) {
1698                        tb->thrown[i] = bh;
1699                        get_bh(bh);     /* free_thrown puts this */
1700                        return;
1701                }
1702        reiserfs_warning(tb->tb_sb, "reiserfs-12321",
1703                         "too many thrown buffers");
1704}
1705
1706static void free_thrown(struct tree_balance *tb)
1707{
1708        int i;
1709        b_blocknr_t blocknr;
1710        for (i = 0; i < ARRAY_SIZE(tb->thrown); i++) {
1711                if (tb->thrown[i]) {
1712                        blocknr = tb->thrown[i]->b_blocknr;
1713                        if (buffer_dirty(tb->thrown[i]))
1714                                reiserfs_warning(tb->tb_sb, "reiserfs-12322",
1715                                                 "called with dirty buffer %d",
1716                                                 blocknr);
1717                        brelse(tb->thrown[i]);  /* incremented in store_thrown */
1718                        reiserfs_free_block(tb->transaction_handle, NULL,
1719                                            blocknr, 0);
1720                }
1721        }
1722}
1723
1724void reiserfs_invalidate_buffer(struct tree_balance *tb, struct buffer_head *bh)
1725{
1726        struct block_head *blkh;
1727        blkh = B_BLK_HEAD(bh);
1728        set_blkh_level(blkh, FREE_LEVEL);
1729        set_blkh_nr_item(blkh, 0);
1730
1731        clear_buffer_dirty(bh);
1732        store_thrown(tb, bh);
1733}
1734
1735/* Replace n_dest'th key in buffer dest by n_src'th key of buffer src.*/
1736void replace_key(struct tree_balance *tb, struct buffer_head *dest, int n_dest,
1737                 struct buffer_head *src, int n_src)
1738{
1739
1740        RFALSE(dest == NULL || src == NULL,
1741               "vs-12305: source or destination buffer is 0 (src=%p, dest=%p)",
1742               src, dest);
1743        RFALSE(!B_IS_KEYS_LEVEL(dest),
1744               "vs-12310: invalid level (%z) for destination buffer. dest must be leaf",
1745               dest);
1746        RFALSE(n_dest < 0 || n_src < 0,
1747               "vs-12315: src(%d) or dest(%d) key number < 0", n_src, n_dest);
1748        RFALSE(n_dest >= B_NR_ITEMS(dest) || n_src >= B_NR_ITEMS(src),
1749               "vs-12320: src(%d(%d)) or dest(%d(%d)) key number is too big",
1750               n_src, B_NR_ITEMS(src), n_dest, B_NR_ITEMS(dest));
1751
1752        if (B_IS_ITEMS_LEVEL(src))
1753                /* source buffer contains leaf node */
1754                memcpy(B_N_PDELIM_KEY(dest, n_dest), B_N_PITEM_HEAD(src, n_src),
1755                       KEY_SIZE);
1756        else
1757                memcpy(B_N_PDELIM_KEY(dest, n_dest), B_N_PDELIM_KEY(src, n_src),
1758                       KEY_SIZE);
1759
1760        do_balance_mark_internal_dirty(tb, dest, 0);
1761}
1762
1763int get_left_neighbor_position(struct tree_balance *tb, int h)
1764{
1765        int Sh_position = PATH_H_POSITION(tb->tb_path, h + 1);
1766
1767        RFALSE(PATH_H_PPARENT(tb->tb_path, h) == NULL || tb->FL[h] == NULL,
1768               "vs-12325: FL[%d](%p) or F[%d](%p) does not exist",
1769               h, tb->FL[h], h, PATH_H_PPARENT(tb->tb_path, h));
1770
1771        if (Sh_position == 0)
1772                return B_NR_ITEMS(tb->FL[h]);
1773        else
1774                return Sh_position - 1;
1775}
1776
1777int get_right_neighbor_position(struct tree_balance *tb, int h)
1778{
1779        int Sh_position = PATH_H_POSITION(tb->tb_path, h + 1);
1780
1781        RFALSE(PATH_H_PPARENT(tb->tb_path, h) == NULL || tb->FR[h] == NULL,
1782               "vs-12330: F[%d](%p) or FR[%d](%p) does not exist",
1783               h, PATH_H_PPARENT(tb->tb_path, h), h, tb->FR[h]);
1784
1785        if (Sh_position == B_NR_ITEMS(PATH_H_PPARENT(tb->tb_path, h)))
1786                return 0;
1787        else
1788                return Sh_position + 1;
1789}
1790
1791#ifdef CONFIG_REISERFS_CHECK
1792
1793int is_reusable(struct super_block *s, b_blocknr_t block, int bit_value);
1794static void check_internal_node(struct super_block *s, struct buffer_head *bh,
1795                                char *mes)
1796{
1797        struct disk_child *dc;
1798        int i;
1799
1800        RFALSE(!bh, "PAP-12336: bh == 0");
1801
1802        if (!bh || !B_IS_IN_TREE(bh))
1803                return;
1804
1805        RFALSE(!buffer_dirty(bh) &&
1806               !(buffer_journaled(bh) || buffer_journal_dirty(bh)),
1807               "PAP-12337: buffer (%b) must be dirty", bh);
1808        dc = B_N_CHILD(bh, 0);
1809
1810        for (i = 0; i <= B_NR_ITEMS(bh); i++, dc++) {
1811                if (!is_reusable(s, dc_block_number(dc), 1)) {
1812                        print_cur_tb(mes);
1813                        reiserfs_panic(s, "PAP-12338",
1814                                       "invalid child pointer %y in %b",
1815                                       dc, bh);
1816                }
1817        }
1818}
1819
1820static int locked_or_not_in_tree(struct tree_balance *tb,
1821                                  struct buffer_head *bh, char *which)
1822{
1823        if ((!buffer_journal_prepared(bh) && buffer_locked(bh)) ||
1824            !B_IS_IN_TREE(bh)) {
1825                reiserfs_warning(tb->tb_sb, "vs-12339", "%s (%b)", which, bh);
1826                return 1;
1827        }
1828        return 0;
1829}
1830
1831static int check_before_balancing(struct tree_balance *tb)
1832{
1833        int retval = 0;
1834
1835        if (REISERFS_SB(tb->tb_sb)->cur_tb) {
1836                reiserfs_panic(tb->tb_sb, "vs-12335", "suspect that schedule "
1837                               "occurred based on cur_tb not being null at "
1838                               "this point in code. do_balance cannot properly "
1839                               "handle concurrent tree accesses on a same "
1840                               "mount point.");
1841        }
1842
1843        /* double check that buffers that we will modify are unlocked. (fix_nodes should already have
1844           prepped all of these for us). */
1845        if (tb->lnum[0]) {
1846                retval |= locked_or_not_in_tree(tb, tb->L[0], "L[0]");
1847                retval |= locked_or_not_in_tree(tb, tb->FL[0], "FL[0]");
1848                retval |= locked_or_not_in_tree(tb, tb->CFL[0], "CFL[0]");
1849                check_leaf(tb->L[0]);
1850        }
1851        if (tb->rnum[0]) {
1852                retval |= locked_or_not_in_tree(tb, tb->R[0], "R[0]");
1853                retval |= locked_or_not_in_tree(tb, tb->FR[0], "FR[0]");
1854                retval |= locked_or_not_in_tree(tb, tb->CFR[0], "CFR[0]");
1855                check_leaf(tb->R[0]);
1856        }
1857        retval |= locked_or_not_in_tree(tb, PATH_PLAST_BUFFER(tb->tb_path),
1858                                        "S[0]");
1859        check_leaf(PATH_PLAST_BUFFER(tb->tb_path));
1860
1861        return retval;
1862}
1863
1864static void check_after_balance_leaf(struct tree_balance *tb)
1865{
1866        if (tb->lnum[0]) {
1867                if (B_FREE_SPACE(tb->L[0]) !=
1868                    MAX_CHILD_SIZE(tb->L[0]) -
1869                    dc_size(B_N_CHILD
1870                            (tb->FL[0], get_left_neighbor_position(tb, 0)))) {
1871                        print_cur_tb("12221");
1872                        reiserfs_panic(tb->tb_sb, "PAP-12355",
1873                                       "shift to left was incorrect");
1874                }
1875        }
1876        if (tb->rnum[0]) {
1877                if (B_FREE_SPACE(tb->R[0]) !=
1878                    MAX_CHILD_SIZE(tb->R[0]) -
1879                    dc_size(B_N_CHILD
1880                            (tb->FR[0], get_right_neighbor_position(tb, 0)))) {
1881                        print_cur_tb("12222");
1882                        reiserfs_panic(tb->tb_sb, "PAP-12360",
1883                                       "shift to right was incorrect");
1884                }
1885        }
1886        if (PATH_H_PBUFFER(tb->tb_path, 1) &&
1887            (B_FREE_SPACE(PATH_H_PBUFFER(tb->tb_path, 0)) !=
1888             (MAX_CHILD_SIZE(PATH_H_PBUFFER(tb->tb_path, 0)) -
1889              dc_size(B_N_CHILD(PATH_H_PBUFFER(tb->tb_path, 1),
1890                                PATH_H_POSITION(tb->tb_path, 1)))))) {
1891                int left = B_FREE_SPACE(PATH_H_PBUFFER(tb->tb_path, 0));
1892                int right = (MAX_CHILD_SIZE(PATH_H_PBUFFER(tb->tb_path, 0)) -
1893                             dc_size(B_N_CHILD(PATH_H_PBUFFER(tb->tb_path, 1),
1894                                               PATH_H_POSITION(tb->tb_path,
1895                                                               1))));
1896                print_cur_tb("12223");
1897                reiserfs_warning(tb->tb_sb, "reiserfs-12363",
1898                                 "B_FREE_SPACE (PATH_H_PBUFFER(tb->tb_path,0)) = %d; "
1899                                 "MAX_CHILD_SIZE (%d) - dc_size( %y, %d ) [%d] = %d",
1900                                 left,
1901                                 MAX_CHILD_SIZE(PATH_H_PBUFFER(tb->tb_path, 0)),
1902                                 PATH_H_PBUFFER(tb->tb_path, 1),
1903                                 PATH_H_POSITION(tb->tb_path, 1),
1904                                 dc_size(B_N_CHILD
1905                                         (PATH_H_PBUFFER(tb->tb_path, 1),
1906                                          PATH_H_POSITION(tb->tb_path, 1))),
1907                                 right);
1908                reiserfs_panic(tb->tb_sb, "PAP-12365", "S is incorrect");
1909        }
1910}
1911
1912static void check_leaf_level(struct tree_balance *tb)
1913{
1914        check_leaf(tb->L[0]);
1915        check_leaf(tb->R[0]);
1916        check_leaf(PATH_PLAST_BUFFER(tb->tb_path));
1917}
1918
1919static void check_internal_levels(struct tree_balance *tb)
1920{
1921        int h;
1922
1923        /* check all internal nodes */
1924        for (h = 1; tb->insert_size[h]; h++) {
1925                check_internal_node(tb->tb_sb, PATH_H_PBUFFER(tb->tb_path, h),
1926                                    "BAD BUFFER ON PATH");
1927                if (tb->lnum[h])
1928                        check_internal_node(tb->tb_sb, tb->L[h], "BAD L");
1929                if (tb->rnum[h])
1930                        check_internal_node(tb->tb_sb, tb->R[h], "BAD R");
1931        }
1932
1933}
1934
1935#endif
1936
1937/* Now we have all of the buffers that must be used in balancing of
1938   the tree.  We rely on the assumption that schedule() will not occur
1939   while do_balance works. ( Only interrupt handlers are acceptable.)
1940   We balance the tree according to the analysis made before this,
1941   using buffers already obtained.  For SMP support it will someday be
1942   necessary to add ordered locking of tb. */
1943
1944/* Some interesting rules of balancing:
1945
1946   we delete a maximum of two nodes per level per balancing: we never
1947   delete R, when we delete two of three nodes L, S, R then we move
1948   them into R.
1949
1950   we only delete L if we are deleting two nodes, if we delete only
1951   one node we delete S
1952
1953   if we shift leaves then we shift as much as we can: this is a
1954   deliberate policy of extremism in node packing which results in
1955   higher average utilization after repeated random balance operations
1956   at the cost of more memory copies and more balancing as a result of
1957   small insertions to full nodes.
1958
1959   if we shift internal nodes we try to evenly balance the node
1960   utilization, with consequent less balancing at the cost of lower
1961   utilization.
1962
1963   one could argue that the policy for directories in leaves should be
1964   that of internal nodes, but we will wait until another day to
1965   evaluate this....  It would be nice to someday measure and prove
1966   these assumptions as to what is optimal....
1967
1968*/
1969
1970static inline void do_balance_starts(struct tree_balance *tb)
1971{
1972        /* use print_cur_tb() to see initial state of struct
1973           tree_balance */
1974
1975        /* store_print_tb (tb); */
1976
1977        /* do not delete, just comment it out */
1978/*    print_tb(flag, PATH_LAST_POSITION(tb->tb_path), tb->tb_path->pos_in_item, tb,
1979             "check");*/
1980        RFALSE(check_before_balancing(tb), "PAP-12340: locked buffers in TB");
1981#ifdef CONFIG_REISERFS_CHECK
1982        REISERFS_SB(tb->tb_sb)->cur_tb = tb;
1983#endif
1984}
1985
1986static inline void do_balance_completed(struct tree_balance *tb)
1987{
1988
1989#ifdef CONFIG_REISERFS_CHECK
1990        check_leaf_level(tb);
1991        check_internal_levels(tb);
1992        REISERFS_SB(tb->tb_sb)->cur_tb = NULL;
1993#endif
1994
1995        /* reiserfs_free_block is no longer schedule safe.  So, we need to
1996         ** put the buffers we want freed on the thrown list during do_balance,
1997         ** and then free them now
1998         */
1999
2000        REISERFS_SB(tb->tb_sb)->s_do_balance++;
2001
2002        /* release all nodes hold to perform the balancing */
2003        unfix_nodes(tb);
2004
2005        free_thrown(tb);
2006}
2007
2008void do_balance(struct tree_balance *tb,        /* tree_balance structure */
2009                struct item_head *ih,   /* item header of inserted item */
2010                const char *body,       /* body  of inserted item or bytes to paste */
2011                int flag)
2012{                               /* i - insert, d - delete
2013                                   c - cut, p - paste
2014
2015                                   Cut means delete part of an item
2016                                   (includes removing an entry from a
2017                                   directory).
2018
2019                                   Delete means delete whole item.
2020
2021                                   Insert means add a new item into the
2022                                   tree.
2023
2024                                   Paste means to append to the end of an
2025                                   existing file or to insert a directory
2026                                   entry.  */
2027        int child_pos,          /* position of a child node in its parent */
2028         h;                     /* level of the tree being processed */
2029        struct item_head insert_key[2]; /* in our processing of one level
2030                                           we sometimes determine what
2031                                           must be inserted into the next
2032                                           higher level.  This insertion
2033                                           consists of a key or two keys
2034                                           and their corresponding
2035                                           pointers */
2036        struct buffer_head *insert_ptr[2];      /* inserted node-ptrs for the next
2037                                                   level */
2038
2039        tb->tb_mode = flag;
2040        tb->need_balance_dirty = 0;
2041
2042        if (FILESYSTEM_CHANGED_TB(tb)) {
2043                reiserfs_panic(tb->tb_sb, "clm-6000", "fs generation has "
2044                               "changed");
2045        }
2046        /* if we have no real work to do  */
2047        if (!tb->insert_size[0]) {
2048                reiserfs_warning(tb->tb_sb, "PAP-12350",
2049                                 "insert_size == 0, mode == %c", flag);
2050                unfix_nodes(tb);
2051                return;
2052        }
2053
2054        atomic_inc(&(fs_generation(tb->tb_sb)));
2055        do_balance_starts(tb);
2056
2057        /* balance leaf returns 0 except if combining L R and S into
2058           one node.  see balance_internal() for explanation of this
2059           line of code. */
2060        child_pos = PATH_H_B_ITEM_ORDER(tb->tb_path, 0) +
2061            balance_leaf(tb, ih, body, flag, insert_key, insert_ptr);
2062
2063#ifdef CONFIG_REISERFS_CHECK
2064        check_after_balance_leaf(tb);
2065#endif
2066
2067        /* Balance internal level of the tree. */
2068        for (h = 1; h < MAX_HEIGHT && tb->insert_size[h]; h++)
2069                child_pos =
2070                    balance_internal(tb, h, child_pos, insert_key, insert_ptr);
2071
2072        do_balance_completed(tb);
2073
2074}
2075
lxr.linux.no kindly hosted by Redpill Linpro AS, provider of Linux consulting and operations services since 1995.