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->bi_bh, 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(NULL,
 172                                                        "vs-10020: leaf_copy_boundary_item: "
 173                                                        "last unformatted node must be filled entirely (%h)",
 174                                                        ih);
 175                 }
 176 #endif
 177
 178                 /* merge first item (or its part) of src buffer with the last
 179                    item of dest buffer. Both are of the same file */
 180                 leaf_paste_in_buffer(dest_bi,
 181                                      dest_nr_item - 1, ih_item_len(dih),
 182                                      bytes_or_entries, B_I_PITEM(src, ih), 0);
 183
 184                 if (is_indirect_le_ih(dih)) {
 185                         RFALSE(get_ih_free_space(dih),
 186                                "vs-10030: merge to left: last unformatted node of non-last indirect item %h must have zerto free space",
 187                                ih);
 188                         if (bytes_or_entries == ih_item_len(ih))
 189                                 set_ih_free_space(dih, get_ih_free_space(ih));
 190                 }
 191
 192                 return 1;
 193         }
 194
 195         /* copy boundary item to right (last_first == LAST_TO_FIRST) */
 196
 197         /* ( DEST is empty or last item of SOURCE and first item of DEST
 198            are the items of different object or of different types )
 199          */
 200         src_nr_item = B_NR_ITEMS(src);
 201         ih = B_N_PITEM_HEAD(src, src_nr_item - 1);
 202         dih = B_N_PITEM_HEAD(dest, 0);
 203
 204         if (!dest_nr_item || !op_is_left_mergeable(&(dih->ih_key), src->b_size))
 205                 return 0;
 206
 207         if (is_direntry_le_ih(ih)) {
 208                 if (bytes_or_entries == -1)
 209                         /* bytes_or_entries = entries number in last item body of SOURCE */
 210                         bytes_or_entries = ih_entry_count(ih);
 211
 212                 leaf_copy_dir_entries(dest_bi, src, LAST_TO_FIRST,
 213                                       src_nr_item - 1,
 214                                       ih_entry_count(ih) - bytes_or_entries,
 215                                       bytes_or_entries);
 216                 return 1;
 217         }
 218
 219         /* copy part of the body of the last item of SOURCE to the begin of the body of the first item of the DEST;
 220            part defined by 'bytes_or_entries'; if byte_or_entriess == -1 copy whole body; change first item key of the DEST;
 221            don't create new item header
 222          */
 223
 224         RFALSE(is_indirect_le_ih(ih) && get_ih_free_space(ih),
 225                "vs-10040: merge to right: last unformatted node of non-last indirect item must be filled entirely (%h)",
 226                ih);
 227
 228         if (bytes_or_entries == -1) {
 229                 /* bytes_or_entries = length of last item body of SOURCE */
 230                 bytes_or_entries = ih_item_len(ih);
 231
 232                 RFALSE(le_ih_k_offset(dih) !=
 233                        le_ih_k_offset(ih) + op_bytes_number(ih, src->b_size),
 234                        "vs-10050: items %h and %h do not match", ih, dih);
 235
 236                 /* change first item key of the DEST */
 237                 set_le_ih_k_offset(dih, le_ih_k_offset(ih));
 238
 239                 /* item becomes non-mergeable */
 240                 /* or mergeable if left item was */
 241                 set_le_ih_k_type(dih, le_ih_k_type(ih));
 242         } else {
 243                 /* merge to right only part of item */
 244                 RFALSE(ih_item_len(ih) <= bytes_or_entries,
 245                        "vs-10060: no so much bytes %lu (needed %lu)",
 246                        (unsigned long)ih_item_len(ih),
 247                        (unsigned long)bytes_or_entries);
 248
 249                 /* change first item key of the DEST */
 250                 if (is_direct_le_ih(dih)) {
 251                         RFALSE(le_ih_k_offset(dih) <=
 252                                (unsigned long)bytes_or_entries,
 253                                "vs-10070: dih %h, bytes_or_entries(%d)", dih,
 254                                bytes_or_entries);
 255                         set_le_ih_k_offset(dih,
 256                                            le_ih_k_offset(dih) -
 257                                            bytes_or_entries);
 258                 } else {
 259                         RFALSE(le_ih_k_offset(dih) <=
 260                                (bytes_or_entries / UNFM_P_SIZE) * dest->b_size,
 261                                "vs-10080: dih %h, bytes_or_entries(%d)",
 262                                dih,
 263                                (bytes_or_entries / UNFM_P_SIZE) * dest->b_size);
 264                         set_le_ih_k_offset(dih,
 265                                            le_ih_k_offset(dih) -
 266                                            ((bytes_or_entries / UNFM_P_SIZE) *
 267                                             dest->b_size));
 268                 }
 269         }
 270
 271         leaf_paste_in_buffer(dest_bi, 0, 0, bytes_or_entries,
 272                              B_I_PITEM(src,
 273                                        ih) + ih_item_len(ih) - bytes_or_entries,
 274                              0);
 275         return 1;
 276 }
 277
 278 /* copy cpy_mun items from buffer src to buffer dest
 279  * last_first == FIRST_TO_LAST means, that we copy cpy_num  items beginning from first-th item in src to tail of dest
 280  * last_first == LAST_TO_FIRST means, that we copy cpy_num  items beginning from first-th item in src to head of dest
 281  */
 282 static void leaf_copy_items_entirely(struct buffer_info *dest_bi,
 283                                      struct buffer_head *src, int last_first,
 284                                      int first, int cpy_num)
 285 {
 286         struct buffer_head *dest;
 287         int nr, free_space;
 288         int dest_before;
 289         int last_loc, last_inserted_loc, location;
 290         int i, j;
 291         struct block_head *blkh;
 292         struct item_head *ih;
 293
 294         RFALSE(last_first != LAST_TO_FIRST && last_first != FIRST_TO_LAST,
 295                "vs-10090: bad last_first parameter %d", last_first);
 296         RFALSE(B_NR_ITEMS(src) - first < cpy_num,
 297                "vs-10100: too few items in source %d, required %d from %d",
 298                B_NR_ITEMS(src), cpy_num, first);
 299         RFALSE(cpy_num < 0, "vs-10110: can not copy negative amount of items");
 300         RFALSE(!dest_bi, "vs-10120: can not copy negative amount of items");
 301
 302         dest = dest_bi->bi_bh;
 303
 304         RFALSE(!dest, "vs-10130: can not copy negative amount of items");
 305
 306         if (cpy_num == 0)
 307                 return;
 308
 309         blkh = B_BLK_HEAD(dest);
 310         nr = blkh_nr_item(blkh);
 311         free_space = blkh_free_space(blkh);
 312
 313         /* we will insert items before 0-th or nr-th item in dest buffer. It depends of last_first parameter */
 314         dest_before = (last_first == LAST_TO_FIRST) ? 0 : nr;
 315
 316         /* location of head of first new item */
 317         ih = B_N_PITEM_HEAD(dest, dest_before);
 318
 319         RFALSE(blkh_free_space(blkh) < cpy_num * IH_SIZE,
 320                "vs-10140: not enough free space for headers %d (needed %d)",
 321                B_FREE_SPACE(dest), cpy_num * IH_SIZE);
 322
 323         /* prepare space for headers */
 324         memmove(ih + cpy_num, ih, (nr - dest_before) * IH_SIZE);
 325
 326         /* copy item headers */
 327         memcpy(ih, B_N_PITEM_HEAD(src, first), cpy_num * IH_SIZE);
 328
 329         free_space -= (IH_SIZE * cpy_num);
 330         set_blkh_free_space(blkh, free_space);
 331
 332         /* location of unmovable item */
 333         j = location = (dest_before == 0) ? dest->b_size : ih_location(ih - 1);
 334         for (i = dest_before; i < nr + cpy_num; i++) {
 335                 location -= ih_item_len(ih + i - dest_before);
 336                 put_ih_location(ih + i - dest_before, location);
 337         }
 338
 339         /* prepare space for items */
 340         last_loc = ih_location(&(ih[nr + cpy_num - 1 - dest_before]));
 341         last_inserted_loc = ih_location(&(ih[cpy_num - 1]));
 342
 343         /* check free space */
 344         RFALSE(free_space < j - last_inserted_loc,
 345                "vs-10150: not enough free space for items %d (needed %d)",
 346                free_space, j - last_inserted_loc);
 347
 348         memmove(dest->b_data + last_loc,
 349                 dest->b_data + last_loc + j - last_inserted_loc,
 350                 last_inserted_loc - last_loc);
 351
 352         /* copy items */
 353         memcpy(dest->b_data + last_inserted_loc,
 354                B_N_PITEM(src, (first + cpy_num - 1)), j - last_inserted_loc);
 355
 356         /* sizes, item number */
 357         set_blkh_nr_item(blkh, nr + cpy_num);
 358         set_blkh_free_space(blkh, free_space - (j - last_inserted_loc));
 359
 360         do_balance_mark_leaf_dirty(dest_bi->tb, dest, 0);
 361
 362         if (dest_bi->bi_parent) {
 363                 struct disk_child *t_dc;
 364                 t_dc = B_N_CHILD(dest_bi->bi_parent, dest_bi->bi_position);
 365                 RFALSE(dc_block_number(t_dc) != dest->b_blocknr,
 366                        "vs-10160: block number in bh does not match to field in disk_child structure %lu and %lu",
 367                        (long unsigned)dest->b_blocknr,
 368                        (long unsigned)dc_block_number(t_dc));
 369                 put_dc_size(t_dc,
 370                             dc_size(t_dc) + (j - last_inserted_loc +
 371                                              IH_SIZE * cpy_num));
 372
 373                 do_balance_mark_internal_dirty(dest_bi->tb, dest_bi->bi_parent,
 374                                                0);
 375         }
 376 }
 377
 378 /* This function splits the (liquid) item into two items (useful when
 379    shifting part of an item into another node.) */
 380 static void leaf_item_bottle(struct buffer_info *dest_bi,
 381                              struct buffer_head *src, int last_first,
 382                              int item_num, int cpy_bytes)
 383 {
 384         struct buffer_head *dest = dest_bi->bi_bh;
 385         struct item_head *ih;
 386
 387         RFALSE(cpy_bytes == -1,
 388                "vs-10170: bytes == - 1 means: do not split item");
 389
 390         if (last_first == FIRST_TO_LAST) {
 391                 /* if ( if item in position item_num in buffer SOURCE is directory item ) */
 392                 if (is_direntry_le_ih(ih = B_N_PITEM_HEAD(src, item_num)))
 393                         leaf_copy_dir_entries(dest_bi, src, FIRST_TO_LAST,
 394                                               item_num, 0, cpy_bytes);
 395                 else {
 396                         struct item_head n_ih;
 397
 398                         /* copy part of the body of the item number 'item_num' of SOURCE to the end of the DEST
 399                            part defined by 'cpy_bytes'; create new item header; change old item_header (????);
 400                            n_ih = new item_header;
 401                          */
 402                         memcpy(&n_ih, ih, IH_SIZE);
 403                         put_ih_item_len(&n_ih, cpy_bytes);
 404                         if (is_indirect_le_ih(ih)) {
 405                                 RFALSE(cpy_bytes == ih_item_len(ih)
 406                                        && get_ih_free_space(ih),
 407                                        "vs-10180: when whole indirect item is bottle to left neighbor, it must have free_space==0 (not %lu)",
 408                                        (long unsigned)get_ih_free_space(ih));
 409                                 set_ih_free_space(&n_ih, 0);
 410                         }
 411
 412                         RFALSE(op_is_left_mergeable(&(ih->ih_key), src->b_size),
 413                                "vs-10190: bad mergeability of item %h", ih);
 414                         n_ih.ih_version = ih->ih_version;       /* JDM Endian safe, both le */
 415                         leaf_insert_into_buf(dest_bi, B_NR_ITEMS(dest), &n_ih,
 416                                              B_N_PITEM(src, item_num), 0);
 417                 }
 418         } else {
 419                 /*  if ( if item in position item_num in buffer SOURCE is directory item ) */
 420                 if (is_direntry_le_ih(ih = B_N_PITEM_HEAD(src, item_num)))
 421                         leaf_copy_dir_entries(dest_bi, src, LAST_TO_FIRST,
 422                                               item_num,
 423                                               I_ENTRY_COUNT(ih) - cpy_bytes,
 424                                               cpy_bytes);
 425                 else {
 426                         struct item_head n_ih;
 427
 428                         /* copy part of the body of the item number 'item_num' of SOURCE to the begin of the DEST
 429                            part defined by 'cpy_bytes'; create new item header;
 430                            n_ih = new item_header;
 431                          */
 432                         memcpy(&n_ih, ih, SHORT_KEY_SIZE);
 433
 434                         n_ih.ih_version = ih->ih_version;       /* JDM Endian safe, both le */
 435
 436                         if (is_direct_le_ih(ih)) {
 437                                 set_le_ih_k_offset(&n_ih,
 438                                                    le_ih_k_offset(ih) +
 439                                                    ih_item_len(ih) - cpy_bytes);
 440                                 set_le_ih_k_type(&n_ih, TYPE_DIRECT);
 441                                 set_ih_free_space(&n_ih, MAX_US_INT);
 442                         } else {
 443                                 /* indirect item */
 444                                 RFALSE(!cpy_bytes && get_ih_free_space(ih),
 445                                        "vs-10200: ih->ih_free_space must be 0 when indirect item will be appended");
 446                                 set_le_ih_k_offset(&n_ih,
 447                                                    le_ih_k_offset(ih) +
 448                                                    (ih_item_len(ih) -
 449                                                     cpy_bytes) / UNFM_P_SIZE *
 450                                                    dest->b_size);
 451                                 set_le_ih_k_type(&n_ih, TYPE_INDIRECT);
 452                                 set_ih_free_space(&n_ih, get_ih_free_space(ih));
 453                         }
 454
 455                         /* set item length */
 456                         put_ih_item_len(&n_ih, cpy_bytes);
 457
 458                         n_ih.ih_version = ih->ih_version;       /* JDM Endian safe, both le */
 459
 460                         leaf_insert_into_buf(dest_bi, 0, &n_ih,
 461                                              B_N_PITEM(src,
 462                                                        item_num) +
 463                                              ih_item_len(ih) - cpy_bytes, 0);
 464                 }
 465         }
 466 }
 467
 468 /* If cpy_bytes equals minus one than copy cpy_num whole items from SOURCE to DEST.
 469    If cpy_bytes not equal to minus one than copy cpy_num-1 whole items from SOURCE to DEST.
 470    From last item copy cpy_num bytes for regular item and cpy_num directory entries for
 471    directory item. */
 472 static int leaf_copy_items(struct buffer_info *dest_bi, struct buffer_head *src,
 473                            int last_first, int cpy_num, int cpy_bytes)
 474 {
 475         struct buffer_head *dest;
 476         int pos, i, src_nr_item, bytes;
 477
 478         dest = dest_bi->bi_bh;
 479         RFALSE(!dest || !src, "vs-10210: !dest || !src");
 480         RFALSE(last_first != FIRST_TO_LAST && last_first != LAST_TO_FIRST,
 481                "vs-10220:last_first != FIRST_TO_LAST && last_first != LAST_TO_FIRST");
 482         RFALSE(B_NR_ITEMS(src) < cpy_num,
 483                "vs-10230: No enough items: %d, req. %d", B_NR_ITEMS(src),
 484                cpy_num);
 485         RFALSE(cpy_num < 0, "vs-10240: cpy_num < 0 (%d)", cpy_num);
 486
 487         if (cpy_num == 0)
 488                 return 0;
 489
 490         if (last_first == FIRST_TO_LAST) {
 491                 /* copy items to left */
 492                 pos = 0;
 493                 if (cpy_num == 1)
 494                         bytes = cpy_bytes;
 495                 else
 496                         bytes = -1;
 497
 498                 /* copy the first item or it part or nothing to the end of the DEST (i = leaf_copy_boundary_item(DEST,SOURCE,0,bytes)) */
 499                 i = leaf_copy_boundary_item(dest_bi, src, FIRST_TO_LAST, bytes);
 500                 cpy_num -= i;
 501                 if (cpy_num == 0)
 502                         return i;
 503                 pos += i;
 504                 if (cpy_bytes == -1)
 505                         /* copy first cpy_num items starting from position 'pos' of SOURCE to end of DEST */
 506                         leaf_copy_items_entirely(dest_bi, src, FIRST_TO_LAST,
 507                                                  pos, cpy_num);
 508                 else {
 509                         /* copy first cpy_num-1 items starting from position 'pos-1' of the SOURCE to the end of the DEST */
 510                         leaf_copy_items_entirely(dest_bi, src, FIRST_TO_LAST,
 511                                                  pos, cpy_num - 1);
 512
 513                         /* copy part of the item which number is cpy_num+pos-1 to the end of the DEST */
 514                         leaf_item_bottle(dest_bi, src, FIRST_TO_LAST,
 515                                          cpy_num + pos - 1, cpy_bytes);
 516                 }
 517         } else {
 518                 /* copy items to right */
 519                 src_nr_item = B_NR_ITEMS(src);
 520                 if (cpy_num == 1)
 521                         bytes = cpy_bytes;
 522                 else
 523                         bytes = -1;
 524
 525                 /* copy the last item or it part or nothing to the begin of the DEST (i = leaf_copy_boundary_item(DEST,SOURCE,1,bytes)); */
 526                 i = leaf_copy_boundary_item(dest_bi, src, LAST_TO_FIRST, bytes);
 527
 528                 cpy_num -= i;
 529                 if (cpy_num == 0)
 530                         return i;
 531
 532                 pos = src_nr_item - cpy_num - i;
 533                 if (cpy_bytes == -1) {
 534                         /* starting from position 'pos' copy last cpy_num items of SOURCE to begin of DEST */
 535                         leaf_copy_items_entirely(dest_bi, src, LAST_TO_FIRST,
 536                                                  pos, cpy_num);
 537                 } else {
 538                         /* copy last cpy_num-1 items starting from position 'pos+1' of the SOURCE to the begin of the DEST; */
 539                         leaf_copy_items_entirely(dest_bi, src, LAST_TO_FIRST,
 540                                                  pos + 1, cpy_num - 1);
 541
 542                         /* copy part of the item which number is pos to the begin of the DEST */
 543                         leaf_item_bottle(dest_bi, src, LAST_TO_FIRST, pos,
 544                                          cpy_bytes);
 545                 }
 546         }
 547         return i;
 548 }
 549
 550 /* there are types of coping: from S[0] to L[0], from S[0] to R[0],
 551    from R[0] to L[0]. for each of these we have to define parent and
 552    positions of destination and source buffers */
 553 static void leaf_define_dest_src_infos(int shift_mode, struct tree_balance *tb,
 554                                        struct buffer_info *dest_bi,
 555                                        struct buffer_info *src_bi,
 556                                        int *first_last,
 557                                        struct buffer_head *Snew)
 558 {
 559         memset(dest_bi, 0, sizeof(struct buffer_info));
 560         memset(src_bi, 0, sizeof(struct buffer_info));
 561
 562         /* define dest, src, dest parent, dest position */
 563         switch (shift_mode) {
 564         case LEAF_FROM_S_TO_L:  /* it is used in leaf_shift_left */
 565                 src_bi->tb = tb;
 566                 src_bi->bi_bh = PATH_PLAST_BUFFER(tb->tb_path);
 567                 src_bi->bi_parent = PATH_H_PPARENT(tb->tb_path, 0);
 568                 src_bi->bi_position = PATH_H_B_ITEM_ORDER(tb->tb_path, 0);      /* src->b_item_order */
 569                 dest_bi->tb = tb;
 570                 dest_bi->bi_bh = tb->L[0];
 571                 dest_bi->bi_parent = tb->FL[0];
 572                 dest_bi->bi_position = get_left_neighbor_position(tb, 0);
 573                 *first_last = FIRST_TO_LAST;
 574                 break;
 575
 576         case LEAF_FROM_S_TO_R:  /* it is used in leaf_shift_right */
 577                 src_bi->tb = tb;
 578                 src_bi->bi_bh = PATH_PLAST_BUFFER(tb->tb_path);
 579                 src_bi->bi_parent = PATH_H_PPARENT(tb->tb_path, 0);
 580                 src_bi->bi_position = PATH_H_B_ITEM_ORDER(tb->tb_path, 0);
 581                 dest_bi->tb = tb;
 582                 dest_bi->bi_bh = tb->R[0];
 583                 dest_bi->bi_parent = tb->FR[0];
 584                 dest_bi->bi_position = get_right_neighbor_position(tb, 0);
 585                 *first_last = LAST_TO_FIRST;
 586                 break;
 587
 588         case LEAF_FROM_R_TO_L:  /* it is used in balance_leaf_when_delete */
 589                 src_bi->tb = tb;
 590                 src_bi->bi_bh = tb->R[0];
 591                 src_bi->bi_parent = tb->FR[0];
 592                 src_bi->bi_position = get_right_neighbor_position(tb, 0);
 593                 dest_bi->tb = tb;
 594                 dest_bi->bi_bh = tb->L[0];
 595                 dest_bi->bi_parent = tb->FL[0];
 596                 dest_bi->bi_position = get_left_neighbor_position(tb, 0);
 597                 *first_last = FIRST_TO_LAST;
 598                 break;
 599
 600         case LEAF_FROM_L_TO_R:  /* it is used in balance_leaf_when_delete */
 601                 src_bi->tb = tb;
 602                 src_bi->bi_bh = tb->L[0];
 603                 src_bi->bi_parent = tb->FL[0];
 604                 src_bi->bi_position = get_left_neighbor_position(tb, 0);
 605                 dest_bi->tb = tb;
 606                 dest_bi->bi_bh = tb->R[0];
 607                 dest_bi->bi_parent = tb->FR[0];
 608                 dest_bi->bi_position = get_right_neighbor_position(tb, 0);
 609                 *first_last = LAST_TO_FIRST;
 610                 break;
 611
 612         case LEAF_FROM_S_TO_SNEW:
 613                 src_bi->tb = tb;
 614                 src_bi->bi_bh = PATH_PLAST_BUFFER(tb->tb_path);
 615                 src_bi->bi_parent = PATH_H_PPARENT(tb->tb_path, 0);
 616                 src_bi->bi_position = PATH_H_B_ITEM_ORDER(tb->tb_path, 0);
 617                 dest_bi->tb = tb;
 618                 dest_bi->bi_bh = Snew;
 619                 dest_bi->bi_parent = NULL;
 620                 dest_bi->bi_position = 0;
 621                 *first_last = LAST_TO_FIRST;
 622                 break;
 623
 624         default:
 625                 reiserfs_panic(NULL,
 626                                "vs-10250: leaf_define_dest_src_infos: shift type is unknown (%d)",
 627                                shift_mode);
 628         }
 629         RFALSE(src_bi->bi_bh == 0 || dest_bi->bi_bh == 0,
 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,
 678                                                "vs-10275: leaf_shift_left: balance condition corrupted (%c)",
 679                                                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                 print_cur_tb("10177");
 893                 reiserfs_panic(NULL,
 894                                "vs-10177: leaf_paste_in_buffer: ero number == %d, paste_size == %d",
 895                                zeros_number, paste_size);
 896         }
 897 #endif                          /* CONFIG_REISERFS_CHECK */
 898
 899         /* item to be appended */
 900         ih = B_N_PITEM_HEAD(bh, affected_item_num);
 901
 902         last_loc = ih_location(&(ih[nr - affected_item_num - 1]));
 903         unmoved_loc = affected_item_num ? ih_location(ih - 1) : bh->b_size;
 904
 905         /* prepare space */
 906         memmove(bh->b_data + last_loc - paste_size, bh->b_data + last_loc,
 907                 unmoved_loc - last_loc);
 908
 909         /* change locations */
 910         for (i = affected_item_num; i < nr; i++)
 911                 put_ih_location(&(ih[i - affected_item_num]),
 912                                 ih_location(&(ih[i - affected_item_num])) -
 913                                 paste_size);
 914
 915         if (body) {
 916                 if (!is_direntry_le_ih(ih)) {
 917                         if (!pos_in_item) {
 918                                 /* shift data to right */
 919                                 memmove(bh->b_data + ih_location(ih) +
 920                                         paste_size,
 921                                         bh->b_data + ih_location(ih),
 922                                         ih_item_len(ih));
 923                                 /* paste data in the head of item */
 924                                 memset(bh->b_data + ih_location(ih), 0,
 925                                        zeros_number);
 926                                 memcpy(bh->b_data + ih_location(ih) +
 927                                        zeros_number, body,
 928                                        paste_size - zeros_number);
 929                         } else {
 930                                 memset(bh->b_data + unmoved_loc - paste_size, 0,
 931                                        zeros_number);
 932                                 memcpy(bh->b_data + unmoved_loc - paste_size +
 933                                        zeros_number, body,
 934                                        paste_size - zeros_number);
 935                         }
 936                 }
 937         } else
 938                 memset(bh->b_data + unmoved_loc - paste_size, '\0', paste_size);
 939
 940         put_ih_item_len(ih, ih_item_len(ih) + paste_size);
 941
 942         /* change free space */
 943         set_blkh_free_space(blkh, free_space - paste_size);
 944
 945         do_balance_mark_leaf_dirty(bi->tb, bh, 0);
 946
 947         if (bi->bi_parent) {
 948                 struct disk_child *t_dc =
 949                     B_N_CHILD(bi->bi_parent, bi->bi_position);
 950                 put_dc_size(t_dc, dc_size(t_dc) + paste_size);
 951                 do_balance_mark_internal_dirty(bi->tb, bi->bi_parent, 0);
 952         }
 953 }
 954
 955 /* cuts DEL_COUNT entries beginning from FROM-th entry. Directory item
 956    does not have free space, so it moves DEHs and remaining records as
 957    necessary. Return value is size of removed part of directory item
 958    in bytes. */
 959 static int leaf_cut_entries(struct buffer_head *bh,
 960                             struct item_head *ih, int from, int del_count)
 961 {
 962         char *item;
 963         struct reiserfs_de_head *deh;
 964         int prev_record_offset; /* offset of record, that is (from-1)th */
 965         char *prev_record;      /* */
 966         int cut_records_len;    /* length of all removed records */
 967         int i;
 968
 969         /* make sure, that item is directory and there are enough entries to
 970            remove */
 971         RFALSE(!is_direntry_le_ih(ih), "10180: item is not directory item");
 972         RFALSE(I_ENTRY_COUNT(ih) < from + del_count,
 973                "10185: item contains not enough entries: entry_cout = %d, from = %d, to delete = %d",
 974                I_ENTRY_COUNT(ih), from, del_count);
 975
 976         if (del_count == 0)
 977                 return 0;
 978
 979         /* first byte of item */
 980         item = bh->b_data + ih_location(ih);
 981
 982         /* entry head array */
 983         deh = B_I_DEH(bh, ih);
 984
 985         /* first byte of remaining entries, those are BEFORE cut entries
 986            (prev_record) and length of all removed records (cut_records_len) */
 987         prev_record_offset =
 988             (from ? deh_location(&(deh[from - 1])) : ih_item_len(ih));
 989         cut_records_len = prev_record_offset /*from_record */  -
 990             deh_location(&(deh[from + del_count - 1]));
 991         prev_record = item + prev_record_offset;
 992
 993         /* adjust locations of remaining entries */
 994         for (i = I_ENTRY_COUNT(ih) - 1; i > from + del_count - 1; i--)
 995                 put_deh_location(&(deh[i]),
 996                                  deh_location(&deh[i]) -
 997                                  (DEH_SIZE * del_count));
 998
 999         for (i = 0; i < from; i++)
1000                 put_deh_location(&(deh[i]),
1001                                  deh_location(&deh[i]) - (DEH_SIZE * del_count +
1002                                                           cut_records_len));
1003
1004         put_ih_entry_count(ih, ih_entry_count(ih) - del_count);
1005
1006         /* shift entry head array and entries those are AFTER removed entries */
1007         memmove((char *)(deh + from),
1008                 deh + from + del_count,
1009                 prev_record - cut_records_len - (char *)(deh + from +
1010                                                          del_count));
1011
1012         /* shift records, those are BEFORE removed entries */
1013         memmove(prev_record - cut_records_len - DEH_SIZE * del_count,
1014                 prev_record, item + ih_item_len(ih) - prev_record);
1015
1016         return DEH_SIZE * del_count + cut_records_len;
1017 }
1018
1019 /*  when cut item is part of regular file
1020         pos_in_item - first byte that must be cut
1021         cut_size - number of bytes to be cut beginning from pos_in_item
1022
1023    when cut item is part of directory
1024         pos_in_item - number of first deleted entry
1025         cut_size - count of deleted entries
1026     */
1027 void leaf_cut_from_buffer(struct buffer_info *bi, int cut_item_num,
1028                           int pos_in_item, int cut_size)
1029 {
1030         int nr;
1031         struct buffer_head *bh = bi->bi_bh;
1032         struct block_head *blkh;
1033         struct item_head *ih;
1034         int last_loc, unmoved_loc;
1035         int i;
1036
1037         blkh = B_BLK_HEAD(bh);
1038         nr = blkh_nr_item(blkh);
1039
1040         /* item head of truncated item */
1041         ih = B_N_PITEM_HEAD(bh, cut_item_num);
1042
1043         if (is_direntry_le_ih(ih)) {
1044                 /* first cut entry () */
1045                 cut_size = leaf_cut_entries(bh, ih, pos_in_item, cut_size);
1046                 if (pos_in_item == 0) {
1047                         /* change key */
1048                         RFALSE(cut_item_num,
1049                                "when 0-th enrty of item is cut, that item must be first in the node, not %d-th",
1050                                cut_item_num);
1051                         /* change item key by key of first entry in the item */
1052                         set_le_ih_k_offset(ih, deh_offset(B_I_DEH(bh, ih)));
1053                         /*memcpy (&ih->ih_key.k_offset, &(B_I_DEH (bh, ih)->deh_offset), SHORT_KEY_SIZE); */
1054                 }
1055         } else {
1056                 /* item is direct or indirect */
1057                 RFALSE(is_statdata_le_ih(ih), "10195: item is stat data");
1058                 RFALSE(pos_in_item && pos_in_item + cut_size != ih_item_len(ih),
1059                        "10200: invalid offset (%lu) or trunc_size (%lu) or ih_item_len (%lu)",
1060                        (long unsigned)pos_in_item, (long unsigned)cut_size,
1061                        (long unsigned)ih_item_len(ih));
1062
1063                 /* shift item body to left if cut is from the head of item */
1064                 if (pos_in_item == 0) {
1065                         memmove(bh->b_data + ih_location(ih),
1066                                 bh->b_data + ih_location(ih) + cut_size,
1067                                 ih_item_len(ih) - cut_size);
1068
1069                         /* change key of item */
1070                         if (is_direct_le_ih(ih))
1071                                 set_le_ih_k_offset(ih,
1072                                                    le_ih_k_offset(ih) +
1073                                                    cut_size);
1074                         else {
1075                                 set_le_ih_k_offset(ih,
1076                                                    le_ih_k_offset(ih) +
1077                                                    (cut_size / UNFM_P_SIZE) *
1078                                                    bh->b_size);
1079                                 RFALSE(ih_item_len(ih) == cut_size
1080                                        && get_ih_free_space(ih),
1081                                        "10205: invalid ih_free_space (%h)", ih);
1082                         }
1083                 }
1084         }
1085
1086         /* location of the last item */
1087         last_loc = ih_location(&(ih[nr - cut_item_num - 1]));
1088
1089         /* location of the item, which is remaining at the same place */
1090         unmoved_loc = cut_item_num ? ih_location(ih - 1) : bh->b_size;
1091
1092         /* shift */
1093         memmove(bh->b_data + last_loc + cut_size, bh->b_data + last_loc,
1094                 unmoved_loc - last_loc - cut_size);
1095
1096         /* change item length */
1097         put_ih_item_len(ih, ih_item_len(ih) - cut_size);
1098
1099         if (is_indirect_le_ih(ih)) {
1100                 if (pos_in_item)
1101                         set_ih_free_space(ih, 0);
1102         }
1103
1104         /* change locations */
1105         for (i = cut_item_num; i < nr; i++)
1106                 put_ih_location(&(ih[i - cut_item_num]),
1107                                 ih_location(&ih[i - cut_item_num]) + cut_size);
1108
1109         /* size, free space */
1110         set_blkh_free_space(blkh, blkh_free_space(blkh) + cut_size);
1111
1112         do_balance_mark_leaf_dirty(bi->tb, bh, 0);
1113
1114         if (bi->bi_parent) {
1115                 struct disk_child *t_dc;
1116                 t_dc = B_N_CHILD(bi->bi_parent, bi->bi_position);
1117                 put_dc_size(t_dc, dc_size(t_dc) - cut_size);
1118                 do_balance_mark_internal_dirty(bi->tb, bi->bi_parent, 0);
1119         }
1120 }
1121
1122 /* delete del_num items from buffer starting from the first'th item */
1123 static void leaf_delete_items_entirely(struct buffer_info *bi,
1124                                        int first, int del_num)
1125 {
1126         struct buffer_head *bh = bi->bi_bh;
1127         int nr;
1128         int i, j;
1129         int last_loc, last_removed_loc;
1130         struct block_head *blkh;
1131         struct item_head *ih;
1132
1133         RFALSE(bh == NULL, "10210: buffer is 0");
1134         RFALSE(del_num < 0, "10215: del_num less than 0 (%d)", del_num);
1135
1136         if (del_num == 0)
1137                 return;
1138
1139         blkh = B_BLK_HEAD(bh);
1140         nr = blkh_nr_item(blkh);
1141
1142         RFALSE(first < 0 || first + del_num > nr,
1143                "10220: first=%d, number=%d, there is %d items", first, del_num,
1144                nr);
1145
1146         if (first == 0 && del_num == nr) {
1147                 /* this does not work */
1148                 make_empty_node(bi);
1149
1150                 do_balance_mark_leaf_dirty(bi->tb, bh, 0);
1151                 return;
1152         }
1153
1154         ih = B_N_PITEM_HEAD(bh, first);
1155
1156         /* location of unmovable item */
1157         j = (first == 0) ? bh->b_size : ih_location(ih - 1);
1158
1159         /* delete items */
1160         last_loc = ih_location(&(ih[nr - 1 - first]));
1161         last_removed_loc = ih_location(&(ih[del_num - 1]));
1162
1163         memmove(bh->b_data + last_loc + j - last_removed_loc,
1164                 bh->b_data + last_loc, last_removed_loc - last_loc);
1165
1166         /* delete item headers */
1167         memmove(ih, ih + del_num, (nr - first - del_num) * IH_SIZE);
1168
1169         /* change item location */
1170         for (i = first; i < nr - del_num; i++)
1171                 put_ih_location(&(ih[i - first]),
1172                                 ih_location(&(ih[i - first])) + (j -
1173                                                                  last_removed_loc));
1174
1175         /* sizes, item number */
1176         set_blkh_nr_item(blkh, blkh_nr_item(blkh) - del_num);
1177         set_blkh_free_space(blkh,
1178                             blkh_free_space(blkh) + (j - last_removed_loc +
1179                                                      IH_SIZE * del_num));
1180
1181         do_balance_mark_leaf_dirty(bi->tb, bh, 0);
1182
1183         if (bi->bi_parent) {
1184                 struct disk_child *t_dc =
1185                     B_N_CHILD(bi->bi_parent, bi->bi_position);
1186                 put_dc_size(t_dc,
1187                             dc_size(t_dc) - (j - last_removed_loc +
1188                                              IH_SIZE * del_num));
1189                 do_balance_mark_internal_dirty(bi->tb, bi->bi_parent, 0);
1190         }
1191 }
1192
1193 /* paste new_entry_count entries (new_dehs, records) into position before to item_num-th item */
1194 void leaf_paste_entries(struct buffer_head *bh,
1195                         int item_num,
1196                         int before,
1197                         int new_entry_count,
1198                         struct reiserfs_de_head *new_dehs,
1199                         const char *records, int paste_size)
1200 {
1201         struct item_head *ih;
1202         char *item;
1203         struct reiserfs_de_head *deh;
1204         char *insert_point;
1205         int i, old_entry_num;
1206
1207         if (new_entry_count == 0)
1208                 return;
1209
1210         ih = B_N_PITEM_HEAD(bh, item_num);
1211
1212         /* make sure, that item is directory, and there are enough records in it */
1213         RFALSE(!is_direntry_le_ih(ih), "10225: item is not directory item");
1214         RFALSE(I_ENTRY_COUNT(ih) < before,
1215                "10230: there are no entry we paste entries before. entry_count = %d, before = %d",
1216                I_ENTRY_COUNT(ih), before);
1217
1218         /* first byte of dest item */
1219         item = bh->b_data + ih_location(ih);
1220
1221         /* entry head array */
1222         deh = B_I_DEH(bh, ih);
1223
1224         /* new records will be pasted at this point */
1225         insert_point =
1226             item +
1227             (before ? deh_location(&(deh[before - 1]))
1228              : (ih_item_len(ih) - paste_size));
1229
1230         /* adjust locations of records that will be AFTER new records */
1231         for (i = I_ENTRY_COUNT(ih) - 1; i >= before; i--)
1232                 put_deh_location(&(deh[i]),
1233                                  deh_location(&(deh[i])) +
1234                                  (DEH_SIZE * new_entry_count));
1235
1236         /* adjust locations of records that will be BEFORE new records */
1237         for (i = 0; i < before; i++)
1238                 put_deh_location(&(deh[i]),
1239                                  deh_location(&(deh[i])) + paste_size);
1240
1241         old_entry_num = I_ENTRY_COUNT(ih);
1242         put_ih_entry_count(ih, ih_entry_count(ih) + new_entry_count);
1243
1244         /* prepare space for pasted records */
1245         memmove(insert_point + paste_size, insert_point,
1246                 item + (ih_item_len(ih) - paste_size) - insert_point);
1247
1248         /* copy new records */
1249         memcpy(insert_point + DEH_SIZE * new_entry_count, records,
1250                paste_size - DEH_SIZE * new_entry_count);
1251
1252         /* prepare space for new entry heads */
1253         deh += before;
1254         memmove((char *)(deh + new_entry_count), deh,
1255                 insert_point - (char *)deh);
1256
1257         /* copy new entry heads */
1258         deh = (struct reiserfs_de_head *)((char *)deh);
1259         memcpy(deh, new_dehs, DEH_SIZE * new_entry_count);
1260
1261         /* set locations of new records */
1262         for (i = 0; i < new_entry_count; i++) {
1263                 put_deh_location(&(deh[i]),
1264                                  deh_location(&(deh[i])) +
1265                                  (-deh_location
1266                                   (&(new_dehs[new_entry_count - 1])) +
1267                                   insert_point + DEH_SIZE * new_entry_count -
1268                                   item));
1269         }
1270
1271         /* change item key if necessary (when we paste before 0-th entry */
1272         if (!before) {
1273                 set_le_ih_k_offset(ih, deh_offset(new_dehs));
1274 /*      memcpy (&ih->ih_key.k_offset,
1275                        &new_dehs->deh_offset, SHORT_KEY_SIZE);*/
1276         }
1277 #ifdef CONFIG_REISERFS_CHECK
1278         {
1279                 int prev, next;
1280                 /* check record locations */
1281                 deh = B_I_DEH(bh, ih);
1282                 for (i = 0; i < I_ENTRY_COUNT(ih); i++) {
1283                         next =
1284                             (i <
1285                              I_ENTRY_COUNT(ih) -
1286                              1) ? deh_location(&(deh[i + 1])) : 0;
1287                         prev = (i != 0) ? deh_location(&(deh[i - 1])) : 0;
1288
1289                         if (prev && prev <= deh_location(&(deh[i])))
1290                                 reiserfs_warning(NULL,
1291                                                  "vs-10240: leaf_paste_entries: directory item (%h) corrupted (prev %a, cur(%d) %a)",
1292                                                  ih, deh + i - 1, i, deh + i);
1293                         if (next && next >= deh_location(&(deh[i])))
1294                                 reiserfs_warning(NULL,
1295                                                  "vs-10250: leaf_paste_entries: directory item (%h) corrupted (cur(%d) %a, next %a)",
1296                                                  ih, i, deh + i, deh + i + 1);
1297                 }
1298         }
1299 #endif
1300
1301 }