Debian Bug report logs - #663237
e2fsprogs: [patch] Make resize2fs shrinking use much less CPU

Toggle useless messages

Message #5 received at submit@bugs.debian.org (full text, mbox, reply):

From: Sami Liedes <sliedes@cc.hut.fi>

To: Debian Bug Tracking System <submit@bugs.debian.org>

Subject: e2fsprogs: [patch] Make resize2fs shrinking use much less CPU

Date: Fri, 9 Mar 2012 20:11:05 +0200

[Message part 1 (text/plain, inline)]

Package: e2fsprogs
Version: 1.42.1-2
Severity: normal
Tags: patch

Shrinking a filesystem is currently very CPU intensive. On a 100G ext4
filesystem filled to 50% full by making copies of /usr/share/doc to
$MNTPOINT/doc{1,2,3,...}, running resize2fs on a fairly slow (~5400
rpm) disk and a fast Core i7 processor:

# time resize2fs -p $FILESYSTEM 75G
[...]
real    96m26.852s
user    56m39.768s
sys     0m27.922s

Apparently shrinking larger filesystems causes even larger slowdowns
(CPU time consumed grows superlinearly), but I don't have the numbers
to back this up right now.

Turns out the slow and CPU intensive phase is the "Scanning inode
table" phase. The reason for this is that the inode table is scanned
bit by bit in ext2fs_new_inode(). It appears that in many cases a huge
string of bits needs to be tested to find the first zero bit. It
doesn't help that for each bit test a modulo operation is done in
ext2fs_new_inode(), after which the bit test is done by calling this
chain of functions for each bit:

ext2fs_new_inode() -> ext2fs_fast_test_inode_bitmap2() [inlined] ->
ext2fs_test_generic_bmap() -> ext2fs_test_generic_bitmap() ->
ext2fs_test_bit().

I also noted that resize2fs does not call ext2fs_open2() with
EXT2_FLAG_64BITS set; is there a reason for that? Adding that flag
change causes a minor speedup by eliminating
ext2fs_test_generic_bitmap() from the call chain.

I don't know if an algorithmic change would be the "proper" solution
for this, but I managed to make the process a lot faster (fast enough
to not be a bottleneck in this case, but perhaps it should also be
tested on both bigger filesystems and SSDs) by changing the following
while trying to affect the performance of other code in libext2fs as
little as possible:

0. Original CPU time: 3400 seconds.

1. Move the modulo out of the loop in ext2fs_new_inode().
   CPU time: 2585 seconds.

2. Call ext2fs_open2() with EXT2_FLAG_64BITS. CPU time: 2057 seconds.

3a. Implement a function, ext2fs_find_first_zero_generic_bmap(), which
    finds the first zero bit in a bitmap. Defaults to doing pretty
    much what ext2fs_new_inode() was doing if the relevant (new)
    function in the bitmap_ops struct is NULL. Change
    ext2fs_new_inode() to use it.

3b. Implement optimized ba_find_first_zero() for bitarray bitmaps.
    Simply scan the bitarray byte by byte to find a value != 0xff.
    CPU time: 45 seconds. This still appears to translate to 45
    seconds real time.

4. Further optimize ba_find_first_zero() to scan in (aligned) 64-bit
   chunks CPU time: 17 seconds

After these optimizations, the wall time taken to resize the same
filesystem has decreased from 96m27s to 39m49s:

# time resize2fs -p $FILESYSTEM 75G
real    39m49.287s
user    0m16.601s
sys     0m26.606s

dumpe2fs output from resulting filesystems before and after my
modifications only differ in last write timestamp. e2fsck -f
$FILESYSTEM reports no problems.

A tentative (or proof of concept) patch is attached. Some concerns
that I have:

1. How should internal errors, like functions returning EINVAL when
   that ostensibly cannot be due to invalid filesystem, be handled?
   Currently ext2fs_new_inode() just propagates the error further:

+                       if (err != ENOENT)
+                               return err; /* Internal error? */

