1 /* 2 * Copyright 2000 by Hans Reiser, licensing governed by reiserfs/README 3 */ 4 5 #include <asm/uaccess.h> 6 #include <linux/string.h> 7 #include <linux/time.h> 8 #include <linux/reiserfs_fs.h> 9 #include <linux/buffer_head.h> 10 11 /* these are used in do_balance.c */ 12 13 /* leaf_move_items 14 leaf_shift_left 15 leaf_shift_right 16 leaf_delete_items 17 leaf_insert_into_buf 18 leaf_paste_in_buffer 19 leaf_cut_from_buffer 20 leaf_paste_entries 21 */ 22 23 /* copy copy_count entries from source directory item to dest buffer (creating new item if needed) */ 24 static void leaf_copy_dir_entries(struct buffer_info *dest_bi, 25 struct buffer_head *source, int last_first, 26 int item_num, int from, int copy_count) 27 { 28 struct buffer_head *dest = dest_bi->bi_bh; 29 int item_num_in_dest; /* either the number of target item, 30 or if we must create a new item, 31 the number of the item we will 32 create it next to */ 33 struct item_head *ih; 34 struct reiserfs_de_head *deh; 35 int copy_records_len; /* length of all records in item to be copied */ 36 char *records; 37 38 ih = B_N_PITEM_HEAD(source, item_num); 39 40 RFALSE(!is_direntry_le_ih(ih), "vs-10000: item must be directory item"); 41 42 /* length of all record to be copied and first byte of the last of them */ 43 deh = B_I_DEH(source, ih); 44 if (copy_count) { 45 copy_records_len = (from ? deh_location(&(deh[from - 1])) : 46 ih_item_len(ih)) - 47 deh_location(&(deh[from + copy_count - 1])); 48 records = 49 source->b_data + ih_location(ih) + 50 deh_location(&(deh[from + copy_count - 1])); 51 } else { 52 copy_records_len = 0; 53 records = NULL; 54 } 55 56 /* when copy last to first, dest buffer can contain 0 items */ 57 item_num_in_dest = 58 (last_first == 59 LAST_TO_FIRST) ? ((B_NR_ITEMS(dest)) ? 0 : -1) : (B_NR_ITEMS(dest) 60 - 1); 61 62 /* if there are no items in dest or the first/last item in dest is not item of the same directory */ 63 if ((item_num_in_dest == -1) || 64 (last_first == FIRST_TO_LAST && le_ih_k_offset(ih) == DOT_OFFSET) || 65 (last_first == LAST_TO_FIRST 66 && comp_short_le_keys /*COMP_SHORT_KEYS */ (&ih->ih_key, 67 B_N_PKEY(dest, 68 item_num_in_dest)))) 69 { 70 /* create new item in dest */ 71 struct item_head new_ih; 72 73 /* form item header */ 74 memcpy(&new_ih.ih_key, &ih->ih_key, KEY_SIZE); 75 put_ih_version(&new_ih, KEY_FORMAT_3_5); 76 /* calculate item len */ 77 put_ih_item_len(&new_ih, 78 DEH_SIZE * copy_count + copy_records_len); 79 put_ih_entry_count(&new_ih, 0); 80 81 if (last_first == LAST_TO_FIRST) { 82 /* form key by the following way */ 83 if (from < I_ENTRY_COUNT(ih)) { 84 set_le_ih_k_offset(&new_ih, 85 deh_offset(&(deh[from]))); 86 /*memcpy (&new_ih.ih_key.k_offset, &deh[from].deh_offset, SHORT_KEY_SIZE); */ 87 } else { 88 /* no entries will be copied to this item in this function */ 89 set_le_ih_k_offset(&new_ih, U32_MAX); 90 /* this item is not yet valid, but we want I_IS_DIRECTORY_ITEM to return 1 for it, so we -1 */ 91 } 92 set_le_key_k_type(KEY_FORMAT_3_5, &(new_ih.ih_key), 93 TYPE_DIRENTRY); 94 } 95 96 /* insert item into dest buffer */ 97 leaf_insert_into_buf(dest_bi, 98 (last_first == 99 LAST_TO_FIRST) ? 0 : B_NR_ITEMS(dest), 100 &new_ih, NULL, 0); 101 } else { 102 /* prepare space for entries */ 103 leaf_paste_in_buffer(dest_bi, 104 (last_first == 105 FIRST_TO_LAST) ? (B_NR_ITEMS(dest) - 106 1) : 0, MAX_US_INT, 107 DEH_SIZE * copy_count + copy_records_len, 108 records, 0); 109 } 110 111 item_num_in_dest = 112 (last_first == FIRST_TO_LAST) ? (B_NR_ITEMS(dest) - 1) : 0; 113 114 leaf_paste_entries(dest_bi, 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 if (is_direntry_le_ih(ih = B_N_PITEM_HEAD(src, item_num))) 394 leaf_copy_dir_entries(dest_bi, src, FIRST_TO_LAST, 395 item_num, 0, cpy_bytes); 396 else { 397 struct item_head n_ih; 398 399 /* copy part of the body of the item number 'item_num' of SOURCE to the end of the DEST 400 part defined by 'cpy_bytes'; create new item header; change old item_header (????); 401 n_ih = new item_header; 402 */ 403 memcpy(&n_ih, ih, IH_SIZE); 404 put_ih_item_len(&n_ih, cpy_bytes); 405 if (is_indirect_le_ih(ih)) { 406 RFALSE(cpy_bytes == ih_item_len(ih) 407 && get_ih_free_space(ih), 408 "vs-10180: when whole indirect item is bottle to left neighbor, it must have free_space==0 (not %lu)", 409 (long unsigned)get_ih_free_space(ih)); 410 set_ih_free_space(&n_ih, 0); 411 } 412 413 RFALSE(op_is_left_mergeable(&(ih->ih_key), src->b_size), 414 "vs-10190: bad mergeability of item %h", ih); 415 n_ih.ih_version = ih->ih_version; /* JDM Endian safe, both le */ 416 leaf_insert_into_buf(dest_bi, B_NR_ITEMS(dest), &n_ih, 417 B_N_PITEM(src, item_num), 0); 418 } 419 } else { 420 /* if ( if item in position item_num in buffer SOURCE is directory item ) */ 421 if (is_direntry_le_ih(ih = B_N_PITEM_HEAD(src, item_num))) 422 leaf_copy_dir_entries(dest_bi, src, LAST_TO_FIRST, 423 item_num, 424 I_ENTRY_COUNT(ih) - cpy_bytes, 425 cpy_bytes); 426 else { 427 struct item_head n_ih; 428 429 /* copy part of the body of the item number 'item_num' of SOURCE to the begin of the DEST 430 part defined by 'cpy_bytes'; create new item header; 431 n_ih = new item_header; 432 */ 433 memcpy(&n_ih, ih, SHORT_KEY_SIZE); 434 435 n_ih.ih_version = ih->ih_version; /* JDM Endian safe, both le */ 436 437 if (is_direct_le_ih(ih)) { 438 set_le_ih_k_offset(&n_ih, 439 le_ih_k_offset(ih) + 440 ih_item_len(ih) - cpy_bytes); 441 set_le_ih_k_type(&n_ih, TYPE_DIRECT); 442 set_ih_free_space(&n_ih, MAX_US_INT); 443 } else { 444 /* indirect item */ 445 RFALSE(!cpy_bytes && get_ih_free_space(ih), 446 "vs-10200: ih->ih_free_space must be 0 when indirect item will be appended"); 447 set_le_ih_k_offset(&n_ih, 448 le_ih_k_offset(ih) + 449 (ih_item_len(ih) - 450 cpy_bytes) / UNFM_P_SIZE * 451 dest->b_size); 452 set_le_ih_k_type(&n_ih, TYPE_INDIRECT); 453 set_ih_free_space(&n_ih, get_ih_free_space(ih)); 454 } 455 456 /* set item length */ 457 put_ih_item_len(&n_ih, cpy_bytes); 458 459 n_ih.ih_version = ih->ih_version; /* JDM Endian safe, both le */ 460 461 leaf_insert_into_buf(dest_bi, 0, &n_ih, 462 B_N_PITEM(src, 463 item_num) + 464 ih_item_len(ih) - cpy_bytes, 0); 465 } 466 } 467 } 468 469 /* If cpy_bytes equals minus one than copy cpy_num whole items from SOURCE to DEST. 470 If cpy_bytes not equal to minus one than copy cpy_num-1 whole items from SOURCE to DEST. 471 From last item copy cpy_num bytes for regular item and cpy_num directory entries for 472 directory item. */ 473 static int leaf_copy_items(struct buffer_info *dest_bi, struct buffer_head *src, 474 int last_first, int cpy_num, int cpy_bytes) 475 { 476 struct buffer_head *dest; 477 int pos, i, src_nr_item, bytes; 478 479 dest = dest_bi->bi_bh; 480 RFALSE(!dest || !src, "vs-10210: !dest || !src"); 481 RFALSE(last_first != FIRST_TO_LAST && last_first != LAST_TO_FIRST, 482 "vs-10220:last_first != FIRST_TO_LAST && last_first != LAST_TO_FIRST"); 483 RFALSE(B_NR_ITEMS(src) < cpy_num, 484 "vs-10230: No enough items: %d, req. %d", B_NR_ITEMS(src), 485 cpy_num); 486 RFALSE(cpy_num < 0, "vs-10240: cpy_num < 0 (%d)", cpy_num); 487 488 if (cpy_num == 0) 489 return 0; 490 491 if (last_first == FIRST_TO_LAST) { 492 /* copy items to left */ 493 pos = 0; 494 if (cpy_num == 1) 495 bytes = cpy_bytes; 496 else 497 bytes = -1; 498 499 /* copy the first item or it part or nothing to the end of the DEST (i = leaf_copy_boundary_item(DEST,SOURCE,0,bytes)) */ 500 i = leaf_copy_boundary_item(dest_bi, src, FIRST_TO_LAST, bytes); 501 cpy_num -= i; 502 if (cpy_num == 0) 503 return i; 504 pos += i; 505 if (cpy_bytes == -1) 506 /* copy first cpy_num items starting from position 'pos' of SOURCE to end of DEST */ 507 leaf_copy_items_entirely(dest_bi, src, FIRST_TO_LAST, 508 pos, cpy_num); 509 else { 510 /* copy first cpy_num-1 items starting from position 'pos-1' of the SOURCE to the end of the DEST */ 511 leaf_copy_items_entirely(dest_bi, src, FIRST_TO_LAST, 512 pos, cpy_num - 1); 513 514 /* copy part of the item which number is cpy_num+pos-1 to the end of the DEST */ 515 leaf_item_bottle(dest_bi, src, FIRST_TO_LAST, 516 cpy_num + pos - 1, cpy_bytes); 517 } 518 } else { 519 /* copy items to right */ 520 src_nr_item = B_NR_ITEMS(src); 521 if (cpy_num == 1) 522 bytes = cpy_bytes; 523 else 524 bytes = -1; 525 526 /* copy the last item or it part or nothing to the begin of the DEST (i = leaf_copy_boundary_item(DEST,SOURCE,1,bytes)); */ 527 i = leaf_copy_boundary_item(dest_bi, src, LAST_TO_FIRST, bytes); 528 529 cpy_num -= i; 530 if (cpy_num == 0) 531 return i; 532 533 pos = src_nr_item - cpy_num - i; 534 if (cpy_bytes == -1) { 535 /* starting from position 'pos' copy last cpy_num items of SOURCE to begin of DEST */ 536 leaf_copy_items_entirely(dest_bi, src, LAST_TO_FIRST, 537 pos, cpy_num); 538 } else { 539 /* copy last cpy_num-1 items starting from position 'pos+1' of the SOURCE to the begin of the DEST; */ 540 leaf_copy_items_entirely(dest_bi, src, LAST_TO_FIRST, 541 pos + 1, cpy_num - 1); 542 543 /* copy part of the item which number is pos to the begin of the DEST */ 544 leaf_item_bottle(dest_bi, src, LAST_TO_FIRST, pos, 545 cpy_bytes); 546 } 547 } 548 return i; 549 } 550 551 /* there are types of coping: from S[0] to L[0], from S[0] to R[0], 552 from R[0] to L[0]. for each of these we have to define parent and 553 positions of destination and source buffers */ 554 static void leaf_define_dest_src_infos(int shift_mode, struct tree_balance *tb, 555 struct buffer_info *dest_bi, 556 struct buffer_info *src_bi, 557 int *first_last, 558 struct buffer_head *Snew) 559 { 560 memset(dest_bi, 0, sizeof(struct buffer_info)); 561 memset(src_bi, 0, sizeof(struct buffer_info)); 562 563 /* define dest, src, dest parent, dest position */ 564 switch (shift_mode) { 565 case LEAF_FROM_S_TO_L: /* it is used in leaf_shift_left */ 566 src_bi->tb = tb; 567 src_bi->bi_bh = PATH_PLAST_BUFFER(tb->tb_path); 568 src_bi->bi_parent = PATH_H_PPARENT(tb->tb_path, 0); 569 src_bi->bi_position = PATH_H_B_ITEM_ORDER(tb->tb_path, 0); /* src->b_item_order */ 570 dest_bi->tb = tb; 571 dest_bi->bi_bh = tb->L[0]; 572 dest_bi->bi_parent = tb->FL[0]; 573 dest_bi->bi_position = get_left_neighbor_position(tb, 0); 574 *first_last = FIRST_TO_LAST; 575 break; 576 577 case LEAF_FROM_S_TO_R: /* it is used in leaf_shift_right */ 578 src_bi->tb = tb; 579 src_bi->bi_bh = PATH_PLAST_BUFFER(tb->tb_path); 580 src_bi->bi_parent = PATH_H_PPARENT(tb->tb_path, 0); 581 src_bi->bi_position = PATH_H_B_ITEM_ORDER(tb->tb_path, 0); 582 dest_bi->tb = tb; 583 dest_bi->bi_bh = tb->R[0]; 584 dest_bi->bi_parent = tb->FR[0]; 585 dest_bi->bi_position = get_right_neighbor_position(tb, 0); 586 *first_last = LAST_TO_FIRST; 587 break; 588 589 case LEAF_FROM_R_TO_L: /* it is used in balance_leaf_when_delete */ 590 src_bi->tb = tb; 591 src_bi->bi_bh = tb->R[0]; 592 src_bi->bi_parent = tb->FR[0]; 593 src_bi->bi_position = get_right_neighbor_position(tb, 0); 594 dest_bi->tb = tb; 595 dest_bi->bi_bh = tb->L[0]; 596 dest_bi->bi_parent = tb->FL[0]; 597 dest_bi->bi_position = get_left_neighbor_position(tb, 0); 598 *first_last = FIRST_TO_LAST; 599 break; 600 601 case LEAF_FROM_L_TO_R: /* it is used in balance_leaf_when_delete */ 602 src_bi->tb = tb; 603 src_bi->bi_bh = tb->L[0]; 604 src_bi->bi_parent = tb->FL[0]; 605 src_bi->bi_position = get_left_neighbor_position(tb, 0); 606 dest_bi->tb = tb; 607 dest_bi->bi_bh = tb->R[0]; 608 dest_bi->bi_parent = tb->FR[0]; 609 dest_bi->bi_position = get_right_neighbor_position(tb, 0); 610 *first_last = LAST_TO_FIRST; 611 break; 612 613 case LEAF_FROM_S_TO_SNEW: 614 src_bi->tb = tb; 615 src_bi->bi_bh = PATH_PLAST_BUFFER(tb->tb_path); 616 src_bi->bi_parent = PATH_H_PPARENT(tb->tb_path, 0); 617 src_bi->bi_position = PATH_H_B_ITEM_ORDER(tb->tb_path, 0); 618 dest_bi->tb = tb; 619 dest_bi->bi_bh = Snew; 620 dest_bi->bi_parent = NULL; 621 dest_bi->bi_position = 0; 622 *first_last = LAST_TO_FIRST; 623 break; 624 625 default: 626 reiserfs_panic(sb_from_bi(src_bi), "vs-10250", 627 "shift type is unknown (%d)", shift_mode); 628 } 629 RFALSE(!src_bi->bi_bh || !dest_bi->bi_bh, 630 "vs-10260: mode==%d, source (%p) or dest (%p) buffer is initialized incorrectly", 631 shift_mode, src_bi->bi_bh, dest_bi->bi_bh); 632 } 633 634 /* copy mov_num items and mov_bytes of the (mov_num-1)th item to 635 neighbor. Delete them from source */ 636 int leaf_move_items(int shift_mode, struct tree_balance *tb, int mov_num, 637 int mov_bytes, struct buffer_head *Snew) 638 { 639 int ret_value; 640 struct buffer_info dest_bi, src_bi; 641 int first_last; 642 643 leaf_define_dest_src_infos(shift_mode, tb, &dest_bi, &src_bi, 644 &first_last, Snew); 645 646 ret_value = 647 leaf_copy_items(&dest_bi, src_bi.bi_bh, first_last, mov_num, 648 mov_bytes); 649 650 leaf_delete_items(&src_bi, first_last, 651 (first_last == 652 FIRST_TO_LAST) ? 0 : (B_NR_ITEMS(src_bi.bi_bh) - 653 mov_num), mov_num, mov_bytes); 654 655 return ret_value; 656 } 657 658 /* Shift shift_num items (and shift_bytes of last shifted item if shift_bytes != -1) 659 from S[0] to L[0] and replace the delimiting key */ 660 int leaf_shift_left(struct tree_balance *tb, int shift_num, int shift_bytes) 661 { 662 struct buffer_head *S0 = PATH_PLAST_BUFFER(tb->tb_path); 663 int i; 664 665 /* move shift_num (and shift_bytes bytes) items from S[0] to left neighbor L[0] */ 666 i = leaf_move_items(LEAF_FROM_S_TO_L, tb, shift_num, shift_bytes, NULL); 667 668 if (shift_num) { 669 if (B_NR_ITEMS(S0) == 0) { /* number of items in S[0] == 0 */ 670 671 RFALSE(shift_bytes != -1, 672 "vs-10270: S0 is empty now, but shift_bytes != -1 (%d)", 673 shift_bytes); 674 #ifdef CONFIG_REISERFS_CHECK 675 if (tb->tb_mode == M_PASTE || tb->tb_mode == M_INSERT) { 676 print_cur_tb("vs-10275"); 677 reiserfs_panic(tb->tb_sb, "vs-10275", 678 "balance condition corrupted " 679 "(%c)", tb->tb_mode); 680 } 681 #endif 682 683 if (PATH_H_POSITION(tb->tb_path, 1) == 0) 684 replace_key(tb, tb->CFL[0], tb->lkey[0], 685 PATH_H_PPARENT(tb->tb_path, 0), 0); 686 687 } else { 688 /* replace lkey in CFL[0] by 0-th key from S[0]; */ 689 replace_key(tb, tb->CFL[0], tb->lkey[0], S0, 0); 690 691 RFALSE((shift_bytes != -1 && 692 !(is_direntry_le_ih(B_N_PITEM_HEAD(S0, 0)) 693 && !I_ENTRY_COUNT(B_N_PITEM_HEAD(S0, 0)))) && 694 (!op_is_left_mergeable 695 (B_N_PKEY(S0, 0), S0->b_size)), 696 "vs-10280: item must be mergeable"); 697 } 698 } 699 700 return i; 701 } 702 703 /* CLEANING STOPPED HERE */ 704 705 /* Shift shift_num (shift_bytes) items from S[0] to the right neighbor, and replace the delimiting key */ 706 int leaf_shift_right(struct tree_balance *tb, int shift_num, int shift_bytes) 707 { 708 // struct buffer_head * S0 = PATH_PLAST_BUFFER (tb->tb_path); 709 int ret_value; 710 711 /* move shift_num (and shift_bytes) items from S[0] to right neighbor R[0] */ 712 ret_value = 713 leaf_move_items(LEAF_FROM_S_TO_R, tb, shift_num, shift_bytes, NULL); 714 715 /* replace rkey in CFR[0] by the 0-th key from R[0] */ 716 if (shift_num) { 717 replace_key(tb, tb->CFR[0], tb->rkey[0], tb->R[0], 0); 718 719 } 720 721 return ret_value; 722 } 723 724 static void leaf_delete_items_entirely(struct buffer_info *bi, 725 int first, int del_num); 726 /* If del_bytes == -1, starting from position 'first' delete del_num items in whole in buffer CUR. 727 If not. 728 If last_first == 0. Starting from position 'first' delete del_num-1 items in whole. Delete part of body of 729 the first item. Part defined by del_bytes. Don't delete first item header 730 If last_first == 1. Starting from position 'first+1' delete del_num-1 items in whole. Delete part of body of 731 the last item . Part defined by del_bytes. Don't delete last item header. 732 */ 733 void leaf_delete_items(struct buffer_info *cur_bi, int last_first, 734 int first, int del_num, int del_bytes) 735 { 736 struct buffer_head *bh; 737 int item_amount = B_NR_ITEMS(bh = cur_bi->bi_bh); 738 739 RFALSE(!bh, "10155: bh is not defined"); 740 RFALSE(del_num < 0, "10160: del_num can not be < 0. del_num==%d", 741 del_num); 742 RFALSE(first < 0 743 || first + del_num > item_amount, 744 "10165: invalid number of first item to be deleted (%d) or " 745 "no so much items (%d) to delete (only %d)", first, 746 first + del_num, item_amount); 747 748 if (del_num == 0) 749 return; 750 751 if (first == 0 && del_num == item_amount && del_bytes == -1) { 752 make_empty_node(cur_bi); 753 do_balance_mark_leaf_dirty(cur_bi->tb, bh, 0); 754 return; 755 } 756 757 if (del_bytes == -1) 758 /* delete del_num items beginning from item in position first */ 759 leaf_delete_items_entirely(cur_bi, first, del_num); 760 else { 761 if (last_first == FIRST_TO_LAST) { 762 /* delete del_num-1 items beginning from item in position first */ 763 leaf_delete_items_entirely(cur_bi, first, del_num - 1); 764 765 /* delete the part of the first item of the bh 766 do not delete item header 767 */ 768 leaf_cut_from_buffer(cur_bi, 0, 0, del_bytes); 769 } else { 770 struct item_head *ih; 771 int len; 772 773 /* delete del_num-1 items beginning from item in position first+1 */ 774 leaf_delete_items_entirely(cur_bi, first + 1, 775 del_num - 1); 776 777 if (is_direntry_le_ih 778 (ih = B_N_PITEM_HEAD(bh, B_NR_ITEMS(bh) - 1))) 779 /* the last item is directory */ 780 /* len = numbers of directory entries in this item */ 781 len = ih_entry_count(ih); 782 else 783 /* len = body len of item */ 784 len = ih_item_len(ih); 785 786 /* delete the part of the last item of the bh 787 do not delete item header 788 */ 789 leaf_cut_from_buffer(cur_bi, B_NR_ITEMS(bh) - 1, 790 len - del_bytes, del_bytes); 791 } 792 } 793 } 794 795 /* insert item into the leaf node in position before */ 796 void leaf_insert_into_buf(struct buffer_info *bi, int before, 797 struct item_head *inserted_item_ih, 798 const char *inserted_item_body, int zeros_number) 799 { 800 struct buffer_head *bh = bi->bi_bh; 801 int nr, free_space; 802 struct block_head *blkh; 803 struct item_head *ih; 804 int i; 805 int last_loc, unmoved_loc; 806 char *to; 807 808 blkh = B_BLK_HEAD(bh); 809 nr = blkh_nr_item(blkh); 810 free_space = blkh_free_space(blkh); 811 812 /* check free space */ 813 RFALSE(free_space < ih_item_len(inserted_item_ih) + IH_SIZE, 814 "vs-10170: not enough free space in block %z, new item %h", 815 bh, inserted_item_ih); 816 RFALSE(zeros_number > ih_item_len(inserted_item_ih), 817 "vs-10172: zero number == %d, item length == %d", 818 zeros_number, ih_item_len(inserted_item_ih)); 819 820 /* get item new item must be inserted before */ 821 ih = B_N_PITEM_HEAD(bh, before); 822 823 /* prepare space for the body of new item */ 824 last_loc = nr ? ih_location(&(ih[nr - before - 1])) : bh->b_size; 825 unmoved_loc = before ? ih_location(ih - 1) : bh->b_size; 826 827 memmove(bh->b_data + last_loc - ih_item_len(inserted_item_ih), 828 bh->b_data + last_loc, unmoved_loc - last_loc); 829 830 to = bh->b_data + unmoved_loc - ih_item_len(inserted_item_ih); 831 memset(to, 0, zeros_number); 832 to += zeros_number; 833 834 /* copy body to prepared space */ 835 if (inserted_item_body) 836 memmove(to, inserted_item_body, 837 ih_item_len(inserted_item_ih) - zeros_number); 838 else 839 memset(to, '\0', ih_item_len(inserted_item_ih) - zeros_number); 840 841 /* insert item header */ 842 memmove(ih + 1, ih, IH_SIZE * (nr - before)); 843 memmove(ih, inserted_item_ih, IH_SIZE); 844 845 /* change locations */ 846 for (i = before; i < nr + 1; i++) { 847 unmoved_loc -= ih_item_len(&(ih[i - before])); 848 put_ih_location(&(ih[i - before]), unmoved_loc); 849 } 850 851 /* sizes, free space, item number */ 852 set_blkh_nr_item(blkh, blkh_nr_item(blkh) + 1); 853 set_blkh_free_space(blkh, 854 free_space - (IH_SIZE + 855 ih_item_len(inserted_item_ih))); 856 do_balance_mark_leaf_dirty(bi->tb, bh, 1); 857 858 if (bi->bi_parent) { 859 struct disk_child *t_dc; 860 t_dc = B_N_CHILD(bi->bi_parent, bi->bi_position); 861 put_dc_size(t_dc, 862 dc_size(t_dc) + (IH_SIZE + 863 ih_item_len(inserted_item_ih))); 864 do_balance_mark_internal_dirty(bi->tb, bi->bi_parent, 0); 865 } 866 } 867 868 /* paste paste_size bytes to affected_item_num-th item. 869 When item is a directory, this only prepare space for new entries */ 870 void leaf_paste_in_buffer(struct buffer_info *bi, int affected_item_num, 871 int pos_in_item, int paste_size, 872 const char *body, int zeros_number) 873 { 874 struct buffer_head *bh = bi->bi_bh; 875 int nr, free_space; 876 struct block_head *blkh; 877 struct item_head *ih; 878 int i; 879 int last_loc, unmoved_loc; 880 881 blkh = B_BLK_HEAD(bh); 882 nr = blkh_nr_item(blkh); 883 free_space = blkh_free_space(blkh); 884 885 /* check free space */ 886 RFALSE(free_space < paste_size, 887 "vs-10175: not enough free space: needed %d, available %d", 888 paste_size, free_space); 889 890 #ifdef CONFIG_REISERFS_CHECK 891 if (zeros_number > paste_size) { 892 struct super_block *sb = NULL; 893 if (bi && bi->tb) 894 sb = bi->tb->tb_sb; 895 print_cur_tb("10177"); 896 reiserfs_panic(sb, "vs-10177", 897 "zeros_number == %d, paste_size == %d", 898 zeros_number, paste_size); 899 } 900 #endif /* CONFIG_REISERFS_CHECK */ 901 902 /* item to be appended */ 903 ih = B_N_PITEM_HEAD(bh, affected_item_num); 904 905 last_loc = ih_location(&(ih[nr - affected_item_num - 1])); 906 unmoved_loc = affected_item_num ? ih_location(ih - 1) : bh->b_size; 907 908 /* prepare space */ 909 memmove(bh->b_data + last_loc - paste_size, bh->b_data + last_loc, 910 unmoved_loc - last_loc); 911 912 /* change locations */ 913 for (i = affected_item_num; i < nr; i++) 914 put_ih_location(&(ih[i - affected_item_num]), 915 ih_location(&(ih[i - affected_item_num])) - 916 paste_size); 917 918 if (body) { 919 if (!is_direntry_le_ih(ih)) { 920 if (!pos_in_item) { 921 /* shift data to right */ 922 memmove(bh->b_data + ih_location(ih) + 923 paste_size, 924 bh->b_data + ih_location(ih), 925 ih_item_len(ih)); 926 /* paste data in the head of item */ 927 memset(bh->b_data + ih_location(ih), 0, 928 zeros_number); 929 memcpy(bh->b_data + ih_location(ih) + 930 zeros_number, body, 931 paste_size - zeros_number); 932 } else { 933 memset(bh->b_data + unmoved_loc - paste_size, 0, 934 zeros_number); 935 memcpy(bh->b_data + unmoved_loc - paste_size + 936 zeros_number, body, 937 paste_size - zeros_number); 938 } 939 } 940 } else 941 memset(bh->b_data + unmoved_loc - paste_size, '\0', paste_size); 942 943 put_ih_item_len(ih, ih_item_len(ih) + paste_size); 944 945 /* change free space */ 946 set_blkh_free_space(blkh, free_space - paste_size); 947 948 do_balance_mark_leaf_dirty(bi->tb, bh, 0); 949 950 if (bi->bi_parent) { 951 struct disk_child *t_dc = 952 B_N_CHILD(bi->bi_parent, bi->bi_position); 953 put_dc_size(t_dc, dc_size(t_dc) + paste_size); 954 do_balance_mark_internal_dirty(bi->tb, bi->bi_parent, 0); 955 } 956 } 957 958 /* cuts DEL_COUNT entries beginning from FROM-th entry. Directory item 959 does not have free space, so it moves DEHs and remaining records as 960 necessary. Return value is size of removed part of directory item 961 in bytes. */ 962 static int leaf_cut_entries(struct buffer_head *bh, 963 struct item_head *ih, int from, int del_count) 964 { 965 char *item; 966 struct reiserfs_de_head *deh; 967 int prev_record_offset; /* offset of record, that is (from-1)th */ 968 char *prev_record; /* */ 969 int cut_records_len; /* length of all removed records */ 970 int i; 971 972 /* make sure, that item is directory and there are enough entries to 973 remove */ 974 RFALSE(!is_direntry_le_ih(ih), "10180: item is not directory item"); 975 RFALSE(I_ENTRY_COUNT(ih) < from + del_count, 976 "10185: item contains not enough entries: entry_cout = %d, from = %d, to delete = %d", 977 I_ENTRY_COUNT(ih), from, del_count); 978 979 if (del_count == 0) 980 return 0; 981 982 /* first byte of item */ 983 item = bh->b_data + ih_location(ih); 984 985 /* entry head array */ 986 deh = B_I_DEH(bh, ih); 987 988 /* first byte of remaining entries, those are BEFORE cut entries 989 (prev_record) and length of all removed records (cut_records_len) */ 990 prev_record_offset = 991 (from ? deh_location(&(deh[from - 1])) : ih_item_len(ih)); 992 cut_records_len = prev_record_offset /*from_record */ - 993 deh_location(&(deh[from + del_count - 1])); 994 prev_record = item + prev_record_offset; 995 996 /* adjust locations of remaining entries */ 997 for (i = I_ENTRY_COUNT(ih) - 1; i > from + del_count - 1; i--) 998 put_deh_location(&(deh[i]), 999 deh_location(&deh[i]) - 1000 (DEH_SIZE * del_count)); 1001 1002 for (i = 0; i < from; i++) 1003 put_deh_location(&(deh[i]), 1004 deh_location(&deh[i]) - (DEH_SIZE * del_count + 1005 cut_records_len)); 1006 1007 put_ih_entry_count(ih, ih_entry_count(ih) - del_count); 1008 1009 /* shift entry head array and entries those are AFTER removed entries */ 1010 memmove((char *)(deh + from), 1011 deh + from + del_count, 1012 prev_record - cut_records_len - (char *)(deh + from + 1013 del_count)); 1014 1015 /* shift records, those are BEFORE removed entries */ 1016 memmove(prev_record - cut_records_len - DEH_SIZE * del_count, 1017 prev_record, item + ih_item_len(ih) - prev_record); 1018 1019 return DEH_SIZE * del_count + cut_records_len; 1020 } 1021 1022 /* when cut item is part of regular file 1023 pos_in_item - first byte that must be cut 1024 cut_size - number of bytes to be cut beginning from pos_in_item 1025 1026 when cut item is part of directory 1027 pos_in_item - number of first deleted entry 1028 cut_size - count of deleted entries 1029 */ 1030 void leaf_cut_from_buffer(struct buffer_info *bi, int cut_item_num, 1031 int pos_in_item, int cut_size) 1032 { 1033 int nr; 1034 struct buffer_head *bh = bi->bi_bh; 1035 struct block_head *blkh; 1036 struct item_head *ih; 1037 int last_loc, unmoved_loc; 1038 int i; 1039 1040 blkh = B_BLK_HEAD(bh); 1041 nr = blkh_nr_item(blkh); 1042 1043 /* item head of truncated item */ 1044 ih = B_N_PITEM_HEAD(bh, cut_item_num); 1045 1046 if (is_direntry_le_ih(ih)) { 1047 /* first cut entry () */ 1048 cut_size = leaf_cut_entries(bh, ih, pos_in_item, cut_size); 1049 if (pos_in_item == 0) { 1050 /* change key */ 1051 RFALSE(cut_item_num, 1052 "when 0-th enrty of item is cut, that item must be first in the node, not %d-th", 1053 cut_item_num); 1054 /* change item key by key of first entry in the item */ 1055 set_le_ih_k_offset(ih, deh_offset(B_I_DEH(bh, ih))); 1056 /*memcpy (&ih->ih_key.k_offset, &(B_I_DEH (bh, ih)->deh_offset), SHORT_KEY_SIZE); */ 1057 } 1058 } else { 1059 /* item is direct or indirect */ 1060 RFALSE(is_statdata_le_ih(ih), "10195: item is stat data"); 1061 RFALSE(pos_in_item && pos_in_item + cut_size != ih_item_len(ih), 1062 "10200: invalid offset (%lu) or trunc_size (%lu) or ih_item_len (%lu)", 1063 (long unsigned)pos_in_item, (long unsigned)cut_size, 1064 (long unsigned)ih_item_len(ih)); 1065 1066 /* shift item body to left if cut is from the head of item */ 1067 if (pos_in_item == 0) { 1068 memmove(bh->b_data + ih_location(ih), 1069 bh->b_data + ih_location(ih) + cut_size, 1070 ih_item_len(ih) - cut_size); 1071 1072 /* change key of item */ 1073 if (is_direct_le_ih(ih)) 1074 set_le_ih_k_offset(ih, 1075 le_ih_k_offset(ih) + 1076 cut_size); 1077 else { 1078 set_le_ih_k_offset(ih, 1079 le_ih_k_offset(ih) + 1080 (cut_size / UNFM_P_SIZE) * 1081 bh->b_size); 1082 RFALSE(ih_item_len(ih) == cut_size 1083 && get_ih_free_space(ih), 1084 "10205: invalid ih_free_space (%h)", ih); 1085 } 1086 } 1087 } 1088 1089 /* location of the last item */ 1090 last_loc = ih_location(&(ih[nr - cut_item_num - 1])); 1091 1092 /* location of the item, which is remaining at the same place */ 1093 unmoved_loc = cut_item_num ? ih_location(ih - 1) : bh->b_size; 1094 1095 /* shift */ 1096 memmove(bh->b_data + last_loc + cut_size, bh->b_data + last_loc, 1097 unmoved_loc - last_loc - cut_size); 1098 1099 /* change item length */ 1100 put_ih_item_len(ih, ih_item_len(ih) - cut_size); 1101 1102 if (is_indirect_le_ih(ih)) { 1103 if (pos_in_item) 1104 set_ih_free_space(ih, 0); 1105 } 1106 1107 /* change locations */ 1108 for (i = cut_item_num; i < nr; i++) 1109 put_ih_location(&(ih[i - cut_item_num]), 1110 ih_location(&ih[i - cut_item_num]) + cut_size); 1111 1112 /* size, free space */ 1113 set_blkh_free_space(blkh, blkh_free_space(blkh) + cut_size); 1114 1115 do_balance_mark_leaf_dirty(bi->tb, bh, 0); 1116 1117 if (bi->bi_parent) { 1118 struct disk_child *t_dc; 1119 t_dc = B_N_CHILD(bi->bi_parent, bi->bi_position); 1120 put_dc_size(t_dc, dc_size(t_dc) - cut_size); 1121 do_balance_mark_internal_dirty(bi->tb, bi->bi_parent, 0); 1122 } 1123 } 1124 1125 /* delete del_num items from buffer starting from the first'th item */ 1126 static void leaf_delete_items_entirely(struct buffer_info *bi, 1127 int first, int del_num) 1128 { 1129 struct buffer_head *bh = bi->bi_bh; 1130 int nr; 1131 int i, j; 1132 int last_loc, last_removed_loc; 1133 struct block_head *blkh; 1134 struct item_head *ih; 1135 1136 RFALSE(bh == NULL, "10210: buffer is 0"); 1137 RFALSE(del_num < 0, "10215: del_num less than 0 (%d)", del_num); 1138 1139 if (del_num == 0) 1140 return; 1141 1142 blkh = B_BLK_HEAD(bh); 1143 nr = blkh_nr_item(blkh); 1144 1145 RFALSE(first < 0 || first + del_num > nr, 1146 "10220: first=%d, number=%d, there is %d items", first, del_num, 1147 nr); 1148 1149 if (first == 0 && del_num == nr) { 1150 /* this does not work */ 1151 make_empty_node(bi); 1152 1153 do_balance_mark_leaf_dirty(bi->tb, bh, 0); 1154 return; 1155 } 1156 1157 ih = B_N_PITEM_HEAD(bh, first); 1158 1159 /* location of unmovable item */ 1160 j = (first == 0) ? bh->b_size : ih_location(ih - 1); 1161 1162 /* delete items */ 1163 last_loc = ih_location(&(ih[nr - 1 - first])); 1164 last_removed_loc = ih_location(&(ih[del_num - 1])); 1165 1166 memmove(bh->b_data + last_loc + j - last_removed_loc, 1167 bh->b_data + last_loc, last_removed_loc - last_loc); 1168 1169 /* delete item headers */ 1170 memmove(ih, ih + del_num, (nr - first - del_num) * IH_SIZE); 1171 1172 /* change item location */ 1173 for (i = first; i < nr - del_num; i++) 1174 put_ih_location(&(ih[i - first]), 1175 ih_location(&(ih[i - first])) + (j - 1176 last_removed_loc)); 1177 1178 /* sizes, item number */ 1179 set_blkh_nr_item(blkh, blkh_nr_item(blkh) - del_num); 1180 set_blkh_free_space(blkh, 1181 blkh_free_space(blkh) + (j - last_removed_loc + 1182 IH_SIZE * del_num)); 1183 1184 do_balance_mark_leaf_dirty(bi->tb, bh, 0); 1185 1186 if (bi->bi_parent) { 1187 struct disk_child *t_dc = 1188 B_N_CHILD(bi->bi_parent, bi->bi_position); 1189 put_dc_size(t_dc, 1190 dc_size(t_dc) - (j - last_removed_loc + 1191 IH_SIZE * del_num)); 1192 do_balance_mark_internal_dirty(bi->tb, bi->bi_parent, 0); 1193 } 1194 } 1195 1196 /* paste new_entry_count entries (new_dehs, records) into position before to item_num-th item */ 1197 void leaf_paste_entries(struct buffer_info *bi, 1198 int item_num, 1199 int before, 1200 int new_entry_count, 1201 struct reiserfs_de_head *new_dehs, 1202 const char *records, int paste_size) 1203 { 1204 struct item_head *ih; 1205 char *item; 1206 struct reiserfs_de_head *deh; 1207 char *insert_point; 1208 int i, old_entry_num; 1209 struct buffer_head *bh = bi->bi_bh; 1210 1211 if (new_entry_count == 0) 1212 return; 1213 1214 ih = B_N_PITEM_HEAD(bh, item_num); 1215 1216 /* make sure, that item is directory, and there are enough records in it */ 1217 RFALSE(!is_direntry_le_ih(ih), "10225: item is not directory item"); 1218 RFALSE(I_ENTRY_COUNT(ih) < before, 1219 "10230: there are no entry we paste entries before. entry_count = %d, before = %d", 1220 I_ENTRY_COUNT(ih), before); 1221 1222 /* first byte of dest item */ 1223 item = bh->b_data + ih_location(ih); 1224 1225 /* entry head array */ 1226 deh = B_I_DEH(bh, ih); 1227 1228 /* new records will be pasted at this point */ 1229 insert_point = 1230 item + 1231 (before ? deh_location(&(deh[before - 1])) 1232 : (ih_item_len(ih) - paste_size)); 1233 1234 /* adjust locations of records that will be AFTER new records */ 1235 for (i = I_ENTRY_COUNT(ih) - 1; i >= before; i--) 1236 put_deh_location(&(deh[i]), 1237 deh_location(&(deh[i])) + 1238 (DEH_SIZE * new_entry_count)); 1239 1240 /* adjust locations of records that will be BEFORE new records */ 1241 for (i = 0; i < before; i++) 1242 put_deh_location(&(deh[i]), 1243 deh_location(&(deh[i])) + paste_size); 1244 1245 old_entry_num = I_ENTRY_COUNT(ih); 1246 put_ih_entry_count(ih, ih_entry_count(ih) + new_entry_count); 1247 1248 /* prepare space for pasted records */ 1249 memmove(insert_point + paste_size, insert_point, 1250 item + (ih_item_len(ih) - paste_size) - insert_point); 1251 1252 /* copy new records */ 1253 memcpy(insert_point + DEH_SIZE * new_entry_count, records, 1254 paste_size - DEH_SIZE * new_entry_count); 1255 1256 /* prepare space for new entry heads */ 1257 deh += before; 1258 memmove((char *)(deh + new_entry_count), deh, 1259 insert_point - (char *)deh); 1260 1261 /* copy new entry heads */ 1262 deh = (struct reiserfs_de_head *)((char *)deh); 1263 memcpy(deh, new_dehs, DEH_SIZE * new_entry_count); 1264 1265 /* set locations of new records */ 1266 for (i = 0; i < new_entry_count; i++) { 1267 put_deh_location(&(deh[i]), 1268 deh_location(&(deh[i])) + 1269 (-deh_location 1270 (&(new_dehs[new_entry_count - 1])) + 1271 insert_point + DEH_SIZE * new_entry_count - 1272 item)); 1273 } 1274 1275 /* change item key if necessary (when we paste before 0-th entry */ 1276 if (!before) { 1277 set_le_ih_k_offset(ih, deh_offset(new_dehs)); 1278 /* memcpy (&ih->ih_key.k_offset, 1279 &new_dehs->deh_offset, SHORT_KEY_SIZE);*/ 1280 } 1281 #ifdef CONFIG_REISERFS_CHECK 1282 { 1283 int prev, next; 1284 /* check record locations */ 1285 deh = B_I_DEH(bh, ih); 1286 for (i = 0; i < I_ENTRY_COUNT(ih); i++) { 1287 next = 1288 (i < 1289 I_ENTRY_COUNT(ih) - 1290 1) ? deh_location(&(deh[i + 1])) : 0; 1291 prev = (i != 0) ? deh_location(&(deh[i - 1])) : 0; 1292 1293 if (prev && prev <= deh_location(&(deh[i]))) 1294 reiserfs_error(sb_from_bi(bi), "vs-10240", 1295 "directory item (%h) " 1296 "corrupted (prev %a, " 1297 "cur(%d) %a)", 1298 ih, deh + i - 1, i, deh + i); 1299 if (next && next >= deh_location(&(deh[i]))) 1300 reiserfs_error(sb_from_bi(bi), "vs-10250", 1301 "directory item (%h) " 1302 "corrupted (cur(%d) %a, " 1303 "next %a)", 1304 ih, i, deh + i, deh + i + 1); 1305 } 1306 } 1307 #endif 1308 1309 } 1310