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) */ 24 static void leaf_copy_dir_entries(struct buffer_info *dest_bi, 25 struct buffer_head *source, int last_first, 26 int item_num, int from, int copy_count) 27 { 28 struct buffer_head *dest = dest_bi->bi_bh; 29 int item_num_in_dest; /* either the number of target item, 30 or if we must create a new item, 31 the number of the item we will 32 create it next to */ 33 struct item_head *ih; 34 struct reiserfs_de_head *deh; 35 int copy_records_len; /* length of all records in item to be copied */ 36 char *records; 37 38 ih = B_N_PITEM_HEAD(source, item_num); 39 40 RFALSE(!is_direntry_le_ih(ih), "vs-10000: item must be directory item"); 41 42 /* length of all record to be copied and first byte of the last of them */ 43 deh = B_I_DEH(source, ih); 44 if (copy_count) { 45 copy_records_len = (from ? deh_location(&(deh[from - 1])) : 46 ih_item_len(ih)) - 47 deh_location(&(deh[from + copy_count - 1])); 48 records = 49 source->b_data + ih_location(ih) + 50 deh_location(&(deh[from + copy_count - 1])); 51 } else { 52 copy_records_len = 0; 53 records = NULL; 54 } 55 56 /* when copy last to first, dest buffer can contain 0 items */ 57 item_num_in_dest = 58 (last_first == 59 LAST_TO_FIRST) ? ((B_NR_ITEMS(dest)) ? 0 : -1) : (B_NR_ITEMS(dest) 60 - 1); 61 62 /* if there are no items in dest or the first/last item in dest is not item of the same directory */ 63 if ((item_num_in_dest == -1) || 64 (last_first == FIRST_TO_LAST && le_ih_k_offset(ih) == DOT_OFFSET) || 65 (last_first == LAST_TO_FIRST 66 && comp_short_le_keys /*COMP_SHORT_KEYS */ (&ih->ih_key, 67 B_N_PKEY(dest, 68 item_num_in_dest)))) 69 { 70 /* create new item in dest */ 71 struct item_head new_ih; 72 73 /* form item header */ 74 memcpy(&new_ih.ih_key, &ih->ih_key, KEY_SIZE); 75 put_ih_version(&new_ih, KEY_FORMAT_3_5); 76 /* calculate item len */ 77 put_ih_item_len(&new_ih, 78 DEH_SIZE * copy_count + copy_records_len); 79 put_ih_entry_count(&new_ih, 0); 80 81 if (last_first == LAST_TO_FIRST) { 82 /* form key by the following way */ 83 if (from < I_ENTRY_COUNT(ih)) { 84 set_le_ih_k_offset(&new_ih, 85 deh_offset(&(deh[from]))); 86 /*memcpy (&new_ih.ih_key.k_offset, &deh[from].deh_offset, SHORT_KEY_SIZE); */ 87 } else { 88 /* no entries will be copied to this item in this function */ 89 set_le_ih_k_offset(&new_ih, U32_MAX); 90 /* this item is not yet valid, but we want I_IS_DIRECTORY_ITEM to return 1 for it, so we -1 */ 91 } 92 set_le_key_k_type(KEY_FORMAT_3_5, &(new_ih.ih_key), 93 TYPE_DIRENTRY); 94 } 95 96 /* insert item into dest buffer */ 97 leaf_insert_into_buf(dest_bi, 98 (last_first == 99 LAST_TO_FIRST) ? 0 : B_NR_ITEMS(dest), 100 &new_ih, NULL, 0); 101 } else { 102 /* prepare space for entries */ 103 leaf_paste_in_buffer(dest_bi, 104 (last_first == 105 FIRST_TO_LAST) ? (B_NR_ITEMS(dest) - 106 1) : 0, MAX_US_INT, 107 DEH_SIZE * copy_count + copy_records_len, 108 records, 0); 109 } 110 111 item_num_in_dest = 112 (last_first == FIRST_TO_LAST) ? (B_NR_ITEMS(dest) - 1) : 0; 113 114 leaf_paste_entries(dest_bi, item_num_in_dest, 115 (last_first == 116 FIRST_TO_LAST) ? I_ENTRY_COUNT(B_N_PITEM_HEAD(dest, 117 item_num_in_dest)) 118 : 0, copy_count, deh + from, records, 119 DEH_SIZE * copy_count + copy_records_len); 120 } 121 122 /* Copy the first (if last_first == FIRST_TO_LAST) or last (last_first == LAST_TO_FIRST) item or 123 part of it or nothing (see the return 0 below) from SOURCE to the end 124 (if last_first) or beginning (!last_first) of the DEST */ 125 /* returns 1 if anything was copied, else 0 */ 126 static int leaf_copy_boundary_item(struct buffer_info *dest_bi, 127 struct buffer_head *src, int last_first, 128 int bytes_or_entries) 129 { 130 struct buffer_head *dest = dest_bi->bi_bh; 131 int dest_nr_item, src_nr_item; /* number of items in the source and destination buffers */ 132 struct item_head *ih; 133 struct item_head *dih; 134 135 dest_nr_item = B_NR_ITEMS(dest); 136 137 if (last_first == FIRST_TO_LAST) { 138 /* if ( DEST is empty or first item of SOURCE and last item of DEST are the items of different objects 139 or of different types ) then there is no need to treat this item differently from the other items 140 that we copy, so we return */ 141 ih = B_N_PITEM_HEAD(src, 0); 142 dih = B_N_PITEM_HEAD(dest, dest_nr_item - 1); 143 if (!dest_nr_item 144 || (!op_is_left_mergeable(&(ih->ih_key), src->b_size))) 145 /* there is nothing to merge */ 146 return 0; 147 148 RFALSE(!ih_item_len(ih), 149 "vs-10010: item can not have empty length"); 150 151 if (is_direntry_le_ih(ih)) { 152 if (bytes_or_entries == -1) 153 /* copy all entries to dest */ 154 bytes_or_entries = ih_entry_count(ih); 155 leaf_copy_dir_entries(dest_bi, src, FIRST_TO_LAST, 0, 0, 156 bytes_or_entries); 157 return 1; 158 } 159 160 /* copy part of the body of the first item of SOURCE to the end of the body of the last item of the DEST 161 part defined by 'bytes_or_entries'; if bytes_or_entries == -1 copy whole body; don't create new item header 162 */ 163 if (bytes_or_entries == -1) 164 bytes_or_entries = ih_item_len(ih); 165 166 #ifdef CONFIG_REISERFS_CHECK 167 else { 168 if (bytes_or_entries == ih_item_len(ih) 169 && is_indirect_le_ih(ih)) 170 if (get_ih_free_space(ih)) 171 reiserfs_panic(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 */ 283 static void leaf_copy_items_entirely(struct buffer_info *dest_bi, 284 struct buffer_head *src, int last_first, 285 int first, int cpy_num) 286 { 287 struct buffer_head *dest; 288 int nr, free_space; 289 int dest_before; 290 int last_loc, last_inserted_loc, location; 291 int i, j; 292 struct block_head *blkh; 293 struct item_head *ih; 294 295 RFALSE(last_first != LAST_TO_FIRST && last_first != FIRST_TO_LAST, 296 "vs-10090: bad last_first parameter %d", last_first); 297 RFALSE(B_NR_ITEMS(src) - first < cpy_num, 298 "vs-10100: too few items in source %d, required %d from %d", 299 B_NR_ITEMS(src), cpy_num, first); 300 RFALSE(cpy_num < 0, "vs-10110: can not copy negative amount of items"); 301 RFALSE(!dest_bi, "vs-10120: can not copy negative amount of items"); 302 303 dest = dest_bi->bi_bh; 304 305 RFALSE(!dest, "vs-10130: can not copy negative amount of items"); 306 307 if (cpy_num == 0) 308 return; 309 310 blkh = B_BLK_HEAD(dest); 311 nr = blkh_nr_item(blkh); 312 free_space = blkh_free_space(blkh); 313 314 /* we will insert items before 0-th or nr-th item in dest buffer. It depends of last_first parameter */ 315 dest_before = (last_first == LAST_TO_FIRST) ? 0 : nr; 316 317 /* location of head of first new item */ 318 ih = B_N_PITEM_HEAD(dest, dest_before); 319 320 RFALSE(blkh_free_space(blkh) < cpy_num * IH_SIZE, 321 "vs-10140: not enough free space for headers %d (needed %d)", 322 B_FREE_SPACE(dest), cpy_num * IH_SIZE); 323 324 /* prepare space for headers */ 325 memmove(ih + cpy_num, ih, (nr - dest_before) * IH_SIZE); 326 327 /* copy item headers */ 328 memcpy(ih, B_N_PITEM_HEAD(src, first), cpy_num * IH_SIZE); 329 330 free_space -= (IH_SIZE * cpy_num); 331 set_blkh_free_space(blkh, free_space); 332 333 /* location of unmovable item */ 334 j = location = (dest_before == 0) ? dest->b_size : ih_location(ih - 1); 335 for (i = dest_before; i < nr + cpy_num; i++) { 336 location -= ih_item_len(ih + i - dest_before); 337 put_ih_location(ih + i - dest_before, location); 338 } 339 340 /* prepare space for items */ 341 last_loc = ih_location(&(ih[nr + cpy_num - 1 - dest_before])); 342 last_inserted_loc = ih_location(&(ih[cpy_num - 1])); 343 344 /* check free space */ 345 RFALSE(free_space < j - last_inserted_loc, 346 "vs-10150: not enough free space for items %d (needed %d)", 347 free_space, j - last_inserted_loc); 348 349 memmove(dest->b_data + last_loc, 350 dest->b_data + last_loc + j - last_inserted_loc, 351 last_inserted_loc - last_loc); 352 353 /* copy items */ 354 memcpy(dest->b_data + last_inserted_loc, 355 B_N_PITEM(src, (first + cpy_num - 1)), j - last_inserted_loc); 356 357 /* sizes, item number */ 358 set_blkh_nr_item(blkh, nr + cpy_num); 359 set_blkh_free_space(blkh, free_space - (j - last_inserted_loc)); 360 361 do_balance_mark_leaf_dirty(dest_bi->tb, dest, 0); 362 363 if (dest_bi->bi_parent) { 364 struct disk_child *t_dc; 365 t_dc = B_N_CHILD(dest_bi->bi_parent, dest_bi->bi_position); 366 RFALSE(dc_block_number(t_dc) != dest->b_blocknr, 367 "vs-10160: block number in bh does not match to field in disk_child structure %lu and %lu", 368 (long unsigned)dest->b_blocknr, 369 (long unsigned)dc_block_number(t_dc)); 370 put_dc_size(t_dc, 371 dc_size(t_dc) + (j - last_inserted_loc + 372 IH_SIZE * cpy_num)); 373 374 do_balance_mark_internal_dirty(dest_bi->tb, dest_bi->bi_parent, 375 0); 376 } 377 } 378 379 /* This function splits the (liquid) item into two items (useful when 380 shifting part of an item into another node.) */ 381 static void leaf_item_bottle(struct buffer_info *dest_bi, 382 struct buffer_head *src, int last_first, 383 int item_num, int cpy_bytes) 384 { 385 struct buffer_head *dest = dest_bi->bi_bh; 386 struct item_head *ih; 387 388 RFALSE(cpy_bytes == -1, 389 "vs-10170: bytes == - 1 means: do not split item"); 390 391 if (last_first == FIRST_TO_LAST) { 392 /* if ( if item in position item_num in buffer SOURCE is directory item ) */ 393 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. */ 475 static 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 */ 556 static 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 */ 638 int 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 */ 662 int 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 */ 708 int 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 726 static 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 */ 735 void 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 */ 798 void 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 */ 872 void 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. */ 964 static 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 */ 1032 void 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 */ 1128 static 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 */ 1199 void 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