This source file includes following definitions.
- old_item_num
- create_virtual_node
- check_left
- check_right
- get_num_ver
- set_parameters
- is_leaf_removable
- are_leaves_removable
- free_buffers_in_tb
- get_empty_nodes
- get_lfree
- get_rfree
- is_left_neighbor_in_cache
- decrement_key
- get_far_parent
- get_parents
- can_node_be_removed
- ip_check_balance
- dc_check_balance_internal
- dc_check_balance_leaf
- dc_check_balance
- check_balance
- get_direct_parent
- get_neighbors
- get_virtual_node_size
- get_mem_for_virtual_node
- tb_buffer_sanity_check
- tb_buffer_sanity_check
- clear_all_dirty_bits
- wait_tb_buffers_until_unlocked
- fix_nodes
- unfix_nodes
1
2
3
4
5 #include <linux/time.h>
6 #include <linux/slab.h>
7 #include <linux/string.h>
8 #include "reiserfs.h"
9 #include <linux/buffer_head.h>
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31 static inline int old_item_num(int new_num, int affected_item_num, int mode)
32 {
33 if (mode == M_PASTE || mode == M_CUT || new_num < affected_item_num)
34 return new_num;
35
36 if (mode == M_INSERT) {
37
38 RFALSE(new_num == 0,
39 "vs-8005: for INSERT mode and item number of inserted item");
40
41 return new_num - 1;
42 }
43
44 RFALSE(mode != M_DELETE,
45 "vs-8010: old_item_num: mode must be M_DELETE (mode = \'%c\'",
46 mode);
47
48 return new_num + 1;
49 }
50
51 static void create_virtual_node(struct tree_balance *tb, int h)
52 {
53 struct item_head *ih;
54 struct virtual_node *vn = tb->tb_vn;
55 int new_num;
56 struct buffer_head *Sh;
57
58 Sh = PATH_H_PBUFFER(tb->tb_path, h);
59
60
61 vn->vn_size =
62 MAX_CHILD_SIZE(Sh) - B_FREE_SPACE(Sh) + tb->insert_size[h];
63
64
65 if (h) {
66 vn->vn_nr_item = (vn->vn_size - DC_SIZE) / (DC_SIZE + KEY_SIZE);
67 return;
68 }
69
70
71 vn->vn_nr_item =
72 B_NR_ITEMS(Sh) + ((vn->vn_mode == M_INSERT) ? 1 : 0) -
73 ((vn->vn_mode == M_DELETE) ? 1 : 0);
74
75
76 vn->vn_vi = (struct virtual_item *)(tb->tb_vn + 1);
77 memset(vn->vn_vi, 0, vn->vn_nr_item * sizeof(struct virtual_item));
78 vn->vn_free_ptr += vn->vn_nr_item * sizeof(struct virtual_item);
79
80
81 ih = item_head(Sh, 0);
82
83
84 if (op_is_left_mergeable(&ih->ih_key, Sh->b_size)
85 && (vn->vn_mode != M_DELETE || vn->vn_affected_item_num))
86 vn->vn_vi[0].vi_type |= VI_TYPE_LEFT_MERGEABLE;
87
88
89
90
91
92 for (new_num = 0; new_num < vn->vn_nr_item; new_num++) {
93 int j;
94 struct virtual_item *vi = vn->vn_vi + new_num;
95 int is_affected =
96 ((new_num != vn->vn_affected_item_num) ? 0 : 1);
97
98 if (is_affected && vn->vn_mode == M_INSERT)
99 continue;
100
101
102 j = old_item_num(new_num, vn->vn_affected_item_num,
103 vn->vn_mode);
104
105 vi->vi_item_len += ih_item_len(ih + j) + IH_SIZE;
106 vi->vi_ih = ih + j;
107 vi->vi_item = ih_item_body(Sh, ih + j);
108 vi->vi_uarea = vn->vn_free_ptr;
109
110
111
112
113
114 vn->vn_free_ptr +=
115 op_create_vi(vn, vi, is_affected, tb->insert_size[0]);
116 if (tb->vn_buf + tb->vn_buf_size < vn->vn_free_ptr)
117 reiserfs_panic(tb->tb_sb, "vs-8030",
118 "virtual node space consumed");
119
120 if (!is_affected)
121
122 continue;
123
124 if (vn->vn_mode == M_PASTE || vn->vn_mode == M_CUT) {
125 vn->vn_vi[new_num].vi_item_len += tb->insert_size[0];
126
127 vi->vi_new_data = vn->vn_data;
128 }
129 }
130
131
132 if (vn->vn_mode == M_INSERT) {
133 struct virtual_item *vi = vn->vn_vi + vn->vn_affected_item_num;
134
135 RFALSE(vn->vn_ins_ih == NULL,
136 "vs-8040: item header of inserted item is not specified");
137 vi->vi_item_len = tb->insert_size[0];
138 vi->vi_ih = vn->vn_ins_ih;
139 vi->vi_item = vn->vn_data;
140 vi->vi_uarea = vn->vn_free_ptr;
141
142 op_create_vi(vn, vi, 0 ,
143 tb->insert_size[0]);
144 }
145
146
147
148
149
150 if (tb->CFR[0]) {
151 struct reiserfs_key *key;
152
153 key = internal_key(tb->CFR[0], tb->rkey[0]);
154 if (op_is_left_mergeable(key, Sh->b_size)
155 && (vn->vn_mode != M_DELETE
156 || vn->vn_affected_item_num != B_NR_ITEMS(Sh) - 1))
157 vn->vn_vi[vn->vn_nr_item - 1].vi_type |=
158 VI_TYPE_RIGHT_MERGEABLE;
159
160 #ifdef CONFIG_REISERFS_CHECK
161 if (op_is_left_mergeable(key, Sh->b_size) &&
162 !(vn->vn_mode != M_DELETE
163 || vn->vn_affected_item_num != B_NR_ITEMS(Sh) - 1)) {
164
165
166
167
168 if (!
169 (B_NR_ITEMS(Sh) == 1
170 && is_direntry_le_ih(item_head(Sh, 0))
171 && ih_entry_count(item_head(Sh, 0)) == 1)) {
172
173
174
175
176
177 print_block(Sh, 0, -1, -1);
178 reiserfs_panic(tb->tb_sb, "vs-8045",
179 "rdkey %k, affected item==%d "
180 "(mode==%c) Must be %c",
181 key, vn->vn_affected_item_num,
182 vn->vn_mode, M_DELETE);
183 }
184 }
185 #endif
186
187 }
188 }
189
190
191
192
193
194 static void check_left(struct tree_balance *tb, int h, int cur_free)
195 {
196 int i;
197 struct virtual_node *vn = tb->tb_vn;
198 struct virtual_item *vi;
199 int d_size, ih_size;
200
201 RFALSE(cur_free < 0, "vs-8050: cur_free (%d) < 0", cur_free);
202
203
204 if (h > 0) {
205 tb->lnum[h] = cur_free / (DC_SIZE + KEY_SIZE);
206 return;
207 }
208
209
210
211 if (!cur_free || !vn->vn_nr_item) {
212
213 tb->lnum[h] = 0;
214 tb->lbytes = -1;
215 return;
216 }
217
218 RFALSE(!PATH_H_PPARENT(tb->tb_path, 0),
219 "vs-8055: parent does not exist or invalid");
220
221 vi = vn->vn_vi;
222 if ((unsigned int)cur_free >=
223 (vn->vn_size -
224 ((vi->vi_type & VI_TYPE_LEFT_MERGEABLE) ? IH_SIZE : 0))) {
225
226
227 RFALSE(vn->vn_mode == M_INSERT || vn->vn_mode == M_PASTE,
228 "vs-8055: invalid mode or balance condition failed");
229
230 tb->lnum[0] = vn->vn_nr_item;
231 tb->lbytes = -1;
232 return;
233 }
234
235 d_size = 0, ih_size = IH_SIZE;
236
237
238 if (vi->vi_type & VI_TYPE_LEFT_MERGEABLE)
239 d_size = -((int)IH_SIZE), ih_size = 0;
240
241 tb->lnum[0] = 0;
242 for (i = 0; i < vn->vn_nr_item;
243 i++, ih_size = IH_SIZE, d_size = 0, vi++) {
244 d_size += vi->vi_item_len;
245 if (cur_free >= d_size) {
246
247 cur_free -= d_size;
248 tb->lnum[0]++;
249 continue;
250 }
251
252
253
254
255
256
257
258
259 if (cur_free <= ih_size) {
260 tb->lbytes = -1;
261 return;
262 }
263 cur_free -= ih_size;
264
265 tb->lbytes = op_check_left(vi, cur_free, 0, 0);
266 if (tb->lbytes != -1)
267
268 tb->lnum[0]++;
269
270 break;
271 }
272
273 return;
274 }
275
276
277
278
279
280 static void check_right(struct tree_balance *tb, int h, int cur_free)
281 {
282 int i;
283 struct virtual_node *vn = tb->tb_vn;
284 struct virtual_item *vi;
285 int d_size, ih_size;
286
287 RFALSE(cur_free < 0, "vs-8070: cur_free < 0");
288
289
290 if (h > 0) {
291 tb->rnum[h] = cur_free / (DC_SIZE + KEY_SIZE);
292 return;
293 }
294
295
296
297 if (!cur_free || !vn->vn_nr_item) {
298
299 tb->rnum[h] = 0;
300 tb->rbytes = -1;
301 return;
302 }
303
304 RFALSE(!PATH_H_PPARENT(tb->tb_path, 0),
305 "vs-8075: parent does not exist or invalid");
306
307 vi = vn->vn_vi + vn->vn_nr_item - 1;
308 if ((unsigned int)cur_free >=
309 (vn->vn_size -
310 ((vi->vi_type & VI_TYPE_RIGHT_MERGEABLE) ? IH_SIZE : 0))) {
311
312
313 RFALSE(vn->vn_mode == M_INSERT || vn->vn_mode == M_PASTE,
314 "vs-8080: invalid mode or balance condition failed");
315
316 tb->rnum[h] = vn->vn_nr_item;
317 tb->rbytes = -1;
318 return;
319 }
320
321 d_size = 0, ih_size = IH_SIZE;
322
323
324 if (vi->vi_type & VI_TYPE_RIGHT_MERGEABLE)
325 d_size = -(int)IH_SIZE, ih_size = 0;
326
327 tb->rnum[0] = 0;
328 for (i = vn->vn_nr_item - 1; i >= 0;
329 i--, d_size = 0, ih_size = IH_SIZE, vi--) {
330 d_size += vi->vi_item_len;
331 if (cur_free >= d_size) {
332
333 cur_free -= d_size;
334 tb->rnum[0]++;
335 continue;
336 }
337
338
339
340
341
342
343
344 if (cur_free <= ih_size) {
345 tb->rbytes = -1;
346 return;
347 }
348
349
350
351
352
353 cur_free -= ih_size;
354
355 tb->rbytes = op_check_right(vi, cur_free);
356 if (tb->rbytes != -1)
357
358 tb->rnum[0]++;
359
360 break;
361 }
362
363 return;
364 }
365
366
367
368
369
370
371
372
373
374 static int get_num_ver(int mode, struct tree_balance *tb, int h,
375 int from, int from_bytes,
376 int to, int to_bytes, short *snum012, int flow)
377 {
378 int i;
379 int units;
380 struct virtual_node *vn = tb->tb_vn;
381 int total_node_size, max_node_size, current_item_size;
382 int needed_nodes;
383
384
385 int start_item;
386
387
388 int end_item;
389
390
391
392
393
394 int start_bytes;
395
396
397
398
399
400 int end_bytes;
401
402
403
404
405
406 int split_item_positions[2];
407
408 split_item_positions[0] = -1;
409 split_item_positions[1] = -1;
410
411
412
413
414
415
416
417 RFALSE(tb->insert_size[h] < 0 || (mode != M_INSERT && mode != M_PASTE),
418 "vs-8100: insert_size < 0 in overflow");
419
420 max_node_size = MAX_CHILD_SIZE(PATH_H_PBUFFER(tb->tb_path, h));
421
422
423
424
425
426 snum012[3] = -1;
427 snum012[4] = -1;
428
429
430 if (h > 0) {
431 i = ((to - from) * (KEY_SIZE + DC_SIZE) + DC_SIZE);
432 if (i == max_node_size)
433 return 1;
434 return (i / max_node_size + 1);
435 }
436
437
438 needed_nodes = 1;
439 total_node_size = 0;
440
441
442 start_item = from;
443
444 start_bytes = ((from_bytes != -1) ? from_bytes : 0);
445
446
447 end_item = vn->vn_nr_item - to - 1;
448
449 end_bytes = (to_bytes != -1) ? to_bytes : 0;
450
451
452
453
454
455
456
457 for (i = start_item; i <= end_item; i++) {
458 struct virtual_item *vi = vn->vn_vi + i;
459 int skip_from_end = ((i == end_item) ? end_bytes : 0);
460
461 RFALSE(needed_nodes > 3, "vs-8105: too many nodes are needed");
462
463
464 current_item_size = vi->vi_item_len;
465
466
467
468
469
470 current_item_size -=
471 op_part_size(vi, 0 , start_bytes);
472
473
474 current_item_size -=
475 op_part_size(vi, 1 , skip_from_end);
476
477
478 if (total_node_size + current_item_size <= max_node_size) {
479 snum012[needed_nodes - 1]++;
480 total_node_size += current_item_size;
481 start_bytes = 0;
482 continue;
483 }
484
485
486
487
488
489 if (current_item_size > max_node_size) {
490 RFALSE(is_direct_le_ih(vi->vi_ih),
491 "vs-8110: "
492 "direct item length is %d. It can not be longer than %d",
493 current_item_size, max_node_size);
494
495 flow = 1;
496 }
497
498
499 if (!flow) {
500 needed_nodes++;
501 i--;
502 total_node_size = 0;
503 continue;
504 }
505
506
507
508
509
510 {
511 int free_space;
512
513 free_space = max_node_size - total_node_size - IH_SIZE;
514 units =
515 op_check_left(vi, free_space, start_bytes,
516 skip_from_end);
517
518
519
520
521 if (units == -1) {
522 needed_nodes++, i--, total_node_size = 0;
523 continue;
524 }
525 }
526
527
528 start_bytes += units;
529 snum012[needed_nodes - 1 + 3] = units;
530
531 if (needed_nodes > 2)
532 reiserfs_warning(tb->tb_sb, "vs-8111",
533 "split_item_position is out of range");
534 snum012[needed_nodes - 1]++;
535 split_item_positions[needed_nodes - 1] = i;
536 needed_nodes++;
537
538 start_item = i;
539 i--;
540 total_node_size = 0;
541 }
542
543
544
545
546
547
548 if (snum012[4] > 0) {
549 int split_item_num;
550 int bytes_to_r, bytes_to_l;
551 int bytes_to_S1new;
552
553 split_item_num = split_item_positions[1];
554 bytes_to_l =
555 ((from == split_item_num
556 && from_bytes != -1) ? from_bytes : 0);
557 bytes_to_r =
558 ((end_item == split_item_num
559 && end_bytes != -1) ? end_bytes : 0);
560 bytes_to_S1new =
561 ((split_item_positions[0] ==
562 split_item_positions[1]) ? snum012[3] : 0);
563
564
565 snum012[4] =
566 op_unit_num(&vn->vn_vi[split_item_num]) - snum012[4] -
567 bytes_to_r - bytes_to_l - bytes_to_S1new;
568
569 if (vn->vn_vi[split_item_num].vi_index != TYPE_DIRENTRY &&
570 vn->vn_vi[split_item_num].vi_index != TYPE_INDIRECT)
571 reiserfs_warning(tb->tb_sb, "vs-8115",
572 "not directory or indirect item");
573 }
574
575
576 if (snum012[3] > 0) {
577 int split_item_num;
578 int bytes_to_r, bytes_to_l;
579 int bytes_to_S2new;
580
581 split_item_num = split_item_positions[0];
582 bytes_to_l =
583 ((from == split_item_num
584 && from_bytes != -1) ? from_bytes : 0);
585 bytes_to_r =
586 ((end_item == split_item_num
587 && end_bytes != -1) ? end_bytes : 0);
588 bytes_to_S2new =
589 ((split_item_positions[0] == split_item_positions[1]
590 && snum012[4] != -1) ? snum012[4] : 0);
591
592
593 snum012[3] =
594 op_unit_num(&vn->vn_vi[split_item_num]) - snum012[3] -
595 bytes_to_r - bytes_to_l - bytes_to_S2new;
596 }
597
598 return needed_nodes;
599 }
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621 static void set_parameters(struct tree_balance *tb, int h, int lnum,
622 int rnum, int blk_num, short *s012, int lb, int rb)
623 {
624
625 tb->lnum[h] = lnum;
626 tb->rnum[h] = rnum;
627 tb->blknum[h] = blk_num;
628
629
630 if (h == 0) {
631 if (s012 != NULL) {
632 tb->s0num = *s012++;
633 tb->snum[0] = *s012++;
634 tb->snum[1] = *s012++;
635 tb->sbytes[0] = *s012++;
636 tb->sbytes[1] = *s012;
637 }
638 tb->lbytes = lb;
639 tb->rbytes = rb;
640 }
641 PROC_INFO_ADD(tb->tb_sb, lnum[h], lnum);
642 PROC_INFO_ADD(tb->tb_sb, rnum[h], rnum);
643
644 PROC_INFO_ADD(tb->tb_sb, lbytes[h], lb);
645 PROC_INFO_ADD(tb->tb_sb, rbytes[h], rb);
646 }
647
648
649
650
651
652 static int is_leaf_removable(struct tree_balance *tb)
653 {
654 struct virtual_node *vn = tb->tb_vn;
655 int to_left, to_right;
656 int size;
657 int remain_items;
658
659
660
661
662
663 to_left = tb->lnum[0] - ((tb->lbytes != -1) ? 1 : 0);
664 to_right = tb->rnum[0] - ((tb->rbytes != -1) ? 1 : 0);
665 remain_items = vn->vn_nr_item;
666
667
668 remain_items -= (to_left + to_right);
669
670
671 if (remain_items < 1) {
672 set_parameters(tb, 0, to_left, vn->vn_nr_item - to_left, 0,
673 NULL, -1, -1);
674 return 1;
675 }
676
677
678 if (remain_items > 1 || tb->lbytes == -1 || tb->rbytes == -1)
679 return 0;
680
681
682
683
684 size = op_unit_num(&vn->vn_vi[to_left]);
685
686 if (tb->lbytes + tb->rbytes >= size) {
687 set_parameters(tb, 0, to_left + 1, to_right + 1, 0, NULL,
688 tb->lbytes, -1);
689 return 1;
690 }
691
692 return 0;
693 }
694
695
696 static int are_leaves_removable(struct tree_balance *tb, int lfree, int rfree)
697 {
698 struct virtual_node *vn = tb->tb_vn;
699 int ih_size;
700 struct buffer_head *S0;
701
702 S0 = PATH_H_PBUFFER(tb->tb_path, 0);
703
704 ih_size = 0;
705 if (vn->vn_nr_item) {
706 if (vn->vn_vi[0].vi_type & VI_TYPE_LEFT_MERGEABLE)
707 ih_size += IH_SIZE;
708
709 if (vn->vn_vi[vn->vn_nr_item - 1].
710 vi_type & VI_TYPE_RIGHT_MERGEABLE)
711 ih_size += IH_SIZE;
712 } else {
713
714 struct item_head *ih;
715
716 RFALSE(B_NR_ITEMS(S0) != 1,
717 "vs-8125: item number must be 1: it is %d",
718 B_NR_ITEMS(S0));
719
720 ih = item_head(S0, 0);
721 if (tb->CFR[0]
722 && !comp_short_le_keys(&ih->ih_key,
723 internal_key(tb->CFR[0],
724 tb->rkey[0])))
725
726
727
728
729
730
731
732
733
734
735 if (is_direntry_le_ih(ih)) {
736 ih_size = IH_SIZE;
737
738
739
740
741
742 RFALSE(le_ih_k_offset(ih) == DOT_OFFSET,
743 "vs-8130: first directory item can not be removed until directory is not empty");
744 }
745
746 }
747
748 if (MAX_CHILD_SIZE(S0) + vn->vn_size <= rfree + lfree + ih_size) {
749 set_parameters(tb, 0, -1, -1, -1, NULL, -1, -1);
750 PROC_INFO_INC(tb->tb_sb, leaves_removable);
751 return 1;
752 }
753 return 0;
754
755 }
756
757
758 #define SET_PAR_SHIFT_LEFT \
759 if (h)\
760 {\
761 int to_l;\
762 \
763 to_l = (MAX_NR_KEY(Sh)+1 - lpar + vn->vn_nr_item + 1) / 2 -\
764 (MAX_NR_KEY(Sh) + 1 - lpar);\
765 \
766 set_parameters (tb, h, to_l, 0, lnver, NULL, -1, -1);\
767 }\
768 else \
769 {\
770 if (lset==LEFT_SHIFT_FLOW)\
771 set_parameters (tb, h, lpar, 0, lnver, snum012+lset,\
772 tb->lbytes, -1);\
773 else\
774 set_parameters (tb, h, lpar - (tb->lbytes!=-1), 0, lnver, snum012+lset,\
775 -1, -1);\
776 }
777
778 #define SET_PAR_SHIFT_RIGHT \
779 if (h)\
780 {\
781 int to_r;\
782 \
783 to_r = (MAX_NR_KEY(Sh)+1 - rpar + vn->vn_nr_item + 1) / 2 - (MAX_NR_KEY(Sh) + 1 - rpar);\
784 \
785 set_parameters (tb, h, 0, to_r, rnver, NULL, -1, -1);\
786 }\
787 else \
788 {\
789 if (rset==RIGHT_SHIFT_FLOW)\
790 set_parameters (tb, h, 0, rpar, rnver, snum012+rset,\
791 -1, tb->rbytes);\
792 else\
793 set_parameters (tb, h, 0, rpar - (tb->rbytes!=-1), rnver, snum012+rset,\
794 -1, -1);\
795 }
796
797 static void free_buffers_in_tb(struct tree_balance *tb)
798 {
799 int i;
800
801 pathrelse(tb->tb_path);
802
803 for (i = 0; i < MAX_HEIGHT; i++) {
804 brelse(tb->L[i]);
805 brelse(tb->R[i]);
806 brelse(tb->FL[i]);
807 brelse(tb->FR[i]);
808 brelse(tb->CFL[i]);
809 brelse(tb->CFR[i]);
810
811 tb->L[i] = NULL;
812 tb->R[i] = NULL;
813 tb->FL[i] = NULL;
814 tb->FR[i] = NULL;
815 tb->CFL[i] = NULL;
816 tb->CFR[i] = NULL;
817 }
818 }
819
820
821
822
823
824
825
826
827 static int get_empty_nodes(struct tree_balance *tb, int h)
828 {
829 struct buffer_head *new_bh, *Sh = PATH_H_PBUFFER(tb->tb_path, h);
830 b_blocknr_t *blocknr, blocknrs[MAX_AMOUNT_NEEDED] = { 0, };
831 int counter, number_of_freeblk;
832 int amount_needed;
833 int retval = CARRY_ON;
834 struct super_block *sb = tb->tb_sb;
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857 for (counter = 0, number_of_freeblk = tb->cur_blknum;
858 counter < h; counter++)
859 number_of_freeblk -=
860 (tb->blknum[counter]) ? (tb->blknum[counter] -
861 1) : 0;
862
863
864
865 amount_needed = (Sh) ? (tb->blknum[h] - 1) : 1;
866
867
868
869
870 if (amount_needed > number_of_freeblk)
871 amount_needed -= number_of_freeblk;
872 else
873 return CARRY_ON;
874
875
876
877
878
879 if (reiserfs_new_form_blocknrs(tb, blocknrs,
880 amount_needed) == NO_DISK_SPACE)
881 return NO_DISK_SPACE;
882
883
884 for (blocknr = blocknrs, counter = 0;
885 counter < amount_needed; blocknr++, counter++) {
886
887 RFALSE(!*blocknr,
888 "PAP-8135: reiserfs_new_blocknrs failed when got new blocks");
889
890 new_bh = sb_getblk(sb, *blocknr);
891 RFALSE(buffer_dirty(new_bh) ||
892 buffer_journaled(new_bh) ||
893 buffer_journal_dirty(new_bh),
894 "PAP-8140: journaled or dirty buffer %b for the new block",
895 new_bh);
896
897
898 RFALSE(tb->FEB[tb->cur_blknum],
899 "PAP-8141: busy slot for new buffer");
900
901 set_buffer_journal_new(new_bh);
902 tb->FEB[tb->cur_blknum++] = new_bh;
903 }
904
905 if (retval == CARRY_ON && FILESYSTEM_CHANGED_TB(tb))
906 retval = REPEAT_SEARCH;
907
908 return retval;
909 }
910
911
912
913
914
915 static int get_lfree(struct tree_balance *tb, int h)
916 {
917 struct buffer_head *l, *f;
918 int order;
919
920 if ((f = PATH_H_PPARENT(tb->tb_path, h)) == NULL ||
921 (l = tb->FL[h]) == NULL)
922 return 0;
923
924 if (f == l)
925 order = PATH_H_B_ITEM_ORDER(tb->tb_path, h) - 1;
926 else {
927 order = B_NR_ITEMS(l);
928 f = l;
929 }
930
931 return (MAX_CHILD_SIZE(f) - dc_size(B_N_CHILD(f, order)));
932 }
933
934
935
936
937
938 static int get_rfree(struct tree_balance *tb, int h)
939 {
940 struct buffer_head *r, *f;
941 int order;
942
943 if ((f = PATH_H_PPARENT(tb->tb_path, h)) == NULL ||
944 (r = tb->FR[h]) == NULL)
945 return 0;
946
947 if (f == r)
948 order = PATH_H_B_ITEM_ORDER(tb->tb_path, h) + 1;
949 else {
950 order = 0;
951 f = r;
952 }
953
954 return (MAX_CHILD_SIZE(f) - dc_size(B_N_CHILD(f, order)));
955
956 }
957
958
959 static int is_left_neighbor_in_cache(struct tree_balance *tb, int h)
960 {
961 struct buffer_head *father, *left;
962 struct super_block *sb = tb->tb_sb;
963 b_blocknr_t left_neighbor_blocknr;
964 int left_neighbor_position;
965
966
967 if (!tb->FL[h])
968 return 0;
969
970
971 father = PATH_H_PBUFFER(tb->tb_path, h + 1);
972
973 RFALSE(!father ||
974 !B_IS_IN_TREE(father) ||
975 !B_IS_IN_TREE(tb->FL[h]) ||
976 !buffer_uptodate(father) ||
977 !buffer_uptodate(tb->FL[h]),
978 "vs-8165: F[h] (%b) or FL[h] (%b) is invalid",
979 father, tb->FL[h]);
980
981
982
983
984
985 left_neighbor_position = (father == tb->FL[h]) ?
986 tb->lkey[h] : B_NR_ITEMS(tb->FL[h]);
987
988 left_neighbor_blocknr =
989 B_N_CHILD_NUM(tb->FL[h], left_neighbor_position);
990
991 if ((left = sb_find_get_block(sb, left_neighbor_blocknr))) {
992
993 RFALSE(buffer_uptodate(left) && !B_IS_IN_TREE(left),
994 "vs-8170: left neighbor (%b %z) is not in the tree",
995 left, left);
996 put_bh(left);
997 return 1;
998 }
999
1000 return 0;
1001 }
1002
1003 #define LEFT_PARENTS 'l'
1004 #define RIGHT_PARENTS 'r'
1005
1006 static void decrement_key(struct cpu_key *key)
1007 {
1008
1009 item_ops[cpu_key_k_type(key)]->decrement_key(key);
1010 }
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023 static int get_far_parent(struct tree_balance *tb,
1024 int h,
1025 struct buffer_head **pfather,
1026 struct buffer_head **pcom_father, char c_lr_par)
1027 {
1028 struct buffer_head *parent;
1029 INITIALIZE_PATH(s_path_to_neighbor_father);
1030 struct treepath *path = tb->tb_path;
1031 struct cpu_key s_lr_father_key;
1032 int counter,
1033 position = INT_MAX,
1034 first_last_position = 0,
1035 path_offset = PATH_H_PATH_OFFSET(path, h);
1036
1037
1038
1039
1040
1041
1042 counter = path_offset;
1043
1044 RFALSE(counter < FIRST_PATH_ELEMENT_OFFSET,
1045 "PAP-8180: invalid path length");
1046
1047 for (; counter > FIRST_PATH_ELEMENT_OFFSET; counter--) {
1048
1049
1050
1051
1052 if (!B_IS_IN_TREE
1053 (parent = PATH_OFFSET_PBUFFER(path, counter - 1)))
1054 return REPEAT_SEARCH;
1055
1056
1057 if ((position =
1058 PATH_OFFSET_POSITION(path,
1059 counter - 1)) >
1060 B_NR_ITEMS(parent))
1061 return REPEAT_SEARCH;
1062
1063
1064
1065
1066
1067 if (B_N_CHILD_NUM(parent, position) !=
1068 PATH_OFFSET_PBUFFER(path, counter)->b_blocknr)
1069 return REPEAT_SEARCH;
1070
1071
1072
1073
1074
1075 if (c_lr_par == RIGHT_PARENTS)
1076 first_last_position = B_NR_ITEMS(parent);
1077 if (position != first_last_position) {
1078 *pcom_father = parent;
1079 get_bh(*pcom_father);
1080
1081 break;
1082 }
1083 }
1084
1085
1086 if (counter == FIRST_PATH_ELEMENT_OFFSET) {
1087
1088
1089
1090
1091 if (PATH_OFFSET_PBUFFER
1092 (tb->tb_path,
1093 FIRST_PATH_ELEMENT_OFFSET)->b_blocknr ==
1094 SB_ROOT_BLOCK(tb->tb_sb)) {
1095 *pfather = *pcom_father = NULL;
1096 return CARRY_ON;
1097 }
1098 return REPEAT_SEARCH;
1099 }
1100
1101 RFALSE(B_LEVEL(*pcom_father) <= DISK_LEAF_NODE_LEVEL,
1102 "PAP-8185: (%b %z) level too small",
1103 *pcom_father, *pcom_father);
1104
1105
1106
1107 if (buffer_locked(*pcom_father)) {
1108
1109
1110 int depth = reiserfs_write_unlock_nested(tb->tb_sb);
1111 __wait_on_buffer(*pcom_father);
1112 reiserfs_write_lock_nested(tb->tb_sb, depth);
1113 if (FILESYSTEM_CHANGED_TB(tb)) {
1114 brelse(*pcom_father);
1115 return REPEAT_SEARCH;
1116 }
1117 }
1118
1119
1120
1121
1122
1123
1124
1125
1126 le_key2cpu_key(&s_lr_father_key,
1127 internal_key(*pcom_father,
1128 (c_lr_par ==
1129 LEFT_PARENTS) ? (tb->lkey[h - 1] =
1130 position -
1131 1) : (tb->rkey[h -
1132 1] =
1133 position)));
1134
1135 if (c_lr_par == LEFT_PARENTS)
1136 decrement_key(&s_lr_father_key);
1137
1138 if (search_by_key
1139 (tb->tb_sb, &s_lr_father_key, &s_path_to_neighbor_father,
1140 h + 1) == IO_ERROR)
1141
1142 return IO_ERROR;
1143
1144 if (FILESYSTEM_CHANGED_TB(tb)) {
1145 pathrelse(&s_path_to_neighbor_father);
1146 brelse(*pcom_father);
1147 return REPEAT_SEARCH;
1148 }
1149
1150 *pfather = PATH_PLAST_BUFFER(&s_path_to_neighbor_father);
1151
1152 RFALSE(B_LEVEL(*pfather) != h + 1,
1153 "PAP-8190: (%b %z) level too small", *pfather, *pfather);
1154 RFALSE(s_path_to_neighbor_father.path_length <
1155 FIRST_PATH_ELEMENT_OFFSET, "PAP-8192: path length is too small");
1156
1157 s_path_to_neighbor_father.path_length--;
1158 pathrelse(&s_path_to_neighbor_father);
1159 return CARRY_ON;
1160 }
1161
1162
1163
1164
1165
1166
1167
1168
1169
1170
1171
1172 static int get_parents(struct tree_balance *tb, int h)
1173 {
1174 struct treepath *path = tb->tb_path;
1175 int position,
1176 ret,
1177 path_offset = PATH_H_PATH_OFFSET(tb->tb_path, h);
1178 struct buffer_head *curf, *curcf;
1179
1180
1181 if (path_offset <= FIRST_PATH_ELEMENT_OFFSET) {
1182
1183
1184
1185
1186
1187 brelse(tb->FL[h]);
1188 brelse(tb->CFL[h]);
1189 brelse(tb->FR[h]);
1190 brelse(tb->CFR[h]);
1191 tb->FL[h] = NULL;
1192 tb->CFL[h] = NULL;
1193 tb->FR[h] = NULL;
1194 tb->CFR[h] = NULL;
1195 return CARRY_ON;
1196 }
1197
1198
1199 position = PATH_OFFSET_POSITION(path, path_offset - 1);
1200 if (position) {
1201
1202 curf = PATH_OFFSET_PBUFFER(path, path_offset - 1);
1203 curcf = PATH_OFFSET_PBUFFER(path, path_offset - 1);
1204 get_bh(curf);
1205 get_bh(curf);
1206 tb->lkey[h] = position - 1;
1207 } else {
1208
1209
1210
1211
1212
1213
1214
1215
1216 if ((ret = get_far_parent(tb, h + 1, &curf,
1217 &curcf,
1218 LEFT_PARENTS)) != CARRY_ON)
1219 return ret;
1220 }
1221
1222 brelse(tb->FL[h]);
1223 tb->FL[h] = curf;
1224 brelse(tb->CFL[h]);
1225 tb->CFL[h] = curcf;
1226
1227 RFALSE((curf && !B_IS_IN_TREE(curf)) ||
1228 (curcf && !B_IS_IN_TREE(curcf)),
1229 "PAP-8195: FL (%b) or CFL (%b) is invalid", curf, curcf);
1230
1231
1232
1233
1234 if (position == B_NR_ITEMS(PATH_H_PBUFFER(path, h + 1))) {
1235
1236
1237
1238
1239
1240
1241 if ((ret =
1242 get_far_parent(tb, h + 1, &curf, &curcf,
1243 RIGHT_PARENTS)) != CARRY_ON)
1244 return ret;
1245 } else {
1246
1247 curf = PATH_OFFSET_PBUFFER(path, path_offset - 1);
1248 curcf = PATH_OFFSET_PBUFFER(path, path_offset - 1);
1249 get_bh(curf);
1250 get_bh(curf);
1251 tb->rkey[h] = position;
1252 }
1253
1254 brelse(tb->FR[h]);
1255
1256 tb->FR[h] = curf;
1257
1258 brelse(tb->CFR[h]);
1259
1260 tb->CFR[h] = curcf;
1261
1262 RFALSE((curf && !B_IS_IN_TREE(curf)) ||
1263 (curcf && !B_IS_IN_TREE(curcf)),
1264 "PAP-8205: FR (%b) or CFR (%b) is invalid", curf, curcf);
1265
1266 return CARRY_ON;
1267 }
1268
1269
1270
1271
1272
1273 static inline int can_node_be_removed(int mode, int lfree, int sfree, int rfree,
1274 struct tree_balance *tb, int h)
1275 {
1276 struct buffer_head *Sh = PATH_H_PBUFFER(tb->tb_path, h);
1277 int levbytes = tb->insert_size[h];
1278 struct item_head *ih;
1279 struct reiserfs_key *r_key = NULL;
1280
1281 ih = item_head(Sh, 0);
1282 if (tb->CFR[h])
1283 r_key = internal_key(tb->CFR[h], tb->rkey[h]);
1284
1285 if (lfree + rfree + sfree < MAX_CHILD_SIZE(Sh) + levbytes
1286
1287 -
1288 ((!h
1289 && op_is_left_mergeable(&ih->ih_key, Sh->b_size)) ? IH_SIZE : 0)
1290 -
1291 ((!h && r_key
1292 && op_is_left_mergeable(r_key, Sh->b_size)) ? IH_SIZE : 0)
1293 + ((h) ? KEY_SIZE : 0)) {
1294
1295 if (sfree >= levbytes) {
1296
1297 if (!h)
1298 tb->s0num =
1299 B_NR_ITEMS(Sh) +
1300 ((mode == M_INSERT) ? 1 : 0);
1301 set_parameters(tb, h, 0, 0, 1, NULL, -1, -1);
1302 return NO_BALANCING_NEEDED;
1303 }
1304 }
1305 PROC_INFO_INC(tb->tb_sb, can_node_be_removed[h]);
1306 return !NO_BALANCING_NEEDED;
1307 }
1308
1309
1310
1311
1312
1313
1314
1315
1316
1317
1318
1319
1320
1321
1322
1323
1324 static int ip_check_balance(struct tree_balance *tb, int h)
1325 {
1326 struct virtual_node *vn = tb->tb_vn;
1327
1328
1329
1330
1331
1332
1333 int levbytes;
1334 int ret;
1335
1336 int lfree, sfree, rfree ;
1337
1338
1339
1340
1341
1342
1343
1344
1345
1346
1347 int nver, lnver, rnver, lrnver;
1348
1349
1350
1351
1352
1353
1354
1355
1356
1357
1358
1359
1360
1361
1362
1363
1364
1365
1366
1367
1368 short snum012[40] = { 0, };
1369
1370
1371 struct buffer_head *Sh;
1372
1373 Sh = PATH_H_PBUFFER(tb->tb_path, h);
1374 levbytes = tb->insert_size[h];
1375
1376
1377 if (!Sh) {
1378 if (!h)
1379 reiserfs_panic(tb->tb_sb, "vs-8210",
1380 "S[0] can not be 0");
1381 switch (ret = get_empty_nodes(tb, h)) {
1382
1383 case CARRY_ON:
1384 set_parameters(tb, h, 0, 0, 1, NULL, -1, -1);
1385 return NO_BALANCING_NEEDED;
1386
1387 case NO_DISK_SPACE:
1388 case REPEAT_SEARCH:
1389 return ret;
1390 default:
1391 reiserfs_panic(tb->tb_sb, "vs-8215", "incorrect "
1392 "return value of get_empty_nodes");
1393 }
1394 }
1395
1396
1397 ret = get_parents(tb, h);
1398 if (ret != CARRY_ON)
1399 return ret;
1400
1401 sfree = B_FREE_SPACE(Sh);
1402
1403
1404 rfree = get_rfree(tb, h);
1405 lfree = get_lfree(tb, h);
1406
1407
1408 if (can_node_be_removed(vn->vn_mode, lfree, sfree, rfree, tb, h) ==
1409 NO_BALANCING_NEEDED)
1410 return NO_BALANCING_NEEDED;
1411
1412 create_virtual_node(tb, h);
1413
1414
1415
1416
1417
1418
1419
1420 check_left(tb, h, lfree);
1421
1422
1423
1424
1425
1426
1427
1428 check_right(tb, h, rfree);
1429
1430
1431
1432
1433
1434 if (h && (tb->rnum[h] + tb->lnum[h] >= vn->vn_nr_item + 1)) {
1435 int to_r;
1436
1437
1438
1439
1440
1441
1442
1443
1444
1445 to_r =
1446 ((MAX_NR_KEY(Sh) << 1) + 2 - tb->lnum[h] - tb->rnum[h] +
1447 vn->vn_nr_item + 1) / 2 - (MAX_NR_KEY(Sh) + 1 -
1448 tb->rnum[h]);
1449 set_parameters(tb, h, vn->vn_nr_item + 1 - to_r, to_r, 0, NULL,
1450 -1, -1);
1451 return CARRY_ON;
1452 }
1453
1454
1455
1456
1457
1458 RFALSE(h &&
1459 (tb->lnum[h] >= vn->vn_nr_item + 1 ||
1460 tb->rnum[h] >= vn->vn_nr_item + 1),
1461 "vs-8220: tree is not balanced on internal level");
1462 RFALSE(!h && ((tb->lnum[h] >= vn->vn_nr_item && (tb->lbytes == -1)) ||
1463 (tb->rnum[h] >= vn->vn_nr_item && (tb->rbytes == -1))),
1464 "vs-8225: tree is not balanced on leaf level");
1465
1466
1467
1468
1469
1470 if (!h && is_leaf_removable(tb))
1471 return CARRY_ON;
1472
1473
1474
1475
1476
1477
1478
1479
1480
1481 if (sfree >= levbytes) {
1482 if (!h)
1483 tb->s0num = vn->vn_nr_item;
1484 set_parameters(tb, h, 0, 0, 1, NULL, -1, -1);
1485 return NO_BALANCING_NEEDED;
1486 }
1487
1488 {
1489 int lpar, rpar, nset, lset, rset, lrset;
1490
1491
1492
1493
1494
1495
1496
1497
1498
1499 #define FLOW 1
1500 #define NO_FLOW 0
1501
1502
1503 #define NOTHING_SHIFT_NO_FLOW 0
1504 #define NOTHING_SHIFT_FLOW 5
1505 #define LEFT_SHIFT_NO_FLOW 10
1506 #define LEFT_SHIFT_FLOW 15
1507 #define RIGHT_SHIFT_NO_FLOW 20
1508 #define RIGHT_SHIFT_FLOW 25
1509 #define LR_SHIFT_NO_FLOW 30
1510 #define LR_SHIFT_FLOW 35
1511
1512 lpar = tb->lnum[h];
1513 rpar = tb->rnum[h];
1514
1515
1516
1517
1518
1519
1520
1521
1522 nset = NOTHING_SHIFT_NO_FLOW;
1523 nver = get_num_ver(vn->vn_mode, tb, h,
1524 0, -1, h ? vn->vn_nr_item : 0, -1,
1525 snum012, NO_FLOW);
1526
1527 if (!h) {
1528 int nver1;
1529
1530
1531
1532
1533
1534 nver1 = get_num_ver(vn->vn_mode, tb, h,
1535 0, -1, 0, -1,
1536 snum012 + NOTHING_SHIFT_FLOW, FLOW);
1537 if (nver > nver1)
1538 nset = NOTHING_SHIFT_FLOW, nver = nver1;
1539 }
1540
1541
1542
1543
1544
1545
1546
1547
1548
1549 lset = LEFT_SHIFT_NO_FLOW;
1550 lnver = get_num_ver(vn->vn_mode, tb, h,
1551 lpar - ((h || tb->lbytes == -1) ? 0 : 1),
1552 -1, h ? vn->vn_nr_item : 0, -1,
1553 snum012 + LEFT_SHIFT_NO_FLOW, NO_FLOW);
1554 if (!h) {
1555 int lnver1;
1556
1557 lnver1 = get_num_ver(vn->vn_mode, tb, h,
1558 lpar -
1559 ((tb->lbytes != -1) ? 1 : 0),
1560 tb->lbytes, 0, -1,
1561 snum012 + LEFT_SHIFT_FLOW, FLOW);
1562 if (lnver > lnver1)
1563 lset = LEFT_SHIFT_FLOW, lnver = lnver1;
1564 }
1565
1566
1567
1568
1569
1570
1571
1572
1573
1574 rset = RIGHT_SHIFT_NO_FLOW;
1575 rnver = get_num_ver(vn->vn_mode, tb, h,
1576 0, -1,
1577 h ? (vn->vn_nr_item - rpar) : (rpar -
1578 ((tb->
1579 rbytes !=
1580 -1) ? 1 :
1581 0)), -1,
1582 snum012 + RIGHT_SHIFT_NO_FLOW, NO_FLOW);
1583 if (!h) {
1584 int rnver1;
1585
1586 rnver1 = get_num_ver(vn->vn_mode, tb, h,
1587 0, -1,
1588 (rpar -
1589 ((tb->rbytes != -1) ? 1 : 0)),
1590 tb->rbytes,
1591 snum012 + RIGHT_SHIFT_FLOW, FLOW);
1592
1593 if (rnver > rnver1)
1594 rset = RIGHT_SHIFT_FLOW, rnver = rnver1;
1595 }
1596
1597
1598
1599
1600
1601
1602
1603
1604 lrset = LR_SHIFT_NO_FLOW;
1605 lrnver = get_num_ver(vn->vn_mode, tb, h,
1606 lpar - ((h || tb->lbytes == -1) ? 0 : 1),
1607 -1,
1608 h ? (vn->vn_nr_item - rpar) : (rpar -
1609 ((tb->
1610 rbytes !=
1611 -1) ? 1 :
1612 0)), -1,
1613 snum012 + LR_SHIFT_NO_FLOW, NO_FLOW);
1614 if (!h) {
1615 int lrnver1;
1616
1617 lrnver1 = get_num_ver(vn->vn_mode, tb, h,
1618 lpar -
1619 ((tb->lbytes != -1) ? 1 : 0),
1620 tb->lbytes,
1621 (rpar -
1622 ((tb->rbytes != -1) ? 1 : 0)),
1623 tb->rbytes,
1624 snum012 + LR_SHIFT_FLOW, FLOW);
1625 if (lrnver > lrnver1)
1626 lrset = LR_SHIFT_FLOW, lrnver = lrnver1;
1627 }
1628
1629
1630
1631
1632
1633
1634
1635
1636
1637 if (lrnver < lnver && lrnver < rnver) {
1638 RFALSE(h &&
1639 (tb->lnum[h] != 1 ||
1640 tb->rnum[h] != 1 ||
1641 lrnver != 1 || rnver != 2 || lnver != 2
1642 || h != 1), "vs-8230: bad h");
1643 if (lrset == LR_SHIFT_FLOW)
1644 set_parameters(tb, h, tb->lnum[h], tb->rnum[h],
1645 lrnver, snum012 + lrset,
1646 tb->lbytes, tb->rbytes);
1647 else
1648 set_parameters(tb, h,
1649 tb->lnum[h] -
1650 ((tb->lbytes == -1) ? 0 : 1),
1651 tb->rnum[h] -
1652 ((tb->rbytes == -1) ? 0 : 1),
1653 lrnver, snum012 + lrset, -1, -1);
1654
1655 return CARRY_ON;
1656 }
1657
1658
1659
1660
1661
1662 if (nver == lrnver) {
1663 set_parameters(tb, h, 0, 0, nver, snum012 + nset, -1,
1664 -1);
1665 return CARRY_ON;
1666 }
1667
1668
1669
1670
1671
1672
1673
1674
1675
1676
1677 if (lnver < rnver) {
1678 SET_PAR_SHIFT_LEFT;
1679 return CARRY_ON;
1680 }
1681
1682
1683
1684
1685
1686 if (lnver > rnver) {
1687 SET_PAR_SHIFT_RIGHT;
1688 return CARRY_ON;
1689 }
1690
1691
1692
1693
1694
1695 if (is_left_neighbor_in_cache(tb, h)) {
1696 SET_PAR_SHIFT_LEFT;
1697 return CARRY_ON;
1698 }
1699
1700
1701
1702
1703
1704 SET_PAR_SHIFT_RIGHT;
1705 return CARRY_ON;
1706 }
1707 }
1708
1709
1710
1711
1712
1713
1714
1715
1716
1717
1718
1719
1720
1721
1722
1723
1724
1725
1726 static int dc_check_balance_internal(struct tree_balance *tb, int h)
1727 {
1728 struct virtual_node *vn = tb->tb_vn;
1729
1730
1731
1732
1733
1734 struct buffer_head *Sh, *Fh;
1735 int ret;
1736 int lfree, rfree ;
1737
1738 Sh = PATH_H_PBUFFER(tb->tb_path, h);
1739 Fh = PATH_H_PPARENT(tb->tb_path, h);
1740
1741
1742
1743
1744
1745
1746
1747 create_virtual_node(tb, h);
1748
1749 if (!Fh) {
1750
1751 if (vn->vn_nr_item > 0) {
1752 set_parameters(tb, h, 0, 0, 1, NULL, -1, -1);
1753 return NO_BALANCING_NEEDED;
1754 }
1755
1756
1757
1758
1759
1760 set_parameters(tb, h, 0, 0, 0, NULL, -1, -1);
1761 return CARRY_ON;
1762 }
1763
1764 if ((ret = get_parents(tb, h)) != CARRY_ON)
1765 return ret;
1766
1767
1768 rfree = get_rfree(tb, h);
1769 lfree = get_lfree(tb, h);
1770
1771
1772 check_left(tb, h, lfree);
1773 check_right(tb, h, rfree);
1774
1775
1776
1777
1778
1779 if (vn->vn_nr_item >= MIN_NR_KEY(Sh)) {
1780
1781
1782
1783
1784 if (vn->vn_nr_item == MIN_NR_KEY(Sh)) {
1785
1786 if (tb->lnum[h] >= vn->vn_nr_item + 1) {
1787 int n;
1788 int order_L;
1789
1790 order_L =
1791 ((n =
1792 PATH_H_B_ITEM_ORDER(tb->tb_path,
1793 h)) ==
1794 0) ? B_NR_ITEMS(tb->FL[h]) : n - 1;
1795 n = dc_size(B_N_CHILD(tb->FL[h], order_L)) /
1796 (DC_SIZE + KEY_SIZE);
1797 set_parameters(tb, h, -n - 1, 0, 0, NULL, -1,
1798 -1);
1799 return CARRY_ON;
1800 }
1801
1802
1803 if (tb->rnum[h] >= vn->vn_nr_item + 1) {
1804 int n;
1805 int order_R;
1806
1807 order_R =
1808 ((n =
1809 PATH_H_B_ITEM_ORDER(tb->tb_path,
1810 h)) ==
1811 B_NR_ITEMS(Fh)) ? 0 : n + 1;
1812 n = dc_size(B_N_CHILD(tb->FR[h], order_R)) /
1813 (DC_SIZE + KEY_SIZE);
1814 set_parameters(tb, h, 0, -n - 1, 0, NULL, -1,
1815 -1);
1816 return CARRY_ON;
1817 }
1818 }
1819
1820
1821
1822
1823
1824 if (tb->rnum[h] + tb->lnum[h] >= vn->vn_nr_item + 1) {
1825 int to_r;
1826
1827 to_r =
1828 ((MAX_NR_KEY(Sh) << 1) + 2 - tb->lnum[h] -
1829 tb->rnum[h] + vn->vn_nr_item + 1) / 2 -
1830 (MAX_NR_KEY(Sh) + 1 - tb->rnum[h]);
1831 set_parameters(tb, h, vn->vn_nr_item + 1 - to_r, to_r,
1832 0, NULL, -1, -1);
1833 return CARRY_ON;
1834 }
1835
1836
1837 set_parameters(tb, h, 0, 0, 1, NULL, -1, -1);
1838 return NO_BALANCING_NEEDED;
1839 }
1840
1841
1842
1843
1844
1845
1846 if (tb->lnum[h] >= vn->vn_nr_item + 1)
1847 if (is_left_neighbor_in_cache(tb, h)
1848 || tb->rnum[h] < vn->vn_nr_item + 1 || !tb->FR[h]) {
1849 int n;
1850 int order_L;
1851
1852 order_L =
1853 ((n =
1854 PATH_H_B_ITEM_ORDER(tb->tb_path,
1855 h)) ==
1856 0) ? B_NR_ITEMS(tb->FL[h]) : n - 1;
1857 n = dc_size(B_N_CHILD(tb->FL[h], order_L)) / (DC_SIZE +
1858 KEY_SIZE);
1859 set_parameters(tb, h, -n - 1, 0, 0, NULL, -1, -1);
1860 return CARRY_ON;
1861 }
1862
1863
1864 if (tb->rnum[h] >= vn->vn_nr_item + 1) {
1865 int n;
1866 int order_R;
1867
1868 order_R =
1869 ((n =
1870 PATH_H_B_ITEM_ORDER(tb->tb_path,
1871 h)) == B_NR_ITEMS(Fh)) ? 0 : (n + 1);
1872 n = dc_size(B_N_CHILD(tb->FR[h], order_R)) / (DC_SIZE +
1873 KEY_SIZE);
1874 set_parameters(tb, h, 0, -n - 1, 0, NULL, -1, -1);
1875 return CARRY_ON;
1876 }
1877
1878
1879 if (tb->rnum[h] + tb->lnum[h] >= vn->vn_nr_item + 1) {
1880 int to_r;
1881
1882 to_r =
1883 ((MAX_NR_KEY(Sh) << 1) + 2 - tb->lnum[h] - tb->rnum[h] +
1884 vn->vn_nr_item + 1) / 2 - (MAX_NR_KEY(Sh) + 1 -
1885 tb->rnum[h]);
1886 set_parameters(tb, h, vn->vn_nr_item + 1 - to_r, to_r, 0, NULL,
1887 -1, -1);
1888 return CARRY_ON;
1889 }
1890
1891
1892 RFALSE(!tb->FL[h] && !tb->FR[h], "vs-8235: trying to borrow for root");
1893
1894
1895 if (is_left_neighbor_in_cache(tb, h) || !tb->FR[h]) {
1896 int from_l;
1897
1898 from_l =
1899 (MAX_NR_KEY(Sh) + 1 - tb->lnum[h] + vn->vn_nr_item +
1900 1) / 2 - (vn->vn_nr_item + 1);
1901 set_parameters(tb, h, -from_l, 0, 1, NULL, -1, -1);
1902 return CARRY_ON;
1903 }
1904
1905 set_parameters(tb, h, 0,
1906 -((MAX_NR_KEY(Sh) + 1 - tb->rnum[h] + vn->vn_nr_item +
1907 1) / 2 - (vn->vn_nr_item + 1)), 1, NULL, -1, -1);
1908 return CARRY_ON;
1909 }
1910
1911
1912
1913
1914
1915
1916
1917
1918
1919
1920
1921
1922
1923
1924
1925 static int dc_check_balance_leaf(struct tree_balance *tb, int h)
1926 {
1927 struct virtual_node *vn = tb->tb_vn;
1928
1929
1930
1931
1932
1933
1934
1935 int levbytes;
1936
1937
1938 int maxsize, ret;
1939
1940
1941
1942
1943
1944 struct buffer_head *S0, *F0;
1945 int lfree, rfree ;
1946
1947 S0 = PATH_H_PBUFFER(tb->tb_path, 0);
1948 F0 = PATH_H_PPARENT(tb->tb_path, 0);
1949
1950 levbytes = tb->insert_size[h];
1951
1952 maxsize = MAX_CHILD_SIZE(S0);
1953
1954 if (!F0) {
1955
1956 RFALSE(-levbytes >= maxsize - B_FREE_SPACE(S0),
1957 "vs-8240: attempt to create empty buffer tree");
1958
1959 set_parameters(tb, h, 0, 0, 1, NULL, -1, -1);
1960 return NO_BALANCING_NEEDED;
1961 }
1962
1963 if ((ret = get_parents(tb, h)) != CARRY_ON)
1964 return ret;
1965
1966
1967 rfree = get_rfree(tb, h);
1968 lfree = get_lfree(tb, h);
1969
1970 create_virtual_node(tb, h);
1971
1972
1973 if (are_leaves_removable(tb, lfree, rfree))
1974 return CARRY_ON;
1975
1976
1977
1978
1979
1980
1981
1982 check_left(tb, h, lfree);
1983 check_right(tb, h, rfree);
1984
1985
1986 if (tb->lnum[0] >= vn->vn_nr_item && tb->lbytes == -1)
1987 if (is_left_neighbor_in_cache(tb, h) || ((tb->rnum[0] - ((tb->rbytes == -1) ? 0 : 1)) < vn->vn_nr_item) ||
1988 !tb->FR[h]) {
1989
1990 RFALSE(!tb->FL[h],
1991 "vs-8245: dc_check_balance_leaf: FL[h] must exist");
1992
1993
1994 set_parameters(tb, h, -1, 0, 0, NULL, -1, -1);
1995 return CARRY_ON;
1996 }
1997
1998
1999 if (tb->rnum[0] >= vn->vn_nr_item && tb->rbytes == -1) {
2000 set_parameters(tb, h, 0, -1, 0, NULL, -1, -1);
2001 return CARRY_ON;
2002 }
2003
2004
2005
2006
2007
2008 if (is_leaf_removable(tb))
2009 return CARRY_ON;
2010
2011
2012 tb->s0num = vn->vn_nr_item;
2013 set_parameters(tb, h, 0, 0, 1, NULL, -1, -1);
2014 return NO_BALANCING_NEEDED;
2015 }
2016
2017
2018
2019
2020
2021
2022
2023
2024
2025
2026
2027
2028
2029
2030
2031 static int dc_check_balance(struct tree_balance *tb, int h)
2032 {
2033 RFALSE(!(PATH_H_PBUFFER(tb->tb_path, h)),
2034 "vs-8250: S is not initialized");
2035
2036 if (h)
2037 return dc_check_balance_internal(tb, h);
2038 else
2039 return dc_check_balance_leaf(tb, h);
2040 }
2041
2042
2043
2044
2045
2046
2047
2048
2049
2050
2051
2052
2053
2054
2055
2056
2057
2058
2059
2060
2061 static int check_balance(int mode,
2062 struct tree_balance *tb,
2063 int h,
2064 int inum,
2065 int pos_in_item,
2066 struct item_head *ins_ih, const void *data)
2067 {
2068 struct virtual_node *vn;
2069
2070 vn = tb->tb_vn = (struct virtual_node *)(tb->vn_buf);
2071 vn->vn_free_ptr = (char *)(tb->tb_vn + 1);
2072 vn->vn_mode = mode;
2073 vn->vn_affected_item_num = inum;
2074 vn->vn_pos_in_item = pos_in_item;
2075 vn->vn_ins_ih = ins_ih;
2076 vn->vn_data = data;
2077
2078 RFALSE(mode == M_INSERT && !vn->vn_ins_ih,
2079 "vs-8255: ins_ih can not be 0 in insert mode");
2080
2081
2082 if (tb->insert_size[h] > 0)
2083 return ip_check_balance(tb, h);
2084
2085
2086 return dc_check_balance(tb, h);
2087 }
2088
2089
2090 static int get_direct_parent(struct tree_balance *tb, int h)
2091 {
2092 struct buffer_head *bh;
2093 struct treepath *path = tb->tb_path;
2094 int position,
2095 path_offset = PATH_H_PATH_OFFSET(tb->tb_path, h);
2096
2097
2098 if (path_offset <= FIRST_PATH_ELEMENT_OFFSET) {
2099
2100 RFALSE(path_offset < FIRST_PATH_ELEMENT_OFFSET - 1,
2101 "PAP-8260: invalid offset in the path");
2102
2103 if (PATH_OFFSET_PBUFFER(path, FIRST_PATH_ELEMENT_OFFSET)->
2104 b_blocknr == SB_ROOT_BLOCK(tb->tb_sb)) {
2105
2106 PATH_OFFSET_PBUFFER(path, path_offset - 1) = NULL;
2107 PATH_OFFSET_POSITION(path, path_offset - 1) = 0;
2108 return CARRY_ON;
2109 }
2110
2111 return REPEAT_SEARCH;
2112 }
2113
2114
2115 if (!B_IS_IN_TREE
2116 (bh = PATH_OFFSET_PBUFFER(path, path_offset - 1)))
2117 return REPEAT_SEARCH;
2118
2119 if ((position =
2120 PATH_OFFSET_POSITION(path,
2121 path_offset - 1)) > B_NR_ITEMS(bh))
2122 return REPEAT_SEARCH;
2123
2124
2125 if (B_N_CHILD_NUM(bh, position) !=
2126 PATH_OFFSET_PBUFFER(path, path_offset)->b_blocknr)
2127 return REPEAT_SEARCH;
2128
2129 if (buffer_locked(bh)) {
2130 int depth = reiserfs_write_unlock_nested(tb->tb_sb);
2131 __wait_on_buffer(bh);
2132 reiserfs_write_lock_nested(tb->tb_sb, depth);
2133 if (FILESYSTEM_CHANGED_TB(tb))
2134 return REPEAT_SEARCH;
2135 }
2136
2137
2138
2139
2140
2141 return CARRY_ON;
2142 }
2143
2144
2145
2146
2147
2148
2149
2150
2151 static int get_neighbors(struct tree_balance *tb, int h)
2152 {
2153 int child_position,
2154 path_offset = PATH_H_PATH_OFFSET(tb->tb_path, h + 1);
2155 unsigned long son_number;
2156 struct super_block *sb = tb->tb_sb;
2157 struct buffer_head *bh;
2158 int depth;
2159
2160 PROC_INFO_INC(sb, get_neighbors[h]);
2161
2162 if (tb->lnum[h]) {
2163
2164 PROC_INFO_INC(sb, need_l_neighbor[h]);
2165 bh = PATH_OFFSET_PBUFFER(tb->tb_path, path_offset);
2166
2167 RFALSE(bh == tb->FL[h] &&
2168 !PATH_OFFSET_POSITION(tb->tb_path, path_offset),
2169 "PAP-8270: invalid position in the parent");
2170
2171 child_position =
2172 (bh ==
2173 tb->FL[h]) ? tb->lkey[h] : B_NR_ITEMS(tb->
2174 FL[h]);
2175 son_number = B_N_CHILD_NUM(tb->FL[h], child_position);
2176 depth = reiserfs_write_unlock_nested(tb->tb_sb);
2177 bh = sb_bread(sb, son_number);
2178 reiserfs_write_lock_nested(tb->tb_sb, depth);
2179 if (!bh)
2180 return IO_ERROR;
2181 if (FILESYSTEM_CHANGED_TB(tb)) {
2182 brelse(bh);
2183 PROC_INFO_INC(sb, get_neighbors_restart[h]);
2184 return REPEAT_SEARCH;
2185 }
2186
2187 RFALSE(!B_IS_IN_TREE(tb->FL[h]) ||
2188 child_position > B_NR_ITEMS(tb->FL[h]) ||
2189 B_N_CHILD_NUM(tb->FL[h], child_position) !=
2190 bh->b_blocknr, "PAP-8275: invalid parent");
2191 RFALSE(!B_IS_IN_TREE(bh), "PAP-8280: invalid child");
2192 RFALSE(!h &&
2193 B_FREE_SPACE(bh) !=
2194 MAX_CHILD_SIZE(bh) -
2195 dc_size(B_N_CHILD(tb->FL[0], child_position)),
2196 "PAP-8290: invalid child size of left neighbor");
2197
2198 brelse(tb->L[h]);
2199 tb->L[h] = bh;
2200 }
2201
2202
2203 if (tb->rnum[h]) {
2204 PROC_INFO_INC(sb, need_r_neighbor[h]);
2205 bh = PATH_OFFSET_PBUFFER(tb->tb_path, path_offset);
2206
2207 RFALSE(bh == tb->FR[h] &&
2208 PATH_OFFSET_POSITION(tb->tb_path,
2209 path_offset) >=
2210 B_NR_ITEMS(bh),
2211 "PAP-8295: invalid position in the parent");
2212
2213 child_position =
2214 (bh == tb->FR[h]) ? tb->rkey[h] + 1 : 0;
2215 son_number = B_N_CHILD_NUM(tb->FR[h], child_position);
2216 depth = reiserfs_write_unlock_nested(tb->tb_sb);
2217 bh = sb_bread(sb, son_number);
2218 reiserfs_write_lock_nested(tb->tb_sb, depth);
2219 if (!bh)
2220 return IO_ERROR;
2221 if (FILESYSTEM_CHANGED_TB(tb)) {
2222 brelse(bh);
2223 PROC_INFO_INC(sb, get_neighbors_restart[h]);
2224 return REPEAT_SEARCH;
2225 }
2226 brelse(tb->R[h]);
2227 tb->R[h] = bh;
2228
2229 RFALSE(!h
2230 && B_FREE_SPACE(bh) !=
2231 MAX_CHILD_SIZE(bh) -
2232 dc_size(B_N_CHILD(tb->FR[0], child_position)),
2233 "PAP-8300: invalid child size of right neighbor (%d != %d - %d)",
2234 B_FREE_SPACE(bh), MAX_CHILD_SIZE(bh),
2235 dc_size(B_N_CHILD(tb->FR[0], child_position)));
2236
2237 }
2238 return CARRY_ON;
2239 }
2240
2241 static int get_virtual_node_size(struct super_block *sb, struct buffer_head *bh)
2242 {
2243 int max_num_of_items;
2244 int max_num_of_entries;
2245 unsigned long blocksize = sb->s_blocksize;
2246
2247 #define MIN_NAME_LEN 1
2248
2249 max_num_of_items = (blocksize - BLKH_SIZE) / (IH_SIZE + MIN_ITEM_LEN);
2250 max_num_of_entries = (blocksize - BLKH_SIZE - IH_SIZE) /
2251 (DEH_SIZE + MIN_NAME_LEN);
2252
2253 return sizeof(struct virtual_node) +
2254 max(max_num_of_items * sizeof(struct virtual_item),
2255 sizeof(struct virtual_item) + sizeof(struct direntry_uarea) +
2256 (max_num_of_entries - 1) * sizeof(__u16));
2257 }
2258
2259
2260
2261
2262
2263
2264 static int get_mem_for_virtual_node(struct tree_balance *tb)
2265 {
2266 int check_fs = 0;
2267 int size;
2268 char *buf;
2269
2270 size = get_virtual_node_size(tb->tb_sb, PATH_PLAST_BUFFER(tb->tb_path));
2271
2272
2273 if (size > tb->vn_buf_size) {
2274 if (tb->vn_buf) {
2275
2276 kfree(tb->vn_buf);
2277
2278 check_fs = 1;
2279 }
2280
2281
2282 tb->vn_buf_size = size;
2283
2284
2285 buf = kmalloc(size, GFP_ATOMIC | __GFP_NOWARN);
2286 if (!buf) {
2287
2288
2289
2290
2291
2292
2293 free_buffers_in_tb(tb);
2294 buf = kmalloc(size, GFP_NOFS);
2295 if (!buf) {
2296 tb->vn_buf_size = 0;
2297 }
2298 tb->vn_buf = buf;
2299 schedule();
2300 return REPEAT_SEARCH;
2301 }
2302
2303 tb->vn_buf = buf;
2304 }
2305
2306 if (check_fs && FILESYSTEM_CHANGED_TB(tb))
2307 return REPEAT_SEARCH;
2308
2309 return CARRY_ON;
2310 }
2311
2312 #ifdef CONFIG_REISERFS_CHECK
2313 static void tb_buffer_sanity_check(struct super_block *sb,
2314 struct buffer_head *bh,
2315 const char *descr, int level)
2316 {
2317 if (bh) {
2318 if (atomic_read(&(bh->b_count)) <= 0)
2319
2320 reiserfs_panic(sb, "jmacd-1", "negative or zero "
2321 "reference counter for buffer %s[%d] "
2322 "(%b)", descr, level, bh);
2323
2324 if (!buffer_uptodate(bh))
2325 reiserfs_panic(sb, "jmacd-2", "buffer is not up "
2326 "to date %s[%d] (%b)",
2327 descr, level, bh);
2328
2329 if (!B_IS_IN_TREE(bh))
2330 reiserfs_panic(sb, "jmacd-3", "buffer is not "
2331 "in tree %s[%d] (%b)",
2332 descr, level, bh);
2333
2334 if (bh->b_bdev != sb->s_bdev)
2335 reiserfs_panic(sb, "jmacd-4", "buffer has wrong "
2336 "device %s[%d] (%b)",
2337 descr, level, bh);
2338
2339 if (bh->b_size != sb->s_blocksize)
2340 reiserfs_panic(sb, "jmacd-5", "buffer has wrong "
2341 "blocksize %s[%d] (%b)",
2342 descr, level, bh);
2343
2344 if (bh->b_blocknr > SB_BLOCK_COUNT(sb))
2345 reiserfs_panic(sb, "jmacd-6", "buffer block "
2346 "number too high %s[%d] (%b)",
2347 descr, level, bh);
2348 }
2349 }
2350 #else
2351 static void tb_buffer_sanity_check(struct super_block *sb,
2352 struct buffer_head *bh,
2353 const char *descr, int level)
2354 {;
2355 }
2356 #endif
2357
2358 static int clear_all_dirty_bits(struct super_block *s, struct buffer_head *bh)
2359 {
2360 return reiserfs_prepare_for_journal(s, bh, 0);
2361 }
2362
2363 static int wait_tb_buffers_until_unlocked(struct tree_balance *tb)
2364 {
2365 struct buffer_head *locked;
2366 #ifdef CONFIG_REISERFS_CHECK
2367 int repeat_counter = 0;
2368 #endif
2369 int i;
2370
2371 do {
2372
2373 locked = NULL;
2374
2375 for (i = tb->tb_path->path_length;
2376 !locked && i > ILLEGAL_PATH_ELEMENT_OFFSET; i--) {
2377 if (PATH_OFFSET_PBUFFER(tb->tb_path, i)) {
2378
2379
2380
2381
2382
2383 #ifdef CONFIG_REISERFS_CHECK
2384 if (PATH_PLAST_BUFFER(tb->tb_path) ==
2385 PATH_OFFSET_PBUFFER(tb->tb_path, i))
2386 tb_buffer_sanity_check(tb->tb_sb,
2387 PATH_OFFSET_PBUFFER
2388 (tb->tb_path,
2389 i), "S",
2390 tb->tb_path->
2391 path_length - i);
2392 #endif
2393 if (!clear_all_dirty_bits(tb->tb_sb,
2394 PATH_OFFSET_PBUFFER
2395 (tb->tb_path,
2396 i))) {
2397 locked =
2398 PATH_OFFSET_PBUFFER(tb->tb_path,
2399 i);
2400 }
2401 }
2402 }
2403
2404 for (i = 0; !locked && i < MAX_HEIGHT && tb->insert_size[i];
2405 i++) {
2406
2407 if (tb->lnum[i]) {
2408
2409 if (tb->L[i]) {
2410 tb_buffer_sanity_check(tb->tb_sb,
2411 tb->L[i],
2412 "L", i);
2413 if (!clear_all_dirty_bits
2414 (tb->tb_sb, tb->L[i]))
2415 locked = tb->L[i];
2416 }
2417
2418 if (!locked && tb->FL[i]) {
2419 tb_buffer_sanity_check(tb->tb_sb,
2420 tb->FL[i],
2421 "FL", i);
2422 if (!clear_all_dirty_bits
2423 (tb->tb_sb, tb->FL[i]))
2424 locked = tb->FL[i];
2425 }
2426
2427 if (!locked && tb->CFL[i]) {
2428 tb_buffer_sanity_check(tb->tb_sb,
2429 tb->CFL[i],
2430 "CFL", i);
2431 if (!clear_all_dirty_bits
2432 (tb->tb_sb, tb->CFL[i]))
2433 locked = tb->CFL[i];
2434 }
2435
2436 }
2437
2438 if (!locked && (tb->rnum[i])) {
2439
2440 if (tb->R[i]) {
2441 tb_buffer_sanity_check(tb->tb_sb,
2442 tb->R[i],
2443 "R", i);
2444 if (!clear_all_dirty_bits
2445 (tb->tb_sb, tb->R[i]))
2446 locked = tb->R[i];
2447 }
2448
2449 if (!locked && tb->FR[i]) {
2450 tb_buffer_sanity_check(tb->tb_sb,
2451 tb->FR[i],
2452 "FR", i);
2453 if (!clear_all_dirty_bits
2454 (tb->tb_sb, tb->FR[i]))
2455 locked = tb->FR[i];
2456 }
2457
2458 if (!locked && tb->CFR[i]) {
2459 tb_buffer_sanity_check(tb->tb_sb,
2460 tb->CFR[i],
2461 "CFR", i);
2462 if (!clear_all_dirty_bits
2463 (tb->tb_sb, tb->CFR[i]))
2464 locked = tb->CFR[i];
2465 }
2466 }
2467 }
2468
2469
2470
2471
2472
2473
2474
2475
2476
2477
2478 for (i = 0; !locked && i < MAX_FEB_SIZE; i++) {
2479 if (tb->FEB[i]) {
2480 if (!clear_all_dirty_bits
2481 (tb->tb_sb, tb->FEB[i]))
2482 locked = tb->FEB[i];
2483 }
2484 }
2485
2486 if (locked) {
2487 int depth;
2488 #ifdef CONFIG_REISERFS_CHECK
2489 repeat_counter++;
2490 if ((repeat_counter % 10000) == 0) {
2491 reiserfs_warning(tb->tb_sb, "reiserfs-8200",
2492 "too many iterations waiting "
2493 "for buffer to unlock "
2494 "(%b)", locked);
2495
2496
2497
2498 return (FILESYSTEM_CHANGED_TB(tb)) ?
2499 REPEAT_SEARCH : CARRY_ON;
2500 }
2501 #endif
2502 depth = reiserfs_write_unlock_nested(tb->tb_sb);
2503 __wait_on_buffer(locked);
2504 reiserfs_write_lock_nested(tb->tb_sb, depth);
2505 if (FILESYSTEM_CHANGED_TB(tb))
2506 return REPEAT_SEARCH;
2507 }
2508
2509 } while (locked);
2510
2511 return CARRY_ON;
2512 }
2513
2514
2515
2516
2517
2518
2519
2520
2521
2522
2523
2524
2525
2526
2527
2528
2529
2530
2531
2532
2533
2534
2535
2536
2537
2538
2539
2540
2541
2542
2543
2544
2545 int fix_nodes(int op_mode, struct tree_balance *tb,
2546 struct item_head *ins_ih, const void *data)
2547 {
2548 int ret, h, item_num = PATH_LAST_POSITION(tb->tb_path);
2549 int pos_in_item;
2550
2551
2552
2553
2554
2555 int wait_tb_buffers_run = 0;
2556 struct buffer_head *tbS0 = PATH_PLAST_BUFFER(tb->tb_path);
2557
2558 ++REISERFS_SB(tb->tb_sb)->s_fix_nodes;
2559
2560 pos_in_item = tb->tb_path->pos_in_item;
2561
2562 tb->fs_gen = get_generation(tb->tb_sb);
2563
2564
2565
2566
2567
2568
2569
2570 reiserfs_prepare_for_journal(tb->tb_sb,
2571 SB_BUFFER_WITH_SB(tb->tb_sb), 1);
2572 journal_mark_dirty(tb->transaction_handle,
2573 SB_BUFFER_WITH_SB(tb->tb_sb));
2574 if (FILESYSTEM_CHANGED_TB(tb))
2575 return REPEAT_SEARCH;
2576
2577
2578 if (buffer_locked(tbS0)) {
2579 int depth = reiserfs_write_unlock_nested(tb->tb_sb);
2580 __wait_on_buffer(tbS0);
2581 reiserfs_write_lock_nested(tb->tb_sb, depth);
2582 if (FILESYSTEM_CHANGED_TB(tb))
2583 return REPEAT_SEARCH;
2584 }
2585 #ifdef CONFIG_REISERFS_CHECK
2586 if (REISERFS_SB(tb->tb_sb)->cur_tb) {
2587 print_cur_tb("fix_nodes");
2588 reiserfs_panic(tb->tb_sb, "PAP-8305",
2589 "there is pending do_balance");
2590 }
2591
2592 if (!buffer_uptodate(tbS0) || !B_IS_IN_TREE(tbS0))
2593 reiserfs_panic(tb->tb_sb, "PAP-8320", "S[0] (%b %z) is "
2594 "not uptodate at the beginning of fix_nodes "
2595 "or not in tree (mode %c)",
2596 tbS0, tbS0, op_mode);
2597
2598
2599 switch (op_mode) {
2600 case M_INSERT:
2601 if (item_num <= 0 || item_num > B_NR_ITEMS(tbS0))
2602 reiserfs_panic(tb->tb_sb, "PAP-8330", "Incorrect "
2603 "item number %d (in S0 - %d) in case "
2604 "of insert", item_num,
2605 B_NR_ITEMS(tbS0));
2606 break;
2607 case M_PASTE:
2608 case M_DELETE:
2609 case M_CUT:
2610 if (item_num < 0 || item_num >= B_NR_ITEMS(tbS0)) {
2611 print_block(tbS0, 0, -1, -1);
2612 reiserfs_panic(tb->tb_sb, "PAP-8335", "Incorrect "
2613 "item number(%d); mode = %c "
2614 "insert_size = %d",
2615 item_num, op_mode,
2616 tb->insert_size[0]);
2617 }
2618 break;
2619 default:
2620 reiserfs_panic(tb->tb_sb, "PAP-8340", "Incorrect mode "
2621 "of operation");
2622 }
2623 #endif
2624
2625 if (get_mem_for_virtual_node(tb) == REPEAT_SEARCH)
2626
2627 return REPEAT_SEARCH;
2628
2629
2630 for (h = 0; h < MAX_HEIGHT && tb->insert_size[h]; h++) {
2631 ret = get_direct_parent(tb, h);
2632 if (ret != CARRY_ON)
2633 goto repeat;
2634
2635 ret = check_balance(op_mode, tb, h, item_num,
2636 pos_in_item, ins_ih, data);
2637 if (ret != CARRY_ON) {
2638 if (ret == NO_BALANCING_NEEDED) {
2639
2640 ret = get_neighbors(tb, h);
2641 if (ret != CARRY_ON)
2642 goto repeat;
2643 if (h != MAX_HEIGHT - 1)
2644 tb->insert_size[h + 1] = 0;
2645
2646
2647
2648
2649 break;
2650 }
2651 goto repeat;
2652 }
2653
2654 ret = get_neighbors(tb, h);
2655 if (ret != CARRY_ON)
2656 goto repeat;
2657
2658
2659
2660
2661
2662 ret = get_empty_nodes(tb, h);
2663 if (ret != CARRY_ON)
2664 goto repeat;
2665
2666
2667
2668
2669
2670 if (!PATH_H_PBUFFER(tb->tb_path, h)) {
2671
2672 RFALSE(tb->blknum[h] != 1,
2673 "PAP-8350: creating new empty root");
2674
2675 if (h < MAX_HEIGHT - 1)
2676 tb->insert_size[h + 1] = 0;
2677 } else if (!PATH_H_PBUFFER(tb->tb_path, h + 1)) {
2678
2679
2680
2681
2682
2683
2684 if (tb->blknum[h] > 1) {
2685
2686 RFALSE(h == MAX_HEIGHT - 1,
2687 "PAP-8355: attempt to create too high of a tree");
2688
2689 tb->insert_size[h + 1] =
2690 (DC_SIZE +
2691 KEY_SIZE) * (tb->blknum[h] - 1) +
2692 DC_SIZE;
2693 } else if (h < MAX_HEIGHT - 1)
2694 tb->insert_size[h + 1] = 0;
2695 } else
2696 tb->insert_size[h + 1] =
2697 (DC_SIZE + KEY_SIZE) * (tb->blknum[h] - 1);
2698 }
2699
2700 ret = wait_tb_buffers_until_unlocked(tb);
2701 if (ret == CARRY_ON) {
2702 if (FILESYSTEM_CHANGED_TB(tb)) {
2703 wait_tb_buffers_run = 1;
2704 ret = REPEAT_SEARCH;
2705 goto repeat;
2706 } else {
2707 return CARRY_ON;
2708 }
2709 } else {
2710 wait_tb_buffers_run = 1;
2711 goto repeat;
2712 }
2713
2714 repeat:
2715
2716
2717
2718
2719
2720
2721
2722 {
2723 int i;
2724
2725
2726 if (wait_tb_buffers_run) {
2727 pathrelse_and_restore(tb->tb_sb, tb->tb_path);
2728 } else {
2729 pathrelse(tb->tb_path);
2730 }
2731
2732 for (i = 0; i < MAX_HEIGHT; i++) {
2733 if (wait_tb_buffers_run) {
2734 reiserfs_restore_prepared_buffer(tb->tb_sb,
2735 tb->L[i]);
2736 reiserfs_restore_prepared_buffer(tb->tb_sb,
2737 tb->R[i]);
2738 reiserfs_restore_prepared_buffer(tb->tb_sb,
2739 tb->FL[i]);
2740 reiserfs_restore_prepared_buffer(tb->tb_sb,
2741 tb->FR[i]);
2742 reiserfs_restore_prepared_buffer(tb->tb_sb,
2743 tb->
2744 CFL[i]);
2745 reiserfs_restore_prepared_buffer(tb->tb_sb,
2746 tb->
2747 CFR[i]);
2748 }
2749
2750 brelse(tb->L[i]);
2751 brelse(tb->R[i]);
2752 brelse(tb->FL[i]);
2753 brelse(tb->FR[i]);
2754 brelse(tb->CFL[i]);
2755 brelse(tb->CFR[i]);
2756
2757 tb->L[i] = NULL;
2758 tb->R[i] = NULL;
2759 tb->FL[i] = NULL;
2760 tb->FR[i] = NULL;
2761 tb->CFL[i] = NULL;
2762 tb->CFR[i] = NULL;
2763 }
2764
2765 if (wait_tb_buffers_run) {
2766 for (i = 0; i < MAX_FEB_SIZE; i++) {
2767 if (tb->FEB[i])
2768 reiserfs_restore_prepared_buffer
2769 (tb->tb_sb, tb->FEB[i]);
2770 }
2771 }
2772 return ret;
2773 }
2774
2775 }
2776
2777 void unfix_nodes(struct tree_balance *tb)
2778 {
2779 int i;
2780
2781
2782 pathrelse_and_restore(tb->tb_sb, tb->tb_path);
2783
2784
2785 for (i = 0; i < MAX_HEIGHT; i++) {
2786 reiserfs_restore_prepared_buffer(tb->tb_sb, tb->L[i]);
2787 reiserfs_restore_prepared_buffer(tb->tb_sb, tb->R[i]);
2788 reiserfs_restore_prepared_buffer(tb->tb_sb, tb->FL[i]);
2789 reiserfs_restore_prepared_buffer(tb->tb_sb, tb->FR[i]);
2790 reiserfs_restore_prepared_buffer(tb->tb_sb, tb->CFL[i]);
2791 reiserfs_restore_prepared_buffer(tb->tb_sb, tb->CFR[i]);
2792
2793 brelse(tb->L[i]);
2794 brelse(tb->R[i]);
2795 brelse(tb->FL[i]);
2796 brelse(tb->FR[i]);
2797 brelse(tb->CFL[i]);
2798 brelse(tb->CFR[i]);
2799 }
2800
2801
2802 for (i = 0; i < MAX_FEB_SIZE; i++) {
2803 if (tb->FEB[i]) {
2804 b_blocknr_t blocknr = tb->FEB[i]->b_blocknr;
2805
2806
2807
2808
2809 brelse(tb->FEB[i]);
2810 reiserfs_free_block(tb->transaction_handle, NULL,
2811 blocknr, 0);
2812 }
2813 if (tb->used[i]) {
2814
2815 brelse(tb->used[i]);
2816 }
2817 }
2818
2819 kfree(tb->vn_buf);
2820
2821 }