git.oblomov.eu Git - linux-2.6/blob - 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                 if (is_direntry_le_ih(ih = B_N_PITEM_HEAD(src, item_num)))
 394                         leaf_copy_dir_entries(dest_bi, src, FIRST_TO_LAST,
 395                                               item_num, 0, cpy_bytes);
 396                 else {
 397                         struct item_head n_ih;
 398
 399                         /* copy part of the body of the item number 'item_num' of SOURCE to the end of the DEST
 400                            part defined by 'cpy_bytes'; create new item header; change old item_header (????);
 401                            n_ih = new item_header;
 402                          */
 403                         memcpy(&n_ih, ih, IH_SIZE);
 404                         put_ih_item_len(&n_ih, cpy_bytes);
 405                         if (is_indirect_le_ih(ih)) {
 406                                 RFALSE(cpy_bytes == ih_item_len(ih)
 407                                        && get_ih_free_space(ih),
 408                                        "vs-10180: when whole indirect item is bottle to left neighbor, it must have free_space==0 (not %lu)",
 409                                        (long unsigned)get_ih_free_space(ih));
 410                                 set_ih_free_space(&n_ih, 0);
 411                         }
 412
 413                         RFALSE(op_is_left_mergeable(&(ih->ih_key), src->b_size),
 414                                "vs-10190: bad mergeability of item %h", ih);
 415                         n_ih.ih_version = ih->ih_version;       /* JDM Endian safe, both le */
 416                         leaf_insert_into_buf(dest_bi, B_NR_ITEMS(dest), &n_ih,
 417                                              B_N_PITEM(src, item_num), 0);
 418                 }
 419         } else {
 420                 /*  if ( if item in position item_num in buffer SOURCE is directory item ) */
 421                 if (is_direntry_le_ih(ih = B_N_PITEM_HEAD(src, item_num)))
 422                         leaf_copy_dir_entries(dest_bi, src, LAST_TO_FIRST,
 423                                               item_num,
 424                                               I_ENTRY_COUNT(ih) - cpy_bytes,
 425                                               cpy_bytes);
 426                 else {
 427                         struct item_head n_ih;
 428
 429                         /* copy part of the body of the item number 'item_num' of SOURCE to the begin of the DEST
 430                            part defined by 'cpy_bytes'; create new item header;
 431                            n_ih = new item_header;
 432                          */
 433                         memcpy(&n_ih, ih, SHORT_KEY_SIZE);
 434
 435                         n_ih.ih_version = ih->ih_version;       /* JDM Endian safe, both le */
 436
 437                         if (is_direct_le_ih(ih)) {
 438                                 set_le_ih_k_offset(&n_ih,
 439                                                    le_ih_k_offset(ih) +
 440                                                    ih_item_len(ih) - cpy_bytes);
 441                                 set_le_ih_k_type(&n_ih, TYPE_DIRECT);
 442                                 set_ih_free_space(&n_ih, MAX_US_INT);
 443                         } else {
 444                                 /* indirect item */
 445                                 RFALSE(!cpy_bytes && get_ih_free_space(ih),
 446                                        "vs-10200: ih->ih_free_space must be 0 when indirect item will be appended");
 447                                 set_le_ih_k_offset(&n_ih,
 448                                                    le_ih_k_offset(ih) +
 449                                                    (ih_item_len(ih) -
 450                                                     cpy_bytes) / UNFM_P_SIZE *
 451                                                    dest->b_size);
 452                                 set_le_ih_k_type(&n_ih, TYPE_INDIRECT);
 453                                 set_ih_free_space(&n_ih, get_ih_free_space(ih));
 454                         }
 455
 456                         /* set item length */
 457                         put_ih_item_len(&n_ih, cpy_bytes);
 458
 459                         n_ih.ih_version = ih->ih_version;       /* JDM Endian safe, both le */
 460
 461                         leaf_insert_into_buf(dest_bi, 0, &n_ih,
 462                                              B_N_PITEM(src,
 463                                                        item_num) +
 464                                              ih_item_len(ih) - cpy_bytes, 0);
 465                 }
 466         }
 467 }
 468
 469 /* If cpy_bytes equals minus one than copy cpy_num whole items from SOURCE to DEST.
 470    If cpy_bytes not equal to minus one than copy cpy_num-1 whole items from SOURCE to DEST.
 471    From last item copy cpy_num bytes for regular item and cpy_num directory entries for
 472    directory item. */
 473 static int leaf_copy_items(struct buffer_info *dest_bi, struct buffer_head *src,
 474                            int last_first, int cpy_num, int cpy_bytes)
 475 {
 476         struct buffer_head *dest;
 477         int pos, i, src_nr_item, bytes;
 478
 479         dest = dest_bi->bi_bh;
 480         RFALSE(!dest || !src, "vs-10210: !dest || !src");
 481         RFALSE(last_first != FIRST_TO_LAST && last_first != LAST_TO_FIRST,
 482                "vs-10220:last_first != FIRST_TO_LAST && last_first != LAST_TO_FIRST");
 483         RFALSE(B_NR_ITEMS(src) < cpy_num,
 484                "vs-10230: No enough items: %d, req. %d", B_NR_ITEMS(src),
 485                cpy_num);
 486         RFALSE(cpy_num < 0, "vs-10240: cpy_num < 0 (%d)", cpy_num);
 487
 488         if (cpy_num == 0)
 489                 return 0;
 490
 491         if (last_first == FIRST_TO_LAST) {
 492                 /* copy items to left */
 493                 pos = 0;
 494                 if (cpy_num == 1)
 495                         bytes = cpy_bytes;
 496                 else
 497                         bytes = -1;
 498
 499                 /* copy the first item or it part or nothing to the end of the DEST (i = leaf_copy_boundary_item(DEST,SOURCE,0,bytes)) */
 500                 i = leaf_copy_boundary_item(dest_bi, src, FIRST_TO_LAST, bytes);
 501                 cpy_num -= i;
 502                 if (cpy_num == 0)
 503                         return i;
 504                 pos += i;
 505                 if (cpy_bytes == -1)
 506                         /* copy first cpy_num items starting from position 'pos' of SOURCE to end of DEST */
 507                         leaf_copy_items_entirely(dest_bi, src, FIRST_TO_LAST,
 508                                                  pos, cpy_num);
 509                 else {
 510                         /* copy first cpy_num-1 items starting from position 'pos-1' of the SOURCE to the end of the DEST */
 511                         leaf_copy_items_entirely(dest_bi, src, FIRST_TO_LAST,
 512                                                  pos, cpy_num - 1);
 513
 514                         /* copy part of the item which number is cpy_num+pos-1 to the end of the DEST */
 515                         leaf_item_bottle(dest_bi, src, FIRST_TO_LAST,
 516                                          cpy_num + pos - 1, cpy_bytes);
 517                 }
 518         } else {
 519                 /* copy items to right */
 520                 src_nr_item = B_NR_ITEMS(src);
 521                 if (cpy_num == 1)
 522                         bytes = cpy_bytes;
 523                 else
 524                         bytes = -1;
 525
 526                 /* copy the last item or it part or nothing to the begin of the DEST (i = leaf_copy_boundary_item(DEST,SOURCE,1,bytes)); */
 527                 i = leaf_copy_boundary_item(dest_bi, src, LAST_TO_FIRST, bytes);
 528
 529                 cpy_num -= i;
 530                 if (cpy_num == 0)
 531                         return i;
 532
 533                 pos = src_nr_item - cpy_num - i;
 534                 if (cpy_bytes == -1) {
 535                         /* starting from position 'pos' copy last cpy_num items of SOURCE to begin of DEST */
 536                         leaf_copy_items_entirely(dest_bi, src, LAST_TO_FIRST,
 537                                                  pos, cpy_num);
 538                 } else {
 539                         /* copy last cpy_num-1 items starting from position 'pos+1' of the SOURCE to the begin of the DEST; */
 540                         leaf_copy_items_entirely(dest_bi, src, LAST_TO_FIRST,
 541                                                  pos + 1, cpy_num - 1);
 542
 543                         /* copy part of the item which number is pos to the begin of the DEST */
 544                         leaf_item_bottle(dest_bi, src, LAST_TO_FIRST, pos,
 545                                          cpy_bytes);
 546                 }
 547         }
 548         return i;
 549 }
 550
 551 /* there are types of coping: from S[0] to L[0], from S[0] to R[0],
 552    from R[0] to L[0]. for each of these we have to define parent and
 553    positions of destination and source buffers */
 554 static void leaf_define_dest_src_infos(int shift_mode, struct tree_balance *tb,
 555                                        struct buffer_info *dest_bi,
 556                                        struct buffer_info *src_bi,
 557                                        int *first_last,
 558                                        struct buffer_head *Snew)
 559 {
 560         memset(dest_bi, 0, sizeof(struct buffer_info));
 561         memset(src_bi, 0, sizeof(struct buffer_info));
 562
 563         /* define dest, src, dest parent, dest position */
 564         switch (shift_mode) {
 565         case LEAF_FROM_S_TO_L:  /* it is used in leaf_shift_left */
 566                 src_bi->tb = tb;
 567                 src_bi->bi_bh = PATH_PLAST_BUFFER(tb->tb_path);
 568                 src_bi->bi_parent = PATH_H_PPARENT(tb->tb_path, 0);
 569                 src_bi->bi_position = PATH_H_B_ITEM_ORDER(tb->tb_path, 0);      /* src->b_item_order */
 570                 dest_bi->tb = tb;
 571                 dest_bi->bi_bh = tb->L[0];
 572                 dest_bi->bi_parent = tb->FL[0];
 573                 dest_bi->bi_position = get_left_neighbor_position(tb, 0);
 574                 *first_last = FIRST_TO_LAST;
 575                 break;
 576
 577         case LEAF_FROM_S_TO_R:  /* it is used in leaf_shift_right */
 578                 src_bi->tb = tb;
 579                 src_bi->bi_bh = PATH_PLAST_BUFFER(tb->tb_path);
 580                 src_bi->bi_parent = PATH_H_PPARENT(tb->tb_path, 0);
 581                 src_bi->bi_position = PATH_H_B_ITEM_ORDER(tb->tb_path, 0);
 582                 dest_bi->tb = tb;
 583                 dest_bi->bi_bh = tb->R[0];
 584                 dest_bi->bi_parent = tb->FR[0];
 585                 dest_bi->bi_position = get_right_neighbor_position(tb, 0);
 586                 *first_last = LAST_TO_FIRST;
 587                 break;
 588
 589         case LEAF_FROM_R_TO_L:  /* it is used in balance_leaf_when_delete */
 590                 src_bi->tb = tb;
 591                 src_bi->bi_bh = tb->R[0];
 592                 src_bi->bi_parent = tb->FR[0];
 593                 src_bi->bi_position = get_right_neighbor_position(tb, 0);
 594                 dest_bi->tb = tb;
 595                 dest_bi->bi_bh = tb->L[0];
 596                 dest_bi->bi_parent = tb->FL[0];
 597                 dest_bi->bi_position = get_left_neighbor_position(tb, 0);
 598                 *first_last = FIRST_TO_LAST;
 599                 break;
 600
 601         case LEAF_FROM_L_TO_R:  /* it is used in balance_leaf_when_delete */
 602                 src_bi->tb = tb;
 603                 src_bi->bi_bh = tb->L[0];
 604                 src_bi->bi_parent = tb->FL[0];
 605                 src_bi->bi_position = get_left_neighbor_position(tb, 0);
 606                 dest_bi->tb = tb;
 607                 dest_bi->bi_bh = tb->R[0];
 608                 dest_bi->bi_parent = tb->FR[0];
 609                 dest_bi->bi_position = get_right_neighbor_position(tb, 0);
 610                 *first_last = LAST_TO_FIRST;
 611                 break;
 612
 613         case LEAF_FROM_S_TO_SNEW:
 614                 src_bi->tb = tb;
 615                 src_bi->bi_bh = PATH_PLAST_BUFFER(tb->tb_path);
 616                 src_bi->bi_parent = PATH_H_PPARENT(tb->tb_path, 0);
 617                 src_bi->bi_position = PATH_H_B_ITEM_ORDER(tb->tb_path, 0);
 618                 dest_bi->tb = tb;
 619                 dest_bi->bi_bh = Snew;
 620                 dest_bi->bi_parent = NULL;
 621                 dest_bi->bi_position = 0;
 622                 *first_last = LAST_TO_FIRST;
 623                 break;
 624
 625         default:
 626                 reiserfs_panic(sb_from_bi(src_bi), "vs-10250",
 627                                "shift type is unknown (%d)", shift_mode);
 628         }
 629         RFALSE(!src_bi->bi_bh || !dest_bi->bi_bh,
 630                "vs-10260: mode==%d, source (%p) or dest (%p) buffer is initialized incorrectly",
 631                shift_mode, src_bi->bi_bh, dest_bi->bi_bh);
 632 }
 633
 634 /* copy mov_num items and mov_bytes of the (mov_num-1)th item to
 635    neighbor. Delete them from source */
 636 int leaf_move_items(int shift_mode, struct tree_balance *tb, int mov_num,
 637                     int mov_bytes, struct buffer_head *Snew)
 638 {
 639         int ret_value;
 640         struct buffer_info dest_bi, src_bi;
 641         int first_last;
 642
 643         leaf_define_dest_src_infos(shift_mode, tb, &dest_bi, &src_bi,
 644                                    &first_last, Snew);
 645
 646         ret_value =
 647             leaf_copy_items(&dest_bi, src_bi.bi_bh, first_last, mov_num,
 648                             mov_bytes);
 649
 650         leaf_delete_items(&src_bi, first_last,
 651                           (first_last ==
 652                            FIRST_TO_LAST) ? 0 : (B_NR_ITEMS(src_bi.bi_bh) -
 653                                                  mov_num), mov_num, mov_bytes);
 654
 655         return ret_value;
 656 }
 657
 658 /* Shift shift_num items (and shift_bytes of last shifted item if shift_bytes != -1)
 659    from S[0] to L[0] and replace the delimiting key */
 660 int leaf_shift_left(struct tree_balance *tb, int shift_num, int shift_bytes)
 661 {
 662         struct buffer_head *S0 = PATH_PLAST_BUFFER(tb->tb_path);
 663         int i;
 664
 665         /* move shift_num (and shift_bytes bytes) items from S[0] to left neighbor L[0] */
 666         i = leaf_move_items(LEAF_FROM_S_TO_L, tb, shift_num, shift_bytes, NULL);
 667
 668         if (shift_num) {
 669                 if (B_NR_ITEMS(S0) == 0) {      /* number of items in S[0] == 0 */
 670
 671                         RFALSE(shift_bytes != -1,
 672                                "vs-10270: S0 is empty now, but shift_bytes != -1 (%d)",
 673                                shift_bytes);
 674 #ifdef CONFIG_REISERFS_CHECK
 675                         if (tb->tb_mode == M_PASTE || tb->tb_mode == M_INSERT) {
 676                                 print_cur_tb("vs-10275");
 677                                 reiserfs_panic(tb->tb_sb, "vs-10275",
 678                                                "balance condition corrupted "
 679                                                "(%c)", tb->tb_mode);
 680                         }
 681 #endif
 682
 683                         if (PATH_H_POSITION(tb->tb_path, 1) == 0)
 684                                 replace_key(tb, tb->CFL[0], tb->lkey[0],
 685                                             PATH_H_PPARENT(tb->tb_path, 0), 0);
 686
 687                 } else {
 688                         /* replace lkey in CFL[0] by 0-th key from S[0]; */
 689                         replace_key(tb, tb->CFL[0], tb->lkey[0], S0, 0);
 690
 691                         RFALSE((shift_bytes != -1 &&
 692                                 !(is_direntry_le_ih(B_N_PITEM_HEAD(S0, 0))
 693                                   && !I_ENTRY_COUNT(B_N_PITEM_HEAD(S0, 0)))) &&
 694                                (!op_is_left_mergeable
 695                                 (B_N_PKEY(S0, 0), S0->b_size)),
 696                                "vs-10280: item must be mergeable");
 697                 }
 698         }
 699
 700         return i;
 701 }
 702
 703 /* CLEANING STOPPED HERE */
 704
 705 /* Shift shift_num (shift_bytes) items from S[0] to the right neighbor, and replace the delimiting key */
 706 int leaf_shift_right(struct tree_balance *tb, int shift_num, int shift_bytes)
 707 {
 708         //  struct buffer_head * S0 = PATH_PLAST_BUFFER (tb->tb_path);
 709         int ret_value;
 710
 711         /* move shift_num (and shift_bytes) items from S[0] to right neighbor R[0] */
 712         ret_value =
 713             leaf_move_items(LEAF_FROM_S_TO_R, tb, shift_num, shift_bytes, NULL);
 714
 715         /* replace rkey in CFR[0] by the 0-th key from R[0] */
 716         if (shift_num) {
 717                 replace_key(tb, tb->CFR[0], tb->rkey[0], tb->R[0], 0);
 718
 719         }
 720
 721         return ret_value;
 722 }
 723
 724 static void leaf_delete_items_entirely(struct buffer_info *bi,
 725                                        int first, int del_num);
 726 /*  If del_bytes == -1, starting from position 'first' delete del_num items in whole in buffer CUR.
 727     If not.
 728     If last_first == 0. Starting from position 'first' delete del_num-1 items in whole. Delete part of body of
 729     the first item. Part defined by del_bytes. Don't delete first item header
 730     If last_first == 1. Starting from position 'first+1' delete del_num-1 items in whole. Delete part of body of
 731     the last item . Part defined by del_bytes. Don't delete last item header.
 732 */
 733 void leaf_delete_items(struct buffer_info *cur_bi, int last_first,
 734                        int first, int del_num, int del_bytes)
 735 {
 736         struct buffer_head *bh;
 737         int item_amount = B_NR_ITEMS(bh = cur_bi->bi_bh);
 738
 739         RFALSE(!bh, "10155: bh is not defined");
 740         RFALSE(del_num < 0, "10160: del_num can not be < 0. del_num==%d",
 741                del_num);
 742         RFALSE(first < 0
 743                || first + del_num > item_amount,
 744                "10165: invalid number of first item to be deleted (%d) or "
 745                "no so much items (%d) to delete (only %d)", first,
 746                first + del_num, item_amount);
 747
 748         if (del_num == 0)
 749                 return;
 750
 751         if (first == 0 && del_num == item_amount && del_bytes == -1) {
 752                 make_empty_node(cur_bi);
 753                 do_balance_mark_leaf_dirty(cur_bi->tb, bh, 0);
 754                 return;
 755         }
 756
 757         if (del_bytes == -1)
 758                 /* delete del_num items beginning from item in position first */
 759                 leaf_delete_items_entirely(cur_bi, first, del_num);
 760         else {
 761                 if (last_first == FIRST_TO_LAST) {
 762                         /* delete del_num-1 items beginning from item in position first  */
 763                         leaf_delete_items_entirely(cur_bi, first, del_num - 1);
 764
 765                         /* delete the part of the first item of the bh
 766                            do not delete item header
 767                          */
 768                         leaf_cut_from_buffer(cur_bi, 0, 0, del_bytes);
 769                 } else {
 770                         struct item_head *ih;
 771                         int len;
 772
 773                         /* delete del_num-1 items beginning from item in position first+1  */
 774                         leaf_delete_items_entirely(cur_bi, first + 1,
 775                                                    del_num - 1);
 776
 777                         if (is_direntry_le_ih
 778                             (ih = B_N_PITEM_HEAD(bh, B_NR_ITEMS(bh) - 1)))
 779                                 /* the last item is directory  */
 780                                 /* len = numbers of directory entries in this item */
 781                                 len = ih_entry_count(ih);
 782                         else
 783                                 /* len = body len of item */
 784                                 len = ih_item_len(ih);
 785
 786                         /* delete the part of the last item of the bh
 787                            do not delete item header
 788                          */
 789                         leaf_cut_from_buffer(cur_bi, B_NR_ITEMS(bh) - 1,
 790                                              len - del_bytes, del_bytes);
 791                 }
 792         }
 793 }
 794
 795 /* insert item into the leaf node in position before */
 796 void leaf_insert_into_buf(struct buffer_info *bi, int before,
 797                           struct item_head *inserted_item_ih,
 798                           const char *inserted_item_body, int zeros_number)
 799 {
 800         struct buffer_head *bh = bi->bi_bh;
 801         int nr, free_space;
 802         struct block_head *blkh;
 803         struct item_head *ih;
 804         int i;
 805         int last_loc, unmoved_loc;
 806         char *to;
 807
 808         blkh = B_BLK_HEAD(bh);
 809         nr = blkh_nr_item(blkh);
 810         free_space = blkh_free_space(blkh);
 811
 812         /* check free space */
 813         RFALSE(free_space < ih_item_len(inserted_item_ih) + IH_SIZE,
 814                "vs-10170: not enough free space in block %z, new item %h",
 815                bh, inserted_item_ih);
 816         RFALSE(zeros_number > ih_item_len(inserted_item_ih),
 817                "vs-10172: zero number == %d, item length == %d",
 818                zeros_number, ih_item_len(inserted_item_ih));
 819
 820         /* get item new item must be inserted before */
 821         ih = B_N_PITEM_HEAD(bh, before);
 822
 823         /* prepare space for the body of new item */
 824         last_loc = nr ? ih_location(&(ih[nr - before - 1])) : bh->b_size;
 825         unmoved_loc = before ? ih_location(ih - 1) : bh->b_size;
 826
 827         memmove(bh->b_data + last_loc - ih_item_len(inserted_item_ih),
 828                 bh->b_data + last_loc, unmoved_loc - last_loc);
 829
 830         to = bh->b_data + unmoved_loc - ih_item_len(inserted_item_ih);
 831         memset(to, 0, zeros_number);
 832         to += zeros_number;
 833
 834         /* copy body to prepared space */
 835         if (inserted_item_body)
 836                 memmove(to, inserted_item_body,
 837                         ih_item_len(inserted_item_ih) - zeros_number);
 838         else
 839                 memset(to, '\0', ih_item_len(inserted_item_ih) - zeros_number);
 840
 841         /* insert item header */
 842         memmove(ih + 1, ih, IH_SIZE * (nr - before));
 843         memmove(ih, inserted_item_ih, IH_SIZE);
 844
 845         /* change locations */
 846         for (i = before; i < nr + 1; i++) {
 847                 unmoved_loc -= ih_item_len(&(ih[i - before]));
 848                 put_ih_location(&(ih[i - before]), unmoved_loc);
 849         }
 850
 851         /* sizes, free space, item number */
 852         set_blkh_nr_item(blkh, blkh_nr_item(blkh) + 1);
 853         set_blkh_free_space(blkh,
 854                             free_space - (IH_SIZE +
 855                                           ih_item_len(inserted_item_ih)));
 856         do_balance_mark_leaf_dirty(bi->tb, bh, 1);
 857
 858         if (bi->bi_parent) {
 859                 struct disk_child *t_dc;
 860                 t_dc = B_N_CHILD(bi->bi_parent, bi->bi_position);
 861                 put_dc_size(t_dc,
 862                             dc_size(t_dc) + (IH_SIZE +
 863                                              ih_item_len(inserted_item_ih)));
 864                 do_balance_mark_internal_dirty(bi->tb, bi->bi_parent, 0);
 865         }
 866 }
 867
 868 /* paste paste_size bytes to affected_item_num-th item.
 869    When item is a directory, this only prepare space for new entries */
 870 void leaf_paste_in_buffer(struct buffer_info *bi, int affected_item_num,
 871                           int pos_in_item, int paste_size,
 872                           const char *body, int zeros_number)
 873 {
 874         struct buffer_head *bh = bi->bi_bh;
 875         int nr, free_space;
 876         struct block_head *blkh;
 877         struct item_head *ih;
 878         int i;
 879         int last_loc, unmoved_loc;
 880
 881         blkh = B_BLK_HEAD(bh);
 882         nr = blkh_nr_item(blkh);
 883         free_space = blkh_free_space(blkh);
 884
 885         /* check free space */
 886         RFALSE(free_space < paste_size,
 887                "vs-10175: not enough free space: needed %d, available %d",
 888                paste_size, free_space);
 889
 890 #ifdef CONFIG_REISERFS_CHECK
 891         if (zeros_number > paste_size) {
 892                 struct super_block *sb = NULL;
 893                 if (bi && bi->tb)
 894                         sb = bi->tb->tb_sb;
 895                 print_cur_tb("10177");
 896                 reiserfs_panic(sb, "vs-10177",
 897                                "zeros_number == %d, paste_size == %d",
 898                                zeros_number, paste_size);
 899         }
 900 #endif                          /* CONFIG_REISERFS_CHECK */
 901
 902         /* item to be appended */
 903         ih = B_N_PITEM_HEAD(bh, affected_item_num);
 904
 905         last_loc = ih_location(&(ih[nr - affected_item_num - 1]));
 906         unmoved_loc = affected_item_num ? ih_location(ih - 1) : bh->b_size;
 907
 908         /* prepare space */
 909         memmove(bh->b_data + last_loc - paste_size, bh->b_data + last_loc,
 910                 unmoved_loc - last_loc);
 911
 912         /* change locations */
 913         for (i = affected_item_num; i < nr; i++)
 914                 put_ih_location(&(ih[i - affected_item_num]),
 915                                 ih_location(&(ih[i - affected_item_num])) -
 916                                 paste_size);
 917
 918         if (body) {
 919                 if (!is_direntry_le_ih(ih)) {
 920                         if (!pos_in_item) {
 921                                 /* shift data to right */
 922                                 memmove(bh->b_data + ih_location(ih) +
 923                                         paste_size,
 924                                         bh->b_data + ih_location(ih),
 925                                         ih_item_len(ih));
 926                                 /* paste data in the head of item */
 927                                 memset(bh->b_data + ih_location(ih), 0,
 928                                        zeros_number);
 929                                 memcpy(bh->b_data + ih_location(ih) +
 930                                        zeros_number, body,
 931                                        paste_size - zeros_number);
 932                         } else {
 933                                 memset(bh->b_data + unmoved_loc - paste_size, 0,
 934                                        zeros_number);
 935                                 memcpy(bh->b_data + unmoved_loc - paste_size +
 936                                        zeros_number, body,
 937                                        paste_size - zeros_number);
 938                         }
 939                 }
 940         } else
 941                 memset(bh->b_data + unmoved_loc - paste_size, '\0', paste_size);
 942
 943         put_ih_item_len(ih, ih_item_len(ih) + paste_size);
 944
 945         /* change free space */
 946         set_blkh_free_space(blkh, free_space - paste_size);
 947
 948         do_balance_mark_leaf_dirty(bi->tb, bh, 0);
 949
 950         if (bi->bi_parent) {
 951                 struct disk_child *t_dc =
 952                     B_N_CHILD(bi->bi_parent, bi->bi_position);
 953                 put_dc_size(t_dc, dc_size(t_dc) + paste_size);
 954                 do_balance_mark_internal_dirty(bi->tb, bi->bi_parent, 0);
 955         }
 956 }
 957
 958 /* cuts DEL_COUNT entries beginning from FROM-th entry. Directory item
 959    does not have free space, so it moves DEHs and remaining records as
 960    necessary. Return value is size of removed part of directory item
 961    in bytes. */
 962 static int leaf_cut_entries(struct buffer_head *bh,
 963                             struct item_head *ih, int from, int del_count)
 964 {
 965         char *item;
 966         struct reiserfs_de_head *deh;
 967         int prev_record_offset; /* offset of record, that is (from-1)th */
 968         char *prev_record;      /* */
 969         int cut_records_len;    /* length of all removed records */
 970         int i;
 971
 972         /* make sure, that item is directory and there are enough entries to
 973            remove */
 974         RFALSE(!is_direntry_le_ih(ih), "10180: item is not directory item");
 975         RFALSE(I_ENTRY_COUNT(ih) < from + del_count,
 976                "10185: item contains not enough entries: entry_cout = %d, from = %d, to delete = %d",
 977                I_ENTRY_COUNT(ih), from, del_count);
 978
 979         if (del_count == 0)
 980                 return 0;
 981
 982         /* first byte of item */
 983         item = bh->b_data + ih_location(ih);
 984
 985         /* entry head array */
 986         deh = B_I_DEH(bh, ih);
 987
 988         /* first byte of remaining entries, those are BEFORE cut entries
 989            (prev_record) and length of all removed records (cut_records_len) */
 990         prev_record_offset =
 991             (from ? deh_location(&(deh[from - 1])) : ih_item_len(ih));
 992         cut_records_len = prev_record_offset /*from_record */  -
 993             deh_location(&(deh[from + del_count - 1]));
 994         prev_record = item + prev_record_offset;
 995
 996         /* adjust locations of remaining entries */
 997         for (i = I_ENTRY_COUNT(ih) - 1; i > from + del_count - 1; i--)
 998                 put_deh_location(&(deh[i]),
 999                                  deh_location(&deh[i]) -
1000                                  (DEH_SIZE * del_count));
1001
1002         for (i = 0; i < from; i++)
1003                 put_deh_location(&(deh[i]),
1004                                  deh_location(&deh[i]) - (DEH_SIZE * del_count +
1005                                                           cut_records_len));
1006
1007         put_ih_entry_count(ih, ih_entry_count(ih) - del_count);
1008
1009         /* shift entry head array and entries those are AFTER removed entries */
1010         memmove((char *)(deh + from),
1011                 deh + from + del_count,
1012                 prev_record - cut_records_len - (char *)(deh + from +
1013                                                          del_count));
1014
1015         /* shift records, those are BEFORE removed entries */
1016         memmove(prev_record - cut_records_len - DEH_SIZE * del_count,
1017                 prev_record, item + ih_item_len(ih) - prev_record);
1018
1019         return DEH_SIZE * del_count + cut_records_len;
1020 }
1021
1022 /*  when cut item is part of regular file
1023         pos_in_item - first byte that must be cut
1024         cut_size - number of bytes to be cut beginning from pos_in_item
1025
1026    when cut item is part of directory
1027         pos_in_item - number of first deleted entry
1028         cut_size - count of deleted entries
1029     */
1030 void leaf_cut_from_buffer(struct buffer_info *bi, int cut_item_num,
1031                           int pos_in_item, int cut_size)
1032 {
1033         int nr;
1034         struct buffer_head *bh = bi->bi_bh;
1035         struct block_head *blkh;
1036         struct item_head *ih;
1037         int last_loc, unmoved_loc;
1038         int i;
1039
1040         blkh = B_BLK_HEAD(bh);
1041         nr = blkh_nr_item(blkh);
1042
1043         /* item head of truncated item */
1044         ih = B_N_PITEM_HEAD(bh, cut_item_num);
1045
1046         if (is_direntry_le_ih(ih)) {
1047                 /* first cut entry () */
1048                 cut_size = leaf_cut_entries(bh, ih, pos_in_item, cut_size);
1049                 if (pos_in_item == 0) {
1050                         /* change key */
1051                         RFALSE(cut_item_num,
1052                                "when 0-th enrty of item is cut, that item must be first in the node, not %d-th",
1053                                cut_item_num);
1054                         /* change item key by key of first entry in the item */
1055                         set_le_ih_k_offset(ih, deh_offset(B_I_DEH(bh, ih)));
1056                         /*memcpy (&ih->ih_key.k_offset, &(B_I_DEH (bh, ih)->deh_offset), SHORT_KEY_SIZE); */
1057                 }
1058         } else {
1059                 /* item is direct or indirect */
1060                 RFALSE(is_statdata_le_ih(ih), "10195: item is stat data");
1061                 RFALSE(pos_in_item && pos_in_item + cut_size != ih_item_len(ih),
1062                        "10200: invalid offset (%lu) or trunc_size (%lu) or ih_item_len (%lu)",
1063                        (long unsigned)pos_in_item, (long unsigned)cut_size,
1064                        (long unsigned)ih_item_len(ih));
1065
1066                 /* shift item body to left if cut is from the head of item */
1067                 if (pos_in_item == 0) {
1068                         memmove(bh->b_data + ih_location(ih),
1069                                 bh->b_data + ih_location(ih) + cut_size,
1070                                 ih_item_len(ih) - cut_size);
1071
1072                         /* change key of item */
1073                         if (is_direct_le_ih(ih))
1074                                 set_le_ih_k_offset(ih,
1075                                                    le_ih_k_offset(ih) +
1076                                                    cut_size);
1077                         else {
1078                                 set_le_ih_k_offset(ih,
1079                                                    le_ih_k_offset(ih) +
1080                                                    (cut_size / UNFM_P_SIZE) *
1081                                                    bh->b_size);
1082                                 RFALSE(ih_item_len(ih) == cut_size
1083                                        && get_ih_free_space(ih),
1084                                        "10205: invalid ih_free_space (%h)", ih);
1085                         }
1086                 }
1087         }
1088
1089         /* location of the last item */
1090         last_loc = ih_location(&(ih[nr - cut_item_num - 1]));
1091
1092         /* location of the item, which is remaining at the same place */
1093         unmoved_loc = cut_item_num ? ih_location(ih - 1) : bh->b_size;
1094
1095         /* shift */
1096         memmove(bh->b_data + last_loc + cut_size, bh->b_data + last_loc,
1097                 unmoved_loc - last_loc - cut_size);
1098
1099         /* change item length */
1100         put_ih_item_len(ih, ih_item_len(ih) - cut_size);
1101
1102         if (is_indirect_le_ih(ih)) {
1103                 if (pos_in_item)
1104                         set_ih_free_space(ih, 0);
1105         }
1106
1107         /* change locations */
1108         for (i = cut_item_num; i < nr; i++)
1109                 put_ih_location(&(ih[i - cut_item_num]),
1110                                 ih_location(&ih[i - cut_item_num]) + cut_size);
1111
1112         /* size, free space */
1113         set_blkh_free_space(blkh, blkh_free_space(blkh) + cut_size);
1114
1115         do_balance_mark_leaf_dirty(bi->tb, bh, 0);
1116
1117         if (bi->bi_parent) {
1118                 struct disk_child *t_dc;
1119                 t_dc = B_N_CHILD(bi->bi_parent, bi->bi_position);
1120                 put_dc_size(t_dc, dc_size(t_dc) - cut_size);
1121                 do_balance_mark_internal_dirty(bi->tb, bi->bi_parent, 0);
1122         }
1123 }
1124
1125 /* delete del_num items from buffer starting from the first'th item */
1126 static void leaf_delete_items_entirely(struct buffer_info *bi,
1127                                        int first, int del_num)
1128 {
1129         struct buffer_head *bh = bi->bi_bh;
1130         int nr;
1131         int i, j;
1132         int last_loc, last_removed_loc;
1133         struct block_head *blkh;
1134         struct item_head *ih;
1135
1136         RFALSE(bh == NULL, "10210: buffer is 0");
1137         RFALSE(del_num < 0, "10215: del_num less than 0 (%d)", del_num);
1138
1139         if (del_num == 0)
1140                 return;
1141
1142         blkh = B_BLK_HEAD(bh);
1143         nr = blkh_nr_item(blkh);
1144
1145         RFALSE(first < 0 || first + del_num > nr,
1146                "10220: first=%d, number=%d, there is %d items", first, del_num,
1147                nr);
1148
1149         if (first == 0 && del_num == nr) {
1150                 /* this does not work */
1151                 make_empty_node(bi);
1152
1153                 do_balance_mark_leaf_dirty(bi->tb, bh, 0);
1154                 return;
1155         }
1156
1157         ih = B_N_PITEM_HEAD(bh, first);
1158
1159         /* location of unmovable item */
1160         j = (first == 0) ? bh->b_size : ih_location(ih - 1);
1161
1162         /* delete items */
1163         last_loc = ih_location(&(ih[nr - 1 - first]));
1164         last_removed_loc = ih_location(&(ih[del_num - 1]));
1165
1166         memmove(bh->b_data + last_loc + j - last_removed_loc,
1167                 bh->b_data + last_loc, last_removed_loc - last_loc);
1168
1169         /* delete item headers */
1170         memmove(ih, ih + del_num, (nr - first - del_num) * IH_SIZE);
1171
1172         /* change item location */
1173         for (i = first; i < nr - del_num; i++)
1174                 put_ih_location(&(ih[i - first]),
1175                                 ih_location(&(ih[i - first])) + (j -
1176                                                                  last_removed_loc));
1177
1178         /* sizes, item number */
1179         set_blkh_nr_item(blkh, blkh_nr_item(blkh) - del_num);
1180         set_blkh_free_space(blkh,
1181                             blkh_free_space(blkh) + (j - last_removed_loc +
1182                                                      IH_SIZE * del_num));
1183
1184         do_balance_mark_leaf_dirty(bi->tb, bh, 0);
1185
1186         if (bi->bi_parent) {
1187                 struct disk_child *t_dc =
1188                     B_N_CHILD(bi->bi_parent, bi->bi_position);
1189                 put_dc_size(t_dc,
1190                             dc_size(t_dc) - (j - last_removed_loc +
1191                                              IH_SIZE * del_num));
1192                 do_balance_mark_internal_dirty(bi->tb, bi->bi_parent, 0);
1193         }
1194 }
1195
1196 /* paste new_entry_count entries (new_dehs, records) into position before to item_num-th item */
1197 void leaf_paste_entries(struct buffer_info *bi,
1198                         int item_num,
1199                         int before,
1200                         int new_entry_count,
1201                         struct reiserfs_de_head *new_dehs,
1202                         const char *records, int paste_size)
1203 {
1204         struct item_head *ih;
1205         char *item;
1206         struct reiserfs_de_head *deh;
1207         char *insert_point;
1208         int i, old_entry_num;
1209         struct buffer_head *bh = bi->bi_bh;
1210
1211         if (new_entry_count == 0)
1212                 return;
1213
1214         ih = B_N_PITEM_HEAD(bh, item_num);
1215
1216         /* make sure, that item is directory, and there are enough records in it */
1217         RFALSE(!is_direntry_le_ih(ih), "10225: item is not directory item");
1218         RFALSE(I_ENTRY_COUNT(ih) < before,
1219                "10230: there are no entry we paste entries before. entry_count = %d, before = %d",
1220                I_ENTRY_COUNT(ih), before);
1221
1222         /* first byte of dest item */
1223         item = bh->b_data + ih_location(ih);
1224
1225         /* entry head array */
1226         deh = B_I_DEH(bh, ih);
1227
1228         /* new records will be pasted at this point */
1229         insert_point =
1230             item +
1231             (before ? deh_location(&(deh[before - 1]))
1232              : (ih_item_len(ih) - paste_size));
1233
1234         /* adjust locations of records that will be AFTER new records */
1235         for (i = I_ENTRY_COUNT(ih) - 1; i >= before; i--)
1236                 put_deh_location(&(deh[i]),
1237                                  deh_location(&(deh[i])) +
1238                                  (DEH_SIZE * new_entry_count));
1239
1240         /* adjust locations of records that will be BEFORE new records */
1241         for (i = 0; i < before; i++)
1242                 put_deh_location(&(deh[i]),
1243                                  deh_location(&(deh[i])) + paste_size);
1244
1245         old_entry_num = I_ENTRY_COUNT(ih);
1246         put_ih_entry_count(ih, ih_entry_count(ih) + new_entry_count);
1247
1248         /* prepare space for pasted records */
1249         memmove(insert_point + paste_size, insert_point,
1250                 item + (ih_item_len(ih) - paste_size) - insert_point);
1251
1252         /* copy new records */
1253         memcpy(insert_point + DEH_SIZE * new_entry_count, records,
1254                paste_size - DEH_SIZE * new_entry_count);
1255
1256         /* prepare space for new entry heads */
1257         deh += before;
1258         memmove((char *)(deh + new_entry_count), deh,
1259                 insert_point - (char *)deh);
1260
1261         /* copy new entry heads */
1262         deh = (struct reiserfs_de_head *)((char *)deh);
1263         memcpy(deh, new_dehs, DEH_SIZE * new_entry_count);
1264
1265         /* set locations of new records */
1266         for (i = 0; i < new_entry_count; i++) {
1267                 put_deh_location(&(deh[i]),
1268                                  deh_location(&(deh[i])) +
1269                                  (-deh_location
1270                                   (&(new_dehs[new_entry_count - 1])) +
1271                                   insert_point + DEH_SIZE * new_entry_count -
1272                                   item));
1273         }
1274
1275         /* change item key if necessary (when we paste before 0-th entry */
1276         if (!before) {
1277                 set_le_ih_k_offset(ih, deh_offset(new_dehs));
1278 /*      memcpy (&ih->ih_key.k_offset,
1279                        &new_dehs->deh_offset, SHORT_KEY_SIZE);*/
1280         }
1281 #ifdef CONFIG_REISERFS_CHECK
1282         {
1283                 int prev, next;
1284                 /* check record locations */
1285                 deh = B_I_DEH(bh, ih);
1286                 for (i = 0; i < I_ENTRY_COUNT(ih); i++) {
1287                         next =
1288                             (i <
1289                              I_ENTRY_COUNT(ih) -
1290                              1) ? deh_location(&(deh[i + 1])) : 0;
1291                         prev = (i != 0) ? deh_location(&(deh[i - 1])) : 0;
1292
1293                         if (prev && prev <= deh_location(&(deh[i])))
1294                                 reiserfs_error(sb_from_bi(bi), "vs-10240",
1295                                                "directory item (%h) "
1296                                                "corrupted (prev %a, "
1297                                                "cur(%d) %a)",
1298                                                ih, deh + i - 1, i, deh + i);
1299                         if (next && next >= deh_location(&(deh[i])))
1300                                 reiserfs_error(sb_from_bi(bi), "vs-10250",
1301                                                "directory item (%h) "
1302                                                "corrupted (cur(%d) %a, "
1303                                                "next %a)",
1304                                                ih, i, deh + i, deh + i + 1);
1305                 }
1306         }
1307 #endif
1308
1309 }