Skip to contentSkip to conversation

Two b-tree bug fixes.

PATCH New Tao Ma 2 participants 9 messages Jul 21, 2009 – Jul 23, 2009 OCFS2

lore
Share & tools
lore

Tao Ma

author
#0 lore raw

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

author
#1 lore raw

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
index 9edcde4..11085af 100644
@@ -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
author
#3 lore raw

PATCH 2/2 ocfs2: Use ocfs2_rec_clusters in ocfs2_adjust_adjacent_records.

In reply to Tao Ma

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. 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
index 11085af..1957645 100644
@@ -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
#4 lore raw

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 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.

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
#2 lore raw

PATCH 1/2 ocfs2: Add extra credits and access the modified bh in update_edge_lengths.

In reply to Tao Ma
Quoted 10 lines · Tao Ma

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.

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
author
#5 lore raw

PATCH 2/2 ocfs2: Use ocfs2_rec_clusters in ocfs2_adjust_adjacent_records.

In reply to Joel Becker
Quoted 10 lines · Joel Becker
Quoted 7 lines · Tao Ma

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. 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.

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         28726

Tree Depth: 1 Count: 28 Next Free Rec: 10

        ## Offset        Clusters       Block#
        0  9107457       196608         28727
        1  9304065       204544         28729

In this case: 196608=0x30000, so if we use ocfs2_is_empty_extent will treat it as 0, and use 9394065.

Regards,
Tao

#6 lore raw

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 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.

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_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.

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-8127
author
#7 lore raw

PATCH 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
index 11085af..f9a3e89 100644
@@ -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
#8 lore raw

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 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.

Quoted 1 line

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