Flash disks and FFS layout heuristics

[Bakul Shah]

On Mon, 31 Mar 2008 13:06:10 PDT Matthew Dillon <dillon at apollo.backplane.com>  wrote:
>     But how do you index that information?  You can't simply append the
>     information to the NAND unless you also have a way to access it.  So
>     does the filesystem have to scan the NAND (or significant portions of it)
>     in order to build an index of the filesystem topology in system memory?

One possible way:

I'd design the system so that each update ends with the write
of a root block[1]. I'd also write root blocks at fixed
locations to find them easily without having to scann the
whole disk. Given this, on reboot use binary search to locate
the latest root block at a fixed location. There may be
further updates so scan forward until you locate the most
uptodate root block and once you have that, you are home
free!  Everything before that root block will be consistent
with it.

Even if the system crashes in the middle of a compacting GC,
the design should be able to recover all data.

What I am not sure about is whether one can do incremental
GC. A stop-and-copy GC is always possible but I don't like
the idea of long pauses.

[1]
The root block contains block # of the earliest valid block,
a sequence number (that will not roll over in device's
lifetime), block #s for various structures such as the root
of inodes, superblock, freelist if any, etc.