[Ocfs2-devel] [PATCH 0/2] Two b-tree bug fixes.

[Ocfs2-devel] [PATCH 0/2] Two b-tree bug fixes.

[Tao Ma]

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

[Ocfs2-devel] [PATCH 1/2] ocfs2: Add extra credits and access the modified bh in update_edge_lengths.

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

Signed-off-by: Tao Ma <tao.ma@oracle.com>
---
 fs/ocfs2/alloc.c |   44 +++++++++++++++++++++++++++++++++++++++-----
 1 files changed, 39 insertions(+), 5 deletions(-)

diff --git a/fs/ocfs2/alloc.c b/fs/ocfs2/alloc.c
index 9edcde4..11085af 100644
--- a/fs/ocfs2/alloc.c
+++ b/fs/ocfs2/alloc.c
@@ -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));
-- 
1.6.2.rc2.16.gf474c

[Ocfs2-devel] [PATCH 2/2] ocfs2: Use ocfs2_rec_clusters in ocfs2_adjust_adjacent_records.

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

Signed-off-by: Tao Ma <tao.ma@oracle.com>
---
 fs/ocfs2/alloc.c |    2 +-
 1 files changed, 1 insertions(+), 1 deletions(-)

diff --git a/fs/ocfs2/alloc.c b/fs/ocfs2/alloc.c
index 11085af..1957645 100644
--- a/fs/ocfs2/alloc.c
+++ b/fs/ocfs2/alloc.c
@@ -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);
 	}
-- 
1.6.2.rc2.16.gf474c

[Ocfs2-devel] [PATCH 2/2] ocfs2: Use ocfs2_rec_clusters in ocfs2_adjust_adjacent_records.

[Joel Becker]

On Tue, Jul 21, 2009 at 03:42:06PM +0800, Tao Ma wrote:
> 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

-- 

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

[Ocfs2-devel] [PATCH 1/2] ocfs2: Add extra credits and access the modified bh in update_edge_lengths.

[Joel Becker]

On Tue, Jul 21, 2009 at 03:42:05PM +0800, Tao Ma wrote:
> 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.
> 
> Signed-off-by: Tao Ma <tao.ma@oracle.com>

This patch is now in the fixes branch of ocfs2.git.

Joel

-- 

"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

[Ocfs2-devel] [PATCH 2/2] ocfs2: Use ocfs2_rec_clusters in ocfs2_adjust_adjacent_records.

[Tao Ma]

Joel Becker wrote:
> On Tue, Jul 21, 2009 at 03:42:06PM +0800, Tao Ma wrote:
>   
>> 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?
>   
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

[Ocfs2-devel] [PATCH 2/2] ocfs2: Use ocfs2_rec_clusters in ocfs2_adjust_adjacent_records.

[Joel Becker]

On Wed, Jul 22, 2009 at 08:32:32AM +0800, Tao Ma wrote:
> Joel Becker wrote:
> >On Tue, Jul 21, 2009 at 03:42:06PM +0800, Tao Ma wrote:
> >>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?
> 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.

	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

-- 

"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

[Ocfs2-devel] [PATCH 2/2] ocfs2: Use ocfs2_rec_clusters in ocfs2_adjust_adjacent_records. v2

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

Signed-off-by: Tao Ma <tao.ma@oracle.com>
---
 fs/ocfs2/alloc.c |    3 ++-
 1 files changed, 2 insertions(+), 1 deletions(-)

diff --git a/fs/ocfs2/alloc.c b/fs/ocfs2/alloc.c
index 11085af..f9a3e89 100644
--- a/fs/ocfs2/alloc.c
+++ b/fs/ocfs2/alloc.c
@@ -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);
 	}
-- 
1.6.2.rc2.16.gf474c

[Ocfs2-devel] [PATCH 2/2] ocfs2: Use ocfs2_rec_clusters in ocfs2_adjust_adjacent_records. v2

[Joel Becker]

On Thu, Jul 23, 2009 at 08:12:58AM +0800, Tao Ma wrote:
> 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.
> 
> Signed-off-by: Tao Ma <tao.ma@oracle.com>

This is now in the fixes branch of ocfs2.git.

Joel

-- 

"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