Patchwork [v2] ext4:Teach ext4_ext_split to caculate extents efficiently.

login
register
mail settings
Submitter Yongqiang Yang
Date May 23, 2011, 9:30 a.m.
Message ID <1306143057-16962-1-git-send-email-xiaoqiangnk@gmail.com>
Download mbox | patch
Permalink /patch/96884/
State Accepted
Headers show

Comments

Yongqiang Yang - May 23, 2011, 9:30 a.m.
Make ext4_ext_split() get extents to be moved by calculating in a statement
instead of counting in a loop.

Signed-off-by: Yongqiang Yang <xiaoqiangnk@gmail.com>
---
v1->v2:
 Make changelog be much more specific.

 fs/ext4/extents.c |   84 +++++++++++++++++++++++++++++------------------------
 1 files changed, 46 insertions(+), 38 deletions(-)
Theodore Ts'o - May 24, 2011, 9:07 p.m.
On Mon, May 23, 2011 at 05:30:57PM +0800, Yongqiang Yang wrote:
> @@ -982,20 +997,13 @@ static int ext4_ext_split(handle_t *handle, struct inode *inode,
>  			err = -EIO;
>  			goto cleanup;
>  		}
> -		while (path[i].p_idx <= EXT_MAX_INDEX(path[i].p_hdr)) {
> -			ext_debug("%d: move %d:%llu in new index %llu\n", i,
> -					le32_to_cpu(path[i].p_idx->ei_block),
> -					ext4_idx_pblock(path[i].p_idx),
> -					newblock);
> -			/*memmove(++fidx, path[i].p_idx++,
> -					sizeof(struct ext4_extent_idx));
> -			neh->eh_entries++;
> -			BUG_ON(neh->eh_entries > neh->eh_max);*/
> -			path[i].p_idx++;
> -			m++;
> -		}
> +		/* start copy indexes */
> +		m = EXT_MAX_INDEX(path[i].p_hdr) - path[i].p_idx++;
> +		ext_debug("cur 0x%p, last 0x%p\n", path[i].p_idx,
> +				EXT_MAX_INDEX(path[i].p_hdr));
> +		ext4_ext_show_move(inode, path, newblock, i);
>  		if (m) {
> -			memmove(++fidx, path[i].p_idx - m,
> +			memmove(++fidx, path[i].p_idx,
>  				sizeof(struct ext4_extent_idx) * m);
>  			le16_add_cpu(&neh->eh_entries, m);
>  		}

So the old code mutates path[i].p_idx, where as your new code doesn't.
The one thing that scares me is that ext4_ext_insert_index() is passed
&path[at], the function preferences path[at].p_idx.

Have you looked at this case?

					- Ted
--
To unsubscribe from this list: send the line "unsubscribe linux-ext4" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Yongqiang Yang - May 25, 2011, 2:02 a.m.
On Wed, May 25, 2011 at 5:07 AM, Ted Ts'o <tytso@mit.edu> wrote:
> On Mon, May 23, 2011 at 05:30:57PM +0800, Yongqiang Yang wrote:
>> @@ -982,20 +997,13 @@ static int ext4_ext_split(handle_t *handle, struct inode *inode,
>>                       err = -EIO;
>>                       goto cleanup;
>>               }
>> -             while (path[i].p_idx <= EXT_MAX_INDEX(path[i].p_hdr)) {
>> -                     ext_debug("%d: move %d:%llu in new index %llu\n", i,
>> -                                     le32_to_cpu(path[i].p_idx->ei_block),
>> -                                     ext4_idx_pblock(path[i].p_idx),
>> -                                     newblock);
>> -                     /*memmove(++fidx, path[i].p_idx++,
>> -                                     sizeof(struct ext4_extent_idx));
>> -                     neh->eh_entries++;
>> -                     BUG_ON(neh->eh_entries > neh->eh_max);*/
>> -                     path[i].p_idx++;
>> -                     m++;
>> -             }
>> +             /* start copy indexes */
>> +             m = EXT_MAX_INDEX(path[i].p_hdr) - path[i].p_idx++;
>> +             ext_debug("cur 0x%p, last 0x%p\n", path[i].p_idx,
>> +                             EXT_MAX_INDEX(path[i].p_hdr));
>> +             ext4_ext_show_move(inode, path, newblock, i);
>>               if (m) {
>> -                     memmove(++fidx, path[i].p_idx - m,
>> +                     memmove(++fidx, path[i].p_idx,
>>                               sizeof(struct ext4_extent_idx) * m);
>>                       le16_add_cpu(&neh->eh_entries, m);
>>               }
>
Hi Ted,

Thank you for your review.  I had looked at this case.

> So the old code mutates path[i].p_idx, where as your new code doesn't.
path[i]p_idx is mutated to EXT_MAX_INDEX(path[i].p_hdr) + 1, it is
meaningless.  ext4_ext_split() is used only by
ext4_ext_create_new_leaf() which drops the path after ext4_ext_split()
returns, so the path[i].p_idx is no longer used.

> The one thing that scares me is that ext4_ext_insert_index() is passed
> &path[at], the function preferences path[at].p_idx.
ext4_ext_split() insert k indexes, where k = depth - at -1, starting
from depth - 1 to depth - 1 - k + 1 = depth - k = at + 1.

So old code does not mutate depth[at].p_idx.

I had tested the patch with fsx.  I am not sure if this test is
enough.  If you want more tests, I can do it.

Thanks,
Yongqiang.
>
> Have you looked at this case?
>
>                                        - Ted
>
Theodore Ts'o - May 25, 2011, 10:02 p.m.
On Wed, May 25, 2011 at 10:02:37AM +0800, Yongqiang Yang wrote:
> path[i]p_idx is mutated to EXT_MAX_INDEX(path[i].p_hdr) + 1, it is
> meaningless.  ext4_ext_split() is used only by
> ext4_ext_create_new_leaf() which drops the path after ext4_ext_split()
> returns, so the path[i].p_idx is no longer used.
> 
> I had tested the patch with fsx.  I am not sure if this test is
> enough.  If you want more tests, I can do it.

OK, thanks for the explanation.  Sometimes testing doesn't find
problems, so I try to understand the patch and make sure it is sane.
I noticed that your path[i].p_ext and path[i].p_idx were no longer
being updated with your patch; I was able to convince myself that
p_ext didn't matter, but I wasn't entirely sure about p_idx, so that's
why I asked you.

I've added it to the ext4 dev tree.

					- Ted
--
To unsubscribe from this list: send the line "unsubscribe linux-ext4" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Patch

diff --git a/fs/ext4/extents.c b/fs/ext4/extents.c
index e363f21..baf846f 100644
--- a/fs/ext4/extents.c
+++ b/fs/ext4/extents.c
@@ -474,9 +474,43 @@  static void ext4_ext_show_leaf(struct inode *inode, struct ext4_ext_path *path)
 	}
 	ext_debug("\n");
 }
