* [PATCH v2] ext4:Teach ext4_ext_split to caculate extents efficiently.
@ 2011-05-23 9:30 Yongqiang Yang
2011-05-24 21:07 ` Ted Ts'o
0 siblings, 1 reply; 4+ messages in thread
From: Yongqiang Yang @ 2011-05-23 9:30 UTC (permalink / raw)
To: tytso; +Cc: linux-ext4, Yongqiang Yang
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(-)
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);
}
--
1.7.5.1
^ permalink raw reply related [flat|nested] 4+ messages in thread
* Re: [PATCH v2] ext4:Teach ext4_ext_split to caculate extents efficiently.
2011-05-23 9:30 [PATCH v2] ext4:Teach ext4_ext_split to caculate extents efficiently Yongqiang Yang
@ 2011-05-24 21:07 ` Ted Ts'o
2011-05-25 2:02 ` Yongqiang Yang
0 siblings, 1 reply; 4+ messages in thread
From: Ted Ts'o @ 2011-05-24 21:07 UTC (permalink / raw)
To: Yongqiang Yang; +Cc: linux-ext4
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
^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: [PATCH v2] ext4:Teach ext4_ext_split to caculate extents efficiently.
2011-05-24 21:07 ` Ted Ts'o
@ 2011-05-25 2:02 ` Yongqiang Yang
2011-05-25 22:02 ` Ted Ts'o
0 siblings, 1 reply; 4+ messages in thread
From: Yongqiang Yang @ 2011-05-25 2:02 UTC (permalink / raw)
To: Ted Ts'o; +Cc: linux-ext4
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
>
--
Best Wishes
Yongqiang Yang
--
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
^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: [PATCH v2] ext4:Teach ext4_ext_split to caculate extents efficiently.
2011-05-25 2:02 ` Yongqiang Yang
@ 2011-05-25 22:02 ` Ted Ts'o
0 siblings, 0 replies; 4+ messages in thread
From: Ted Ts'o @ 2011-05-25 22:02 UTC (permalink / raw)
To: Yongqiang Yang; +Cc: linux-ext4
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
^ permalink raw reply [flat|nested] 4+ messages in thread
end of thread, other threads:[~2011-05-25 22:02 UTC | newest]
Thread overview: 4+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2011-05-23 9:30 [PATCH v2] ext4:Teach ext4_ext_split to caculate extents efficiently Yongqiang Yang
2011-05-24 21:07 ` Ted Ts'o
2011-05-25 2:02 ` Yongqiang Yang
2011-05-25 22:02 ` Ted Ts'o
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.