Automatic volume recognition

[davidefer]

Hi everybody
I was wondering whether lfs could automatically detect the volume setup when mounting, without specifying the volume configuration in the lfs_config structure.
Would it be possible to store somewhere in the volume this information while formatting? Or at least all the information needed to detect the volume topology and let it be mounted.
The only information to be hardcoded in the fw would be the start address of lfs in the flash.
Thanks in advance.

[geky]

Hi @davidefer, this has been on my mind for a while.

littlefs does have a "superblock entry" that contains static info about the filesystem (can you can add your own with lfs_setattr("/"), though I realize this doesn't help before you mount the filesystem).

Sidenote: Most of the configuration isn't needed for portability.

• cache_size - Does nothing with disk.
• read_size/prog_size - As long as these are compatible with the underlying disk, they are only used for cache-alignment and can change between systems.
• block_cycles - Only used to determine when to evict blocks, can change.

littlefs only needs to know two things: The block_size and block_count.

The block_count is easy, we can read that from the superblock entry.

The block_size, however, present a chicken-and-egg problem I haven't found a good answer for yet.

The root/superblock in littlefs is a small two-block log in blocks 0 and 1. This means that at any given time one of the two blocks may be in the middle of an erase operation. For most flash, this means temporarily setting the flash to 1s, losing any data on the block. Handling is a hard requirement for power-resilience.

So we have a superblock in one of the two blocks at the start of storage. If we can get to one of the two blocks, we can fetch the configuration. But this is where we run into a problem. How do we load the second block if we don't know our block size? We only need the offset (not the size) to fetch a block, but without knowing the size, we don't know where the second block could be.

I'm very interested in solving this problem. But have no idea how to.

---

Some possible solutions:

1. Provide configuration-detection as a "best-effort" operation, allowing for a possible failure if the device was caught erasing the superblock. I really don't like this "solution" as it could create rare problems for unaware-users and can't be relied on for any sort of real product

2. Reserve one permanently-static block to store the superblock. This is a problem for small devices, such as internal flash, that only have two blocks in total. It could be an optional feature, though that doesn't mesh well with a consistent user-interface for storage. It's also costly.

3. Iterate though possible block sizes (multiples of physical block size) until we find the superblock. This is the most promising, though it has the downside that invalid mounts could take an awfully long time to fail (O(n)). It would also be inconsistent depending on which of the two blocks the superblock resides in. We could reduce the runtime cost to O(log n) by only searching for powers-of-two of the physical block size, but this currently isn't a requirement.

[davidefer]

Hi @geky
"3.Iterate though possible block size"
I think this is the easiest solution. If I remember correctly, the block size we can configure is dictated by the flash erasable areas , e.g. 4KB and 64KB blocks or sectors, so there would be only two options in this case to choose from. Am I missing something?

[e107steved]

Afraid so. Not everyone is using flash. For example, I'm using FRAM with a block size of 128, and small EEPROMs would be similar. Other people here appear to be using SD cards with 1M block sizes and so on. In any case, it could cause future problems if assumptions were made about the size of erasable blocks.

[e107steved]

Further thought. Option 3 looks to be the best (least bad?) choice for auto-determination. Firstly, I suggest this should be a compile-time option, since not all users will need it. Secondly, with auto-determination enabled, how about treating the value in the blocksize field as a hint? If its zero, try different block sizes according to some algorithm; otherwise, start from the hint value and try bigger and smaller values from there.

It may be possible to speed up the process by defining a search order for block sizes; perhaps 128, 256, 512, 4K, 1M early in the list, then fill in the gaps?

[davidefer]

I was meaning that for every chip you don't have so many possibilities for block sizes. It was just an example, lfs doesn't have to hardcode those numbers. They should be proposed to lfs while mounting or similar.
So basically we are saying the same thing, lfs should get like an ordered array of possible block sizes to choose from while mounting.
In addition, lfs should be able to report which valid block size has found while mounting.

[geky]

I was meaning that for every chip you don't have so many possibilities for block sizes.

If there is a known set of block sizes, you could iterate and try mounting each. This is one way to the filesystem which block sizes you support.

lfs_size_t block_sizes[] = {4096, 65536}; 
for (int i = 0; i < sizeof(block_sizes)/sizeof(block_sizes[0]); i++) {
    cfg.block_size = block_sizes[i];
    int err = lfs_mount(&lfs, &cfg);
    if (!err) {
        break;
    }
}

Of course right now littlefs is still missing the option of loading the block_count from disk. #279 and #238 are similar issues around this.

Keep in mind the block_size config option is a "virtual block size". It can be any multiple of the physical block, which is useful if you're working around performance issues.

It may be possible to speed up the process by defining a search order for block sizes; perhaps 128, 256, 512, 4K, 1M early in the list, then fill in the gaps?

That's a good idea. It wouldn't be unreasonable to search all powers-of-two (O(log n)) before searching other multiple (O(n)). It wouldn't change the amount of time needed to reject an unformated disk though.

I'm currently waiting on this to build up better benchmarks, which is needed for a number of other scalability issues. My concern is that the time taken to scan makes this option unreasonable. Disks can be surprisingly large.

[geky]

Firstly, I suggest this should be a compile-time option, since not all users will need it.

It sounds like we should have a special value for lfs->cfg->block_size that is "LFS_BLOCK_SIZE_UNKNOWN" or similar.

There's been some ideas around improving how the lfs_config struct works to be possible to optimize out at compile time: #158 (comment)

[e107steved]

Is there actually any merit in integrating this within littleFs? That basic loop to try opening with different block sizes is so simple, and easily added by those that want it. I was concerned that code size would be increased with a feature that some (many? most?) don't want. Just needs a way of reading the block_count from disc. (And that possibly has to be configurable, since the config structure could be in ROM.)

[davidefer]

If lfs could deal with something like cfg .block_count = LFS_BLOCK_COUNT_UNKNOWN (0xFFFFFFFFUL) and the search by itself the real block count while mounting (and providing it back as info), then the loop with the block sizes would be acceptable.

[dpgeorge]

We wanted this feature (automatic block size and block count detection) in MicroPython and implemented it using option 1 (best effort, just look at the first part of the first block). But indeed it turns out to be unreliable, there have been cases where the first block was partially erased and did not contain a valid superblock (but the second block did).

Option 2 seems interesting if there's another place the data can be stored so it doesn't waste too much flash (external to the filesystem data).

Another idea is to store a copy of the info at the very end of the block device, so it's either at the start or end and there are only 2 places to search for it (only one of these would be erased at any one time, at the most).

But in the short term I think option 3 is the best way to solve it. Instead of making lfs_mount() automatic, there could be a new (optional) function like:

// Will fill in block_size and block_count in the given config struct if a valid FS is found.
// Returns 0 on success, or non-zero if no filesystem found.
int lfs_detect(lfs2_t *lfs2, const struct lfs2_config *config);

[geky]

Another idea is to store a copy of the info at the very end of the block device, so it's either at the start or end and there are only 2 places to search for it (only one of these would be erased at any one time, at the most).

This is a clever idea, and almost works, except right now the metadata blocks can only be fetched from the beginning. So ironically we would need to know the block size in order to read a metadata block at the end of disk.

But maybe you could search for the magic string to try to guess where the block starts? Unfortunately that ends up again needing to search half of the entire block device in case the block size = 1/2 the disk size.

Hmm, but I suppose nothing says we couldn't just always invert the order we write one of the blocks in our metadata pair...

[geky]

Ah, though storing the superblock at both the front+end means you need to know the block size. A sort of Heisenberg superblock.

Though maybe that's an acceptable tradeoff? The main use case you would lose is being able to store extra data after the filesystem without needing a partition table.