2 * Copyright 2000 by Hans Reiser, licensing governed by reiserfs/README
12 ** directory_part_size
16 ** are_leaves_removable
20 ** is_left_neighbor_in_cache
24 ** can_node_be_removed
26 ** dc_check_balance_internal
27 ** dc_check_balance_leaf
37 #include <linux/time.h>
38 #include <linux/string.h>
39 #include <linux/reiserfs_fs.h>
40 #include <linux/buffer_head.h>
42 /* To make any changes in the tree we find a node, that contains item
43 to be changed/deleted or position in the node we insert a new item
44 to. We call this node S. To do balancing we need to decide what we
45 will shift to left/right neighbor, or to a new node, where new item
46 will be etc. To make this analysis simpler we build virtual
47 node. Virtual node is an array of items, that will replace items of
48 node S. (For instance if we are going to delete an item, virtual
49 node does not contain it). Virtual node keeps information about
50 item sizes and types, mergeability of first and last items, sizes
51 of all entries in directory item. We use this array of items when
52 calculating what we can shift to neighbors and how many nodes we
53 have to have if we do not any shiftings, if we shift to left/right
54 neighbor or to both. */
56 /* taking item number in virtual node, returns number of item, that it has in source buffer */
57 static inline int old_item_num(int new_num
, int affected_item_num
, int mode
)
59 if (mode
== M_PASTE
|| mode
== M_CUT
|| new_num
< affected_item_num
)
62 if (mode
== M_INSERT
) {
65 "vs-8005: for INSERT mode and item number of inserted item");
70 RFALSE(mode
!= M_DELETE
,
71 "vs-8010: old_item_num: mode must be M_DELETE (mode = \'%c\'",
77 static void create_virtual_node(struct tree_balance
*tb
, int h
)
80 struct virtual_node
*vn
= tb
->tb_vn
;
82 struct buffer_head
*Sh
; /* this comes from tb->S[h] */
84 Sh
= PATH_H_PBUFFER(tb
->tb_path
, h
);
86 /* size of changed node */
88 MAX_CHILD_SIZE(Sh
) - B_FREE_SPACE(Sh
) + tb
->insert_size
[h
];
90 /* for internal nodes array if virtual items is not created */
92 vn
->vn_nr_item
= (vn
->vn_size
- DC_SIZE
) / (DC_SIZE
+ KEY_SIZE
);
96 /* number of items in virtual node */
98 B_NR_ITEMS(Sh
) + ((vn
->vn_mode
== M_INSERT
) ? 1 : 0) -
99 ((vn
->vn_mode
== M_DELETE
) ? 1 : 0);
101 /* first virtual item */
102 vn
->vn_vi
= (struct virtual_item
*)(tb
->tb_vn
+ 1);
103 memset(vn
->vn_vi
, 0, vn
->vn_nr_item
* sizeof(struct virtual_item
));
104 vn
->vn_free_ptr
+= vn
->vn_nr_item
* sizeof(struct virtual_item
);
106 /* first item in the node */
107 ih
= B_N_PITEM_HEAD(Sh
, 0);
109 /* define the mergeability for 0-th item (if it is not being deleted) */
110 if (op_is_left_mergeable(&(ih
->ih_key
), Sh
->b_size
)
111 && (vn
->vn_mode
!= M_DELETE
|| vn
->vn_affected_item_num
))
112 vn
->vn_vi
[0].vi_type
|= VI_TYPE_LEFT_MERGEABLE
;
114 /* go through all items those remain in the virtual node (except for the new (inserted) one) */
115 for (new_num
= 0; new_num
< vn
->vn_nr_item
; new_num
++) {
117 struct virtual_item
*vi
= vn
->vn_vi
+ new_num
;
119 ((new_num
!= vn
->vn_affected_item_num
) ? 0 : 1);
121 if (is_affected
&& vn
->vn_mode
== M_INSERT
)
124 /* get item number in source node */
125 j
= old_item_num(new_num
, vn
->vn_affected_item_num
,
128 vi
->vi_item_len
+= ih_item_len(ih
+ j
) + IH_SIZE
;
130 vi
->vi_item
= B_I_PITEM(Sh
, ih
+ j
);
131 vi
->vi_uarea
= vn
->vn_free_ptr
;
133 // FIXME: there is no check, that item operation did not
134 // consume too much memory
136 op_create_vi(vn
, vi
, is_affected
, tb
->insert_size
[0]);
137 if (tb
->vn_buf
+ tb
->vn_buf_size
< vn
->vn_free_ptr
)
138 reiserfs_panic(tb
->tb_sb
, "vs-8030",
139 "virtual node space consumed");
142 /* this is not being changed */
145 if (vn
->vn_mode
== M_PASTE
|| vn
->vn_mode
== M_CUT
) {
146 vn
->vn_vi
[new_num
].vi_item_len
+= tb
->insert_size
[0];
147 vi
->vi_new_data
= vn
->vn_data
; // pointer to data which is going to be pasted
151 /* virtual inserted item is not defined yet */
152 if (vn
->vn_mode
== M_INSERT
) {
153 struct virtual_item
*vi
= vn
->vn_vi
+ vn
->vn_affected_item_num
;
155 RFALSE(vn
->vn_ins_ih
== NULL
,
156 "vs-8040: item header of inserted item is not specified");
157 vi
->vi_item_len
= tb
->insert_size
[0];
158 vi
->vi_ih
= vn
->vn_ins_ih
;
159 vi
->vi_item
= vn
->vn_data
;
160 vi
->vi_uarea
= vn
->vn_free_ptr
;
162 op_create_vi(vn
, vi
, 0 /*not pasted or cut */ ,
166 /* set right merge flag we take right delimiting key and check whether it is a mergeable item */
168 struct reiserfs_key
*key
;
170 key
= B_N_PDELIM_KEY(tb
->CFR
[0], tb
->rkey
[0]);
171 if (op_is_left_mergeable(key
, Sh
->b_size
)
172 && (vn
->vn_mode
!= M_DELETE
173 || vn
->vn_affected_item_num
!= B_NR_ITEMS(Sh
) - 1))
174 vn
->vn_vi
[vn
->vn_nr_item
- 1].vi_type
|=
175 VI_TYPE_RIGHT_MERGEABLE
;
177 #ifdef CONFIG_REISERFS_CHECK
178 if (op_is_left_mergeable(key
, Sh
->b_size
) &&
179 !(vn
->vn_mode
!= M_DELETE
180 || vn
->vn_affected_item_num
!= B_NR_ITEMS(Sh
) - 1)) {
181 /* we delete last item and it could be merged with right neighbor's first item */
184 && is_direntry_le_ih(B_N_PITEM_HEAD(Sh
, 0))
185 && I_ENTRY_COUNT(B_N_PITEM_HEAD(Sh
, 0)) == 1)) {
186 /* node contains more than 1 item, or item is not directory item, or this item contains more than 1 entry */
187 print_block(Sh
, 0, -1, -1);
188 reiserfs_panic(tb
->tb_sb
, "vs-8045",
189 "rdkey %k, affected item==%d "
190 "(mode==%c) Must be %c",
191 key
, vn
->vn_affected_item_num
,
192 vn
->vn_mode
, M_DELETE
);
200 /* using virtual node check, how many items can be shifted to left
202 static void check_left(struct tree_balance
*tb
, int h
, int cur_free
)
205 struct virtual_node
*vn
= tb
->tb_vn
;
206 struct virtual_item
*vi
;
209 RFALSE(cur_free
< 0, "vs-8050: cur_free (%d) < 0", cur_free
);
213 tb
->lnum
[h
] = cur_free
/ (DC_SIZE
+ KEY_SIZE
);
219 if (!cur_free
|| !vn
->vn_nr_item
) {
220 /* no free space or nothing to move */
226 RFALSE(!PATH_H_PPARENT(tb
->tb_path
, 0),
227 "vs-8055: parent does not exist or invalid");
230 if ((unsigned int)cur_free
>=
232 ((vi
->vi_type
& VI_TYPE_LEFT_MERGEABLE
) ? IH_SIZE
: 0))) {
233 /* all contents of S[0] fits into L[0] */
235 RFALSE(vn
->vn_mode
== M_INSERT
|| vn
->vn_mode
== M_PASTE
,
236 "vs-8055: invalid mode or balance condition failed");
238 tb
->lnum
[0] = vn
->vn_nr_item
;
243 d_size
= 0, ih_size
= IH_SIZE
;
245 /* first item may be merge with last item in left neighbor */
246 if (vi
->vi_type
& VI_TYPE_LEFT_MERGEABLE
)
247 d_size
= -((int)IH_SIZE
), ih_size
= 0;
250 for (i
= 0; i
< vn
->vn_nr_item
;
251 i
++, ih_size
= IH_SIZE
, d_size
= 0, vi
++) {
252 d_size
+= vi
->vi_item_len
;
253 if (cur_free
>= d_size
) {
254 /* the item can be shifted entirely */
260 /* the item cannot be shifted entirely, try to split it */
261 /* check whether L[0] can hold ih and at least one byte of the item body */
262 if (cur_free
<= ih_size
) {
263 /* cannot shift even a part of the current item */
269 tb
->lbytes
= op_check_left(vi
, cur_free
, 0, 0);
270 if (tb
->lbytes
!= -1)
271 /* count partially shifted item */
280 /* using virtual node check, how many items can be shifted to right
282 static void check_right(struct tree_balance
*tb
, int h
, int cur_free
)
285 struct virtual_node
*vn
= tb
->tb_vn
;
286 struct virtual_item
*vi
;
289 RFALSE(cur_free
< 0, "vs-8070: cur_free < 0");
293 tb
->rnum
[h
] = cur_free
/ (DC_SIZE
+ KEY_SIZE
);
299 if (!cur_free
|| !vn
->vn_nr_item
) {
306 RFALSE(!PATH_H_PPARENT(tb
->tb_path
, 0),
307 "vs-8075: parent does not exist or invalid");
309 vi
= vn
->vn_vi
+ vn
->vn_nr_item
- 1;
310 if ((unsigned int)cur_free
>=
312 ((vi
->vi_type
& VI_TYPE_RIGHT_MERGEABLE
) ? IH_SIZE
: 0))) {
313 /* all contents of S[0] fits into R[0] */
315 RFALSE(vn
->vn_mode
== M_INSERT
|| vn
->vn_mode
== M_PASTE
,
316 "vs-8080: invalid mode or balance condition failed");
318 tb
->rnum
[h
] = vn
->vn_nr_item
;
323 d_size
= 0, ih_size
= IH_SIZE
;
325 /* last item may be merge with first item in right neighbor */
326 if (vi
->vi_type
& VI_TYPE_RIGHT_MERGEABLE
)
327 d_size
= -(int)IH_SIZE
, ih_size
= 0;
330 for (i
= vn
->vn_nr_item
- 1; i
>= 0;
331 i
--, d_size
= 0, ih_size
= IH_SIZE
, vi
--) {
332 d_size
+= vi
->vi_item_len
;
333 if (cur_free
>= d_size
) {
334 /* the item can be shifted entirely */
340 /* check whether R[0] can hold ih and at least one byte of the item body */
341 if (cur_free
<= ih_size
) { /* cannot shift even a part of the current item */
346 /* R[0] can hold the header of the item and at least one byte of its body */
347 cur_free
-= ih_size
; /* cur_free is still > 0 */
349 tb
->rbytes
= op_check_right(vi
, cur_free
);
350 if (tb
->rbytes
!= -1)
351 /* count partially shifted item */
361 * from - number of items, which are shifted to left neighbor entirely
362 * to - number of item, which are shifted to right neighbor entirely
363 * from_bytes - number of bytes of boundary item (or directory entries) which are shifted to left neighbor
364 * to_bytes - number of bytes of boundary item (or directory entries) which are shifted to right neighbor */
365 static int get_num_ver(int mode
, struct tree_balance
*tb
, int h
,
366 int from
, int from_bytes
,
367 int to
, int to_bytes
, short *snum012
, int flow
)
373 struct virtual_node
*vn
= tb
->tb_vn
;
374 // struct virtual_item * vi;
376 int total_node_size
, max_node_size
, current_item_size
;
378 int start_item
, /* position of item we start filling node from */
379 end_item
, /* position of item we finish filling node by */
380 start_bytes
, /* number of first bytes (entries for directory) of start_item-th item
381 we do not include into node that is being filled */
382 end_bytes
; /* number of last bytes (entries for directory) of end_item-th item
383 we do node include into node that is being filled */
384 int split_item_positions
[2]; /* these are positions in virtual item of
385 items, that are split between S[0] and
386 S1new and S1new and S2new */
388 split_item_positions
[0] = -1;
389 split_item_positions
[1] = -1;
391 /* We only create additional nodes if we are in insert or paste mode
392 or we are in replace mode at the internal level. If h is 0 and
393 the mode is M_REPLACE then in fix_nodes we change the mode to
394 paste or insert before we get here in the code. */
395 RFALSE(tb
->insert_size
[h
] < 0 || (mode
!= M_INSERT
&& mode
!= M_PASTE
),
396 "vs-8100: insert_size < 0 in overflow");
398 max_node_size
= MAX_CHILD_SIZE(PATH_H_PBUFFER(tb
->tb_path
, h
));
400 /* snum012 [0-2] - number of items, that lay
401 to S[0], first new node and second new node */
402 snum012
[3] = -1; /* s1bytes */
403 snum012
[4] = -1; /* s2bytes */
407 i
= ((to
- from
) * (KEY_SIZE
+ DC_SIZE
) + DC_SIZE
);
408 if (i
== max_node_size
)
410 return (i
/ max_node_size
+ 1);
416 cur_free
= max_node_size
;
418 // start from 'from'-th item
420 // skip its first 'start_bytes' units
421 start_bytes
= ((from_bytes
!= -1) ? from_bytes
: 0);
423 // last included item is the 'end_item'-th one
424 end_item
= vn
->vn_nr_item
- to
- 1;
425 // do not count last 'end_bytes' units of 'end_item'-th item
426 end_bytes
= (to_bytes
!= -1) ? to_bytes
: 0;
428 /* go through all item beginning from the start_item-th item and ending by
429 the end_item-th item. Do not count first 'start_bytes' units of
430 'start_item'-th item and last 'end_bytes' of 'end_item'-th item */
432 for (i
= start_item
; i
<= end_item
; i
++) {
433 struct virtual_item
*vi
= vn
->vn_vi
+ i
;
434 int skip_from_end
= ((i
== end_item
) ? end_bytes
: 0);
436 RFALSE(needed_nodes
> 3, "vs-8105: too many nodes are needed");
438 /* get size of current item */
439 current_item_size
= vi
->vi_item_len
;
441 /* do not take in calculation head part (from_bytes) of from-th item */
443 op_part_size(vi
, 0 /*from start */ , start_bytes
);
445 /* do not take in calculation tail part of last item */
447 op_part_size(vi
, 1 /*from end */ , skip_from_end
);
449 /* if item fits into current node entierly */
450 if (total_node_size
+ current_item_size
<= max_node_size
) {
451 snum012
[needed_nodes
- 1]++;
452 total_node_size
+= current_item_size
;
457 if (current_item_size
> max_node_size
) {
458 /* virtual item length is longer, than max size of item in
459 a node. It is impossible for direct item */
460 RFALSE(is_direct_le_ih(vi
->vi_ih
),
462 "direct item length is %d. It can not be longer than %d",
463 current_item_size
, max_node_size
);
464 /* we will try to split it */
469 /* as we do not split items, take new node and continue */
475 // calculate number of item units which fit into node being
480 free_space
= max_node_size
- total_node_size
- IH_SIZE
;
482 op_check_left(vi
, free_space
, start_bytes
,
485 /* nothing fits into current node, take new node and continue */
486 needed_nodes
++, i
--, total_node_size
= 0;
491 /* something fits into the current node */
492 //if (snum012[3] != -1 || needed_nodes != 1)
493 // reiserfs_panic (tb->tb_sb, "vs-8115: get_num_ver: too many nodes required");
494 //snum012[needed_nodes - 1 + 3] = op_unit_num (vi) - start_bytes - units;
495 start_bytes
+= units
;
496 snum012
[needed_nodes
- 1 + 3] = units
;
498 if (needed_nodes
> 2)
499 reiserfs_warning(tb
->tb_sb
, "vs-8111",
500 "split_item_position is out of range");
501 snum012
[needed_nodes
- 1]++;
502 split_item_positions
[needed_nodes
- 1] = i
;
504 /* continue from the same item with start_bytes != -1 */
510 // sum012[4] (if it is not -1) contains number of units of which
511 // are to be in S1new, snum012[3] - to be in S0. They are supposed
512 // to be S1bytes and S2bytes correspondingly, so recalculate
513 if (snum012
[4] > 0) {
515 int bytes_to_r
, bytes_to_l
;
518 split_item_num
= split_item_positions
[1];
520 ((from
== split_item_num
521 && from_bytes
!= -1) ? from_bytes
: 0);
523 ((end_item
== split_item_num
524 && end_bytes
!= -1) ? end_bytes
: 0);
526 ((split_item_positions
[0] ==
527 split_item_positions
[1]) ? snum012
[3] : 0);
531 op_unit_num(&vn
->vn_vi
[split_item_num
]) - snum012
[4] -
532 bytes_to_r
- bytes_to_l
- bytes_to_S1new
;
534 if (vn
->vn_vi
[split_item_num
].vi_index
!= TYPE_DIRENTRY
&&
535 vn
->vn_vi
[split_item_num
].vi_index
!= TYPE_INDIRECT
)
536 reiserfs_warning(tb
->tb_sb
, "vs-8115",
537 "not directory or indirect item");
540 /* now we know S2bytes, calculate S1bytes */
541 if (snum012
[3] > 0) {
543 int bytes_to_r
, bytes_to_l
;
546 split_item_num
= split_item_positions
[0];
548 ((from
== split_item_num
549 && from_bytes
!= -1) ? from_bytes
: 0);
551 ((end_item
== split_item_num
552 && end_bytes
!= -1) ? end_bytes
: 0);
554 ((split_item_positions
[0] == split_item_positions
[1]
555 && snum012
[4] != -1) ? snum012
[4] : 0);
559 op_unit_num(&vn
->vn_vi
[split_item_num
]) - snum012
[3] -
560 bytes_to_r
- bytes_to_l
- bytes_to_S2new
;
566 #ifdef CONFIG_REISERFS_CHECK
567 extern struct tree_balance
*cur_tb
;
570 /* Set parameters for balancing.
571 * Performs write of results of analysis of balancing into structure tb,
572 * where it will later be used by the functions that actually do the balancing.
574 * tb tree_balance structure;
575 * h current level of the node;
576 * lnum number of items from S[h] that must be shifted to L[h];
577 * rnum number of items from S[h] that must be shifted to R[h];
578 * blk_num number of blocks that S[h] will be splitted into;
579 * s012 number of items that fall into splitted nodes.
580 * lbytes number of bytes which flow to the left neighbor from the item that is not
581 * not shifted entirely
582 * rbytes number of bytes which flow to the right neighbor from the item that is not
583 * not shifted entirely
584 * s1bytes number of bytes which flow to the first new node when S[0] splits (this number is contained in s012 array)
587 static void set_parameters(struct tree_balance
*tb
, int h
, int lnum
,
588 int rnum
, int blk_num
, short *s012
, int lb
, int rb
)
593 tb
->blknum
[h
] = blk_num
;
595 if (h
== 0) { /* only for leaf level */
598 tb
->s1num
= *s012
++, tb
->s2num
= *s012
++;
599 tb
->s1bytes
= *s012
++;
605 PROC_INFO_ADD(tb
->tb_sb
, lnum
[h
], lnum
);
606 PROC_INFO_ADD(tb
->tb_sb
, rnum
[h
], rnum
);
608 PROC_INFO_ADD(tb
->tb_sb
, lbytes
[h
], lb
);
609 PROC_INFO_ADD(tb
->tb_sb
, rbytes
[h
], rb
);
612 /* check, does node disappear if we shift tb->lnum[0] items to left
613 neighbor and tb->rnum[0] to the right one. */
614 static int is_leaf_removable(struct tree_balance
*tb
)
616 struct virtual_node
*vn
= tb
->tb_vn
;
617 int to_left
, to_right
;
621 /* number of items, that will be shifted to left (right) neighbor
623 to_left
= tb
->lnum
[0] - ((tb
->lbytes
!= -1) ? 1 : 0);
624 to_right
= tb
->rnum
[0] - ((tb
->rbytes
!= -1) ? 1 : 0);
625 remain_items
= vn
->vn_nr_item
;
627 /* how many items remain in S[0] after shiftings to neighbors */
628 remain_items
-= (to_left
+ to_right
);
630 if (remain_items
< 1) {
631 /* all content of node can be shifted to neighbors */
632 set_parameters(tb
, 0, to_left
, vn
->vn_nr_item
- to_left
, 0,
637 if (remain_items
> 1 || tb
->lbytes
== -1 || tb
->rbytes
== -1)
638 /* S[0] is not removable */
641 /* check, whether we can divide 1 remaining item between neighbors */
643 /* get size of remaining item (in item units) */
644 size
= op_unit_num(&(vn
->vn_vi
[to_left
]));
646 if (tb
->lbytes
+ tb
->rbytes
>= size
) {
647 set_parameters(tb
, 0, to_left
+ 1, to_right
+ 1, 0, NULL
,
655 /* check whether L, S, R can be joined in one node */
656 static int are_leaves_removable(struct tree_balance
*tb
, int lfree
, int rfree
)
658 struct virtual_node
*vn
= tb
->tb_vn
;
660 struct buffer_head
*S0
;
662 S0
= PATH_H_PBUFFER(tb
->tb_path
, 0);
665 if (vn
->vn_nr_item
) {
666 if (vn
->vn_vi
[0].vi_type
& VI_TYPE_LEFT_MERGEABLE
)
669 if (vn
->vn_vi
[vn
->vn_nr_item
- 1].
670 vi_type
& VI_TYPE_RIGHT_MERGEABLE
)
673 /* there was only one item and it will be deleted */
674 struct item_head
*ih
;
676 RFALSE(B_NR_ITEMS(S0
) != 1,
677 "vs-8125: item number must be 1: it is %d",
680 ih
= B_N_PITEM_HEAD(S0
, 0);
682 && !comp_short_le_keys(&(ih
->ih_key
),
683 B_N_PDELIM_KEY(tb
->CFR
[0],
685 if (is_direntry_le_ih(ih
)) {
686 /* Directory must be in correct state here: that is
687 somewhere at the left side should exist first directory
688 item. But the item being deleted can not be that first
689 one because its right neighbor is item of the same
690 directory. (But first item always gets deleted in last
691 turn). So, neighbors of deleted item can be merged, so
692 we can save ih_size */
695 /* we might check that left neighbor exists and is of the
697 RFALSE(le_ih_k_offset(ih
) == DOT_OFFSET
,
698 "vs-8130: first directory item can not be removed until directory is not empty");
703 if (MAX_CHILD_SIZE(S0
) + vn
->vn_size
<= rfree
+ lfree
+ ih_size
) {
704 set_parameters(tb
, 0, -1, -1, -1, NULL
, -1, -1);
705 PROC_INFO_INC(tb
->tb_sb
, leaves_removable
);
712 /* when we do not split item, lnum and rnum are numbers of entire items */
713 #define SET_PAR_SHIFT_LEFT \
718 to_l = (MAX_NR_KEY(Sh)+1 - lpar + vn->vn_nr_item + 1) / 2 -\
719 (MAX_NR_KEY(Sh) + 1 - lpar);\
721 set_parameters (tb, h, to_l, 0, lnver, NULL, -1, -1);\
725 if (lset==LEFT_SHIFT_FLOW)\
726 set_parameters (tb, h, lpar, 0, lnver, snum012+lset,\
729 set_parameters (tb, h, lpar - (tb->lbytes!=-1), 0, lnver, snum012+lset,\
733 #define SET_PAR_SHIFT_RIGHT \
738 to_r = (MAX_NR_KEY(Sh)+1 - rpar + vn->vn_nr_item + 1) / 2 - (MAX_NR_KEY(Sh) + 1 - rpar);\
740 set_parameters (tb, h, 0, to_r, rnver, NULL, -1, -1);\
744 if (rset==RIGHT_SHIFT_FLOW)\
745 set_parameters (tb, h, 0, rpar, rnver, snum012+rset,\
748 set_parameters (tb, h, 0, rpar - (tb->rbytes!=-1), rnver, snum012+rset,\
752 static void free_buffers_in_tb(struct tree_balance
*p_s_tb
)
756 decrement_counters_in_path(p_s_tb
->tb_path
);
758 for (n_counter
= 0; n_counter
< MAX_HEIGHT
; n_counter
++) {
759 decrement_bcount(p_s_tb
->L
[n_counter
]);
760 p_s_tb
->L
[n_counter
] = NULL
;
761 decrement_bcount(p_s_tb
->R
[n_counter
]);
762 p_s_tb
->R
[n_counter
] = NULL
;
763 decrement_bcount(p_s_tb
->FL
[n_counter
]);
764 p_s_tb
->FL
[n_counter
] = NULL
;
765 decrement_bcount(p_s_tb
->FR
[n_counter
]);
766 p_s_tb
->FR
[n_counter
] = NULL
;
767 decrement_bcount(p_s_tb
->CFL
[n_counter
]);
768 p_s_tb
->CFL
[n_counter
] = NULL
;
769 decrement_bcount(p_s_tb
->CFR
[n_counter
]);
770 p_s_tb
->CFR
[n_counter
] = NULL
;
774 /* Get new buffers for storing new nodes that are created while balancing.
775 * Returns: SCHEDULE_OCCURRED - schedule occurred while the function worked;
776 * CARRY_ON - schedule didn't occur while the function worked;
777 * NO_DISK_SPACE - no disk space.
779 /* The function is NOT SCHEDULE-SAFE! */
780 static int get_empty_nodes(struct tree_balance
*p_s_tb
, int n_h
)
782 struct buffer_head
*p_s_new_bh
,
783 *p_s_Sh
= PATH_H_PBUFFER(p_s_tb
->tb_path
, n_h
);
784 b_blocknr_t
*p_n_blocknr
, a_n_blocknrs
[MAX_AMOUNT_NEEDED
] = { 0, };
785 int n_counter
, n_number_of_freeblk
, n_amount_needed
, /* number of needed empty blocks */
787 struct super_block
*p_s_sb
= p_s_tb
->tb_sb
;
789 /* number_of_freeblk is the number of empty blocks which have been
790 acquired for use by the balancing algorithm minus the number of
791 empty blocks used in the previous levels of the analysis,
792 number_of_freeblk = tb->cur_blknum can be non-zero if a schedule occurs
793 after empty blocks are acquired, and the balancing analysis is
794 then restarted, amount_needed is the number needed by this level
795 (n_h) of the balancing analysis.
797 Note that for systems with many processes writing, it would be
798 more layout optimal to calculate the total number needed by all
799 levels and then to run reiserfs_new_blocks to get all of them at once. */
801 /* Initiate number_of_freeblk to the amount acquired prior to the restart of
802 the analysis or 0 if not restarted, then subtract the amount needed
803 by all of the levels of the tree below n_h. */
804 /* blknum includes S[n_h], so we subtract 1 in this calculation */
805 for (n_counter
= 0, n_number_of_freeblk
= p_s_tb
->cur_blknum
;
806 n_counter
< n_h
; n_counter
++)
807 n_number_of_freeblk
-=
808 (p_s_tb
->blknum
[n_counter
]) ? (p_s_tb
->blknum
[n_counter
] -
811 /* Allocate missing empty blocks. */
812 /* if p_s_Sh == 0 then we are getting a new root */
813 n_amount_needed
= (p_s_Sh
) ? (p_s_tb
->blknum
[n_h
] - 1) : 1;
814 /* Amount_needed = the amount that we need more than the amount that we have. */
815 if (n_amount_needed
> n_number_of_freeblk
)
816 n_amount_needed
-= n_number_of_freeblk
;
817 else /* If we have enough already then there is nothing to do. */
820 /* No need to check quota - is not allocated for blocks used for formatted nodes */
821 if (reiserfs_new_form_blocknrs(p_s_tb
, a_n_blocknrs
,
822 n_amount_needed
) == NO_DISK_SPACE
)
823 return NO_DISK_SPACE
;
825 /* for each blocknumber we just got, get a buffer and stick it on FEB */
826 for (p_n_blocknr
= a_n_blocknrs
, n_counter
= 0;
827 n_counter
< n_amount_needed
; p_n_blocknr
++, n_counter
++) {
829 RFALSE(!*p_n_blocknr
,
830 "PAP-8135: reiserfs_new_blocknrs failed when got new blocks");
832 p_s_new_bh
= sb_getblk(p_s_sb
, *p_n_blocknr
);
833 RFALSE(buffer_dirty(p_s_new_bh
) ||
834 buffer_journaled(p_s_new_bh
) ||
835 buffer_journal_dirty(p_s_new_bh
),
836 "PAP-8140: journlaled or dirty buffer %b for the new block",
839 /* Put empty buffers into the array. */
840 RFALSE(p_s_tb
->FEB
[p_s_tb
->cur_blknum
],
841 "PAP-8141: busy slot for new buffer");
843 set_buffer_journal_new(p_s_new_bh
);
844 p_s_tb
->FEB
[p_s_tb
->cur_blknum
++] = p_s_new_bh
;
847 if (n_retval
== CARRY_ON
&& FILESYSTEM_CHANGED_TB(p_s_tb
))
848 n_retval
= REPEAT_SEARCH
;
853 /* Get free space of the left neighbor, which is stored in the parent
854 * node of the left neighbor. */
855 static int get_lfree(struct tree_balance
*tb
, int h
)
857 struct buffer_head
*l
, *f
;
860 if ((f
= PATH_H_PPARENT(tb
->tb_path
, h
)) == NULL
||
861 (l
= tb
->FL
[h
]) == NULL
)
865 order
= PATH_H_B_ITEM_ORDER(tb
->tb_path
, h
) - 1;
867 order
= B_NR_ITEMS(l
);
871 return (MAX_CHILD_SIZE(f
) - dc_size(B_N_CHILD(f
, order
)));
874 /* Get free space of the right neighbor,
875 * which is stored in the parent node of the right neighbor.
877 static int get_rfree(struct tree_balance
*tb
, int h
)
879 struct buffer_head
*r
, *f
;
882 if ((f
= PATH_H_PPARENT(tb
->tb_path
, h
)) == NULL
||
883 (r
= tb
->FR
[h
]) == NULL
)
887 order
= PATH_H_B_ITEM_ORDER(tb
->tb_path
, h
) + 1;
893 return (MAX_CHILD_SIZE(f
) - dc_size(B_N_CHILD(f
, order
)));
897 /* Check whether left neighbor is in memory. */
898 static int is_left_neighbor_in_cache(struct tree_balance
*p_s_tb
, int n_h
)
900 struct buffer_head
*p_s_father
, *left
;
901 struct super_block
*p_s_sb
= p_s_tb
->tb_sb
;
902 b_blocknr_t n_left_neighbor_blocknr
;
903 int n_left_neighbor_position
;
905 if (!p_s_tb
->FL
[n_h
]) /* Father of the left neighbor does not exist. */
908 /* Calculate father of the node to be balanced. */
909 p_s_father
= PATH_H_PBUFFER(p_s_tb
->tb_path
, n_h
+ 1);
911 RFALSE(!p_s_father
||
912 !B_IS_IN_TREE(p_s_father
) ||
913 !B_IS_IN_TREE(p_s_tb
->FL
[n_h
]) ||
914 !buffer_uptodate(p_s_father
) ||
915 !buffer_uptodate(p_s_tb
->FL
[n_h
]),
916 "vs-8165: F[h] (%b) or FL[h] (%b) is invalid",
917 p_s_father
, p_s_tb
->FL
[n_h
]);
919 /* Get position of the pointer to the left neighbor into the left father. */
920 n_left_neighbor_position
= (p_s_father
== p_s_tb
->FL
[n_h
]) ?
921 p_s_tb
->lkey
[n_h
] : B_NR_ITEMS(p_s_tb
->FL
[n_h
]);
922 /* Get left neighbor block number. */
923 n_left_neighbor_blocknr
=
924 B_N_CHILD_NUM(p_s_tb
->FL
[n_h
], n_left_neighbor_position
);
925 /* Look for the left neighbor in the cache. */
926 if ((left
= sb_find_get_block(p_s_sb
, n_left_neighbor_blocknr
))) {
928 RFALSE(buffer_uptodate(left
) && !B_IS_IN_TREE(left
),
929 "vs-8170: left neighbor (%b %z) is not in the tree",
938 #define LEFT_PARENTS 'l'
939 #define RIGHT_PARENTS 'r'
941 static void decrement_key(struct cpu_key
*p_s_key
)
943 // call item specific function for this key
944 item_ops
[cpu_key_k_type(p_s_key
)]->decrement_key(p_s_key
);
947 /* Calculate far left/right parent of the left/right neighbor of the current node, that
948 * is calculate the left/right (FL[h]/FR[h]) neighbor of the parent F[h].
949 * Calculate left/right common parent of the current node and L[h]/R[h].
950 * Calculate left/right delimiting key position.
951 * Returns: PATH_INCORRECT - path in the tree is not correct;
952 SCHEDULE_OCCURRED - schedule occurred while the function worked;
953 * CARRY_ON - schedule didn't occur while the function worked;
955 static int get_far_parent(struct tree_balance
*p_s_tb
,
957 struct buffer_head
**pp_s_father
,
958 struct buffer_head
**pp_s_com_father
, char c_lr_par
)
960 struct buffer_head
*p_s_parent
;
961 INITIALIZE_PATH(s_path_to_neighbor_father
);
962 struct treepath
*p_s_path
= p_s_tb
->tb_path
;
963 struct cpu_key s_lr_father_key
;
965 n_position
= INT_MAX
,
966 n_first_last_position
= 0,
967 n_path_offset
= PATH_H_PATH_OFFSET(p_s_path
, n_h
);
969 /* Starting from F[n_h] go upwards in the tree, and look for the common
970 ancestor of F[n_h], and its neighbor l/r, that should be obtained. */
972 n_counter
= n_path_offset
;
974 RFALSE(n_counter
< FIRST_PATH_ELEMENT_OFFSET
,
975 "PAP-8180: invalid path length");
977 for (; n_counter
> FIRST_PATH_ELEMENT_OFFSET
; n_counter
--) {
978 /* Check whether parent of the current buffer in the path is really parent in the tree. */
980 (p_s_parent
= PATH_OFFSET_PBUFFER(p_s_path
, n_counter
- 1)))
981 return REPEAT_SEARCH
;
982 /* Check whether position in the parent is correct. */
984 PATH_OFFSET_POSITION(p_s_path
,
986 B_NR_ITEMS(p_s_parent
))
987 return REPEAT_SEARCH
;
988 /* Check whether parent at the path really points to the child. */
989 if (B_N_CHILD_NUM(p_s_parent
, n_position
) !=
990 PATH_OFFSET_PBUFFER(p_s_path
, n_counter
)->b_blocknr
)
991 return REPEAT_SEARCH
;
992 /* Return delimiting key if position in the parent is not equal to first/last one. */
993 if (c_lr_par
== RIGHT_PARENTS
)
994 n_first_last_position
= B_NR_ITEMS(p_s_parent
);
995 if (n_position
!= n_first_last_position
) {
996 *pp_s_com_father
= p_s_parent
;
997 get_bh(*pp_s_com_father
);
998 /*(*pp_s_com_father = p_s_parent)->b_count++; */
1003 /* if we are in the root of the tree, then there is no common father */
1004 if (n_counter
== FIRST_PATH_ELEMENT_OFFSET
) {
1005 /* Check whether first buffer in the path is the root of the tree. */
1006 if (PATH_OFFSET_PBUFFER
1008 FIRST_PATH_ELEMENT_OFFSET
)->b_blocknr
==
1009 SB_ROOT_BLOCK(p_s_tb
->tb_sb
)) {
1010 *pp_s_father
= *pp_s_com_father
= NULL
;
1013 return REPEAT_SEARCH
;
1016 RFALSE(B_LEVEL(*pp_s_com_father
) <= DISK_LEAF_NODE_LEVEL
,
1017 "PAP-8185: (%b %z) level too small",
1018 *pp_s_com_father
, *pp_s_com_father
);
1020 /* Check whether the common parent is locked. */
1022 if (buffer_locked(*pp_s_com_father
)) {
1023 __wait_on_buffer(*pp_s_com_father
);
1024 if (FILESYSTEM_CHANGED_TB(p_s_tb
)) {
1025 decrement_bcount(*pp_s_com_father
);
1026 return REPEAT_SEARCH
;
1030 /* So, we got common parent of the current node and its left/right neighbor.
1031 Now we are geting the parent of the left/right neighbor. */
1033 /* Form key to get parent of the left/right neighbor. */
1034 le_key2cpu_key(&s_lr_father_key
,
1035 B_N_PDELIM_KEY(*pp_s_com_father
,
1037 LEFT_PARENTS
) ? (p_s_tb
->lkey
[n_h
- 1] =
1039 1) : (p_s_tb
->rkey
[n_h
-
1043 if (c_lr_par
== LEFT_PARENTS
)
1044 decrement_key(&s_lr_father_key
);
1047 (p_s_tb
->tb_sb
, &s_lr_father_key
, &s_path_to_neighbor_father
,
1048 n_h
+ 1) == IO_ERROR
)
1052 if (FILESYSTEM_CHANGED_TB(p_s_tb
)) {
1053 decrement_counters_in_path(&s_path_to_neighbor_father
);
1054 decrement_bcount(*pp_s_com_father
);
1055 return REPEAT_SEARCH
;
1058 *pp_s_father
= PATH_PLAST_BUFFER(&s_path_to_neighbor_father
);
1060 RFALSE(B_LEVEL(*pp_s_father
) != n_h
+ 1,
1061 "PAP-8190: (%b %z) level too small", *pp_s_father
, *pp_s_father
);
1062 RFALSE(s_path_to_neighbor_father
.path_length
<
1063 FIRST_PATH_ELEMENT_OFFSET
, "PAP-8192: path length is too small");
1065 s_path_to_neighbor_father
.path_length
--;
1066 decrement_counters_in_path(&s_path_to_neighbor_father
);
1070 /* Get parents of neighbors of node in the path(S[n_path_offset]) and common parents of
1071 * S[n_path_offset] and L[n_path_offset]/R[n_path_offset]: F[n_path_offset], FL[n_path_offset],
1072 * FR[n_path_offset], CFL[n_path_offset], CFR[n_path_offset].
1073 * Calculate numbers of left and right delimiting keys position: lkey[n_path_offset], rkey[n_path_offset].
1074 * Returns: SCHEDULE_OCCURRED - schedule occurred while the function worked;
1075 * CARRY_ON - schedule didn't occur while the function worked;
1077 static int get_parents(struct tree_balance
*p_s_tb
, int n_h
)
1079 struct treepath
*p_s_path
= p_s_tb
->tb_path
;
1082 n_path_offset
= PATH_H_PATH_OFFSET(p_s_tb
->tb_path
, n_h
);
1083 struct buffer_head
*p_s_curf
, *p_s_curcf
;
1085 /* Current node is the root of the tree or will be root of the tree */
1086 if (n_path_offset
<= FIRST_PATH_ELEMENT_OFFSET
) {
1087 /* The root can not have parents.
1088 Release nodes which previously were obtained as parents of the current node neighbors. */
1089 decrement_bcount(p_s_tb
->FL
[n_h
]);
1090 decrement_bcount(p_s_tb
->CFL
[n_h
]);
1091 decrement_bcount(p_s_tb
->FR
[n_h
]);
1092 decrement_bcount(p_s_tb
->CFR
[n_h
]);
1093 p_s_tb
->FL
[n_h
] = p_s_tb
->CFL
[n_h
] = p_s_tb
->FR
[n_h
] =
1094 p_s_tb
->CFR
[n_h
] = NULL
;
1098 /* Get parent FL[n_path_offset] of L[n_path_offset]. */
1099 if ((n_position
= PATH_OFFSET_POSITION(p_s_path
, n_path_offset
- 1))) {
1100 /* Current node is not the first child of its parent. */
1101 /*(p_s_curf = p_s_curcf = PATH_OFFSET_PBUFFER(p_s_path, n_path_offset - 1))->b_count += 2; */
1102 p_s_curf
= p_s_curcf
=
1103 PATH_OFFSET_PBUFFER(p_s_path
, n_path_offset
- 1);
1106 p_s_tb
->lkey
[n_h
] = n_position
- 1;
1108 /* Calculate current parent of L[n_path_offset], which is the left neighbor of the current node.
1109 Calculate current common parent of L[n_path_offset] and the current node. Note that
1110 CFL[n_path_offset] not equal FL[n_path_offset] and CFL[n_path_offset] not equal F[n_path_offset].
1111 Calculate lkey[n_path_offset]. */
1112 if ((n_ret_value
= get_far_parent(p_s_tb
, n_h
+ 1, &p_s_curf
,
1114 LEFT_PARENTS
)) != CARRY_ON
)
1118 decrement_bcount(p_s_tb
->FL
[n_h
]);
1119 p_s_tb
->FL
[n_h
] = p_s_curf
; /* New initialization of FL[n_h]. */
1120 decrement_bcount(p_s_tb
->CFL
[n_h
]);
1121 p_s_tb
->CFL
[n_h
] = p_s_curcf
; /* New initialization of CFL[n_h]. */
1123 RFALSE((p_s_curf
&& !B_IS_IN_TREE(p_s_curf
)) ||
1124 (p_s_curcf
&& !B_IS_IN_TREE(p_s_curcf
)),
1125 "PAP-8195: FL (%b) or CFL (%b) is invalid", p_s_curf
, p_s_curcf
);
1127 /* Get parent FR[n_h] of R[n_h]. */
1129 /* Current node is the last child of F[n_h]. FR[n_h] != F[n_h]. */
1130 if (n_position
== B_NR_ITEMS(PATH_H_PBUFFER(p_s_path
, n_h
+ 1))) {
1131 /* Calculate current parent of R[n_h], which is the right neighbor of F[n_h].
1132 Calculate current common parent of R[n_h] and current node. Note that CFR[n_h]
1133 not equal FR[n_path_offset] and CFR[n_h] not equal F[n_h]. */
1135 get_far_parent(p_s_tb
, n_h
+ 1, &p_s_curf
, &p_s_curcf
,
1136 RIGHT_PARENTS
)) != CARRY_ON
)
1139 /* Current node is not the last child of its parent F[n_h]. */
1140 /*(p_s_curf = p_s_curcf = PATH_OFFSET_PBUFFER(p_s_path, n_path_offset - 1))->b_count += 2; */
1141 p_s_curf
= p_s_curcf
=
1142 PATH_OFFSET_PBUFFER(p_s_path
, n_path_offset
- 1);
1145 p_s_tb
->rkey
[n_h
] = n_position
;
1148 decrement_bcount(p_s_tb
->FR
[n_h
]);
1149 p_s_tb
->FR
[n_h
] = p_s_curf
; /* New initialization of FR[n_path_offset]. */
1151 decrement_bcount(p_s_tb
->CFR
[n_h
]);
1152 p_s_tb
->CFR
[n_h
] = p_s_curcf
; /* New initialization of CFR[n_path_offset]. */
1154 RFALSE((p_s_curf
&& !B_IS_IN_TREE(p_s_curf
)) ||
1155 (p_s_curcf
&& !B_IS_IN_TREE(p_s_curcf
)),
1156 "PAP-8205: FR (%b) or CFR (%b) is invalid", p_s_curf
, p_s_curcf
);
1161 /* it is possible to remove node as result of shiftings to
1162 neighbors even when we insert or paste item. */
1163 static inline int can_node_be_removed(int mode
, int lfree
, int sfree
, int rfree
,
1164 struct tree_balance
*tb
, int h
)
1166 struct buffer_head
*Sh
= PATH_H_PBUFFER(tb
->tb_path
, h
);
1167 int levbytes
= tb
->insert_size
[h
];
1168 struct item_head
*ih
;
1169 struct reiserfs_key
*r_key
= NULL
;
1171 ih
= B_N_PITEM_HEAD(Sh
, 0);
1173 r_key
= B_N_PDELIM_KEY(tb
->CFR
[h
], tb
->rkey
[h
]);
1175 if (lfree
+ rfree
+ sfree
< MAX_CHILD_SIZE(Sh
) + levbytes
1176 /* shifting may merge items which might save space */
1179 && op_is_left_mergeable(&(ih
->ih_key
), Sh
->b_size
)) ? IH_SIZE
: 0)
1182 && op_is_left_mergeable(r_key
, Sh
->b_size
)) ? IH_SIZE
: 0)
1183 + ((h
) ? KEY_SIZE
: 0)) {
1184 /* node can not be removed */
1185 if (sfree
>= levbytes
) { /* new item fits into node S[h] without any shifting */
1189 ((mode
== M_INSERT
) ? 1 : 0);
1190 set_parameters(tb
, h
, 0, 0, 1, NULL
, -1, -1);
1191 return NO_BALANCING_NEEDED
;
1194 PROC_INFO_INC(tb
->tb_sb
, can_node_be_removed
[h
]);
1195 return !NO_BALANCING_NEEDED
;
1198 /* Check whether current node S[h] is balanced when increasing its size by
1199 * Inserting or Pasting.
1200 * Calculate parameters for balancing for current level h.
1202 * tb tree_balance structure;
1203 * h current level of the node;
1204 * inum item number in S[h];
1205 * mode i - insert, p - paste;
1206 * Returns: 1 - schedule occurred;
1207 * 0 - balancing for higher levels needed;
1208 * -1 - no balancing for higher levels needed;
1209 * -2 - no disk space.
1211 /* ip means Inserting or Pasting */
1212 static int ip_check_balance(struct tree_balance
*tb
, int h
)
1214 struct virtual_node
*vn
= tb
->tb_vn
;
1215 int levbytes
, /* Number of bytes that must be inserted into (value
1216 is negative if bytes are deleted) buffer which
1217 contains node being balanced. The mnemonic is
1218 that the attempted change in node space used level
1219 is levbytes bytes. */
1222 int lfree
, sfree
, rfree
/* free space in L, S and R */ ;
1224 /* nver is short for number of vertixes, and lnver is the number if
1225 we shift to the left, rnver is the number if we shift to the
1226 right, and lrnver is the number if we shift in both directions.
1227 The goal is to minimize first the number of vertixes, and second,
1228 the number of vertixes whose contents are changed by shifting,
1229 and third the number of uncached vertixes whose contents are
1230 changed by shifting and must be read from disk. */
1231 int nver
, lnver
, rnver
, lrnver
;
1233 /* used at leaf level only, S0 = S[0] is the node being balanced,
1234 sInum [ I = 0,1,2 ] is the number of items that will
1235 remain in node SI after balancing. S1 and S2 are new
1236 nodes that might be created. */
1238 /* we perform 8 calls to get_num_ver(). For each call we calculate five parameters.
1239 where 4th parameter is s1bytes and 5th - s2bytes
1241 short snum012
[40] = { 0, }; /* s0num, s1num, s2num for 8 cases
1242 0,1 - do not shift and do not shift but bottle
1243 2 - shift only whole item to left
1244 3 - shift to left and bottle as much as possible
1245 4,5 - shift to right (whole items and as much as possible
1246 6,7 - shift to both directions (whole items and as much as possible)
1249 /* Sh is the node whose balance is currently being checked */
1250 struct buffer_head
*Sh
;
1252 Sh
= PATH_H_PBUFFER(tb
->tb_path
, h
);
1253 levbytes
= tb
->insert_size
[h
];
1255 /* Calculate balance parameters for creating new root. */
1258 reiserfs_panic(tb
->tb_sb
, "vs-8210",
1259 "S[0] can not be 0");
1260 switch (n_ret_value
= get_empty_nodes(tb
, h
)) {
1262 set_parameters(tb
, h
, 0, 0, 1, NULL
, -1, -1);
1263 return NO_BALANCING_NEEDED
; /* no balancing for higher levels needed */
1269 reiserfs_panic(tb
->tb_sb
, "vs-8215", "incorrect "
1270 "return value of get_empty_nodes");
1274 if ((n_ret_value
= get_parents(tb
, h
)) != CARRY_ON
) /* get parents of S[h] neighbors. */
1277 sfree
= B_FREE_SPACE(Sh
);
1279 /* get free space of neighbors */
1280 rfree
= get_rfree(tb
, h
);
1281 lfree
= get_lfree(tb
, h
);
1283 if (can_node_be_removed(vn
->vn_mode
, lfree
, sfree
, rfree
, tb
, h
) ==
1284 NO_BALANCING_NEEDED
)
1285 /* and new item fits into node S[h] without any shifting */
1286 return NO_BALANCING_NEEDED
;
1288 create_virtual_node(tb
, h
);
1291 determine maximal number of items we can shift to the left neighbor (in tb structure)
1292 and the maximal number of bytes that can flow to the left neighbor
1293 from the left most liquid item that cannot be shifted from S[0] entirely (returned value)
1295 check_left(tb
, h
, lfree
);
1298 determine maximal number of items we can shift to the right neighbor (in tb structure)
1299 and the maximal number of bytes that can flow to the right neighbor
1300 from the right most liquid item that cannot be shifted from S[0] entirely (returned value)
1302 check_right(tb
, h
, rfree
);
1304 /* all contents of internal node S[h] can be moved into its
1305 neighbors, S[h] will be removed after balancing */
1306 if (h
&& (tb
->rnum
[h
] + tb
->lnum
[h
] >= vn
->vn_nr_item
+ 1)) {
1309 /* Since we are working on internal nodes, and our internal
1310 nodes have fixed size entries, then we can balance by the
1311 number of items rather than the space they consume. In this
1312 routine we set the left node equal to the right node,
1313 allowing a difference of less than or equal to 1 child
1316 ((MAX_NR_KEY(Sh
) << 1) + 2 - tb
->lnum
[h
] - tb
->rnum
[h
] +
1317 vn
->vn_nr_item
+ 1) / 2 - (MAX_NR_KEY(Sh
) + 1 -
1319 set_parameters(tb
, h
, vn
->vn_nr_item
+ 1 - to_r
, to_r
, 0, NULL
,
1324 /* this checks balance condition, that any two neighboring nodes can not fit in one node */
1326 (tb
->lnum
[h
] >= vn
->vn_nr_item
+ 1 ||
1327 tb
->rnum
[h
] >= vn
->vn_nr_item
+ 1),
1328 "vs-8220: tree is not balanced on internal level");
1329 RFALSE(!h
&& ((tb
->lnum
[h
] >= vn
->vn_nr_item
&& (tb
->lbytes
== -1)) ||
1330 (tb
->rnum
[h
] >= vn
->vn_nr_item
&& (tb
->rbytes
== -1))),
1331 "vs-8225: tree is not balanced on leaf level");
1333 /* all contents of S[0] can be moved into its neighbors
1334 S[0] will be removed after balancing. */
1335 if (!h
&& is_leaf_removable(tb
))
1338 /* why do we perform this check here rather than earlier??
1339 Answer: we can win 1 node in some cases above. Moreover we
1340 checked it above, when we checked, that S[0] is not removable
1342 if (sfree
>= levbytes
) { /* new item fits into node S[h] without any shifting */
1344 tb
->s0num
= vn
->vn_nr_item
;
1345 set_parameters(tb
, h
, 0, 0, 1, NULL
, -1, -1);
1346 return NO_BALANCING_NEEDED
;
1350 int lpar
, rpar
, nset
, lset
, rset
, lrset
;
1352 * regular overflowing of the node
1355 /* get_num_ver works in 2 modes (FLOW & NO_FLOW)
1356 lpar, rpar - number of items we can shift to left/right neighbor (including splitting item)
1357 nset, lset, rset, lrset - shows, whether flowing items give better packing
1360 #define NO_FLOW 0 /* do not any splitting */
1362 /* we choose one the following */
1363 #define NOTHING_SHIFT_NO_FLOW 0
1364 #define NOTHING_SHIFT_FLOW 5
1365 #define LEFT_SHIFT_NO_FLOW 10
1366 #define LEFT_SHIFT_FLOW 15
1367 #define RIGHT_SHIFT_NO_FLOW 20
1368 #define RIGHT_SHIFT_FLOW 25
1369 #define LR_SHIFT_NO_FLOW 30
1370 #define LR_SHIFT_FLOW 35
1375 /* calculate number of blocks S[h] must be split into when
1376 nothing is shifted to the neighbors,
1377 as well as number of items in each part of the split node (s012 numbers),
1378 and number of bytes (s1bytes) of the shared drop which flow to S1 if any */
1379 nset
= NOTHING_SHIFT_NO_FLOW
;
1380 nver
= get_num_ver(vn
->vn_mode
, tb
, h
,
1381 0, -1, h
? vn
->vn_nr_item
: 0, -1,
1387 /* note, that in this case we try to bottle between S[0] and S1 (S1 - the first new node) */
1388 nver1
= get_num_ver(vn
->vn_mode
, tb
, h
,
1390 snum012
+ NOTHING_SHIFT_FLOW
, FLOW
);
1392 nset
= NOTHING_SHIFT_FLOW
, nver
= nver1
;
1395 /* calculate number of blocks S[h] must be split into when
1396 l_shift_num first items and l_shift_bytes of the right most
1397 liquid item to be shifted are shifted to the left neighbor,
1398 as well as number of items in each part of the splitted node (s012 numbers),
1399 and number of bytes (s1bytes) of the shared drop which flow to S1 if any
1401 lset
= LEFT_SHIFT_NO_FLOW
;
1402 lnver
= get_num_ver(vn
->vn_mode
, tb
, h
,
1403 lpar
- ((h
|| tb
->lbytes
== -1) ? 0 : 1),
1404 -1, h
? vn
->vn_nr_item
: 0, -1,
1405 snum012
+ LEFT_SHIFT_NO_FLOW
, NO_FLOW
);
1409 lnver1
= get_num_ver(vn
->vn_mode
, tb
, h
,
1411 ((tb
->lbytes
!= -1) ? 1 : 0),
1413 snum012
+ LEFT_SHIFT_FLOW
, FLOW
);
1415 lset
= LEFT_SHIFT_FLOW
, lnver
= lnver1
;
1418 /* calculate number of blocks S[h] must be split into when
1419 r_shift_num first items and r_shift_bytes of the left most
1420 liquid item to be shifted are shifted to the right neighbor,
1421 as well as number of items in each part of the splitted node (s012 numbers),
1422 and number of bytes (s1bytes) of the shared drop which flow to S1 if any
1424 rset
= RIGHT_SHIFT_NO_FLOW
;
1425 rnver
= get_num_ver(vn
->vn_mode
, tb
, h
,
1427 h
? (vn
->vn_nr_item
- rpar
) : (rpar
-
1432 snum012
+ RIGHT_SHIFT_NO_FLOW
, NO_FLOW
);
1436 rnver1
= get_num_ver(vn
->vn_mode
, tb
, h
,
1439 ((tb
->rbytes
!= -1) ? 1 : 0)),
1441 snum012
+ RIGHT_SHIFT_FLOW
, FLOW
);
1444 rset
= RIGHT_SHIFT_FLOW
, rnver
= rnver1
;
1447 /* calculate number of blocks S[h] must be split into when
1448 items are shifted in both directions,
1449 as well as number of items in each part of the splitted node (s012 numbers),
1450 and number of bytes (s1bytes) of the shared drop which flow to S1 if any
1452 lrset
= LR_SHIFT_NO_FLOW
;
1453 lrnver
= get_num_ver(vn
->vn_mode
, tb
, h
,
1454 lpar
- ((h
|| tb
->lbytes
== -1) ? 0 : 1),
1456 h
? (vn
->vn_nr_item
- rpar
) : (rpar
-
1461 snum012
+ LR_SHIFT_NO_FLOW
, NO_FLOW
);
1465 lrnver1
= get_num_ver(vn
->vn_mode
, tb
, h
,
1467 ((tb
->lbytes
!= -1) ? 1 : 0),
1470 ((tb
->rbytes
!= -1) ? 1 : 0)),
1472 snum012
+ LR_SHIFT_FLOW
, FLOW
);
1473 if (lrnver
> lrnver1
)
1474 lrset
= LR_SHIFT_FLOW
, lrnver
= lrnver1
;
1477 /* Our general shifting strategy is:
1478 1) to minimized number of new nodes;
1479 2) to minimized number of neighbors involved in shifting;
1480 3) to minimized number of disk reads; */
1482 /* we can win TWO or ONE nodes by shifting in both directions */
1483 if (lrnver
< lnver
&& lrnver
< rnver
) {
1485 (tb
->lnum
[h
] != 1 ||
1487 lrnver
!= 1 || rnver
!= 2 || lnver
!= 2
1488 || h
!= 1), "vs-8230: bad h");
1489 if (lrset
== LR_SHIFT_FLOW
)
1490 set_parameters(tb
, h
, tb
->lnum
[h
], tb
->rnum
[h
],
1491 lrnver
, snum012
+ lrset
,
1492 tb
->lbytes
, tb
->rbytes
);
1494 set_parameters(tb
, h
,
1496 ((tb
->lbytes
== -1) ? 0 : 1),
1498 ((tb
->rbytes
== -1) ? 0 : 1),
1499 lrnver
, snum012
+ lrset
, -1, -1);
1504 /* if shifting doesn't lead to better packing then don't shift */
1505 if (nver
== lrnver
) {
1506 set_parameters(tb
, h
, 0, 0, nver
, snum012
+ nset
, -1,
1511 /* now we know that for better packing shifting in only one
1512 direction either to the left or to the right is required */
1514 /* if shifting to the left is better than shifting to the right */
1515 if (lnver
< rnver
) {
1520 /* if shifting to the right is better than shifting to the left */
1521 if (lnver
> rnver
) {
1522 SET_PAR_SHIFT_RIGHT
;
1526 /* now shifting in either direction gives the same number
1527 of nodes and we can make use of the cached neighbors */
1528 if (is_left_neighbor_in_cache(tb
, h
)) {
1533 /* shift to the right independently on whether the right neighbor in cache or not */
1534 SET_PAR_SHIFT_RIGHT
;
1539 /* Check whether current node S[h] is balanced when Decreasing its size by
1540 * Deleting or Cutting for INTERNAL node of S+tree.
1541 * Calculate parameters for balancing for current level h.
1543 * tb tree_balance structure;
1544 * h current level of the node;
1545 * inum item number in S[h];
1546 * mode i - insert, p - paste;
1547 * Returns: 1 - schedule occurred;
1548 * 0 - balancing for higher levels needed;
1549 * -1 - no balancing for higher levels needed;
1550 * -2 - no disk space.
1552 * Note: Items of internal nodes have fixed size, so the balance condition for
1553 * the internal part of S+tree is as for the B-trees.
1555 static int dc_check_balance_internal(struct tree_balance
*tb
, int h
)
1557 struct virtual_node
*vn
= tb
->tb_vn
;
1559 /* Sh is the node whose balance is currently being checked,
1560 and Fh is its father. */
1561 struct buffer_head
*Sh
, *Fh
;
1562 int maxsize
, n_ret_value
;
1563 int lfree
, rfree
/* free space in L and R */ ;
1565 Sh
= PATH_H_PBUFFER(tb
->tb_path
, h
);
1566 Fh
= PATH_H_PPARENT(tb
->tb_path
, h
);
1568 maxsize
= MAX_CHILD_SIZE(Sh
);
1570 /* using tb->insert_size[h], which is negative in this case, create_virtual_node calculates: */
1571 /* new_nr_item = number of items node would have if operation is */
1572 /* performed without balancing (new_nr_item); */
1573 create_virtual_node(tb
, h
);
1575 if (!Fh
) { /* S[h] is the root. */
1576 if (vn
->vn_nr_item
> 0) {
1577 set_parameters(tb
, h
, 0, 0, 1, NULL
, -1, -1);
1578 return NO_BALANCING_NEEDED
; /* no balancing for higher levels needed */
1580 /* new_nr_item == 0.
1581 * Current root will be deleted resulting in
1582 * decrementing the tree height. */
1583 set_parameters(tb
, h
, 0, 0, 0, NULL
, -1, -1);
1587 if ((n_ret_value
= get_parents(tb
, h
)) != CARRY_ON
)
1590 /* get free space of neighbors */
1591 rfree
= get_rfree(tb
, h
);
1592 lfree
= get_lfree(tb
, h
);
1594 /* determine maximal number of items we can fit into neighbors */
1595 check_left(tb
, h
, lfree
);
1596 check_right(tb
, h
, rfree
);
1598 if (vn
->vn_nr_item
>= MIN_NR_KEY(Sh
)) { /* Balance condition for the internal node is valid.
1599 * In this case we balance only if it leads to better packing. */
1600 if (vn
->vn_nr_item
== MIN_NR_KEY(Sh
)) { /* Here we join S[h] with one of its neighbors,
1601 * which is impossible with greater values of new_nr_item. */
1602 if (tb
->lnum
[h
] >= vn
->vn_nr_item
+ 1) {
1603 /* All contents of S[h] can be moved to L[h]. */
1609 PATH_H_B_ITEM_ORDER(tb
->tb_path
,
1611 0) ? B_NR_ITEMS(tb
->FL
[h
]) : n
- 1;
1612 n
= dc_size(B_N_CHILD(tb
->FL
[h
], order_L
)) /
1613 (DC_SIZE
+ KEY_SIZE
);
1614 set_parameters(tb
, h
, -n
- 1, 0, 0, NULL
, -1,
1619 if (tb
->rnum
[h
] >= vn
->vn_nr_item
+ 1) {
1620 /* All contents of S[h] can be moved to R[h]. */
1626 PATH_H_B_ITEM_ORDER(tb
->tb_path
,
1628 B_NR_ITEMS(Fh
)) ? 0 : n
+ 1;
1629 n
= dc_size(B_N_CHILD(tb
->FR
[h
], order_R
)) /
1630 (DC_SIZE
+ KEY_SIZE
);
1631 set_parameters(tb
, h
, 0, -n
- 1, 0, NULL
, -1,
1637 if (tb
->rnum
[h
] + tb
->lnum
[h
] >= vn
->vn_nr_item
+ 1) {
1638 /* All contents of S[h] can be moved to the neighbors (L[h] & R[h]). */
1642 ((MAX_NR_KEY(Sh
) << 1) + 2 - tb
->lnum
[h
] -
1643 tb
->rnum
[h
] + vn
->vn_nr_item
+ 1) / 2 -
1644 (MAX_NR_KEY(Sh
) + 1 - tb
->rnum
[h
]);
1645 set_parameters(tb
, h
, vn
->vn_nr_item
+ 1 - to_r
, to_r
,
1650 /* Balancing does not lead to better packing. */
1651 set_parameters(tb
, h
, 0, 0, 1, NULL
, -1, -1);
1652 return NO_BALANCING_NEEDED
;
1655 /* Current node contain insufficient number of items. Balancing is required. */
1656 /* Check whether we can merge S[h] with left neighbor. */
1657 if (tb
->lnum
[h
] >= vn
->vn_nr_item
+ 1)
1658 if (is_left_neighbor_in_cache(tb
, h
)
1659 || tb
->rnum
[h
] < vn
->vn_nr_item
+ 1 || !tb
->FR
[h
]) {
1665 PATH_H_B_ITEM_ORDER(tb
->tb_path
,
1667 0) ? B_NR_ITEMS(tb
->FL
[h
]) : n
- 1;
1668 n
= dc_size(B_N_CHILD(tb
->FL
[h
], order_L
)) / (DC_SIZE
+
1670 set_parameters(tb
, h
, -n
- 1, 0, 0, NULL
, -1, -1);
1674 /* Check whether we can merge S[h] with right neighbor. */
1675 if (tb
->rnum
[h
] >= vn
->vn_nr_item
+ 1) {
1681 PATH_H_B_ITEM_ORDER(tb
->tb_path
,
1682 h
)) == B_NR_ITEMS(Fh
)) ? 0 : (n
+ 1);
1683 n
= dc_size(B_N_CHILD(tb
->FR
[h
], order_R
)) / (DC_SIZE
+
1685 set_parameters(tb
, h
, 0, -n
- 1, 0, NULL
, -1, -1);
1689 /* All contents of S[h] can be moved to the neighbors (L[h] & R[h]). */
1690 if (tb
->rnum
[h
] + tb
->lnum
[h
] >= vn
->vn_nr_item
+ 1) {
1694 ((MAX_NR_KEY(Sh
) << 1) + 2 - tb
->lnum
[h
] - tb
->rnum
[h
] +
1695 vn
->vn_nr_item
+ 1) / 2 - (MAX_NR_KEY(Sh
) + 1 -
1697 set_parameters(tb
, h
, vn
->vn_nr_item
+ 1 - to_r
, to_r
, 0, NULL
,
1702 /* For internal nodes try to borrow item from a neighbor */
1703 RFALSE(!tb
->FL
[h
] && !tb
->FR
[h
], "vs-8235: trying to borrow for root");
1705 /* Borrow one or two items from caching neighbor */
1706 if (is_left_neighbor_in_cache(tb
, h
) || !tb
->FR
[h
]) {
1710 (MAX_NR_KEY(Sh
) + 1 - tb
->lnum
[h
] + vn
->vn_nr_item
+
1711 1) / 2 - (vn
->vn_nr_item
+ 1);
1712 set_parameters(tb
, h
, -from_l
, 0, 1, NULL
, -1, -1);
1716 set_parameters(tb
, h
, 0,
1717 -((MAX_NR_KEY(Sh
) + 1 - tb
->rnum
[h
] + vn
->vn_nr_item
+
1718 1) / 2 - (vn
->vn_nr_item
+ 1)), 1, NULL
, -1, -1);
1722 /* Check whether current node S[h] is balanced when Decreasing its size by
1723 * Deleting or Truncating for LEAF node of S+tree.
1724 * Calculate parameters for balancing for current level h.
1726 * tb tree_balance structure;
1727 * h current level of the node;
1728 * inum item number in S[h];
1729 * mode i - insert, p - paste;
1730 * Returns: 1 - schedule occurred;
1731 * 0 - balancing for higher levels needed;
1732 * -1 - no balancing for higher levels needed;
1733 * -2 - no disk space.
1735 static int dc_check_balance_leaf(struct tree_balance
*tb
, int h
)
1737 struct virtual_node
*vn
= tb
->tb_vn
;
1739 /* Number of bytes that must be deleted from
1740 (value is negative if bytes are deleted) buffer which
1741 contains node being balanced. The mnemonic is that the
1742 attempted change in node space used level is levbytes bytes. */
1744 /* the maximal item size */
1745 int maxsize
, n_ret_value
;
1746 /* S0 is the node whose balance is currently being checked,
1747 and F0 is its father. */
1748 struct buffer_head
*S0
, *F0
;
1749 int lfree
, rfree
/* free space in L and R */ ;
1751 S0
= PATH_H_PBUFFER(tb
->tb_path
, 0);
1752 F0
= PATH_H_PPARENT(tb
->tb_path
, 0);
1754 levbytes
= tb
->insert_size
[h
];
1756 maxsize
= MAX_CHILD_SIZE(S0
); /* maximal possible size of an item */
1758 if (!F0
) { /* S[0] is the root now. */
1760 RFALSE(-levbytes
>= maxsize
- B_FREE_SPACE(S0
),
1761 "vs-8240: attempt to create empty buffer tree");
1763 set_parameters(tb
, h
, 0, 0, 1, NULL
, -1, -1);
1764 return NO_BALANCING_NEEDED
;
1767 if ((n_ret_value
= 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 create_virtual_node(tb
, h
);
1776 /* if 3 leaves can be merge to one, set parameters and return */
1777 if (are_leaves_removable(tb
, lfree
, rfree
))
1780 /* determine maximal number of items we can shift to the left/right neighbor
1781 and the maximal number of bytes that can flow to the left/right neighbor
1782 from the left/right most liquid item that cannot be shifted from S[0] entirely
1784 check_left(tb
, h
, lfree
);
1785 check_right(tb
, h
, rfree
);
1787 /* check whether we can merge S with left neighbor. */
1788 if (tb
->lnum
[0] >= vn
->vn_nr_item
&& tb
->lbytes
== -1)
1789 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 */
1793 "vs-8245: dc_check_balance_leaf: FL[h] must exist");
1795 /* set parameter to merge S[0] with its left neighbor */
1796 set_parameters(tb
, h
, -1, 0, 0, NULL
, -1, -1);
1800 /* check whether we can merge S[0] with right neighbor. */
1801 if (tb
->rnum
[0] >= vn
->vn_nr_item
&& tb
->rbytes
== -1) {
1802 set_parameters(tb
, h
, 0, -1, 0, NULL
, -1, -1);
1806 /* All contents of S[0] can be moved to the neighbors (L[0] & R[0]). Set parameters and return */
1807 if (is_leaf_removable(tb
))
1810 /* Balancing is not required. */
1811 tb
->s0num
= vn
->vn_nr_item
;
1812 set_parameters(tb
, h
, 0, 0, 1, NULL
, -1, -1);
1813 return NO_BALANCING_NEEDED
;
1816 /* Check whether current node S[h] is balanced when Decreasing its size by
1817 * Deleting or Cutting.
1818 * Calculate parameters for balancing for current level h.
1820 * tb tree_balance structure;
1821 * h current level of the node;
1822 * inum item number in S[h];
1823 * mode d - delete, c - cut.
1824 * Returns: 1 - schedule occurred;
1825 * 0 - balancing for higher levels needed;
1826 * -1 - no balancing for higher levels needed;
1827 * -2 - no disk space.
1829 static int dc_check_balance(struct tree_balance
*tb
, int h
)
1831 RFALSE(!(PATH_H_PBUFFER(tb
->tb_path
, h
)),
1832 "vs-8250: S is not initialized");
1835 return dc_check_balance_internal(tb
, h
);
1837 return dc_check_balance_leaf(tb
, h
);
1840 /* Check whether current node S[h] is balanced.
1841 * Calculate parameters for balancing for current level h.
1844 * tb tree_balance structure:
1846 * tb is a large structure that must be read about in the header file
1847 * at the same time as this procedure if the reader is to successfully
1848 * understand this procedure
1850 * h current level of the node;
1851 * inum item number in S[h];
1852 * mode i - insert, p - paste, d - delete, c - cut.
1853 * Returns: 1 - schedule occurred;
1854 * 0 - balancing for higher levels needed;
1855 * -1 - no balancing for higher levels needed;
1856 * -2 - no disk space.
1858 static int check_balance(int mode
,
1859 struct tree_balance
*tb
,
1863 struct item_head
*ins_ih
, const void *data
)
1865 struct virtual_node
*vn
;
1867 vn
= tb
->tb_vn
= (struct virtual_node
*)(tb
->vn_buf
);
1868 vn
->vn_free_ptr
= (char *)(tb
->tb_vn
+ 1);
1870 vn
->vn_affected_item_num
= inum
;
1871 vn
->vn_pos_in_item
= pos_in_item
;
1872 vn
->vn_ins_ih
= ins_ih
;
1875 RFALSE(mode
== M_INSERT
&& !vn
->vn_ins_ih
,
1876 "vs-8255: ins_ih can not be 0 in insert mode");
1878 if (tb
->insert_size
[h
] > 0)
1879 /* Calculate balance parameters when size of node is increasing. */
1880 return ip_check_balance(tb
, h
);
1882 /* Calculate balance parameters when size of node is decreasing. */
1883 return dc_check_balance(tb
, h
);
1886 /* Check whether parent at the path is the really parent of the current node.*/
1887 static int get_direct_parent(struct tree_balance
*p_s_tb
, int n_h
)
1889 struct buffer_head
*p_s_bh
;
1890 struct treepath
*p_s_path
= p_s_tb
->tb_path
;
1892 n_path_offset
= PATH_H_PATH_OFFSET(p_s_tb
->tb_path
, n_h
);
1894 /* We are in the root or in the new root. */
1895 if (n_path_offset
<= FIRST_PATH_ELEMENT_OFFSET
) {
1897 RFALSE(n_path_offset
< FIRST_PATH_ELEMENT_OFFSET
- 1,
1898 "PAP-8260: invalid offset in the path");
1900 if (PATH_OFFSET_PBUFFER(p_s_path
, FIRST_PATH_ELEMENT_OFFSET
)->
1901 b_blocknr
== SB_ROOT_BLOCK(p_s_tb
->tb_sb
)) {
1902 /* Root is not changed. */
1903 PATH_OFFSET_PBUFFER(p_s_path
, n_path_offset
- 1) = NULL
;
1904 PATH_OFFSET_POSITION(p_s_path
, n_path_offset
- 1) = 0;
1907 return REPEAT_SEARCH
; /* Root is changed and we must recalculate the path. */
1911 (p_s_bh
= PATH_OFFSET_PBUFFER(p_s_path
, n_path_offset
- 1)))
1912 return REPEAT_SEARCH
; /* Parent in the path is not in the tree. */
1915 PATH_OFFSET_POSITION(p_s_path
,
1916 n_path_offset
- 1)) > B_NR_ITEMS(p_s_bh
))
1917 return REPEAT_SEARCH
;
1919 if (B_N_CHILD_NUM(p_s_bh
, n_position
) !=
1920 PATH_OFFSET_PBUFFER(p_s_path
, n_path_offset
)->b_blocknr
)
1921 /* Parent in the path is not parent of the current node in the tree. */
1922 return REPEAT_SEARCH
;
1924 if (buffer_locked(p_s_bh
)) {
1925 __wait_on_buffer(p_s_bh
);
1926 if (FILESYSTEM_CHANGED_TB(p_s_tb
))
1927 return REPEAT_SEARCH
;
1930 return CARRY_ON
; /* Parent in the path is unlocked and really parent of the current node. */
1933 /* Using lnum[n_h] and rnum[n_h] we should determine what neighbors
1935 * need in order to balance S[n_h], and get them if necessary.
1936 * Returns: SCHEDULE_OCCURRED - schedule occurred while the function worked;
1937 * CARRY_ON - schedule didn't occur while the function worked;
1939 static int get_neighbors(struct tree_balance
*p_s_tb
, int n_h
)
1941 int n_child_position
,
1942 n_path_offset
= PATH_H_PATH_OFFSET(p_s_tb
->tb_path
, n_h
+ 1);
1943 unsigned long n_son_number
;
1944 struct super_block
*p_s_sb
= p_s_tb
->tb_sb
;
1945 struct buffer_head
*p_s_bh
;
1947 PROC_INFO_INC(p_s_sb
, get_neighbors
[n_h
]);
1949 if (p_s_tb
->lnum
[n_h
]) {
1950 /* We need left neighbor to balance S[n_h]. */
1951 PROC_INFO_INC(p_s_sb
, need_l_neighbor
[n_h
]);
1952 p_s_bh
= PATH_OFFSET_PBUFFER(p_s_tb
->tb_path
, n_path_offset
);
1954 RFALSE(p_s_bh
== p_s_tb
->FL
[n_h
] &&
1955 !PATH_OFFSET_POSITION(p_s_tb
->tb_path
, n_path_offset
),
1956 "PAP-8270: invalid position in the parent");
1960 p_s_tb
->FL
[n_h
]) ? p_s_tb
->lkey
[n_h
] : B_NR_ITEMS(p_s_tb
->
1962 n_son_number
= B_N_CHILD_NUM(p_s_tb
->FL
[n_h
], n_child_position
);
1963 p_s_bh
= sb_bread(p_s_sb
, n_son_number
);
1966 if (FILESYSTEM_CHANGED_TB(p_s_tb
)) {
1967 decrement_bcount(p_s_bh
);
1968 PROC_INFO_INC(p_s_sb
, get_neighbors_restart
[n_h
]);
1969 return REPEAT_SEARCH
;
1972 RFALSE(!B_IS_IN_TREE(p_s_tb
->FL
[n_h
]) ||
1973 n_child_position
> B_NR_ITEMS(p_s_tb
->FL
[n_h
]) ||
1974 B_N_CHILD_NUM(p_s_tb
->FL
[n_h
], n_child_position
) !=
1975 p_s_bh
->b_blocknr
, "PAP-8275: invalid parent");
1976 RFALSE(!B_IS_IN_TREE(p_s_bh
), "PAP-8280: invalid child");
1978 B_FREE_SPACE(p_s_bh
) !=
1979 MAX_CHILD_SIZE(p_s_bh
) -
1980 dc_size(B_N_CHILD(p_s_tb
->FL
[0], n_child_position
)),
1981 "PAP-8290: invalid child size of left neighbor");
1983 decrement_bcount(p_s_tb
->L
[n_h
]);
1984 p_s_tb
->L
[n_h
] = p_s_bh
;
1987 if (p_s_tb
->rnum
[n_h
]) { /* We need right neighbor to balance S[n_path_offset]. */
1988 PROC_INFO_INC(p_s_sb
, need_r_neighbor
[n_h
]);
1989 p_s_bh
= PATH_OFFSET_PBUFFER(p_s_tb
->tb_path
, n_path_offset
);
1991 RFALSE(p_s_bh
== p_s_tb
->FR
[n_h
] &&
1992 PATH_OFFSET_POSITION(p_s_tb
->tb_path
,
1995 "PAP-8295: invalid position in the parent");
1998 (p_s_bh
== p_s_tb
->FR
[n_h
]) ? p_s_tb
->rkey
[n_h
] + 1 : 0;
1999 n_son_number
= B_N_CHILD_NUM(p_s_tb
->FR
[n_h
], n_child_position
);
2000 p_s_bh
= sb_bread(p_s_sb
, n_son_number
);
2003 if (FILESYSTEM_CHANGED_TB(p_s_tb
)) {
2004 decrement_bcount(p_s_bh
);
2005 PROC_INFO_INC(p_s_sb
, get_neighbors_restart
[n_h
]);
2006 return REPEAT_SEARCH
;
2008 decrement_bcount(p_s_tb
->R
[n_h
]);
2009 p_s_tb
->R
[n_h
] = p_s_bh
;
2012 && B_FREE_SPACE(p_s_bh
) !=
2013 MAX_CHILD_SIZE(p_s_bh
) -
2014 dc_size(B_N_CHILD(p_s_tb
->FR
[0], n_child_position
)),
2015 "PAP-8300: invalid child size of right neighbor (%d != %d - %d)",
2016 B_FREE_SPACE(p_s_bh
), MAX_CHILD_SIZE(p_s_bh
),
2017 dc_size(B_N_CHILD(p_s_tb
->FR
[0], n_child_position
)));
2023 static int get_virtual_node_size(struct super_block
*sb
, struct buffer_head
*bh
)
2025 int max_num_of_items
;
2026 int max_num_of_entries
;
2027 unsigned long blocksize
= sb
->s_blocksize
;
2029 #define MIN_NAME_LEN 1
2031 max_num_of_items
= (blocksize
- BLKH_SIZE
) / (IH_SIZE
+ MIN_ITEM_LEN
);
2032 max_num_of_entries
= (blocksize
- BLKH_SIZE
- IH_SIZE
) /
2033 (DEH_SIZE
+ MIN_NAME_LEN
);
2035 return sizeof(struct virtual_node
) +
2036 max(max_num_of_items
* sizeof(struct virtual_item
),
2037 sizeof(struct virtual_item
) + sizeof(struct direntry_uarea
) +
2038 (max_num_of_entries
- 1) * sizeof(__u16
));
2041 /* maybe we should fail balancing we are going to perform when kmalloc
2042 fails several times. But now it will loop until kmalloc gets
2044 static int get_mem_for_virtual_node(struct tree_balance
*tb
)
2050 size
= get_virtual_node_size(tb
->tb_sb
, PATH_PLAST_BUFFER(tb
->tb_path
));
2052 if (size
> tb
->vn_buf_size
) {
2053 /* we have to allocate more memory for virtual node */
2055 /* free memory allocated before */
2057 /* this is not needed if kfree is atomic */
2061 /* virtual node requires now more memory */
2062 tb
->vn_buf_size
= size
;
2064 /* get memory for virtual item */
2065 buf
= kmalloc(size
, GFP_ATOMIC
| __GFP_NOWARN
);
2067 /* getting memory with GFP_KERNEL priority may involve
2068 balancing now (due to indirect_to_direct conversion on
2069 dcache shrinking). So, release path and collected
2071 free_buffers_in_tb(tb
);
2072 buf
= kmalloc(size
, GFP_NOFS
);
2074 tb
->vn_buf_size
= 0;
2078 return REPEAT_SEARCH
;
2084 if (check_fs
&& FILESYSTEM_CHANGED_TB(tb
))
2085 return REPEAT_SEARCH
;
2090 #ifdef CONFIG_REISERFS_CHECK
2091 static void tb_buffer_sanity_check(struct super_block
*p_s_sb
,
2092 struct buffer_head
*p_s_bh
,
2093 const char *descr
, int level
)
2096 if (atomic_read(&(p_s_bh
->b_count
)) <= 0) {
2098 reiserfs_panic(p_s_sb
, "jmacd-1", "negative or zero "
2099 "reference counter for buffer %s[%d] "
2100 "(%b)", descr
, level
, p_s_bh
);
2103 if (!buffer_uptodate(p_s_bh
)) {
2104 reiserfs_panic(p_s_sb
, "jmacd-2", "buffer is not up "
2105 "to date %s[%d] (%b)",
2106 descr
, level
, p_s_bh
);
2109 if (!B_IS_IN_TREE(p_s_bh
)) {
2110 reiserfs_panic(p_s_sb
, "jmacd-3", "buffer is not "
2111 "in tree %s[%d] (%b)",
2112 descr
, level
, p_s_bh
);
2115 if (p_s_bh
->b_bdev
!= p_s_sb
->s_bdev
) {
2116 reiserfs_panic(p_s_sb
, "jmacd-4", "buffer has wrong "
2117 "device %s[%d] (%b)",
2118 descr
, level
, p_s_bh
);
2121 if (p_s_bh
->b_size
!= p_s_sb
->s_blocksize
) {
2122 reiserfs_panic(p_s_sb
, "jmacd-5", "buffer has wrong "
2123 "blocksize %s[%d] (%b)",
2124 descr
, level
, p_s_bh
);
2127 if (p_s_bh
->b_blocknr
> SB_BLOCK_COUNT(p_s_sb
)) {
2128 reiserfs_panic(p_s_sb
, "jmacd-6", "buffer block "
2129 "number too high %s[%d] (%b)",
2130 descr
, level
, p_s_bh
);
2135 static void tb_buffer_sanity_check(struct super_block
*p_s_sb
,
2136 struct buffer_head
*p_s_bh
,
2137 const char *descr
, int level
)
2142 static int clear_all_dirty_bits(struct super_block
*s
, struct buffer_head
*bh
)
2144 return reiserfs_prepare_for_journal(s
, bh
, 0);
2147 static int wait_tb_buffers_until_unlocked(struct tree_balance
*p_s_tb
)
2149 struct buffer_head
*locked
;
2150 #ifdef CONFIG_REISERFS_CHECK
2151 int repeat_counter
= 0;
2159 for (i
= p_s_tb
->tb_path
->path_length
;
2160 !locked
&& i
> ILLEGAL_PATH_ELEMENT_OFFSET
; i
--) {
2161 if (PATH_OFFSET_PBUFFER(p_s_tb
->tb_path
, i
)) {
2162 /* if I understand correctly, we can only be sure the last buffer
2163 ** in the path is in the tree --clm
2165 #ifdef CONFIG_REISERFS_CHECK
2166 if (PATH_PLAST_BUFFER(p_s_tb
->tb_path
) ==
2167 PATH_OFFSET_PBUFFER(p_s_tb
->tb_path
, i
)) {
2168 tb_buffer_sanity_check(p_s_tb
->tb_sb
,
2176 if (!clear_all_dirty_bits(p_s_tb
->tb_sb
,
2181 PATH_OFFSET_PBUFFER(p_s_tb
->tb_path
,
2187 for (i
= 0; !locked
&& i
< MAX_HEIGHT
&& p_s_tb
->insert_size
[i
];
2190 if (p_s_tb
->lnum
[i
]) {
2193 tb_buffer_sanity_check(p_s_tb
->tb_sb
,
2196 if (!clear_all_dirty_bits
2197 (p_s_tb
->tb_sb
, p_s_tb
->L
[i
]))
2198 locked
= p_s_tb
->L
[i
];
2201 if (!locked
&& p_s_tb
->FL
[i
]) {
2202 tb_buffer_sanity_check(p_s_tb
->tb_sb
,
2205 if (!clear_all_dirty_bits
2206 (p_s_tb
->tb_sb
, p_s_tb
->FL
[i
]))
2207 locked
= p_s_tb
->FL
[i
];
2210 if (!locked
&& p_s_tb
->CFL
[i
]) {
2211 tb_buffer_sanity_check(p_s_tb
->tb_sb
,
2214 if (!clear_all_dirty_bits
2215 (p_s_tb
->tb_sb
, p_s_tb
->CFL
[i
]))
2216 locked
= p_s_tb
->CFL
[i
];
2221 if (!locked
&& (p_s_tb
->rnum
[i
])) {
2224 tb_buffer_sanity_check(p_s_tb
->tb_sb
,
2227 if (!clear_all_dirty_bits
2228 (p_s_tb
->tb_sb
, p_s_tb
->R
[i
]))
2229 locked
= p_s_tb
->R
[i
];
2232 if (!locked
&& p_s_tb
->FR
[i
]) {
2233 tb_buffer_sanity_check(p_s_tb
->tb_sb
,
2236 if (!clear_all_dirty_bits
2237 (p_s_tb
->tb_sb
, p_s_tb
->FR
[i
]))
2238 locked
= p_s_tb
->FR
[i
];
2241 if (!locked
&& p_s_tb
->CFR
[i
]) {
2242 tb_buffer_sanity_check(p_s_tb
->tb_sb
,
2245 if (!clear_all_dirty_bits
2246 (p_s_tb
->tb_sb
, p_s_tb
->CFR
[i
]))
2247 locked
= p_s_tb
->CFR
[i
];
2251 /* as far as I can tell, this is not required. The FEB list seems
2252 ** to be full of newly allocated nodes, which will never be locked,
2253 ** dirty, or anything else.
2254 ** To be safe, I'm putting in the checks and waits in. For the moment,
2255 ** they are needed to keep the code in journal.c from complaining
2256 ** about the buffer. That code is inside CONFIG_REISERFS_CHECK as well.
2259 for (i
= 0; !locked
&& i
< MAX_FEB_SIZE
; i
++) {
2260 if (p_s_tb
->FEB
[i
]) {
2261 if (!clear_all_dirty_bits
2262 (p_s_tb
->tb_sb
, p_s_tb
->FEB
[i
]))
2263 locked
= p_s_tb
->FEB
[i
];
2268 #ifdef CONFIG_REISERFS_CHECK
2270 if ((repeat_counter
% 10000) == 0) {
2271 reiserfs_warning(p_s_tb
->tb_sb
, "reiserfs-8200",
2272 "too many iterations waiting "
2273 "for buffer to unlock "
2276 /* Don't loop forever. Try to recover from possible error. */
2278 return (FILESYSTEM_CHANGED_TB(p_s_tb
)) ?
2279 REPEAT_SEARCH
: CARRY_ON
;
2282 __wait_on_buffer(locked
);
2283 if (FILESYSTEM_CHANGED_TB(p_s_tb
)) {
2284 return REPEAT_SEARCH
;
2293 /* Prepare for balancing, that is
2294 * get all necessary parents, and neighbors;
2295 * analyze what and where should be moved;
2296 * get sufficient number of new nodes;
2297 * Balancing will start only after all resources will be collected at a time.
2299 * When ported to SMP kernels, only at the last moment after all needed nodes
2300 * are collected in cache, will the resources be locked using the usual
2301 * textbook ordered lock acquisition algorithms. Note that ensuring that
2302 * this code neither write locks what it does not need to write lock nor locks out of order
2303 * will be a pain in the butt that could have been avoided. Grumble grumble. -Hans
2305 * fix is meant in the sense of render unchanging
2307 * Latency might be improved by first gathering a list of what buffers are needed
2308 * and then getting as many of them in parallel as possible? -Hans
2311 * op_mode i - insert, d - delete, c - cut (truncate), p - paste (append)
2312 * tb tree_balance structure;
2313 * inum item number in S[h];
2314 * pos_in_item - comment this if you can
2315 * ins_ih & ins_sd are used when inserting
2316 * Returns: 1 - schedule occurred while the function worked;
2317 * 0 - schedule didn't occur while the function worked;
2318 * -1 - if no_disk_space
2321 int fix_nodes(int n_op_mode
, struct tree_balance
*p_s_tb
, struct item_head
*p_s_ins_ih
, // item head of item being inserted
2322 const void *data
// inserted item or data to be pasted
2325 int n_ret_value
, n_h
, n_item_num
= PATH_LAST_POSITION(p_s_tb
->tb_path
);
2328 /* we set wait_tb_buffers_run when we have to restore any dirty bits cleared
2329 ** during wait_tb_buffers_run
2331 int wait_tb_buffers_run
= 0;
2332 struct buffer_head
*p_s_tbS0
= PATH_PLAST_BUFFER(p_s_tb
->tb_path
);
2334 ++REISERFS_SB(p_s_tb
->tb_sb
)->s_fix_nodes
;
2336 n_pos_in_item
= p_s_tb
->tb_path
->pos_in_item
;
2338 p_s_tb
->fs_gen
= get_generation(p_s_tb
->tb_sb
);
2340 /* we prepare and log the super here so it will already be in the
2341 ** transaction when do_balance needs to change it.
2342 ** This way do_balance won't have to schedule when trying to prepare
2343 ** the super for logging
2345 reiserfs_prepare_for_journal(p_s_tb
->tb_sb
,
2346 SB_BUFFER_WITH_SB(p_s_tb
->tb_sb
), 1);
2347 journal_mark_dirty(p_s_tb
->transaction_handle
, p_s_tb
->tb_sb
,
2348 SB_BUFFER_WITH_SB(p_s_tb
->tb_sb
));
2349 if (FILESYSTEM_CHANGED_TB(p_s_tb
))
2350 return REPEAT_SEARCH
;
2352 /* if it possible in indirect_to_direct conversion */
2353 if (buffer_locked(p_s_tbS0
)) {
2354 __wait_on_buffer(p_s_tbS0
);
2355 if (FILESYSTEM_CHANGED_TB(p_s_tb
))
2356 return REPEAT_SEARCH
;
2358 #ifdef CONFIG_REISERFS_CHECK
2360 print_cur_tb("fix_nodes");
2361 reiserfs_panic(p_s_tb
->tb_sb
, "PAP-8305",
2362 "there is pending do_balance");
2365 if (!buffer_uptodate(p_s_tbS0
) || !B_IS_IN_TREE(p_s_tbS0
)) {
2366 reiserfs_panic(p_s_tb
->tb_sb
, "PAP-8320", "S[0] (%b %z) is "
2367 "not uptodate at the beginning of fix_nodes "
2368 "or not in tree (mode %c)",
2369 p_s_tbS0
, p_s_tbS0
, n_op_mode
);
2372 /* Check parameters. */
2373 switch (n_op_mode
) {
2375 if (n_item_num
<= 0 || n_item_num
> B_NR_ITEMS(p_s_tbS0
))
2376 reiserfs_panic(p_s_tb
->tb_sb
, "PAP-8330", "Incorrect "
2377 "item number %d (in S0 - %d) in case "
2378 "of insert", n_item_num
,
2379 B_NR_ITEMS(p_s_tbS0
));
2384 if (n_item_num
< 0 || n_item_num
>= B_NR_ITEMS(p_s_tbS0
)) {
2385 print_block(p_s_tbS0
, 0, -1, -1);
2386 reiserfs_panic(p_s_tb
->tb_sb
, "PAP-8335", "Incorrect "
2387 "item number(%d); mode = %c "
2389 n_item_num
, n_op_mode
,
2390 p_s_tb
->insert_size
[0]);
2394 reiserfs_panic(p_s_tb
->tb_sb
, "PAP-8340", "Incorrect mode "
2399 if (get_mem_for_virtual_node(p_s_tb
) == REPEAT_SEARCH
)
2400 // FIXME: maybe -ENOMEM when tb->vn_buf == 0? Now just repeat
2401 return REPEAT_SEARCH
;
2403 /* Starting from the leaf level; for all levels n_h of the tree. */
2404 for (n_h
= 0; n_h
< MAX_HEIGHT
&& p_s_tb
->insert_size
[n_h
]; n_h
++) {
2405 if ((n_ret_value
= get_direct_parent(p_s_tb
, n_h
)) != CARRY_ON
) {
2410 check_balance(n_op_mode
, p_s_tb
, n_h
, n_item_num
,
2411 n_pos_in_item
, p_s_ins_ih
,
2412 data
)) != CARRY_ON
) {
2413 if (n_ret_value
== NO_BALANCING_NEEDED
) {
2414 /* No balancing for higher levels needed. */
2416 get_neighbors(p_s_tb
, n_h
)) != CARRY_ON
) {
2419 if (n_h
!= MAX_HEIGHT
- 1)
2420 p_s_tb
->insert_size
[n_h
+ 1] = 0;
2421 /* ok, analysis and resource gathering are complete */
2427 if ((n_ret_value
= get_neighbors(p_s_tb
, n_h
)) != CARRY_ON
) {
2431 if ((n_ret_value
= get_empty_nodes(p_s_tb
, n_h
)) != CARRY_ON
) {
2432 goto repeat
; /* No disk space, or schedule occurred and
2433 analysis may be invalid and needs to be redone. */
2436 if (!PATH_H_PBUFFER(p_s_tb
->tb_path
, n_h
)) {
2437 /* We have a positive insert size but no nodes exist on this
2438 level, this means that we are creating a new root. */
2440 RFALSE(p_s_tb
->blknum
[n_h
] != 1,
2441 "PAP-8350: creating new empty root");
2443 if (n_h
< MAX_HEIGHT
- 1)
2444 p_s_tb
->insert_size
[n_h
+ 1] = 0;
2445 } else if (!PATH_H_PBUFFER(p_s_tb
->tb_path
, n_h
+ 1)) {
2446 if (p_s_tb
->blknum
[n_h
] > 1) {
2447 /* The tree needs to be grown, so this node S[n_h]
2448 which is the root node is split into two nodes,
2449 and a new node (S[n_h+1]) will be created to
2450 become the root node. */
2452 RFALSE(n_h
== MAX_HEIGHT
- 1,
2453 "PAP-8355: attempt to create too high of a tree");
2455 p_s_tb
->insert_size
[n_h
+ 1] =
2457 KEY_SIZE
) * (p_s_tb
->blknum
[n_h
] - 1) +
2459 } else if (n_h
< MAX_HEIGHT
- 1)
2460 p_s_tb
->insert_size
[n_h
+ 1] = 0;
2462 p_s_tb
->insert_size
[n_h
+ 1] =
2463 (DC_SIZE
+ KEY_SIZE
) * (p_s_tb
->blknum
[n_h
] - 1);
2466 if ((n_ret_value
= wait_tb_buffers_until_unlocked(p_s_tb
)) == CARRY_ON
) {
2467 if (FILESYSTEM_CHANGED_TB(p_s_tb
)) {
2468 wait_tb_buffers_run
= 1;
2469 n_ret_value
= REPEAT_SEARCH
;
2475 wait_tb_buffers_run
= 1;
2480 // fix_nodes was unable to perform its calculation due to
2481 // filesystem got changed under us, lack of free disk space or i/o
2482 // failure. If the first is the case - the search will be
2483 // repeated. For now - free all resources acquired so far except
2484 // for the new allocated nodes
2488 /* Release path buffers. */
2489 if (wait_tb_buffers_run
) {
2490 pathrelse_and_restore(p_s_tb
->tb_sb
, p_s_tb
->tb_path
);
2492 pathrelse(p_s_tb
->tb_path
);
2494 /* brelse all resources collected for balancing */
2495 for (i
= 0; i
< MAX_HEIGHT
; i
++) {
2496 if (wait_tb_buffers_run
) {
2497 reiserfs_restore_prepared_buffer(p_s_tb
->tb_sb
,
2499 reiserfs_restore_prepared_buffer(p_s_tb
->tb_sb
,
2501 reiserfs_restore_prepared_buffer(p_s_tb
->tb_sb
,
2503 reiserfs_restore_prepared_buffer(p_s_tb
->tb_sb
,
2505 reiserfs_restore_prepared_buffer(p_s_tb
->tb_sb
,
2508 reiserfs_restore_prepared_buffer(p_s_tb
->tb_sb
,
2513 brelse(p_s_tb
->L
[i
]);
2514 p_s_tb
->L
[i
] = NULL
;
2515 brelse(p_s_tb
->R
[i
]);
2516 p_s_tb
->R
[i
] = NULL
;
2517 brelse(p_s_tb
->FL
[i
]);
2518 p_s_tb
->FL
[i
] = NULL
;
2519 brelse(p_s_tb
->FR
[i
]);
2520 p_s_tb
->FR
[i
] = NULL
;
2521 brelse(p_s_tb
->CFL
[i
]);
2522 p_s_tb
->CFL
[i
] = NULL
;
2523 brelse(p_s_tb
->CFR
[i
]);
2524 p_s_tb
->CFR
[i
] = NULL
;
2527 if (wait_tb_buffers_run
) {
2528 for (i
= 0; i
< MAX_FEB_SIZE
; i
++) {
2529 if (p_s_tb
->FEB
[i
]) {
2530 reiserfs_restore_prepared_buffer
2531 (p_s_tb
->tb_sb
, p_s_tb
->FEB
[i
]);
2540 /* Anatoly will probably forgive me renaming p_s_tb to tb. I just
2541 wanted to make lines shorter */
2542 void unfix_nodes(struct tree_balance
*tb
)
2546 /* Release path buffers. */
2547 pathrelse_and_restore(tb
->tb_sb
, tb
->tb_path
);
2549 /* brelse all resources collected for balancing */
2550 for (i
= 0; i
< MAX_HEIGHT
; i
++) {
2551 reiserfs_restore_prepared_buffer(tb
->tb_sb
, tb
->L
[i
]);
2552 reiserfs_restore_prepared_buffer(tb
->tb_sb
, tb
->R
[i
]);
2553 reiserfs_restore_prepared_buffer(tb
->tb_sb
, tb
->FL
[i
]);
2554 reiserfs_restore_prepared_buffer(tb
->tb_sb
, tb
->FR
[i
]);
2555 reiserfs_restore_prepared_buffer(tb
->tb_sb
, tb
->CFL
[i
]);
2556 reiserfs_restore_prepared_buffer(tb
->tb_sb
, tb
->CFR
[i
]);
2566 /* deal with list of allocated (used and unused) nodes */
2567 for (i
= 0; i
< MAX_FEB_SIZE
; i
++) {
2569 b_blocknr_t blocknr
= tb
->FEB
[i
]->b_blocknr
;
2570 /* de-allocated block which was not used by balancing and
2571 bforget about buffer for it */
2573 reiserfs_free_block(tb
->transaction_handle
, NULL
,
2577 /* release used as new nodes including a new root */
2578 brelse(tb
->used
[i
]);