2. My additions in blkmap64_ba.c rely on the availability of
   <stdint.h> and intptr_t (to detect when a pointer is 8-byte
   aligned). Perhaps that should be done in another way if C89
   compatibility is a concern?

3. 64-bit scans might be slower on a system with native register size
   <64 bits. I doubt they will be slower than the code used to be,
   though.

4. What is bitmap->cluster_bits and how should it be handled? in
   ba_find_first_zero(); similar code in
   ext2fs_find_first_zero_generic_bmap():

+       /* FIXME what is this? */
+       if (bitmap->cluster_bits)
+               return EINVAL;

5. Is returning ENOENT the preferred way of indicating "not found"?
   How is this supposed to integrate in the com_err framework?

I'd be happy to update the patch to fix any remaining issues, unless
you think there's another, cleaner solution to the slowness.

By the way, compiling e2fsprogs with -Wall reveals things like missing
headers:

../../lib/ext2fs/ext2fs.h:1712:3: warning: implicit declaration of function ‘open64’ [-Wimplicit-function-declaration]

	Sami


-- System Information:
Debian Release: wheezy/sid
  APT prefers unstable
  APT policy: (500, 'unstable')
Architecture: amd64 (x86_64)

Kernel: Linux 3.2.9 (SMP w/8 CPU cores)
Locale: LANG=en_US.UTF-8, LC_CTYPE=en_US.UTF-8 (charmap=UTF-8)
Shell: /bin/sh linked to /bin/dash

Versions of packages e2fsprogs depends on:
ii  e2fslibs    1.42.1-2
ii  libblkid1   2.20.1-4
ii  libc6       2.13-27
ii  libcomerr2  1.42.1-2
ii  libss2      1.42.1-2
ii  libuuid1    2.20.1-4
ii  util-linux  2.20.1-4

e2fsprogs recommends no packages.

Versions of packages e2fsprogs suggests:
ii  e2fsck-static  1.42.1-2
ii  gpart          <none>
ii  parted         2.3-8

-- no debconf information

[e2fsprogs-faster-inode-scan.patch (text/x-diff, attachment)]

[signature.asc (application/pgp-signature, inline)]

Message #10 received at 663237@bugs.debian.org (full text, mbox, reply):

From: Ted Ts'o <tytso@mit.edu>

To: Sami Liedes <sliedes@cc.hut.fi>, 663237@bugs.debian.org

Subject: Re: Bug#663237: e2fsprogs: [patch] Make resize2fs shrinking use much less CPU

Date: Fri, 9 Mar 2012 14:19:47 -0500

On Fri, Mar 09, 2012 at 08:11:05PM +0200, Sami Liedes wrote:
> Shrinking a filesystem is currently very CPU intensive. On a 100G ext4
> filesystem filled to 50% full by making copies of /usr/share/doc to
> $MNTPOINT/doc{1,2,3,...}, running resize2fs on a fairly slow (~5400
> rpm) disk and a fast Core i7 processor....

Thanks for looking into this!

> I also noted that resize2fs does not call ext2fs_open2() with
> EXT2_FLAG_64BITS set; is there a reason for that? Adding that flag
> change causes a minor speedup by eliminating
> ext2fs_test_generic_bitmap() from the call chain.

Yeah, resize2fs hasn't had work done on it to support 64-bit file
systems, which is why it hasn't been changed to set that flag.  That
flag only means that it was compiled with the new 64-bit capable
header files, though, so it's safe to set that flag.  We just hadn't
gotten around to it.

> After these optimizations, the wall time taken to resize the same
> filesystem has decreased from 96m27s to 39m49s:

Cool!!

> 
> A tentative (or proof of concept) patch is attached. Some concerns
> that I have:
> 
> 1. How should internal errors, like functions returning EINVAL when
>    that ostensibly cannot be due to invalid filesystem, be handled?
>    Currently ext2fs_new_inode() just propagates the error further:
> 
> +                       if (err != ENOENT)
> +                               return err; /* Internal error? */

