HOW CONVERTFS WORKS
-------------------

Convertfs is a cool idea by Serguei Tzukanov.  This idea has been further
discussed and developed by several people (including myself) on the
bug-parted and ntfs-devel mailing lists, and #xfs IRC channel.

It is available from here:

	http://tzukanov.narod.ru/convertfs

Convertfs can be used to do in-place conversion and resize.  It is
quite linux-dependent, although there are probably analogous ways to
do this on other operating systems.


CONTENTS:
---------
1. The Basic Algorithm
2. In-place LVM conversion
3. File system resizing on top of LVM, without inode-renumbering


1. THE BASIC ALGORITHM
----------------------
Here's the basic algorithm:

(1) mount the file system you wish to "convert" (or resize).

(2) create a sparse file inside that file system, of the size you wish
your new fs to be.  This is done by seek(2)ing to the desired size,
and write(2)ing something.  (Note: in modern filesystems, this doesn't
allocate (m)any blocks)

(3) run mkfs on that sparse file, using the mkfs of the file system type
you wish to convert to.  (mkfs must not write blank 0's in free space)
I'll call this new filesystem the "nested" file system.

(4) mount the nested file system.  (mount -o loopback ...)

(5) mv(1) everything in the old file system to the nested one, except
the nested file system itself ;)

(6) unmount the nested filesystem

(7) use the FIBMAP ioctl to find out where the blocks of the nested file
system are.  (Some of them will be unallocated).  Store this somewhere.

(8) unmount the old file system

(9) move all blocks into their correct places, to "activate" the nested
file system.  That is, copy all the (allocated) blocks from the file
containing the nested file system to their absolute positions.  You
can find these blocks from the output of part (7).
	This destroys the old file system, and creates the new one
in-place.

This algorithm executes in roughly O(N) time, where N is the size of
the file system, since it must reconstruct the file system.


2. IN-PLACE LVM CONVERSION
--------------------------
Here's an algorithm for converting a partition containing a file system
to an LVM physical volume which contains a single logical volume containing
the original file system, in place.  It's a bit pie-in-the-sky, because
it would probably require file systems to support having "holes" on
the devices they store themselves on.  But I think that's a really valuable
thing.  The algorithm:

(1) Figure out how much metadata will be needed at the start of
the partition.  [Ask LVM somehow?]  Anyway, call this number METADATA-SIZE

(2) Mount the file system on the partition.

(3) Create a file of size METADATA-SIZE (from step 1), and fill it with
0's.  Call that file "start-copy".

(4) Get the addresses of the blocks of the file "start-copy" via
the FIBMAP ioctl.  Store them somewhere.

(5) Unmount the file system.

(6) Copy the first METADATA-SIZE (from step 1) of the partition into
"start-copy".  We do this by copying to the appropriate blocks obtained
from step 4.

(7) Use the usual LVM utilities to create a physical volume, and a logical
volume inside.  Configure the logical volume to to cover the entire
partition, except the first METADATA-SIZE blocks.  (That is, the
last blocks in the logical volume's address space should map to the last
blocks in the physical volume).  The first METADATA-SIZE blocks in the
logical volume should be matched up with the blocks from the file
start-copy, obtained through step 4.  NOTE: Linux LVM version 1
doesn't support such fine-grained mapping, but Linux LVM version 2 does.

At this stage, LVM and the file system should be functional, in theory.
There's one dodgey thing we're doing here: the blocks from the file
"super-block" are allocated twice: once for the file, and once for
the first few blocks of the file system.  This is kind-of ok, because
we don't care about the 0's we "lost" when we overwrite "super-block".
	More importantly, LVM is mapping two different parts of the
logical volume's address space to the same part of the physical volume!
LVM might not like that.
	Also, if the file system gets corrupted, or perhaps if someone
tries to write to "start-copy", the consequences might not be pretty.

Anyway, I think the best solution to all of these problems is to allow
address spaces to have holes.  That is, we should be able to say
that the part of the logical volume's address space containing the
blocks of "start-copy" are not actually mapped anyway.  File systems
should be able to deal with this.  If this is implemented, then all
file system resize operations become trivial.  [TODO: add a section on
this]

Anyway, this algorithm runs in roughly O(METADATA_SIZE) time.


3. FILE SYSTEM RESIZING ON TOP OF LVM, WITHOUT INODE-RENUMBERING
----------------------------------------------------------------
Once you have LVM (hint: use the algorithm from part 2) installed
below your file system, you can grow it and shrink it without
renumbering inodes!  I'll describe the shrink algorithm here:

(1) Mount your file system you want to shrink.
(2) Create a file of the size that you want to shrink the file system by.
(3) Write 0's (or whatever.. to ensure blocks get allocated).
(4) Use the FIBMAP ioctl to find the blocks in this file.
(5) Unmount the file system.
(6) Map those blocks to "no-where" (eg: some magical /dev/zero)... you
don't need them anymore.

You just shrunk your file system's consumption.  But, it's somewhat
dangerous, for the same reasons algorithm 2 is, since the file system
is making false assumptions about the underlying volume.

Inode numbers weren't changed, since inodes weren't even touched :)

This algorithm runs in roughly O(METADATA_SIZE + SHRINK_AMT) time.