e2fuzz: Create a tool to fuzz ext* filesystems

Creates a program that fuzzes only the metadata blocks (or optionally
all in-use blocks) of an ext* filesystem.  There's also a script to
automate fuzz testing of the kernel and e2fsck in a loop.

[ Modified by tytso to add e2fuzz to the clean makefile rule ]

Signed-off-by: Darrick J. Wong <darrick.wong@oracle.com>
Signed-off-by: Theodore Ts'o <tytso@mit.edu>
build: fix unused/uninitialized variable warnings

Fix a few warnings about unused and uninitialized variables.

Also fix util/subst.c to include <sys/time.h> to avoid using
undeclared functions gettimeofday() and futimes().

Signed-off-by: Andreas Dilger <adilger@dilger.ca>
Signed-off-by: Theodore Ts'o <tytso@mit.edu>
tests: use e2fsck -f instead of -p for resize tests

Using e2sck -f provides better debugging information if things go
wrong.

Signed-off-by: Theodore Ts'o <tytso@mit.edu>
libext2fs: fix rb_resize_bmap to handle the padding bits

The bits between end and real_end are set as a safety measure for the
kernel when it uses the bit scan instructions.  We need to take this
into account when shrinking or growing the block allocation bitmap,
before we can safely use rbtree bitmaps in resize2fs.

Signed-off-by: Theodore Ts'o <tytso@mit.edu>
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>
libext2fs: use C99 initializers for the io_manager structure

Using C99 initializers makes the code a bit more readable, and it
avoids some gcc -Wall warnings regarding missing initializers.

Signed-off-by: Theodore Ts'o <tytso@mit.edu>
Fix 32/64-bit overflow when multiplying by blocks/clusters per group

There are a number of places where we need convert groups to blocks or
clusters by multiply the groups by blocks/clusters per group.
Unfortunately, both quantities are 32-bit, but the result needs to be
64-bit, and very often the cast to 64-bit gets lost.

Fix this by adding new macros, EXT2_GROUPS_TO_BLOCKS() and
EXT2_GROUPS_TO_CLUSTERS().

This should fix a bug where resizing a 64bit file system can result in
calculate_minimum_resize_size() looping forever.

Addresses-Launchpad-Bug: #1321958

Signed-off-by: Theodore Ts'o <tytso@mit.edu>
libext2fs: fix free block accounting for 64-bit file systems

We rely on a nasty hack to adjust the free block count where we pass
signed value into ext2fs_free_blocks_count_add(), which takes an
64-bit unsigned value, and relies on overflow and C's signed->unsigned
semantics to do the subtraction.  This works, so long as a 64-bit
signed value is used.

Unfortunately, ext2fs_block_alloc_stats2() and
ext2fs_block_alloc_stats_range(), this is not true, so on a 64-bit
file system, the free blocks accounting can get screwed up.

A simple way to demonstrate the problem is:

mke2fs -F -t ext4 -O 64bit /tmp/foo.img 1M
e2fsck -fy /tmp/foo.img

... which will result in the following e2fsck complaint:

Pass 5: Checking group summary information
Free blocks count wrong (4294968278, counted=982).
Fix? yes

Signed-off-by: Theodore Ts'o <tytso@mit.edu>
Merge branch 'maint' into next

Conflicts:
	debugfs/debugfs.c
	e2fsck/pass5.c
libext2fs: provide a function to set inode size

Provide an API to set i_size in an inode and take care of all required
feature flag modifications.  Refactor the code to use this new
function.

[ Moved the function to lib/ext2fs/blk_num.c, which is the rest of
  these sorts of functions live, and renamed it to be
  ext2fs_inode_size_set() instead of ext2fs_inode_set_size() to be
  consistent with the other functions in in blk_num.c -- tytso ]

Signed-off-by: Darrick J. Wong <darrick.wong@oracle.com>
Signed-off-by: Theodore Ts'o <tytso@mit.edu>
e2fsck: reserve blocks for root/lost+found directory repair

If we think we're going to need to repair either the root directory or
the lost+found directory, reserve a block at the end of pass 1 to
reduce the likelihood of an e2fsck abort while reconstructing
root/lost+found during pass 3.

If / and/or /lost+found are corrupt and duplicate processing in pass
1b allocates all the free blocks in the FS, fsck aborts with an
unusable FS since pass 3 can't recreate / or /lost+found.  If either
of those directories are missing, an admin can't easily mount the FS
and access the directory tree to move files off the injured FS and
free up space; this in turn prevents subsequent runs of e2fsck from
being able to continue repairs of the FS.

