This is the third in a set of 4 patches that split balance_leaf up into a group of functions rather than the 2500 beast it once was. This patch splits off the new node filling behavior. Signed-off-by: Jeff Mahoney <jeffm@xxxxxxxx> --- fs/reiserfs/do_balan.c | 693 +++++++++++++++++++++++-------------------------- 1 file changed, 338 insertions(+), 355 deletions(-) --- a/fs/reiserfs/do_balan.c 2007-06-11 14:49:42.000000000 -0400 +++ b/fs/reiserfs/do_balan.c 2007-06-11 14:50:00.000000000 -0400 @@ -873,6 +873,342 @@ bl_right(struct tree_balance *tb, struct item_pos, pos_in_item); } +static void +bl_new_nodes_insert(struct tree_balance *tb, struct item_head *ih, + const char *body, int flag, + struct item_head *insert_key, int *zeros_num, + int item_pos, int snum, int sbytes, + struct buffer_head *bh) +{ + struct buffer_head *tbS0 = PATH_PLAST_BUFFER(tb->tb_path); + int n = B_NR_ITEMS(tbS0); + struct buffer_info bi; + int old_key_comp, old_len, r_zeros_number; + const char *r_body; + int version; + + if (n - snum >= item_pos) { + /* new item or it part don't falls into bh */ + leaf_move_items(LEAF_FROM_S_TO_SNEW, tb, snum, sbytes, bh); + return; + } + + if (item_pos != n - snum + 1 || sbytes == -1) { + /* Shift snum - 1 items to bh (sbytes of split item) */ + leaf_move_items(LEAF_FROM_S_TO_SNEW, tb, snum - 1, + sbytes, bh); + + /* Insert new item into bh */ + buffer_info_init_bh(tb, &bi, bh); + leaf_insert_into_buf(&bi, item_pos - n + snum - 1, + ih, body, *zeros_num); + + *zeros_num = tb->insert_size[0] = 0; + return; + } + + /* new item or it's part falls to first new node bh */ + /* part of new item falls into bh */ + + /* Move snum-1 items from S[0] to bh */ + leaf_move_items(LEAF_FROM_S_TO_SNEW, tb, + snum - 1, -1, bh); + + /* Remember key component and item length */ + version = ih_version(ih); + old_key_comp = le_ih_k_offset(ih); + old_len = ih_item_len(ih); + + /* Calculate key component and item length to + * insert into bh */ + set_le_ih_k_offset(ih, le_ih_k_offset(ih) + + ((old_len - sbytes) << + (is_indirect_le_ih + (ih) ? tb->tb_sb->s_blocksize_bits - + UNFM_P_SHIFT : 0))); + + put_ih_item_len(ih, sbytes); + + /* Insert part of the item into bh before 0-th item */ + buffer_info_init_bh(tb, &bi, bh); + + if ((old_len - sbytes) > *zeros_num) { + r_zeros_number = 0; + r_body = body + (old_len - sbytes) - *zeros_num; + } else { + r_body = body; + r_zeros_number = *zeros_num - (old_len - sbytes); + *zeros_num -= r_zeros_number; + } + + leaf_insert_into_buf(&bi, 0, ih, r_body, r_zeros_number); + + /* Calculate key component and item length to + * insert into S[i] */ + set_le_ih_k_offset(ih, old_key_comp); + put_ih_item_len(ih, old_len - sbytes); + tb->insert_size[0] -= sbytes; +} + +static void +bl_new_nodes_paste_de_partial(struct tree_balance *tb, struct item_head *ih, + const char *body, int flag, + struct item_head *insert_key, + int *zeros_num, int item_pos, + int *pos_in_item, + int snum, int sbytes, struct buffer_head *bh) +{ + /* we append to directory item */ + struct buffer_head *tbS0 = PATH_PLAST_BUFFER(tb->tb_path); + int entry_count; + struct buffer_info bi; + struct item_head *aux_ih = B_N_PITEM_HEAD(tbS0, item_pos);; + + entry_count = ih_entry_count(aux_ih); + + /* new directory entry doesn't fall into bh */ + if (entry_count - sbytes >= *pos_in_item || + *pos_in_item > entry_count) { + leaf_move_items(LEAF_FROM_S_TO_SNEW, tb, + snum, sbytes, bh); + return; + } + + /* new directory entry falls into bh */ + RFALSE(!tb-> insert_size[0], + "PAP-12215: insert_size is already 0"); + RFALSE(sbytes - 1 >= entry_count, + "PAP-12220: there are no so much entries (%d), only %d", + sbytes - 1, entry_count); + + /* Shift snum-1 items in whole. Shift + * sbytes directory entries from directory + * item number snum */ + leaf_move_items(LEAF_FROM_S_TO_SNEW, + tb, snum, sbytes - 1, + bh); + /* Paste given directory entry to + * directory item */ + buffer_info_init_bh(tb, &bi, bh); + leaf_paste_in_buffer(&bi, 0, + *pos_in_item - entry_count + sbytes - 1, + tb->insert_size[0], body, *zeros_num); + /* paste new directory entry */ + leaf_paste_entries(bi.bi_bh, 0, + *pos_in_item - entry_count + + sbytes - 1, 1, + (struct reiserfs_de_head *) + body, body + DEH_SIZE, + tb->insert_size[0]); + tb->insert_size[0] = 0; + (*pos_in_item)++; +} + +static void +bl_new_nodes_paste_non_de_partial(struct tree_balance *tb, + struct item_head *ih, + const char *body, int flag, + struct item_head *insert_key, + int *zeros_num, int item_pos, + int *pos_in_item, int snum, int sbytes, + struct buffer_head *bh) +{ +#ifdef CONFIG_REISERFS_CHECK + struct buffer_head *tbS0 = PATH_PLAST_BUFFER(tb->tb_path); +#endif + int n_shift, n_rem, r_zeros_number; + const char *r_body; + struct item_head *tmp; + struct buffer_info bi; + + RFALSE(*pos_in_item != ih_item_len(B_N_PITEM_HEAD(tbS0, item_pos)) + || tb->insert_size[0] <= 0, + "PAP-12225", "item too short or insert_size <= 0"); + + /* Calculate number of bytes which must be shifted from appended item */ + n_shift = sbytes - tb->insert_size[0]; + if (n_shift < 0) + n_shift = 0; + leaf_move_items(LEAF_FROM_S_TO_SNEW, tb, snum, n_shift, bh); + + /* Calculate number of bytes which must remain + * in body after append to bh */ + n_rem = tb->insert_size[0] - sbytes; + if (n_rem < 0) + n_rem = 0; + + /* Append part of body into bh */ + buffer_info_init_bh(tb, &bi, bh); + + if (n_rem > *zeros_num) { + r_zeros_number = 0; + r_body = body + n_rem - *zeros_num; + } else { + r_body = body; + r_zeros_number = *zeros_num - n_rem; + *zeros_num -= r_zeros_number; + } + + leaf_paste_in_buffer(&bi, 0, n_shift, tb->insert_size[0] - n_rem, + r_body, r_zeros_number); + + tmp = B_N_PITEM_HEAD(bh, 0); + if (is_indirect_le_ih(tmp)) { + set_ih_free_space(tmp, 0); + set_le_ih_k_offset(tmp, le_ih_k_offset(tmp) + + (n_rem << (tb->tb_sb->s_blocksize_bits - UNFM_P_SHIFT))); + } else { + set_le_ih_k_offset(tmp, le_ih_k_offset(tmp) + n_rem); + } + + tb->insert_size[0] = n_rem; + if (!n_rem) + (*pos_in_item)++; +} + +static void +bl_new_nodes_paste_solid(struct tree_balance *tb, struct item_head *ih, + const char *body, int flag, + struct item_head *insert_key, + int *zeros_num, int item_pos, + int *pos_in_item, int snum, int sbytes, + struct buffer_head *bh) +{ + struct buffer_head *tbS0 = PATH_PLAST_BUFFER(tb->tb_path); + int n = B_NR_ITEMS(tbS0); + struct buffer_info bi; + struct item_head *pasted; + int was_copied; +#ifdef CONFIG_REISERFS_CHECK + struct item_head *aux_ih = B_N_PITEM_HEAD(tbS0, item_pos);; + + /* item falls wholly into bh */ + if (!is_direntry_le_ih(aux_ih) && (*pos_in_item != ih_item_len(aux_ih) + || tb->insert_size[0] <= 0)) + reiserfs_panic(tb->tb_sb, "PAP-12235", "pos_in_item must be " + "equal to ih_item_len"); +#endif + + was_copied = leaf_move_items(LEAF_FROM_S_TO_SNEW, tb, snum, + sbytes, bh); + + RFALSE(was_copied, "PAP-12240: unexpected value returned by " + "leaf_move_items (%d)", was_copied); + + /* paste into item */ + buffer_info_init_bh(tb, &bi, bh); + leaf_paste_in_buffer(&bi, item_pos - n + snum, *pos_in_item, + tb->insert_size[0], body, *zeros_num); + + pasted = B_N_PITEM_HEAD(bh, item_pos - n + snum); + if (is_direntry_le_ih(pasted)) { + leaf_paste_entries(bi.bi_bh, item_pos - n + snum, + *pos_in_item, 1, + (struct reiserfs_de_head *)body, + body + DEH_SIZE, tb->insert_size[0]); + } + + /* if we paste to indirect item update ih_free_space */ + if (is_indirect_le_ih(pasted)) + set_ih_free_space(pasted, 0); + *zeros_num = tb->insert_size[0] = 0; + +} + +static void +bl_new_nodes_paste(struct tree_balance *tb, struct item_head *ih, + const char *body, int flag, + struct item_head *insert_key, + int *zeros_num, int item_pos, + int *pos_in_item, int snum, int sbytes, + struct buffer_head *bh) +{ + struct buffer_head *tbS0 = PATH_PLAST_BUFFER(tb->tb_path); + int n = B_NR_ITEMS(tbS0); + struct item_head *aux_ih = B_N_PITEM_HEAD(tbS0, item_pos);; + + /* pasted item doesn't fall into bh */ + if (n - snum > item_pos) { + leaf_move_items(LEAF_FROM_S_TO_SNEW, tb, snum, sbytes, bh); + return; + } + /* pasted item or part if it falls to bh */ + /* we must shift part of the appended item */ + if (item_pos == n - snum && sbytes != -1) { + RFALSE(ih, "PAP-12210: ih must be 0"); + + if (is_direntry_le_ih(aux_ih)) + bl_new_nodes_paste_de_partial(tb, ih, body, flag, + insert_key, zeros_num, + item_pos, pos_in_item, + snum, sbytes, bh); + else + bl_new_nodes_paste_non_de_partial(tb, ih, body, flag, + insert_key, + zeros_num, item_pos, + pos_in_item, snum, + sbytes, bh); + } else { + bl_new_nodes_paste_solid(tb, ih, body, flag, insert_key, + zeros_num, item_pos, pos_in_item, + snum, sbytes, bh); + } +} + +/* @snum: number of items that will be placed into bh + * (includes partially shifted items) + * @sbytes: if an item is partially shifted into bh then + * if it is a directory item: + * it is the number of entries from the item that are + * shifted into bh + * else + * it is the number of bytes from the item that are + * shifted into bh + */ +static void +bl_new_nodes(struct tree_balance *tb, struct item_head *ih, + const char *body, int flag, + struct item_head *insert_key, + struct buffer_head **insert_ptr, int *zeros_num, + int item_pos, int *pos_in_item) +{ + int i; + + BUG_ON(flag != M_INSERT && flag != M_PASTE); + + /* Fill new nodes that appear in place of S[0] */ + for (i = tb->blknum[0] - 2; i >= 0; i--) { + struct buffer_head *bh; + RFALSE(!tb->snum[i], "PAP-12200: snum[%d] == %d. Must be > 0", + i, tb->snum[i]); + + /* Use new node since it won't fit in S */ + bh = get_FEB(tb); + + /* initialized block type and tree level */ + set_blkh_level(B_BLK_HEAD(bh), DISK_LEAF_NODE_LEVEL); + + if (flag == M_INSERT) + bl_new_nodes_insert(tb, ih, body, flag, + insert_key, zeros_num, + item_pos, tb->snum[i], + tb->sbytes[i], bh); + else + bl_new_nodes_paste(tb, ih, body, flag, + insert_key, zeros_num, + item_pos, pos_in_item, + tb->snum[i], + tb->sbytes[i], bh); + + memcpy(insert_key + i, B_N_PKEY(bh, 0), KEY_SIZE); + insert_ptr[i] = bh; + + RFALSE(!buffer_journaled(bh) + || buffer_journal_dirty(bh) + || buffer_dirty(bh), + "PAP-12247: bad state for new buffer : (%b)", bh); + } +} 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 */ @@ -889,8 +1225,6 @@ static int balance_leaf(struct tree_bala 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 n, i; int pos_in_item; int zeros_num; @@ -953,359 +1287,8 @@ static int balance_leaf(struct tree_bala return 0; } - /* Fill new nodes that appear in place of S[0] */ - for (i = tb->blknum[0] - 2; i >= 0; i--) { - - RFALSE(!tb->snum[i], "PAP-12200: tb->snum[%d] == %d. Must be > 0", i, - tb->snum[i]); - - /* here we shift from S to S_new nodes */ - - S_new[i] = get_FEB(tb); - - /* initialized block type and tree level */ - set_blkh_level(B_BLK_HEAD(S_new[i]), DISK_LEAF_NODE_LEVEL); - - n = B_NR_ITEMS(tbS0); - - switch (flag) { - case M_INSERT: /* insert item */ - - if (n - tb->snum[i] < item_pos) { /* new item or it's part falls to first new node S_new[i] */ - if (item_pos == n - tb->snum[i] + 1 && tb->sbytes[i] != -1) { /* part of new item falls into S_new[i] */ - int old_key_comp, old_len, - r_zeros_number; - const char *r_body; - int version; - - /* Move tb->snum[i]-1 items from S[0] to S_new[i] */ - leaf_move_items(LEAF_FROM_S_TO_SNEW, tb, - tb->snum[i] - 1, -1, - S_new[i]); - /* Remember key component and item length */ - version = ih_version(ih); - old_key_comp = le_ih_k_offset(ih); - old_len = ih_item_len(ih); - - /* Calculate key component and item length to insert into S_new[i] */ - set_le_ih_k_offset(ih, - le_ih_k_offset(ih) + - ((old_len - - tb->sbytes[i]) << - (is_indirect_le_ih - (ih) ? tb->tb_sb-> - s_blocksize_bits - - UNFM_P_SHIFT : - 0))); - - put_ih_item_len(ih, tb->sbytes[i]); - - /* Insert part of the item into S_new[i] before 0-th item */ - buffer_info_init_bh(tb, &bi, S_new[i]); - - if ((old_len - tb->sbytes[i]) > zeros_num) { - r_zeros_number = 0; - r_body = - body + (old_len - - tb->sbytes[i]) - - zeros_num; - } else { - r_body = body; - r_zeros_number = - zeros_num - (old_len - - tb->sbytes[i]); - zeros_num -= r_zeros_number; - } - - leaf_insert_into_buf(&bi, 0, ih, r_body, - r_zeros_number); - - /* Calculate key component and item length to insert into S[i] */ - set_le_ih_k_offset(ih, old_key_comp); - put_ih_item_len(ih, - old_len - tb->sbytes[i]); - tb->insert_size[0] -= tb->sbytes[i]; - } else { /* whole new item falls into S_new[i] */ - - /* Shift tb->snum[0] - 1 items to S_new[i] (tb->sbytes[i] of split item) */ - leaf_move_items(LEAF_FROM_S_TO_SNEW, tb, - tb->snum[i] - 1, tb->sbytes[i], - S_new[i]); - - /* Insert new item into S_new[i] */ - buffer_info_init_bh(tb, &bi, S_new[i]); - leaf_insert_into_buf(&bi, - item_pos - n + - tb->snum[i] - 1, ih, - body, zeros_num); - - zeros_num = tb->insert_size[0] = 0; - } - } - - else { /* new item or it part don't falls into S_new[i] */ - - leaf_move_items(LEAF_FROM_S_TO_SNEW, tb, - tb->snum[i], tb->sbytes[i], S_new[i]); - } - break; - - case M_PASTE: /* append item */ - - if (n - tb->snum[i] <= item_pos) { /* pasted item or part if it falls to S_new[i] */ - if (item_pos == n - tb->snum[i] && tb->sbytes[i] != -1) { /* we must shift part of the appended item */ - struct item_head *aux_ih; - - RFALSE(ih, "PAP-12210: ih must be 0"); - - if (is_direntry_le_ih - (aux_ih = - B_N_PITEM_HEAD(tbS0, item_pos))) { - /* we append to directory item */ - - int entry_count; - - entry_count = - ih_entry_count(aux_ih); - - if (entry_count - tb->sbytes[i] < - pos_in_item - && pos_in_item <= - entry_count) { - /* new directory entry falls into S_new[i] */ - - RFALSE(!tb-> - insert_size[0], - "PAP-12215: insert_size is already 0"); - RFALSE(tb->sbytes[i] - 1 >= - entry_count, - "PAP-12220: there are no so much entries (%d), only %d", - tb->sbytes[i] - 1, - entry_count); - - /* Shift tb->snum[i]-1 items in whole. Shift tb->sbytes[i] directory entries from directory item number tb->snum[i] */ - leaf_move_items - (LEAF_FROM_S_TO_SNEW, - tb, tb->snum[i], - tb->sbytes[i] - 1, - S_new[i]); - /* Paste given directory entry to directory item */ - buffer_info_init_bh(tb, &bi, S_new[i]); - leaf_paste_in_buffer - (&bi, 0, - pos_in_item - - entry_count + - tb->sbytes[i] - 1, - tb->insert_size[0], - body, zeros_num); - /* paste new directory entry */ - leaf_paste_entries(bi. - bi_bh, - 0, - pos_in_item - - - entry_count - + - tb->sbytes - [i] - - 1, 1, - (struct - reiserfs_de_head - *) - body, - body - + - DEH_SIZE, - tb-> - insert_size - [0] - ); - tb->insert_size[0] = 0; - pos_in_item++; - } else { /* new directory entry doesn't fall into S_new[i] */ - leaf_move_items - (LEAF_FROM_S_TO_SNEW, - tb, tb->snum[i], - tb->sbytes[i], - S_new[i]); - } - } else { /* regular object */ - - int n_shift, n_rem, - r_zeros_number; - const char *r_body; - - RFALSE(pos_in_item != - ih_item_len - (B_N_PITEM_HEAD - (tbS0, item_pos)) - || tb->insert_size[0] <= - 0, - "PAP-12225: item too short or insert_size <= 0"); - - /* Calculate number of bytes which must be shifted from appended item */ - n_shift = - tb->sbytes[i] - - tb->insert_size[0]; - if (n_shift < 0) - n_shift = 0; - leaf_move_items - (LEAF_FROM_S_TO_SNEW, tb, - tb->snum[i], n_shift, - S_new[i]); - - /* Calculate number of bytes which must remain in body after append to S_new[i] */ - n_rem = - tb->insert_size[0] - - tb->sbytes[i]; - if (n_rem < 0) - n_rem = 0; - /* Append part of body into S_new[0] */ - buffer_info_init_bh(tb, &bi, S_new[i]); - if (n_rem > zeros_num) { - r_zeros_number = 0; - r_body = - body + n_rem - - zeros_num; - } else { - r_body = body; - r_zeros_number = - zeros_num - n_rem; - zeros_num -= - r_zeros_number; - } - - leaf_paste_in_buffer(&bi, 0, - n_shift, - tb-> - insert_size - [0] - - n_rem, - r_body, - r_zeros_number); - { - struct item_head *tmp; - - tmp = - B_N_PITEM_HEAD(S_new - [i], - 0); - if (is_indirect_le_ih - (tmp)) { - set_ih_free_space - (tmp, 0); - set_le_ih_k_offset - (tmp, - le_ih_k_offset - (tmp) + - (n_rem << - (tb-> - tb_sb-> - s_blocksize_bits - - - UNFM_P_SHIFT))); - } else { - set_le_ih_k_offset - (tmp, - le_ih_k_offset - (tmp) + - n_rem); - } - } - - tb->insert_size[0] = n_rem; - if (!n_rem) - pos_in_item++; - } - } else - /* item falls wholly into S_new[i] */ - { - int ret_val; - struct item_head *pasted; - -#ifdef CONFIG_REISERFS_CHECK - struct item_head *ih = - B_N_PITEM_HEAD(tbS0, item_pos); - - if (!is_direntry_le_ih(ih) - && (pos_in_item != ih_item_len(ih) - || tb->insert_size[0] <= 0)) - reiserfs_panic(tb->tb_sb, - "PAP-12235", - "pos_in_item must be equal to ih_item_len"); -#endif /* CONFIG_REISERFS_CHECK */ - - ret_val = - leaf_move_items(LEAF_FROM_S_TO_SNEW, - tb, tb->snum[i], - tb->sbytes[i], - S_new[i]); - - RFALSE(ret_val, - "PAP-12240: unexpected value returned by leaf_move_items (%d)", - ret_val); - - /* paste into item */ - buffer_info_init_bh(tb, &bi, S_new[i]); - leaf_paste_in_buffer(&bi, - item_pos - n + - tb->snum[i], - pos_in_item, - tb->insert_size[0], - body, zeros_num); - - pasted = - B_N_PITEM_HEAD(S_new[i], - item_pos - n + - tb->snum[i]); - if (is_direntry_le_ih(pasted)) { - leaf_paste_entries(bi.bi_bh, - item_pos - - n + tb->snum[i], - pos_in_item, - 1, - (struct - reiserfs_de_head - *)body, - body + - DEH_SIZE, - tb-> - insert_size - [0] - ); - } - - /* if we paste to indirect item update ih_free_space */ - if (is_indirect_le_ih(pasted)) - set_ih_free_space(pasted, 0); - zeros_num = tb->insert_size[0] = 0; - } - } - - else { /* pasted item doesn't fall into S_new[i] */ - - leaf_move_items(LEAF_FROM_S_TO_SNEW, tb, - tb->snum[i], tb->sbytes[i], S_new[i]); - } - break; - default: /* cases d and t */ - reiserfs_panic(tb->tb_sb, "PAP-12245", - "blknum > 2: unexpected mode: %s(%d)", - (flag == - M_DELETE) ? "DELETE" : ((flag == - M_CUT) ? "CUT" - : "UNKNOWN"), - flag); - } - - memcpy(insert_key + i, B_N_PKEY(S_new[i], 0), KEY_SIZE); - insert_ptr[i] = S_new[i]; - - RFALSE(!buffer_journaled(S_new[i]) - || buffer_journal_dirty(S_new[i]) - || buffer_dirty(S_new[i]), "PAP-12247: S_new[%d] : (%b)", - i, S_new[i]); - } + bl_new_nodes(tb, ih, body, flag, insert_key, insert_ptr, + &zeros_num, item_pos, &pos_in_item); /* if the affected item was not wholly shifted then we perform all necessary operations on that part or whole of the affected item which remains in S */ -- Jeff Mahoney SUSE Labs - To unsubscribe from this list: send the line "unsubscribe reiserfs-devel" in the body of a message to majordomo@xxxxxxxxxxxxxxx More majordomo info at http://vger.kernel.org/majordomo-info.html