[PATCH] resize2fs: radically reduce memory utilization by using rbtree bitmaps

[PATCH] resize2fs: radically reduce memory utilization by using rbtree bitmaps

[Theodore Ts'o]

When resizing an empty 21T file system to 28T, resize2fs was using
this much CPU time and memory:

216.98user 19.77system 4:02.92elapsed 97%CPU (0avgtext+0avgdata 4485664maxresident)k
8inputs+1068680outputs (0major+800745minor)pagefaults 0swaps

After this one-line change:

222.29user 0.49system 3:48.79elapsed 97%CPU (0avgtext+0avgdata 30080maxresident)k
8inputs+1068552outputs (0major+2497minor)pagefaults 0swaps

An extra 14 seconds (+6%) of elapsed time to reduce the memory
utilization from 4.2GB to 29MB seems like a fair trade.  :-)

For future work, the primary place where we are spending the most cpu
time (from resize2fs -d 16) are these two places:

blocks_to_move: Memory used: 2508k/25096k (1903k/606k), time: 91.42/91.53/ 0.00

and

calculate_summary_stats: Memory used: 2508k/25612k (1908k/601k), time: 95.33/95.45/ 0.00

The calculate_summary_stats pass can be sped up by using
ext2fs_find_first_{zero,set}_block_bitmap2(), instead of iterating
over the entire block bitmap one bit at a time.

The blocks_to_move pass can be sped up by using a bitmap to store the
location of fs metadata blocks, to avoid an O(N**2) algorithm where N
is the number of groups in the file system.

The use of using rbtree bitmaps makes the above two optimizations
possible, which will more than claw back the extra 14 seconds in CPU
time.

Signed-off-by: Theodore Ts'o <tytso@mit.edu>
---
 resize/main.c | 1 +
 1 file changed, 1 insertion(+)

diff --git a/resize/main.c b/resize/main.c
index e4b4435..ef2a810 100644
--- a/resize/main.c
+++ b/resize/main.c
@@ -318,6 +318,7 @@ int main (int argc, char ** argv)
 		printf("%s", _("Couldn't find valid filesystem superblock.\n"));
 		exit (1);
 	}
+	fs->default_bitmap_type = EXT2FS_BMAP64_RBTREE;
 
 	if (!(mount_flags & EXT2_MF_MOUNTED)) {
 		if (!force && ((fs->super->s_lastcheck < fs->super->s_mtime) ||
-- 
2.0.0

Re: [PATCH] resize2fs: radically reduce memory utilization by using rbtree bitmaps

[Eric Sandeen]

On 7/25/14, 12:51 PM, Theodore Ts'o wrote:
> When resizing an empty 21T file system to 28T, resize2fs was using
> this much CPU time and memory:
> 
> 216.98user 19.77system 4:02.92elapsed 97%CPU (0avgtext+0avgdata 4485664maxresident)k
> 8inputs+1068680outputs (0major+800745minor)pagefaults 0swaps
> 
> After this one-line change:
> 
> 222.29user 0.49system 3:48.79elapsed 97%CPU (0avgtext+0avgdata 30080maxresident)k
> 8inputs+1068552outputs (0major+2497minor)pagefaults 0swaps
> 
> An extra 14 seconds (+6%) of elapsed time to reduce the memory
> utilization from 4.2GB to 29MB seems like a fair trade.  :-)

especially when it actually looks like 14 *fewer* seconds (-6%) ?

-Eric

Re: [PATCH] resize2fs: radically reduce memory utilization by using rbtree bitmaps

[Theodore Ts'o]

On Fri, Jul 25, 2014 at 01:11:42PM -0500, Eric Sandeen wrote:
> On 7/25/14, 12:51 PM, Theodore Ts'o wrote:
> > When resizing an empty 21T file system to 28T, resize2fs was using
> > this much CPU time and memory:
> > 
> > 216.98user 19.77system 4:02.92elapsed 97%CPU (0avgtext+0avgdata 4485664maxresident)k
> > 8inputs+1068680outputs (0major+800745minor)pagefaults 0swaps
> > 
> > After this one-line change:
> > 
> > 222.29user 0.49system 3:48.79elapsed 97%CPU (0avgtext+0avgdata 30080maxresident)k
> > 8inputs+1068552outputs (0major+2497minor)pagefaults 0swaps
> > 
> > An extra 14 seconds (+6%) of elapsed time to reduce the memory
> > utilization from 4.2GB to 29MB seems like a fair trade.  :-)
> 
> especially when it actually looks like 14 *fewer* seconds (-6%) ?

Yeah, I was initially looking at the increase in user time, and then
didn't notice that this was more than compensated by the decrease in
system time (probably due to all of the page faults when dealing with
traditional bitmaps).  Oops.

I'll adjust the comments appropriately.

							- Ted