fs/reiserfs/lbalance.c

   1 /*
   2  * Copyright 2000 by Hans Reiser, licensing governed by reiserfs/README
   3  */
   4
   5 #include <asm/uaccess.h>
   6 #include <linux/string.h>
   7 #include <linux/time.h>
   8 #include <linux/reiserfs_fs.h>
   9 #include <linux/buffer_head.h>
  10
  11 /* these are used in do_balance.c */
  12
  13 /* leaf_move_items
  14    leaf_shift_left
  15    leaf_shift_right
  16    leaf_delete_items
  17    leaf_insert_into_buf
  18    leaf_paste_in_buffer
  19    leaf_cut_from_buffer
  20    leaf_paste_entries
  21    */
  22
  23 /* copy copy_count entries from source directory item to dest buffer (creating new item if needed) */
  24 static void leaf_copy_dir_entries(struct buffer_info *dest_bi,
  25                                   struct buffer_head *source, int last_first,
  26                                   int item_num, int from, int copy_count)
  27 {
  28         struct buffer_head *dest = dest_bi->bi_bh;
  29         int item_num_in_dest;   /* either the number of target item,
  30                                    or if we must create a new item,
  31                                    the number of the item we will
  32                                    create it next to */
  33         struct item_head *ih;
  34         struct reiserfs_de_head *deh;
  35         int copy_records_len;   /* length of all records in item to be copied */
  36         char *records;
  37
  38         ih = B_N_PITEM_HEAD(source, item_num);
  39
  40         RFALSE(!is_direntry_le_ih(ih), "vs-10000: item must be directory item");
  41
  42         /* length of all record to be copied and first byte of the last of them */
  43         deh = B_I_DEH(source, ih);
  44         if (copy_count) {
  45                 copy_records_len = (from ? deh_location(&(deh[from - 1])) :
  46                                     ih_item_len(ih)) -
  47                     deh_location(&(deh[from + copy_count - 1]));
  48                 records =
  49                     source->b_data + ih_location(ih) +
  50                     deh_location(&(deh[from + copy_count - 1]));
  51         } else {
  52                 copy_records_len = 0;
  53                 records = NULL;
  54         }
  55
  56         /* when copy last to first, dest buffer can contain 0 items */
  57         item_num_in_dest =
  58             (last_first ==
  59              LAST_TO_FIRST) ? ((B_NR_ITEMS(dest)) ? 0 : -1) : (B_NR_ITEMS(dest)
  60                                                                - 1);
  61
  62         /* if there are no items in dest or the first/last item in dest is not item of the same directory */
  63         if ((item_num_in_dest == -1) ||
  64             (last_first == FIRST_TO_LAST && le_ih_k_offset(ih) == DOT_OFFSET) ||
  65             (last_first == LAST_TO_FIRST
  66              && comp_short_le_keys /*COMP_SHORT_KEYS */ (&ih->ih_key,
  67                                                          B_N_PKEY(dest,
  68                                                                   item_num_in_dest))))
  69         {
  70                 /* create new item in dest */
  71                 struct item_head new_ih;
  72
  73                 /* form item header */
  74                 memcpy(&new_ih.ih_key, &ih->ih_key, KEY_SIZE);
  75                 put_ih_version(&new_ih, KEY_FORMAT_3_5);
  76                 /* calculate item len */
  77                 put_ih_item_len(&new_ih,
  78                                 DEH_SIZE * copy_count + copy_records_len);
  79                 put_ih_entry_count(&new_ih, 0);
  80
  81                 if (last_first == LAST_TO_FIRST) {
  82                         /* form key by the following way */
  83                         if (from < I_ENTRY_COUNT(ih)) {
  84                                 set_le_ih_k_offset(&new_ih,
  85                                                    deh_offset(&(deh[from])));
  86                                 /*memcpy (&new_ih.ih_key.k_offset, &deh[from].deh_offset, SHORT_KEY_SIZE); */
  87                         } else {
  88                                 /* no entries will be copied to this item in this function */
  89                                 set_le_ih_k_offset(&new_ih, U32_MAX);
  90                                 /* this item is not yet valid, but we want I_IS_DIRECTORY_ITEM to return 1 for it, so we -1 */
  91                         }
  92                         set_le_key_k_type(KEY_FORMAT_3_5, &(new_ih.ih_key),
  93                                           TYPE_DIRENTRY);
  94                 }
  95
  96                 /* insert item into dest buffer */
  97                 leaf_insert_into_buf(dest_bi,
  98                                      (last_first ==
  99                                       LAST_TO_FIRST) ? 0 : B_NR_ITEMS(dest),
 100                                      &new_ih, NULL, 0);
 101         } else {
 102                 /* prepare space for entries */
 103                 leaf_paste_in_buffer(dest_bi,
 104                                      (last_first ==
 105                                       FIRST_TO_LAST) ? (B_NR_ITEMS(dest) -
 106                                                         1) : 0, MAX_US_INT,
 107                                      DEH_SIZE * copy_count + copy_records_len,
 108                                      records, 0);
 109         }
 110
 111         item_num_in_dest =
 112             (last_first == FIRST_TO_LAST) ? (B_NR_ITEMS(dest) - 1) : 0;
 113
 114         leaf_paste_entries(dest_bi, item_num_in_dest,
 115                            (last_first ==
 116                             FIRST_TO_LAST) ? I_ENTRY_COUNT(B_N_PITEM_HEAD(dest,
 117                                                                           item_num_in_dest))
 118                            : 0, copy_count, deh + from, records,
 119                            DEH_SIZE * copy_count + copy_records_len);
 120 }
 121
 122 /* Copy the first (if last_first == FIRST_TO_LAST) or last (last_first == LAST_TO_FIRST) item or
 123    part of it or nothing (see the return 0 below) from SOURCE to the end
 124    (if last_first) or beginning (!last_first) of the DEST */
 125 /* returns 1 if anything was copied, else 0 */
 126 static int leaf_copy_boundary_item(struct buffer_info *dest_bi,
 127                                    struct buffer_head *src, int last_first,
 128                                    int bytes_or_entries)
 129 {
 130         struct buffer_head *dest = dest_bi->bi_bh;
 131         int dest_nr_item, src_nr_item;  /* number of items in the source and destination buffers */
 132         struct item_head *ih;
 133         struct item_head *dih;
 134
 135         dest_nr_item = B_NR_ITEMS(dest);
 136
 137         if (last_first == FIRST_TO_LAST) {
 138                 /* if ( DEST is empty or first item of SOURCE and last item of DEST are the items of different objects
 139                    or of different types ) then there is no need to treat this item differently from the other items
 140                    that we copy, so we return */
 141                 ih = B_N_PITEM_HEAD(src, 0);
 142                 dih = B_N_PITEM_HEAD(dest, dest_nr_item - 1);
 143                 if (!dest_nr_item
 144                     || (!op_is_left_mergeable(&(ih->ih_key), src->b_size)))
 145                         /* there is nothing to merge */
 146                         return 0;
 147
 148                 RFALSE(!ih_item_len(ih),
 149                        "vs-10010: item can not have empty length");
 150
 151                 if (is_direntry_le_ih(ih)) {
 152                         if (bytes_or_entries == -1)
 153                                 /* copy all entries to dest */
 154                                 bytes_or_entries = ih_entry_count(ih);
 155                         leaf_copy_dir_entries(dest_bi, src, FIRST_TO_LAST, 0, 0,
 156                                               bytes_or_entries);
 157                         return 1;
 158                 }
 159
 160                 /* copy part of the body of the first item of SOURCE to the end of the body of the last item of the DEST
 161                    part defined by 'bytes_or_entries'; if bytes_or_entries == -1 copy whole body; don't create new item header
 162                  */
 163                 if (bytes_or_entries == -1)
 164                         bytes_or_entries = ih_item_len(ih);
 165
 166 #ifdef CONFIG_REISERFS_CHECK
 167                 else {
 168                         if (bytes_or_entries == ih_item_len(ih)
 169                             && is_indirect_le_ih(ih))
 170                                 if (get_ih_free_space(ih))
 171                                         reiserfs_panic(sb_from_bi(dest_bi),
 172                                                        "vs-10020",
 173                                                        "last unformatted node "
 174                                                        "must be filled "
 175                                                        "entirely (%h)", ih);
 176                 }
 177 #endif
 178
 179                 /* merge first item (or its part) of src buffer with the last
 180                    item of dest buffer. Both are of the same file */
 181                 leaf_paste_in_buffer(dest_bi,
 182                                      dest_nr_item - 1, ih_item_len(dih),
 183                                      bytes_or_entries, B_I_PITEM(src, ih), 0);
 184
 185                 if (is_indirect_le_ih(dih)) {
 186                         RFALSE(get_ih_free_space(dih),
 187                                "vs-10030: merge to left: last unformatted node of non-last indirect item %h must have zerto free space",
 188                                ih);
 189                         if (bytes_or_entries == ih_item_len(ih))
 190                                 set_ih_free_space(dih, get_ih_free_space(ih));
 191                 }
 192
 193                 return 1;
 194         }
 195
 196         /* copy boundary item to right (last_first == LAST_TO_FIRST) */
 197
 198         /* ( DEST is empty or last item of SOURCE and first item of DEST
 199            are the items of different object or of different types )
 200          */
 201         src_nr_item = B_NR_ITEMS(src);
 202         ih = B_N_PITEM_HEAD(src, src_nr_item - 1);
 203         dih = B_N_PITEM_HEAD(dest, 0);
 204
 205         if (!dest_nr_item || !op_is_left_mergeable(&(dih->ih_key), src->b_size))
 206                 return 0;
 207
 208         if (is_direntry_le_ih(ih)) {
 209                 if (bytes_or_entries == -1)
 210                         /* bytes_or_entries = entries number in last item body of SOURCE */
 211                         bytes_or_entries = ih_entry_count(ih);
 212
 213                 leaf_copy_dir_entries(dest_bi, src, LAST_TO_FIRST,
 214                                       src_nr_item - 1,
 215                                       ih_entry_count(ih) - bytes_or_entries,
 216                                       bytes_or_entries);
 217                 return 1;
 218         }
 219
 220         /* copy part of the body of the last item of SOURCE to the begin of the body of the first item of the DEST;
 221            part defined by 'bytes_or_entries'; if byte_or_entriess == -1 copy whole body; change first item key of the DEST;
 222            don't create new item header
 223          */
 224
 225         RFALSE(is_indirect_le_ih(ih) && get_ih_free_space(ih),
 226                "vs-10040: merge to right: last unformatted node of non-last indirect item must be filled entirely (%h)",
 227                ih);
 228
 229         if (bytes_or_entries == -1) {
 230                 /* bytes_or_entries = length of last item body of SOURCE */
 231                 bytes_or_entries = ih_item_len(ih);
 232
 233                 RFALSE(le_ih_k_offset(dih) !=
 234                        le_ih_k_offset(ih) + op_bytes_number(ih, src->b_size),
 235                        "vs-10050: items %h and %h do not match", ih, dih);
 236
 237                 /* change first item key of the DEST */
 238                 set_le_ih_k_offset(dih, le_ih_k_offset(ih));
 239
 240                 /* item becomes non-mergeable */
 241                 /* or mergeable if left item was */
 242                 set_le_ih_k_type(dih, le_ih_k_type(ih));
 243         } else {
 244                 /* merge to right only part of item */
 245                 RFALSE(ih_item_len(ih) <= bytes_or_entries,
 246                        "vs-10060: no so much bytes %lu (needed %lu)",
 247                        (unsigned long)ih_item_len(ih),
 248                        (unsigned long)bytes_or_entries);
 249
 250                 /* change first item key of the DEST */
 251                 if (is_direct_le_ih(dih)) {
 252                         RFALSE(le_ih_k_offset(dih) <=
 253                                (unsigned long)bytes_or_entries,
 254                                "vs-10070: dih %h, bytes_or_entries(%d)", dih,
 255                                bytes_or_entries);
 256                         set_le_ih_k_offset(dih,
 257                                            le_ih_k_offset(dih) -
 258                                            bytes_or_entries);
 259                 } else {
 260                         RFALSE(le_ih_k_offset(dih) <=
 261                                (bytes_or_entries / UNFM_P_SIZE) * dest->b_size,
 262                                "vs-10080: dih %h, bytes_or_entries(%d)",
 263                                dih,
 264                                (bytes_or_entries / UNFM_P_SIZE) * dest->b_size);
 265                         set_le_ih_k_offset(dih,
 266                                            le_ih_k_offset(dih) -
 267                                            ((bytes_or_entries / UNFM_P_SIZE) *
 268                                             dest->b_size));
 269                 }
 270         }
 271
 272         leaf_paste_in_buffer(dest_bi, 0, 0, bytes_or_entries,
 273                              B_I_PITEM(src,
 274                                        ih) + ih_item_len(ih) - bytes_or_entries,
 275                              0);
 276         return 1;
 277 }
 278
 279 /* copy cpy_mun items from buffer src to buffer dest
 280  * last_first == FIRST_TO_LAST means, that we copy cpy_num  items beginning from first-th item in src to tail of dest
 281  * last_first == LAST_TO_FIRST means, that we copy cpy_num  items beginning from first-th item in src to head of dest
 282  */
 283 static void leaf_copy_items_entirely(struct buffer_info *dest_bi,
 284                                      struct buffer_head *src, int last_first,
 285                                      int first, int cpy_num)
 286 {
 287         struct buffer_head *dest;
 288         int nr, free_space;
 289         int dest_before;
 290         int last_loc, last_inserted_loc, location;
 291         int i, j;
 292         struct block_head *blkh;
 293         struct item_head *ih;
 294
 295         RFALSE(last_first != LAST_TO_FIRST && last_first != FIRST_TO_LAST,
 296                "vs-10090: bad last_first parameter %d", last_first);
 297         RFALSE(B_NR_ITEMS(src) - first < cpy_num,
 298                "vs-10100: too few items in source %d, required %d from %d",
 299                B_NR_ITEMS(src), cpy_num, first);
 300         RFALSE(cpy_num < 0, "vs-10110: can not copy negative amount of items");
 301         RFALSE(!dest_bi, "vs-10120: can not copy negative amount of items");
 302
 303         dest = dest_bi->bi_bh;
 304
 305         RFALSE(!dest, "vs-10130: can not copy negative amount of items");
 306
 307         if (cpy_num == 0)
 308                 return;
 309
 310         blkh = B_BLK_HEAD(dest);
 311         nr = blkh_nr_item(blkh);
 312         free_space = blkh_free_space(blkh);
 313
 314         /* we will insert items before 0-th or nr-th item in dest buffer. It depends of last_first parameter */
 315         dest_before = (last_first == LAST_TO_FIRST) ? 0 : nr;
 316
 317         /* location of head of first new item */
 318         ih = B_N_PITEM_HEAD(dest, dest_before);
 319
 320         RFALSE(blkh_free_space(blkh) < cpy_num * IH_SIZE,
 321                "vs-10140: not enough free space for headers %d (needed %d)",
 322                B_FREE_SPACE(dest), cpy_num * IH_SIZE);
 323
 324         /* prepare space for headers */
 325         memmove(ih + cpy_num, ih, (nr - dest_before) * IH_SIZE);
 326
 327         /* copy item headers */
 328         memcpy(ih, B_N_PITEM_HEAD(src, first), cpy_num * IH_SIZE);
 329
 330         free_space -= (IH_SIZE * cpy_num);
 331         set_blkh_free_space(blkh, free_space);
 332
 333         /* location of unmovable item */
 334         j = location = (dest_before == 0) ? dest->b_size : ih_location(ih - 1);
 335         for (i = dest_before; i < nr + cpy_num; i++) {
 336                 location -= ih_item_len(ih + i - dest_before);
 337                 put_ih_location(ih + i - dest_before, location);
 338         }
 339
 340         /* prepare space for items */
 341         last_loc = ih_location(&(ih[nr + cpy_num - 1 - dest_before]));
 342         last_inserted_loc = ih_location(&(ih[cpy_num - 1]));
 343
 344         /* check free space */
 345         RFALSE(free_space < j - last_inserted_loc,
 346                "vs-10150: not enough free space for items %d (needed %d)",
 347                free_space, j - last_inserted_loc);
 348
 349         memmove(dest->b_data + last_loc,
 350                 dest->b_data + last_loc + j - last_inserted_loc,
 351                 last_inserted_loc - last_loc);
 352
 353         /* copy items */
 354         memcpy(dest->b_data + last_inserted_loc,
 355                B_N_PITEM(src, (first + cpy_num - 1)), j - last_inserted_loc);
 356
 357         /* sizes, item number */
 358         set_blkh_nr_item(blkh, nr + cpy_num);
 359         set_blkh_free_space(blkh, free_space - (j - last_inserted_loc));
 360
 361         do_balance_mark_leaf_dirty(dest_bi->tb, dest, 0);
 362
 363         if (dest_bi->bi_parent) {
 364                 struct disk_child *t_dc;
 365                 t_dc = B_N_CHILD(dest_bi->bi_parent, dest_bi->bi_position);
 366                 RFALSE(dc_block_number(t_dc) != dest->b_blocknr,
 367                        "vs-10160: block number in bh does not match to field in disk_child structure %lu and %lu",
 368                        (long unsigned)dest->b_blocknr,
 369                        (long unsigned)dc_block_number(t_dc));
 370                 put_dc_size(t_dc,
 371                             dc_size(t_dc) + (j - last_inserted_loc +
 372                                              IH_SIZE * cpy_num));
 373
 374                 do_balance_mark_internal_dirty(dest_bi->tb, dest_bi->bi_parent,
 375                                                0);
 376         }
 377 }
 378
 379 /* This function splits the (liquid) item into two items (useful when
 380    shifting part of an item into another node.) */
 381 static void leaf_item_bottle(struct buffer_info *dest_bi,
 382                              struct buffer_head *src, int last_first,
 383                              int item_num, int cpy_bytes)
 384 {
 385         struct buffer_head *dest = dest_bi->bi_bh;
 386         struct item_head *ih;
 387
 388         RFALSE(cpy_bytes == -1,
 389                "vs-10170: bytes == - 1 means: do not split item");
 390
 391         if (last_first == FIRST_TO_LAST) {
 392                 /* if ( if item in position item_num in buffer SOURCE is directory item ) */
 393                 ih = B_N_PITEM_HEAD(src, item_num);
 394                 if (is_direntry_le_ih(ih))
 395                         leaf_copy_dir_entries(dest_bi, src, FIRST_TO_LAST,
 396                                               item_num, 0, cpy_bytes);
 397                 else {
 398                         struct item_head n_ih;
 399
 400                         /* copy part of the body of the item number 'item_num' of SOURCE to the end of the DEST
 401                            part defined by 'cpy_bytes'; create new item header; change old item_header (????);
 402                            n_ih = new item_header;
 403                          */
 404                         memcpy(&n_ih, ih, IH_SIZE);
 405                         put_ih_item_len(&n_ih, cpy_bytes);
 406                         if (is_indirect_le_ih(ih)) {
 407                                 RFALSE(cpy_bytes == ih_item_len(ih)
 408                                        && get_ih_free_space(ih),
 409                                        "vs-10180: when whole indirect item is bottle to left neighbor, it must have free_space==0 (not %lu)",
 410                                        (long unsigned)get_ih_free_space(ih));
 411                                 set_ih_free_space(&n_ih, 0);
 412                         }
 413
 414                         RFALSE(op_is_left_mergeable(&(ih->ih_key), src->b_size),
 415                                "vs-10190: bad mergeability of item %h", ih);
 416                         n_ih.ih_version = ih->ih_version;       /* JDM Endian safe, both le */
 417                         leaf_insert_into_buf(dest_bi, B_NR_ITEMS(dest), &n_ih,
 418                                              B_N_PITEM(src, item_num), 0);
 419                 }
 420         } else {
 421                 /*  if ( if item in position item_num in buffer SOURCE is directory item ) */
 422                 ih = B_N_PITEM_HEAD(src, item_num);
 423                 if (is_direntry_le_ih(ih))
 424                         leaf_copy_dir_entries(dest_bi, src, LAST_TO_FIRST,
 425                                               item_num,
 426                                               I_ENTRY_COUNT(ih) - cpy_bytes,
 427                                               cpy_bytes);
 428                 else {
 429                         struct item_head n_ih;
 430
 431                         /* copy part of the body of the item number 'item_num' of SOURCE to the begin of the DEST
 432                            part defined by 'cpy_bytes'; create new item header;
 433                            n_ih = new item_header;
 434                          */
 435                         memcpy(&n_ih, ih, SHORT_KEY_SIZE);
 436
 437                         n_ih.ih_version = ih->ih_version;       /* JDM Endian safe, both le */
 438
 439                         if (is_direct_le_ih(ih)) {
 440                                 set_le_ih_k_offset(&n_ih,
 441                                                    le_ih_k_offset(ih) +
 442                                                    ih_item_len(ih) - cpy_bytes);
 443                                 set_le_ih_k_type(&n_ih, TYPE_DIRECT);
 444                                 set_ih_free_space(&n_ih, MAX_US_INT);
 445                         } else {
 446                                 /* indirect item */
 447                                 RFALSE(!cpy_bytes && get_ih_free_space(ih),
 448                                        "vs-10200: ih->ih_free_space must be 0 when indirect item will be appended");
 449                                 set_le_ih_k_offset(&n_ih,
 450                                                    le_ih_k_offset(ih) +
 451                                                    (ih_item_len(ih) -
 452                                                     cpy_bytes) / UNFM_P_SIZE *
 453                                                    dest->b_size);
 454                                 set_le_ih_k_type(&n_ih, TYPE_INDIRECT);
 455                                 set_ih_free_space(&n_ih, get_ih_free_space(ih));
 456                         }
 457
 458                         /* set item length */
 459                         put_ih_item_len(&n_ih, cpy_bytes);
 460
 461                         n_ih.ih_version = ih->ih_version;       /* JDM Endian safe, both le */
 462
 463                         leaf_insert_into_buf(dest_bi, 0, &n_ih,
 464                                              B_N_PITEM(src,
 465                                                        item_num) +
 466                                              ih_item_len(ih) - cpy_bytes, 0);
 467                 }
 468         }
 469 }
 470
 471 /* If cpy_bytes equals minus one than copy cpy_num whole items from SOURCE to DEST.
 472    If cpy_bytes not equal to minus one than copy cpy_num-1 whole items from SOURCE to DEST.
 473    From last item copy cpy_num bytes for regular item and cpy_num directory entries for
 474    directory item. */
 475 static int leaf_copy_items(struct buffer_info *dest_bi, struct buffer_head *src,
 476                            int last_first, int cpy_num, int cpy_bytes)
 477 {
 478         struct buffer_head *dest;
 479         int pos, i, src_nr_item, bytes;
 480
 481         dest = dest_bi->bi_bh;
 482         RFALSE(!dest || !src, "vs-10210: !dest || !src");
 483         RFALSE(last_first != FIRST_TO_LAST && last_first != LAST_TO_FIRST,
 484                "vs-10220:last_first != FIRST_TO_LAST && last_first != LAST_TO_FIRST");
 485         RFALSE(B_NR_ITEMS(src) < cpy_num,
 486                "vs-10230: No enough items: %d, req. %d", B_NR_ITEMS(src),
 487                cpy_num);
 488         RFALSE(cpy_num < 0, "vs-10240: cpy_num < 0 (%d)", cpy_num);
 489
 490         if (cpy_num == 0)
 491                 return 0;
 492
 493         if (last_first == FIRST_TO_LAST) {
 494                 /* copy items to left */
 495                 pos = 0;
 496                 if (cpy_num == 1)
 497                         bytes = cpy_bytes;
 498                 else
 499                         bytes = -1;
 500
 501                 /* copy the first item or it part or nothing to the end of the DEST (i = leaf_copy_boundary_item(DEST,SOURCE,0,bytes)) */
 502                 i = leaf_copy_boundary_item(dest_bi, src, FIRST_TO_LAST, bytes);
 503                 cpy_num -= i;
 504                 if (cpy_num == 0)
 505                         return i;
 506                 pos += i;
 507                 if (cpy_bytes == -1)
 508                         /* copy first cpy_num items starting from position 'pos' of SOURCE to end of DEST */
 509                         leaf_copy_items_entirely(dest_bi, src, FIRST_TO_LAST,
 510                                                  pos, cpy_num);
 511                 else {
 512                         /* copy first cpy_num-1 items starting from position 'pos-1' of the SOURCE to the end of the DEST */
 513                         leaf_copy_items_entirely(dest_bi, src, FIRST_TO_LAST,
 514                                                  pos, cpy_num - 1);
 515
 516                         /* copy part of the item which number is cpy_num+pos-1 to the end of the DEST */
 517                         leaf_item_bottle(dest_bi, src, FIRST_TO_LAST,
 518                                          cpy_num + pos - 1, cpy_bytes);
 519                 }
 520         } else {
 521                 /* copy items to right */
 522                 src_nr_item = B_NR_ITEMS(src);
 523                 if (cpy_num == 1)
 524                         bytes = cpy_bytes;
 525                 else
 526                         bytes = -1;
 527
 528                 /* copy the last item or it part or nothing to the begin of the DEST (i = leaf_copy_boundary_item(DEST,SOURCE,1,bytes)); */
 529                 i = leaf_copy_boundary_item(dest_bi, src, LAST_TO_FIRST, bytes);
 530
 531                 cpy_num -= i;
 532                 if (cpy_num == 0)
 533                         return i;
 534
 535                 pos = src_nr_item - cpy_num - i;
 536                 if (cpy_bytes == -1) {
 537                         /* starting from position 'pos' copy last cpy_num items of SOURCE to begin of DEST */
 538                         leaf_copy_items_entirely(dest_bi, src, LAST_TO_FIRST,
 539                                                  pos, cpy_num);
 540                 } else {
 541                         /* copy last cpy_num-1 items starting from position 'pos+1' of the SOURCE to the begin of the DEST; */
 542                         leaf_copy_items_entirely(dest_bi, src, LAST_TO_FIRST,
 543                                                  pos + 1, cpy_num - 1);
 544
 545                         /* copy part of the item which number is pos to the begin of the DEST */
 546                         leaf_item_bottle(dest_bi, src, LAST_TO_FIRST, pos,
 547                                          cpy_bytes);
 548                 }
 549         }
 550         return i;
 551 }
 552
 553 /* there are types of coping: from S[0] to L[0], from S[0] to R[0],
 554    from R[0] to L[0]. for each of these we have to define parent and
 555    positions of destination and source buffers */
 556 static void leaf_define_dest_src_infos(int shift_mode, struct tree_balance *tb,
 557                                        struct buffer_info *dest_bi,
 558                                        struct buffer_info *src_bi,
 559                                        int *first_last,
 560                                        struct buffer_head *Snew)
 561 {
 562         memset(dest_bi, 0, sizeof(struct buffer_info));
 563         memset(src_bi, 0, sizeof(struct buffer_info));
 564
 565         /* define dest, src, dest parent, dest position */
 566         switch (shift_mode) {
 567         case LEAF_FROM_S_TO_L:  /* it is used in leaf_shift_left */
 568                 src_bi->tb = tb;
 569                 src_bi->bi_bh = PATH_PLAST_BUFFER(tb->tb_path);
 570                 src_bi->bi_parent = PATH_H_PPARENT(tb->tb_path, 0);
 571                 src_bi->bi_position = PATH_H_B_ITEM_ORDER(tb->tb_path, 0);      /* src->b_item_order */
 572                 dest_bi->tb = tb;
 573                 dest_bi->bi_bh = tb->L[0];
 574                 dest_bi->bi_parent = tb->FL[0];
 575                 dest_bi->bi_position = get_left_neighbor_position(tb, 0);
 576                 *first_last = FIRST_TO_LAST;
 577                 break;
 578
 579         case LEAF_FROM_S_TO_R:  /* it is used in leaf_shift_right */
 580                 src_bi->tb = tb;
 581                 src_bi->bi_bh = PATH_PLAST_BUFFER(tb->tb_path);
 582                 src_bi->bi_parent = PATH_H_PPARENT(tb->tb_path, 0);
 583                 src_bi->bi_position = PATH_H_B_ITEM_ORDER(tb->tb_path, 0);
 584                 dest_bi->tb = tb;
 585                 dest_bi->bi_bh = tb->R[0];
 586                 dest_bi->bi_parent = tb->FR[0];
 587                 dest_bi->bi_position = get_right_neighbor_position(tb, 0);
 588                 *first_last = LAST_TO_FIRST;
 589                 break;
 590
 591         case LEAF_FROM_R_TO_L:  /* it is used in balance_leaf_when_delete */
 592                 src_bi->tb = tb;
 593                 src_bi->bi_bh = tb->R[0];
 594                 src_bi->bi_parent = tb->FR[0];
 595                 src_bi->bi_position = get_right_neighbor_position(tb, 0);
 596                 dest_bi->tb = tb;
 597                 dest_bi->bi_bh = tb->L[0];
 598                 dest_bi->bi_parent = tb->FL[0];
 599                 dest_bi->bi_position = get_left_neighbor_position(tb, 0);
 600                 *first_last = FIRST_TO_LAST;
 601                 break;
 602
 603         case LEAF_FROM_L_TO_R:  /* it is used in balance_leaf_when_delete */
 604                 src_bi->tb = tb;
 605                 src_bi->bi_bh = tb->L[0];
 606                 src_bi->bi_parent = tb->FL[0];
 607                 src_bi->bi_position = get_left_neighbor_position(tb, 0);
 608                 dest_bi->tb = tb;
 609                 dest_bi->bi_bh = tb->R[0];
 610                 dest_bi->bi_parent = tb->FR[0];
 611                 dest_bi->bi_position = get_right_neighbor_position(tb, 0);
 612                 *first_last = LAST_TO_FIRST;
 613                 break;
 614
 615         case LEAF_FROM_S_TO_SNEW:
 616                 src_bi->tb = tb;
 617                 src_bi->bi_bh = PATH_PLAST_BUFFER(tb->tb_path);
 618                 src_bi->bi_parent = PATH_H_PPARENT(tb->tb_path, 0);
 619                 src_bi->bi_position = PATH_H_B_ITEM_ORDER(tb->tb_path, 0);
 620                 dest_bi->tb = tb;
 621                 dest_bi->bi_bh = Snew;
 622                 dest_bi->bi_parent = NULL;
 623                 dest_bi->bi_position = 0;
 624                 *first_last = LAST_TO_FIRST;
 625                 break;
 626
 627         default:
 628                 reiserfs_panic(sb_from_bi(src_bi), "vs-10250",
 629                                "shift type is unknown (%d)", shift_mode);
 630         }
 631         RFALSE(!src_bi->bi_bh || !dest_bi->bi_bh,
 632                "vs-10260: mode==%d, source (%p) or dest (%p) buffer is initialized incorrectly",
 633                shift_mode, src_bi->bi_bh, dest_bi->bi_bh);
 634 }
 635
 636 /* copy mov_num items and mov_bytes of the (mov_num-1)th item to
 637    neighbor. Delete them from source */
 638 int leaf_move_items(int shift_mode, struct tree_balance *tb, int mov_num,
 639                     int mov_bytes, struct buffer_head *Snew)
 640 {
 641         int ret_value;
 642         struct buffer_info dest_bi, src_bi;
 643         int first_last;
 644
 645         leaf_define_dest_src_infos(shift_mode, tb, &dest_bi, &src_bi,
 646                                    &first_last, Snew);
 647
 648         ret_value =
 649             leaf_copy_items(&dest_bi, src_bi.bi_bh, first_last, mov_num,
 650                             mov_bytes);
 651
 652         leaf_delete_items(&src_bi, first_last,
 653                           (first_last ==
 654                            FIRST_TO_LAST) ? 0 : (B_NR_ITEMS(src_bi.bi_bh) -
 655                                                  mov_num), mov_num, mov_bytes);
 656
 657         return ret_value;
 658 }
 659
 660 /* Shift shift_num items (and shift_bytes of last shifted item if shift_bytes != -1)
 661    from S[0] to L[0] and replace the delimiting key */
 662 int leaf_shift_left(struct tree_balance *tb, int shift_num, int shift_bytes)
 663 {
 664         struct buffer_head *S0 = PATH_PLAST_BUFFER(tb->tb_path);
 665         int i;
 666
 667         /* move shift_num (and shift_bytes bytes) items from S[0] to left neighbor L[0] */
 668         i = leaf_move_items(LEAF_FROM_S_TO_L, tb, shift_num, shift_bytes, NULL);
 669
 670         if (shift_num) {
 671                 if (B_NR_ITEMS(S0) == 0) {      /* number of items in S[0] == 0 */
 672
 673                         RFALSE(shift_bytes != -1,
 674                                "vs-10270: S0 is empty now, but shift_bytes != -1 (%d)",
 675                                shift_bytes);
 676 #ifdef CONFIG_REISERFS_CHECK
 677                         if (tb->tb_mode == M_PASTE || tb->tb_mode == M_INSERT) {
 678                                 print_cur_tb("vs-10275");
 679                                 reiserfs_panic(tb->tb_sb, "vs-10275",
 680                                                "balance condition corrupted "
 681                                                "(%c)", tb->tb_mode);
 682                         }
 683 #endif
 684
 685                         if (PATH_H_POSITION(tb->tb_path, 1) == 0)
 686                                 replace_key(tb, tb->CFL[0], tb->lkey[0],
 687                                             PATH_H_PPARENT(tb->tb_path, 0), 0);
 688
 689                 } else {
 690                         /* replace lkey in CFL[0] by 0-th key from S[0]; */
 691                         replace_key(tb, tb->CFL[0], tb->lkey[0], S0, 0);
 692
 693                         RFALSE((shift_bytes != -1 &&
 694                                 !(is_direntry_le_ih(B_N_PITEM_HEAD(S0, 0))
 695                                   && !I_ENTRY_COUNT(B_N_PITEM_HEAD(S0, 0)))) &&
 696                                (!op_is_left_mergeable
 697                                 (B_N_PKEY(S0, 0), S0->b_size)),
 698                                "vs-10280: item must be mergeable");
 699                 }
 700         }
 701
 702         return i;
 703 }
 704
 705 /* CLEANING STOPPED HERE */
 706
 707 /* Shift shift_num (shift_bytes) items from S[0] to the right neighbor, and replace the delimiting key */
 708 int leaf_shift_right(struct tree_balance *tb, int shift_num, int shift_bytes)
 709 {
 710         //  struct buffer_head * S0 = PATH_PLAST_BUFFER (tb->tb_path);
 711         int ret_value;
 712
 713         /* move shift_num (and shift_bytes) items from S[0] to right neighbor R[0] */
 714         ret_value =
 715             leaf_move_items(LEAF_FROM_S_TO_R, tb, shift_num, shift_bytes, NULL);
 716
 717         /* replace rkey in CFR[0] by the 0-th key from R[0] */
 718         if (shift_num) {
 719                 replace_key(tb, tb->CFR[0], tb->rkey[0], tb->R[0], 0);
 720
 721         }
 722
 723         return ret_value;
 724 }
 725
 726 static void leaf_delete_items_entirely(struct buffer_info *bi,
 727                                        int first, int del_num);
 728 /*  If del_bytes == -1, starting from position 'first' delete del_num items in whole in buffer CUR.
 729     If not.
 730     If last_first == 0. Starting from position 'first' delete del_num-1 items in whole. Delete part of body of
 731     the first item. Part defined by del_bytes. Don't delete first item header
 732     If last_first == 1. Starting from position 'first+1' delete del_num-1 items in whole. Delete part of body of
 733     the last item . Part defined by del_bytes. Don't delete last item header.
 734 */
 735 void leaf_delete_items(struct buffer_info *cur_bi, int last_first,
 736                        int first, int del_num, int del_bytes)
 737 {
 738         struct buffer_head *bh;
 739         int item_amount = B_NR_ITEMS(bh = cur_bi->bi_bh);
 740
 741         RFALSE(!bh, "10155: bh is not defined");
 742         RFALSE(del_num < 0, "10160: del_num can not be < 0. del_num==%d",
 743                del_num);
 744         RFALSE(first < 0
 745                || first + del_num > item_amount,
 746                "10165: invalid number of first item to be deleted (%d) or "
 747                "no so much items (%d) to delete (only %d)", first,
 748                first + del_num, item_amount);
 749
 750         if (del_num == 0)
 751                 return;
 752
 753         if (first == 0 && del_num == item_amount && del_bytes == -1) {
 754                 make_empty_node(cur_bi);
 755                 do_balance_mark_leaf_dirty(cur_bi->tb, bh, 0);
 756                 return;
 757         }
 758
 759         if (del_bytes == -1)
 760                 /* delete del_num items beginning from item in position first */
 761                 leaf_delete_items_entirely(cur_bi, first, del_num);
 762         else {
 763                 if (last_first == FIRST_TO_LAST) {
 764                         /* delete del_num-1 items beginning from item in position first  */
 765                         leaf_delete_items_entirely(cur_bi, first, del_num - 1);
 766
 767                         /* delete the part of the first item of the bh
 768                            do not delete item header
 769                          */
 770                         leaf_cut_from_buffer(cur_bi, 0, 0, del_bytes);
 771                 } else {
 772                         struct item_head *ih;
 773                         int len;
 774
 775                         /* delete del_num-1 items beginning from item in position first+1  */
 776                         leaf_delete_items_entirely(cur_bi, first + 1,
 777                                                    del_num - 1);
 778
 779                         ih = B_N_PITEM_HEAD(bh, B_NR_ITEMS(bh) - 1);
 780                         if (is_direntry_le_ih(ih))
 781                                 /* the last item is directory  */
 782                                 /* len = numbers of directory entries in this item */
 783                                 len = ih_entry_count(ih);
 784                         else
 785                                 /* len = body len of item */
 786                                 len = ih_item_len(ih);
 787
 788                         /* delete the part of the last item of the bh
 789                            do not delete item header
 790                          */
 791                         leaf_cut_from_buffer(cur_bi, B_NR_ITEMS(bh) - 1,
 792                                              len - del_bytes, del_bytes);
 793                 }
 794         }
 795 }
 796
 797 /* insert item into the leaf node in position before */
 798 void leaf_insert_into_buf(struct buffer_info *bi, int before,
 799                           struct item_head *inserted_item_ih,
 800                           const char *inserted_item_body, int zeros_number)
 801 {
 802         struct buffer_head *bh = bi->bi_bh;
 803         int nr, free_space;
 804         struct block_head *blkh;
 805         struct item_head *ih;
 806         int i;
 807         int last_loc, unmoved_loc;
 808         char *to;
 809
 810         blkh = B_BLK_HEAD(bh);
 811         nr = blkh_nr_item(blkh);
 812         free_space = blkh_free_space(blkh);
 813
 814         /* check free space */
 815         RFALSE(free_space < ih_item_len(inserted_item_ih) + IH_SIZE,
 816                "vs-10170: not enough free space in block %z, new item %h",
 817                bh, inserted_item_ih);
 818         RFALSE(zeros_number > ih_item_len(inserted_item_ih),
 819                "vs-10172: zero number == %d, item length == %d",
 820                zeros_number, ih_item_len(inserted_item_ih));
 821
 822         /* get item new item must be inserted before */
 823         ih = B_N_PITEM_HEAD(bh, before);
 824
 825         /* prepare space for the body of new item */
 826         last_loc = nr ? ih_location(&(ih[nr - before - 1])) : bh->b_size;
 827         unmoved_loc = before ? ih_location(ih - 1) : bh->b_size;
 828
 829         memmove(bh->b_data + last_loc - ih_item_len(inserted_item_ih),
 830                 bh->b_data + last_loc, unmoved_loc - last_loc);
 831
 832         to = bh->b_data + unmoved_loc - ih_item_len(inserted_item_ih);
 833         memset(to, 0, zeros_number);
 834         to += zeros_number;
 835
 836         /* copy body to prepared space */
 837         if (inserted_item_body)
 838                 memmove(to, inserted_item_body,
 839                         ih_item_len(inserted_item_ih) - zeros_number);
 840         else
 841                 memset(to, '\0', ih_item_len(inserted_item_ih) - zeros_number);
 842
 843         /* insert item header */
 844         memmove(ih + 1, ih, IH_SIZE * (nr - before));
 845         memmove(ih, inserted_item_ih, IH_SIZE);
 846
 847         /* change locations */
 848         for (i = before; i < nr + 1; i++) {
 849                 unmoved_loc -= ih_item_len(&(ih[i - before]));
 850                 put_ih_location(&(ih[i - before]), unmoved_loc);
 851         }
 852
 853         /* sizes, free space, item number */
 854         set_blkh_nr_item(blkh, blkh_nr_item(blkh) + 1);
 855         set_blkh_free_space(blkh,
 856                             free_space - (IH_SIZE +
 857                                           ih_item_len(inserted_item_ih)));
 858         do_balance_mark_leaf_dirty(bi->tb, bh, 1);
 859
 860         if (bi->bi_parent) {
 861                 struct disk_child *t_dc;
 862                 t_dc = B_N_CHILD(bi->bi_parent, bi->bi_position);
 863                 put_dc_size(t_dc,
 864                             dc_size(t_dc) + (IH_SIZE +
 865                                              ih_item_len(inserted_item_ih)));
 866                 do_balance_mark_internal_dirty(bi->tb, bi->bi_parent, 0);
 867         }
 868 }
 869
 870 /* paste paste_size bytes to affected_item_num-th item.
 871    When item is a directory, this only prepare space for new entries */
 872 void leaf_paste_in_buffer(struct buffer_info *bi, int affected_item_num,
 873                           int pos_in_item, int paste_size,
 874                           const char *body, int zeros_number)
 875 {
 876         struct buffer_head *bh = bi->bi_bh;
 877         int nr, free_space;
 878         struct block_head *blkh;
 879         struct item_head *ih;
 880         int i;
 881         int last_loc, unmoved_loc;
 882
 883         blkh = B_BLK_HEAD(bh);
 884         nr = blkh_nr_item(blkh);
 885         free_space = blkh_free_space(blkh);
 886
 887         /* check free space */
 888         RFALSE(free_space < paste_size,
 889                "vs-10175: not enough free space: needed %d, available %d",
 890                paste_size, free_space);
 891
 892 #ifdef CONFIG_REISERFS_CHECK
 893         if (zeros_number > paste_size) {
 894                 struct super_block *sb = NULL;
 895                 if (bi && bi->tb)
 896                         sb = bi->tb->tb_sb;
 897                 print_cur_tb("10177");
 898                 reiserfs_panic(sb, "vs-10177",
 899                                "zeros_number == %d, paste_size == %d",
 900                                zeros_number, paste_size);
 901         }
 902 #endif                          /* CONFIG_REISERFS_CHECK */
 903
 904         /* item to be appended */
 905         ih = B_N_PITEM_HEAD(bh, affected_item_num);
 906
 907         last_loc = ih_location(&(ih[nr - affected_item_num - 1]));
 908         unmoved_loc = affected_item_num ? ih_location(ih - 1) : bh->b_size;
 909
 910         /* prepare space */
 911         memmove(bh->b_data + last_loc - paste_size, bh->b_data + last_loc,
 912                 unmoved_loc - last_loc);
 913
 914         /* change locations */
 915         for (i = affected_item_num; i < nr; i++)
 916                 put_ih_location(&(ih[i - affected_item_num]),
 917                                 ih_location(&(ih[i - affected_item_num])) -
 918                                 paste_size);
 919
 920         if (body) {
 921                 if (!is_direntry_le_ih(ih)) {
 922                         if (!pos_in_item) {
 923                                 /* shift data to right */
 924                                 memmove(bh->b_data + ih_location(ih) +
 925                                         paste_size,
 926                                         bh->b_data + ih_location(ih),
 927                                         ih_item_len(ih));
 928                                 /* paste data in the head of item */
 929                                 memset(bh->b_data + ih_location(ih), 0,
 930                                        zeros_number);
 931                                 memcpy(bh->b_data + ih_location(ih) +
 932                                        zeros_number, body,
 933                                        paste_size - zeros_number);
 934                         } else {
 935                                 memset(bh->b_data + unmoved_loc - paste_size, 0,
 936                                        zeros_number);
 937                                 memcpy(bh->b_data + unmoved_loc - paste_size +
 938                                        zeros_number, body,
 939                                        paste_size - zeros_number);
 940                         }
 941                 }
 942         } else
 943                 memset(bh->b_data + unmoved_loc - paste_size, '\0', paste_size);
 944
 945         put_ih_item_len(ih, ih_item_len(ih) + paste_size);
 946
 947         /* change free space */
 948         set_blkh_free_space(blkh, free_space - paste_size);
 949
 950         do_balance_mark_leaf_dirty(bi->tb, bh, 0);
 951
 952         if (bi->bi_parent) {
 953                 struct disk_child *t_dc =
 954                     B_N_CHILD(bi->bi_parent, bi->bi_position);
 955                 put_dc_size(t_dc, dc_size(t_dc) + paste_size);
 956                 do_balance_mark_internal_dirty(bi->tb, bi->bi_parent, 0);
 957         }
 958 }
 959
 960 /* cuts DEL_COUNT entries beginning from FROM-th entry. Directory item
 961    does not have free space, so it moves DEHs and remaining records as
 962    necessary. Return value is size of removed part of directory item
 963    in bytes. */
 964 static int leaf_cut_entries(struct buffer_head *bh,
 965                             struct item_head *ih, int from, int del_count)
 966 {
 967         char *item;
 968         struct reiserfs_de_head *deh;
 969         int prev_record_offset; /* offset of record, that is (from-1)th */
 970         char *prev_record;      /* */
 971         int cut_records_len;    /* length of all removed records */
 972         int i;
 973
 974         /* make sure, that item is directory and there are enough entries to
 975            remove */
 976         RFALSE(!is_direntry_le_ih(ih), "10180: item is not directory item");
 977         RFALSE(I_ENTRY_COUNT(ih) < from + del_count,
 978                "10185: item contains not enough entries: entry_cout = %d, from = %d, to delete = %d",
 979                I_ENTRY_COUNT(ih), from, del_count);
 980
 981         if (del_count == 0)
 982                 return 0;
 983
 984         /* first byte of item */
 985         item = bh->b_data + ih_location(ih);
 986
 987         /* entry head array */
 988         deh = B_I_DEH(bh, ih);
 989
 990         /* first byte of remaining entries, those are BEFORE cut entries
 991            (prev_record) and length of all removed records (cut_records_len) */
 992         prev_record_offset =
 993             (from ? deh_location(&(deh[from - 1])) : ih_item_len(ih));
 994         cut_records_len = prev_record_offset /*from_record */  -
 995             deh_location(&(deh[from + del_count - 1]));
 996         prev_record = item + prev_record_offset;
 997
 998         /* adjust locations of remaining entries */
 999         for (i = I_ENTRY_COUNT(ih) - 1; i > from + del_count - 1; i--)
1000                 put_deh_location(&(deh[i]),
1001                                  deh_location(&deh[i]) -
1002                                  (DEH_SIZE * del_count));
1003
1004         for (i = 0; i < from; i++)
1005                 put_deh_location(&(deh[i]),
1006                                  deh_location(&deh[i]) - (DEH_SIZE * del_count +
1007                                                           cut_records_len));
1008
1009         put_ih_entry_count(ih, ih_entry_count(ih) - del_count);
1010
1011         /* shift entry head array and entries those are AFTER removed entries */
1012         memmove((char *)(deh + from),
1013                 deh + from + del_count,
1014                 prev_record - cut_records_len - (char *)(deh + from +
1015                                                          del_count));
1016
1017         /* shift records, those are BEFORE removed entries */
1018         memmove(prev_record - cut_records_len - DEH_SIZE * del_count,
1019                 prev_record, item + ih_item_len(ih) - prev_record);
1020
1021         return DEH_SIZE * del_count + cut_records_len;
1022 }
1023
1024 /*  when cut item is part of regular file
1025         pos_in_item - first byte that must be cut
1026         cut_size - number of bytes to be cut beginning from pos_in_item
1027
1028    when cut item is part of directory
1029         pos_in_item - number of first deleted entry
1030         cut_size - count of deleted entries
1031     */
1032 void leaf_cut_from_buffer(struct buffer_info *bi, int cut_item_num,
1033                           int pos_in_item, int cut_size)
1034 {
1035         int nr;
1036         struct buffer_head *bh = bi->bi_bh;
1037         struct block_head *blkh;
1038         struct item_head *ih;
1039         int last_loc, unmoved_loc;
1040         int i;
1041
1042         blkh = B_BLK_HEAD(bh);
1043         nr = blkh_nr_item(blkh);
1044
1045         /* item head of truncated item */
1046         ih = B_N_PITEM_HEAD(bh, cut_item_num);
1047
1048         if (is_direntry_le_ih(ih)) {
1049                 /* first cut entry () */
1050                 cut_size = leaf_cut_entries(bh, ih, pos_in_item, cut_size);
1051                 if (pos_in_item == 0) {
1052                         /* change key */
1053                         RFALSE(cut_item_num,
1054                                "when 0-th enrty of item is cut, that item must be first in the node, not %d-th",
1055                                cut_item_num);
1056                         /* change item key by key of first entry in the item */
1057                         set_le_ih_k_offset(ih, deh_offset(B_I_DEH(bh, ih)));
1058                         /*memcpy (&ih->ih_key.k_offset, &(B_I_DEH (bh, ih)->deh_offset), SHORT_KEY_SIZE); */
1059                 }
1060         } else {
1061                 /* item is direct or indirect */
1062                 RFALSE(is_statdata_le_ih(ih), "10195: item is stat data");
1063                 RFALSE(pos_in_item && pos_in_item + cut_size != ih_item_len(ih),
1064                        "10200: invalid offset (%lu) or trunc_size (%lu) or ih_item_len (%lu)",
1065                        (long unsigned)pos_in_item, (long unsigned)cut_size,
1066                        (long unsigned)ih_item_len(ih));
1067
1068                 /* shift item body to left if cut is from the head of item */
1069                 if (pos_in_item == 0) {
1070                         memmove(bh->b_data + ih_location(ih),
1071                                 bh->b_data + ih_location(ih) + cut_size,
1072                                 ih_item_len(ih) - cut_size);
1073
1074                         /* change key of item */
1075                         if (is_direct_le_ih(ih))
1076                                 set_le_ih_k_offset(ih,
1077                                                    le_ih_k_offset(ih) +
1078                                                    cut_size);
1079                         else {
1080                                 set_le_ih_k_offset(ih,
1081                                                    le_ih_k_offset(ih) +
1082                                                    (cut_size / UNFM_P_SIZE) *
1083                                                    bh->b_size);
1084                                 RFALSE(ih_item_len(ih) == cut_size
1085                                        && get_ih_free_space(ih),
1086                                        "10205: invalid ih_free_space (%h)", ih);
1087                         }
1088                 }
1089         }
1090
1091         /* location of the last item */
1092         last_loc = ih_location(&(ih[nr - cut_item_num - 1]));
1093
1094         /* location of the item, which is remaining at the same place */
1095         unmoved_loc = cut_item_num ? ih_location(ih - 1) : bh->b_size;
1096
1097         /* shift */
1098         memmove(bh->b_data + last_loc + cut_size, bh->b_data + last_loc,
1099                 unmoved_loc - last_loc - cut_size);
1100
1101         /* change item length */
1102         put_ih_item_len(ih, ih_item_len(ih) - cut_size);
1103
1104         if (is_indirect_le_ih(ih)) {
1105                 if (pos_in_item)
1106                         set_ih_free_space(ih, 0);
1107         }
1108
1109         /* change locations */
1110         for (i = cut_item_num; i < nr; i++)
1111                 put_ih_location(&(ih[i - cut_item_num]),
1112                                 ih_location(&ih[i - cut_item_num]) + cut_size);
1113
1114         /* size, free space */
1115         set_blkh_free_space(blkh, blkh_free_space(blkh) + cut_size);
1116
1117         do_balance_mark_leaf_dirty(bi->tb, bh, 0);
1118
1119         if (bi->bi_parent) {
1120                 struct disk_child *t_dc;
1121                 t_dc = B_N_CHILD(bi->bi_parent, bi->bi_position);
1122                 put_dc_size(t_dc, dc_size(t_dc) - cut_size);
1123                 do_balance_mark_internal_dirty(bi->tb, bi->bi_parent, 0);
1124         }
1125 }
1126
1127 /* delete del_num items from buffer starting from the first'th item */
1128 static void leaf_delete_items_entirely(struct buffer_info *bi,
1129                                        int first, int del_num)
1130 {
1131         struct buffer_head *bh = bi->bi_bh;
1132         int nr;
1133         int i, j;
1134         int last_loc, last_removed_loc;
1135         struct block_head *blkh;
1136         struct item_head *ih;
1137
1138         RFALSE(bh == NULL, "10210: buffer is 0");
1139         RFALSE(del_num < 0, "10215: del_num less than 0 (%d)", del_num);
1140
1141         if (del_num == 0)
1142                 return;
1143
1144         blkh = B_BLK_HEAD(bh);
1145         nr = blkh_nr_item(blkh);
1146
1147         RFALSE(first < 0 || first + del_num > nr,
1148                "10220: first=%d, number=%d, there is %d items", first, del_num,
1149                nr);
1150
1151         if (first == 0 && del_num == nr) {
1152                 /* this does not work */
1153                 make_empty_node(bi);
1154
1155                 do_balance_mark_leaf_dirty(bi->tb, bh, 0);
1156                 return;
1157         }
1158
1159         ih = B_N_PITEM_HEAD(bh, first);
1160
1161         /* location of unmovable item */
1162         j = (first == 0) ? bh->b_size : ih_location(ih - 1);
1163
1164         /* delete items */
1165         last_loc = ih_location(&(ih[nr - 1 - first]));
1166         last_removed_loc = ih_location(&(ih[del_num - 1]));
1167
1168         memmove(bh->b_data + last_loc + j - last_removed_loc,
1169                 bh->b_data + last_loc, last_removed_loc - last_loc);
1170
1171         /* delete item headers */
1172         memmove(ih, ih + del_num, (nr - first - del_num) * IH_SIZE);
1173
1174         /* change item location */
1175         for (i = first; i < nr - del_num; i++)
1176                 put_ih_location(&(ih[i - first]),
1177                                 ih_location(&(ih[i - first])) + (j -
1178                                                                  last_removed_loc));
1179
1180         /* sizes, item number */
1181         set_blkh_nr_item(blkh, blkh_nr_item(blkh) - del_num);
1182         set_blkh_free_space(blkh,
1183                             blkh_free_space(blkh) + (j - last_removed_loc +
1184                                                      IH_SIZE * del_num));
1185
1186         do_balance_mark_leaf_dirty(bi->tb, bh, 0);
1187
1188         if (bi->bi_parent) {
1189                 struct disk_child *t_dc =
1190                     B_N_CHILD(bi->bi_parent, bi->bi_position);
1191                 put_dc_size(t_dc,
1192                             dc_size(t_dc) - (j - last_removed_loc +
1193                                              IH_SIZE * del_num));
1194                 do_balance_mark_internal_dirty(bi->tb, bi->bi_parent, 0);
1195         }
1196 }
1197
1198 /* paste new_entry_count entries (new_dehs, records) into position before to item_num-th item */
1199 void leaf_paste_entries(struct buffer_info *bi,
1200                         int item_num,
1201                         int before,
1202                         int new_entry_count,
1203                         struct reiserfs_de_head *new_dehs,
1204                         const char *records, int paste_size)
1205 {
1206         struct item_head *ih;
1207         char *item;
1208         struct reiserfs_de_head *deh;
1209         char *insert_point;
1210         int i, old_entry_num;
1211         struct buffer_head *bh = bi->bi_bh;
1212
1213         if (new_entry_count == 0)
1214                 return;
1215
1216         ih = B_N_PITEM_HEAD(bh, item_num);
1217
1218         /* make sure, that item is directory, and there are enough records in it */
1219         RFALSE(!is_direntry_le_ih(ih), "10225: item is not directory item");
1220         RFALSE(I_ENTRY_COUNT(ih) < before,
1221                "10230: there are no entry we paste entries before. entry_count = %d, before = %d",
1222                I_ENTRY_COUNT(ih), before);
1223
1224         /* first byte of dest item */
1225         item = bh->b_data + ih_location(ih);
1226
1227         /* entry head array */
1228         deh = B_I_DEH(bh, ih);
1229
1230         /* new records will be pasted at this point */
1231         insert_point =
1232             item +
1233             (before ? deh_location(&(deh[before - 1]))
1234              : (ih_item_len(ih) - paste_size));
1235
1236         /* adjust locations of records that will be AFTER new records */
1237         for (i = I_ENTRY_COUNT(ih) - 1; i >= before; i--)
1238                 put_deh_location(&(deh[i]),
1239                                  deh_location(&(deh[i])) +
1240                                  (DEH_SIZE * new_entry_count));
1241
1242         /* adjust locations of records that will be BEFORE new records */
1243         for (i = 0; i < before; i++)
1244                 put_deh_location(&(deh[i]),
1245                                  deh_location(&(deh[i])) + paste_size);
1246
1247         old_entry_num = I_ENTRY_COUNT(ih);
1248         put_ih_entry_count(ih, ih_entry_count(ih) + new_entry_count);
1249
1250         /* prepare space for pasted records */
1251         memmove(insert_point + paste_size, insert_point,
1252                 item + (ih_item_len(ih) - paste_size) - insert_point);
1253
1254         /* copy new records */
1255         memcpy(insert_point + DEH_SIZE * new_entry_count, records,
1256                paste_size - DEH_SIZE * new_entry_count);
1257
1258         /* prepare space for new entry heads */
1259         deh += before;
1260         memmove((char *)(deh + new_entry_count), deh,
1261                 insert_point - (char *)deh);
1262
1263         /* copy new entry heads */
1264         deh = (struct reiserfs_de_head *)((char *)deh);
1265         memcpy(deh, new_dehs, DEH_SIZE * new_entry_count);
1266
1267         /* set locations of new records */
1268         for (i = 0; i < new_entry_count; i++) {
1269                 put_deh_location(&(deh[i]),
1270                                  deh_location(&(deh[i])) +
1271                                  (-deh_location
1272                                   (&(new_dehs[new_entry_count - 1])) +
1273                                   insert_point + DEH_SIZE * new_entry_count -
1274                                   item));
1275         }
1276
1277         /* change item key if necessary (when we paste before 0-th entry */
1278         if (!before) {
1279                 set_le_ih_k_offset(ih, deh_offset(new_dehs));
1280 /*      memcpy (&ih->ih_key.k_offset,
1281                        &new_dehs->deh_offset, SHORT_KEY_SIZE);*/
1282         }
1283 #ifdef CONFIG_REISERFS_CHECK
1284         {
1285                 int prev, next;
1286                 /* check record locations */
1287                 deh = B_I_DEH(bh, ih);
1288                 for (i = 0; i < I_ENTRY_COUNT(ih); i++) {
1289                         next =
1290                             (i <
1291                              I_ENTRY_COUNT(ih) -
1292                              1) ? deh_location(&(deh[i + 1])) : 0;
1293                         prev = (i != 0) ? deh_location(&(deh[i - 1])) : 0;
1294
1295                         if (prev && prev <= deh_location(&(deh[i])))
1296                                 reiserfs_error(sb_from_bi(bi), "vs-10240",
1297                                                "directory item (%h) "
1298                                                "corrupted (prev %a, "
1299                                                "cur(%d) %a)",
1300                                                ih, deh + i - 1, i, deh + i);
1301                         if (next && next >= deh_location(&(deh[i])))
1302                                 reiserfs_error(sb_from_bi(bi), "vs-10250",
1303                                                "directory item (%h) "
1304                                                "corrupted (cur(%d) %a, "
1305                                                "next %a)",
1306                                                ih, i, deh + i, deh + i + 1);
1307                 }
1308         }
1309 #endif
1310
1311 }