aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--fs/reiserfs/do_balan.c361
1 files changed, 222 insertions, 139 deletions
diff --git a/fs/reiserfs/do_balan.c b/fs/reiserfs/do_balan.c
index cca685daf26d..843c4023ad36 100644
--- a/fs/reiserfs/do_balan.c
+++ b/fs/reiserfs/do_balan.c
@@ -355,164 +355,247 @@ static void balance_leaf_insert_left(struct tree_balance *tb,
355 } 355 }
356} 356}
357 357
358static void balance_leaf_paste_left(struct tree_balance *tb, 358static void balance_leaf_paste_left_shift_dirent(struct tree_balance *tb,
359 struct item_head *ih, const char *body) 359 struct item_head *ih,
360 const char *body)
360{ 361{
361 struct buffer_head *tbS0 = PATH_PLAST_BUFFER(tb->tb_path); 362 int n = B_NR_ITEMS(tb->L[0]);
362 int ret_val;
363 struct buffer_info bi; 363 struct buffer_info bi;
364
365 RFALSE(tb->zeroes_num,
366 "PAP-12090: invalid parameter in case of a directory");
367
368 /* directory item */
369 if (tb->lbytes > tb->pos_in_item) {
370 /* new directory entry falls into L[0] */
371 struct item_head *pasted;
372 int ret, l_pos_in_item = tb->pos_in_item;
373
374 /*
375 * Shift lnum[0] - 1 items in whole.
376 * Shift lbytes - 1 entries from given directory item
377 */
378 ret = leaf_shift_left(tb, tb->lnum[0], tb->lbytes - 1);
379 if (ret && !tb->item_pos) {
380 pasted = item_head(tb->L[0], B_NR_ITEMS(tb->L[0]) - 1);
381 l_pos_in_item += ih_entry_count(pasted) -
382 (tb->lbytes - 1);
383 }
384
385 /* Append given directory entry to directory item */
386 buffer_info_init_left(tb, &bi);
387 leaf_paste_in_buffer(&bi, n + tb->item_pos - ret,
388 l_pos_in_item, tb->insert_size[0],
389 body, tb->zeroes_num);
390
391 /*
392 * previous string prepared space for pasting new entry,
393 * following string pastes this entry
394 */
395
396 /*
397 * when we have merge directory item, pos_in_item
398 * has been changed too
399 */
400
401 /* paste new directory entry. 1 is entry number */
402 leaf_paste_entries(&bi, n + tb->item_pos - ret,
403 l_pos_in_item, 1,
404 (struct reiserfs_de_head *) body,
405 body + DEH_SIZE, tb->insert_size[0]);
406 tb->insert_size[0] = 0;
407 } else {
408 /* new directory item doesn't fall into L[0] */
409 /*
410 * Shift lnum[0]-1 items in whole. Shift lbytes
411 * directory entries from directory item number lnum[0]
412 */
413 leaf_shift_left(tb, tb->lnum[0], tb->lbytes);
414 }
415
416 /* Calculate new position to append in item body */
417 tb->pos_in_item -= tb->lbytes;
418}
419
420static void balance_leaf_paste_left_shift(struct tree_balance *tb,
421 struct item_head *ih,
422 const char *body)
423{
424 struct buffer_head *tbS0 = PATH_PLAST_BUFFER(tb->tb_path);
364 int n = B_NR_ITEMS(tb->L[0]); 425 int n = B_NR_ITEMS(tb->L[0]);
426 struct buffer_info bi;
365 427
366 if (tb->item_pos == tb->lnum[0] - 1 && tb->lbytes != -1) { 428 if (is_direntry_le_ih(item_head(tbS0, tb->item_pos))) {
367 /* we must shift the part of the appended item */ 429 balance_leaf_paste_left_shift_dirent(tb, ih, body);
368 if (is_direntry_le_ih(item_head(tbS0, tb->item_pos))) { 430 return;
431 }
369 432
370 RFALSE(tb->zeroes_num, 433 RFALSE(tb->lbytes <= 0,
371 "PAP-12090: invalid parameter in case of a directory"); 434 "PAP-12095: there is nothing to shift to L[0]. "
372 /* directory item */ 435 "lbytes=%d", tb->lbytes);
373 if (tb->lbytes > tb->pos_in_item) { 436 RFALSE(tb->pos_in_item != ih_item_len(item_head(tbS0, tb->item_pos)),
374 /* new directory entry falls into L[0] */ 437 "PAP-12100: incorrect position to paste: "
375 struct item_head *pasted; 438 "item_len=%d, pos_in_item=%d",
376 int l_pos_in_item = tb->pos_in_item; 439 ih_item_len(item_head(tbS0, tb->item_pos)), tb->pos_in_item);
377
378 /* Shift lnum[0] - 1 items in whole. Shift lbytes - 1 entries from given directory item */
379 ret_val = leaf_shift_left(tb, tb->lnum[0], tb->lbytes-1);
380 if (ret_val && !tb->item_pos) {
381 pasted = item_head(tb->L[0], B_NR_ITEMS(tb->L[0]) - 1);
382 l_pos_in_item += ih_entry_count(pasted) - (tb->lbytes -1);
383 }
384 440
385 /* Append given directory entry to directory item */ 441 /* appended item will be in L[0] in whole */
386 buffer_info_init_left(tb, &bi); 442 if (tb->lbytes >= tb->pos_in_item) {
387 leaf_paste_in_buffer(&bi, n + tb->item_pos - ret_val, l_pos_in_item, tb->insert_size[0], body, tb->zeroes_num); 443 struct item_head *tbS0_pos_ih, *tbL0_ih;
444 struct item_head *tbS0_0_ih;
445 struct reiserfs_key *left_delim_key;
446 int ret, l_n, version, temp_l;
388 447
389 /* previous string prepared space for pasting new entry, following string pastes this entry */ 448 tbS0_pos_ih = item_head(tbS0, tb->item_pos);
449 tbS0_0_ih = item_head(tbS0, 0);
390 450
391 /* when we have merge directory item, pos_in_item has been changed too */ 451 /*
452 * this bytes number must be appended
453 * to the last item of L[h]
454 */
455 l_n = tb->lbytes - tb->pos_in_item;
392 456
393 /* paste new directory entry. 1 is entry number */ 457 /* Calculate new insert_size[0] */
394 leaf_paste_entries(&bi, n + tb->item_pos - ret_val, l_pos_in_item, 458 tb->insert_size[0] -= l_n;
395 1, (struct reiserfs_de_head *) body,
396 body + DEH_SIZE, tb->insert_size[0]);
397 tb->insert_size[0] = 0;
398 } else {
399 /* new directory item doesn't fall into L[0] */
400 /* Shift lnum[0]-1 items in whole. Shift lbytes directory entries from directory item number lnum[0] */
401 leaf_shift_left(tb, tb->lnum[0], tb->lbytes);
402 }
403 /* Calculate new position to append in item body */
404 tb->pos_in_item -= tb->lbytes;
405 } else {
406 /* regular object */
407 RFALSE(tb->lbytes <= 0, "PAP-12095: there is nothing to shift to L[0]. lbytes=%d", tb->lbytes);
408 RFALSE(tb->pos_in_item != ih_item_len(item_head(tbS0, tb->item_pos)),
409 "PAP-12100: incorrect position to paste: item_len=%d, pos_in_item=%d",
410 ih_item_len(item_head(tbS0, tb->item_pos)), tb->pos_in_item);
411
412 if (tb->lbytes >= tb->pos_in_item) {
413 /* appended item will be in L[0] in whole */
414 int l_n;
415
416 /* this bytes number must be appended to the last item of L[h] */
417 l_n = tb->lbytes - tb->pos_in_item;
418
419 /* Calculate new insert_size[0] */
420 tb->insert_size[0] -= l_n;
421
422 RFALSE(tb->insert_size[0] <= 0,
423 "PAP-12105: there is nothing to paste into L[0]. insert_size=%d",
424 tb->insert_size[0]);
425 ret_val = leaf_shift_left(tb, tb->lnum[0], ih_item_len
426 (item_head(tbS0, tb->item_pos)));
427 /* Append to body of item in L[0] */
428 buffer_info_init_left(tb, &bi);
429 leaf_paste_in_buffer
430 (&bi, n + tb->item_pos - ret_val, ih_item_len
431 (item_head(tb->L[0], n + tb->item_pos - ret_val)),
432 l_n, body,
433 tb->zeroes_num > l_n ? l_n : tb->zeroes_num);
434 /* 0-th item in S0 can be only of DIRECT type when l_n != 0 */
435 {
436 int version;
437 int temp_l = l_n;
438
439 RFALSE(ih_item_len(item_head(tbS0, 0)),
440 "PAP-12106: item length must be 0");
441 RFALSE(comp_short_le_keys(leaf_key(tbS0, 0), leaf_key
442 (tb->L[0], n + tb->item_pos - ret_val)),
443 "PAP-12107: items must be of the same file");
444 if (is_indirect_le_ih(item_head(tb->L[0], n + tb->item_pos - ret_val))) {
445 temp_l = l_n << (tb->tb_sb-> s_blocksize_bits - UNFM_P_SHIFT);
446 }
447 /* update key of first item in S0 */
448 version = ih_version(item_head(tbS0, 0));
449 set_le_key_k_offset(version, leaf_key(tbS0, 0),
450 le_key_k_offset(version,leaf_key(tbS0, 0)) + temp_l);
451 /* update left delimiting key */
452 set_le_key_k_offset(version, internal_key(tb->CFL[0], tb->lkey[0]),
453 le_key_k_offset(version, internal_key(tb->CFL[0], tb->lkey[0])) + temp_l);
454 }
455 459
456 /* Calculate new body, position in item and insert_size[0] */ 460 RFALSE(tb->insert_size[0] <= 0,
457 if (l_n > tb->zeroes_num) { 461 "PAP-12105: there is nothing to paste into "
458 body += (l_n - tb->zeroes_num); 462 "L[0]. insert_size=%d", tb->insert_size[0]);
459 tb->zeroes_num = 0;
460 } else
461 tb->zeroes_num -= l_n;
462 tb->pos_in_item = 0;
463 463
464 RFALSE(comp_short_le_keys(leaf_key(tbS0, 0), leaf_key(tb->L[0], B_NR_ITEMS(tb->L[0]) - 1)) 464 ret = leaf_shift_left(tb, tb->lnum[0],
465 || !op_is_left_mergeable(leaf_key(tbS0, 0), tbS0->b_size) 465 ih_item_len(tbS0_pos_ih));
466 || !op_is_left_mergeable(internal_key(tb->CFL[0], tb->lkey[0]), tbS0->b_size),
467 "PAP-12120: item must be merge-able with left neighboring item");
468 } else { /* only part of the appended item will be in L[0] */
469 466
470 /* Calculate position in item for append in S[0] */ 467 tbL0_ih = item_head(tb->L[0], n + tb->item_pos - ret);
471 tb->pos_in_item -= tb->lbytes;
472 468
473 RFALSE(tb->pos_in_item <= 0, "PAP-12125: no place for paste. pos_in_item=%d", tb->pos_in_item); 469 /* Append to body of item in L[0] */
470 buffer_info_init_left(tb, &bi);
471 leaf_paste_in_buffer(&bi, n + tb->item_pos - ret,
472 ih_item_len(tbL0_ih), l_n, body,
473 min_t(int, l_n, tb->zeroes_num));
474 474
475 /* Shift lnum[0] - 1 items in whole. Shift lbytes - 1 byte from item number lnum[0] */ 475 /*
476 leaf_shift_left(tb, tb->lnum[0], tb->lbytes); 476 * 0-th item in S0 can be only of DIRECT type
477 } 477 * when l_n != 0
478 } 478 */
479 } else { /* appended item will be in L[0] in whole */ 479 temp_l = l_n;
480 480
481 struct item_head *pasted; 481 RFALSE(ih_item_len(tbS0_0_ih),
482 "PAP-12106: item length must be 0");
483 RFALSE(comp_short_le_keys(&tbS0_0_ih->ih_key,
484 leaf_key(tb->L[0], n + tb->item_pos - ret)),
485 "PAP-12107: items must be of the same file");
482 486
483 if (!tb->item_pos && op_is_left_mergeable(leaf_key(tbS0, 0), tbS0->b_size)) { /* if we paste into first item of S[0] and it is left mergable */ 487 if (is_indirect_le_ih(tbL0_ih)) {
484 /* then increment pos_in_item by the size of the last item in L[0] */ 488 int shift = tb->tb_sb->s_blocksize_bits - UNFM_P_SHIFT;
485 pasted = item_head(tb->L[0], n - 1); 489 temp_l = l_n << shift;
486 if (is_direntry_le_ih(pasted)) 490 }
487 tb->pos_in_item += ih_entry_count(pasted); 491 /* update key of first item in S0 */
488 else 492 version = ih_version(tbS0_0_ih);
489 tb->pos_in_item += ih_item_len(pasted); 493 add_le_key_k_offset(version, &tbS0_0_ih->ih_key, temp_l);
490 }
491 494
492 /* Shift lnum[0] - 1 items in whole. Shift lbytes - 1 byte from item number lnum[0] */ 495 /* update left delimiting key */
493 ret_val = leaf_shift_left(tb, tb->lnum[0], tb->lbytes); 496 left_delim_key = internal_key(tb->CFL[0], tb->lkey[0]);
494 /* Append to body of item in L[0] */ 497 add_le_key_k_offset(version, left_delim_key, temp_l);
495 buffer_info_init_left(tb, &bi);
496 leaf_paste_in_buffer(&bi, n + tb->item_pos - ret_val,
497 tb->pos_in_item,
498 tb->insert_size[0],
499 body, tb->zeroes_num);
500 498
501 /* if appended item is directory, paste entry */ 499 /*
502 pasted = item_head(tb->L[0], n + tb->item_pos - ret_val); 500 * Calculate new body, position in item and
503 if (is_direntry_le_ih(pasted)) 501 * insert_size[0]
504 leaf_paste_entries(&bi, n + tb->item_pos - ret_val, 502 */
505 tb->pos_in_item, 1, 503 if (l_n > tb->zeroes_num) {
506 (struct reiserfs_de_head *) body, 504 body += (l_n - tb->zeroes_num);
507 body + DEH_SIZE, 505 tb->zeroes_num = 0;
508 tb->insert_size[0]); 506 } else
509 /* if appended item is indirect item, put unformatted node into un list */ 507 tb->zeroes_num -= l_n;
510 if (is_indirect_le_ih(pasted)) 508 tb->pos_in_item = 0;
511 set_ih_free_space(pasted, 0); 509
512 tb->insert_size[0] = 0; 510 RFALSE(comp_short_le_keys(&tbS0_0_ih->ih_key,
513 tb->zeroes_num = 0; 511 leaf_key(tb->L[0],
514 } 512 B_NR_ITEMS(tb->L[0]) - 1)) ||
513 !op_is_left_mergeable(leaf_key(tbS0, 0), tbS0->b_size) ||
514 !op_is_left_mergeable(left_delim_key, tbS0->b_size),
515 "PAP-12120: item must be merge-able with left "
516 "neighboring item");
517 } else {
518 /* only part of the appended item will be in L[0] */
519
520 /* Calculate position in item for append in S[0] */
521 tb->pos_in_item -= tb->lbytes;
515 522
523 RFALSE(tb->pos_in_item <= 0,
524 "PAP-12125: no place for paste. pos_in_item=%d",
525 tb->pos_in_item);
526
527 /*
528 * Shift lnum[0] - 1 items in whole.
529 * Shift lbytes - 1 byte from item number lnum[0]
530 */
531 leaf_shift_left(tb, tb->lnum[0], tb->lbytes);
532 }
533}
534
535
536/* appended item will be in L[0] in whole */
537static void balance_leaf_paste_left_whole(struct tree_balance *tb,
538 struct item_head *ih,
539 const char *body)
540{
541 struct buffer_head *tbS0 = PATH_PLAST_BUFFER(tb->tb_path);
542 int n = B_NR_ITEMS(tb->L[0]);
543 struct buffer_info bi;
544 struct item_head *pasted;
545 int ret;
546
547 /* if we paste into first item of S[0] and it is left mergable */
548 if (!tb->item_pos &&
549 op_is_left_mergeable(leaf_key(tbS0, 0), tbS0->b_size)) {
550 /*
551 * then increment pos_in_item by the size of the
552 * last item in L[0]
553 */
554 pasted = item_head(tb->L[0], n - 1);
555 if (is_direntry_le_ih(pasted))
556 tb->pos_in_item += ih_entry_count(pasted);
557 else
558 tb->pos_in_item += ih_item_len(pasted);
559 }
560
561 /*
562 * Shift lnum[0] - 1 items in whole.
563 * Shift lbytes - 1 byte from item number lnum[0]
564 */
565 ret = leaf_shift_left(tb, tb->lnum[0], tb->lbytes);
566
567 /* Append to body of item in L[0] */
568 buffer_info_init_left(tb, &bi);
569 leaf_paste_in_buffer(&bi, n + tb->item_pos - ret, tb->pos_in_item,
570 tb->insert_size[0], body, tb->zeroes_num);
571
572 /* if appended item is directory, paste entry */
573 pasted = item_head(tb->L[0], n + tb->item_pos - ret);
574 if (is_direntry_le_ih(pasted))
575 leaf_paste_entries(&bi, n + tb->item_pos - ret,
576 tb->pos_in_item, 1,
577 (struct reiserfs_de_head *)body,
578 body + DEH_SIZE, tb->insert_size[0]);
579
580 /*
581 * if appended item is indirect item, put unformatted node
582 * into un list
583 */
584 if (is_indirect_le_ih(pasted))
585 set_ih_free_space(pasted, 0);
586
587 tb->insert_size[0] = 0;
588 tb->zeroes_num = 0;
589}
590
591static void balance_leaf_paste_left(struct tree_balance *tb,
592 struct item_head *ih, const char *body)
593{
594 /* we must shift the part of the appended item */
595 if (tb->item_pos == tb->lnum[0] - 1 && tb->lbytes != -1)
596 balance_leaf_paste_left_shift(tb, ih, body);
597 else
598 balance_leaf_paste_left_whole(tb, ih, body);
516} 599}
517 600
518/* Shift lnum[0] items from S[0] to the left neighbor L[0] */ 601/* Shift lnum[0] items from S[0] to the left neighbor L[0] */
generated by cgit v1.2.2 (git 2.25.0) at 2025-12-28 11:21:05 -0500