[Feature Request] Improve seed generation / allow for platform-provided entropy/seeds.

[gtaska]

I am in the process of evaluating littlefs for our platform and wanted to get a better understanding of how well the wear-levelling works. I spent the last couple of days playing around with the littlefs-js demo (http://littlefs.geky.net/demo.html), and noticed that wear levelling does not appear to work in the demo - it always starts wearing out the start of the emulated device first.

(This lead me to checking the code for possible issues and ended up finding issue #484).

I haven't had much luck getting littlefs-js running locally, so added some debug logs to our platform, and got output similar to the following:

lfs_mount
lfs_init: seed = 0
lfs_dir_fetchmatch()
lfs_dir_fetchmatch: seed = 00000000 ^ 83F4A2A4 = 83F4A2A4
lfs_alloc_reset()
lfs_dir_fetchmatch()
lfs_dir_fetchmatch: seed = 83F4A2A4 ^ 83F4A2A4 = 00000000
lfs_dir_fetchmatch()
lfs_dir_fetchmatch: seed = 00000000 ^ 83F4A2A4 = 83F4A2A4
lfs_alloc(): 676

(Note: I know that this doesn't show the problem that the littlefs-js demo exhibits, as the seed value is non-zero when lfs_alloc_reset is called. In this log, the first lfs_alloc does in fact pick a block from a relatively random location in flash).

What is alarming to see, is the fact that the seed gets updated multiple times - and that (in this case) every second instance causes the result to be 0x00000000 (an obvious side-effect of using the XOR operation - a repeat of the operation will undo the previous operation). Now, this is only a highly contrived example with only minimal FS usage (essentially, the boot cycle count example mentioned in the main README.md file), but it is a worry that the seed keeps flip-flopping with 0. Whether or not this is a problem depends on when lfs_alloc_reset() is called, relative to the number of times lfs_dir_fetchmatch gets called. IMHO, the current solution is fragile - it wouldn't be hard for a second innocuous call to be added within the callflow of lfs_mount - and wear levelling to become broken.

A better option might be to use these crc values as input into a separate, on-going hash algorithm (which, ironically, could be a crc32). Pretty much any hash algorithm other than XOR would not suffer this problem.

An even better option, at least for some users, would be to allow the entropy/seed to be provided via a separate (optional) callback function. This would allow platforms using littlefs to leverage platform-specific entropy sources, such as a hardware-based random number generator, or even a real-time clock.

[geky]

Ah! I should note http://littlefs.geky.net/demo.html is very outdated, and still uses v1. I should add a warning to that page, but probably won't update it. v2 now has sub-block wear-leveling, which isn't captured, and using the google graph APIs for animation was a terrible idea.

---

It looks like the repeated 0x00000000 is coming from the xor being applied to the filesystem repeatedly. The intention was to hash the filesystem in a single pass during mount, and allocate from that point linearly.

I'm confused why lfs_alloc_reset is randomizing the offset, I think that is actually the root of the bug. lfs_alloc_reset is being called on IO errors only to throwaway possibly corrupted lookahead info, I don't think it should be randomizing the offset.

That being said, using crc32 as a top-level hash is a great idea, and we should probably adopt that anyways.

However, I am hesitant to add support for a custom entropy. The current implementation is completely deterministic, which is very useful for reproducibility.

[mishka88ru]

Hi.
I don't know internals of little-fs and how crc32 hashes will be used, so may be I am completely wrong...

crc32 is slow and distribution randomness is doubtful. Take a look at http://prng.di.unimi.it/, e.g. xoroshiro64**.

Custom entropy value can be logged or become a part of a crash dump for post-mortem debug for example.

[geky]

Will look into these, thanks for the pointers.

The crc32 is convenient as it's already used to check for metadatadata errors. The use as a hash function is only during mount, so I suspect performance is not a big concern.

You're right the custom entropy could be incorporated into debug information, but it would add complexity to reproducing issues for what I'm not sure is a big benefit.

[gtaska]

There are a number of different ways to implement a crc32 algorithm. A 'closed' form where you provide all the data in one call, and it returns the final result, and an 'open' form where you have what I will call init(), iterate() and finalize() functions. Processing data makes repeated calls to the iterate function with blocks of data. The 'finalize' function only inverts the bits, which for us doesn't really add any additional benefit in this use case, so using the raw intermediate value for the purposes of wear-leveling seed would be just as valid.

In the 'open' form, you can read the intermediate results after iterating over new chunks of data (which in this case would be 4 bytes). The crc32 algorithm will not be that slow for iterating over 4 bytes at a time - and if you use an accelerated version of the algorithm that uses a lookup-table it would reduce down to approximately 8 xors, 4 shifts, 4 ands, & 4 value lookups. (https://en.wikipedia.org/wiki/Cyclic_redundancy_check#CRC-32_algorithm).

IMHO, a PRNG is not the appropriate solution here. It takes a seed, and from that one value generates a stream of pseudo-random values. If the PRNG's seed is not random, then the output is entirely deterministic. Littlefs is only looking for a single random value at mount time to select where to start allocating blocks from - using a PRNG would either always produce the same first result - or you have gone back to the original problem of trying to come up with a random seed.

PRNGs are often analyzed for failures to produce values that appear to be truly random, but you would need to consider whether or not that level of randomness is really required for selecting an initial block. What is more important, is to ensure that the algorithm chosen provides an evenly-distributed output. Luckily it looks like there are some folks that have looked at this problem already:

• https://michiel.buddingh.eu/distribution-of-hash-values "CRC32 seems to score really well, but its graph is skewed by the results of Dataset 5 (binary numbers), which may or may not be too synthetic to be considered a fair benchmark. But even if you substract the results from that test, it does not fare significantly worse than other, cryptographic hash functions."
• https://www.strchr.com/hash_functions "Murmur2, Meiyan, SBox, and CRC32 provide good performance for all kinds of keys. They can be recommended as general-purpose hashing functions on x86."

[geky]

@gtaska, good points, a PRNG isn't applicable here. A better hash function maybe, but CRC32 is already available, performance isn't a big concern here, and as noted CRC32 is probably distributed sufficiently enough. Considering it is being used to combine other CRCs, which already look close to noise, we probably don't have to worry about the pathological cases.

I've removed the randomization during allocation errors and adopted CRC as the hash-combination function here: #487

[geky]

So I was thinking about this filesystem-wide hash, and how it's a bit funny that we calculate what is effectively a checksum of the full filesystem, but don't actually use it for validation at all.

I wonder if we could actually store this hash in littlefs's gstate mechanism to fully validate the filesystem's metadata at mount time.

The way littlefs's gstate works is it stores a small fixed size of data in every metadata-pair that can be reconstructed by xoring the field in all of the metadata-pairs together. This allows the gstate to be updated atomically on every metadata update.

One issue is that we'd need to recalculate the filesystem-wide hash (I'm going to start calling it the "gcrc") every time we update a metadata-pair. While it looks like it's mathematically possible to update a CRC based on random changes (here), it appears complex and relatively expensive.

So far the best hash-combining function I've found is to just add the CRCs together, allowing overflow. This avoids the a xor a = 0 issue, and allows cheap updates by subtracting the old value, allowing underflow. Open to suggestions/concerns.

So this gcrc scheme would effectively look like this:

.--------.     .--------.     .--------.     .--------.
| pair1  |     | pair2  |     | pair3  |     | pair4  |
|        |     |        |     |        |     |        |
| gdelta --xor-> gdelta --xor-> gdelta --xor-> gdelta ---> gcrc
'--------'     '--------'     '--------'     '--------'
\----.---/     \----.---/     \----.---/     \----.---/     =
     v              v              v              v
    crc --- + ---> crc --- + ---> crc --- + ---> crc ----> gcrc

I realize this is a bit off topic, but would be interested if anything stands out as concerning using addition for this.