fs/reiserfs/do_balan.c

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