Skip to contentSkip to conversation

e2fsprogs: Speed up ext2fs_new_block2

RFC PATCH In review Darren Hart 2 participants 2 messages Feb 20, 2015 – Feb 21, 2015

lore
Share & tools
lore

Darren Hart

author
#0 lore raw

RFC PATCH 1/1 e2fsprogs: Speed up ext2fs_new_block2

Ted and Darrick,

We're back with a Yocto Project use case. We use mkfs.ext4 to create our root filesystems. For one of our larger images including an X desktop and an SDK (toolchain, etc.), it took over 8 minutes to complete. Richard Purdie noticed most of this time was in ext2fs_new_block2. He provided this small hack to test an idea and it has reduced the runtime to 35 seconds. The images function as expected.

Can you have a look and see if there some value in this approach, or if perhaps it might lead to a more appropriate/correct solution?

Thanks!

Darren

(What follows is the test patch from Richard for the Yocto Project)

The comment to this function says:

"""
* Stupid algorithm --- we now just search forward starting from the
* goal. Should put in a smarter one someday....
"""

This adds in a rather hacky algorthim which starts where we finished searching previously using a static variable rather than starting from scratch if a hint isn't provided.

This was after noticing that mkfs.ext4 -F X -d Y was spending *lots* of time in ext2fs_new_block2 called from ext2fs_bmap from ext2fs_file_write().

Numbers wise, this took a core-image-sato-sdk mkfs time from over 8 minutes to around 35 seconds.

Upstream-Status: Pending

RP 2015/02/20

lib/ext2fs/alloc.c +6 -0
Index: e2fsprogs-1.42.9/lib/ext2fs/alloc.c
===================================================================
@@ -160,6 +160,8 @@ errcode_t ext2fs_new_inode(ext2_filsys f
 	return 0;
 }
 
+static blk64_t last_goal = 0;
+
 /*
  * Stupid algorithm --- we now just search forward starting from the
  * goal.  Should put in a smarter one someday....

@@ -170,6 +172,9 @@ errcode_t ext2fs_new_block2(ext2_filsys
 	blk64_t	i;
 	int	c_ratio;
 
+        if (!goal)
+            goal = last_goal;
+
 	EXT2_CHECK_MAGIC(fs, EXT2_ET_MAGIC_EXT2FS_FILSYS);
 
 	if (!map)

@@ -194,6 +199,7 @@ errcode_t ext2fs_new_block2(ext2_filsys
 
 		if (!ext2fs_fast_test_block_bitmap2(map, i)) {
 			*ret = i;
+			last_goal = i;
 			return 0;
 		}
 		i = (i + c_ratio) & ~(c_ratio - 1);
Signature · 2 lines
Darren Hart
Intel Open Source Technology Center
#1 lore raw
Quoted 21 lines · Darren Hart

Ted and Darrick,

We're back with a Yocto Project use case. We use mkfs.ext4 to create our root filesystems. For one of our larger images including an X desktop and an SDK (toolchain, etc.), it took over 8 minutes to complete. Richard Purdie noticed most of this time was in ext2fs_new_block2. He provided this small hack to test an idea and it has reduced the runtime to 35 seconds. The images function as expected.

Can you have a look and see if there some value in this approach, or if perhaps it might lead to a more appropriate/correct solution?

Thanks!

Darren

(What follows is the test patch from Richard for the Yocto Project)

The comment to this function says:

Quoted 8 lines

"""
* Stupid algorithm --- we now just search forward starting from the
* goal. Should put in a smarter one someday....
"""

This adds in a rather hacky algorthim which starts where we finished searching previously using a static variable rather than starting from scratch if a hint isn't provided.

Not a horrible idea, esp. for laying out files one after the other at mkfs time.

Quoted 3 lines

This was after noticing that mkfs.ext4 -F X -d Y was spending *lots* of time in ext2fs_new_block2 called from ext2fs_bmap from ext2fs_file_write().

Yeah, it did.

lib/ext2fs/alloc.c

Quoted 11 lines

Numbers wise, this took a core-image-sato-sdk mkfs time from over 8 minutes to around 35 seconds.

Upstream-Status: Pending

RP 2015/02/20

Index: e2fsprogs-1.42.9/lib/ext2fs/alloc.c
===================================================================

lib/ext2fs/alloc.c +0 -0

1.42.9? That's pretty old. :)

I've patches in -next sitting that make the allocators a bit less stupid. One makes it so that if there's no goal explicitly given, we'll try to start allocating in the same block group that the inode lives in. Some time ago Ted also added a bitmap helper function that really sped up file allocations.

Also, could you have a look at patches 42-46 in:
http://thread.gmane.org/gmane.comp.file-systems.ext4/47584
since they directly touch pieces that your team seems to want?

For more fun, could you take a look at 47-52? They provide a fallocate() implementation so that you can preallocate the entire file before writing, which (if you have big files) avoids having to rewrite the extent tree with every new FS block.

Quoted 10 lines
lib/ext2fs/alloc.c +2 -0
@@ -160,6 +160,8 @@ errcode_t ext2fs_new_inode(ext2_filsys f
 	return 0;
 }
 
+static blk64_t last_goal = 0;
+
 /*
  * Stupid algorithm --- we now just search forward starting from the
  * goal.  Should put in a smarter one someday....

lib/ext2fs/alloc.c errcode_t ext2fs_new_block2(ext2_filsys · line 176

Quoted 5 lines
lib/ext2fs/alloc.c +2 -0
@@ -170,6 +172,9 @@ errcode_t ext2fs_new_block2(ext2_filsys
 	blk64_t	i;
 	int	c_ratio;
 
+        if (!goal)
+            goal = last_goal;

Offhand this doesn't seem like a bad idea to me.

'last_allocated' might be a better name, and if it's not going to be used outside the function, it could be a static var inside new_block2().

--D

Quoted 16 lines
lib/ext2fs/alloc.c +2 -0
+
 	EXT2_CHECK_MAGIC(fs, EXT2_ET_MAGIC_EXT2FS_FILSYS);
 
 	if (!map)

@@ -194,6 +199,7 @@ errcode_t ext2fs_new_block2(ext2_filsys
 
 		if (!ext2fs_fast_test_block_bitmap2(map, i)) {
 			*ret = i;
+			last_goal = i;
 			return 0;
 		}
 		i = (i + c_ratio) & ~(c_ratio - 1);
Signature · 3 lines
-- 
Darren Hart
Intel Open Source Technology Center