In general, errors get propagated upwords, although if a function can
recover in some way, or wishes to translate the error from ENOENT to
some new com_err defined code, so that the user gets a more specific
error message (i.e, "Configuration file not found" instead of just
"file not found"), it can do that.

> 2. My additions in blkmap64_ba.c rely on the availability of
>    <stdint.h> and intptr_t (to detect when a pointer is 8-byte
>    aligned). Perhaps that should be done in another way if C89
>    compatibility is a concern?

You could just cast the pointer to an unsigned long before you mask it
with 0x07....  in the highly unlikely case that the pointer is wider
than an unsigned long, it won't matter since you really want to look
at the low three bits anyway.

> 3. 64-bit scans might be slower on a system with native register size
>    <64 bits. I doubt they will be slower than the code used to be,
>    though.

Probably; it's easy enough to test on a 32-bit x86 binary.


> 4. What is bitmap->cluster_bits and how should it be handled? in
>    ba_find_first_zero(); similar code in
>    ext2fs_find_first_zero_generic_bmap():
> 
> +       /* FIXME what is this? */
> +       if (bitmap->cluster_bits)
> +               return EINVAL;
> 

It's something which is only used for "bigalloc" file systems, where
it indicates the cluster size.  With this feature, instead of the
block allocation bitmap indicate block numbers being free, it
indicates "cluster numbers" being free, where a cluster is a power of
two number of blocks.  It's not something you need to worry about in
this context, because resize2fs doesn't support bigalloc file systems
yet, and it doesn't make much difference in terms of how the libext2fs
library functions work.

> 5. Is returning ENOENT the preferred way of indicating "not found"?
>    How is this supposed to integrate in the com_err framework?

What is it that is not being found?  A bit in the bitmap?  In that
case I'd probably define a new com_err error code.

> I'd be happy to update the patch to fix any remaining issues, unless
> you think there's another, cleaner solution to the slowness.

It would be really great if you could break things into small logical
patches, and send them to the linux-ext4 list for review.

Thanks,

						- Ted

Message #15 received at 663237-close@bugs.debian.org (full text, mbox, reply):

