summaryrefslogtreecommitdiff
path: root/fs/reiserfs/fix_node.c
diff options
context:
space:
mode:
authorLinus Torvalds <torvalds@g5.osdl.org>2005-07-12 20:21:28 -0700
committerLinus Torvalds <torvalds@g5.osdl.org>2005-07-12 20:21:28 -0700
commitbd4c625c061c2a38568d0add3478f59172455159 (patch)
tree1c44a17c55bce2ee7ad5ea3d15a208ecc0955f74 /fs/reiserfs/fix_node.c
parent7fa94c8868edfef8cb6a201fcc9a5078b7b961da (diff)
reiserfs: run scripts/Lindent on reiserfs code
This was a pure indentation change, using: scripts/Lindent fs/reiserfs/*.c include/linux/reiserfs_*.h to make reiserfs match the regular Linux indentation style. As Jeff Mahoney <jeffm@suse.com> writes: The ReiserFS code is a mix of a number of different coding styles, sometimes different even from line-to-line. Since the code has been relatively stable for quite some time and there are few outstanding patches to be applied, it is time to reformat the code to conform to the Linux style standard outlined in Documentation/CodingStyle. This patch contains the result of running scripts/Lindent against fs/reiserfs/*.c and include/linux/reiserfs_*.h. There are places where the code can be made to look better, but I'd rather keep those patches separate so that there isn't a subtle by-hand hand accident in the middle of a huge patch. To be clear: This patch is reformatting *only*. A number of patches may follow that continue to make the code more consistent with the Linux coding style. Hans wasn't particularly enthusiastic about these patches, but said he wouldn't really oppose them either. Signed-off-by: Linus Torvalds <torvalds@osdl.org>
Diffstat (limited to 'fs/reiserfs/fix_node.c')
-rw-r--r--fs/reiserfs/fix_node.c4051
1 files changed, 2079 insertions, 1972 deletions
diff --git a/fs/reiserfs/fix_node.c b/fs/reiserfs/fix_node.c
index e4f64be9e15..2706e2adffa 100644
--- a/fs/reiserfs/fix_node.c
+++ b/fs/reiserfs/fix_node.c
@@ -34,14 +34,12 @@
**
**/
-
#include <linux/config.h>
#include <linux/time.h>
#include <linux/string.h>
#include <linux/reiserfs_fs.h>
#include <linux/buffer_head.h>
-
/* To make any changes in the tree we find a node, that contains item
to be changed/deleted or position in the node we insert a new item
to. We call this node S. To do balancing we need to decide what we
@@ -56,490 +54,522 @@
have to have if we do not any shiftings, if we shift to left/right
neighbor or to both. */
-
/* taking item number in virtual node, returns number of item, that it has in source buffer */
-static inline int old_item_num (int new_num, int affected_item_num, int mode)
+static inline int old_item_num(int new_num, int affected_item_num, int mode)
{
- if (mode == M_PASTE || mode == M_CUT || new_num < affected_item_num)
- return new_num;
+ if (mode == M_PASTE || mode == M_CUT || new_num < affected_item_num)
+ return new_num;
- if (mode == M_INSERT) {
+ if (mode == M_INSERT) {
- RFALSE( new_num == 0,
- "vs-8005: for INSERT mode and item number of inserted item");
+ RFALSE(new_num == 0,
+ "vs-8005: for INSERT mode and item number of inserted item");
- return new_num - 1;
- }
+ return new_num - 1;
+ }
- RFALSE( mode != M_DELETE,
- "vs-8010: old_item_num: mode must be M_DELETE (mode = \'%c\'", mode);
- /* delete mode */
- return new_num + 1;
+ RFALSE(mode != M_DELETE,
+ "vs-8010: old_item_num: mode must be M_DELETE (mode = \'%c\'",
+ mode);
+ /* delete mode */
+ return new_num + 1;
}
-static void create_virtual_node (struct tree_balance * tb, int h)
+static void create_virtual_node(struct tree_balance *tb, int h)
{
- struct item_head * ih;
- struct virtual_node * vn = tb->tb_vn;
- int new_num;
- struct buffer_head * Sh; /* this comes from tb->S[h] */
+ struct item_head *ih;
+ struct virtual_node *vn = tb->tb_vn;
+ int new_num;
+ struct buffer_head *Sh; /* this comes from tb->S[h] */
- Sh = PATH_H_PBUFFER (tb->tb_path, h);
+ Sh = PATH_H_PBUFFER(tb->tb_path, h);
- /* size of changed node */
- vn->vn_size = MAX_CHILD_SIZE (Sh) - B_FREE_SPACE (Sh) + tb->insert_size[h];
+ /* size of changed node */
+ vn->vn_size =
+ MAX_CHILD_SIZE(Sh) - B_FREE_SPACE(Sh) + tb->insert_size[h];
- /* for internal nodes array if virtual items is not created */
- if (h) {
- vn->vn_nr_item = (vn->vn_size - DC_SIZE) / (DC_SIZE + KEY_SIZE);
- return;
- }
-
- /* number of items in virtual node */
- vn->vn_nr_item = B_NR_ITEMS (Sh) + ((vn->vn_mode == M_INSERT)? 1 : 0) - ((vn->vn_mode == M_DELETE)? 1 : 0);
-
- /* first virtual item */
- vn->vn_vi = (struct virtual_item *)(tb->tb_vn + 1);
- memset (vn->vn_vi, 0, vn->vn_nr_item * sizeof (struct virtual_item));
- vn->vn_free_ptr += vn->vn_nr_item * sizeof (struct virtual_item);
-
-
- /* first item in the node */
- ih = B_N_PITEM_HEAD (Sh, 0);
-
- /* define the mergeability for 0-th item (if it is not being deleted) */
- if (op_is_left_mergeable (&(ih->ih_key), Sh->b_size) && (vn->vn_mode != M_DELETE || vn->vn_affected_item_num))
- vn->vn_vi[0].vi_type |= VI_TYPE_LEFT_MERGEABLE;
-
- /* go through all items those remain in the virtual node (except for the new (inserted) one) */
- for (new_num = 0; new_num < vn->vn_nr_item; new_num ++) {
- int j;
- struct virtual_item * vi = vn->vn_vi + new_num;
- int is_affected = ((new_num != vn->vn_affected_item_num) ? 0 : 1);
-
-
- if (is_affected && vn->vn_mode == M_INSERT)
- continue;
-
- /* get item number in source node */
- j = old_item_num (new_num, vn->vn_affected_item_num, vn->vn_mode);
-
- vi->vi_item_len += ih_item_len(ih + j) + IH_SIZE;
- vi->vi_ih = ih + j;
- vi->vi_item = B_I_PITEM (Sh, ih + j);
- vi->vi_uarea = vn->vn_free_ptr;
-
- // FIXME: there is no check, that item operation did not
- // consume too much memory
- vn->vn_free_ptr += op_create_vi (vn, vi, is_affected, tb->insert_size [0]);
- if (tb->vn_buf + tb->vn_buf_size < vn->vn_free_ptr)
- reiserfs_panic (tb->tb_sb, "vs-8030: create_virtual_node: "
- "virtual node space consumed");
-
- if (!is_affected)
- /* this is not being changed */
- continue;
-
- if (vn->vn_mode == M_PASTE || vn->vn_mode == M_CUT) {
- vn->vn_vi[new_num].vi_item_len += tb->insert_size[0];
- vi->vi_new_data = vn->vn_data; // pointer to data which is going to be pasted
+ /* for internal nodes array if virtual items is not created */
+ if (h) {
+ vn->vn_nr_item = (vn->vn_size - DC_SIZE) / (DC_SIZE + KEY_SIZE);
+ return;
}
- }
-
-
- /* virtual inserted item is not defined yet */
- if (vn->vn_mode == M_INSERT) {
- struct virtual_item * vi = vn->vn_vi + vn->vn_affected_item_num;
-
- RFALSE( vn->vn_ins_ih == 0,
- "vs-8040: item header of inserted item is not specified");
- vi->vi_item_len = tb->insert_size[0];
- vi->vi_ih = vn->vn_ins_ih;
- vi->vi_item = vn->vn_data;
- vi->vi_uarea = vn->vn_free_ptr;
-
- op_create_vi (vn, vi, 0/*not pasted or cut*/, tb->insert_size [0]);
- }
-
- /* set right merge flag we take right delimiting key and check whether it is a mergeable item */
- if (tb->CFR[0]) {
- struct reiserfs_key * key;
-
- key = B_N_PDELIM_KEY (tb->CFR[0], tb->rkey[0]);
- if (op_is_left_mergeable (key, Sh->b_size) && (vn->vn_mode != M_DELETE ||
- vn->vn_affected_item_num != B_NR_ITEMS (Sh) - 1))
- vn->vn_vi[vn->vn_nr_item-1].vi_type |= VI_TYPE_RIGHT_MERGEABLE;
-#ifdef CONFIG_REISERFS_CHECK
- if (op_is_left_mergeable (key, Sh->b_size) &&
- !(vn->vn_mode != M_DELETE || vn->vn_affected_item_num != B_NR_ITEMS (Sh) - 1) ) {
- /* we delete last item and it could be merged with right neighbor's first item */
- if (!(B_NR_ITEMS (Sh) == 1 && is_direntry_le_ih (B_N_PITEM_HEAD (Sh, 0)) &&
- I_ENTRY_COUNT (B_N_PITEM_HEAD (Sh, 0)) == 1)) {
- /* node contains more than 1 item, or item is not directory item, or this item contains more than 1 entry */
- print_block (Sh, 0, -1, -1);
- reiserfs_panic (tb->tb_sb, "vs-8045: create_virtual_node: rdkey %k, affected item==%d (mode==%c) Must be %c",
- key, vn->vn_affected_item_num, vn->vn_mode, M_DELETE);
- } else
- /* we can delete directory item, that has only one directory entry in it */
- ;
+ /* number of items in virtual node */
+ vn->vn_nr_item =
+ B_NR_ITEMS(Sh) + ((vn->vn_mode == M_INSERT) ? 1 : 0) -
+ ((vn->vn_mode == M_DELETE) ? 1 : 0);
+
+ /* first virtual item */
+ vn->vn_vi = (struct virtual_item *)(tb->tb_vn + 1);
+ memset(vn->vn_vi, 0, vn->vn_nr_item * sizeof(struct virtual_item));
+ vn->vn_free_ptr += vn->vn_nr_item * sizeof(struct virtual_item);
+
+ /* first item in the node */
+ ih = B_N_PITEM_HEAD(Sh, 0);
+
+ /* define the mergeability for 0-th item (if it is not being deleted) */
+ if (op_is_left_mergeable(&(ih->ih_key), Sh->b_size)
+ && (vn->vn_mode != M_DELETE || vn->vn_affected_item_num))
+ vn->vn_vi[0].vi_type |= VI_TYPE_LEFT_MERGEABLE;
+
+ /* go through all items those remain in the virtual node (except for the new (inserted) one) */
+ for (new_num = 0; new_num < vn->vn_nr_item; new_num++) {
+ int j;
+ struct virtual_item *vi = vn->vn_vi + new_num;
+ int is_affected =
+ ((new_num != vn->vn_affected_item_num) ? 0 : 1);
+
+ if (is_affected && vn->vn_mode == M_INSERT)
+ continue;
+
+ /* get item number in source node */
+ j = old_item_num(new_num, vn->vn_affected_item_num,
+ vn->vn_mode);
+
+ vi->vi_item_len += ih_item_len(ih + j) + IH_SIZE;
+ vi->vi_ih = ih + j;
+ vi->vi_item = B_I_PITEM(Sh, ih + j);
+ vi->vi_uarea = vn->vn_free_ptr;
+
+ // FIXME: there is no check, that item operation did not
+ // consume too much memory
+ vn->vn_free_ptr +=
+ op_create_vi(vn, vi, is_affected, tb->insert_size[0]);
+ if (tb->vn_buf + tb->vn_buf_size < vn->vn_free_ptr)
+ reiserfs_panic(tb->tb_sb,
+ "vs-8030: create_virtual_node: "
+ "virtual node space consumed");
+
+ if (!is_affected)
+ /* this is not being changed */
+ continue;
+
+ if (vn->vn_mode == M_PASTE || vn->vn_mode == M_CUT) {
+ vn->vn_vi[new_num].vi_item_len += tb->insert_size[0];
+ vi->vi_new_data = vn->vn_data; // pointer to data which is going to be pasted
+ }
}
+
+ /* virtual inserted item is not defined yet */
+ if (vn->vn_mode == M_INSERT) {
+ struct virtual_item *vi = vn->vn_vi + vn->vn_affected_item_num;
+
+ RFALSE(vn->vn_ins_ih == 0,
+ "vs-8040: item header of inserted item is not specified");
+ vi->vi_item_len = tb->insert_size[0];
+ vi->vi_ih = vn->vn_ins_ih;
+ vi->vi_item = vn->vn_data;
+ vi->vi_uarea = vn->vn_free_ptr;
+
+ op_create_vi(vn, vi, 0 /*not pasted or cut */ ,
+ tb->insert_size[0]);
+ }
+
+ /* set right merge flag we take right delimiting key and check whether it is a mergeable item */
+ if (tb->CFR[0]) {
+ struct reiserfs_key *key;
+
+ key = B_N_PDELIM_KEY(tb->CFR[0], tb->rkey[0]);
+ if (op_is_left_mergeable(key, Sh->b_size)
+ && (vn->vn_mode != M_DELETE
+ || vn->vn_affected_item_num != B_NR_ITEMS(Sh) - 1))
+ vn->vn_vi[vn->vn_nr_item - 1].vi_type |=
+ VI_TYPE_RIGHT_MERGEABLE;
+
+#ifdef CONFIG_REISERFS_CHECK
+ if (op_is_left_mergeable(key, Sh->b_size) &&
+ !(vn->vn_mode != M_DELETE
+ || vn->vn_affected_item_num != B_NR_ITEMS(Sh) - 1)) {
+ /* we delete last item and it could be merged with right neighbor's first item */
+ if (!
+ (B_NR_ITEMS(Sh) == 1
+ && is_direntry_le_ih(B_N_PITEM_HEAD(Sh, 0))
+ && I_ENTRY_COUNT(B_N_PITEM_HEAD(Sh, 0)) == 1)) {
+ /* node contains more than 1 item, or item is not directory item, or this item contains more than 1 entry */
+ print_block(Sh, 0, -1, -1);
+ reiserfs_panic(tb->tb_sb,
+ "vs-8045: create_virtual_node: rdkey %k, affected item==%d (mode==%c) Must be %c",
+ key, vn->vn_affected_item_num,
+ vn->vn_mode, M_DELETE);
+ } else
+ /* we can delete directory item, that has only one directory entry in it */
+ ;
+ }
#endif
-
- }
-}
+ }
+}
/* using virtual node check, how many items can be shifted to left
neighbor */
-static void check_left (struct tree_balance * tb, int h, int cur_free)
+static void check_left(struct tree_balance *tb, int h, int cur_free)
{
- int i;
- struct virtual_node * vn = tb->tb_vn;
- struct virtual_item * vi;
- int d_size, ih_size;
+ int i;
+ struct virtual_node *vn = tb->tb_vn;
+ struct virtual_item *vi;
+ int d_size, ih_size;
- RFALSE( cur_free < 0, "vs-8050: cur_free (%d) < 0", cur_free);
+ RFALSE(cur_free < 0, "vs-8050: cur_free (%d) < 0", cur_free);
- /* internal level */
- if (h > 0) {
- tb->lnum[h] = cur_free / (DC_SIZE + KEY_SIZE);
- return;
- }
+ /* internal level */
+ if (h > 0) {
+ tb->lnum[h] = cur_free / (DC_SIZE + KEY_SIZE);
+ return;
+ }
- /* leaf level */
+ /* leaf level */
- if (!cur_free || !vn->vn_nr_item) {
- /* no free space or nothing to move */
- tb->lnum[h] = 0;
- tb->lbytes = -1;
- return;
- }
+ if (!cur_free || !vn->vn_nr_item) {
+ /* no free space or nothing to move */
+ tb->lnum[h] = 0;
+ tb->lbytes = -1;
+ return;
+ }
- RFALSE( !PATH_H_PPARENT (tb->tb_path, 0),
- "vs-8055: parent does not exist or invalid");
+ RFALSE(!PATH_H_PPARENT(tb->tb_path, 0),
+ "vs-8055: parent does not exist or invalid");
- vi = vn->vn_vi;
- if ((unsigned int)cur_free >= (vn->vn_size - ((vi->vi_type & VI_TYPE_LEFT_MERGEABLE) ? IH_SIZE : 0))) {
- /* all contents of S[0] fits into L[0] */
+ vi = vn->vn_vi;
+ if ((unsigned int)cur_free >=
+ (vn->vn_size -
+ ((vi->vi_type & VI_TYPE_LEFT_MERGEABLE) ? IH_SIZE : 0))) {
+ /* all contents of S[0] fits into L[0] */
- RFALSE( vn->vn_mode == M_INSERT || vn->vn_mode == M_PASTE,
- "vs-8055: invalid mode or balance condition failed");
+ RFALSE(vn->vn_mode == M_INSERT || vn->vn_mode == M_PASTE,
+ "vs-8055: invalid mode or balance condition failed");
- tb->lnum[0] = vn->vn_nr_item;
- tb->lbytes = -1;
- return;
- }
-
-
- d_size = 0, ih_size = IH_SIZE;
-
- /* first item may be merge with last item in left neighbor */
- if (vi->vi_type & VI_TYPE_LEFT_MERGEABLE)
- d_size = -((int)IH_SIZE), ih_size = 0;
-
- tb->lnum[0] = 0;
- for (i = 0; i < vn->vn_nr_item; i ++, ih_size = IH_SIZE, d_size = 0, vi ++) {
- d_size += vi->vi_item_len;
- if (cur_free >= d_size) {
- /* the item can be shifted entirely */
- cur_free -= d_size;
- tb->lnum[0] ++;
- continue;
+ tb->lnum[0] = vn->vn_nr_item;
+ tb->lbytes = -1;
+ return;
}
-
- /* the item cannot be shifted entirely, try to split it */
- /* check whether L[0] can hold ih and at least one byte of the item body */
- if (cur_free <= ih_size) {
- /* cannot shift even a part of the current item */
- tb->lbytes = -1;
- return;
+
+ d_size = 0, ih_size = IH_SIZE;
+
+ /* first item may be merge with last item in left neighbor */
+ if (vi->vi_type & VI_TYPE_LEFT_MERGEABLE)
+ d_size = -((int)IH_SIZE), ih_size = 0;
+
+ tb->lnum[0] = 0;
+ for (i = 0; i < vn->vn_nr_item;
+ i++, ih_size = IH_SIZE, d_size = 0, vi++) {
+ d_size += vi->vi_item_len;
+ if (cur_free >= d_size) {
+ /* the item can be shifted entirely */
+ cur_free -= d_size;
+ tb->lnum[0]++;
+ continue;
+ }
+
+ /* the item cannot be shifted entirely, try to split it */
+ /* check whether L[0] can hold ih and at least one byte of the item body */
+ if (cur_free <= ih_size) {
+ /* cannot shift even a part of the current item */
+ tb->lbytes = -1;
+ return;
+ }
+ cur_free -= ih_size;
+
+ tb->lbytes = op_check_left(vi, cur_free, 0, 0);
+ if (tb->lbytes != -1)
+ /* count partially shifted item */
+ tb->lnum[0]++;
+
+ break;
}
- cur_free -= ih_size;
-
- tb->lbytes = op_check_left (vi, cur_free, 0, 0);
- if (tb->lbytes != -1)
- /* count partially shifted item */
- tb->lnum[0] ++;
-
- break;
- }
-
- return;
-}
+ return;
+}
/* using virtual node check, how many items can be shifted to right
neighbor */
-static void check_right (struct tree_balance * tb, int h, int cur_free)
+static void check_right(struct tree_balance *tb, int h, int cur_free)
{
- int i;
- struct virtual_node * vn = tb->tb_vn;
- struct virtual_item * vi;
- int d_size, ih_size;
-
- RFALSE( cur_free < 0, "vs-8070: cur_free < 0");
-
- /* internal level */
- if (h > 0) {
- tb->rnum[h] = cur_free / (DC_SIZE + KEY_SIZE);
- return;
- }
-
- /* leaf level */
-
- if (!cur_free || !vn->vn_nr_item) {
- /* no free space */
- tb->rnum[h] = 0;
- tb->rbytes = -1;
- return;
- }
-
- RFALSE( !PATH_H_PPARENT (tb->tb_path, 0),
- "vs-8075: parent does not exist or invalid");
-
- vi = vn->vn_vi + vn->vn_nr_item - 1;
- if ((unsigned int)cur_free >= (vn->vn_size - ((vi->vi_type & VI_TYPE_RIGHT_MERGEABLE) ? IH_SIZE : 0))) {
- /* all contents of S[0] fits into R[0] */
-
- RFALSE( vn->vn_mode == M_INSERT || vn->vn_mode == M_PASTE,
- "vs-8080: invalid mode or balance condition failed");
-
- tb->rnum[h] = vn->vn_nr_item;
- tb->rbytes = -1;
- return;
- }
-
- d_size = 0, ih_size = IH_SIZE;
-
- /* last item may be merge with first item in right neighbor */
- if (vi->vi_type & VI_TYPE_RIGHT_MERGEABLE)
- d_size = -(int)IH_SIZE, ih_size = 0;
-
- tb->rnum[0] = 0;
- for (i = vn->vn_nr_item - 1; i >= 0; i --, d_size = 0, ih_size = IH_SIZE, vi --) {
- d_size += vi->vi_item_len;
- if (cur_free >= d_size) {
- /* the item can be shifted entirely */
- cur_free -= d_size;
- tb->rnum[0] ++;
- continue;
+ int i;
+ struct virtual_node *vn = tb->tb_vn;
+ struct virtual_item *vi;
+ int d_size, ih_size;
+
+ RFALSE(cur_free < 0, "vs-8070: cur_free < 0");
+
+ /* internal level */
+ if (h > 0) {
+ tb->rnum[h] = cur_free / (DC_SIZE + KEY_SIZE);
+ return;
}
-
- /* check whether R[0] can hold ih and at least one byte of the item body */
- if ( cur_free <= ih_size ) { /* cannot shift even a part of the current item */
- tb->rbytes = -1;
- return;
+
+ /* leaf level */
+
+ if (!cur_free || !vn->vn_nr_item) {
+ /* no free space */
+ tb->rnum[h] = 0;
+ tb->rbytes = -1;
+ return;
}
-
- /* R[0] can hold the header of the item and at least one byte of its body */
- cur_free -= ih_size; /* cur_free is still > 0 */
-
- tb->rbytes = op_check_right (vi, cur_free);
- if (tb->rbytes != -1)
- /* count partially shifted item */
- tb->rnum[0] ++;
-
- break;
- }
-
- return;
-}
+ RFALSE(!PATH_H_PPARENT(tb->tb_path, 0),
+ "vs-8075: parent does not exist or invalid");
+
+ vi = vn->vn_vi + vn->vn_nr_item - 1;
+ if ((unsigned int)cur_free >=
+ (vn->vn_size -
+ ((vi->vi_type & VI_TYPE_RIGHT_MERGEABLE) ? IH_SIZE : 0))) {
+ /* all contents of S[0] fits into R[0] */
+
+ RFALSE(vn->vn_mode == M_INSERT || vn->vn_mode == M_PASTE,
+ "vs-8080: invalid mode or balance condition failed");
+
+ tb->rnum[h] = vn->vn_nr_item;
+ tb->rbytes = -1;
+ return;
+ }
+
+ d_size = 0, ih_size = IH_SIZE;
+
+ /* last item may be merge with first item in right neighbor */
+ if (vi->vi_type & VI_TYPE_RIGHT_MERGEABLE)
+ d_size = -(int)IH_SIZE, ih_size = 0;
+
+ tb->rnum[0] = 0;
+ for (i = vn->vn_nr_item - 1; i >= 0;
+ i--, d_size = 0, ih_size = IH_SIZE, vi--) {
+ d_size += vi->vi_item_len;
+ if (cur_free >= d_size) {
+ /* the item can be shifted entirely */
+ cur_free -= d_size;
+ tb->rnum[0]++;
+ continue;
+ }
+
+ /* check whether R[0] can hold ih and at least one byte of the item body */
+ if (cur_free <= ih_size) { /* cannot shift even a part of the current item */
+ tb->rbytes = -1;
+ return;
+ }
+
+ /* R[0] can hold the header of the item and at least one byte of its body */
+ cur_free -= ih_size; /* cur_free is still > 0 */
+
+ tb->rbytes = op_check_right(vi, cur_free);
+ if (tb->rbytes != -1)
+ /* count partially shifted item */
+ tb->rnum[0]++;
+
+ break;
+ }
+
+ return;
+}
/*
* from - number of items, which are shifted to left neighbor entirely
* to - number of item, which are shifted to right neighbor entirely
* from_bytes - number of bytes of boundary item (or directory entries) which are shifted to left neighbor
* to_bytes - number of bytes of boundary item (or directory entries) which are shifted to right neighbor */
-static int get_num_ver (int mode, struct tree_balance * tb, int h,
- int from, int from_bytes,
- int to, int to_bytes,
- short * snum012, int flow
- )
+static int get_num_ver(int mode, struct tree_balance *tb, int h,
+ int from, int from_bytes,
+ int to, int to_bytes, short *snum012, int flow)
{
- int i;
- int cur_free;
- // int bytes;
- int units;
- struct virtual_node * vn = tb->tb_vn;
- // struct virtual_item * vi;
-
- int total_node_size, max_node_size, current_item_size;
- int needed_nodes;
- int start_item, /* position of item we start filling node from */
- end_item, /* position of item we finish filling node by */
- start_bytes,/* number of first bytes (entries for directory) of start_item-th item
- we do not include into node that is being filled */
- end_bytes; /* number of last bytes (entries for directory) of end_item-th item
- we do node include into node that is being filled */
- int split_item_positions[2]; /* these are positions in virtual item of
- items, that are split between S[0] and
- S1new and S1new and S2new */
-
- split_item_positions[0] = -1;
- split_item_positions[1] = -1;
-
- /* We only create additional nodes if we are in insert or paste mode
- or we are in replace mode at the internal level. If h is 0 and
- the mode is M_REPLACE then in fix_nodes we change the mode to
- paste or insert before we get here in the code. */
- RFALSE( tb->insert_size[h] < 0 || (mode != M_INSERT && mode != M_PASTE),
- "vs-8100: insert_size < 0 in overflow");
-
- max_node_size = MAX_CHILD_SIZE (PATH_H_PBUFFER (tb->tb_path, h));
-
- /* snum012 [0-2] - number of items, that lay
- to S[0], first new node and second new node */
- snum012[3] = -1; /* s1bytes */
- snum012[4] = -1; /* s2bytes */
-
- /* internal level */
- if (h > 0) {
- i = ((to - from) * (KEY_SIZE + DC_SIZE) + DC_SIZE);
- if (i == max_node_size)
- return 1;
- return (i / max_node_size + 1);
- }
-
- /* leaf level */
- needed_nodes = 1;
- total_node_size = 0;
- cur_free = max_node_size;
-
- // start from 'from'-th item
- start_item = from;
- // skip its first 'start_bytes' units
- start_bytes = ((from_bytes != -1) ? from_bytes : 0);
-
- // last included item is the 'end_item'-th one
- end_item = vn->vn_nr_item - to - 1;
- // do not count last 'end_bytes' units of 'end_item'-th item
- end_bytes = (to_bytes != -1) ? to_bytes : 0;
-
- /* go through all item beginning from the start_item-th item and ending by
- the end_item-th item. Do not count first 'start_bytes' units of
- 'start_item'-th item and last 'end_bytes' of 'end_item'-th item */
-
- for (i = start_item; i <= end_item; i ++) {
- struct virtual_item * vi = vn->vn_vi + i;
- int skip_from_end = ((i == end_item) ? end_bytes : 0);
-
- RFALSE( needed_nodes > 3, "vs-8105: too many nodes are needed");
-
- /* get size of current item */
- current_item_size = vi->vi_item_len;
-
- /* do not take in calculation head part (from_bytes) of from-th item */
- current_item_size -= op_part_size (vi, 0/*from start*/, start_bytes);
-
- /* do not take in calculation tail part of last item */
- current_item_size -= op_part_size (vi, 1/*from end*/, skip_from_end);
-
- /* if item fits into current node entierly */
- if (total_node_size + current_item_size <= max_node_size) {
- snum012[needed_nodes - 1] ++;
- total_node_size += current_item_size;
- start_bytes = 0;
- continue;
+ int i;
+ int cur_free;
+ // int bytes;
+ int units;
+ struct virtual_node *vn = tb->tb_vn;
+ // struct virtual_item * vi;
+
+ int total_node_size, max_node_size, current_item_size;
+ int needed_nodes;
+ int start_item, /* position of item we start filling node from */
+ end_item, /* position of item we finish filling node by */
+ start_bytes, /* number of first bytes (entries for directory) of start_item-th item
+ we do not include into node that is being filled */
+ end_bytes; /* number of last bytes (entries for directory) of end_item-th item
+ we do node include into node that is being filled */
+ int split_item_positions[2]; /* these are positions in virtual item of
+ items, that are split between S[0] and
+ S1new and S1new and S2new */
+
+ split_item_positions[0] = -1;
+ split_item_positions[1] = -1;
+
+ /* We only create additional nodes if we are in insert or paste mode
+ or we are in replace mode at the internal level. If h is 0 and
+ the mode is M_REPLACE then in fix_nodes we change the mode to
+ paste or insert before we get here in the code. */
+ RFALSE(tb->insert_size[h] < 0 || (mode != M_INSERT && mode != M_PASTE),
+ "vs-8100: insert_size < 0 in overflow");
+
+ max_node_size = MAX_CHILD_SIZE(PATH_H_PBUFFER(tb->tb_path, h));
+
+ /* snum012 [0-2] - number of items, that lay
+ to S[0], first new node and second new node */
+ snum012[3] = -1; /* s1bytes */
+ snum012[4] = -1; /* s2bytes */
+
+ /* internal level */
+ if (h > 0) {
+ i = ((to - from) * (KEY_SIZE + DC_SIZE) + DC_SIZE);
+ if (i == max_node_size)
+ return 1;
+ return (i / max_node_size + 1);
}
- if (current_item_size > max_node_size) {
- /* virtual item length is longer, than max size of item in
- a node. It is impossible for direct item */
- RFALSE( is_direct_le_ih (vi->vi_ih),
- "vs-8110: "
- "direct item length is %d. It can not be longer than %d",
- current_item_size, max_node_size);
- /* we will try to split it */
- flow = 1;
+ /* leaf level */
+ needed_nodes = 1;
+ total_node_size = 0;
+ cur_free = max_node_size;
+
+ // start from 'from'-th item
+ start_item = from;
+ // skip its first 'start_bytes' units
+ start_bytes = ((from_bytes != -1) ? from_bytes : 0);
+
+ // last included item is the 'end_item'-th one
+ end_item = vn->vn_nr_item - to - 1;
+ // do not count last 'end_bytes' units of 'end_item'-th item
+ end_bytes = (to_bytes != -1) ? to_bytes : 0;
+
+ /* go through all item beginning from the start_item-th item and ending by
+ the end_item-th item. Do not count first 'start_bytes' units of
+ 'start_item'-th item and last 'end_bytes' of 'end_item'-th item */
+
+ for (i = start_item; i <= end_item; i++) {
+ struct virtual_item *vi = vn->vn_vi + i;
+ int skip_from_end = ((i == end_item) ? end_bytes : 0);
+
+ RFALSE(needed_nodes > 3, "vs-8105: too many nodes are needed");
+
+ /* get size of current item */
+ current_item_size = vi->vi_item_len;
+
+ /* do not take in calculation head part (from_bytes) of from-th item */
+ current_item_size -=
+ op_part_size(vi, 0 /*from start */ , start_bytes);
+
+ /* do not take in calculation tail part of last item */
+ current_item_size -=
+ op_part_size(vi, 1 /*from end */ , skip_from_end);
+
+ /* if item fits into current node entierly */
+ if (total_node_size + current_item_size <= max_node_size) {
+ snum012[needed_nodes - 1]++;
+ total_node_size += current_item_size;
+ start_bytes = 0;
+ continue;
+ }
+
+ if (current_item_size > max_node_size) {
+ /* virtual item length is longer, than max size of item in
+ a node. It is impossible for direct item */
+ RFALSE(is_direct_le_ih(vi->vi_ih),
+ "vs-8110: "
+ "direct item length is %d. It can not be longer than %d",
+ current_item_size, max_node_size);
+ /* we will try to split it */
+ flow = 1;
+ }
+
+ if (!flow) {
+ /* as we do not split items, take new node and continue */
+ needed_nodes++;
+ i--;
+ total_node_size = 0;
+ continue;
+ }
+ // calculate number of item units which fit into node being
+ // filled
+ {
+ int free_space;
+
+ free_space = max_node_size - total_node_size - IH_SIZE;
+ units =
+ op_check_left(vi, free_space, start_bytes,
+ skip_from_end);
+ if (units == -1) {
+ /* nothing fits into current node, take new node and continue */
+ needed_nodes++, i--, total_node_size = 0;
+ continue;
+ }
+ }
+
+ /* something fits into the current node */
+ //if (snum012[3] != -1 || needed_nodes != 1)
+ // reiserfs_panic (tb->tb_sb, "vs-8115: get_num_ver: too many nodes required");
+ //snum012[needed_nodes - 1 + 3] = op_unit_num (vi) - start_bytes - units;
+ start_bytes += units;
+ snum012[needed_nodes - 1 + 3] = units;
+
+ if (needed_nodes > 2)
+ reiserfs_warning(tb->tb_sb, "vs-8111: get_num_ver: "
+ "split_item_position is out of boundary");
+ snum012[needed_nodes - 1]++;
+ split_item_positions[needed_nodes - 1] = i;
+ needed_nodes++;
+ /* continue from the same item with start_bytes != -1 */
+ start_item = i;
+ i--;
+ total_node_size = 0;
}
- if (!flow) {
- /* as we do not split items, take new node and continue */
- needed_nodes ++; i --; total_node_size = 0;
- continue;
+ // sum012[4] (if it is not -1) contains number of units of which
+ // are to be in S1new, snum012[3] - to be in S0. They are supposed
+ // to be S1bytes and S2bytes correspondingly, so recalculate
+ if (snum012[4] > 0) {
+ int split_item_num;
+ int bytes_to_r, bytes_to_l;
+ int bytes_to_S1new;
+
+ split_item_num = split_item_positions[1];
+ bytes_to_l =
+ ((from == split_item_num
+ && from_bytes != -1) ? from_bytes : 0);
+ bytes_to_r =
+ ((end_item == split_item_num
+ && end_bytes != -1) ? end_bytes : 0);
+ bytes_to_S1new =
+ ((split_item_positions[0] ==
+ split_item_positions[1]) ? snum012[3] : 0);
+
+ // s2bytes
+ snum012[4] =
+ op_unit_num(&vn->vn_vi[split_item_num]) - snum012[4] -
+ bytes_to_r - bytes_to_l - bytes_to_S1new;
+
+ if (vn->vn_vi[split_item_num].vi_index != TYPE_DIRENTRY &&
+ vn->vn_vi[split_item_num].vi_index != TYPE_INDIRECT)
+ reiserfs_warning(tb->tb_sb, "vs-8115: get_num_ver: not "
+ "directory or indirect item");
}
- // calculate number of item units which fit into node being
- // filled
- {
- int free_space;
-
- free_space = max_node_size - total_node_size - IH_SIZE;
- units = op_check_left (vi, free_space, start_bytes, skip_from_end);
- if (units == -1) {
- /* nothing fits into current node, take new node and continue */
- needed_nodes ++, i--, total_node_size = 0;
- continue;
- }
+ /* now we know S2bytes, calculate S1bytes */
+ if (snum012[3] > 0) {
+ int split_item_num;
+ int bytes_to_r, bytes_to_l;
+ int bytes_to_S2new;
+
+ split_item_num = split_item_positions[0];
+ bytes_to_l =
+ ((from == split_item_num
+ && from_bytes != -1) ? from_bytes : 0);
+ bytes_to_r =
+ ((end_item == split_item_num
+ && end_bytes != -1) ? end_bytes : 0);
+ bytes_to_S2new =
+ ((split_item_positions[0] == split_item_positions[1]
+ && snum012[4] != -1) ? snum012[4] : 0);
+
+ // s1bytes
+ snum012[3] =
+ op_unit_num(&vn->vn_vi[split_item_num]) - snum012[3] -
+ bytes_to_r - bytes_to_l - bytes_to_S2new;
}
- /* something fits into the current node */
- //if (snum012[3] != -1 || needed_nodes != 1)
- // reiserfs_panic (tb->tb_sb, "vs-8115: get_num_ver: too many nodes required");
- //snum012[needed_nodes - 1 + 3] = op_unit_num (vi) - start_bytes - units;
- start_bytes += units;
- snum012[needed_nodes - 1 + 3] = units;
-
- if (needed_nodes > 2)
- reiserfs_warning (tb->tb_sb, "vs-8111: get_num_ver: "
- "split_item_position is out of boundary");
- snum012[needed_nodes - 1] ++;
- split_item_positions[needed_nodes - 1] = i;
- needed_nodes ++;
- /* continue from the same item with start_bytes != -1 */
- start_item = i;
- i --;
- total_node_size = 0;
- }
-
- // sum012[4] (if it is not -1) contains number of units of which
- // are to be in S1new, snum012[3] - to be in S0. They are supposed
- // to be S1bytes and S2bytes correspondingly, so recalculate
- if (snum012[4] > 0) {
- int split_item_num;
- int bytes_to_r, bytes_to_l;
- int bytes_to_S1new;
-
- split_item_num = split_item_positions[1];
- bytes_to_l = ((from == split_item_num && from_bytes != -1) ? from_bytes : 0);
- bytes_to_r = ((end_item == split_item_num && end_bytes != -1) ? end_bytes : 0);
- bytes_to_S1new = ((split_item_positions[0] == split_item_positions[1]) ? snum012[3] : 0);
-
- // s2bytes
- snum012[4] = op_unit_num (&vn->vn_vi[split_item_num]) - snum012[4] - bytes_to_r - bytes_to_l - bytes_to_S1new;
-
- if (vn->vn_vi[split_item_num].vi_index != TYPE_DIRENTRY &&
- vn->vn_vi[split_item_num].vi_index != TYPE_INDIRECT)
- reiserfs_warning (tb->tb_sb, "vs-8115: get_num_ver: not "
- "directory or indirect item");
- }
-
- /* now we know S2bytes, calculate S1bytes */
- if (snum012[3] > 0) {
- int split_item_num;
- int bytes_to_r, bytes_to_l;
- int bytes_to_S2new;
-
- split_item_num = split_item_positions[0];
- bytes_to_l = ((from == split_item_num && from_bytes != -1) ? from_bytes : 0);
- bytes_to_r = ((end_item == split_item_num && end_bytes != -1) ? end_bytes : 0);
- bytes_to_S2new = ((split_item_positions[0] == split_item_positions[1] && snum012[4] != -1) ? snum012[4] : 0);
-
- // s1bytes
- snum012[3] = op_unit_num (&vn->vn_vi[split_item_num]) - snum012[3] - bytes_to_r - bytes_to_l - bytes_to_S2new;
- }
-
- return needed_nodes;
+ return needed_nodes;
}
-
#ifdef CONFIG_REISERFS_CHECK
-extern struct tree_balance * cur_tb;
+extern struct tree_balance *cur_tb;
#endif
-
/* Set parameters for balancing.
* Performs write of results of analysis of balancing into structure tb,
* where it will later be used by the functions that actually do the balancing.
@@ -557,131 +587,130 @@ extern struct tree_balance * cur_tb;
* s1bytes number of bytes which flow to the first new node when S[0] splits (this number is contained in s012 array)
*/
-static void set_parameters (struct tree_balance * tb, int h, int lnum,
- int rnum, int blk_num, short * s012, int lb, int rb)
+static void set_parameters(struct tree_balance *tb, int h, int lnum,
+ int rnum, int blk_num, short *s012, int lb, int rb)
{
- tb->lnum[h] = lnum;
- tb->rnum[h] = rnum;
- tb->blknum[h] = blk_num;
+ tb->lnum[h] = lnum;
+ tb->rnum[h] = rnum;
+ tb->blknum[h] = blk_num;
- if (h == 0)
- { /* only for leaf level */
- if (s012 != NULL)
- {
- tb->s0num = * s012 ++,
- tb->s1num = * s012 ++,
- tb->s2num = * s012 ++;
- tb->s1bytes = * s012 ++;
- tb->s2bytes = * s012;
+ if (h == 0) { /* only for leaf level */
+ if (s012 != NULL) {
+ tb->s0num = *s012++,
+ tb->s1num = *s012++, tb->s2num = *s012++;
+ tb->s1bytes = *s012++;
+ tb->s2bytes = *s012;
+ }
+ tb->lbytes = lb;
+ tb->rbytes = rb;
}
- tb->lbytes = lb;
- tb->rbytes = rb;
- }
- PROC_INFO_ADD( tb -> tb_sb, lnum[ h ], lnum );
- PROC_INFO_ADD( tb -> tb_sb, rnum[ h ], rnum );
-
- PROC_INFO_ADD( tb -> tb_sb, lbytes[ h ], lb );
- PROC_INFO_ADD( tb -> tb_sb, rbytes[ h ], rb );
-}
-
+ PROC_INFO_ADD(tb->tb_sb, lnum[h], lnum);
+ PROC_INFO_ADD(tb->tb_sb, rnum[h], rnum);
+ PROC_INFO_ADD(tb->tb_sb, lbytes[h], lb);
+ PROC_INFO_ADD(tb->tb_sb, rbytes[h], rb);
+}
/* check, does node disappear if we shift tb->lnum[0] items to left
neighbor and tb->rnum[0] to the right one. */
-static int is_leaf_removable (struct tree_balance * tb)
+static int is_leaf_removable(struct tree_balance *tb)
{
- struct virtual_node * vn = tb->tb_vn;
- int to_left, to_right;
- int size;
- int remain_items;
-
- /* number of items, that will be shifted to left (right) neighbor
- entirely */
- to_left = tb->lnum[0] - ((tb->lbytes != -1) ? 1 : 0);
- to_right = tb->rnum[0] - ((tb->rbytes != -1) ? 1 : 0);
- remain_items = vn->vn_nr_item;
-
- /* how many items remain in S[0] after shiftings to neighbors */
- remain_items -= (to_left + to_right);
-
- if (remain_items < 1) {
- /* all content of node can be shifted to neighbors */
- set_parameters (tb, 0, to_left, vn->vn_nr_item - to_left, 0, NULL, -1, -1);
- return 1;
- }
-
- if (remain_items > 1 || tb->lbytes == -1 || tb->rbytes == -1)
- /* S[0] is not removable */
- return 0;
-
- /* check, whether we can divide 1 remaining item between neighbors */
-
- /* get size of remaining item (in item units) */
- size = op_unit_num (&(vn->vn_vi[to_left]));
-
- if (tb->lbytes + tb->rbytes >= size) {
- set_parameters (tb, 0, to_left + 1, to_right + 1, 0, NULL, tb->lbytes, -1);
- return 1;
- }
-
- return 0;
-}
+ struct virtual_node *vn = tb->tb_vn;
+ int to_left, to_right;
+ int size;
+ int remain_items;
+
+ /* number of items, that will be shifted to left (right) neighbor
+ entirely */
+ to_left = tb->lnum[0] - ((tb->lbytes != -1) ? 1 : 0);
+ to_right = tb->rnum[0] - ((tb->rbytes != -1) ? 1 : 0);
+ remain_items = vn->vn_nr_item;
+
+ /* how many items remain in S[0] after shiftings to neighbors */
+ remain_items -= (to_left + to_right);
+
+ if (remain_items < 1) {
+ /* all content of node can be shifted to neighbors */
+ set_parameters(tb, 0, to_left, vn->vn_nr_item - to_left, 0,
+ NULL, -1, -1);
+ return 1;
+ }
+ if (remain_items > 1 || tb->lbytes == -1 || tb->rbytes == -1)
+ /* S[0] is not removable */
+ return 0;
+
+ /* check, whether we can divide 1 remaining item between neighbors */
+
+ /* get size of remaining item (in item units) */
+ size = op_unit_num(&(vn->vn_vi[to_left]));
+
+ if (tb->lbytes + tb->rbytes >= size) {
+ set_parameters(tb, 0, to_left + 1, to_right + 1, 0, NULL,
+ tb->lbytes, -1);
+ return 1;
+ }
+
+ return 0;
+}
/* check whether L, S, R can be joined in one node */
-static int are_leaves_removable (struct tree_balance * tb, int lfree, int rfree)
+static int are_leaves_removable(struct tree_balance *tb, int lfree, int rfree)
{
- struct virtual_node * vn = tb->tb_vn;
- int ih_size;
- struct buffer_head *S0;
-
- S0 = PATH_H_PBUFFER (tb->tb_path, 0);
-
- ih_size = 0;
- if (vn->vn_nr_item) {
- if (vn->vn_vi[0].vi_type & VI_TYPE_LEFT_MERGEABLE)
- ih_size += IH_SIZE;
-
- if (vn->vn_vi[vn->vn_nr_item-1].vi_type & VI_TYPE_RIGHT_MERGEABLE)
- ih_size += IH_SIZE;
- } else {
- /* there was only one item and it will be deleted */
- struct item_head * ih;
-
- RFALSE( B_NR_ITEMS (S0) != 1,
- "vs-8125: item number must be 1: it is %d", B_NR_ITEMS(S0));
-
- ih = B_N_PITEM_HEAD (S0, 0);
- if (tb->CFR[0] && !comp_short_le_keys (&(ih->ih_key), B_N_PDELIM_KEY (tb->CFR[0], tb->rkey[0])))
- if (is_direntry_le_ih (ih)) {
- /* Directory must be in correct state here: that is
- somewhere at the left side should exist first directory
- item. But the item being deleted can not be that first
- one because its right neighbor is item of the same
- directory. (But first item always gets deleted in last
- turn). So, neighbors of deleted item can be merged, so
- we can save ih_size */
- ih_size = IH_SIZE;
-
- /* we might check that left neighbor exists and is of the
- same directory */
- RFALSE(le_ih_k_offset (ih) == DOT_OFFSET,
- "vs-8130: first directory item can not be removed until directory is not empty");
- }
-
- }
-
- if (MAX_CHILD_SIZE (S0) + vn->vn_size <= rfree + lfree + ih_size) {
- set_parameters (tb, 0, -1, -1, -1, NULL, -1, -1);
- PROC_INFO_INC( tb -> tb_sb, leaves_removable );
- return 1;
- }
- return 0;
-
-}
+ struct virtual_node *vn = tb->tb_vn;
+ int ih_size;
+ struct buffer_head *S0;
+
+ S0 = PATH_H_PBUFFER(tb->tb_path, 0);
+
+ ih_size = 0;
+ if (vn->vn_nr_item) {
+ if (vn->vn_vi[0].vi_type & VI_TYPE_LEFT_MERGEABLE)
+ ih_size += IH_SIZE;
+
+ if (vn->vn_vi[vn->vn_nr_item - 1].
+ vi_type & VI_TYPE_RIGHT_MERGEABLE)
+ ih_size += IH_SIZE;
+ } else {
+ /* there was only one item and it will be deleted */
+ struct item_head *ih;
+
+ RFALSE(B_NR_ITEMS(S0) != 1,
+ "vs-8125: item number must be 1: it is %d",
+ B_NR_ITEMS(S0));
+
+ ih = B_N_PITEM_HEAD(S0, 0);
+ if (tb->CFR[0]
+ && !comp_short_le_keys(&(ih->ih_key),
+ B_N_PDELIM_KEY(tb->CFR[0],
+ tb->rkey[0])))
+ if (is_direntry_le_ih(ih)) {
+ /* Directory must be in correct state here: that is
+ somewhere at the left side should exist first directory
+ item. But the item being deleted can not be that first
+ one because its right neighbor is item of the same
+ directory. (But first item always gets deleted in last
+ turn). So, neighbors of deleted item can be merged, so
+ we can save ih_size */
+ ih_size = IH_SIZE;
+
+ /* we might check that left neighbor exists and is of the
+ same directory */
+ RFALSE(le_ih_k_offset(ih) == DOT_OFFSET,
+ "vs-8130: first directory item can not be removed until directory is not empty");
+ }
+ }
+
+ if (MAX_CHILD_SIZE(S0) + vn->vn_size <= rfree + lfree + ih_size) {
+ set_parameters(tb, 0, -1, -1, -1, NULL, -1, -1);
+ PROC_INFO_INC(tb->tb_sb, leaves_removable);
+ return 1;
+ }
+ return 0;
+}
/* when we do not split item, lnum and rnum are numbers of entire items */
#define SET_PAR_SHIFT_LEFT \
@@ -704,7 +733,6 @@ else \
-1, -1);\
}
-
#define SET_PAR_SHIFT_RIGHT \
if (h)\
{\
@@ -724,214 +752,199 @@ else \
-1, -1);\
}
-
-static void free_buffers_in_tb (
- struct tree_balance * p_s_tb
- ) {
- int n_counter;
-
- decrement_counters_in_path(p_s_tb->tb_path);
-
- for ( n_counter = 0; n_counter < MAX_HEIGHT; n_counter++ ) {
- decrement_bcount(p_s_tb->L[n_counter]);
- p_s_tb->L[n_counter] = NULL;
- decrement_bcount(p_s_tb->R[n_counter]);
- p_s_tb->R[n_counter] = NULL;
- decrement_bcount(p_s_tb->FL[n_counter]);
- p_s_tb->FL[n_counter] = NULL;
- decrement_bcount(p_s_tb->FR[n_counter]);
- p_s_tb->FR[n_counter] = NULL;
- decrement_bcount(p_s_tb->CFL[n_counter]);
- p_s_tb->CFL[n_counter] = NULL;
- decrement_bcount(p_s_tb->CFR[n_counter]);
- p_s_tb->CFR[n_counter] = NULL;
- }
+static void free_buffers_in_tb(struct tree_balance *p_s_tb)
+{
+ int n_counter;
+
+ decrement_counters_in_path(p_s_tb->tb_path);
+
+ for (n_counter = 0; n_counter < MAX_HEIGHT; n_counter++) {
+ decrement_bcount(p_s_tb->L[n_counter]);
+ p_s_tb->L[n_counter] = NULL;
+ decrement_bcount(p_s_tb->R[n_counter]);
+ p_s_tb->R[n_counter] = NULL;
+ decrement_bcount(p_s_tb->FL[n_counter]);
+ p_s_tb->FL[n_counter] = NULL;
+ decrement_bcount(p_s_tb->FR[n_counter]);
+ p_s_tb->FR[n_counter] = NULL;
+ decrement_bcount(p_s_tb->CFL[n_counter]);
+ p_s_tb->CFL[n_counter] = NULL;
+ decrement_bcount(p_s_tb->CFR[n_counter]);
+ p_s_tb->CFR[n_counter] = NULL;
+ }
}
-
/* Get new buffers for storing new nodes that are created while balancing.
* Returns: SCHEDULE_OCCURRED - schedule occurred while the function worked;
* CARRY_ON - schedule didn't occur while the function worked;
* NO_DISK_SPACE - no disk space.
*/
/* The function is NOT SCHEDULE-SAFE! */
-static int get_empty_nodes(
- struct tree_balance * p_s_tb,
- int n_h
- ) {
- struct buffer_head * p_s_new_bh,
- * p_s_Sh = PATH_H_PBUFFER (p_s_tb->tb_path, n_h);
- b_blocknr_t * p_n_blocknr,
- a_n_blocknrs[MAX_AMOUNT_NEEDED] = {0, };
- int n_counter,
- n_number_of_freeblk,
- n_amount_needed,/* number of needed empty blocks */
- n_retval = CARRY_ON;
- struct super_block * p_s_sb = p_s_tb->tb_sb;
-
-
- /* number_of_freeblk is the number of empty blocks which have been
- acquired for use by the balancing algorithm minus the number of
- empty blocks used in the previous levels of the analysis,
- number_of_freeblk = tb->cur_blknum can be non-zero if a schedule occurs
- after empty blocks are acquired, and the balancing analysis is
- then restarted, amount_needed is the number needed by this level
- (n_h) of the balancing analysis.
-
- Note that for systems with many processes writing, it would be
- more layout optimal to calculate the total number needed by all
- levels and then to run reiserfs_new_blocks to get all of them at once. */
-
- /* Initiate number_of_freeblk to the amount acquired prior to the restart of
- the analysis or 0 if not restarted, then subtract the amount needed
- by all of the levels of the tree below n_h. */
- /* blknum includes S[n_h], so we subtract 1 in this calculation */
- for ( n_counter = 0, n_number_of_freeblk = p_s_tb->cur_blknum; n_counter < n_h; n_counter++ )
- n_number_of_freeblk -= ( p_s_tb->blknum[n_counter] ) ? (p_s_tb->blknum[n_counter] - 1) : 0;
-
- /* Allocate missing empty blocks. */
- /* if p_s_Sh == 0 then we are getting a new root */
- n_amount_needed = ( p_s_Sh ) ? (p_s_tb->blknum[n_h] - 1) : 1;
- /* Amount_needed = the amount that we need more than the amount that we have. */
- if ( n_amount_needed > n_number_of_freeblk )
- n_amount_needed -= n_number_of_freeblk;
- else /* If we have enough already then there is nothing to do. */
- return CARRY_ON;
-
- /* No need to check quota - is not allocated for blocks used for formatted nodes */
- if (reiserfs_new_form_blocknrs (p_s_tb, a_n_blocknrs,
- n_amount_needed) == NO_DISK_SPACE)
- return NO_DISK_SPACE;
-
- /* for each blocknumber we just got, get a buffer and stick it on FEB */
- for ( p_n_blocknr = a_n_blocknrs, n_counter = 0; n_counter < n_amount_needed;
- p_n_blocknr++, n_counter++ ) {
-
- RFALSE( ! *p_n_blocknr,
- "PAP-8135: reiserfs_new_blocknrs failed when got new blocks");
-
- p_s_new_bh = sb_getblk(p_s_sb, *p_n_blocknr);
- RFALSE (buffer_dirty (p_s_new_bh) ||
- buffer_journaled (p_s_new_bh) ||
- buffer_journal_dirty (p_s_new_bh),
- "PAP-8140: journlaled or dirty buffer %b for the new block",
- p_s_new_bh);
-
- /* Put empty buffers into the array. */
- RFALSE (p_s_tb->FEB[p_s_tb->cur_blknum],
- "PAP-8141: busy slot for new buffer");
-
- set_buffer_journal_new (p_s_new_bh);
- p_s_tb->FEB[p_s_tb->cur_blknum++] = p_s_new_bh;
- }
-
- if ( n_retval == CARRY_ON && FILESYSTEM_CHANGED_TB (p_s_tb) )
- n_retval = REPEAT_SEARCH ;
-
- return n_retval;
-}
+static int get_empty_nodes(struct tree_balance *p_s_tb, int n_h)
+{
+ struct buffer_head *p_s_new_bh,
+ *p_s_Sh = PATH_H_PBUFFER(p_s_tb->tb_path, n_h);
+ b_blocknr_t *p_n_blocknr, a_n_blocknrs[MAX_AMOUNT_NEEDED] = { 0, };
+ int n_counter, n_number_of_freeblk, n_amount_needed, /* number of needed empty blocks */
+ n_retval = CARRY_ON;
+ struct super_block *p_s_sb = p_s_tb->tb_sb;
+
+ /* number_of_freeblk is the number of empty blocks which have been
+ acquired for use by the balancing algorithm minus the number of
+ empty blocks used in the previous levels of the analysis,
+ number_of_freeblk = tb->cur_blknum can be non-zero if a schedule occurs
+ after empty blocks are acquired, and the balancing analysis is
+ then restarted, amount_needed is the number needed by this level
+ (n_h) of the balancing analysis.
+
+ Note that for systems with many processes writing, it would be
+ more layout optimal to calculate the total number needed by all
+ levels and then to run reiserfs_new_blocks to get all of them at once. */
+
+ /* Initiate number_of_freeblk to the amount acquired prior to the restart of
+ the analysis or 0 if not restarted, then subtract the amount needed
+ by all of the levels of the tree below n_h. */
+ /* blknum includes S[n_h], so we subtract 1 in this calculation */
+ for (n_counter = 0, n_number_of_freeblk = p_s_tb->cur_blknum;
+ n_counter < n_h; n_counter++)
+ n_number_of_freeblk -=
+ (p_s_tb->blknum[n_counter]) ? (p_s_tb->blknum[n_counter] -
+ 1) : 0;
+
+ /* Allocate missing empty blocks. */
+ /* if p_s_Sh == 0 then we are getting a new root */
+ n_amount_needed = (p_s_Sh) ? (p_s_tb->blknum[n_h] - 1) : 1;
+ /* Amount_needed = the amount that we need more than the amount that we have. */
+ if (n_amount_needed > n_number_of_freeblk)
+ n_amount_needed -= n_number_of_freeblk;
+ else /* If we have enough already then there is nothing to do. */
+ return CARRY_ON;
+
+ /* No need to check quota - is not allocated for blocks used for formatted nodes */
+ if (reiserfs_new_form_blocknrs(p_s_tb, a_n_blocknrs,
+ n_amount_needed) == NO_DISK_SPACE)
+ return NO_DISK_SPACE;
+
+ /* for each blocknumber we just got, get a buffer and stick it on FEB */
+ for (p_n_blocknr = a_n_blocknrs, n_counter = 0;
+ n_counter < n_amount_needed; p_n_blocknr++, n_counter++) {
+
+ RFALSE(!*p_n_blocknr,
+ "PAP-8135: reiserfs_new_blocknrs failed when got new blocks");
+
+ p_s_new_bh = sb_getblk(p_s_sb, *p_n_blocknr);
+ RFALSE(buffer_dirty(p_s_new_bh) ||
+ buffer_journaled(p_s_new_bh) ||
+ buffer_journal_dirty(p_s_new_bh),
+ "PAP-8140: journlaled or dirty buffer %b for the new block",
+ p_s_new_bh);
+
+ /* Put empty buffers into the array. */
+ RFALSE(p_s_tb->FEB[p_s_tb->cur_blknum],
+ "PAP-8141: busy slot for new buffer");
+
+ set_buffer_journal_new(p_s_new_bh);
+ p_s_tb->FEB[p_s_tb->cur_blknum++] = p_s_new_bh;
+ }
+
+ if (n_retval == CARRY_ON && FILESYSTEM_CHANGED_TB(p_s_tb))
+ n_retval = REPEAT_SEARCH;
+ return n_retval;
+}
/* Get free space of the left neighbor, which is stored in the parent
* node of the left neighbor. */
-static int get_lfree (struct tree_balance * tb, int h)
+static int get_lfree(struct tree_balance *tb, int h)
{
- struct buffer_head * l, * f;
- int order;
+ struct buffer_head *l, *f;
+ int order;
- if ((f = PATH_H_PPARENT (tb->tb_path, h)) == 0 || (l = tb->FL[h]) == 0)
- return 0;
+ if ((f = PATH_H_PPARENT(tb->tb_path, h)) == 0 || (l = tb->FL[h]) == 0)
+ return 0;
- if (f == l)
- order = PATH_H_B_ITEM_ORDER (tb->tb_path, h) - 1;
- else {
- order = B_NR_ITEMS (l);
- f = l;
- }
+ if (f == l)
+ order = PATH_H_B_ITEM_ORDER(tb->tb_path, h) - 1;
+ else {
+ order = B_NR_ITEMS(l);
+ f = l;
+ }
- return (MAX_CHILD_SIZE(f) - dc_size(B_N_CHILD(f,order)));
+ return (MAX_CHILD_SIZE(f) - dc_size(B_N_CHILD(f, order)));
}
-
/* Get free space of the right neighbor,
* which is stored in the parent node of the right neighbor.
*/
-static int get_rfree (struct tree_balance * tb, int h)
+static int get_rfree(struct tree_balance *tb, int h)
{
- struct buffer_head * r, * f;
- int order;
+ struct buffer_head *r, *f;
+ int order;
- if ((f = PATH_H_PPARENT (tb->tb_path, h)) == 0 || (r = tb->FR[h]) == 0)
- return 0;
+ if ((f = PATH_H_PPARENT(tb->tb_path, h)) == 0 || (r = tb->FR[h]) == 0)
+ return 0;
- if (f == r)
- order = PATH_H_B_ITEM_ORDER (tb->tb_path, h) + 1;
- else {
- order = 0;
- f = r;
- }
+ if (f == r)
+ order = PATH_H_B_ITEM_ORDER(tb->tb_path, h) + 1;
+ else {
+ order = 0;
+ f = r;
+ }
- return (MAX_CHILD_SIZE(f) - dc_size( B_N_CHILD(f,order)));
+ return (MAX_CHILD_SIZE(f) - dc_size(B_N_CHILD(f, order)));
}
-
/* Check whether left neighbor is in memory. */
-static int is_left_neighbor_in_cache(
- struct tree_balance * p_s_tb,
- int n_h
- ) {
- struct buffer_head * p_s_father, * left;
- struct super_block * p_s_sb = p_s_tb->tb_sb;
- b_blocknr_t n_left_neighbor_blocknr;
- int n_left_neighbor_position;
-
- if ( ! p_s_tb->FL[n_h] ) /* Father of the left neighbor does not exist. */
- return 0;
-
- /* Calculate father of the node to be balanced. */
- p_s_father = PATH_H_PBUFFER(p_s_tb->tb_path, n_h + 1);
-
- RFALSE( ! p_s_father ||
- ! B_IS_IN_TREE (p_s_father) ||
- ! B_IS_IN_TREE (p_s_tb->FL[n_h]) ||
- ! buffer_uptodate (p_s_father) ||
- ! buffer_uptodate (p_s_tb->FL[n_h]),
- "vs-8165: F[h] (%b) or FL[h] (%b) is invalid",
- p_s_father, p_s_tb->FL[n_h]);
-
-
- /* Get position of the pointer to the left neighbor into the left father. */
- n_left_neighbor_position = ( p_s_father == p_s_tb->FL[n_h] ) ?
- p_s_tb->lkey[n_h] : B_NR_ITEMS (p_s_tb->FL[n_h]);
- /* Get left neighbor block number. */
- n_left_neighbor_blocknr = B_N_CHILD_NUM(p_s_tb->FL[n_h], n_left_neighbor_position);
- /* Look for the left neighbor in the cache. */
- if ( (left = sb_find_get_block(p_s_sb, n_left_neighbor_blocknr)) ) {
-
- RFALSE( buffer_uptodate (left) && ! B_IS_IN_TREE(left),
- "vs-8170: left neighbor (%b %z) is not in the tree", left, left);
- put_bh(left) ;
- return 1;
- }
-
- return 0;
-}
+static int is_left_neighbor_in_cache(struct tree_balance *p_s_tb, int n_h)
+{
+ struct buffer_head *p_s_father, *left;
+ struct super_block *p_s_sb = p_s_tb->tb_sb;
+ b_blocknr_t n_left_neighbor_blocknr;
+ int n_left_neighbor_position;
+
+ if (!p_s_tb->FL[n_h]) /* Father of the left neighbor does not exist. */
+ return 0;
+
+ /* Calculate father of the node to be balanced. */
+ p_s_father = PATH_H_PBUFFER(p_s_tb->tb_path, n_h + 1);
+
+ RFALSE(!p_s_father ||
+ !B_IS_IN_TREE(p_s_father) ||
+ !B_IS_IN_TREE(p_s_tb->FL[n_h]) ||
+ !buffer_uptodate(p_s_father) ||
+ !buffer_uptodate(p_s_tb->FL[n_h]),
+ "vs-8165: F[h] (%b) or FL[h] (%b) is invalid",
+ p_s_father, p_s_tb->FL[n_h]);
+
+ /* Get position of the pointer to the left neighbor into the left father. */
+ n_left_neighbor_position = (p_s_father == p_s_tb->FL[n_h]) ?
+ p_s_tb->lkey[n_h] : B_NR_ITEMS(p_s_tb->FL[n_h]);
+ /* Get left neighbor block number. */
+ n_left_neighbor_blocknr =
+ B_N_CHILD_NUM(p_s_tb->FL[n_h], n_left_neighbor_position);
+ /* Look for the left neighbor in the cache. */
+ if ((left = sb_find_get_block(p_s_sb, n_left_neighbor_blocknr))) {
+
+ RFALSE(buffer_uptodate(left) && !B_IS_IN_TREE(left),
+ "vs-8170: left neighbor (%b %z) is not in the tree",
+ left, left);
+ put_bh(left);
+ return 1;
+ }
+ return 0;
+}
#define LEFT_PARENTS 'l'
#define RIGHT_PARENTS 'r'
-
-static void decrement_key (struct cpu_key * p_s_key)
+static void decrement_key(struct cpu_key *p_s_key)
{
- // call item specific function for this key
- item_ops[cpu_key_k_type (p_s_key)]->decrement_key (p_s_key);
+ // call item specific function for this key
+ item_ops[cpu_key_k_type(p_s_key)]->decrement_key(p_s_key);
}
-
-
-
/* Calculate far left/right parent of the left/right neighbor of the current node, that
* is calculate the left/right (FL[h]/FR[h]) neighbor of the parent F[h].
* Calculate left/right common parent of the current node and L[h]/R[h].
@@ -940,111 +953,121 @@ static void decrement_key (struct cpu_key * p_s_key)
SCHEDULE_OCCURRED - schedule occurred while the function worked;
* CARRY_ON - schedule didn't occur while the function worked;
*/
-static int get_far_parent (struct tree_balance * p_s_tb,
- int n_h,
- struct buffer_head ** pp_s_father,
- struct buffer_head ** pp_s_com_father,
- char c_lr_par)
+static int get_far_parent(struct tree_balance *p_s_tb,
+ int n_h,
+ struct buffer_head **pp_s_father,
+ struct buffer_head **pp_s_com_father, char c_lr_par)
{
- struct buffer_head * p_s_parent;
- INITIALIZE_PATH (s_path_to_neighbor_father);
- struct path * p_s_path = p_s_tb->tb_path;
- struct cpu_key s_lr_father_key;
- int n_counter,
- n_position = INT_MAX,
- n_first_last_position = 0,
- n_path_offset = PATH_H_PATH_OFFSET(p_s_path, n_h);
-
- /* Starting from F[n_h] go upwards in the tree, and look for the common
- ancestor of F[n_h], and its neighbor l/r, that should be obtained. */
-
- n_counter = n_path_offset;
-
- RFALSE( n_counter < FIRST_PATH_ELEMENT_OFFSET,
- "PAP-8180: invalid path length");
-
-
- for ( ; n_counter > FIRST_PATH_ELEMENT_OFFSET; n_counter-- ) {
- /* Check whether parent of the current buffer in the path is really parent in the tree. */
- if ( ! B_IS_IN_TREE(p_s_parent = PATH_OFFSET_PBUFFER(p_s_path, n_counter - 1)) )
- return REPEAT_SEARCH;
- /* Check whether position in the parent is correct. */
- if ( (n_position = PATH_OFFSET_POSITION(p_s_path, n_counter - 1)) > B_NR_ITEMS(p_s_parent) )
- return REPEAT_SEARCH;
- /* Check whether parent at the path really points to the child. */
- if ( B_N_CHILD_NUM(p_s_parent, n_position) !=
- PATH_OFFSET_PBUFFER(p_s_path, n_counter)->b_blocknr )
- return REPEAT_SEARCH;
- /* Return delimiting key if position in the parent is not equal to first/last one. */
- if ( c_lr_par == RIGHT_PARENTS )
- n_first_last_position = B_NR_ITEMS (p_s_parent);
- if ( n_position != n_first_last_position ) {
- *pp_s_com_father = p_s_parent;
- get_bh(*pp_s_com_father) ;
- /*(*pp_s_com_father = p_s_parent)->b_count++;*/
- break;
+ struct buffer_head *p_s_parent;
+ INITIALIZE_PATH(s_path_to_neighbor_father);
+ struct path *p_s_path = p_s_tb->tb_path;
+ struct cpu_key s_lr_father_key;
+ int n_counter,
+ n_position = INT_MAX,
+ n_first_last_position = 0,
+ n_path_offset = PATH_H_PATH_OFFSET(p_s_path, n_h);
+
+ /* Starting from F[n_h] go upwards in the tree, and look for the common
+ ancestor of F[n_h], and its neighbor l/r, that should be obtained. */
+
+ n_counter = n_path_offset;
+
+ RFALSE(n_counter < FIRST_PATH_ELEMENT_OFFSET,
+ "PAP-8180: invalid path length");
+
+ for (; n_counter > FIRST_PATH_ELEMENT_OFFSET; n_counter--) {
+ /* Check whether parent of the current buffer in the path is really parent in the tree. */
+ if (!B_IS_IN_TREE
+ (p_s_parent = PATH_OFFSET_PBUFFER(p_s_path, n_counter - 1)))
+ return REPEAT_SEARCH;
+ /* Check whether position in the parent is correct. */
+ if ((n_position =
+ PATH_OFFSET_POSITION(p_s_path,
+ n_counter - 1)) >
+ B_NR_ITEMS(p_s_parent))
+ return REPEAT_SEARCH;
+ /* Check whether parent at the path really points to the child. */
+ if (B_N_CHILD_NUM(p_s_parent, n_position) !=
+ PATH_OFFSET_PBUFFER(p_s_path, n_counter)->b_blocknr)
+ return REPEAT_SEARCH;
+ /* Return delimiting key if position in the parent is not equal to first/last one. */
+ if (c_lr_par == RIGHT_PARENTS)
+ n_first_last_position = B_NR_ITEMS(p_s_parent);
+ if (n_position != n_first_last_position) {
+ *pp_s_com_father = p_s_parent;
+ get_bh(*pp_s_com_father);
+ /*(*pp_s_com_father = p_s_parent)->b_count++; */
+ break;
+ }
}
- }
-
- /* if we are in the root of the tree, then there is no common father */
- if ( n_counter == FIRST_PATH_ELEMENT_OFFSET ) {
- /* Check whether first buffer in the path is the root of the tree. */
- if ( PATH_OFFSET_PBUFFER(p_s_tb->tb_path, FIRST_PATH_ELEMENT_OFFSET)->b_blocknr ==
- SB_ROOT_BLOCK (p_s_tb->tb_sb) ) {
- *pp_s_father = *pp_s_com_father = NULL;
- return CARRY_ON;
+
+ /* if we are in the root of the tree, then there is no common father */
+ if (n_counter == FIRST_PATH_ELEMENT_OFFSET) {
+ /* Check whether first buffer in the path is the root of the tree. */
+ if (PATH_OFFSET_PBUFFER
+ (p_s_tb->tb_path,
+ FIRST_PATH_ELEMENT_OFFSET)->b_blocknr ==
+ SB_ROOT_BLOCK(p_s_tb->tb_sb)) {
+ *pp_s_father = *pp_s_com_father = NULL;
+ return CARRY_ON;
+ }
+ return REPEAT_SEARCH;
}
- return REPEAT_SEARCH;
- }
- RFALSE( B_LEVEL (*pp_s_com_father) <= DISK_LEAF_NODE_LEVEL,
- "PAP-8185: (%b %z) level too small",
- *pp_s_com_father, *pp_s_com_father);
+ RFALSE(B_LEVEL(*pp_s_com_father) <= DISK_LEAF_NODE_LEVEL,
+ "PAP-8185: (%b %z) level too small",
+ *pp_s_com_father, *pp_s_com_father);
- /* Check whether the common parent is locked. */
+ /* Check whether the common parent is locked. */
- if ( buffer_locked (*pp_s_com_father) ) {
- __wait_on_buffer(*pp_s_com_father);
- if ( FILESYSTEM_CHANGED_TB (p_s_tb) ) {
- decrement_bcount(*pp_s_com_father);
- return REPEAT_SEARCH;
+ if (buffer_locked(*pp_s_com_father)) {
+ __wait_on_buffer(*pp_s_com_father);
+ if (FILESYSTEM_CHANGED_TB(p_s_tb)) {
+ decrement_bcount(*pp_s_com_father);
+ return REPEAT_SEARCH;
+ }
}
- }
-
- /* So, we got common parent of the current node and its left/right neighbor.
- Now we are geting the parent of the left/right neighbor. */
- /* Form key to get parent of the left/right neighbor. */
- le_key2cpu_key (&s_lr_father_key, B_N_PDELIM_KEY(*pp_s_com_father, ( c_lr_par == LEFT_PARENTS ) ?
- (p_s_tb->lkey[n_h - 1] = n_position - 1) : (p_s_tb->rkey[n_h - 1] = n_position)));
+ /* So, we got common parent of the current node and its left/right neighbor.
+ Now we are geting the parent of the left/right neighbor. */
+ /* Form key to get parent of the left/right neighbor. */
+ le_key2cpu_key(&s_lr_father_key,
+ B_N_PDELIM_KEY(*pp_s_com_father,
+ (c_lr_par ==
+ LEFT_PARENTS) ? (p_s_tb->lkey[n_h - 1] =
+ n_position -
+ 1) : (p_s_tb->rkey[n_h -
+ 1] =
+ n_position)));
- if ( c_lr_par == LEFT_PARENTS )
- decrement_key(&s_lr_father_key);
+ if (c_lr_par == LEFT_PARENTS)
+ decrement_key(&s_lr_father_key);
- if (search_by_key(p_s_tb->tb_sb, &s_lr_father_key, &s_path_to_neighbor_father, n_h + 1) == IO_ERROR)
- // path is released
- return IO_ERROR;
+ if (search_by_key
+ (p_s_tb->tb_sb, &s_lr_father_key, &s_path_to_neighbor_father,
+ n_h + 1) == IO_ERROR)
+ // path is released
+ return IO_ERROR;
- if ( FILESYSTEM_CHANGED_TB (p_s_tb) ) {
- decrement_counters_in_path(&s_path_to_neighbor_father);
- decrement_bcount(*pp_s_com_father);
- return REPEAT_SEARCH;
- }
+ if (FILESYSTEM_CHANGED_TB(p_s_tb)) {
+ decrement_counters_in_path(&s_path_to_neighbor_father);
+ decrement_bcount(*pp_s_com_father);
+ return REPEAT_SEARCH;
+ }
- *pp_s_father = PATH_PLAST_BUFFER(&s_path_to_neighbor_father);
+ *pp_s_father = PATH_PLAST_BUFFER(&s_path_to_neighbor_father);
- RFALSE( B_LEVEL (*pp_s_father) != n_h + 1,
- "PAP-8190: (%b %z) level too small", *pp_s_father, *pp_s_father);
- RFALSE( s_path_to_neighbor_father.path_length < FIRST_PATH_ELEMENT_OFFSET,
- "PAP-8192: path length is too small");
+ RFALSE(B_LEVEL(*pp_s_father) != n_h + 1,
+ "PAP-8190: (%b %z) level too small", *pp_s_father, *pp_s_father);
+ RFALSE(s_path_to_neighbor_father.path_length <
+ FIRST_PATH_ELEMENT_OFFSET, "PAP-8192: path length is too small");
- s_path_to_neighbor_father.path_length--;
- decrement_counters_in_path(&s_path_to_neighbor_father);
- return CARRY_ON;
+ s_path_to_neighbor_father.path_length--;
+ decrement_counters_in_path(&s_path_to_neighbor_father);
+ return CARRY_ON;
}
-
/* Get parents of neighbors of node in the path(S[n_path_offset]) and common parents of
* S[n_path_offset] and L[n_path_offset]/R[n_path_offset]: F[n_path_offset], FL[n_path_offset],
* FR[n_path_offset], CFL[n_path_offset], CFR[n_path_offset].
@@ -1052,122 +1075,127 @@ static int get_far_parent (struct tree_balance * p_s_tb,
* Returns: SCHEDULE_OCCURRED - schedule occurred while the function worked;
* CARRY_ON - schedule didn't occur while the function worked;
*/
-static int get_parents (struct tree_balance * p_s_tb, int n_h)
+static int get_parents(struct tree_balance *p_s_tb, int n_h)
{
- struct path * p_s_path = p_s_tb->tb_path;
- int n_position,
- n_ret_value,
- n_path_offset = PATH_H_PATH_OFFSET(p_s_tb->tb_path, n_h);
- struct buffer_head * p_s_curf,
- * p_s_curcf;
-
- /* Current node is the root of the tree or will be root of the tree */
- if ( n_path_offset <= FIRST_PATH_ELEMENT_OFFSET ) {
- /* The root can not have parents.
- Release nodes which previously were obtained as parents of the current node neighbors. */
+ struct path *p_s_path = p_s_tb->tb_path;
+ int n_position,
+ n_ret_value,
+ n_path_offset = PATH_H_PATH_OFFSET(p_s_tb->tb_path, n_h);
+ struct buffer_head *p_s_curf, *p_s_curcf;
+
+ /* Current node is the root of the tree or will be root of the tree */
+ if (n_path_offset <= FIRST_PATH_ELEMENT_OFFSET) {
+ /* The root can not have parents.
+ Release nodes which previously were obtained as parents of the current node neighbors. */
+ decrement_bcount(p_s_tb->FL[n_h]);
+ decrement_bcount(p_s_tb->CFL[n_h]);
+ decrement_bcount(p_s_tb->FR[n_h]);
+ decrement_bcount(p_s_tb->CFR[n_h]);
+ p_s_tb->FL[n_h] = p_s_tb->CFL[n_h] = p_s_tb->FR[n_h] =
+ p_s_tb->CFR[n_h] = NULL;
+ return CARRY_ON;
+ }
+
+ /* Get parent FL[n_path_offset] of L[n_path_offset]. */
+ if ((n_position = PATH_OFFSET_POSITION(p_s_path, n_path_offset - 1))) {
+ /* Current node is not the first child of its parent. */
+ /*(p_s_curf = p_s_curcf = PATH_OFFSET_PBUFFER(p_s_path, n_path_offset - 1))->b_count += 2; */
+ p_s_curf = p_s_curcf =
+ PATH_OFFSET_PBUFFER(p_s_path, n_path_offset - 1);
+ get_bh(p_s_curf);
+ get_bh(p_s_curf);
+ p_s_tb->lkey[n_h] = n_position - 1;
+ } else {
+ /* Calculate current parent of L[n_path_offset], which is the left neighbor of the current node.
+ Calculate current common parent of L[n_path_offset] and the current node. Note that
+ CFL[n_path_offset] not equal FL[n_path_offset] and CFL[n_path_offset] not equal F[n_path_offset].
+ Calculate lkey[n_path_offset]. */
+ if ((n_ret_value = get_far_parent(p_s_tb, n_h + 1, &p_s_curf,
+ &p_s_curcf,
+ LEFT_PARENTS)) != CARRY_ON)
+ return n_ret_value;
+ }
+
decrement_bcount(p_s_tb->FL[n_h]);
+ p_s_tb->FL[n_h] = p_s_curf; /* New initialization of FL[n_h]. */
decrement_bcount(p_s_tb->CFL[n_h]);
- decrement_bcount(p_s_tb->FR[n_h]);
- decrement_bcount(p_s_tb->CFR[n_h]);
- p_s_tb->FL[n_h] = p_s_tb->CFL[n_h] = p_s_tb->FR[n_h] = p_s_tb->CFR[n_h] = NULL;
- return CARRY_ON;
- }
-
- /* Get parent FL[n_path_offset] of L[n_path_offset]. */
- if ( (n_position = PATH_OFFSET_POSITION(p_s_path, n_path_offset - 1)) ) {
- /* Current node is not the first child of its parent. */
- /*(p_s_curf = p_s_curcf = PATH_OFFSET_PBUFFER(p_s_path, n_path_offset - 1))->b_count += 2;*/
- p_s_curf = p_s_curcf = PATH_OFFSET_PBUFFER(p_s_path, n_path_offset - 1);
- get_bh(p_s_curf) ;
- get_bh(p_s_curf) ;
- p_s_tb->lkey[n_h] = n_position - 1;
- }
- else {
- /* Calculate current parent of L[n_path_offset], which is the left neighbor of the current node.
- Calculate current common parent of L[n_path_offset] and the current node. Note that
- CFL[n_path_offset] not equal FL[n_path_offset] and CFL[n_path_offset] not equal F[n_path_offset].
- Calculate lkey[n_path_offset]. */
- if ( (n_ret_value = get_far_parent(p_s_tb, n_h + 1, &p_s_curf,
- &p_s_curcf, LEFT_PARENTS)) != CARRY_ON )
- return n_ret_value;
- }
-
- decrement_bcount(p_s_tb->FL[n_h]);
- p_s_tb->FL[n_h] = p_s_curf; /* New initialization of FL[n_h]. */
- decrement_bcount(p_s_tb->CFL[n_h]);
- p_s_tb->CFL[n_h] = p_s_curcf; /* New initialization of CFL[n_h]. */
-
- RFALSE( (p_s_curf && !B_IS_IN_TREE (p_s_curf)) ||
- (p_s_curcf && !B_IS_IN_TREE (p_s_curcf)),
- "PAP-8195: FL (%b) or CFL (%b) is invalid", p_s_curf, p_s_curcf);
+ p_s_tb->CFL[n_h] = p_s_curcf; /* New initialization of CFL[n_h]. */
+
+ RFALSE((p_s_curf && !B_IS_IN_TREE(p_s_curf)) ||
+ (p_s_curcf && !B_IS_IN_TREE(p_s_curcf)),
+ "PAP-8195: FL (%b) or CFL (%b) is invalid", p_s_curf, p_s_curcf);
/* Get parent FR[n_h] of R[n_h]. */
/* Current node is the last child of F[n_h]. FR[n_h] != F[n_h]. */
- if ( n_position == B_NR_ITEMS (PATH_H_PBUFFER(p_s_path, n_h + 1)) ) {
+ if (n_position == B_NR_ITEMS(PATH_H_PBUFFER(p_s_path, n_h + 1))) {
/* Calculate current parent of R[n_h], which is the right neighbor of F[n_h].
Calculate current common parent of R[n_h] and current node. Note that CFR[n_h]
not equal FR[n_path_offset] and CFR[n_h] not equal F[n_h]. */
- if ( (n_ret_value = get_far_parent(p_s_tb, n_h + 1, &p_s_curf, &p_s_curcf, RIGHT_PARENTS)) != CARRY_ON )
- return n_ret_value;
- }
- else {
+ if ((n_ret_value =
+ get_far_parent(p_s_tb, n_h + 1, &p_s_curf, &p_s_curcf,
+ RIGHT_PARENTS)) != CARRY_ON)
+ return n_ret_value;
+ } else {
/* Current node is not the last child of its parent F[n_h]. */
- /*(p_s_curf = p_s_curcf = PATH_OFFSET_PBUFFER(p_s_path, n_path_offset - 1))->b_count += 2;*/
- p_s_curf = p_s_curcf = PATH_OFFSET_PBUFFER(p_s_path, n_path_offset - 1);
- get_bh(p_s_curf) ;
- get_bh(p_s_curf) ;
- p_s_tb->rkey[n_h] = n_position;
- }
-
- decrement_bcount(p_s_tb->FR[n_h]);
- p_s_tb->FR[n_h] = p_s_curf; /* New initialization of FR[n_path_offset]. */
-
- decrement_bcount(p_s_tb->CFR[n_h]);
- p_s_tb->CFR[n_h] = p_s_curcf; /* New initialization of CFR[n_path_offset]. */
-
- RFALSE( (p_s_curf && !B_IS_IN_TREE (p_s_curf)) ||
- (p_s_curcf && !B_IS_IN_TREE (p_s_curcf)),
- "PAP-8205: FR (%b) or CFR (%b) is invalid", p_s_curf, p_s_curcf);
-
- return CARRY_ON;
-}
+ /*(p_s_curf = p_s_curcf = PATH_OFFSET_PBUFFER(p_s_path, n_path_offset - 1))->b_count += 2; */
+ p_s_curf = p_s_curcf =
+ PATH_OFFSET_PBUFFER(p_s_path, n_path_offset - 1);
+ get_bh(p_s_curf);
+ get_bh(p_s_curf);
+ p_s_tb->rkey[n_h] = n_position;
+ }
+ decrement_bcount(p_s_tb->FR[n_h]);
+ p_s_tb->FR[n_h] = p_s_curf; /* New initialization of FR[n_path_offset]. */
+
+ decrement_bcount(p_s_tb->CFR[n_h]);
+ p_s_tb->CFR[n_h] = p_s_curcf; /* New initialization of CFR[n_path_offset]. */
+
+ RFALSE((p_s_curf && !B_IS_IN_TREE(p_s_curf)) ||
+ (p_s_curcf && !B_IS_IN_TREE(p_s_curcf)),
+ "PAP-8205: FR (%b) or CFR (%b) is invalid", p_s_curf, p_s_curcf);
+
+ return CARRY_ON;
+}
/* it is possible to remove node as result of shiftings to
neighbors even when we insert or paste item. */
-static inline int can_node_be_removed (int mode, int lfree, int sfree, int rfree, struct tree_balance * tb, int h)
+static inline int can_node_be_removed(int mode, int lfree, int sfree, int rfree,
+ struct tree_balance *tb, int h)
{
- struct buffer_head * Sh = PATH_H_PBUFFER (tb->tb_path, h);
- int levbytes = tb->insert_size[h];
- struct item_head * ih;
- struct reiserfs_key * r_key = NULL;
-
- ih = B_N_PITEM_HEAD (Sh, 0);
- if ( tb->CFR[h] )
- r_key = B_N_PDELIM_KEY(tb->CFR[h],tb->rkey[h]);
-
- if (
- lfree + rfree + sfree < MAX_CHILD_SIZE(Sh) + levbytes
- /* shifting may merge items which might save space */
- - (( ! h && op_is_left_mergeable (&(ih->ih_key), Sh->b_size) ) ? IH_SIZE : 0)
- - (( ! h && r_key && op_is_left_mergeable (r_key, Sh->b_size) ) ? IH_SIZE : 0)
- + (( h ) ? KEY_SIZE : 0))
- {
- /* node can not be removed */
- if (sfree >= levbytes ) { /* new item fits into node S[h] without any shifting */
- if ( ! h )
- tb->s0num = B_NR_ITEMS(Sh) + ((mode == M_INSERT ) ? 1 : 0);
- set_parameters (tb, h, 0, 0, 1, NULL, -1, -1);
- return NO_BALANCING_NEEDED;
+ struct buffer_head *Sh = PATH_H_PBUFFER(tb->tb_path, h);
+ int levbytes = tb->insert_size[h];
+ struct item_head *ih;
+ struct reiserfs_key *r_key = NULL;
+
+ ih = B_N_PITEM_HEAD(Sh, 0);
+ if (tb->CFR[h])
+ r_key = B_N_PDELIM_KEY(tb->CFR[h], tb->rkey[h]);
+
+ if (lfree + rfree + sfree < MAX_CHILD_SIZE(Sh) + levbytes
+ /* shifting may merge items which might save space */
+ -
+ ((!h
+ && op_is_left_mergeable(&(ih->ih_key), Sh->b_size)) ? IH_SIZE : 0)
+ -
+ ((!h && r_key
+ && op_is_left_mergeable(r_key, Sh->b_size)) ? IH_SIZE : 0)
+ + ((h) ? KEY_SIZE : 0)) {
+ /* node can not be removed */
+ if (sfree >= levbytes) { /* new item fits into node S[h] without any shifting */
+ if (!h)
+ tb->s0num =
+ B_NR_ITEMS(Sh) +
+ ((mode == M_INSERT) ? 1 : 0);
+ set_parameters(tb, h, 0, 0, 1, NULL, -1, -1);
+ return NO_BALANCING_NEEDED;
+ }
}
- }
- PROC_INFO_INC( tb -> tb_sb, can_node_be_removed[ h ] );
- return !NO_BALANCING_NEEDED;
+ PROC_INFO_INC(tb->tb_sb, can_node_be_removed[h]);
+ return !NO_BALANCING_NEEDED;
}
-
-
/* Check whether current node S[h] is balanced when increasing its size by
* Inserting or Pasting.
* Calculate parameters for balancing for current level h.
@@ -1182,154 +1210,157 @@ static inline int can_node_be_removed (int mode, int lfree, int sfree, int rfree
* -2 - no disk space.
*/
/* ip means Inserting or Pasting */
-static int ip_check_balance (struct tree_balance * tb, int h)
+static int ip_check_balance(struct tree_balance *tb, int h)
{
- struct virtual_node * vn = tb->tb_vn;
- int levbytes, /* Number of bytes that must be inserted into (value
- is negative if bytes are deleted) buffer which
- contains node being balanced. The mnemonic is
- that the attempted change in node space used level
- is levbytes bytes. */
- n_ret_value;
-
- int lfree, sfree, rfree /* free space in L, S and R */;
-
- /* nver is short for number of vertixes, and lnver is the number if
- we shift to the left, rnver is the number if we shift to the
- right, and lrnver is the number if we shift in both directions.
- The goal is to minimize first the number of vertixes, and second,
- the number of vertixes whose contents are changed by shifting,
- and third the number of uncached vertixes whose contents are
- changed by shifting and must be read from disk. */
- int nver, lnver, rnver, lrnver;
-
- /* used at leaf level only, S0 = S[0] is the node being balanced,
- sInum [ I = 0,1,2 ] is the number of items that will
- remain in node SI after balancing. S1 and S2 are new
- nodes that might be created. */
-
- /* we perform 8 calls to get_num_ver(). For each call we calculate five parameters.
- where 4th parameter is s1bytes and 5th - s2bytes
- */
- short snum012[40] = {0,}; /* s0num, s1num, s2num for 8 cases
- 0,1 - do not shift and do not shift but bottle
- 2 - shift only whole item to left
- 3 - shift to left and bottle as much as possible
- 4,5 - shift to right (whole items and as much as possible
- 6,7 - shift to both directions (whole items and as much as possible)
- */
-
- /* Sh is the node whose balance is currently being checked */
- struct buffer_head * Sh;
-
- Sh = PATH_H_PBUFFER (tb->tb_path, h);
- levbytes = tb->insert_size[h];
-
- /* Calculate balance parameters for creating new root. */
- if ( ! Sh ) {
- if ( ! h )
- reiserfs_panic (tb->tb_sb, "vs-8210: ip_check_balance: S[0] can not be 0");
- switch ( n_ret_value = get_empty_nodes (tb, h) ) {
- case CARRY_ON:
- set_parameters (tb, h, 0, 0, 1, NULL, -1, -1);
- return NO_BALANCING_NEEDED; /* no balancing for higher levels needed */
-
- case NO_DISK_SPACE:
- case REPEAT_SEARCH:
- return n_ret_value;
- default:
- reiserfs_panic(tb->tb_sb, "vs-8215: ip_check_balance: incorrect return value of get_empty_nodes");
+ struct virtual_node *vn = tb->tb_vn;
+ int levbytes, /* Number of bytes that must be inserted into (value
+ is negative if bytes are deleted) buffer which
+ contains node being balanced. The mnemonic is
+ that the attempted change in node space used level
+ is levbytes bytes. */
+ n_ret_value;
+
+ int lfree, sfree, rfree /* free space in L, S and R */ ;
+
+ /* nver is short for number of vertixes, and lnver is the number if
+ we shift to the left, rnver is the number if we shift to the
+ right, and lrnver is the number if we shift in both directions.
+ The goal is to minimize first the number of vertixes, and second,
+ the number of vertixes whose contents are changed by shifting,
+ and third the number of uncached vertixes whose contents are
+ changed by shifting and must be read from disk. */
+ int nver, lnver, rnver, lrnver;
+
+ /* used at leaf level only, S0 = S[0] is the node being balanced,
+ sInum [ I = 0,1,2 ] is the number of items that will
+ remain in node SI after balancing. S1 and S2 are new
+ nodes that might be created. */
+
+ /* we perform 8 calls to get_num_ver(). For each call we calculate five parameters.
+ where 4th parameter is s1bytes and 5th - s2bytes
+ */
+ short snum012[40] = { 0, }; /* s0num, s1num, s2num for 8 cases
+ 0,1 - do not shift and do not shift but bottle
+ 2 - shift only whole item to left
+ 3 - shift to left and bottle as much as possible
+ 4,5 - shift to right (whole items and as much as possible
+ 6,7 - shift to both directions (whole items and as much as possible)
+ */
+
+ /* Sh is the node whose balance is currently being checked */
+ struct buffer_head *Sh;
+
+ Sh = PATH_H_PBUFFER(tb->tb_path, h);
+ levbytes = tb->insert_size[h];
+
+ /* Calculate balance parameters for creating new root. */
+ if (!Sh) {
+ if (!h)
+ reiserfs_panic(tb->tb_sb,
+ "vs-8210: ip_check_balance: S[0] can not be 0");
+ switch (n_ret_value = get_empty_nodes(tb, h)) {
+ case CARRY_ON:
+ set_parameters(tb, h, 0, 0, 1, NULL, -1, -1);
+ return NO_BALANCING_NEEDED; /* no balancing for higher levels needed */
+
+ case NO_DISK_SPACE:
+ case REPEAT_SEARCH:
+ return n_ret_value;
+ default:
+ reiserfs_panic(tb->tb_sb,
+ "vs-8215: ip_check_balance: incorrect return value of get_empty_nodes");
+ }
}
- }
-
- if ( (n_ret_value = get_parents (tb, h)) != CARRY_ON ) /* get parents of S[h] neighbors. */
- return n_ret_value;
-
- sfree = B_FREE_SPACE (Sh);
-
- /* get free space of neighbors */
- rfree = get_rfree (tb, h);
- lfree = get_lfree (tb, h);
-
- if (can_node_be_removed (vn->vn_mode, lfree, sfree, rfree, tb, h) == NO_BALANCING_NEEDED)
- /* and new item fits into node S[h] without any shifting */
- return NO_BALANCING_NEEDED;
-
- create_virtual_node (tb, h);
-
- /*
- determine maximal number of items we can shift to the left neighbor (in tb structure)
- and the maximal number of bytes that can flow to the left neighbor
- from the left most liquid item that cannot be shifted from S[0] entirely (returned value)
- */
- check_left (tb, h, lfree);
-
- /*
- determine maximal number of items we can shift to the right neighbor (in tb structure)
- and the maximal number of bytes that can flow to the right neighbor
- from the right most liquid item that cannot be shifted from S[0] entirely (returned value)
- */
- check_right (tb, h, rfree);
-
-
- /* all contents of internal node S[h] can be moved into its
- neighbors, S[h] will be removed after balancing */
- if (h && (tb->rnum[h] + tb->lnum[h] >= vn->vn_nr_item + 1)) {
- int to_r;
-
- /* Since we are working on internal nodes, and our internal
- nodes have fixed size entries, then we can balance by the
- number of items rather than the space they consume. In this
- routine we set the left node equal to the right node,
- allowing a difference of less than or equal to 1 child
- pointer. */
- to_r = ((MAX_NR_KEY(Sh)<<1)+2-tb->lnum[h]-tb->rnum[h]+vn->vn_nr_item+1)/2 -
- (MAX_NR_KEY(Sh) + 1 - tb->rnum[h]);
- set_parameters (tb, h, vn->vn_nr_item + 1 - to_r, to_r, 0, NULL, -1, -1);
- return CARRY_ON;
- }
-
- /* this checks balance condition, that any two neighboring nodes can not fit in one node */
- RFALSE( h &&
- ( tb->lnum[h] >= vn->vn_nr_item + 1 ||
- tb->rnum[h] >= vn->vn_nr_item + 1),
- "vs-8220: tree is not balanced on internal level");
- RFALSE( ! h && ((tb->lnum[h] >= vn->vn_nr_item && (tb->lbytes == -1)) ||
- (tb->rnum[h] >= vn->vn_nr_item && (tb->rbytes == -1)) ),
- "vs-8225: tree is not balanced on leaf level");
-
- /* all contents of S[0] can be moved into its neighbors
- S[0] will be removed after balancing. */
- if (!h && is_leaf_removable (tb))
- return CARRY_ON;
+ if ((n_ret_value = get_parents(tb, h)) != CARRY_ON) /* get parents of S[h] neighbors. */
+ return n_ret_value;
- /* why do we perform this check here rather than earlier??
- Answer: we can win 1 node in some cases above. Moreover we
- checked it above, when we checked, that S[0] is not removable
- in principle */
- if (sfree >= levbytes) { /* new item fits into node S[h] without any shifting */
- if ( ! h )
- tb->s0num = vn->vn_nr_item;
- set_parameters (tb, h, 0, 0, 1, NULL, -1, -1);
- return NO_BALANCING_NEEDED;
- }
+ sfree = B_FREE_SPACE(Sh);
+
+ /* get free space of neighbors */
+ rfree = get_rfree(tb, h);
+ lfree = get_lfree(tb, h);
+
+ if (can_node_be_removed(vn->vn_mode, lfree, sfree, rfree, tb, h) ==
+ NO_BALANCING_NEEDED)
+ /* and new item fits into node S[h] without any shifting */
+ return NO_BALANCING_NEEDED;
+ create_virtual_node(tb, h);
- {
- int lpar, rpar, nset, lset, rset, lrset;
- /*
- * regular overflowing of the node
+ /*
+ determine maximal number of items we can shift to the left neighbor (in tb structure)
+ and the maximal number of bytes that can flow to the left neighbor
+ from the left most liquid item that cannot be shifted from S[0] entirely (returned value)
*/
+ check_left(tb, h, lfree);
- /* get_num_ver works in 2 modes (FLOW & NO_FLOW)
- lpar, rpar - number of items we can shift to left/right neighbor (including splitting item)
- nset, lset, rset, lrset - shows, whether flowing items give better packing
- */
+ /*
+ determine maximal number of items we can shift to the right neighbor (in tb structure)
+ and the maximal number of bytes that can flow to the right neighbor
+ from the right most liquid item that cannot be shifted from S[0] entirely (returned value)
+ */
+ check_right(tb, h, rfree);
+
+ /* all contents of internal node S[h] can be moved into its
+ neighbors, S[h] will be removed after balancing */
+ if (h && (tb->rnum[h] + tb->lnum[h] >= vn->vn_nr_item + 1)) {
+ int to_r;
+
+ /* Since we are working on internal nodes, and our internal
+ nodes have fixed size entries, then we can balance by the
+ number of items rather than the space they consume. In this
+ routine we set the left node equal to the right node,
+ allowing a difference of less than or equal to 1 child
+ pointer. */
+ to_r =
+ ((MAX_NR_KEY(Sh) << 1) + 2 - tb->lnum[h] - tb->rnum[h] +
+ vn->vn_nr_item + 1) / 2 - (MAX_NR_KEY(Sh) + 1 -
+ tb->rnum[h]);
+ set_parameters(tb, h, vn->vn_nr_item + 1 - to_r, to_r, 0, NULL,
+ -1, -1);
+ return CARRY_ON;
+ }
+
+ /* this checks balance condition, that any two neighboring nodes can not fit in one node */
+ RFALSE(h &&
+ (tb->lnum[h] >= vn->vn_nr_item + 1 ||
+ tb->rnum[h] >= vn->vn_nr_item + 1),
+ "vs-8220: tree is not balanced on internal level");
+ RFALSE(!h && ((tb->lnum[h] >= vn->vn_nr_item && (tb->lbytes == -1)) ||
+ (tb->rnum[h] >= vn->vn_nr_item && (tb->rbytes == -1))),
+ "vs-8225: tree is not balanced on leaf level");
+
+ /* all contents of S[0] can be moved into its neighbors
+ S[0] will be removed after balancing. */
+ if (!h && is_leaf_removable(tb))
+ return CARRY_ON;
+
+ /* why do we perform this check here rather than earlier??
+ Answer: we can win 1 node in some cases above. Moreover we
+ checked it above, when we checked, that S[0] is not removable
+ in principle */
+ if (sfree >= levbytes) { /* new item fits into node S[h] without any shifting */
+ if (!h)
+ tb->s0num = vn->vn_nr_item;
+ set_parameters(tb, h, 0, 0, 1, NULL, -1, -1);
+ return NO_BALANCING_NEEDED;
+ }
+
+ {
+ int lpar, rpar, nset, lset, rset, lrset;
+ /*
+ * regular overflowing of the node
+ */
+
+ /* get_num_ver works in 2 modes (FLOW & NO_FLOW)
+ lpar, rpar - number of items we can shift to left/right neighbor (including splitting item)
+ nset, lset, rset, lrset - shows, whether flowing items give better packing
+ */
#define FLOW 1
-#define NO_FLOW 0 /* do not any splitting */
+#define NO_FLOW 0 /* do not any splitting */
- /* we choose one the following */
+ /* we choose one the following */
#define NOTHING_SHIFT_NO_FLOW 0
#define NOTHING_SHIFT_FLOW 5
#define LEFT_SHIFT_NO_FLOW 10
@@ -1339,164 +1370,173 @@ static int ip_check_balance (struct tree_balance * tb, int h)
#define LR_SHIFT_NO_FLOW 30
#define LR_SHIFT_FLOW 35
+ lpar = tb->lnum[h];
+ rpar = tb->rnum[h];
+
+ /* calculate number of blocks S[h] must be split into when
+ nothing is shifted to the neighbors,
+ as well as number of items in each part of the split node (s012 numbers),
+ and number of bytes (s1bytes) of the shared drop which flow to S1 if any */
+ nset = NOTHING_SHIFT_NO_FLOW;
+ nver = get_num_ver(vn->vn_mode, tb, h,
+ 0, -1, h ? vn->vn_nr_item : 0, -1,
+ snum012, NO_FLOW);
+
+ if (!h) {
+ int nver1;
+
+ /* note, that in this case we try to bottle between S[0] and S1 (S1 - the first new node) */
+ nver1 = get_num_ver(vn->vn_mode, tb, h,
+ 0, -1, 0, -1,
+ snum012 + NOTHING_SHIFT_FLOW, FLOW);
+ if (nver > nver1)
+ nset = NOTHING_SHIFT_FLOW, nver = nver1;
+ }
- lpar = tb->lnum[h];
- rpar = tb->rnum[h];
-
-
- /* calculate number of blocks S[h] must be split into when
- nothing is shifted to the neighbors,
- as well as number of items in each part of the split node (s012 numbers),
- and number of bytes (s1bytes) of the shared drop which flow to S1 if any */
- nset = NOTHING_SHIFT_NO_FLOW;
- nver = get_num_ver (vn->vn_mode, tb, h,
- 0, -1, h?vn->vn_nr_item:0, -1,
- snum012, NO_FLOW);
-
- if (!h)
- {
- int nver1;
-
- /* note, that in this case we try to bottle between S[0] and S1 (S1 - the first new node) */
- nver1 = get_num_ver (vn->vn_mode, tb, h,
- 0, -1, 0, -1,
- snum012 + NOTHING_SHIFT_FLOW, FLOW);
- if (nver > nver1)
- nset = NOTHING_SHIFT_FLOW, nver = nver1;
- }
-
-
- /* calculate number of blocks S[h] must be split into when
- l_shift_num first items and l_shift_bytes of the right most
- liquid item to be shifted are shifted to the left neighbor,
- as well as number of items in each part of the splitted node (s012 numbers),
- and number of bytes (s1bytes) of the shared drop which flow to S1 if any
- */
- lset = LEFT_SHIFT_NO_FLOW;
- lnver = get_num_ver (vn->vn_mode, tb, h,
- lpar - (( h || tb->lbytes == -1 ) ? 0 : 1), -1, h ? vn->vn_nr_item:0, -1,
- snum012 + LEFT_SHIFT_NO_FLOW, NO_FLOW);
- if (!h)
- {
- int lnver1;
-
- lnver1 = get_num_ver (vn->vn_mode, tb, h,
- lpar - ((tb->lbytes != -1) ? 1 : 0), tb->lbytes, 0, -1,
- snum012 + LEFT_SHIFT_FLOW, FLOW);
- if (lnver > lnver1)
- lset = LEFT_SHIFT_FLOW, lnver = lnver1;
- }
-
-
- /* calculate number of blocks S[h] must be split into when
- r_shift_num first items and r_shift_bytes of the left most
- liquid item to be shifted are shifted to the right neighbor,
- as well as number of items in each part of the splitted node (s012 numbers),
- and number of bytes (s1bytes) of the shared drop which flow to S1 if any
- */
- rset = RIGHT_SHIFT_NO_FLOW;
- rnver = get_num_ver (vn->vn_mode, tb, h,
- 0, -1, h ? (vn->vn_nr_item-rpar) : (rpar - (( tb->rbytes != -1 ) ? 1 : 0)), -1,
- snum012 + RIGHT_SHIFT_NO_FLOW, NO_FLOW);
- if (!h)
- {
- int rnver1;
-
- rnver1 = get_num_ver (vn->vn_mode, tb, h,
- 0, -1, (rpar - ((tb->rbytes != -1) ? 1 : 0)), tb->rbytes,
- snum012 + RIGHT_SHIFT_FLOW, FLOW);
-
- if (rnver > rnver1)
- rset = RIGHT_SHIFT_FLOW, rnver = rnver1;
- }
-
-
- /* calculate number of blocks S[h] must be split into when
- items are shifted in both directions,
- as well as number of items in each part of the splitted node (s012 numbers),
- and number of bytes (s1bytes) of the shared drop which flow to S1 if any
- */
- lrset = LR_SHIFT_NO_FLOW;
- lrnver = get_num_ver (vn->vn_mode, tb, h,
- lpar - ((h || tb->lbytes == -1) ? 0 : 1), -1, h ? (vn->vn_nr_item-rpar):(rpar - ((tb->rbytes != -1) ? 1 : 0)), -1,
- snum012 + LR_SHIFT_NO_FLOW, NO_FLOW);
- if (!h)
- {
- int lrnver1;
-
- lrnver1 = get_num_ver (vn->vn_mode, tb, h,
- lpar - ((tb->lbytes != -1) ? 1 : 0), tb->lbytes, (rpar - ((tb->rbytes != -1) ? 1 : 0)), tb->rbytes,
- snum012 + LR_SHIFT_FLOW, FLOW);
- if (lrnver > lrnver1)
- lrset = LR_SHIFT_FLOW, lrnver = lrnver1;
- }
-
-
+ /* calculate number of blocks S[h] must be split into when
+ l_shift_num first items and l_shift_bytes of the right most
+ liquid item to be shifted are shifted to the left neighbor,
+ as well as number of items in each part of the splitted node (s012 numbers),
+ and number of bytes (s1bytes) of the shared drop which flow to S1 if any
+ */
+ lset = LEFT_SHIFT_NO_FLOW;
+ lnver = get_num_ver(vn->vn_mode, tb, h,
+ lpar - ((h || tb->lbytes == -1) ? 0 : 1),
+ -1, h ? vn->vn_nr_item : 0, -1,
+ snum012 + LEFT_SHIFT_NO_FLOW, NO_FLOW);
+ if (!h) {
+ int lnver1;
+
+ lnver1 = get_num_ver(vn->vn_mode, tb, h,
+ lpar -
+ ((tb->lbytes != -1) ? 1 : 0),
+ tb->lbytes, 0, -1,
+ snum012 + LEFT_SHIFT_FLOW, FLOW);
+ if (lnver > lnver1)
+ lset = LEFT_SHIFT_FLOW, lnver = lnver1;
+ }
- /* Our general shifting strategy is:
- 1) to minimized number of new nodes;
- 2) to minimized number of neighbors involved in shifting;
- 3) to minimized number of disk reads; */
+ /* calculate number of blocks S[h] must be split into when
+ r_shift_num first items and r_shift_bytes of the left most
+ liquid item to be shifted are shifted to the right neighbor,
+ as well as number of items in each part of the splitted node (s012 numbers),
+ and number of bytes (s1bytes) of the shared drop which flow to S1 if any
+ */
+ rset = RIGHT_SHIFT_NO_FLOW;
+ rnver = get_num_ver(vn->vn_mode, tb, h,
+ 0, -1,
+ h ? (vn->vn_nr_item - rpar) : (rpar -
+ ((tb->
+ rbytes !=
+ -1) ? 1 :
+ 0)), -1,
+ snum012 + RIGHT_SHIFT_NO_FLOW, NO_FLOW);
+ if (!h) {
+ int rnver1;
+
+ rnver1 = get_num_ver(vn->vn_mode, tb, h,
+ 0, -1,
+ (rpar -
+ ((tb->rbytes != -1) ? 1 : 0)),
+ tb->rbytes,
+ snum012 + RIGHT_SHIFT_FLOW, FLOW);
+
+ if (rnver > rnver1)
+ rset = RIGHT_SHIFT_FLOW, rnver = rnver1;
+ }
- /* we can win TWO or ONE nodes by shifting in both directions */
- if (lrnver < lnver && lrnver < rnver)
- {
- RFALSE( h &&
- (tb->lnum[h] != 1 ||
- tb->rnum[h] != 1 ||
- lrnver != 1 || rnver != 2 || lnver != 2 || h != 1),
- "vs-8230: bad h");
- if (lrset == LR_SHIFT_FLOW)
- set_parameters (tb, h, tb->lnum[h], tb->rnum[h], lrnver, snum012 + lrset,
- tb->lbytes, tb->rbytes);
- else
- set_parameters (tb, h, tb->lnum[h] - ((tb->lbytes == -1) ? 0 : 1),
- tb->rnum[h] - ((tb->rbytes == -1) ? 0 : 1), lrnver, snum012 + lrset, -1, -1);
-
- return CARRY_ON;
- }
+ /* calculate number of blocks S[h] must be split into when
+ items are shifted in both directions,
+ as well as number of items in each part of the splitted node (s012 numbers),
+ and number of bytes (s1bytes) of the shared drop which flow to S1 if any
+ */
+ lrset = LR_SHIFT_NO_FLOW;
+ lrnver = get_num_ver(vn->vn_mode, tb, h,
+ lpar - ((h || tb->lbytes == -1) ? 0 : 1),
+ -1,
+ h ? (vn->vn_nr_item - rpar) : (rpar -
+ ((tb->
+ rbytes !=
+ -1) ? 1 :
+ 0)), -1,
+ snum012 + LR_SHIFT_NO_FLOW, NO_FLOW);
+ if (!h) {
+ int lrnver1;
+
+ lrnver1 = get_num_ver(vn->vn_mode, tb, h,
+ lpar -
+ ((tb->lbytes != -1) ? 1 : 0),
+ tb->lbytes,
+ (rpar -
+ ((tb->rbytes != -1) ? 1 : 0)),
+ tb->rbytes,
+ snum012 + LR_SHIFT_FLOW, FLOW);
+ if (lrnver > lrnver1)
+ lrset = LR_SHIFT_FLOW, lrnver = lrnver1;
+ }
- /* if shifting doesn't lead to better packing then don't shift */
- if (nver == lrnver)
- {
- set_parameters (tb, h, 0, 0, nver, snum012 + nset, -1, -1);
- return CARRY_ON;
- }
+ /* Our general shifting strategy is:
+ 1) to minimized number of new nodes;
+ 2) to minimized number of neighbors involved in shifting;
+ 3) to minimized number of disk reads; */
+
+ /* we can win TWO or ONE nodes by shifting in both directions */
+ if (lrnver < lnver && lrnver < rnver) {
+ RFALSE(h &&
+ (tb->lnum[h] != 1 ||
+ tb->rnum[h] != 1 ||
+ lrnver != 1 || rnver != 2 || lnver != 2
+ || h != 1), "vs-8230: bad h");
+ if (lrset == LR_SHIFT_FLOW)
+ set_parameters(tb, h, tb->lnum[h], tb->rnum[h],
+ lrnver, snum012 + lrset,
+ tb->lbytes, tb->rbytes);
+ else
+ set_parameters(tb, h,
+ tb->lnum[h] -
+ ((tb->lbytes == -1) ? 0 : 1),
+ tb->rnum[h] -
+ ((tb->rbytes == -1) ? 0 : 1),
+ lrnver, snum012 + lrset, -1, -1);
+
+ return CARRY_ON;
+ }
+ /* if shifting doesn't lead to better packing then don't shift */
+ if (nver == lrnver) {
+ set_parameters(tb, h, 0, 0, nver, snum012 + nset, -1,
+ -1);
+ return CARRY_ON;
+ }
- /* now we know that for better packing shifting in only one
- direction either to the left or to the right is required */
+ /* now we know that for better packing shifting in only one
+ direction either to the left or to the right is required */
- /* if shifting to the left is better than shifting to the right */
- if (lnver < rnver)
- {
- SET_PAR_SHIFT_LEFT;
- return CARRY_ON;
- }
+ /* if shifting to the left is better than shifting to the right */
+ if (lnver < rnver) {
+ SET_PAR_SHIFT_LEFT;
+ return CARRY_ON;
+ }
- /* if shifting to the right is better than shifting to the left */
- if (lnver > rnver)
- {
- SET_PAR_SHIFT_RIGHT;
- return CARRY_ON;
- }
+ /* if shifting to the right is better than shifting to the left */
+ if (lnver > rnver) {
+ SET_PAR_SHIFT_RIGHT;
+ return CARRY_ON;
+ }
+ /* now shifting in either direction gives the same number
+ of nodes and we can make use of the cached neighbors */
+ if (is_left_neighbor_in_cache(tb, h)) {
+ SET_PAR_SHIFT_LEFT;
+ return CARRY_ON;
+ }
- /* now shifting in either direction gives the same number
- of nodes and we can make use of the cached neighbors */
- if (is_left_neighbor_in_cache (tb,h))
- {
- SET_PAR_SHIFT_LEFT;
- return CARRY_ON;
+ /* shift to the right independently on whether the right neighbor in cache or not */
+ SET_PAR_SHIFT_RIGHT;
+ return CARRY_ON;
}
-
- /* shift to the right independently on whether the right neighbor in cache or not */
- SET_PAR_SHIFT_RIGHT;
- return CARRY_ON;
- }
}
-
/* Check whether current node S[h] is balanced when Decreasing its size by
* Deleting or Cutting for INTERNAL node of S+tree.
* Calculate parameters for balancing for current level h.
@@ -1513,157 +1553,173 @@ static int ip_check_balance (struct tree_balance * tb, int h)
* Note: Items of internal nodes have fixed size, so the balance condition for
* the internal part of S+tree is as for the B-trees.
*/
-static int dc_check_balance_internal (struct tree_balance * tb, int h)
+static int dc_check_balance_internal(struct tree_balance *tb, int h)
{
- struct virtual_node * vn = tb->tb_vn;
+ struct virtual_node *vn = tb->tb_vn;
- /* Sh is the node whose balance is currently being checked,
- and Fh is its father. */
- struct buffer_head * Sh, * Fh;
- int maxsize,
- n_ret_value;
- int lfree, rfree /* free space in L and R */;
+ /* Sh is the node whose balance is currently being checked,
+ and Fh is its father. */
+ struct buffer_head *Sh, *Fh;
+ int maxsize, n_ret_value;
+ int lfree, rfree /* free space in L and R */ ;
- Sh = PATH_H_PBUFFER (tb->tb_path, h);
- Fh = PATH_H_PPARENT (tb->tb_path, h);
+ Sh = PATH_H_PBUFFER(tb->tb_path, h);
+ Fh = PATH_H_PPARENT(tb->tb_path, h);
- maxsize = MAX_CHILD_SIZE(Sh);
+ maxsize = MAX_CHILD_SIZE(Sh);
/* using tb->insert_size[h], which is negative in this case, create_virtual_node calculates: */
/* new_nr_item = number of items node would have if operation is */
/* performed without balancing (new_nr_item); */
- create_virtual_node (tb, h);
+ create_virtual_node(tb, h);
- if ( ! Fh )
- { /* S[h] is the root. */
- if ( vn->vn_nr_item > 0 )
- {
- set_parameters (tb, h, 0, 0, 1, NULL, -1, -1);
- return NO_BALANCING_NEEDED; /* no balancing for higher levels needed */
+ if (!Fh) { /* S[h] is the root. */
+ if (vn->vn_nr_item > 0) {
+ set_parameters(tb, h, 0, 0, 1, NULL, -1, -1);
+ return NO_BALANCING_NEEDED; /* no balancing for higher levels needed */
+ }
+ /* new_nr_item == 0.
+ * Current root will be deleted resulting in
+ * decrementing the tree height. */
+ set_parameters(tb, h, 0, 0, 0, NULL, -1, -1);
+ return CARRY_ON;
+ }
+
+ if ((n_ret_value = get_parents(tb, h)) != CARRY_ON)
+ return n_ret_value;
+
+ /* get free space of neighbors */
+ rfree = get_rfree(tb, h);
+ lfree = get_lfree(tb, h);
+
+ /* determine maximal number of items we can fit into neighbors */
+ check_left(tb, h, lfree);
+ check_right(tb, h, rfree);
+
+ if (vn->vn_nr_item >= MIN_NR_KEY(Sh)) { /* Balance condition for the internal node is valid.
+ * In this case we balance only if it leads to better packing. */
+ if (vn->vn_nr_item == MIN_NR_KEY(Sh)) { /* Here we join S[h] with one of its neighbors,
+ * which is impossible with greater values of new_nr_item. */
+ if (tb->lnum[h] >= vn->vn_nr_item + 1) {
+ /* All contents of S[h] can be moved to L[h]. */
+ int n;
+ int order_L;
+
+ order_L =
+ ((n =
+ PATH_H_B_ITEM_ORDER(tb->tb_path,
+ h)) ==
+ 0) ? B_NR_ITEMS(tb->FL[h]) : n - 1;
+ n = dc_size(B_N_CHILD(tb->FL[h], order_L)) /
+ (DC_SIZE + KEY_SIZE);
+ set_parameters(tb, h, -n - 1, 0, 0, NULL, -1,
+ -1);
+ return CARRY_ON;
+ }
+
+ if (tb->rnum[h] >= vn->vn_nr_item + 1) {
+ /* All contents of S[h] can be moved to R[h]. */
+ int n;
+ int order_R;
+
+ order_R =
+ ((n =
+ PATH_H_B_ITEM_ORDER(tb->tb_path,
+ h)) ==
+ B_NR_ITEMS(Fh)) ? 0 : n + 1;
+ n = dc_size(B_N_CHILD(tb->FR[h], order_R)) /
+ (DC_SIZE + KEY_SIZE);
+ set_parameters(tb, h, 0, -n - 1, 0, NULL, -1,
+ -1);
+ return CARRY_ON;
+ }
+ }
+
+ if (tb->rnum[h] + tb->lnum[h] >= vn->vn_nr_item + 1) {
+ /* All contents of S[h] can be moved to the neighbors (L[h] & R[h]). */
+ int to_r;
+
+ to_r =
+ ((MAX_NR_KEY(Sh) << 1) + 2 - tb->lnum[h] -
+ tb->rnum[h] + vn->vn_nr_item + 1) / 2 -
+ (MAX_NR_KEY(Sh) + 1 - tb->rnum[h]);
+ set_parameters(tb, h, vn->vn_nr_item + 1 - to_r, to_r,
+ 0, NULL, -1, -1);
+ return CARRY_ON;
+ }
+
+ /* Balancing does not lead to better packing. */
+ set_parameters(tb, h, 0, 0, 1, NULL, -1, -1);
+ return NO_BALANCING_NEEDED;
}
- /* new_nr_item == 0.
- * Current root will be deleted resulting in
- * decrementing the tree height. */
- set_parameters (tb, h, 0, 0, 0, NULL, -1, -1);
- return CARRY_ON;
- }
-
- if ( (n_ret_value = get_parents(tb,h)) != CARRY_ON )
- return n_ret_value;
-
-
- /* get free space of neighbors */
- rfree = get_rfree (tb, h);
- lfree = get_lfree (tb, h);
-
- /* determine maximal number of items we can fit into neighbors */
- check_left (tb, h, lfree);
- check_right (tb, h, rfree);
-
-
- if ( vn->vn_nr_item >= MIN_NR_KEY(Sh) )
- { /* Balance condition for the internal node is valid.
- * In this case we balance only if it leads to better packing. */
- if ( vn->vn_nr_item == MIN_NR_KEY(Sh) )
- { /* Here we join S[h] with one of its neighbors,
- * which is impossible with greater values of new_nr_item. */
- if ( tb->lnum[h] >= vn->vn_nr_item + 1 )
- {
- /* All contents of S[h] can be moved to L[h]. */
- int n;
- int order_L;
-
- order_L = ((n=PATH_H_B_ITEM_ORDER(tb->tb_path, h))==0) ? B_NR_ITEMS(tb->FL[h]) : n - 1;
- n = dc_size(B_N_CHILD(tb->FL[h],order_L)) / (DC_SIZE + KEY_SIZE);
- set_parameters (tb, h, -n-1, 0, 0, NULL, -1, -1);
- return CARRY_ON;
- }
-
- if ( tb->rnum[h] >= vn->vn_nr_item + 1 )
- {
- /* All contents of S[h] can be moved to R[h]. */
- int n;
- int order_R;
-
- order_R = ((n=PATH_H_B_ITEM_ORDER(tb->tb_path, h))==B_NR_ITEMS(Fh)) ? 0 : n + 1;
- n = dc_size(B_N_CHILD(tb->FR[h],order_R)) / (DC_SIZE + KEY_SIZE);
- set_parameters (tb, h, 0, -n-1, 0, NULL, -1, -1);
- return CARRY_ON;
- }
+
+ /* Current node contain insufficient number of items. Balancing is required. */
+ /* Check whether we can merge S[h] with left neighbor. */
+ if (tb->lnum[h] >= vn->vn_nr_item + 1)
+ if (is_left_neighbor_in_cache(tb, h)
+ || tb->rnum[h] < vn->vn_nr_item + 1 || !tb->FR[h]) {
+ int n;
+ int order_L;
+
+ order_L =
+ ((n =
+ PATH_H_B_ITEM_ORDER(tb->tb_path,
+ h)) ==
+ 0) ? B_NR_ITEMS(tb->FL[h]) : n - 1;
+ n = dc_size(B_N_CHILD(tb->FL[h], order_L)) / (DC_SIZE +
+ KEY_SIZE);
+ set_parameters(tb, h, -n - 1, 0, 0, NULL, -1, -1);
+ return CARRY_ON;
+ }
+
+ /* Check whether we can merge S[h] with right neighbor. */
+ if (tb->rnum[h] >= vn->vn_nr_item + 1) {
+ int n;
+ int order_R;
+
+ order_R =
+ ((n =
+ PATH_H_B_ITEM_ORDER(tb->tb_path,
+ h)) == B_NR_ITEMS(Fh)) ? 0 : (n + 1);
+ n = dc_size(B_N_CHILD(tb->FR[h], order_R)) / (DC_SIZE +
+ KEY_SIZE);
+ set_parameters(tb, h, 0, -n - 1, 0, NULL, -1, -1);
+ return CARRY_ON;
}
- if (tb->rnum[h] + tb->lnum[h] >= vn->vn_nr_item + 1)
- {
- /* All contents of S[h] can be moved to the neighbors (L[h] & R[h]). */
- int to_r;
+ /* All contents of S[h] can be moved to the neighbors (L[h] & R[h]). */
+ if (tb->rnum[h] + tb->lnum[h] >= vn->vn_nr_item + 1) {
+ int to_r;
+
+ to_r =
+ ((MAX_NR_KEY(Sh) << 1) + 2 - tb->lnum[h] - tb->rnum[h] +
+ vn->vn_nr_item + 1) / 2 - (MAX_NR_KEY(Sh) + 1 -
+ tb->rnum[h]);
+ set_parameters(tb, h, vn->vn_nr_item + 1 - to_r, to_r, 0, NULL,
+ -1, -1);
+ return CARRY_ON;
+ }
- to_r = ((MAX_NR_KEY(Sh)<<1)+2-tb->lnum[h]-tb->rnum[h]+vn->vn_nr_item+1)/2 -
- (MAX_NR_KEY(Sh) + 1 - tb->rnum[h]);
- set_parameters (tb, h, vn->vn_nr_item + 1 - to_r, to_r, 0, NULL, -1, -1);
- return CARRY_ON;
+ /* For internal nodes try to borrow item from a neighbor */
+ RFALSE(!tb->FL[h] && !tb->FR[h], "vs-8235: trying to borrow for root");
+
+ /* Borrow one or two items from caching neighbor */
+ if (is_left_neighbor_in_cache(tb, h) || !tb->FR[h]) {
+ int from_l;
+
+ from_l =
+ (MAX_NR_KEY(Sh) + 1 - tb->lnum[h] + vn->vn_nr_item +
+ 1) / 2 - (vn->vn_nr_item + 1);
+ set_parameters(tb, h, -from_l, 0, 1, NULL, -1, -1);
+ return CARRY_ON;
}
- /* Balancing does not lead to better packing. */
- set_parameters (tb, h, 0, 0, 1, NULL, -1, -1);
- return NO_BALANCING_NEEDED;
- }
-
- /* Current node contain insufficient number of items. Balancing is required. */
- /* Check whether we can merge S[h] with left neighbor. */
- if (tb->lnum[h] >= vn->vn_nr_item + 1)
- if (is_left_neighbor_in_cache (tb,h) || tb->rnum[h] < vn->vn_nr_item + 1 || !tb->FR[h])
- {
- int n;
- int order_L;
-
- order_L = ((n=PATH_H_B_ITEM_ORDER(tb->tb_path, h))==0) ? B_NR_ITEMS(tb->FL[h]) : n - 1;
- n = dc_size(B_N_CHILD(tb->FL[h],order_L)) / (DC_SIZE + KEY_SIZE);
- set_parameters (tb, h, -n-1, 0, 0, NULL, -1, -1);
+ set_parameters(tb, h, 0,
+ -((MAX_NR_KEY(Sh) + 1 - tb->rnum[h] + vn->vn_nr_item +
+ 1) / 2 - (vn->vn_nr_item + 1)), 1, NULL, -1, -1);
return CARRY_ON;
- }
-
- /* Check whether we can merge S[h] with right neighbor. */
- if (tb->rnum[h] >= vn->vn_nr_item + 1)
- {
- int n;
- int order_R;
-
- order_R = ((n=PATH_H_B_ITEM_ORDER(tb->tb_path, h))==B_NR_ITEMS(Fh)) ? 0 : (n + 1);
- n = dc_size(B_N_CHILD(tb->FR[h],order_R)) / (DC_SIZE + KEY_SIZE);
- set_parameters (tb, h, 0, -n-1, 0, NULL, -1, -1);
- return CARRY_ON;
- }
-
- /* All contents of S[h] can be moved to the neighbors (L[h] & R[h]). */
- if (tb->rnum[h] + tb->lnum[h] >= vn->vn_nr_item + 1)
- {
- int to_r;
-
- to_r = ((MAX_NR_KEY(Sh)<<1)+2-tb->lnum[h]-tb->rnum[h]+vn->vn_nr_item+1)/2 -
- (MAX_NR_KEY(Sh) + 1 - tb->rnum[h]);
- set_parameters (tb, h, vn->vn_nr_item + 1 - to_r, to_r, 0, NULL, -1, -1);
- return CARRY_ON;
- }
-
- /* For internal nodes try to borrow item from a neighbor */
- RFALSE( !tb->FL[h] && !tb->FR[h], "vs-8235: trying to borrow for root");
-
- /* Borrow one or two items from caching neighbor */
- if (is_left_neighbor_in_cache (tb,h) || !tb->FR[h])
- {
- int from_l;
-
- from_l = (MAX_NR_KEY(Sh) + 1 - tb->lnum[h] + vn->vn_nr_item + 1) / 2 - (vn->vn_nr_item + 1);
- set_parameters (tb, h, -from_l, 0, 1, NULL, -1, -1);
- return CARRY_ON;
- }
-
- set_parameters (tb, h, 0, -((MAX_NR_KEY(Sh)+1-tb->rnum[h]+vn->vn_nr_item+1)/2-(vn->vn_nr_item+1)), 1,
- NULL, -1, -1);
- return CARRY_ON;
}
-
/* Check whether current node S[h] is balanced when Decreasing its size by
* Deleting or Truncating for LEAF node of S+tree.
* Calculate parameters for balancing for current level h.
@@ -1677,90 +1733,86 @@ static int dc_check_balance_internal (struct tree_balance * tb, int h)
* -1 - no balancing for higher levels needed;
* -2 - no disk space.
*/
-static int dc_check_balance_leaf (struct tree_balance * tb, int h)
+static int dc_check_balance_leaf(struct tree_balance *tb, int h)
{
- struct virtual_node * vn = tb->tb_vn;
-
- /* Number of bytes that must be deleted from
- (value is negative if bytes are deleted) buffer which
- contains node being balanced. The mnemonic is that the
- attempted change in node space used level is levbytes bytes. */
- int levbytes;
- /* the maximal item size */
- int maxsize,
- n_ret_value;
- /* S0 is the node whose balance is currently being checked,
- and F0 is its father. */
- struct buffer_head * S0, * F0;
- int lfree, rfree /* free space in L and R */;
-
- S0 = PATH_H_PBUFFER (tb->tb_path, 0);
- F0 = PATH_H_PPARENT (tb->tb_path, 0);
-
- levbytes = tb->insert_size[h];
-
- maxsize = MAX_CHILD_SIZE(S0); /* maximal possible size of an item */
-
- if ( ! F0 )
- { /* S[0] is the root now. */
-
- RFALSE( -levbytes >= maxsize - B_FREE_SPACE (S0),
- "vs-8240: attempt to create empty buffer tree");
-
- set_parameters (tb, h, 0, 0, 1, NULL, -1, -1);
- return NO_BALANCING_NEEDED;
- }
-
- if ( (n_ret_value = get_parents(tb,h)) != CARRY_ON )
- return n_ret_value;
-
- /* get free space of neighbors */
- rfree = get_rfree (tb, h);
- lfree = get_lfree (tb, h);
-
- create_virtual_node (tb, h);
-
- /* if 3 leaves can be merge to one, set parameters and return */
- if (are_leaves_removable (tb, lfree, rfree))
- return CARRY_ON;
-
- /* determine maximal number of items we can shift to the left/right neighbor
- and the maximal number of bytes that can flow to the left/right neighbor
- from the left/right most liquid item that cannot be shifted from S[0] entirely
- */
- check_left (tb, h, lfree);
- check_right (tb, h, rfree);
-
- /* check whether we can merge S with left neighbor. */
- if (tb->lnum[0] >= vn->vn_nr_item && tb->lbytes == -1)
- 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 */
- !tb->FR[h]) {
-
- RFALSE( !tb->FL[h], "vs-8245: dc_check_balance_leaf: FL[h] must exist");
-
- /* set parameter to merge S[0] with its left neighbor */
- set_parameters (tb, h, -1, 0, 0, NULL, -1, -1);
- return CARRY_ON;
- }
-
- /* check whether we can merge S[0] with right neighbor. */
- if (tb->rnum[0] >= vn->vn_nr_item && tb->rbytes == -1) {
- set_parameters (tb, h, 0, -1, 0, NULL, -1, -1);
- return CARRY_ON;
- }
-
- /* All contents of S[0] can be moved to the neighbors (L[0] & R[0]). Set parameters and return */
- if (is_leaf_removable (tb))
- return CARRY_ON;
-
- /* Balancing is not required. */
- tb->s0num = vn->vn_nr_item;
- set_parameters (tb, h, 0, 0, 1, NULL, -1, -1);
- return NO_BALANCING_NEEDED;
-}
+ struct virtual_node *vn = tb->tb_vn;
+
+ /* Number of bytes that must be deleted from
+ (value is negative if bytes are deleted) buffer which
+ contains node being balanced. The mnemonic is that the
+ attempted change in node space used level is levbytes bytes. */
+ int levbytes;
+ /* the maximal item size */
+ int maxsize, n_ret_value;
+ /* S0 is the node whose balance is currently being checked,
+ and F0 is its father. */
+ struct buffer_head *S0, *F0;
+ int lfree, rfree /* free space in L and R */ ;
+
+ S0 = PATH_H_PBUFFER(tb->tb_path, 0);
+ F0 = PATH_H_PPARENT(tb->tb_path, 0);
+ levbytes = tb->insert_size[h];
+ maxsize = MAX_CHILD_SIZE(S0); /* maximal possible size of an item */
+
+ if (!F0) { /* S[0] is the root now. */
+
+ RFALSE(-levbytes >= maxsize - B_FREE_SPACE(S0),
+ "vs-8240: attempt to create empty buffer tree");
+
+ set_parameters(tb, h, 0, 0, 1, NULL, -1, -1);
+ return NO_BALANCING_NEEDED;
+ }
+
+ if ((n_ret_value = get_parents(tb, h)) != CARRY_ON)
+ return n_ret_value;
+
+ /* get free space of neighbors */
+ rfree = get_rfree(tb, h);
+ lfree = get_lfree(tb, h);
+
+ create_virtual_node(tb, h);
+
+ /* if 3 leaves can be merge to one, set parameters and return */
+ if (are_leaves_removable(tb, lfree, rfree))
+ return CARRY_ON;
+
+ /* determine maximal number of items we can shift to the left/right neighbor
+ and the maximal number of bytes that can flow to the left/right neighbor
+ from the left/right most liquid item that cannot be shifted from S[0] entirely
+ */
+ check_left(tb, h, lfree);
+ check_right(tb, h, rfree);
+
+ /* check whether we can merge S with left neighbor. */
+ if (tb->lnum[0] >= vn->vn_nr_item && tb->lbytes == -1)
+ 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 */
+ !tb->FR[h]) {
+
+ RFALSE(!tb->FL[h],
+ "vs-8245: dc_check_balance_leaf: FL[h] must exist");
+
+ /* set parameter to merge S[0] with its left neighbor */
+ set_parameters(tb, h, -1, 0, 0, NULL, -1, -1);
+ return CARRY_ON;
+ }
+
+ /* check whether we can merge S[0] with right neighbor. */
+ if (tb->rnum[0] >= vn->vn_nr_item && tb->rbytes == -1) {
+ set_parameters(tb, h, 0, -1, 0, NULL, -1, -1);
+ return CARRY_ON;
+ }
+
+ /* All contents of S[0] can be moved to the neighbors (L[0] & R[0]). Set parameters and return */
+ if (is_leaf_removable(tb))
+ return CARRY_ON;
+
+ /* Balancing is not required. */
+ tb->s0num = vn->vn_nr_item;
+ set_parameters(tb, h, 0, 0, 1, NULL, -1, -1);
+ return NO_BALANCING_NEEDED;
+}
/* Check whether current node S[h] is balanced when Decreasing its size by
* Deleting or Cutting.
@@ -1775,18 +1827,17 @@ static int dc_check_balance_leaf (struct tree_balance * tb, int h)
* -1 - no balancing for higher levels needed;
* -2 - no disk space.
*/
-static int dc_check_balance (struct tree_balance * tb, int h)
+static int dc_check_balance(struct tree_balance *tb, int h)
{
- RFALSE( ! (PATH_H_PBUFFER (tb->tb_path, h)), "vs-8250: S is not initialized");
+ RFALSE(!(PATH_H_PBUFFER(tb->tb_path, h)),
+ "vs-8250: S is not initialized");
- if ( h )
- return dc_check_balance_internal (tb, h);
- else
- return dc_check_balance_leaf (tb, h);
+ if (h)
+ return dc_check_balance_internal(tb, h);
+ else
+ return dc_check_balance_leaf(tb, h);
}
-
-
/* Check whether current node S[h] is balanced.
* Calculate parameters for balancing for current level h.
* Parameters:
@@ -1805,83 +1856,80 @@ static int dc_check_balance (struct tree_balance * tb, int h)
* -1 - no balancing for higher levels needed;
* -2 - no disk space.
*/
-static int check_balance (int mode,
- struct tree_balance * tb,
- int h,
- int inum,
- int pos_in_item,
- struct item_head * ins_ih,
- const void * data
- )
+static int check_balance(int mode,
+ struct tree_balance *tb,
+ int h,
+ int inum,
+ int pos_in_item,
+ struct item_head *ins_ih, const void *data)
{
- struct virtual_node * vn;
+ struct virtual_node *vn;
- vn = tb->tb_vn = (struct virtual_node *)(tb->vn_buf);
- vn->vn_free_ptr = (char *)(tb->tb_vn + 1);
- vn->vn_mode = mode;
- vn->vn_affected_item_num = inum;
- vn->vn_pos_in_item = pos_in_item;
- vn->vn_ins_ih = ins_ih;
- vn->vn_data = data;
+ vn = tb->tb_vn = (struct virtual_node *)(tb->vn_buf);
+ vn->vn_free_ptr = (char *)(tb->tb_vn + 1);
+ vn->vn_mode = mode;
+ vn->vn_affected_item_num = inum;
+ vn->vn_pos_in_item = pos_in_item;
+ vn->vn_ins_ih = ins_ih;
+ vn->vn_data = data;
- RFALSE( mode == M_INSERT && !vn->vn_ins_ih,
- "vs-8255: ins_ih can not be 0 in insert mode");
+ RFALSE(mode == M_INSERT && !vn->vn_ins_ih,
+ "vs-8255: ins_ih can not be 0 in insert mode");
- if ( tb->insert_size[h] > 0 )
- /* Calculate balance parameters when size of node is increasing. */
- return ip_check_balance (tb, h);
+ if (tb->insert_size[h] > 0)
+ /* Calculate balance parameters when size of node is increasing. */
+ return ip_check_balance(tb, h);
- /* Calculate balance parameters when size of node is decreasing. */
- return dc_check_balance (tb, h);
+ /* Calculate balance parameters when size of node is decreasing. */
+ return dc_check_balance(tb, h);
}
+/* Check whether parent at the path is the really parent of the current node.*/
+static int get_direct_parent(struct tree_balance *p_s_tb, int n_h)
+{
+ struct buffer_head *p_s_bh;
+ struct path *p_s_path = p_s_tb->tb_path;
+ int n_position,
+ n_path_offset = PATH_H_PATH_OFFSET(p_s_tb->tb_path, n_h);
+
+ /* We are in the root or in the new root. */
+ if (n_path_offset <= FIRST_PATH_ELEMENT_OFFSET) {
+
+ RFALSE(n_path_offset < FIRST_PATH_ELEMENT_OFFSET - 1,
+ "PAP-8260: invalid offset in the path");
+
+ if (PATH_OFFSET_PBUFFER(p_s_path, FIRST_PATH_ELEMENT_OFFSET)->
+ b_blocknr == SB_ROOT_BLOCK(p_s_tb->tb_sb)) {
+ /* Root is not changed. */
+ PATH_OFFSET_PBUFFER(p_s_path, n_path_offset - 1) = NULL;
+ PATH_OFFSET_POSITION(p_s_path, n_path_offset - 1) = 0;
+ return CARRY_ON;
+ }
+ return REPEAT_SEARCH; /* Root is changed and we must recalculate the path. */
+ }
+
+ if (!B_IS_IN_TREE
+ (p_s_bh = PATH_OFFSET_PBUFFER(p_s_path, n_path_offset - 1)))
+ return REPEAT_SEARCH; /* Parent in the path is not in the tree. */
+ if ((n_position =
+ PATH_OFFSET_POSITION(p_s_path,
+ n_path_offset - 1)) > B_NR_ITEMS(p_s_bh))
+ return REPEAT_SEARCH;
-/* Check whether parent at the path is the really parent of the current node.*/
-static int get_direct_parent(
- struct tree_balance * p_s_tb,
- int n_h
- ) {
- struct buffer_head * p_s_bh;
- struct path * p_s_path = p_s_tb->tb_path;
- int n_position,
- n_path_offset = PATH_H_PATH_OFFSET(p_s_tb->tb_path, n_h);
-
- /* We are in the root or in the new root. */
- if ( n_path_offset <= FIRST_PATH_ELEMENT_OFFSET ) {
-
- RFALSE( n_path_offset < FIRST_PATH_ELEMENT_OFFSET - 1,
- "PAP-8260: invalid offset in the path");
-
- if ( PATH_OFFSET_PBUFFER(p_s_path, FIRST_PATH_ELEMENT_OFFSET)->b_blocknr ==
- SB_ROOT_BLOCK (p_s_tb->tb_sb) ) {
- /* Root is not changed. */
- PATH_OFFSET_PBUFFER(p_s_path, n_path_offset - 1) = NULL;
- PATH_OFFSET_POSITION(p_s_path, n_path_offset - 1) = 0;
- return CARRY_ON;
+ if (B_N_CHILD_NUM(p_s_bh, n_position) !=
+ PATH_OFFSET_PBUFFER(p_s_path, n_path_offset)->b_blocknr)
+ /* Parent in the path is not parent of the current node in the tree. */
+ return REPEAT_SEARCH;
+
+ if (buffer_locked(p_s_bh)) {
+ __wait_on_buffer(p_s_bh);
+ if (FILESYSTEM_CHANGED_TB(p_s_tb))
+ return REPEAT_SEARCH;
}
- return REPEAT_SEARCH; /* Root is changed and we must recalculate the path. */
- }
-
- if ( ! B_IS_IN_TREE(p_s_bh = PATH_OFFSET_PBUFFER(p_s_path, n_path_offset - 1)) )
- return REPEAT_SEARCH; /* Parent in the path is not in the tree. */
-
- if ( (n_position = PATH_OFFSET_POSITION(p_s_path, n_path_offset - 1)) > B_NR_ITEMS(p_s_bh) )
- return REPEAT_SEARCH;
-
- if ( B_N_CHILD_NUM(p_s_bh, n_position) != PATH_OFFSET_PBUFFER(p_s_path, n_path_offset)->b_blocknr )
- /* Parent in the path is not parent of the current node in the tree. */
- return REPEAT_SEARCH;
-
- if ( buffer_locked(p_s_bh) ) {
- __wait_on_buffer(p_s_bh);
- if ( FILESYSTEM_CHANGED_TB (p_s_tb) )
- return REPEAT_SEARCH;
- }
-
- return CARRY_ON; /* Parent in the path is unlocked and really parent of the current node. */
-}
+ return CARRY_ON; /* Parent in the path is unlocked and really parent of the current node. */
+}
/* Using lnum[n_h] and rnum[n_h] we should determine what neighbors
* of S[n_h] we
@@ -1889,356 +1937,401 @@ static int get_direct_parent(
* Returns: SCHEDULE_OCCURRED - schedule occurred while the function worked;
* CARRY_ON - schedule didn't occur while the function worked;
*/
-static int get_neighbors(
- struct tree_balance * p_s_tb,
- int n_h
- ) {
- int n_child_position,
- n_path_offset = PATH_H_PATH_OFFSET(p_s_tb->tb_path, n_h + 1);
- unsigned long n_son_number;
- struct super_block * p_s_sb = p_s_tb->tb_sb;
- struct buffer_head * p_s_bh;
-
-
- PROC_INFO_INC( p_s_sb, get_neighbors[ n_h ] );
-
- if ( p_s_tb->lnum[n_h] ) {
- /* We need left neighbor to balance S[n_h]. */
- PROC_INFO_INC( p_s_sb, need_l_neighbor[ n_h ] );
- p_s_bh = PATH_OFFSET_PBUFFER(p_s_tb->tb_path, n_path_offset);
-
- RFALSE( p_s_bh == p_s_tb->FL[n_h] &&
- ! PATH_OFFSET_POSITION(p_s_tb->tb_path, n_path_offset),
- "PAP-8270: invalid position in the parent");
-
- n_child_position = ( p_s_bh == p_s_tb->FL[n_h] ) ? p_s_tb->lkey[n_h] : B_NR_ITEMS (p_s_tb->FL[n_h]);
- n_son_number = B_N_CHILD_NUM(p_s_tb->FL[n_h], n_child_position);
- p_s_bh = sb_bread(p_s_sb, n_son_number);
- if (!p_s_bh)
- return IO_ERROR;
- if ( FILESYSTEM_CHANGED_TB (p_s_tb) ) {
- decrement_bcount(p_s_bh);
- PROC_INFO_INC( p_s_sb, get_neighbors_restart[ n_h ] );
- return REPEAT_SEARCH;
+static int get_neighbors(struct tree_balance *p_s_tb, int n_h)
+{
+ int n_child_position,
+ n_path_offset = PATH_H_PATH_OFFSET(p_s_tb->tb_path, n_h + 1);
+ unsigned long n_son_number;
+ struct super_block *p_s_sb = p_s_tb->tb_sb;
+ struct buffer_head *p_s_bh;
+
+ PROC_INFO_INC(p_s_sb, get_neighbors[n_h]);
+
+ if (p_s_tb->lnum[n_h]) {
+ /* We need left neighbor to balance S[n_h]. */
+ PROC_INFO_INC(p_s_sb, need_l_neighbor[n_h]);
+ p_s_bh = PATH_OFFSET_PBUFFER(p_s_tb->tb_path, n_path_offset);
+
+ RFALSE(p_s_bh == p_s_tb->FL[n_h] &&
+ !PATH_OFFSET_POSITION(p_s_tb->tb_path, n_path_offset),
+ "PAP-8270: invalid position in the parent");
+
+ n_child_position =
+ (p_s_bh ==
+ p_s_tb->FL[n_h]) ? p_s_tb->lkey[n_h] : B_NR_ITEMS(p_s_tb->
+ FL[n_h]);
+ n_son_number = B_N_CHILD_NUM(p_s_tb->FL[n_h], n_child_position);
+ p_s_bh = sb_bread(p_s_sb, n_son_number);
+ if (!p_s_bh)
+ return IO_ERROR;
+ if (FILESYSTEM_CHANGED_TB(p_s_tb)) {
+ decrement_bcount(p_s_bh);
+ PROC_INFO_INC(p_s_sb, get_neighbors_restart[n_h]);
+ return REPEAT_SEARCH;
+ }
+
+ RFALSE(!B_IS_IN_TREE(p_s_tb->FL[n_h]) ||
+ n_child_position > B_NR_ITEMS(p_s_tb->FL[n_h]) ||
+ B_N_CHILD_NUM(p_s_tb->FL[n_h], n_child_position) !=
+ p_s_bh->b_blocknr, "PAP-8275: invalid parent");
+ RFALSE(!B_IS_IN_TREE(p_s_bh), "PAP-8280: invalid child");
+ RFALSE(!n_h &&
+ B_FREE_SPACE(p_s_bh) !=
+ MAX_CHILD_SIZE(p_s_bh) -
+ dc_size(B_N_CHILD(p_s_tb->FL[0], n_child_position)),
+ "PAP-8290: invalid child size of left neighbor");
+
+ decrement_bcount(p_s_tb->L[n_h]);
+ p_s_tb->L[n_h] = p_s_bh;
}
-
- RFALSE( ! B_IS_IN_TREE(p_s_tb->FL[n_h]) ||
- n_child_position > B_NR_ITEMS(p_s_tb->FL[n_h]) ||
- B_N_CHILD_NUM(p_s_tb->FL[n_h], n_child_position) !=
- p_s_bh->b_blocknr, "PAP-8275: invalid parent");
- RFALSE( ! B_IS_IN_TREE(p_s_bh), "PAP-8280: invalid child");
- RFALSE( ! n_h &&
- B_FREE_SPACE (p_s_bh) != MAX_CHILD_SIZE (p_s_bh) - dc_size(B_N_CHILD (p_s_tb->FL[0],n_child_position)),
- "PAP-8290: invalid child size of left neighbor");
-
- decrement_bcount(p_s_tb->L[n_h]);
- p_s_tb->L[n_h] = p_s_bh;
- }
-
-
- if ( p_s_tb->rnum[n_h] ) { /* We need right neighbor to balance S[n_path_offset]. */
- PROC_INFO_INC( p_s_sb, need_r_neighbor[ n_h ] );
- p_s_bh = PATH_OFFSET_PBUFFER(p_s_tb->tb_path, n_path_offset);
-
- RFALSE( p_s_bh == p_s_tb->FR[n_h] &&
- PATH_OFFSET_POSITION(p_s_tb->tb_path, n_path_offset) >= B_NR_ITEMS(p_s_bh),
- "PAP-8295: invalid position in the parent");
-
- n_child_position = ( p_s_bh == p_s_tb->FR[n_h] ) ? p_s_tb->rkey[n_h] + 1 : 0;
- n_son_number = B_N_CHILD_NUM(p_s_tb->FR[n_h], n_child_position);
- p_s_bh = sb_bread(p_s_sb, n_son_number);
- if (!p_s_bh)
- return IO_ERROR;
- if ( FILESYSTEM_CHANGED_TB (p_s_tb) ) {
- decrement_bcount(p_s_bh);
- PROC_INFO_INC( p_s_sb, get_neighbors_restart[ n_h ] );
- return REPEAT_SEARCH;
+
+ if (p_s_tb->rnum[n_h]) { /* We need right neighbor to balance S[n_path_offset]. */
+ PROC_INFO_INC(p_s_sb, need_r_neighbor[n_h]);
+ p_s_bh = PATH_OFFSET_PBUFFER(p_s_tb->tb_path, n_path_offset);
+
+ RFALSE(p_s_bh == p_s_tb->FR[n_h] &&
+ PATH_OFFSET_POSITION(p_s_tb->tb_path,
+ n_path_offset) >=
+ B_NR_ITEMS(p_s_bh),
+ "PAP-8295: invalid position in the parent");
+
+ n_child_position =
+ (p_s_bh == p_s_tb->FR[n_h]) ? p_s_tb->rkey[n_h] + 1 : 0;
+ n_son_number = B_N_CHILD_NUM(p_s_tb->FR[n_h], n_child_position);
+ p_s_bh = sb_bread(p_s_sb, n_son_number);
+ if (!p_s_bh)
+ return IO_ERROR;
+ if (FILESYSTEM_CHANGED_TB(p_s_tb)) {
+ decrement_bcount(p_s_bh);
+ PROC_INFO_INC(p_s_sb, get_neighbors_restart[n_h]);
+ return REPEAT_SEARCH;
+ }
+ decrement_bcount(p_s_tb->R[n_h]);
+ p_s_tb->R[n_h] = p_s_bh;
+
+ RFALSE(!n_h
+ && B_FREE_SPACE(p_s_bh) !=
+ MAX_CHILD_SIZE(p_s_bh) -
+ dc_size(B_N_CHILD(p_s_tb->FR[0], n_child_position)),
+ "PAP-8300: invalid child size of right neighbor (%d != %d - %d)",
+ B_FREE_SPACE(p_s_bh), MAX_CHILD_SIZE(p_s_bh),
+ dc_size(B_N_CHILD(p_s_tb->FR[0], n_child_position)));
+
}
- decrement_bcount(p_s_tb->R[n_h]);
- p_s_tb->R[n_h] = p_s_bh;
-
- RFALSE( ! n_h && B_FREE_SPACE (p_s_bh) != MAX_CHILD_SIZE (p_s_bh) - dc_size(B_N_CHILD (p_s_tb->FR[0],n_child_position)),
- "PAP-8300: invalid child size of right neighbor (%d != %d - %d)",
- B_FREE_SPACE (p_s_bh), MAX_CHILD_SIZE (p_s_bh),
- dc_size(B_N_CHILD (p_s_tb->FR[0],n_child_position)));
-
- }
- return CARRY_ON;
+ return CARRY_ON;
}
#ifdef CONFIG_REISERFS_CHECK
-void * reiserfs_kmalloc (size_t size, int flags, struct super_block * s)
+void *reiserfs_kmalloc(size_t size, int flags, struct super_block *s)
{
- void * vp;
- static size_t malloced;
-
-
- vp = kmalloc (size, flags);
- if (vp) {
- REISERFS_SB(s)->s_kmallocs += size;
- if (REISERFS_SB(s)->s_kmallocs > malloced + 200000) {
- reiserfs_warning (s,
- "vs-8301: reiserfs_kmalloc: allocated memory %d",
- REISERFS_SB(s)->s_kmallocs);
- malloced = REISERFS_SB(s)->s_kmallocs;
+ void *vp;
+ static size_t malloced;
+
+ vp = kmalloc(size, flags);
+ if (vp) {
+ REISERFS_SB(s)->s_kmallocs += size;
+ if (REISERFS_SB(s)->s_kmallocs > malloced + 200000) {
+ reiserfs_warning(s,
+ "vs-8301: reiserfs_kmalloc: allocated memory %d",
+ REISERFS_SB(s)->s_kmallocs);
+ malloced = REISERFS_SB(s)->s_kmallocs;
+ }
}
- }
- return vp;
+ return vp;
}
-void reiserfs_kfree (const void * vp, size_t size, struct super_block * s)
+void reiserfs_kfree(const void *vp, size_t size, struct super_block *s)
{
- kfree (vp);
-
- REISERFS_SB(s)->s_kmallocs -= size;
- if (REISERFS_SB(s)->s_kmallocs < 0)
- reiserfs_warning (s, "vs-8302: reiserfs_kfree: allocated memory %d",
- REISERFS_SB(s)->s_kmallocs);
+ kfree(vp);
+
+ REISERFS_SB(s)->s_kmallocs -= size;
+ if (REISERFS_SB(s)->s_kmallocs < 0)
+ reiserfs_warning(s,
+ "vs-8302: reiserfs_kfree: allocated memory %d",
+ REISERFS_SB(s)->s_kmallocs);
}
#endif
-
-static int get_virtual_node_size (struct super_block * sb, struct buffer_head * bh)
+static int get_virtual_node_size(struct super_block *sb, struct buffer_head *bh)
{
- int max_num_of_items;
- int max_num_of_entries;
- unsigned long blocksize = sb->s_blocksize;
+ int max_num_of_items;
+ int max_num_of_entries;
+ unsigned long blocksize = sb->s_blocksize;
#define MIN_NAME_LEN 1
- max_num_of_items = (blocksize - BLKH_SIZE) / (IH_SIZE + MIN_ITEM_LEN);
- max_num_of_entries = (blocksize - BLKH_SIZE - IH_SIZE) /
- (DEH_SIZE + MIN_NAME_LEN);
+ max_num_of_items = (blocksize - BLKH_SIZE) / (IH_SIZE + MIN_ITEM_LEN);
+ max_num_of_entries = (blocksize - BLKH_SIZE - IH_SIZE) /
+ (DEH_SIZE + MIN_NAME_LEN);
- return sizeof(struct virtual_node) +
- max(max_num_of_items * sizeof (struct virtual_item),
- sizeof (struct virtual_item) + sizeof(struct direntry_uarea) +
- (max_num_of_entries - 1) * sizeof (__u16));
+ return sizeof(struct virtual_node) +
+ max(max_num_of_items * sizeof(struct virtual_item),
+ sizeof(struct virtual_item) + sizeof(struct direntry_uarea) +
+ (max_num_of_entries - 1) * sizeof(__u16));
}
-
-
/* maybe we should fail balancing we are going to perform when kmalloc
fails several times. But now it will loop until kmalloc gets
required memory */
-static int get_mem_for_virtual_node (struct tree_balance * tb)
+static int get_mem_for_virtual_node(struct tree_balance *tb)
{
- int check_fs = 0;
- int size;
- char * buf;
-
- size = get_virtual_node_size (tb->tb_sb, PATH_PLAST_BUFFER (tb->tb_path));
-
- if (size > tb->vn_buf_size) {
- /* we have to allocate more memory for virtual node */
- if (tb->vn_buf) {
- /* free memory allocated before */
- reiserfs_kfree (tb->vn_buf, tb->vn_buf_size, tb->tb_sb);
- /* this is not needed if kfree is atomic */
- check_fs = 1;
- }
+ int check_fs = 0;
+ int size;
+ char *buf;
+
+ size = get_virtual_node_size(tb->tb_sb, PATH_PLAST_BUFFER(tb->tb_path));
+
+ if (size > tb->vn_buf_size) {
+ /* we have to allocate more memory for virtual node */
+ if (tb->vn_buf) {
+ /* free memory allocated before */
+ reiserfs_kfree(tb->vn_buf, tb->vn_buf_size, tb->tb_sb);
+ /* this is not needed if kfree is atomic */
+ check_fs = 1;
+ }
- /* virtual node requires now more memory */
- tb->vn_buf_size = size;
-
- /* get memory for virtual item */
- buf = reiserfs_kmalloc(size, GFP_ATOMIC | __GFP_NOWARN, tb->tb_sb);
- if ( ! buf ) {
- /* getting memory with GFP_KERNEL priority may involve
- balancing now (due to indirect_to_direct conversion on
- dcache shrinking). So, release path and collected
- resources here */
- free_buffers_in_tb (tb);
- buf = reiserfs_kmalloc(size, GFP_NOFS, tb->tb_sb);
- if ( !buf ) {
+ /* virtual node requires now more memory */
+ tb->vn_buf_size = size;
+
+ /* get memory for virtual item */
+ buf =
+ reiserfs_kmalloc(size, GFP_ATOMIC | __GFP_NOWARN,
+ tb->tb_sb);
+ if (!buf) {
+ /* getting memory with GFP_KERNEL priority may involve
+ balancing now (due to indirect_to_direct conversion on
+ dcache shrinking). So, release path and collected
+ resources here */
+ free_buffers_in_tb(tb);
+ buf = reiserfs_kmalloc(size, GFP_NOFS, tb->tb_sb);
+ if (!buf) {
#ifdef CONFIG_REISERFS_CHECK
- reiserfs_warning (tb->tb_sb,
- "vs-8345: get_mem_for_virtual_node: "
- "kmalloc failed. reiserfs kmalloced %d bytes",
- REISERFS_SB(tb->tb_sb)->s_kmallocs);
+ reiserfs_warning(tb->tb_sb,
+ "vs-8345: get_mem_for_virtual_node: "
+ "kmalloc failed. reiserfs kmalloced %d bytes",
+ REISERFS_SB(tb->tb_sb)->
+ s_kmallocs);
#endif
- tb->vn_buf_size = 0;
- }
- tb->vn_buf = buf;
- schedule() ;
- return REPEAT_SEARCH;
- }
+ tb->vn_buf_size = 0;
+ }
+ tb->vn_buf = buf;
+ schedule();
+ return REPEAT_SEARCH;
+ }
- tb->vn_buf = buf;
- }
+ tb->vn_buf = buf;
+ }
- if ( check_fs && FILESYSTEM_CHANGED_TB (tb) )
- return REPEAT_SEARCH;
+ if (check_fs && FILESYSTEM_CHANGED_TB(tb))
+ return REPEAT_SEARCH;
- return CARRY_ON;
+ return CARRY_ON;
}
-
#ifdef CONFIG_REISERFS_CHECK
-static void tb_buffer_sanity_check (struct super_block * p_s_sb,
- struct buffer_head * p_s_bh,
- const char *descr, int level) {
- if (p_s_bh) {
- if (atomic_read (&(p_s_bh->b_count)) <= 0) {
-
- reiserfs_panic (p_s_sb, "jmacd-1: tb_buffer_sanity_check(): negative or zero reference counter for buffer %s[%d] (%b)\n", descr, level, p_s_bh);
- }
-
- if ( ! buffer_uptodate (p_s_bh) ) {
- reiserfs_panic (p_s_sb, "jmacd-2: tb_buffer_sanity_check(): buffer is not up to date %s[%d] (%b)\n", descr, level, p_s_bh);
- }
-
- if ( ! B_IS_IN_TREE (p_s_bh) ) {
- reiserfs_panic (p_s_sb, "jmacd-3: tb_buffer_sanity_check(): buffer is not in tree %s[%d] (%b)\n", descr, level, p_s_bh);
- }
-
- if (p_s_bh->b_bdev != p_s_sb->s_bdev) {
- reiserfs_panic (p_s_sb, "jmacd-4: tb_buffer_sanity_check(): buffer has wrong device %s[%d] (%b)\n", descr, level, p_s_bh);
- }
-
- if (p_s_bh->b_size != p_s_sb->s_blocksize) {
- reiserfs_panic (p_s_sb, "jmacd-5: tb_buffer_sanity_check(): buffer has wrong blocksize %s[%d] (%b)\n", descr, level, p_s_bh);
- }
-
- if (p_s_bh->b_blocknr > SB_BLOCK_COUNT(p_s_sb)) {
- reiserfs_panic (p_s_sb, "jmacd-6: tb_buffer_sanity_check(): buffer block number too high %s[%d] (%b)\n", descr, level, p_s_bh);
- }
- }
-}
-#else
-static void tb_buffer_sanity_check (struct super_block * p_s_sb,
- struct buffer_head * p_s_bh,
- const char *descr, int level)
-{;}
-#endif
-
-static int clear_all_dirty_bits(struct super_block *s,
- struct buffer_head *bh) {
- return reiserfs_prepare_for_journal(s, bh, 0) ;
-}
-
-static int wait_tb_buffers_until_unlocked (struct tree_balance * p_s_tb)
+static void tb_buffer_sanity_check(struct super_block *p_s_sb,
+ struct buffer_head *p_s_bh,
+ const char *descr, int level)
{
- struct buffer_head * locked;
-#ifdef CONFIG_REISERFS_CHECK
- int repeat_counter = 0;
-#endif
- int i;
+ if (p_s_bh) {
+ if (atomic_read(&(p_s_bh->b_count)) <= 0) {
- do {
-
- locked = NULL;
-
- for ( i = p_s_tb->tb_path->path_length; !locked && i > ILLEGAL_PATH_ELEMENT_OFFSET; i-- ) {
- if ( PATH_OFFSET_PBUFFER (p_s_tb->tb_path, i) ) {
- /* if I understand correctly, we can only be sure the last buffer
- ** in the path is in the tree --clm
- */
-#ifdef CONFIG_REISERFS_CHECK
- if (PATH_PLAST_BUFFER(p_s_tb->tb_path) ==
- PATH_OFFSET_PBUFFER(p_s_tb->tb_path, i)) {
- tb_buffer_sanity_check (p_s_tb->tb_sb,
- PATH_OFFSET_PBUFFER (p_s_tb->tb_path, i),
- "S",
- p_s_tb->tb_path->path_length - i);
+ reiserfs_panic(p_s_sb,
+ "jmacd-1: tb_buffer_sanity_check(): negative or zero reference counter for buffer %s[%d] (%b)\n",
+ descr, level, p_s_bh);
}
-#endif
- if (!clear_all_dirty_bits(p_s_tb->tb_sb,
- PATH_OFFSET_PBUFFER (p_s_tb->tb_path, i)))
- {
- locked = PATH_OFFSET_PBUFFER (p_s_tb->tb_path, i);
- }
- }
- }
- for ( i = 0; !locked && i < MAX_HEIGHT && p_s_tb->insert_size[i]; i++ ) {
+ if (!buffer_uptodate(p_s_bh)) {
+ reiserfs_panic(p_s_sb,
+ "jmacd-2: tb_buffer_sanity_check(): buffer is not up to date %s[%d] (%b)\n",
+ descr, level, p_s_bh);
+ }
- if (p_s_tb->lnum[i] ) {
+ if (!B_IS_IN_TREE(p_s_bh)) {
+ reiserfs_panic(p_s_sb,
+ "jmacd-3: tb_buffer_sanity_check(): buffer is not in tree %s[%d] (%b)\n",
+ descr, level, p_s_bh);
+ }
- if ( p_s_tb->L[i] ) {
- tb_buffer_sanity_check (p_s_tb->tb_sb, p_s_tb->L[i], "L", i);
- if (!clear_all_dirty_bits(p_s_tb->tb_sb, p_s_tb->L[i]))
- locked = p_s_tb->L[i];
+ if (p_s_bh->b_bdev != p_s_sb->s_bdev) {
+ reiserfs_panic(p_s_sb,
+ "jmacd-4: tb_buffer_sanity_check(): buffer has wrong device %s[%d] (%b)\n",
+ descr, level, p_s_bh);
}
- if ( !locked && p_s_tb->FL[i] ) {
- tb_buffer_sanity_check (p_s_tb->tb_sb, p_s_tb->FL[i], "FL", i);
- if (!clear_all_dirty_bits(p_s_tb->tb_sb, p_s_tb->FL[i]))
- locked = p_s_tb->FL[i];
+ if (p_s_bh->b_size != p_s_sb->s_blocksize) {
+ reiserfs_panic(p_s_sb,
+ "jmacd-5: tb_buffer_sanity_check(): buffer has wrong blocksize %s[%d] (%b)\n",
+ descr, level, p_s_bh);
}
- if ( !locked && p_s_tb->CFL[i] ) {
- tb_buffer_sanity_check (p_s_tb->tb_sb, p_s_tb->CFL[i], "CFL", i);
- if (!clear_all_dirty_bits(p_s_tb->tb_sb, p_s_tb->CFL[i]))
- locked = p_s_tb->CFL[i];
+ if (p_s_bh->b_blocknr > SB_BLOCK_COUNT(p_s_sb)) {
+ reiserfs_panic(p_s_sb,
+ "jmacd-6: tb_buffer_sanity_check(): buffer block number too high %s[%d] (%b)\n",
+ descr, level, p_s_bh);
}
+ }
+}
+#else
+static void tb_buffer_sanity_check(struct super_block *p_s_sb,
+ struct buffer_head *p_s_bh,
+ const char *descr, int level)
+{;
+}
+#endif
- }
+static int clear_all_dirty_bits(struct super_block *s, struct buffer_head *bh)
+{
+ return reiserfs_prepare_for_journal(s, bh, 0);
+}
- if ( !locked && (p_s_tb->rnum[i]) ) {
+static int wait_tb_buffers_until_unlocked(struct tree_balance *p_s_tb)
+{
+ struct buffer_head *locked;
+#ifdef CONFIG_REISERFS_CHECK
+ int repeat_counter = 0;
+#endif
+ int i;
- if ( p_s_tb->R[i] ) {
- tb_buffer_sanity_check (p_s_tb->tb_sb, p_s_tb->R[i], "R", i);
- if (!clear_all_dirty_bits(p_s_tb->tb_sb, p_s_tb->R[i]))
- locked = p_s_tb->R[i];
- }
+ do {
-
- if ( !locked && p_s_tb->FR[i] ) {
- tb_buffer_sanity_check (p_s_tb->tb_sb, p_s_tb->FR[i], "FR", i);
- if (!clear_all_dirty_bits(p_s_tb->tb_sb, p_s_tb->FR[i]))
- locked = p_s_tb->FR[i];
+ locked = NULL;
+
+ for (i = p_s_tb->tb_path->path_length;
+ !locked && i > ILLEGAL_PATH_ELEMENT_OFFSET; i--) {
+ if (PATH_OFFSET_PBUFFER(p_s_tb->tb_path, i)) {
+ /* if I understand correctly, we can only be sure the last buffer
+ ** in the path is in the tree --clm
+ */
+#ifdef CONFIG_REISERFS_CHECK
+ if (PATH_PLAST_BUFFER(p_s_tb->tb_path) ==
+ PATH_OFFSET_PBUFFER(p_s_tb->tb_path, i)) {
+ tb_buffer_sanity_check(p_s_tb->tb_sb,
+ PATH_OFFSET_PBUFFER
+ (p_s_tb->tb_path,
+ i), "S",
+ p_s_tb->tb_path->
+ path_length - i);
+ }
+#endif
+ if (!clear_all_dirty_bits(p_s_tb->tb_sb,
+ PATH_OFFSET_PBUFFER
+ (p_s_tb->tb_path,
+ i))) {
+ locked =
+ PATH_OFFSET_PBUFFER(p_s_tb->tb_path,
+ i);
+ }
+ }
}
- if ( !locked && p_s_tb->CFR[i] ) {
- tb_buffer_sanity_check (p_s_tb->tb_sb, p_s_tb->CFR[i], "CFR", i);
- if (!clear_all_dirty_bits(p_s_tb->tb_sb, p_s_tb->CFR[i]))
- locked = p_s_tb->CFR[i];
+ for (i = 0; !locked && i < MAX_HEIGHT && p_s_tb->insert_size[i];
+ i++) {
+
+ if (p_s_tb->lnum[i]) {
+
+ if (p_s_tb->L[i]) {
+ tb_buffer_sanity_check(p_s_tb->tb_sb,
+ p_s_tb->L[i],
+ "L", i);
+ if (!clear_all_dirty_bits
+ (p_s_tb->tb_sb, p_s_tb->L[i]))
+ locked = p_s_tb->L[i];
+ }
+
+ if (!locked && p_s_tb->FL[i]) {
+ tb_buffer_sanity_check(p_s_tb->tb_sb,
+ p_s_tb->FL[i],
+ "FL", i);
+ if (!clear_all_dirty_bits
+ (p_s_tb->tb_sb, p_s_tb->FL[i]))
+ locked = p_s_tb->FL[i];
+ }
+
+ if (!locked && p_s_tb->CFL[i]) {
+ tb_buffer_sanity_check(p_s_tb->tb_sb,
+ p_s_tb->CFL[i],
+ "CFL", i);
+ if (!clear_all_dirty_bits
+ (p_s_tb->tb_sb, p_s_tb->CFL[i]))
+ locked = p_s_tb->CFL[i];
+ }
+
+ }
+
+ if (!locked && (p_s_tb->rnum[i])) {
+
+ if (p_s_tb->R[i]) {
+ tb_buffer_sanity_check(p_s_tb->tb_sb,
+ p_s_tb->R[i],
+ "R", i);
+ if (!clear_all_dirty_bits
+ (p_s_tb->tb_sb, p_s_tb->R[i]))
+ locked = p_s_tb->R[i];
+ }
+
+ if (!locked && p_s_tb->FR[i]) {
+ tb_buffer_sanity_check(p_s_tb->tb_sb,
+ p_s_tb->FR[i],
+ "FR", i);
+ if (!clear_all_dirty_bits
+ (p_s_tb->tb_sb, p_s_tb->FR[i]))
+ locked = p_s_tb->FR[i];
+ }
+
+ if (!locked && p_s_tb->CFR[i]) {
+ tb_buffer_sanity_check(p_s_tb->tb_sb,
+ p_s_tb->CFR[i],
+ "CFR", i);
+ if (!clear_all_dirty_bits
+ (p_s_tb->tb_sb, p_s_tb->CFR[i]))
+ locked = p_s_tb->CFR[i];
+ }
+ }
+ }
+ /* as far as I can tell, this is not required. The FEB list seems
+ ** to be full of newly allocated nodes, which will never be locked,
+ ** dirty, or anything else.
+ ** To be safe, I'm putting in the checks and waits in. For the moment,
+ ** they are needed to keep the code in journal.c from complaining
+ ** about the buffer. That code is inside CONFIG_REISERFS_CHECK as well.
+ ** --clm
+ */
+ for (i = 0; !locked && i < MAX_FEB_SIZE; i++) {
+ if (p_s_tb->FEB[i]) {
+ if (!clear_all_dirty_bits
+ (p_s_tb->tb_sb, p_s_tb->FEB[i]))
+ locked = p_s_tb->FEB[i];
+ }
}
- }
- }
- /* as far as I can tell, this is not required. The FEB list seems
- ** to be full of newly allocated nodes, which will never be locked,
- ** dirty, or anything else.
- ** To be safe, I'm putting in the checks and waits in. For the moment,
- ** they are needed to keep the code in journal.c from complaining
- ** about the buffer. That code is inside CONFIG_REISERFS_CHECK as well.
- ** --clm
- */
- for ( i = 0; !locked && i < MAX_FEB_SIZE; i++ ) {
- if ( p_s_tb->FEB[i] ) {
- if (!clear_all_dirty_bits(p_s_tb->tb_sb, p_s_tb->FEB[i]))
- locked = p_s_tb->FEB[i] ;
- }
- }
- if (locked) {
+ if (locked) {
#ifdef CONFIG_REISERFS_CHECK
- repeat_counter++;
- if ( (repeat_counter % 10000) == 0) {
- reiserfs_warning (p_s_tb->tb_sb,
- "wait_tb_buffers_until_released(): too many "
- "iterations waiting for buffer to unlock "
- "(%b)", locked);
-
- /* Don't loop forever. Try to recover from possible error. */
-
- return ( FILESYSTEM_CHANGED_TB (p_s_tb) ) ? REPEAT_SEARCH : CARRY_ON;
- }
+ repeat_counter++;
+ if ((repeat_counter % 10000) == 0) {
+ reiserfs_warning(p_s_tb->tb_sb,
+ "wait_tb_buffers_until_released(): too many "
+ "iterations waiting for buffer to unlock "
+ "(%b)", locked);
+
+ /* Don't loop forever. Try to recover from possible error. */
+
+ return (FILESYSTEM_CHANGED_TB(p_s_tb)) ?
+ REPEAT_SEARCH : CARRY_ON;
+ }
#endif
- __wait_on_buffer (locked);
- if ( FILESYSTEM_CHANGED_TB (p_s_tb) ) {
- return REPEAT_SEARCH;
- }
- }
+ __wait_on_buffer(locked);
+ if (FILESYSTEM_CHANGED_TB(p_s_tb)) {
+ return REPEAT_SEARCH;
+ }
+ }
- } while (locked);
+ } while (locked);
- return CARRY_ON;
+ return CARRY_ON;
}
-
/* Prepare for balancing, that is
* get all necessary parents, and neighbors;
* analyze what and where should be moved;
@@ -2267,252 +2360,266 @@ static int wait_tb_buffers_until_unlocked (struct tree_balance * p_s_tb)
* -1 - if no_disk_space
*/
+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
+ const void *data // inserted item or data to be pasted
+ )
+{
+ int n_ret_value, n_h, n_item_num = PATH_LAST_POSITION(p_s_tb->tb_path);
+ int n_pos_in_item;
-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
- const void * data // inserted item or data to be pasted
- ) {
- int n_ret_value,
- n_h,
- n_item_num = PATH_LAST_POSITION(p_s_tb->tb_path);
- int n_pos_in_item;
-
- /* we set wait_tb_buffers_run when we have to restore any dirty bits cleared
- ** during wait_tb_buffers_run
- */
- int wait_tb_buffers_run = 0 ;
- struct buffer_head * p_s_tbS0 = PATH_PLAST_BUFFER(p_s_tb->tb_path);
-
- ++ REISERFS_SB(p_s_tb -> tb_sb) -> s_fix_nodes;
-
- n_pos_in_item = p_s_tb->tb_path->pos_in_item;
-
-
- p_s_tb->fs_gen = get_generation (p_s_tb->tb_sb);
-
- /* we prepare and log the super here so it will already be in the
- ** transaction when do_balance needs to change it.
- ** This way do_balance won't have to schedule when trying to prepare
- ** the super for logging
- */
- reiserfs_prepare_for_journal(p_s_tb->tb_sb,
- SB_BUFFER_WITH_SB(p_s_tb->tb_sb), 1) ;
- journal_mark_dirty(p_s_tb->transaction_handle, p_s_tb->tb_sb,
- SB_BUFFER_WITH_SB(p_s_tb->tb_sb)) ;
- if ( FILESYSTEM_CHANGED_TB (p_s_tb) )
- return REPEAT_SEARCH;
-
- /* if it possible in indirect_to_direct conversion */
- if (buffer_locked (p_s_tbS0)) {
- __wait_on_buffer (p_s_tbS0);
- if ( FILESYSTEM_CHANGED_TB (p_s_tb) )
- return REPEAT_SEARCH;
- }
+ /* we set wait_tb_buffers_run when we have to restore any dirty bits cleared
+ ** during wait_tb_buffers_run
+ */
+ int wait_tb_buffers_run = 0;
+ struct buffer_head *p_s_tbS0 = PATH_PLAST_BUFFER(p_s_tb->tb_path);
-#ifdef CONFIG_REISERFS_CHECK
- if ( cur_tb ) {
- print_cur_tb ("fix_nodes");
- reiserfs_panic(p_s_tb->tb_sb,"PAP-8305: fix_nodes: there is pending do_balance");
- }
-
- if (!buffer_uptodate (p_s_tbS0) || !B_IS_IN_TREE (p_s_tbS0)) {
- reiserfs_panic (p_s_tb->tb_sb, "PAP-8320: fix_nodes: S[0] (%b %z) is not uptodate "
- "at the beginning of fix_nodes or not in tree (mode %c)", p_s_tbS0, p_s_tbS0, n_op_mode);
- }
-
- /* Check parameters. */
- switch (n_op_mode) {
- case M_INSERT:
- if ( n_item_num <= 0 || n_item_num > B_NR_ITEMS(p_s_tbS0) )
- reiserfs_panic(p_s_tb->tb_sb,"PAP-8330: fix_nodes: Incorrect item number %d (in S0 - %d) in case of insert",
- n_item_num, B_NR_ITEMS(p_s_tbS0));
- break;
- case M_PASTE:
- case M_DELETE:
- case M_CUT:
- if ( n_item_num < 0 || n_item_num >= B_NR_ITEMS(p_s_tbS0) ) {
- print_block (p_s_tbS0, 0, -1, -1);
- reiserfs_panic(p_s_tb->tb_sb,"PAP-8335: fix_nodes: Incorrect item number(%d); mode = %c insert_size = %d\n", n_item_num, n_op_mode, p_s_tb->insert_size[0]);
- }
- break;
- default:
- reiserfs_panic(p_s_tb->tb_sb,"PAP-8340: fix_nodes: Incorrect mode of operation");
- }
-#endif
+ ++REISERFS_SB(p_s_tb->tb_sb)->s_fix_nodes;
+
+ n_pos_in_item = p_s_tb->tb_path->pos_in_item;
+
+ p_s_tb->fs_gen = get_generation(p_s_tb->tb_sb);
- if (get_mem_for_virtual_node (p_s_tb) == REPEAT_SEARCH)
- // FIXME: maybe -ENOMEM when tb->vn_buf == 0? Now just repeat
- return REPEAT_SEARCH;
+ /* we prepare and log the super here so it will already be in the
+ ** transaction when do_balance needs to change it.
+ ** This way do_balance won't have to schedule when trying to prepare
+ ** the super for logging
+ */
+ reiserfs_prepare_for_journal(p_s_tb->tb_sb,
+ SB_BUFFER_WITH_SB(p_s_tb->tb_sb), 1);
+ journal_mark_dirty(p_s_tb->transaction_handle, p_s_tb->tb_sb,
+ SB_BUFFER_WITH_SB(p_s_tb->tb_sb));
+ if (FILESYSTEM_CHANGED_TB(p_s_tb))
+ return REPEAT_SEARCH;
+ /* if it possible in indirect_to_direct conversion */
+ if (buffer_locked(p_s_tbS0)) {
+ __wait_on_buffer(p_s_tbS0);
+ if (FILESYSTEM_CHANGED_TB(p_s_tb))
+ return REPEAT_SEARCH;
+ }
+#ifdef CONFIG_REISERFS_CHECK
+ if (cur_tb) {
+ print_cur_tb("fix_nodes");
+ reiserfs_panic(p_s_tb->tb_sb,
+ "PAP-8305: fix_nodes: there is pending do_balance");
+ }
- /* Starting from the leaf level; for all levels n_h of the tree. */
- for ( n_h = 0; n_h < MAX_HEIGHT && p_s_tb->insert_size[n_h]; n_h++ ) {
- if ( (n_ret_value = get_direct_parent(p_s_tb, n_h)) != CARRY_ON ) {
- goto repeat;
+ if (!buffer_uptodate(p_s_tbS0) || !B_IS_IN_TREE(p_s_tbS0)) {
+ reiserfs_panic(p_s_tb->tb_sb,
+ "PAP-8320: fix_nodes: S[0] (%b %z) is not uptodate "
+ "at the beginning of fix_nodes or not in tree (mode %c)",
+ p_s_tbS0, p_s_tbS0, n_op_mode);
}
- if ( (n_ret_value = check_balance (n_op_mode, p_s_tb, n_h, n_item_num,
- n_pos_in_item, p_s_ins_ih, data)) != CARRY_ON ) {
- if ( n_ret_value == NO_BALANCING_NEEDED ) {
- /* No balancing for higher levels needed. */
- if ( (n_ret_value = get_neighbors(p_s_tb, n_h)) != CARRY_ON ) {
- goto repeat;
+ /* Check parameters. */
+ switch (n_op_mode) {
+ case M_INSERT:
+ if (n_item_num <= 0 || n_item_num > B_NR_ITEMS(p_s_tbS0))
+ reiserfs_panic(p_s_tb->tb_sb,
+ "PAP-8330: fix_nodes: Incorrect item number %d (in S0 - %d) in case of insert",
+ n_item_num, B_NR_ITEMS(p_s_tbS0));
+ break;
+ case M_PASTE:
+ case M_DELETE:
+ case M_CUT:
+ if (n_item_num < 0 || n_item_num >= B_NR_ITEMS(p_s_tbS0)) {
+ print_block(p_s_tbS0, 0, -1, -1);
+ reiserfs_panic(p_s_tb->tb_sb,
+ "PAP-8335: fix_nodes: Incorrect item number(%d); mode = %c insert_size = %d\n",
+ n_item_num, n_op_mode,
+ p_s_tb->insert_size[0]);
}
- if ( n_h != MAX_HEIGHT - 1 )
- p_s_tb->insert_size[n_h + 1] = 0;
- /* ok, analysis and resource gathering are complete */
break;
- }
- goto repeat;
+ default:
+ reiserfs_panic(p_s_tb->tb_sb,
+ "PAP-8340: fix_nodes: Incorrect mode of operation");
}
+#endif
- if ( (n_ret_value = get_neighbors(p_s_tb, n_h)) != CARRY_ON ) {
- goto repeat;
- }
+ if (get_mem_for_virtual_node(p_s_tb) == REPEAT_SEARCH)
+ // FIXME: maybe -ENOMEM when tb->vn_buf == 0? Now just repeat
+ return REPEAT_SEARCH;
- if ( (n_ret_value = get_empty_nodes(p_s_tb, n_h)) != CARRY_ON ) {
- goto repeat; /* No disk space, or schedule occurred and
- analysis may be invalid and needs to be redone. */
- }
-
- if ( ! PATH_H_PBUFFER(p_s_tb->tb_path, n_h) ) {
- /* We have a positive insert size but no nodes exist on this
- level, this means that we are creating a new root. */
+ /* Starting from the leaf level; for all levels n_h of the tree. */
+ for (n_h = 0; n_h < MAX_HEIGHT && p_s_tb->insert_size[n_h]; n_h++) {
+ if ((n_ret_value = get_direct_parent(p_s_tb, n_h)) != CARRY_ON) {
+ goto repeat;
+ }
- RFALSE( p_s_tb->blknum[n_h] != 1,
- "PAP-8350: creating new empty root");
+ if ((n_ret_value =
+ check_balance(n_op_mode, p_s_tb, n_h, n_item_num,
+ n_pos_in_item, p_s_ins_ih,
+ data)) != CARRY_ON) {
+ if (n_ret_value == NO_BALANCING_NEEDED) {
+ /* No balancing for higher levels needed. */
+ if ((n_ret_value =
+ get_neighbors(p_s_tb, n_h)) != CARRY_ON) {
+ goto repeat;
+ }
+ if (n_h != MAX_HEIGHT - 1)
+ p_s_tb->insert_size[n_h + 1] = 0;
+ /* ok, analysis and resource gathering are complete */
+ break;
+ }
+ goto repeat;
+ }
- if ( n_h < MAX_HEIGHT - 1 )
- p_s_tb->insert_size[n_h + 1] = 0;
- }
- else
- if ( ! PATH_H_PBUFFER(p_s_tb->tb_path, n_h + 1) ) {
- if ( p_s_tb->blknum[n_h] > 1 ) {
- /* The tree needs to be grown, so this node S[n_h]
- which is the root node is split into two nodes,
- and a new node (S[n_h+1]) will be created to
- become the root node. */
-
- RFALSE( n_h == MAX_HEIGHT - 1,
- "PAP-8355: attempt to create too high of a tree");
-
- p_s_tb->insert_size[n_h + 1] = (DC_SIZE + KEY_SIZE) * (p_s_tb->blknum[n_h] - 1) + DC_SIZE;
+ if ((n_ret_value = get_neighbors(p_s_tb, n_h)) != CARRY_ON) {
+ goto repeat;
}
- else
- if ( n_h < MAX_HEIGHT - 1 )
- p_s_tb->insert_size[n_h + 1] = 0;
- }
- else
- p_s_tb->insert_size[n_h + 1] = (DC_SIZE + KEY_SIZE) * (p_s_tb->blknum[n_h] - 1);
- }
-
- if ((n_ret_value = wait_tb_buffers_until_unlocked (p_s_tb)) == CARRY_ON) {
- if (FILESYSTEM_CHANGED_TB(p_s_tb)) {
- wait_tb_buffers_run = 1 ;
- n_ret_value = REPEAT_SEARCH ;
- goto repeat;
- } else {
- return CARRY_ON;
+
+ if ((n_ret_value = get_empty_nodes(p_s_tb, n_h)) != CARRY_ON) {
+ goto repeat; /* No disk space, or schedule occurred and
+ analysis may be invalid and needs to be redone. */
+ }
+
+ if (!PATH_H_PBUFFER(p_s_tb->tb_path, n_h)) {
+ /* We have a positive insert size but no nodes exist on this
+ level, this means that we are creating a new root. */
+
+ RFALSE(p_s_tb->blknum[n_h] != 1,
+ "PAP-8350: creating new empty root");
+
+ if (n_h < MAX_HEIGHT - 1)
+ p_s_tb->insert_size[n_h + 1] = 0;
+ } else if (!PATH_H_PBUFFER(p_s_tb->tb_path, n_h + 1)) {
+ if (p_s_tb->blknum[n_h] > 1) {
+ /* The tree needs to be grown, so this node S[n_h]
+ which is the root node is split into two nodes,
+ and a new node (S[n_h+1]) will be created to
+ become the root node. */
+
+ RFALSE(n_h == MAX_HEIGHT - 1,
+ "PAP-8355: attempt to create too high of a tree");
+
+ p_s_tb->insert_size[n_h + 1] =
+ (DC_SIZE +
+ KEY_SIZE) * (p_s_tb->blknum[n_h] - 1) +
+ DC_SIZE;
+ } else if (n_h < MAX_HEIGHT - 1)
+ p_s_tb->insert_size[n_h + 1] = 0;
+ } else
+ p_s_tb->insert_size[n_h + 1] =
+ (DC_SIZE + KEY_SIZE) * (p_s_tb->blknum[n_h] - 1);
}
- } else {
- wait_tb_buffers_run = 1 ;
- goto repeat;
- }
-
- repeat:
- // fix_nodes was unable to perform its calculation due to
- // filesystem got changed under us, lack of free disk space or i/o
- // failure. If the first is the case - the search will be
- // repeated. For now - free all resources acquired so far except
- // for the new allocated nodes
- {
- int i;
- /* Release path buffers. */
- if (wait_tb_buffers_run) {
- pathrelse_and_restore(p_s_tb->tb_sb, p_s_tb->tb_path) ;
+ if ((n_ret_value = wait_tb_buffers_until_unlocked(p_s_tb)) == CARRY_ON) {
+ if (FILESYSTEM_CHANGED_TB(p_s_tb)) {
+ wait_tb_buffers_run = 1;
+ n_ret_value = REPEAT_SEARCH;
+ goto repeat;
+ } else {
+ return CARRY_ON;
+ }
} else {
- pathrelse (p_s_tb->tb_path);
- }
- /* brelse all resources collected for balancing */
- for ( i = 0; i < MAX_HEIGHT; i++ ) {
- if (wait_tb_buffers_run) {
- reiserfs_restore_prepared_buffer(p_s_tb->tb_sb, p_s_tb->L[i]);
- reiserfs_restore_prepared_buffer(p_s_tb->tb_sb, p_s_tb->R[i]);
- reiserfs_restore_prepared_buffer(p_s_tb->tb_sb, p_s_tb->FL[i]);
- reiserfs_restore_prepared_buffer(p_s_tb->tb_sb, p_s_tb->FR[i]);
- reiserfs_restore_prepared_buffer(p_s_tb->tb_sb, p_s_tb->CFL[i]);
- reiserfs_restore_prepared_buffer(p_s_tb->tb_sb, p_s_tb->CFR[i]);
- }
-
- brelse (p_s_tb->L[i]);p_s_tb->L[i] = NULL;
- brelse (p_s_tb->R[i]);p_s_tb->R[i] = NULL;
- brelse (p_s_tb->FL[i]);p_s_tb->FL[i] = NULL;
- brelse (p_s_tb->FR[i]);p_s_tb->FR[i] = NULL;
- brelse (p_s_tb->CFL[i]);p_s_tb->CFL[i] = NULL;
- brelse (p_s_tb->CFR[i]);p_s_tb->CFR[i] = NULL;
+ wait_tb_buffers_run = 1;
+ goto repeat;
}
- if (wait_tb_buffers_run) {
- for ( i = 0; i < MAX_FEB_SIZE; i++ ) {
- if ( p_s_tb->FEB[i] ) {
- reiserfs_restore_prepared_buffer(p_s_tb->tb_sb,
- p_s_tb->FEB[i]) ;
+ repeat:
+ // fix_nodes was unable to perform its calculation due to
+ // filesystem got changed under us, lack of free disk space or i/o
+ // failure. If the first is the case - the search will be
+ // repeated. For now - free all resources acquired so far except
+ // for the new allocated nodes
+ {
+ int i;
+
+ /* Release path buffers. */
+ if (wait_tb_buffers_run) {
+ pathrelse_and_restore(p_s_tb->tb_sb, p_s_tb->tb_path);
+ } else {
+ pathrelse(p_s_tb->tb_path);
+ }
+ /* brelse all resources collected for balancing */
+ for (i = 0; i < MAX_HEIGHT; i++) {
+ if (wait_tb_buffers_run) {
+ reiserfs_restore_prepared_buffer(p_s_tb->tb_sb,
+ p_s_tb->L[i]);
+ reiserfs_restore_prepared_buffer(p_s_tb->tb_sb,
+ p_s_tb->R[i]);
+ reiserfs_restore_prepared_buffer(p_s_tb->tb_sb,
+ p_s_tb->FL[i]);
+ reiserfs_restore_prepared_buffer(p_s_tb->tb_sb,
+ p_s_tb->FR[i]);
+ reiserfs_restore_prepared_buffer(p_s_tb->tb_sb,
+ p_s_tb->
+ CFL[i]);
+ reiserfs_restore_prepared_buffer(p_s_tb->tb_sb,
+ p_s_tb->
+ CFR[i]);
+ }
+
+ brelse(p_s_tb->L[i]);
+ p_s_tb->L[i] = NULL;
+ brelse(p_s_tb->R[i]);
+ p_s_tb->R[i] = NULL;
+ brelse(p_s_tb->FL[i]);
+ p_s_tb->FL[i] = NULL;
+ brelse(p_s_tb->FR[i]);
+ p_s_tb->FR[i] = NULL;
+ brelse(p_s_tb->CFL[i]);
+ p_s_tb->CFL[i] = NULL;
+ brelse(p_s_tb->CFR[i]);
+ p_s_tb->CFR[i] = NULL;
+ }
+
+ if (wait_tb_buffers_run) {
+ for (i = 0; i < MAX_FEB_SIZE; i++) {
+ if (p_s_tb->FEB[i]) {
+ reiserfs_restore_prepared_buffer
+ (p_s_tb->tb_sb, p_s_tb->FEB[i]);
+ }
+ }
}
- }
+ return n_ret_value;
}
- return n_ret_value;
- }
}
-
/* Anatoly will probably forgive me renaming p_s_tb to tb. I just
wanted to make lines shorter */
-void unfix_nodes (struct tree_balance * tb)
+void unfix_nodes(struct tree_balance *tb)
{
- int i;
-
- /* Release path buffers. */
- pathrelse_and_restore (tb->tb_sb, tb->tb_path);
-
- /* brelse all resources collected for balancing */
- for ( i = 0; i < MAX_HEIGHT; i++ ) {
- reiserfs_restore_prepared_buffer (tb->tb_sb, tb->L[i]);
- reiserfs_restore_prepared_buffer (tb->tb_sb, tb->R[i]);
- reiserfs_restore_prepared_buffer (tb->tb_sb, tb->FL[i]);
- reiserfs_restore_prepared_buffer (tb->tb_sb, tb->FR[i]);
- reiserfs_restore_prepared_buffer (tb->tb_sb, tb->CFL[i]);
- reiserfs_restore_prepared_buffer (tb->tb_sb, tb->CFR[i]);
-
- brelse (tb->L[i]);
- brelse (tb->R[i]);
- brelse (tb->FL[i]);
- brelse (tb->FR[i]);
- brelse (tb->CFL[i]);
- brelse (tb->CFR[i]);
- }
-
- /* deal with list of allocated (used and unused) nodes */
- for ( i = 0; i < MAX_FEB_SIZE; i++ ) {
- if ( tb->FEB[i] ) {
- b_blocknr_t blocknr = tb->FEB[i]->b_blocknr ;
- /* de-allocated block which was not used by balancing and
- bforget about buffer for it */
- brelse (tb->FEB[i]);
- reiserfs_free_block (tb->transaction_handle, NULL, blocknr, 0);
- }
- if (tb->used[i]) {
- /* release used as new nodes including a new root */
- brelse (tb->used[i]);
- }
- }
+ int i;
- if (tb->vn_buf)
- reiserfs_kfree (tb->vn_buf, tb->vn_buf_size, tb->tb_sb);
+ /* Release path buffers. */
+ pathrelse_and_restore(tb->tb_sb, tb->tb_path);
-}
+ /* brelse all resources collected for balancing */
+ for (i = 0; i < MAX_HEIGHT; i++) {
+ reiserfs_restore_prepared_buffer(tb->tb_sb, tb->L[i]);
+ reiserfs_restore_prepared_buffer(tb->tb_sb, tb->R[i]);
+ reiserfs_restore_prepared_buffer(tb->tb_sb, tb->FL[i]);
+ reiserfs_restore_prepared_buffer(tb->tb_sb, tb->FR[i]);
+ reiserfs_restore_prepared_buffer(tb->tb_sb, tb->CFL[i]);
+ reiserfs_restore_prepared_buffer(tb->tb_sb, tb->CFR[i]);
+
+ brelse(tb->L[i]);
+ brelse(tb->R[i]);
+ brelse(tb->FL[i]);
+ brelse(tb->FR[i]);
+ brelse(tb->CFL[i]);
+ brelse(tb->CFR[i]);
+ }
+ /* deal with list of allocated (used and unused) nodes */
+ for (i = 0; i < MAX_FEB_SIZE; i++) {
+ if (tb->FEB[i]) {
+ b_blocknr_t blocknr = tb->FEB[i]->b_blocknr;
+ /* de-allocated block which was not used by balancing and
+ bforget about buffer for it */
+ brelse(tb->FEB[i]);
+ reiserfs_free_block(tb->transaction_handle, NULL,
+ blocknr, 0);
+ }
+ if (tb->used[i]) {
+ /* release used as new nodes including a new root */
+ brelse(tb->used[i]);
+ }
+ }
+ if (tb->vn_buf)
+ reiserfs_kfree(tb->vn_buf, tb->vn_buf_size, tb->tb_sb);
+}