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>
resize2fs: don't mark unallocated bg metadata blocks when fixing bg flags

When fixing up block group bitmaps on the new fs, don't try to mark
unallocated group metadata blocks; these will be allocated (and
marked) later.

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.

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

Teach e2fsck to 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.

For files that are already extent based, this algorithm will only run
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.

For block-mapped files, conversion only happens if the extent feature
is enabled and "-E bmap2extent" is passed to e2fsck.  It will not run
at all if errors are left unfixed.  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 pass 3B (which is really just 1E).

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>
libext2fs: 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.

Signed-off-by: Darrick J. Wong <darrick.wong@oracle.com>
e2undo: 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 put in
a new IO channel option that lets us set the huge size and lock that
in place.  This greatly reduces index overhead for undo files for
e2fsck/tune2fs/resize2fs while reducing it even more for mke2fs.

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

Don't use the hash to track blocks that we already wrote.
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>
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>
tests: test undo file creation in e2fsck/resize2fs/tune2fs/mke2fs

Regression tests to ensure that we can create undo files and roll
things back if need be.

Signed-off-by: Darrick J. Wong <darrick.wong@oracle.com>
libext2fs: support allocating uninit blocks in bmap2()

As part of supporting fallocate-like functionality, extend
ext2fs_bmap() with two flags -- BMAP_UNINIT and BMAP_ZERO.  The first
will cause it to mark/set a block uninitialized, if it's part of an
extent based file.  For a block mapped file, the mapping is put in,
but there is no way to remember the uninitialized status.  The second
flag causes the block to be zeroed to support the use case of
emulating uninitialized blocks on a block-map file by zeroing them.

Eventually fallocate or fuse2fs or somebody will use these.

Signed-off-by: Darrick J. Wong <darrick.wong@oracle.com>
libext2fs: find/alloc a range of empty blocks

Provide a function that, given a goal pblk and a range, will try to
find a run of free blocks to satisfy the allocation.  By default the
function will look anywhere in the filesystem for the run, though this
can be constrained with optional flags.  One flag indicates that the
range must start at the goal block; the other flag indicates that we
should not return a range shorter than len.

v2: Add a second function to allocate a range of blocks.

Signed-off-by: Darrick J. Wong <darrick.wong@oracle.com>
libext2fs: add new hooks to support large allocations

Add a new get_alloc_blocks hook and a block_alloc_stats_range hook so
that e2fsck can capture allocation requests spanning more than a
block to its block_found_map.

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

Create a library function to perform fallocation on arbitrary files,
and wire up a few users for this function.  This is a bit more intense
than Ted's original mk_hugefiles implementation since we have to honor
any blocks that may already be allocated to the file.

Signed-off-by: Darrick J. Wong <darrick.wong@oracle.com>
libext2fs: use fallocate for creating journals and hugefiles

Use the new fallocate API for creating the journal and the mk_hugefile
feature.

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