+
+static void ext4_ext_show_move(struct inode *inode, struct ext4_ext_path *path,
+			ext4_fsblk_t newblock, int level)
+{
+	int depth = ext_depth(inode);
+	struct ext4_extent *ex;
+
+	if (depth != level) {
+		struct ext4_extent_idx *idx;
+		idx = path[level].p_idx;
+		while (idx <= EXT_MAX_INDEX(path[level].p_hdr)) {
+			ext_debug("%d: move %d:%llu in new index %llu\n", level,
+					le32_to_cpu(idx->ei_block),
+					ext4_idx_pblock(idx),
+					newblock);
+			idx++;
+		}
+
+		return;
+	}
+
+	ex = path[depth].p_ext;
+	while (ex <= EXT_MAX_EXTENT(path[depth].p_hdr)) {
+		ext_debug("move %d:%llu:[%d]%d in new leaf %llu\n",
+				le32_to_cpu(ex->ee_block),
+				ext4_ext_pblock(ex),
+				ext4_ext_is_uninitialized(ex),
+				ext4_ext_get_actual_len(ex),
+				newblock);
+		ex++;
+	}
+}
+
 #else
 #define ext4_ext_show_path(inode, path)
 #define ext4_ext_show_leaf(inode, path)
+#define ext4_ext_show_move(inode, path, newblock, level)
 #endif
 
 void ext4_ext_drop_refs(struct ext4_ext_path *path)
