Patchwork "tune2fs -I 256" runtime---can it be interrupted safely?

login
register
mail settings
Submitter Theodore Ts'o
Date Nov. 15, 2008, 5:50 a.m.
Message ID <20081115055017.GO25117@mit.edu>
Download mbox | patch
Permalink /patch/8893/
State Accepted, archived
Headers show

Comments

Theodore Ts'o - Nov. 15, 2008, 5:50 a.m.
On Fri, Nov 14, 2008 at 02:06:12PM -0700, Andreas Dilger wrote:
> 
> Ah, it is trying to find free blocks, but the e2fsprogs allocator is very
> inefficient, IIRC, doing a linear scan of the filesystem.  We probably
> would be far better off to generate an RB tree of the block maps so that
> it is easier to work with lists of blocks that need to be moved or marked
> in use for the resized inode table.

We eventually could use a more sophisticated block allocator in the
ext2fs userspace library, but there's a quick fix should do the job
without having to do something more complicated.  The problem is that
the goal block is always reset to blk, which makes this an O(n**2)
operation in the number of in-use blocks in the filesystem.  This
following patch makes it be O(n), which should make it be a marked
improvement.

Running a profile analysis on tune2fs, there's another O(n*m)
operation in transalate_block() (yes, the function name is mispelled),
where n is the number of blocks that needs to be moved, and m is the
number of in-use blocks in the filesystems.

Fixing both of these should remove most of the user-space time that's
being burned by tune2fs -I 256.  There is still some CPU burned by the
undo file, and indeed we can probably speed this up some more by
omitting creating an undo entry when we're copying a data block to a
previously unused block.  But hopefully this should be enough to speed
up "tune2fs -I 256" for most people.

							- Ted

commit 27c6de45a4187a348ec0960472d4a113ee6ea425
Author: Theodore Ts'o <tytso@mit.edu>
Date:   Sat Nov 15 00:32:39 2008 -0500

    tune2fs: Fix inefficient O(n**2) algorithms when expanding the inode size
    
    When running "tune2fs -I 256" on moderate to large filesystems, the
    time required to run tune2fs can take many hours (20+ before some
    users gave up in disgust).  This was due to some O(n**2) and O(n*m)
    algorithms in move_block() and inode_scan_and_fix(), respectively.
    
    Signed-off-by: "Theodore Ts'o" <tytso@mit.edu>


--
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
Andreas Schultz - Nov. 16, 2008, 12:11 p.m.
Hi,

On Saturday 15 November 2008 06:50:17 Theodore Tso wrote:

> Fixing both of these should remove most of the user-space time that's
> being burned by tune2fs -I 256.  There is still some CPU burned by the
> undo file, and indeed we can probably speed this up some more by
> omitting creating an undo entry when we're copying a data block to a
> previously unused block.  But hopefully this should be enough to speed
> up "tune2fs -I 256" for most people.

it does speed up things, but it is still quite slow. I tried it on a 250GB partition which is about 86% filled:

root@ws-aschultz:~# df -i /usr/src2/
Filesystem            Inodes   IUsed   IFree IUse% Mounted on
/dev/sdb1            30523392 1401574 29121818    5% /usr/src2
root@ws-aschultz:~# df /usr/src2/
Filesystem           1K-blocks      Used Available Use% Mounted on
/dev/sdb1            240308484 196091320  32010176  86% /usr/src2
root@ws-aschultz:~# umount /usr/src2
root@ws-aschultz:~# time tune2fs -I 256 /dev/sdb1
tune2fs 1.41.3 (12-Oct-2008)
Setting inode size 256

real    64m31.189s
user    43m46.708s
sys     1m50.627s

64min for 250GB seems to be to much for the average user.

From watching the disc activity and the output of 'top', it seems that the operation periodically consumes 100%CPU for extended periods without any disc activity, followed by a brief period of about 20%CPU load and light disc activity.

Andreas

Patch

diff --git a/misc/tune2fs.c b/misc/tune2fs.c
index b29b344..e72518a 100644
--- a/misc/tune2fs.c
+++ b/misc/tune2fs.c
@@ -1011,13 +1011,13 @@  static int move_block(ext2_filsys fs, ext2fs_block_bitmap bmap)
 	if (retval)
 		return retval;
 
-	for (blk = fs->super->s_first_data_block;
-			blk < fs->super->s_blocks_count; blk++) {
+	for (new_blk = blk = fs->super->s_first_data_block;
+	     blk < fs->super->s_blocks_count; blk++) {
 
 		if (!ext2fs_test_block_bitmap(bmap, blk))
 			continue;
 
-		retval = ext2fs_new_block(fs, blk, NULL, &new_blk);
+		retval = ext2fs_new_block(fs, new_blk, NULL, &new_blk);
 		if (retval)
 			goto err_out;
 
@@ -1068,12 +1068,14 @@  static int process_block(ext2_filsys fs EXT2FS_ATTR((unused)),
 			 e2_blkcnt_t blockcnt EXT2FS_ATTR((unused)),
 			 blk_t ref_block EXT2FS_ATTR((unused)),
 			 int ref_offset EXT2FS_ATTR((unused)),
-			 void *priv_data EXT2FS_ATTR((unused)))
+			 void *priv_data)
 {
 	int ret = 0;
 	blk_t new_blk;
+	ext2fs_block_bitmap bmap = (ext2fs_block_bitmap) priv_data;
 
-
+	if (!ext2fs_test_block_bitmap(bmap, *block_nr))
+		return 0;
 	new_blk = transalate_block(*block_nr);
 	if (new_blk) {
 		*block_nr = new_blk;
@@ -1086,7 +1088,7 @@  static int process_block(ext2_filsys fs EXT2FS_ATTR((unused)),
 	return ret;
 }
 
-static int inode_scan_and_fix(ext2_filsys fs)
+static int inode_scan_and_fix(ext2_filsys fs, ext2fs_block_bitmap bmap)
 {
 	errcode_t retval = 0;
 	ext2_ino_t ino;
@@ -1122,8 +1124,8 @@  static int inode_scan_and_fix(ext2_filsys fs)
 		 * Do we need to fix this ??
 		 */
 
-		if (inode.i_file_acl) {
-
+		if (inode.i_file_acl &&
+		    ext2fs_test_block_bitmap(bmap, inode.i_file_acl)) {
 			blk = transalate_block(inode.i_file_acl);
 			if (!blk)
 				continue;
@@ -1142,9 +1144,8 @@  static int inode_scan_and_fix(ext2_filsys fs)
 		if (!ext2fs_inode_has_valid_blocks(&inode))
 			continue;
 
-		retval = ext2fs_block_iterate2(fs, ino, 0,
-						block_buf, process_block,
-						0);
+		retval = ext2fs_block_iterate2(fs, ino, 0, block_buf,
+					       process_block, bmap);
 		if (retval)
 			goto err_out;
 
@@ -1344,7 +1345,7 @@  static int resize_inode(ext2_filsys fs, unsigned long new_size)
 	if (retval)
 		goto err_out;
 
-	retval = inode_scan_and_fix(fs);
+	retval = inode_scan_and_fix(fs, bmap);
 	if (retval)
 		goto err_out;