diff options
Diffstat (limited to 'fs/reiserfs/do_balan.c')
| -rw-r--r-- | fs/reiserfs/do_balan.c | 3236 |
1 files changed, 1888 insertions, 1348 deletions
diff --git a/fs/reiserfs/do_balan.c b/fs/reiserfs/do_balan.c index 2118db2896c..b2264ba3cc5 100644 --- a/fs/reiserfs/do_balan.c +++ b/fs/reiserfs/do_balan.c @@ -8,7 +8,6 @@ /* balance the tree according to the analysis made before, */ /* and using buffers obtained after all above. */ - /** ** balance_leaf_when_delete ** balance_leaf @@ -24,23 +23,22 @@ #ifdef CONFIG_REISERFS_CHECK -struct tree_balance * cur_tb = NULL; /* detects whether more than one - copy of tb exists as a means - of checking whether schedule - is interrupting do_balance */ +struct tree_balance *cur_tb = NULL; /* detects whether more than one + copy of tb exists as a means + of checking whether schedule + is interrupting do_balance */ #endif -inline void do_balance_mark_leaf_dirty (struct tree_balance * tb, - struct buffer_head * bh, int flag) +inline void do_balance_mark_leaf_dirty(struct tree_balance *tb, + struct buffer_head *bh, int flag) { - journal_mark_dirty(tb->transaction_handle, - tb->transaction_handle->t_super, bh) ; + journal_mark_dirty(tb->transaction_handle, + tb->transaction_handle->t_super, bh); } #define do_balance_mark_internal_dirty do_balance_mark_leaf_dirty #define do_balance_mark_sb_dirty do_balance_mark_leaf_dirty - /* summary: if deleting something ( tb->insert_size[0] < 0 ) return(balance_leaf_when_delete()); (flag d handled here) @@ -64,8 +62,6 @@ be performed by do_balance. -Hans */ - - /* Balance leaf node in case of delete or cut: insert_size[0] < 0 * * lnum, rnum can have values >= -1 @@ -73,1384 +69,1933 @@ be performed by do_balance. * 0 means that nothing should be done with the neighbor * >0 means to shift entirely or partly the specified number of items to the neighbor */ -static int balance_leaf_when_delete (struct tree_balance * tb, int flag) +static int balance_leaf_when_delete(struct tree_balance *tb, int flag) { - struct buffer_head * tbS0 = PATH_PLAST_BUFFER (tb->tb_path); - int item_pos = PATH_LAST_POSITION (tb->tb_path); - int pos_in_item = tb->tb_path->pos_in_item; - struct buffer_info bi; - int n; - struct item_head * ih; + struct buffer_head *tbS0 = PATH_PLAST_BUFFER(tb->tb_path); + int item_pos = PATH_LAST_POSITION(tb->tb_path); + int pos_in_item = tb->tb_path->pos_in_item; + struct buffer_info bi; + int n; + struct item_head *ih; - RFALSE( tb->FR[0] && B_LEVEL (tb->FR[0]) != DISK_LEAF_NODE_LEVEL + 1, - "vs- 12000: level: wrong FR %z", tb->FR[0]); - RFALSE( tb->blknum[0] > 1, - "PAP-12005: tb->blknum == %d, can not be > 1", tb->blknum[0]); - RFALSE( ! tb->blknum[0] && ! PATH_H_PPARENT(tb->tb_path, 0), - "PAP-12010: tree can not be empty"); + RFALSE(tb->FR[0] && B_LEVEL(tb->FR[0]) != DISK_LEAF_NODE_LEVEL + 1, + "vs- 12000: level: wrong FR %z", tb->FR[0]); + RFALSE(tb->blknum[0] > 1, + "PAP-12005: tb->blknum == %d, can not be > 1", tb->blknum[0]); + RFALSE(!tb->blknum[0] && !PATH_H_PPARENT(tb->tb_path, 0), + "PAP-12010: tree can not be empty"); - ih = B_N_PITEM_HEAD (tbS0, item_pos); + ih = B_N_PITEM_HEAD(tbS0, item_pos); - /* Delete or truncate the item */ + /* Delete or truncate the item */ - switch (flag) { - case M_DELETE: /* delete item in S[0] */ + switch (flag) { + case M_DELETE: /* delete item in S[0] */ + + RFALSE(ih_item_len(ih) + IH_SIZE != -tb->insert_size[0], + "vs-12013: mode Delete, insert size %d, ih to be deleted %h", + -tb->insert_size[0], ih); + + bi.tb = tb; + bi.bi_bh = tbS0; + bi.bi_parent = PATH_H_PPARENT(tb->tb_path, 0); + bi.bi_position = PATH_H_POSITION(tb->tb_path, 1); + leaf_delete_items(&bi, 0, item_pos, 1, -1); + + if (!item_pos && tb->CFL[0]) { + if (B_NR_ITEMS(tbS0)) { + replace_key(tb, tb->CFL[0], tb->lkey[0], tbS0, + 0); + } else { + if (!PATH_H_POSITION(tb->tb_path, 1)) + replace_key(tb, tb->CFL[0], tb->lkey[0], + PATH_H_PPARENT(tb->tb_path, + 0), 0); + } + } - RFALSE( ih_item_len(ih) + IH_SIZE != -tb->insert_size[0], - "vs-12013: mode Delete, insert size %d, ih to be deleted %h", - -tb->insert_size [0], ih); + RFALSE(!item_pos && !tb->CFL[0], + "PAP-12020: tb->CFL[0]==%p, tb->L[0]==%p", tb->CFL[0], + tb->L[0]); - bi.tb = tb; - bi.bi_bh = tbS0; - bi.bi_parent = PATH_H_PPARENT (tb->tb_path, 0); - bi.bi_position = PATH_H_POSITION (tb->tb_path, 1); - leaf_delete_items (&bi, 0, item_pos, 1, -1); - - if ( ! item_pos && tb->CFL[0] ) { - if ( B_NR_ITEMS(tbS0) ) { - replace_key(tb, tb->CFL[0],tb->lkey[0],tbS0,0); - } - else { - if ( ! PATH_H_POSITION (tb->tb_path, 1) ) - replace_key(tb, tb->CFL[0],tb->lkey[0],PATH_H_PPARENT(tb->tb_path, 0),0); - } - } - - RFALSE( ! item_pos && !tb->CFL[0], - "PAP-12020: tb->CFL[0]==%p, tb->L[0]==%p", tb->CFL[0], tb->L[0]); - - break; - - case M_CUT: { /* cut item in S[0] */ - bi.tb = tb; - bi.bi_bh = tbS0; - bi.bi_parent = PATH_H_PPARENT (tb->tb_path, 0); - bi.bi_position = PATH_H_POSITION (tb->tb_path, 1); - if (is_direntry_le_ih (ih)) { - - /* UFS unlink semantics are such that you can only delete one directory entry at a time. */ - /* when we cut a directory tb->insert_size[0] means number of entries to be cut (always 1) */ - tb->insert_size[0] = -1; - leaf_cut_from_buffer (&bi, item_pos, pos_in_item, -tb->insert_size[0]); - - RFALSE( ! item_pos && ! pos_in_item && ! tb->CFL[0], - "PAP-12030: can not change delimiting key. CFL[0]=%p", - tb->CFL[0]); - - if ( ! item_pos && ! pos_in_item && tb->CFL[0] ) { - replace_key(tb, tb->CFL[0],tb->lkey[0],tbS0,0); - } - } else { - leaf_cut_from_buffer (&bi, item_pos, pos_in_item, -tb->insert_size[0]); - - RFALSE( ! ih_item_len(ih), - "PAP-12035: cut must leave non-zero dynamic length of item"); - } - break; - } - - default: - print_cur_tb ("12040"); - reiserfs_panic (tb->tb_sb, "PAP-12040: balance_leaf_when_delete: unexpectable mode: %s(%d)", - (flag == M_PASTE) ? "PASTE" : ((flag == M_INSERT) ? "INSERT" : "UNKNOWN"), flag); - } - - /* the rule is that no shifting occurs unless by shifting a node can be freed */ - n = B_NR_ITEMS(tbS0); - if ( tb->lnum[0] ) /* L[0] takes part in balancing */ - { - if ( tb->lnum[0] == -1 ) /* L[0] must be joined with S[0] */ - { - if ( tb->rnum[0] == -1 ) /* R[0] must be also joined with S[0] */ - { - if ( tb->FR[0] == PATH_H_PPARENT(tb->tb_path, 0) ) - { - /* all contents of all the 3 buffers will be in L[0] */ - if ( PATH_H_POSITION (tb->tb_path, 1) == 0 && 1 < B_NR_ITEMS(tb->FR[0]) ) - replace_key(tb, tb->CFL[0],tb->lkey[0],tb->FR[0],1); - - leaf_move_items (LEAF_FROM_S_TO_L, tb, n, -1, NULL); - leaf_move_items (LEAF_FROM_R_TO_L, tb, B_NR_ITEMS(tb->R[0]), -1, NULL); - - reiserfs_invalidate_buffer (tb, tbS0); - reiserfs_invalidate_buffer (tb, tb->R[0]); - - return 0; + break; + + case M_CUT:{ /* cut item in S[0] */ + bi.tb = tb; + bi.bi_bh = tbS0; + bi.bi_parent = PATH_H_PPARENT(tb->tb_path, 0); + bi.bi_position = PATH_H_POSITION(tb->tb_path, 1); + if (is_direntry_le_ih(ih)) { + + /* UFS unlink semantics are such that you can only delete one directory entry at a time. */ + /* when we cut a directory tb->insert_size[0] means number of entries to be cut (always 1) */ + tb->insert_size[0] = -1; + leaf_cut_from_buffer(&bi, item_pos, pos_in_item, + -tb->insert_size[0]); + + RFALSE(!item_pos && !pos_in_item && !tb->CFL[0], + "PAP-12030: can not change delimiting key. CFL[0]=%p", + tb->CFL[0]); + + if (!item_pos && !pos_in_item && tb->CFL[0]) { + replace_key(tb, tb->CFL[0], tb->lkey[0], + tbS0, 0); + } + } else { + leaf_cut_from_buffer(&bi, item_pos, pos_in_item, + -tb->insert_size[0]); + + RFALSE(!ih_item_len(ih), + "PAP-12035: cut must leave non-zero dynamic length of item"); + } + break; } - /* all contents of all the 3 buffers will be in R[0] */ - leaf_move_items (LEAF_FROM_S_TO_R, tb, n, -1, NULL); - leaf_move_items (LEAF_FROM_L_TO_R, tb, B_NR_ITEMS(tb->L[0]), -1, NULL); - /* right_delimiting_key is correct in R[0] */ - replace_key(tb, tb->CFR[0],tb->rkey[0],tb->R[0],0); + default: + print_cur_tb("12040"); + reiserfs_panic(tb->tb_sb, + "PAP-12040: balance_leaf_when_delete: unexpectable mode: %s(%d)", + (flag == + M_PASTE) ? "PASTE" : ((flag == + M_INSERT) ? "INSERT" : + "UNKNOWN"), flag); + } - reiserfs_invalidate_buffer (tb, tbS0); - reiserfs_invalidate_buffer (tb, tb->L[0]); + /* the rule is that no shifting occurs unless by shifting a node can be freed */ + n = B_NR_ITEMS(tbS0); + if (tb->lnum[0]) { /* L[0] takes part in balancing */ + if (tb->lnum[0] == -1) { /* L[0] must be joined with S[0] */ + if (tb->rnum[0] == -1) { /* R[0] must be also joined with S[0] */ + if (tb->FR[0] == PATH_H_PPARENT(tb->tb_path, 0)) { + /* all contents of all the 3 buffers will be in L[0] */ + if (PATH_H_POSITION(tb->tb_path, 1) == 0 + && 1 < B_NR_ITEMS(tb->FR[0])) + replace_key(tb, tb->CFL[0], + tb->lkey[0], + tb->FR[0], 1); + + leaf_move_items(LEAF_FROM_S_TO_L, tb, n, + -1, NULL); + leaf_move_items(LEAF_FROM_R_TO_L, tb, + B_NR_ITEMS(tb->R[0]), + -1, NULL); + + reiserfs_invalidate_buffer(tb, tbS0); + reiserfs_invalidate_buffer(tb, + tb->R[0]); + + return 0; + } + /* all contents of all the 3 buffers will be in R[0] */ + leaf_move_items(LEAF_FROM_S_TO_R, tb, n, -1, + NULL); + leaf_move_items(LEAF_FROM_L_TO_R, tb, + B_NR_ITEMS(tb->L[0]), -1, NULL); + + /* right_delimiting_key is correct in R[0] */ + replace_key(tb, tb->CFR[0], tb->rkey[0], + tb->R[0], 0); - return -1; - } + reiserfs_invalidate_buffer(tb, tbS0); + reiserfs_invalidate_buffer(tb, tb->L[0]); - RFALSE( tb->rnum[0] != 0, - "PAP-12045: rnum must be 0 (%d)", tb->rnum[0]); - /* all contents of L[0] and S[0] will be in L[0] */ - leaf_shift_left(tb, n, -1); + return -1; + } - reiserfs_invalidate_buffer (tb, tbS0); + RFALSE(tb->rnum[0] != 0, + "PAP-12045: rnum must be 0 (%d)", tb->rnum[0]); + /* all contents of L[0] and S[0] will be in L[0] */ + leaf_shift_left(tb, n, -1); - return 0; + reiserfs_invalidate_buffer(tb, tbS0); + + return 0; + } + /* a part of contents of S[0] will be in L[0] and the rest part of S[0] will be in R[0] */ + + RFALSE((tb->lnum[0] + tb->rnum[0] < n) || + (tb->lnum[0] + tb->rnum[0] > n + 1), + "PAP-12050: rnum(%d) and lnum(%d) and item number(%d) in S[0] are not consistent", + tb->rnum[0], tb->lnum[0], n); + RFALSE((tb->lnum[0] + tb->rnum[0] == n) && + (tb->lbytes != -1 || tb->rbytes != -1), + "PAP-12055: bad rbytes (%d)/lbytes (%d) parameters when items are not split", + tb->rbytes, tb->lbytes); + RFALSE((tb->lnum[0] + tb->rnum[0] == n + 1) && + (tb->lbytes < 1 || tb->rbytes != -1), + "PAP-12060: bad rbytes (%d)/lbytes (%d) parameters when items are split", + tb->rbytes, tb->lbytes); + + leaf_shift_left(tb, tb->lnum[0], tb->lbytes); + leaf_shift_right(tb, tb->rnum[0], tb->rbytes); + + reiserfs_invalidate_buffer(tb, tbS0); + + return 0; } - /* a part of contents of S[0] will be in L[0] and the rest part of S[0] will be in R[0] */ - - RFALSE( ( tb->lnum[0] + tb->rnum[0] < n ) || - ( tb->lnum[0] + tb->rnum[0] > n+1 ), - "PAP-12050: rnum(%d) and lnum(%d) and item number(%d) in S[0] are not consistent", - tb->rnum[0], tb->lnum[0], n); - RFALSE( ( tb->lnum[0] + tb->rnum[0] == n ) && - (tb->lbytes != -1 || tb->rbytes != -1), - "PAP-12055: bad rbytes (%d)/lbytes (%d) parameters when items are not split", - tb->rbytes, tb->lbytes); - RFALSE( ( tb->lnum[0] + tb->rnum[0] == n + 1 ) && - (tb->lbytes < 1 || tb->rbytes != -1), - "PAP-12060: bad rbytes (%d)/lbytes (%d) parameters when items are split", - tb->rbytes, tb->lbytes); - - leaf_shift_left (tb, tb->lnum[0], tb->lbytes); - leaf_shift_right(tb, tb->rnum[0], tb->rbytes); - - reiserfs_invalidate_buffer (tb, tbS0); - return 0; - } + if (tb->rnum[0] == -1) { + /* all contents of R[0] and S[0] will be in R[0] */ + leaf_shift_right(tb, n, -1); + reiserfs_invalidate_buffer(tb, tbS0); + return 0; + } - if ( tb->rnum[0] == -1 ) { - /* all contents of R[0] and S[0] will be in R[0] */ - leaf_shift_right(tb, n, -1); - reiserfs_invalidate_buffer (tb, tbS0); + RFALSE(tb->rnum[0], + "PAP-12065: bad rnum parameter must be 0 (%d)", tb->rnum[0]); return 0; - } - - RFALSE( tb->rnum[0], - "PAP-12065: bad rnum parameter must be 0 (%d)", tb->rnum[0]); - return 0; } - -static int balance_leaf (struct tree_balance * tb, - struct item_head * ih, /* item header of inserted item (this is on little endian) */ - const char * body, /* body of inserted item or bytes to paste */ - int flag, /* i - insert, d - delete, c - cut, p - paste - (see comment to do_balance) */ - struct item_head * insert_key, /* in our processing of one level we sometimes determine what - must be inserted into the next higher level. This insertion - consists of a key or two keys and their corresponding - pointers */ - struct buffer_head ** insert_ptr /* inserted node-ptrs for the next level */ +static int balance_leaf(struct tree_balance *tb, struct item_head *ih, /* item header of inserted item (this is on little endian) */ + const char *body, /* body of inserted item or bytes to paste */ + int flag, /* i - insert, d - delete, c - cut, p - paste + (see comment to do_balance) */ + struct item_head *insert_key, /* in our processing of one level we sometimes determine what + must be inserted into the next higher level. This insertion + consists of a key or two keys and their corresponding + pointers */ + struct buffer_head **insert_ptr /* inserted node-ptrs for the next level */ ) { - struct buffer_head * tbS0 = PATH_PLAST_BUFFER (tb->tb_path); - int item_pos = PATH_LAST_POSITION (tb->tb_path); /* index into the array of item headers in S[0] - of the affected item */ - struct buffer_info bi; - struct buffer_head *S_new[2]; /* new nodes allocated to hold what could not fit into S */ - int snum[2]; /* number of items that will be placed - into S_new (includes partially shifted - items) */ - int sbytes[2]; /* if an item is partially shifted into S_new then - if it is a directory item - it is the number of entries from the item that are shifted into S_new - else - it is the number of bytes from the item that are shifted into S_new - */ - int n, i; - int ret_val; - int pos_in_item; - int zeros_num; - - PROC_INFO_INC( tb -> tb_sb, balance_at[ 0 ] ); - - /* Make balance in case insert_size[0] < 0 */ - if ( tb->insert_size[0] < 0 ) - return balance_leaf_when_delete (tb, flag); - - zeros_num = 0; - if (flag == M_INSERT && body == 0) - zeros_num = ih_item_len( ih ); - - pos_in_item = tb->tb_path->pos_in_item; - /* for indirect item pos_in_item is measured in unformatted node - pointers. Recalculate to bytes */ - if (flag != M_INSERT && is_indirect_le_ih (B_N_PITEM_HEAD (tbS0, item_pos))) - pos_in_item *= UNFM_P_SIZE; - - if ( tb->lnum[0] > 0 ) { - /* Shift lnum[0] items from S[0] to the left neighbor L[0] */ - if ( item_pos < tb->lnum[0] ) { - /* new item or it part falls to L[0], shift it too */ - n = B_NR_ITEMS(tb->L[0]); - - switch (flag) { - case M_INSERT: /* insert item into L[0] */ - - if ( item_pos == tb->lnum[0] - 1 && tb->lbytes != -1 ) { - /* part of new item falls into L[0] */ - int new_item_len; - int version; - - ret_val = leaf_shift_left (tb, tb->lnum[0]-1, -1); - - /* Calculate item length to insert to S[0] */ - new_item_len = ih_item_len(ih) - tb->lbytes; - /* Calculate and check item length to insert to L[0] */ - put_ih_item_len(ih, ih_item_len(ih) - new_item_len ); - - RFALSE( ih_item_len(ih) <= 0, - "PAP-12080: there is nothing to insert into L[0]: ih_item_len=%d", - ih_item_len(ih)); - - /* Insert new item into L[0] */ - bi.tb = tb; - bi.bi_bh = tb->L[0]; - bi.bi_parent = tb->FL[0]; - bi.bi_position = get_left_neighbor_position (tb, 0); - leaf_insert_into_buf (&bi, n + item_pos - ret_val, ih, body, - zeros_num > ih_item_len(ih) ? ih_item_len(ih) : zeros_num); - - version = ih_version (ih); - - /* Calculate key component, item length and body to insert into S[0] */ - set_le_ih_k_offset( ih, le_ih_k_offset( ih ) + (tb->lbytes << (is_indirect_le_ih(ih)?tb->tb_sb->s_blocksize_bits - UNFM_P_SHIFT:0)) ); - - put_ih_item_len( ih, new_item_len ); - if ( tb->lbytes > zeros_num ) { - body += (tb->lbytes - zeros_num); - zeros_num = 0; - } - else - zeros_num -= tb->lbytes; - - RFALSE( ih_item_len(ih) <= 0, - "PAP-12085: there is nothing to insert into S[0]: ih_item_len=%d", - ih_item_len(ih)); - } else { - /* new item in whole falls into L[0] */ - /* Shift lnum[0]-1 items to L[0] */ - ret_val = leaf_shift_left(tb, tb->lnum[0]-1, tb->lbytes); - /* Insert new item into L[0] */ - bi.tb = tb; - bi.bi_bh = tb->L[0]; - bi.bi_parent = tb->FL[0]; - bi.bi_position = get_left_neighbor_position (tb, 0); - leaf_insert_into_buf (&bi, n + item_pos - ret_val, ih, body, zeros_num); - tb->insert_size[0] = 0; - zeros_num = 0; - } - break; - - case M_PASTE: /* append item in L[0] */ - - if ( item_pos == tb->lnum[0] - 1 && tb->lbytes != -1 ) { - /* we must shift the part of the appended item */ - if ( is_direntry_le_ih (B_N_PITEM_HEAD (tbS0, item_pos))) { - - RFALSE( zeros_num, - "PAP-12090: invalid parameter in case of a directory"); - /* directory item */ - if ( tb->lbytes > pos_in_item ) { - /* new directory entry falls into L[0] */ - struct item_head * pasted; - int l_pos_in_item = pos_in_item; - - /* Shift lnum[0] - 1 items in whole. Shift lbytes - 1 entries from given directory item */ - ret_val = leaf_shift_left(tb, tb->lnum[0], tb->lbytes - 1); - if ( ret_val && ! item_pos ) { - pasted = B_N_PITEM_HEAD(tb->L[0],B_NR_ITEMS(tb->L[0])-1); - l_pos_in_item += I_ENTRY_COUNT(pasted) - (tb->lbytes-1); - } - - /* Append given directory entry to directory item */ - bi.tb = tb; - bi.bi_bh = tb->L[0]; - bi.bi_parent = tb->FL[0]; - bi.bi_position = get_left_neighbor_position (tb, 0); - leaf_paste_in_buffer (&bi, n + item_pos - ret_val, l_pos_in_item, - tb->insert_size[0], body, zeros_num); - - /* previous string prepared space for pasting new entry, following string pastes this entry */ - - /* when we have merge directory item, pos_in_item has been changed too */ - - /* paste new directory entry. 1 is entry number */ - leaf_paste_entries (bi.bi_bh, n + item_pos - ret_val, l_pos_in_item, 1, - (struct reiserfs_de_head *)body, - body + DEH_SIZE, tb->insert_size[0] - ); - tb->insert_size[0] = 0; - } else { - /* new directory item doesn't fall into L[0] */ - /* Shift lnum[0]-1 items in whole. Shift lbytes directory entries from directory item number lnum[0] */ - leaf_shift_left (tb, tb->lnum[0], tb->lbytes); - } - /* Calculate new position to append in item body */ - pos_in_item -= tb->lbytes; - } - else { - /* regular object */ - RFALSE( tb->lbytes <= 0, - "PAP-12095: there is nothing to shift to L[0]. lbytes=%d", - tb->lbytes); - RFALSE( pos_in_item != ih_item_len(B_N_PITEM_HEAD(tbS0, item_pos)), - "PAP-12100: incorrect position to paste: item_len=%d, pos_in_item=%d", - ih_item_len(B_N_PITEM_HEAD(tbS0,item_pos)), pos_in_item); - - if ( tb->lbytes >= pos_in_item ) { - /* appended item will be in L[0] in whole */ - int l_n; - - /* this bytes number must be appended to the last item of L[h] */ - l_n = tb->lbytes - pos_in_item; - - /* Calculate new insert_size[0] */ - tb->insert_size[0] -= l_n; - - RFALSE( tb->insert_size[0] <= 0, - "PAP-12105: there is nothing to paste into L[0]. insert_size=%d", - tb->insert_size[0]); - ret_val = leaf_shift_left(tb,tb->lnum[0], - ih_item_len(B_N_PITEM_HEAD(tbS0,item_pos))); - /* Append to body of item in L[0] */ - bi.tb = tb; - bi.bi_bh = tb->L[0]; - bi.bi_parent = tb->FL[0]; - bi.bi_position = get_left_neighbor_position (tb, 0); - leaf_paste_in_buffer( - &bi,n + item_pos - ret_val, - ih_item_len( B_N_PITEM_HEAD(tb->L[0],n+item_pos-ret_val)), - l_n,body, zeros_num > l_n ? l_n : zeros_num - ); - /* 0-th item in S0 can be only of DIRECT type when l_n != 0*/ - { - int version; - int temp_l = l_n; - - RFALSE (ih_item_len (B_N_PITEM_HEAD (tbS0, 0)), - "PAP-12106: item length must be 0"); - RFALSE (comp_short_le_keys (B_N_PKEY (tbS0, 0), - B_N_PKEY (tb->L[0], - n + item_pos - ret_val)), - "PAP-12107: items must be of the same file"); - if (is_indirect_le_ih(B_N_PITEM_HEAD (tb->L[0], - n + item_pos - ret_val))) { - temp_l = l_n << (tb->tb_sb->s_blocksize_bits - UNFM_P_SHIFT); + struct buffer_head *tbS0 = PATH_PLAST_BUFFER(tb->tb_path); + int item_pos = PATH_LAST_POSITION(tb->tb_path); /* index into the array of item headers in S[0] + of the affected item */ + struct buffer_info bi; + struct buffer_head *S_new[2]; /* new nodes allocated to hold what could not fit into S */ + int snum[2]; /* number of items that will be placed + into S_new (includes partially shifted + items) */ + int sbytes[2]; /* if an item is partially shifted into S_new then + if it is a directory item + it is the number of entries from the item that are shifted into S_new + else + it is the number of bytes from the item that are shifted into S_new + */ + int n, i; + int ret_val; + int pos_in_item; + int zeros_num; + + PROC_INFO_INC(tb->tb_sb, balance_at[0]); + + /* Make balance in case insert_size[0] < 0 */ + if (tb->insert_size[0] < 0) + return balance_leaf_when_delete(tb, flag); + + zeros_num = 0; + if (flag == M_INSERT && body == 0) + zeros_num = ih_item_len(ih); + + pos_in_item = tb->tb_path->pos_in_item; + /* for indirect item pos_in_item is measured in unformatted node + pointers. Recalculate to bytes */ + if (flag != M_INSERT + && is_indirect_le_ih(B_N_PITEM_HEAD(tbS0, item_pos))) + pos_in_item *= UNFM_P_SIZE; + + if (tb->lnum[0] > 0) { + /* Shift lnum[0] items from S[0] to the left neighbor L[0] */ + if (item_pos < tb->lnum[0]) { + /* new item or it part falls to L[0], shift it too */ + n = B_NR_ITEMS(tb->L[0]); + + switch (flag) { + case M_INSERT: /* insert item into L[0] */ + + if (item_pos == tb->lnum[0] - 1 + && tb->lbytes != -1) { + /* part of new item falls into L[0] */ + int new_item_len; + int version; + + ret_val = + leaf_shift_left(tb, tb->lnum[0] - 1, + -1); + + /* Calculate item length to insert to S[0] */ + new_item_len = + ih_item_len(ih) - tb->lbytes; + /* Calculate and check item length to insert to L[0] */ + put_ih_item_len(ih, + ih_item_len(ih) - + new_item_len); + + RFALSE(ih_item_len(ih) <= 0, + "PAP-12080: there is nothing to insert into L[0]: ih_item_len=%d", + ih_item_len(ih)); + + /* Insert new item into L[0] */ + bi.tb = tb; + bi.bi_bh = tb->L[0]; + bi.bi_parent = tb->FL[0]; + bi.bi_position = + get_left_neighbor_position(tb, 0); + leaf_insert_into_buf(&bi, + n + item_pos - + ret_val, ih, body, + zeros_num > + ih_item_len(ih) ? + ih_item_len(ih) : + zeros_num); + + version = ih_version(ih); + + /* Calculate key component, item length and body to insert into S[0] */ + set_le_ih_k_offset(ih, + le_ih_k_offset(ih) + + (tb-> + lbytes << + (is_indirect_le_ih + (ih) ? tb->tb_sb-> + s_blocksize_bits - + UNFM_P_SHIFT : + 0))); + + put_ih_item_len(ih, new_item_len); + if (tb->lbytes > zeros_num) { + body += + (tb->lbytes - zeros_num); + zeros_num = 0; + } else + zeros_num -= tb->lbytes; + + RFALSE(ih_item_len(ih) <= 0, + "PAP-12085: there is nothing to insert into S[0]: ih_item_len=%d", + ih_item_len(ih)); + } else { + /* new item in whole falls into L[0] */ + /* Shift lnum[0]-1 items to L[0] */ + ret_val = + leaf_shift_left(tb, tb->lnum[0] - 1, + tb->lbytes); + /* Insert new item into L[0] */ + bi.tb = tb; + bi.bi_bh = tb->L[0]; + bi.bi_parent = tb->FL[0]; + bi.bi_position = + get_left_neighbor_position(tb, 0); + leaf_insert_into_buf(&bi, + n + item_pos - + ret_val, ih, body, + zeros_num); + tb->insert_size[0] = 0; + zeros_num = 0; } - /* update key of first item in S0 */ - version = ih_version (B_N_PITEM_HEAD (tbS0, 0)); - set_le_key_k_offset (version, B_N_PKEY (tbS0, 0), - le_key_k_offset (version, B_N_PKEY (tbS0, 0)) + temp_l); - /* update left delimiting key */ - set_le_key_k_offset (version, B_N_PDELIM_KEY(tb->CFL[0],tb->lkey[0]), - le_key_k_offset (version, B_N_PDELIM_KEY(tb->CFL[0],tb->lkey[0])) + temp_l); - } - - /* Calculate new body, position in item and insert_size[0] */ - if ( l_n > zeros_num ) { - body += (l_n - zeros_num); - zeros_num = 0; - } - else - zeros_num -= l_n; - pos_in_item = 0; - - RFALSE( comp_short_le_keys - (B_N_PKEY(tbS0,0), - B_N_PKEY(tb->L[0],B_NR_ITEMS(tb->L[0])-1)) || - - !op_is_left_mergeable - (B_N_PKEY (tbS0, 0), tbS0->b_size) || - !op_is_left_mergeable - (B_N_PDELIM_KEY(tb->CFL[0],tb->lkey[0]), - tbS0->b_size), - "PAP-12120: item must be merge-able with left neighboring item"); - } - else /* only part of the appended item will be in L[0] */ - { - /* Calculate position in item for append in S[0] */ - pos_in_item -= tb->lbytes; - - RFALSE( pos_in_item <= 0, - "PAP-12125: no place for paste. pos_in_item=%d", pos_in_item); - - /* Shift lnum[0] - 1 items in whole. Shift lbytes - 1 byte from item number lnum[0] */ - leaf_shift_left(tb,tb->lnum[0],tb->lbytes); - } - } - } - else /* appended item will be in L[0] in whole */ - { - struct item_head * pasted; - - if ( ! item_pos && op_is_left_mergeable (B_N_PKEY (tbS0, 0), tbS0->b_size) ) - { /* if we paste into first item of S[0] and it is left mergable */ - /* then increment pos_in_item by the size of the last item in L[0] */ - pasted = B_N_PITEM_HEAD(tb->L[0],n-1); - if ( is_direntry_le_ih (pasted) ) - pos_in_item += ih_entry_count(pasted); - else - pos_in_item += ih_item_len(pasted); + break; + + case M_PASTE: /* append item in L[0] */ + + if (item_pos == tb->lnum[0] - 1 + && tb->lbytes != -1) { + /* we must shift the part of the appended item */ + if (is_direntry_le_ih + (B_N_PITEM_HEAD(tbS0, item_pos))) { + + RFALSE(zeros_num, + "PAP-12090: invalid parameter in case of a directory"); + /* directory item */ + if (tb->lbytes > pos_in_item) { + /* new directory entry falls into L[0] */ + struct item_head + *pasted; + int l_pos_in_item = + pos_in_item; + + /* Shift lnum[0] - 1 items in whole. Shift lbytes - 1 entries from given directory item */ + ret_val = + leaf_shift_left(tb, + tb-> + lnum + [0], + tb-> + lbytes + - + 1); + if (ret_val + && !item_pos) { + pasted = + B_N_PITEM_HEAD + (tb->L[0], + B_NR_ITEMS + (tb-> + L[0]) - + 1); + l_pos_in_item += + I_ENTRY_COUNT + (pasted) - + (tb-> + lbytes - + 1); + } + + /* Append given directory entry to directory item */ + bi.tb = tb; + bi.bi_bh = tb->L[0]; + bi.bi_parent = + tb->FL[0]; + bi.bi_position = + get_left_neighbor_position + (tb, 0); + leaf_paste_in_buffer + (&bi, + n + item_pos - + ret_val, + l_pos_in_item, + tb->insert_size[0], + body, zeros_num); + + /* previous string prepared space for pasting new entry, following string pastes this entry */ + + /* when we have merge directory item, pos_in_item has been changed too */ + + /* paste new directory entry. 1 is entry number */ + leaf_paste_entries(bi. + bi_bh, + n + + item_pos + - + ret_val, + l_pos_in_item, + 1, + (struct + reiserfs_de_head + *) + body, + body + + + DEH_SIZE, + tb-> + insert_size + [0] + ); + tb->insert_size[0] = 0; + } else { + /* new directory item doesn't fall into L[0] */ + /* Shift lnum[0]-1 items in whole. Shift lbytes directory entries from directory item number lnum[0] */ + leaf_shift_left(tb, + tb-> + lnum[0], + tb-> + lbytes); + } + /* Calculate new position to append in item body */ + pos_in_item -= tb->lbytes; + } else { + /* regular object */ + RFALSE(tb->lbytes <= 0, + "PAP-12095: there is nothing to shift to L[0]. lbytes=%d", + tb->lbytes); + RFALSE(pos_in_item != + ih_item_len + (B_N_PITEM_HEAD + (tbS0, item_pos)), + "PAP-12100: incorrect position to paste: item_len=%d, pos_in_item=%d", + ih_item_len + (B_N_PITEM_HEAD + (tbS0, item_pos)), + pos_in_item); + + if (tb->lbytes >= pos_in_item) { + /* appended item will be in L[0] in whole */ + int l_n; + + /* this bytes number must be appended to the last item of L[h] */ + l_n = + tb->lbytes - + pos_in_item; + + /* Calculate new insert_size[0] */ + tb->insert_size[0] -= + l_n; + + RFALSE(tb-> + insert_size[0] <= + 0, + "PAP-12105: there is nothing to paste into L[0]. insert_size=%d", + tb-> + insert_size[0]); + ret_val = + leaf_shift_left(tb, + tb-> + lnum + [0], + ih_item_len + (B_N_PITEM_HEAD + (tbS0, + item_pos))); + /* Append to body of item in L[0] */ + bi.tb = tb; + bi.bi_bh = tb->L[0]; + bi.bi_parent = + tb->FL[0]; + bi.bi_position = + get_left_neighbor_position + (tb, 0); + leaf_paste_in_buffer + (&bi, + n + item_pos - + ret_val, + ih_item_len + (B_N_PITEM_HEAD + (tb->L[0], + n + item_pos - + ret_val)), l_n, + body, + zeros_num > + l_n ? l_n : + zeros_num); + /* 0-th item in S0 can be only of DIRECT type when l_n != 0 */ + { + int version; + int temp_l = + l_n; + + RFALSE + (ih_item_len + (B_N_PITEM_HEAD + (tbS0, + 0)), + "PAP-12106: item length must be 0"); + RFALSE + (comp_short_le_keys + (B_N_PKEY + (tbS0, 0), + B_N_PKEY + (tb->L[0], + n + + item_pos + - + ret_val)), + "PAP-12107: items must be of the same file"); + if (is_indirect_le_ih(B_N_PITEM_HEAD(tb->L[0], n + item_pos - ret_val))) { + temp_l = + l_n + << + (tb-> + tb_sb-> + s_blocksize_bits + - + UNFM_P_SHIFT); + } + /* update key of first item in S0 */ + version = + ih_version + (B_N_PITEM_HEAD + (tbS0, 0)); + set_le_key_k_offset + (version, + B_N_PKEY + (tbS0, 0), + le_key_k_offset + (version, + B_N_PKEY + (tbS0, + 0)) + + temp_l); + /* update left delimiting key */ + set_le_key_k_offset + (version, + B_N_PDELIM_KEY + (tb-> + CFL[0], + tb-> + lkey[0]), + le_key_k_offset + (version, + B_N_PDELIM_KEY + (tb-> + CFL[0], + tb-> + lkey[0])) + + temp_l); + } + + /* Calculate new body, position in item and insert_size[0] */ + if (l_n > zeros_num) { + body += + (l_n - + zeros_num); + zeros_num = 0; + } else + zeros_num -= + l_n; + pos_in_item = 0; + + RFALSE + (comp_short_le_keys + (B_N_PKEY(tbS0, 0), + B_N_PKEY(tb->L[0], + B_NR_ITEMS + (tb-> + L[0]) - + 1)) + || + !op_is_left_mergeable + (B_N_PKEY(tbS0, 0), + tbS0->b_size) + || + !op_is_left_mergeable + (B_N_PDELIM_KEY + (tb->CFL[0], + tb->lkey[0]), + tbS0->b_size), + "PAP-12120: item must be merge-able with left neighboring item"); + } else { /* only part of the appended item will be in L[0] */ + + /* Calculate position in item for append in S[0] */ + pos_in_item -= + tb->lbytes; + + RFALSE(pos_in_item <= 0, + "PAP-12125: no place for paste. pos_in_item=%d", + pos_in_item); + + /* Shift lnum[0] - 1 items in whole. Shift lbytes - 1 byte from item number lnum[0] */ + leaf_shift_left(tb, + tb-> + lnum[0], + tb-> + lbytes); + } + } + } else { /* appended item will be in L[0] in whole */ + + struct item_head *pasted; + + if (!item_pos && op_is_left_mergeable(B_N_PKEY(tbS0, 0), tbS0->b_size)) { /* if we paste into first item of S[0] and it is left mergable |