/* * Copyright 2000 by Hans Reiser, licensing governed by reiserfs/README */ /** ** old_item_num ** old_entry_num ** set_entry_sizes ** create_virtual_node ** check_left ** check_right ** directory_part_size ** get_num_ver ** set_parameters ** is_leaf_removable ** are_leaves_removable ** get_empty_nodes ** get_lfree ** get_rfree ** is_left_neighbor_in_cache ** decrement_key ** get_far_parent ** get_parents ** can_node_be_removed ** ip_check_balance ** dc_check_balance_internal ** dc_check_balance_leaf ** dc_check_balance ** check_balance ** get_direct_parent ** get_neighbors ** fix_nodes ** ** **/ #include <linux/time.h>#include <linux/slab.h>#include <linux/string.h>#include "reiserfs.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 will shift to left/right neighbor, or to a new node, where new item will be etc. To make this analysis simpler we build virtual node. Virtual node is an array of items, that will replace items of node S. (For instance if we are going to delete an item, virtual node does not contain it). Virtual node keeps information about item sizes and types, mergeability of first and last items, sizes of all entries in directory item. We use this array of items when calculating what we can shift to neighbors and how many nodes we 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){ if (mode == M_PASTE || mode == M_CUT || new_num < affected_item_num) return new_num; if (mode == M_INSERT) { RFALSE(new_num == 0, "vs-8005: for INSERT mode and item number of inserted item"); 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){ 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); /* 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", "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 == NULL, "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", "rdkey %k, affected item==%d " "(mode==%c) Must be %c", key, vn->vn_affected_item_num, vn->vn_mode, M_DELETE); } }#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){ 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); /* internal level */ if (h > 0) { tb->lnum[h] = cur_free / (DC_SIZE + KEY_SIZE); return; } /* leaf level */ 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"); 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"); 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; } /* 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; } 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){ 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; } /* 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){ 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; } 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",Lines 1–500 of 2595. Load more
/* * Copyright 2000 by Hans Reiser, licensing governed by reiserfs/README */ /** ** old_item_num ** old_entry_num ** set_entry_sizes ** create_virtual_node ** check_left ** check_right ** directory_part_size ** get_num_ver ** set_parameters ** is_leaf_removable ** are_leaves_removable ** get_empty_nodes ** get_lfree ** get_rfree ** is_left_neighbor_in_cache ** decrement_key ** get_far_parent ** get_parents ** can_node_be_removed ** ip_check_balance ** dc_check_balance_internal ** dc_check_balance_leaf ** dc_check_balance ** check_balance ** get_direct_parent ** get_neighbors ** fix_nodes ** ** **/ #include <linux/time.h> #include <linux/slab.h> #include <linux/string.h> #include "reiserfs.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 will shift to left/right neighbor, or to a new node, where new item will be etc. To make this analysis simpler we build virtual node. Virtual node is an array of items, that will replace items of node S. (For instance if we are going to delete an item, virtual node does not contain it). Virtual node keeps information about item sizes and types, mergeability of first and last items, sizes of all entries in directory item. We use this array of items when calculating what we can shift to neighbors and how many nodes we 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) { if (mode == M_PASTE || mode == M_CUT || new_num < affected_item_num) return new_num; if (mode == M_INSERT) { RFALSE(new_num == 0, "vs-8005: for INSERT mode and item number of inserted item"); 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) { 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); /* 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", "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 == NULL, "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", "rdkey %k, affected item==%d " "(mode==%c) Must be %c", key, vn->vn_affected_item_num, vn->vn_mode, M_DELETE); } } #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) { 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); /* internal level */ if (h > 0) { tb->lnum[h] = cur_free / (DC_SIZE + KEY_SIZE); return; } /* leaf level */ 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"); 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"); 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; } /* 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; } 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) { 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; } /* 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) { 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; } 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",