1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18#include <asm/uaccess.h>
19#include <linux/time.h>
20#include <linux/reiserfs_fs.h>
21#include <linux/buffer_head.h>
22#include <linux/kernel.h>
23
24#ifdef CONFIG_REISERFS_CHECK
25
26struct tree_balance *cur_tb = NULL;
27
28
29
30#endif
31
32static inline void buffer_info_init_left(struct tree_balance *tb,
33 struct buffer_info *bi)
34{
35 bi->tb = tb;
36 bi->bi_bh = tb->L[0];
37 bi->bi_parent = tb->FL[0];
38 bi->bi_position = get_left_neighbor_position(tb, 0);
39}
40
41static inline void buffer_info_init_right(struct tree_balance *tb,
42 struct buffer_info *bi)
43{
44 bi->tb = tb;
45 bi->bi_bh = tb->R[0];
46 bi->bi_parent = tb->FR[0];
47 bi->bi_position = get_right_neighbor_position(tb, 0);
48}
49
50static inline void buffer_info_init_tbS0(struct tree_balance *tb,
51 struct buffer_info *bi)
52{
53 bi->tb = tb;
54 bi->bi_bh = PATH_PLAST_BUFFER(tb->tb_path);
55 bi->bi_parent = PATH_H_PPARENT(tb->tb_path, 0);
56 bi->bi_position = PATH_H_POSITION(tb->tb_path, 1);
57}
58
59static inline void buffer_info_init_bh(struct tree_balance *tb,
60 struct buffer_info *bi,
61 struct buffer_head *bh)
62{
63 bi->tb = tb;
64 bi->bi_bh = bh;
65 bi->bi_parent = NULL;
66 bi->bi_position = 0;
67}
68
69inline void do_balance_mark_leaf_dirty(struct tree_balance *tb,
70 struct buffer_head *bh, int flag)
71{
72 journal_mark_dirty(tb->transaction_handle,
73 tb->transaction_handle->t_super, bh);
74}
75
76#define do_balance_mark_internal_dirty do_balance_mark_leaf_dirty
77#define do_balance_mark_sb_dirty do_balance_mark_leaf_dirty
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109static int balance_leaf_when_delete(struct tree_balance *tb, int flag)
110{
111 struct buffer_head *tbS0 = PATH_PLAST_BUFFER(tb->tb_path);
112 int item_pos = PATH_LAST_POSITION(tb->tb_path);
113 int pos_in_item = tb->tb_path->pos_in_item;
114 struct buffer_info bi;
115 int n;
116 struct item_head *ih;
117
118 RFALSE(tb->FR[0] && B_LEVEL(tb->FR[0]) != DISK_LEAF_NODE_LEVEL + 1,
119 "vs- 12000: level: wrong FR %z", tb->FR[0]);
120 RFALSE(tb->blknum[0] > 1,
121 "PAP-12005: tb->blknum == %d, can not be > 1", tb->blknum[0]);
122 RFALSE(!tb->blknum[0] && !PATH_H_PPARENT(tb->tb_path, 0),
123 "PAP-12010: tree can not be empty");
124
125 ih = B_N_PITEM_HEAD(tbS0, item_pos);
126 buffer_info_init_tbS0(tb, &bi);
127
128
129
130 switch (flag) {
131 case M_DELETE:
132
133 RFALSE(ih_item_len(ih) + IH_SIZE != -tb->insert_size[0],
134 "vs-12013: mode Delete, insert size %d, ih to be deleted %h",
135 -tb->insert_size[0], ih);
136
137 leaf_delete_items(&bi, 0, item_pos, 1, -1);
138
139 if (!item_pos && tb->CFL[0]) {
140 if (B_NR_ITEMS(tbS0)) {
141 replace_key(tb, tb->CFL[0], tb->lkey[0], tbS0,
142 0);
143 } else {
144 if (!PATH_H_POSITION(tb->tb_path, 1))
145 replace_key(tb, tb->CFL[0], tb->lkey[0],
146 PATH_H_PPARENT(tb->tb_path,
147 0), 0);
148 }
149 }
150
151 RFALSE(!item_pos && !tb->CFL[0],
152 "PAP-12020: tb->CFL[0]==%p, tb->L[0]==%p", tb->CFL[0],
153 tb->L[0]);
154
155 break;
156
157 case M_CUT:{
158 if (is_direntry_le_ih(ih)) {
159
160
161
162 tb->insert_size[0] = -1;
163 leaf_cut_from_buffer(&bi, item_pos, pos_in_item,
164 -tb->insert_size[0]);
165
166 RFALSE(!item_pos && !pos_in_item && !tb->CFL[0],
167 "PAP-12030: can not change delimiting key. CFL[0]=%p",
168 tb->CFL[0]);
169
170 if (!item_pos && !pos_in_item && tb->CFL[0]) {
171 replace_key(tb, tb->CFL[0], tb->lkey[0],
172 tbS0, 0);
173 }
174 } else {
175 leaf_cut_from_buffer(&bi, item_pos, pos_in_item,
176 -tb->insert_size[0]);
177
178 RFALSE(!ih_item_len(ih),
179 "PAP-12035: cut must leave non-zero dynamic length of item");
180 }
181 break;
182 }
183
184 default:
185 print_cur_tb("12040");
186 reiserfs_panic(tb->tb_sb, "PAP-12040",
187 "unexpected mode: %s(%d)",
188 (flag ==
189 M_PASTE) ? "PASTE" : ((flag ==
190 M_INSERT) ? "INSERT" :
191 "UNKNOWN"), flag);
192 }
193
194
195 n = B_NR_ITEMS(tbS0);
196 if (tb->lnum[0]) {
197 if (tb->lnum[0] == -1) {
198 if (tb->rnum[0] == -1) {
199 if (tb->FR[0] == PATH_H_PPARENT(tb->tb_path, 0)) {
200
201 if (PATH_H_POSITION(tb->tb_path, 1) == 0
202 && 1 < B_NR_ITEMS(tb->FR[0]))
203 replace_key(tb, tb->CFL[0],
204 tb->lkey[0],
205 tb->FR[0], 1);
206
207 leaf_move_items(LEAF_FROM_S_TO_L, tb, n,
208 -1, NULL);
209 leaf_move_items(LEAF_FROM_R_TO_L, tb,
210 B_NR_ITEMS(tb->R[0]),
211 -1, NULL);
212
213 reiserfs_invalidate_buffer(tb, tbS0);
214 reiserfs_invalidate_buffer(tb,
215 tb->R[0]);
216
217 return 0;
218 }
219
220 leaf_move_items(LEAF_FROM_S_TO_R, tb, n, -1,
221 NULL);
222 leaf_move_items(LEAF_FROM_L_TO_R, tb,
223 B_NR_ITEMS(tb->L[0]), -1, NULL);
224
225
226 replace_key(tb, tb->CFR[0], tb->rkey[0],
227 tb->R[0], 0);
228
229 reiserfs_invalidate_buffer(tb, tbS0);
230 reiserfs_invalidate_buffer(tb, tb->L[0]);
231
232 return -1;
233 }
234
235 RFALSE(tb->rnum[0] != 0,
236 "PAP-12045: rnum must be 0 (%d)", tb->rnum[0]);
237
238 leaf_shift_left(tb, n, -1);
239
240 reiserfs_invalidate_buffer(tb, tbS0);
241
242 return 0;
243 }
244
245
246 RFALSE((tb->lnum[0] + tb->rnum[0] < n) ||
247 (tb->lnum[0] + tb->rnum[0] > n + 1),
248 "PAP-12050: rnum(%d) and lnum(%d) and item number(%d) in S[0] are not consistent",
249 tb->rnum[0], tb->lnum[0], n);
250 RFALSE((tb->lnum[0] + tb->rnum[0] == n) &&
251 (tb->lbytes != -1 || tb->rbytes != -1),
252 "PAP-12055: bad rbytes (%d)/lbytes (%d) parameters when items are not split",
253 tb->rbytes, tb->lbytes);
254 RFALSE((tb->lnum[0] + tb->rnum[0] == n + 1) &&
255 (tb->lbytes < 1 || tb->rbytes != -1),
256 "PAP-12060: bad rbytes (%d)/lbytes (%d) parameters when items are split",
257 tb->rbytes, tb->lbytes);
258
259 leaf_shift_left(tb, tb->lnum[0], tb->lbytes);
260 leaf_shift_right(tb, tb->rnum[0], tb->rbytes);
261
262 reiserfs_invalidate_buffer(tb, tbS0);
263
264 return 0;
265 }
266
267 if (tb->rnum[0] == -1) {
268
269 leaf_shift_right(tb, n, -1);
270 reiserfs_invalidate_buffer(tb, tbS0);
271 return 0;
272 }
273
274 RFALSE(tb->rnum[0],
275 "PAP-12065: bad rnum parameter must be 0 (%d)", tb->rnum[0]);
276 return 0;
277}
278
279static int balance_leaf(struct tree_balance *tb, struct item_head *ih,
280 const char *body,
281 int flag,
282
283 struct item_head *insert_key,
284
285
286
287 struct buffer_head **insert_ptr
288 )
289{
290 struct buffer_head *tbS0 = PATH_PLAST_BUFFER(tb->tb_path);
291 int item_pos = PATH_LAST_POSITION(tb->tb_path);
292
293 struct buffer_info bi;
294 struct buffer_head *S_new[2];
295 int snum[2];
296
297
298 int sbytes[2];
299
300
301
302
303
304 int n, i;
305 int ret_val;
306 int pos_in_item;
307 int zeros_num;
308
309 PROC_INFO_INC(tb->tb_sb, balance_at[0]);
310
311
312 if (tb->insert_size[0] < 0)
313 return balance_leaf_when_delete(tb, flag);
314
315 zeros_num = 0;
316 if (flag == M_INSERT && !body)
317 zeros_num = ih_item_len(ih);
318
319 pos_in_item = tb->tb_path->pos_in_item;
320
321
322 if (flag != M_INSERT
323 && is_indirect_le_ih(B_N_PITEM_HEAD(tbS0, item_pos)))
324 pos_in_item *= UNFM_P_SIZE;
325
326 if (tb->lnum[0] > 0) {
327
328 if (item_pos < tb->lnum[0]) {
329
330 n = B_NR_ITEMS(tb->L[0]);
331
332 switch (flag) {
333 case M_INSERT:
334
335 if (item_pos == tb->lnum[0] - 1
336 && tb->lbytes != -1) {
337
338 int new_item_len;
339 int version;
340
341 ret_val =
342 leaf_shift_left(tb, tb->lnum[0] - 1,
343 -1);
344
345
346 new_item_len =
347 ih_item_len(ih) - tb->lbytes;
348
349 put_ih_item_len(ih,
350 ih_item_len(ih) -
351 new_item_len);
352
353 RFALSE(ih_item_len(ih) <= 0,
354 "PAP-12080: there is nothing to insert into L[0]: ih_item_len=%d",
355 ih_item_len(ih));
356
357
358 buffer_info_init_left(tb, &bi);
359 leaf_insert_into_buf(&bi,
360 n + item_pos -
361 ret_val, ih, body,
362 zeros_num >
363 ih_item_len(ih) ?
364 ih_item_len(ih) :
365 zeros_num);
366
367 version = ih_version(ih);
368
369
370 set_le_ih_k_offset(ih,
371 le_ih_k_offset(ih) +
372 (tb->
373 lbytes <<
374 (is_indirect_le_ih
375 (ih) ? tb->tb_sb->
376 s_blocksize_bits -
377 UNFM_P_SHIFT :
378 0)));
379
380 put_ih_item_len(ih, new_item_len);
381 if (tb->lbytes > zeros_num) {
382 body +=
383 (tb->lbytes - zeros_num);
384 zeros_num = 0;
385 } else
386 zeros_num -= tb->lbytes;
387
388 RFALSE(ih_item_len(ih) <= 0,
389 "PAP-12085: there is nothing to insert into S[0]: ih_item_len=%d",
390 ih_item_len(ih));
391 } else {
392
393
394 ret_val =
395 leaf_shift_left(tb, tb->lnum[0] - 1,
396 tb->lbytes);
397
398 buffer_info_init_left(tb, &bi);
399 leaf_insert_into_buf(&bi,
400 n + item_pos -
401 ret_val, ih, body,
402 zeros_num);
403 tb->insert_size[0] = 0;
404 zeros_num = 0;
405 }
406 break;
407
408 case M_PASTE:
409
410 if (item_pos == tb->lnum[0] - 1
411 && tb->lbytes != -1) {
412
413 if (is_direntry_le_ih
414 (B_N_PITEM_HEAD(tbS0, item_pos))) {
415
416 RFALSE(zeros_num,
417 "PAP-12090: invalid parameter in case of a directory");
418
419 if (tb->lbytes > pos_in_item) {
420
421 struct item_head
422 *pasted;
423 int l_pos_in_item =
424 pos_in_item;
425
426
427 ret_val =
428 leaf_shift_left(tb,
429 tb->
430 lnum
431 [0],
432 tb->
433 lbytes
434 -
435 1);
436 if (ret_val
437 && !item_pos) {
438 pasted =
439 B_N_PITEM_HEAD
440 (tb->L[0],
441 B_NR_ITEMS
442 (tb->
443 L[0]) -
444 1);
445 l_pos_in_item +=
446 I_ENTRY_COUNT
447 (pasted) -
448 (tb->
449 lbytes -
450 1);
451 }
452
453
454 buffer_info_init_left(tb, &bi);
455 leaf_paste_in_buffer
456 (&bi,
457 n + item_pos -
458 ret_val,
459 l_pos_in_item,
460 tb->insert_size[0],
461 body, zeros_num);
462
463
464
465
466
467
468 leaf_paste_entries(&bi,
469 n +
470 item_pos
471 -
472 ret_val,
473 l_pos_in_item,
474 1,
475 (struct
476 reiserfs_de_head
477 *)
478 body,
479 body
480 +
481 DEH_SIZE,
482 tb->
483 insert_size
484 [0]
485 );
486 tb->insert_size[0] = 0;
487 } else {
488
489
490 leaf_shift_left(tb,
491 tb->
492 lnum[0],
493 tb->
494 lbytes);
495 }
496
497 pos_in_item -= tb->lbytes;
498 } else {
499
500 RFALSE(tb->lbytes <= 0,
501 "PAP-12095: there is nothing to shift to L[0]. lbytes=%d",
502 tb->lbytes);
503 RFALSE(pos_in_item !=
504 ih_item_len
505 (B_N_PITEM_HEAD
506 (tbS0, item_pos)),
507 "PAP-12100: incorrect position to paste: item_len=%d, pos_in_item=%d",
508 ih_item_len
509 (B_N_PITEM_HEAD
510 (tbS0, item_pos)),
511 pos_in_item);
512
513 if (tb->lbytes >= pos_in_item) {
514
515 int l_n;
516
517
518 l_n =
519 tb->lbytes -
520 pos_in_item;
521
522
523 tb->insert_size[0] -=
524 l_n;
525
526 RFALSE(tb->
527 insert_size[0] <=
528 0,
529 "PAP-12105: there is nothing to paste into L[0]. insert_size=%d",
530 tb->
531 insert_size[0]);
532 ret_val =
533 leaf_shift_left(tb,
534 tb->
535 lnum
536 [0],
537 ih_item_len
538 (B_N_PITEM_HEAD
539 (tbS0,
540 item_pos)));
541
542 buffer_info_init_left(tb, &bi);
543 leaf_paste_in_buffer
544 (&bi,
545 n + item_pos -
546 ret_val,
547 ih_item_len
548 (B_N_PITEM_HEAD
549 (tb->L[0],
550 n + item_pos -
551 ret_val)), l_n,
552 body,
553 zeros_num >
554 l_n ? l_n :
555 zeros_num);
556
557 {
558 int version;
559 int temp_l =
560 l_n;
561
562 RFALSE
563 (ih_item_len
564 (B_N_PITEM_HEAD
565 (tbS0,
566 0)),
567 "PAP-12106: item length must be 0");
568 RFALSE
569 (comp_short_le_keys
570 (B_N_PKEY
571 (tbS0, 0),
572 B_N_PKEY
573 (tb->L[0],
574 n +
575 item_pos
576 -
577 ret_val)),
578 "PAP-12107: items must be of the same file");
579 if (is_indirect_le_ih(B_N_PITEM_HEAD(tb->L[0], n + item_pos - ret_val))) {
580 temp_l =
581 l_n
582 <<
583 (tb->
584 tb_sb->
585 s_blocksize_bits
586 -
587 UNFM_P_SHIFT);
588 }
589
590 version =
591 ih_version
592 (B_N_PITEM_HEAD
593 (tbS0, 0));
594 set_le_key_k_offset
595 (version,
596 B_N_PKEY
597 (tbS0, 0),
598 le_key_k_offset
599 (version,
600 B_N_PKEY
601 (tbS0,
602 0)) +
603 temp_l);
604
605 set_le_key_k_offset
606 (version,
607 B_N_PDELIM_KEY
608 (tb->
609 CFL[0],
610 tb->
611 lkey[0]),
612 le_key_k_offset
613 (version,
614 B_N_PDELIM_KEY
615 (tb->
616 CFL[0],
617 tb->
618 lkey[0]))
619 + temp_l);
620 }
621
622
623 if (l_n > zeros_num) {
624 body +=
625 (l_n -
626 zeros_num);
627 zeros_num = 0;
628 } else
629 zeros_num -=
630 l_n;
631 pos_in_item = 0;
632
633 RFALSE
634 (comp_short_le_keys
635 (B_N_PKEY(tbS0, 0),
636 B_N_PKEY(tb->L[0],
637 B_NR_ITEMS
638 (tb->
639 L[0]) -
640 1))
641 ||
642 !op_is_left_mergeable
643 (B_N_PKEY(tbS0, 0),
644 tbS0->b_size)
645 ||
646 !op_is_left_mergeable
647 (B_N_PDELIM_KEY
648 (tb->CFL[0],
649 tb->lkey[0]),
650 tbS0->b_size),
651 "PAP-12120: item must be merge-able with left neighboring item");
652 } else {
653
654
655 pos_in_item -=
656 tb->lbytes;
657
658 RFALSE(pos_in_item <= 0,
659 "PAP-12125: no place for paste. pos_in_item=%d",
660 pos_in_item);
661
662
663 leaf_shift_left(tb,
664 tb->
665 lnum[0],
666 tb->
667 lbytes);
668 }
669 }
670 } else {
671
672 struct item_head *pasted;
673
674 if (!item_pos && op_is_left_mergeable(B_N_PKEY(tbS0, 0), tbS0->b_size)) {
675
676 pasted =
677 B_N_PITEM_HEAD(tb->L[0],
678 n - 1);
679 if (is_direntry_le_ih(pasted))
680 pos_in_item +=
681 ih_entry_count
682 (pasted);
683 else
684 pos_in_item +=
685 ih_item_len(pasted);
686 }
687
688
689 ret_val =
690 leaf_shift_left(tb, tb->lnum[0],
691 tb->lbytes);
692
693 buffer_info_init_left(tb, &bi);
694 leaf_paste_in_buffer(&bi,
695 n + item_pos -
696 ret_val,
697 pos_in_item,
698 tb->insert_size[0],
699 body, zeros_num);
700
701
702 pasted =
703 B_N_PITEM_HEAD(tb->L[0],
704 n + item_pos -
705 ret_val);
706 if (is_direntry_le_ih(pasted))
707 leaf_paste_entries(&bi,
708 n +
709 item_pos -
710 ret_val,
711 pos_in_item,
712 1,
713 (struct
714 reiserfs_de_head
715 *)body,
716 body +
717 DEH_SIZE,
718 tb->
719 insert_size
720 [0]
721 );
722
723 if (is_indirect_le_ih(pasted))
724 set_ih_free_space(pasted, 0);
725 tb->insert_size[0] = 0;
726 zeros_num = 0;
727 }
728 break;
729 default:
730 reiserfs_panic(tb->tb_sb, "PAP-12130",
731 "lnum > 0: unexpected mode: "
732 " %s(%d)",
733 (flag ==
734 M_DELETE) ? "DELETE" : ((flag ==
735 M_CUT)
736 ? "CUT"
737 :
738 "UNKNOWN"),
739 flag);
740 }
741 } else {
742
743 leaf_shift_left(tb, tb->lnum[0], tb->lbytes);
744 }
745 }
746
747
748
749 item_pos -= (tb->lnum[0] - ((tb->lbytes != -1) ? 1 : 0));
750
751 if (tb->rnum[0] > 0) {
752
753 n = B_NR_ITEMS(tbS0);
754 switch (flag) {
755
756 case M_INSERT:
757 if (n - tb->rnum[0] < item_pos) {
758 if (item_pos == n - tb->rnum[0] + 1 && tb->rbytes != -1) {
759 loff_t old_key_comp, old_len,
760 r_zeros_number;
761 const char *r_body;
762 int version;
763 loff_t offset;
764
765 leaf_shift_right(tb, tb->rnum[0] - 1,
766 -1);
767
768 version = ih_version(ih);
769
770 old_key_comp = le_ih_k_offset(ih);
771 old_len = ih_item_len(ih);
772
773
774 offset =
775 le_ih_k_offset(ih) +
776 ((old_len -
777 tb->
778 rbytes) << (is_indirect_le_ih(ih)
779 ? tb->tb_sb->
780 s_blocksize_bits -
781 UNFM_P_SHIFT : 0));
782 set_le_ih_k_offset(ih, offset);
783 put_ih_item_len(ih, tb->rbytes);
784
785 buffer_info_init_right(tb, &bi);
786 if ((old_len - tb->rbytes) > zeros_num) {
787 r_zeros_number = 0;
788 r_body =
789 body + (old_len -
790 tb->rbytes) -
791 zeros_num;
792 } else {
793 r_body = body;
794 r_zeros_number =
795 zeros_num - (old_len -
796 tb->rbytes);
797 zeros_num -= r_zeros_number;
798 }
799
800 leaf_insert_into_buf(&bi, 0, ih, r_body,
801 r_zeros_number);
802
803
804 replace_key(tb, tb->CFR[0], tb->rkey[0],
805 tb->R[0], 0);
806
807
808 set_le_ih_k_offset(ih, old_key_comp);
809 put_ih_item_len(ih,
810 old_len - tb->rbytes);
811
812 tb->insert_size[0] -= tb->rbytes;
813
814 } else {
815
816
817 ret_val =
818 leaf_shift_right(tb,
819 tb->rnum[0] - 1,
820 tb->rbytes);
821
822 buffer_info_init_right(tb, &bi);
823 leaf_insert_into_buf(&bi,
824 item_pos - n +
825 tb->rnum[0] - 1,
826 ih, body,
827 zeros_num);
828
829 if (item_pos - n + tb->rnum[0] - 1 == 0) {
830 replace_key(tb, tb->CFR[0],
831 tb->rkey[0],
832 tb->R[0], 0);
833
834 }
835 zeros_num = tb->insert_size[0] = 0;
836 }
837 } else {
838
839 leaf_shift_right(tb, tb->rnum[0], tb->rbytes);
840 }
841 break;
842
843 case M_PASTE:
844
845 if (n - tb->rnum[0] <= item_pos) {
846 if (item_pos == n - tb->rnum[0] && tb->rbytes != -1) {
847 if (is_direntry_le_ih(B_N_PITEM_HEAD(tbS0, item_pos))) {
848 int entry_count;
849
850 RFALSE(zeros_num,
851 "PAP-12145: invalid parameter in case of a directory");
852 entry_count =
853 I_ENTRY_COUNT(B_N_PITEM_HEAD
854 (tbS0,
855 item_pos));
856 if (entry_count - tb->rbytes <
857 pos_in_item)
858
859 {
860 int paste_entry_position;
861
862 RFALSE(tb->rbytes - 1 >=
863 entry_count
864 || !tb->
865 insert_size[0],
866 "PAP-12150: no enough of entries to shift to R[0]: rbytes=%d, entry_count=%d",
867 tb->rbytes,
868 entry_count);
869
870 leaf_shift_right(tb,
871 tb->
872 rnum
873 [0],
874 tb->
875 rbytes
876 - 1);
877
878 paste_entry_position =
879 pos_in_item -
880 entry_count +
881 tb->rbytes - 1;
882 buffer_info_init_right(tb, &bi);
883 leaf_paste_in_buffer
884 (&bi, 0,
885 paste_entry_position,
886 tb->insert_size[0],
887 body, zeros_num);
888
889 leaf_paste_entries(&bi,
890 0,
891 paste_entry_position,
892 1,
893 (struct
894 reiserfs_de_head
895 *)
896 body,
897 body
898 +
899 DEH_SIZE,
900 tb->
901 insert_size
902 [0]
903 );
904
905 if (paste_entry_position
906 == 0) {
907
908 replace_key(tb,
909 tb->
910 CFR
911 [0],
912 tb->
913 rkey
914 [0],
915 tb->
916 R
917 [0],
918 0);
919 }
920
921 tb->insert_size[0] = 0;
922 pos_in_item++;
923 } else {
924
925 leaf_shift_right(tb,
926 tb->
927 rnum
928 [0],
929 tb->
930 rbytes);
931 }
932 } else {
933
934 int n_shift, n_rem,
935 r_zeros_number;
936 const char *r_body;
937
938
939 if ((n_shift =
940 tb->rbytes -
941 tb->insert_size[0]) < 0)
942 n_shift = 0;
943
944 RFALSE(pos_in_item !=
945 ih_item_len
946 (B_N_PITEM_HEAD
947 (tbS0, item_pos)),
948 "PAP-12155: invalid position to paste. ih_item_len=%d, pos_in_item=%d",
949 pos_in_item,
950 ih_item_len
951 (B_N_PITEM_HEAD
952 (tbS0, item_pos)));
953
954 leaf_shift_right(tb,
955 tb->rnum[0],
956 n_shift);
957
958 if ((n_rem =
959 tb->insert_size[0] -
960 tb->rbytes) < 0)
961 n_rem = 0;
962
963 {
964 int version;
965 unsigned long temp_rem =
966 n_rem;
967
968 version =
969 ih_version
970 (B_N_PITEM_HEAD
971 (tb->R[0], 0));
972 if (is_indirect_le_key
973 (version,
974 B_N_PKEY(tb->R[0],
975 0))) {
976 temp_rem =
977 n_rem <<
978 (tb->tb_sb->
979 s_blocksize_bits
980 -
981 UNFM_P_SHIFT);
982 }
983 set_le_key_k_offset
984 (version,
985 B_N_PKEY(tb->R[0],
986 0),
987 le_key_k_offset
988 (version,
989 B_N_PKEY(tb->R[0],
990 0)) +
991 temp_rem);
992 set_le_key_k_offset
993 (version,
994 B_N_PDELIM_KEY(tb->
995 CFR
996 [0],
997 tb->
998 rkey
999 [0]),
1000 le_key_k_offset
1001 (version,
1002 B_N_PDELIM_KEY
1003 (tb->CFR[0],
1004 tb->rkey[0])) +
1005 temp_rem);
1006 }
1007
1008
1009 do_balance_mark_internal_dirty
1010 (tb, tb->CFR[0], 0);
1011
1012
1013 buffer_info_init_right(tb, &bi);
1014 if (n_rem > zeros_num) {
1015 r_zeros_number = 0;
1016 r_body =
1017 body + n_rem -
1018 zeros_num;
1019 } else {
1020 r_body = body;
1021 r_zeros_number =
1022 zeros_num - n_rem;
1023 zeros_num -=
1024 r_zeros_number;
1025 }
1026
1027 leaf_paste_in_buffer(&bi, 0,
1028 n_shift,
1029 tb->
1030 insert_size
1031 [0] -
1032 n_rem,
1033 r_body,
1034 r_zeros_number);
1035
1036 if (is_indirect_le_ih
1037 (B_N_PITEM_HEAD
1038 (tb->R[0], 0))) {
1039#if 0
1040 RFALSE(n_rem,
1041 "PAP-12160: paste more than one unformatted node pointer");
1042#endif
1043 set_ih_free_space
1044 (B_N_PITEM_HEAD
1045 (tb->R[0], 0), 0);
1046 }
1047 tb->insert_size[0] = n_rem;
1048 if (!n_rem)
1049 pos_in_item++;
1050 }
1051 } else {
1052
1053 struct item_head *pasted;
1054
1055 ret_val =
1056 leaf_shift_right(tb, tb->rnum[0],
1057 tb->rbytes);
1058
1059 if (pos_in_item >= 0) {
1060 buffer_info_init_right(tb, &bi);
1061 leaf_paste_in_buffer(&bi,
1062 item_pos -
1063 n +
1064 tb->
1065 rnum[0],
1066 pos_in_item,
1067 tb->
1068 insert_size
1069 [0], body,
1070 zeros_num);
1071 }
1072
1073
1074 pasted =
1075 B_N_PITEM_HEAD(tb->R[0],
1076 item_pos - n +
1077 tb->rnum[0]);
1078 if (is_direntry_le_ih(pasted)
1079 && pos_in_item >= 0) {
1080 leaf_paste_entries(&bi,
1081 item_pos -
1082 n +
1083 tb->rnum[0],
1084 pos_in_item,
1085 1,
1086 (struct
1087 reiserfs_de_head
1088 *)body,
1089 body +
1090 DEH_SIZE,
1091 tb->
1092 insert_size
1093 [0]
1094 );
1095 if (!pos_in_item) {
1096
1097 RFALSE(item_pos - n +
1098 tb->rnum[0],
1099 "PAP-12165: directory item must be first item of node when pasting is in 0th position");
1100
1101
1102 replace_key(tb,
1103 tb->CFR[0],
1104 tb->rkey[0],
1105 tb->R[0],
1106 0);
1107 }
1108 }
1109
1110 if (is_indirect_le_ih(pasted))
1111 set_ih_free_space(pasted, 0);
1112 zeros_num = tb->insert_size[0] = 0;
1113 }
1114 } else {
1115
1116 leaf_shift_right(tb, tb->rnum[0], tb->rbytes);
1117 }
1118 break;
1119 default:
1120 reiserfs_panic(tb->tb_sb, "PAP-12175",
1121 "rnum > 0: unexpected mode: %s(%d)",
1122 (flag ==
1123 M_DELETE) ? "DELETE" : ((flag ==
1124 M_CUT) ? "CUT"
1125 : "UNKNOWN"),
1126 flag);
1127 }
1128
1129 }
1130
1131
1132 RFALSE(tb->blknum[0] > 3,
1133 "PAP-12180: blknum can not be %d. It must be <= 3",
1134 tb->blknum[0]);
1135 RFALSE(tb->blknum[0] < 0,
1136 "PAP-12185: blknum can not be %d. It must be >= 0",
1137 tb->blknum[0]);
1138
1139
1140
1141
1142 if (tb->blknum[0] == 0) {
1143
1144 RFALSE(!tb->lnum[0] || !tb->rnum[0],
1145 "PAP-12190: lnum and rnum must not be zero");
1146
1147
1148
1149 if (tb->CFL[0]) {
1150 if (!tb->CFR[0])
1151 reiserfs_panic(tb->tb_sb, "vs-12195",
1152 "CFR not initialized");
1153 copy_key(B_N_PDELIM_KEY(tb->CFL[0], tb->lkey[0]),
1154 B_N_PDELIM_KEY(tb->CFR[0], tb->rkey[0]));
1155 do_balance_mark_internal_dirty(tb, tb->CFL[0], 0);
1156 }
1157
1158 reiserfs_invalidate_buffer(tb, tbS0);
1159 return 0;
1160 }
1161
1162
1163
1164
1165
1166 snum[0] = tb->s1num, snum[1] = tb->s2num;
1167 sbytes[0] = tb->s1bytes;
1168 sbytes[1] = tb->s2bytes;
1169 for (i = tb->blknum[0] - 2; i >= 0; i--) {
1170
1171 RFALSE(!snum[i], "PAP-12200: snum[%d] == %d. Must be > 0", i,
1172 snum[i]);
1173
1174
1175
1176 S_new[i] = get_FEB(tb);
1177
1178
1179 set_blkh_level(B_BLK_HEAD(S_new[i]), DISK_LEAF_NODE_LEVEL);
1180
1181 n = B_NR_ITEMS(tbS0);
1182
1183 switch (flag) {
1184 case M_INSERT:
1185
1186 if (n - snum[i] < item_pos) {
1187 if (item_pos == n - snum[i] + 1 && sbytes[i] != -1) {
1188 int old_key_comp, old_len,
1189 r_zeros_number;
1190 const char *r_body;
1191 int version;
1192
1193
1194 leaf_move_items(LEAF_FROM_S_TO_SNEW, tb,
1195 snum[i] - 1, -1,
1196 S_new[i]);
1197
1198 version = ih_version(ih);
1199 old_key_comp = le_ih_k_offset(ih);
1200 old_len = ih_item_len(ih);
1201
1202
1203 set_le_ih_k_offset(ih,
1204 le_ih_k_offset(ih) +
1205 ((old_len -
1206 sbytes[i]) <<
1207 (is_indirect_le_ih
1208 (ih) ? tb->tb_sb->
1209 s_blocksize_bits -
1210 UNFM_P_SHIFT :
1211 0)));
1212
1213 put_ih_item_len(ih, sbytes[i]);
1214
1215
1216 buffer_info_init_bh(tb, &bi, S_new[i]);
1217
1218 if ((old_len - sbytes[i]) > zeros_num) {
1219 r_zeros_number = 0;
1220 r_body =
1221 body + (old_len -
1222 sbytes[i]) -
1223 zeros_num;
1224 } else {
1225 r_body = body;
1226 r_zeros_number =
1227 zeros_num - (old_len -
1228 sbytes[i]);
1229 zeros_num -= r_zeros_number;
1230 }
1231
1232 leaf_insert_into_buf(&bi, 0, ih, r_body,
1233 r_zeros_number);
1234
1235
1236 set_le_ih_k_offset(ih, old_key_comp);
1237 put_ih_item_len(ih,
1238 old_len - sbytes[i]);
1239 tb->insert_size[0] -= sbytes[i];
1240 } else {
1241
1242
1243 leaf_move_items(LEAF_FROM_S_TO_SNEW, tb,
1244 snum[i] - 1, sbytes[i],
1245 S_new[i]);
1246
1247
1248 buffer_info_init_bh(tb, &bi, S_new[i]);
1249 leaf_insert_into_buf(&bi,
1250 item_pos - n +
1251 snum[i] - 1, ih,
1252 body, zeros_num);
1253
1254 zeros_num = tb->insert_size[0] = 0;
1255 }
1256 }
1257
1258 else {
1259
1260 leaf_move_items(LEAF_FROM_S_TO_SNEW, tb,
1261 snum[i], sbytes[i], S_new[i]);
1262 }
1263 break;
1264
1265 case M_PASTE:
1266
1267 if (n - snum[i] <= item_pos) {
1268 if (item_pos == n - snum[i] && sbytes[i] != -1) {
1269 struct item_head *aux_ih;
1270
1271 RFALSE(ih, "PAP-12210: ih must be 0");
1272
1273 aux_ih = B_N_PITEM_HEAD(tbS0, item_pos);
1274 if (is_direntry_le_ih(aux_ih)) {
1275
1276
1277 int entry_count;
1278
1279 entry_count =
1280 ih_entry_count(aux_ih);
1281
1282 if (entry_count - sbytes[i] <
1283 pos_in_item
1284 && pos_in_item <=
1285 entry_count) {
1286
1287
1288 RFALSE(!tb->
1289 insert_size[0],
1290 "PAP-12215: insert_size is already 0");
1291 RFALSE(sbytes[i] - 1 >=
1292 entry_count,
1293 "PAP-12220: there are no so much entries (%d), only %d",
1294 sbytes[i] - 1,
1295 entry_count);
1296
1297
1298 leaf_move_items
1299 (LEAF_FROM_S_TO_SNEW,
1300 tb, snum[i],
1301 sbytes[i] - 1,
1302 S_new[i]);
1303
1304 buffer_info_init_bh(tb, &bi, S_new[i]);
1305 leaf_paste_in_buffer
1306 (&bi, 0,
1307 pos_in_item -
1308 entry_count +
1309 sbytes[i] - 1,
1310 tb->insert_size[0],
1311 body, zeros_num);
1312
1313 leaf_paste_entries(&bi,
1314 0,
1315 pos_in_item
1316 -
1317 entry_count
1318 +
1319 sbytes
1320 [i] -
1321 1, 1,
1322 (struct
1323 reiserfs_de_head
1324 *)
1325 body,
1326 body
1327 +
1328 DEH_SIZE,
1329 tb->
1330 insert_size
1331 [0]
1332 );
1333 tb->insert_size[0] = 0;
1334 pos_in_item++;
1335 } else {
1336 leaf_move_items
1337 (LEAF_FROM_S_TO_SNEW,
1338 tb, snum[i],
1339 sbytes[i],
1340 S_new[i]);
1341 }
1342 } else {
1343
1344 int n_shift, n_rem,
1345 r_zeros_number;
1346 const char *r_body;
1347
1348 RFALSE(pos_in_item !=
1349 ih_item_len
1350 (B_N_PITEM_HEAD
1351 (tbS0, item_pos))
1352 || tb->insert_size[0] <=
1353 0,
1354 "PAP-12225: item too short or insert_size <= 0");
1355
1356
1357 n_shift =
1358 sbytes[i] -
1359 tb->insert_size[0];
1360 if (n_shift < 0)
1361 n_shift = 0;
1362 leaf_move_items
1363 (LEAF_FROM_S_TO_SNEW, tb,
1364 snum[i], n_shift,
1365 S_new[i]);
1366
1367
1368 n_rem =
1369 tb->insert_size[0] -
1370 sbytes[i];
1371 if (n_rem < 0)
1372 n_rem = 0;
1373
1374 buffer_info_init_bh(tb, &bi, S_new[i]);
1375 if (n_rem > zeros_num) {
1376 r_zeros_number = 0;
1377 r_body =
1378 body + n_rem -
1379 zeros_num;
1380 } else {
1381 r_body = body;
1382 r_zeros_number =
1383 zeros_num - n_rem;
1384 zeros_num -=
1385 r_zeros_number;
1386 }
1387
1388 leaf_paste_in_buffer(&bi, 0,
1389 n_shift,
1390 tb->
1391 insert_size
1392 [0] -
1393 n_rem,
1394 r_body,
1395 r_zeros_number);
1396 {
1397 struct item_head *tmp;
1398
1399 tmp =
1400 B_N_PITEM_HEAD(S_new
1401 [i],
1402 0);
1403 if (is_indirect_le_ih
1404 (tmp)) {
1405 set_ih_free_space
1406 (tmp, 0);
1407 set_le_ih_k_offset
1408 (tmp,
1409 le_ih_k_offset
1410 (tmp) +
1411 (n_rem <<
1412 (tb->
1413 tb_sb->
1414 s_blocksize_bits
1415 -
1416 UNFM_P_SHIFT)));
1417 } else {
1418 set_le_ih_k_offset
1419 (tmp,
1420 le_ih_k_offset
1421 (tmp) +
1422 n_rem);
1423 }
1424 }
1425
1426 tb->insert_size[0] = n_rem;
1427 if (!n_rem)
1428 pos_in_item++;
1429 }
1430 } else
1431
1432 {
1433 int leaf_mi;
1434 struct item_head *pasted;
1435
1436#ifdef CONFIG_REISERFS_CHECK
1437 struct item_head *ih_check =
1438 B_N_PITEM_HEAD(tbS0, item_pos);
1439
1440 if (!is_direntry_le_ih(ih_check)
1441 && (pos_in_item != ih_item_len(ih_check)
1442 || tb->insert_size[0] <= 0))
1443 reiserfs_panic(tb->tb_sb,
1444 "PAP-12235",
1445 "pos_in_item "
1446 "must be equal "
1447 "to ih_item_len");
1448#endif
1449
1450 leaf_mi =
1451 leaf_move_items(LEAF_FROM_S_TO_SNEW,
1452 tb, snum[i],
1453 sbytes[i],
1454 S_new[i]);
1455
1456 RFALSE(leaf_mi,
1457 "PAP-12240: unexpected value returned by leaf_move_items (%d)",
1458 leaf_mi);
1459
1460
1461 buffer_info_init_bh(tb, &bi, S_new[i]);
1462 leaf_paste_in_buffer(&bi,
1463 item_pos - n +
1464 snum[i],
1465 pos_in_item,
1466 tb->insert_size[0],
1467 body, zeros_num);
1468
1469 pasted =
1470 B_N_PITEM_HEAD(S_new[i],
1471 item_pos - n +
1472 snum[i]);
1473 if (is_direntry_le_ih(pasted)) {
1474 leaf_paste_entries(&bi,
1475 item_pos -
1476 n + snum[i],
1477 pos_in_item,
1478 1,
1479 (struct
1480 reiserfs_de_head
1481 *)body,
1482 body +
1483 DEH_SIZE,
1484 tb->
1485 insert_size
1486 [0]
1487 );
1488 }
1489
1490
1491 if (is_indirect_le_ih(pasted))
1492 set_ih_free_space(pasted, 0);
1493 zeros_num = tb->insert_size[0] = 0;
1494 }
1495 }
1496
1497 else {
1498
1499 leaf_move_items(LEAF_FROM_S_TO_SNEW, tb,
1500 snum[i], sbytes[i], S_new[i]);
1501 }
1502 break;
1503 default:
1504 reiserfs_panic(tb->tb_sb, "PAP-12245",
1505 "blknum > 2: unexpected mode: %s(%d)",
1506 (flag ==
1507 M_DELETE) ? "DELETE" : ((flag ==
1508 M_CUT) ? "CUT"
1509 : "UNKNOWN"),
1510 flag);
1511 }
1512
1513 memcpy(insert_key + i, B_N_PKEY(S_new[i], 0), KEY_SIZE);
1514 insert_ptr[i] = S_new[i];
1515
1516 RFALSE(!buffer_journaled(S_new[i])
1517 || buffer_journal_dirty(S_new[i])
1518 || buffer_dirty(S_new[i]), "PAP-12247: S_new[%d] : (%b)",
1519 i, S_new[i]);
1520 }
1521
1522
1523
1524 if (0 <= item_pos && item_pos < tb->s0num) {
1525
1526 switch (flag) {
1527 case M_INSERT:
1528 buffer_info_init_tbS0(tb, &bi);
1529 leaf_insert_into_buf(&bi, item_pos, ih, body,
1530 zeros_num);
1531
1532
1533 if (item_pos == 0) {
1534 if (tb->CFL[0])
1535 replace_key(tb, tb->CFL[0], tb->lkey[0],
1536 tbS0, 0);
1537
1538 }
1539 break;
1540
1541 case M_PASTE:{
1542 struct item_head *pasted;
1543
1544 pasted = B_N_PITEM_HEAD(tbS0, item_pos);
1545
1546 if (is_direntry_le_ih(pasted)) {
1547 if (pos_in_item >= 0 &&
1548 pos_in_item <=
1549 ih_entry_count(pasted)) {
1550
1551 RFALSE(!tb->insert_size[0],
1552 "PAP-12260: insert_size is 0 already");
1553
1554
1555 buffer_info_init_tbS0(tb, &bi);
1556 leaf_paste_in_buffer(&bi,
1557 item_pos,
1558 pos_in_item,
1559 tb->
1560 insert_size
1561 [0], body,
1562 zeros_num);
1563
1564
1565 leaf_paste_entries(&bi,
1566 item_pos,
1567 pos_in_item,
1568 1,
1569 (struct
1570 reiserfs_de_head
1571 *)body,
1572 body +
1573 DEH_SIZE,
1574 tb->
1575 insert_size
1576 [0]
1577 );
1578 if (!item_pos && !pos_in_item) {
1579 RFALSE(!tb->CFL[0]
1580 || !tb->L[0],
1581 "PAP-12270: CFL[0]/L[0] must be specified");
1582 if (tb->CFL[0]) {
1583 replace_key(tb,
1584 tb->
1585 CFL
1586 [0],
1587 tb->
1588 lkey
1589 [0],
1590 tbS0,
1591 0);
1592
1593 }
1594 }
1595 tb->insert_size[0] = 0;
1596 }
1597 } else {
1598 if (pos_in_item == ih_item_len(pasted)) {
1599
1600 RFALSE(tb->insert_size[0] <= 0,
1601 "PAP-12275: insert size must not be %d",
1602 tb->insert_size[0]);
1603 buffer_info_init_tbS0(tb, &bi);
1604 leaf_paste_in_buffer(&bi,
1605 item_pos,
1606 pos_in_item,
1607 tb->
1608 insert_size
1609 [0], body,
1610 zeros_num);
1611
1612 if (is_indirect_le_ih(pasted)) {
1613#if 0
1614 RFALSE(tb->
1615 insert_size[0] !=
1616 UNFM_P_SIZE,
1617 "PAP-12280: insert_size for indirect item must be %d, not %d",
1618 UNFM_P_SIZE,
1619 tb->
1620 insert_size[0]);
1621#endif
1622 set_ih_free_space
1623 (pasted, 0);
1624 }
1625 tb->insert_size[0] = 0;
1626 }
1627#ifdef CONFIG_REISERFS_CHECK
1628 else {
1629 if (tb->insert_size[0]) {
1630 print_cur_tb("12285");
1631 reiserfs_panic(tb->
1632 tb_sb,
1633 "PAP-12285",
1634 "insert_size "
1635 "must be 0 "
1636 "(%d)",
1637 tb->insert_size[0]);
1638 }
1639 }
1640#endif
1641
1642 }
1643 }
1644 }
1645 }
1646#ifdef CONFIG_REISERFS_CHECK
1647 if (flag == M_PASTE && tb->insert_size[0]) {
1648 print_cur_tb("12290");
1649 reiserfs_panic(tb->tb_sb,
1650 "PAP-12290", "insert_size is still not 0 (%d)",
1651 tb->insert_size[0]);
1652 }
1653#endif
1654 return 0;
1655}
1656
1657
1658void make_empty_node(struct buffer_info *bi)
1659{
1660 struct block_head *blkh;
1661
1662 RFALSE(bi->bi_bh == NULL, "PAP-12295: pointer to the buffer is NULL");
1663
1664 blkh = B_BLK_HEAD(bi->bi_bh);
1665 set_blkh_nr_item(blkh, 0);
1666 set_blkh_free_space(blkh, MAX_CHILD_SIZE(bi->bi_bh));
1667
1668 if (bi->bi_parent)
1669 B_N_CHILD(bi->bi_parent, bi->bi_position)->dc_size = 0;
1670}
1671
1672
1673struct buffer_head *get_FEB(struct tree_balance *tb)
1674{
1675 int i;
1676 struct buffer_info bi;
1677
1678 for (i = 0; i < MAX_FEB_SIZE; i++)
1679 if (tb->FEB[i] != NULL)
1680 break;
1681
1682 if (i == MAX_FEB_SIZE)
1683 reiserfs_panic(tb->tb_sb, "vs-12300", "FEB list is empty");
1684
1685 buffer_info_init_bh(tb, &bi, tb->FEB[i]);
1686 make_empty_node(&bi);
1687 set_buffer_uptodate(tb->FEB[i]);
1688 tb->used[i] = tb->FEB[i];
1689 tb->FEB[i] = NULL;
1690
1691 return tb->used[i];
1692}
1693
1694
1695
1696
1697static void store_thrown(struct tree_balance *tb, struct buffer_head *bh)
1698{
1699 int i;
1700
1701 if (buffer_dirty(bh))
1702 reiserfs_warning(tb->tb_sb, "reiserfs-12320",
1703 "called with dirty buffer");
1704 for (i = 0; i < ARRAY_SIZE(tb->thrown); i++)
1705 if (!tb->thrown[i]) {
1706 tb->thrown[i] = bh;
1707 get_bh(bh);
1708 return;
1709 }
1710 reiserfs_warning(tb->tb_sb, "reiserfs-12321",
1711 "too many thrown buffers");
1712}
1713
1714static void free_thrown(struct tree_balance *tb)
1715{
1716 int i;
1717 b_blocknr_t blocknr;
1718 for (i = 0; i < ARRAY_SIZE(tb->thrown); i++) {
1719 if (tb->thrown[i]) {
1720 blocknr = tb->thrown[i]->b_blocknr;
1721 if (buffer_dirty(tb->thrown[i]))
1722 reiserfs_warning(tb->tb_sb, "reiserfs-12322",
1723 "called with dirty buffer %d",
1724 blocknr);
1725 brelse(tb->thrown[i]);
1726 reiserfs_free_block(tb->transaction_handle, NULL,
1727 blocknr, 0);
1728 }
1729 }
1730}
1731
1732void reiserfs_invalidate_buffer(struct tree_balance *tb, struct buffer_head *bh)
1733{
1734 struct block_head *blkh;
1735 blkh = B_BLK_HEAD(bh);
1736 set_blkh_level(blkh, FREE_LEVEL);
1737 set_blkh_nr_item(blkh, 0);
1738
1739 clear_buffer_dirty(bh);
1740 store_thrown(tb, bh);
1741}
1742
1743
1744void replace_key(struct tree_balance *tb, struct buffer_head *dest, int n_dest,
1745 struct buffer_head *src, int n_src)
1746{
1747
1748 RFALSE(dest == NULL || src == NULL,
1749 "vs-12305: source or destination buffer is 0 (src=%p, dest=%p)",
1750 src, dest);
1751 RFALSE(!B_IS_KEYS_LEVEL(dest),
1752 "vs-12310: invalid level (%z) for destination buffer. dest must be leaf",
1753 dest);
1754 RFALSE(n_dest < 0 || n_src < 0,
1755 "vs-12315: src(%d) or dest(%d) key number < 0", n_src, n_dest);
1756 RFALSE(n_dest >= B_NR_ITEMS(dest) || n_src >= B_NR_ITEMS(src),
1757 "vs-12320: src(%d(%d)) or dest(%d(%d)) key number is too big",
1758 n_src, B_NR_ITEMS(src), n_dest, B_NR_ITEMS(dest));
1759
1760 if (B_IS_ITEMS_LEVEL(src))
1761
1762 memcpy(B_N_PDELIM_KEY(dest, n_dest), B_N_PITEM_HEAD(src, n_src),
1763 KEY_SIZE);
1764 else
1765 memcpy(B_N_PDELIM_KEY(dest, n_dest), B_N_PDELIM_KEY(src, n_src),
1766 KEY_SIZE);
1767
1768 do_balance_mark_internal_dirty(tb, dest, 0);
1769}
1770
1771int get_left_neighbor_position(struct tree_balance *tb, int h)
1772{
1773 int Sh_position = PATH_H_POSITION(tb->tb_path, h + 1);
1774
1775 RFALSE(PATH_H_PPARENT(tb->tb_path, h) == NULL || tb->FL[h] == NULL,
1776 "vs-12325: FL[%d](%p) or F[%d](%p) does not exist",
1777 h, tb->FL[h], h, PATH_H_PPARENT(tb->tb_path, h));
1778
1779 if (Sh_position == 0)
1780 return B_NR_ITEMS(tb->FL[h]);
1781 else
1782 return Sh_position - 1;
1783}
1784
1785int get_right_neighbor_position(struct tree_balance *tb, int h)
1786{
1787 int Sh_position = PATH_H_POSITION(tb->tb_path, h + 1);
1788
1789 RFALSE(PATH_H_PPARENT(tb->tb_path, h) == NULL || tb->FR[h] == NULL,
1790 "vs-12330: F[%d](%p) or FR[%d](%p) does not exist",
1791 h, PATH_H_PPARENT(tb->tb_path, h), h, tb->FR[h]);
1792
1793 if (Sh_position == B_NR_ITEMS(PATH_H_PPARENT(tb->tb_path, h)))
1794 return 0;
1795 else
1796 return Sh_position + 1;
1797}
1798
1799#ifdef CONFIG_REISERFS_CHECK
1800
1801int is_reusable(struct super_block *s, b_blocknr_t block, int bit_value);
1802static void check_internal_node(struct super_block *s, struct buffer_head *bh,
1803 char *mes)
1804{
1805 struct disk_child *dc;
1806 int i;
1807
1808 RFALSE(!bh, "PAP-12336: bh == 0");
1809
1810 if (!bh || !B_IS_IN_TREE(bh))
1811 return;
1812
1813 RFALSE(!buffer_dirty(bh) &&
1814 !(buffer_journaled(bh) || buffer_journal_dirty(bh)),
1815 "PAP-12337: buffer (%b) must be dirty", bh);
1816 dc = B_N_CHILD(bh, 0);
1817
1818 for (i = 0; i <= B_NR_ITEMS(bh); i++, dc++) {
1819 if (!is_reusable(s, dc_block_number(dc), 1)) {
1820 print_cur_tb(mes);
1821 reiserfs_panic(s, "PAP-12338",
1822 "invalid child pointer %y in %b",
1823 dc, bh);
1824 }
1825 }
1826}
1827
1828static int locked_or_not_in_tree(struct tree_balance *tb,
1829 struct buffer_head *bh, char *which)
1830{
1831 if ((!buffer_journal_prepared(bh) && buffer_locked(bh)) ||
1832 !B_IS_IN_TREE(bh)) {
1833 reiserfs_warning(tb->tb_sb, "vs-12339", "%s (%b)", which, bh);
1834 return 1;
1835 }
1836 return 0;
1837}
1838
1839static int check_before_balancing(struct tree_balance *tb)
1840{
1841 int retval = 0;
1842
1843 if (cur_tb) {
1844 reiserfs_panic(tb->tb_sb, "vs-12335", "suspect that schedule "
1845 "occurred based on cur_tb not being null at "
1846 "this point in code. do_balance cannot properly "
1847 "handle schedule occurring while it runs.");
1848 }
1849
1850
1851
1852 if (tb->lnum[0]) {
1853 retval |= locked_or_not_in_tree(tb, tb->L[0], "L[0]");
1854 retval |= locked_or_not_in_tree(tb, tb->FL[0], "FL[0]");
1855 retval |= locked_or_not_in_tree(tb, tb->CFL[0], "CFL[0]");
1856 check_leaf(tb->L[0]);
1857 }
1858 if (tb->rnum[0]) {
1859 retval |= locked_or_not_in_tree(tb, tb->R[0], "R[0]");
1860 retval |= locked_or_not_in_tree(tb, tb->FR[0], "FR[0]");
1861 retval |= locked_or_not_in_tree(tb, tb->CFR[0], "CFR[0]");
1862 check_leaf(tb->R[0]);
1863 }
1864 retval |= locked_or_not_in_tree(tb, PATH_PLAST_BUFFER(tb->tb_path),
1865 "S[0]");
1866 check_leaf(PATH_PLAST_BUFFER(tb->tb_path));
1867
1868 return retval;
1869}
1870
1871static void check_after_balance_leaf(struct tree_balance *tb)
1872{
1873 if (tb->lnum[0]) {
1874 if (B_FREE_SPACE(tb->L[0]) !=
1875 MAX_CHILD_SIZE(tb->L[0]) -
1876 dc_size(B_N_CHILD
1877 (tb->FL[0], get_left_neighbor_position(tb, 0)))) {
1878 print_cur_tb("12221");
1879 reiserfs_panic(tb->tb_sb, "PAP-12355",
1880 "shift to left was incorrect");
1881 }
1882 }
1883 if (tb->rnum[0]) {
1884 if (B_FREE_SPACE(tb->R[0]) !=
1885 MAX_CHILD_SIZE(tb->R[0]) -
1886 dc_size(B_N_CHILD
1887 (tb->FR[0], get_right_neighbor_position(tb, 0)))) {
1888 print_cur_tb("12222");
1889 reiserfs_panic(tb->tb_sb, "PAP-12360",
1890 "shift to right was incorrect");
1891 }
1892 }
1893 if (PATH_H_PBUFFER(tb->tb_path, 1) &&
1894 (B_FREE_SPACE(PATH_H_PBUFFER(tb->tb_path, 0)) !=
1895 (MAX_CHILD_SIZE(PATH_H_PBUFFER(tb->tb_path, 0)) -
1896 dc_size(B_N_CHILD(PATH_H_PBUFFER(tb->tb_path, 1),
1897 PATH_H_POSITION(tb->tb_path, 1)))))) {
1898 int left = B_FREE_SPACE(PATH_H_PBUFFER(tb->tb_path, 0));
1899 int right = (MAX_CHILD_SIZE(PATH_H_PBUFFER(tb->tb_path, 0)) -
1900 dc_size(B_N_CHILD(PATH_H_PBUFFER(tb->tb_path, 1),
1901 PATH_H_POSITION(tb->tb_path,
1902 1))));
1903 print_cur_tb("12223");
1904 reiserfs_warning(tb->tb_sb, "reiserfs-12363",
1905 "B_FREE_SPACE (PATH_H_PBUFFER(tb->tb_path,0)) = %d; "
1906 "MAX_CHILD_SIZE (%d) - dc_size( %y, %d ) [%d] = %d",
1907 left,
1908 MAX_CHILD_SIZE(PATH_H_PBUFFER(tb->tb_path, 0)),
1909 PATH_H_PBUFFER(tb->tb_path, 1),
1910 PATH_H_POSITION(tb->tb_path, 1),
1911 dc_size(B_N_CHILD
1912 (PATH_H_PBUFFER(tb->tb_path, 1),
1913 PATH_H_POSITION(tb->tb_path, 1))),
1914 right);
1915 reiserfs_panic(tb->tb_sb, "PAP-12365", "S is incorrect");
1916 }
1917}
1918
1919static void check_leaf_level(struct tree_balance *tb)
1920{
1921 check_leaf(tb->L[0]);
1922 check_leaf(tb->R[0]);
1923 check_leaf(PATH_PLAST_BUFFER(tb->tb_path));
1924}
1925
1926static void check_internal_levels(struct tree_balance *tb)
1927{
1928 int h;
1929
1930
1931 for (h = 1; tb->insert_size[h]; h++) {
1932 check_internal_node(tb->tb_sb, PATH_H_PBUFFER(tb->tb_path, h),
1933 "BAD BUFFER ON PATH");
1934 if (tb->lnum[h])
1935 check_internal_node(tb->tb_sb, tb->L[h], "BAD L");
1936 if (tb->rnum[h])
1937 check_internal_node(tb->tb_sb, tb->R[h], "BAD R");
1938 }
1939
1940}
1941
1942#endif
1943
1944
1945
1946
1947
1948
1949
1950
1951
1952
1953
1954
1955
1956
1957
1958
1959
1960
1961
1962
1963
1964
1965
1966
1967
1968
1969
1970
1971
1972
1973
1974
1975
1976
1977static inline void do_balance_starts(struct tree_balance *tb)
1978{
1979
1980
1981
1982
1983
1984
1985
1986
1987 RFALSE(check_before_balancing(tb), "PAP-12340: locked buffers in TB");
1988#ifdef CONFIG_REISERFS_CHECK
1989 cur_tb = tb;
1990#endif
1991}
1992
1993static inline void do_balance_completed(struct tree_balance *tb)
1994{
1995
1996#ifdef CONFIG_REISERFS_CHECK
1997 check_leaf_level(tb);
1998 check_internal_levels(tb);
1999 cur_tb = NULL;
2000#endif
2001
2002
2003
2004
2005
2006
2007 REISERFS_SB(tb->tb_sb)->s_do_balance++;
2008
2009
2010 unfix_nodes(tb);
2011
2012 free_thrown(tb);
2013}
2014
2015void do_balance(struct tree_balance *tb,
2016 struct item_head *ih,
2017 const char *body,
2018 int flag)
2019{
2020
2021
2022
2023
2024
2025
2026
2027
2028
2029
2030
2031
2032
2033
2034 int child_pos,
2035 h;
2036 struct item_head insert_key[2];
2037
2038
2039
2040
2041
2042
2043 struct buffer_head *insert_ptr[2];
2044
2045
2046 tb->tb_mode = flag;
2047 tb->need_balance_dirty = 0;
2048
2049 if (FILESYSTEM_CHANGED_TB(tb)) {
2050 reiserfs_panic(tb->tb_sb, "clm-6000", "fs generation has "
2051 "changed");
2052 }
2053
2054 if (!tb->insert_size[0]) {
2055 reiserfs_warning(tb->tb_sb, "PAP-12350",
2056 "insert_size == 0, mode == %c", flag);
2057 unfix_nodes(tb);
2058 return;
2059 }
2060
2061 atomic_inc(&(fs_generation(tb->tb_sb)));
2062 do_balance_starts(tb);
2063
2064
2065
2066
2067 child_pos = PATH_H_B_ITEM_ORDER(tb->tb_path, 0) +
2068 balance_leaf(tb, ih, body, flag, insert_key, insert_ptr);
2069
2070#ifdef CONFIG_REISERFS_CHECK
2071 check_after_balance_leaf(tb);
2072#endif
2073
2074
2075 for (h = 1; h < MAX_HEIGHT && tb->insert_size[h]; h++)
2076 child_pos =
2077 balance_internal(tb, h, child_pos, insert_key, insert_ptr);
2078
2079 do_balance_completed(tb);
2080
2081}
2082