1 /*
2 * Copyright 2000 by Hans Reiser, licensing governed by reiserfs/README
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 /* this is one and only function that is used outside (do_balance.c) */
12 int balance_internal(struct tree_balance *,
13 int, int, struct item_head *, struct buffer_head **);
14
15 /*
16 * modes of internal_shift_left, internal_shift_right and
17 * internal_insert_childs
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 /* define dest, src, dest parent, dest position */
37 switch (shift_mode) {
38
39 /* used in internal_shift_left */
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 /* dest position is analog of dest->b_item_order */
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 /* used in internal_shift_left */
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 * Insert count node pointers into buffer cur before position to + 1.
123 * Insert count items into buffer cur before position to.
124 * Items and node pointers are specified by inserted and bh respectively.
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 /* prepare space for count disk_child */
151 dc = B_N_CHILD(cur, to + 1);
152
153 memmove(dc + count, dc, (nr + 1 - (to + 1)) * DC_SIZE);
154
155 /* copy to_be_insert disk children */
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 /* prepare space for count items */
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 /* copy item headers (keys) */
170 memcpy(ih, inserted, KEY_SIZE);
171 if (count > 1)
172 memcpy(ih + 1, inserted + 1, KEY_SIZE);
173
174 /* sizes, item number */
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 * Delete del_num items and node pointers from buffer cur starting from
203 * the first_i'th item and first_p'th pointers respectively.
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 /* deleting */
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 /* sizes, item number */
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 /* delete n node pointers and items starting from given position */
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 * delete n pointers starting from `from' position in CUR;
285 * delete n keys starting from 'i_from' position in CUR;
286 */
287 internal_delete_pointers_items(cur_bi, from, i_from, n);
288 }
289
290 /*
291 * copy cpy_num node pointers and cpy_num - 1 items from buffer src to buffer
292 * dest
293 * last_first == FIRST_TO_LAST means that we copy first items
294 * from src to tail of dest
295 * last_first == LAST_TO_FIRST means that we copy last items
296 * from src to head of dest
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 * ATTENTION! Number of node pointers in DEST is equal to number
304 * of items in DEST as delimiting key have already inserted to
305 * buffer dest.
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 /* coping */
331 blkh = B_BLK_HEAD(dest);
332 nr_dest = blkh_nr_item(blkh);
333
334 /*dest_order = (last_first == LAST_TO_FIRST) ? 0 : nr_dest; */
335 /*src_order = (last_first == LAST_TO_FIRST) ? (nr_src - cpy_num + 1) : 0; */
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 /* prepare space for cpy_num pointers */
343 dc = B_N_CHILD(dest, dest_order);
344
345 memmove(dc + cpy_num, dc, (nr_dest - dest_order) * DC_SIZE);
346
347 /* insert pointers */
348 memcpy(dc, B_N_CHILD(src, src_order), DC_SIZE * cpy_num);
349
350 /* prepare space for cpy_num - 1 item headers */
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 /* insert headers */
357 memcpy(key, internal_key(src, src_order), KEY_SIZE * (cpy_num - 1));
358
359 /* sizes, item number */
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 * Copy cpy_num node pointers and cpy_num - 1 items from buffer src to
389 * buffer dest.
390 * Delete cpy_num - del_par items and node pointers from buffer src.
391 * last_first == FIRST_TO_LAST means, that we copy/delete first items from src.
392 * last_first == LAST_TO_FIRST means, that we copy/delete last items from src.
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) { /* shift_left occurs */
406 first_pointer = 0;
407 first_item = 0;
408 /*
409 * delete cpy_num - del_par pointers and keys starting for
410 * pointers with first_pointer, for key - with first_item
411 */
412 internal_delete_pointers_items(src_bi, first_pointer,
413 first_item, cpy_num - del_par);
414 } else { /* shift_right occurs */
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 /* Insert n_src'th key of buffer src before n_dest'th key of buffer dest. */
429 static void internal_insert_key(struct buffer_info *dest_bi,
430 /* insert key before key with n_dest number */
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 /* prepare space for inserting key */
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 /* insert key */
461 memcpy(key, internal_key(src, src_position), KEY_SIZE);
462
463 /* Change dirt, free space, item number fields. */
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 * Insert d_key'th (delimiting) key from buffer cfl to tail of dest.
482 * Copy pointer_amount node pointers and pointer_amount - 1 items from
483 * buffer src to buffer dest.
484 * Replace d_key'th key in buffer cfl.
485 * Delete pointer_amount items and node pointers from buffer src.
486 */
487 /* this can be invoked both to shift from S to L and from R to S */
488 static void internal_shift_left(
489 /*
490 * INTERNAL_FROM_S_TO_L | INTERNAL_FROM_R_TO_S
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 /*printk("pointer_amount = %d\n",pointer_amount); */
504
505 if (pointer_amount) {
506 /*
507 * insert delimiting key from common father of dest and
508 * src to node dest into position B_NR_ITEM(dest)
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 /*src->b_item_order */ == 0)
515 replace_key(tb, cf, d_key_position,
516 src_bi.
517 bi_parent /*src->b_parent */ , 0);
518 } else
519 replace_key(tb, cf, d_key_position, src_bi.bi_bh,
520 pointer_amount - 1);
521 }
522 /* last parameter is del_parameter */
523 internal_move_pointers_items(&dest_bi, &src_bi, FIRST_TO_LAST,
524 pointer_amount, 0);
525
526 }
527
528 /*
529 * Insert delimiting key to L[h].
530 * Copy n node pointers and n - 1 items from buffer S[h] to L[h].
531 * Delete n - 1 items and node pointers from buffer S[h].
532 */
533 /* it always shifts from S[h] to L[h] */
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 /* insert lkey[h]-th key from CFL[h] to left neighbor L[h] */
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 /* last parameter is del_parameter */
550 internal_move_pointers_items(&dest_bi, &src_bi, FIRST_TO_LAST,
551 pointer_amount, 1);
552 }
553
554 /*
555 * Insert d_key'th (delimiting) key from buffer cfr to head of dest.
556 * Copy n node pointers and n - 1 items from buffer src to buffer dest.
557 * Replace d_key'th key in buffer cfr.
558 * Delete n items and node pointers from buffer src.
559 */
560 static void internal_shift_right(
561 /*
562 * INTERNAL_FROM_S_TO_R | INTERNAL_FROM_L_TO_S
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 * insert delimiting key from common father of dest
581 * and src to dest node into position 0
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) /*tb->S[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 /* when S[h] disappers replace left delemiting key as well */
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 /* last parameter is del_parameter */
599 internal_move_pointers_items(&dest_bi, &src_bi, LAST_TO_FIRST,
600 pointer_amount, 0);
601 }
602
603 /*
604 * Insert delimiting key to R[h].
605 * Copy n node pointers and n - 1 items from buffer S[h] to R[h].
606 * Delete n - 1 items and node pointers from buffer S[h].
607 */
608 /* it always shift from S[h] to R[h] */
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 /* insert rkey from CFR[h] to right neighbor R[h] */
620 if (pointer_amount > 0)
621 internal_insert_key(&dest_bi, 0, cf, d_key_position);
622
623 /* last parameter is del_parameter */
624 internal_move_pointers_items(&dest_bi, &src_bi, LAST_TO_FIRST,
625 pointer_amount, 1);
626 }
627
628 /*
629 * Delete insert_num node pointers together with their left items
630 * and balance current node.
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 /* delete child-node-pointer(s) together with their left item(s) */
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 /* node S[h] (root of the tree) is empty now */
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 /* choose a new root */
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 * switch super block's tree root block
674 * number to the new value */
675 PUT_SB_ROOT_BLOCK(tb->tb_sb, new_root->b_blocknr);
676 /*REISERFS_SB(tb->tb_sb)->s_rs->s_tree_height --; */
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 /* use check_internal if new root is an internal node */
685 if (h > 1)
686 check_internal(new_root);
687 /*&&&&&&&&&&&&&&&&&&&&&& */
688
689 /* do what is needed for buffer thrown from tree */
690 reiserfs_invalidate_buffer(tb, tbSh);
691 return;
692 }
693 return;
694 }
695
696 /* join S[h] with L[h] */
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 /* join S[h] with R[h] */
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 /* borrow from left neighbor L[h] */
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 /* borrow from right neighbor R[h] */
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]); /*tb->S[h], tb->CFR[h], tb->rkey[h], tb->R[h], -tb->rnum[h]); */
737 return;
738 }
739
740 /* split S[h] into two parts and put them into neighbors */
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]); /*tb->L[h], tb->CFL[h], tb->lkey[h], tb->S[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 /* Replace delimiting key of buffers L[h] and S[h] by the given key.*/
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 /* Replace delimiting key of buffers S[h] and R[h] by the given key.*/
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 * if inserting/pasting {
792 * child_pos is the position of the node-pointer in S[h] that
793 * pointed to S[h-1] before balancing of the h-1 level;
794 * this means that new pointers and items must be inserted AFTER
795 * child_pos
796 * } else {
797 * it is the position of the leftmost pointer that must be deleted
798 * (together with its corresponding key to the left of the pointer)
799 * as a result of the previous level's balancing.
800 * }
801 */
802
803 int balance_internal(struct tree_balance *tb,
804 int h, /* level of the tree */
805 int child_pos,
806 /* key for insertion on higher level */
807 struct item_head *insert_key,
808 /* node for insertion on higher level */
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 * we return this: it is 0 if there is no S[h],
816 * else it is tb->S[h]->b_item_order
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) /*tb->S[h]->b_item_order */ : 0;
832
833 /*
834 * Using insert_size[h] calculate the number insert_num of items
835 * that must be inserted to or deleted from S[h].
836 */
837 insert_num = tb->insert_size[h] / ((int)(KEY_SIZE + DC_SIZE));
838
839 /* Check whether insert_num is proper * */
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 /* Make balance in case insert_num < 0 */
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 * shift lnum[h] items from S[h] to the left neighbor L[h].
857 * check how many of new items fall into L[h] or CFL[h] after
858 * shifting
859 */
860 n = B_NR_ITEMS(tb->L[h]); /* number of items in L[h] */
861 if (tb->lnum[h] <= child_pos) {
862 /* new items don't fall into L[h] or CFL[h] */
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 /* all new items fall into L[h] */
868 internal_shift_left(INTERNAL_SHIFT_FROM_S_TO_L, tb, h,
869 tb->lnum[h] - insert_num);
870 /* insert insert_num keys and node-pointers into L[h] */
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 /*tb->L[h], tb->S[h-1]->b_next */
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 * some items fall into L[h] or CFL[h],
887 * but some don't fall
888 */
889 internal_shift1_left(tb, h, child_pos + 1);
890 /* calculate number of new items that fall into L[h] */
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 /*tb->L[h], tb->S[h-1]->b_next, */
898 n + child_pos + 1, k,
899 insert_key, insert_ptr);
900
901 replace_lkey(tb, h, insert_key + k);
902
903 /*
904 * replace the first node-ptr in S[h] by
905 * node-ptr to insert_ptr[k]
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 /* tb->lnum[h] > 0 */
923 if (tb->rnum[h] > 0) {
924 /*shift rnum[h] items from S[h] to the right neighbor R[h] */
925 /*
926 * check how many of new items fall into R or CFR
927 * after shifting
928 */
929 n = B_NR_ITEMS(tbSh); /* number of items in S[h] */
930 if (n - tb->rnum[h] >= child_pos)
931 /* new items fall into S[h] */
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 /* all new items fall into R[h] */
936 internal_shift_right(INTERNAL_SHIFT_FROM_S_TO_R, tb, h,
937 tb->rnum[h] - insert_num);
938
939 /* insert insert_num keys and node-pointers into R[h] */
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 /*tb->R[h],tb->S[h-1]->b_next */
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 /* one of the items falls into CFR[h] */
955 internal_shift1_right(tb, h, n - child_pos + 1);
956 /* calculate number of new items that fall into R[h] */
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 /*tb->R[h], tb->R[h]->b_child, */
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 * replace the first node-ptr in R[h] by
971 * node-ptr insert_ptr[insert_num-k-1]
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 /** Fill new node that appears instead of S[h] **/
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]) { /* node S[h] is empty now */
994 RFALSE(!tbSh, "S[h] is equal NULL");
995
996 /* do what is needed for buffer thrown from tree */
997 reiserfs_invalidate_buffer(tb, tbSh);
998 return order;
999 }
1000
1001 if (!tbSh) {
1002 /* create new root */
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 /* S[h] = empty buffer from the list FEB. */
1011 tbSh = get_FEB(tb);
1012 blkh = B_BLK_HEAD(tbSh);
1013 set_blkh_level(blkh, h + 1);
1014
1015 /* Put the unique node-pointer to S[h] that points to S[h-1]. */
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 /* put new root into path structure */
1032 PATH_OFFSET_PBUFFER(tb->tb_path, ILLEGAL_PATH_ELEMENT_OFFSET) =
1033 tbSh;
1034
1035 /* Change root in structure super block. */
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 /* S_new = free buffer from list FEB */
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); /* number of items in S[h] */
1060 snum = (insert_num + n + 1) / 2;
1061 if (n - snum >= child_pos) {
1062 /* new items don't fall into S_new */
1063 /* store the delimiting key for the next level */
1064 /* new_insert_key = (n - snum)'th key in S[h] */
1065 memcpy(&new_insert_key, internal_key(tbSh, n - snum),
1066 KEY_SIZE);
1067 /* last parameter is del_par */
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 /* all new items fall into S_new */
1072 /* store the delimiting key for the next level */
1073 /*
1074 * new_insert_key = (n + insert_item - snum)'th
1075 * key in S[h]
1076 */
1077 memcpy(&new_insert_key,
1078 internal_key(tbSh, n + insert_num - snum),
1079 KEY_SIZE);
1080 /* last parameter is del_par */
1081 internal_move_pointers_items(&dest_bi, &src_bi,
1082 LAST_TO_FIRST,
1083 snum - insert_num, 0);
1084
1085 /*
1086 * insert insert_num keys and node-pointers
1087 * into S_new
1088 */
1089 internal_insert_childs(&dest_bi,
1090 /*S_new,tb->S[h-1]->b_next, */
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 /* some items fall into S_new, but some don't fall */
1101 /* last parameter is del_par */
1102 internal_move_pointers_items(&dest_bi, &src_bi,
1103 LAST_TO_FIRST,
1104 n - child_pos + 1, 1);
1105 /* calculate number of new items that fall into S_new */
1106 k = snum - n + child_pos - 1;
1107
1108 internal_insert_childs(&dest_bi, /*S_new, */ 0, k,
1109 insert_key + 1, insert_ptr + 1);
1110
1111 /* new_insert_key = insert_key[insert_num - k - 1] */
1112 memcpy(&new_insert_key, insert_key + insert_num - k - 1,
1113 KEY_SIZE);
1114 /*
1115 * replace first node-ptr in S_new by node-ptr
1116 * to insert_ptr[insert_num-k-1]
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 /* new_insert_ptr = node_pointer to S_new */
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 /* S_new is released in unfix_nodes */
1141 }
1142
1143 n = B_NR_ITEMS(tbSh); /*number of items in S[h] */
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, /*tbSh, */
1151 /* ( tb->S[h-1]->b_parent == tb->S[h] ) ? tb->S[h-1]->b_next : tb->S[h]->b_child->b_next, */
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 }
1162
Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.