From: tytso@mit.edu (Theodore Y. Ts'o)

To: 663237-close@bugs.debian.org

Subject: Bug#663237: fixed in e2fsprogs 1.42.2-1

Date: Wed, 28 Mar 2012 05:32:53 +0000

Source: e2fsprogs
Source-Version: 1.42.2-1

We believe that the bug you reported is fixed in the latest version of
e2fsprogs, which is due to be installed in the Debian FTP archive:

comerr-dev_2.1-1.42.2-1_i386.deb
  to main/e/e2fsprogs/comerr-dev_2.1-1.42.2-1_i386.deb
e2fsck-static_1.42.2-1_i386.deb
  to main/e/e2fsprogs/e2fsck-static_1.42.2-1_i386.deb
e2fslibs-dbg_1.42.2-1_i386.deb
  to main/e/e2fsprogs/e2fslibs-dbg_1.42.2-1_i386.deb
e2fslibs-dev_1.42.2-1_i386.deb
  to main/e/e2fsprogs/e2fslibs-dev_1.42.2-1_i386.deb
e2fslibs_1.42.2-1_i386.deb
  to main/e/e2fsprogs/e2fslibs_1.42.2-1_i386.deb
e2fsprogs-dbg_1.42.2-1_i386.deb
  to main/e/e2fsprogs/e2fsprogs-dbg_1.42.2-1_i386.deb
e2fsprogs-udeb_1.42.2-1_i386.udeb
  to main/e/e2fsprogs/e2fsprogs-udeb_1.42.2-1_i386.udeb
e2fsprogs_1.42.2-1.debian.tar.gz
  to main/e/e2fsprogs/e2fsprogs_1.42.2-1.debian.tar.gz
e2fsprogs_1.42.2-1.dsc
  to main/e/e2fsprogs/e2fsprogs_1.42.2-1.dsc
e2fsprogs_1.42.2-1_i386.deb
  to main/e/e2fsprogs/e2fsprogs_1.42.2-1_i386.deb
e2fsprogs_1.42.2.orig.tar.gz
  to main/e/e2fsprogs/e2fsprogs_1.42.2.orig.tar.gz
libcomerr2-dbg_1.42.2-1_i386.deb
  to main/e/e2fsprogs/libcomerr2-dbg_1.42.2-1_i386.deb
libcomerr2_1.42.2-1_i386.deb
  to main/e/e2fsprogs/libcomerr2_1.42.2-1_i386.deb
libss2-dbg_1.42.2-1_i386.deb
  to main/e/e2fsprogs/libss2-dbg_1.42.2-1_i386.deb
libss2_1.42.2-1_i386.deb
  to main/e/e2fsprogs/libss2_1.42.2-1_i386.deb
ss-dev_2.0-1.42.2-1_i386.deb
  to main/e/e2fsprogs/ss-dev_2.0-1.42.2-1_i386.deb



A summary of the changes between this version and the previous one is
attached.

Thank you for reporting the bug, which will now be closed.  If you
have further comments please address them to 663237@bugs.debian.org,
and the maintainer will reopen the bug report if appropriate.

Debian distribution maintenance software
pp.
Theodore Y. Ts'o <tytso@mit.edu> (supplier of updated e2fsprogs package)

(This message was generated automatically at their request; if you
believe that there is a problem with it please contact the archive
administrators by mailing ftpmaster@debian.org)


-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Format: 1.8
Date: Tue, 27 Mar 2012 15:55:57 -0700
Source: e2fsprogs
Binary: e2fsck-static libcomerr2 comerr-dev libss2 ss-dev e2fsprogs-udeb e2fslibs e2fslibs-dev e2fsprogs e2fsprogs-dbg e2fslibs-dbg libcomerr2-dbg libss2-dbg
Architecture: source i386
Version: 1.42.2-1
Distribution: unstable
Urgency: low
Maintainer: Theodore Y. Ts'o <tytso@mit.edu>
Changed-By: Theodore Y. Ts'o <tytso@mit.edu>
Description: 
 comerr-dev - common error description library - headers and static libraries
 e2fsck-static - statically-linked version of the ext2/ext3/ext4 filesystem checke
 e2fslibs   - ext2/ext3/ext4 file system libraries
 e2fslibs-dbg - debugging information for e2fslibs
 e2fslibs-dev - ext2/ext3/ext4 file system libraries - headers and static librari
 e2fsprogs  - ext2/ext3/ext4 file system utilities
 e2fsprogs-dbg - debugging information for e2fsprogs
 e2fsprogs-udeb - stripped-down versions of e2fsprogs, for debian-installer (udeb)
 libcomerr2 - common error description library
 libcomerr2-dbg - debugging information for libcomerr2
 libss2     - command-line interface parsing library
 libss2-dbg - debugging information for libss2
 ss-dev     - command-line interface parsing library - headers and static libra
Closes: 663237 665427 665885
Changes: 
 e2fsprogs (1.42.2-1) unstable; urgency=low
 .
   * New upstream version
   * Fixed various man pages (Closes: #665427)
   * Speed up resize2fs for large file systems (Closes: #663237)
   * Be less strict about the EXT4_EOFBLOCKS_FL flag (which will
     eventually be going away in the ext4 file system format)
   * Teach mke2fs to use direct I/O if the -D option is given
   * Print errors returned by ext2fs_open2() and ext2fs_check_desc() so
     we can more easily diagnose memory allocation failures caused by
     insufficient memory and abort on memory allocation failures
   * E2fsck can now write log files containing the details of the
     problems that were found and fixed directly.
   * E2fsck can now limit the number of messages issued and printed on
     the console
   * The dumpe2fs, debugfs, and tune2fs now use rbtree bitmaps, which
     cause them to use much less memory for large file systems.
   * E2fsck will now check for zero-length extents, since older kernels will
     OOPS if they comes across one
   * Fix e2fsck's discard behaviour so it does not discard too many
     blocks, and it will not use discard if the device advertises
     that discard does not persistently zero data.  Also, if e2fsck is
     run in read-only mode, do not try to discard data.
   * Fix mke2fs -S so it does not corrupt the first block group's
     information.
   * Add pointer for e2fsprogs-udeb to libcomerr2.shlibs (Closes: #665885)
Checksums-Sha1: 
 19952666d35a9dea88c38e32784ea0f073eb2972 1828 e2fsprogs_1.42.2-1.dsc
 bfba3716b78310cf2a288909f13214a718d91e25 5753009 e2fsprogs_1.42.2.orig.tar.gz
 3333469f967332a8a41aa0dad551bf917b7ba29c 70519 e2fsprogs_1.42.2-1.debian.tar.gz
 624a7a5768a63db1aabd3106dab079f79dd1f343 536664 e2fsck-static_1.42.2-1_i386.deb
 7363285262f26cbffc54856c299426e7e29f4420 54730 libcomerr2_1.42.2-1_i386.deb
 5c09d2269f28f847092d4b974869701da8d35d31 59738 libss2_1.42.2-1_i386.deb
 47932b5e20eb08b97b8857631e4c1e32ce760028 210066 e2fslibs_1.42.2-1_i386.deb
 8b9f957ca9adcbbad1ceecaa1a770bcfee39218e 247274 e2fslibs-dev_1.42.2-1_i386.deb
 319e807e290ce08671a6727659359a850bdf5b32 993998 e2fsprogs_1.42.2-1_i386.deb
 790a7c42fda494c4050e0cb8f2abd87afea6d217 1246252 e2fsprogs-dbg_1.42.2-1_i386.deb
 5f923bdf11660a1a78fddf4013f5dd3554d61e11 354518 e2fslibs-dbg_1.42.2-1_i386.deb
 c383fbab763a2d6ef80b3adb1c828b341e17f841 57346 libcomerr2-dbg_1.42.2-1_i386.deb
 c7f23ed6a2fc237cf5aed74f1991e274b8949776 67348 libss2-dbg_1.42.2-1_i386.deb
 3456bd1d541e9bcb64e4432f4df7761c7518d523 43360 comerr-dev_2.1-1.42.2-1_i386.deb
 50f76f8a5fe0c00aca252f409b7d36fe0f976afd 18614 ss-dev_2.0-1.42.2-1_i386.deb
 d36efd74093fd21c9e0fbd963b30452d04b20d56 337632 e2fsprogs-udeb_1.42.2-1_i386.udeb
Checksums-Sha256: 
 1d7b5174ee26665fa8e39fb02e41091d73764a04ada18a3dd9950851fc1bd499 1828 e2fsprogs_1.42.2-1.dsc
 1d36fec5e34ac285f59dff3851d6f4ca9f0b964ddd7e8fe00f1f920b091cb8be 5753009 e2fsprogs_1.42.2.orig.tar.gz
 78c02634a53b860d7ca87006ca53cc5e15f66c25fba2f9288c46d4077c512159 70519 e2fsprogs_1.42.2-1.debian.tar.gz
 7a285c1160e950fc5cdea91d3d1e90b9c2d71c87cbc6447f143bd3e3b3a16d40 536664 e2fsck-static_1.42.2-1_i386.deb
 d07f20ae84c5f325d9ab95e0825fcc6f4deea7204f45b670d4ed7dbdc775d989 54730 libcomerr2_1.42.2-1_i386.deb
 01cbd9e60f210dfa44ceeba39b7413b83a95e26609abacdf1a6c1e0e577b9adc 59738 libss2_1.42.2-1_i386.deb
 60bed9bf7192ed9a616d1726423273e38049a951cdb447e253ab5ae3691413ae 210066 e2fslibs_1.42.2-1_i386.deb
 4869229ddff781a7e42aa1bc6b9b7eafcac9065c6233cb9c7f0f80a12a3f6e57 247274 e2fslibs-dev_1.42.2-1_i386.deb
 66dda6a4cf20c128e03fa5c2cf195b35887952da0d6ff7025b7f2a669a26259a 993998 e2fsprogs_1.42.2-1_i386.deb
 cc0b41904357ad91240d4be7a934665433fe21536353c0ef5abd891cd9c652a7 1246252 e2fsprogs-dbg_1.42.2-1_i386.deb
 ed8db367511bb59b0f8a60281d33cffedfb3701dfb200e6f0e24229b1c93ffc7 354518 e2fslibs-dbg_1.42.2-1_i386.deb
 7b2edf133ff080d2f2224ae523f74bedb33698da606d0f9f7b4cd6bc8ccd2bdc 57346 libcomerr2-dbg_1.42.2-1_i386.deb
 f3bb6e20119d4138d1b1ffe652caeffcd279a6928330485264040b6e4c9dafd4 67348 libss2-dbg_1.42.2-1_i386.deb
 748e9a7c98c0b034cdff9775fa80e80db88c12d971e160f86c2d668ed33e0526 43360 comerr-dev_2.1-1.42.2-1_i386.deb
 8ee14829b8500eefa84036623ea91953b96cbe8979ecaf99f52ad969c4504304 18614 ss-dev_2.0-1.42.2-1_i386.deb
 ee8f01c61468d3c8fbd9ce371d7c16fd1246d66bf8dcab4f4ffe423bcfb59a3c 337632 e2fsprogs-udeb_1.42.2-1_i386.udeb
Files: 
 fee62fb166b989dcc5d7413323c7fada 1828 admin required e2fsprogs_1.42.2-1.dsc
 04f4561a54ad0419248316a00c016baa 5753009 admin required e2fsprogs_1.42.2.orig.tar.gz
 85567de61eeb55a07fdfbc7f0d3be8c4 70519 admin required e2fsprogs_1.42.2-1.debian.tar.gz
 d9efc67ae46ae54b7e9d709732cab98f 536664 admin optional e2fsck-static_1.42.2-1_i386.deb
 026bc9e0689bf97d430adb9f1526f50d 54730 libs required libcomerr2_1.42.2-1_i386.deb
 1fbc05196b04d5ed858f69eaf77312ac 59738 libs required libss2_1.42.2-1_i386.deb
 ac39e93bcc705aac5c30910315432cb9 210066 libs required e2fslibs_1.42.2-1_i386.deb
 8d63375b9c121c8220ee321c3572923d 247274 libdevel extra e2fslibs-dev_1.42.2-1_i386.deb
 7c36a08070e701d769b55ab7958d214a 993998 admin required e2fsprogs_1.42.2-1_i386.deb
 93d570b42c50411b4c88d30b77f773cd 1246252 debug extra e2fsprogs-dbg_1.42.2-1_i386.deb
 6e9c66ba24f52d5f76a82a11a6fedc49 354518 debug extra e2fslibs-dbg_1.42.2-1_i386.deb
 695b559e74227212869b662b8692178c 57346 debug extra libcomerr2-dbg_1.42.2-1_i386.deb
 858b3ad6f08577f183a8679d2a96d75b 67348 debug extra libss2-dbg_1.42.2-1_i386.deb
 3f9ff88e9ae2c05acf7a369334c5f143 43360 libdevel extra comerr-dev_2.1-1.42.2-1_i386.deb
 bc156ae822714bb18e89a0ce2c7b7d5b 18614 libdevel extra ss-dev_2.0-1.42.2-1_i386.deb
 2511e8e02c8b5f1bc127682f9425fbf9 337632 debian-installer optional e2fsprogs-udeb_1.42.2-1_i386.udeb
Package-Type: udeb

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.12 (GNU/Linux)

iEYEARECAAYFAk9yTJMACgkQ7To545NnTEA87wCgmaOp2bzBc3qiS5cQx/tfyoie
B4UAoNlvYGR+rKBksBCTzhyqLR0YHjB3
=S4G5
-----END PGP SIGNATURE-----

Send a report that this bug log contains spam.