misc: fix clang warnings and a resource leak

Signed-off-by: Darrick J. Wong <darrick.wong@oracle.com>
debugfs: document new commands

Document the new journal and xattr commands in the debugfs manpage.

Signed-off-by: Darrick J. Wong <darrick.wong@oracle.com>
libext2fs: zero blocks via FALLOC_FL_ZERO_RANGE in ext2fs_zero_blocks

Plumb a new call into the IO manager to support translating
ext2fs_zero_blocks calls into the equivalent FALLOC_FL_ZERO_RANGE
fallocate flag primitive when possible.  This patch provides _only_
support for file-based images.

v2: Remove zero-out for block devices until BLKZEROOUT is cleaned up.

Signed-off-by: Darrick J. Wong <darrick.wong@oracle.com>
libext2fs: ext2fs_new_block2() should call alloc_block hook

If ext2fs_new_block2() is called without a specific block map, we
should call the alloc_block hook before checking fs->block_map.  This
helps us to avoid a bug in e2fsck where we need to allocate a block
but instead of consulting block_found_map, we use the FS bitmaps,
which (prior to pass 5) could be wrong.

Signed-off-by: Darrick J. Wong <darrick.wong@oracle.com>
tune2fs: disable csum verification before resizing inode

When we're turning on metadata checksumming /and/ resizing the inode
at the same time, disable checksum verification during the
resize_inode() call because the subroutines it calls will try to
verify the checksums (which have not yet been set), causing the
operation to fail unnecessarily.

Signed-off-by: Darrick J. Wong <darrick.wong@oracle.com>
e2fsck: clear i_block[] when there are too many bad mappings on a special inode

If we decide to clear a special inode because of bad mappings, we need
to zero the i_block array.  The clearing routine depends on setting
i_links_count to zero to keep us from re-checking the block maps,
but that field isn't checked for special inodes.  Therefore, if we
haven't erased the mappings, check_blocks will restart fsck and fsck
will try to check the blocks again, leading to an infinite loop.

Signed-off-by: Darrick J. Wong <darrick.wong@oracle.com>
libext2fs/e2fsck: provide routines to read-ahead metadata

This patch adds to e2fsck the ability to pre-fetch metadata into the
page cache in the hopes of speeding up fsck runs.  There are two new
functions -- the first allows a caller to readahead a list of blocks,
and the second is a helper function that uses that first mechanism to
load group data (bitmaps, inode tables).

These new e2fsck routines require the addition of a dblist API to
allow us to iterate a subset of a dblist.  This will enable
incremental directory block readahead in e2fsck pass 2.

There's also a function to estimate the readahead given a FS.

v2: Add an API to create a dblist with a given number of list elements
pre-allocated.  This enables us to save ~2ms per call to
e2fsck_readahead() (assuming a 2MB RA buffer) by not having to
repeatedly call ext2_resize_mem as we add blocks to the list.

v3: Instead of creating dblists of arbitrary size, change the dblist
iterator to allow iterating a sub-range.  This eliminates a lot of
unnecessary list copying during e2fsck part2.

Signed-off-by: Darrick J. Wong <darrick.wong@oracle.com>
e2fsck: read-ahead metadata during passes 1, 2, and 4

e2fsck pass1 is modified to use the block group data prefetch function
to try to fetch the inode tables into the pagecache before it is
needed.  We iterate through the blockgroups until we have enough inode
tables that need reading such that we can issue readahead; then we sit
and wait until the last inode table block read of the last group to
start fetching the next bunch.

pass2 is modified to use the dirblock prefetching function to prefetch
the list of directory blocks that are assembled in pass1.  We use the
"iterate a subset of a dblist" and avoid copying the dblist.  Directory
blocks are fetched incrementally as we walk through the directory
block list.  In previous iterations of this patch we would free the
directory blocks after processing, but the performance hit to e2fsck
itself wasn't worth it.  Furthermore, it is anticipated that most
users will then mount the FS and start using the directories, so they
may as well remain in the page cache.

pass4 is modified to prefetch the block and inode bitmaps in
anticipation of pass 5, because pass4 is entirely CPU bound.

