See SPEC.md for more info.
Also considered adding an explanation to DESIGN.md, but there's not a
great place for it. Maybe FCRCs are too low-level for the high-level
design document. Though may be worth reconsidering if DESIGN.md gets
revisited.
This just means a rewrite of the superblock entry with the new minor
version.
Though it's interesting to note, we don't need to rewrite the superblock
entry until the first write operation in the filesystem, an optimization
that is already in use for the fixing of orphans and in-flight moves.
To keep track of any outdated minor version found during lfs_mount, we
can carve out a bit from the reserved bits in our gstate. These are
currently used for a counter tracking the number of orphans in the
filesystem, but this is usually a very small number so this hopefully
won't be an issue.
In-device gstate tag:
[-- 32 --]
[1|- 11 -| 10 |1| 9 ]
^----^-----^--^--^-- 1-bit has orphans
'-----|--|--|-- 11-bit move type
'--|--|-- 10-bit move id
'--|-- 1-bit needs superblock
'-- 9-bit orphan count
This is a bit tricky since we need two different version of littlefs in
order to test for most compatibility concerns.
Fortunately we already have scripts/changeprefix.py for version-specific
symbols, so it's not that hard to link in the previous version of
littlefs in CI as a separate set of symbols, "lfsp_" in this case.
So that we can at least test the compatibility tests locally, I've added
an ifdef against the expected define "LFSP" to define a set of aliases
mapping "lfsp_" symbols to "lfs_" symbols. This is manual at the moment,
and a bit hacky, but gets the job done.
---
Also changed BUILDDIR creation to derive subdirectories from a few
Makefile variables. This makes the subdirectories less manual and more
flexible for things like LFSP. Note this wasn't possible until BUILDDIR
was changed to default to "." when omitted.
This wasn't implemented correctly anyways, as it would need to recursively
rename directories that may not exist. Things would also get a bit
complicated if only some files in a directory were renamed.
Doable, but not needed for our use case.
For now just ignore any directory components. Though this may be worth
changing if the source directory structure becomes more complicated in
the future (maybe with a -r/--recursive flag?).
This of course should never happen normally, two half-orphans requires
two parents, which is disallowed in littlefs for this reason. But it can
happen if there is an outdated half-orphan later in the metadata
linked-list. The two half-orphans can cause the deorphan step to get
stuck, constantly "fixing" the first half-orphan before it has a chance
to remove the problematic, outdated half-orphan later in the list.
The solution here is to do a full check for half-orphans before
restarting the half-orphan loop. This strategy has the potential to
visit more metadata blocks unnecessarily, but avoids situations where
removing a later half-orphan will eventually cause an earlier
half-orphan to resolve itself.
Found with heuristic powerloss testing with test_relocations_reentrant_renames
after 192 nested powerlosses.
Initially I thought the fcrc would be sufficient for all of the
end-of-commit context, since indicating that there is a new commit is a
simple as invalidating the fcrc. But it turns out there are cases that
make this impossible.
The surprising, and actually common, case, is that of an fcrc that
will end up containing a full commit. This is common as soon as the
prog_size is big, as small commits are padded to the prog_size at
minimum.
.------------------. \
| metadata | |
| | |
| | +-.
|------------------| | |
| foward CRC ------------.
|------------------| / | |
| commit CRC -----' |
|------------------| |
| padding | |
| | |
|------------------| \ \ |
| metadata | | | |
| | +-. | |
| | | | +-'
|------------------| / | |
| commit CRC --------' |
|------------------| |
| | /
'------------------'
When the commit + crc is all contained in the fcrc, something silly
happens with the math behind crcs. Everything in the commit gets
canceled out:
crc(m) = m(x) x^|P|-1 mod P(x)
m ++ crc(m) = m(x) x^|P|-1 + (m(x) x^|P|-1 mod P(x))
crc(m ++ crc(m)) = (m(x) x^|P|-1 + (m(x) x^|P|-1 mod P(x))) x^|P|-1 mod P(x)
crc(m ++ crc(m)) = (m(x) x^|P|-1 + m(x) x^|P|-1) x^|P|-1 mod P(x)
crc(m ++ crc(m)) = 0 * x^|P|-1 mod P(x)
This is the reason the crc of a message + naive crc is zero. Even with an
initializer/bit-fiddling, the crc of the whole commit ends up as some
constant.
So no manipulation of the commit can change the fcrc...
But even if this did work, or we changed this scheme to use two
different checksums, it would still require calculating the fcrc of
the whole commit to know if we need to tweak the first bit to invalidate
the unlikely-but-problematic case where we happen to match the fcrc. This
would add a large amount of complexity to the commit code.
It's much simpler and cheaper to keep the 1-bit counter in the tag, even
if it adds another moving part to the system.
This fixes most of the remaining bugs (except one with multiple padding
commits + noop erases in test_badblocks), with some other code tweaks.
The biggest change was dropping reliance on end-of-block commits to know
when to stop parsing commits. We can just continue to parse tags and
rely on the crc for catch bad commits, avoiding a backwards-compatiblity
hiccup. So no new commit tag.
Also renamed nprogcrc -> fcrc and commitcrc -> ccrc and made naming in
the code a bit more consistent.
Previously forward-looking CRCs was just two new CRC types, one for
commits with forward-looking CRCs, one without. These both contained the
CRC needed to complete the current commit (note that the commit CRC
must come last!).
[-- 32 --|-- 32 --|-- 32 --|-- 32 --]
with: [ crc3 tag | nprog size | nprog crc | commit crc ]
without: [ crc2 tag | commit crc ]
This meant there had to be several checks for the two possible structure
sizes, messying up the implementation.
[-- 32 --|-- 32 --|-- 32 --|-- 32 --|-- 32 --]
with: [nprogcrc tag| nprog size | nprog crc | commit tag | commit crc ]
without: [ commit tag | commit crc ]
But we already have a mechanism for storing optional metadata! The
different metadata tags! So why not use a separate tage for the
forward-looking CRC, separate from the commit CRC?
I wasn't sure this would actually help that much, there are still
necessary conditions for wether or not a forward-looking CRC is there,
but in the end it simplified the code quite nicely, and resulted in a ~200 byte
code-cost saving.
- General cleanup from integration, including cleaning up some older
commit code
- Partial-prog tests do not make sense when prog_size == block_size
(there can't be partial-progs!)
- Fixed signed-comparison issue in modified filebd
This change is necessary to handle out-of-order writes found by pjsg's
fuzzing work.
The problem is that it is possible for (non-NOR) block devices to write
pages in any order, or to even write random data in the case of a
power-loss. This breaks littlefs's use of the first bit in a page to
indicate the erase-state.
pjsg notes this behavior is documented in the W25Q here:
https://community.cypress.com/docs/DOC-10507
---
The basic idea here is to CRC the next page, and use this "erase-state CRC" to
check if the next page is erased and ready to accept programs.
.------------------. \ commit
| metadata | |
| | +---.
| | | |
|------------------| | |
| erase-state CRC -----. |
|------------------| | | |
| commit CRC ---|-|-'
|------------------| / |
| padding | | padding (doesn't need CRC)
| | |
|------------------| \ | next prog
| erased? | +-'
| | | |
| v | /
| |
| |
'------------------'
This is made a bit annoying since littlefs doesn't actually store the
page (prog_size) in the superblock, since it doesn't need to know the
size for any other operation. We can work around this by storing both
the CRC and size of the next page when necessary.
Another interesting note is that we don't need to any bit tweaking
information, since we read the next page every time we would need to
know how to clobber the erase-state CRC. And since we only read
prog_size, this works really well with our caching, since the caches
must be a multiple of prog_size.
This also brings back the internal lfs_bd_crc function, in which we can
use some optimizations added to lfs_bd_cmp.
Needs some cleanup but the idea is passing most relevant tests.
The previous cycle detection algorithm (a naive check against the largest
possible tail list) is simple and gets the job done, but has the potential to
take a very long time on disks with many blocks. Brent's algorithm, on
the other hand, takes at most 2x the number of blocks in the tail list.
Originally naive cycle detection was chosen over Floyd's algorithm to
avoid the extra complexity of managing two desynced traversals for every
traversal of the tail list, but Brent's algorithm is very well suited for our
use case, requiring only we keep track of an additional mdir pointer on the
stack as we traverse.
- Added support for negative numbers in the leb16 encoding with an
optional 'w' prefix.
- Changed prettyasserts.py rule to .a.c => .c, allowing other .a.c files
in the future.
- Updated .gitignore with missing generated files (tags, .csv).
- Removed suite-namespacing of test symbols, these are no longer needed.
- Changed test define overrides to have higher priority than explicit
defines encoded in test ids. So:
./runners/bench_runner bench_dir_open:0f1g12gg2b8c8dgg4e0 -DREAD_SIZE=16
Behaves as expected.
Otherwise it's not easy to experiment with known failing test cases.
- Fixed issue where the -b flag ignored explicit test/bench ids.
Driven primarily by a want to compare measurements of different runtime
complexities (it's difficult to fit O(n) and O(log n) on the same plot),
this adds the ability to nest subplots in the same .svg which try to align
as much as possible. This turned out to be surprisingly complicated.
As a part of this, adopted matplotlib's relatively recent
constrained_layout, which behaves much more consistently.
Also dropped --legend-left, no one should really be using that.
The difference between ggplot's gray and GitHub's gray was a bit jarring.
This also adds --foreground and --font-color for this sort of additional
color control without needing to add a new flag for every color scheme
out there.
When you add a function to every benchmark suite, you know if should
probably be provided by the benchmark runner itself. That being said,
randomness in tests/benchmarks is a bit tricky because it needs to be
strictly controlled and reproducible.
No global state is used, allowing tests/benches to maintain multiple
randomness stream which can be useful for checking results during a run.
There's an argument for having global prng state in that the prng could
be preserved across power-loss, but I have yet to see a use for this,
and it would add a significant requirement to any future test/bench runner.
The linear powerloss heuristic provides very good powerloss coverage
without a significant runtime hit, so there's really no reason to run
the tests without -Plinear.
Previous behavior can be accomplished with an explicit -Pnone.
- Renamed struct_.py -> structs.py again.
- Removed lfs.csv, instead prefering script specific csv files.
- Added *-diff make rules for quick comparison against a previous
result, results are now implicitly written on each run.
For example, `make code` creates lfs.code.csv and prints the summary, which
can be followed by `make code-diff` to compare changes against the saved
lfs.code.csv without overwriting.
- Added nargs=? support for -s and -S, now uses a per-result _sort
attribute to decide sort if fields are unspecified.
Two flags introduced: -fcallgraph-info=su for stack analysis, and
-ftrack-macro-expansions=0 for cleaner prettyassert.py warnings, are
unfortunately not supported in Clang.
The override vars in the Makefile meant it wasn't actually possible to
remove these flags for Clang testing, so this commit changes those vars
to normal, non-overriding vars. This means `make CFLAGS=-Werror` and
`CFLAGS=-Werror make` behave _very_ differently, but this is just an
unfortunate quirk of make that needs to be worked around.
changeprefix.py only works on prefixes, which is a bit of a problem for
flags in the workflow scripts, requiring extra handling to not hide the prefix
from changeprefix.py
The littlefs CI is actually in a nice state that generates a lot of
information about PRs (code/stack/struct changes, line/branch coverage
changes, benchmark changes), but GitHub's UI has changed overtime to
make CI statuses harder to find for some reason.
This bot comment should hopefully make this information easy to find
without creating too much noise in the discussion. If not, this can
always be changed later.
For long running processes (testing with >1pls) these logs can grow into
multiple gigabytes, humorously we never access more than the last n lines
as requested by --context. Piping the stdout with --stdout does not use
additional RAM.
- Moved to Ubuntu 22.04
This notably means we no longer have to bend over backwards to
install GCC 10!
- Changed shell in gha to include the verbose/undefined flags, making
debugging gha a bit less painful
- Adopted the new test.py/test_runners framework, which means no more
heavy recompilation for different configurations. This reduces the test job
runtime from >1 hour to ~15 minutes, while increasing the number of
geometries we are testing.
- Added exhaustive powerloss testing, because of time constraints this
is at most 1pls for general tests, 2pls for a subset of useful tests.
- Limited coverage measurements to `make test`
Originally I tried to maximize coverage numbers by including coverage
from every possible source, including the more elaborate CI jobs which
provide an extra level of fuzzing.
But this missed the purpose of coverage measurements, which is to find
areas where test cases can be improved. We don't want to improve coverage
by just shoving more fuzz tests into CI, we want to improve coverage by
adding specific, intentioned test cases, that, if they fail, highlight
the reason for the failure.
With this perspective, maximizing coverage measurement in CI is
counter-productive. This changes makes it so the reported coverage is
always less than actual CI coverage, but acts as a more useful metric.
This also simplifies coverage collection, so that's an extra plus.
- Added benchmarks to CI
Note this doesn't suffer from inconsistent CPU performance because our
benchmarks are based on purely simulated read/prog/erase measurements.
- Updated the generated markdown table to include line+branch coverage
info and benchmark results.
- Fixed added/removed count in scripts when an entry has no field in
the expected results
- Fixed a python-sort-type issue when by-field is missing in a result
Despite the comment being correct, the calculation is somehow off by a word,
meaning something must have been missed. Maybe the space for the move-delete
was missed since that was added later to avoid losing move-deletes during
relocations.
This was found with the new exhaustive power-loss searching added to the
test framework with -P2. The exact failure was
test_dirs_many_reentrant:2gg2cb:k4o6. This must be the first test that
ends up with all possible extra state in a single mdir block.
This happens in rare situations where there is a failed mdir relocation,
interrupted by a power-loss, containing the destination of a directory
rename operation, where the directory being renamed preceded the
relocating mdir in the mdir tail-list. This requires at some point for a
previous directory rename to create a cycle.
If this happens, it's possible for the half-orphan to contain the only
reference to the renamed directory. Since half-orphans contain outdated
state when viewed through the mdir tail-list, the renamed directory
appears to be a full-orphan until we fix the relocating half-orphan.
This causes littlefs to incorrectly remove the renamed directory from
the mdir tail-list, causes catastrophic problems down the line.
The source of the problem is that the two different types of orphans
really operate on two different levels of abstraction: half-orphans fix
failed mdir commits, while full-orphans fix directory removes/renames.
Conflating the two leads to situations where we attempt to fix assumed
problems about the directory tree before we have fixed problems with the
mdir state.
The fix here is to separate out the deorphan search into two passes: one
to fix half-orphans and correct any mdir-commits, restoring the mdirs
and gstate to a known good state, then two to fix failed
removes/renames.
---
This was found with the -Plinear heuristic powerloss testing, which now
runs on more geometries. The failing case was:
test_relocations_reentrant_renames:112gg261dk1e3f3:123456789abcdefg1h1i1j1k1
l1m1n1o1p1q1r1s1t1u1v1g2h2i2j2k2l2m2n2o2p2q2r2s2t2
Also fixed/tweaked some parts of the test framework as a part of finding
this bug:
- Fixed off-by-one in exhaustive powerloss state encoding.
- Added --gdb-powerloss-before and --gdb-powerloss-after to help debug
state changes through a failing powerloss, maybe this should be
expanded to any arbitrary powerloss number in the future.
- Added lfs_emubd_crc and lfs_emubd_bdcrc to get block/bd crcs for quick
state comparisons while debugging.
- Fixed bd read/prog/erase counts not being copied during exhaustive
powerloss testing.
- Fixed small typo in lfs_emubd trace.
These are just incorrect limits in the tests that can be triggered by
powerloss testing, which can end up with more metadata-pairs than
without powerloss testing due to orphans.
This is the name expected if you are actually linking against littlefs.
The use as a default build rule is mostly for linting. Most uses of
littlefs likely compile directly with the sources (it is only several K
of code), or use their own build system, and the previous name would have made
linking a bit of a challenge.
Still, this might cause some breakage for someone...
- Changed --(tool)-tool to --(tool)-path in scripts, this seems to be
a more common name for this sort of flag.
- Changed BUILDDIR to not have implicit slash, makes Makefile internals
a bit more readable.
- Fixed some outdated names hidden in less-often used ifdefs.
Added a couple flags to make the script a bit more flexible, and removed
littlefs-specific default in line with the other scripts which aren't
really littlefs-specific. (These defaults can be moved to the
littlefs-specific Makefile easily enough).
The original behavior can be reproduced like so:
./script/changeprefix.py lfs lfs2 --git
- Fixed prettyasserts.py parsing when '->' is in expr
- Made prettyasserts.py failures not crash (yay dynamic typing)
- Fixed the initial state of the emubd disk file to match the internal
state in RAM
- Fixed true/false getting changed to True/False in test.py/bench.py
defines
- Fixed accidental substring matching in plot.py's --by comparison
- Fixed a missed LFS_BLOCk_CYCLES in test_superblocks.toml that was
missed
- Changed test.py/bench.py -v to only show commands being run
Including the test output is still possible with test.py -v -O-, making
the implicit inclusion redundant and noisy.
- Added license comments to bench_runner/test_runner
Note that plotmpl.py tries to share many arguments with plot.py,
allowing plot.py to act as a sort of draft mode for previewing plots
before creating an svg.
Based loosely on Linux's perf tool, perfbd.py uses trace output with
backtraces to aggregate and show the block device usage of all functions
in a program, propagating block devices operation cost up the backtrace
for each operation.
This combined with --trace-period and --trace-freq for
sampling/filtering trace events allow the bench-runner to very
efficiently record the general cost of block device operations with very
little overhead.
Adopted this as the default side-effect of make bench, replacing
cycle-based performance measurements which are less important for
littlefs.
Christopher Haster