diff options
author | Christopher Haster <chaster@utexas.edu> | 2020-01-22 07:18:19 +0300 |
---|---|---|
committer | Christopher Haster <chaster@utexas.edu> | 2020-01-27 08:45:54 +0300 |
commit | a5d614fbfbf19b8605e08c28a53bc69ea3179a3e (patch) | |
tree | 1abefa376bca07681b78d967c08b0dddfacab0d6 /scripts | |
parent | f4b6a6b3284d8b721ba3db0bba93ee45fde7ead9 (diff) |
Added tests for power-cycled-relocations and fixed the bugs that fell out
The power-cycled-relocation test with random renames has been the most
aggressive test applied to littlefs so far, with:
- Random nested directory creation
- Random nested directory removal
- Random nested directory renames (this could make the
threaded linked-list very interesting)
- Relocating blocks every write (maximum wear-leveling)
- Incrementally cycling power every write
Also added a couple other tests to test_orphans and test_relocations.
The good news is the added testing worked well, it found quite a number
of complex and subtle bugs that have been difficult to find.
1. It's actually possible for our parent to be relocated and go out of
sync in lfs_mkdir. This can happen if our predecessor's predecessor
is our parent as we are threading ourselves into the filesystem's
threaded list. (note this doesn't happen if our predecessor _is_ our
parent, as we then update our parent in a single commit).
This is annoying because it only happens if our parent is a long (>1
pair) directory, otherwise we wouldn't need to catch relocations.
Fortunately we can reuse the internal open file/dir linked-list to
catch relocations easily, as long as we're careful to unhook our
parent whenever lfs_mkdir returns.
2. Even more surprising, it's possible for the child in lfs_remove
to be relocated while we delete the entry from our parent. This
can happen if we are our own parent's predecessor, since we need
to be updated then if our parent relocates.
Fortunately we can also hook into the open linked-list here.
Note this same issue was present in lfs_rename.
Fortunately, this means now all fetched dirs are hooked into the
open linked-list if they are needed across a commit. This means
we shouldn't need assumptions about tree movement for correctness.
3. lfs_rename("deja/vu", "deja/vu") with the same source and destination
was broken and tried to delete the entry twice.
4. Managing gstate deltas when we lose power during relocations was
broken. And unfortunately complicated.
The issue happens when we lose power during a relocation while
removing a directory.
When we remove a directory, we need to move the contents of its
gstate delta to another directory or we'll corrupt littlefs gstate.
(gstate is an xor of all deltas on the filesystem). We used to just
xor the gstate into our parent's gstate, however this isn't correct.
The gstate isn't built out of the directory tree, but rather out of
the threaded linked-list (which exists to make collecting this
gstate efficient).
Because we have to remove our dir in two operations, there's a point
were both the updated parent and child can exist in threaded
linked-list and duplicate the child's gstate delta.
.--------.
->| parent |-.
| gstate | |
.-| a |-'
| '--------'
| X <- child is orphaned
| .--------.
'>| child |->
| gstate |
| a |
'--------'
What we need to do is save our child's gstate and only give it to our
predecessor, since this finalizes the removal of the child.
However we still need to make valid updates to the gstate to mark
that we've created an orphan when we start removing the child.
This led to a small rework of how the gstate is handled. Now we have
a separation of the gpending state that should be written out ASAP
and the gdelta state that is collected from orphans awaiting
deletion.
5. lfs_deorphan wasn't actually able to handle deorphaning/desyncing
more than one orphan after a power-cycle. Having more than one orphan
is very rare, but of course very possible. Fortunately this was just
a mistake with using a break the in the deorphan, perhaps left from
v1 where multiple orphans weren't possible?
Note that we use a continue to force a refetch of the orphaned block.
This is needed in the case of a half-orphan, since the fetched
half-orphan may have an outdated tail pointer.
Diffstat (limited to 'scripts')
-rwxr-xr-x | scripts/readtree.py | 19 |
1 files changed, 10 insertions, 9 deletions
diff --git a/scripts/readtree.py b/scripts/readtree.py index 7d112fd..30e3cfc 100755 --- a/scripts/readtree.py +++ b/scripts/readtree.py @@ -197,16 +197,17 @@ def main(args): args.mdirs = True if args.superblock and superblock: - print("superblock %s" % json.dumps(superblock[0].data.decode('utf8'))) + print("superblock %s v%d.%d" % ( + json.dumps(superblock[0].data.decode('utf8')), + struct.unpack('<H', superblock[1].data[2:2+2])[0], + struct.unpack('<H', superblock[1].data[0:0+2])[0])) print( - " version v{1}.{0}\n" - " block_size {2}\n" - " block_count {3}\n" - " name_max {4}\n" - " file_max {5}\n" - " attr_max {6}" - .format(*struct.unpack( - '<HHIIIII', superblock[1].data[:24].ljust(24, b'\xff')))) + " block_size %d\n" + " block_count %d\n" + " name_max %d\n" + " file_max %d\n" + " attr_max %d" % struct.unpack( + '<IIIII', superblock[1].data[4:4+20].ljust(20, b'\xff'))) if args.gstate and gstate: print("gstate 0x%s" % ''.join('%02x' % c for c in gstate)) |