@@ -799,7 +833,6 @@  static int ext4_ext_split(handle_t *handle, struct inode *inode,
 	int depth = ext_depth(inode);
 	struct ext4_extent_header *neh;
 	struct ext4_extent_idx *fidx;
-	struct ext4_extent *ex;
 	int i = at, k, m, a;
 	ext4_fsblk_t newblock, oldblock;
 	__le32 border;
@@ -876,7 +909,6 @@  static int ext4_ext_split(handle_t *handle, struct inode *inode,
 	neh->eh_max = cpu_to_le16(ext4_ext_space_block(inode, 0));
 	neh->eh_magic = EXT4_EXT_MAGIC;
 	neh->eh_depth = 0;
-	ex = EXT_FIRST_EXTENT(neh);
 
 	/* move remainder of path[depth] to the new leaf */
 	if (unlikely(path[depth].p_hdr->eh_entries !=
@@ -888,25 +920,12 @@  static int ext4_ext_split(handle_t *handle, struct inode *inode,
 		goto cleanup;
 	}
 	/* start copy from next extent */
-	/* TODO: we could do it by single memmove */
-	m = 0;
-	path[depth].p_ext++;
-	while (path[depth].p_ext <=
-			EXT_MAX_EXTENT(path[depth].p_hdr)) {
-		ext_debug("move %d:%llu:[%d]%d in new leaf %llu\n",
-				le32_to_cpu(path[depth].p_ext->ee_block),
-				ext4_ext_pblock(path[depth].p_ext),
-				ext4_ext_is_uninitialized(path[depth].p_ext),
-				ext4_ext_get_actual_len(path[depth].p_ext),
-				newblock);
-		/*memmove(ex++, path[depth].p_ext++,
-				sizeof(struct ext4_extent));
-		neh->eh_entries++;*/
-		path[depth].p_ext++;
-		m++;
-	}
+	m = EXT_MAX_EXTENT(path[depth].p_hdr) - path[depth].p_ext++;
+	ext4_ext_show_move(inode, path, newblock, depth);
 	if (m) {
-		memmove(ex, path[depth].p_ext-m, sizeof(struct ext4_extent)*m);
+		struct ext4_extent *ex;
+		ex = EXT_FIRST_EXTENT(neh);
+		memmove(ex, path[depth].p_ext, sizeof(struct ext4_extent) * m);
 		le16_add_cpu(&neh->eh_entries, m);
 	}
 
@@ -968,12 +987,8 @@  static int ext4_ext_split(handle_t *handle, struct inode *inode,
 
 		ext_debug("int.index at %d (block %llu): %u -> %llu\n",
 				i, newblock, le32_to_cpu(border), oldblock);
-		/* copy indexes */
-		m = 0;
-		path[i].p_idx++;
 
-		ext_debug("cur 0x%p, last 0x%p\n", path[i].p_idx,
-				EXT_MAX_INDEX(path[i].p_hdr));
+		/* move remainder of path[i] to the new index block */
 		if (unlikely(EXT_MAX_INDEX(path[i].p_hdr) !=
 					EXT_LAST_INDEX(path[i].p_hdr))) {
 			EXT4_ERROR_INODE(inode,
@@ -982,20 +997,13 @@  static int ext4_ext_split(handle_t *handle, struct inode *inode,
 			err = -EIO;
 			goto cleanup;
 		}
-		while (path[i].p_idx <= EXT_MAX_INDEX(path[i].p_hdr)) {
-			ext_debug("%d: move %d:%llu in new index %llu\n", i,
-					le32_to_cpu(path[i].p_idx->ei_block),
-					ext4_idx_pblock(path[i].p_idx),
-					newblock);
-			/*memmove(++fidx, path[i].p_idx++,
-					sizeof(struct ext4_extent_idx));
-			neh->eh_entries++;
-			BUG_ON(neh->eh_entries > neh->eh_max);*/
-			path[i].p_idx++;
-			m++;
-		}
+		/* start copy indexes */
+		m = EXT_MAX_INDEX(path[i].p_hdr) - path[i].p_idx++;
+		ext_debug("cur 0x%p, last 0x%p\n", path[i].p_idx,
+				EXT_MAX_INDEX(path[i].p_hdr));
+		ext4_ext_show_move(inode, path, newblock, i);
 		if (m) {
-			memmove(++fidx, path[i].p_idx - m,
+			memmove(++fidx, path[i].p_idx,
 				sizeof(struct ext4_extent_idx) * m);
 			le16_add_cpu(&neh->eh_entries, m);
 		}