(One could migrate files manually with debugfs without the help of
path names, but it seems easier if users can simply mount the FS and
use regular FS management tools.)

[ Fixed up an obvious C trap: const char * and const char [] are not
  the same thing when you are taking the size of the parameter.
  People, run your regression tests!  Like spinach, it's good for you.  :-)
  -- tytso ]

Signed-off-by: Darrick J. Wong <darrick.wong@oracle.com>
Signed-off-by: Theodore Ts'o <tytso@mit.edu>
Merge branch 'maint' into next

Conflicts:
	debugfs/debugfs.c
	e2fsck/pass1.c
e2fsck: fix merge error in "clear uninit flag on directory extents"

In the original patch (against -next), the hunk to fix uninit dirs was
just prior to the hunk labelled "Corrupt but passes checks?".  The
hunks are ordered this way so that if e2fsck obtains permission to fix
a failed-csum extent (which in turn fixes the checksum), it will not
subsequently ask to (re)fix the checksum.

Due to a merge error the hunk moved to the wrong place, so put it
back.

Signed-off-by: Darrick J. Wong <darrick.wong@oracle.com>
Signed-off-by: Theodore Ts'o <tytso@mit.edu>
e2fsck: perform implied cluster allocations when filling a directory hole

If we're filling a directory hole, we need to perform an implied
cluster allocation to satisfy the bigalloc rule of mapping only one
pblk to a logical cluster.

Signed-off-by: Darrick J. Wong <darrick.wong@oracle.com>
Signed-off-by: Theodore Ts'o <tytso@mit.edu>
e2fsck: fix rule-violating lblk->pblk mappings on bigalloc filesystems

As far as I can tell, logical block mappings on a bigalloc filesystem are
supposed to follow a few constraints:

 * The logical cluster offset must match the physical cluster offset.
 * A logical cluster may not map to multiple physical clusters.

Since the multiply-claimed block recovery code can be used to fix these
problems, teach e2fsck to find these transgressions and fix them.

Signed-off-by: Darrick J. Wong <darrick.wong@oracle.com>
Signed-off-by: Theodore Ts'o <tytso@mit.edu>
e2fsck: during pass1b delete_file, only free a cluster once

If we're forced to delete a crosslinked file, only call
ext2fs_block_alloc_stats2() on cluster boundaries, since the block
bitmaps are all cluster bitmaps at this point.  It's safe to do this
only once per cluster since we know all the blocks are going away.

Signed-off-by: Darrick J. Wong <darrick.wong@oracle.com>
Signed-off-by: Theodore Ts'o <tytso@mit.edu>
Merge branch 'maint' into next

Conflicts:
	e2fsck/pass1b.c
e2fsck: fix the various checksum error messages

Make the "EA block passes checks but fails checksum" message less
strange, and make the other checksum error messages actually print a
period at the end of the sentence.

Signed-off-by: Darrick J. Wong <darrick.wong@oracle.com>
Signed-off-by: Theodore Ts'o <tytso@mit.edu>
e2fsck: insert a missing dirent tail for checksums if possible

If e2fsck is writing a block of directory entries to disk, it should
adjust the dirents to add the dirent tail if one is missing.  It's not
a big deal if there's no space to do this since rehash (pass 3A) will
reconstruct directories for us.  However, we may as well avoid
unnecessary work.

Signed-off-by: Darrick J. Wong <darrick.wong@oracle.com>
Signed-off-by: Theodore Ts'o <tytso@mit.edu>
e2fsck: write dir blocks after new inode when reconstructing root/lost+found

If we trash the root directory block, e2fsck will find inode 11 (the
old lost+found) and try to attach it to l+f.  The lost+found checker
also fails to find l+f and tries to add one to the root dir.  The root
dir is not found but is recreated with incorrect checksums, so linking
in the l+f dir fails and the l+f '..' entry isn't set.  Since both
dirs now fail checksum verification, they're both referred to rehash
to have that fixed, but because l+f doesn't have a '..' entry, rehash
crashes because l+f has < 2 entries.

On a checksumming filesystem, the routines in e2fsck that recreate
/lost+found and / must write the new directory block *after* the inode
has been written to disk because the checksum depends on i_generation.
Add a regression test while we're at it.

Signed-off-by: Darrick J. Wong <darrick.wong@oracle.com>
Signed-off-by: Theodore Ts'o <tytso@mit.edu>