1162 lines · c
1/*2 * Copyright 2000 by Hans Reiser, licensing governed by reiserfs/README3 */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) */12int 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 and17 * internal_insert_childs18 */19#define INTERNAL_SHIFT_FROM_S_TO_L 020#define INTERNAL_SHIFT_FROM_R_TO_S 121#define INTERNAL_SHIFT_FROM_L_TO_S 222#define INTERNAL_SHIFT_FROM_S_TO_R 323#define INTERNAL_INSERT_TO_S 424#define INTERNAL_INSERT_TO_L 525#define INTERNAL_INSERT_TO_R 626 27static 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 */126static 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 from203 * the first_i'th item and first_p'th pointers respectively.204 */205static 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) + 1219 || 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 */277static 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 buffer292 * dest293 * last_first == FIRST_TO_LAST means that we copy first items294 * from src to tail of dest295 * last_first == LAST_TO_FIRST means that we copy last items296 * from src to head of dest297 */298static 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 number304 * of items in DEST as delimiting key have already inserted to305 * 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 to389 * 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 */394static 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 for410 * pointers with first_pointer, for key - with first_item411 */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. */429static 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 from483 * 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 */488static void internal_shift_left(489 /*490 * INTERNAL_FROM_S_TO_L | INTERNAL_FROM_R_TO_S491 */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 and508 * 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 } else519 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] */534static 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 */560static void internal_shift_right(561 /*562 * INTERNAL_FROM_S_TO_R | INTERNAL_FROM_L_TO_S563 */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 dest581 * and src to dest node into position 0582 */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 } else594 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] */609static 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 items630 * and balance current node.631 */632static 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(n661 || 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 else671 new_root = tb->L[h - 1];672 /*673 * switch super block's tree root block674 * 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.*/760static 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.*/775static 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] that793 * pointed to S[h-1] before balancing of the h-1 level;794 * this means that new pointers and items must be inserted AFTER795 * child_pos796 * } else {797 * it is the position of the leftmost pointer that must be deleted798 * (together with its corresponding key to the left of the pointer)799 * as a result of the previous level's balancing.800 * }801 */802 803int 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_order817 */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 items835 * 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] after858 * shifting859 */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 fall888 */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] by905 * 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 CFR927 * after shifting928 */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] by971 * 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_ptr976 [insert_num - k - 1]) -977 B_FREE_SPACE(insert_ptr978 [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)'th1075 * 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-pointers1087 * into S_new1088 */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-ptr1116 * 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_SIZE1122 (insert_ptr[insert_num - k - 1]) -1123 B_FREE_SPACE(insert_ptr1124 [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