Added root entry and expanding superblocks

Expanding superblocks has been on my wishlist for a while. The basic
idea is that instead of maintaining a fixed offset blocks {0, 1} to the
the root directory (1 pointer), we maintain a dynamically sized
linked-list of superblocks that point to the actual root. If the number
of writes to the root exceeds some value, we increase the size of the
superblock linked-list.

This can leverage existing metadata-pair operations. The revision count for
metadata-pairs provides some knowledge on how much wear we've put on the
superblock, and the threaded linked-list can also be reused for this
purpose. This means superblock expansion is both optional and cheap to
implement.

Expanding superblocks helps both extremely small and extremely large filesystem
(extreme being relative of course). On the small end, we can actually
collapse the superblock into the root directory and drop the hard requirement
of 4-blocks for the superblock. On the large end, our superblock will
now last longer than the rest of the filesystem. Each time we expand,
the number of cycles until the superblock dies is increased by a power.

Before we were stuck with this layout:
level  cycles  limit    layout
1      E^2     390 MiB  s0 -> root

Now we expand every time a fixed offset is exceeded:
level  cycles  limit    layout
0      E       4 KiB    s0+root
1      E^2     390 MiB  s0 -> root
2      E^3     37 TiB   s0 -> s1 -> root
3      E^4     3.6 EiB  s0 -> s1 -> s2 -> root
...

Where the cycles are the number of cycles before death, and the limit is
the worst-case size a filesystem where early superblock death becomes a
concern (all writes to root using this formula: E^|s| = E*B, E = erase
cycles = 100000, B = block count, assuming 4096 byte blocks).

Note we can also store copies of the superblock entry on the expanded
superblocks. This may help filesystem recover tools in the future.

1 files changed, 5 insertions, 3 deletions

diff --git a/lfs.h b/lfs.h
index 4ced50a..df0927e 100644
--- a/lfs.h
+++ b/lfs.h
@@ -93,7 +93,8 @@ enum lfs_type {
 
     // internally used types
     LFS_TYPE_USER           = 0x100,
-    LFS_TYPE_SUPERBLOCK     = 0x010,
+    LFS_TYPE_SUPERBLOCK     = 0x011,
+    LFS_TYPE_ROOT           = 0x012,
     LFS_TYPE_NAME           = 0x000,
     LFS_TYPE_DELETE         = 0x030,
     LFS_TYPE_STRUCT         = 0x040,
@@ -110,8 +111,9 @@ enum lfs_type {
     // internal chip sources
     LFS_FROM_REGION         = 0x000,
     LFS_FROM_DISK           = 0x200,
-    LFS_FROM_MOVE           = 0x021,
-    LFS_FROM_ATTRS          = 0x022,
+    LFS_FROM_MOVE           = 0x050,
+    LFS_FROM_ATTRS          = 0x060,
+    LFS_FROM_SUPERBLOCK     = 0x070,
 };
 
 // File open flags