In general, these mechanisms can decrease fsck time by 10-40%, if the
host system has sufficient memory and the storage system can provide a
lot of IOPs.  Pretty much any storage system capable of handling
multiple IOs in-flight at any time will see a fairly large performance
boost.  (Single-issue USB mass storage disks seem to suffer badly.)

By default, the readahead buffer size will be set to the size of a block
group's inode table (which is 2MiB for a regular ext4 FS).  The -E
readahead_kb= option can be given to specify the amount of memory to
use for readahead or zero to disable it entirely; or an option can be
given in e2fsck.conf.

v2: Fix an off-by-one error in the pass1 readahead which made the
readahead trigger one inode too late if the block groups are full.

v3: Use the dblist partial iterator function to read ahead parts
of the directory block list in pass 2, instead of making sublists.

Signed-off-by: Darrick J. Wong <darrick.wong@oracle.com>
e2fsck: track directories to be rehashed with a bitmap

Use a bitmap to track which directories we want to rehash, since
bitmaps will use less memory.  This enables us to clean up the
rehash-all case to use inode_dir_map, and we can free the dirinfo
memory sooner.

Signed-off-by: Darrick J. Wong <darrick.wong@oracle.com>
e2fsck: rebuild sparse extent trees/convert non-extent ext3 files

Teach e2fsck to (re)construct extent trees.  This enables us to do
either of the following: compress a highly sparse extent tree into
fewer ETB blocks; or convert a ext3-style block mapped file to an
extent file.  The reconstruction is performed during pass 1E or 3A,
as detailed below.

For files that are already extent based, this algorithm will
automatically run (pending user approval) if pass1 determines either
(1) that a whole level of extent tree will fit into a higher level of
the tree; (2) that the size of any level can be reduced by at least
one ETB block; or (3) the extent tree is unnecessarily deep.  It will
not run at all if errors are found and the user declines to fix the
errors.

The option "-E bmap2extent" can be used to force e2fsck to convert all
block map files to extent trees, and to rebuild all extent files'
extent trees.  After conversion, files larger than 12 blocks should be
defragmented to eliminate empty holes where a block lives.

The extent tree constructor is pretty dumb -- it creates a list of
leaf extents (adjacent extents are collapsed), marks all indirect
blocks / ETB blocks free, installs a new extent tree root in the
inode, then loads the leaf extents into the tree.

v2: Account for extent tree block slack that we create when splitting
a block, so that we don't repeatedly annoy the user to rebuild a tree
that we can't optimize further.

v3: For any directory being rebuilt during pass 3A, defer any extent
tree rebuilding until after the rehash.  It's quite possible that the
act of compressing an aged directory will cause it to shrink far
enough to enable us to knock a level off the dir's extent tree.

Signed-off-by: Darrick J. Wong <darrick.wong@oracle.com>
tests: verify proper rebuilding of sparse extent trees and block map file conversion

Signed-off-by: Darrick J. Wong <darrick.wong@oracle.com>
undo-io: add new calls to and speed up the undo io manager

Implement pass-through calls for discard, zero-out, and readahead in
the IO manager so that we can take advantage of any underlying
support.

Furthermore, improve tdb write-out speed by disabling locking and only
fsyncing at the end -- we don't care about locking because having
multiple writers to the undo file will produce an undo database full
of garbage blocks; and we only need to fsync at the end because if we
fail before the end, our undo file will lack the necessary superblock
data that e2undo requires to do replay safely.  Without this, we call
fsync four times per tdb update(!)  This reduces the overhead of using
undo_io while converting a 2TB FS to metadata_csum from 3+ hours to 55
minutes.

Signed-off-by: Darrick J. Wong <darrick.wong@oracle.com>
undo-io: be more flexible about setting block size

Most of the e2fsprogs utilities set the IO block size multiple times
(once to 1k to read the superblock, then again to set the real block
size if we find a real superblock).  Unfortunately, the undo IO
manager only lets the block size be set once.  For the non-mke2fs
utilities we'd rather catch the real block size and use that.  mke2fs
of course wants to use a really large block size since it's probably
writing a lot of data.

