Whamcloud - gitweb
resize2fs: radically reduce memory utilization by using rbtree bitmaps
authorTheodore Ts'o <tytso@mit.edu>
Fri, 25 Jul 2014 17:38:50 +0000 (13:38 -0400)
committerTheodore Ts'o <tytso@mit.edu>
Sat, 26 Jul 2014 04:48:29 +0000 (00:48 -0400)
commitbaab9f43bf0ecacd043dafb2de29163da5deaf24
tree84b3fda0ca5fcde7253da2d9afaacdaacaac5e9e
parent2dbf34e50562d08d5da4d3f373f3bc0b2fd46728
resize2fs: radically reduce memory utilization by using rbtree bitmaps

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

So this reduces the max memory utilized from 4.2GB to 29MB!

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.

Signed-off-by: Theodore Ts'o <tytso@mit.edu>
resize/main.c