fs/reiserfs/lbalance.c

   1 /*
   2  * Copyright 2000 by Hans Reiser, licensing governed by reiserfs/README
   3  */
   4
   5 #include <linux/config.h>
   6 #include <asm/uaccess.h>
   7 #include <linux/string.h>
   8 #include <linux/time.h>
   9 #include <linux/reiserfs_fs.h>
  10 #include <linux/buffer_head.h>
  11
  12 /* these are used in do_balance.c */
  13
  14 /* leaf_move_items
  15    leaf_shift_left
  16    leaf_shift_right
  17    leaf_delete_items
  18    leaf_insert_into_buf
  19    leaf_paste_in_buffer
  20    leaf_cut_from_buffer
  21    leaf_paste_entries
  22    */
  23
  24 /* copy copy_count entries from source directory item to dest buffer (creating new item if needed) */
  25 static void leaf_copy_dir_entries(struct buffer_info *dest_bi,
  26                                   struct buffer_head *source, int last_first,
  27                                   int item_num, int from, int copy_count)
  28 {
  29         struct buffer_head *dest = dest_bi->bi_bh;
  30         int item_num_in_dest;   /* either the number of target item,
  31                                    or if we must create a new item,
  32                                    the number of the item we will
  33                                    create it next to */
  34         struct item_head *ih;
  35         struct reiserfs_de_head *deh;
  36         int copy_records_len;   /* length of all records in item to be copied */
  37         char *records;
  38
  39         ih = B_N_PITEM_HEAD(source, item_num);
  40
  41         RFALSE(!is_direntry_le_ih(ih), "vs-10000: item must be directory item");
  42
  43         /* length of all record to be copied and first byte of the last of them */
  44         deh = B_I_DEH(source, ih);
  45         if (copy_count) {
  46                 copy_records_len = (from ? deh_location(&(deh[from - 1])) :
  47                                     ih_item_len(ih)) -
  48                     deh_location(&(deh[from + copy_count - 1]));
  49                 records =
  50                     source->b_data + ih_location(ih) +
  51                     deh_location(&(deh[from + copy_count - 1]));
  52         } else {
  53                 copy_records_len = 0;
  54                 records = NULL;
  55         }
  56
  57         /* when copy last to first, dest buffer can contain 0 items */
  58         item_num_in_dest =
  59             (last_first ==
  60              LAST_TO_FIRST) ? ((B_NR_ITEMS(dest)) ? 0 : -1) : (B_NR_ITEMS(dest)
  61                                                                - 1);
  62
  63         /* if there are no items in dest or the first/last item in dest is not item of the same directory */
  64         if ((item_num_in_dest == -1) ||
  65             (last_first == FIRST_TO_LAST && le_ih_k_offset(ih) == DOT_OFFSET) ||
  66             (last_first == LAST_TO_FIRST
  67              && comp_short_le_keys /*COMP_SHORT_KEYS */ (&ih->ih_key,
  68                                                          B_N_PKEY(dest,
  69                                                                   item_num_in_dest))))
  70         {
  71                 /* create new item in dest */
  72                 struct item_head new_ih;
  73
  74                 /* form item header */
  75                 memcpy(&new_ih.ih_key, &ih->ih_key, KEY_SIZE);
  76                 put_ih_version(&new_ih, KEY_FORMAT_3_5);
  77                 /* calculate item len */
  78                 put_ih_item_len(&new_ih,
  79                                 DEH_SIZE * copy_count + copy_records_len);
  80                 put_ih_entry_count(&new_ih, 0);
  81
  82                 if (last_first == LAST_TO_FIRST) {
  83                         /* form key by the following way */
  84                         if (from < I_ENTRY_COUNT(ih)) {
  85                                 set_le_ih_k_offset(&new_ih,
  86                                                    deh_offset(&(deh[from])));
  87                                 /*memcpy (&new_ih.ih_key.k_offset, &deh[from].deh_offset, SHORT_KEY_SIZE); */
  88                         } else {
  89                                 /* no entries will be copied to this item in this function */
  90                                 set_le_ih_k_offset(&new_ih, U32_MAX);
  91                                 /* this item is not yet valid, but we want I_IS_DIRECTORY_ITEM to return 1 for it, so we -1 */
  92                         }
  93                         set_le_key_k_type(KEY_FORMAT_3_5, &(new_ih.ih_key),
  94                                           TYPE_DIRENTRY);
  95                 }
  96
  97                 /* insert item into dest buffer */
  98                 leaf_insert_into_buf(dest_bi,
  99                                      (last_first ==
 100                                       LAST_TO_FIRST) ? 0 : B_NR_ITEMS(dest),
 101                                      &new_ih, NULL, 0);
 102         } else {
 103                 /* prepare space for entries */
 104                 leaf_paste_in_buffer(dest_bi,
 105                                      (last_first ==
 106                                       FIRST_TO_LAST) ? (B_NR_ITEMS(dest) -
 107                                                         1) : 0, MAX_US_INT,
 108                                      DEH_SIZE * copy_count + copy_records_len,
 109                                      records, 0);
 110         }
 111
 112         item_num_in_dest =
 113             (last_first == FIRST_TO_LAST) ? (B_NR_ITEMS(dest) - 1) : 0;
 114
 115         leaf_paste_entries(dest_bi->bi_bh, item_num_in_dest,
 116                            (last_first ==
 117                             FIRST_TO_LAST) ? I_ENTRY_COUNT(B_N_PITEM_HEAD(dest,
 118                                                                           item_num_in_dest))
 119                            : 0, copy_count, deh + from, records,
 120                            DEH_SIZE * copy_count + copy_records_len);
 121 }
 122
 123 /* Copy the first (if last_first == FIRST_TO_LAST) or last (last_first == LAST_TO_FIRST) item or
 124    part of it or nothing (see the return 0 below) from SOURCE to the end
 125    (if last_first) or beginning (!last_first) of the DEST */
 126 /* returns 1 if anything was copied, else 0 */
 127 static int leaf_copy_boundary_item(struct buffer_info *dest_bi,
 128                                    struct buffer_head *src, int last_first,
 129                                    int bytes_or_entries)
 130 {
 131         struct buffer_head *dest = dest_bi->bi_bh;
 132         int dest_nr_item, src_nr_item;  /* number of items in the source and destination buffers */
 133         struct item_head *ih;
 134         struct item_head *dih;
 135
 136         dest_nr_item = B_NR_ITEMS(dest);
 137
 138         if (last_first == FIRST_TO_LAST) {
 139                 /* if ( DEST is empty or first item of SOURCE and last item of DEST are the items of different objects
 140                    or of different types ) then there is no need to treat this item differently from the other items
 141                    that we copy, so we return */
 142                 ih = B_N_PITEM_HEAD(src, 0);
 143                 dih = B_N_PITEM_HEAD(dest, dest_nr_item - 1);
 144                 if (!dest_nr_item
 145                     || (!op_is_left_mergeable(&(ih->ih_key), src->b_size)))
 146                         /* there is nothing to merge */
 147                         return 0;
 148
 149                 RFALSE(!ih_item_len(ih),
 150                        "vs-10010: item can not have empty length");
 151
 152                 if (is_direntry_le_ih(ih)) {
 153                         if (bytes_or_entries == -1)
 154                                 /* copy all entries to dest */
 155                                 bytes_or_entries = ih_entry_count(ih);
 156                         leaf_copy_dir_entries(dest_bi, src, FIRST_TO_LAST, 0, 0,
 157                                               bytes_or_entries);
 158                         return 1;
 159                 }
 160
 161                 /* copy part of the body of the first item of SOURCE to the end of the body of the last item of the DEST
 162                    part defined by 'bytes_or_entries'; if bytes_or_entries == -1 copy whole body; don't create new item header
 163                  */
 164                 if (bytes_or_entries == -1)
 165                         bytes_or_entries = ih_item_len(ih);
 166
 167 #ifdef CONFIG_REISERFS_CHECK
 168                 else {
 169                         if (bytes_or_entries == ih_item_len(ih)
 170                             && is_indirect_le_ih(ih))
 171                                 if (get_ih_free_space(ih))
 172                                         reiserfs_panic(NULL,
 173                                                        "vs-10020: leaf_copy_boundary_item: "
 174                                                        "last unformatted node must be filled entirely (%h)",
 175                                                        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(NULL,
 627                                "vs-10250: leaf_define_dest_src_infos: shift type is unknown (%d)",
 628                                shift_mode);
 629         }
 630         RFALSE(src_bi->bi_bh == 0 || dest_bi->bi_bh == 0,
 631                "vs-10260: mode==%d, source (%p) or dest (%p) buffer is initialized incorrectly",
 632                shift_mode, src_bi->bi_bh, dest_bi->bi_bh);
 633 }
 634
 635 /* copy mov_num items and mov_bytes of the (mov_num-1)th item to
 636    neighbor. Delete them from source */
 637 int leaf_move_items(int shift_mode, struct tree_balance *tb, int mov_num,
 638                     int mov_bytes, struct buffer_head *Snew)
 639 {
 640         int ret_value;
 641         struct buffer_info dest_bi, src_bi;
 642         int first_last;
 643
 644         leaf_define_dest_src_infos(shift_mode, tb, &dest_bi, &src_bi,
 645                                    &first_last, Snew);
 646
 647         ret_value =
 648             leaf_copy_items(&dest_bi, src_bi.bi_bh, first_last, mov_num,
 649                             mov_bytes);
 650
 651         leaf_delete_items(&src_bi, first_last,
 652                           (first_last ==
 653                            FIRST_TO_LAST) ? 0 : (B_NR_ITEMS(src_bi.bi_bh) -
 654                                                  mov_num), mov_num, mov_bytes);
 655
 656         return ret_value;
 657 }
 658
 659 /* Shift shift_num items (and shift_bytes of last shifted item if shift_bytes != -1)
 660    from S[0] to L[0] and replace the delimiting key */
 661 int leaf_shift_left(struct tree_balance *tb, int shift_num, int shift_bytes)
 662 {
 663         struct buffer_head *S0 = PATH_PLAST_BUFFER(tb->tb_path);
 664         int i;
 665
 666         /* move shift_num (and shift_bytes bytes) items from S[0] to left neighbor L[0] */
 667         i = leaf_move_items(LEAF_FROM_S_TO_L, tb, shift_num, shift_bytes, NULL);
 668
 669         if (shift_num) {
 670                 if (B_NR_ITEMS(S0) == 0) {      /* number of items in S[0] == 0 */
 671
 672                         RFALSE(shift_bytes != -1,
 673                                "vs-10270: S0 is empty now, but shift_bytes != -1 (%d)",
 674                                shift_bytes);
 675 #ifdef CONFIG_REISERFS_CHECK
 676                         if (tb->tb_mode == M_PASTE || tb->tb_mode == M_INSERT) {
 677                                 print_cur_tb("vs-10275");
 678                                 reiserfs_panic(tb->tb_sb,
 679                                                "vs-10275: leaf_shift_left: balance condition corrupted (%c)",
 680                                                tb->tb_mode);
 681                         }
 682 #endif
 683
 684                         if (PATH_H_POSITION(tb->tb_path, 1) == 0)
 685                                 replace_key(tb, tb->CFL[0], tb->lkey[0],
 686                                             PATH_H_PPARENT(tb->tb_path, 0), 0);
 687
 688                 } else {
 689                         /* replace lkey in CFL[0] by 0-th key from S[0]; */
 690                         replace_key(tb, tb->CFL[0], tb->lkey[0], S0, 0);
 691
 692                         RFALSE((shift_bytes != -1 &&
 693                                 !(is_direntry_le_ih(B_N_PITEM_HEAD(S0, 0))
 694                                   && !I_ENTRY_COUNT(B_N_PITEM_HEAD(S0, 0)))) &&
 695                                (!op_is_left_mergeable
 696                                 (B_N_PKEY(S0, 0), S0->b_size)),
 697                                "vs-10280: item must be mergeable");
 698                 }
 699         }
 700
 701         return i;
 702 }
 703
 704 /* CLEANING STOPPED HERE */
 705
 706 /* Shift shift_num (shift_bytes) items from S[0] to the right neighbor, and replace the delimiting key */
 707 int leaf_shift_right(struct tree_balance *tb, int shift_num, int shift_bytes)
 708 {
 709         //  struct buffer_head * S0 = PATH_PLAST_BUFFER (tb->tb_path);
 710         int ret_value;
 711
 712         /* move shift_num (and shift_bytes) items from S[0] to right neighbor R[0] */
 713         ret_value =
 714             leaf_move_items(LEAF_FROM_S_TO_R, tb, shift_num, shift_bytes, NULL);
 715
 716         /* replace rkey in CFR[0] by the 0-th key from R[0] */
 717         if (shift_num) {
 718                 replace_key(tb, tb->CFR[0], tb->rkey[0], tb->R[0], 0);
 719
 720         }
 721
 722         return ret_value;
 723 }
 724
 725 static void leaf_delete_items_entirely(struct buffer_info *bi,
 726                                        int first, int del_num);
 727 /*  If del_bytes == -1, starting from position 'first' delete del_num items in whole in buffer CUR.
 728     If not.
 729     If last_first == 0. Starting from position 'first' delete del_num-1 items in whole. Delete part of body of
 730     the first item. Part defined by del_bytes. Don't delete first item header
 731     If last_first == 1. Starting from position 'first+1' delete del_num-1 items in whole. Delete part of body of
 732     the last item . Part defined by del_bytes. Don't delete last item header.
 733 */
 734 void leaf_delete_items(struct buffer_info *cur_bi, int last_first,
 735                        int first, int del_num, int del_bytes)
 736 {
 737         struct buffer_head *bh;
 738         int item_amount = B_NR_ITEMS(bh = cur_bi->bi_bh);
 739
 740         RFALSE(!bh, "10155: bh is not defined");
 741         RFALSE(del_num < 0, "10160: del_num can not be < 0. del_num==%d",
 742                del_num);
 743         RFALSE(first < 0
 744                || first + del_num > item_amount,
 745                "10165: invalid number of first item to be deleted (%d) or "
 746                "no so much items (%d) to delete (only %d)", first,
 747                first + del_num, item_amount);
 748
 749         if (del_num == 0)
 750                 return;
 751
 752         if (first == 0 && del_num == item_amount && del_bytes == -1) {
 753                 make_empty_node(cur_bi);
 754                 do_balance_mark_leaf_dirty(cur_bi->tb, bh, 0);
 755                 return;
 756         }
 757
 758         if (del_bytes == -1)
 759                 /* delete del_num items beginning from item in position first */
 760                 leaf_delete_items_entirely(cur_bi, first, del_num);
 761         else {
 762                 if (last_first == FIRST_TO_LAST) {
 763                         /* delete del_num-1 items beginning from item in position first  */
 764                         leaf_delete_items_entirely(cur_bi, first, del_num - 1);
 765
 766                         /* delete the part of the first item of the bh
 767                            do not delete item header
 768                          */
 769                         leaf_cut_from_buffer(cur_bi, 0, 0, del_bytes);
 770                 } else {
 771                         struct item_head *ih;
 772                         int len;
 773
 774                         /* delete del_num-1 items beginning from item in position first+1  */
 775                         leaf_delete_items_entirely(cur_bi, first + 1,
 776                                                    del_num - 1);
 777
 778                         if (is_direntry_le_ih
 779                             (ih = B_N_PITEM_HEAD(bh, B_NR_ITEMS(bh) - 1)))
 780                                 /* the last item is directory  */
 781                                 /* len = numbers of directory entries in this item */
 782                                 len = ih_entry_count(ih);
 783                         else
 784                                 /* len = body len of item */
 785                                 len = ih_item_len(ih);
 786
 787                         /* delete the part of the last item of the bh
 788                            do not delete item header
 789                          */
 790                         leaf_cut_from_buffer(cur_bi, B_NR_ITEMS(bh) - 1,
 791                                              len - del_bytes, del_bytes);
 792                 }
 793         }
 794 }
 795
 796 /* insert item into the leaf node in position before */
 797 void leaf_insert_into_buf(struct buffer_info *bi, int before,
 798                           struct item_head *inserted_item_ih,
 799                           const char *inserted_item_body, int zeros_number)
 800 {
 801         struct buffer_head *bh = bi->bi_bh;
 802         int nr, free_space;
 803         struct block_head *blkh;
 804         struct item_head *ih;
 805         int i;
 806         int last_loc, unmoved_loc;
 807         char *to;
 808
 809         blkh = B_BLK_HEAD(bh);
 810         nr = blkh_nr_item(blkh);
 811         free_space = blkh_free_space(blkh);
 812
 813         /* check free space */
 814         RFALSE(free_space < ih_item_len(inserted_item_ih) + IH_SIZE,
 815                "vs-10170: not enough free space in block %z, new item %h",
 816                bh, inserted_item_ih);
 817         RFALSE(zeros_number > ih_item_len(inserted_item_ih),
 818                "vs-10172: zero number == %d, item length == %d",
 819                zeros_number, ih_item_len(inserted_item_ih));
 820
 821         /* get item new item must be inserted before */
 822         ih = B_N_PITEM_HEAD(bh, before);
 823
 824         /* prepare space for the body of new item */
 825         last_loc = nr ? ih_location(&(ih[nr - before - 1])) : bh->b_size;
 826         unmoved_loc = before ? ih_location(ih - 1) : bh->b_size;
 827
 828         memmove(bh->b_data + last_loc - ih_item_len(inserted_item_ih),
 829                 bh->b_data + last_loc, unmoved_loc - last_loc);
 830
 831         to = bh->b_data + unmoved_loc - ih_item_len(inserted_item_ih);
 832         memset(to, 0, zeros_number);
 833         to += zeros_number;
 834
 835         /* copy body to prepared space */
 836         if (inserted_item_body)
 837                 memmove(to, inserted_item_body,
 838                         ih_item_len(inserted_item_ih) - zeros_number);
 839         else
 840                 memset(to, '\0', ih_item_len(inserted_item_ih) - zeros_number);
 841
 842         /* insert item header */
 843         memmove(ih + 1, ih, IH_SIZE * (nr - before));
 844         memmove(ih, inserted_item_ih, IH_SIZE);
 845
 846         /* change locations */
 847         for (i = before; i < nr + 1; i++) {
 848                 unmoved_loc -= ih_item_len(&(ih[i - before]));
 849                 put_ih_location(&(ih[i - before]), unmoved_loc);
 850         }
 851
 852         /* sizes, free space, item number */
 853         set_blkh_nr_item(blkh, blkh_nr_item(blkh) + 1);
 854         set_blkh_free_space(blkh,
 855                             free_space - (IH_SIZE +
 856                                           ih_item_len(inserted_item_ih)));
 857         do_balance_mark_leaf_dirty(bi->tb, bh, 1);
 858
 859         if (bi->bi_parent) {
 860                 struct disk_child *t_dc;
 861                 t_dc = B_N_CHILD(bi->bi_parent, bi->bi_position);
 862                 put_dc_size(t_dc,
 863                             dc_size(t_dc) + (IH_SIZE +
 864                                              ih_item_len(inserted_item_ih)));
 865                 do_balance_mark_internal_dirty(bi->tb, bi->bi_parent, 0);
 866         }
 867 }
 868
 869 /* paste paste_size bytes to affected_item_num-th item.
 870    When item is a directory, this only prepare space for new entries */
 871 void leaf_paste_in_buffer(struct buffer_info *bi, int affected_item_num,
 872                           int pos_in_item, int paste_size,
 873                           const char *body, int zeros_number)
 874 {
 875         struct buffer_head *bh = bi->bi_bh;
 876         int nr, free_space;
 877         struct block_head *blkh;
 878         struct item_head *ih;
 879         int i;
 880         int last_loc, unmoved_loc;
 881
 882         blkh = B_BLK_HEAD(bh);
 883         nr = blkh_nr_item(blkh);
 884         free_space = blkh_free_space(blkh);
 885
 886         /* check free space */
 887         RFALSE(free_space < paste_size,
 888                "vs-10175: not enough free space: needed %d, available %d",
 889                paste_size, free_space);
 890
 891 #ifdef CONFIG_REISERFS_CHECK
 892         if (zeros_number > paste_size) {
 893                 print_cur_tb("10177");
 894                 reiserfs_panic(NULL,
 895                                "vs-10177: leaf_paste_in_buffer: ero number == %d, paste_size == %d",
 896                                zeros_number, paste_size);
 897         }
 898 #endif                          /* CONFIG_REISERFS_CHECK */
 899
 900         /* item to be appended */
 901         ih = B_N_PITEM_HEAD(bh, affected_item_num);
 902
 903         last_loc = ih_location(&(ih[nr - affected_item_num - 1]));
 904         unmoved_loc = affected_item_num ? ih_location(ih - 1) : bh->b_size;
 905
 906         /* prepare space */
 907         memmove(bh->b_data + last_loc - paste_size, bh->b_data + last_loc,
 908                 unmoved_loc - last_loc);
 909
 910         /* change locations */
 911         for (i = affected_item_num; i < nr; i++)
 912                 put_ih_location(&(ih[i - affected_item_num]),
 913                                 ih_location(&(ih[i - affected_item_num])) -
 914                                 paste_size);
 915
 916         if (body) {
 917                 if (!is_direntry_le_ih(ih)) {
 918                         if (!pos_in_item) {
 919                                 /* shift data to right */
 920                                 memmove(bh->b_data + ih_location(ih) +
 921                                         paste_size,
 922                                         bh->b_data + ih_location(ih),
 923                                         ih_item_len(ih));
 924                                 /* paste data in the head of item */
 925                                 memset(bh->b_data + ih_location(ih), 0,
 926                                        zeros_number);
 927                                 memcpy(bh->b_data + ih_location(ih) +
 928                                        zeros_number, body,
 929                                        paste_size - zeros_number);
 930                         } else {
 931                                 memset(bh->b_data + unmoved_loc - paste_size, 0,
 932                                        zeros_number);
 933                                 memcpy(bh->b_data + unmoved_loc - paste_size +
 934                                        zeros_number, body,
 935                                        paste_size - zeros_number);
 936                         }
 937                 }
 938         } else
 939                 memset(bh->b_data + unmoved_loc - paste_size, '\0', paste_size);
 940
 941         put_ih_item_len(ih, ih_item_len(ih) + paste_size);
 942
 943         /* change free space */
 944         set_blkh_free_space(blkh, free_space - paste_size);
 945
 946         do_balance_mark_leaf_dirty(bi->tb, bh, 0);
 947
 948         if (bi->bi_parent) {
 949                 struct disk_child *t_dc =
 950                     B_N_CHILD(bi->bi_parent, bi->bi_position);
 951                 put_dc_size(t_dc, dc_size(t_dc) + paste_size);
 952                 do_balance_mark_internal_dirty(bi->tb, bi->bi_parent, 0);
 953         }
 954 }
 955
 956 /* cuts DEL_COUNT entries beginning from FROM-th entry. Directory item
 957    does not have free space, so it moves DEHs and remaining records as
 958    necessary. Return value is size of removed part of directory item
 959    in bytes. */
 960 static int leaf_cut_entries(struct buffer_head *bh,
 961                             struct item_head *ih, int from, int del_count)
 962 {
 963         char *item;
 964         struct reiserfs_de_head *deh;
 965         int prev_record_offset; /* offset of record, that is (from-1)th */
 966         char *prev_record;      /* */
 967         int cut_records_len;    /* length of all removed records */
 968         int i;
 969
 970         /* make sure, that item is directory and there are enough entries to
 971            remove */
 972         RFALSE(!is_direntry_le_ih(ih), "10180: item is not directory item");
 973         RFALSE(I_ENTRY_COUNT(ih) < from + del_count,
 974                "10185: item contains not enough entries: entry_cout = %d, from = %d, to delete = %d",
 975                I_ENTRY_COUNT(ih), from, del_count);
 976
 977         if (del_count == 0)
 978                 return 0;
 979
 980         /* first byte of item */
 981         item = bh->b_data + ih_location(ih);
 982
 983         /* entry head array */
 984         deh = B_I_DEH(bh, ih);
 985
 986         /* first byte of remaining entries, those are BEFORE cut entries
 987            (prev_record) and length of all removed records (cut_records_len) */
 988         prev_record_offset =
 989             (from ? deh_location(&(deh[from - 1])) : ih_item_len(ih));
 990         cut_records_len = prev_record_offset /*from_record */  -
 991             deh_location(&(deh[from + del_count - 1]));
 992         prev_record = item + prev_record_offset;
 993
 994         /* adjust locations of remaining entries */
 995         for (i = I_ENTRY_COUNT(ih) - 1; i > from + del_count - 1; i--)
 996                 put_deh_location(&(deh[i]),
 997                                  deh_location(&deh[i]) -
 998                                  (DEH_SIZE * del_count));
 999
1000         for (i = 0; i < from; i++)
1001                 put_deh_location(&(deh[i]),
1002                                  deh_location(&deh[i]) - (DEH_SIZE * del_count +
1003                                                           cut_records_len));
1004
1005         put_ih_entry_count(ih, ih_entry_count(ih) - del_count);
1006
1007         /* shift entry head array and entries those are AFTER removed entries */
1008         memmove((char *)(deh + from),
1009                 deh + from + del_count,
1010                 prev_record - cut_records_len - (char *)(deh + from +
1011                                                          del_count));
1012
1013         /* shift records, those are BEFORE removed entries */
1014         memmove(prev_record - cut_records_len - DEH_SIZE * del_count,
1015                 prev_record, item + ih_item_len(ih) - prev_record);
1016
1017         return DEH_SIZE * del_count + cut_records_len;
1018 }
1019
1020 /*  when cut item is part of regular file
1021         pos_in_item - first byte that must be cut
1022         cut_size - number of bytes to be cut beginning from pos_in_item
1023
1024    when cut item is part of directory
1025         pos_in_item - number of first deleted entry
1026         cut_size - count of deleted entries
1027     */
1028 void leaf_cut_from_buffer(struct buffer_info *bi, int cut_item_num,
1029                           int pos_in_item, int cut_size)
1030 {
1031         int nr;
1032         struct buffer_head *bh = bi->bi_bh;
1033         struct block_head *blkh;
1034         struct item_head *ih;
1035         int last_loc, unmoved_loc;
1036         int i;
1037
1038         blkh = B_BLK_HEAD(bh);
1039         nr = blkh_nr_item(blkh);
1040
1041         /* item head of truncated item */
1042         ih = B_N_PITEM_HEAD(bh, cut_item_num);
1043
1044         if (is_direntry_le_ih(ih)) {
1045                 /* first cut entry () */
1046                 cut_size = leaf_cut_entries(bh, ih, pos_in_item, cut_size);
1047                 if (pos_in_item == 0) {
1048                         /* change key */
1049                         RFALSE(cut_item_num,
1050                                "when 0-th enrty of item is cut, that item must be first in the node, not %d-th",
1051                                cut_item_num);
1052                         /* change item key by key of first entry in the item */
1053                         set_le_ih_k_offset(ih, deh_offset(B_I_DEH(bh, ih)));
1054                         /*memcpy (&ih->ih_key.k_offset, &(B_I_DEH (bh, ih)->deh_offset), SHORT_KEY_SIZE); */
1055                 }
1056         } else {
1057                 /* item is direct or indirect */
1058                 RFALSE(is_statdata_le_ih(ih), "10195: item is stat data");
1059                 RFALSE(pos_in_item && pos_in_item + cut_size != ih_item_len(ih),
1060                        "10200: invalid offset (%lu) or trunc_size (%lu) or ih_item_len (%lu)",
1061                        (long unsigned)pos_in_item, (long unsigned)cut_size,
1062                        (long unsigned)ih_item_len(ih));
1063
1064                 /* shift item body to left if cut is from the head of item */
1065                 if (pos_in_item == 0) {
1066                         memmove(bh->b_data + ih_location(ih),
1067                                 bh->b_data + ih_location(ih) + cut_size,
1068                                 ih_item_len(ih) - cut_size);
1069
1070                         /* change key of item */
1071                         if (is_direct_le_ih(ih))
1072                                 set_le_ih_k_offset(ih,
1073                                                    le_ih_k_offset(ih) +
1074                                                    cut_size);
1075                         else {
1076                                 set_le_ih_k_offset(ih,
1077                                                    le_ih_k_offset(ih) +
1078                                                    (cut_size / UNFM_P_SIZE) *
1079                                                    bh->b_size);
1080                                 RFALSE(ih_item_len(ih) == cut_size
1081                                        && get_ih_free_space(ih),
1082                                        "10205: invalid ih_free_space (%h)", ih);
1083                         }
1084                 }
1085         }
1086
1087         /* location of the last item */
1088         last_loc = ih_location(&(ih[nr - cut_item_num - 1]));
1089
1090         /* location of the item, which is remaining at the same place */
1091         unmoved_loc = cut_item_num ? ih_location(ih - 1) : bh->b_size;
1092
1093         /* shift */
1094         memmove(bh->b_data + last_loc + cut_size, bh->b_data + last_loc,
1095                 unmoved_loc - last_loc - cut_size);
1096
1097         /* change item length */
1098         put_ih_item_len(ih, ih_item_len(ih) - cut_size);
1099
1100         if (is_indirect_le_ih(ih)) {
1101                 if (pos_in_item)
1102                         set_ih_free_space(ih, 0);
1103         }
1104
1105         /* change locations */
1106         for (i = cut_item_num; i < nr; i++)
1107                 put_ih_location(&(ih[i - cut_item_num]),
1108                                 ih_location(&ih[i - cut_item_num]) + cut_size);
1109
1110         /* size, free space */
1111         set_blkh_free_space(blkh, blkh_free_space(blkh) + cut_size);
1112
1113         do_balance_mark_leaf_dirty(bi->tb, bh, 0);
1114
1115         if (bi->bi_parent) {
1116                 struct disk_child *t_dc;
1117                 t_dc = B_N_CHILD(bi->bi_parent, bi->bi_position);
1118                 put_dc_size(t_dc, dc_size(t_dc) - cut_size);
1119                 do_balance_mark_internal_dirty(bi->tb, bi->bi_parent, 0);
1120         }
1121 }
1122
1123 /* delete del_num items from buffer starting from the first'th item */
1124 static void leaf_delete_items_entirely(struct buffer_info *bi,
1125                                        int first, int del_num)
1126 {
1127         struct buffer_head *bh = bi->bi_bh;
1128         int nr;
1129         int i, j;
1130         int last_loc, last_removed_loc;
1131         struct block_head *blkh;
1132         struct item_head *ih;
1133
1134         RFALSE(bh == NULL, "10210: buffer is 0");
1135         RFALSE(del_num < 0, "10215: del_num less than 0 (%d)", del_num);
1136
1137         if (del_num == 0)
1138                 return;
1139
1140         blkh = B_BLK_HEAD(bh);
1141         nr = blkh_nr_item(blkh);
1142
1143         RFALSE(first < 0 || first + del_num > nr,
1144                "10220: first=%d, number=%d, there is %d items", first, del_num,
1145                nr);
1146
1147         if (first == 0 && del_num == nr) {
1148                 /* this does not work */
1149                 make_empty_node(bi);
1150
1151                 do_balance_mark_leaf_dirty(bi->tb, bh, 0);
1152                 return;
1153         }
1154
1155         ih = B_N_PITEM_HEAD(bh, first);
1156
1157         /* location of unmovable item */
1158         j = (first == 0) ? bh->b_size : ih_location(ih - 1);
1159
1160         /* delete items */
1161         last_loc = ih_location(&(ih[nr - 1 - first]));
1162         last_removed_loc = ih_location(&(ih[del_num - 1]));
1163
1164         memmove(bh->b_data + last_loc + j - last_removed_loc,
1165                 bh->b_data + last_loc, last_removed_loc - last_loc);
1166
1167         /* delete item headers */
1168         memmove(ih, ih + del_num, (nr - first - del_num) * IH_SIZE);
1169
1170         /* change item location */
1171         for (i = first; i < nr - del_num; i++)
1172                 put_ih_location(&(ih[i - first]),
1173                                 ih_location(&(ih[i - first])) + (j -
1174                                                                  last_removed_loc));
1175
1176         /* sizes, item number */
1177         set_blkh_nr_item(blkh, blkh_nr_item(blkh) - del_num);
1178         set_blkh_free_space(blkh,
1179                             blkh_free_space(blkh) + (j - last_removed_loc +
1180                                                      IH_SIZE * del_num));
1181
1182         do_balance_mark_leaf_dirty(bi->tb, bh, 0);
1183
1184         if (bi->bi_parent) {
1185                 struct disk_child *t_dc =
1186                     B_N_CHILD(bi->bi_parent, bi->bi_position);
1187                 put_dc_size(t_dc,
1188                             dc_size(t_dc) - (j - last_removed_loc +
1189                                              IH_SIZE * del_num));
1190                 do_balance_mark_internal_dirty(bi->tb, bi->bi_parent, 0);
1191         }
1192 }
1193
1194 /* paste new_entry_count entries (new_dehs, records) into position before to item_num-th item */
1195 void leaf_paste_entries(struct buffer_head *bh,
1196                         int item_num,
1197                         int before,
1198                         int new_entry_count,
1199                         struct reiserfs_de_head *new_dehs,
1200                         const char *records, int paste_size)
1201 {
1202         struct item_head *ih;
1203         char *item;
1204         struct reiserfs_de_head *deh;
1205         char *insert_point;
1206         int i, old_entry_num;
1207
1208         if (new_entry_count == 0)
1209                 return;
1210
1211         ih = B_N_PITEM_HEAD(bh, item_num);
1212
1213         /* make sure, that item is directory, and there are enough records in it */
1214         RFALSE(!is_direntry_le_ih(ih), "10225: item is not directory item");
1215         RFALSE(I_ENTRY_COUNT(ih) < before,
1216                "10230: there are no entry we paste entries before. entry_count = %d, before = %d",
1217                I_ENTRY_COUNT(ih), before);
1218
1219         /* first byte of dest item */
1220         item = bh->b_data + ih_location(ih);
1221
1222         /* entry head array */
1223         deh = B_I_DEH(bh, ih);
1224
1225         /* new records will be pasted at this point */
1226         insert_point =
1227             item +
1228             (before ? deh_location(&(deh[before - 1]))
1229              : (ih_item_len(ih) - paste_size));
1230
1231         /* adjust locations of records that will be AFTER new records */
1232         for (i = I_ENTRY_COUNT(ih) - 1; i >= before; i--)
1233                 put_deh_location(&(deh[i]),
1234                                  deh_location(&(deh[i])) +
1235                                  (DEH_SIZE * new_entry_count));
1236
1237         /* adjust locations of records that will be BEFORE new records */
1238         for (i = 0; i < before; i++)
1239                 put_deh_location(&(deh[i]),
1240                                  deh_location(&(deh[i])) + paste_size);
1241
1242         old_entry_num = I_ENTRY_COUNT(ih);
1243         put_ih_entry_count(ih, ih_entry_count(ih) + new_entry_count);
1244
1245         /* prepare space for pasted records */
1246         memmove(insert_point + paste_size, insert_point,
1247                 item + (ih_item_len(ih) - paste_size) - insert_point);
1248
1249         /* copy new records */
1250         memcpy(insert_point + DEH_SIZE * new_entry_count, records,
1251                paste_size - DEH_SIZE * new_entry_count);
1252
1253         /* prepare space for new entry heads */
1254         deh += before;
1255         memmove((char *)(deh + new_entry_count), deh,
1256                 insert_point - (char *)deh);
1257
1258         /* copy new entry heads */
1259         deh = (struct reiserfs_de_head *)((char *)deh);
1260         memcpy(deh, new_dehs, DEH_SIZE * new_entry_count);
1261
1262         /* set locations of new records */
1263         for (i = 0; i < new_entry_count; i++) {
1264                 put_deh_location(&(deh[i]),
1265                                  deh_location(&(deh[i])) +
1266                                  (-deh_location
1267                                   (&(new_dehs[new_entry_count - 1])) +
1268                                   insert_point + DEH_SIZE * new_entry_count -
1269                                   item));
1270         }
1271
1272         /* change item key if necessary (when we paste before 0-th entry */
1273         if (!before) {
1274                 set_le_ih_k_offset(ih, deh_offset(new_dehs));
1275 /*      memcpy (&ih->ih_key.k_offset,
1276                        &new_dehs->deh_offset, SHORT_KEY_SIZE);*/
1277         }
1278 #ifdef CONFIG_REISERFS_CHECK
1279         {
1280                 int prev, next;
1281                 /* check record locations */
1282                 deh = B_I_DEH(bh, ih);
1283                 for (i = 0; i < I_ENTRY_COUNT(ih); i++) {
1284                         next =
1285                             (i <
1286                              I_ENTRY_COUNT(ih) -
1287                              1) ? deh_location(&(deh[i + 1])) : 0;
1288                         prev = (i != 0) ? deh_location(&(deh[i - 1])) : 0;
1289
1290                         if (prev && prev <= deh_location(&(deh[i])))
1291                                 reiserfs_warning(NULL,
1292                                                  "vs-10240: leaf_paste_entries: directory item (%h) corrupted (prev %a, cur(%d) %a)",
1293                                                  ih, deh + i - 1, i, deh + i);
1294                         if (next && next >= deh_location(&(deh[i])))
1295                                 reiserfs_warning(NULL,
1296                                                  "vs-10250: leaf_paste_entries: directory item (%h) corrupted (cur(%d) %a, next %a)",
1297                                                  ih, i, deh + i, deh + i + 1);
1298                 }
1299         }
1300 #endif
1301
1302 }