- Valgrind-detected memory leak in test_superblocks.
- Valgrind-detected uninitialized lfs->block_size in lfs_init caused by
an unintended sed replacement.
- Said sed replacement also changed the implementation of the v1 portion
of lfs_migrate, this is out of scope and caused migrate to fail, which
fortunately CI noticed.
- We also need to copy the block_size/block_count configs in v1 so that
low-level bd operations still work.
- le-conversion in test_evil now matters due to difference in
LFS_ERR_CORRUPT/LFS_ERR_INVAL paths during lfs_mount. This is good
because we're actually testing for loop detection not pointer
out-of-bounds as intended.
These locally show the expected O(d(n)) growth of the block_size search
when block_count is known.
A rough estimate of runtime for a 1 GiB device with a 90 MiB/s read bandwidth
(using the mt25q for rough numbers):
known bs/bc => ~1.44 us
known block_size => ~1.44 us
known block_count => ~125 us
unknown bs/bc => ~376 ms
The initial implementation for this was provided by kaetemi, originally
as a mount flag. However, it has been modified here to be self-contained
in an explicit runtime function that can be called after mount.
The reasons for an explicit function:
1. lfs_mount stays a strictly readonly operation, and avoids pulling in
all of the write machinery.
2. filesystem-wide operations such as lfs_fs_grow can be a bit risky,
and irreversable. The action of growing the filesystem should be very
intentional.
---
One concern with this change is that this will be the first function
that changes metadata in the superblock. This might break tools that
expect the first valid superblock entry to contain the most recent
metadata.
- Need to drop cache during block_size search.
- Removed "Corrupted" messages when root is not found to avoid too much debug
output. This also gets rid of a long-term point of confusion arround
"Corrupted" messages on a mount that is intended to fail.
This is necessary for accessing format-specific information stored in
the superblock after mounting.
As is common in other filesystems this also provides the filesystem
usage. However collecting the filesystem usage is more expensive in
littlefs than other filesystem (and less accurate because of CoW), so
this may need to be cached after mount in the future.
This ended up needing a bit of API rework since littlefs no longer needs
to know the actual erase_count. We can no longer rely on lfs_config to
contain all the information necessary to configure the block devices.
Changing the lfs_bd_config structs to be required is probably a good
idea anyways as it moves us more towards separating the bds from
littlefs, though we can't quite get rid of the lfs_config parameter
because of the block-device API in lfs_config. Eventually it would be
nice to get rid of it, but that would require API breakage.
Aside from asserts (which can be implemented in block devices), erase_count
provides no useful info aside from what's known with block_count and
risks mistakes during configuration.
Each set of known/unknown block_size-related variables has a well-defined
mount behavior:
block_size block_count
known known => known bs, O(1)
known unknown => known bs, O(1)
unknown known => bs search, O(d(n))
unknown unknown => bs search, O(n)
If block_size is unknown, block_count uses the erase_size as a unit,
which is the only reasonable option since block_size must be
>= prog/read/cache_size.
This hopefully helps make it more clear that we are using erase_size as the
unit during the block_size search. However this does mean you need to
set erase_count to zero to allow any littlefs size, which might be a bit
confusing:
block_size block_count erase_size erase_count
known known known known => known bs, O(1)
known unknown known known => known bs, O(1)
unknown unknown known known => bs search, O(d(n))
unknown unknown known unknown => bs search, O(n)
This adds two new configuration options: erase_size and erase_count,
allowing block_size and block_count to be loaded from the superblock
during mount. For backwards compability these default to block_size and
block_count if zero.
---
Unfortunately this is a bit easier said than done. littlefs keeps its
superblock in the metadata pair located at blocks {0,1}, which is also
where the root directory lives (keep in mind small littlefs images may
only have 2 blocks in total). If we mutate blocks {0,1}, we have to
erase before programming, which means it's possible to have the only
superblock in block 1. This presents a puzzle because how do you find
block 1 if you don't know the size of a block?
One solution presented here is to search for block 1 by trying different
sizes until we find a superblock. This isn't great but there are some
properties of this search that help:
1. If we do find a superblock, the search will never take longer than a
mount with a known block_size. This is because we stop at block 1,
searching at most O(block_size) bytes, and metadata fetch is already
a O(block_size) operation.
This means the concern is limited to how long it takes to fail when
littlefs is not present on the disk.
2. We can assume the on-disk block_size is probably a factor of the
total size of the disk. After a bit of digging into the math, this
apparently reduces the runtime to the divisor function, d(n), which
is sublinear.
According to a blog post by Terence Tao this is bounded by the
ridiculous O(e^O(log(n)/log(log(n)))):
https://terrytao.wordpress.com/2008/09/23/the-divisor-bound
This is apparently somewhere between O(sqrt(n)) and O(log(n)), but
conveniently O(log(n)) on average and O(log(n)) for powers of 2.
I've left it as O(d(n)) in the documentation, which might be a bit
confusing, but I'm not sure how best to capture "mostly log(n)"
correctly.
3. If we don't know the block_size, or don't know that block_size is
aligned to the disk size, the best we can do is a O(n) search.
In this case I've added a warning, so at least it's distinguishable
from an infinite loop if debugging.
- 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.
This adds -P/--propagate and -Z/--depth to perf.py for showing recursive
results, making it easy to narrow down on where spikes in performance
come from.
This ended up being a bit different from stack.py's recursive results,
as we end up with different (diminishing) numbers as we descend.
This provides 2 things:
1. perf integration with the bench/test runners - This is a bit tricky
with perf as it doesn't have its own way to combine perf measurements
across multiple processes. perf.py works around this by writing
everything to a zip file, using flock to synchronize. As a plus, free
compression!
2. Parsing and presentation of perf results in a format consistent with
the other CSV-based tools. This actually ran into a surprising number of
issues:
- We need to process raw events to get the information we want, this
ends up being a lot of data (~16MiB at 100Hz uncompressed), so we
paralellize the parsing of each decompressed perf file.
- perf reports raw addresses post-ASLR. It does provide sym+off which
is very useful, but to find the source of static functions we need to
reverse the ASLR by finding the delta the produces the best
symbol<->addr matches.
- This isn't related to perf, but decoding dwarf line-numbers is
really complicated. You basically need to write a tiny VM.
This also turns on perf measurement by default for the bench-runner, but at a
low frequency (100 Hz). This can be decreased or removed in the future
if it causes any slowdown.
The main change is requiring field names for -b/-f/-s/-S, this
is a bit more powerful, and supports hidden extra fields, but
can require a bit more typing in some cases.
- Changed multi-field flags to action=append instead of comma-separated.
- Dropped short-names for geometries/powerlosses
- Renamed -Pexponential -> -Plog
- Allowed omitting the 0 for -W0/-H0/-n0 and made -j0 consistent
- Better handling of --xlim/--ylim
Instead of trying to align to block-boundaries tracebd.py now just
aliases to whatever dimensions are provided.
Also reworked how scripts handle default sizing. Now using reasonable
defaults with 0 being a placeholder for automatic sizing. The addition
of -z/--cat makes it possible to pipe directly to stdout.
Also added support for dots/braille output which can capture more
detail, though care needs to be taken to not rely on accurate coloring.
Now both scripts also fallback to guessing what fields to use based on
what fields can be converted to integers. This is more falible, and
doesn't work for tests/benchmarks, but in those cases explicit fields
can be used (which is what would be needed without guessing anyways).
Without this redundant permutations can easily happen with runtime
overrides because the different define layers aren't aware of each
other. This causes problems for collecting benchmark results.
Christopher Haster