Two b-tree bug fixes.
cover Two b-tree bug fixes.
Hi Mark/Joel,
These are 2 bug fix for b-tree. Please review.
I have sent out the first one last week, but it was based on cacheme.
So resend it. Now it bases on joel's fixes branch.
The second one is another b-tree rotation bug. I guess the reason why
we never meet with it is that no one has ever used b-tree like reflink before. ;)
Regards,
Tao
PATCH 1/2 ocfs2: Add extra credits and access the modified bh in update_edge_lengths.
In normal tree rotation left process, we will never touch the tree branch above subtree_index and ocfs2_extend_rotate_transaction doesn't reserve the credits for them either.
But when we want to delete the rightmost extent block, we have to update the rightmost records for all the rightmost branch(See ocfs2_update_edge_lengths), so we have to allocate extra credits for them. What's more, we have to access them also.
--- fs/ocfs2/alloc.c | 44 +++++++++++++++++++++++++++++++++++++++----- 1 files changed, 39 insertions(+), 5 deletions(-)
fs/ocfs2/alloc.c +39 -5
@@ -2476,15 +2476,37 @@ out_ret_path:return ret; } -static void ocfs2_update_edge_lengths (struct inode *inode,handle_t *handle, -struct ocfs2_path *path) +static int ocfs2_update_edge_lengths (struct inode *inode,handle_t *handle, +int subtree_index,struct ocfs2_path *path) { -int i, idx; +int i, idx, ret;struct ocfs2_extent_rec *rec;struct ocfs2_extent_list *el;struct ocfs2_extent_block *eb;u32 range; +/* +* In normal tree rotation process, we will never touch the +* tree branch above subtree_index and ocfs2_extend_rotate_transaction +* doesn't reserve the credits for them either. +* +* But we do have a special case here which will update the rightmost +* records for all the bh in the path. +* So we have to allocate extra credits and access them. +*/ + ret =ocfs2_extend_trans (handle, + handle->h_buffer_credits + subtree_index); +if (ret) { +mlog_errno (ret); + goto out; + } + + ret =ocfs2_journal_access_path (inode, handle, path); +if (ret) { +mlog_errno (ret); + goto out; + } +/* Path should always be rightmost. */ eb = (struct ocfs2_extent_block *)path_leaf_bh (path)->b_data;BUG_ON (eb->h_next_leaf_blk !=0ULL );
@@ -2505,6 +2527,8 @@ static void ocfs2_update_edge_lengths(struct inode *inode, handle_t *handle,ocfs2_journal_dirty (handle, path->p_node[i].bh); } +out: +return ret; } static void ocfs2_unlink_path(struct inode *inode, handle_t *handle,
@@ -2717,7 +2741,12 @@ static int ocfs2_rotate_subtree_left(struct inode *inode, handle_t *handle,if (del_right_subtree) {ocfs2_unlink_subtree (inode, handle, left_path, right_path, subtree_index, dealloc); -ocfs2_update_edge_lengths (inode, handle, left_path); + ret =ocfs2_update_edge_lengths (inode, handle, subtree_index, + left_path); +if (ret) { +mlog_errno (ret); + goto out; + } eb = (struct ocfs2_extent_block *)path_leaf_bh (left_path)->b_data;ocfs2_et_set_last_eb_blk (et,le64_to_cpu (eb->h_blkno));
@@ -3034,7 +3063,12 @@ static int ocfs2_remove_rightmost_path(struct inode *inode, handle_t *handle,ocfs2_unlink_subtree (inode, handle, left_path, path, subtree_index, dealloc); -ocfs2_update_edge_lengths (inode, handle, left_path); + ret =ocfs2_update_edge_lengths (inode, handle, subtree_index, + left_path); +if (ret) { +mlog_errno (ret); + goto out; + } eb = (struct ocfs2_extent_block *)path_leaf_bh (left_path)->b_data;ocfs2_et_set_last_eb_blk (et,le64_to_cpu (eb->h_blkno));
Signature · 1 line
1.6.2.rc2.16.gf474c
PATCH 1/2 ocfs2: Add extra credits and access the modified bh in update_edge_lengths.
Quoted 10 lines · Tao Ma
In normal tree rotation left process, we will never touch the tree branch above
subtree_indexandocfs2_extend_rotate_transactiondoesn't reserve the credits for them either.But when we want to delete the rightmost extent block, we have to update the rightmost records for all the rightmost
branch(See ocfs2_update_edge_lengths), so we have to allocate extra credits for them. What's more, we have to access them also.Signed-off-by Tao Ma <[email protected]>
This patch is now in the fixes branch of ocfs2.git.
Joel
Signature · 8 lines
"Hey mister if you're gonna walk on water, Could you drop a line my way?" Joel Becker Principal Software Developer Oracle E-mail: joel.becker at oracle.com Phone: (650) 506-8127
PATCH 2/2 ocfs2: Use ocfs2_rec_clusters in ocfs2_adjust_adjacent_records.
In reply to Tao MaIn ocfs2_adjust_adjacent_records, we will adjust adjacent records according to the extent_list in the lower level. But actually the lower level tree will either be a leaf or a branch. So we shouldn't use ocfs2_is_empty_extent which is only valid for a tree leaf. Use ocfs2_rec_clusters instead. We will meet with some problem when the tree depth > 2.
--- fs/ocfs2/alloc.c | 2 +- 1 files changed, 1 insertions(+), 1 deletions(-)
fs/ocfs2/alloc.c +1 -1
@@ -1914,7 +1914,7 @@ static void ocfs2_adjust_adjacent_records(struct ocfs2_extent_rec *left_rec,* immediately to their right. */ left_clusters =le32_to_cpu (right_child_el->l_recs[0 ].e_cpos); -if (ocfs2_is_empty_extent (&right_child_el->l_recs[0 ])) { +if (!ocfs2_rec_clusters (right_child_el, &right_child_el->l_recs[0 ])) {BUG_ON (le16_to_cpu (right_child_el->l_next_free_rec) <=1 ); left_clusters =le32_to_cpu (right_child_el->l_recs[1 ].e_cpos); }
Signature · 1 line
1.6.2.rc2.16.gf474c
PATCH 2/2 ocfs2: Use ocfs2_rec_clusters in ocfs2_adjust_adjacent_records.
Quoted 6 lines · Tao Ma
In
ocfs2_adjust_adjacent_records, we will adjust adjacent records according to theextent_listin the lower level. But actually the lower level tree will either be a leaf or a branch. So we shouldn't useocfs2_is_empty_extentwhich is only valid for a tree leaf. Useocfs2_rec_clustersinstead. We will meet with some problem when the tree depth > 2.
I think you mean "if we leave it as checking e_leaf_clusters,
we'll have a problem rotating trees with depth > 2". Is that right? Can interior nodes have these empty l_rec[0]s? If they can't, perhaps we should be bugging?
Joel
Signature · 9 lines
Life's Little Instruction Book #24 "Drink champagne for no reason at all." Joel Becker Principal Software Developer Oracle E-mail: joel.becker at oracle.com Phone: (650) 506-8127
PATCH 2/2 ocfs2: Use ocfs2_rec_clusters in ocfs2_adjust_adjacent_records.
Quoted 10 lines · Joel Becker
Quoted 7 lines · Tao Ma
In
ocfs2_adjust_adjacent_records, we will adjust adjacent records according to theextent_listin the lower level. But actually the lower level tree will either be a leaf or a branch. So we shouldn't useocfs2_is_empty_extentwhich is only valid for a tree leaf. Useocfs2_rec_clustersinstead. We will meet with some problem when the tree depth > 2.
Quoted 5 lines
I think you mean "if we leave it as checking
e_leaf_clusters,
we'll have a problem rotating trees with depth > 2". Is that right? Can interior nodes have these empty l_rec[0]s? If they can't, perhaps we should be bugging?
sorry, It should be tree_depth >=2.
ocfs2_adjust_adjacent_records is used to for rotation. And it only use e_cpos in most cases.
So we don't have a problem if the lower 16 bits of e_int_clusters isn't equal to 0 for a branch.
But if the low 16 bits are 0, this ocfs2_is_empty_extent will treat it as an empty record and use the l_recs[1] which will corrupt the tree. So let me give you a test case I meet.
Tree Depth: 2 Count: 23 Next Free Rec: 2
## Offset Clusters Block#
0 0 9107457 28721
1 9107457 1922049 28728
Tree Depth: 1 Count: 28 Next Free Rec: 28
## Offset Clusters Block#
0 0 227105 28698
1 227105 197405 28699
...
26 8372225 542208 28725
27 8914433 193024 28726Tree Depth: 1 Count: 28 Next Free Rec: 10
## Offset Clusters Block#
0 9107457 196608 28727
1 9304065 204544 28729In this case: 196608=0x30000, so if we use ocfs2_is_empty_extent will treat it as 0, and use 9394065.
Regards,
Tao
PATCH 2/2 ocfs2: Use ocfs2_rec_clusters in ocfs2_adjust_adjacent_records.
Quoted 15 lines · Tao Ma
Quoted 8 lines · Joel Becker
Quoted 6 lines · Tao Ma
In
ocfs2_adjust_adjacent_records, we will adjust adjacent records according to theextent_listin the lower level. But actually the lower level tree will either be a leaf or a branch. So we shouldn't useocfs2_is_empty_extentwhich is only valid for a tree leaf. Useocfs2_rec_clustersinstead. We will meet with some problem when the tree depth > 2.Quoted 4 lines
I think you mean "if we leave it as checking
e_leaf_clusters,
we'll have a problem rotating trees with depth > 2". Is that right? Can interior nodes have these empty l_rec[0]s? If they can't, perhaps we should be bugging?sorry, It should be
tree_depth>=2.
Quoted 7 lines
ocfs2_adjust_adjacent_recordsis used to for rotation. And it only usee_cposin most cases.
So we don't have a problem if the lower 16 bits ofe_int_clustersisn't equal to 0 for a branch.
But if the low 16 bits are 0, thisocfs2_is_empty_extentwill treat it as an empty record and use the l_recs[1] which will corrupt the tree. So let me give you a test case I meet.
Oh, I understand the problem. My comment above was that it
sounds like you said "Here's a fix, but the fix will still have problems if tree depth is greater than two". I think you mean "without this fix we have problems when tree depth is greater than (or equal to) two".
We need the fix. Now let's figure out if we should bug on
interior children.
Joel
Signature · 9 lines
"Three o'clock is always too late or too early for anything you
want to do."
- Jean-Paul Sartre
Joel Becker
Principal Software Developer
Oracle
E-mail: joel.becker at oracle.com
Phone: (650) 506-8127PATCH 2/2 ocfs2: Use ocfs2_rec_clusters in ocfs2_adjust_adjacent_records. v2
Hi Joel,
how about this? I add a bug_on and change the commit log some how.
Regards,
Tao
In ocfs2_adjust_adjacent_records, we will adjust adjacent records according to the extent_list in the lower level. But actually the lower level tree will either be a leaf or a branch. If we only use ocfs2_is_empty_extent we will meet with some problem if the lower tree is a branch(tree_depth > 1). So use !ocfs2_rec_clusters instead. And actually only the leaf record can have holes. So add a BUG_ON for non-leaf branch.
--- fs/ocfs2/alloc.c | 3 ++- 1 files changed, 2 insertions(+), 1 deletions(-)
fs/ocfs2/alloc.c +2 -1
@@ -1914,7 +1914,8 @@ static void ocfs2_adjust_adjacent_records(struct ocfs2_extent_rec *left_rec,* immediately to their right. */ left_clusters =le32_to_cpu (right_child_el->l_recs[0 ].e_cpos); -if (ocfs2_is_empty_extent (&right_child_el->l_recs[0 ])) { +if (!ocfs2_rec_clusters (right_child_el, &right_child_el->l_recs[0 ])) { +BUG_ON (right_child_el->l_tree_depth);BUG_ON (le16_to_cpu (right_child_el->l_next_free_rec) <=1 ); left_clusters =le32_to_cpu (right_child_el->l_recs[1 ].e_cpos); }
Signature · 1 line
1.6.2.rc2.16.gf474c
PATCH 2/2 ocfs2: Use ocfs2_rec_clusters in ocfs2_adjust_adjacent_records. v2
Quoted 14 lines · Tao Ma
Hi Joel,
how about this? I add abug_onand change the commit log some how.Regards,
TaoIn
ocfs2_adjust_adjacent_records, we will adjust adjacent records according to theextent_listin the lower level. But actually the lower level tree will either be a leaf or a branch. If we only useocfs2_is_empty_extentwe will meet with some problem if the lower tree is abranch(tree_depth > 1). So use !ocfs2_rec_clusters instead. And actually only the leaf record can have holes. So add aBUG_ONfor non-leaf branch.
Quoted 1 line
Signed-off-by Tao Ma <[email protected]>
This is now in the fixes branch of ocfs2.git.
Joel
Signature · 8 lines
"The cynics are right nine times out of ten."
- H. L. Mencken
Joel Becker
Principal Software Developer
Oracle
E-mail: joel.becker at oracle.com
Phone: (650) 506-8127