Added migration from littlefs v1

This is the help the introduction of littlefs v2, which is disk
incompatible with littlefs v1. While v2 can't mount v1, what we can
do is provide an optional migration, which can convert v1 into v2
partially in-place.

At worse, we only need to carry over the readonly operations on v1,
which are much less complicated than the write operations, so the extra
code cost may be as low as 25% of the v1 code size. Also, because v2
contains only metadata changes, it's possible to avoid copying file
data during the update.

Enabling the migration requires two steps
1. Defining LFS_MIGRATE
2. Call lfs_migrate (only available with the above macro)

Each macro multiplies the number of configurations needed to be tested,
so I've been avoiding macro controlled features since there's still work
to be done around testing the single configuration that's already
available. However, here the cost would be too high if we included migration
code in the standard build. We can't use the lfs_migrate function for
link time gc because of a dependency between the allocator and v1 data
structures.

So how does lfs_migrate work? It turned out to be a bit complicated, but
the answer is a multistep process that relies on mounting v1 readonly and
building the metadata skeleton needed by v2.

1. For each directory, create a v2 directory
2. Copy over v1 entries into v2 directory, including the soft-tail entry
3. Move head block of v2 directory into the unused metadata block in v1
   directory. This results in both a v1 and v2 directory sharing the
   same metadata pair.
4. Finally, create a new superblock in the unused metadata block of the
   v1 superblock.

Just like with normal metadata updates, the completion of the write to
the second metadata block marks a succesful migration that can be
mounted with littlefs v2. And all of this can occur atomically, enabling
complete fallback if power is lost of an error occurs.

Note there are several limitations with this solution.

1. While migration doesn't duplicate file data, it does temporarily
   duplicate all metadata. This can cause a device to run out of space if
   storage is tight and the filesystem as many files. If the device was
   created with >~2x the expected storage, it should be fine.

2. The current implementation is not able to recover if the metadata
   pairs develop bad blocks. It may be possilbe to workaround this, but
   it creates the problem that directories may change location during
   the migration. The other solutions I've looked at are complicated and
   require superlinear runtime. Currently I don't think it's worth
   fixing this limitation.

3. Enabling the migration requires additional code size. Currently this
   looks like it's roughly 11% at least on x86.

And, if any failure does occur, no harm is done to the original v1
filesystem on disk.

0 files changed, 0 insertions, 0 deletions