2823 lines · c
1/*2 * Copyright 2000 by Hans Reiser, licensing governed by reiserfs/README3 */4 5#include <linux/time.h>6#include <linux/slab.h>7#include <linux/string.h>8#include "reiserfs.h"9#include <linux/buffer_head.h>10 11/*12 * To make any changes in the tree we find a node that contains item13 * to be changed/deleted or position in the node we insert a new item14 * to. We call this node S. To do balancing we need to decide what we15 * will shift to left/right neighbor, or to a new node, where new item16 * will be etc. To make this analysis simpler we build virtual17 * node. Virtual node is an array of items, that will replace items of18 * node S. (For instance if we are going to delete an item, virtual19 * node does not contain it). Virtual node keeps information about20 * item sizes and types, mergeability of first and last items, sizes21 * of all entries in directory item. We use this array of items when22 * calculating what we can shift to neighbors and how many nodes we23 * have to have if we do not any shiftings, if we shift to left/right24 * neighbor or to both.25 */26 27/*28 * Takes item number in virtual node, returns number of item29 * that it has in source buffer30 */31static inline int old_item_num(int new_num, int affected_item_num, int mode)32{33 if (mode == M_PASTE || mode == M_CUT || new_num < affected_item_num)34 return new_num;35 36 if (mode == M_INSERT) {37 38 RFALSE(new_num == 0,39 "vs-8005: for INSERT mode and item number of inserted item");40 41 return new_num - 1;42 }43 44 RFALSE(mode != M_DELETE,45 "vs-8010: old_item_num: mode must be M_DELETE (mode = \'%c\'",46 mode);47 /* delete mode */48 return new_num + 1;49}50 51static void create_virtual_node(struct tree_balance *tb, int h)52{53 struct item_head *ih;54 struct virtual_node *vn = tb->tb_vn;55 int new_num;56 struct buffer_head *Sh; /* this comes from tb->S[h] */57 58 Sh = PATH_H_PBUFFER(tb->tb_path, h);59 60 /* size of changed node */61 vn->vn_size =62 MAX_CHILD_SIZE(Sh) - B_FREE_SPACE(Sh) + tb->insert_size[h];63 64 /* for internal nodes array if virtual items is not created */65 if (h) {66 vn->vn_nr_item = (vn->vn_size - DC_SIZE) / (DC_SIZE + KEY_SIZE);67 return;68 }69 70 /* number of items in virtual node */71 vn->vn_nr_item =72 B_NR_ITEMS(Sh) + ((vn->vn_mode == M_INSERT) ? 1 : 0) -73 ((vn->vn_mode == M_DELETE) ? 1 : 0);74 75 /* first virtual item */76 vn->vn_vi = (struct virtual_item *)(tb->tb_vn + 1);77 memset(vn->vn_vi, 0, vn->vn_nr_item * sizeof(struct virtual_item));78 vn->vn_free_ptr += vn->vn_nr_item * sizeof(struct virtual_item);79 80 /* first item in the node */81 ih = item_head(Sh, 0);82 83 /* define the mergeability for 0-th item (if it is not being deleted) */84 if (op_is_left_mergeable(&ih->ih_key, Sh->b_size)85 && (vn->vn_mode != M_DELETE || vn->vn_affected_item_num))86 vn->vn_vi[0].vi_type |= VI_TYPE_LEFT_MERGEABLE;87 88 /*89 * go through all items that remain in the virtual90 * node (except for the new (inserted) one)91 */92 for (new_num = 0; new_num < vn->vn_nr_item; new_num++) {93 int j;94 struct virtual_item *vi = vn->vn_vi + new_num;95 int is_affected =96 ((new_num != vn->vn_affected_item_num) ? 0 : 1);97 98 if (is_affected && vn->vn_mode == M_INSERT)99 continue;100 101 /* get item number in source node */102 j = old_item_num(new_num, vn->vn_affected_item_num,103 vn->vn_mode);104 105 vi->vi_item_len += ih_item_len(ih + j) + IH_SIZE;106 vi->vi_ih = ih + j;107 vi->vi_item = ih_item_body(Sh, ih + j);108 vi->vi_uarea = vn->vn_free_ptr;109 110 /*111 * FIXME: there is no check that item operation did not112 * consume too much memory113 */114 vn->vn_free_ptr +=115 op_create_vi(vn, vi, is_affected, tb->insert_size[0]);116 if (tb->vn_buf + tb->vn_buf_size < vn->vn_free_ptr)117 reiserfs_panic(tb->tb_sb, "vs-8030",118 "virtual node space consumed");119 120 if (!is_affected)121 /* this is not being changed */122 continue;123 124 if (vn->vn_mode == M_PASTE || vn->vn_mode == M_CUT) {125 vn->vn_vi[new_num].vi_item_len += tb->insert_size[0];126 /* pointer to data which is going to be pasted */127 vi->vi_new_data = vn->vn_data;128 }129 }130 131 /* virtual inserted item is not defined yet */132 if (vn->vn_mode == M_INSERT) {133 struct virtual_item *vi = vn->vn_vi + vn->vn_affected_item_num;134 135 RFALSE(vn->vn_ins_ih == NULL,136 "vs-8040: item header of inserted item is not specified");137 vi->vi_item_len = tb->insert_size[0];138 vi->vi_ih = vn->vn_ins_ih;139 vi->vi_item = vn->vn_data;140 vi->vi_uarea = vn->vn_free_ptr;141 142 op_create_vi(vn, vi, 0 /*not pasted or cut */ ,143 tb->insert_size[0]);144 }145 146 /*147 * set right merge flag we take right delimiting key and148 * check whether it is a mergeable item149 */150 if (tb->CFR[0]) {151 struct reiserfs_key *key;152 153 key = internal_key(tb->CFR[0], tb->rkey[0]);154 if (op_is_left_mergeable(key, Sh->b_size)155 && (vn->vn_mode != M_DELETE156 || vn->vn_affected_item_num != B_NR_ITEMS(Sh) - 1))157 vn->vn_vi[vn->vn_nr_item - 1].vi_type |=158 VI_TYPE_RIGHT_MERGEABLE;159 160#ifdef CONFIG_REISERFS_CHECK161 if (op_is_left_mergeable(key, Sh->b_size) &&162 !(vn->vn_mode != M_DELETE163 || vn->vn_affected_item_num != B_NR_ITEMS(Sh) - 1)) {164 /*165 * we delete last item and it could be merged166 * with right neighbor's first item167 */168 if (!169 (B_NR_ITEMS(Sh) == 1170 && is_direntry_le_ih(item_head(Sh, 0))171 && ih_entry_count(item_head(Sh, 0)) == 1)) {172 /*173 * node contains more than 1 item, or item174 * is not directory item, or this item175 * contains more than 1 entry176 */177 print_block(Sh, 0, -1, -1);178 reiserfs_panic(tb->tb_sb, "vs-8045",179 "rdkey %k, affected item==%d "180 "(mode==%c) Must be %c",181 key, vn->vn_affected_item_num,182 vn->vn_mode, M_DELETE);183 }184 }185#endif186 187 }188}189 190/*191 * Using virtual node check, how many items can be192 * shifted to left neighbor193 */194static void check_left(struct tree_balance *tb, int h, int cur_free)195{196 int i;197 struct virtual_node *vn = tb->tb_vn;198 struct virtual_item *vi;199 int d_size, ih_size;200 201 RFALSE(cur_free < 0, "vs-8050: cur_free (%d) < 0", cur_free);202 203 /* internal level */204 if (h > 0) {205 tb->lnum[h] = cur_free / (DC_SIZE + KEY_SIZE);206 return;207 }208 209 /* leaf level */210 211 if (!cur_free || !vn->vn_nr_item) {212 /* no free space or nothing to move */213 tb->lnum[h] = 0;214 tb->lbytes = -1;215 return;216 }217 218 RFALSE(!PATH_H_PPARENT(tb->tb_path, 0),219 "vs-8055: parent does not exist or invalid");220 221 vi = vn->vn_vi;222 if ((unsigned int)cur_free >=223 (vn->vn_size -224 ((vi->vi_type & VI_TYPE_LEFT_MERGEABLE) ? IH_SIZE : 0))) {225 /* all contents of S[0] fits into L[0] */226 227 RFALSE(vn->vn_mode == M_INSERT || vn->vn_mode == M_PASTE,228 "vs-8055: invalid mode or balance condition failed");229 230 tb->lnum[0] = vn->vn_nr_item;231 tb->lbytes = -1;232 return;233 }234 235 d_size = 0, ih_size = IH_SIZE;236 237 /* first item may be merge with last item in left neighbor */238 if (vi->vi_type & VI_TYPE_LEFT_MERGEABLE)239 d_size = -((int)IH_SIZE), ih_size = 0;240 241 tb->lnum[0] = 0;242 for (i = 0; i < vn->vn_nr_item;243 i++, ih_size = IH_SIZE, d_size = 0, vi++) {244 d_size += vi->vi_item_len;245 if (cur_free >= d_size) {246 /* the item can be shifted entirely */247 cur_free -= d_size;248 tb->lnum[0]++;249 continue;250 }251 252 /* the item cannot be shifted entirely, try to split it */253 /*254 * check whether L[0] can hold ih and at least one byte255 * of the item body256 */257 258 /* cannot shift even a part of the current item */259 if (cur_free <= ih_size) {260 tb->lbytes = -1;261 return;262 }263 cur_free -= ih_size;264 265 tb->lbytes = op_check_left(vi, cur_free, 0, 0);266 if (tb->lbytes != -1)267 /* count partially shifted item */268 tb->lnum[0]++;269 270 break;271 }272 273 return;274}275 276/*277 * Using virtual node check, how many items can be278 * shifted to right neighbor279 */280static void check_right(struct tree_balance *tb, int h, int cur_free)281{282 int i;283 struct virtual_node *vn = tb->tb_vn;284 struct virtual_item *vi;285 int d_size, ih_size;286 287 RFALSE(cur_free < 0, "vs-8070: cur_free < 0");288 289 /* internal level */290 if (h > 0) {291 tb->rnum[h] = cur_free / (DC_SIZE + KEY_SIZE);292 return;293 }294 295 /* leaf level */296 297 if (!cur_free || !vn->vn_nr_item) {298 /* no free space */299 tb->rnum[h] = 0;300 tb->rbytes = -1;301 return;302 }303 304 RFALSE(!PATH_H_PPARENT(tb->tb_path, 0),305 "vs-8075: parent does not exist or invalid");306 307 vi = vn->vn_vi + vn->vn_nr_item - 1;308 if ((unsigned int)cur_free >=309 (vn->vn_size -310 ((vi->vi_type & VI_TYPE_RIGHT_MERGEABLE) ? IH_SIZE : 0))) {311 /* all contents of S[0] fits into R[0] */312 313 RFALSE(vn->vn_mode == M_INSERT || vn->vn_mode == M_PASTE,314 "vs-8080: invalid mode or balance condition failed");315 316 tb->rnum[h] = vn->vn_nr_item;317 tb->rbytes = -1;318 return;319 }320 321 d_size = 0, ih_size = IH_SIZE;322 323 /* last item may be merge with first item in right neighbor */324 if (vi->vi_type & VI_TYPE_RIGHT_MERGEABLE)325 d_size = -(int)IH_SIZE, ih_size = 0;326 327 tb->rnum[0] = 0;328 for (i = vn->vn_nr_item - 1; i >= 0;329 i--, d_size = 0, ih_size = IH_SIZE, vi--) {330 d_size += vi->vi_item_len;331 if (cur_free >= d_size) {332 /* the item can be shifted entirely */333 cur_free -= d_size;334 tb->rnum[0]++;335 continue;336 }337 338 /*339 * check whether R[0] can hold ih and at least one340 * byte of the item body341 */342 343 /* cannot shift even a part of the current item */344 if (cur_free <= ih_size) {345 tb->rbytes = -1;346 return;347 }348 349 /*350 * R[0] can hold the header of the item and at least351 * one byte of its body352 */353 cur_free -= ih_size; /* cur_free is still > 0 */354 355 tb->rbytes = op_check_right(vi, cur_free);356 if (tb->rbytes != -1)357 /* count partially shifted item */358 tb->rnum[0]++;359 360 break;361 }362 363 return;364}365 366/*367 * from - number of items, which are shifted to left neighbor entirely368 * to - number of item, which are shifted to right neighbor entirely369 * from_bytes - number of bytes of boundary item (or directory entries)370 * which are shifted to left neighbor371 * to_bytes - number of bytes of boundary item (or directory entries)372 * which are shifted to right neighbor373 */374static int get_num_ver(int mode, struct tree_balance *tb, int h,375 int from, int from_bytes,376 int to, int to_bytes, short *snum012, int flow)377{378 int i;379 int units;380 struct virtual_node *vn = tb->tb_vn;381 int total_node_size, max_node_size, current_item_size;382 int needed_nodes;383 384 /* position of item we start filling node from */385 int start_item;386 387 /* position of item we finish filling node by */388 int end_item;389 390 /*391 * number of first bytes (entries for directory) of start_item-th item392 * we do not include into node that is being filled393 */394 int start_bytes;395 396 /*397 * number of last bytes (entries for directory) of end_item-th item398 * we do node include into node that is being filled399 */400 int end_bytes;401 402 /*403 * these are positions in virtual item of items, that are split404 * between S[0] and S1new and S1new and S2new405 */406 int split_item_positions[2];407 408 split_item_positions[0] = -1;409 split_item_positions[1] = -1;410 411 /*412 * We only create additional nodes if we are in insert or paste mode413 * or we are in replace mode at the internal level. If h is 0 and414 * the mode is M_REPLACE then in fix_nodes we change the mode to415 * paste or insert before we get here in the code.416 */417 RFALSE(tb->insert_size[h] < 0 || (mode != M_INSERT && mode != M_PASTE),418 "vs-8100: insert_size < 0 in overflow");419 420 max_node_size = MAX_CHILD_SIZE(PATH_H_PBUFFER(tb->tb_path, h));421 422 /*423 * snum012 [0-2] - number of items, that lay424 * to S[0], first new node and second new node425 */426 snum012[3] = -1; /* s1bytes */427 snum012[4] = -1; /* s2bytes */428 429 /* internal level */430 if (h > 0) {431 i = ((to - from) * (KEY_SIZE + DC_SIZE) + DC_SIZE);432 if (i == max_node_size)433 return 1;434 return (i / max_node_size + 1);435 }436 437 /* leaf level */438 needed_nodes = 1;439 total_node_size = 0;440 441 /* start from 'from'-th item */442 start_item = from;443 /* skip its first 'start_bytes' units */444 start_bytes = ((from_bytes != -1) ? from_bytes : 0);445 446 /* last included item is the 'end_item'-th one */447 end_item = vn->vn_nr_item - to - 1;448 /* do not count last 'end_bytes' units of 'end_item'-th item */449 end_bytes = (to_bytes != -1) ? to_bytes : 0;450 451 /*452 * go through all item beginning from the start_item-th item453 * and ending by the end_item-th item. Do not count first454 * 'start_bytes' units of 'start_item'-th item and last455 * 'end_bytes' of 'end_item'-th item456 */457 for (i = start_item; i <= end_item; i++) {458 struct virtual_item *vi = vn->vn_vi + i;459 int skip_from_end = ((i == end_item) ? end_bytes : 0);460 461 RFALSE(needed_nodes > 3, "vs-8105: too many nodes are needed");462 463 /* get size of current item */464 current_item_size = vi->vi_item_len;465 466 /*467 * do not take in calculation head part (from_bytes)468 * of from-th item469 */470 current_item_size -=471 op_part_size(vi, 0 /*from start */ , start_bytes);472 473 /* do not take in calculation tail part of last item */474 current_item_size -=475 op_part_size(vi, 1 /*from end */ , skip_from_end);476 477 /* if item fits into current node entierly */478 if (total_node_size + current_item_size <= max_node_size) {479 snum012[needed_nodes - 1]++;480 total_node_size += current_item_size;481 start_bytes = 0;482 continue;483 }484 485 /*486 * virtual item length is longer, than max size of item in487 * a node. It is impossible for direct item488 */489 if (current_item_size > max_node_size) {490 RFALSE(is_direct_le_ih(vi->vi_ih),491 "vs-8110: "492 "direct item length is %d. It can not be longer than %d",493 current_item_size, max_node_size);494 /* we will try to split it */495 flow = 1;496 }497 498 /* as we do not split items, take new node and continue */499 if (!flow) {500 needed_nodes++;501 i--;502 total_node_size = 0;503 continue;504 }505 506 /*507 * calculate number of item units which fit into node being508 * filled509 */510 {511 int free_space;512 513 free_space = max_node_size - total_node_size - IH_SIZE;514 units =515 op_check_left(vi, free_space, start_bytes,516 skip_from_end);517 /*518 * nothing fits into current node, take new519 * node and continue520 */521 if (units == -1) {522 needed_nodes++, i--, total_node_size = 0;523 continue;524 }525 }526 527 /* something fits into the current node */528 start_bytes += units;529 snum012[needed_nodes - 1 + 3] = units;530 531 if (needed_nodes > 2)532 reiserfs_warning(tb->tb_sb, "vs-8111",533 "split_item_position is out of range");534 snum012[needed_nodes - 1]++;535 split_item_positions[needed_nodes - 1] = i;536 needed_nodes++;537 /* continue from the same item with start_bytes != -1 */538 start_item = i;539 i--;540 total_node_size = 0;541 }542 543 /*544 * sum012[4] (if it is not -1) contains number of units of which545 * are to be in S1new, snum012[3] - to be in S0. They are supposed546 * to be S1bytes and S2bytes correspondingly, so recalculate547 */548 if (snum012[4] > 0) {549 int split_item_num;550 int bytes_to_r, bytes_to_l;551 int bytes_to_S1new;552 553 split_item_num = split_item_positions[1];554 bytes_to_l =555 ((from == split_item_num556 && from_bytes != -1) ? from_bytes : 0);557 bytes_to_r =558 ((end_item == split_item_num559 && end_bytes != -1) ? end_bytes : 0);560 bytes_to_S1new =561 ((split_item_positions[0] ==562 split_item_positions[1]) ? snum012[3] : 0);563 564 /* s2bytes */565 snum012[4] =566 op_unit_num(&vn->vn_vi[split_item_num]) - snum012[4] -567 bytes_to_r - bytes_to_l - bytes_to_S1new;568 569 if (vn->vn_vi[split_item_num].vi_index != TYPE_DIRENTRY &&570 vn->vn_vi[split_item_num].vi_index != TYPE_INDIRECT)571 reiserfs_warning(tb->tb_sb, "vs-8115",572 "not directory or indirect item");573 }574 575 /* now we know S2bytes, calculate S1bytes */576 if (snum012[3] > 0) {577 int split_item_num;578 int bytes_to_r, bytes_to_l;579 int bytes_to_S2new;580 581 split_item_num = split_item_positions[0];582 bytes_to_l =583 ((from == split_item_num584 && from_bytes != -1) ? from_bytes : 0);585 bytes_to_r =586 ((end_item == split_item_num587 && end_bytes != -1) ? end_bytes : 0);588 bytes_to_S2new =589 ((split_item_positions[0] == split_item_positions[1]590 && snum012[4] != -1) ? snum012[4] : 0);591 592 /* s1bytes */593 snum012[3] =594 op_unit_num(&vn->vn_vi[split_item_num]) - snum012[3] -595 bytes_to_r - bytes_to_l - bytes_to_S2new;596 }597 598 return needed_nodes;599}600 601 602/*603 * Set parameters for balancing.604 * Performs write of results of analysis of balancing into structure tb,605 * where it will later be used by the functions that actually do the balancing.606 * Parameters:607 * tb tree_balance structure;608 * h current level of the node;609 * lnum number of items from S[h] that must be shifted to L[h];610 * rnum number of items from S[h] that must be shifted to R[h];611 * blk_num number of blocks that S[h] will be splitted into;612 * s012 number of items that fall into splitted nodes.613 * lbytes number of bytes which flow to the left neighbor from the614 * item that is not shifted entirely615 * rbytes number of bytes which flow to the right neighbor from the616 * item that is not shifted entirely617 * s1bytes number of bytes which flow to the first new node when618 * S[0] splits (this number is contained in s012 array)619 */620 621static void set_parameters(struct tree_balance *tb, int h, int lnum,622 int rnum, int blk_num, short *s012, int lb, int rb)623{624 625 tb->lnum[h] = lnum;626 tb->rnum[h] = rnum;627 tb->blknum[h] = blk_num;628 629 /* only for leaf level */630 if (h == 0) {631 if (s012 != NULL) {632 tb->s0num = *s012++;633 tb->snum[0] = *s012++;634 tb->snum[1] = *s012++;635 tb->sbytes[0] = *s012++;636 tb->sbytes[1] = *s012;637 }638 tb->lbytes = lb;639 tb->rbytes = rb;640 }641 PROC_INFO_ADD(tb->tb_sb, lnum[h], lnum);642 PROC_INFO_ADD(tb->tb_sb, rnum[h], rnum);643 644 PROC_INFO_ADD(tb->tb_sb, lbytes[h], lb);645 PROC_INFO_ADD(tb->tb_sb, rbytes[h], rb);646}647 648/*649 * check if node disappears if we shift tb->lnum[0] items to left650 * neighbor and tb->rnum[0] to the right one.651 */652static int is_leaf_removable(struct tree_balance *tb)653{654 struct virtual_node *vn = tb->tb_vn;655 int to_left, to_right;656 int size;657 int remain_items;658 659 /*660 * number of items that will be shifted to left (right) neighbor661 * entirely662 */663 to_left = tb->lnum[0] - ((tb->lbytes != -1) ? 1 : 0);664 to_right = tb->rnum[0] - ((tb->rbytes != -1) ? 1 : 0);665 remain_items = vn->vn_nr_item;666 667 /* how many items remain in S[0] after shiftings to neighbors */668 remain_items -= (to_left + to_right);669 670 /* all content of node can be shifted to neighbors */671 if (remain_items < 1) {672 set_parameters(tb, 0, to_left, vn->vn_nr_item - to_left, 0,673 NULL, -1, -1);674 return 1;675 }676 677 /* S[0] is not removable */678 if (remain_items > 1 || tb->lbytes == -1 || tb->rbytes == -1)679 return 0;680 681 /* check whether we can divide 1 remaining item between neighbors */682 683 /* get size of remaining item (in item units) */684 size = op_unit_num(&vn->vn_vi[to_left]);685 686 if (tb->lbytes + tb->rbytes >= size) {687 set_parameters(tb, 0, to_left + 1, to_right + 1, 0, NULL,688 tb->lbytes, -1);689 return 1;690 }691 692 return 0;693}694 695/* check whether L, S, R can be joined in one node */696static int are_leaves_removable(struct tree_balance *tb, int lfree, int rfree)697{698 struct virtual_node *vn = tb->tb_vn;699 int ih_size;700 struct buffer_head *S0;701 702 S0 = PATH_H_PBUFFER(tb->tb_path, 0);703 704 ih_size = 0;705 if (vn->vn_nr_item) {706 if (vn->vn_vi[0].vi_type & VI_TYPE_LEFT_MERGEABLE)707 ih_size += IH_SIZE;708 709 if (vn->vn_vi[vn->vn_nr_item - 1].710 vi_type & VI_TYPE_RIGHT_MERGEABLE)711 ih_size += IH_SIZE;712 } else {713 /* there was only one item and it will be deleted */714 struct item_head *ih;715 716 RFALSE(B_NR_ITEMS(S0) != 1,717 "vs-8125: item number must be 1: it is %d",718 B_NR_ITEMS(S0));719 720 ih = item_head(S0, 0);721 if (tb->CFR[0]722 && !comp_short_le_keys(&ih->ih_key,723 internal_key(tb->CFR[0],724 tb->rkey[0])))725 /*726 * Directory must be in correct state here: that is727 * somewhere at the left side should exist first728 * directory item. But the item being deleted can729 * not be that first one because its right neighbor730 * is item of the same directory. (But first item731 * always gets deleted in last turn). So, neighbors732 * of deleted item can be merged, so we can save733 * ih_size734 */735 if (is_direntry_le_ih(ih)) {736 ih_size = IH_SIZE;737 738 /*739 * we might check that left neighbor exists740 * and is of the same directory741 */742 RFALSE(le_ih_k_offset(ih) == DOT_OFFSET,743 "vs-8130: first directory item can not be removed until directory is not empty");744 }745 746 }747 748 if (MAX_CHILD_SIZE(S0) + vn->vn_size <= rfree + lfree + ih_size) {749 set_parameters(tb, 0, -1, -1, -1, NULL, -1, -1);750 PROC_INFO_INC(tb->tb_sb, leaves_removable);751 return 1;752 }753 return 0;754 755}756 757/* when we do not split item, lnum and rnum are numbers of entire items */758#define SET_PAR_SHIFT_LEFT \759if (h)\760{\761 int to_l;\762 \763 to_l = (MAX_NR_KEY(Sh)+1 - lpar + vn->vn_nr_item + 1) / 2 -\764 (MAX_NR_KEY(Sh) + 1 - lpar);\765 \766 set_parameters (tb, h, to_l, 0, lnver, NULL, -1, -1);\767}\768else \769{\770 if (lset==LEFT_SHIFT_FLOW)\771 set_parameters (tb, h, lpar, 0, lnver, snum012+lset,\772 tb->lbytes, -1);\773 else\774 set_parameters (tb, h, lpar - (tb->lbytes!=-1), 0, lnver, snum012+lset,\775 -1, -1);\776}777 778#define SET_PAR_SHIFT_RIGHT \779if (h)\780{\781 int to_r;\782 \783 to_r = (MAX_NR_KEY(Sh)+1 - rpar + vn->vn_nr_item + 1) / 2 - (MAX_NR_KEY(Sh) + 1 - rpar);\784 \785 set_parameters (tb, h, 0, to_r, rnver, NULL, -1, -1);\786}\787else \788{\789 if (rset==RIGHT_SHIFT_FLOW)\790 set_parameters (tb, h, 0, rpar, rnver, snum012+rset,\791 -1, tb->rbytes);\792 else\793 set_parameters (tb, h, 0, rpar - (tb->rbytes!=-1), rnver, snum012+rset,\794 -1, -1);\795}796 797static void free_buffers_in_tb(struct tree_balance *tb)798{799 int i;800 801 pathrelse(tb->tb_path);802 803 for (i = 0; i < MAX_HEIGHT; i++) {804 brelse(tb->L[i]);805 brelse(tb->R[i]);806 brelse(tb->FL[i]);807 brelse(tb->FR[i]);808 brelse(tb->CFL[i]);809 brelse(tb->CFR[i]);810 811 tb->L[i] = NULL;812 tb->R[i] = NULL;813 tb->FL[i] = NULL;814 tb->FR[i] = NULL;815 tb->CFL[i] = NULL;816 tb->CFR[i] = NULL;817 }818}819 820/*821 * Get new buffers for storing new nodes that are created while balancing.822 * Returns: SCHEDULE_OCCURRED - schedule occurred while the function worked;823 * CARRY_ON - schedule didn't occur while the function worked;824 * NO_DISK_SPACE - no disk space.825 */826/* The function is NOT SCHEDULE-SAFE! */827static int get_empty_nodes(struct tree_balance *tb, int h)828{829 struct buffer_head *new_bh, *Sh = PATH_H_PBUFFER(tb->tb_path, h);830 b_blocknr_t *blocknr, blocknrs[MAX_AMOUNT_NEEDED] = { 0, };831 int counter, number_of_freeblk;832 int amount_needed; /* number of needed empty blocks */833 int retval = CARRY_ON;834 struct super_block *sb = tb->tb_sb;835 836 /*837 * number_of_freeblk is the number of empty blocks which have been838 * acquired for use by the balancing algorithm minus the number of839 * empty blocks used in the previous levels of the analysis,840 * number_of_freeblk = tb->cur_blknum can be non-zero if a schedule841 * occurs after empty blocks are acquired, and the balancing analysis842 * is then restarted, amount_needed is the number needed by this843 * level (h) of the balancing analysis.844 *845 * Note that for systems with many processes writing, it would be846 * more layout optimal to calculate the total number needed by all847 * levels and then to run reiserfs_new_blocks to get all of them at848 * once.849 */850 851 /*852 * Initiate number_of_freeblk to the amount acquired prior to the853 * restart of the analysis or 0 if not restarted, then subtract the854 * amount needed by all of the levels of the tree below h.855 */856 /* blknum includes S[h], so we subtract 1 in this calculation */857 for (counter = 0, number_of_freeblk = tb->cur_blknum;858 counter < h; counter++)859 number_of_freeblk -=860 (tb->blknum[counter]) ? (tb->blknum[counter] -861 1) : 0;862 863 /* Allocate missing empty blocks. */864 /* if Sh == 0 then we are getting a new root */865 amount_needed = (Sh) ? (tb->blknum[h] - 1) : 1;866 /*867 * Amount_needed = the amount that we need more than the868 * amount that we have.869 */870 if (amount_needed > number_of_freeblk)871 amount_needed -= number_of_freeblk;872 else /* If we have enough already then there is nothing to do. */873 return CARRY_ON;874 875 /*876 * No need to check quota - is not allocated for blocks used877 * for formatted nodes878 */879 if (reiserfs_new_form_blocknrs(tb, blocknrs,880 amount_needed) == NO_DISK_SPACE)881 return NO_DISK_SPACE;882 883 /* for each blocknumber we just got, get a buffer and stick it on FEB */884 for (blocknr = blocknrs, counter = 0;885 counter < amount_needed; blocknr++, counter++) {886 887 RFALSE(!*blocknr,888 "PAP-8135: reiserfs_new_blocknrs failed when got new blocks");889 890 new_bh = sb_getblk(sb, *blocknr);891 RFALSE(buffer_dirty(new_bh) ||892 buffer_journaled(new_bh) ||893 buffer_journal_dirty(new_bh),894 "PAP-8140: journaled or dirty buffer %b for the new block",895 new_bh);896 897 /* Put empty buffers into the array. */898 RFALSE(tb->FEB[tb->cur_blknum],899 "PAP-8141: busy slot for new buffer");900 901 set_buffer_journal_new(new_bh);902 tb->FEB[tb->cur_blknum++] = new_bh;903 }904 905 if (retval == CARRY_ON && FILESYSTEM_CHANGED_TB(tb))906 retval = REPEAT_SEARCH;907 908 return retval;909}910 911/*912 * Get free space of the left neighbor, which is stored in the parent913 * node of the left neighbor.914 */915static int get_lfree(struct tree_balance *tb, int h)916{917 struct buffer_head *l, *f;918 int order;919 920 if ((f = PATH_H_PPARENT(tb->tb_path, h)) == NULL ||921 (l = tb->FL[h]) == NULL)922 return 0;923 924 if (f == l)925 order = PATH_H_B_ITEM_ORDER(tb->tb_path, h) - 1;926 else {927 order = B_NR_ITEMS(l);928 f = l;929 }930 931 return (MAX_CHILD_SIZE(f) - dc_size(B_N_CHILD(f, order)));932}933 934/*935 * Get free space of the right neighbor,936 * which is stored in the parent node of the right neighbor.937 */938static int get_rfree(struct tree_balance *tb, int h)939{940 struct buffer_head *r, *f;941 int order;942 943 if ((f = PATH_H_PPARENT(tb->tb_path, h)) == NULL ||944 (r = tb->FR[h]) == NULL)945 return 0;946 947 if (f == r)948 order = PATH_H_B_ITEM_ORDER(tb->tb_path, h) + 1;949 else {950 order = 0;951 f = r;952 }953 954 return (MAX_CHILD_SIZE(f) - dc_size(B_N_CHILD(f, order)));955 956}957 958/* Check whether left neighbor is in memory. */959static int is_left_neighbor_in_cache(struct tree_balance *tb, int h)960{961 struct buffer_head *father, *left;962 struct super_block *sb = tb->tb_sb;963 b_blocknr_t left_neighbor_blocknr;964 int left_neighbor_position;965 966 /* Father of the left neighbor does not exist. */967 if (!tb->FL[h])968 return 0;969 970 /* Calculate father of the node to be balanced. */971 father = PATH_H_PBUFFER(tb->tb_path, h + 1);972 973 RFALSE(!father ||974 !B_IS_IN_TREE(father) ||975 !B_IS_IN_TREE(tb->FL[h]) ||976 !buffer_uptodate(father) ||977 !buffer_uptodate(tb->FL[h]),978 "vs-8165: F[h] (%b) or FL[h] (%b) is invalid",979 father, tb->FL[h]);980 981 /*982 * Get position of the pointer to the left neighbor983 * into the left father.984 */985 left_neighbor_position = (father == tb->FL[h]) ?986 tb->lkey[h] : B_NR_ITEMS(tb->FL[h]);987 /* Get left neighbor block number. */988 left_neighbor_blocknr =989 B_N_CHILD_NUM(tb->FL[h], left_neighbor_position);990 /* Look for the left neighbor in the cache. */991 if ((left = sb_find_get_block(sb, left_neighbor_blocknr))) {992 993 RFALSE(buffer_uptodate(left) && !B_IS_IN_TREE(left),994 "vs-8170: left neighbor (%b %z) is not in the tree",995 left, left);996 put_bh(left);997 return 1;998 }999 1000 return 0;1001}1002 1003#define LEFT_PARENTS 'l'1004#define RIGHT_PARENTS 'r'1005 1006static void decrement_key(struct cpu_key *key)1007{1008 /* call item specific function for this key */1009 item_ops[cpu_key_k_type(key)]->decrement_key(key);1010}1011 1012/*1013 * Calculate far left/right parent of the left/right neighbor of the1014 * current node, that is calculate the left/right (FL[h]/FR[h]) neighbor1015 * of the parent F[h].1016 * Calculate left/right common parent of the current node and L[h]/R[h].1017 * Calculate left/right delimiting key position.1018 * Returns: PATH_INCORRECT - path in the tree is not correct1019 * SCHEDULE_OCCURRED - schedule occurred while the function worked1020 * CARRY_ON - schedule didn't occur while the function1021 * worked1022 */1023static int get_far_parent(struct tree_balance *tb,1024 int h,1025 struct buffer_head **pfather,1026 struct buffer_head **pcom_father, char c_lr_par)1027{1028 struct buffer_head *parent;1029 INITIALIZE_PATH(s_path_to_neighbor_father);1030 struct treepath *path = tb->tb_path;1031 struct cpu_key s_lr_father_key;1032 int counter,1033 position = INT_MAX,1034 first_last_position = 0,1035 path_offset = PATH_H_PATH_OFFSET(path, h);1036 1037 /*1038 * Starting from F[h] go upwards in the tree, and look for the common1039 * ancestor of F[h], and its neighbor l/r, that should be obtained.1040 */1041 1042 counter = path_offset;1043 1044 RFALSE(counter < FIRST_PATH_ELEMENT_OFFSET,1045 "PAP-8180: invalid path length");1046 1047 for (; counter > FIRST_PATH_ELEMENT_OFFSET; counter--) {1048 /*1049 * Check whether parent of the current buffer in the path1050 * is really parent in the tree.1051 */1052 if (!B_IS_IN_TREE1053 (parent = PATH_OFFSET_PBUFFER(path, counter - 1)))1054 return REPEAT_SEARCH;1055 1056 /* Check whether position in the parent is correct. */1057 if ((position =1058 PATH_OFFSET_POSITION(path,1059 counter - 1)) >1060 B_NR_ITEMS(parent))1061 return REPEAT_SEARCH;1062 1063 /*1064 * Check whether parent at the path really points1065 * to the child.1066 */1067 if (B_N_CHILD_NUM(parent, position) !=1068 PATH_OFFSET_PBUFFER(path, counter)->b_blocknr)1069 return REPEAT_SEARCH;1070 1071 /*1072 * Return delimiting key if position in the parent is not1073 * equal to first/last one.1074 */1075 if (c_lr_par == RIGHT_PARENTS)1076 first_last_position = B_NR_ITEMS(parent);1077 if (position != first_last_position) {1078 *pcom_father = parent;1079 get_bh(*pcom_father);1080 /*(*pcom_father = parent)->b_count++; */1081 break;1082 }1083 }1084 1085 /* if we are in the root of the tree, then there is no common father */1086 if (counter == FIRST_PATH_ELEMENT_OFFSET) {1087 /*1088 * Check whether first buffer in the path is the1089 * root of the tree.1090 */1091 if (PATH_OFFSET_PBUFFER1092 (tb->tb_path,1093 FIRST_PATH_ELEMENT_OFFSET)->b_blocknr ==1094 SB_ROOT_BLOCK(tb->tb_sb)) {1095 *pfather = *pcom_father = NULL;1096 return CARRY_ON;1097 }1098 return REPEAT_SEARCH;1099 }1100 1101 RFALSE(B_LEVEL(*pcom_father) <= DISK_LEAF_NODE_LEVEL,1102 "PAP-8185: (%b %z) level too small",1103 *pcom_father, *pcom_father);1104 1105 /* Check whether the common parent is locked. */1106 1107 if (buffer_locked(*pcom_father)) {1108 1109 /* Release the write lock while the buffer is busy */1110 int depth = reiserfs_write_unlock_nested(tb->tb_sb);1111 __wait_on_buffer(*pcom_father);1112 reiserfs_write_lock_nested(tb->tb_sb, depth);1113 if (FILESYSTEM_CHANGED_TB(tb)) {1114 brelse(*pcom_father);1115 return REPEAT_SEARCH;1116 }1117 }1118 1119 /*1120 * So, we got common parent of the current node and its1121 * left/right neighbor. Now we are getting the parent of the1122 * left/right neighbor.1123 */1124 1125 /* Form key to get parent of the left/right neighbor. */1126 le_key2cpu_key(&s_lr_father_key,1127 internal_key(*pcom_father,1128 (c_lr_par ==1129 LEFT_PARENTS) ? (tb->lkey[h - 1] =1130 position -1131 1) : (tb->rkey[h -1132 1] =1133 position)));1134 1135 if (c_lr_par == LEFT_PARENTS)1136 decrement_key(&s_lr_father_key);1137 1138 if (search_by_key1139 (tb->tb_sb, &s_lr_father_key, &s_path_to_neighbor_father,1140 h + 1) == IO_ERROR)1141 /* path is released */1142 return IO_ERROR;1143 1144 if (FILESYSTEM_CHANGED_TB(tb)) {1145 pathrelse(&s_path_to_neighbor_father);1146 brelse(*pcom_father);1147 return REPEAT_SEARCH;1148 }1149 1150 *pfather = PATH_PLAST_BUFFER(&s_path_to_neighbor_father);1151 1152 RFALSE(B_LEVEL(*pfather) != h + 1,1153 "PAP-8190: (%b %z) level too small", *pfather, *pfather);1154 RFALSE(s_path_to_neighbor_father.path_length <1155 FIRST_PATH_ELEMENT_OFFSET, "PAP-8192: path length is too small");1156 1157 s_path_to_neighbor_father.path_length--;1158 pathrelse(&s_path_to_neighbor_father);1159 return CARRY_ON;1160}1161 1162/*1163 * Get parents of neighbors of node in the path(S[path_offset]) and1164 * common parents of S[path_offset] and L[path_offset]/R[path_offset]:1165 * F[path_offset], FL[path_offset], FR[path_offset], CFL[path_offset],1166 * CFR[path_offset].1167 * Calculate numbers of left and right delimiting keys position:1168 * lkey[path_offset], rkey[path_offset].1169 * Returns: SCHEDULE_OCCURRED - schedule occurred while the function worked1170 * CARRY_ON - schedule didn't occur while the function worked1171 */1172static int get_parents(struct tree_balance *tb, int h)1173{1174 struct treepath *path = tb->tb_path;1175 int position,1176 ret,1177 path_offset = PATH_H_PATH_OFFSET(tb->tb_path, h);1178 struct buffer_head *curf, *curcf;1179 1180 /* Current node is the root of the tree or will be root of the tree */1181 if (path_offset <= FIRST_PATH_ELEMENT_OFFSET) {1182 /*1183 * The root can not have parents.1184 * Release nodes which previously were obtained as1185 * parents of the current node neighbors.1186 */1187 brelse(tb->FL[h]);1188 brelse(tb->CFL[h]);1189 brelse(tb->FR[h]);1190 brelse(tb->CFR[h]);1191 tb->FL[h] = NULL;1192 tb->CFL[h] = NULL;1193 tb->FR[h] = NULL;1194 tb->CFR[h] = NULL;1195 return CARRY_ON;1196 }1197 1198 /* Get parent FL[path_offset] of L[path_offset]. */1199 position = PATH_OFFSET_POSITION(path, path_offset - 1);1200 if (position) {1201 /* Current node is not the first child of its parent. */1202 curf = PATH_OFFSET_PBUFFER(path, path_offset - 1);1203 curcf = PATH_OFFSET_PBUFFER(path, path_offset - 1);1204 get_bh(curf);1205 get_bh(curf);1206 tb->lkey[h] = position - 1;1207 } else {1208 /*1209 * Calculate current parent of L[path_offset], which is the1210 * left neighbor of the current node. Calculate current1211 * common parent of L[path_offset] and the current node.1212 * Note that CFL[path_offset] not equal FL[path_offset] and1213 * CFL[path_offset] not equal F[path_offset].1214 * Calculate lkey[path_offset].1215 */1216 if ((ret = get_far_parent(tb, h + 1, &curf,1217 &curcf,1218 LEFT_PARENTS)) != CARRY_ON)1219 return ret;1220 }1221 1222 brelse(tb->FL[h]);1223 tb->FL[h] = curf; /* New initialization of FL[h]. */1224 brelse(tb->CFL[h]);1225 tb->CFL[h] = curcf; /* New initialization of CFL[h]. */1226 1227 RFALSE((curf && !B_IS_IN_TREE(curf)) ||1228 (curcf && !B_IS_IN_TREE(curcf)),1229 "PAP-8195: FL (%b) or CFL (%b) is invalid", curf, curcf);1230 1231 /* Get parent FR[h] of R[h]. */1232 1233 /* Current node is the last child of F[h]. FR[h] != F[h]. */1234 if (position == B_NR_ITEMS(PATH_H_PBUFFER(path, h + 1))) {1235 /*1236 * Calculate current parent of R[h], which is the right1237 * neighbor of F[h]. Calculate current common parent of1238 * R[h] and current node. Note that CFR[h] not equal1239 * FR[path_offset] and CFR[h] not equal F[h].1240 */1241 if ((ret =1242 get_far_parent(tb, h + 1, &curf, &curcf,1243 RIGHT_PARENTS)) != CARRY_ON)1244 return ret;1245 } else {1246 /* Current node is not the last child of its parent F[h]. */1247 curf = PATH_OFFSET_PBUFFER(path, path_offset - 1);1248 curcf = PATH_OFFSET_PBUFFER(path, path_offset - 1);1249 get_bh(curf);1250 get_bh(curf);1251 tb->rkey[h] = position;1252 }1253 1254 brelse(tb->FR[h]);1255 /* New initialization of FR[path_offset]. */1256 tb->FR[h] = curf;1257 1258 brelse(tb->CFR[h]);1259 /* New initialization of CFR[path_offset]. */1260 tb->CFR[h] = curcf;1261 1262 RFALSE((curf && !B_IS_IN_TREE(curf)) ||1263 (curcf && !B_IS_IN_TREE(curcf)),1264 "PAP-8205: FR (%b) or CFR (%b) is invalid", curf, curcf);1265 1266 return CARRY_ON;1267}1268 1269/*1270 * it is possible to remove node as result of shiftings to1271 * neighbors even when we insert or paste item.1272 */1273static inline int can_node_be_removed(int mode, int lfree, int sfree, int rfree,1274 struct tree_balance *tb, int h)1275{1276 struct buffer_head *Sh = PATH_H_PBUFFER(tb->tb_path, h);1277 int levbytes = tb->insert_size[h];1278 struct item_head *ih;1279 struct reiserfs_key *r_key = NULL;1280 1281 ih = item_head(Sh, 0);1282 if (tb->CFR[h])1283 r_key = internal_key(tb->CFR[h], tb->rkey[h]);1284 1285 if (lfree + rfree + sfree < MAX_CHILD_SIZE(Sh) + levbytes1286 /* shifting may merge items which might save space */1287 -1288 ((!h1289 && op_is_left_mergeable(&ih->ih_key, Sh->b_size)) ? IH_SIZE : 0)1290 -1291 ((!h && r_key1292 && op_is_left_mergeable(r_key, Sh->b_size)) ? IH_SIZE : 0)1293 + ((h) ? KEY_SIZE : 0)) {1294 /* node can not be removed */1295 if (sfree >= levbytes) {1296 /* new item fits into node S[h] without any shifting */1297 if (!h)1298 tb->s0num =1299 B_NR_ITEMS(Sh) +1300 ((mode == M_INSERT) ? 1 : 0);1301 set_parameters(tb, h, 0, 0, 1, NULL, -1, -1);1302 return NO_BALANCING_NEEDED;1303 }1304 }1305 PROC_INFO_INC(tb->tb_sb, can_node_be_removed[h]);1306 return !NO_BALANCING_NEEDED;1307}1308 1309/*1310 * Check whether current node S[h] is balanced when increasing its size by1311 * Inserting or Pasting.1312 * Calculate parameters for balancing for current level h.1313 * Parameters:1314 * tb tree_balance structure;1315 * h current level of the node;1316 * inum item number in S[h];1317 * mode i - insert, p - paste;1318 * Returns: 1 - schedule occurred;1319 * 0 - balancing for higher levels needed;1320 * -1 - no balancing for higher levels needed;1321 * -2 - no disk space.1322 */1323/* ip means Inserting or Pasting */1324static int ip_check_balance(struct tree_balance *tb, int h)1325{1326 struct virtual_node *vn = tb->tb_vn;1327 /*1328 * Number of bytes that must be inserted into (value is negative1329 * if bytes are deleted) buffer which contains node being balanced.1330 * The mnemonic is that the attempted change in node space used1331 * level is levbytes bytes.1332 */1333 int levbytes;1334 int ret;1335 1336 int lfree, sfree, rfree /* free space in L, S and R */ ;1337 1338 /*1339 * nver is short for number of vertixes, and lnver is the number if1340 * we shift to the left, rnver is the number if we shift to the1341 * right, and lrnver is the number if we shift in both directions.1342 * The goal is to minimize first the number of vertixes, and second,1343 * the number of vertixes whose contents are changed by shifting,1344 * and third the number of uncached vertixes whose contents are1345 * changed by shifting and must be read from disk.1346 */1347 int nver, lnver, rnver, lrnver;1348 1349 /*1350 * used at leaf level only, S0 = S[0] is the node being balanced,1351 * sInum [ I = 0,1,2 ] is the number of items that will1352 * remain in node SI after balancing. S1 and S2 are new1353 * nodes that might be created.1354 */1355 1356 /*1357 * we perform 8 calls to get_num_ver(). For each call we1358 * calculate five parameters. where 4th parameter is s1bytes1359 * and 5th - s2bytes1360 *1361 * s0num, s1num, s2num for 8 cases1362 * 0,1 - do not shift and do not shift but bottle1363 * 2 - shift only whole item to left1364 * 3 - shift to left and bottle as much as possible1365 * 4,5 - shift to right (whole items and as much as possible1366 * 6,7 - shift to both directions (whole items and as much as possible)1367 */1368 short snum012[40] = { 0, };1369 1370 /* Sh is the node whose balance is currently being checked */1371 struct buffer_head *Sh;1372 1373 Sh = PATH_H_PBUFFER(tb->tb_path, h);1374 levbytes = tb->insert_size[h];1375 1376 /* Calculate balance parameters for creating new root. */1377 if (!Sh) {1378 if (!h)1379 reiserfs_panic(tb->tb_sb, "vs-8210",1380 "S[0] can not be 0");1381 switch (ret = get_empty_nodes(tb, h)) {1382 /* no balancing for higher levels needed */1383 case CARRY_ON:1384 set_parameters(tb, h, 0, 0, 1, NULL, -1, -1);1385 return NO_BALANCING_NEEDED;1386 1387 case NO_DISK_SPACE:1388 case REPEAT_SEARCH:1389 return ret;1390 default:1391 reiserfs_panic(tb->tb_sb, "vs-8215", "incorrect "1392 "return value of get_empty_nodes");1393 }1394 }1395 1396 /* get parents of S[h] neighbors. */1397 ret = get_parents(tb, h);1398 if (ret != CARRY_ON)1399 return ret;1400 1401 sfree = B_FREE_SPACE(Sh);1402 1403 /* get free space of neighbors */1404 rfree = get_rfree(tb, h);1405 lfree = get_lfree(tb, h);1406 1407 /* and new item fits into node S[h] without any shifting */1408 if (can_node_be_removed(vn->vn_mode, lfree, sfree, rfree, tb, h) ==1409 NO_BALANCING_NEEDED)1410 return NO_BALANCING_NEEDED;1411 1412 create_virtual_node(tb, h);1413 1414 /*1415 * determine maximal number of items we can shift to the left1416 * neighbor (in tb structure) and the maximal number of bytes1417 * that can flow to the left neighbor from the left most liquid1418 * item that cannot be shifted from S[0] entirely (returned value)1419 */1420 check_left(tb, h, lfree);1421 1422 /*1423 * determine maximal number of items we can shift to the right1424 * neighbor (in tb structure) and the maximal number of bytes1425 * that can flow to the right neighbor from the right most liquid1426 * item that cannot be shifted from S[0] entirely (returned value)1427 */1428 check_right(tb, h, rfree);1429 1430 /*1431 * all contents of internal node S[h] can be moved into its1432 * neighbors, S[h] will be removed after balancing1433 */1434 if (h && (tb->rnum[h] + tb->lnum[h] >= vn->vn_nr_item + 1)) {1435 int to_r;1436 1437 /*1438 * Since we are working on internal nodes, and our internal1439 * nodes have fixed size entries, then we can balance by the1440 * number of items rather than the space they consume. In this1441 * routine we set the left node equal to the right node,1442 * allowing a difference of less than or equal to 1 child1443 * pointer.1444 */1445 to_r =1446 ((MAX_NR_KEY(Sh) << 1) + 2 - tb->lnum[h] - tb->rnum[h] +1447 vn->vn_nr_item + 1) / 2 - (MAX_NR_KEY(Sh) + 1 -1448 tb->rnum[h]);1449 set_parameters(tb, h, vn->vn_nr_item + 1 - to_r, to_r, 0, NULL,1450 -1, -1);1451 return CARRY_ON;1452 }1453 1454 /*1455 * this checks balance condition, that any two neighboring nodes1456 * can not fit in one node1457 */1458 RFALSE(h &&1459 (tb->lnum[h] >= vn->vn_nr_item + 1 ||1460 tb->rnum[h] >= vn->vn_nr_item + 1),1461 "vs-8220: tree is not balanced on internal level");1462 RFALSE(!h && ((tb->lnum[h] >= vn->vn_nr_item && (tb->lbytes == -1)) ||1463 (tb->rnum[h] >= vn->vn_nr_item && (tb->rbytes == -1))),1464 "vs-8225: tree is not balanced on leaf level");1465 1466 /*1467 * all contents of S[0] can be moved into its neighbors1468 * S[0] will be removed after balancing.1469 */1470 if (!h && is_leaf_removable(tb))1471 return CARRY_ON;1472 1473 /*1474 * why do we perform this check here rather than earlier??1475 * Answer: we can win 1 node in some cases above. Moreover we1476 * checked it above, when we checked, that S[0] is not removable1477 * in principle1478 */1479 1480 /* new item fits into node S[h] without any shifting */1481 if (sfree >= levbytes) {1482 if (!h)1483 tb->s0num = vn->vn_nr_item;1484 set_parameters(tb, h, 0, 0, 1, NULL, -1, -1);1485 return NO_BALANCING_NEEDED;1486 }1487 1488 {1489 int lpar, rpar, nset, lset, rset, lrset;1490 /* regular overflowing of the node */1491 1492 /*1493 * get_num_ver works in 2 modes (FLOW & NO_FLOW)1494 * lpar, rpar - number of items we can shift to left/right1495 * neighbor (including splitting item)1496 * nset, lset, rset, lrset - shows, whether flowing items1497 * give better packing1498 */1499#define FLOW 11500#define NO_FLOW 0 /* do not any splitting */1501 1502 /* we choose one of the following */1503#define NOTHING_SHIFT_NO_FLOW 01504#define NOTHING_SHIFT_FLOW 51505#define LEFT_SHIFT_NO_FLOW 101506#define LEFT_SHIFT_FLOW 151507#define RIGHT_SHIFT_NO_FLOW 201508#define RIGHT_SHIFT_FLOW 251509#define LR_SHIFT_NO_FLOW 301510#define LR_SHIFT_FLOW 351511 1512 lpar = tb->lnum[h];1513 rpar = tb->rnum[h];1514 1515 /*1516 * calculate number of blocks S[h] must be split into when1517 * nothing is shifted to the neighbors, as well as number of1518 * items in each part of the split node (s012 numbers),1519 * and number of bytes (s1bytes) of the shared drop which1520 * flow to S1 if any1521 */1522 nset = NOTHING_SHIFT_NO_FLOW;1523 nver = get_num_ver(vn->vn_mode, tb, h,1524 0, -1, h ? vn->vn_nr_item : 0, -1,1525 snum012, NO_FLOW);1526 1527 if (!h) {1528 int nver1;1529 1530 /*1531 * note, that in this case we try to bottle1532 * between S[0] and S1 (S1 - the first new node)1533 */1534 nver1 = get_num_ver(vn->vn_mode, tb, h,1535 0, -1, 0, -1,1536 snum012 + NOTHING_SHIFT_FLOW, FLOW);1537 if (nver > nver1)1538 nset = NOTHING_SHIFT_FLOW, nver = nver1;1539 }1540 1541 /*1542 * calculate number of blocks S[h] must be split into when1543 * l_shift_num first items and l_shift_bytes of the right1544 * most liquid item to be shifted are shifted to the left1545 * neighbor, as well as number of items in each part of the1546 * splitted node (s012 numbers), and number of bytes1547 * (s1bytes) of the shared drop which flow to S1 if any1548 */1549 lset = LEFT_SHIFT_NO_FLOW;1550 lnver = get_num_ver(vn->vn_mode, tb, h,1551 lpar - ((h || tb->lbytes == -1) ? 0 : 1),1552 -1, h ? vn->vn_nr_item : 0, -1,1553 snum012 + LEFT_SHIFT_NO_FLOW, NO_FLOW);1554 if (!h) {1555 int lnver1;1556 1557 lnver1 = get_num_ver(vn->vn_mode, tb, h,1558 lpar -1559 ((tb->lbytes != -1) ? 1 : 0),1560 tb->lbytes, 0, -1,1561 snum012 + LEFT_SHIFT_FLOW, FLOW);1562 if (lnver > lnver1)1563 lset = LEFT_SHIFT_FLOW, lnver = lnver1;1564 }1565 1566 /*1567 * calculate number of blocks S[h] must be split into when1568 * r_shift_num first items and r_shift_bytes of the left most1569 * liquid item to be shifted are shifted to the right neighbor,1570 * as well as number of items in each part of the splitted1571 * node (s012 numbers), and number of bytes (s1bytes) of the1572 * shared drop which flow to S1 if any1573 */1574 rset = RIGHT_SHIFT_NO_FLOW;1575 rnver = get_num_ver(vn->vn_mode, tb, h,1576 0, -1,1577 h ? (vn->vn_nr_item - rpar) : (rpar -1578 ((tb->1579 rbytes !=1580 -1) ? 1 :1581 0)), -1,1582 snum012 + RIGHT_SHIFT_NO_FLOW, NO_FLOW);1583 if (!h) {1584 int rnver1;1585 1586 rnver1 = get_num_ver(vn->vn_mode, tb, h,1587 0, -1,1588 (rpar -1589 ((tb->rbytes != -1) ? 1 : 0)),1590 tb->rbytes,1591 snum012 + RIGHT_SHIFT_FLOW, FLOW);1592 1593 if (rnver > rnver1)1594 rset = RIGHT_SHIFT_FLOW, rnver = rnver1;1595 }1596 1597 /*1598 * calculate number of blocks S[h] must be split into when1599 * items are shifted in both directions, as well as number1600 * of items in each part of the splitted node (s012 numbers),1601 * and number of bytes (s1bytes) of the shared drop which1602 * flow to S1 if any1603 */1604 lrset = LR_SHIFT_NO_FLOW;1605 lrnver = get_num_ver(vn->vn_mode, tb, h,1606 lpar - ((h || tb->lbytes == -1) ? 0 : 1),1607 -1,1608 h ? (vn->vn_nr_item - rpar) : (rpar -1609 ((tb->1610 rbytes !=1611 -1) ? 1 :1612 0)), -1,1613 snum012 + LR_SHIFT_NO_FLOW, NO_FLOW);1614 if (!h) {1615 int lrnver1;1616 1617 lrnver1 = get_num_ver(vn->vn_mode, tb, h,1618 lpar -1619 ((tb->lbytes != -1) ? 1 : 0),1620 tb->lbytes,1621 (rpar -1622 ((tb->rbytes != -1) ? 1 : 0)),1623 tb->rbytes,1624 snum012 + LR_SHIFT_FLOW, FLOW);1625 if (lrnver > lrnver1)1626 lrset = LR_SHIFT_FLOW, lrnver = lrnver1;1627 }1628 1629 /*1630 * Our general shifting strategy is:1631 * 1) to minimized number of new nodes;1632 * 2) to minimized number of neighbors involved in shifting;1633 * 3) to minimized number of disk reads;1634 */1635 1636 /* we can win TWO or ONE nodes by shifting in both directions */1637 if (lrnver < lnver && lrnver < rnver) {1638 RFALSE(h &&1639 (tb->lnum[h] != 1 ||1640 tb->rnum[h] != 1 ||1641 lrnver != 1 || rnver != 2 || lnver != 21642 || h != 1), "vs-8230: bad h");1643 if (lrset == LR_SHIFT_FLOW)1644 set_parameters(tb, h, tb->lnum[h], tb->rnum[h],1645 lrnver, snum012 + lrset,1646 tb->lbytes, tb->rbytes);1647 else1648 set_parameters(tb, h,1649 tb->lnum[h] -1650 ((tb->lbytes == -1) ? 0 : 1),1651 tb->rnum[h] -1652 ((tb->rbytes == -1) ? 0 : 1),1653 lrnver, snum012 + lrset, -1, -1);1654 1655 return CARRY_ON;1656 }1657 1658 /*1659 * if shifting doesn't lead to better packing1660 * then don't shift1661 */1662 if (nver == lrnver) {1663 set_parameters(tb, h, 0, 0, nver, snum012 + nset, -1,1664 -1);1665 return CARRY_ON;1666 }1667 1668 /*1669 * now we know that for better packing shifting in only one1670 * direction either to the left or to the right is required1671 */1672 1673 /*1674 * if shifting to the left is better than1675 * shifting to the right1676 */1677 if (lnver < rnver) {1678 SET_PAR_SHIFT_LEFT;1679 return CARRY_ON;1680 }1681 1682 /*1683 * if shifting to the right is better than1684 * shifting to the left1685 */1686 if (lnver > rnver) {1687 SET_PAR_SHIFT_RIGHT;1688 return CARRY_ON;1689 }1690 1691 /*1692 * now shifting in either direction gives the same number1693 * of nodes and we can make use of the cached neighbors1694 */1695 if (is_left_neighbor_in_cache(tb, h)) {1696 SET_PAR_SHIFT_LEFT;1697 return CARRY_ON;1698 }1699 1700 /*1701 * shift to the right independently on whether the1702 * right neighbor in cache or not1703 */1704 SET_PAR_SHIFT_RIGHT;1705 return CARRY_ON;1706 }1707}1708 1709/*1710 * Check whether current node S[h] is balanced when Decreasing its size by1711 * Deleting or Cutting for INTERNAL node of S+tree.1712 * Calculate parameters for balancing for current level h.1713 * Parameters:1714 * tb tree_balance structure;1715 * h current level of the node;1716 * inum item number in S[h];1717 * mode i - insert, p - paste;1718 * Returns: 1 - schedule occurred;1719 * 0 - balancing for higher levels needed;1720 * -1 - no balancing for higher levels needed;1721 * -2 - no disk space.1722 *1723 * Note: Items of internal nodes have fixed size, so the balance condition for1724 * the internal part of S+tree is as for the B-trees.1725 */1726static int dc_check_balance_internal(struct tree_balance *tb, int h)1727{1728 struct virtual_node *vn = tb->tb_vn;1729 1730 /*1731 * Sh is the node whose balance is currently being checked,1732 * and Fh is its father.1733 */1734 struct buffer_head *Sh, *Fh;1735 int ret;1736 int lfree, rfree /* free space in L and R */ ;1737 1738 Sh = PATH_H_PBUFFER(tb->tb_path, h);1739 Fh = PATH_H_PPARENT(tb->tb_path, h);1740 1741 /*1742 * using tb->insert_size[h], which is negative in this case,1743 * create_virtual_node calculates:1744 * new_nr_item = number of items node would have if operation is1745 * performed without balancing (new_nr_item);1746 */1747 create_virtual_node(tb, h);1748 1749 if (!Fh) { /* S[h] is the root. */1750 /* no balancing for higher levels needed */1751 if (vn->vn_nr_item > 0) {1752 set_parameters(tb, h, 0, 0, 1, NULL, -1, -1);1753 return NO_BALANCING_NEEDED;1754 }1755 /*1756 * new_nr_item == 0.1757 * Current root will be deleted resulting in1758 * decrementing the tree height.1759 */1760 set_parameters(tb, h, 0, 0, 0, NULL, -1, -1);1761 return CARRY_ON;1762 }1763 1764 if ((ret = get_parents(tb, h)) != CARRY_ON)1765 return ret;1766 1767 /* get free space of neighbors */1768 rfree = get_rfree(tb, h);1769 lfree = get_lfree(tb, h);1770 1771 /* determine maximal number of items we can fit into neighbors */1772 check_left(tb, h, lfree);1773 check_right(tb, h, rfree);1774 1775 /*1776 * Balance condition for the internal node is valid.1777 * In this case we balance only if it leads to better packing.1778 */1779 if (vn->vn_nr_item >= MIN_NR_KEY(Sh)) {1780 /*1781 * Here we join S[h] with one of its neighbors,1782 * which is impossible with greater values of new_nr_item.1783 */1784 if (vn->vn_nr_item == MIN_NR_KEY(Sh)) {1785 /* All contents of S[h] can be moved to L[h]. */1786 if (tb->lnum[h] >= vn->vn_nr_item + 1) {1787 int n;1788 int order_L;1789 1790 order_L =1791 ((n =1792 PATH_H_B_ITEM_ORDER(tb->tb_path,1793 h)) ==1794 0) ? B_NR_ITEMS(tb->FL[h]) : n - 1;1795 n = dc_size(B_N_CHILD(tb->FL[h], order_L)) /1796 (DC_SIZE + KEY_SIZE);1797 set_parameters(tb, h, -n - 1, 0, 0, NULL, -1,1798 -1);1799 return CARRY_ON;1800 }1801 1802 /* All contents of S[h] can be moved to R[h]. */1803 if (tb->rnum[h] >= vn->vn_nr_item + 1) {1804 int n;1805 int order_R;1806 1807 order_R =1808 ((n =1809 PATH_H_B_ITEM_ORDER(tb->tb_path,1810 h)) ==1811 B_NR_ITEMS(Fh)) ? 0 : n + 1;1812 n = dc_size(B_N_CHILD(tb->FR[h], order_R)) /1813 (DC_SIZE + KEY_SIZE);1814 set_parameters(tb, h, 0, -n - 1, 0, NULL, -1,1815 -1);1816 return CARRY_ON;1817 }1818 }1819 1820 /*1821 * All contents of S[h] can be moved to the neighbors1822 * (L[h] & R[h]).1823 */1824 if (tb->rnum[h] + tb->lnum[h] >= vn->vn_nr_item + 1) {1825 int to_r;1826 1827 to_r =1828 ((MAX_NR_KEY(Sh) << 1) + 2 - tb->lnum[h] -1829 tb->rnum[h] + vn->vn_nr_item + 1) / 2 -1830 (MAX_NR_KEY(Sh) + 1 - tb->rnum[h]);1831 set_parameters(tb, h, vn->vn_nr_item + 1 - to_r, to_r,1832 0, NULL, -1, -1);1833 return CARRY_ON;1834 }1835 1836 /* Balancing does not lead to better packing. */1837 set_parameters(tb, h, 0, 0, 1, NULL, -1, -1);1838 return NO_BALANCING_NEEDED;1839 }1840 1841 /*1842 * Current node contain insufficient number of items.1843 * Balancing is required.1844 */1845 /* Check whether we can merge S[h] with left neighbor. */1846 if (tb->lnum[h] >= vn->vn_nr_item + 1)1847 if (is_left_neighbor_in_cache(tb, h)1848 || tb->rnum[h] < vn->vn_nr_item + 1 || !tb->FR[h]) {1849 int n;1850 int order_L;1851 1852 order_L =1853 ((n =1854 PATH_H_B_ITEM_ORDER(tb->tb_path,1855 h)) ==1856 0) ? B_NR_ITEMS(tb->FL[h]) : n - 1;1857 n = dc_size(B_N_CHILD(tb->FL[h], order_L)) / (DC_SIZE +1858 KEY_SIZE);1859 set_parameters(tb, h, -n - 1, 0, 0, NULL, -1, -1);1860 return CARRY_ON;1861 }1862 1863 /* Check whether we can merge S[h] with right neighbor. */1864 if (tb->rnum[h] >= vn->vn_nr_item + 1) {1865 int n;1866 int order_R;1867 1868 order_R =1869 ((n =1870 PATH_H_B_ITEM_ORDER(tb->tb_path,1871 h)) == B_NR_ITEMS(Fh)) ? 0 : (n + 1);1872 n = dc_size(B_N_CHILD(tb->FR[h], order_R)) / (DC_SIZE +1873 KEY_SIZE);1874 set_parameters(tb, h, 0, -n - 1, 0, NULL, -1, -1);1875 return CARRY_ON;1876 }1877 1878 /* All contents of S[h] can be moved to the neighbors (L[h] & R[h]). */1879 if (tb->rnum[h] + tb->lnum[h] >= vn->vn_nr_item + 1) {1880 int to_r;1881 1882 to_r =1883 ((MAX_NR_KEY(Sh) << 1) + 2 - tb->lnum[h] - tb->rnum[h] +1884 vn->vn_nr_item + 1) / 2 - (MAX_NR_KEY(Sh) + 1 -1885 tb->rnum[h]);1886 set_parameters(tb, h, vn->vn_nr_item + 1 - to_r, to_r, 0, NULL,1887 -1, -1);1888 return CARRY_ON;1889 }1890 1891 /* For internal nodes try to borrow item from a neighbor */1892 RFALSE(!tb->FL[h] && !tb->FR[h], "vs-8235: trying to borrow for root");1893 1894 /* Borrow one or two items from caching neighbor */1895 if (is_left_neighbor_in_cache(tb, h) || !tb->FR[h]) {1896 int from_l;1897 1898 from_l =1899 (MAX_NR_KEY(Sh) + 1 - tb->lnum[h] + vn->vn_nr_item +1900 1) / 2 - (vn->vn_nr_item + 1);1901 set_parameters(tb, h, -from_l, 0, 1, NULL, -1, -1);1902 return CARRY_ON;1903 }1904 1905 set_parameters(tb, h, 0,1906 -((MAX_NR_KEY(Sh) + 1 - tb->rnum[h] + vn->vn_nr_item +1907 1) / 2 - (vn->vn_nr_item + 1)), 1, NULL, -1, -1);1908 return CARRY_ON;1909}1910 1911/*1912 * Check whether current node S[h] is balanced when Decreasing its size by1913 * Deleting or Truncating for LEAF node of S+tree.1914 * Calculate parameters for balancing for current level h.1915 * Parameters:1916 * tb tree_balance structure;1917 * h current level of the node;1918 * inum item number in S[h];1919 * mode i - insert, p - paste;1920 * Returns: 1 - schedule occurred;1921 * 0 - balancing for higher levels needed;1922 * -1 - no balancing for higher levels needed;1923 * -2 - no disk space.1924 */1925static int dc_check_balance_leaf(struct tree_balance *tb, int h)1926{1927 struct virtual_node *vn = tb->tb_vn;1928 1929 /*1930 * Number of bytes that must be deleted from1931 * (value is negative if bytes are deleted) buffer which1932 * contains node being balanced. The mnemonic is that the1933 * attempted change in node space used level is levbytes bytes.1934 */1935 int levbytes;1936 1937 /* the maximal item size */1938 int maxsize, ret;1939 1940 /*1941 * S0 is the node whose balance is currently being checked,1942 * and F0 is its father.1943 */1944 struct buffer_head *S0, *F0;1945 int lfree, rfree /* free space in L and R */ ;1946 1947 S0 = PATH_H_PBUFFER(tb->tb_path, 0);1948 F0 = PATH_H_PPARENT(tb->tb_path, 0);1949 1950 levbytes = tb->insert_size[h];1951 1952 maxsize = MAX_CHILD_SIZE(S0); /* maximal possible size of an item */1953 1954 if (!F0) { /* S[0] is the root now. */1955 1956 RFALSE(-levbytes >= maxsize - B_FREE_SPACE(S0),1957 "vs-8240: attempt to create empty buffer tree");1958 1959 set_parameters(tb, h, 0, 0, 1, NULL, -1, -1);1960 return NO_BALANCING_NEEDED;1961 }1962 1963 if ((ret = get_parents(tb, h)) != CARRY_ON)1964 return ret;1965 1966 /* get free space of neighbors */1967 rfree = get_rfree(tb, h);1968 lfree = get_lfree(tb, h);1969 1970 create_virtual_node(tb, h);1971 1972 /* if 3 leaves can be merge to one, set parameters and return */1973 if (are_leaves_removable(tb, lfree, rfree))1974 return CARRY_ON;1975 1976 /*1977 * determine maximal number of items we can shift to the left/right1978 * neighbor and the maximal number of bytes that can flow to the1979 * left/right neighbor from the left/right most liquid item that1980 * cannot be shifted from S[0] entirely1981 */1982 check_left(tb, h, lfree);1983 check_right(tb, h, rfree);1984 1985 /* check whether we can merge S with left neighbor. */1986 if (tb->lnum[0] >= vn->vn_nr_item && tb->lbytes == -1)1987 if (is_left_neighbor_in_cache(tb, h) || ((tb->rnum[0] - ((tb->rbytes == -1) ? 0 : 1)) < vn->vn_nr_item) || /* S can not be merged with R */1988 !tb->FR[h]) {1989 1990 RFALSE(!tb->FL[h],1991 "vs-8245: dc_check_balance_leaf: FL[h] must exist");1992 1993 /* set parameter to merge S[0] with its left neighbor */1994 set_parameters(tb, h, -1, 0, 0, NULL, -1, -1);1995 return CARRY_ON;1996 }1997 1998 /* check whether we can merge S[0] with right neighbor. */1999 if (tb->rnum[0] >= vn->vn_nr_item && tb->rbytes == -1) {2000 set_parameters(tb, h, 0, -1, 0, NULL, -1, -1);2001 return CARRY_ON;2002 }2003 2004 /*2005 * All contents of S[0] can be moved to the neighbors (L[0] & R[0]).2006 * Set parameters and return2007 */2008 if (is_leaf_removable(tb))2009 return CARRY_ON;2010 2011 /* Balancing is not required. */2012 tb->s0num = vn->vn_nr_item;2013 set_parameters(tb, h, 0, 0, 1, NULL, -1, -1);2014 return NO_BALANCING_NEEDED;2015}2016 2017/*2018 * Check whether current node S[h] is balanced when Decreasing its size by2019 * Deleting or Cutting.2020 * Calculate parameters for balancing for current level h.2021 * Parameters:2022 * tb tree_balance structure;2023 * h current level of the node;2024 * inum item number in S[h];2025 * mode d - delete, c - cut.2026 * Returns: 1 - schedule occurred;2027 * 0 - balancing for higher levels needed;2028 * -1 - no balancing for higher levels needed;2029 * -2 - no disk space.2030 */2031static int dc_check_balance(struct tree_balance *tb, int h)2032{2033 RFALSE(!(PATH_H_PBUFFER(tb->tb_path, h)),2034 "vs-8250: S is not initialized");2035 2036 if (h)2037 return dc_check_balance_internal(tb, h);2038 else2039 return dc_check_balance_leaf(tb, h);2040}2041 2042/*2043 * Check whether current node S[h] is balanced.2044 * Calculate parameters for balancing for current level h.2045 * Parameters:2046 *2047 * tb tree_balance structure:2048 *2049 * tb is a large structure that must be read about in the header2050 * file at the same time as this procedure if the reader is2051 * to successfully understand this procedure2052 *2053 * h current level of the node;2054 * inum item number in S[h];2055 * mode i - insert, p - paste, d - delete, c - cut.2056 * Returns: 1 - schedule occurred;2057 * 0 - balancing for higher levels needed;2058 * -1 - no balancing for higher levels needed;2059 * -2 - no disk space.2060 */2061static int check_balance(int mode,2062 struct tree_balance *tb,2063 int h,2064 int inum,2065 int pos_in_item,2066 struct item_head *ins_ih, const void *data)2067{2068 struct virtual_node *vn;2069 2070 vn = tb->tb_vn = (struct virtual_node *)(tb->vn_buf);2071 vn->vn_free_ptr = (char *)(tb->tb_vn + 1);2072 vn->vn_mode = mode;2073 vn->vn_affected_item_num = inum;2074 vn->vn_pos_in_item = pos_in_item;2075 vn->vn_ins_ih = ins_ih;2076 vn->vn_data = data;2077 2078 RFALSE(mode == M_INSERT && !vn->vn_ins_ih,2079 "vs-8255: ins_ih can not be 0 in insert mode");2080 2081 /* Calculate balance parameters when size of node is increasing. */2082 if (tb->insert_size[h] > 0)2083 return ip_check_balance(tb, h);2084 2085 /* Calculate balance parameters when size of node is decreasing. */2086 return dc_check_balance(tb, h);2087}2088 2089/* Check whether parent at the path is the really parent of the current node.*/2090static int get_direct_parent(struct tree_balance *tb, int h)2091{2092 struct buffer_head *bh;2093 struct treepath *path = tb->tb_path;2094 int position,2095 path_offset = PATH_H_PATH_OFFSET(tb->tb_path, h);2096 2097 /* We are in the root or in the new root. */2098 if (path_offset <= FIRST_PATH_ELEMENT_OFFSET) {2099 2100 RFALSE(path_offset < FIRST_PATH_ELEMENT_OFFSET - 1,2101 "PAP-8260: invalid offset in the path");2102 2103 if (PATH_OFFSET_PBUFFER(path, FIRST_PATH_ELEMENT_OFFSET)->2104 b_blocknr == SB_ROOT_BLOCK(tb->tb_sb)) {2105 /* Root is not changed. */2106 PATH_OFFSET_PBUFFER(path, path_offset - 1) = NULL;2107 PATH_OFFSET_POSITION(path, path_offset - 1) = 0;2108 return CARRY_ON;2109 }2110 /* Root is changed and we must recalculate the path. */2111 return REPEAT_SEARCH;2112 }2113 2114 /* Parent in the path is not in the tree. */2115 if (!B_IS_IN_TREE2116 (bh = PATH_OFFSET_PBUFFER(path, path_offset - 1)))2117 return REPEAT_SEARCH;2118 2119 if ((position =2120 PATH_OFFSET_POSITION(path,2121 path_offset - 1)) > B_NR_ITEMS(bh))2122 return REPEAT_SEARCH;2123 2124 /* Parent in the path is not parent of the current node in the tree. */2125 if (B_N_CHILD_NUM(bh, position) !=2126 PATH_OFFSET_PBUFFER(path, path_offset)->b_blocknr)2127 return REPEAT_SEARCH;2128 2129 if (buffer_locked(bh)) {2130 int depth = reiserfs_write_unlock_nested(tb->tb_sb);2131 __wait_on_buffer(bh);2132 reiserfs_write_lock_nested(tb->tb_sb, depth);2133 if (FILESYSTEM_CHANGED_TB(tb))2134 return REPEAT_SEARCH;2135 }2136 2137 /*2138 * Parent in the path is unlocked and really parent2139 * of the current node.2140 */2141 return CARRY_ON;2142}2143 2144/*2145 * Using lnum[h] and rnum[h] we should determine what neighbors2146 * of S[h] we2147 * need in order to balance S[h], and get them if necessary.2148 * Returns: SCHEDULE_OCCURRED - schedule occurred while the function worked;2149 * CARRY_ON - schedule didn't occur while the function worked;2150 */2151static int get_neighbors(struct tree_balance *tb, int h)2152{2153 int child_position,2154 path_offset = PATH_H_PATH_OFFSET(tb->tb_path, h + 1);2155 unsigned long son_number;2156 struct super_block *sb = tb->tb_sb;2157 struct buffer_head *bh;2158 int depth;2159 2160 PROC_INFO_INC(sb, get_neighbors[h]);2161 2162 if (tb->lnum[h]) {2163 /* We need left neighbor to balance S[h]. */2164 PROC_INFO_INC(sb, need_l_neighbor[h]);2165 bh = PATH_OFFSET_PBUFFER(tb->tb_path, path_offset);2166 2167 RFALSE(bh == tb->FL[h] &&2168 !PATH_OFFSET_POSITION(tb->tb_path, path_offset),2169 "PAP-8270: invalid position in the parent");2170 2171 child_position =2172 (bh ==2173 tb->FL[h]) ? tb->lkey[h] : B_NR_ITEMS(tb->2174 FL[h]);2175 son_number = B_N_CHILD_NUM(tb->FL[h], child_position);2176 depth = reiserfs_write_unlock_nested(tb->tb_sb);2177 bh = sb_bread(sb, son_number);2178 reiserfs_write_lock_nested(tb->tb_sb, depth);2179 if (!bh)2180 return IO_ERROR;2181 if (FILESYSTEM_CHANGED_TB(tb)) {2182 brelse(bh);2183 PROC_INFO_INC(sb, get_neighbors_restart[h]);2184 return REPEAT_SEARCH;2185 }2186 2187 RFALSE(!B_IS_IN_TREE(tb->FL[h]) ||2188 child_position > B_NR_ITEMS(tb->FL[h]) ||2189 B_N_CHILD_NUM(tb->FL[h], child_position) !=2190 bh->b_blocknr, "PAP-8275: invalid parent");2191 RFALSE(!B_IS_IN_TREE(bh), "PAP-8280: invalid child");2192 RFALSE(!h &&2193 B_FREE_SPACE(bh) !=2194 MAX_CHILD_SIZE(bh) -2195 dc_size(B_N_CHILD(tb->FL[0], child_position)),2196 "PAP-8290: invalid child size of left neighbor");2197 2198 brelse(tb->L[h]);2199 tb->L[h] = bh;2200 }2201 2202 /* We need right neighbor to balance S[path_offset]. */2203 if (tb->rnum[h]) {2204 PROC_INFO_INC(sb, need_r_neighbor[h]);2205 bh = PATH_OFFSET_PBUFFER(tb->tb_path, path_offset);2206 2207 RFALSE(bh == tb->FR[h] &&2208 PATH_OFFSET_POSITION(tb->tb_path,2209 path_offset) >=2210 B_NR_ITEMS(bh),2211 "PAP-8295: invalid position in the parent");2212 2213 child_position =2214 (bh == tb->FR[h]) ? tb->rkey[h] + 1 : 0;2215 son_number = B_N_CHILD_NUM(tb->FR[h], child_position);2216 depth = reiserfs_write_unlock_nested(tb->tb_sb);2217 bh = sb_bread(sb, son_number);2218 reiserfs_write_lock_nested(tb->tb_sb, depth);2219 if (!bh)2220 return IO_ERROR;2221 if (FILESYSTEM_CHANGED_TB(tb)) {2222 brelse(bh);2223 PROC_INFO_INC(sb, get_neighbors_restart[h]);2224 return REPEAT_SEARCH;2225 }2226 brelse(tb->R[h]);2227 tb->R[h] = bh;2228 2229 RFALSE(!h2230 && B_FREE_SPACE(bh) !=2231 MAX_CHILD_SIZE(bh) -2232 dc_size(B_N_CHILD(tb->FR[0], child_position)),2233 "PAP-8300: invalid child size of right neighbor (%d != %d - %d)",2234 B_FREE_SPACE(bh), MAX_CHILD_SIZE(bh),2235 dc_size(B_N_CHILD(tb->FR[0], child_position)));2236 2237 }2238 return CARRY_ON;2239}2240 2241static int get_virtual_node_size(struct super_block *sb, struct buffer_head *bh)2242{2243 int max_num_of_items;2244 int max_num_of_entries;2245 unsigned long blocksize = sb->s_blocksize;2246 2247#define MIN_NAME_LEN 12248 2249 max_num_of_items = (blocksize - BLKH_SIZE) / (IH_SIZE + MIN_ITEM_LEN);2250 max_num_of_entries = (blocksize - BLKH_SIZE - IH_SIZE) /2251 (DEH_SIZE + MIN_NAME_LEN);2252 2253 return sizeof(struct virtual_node) +2254 max(max_num_of_items * sizeof(struct virtual_item),2255 sizeof(struct virtual_item) +2256 struct_size_t(struct direntry_uarea, entry_sizes,2257 max_num_of_entries));2258}2259 2260/*2261 * maybe we should fail balancing we are going to perform when kmalloc2262 * fails several times. But now it will loop until kmalloc gets2263 * required memory2264 */2265static int get_mem_for_virtual_node(struct tree_balance *tb)2266{2267 int check_fs = 0;2268 int size;2269 char *buf;2270 2271 size = get_virtual_node_size(tb->tb_sb, PATH_PLAST_BUFFER(tb->tb_path));2272 2273 /* we have to allocate more memory for virtual node */2274 if (size > tb->vn_buf_size) {2275 if (tb->vn_buf) {2276 /* free memory allocated before */2277 kfree(tb->vn_buf);2278 /* this is not needed if kfree is atomic */2279 check_fs = 1;2280 }2281 2282 /* virtual node requires now more memory */2283 tb->vn_buf_size = size;2284 2285 /* get memory for virtual item */2286 buf = kmalloc(size, GFP_ATOMIC | __GFP_NOWARN);2287 if (!buf) {2288 /*2289 * getting memory with GFP_KERNEL priority may involve2290 * balancing now (due to indirect_to_direct conversion2291 * on dcache shrinking). So, release path and collected2292 * resources here2293 */2294 free_buffers_in_tb(tb);2295 buf = kmalloc(size, GFP_NOFS);2296 if (!buf) {2297 tb->vn_buf_size = 0;2298 }2299 tb->vn_buf = buf;2300 schedule();2301 return REPEAT_SEARCH;2302 }2303 2304 tb->vn_buf = buf;2305 }2306 2307 if (check_fs && FILESYSTEM_CHANGED_TB(tb))2308 return REPEAT_SEARCH;2309 2310 return CARRY_ON;2311}2312 2313#ifdef CONFIG_REISERFS_CHECK2314static void tb_buffer_sanity_check(struct super_block *sb,2315 struct buffer_head *bh,2316 const char *descr, int level)2317{2318 if (bh) {2319 if (atomic_read(&(bh->b_count)) <= 0)2320 2321 reiserfs_panic(sb, "jmacd-1", "negative or zero "2322 "reference counter for buffer %s[%d] "2323 "(%b)", descr, level, bh);2324 2325 if (!buffer_uptodate(bh))2326 reiserfs_panic(sb, "jmacd-2", "buffer is not up "2327 "to date %s[%d] (%b)",2328 descr, level, bh);2329 2330 if (!B_IS_IN_TREE(bh))2331 reiserfs_panic(sb, "jmacd-3", "buffer is not "2332 "in tree %s[%d] (%b)",2333 descr, level, bh);2334 2335 if (bh->b_bdev != sb->s_bdev)2336 reiserfs_panic(sb, "jmacd-4", "buffer has wrong "2337 "device %s[%d] (%b)",2338 descr, level, bh);2339 2340 if (bh->b_size != sb->s_blocksize)2341 reiserfs_panic(sb, "jmacd-5", "buffer has wrong "2342 "blocksize %s[%d] (%b)",2343 descr, level, bh);2344 2345 if (bh->b_blocknr > SB_BLOCK_COUNT(sb))2346 reiserfs_panic(sb, "jmacd-6", "buffer block "2347 "number too high %s[%d] (%b)",2348 descr, level, bh);2349 }2350}2351#else2352static void tb_buffer_sanity_check(struct super_block *sb,2353 struct buffer_head *bh,2354 const char *descr, int level)2355{;2356}2357#endif2358 2359static int clear_all_dirty_bits(struct super_block *s, struct buffer_head *bh)2360{2361 return reiserfs_prepare_for_journal(s, bh, 0);2362}2363 2364static int wait_tb_buffers_until_unlocked(struct tree_balance *tb)2365{2366 struct buffer_head *locked;2367#ifdef CONFIG_REISERFS_CHECK2368 int repeat_counter = 0;2369#endif2370 int i;2371 2372 do {2373 2374 locked = NULL;2375 2376 for (i = tb->tb_path->path_length;2377 !locked && i > ILLEGAL_PATH_ELEMENT_OFFSET; i--) {2378 if (PATH_OFFSET_PBUFFER(tb->tb_path, i)) {2379 /*2380 * if I understand correctly, we can only2381 * be sure the last buffer in the path is2382 * in the tree --clm2383 */2384#ifdef CONFIG_REISERFS_CHECK2385 if (PATH_PLAST_BUFFER(tb->tb_path) ==2386 PATH_OFFSET_PBUFFER(tb->tb_path, i))2387 tb_buffer_sanity_check(tb->tb_sb,2388 PATH_OFFSET_PBUFFER2389 (tb->tb_path,2390 i), "S",2391 tb->tb_path->2392 path_length - i);2393#endif2394 if (!clear_all_dirty_bits(tb->tb_sb,2395 PATH_OFFSET_PBUFFER2396 (tb->tb_path,2397 i))) {2398 locked =2399 PATH_OFFSET_PBUFFER(tb->tb_path,2400 i);2401 }2402 }2403 }2404 2405 for (i = 0; !locked && i < MAX_HEIGHT && tb->insert_size[i];2406 i++) {2407 2408 if (tb->lnum[i]) {2409 2410 if (tb->L[i]) {2411 tb_buffer_sanity_check(tb->tb_sb,2412 tb->L[i],2413 "L", i);2414 if (!clear_all_dirty_bits2415 (tb->tb_sb, tb->L[i]))2416 locked = tb->L[i];2417 }2418 2419 if (!locked && tb->FL[i]) {2420 tb_buffer_sanity_check(tb->tb_sb,2421 tb->FL[i],2422 "FL", i);2423 if (!clear_all_dirty_bits2424 (tb->tb_sb, tb->FL[i]))2425 locked = tb->FL[i];2426 }2427 2428 if (!locked && tb->CFL[i]) {2429 tb_buffer_sanity_check(tb->tb_sb,2430 tb->CFL[i],2431 "CFL", i);2432 if (!clear_all_dirty_bits2433 (tb->tb_sb, tb->CFL[i]))2434 locked = tb->CFL[i];2435 }2436 2437 }2438 2439 if (!locked && (tb->rnum[i])) {2440 2441 if (tb->R[i]) {2442 tb_buffer_sanity_check(tb->tb_sb,2443 tb->R[i],2444 "R", i);2445 if (!clear_all_dirty_bits2446 (tb->tb_sb, tb->R[i]))2447 locked = tb->R[i];2448 }2449 2450 if (!locked && tb->FR[i]) {2451 tb_buffer_sanity_check(tb->tb_sb,2452 tb->FR[i],2453 "FR", i);2454 if (!clear_all_dirty_bits2455 (tb->tb_sb, tb->FR[i]))2456 locked = tb->FR[i];2457 }2458 2459 if (!locked && tb->CFR[i]) {2460 tb_buffer_sanity_check(tb->tb_sb,2461 tb->CFR[i],2462 "CFR", i);2463 if (!clear_all_dirty_bits2464 (tb->tb_sb, tb->CFR[i]))2465 locked = tb->CFR[i];2466 }2467 }2468 }2469 2470 /*2471 * as far as I can tell, this is not required. The FEB list2472 * seems to be full of newly allocated nodes, which will2473 * never be locked, dirty, or anything else.2474 * To be safe, I'm putting in the checks and waits in.2475 * For the moment, they are needed to keep the code in2476 * journal.c from complaining about the buffer.2477 * That code is inside CONFIG_REISERFS_CHECK as well. --clm2478 */2479 for (i = 0; !locked && i < MAX_FEB_SIZE; i++) {2480 if (tb->FEB[i]) {2481 if (!clear_all_dirty_bits2482 (tb->tb_sb, tb->FEB[i]))2483 locked = tb->FEB[i];2484 }2485 }2486 2487 if (locked) {2488 int depth;2489#ifdef CONFIG_REISERFS_CHECK2490 repeat_counter++;2491 if ((repeat_counter % 10000) == 0) {2492 reiserfs_warning(tb->tb_sb, "reiserfs-8200",2493 "too many iterations waiting "2494 "for buffer to unlock "2495 "(%b)", locked);2496 2497 /* Don't loop forever. Try to recover from possible error. */2498 2499 return (FILESYSTEM_CHANGED_TB(tb)) ?2500 REPEAT_SEARCH : CARRY_ON;2501 }2502#endif2503 depth = reiserfs_write_unlock_nested(tb->tb_sb);2504 __wait_on_buffer(locked);2505 reiserfs_write_lock_nested(tb->tb_sb, depth);2506 if (FILESYSTEM_CHANGED_TB(tb))2507 return REPEAT_SEARCH;2508 }2509 2510 } while (locked);2511 2512 return CARRY_ON;2513}2514 2515/*2516 * Prepare for balancing, that is2517 * get all necessary parents, and neighbors;2518 * analyze what and where should be moved;2519 * get sufficient number of new nodes;2520 * Balancing will start only after all resources will be collected at a time.2521 *2522 * When ported to SMP kernels, only at the last moment after all needed nodes2523 * are collected in cache, will the resources be locked using the usual2524 * textbook ordered lock acquisition algorithms. Note that ensuring that2525 * this code neither write locks what it does not need to write lock nor locks2526 * out of order will be a pain in the butt that could have been avoided.2527 * Grumble grumble. -Hans2528 *2529 * fix is meant in the sense of render unchanging2530 *2531 * Latency might be improved by first gathering a list of what buffers2532 * are needed and then getting as many of them in parallel as possible? -Hans2533 *2534 * Parameters:2535 * op_mode i - insert, d - delete, c - cut (truncate), p - paste (append)2536 * tb tree_balance structure;2537 * inum item number in S[h];2538 * pos_in_item - comment this if you can2539 * ins_ih item head of item being inserted2540 * data inserted item or data to be pasted2541 * Returns: 1 - schedule occurred while the function worked;2542 * 0 - schedule didn't occur while the function worked;2543 * -1 - if no_disk_space2544 */2545 2546int fix_nodes(int op_mode, struct tree_balance *tb,2547 struct item_head *ins_ih, const void *data)2548{2549 int ret, h, item_num = PATH_LAST_POSITION(tb->tb_path);2550 int pos_in_item;2551 2552 /*2553 * we set wait_tb_buffers_run when we have to restore any dirty2554 * bits cleared during wait_tb_buffers_run2555 */2556 int wait_tb_buffers_run = 0;2557 struct buffer_head *tbS0 = PATH_PLAST_BUFFER(tb->tb_path);2558 2559 ++REISERFS_SB(tb->tb_sb)->s_fix_nodes;2560 2561 pos_in_item = tb->tb_path->pos_in_item;2562 2563 tb->fs_gen = get_generation(tb->tb_sb);2564 2565 /*2566 * we prepare and log the super here so it will already be in the2567 * transaction when do_balance needs to change it.2568 * This way do_balance won't have to schedule when trying to prepare2569 * the super for logging2570 */2571 reiserfs_prepare_for_journal(tb->tb_sb,2572 SB_BUFFER_WITH_SB(tb->tb_sb), 1);2573 journal_mark_dirty(tb->transaction_handle,2574 SB_BUFFER_WITH_SB(tb->tb_sb));2575 if (FILESYSTEM_CHANGED_TB(tb))2576 return REPEAT_SEARCH;2577 2578 /* if it possible in indirect_to_direct conversion */2579 if (buffer_locked(tbS0)) {2580 int depth = reiserfs_write_unlock_nested(tb->tb_sb);2581 __wait_on_buffer(tbS0);2582 reiserfs_write_lock_nested(tb->tb_sb, depth);2583 if (FILESYSTEM_CHANGED_TB(tb))2584 return REPEAT_SEARCH;2585 }2586#ifdef CONFIG_REISERFS_CHECK2587 if (REISERFS_SB(tb->tb_sb)->cur_tb) {2588 print_cur_tb("fix_nodes");2589 reiserfs_panic(tb->tb_sb, "PAP-8305",2590 "there is pending do_balance");2591 }2592 2593 if (!buffer_uptodate(tbS0) || !B_IS_IN_TREE(tbS0))2594 reiserfs_panic(tb->tb_sb, "PAP-8320", "S[0] (%b %z) is "2595 "not uptodate at the beginning of fix_nodes "2596 "or not in tree (mode %c)",2597 tbS0, tbS0, op_mode);2598 2599 /* Check parameters. */2600 switch (op_mode) {2601 case M_INSERT:2602 if (item_num <= 0 || item_num > B_NR_ITEMS(tbS0))2603 reiserfs_panic(tb->tb_sb, "PAP-8330", "Incorrect "2604 "item number %d (in S0 - %d) in case "2605 "of insert", item_num,2606 B_NR_ITEMS(tbS0));2607 break;2608 case M_PASTE:2609 case M_DELETE:2610 case M_CUT:2611 if (item_num < 0 || item_num >= B_NR_ITEMS(tbS0)) {2612 print_block(tbS0, 0, -1, -1);2613 reiserfs_panic(tb->tb_sb, "PAP-8335", "Incorrect "2614 "item number(%d); mode = %c "2615 "insert_size = %d",2616 item_num, op_mode,2617 tb->insert_size[0]);2618 }2619 break;2620 default:2621 reiserfs_panic(tb->tb_sb, "PAP-8340", "Incorrect mode "2622 "of operation");2623 }2624#endif2625 2626 if (get_mem_for_virtual_node(tb) == REPEAT_SEARCH)2627 /* FIXME: maybe -ENOMEM when tb->vn_buf == 0? Now just repeat */2628 return REPEAT_SEARCH;2629 2630 /* Starting from the leaf level; for all levels h of the tree. */2631 for (h = 0; h < MAX_HEIGHT && tb->insert_size[h]; h++) {2632 ret = get_direct_parent(tb, h);2633 if (ret != CARRY_ON)2634 goto repeat;2635 2636 ret = check_balance(op_mode, tb, h, item_num,2637 pos_in_item, ins_ih, data);2638 if (ret != CARRY_ON) {2639 if (ret == NO_BALANCING_NEEDED) {2640 /* No balancing for higher levels needed. */2641 ret = get_neighbors(tb, h);2642 if (ret != CARRY_ON)2643 goto repeat;2644 if (h != MAX_HEIGHT - 1)2645 tb->insert_size[h + 1] = 0;2646 /*2647 * ok, analysis and resource gathering2648 * are complete2649 */2650 break;2651 }2652 goto repeat;2653 }2654 2655 ret = get_neighbors(tb, h);2656 if (ret != CARRY_ON)2657 goto repeat;2658 2659 /*2660 * No disk space, or schedule occurred and analysis may be2661 * invalid and needs to be redone.2662 */2663 ret = get_empty_nodes(tb, h);2664 if (ret != CARRY_ON)2665 goto repeat;2666 2667 /*2668 * We have a positive insert size but no nodes exist on this2669 * level, this means that we are creating a new root.2670 */2671 if (!PATH_H_PBUFFER(tb->tb_path, h)) {2672 2673 RFALSE(tb->blknum[h] != 1,2674 "PAP-8350: creating new empty root");2675 2676 if (h < MAX_HEIGHT - 1)2677 tb->insert_size[h + 1] = 0;2678 } else if (!PATH_H_PBUFFER(tb->tb_path, h + 1)) {2679 /*2680 * The tree needs to be grown, so this node S[h]2681 * which is the root node is split into two nodes,2682 * and a new node (S[h+1]) will be created to2683 * become the root node.2684 */2685 if (tb->blknum[h] > 1) {2686 2687 RFALSE(h == MAX_HEIGHT - 1,2688 "PAP-8355: attempt to create too high of a tree");2689 2690 tb->insert_size[h + 1] =2691 (DC_SIZE +2692 KEY_SIZE) * (tb->blknum[h] - 1) +2693 DC_SIZE;2694 } else if (h < MAX_HEIGHT - 1)2695 tb->insert_size[h + 1] = 0;2696 } else2697 tb->insert_size[h + 1] =2698 (DC_SIZE + KEY_SIZE) * (tb->blknum[h] - 1);2699 }2700 2701 ret = wait_tb_buffers_until_unlocked(tb);2702 if (ret == CARRY_ON) {2703 if (FILESYSTEM_CHANGED_TB(tb)) {2704 wait_tb_buffers_run = 1;2705 ret = REPEAT_SEARCH;2706 goto repeat;2707 } else {2708 return CARRY_ON;2709 }2710 } else {2711 wait_tb_buffers_run = 1;2712 goto repeat;2713 }2714 2715repeat:2716 /*2717 * fix_nodes was unable to perform its calculation due to2718 * filesystem got changed under us, lack of free disk space or i/o2719 * failure. If the first is the case - the search will be2720 * repeated. For now - free all resources acquired so far except2721 * for the new allocated nodes2722 */2723 {2724 int i;2725 2726 /* Release path buffers. */2727 if (wait_tb_buffers_run) {2728 pathrelse_and_restore(tb->tb_sb, tb->tb_path);2729 } else {2730 pathrelse(tb->tb_path);2731 }2732 /* brelse all resources collected for balancing */2733 for (i = 0; i < MAX_HEIGHT; i++) {2734 if (wait_tb_buffers_run) {2735 reiserfs_restore_prepared_buffer(tb->tb_sb,2736 tb->L[i]);2737 reiserfs_restore_prepared_buffer(tb->tb_sb,2738 tb->R[i]);2739 reiserfs_restore_prepared_buffer(tb->tb_sb,2740 tb->FL[i]);2741 reiserfs_restore_prepared_buffer(tb->tb_sb,2742 tb->FR[i]);2743 reiserfs_restore_prepared_buffer(tb->tb_sb,2744 tb->2745 CFL[i]);2746 reiserfs_restore_prepared_buffer(tb->tb_sb,2747 tb->2748 CFR[i]);2749 }2750 2751 brelse(tb->L[i]);2752 brelse(tb->R[i]);2753 brelse(tb->FL[i]);2754 brelse(tb->FR[i]);2755 brelse(tb->CFL[i]);2756 brelse(tb->CFR[i]);2757 2758 tb->L[i] = NULL;2759 tb->R[i] = NULL;2760 tb->FL[i] = NULL;2761 tb->FR[i] = NULL;2762 tb->CFL[i] = NULL;2763 tb->CFR[i] = NULL;2764 }2765 2766 if (wait_tb_buffers_run) {2767 for (i = 0; i < MAX_FEB_SIZE; i++) {2768 if (tb->FEB[i])2769 reiserfs_restore_prepared_buffer2770 (tb->tb_sb, tb->FEB[i]);2771 }2772 }2773 return ret;2774 }2775 2776}2777 2778void unfix_nodes(struct tree_balance *tb)2779{2780 int i;2781 2782 /* Release path buffers. */2783 pathrelse_and_restore(tb->tb_sb, tb->tb_path);2784 2785 /* brelse all resources collected for balancing */2786 for (i = 0; i < MAX_HEIGHT; i++) {2787 reiserfs_restore_prepared_buffer(tb->tb_sb, tb->L[i]);2788 reiserfs_restore_prepared_buffer(tb->tb_sb, tb->R[i]);2789 reiserfs_restore_prepared_buffer(tb->tb_sb, tb->FL[i]);2790 reiserfs_restore_prepared_buffer(tb->tb_sb, tb->FR[i]);2791 reiserfs_restore_prepared_buffer(tb->tb_sb, tb->CFL[i]);2792 reiserfs_restore_prepared_buffer(tb->tb_sb, tb->CFR[i]);2793 2794 brelse(tb->L[i]);2795 brelse(tb->R[i]);2796 brelse(tb->FL[i]);2797 brelse(tb->FR[i]);2798 brelse(tb->CFL[i]);2799 brelse(tb->CFR[i]);2800 }2801 2802 /* deal with list of allocated (used and unused) nodes */2803 for (i = 0; i < MAX_FEB_SIZE; i++) {2804 if (tb->FEB[i]) {2805 b_blocknr_t blocknr = tb->FEB[i]->b_blocknr;2806 /*2807 * de-allocated block which was not used by2808 * balancing and bforget about buffer for it2809 */2810 brelse(tb->FEB[i]);2811 reiserfs_free_block(tb->transaction_handle, NULL,2812 blocknr, 0);2813 }2814 if (tb->used[i]) {2815 /* release used as new nodes including a new root */2816 brelse(tb->used[i]);2817 }2818 }2819 2820 kfree(tb->vn_buf);2821 2822}2823