This is the second 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 right-tree balancing behavior.
Signed-off-by: Jeff Mahoney <jeffm@xxxxxxxx>
---
fs/reiserfs/do_balan.c | 671 +++++++++++++++++++++----------------------------
1 file changed, 290 insertions(+), 381 deletions(-)
--- a/fs/reiserfs/do_balan.c 2007-05-30 17:54:43.000000000 -0400
+++ b/fs/reiserfs/do_balan.c 2007-05-30 17:55:02.000000000 -0400
@@ -587,6 +587,293 @@ balance_leaf_left(struct tree_balance *t
pos_in_item);
}
+static void
+balance_leaf_right_insert(struct tree_balance *tb, struct item_head *ih,
+ const char *body, int flag, int *zeros_num,
+ int item_pos)
+{
+ loff_t old_key_comp, old_len, r_zeros_number;
+ const char *r_body;
+ loff_t offset;
+ struct buffer_head *tbS0 = PATH_PLAST_BUFFER(tb->tb_path);
+ int n = B_NR_ITEMS(tbS0);
+ struct buffer_info bi;
+
+ /* Doesn't fall into R[0] */
+ if (n - tb->rnum[0] >= item_pos) {
+ leaf_shift_right(tb, tb->rnum[0], tb->rbytes);
+ return;
+ }
+
+ /* whole new item falls into R[0] */
+ if (item_pos != n - tb->rnum[0] + 1 || tb->rbytes == -1) {
+ /* Shift rnum[0]-1 items to R[0] */
+ leaf_shift_right(tb, tb->rnum[0] - 1, tb->rbytes);
+
+ /* Insert new item into R[0] */
+ buffer_info_init_right(tb, &bi);
+ leaf_insert_into_buf(&bi, item_pos - n + tb->rnum[0] - 1,
+ ih, body, *zeros_num);
+
+ if (item_pos - n + tb->rnum[0] - 1 == 0)
+ replace_key(tb, tb->CFR[0], tb->rkey[0], tb->R[0], 0);
+ *zeros_num = tb->insert_size[0] = 0;
+ return;
+ }
+
+ /* Only part of item falls into R[0] */
+
+ leaf_shift_right(tb, tb->rnum[0] - 1, -1);
+
+ /* Remember key component and item length */
+ old_key_comp = le_ih_k_offset(ih);
+ old_len = ih_item_len(ih);
+
+ /* Calculate key component and item length to insert into R[0] */
+ offset = le_ih_k_offset(ih) +
+ ((old_len - tb->rbytes) << (is_indirect_le_ih(ih)
+ ? tb->tb_sb->
+ s_blocksize_bits -
+ UNFM_P_SHIFT : 0));
+ set_le_ih_k_offset(ih, offset);
+ put_ih_item_len(ih, tb->rbytes);
+ /* Insert part of the item into R[0] */
+ buffer_info_init_right(tb, &bi);
+ if ((old_len - tb->rbytes) > *zeros_num) {
+ r_zeros_number = 0;
+ r_body = body + (old_len - tb->rbytes) - *zeros_num;
+ } else {
+ r_body = body;
+ r_zeros_number = *zeros_num - (old_len - tb->rbytes);
+ *zeros_num -= r_zeros_number;
+ }
+
+ leaf_insert_into_buf(&bi, 0, ih, r_body, r_zeros_number);
+
+ /* Replace right delimiting key by first key in R[0] */
+ replace_key(tb, tb->CFR[0], tb->rkey[0], tb->R[0], 0);
+
+ /* Calculate key component and item length to insert into S[0] */
+ set_le_ih_k_offset(ih, old_key_comp);
+ put_ih_item_len(ih, old_len - tb->rbytes);
+
+ tb->insert_size[0] -= tb->rbytes;
+}
+
+static void
+bl_right_paste_de_partial(struct tree_balance *tb, struct item_head *ih,
+ const char *body, int flag, int *zeros_num,
+ int item_pos, int *pos_in_item)
+{
+ struct buffer_head *tbS0 = PATH_PLAST_BUFFER(tb->tb_path);
+ struct buffer_info bi;
+ int paste_entry_position;
+ int entry_count;
+
+ RFALSE(*zeros_num, "PAP-12145: invalid parameter "
+ "in case of a directory");
+ entry_count = I_ENTRY_COUNT(B_N_PITEM_HEAD(tbS0,
+ item_pos));
+
+ if (entry_count - tb->rbytes >= *pos_in_item) {
+ leaf_shift_right(tb, tb->rnum[0], tb->rbytes);
+ return;
+ }
+
+ /* new directory entry falls into R[0] */
+ RFALSE(tb->rbytes - 1 >= entry_count
+ || !tb-> insert_size[0], "PAP-12150: no enough of entries "
+ "to shift to R[0]: rbytes=%d, entry_count=%d",
+ tb->rbytes, entry_count);
+
+ /* Shift rnum[0]-1 items in whole.
+ * Shift rbytes-1 directory entries from
+ * directory item number rnum[0] */
+ leaf_shift_right(tb, tb->rnum[0], tb->rbytes - 1);
+
+ /* Paste given directory entry to
+ * directory item */
+ paste_entry_position = *pos_in_item - entry_count + tb->rbytes - 1;
+ buffer_info_init_right(tb, &bi);
+ leaf_paste_in_buffer(&bi, 0, paste_entry_position, tb->insert_size[0],
+ body, *zeros_num);
+ /* paste entry */
+ leaf_paste_entries(bi.bi_bh, 0, paste_entry_position, 1,
+ (struct reiserfs_de_head *) body, body + DEH_SIZE,
+ tb->insert_size[0]);
+
+ /* change delimiting keys */
+ if (paste_entry_position == 0)
+ replace_key(tb, tb->CFR[0], tb->rkey[0], tb->R[0], 0);
+
+ tb->insert_size[0] = 0;
+ (*pos_in_item)++;
+}
+
+static void
+bl_right_paste_non_de_partial(struct tree_balance *tb, struct item_head *ih,
+ const char *body, int flag, int *zeros_num,
+ int item_pos, int *pos_in_item)
+{
+
+#ifdef CONFIG_REISERFS_CHECK
+ struct buffer_head *tbS0 = PATH_PLAST_BUFFER(tb->tb_path);
+#endif
+ struct buffer_info bi;
+ int n_shift, n_rem, r_zeros_number;
+ const char *r_body;
+ int version;
+ unsigned long temp_rem;
+ u64 offset;
+
+ /* Calculate number of bytes which must be
+ * shifted from appended item */
+ if ((n_shift = tb->rbytes - tb->insert_size[0]) < 0)
+ n_shift = 0;
+
+ RFALSE(*pos_in_item !=
+ ih_item_len(B_N_PITEM_HEAD(tbS0, item_pos)),
+ "PAP-12155: invalid position to paste. "
+ "ih_item_len=%d, pos_in_item=%d", *pos_in_item,
+ ih_item_len(B_N_PITEM_HEAD(tbS0, item_pos)));
+
+ leaf_shift_right(tb, tb->rnum[0], n_shift);
+ /* Calculate number of bytes which must remain
+ * in body after appending to R[0] */
+ if ((n_rem = tb->insert_size[0] - tb->rbytes) < 0)
+ n_rem = 0;
+
+ temp_rem = n_rem;
+ version = ih_version(B_N_PITEM_HEAD(tb->R[0], 0));
+ if (is_indirect_le_key(version, B_N_PKEY(tb->R[0], 0))) {
+ temp_rem = n_rem << (tb->tb_sb->s_blocksize_bits -
+ UNFM_P_SHIFT);
+ }
+ offset = le_key_k_offset(version, B_N_PKEY(tb->R[0], 0));
+ set_le_key_k_offset(version, B_N_PKEY(tb->R[0], 0), offset + temp_rem);
+
+ offset = le_key_k_offset (version,
+ B_N_PDELIM_KEY(tb->CFR[0], tb->rkey[0]));
+ set_le_key_k_offset(version, B_N_PDELIM_KEY(tb->CFR[0], tb->rkey[0]),
+ offset + temp_rem);
+ do_balance_mark_internal_dirty(tb, tb->CFR[0], 0);
+
+ /* Append part of body into R[0] */
+ buffer_info_init_right(tb, &bi);
+ 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);
+
+ if (is_indirect_le_ih(B_N_PITEM_HEAD(tb->R[0], 0)))
+ set_ih_free_space(B_N_PITEM_HEAD(tb->R[0], 0), 0);
+
+ tb->insert_size[0] = n_rem;
+ if (!n_rem)
+ (*pos_in_item)++;
+}
+
+static void
+bl_right_paste_solid(struct tree_balance *tb, struct item_head *ih,
+ const char *body, int flag, int *zeros_num,
+ int item_pos, int *pos_in_item)
+{
+ struct item_head *pasted;
+ struct buffer_head *tbS0 = PATH_PLAST_BUFFER(tb->tb_path);
+ int n = B_NR_ITEMS(tbS0);
+ struct buffer_info bi;
+
+ /* pasted item in whole falls into R[0] */
+ leaf_shift_right(tb, tb->rnum[0], tb->rbytes);
+ /* append item in R[0] */
+ if (*pos_in_item >= 0) {
+ buffer_info_init_right(tb, &bi);
+ leaf_paste_in_buffer(&bi,
+ item_pos - n + tb->rnum[0],
+ *pos_in_item,
+ tb->insert_size[0], body,
+ *zeros_num);
+ }
+
+ /* paste new entry, if item is directory item */
+ pasted = B_N_PITEM_HEAD(tb->R[0], item_pos - n + tb->rnum[0]);
+ if (is_direntry_le_ih(pasted) && *pos_in_item >= 0) {
+ leaf_paste_entries(bi.bi_bh, item_pos - n + tb->rnum[0],
+ *pos_in_item, 1,
+ (struct reiserfs_de_head *)body,
+ body + DEH_SIZE, tb->insert_size[0]);
+
+ if (!*pos_in_item) {
+ RFALSE(item_pos - n + tb->rnum[0],
+ "PAP-12165: directory item must be "
+ "first item of node when pasting is "
+ "in 0th position");
+
+ /* update delimiting keys */
+ replace_key(tb, tb->CFR[0], tb->rkey[0],
+ tb->R[0], 0);
+ }
+ }
+
+ if (is_indirect_le_ih(pasted))
+ set_ih_free_space(pasted, 0);
+ *zeros_num = tb->insert_size[0] = 0;
+
+}
+
+static void
+balance_leaf_right_paste(struct tree_balance *tb,
+ struct item_head *ih, const char *body, int flag,
+ int *zeros_num, int item_pos, int *pos_in_item)
+{
+ struct buffer_head *tbS0 = PATH_PLAST_BUFFER(tb->tb_path);
+ int n = B_NR_ITEMS(tbS0);
+
+ if (n - tb->rnum[0] > item_pos) {
+ leaf_shift_right(tb, tb->rnum[0], tb->rbytes);
+ return;
+ }
+ /* pasted item or part of it falls to R[0] */
+ /* we must shift the part of the appended item */
+ if (item_pos == n - tb->rnum[0] && tb->rbytes != -1) {
+ if (is_direntry_le_ih(B_N_PITEM_HEAD(tbS0, item_pos)))
+ bl_right_paste_de_partial(tb, ih, body, flag,
+ zeros_num, item_pos,
+ pos_in_item);
+ else
+ bl_right_paste_non_de_partial(tb, ih, body, flag,
+ zeros_num, item_pos,
+ pos_in_item);
+ } else {
+ bl_right_paste_solid(tb, ih, body, flag, zeros_num, item_pos,
+ pos_in_item);
+ }
+}
+
+static void
+balance_leaf_right(struct tree_balance *tb, struct item_head *ih,
+ const char *body, int flag, int *zeros_num, int item_pos,
+ int *pos_in_item)
+{
+ BUG_ON(flag != M_INSERT && flag != M_PASTE);
+
+ /* shift rnum[0] items from S[0] to the right neighbor R[0] */
+ if (flag == M_INSERT)
+ balance_leaf_right_insert(tb, ih, body, flag, zeros_num,
+ item_pos);
+ else
+ balance_leaf_right_paste(tb, ih, body, flag, zeros_num,
+ item_pos, pos_in_item);
+}
+
+
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
@@ -604,7 +891,6 @@ static int balance_leaf(struct tree_bala
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 ret_val;
int pos_in_item;
int zeros_num;
@@ -632,386 +918,9 @@ static int balance_leaf(struct tree_bala
/* Calculate new item position */
item_pos -= (tb->lnum[0] - ((tb->lbytes != -1) ? 1 : 0));
- if (tb->rnum[0] > 0) {
- /* shift rnum[0] items from S[0] to the right neighbor R[0] */
- n = B_NR_ITEMS(tbS0);
- switch (flag) {
-
- case M_INSERT: /* insert item */
- if (n - tb->rnum[0] < item_pos) { /* new item or its part falls to R[0] */
- if (item_pos == n - tb->rnum[0] + 1 && tb->rbytes != -1) { /* part of new item falls into R[0] */
- loff_t old_key_comp, old_len,
- r_zeros_number;
- const char *r_body;
- int version;
- loff_t offset;
-
- leaf_shift_right(tb, tb->rnum[0] - 1,
- -1);
-
- version = ih_version(ih);
- /* Remember key component and item length */
- old_key_comp = le_ih_k_offset(ih);
- old_len = ih_item_len(ih);
-
- /* Calculate key component and item length to insert into R[0] */
- offset =
- le_ih_k_offset(ih) +
- ((old_len -
- tb->
- rbytes) << (is_indirect_le_ih(ih)
- ? tb->tb_sb->
- s_blocksize_bits -
- UNFM_P_SHIFT : 0));
- set_le_ih_k_offset(ih, offset);
- put_ih_item_len(ih, tb->rbytes);
- /* Insert part of the item into R[0] */
- buffer_info_init_right(tb, &bi);
- if ((old_len - tb->rbytes) > zeros_num) {
- r_zeros_number = 0;
- r_body =
- body + (old_len -
- tb->rbytes) -
- zeros_num;
- } else {
- r_body = body;
- r_zeros_number =
- zeros_num - (old_len -
- tb->rbytes);
- zeros_num -= r_zeros_number;
- }
-
- leaf_insert_into_buf(&bi, 0, ih, r_body,
- r_zeros_number);
-
- /* Replace right delimiting key by first key in R[0] */
- replace_key(tb, tb->CFR[0], tb->rkey[0],
- tb->R[0], 0);
-
- /* Calculate key component and item length to insert into S[0] */
- set_le_ih_k_offset(ih, old_key_comp);
- put_ih_item_len(ih,
- old_len - tb->rbytes);
-
- tb->insert_size[0] -= tb->rbytes;
-
- } else { /* whole new item falls into R[0] */
-
- /* Shift rnum[0]-1 items to R[0] */
- ret_val =
- leaf_shift_right(tb,
- tb->rnum[0] - 1,
- tb->rbytes);
- /* Insert new item into R[0] */
- buffer_info_init_right(tb, &bi);
- leaf_insert_into_buf(&bi,
- item_pos - n +
- tb->rnum[0] - 1,
- ih, body,
- zeros_num);
-
- if (item_pos - n + tb->rnum[0] - 1 == 0) {
- replace_key(tb, tb->CFR[0],
- tb->rkey[0],
- tb->R[0], 0);
-
- }
- zeros_num = tb->insert_size[0] = 0;
- }
- } else { /* new item or part of it doesn't fall into R[0] */
-
- leaf_shift_right(tb, tb->rnum[0], tb->rbytes);
- }
- break;
-
- case M_PASTE: /* append item */
-
- if (n - tb->rnum[0] <= item_pos) { /* pasted item or part of it falls to R[0] */
- if (item_pos == n - tb->rnum[0] && tb->rbytes != -1) { /* we must shift the part of the appended item */
- if (is_direntry_le_ih(B_N_PITEM_HEAD(tbS0, item_pos))) { /* we append to directory item */
- int entry_count;
-
- RFALSE(zeros_num,
- "PAP-12145: invalid parameter in case of a directory");
- entry_count =
- I_ENTRY_COUNT(B_N_PITEM_HEAD
- (tbS0,
- item_pos));
- if (entry_count - tb->rbytes <
- pos_in_item)
- /* new directory entry falls into R[0] */
- {
- int paste_entry_position;
-
- RFALSE(tb->rbytes - 1 >=
- entry_count
- || !tb->
- insert_size[0],
- "PAP-12150: no enough of entries to shift to R[0]: rbytes=%d, entry_count=%d",
- tb->rbytes,
- entry_count);
- /* Shift rnum[0]-1 items in whole. Shift rbytes-1 directory entries from directory item number rnum[0] */
- leaf_shift_right(tb,
- tb->
- rnum
- [0],
- tb->
- rbytes
- - 1);
- /* Paste given directory entry to directory item */
- paste_entry_position =
- pos_in_item -
- entry_count +
- tb->rbytes - 1;
- buffer_info_init_right(tb, &bi);
- leaf_paste_in_buffer
- (&bi, 0,
- paste_entry_position,
- tb->insert_size[0],
- body, zeros_num);
- /* paste entry */
- leaf_paste_entries(bi.
- bi_bh,
- 0,
- paste_entry_position,
- 1,
- (struct
- reiserfs_de_head
- *)
- body,
- body
- +
- DEH_SIZE,
- tb->
- insert_size
- [0]
- );
-
- if (paste_entry_position
- == 0) {
- /* change delimiting keys */
- replace_key(tb,
- tb->
- CFR
- [0],
- tb->
- rkey
- [0],
- tb->
- R
- [0],
- 0);
- }
-
- tb->insert_size[0] = 0;
- pos_in_item++;
- } else { /* new directory entry doesn't fall into R[0] */
-
- leaf_shift_right(tb,
- tb->
- rnum
- [0],
- tb->
- rbytes);
- }
- } else { /* regular object */
-
- int n_shift, n_rem,
- r_zeros_number;
- const char *r_body;
-
- /* Calculate number of bytes which must be shifted from appended item */
- if ((n_shift =
- tb->rbytes -
- tb->insert_size[0]) < 0)
- n_shift = 0;
-
- RFALSE(pos_in_item !=
- ih_item_len
- (B_N_PITEM_HEAD
- (tbS0, item_pos)),
- "PAP-12155: invalid position to paste. ih_item_len=%d, pos_in_item=%d",
- pos_in_item,
- ih_item_len
- (B_N_PITEM_HEAD
- (tbS0, item_pos)));
-
- leaf_shift_right(tb,
- tb->rnum[0],
- n_shift);
- /* Calculate number of bytes which must remain in body after appending to R[0] */
- if ((n_rem =
- tb->insert_size[0] -
- tb->rbytes) < 0)
- n_rem = 0;
-
- {
- int version;
- unsigned long temp_rem =
- n_rem;
-
- version =
- ih_version
- (B_N_PITEM_HEAD
- (tb->R[0], 0));
- if (is_indirect_le_key
- (version,
- B_N_PKEY(tb->R[0],
- 0))) {
- temp_rem =
- n_rem <<
- (tb->tb_sb->
- s_blocksize_bits
- -
- UNFM_P_SHIFT);
- }
- set_le_key_k_offset
- (version,
- B_N_PKEY(tb->R[0],
- 0),
- le_key_k_offset
- (version,
- B_N_PKEY(tb->R[0],
- 0)) +
- temp_rem);
- set_le_key_k_offset
- (version,
- B_N_PDELIM_KEY(tb->
- CFR
- [0],
- tb->
- rkey
- [0]),
- le_key_k_offset
- (version,
- B_N_PDELIM_KEY
- (tb->CFR[0],
- tb->rkey[0])) +
- temp_rem);
- }
-/* k_offset (B_N_PKEY(tb->R[0],0)) += n_rem;
- k_offset (B_N_PDELIM_KEY(tb->CFR[0],tb->rkey[0])) += n_rem;*/
- do_balance_mark_internal_dirty
- (tb, tb->CFR[0], 0);
-
- /* Append part of body into R[0] */
- buffer_info_init_right(tb, &bi);
- 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);
-
- if (is_indirect_le_ih
- (B_N_PITEM_HEAD
- (tb->R[0], 0))) {
-#if 0
- RFALSE(n_rem,
- "PAP-12160: paste more than one unformatted node pointer");
-#endif
- set_ih_free_space
- (B_N_PITEM_HEAD
- (tb->R[0], 0), 0);
- }
- tb->insert_size[0] = n_rem;
- if (!n_rem)
- pos_in_item++;
- }
- } else { /* pasted item in whole falls into R[0] */
-
- struct item_head *pasted;
-
- ret_val =
- leaf_shift_right(tb, tb->rnum[0],
- tb->rbytes);
- /* append item in R[0] */
- if (pos_in_item >= 0) {
- buffer_info_init_right(tb, &bi);
- leaf_paste_in_buffer(&bi,
- item_pos -
- n +
- tb->
- rnum[0],
- pos_in_item,
- tb->
- insert_size
- [0], body,
- zeros_num);
- }
-
- /* paste new entry, if item is directory item */
- pasted =
- B_N_PITEM_HEAD(tb->R[0],
- item_pos - n +
- tb->rnum[0]);
- if (is_direntry_le_ih(pasted)
- && pos_in_item >= 0) {
- leaf_paste_entries(bi.bi_bh,
- item_pos -
- n +
- tb->rnum[0],
- pos_in_item,
- 1,
- (struct
- reiserfs_de_head
- *)body,
- body +
- DEH_SIZE,
- tb->
- insert_size
- [0]
- );
- if (!pos_in_item) {
-
- RFALSE(item_pos - n +
- tb->rnum[0],
- "PAP-12165: directory item must be first item of node when pasting is in 0th position");
-
- /* update delimiting keys */
- replace_key(tb,
- tb->CFR[0],
- tb->rkey[0],
- tb->R[0],
- 0);
- }
- }
-
- if (is_indirect_le_ih(pasted))
- set_ih_free_space(pasted, 0);
- zeros_num = tb->insert_size[0] = 0;
- }
- } else { /* new item doesn't fall into R[0] */
-
- leaf_shift_right(tb, tb->rnum[0], tb->rbytes);
- }
- break;
- default: /* cases d and t */
- reiserfs_panic(tb->tb_sb, "PAP-12175",
- "rnum > 0: unexpected mode: %s(%d)",
- (flag ==
- M_DELETE) ? "DELETE" : ((flag ==
- M_CUT) ? "CUT"
- : "UNKNOWN"),
- flag);
- }
-
- }
+ if (tb->rnum[0] > 0)
+ balance_leaf_right(tb, ih, body, flag, &zeros_num, item_pos,
+ &pos_in_item);
/* tb->rnum[0] > 0 */
RFALSE(tb->blknum[0] > 3,
--
-
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
