| /* |
| * Copyright 1996-2004 by Hans Reiser, licensing governed by |
| * reiserfsprogs/README |
| */ |
| |
| /** |
| ** old_item_num |
| ** old_entry_num |
| ** set_entry_sizes |
| ** create_virtual_node |
| ** check_left |
| ** check_right |
| ** directory_part_size |
| ** get_num_ver |
| ** item_length |
| ** 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 "includes.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) |
| return new_num - 1; |
| |
| /* delete mode */ |
| return new_num + 1; |
| } |
| |
| |
| /* function returns old entry number in directory item in real node using new |
| entry number in virtual item in virtual node */ |
| static inline int old_entry_num (int new_num, int affected_item_num, int new_entry_num, int pos_in_item, int mode) |
| { |
| if ( mode == M_INSERT || mode == M_DELETE) |
| return new_entry_num; |
| |
| if (new_num != affected_item_num) { |
| /* cut or paste is applied to another item */ |
| return new_entry_num; |
| } |
| |
| if (new_entry_num < pos_in_item) |
| return new_entry_num; |
| |
| if (mode == M_CUT) |
| return new_entry_num + 1; |
| |
| return new_entry_num - 1; |
| } |
| |
| |
| |
| /* |
| * Create an array of sizes of directory entries for virtual item |
| */ |
| static void set_entry_sizes (struct tree_balance * tb, |
| int old_num, int new_num, |
| struct buffer_head * bh, |
| struct item_head * ih) |
| { |
| struct virtual_node * vn = tb->tb_vn; |
| int i; |
| struct reiserfs_de_head * deh; |
| struct virtual_item * vi; |
| |
| deh = B_I_DEH (bh, ih); |
| |
| /* seek to given virtual item in array of virtual items */ |
| vi = vn->vn_vi + new_num; |
| |
| /* virtual directory item have this amount of entry after */ |
| vi->vi_entry_count = get_ih_entry_count (ih) + |
| ((old_num == vn->vn_affected_item_num) ? ((vn->vn_mode == M_CUT) ? -1 : |
| (vn->vn_mode == M_PASTE ? 1 : 0)) : 0); |
| vi->vi_entry_sizes = (__u16 *)vn->vn_free_ptr; |
| vn->vn_free_ptr += vi->vi_entry_count * sizeof (__u16); |
| |
| /* set sizes of old entries */ |
| for (i = 0; i < vi->vi_entry_count; i ++) { |
| int j; |
| |
| j = old_entry_num (old_num, vn->vn_affected_item_num, i, vn->vn_pos_in_item, vn->vn_mode); |
| vi->vi_entry_sizes[i] = entry_length (ih, &(deh[j]), j) + DEH_SIZE; |
| } |
| |
| /* set size of pasted entry */ |
| if (old_num == vn->vn_affected_item_num && vn->vn_mode == M_PASTE) |
| vi->vi_entry_sizes[vn->vn_pos_in_item] = tb->insert_size[0]; |
| } |
| |
| |
| 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_size) - get_blkh_free_space (B_BLK_HEAD (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 (is_left_mergeable (tb->tb_fs, tb->tb_path) == 1 && (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; |
| |
| if (vn->vn_affected_item_num == new_num && 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); |
| |
| vn->vn_vi[new_num].vi_item_len += get_ih_item_len (&ih[j]) + IH_SIZE; |
| |
| if (I_IS_STAT_DATA_ITEM (ih + j)) { |
| vn->vn_vi[new_num].vi_type |= VI_TYPE_STAT_DATA; |
| continue; |
| } |
| |
| /* set type of item */ |
| if (I_IS_DIRECT_ITEM (ih + j)) |
| vn->vn_vi[new_num].vi_type |= VI_TYPE_DIRECT; |
| |
| if (I_IS_INDIRECT_ITEM (ih + j)) |
| vn->vn_vi[new_num].vi_type |= VI_TYPE_INDIRECT; |
| |
| if (I_IS_DIRECTORY_ITEM (ih + j)) { |
| set_entry_sizes (tb, j, new_num, Sh, ih + j); |
| vn->vn_vi[new_num].vi_type |= VI_TYPE_DIRECTORY; |
| if (get_key_offset_v1 (&ih[j].ih_key) == DOT_OFFSET) |
| vn->vn_vi[new_num].vi_type |= VI_TYPE_FIRST_DIRECTORY_ITEM; |
| } |
| |
| vn->vn_vi[new_num].vi_item_offset = get_offset (&(ih + j)->ih_key); |
| |
| if (new_num != vn->vn_affected_item_num) |
| /* 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]; |
| } |
| |
| |
| /* virtual inserted item is not defined yet */ |
| if (vn->vn_mode == M_INSERT) { |
| vn->vn_vi[vn->vn_affected_item_num].vi_item_len = tb->insert_size[0]; |
| vn->vn_vi[vn->vn_affected_item_num].vi_item_offset = get_offset (&vn->vn_ins_ih->ih_key); |
| |
| switch (get_type (&vn->vn_ins_ih->ih_key)) { |
| case TYPE_STAT_DATA: |
| vn->vn_vi[vn->vn_affected_item_num].vi_type |= VI_TYPE_STAT_DATA; |
| break; |
| case TYPE_DIRECT: |
| vn->vn_vi[vn->vn_affected_item_num].vi_type |= VI_TYPE_DIRECT; |
| break; |
| case TYPE_INDIRECT: |
| vn->vn_vi[vn->vn_affected_item_num].vi_type |= VI_TYPE_INDIRECT; |
| break; |
| default: |
| /* inseted item is directory (it must be item with "." and "..") */ |
| vn->vn_vi[vn->vn_affected_item_num].vi_type |= |
| (VI_TYPE_DIRECTORY | VI_TYPE_FIRST_DIRECTORY_ITEM | VI_TYPE_INSERTED_DIRECTORY_ITEM); |
| |
| /* this directory item can not be split, so do not set sizes of entries */ |
| break; |
| } |
| } |
| |
| /* set right merge flag we take right delimiting key and check whether it is a mergeable item */ |
| if (tb->CFR[0]) { |
| ih = (struct item_head *)B_N_PDELIM_KEY (tb->CFR[0], tb->rkey[0]); |
| if (is_right_mergeable (tb->tb_fs, tb->tb_path) == 1 && |
| (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; |
| } |
| } |
| |
| |
| /* using virtual node check, how many items can be shifted to left |
| neighbor */ |
| static int check_left (struct tree_balance * tb, int h, int cur_free) |
| { |
| int i; |
| struct virtual_node * vn = tb->tb_vn; |
| int d_size, ih_size, bytes = -1; |
| |
| /* internal level */ |
| if (h > 0) { |
| if (!cur_free ) { |
| tb->lnum[h] = 0; |
| return 0; |
| } |
| tb->lnum[h] = cur_free / (DC_SIZE + KEY_SIZE); |
| return -1; |
| } |
| |
| /* leaf level */ |
| |
| if (!cur_free || !vn->vn_nr_item) { |
| /* no free space */ |
| tb->lnum[h] = 0; |
| tb->lbytes = -1; |
| return 0; |
| } |
| |
| if ((unsigned int)cur_free >= (vn->vn_size - ((vn->vn_vi[0].vi_type & VI_TYPE_LEFT_MERGEABLE) ? IH_SIZE : 0))) { |
| /* all contents of S[0] fits into L[0] */ |
| tb->lnum[0] = vn->vn_nr_item; |
| tb->lbytes = -1; |
| return -1; |
| } |
| |
| d_size = 0, ih_size = IH_SIZE; |
| |
| /* first item may be merge with last item in left neighbor */ |
| if (vn->vn_vi[0].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) { |
| d_size += vn->vn_vi[i].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 -1; |
| } |
| cur_free -= ih_size; |
| |
| if (vn->vn_vi[i].vi_type & VI_TYPE_STAT_DATA || |
| vn->vn_vi[i].vi_type & VI_TYPE_INSERTED_DIRECTORY_ITEM) { |
| /* virtual item is a stat_data or empty directory body ("." and ".."), that is not split able */ |
| tb->lbytes = -1; |
| return -1; |
| } |
| |
| if (vn->vn_vi[i].vi_type & VI_TYPE_DIRECT) { |
| /* body of a direct item can be split by 8 bytes */ |
| int align = 8 - (vn->vn_vi[i].vi_item_offset - 1) % 8; |
| // reiserfs_warning(stderr,"\nbalancing: cur_free (%d) ", cur_free); |
| tb->lbytes = bytes = (cur_free >= align) ? (align + ((cur_free - align) / 8 * 8)) : 0; |
| // reiserfs_warning(stderr,"offset (0x%Lx), move_left (%d), get offset (0x%Lx)", |
| // vn->vn_vi[i].vi_item_offset, bytes, vn->vn_vi[i].vi_item_offset + bytes); |
| } |
| |
| if (vn->vn_vi[i].vi_type & VI_TYPE_INDIRECT) |
| /* body of a indirect item can be split at unformatted pointer bound */ |
| tb->lbytes = bytes = cur_free - cur_free % UNFM_P_SIZE; |
| |
| /* item is of directory type */ |
| if (vn->vn_vi[i].vi_type & VI_TYPE_DIRECTORY) { |
| /* directory entries are the solid granules of the directory |
| item, they cannot be split in the middle */ |
| |
| /* calculate number of dir entries that can be shifted, and |
| their total size */ |
| int j; |
| struct virtual_item * vi; |
| |
| tb->lbytes = 0; |
| bytes = 0; |
| vi = &vn->vn_vi[i]; |
| |
| for (j = 0; j < vi->vi_entry_count; j ++) { |
| if (vi->vi_entry_sizes[j] > cur_free) |
| /* j-th entry doesn't fit into L[0] */ |
| break; |
| |
| bytes += vi->vi_entry_sizes[j]; |
| cur_free -= vi->vi_entry_sizes[j]; |
| tb->lbytes ++; |
| } |
| /* "." can not be cut from first directory item */ |
| if ((vn->vn_vi[i].vi_type & VI_TYPE_FIRST_DIRECTORY_ITEM) && tb->lbytes < 2) |
| tb->lbytes = 0; |
| } |
| |
| |
| if (tb->lbytes <= 0) { |
| /* nothing can flow from the item */ |
| tb->lbytes = -1; |
| return -1; |
| } |
| |
| /* something can flow from the item */ |
| tb->lnum[0] ++; |
| return bytes; /* part of split item in bytes */ |
| } |
| |
| |
| reiserfs_panic (0, "vs-8065: check_left: all items fit in the left neighbor"); |
| return 0; |
| } |
| |
| |
| |
| /* using virtual node check, how many items can be shifted to right |
| neighbor */ |
| static int check_right (struct tree_balance * tb, int h, int cur_free) |
| { |
| int i; |
| struct virtual_node * vn = tb->tb_vn; |
| int d_size, ih_size, bytes = -1; |
| |
| /* internal level */ |
| if (h > 0) { |
| if (!cur_free) { |
| tb->rnum[h] = 0; |
| return 0; |
| } |
| tb->rnum[h] = cur_free / (DC_SIZE + KEY_SIZE); |
| return -1; |
| } |
| |
| /* leaf level */ |
| |
| if (!cur_free || !vn->vn_nr_item) { |
| /* no free space */ |
| tb->rnum[h] = 0; |
| tb->rbytes = -1; |
| return 0; |
| } |
| |
| if ((unsigned int)cur_free >= (vn->vn_size - ((vn->vn_vi[vn->vn_nr_item-1].vi_type & VI_TYPE_RIGHT_MERGEABLE) ? IH_SIZE : 0))) |
| { |
| /* all contents of S[0] fits into R[0] */ |
| tb->rnum[h] = vn->vn_nr_item; |
| tb->rbytes = -1; |
| return -1; |
| } |
| |
| d_size = 0, ih_size = IH_SIZE; |
| |
| /* last item may be merge with first item in right neighbor */ |
| if (vn->vn_vi[vn->vn_nr_item - 1].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) { |
| d_size += vn->vn_vi[i].vi_item_len; |
| if (cur_free >= d_size) { |
| /* the item can be shifted entirely */ |
| cur_free -= d_size; |
| tb->rnum[0] ++; |
| continue; |
| } |
| |
| /* the item cannot be shifted entirely, try to split it */ |
| if (vn->vn_vi[i].vi_type & VI_TYPE_STAT_DATA || vn->vn_vi[i].vi_type & VI_TYPE_INSERTED_DIRECTORY_ITEM) { |
| /* virtual item is a stat_data or empty directory body ("." and |
| "..), that is not split able */ |
| tb->rbytes = -1; |
| return -1; |
| } |
| |
| /* 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 -1; |
| } |
| |
| /* 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 */ |
| |
| /* item is of direct type */ |
| if (vn->vn_vi[i].vi_type & VI_TYPE_DIRECT) { |
| /* body of a direct item can be split by 8 bytes */ |
| int align = vn->vn_vi[i].vi_item_len % 8; |
| // reiserfs_warning(stderr,"\nbalancing: cur_free (%d) ", cur_free); |
| tb->rbytes = bytes = (cur_free >= align) ? (align + ((cur_free - align) / 8 * 8)) : 0; |
| // reiserfs_warning(stderr, "offset (0x%Lx) len (%d), move right (%d), get offset (0x%Lx)", |
| // vn->vn_vi[i].vi_item_offset, vn->vn_vi[i].vi_item_len, bytes, |
| // vn->vn_vi[i].vi_item_offset + vn->vn_vi[i].vi_item_len - bytes); |
| } |
| |
| /* item is of indirect type */ |
| if (vn->vn_vi[i].vi_type & VI_TYPE_INDIRECT) |
| /* an unformatted node pointer (having size long) is a solid |
| granule of the item */ |
| tb->rbytes = bytes = cur_free - cur_free % UNFM_P_SIZE; |
| |
| /* item is of directory type */ |
| if (vn->vn_vi[i].vi_type & VI_TYPE_DIRECTORY) { |
| int j; |
| struct virtual_item * vi; |
| |
| tb->rbytes = 0; |
| bytes = 0; |
| vi = &vn->vn_vi[i]; |
| |
| for (j = vi->vi_entry_count - 1; j >= 0; j --) { |
| if (vi->vi_entry_sizes[j] > cur_free) |
| /* j-th entry doesn't fit into L[0] */ |
| break; |
| |
| bytes += vi->vi_entry_sizes[j]; |
| cur_free -= vi->vi_entry_sizes[j]; |
| tb->rbytes ++; |
| } |
| |
| /* ".." can not be cut from first directory item */ |
| if ((vn->vn_vi[i].vi_type & VI_TYPE_FIRST_DIRECTORY_ITEM) && tb->rbytes > vi->vi_entry_count - 2) |
| tb->rbytes = vi->vi_entry_count - 2; |
| } |
| |
| if ( tb->rbytes <= 0 ) { |
| /* nothing can flow from the item */ |
| tb->rbytes = -1; |
| return -1; |
| } |
| |
| |
| /* something can flow from the item */ |
| tb->rnum[0] ++; |
| return bytes; /* part of split item in bytes */ |
| } |
| |
| reiserfs_panic ("vs-8095: check_right: all items fit in the left neighbor"); |
| return 0; |
| } |
| |
| |
| /* sum of entry sizes between from-th and to-th entries including both edges */ |
| static int directory_part_size (struct virtual_item * vi, int from, int to) |
| { |
| int i, retval; |
| |
| retval = 0; |
| for (i = from; i <= to; i ++) |
| retval += vi->vi_entry_sizes[i]; |
| |
| return retval; |
| } |
| |
| |
| /* |
| * 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 bytes; |
| 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 splitted_item_positions[2]; /* these are positions in virtual item of items, |
| that are splitted between S[0] and S1new and S1new and S2new */ |
| |
| max_node_size = MAX_CHILD_SIZE (tb->tb_fs->fs_blocksize); |
| |
| /* 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; |
| |
| start_item = from; |
| start_bytes = from_bytes; |
| end_item = vn->vn_nr_item - to - 1; |
| end_bytes = to_bytes; |
| |
| /* go through all items begining from the start_item-th item and ending by |
| the end_item-th item. If start_bytes != -1 we skip first start_bytes |
| item units (entries in case of directory). If end_bytes != -1 we skip |
| end_bytes units of the end_item-th item. */ |
| for (i = start_item; i <= end_item; i ++) { |
| /* get size of current item */ |
| current_item_size = (vi = &vn->vn_vi[i])->vi_item_len; |
| |
| /* do not take in calculation head part (from_bytes) of from-th item */ |
| if (i == start_item && start_bytes != -1) { |
| if (vi->vi_type & VI_TYPE_DIRECTORY) |
| current_item_size -= directory_part_size (vi, 0, start_bytes - 1); |
| else |
| current_item_size -= start_bytes; |
| } |
| |
| /* do not take in calculation tail part of (to-1)-th item */ |
| if (i == end_item && end_bytes != -1) { |
| if (vi->vi_type & VI_TYPE_DIRECTORY) |
| /* first entry, that is not included */ |
| current_item_size -= directory_part_size (vi, vi->vi_entry_count - end_bytes, vi->vi_entry_count - 1); |
| else |
| current_item_size -= end_bytes; |
| } |
| |
| /* if item fits into current node entirely */ |
| if (total_node_size + current_item_size <= max_node_size) { |
| snum012[needed_nodes - 1] ++; |
| total_node_size += current_item_size; |
| 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 */ |
| /* 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; |
| } |
| |
| if (total_node_size + (int)IH_SIZE >= max_node_size) { |
| /* even minimal item does not fit into current node, take new node |
| and continue */ |
| needed_nodes ++, i--, total_node_size = 0; |
| continue; |
| } |
| if (vi->vi_type & VI_TYPE_STAT_DATA) { |
| /* stat data can not be split */ |
| needed_nodes ++, i--, total_node_size = 0; |
| continue; |
| } |
| |
| /*bytes is free space in filled node*/ |
| bytes = max_node_size - total_node_size - IH_SIZE; |
| |
| if (vi->vi_type & VI_TYPE_DIRECT) { |
| /* body of a direct item can be split by 8 bytes. */ |
| int align = 8 - (vn->vn_vi[i].vi_item_offset - 1) % 8; |
| // reiserfs_warning(stderr,"\nbalancing: cur_free (%d) ", bytes); |
| // reiserfs_warning(stderr,"offset (0x%Lx), move (%d), get offset (0x%Lx)", |
| // vn->vn_vi[i].vi_item_offset, (bytes - align) / 8 * 8, |
| // vn->vn_vi[i].vi_item_offset + ((bytes - align) / 8 * 8)); |
| bytes = (bytes >= align) ? (align + ((bytes - align) / 8 * 8)) : 0; |
| } |
| |
| |
| /* item is of indirect type */ |
| if (vi->vi_type & VI_TYPE_INDIRECT) |
| /* an unformatted node pointer (having size long) is a solid |
| granule of the item. bytes of unformatted node pointers fits |
| into free space of filled node */ |
| bytes -= (bytes) % UNFM_P_SIZE; |
| |
| /* S1bytes or S2bytes. It depends from needed_nodes */ |
| snum012[needed_nodes - 1 + 3] = bytes; |
| |
| /* item is of directory type */ |
| if (vi->vi_type & VI_TYPE_DIRECTORY) { |
| /* calculate, how many entries can be put into current node */ |
| int j; |
| int end_entry; |
| |
| snum012[needed_nodes - 1 + 3] = 0; |
| |
| total_node_size += IH_SIZE; |
| if (start_bytes == -1 || i != start_item) |
| start_bytes = 0; |
| |
| end_entry = vi->vi_entry_count - ((i == end_item && end_bytes != -1) ? end_bytes : 0); |
| for (j = start_bytes; j < end_entry; j ++) { |
| /* j-th entry doesn't fit into current node */ |
| if (total_node_size + vi->vi_entry_sizes[j] > max_node_size) |
| break; |
| snum012[needed_nodes - 1 + 3] ++; |
| bytes += vi->vi_entry_sizes[j]; |
| total_node_size += vi->vi_entry_sizes[j]; |
| } |
| /* "." can not be cut from first directory item */ |
| if (start_bytes == 0 && (vn->vn_vi[i].vi_type & VI_TYPE_FIRST_DIRECTORY_ITEM) && |
| snum012[needed_nodes - 1 + 3] < 2) |
| snum012[needed_nodes - 1 + 3] = 0; |
| } |
| |
| if (snum012[needed_nodes-1+3] <= 0 ) { |
| /* 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 (vi->vi_type & VI_TYPE_DIRECTORY) |
| start_bytes += snum012[needed_nodes - 1 + 3]; |
| else |
| start_bytes = bytes; |
| |
| snum012[needed_nodes - 1] ++; |
| splitted_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; |
| } |
| |
| |
| /* snum012[3] and snum012[4] contain how many bytes (entries) of split |
| item can be in S[0] and S1new. s1bytes and s2bytes are how many bytes |
| (entries) can be in S1new and S2new. Recalculate it */ |
| |
| if (snum012[4] > 0) { /* s2bytes */ |
| /* get number of item that is split between S1new and S2new */ |
| int split_item_num; |
| int bytes_to_r, bytes_to_l; |
| |
| split_item_num = splitted_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); |
| if (vn->vn_vi[split_item_num].vi_type & VI_TYPE_DIRECTORY) { |
| int entries_to_S2new; |
| |
| /* calculate number of entries fit into S2new */ |
| entries_to_S2new = vn->vn_vi[split_item_num].vi_entry_count - snum012[4] - bytes_to_r - bytes_to_l; |
| if (snum012[3] != -1 && snum012[1] == 1) { |
| /* directory split into 3 nodes */ |
| int entries_to_S1new; |
| |
| entries_to_S2new -= snum012[3]; |
| entries_to_S1new = snum012[4]; |
| snum012[3] = entries_to_S1new; |
| snum012[4] = entries_to_S2new; |
| return needed_nodes; |
| } |
| snum012[4] = entries_to_S2new; |
| } else { |
| /* item is not of directory type */ |
| int bytes_to_S2new; |
| |
| bytes_to_S2new = vn->vn_vi[split_item_num].vi_item_len - IH_SIZE - snum012[4] - bytes_to_r - bytes_to_l; |
| snum012[4] = bytes_to_S2new; |
| } |
| } |
| |
| /* now we know S2bytes, calculate S1bytes */ |
| if (snum012[3] > 0) { /* s1bytes */ |
| /* get number of item that is split between S0 and S1new */ |
| int split_item_num; |
| int bytes_to_r, bytes_to_l; |
| |
| split_item_num = splitted_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); |
| if (vn->vn_vi[split_item_num].vi_type & VI_TYPE_DIRECTORY) { |
| /* entries, who go to S1new node */ |
| snum012[3] = vn->vn_vi[split_item_num].vi_entry_count - snum012[3] - bytes_to_r - bytes_to_l; |
| } else |
| /* bytes, who go to S1new node (not including HI_SIZE) */ |
| snum012[3] = vn->vn_vi[split_item_num].vi_item_len - IH_SIZE - snum012[3] - bytes_to_r - bytes_to_l; |
| } |
| |
| return needed_nodes; |
| } |
| |
| /* size of item_num-th item in bytes when regular and in entries when item is |
| directory */ |
| static int item_length (struct tree_balance * tb, int item_num) |
| { |
| struct virtual_node * vn = tb->tb_vn; |
| |
| if (vn->vn_vi[item_num].vi_type & VI_TYPE_DIRECTORY) |
| return vn->vn_vi[item_num].vi_entry_count; |
| |
| return vn->vn_vi[item_num].vi_item_len - IH_SIZE; |
| } |
| |
| |
| /* 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. |
| * Parameters: |
| * tb tree_balance structure; |
| * h current level of the node; |
| * lnum number of items from S[h] that must be shifted to L[h]; |
| * rnum number of items from S[h] that must be shifted to R[h]; |
| * blk_num number of blocks that S[h] will be splitted into; |
| * s012 number of items that fall into splitted nodes. |
| * lbytes number of bytes which flow to the left neighbor from the item that is not |
| * not shifted entirely |
| * rbytes number of bytes which flow to the right neighbor from the item that is not |
| * not shifted entirely |
| * 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) |
| { |
| |
| 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; |
| } |
| tb->lbytes = lb; |
| tb->rbytes = rb; |
| } |
| } |
| |
| static void decrement_key (struct key * p_s_key) |
| { |
| int type; |
| |
| type = get_type (p_s_key); |
| switch (type) { |
| case TYPE_STAT_DATA: |
| set_key_objectid (p_s_key, get_key_objectid (p_s_key) - 1); |
| set_type_and_offset (key_format (p_s_key), p_s_key, |
| (loff_t)MAX_FILE_SIZE_V2, TYPE_INDIRECT); |
| return; |
| |
| case TYPE_INDIRECT: |
| case TYPE_DIRECT: |
| case TYPE_DIRENTRY: |
| set_offset (key_format (p_s_key), p_s_key, get_offset (p_s_key) - 1); |
| if (get_offset (p_s_key) == 0) |
| set_type (key_format (p_s_key), p_s_key, TYPE_STAT_DATA); |
| return; |
| } |
| reiserfs_warning (stderr, "vs-8125: decrement_key: item of wrong type found %k", |
| p_s_key); |
| } |
| |
| |
| int are_items_mergeable (struct item_head * left, struct item_head * right, int bsize) |
| { |
| if (comp_keys (&left->ih_key, &right->ih_key) != -1) { |
| reiserfs_panic ("vs-16070: are_items_mergeable: left %k, right %k", &(left->ih_key), &(right->ih_key)); |
| } |
| |
| if (not_of_one_file (&left->ih_key, &right->ih_key)) |
| return 0; |
| |
| if (I_IS_DIRECTORY_ITEM (left)) { |
| return 1; |
| } |
| |
| if ((I_IS_DIRECT_ITEM (left) && I_IS_DIRECT_ITEM (right)) || |
| (I_IS_INDIRECT_ITEM (left) && I_IS_INDIRECT_ITEM (right))) |
| return (get_offset (&left->ih_key) + get_bytes_number (left, bsize) == get_offset (&right->ih_key)) ? 1 : 0; |
| |
| return 0; |
| } |
| |
| /* get left neighbor of the leaf node */ |
| static struct buffer_head * get_left_neighbor (reiserfs_filsys_t * s, struct path * path) |
| { |
| struct key key; |
| struct path path_to_left_neighbor; |
| struct buffer_head * bh; |
| |
| copy_key (&key, B_N_PKEY (PATH_PLAST_BUFFER (path), 0)); |
| decrement_key (&key); |
| |
| init_path (&path_to_left_neighbor); |
| search_by_key (s, &key, &path_to_left_neighbor, DISK_LEAF_NODE_LEVEL); |
| if (PATH_LAST_POSITION (&path_to_left_neighbor) == 0) { |
| pathrelse (&path_to_left_neighbor); |
| return 0; |
| } |
| bh = PATH_PLAST_BUFFER (&path_to_left_neighbor); |
| bh->b_count ++; |
| pathrelse (&path_to_left_neighbor); |
| return bh; |
| } |
| |
| |
| extern struct key MIN_KEY; |
| static struct buffer_head * get_right_neighbor (reiserfs_filsys_t * s, struct path * path) |
| { |
| struct key key; |
| struct key * rkey; |
| struct path path_to_right_neighbor; |
| struct buffer_head * bh; |
| |
| rkey = get_rkey (path, s); |
| if (comp_keys (rkey, &MIN_KEY) == 0) |
| reiserfs_panic ("vs-16080: get_right_neighbor: get_rkey returned min key (path has changed)"); |
| copy_key (&key, rkey); |
| |
| |
| init_path (&path_to_right_neighbor); |
| search_by_key (s, &key, &path_to_right_neighbor, DISK_LEAF_NODE_LEVEL); |
| if (PATH_PLAST_BUFFER (&path_to_right_neighbor) == PATH_PLAST_BUFFER (path)) { |
| pathrelse (&path_to_right_neighbor); |
| return 0; |
| } |
| bh = PATH_PLAST_BUFFER (&path_to_right_neighbor); |
| bh->b_count ++; |
| pathrelse (&path_to_right_neighbor); |
| return bh; |
| } |
| |
| |
| int is_left_mergeable (reiserfs_filsys_t * s, struct path * path) |
| { |
| struct item_head * right; |
| struct buffer_head * bh; |
| int retval; |
| |
| right = B_N_PITEM_HEAD (PATH_PLAST_BUFFER (path), 0); |
| |
| bh = get_left_neighbor (s, path); |
| if (bh == 0) { |
| return 0; |
| } |
| retval = are_items_mergeable (B_N_PITEM_HEAD (bh, B_NR_ITEMS (bh) - 1), right, bh->b_size); |
| brelse (bh); |
| return retval; |
| } |
| |
| |
| int is_right_mergeable (reiserfs_filsys_t * s, struct path * path) |
| { |
| struct item_head * left; |
| struct buffer_head * bh; |
| int retval; |
| |
| left = B_N_PITEM_HEAD (PATH_PLAST_BUFFER (path), B_NR_ITEMS (PATH_PLAST_BUFFER (path)) - 1); |
| |
| bh = get_right_neighbor (s, path); |
| if (bh == 0) { |
| return 0; |
| } |
| retval = are_items_mergeable (left, B_N_PITEM_HEAD (bh, 0), bh->b_size); |
| brelse (bh); |
| return retval; |
| } |
| |
| |
| |
| /* 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) |
| { |
| 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 directory entry count if directory) */ |
| size = item_length (tb, 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) |
| { |
| 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; |
| |
| ih = B_N_PITEM_HEAD (S0, 0); |
| if (tb->CFR[0] && !not_of_one_file (&(ih->ih_key), B_N_PDELIM_KEY (tb->CFR[0], tb->rkey[0]))) |
| if (I_IS_DIRECTORY_ITEM(ih)) { |
| /* we can delete any directory item in fsck (if it is unreachable) */ |
| if (get_offset (&ih->ih_key) != DOT_OFFSET) { |
| /* must get left neighbor here to make sure, that |
| left neighbor is of the same directory */ |
| struct buffer_head * left; |
| |
| left = get_left_neighbor (tb->tb_fs, tb->tb_path); |
| if (left) { |
| struct item_head * last; |
| |
| if (B_NR_ITEMS (left) == 0) |
| reiserfs_panic ("vs-8135: are_leaves_removable: " |
| "empty node in the tree"); |
| last = B_N_PITEM_HEAD (left, B_NR_ITEMS (left) - 1); |
| if (!comp_short_keys (&last->ih_key, &ih->ih_key)) |
| ih_size = IH_SIZE; |
| brelse (left); |
| } |
| } |
| } |
| |
| } |
| |
| if ((int)MAX_CHILD_SIZE(S0->b_size) + vn->vn_size <= rfree + lfree + ih_size) { |
| set_parameters (tb, 0, -1, -1, -1, NULL, -1, -1); |
| return 1; |
| } |
| return 0; |
| |
| } |
| |
| |
| |
| /* when we do not split item, lnum and rnum are numbers of entire items */ |
| #define SET_PAR_SHIFT_LEFT \ |
| if (h)\ |
| {\ |
| int to_l;\ |
| \ |
| to_l = (MAX_NR_KEY(Sh)+1 - lpar + vn->vn_nr_item + 1) / 2 -\ |
| (MAX_NR_KEY(Sh) + 1 - lpar);\ |
| \ |
| set_parameters (tb, h, to_l, 0, lnver, NULL, -1, -1);\ |
| }\ |
| else \ |
| {\ |
| if (lset==LEFT_SHIFT_FLOW)\ |
| set_parameters (tb, h, lpar, 0, lnver, snum012+lset,\ |
| tb->lbytes, -1);\ |
| else\ |
| set_parameters (tb, h, lpar - (tb->lbytes!=-1), 0, lnver, snum012+lset,\ |
| -1, -1);\ |
| } |
| |
| |
| #define SET_PAR_SHIFT_RIGHT \ |
| if (h)\ |
| {\ |
| int to_r;\ |
| \ |
| to_r = (MAX_NR_KEY(Sh)+1 - rpar + vn->vn_nr_item + 1) / 2 - (MAX_NR_KEY(Sh) + 1 - rpar);\ |
| \ |
| set_parameters (tb, h, 0, to_r, rnver, NULL, -1, -1);\ |
| }\ |
| else \ |
| {\ |
| if (rset==RIGHT_SHIFT_FLOW)\ |
| set_parameters (tb, h, 0, rpar, rnver, snum012+rset,\ |
| -1, tb->rbytes);\ |
| else\ |
| set_parameters (tb, h, 0, rpar - (tb->rbytes!=-1), rnver, snum012+rset,\ |
| -1, -1);\ |
| } |
| |
| |
| |
| /* Get new buffers for storing new nodes that are created while balancing. |
| * Returns: SCHEDULE_OCCURED - schedule occured while the function worked; |
| * CARRY_ON - schedule didn't occur while the function worked; |
| * NO_DISK_SPACE - no disk space. |
| */ |
| 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); |
| unsigned long * 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_repeat; |
| reiserfs_filsys_t * fs = p_s_tb->tb_fs; |
| |
| |
| if (n_h == 0 && p_s_tb->insert_size[n_h] == 0x7fff) |
| return CARRY_ON; |
| |
| /* 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; |
| |
| if ( (n_repeat = reiserfs_new_blocknrs (p_s_tb->tb_fs, a_n_blocknrs, |
| PATH_PLAST_BUFFER(p_s_tb->tb_path)->b_blocknr, n_amount_needed)) != CARRY_ON ) { |
| return n_repeat; /* Out of 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++ ) { |
| p_s_new_bh = getblk (fs->fs_dev, *p_n_blocknr, fs->fs_blocksize); |
| if (p_s_new_bh->b_count > 1) { |
| die ("get_empty_nodes: not free empty buffer"); |
| } |
| |
| /* Put empty buffers into the array. */ |
| p_s_tb->FEB[p_s_tb->cur_blknum++] = p_s_new_bh; |
| } |
| |
| return CARRY_ON; |
| } |
| |
| |
| /* 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) |
| { |
| 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 == l) |
| order = PATH_H_B_ITEM_ORDER (tb->tb_path, h) - 1; |
| else { |
| order = get_blkh_nr_items (B_BLK_HEAD(l)); |
| f = l; |
| } |
| |
| if (get_dc_child_size (B_N_CHILD(f,order)) == 0) { |
| reiserfs_warning (stderr, "get_lfree: block %u block_head %z has bad child pointer %y, order %d\n", |
| l->b_blocknr, l, B_N_CHILD(f,order), order); |
| } |
| return (MAX_CHILD_SIZE(f->b_size) - get_dc_child_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) |
| { |
| 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 == r) |
| order = PATH_H_B_ITEM_ORDER (tb->tb_path, h) + 1; |
| else { |
| order = 0; |
| f = r; |
| } |
| |
| return (MAX_CHILD_SIZE(f->b_size) - get_dc_child_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; |
| reiserfs_filsys_t * fs = p_s_tb->tb_fs; |
| unsigned long 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); |
| /* 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] : get_blkh_nr_items (B_BLK_HEAD(p_s_tb->FL[n_h])); |
| /* Get left neighbor block number. */ |
| n_left_neighbor_blocknr = get_dc_child_blocknr (B_N_CHILD (p_s_tb->FL[n_h], n_left_neighbor_position)); |
| /* Look for the left neighbor in the cache. */ |
| if ( (p_s_father = find_buffer(fs->fs_dev, n_left_neighbor_blocknr, fs->fs_blocksize)) ) |
| return 1; |
| |
| return 0; |
| } |
| |
| |
| #define LEFT_PARENTS 'l' |
| #define RIGHT_PARENTS 'r' |
| |
| |
| |
| void init_path (struct path * path) |
| { |
| path->path_length = ILLEGAL_PATH_ELEMENT_OFFSET; |
| } |
| |
| |
| /* 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]. |
| * Calculate left/right delimiting key position. |
| * Returns: PATH_INCORRECT - path in the tree is not correct; |
| SCHEDULE_OCCURRED - schedule occured 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) |
| { |
| struct buffer_head * p_s_parent; |
| struct path s_path_to_neighbor_father, |
| * p_s_path = p_s_tb->tb_path; |
| struct key s_lr_father_key; |
| int n_counter, |
| n_position = -1, |
| 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; |
| |
| 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)) ) |
| reiserfs_panic ("get_far_parent: buffer of path is notin the tree"); |
| |
| /* 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) ) |
| reiserfs_panic ("get_far_parent: incorrect position in the parent"); |
| |
| /* Check whether parent at the path really points to the child. */ |
| if ( get_dc_child_blocknr (B_N_CHILD (p_s_parent, n_position)) != |
| PATH_OFFSET_PBUFFER(p_s_path, n_counter)->b_blocknr ) |
| reiserfs_panic ("get_far_parent: incorrect disk child in the parent"); |
| |
| /* 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 = get_blkh_nr_items (B_BLK_HEAD(p_s_parent)); |
| if ( n_position != n_first_last_position ) { |
| (*pp_s_com_father = p_s_parent)->b_count++; |
| break; |
| } |
| } |
| |
| /* we are in the root of the tree. */ |
| if ( n_counter == FIRST_PATH_ELEMENT_OFFSET ) { |
| struct reiserfs_super_block * sb; |
| |
| sb = p_s_tb->tb_fs->fs_ondisk_sb; |
| |
| /* 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 == |
| get_sb_root_block (sb) ) { |
| *pp_s_father = *pp_s_com_father = NULL; |
| return CARRY_ON; |
| } |
| reiserfs_panic ("get_far_parent: root not found in the path"); |
| } |
| |
| if (n_position == -1) |
| reiserfs_panic ("get_far_parent: position is not defined"); |
| |
| /* 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. */ |
| copy_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 ) { |
| //reiserfs_warning ("decrememnting key %k\n", &s_lr_father_key); |
| decrement_key(&s_lr_father_key); |
| //reiserfs_warning ("done: %k\n", &s_lr_father_key); |
| } |
| |
| init_path (&s_path_to_neighbor_father); |
| |
| if (search_by_key(p_s_tb->tb_fs, &s_lr_father_key, &s_path_to_neighbor_father, n_h + 1) == IO_ERROR) |
| return IO_ERROR; |
| |
| *pp_s_father = PATH_PLAST_BUFFER(&s_path_to_neighbor_father); |
| s_path_to_neighbor_father.path_length--; |
| pathrelse (&s_path_to_neighbor_father); |
| //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]. |
| * Calculate numbers of left and right delimiting keys position: lkey[n_path_offset], rkey[n_path_offset]. |
| * Returns: SCHEDULE_OCCURRED - schedule occured 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) |
| { |
| 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. */ |
| brelse(p_s_tb->FL[n_h]); |
| brelse(p_s_tb->CFL[n_h]); |
| brelse(p_s_tb->FR[n_h]); |
| brelse(p_s_tb->CFR[n_h]); |
| //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_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; /*schedule() occured or path is not correct*/ |
| } |
| |
| brelse(p_s_tb->FL[n_h]); |
| p_s_tb->FL[n_h] = p_s_curf; /* New initialization of FL[n_h]. */ |
| |
| brelse(p_s_tb->CFL[n_h]); |
| p_s_tb->CFL[n_h] = p_s_curcf; /* New initialization of CFL[n_h]. */ |
| |
| /* 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 == get_blkh_nr_items (B_BLK_HEAD(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; /*schedule() occured while get_far_parent() worked.*/ |
| } |
| 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_tb->rkey[n_h] = n_position; |
| } |
| |
| brelse/*decrement_bcount*/(p_s_tb->FR[n_h]); |
| p_s_tb->FR[n_h] = p_s_curf; /* New initialization of FR[n_path_offset]. */ |
| |
| brelse/*decrement_bcount*/(p_s_tb->CFR[n_h]); |
| p_s_tb->CFR[n_h] = p_s_curcf; /* New initialization of CFR[n_path_offset]. */ |
| |
| return CARRY_ON; /* schedule not occured while get_parents() worked. */ |
| } |
| |
| |
| /* 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) |
| { |
| struct buffer_head * Sh = PATH_H_PBUFFER (tb->tb_path, h); |
| int levbytes = tb->insert_size[h]; |
| struct item_head * r_ih = NULL; |
| |
| if ( tb->CFR[h] ) |
| r_ih = (struct item_head *)B_N_PDELIM_KEY(tb->CFR[h],tb->rkey[h]); |
| |
| if (lfree + rfree + sfree < (int)(MAX_CHILD_SIZE(Sh->b_size) + levbytes |
| /* shifting may merge items which might save space */ |
| - (( ! h && is_left_mergeable (tb->tb_fs, tb->tb_path) == 1 ) ? IH_SIZE : 0) |
| - (( ! h && r_ih && is_right_mergeable (tb->tb_fs, tb->tb_path) == 1 ) ? 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; |
| } |
| } |
| 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. |
| * Parameters: |
| * tb tree_balance structure; |
| * h current level of the node; |
| * inum item number in S[h]; |
| * mode i - insert, p - paste; |
| * Returns: 1 - schedule occured; |
| * 0 - balancing for higher levels needed; |
| * -1 - no balancing for higher levels needed; |
| * -2 - no disk space. |
| */ |
| /* ip means Inserting or Pasting */ |
| static int ip_check_balance (/*struct reiserfs_transaction_handle *th,*/ 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 vertices, 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 vertices, and second, the number of |
| vertices whose contents are changed by shifting, and third the number |
| of uncached vertices 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; |
| |
| /* special mode for insert pointer to the most low internal node */ |
| if (h == 0 && vn->vn_mode == M_INTERNAL) { |
| /* blk_num == 2 is to get pointer inserted to the next level */ |
| set_parameters (tb, h, 0, 0, 2, NULL, -1, -1); |
| return 0; |
| } |
| |
| 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 ("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: |
| return n_ret_value; |
| |
| default: |
| reiserfs_panic("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 = get_blkh_free_space (B_BLK_HEAD(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; |
| } |
| |
| /* 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 */ |
| |
| /* we choose one the following */ |
| #define NOTHING_SHIFT_NO_FLOW 0 |
| #define NOTHING_SHIFT_FLOW 5 |
| #define LEFT_SHIFT_NO_FLOW 10 |
| #define LEFT_SHIFT_FLOW 15 |
| #define RIGHT_SHIFT_NO_FLOW 20 |
| #define RIGHT_SHIFT_FLOW 25 |
| #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; |
| } |
| |
| |
| /* 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 split 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; |
| } |
| |
| |
| |
| /* 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) { |
| 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 */ |
| |
| /* 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; |
| } |
| |
| /* 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; |
| } |
| } |
| |
| |
| /* Check whether current node S[h] is balanced when Decreasing its size by |
| * Deleting or Cutting for INTERNAL node of internal tree. |
| * Calculate parameters for balancing for current level h. |
| * Parameters: |
| * tb tree_balance structure; |
| * h current level of the node; |
| * inum item number in S[h]; |
| * mode i - insert, p - paste; |
| * Returns: 1 - schedule occured; |
| * 0 - balancing for higher levels needed; |
| * -1 - no balancing for higher levels needed; |
| * -2 - no disk space. |
| * |
| * Note: Items of internal nodes have fixed size, so the balance condition for |
| * the internal part of internal tree is as for the B-trees. |
| */ |
| static int dc_check_balance_internal (struct tree_balance * tb, int h) |
| { |
| 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 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); |
| |
| /* 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); |
| |
| 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 = get_dc_child_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 = get_dc_child_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; |
| } |
| |
| /* 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 = get_dc_child_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 = get_dc_child_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 */ |
| /* 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 internal tree. |
| * Calculate parameters for balancing for current level h. |
| * Parameters: |
| * tb tree_balance structure; |
| * h current level of the node; |
| * inum item number in S[h]; |
| * mode i - insert, p - paste; |
| * Returns: 1 - schedule occured; |
| * 0 - balancing for higher levels needed; |
| * -1 - no balancing for higher levels needed; |
| * -2 - no disk space. |
| */ |
| static int dc_check_balance_leaf (struct tree_balance * tb, int h) |
| { |
| struct virtual_node * vn = tb->tb_vn; |
| |
| /* the maximal item size */ |
| int n_ret_value; |
| /* F0 is the parent of the node whose balance is currently being checked */ |
| struct buffer_head * F0; |
| int lfree, rfree /* free space in L and R */; |
| |
| F0 = PATH_H_PPARENT (tb->tb_path, 0); |
| |
| if ( ! F0 ) { |
| /* S[0] is the root now. */ |
| 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]) { |
| /* 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. |
| * Calculate parameters for balancing for current level h. |
| * Parameters: |
| * tb tree_balance structure; |
| * h current level of the node; |
| * inum item number in S[h]; |
| * mode d - delete, c - cut. |
| * Returns: 1 - schedule occured; |
| * 0 - balancing for higher levels needed; |
| * -1 - no balancing for higher levels needed; |
| * -2 - no disk space. |
| */ |
| static int dc_check_balance (struct tree_balance * tb, int 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: |
| * |
| * tb tree_balance structure: |
| * |
| * tb is a large structure that must be read about in the header file |
| * at the same time as this procedure if the reader is to successfully |
| * understand this procedure |
| * |
| * h current level of the node; |
| * inum item number in S[h]; |
| * mode i - insert, p - paste, d - delete, c - cut. |
| * Returns: 1 - schedule occured; |
| * 0 - balancing for higher levels needed; |
| * -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) |
| { |
| struct virtual_node * vn; |
| |
| vn = tb->tb_vn = (struct virtual_node *)(tb->vn_buf);// + ROUND_UP(SB_BMAP_NR (tb->tb_fs) * 2 / 8 + 1, 4)); |
| 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; |
| |
| 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); |
| } |
| |
| |
| /* Check whether parent at the path is the really parent of the current node.*/ |
| static void 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 ) { |
| struct reiserfs_super_block * sb; |
| |
| if ( n_path_offset < FIRST_PATH_ELEMENT_OFFSET - 1 ) |
| reiserfs_panic ("PAP-8260: get_direct_parent: illegal offset in the path"); |
| |
| sb = p_s_tb->tb_fs->fs_ondisk_sb; |
| if ( PATH_OFFSET_PBUFFER(p_s_path, FIRST_PATH_ELEMENT_OFFSET)->b_blocknr == |
| get_sb_root_block (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; |
| } |
| reiserfs_panic ("get_direct_parent: root changed"); |
| } |
| |
| if ( ! B_IS_IN_TREE(p_s_bh = PATH_OFFSET_PBUFFER(p_s_path, n_path_offset - 1)) ) |
| reiserfs_panic ("get_direct_parent: 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) ) |
| reiserfs_panic ("get_direct_parent: wrong position in the path"); |
| |
| if ( get_dc_child_blocknr (B_N_CHILD(p_s_bh, n_position)) != PATH_OFFSET_PBUFFER(p_s_path, n_path_offset)->b_blocknr ) |
| reiserfs_panic ("get_direct_parent: parent in the path is not parent " |
| "of the current node in the tree"); |
| |
| return ; /* 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 |
| * need in order to balance S[n_h], and get them if necessary. |
| * Returns: SCHEDULE_OCCURRED - schedule occured 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; |
| reiserfs_filsys_t * fs = p_s_tb->tb_fs; |
| struct buffer_head * p_s_bh; |
| /*struct virtual_node * vn = p_s_tb->tb_vn;*/ |
| |
| if ( p_s_tb->lnum[n_h] ) { |
| /* We need left neighbor to balance S[n_h]. */ |
| p_s_bh = PATH_OFFSET_PBUFFER(p_s_tb->tb_path, n_path_offset); |
| |
| n_child_position = ( p_s_bh == p_s_tb->FL[n_h] ) ? p_s_tb->lkey[n_h] : |
| get_blkh_nr_items (B_BLK_HEAD(p_s_tb->FL[n_h])); |
| n_son_number = get_dc_child_blocknr (B_N_CHILD (p_s_tb->FL[n_h], n_child_position)); |
| p_s_bh = bread(fs->fs_dev, n_son_number, fs->fs_blocksize); |
| if (!p_s_bh) |
| return IO_ERROR; |
| brelse (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]. */ |
| p_s_bh = PATH_OFFSET_PBUFFER(p_s_tb->tb_path, n_path_offset); |
| n_child_position = ( p_s_bh == p_s_tb->FR[n_h] ) ? p_s_tb->rkey[n_h] + 1 : 0; |
| n_son_number = get_dc_child_blocknr (B_N_CHILD (p_s_tb->FR[n_h], n_child_position)); |
| p_s_bh = bread(fs->fs_dev, n_son_number, fs->fs_blocksize); |
| if (!p_s_bh) |
| return IO_ERROR; |
| |
| brelse (p_s_tb->R[n_h]); |
| p_s_tb->R[n_h] = p_s_bh; |
| } |
| return CARRY_ON; |
| } |
| |
| #if 0 |
| void * reiserfs_kmalloc (size_t size, int flags, struct super_block * s) |
| { |
| void * vp; |
| |
| vp = getmem (size); |
| return vp; |
| } |
| |
| void reiserfs_kfree (/*const */void * vp, size_t size, struct super_block * s) |
| { |
| freemem (vp); |
| |
| |
| kfree (vp); |
| |
| s->u.reiserfs_sb.s_kmallocs -= size; |
| if (s->u.reiserfs_sb.s_kmallocs < 0) |
| reiserfs_warning ("vs-8302: reiserfs_kfree: allocated memory %d\n", s->u.reiserfs_sb.s_kmallocs); |
| |
| } |
| #endif |
| |
| |
| static int get_mem_for_virtual_node (struct tree_balance * tb) |
| { |
| tb->vn_buf = getmem (tb->tb_fs->fs_blocksize); |
| return CARRY_ON; |
| } |
| |
| |
| static void free_virtual_node_mem (struct tree_balance * tb) |
| { |
| freemem (tb->vn_buf); |
| } |
| |
| |
| /* Prepare for balancing, that is |
| * get all necessary parents, and neighbors; |
| * analyze what and where should be moved; |
| * get sufficient number of new nodes; |
| * Balancing will start only after all resources will be collected at a time. |
| * |
| * When ported to SMP kernels, only at the last moment after all needed nodes |
| * are collected in cache, will the resources be locked using the usual |
| * textbook ordered lock acquisition algorithms. Note that ensuring that |
| * this code neither write locks what it does not need to write lock nor locks out of order |
| * will be a pain in the butt that could have been avoided. Grumble grumble. -Hans |
| * |
| * fix is meant in the sense of render unchanging |
| * |
| * Latency might be improved by first gathering a list of what buffers are needed |
| * and then getting as many of them in parallel as possible? -Hans |
| * |
| * Parameters: |
| * op_mode i - insert, d - delete, c - cut (truncate), p - paste (append) |
| * tb tree_balance structure; |
| * inum item number in S[h]; |
| * pos_in_item - comment this if you can |
| * ins_ih & ins_sd are used when inserting |
| * Returns: 1 - schedule occurred while the function worked; |
| * 0 - schedule didn't occur while the function worked; |
| * -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) |
| { |
| int n_pos_in_item = p_s_tb->tb_path->pos_in_item; |
| int n_ret_value, |
| n_h, |
| n_item_num = get_item_pos (p_s_tb->tb_path); |
| /* struct buffer_head * p_s_tbS0 = get_bh (p_s_tb->tb_path);*/ |
| /* struct item_head * ih = get_ih (p_s_tb->tb_path);*/ |
| |
| |
| if (get_mem_for_virtual_node (p_s_tb) != CARRY_ON) |
| reiserfs_panic ("fix_nodes: no memory for virtual node"); |
| |
| /* 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++ ) { |
| get_direct_parent(p_s_tb, n_h); |
| |
| if ( (n_ret_value = check_balance (/*th,*/ n_op_mode, p_s_tb, n_h, n_item_num, |
| n_pos_in_item, p_s_ins_ih)) != 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 ) { |
| return n_ret_value; |
| } |
| if ( n_h != MAX_HEIGHT - 1 ) |
| p_s_tb->insert_size[n_h + 1] = 0; |
| /* ok, analysis and resource gathering are complete */ |
| break; |
| } |
| |
| return n_ret_value; |
| } |
| |
| if ( (n_ret_value = get_neighbors(p_s_tb, n_h)) != CARRY_ON ) { |
| return n_ret_value; |
| } |
| |
| if ( (n_ret_value = get_empty_nodes(/*th,*/ p_s_tb, n_h)) != CARRY_ON ) { |
| return n_ret_value; /* No disk space */ |
| } |
| |
| 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. */ |
| 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. */ |
| 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); |
| } |
| |
| return CARRY_ON; /* go ahead and balance */ |
| } |
| |
| |
| void unfix_nodes (struct tree_balance * p_s_tb) |
| { |
| struct path * p_s_path = p_s_tb->tb_path; |
| int n_counter; |
| // int i, j; |
| //struct buffer_head * bh; |
| |
| /* Release path buffers. */ |
| pathrelse(p_s_path); |
| |
| |
| for ( n_counter = 0; n_counter < MAX_HEIGHT; n_counter++ ) { |
| /* Release fathers and neighbors. */ |
| brelse(p_s_tb->L[n_counter]); |
| brelse(p_s_tb->R[n_counter]); |
| brelse(p_s_tb->FL[n_counter]); |
| brelse(p_s_tb->FR[n_counter]); |
| brelse(p_s_tb->CFL[n_counter]); |
| brelse(p_s_tb->CFR[n_counter]); |
| } |
| |
| /* Could be optimized. Will be done by PAP someday */ |
| for ( n_counter = 0; n_counter < MAX_FEB_SIZE; n_counter++ ) { |
| if ( p_s_tb->FEB[n_counter] ) { |
| /* release what was not used */ |
| reiserfs_free_block(p_s_tb->tb_fs, p_s_tb->FEB[n_counter]->b_blocknr); |
| |
| bforget(p_s_tb->FEB[n_counter]); |
| /* tree balance bitmap of bitmaps has bit set already */ |
| } |
| /* release used as new nodes including a new root */ |
| brelse (p_s_tb->used[n_counter]); |
| } |
| |
| free_virtual_node_mem (p_s_tb); |
| } |
| |
| |
| |
| |
| |
| |