fs/reiserfs/do_balan.c

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