This function is actually pretty much the same in both the lazy and
eager crystallization write strategies. The main difference being the
nuances around the crystal_size parameter:
- lazy: crystal_size => rough upper bound on crystal
- eager: crystal_size => strict lower bound on crystal
If we change these to an explicit crystal_min and crystal_max, we can
use lfsr_file_crystallize_ in both write strategies without changing the
logic.
It's out of scope right now, but this will help supporting both write
strategies in the future.
---
Unfortunately this added more code/stack that I was expecting:
code stack ctx
before: 36428 2248 636
after: 36460 (+0.1%) 2280 (+1.4%) 636 (+0.0%)
I'm not exactly sure why, I guess the crystal_limit calculation is too
complex to const propagate the crystal_max=-1?
Maybe the LFS_NOINLINE is disabling certain cross-function
optimizations...
This reverts most of the lazy-grafting/crystallization logic, but keeps
the general crystallization algorithm rewrite and file->leaf for caching
read operations and erased-state.
Unfortunately lazy-grafting/crystallization is both a code and stack
heavy feature for a relatively specific write pattern. It doesn't even
help if we're forced to write fragments due to prog alignment.
Dropping lazy-grafting/crystallization trades off linear write/rewrite
performance for code and stack savings:
code stack ctx
before: 37084 2304 636
after: 36428 (-1.8%) 2248 (-2.4%) 636 (+0.0%)
But with file->leaf we still keep the improvements to linear read
performance!
Compared to pre-file->leaf:
code stack ctx
before file->leaf: 36016 2296 636
after lazy file->leaf: 37084 (+3.0%) 2304 (+0.3%) 636 (+0.0%)
after eager file->leaf: 36428 (+1.1%) 2248 (-2.1%) 636 (+0.0%)
I'm still on the fence about this, but lazy-grafting/crystallization is
just a lot of code... And the first 6 letters of littlefs don't spell
"speedy" last time I checked...
At the very least we can always add lazy-grafting/crystallization as an
opt-in write strategy later.
This adopts lazy crystallization in _addition_ to lazy grafting, managed
by separate LFS_o_UNCRYST and LFS_o_UNGRAFT flags:
LFS_o_UNCRYST 0x00400000 File's leaf not fully crystallized
LFS_o_UNGRAFT 0x00800000 File's leaf does not match bshrub/btree
This lets us graft not-fully-crystallized blocks into the tree without
needing to fully crystallize, avoiding repeated recrystallizations when
linearly rewriting a file.
Long story short, this gives file rewrites roughly the same performance
as linear file writes.
---
In theory you could also have fully crystallized but ungrafted blocks
(UNGRAFT + ~UNCRYST), but this doesn't happen with the current logic.
lfsr_file_crystallize eagerly grafts blocks once they're crystallized.
Internally, lfsr_file_crystallize replaces lfsr_file_graft for the
"don't care, gimme file->leaf" operation. This is analogous to
lfsr_file_flush for file->cache.
Note we do _not_ use LFS_o_UNCRYST to track erased-state! If we did,
erased-state wouldn't survive lfsr_file_flush!
---
Of course, this adds even more code. Fortunately not _that_ much
considering how many lines of code changed:
code stack ctx
before: 37012 2304 636
after 37084 (+0.2%) 2304 (+0.0%) 636 (+0.0%)
There is another downside however, and that's that our benchmarked disk
usage is slightly worse during random writes.
I haven't fully investigated this, but I think it's due to more
temporary fragments/blocks in the B-tree before flushing. This can cause
B-tree inner nodes to split earlier than when eagerly recrystallizing.
This also leads to higher disk usage pre-flush since we keep both the
old and new blocks around while uncrystallized, but since most rewrites
are probably going to be CoW on top of committed files, I don't think
this will be a big deal.
Note the disk usage ends up the same after lfsr_file_flush.
This should better match other relocation loops in the codebase, and is
hopefully a bit more readable.
---
Note we generally have two patterns for relocation loops:
Loops where we unconditionally allocate/relocate:
relocate:;
alloc();
compact();
if (err) goto relocate;
commit();
if (err) goto relocate;
return;
And loops where we fallback to allocation/relocation:
while (true) {
commit();
if (err) goto relocate;
return;
relocate:;
alloc();
compact();
if (err) goto relocate;
}
lfsr_mdir_commit_ falls into the latter.
No code changes.
This tweaks lfsr_mdir_commit_ to avoid overrecycling if we encounter a
bad prog (LFS_ERR_CORRUPT). This avoids compacting to the same block
twice, which risks an undetected prog error and breaks internal
invariants.
Note we still overrecycle if the relocation reason is a recycle
overflow.
---
This is an alternative solution to the previous overrecycling + shrub +
ckprog bug: Just make sure we don't compact to the same block twice!
After all, if we just got a bad prog, why are we trying to prog again?
(There are actually some arguments for multiple prog attempts, bus
errors for example, but I don't think that's a great excuse for littlefs
attempting multiple progs without user input.)
Even though this adds logic to lfsr_mdir_commit_, it ends up saving
code since we can drop the shrub discard pass:
code stack ctx
before: 37088 2304 636
after: 37056 (-0.1%) 2304 (+0.0%) 636 (+0.0%)
Not that we _really_ care about this quantity of code. The real
motivation is 1. lowering the risk of a missed prog error, and
2. maintaining the never-compact-same-block invariant in case there
are other invariant-dependent bugs lurking around.
In lfsr_mdir_compact__, we rely on shrub_.block != mdir.block to avoid
compacting shrubs multiple times. This works for the most part because
we set shrub_.block = shrub.block (the old mdir block) at the beginning
of lfsr_mdir_commit. We don't actually reset shrub_.block on a bad prog,
but in theory that was ok because we never try to compact into the same
block twice.
But this falls apart if we overrecycle the mdir!
With overrecycling, if we encounter a bad prog during a compaction and
there are no more blocks to relocate to, we try one last time to compact
into the same block (this logic is mainly for recycle overflows, where
it makes a bit more sense).
Of course, compacting into the same block breaks the above shrub_.block
!= mdir.block invariant, which causes the shrub compaction to be
skipped, uses the old shrub_.trunk (which now points to garbage), and
breaks everything.
Fortunately the solution is relatively simple: Just discard any staged
shrubs that have been committed when we relocate/overrecycle.
---
While fixing this I went ahead and renamed overcompaction ->
overrecycling. To me, overcompaction implies something _very_ different,
and I think this better describes the relationship between overrecycling
and block_recycles.
Also added test_ck_ckprogs_overrecycling to nail this down and prevent a
regression in the future. This bug _was_ caught by
test_ck_spam_fwrite_fuzz, but only after unrelated fs changes.
Adds a bit of code, but a smaller + dysfunctional filesystem is not very
useful:
code stack ctx
before: 37056 2304 (+0.0%) 636 (+0.0%)
after: 37088 (+0.1%) 2304 (+0.0%) 636 (+0.0%)
With the new crystallization logic, we have two routes for resuming
crystallization:
1. before finding our crystal heuristic, if buffer is in-block and
enough for prog alignment
2. after finding our crystal heuristic, if crystal heuristic is in-block
and enough for prog alignment
But thinking about the second case, when would this happen that isn't
caught by the first case? When there are fragments trailing our buffer?
Are you writing to the file backwards?
This corner case doesn't seem worth the extra logic.
Benchmarking didn't find a noticeable difference in performance, so
removing.
Saves a bit of code:
code stack ctx
before: 37080 2304 636
after: 37056 (-0.1%) 2304 (+0.0%) 636 (+0.0%)
This sort of abuses the bptr/data type overlap again, taking an explicit
delta along with a list of datas where:
- data_count=-1 => single bptr
- data_count>=0 => list of concatenated fragments
It's a bit of a hack, but the previous rattr argument it replaces was
an arguably worse hack. I figured if we're going to interrogate the
rattr to figure out what type it is, we might as well just make the type
explicit.
Saved a surprising amount of stack! So that's nice:
code stack ctx
before: 37192 2360 636
after: 37080 (-0.3%) 2304 (-2.4%) 636 (+0.0%)
Except for the unknown flag checks. I don't know why but they really
mess with readability there for me. Maybe because the logic matches
english grammar ("is not any of these" vs "is any not of these")?
No code changes.
This is just a bit simpler/more flexible of an API. Taking flags
directly has worked well for similar functions.
This also drops lfsr_*_mkdirty. I think we should keep the mk* names
reserved for heavy-weight filesystem operations.
That being said, this does add a surprising bit of code. I because the
flags end up in literal pools? Doesn't thumb have a bunch of fancy
single-bit immediate encodings?
code stack ctx
before: 37180 2360 636
after: 37192 (+0.0%) 2360 (+0.0%) 636 (+0.0%)
Mostly adding convenience functions to deduplicate code:
- Adopted lfsr_bptr_claim
- Renamed lfsr_file_graft -> lfsr_file_graft_
- Adopted lfsr_file_graft
- Didn't bother with lfsr_file_discardleaf
This saves a bit of code, though not that much in the context of the
file->leaf code cost:
code stack ctx
before cleanup: 37228 2328 636
after: 37180 (-0.1%) 2360 (+1.4%) 636 (+0.0%)
code stack ctx
before file->leaf: 36016 2296 636
after: 37180 (+3.2%) 2360 (+2.8%) 636 (+0.0%)
TLDR: Added file->leaf, which can track file fragments (read only) and
blocks independently from file->b.shrub. This speeds up linear
read/write performance at a heavy code/stack cost.
The jury is still out on if this ends up reverted.
---
This is another change motivated by benchmarking, specifically the
significant regression in linear reads.
The problem is that CTZ skip-lists are actually _really_ good at
appending blocks! (but only appending blocks) The entire state of the
file is contained in the last block, so file writes can resume without
any reads. With B-trees, we need at least 1 B-tree lookup to resume
appending, and this really adds up when writing extremely blocks.
To try to mitigate this, I added file->leaf, a single in-RAM bptr for
tracking the most recent leaf we've operated on. This avoids B-tree
lookups during linear reads, and allowing the leaf to fall out-of-sync
with the B-tree avoids both B-tree lookups and commits during writes.
Unfortunately this isn't a complete win for writes. If we write
fragments, i.e. cache_size < prog_size, we still need to incrementally
commit to the B-tree. Fragments are a bit annoying for caching as any
B-tree commit can discard the block they reside on.
For reading, however, this brings read performance back to roughly the
same as CTZ skip-lists.
---
This also turned into more-or-less a full rewrite of the lfsr_file_flush
-> lfsr_file_crystallize code path, which is probably a good thing. This
code needed some TLC.
file->leaf also replaces the previous eblock/eoff mechanism for
erased-state tracking via the new LFSR_BPTR_ISERASED flag. This should
be useful when exploring more erased-state tracking mechanisms (ddtree).
Unfortunately, all of this additional in-RAM state is very costly. I
think there's some cleanup that can be done (the current impl is a bit
of a mess/proof-of-concept), but this does add a significant chunk of
both code and stack:
code stack ctx
before: 36016 2296 636
after: 37228 (+3.4%) 2328 (+1.4%) 636 (+0.0%)
file->leaf also increases the size of lfsr_file_t, but this doesn't show
up in ctx because struct lfs_info dominates:
lfsr_file_t before: 116
lfsr_file_t after: 136 (+17.2%)
Hm... Maybe ctx measurements should use a lower LFS_NAME_MAX?
Maybe it's just habit, but the trailing underscores_ felt far more
useful serving only as a out-pointer/new/biproduct hint. Having trailing
underscores_ serve dual purposes as both a new/biproduct hint and
optional hint just muddies things and makes the hint much less useful.
No code changes.
This adds LFS_NOINLINE, and forces lfsr_file_sync_ (the commit logic in
lfsr_file_sync) off the stack hot-path.
This adds a bit of code, function calls are surprisingly expensive, but
saves a nice big chunk of stack:
code stack ctx
before: 35992 2408 636
after: 36016 (+0.1%) 2296 (-4.7%) 636 (+0.0%)
Well, maybe not _real_ stack. The fact that this worked suggests the
real stack usage is less than our measured value.
The reason is because our stack.py script is relatively simple. It just
adds together stack frames based on the callgraph at compile time, which
misses shrinkwrapping and similar optimizations. Unfortunately that sort
of information is simply not available via GCC short of parsing the
disassembly.
But this is the number that will be used for statically allocated stacks,
and of course the number that will probably end up associated with
littlefs, so it still seems like a worthwhile number to "optimize" for.
Maybe in the future this will be different as tooling around stack
measurements improves.
---
The other benefit of moving lfsr_file_sync_ off the hot-path is that we
now no longer incorrectly include the sync commit context in the
hot-path. This tells a much different story for the cost of 1-commit
shrubs:
code stack ctx
before 1c-shrubs: 35848 2296 636
after 1c-shrubs: 36016 (+0.5%) 2296 (+0.0%) 636 (+0.0%)
This adds an alternative sync path for small in-cache files, where we
combine the shrub commit with the file sync commit, potentially writing
everything out in a single prog.
This is reminiscent of bmoss (old inlined) files, but notably avoids the
additional on-disk data-structure and extra code necessary to manage it.
---
The motivation for this comes from ongoing benchmarking, where we're
seeing a fairly significant regression in small-file performance on NAND
flash. Especially curious since the whole goal of this work was to make
NAND flash tractable.
But it makes sense: 2 commits are more than 1.
While the separate shrub + sync commits are barely noticeable on NOR
flash, on NAND flash, with its huge >512B prog sizes, the extra commit
is hard to miss.
In theory, the most performant solution would be to merge all bshrub
commits with sync commits whenever possible. This is technically doable,
and may make sense for a more performance-focused littlefs driver, but
it would 1. require an invasive code rewrite, 2. entangle lfsr_file_sync
-> lfsr_file_flush -> lfsr_file_carve, and 3. add even more code.
If we only merge shrub + sync commits when the file fits in the cache,
we can skip lfsr_file_flush, craft a simple shrubcommit by hand, and
avoid all of this mess. While still speeding up the most common write
path for small files.
And sure enough, our bench-many benchmark, which creates ~1000 4 byte
files, shows a ~2x speed improvement on bs=128KiB NAND (basically just
because we compact/split ~5 times instead of ~10 times).
---
Unfortunately the shrub commit requires quite a bit of state to set up,
and in the middle of lfsr_file_sync, one of the more critical functions
on our stack hot-path. So this does have a big cost:
code stack ctx
before: 35836 2368 636
after: 35992 (+0.4%) 2408 (+1.7%) 636 (+0.0%)
Though this is also a perfect contender to be compile-time ifdefed. It
may be worth adding something like LFS_NO_MERGESHRUBCOMMITS (better
name?) to claw back some of the cost if you don't care about
performances as much.
This could also probably be a bit cheaper if our file write configs were
organized differently... At the moment we need to check inline_size,
fragment_size, _and_ crystal_thresh since these can sometimes overlap.
But this is waiting on the future config rework.
---
Actually... Looking at this closer, I'm not sure the added commit logic
should really be included in the hot-path cost...
lfsr_file_flush is the hot path, and flush -> sync are sequential
operations that don't really share stack (with the shrub commit we
humorously _never_ call flush). The commit logic is only being dragged
in because our stack measurements are pessimistic about shrinkwrapping,
which is a bit frustrating.
I've explored shrinkwrapping in stack.py before, but the idea pretty
much failed. Unfortunately GCC simply doesn't make this info available
short of parsing the per-arch disassembly.
This adds mattr_estimate, which is basically the same as rattr_estimate,
but assumes weight <= 1:
rattr tag:
.---+---+---+- -+- -+- -+- -+---+- -+- -+- -. worst case: <=11 bytes
| tag | weight | size | rattr est: <=3t + 4
'---+---+---+- -+- -+- -+- -+---+- -+- -+- -' <=37 bytes
mattr tag:
.---+---+---+---+- -+- -+- -. worst case: <=7 bytes
| tag | w | size | mattr est: <=3t + 4
'---+---+---+---+- -+- -+- -' <=25 bytes
This may seem like only a minor improvement, but with 3 tags for every
attr, this really adds up. And with our compaction estimate overheads we
need every byte of shaving we can get.
---
This ended up necessary to get littlefs running with 512 byte blocks
again. Now that our compaction overheads are so high, littlefs is having
a hard time fitting even just the filesystem config in a single block:
mroot estimate 512B before: 246/256
mroot estimate 512B after: 162/256 (-34.1%)
Whether or not it makes sense to run littlefs with 512 byte blocks is
still an open question, even after this tweak.
Note that even if 512 byte blocks ends up intractable, this doesn't mean
littlefs won't be able to run on SD/eMMC! The configured block_size can
always be a multiple, >=, of the physical block_size, and choosing a
larger block_size completely side-steps this problem.
The new design of littlefs is primarily focused on devices with very
large block sizes, so you may want to use larger block sizes on SD/eMMC
for performance reasons anyways.
---
Code changes were pretty minimal. This does add an additional field to
lfs_t, but it's just a byte and fits into padding with the other small
precomputed constants:
code stack ctx
before: 35824 2368 636
after: 35836 (+0.0%) 2368 (+0.0%) 636 (+0.0%)
This better matches how other filesystems refer to the number of in-use
blocks.
Which makes sense when you consider that "size" could also refer to the
configured block_count. The term "usage" avoids this ambiguity.
This carves out two more bits in cksum tags to store the "phase" of the
rbyd block (maybe the name is too fancy, this is just the lowest 2 bits
of the block address):
LFSR_TAG_CKSUM 0x300p v-11 ---- ---- -pqq
^ ^
| '-- phase bits
'---- perturb bit
The intention here is to catch mrootanchors that are "out-of-phase",
i.e. they've been shifted by a small number of blocks.
This can happen if we find the wrong mrootanchor (after, say, a magic
scan), and risks filesystem corruption:
formatted
.-----------------'-----------------.
mounted
.-----------------'-----------------.
.--------+--------+--------+--------+ ...
|(erased)| mroot |
| | anchor | ...
| | |
'--------+--------+--------+--------+ ...
Including the lower 2 bits of the block address in cksum tags avoids
this, for up to a 3 block shift (the maximum number of redund
mrootanchors).
---
Note that cksum tags really are the only place we could put these bits.
Anywhere else and they would interfere with the canonical cksum, which
would break error correction. By definition these need to be different
per block.
We include these phase bits in every cksum tag (because it's easier),
but these don't really say much about mdirs that are not the
mrootanchor. Non-anchor mdirs can have arbitrary block addresses,
therefore arbitrary phase bits.
You _might_ be able to do something interesting if you sort the rbyd
addresses and use the index as the phase bits, but that would add quite
a bit of code for questionable benefit...
You could argue this adds noise to our cksums, but:
1. 2 bits seems like a really small amount of noise
2. our cksums are just crc32cs
3. the phase bits humorously never change when you rewrite a block
---
As with any feature this adds code, but only a small amount. I think
it's worth the extra protection:
code stack ctx
before: 35792 2368 636
after: 35824 (+0.1%) 2368 (+0.0%) 636 (+0.0%)
Also added test_mount_incompat_out_of_phase to test this.
The dbg scripts _don't_ error (block mismatch seems likely when
debugging), but dbgrbyd.py at least adds phase mismatch notes in
-l/--log mode.
Mainly the grm and ptail subsystems. This matches the internal mtree
API.
Unfortunately this _did_ add a little bit of code, I guess due to the
larger struct offsets. But since this simplifies the internal API I'm
going to chalk it up to compiler noise:
code stack ctx
before: 35768 2368 636
after: 35792 (+0.1%) 2368 (+0.0%) 636 (+0.0%)
This drops the leading count/mode byte, and instead uses mid=0 to
terminate grms. This shaves off 1 bytes from grmdeltas.
Previously, we needed the count/mode byte for a couple reasons:
- We needed to know the number of grm entries somehow, and there wasn't
always an obvious sentinel value. mid=-1, for example, is
unrepresentable with our unsigned leb128 encoding.
But now that development has settled, we can use mid=0.0 to figure out
the end-of-queue. mid=0.0 should always map to the root bookmark,
which doesn't make sense to delete, so it makes for a reasonable null
terminator here.
- It provided a route for future grm extensions, which could use the >2
count/mode encodings.
But I think we can use additional grm tag encodings for this.
There's only one gdelta tag so far, but the current plan for future
gdelta tags is to carve out the bottom 2 bits for redund like we do
with the struct tags:
LFSR_TAG_GDELTA 0x01tt v--- ---1 -ttt ttrr
LFSR_TAG_GRMDELTA 0x0100 v--- ---1 ---- ----
LFSR_TAG_GBMAPDELTA 0x0104 v--- ---1 ---- -1rr
LFSR_TAG_GDDTREEDELTA 0x0108 v--- ---1 ---- 1-rr
LFSR_TAG_GPTREEDELTA 0x010c v--- ---1 ---- 11rr
...
Decoding is a bit more complicated for gstate, since we will need to
xor those bits if mutable, but this avoids needing a full byte just
for redund in every auxiliary tree.
Long story short, we can leverage the lower 2 bits of the grm tag for
future extensions using the same mechanism.
This may seem like a lot of effort for only a handful of bytes, but keep
in mind each gdelta lives in more-or-less every mdir in the filesystem.
Also saves a bit of code/ctx:
code stack ctx
before: 35772 2368 640
after: 35768 (-0.0%) 2368 (+0.0%) 636 (-0.6%)
I think this was left over from when we handled LFSR_TAG_SHRUBTRUNK in
lfsr_mdir_commit__, which needed to forward mode bits to the generated
rattr.
Now that lfsr_mdir_commit__ only handles high-level in-device tags, we
can drop the lfsr_tag_key masks and save a bit of code:
code stack ctx
before: 35796 2368 640
after: 35772 (-0.1%) 2368 (+0.0%) 640 (+0.0%)
So instead of special behavior for only bookmark tags, LFSR_TAG_GRMPUSH
allows pushing any mid to the grm queue.
The benefit of LFSR_TAG_GRMPUSH, vs just calling lfsr_grm_push before
lfsr_mdir_commit, is that you can push mids that don't exist yet. This
lets you to create self-grming mids that effectively don't exist until
some other work has completed.
We currently use this to atomically create directory + bookmark entries,
but it may have some other uses in the future.
---
The extra rattr does add a bit of code, but fortunately no stack, since
lfsr_mkdir is not on the stack hot-path:
code stack ctx
before: 35768 2368 640
after: 35796 (+0.1%) 2368 (+0.0%) 640 (+0.0%)
A bit of a hack, but this saves some stack:
code stack ctx
before: 35764 2392 640
after: 35768 (+0.0%) 2368 (-1.0%) 640 (+0.0%)
It's not like the rbyd is doing anything else until we fetch the mdir.
Why?
- lfsr_mtree_lookupleaf vs lfsr_mtree_commit is inconsistent. Should
lfsr_mdir_commit be called lfsr_mtree_commitleaf? That'd be weird.
It's reasonable to call mdirs entries of the mtree, but it'd be weird
to call rbyds entries of btrees, so the inconsistency there is
expected.
- lfsr_mtree_lookup/lfsr_mtree_lookupnext (going mtree -> mdir) aren't
actually useful.
- The lfsr_mtree_namelookup/lfsr_mtree_namelookupleaf split is just more
of a headache than it's worth.
Saves a tiny bit of code:
code stack ctx
before: 35768 2392 640
after: 35764 (-0.0%) 2392 (+0.0%) 640 (+0.0%)
This matches the behavior of rbyd_/mdir_ out-pointers.
I mostly just wanted to see the separate affects on code size. Saves a
bit more code/stack:
code stack ctx
before: 35780 2408 640
after: 35768 (-0.0%) 2392 (-0.7%) 640 (+0.0%)
At least this simplifies lfsr_mtree_traverse_ quite a bit.
This makes all rbyd_/mdir_ out-pointers required, dropping all of the
internal copies needed to make lookup/namelookup/pathlookup/etc work.
Previously, the -- rough -- rule was to make out-pointers generally
optional (lfsr_data_read and other struct initers being notable
exceptions), the idea being you can opt-out of stack allocations where
possible.
In practice this kind of backfired, with many internal functions needing
redundant stack allocations in case the relevant parameter is NULL
(lfsr_btree_lookupleaf being an excellent example).
---
As an alternative rule, I think we should only expect optional
out-pointers for things you would pass-by-value (lfsr_rid_t, lfsr_tag_t,
lfsr_data_t, etc).
I've also developed a habit of naming optional out-pointers with a
trailing underscore_, to hopefully make this subtlety a bit less subtle.
This claws back all of the stack cost of BNAMEs/MNAMEs, and most of the
code cost:
code stack ctx
before: 35888 2480 640
after: 35780 (-0.3%) 2408 (-2.9%) 640 (+0.0%)
Though we still have more function calls than we started with
(lfsr_mtree_*lookup mtree -> mdir lookups).
This is the _nth_ time I've tried to force arbitrary btree name inserts
to work, so _clearly_ I need a bigger comment.
Hopefully this will prevent me from trying to delete the LFSR_RATTR_NOOP
in test_btree_find_general_fuzz _again_.
---
The gist is that insert-before-bid+1 is fundamentally different from
insert-after-bid when named btrees are involved:
.-----f-----. insert-after-d .-------f-----.
.-b--. .--j-. => .-b---. .--j-.
| .-. .-. | | .---. .-. |
a c d h i k a c d e h i k
^
insert-before-h
=> .-----f-------.
.-b--. .---j-.
| .-. .---. |
a c d g h i k
^
The problem is that lfsr_btree_commit_ needs to find the same leaf
rbyd as lfsr_btree_namelookup, and potentially insert-before the
first rid or insert-after the last rid.
Instead of separate insert-before/after flags, we make the first tag
in a commit insert-before, and all following non-grow tags
insert-after (splits).
This info is now captured in the above mentioned comment.
Now that we don't have to worry about name tag conflicts as much, we
can add name tags for things that aren't files.
This adds LFSR_TAG_BNAME for branch names, and LFSR_TAG_MNAME for mtree
names. Note that the upper 4 bits of the subtype match LFSR_TAG_BRANCH
and LFSR_TAG_MDIR respectively:
LFSR_TAG_BNAME 0x0200 v--- --1- ---- ----
LFSR_TAG_MNAME 0x0220 v--- --1- --1- ----
LFSR_TAG_BRANCH 0x030r v--- --11 ---- --rr
LFSR_TAG_MDIR 0x0324 v--- --11 --1- -1rr
The encoding is somewhat arbitrary, but I figured reserving ~31 types
for files is probably going to be plenty for littlefs. POSIX seems to
do just fine with only ~7 all these years, and I think custom attributes
will be more enticing for "niche" file types (symlinks, compressed
files, etc), given the easy backwards compatibility.
---
In addition to the debugging benefits, the new name tags let us stop
btree lookups on the first non-bname/branch tag. Previously we always
had to fetch the first struct tag as well to check if it was a branch.
In theory this saves one rbyd lookup, but in practice it's a bit muddy.
The problem is that there's two ways to use named btrees:
1. As buckets: mtree -> mdir -> mid
2. As a table: ddtree -> ddid
The only named btree we _currently_ have is the mtree. And the mtree
operates in bucket mode, with each mdir acting more-or-less as an
extension to the btree. So we end up needing to do the second tag lookup
anyways, and all we've done is complicated up the code.
But we will _eventually_ need the table mode for the ddtree, where we
care if the ddname is an exact match.
And returning the first tag is arguably the more "correct" internal API,
vs arbitrarily the first struct tag.
But then again this change is pretty pricey...
code stack ctx
before: 35732 2440 640
after: 35888 (+0.4%) 2480 (+1.6%) 640 (+0.0%)
---
It's worth noting the new BNAME/MNAME tags don't _require_ the btree
lookup changes (which is why we can get away with not touching the dbg
scripts). The previous algorithm of always checking for branch tags
still works.
Maybe there's an argument for conditionally using the previous API when
compiling without the ddtree, but that sounds horrendously messy...
Mainly to make room for some future planned stuff:
- Moved the mroot's redund bits from LFSR_TAG_GEOMETRY to
LFSR_TAG_MAGIC:
LFSR_TAG_MAGIC 0x003r v--- ---- --11 --rr
This has the benefit of living in a fixed location (off=0x5), which
may make mounting/debugging easier. It also makes LFSR_TAG_GEOMETRY
less of a special case (LFSR_TAG_MAGIC is already a _very_ special
case).
Unfortunately, this does get in the way of our previous magic=0x3
encoding. To compensate (and to avoid conflicts with LFSR_TAG_NULL),
I've added the 0x3_ prefix. This has the funny side-effect of
rendering redunds 0-3 as ascii 0-3 (0x30-0x33), which is a complete
accident but may actually be useful when debugging.
Currently all config tags fit in the 0x3_ prefix, which is nice for
debugging but not a hard requirement.
- Flipped LFSR_TAG_FILELIMIT/NAMELIMIT:
LFSR_TAG_FILELIMIT 0x0039 v--- ---- --11 1--1
LFSR_TAG_NAMELIMIT 0x003a v--- ---- --11 1-1-
The file limit is a _bit_ more fundamental. It's effectively the
required integer size for the filesystem.
These may also be followed by LFSR_TAG_ATTRLIMIT based on how future
attr revisits go.
- Rearranged struct tags so that LFSR_TAG_BRANCH = 0x300:
LFSR_TAG_BRANCH 0x030r v--- --11 ---- --rr
LFSR_TAG_DATA 0x0304 v--- --11 ---- -1--
LFSR_TAG_BLOCK 0x0308 v--- --11 ---- 1err
LFSR_TAG_DDKEY* 0x0310 v--- --11 ---1 ----
LFSR_TAG_DID 0x0314 v--- --11 ---1 -1--
LFSR_TAG_BSHRUB 0x0318 v--- --11 ---1 1---
LFSR_TAG_BTREE 0x031c v--- --11 ---1 11rr
LFSR_TAG_MROOT 0x032r v--- --11 --1- --rr
LFSR_TAG_MDIR 0x0324 v--- --11 --1- -1rr
LFSR_TAG_MTREE 0x032c v--- --11 --1- 11rr
*Planned
LFSR_TAG_BRANCH is a very special tag when it comes to bshrub/btree
traversal, so I think it deserves the subtype=0 slot.
This also just makes everything fit together better, and makes room
for the future planned ddkey tag.
Code changes minimal:
code stack ctx
before: 35728 2440 640
after: 35732 (+0.0%) 2440 (+0.0%) 640 (+0.0%)
Ok so, funny story, looks like we won't actually need pure-tree
bshrubs/btrees.
It _is_ true that the single-parent constraint imposed by pure-trees can
enable a wider range of algorithms. But looking forward into the planned
design, we just happen to not need this constraint at all. I made a
mistake here:
1. Block allocation - On paper block allocation benefits the most from
the single-parent constraint. But we have another daggish problem,
how do we efficiently account for in-flight/open btrees?
Naively, you might think we can just traverse all open btrees during
allocation, since we shouldn't have _that_ many. But this scales
O(n^2) when writing a large file. The key observation being that open
files reference on-disk btrees and are _not_ RAM constrained.
The current solution involves tree-diffing in order to figure out
bmap updates. Which, humorously, works perfectly fine even if the
trees are dags.
2. Error correction - I just completely forgot that the current plans
for block redundancy require the ddtree.
Each block gets mapped into the dense ddtree, with subranges of the
ddtree grouped into parity groups backed by the ptree. Instead of
bptrs, file btrees store indirect ddkeys into the ddtree. No bptrs?
No dag problem!
This is still a problem if we ever support naive data redund (redund
blocks in a bptrs), but that's out of scope for other reasons
(basically just a lot more code).
So reverting. Allowing dags allows for much faster random writes, at
least in theory.
---
For now I'm still keeping the dag-avoidance in lfsr_file_flush_ around
under the LFS_NONDAG ifdef. This will likely be dropped at some point,
but I'm curious how it affects benchmarks.
Ugh, and of course the unused label makes GCC unhappy. Added
-Wno-unused-label to CFLAGS because labels have other uses besides just
being goto targets (debug targets, code organization, etc).
We probably use labels more that other libraries because to littlefs's
no-recursion requirement.
Code changes minimal, still not sure where that stack difference comes
from:
code stack ctx
before: 35740 2424 640
after: 35736 (-0.0%) 2440 (+0.7%) 640 (+0.0%)
This tears out most of the implied lfsr_file_sync calls, and restricts
LFS_O_SYNC to only imply lfsr_file_sync on _write_ operations. So only
lfsr_file_write, and maybe pwrite/writev/etc in the future.
This mainly affects lfsr_file_truncate/fruncate (and punchhole/
insertrange/collapserange in the future), while reverting the LFS_O_SYNC
related changes in lfsr_file_open:
- lfsr_file_open + LFS_O_SYNC => does _not_ sync
- lfsr_file_close + LFS_O_SYNC => syncs (unless desynced)
- lfsr_file_write + LFS_O_SYNC => syncs
- lfsr_file_sync + LFS_O_SYNC => syncs
- lfsr_file_truncate + LFS_O_SYNC => does _not_ sync
- lfsr_file_fruncate + LFS_O_SYNC => does _not_ sync
Note LFS_O_FLUSH is unaffected, it was always limited to
lfsr_file_write since that's the only function that touches file
buffers.
Also note I want this rule to apply to the future lfsr_file_punchhole/
insertrange/collapserange functions as well. Even though you can argue
these effectuate writes, they're at a level of sophistication that we
can just expect users to just call lfsr_file_sync if they want to.
---
Ok, so a number of reasons:
- This matches behavior of LFS_O_APPEND, which is intentionally
restricted to only write operations.
In that case I think the explicit limitation is easier to understand
than trying to define an abstract model.
This makes LFS_O_SYNC, LFS_O_FLUSH, and LFS_O_APPEND consistent in
when the relevant behavior takes effect.
- This avoids the zero-sized files after powerloss. Which are just as
likely, if not more, to trip up users vs missing syncs.
- Most truncate/fruncate operations are immediately followed by a write
operation anyways. Which just makes the truncate/fruncate syncs wasted
prog/erase cycles.
Even in some of the more complicated truncate/function use cases, you
just don't care about when fruncates/truncates hit the disk.
Take logging via lfsr_file_fruncate for example. Yes the fruncate will
usually happen _after_ the write operation, but this just means the
log file will usually be one entry larger than expected. Which is a
state you can end up with anyways after powerloss.
- This avoids confusing/conflicting LFS_O_SYNC + LFS_O_DESYNC behavior.
Again, this simple rule is easier to reason about than a model.
You would think this would be well defined in POSIX, but it's really
not. POSIX limits O_SYNC to "write I/O operations", but doesn't really
define a "write" (it is a retroactive standard after all). ftruncate is
a bit funny in that it states "the extended area shall appear as if it
were zero-filled", but the term "write" doesn't appear in ftruncate's
documentation at all.
Searching through LKML, stack overflow, etc, it doesn't seem like anyone
else knows exactly what to do either. There was a bug report[1] in 2005
for ext3 + O_SYNC + ftruncate that was rejected, but a later bug
report[2] in 2012 for xfs + O_SYNC + fallocate that was fixed (but was
broken in almost every Linux fs?).
1: https://lore.kernel.org/lkml/1111610558.1998.193.camel@sisko.sctweedie.blueyonder.co.uk
2: https://lore.kernel.org/linux-ext4/20111116084256.GA22963@infradead.org
So, this may end up a bit controversial, but I'm going to go with the
simpler truncate/fruncate-do-not-imply-sync rule for the above reasons.
I think this is a bit more important for littlefs than other
filesystems, as it also defines the behavior of lfsr_file_open, and with
a rigorous powerloss model being core to the design.
---
This is also cheaper code/stack-wise, but if this was going to be a
deciding factor we should just put LFS_O_SYNC/LFS_O_FLUSH behind ifdefs:
code stack ctx
before: 35816 2480 640
after: 35740 (-0.2%) 2424 (-2.3%) 640 (+0.0%)
Compared to before the LFS_O_SYNC tweaks:
code stack ctx
before-tweaks: 35780 2440 640
before: 35816 (+0.1%) 2480 (+1.6%) 640 (+0.0%)
after: 35740 (-0.1%) 2424 (-0.7%) 640 (+0.0%)
This is the only way I can think of resolving the weirdness that is
LFS_O_SYNC + LFS_O_DESYNC. Just don't allow it.
LFS_O_SYNC and LFS_O_DESYNC are pretty much opposite behaviors, so an
LFS_O_SYNC + LFS_O_DESYNC file seems like a contradiction.
---
This does limit a little bit what's possible with the API, but hey that
just means fewer tests/smaller API surface area for users to stub their
toes on.
Saves a tiny bit of code:
code stack ctx
before: 35824 2480 640
after: 35816 (-0.0%) 2480 (+0.0%) 640 (+0.0%)
Do'h! I almost forgot about LFS_O_TRUNC. If LFS_O_CREAT + LFS_O_SYNC
implies lfsr_file_sync, clearly LFS_O_TRUNC + LFS_O_SYNC should as well.
This changes lfsr_file_open to only imply lfsr_file_sync if any open
operation sets the unsync flag, which is the only case where
lfsr_file_sync would do anything anyways.
This does have a subtle change in behavior when LFS_O_CREAT + LFS_O_SYNC
+ LFS_O_DESYNC, in that the desync flag is only cleared if the file did
not exist before. But I think this is more expected than unconditionally
syncing.
Note this matches the behavior of lfsr_file_write, which does _not_
imply lfsr_file_sync if the write is size=0.
---
Also added better tests over lfsr_file_open + LFS_O_TRUNC, this flag
isn't very well tested...
Which found a bug!
We were incorrectly setting LFS_o_UNFLUSH when opening with LFS_O_TRUNC,
when we should have set LFS_o_UNSYNC. This caused littlefs to never
bother updating the file's metadata unless some other write comes along
(which is what usually follows LFS_O_TRUNC).
To help catch bugs like this, I added an assert to lfsr_file_flush that
unflushed files are always marked unsynced. A synced + unflushed file is
weird and should never happen.
---
Code changes minimal:
code stack ctx
before: 35820 2480 640
after: 35824 (+0.0%) 2480 (+0.0%) 640 (+0.0%)
So we keep the behavior of creating reg files with lfsr_file_open +
LFS_O_SYNC, but only clear the desync flag if lfsr_file_open would
mutate the filesystem.
This is hopefully a simpler model to reason about, and makes LFS_O_SYNC
+ LFS_O_DESYNC a bit less weird.
Saves a little bit of code:
code stack ctx
before: 35836 2488 640
after: 35820 (-0.0%) 2480 (-0.3%) 640 (+0.0%)
So now the following creates a reg file (instead of just a stickynote):
lfsr_file_open(&lfs, &file, "test.txt",
LFS_O_WRONLY | LFS_O_CREAT | LFS_O_EXCL | LFS_O_SYNC) => 0;
// powerloss!!
struct lfsr_info info;
lfsr_stat(&lfs, "test.txt", &info) => 0; // LFS_ERR_NOENT before
assert(info.type == LFS_TYPE_REG);
This hopefully results in more intuitive behavior around lfsr_file_open
with LFS_O_SYNC. Which is important as LFS_O_SYNC is often used as an
escape hatch to avoid needing to reason about syncing things when
performance is not a big concern.
Unfortunately this does come with a surprisingly big code/stack cost,
but I'm thinking of putting these flags (LFS_O_FLUSH/LFS_O_SYNC) behind
ifdefs anyways (LFS_MAYBE_SYNC?):
code stack ctx
before: 35780 2440 640
after: 35836 (+0.2%) 2488 (+2.0%) 640 (+0.0%)
Also added some more tests to make sure these open+LFS_O_SYNC cases are
explicitly covered:
- test_fsync_sync_o_wrr
- test_fsync_sync_o_wwrr
- test_fsync_desync_o_wdwrr
- test_fsync_resync_o_wdwyrr
This does make a bit of a mess when you combined LFS_O_SYNC +
LFS_O_DESYNC. What exactly should a SYNC + DESYNC file look like?
For now I've just made LFS_O_SYNC + LFS_O_DESYNC behave as if you opened
a file with LFS_O_SYNC and then immediately called lfsr_file_desync on
it. So it doesn't receive broadcasts, but _does_ create the reg file,
and _does_ sync on first write, clearing the desync flag.
But this may be worth revisiting. Maybe LFS_O_DESYNC files shouldn't
have their desync flags cleared unless lfsr_file_sync is explicitly
called? Or maybe LFS_O_SYNC + LFS_O_DESYNC should just be an error?
Unsure...
So now calling lfsr_file_sync on zombied files is a noop:
// create a file
lfsr_file_t a;
lfsr_file_open(&lfs, &a, "a",
LFS_O_RDWR | LFS_O_CREAT | LFS_O_EXCL) => 0;
// remove, creating a zombie
lfsr_remove(&lfs, "a") => 0;
// sync, this is now a noop (previously LFS_ERR_NOENT)
lfsr_file_sync(&lfs, &a) => 0;
// close is also a noop
lfsr_file_close(&lfs, &a) => 0;
I've been on the fence on this for a while, on one hand erroring
provides more information to the user, on the other hand a noop is less
surprising if the user comes from other systems.
Ended up making this a noop. I figured minimizing surprises is good API
design, and the user can always use lfsr_stat to check if the file still
exists.
This also matches POSIX, and, perhaps more importantly, the current
version of littlefs.
---
Note that lfsr_file_resync still errors with LFS_ERR_NOENT. It's hard to
argue the file "matches the state of disk" otherwise.
Code changes minimal:
code stack ctx
before: 35784 2440 640
after: 35780 (-0.0%) 2440 (+0.0%) 640 (+0.0%)
I think these cases were mostly just overlooked as the API churned
internally, bmosses/bprout were added and removed, etc.
Shaves off some more code:
code stack ctx
before: 35820 2440 640 (+0.0%)
after: 35784 (-0.1%) 2440 (+0.0%) 640 (+0.0%)
I think this was just overlooked when dropping bmoss/bsprouts.
Dropping bmoss here makes it so file size is always the first leb128 in
the data, which is nice.
Saves a bit of code:
code stack ctx
before: 35864 2440 640
after: 35820 (-0.1%) 2440 (+0.0%) 640 (+0.0%)
In hindsight this was way too fragile.
Explicitly checking for both LFS_TYPE_REG and LFS_type_TRAVERSAL (the 2
in-device types that can have attached bshrubs) solves this and
hopefully prevents lfsr_o_isbshrub from falling out-of-date in the
future.
The downside being a little bit more code:
code stack ctx
before: 35832 2440 640
after: 35864 (+0.1%) 2440 (+0.0%) 640 (+0.0%)
Found by test_traversal_mutation_mroot_split_bshrub_l and
test_traversal_mutation_mroot_split_bshrub_r.
This adds LFSR_TAG_ORPHAN, which simplifies quite a bit of the internal
stickynote handling.
Now that we don't have to worry about conflicts with future unknown
types, we can add whatever types we want internally. One useful one
is LFSR_TAG_ORPHAN, which lets us determine stickynote's orphan status
early (in lfsr_mdir_lookupnext and lfsr_mdir_namelookup):
- non-orphan stickynotes -> LFSR_TAG_STICKYNOTE
- orphan stickynotes -> LFSR_TAG_ORPHAN
This simplifies all the places where we need to check if a stickynote
really exists, which is most of the high-level functions.
One downside is that this makes stickynote _manipulation_ a bit more
delicate. lfsr_mdir_lookup(LFSR_TAG_ORPHAN) no longer works as expected,
for example.
Fortunately we can sidestep this issue by dropping down to
lfsr_rbyd_lookup when we need to interact with stickynotes directly,
skipping the is-orphan checks.
---
Saves a nice bit of code:
code stack ctx
before: 35984 2440 640
after: 35832 (-0.4%) 2440 (+0.0%) 640 (+0.0%)
It got a little muddy since this now include the unknown-type changes,
but here's the code diff from before we exposed LFSR_TYPE_STICKYNOTE to
users:
code stack ctx
before: 35740 2440 640
after: 35832 (+0.3%) 2440 (+0.0%) 640 (+0.0%)
Now that name tags are a special case, using a switch case statement
here continues to make less sense.
Also switched to just checking count >= 0 directly instead of via
lfsr_attr_dtag, because lfsr_tag_suptype(lfsr_tag_dtag(rattr)) would've
been a mouthful.
Saves a teensy bit of code:
code stack ctx
before: 35992 2440 640
after: 35984 (-0.0%) 2440 (+0.0%) 640 (+0.0%)
This drops the requirement that all file types are introduced with a
related wcompat flag. Instead, the wcompat flag is only required if
modification _would_ leak resources, and we treat unknown file types as
though they are regular files.
This allows modification of unknown file types without the risk of
breaking anything.
To compare with before the unknown-type rework:
Before:
> Unknown file types are allowed and may leak resources if modified,
> so attempted modification (rename/remove) will error with
> LFS_ERR_NOTSUP.
Now:
> Unknown file types are allowed but must not leak resources if
> modified. If an unknown file type would leak resources, it should set
> a related wcompat flag to only allow mounting RDONLY.
Note this includes directories, which can leak bookmarks if removed, so
filesystems using directories should set the LFSR_WCOMPAT_DIR flag.
But we no longer need the LFSR_WCOMPAT_REG/LFSR_WCOMPAT_STICKYNOTE
flags.
---
The real tricky part was getting lfsr_rename to work with unknown types,
as this broke the invariant that we only ever commit tags we know about.
Fixing this required:
- Fetching the non-unknown-mapped tag in lfsr_rename
- Mapping all name tags to LFSR_TAG_NAME in lfsr_rbyd_appendrattr_
- Adopting LFSR_RATTR_NAME for bookmark name tags
This was broken by the above lfsr_rbyd_appendrattr_ change, but it's
probably good to handle these the same as other name tags anyways.
This adds a bit of code, but not enough that I think this isn't worth
it (or worth a build-time option):
code stack ctx
before: 35924 2440 640
after: 35992 (+0.0%) 2440 (+0.0%) 640 (+0.0%)
This changes how we approach unknown file types.
Before:
> Unknown file types are allowed and may leak resources if modified,
> so attempted modification (rename/remove) will error with
> LFS_ERR_NOTSUP.
Now:
> Unknown file types are only allowed in RDONLY mode. This avoids the
> whole leaking resources headache.
Additionally, unknown types are now mapped to LFS_TYPE_UNKNOWN, instead
of just being forwarded to the user. This allows us to add internal
types/tags to the LFSR_TAG_NAME type space without worrying about
conflicts with future types:
- reg -> LFS_TYPE_REG
- dir -> LFS_TYPE_DIR
- stickynote -> LFS_TYPE_STICKYNOTE
- everything else -> LFS_TYPE_UNKNOWN
Thinking about potential future types, it seems most (symlinks,
compressed files, etc) can be better implemented via custom attributes.
Using custom attributes doesn't mean the filesystem _can't_ inject
special behavior, and custom attributes allow for perfect backwards
compatibility.
So with future types less likely, forwarding type info to users is less
important (and potentially error prone). Instead, allowing on-disk +
internal types to be represented densely is much more useful.
And it avoids setting an upper bound on future types prematurely.
---
This also includes a minor rcompat/wcompat rework. Since we're probably
going to end up with 32-bit rcompat flags anyways, might as well make
them more human-readable (nibble-aligned):
LFS_RCOMPAT_NONSTANDARD 0x00000001 Non-standard filesystem format
LFS_RCOMPAT_WRONLY 0x00000002 Reading is disallowed
LFS_RCOMPAT_BMOSS 0x00000010 Files may use inlined data
LFS_RCOMPAT_BSPROUT 0x00000020 Files may use block pointers
LFS_RCOMPAT_BSHRUB 0x00000040 Files may use inlined btrees
LFS_RCOMPAT_BTREE 0x00000080 Files may use btrees
LFS_RCOMPAT_MMOSS 0x00000100 May use an inlined mdir
LFS_RCOMPAT_MSPROUT 0x00000200 May use an mdir pointer
LFS_RCOMPAT_MSHRUB 0x00000400 May use an inlined mtree
LFS_RCOMPAT_MTREE 0x00000800 May use an mdir btree
LFS_RCOMPAT_GRM 0x00001000 Global-remove in use
LFS_WCOMPAT_NONSTANDARD 0x00000001 Non-standard filesystem format
LFS_WCOMPAT_RDONLY 0x00000002 Writing is disallowed
LFS_WCOMPAT_REG 0x00000010 Regular file types in use
LFS_WCOMPAT_DIR 0x00000020 Directory file types in use
LFS_WCOMPAT_STICKYNOTE 0x00000040 Stickynote file types in use
LFS_WCOMPAT_GCKSUM 0x00001000 Global-checksum in use
---
Code changes:
code stack ctx
before: 35928 2440 640
after: 35924 (-0.0%) 2440 (+0.0%) 640 (+0.0%)
Now that LFS_TYPE_STICKYNOTE is a real type users can interact with, it
makes sense to group it with REG/DIR. This also has the side-effect of
making these contiguous.
---
LFSR_TAG_BOOKMARKs, however, are still hidden from the user. This
unfortunately means there will be a bit of a jump if we ever add
LFS_TYPE_SYMLINK in the future, but I'm starting to wonder if that's the
best way to approach symlinks in littlefs...
If instead LFS_TYPE_SYMLINKS were implied via custom attribute, you
could avoid the headache that comes with adding a new tag encoding, and
allow perfect compatibility with non-symlink drivers. Win win.
This seems like a better approach for _all_ of the theoretical future
types (compressed files, device files, etc), and avoids the risk of
oversaturating the type space.
---
This had a surprising impact on code for just a minor encoding tweak. I
guess the contiguousness pushed the compiler to use tables/ranges for
more things? Or maybe 3 vs 5 is just an easier constant to encode?
code stack ctx
before: 35952 2440 640
after: 35928 (-0.1%) 2440 (+0.0%) 640 (+0.0%)
This adds the LFS_TYPE_STICKYNOTE type, allowing users to interact with
stickynotes as long as they aren't orphaned.
This hopefully solves the long-standing mess that was the LFS_O_EXCL
API.
---
As for what I mean by orphaned vs non-orphaned stickynotes:
Non-orphaned stickynotes represent files that have been "created" (via
LFS_O_CREAT), but not "committed" (via sync/close). You can still close
and convert the stickynote to a reg file, so these aren't orphans. These
are also called "uncreated" files in some parts of the codebase:
- open+O_CREAT -> non-orphaned stickynote (uncreated file)
Orphaned stickynotes are possible by either removing an open file, or
desyncing a file before sync/close. These are still invisible to the
user and will be eventually cleaned up after the last file handle is
closed:
- open+remove -> orphaned stickynote (zombied file)
- open+O_CREAT+desync+close -> orphaned stickynote (orphaned file)
Desynced files are a bit special. Even though they technically aren't
orphaned, they also behave like orphaned file handles:
- open+O_CREAT+close -> orphaned stickynote (desynced file)
The idea is this mimics the state of files post-close, and allows for
some tricks like using a desync file as a temporary file with no
observable effects on the filesystem.
---
The motivation for this comes from staring at the LFS_O_EXCL API for too
long and realizing the problem is that littlefs's API contradicts itself
when it comes to whether or not uncreated files exist.
This solution is to consistently treat uncreated files as though they
exist (the alternative would make LFS_O_EXCL pretty much useless), but I
really didn't want to do this as having what appears to be normal files
disappear after powerloss risks confusion.
The compromise here is to give these files a special type, repurposing
the internal LFS_TAG_STICKYNOTE, which hopefully hints to the user these
won't behave like normal files.
If the user is more interested in POSIX compatibility, they can always
map these to either LFS_TYPE_REG or LFS_ERR_NOENT, whichever they think
is the least confusing.
As a quirk of littlefs's API, stickynotes should never actually contain
any data, and will always have size 0.
However they can have custom attributes assigned now (which is I guess
ok? also TODO should probably test this).
---
The implementation right now is a bit naive, I mostly just wanted to get
the tests working again in this new model. It may be possible to claw
back some of this code cost:
code stack ctx
before: 35740 2440 640
after: 35952 (+0.6%) 2440 (+0.0%) 640 (+0.0%)
This may be useful for compression in the future, where compression +
noise can result in blocks _larger_ than the expected weight.
Thinking about how compression might be integrated into littlefs, it
would be nice if such a topology did _not_ trigger asserts. This would
allow littlefs images to interact with compressed files at least a
little bit (rename/remove could be very useful), even if the compression
algorithm isn't supported.
Supporting this requires only a single clamp in lfsr_file_lookupleaf,
but it's a little bit more costly than you might expect:
code stack ctx
before: 35692 2440 640
after: 35740 (+0.1%) 2440 (+0.0%) 640 (+0.0%)
This is due to internal API awkwardness:
1. LFSR_DATA_TRUNCATE is surprisingly costly
2. We need to create a local weight copy in case the caller's is NULL
Christopher Haster