This source file includes following definitions.
- internal_define_dest_src_infos
- internal_insert_childs
- internal_delete_pointers_items
- internal_delete_childs
- internal_copy_pointers_items
- internal_move_pointers_items
- internal_insert_key
- internal_shift_left
- internal_shift1_left
- internal_shift_right
- internal_shift1_right
- balance_internal_when_delete
- replace_lkey
- replace_rkey
- balance_internal
1
2
3
4
5 #include <linux/uaccess.h>
6 #include <linux/string.h>
7 #include <linux/time.h>
8 #include "reiserfs.h"
9 #include <linux/buffer_head.h>
10
11
12 int balance_internal(struct tree_balance *,
13 int, int, struct item_head *, struct buffer_head **);
14
15
16
17
18
19 #define INTERNAL_SHIFT_FROM_S_TO_L 0
20 #define INTERNAL_SHIFT_FROM_R_TO_S 1
21 #define INTERNAL_SHIFT_FROM_L_TO_S 2
22 #define INTERNAL_SHIFT_FROM_S_TO_R 3
23 #define INTERNAL_INSERT_TO_S 4
24 #define INTERNAL_INSERT_TO_L 5
25 #define INTERNAL_INSERT_TO_R 6
26
27 static void internal_define_dest_src_infos(int shift_mode,
28 struct tree_balance *tb,
29 int h,
30 struct buffer_info *dest_bi,
31 struct buffer_info *src_bi,
32 int *d_key, struct buffer_head **cf)
33 {
34 memset(dest_bi, 0, sizeof(struct buffer_info));
35 memset(src_bi, 0, sizeof(struct buffer_info));
36
37 switch (shift_mode) {
38
39
40 case INTERNAL_SHIFT_FROM_S_TO_L:
41 src_bi->tb = tb;
42 src_bi->bi_bh = PATH_H_PBUFFER(tb->tb_path, h);
43 src_bi->bi_parent = PATH_H_PPARENT(tb->tb_path, h);
44 src_bi->bi_position = PATH_H_POSITION(tb->tb_path, h + 1);
45 dest_bi->tb = tb;
46 dest_bi->bi_bh = tb->L[h];
47 dest_bi->bi_parent = tb->FL[h];
48 dest_bi->bi_position = get_left_neighbor_position(tb, h);
49 *d_key = tb->lkey[h];
50 *cf = tb->CFL[h];
51 break;
52 case INTERNAL_SHIFT_FROM_L_TO_S:
53 src_bi->tb = tb;
54 src_bi->bi_bh = tb->L[h];
55 src_bi->bi_parent = tb->FL[h];
56 src_bi->bi_position = get_left_neighbor_position(tb, h);
57 dest_bi->tb = tb;
58 dest_bi->bi_bh = PATH_H_PBUFFER(tb->tb_path, h);
59 dest_bi->bi_parent = PATH_H_PPARENT(tb->tb_path, h);
60
61 dest_bi->bi_position = PATH_H_POSITION(tb->tb_path, h + 1);
62 *d_key = tb->lkey[h];
63 *cf = tb->CFL[h];
64 break;
65
66
67 case INTERNAL_SHIFT_FROM_R_TO_S:
68 src_bi->tb = tb;
69 src_bi->bi_bh = tb->R[h];
70 src_bi->bi_parent = tb->FR[h];
71 src_bi->bi_position = get_right_neighbor_position(tb, h);
72 dest_bi->tb = tb;
73 dest_bi->bi_bh = PATH_H_PBUFFER(tb->tb_path, h);
74 dest_bi->bi_parent = PATH_H_PPARENT(tb->tb_path, h);
75 dest_bi->bi_position = PATH_H_POSITION(tb->tb_path, h + 1);
76 *d_key = tb->rkey[h];
77 *cf = tb->CFR[h];
78 break;
79
80 case INTERNAL_SHIFT_FROM_S_TO_R:
81 src_bi->tb = tb;
82 src_bi->bi_bh = PATH_H_PBUFFER(tb->tb_path, h);
83 src_bi->bi_parent = PATH_H_PPARENT(tb->tb_path, h);
84 src_bi->bi_position = PATH_H_POSITION(tb->tb_path, h + 1);
85 dest_bi->tb = tb;
86 dest_bi->bi_bh = tb->R[h];
87 dest_bi->bi_parent = tb->FR[h];
88 dest_bi->bi_position = get_right_neighbor_position(tb, h);
89 *d_key = tb->rkey[h];
90 *cf = tb->CFR[h];
91 break;
92
93 case INTERNAL_INSERT_TO_L:
94 dest_bi->tb = tb;
95 dest_bi->bi_bh = tb->L[h];
96 dest_bi->bi_parent = tb->FL[h];
97 dest_bi->bi_position = get_left_neighbor_position(tb, h);
98 break;
99
100 case INTERNAL_INSERT_TO_S:
101 dest_bi->tb = tb;
102 dest_bi->bi_bh = PATH_H_PBUFFER(tb->tb_path, h);
103 dest_bi->bi_parent = PATH_H_PPARENT(tb->tb_path, h);
104 dest_bi->bi_position = PATH_H_POSITION(tb->tb_path, h + 1);
105 break;
106
107 case INTERNAL_INSERT_TO_R:
108 dest_bi->tb = tb;
109 dest_bi->bi_bh = tb->R[h];
110 dest_bi->bi_parent = tb->FR[h];
111 dest_bi->bi_position = get_right_neighbor_position(tb, h);
112 break;
113
114 default:
115 reiserfs_panic(tb->tb_sb, "ibalance-1",
116 "shift type is unknown (%d)",
117 shift_mode);
118 }
119 }
120
121
122
123
124
125
126 static void internal_insert_childs(struct buffer_info *cur_bi,
127 int to, int count,
128 struct item_head *inserted,
129 struct buffer_head **bh)
130 {
131 struct buffer_head *cur = cur_bi->bi_bh;
132 struct block_head *blkh;
133 int nr;
134 struct reiserfs_key *ih;
135 struct disk_child new_dc[2];
136 struct disk_child *dc;
137 int i;
138
139 if (count <= 0)
140 return;
141
142 blkh = B_BLK_HEAD(cur);
143 nr = blkh_nr_item(blkh);
144
145 RFALSE(count > 2, "too many children (%d) are to be inserted", count);
146 RFALSE(B_FREE_SPACE(cur) < count * (KEY_SIZE + DC_SIZE),
147 "no enough free space (%d), needed %d bytes",
148 B_FREE_SPACE(cur), count * (KEY_SIZE + DC_SIZE));
149
150
151 dc = B_N_CHILD(cur, to + 1);
152
153 memmove(dc + count, dc, (nr + 1 - (to + 1)) * DC_SIZE);
154
155
156 for (i = 0; i < count; i++) {
157 put_dc_size(&new_dc[i],
158 MAX_CHILD_SIZE(bh[i]) - B_FREE_SPACE(bh[i]));
159 put_dc_block_number(&new_dc[i], bh[i]->b_blocknr);
160 }
161 memcpy(dc, new_dc, DC_SIZE * count);
162
163
164 ih = internal_key(cur, ((to == -1) ? 0 : to));
165
166 memmove(ih + count, ih,
167 (nr - to) * KEY_SIZE + (nr + 1 + count) * DC_SIZE);
168
169
170 memcpy(ih, inserted, KEY_SIZE);
171 if (count > 1)
172 memcpy(ih + 1, inserted + 1, KEY_SIZE);
173
174
175 set_blkh_nr_item(blkh, blkh_nr_item(blkh) + count);
176 set_blkh_free_space(blkh,
177 blkh_free_space(blkh) - count * (DC_SIZE +
178 KEY_SIZE));
179
180 do_balance_mark_internal_dirty(cur_bi->tb, cur, 0);
181
182
183 check_internal(cur);
184
185
186 if (cur_bi->bi_parent) {
187 struct disk_child *t_dc =
188 B_N_CHILD(cur_bi->bi_parent, cur_bi->bi_position);
189 put_dc_size(t_dc,
190 dc_size(t_dc) + (count * (DC_SIZE + KEY_SIZE)));
191 do_balance_mark_internal_dirty(cur_bi->tb, cur_bi->bi_parent,
192 0);
193
194
195 check_internal(cur_bi->bi_parent);
196
197 }
198
199 }
200
201
202
203
204
205 static void internal_delete_pointers_items(struct buffer_info *cur_bi,
206 int first_p,
207 int first_i, int del_num)
208 {
209 struct buffer_head *cur = cur_bi->bi_bh;
210 int nr;
211 struct block_head *blkh;
212 struct reiserfs_key *key;
213 struct disk_child *dc;
214
215 RFALSE(cur == NULL, "buffer is 0");
216 RFALSE(del_num < 0,
217 "negative number of items (%d) can not be deleted", del_num);
218 RFALSE(first_p < 0 || first_p + del_num > B_NR_ITEMS(cur) + 1
219 || first_i < 0,
220 "first pointer order (%d) < 0 or "
221 "no so many pointers (%d), only (%d) or "
222 "first key order %d < 0", first_p, first_p + del_num,
223 B_NR_ITEMS(cur) + 1, first_i);
224 if (del_num == 0)
225 return;
226
227 blkh = B_BLK_HEAD(cur);
228 nr = blkh_nr_item(blkh);
229
230 if (first_p == 0 && del_num == nr + 1) {
231 RFALSE(first_i != 0,
232 "1st deleted key must have order 0, not %d", first_i);
233 make_empty_node(cur_bi);
234 return;
235 }
236
237 RFALSE(first_i + del_num > B_NR_ITEMS(cur),
238 "first_i = %d del_num = %d "
239 "no so many keys (%d) in the node (%b)(%z)",
240 first_i, del_num, first_i + del_num, cur, cur);
241
242
243 dc = B_N_CHILD(cur, first_p);
244
245 memmove(dc, dc + del_num, (nr + 1 - first_p - del_num) * DC_SIZE);
246 key = internal_key(cur, first_i);
247 memmove(key, key + del_num,
248 (nr - first_i - del_num) * KEY_SIZE + (nr + 1 -
249 del_num) * DC_SIZE);
250
251
252 set_blkh_nr_item(blkh, blkh_nr_item(blkh) - del_num);
253 set_blkh_free_space(blkh,
254 blkh_free_space(blkh) +
255 (del_num * (KEY_SIZE + DC_SIZE)));
256
257 do_balance_mark_internal_dirty(cur_bi->tb, cur, 0);
258
259 check_internal(cur);
260
261
262 if (cur_bi->bi_parent) {
263 struct disk_child *t_dc;
264 t_dc = B_N_CHILD(cur_bi->bi_parent, cur_bi->bi_position);
265 put_dc_size(t_dc,
266 dc_size(t_dc) - (del_num * (KEY_SIZE + DC_SIZE)));
267
268 do_balance_mark_internal_dirty(cur_bi->tb, cur_bi->bi_parent,
269 0);
270
271 check_internal(cur_bi->bi_parent);
272
273 }
274 }
275
276
277 static void internal_delete_childs(struct buffer_info *cur_bi, int from, int n)
278 {
279 int i_from;
280
281 i_from = (from == 0) ? from : from - 1;
282
283
284
285
286
287 internal_delete_pointers_items(cur_bi, from, i_from, n);
288 }
289
290
291
292
293
294
295
296
297
298 static void internal_copy_pointers_items(struct buffer_info *dest_bi,
299 struct buffer_head *src,
300 int last_first, int cpy_num)
301 {
302
303
304
305
306
307 struct buffer_head *dest = dest_bi->bi_bh;
308 int nr_dest, nr_src;
309 int dest_order, src_order;
310 struct block_head *blkh;
311 struct reiserfs_key *key;
312 struct disk_child *dc;
313
314 nr_src = B_NR_ITEMS(src);
315
316 RFALSE(dest == NULL || src == NULL,
317 "src (%p) or dest (%p) buffer is 0", src, dest);
318 RFALSE(last_first != FIRST_TO_LAST && last_first != LAST_TO_FIRST,
319 "invalid last_first parameter (%d)", last_first);
320 RFALSE(nr_src < cpy_num - 1,
321 "no so many items (%d) in src (%d)", cpy_num, nr_src);
322 RFALSE(cpy_num < 0, "cpy_num less than 0 (%d)", cpy_num);
323 RFALSE(cpy_num - 1 + B_NR_ITEMS(dest) > (int)MAX_NR_KEY(dest),
324 "cpy_num (%d) + item number in dest (%d) can not be > MAX_NR_KEY(%d)",
325 cpy_num, B_NR_ITEMS(dest), MAX_NR_KEY(dest));
326
327 if (cpy_num == 0)
328 return;
329
330
331 blkh = B_BLK_HEAD(dest);
332 nr_dest = blkh_nr_item(blkh);
333
334
335
336 (last_first == LAST_TO_FIRST) ? (dest_order = 0, src_order =
337 nr_src - cpy_num + 1) : (dest_order =
338 nr_dest,
339 src_order =
340 0);
341
342
343 dc = B_N_CHILD(dest, dest_order);
344
345 memmove(dc + cpy_num, dc, (nr_dest - dest_order) * DC_SIZE);
346
347
348 memcpy(dc, B_N_CHILD(src, src_order), DC_SIZE * cpy_num);
349
350
351 key = internal_key(dest, dest_order);
352 memmove(key + cpy_num - 1, key,
353 KEY_SIZE * (nr_dest - dest_order) + DC_SIZE * (nr_dest +
354 cpy_num));
355
356
357 memcpy(key, internal_key(src, src_order), KEY_SIZE * (cpy_num - 1));
358
359
360 set_blkh_nr_item(blkh, blkh_nr_item(blkh) + (cpy_num - 1));
361 set_blkh_free_space(blkh,
362 blkh_free_space(blkh) - (KEY_SIZE * (cpy_num - 1) +
363 DC_SIZE * cpy_num));
364
365 do_balance_mark_internal_dirty(dest_bi->tb, dest, 0);
366
367
368 check_internal(dest);
369
370
371 if (dest_bi->bi_parent) {
372 struct disk_child *t_dc;
373 t_dc = B_N_CHILD(dest_bi->bi_parent, dest_bi->bi_position);
374 put_dc_size(t_dc,
375 dc_size(t_dc) + (KEY_SIZE * (cpy_num - 1) +
376 DC_SIZE * cpy_num));
377
378 do_balance_mark_internal_dirty(dest_bi->tb, dest_bi->bi_parent,
379 0);
380
381 check_internal(dest_bi->bi_parent);
382
383 }
384
385 }
386
387
388
389
390
391
392
393
394 static void internal_move_pointers_items(struct buffer_info *dest_bi,
395 struct buffer_info *src_bi,
396 int last_first, int cpy_num,
397 int del_par)
398 {
399 int first_pointer;
400 int first_item;
401
402 internal_copy_pointers_items(dest_bi, src_bi->bi_bh, last_first,
403 cpy_num);
404
405 if (last_first == FIRST_TO_LAST) {
406 first_pointer = 0;
407 first_item = 0;
408
409
410
411
412 internal_delete_pointers_items(src_bi, first_pointer,
413 first_item, cpy_num - del_par);
414 } else {
415 int i, j;
416
417 i = (cpy_num - del_par ==
418 (j =
419 B_NR_ITEMS(src_bi->bi_bh)) + 1) ? 0 : j - cpy_num +
420 del_par;
421
422 internal_delete_pointers_items(src_bi,
423 j + 1 - cpy_num + del_par, i,
424 cpy_num - del_par);
425 }
426 }
427
428
429 static void internal_insert_key(struct buffer_info *dest_bi,
430
431 int dest_position_before,
432 struct buffer_head *src, int src_position)
433 {
434 struct buffer_head *dest = dest_bi->bi_bh;
435 int nr;
436 struct block_head *blkh;
437 struct reiserfs_key *key;
438
439 RFALSE(dest == NULL || src == NULL,
440 "source(%p) or dest(%p) buffer is 0", src, dest);
441 RFALSE(dest_position_before < 0 || src_position < 0,
442 "source(%d) or dest(%d) key number less than 0",
443 src_position, dest_position_before);
444 RFALSE(dest_position_before > B_NR_ITEMS(dest) ||
445 src_position >= B_NR_ITEMS(src),
446 "invalid position in dest (%d (key number %d)) or in src (%d (key number %d))",
447 dest_position_before, B_NR_ITEMS(dest),
448 src_position, B_NR_ITEMS(src));
449 RFALSE(B_FREE_SPACE(dest) < KEY_SIZE,
450 "no enough free space (%d) in dest buffer", B_FREE_SPACE(dest));
451
452 blkh = B_BLK_HEAD(dest);
453 nr = blkh_nr_item(blkh);
454
455
456 key = internal_key(dest, dest_position_before);
457 memmove(key + 1, key,
458 (nr - dest_position_before) * KEY_SIZE + (nr + 1) * DC_SIZE);
459
460
461 memcpy(key, internal_key(src, src_position), KEY_SIZE);
462
463
464
465 set_blkh_nr_item(blkh, blkh_nr_item(blkh) + 1);
466 set_blkh_free_space(blkh, blkh_free_space(blkh) - KEY_SIZE);
467
468 do_balance_mark_internal_dirty(dest_bi->tb, dest, 0);
469
470 if (dest_bi->bi_parent) {
471 struct disk_child *t_dc;
472 t_dc = B_N_CHILD(dest_bi->bi_parent, dest_bi->bi_position);
473 put_dc_size(t_dc, dc_size(t_dc) + KEY_SIZE);
474
475 do_balance_mark_internal_dirty(dest_bi->tb, dest_bi->bi_parent,
476 0);
477 }
478 }
479
480
481
482
483
484
485
486
487
488 static void internal_shift_left(
489
490
491
492 int mode,
493 struct tree_balance *tb,
494 int h, int pointer_amount)
495 {
496 struct buffer_info dest_bi, src_bi;
497 struct buffer_head *cf;
498 int d_key_position;
499
500 internal_define_dest_src_infos(mode, tb, h, &dest_bi, &src_bi,
501 &d_key_position, &cf);
502
503
504
505 if (pointer_amount) {
506
507
508
509
510 internal_insert_key(&dest_bi, B_NR_ITEMS(dest_bi.bi_bh), cf,
511 d_key_position);
512
513 if (B_NR_ITEMS(src_bi.bi_bh) == pointer_amount - 1) {
514 if (src_bi.bi_position == 0)
515 replace_key(tb, cf, d_key_position,
516 src_bi.
517 bi_parent , 0);
518 } else
519 replace_key(tb, cf, d_key_position, src_bi.bi_bh,
520 pointer_amount - 1);
521 }
522
523 internal_move_pointers_items(&dest_bi, &src_bi, FIRST_TO_LAST,
524 pointer_amount, 0);
525
526 }
527
528
529
530
531
532
533
534 static void internal_shift1_left(struct tree_balance *tb,
535 int h, int pointer_amount)
536 {
537 struct buffer_info dest_bi, src_bi;
538 struct buffer_head *cf;
539 int d_key_position;
540
541 internal_define_dest_src_infos(INTERNAL_SHIFT_FROM_S_TO_L, tb, h,
542 &dest_bi, &src_bi, &d_key_position, &cf);
543
544
545 if (pointer_amount > 0)
546 internal_insert_key(&dest_bi, B_NR_ITEMS(dest_bi.bi_bh), cf,
547 d_key_position);
548
549
550 internal_move_pointers_items(&dest_bi, &src_bi, FIRST_TO_LAST,
551 pointer_amount, 1);
552 }
553
554
555
556
557
558
559
560 static void internal_shift_right(
561
562
563
564 int mode,
565 struct tree_balance *tb,
566 int h, int pointer_amount)
567 {
568 struct buffer_info dest_bi, src_bi;
569 struct buffer_head *cf;
570 int d_key_position;
571 int nr;
572
573 internal_define_dest_src_infos(mode, tb, h, &dest_bi, &src_bi,
574 &d_key_position, &cf);
575
576 nr = B_NR_ITEMS(src_bi.bi_bh);
577
578 if (pointer_amount > 0) {
579
580
581
582
583 internal_insert_key(&dest_bi, 0, cf, d_key_position);
584 if (nr == pointer_amount - 1) {
585 RFALSE(src_bi.bi_bh != PATH_H_PBUFFER(tb->tb_path, h) ||
586 dest_bi.bi_bh != tb->R[h],
587 "src (%p) must be == tb->S[h](%p) when it disappears",
588 src_bi.bi_bh, PATH_H_PBUFFER(tb->tb_path, h));
589
590 if (tb->CFL[h])
591 replace_key(tb, cf, d_key_position, tb->CFL[h],
592 tb->lkey[h]);
593 } else
594 replace_key(tb, cf, d_key_position, src_bi.bi_bh,
595 nr - pointer_amount);
596 }
597
598
599 internal_move_pointers_items(&dest_bi, &src_bi, LAST_TO_FIRST,
600 pointer_amount, 0);
601 }
602
603
604
605
606
607
608
609 static void internal_shift1_right(struct tree_balance *tb,
610 int h, int pointer_amount)
611 {
612 struct buffer_info dest_bi, src_bi;
613 struct buffer_head *cf;
614 int d_key_position;
615
616 internal_define_dest_src_infos(INTERNAL_SHIFT_FROM_S_TO_R, tb, h,
617 &dest_bi, &src_bi, &d_key_position, &cf);
618
619
620 if (pointer_amount > 0)
621 internal_insert_key(&dest_bi, 0, cf, d_key_position);
622
623
624 internal_move_pointers_items(&dest_bi, &src_bi, LAST_TO_FIRST,
625 pointer_amount, 1);
626 }
627
628
629
630
631
632 static void balance_internal_when_delete(struct tree_balance *tb,
633 int h, int child_pos)
634 {
635 int insert_num;
636 int n;
637 struct buffer_head *tbSh = PATH_H_PBUFFER(tb->tb_path, h);
638 struct buffer_info bi;
639
640 insert_num = tb->insert_size[h] / ((int)(DC_SIZE + KEY_SIZE));
641
642
643 bi.tb = tb;
644 bi.bi_bh = tbSh;
645 bi.bi_parent = PATH_H_PPARENT(tb->tb_path, h);
646 bi.bi_position = PATH_H_POSITION(tb->tb_path, h + 1);
647
648 internal_delete_childs(&bi, child_pos, -insert_num);
649
650 RFALSE(tb->blknum[h] > 1,
651 "tb->blknum[%d]=%d when insert_size < 0", h, tb->blknum[h]);
652
653 n = B_NR_ITEMS(tbSh);
654
655 if (tb->lnum[h] == 0 && tb->rnum[h] == 0) {
656 if (tb->blknum[h] == 0) {
657
658 struct buffer_head *new_root;
659
660 RFALSE(n
661 || B_FREE_SPACE(tbSh) !=
662 MAX_CHILD_SIZE(tbSh) - DC_SIZE,
663 "buffer must have only 0 keys (%d)", n);
664 RFALSE(bi.bi_parent, "root has parent (%p)",
665 bi.bi_parent);
666
667
668 if (!tb->L[h - 1] || !B_NR_ITEMS(tb->L[h - 1]))
669 new_root = tb->R[h - 1];
670 else
671 new_root = tb->L[h - 1];
672
673
674
675 PUT_SB_ROOT_BLOCK(tb->tb_sb, new_root->b_blocknr);
676
677 PUT_SB_TREE_HEIGHT(tb->tb_sb,
678 SB_TREE_HEIGHT(tb->tb_sb) - 1);
679
680 do_balance_mark_sb_dirty(tb,
681 REISERFS_SB(tb->tb_sb)->s_sbh,
682 1);
683
684
685 if (h > 1)
686 check_internal(new_root);
687
688
689
690 reiserfs_invalidate_buffer(tb, tbSh);
691 return;
692 }
693 return;
694 }
695
696
697 if (tb->L[h] && tb->lnum[h] == -B_NR_ITEMS(tb->L[h]) - 1) {
698
699 RFALSE(tb->rnum[h] != 0,
700 "invalid tb->rnum[%d]==%d when joining S[h] with L[h]",
701 h, tb->rnum[h]);
702
703 internal_shift_left(INTERNAL_SHIFT_FROM_S_TO_L, tb, h, n + 1);
704 reiserfs_invalidate_buffer(tb, tbSh);
705
706 return;
707 }
708
709
710 if (tb->R[h] && tb->rnum[h] == -B_NR_ITEMS(tb->R[h]) - 1) {
711 RFALSE(tb->lnum[h] != 0,
712 "invalid tb->lnum[%d]==%d when joining S[h] with R[h]",
713 h, tb->lnum[h]);
714
715 internal_shift_right(INTERNAL_SHIFT_FROM_S_TO_R, tb, h, n + 1);
716
717 reiserfs_invalidate_buffer(tb, tbSh);
718 return;
719 }
720
721
722 if (tb->lnum[h] < 0) {
723 RFALSE(tb->rnum[h] != 0,
724 "wrong tb->rnum[%d]==%d when borrow from L[h]", h,
725 tb->rnum[h]);
726 internal_shift_right(INTERNAL_SHIFT_FROM_L_TO_S, tb, h,
727 -tb->lnum[h]);
728 return;
729 }
730
731
732 if (tb->rnum[h] < 0) {
733 RFALSE(tb->lnum[h] != 0,
734 "invalid tb->lnum[%d]==%d when borrow from R[h]",
735 h, tb->lnum[h]);
736 internal_shift_left(INTERNAL_SHIFT_FROM_R_TO_S, tb, h, -tb->rnum[h]);
737 return;
738 }
739
740
741 if (tb->lnum[h] > 0) {
742 RFALSE(tb->rnum[h] == 0 || tb->lnum[h] + tb->rnum[h] != n + 1,
743 "invalid tb->lnum[%d]==%d or tb->rnum[%d]==%d when S[h](item number == %d) is split between them",
744 h, tb->lnum[h], h, tb->rnum[h], n);
745
746 internal_shift_left(INTERNAL_SHIFT_FROM_S_TO_L, tb, h, tb->lnum[h]);
747 internal_shift_right(INTERNAL_SHIFT_FROM_S_TO_R, tb, h,
748 tb->rnum[h]);
749
750 reiserfs_invalidate_buffer(tb, tbSh);
751
752 return;
753 }
754 reiserfs_panic(tb->tb_sb, "ibalance-2",
755 "unexpected tb->lnum[%d]==%d or tb->rnum[%d]==%d",
756 h, tb->lnum[h], h, tb->rnum[h]);
757 }
758
759
760 static void replace_lkey(struct tree_balance *tb, int h, struct item_head *key)
761 {
762 RFALSE(tb->L[h] == NULL || tb->CFL[h] == NULL,
763 "L[h](%p) and CFL[h](%p) must exist in replace_lkey",
764 tb->L[h], tb->CFL[h]);
765
766 if (B_NR_ITEMS(PATH_H_PBUFFER(tb->tb_path, h)) == 0)
767 return;
768
769 memcpy(internal_key(tb->CFL[h], tb->lkey[h]), key, KEY_SIZE);
770
771 do_balance_mark_internal_dirty(tb, tb->CFL[h], 0);
772 }
773
774
775 static void replace_rkey(struct tree_balance *tb, int h, struct item_head *key)
776 {
777 RFALSE(tb->R[h] == NULL || tb->CFR[h] == NULL,
778 "R[h](%p) and CFR[h](%p) must exist in replace_rkey",
779 tb->R[h], tb->CFR[h]);
780 RFALSE(B_NR_ITEMS(tb->R[h]) == 0,
781 "R[h] can not be empty if it exists (item number=%d)",
782 B_NR_ITEMS(tb->R[h]));
783
784 memcpy(internal_key(tb->CFR[h], tb->rkey[h]), key, KEY_SIZE);
785
786 do_balance_mark_internal_dirty(tb, tb->CFR[h], 0);
787 }
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803 int balance_internal(struct tree_balance *tb,
804 int h,
805 int child_pos,
806
807 struct item_head *insert_key,
808
809 struct buffer_head **insert_ptr)
810 {
811 struct buffer_head *tbSh = PATH_H_PBUFFER(tb->tb_path, h);
812 struct buffer_info bi;
813
814
815
816
817
818 int order;
819 int insert_num, n, k;
820 struct buffer_head *S_new;
821 struct item_head new_insert_key;
822 struct buffer_head *new_insert_ptr = NULL;
823 struct item_head *new_insert_key_addr = insert_key;
824
825 RFALSE(h < 1, "h (%d) can not be < 1 on internal level", h);
826
827 PROC_INFO_INC(tb->tb_sb, balance_at[h]);
828
829 order =
830 (tbSh) ? PATH_H_POSITION(tb->tb_path,
831 h + 1) : 0;
832
833
834
835
836
837 insert_num = tb->insert_size[h] / ((int)(KEY_SIZE + DC_SIZE));
838
839
840 RFALSE(insert_num < -2 || insert_num > 2,
841 "incorrect number of items inserted to the internal node (%d)",
842 insert_num);
843 RFALSE(h > 1 && (insert_num > 1 || insert_num < -1),
844 "incorrect number of items (%d) inserted to the internal node on a level (h=%d) higher than last internal level",
845 insert_num, h);
846
847
848 if (insert_num < 0) {
849 balance_internal_when_delete(tb, h, child_pos);
850 return order;
851 }
852
853 k = 0;
854 if (tb->lnum[h] > 0) {
855
856
857
858
859
860 n = B_NR_ITEMS(tb->L[h]);
861 if (tb->lnum[h] <= child_pos) {
862
863 internal_shift_left(INTERNAL_SHIFT_FROM_S_TO_L, tb, h,
864 tb->lnum[h]);
865 child_pos -= tb->lnum[h];
866 } else if (tb->lnum[h] > child_pos + insert_num) {
867
868 internal_shift_left(INTERNAL_SHIFT_FROM_S_TO_L, tb, h,
869 tb->lnum[h] - insert_num);
870
871 bi.tb = tb;
872 bi.bi_bh = tb->L[h];
873 bi.bi_parent = tb->FL[h];
874 bi.bi_position = get_left_neighbor_position(tb, h);
875 internal_insert_childs(&bi,
876
877 n + child_pos + 1,
878 insert_num, insert_key,
879 insert_ptr);
880
881 insert_num = 0;
882 } else {
883 struct disk_child *dc;
884
885
886
887
888
889 internal_shift1_left(tb, h, child_pos + 1);
890
891 k = tb->lnum[h] - child_pos - 1;
892 bi.tb = tb;
893 bi.bi_bh = tb->L[h];
894 bi.bi_parent = tb->FL[h];
895 bi.bi_position = get_left_neighbor_position(tb, h);
896 internal_insert_childs(&bi,
897
898 n + child_pos + 1, k,
899 insert_key, insert_ptr);
900
901 replace_lkey(tb, h, insert_key + k);
902
903
904
905
906
907 dc = B_N_CHILD(tbSh, 0);
908 put_dc_size(dc,
909 MAX_CHILD_SIZE(insert_ptr[k]) -
910 B_FREE_SPACE(insert_ptr[k]));
911 put_dc_block_number(dc, insert_ptr[k]->b_blocknr);
912
913 do_balance_mark_internal_dirty(tb, tbSh, 0);
914
915 k++;
916 insert_key += k;
917 insert_ptr += k;
918 insert_num -= k;
919 child_pos = 0;
920 }
921 }
922
923 if (tb->rnum[h] > 0) {
924
925
926
927
928
929 n = B_NR_ITEMS(tbSh);
930 if (n - tb->rnum[h] >= child_pos)
931
932 internal_shift_right(INTERNAL_SHIFT_FROM_S_TO_R, tb, h,
933 tb->rnum[h]);
934 else if (n + insert_num - tb->rnum[h] < child_pos) {
935
936 internal_shift_right(INTERNAL_SHIFT_FROM_S_TO_R, tb, h,
937 tb->rnum[h] - insert_num);
938
939
940 bi.tb = tb;
941 bi.bi_bh = tb->R[h];
942 bi.bi_parent = tb->FR[h];
943 bi.bi_position = get_right_neighbor_position(tb, h);
944 internal_insert_childs(&bi,
945
946 child_pos - n - insert_num +
947 tb->rnum[h] - 1,
948 insert_num, insert_key,
949 insert_ptr);
950 insert_num = 0;
951 } else {
952 struct disk_child *dc;
953
954
955 internal_shift1_right(tb, h, n - child_pos + 1);
956
957 k = tb->rnum[h] - n + child_pos - 1;
958 bi.tb = tb;
959 bi.bi_bh = tb->R[h];
960 bi.bi_parent = tb->FR[h];
961 bi.bi_position = get_right_neighbor_position(tb, h);
962 internal_insert_childs(&bi,
963
964 0, k, insert_key + 1,
965 insert_ptr + 1);
966
967 replace_rkey(tb, h, insert_key + insert_num - k - 1);
968
969
970
971
972
973 dc = B_N_CHILD(tb->R[h], 0);
974 put_dc_size(dc,
975 MAX_CHILD_SIZE(insert_ptr
976 [insert_num - k - 1]) -
977 B_FREE_SPACE(insert_ptr
978 [insert_num - k - 1]));
979 put_dc_block_number(dc,
980 insert_ptr[insert_num - k -
981 1]->b_blocknr);
982
983 do_balance_mark_internal_dirty(tb, tb->R[h], 0);
984
985 insert_num -= (k + 1);
986 }
987 }
988
989
990 RFALSE(tb->blknum[h] > 2, "blknum can not be > 2 for internal level");
991 RFALSE(tb->blknum[h] < 0, "blknum can not be < 0");
992
993 if (!tb->blknum[h]) {
994 RFALSE(!tbSh, "S[h] is equal NULL");
995
996
997 reiserfs_invalidate_buffer(tb, tbSh);
998 return order;
999 }
1000
1001 if (!tbSh) {
1002
1003 struct disk_child *dc;
1004 struct buffer_head *tbSh_1 = PATH_H_PBUFFER(tb->tb_path, h - 1);
1005 struct block_head *blkh;
1006
1007 if (tb->blknum[h] != 1)
1008 reiserfs_panic(NULL, "ibalance-3", "One new node "
1009 "required for creating the new root");
1010
1011 tbSh = get_FEB(tb);
1012 blkh = B_BLK_HEAD(tbSh);
1013 set_blkh_level(blkh, h + 1);
1014
1015
1016
1017 dc = B_N_CHILD(tbSh, 0);
1018 put_dc_block_number(dc, tbSh_1->b_blocknr);
1019 put_dc_size(dc,
1020 (MAX_CHILD_SIZE(tbSh_1) - B_FREE_SPACE(tbSh_1)));
1021
1022 tb->insert_size[h] -= DC_SIZE;
1023 set_blkh_free_space(blkh, blkh_free_space(blkh) - DC_SIZE);
1024
1025 do_balance_mark_internal_dirty(tb, tbSh, 0);
1026
1027
1028 check_internal(tbSh);
1029
1030
1031
1032 PATH_OFFSET_PBUFFER(tb->tb_path, ILLEGAL_PATH_ELEMENT_OFFSET) =
1033 tbSh;
1034
1035
1036 PUT_SB_ROOT_BLOCK(tb->tb_sb, tbSh->b_blocknr);
1037 PUT_SB_TREE_HEIGHT(tb->tb_sb, SB_TREE_HEIGHT(tb->tb_sb) + 1);
1038 do_balance_mark_sb_dirty(tb, REISERFS_SB(tb->tb_sb)->s_sbh, 1);
1039 }
1040
1041 if (tb->blknum[h] == 2) {
1042 int snum;
1043 struct buffer_info dest_bi, src_bi;
1044
1045
1046 S_new = get_FEB(tb);
1047
1048 set_blkh_level(B_BLK_HEAD(S_new), h + 1);
1049
1050 dest_bi.tb = tb;
1051 dest_bi.bi_bh = S_new;
1052 dest_bi.bi_parent = NULL;
1053 dest_bi.bi_position = 0;
1054 src_bi.tb = tb;
1055 src_bi.bi_bh = tbSh;
1056 src_bi.bi_parent = PATH_H_PPARENT(tb->tb_path, h);
1057 src_bi.bi_position = PATH_H_POSITION(tb->tb_path, h + 1);
1058
1059 n = B_NR_ITEMS(tbSh);
1060 snum = (insert_num + n + 1) / 2;
1061 if (n - snum >= child_pos) {
1062
1063
1064
1065 memcpy(&new_insert_key, internal_key(tbSh, n - snum),
1066 KEY_SIZE);
1067
1068 internal_move_pointers_items(&dest_bi, &src_bi,
1069 LAST_TO_FIRST, snum, 0);
1070 } else if (n + insert_num - snum < child_pos) {
1071
1072
1073
1074
1075
1076
1077 memcpy(&new_insert_key,
1078 internal_key(tbSh, n + insert_num - snum),
1079 KEY_SIZE);
1080
1081 internal_move_pointers_items(&dest_bi, &src_bi,
1082 LAST_TO_FIRST,
1083 snum - insert_num, 0);
1084
1085
1086
1087
1088
1089 internal_insert_childs(&dest_bi,
1090
1091 child_pos - n - insert_num +
1092 snum - 1,
1093 insert_num, insert_key,
1094 insert_ptr);
1095
1096 insert_num = 0;
1097 } else {
1098 struct disk_child *dc;
1099
1100
1101
1102 internal_move_pointers_items(&dest_bi, &src_bi,
1103 LAST_TO_FIRST,
1104 n - child_pos + 1, 1);
1105
1106 k = snum - n + child_pos - 1;
1107
1108 internal_insert_childs(&dest_bi, 0, k,
1109 insert_key + 1, insert_ptr + 1);
1110
1111
1112 memcpy(&new_insert_key, insert_key + insert_num - k - 1,
1113 KEY_SIZE);
1114
1115
1116
1117
1118
1119 dc = B_N_CHILD(S_new, 0);
1120 put_dc_size(dc,
1121 (MAX_CHILD_SIZE
1122 (insert_ptr[insert_num - k - 1]) -
1123 B_FREE_SPACE(insert_ptr
1124 [insert_num - k - 1])));
1125 put_dc_block_number(dc,
1126 insert_ptr[insert_num - k -
1127 1]->b_blocknr);
1128
1129 do_balance_mark_internal_dirty(tb, S_new, 0);
1130
1131 insert_num -= (k + 1);
1132 }
1133
1134 new_insert_ptr = S_new;
1135
1136 RFALSE(!buffer_journaled(S_new) || buffer_journal_dirty(S_new)
1137 || buffer_dirty(S_new), "cm-00001: bad S_new (%b)",
1138 S_new);
1139
1140
1141 }
1142
1143 n = B_NR_ITEMS(tbSh);
1144
1145 if (0 <= child_pos && child_pos <= n && insert_num > 0) {
1146 bi.tb = tb;
1147 bi.bi_bh = tbSh;
1148 bi.bi_parent = PATH_H_PPARENT(tb->tb_path, h);
1149 bi.bi_position = PATH_H_POSITION(tb->tb_path, h + 1);
1150 internal_insert_childs(&bi,
1151
1152 child_pos, insert_num, insert_key,
1153 insert_ptr);
1154 }
1155
1156 insert_ptr[0] = new_insert_ptr;
1157 if (new_insert_ptr)
1158 memcpy(new_insert_key_addr, &new_insert_key, KEY_SIZE);
1159
1160 return order;
1161 }