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