2 * Copyright 2000 by Hans Reiser, licensing governed by reiserfs/README
5 #include <linux/time.h>
6 #include <linux/slab.h>
7 #include <linux/string.h>
9 #include <linux/buffer_head.h>
12 * To make any changes in the tree we find a node that contains item
13 * to be changed/deleted or position in the node we insert a new item
14 * to. We call this node S. To do balancing we need to decide what we
15 * will shift to left/right neighbor, or to a new node, where new item
16 * will be etc. To make this analysis simpler we build virtual
17 * node. Virtual node is an array of items, that will replace items of
18 * node S. (For instance if we are going to delete an item, virtual
19 * node does not contain it). Virtual node keeps information about
20 * item sizes and types, mergeability of first and last items, sizes
21 * of all entries in directory item. We use this array of items when
22 * calculating what we can shift to neighbors and how many nodes we
23 * have to have if we do not any shiftings, if we shift to left/right
24 * neighbor or to both.
28 * Takes item number in virtual node, returns number of item
29 * that it has in source buffer
31 static inline int old_item_num(int new_num, int affected_item_num, int mode)
33 if (mode == M_PASTE || mode == M_CUT || new_num < affected_item_num)
36 if (mode == M_INSERT) {
39 "vs-8005: for INSERT mode and item number of inserted item");
44 RFALSE(mode != M_DELETE,
45 "vs-8010: old_item_num: mode must be M_DELETE (mode = \'%c\'",
51 static void create_virtual_node(struct tree_balance *tb, int h)
54 struct virtual_node *vn = tb->tb_vn;
56 struct buffer_head *Sh; /* this comes from tb->S[h] */
58 Sh = PATH_H_PBUFFER(tb->tb_path, h);
60 /* size of changed node */
62 MAX_CHILD_SIZE(Sh) - B_FREE_SPACE(Sh) + tb->insert_size[h];
64 /* for internal nodes array if virtual items is not created */
66 vn->vn_nr_item = (vn->vn_size - DC_SIZE) / (DC_SIZE + KEY_SIZE);
70 /* number of items in virtual node */
72 B_NR_ITEMS(Sh) + ((vn->vn_mode == M_INSERT) ? 1 : 0) -
73 ((vn->vn_mode == M_DELETE) ? 1 : 0);
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);
80 /* first item in the node */
81 ih = item_head(Sh, 0);
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;
89 * go through all items that remain in the virtual
90 * node (except for the new (inserted) one)
92 for (new_num = 0; new_num < vn->vn_nr_item; new_num++) {
94 struct virtual_item *vi = vn->vn_vi + new_num;
96 ((new_num != vn->vn_affected_item_num) ? 0 : 1);
98 if (is_affected && vn->vn_mode == M_INSERT)
101 /* get item number in source node */
102 j = old_item_num(new_num, vn->vn_affected_item_num,
105 vi->vi_item_len += ih_item_len(ih + j) + IH_SIZE;
107 vi->vi_item = ih_item_body(Sh, ih + j);
108 vi->vi_uarea = vn->vn_free_ptr;
111 * FIXME: there is no check that item operation did not
112 * consume too much memory
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");
121 /* this is not being changed */
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;
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;
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;
142 op_create_vi(vn, vi, 0 /*not pasted or cut */ ,
147 * set right merge flag we take right delimiting key and
148 * check whether it is a mergeable item
151 struct reiserfs_key *key;
153 key = internal_key(tb->CFR[0], tb->rkey[0]);
154 if (op_is_left_mergeable(key, Sh->b_size)
155 && (vn->vn_mode != M_DELETE
156 || vn->vn_affected_item_num != B_NR_ITEMS(Sh) - 1))
157 vn->vn_vi[vn->vn_nr_item - 1].vi_type |=
158 VI_TYPE_RIGHT_MERGEABLE;
160 #ifdef CONFIG_REISERFS_CHECK
161 if (op_is_left_mergeable(key, Sh->b_size) &&
162 !(vn->vn_mode != M_DELETE
163 || vn->vn_affected_item_num != B_NR_ITEMS(Sh) - 1)) {
165 * we delete last item and it could be merged
166 * with right neighbor's first item
170 && is_direntry_le_ih(item_head(Sh, 0))
171 && ih_entry_count(item_head(Sh, 0)) == 1)) {
173 * node contains more than 1 item, or item
174 * is not directory item, or this item
175 * contains more than 1 entry
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);
191 * Using virtual node check, how many items can be
192 * shifted to left neighbor
194 static void check_left(struct tree_balance *tb, int h, int cur_free)
197 struct virtual_node *vn = tb->tb_vn;
198 struct virtual_item *vi;
201 RFALSE(cur_free < 0, "vs-8050: cur_free (%d) < 0", cur_free);
205 tb->lnum[h] = cur_free / (DC_SIZE + KEY_SIZE);
211 if (!cur_free || !vn->vn_nr_item) {
212 /* no free space or nothing to move */
218 RFALSE(!PATH_H_PPARENT(tb->tb_path, 0),
219 "vs-8055: parent does not exist or invalid");
222 if ((unsigned int)cur_free >=
224 ((vi->vi_type & VI_TYPE_LEFT_MERGEABLE) ? IH_SIZE : 0))) {
225 /* all contents of S[0] fits into L[0] */
227 RFALSE(vn->vn_mode == M_INSERT || vn->vn_mode == M_PASTE,
228 "vs-8055: invalid mode or balance condition failed");
230 tb->lnum[0] = vn->vn_nr_item;
235 d_size = 0, ih_size = IH_SIZE;
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;
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 */
252 /* the item cannot be shifted entirely, try to split it */
254 * check whether L[0] can hold ih and at least one byte
258 /* cannot shift even a part of the current item */
259 if (cur_free <= ih_size) {
265 tb->lbytes = op_check_left(vi, cur_free, 0, 0);
266 if (tb->lbytes != -1)
267 /* count partially shifted item */
277 * Using virtual node check, how many items can be
278 * shifted to right neighbor
280 static void check_right(struct tree_balance *tb, int h, int cur_free)
283 struct virtual_node *vn = tb->tb_vn;
284 struct virtual_item *vi;
287 RFALSE(cur_free < 0, "vs-8070: cur_free < 0");
291 tb->rnum[h] = cur_free / (DC_SIZE + KEY_SIZE);
297 if (!cur_free || !vn->vn_nr_item) {
304 RFALSE(!PATH_H_PPARENT(tb->tb_path, 0),
305 "vs-8075: parent does not exist or invalid");
307 vi = vn->vn_vi + vn->vn_nr_item - 1;
308 if ((unsigned int)cur_free >=
310 ((vi->vi_type & VI_TYPE_RIGHT_MERGEABLE) ? IH_SIZE : 0))) {
311 /* all contents of S[0] fits into R[0] */
313 RFALSE(vn->vn_mode == M_INSERT || vn->vn_mode == M_PASTE,
314 "vs-8080: invalid mode or balance condition failed");
316 tb->rnum[h] = vn->vn_nr_item;
321 d_size = 0, ih_size = IH_SIZE;
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;
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 */
339 * check whether R[0] can hold ih and at least one
340 * byte of the item body
343 /* cannot shift even a part of the current item */
344 if (cur_free <= ih_size) {
350 * R[0] can hold the header of the item and at least
351 * one byte of its body
353 cur_free -= ih_size; /* cur_free is still > 0 */
355 tb->rbytes = op_check_right(vi, cur_free);
356 if (tb->rbytes != -1)
357 /* count partially shifted item */
367 * from - number of items, which are shifted to left neighbor entirely
368 * to - number of item, which are shifted to right neighbor entirely
369 * from_bytes - number of bytes of boundary item (or directory entries)
370 * which are shifted to left neighbor
371 * to_bytes - number of bytes of boundary item (or directory entries)
372 * which are shifted to right neighbor
374 static int get_num_ver(int mode, struct tree_balance *tb, int h,
375 int from, int from_bytes,
376 int to, int to_bytes, short *snum012, int flow)
381 struct virtual_node *vn = tb->tb_vn;
382 int total_node_size, max_node_size, current_item_size;
385 /* position of item we start filling node from */
388 /* position of item we finish filling node by */
392 * number of first bytes (entries for directory) of start_item-th item
393 * we do not include into node that is being filled
398 * number of last bytes (entries for directory) of end_item-th item
399 * we do node include into node that is being filled
404 * these are positions in virtual item of items, that are split
405 * between S[0] and S1new and S1new and S2new
407 int split_item_positions[2];
409 split_item_positions[0] = -1;
410 split_item_positions[1] = -1;
413 * We only create additional nodes if we are in insert or paste mode
414 * or we are in replace mode at the internal level. If h is 0 and
415 * the mode is M_REPLACE then in fix_nodes we change the mode to
416 * paste or insert before we get here in the code.
418 RFALSE(tb->insert_size[h] < 0 || (mode != M_INSERT && mode != M_PASTE),
419 "vs-8100: insert_size < 0 in overflow");
421 max_node_size = MAX_CHILD_SIZE(PATH_H_PBUFFER(tb->tb_path, h));
424 * snum012 [0-2] - number of items, that lay
425 * to S[0], first new node and second new node
427 snum012[3] = -1; /* s1bytes */
428 snum012[4] = -1; /* s2bytes */
432 i = ((to - from) * (KEY_SIZE + DC_SIZE) + DC_SIZE);
433 if (i == max_node_size)
435 return (i / max_node_size + 1);
441 cur_free = max_node_size;
443 /* start from 'from'-th item */
445 /* skip its first 'start_bytes' units */
446 start_bytes = ((from_bytes != -1) ? from_bytes : 0);
448 /* last included item is the 'end_item'-th one */
449 end_item = vn->vn_nr_item - to - 1;
450 /* do not count last 'end_bytes' units of 'end_item'-th item */
451 end_bytes = (to_bytes != -1) ? to_bytes : 0;
454 * go through all item beginning from the start_item-th item
455 * and ending by the end_item-th item. Do not count first
456 * 'start_bytes' units of 'start_item'-th item and last
457 * 'end_bytes' of 'end_item'-th item
459 for (i = start_item; i <= end_item; i++) {
460 struct virtual_item *vi = vn->vn_vi + i;
461 int skip_from_end = ((i == end_item) ? end_bytes : 0);
463 RFALSE(needed_nodes > 3, "vs-8105: too many nodes are needed");
465 /* get size of current item */
466 current_item_size = vi->vi_item_len;
469 * do not take in calculation head part (from_bytes)
473 op_part_size(vi, 0 /*from start */ , start_bytes);
475 /* do not take in calculation tail part of last item */
477 op_part_size(vi, 1 /*from end */ , skip_from_end);
479 /* if item fits into current node entierly */
480 if (total_node_size + current_item_size <= max_node_size) {
481 snum012[needed_nodes - 1]++;
482 total_node_size += current_item_size;
488 * virtual item length is longer, than max size of item in
489 * a node. It is impossible for direct item
491 if (current_item_size > max_node_size) {
492 RFALSE(is_direct_le_ih(vi->vi_ih),
494 "direct item length is %d. It can not be longer than %d",
495 current_item_size, max_node_size);
496 /* we will try to split it */
500 /* as we do not split items, take new node and continue */
509 * calculate number of item units which fit into node being
515 free_space = max_node_size - total_node_size - IH_SIZE;
517 op_check_left(vi, free_space, start_bytes,
520 * nothing fits into current node, take new
524 needed_nodes++, i--, total_node_size = 0;
529 /* something fits into the current node */
530 start_bytes += units;
531 snum012[needed_nodes - 1 + 3] = units;
533 if (needed_nodes > 2)
534 reiserfs_warning(tb->tb_sb, "vs-8111",
535 "split_item_position is out of range");
536 snum012[needed_nodes - 1]++;
537 split_item_positions[needed_nodes - 1] = i;
539 /* continue from the same item with start_bytes != -1 */
546 * sum012[4] (if it is not -1) contains number of units of which
547 * are to be in S1new, snum012[3] - to be in S0. They are supposed
548 * to be S1bytes and S2bytes correspondingly, so recalculate
550 if (snum012[4] > 0) {
552 int bytes_to_r, bytes_to_l;
555 split_item_num = split_item_positions[1];
557 ((from == split_item_num
558 && from_bytes != -1) ? from_bytes : 0);
560 ((end_item == split_item_num
561 && end_bytes != -1) ? end_bytes : 0);
563 ((split_item_positions[0] ==
564 split_item_positions[1]) ? snum012[3] : 0);
568 op_unit_num(&vn->vn_vi[split_item_num]) - snum012[4] -
569 bytes_to_r - bytes_to_l - bytes_to_S1new;
571 if (vn->vn_vi[split_item_num].vi_index != TYPE_DIRENTRY &&
572 vn->vn_vi[split_item_num].vi_index != TYPE_INDIRECT)
573 reiserfs_warning(tb->tb_sb, "vs-8115",
574 "not directory or indirect item");
577 /* now we know S2bytes, calculate S1bytes */
578 if (snum012[3] > 0) {
580 int bytes_to_r, bytes_to_l;
583 split_item_num = split_item_positions[0];
585 ((from == split_item_num
586 && from_bytes != -1) ? from_bytes : 0);
588 ((end_item == split_item_num
589 && end_bytes != -1) ? end_bytes : 0);
591 ((split_item_positions[0] == split_item_positions[1]
592 && snum012[4] != -1) ? snum012[4] : 0);
596 op_unit_num(&vn->vn_vi[split_item_num]) - snum012[3] -
597 bytes_to_r - bytes_to_l - bytes_to_S2new;
605 * Set parameters for balancing.
606 * Performs write of results of analysis of balancing into structure tb,
607 * where it will later be used by the functions that actually do the balancing.
609 * tb tree_balance structure;
610 * h current level of the node;
611 * lnum number of items from S[h] that must be shifted to L[h];
612 * rnum number of items from S[h] that must be shifted to R[h];
613 * blk_num number of blocks that S[h] will be splitted into;
614 * s012 number of items that fall into splitted nodes.
615 * lbytes number of bytes which flow to the left neighbor from the
616 * item that is not not shifted entirely
617 * rbytes number of bytes which flow to the right neighbor from the
618 * item that is not not shifted entirely
619 * s1bytes number of bytes which flow to the first new node when
620 * S[0] splits (this number is contained in s012 array)
623 static void set_parameters(struct tree_balance *tb, int h, int lnum,
624 int rnum, int blk_num, short *s012, int lb, int rb)
629 tb->blknum[h] = blk_num;
631 /* only for leaf level */
635 tb->s1num = *s012++, tb->s2num = *s012++;
636 tb->s1bytes = *s012++;
642 PROC_INFO_ADD(tb->tb_sb, lnum[h], lnum);
643 PROC_INFO_ADD(tb->tb_sb, rnum[h], rnum);
645 PROC_INFO_ADD(tb->tb_sb, lbytes[h], lb);
646 PROC_INFO_ADD(tb->tb_sb, rbytes[h], rb);
650 * check if node disappears if we shift tb->lnum[0] items to left
651 * neighbor and tb->rnum[0] to the right one.
653 static int is_leaf_removable(struct tree_balance *tb)
655 struct virtual_node *vn = tb->tb_vn;
656 int to_left, to_right;
661 * number of items that will be shifted to left (right) neighbor
664 to_left = tb->lnum[0] - ((tb->lbytes != -1) ? 1 : 0);
665 to_right = tb->rnum[0] - ((tb->rbytes != -1) ? 1 : 0);
666 remain_items = vn->vn_nr_item;
668 /* how many items remain in S[0] after shiftings to neighbors */
669 remain_items -= (to_left + to_right);
671 /* all content of node can be shifted to neighbors */
672 if (remain_items < 1) {
673 set_parameters(tb, 0, to_left, vn->vn_nr_item - to_left, 0,
678 /* S[0] is not removable */
679 if (remain_items > 1 || tb->lbytes == -1 || tb->rbytes == -1)
682 /* check whether we can divide 1 remaining item between neighbors */
684 /* get size of remaining item (in item units) */
685 size = op_unit_num(&(vn->vn_vi[to_left]));
687 if (tb->lbytes + tb->rbytes >= size) {
688 set_parameters(tb, 0, to_left + 1, to_right + 1, 0, NULL,
696 /* check whether L, S, R can be joined in one node */
697 static int are_leaves_removable(struct tree_balance *tb, int lfree, int rfree)
699 struct virtual_node *vn = tb->tb_vn;
701 struct buffer_head *S0;
703 S0 = PATH_H_PBUFFER(tb->tb_path, 0);
706 if (vn->vn_nr_item) {
707 if (vn->vn_vi[0].vi_type & VI_TYPE_LEFT_MERGEABLE)
710 if (vn->vn_vi[vn->vn_nr_item - 1].
711 vi_type & VI_TYPE_RIGHT_MERGEABLE)
714 /* there was only one item and it will be deleted */
715 struct item_head *ih;
717 RFALSE(B_NR_ITEMS(S0) != 1,
718 "vs-8125: item number must be 1: it is %d",
721 ih = item_head(S0, 0);
723 && !comp_short_le_keys(&(ih->ih_key),
724 internal_key(tb->CFR[0],
727 * Directory must be in correct state here: that is
728 * somewhere at the left side should exist first
729 * directory item. But the item being deleted can
730 * not be that first one because its right neighbor
731 * is item of the same directory. (But first item
732 * always gets deleted in last turn). So, neighbors
733 * of deleted item can be merged, so we can save
736 if (is_direntry_le_ih(ih)) {
740 * we might check that left neighbor exists
741 * and is of the same directory
743 RFALSE(le_ih_k_offset(ih) == DOT_OFFSET,
744 "vs-8130: first directory item can not be removed until directory is not empty");
749 if (MAX_CHILD_SIZE(S0) + vn->vn_size <= rfree + lfree + ih_size) {
750 set_parameters(tb, 0, -1, -1, -1, NULL, -1, -1);
751 PROC_INFO_INC(tb->tb_sb, leaves_removable);
758 /* when we do not split item, lnum and rnum are numbers of entire items */
759 #define SET_PAR_SHIFT_LEFT \
764 to_l = (MAX_NR_KEY(Sh)+1 - lpar + vn->vn_nr_item + 1) / 2 -\
765 (MAX_NR_KEY(Sh) + 1 - lpar);\
767 set_parameters (tb, h, to_l, 0, lnver, NULL, -1, -1);\
771 if (lset==LEFT_SHIFT_FLOW)\
772 set_parameters (tb, h, lpar, 0, lnver, snum012+lset,\
775 set_parameters (tb, h, lpar - (tb->lbytes!=-1), 0, lnver, snum012+lset,\
779 #define SET_PAR_SHIFT_RIGHT \
784 to_r = (MAX_NR_KEY(Sh)+1 - rpar + vn->vn_nr_item + 1) / 2 - (MAX_NR_KEY(Sh) + 1 - rpar);\
786 set_parameters (tb, h, 0, to_r, rnver, NULL, -1, -1);\
790 if (rset==RIGHT_SHIFT_FLOW)\
791 set_parameters (tb, h, 0, rpar, rnver, snum012+rset,\
794 set_parameters (tb, h, 0, rpar - (tb->rbytes!=-1), rnver, snum012+rset,\
798 static void free_buffers_in_tb(struct tree_balance *tb)
802 pathrelse(tb->tb_path);
804 for (i = 0; i < MAX_HEIGHT; i++) {
822 * Get new buffers for storing new nodes that are created while balancing.
823 * Returns: SCHEDULE_OCCURRED - schedule occurred while the function worked;
824 * CARRY_ON - schedule didn't occur while the function worked;
825 * NO_DISK_SPACE - no disk space.
827 /* The function is NOT SCHEDULE-SAFE! */
828 static int get_empty_nodes(struct tree_balance *tb, int h)
830 struct buffer_head *new_bh, *Sh = PATH_H_PBUFFER(tb->tb_path, h);
831 b_blocknr_t *blocknr, blocknrs[MAX_AMOUNT_NEEDED] = { 0, };
832 int counter, number_of_freeblk;
833 int amount_needed; /* number of needed empty blocks */
834 int retval = CARRY_ON;
835 struct super_block *sb = tb->tb_sb;
838 * number_of_freeblk is the number of empty blocks which have been
839 * acquired for use by the balancing algorithm minus the number of
840 * empty blocks used in the previous levels of the analysis,
841 * number_of_freeblk = tb->cur_blknum can be non-zero if a schedule
842 * occurs after empty blocks are acquired, and the balancing analysis
843 * is then restarted, amount_needed is the number needed by this
844 * level (h) of the balancing analysis.
846 * Note that for systems with many processes writing, it would be
847 * more layout optimal to calculate the total number needed by all
848 * levels and then to run reiserfs_new_blocks to get all of them at
853 * Initiate number_of_freeblk to the amount acquired prior to the
854 * restart of the analysis or 0 if not restarted, then subtract the
855 * amount needed by all of the levels of the tree below h.
857 /* blknum includes S[h], so we subtract 1 in this calculation */
858 for (counter = 0, number_of_freeblk = tb->cur_blknum;
859 counter < h; counter++)
861 (tb->blknum[counter]) ? (tb->blknum[counter] -
864 /* Allocate missing empty blocks. */
865 /* if Sh == 0 then we are getting a new root */
866 amount_needed = (Sh) ? (tb->blknum[h] - 1) : 1;
868 * Amount_needed = the amount that we need more than the
869 * amount that we have.
871 if (amount_needed > number_of_freeblk)
872 amount_needed -= number_of_freeblk;
873 else /* If we have enough already then there is nothing to do. */
877 * No need to check quota - is not allocated for blocks used
878 * for formatted nodes
880 if (reiserfs_new_form_blocknrs(tb, blocknrs,
881 amount_needed) == NO_DISK_SPACE)
882 return NO_DISK_SPACE;
884 /* for each blocknumber we just got, get a buffer and stick it on FEB */
885 for (blocknr = blocknrs, counter = 0;
886 counter < amount_needed; blocknr++, counter++) {
889 "PAP-8135: reiserfs_new_blocknrs failed when got new blocks");
891 new_bh = sb_getblk(sb, *blocknr);
892 RFALSE(buffer_dirty(new_bh) ||
893 buffer_journaled(new_bh) ||
894 buffer_journal_dirty(new_bh),
895 "PAP-8140: journaled or dirty buffer %b for the new block",
898 /* Put empty buffers into the array. */
899 RFALSE(tb->FEB[tb->cur_blknum],
900 "PAP-8141: busy slot for new buffer");
902 set_buffer_journal_new(new_bh);
903 tb->FEB[tb->cur_blknum++] = new_bh;
906 if (retval == CARRY_ON && FILESYSTEM_CHANGED_TB(tb))
907 retval = REPEAT_SEARCH;
913 * Get free space of the left neighbor, which is stored in the parent
914 * node of the left neighbor.
916 static int get_lfree(struct tree_balance *tb, int h)
918 struct buffer_head *l, *f;
921 if ((f = PATH_H_PPARENT(tb->tb_path, h)) == NULL ||
922 (l = tb->FL[h]) == NULL)
926 order = PATH_H_B_ITEM_ORDER(tb->tb_path, h) - 1;
928 order = B_NR_ITEMS(l);
932 return (MAX_CHILD_SIZE(f) - dc_size(B_N_CHILD(f, order)));
936 * Get free space of the right neighbor,
937 * which is stored in the parent node of the right neighbor.
939 static int get_rfree(struct tree_balance *tb, int h)
941 struct buffer_head *r, *f;
944 if ((f = PATH_H_PPARENT(tb->tb_path, h)) == NULL ||
945 (r = tb->FR[h]) == NULL)
949 order = PATH_H_B_ITEM_ORDER(tb->tb_path, h) + 1;
955 return (MAX_CHILD_SIZE(f) - dc_size(B_N_CHILD(f, order)));
959 /* Check whether left neighbor is in memory. */
960 static int is_left_neighbor_in_cache(struct tree_balance *tb, int h)
962 struct buffer_head *father, *left;
963 struct super_block *sb = tb->tb_sb;
964 b_blocknr_t left_neighbor_blocknr;
965 int left_neighbor_position;
967 /* Father of the left neighbor does not exist. */
971 /* Calculate father of the node to be balanced. */
972 father = PATH_H_PBUFFER(tb->tb_path, h + 1);
975 !B_IS_IN_TREE(father) ||
976 !B_IS_IN_TREE(tb->FL[h]) ||
977 !buffer_uptodate(father) ||
978 !buffer_uptodate(tb->FL[h]),
979 "vs-8165: F[h] (%b) or FL[h] (%b) is invalid",
983 * Get position of the pointer to the left neighbor
984 * into the left father.
986 left_neighbor_position = (father == tb->FL[h]) ?
987 tb->lkey[h] : B_NR_ITEMS(tb->FL[h]);
988 /* Get left neighbor block number. */
989 left_neighbor_blocknr =
990 B_N_CHILD_NUM(tb->FL[h], left_neighbor_position);
991 /* Look for the left neighbor in the cache. */
992 if ((left = sb_find_get_block(sb, left_neighbor_blocknr))) {
994 RFALSE(buffer_uptodate(left) && !B_IS_IN_TREE(left),
995 "vs-8170: left neighbor (%b %z) is not in the tree",
1004 #define LEFT_PARENTS 'l'
1005 #define RIGHT_PARENTS 'r'
1007 static void decrement_key(struct cpu_key *key)
1009 /* call item specific function for this key */
1010 item_ops[cpu_key_k_type(key)]->decrement_key(key);
1014 * Calculate far left/right parent of the left/right neighbor of the
1015 * current node, that is calculate the left/right (FL[h]/FR[h]) neighbor
1016 * of the parent F[h].
1017 * Calculate left/right common parent of the current node and L[h]/R[h].
1018 * Calculate left/right delimiting key position.
1019 * Returns: PATH_INCORRECT - path in the tree is not correct
1020 * SCHEDULE_OCCURRED - schedule occurred while the function worked
1021 * CARRY_ON - schedule didn't occur while the function
1024 static int get_far_parent(struct tree_balance *tb,
1026 struct buffer_head **pfather,
1027 struct buffer_head **pcom_father, char c_lr_par)
1029 struct buffer_head *parent;
1030 INITIALIZE_PATH(s_path_to_neighbor_father);
1031 struct treepath *path = tb->tb_path;
1032 struct cpu_key s_lr_father_key;
1035 first_last_position = 0,
1036 path_offset = PATH_H_PATH_OFFSET(path, h);
1039 * Starting from F[h] go upwards in the tree, and look for the common
1040 * ancestor of F[h], and its neighbor l/r, that should be obtained.
1043 counter = path_offset;
1045 RFALSE(counter < FIRST_PATH_ELEMENT_OFFSET,
1046 "PAP-8180: invalid path length");
1048 for (; counter > FIRST_PATH_ELEMENT_OFFSET; counter--) {
1050 * Check whether parent of the current buffer in the path
1051 * is really parent in the tree.
1054 (parent = PATH_OFFSET_PBUFFER(path, counter - 1)))
1055 return REPEAT_SEARCH;
1057 /* Check whether position in the parent is correct. */
1059 PATH_OFFSET_POSITION(path,
1062 return REPEAT_SEARCH;
1065 * Check whether parent at the path really points
1068 if (B_N_CHILD_NUM(parent, position) !=
1069 PATH_OFFSET_PBUFFER(path, counter)->b_blocknr)
1070 return REPEAT_SEARCH;
1073 * Return delimiting key if position in the parent is not
1074 * equal to first/last one.
1076 if (c_lr_par == RIGHT_PARENTS)
1077 first_last_position = B_NR_ITEMS(parent);
1078 if (position != first_last_position) {
1079 *pcom_father = parent;
1080 get_bh(*pcom_father);
1081 /*(*pcom_father = parent)->b_count++; */
1086 /* if we are in the root of the tree, then there is no common father */
1087 if (counter == FIRST_PATH_ELEMENT_OFFSET) {
1089 * Check whether first buffer in the path is the
1092 if (PATH_OFFSET_PBUFFER
1094 FIRST_PATH_ELEMENT_OFFSET)->b_blocknr ==
1095 SB_ROOT_BLOCK(tb->tb_sb)) {
1096 *pfather = *pcom_father = NULL;
1099 return REPEAT_SEARCH;
1102 RFALSE(B_LEVEL(*pcom_father) <= DISK_LEAF_NODE_LEVEL,
1103 "PAP-8185: (%b %z) level too small",
1104 *pcom_father, *pcom_father);
1106 /* Check whether the common parent is locked. */
1108 if (buffer_locked(*pcom_father)) {
1110 /* Release the write lock while the buffer is busy */
1111 int depth = reiserfs_write_unlock_nested(tb->tb_sb);
1112 __wait_on_buffer(*pcom_father);
1113 reiserfs_write_lock_nested(tb->tb_sb, depth);
1114 if (FILESYSTEM_CHANGED_TB(tb)) {
1115 brelse(*pcom_father);
1116 return REPEAT_SEARCH;
1121 * So, we got common parent of the current node and its
1122 * left/right neighbor. Now we are getting the parent of the
1123 * left/right neighbor.
1126 /* Form key to get parent of the left/right neighbor. */
1127 le_key2cpu_key(&s_lr_father_key,
1128 internal_key(*pcom_father,
1130 LEFT_PARENTS) ? (tb->lkey[h - 1] =
1136 if (c_lr_par == LEFT_PARENTS)
1137 decrement_key(&s_lr_father_key);
1140 (tb->tb_sb, &s_lr_father_key, &s_path_to_neighbor_father,
1142 /* path is released */
1145 if (FILESYSTEM_CHANGED_TB(tb)) {
1146 pathrelse(&s_path_to_neighbor_father);
1147 brelse(*pcom_father);
1148 return REPEAT_SEARCH;
1151 *pfather = PATH_PLAST_BUFFER(&s_path_to_neighbor_father);
1153 RFALSE(B_LEVEL(*pfather) != h + 1,
1154 "PAP-8190: (%b %z) level too small", *pfather, *pfather);
1155 RFALSE(s_path_to_neighbor_father.path_length <
1156 FIRST_PATH_ELEMENT_OFFSET, "PAP-8192: path length is too small");
1158 s_path_to_neighbor_father.path_length--;
1159 pathrelse(&s_path_to_neighbor_father);
1164 * Get parents of neighbors of node in the path(S[path_offset]) and
1165 * common parents of S[path_offset] and L[path_offset]/R[path_offset]:
1166 * F[path_offset], FL[path_offset], FR[path_offset], CFL[path_offset],
1168 * Calculate numbers of left and right delimiting keys position:
1169 * lkey[path_offset], rkey[path_offset].
1170 * Returns: SCHEDULE_OCCURRED - schedule occurred while the function worked
1171 * CARRY_ON - schedule didn't occur while the function worked
1173 static int get_parents(struct tree_balance *tb, int h)
1175 struct treepath *path = tb->tb_path;
1178 path_offset = PATH_H_PATH_OFFSET(tb->tb_path, h);
1179 struct buffer_head *curf, *curcf;
1181 /* Current node is the root of the tree or will be root of the tree */
1182 if (path_offset <= FIRST_PATH_ELEMENT_OFFSET) {
1184 * The root can not have parents.
1185 * Release nodes which previously were obtained as
1186 * parents of the current node neighbors.
1199 /* Get parent FL[path_offset] of L[path_offset]. */
1200 position = PATH_OFFSET_POSITION(path, path_offset - 1);
1202 /* Current node is not the first child of its parent. */
1203 curf = PATH_OFFSET_PBUFFER(path, path_offset - 1);
1204 curcf = PATH_OFFSET_PBUFFER(path, path_offset - 1);
1207 tb->lkey[h] = position - 1;
1210 * Calculate current parent of L[path_offset], which is the
1211 * left neighbor of the current node. Calculate current
1212 * common parent of L[path_offset] and the current node.
1213 * Note that CFL[path_offset] not equal FL[path_offset] and
1214 * CFL[path_offset] not equal F[path_offset].
1215 * Calculate lkey[path_offset].
1217 if ((ret = get_far_parent(tb, h + 1, &curf,
1219 LEFT_PARENTS)) != CARRY_ON)
1224 tb->FL[h] = curf; /* New initialization of FL[h]. */
1226 tb->CFL[h] = curcf; /* New initialization of CFL[h]. */
1228 RFALSE((curf && !B_IS_IN_TREE(curf)) ||
1229 (curcf && !B_IS_IN_TREE(curcf)),
1230 "PAP-8195: FL (%b) or CFL (%b) is invalid", curf, curcf);
1232 /* Get parent FR[h] of R[h]. */
1234 /* Current node is the last child of F[h]. FR[h] != F[h]. */
1235 if (position == B_NR_ITEMS(PATH_H_PBUFFER(path, h + 1))) {
1237 * Calculate current parent of R[h], which is the right
1238 * neighbor of F[h]. Calculate current common parent of
1239 * R[h] and current node. Note that CFR[h] not equal
1240 * FR[path_offset] and CFR[h] not equal F[h].
1243 get_far_parent(tb, h + 1, &curf, &curcf,
1244 RIGHT_PARENTS)) != CARRY_ON)
1247 /* Current node is not the last child of its parent F[h]. */
1248 curf = PATH_OFFSET_PBUFFER(path, path_offset - 1);
1249 curcf = PATH_OFFSET_PBUFFER(path, path_offset - 1);
1252 tb->rkey[h] = position;
1256 /* New initialization of FR[path_offset]. */
1260 /* New initialization of CFR[path_offset]. */
1263 RFALSE((curf && !B_IS_IN_TREE(curf)) ||
1264 (curcf && !B_IS_IN_TREE(curcf)),
1265 "PAP-8205: FR (%b) or CFR (%b) is invalid", curf, curcf);
1271 * it is possible to remove node as result of shiftings to
1272 * neighbors even when we insert or paste item.
1274 static inline int can_node_be_removed(int mode, int lfree, int sfree, int rfree,
1275 struct tree_balance *tb, int h)
1277 struct buffer_head *Sh = PATH_H_PBUFFER(tb->tb_path, h);
1278 int levbytes = tb->insert_size[h];
1279 struct item_head *ih;
1280 struct reiserfs_key *r_key = NULL;
1282 ih = item_head(Sh, 0);
1284 r_key = internal_key(tb->CFR[h], tb->rkey[h]);
1286 if (lfree + rfree + sfree < MAX_CHILD_SIZE(Sh) + levbytes
1287 /* shifting may merge items which might save space */
1290 && op_is_left_mergeable(&(ih->ih_key), Sh->b_size)) ? IH_SIZE : 0)
1293 && op_is_left_mergeable(r_key, Sh->b_size)) ? IH_SIZE : 0)
1294 + ((h) ? KEY_SIZE : 0)) {
1295 /* node can not be removed */
1296 if (sfree >= levbytes) {
1297 /* new item fits into node S[h] without any shifting */
1301 ((mode == M_INSERT) ? 1 : 0);
1302 set_parameters(tb, h, 0, 0, 1, NULL, -1, -1);
1303 return NO_BALANCING_NEEDED;
1306 PROC_INFO_INC(tb->tb_sb, can_node_be_removed[h]);
1307 return !NO_BALANCING_NEEDED;
1311 * Check whether current node S[h] is balanced when increasing its size by
1312 * Inserting or Pasting.
1313 * Calculate parameters for balancing for current level h.
1315 * tb tree_balance structure;
1316 * h current level of the node;
1317 * inum item number in S[h];
1318 * mode i - insert, p - paste;
1319 * Returns: 1 - schedule occurred;
1320 * 0 - balancing for higher levels needed;
1321 * -1 - no balancing for higher levels needed;
1322 * -2 - no disk space.
1324 /* ip means Inserting or Pasting */
1325 static int ip_check_balance(struct tree_balance *tb, int h)
1327 struct virtual_node *vn = tb->tb_vn;
1329 * Number of bytes that must be inserted into (value is negative
1330 * if bytes are deleted) buffer which contains node being balanced.
1331 * The mnemonic is that the attempted change in node space used
1332 * level is levbytes bytes.
1337 int lfree, sfree, rfree /* free space in L, S and R */ ;
1340 * nver is short for number of vertixes, and lnver is the number if
1341 * we shift to the left, rnver is the number if we shift to the
1342 * right, and lrnver is the number if we shift in both directions.
1343 * The goal is to minimize first the number of vertixes, and second,
1344 * the number of vertixes whose contents are changed by shifting,
1345 * and third the number of uncached vertixes whose contents are
1346 * changed by shifting and must be read from disk.
1348 int nver, lnver, rnver, lrnver;
1351 * used at leaf level only, S0 = S[0] is the node being balanced,
1352 * sInum [ I = 0,1,2 ] is the number of items that will
1353 * remain in node SI after balancing. S1 and S2 are new
1354 * nodes that might be created.
1358 * we perform 8 calls to get_num_ver(). For each call we
1359 * calculate five parameters. where 4th parameter is s1bytes
1362 * s0num, s1num, s2num for 8 cases
1363 * 0,1 - do not shift and do not shift but bottle
1364 * 2 - shift only whole item to left
1365 * 3 - shift to left and bottle as much as possible
1366 * 4,5 - shift to right (whole items and as much as possible
1367 * 6,7 - shift to both directions (whole items and as much as possible)
1369 short snum012[40] = { 0, };
1371 /* Sh is the node whose balance is currently being checked */
1372 struct buffer_head *Sh;
1374 Sh = PATH_H_PBUFFER(tb->tb_path, h);
1375 levbytes = tb->insert_size[h];
1377 /* Calculate balance parameters for creating new root. */
1380 reiserfs_panic(tb->tb_sb, "vs-8210",
1381 "S[0] can not be 0");
1382 switch (ret = get_empty_nodes(tb, h)) {
1383 /* no balancing for higher levels needed */
1385 set_parameters(tb, h, 0, 0, 1, NULL, -1, -1);
1386 return NO_BALANCING_NEEDED;
1392 reiserfs_panic(tb->tb_sb, "vs-8215", "incorrect "
1393 "return value of get_empty_nodes");
1397 /* get parents of S[h] neighbors. */
1398 ret = get_parents(tb, h);
1399 if (ret != CARRY_ON)
1402 sfree = B_FREE_SPACE(Sh);
1404 /* get free space of neighbors */
1405 rfree = get_rfree(tb, h);
1406 lfree = get_lfree(tb, h);
1408 /* and new item fits into node S[h] without any shifting */
1409 if (can_node_be_removed(vn->vn_mode, lfree, sfree, rfree, tb, h) ==
1410 NO_BALANCING_NEEDED)
1411 return NO_BALANCING_NEEDED;
1413 create_virtual_node(tb, h);
1416 * determine maximal number of items we can shift to the left
1417 * neighbor (in tb structure) and the maximal number of bytes
1418 * that can flow to the left neighbor from the left most liquid
1419 * item that cannot be shifted from S[0] entirely (returned value)
1421 check_left(tb, h, lfree);
1424 * determine maximal number of items we can shift to the right
1425 * neighbor (in tb structure) and the maximal number of bytes
1426 * that can flow to the right neighbor from the right most liquid
1427 * item that cannot be shifted from S[0] entirely (returned value)
1429 check_right(tb, h, rfree);
1432 * all contents of internal node S[h] can be moved into its
1433 * neighbors, S[h] will be removed after balancing
1435 if (h && (tb->rnum[h] + tb->lnum[h] >= vn->vn_nr_item + 1)) {
1439 * Since we are working on internal nodes, and our internal
1440 * nodes have fixed size entries, then we can balance by the
1441 * number of items rather than the space they consume. In this
1442 * routine we set the left node equal to the right node,
1443 * allowing a difference of less than or equal to 1 child
1447 ((MAX_NR_KEY(Sh) << 1) + 2 - tb->lnum[h] - tb->rnum[h] +
1448 vn->vn_nr_item + 1) / 2 - (MAX_NR_KEY(Sh) + 1 -
1450 set_parameters(tb, h, vn->vn_nr_item + 1 - to_r, to_r, 0, NULL,
1456 * this checks balance condition, that any two neighboring nodes
1457 * can not fit in one node
1460 (tb->lnum[h] >= vn->vn_nr_item + 1 ||
1461 tb->rnum[h] >= vn->vn_nr_item + 1),
1462 "vs-8220: tree is not balanced on internal level");
1463 RFALSE(!h && ((tb->lnum[h] >= vn->vn_nr_item && (tb->lbytes == -1)) ||
1464 (tb->rnum[h] >= vn->vn_nr_item && (tb->rbytes == -1))),
1465 "vs-8225: tree is not balanced on leaf level");
1468 * all contents of S[0] can be moved into its neighbors
1469 * S[0] will be removed after balancing.
1471 if (!h && is_leaf_removable(tb))
1475 * why do we perform this check here rather than earlier??
1476 * Answer: we can win 1 node in some cases above. Moreover we
1477 * checked it above, when we checked, that S[0] is not removable
1481 /* new item fits into node S[h] without any shifting */
1482 if (sfree >= levbytes) {
1484 tb->s0num = vn->vn_nr_item;
1485 set_parameters(tb, h, 0, 0, 1, NULL, -1, -1);
1486 return NO_BALANCING_NEEDED;
1490 int lpar, rpar, nset, lset, rset, lrset;
1491 /* regular overflowing of the node */
1494 * get_num_ver works in 2 modes (FLOW & NO_FLOW)
1495 * lpar, rpar - number of items we can shift to left/right
1496 * neighbor (including splitting item)
1497 * nset, lset, rset, lrset - shows, whether flowing items
1498 * give better packing
1501 #define NO_FLOW 0 /* do not any splitting */
1503 /* we choose one of the following */
1504 #define NOTHING_SHIFT_NO_FLOW 0
1505 #define NOTHING_SHIFT_FLOW 5
1506 #define LEFT_SHIFT_NO_FLOW 10
1507 #define LEFT_SHIFT_FLOW 15
1508 #define RIGHT_SHIFT_NO_FLOW 20
1509 #define RIGHT_SHIFT_FLOW 25
1510 #define LR_SHIFT_NO_FLOW 30
1511 #define LR_SHIFT_FLOW 35
1517 * calculate number of blocks S[h] must be split into when
1518 * nothing is shifted to the neighbors, as well as number of
1519 * items in each part of the split node (s012 numbers),
1520 * and number of bytes (s1bytes) of the shared drop which
1523 nset = NOTHING_SHIFT_NO_FLOW;
1524 nver = get_num_ver(vn->vn_mode, tb, h,
1525 0, -1, h ? vn->vn_nr_item : 0, -1,
1532 * note, that in this case we try to bottle
1533 * between S[0] and S1 (S1 - the first new node)
1535 nver1 = get_num_ver(vn->vn_mode, tb, h,
1537 snum012 + NOTHING_SHIFT_FLOW, FLOW);
1539 nset = NOTHING_SHIFT_FLOW, nver = nver1;
1543 * calculate number of blocks S[h] must be split into when
1544 * l_shift_num first items and l_shift_bytes of the right
1545 * most liquid item to be shifted are shifted to the left
1546 * neighbor, as well as number of items in each part of the
1547 * splitted node (s012 numbers), and number of bytes
1548 * (s1bytes) of the shared drop which flow to S1 if any
1550 lset = LEFT_SHIFT_NO_FLOW;
1551 lnver = get_num_ver(vn->vn_mode, tb, h,
1552 lpar - ((h || tb->lbytes == -1) ? 0 : 1),
1553 -1, h ? vn->vn_nr_item : 0, -1,
1554 snum012 + LEFT_SHIFT_NO_FLOW, NO_FLOW);
1558 lnver1 = get_num_ver(vn->vn_mode, tb, h,
1560 ((tb->lbytes != -1) ? 1 : 0),
1562 snum012 + LEFT_SHIFT_FLOW, FLOW);
1564 lset = LEFT_SHIFT_FLOW, lnver = lnver1;
1568 * calculate number of blocks S[h] must be split into when
1569 * r_shift_num first items and r_shift_bytes of the left most
1570 * liquid item to be shifted are shifted to the right neighbor,
1571 * as well as number of items in each part of the splitted
1572 * node (s012 numbers), and number of bytes (s1bytes) of the
1573 * shared drop which flow to S1 if any
1575 rset = RIGHT_SHIFT_NO_FLOW;
1576 rnver = get_num_ver(vn->vn_mode, tb, h,
1578 h ? (vn->vn_nr_item - rpar) : (rpar -
1583 snum012 + RIGHT_SHIFT_NO_FLOW, NO_FLOW);
1587 rnver1 = get_num_ver(vn->vn_mode, tb, h,
1590 ((tb->rbytes != -1) ? 1 : 0)),
1592 snum012 + RIGHT_SHIFT_FLOW, FLOW);
1595 rset = RIGHT_SHIFT_FLOW, rnver = rnver1;
1599 * calculate number of blocks S[h] must be split into when
1600 * items are shifted in both directions, as well as number
1601 * of items in each part of the splitted node (s012 numbers),
1602 * and number of bytes (s1bytes) of the shared drop which
1605 lrset = LR_SHIFT_NO_FLOW;
1606 lrnver = get_num_ver(vn->vn_mode, tb, h,
1607 lpar - ((h || tb->lbytes == -1) ? 0 : 1),
1609 h ? (vn->vn_nr_item - rpar) : (rpar -
1614 snum012 + LR_SHIFT_NO_FLOW, NO_FLOW);
1618 lrnver1 = get_num_ver(vn->vn_mode, tb, h,
1620 ((tb->lbytes != -1) ? 1 : 0),
1623 ((tb->rbytes != -1) ? 1 : 0)),
1625 snum012 + LR_SHIFT_FLOW, FLOW);
1626 if (lrnver > lrnver1)
1627 lrset = LR_SHIFT_FLOW, lrnver = lrnver1;
1631 * Our general shifting strategy is:
1632 * 1) to minimized number of new nodes;
1633 * 2) to minimized number of neighbors involved in shifting;
1634 * 3) to minimized number of disk reads;
1637 /* we can win TWO or ONE nodes by shifting in both directions */
1638 if (lrnver < lnver && lrnver < rnver) {
1640 (tb->lnum[h] != 1 ||
1642 lrnver != 1 || rnver != 2 || lnver != 2
1643 || h != 1), "vs-8230: bad h");
1644 if (lrset == LR_SHIFT_FLOW)
1645 set_parameters(tb, h, tb->lnum[h], tb->rnum[h],
1646 lrnver, snum012 + lrset,
1647 tb->lbytes, tb->rbytes);
1649 set_parameters(tb, h,
1651 ((tb->lbytes == -1) ? 0 : 1),
1653 ((tb->rbytes == -1) ? 0 : 1),
1654 lrnver, snum012 + lrset, -1, -1);
1660 * if shifting doesn't lead to better packing
1663 if (nver == lrnver) {
1664 set_parameters(tb, h, 0, 0, nver, snum012 + nset, -1,
1670 * now we know that for better packing shifting in only one
1671 * direction either to the left or to the right is required
1675 * if shifting to the left is better than
1676 * shifting to the right
1678 if (lnver < rnver) {
1684 * if shifting to the right is better than
1685 * shifting to the left
1687 if (lnver > rnver) {
1688 SET_PAR_SHIFT_RIGHT;
1693 * now shifting in either direction gives the same number
1694 * of nodes and we can make use of the cached neighbors
1696 if (is_left_neighbor_in_cache(tb, h)) {
1702 * shift to the right independently on whether the
1703 * right neighbor in cache or not
1705 SET_PAR_SHIFT_RIGHT;
1711 * Check whether current node S[h] is balanced when Decreasing its size by
1712 * Deleting or Cutting for INTERNAL node of S+tree.
1713 * Calculate parameters for balancing for current level h.
1715 * tb tree_balance structure;
1716 * h current level of the node;
1717 * inum item number in S[h];
1718 * mode i - insert, p - paste;
1719 * Returns: 1 - schedule occurred;
1720 * 0 - balancing for higher levels needed;
1721 * -1 - no balancing for higher levels needed;
1722 * -2 - no disk space.
1724 * Note: Items of internal nodes have fixed size, so the balance condition for
1725 * the internal part of S+tree is as for the B-trees.
1727 static int dc_check_balance_internal(struct tree_balance *tb, int h)
1729 struct virtual_node *vn = tb->tb_vn;
1732 * Sh is the node whose balance is currently being checked,
1733 * and Fh is its father.
1735 struct buffer_head *Sh, *Fh;
1737 int lfree, rfree /* free space in L and R */ ;
1739 Sh = PATH_H_PBUFFER(tb->tb_path, h);
1740 Fh = PATH_H_PPARENT(tb->tb_path, h);
1742 maxsize = MAX_CHILD_SIZE(Sh);
1745 * using tb->insert_size[h], which is negative in this case,
1746 * create_virtual_node calculates:
1747 * new_nr_item = number of items node would have if operation is
1748 * performed without balancing (new_nr_item);
1750 create_virtual_node(tb, h);
1752 if (!Fh) { /* S[h] is the root. */
1753 /* no balancing for higher levels needed */
1754 if (vn->vn_nr_item > 0) {
1755 set_parameters(tb, h, 0, 0, 1, NULL, -1, -1);
1756 return NO_BALANCING_NEEDED;
1760 * Current root will be deleted resulting in
1761 * decrementing the tree height.
1763 set_parameters(tb, h, 0, 0, 0, NULL, -1, -1);
1767 if ((ret = get_parents(tb, h)) != CARRY_ON)
1770 /* get free space of neighbors */
1771 rfree = get_rfree(tb, h);
1772 lfree = get_lfree(tb, h);
1774 /* determine maximal number of items we can fit into neighbors */
1775 check_left(tb, h, lfree);
1776 check_right(tb, h, rfree);
1779 * Balance condition for the internal node is valid.
1780 * In this case we balance only if it leads to better packing.
1782 if (vn->vn_nr_item >= MIN_NR_KEY(Sh)) {
1784 * Here we join S[h] with one of its neighbors,
1785 * which is impossible with greater values of new_nr_item.
1787 if (vn->vn_nr_item == MIN_NR_KEY(Sh)) {
1788 /* All contents of S[h] can be moved to L[h]. */
1789 if (tb->lnum[h] >= vn->vn_nr_item + 1) {
1795 PATH_H_B_ITEM_ORDER(tb->tb_path,
1797 0) ? B_NR_ITEMS(tb->FL[h]) : n - 1;
1798 n = dc_size(B_N_CHILD(tb->FL[h], order_L)) /
1799 (DC_SIZE + KEY_SIZE);
1800 set_parameters(tb, h, -n - 1, 0, 0, NULL, -1,
1805 /* All contents of S[h] can be moved to R[h]. */
1806 if (tb->rnum[h] >= vn->vn_nr_item + 1) {
1812 PATH_H_B_ITEM_ORDER(tb->tb_path,
1814 B_NR_ITEMS(Fh)) ? 0 : n + 1;
1815 n = dc_size(B_N_CHILD(tb->FR[h], order_R)) /
1816 (DC_SIZE + KEY_SIZE);
1817 set_parameters(tb, h, 0, -n - 1, 0, NULL, -1,
1824 * All contents of S[h] can be moved to the neighbors
1827 if (tb->rnum[h] + tb->lnum[h] >= vn->vn_nr_item + 1) {
1831 ((MAX_NR_KEY(Sh) << 1) + 2 - tb->lnum[h] -
1832 tb->rnum[h] + vn->vn_nr_item + 1) / 2 -
1833 (MAX_NR_KEY(Sh) + 1 - tb->rnum[h]);
1834 set_parameters(tb, h, vn->vn_nr_item + 1 - to_r, to_r,
1839 /* Balancing does not lead to better packing. */
1840 set_parameters(tb, h, 0, 0, 1, NULL, -1, -1);
1841 return NO_BALANCING_NEEDED;
1845 * Current node contain insufficient number of items.
1846 * Balancing is required.
1848 /* Check whether we can merge S[h] with left neighbor. */
1849 if (tb->lnum[h] >= vn->vn_nr_item + 1)
1850 if (is_left_neighbor_in_cache(tb, h)
1851 || tb->rnum[h] < vn->vn_nr_item + 1 || !tb->FR[h]) {
1857 PATH_H_B_ITEM_ORDER(tb->tb_path,
1859 0) ? B_NR_ITEMS(tb->FL[h]) : n - 1;
1860 n = dc_size(B_N_CHILD(tb->FL[h], order_L)) / (DC_SIZE +
1862 set_parameters(tb, h, -n - 1, 0, 0, NULL, -1, -1);
1866 /* Check whether we can merge S[h] with right neighbor. */
1867 if (tb->rnum[h] >= vn->vn_nr_item + 1) {
1873 PATH_H_B_ITEM_ORDER(tb->tb_path,
1874 h)) == B_NR_ITEMS(Fh)) ? 0 : (n + 1);
1875 n = dc_size(B_N_CHILD(tb->FR[h], order_R)) / (DC_SIZE +
1877 set_parameters(tb, h, 0, -n - 1, 0, NULL, -1, -1);
1881 /* All contents of S[h] can be moved to the neighbors (L[h] & R[h]). */
1882 if (tb->rnum[h] + tb->lnum[h] >= vn->vn_nr_item + 1) {
1886 ((MAX_NR_KEY(Sh) << 1) + 2 - tb->lnum[h] - tb->rnum[h] +
1887 vn->vn_nr_item + 1) / 2 - (MAX_NR_KEY(Sh) + 1 -
1889 set_parameters(tb, h, vn->vn_nr_item + 1 - to_r, to_r, 0, NULL,
1894 /* For internal nodes try to borrow item from a neighbor */
1895 RFALSE(!tb->FL[h] && !tb->FR[h], "vs-8235: trying to borrow for root");
1897 /* Borrow one or two items from caching neighbor */
1898 if (is_left_neighbor_in_cache(tb, h) || !tb->FR[h]) {
1902 (MAX_NR_KEY(Sh) + 1 - tb->lnum[h] + vn->vn_nr_item +
1903 1) / 2 - (vn->vn_nr_item + 1);
1904 set_parameters(tb, h, -from_l, 0, 1, NULL, -1, -1);
1908 set_parameters(tb, h, 0,
1909 -((MAX_NR_KEY(Sh) + 1 - tb->rnum[h] + vn->vn_nr_item +
1910 1) / 2 - (vn->vn_nr_item + 1)), 1, NULL, -1, -1);
1915 * Check whether current node S[h] is balanced when Decreasing its size by
1916 * Deleting or Truncating for LEAF node of S+tree.
1917 * Calculate parameters for balancing for current level h.
1919 * tb tree_balance structure;
1920 * h current level of the node;
1921 * inum item number in S[h];
1922 * mode i - insert, p - paste;
1923 * Returns: 1 - schedule occurred;
1924 * 0 - balancing for higher levels needed;
1925 * -1 - no balancing for higher levels needed;
1926 * -2 - no disk space.
1928 static int dc_check_balance_leaf(struct tree_balance *tb, int h)
1930 struct virtual_node *vn = tb->tb_vn;
1933 * Number of bytes that must be deleted from
1934 * (value is negative if bytes are deleted) buffer which
1935 * contains node being balanced. The mnemonic is that the
1936 * attempted change in node space used level is levbytes bytes.
1940 /* the maximal item size */
1944 * S0 is the node whose balance is currently being checked,
1945 * and F0 is its father.
1947 struct buffer_head *S0, *F0;
1948 int lfree, rfree /* free space in L and R */ ;
1950 S0 = PATH_H_PBUFFER(tb->tb_path, 0);
1951 F0 = PATH_H_PPARENT(tb->tb_path, 0);
1953 levbytes = tb->insert_size[h];
1955 maxsize = MAX_CHILD_SIZE(S0); /* maximal possible size of an item */
1957 if (!F0) { /* S[0] is the root now. */
1959 RFALSE(-levbytes >= maxsize - B_FREE_SPACE(S0),
1960 "vs-8240: attempt to create empty buffer tree");
1962 set_parameters(tb, h, 0, 0, 1, NULL, -1, -1);
1963 return NO_BALANCING_NEEDED;
1966 if ((ret = get_parents(tb, h)) != CARRY_ON)
1969 /* get free space of neighbors */
1970 rfree = get_rfree(tb, h);
1971 lfree = get_lfree(tb, h);
1973 create_virtual_node(tb, h);
1975 /* if 3 leaves can be merge to one, set parameters and return */
1976 if (are_leaves_removable(tb, lfree, rfree))
1980 * determine maximal number of items we can shift to the left/right
1981 * neighbor and the maximal number of bytes that can flow to the
1982 * left/right neighbor from the left/right most liquid item that
1983 * cannot be shifted from S[0] entirely
1985 check_left(tb, h, lfree);
1986 check_right(tb, h, rfree);
1988 /* check whether we can merge S with left neighbor. */
1989 if (tb->lnum[0] >= vn->vn_nr_item && tb->lbytes == -1)
1990 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 */
1994 "vs-8245: dc_check_balance_leaf: FL[h] must exist");
1996 /* set parameter to merge S[0] with its left neighbor */
1997 set_parameters(tb, h, -1, 0, 0, NULL, -1, -1);
2001 /* check whether we can merge S[0] with right neighbor. */
2002 if (tb->rnum[0] >= vn->vn_nr_item && tb->rbytes == -1) {
2003 set_parameters(tb, h, 0, -1, 0, NULL, -1, -1);
2008 * All contents of S[0] can be moved to the neighbors (L[0] & R[0]).
2009 * Set parameters and return
2011 if (is_leaf_removable(tb))
2014 /* Balancing is not required. */
2015 tb->s0num = vn->vn_nr_item;
2016 set_parameters(tb, h, 0, 0, 1, NULL, -1, -1);
2017 return NO_BALANCING_NEEDED;
2021 * Check whether current node S[h] is balanced when Decreasing its size by
2022 * Deleting or Cutting.
2023 * Calculate parameters for balancing for current level h.
2025 * tb tree_balance structure;
2026 * h current level of the node;
2027 * inum item number in S[h];
2028 * mode d - delete, c - cut.
2029 * Returns: 1 - schedule occurred;
2030 * 0 - balancing for higher levels needed;
2031 * -1 - no balancing for higher levels needed;
2032 * -2 - no disk space.
2034 static int dc_check_balance(struct tree_balance *tb, int h)
2036 RFALSE(!(PATH_H_PBUFFER(tb->tb_path, h)),
2037 "vs-8250: S is not initialized");
2040 return dc_check_balance_internal(tb, h);
2042 return dc_check_balance_leaf(tb, h);
2046 * Check whether current node S[h] is balanced.
2047 * Calculate parameters for balancing for current level h.
2050 * tb tree_balance structure:
2052 * tb is a large structure that must be read about in the header
2053 * file at the same time as this procedure if the reader is
2054 * to successfully understand this procedure
2056 * h current level of the node;
2057 * inum item number in S[h];
2058 * mode i - insert, p - paste, d - delete, c - cut.
2059 * Returns: 1 - schedule occurred;
2060 * 0 - balancing for higher levels needed;
2061 * -1 - no balancing for higher levels needed;
2062 * -2 - no disk space.
2064 static int check_balance(int mode,
2065 struct tree_balance *tb,
2069 struct item_head *ins_ih, const void *data)
2071 struct virtual_node *vn;
2073 vn = tb->tb_vn = (struct virtual_node *)(tb->vn_buf);
2074 vn->vn_free_ptr = (char *)(tb->tb_vn + 1);
2076 vn->vn_affected_item_num = inum;
2077 vn->vn_pos_in_item = pos_in_item;
2078 vn->vn_ins_ih = ins_ih;
2081 RFALSE(mode == M_INSERT && !vn->vn_ins_ih,
2082 "vs-8255: ins_ih can not be 0 in insert mode");
2084 /* Calculate balance parameters when size of node is increasing. */
2085 if (tb->insert_size[h] > 0)
2086 return ip_check_balance(tb, h);
2088 /* Calculate balance parameters when size of node is decreasing. */
2089 return dc_check_balance(tb, h);
2092 /* Check whether parent at the path is the really parent of the current node.*/
2093 static int get_direct_parent(struct tree_balance *tb, int h)
2095 struct buffer_head *bh;
2096 struct treepath *path = tb->tb_path;
2098 path_offset = PATH_H_PATH_OFFSET(tb->tb_path, h);
2100 /* We are in the root or in the new root. */
2101 if (path_offset <= FIRST_PATH_ELEMENT_OFFSET) {
2103 RFALSE(path_offset < FIRST_PATH_ELEMENT_OFFSET - 1,
2104 "PAP-8260: invalid offset in the path");
2106 if (PATH_OFFSET_PBUFFER(path, FIRST_PATH_ELEMENT_OFFSET)->
2107 b_blocknr == SB_ROOT_BLOCK(tb->tb_sb)) {
2108 /* Root is not changed. */
2109 PATH_OFFSET_PBUFFER(path, path_offset - 1) = NULL;
2110 PATH_OFFSET_POSITION(path, path_offset - 1) = 0;
2113 /* Root is changed and we must recalculate the path. */
2114 return REPEAT_SEARCH;
2117 /* Parent in the path is not in the tree. */
2119 (bh = PATH_OFFSET_PBUFFER(path, path_offset - 1)))
2120 return REPEAT_SEARCH;
2123 PATH_OFFSET_POSITION(path,
2124 path_offset - 1)) > B_NR_ITEMS(bh))
2125 return REPEAT_SEARCH;
2127 /* Parent in the path is not parent of the current node in the tree. */
2128 if (B_N_CHILD_NUM(bh, position) !=
2129 PATH_OFFSET_PBUFFER(path, path_offset)->b_blocknr)
2130 return REPEAT_SEARCH;
2132 if (buffer_locked(bh)) {
2133 int depth = reiserfs_write_unlock_nested(tb->tb_sb);
2134 __wait_on_buffer(bh);
2135 reiserfs_write_lock_nested(tb->tb_sb, depth);
2136 if (FILESYSTEM_CHANGED_TB(tb))
2137 return REPEAT_SEARCH;
2141 * Parent in the path is unlocked and really parent
2142 * of the current node.
2148 * Using lnum[h] and rnum[h] we should determine what neighbors
2150 * need in order to balance S[h], and get them if necessary.
2151 * Returns: SCHEDULE_OCCURRED - schedule occurred while the function worked;
2152 * CARRY_ON - schedule didn't occur while the function worked;
2154 static int get_neighbors(struct tree_balance *tb, int h)
2157 path_offset = PATH_H_PATH_OFFSET(tb->tb_path, h + 1);
2158 unsigned long son_number;
2159 struct super_block *sb = tb->tb_sb;
2160 struct buffer_head *bh;
2163 PROC_INFO_INC(sb, get_neighbors[h]);
2166 /* We need left neighbor to balance S[h]. */
2167 PROC_INFO_INC(sb, need_l_neighbor[h]);
2168 bh = PATH_OFFSET_PBUFFER(tb->tb_path, path_offset);
2170 RFALSE(bh == tb->FL[h] &&
2171 !PATH_OFFSET_POSITION(tb->tb_path, path_offset),
2172 "PAP-8270: invalid position in the parent");
2176 tb->FL[h]) ? tb->lkey[h] : B_NR_ITEMS(tb->
2178 son_number = B_N_CHILD_NUM(tb->FL[h], child_position);
2179 depth = reiserfs_write_unlock_nested(tb->tb_sb);
2180 bh = sb_bread(sb, son_number);
2181 reiserfs_write_lock_nested(tb->tb_sb, depth);
2184 if (FILESYSTEM_CHANGED_TB(tb)) {
2186 PROC_INFO_INC(sb, get_neighbors_restart[h]);
2187 return REPEAT_SEARCH;
2190 RFALSE(!B_IS_IN_TREE(tb->FL[h]) ||
2191 child_position > B_NR_ITEMS(tb->FL[h]) ||
2192 B_N_CHILD_NUM(tb->FL[h], child_position) !=
2193 bh->b_blocknr, "PAP-8275: invalid parent");
2194 RFALSE(!B_IS_IN_TREE(bh), "PAP-8280: invalid child");
2197 MAX_CHILD_SIZE(bh) -
2198 dc_size(B_N_CHILD(tb->FL[0], child_position)),
2199 "PAP-8290: invalid child size of left neighbor");
2205 /* We need right neighbor to balance S[path_offset]. */
2207 PROC_INFO_INC(sb, need_r_neighbor[h]);
2208 bh = PATH_OFFSET_PBUFFER(tb->tb_path, path_offset);
2210 RFALSE(bh == tb->FR[h] &&
2211 PATH_OFFSET_POSITION(tb->tb_path,
2214 "PAP-8295: invalid position in the parent");
2217 (bh == tb->FR[h]) ? tb->rkey[h] + 1 : 0;
2218 son_number = B_N_CHILD_NUM(tb->FR[h], child_position);
2219 depth = reiserfs_write_unlock_nested(tb->tb_sb);
2220 bh = sb_bread(sb, son_number);
2221 reiserfs_write_lock_nested(tb->tb_sb, depth);
2224 if (FILESYSTEM_CHANGED_TB(tb)) {
2226 PROC_INFO_INC(sb, get_neighbors_restart[h]);
2227 return REPEAT_SEARCH;
2233 && B_FREE_SPACE(bh) !=
2234 MAX_CHILD_SIZE(bh) -
2235 dc_size(B_N_CHILD(tb->FR[0], child_position)),
2236 "PAP-8300: invalid child size of right neighbor (%d != %d - %d)",
2237 B_FREE_SPACE(bh), MAX_CHILD_SIZE(bh),
2238 dc_size(B_N_CHILD(tb->FR[0], child_position)));
2244 static int get_virtual_node_size(struct super_block *sb, struct buffer_head *bh)
2246 int max_num_of_items;
2247 int max_num_of_entries;
2248 unsigned long blocksize = sb->s_blocksize;
2250 #define MIN_NAME_LEN 1
2252 max_num_of_items = (blocksize - BLKH_SIZE) / (IH_SIZE + MIN_ITEM_LEN);
2253 max_num_of_entries = (blocksize - BLKH_SIZE - IH_SIZE) /
2254 (DEH_SIZE + MIN_NAME_LEN);
2256 return sizeof(struct virtual_node) +
2257 max(max_num_of_items * sizeof(struct virtual_item),
2258 sizeof(struct virtual_item) + sizeof(struct direntry_uarea) +
2259 (max_num_of_entries - 1) * sizeof(__u16));
2263 * maybe we should fail balancing we are going to perform when kmalloc
2264 * fails several times. But now it will loop until kmalloc gets
2267 static int get_mem_for_virtual_node(struct tree_balance *tb)
2273 size = get_virtual_node_size(tb->tb_sb, PATH_PLAST_BUFFER(tb->tb_path));
2275 /* we have to allocate more memory for virtual node */
2276 if (size > tb->vn_buf_size) {
2278 /* free memory allocated before */
2280 /* this is not needed if kfree is atomic */
2284 /* virtual node requires now more memory */
2285 tb->vn_buf_size = size;
2287 /* get memory for virtual item */
2288 buf = kmalloc(size, GFP_ATOMIC | __GFP_NOWARN);
2291 * getting memory with GFP_KERNEL priority may involve
2292 * balancing now (due to indirect_to_direct conversion
2293 * on dcache shrinking). So, release path and collected
2296 free_buffers_in_tb(tb);
2297 buf = kmalloc(size, GFP_NOFS);
2299 tb->vn_buf_size = 0;
2303 return REPEAT_SEARCH;
2309 if (check_fs && FILESYSTEM_CHANGED_TB(tb))
2310 return REPEAT_SEARCH;
2315 #ifdef CONFIG_REISERFS_CHECK
2316 static void tb_buffer_sanity_check(struct super_block *sb,
2317 struct buffer_head *bh,
2318 const char *descr, int level)
2321 if (atomic_read(&(bh->b_count)) <= 0)
2323 reiserfs_panic(sb, "jmacd-1", "negative or zero "
2324 "reference counter for buffer %s[%d] "
2325 "(%b)", descr, level, bh);
2327 if (!buffer_uptodate(bh))
2328 reiserfs_panic(sb, "jmacd-2", "buffer is not up "
2329 "to date %s[%d] (%b)",
2332 if (!B_IS_IN_TREE(bh))
2333 reiserfs_panic(sb, "jmacd-3", "buffer is not "
2334 "in tree %s[%d] (%b)",
2337 if (bh->b_bdev != sb->s_bdev)
2338 reiserfs_panic(sb, "jmacd-4", "buffer has wrong "
2339 "device %s[%d] (%b)",
2342 if (bh->b_size != sb->s_blocksize)
2343 reiserfs_panic(sb, "jmacd-5", "buffer has wrong "
2344 "blocksize %s[%d] (%b)",
2347 if (bh->b_blocknr > SB_BLOCK_COUNT(sb))
2348 reiserfs_panic(sb, "jmacd-6", "buffer block "
2349 "number too high %s[%d] (%b)",
2354 static void tb_buffer_sanity_check(struct super_block *sb,
2355 struct buffer_head *bh,
2356 const char *descr, int level)
2361 static int clear_all_dirty_bits(struct super_block *s, struct buffer_head *bh)
2363 return reiserfs_prepare_for_journal(s, bh, 0);
2366 static int wait_tb_buffers_until_unlocked(struct tree_balance *tb)
2368 struct buffer_head *locked;
2369 #ifdef CONFIG_REISERFS_CHECK
2370 int repeat_counter = 0;
2378 for (i = tb->tb_path->path_length;
2379 !locked && i > ILLEGAL_PATH_ELEMENT_OFFSET; i--) {
2380 if (PATH_OFFSET_PBUFFER(tb->tb_path, i)) {
2382 * if I understand correctly, we can only
2383 * be sure the last buffer in the path is
2386 #ifdef CONFIG_REISERFS_CHECK
2387 if (PATH_PLAST_BUFFER(tb->tb_path) ==
2388 PATH_OFFSET_PBUFFER(tb->tb_path, i))
2389 tb_buffer_sanity_check(tb->tb_sb,
2396 if (!clear_all_dirty_bits(tb->tb_sb,
2401 PATH_OFFSET_PBUFFER(tb->tb_path,
2407 for (i = 0; !locked && i < MAX_HEIGHT && tb->insert_size[i];
2413 tb_buffer_sanity_check(tb->tb_sb,
2416 if (!clear_all_dirty_bits
2417 (tb->tb_sb, tb->L[i]))
2421 if (!locked && tb->FL[i]) {
2422 tb_buffer_sanity_check(tb->tb_sb,
2425 if (!clear_all_dirty_bits
2426 (tb->tb_sb, tb->FL[i]))
2430 if (!locked && tb->CFL[i]) {
2431 tb_buffer_sanity_check(tb->tb_sb,
2434 if (!clear_all_dirty_bits
2435 (tb->tb_sb, tb->CFL[i]))
2436 locked = tb->CFL[i];
2441 if (!locked && (tb->rnum[i])) {
2444 tb_buffer_sanity_check(tb->tb_sb,
2447 if (!clear_all_dirty_bits
2448 (tb->tb_sb, tb->R[i]))
2452 if (!locked && tb->FR[i]) {
2453 tb_buffer_sanity_check(tb->tb_sb,
2456 if (!clear_all_dirty_bits
2457 (tb->tb_sb, tb->FR[i]))
2461 if (!locked && tb->CFR[i]) {
2462 tb_buffer_sanity_check(tb->tb_sb,
2465 if (!clear_all_dirty_bits
2466 (tb->tb_sb, tb->CFR[i]))
2467 locked = tb->CFR[i];
2473 * as far as I can tell, this is not required. The FEB list
2474 * seems to be full of newly allocated nodes, which will
2475 * never be locked, dirty, or anything else.
2476 * To be safe, I'm putting in the checks and waits in.
2477 * For the moment, they are needed to keep the code in
2478 * journal.c from complaining about the buffer.
2479 * That code is inside CONFIG_REISERFS_CHECK as well. --clm
2481 for (i = 0; !locked && i < MAX_FEB_SIZE; i++) {
2483 if (!clear_all_dirty_bits
2484 (tb->tb_sb, tb->FEB[i]))
2485 locked = tb->FEB[i];
2491 #ifdef CONFIG_REISERFS_CHECK
2493 if ((repeat_counter % 10000) == 0) {
2494 reiserfs_warning(tb->tb_sb, "reiserfs-8200",
2495 "too many iterations waiting "
2496 "for buffer to unlock "
2499 /* Don't loop forever. Try to recover from possible error. */
2501 return (FILESYSTEM_CHANGED_TB(tb)) ?
2502 REPEAT_SEARCH : CARRY_ON;
2505 depth = reiserfs_write_unlock_nested(tb->tb_sb);
2506 __wait_on_buffer(locked);
2507 reiserfs_write_lock_nested(tb->tb_sb, depth);
2508 if (FILESYSTEM_CHANGED_TB(tb))
2509 return REPEAT_SEARCH;
2518 * Prepare for balancing, that is
2519 * get all necessary parents, and neighbors;
2520 * analyze what and where should be moved;
2521 * get sufficient number of new nodes;
2522 * Balancing will start only after all resources will be collected at a time.
2524 * When ported to SMP kernels, only at the last moment after all needed nodes
2525 * are collected in cache, will the resources be locked using the usual
2526 * textbook ordered lock acquisition algorithms. Note that ensuring that
2527 * this code neither write locks what it does not need to write lock nor locks
2528 * out of order will be a pain in the butt that could have been avoided.
2529 * Grumble grumble. -Hans
2531 * fix is meant in the sense of render unchanging
2533 * Latency might be improved by first gathering a list of what buffers
2534 * are needed and then getting as many of them in parallel as possible? -Hans
2537 * op_mode i - insert, d - delete, c - cut (truncate), p - paste (append)
2538 * tb tree_balance structure;
2539 * inum item number in S[h];
2540 * pos_in_item - comment this if you can
2541 * ins_ih item head of item being inserted
2542 * data inserted item or data to be pasted
2543 * Returns: 1 - schedule occurred while the function worked;
2544 * 0 - schedule didn't occur while the function worked;
2545 * -1 - if no_disk_space
2548 int fix_nodes(int op_mode, struct tree_balance *tb,
2549 struct item_head *ins_ih, const void *data)
2551 int ret, h, item_num = PATH_LAST_POSITION(tb->tb_path);
2555 * we set wait_tb_buffers_run when we have to restore any dirty
2556 * bits cleared during wait_tb_buffers_run
2558 int wait_tb_buffers_run = 0;
2559 struct buffer_head *tbS0 = PATH_PLAST_BUFFER(tb->tb_path);
2561 ++REISERFS_SB(tb->tb_sb)->s_fix_nodes;
2563 pos_in_item = tb->tb_path->pos_in_item;
2565 tb->fs_gen = get_generation(tb->tb_sb);
2568 * we prepare and log the super here so it will already be in the
2569 * transaction when do_balance needs to change it.
2570 * This way do_balance won't have to schedule when trying to prepare
2571 * the super for logging
2573 reiserfs_prepare_for_journal(tb->tb_sb,
2574 SB_BUFFER_WITH_SB(tb->tb_sb), 1);
2575 journal_mark_dirty(tb->transaction_handle, tb->tb_sb,
2576 SB_BUFFER_WITH_SB(tb->tb_sb));
2577 if (FILESYSTEM_CHANGED_TB(tb))
2578 return REPEAT_SEARCH;
2580 /* if it possible in indirect_to_direct conversion */
2581 if (buffer_locked(tbS0)) {
2582 int depth = reiserfs_write_unlock_nested(tb->tb_sb);
2583 __wait_on_buffer(tbS0);
2584 reiserfs_write_lock_nested(tb->tb_sb, depth);
2585 if (FILESYSTEM_CHANGED_TB(tb))
2586 return REPEAT_SEARCH;
2588 #ifdef CONFIG_REISERFS_CHECK
2589 if (REISERFS_SB(tb->tb_sb)->cur_tb) {
2590 print_cur_tb("fix_nodes");
2591 reiserfs_panic(tb->tb_sb, "PAP-8305",
2592 "there is pending do_balance");
2595 if (!buffer_uptodate(tbS0) || !B_IS_IN_TREE(tbS0))
2596 reiserfs_panic(tb->tb_sb, "PAP-8320", "S[0] (%b %z) is "
2597 "not uptodate at the beginning of fix_nodes "
2598 "or not in tree (mode %c)",
2599 tbS0, tbS0, op_mode);
2601 /* Check parameters. */
2604 if (item_num <= 0 || item_num > B_NR_ITEMS(tbS0))
2605 reiserfs_panic(tb->tb_sb, "PAP-8330", "Incorrect "
2606 "item number %d (in S0 - %d) in case "
2607 "of insert", item_num,
2613 if (item_num < 0 || item_num >= B_NR_ITEMS(tbS0)) {
2614 print_block(tbS0, 0, -1, -1);
2615 reiserfs_panic(tb->tb_sb, "PAP-8335", "Incorrect "
2616 "item number(%d); mode = %c "
2619 tb->insert_size[0]);
2623 reiserfs_panic(tb->tb_sb, "PAP-8340", "Incorrect mode "
2628 if (get_mem_for_virtual_node(tb) == REPEAT_SEARCH)
2629 /* FIXME: maybe -ENOMEM when tb->vn_buf == 0? Now just repeat */
2630 return REPEAT_SEARCH;
2632 /* Starting from the leaf level; for all levels h of the tree. */
2633 for (h = 0; h < MAX_HEIGHT && tb->insert_size[h]; h++) {
2634 ret = get_direct_parent(tb, h);
2635 if (ret != CARRY_ON)
2638 ret = check_balance(op_mode, tb, h, item_num,
2639 pos_in_item, ins_ih, data);
2640 if (ret != CARRY_ON) {
2641 if (ret == NO_BALANCING_NEEDED) {
2642 /* No balancing for higher levels needed. */
2643 ret = get_neighbors(tb, h);
2644 if (ret != CARRY_ON)
2646 if (h != MAX_HEIGHT - 1)
2647 tb->insert_size[h + 1] = 0;
2649 * ok, analysis and resource gathering
2657 ret = get_neighbors(tb, h);
2658 if (ret != CARRY_ON)
2662 * No disk space, or schedule occurred and analysis may be
2663 * invalid and needs to be redone.
2665 ret = get_empty_nodes(tb, h);
2666 if (ret != CARRY_ON)
2670 * We have a positive insert size but no nodes exist on this
2671 * level, this means that we are creating a new root.
2673 if (!PATH_H_PBUFFER(tb->tb_path, h)) {
2675 RFALSE(tb->blknum[h] != 1,
2676 "PAP-8350: creating new empty root");
2678 if (h < MAX_HEIGHT - 1)
2679 tb->insert_size[h + 1] = 0;
2680 } else if (!PATH_H_PBUFFER(tb->tb_path, h + 1)) {
2682 * The tree needs to be grown, so this node S[h]
2683 * which is the root node is split into two nodes,
2684 * and a new node (S[h+1]) will be created to
2685 * become the root node.
2687 if (tb->blknum[h] > 1) {
2689 RFALSE(h == MAX_HEIGHT - 1,
2690 "PAP-8355: attempt to create too high of a tree");
2692 tb->insert_size[h + 1] =
2694 KEY_SIZE) * (tb->blknum[h] - 1) +
2696 } else if (h < MAX_HEIGHT - 1)
2697 tb->insert_size[h + 1] = 0;
2699 tb->insert_size[h + 1] =
2700 (DC_SIZE + KEY_SIZE) * (tb->blknum[h] - 1);
2703 ret = wait_tb_buffers_until_unlocked(tb);
2704 if (ret == CARRY_ON) {
2705 if (FILESYSTEM_CHANGED_TB(tb)) {
2706 wait_tb_buffers_run = 1;
2707 ret = REPEAT_SEARCH;
2713 wait_tb_buffers_run = 1;
2719 * fix_nodes was unable to perform its calculation due to
2720 * filesystem got changed under us, lack of free disk space or i/o
2721 * failure. If the first is the case - the search will be
2722 * repeated. For now - free all resources acquired so far except
2723 * for the new allocated nodes
2728 /* Release path buffers. */
2729 if (wait_tb_buffers_run) {
2730 pathrelse_and_restore(tb->tb_sb, tb->tb_path);
2732 pathrelse(tb->tb_path);
2734 /* brelse all resources collected for balancing */
2735 for (i = 0; i < MAX_HEIGHT; i++) {
2736 if (wait_tb_buffers_run) {
2737 reiserfs_restore_prepared_buffer(tb->tb_sb,
2739 reiserfs_restore_prepared_buffer(tb->tb_sb,
2741 reiserfs_restore_prepared_buffer(tb->tb_sb,
2743 reiserfs_restore_prepared_buffer(tb->tb_sb,
2745 reiserfs_restore_prepared_buffer(tb->tb_sb,
2748 reiserfs_restore_prepared_buffer(tb->tb_sb,
2768 if (wait_tb_buffers_run) {
2769 for (i = 0; i < MAX_FEB_SIZE; i++) {
2771 reiserfs_restore_prepared_buffer
2772 (tb->tb_sb, tb->FEB[i]);
2780 void unfix_nodes(struct tree_balance *tb)
2784 /* Release path buffers. */
2785 pathrelse_and_restore(tb->tb_sb, tb->tb_path);
2787 /* brelse all resources collected for balancing */
2788 for (i = 0; i < MAX_HEIGHT; i++) {
2789 reiserfs_restore_prepared_buffer(tb->tb_sb, tb->L[i]);
2790 reiserfs_restore_prepared_buffer(tb->tb_sb, tb->R[i]);
2791 reiserfs_restore_prepared_buffer(tb->tb_sb, tb->FL[i]);
2792 reiserfs_restore_prepared_buffer(tb->tb_sb, tb->FR[i]);
2793 reiserfs_restore_prepared_buffer(tb->tb_sb, tb->CFL[i]);
2794 reiserfs_restore_prepared_buffer(tb->tb_sb, tb->CFR[i]);
2804 /* deal with list of allocated (used and unused) nodes */
2805 for (i = 0; i < MAX_FEB_SIZE; i++) {
2807 b_blocknr_t blocknr = tb->FEB[i]->b_blocknr;
2809 * de-allocated block which was not used by
2810 * balancing and bforget about buffer for it
2813 reiserfs_free_block(tb->transaction_handle, NULL,
2817 /* release used as new nodes including a new root */
2818 brelse(tb->used[i]);