root/fs/reiserfs/lbalance.c

DEFINITIONS

1. leaf_copy_dir_entries
2. leaf_copy_boundary_item
3. leaf_copy_items_entirely
4. leaf_item_bottle
5. leaf_copy_items
6. leaf_define_dest_src_infos
7. leaf_move_items
8. leaf_shift_left
9. leaf_shift_right
10. leaf_delete_items
11. leaf_insert_into_buf
12. leaf_paste_in_buffer
13. leaf_cut_entries
14. leaf_cut_from_buffer
15. leaf_delete_items_entirely
16. leaf_paste_entries

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