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 */ 15static 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 */ 134static 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 */ 310static 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 */ 414static 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 */ 521static 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 */ 629static 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 */ 715int 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 */ 741int 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 */ 794int 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 814static 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*/ 827void 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 */ 901void 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 */ 978void 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 */ 1072static 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 */ 1145void 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 */ 1240static 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 */ 1314void 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} 1427