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