Therefore, if we haven't written any blocks to the undo file, it's
perfectly fine to allow block size changes.  For mke2fs, we'll modify
the IO channel option that lets us set the huge size to lock that
in place.  This greatly reduces index overhead for undo files for
e2fsck/tune2fs/resize2fs while continuing the practice of reducing
it even more for mke2fs.

Signed-off-by: Darrick J. Wong <darrick.wong@oracle.com>
undo-io: use a bitmap to track what we've already written

It's really inefficient to (ab)use the TDB key store as a bitmap to
find out if we've already written a block to the undo file, because
the tdb code is reads the database key btree disk blocks for *every*
query.  Changing that logic to a bitmap reduces overhead by a large
margin -- the overhead of using undo_io while converting a 2TB FS to
metadata_csum is reduced from 55 minutes to 45.

Signed-off-by: Darrick J. Wong <darrick.wong@oracle.com>
e2undo: fix memory leaks and tweak the error messages somewhat

Fix memory leaks and improve the error messages to make it easier
to figure out why e2undo went wrong.

Signed-off-by: Darrick J. Wong <darrick.wong@oracle.com>
e2undo: ditch tdb file, write everything to a flat file

The existing undo file format (which is based on tdb) has many
problems.  First, its comparison of superblock fields is ineffective,
since the last mount time is only written by the kernel, not the tools
(which means that undo files can be applied out of order, thus
corrupting the filesystem); block numbers are written in CPU byte
order, which will cause silent failures if an undo file is moved from
one type of system to another; using the tdb database costs us an
enormous amount of CPU overhead to maintain the key data structure,
and finally, the tdb database is unable to deal with databases larger
than 2GB.  (Upstream tdb 1.2.12 can handle 4GB, but upgrading a 2TB FS
to 64bit,metadata_csum easily produces 4.5GB of undo files, so we
might as well move off of tdb now.)

The last problem is fatal if you want to use tune2fs to turn on
metadata checksumming, since that rewrites every block on the
filesystem, which can easily produce a many-gigabyte undo file, which
of course is unreadable and therefore the operation cannot be undone.

Therefore, rip all of that out in favor of writing to a flat file.
Old blocks are appended to a file and the index is written to the end
when we're done.  This implementation is much faster than wasting a
considerable amount of time trying to maintain a hash index, which
drops the runtime overhead of tune2fs -O metadata_csum from ~45min
to ~20 seconds on a 2TB filesystem.

I have a few reasons that factored in my decision not to repurpose the
jbd2 file format for undo files.  First, undo files are limited to
2^32 blocks (16TB) which some day might not serve us well.  Second,
the journal block size is tied to the file system block size, but
mke2fs wants to be able to back up big chunks of old device contents.
This would require large changes to the e2fsck journal replay code,
which itself is derived from the kernel jbd2 driver, which I'd rather
not destabilize.  Third, I want to require undo files to store the FS
superblock at the end of undo file creation so that e2undo can be
reasonably sure that an undo file is supposed to apply against the
given block device, and doing so would require changes to the jbd2
format.  Fourth, it didn't seem like a good idea that external
journals should resemble undo files so closely.

Signed-off-by: Darrick J. Wong <darrick.wong@oracle.com>
e2fsck: optionally create an undo file

Provide the user with an option to create an undo file so that they
can roll back a failed repair operation.

Signed-off-by: Darrick J. Wong <darrick.wong@oracle.com>
resize2fs: optionally create undo file

Provide the user with an option to create an undo file so that they
can roll back a failed resize operation.

Signed-off-by: Darrick J. Wong <darrick.wong@oracle.com>
tune2fs: optionally create undo file

Provide the user with an option to create an undo file so that they
can roll back a failed tuning operation.  Previously, one would be
created for inode resize if a bunch of (undocumented) conditions were
met.

Signed-off-by: Darrick J. Wong <darrick.wong@oracle.com>
mke2fs: optionally create undo file

Provide the user with an option to create an undo file so that they
can roll back a failed tuning operation.  Previously, one would be
created if force_undo was set in the configuration file and a bunch of
(undocumented) conditions were met.

Signed-off-by: Darrick J. Wong <darrick.wong@oracle.com>