Is it possible to "discover" a littlefs filesystem partition?

[BrianPugh]

Question

Can a littlefs partition be automatically discovered? I.e. figure out the block_count and the starting address without any other information (well, except maybe block_size).

Context

I'm working on a project where different hardware/software configurations may put the littlefs partition at different locations.

Using a probe, I'd like to be able to find the littlefs partition by scanning the entire flash. I know the superblock contains the magic header "littlefs", block size, and block count, but it doesn't look straight forward to discover the superblock in a relatively robust way.

The simplest thing would be to just scan for "littlefs", operating the assumption that "littlefs" doesn't exist anywhere else on the storage, but that seems a bit too crude/fragile.

[geky]

The string "littlefs" is always 8-bytes from the beginning of the superblock, in case that helps. Unfortunately, because of the possibility of power-loss, the superblock can be at either block 0 or block 1, and I don't think anything indicates which block it's on. Though it may be possible to infer this from the revision count.

If you have a guess where the filesystem is, you can try mounting the filesystem. lfs_mount should fail if the superblock's checksum doesn't validate. If something else writes "littlefs" and the checksum correctly (e.g. an outdated littlefs image), the problem gets much harder. I am actually working on a sort of "global checksum" that would protect against this, but it's a long-term piece of work.

Once mounted, the block_count is stored in the superblock, and can theoretically be read, but littlefs currently doesn't support block_counts that don't match the provided configuration. This is an open issue (#349), and on the TODO list, but requires some internal changes to support.

But in theory, if you're happy using unstable internal APIs, it should be possible:

littlefs/lfs.c

Line 4425 in 611c9b2

if (superblock.block_count != lfs->cfg->block_count) {

As for block_size, the problem gets much trickier. Since the superblock can be at either block 0 or block 1, you need to know the block_size to fetch the superblock, which tells you the block_size, a catch-22 situation.

Determining the block_size at mount time is actually the same problem as finding the start of littlefs. Unfortunately for very large pieces of storage, scanning for "littlefs" risks making an attempted mount of unformatted storage a non-halting operation.

---

Something to consider: If the problem is the littlefs image sharing storage space with other things, such as code or bootloader space that need to reside at block 0, consider mapping the block addresses "backwards" in littlefs's block device functions. So block 0 -> block -1, block 1 -> block -2, etc.

If you do this, it'd be possible to mount littlefs without needing to find the superblock first.

Though this wouldn't work if you also had something at the end of storage, or the total size of storage is unknown.

[geky]

But in theory, if you're happy using unstable internal APIs, it should be possible:

Sorry, to make this actionable, you could in theory copy the internal lfs_dir_fetch function:

littlefs/lfs.c

Line 1338 in 611c9b2

static int lfs_dir_fetch(lfs_t *lfs,

Fetch the superblock, (block pair 0x{0,1}), and then read the superblock config info with lfs_dir_get:

littlefs/lfs.c

Line 736 in 611c9b2

static lfs_stag_t lfs_dir_get(lfs_t *lfs, const lfs_mdir_t *dir,

This would get you access to the block_count without needing to mount littlefs.

Copy this code into your own tool, and you can then provide the correct block_count when mounting littlefs.

It's not great, and a bit of work, but it's what's available right now until littlefs supports variable block_counts.

---

This is pretty much what lfs_mount does internally, so that code may be useful for reference if this is the route you want to take:

littlefs/lfs.c

Line 4352 in 611c9b2

tag = lfs_dir_get(lfs, &dir, LFS_MKTAG(0x7ff, 0x3ff, 0),

[BrianPugh]

thanks for the insight! I'll digest this for a bit.

[BrianPugh]

@geky so I think you've provided most of the solution here. A few more questions/comments:

1. Lets say I format a 1MB filesystem at offset offset 0x1000. I then decide I want to change the location of my filesystem to 0x4000 and format a 1MB filesystem at that location. The old page at 0x1000 remains untouched. As I'm searching my storage for the superblock, is it possible that I'd discover the old superblock and not detect that the partition as a whole is corrupted?

2. Both superblocks at 0x0 and 0x1 should contain the "littlefs" magic commit, right? I'm worried of an "off-by-one" error where superblock data might be accidentally written to 0x2 if we get the filesystem start off by one page.

3. I think the "backwards" filesystem suggestion might be my best option, as I have pretty strong control over those elements.

[BrianPugh]

another thought: It would be cool that if cfg->block_count==0 in lfs_mount, for it to be automatically be set in lfs_mount by the contents of the superblock. However, cfg is const. We could copy block_count to lfs_t and update all references to point at that instead of lfs->cfg->block_count. Thoughts on that? I could make a PR.

This way I'd have less lfs internals in my code base, and it might be more generically useful to other people.

[geky]

There is #753, which includes more-or-less exactly what you described as a feature.

Though it needs a bit of work:

1. A rebase now that lfs_fs_stat has been introduced.
2. The idea of automatically determining the block_size should be removed.

I've moved away from this, as the solution in #753 relies on the divisibility of block_count, which may make it not really usable. That and it makes the API really confusing.

I think littlefs will just always need the block_count configuration option, as the general problem seems sort of intractable.

There was pushback from @e107steved on the increased RAM cost, so I was going to wait until after #491 to bring #753 in, since in theory with #491 (allowing compile-time config), the RAM cost could be eliminated at compile time if you don't use variable block_sizes.

Though I think most of the cost came from the variable block_size. This required changes to the internal block device interface, since the current implementation assumes the block device's block size matches the configured block size.

With only a variable block_count the cost may be much less.

I'd say go for it. A couple other users have requested a way to mount a filesystem of unknown size.

---

1. Lets say I format a 1MB filesystem at offset offset 0x1000. I then decide I want to change the location of my filesystem to 0x4000 and format a 1MB filesystem at that location. The old page at 0x1000 remains untouched. As I'm searching my storage for the superblock, is it possible that I'd discover the old superblock and not detect that the partition as a whole is corrupted?

Yes this is a risk, and a tricky one. The only way to avoid accidentally mounting the earlier filesystem, short of intentionally scrubbing the superblocks, would be to check the validity of every block in the filesystem.

There happens to be a feature to do this, via a "global checksum", in the works. But enabling it may add a significant runtime cost to lfs_mount, since it, well, needs to check the validity of every block in the filesystem.

2. Both superblocks at 0x0 and 0x1 should contain the "littlefs" magic commit, right? I'm worried of an "off-by-one" error where superblock data might be accidentally written to 0x2 if we get the filesystem start off by one page.

No. This is a valid concern. Only one of 0 and 1 may be valid at any given time, since, in the case of powerloss, littlefs may have erased one of these blocks, leaving it with garbage.

This is the same reason we need the block_size at mount time, as otherwise we could just read it off block 0.

The only way to avoid this would be to make block 0 readonly. Which I have considered as an option, but it doesn't seem that appealing since the user might as well reserve a block for their own partition table, either MBR or custom, and store the block_size there.

littlefs wasn't designed for this, but it may be possible to determine if the superblock is on block 0 or 1 by the revision count that is stored in the first 32-bits. Every time littlefs switches which block is in use, the revision count is incremented by 1, so if you know what revision count the filesystem is formatted in you can determine which block is 0 or 1 based on if the revision count is "odd" or "even" for some definition of "odd" and "even".

Though getting this working will probably have its own challenges...

[geky]

littlefs wasn't designed for this, but it may be possible to determine if the superblock is on block 0 or 1 by the revision count that is stored in the first 32-bits.

Actually, thinking about this more, this is incompatible with current plans around metadata redundancy. Since the revision counts of both blocks would set to the same value in such a scheme...

[BenBE]

I'm somehow pondering if encoding the block number inside the copy of the superblock would be viable. Like one byte, at a fixed location of the superblock, that's the log of the block id that block is in. 0 for the 1st block, 1 for the 2nd block, 2 for the 4th black, etc. …

This would both allow for detecting the start of the filesystem (calculate backwards from where the signature was found) and having redundancy of the superblock. This would need some special casing when generating an updated superblock though, to handle this blockid exception.

Regarding the detection of the block size: There are multiple cases to consider here:

1. Only 1 valid superblock present: Size would need to be present in the block itself.
2. Two blocks with signature present: Offset between the signatures allows for size detection, when not done from explicit metadata. Blockid field would provide number of blocks between those copies.
3. Three or more blocks with signature: Choose any two and based on offset calculate the block size. Maybe cross-check with other combination.

Overall, having some self-referential data inside the superblock simplifies things without complicating the implementation too much. Having this information implicit is good; but having it explicit makes life easier even more.

[geky]

I'm somehow pondering if encoding the block number inside the copy of the superblock would be viable.

We can always add another field to the superblocks. Though as you note there would be a bit of overhead involved in updating this field, since the current logic treats writes to both superblocks as the same.

Alternatively we could carve out 2-bits of the revision count for this purpose, and ignore those bits when in metadata redundancy mode.

Regarding the detection of the block size: There are multiple cases to consider here:

littlefs actually already stores the block_size in the superblock. The problem isn't really "how do we figure out the block_size when we have a superblock", it's "how do we find a superblock".

If the first superblock is in the middle of an erase, it can be unreadable, forcing us to search for the second, backup, superblock. For larger disks, this search can take an unreasonably long amount of time.

that's the log of the block id that block is in. 0 for the 1st block, 1 for the 2nd block, 2 for the 4th black, etc. …

Storing superblocks at powers-of-2 is a really enticing, simple solution, but unfortunately incompatible with the fact that littlefs supports non-powers-of-2 block sizes. This has been a surprisingly useful feature for injecting ECC and similar things into physical blocks.

Consider the use case of a device with 4096-byte blocks, but 96-bytes reserved in each block for ECC. If you dump each of the 4000-byte blocks to a file, it's not clear to me how you could find the original filesystem short of linearly searching.

[geky]

Actually, I just realized the current design of the "global checksum" includes permuting each metadata block's CRC by its block address. This would protect against the "mounting-wrong-superblock" problem.

Though it wouldn't help find the right block offset. At best you could try mounting every option the filesystem validates correctly...

[adokitkat]

Hello. Sorry for replying to an old thread but I would like to know if using MBR to store partition offset (starting LBA) would help this problem? If so, can littlefs define a custom MBR partition type like 0xDA, DB, FC, FD, etc. (unused / not used anymore) ? MBR partition types are more of a suggestion than concrete types anyway. This way we could combine MBR type + superblock + littlefs string to find the partition reliably I suppose.

However maybe using 0x00 (unused/unknown) type would be enough if we would know the partition offset from MBR and then then just scan for the superblock and littlefs string?

I would like tho know your thoughts on this, thanks you!

This would be helpful especially on SD cards, where then we could use MBR + larger FAT partition + LittleFS partition on a single card.