diff options
Diffstat (limited to 'fs/reiserfs/fix_node.c')
| -rw-r--r-- | fs/reiserfs/fix_node.c | 4051 |
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); |