Github/littlefs
1
Fork 0
Code Actions Activity
Files
rbyd-btree-leaf-caches
littlefs/tests/test_mtree.toml
T
Christopher Haster a49e13b992 Attempted to implement per-btree leaf caches 
The idea here, is we give each lfsr_btree_t an optional leaf rbyd, in
addition to the root rbyd. This leaf rbyd acts as a cache for the most
recent leaf, allowing nearby btree lookups to skip the full btree walk.

Unfortunately, this failed on pretty much every measurable metric...

---

The motivation for this is that we often do a bunch of nearby btree
lookups:

- Btree iteration via lfsr_btree_lookupnext is a bit naive, walking from
  the root every step.

- Our crystallization algorithm requires a bunch of nearby lookups to
  figure out our crystallization heuristic. Currently at most 4, when
  you need to lookup both crystal neighbors and then _also_ both
  fragment neighbors for coalescing.

- Checksum collision resolution for dids and (FUTURE) ddkeys can require
  an unbounded number of sequential lookups.

  Though to be fair, this is an exceptional case if our checksum is any
  good.

- Bids with multiple rattrs require nearby lookups to resolve.

  Though currently this can be explicitly avoided via
  lfsr_btree_lookupleaf + lfsr_rbyd_lookup.

The theory was that cases like these could explicitly keep track of the
leaf rbyd to avoid full btree walks, but in practice this never really
worked out. Tracking if we're still in the relevant leaf rbyd just adds
too much logic/code cost.

But if this leaf tracking logic was implemented once in the btree
layer...

The other theoretical benefit was being able to move more rbyds off the
stack. Sure our btrees take up more RAM, but if that results in stack
savings, that may be a win.

Oh, and this would let our btree API and rbyd API converge without
performance concerns. Internal users could in theory call
lfsr_btree_lookupnext + lfsr_btree_lookup with the same performance as
explicitly tracking the rbyd.

---

But this was a complete failure!

First the good news: There was a modest speedup of around ~2x to linear
reads.

And that's the good news.

Now the bad news:

1. There was no noticeable performance gain in any other benchmarks.

   To be fair, we're at the early stages of benchmarking, so the
   benchmarks may not be the most thorough, but thinking about it, there
   are some explanations:

   - In any benchmark that writes, fetch + erase + prog dominates. Being
     able to skip fetches during lookups makes our btree lookups
     surprisingly cheap!

   - Any random read heavy benchmark is likely thrashing this cache,
     which is to be expected.

   - For small 1-block btrees, the leaf cache is useless because the
     entire btree is cache in the root rbyd.

     And keep in mind, our blocks are BIG. "Small" here could be on
     the order of ~128KiB-1MiB for NAND flash.

   - For the mtree, fetched mdirs actually already act as a sort of leaf
     cache.

     The extra btree leaf cache isn't doing _nothing_, but each layer of
     the mtree has diminishing returns due to btree's ridiculous
     branching factor.

   - For file btrees, we're explicitly caching the leaf fragments/
     blocks, so the extra btree leaf cache has diminishing returns for
     the same reason.

2. Code cost was bad, stack cost was worse:

              code          stack          ctx
     before: 37172           2288          636
     after:  38068 (+2.4%)   2416 (+5.6%)  664 (+4.4%)

   Tracking the leaf required more code, that's expected. And, to be
   fair, the current code has had a lot more time to congeal.

   What wasn't expected was the stack cost.

   Unfortunately these caches didn't really take any rbyds off the stack
   hot-path:

   - We _can_ get rid of the rbyd in lfsr_btree_lookup/namelookup, but
     we were already hacking our way around the critical one in
     lfsr_mtree_lookup/namelookup by reusing the mdir's rbyd!

   - We can't even abuse the leaf rbyd in the commit logic, since the
     target btree can end up iterated/traversed by lfs_alloc.

     That was a fun bug.

   And the addition of a second rbyd to lfsr_btree_t increases both ctx
   and stack anywhere btrees are allocated.

Maybe this will make more sense when we add the auxiliary btrees, or
after more benchmarking, but for now the theoretical performance
improvements just aren't worth it.

Will probably revert this, but I wanted to commit it in case the idea is
worth resurrecting in the future, if in the future nearby btree lookups
are a bigger penalty than they are now.
2025-05-24 18:37:37 -05:00

4905 lines
172 KiB
TOML
Raw Permalink Blame History

# Test the high-level metadata tree in the core of littlefs
after = ['test_rbyd', 'test_btree']
# maximize lookahead buffer, we don't actually gc so we only get one pass
# of the disk for these tests
defines.LOOKAHEAD_SIZE = '(BLOCK_COUNT+8-1) / 8'
# test with normal revision counts, debug revision counts, and noisy
# revision counts
defines.REVDBG = [false, true]
defines.REVNOISE = [false, true]
defines.F_FLAGS = '''
((REVDBG) ? LFS_IFDEF_REVDBG(LFS_F_REVDBG, -1) : 0)
| ((REVNOISE) ? LFS_IFDEF_REVNOISE(LFS_F_REVNOISE, -1) : 0)
'''
defines.M_FLAGS = '''
((REVDBG) ? LFS_IFDEF_REVDBG(LFS_M_REVDBG, -1) : 0)
| ((REVNOISE) ? LFS_IFDEF_REVNOISE(LFS_M_REVNOISE, -1) : 0)
'''
if = [
'LFS_IFDEF_REVDBG(true, !REVDBG)',
'LFS_IFDEF_REVNOISE(true, !REVNOISE)',
'!REVDBG || !REVNOISE',
]
# test a single mroot
[cases.test_mtree_mroot]
code = '''
lfs_t lfs;
lfsr_format(&lfs, LFS_F_RDWR | F_FLAGS, CFG) => 0;
lfsr_mount(&lfs, LFS_M_RDWR | M_FLAGS, CFG) => 0;
lfsr_unmount(&lfs) => 0;
'''
# test a single mroot with attributes
[cases.test_mtree_mroot_rattrs]
defines.N = [1, 3]
in = 'lfs.c'
code = '''
lfs_t lfs;
lfsr_format(&lfs, LFS_F_RDWR | F_FLAGS, CFG) => 0;
lfsr_mount(&lfs, LFS_M_RDWR | M_FLAGS, CFG) => 0;
lfs_alloc_ckpoint(&lfs);
for (lfs_size_t i = 0; i < N; i++) {
lfsr_mdir_commit(&lfs, &lfs.mroot, LFSR_RATTRS(
LFSR_RATTR_BUF(
LFSR_TAG_ATTR(i), 0,
&(uint8_t){'a'+(i % 26)}, 1))) => 0;
}
for (lfs_size_t i = 0; i < N; i++) {
lfsr_data_t data;
uint8_t buffer[1];
lfsr_mdir_lookup(&lfs, &lfs.mroot, LFSR_TAG_ATTR(i), NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, 1) => 1;
assert(memcmp(buffer, &(uint8_t){'a'+(i % 26)}, 1) == 0);
}
lfsr_unmount(&lfs) => 0;
// check things stay sane after remount
lfsr_mount(&lfs, LFS_M_RDWR | M_FLAGS, CFG) => 0;
for (lfs_size_t i = 0; i < N; i++) {
lfsr_data_t data;
uint8_t buffer[1];
lfsr_mdir_lookup(&lfs, &lfs.mroot, LFSR_TAG_ATTR(i), NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, 1) => 1;
assert(memcmp(buffer, &(uint8_t){'a'+(i % 26)}, 1) == 0);
}
lfsr_unmount(&lfs) => 0;
'''
# test a single mroot with forced compaction
[cases.test_mtree_mroot_compact]
defines.N = [1, 3]
in = 'lfs.c'
code = '''
lfs_t lfs;
lfsr_format(&lfs, LFS_F_RDWR | F_FLAGS, CFG) => 0;
lfsr_mount(&lfs, LFS_M_RDWR | M_FLAGS, CFG) => 0;
lfs_alloc_ckpoint(&lfs);
for (lfs_size_t i = 0; i < N; i++) {
// force mroot to compact
lfs.mroot.rbyd.eoff = -1;
lfsr_mdir_commit(&lfs, &lfs.mroot, LFSR_RATTRS(
LFSR_RATTR_BUF(
LFSR_TAG_ATTR(i), 0,
&(uint8_t){'a'+(i % 26)}, 1))) => 0;
}
for (lfs_size_t i = 0; i < N; i++) {
lfsr_data_t data;
uint8_t buffer[1];
lfsr_mdir_lookup(&lfs, &lfs.mroot, LFSR_TAG_ATTR(i), NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, 1) => 1;
assert(memcmp(buffer, &(uint8_t){'a'+(i % 26)}, 1) == 0);
}
lfsr_unmount(&lfs) => 0;
// check things stay sane after remount
lfsr_mount(&lfs, LFS_M_RDWR | M_FLAGS, CFG) => 0;
for (lfs_size_t i = 0; i < N; i++) {
lfsr_data_t data;
uint8_t buffer[1];
lfsr_mdir_lookup(&lfs, &lfs.mroot, LFSR_TAG_ATTR(i), NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, 1) => 1;
assert(memcmp(buffer, &(uint8_t){'a'+(i % 26)}, 1) == 0);
}
lfsr_unmount(&lfs) => 0;
'''
# test a single mroot with many commits
[cases.test_mtree_mroot_many_commits]
defines.N = [5, 5000]
in = 'lfs.c'
code = '''
lfs_t lfs;
lfsr_format(&lfs, LFS_F_RDWR | F_FLAGS, CFG) => 0;
lfsr_mount(&lfs, LFS_M_RDWR | M_FLAGS, CFG) => 0;
lfs_alloc_ckpoint(&lfs);
for (lfs_size_t i = 0; i < N; i++) {
lfsr_mdir_commit(&lfs, &lfs.mroot, LFSR_RATTRS(
LFSR_RATTR_BUF(
LFSR_TAG_ATTR(1), 0,
&(uint8_t){'a'+(i % 26)}, 1))) => 0;
lfsr_data_t data;
uint8_t buffer[4];
lfsr_mdir_lookup(&lfs, &lfs.mroot, LFSR_TAG_ATTR(1), NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, 4) => 1;
assert(memcmp(buffer, &(uint8_t){'a'+(i % 26)}, 1) == 0);
}
lfsr_data_t data;
uint8_t buffer[4];
lfsr_mdir_lookup(&lfs, &lfs.mroot, LFSR_TAG_ATTR(1), NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, 4) => 1;
assert(memcmp(buffer, &(uint8_t){'a'+((N-1) % 26)}, 1) == 0);
lfsr_unmount(&lfs) => 0;
// check things stay sane after remount
lfsr_mount(&lfs, LFS_M_RDWR | M_FLAGS, CFG) => 0;
lfsr_mdir_lookup(&lfs, &lfs.mroot, LFSR_TAG_ATTR(1), NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, 4) => 1;
assert(memcmp(buffer, &(uint8_t){'a'+((N-1) % 26)}, 1) == 0);
lfsr_unmount(&lfs) => 0;
'''
## Splitting operations ##
# specific split corner cases
[cases.test_mtree_uninline]
# this should be set so only one entry can fit in a metadata block
defines.SIZE = 'BLOCK_SIZE / 4'
in = 'lfs.c'
code = '''
lfs_t lfs;
lfsr_format(&lfs, LFS_F_RDWR | F_FLAGS, CFG) => 0;
lfsr_mount(&lfs, LFS_M_RDWR | M_FLAGS, CFG) => 0;
lfs_alloc_ckpoint(&lfs);
lfsr_data_t data;
// create a 2 large rattrs that needs to be uninlined
uint8_t buffer[SIZE];
memset(buffer, 'a', SIZE);
lfsr_mdir_commit(&lfs, &lfs.mroot, LFSR_RATTRS(
LFSR_RATTR_BUF(LFSR_TAG_ATTR(1), 0, buffer, SIZE))) => 0;
memset(buffer, 'b', SIZE);
lfsr_mdir_t mdir;
lfsr_mtree_lookup(&lfs, 0, &mdir) => 0;
lfsr_mdir_commit(&lfs, &mdir, LFSR_RATTRS(
LFSR_RATTR_BUF(LFSR_TAG_ATTR(2), 0, buffer, SIZE))) => 0;
// force mroot to compact
lfs.mroot.rbyd.eoff = -1;
lfsr_mdir_commit(&lfs, &lfs.mroot, LFSR_RATTRS(
LFSR_RATTR_BUF(LFSR_TAG_ATTR(3), 0, "c", 1))) => 0;
// assert mdirs were unininlined
assert(lfs.mtree.root.weight == (1 << lfs.mbits));
// assert mroot now has no entries
assert(lfs.mroot.rbyd.weight == 0);
// assert that our rattrs are still in the mroot/mtree
lfsr_mdir_lookup(&lfs, &lfs.mroot, LFSR_TAG_ATTR(1), NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, SIZE) => SIZE;
assert(buffer[0] == 'a');
lfsr_mtree_lookup(&lfs, 0, &mdir) => 0;
assert(mdir.rbyd.weight == 1);
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_ATTR(2), NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, SIZE) => SIZE;
assert(buffer[0] == 'b');
lfsr_mdir_lookup(&lfs, &lfs.mroot, LFSR_TAG_ATTR(3), NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, 1) => 1;
assert(buffer[0] == 'c');
// check things stay sane after remount
lfsr_unmount(&lfs) => 0;
lfsr_mount(&lfs, LFS_M_RDWR | M_FLAGS, CFG) => 0;
// assert mdirs were unininlined
assert(lfs.mtree.root.weight == (1 << lfs.mbits));
// assert mroot now has no entries
assert(lfs.mroot.rbyd.weight == 0);
// assert that our rattrs are still in the mroot/mtree
lfsr_mdir_lookup(&lfs, &lfs.mroot, LFSR_TAG_ATTR(1), NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, SIZE) => SIZE;
assert(buffer[0] == 'a');
lfsr_mtree_lookup(&lfs, 0, &mdir) => 0;
assert(mdir.rbyd.weight == 1);
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_ATTR(2), NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, SIZE) => SIZE;
assert(buffer[0] == 'b');
lfsr_mdir_lookup(&lfs, &lfs.mroot, LFSR_TAG_ATTR(3), NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, 1) => 1;
assert(buffer[0] == 'c');
lfsr_unmount(&lfs) => 0;
'''
[cases.test_mtree_uninline_split]
# this should be set so only one entry can fit in a metadata block
defines.SIZE = 'BLOCK_SIZE / 4'
in = 'lfs.c'
code = '''
lfs_t lfs;
lfsr_format(&lfs, LFS_F_RDWR | F_FLAGS, CFG) => 0;
lfsr_mount(&lfs, LFS_M_RDWR | M_FLAGS, CFG) => 0;
lfs_alloc_ckpoint(&lfs);
lfsr_data_t data;
// create 2 large entries that needs to be uninlined and split
uint8_t buffer[SIZE];
buffer[0] = '\0';
memset(buffer+1, 'a', SIZE-1);
lfsr_mdir_t mdir;
lfsr_mtree_namelookup(&lfs, 0, (const char*)buffer+1, SIZE-1,
&mdir, NULL, NULL) => LFS_ERR_NOENT;
lfsr_mdir_commit(&lfs, &mdir, LFSR_RATTRS(
LFSR_RATTR_NAME(
LFSR_TAG_REG, +1,
0, (const char*)buffer+1, SIZE-1))) => 0;
assert(mdir.rbyd.weight == 2);
memset(buffer+1, 'b', SIZE-1);
lfsr_mtree_namelookup(&lfs, 0, (const char*)buffer+1, SIZE-1,
&mdir, NULL, NULL) => LFS_ERR_NOENT;
lfsr_mdir_commit(&lfs, &mdir, LFSR_RATTRS(
LFSR_RATTR_NAME(
LFSR_TAG_REG, +1,
0, (const char*)buffer+1, SIZE-1))) => 0;
assert(mdir.rbyd.weight == 3);
// force mroot to compact
lfs.mroot.rbyd.eoff = -1;
lfsr_mdir_commit(&lfs, &lfs.mroot, LFSR_RATTRS(
LFSR_RATTR_BUF(LFSR_TAG_ATTR(1), 0, "c", 1))) => 0;
// assert mdirs were unininlined and split
assert(lfs.mtree.root.weight == (2 << lfs.mbits));
// assert mroot now has no entries
assert(lfs.mroot.rbyd.weight == 0);
// assert that our entries are still in the mtree
lfsr_mtree_lookup(&lfs, (0 << lfs.mbits)+1, &mdir) => 0;
assert(mdir.rbyd.weight == 2);
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_REG, NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, SIZE) => SIZE;
assert(buffer[1] == 'a');
lfsr_mtree_lookup(&lfs, (1 << lfs.mbits)+0, &mdir) => 0;
assert(mdir.rbyd.weight == 1);
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_REG, NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, SIZE) => SIZE;
assert(buffer[1] == 'b');
lfsr_mdir_lookup(&lfs, &lfs.mroot, LFSR_TAG_ATTR(1), NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, 1) => 1;
assert(buffer[0] == 'c');
// check things stay sane after remount
lfsr_unmount(&lfs) => 0;
lfsr_mount(&lfs, LFS_M_RDWR | M_FLAGS, CFG) => 0;
// assert mdirs were unininlined and split
assert(lfs.mtree.root.weight == (2 << lfs.mbits));
// assert mroot now has no entries
assert(lfs.mroot.rbyd.weight == 0);
// assert that our entries are still in the mtree
lfsr_mtree_lookup(&lfs, (0 << lfs.mbits)+1, &mdir) => 0;
assert(mdir.rbyd.weight == 2);
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_REG, NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, SIZE) => SIZE;
assert(buffer[1] == 'a');
lfsr_mtree_lookup(&lfs, (1 << lfs.mbits)+0, &mdir) => 0;
assert(mdir.rbyd.weight == 1);
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_REG, NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, SIZE) => SIZE;
assert(buffer[1] == 'b');
lfsr_mdir_lookup(&lfs, &lfs.mroot, LFSR_TAG_ATTR(1), NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, 1) => 1;
assert(buffer[0] == 'c');
lfsr_unmount(&lfs) => 0;
'''
[cases.test_mtree_split]
# this should be set so only one entry can fit in a metadata block
defines.SIZE = 'BLOCK_SIZE / 4'
in = 'lfs.c'
code = '''
lfs_t lfs;
lfsr_format(&lfs, LFS_F_RDWR | F_FLAGS, CFG) => 0;
lfsr_mount(&lfs, LFS_M_RDWR | M_FLAGS, CFG) => 0;
lfs_alloc_ckpoint(&lfs);
lfsr_data_t data;
// create 2 large entries that needs to be uninlined and split
uint8_t buffer[SIZE];
buffer[0] = '\0';
memset(buffer+1, 'a', SIZE-1);
lfsr_mdir_t mdir;
lfsr_mtree_namelookup(&lfs, 0, (const char*)buffer+1, SIZE-1,
&mdir, NULL, NULL) => LFS_ERR_NOENT;
lfsr_mdir_commit(&lfs, &mdir, LFSR_RATTRS(
LFSR_RATTR_NAME(
LFSR_TAG_REG, +1,
0, (const char*)buffer+1, SIZE-1))) => 0;
assert(mdir.rbyd.weight == 2);
memset(buffer+1, 'b', SIZE-1);
lfsr_mtree_namelookup(&lfs, 0, (const char*)buffer+1, SIZE-1,
&mdir, NULL, NULL) => LFS_ERR_NOENT;
lfsr_mdir_commit(&lfs, &mdir, LFSR_RATTRS(
LFSR_RATTR_NAME(
LFSR_TAG_REG, +1,
0, (const char*)buffer+1, SIZE-1))) => 0;
assert(mdir.rbyd.weight == 3);
// force mroot to compact
lfs.mroot.rbyd.eoff = -1;
lfsr_mdir_commit(&lfs, &lfs.mroot, LFSR_RATTRS(
LFSR_RATTR_BUF(LFSR_TAG_ATTR(1), 0, "c", 1))) => 0;
// assert mdirs were unininlined and split
assert(lfs.mtree.root.weight == (2 << lfs.mbits));
// assert mroot now has no entries
assert(lfs.mroot.rbyd.weight == 0);
// now add another large entry to an mdir, forcing a split
memset(buffer+1, 'd', SIZE-1);
lfsr_mtree_namelookup(&lfs, 0, (const char*)buffer+1, SIZE-1,
&mdir, NULL, NULL) => LFS_ERR_NOENT;
lfsr_mdir_commit(&lfs, &mdir, LFSR_RATTRS(
LFSR_RATTR_NAME(
LFSR_TAG_REG, +1,
0, (const char*)buffer+1, SIZE-1))) => 0;
assert(mdir.rbyd.weight == 2);
// force mdir to compact
mdir.rbyd.eoff = -1;
lfsr_mdir_commit(&lfs, &mdir, LFSR_RATTRS(
LFSR_RATTR_BUF(LFSR_TAG_ATTR(2), 0, "e", 1))) => 0;
// assert mdir was split correctly
assert(lfs.mtree.root.weight == (3 << lfs.mbits));
// assert mroot still has no entries
assert(lfs.mroot.rbyd.weight == 0);
// assert that our entries are still in the mtree
lfsr_mtree_lookup(&lfs, (0 << lfs.mbits)+1, &mdir) => 0;
assert(mdir.rbyd.weight == 2);
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_REG, NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, SIZE) => SIZE;
assert(buffer[1] == 'a');
lfsr_mtree_lookup(&lfs, (1 << lfs.mbits)+0, &mdir) => 0;
assert(mdir.rbyd.weight == 1);
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_REG, NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, SIZE) => SIZE;
assert(buffer[1] == 'b');
lfsr_mdir_lookup(&lfs, &lfs.mroot, LFSR_TAG_ATTR(1), NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, 1) => 1;
assert(buffer[0] == 'c');
lfsr_mtree_lookup(&lfs, (2 << lfs.mbits)+0, &mdir) => 0;
assert(mdir.rbyd.weight == 1);
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_REG, NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, SIZE) => SIZE;
assert(buffer[1] == 'd');
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_ATTR(2), NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, 1) => 1;
assert(buffer[0] == 'e');
// check things stay sane after remount
lfsr_unmount(&lfs) => 0;
lfsr_mount(&lfs, LFS_M_RDWR | M_FLAGS, CFG) => 0;
// assert mdir was split correctly
assert(lfs.mtree.root.weight == (3 << lfs.mbits));
// assert mroot still has no entries
assert(lfs.mroot.rbyd.weight == 0);
// assert that our entries are still in the mtree
lfsr_mtree_lookup(&lfs, (0 << lfs.mbits)+1, &mdir) => 0;
assert(mdir.rbyd.weight == 2);
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_REG, NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, SIZE) => SIZE;
assert(buffer[1] == 'a');
lfsr_mtree_lookup(&lfs, (1 << lfs.mbits)+0, &mdir) => 0;
assert(mdir.rbyd.weight == 1);
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_REG, NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, SIZE) => SIZE;
assert(buffer[1] == 'b');
lfsr_mdir_lookup(&lfs, &lfs.mroot, LFSR_TAG_ATTR(1), NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, 1) => 1;
assert(buffer[0] == 'c');
lfsr_mtree_lookup(&lfs, (2 << lfs.mbits)+0, &mdir) => 0;
assert(mdir.rbyd.weight == 1);
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_REG, NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, SIZE) => SIZE;
assert(buffer[1] == 'd');
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_ATTR(2), NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, 1) => 1;
assert(buffer[0] == 'e');
lfsr_unmount(&lfs) => 0;
'''
# try creating a range of entries that may or may not split our mtree
[cases.test_mtree_split_many]
defines.N = [5, 10, 20, 40, 80, 160, 320]
defines.FORCE_COMPACTION = [false, true]
in = 'lfs.c'
code = '''
lfs_t lfs;
lfsr_format(&lfs, LFS_F_RDWR | F_FLAGS, CFG) => 0;
lfsr_mount(&lfs, LFS_M_RDWR | M_FLAGS, CFG) => 0;
lfs_alloc_ckpoint(&lfs);
// create entries
for (lfs_size_t i = 0; i < N; i++) {
char name[256];
name[0] = '\0';
sprintf(name+1, "%03x", i);
lfsr_mdir_t mdir;
lfsr_mtree_namelookup(&lfs, 0, name+1, 3,
&mdir, NULL, NULL) => LFS_ERR_NOENT;
// force a compaction?
if (FORCE_COMPACTION) {
lfs.mroot.rbyd.eoff = -1;
mdir.rbyd.eoff = -1;
}
lfsr_mdir_commit(&lfs, &mdir, LFSR_RATTRS(
LFSR_RATTR_NAME(LFSR_TAG_REG, +1, 0, name+1, 3))) => 0;
lfsr_data_t data;
uint8_t buffer[256];
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_REG, NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, sizeof(buffer)) => 4;
assert(memcmp(buffer, name, 4) == 0);
}
// try looking up each entry
lfsr_mdir_t mdir;
lfsr_mtree_lookup(&lfs, 0, &mdir) => 0;
lfsr_data_t data;
uint8_t buffer[256];
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_BOOKMARK, NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, sizeof(buffer)) => 1;
for (lfs_size_t i = 0; i < N; i++) {
char name[256];
name[0] = '\0';
sprintf(name+1, "%03x", i);
mdir.mid += 1;
if (lfsr_mrid(&lfs, mdir.mid) >= (lfsr_srid_t)mdir.rbyd.weight) {
lfsr_mtree_lookup(&lfs, lfsr_mbid(&lfs, mdir.mid) + 1,
&mdir) => 0;
}
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_REG, NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, sizeof(buffer)) => 4;
assert(memcmp(buffer, name, 4) == 0);
}
// check things stay sane after remount
lfsr_unmount(&lfs) => 0;
lfsr_mount(&lfs, LFS_M_RDWR | M_FLAGS, CFG) => 0;
// try looking up each entry
lfsr_mtree_lookup(&lfs, 0, &mdir) => 0;
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_BOOKMARK, NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, sizeof(buffer)) => 1;
for (lfs_size_t i = 0; i < N; i++) {
char name[256];
name[0] = '\0';
sprintf(name+1, "%03x", i);
mdir.mid += 1;
if (lfsr_mrid(&lfs, mdir.mid) >= (lfsr_srid_t)mdir.rbyd.weight) {
lfsr_mtree_lookup(&lfs, lfsr_mbid(&lfs, mdir.mid) + 1,
&mdir) => 0;
}
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_REG, NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, sizeof(buffer)) => 4;
assert(memcmp(buffer, name, 4) == 0);
}
lfsr_unmount(&lfs) => 0;
'''
# create random entries
[cases.test_mtree_split_fuzz]
defines.N = [5, 10, 20, 40, 80, 160]
defines.FORCE_COMPACTION = [false, true]
defines.SEED = 'range(100)'
fuzz = 'SEED'
in = 'lfs.c'
code = '''
lfs_t lfs;
lfsr_format(&lfs, LFS_F_RDWR | F_FLAGS, CFG) => 0;
lfsr_mount(&lfs, LFS_M_RDWR | M_FLAGS, CFG) => 0;
lfs_alloc_ckpoint(&lfs);
bool sim[N];
for (lfs_size_t i = 0; i < N; i++) {
sim[i] = false;
}
uint32_t prng = SEED;
for (lfs_size_t i = 0; i < N; i++) {
// choose a pseudo-random name
lfs_size_t x = TEST_PRNG(&prng) % N;
// update sim
sim[x] = true;
// update mtree
char name[256];
name[0] = '\0';
sprintf(name+1, "%03x", x);
lfsr_mdir_t mdir;
int err = lfsr_mtree_namelookup(&lfs, 0, name+1, 3,
&mdir, NULL, NULL);
assert(!err || err == LFS_ERR_NOENT);
if (!err) {
continue;
}
// force a compaction?
if (FORCE_COMPACTION) {
lfs.mroot.rbyd.eoff = -1;
mdir.rbyd.eoff = -1;
}
lfsr_mdir_commit(&lfs, &mdir, LFSR_RATTRS(
LFSR_RATTR_NAME(LFSR_TAG_REG, +1, 0, name+1, 3))) => 0;
lfsr_data_t data;
// double check
uint8_t buffer[256];
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_REG, NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, sizeof(buffer)) => 4;
assert(memcmp(buffer, name, 4) == 0);
}
// try looking up each entry
lfsr_mdir_t mdir;
lfsr_mtree_lookup(&lfs, 0, &mdir) => 0;
lfsr_data_t data;
uint8_t buffer[256];
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_BOOKMARK, NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, sizeof(buffer)) => 1;
for (lfs_size_t i = 0; i < N; i++) {
char name[256];
name[0] = '\0';
sprintf(name+1, "%03x", i);
if (sim[i]) {
lfsr_mtree_namelookup(&lfs, 0, name+1, 3,
&mdir, NULL, NULL) => 0;
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_REG, NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, sizeof(buffer)) => 4;
assert(memcmp(buffer, name, 4) == 0);
} else {
lfsr_mtree_namelookup(&lfs, 0, name+1, 3,
&mdir, NULL, NULL) => LFS_ERR_NOENT;
}
}
// check things stay sane after remount
lfsr_unmount(&lfs) => 0;
lfsr_mount(&lfs, LFS_M_RDWR | M_FLAGS, CFG) => 0;
// try looking up each entry
lfsr_mtree_lookup(&lfs, 0, &mdir) => 0;
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_BOOKMARK, NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, sizeof(buffer)) => 1;
for (lfs_size_t i = 0; i < N; i++) {
char name[256];
name[0] = '\0';
sprintf(name+1, "%03x", i);
if (sim[i]) {
lfsr_mtree_namelookup(&lfs, 0, name+1, 3,
&mdir, NULL, NULL) => 0;
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_REG, NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, sizeof(buffer)) => 4;
assert(memcmp(buffer, name, 4) == 0);
} else {
lfsr_mtree_namelookup(&lfs, 0, name+1, 3,
&mdir, NULL, NULL) => LFS_ERR_NOENT;
}
}
lfsr_unmount(&lfs) => 0;
'''
## Dropping operations ##
# specific drop corner cases
[cases.test_mtree_drop]
# this should be set so only one entry can fit in a metadata block
defines.SIZE = 'BLOCK_SIZE / 4'
in = 'lfs.c'
code = '''
lfs_t lfs;
lfsr_format(&lfs, LFS_F_RDWR | F_FLAGS, CFG) => 0;
lfsr_mount(&lfs, LFS_M_RDWR | M_FLAGS, CFG) => 0;
lfs_alloc_ckpoint(&lfs);
lfsr_data_t data;
// create 2 large entries that needs to be uninlined and split
uint8_t buffer[SIZE];
buffer[0] = '\0';
memset(buffer+1, 'a', SIZE-1);
lfsr_mdir_t mdir;
lfsr_mtree_namelookup(&lfs, 0, (const char*)buffer+1, SIZE-1,
&mdir, NULL, NULL) => LFS_ERR_NOENT;
lfsr_mdir_commit(&lfs, &mdir, LFSR_RATTRS(
LFSR_RATTR_NAME(
LFSR_TAG_REG, +1,
0, (const char*)buffer+1, SIZE-1))) => 0;
assert(mdir.rbyd.weight == 2);
memset(buffer+1, 'b', SIZE-1);
lfsr_mtree_namelookup(&lfs, 0, (const char*)buffer+1, SIZE-1,
&mdir, NULL, NULL) => LFS_ERR_NOENT;
lfsr_mdir_commit(&lfs, &mdir, LFSR_RATTRS(
LFSR_RATTR_NAME(
LFSR_TAG_REG, +1,
0, (const char*)buffer+1, SIZE-1))) => 0;
assert(mdir.rbyd.weight == 3);
// force mroot to compact
lfs.mroot.rbyd.eoff = -1;
lfsr_mdir_commit(&lfs, &lfs.mroot, LFSR_RATTRS(
LFSR_RATTR_BUF(LFSR_TAG_ATTR(1), 0, "c", 1))) => 0;
// assert mdirs were unininlined and split
assert(lfs.mtree.root.weight == (2 << lfs.mbits));
// assert mroot now has no entries
assert(lfs.mroot.rbyd.weight == 0);
// remove an entry, forcing the mdir to be dropped
memset(buffer+1, 'b', SIZE-1);
lfsr_mtree_namelookup(&lfs, 0, (const char*)buffer+1, SIZE-1,
&mdir, NULL, NULL) => 0;
lfsr_mdir_commit(&lfs, &mdir, LFSR_RATTRS(
LFSR_RATTR(LFSR_TAG_RM, -1))) => 0;
assert(mdir.rbyd.weight == 0);
// assert mdir was dropped
assert(lfs.mtree.root.weight == (1 << lfs.mbits));
// assert mroot still has no entries
assert(lfs.mroot.rbyd.weight == 0);
// assert that our entries are still in the mtree
lfsr_mtree_lookup(&lfs, (0 << lfs.mbits)+1, &mdir) => 0;
assert(mdir.rbyd.weight == 2);
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_REG, NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, SIZE) => SIZE;
assert(buffer[1] == 'a');
lfsr_mdir_lookup(&lfs, &lfs.mroot, LFSR_TAG_ATTR(1), NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, 1) => 1;
assert(buffer[0] == 'c');
// check things stay sane after remount
lfsr_unmount(&lfs) => 0;
lfsr_mount(&lfs, LFS_M_RDWR | M_FLAGS, CFG) => 0;
// assert mdir was dropped
assert(lfs.mtree.root.weight == (1 << lfs.mbits));
// assert mroot still has no entries
assert(lfs.mroot.rbyd.weight == 0);
// assert that our entries are still in the mtree
lfsr_mtree_lookup(&lfs, (0 << lfs.mbits)+1, &mdir) => 0;
assert(mdir.rbyd.weight == 2);
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_REG, NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, SIZE) => SIZE;
assert(buffer[1] == 'a');
lfsr_mdir_lookup(&lfs, &lfs.mroot, LFSR_TAG_ATTR(1), NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, 1) => 1;
assert(buffer[0] == 'c');
lfsr_unmount(&lfs) => 0;
'''
[cases.test_mtree_drop_compact]
# this should be set so only one entry can fit in a metadata block
defines.SIZE = 'BLOCK_SIZE / 4'
in = 'lfs.c'
code = '''
lfs_t lfs;
lfsr_format(&lfs, LFS_F_RDWR | F_FLAGS, CFG) => 0;
lfsr_mount(&lfs, LFS_M_RDWR | M_FLAGS, CFG) => 0;
lfs_alloc_ckpoint(&lfs);
lfsr_data_t data;
// create 2 large entries that needs to be uninlined and split
uint8_t buffer[SIZE];
buffer[0] = '\0';
memset(buffer+1, 'a', SIZE-1);
lfsr_mdir_t mdir;
lfsr_mtree_namelookup(&lfs, 0, (const char*)buffer+1, SIZE-1,
&mdir, NULL, NULL) => LFS_ERR_NOENT;
lfsr_mdir_commit(&lfs, &mdir, LFSR_RATTRS(
LFSR_RATTR_NAME(
LFSR_TAG_REG, +1,
0, (const char*)buffer+1, SIZE-1))) => 0;
assert(mdir.rbyd.weight == 2);
memset(buffer+1, 'b', SIZE-1);
lfsr_mtree_namelookup(&lfs, 0, (const char*)buffer+1, SIZE-1,
&mdir, NULL, NULL) => LFS_ERR_NOENT;
lfsr_mdir_commit(&lfs, &mdir, LFSR_RATTRS(
LFSR_RATTR_NAME(
LFSR_TAG_REG, +1,
0, (const char*)buffer+1, SIZE-1))) => 0;
assert(mdir.rbyd.weight == 3);
// force mroot to compact
lfs.mroot.rbyd.eoff = -1;
lfsr_mdir_commit(&lfs, &lfs.mroot, LFSR_RATTRS(
LFSR_RATTR_BUF(LFSR_TAG_ATTR(1), 0, "c", 1))) => 0;
// assert mdirs were unininlined and split
assert(lfs.mtree.root.weight == (2 << lfs.mbits));
// assert mroot now has no entries
assert(lfs.mroot.rbyd.weight == 0);
// remove an entry, forcing the mdir to be dropped
memset(buffer+1, 'b', SIZE-1);
lfsr_mtree_namelookup(&lfs, 0, (const char*)buffer+1, SIZE-1,
&mdir, NULL, NULL) => 0;
// force mdir to compact while we're removing
mdir.rbyd.eoff = -1;
lfsr_mdir_commit(&lfs, &mdir, LFSR_RATTRS(
LFSR_RATTR(LFSR_TAG_RM, -1))) => 0;
assert(mdir.rbyd.weight == 0);
// assert mdir was dropped
assert(lfs.mtree.root.weight == (1 << lfs.mbits));
// assert mroot still has no entries
assert(lfs.mroot.rbyd.weight == 0);
// assert that our entries are still in the mtree
lfsr_mtree_lookup(&lfs, (0 << lfs.mbits)+1, &mdir) => 0;
assert(mdir.rbyd.weight == 2);
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_REG, NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, SIZE) => SIZE;
assert(buffer[1] == 'a');
lfsr_mdir_lookup(&lfs, &lfs.mroot, LFSR_TAG_ATTR(1), NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, 1) => 1;
assert(buffer[0] == 'c');
// check things stay sane after remount
lfsr_unmount(&lfs) => 0;
lfsr_mount(&lfs, LFS_M_RDWR | M_FLAGS, CFG) => 0;
// assert mdir was dropped
assert(lfs.mtree.root.weight == (1 << lfs.mbits));
// assert mroot still has no entries
assert(lfs.mroot.rbyd.weight == 0);
// assert that our entries are still in the mtree
lfsr_mtree_lookup(&lfs, (0 << lfs.mbits)+1, &mdir) => 0;
assert(mdir.rbyd.weight == 2);
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_REG, NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, SIZE) => SIZE;
assert(buffer[1] == 'a');
lfsr_mdir_lookup(&lfs, &lfs.mroot, LFSR_TAG_ATTR(1), NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, 1) => 1;
assert(buffer[0] == 'c');
lfsr_unmount(&lfs) => 0;
'''
[cases.test_mtree_drop_uninline_split]
# this should be set so only one entry can fit in a metadata block
defines.SIZE = 'BLOCK_SIZE / 4'
in = 'lfs.c'
code = '''
lfs_t lfs;
lfsr_format(&lfs, LFS_F_RDWR | F_FLAGS, CFG) => 0;
lfsr_mount(&lfs, LFS_M_RDWR | M_FLAGS, CFG) => 0;
lfs_alloc_ckpoint(&lfs);
lfsr_data_t data;
// create 2 large entries that needs to be uninlined and split
uint8_t buffer[SIZE];
buffer[0] = '\0';
memset(buffer+1, 'a', SIZE-1);
lfsr_mdir_t mdir;
lfsr_mtree_namelookup(&lfs, 0, (const char*)buffer+1, SIZE-1,
&mdir, NULL, NULL) => LFS_ERR_NOENT;
lfsr_mdir_commit(&lfs, &mdir, LFSR_RATTRS(
LFSR_RATTR_NAME(
LFSR_TAG_REG, +1,
0, (const char*)buffer+1, SIZE-1))) => 0;
assert(mdir.rbyd.weight == 2);
memset(buffer+1, 'b', SIZE-1);
lfsr_mtree_namelookup(&lfs, 0, (const char*)buffer+1, SIZE-1,
&mdir, NULL, NULL) => LFS_ERR_NOENT;
lfsr_mdir_commit(&lfs, &mdir, LFSR_RATTRS(
LFSR_RATTR_NAME(
LFSR_TAG_REG, +1,
0, (const char*)buffer+1, SIZE-1))) => 0;
assert(mdir.rbyd.weight == 3);
// remove an entry, forcing the mdir to be dropped
memset(buffer+1, 'b', SIZE-1);
lfsr_mtree_namelookup(&lfs, 0, (const char*)buffer+1, SIZE-1,
&mdir, NULL, NULL) => 0;
// force mdir to compact while we're removing
lfs.mroot.rbyd.eoff = -1;
mdir.rbyd.eoff = -1;
lfsr_mdir_commit(&lfs, &mdir, LFSR_RATTRS(
LFSR_RATTR(LFSR_TAG_RM, -1))) => 0;
assert(mdir.rbyd.weight == 2);
// assert split/drop worked out
assert(lfs.mtree.root.weight == (1 << lfs.mbits));
// assert mroot still has no entries
assert(lfs.mroot.rbyd.weight == 0);
// assert that our entries are still in the mtree
lfsr_mtree_lookup(&lfs, (0 << lfs.mbits)+1, &mdir) => 0;
assert(mdir.rbyd.weight == 2);
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_REG, NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, SIZE) => SIZE;
assert(buffer[1] == 'a');
// check things stay sane after remount
lfsr_unmount(&lfs) => 0;
lfsr_mount(&lfs, LFS_M_RDWR | M_FLAGS, CFG) => 0;
// assert mdir was dropped
assert(lfs.mtree.root.weight == (1 << lfs.mbits));
// assert mroot still has no entries
assert(lfs.mroot.rbyd.weight == 0);
// assert that our entries are still in the mtree
lfsr_mtree_lookup(&lfs, (0 << lfs.mbits)+1, &mdir) => 0;
assert(mdir.rbyd.weight == 2);
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_REG, NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, SIZE) => SIZE;
assert(buffer[1] == 'a');
lfsr_unmount(&lfs) => 0;
'''
[cases.test_mtree_drop_split_l]
# this should be set so only one entry can fit in a metadata block
defines.SIZE = 'BLOCK_SIZE / 4'
in = 'lfs.c'
code = '''
lfs_t lfs;
lfsr_format(&lfs, LFS_F_RDWR | F_FLAGS, CFG) => 0;
lfsr_mount(&lfs, LFS_M_RDWR | M_FLAGS, CFG) => 0;
lfs_alloc_ckpoint(&lfs);
lfsr_data_t data;
// create 2 large entries that needs to be uninlined and split
uint8_t buffer[SIZE];
buffer[0] = '\0';
memset(buffer+1, 'a', SIZE-1);
lfsr_mdir_t mdir;
lfsr_mtree_namelookup(&lfs, 0, (const char*)buffer+1, SIZE-1,
&mdir, NULL, NULL) => LFS_ERR_NOENT;
lfsr_mdir_commit(&lfs, &mdir, LFSR_RATTRS(
LFSR_RATTR_NAME(
LFSR_TAG_REG, +1,
0, (const char*)buffer+1, SIZE-1))) => 0;
assert(mdir.rbyd.weight == 2);
memset(buffer+1, 'b', SIZE-1);
lfsr_mtree_namelookup(&lfs, 0, (const char*)buffer+1, SIZE-1,
&mdir, NULL, NULL) => LFS_ERR_NOENT;
lfsr_mdir_commit(&lfs, &mdir, LFSR_RATTRS(
LFSR_RATTR_NAME(
LFSR_TAG_REG, +1,
0, (const char*)buffer+1, SIZE-1))) => 0;
assert(mdir.rbyd.weight == 3);
// force mroot to compact
lfs.mroot.rbyd.eoff = -1;
lfsr_mdir_commit(&lfs, &lfs.mroot, LFSR_RATTRS(
LFSR_RATTR_BUF(LFSR_TAG_ATTR(1), 0, "c", 1))) => 0;
// assert mdirs were unininlined and split
assert(lfs.mtree.root.weight == (2 << lfs.mbits));
// assert mroot now has no entries
assert(lfs.mroot.rbyd.weight == 0);
// now add another large entry to an mdir, forcing a split
memset(buffer+1, 'd', SIZE-1);
lfsr_mtree_namelookup(&lfs, 0, (const char*)buffer+1, SIZE-1,
&mdir, NULL, NULL) => LFS_ERR_NOENT;
lfsr_mdir_commit(&lfs, &mdir, LFSR_RATTRS(
LFSR_RATTR_NAME(
LFSR_TAG_REG, +1,
0, (const char*)buffer+1, SIZE-1))) => 0;
assert(mdir.rbyd.weight == 2);
// remove an entry, forcing the mdir to be dropped
memset(buffer+1, 'b', SIZE-1);
lfsr_mtree_namelookup(&lfs, 0, (const char*)buffer+1, SIZE-1,
&mdir, NULL, NULL) => 0;
// force mdir to compact while we're removing
mdir.rbyd.eoff = -1;
lfsr_mdir_commit(&lfs, &mdir, LFSR_RATTRS(
LFSR_RATTR(LFSR_TAG_RM, -1))) => 0;
assert(mdir.rbyd.weight == 1);
// assert split/drop worked out
assert(lfs.mtree.root.weight == (2 << lfs.mbits));
// assert mroot still has no entries
assert(lfs.mroot.rbyd.weight == 0);
// assert that our entries are still in the mtree
lfsr_mtree_lookup(&lfs, (0 << lfs.mbits)+1, &mdir) => 0;
assert(mdir.rbyd.weight == 2);
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_REG, NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, SIZE) => SIZE;
assert(buffer[1] == 'a');
lfsr_mdir_lookup(&lfs, &lfs.mroot, LFSR_TAG_ATTR(1), NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, 1) => 1;
assert(buffer[0] == 'c');
lfsr_mtree_lookup(&lfs, (1 << lfs.mbits)+0, &mdir) => 0;
assert(mdir.rbyd.weight == 1);
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_REG, NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, SIZE) => SIZE;
assert(buffer[1] == 'd');
// check things stay sane after remount
lfsr_unmount(&lfs) => 0;
lfsr_mount(&lfs, LFS_M_RDWR | M_FLAGS, CFG) => 0;
// assert split/drop worked out
assert(lfs.mtree.root.weight == (2 << lfs.mbits));
// assert mroot still has no entries
assert(lfs.mroot.rbyd.weight == 0);
// assert that our entries are still in the mtree
lfsr_mtree_lookup(&lfs, (0 << lfs.mbits)+1, &mdir) => 0;
assert(mdir.rbyd.weight == 2);
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_REG, NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, SIZE) => SIZE;
assert(buffer[1] == 'a');
lfsr_mdir_lookup(&lfs, &lfs.mroot, LFSR_TAG_ATTR(1), NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, 1) => 1;
assert(buffer[0] == 'c');
lfsr_mtree_lookup(&lfs, (1 << lfs.mbits)+0, &mdir) => 0;
assert(mdir.rbyd.weight == 1);
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_REG, NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, SIZE) => SIZE;
assert(buffer[1] == 'd');
lfsr_unmount(&lfs) => 0;
'''
[cases.test_mtree_drop_split_r]
# this should be set so only one entry can fit in a metadata block
defines.SIZE = 'BLOCK_SIZE / 4'
in = 'lfs.c'
code = '''
lfs_t lfs;
lfsr_format(&lfs, LFS_F_RDWR | F_FLAGS, CFG) => 0;
lfsr_mount(&lfs, LFS_M_RDWR | M_FLAGS, CFG) => 0;
lfs_alloc_ckpoint(&lfs);
lfsr_data_t data;
// create 2 large entries that needs to be uninlined and split
uint8_t buffer[SIZE];
buffer[0] = '\0';
memset(buffer+1, 'a', SIZE-1);
lfsr_mdir_t mdir;
lfsr_mtree_namelookup(&lfs, 0, (const char*)buffer+1, SIZE-1,
&mdir, NULL, NULL) => LFS_ERR_NOENT;
lfsr_mdir_commit(&lfs, &mdir, LFSR_RATTRS(
LFSR_RATTR_NAME(
LFSR_TAG_REG, +1,
0, (const char*)buffer+1, SIZE-1))) => 0;
assert(mdir.rbyd.weight == 2);
memset(buffer+1, 'b', SIZE-1);
lfsr_mtree_namelookup(&lfs, 0, (const char*)buffer+1, SIZE-1,
&mdir, NULL, NULL) => LFS_ERR_NOENT;
lfsr_mdir_commit(&lfs, &mdir, LFSR_RATTRS(
LFSR_RATTR_NAME(
LFSR_TAG_REG, +1,
0, (const char*)buffer+1, SIZE-1))) => 0;
assert(mdir.rbyd.weight == 3);
// force mroot to compact
lfs.mroot.rbyd.eoff = -1;
lfsr_mdir_commit(&lfs, &lfs.mroot, LFSR_RATTRS(
LFSR_RATTR_BUF(LFSR_TAG_ATTR(1), 0, "c", 1))) => 0;
// assert mdirs were unininlined and split
assert(lfs.mtree.root.weight == (2 << lfs.mbits));
// assert mroot now has no entries
assert(lfs.mroot.rbyd.weight == 0);
// now add another large entry to an mdir, forcing a split
memset(buffer+1, 'd', SIZE-1);
lfsr_mtree_namelookup(&lfs, 0, (const char*)buffer+1, SIZE-1,
&mdir, NULL, NULL) => LFS_ERR_NOENT;
lfsr_mdir_commit(&lfs, &mdir, LFSR_RATTRS(
LFSR_RATTR_NAME(
LFSR_TAG_REG, +1,
0, (const char*)buffer+1, SIZE-1))) => 0;
assert(mdir.rbyd.weight == 2);
// remove an entry, forcing the mdir to be dropped
memset(buffer+1, 'd', SIZE-1);
lfsr_mtree_namelookup(&lfs, 0, (const char*)buffer+1, SIZE-1,
&mdir, NULL, NULL) => 0;
// force mdir to compact while we're removing
mdir.rbyd.eoff = -1;
lfsr_mdir_commit(&lfs, &mdir, LFSR_RATTRS(
LFSR_RATTR(LFSR_TAG_RM, -1))) => 0;
assert(mdir.rbyd.weight == 1);
// assert split/drop worked out
assert(lfs.mtree.root.weight == (2 << lfs.mbits));
// assert mroot still has no entries
assert(lfs.mroot.rbyd.weight == 0);
// assert that our entries are still in the mtree
lfsr_mtree_lookup(&lfs, (0 << lfs.mbits)+1, &mdir) => 0;
assert(mdir.rbyd.weight == 2);
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_REG, NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, SIZE) => SIZE;
assert(buffer[1] == 'a');
lfsr_mtree_lookup(&lfs, (1 << lfs.mbits)+0, &mdir) => 0;
assert(mdir.rbyd.weight == 1);
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_REG, NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, SIZE) => SIZE;
assert(buffer[1] == 'b');
lfsr_mdir_lookup(&lfs, &lfs.mroot, LFSR_TAG_ATTR(1), NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, 1) => 1;
assert(buffer[0] == 'c');
// check things stay sane after remount
lfsr_unmount(&lfs) => 0;
lfsr_mount(&lfs, LFS_M_RDWR | M_FLAGS, CFG) => 0;
// assert split/drop worked out
assert(lfs.mtree.root.weight == (2 << lfs.mbits));
// assert mroot still has no entries
assert(lfs.mroot.rbyd.weight == 0);
// assert that our entries are still in the mtree
lfsr_mtree_lookup(&lfs, (0 << lfs.mbits)+1, &mdir) => 0;
assert(mdir.rbyd.weight == 2);
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_REG, NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, SIZE) => SIZE;
assert(buffer[1] == 'a');
lfsr_mtree_lookup(&lfs, (1 << lfs.mbits)+0, &mdir) => 0;
assert(mdir.rbyd.weight == 1);
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_REG, NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, SIZE) => SIZE;
assert(buffer[1] == 'b');
lfsr_mdir_lookup(&lfs, &lfs.mroot, LFSR_TAG_ATTR(1), NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, 1) => 1;
assert(buffer[0] == 'c');
lfsr_unmount(&lfs) => 0;
'''
[cases.test_mtree_drop_fuzz]
defines.N = [5, 10, 20, 40, 80, 160]
defines.FORCE_COMPACTION = [false, true]
defines.SEED = 'range(100)'
fuzz = 'SEED'
in = 'lfs.c'
code = '''
lfs_t lfs;
lfsr_format(&lfs, LFS_F_RDWR | F_FLAGS, CFG) => 0;
lfsr_mount(&lfs, LFS_M_RDWR | M_FLAGS, CFG) => 0;
lfs_alloc_ckpoint(&lfs);
bool sim[N];
for (lfs_size_t i = 0; i < N; i++) {
sim[i] = false;
}
uint32_t prng = SEED;
for (lfs_size_t i = 0; i < N; i++) {
// choose a pseudo-random name
lfs_size_t x = TEST_PRNG(&prng) % N;
char name[256];
name[0] = '\0';
sprintf(name+1, "%03x", x);
// choose to create or delete
uint8_t op = TEST_PRNG(&prng) % 2;
// create
if (op == 0) {
// update sim
sim[x] = true;
// update mtree
lfsr_mdir_t mdir;
int err = lfsr_mtree_namelookup(&lfs, 0, name+1, 3,
&mdir, NULL, NULL);
assert(!err || err == LFS_ERR_NOENT);
if (!err) {
continue;
}
// force a compaction?
if (FORCE_COMPACTION) {
lfs.mroot.rbyd.eoff = -1;
mdir.rbyd.eoff = -1;
}
lfsr_mdir_commit(&lfs, &mdir, LFSR_RATTRS(
LFSR_RATTR_NAME(LFSR_TAG_REG, +1, 0, name+1, 3))) => 0;
lfsr_data_t data;
// double check
uint8_t buffer[256];
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_REG, NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, sizeof(buffer)) => 4;
assert(memcmp(buffer, name, 4) == 0);
// delete
} else {
// update sim
sim[x] = false;
// update mtree
lfsr_mdir_t mdir;
int err = lfsr_mtree_namelookup(&lfs, 0, name+1, 3,
&mdir, NULL, NULL);
assert(!err || err == LFS_ERR_NOENT);
if (err == LFS_ERR_NOENT) {
continue;
}
// force a compaction?
if (FORCE_COMPACTION) {
lfs.mroot.rbyd.eoff = -1;
mdir.rbyd.eoff = -1;
}
lfsr_mdir_commit(&lfs, &mdir, LFSR_RATTRS(
LFSR_RATTR(LFSR_TAG_RM, -1))) => 0;
}
}
// try looking up each entry
lfsr_mdir_t mdir;
lfsr_mtree_lookup(&lfs, 0, &mdir) => 0;
lfsr_data_t data;
uint8_t buffer[256];
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_BOOKMARK, NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, sizeof(buffer)) => 1;
for (lfs_size_t i = 0; i < N; i++) {
char name[256];
name[0] = '\0';
sprintf(name+1, "%03x", i);
if (sim[i]) {
lfsr_mtree_namelookup(&lfs, 0, name+1, 3,
&mdir, NULL, NULL) => 0;
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_REG, NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, sizeof(buffer)) => 4;
assert(memcmp(buffer, name, 4) == 0);
} else {
lfsr_mtree_namelookup(&lfs, 0, name+1, 3,
&mdir, NULL, NULL) => LFS_ERR_NOENT;
}
}
// check things stay sane after remount
lfsr_unmount(&lfs) => 0;
lfsr_mount(&lfs, LFS_M_RDWR | M_FLAGS, CFG) => 0;
// try looking up each entry
lfsr_mtree_lookup(&lfs, 0, &mdir) => 0;
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_BOOKMARK, NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, sizeof(buffer)) => 1;
for (lfs_size_t i = 0; i < N; i++) {
char name[256];
name[0] = '\0';
sprintf(name+1, "%03x", i);
if (sim[i]) {
lfsr_mtree_namelookup(&lfs, 0, name+1, 3,
&mdir, NULL, NULL) => 0;
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_REG, NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, sizeof(buffer)) => 4;
assert(memcmp(buffer, name, 4) == 0);
} else {
lfsr_mtree_namelookup(&lfs, 0, name+1, 3,
&mdir, NULL, NULL) => LFS_ERR_NOENT;
}
}
lfsr_unmount(&lfs) => 0;
'''
## Relocation operations ##
# specific relocation corner cases
[cases.test_mtree_relocate]
# this should be set so only one entry can fit in a metadata block
defines.SIZE = 'BLOCK_SIZE / 4'
# make it so blocks relocate every two compacts
defines.BLOCK_RECYCLES = 0
in = 'lfs.c'
code = '''
lfs_t lfs;
lfsr_format(&lfs, LFS_F_RDWR | F_FLAGS, CFG) => 0;
lfsr_mount(&lfs, LFS_M_RDWR | M_FLAGS, CFG) => 0;
lfs_alloc_ckpoint(&lfs);
lfsr_data_t data;
// create a 2 large rattrs that needs to be uninlined
uint8_t buffer[SIZE];
memset(buffer, 'a', SIZE);
lfsr_mdir_commit(&lfs, &lfs.mroot, LFSR_RATTRS(
LFSR_RATTR_BUF(LFSR_TAG_ATTR(1), 0, buffer, SIZE))) => 0;
memset(buffer, 'b', SIZE);
lfsr_mdir_t mdir;
lfsr_mtree_lookup(&lfs, 0, &mdir) => 0;
lfsr_mdir_commit(&lfs, &mdir, LFSR_RATTRS(
LFSR_RATTR_BUF(LFSR_TAG_ATTR(2), 0, buffer, SIZE))) => 0;
// force mroot to compact
lfs.mroot.rbyd.eoff = -1;
lfsr_mdir_commit(&lfs, &lfs.mroot, LFSR_RATTRS(
LFSR_RATTR_BUF(LFSR_TAG_ATTR(3), 0, "c", 1))) => 0;
// assert mdirs were unininlined
assert(lfs.mtree.root.weight == (1 << lfs.mbits));
// assert mroot now has no entries
assert(lfs.mroot.rbyd.weight == 0);
// force mdir to compact twice, this should relocate
lfsr_mtree_lookup(&lfs, 0, &mdir) => 0;
lfsr_mdir_t old_mdir = mdir;
mdir.rbyd.eoff = -1;
lfsr_mdir_commit(&lfs, &mdir, LFSR_RATTRS(
LFSR_RATTR_BUF(LFSR_TAG_ATTR(4), 0, "d", 1))) => 0;
mdir.rbyd.eoff = -1;
lfsr_mdir_commit(&lfs, &mdir, LFSR_RATTRS(
LFSR_RATTR_BUF(LFSR_TAG_ATTR(5), 0, "e", 1))) => 0;
// assert we relocated
assert(lfsr_mdir_cmp(&old_mdir, &mdir) != 0);
// assert mdirs were unininlined
assert(lfs.mtree.root.weight == (1 << lfs.mbits));
// assert mroot now has no entries
assert(lfs.mroot.rbyd.weight == 0);
// assert that our rattrs are still in the mroot/mtree
lfsr_mdir_lookup(&lfs, &lfs.mroot, LFSR_TAG_ATTR(1), NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, SIZE) => SIZE;
assert(buffer[0] == 'a');
lfsr_mtree_lookup(&lfs, 0, &mdir) => 0;
assert(mdir.rbyd.weight == 1);
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_ATTR(2), NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, SIZE) => SIZE;
assert(buffer[0] == 'b');
lfsr_mdir_lookup(&lfs, &lfs.mroot, LFSR_TAG_ATTR(3), NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, 1) => 1;
assert(buffer[0] == 'c');
lfsr_mtree_lookup(&lfs, 0, &mdir) => 0;
assert(mdir.rbyd.weight == 1);
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_ATTR(4), NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, 1) => 1;
assert(buffer[0] == 'd');
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_ATTR(5), NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, 1) => 1;
assert(buffer[0] == 'e');
// check things stay sane after remount
lfsr_unmount(&lfs) => 0;
lfsr_mount(&lfs, LFS_M_RDWR | M_FLAGS, CFG) => 0;
// assert mdirs were unininlined
assert(lfs.mtree.root.weight == (1 << lfs.mbits));
// assert mroot now has no entries
assert(lfs.mroot.rbyd.weight == 0);
// assert that our rattrs are still in the mroot/mtree
lfsr_mdir_lookup(&lfs, &lfs.mroot, LFSR_TAG_ATTR(1), NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, SIZE) => SIZE;
assert(buffer[0] == 'a');
lfsr_mtree_lookup(&lfs, 0, &mdir) => 0;
assert(mdir.rbyd.weight == 1);
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_ATTR(2), NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, SIZE) => SIZE;
assert(buffer[0] == 'b');
lfsr_mdir_lookup(&lfs, &lfs.mroot, LFSR_TAG_ATTR(3), NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, 1) => 1;
assert(buffer[0] == 'c');
lfsr_mtree_lookup(&lfs, 0, &mdir) => 0;
assert(mdir.rbyd.weight == 1);
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_ATTR(4), NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, 1) => 1;
assert(buffer[0] == 'd');
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_ATTR(5), NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, 1) => 1;
assert(buffer[0] == 'e');
lfsr_unmount(&lfs) => 0;
'''
[cases.test_mtree_relocate_l]
# this should be set so only one entry can fit in a metadata block
defines.SIZE = 'BLOCK_SIZE / 4'
# make it so blocks relocate every two compacts
defines.BLOCK_RECYCLES = 0
in = 'lfs.c'
code = '''
lfs_t lfs;
lfsr_format(&lfs, LFS_F_RDWR | F_FLAGS, CFG) => 0;
lfsr_mount(&lfs, LFS_M_RDWR | M_FLAGS, CFG) => 0;
lfs_alloc_ckpoint(&lfs);
lfsr_data_t data;
// create 2 large entries that needs to be uninlined and split
uint8_t buffer[SIZE];
buffer[0] = '\0';
memset(buffer+1, 'a', SIZE-1);
lfsr_mdir_t mdir;
lfsr_mtree_namelookup(&lfs, 0, (const char*)buffer+1, SIZE-1,
&mdir, NULL, NULL) => LFS_ERR_NOENT;
lfsr_mdir_commit(&lfs, &mdir, LFSR_RATTRS(
LFSR_RATTR_NAME(
LFSR_TAG_REG, +1,
0, (const char*)buffer+1, SIZE-1))) => 0;
assert(mdir.rbyd.weight == 2);
memset(buffer+1, 'b', SIZE-1);
lfsr_mtree_namelookup(&lfs, 0, (const char*)buffer+1, SIZE-1,
&mdir, NULL, NULL) => LFS_ERR_NOENT;
lfsr_mdir_commit(&lfs, &mdir, LFSR_RATTRS(
LFSR_RATTR_NAME(
LFSR_TAG_REG, +1,
0, (const char*)buffer+1, SIZE-1))) => 0;
assert(mdir.rbyd.weight == 3);
// force mroot to compact
lfs.mroot.rbyd.eoff = -1;
lfsr_mdir_commit(&lfs, &lfs.mroot, LFSR_RATTRS(
LFSR_RATTR_BUF(LFSR_TAG_ATTR(1), 0, "c", 1))) => 0;
// assert mdirs were unininlined and split
assert(lfs.mtree.root.weight == (2 << lfs.mbits));
// assert mroot now has no entries
assert(lfs.mroot.rbyd.weight == 0);
// force mdir to compact twice, this should relocate
memset(buffer+1, 'a', SIZE-1);
lfsr_mtree_namelookup(&lfs, 0, (const char*)buffer+1, SIZE-1,
&mdir, NULL, NULL) => 0;
lfsr_mdir_t old_mdir = mdir;
mdir.rbyd.eoff = -1;
lfsr_mdir_commit(&lfs, &mdir, LFSR_RATTRS(
LFSR_RATTR_BUF(LFSR_TAG_ATTR(2), 0, "d", 1))) => 0;
mdir.rbyd.eoff = -1;
lfsr_mdir_commit(&lfs, &mdir, LFSR_RATTRS(
LFSR_RATTR_BUF(LFSR_TAG_ATTR(3), 0, "e", 1))) => 0;
// assert we relocated
assert(lfsr_mdir_cmp(&old_mdir, &mdir) != 0);
// assert mdirs were unininlined and split
assert(lfs.mtree.root.weight == (2 << lfs.mbits));
// assert mroot now has no entries
assert(lfs.mroot.rbyd.weight == 0);
// assert that our entries are still in the mtree
lfsr_mtree_lookup(&lfs, (0 << lfs.mbits)+1, &mdir) => 0;
assert(mdir.rbyd.weight == 2);
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_REG, NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, SIZE) => SIZE;
assert(buffer[1] == 'a');
lfsr_mtree_lookup(&lfs, (1 << lfs.mbits)+0, &mdir) => 0;
assert(mdir.rbyd.weight == 1);
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_REG, NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, SIZE) => SIZE;
assert(buffer[1] == 'b');
lfsr_mdir_lookup(&lfs, &lfs.mroot, LFSR_TAG_ATTR(1), NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, 1) => 1;
assert(buffer[0] == 'c');
lfsr_mtree_lookup(&lfs, (0 << lfs.mbits)+1, &mdir) => 0;
assert(mdir.rbyd.weight == 2);
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_ATTR(2), NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, 1) => 1;
assert(buffer[0] == 'd');
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_ATTR(3), NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, 1) => 1;
assert(buffer[0] == 'e');
// check things stay sane after remount
lfsr_unmount(&lfs) => 0;
lfsr_mount(&lfs, LFS_M_RDWR | M_FLAGS, CFG) => 0;
// assert mdirs were unininlined and split
assert(lfs.mtree.root.weight == (2 << lfs.mbits));
// assert mroot now has no entries
assert(lfs.mroot.rbyd.weight == 0);
// assert that our entries are still in the mtree
lfsr_mtree_lookup(&lfs, (0 << lfs.mbits)+1, &mdir) => 0;
assert(mdir.rbyd.weight == 2);
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_REG, NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, SIZE) => SIZE;
assert(buffer[1] == 'a');
lfsr_mtree_lookup(&lfs, (1 << lfs.mbits)+0, &mdir) => 0;
assert(mdir.rbyd.weight == 1);
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_REG, NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, SIZE) => SIZE;
assert(buffer[1] == 'b');
lfsr_mdir_lookup(&lfs, &lfs.mroot, LFSR_TAG_ATTR(1), NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, 1) => 1;
assert(buffer[0] == 'c');
lfsr_mtree_lookup(&lfs, (0 << lfs.mbits)+1, &mdir) => 0;
assert(mdir.rbyd.weight == 2);
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_ATTR(2), NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, 1) => 1;
assert(buffer[0] == 'd');
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_ATTR(3), NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, 1) => 1;
assert(buffer[0] == 'e');
lfsr_unmount(&lfs) => 0;
'''
[cases.test_mtree_relocate_r]
# this should be set so only one entry can fit in a metadata block
defines.SIZE = 'BLOCK_SIZE / 4'
# make it so blocks relocate every two compacts
defines.BLOCK_RECYCLES = 0
in = 'lfs.c'
code = '''
lfs_t lfs;
lfsr_format(&lfs, LFS_F_RDWR | F_FLAGS, CFG) => 0;
lfsr_mount(&lfs, LFS_M_RDWR | M_FLAGS, CFG) => 0;
lfs_alloc_ckpoint(&lfs);
lfsr_data_t data;
// create 2 large entries that needs to be uninlined and split
uint8_t buffer[SIZE];
buffer[0] = '\0';
memset(buffer+1, 'a', SIZE-1);
lfsr_mdir_t mdir;
lfsr_mtree_namelookup(&lfs, 0, (const char*)buffer+1, SIZE-1,
&mdir, NULL, NULL) => LFS_ERR_NOENT;
lfsr_mdir_commit(&lfs, &mdir, LFSR_RATTRS(
LFSR_RATTR_NAME(
LFSR_TAG_REG, +1,
0, (const char*)buffer+1, SIZE-1))) => 0;
assert(mdir.rbyd.weight == 2);
memset(buffer+1, 'b', SIZE-1);
lfsr_mtree_namelookup(&lfs, 0, (const char*)buffer+1, SIZE-1,
&mdir, NULL, NULL) => LFS_ERR_NOENT;
lfsr_mdir_commit(&lfs, &mdir, LFSR_RATTRS(
LFSR_RATTR_NAME(
LFSR_TAG_REG, +1,
0, (const char*)buffer+1, SIZE-1))) => 0;
assert(mdir.rbyd.weight == 3);
// force mroot to compact
lfs.mroot.rbyd.eoff = -1;
lfsr_mdir_commit(&lfs, &lfs.mroot, LFSR_RATTRS(
LFSR_RATTR_BUF(LFSR_TAG_ATTR(1), 0, "c", 1))) => 0;
// assert mdirs were unininlined and split
assert(lfs.mtree.root.weight == (2 << lfs.mbits));
// assert mroot now has no entries
assert(lfs.mroot.rbyd.weight == 0);
// force mdir to compact twice, this should relocate
memset(buffer+1, 'b', SIZE-1);
lfsr_mtree_namelookup(&lfs, 0, (const char*)buffer+1, SIZE-1,
&mdir, NULL, NULL) => 0;
lfsr_mdir_t old_mdir = mdir;
mdir.rbyd.eoff = -1;
lfsr_mdir_commit(&lfs, &mdir, LFSR_RATTRS(
LFSR_RATTR_BUF(LFSR_TAG_ATTR(2), 0, "d", 1))) => 0;
mdir.rbyd.eoff = -1;
lfsr_mdir_commit(&lfs, &mdir, LFSR_RATTRS(
LFSR_RATTR_BUF(LFSR_TAG_ATTR(3), 0, "e", 1))) => 0;
// assert we relocated
assert(lfsr_mdir_cmp(&old_mdir, &mdir) != 0);
// assert mdirs were unininlined and split
assert(lfs.mtree.root.weight == (2 << lfs.mbits));
// assert mroot now has no entries
assert(lfs.mroot.rbyd.weight == 0);
// assert that our entries are still in the mtree
lfsr_mtree_lookup(&lfs, (0 << lfs.mbits)+1, &mdir) => 0;
assert(mdir.rbyd.weight == 2);
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_REG, NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, SIZE) => SIZE;
assert(buffer[1] == 'a');
lfsr_mtree_lookup(&lfs, (1 << lfs.mbits)+0, &mdir) => 0;
assert(mdir.rbyd.weight == 1);
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_REG, NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, SIZE) => SIZE;
assert(buffer[1] == 'b');
lfsr_mdir_lookup(&lfs, &lfs.mroot, LFSR_TAG_ATTR(1), NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, 1) => 1;
assert(buffer[0] == 'c');
lfsr_mtree_lookup(&lfs, (1 << lfs.mbits)+0, &mdir) => 0;
assert(mdir.rbyd.weight == 1);
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_ATTR(2), NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, 1) => 1;
assert(buffer[0] == 'd');
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_ATTR(3), NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, 1) => 1;
assert(buffer[0] == 'e');
// check things stay sane after remount
lfsr_unmount(&lfs) => 0;
lfsr_mount(&lfs, LFS_M_RDWR | M_FLAGS, CFG) => 0;
// assert mdirs were unininlined and split
assert(lfs.mtree.root.weight == (2 << lfs.mbits));
// assert mroot now has no entries
assert(lfs.mroot.rbyd.weight == 0);
// assert that our entries are still in the mtree
lfsr_mtree_lookup(&lfs, (0 << lfs.mbits)+1, &mdir) => 0;
assert(mdir.rbyd.weight == 2);
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_REG, NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, SIZE) => SIZE;
assert(buffer[1] == 'a');
lfsr_mtree_lookup(&lfs, (1 << lfs.mbits)+0, &mdir) => 0;
assert(mdir.rbyd.weight == 1);
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_REG, NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, SIZE) => SIZE;
assert(buffer[1] == 'b');
lfsr_mdir_lookup(&lfs, &lfs.mroot, LFSR_TAG_ATTR(1), NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, 1) => 1;
assert(buffer[0] == 'c');
lfsr_mtree_lookup(&lfs, (1 << lfs.mbits)+0, &mdir) => 0;
assert(mdir.rbyd.weight == 1);
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_ATTR(2), NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, 1) => 1;
assert(buffer[0] == 'd');
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_ATTR(3), NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, 1) => 1;
assert(buffer[0] == 'e');
lfsr_unmount(&lfs) => 0;
'''
[cases.test_mtree_extend]
# this should be set so only one entry can fit in a metadata block
defines.SIZE = 'BLOCK_SIZE / 4'
# make it so blocks relocate every two compacts
defines.BLOCK_RECYCLES = 0
in = 'lfs.c'
code = '''
lfs_t lfs;
lfsr_format(&lfs, LFS_F_RDWR | F_FLAGS, CFG) => 0;
lfsr_mount(&lfs, LFS_M_RDWR | M_FLAGS, CFG) => 0;
lfs_alloc_ckpoint(&lfs);
lfsr_data_t data;
// prepare mroot with an entry
uint8_t buffer[SIZE];
buffer[0] = '\0';
memset(buffer+1, 'a', SIZE-1);
lfsr_mdir_t mdir;
lfsr_mtree_namelookup(&lfs, 0, (const char*)buffer+1, SIZE-1,
&mdir, NULL, NULL) => LFS_ERR_NOENT;
lfsr_mdir_commit(&lfs, &mdir, LFSR_RATTRS(
LFSR_RATTR_NAME(
LFSR_TAG_REG, +1,
0, (const char*)buffer+1, SIZE-1))) => 0;
assert(mdir.rbyd.weight == 2);
// force mroot to compact twice, this should extend the mroot
lfsr_mdir_t old_mroot = lfs.mroot;
lfs.mroot.rbyd.eoff = -1;
lfsr_mdir_commit(&lfs, &lfs.mroot, LFSR_RATTRS(
LFSR_RATTR_BUF(LFSR_TAG_ATTR(1), 0, "b", 1))) => 0;
lfs.mroot.rbyd.eoff = -1;
lfsr_mdir_commit(&lfs, &lfs.mroot, LFSR_RATTRS(
LFSR_RATTR_BUF(LFSR_TAG_ATTR(2), 0, "c", 1))) => 0;
// assert we relocated
assert(lfsr_mdir_cmp(&old_mroot, &lfs.mroot) != 0);
// assert that our entry is still in the mroot
lfsr_mtree_lookup(&lfs, (0 << lfs.mbits)+1, &mdir) => 0;
assert(mdir.rbyd.weight == 2);
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_REG, NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, SIZE) => SIZE;
assert(buffer[1] == 'a');
lfsr_mdir_lookup(&lfs, &lfs.mroot, LFSR_TAG_ATTR(1), NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, 1) => 1;
assert(buffer[0] == 'b');
lfsr_mdir_lookup(&lfs, &lfs.mroot, LFSR_TAG_ATTR(2), NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, 1) => 1;
assert(buffer[0] == 'c');
// check things stay sane after remount
lfsr_unmount(&lfs) => 0;
lfsr_mount(&lfs, LFS_M_RDWR | M_FLAGS, CFG) => 0;
// assert that our rattr is still in the mroot
lfsr_mtree_lookup(&lfs, (0 << lfs.mbits)+1, &mdir) => 0;
assert(mdir.rbyd.weight == 2);
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_REG, NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, SIZE) => SIZE;
assert(buffer[1] == 'a');
lfsr_mdir_lookup(&lfs, &lfs.mroot, LFSR_TAG_ATTR(1), NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, 1) => 1;
assert(buffer[0] == 'b');
lfsr_mdir_lookup(&lfs, &lfs.mroot, LFSR_TAG_ATTR(2), NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, 1) => 1;
assert(buffer[0] == 'c');
lfsr_unmount(&lfs) => 0;
'''
[cases.test_mtree_extend_twice]
# this should be set so only one entry can fit in a metadata block
defines.SIZE = 'BLOCK_SIZE / 4'
# make it so blocks relocate every two compacts
defines.BLOCK_RECYCLES = 0
# force our block to compact by setting prog_size=block_size, we don't have
# an easy way to force the intermediary mroots to compact otherwise
defines.PROG_SIZE = 'BLOCK_SIZE'
in = 'lfs.c'
code = '''
lfs_t lfs;
lfsr_format(&lfs, LFS_F_RDWR | F_FLAGS, CFG) => 0;
lfsr_mount(&lfs, LFS_M_RDWR | M_FLAGS, CFG) => 0;
lfs_alloc_ckpoint(&lfs);
lfsr_data_t data;
// prepare mroot with an entry
uint8_t buffer[SIZE];
buffer[0] = '\0';
memset(buffer+1, 'a', SIZE-1);
lfsr_mdir_t mdir;
lfsr_mtree_namelookup(&lfs, 0, (const char*)buffer+1, SIZE-1,
&mdir, NULL, NULL) => LFS_ERR_NOENT;
lfsr_mdir_commit(&lfs, &mdir, LFSR_RATTRS(
LFSR_RATTR_NAME(
LFSR_TAG_REG, +1,
0, (const char*)buffer+1, SIZE-1))) => 0;
assert(mdir.rbyd.weight == 2);
// force mroot to compact twice, this should extend the mroot
lfsr_mdir_t old_mroot = lfs.mroot;
lfs.mroot.rbyd.eoff = -1;
lfsr_mdir_commit(&lfs, &lfs.mroot, LFSR_RATTRS(
LFSR_RATTR_BUF(LFSR_TAG_ATTR(1), 0, "b", 1))) => 0;
lfs.mroot.rbyd.eoff = -1;
lfsr_mdir_commit(&lfs, &lfs.mroot, LFSR_RATTRS(
LFSR_RATTR_BUF(LFSR_TAG_ATTR(2), 0, "c", 1))) => 0;
// assert we relocated
assert(lfsr_mdir_cmp(&old_mroot, &lfs.mroot) != 0);
// force mroot to compact four times, this should relocate the mroot
// twice, forcing a second mroot extension
old_mroot = lfs.mroot;
lfs.mroot.rbyd.eoff = -1;
lfsr_mdir_commit(&lfs, &lfs.mroot, LFSR_RATTRS(
LFSR_RATTR_BUF(LFSR_TAG_ATTR(3), 0, "d", 1))) => 0;
lfs.mroot.rbyd.eoff = -1;
lfsr_mdir_commit(&lfs, &lfs.mroot, LFSR_RATTRS(
LFSR_RATTR_BUF(LFSR_TAG_ATTR(4), 0, "e", 1))) => 0;
lfs.mroot.rbyd.eoff = -1;
lfsr_mdir_commit(&lfs, &lfs.mroot, LFSR_RATTRS(
LFSR_RATTR_BUF(LFSR_TAG_ATTR(5), 0, "f", 1))) => 0;
lfs.mroot.rbyd.eoff = -1;
lfsr_mdir_commit(&lfs, &lfs.mroot, LFSR_RATTRS(
LFSR_RATTR_BUF(LFSR_TAG_ATTR(6), 0, "g", 1))) => 0;
// assert we relocated
assert(lfsr_mdir_cmp(&old_mroot, &lfs.mroot) != 0);
// assert that our rattr is still in the mroot
lfsr_mtree_lookup(&lfs, (0 << lfs.mbits)+1, &mdir) => 0;
assert(mdir.rbyd.weight == 2);
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_REG, NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, SIZE) => SIZE;
assert(buffer[1] == 'a');
lfsr_mdir_lookup(&lfs, &lfs.mroot, LFSR_TAG_ATTR(1), NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, 1) => 1;
assert(buffer[0] == 'b');
lfsr_mdir_lookup(&lfs, &lfs.mroot, LFSR_TAG_ATTR(2), NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, 1) => 1;
assert(buffer[0] == 'c');
lfsr_mdir_lookup(&lfs, &lfs.mroot, LFSR_TAG_ATTR(3), NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, 1) => 1;
assert(buffer[0] == 'd');
lfsr_mdir_lookup(&lfs, &lfs.mroot, LFSR_TAG_ATTR(4), NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, 1) => 1;
assert(buffer[0] == 'e');
lfsr_mdir_lookup(&lfs, &lfs.mroot, LFSR_TAG_ATTR(5), NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, 1) => 1;
assert(buffer[0] == 'f');
lfsr_mdir_lookup(&lfs, &lfs.mroot, LFSR_TAG_ATTR(6), NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, 1) => 1;
assert(buffer[0] == 'g');
// check things stay sane after remount
lfsr_unmount(&lfs) => 0;
lfsr_mount(&lfs, LFS_M_RDWR | M_FLAGS, CFG) => 0;
// assert that our rattr is still in the mroot
lfsr_mtree_lookup(&lfs, (0 << lfs.mbits)+1, &mdir) => 0;
assert(mdir.rbyd.weight == 2);
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_REG, NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, SIZE) => SIZE;
assert(buffer[1] == 'a');
lfsr_mdir_lookup(&lfs, &lfs.mroot, LFSR_TAG_ATTR(1), NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, 1) => 1;
assert(buffer[0] == 'b');
lfsr_mdir_lookup(&lfs, &lfs.mroot, LFSR_TAG_ATTR(2), NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, 1) => 1;
assert(buffer[0] == 'c');
lfsr_mdir_lookup(&lfs, &lfs.mroot, LFSR_TAG_ATTR(3), NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, 1) => 1;
assert(buffer[0] == 'd');
lfsr_mdir_lookup(&lfs, &lfs.mroot, LFSR_TAG_ATTR(4), NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, 1) => 1;
assert(buffer[0] == 'e');
lfsr_mdir_lookup(&lfs, &lfs.mroot, LFSR_TAG_ATTR(5), NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, 1) => 1;
assert(buffer[0] == 'f');
lfsr_mdir_lookup(&lfs, &lfs.mroot, LFSR_TAG_ATTR(6), NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, 1) => 1;
assert(buffer[0] == 'g');
lfsr_unmount(&lfs) => 0;
'''
[cases.test_mtree_relocate_mroot]
# this should be set so only one entry can fit in a metadata block
defines.SIZE = 'BLOCK_SIZE / 4'
# make it so blocks relocate every two compacts
defines.BLOCK_RECYCLES = 0
in = 'lfs.c'
code = '''
lfs_t lfs;
lfsr_format(&lfs, LFS_F_RDWR | F_FLAGS, CFG) => 0;
lfsr_mount(&lfs, LFS_M_RDWR | M_FLAGS, CFG) => 0;
lfs_alloc_ckpoint(&lfs);
lfsr_data_t data;
// prepare mroot with an entry
uint8_t buffer[SIZE];
buffer[0] = '\0';
memset(buffer+1, 'a', SIZE-1);
lfsr_mdir_t mdir;
lfsr_mtree_namelookup(&lfs, 0, (const char*)buffer+1, SIZE-1,
&mdir, NULL, NULL) => LFS_ERR_NOENT;
lfsr_mdir_commit(&lfs, &mdir, LFSR_RATTRS(
LFSR_RATTR_NAME(
LFSR_TAG_REG, +1,
0, (const char*)buffer+1, SIZE-1))) => 0;
assert(mdir.rbyd.weight == 2);
// force mroot to compact twice, this should extend the mroot
lfsr_mdir_t old_mroot = lfs.mroot;
lfs.mroot.rbyd.eoff = -1;
lfsr_mdir_commit(&lfs, &lfs.mroot, LFSR_RATTRS(
LFSR_RATTR_BUF(LFSR_TAG_ATTR(1), 0, "b", 1))) => 0;
lfs.mroot.rbyd.eoff = -1;
lfsr_mdir_commit(&lfs, &lfs.mroot, LFSR_RATTRS(
LFSR_RATTR_BUF(LFSR_TAG_ATTR(2), 0, "c", 1))) => 0;
// assert we relocated
assert(lfsr_mdir_cmp(&old_mroot, &lfs.mroot) != 0);
// force mroot to compact twice again, this should relocate the mroot
old_mroot = lfs.mroot;
lfs.mroot.rbyd.eoff = -1;
lfsr_mdir_commit(&lfs, &lfs.mroot, LFSR_RATTRS(
LFSR_RATTR_BUF(LFSR_TAG_ATTR(3), 0, "d", 1))) => 0;
lfs.mroot.rbyd.eoff = -1;
lfsr_mdir_commit(&lfs, &lfs.mroot, LFSR_RATTRS(
LFSR_RATTR_BUF(LFSR_TAG_ATTR(4), 0, "e", 1))) => 0;
// assert we relocated
assert(lfsr_mdir_cmp(&old_mroot, &lfs.mroot) != 0);
// assert that our entry is still in the mroot
lfsr_mtree_lookup(&lfs, (0 << lfs.mbits)+1, &mdir) => 0;
assert(mdir.rbyd.weight == 2);
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_REG, NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, SIZE) => SIZE;
assert(buffer[1] == 'a');
lfsr_mdir_lookup(&lfs, &lfs.mroot, LFSR_TAG_ATTR(1), NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, 1) => 1;
assert(buffer[0] == 'b');
lfsr_mdir_lookup(&lfs, &lfs.mroot, LFSR_TAG_ATTR(2), NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, 1) => 1;
assert(buffer[0] == 'c');
lfsr_mdir_lookup(&lfs, &lfs.mroot, LFSR_TAG_ATTR(3), NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, 1) => 1;
assert(buffer[0] == 'd');
lfsr_mdir_lookup(&lfs, &lfs.mroot, LFSR_TAG_ATTR(4), NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, 1) => 1;
assert(buffer[0] == 'e');
// check things stay sane after remount
lfsr_unmount(&lfs) => 0;
lfsr_mount(&lfs, LFS_M_RDWR | M_FLAGS, CFG) => 0;
// assert that our rattr is still in the mroot
lfsr_mtree_lookup(&lfs, (0 << lfs.mbits)+1, &mdir) => 0;
assert(mdir.rbyd.weight == 2);
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_REG, NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, SIZE) => SIZE;
assert(buffer[1] == 'a');
lfsr_mdir_lookup(&lfs, &lfs.mroot, LFSR_TAG_ATTR(1), NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, 1) => 1;
assert(buffer[0] == 'b');
lfsr_mdir_lookup(&lfs, &lfs.mroot, LFSR_TAG_ATTR(2), NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, 1) => 1;
assert(buffer[0] == 'c');
lfsr_mdir_lookup(&lfs, &lfs.mroot, LFSR_TAG_ATTR(3), NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, 1) => 1;
assert(buffer[0] == 'd');
lfsr_mdir_lookup(&lfs, &lfs.mroot, LFSR_TAG_ATTR(4), NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, 1) => 1;
assert(buffer[0] == 'e');
lfsr_unmount(&lfs) => 0;
'''
[cases.test_mtree_relocate_extend]
# this should be set so only one entry can fit in a metadata block
defines.SIZE = 'BLOCK_SIZE / 4'
# make it so blocks relocate every two compacts
defines.BLOCK_RECYCLES = 0
in = 'lfs.c'
code = '''
lfs_t lfs;
lfsr_format(&lfs, LFS_F_RDWR | F_FLAGS, CFG) => 0;
lfsr_mount(&lfs, LFS_M_RDWR | M_FLAGS, CFG) => 0;
lfs_alloc_ckpoint(&lfs);
lfsr_data_t data;
// create 2 large entries that needs to be uninlined and split
uint8_t buffer[SIZE];
buffer[0] = '\0';
memset(buffer+1, 'a', SIZE-1);
lfsr_mdir_t mdir;
lfsr_mtree_namelookup(&lfs, 0, (const char*)buffer+1, SIZE-1,
&mdir, NULL, NULL) => LFS_ERR_NOENT;
lfsr_mdir_commit(&lfs, &mdir, LFSR_RATTRS(
LFSR_RATTR_NAME(
LFSR_TAG_REG, +1,
0, (const char*)buffer+1, SIZE-1))) => 0;
assert(mdir.rbyd.weight == 2);
memset(buffer+1, 'b', SIZE-1);
lfsr_mtree_namelookup(&lfs, 0, (const char*)buffer+1, SIZE-1,
&mdir, NULL, NULL) => LFS_ERR_NOENT;
lfsr_mdir_commit(&lfs, &mdir, LFSR_RATTRS(
LFSR_RATTR_NAME(
LFSR_TAG_REG, +1,
0, (const char*)buffer+1, SIZE-1))) => 0;
assert(mdir.rbyd.weight == 3);
// force mroot to compact
lfs.mroot.rbyd.eoff = -1;
lfsr_mdir_commit(&lfs, &lfs.mroot, LFSR_RATTRS(
LFSR_RATTR_BUF(LFSR_TAG_ATTR(1), 0, "c", 1))) => 0;
// assert mdirs were unininlined and split
assert(lfs.mtree.root.weight == (2 << lfs.mbits));
// assert mroot now has no entries
assert(lfs.mroot.rbyd.weight == 0);
// setup mroot to compact and relocate on next commit
lfs.mroot.rbyd.eoff = -1;
lfsr_mdir_t old_mroot = lfs.mroot;
// force mdir to compact twice, this should relocate
memset(buffer+1, 'b', SIZE-1);
lfsr_mtree_namelookup(&lfs, 0, (const char*)buffer+1, SIZE-1,
&mdir, NULL, NULL) => 0;
lfsr_mdir_t old_mdir = mdir;
mdir.rbyd.eoff = -1;
lfsr_mdir_commit(&lfs, &mdir, LFSR_RATTRS(
LFSR_RATTR_BUF(LFSR_TAG_ATTR(2), 0, "d", 1))) => 0;
mdir.rbyd.eoff = -1;
lfsr_mdir_commit(&lfs, &mdir, LFSR_RATTRS(
LFSR_RATTR_BUF(LFSR_TAG_ATTR(3), 0, "e", 1))) => 0;
// assert we relocated
assert(lfsr_mdir_cmp(&old_mdir, &mdir) != 0);
// assert mroot relocated
assert(lfsr_mdir_cmp(&old_mroot, &lfs.mroot) != 0);
// assert mdirs were unininlined and split
assert(lfs.mtree.root.weight == (2 << lfs.mbits));
// assert mroot now has no entries
assert(lfs.mroot.rbyd.weight == 0);
// assert that our entries are still in the mtree
lfsr_mtree_lookup(&lfs, (0 << lfs.mbits)+1, &mdir) => 0;
assert(mdir.rbyd.weight == 2);
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_REG, NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, SIZE) => SIZE;
assert(buffer[1] == 'a');
lfsr_mtree_lookup(&lfs, (1 << lfs.mbits)+0, &mdir) => 0;
assert(mdir.rbyd.weight == 1);
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_REG, NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, SIZE) => SIZE;
assert(buffer[1] == 'b');
lfsr_mdir_lookup(&lfs, &lfs.mroot, LFSR_TAG_ATTR(1), NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, 1) => 1;
assert(buffer[0] == 'c');
lfsr_mtree_lookup(&lfs, (1 << lfs.mbits)+0, &mdir) => 0;
assert(mdir.rbyd.weight == 1);
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_ATTR(2), NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, 1) => 1;
assert(buffer[0] == 'd');
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_ATTR(3), NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, 1) => 1;
assert(buffer[0] == 'e');
// check things stay sane after remount
lfsr_unmount(&lfs) => 0;
lfsr_mount(&lfs, LFS_M_RDWR | M_FLAGS, CFG) => 0;
// assert mdirs were unininlined and split
assert(lfs.mtree.root.weight == (2 << lfs.mbits));
// assert mroot now has no entries
assert(lfs.mroot.rbyd.weight == 0);
// assert that our entries are still in the mtree
lfsr_mtree_lookup(&lfs, (0 << lfs.mbits)+1, &mdir) => 0;
assert(mdir.rbyd.weight == 2);
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_REG, NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, SIZE) => SIZE;
assert(buffer[1] == 'a');
lfsr_mtree_lookup(&lfs, (1 << lfs.mbits)+0, &mdir) => 0;
assert(mdir.rbyd.weight == 1);
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_REG, NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, SIZE) => SIZE;
assert(buffer[1] == 'b');
lfsr_mdir_lookup(&lfs, &lfs.mroot, LFSR_TAG_ATTR(1), NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, 1) => 1;
assert(buffer[0] == 'c');
lfsr_mtree_lookup(&lfs, (1 << lfs.mbits)+0, &mdir) => 0;
assert(mdir.rbyd.weight == 1);
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_ATTR(2), NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, 1) => 1;
assert(buffer[0] == 'd');
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_ATTR(3), NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, 1) => 1;
assert(buffer[0] == 'e');
lfsr_unmount(&lfs) => 0;
'''
[cases.test_mtree_split_extend]
# this should be set so only one entry can fit in a metadata block
defines.SIZE = 'BLOCK_SIZE / 4'
# make it so blocks relocate every two compacts
defines.BLOCK_RECYCLES = 0
in = 'lfs.c'
code = '''
lfs_t lfs;
lfsr_format(&lfs, LFS_F_RDWR | F_FLAGS, CFG) => 0;
lfsr_mount(&lfs, LFS_M_RDWR | M_FLAGS, CFG) => 0;
lfs_alloc_ckpoint(&lfs);
lfsr_data_t data;
// create 2 large entries that needs to be uninlined and split
uint8_t buffer[SIZE];
buffer[0] = '\0';
memset(buffer+1, 'a', SIZE-1);
lfsr_mdir_t mdir;
lfsr_mtree_namelookup(&lfs, 0, (const char*)buffer+1, SIZE-1,
&mdir, NULL, NULL) => LFS_ERR_NOENT;
lfsr_mdir_commit(&lfs, &mdir, LFSR_RATTRS(
LFSR_RATTR_NAME(
LFSR_TAG_REG, +1,
0, (const char*)buffer+1, SIZE-1))) => 0;
assert(mdir.rbyd.weight == 2);
memset(buffer+1, 'b', SIZE-1);
lfsr_mtree_namelookup(&lfs, 0, (const char*)buffer+1, SIZE-1,
&mdir, NULL, NULL) => LFS_ERR_NOENT;
lfsr_mdir_commit(&lfs, &mdir, LFSR_RATTRS(
LFSR_RATTR_NAME(
LFSR_TAG_REG, +1,
0, (const char*)buffer+1, SIZE-1))) => 0;
assert(mdir.rbyd.weight == 3);
// force mroot to compact
lfs.mroot.rbyd.eoff = -1;
lfsr_mdir_commit(&lfs, &lfs.mroot, LFSR_RATTRS(
LFSR_RATTR_BUF(LFSR_TAG_ATTR(1), 0, "c", 1))) => 0;
// assert mdirs were unininlined and split
assert(lfs.mtree.root.weight == (2 << lfs.mbits));
// assert mroot now has no entries
assert(lfs.mroot.rbyd.weight == 0);
// now add another large entry to an mdir, forcing a split
memset(buffer+1, 'd', SIZE-1);
lfsr_mtree_namelookup(&lfs, 0, (const char*)buffer+1, SIZE-1,
&mdir, NULL, NULL) => LFS_ERR_NOENT;
lfsr_mdir_commit(&lfs, &mdir, LFSR_RATTRS(
LFSR_RATTR_NAME(
LFSR_TAG_REG, +1,
0, (const char*)buffer+1, SIZE-1))) => 0;
assert(mdir.rbyd.weight == 2);
// setup mroot to compact and relocate on next commit
lfs.mroot.rbyd.eoff = -1;
lfsr_mdir_t old_mroot = lfs.mroot;
// force mdir to compact twice, this should relocate
lfsr_mdir_t old_mdir = mdir;
mdir.rbyd.eoff = -1;
lfsr_mdir_commit(&lfs, &mdir, LFSR_RATTRS(
LFSR_RATTR_BUF(LFSR_TAG_ATTR(2), 0, "e", 1))) => 0;
mdir.rbyd.eoff = -1;
lfsr_mdir_commit(&lfs, &mdir, LFSR_RATTRS(
LFSR_RATTR_BUF(LFSR_TAG_ATTR(3), 0, "f", 1))) => 0;
// assert we relocated
assert(lfsr_mdir_cmp(&old_mdir, &mdir) != 0);
// assert mroot relocated
assert(lfsr_mdir_cmp(&old_mroot, &lfs.mroot) != 0);
// assert mdir was split correctly
assert(lfs.mtree.root.weight == (3 << lfs.mbits));
// assert mroot still has no entries
assert(lfs.mroot.rbyd.weight == 0);
// assert that our entries are still in the mtree
lfsr_mtree_lookup(&lfs, (0 << lfs.mbits)+1, &mdir) => 0;
assert(mdir.rbyd.weight == 2);
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_REG, NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, SIZE) => SIZE;
assert(buffer[1] == 'a');
lfsr_mtree_lookup(&lfs, (1 << lfs.mbits)+0, &mdir) => 0;
assert(mdir.rbyd.weight == 1);
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_REG, NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, SIZE) => SIZE;
assert(buffer[1] == 'b');
lfsr_mdir_lookup(&lfs, &lfs.mroot, LFSR_TAG_ATTR(1), NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, 1) => 1;
assert(buffer[0] == 'c');
lfsr_mtree_lookup(&lfs, (2 << lfs.mbits)+0, &mdir) => 0;
assert(mdir.rbyd.weight == 1);
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_REG, NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, SIZE) => SIZE;
assert(buffer[1] == 'd');
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_ATTR(2), NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, 1) => 1;
assert(buffer[0] == 'e');
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_ATTR(3), NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, 1) => 1;
assert(buffer[0] == 'f');
// check things stay sane after remount
lfsr_unmount(&lfs) => 0;
lfsr_mount(&lfs, LFS_M_RDWR | M_FLAGS, CFG) => 0;
// assert mdir was split correctly
assert(lfs.mtree.root.weight == (3 << lfs.mbits));
// assert mroot still has no entries
assert(lfs.mroot.rbyd.weight == 0);
// assert that our entries are still in the mtree
lfsr_mtree_lookup(&lfs, (0 << lfs.mbits)+1, &mdir) => 0;
assert(mdir.rbyd.weight == 2);
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_REG, NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, SIZE) => SIZE;
assert(buffer[1] == 'a');
lfsr_mtree_lookup(&lfs, (1 << lfs.mbits)+0, &mdir) => 0;
assert(mdir.rbyd.weight == 1);
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_REG, NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, SIZE) => SIZE;
assert(buffer[1] == 'b');
lfsr_mdir_lookup(&lfs, &lfs.mroot, LFSR_TAG_ATTR(1), NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, 1) => 1;
assert(buffer[0] == 'c');
lfsr_mtree_lookup(&lfs, (2 << lfs.mbits)+0, &mdir) => 0;
assert(mdir.rbyd.weight == 1);
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_REG, NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, SIZE) => SIZE;
assert(buffer[1] == 'd');
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_ATTR(2), NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, 1) => 1;
assert(buffer[0] == 'e');
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_ATTR(3), NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, 1) => 1;
assert(buffer[0] == 'f');
lfsr_unmount(&lfs) => 0;
'''
[cases.test_mtree_drop_extend]
# this should be set so only one entry can fit in a metadata block
defines.SIZE = 'BLOCK_SIZE / 4'
# make it so blocks relocate every two compacts
defines.BLOCK_RECYCLES = 0
in = 'lfs.c'
code = '''
lfs_t lfs;
lfsr_format(&lfs, LFS_F_RDWR | F_FLAGS, CFG) => 0;
lfsr_mount(&lfs, LFS_M_RDWR | M_FLAGS, CFG) => 0;
lfs_alloc_ckpoint(&lfs);
lfsr_data_t data;
// create 2 large entries that needs to be uninlined and split
uint8_t buffer[SIZE];
buffer[0] = '\0';
memset(buffer+1, 'a', SIZE-1);
lfsr_mdir_t mdir;
lfsr_mtree_namelookup(&lfs, 0, (const char*)buffer+1, SIZE-1,
&mdir, NULL, NULL) => LFS_ERR_NOENT;
lfsr_mdir_commit(&lfs, &mdir, LFSR_RATTRS(
LFSR_RATTR_NAME(
LFSR_TAG_REG, +1,
0, (const char*)buffer+1, SIZE-1))) => 0;
assert(mdir.rbyd.weight == 2);
memset(buffer+1, 'b', SIZE-1);
lfsr_mtree_namelookup(&lfs, 0, (const char*)buffer+1, SIZE-1,
&mdir, NULL, NULL) => LFS_ERR_NOENT;
lfsr_mdir_commit(&lfs, &mdir, LFSR_RATTRS(
LFSR_RATTR_NAME(
LFSR_TAG_REG, +1,
0, (const char*)buffer+1, SIZE-1))) => 0;
assert(mdir.rbyd.weight == 3);
// force mroot to compact
lfs.mroot.rbyd.eoff = -1;
lfsr_mdir_commit(&lfs, &lfs.mroot, LFSR_RATTRS(
LFSR_RATTR_BUF(LFSR_TAG_ATTR(1), 0, "c", 1))) => 0;
// assert mdirs were unininlined and split
assert(lfs.mtree.root.weight == (2 << lfs.mbits));
// assert mroot now has no entries
assert(lfs.mroot.rbyd.weight == 0);
// setup mroot to compact and relocate on next commit
lfs.mroot.rbyd.eoff = -1;
lfsr_mdir_t old_mroot = lfs.mroot;
// remove an entry, forcing the mdir to be dropped
memset(buffer+1, 'b', SIZE-1);
lfsr_mtree_namelookup(&lfs, 0, (const char*)buffer+1, SIZE-1,
&mdir, NULL, NULL) => 0;
// force mdir to compact twice, this should relocate
mdir.rbyd.eoff = -1;
lfsr_mdir_commit(&lfs, &mdir, LFSR_RATTRS(
LFSR_RATTR_BUF(LFSR_TAG_ATTR(2), 0, "d", 1))) => 0;
// force mdir to compact while we're removing
mdir.rbyd.eoff = -1;
lfsr_mdir_commit(&lfs, &mdir, LFSR_RATTRS(
LFSR_RATTR(LFSR_TAG_RM, -1))) => 0;
assert(mdir.rbyd.weight == 0);
// assert mroot relocated
assert(lfsr_mdir_cmp(&old_mroot, &lfs.mroot) != 0);
// assert mdir was dropped
assert(lfs.mtree.root.weight == (1 << lfs.mbits));
// assert mroot still has no entries
assert(lfs.mroot.rbyd.weight == 0);
// assert that our entries are still in the mtree
lfsr_mtree_lookup(&lfs, (0 << lfs.mbits)+1, &mdir) => 0;
assert(mdir.rbyd.weight == 2);
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_REG, NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, SIZE) => SIZE;
assert(buffer[1] == 'a');
lfsr_mdir_lookup(&lfs, &lfs.mroot, LFSR_TAG_ATTR(1), NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, 1) => 1;
assert(buffer[0] == 'c');
// check things stay sane after remount
lfsr_unmount(&lfs) => 0;
lfsr_mount(&lfs, LFS_M_RDWR | M_FLAGS, CFG) => 0;
// assert mdir was dropped
assert(lfs.mtree.root.weight == (1 << lfs.mbits));
// assert mroot still has no entries
assert(lfs.mroot.rbyd.weight == 0);
// assert that our entries are still in the mtree
lfsr_mtree_lookup(&lfs, (0 << lfs.mbits)+1, &mdir) => 0;
assert(mdir.rbyd.weight == 2);
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_REG, NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, SIZE) => SIZE;
assert(buffer[1] == 'a');
lfsr_mdir_lookup(&lfs, &lfs.mroot, LFSR_TAG_ATTR(1), NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, 1) => 1;
assert(buffer[0] == 'c');
lfsr_unmount(&lfs) => 0;
'''
[cases.test_mtree_uninline_extend]
# this should be set so only one entry can fit in a metadata block
defines.SIZE = 'BLOCK_SIZE / 4'
# make it so blocks relocate every two compacts
defines.BLOCK_RECYCLES = 0
in = 'lfs.c'
code = '''
lfs_t lfs;
lfsr_format(&lfs, LFS_F_RDWR | F_FLAGS, CFG) => 0;
lfsr_mount(&lfs, LFS_M_RDWR | M_FLAGS, CFG) => 0;
lfs_alloc_ckpoint(&lfs);
// force mroot to compact once, so the second compact below will
// trigger a relocation
lfs.mroot.rbyd.eoff = -1;
lfsr_mdir_commit(&lfs, &lfs.mroot, NULL, 0) => 0;
lfsr_data_t data;
// create a 2 large rattrs that needs to be uninlined
uint8_t buffer[SIZE];
memset(buffer, 'a', SIZE);
lfsr_mdir_commit(&lfs, &lfs.mroot, LFSR_RATTRS(
LFSR_RATTR_BUF(LFSR_TAG_ATTR(1), 0, buffer, SIZE))) => 0;
memset(buffer, 'b', SIZE);
lfsr_mdir_t mdir;
lfsr_mtree_lookup(&lfs, 0, &mdir) => 0;
lfsr_mdir_commit(&lfs, &mdir, LFSR_RATTRS(
LFSR_RATTR_BUF(LFSR_TAG_ATTR(2), 0, buffer, SIZE))) => 0;
// force mroot to compact, this should both uninline and relocate
lfsr_mdir_t old_mroot = lfs.mroot;
lfs.mroot.rbyd.eoff = -1;
lfsr_mdir_commit(&lfs, &lfs.mroot, LFSR_RATTRS(
LFSR_RATTR_BUF(LFSR_TAG_ATTR(3), 0, "c", 1))) => 0;
// assert mroot relocated
assert(lfsr_mdir_cmp(&old_mroot, &lfs.mroot) != 0);
// assert mdirs were unininlined
assert(lfs.mtree.root.weight == (1 << lfs.mbits));
// assert mroot now has no entries
assert(lfs.mroot.rbyd.weight == 0);
// assert that our rattrs are still in the mroot/mtree
lfsr_mdir_lookup(&lfs, &lfs.mroot, LFSR_TAG_ATTR(1), NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, SIZE) => SIZE;
assert(buffer[0] == 'a');
lfsr_mtree_lookup(&lfs, 0, &mdir) => 0;
assert(mdir.rbyd.weight == 1);
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_ATTR(2), NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, SIZE) => SIZE;
assert(buffer[0] == 'b');
lfsr_mdir_lookup(&lfs, &lfs.mroot, LFSR_TAG_ATTR(3), NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, 1) => 1;
assert(buffer[0] == 'c');
// check things stay sane after remount
lfsr_unmount(&lfs) => 0;
lfsr_mount(&lfs, LFS_M_RDWR | M_FLAGS, CFG) => 0;
// assert mdirs were unininlined
assert(lfs.mtree.root.weight == (1 << lfs.mbits));
// assert mroot now has no entries
assert(lfs.mroot.rbyd.weight == 0);
// assert that our rattrs are still in the mroot/mtree
lfsr_mdir_lookup(&lfs, &lfs.mroot, LFSR_TAG_ATTR(1), NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, SIZE) => SIZE;
assert(buffer[0] == 'a');
lfsr_mtree_lookup(&lfs, 0, &mdir) => 0;
assert(mdir.rbyd.weight == 1);
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_ATTR(2), NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, SIZE) => SIZE;
assert(buffer[0] == 'b');
lfsr_mdir_lookup(&lfs, &lfs.mroot, LFSR_TAG_ATTR(3), NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, 1) => 1;
assert(buffer[0] == 'c');
lfsr_unmount(&lfs) => 0;
'''
[cases.test_mtree_uninline_split_extend]
# this should be set so only one entry can fit in a metadata block
defines.SIZE = 'BLOCK_SIZE / 4'
# make it so blocks relocate every two compacts
defines.BLOCK_RECYCLES = 0
in = 'lfs.c'
code = '''
lfs_t lfs;
lfsr_format(&lfs, LFS_F_RDWR | F_FLAGS, CFG) => 0;
lfsr_mount(&lfs, LFS_M_RDWR | M_FLAGS, CFG) => 0;
lfs_alloc_ckpoint(&lfs);
// force mroot to compact once, so the second compact below will
// trigger a relocation
lfs.mroot.rbyd.eoff = -1;
lfsr_mdir_commit(&lfs, &lfs.mroot, NULL, 0) => 0;
lfsr_data_t data;
// create 2 large entries that needs to be uninlined and split
uint8_t buffer[SIZE];
buffer[0] = '\0';
memset(buffer+1, 'a', SIZE-1);
lfsr_mdir_t mdir;
lfsr_mtree_namelookup(&lfs, 0, (const char*)buffer+1, SIZE-1,
&mdir, NULL, NULL) => LFS_ERR_NOENT;
lfsr_mdir_commit(&lfs, &mdir, LFSR_RATTRS(
LFSR_RATTR_NAME(
LFSR_TAG_REG, +1,
0, (const char*)buffer+1, SIZE-1))) => 0;
assert(mdir.rbyd.weight == 2);
memset(buffer+1, 'b', SIZE-1);
lfsr_mtree_namelookup(&lfs, 0, (const char*)buffer+1, SIZE-1,
&mdir, NULL, NULL) => LFS_ERR_NOENT;
lfsr_mdir_commit(&lfs, &mdir, LFSR_RATTRS(
LFSR_RATTR_NAME(
LFSR_TAG_REG, +1,
0, (const char*)buffer+1, SIZE-1))) => 0;
assert(mdir.rbyd.weight == 3);
// force mroot to compact, this should both split and relocate
lfsr_mdir_t old_mroot = lfs.mroot;
lfs.mroot.rbyd.eoff = -1;
lfsr_mdir_commit(&lfs, &lfs.mroot, LFSR_RATTRS(
LFSR_RATTR_BUF(LFSR_TAG_ATTR(1), 0, "c", 1))) => 0;
// assert mroot relocated
assert(lfsr_mdir_cmp(&old_mroot, &lfs.mroot) != 0);
// assert mdirs were unininlined and split
assert(lfs.mtree.root.weight == (2 << lfs.mbits));
// assert mroot now has no entries
assert(lfs.mroot.rbyd.weight == 0);
// assert that our entries are still in the mtree
lfsr_mtree_lookup(&lfs, (0 << lfs.mbits)+1, &mdir) => 0;
assert(mdir.rbyd.weight == 2);
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_REG, NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, SIZE) => SIZE;
assert(buffer[1] == 'a');
lfsr_mtree_lookup(&lfs, (1 << lfs.mbits)+0, &mdir) => 0;
assert(mdir.rbyd.weight == 1);
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_REG, NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, SIZE) => SIZE;
assert(buffer[1] == 'b');
lfsr_mdir_lookup(&lfs, &lfs.mroot, LFSR_TAG_ATTR(1), NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, 1) => 1;
assert(buffer[0] == 'c');
// check things stay sane after remount
lfsr_unmount(&lfs) => 0;
lfsr_mount(&lfs, LFS_M_RDWR | M_FLAGS, CFG) => 0;
// assert mdirs were unininlined and split
assert(lfs.mtree.root.weight == (2 << lfs.mbits));
// assert mroot now has no entries
assert(lfs.mroot.rbyd.weight == 0);
// assert that our entries are still in the mtree
lfsr_mtree_lookup(&lfs, (0 << lfs.mbits)+1, &mdir) => 0;
assert(mdir.rbyd.weight == 2);
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_REG, NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, SIZE) => SIZE;
assert(buffer[1] == 'a');
lfsr_mtree_lookup(&lfs, (1 << lfs.mbits)+0, &mdir) => 0;
assert(mdir.rbyd.weight == 1);
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_REG, NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, SIZE) => SIZE;
assert(buffer[1] == 'b');
lfsr_mdir_lookup(&lfs, &lfs.mroot, LFSR_TAG_ATTR(1), NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, 1) => 1;
assert(buffer[0] == 'c');
lfsr_unmount(&lfs) => 0;
'''
# this fuzz covers a lot of configurations
[cases.test_mtree_relocate_fuzz]
defines.N = [5, 10, 20, 40]
defines.FORCE_COMPACTION = [false, true]
defines.BLOCK_RECYCLES = [4, 1, 0]
defines.SEED = 'range(500)'
fuzz = 'SEED'
in = 'lfs.c'
code = '''
lfs_t lfs;
lfsr_format(&lfs, LFS_F_RDWR | F_FLAGS, CFG) => 0;
lfsr_mount(&lfs, LFS_M_RDWR | M_FLAGS, CFG) => 0;
lfs_alloc_ckpoint(&lfs);
bool sim[N];
for (lfs_size_t i = 0; i < N; i++) {
sim[i] = false;
}
uint32_t prng = SEED;
for (lfs_size_t i = 0; i < N; i++) {
// choose a pseudo-random name
lfs_size_t x = TEST_PRNG(&prng) % N;
char name[256];
name[0] = '\0';
sprintf(name+1, "%03x", x);
// choose to create or delete
uint8_t op = TEST_PRNG(&prng) % 2;
// create
if (op == 0) {
// update sim
sim[x] = true;
// update mtree
lfsr_mdir_t mdir;
int err = lfsr_mtree_namelookup(&lfs, 0, name+1, 3,
&mdir, NULL, NULL);
assert(!err || err == LFS_ERR_NOENT);
if (!err) {
continue;
}
// force a compaction?
if (FORCE_COMPACTION) {
lfs.mroot.rbyd.eoff = -1;
mdir.rbyd.eoff = -1;
}
lfsr_mdir_commit(&lfs, &mdir, LFSR_RATTRS(
LFSR_RATTR_NAME(LFSR_TAG_REG, +1, 0, name+1, 3))) => 0;
lfsr_data_t data;
// double check
uint8_t buffer[256];
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_REG, NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, sizeof(buffer)) => 4;
assert(memcmp(buffer, name, 4) == 0);
// update
} else if (op == 1) {
// sim update is a noop
// update mtree
lfsr_mdir_t mdir;
int err = lfsr_mtree_namelookup(&lfs, 0, name+1, 3,
&mdir, NULL, NULL);
assert(!err || err == LFS_ERR_NOENT);
if (err == LFS_ERR_NOENT) {
continue;
}
// force a compaction?
if (FORCE_COMPACTION) {
lfs.mroot.rbyd.eoff = -1;
mdir.rbyd.eoff = -1;
}
// we can't really change metadata names, but commits still
// trigger writes to the mdir
lfsr_mdir_commit(&lfs, &mdir, LFSR_RATTRS(
LFSR_RATTR_NAME(LFSR_TAG_REG, 0, 0, name+1, 3))) => 0;
lfsr_data_t data;
// double check
uint8_t buffer[256];
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_REG, NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, sizeof(buffer)) => 4;
assert(memcmp(buffer, name, 4) == 0);
// delete
} else {
// update sim
sim[x] = false;
// update mtree
lfsr_mdir_t mdir;
int err = lfsr_mtree_namelookup(&lfs, 0, name+1, 3,
&mdir, NULL, NULL);
assert(!err || err == LFS_ERR_NOENT);
if (err == LFS_ERR_NOENT) {
continue;
}
// force a compaction?
if (FORCE_COMPACTION) {
lfs.mroot.rbyd.eoff = -1;
mdir.rbyd.eoff = -1;
}
lfsr_mdir_commit(&lfs, &mdir, LFSR_RATTRS(
LFSR_RATTR(LFSR_TAG_RM, -1))) => 0;
}
}
// try looking up each entry
lfsr_mdir_t mdir;
lfsr_mtree_lookup(&lfs, 0, &mdir) => 0;
lfsr_data_t data;
uint8_t buffer[256];
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_BOOKMARK, NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, sizeof(buffer)) => 1;
for (lfs_size_t i = 0; i < N; i++) {
char name[256];
name[0] = '\0';
sprintf(name+1, "%03x", i);
if (sim[i]) {
lfsr_mtree_namelookup(&lfs, 0, name+1, 3,
&mdir, NULL, NULL) => 0;
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_REG, NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, sizeof(buffer)) => 4;
assert(memcmp(buffer, name, 4) == 0);
} else {
lfsr_mtree_namelookup(&lfs, 0, name+1, 3,
&mdir, NULL, NULL) => LFS_ERR_NOENT;
}
}
// check things stay sane after remount
lfsr_unmount(&lfs) => 0;
lfsr_mount(&lfs, LFS_M_RDWR | M_FLAGS, CFG) => 0;
// try looking up each entry
lfsr_mtree_lookup(&lfs, 0, &mdir) => 0;
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_BOOKMARK, NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, sizeof(buffer)) => 1;
for (lfs_size_t i = 0; i < N; i++) {
char name[256];
name[0] = '\0';
sprintf(name+1, "%03x", i);
if (sim[i]) {
lfsr_mtree_namelookup(&lfs, 0, name+1, 3,
&mdir, NULL, NULL) => 0;
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_REG, NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, sizeof(buffer)) => 4;
assert(memcmp(buffer, name, 4) == 0);
} else {
lfsr_mtree_namelookup(&lfs, 0, name+1, 3,
&mdir, NULL, NULL) => LFS_ERR_NOENT;
}
}
lfsr_unmount(&lfs) => 0;
'''
## Opened mdir tracking ##
[cases.test_mtree_opened]
in = 'lfs.c'
code = '''
lfs_t lfs;
lfsr_format(&lfs, LFS_F_RDWR | F_FLAGS, CFG) => 0;
lfsr_mount(&lfs, LFS_M_RDWR | M_FLAGS, CFG) => 0;
lfs_alloc_ckpoint(&lfs);
// setup our neighbors
lfsr_omdir_t left = {.flags=0};
lfsr_mtree_namelookup(&lfs, 0, "a", 1,
&left.mdir, NULL, NULL) => LFS_ERR_NOENT;
lfsr_mdir_commit(&lfs, &left.mdir, LFSR_RATTRS(
LFSR_RATTR_NAME(LFSR_TAG_REG, +1, 0, "a", 1))) => 0;
assert(left.mdir.rbyd.weight == 2);
lfsr_omdir_open(&lfs, &left);
lfsr_omdir_t right = {.flags=0};
lfsr_mtree_namelookup(&lfs, 0, "c", 1,
&right.mdir, NULL, NULL) => LFS_ERR_NOENT;
lfsr_mdir_commit(&lfs, &right.mdir, LFSR_RATTRS(
LFSR_RATTR_NAME(LFSR_TAG_REG, +1, 0, "c", 1))) => 0;
assert(right.mdir.rbyd.weight == 3);
lfsr_omdir_open(&lfs, &right);
// insert a new entry, this should update our neighbors
lfsr_mdir_t mdir;
lfsr_mtree_namelookup(&lfs, 0, "b", 1,
&mdir, NULL, NULL) => LFS_ERR_NOENT;
lfsr_mdir_commit(&lfs, &mdir, LFSR_RATTRS(
LFSR_RATTR_NAME(LFSR_TAG_REG, +1, 0, "b", 1))) => 0;
assert(mdir.rbyd.weight == 4);
lfsr_data_t data;
// assert our entry was created
uint8_t buffer[2];
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_REG, NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, 2) => 2;
assert(buffer[1] == 'b');
// assert that our neighbors were updated correctly
lfsr_mtree_namelookup(&lfs, 0, "a", 1,
&mdir, NULL, NULL) => 0;
assert(left.mdir.mid == mdir.mid);
assert(lfsr_mdir_cmp(&left.mdir, &mdir) == 0);
assert(left.mdir.rbyd.trunk == mdir.rbyd.trunk);
assert(left.mdir.rbyd.cksum == mdir.rbyd.cksum);
lfsr_mtree_namelookup(&lfs, 0, "c", 1,
&mdir, NULL, NULL) => 0;
assert(right.mdir.mid == mdir.mid);
assert(lfsr_mdir_cmp(&right.mdir, &mdir) == 0);
assert(right.mdir.rbyd.trunk == mdir.rbyd.trunk);
assert(right.mdir.rbyd.cksum == mdir.rbyd.cksum);
lfsr_omdir_close(&lfs, &left);
lfsr_omdir_close(&lfs, &right);
lfsr_unmount(&lfs) => 0;
'''
[cases.test_mtree_opened_remove_l]
in = 'lfs.c'
code = '''
lfs_t lfs;
lfsr_format(&lfs, LFS_F_RDWR | F_FLAGS, CFG) => 0;
lfsr_mount(&lfs, LFS_M_RDWR | M_FLAGS, CFG) => 0;
lfs_alloc_ckpoint(&lfs);
// setup our neighbors
lfsr_omdir_t left = {.flags=0};
lfsr_mtree_namelookup(&lfs, 0, "a", 1,
&left.mdir, NULL, NULL) => LFS_ERR_NOENT;
lfsr_mdir_commit(&lfs, &left.mdir, LFSR_RATTRS(
LFSR_RATTR_NAME(LFSR_TAG_REG, +1, 0, "a", 1))) => 0;
assert(left.mdir.rbyd.weight == 2);
lfsr_omdir_open(&lfs, &left);
lfsr_omdir_t right = {.flags=0};
lfsr_mtree_namelookup(&lfs, 0, "b", 1,
&right.mdir, NULL, NULL) => LFS_ERR_NOENT;
lfsr_mdir_commit(&lfs, &right.mdir, LFSR_RATTRS(
LFSR_RATTR_NAME(LFSR_TAG_REG, +1, 0, "b", 1))) => 0;
assert(right.mdir.rbyd.weight == 3);
lfsr_omdir_open(&lfs, &right);
// try removing left neighbor
lfsr_mdir_t mdir;
lfsr_mtree_namelookup(&lfs, 0, "a", 1,
&mdir, NULL, NULL) => 0;
lfsr_mdir_commit(&lfs, &mdir, LFSR_RATTRS(
LFSR_RATTR(LFSR_TAG_RM, -1))) => 0;
assert(mdir.rbyd.weight == 2);
// assert neighbor was removed
lfsr_mtree_namelookup(&lfs, 0, "a", 1,
&mdir, NULL, NULL) => LFS_ERR_NOENT;
// assert that our neighbors were updated correctly
lfsr_mtree_namelookup(&lfs, 0, "b", 1,
&mdir, NULL, NULL) => 0;
assert(right.mdir.mid == mdir.mid);
assert(lfsr_mdir_cmp(&right.mdir, &mdir) == 0);
assert(right.mdir.rbyd.trunk == mdir.rbyd.trunk);
assert(right.mdir.rbyd.cksum == mdir.rbyd.cksum);
lfsr_omdir_close(&lfs, &left);
lfsr_omdir_close(&lfs, &right);
lfsr_unmount(&lfs) => 0;
'''
[cases.test_mtree_opened_remove_r]
in = 'lfs.c'
code = '''
lfs_t lfs;
lfsr_format(&lfs, LFS_F_RDWR | F_FLAGS, CFG) => 0;
lfsr_mount(&lfs, LFS_M_RDWR | M_FLAGS, CFG) => 0;
lfs_alloc_ckpoint(&lfs);
// setup our neighbors
lfsr_omdir_t left = {.flags=0};
lfsr_mtree_namelookup(&lfs, 0, "a", 1,
&left.mdir, NULL, NULL) => LFS_ERR_NOENT;
lfsr_mdir_commit(&lfs, &left.mdir, LFSR_RATTRS(
LFSR_RATTR_NAME(LFSR_TAG_REG, +1, 0, "a", 1))) => 0;
assert(left.mdir.rbyd.weight == 2);
lfsr_omdir_open(&lfs, &left);
lfsr_omdir_t right = {.flags=0};
lfsr_mtree_namelookup(&lfs, 0, "b", 1,
&right.mdir, NULL, NULL) => LFS_ERR_NOENT;
lfsr_mdir_commit(&lfs, &right.mdir, LFSR_RATTRS(
LFSR_RATTR_NAME(LFSR_TAG_REG, +1, 0, "b", 1))) => 0;
assert(right.mdir.rbyd.weight == 3);
lfsr_omdir_open(&lfs, &right);
// try removing right neighbor
lfsr_mdir_t mdir;
lfsr_mtree_namelookup(&lfs, 0, "b", 1,
&mdir, NULL, NULL) => 0;
lfsr_mdir_commit(&lfs, &mdir, LFSR_RATTRS(
LFSR_RATTR(LFSR_TAG_RM, -1))) => 0;
assert(mdir.rbyd.weight == 2);
// assert neighbor was removed
lfsr_mtree_namelookup(&lfs, 0, "b", 1,
&mdir, NULL, NULL) => LFS_ERR_NOENT;
// assert that our neighbors were updated correctly
lfsr_mtree_namelookup(&lfs, 0, "a", 1,
&mdir, NULL, NULL) => 0;
assert(left.mdir.mid == mdir.mid);
assert(lfsr_mdir_cmp(&left.mdir, &mdir) == 0);
assert(left.mdir.rbyd.trunk == mdir.rbyd.trunk);
assert(left.mdir.rbyd.cksum == mdir.rbyd.cksum);
lfsr_omdir_close(&lfs, &left);
lfsr_omdir_close(&lfs, &right);
lfsr_unmount(&lfs) => 0;
'''
[cases.test_mtree_opened_uninline_split]
# this should be set so only one entry can fit in a metadata block
defines.SIZE = 'BLOCK_SIZE / 4'
in = 'lfs.c'
code = '''
lfs_t lfs;
lfsr_format(&lfs, LFS_F_RDWR | F_FLAGS, CFG) => 0;
lfsr_mount(&lfs, LFS_M_RDWR | M_FLAGS, CFG) => 0;
lfs_alloc_ckpoint(&lfs);
// setup our neighbors
lfsr_omdir_t left = {.flags=0};
lfsr_mtree_namelookup(&lfs, 0, "a", 1,
&left.mdir, NULL, NULL) => LFS_ERR_NOENT;
lfsr_mdir_commit(&lfs, &left.mdir, LFSR_RATTRS(
LFSR_RATTR_NAME(LFSR_TAG_REG, +1, 0, "a", 1))) => 0;
assert(left.mdir.rbyd.weight == 2);
lfsr_omdir_open(&lfs, &left);
lfsr_omdir_t right = {.flags=0};
lfsr_mtree_namelookup(&lfs, 0, "d", 1,
&right.mdir, NULL, NULL) => LFS_ERR_NOENT;
lfsr_mdir_commit(&lfs, &right.mdir, LFSR_RATTRS(
LFSR_RATTR_NAME(LFSR_TAG_REG, +1, 0, "d", 1))) => 0;
assert(right.mdir.rbyd.weight == 3);
lfsr_omdir_open(&lfs, &right);
// create 2 large entries that needs to be uninlined and split
uint8_t buffer[SIZE];
buffer[0] = '\0';
memset(buffer+1, 'b', SIZE-1);
lfsr_mdir_t mdir;
lfsr_mtree_namelookup(&lfs, 0, (const char*)buffer+1, SIZE-1,
&mdir, NULL, NULL) => LFS_ERR_NOENT;
lfsr_mdir_commit(&lfs, &mdir, LFSR_RATTRS(
LFSR_RATTR_NAME(
LFSR_TAG_REG, +1,
0, (const char*)buffer+1, SIZE-1))) => 0;
assert(mdir.rbyd.weight == 4);
memset(buffer+1, 'c', SIZE-1);
lfsr_mtree_namelookup(&lfs, 0, (const char*)buffer+1, SIZE-1,
&mdir, NULL, NULL) => LFS_ERR_NOENT;
lfsr_mdir_commit(&lfs, &mdir, LFSR_RATTRS(
LFSR_RATTR_NAME(
LFSR_TAG_REG, +1,
0, (const char*)buffer+1, SIZE-1))) => 0;
assert(mdir.rbyd.weight == 5);
// force mroot to compact
lfs.mroot.rbyd.eoff = -1;
lfsr_mdir_commit(&lfs, &lfs.mroot, NULL, 0) => 0;
// assert mdirs were unininlined and split
assert(lfs.mtree.root.weight == (2 << lfs.mbits));
// assert mroot now has no entries
assert(lfs.mroot.rbyd.weight == 0);
// assert that our neighbors were updated correctly
lfsr_mtree_namelookup(&lfs, 0, "a", 1,
&mdir, NULL, NULL) => 0;
assert(left.mdir.mid == mdir.mid);
assert(lfsr_mdir_cmp(&left.mdir, &mdir) == 0);
assert(left.mdir.rbyd.trunk == mdir.rbyd.trunk);
assert(left.mdir.rbyd.cksum == mdir.rbyd.cksum);
lfsr_mtree_namelookup(&lfs, 0, "d", 1,
&mdir, NULL, NULL) => 0;
assert(right.mdir.mid == mdir.mid);
assert(lfsr_mdir_cmp(&right.mdir, &mdir) == 0);
assert(right.mdir.rbyd.trunk == mdir.rbyd.trunk);
assert(right.mdir.rbyd.cksum == mdir.rbyd.cksum);
lfsr_omdir_close(&lfs, &left);
lfsr_omdir_close(&lfs, &right);
lfsr_unmount(&lfs) => 0;
'''
[cases.test_mtree_opened_split]
# this should be set so only one entry can fit in a metadata block
defines.SIZE = 'BLOCK_SIZE / 4'
in = 'lfs.c'
code = '''
lfs_t lfs;
lfsr_format(&lfs, LFS_F_RDWR | F_FLAGS, CFG) => 0;
lfsr_mount(&lfs, LFS_M_RDWR | M_FLAGS, CFG) => 0;
lfs_alloc_ckpoint(&lfs);
// setup our neighbors
lfsr_omdir_t left = {.flags=0};
lfsr_mtree_namelookup(&lfs, 0, "a", 1,
&left.mdir, NULL, NULL) => LFS_ERR_NOENT;
lfsr_mdir_commit(&lfs, &left.mdir, LFSR_RATTRS(
LFSR_RATTR_NAME(LFSR_TAG_REG, +1, 0, "a", 1))) => 0;
assert(left.mdir.rbyd.weight == 2);
lfsr_omdir_open(&lfs, &left);
lfsr_omdir_t right = {.flags=0};
lfsr_mtree_namelookup(&lfs, 0, "e", 1,
&right.mdir, NULL, NULL) => LFS_ERR_NOENT;
lfsr_mdir_commit(&lfs, &right.mdir, LFSR_RATTRS(
LFSR_RATTR_NAME(LFSR_TAG_REG, +1, 0, "e", 1))) => 0;
assert(right.mdir.rbyd.weight == 3);
lfsr_omdir_open(&lfs, &right);
// create 2 large entries that needs to be uninlined and split
uint8_t buffer[SIZE];
buffer[0] = '\0';
memset(buffer+1, 'b', SIZE-1);
lfsr_mdir_t mdir;
lfsr_mtree_namelookup(&lfs, 0, (const char*)buffer+1, SIZE-1,
&mdir, NULL, NULL) => LFS_ERR_NOENT;
lfsr_mdir_commit(&lfs, &mdir, LFSR_RATTRS(
LFSR_RATTR_NAME(
LFSR_TAG_REG, +1,
0, (const char*)buffer+1, SIZE-1))) => 0;
assert(mdir.rbyd.weight == 4);
memset(buffer+1, 'd', SIZE-1);
lfsr_mtree_namelookup(&lfs, 0, (const char*)buffer+1, SIZE-1,
&mdir, NULL, NULL) => LFS_ERR_NOENT;
lfsr_mdir_commit(&lfs, &mdir, LFSR_RATTRS(
LFSR_RATTR_NAME(
LFSR_TAG_REG, +1,
0, (const char*)buffer+1, SIZE-1))) => 0;
assert(mdir.rbyd.weight == 5);
// force mroot to compact
lfs.mroot.rbyd.eoff = -1;
lfsr_mdir_commit(&lfs, &lfs.mroot, NULL, 0) => 0;
// now add another large entry to an mdir, forcing a split
memset(buffer+1, 'c', SIZE-1);
lfsr_mtree_namelookup(&lfs, 0, (const char*)buffer+1, SIZE-1,
&mdir, NULL, NULL) => LFS_ERR_NOENT;
lfsr_mdir_commit(&lfs, &mdir, LFSR_RATTRS(
LFSR_RATTR_NAME(
LFSR_TAG_REG, +1,
0, (const char*)buffer+1, SIZE-1))) => 0;
assert(mdir.rbyd.weight == 4);
// force mdir to compact
mdir.rbyd.eoff = -1;
lfsr_mdir_commit(&lfs, &mdir, NULL, 0) => 0;
// assert mdir was split correctly
assert(lfs.mtree.root.weight == (3 << lfs.mbits));
// assert mroot still has no entries
assert(lfs.mroot.rbyd.weight == 0);
// assert that our neighbors were updated correctly
lfsr_mtree_namelookup(&lfs, 0, "a", 1,
&mdir, NULL, NULL) => 0;
assert(left.mdir.mid == mdir.mid);
assert(lfsr_mdir_cmp(&left.mdir, &mdir) == 0);
assert(left.mdir.rbyd.trunk == mdir.rbyd.trunk);
assert(left.mdir.rbyd.cksum == mdir.rbyd.cksum);
lfsr_mtree_namelookup(&lfs, 0, "e", 1,
&mdir, NULL, NULL) => 0;
assert(right.mdir.mid == mdir.mid);
assert(lfsr_mdir_cmp(&right.mdir, &mdir) == 0);
assert(right.mdir.rbyd.trunk == mdir.rbyd.trunk);
assert(right.mdir.rbyd.cksum == mdir.rbyd.cksum);
lfsr_omdir_close(&lfs, &left);
lfsr_omdir_close(&lfs, &right);
lfsr_unmount(&lfs) => 0;
'''
[cases.test_mtree_opened_extend]
# make it so blocks relocate every two compacts
defines.BLOCK_RECYCLES = 0
in = 'lfs.c'
code = '''
lfs_t lfs;
lfsr_format(&lfs, LFS_F_RDWR | F_FLAGS, CFG) => 0;
lfsr_mount(&lfs, LFS_M_RDWR | M_FLAGS, CFG) => 0;
lfs_alloc_ckpoint(&lfs);
// setup our neighbors
lfsr_omdir_t left = {.flags=0};
lfsr_mtree_namelookup(&lfs, 0, "a", 1,
&left.mdir, NULL, NULL) => LFS_ERR_NOENT;
lfsr_mdir_commit(&lfs, &left.mdir, LFSR_RATTRS(
LFSR_RATTR_NAME(LFSR_TAG_REG, +1, 0, "a", 1))) => 0;
assert(left.mdir.rbyd.weight == 2);
lfsr_omdir_open(&lfs, &left);
lfsr_omdir_t right = {.flags=0};
lfsr_mtree_namelookup(&lfs, 0, "b", 1,
&right.mdir, NULL, NULL) => LFS_ERR_NOENT;
lfsr_mdir_commit(&lfs, &right.mdir, LFSR_RATTRS(
LFSR_RATTR_NAME(LFSR_TAG_REG, +1, 0, "b", 1))) => 0;
assert(right.mdir.rbyd.weight == 3);
lfsr_omdir_open(&lfs, &right);
// force mroot to compact twice, this should extend the mroot
lfsr_mdir_t old_mroot = lfs.mroot;
lfs.mroot.rbyd.eoff = -1;
lfsr_mdir_commit(&lfs, &lfs.mroot, NULL, 0) => 0;
lfs.mroot.rbyd.eoff = -1;
lfsr_mdir_commit(&lfs, &lfs.mroot, NULL, 0) => 0;
// assert we relocated
assert(lfsr_mdir_cmp(&old_mroot, &lfs.mroot) != 0);
// assert that our neighbors were updated correctly
lfsr_mdir_t mdir;
lfsr_mtree_namelookup(&lfs, 0, "a", 1,
&mdir, NULL, NULL) => 0;
assert(left.mdir.mid == mdir.mid);
assert(lfsr_mdir_cmp(&left.mdir, &mdir) == 0);
assert(left.mdir.rbyd.trunk == mdir.rbyd.trunk);
assert(left.mdir.rbyd.cksum == mdir.rbyd.cksum);
lfsr_mtree_namelookup(&lfs, 0, "b", 1,
&mdir, NULL, NULL) => 0;
assert(right.mdir.mid == mdir.mid);
assert(lfsr_mdir_cmp(&right.mdir, &mdir) == 0);
assert(right.mdir.rbyd.trunk == mdir.rbyd.trunk);
assert(right.mdir.rbyd.cksum == mdir.rbyd.cksum);
lfsr_omdir_close(&lfs, &left);
lfsr_omdir_close(&lfs, &right);
lfsr_unmount(&lfs) => 0;
'''
[cases.test_mtree_opened_relocate_l]
# this should be set so only one entry can fit in a metadata block
defines.SIZE = 'BLOCK_SIZE / 4'
# make it so blocks relocate every two compacts
defines.BLOCK_RECYCLES = 0
in = 'lfs.c'
code = '''
lfs_t lfs;
lfsr_format(&lfs, LFS_F_RDWR | F_FLAGS, CFG) => 0;
lfsr_mount(&lfs, LFS_M_RDWR | M_FLAGS, CFG) => 0;
lfs_alloc_ckpoint(&lfs);
// setup our neighbors
lfsr_omdir_t left = {.flags=0};
lfsr_mtree_namelookup(&lfs, 0, "a", 1,
&left.mdir, NULL, NULL) => LFS_ERR_NOENT;
lfsr_mdir_commit(&lfs, &left.mdir, LFSR_RATTRS(
LFSR_RATTR_NAME(LFSR_TAG_REG, +1, 0, "a", 1))) => 0;
assert(left.mdir.rbyd.weight == 2);
lfsr_omdir_open(&lfs, &left);
lfsr_omdir_t right = {.flags=0};
lfsr_mtree_namelookup(&lfs, 0, "d", 1,
&right.mdir, NULL, NULL) => LFS_ERR_NOENT;
lfsr_mdir_commit(&lfs, &right.mdir, LFSR_RATTRS(
LFSR_RATTR_NAME(LFSR_TAG_REG, +1, 0, "d", 1))) => 0;
assert(right.mdir.rbyd.weight == 3);
lfsr_omdir_open(&lfs, &right);
// create 2 large entries that needs to be uninlined and split
uint8_t buffer[SIZE];
buffer[0] = '\0';
memset(buffer+1, 'b', SIZE-1);
lfsr_mdir_t mdir;
lfsr_mtree_namelookup(&lfs, 0, (const char*)buffer+1, SIZE-1,
&mdir, NULL, NULL) => LFS_ERR_NOENT;
lfsr_mdir_commit(&lfs, &mdir, LFSR_RATTRS(
LFSR_RATTR_NAME(
LFSR_TAG_REG, +1,
0, (const char*)buffer+1, SIZE-1))) => 0;
assert(mdir.rbyd.weight == 4);
memset(buffer+1, 'c', SIZE-1);
lfsr_mtree_namelookup(&lfs, 0, (const char*)buffer+1, SIZE-1,
&mdir, NULL, NULL) => LFS_ERR_NOENT;
lfsr_mdir_commit(&lfs, &mdir, LFSR_RATTRS(
LFSR_RATTR_NAME(
LFSR_TAG_REG, +1,
0, (const char*)buffer+1, SIZE-1))) => 0;
assert(mdir.rbyd.weight == 5);
// force mroot to compact
lfs.mroot.rbyd.eoff = -1;
lfsr_mdir_commit(&lfs, &lfs.mroot, NULL, 0) => 0;
// assert mdirs were unininlined and split
assert(lfs.mtree.root.weight == (2 << lfs.mbits));
// assert mroot now has no entries
assert(lfs.mroot.rbyd.weight == 0);
// force mdir to compact twice, this should relocate
memset(buffer+1, 'b', SIZE-1);
lfsr_mtree_namelookup(&lfs, 0, (const char*)buffer+1, SIZE-1,
&mdir, NULL, NULL) => 0;
lfsr_mdir_t old_mdir = mdir;
mdir.rbyd.eoff = -1;
lfsr_mdir_commit(&lfs, &mdir, LFSR_RATTRS(
LFSR_RATTR_NAME(
LFSR_TAG_REG, 0,
0, (const char*)buffer+1, SIZE-1))) => 0;
mdir.rbyd.eoff = -1;
lfsr_mdir_commit(&lfs, &mdir, LFSR_RATTRS(
LFSR_RATTR_NAME(
LFSR_TAG_REG, 0,
0, (const char*)buffer+1, SIZE-1))) => 0;
// assert we relocated
assert(lfsr_mdir_cmp(&old_mdir, &mdir) != 0);
// assert that our neighbors were updated correctly
lfsr_mtree_namelookup(&lfs, 0, "a", 1,
&mdir, NULL, NULL) => 0;
assert(left.mdir.mid == mdir.mid);
assert(lfsr_mdir_cmp(&left.mdir, &mdir) == 0);
assert(left.mdir.rbyd.trunk == mdir.rbyd.trunk);
assert(left.mdir.rbyd.cksum == mdir.rbyd.cksum);
lfsr_mtree_namelookup(&lfs, 0, "d", 1,
&mdir, NULL, NULL) => 0;
assert(right.mdir.mid == mdir.mid);
assert(lfsr_mdir_cmp(&right.mdir, &mdir) == 0);
assert(right.mdir.rbyd.trunk == mdir.rbyd.trunk);
assert(right.mdir.rbyd.cksum == mdir.rbyd.cksum);
lfsr_omdir_close(&lfs, &left);
lfsr_omdir_close(&lfs, &right);
lfsr_unmount(&lfs) => 0;
'''
[cases.test_mtree_opened_relocate_r]
# this should be set so only one entry can fit in a metadata block
defines.SIZE = 'BLOCK_SIZE / 4'
# make it so blocks relocate every two compacts
defines.BLOCK_RECYCLES = 0
in = 'lfs.c'
code = '''
lfs_t lfs;
lfsr_format(&lfs, LFS_F_RDWR | F_FLAGS, CFG) => 0;
lfsr_mount(&lfs, LFS_M_RDWR | M_FLAGS, CFG) => 0;
lfs_alloc_ckpoint(&lfs);
// setup our neighbors
lfsr_omdir_t left = {.flags=0};
lfsr_mtree_namelookup(&lfs, 0, "a", 1,
&left.mdir, NULL, NULL) => LFS_ERR_NOENT;
lfsr_mdir_commit(&lfs, &left.mdir, LFSR_RATTRS(
LFSR_RATTR_NAME(LFSR_TAG_REG, +1, 0, "a", 1))) => 0;
assert(left.mdir.rbyd.weight == 2);
lfsr_omdir_open(&lfs, &left);
lfsr_omdir_t right = {.flags=0};
lfsr_mtree_namelookup(&lfs, 0, "d", 1,
&right.mdir, NULL, NULL) => LFS_ERR_NOENT;
lfsr_mdir_commit(&lfs, &right.mdir, LFSR_RATTRS(
LFSR_RATTR_NAME(LFSR_TAG_REG, +1, 0, "d", 1))) => 0;
assert(right.mdir.rbyd.weight == 3);
lfsr_omdir_open(&lfs, &right);
// create 2 large entries that needs to be uninlined and split
uint8_t buffer[SIZE];
buffer[0] = '\0';
memset(buffer+1, 'b', SIZE-1);
lfsr_mdir_t mdir;
lfsr_mtree_namelookup(&lfs, 0, (const char*)buffer+1, SIZE-1,
&mdir, NULL, NULL) => LFS_ERR_NOENT;
lfsr_mdir_commit(&lfs, &mdir, LFSR_RATTRS(
LFSR_RATTR_NAME(
LFSR_TAG_REG, +1,
0, (const char*)buffer+1, SIZE-1))) => 0;
assert(mdir.rbyd.weight == 4);
memset(buffer+1, 'c', SIZE-1);
lfsr_mtree_namelookup(&lfs, 0, (const char*)buffer+1, SIZE-1,
&mdir, NULL, NULL) => LFS_ERR_NOENT;
lfsr_mdir_commit(&lfs, &mdir, LFSR_RATTRS(
LFSR_RATTR_NAME(
LFSR_TAG_REG, +1,
0, (const char*)buffer+1, SIZE-1))) => 0;
assert(mdir.rbyd.weight == 5);
// force mroot to compact
lfs.mroot.rbyd.eoff = -1;
lfsr_mdir_commit(&lfs, &lfs.mroot, NULL, 0) => 0;
// assert mdirs were unininlined and split
assert(lfs.mtree.root.weight == (2 << lfs.mbits));
// assert mroot now has no entries
assert(lfs.mroot.rbyd.weight == 0);
// force mdir to compact twice, this should relocate
memset(buffer+1, 'c', SIZE-1);
lfsr_mtree_namelookup(&lfs, 0, (const char*)buffer+1, SIZE-1,
&mdir, NULL, NULL) => 0;
lfsr_mdir_t old_mdir = mdir;
mdir.rbyd.eoff = -1;
lfsr_mdir_commit(&lfs, &mdir, LFSR_RATTRS(
LFSR_RATTR_NAME(
LFSR_TAG_REG, 0,
0, (const char*)buffer+1, SIZE-1))) => 0;
mdir.rbyd.eoff = -1;
lfsr_mdir_commit(&lfs, &mdir, LFSR_RATTRS(
LFSR_RATTR_NAME(
LFSR_TAG_REG, 0,
0, (const char*)buffer+1, SIZE-1))) => 0;
// assert we relocated
assert(lfsr_mdir_cmp(&old_mdir, &mdir) != 0);
// assert that our neighbors were updated correctly
lfsr_mtree_namelookup(&lfs, 0, "a", 1,
&mdir, NULL, NULL) => 0;
assert(left.mdir.mid == mdir.mid);
assert(lfsr_mdir_cmp(&left.mdir, &mdir) == 0);
assert(left.mdir.rbyd.trunk == mdir.rbyd.trunk);
assert(left.mdir.rbyd.cksum == mdir.rbyd.cksum);
lfsr_mtree_namelookup(&lfs, 0, "d", 1,
&mdir, NULL, NULL) => 0;
assert(right.mdir.mid == mdir.mid);
assert(lfsr_mdir_cmp(&right.mdir, &mdir) == 0);
assert(right.mdir.rbyd.trunk == mdir.rbyd.trunk);
assert(right.mdir.rbyd.cksum == mdir.rbyd.cksum);
lfsr_omdir_close(&lfs, &left);
lfsr_omdir_close(&lfs, &right);
lfsr_unmount(&lfs) => 0;
'''
[cases.test_mtree_opened_middle_split]
# this should be set so only one entry can fit in a metadata block
defines.SIZE = 'BLOCK_SIZE / 4'
in = 'lfs.c'
code = '''
lfs_t lfs;
lfsr_format(&lfs, LFS_F_RDWR | F_FLAGS, CFG) => 0;
lfsr_mount(&lfs, LFS_M_RDWR | M_FLAGS, CFG) => 0;
lfs_alloc_ckpoint(&lfs);
// setup our neighbors
lfsr_omdir_t left = {.flags=0};
lfsr_mtree_namelookup(&lfs, 0, "a", 1,
&left.mdir, NULL, NULL) => LFS_ERR_NOENT;
lfsr_mdir_commit(&lfs, &left.mdir, LFSR_RATTRS(
LFSR_RATTR_NAME(LFSR_TAG_REG, +1, 0, "a", 1))) => 0;
assert(left.mdir.rbyd.weight == 2);
lfsr_omdir_open(&lfs, &left);
lfsr_omdir_t right = {.flags=0};
lfsr_mtree_namelookup(&lfs, 0, "f", 1,
&right.mdir, NULL, NULL) => LFS_ERR_NOENT;
lfsr_mdir_commit(&lfs, &right.mdir, LFSR_RATTRS(
LFSR_RATTR_NAME(LFSR_TAG_REG, +1, 0, "f", 1))) => 0;
assert(right.mdir.rbyd.weight == 3);
lfsr_omdir_open(&lfs, &right);
// create 2 large entries that needs to be uninlined and split
uint8_t buffer[SIZE];
buffer[0] = '\0';
memset(buffer+1, 'b', SIZE-1);
lfsr_mdir_t mdir;
lfsr_mtree_namelookup(&lfs, 0, (const char*)buffer+1, SIZE-1,
&mdir, NULL, NULL) => LFS_ERR_NOENT;
lfsr_mdir_commit(&lfs, &mdir, LFSR_RATTRS(
LFSR_RATTR_NAME(
LFSR_TAG_REG, +1,
0, (const char*)buffer+1, SIZE-1))) => 0;
assert(mdir.rbyd.weight == 4);
memset(buffer+1, 'e', SIZE-1);
lfsr_mtree_namelookup(&lfs, 0, (const char*)buffer+1, SIZE-1,
&mdir, NULL, NULL) => LFS_ERR_NOENT;
lfsr_mdir_commit(&lfs, &mdir, LFSR_RATTRS(
LFSR_RATTR_NAME(
LFSR_TAG_REG, +1,
0, (const char*)buffer+1, SIZE-1))) => 0;
assert(mdir.rbyd.weight == 5);
// force mroot to compact
lfs.mroot.rbyd.eoff = -1;
lfsr_mdir_commit(&lfs, &lfs.mroot, NULL, 0) => 0;
// now add another large entry to an mdir, forcing a split
memset(buffer+1, 'c', SIZE-1);
lfsr_mtree_namelookup(&lfs, 0, (const char*)buffer+1, SIZE-1,
&mdir, NULL, NULL) => LFS_ERR_NOENT;
lfsr_mdir_commit(&lfs, &mdir, LFSR_RATTRS(
LFSR_RATTR_NAME(
LFSR_TAG_REG, +1,
0, (const char*)buffer+1, SIZE-1))) => 0;
assert(mdir.rbyd.weight == 4);
// force mdir to compact
mdir.rbyd.eoff = -1;
lfsr_mdir_commit(&lfs, &mdir, NULL, 0) => 0;
// assert mdir was split correctly
assert(lfs.mtree.root.weight == (3 << lfs.mbits));
// assert mroot still has no entries
assert(lfs.mroot.rbyd.weight == 0);
// now add _another_ large entry to the middle mdir, forcing another split
memset(buffer+1, 'd', SIZE-1);
lfsr_mtree_namelookup(&lfs, 0, (const char*)buffer+1, SIZE-1,
&mdir, NULL, NULL) => LFS_ERR_NOENT;
lfsr_mdir_commit(&lfs, &mdir, LFSR_RATTRS(
LFSR_RATTR_NAME(
LFSR_TAG_REG, +1,
0, (const char*)buffer+1, SIZE-1))) => 0;
assert(mdir.rbyd.weight == 2);
// force mdir to compact
mdir.rbyd.eoff = -1;
lfsr_mdir_commit(&lfs, &mdir, NULL, 0) => 0;
// assert mdir was split correctly
assert(lfs.mtree.root.weight == (4 << lfs.mbits));
// assert mroot still has no entries
assert(lfs.mroot.rbyd.weight == 0);
// assert that our neighbors were updated correctly
lfsr_mtree_namelookup(&lfs, 0, "a", 1,
&mdir, NULL, NULL) => 0;
assert(left.mdir.mid == mdir.mid);
assert(lfsr_mdir_cmp(&left.mdir, &mdir) == 0);
assert(left.mdir.rbyd.trunk == mdir.rbyd.trunk);
assert(left.mdir.rbyd.cksum == mdir.rbyd.cksum);
lfsr_mtree_namelookup(&lfs, 0, "f", 1,
&mdir, NULL, NULL) => 0;
assert(right.mdir.mid == mdir.mid);
assert(lfsr_mdir_cmp(&right.mdir, &mdir) == 0);
assert(right.mdir.rbyd.trunk == mdir.rbyd.trunk);
assert(right.mdir.rbyd.cksum == mdir.rbyd.cksum);
lfsr_omdir_close(&lfs, &left);
lfsr_omdir_close(&lfs, &right);
lfsr_unmount(&lfs) => 0;
'''
[cases.test_mtree_opened_middle_drop]
# this should be set so only one entry can fit in a metadata block
defines.SIZE = 'BLOCK_SIZE / 4'
in = 'lfs.c'
code = '''
lfs_t lfs;
lfsr_format(&lfs, LFS_F_RDWR | F_FLAGS, CFG) => 0;
lfsr_mount(&lfs, LFS_M_RDWR | M_FLAGS, CFG) => 0;
lfs_alloc_ckpoint(&lfs);
// setup our neighbors
lfsr_omdir_t left = {.flags=0};
lfsr_mtree_namelookup(&lfs, 0, "a", 1,
&left.mdir, NULL, NULL) => LFS_ERR_NOENT;
lfsr_mdir_commit(&lfs, &left.mdir, LFSR_RATTRS(
LFSR_RATTR_NAME(LFSR_TAG_REG, +1, 0, "a", 1))) => 0;
assert(left.mdir.rbyd.weight == 2);
lfsr_omdir_open(&lfs, &left);
lfsr_omdir_t right = {.flags=0};
lfsr_mtree_namelookup(&lfs, 0, "e", 1,
&right.mdir, NULL, NULL) => LFS_ERR_NOENT;
lfsr_mdir_commit(&lfs, &right.mdir, LFSR_RATTRS(
LFSR_RATTR_NAME(LFSR_TAG_REG, +1, 0, "e", 1))) => 0;
assert(right.mdir.rbyd.weight == 3);
lfsr_omdir_open(&lfs, &right);
// create 2 large entries that needs to be uninlined and split
uint8_t buffer[SIZE];
buffer[0] = '\0';
memset(buffer+1, 'b', SIZE-1);
lfsr_mdir_t mdir;
lfsr_mtree_namelookup(&lfs, 0, (const char*)buffer+1, SIZE-1,
&mdir, NULL, NULL) => LFS_ERR_NOENT;
lfsr_mdir_commit(&lfs, &mdir, LFSR_RATTRS(
LFSR_RATTR_NAME(
LFSR_TAG_REG, +1,
0, (const char*)buffer+1, SIZE-1))) => 0;
assert(mdir.rbyd.weight == 4);
memset(buffer+1, 'd', SIZE-1);
lfsr_mtree_namelookup(&lfs, 0, (const char*)buffer+1, SIZE-1,
&mdir, NULL, NULL) => LFS_ERR_NOENT;
lfsr_mdir_commit(&lfs, &mdir, LFSR_RATTRS(
LFSR_RATTR_NAME(
LFSR_TAG_REG, +1,
0, (const char*)buffer+1, SIZE-1))) => 0;
assert(mdir.rbyd.weight == 5);
// force mroot to compact
lfs.mroot.rbyd.eoff = -1;
lfsr_mdir_commit(&lfs, &lfs.mroot, NULL, 0) => 0;
// now add another large entry to an mdir, forcing a split
memset(buffer+1, 'c', SIZE-1);
lfsr_mtree_namelookup(&lfs, 0, (const char*)buffer+1, SIZE-1,
&mdir, NULL, NULL) => LFS_ERR_NOENT;
lfsr_mdir_commit(&lfs, &mdir, LFSR_RATTRS(
LFSR_RATTR_NAME(
LFSR_TAG_REG, +1,
0, (const char*)buffer+1, SIZE-1))) => 0;
assert(mdir.rbyd.weight == 4);
// force mdir to compact
mdir.rbyd.eoff = -1;
lfsr_mdir_commit(&lfs, &mdir, NULL, 0) => 0;
// assert mdir was split correctly
assert(lfs.mtree.root.weight == (3 << lfs.mbits));
// assert mroot still has no entries
assert(lfs.mroot.rbyd.weight == 0);
// now remove the middle entry, forcing a drop
lfsr_mdir_commit(&lfs, &mdir, LFSR_RATTRS(
LFSR_RATTR(LFSR_TAG_RM, -1))) => 0;
assert(mdir.rbyd.weight == 0);
// assert mdir was dropped correctly
assert(lfs.mtree.root.weight == (2 << lfs.mbits));
// assert mroot still has no entries
assert(lfs.mroot.rbyd.weight == 0);
// assert that our neighbors were updated correctly
lfsr_mtree_namelookup(&lfs, 0, "a", 1,
&mdir, NULL, NULL) => 0;
assert(left.mdir.mid == mdir.mid);
assert(lfsr_mdir_cmp(&left.mdir, &mdir) == 0);
assert(left.mdir.rbyd.trunk == mdir.rbyd.trunk);
assert(left.mdir.rbyd.cksum == mdir.rbyd.cksum);
lfsr_mtree_namelookup(&lfs, 0, "e", 1,
&mdir, NULL, NULL) => 0;
assert(right.mdir.mid == mdir.mid);
assert(lfsr_mdir_cmp(&right.mdir, &mdir) == 0);
assert(right.mdir.rbyd.trunk == mdir.rbyd.trunk);
assert(right.mdir.rbyd.cksum == mdir.rbyd.cksum);
lfsr_omdir_close(&lfs, &left);
lfsr_omdir_close(&lfs, &right);
lfsr_unmount(&lfs) => 0;
'''
## mtree traversal ##
# test specific corner cases
[cases.test_mtree_traversal]
defines.CKMETA = [false, true]
in = 'lfs.c'
code = '''
lfs_t lfs;
lfsr_format(&lfs, LFS_F_RDWR | F_FLAGS, CFG) => 0;
lfsr_mount(&lfs, LFS_M_RDWR | M_FLAGS, CFG) => 0;
lfs_alloc_ckpoint(&lfs);
// insert at least one entry
lfsr_mdir_t mdir;
lfsr_mtree_namelookup(&lfs, 0, "a", 1,
&mdir, NULL, NULL) => LFS_ERR_NOENT;
lfsr_mdir_commit(&lfs, &mdir, LFSR_RATTRS(
LFSR_RATTR_NAME(LFSR_TAG_REG, +1, 0, "a", 1))) => 0;
assert(mdir.rbyd.weight == 2);
// test that we can traverse the tree, keeping track of all blocks we see
uint8_t *seen = malloc((BLOCK_COUNT+7)/8);
memset(seen, 0, (BLOCK_COUNT+7)/8);
lfsr_traversal_t t;
lfsr_traversal_init(&t,
LFS_T_MTREEONLY
| ((CKMETA) ? LFS_T_CKMETA : 0));
for (lfs_block_t i = 0;; i++) {
// a bit hacky, but this catches infinite loops
assert(i < 2*BLOCK_COUNT);
lfsr_tag_t tag;
lfsr_bptr_t bptr;
int err = lfsr_mtree_traverse(&lfs, &t,
&tag, &bptr);
assert(!err || err == LFS_ERR_NOENT);
if (err == LFS_ERR_NOENT) {
break;
}
if (tag == LFSR_TAG_MDIR) {
lfsr_mdir_t *mdir = (lfsr_mdir_t*)bptr.data.u.buffer;
printf("traversal: 0x%x mdir 0x{%x,%x}\n",
tag,
mdir->rbyd.blocks[0],
mdir->rbyd.blocks[1]);
// keep track of seen blocks
seen[mdir->rbyd.blocks[1] / 8] |= 1 << (mdir->rbyd.blocks[1] % 8);
seen[mdir->rbyd.blocks[0] / 8] |= 1 << (mdir->rbyd.blocks[0] % 8);
} else if (tag == LFSR_TAG_BRANCH) {
lfsr_rbyd_t *rbyd = (lfsr_rbyd_t*)bptr.data.u.buffer;
printf("traversal: 0x%x btree 0x%x.%x\n",
tag,
rbyd->blocks[0], rbyd->trunk);
// keep track of seen blocks
seen[rbyd->blocks[0] / 8] |= 1 << (rbyd->blocks[0] % 8);
} else {
// this shouldn't happen
printf("traversal: 0x%x\n", tag);
assert(false);
}
}
// if traversal worked, we should be able to clobber all other blocks
uint8_t clobber_buf[BLOCK_SIZE];
memset(clobber_buf, 0xcc, BLOCK_SIZE);
for (lfs_block_t block = 0; block < BLOCK_COUNT; block++) {
if (!(seen[block / 8] & (1 << (block % 8)))) {
CFG->erase(CFG, block) => 0;
CFG->prog(CFG, block, 0, clobber_buf, BLOCK_SIZE) => 0;
}
}
free(seen);
lfsr_data_t data;
// and the tree should still work
// assert that our entry is still in the mtree
uint8_t buffer[256];
lfsr_mtree_namelookup(&lfs, 0, "a", 1,
&mdir, NULL, NULL) => 0;
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_REG, NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, sizeof(buffer)) => 2;
assert(memcmp(buffer, "\0a", 2) == 0);
// check things stay sane after remount
lfsr_unmount(&lfs) => 0;
lfsr_mount(&lfs, LFS_M_RDWR | M_FLAGS, CFG) => 0;
// assert that our entry is still in the mtree
lfsr_mtree_namelookup(&lfs, 0, "a", 1,
&mdir, NULL, NULL) => 0;
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_REG, NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, sizeof(buffer)) => 2;
assert(memcmp(buffer, "\0a", 2) == 0);
lfsr_unmount(&lfs) => 0;
'''
[cases.test_mtree_traversal_uninline]
defines.CKMETA = [false, true]
# this should be set so only one entry can fit in a metadata block
defines.SIZE = 'BLOCK_SIZE / 4'
in = 'lfs.c'
code = '''
lfs_t lfs;
lfsr_format(&lfs, LFS_F_RDWR | F_FLAGS, CFG) => 0;
lfsr_mount(&lfs, LFS_M_RDWR | M_FLAGS, CFG) => 0;
lfs_alloc_ckpoint(&lfs);
lfsr_data_t data;
// create a 2 large rattrs that needs to be uninlined
uint8_t buffer[SIZE];
memset(buffer, 'a', SIZE);
lfsr_mdir_commit(&lfs, &lfs.mroot, LFSR_RATTRS(
LFSR_RATTR_BUF(LFSR_TAG_ATTR(1), 0, buffer, SIZE))) => 0;
memset(buffer, 'b', SIZE);
lfsr_mdir_t mdir;
lfsr_mtree_lookup(&lfs, 0, &mdir) => 0;
lfsr_mdir_commit(&lfs, &mdir, LFSR_RATTRS(
LFSR_RATTR_BUF(LFSR_TAG_ATTR(1), 0, buffer, SIZE))) => 0;
// force mroot to compact
lfs.mroot.rbyd.eoff = -1;
lfsr_mdir_commit(&lfs, &lfs.mroot, NULL, 0) => 0;
// assert mdirs were unininlined
assert(lfs.mtree.root.weight == (1 << lfs.mbits));
// assert mroot now has no entries
assert(lfs.mroot.rbyd.weight == 0);
// test that we can traverse the tree, keeping track of all blocks we see
uint8_t *seen = malloc((BLOCK_COUNT+7)/8);
memset(seen, 0, (BLOCK_COUNT+7)/8);
lfsr_traversal_t t;
lfsr_traversal_init(&t,
LFS_T_MTREEONLY
| ((CKMETA) ? LFS_T_CKMETA : 0));
for (lfs_block_t i = 0;; i++) {
// a bit hacky, but this catches infinite loops
assert(i < 2*BLOCK_COUNT);
lfsr_tag_t tag;
lfsr_bptr_t bptr;
int err = lfsr_mtree_traverse(&lfs, &t,
&tag, &bptr);
assert(!err || err == LFS_ERR_NOENT);
if (err == LFS_ERR_NOENT) {
break;
}
if (tag == LFSR_TAG_MDIR) {
lfsr_mdir_t *mdir = (lfsr_mdir_t*)bptr.data.u.buffer;
printf("traversal: 0x%x mdir 0x{%x,%x}\n",
tag,
mdir->rbyd.blocks[0],
mdir->rbyd.blocks[1]);
// keep track of seen blocks
seen[mdir->rbyd.blocks[1] / 8] |= 1 << (mdir->rbyd.blocks[1] % 8);
seen[mdir->rbyd.blocks[0] / 8] |= 1 << (mdir->rbyd.blocks[0] % 8);
} else if (tag == LFSR_TAG_BRANCH) {
lfsr_rbyd_t *rbyd = (lfsr_rbyd_t*)bptr.data.u.buffer;
printf("traversal: 0x%x btree 0x%x.%x\n",
tag,
rbyd->blocks[0], rbyd->trunk);
// keep track of seen blocks
seen[rbyd->blocks[0] / 8] |= 1 << (rbyd->blocks[0] % 8);
} else {
// this shouldn't happen
printf("traversal: 0x%x\n", tag);
assert(false);
}
}
// if traversal worked, we should be able to clobber all other blocks
uint8_t clobber_buf[BLOCK_SIZE];
memset(clobber_buf, 0xcc, BLOCK_SIZE);
for (lfs_block_t block = 0; block < BLOCK_COUNT; block++) {
if (!(seen[block / 8] & (1 << (block % 8)))) {
CFG->erase(CFG, block) => 0;
CFG->prog(CFG, block, 0, clobber_buf, BLOCK_SIZE) => 0;
}
}
free(seen);
// and the tree should still work
// assert mdirs were unininlined
assert(lfs.mtree.root.weight == (1 << lfs.mbits));
// assert mroot now has no entries
assert(lfs.mroot.rbyd.weight == 0);
// assert that our rattrs are still in the mroot/mtree
lfsr_mdir_lookup(&lfs, &lfs.mroot, LFSR_TAG_ATTR(1), NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, SIZE) => SIZE;
assert(buffer[0] == 'a');
lfsr_mtree_lookup(&lfs, 0, &mdir) => 0;
assert(mdir.rbyd.weight == 1);
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_ATTR(1), NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, SIZE) => SIZE;
assert(buffer[0] == 'b');
// check things stay sane after remount
lfsr_unmount(&lfs) => 0;
lfsr_mount(&lfs, LFS_M_RDWR | M_FLAGS, CFG) => 0;
// assert mdirs were unininlined
assert(lfs.mtree.root.weight == (1 << lfs.mbits));
// assert mroot now has no entries
assert(lfs.mroot.rbyd.weight == 0);
// assert that our rattrs are still in the mroot/mtree
lfsr_mdir_lookup(&lfs, &lfs.mroot, LFSR_TAG_ATTR(1), NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, SIZE) => SIZE;
assert(buffer[0] == 'a');
lfsr_mtree_lookup(&lfs, 0, &mdir) => 0;
assert(mdir.rbyd.weight == 1);
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_ATTR(1), NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, SIZE) => SIZE;
assert(buffer[0] == 'b');
lfsr_unmount(&lfs) => 0;
'''
[cases.test_mtree_traversal_uninline_split]
defines.CKMETA = [false, true]
# this should be set so only one entry can fit in a metadata block
defines.SIZE = 'BLOCK_SIZE / 4'
in = 'lfs.c'
code = '''
lfs_t lfs;
lfsr_format(&lfs, LFS_F_RDWR | F_FLAGS, CFG) => 0;
lfsr_mount(&lfs, LFS_M_RDWR | M_FLAGS, CFG) => 0;
lfs_alloc_ckpoint(&lfs);
lfsr_data_t data;
// create 2 large entries that needs to be uninlined and split
uint8_t buffer[SIZE];
buffer[0] = '\0';
memset(buffer+1, 'a', SIZE-1);
lfsr_mdir_t mdir;
lfsr_mtree_namelookup(&lfs, 0, (const char*)buffer+1, SIZE-1,
&mdir, NULL, NULL) => LFS_ERR_NOENT;
lfsr_mdir_commit(&lfs, &mdir, LFSR_RATTRS(
LFSR_RATTR_NAME(
LFSR_TAG_REG, +1,
0, (const char*)buffer+1, SIZE-1))) => 0;
assert(mdir.rbyd.weight == 2);
memset(buffer+1, 'b', SIZE-1);
lfsr_mtree_namelookup(&lfs, 0, (const char*)buffer+1, SIZE-1,
&mdir, NULL, NULL) => LFS_ERR_NOENT;
lfsr_mdir_commit(&lfs, &mdir, LFSR_RATTRS(
LFSR_RATTR_NAME(
LFSR_TAG_REG, +1,
0, (const char*)buffer+1, SIZE-1))) => 0;
assert(mdir.rbyd.weight == 3);
// force mroot to compact
lfs.mroot.rbyd.eoff = -1;
lfsr_mdir_commit(&lfs, &lfs.mroot, NULL, 0) => 0;
// assert mdirs were unininlined and split
assert(lfs.mtree.root.weight == (2 << lfs.mbits));
// assert mroot now has no entries
assert(lfs.mroot.rbyd.weight == 0);
// test that we can traverse the tree, keeping track of all blocks we see
uint8_t *seen = malloc((BLOCK_COUNT+7)/8);
memset(seen, 0, (BLOCK_COUNT+7)/8);
lfsr_traversal_t t;
lfsr_traversal_init(&t,
LFS_T_MTREEONLY
| ((CKMETA) ? LFS_T_CKMETA : 0));
for (lfs_block_t i = 0;; i++) {
// a bit hacky, but this catches infinite loops
assert(i < 2*BLOCK_COUNT);
lfsr_tag_t tag;
lfsr_bptr_t bptr;
int err = lfsr_mtree_traverse(&lfs, &t,
&tag, &bptr);
assert(!err || err == LFS_ERR_NOENT);
if (err == LFS_ERR_NOENT) {
break;
}
if (tag == LFSR_TAG_MDIR) {
lfsr_mdir_t *mdir = (lfsr_mdir_t*)bptr.data.u.buffer;
printf("traversal: 0x%x mdir 0x{%x,%x}\n",
tag,
mdir->rbyd.blocks[0],
mdir->rbyd.blocks[1]);
// keep track of seen blocks
seen[mdir->rbyd.blocks[1] / 8] |= 1 << (mdir->rbyd.blocks[1] % 8);
seen[mdir->rbyd.blocks[0] / 8] |= 1 << (mdir->rbyd.blocks[0] % 8);
} else if (tag == LFSR_TAG_BRANCH) {
lfsr_rbyd_t *rbyd = (lfsr_rbyd_t*)bptr.data.u.buffer;
printf("traversal: 0x%x btree 0x%x.%x\n",
tag,
rbyd->blocks[0], rbyd->trunk);
// keep track of seen blocks
seen[rbyd->blocks[0] / 8] |= 1 << (rbyd->blocks[0] % 8);
} else {
// this shouldn't happen
printf("traversal: 0x%x\n", tag);
assert(false);
}
}
// if traversal worked, we should be able to clobber all other blocks
uint8_t clobber_buf[BLOCK_SIZE];
memset(clobber_buf, 0xcc, BLOCK_SIZE);
for (lfs_block_t block = 0; block < BLOCK_COUNT; block++) {
if (!(seen[block / 8] & (1 << (block % 8)))) {
CFG->erase(CFG, block) => 0;
CFG->prog(CFG, block, 0, clobber_buf, BLOCK_SIZE) => 0;
}
}
free(seen);
// and the tree should still work
// assert mdirs were unininlined and split
assert(lfs.mtree.root.weight == (2 << lfs.mbits));
// assert mroot now has no entries
assert(lfs.mroot.rbyd.weight == 0);
// assert that our entries are still in the mtree
lfsr_mtree_lookup(&lfs, (0 << lfs.mbits)+1, &mdir) => 0;
assert(mdir.rbyd.weight == 2);
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_REG, NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, SIZE) => SIZE;
assert(buffer[1] == 'a');
lfsr_mtree_lookup(&lfs, (1 << lfs.mbits)+0, &mdir) => 0;
assert(mdir.rbyd.weight == 1);
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_REG, NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, SIZE) => SIZE;
assert(buffer[1] == 'b');
// check things stay sane after remount
lfsr_unmount(&lfs) => 0;
lfsr_mount(&lfs, LFS_M_RDWR | M_FLAGS, CFG) => 0;
// assert mdirs were unininlined and split
assert(lfs.mtree.root.weight == (2 << lfs.mbits));
// assert mroot now has no entries
assert(lfs.mroot.rbyd.weight == 0);
// assert that our entries are still in the mtree
lfsr_mtree_lookup(&lfs, (0 << lfs.mbits)+1, &mdir) => 0;
assert(mdir.rbyd.weight == 2);
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_REG, NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, SIZE) => SIZE;
assert(buffer[1] == 'a');
lfsr_mtree_lookup(&lfs, (1 << lfs.mbits)+0, &mdir) => 0;
assert(mdir.rbyd.weight == 1);
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_REG, NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, SIZE) => SIZE;
assert(buffer[1] == 'b');
lfsr_unmount(&lfs) => 0;
'''
[cases.test_mtree_traversal_split]
defines.CKMETA = [false, true]
# this should be set so only one entry can fit in a metadata block
defines.SIZE = 'BLOCK_SIZE / 4'
in = 'lfs.c'
code = '''
lfs_t lfs;
lfsr_format(&lfs, LFS_F_RDWR | F_FLAGS, CFG) => 0;
lfsr_mount(&lfs, LFS_M_RDWR | M_FLAGS, CFG) => 0;
lfs_alloc_ckpoint(&lfs);
lfsr_data_t data;
// create 2 large entries that needs to be uninlined and split
uint8_t buffer[SIZE];
buffer[0] = '\0';
memset(buffer+1, 'a', SIZE-1);
lfsr_mdir_t mdir;
lfsr_mtree_namelookup(&lfs, 0, (const char*)buffer+1, SIZE-1,
&mdir, NULL, NULL) => LFS_ERR_NOENT;
lfsr_mdir_commit(&lfs, &mdir, LFSR_RATTRS(
LFSR_RATTR_NAME(
LFSR_TAG_REG, +1,
0, (const char*)buffer+1, SIZE-1))) => 0;
assert(mdir.rbyd.weight == 2);
memset(buffer+1, 'b', SIZE-1);
lfsr_mtree_namelookup(&lfs, 0, (const char*)buffer+1, SIZE-1,
&mdir, NULL, NULL) => LFS_ERR_NOENT;
lfsr_mdir_commit(&lfs, &mdir, LFSR_RATTRS(
LFSR_RATTR_NAME(
LFSR_TAG_REG, +1,
0, (const char*)buffer+1, SIZE-1))) => 0;
assert(mdir.rbyd.weight == 3);
// force mroot to compact
lfs.mroot.rbyd.eoff = -1;
lfsr_mdir_commit(&lfs, &lfs.mroot, NULL, 0) => 0;
// assert mdirs were unininlined and split
assert(lfs.mtree.root.weight == (2 << lfs.mbits));
// assert mroot now has no entries
assert(lfs.mroot.rbyd.weight == 0);
// now add another large entry to an mdir, forcing a split
memset(buffer+1, 'c', SIZE-1);
lfsr_mtree_namelookup(&lfs, 0, (const char*)buffer+1, SIZE-1,
&mdir, NULL, NULL) => LFS_ERR_NOENT;
lfsr_mdir_commit(&lfs, &mdir, LFSR_RATTRS(
LFSR_RATTR_NAME(
LFSR_TAG_REG, +1,
0, (const char*)buffer+1, SIZE-1))) => 0;
assert(mdir.rbyd.weight == 2);
// force mdir to compact
mdir.rbyd.eoff = -1;
lfsr_mdir_commit(&lfs, &mdir, NULL, 0) => 0;
// assert mdir was split correctly
assert(lfs.mtree.root.weight == (3 << lfs.mbits));
// assert mroot still has no entries
assert(lfs.mroot.rbyd.weight == 0);
// test that we can traverse the tree, keeping track of all blocks we see
uint8_t *seen = malloc((BLOCK_COUNT+7)/8);
memset(seen, 0, (BLOCK_COUNT+7)/8);
lfsr_traversal_t t;
lfsr_traversal_init(&t,
LFS_T_MTREEONLY
| ((CKMETA) ? LFS_T_CKMETA : 0));
for (lfs_block_t i = 0;; i++) {
// a bit hacky, but this catches infinite loops
assert(i < 2*BLOCK_COUNT);
lfsr_tag_t tag;
lfsr_bptr_t bptr;
int err = lfsr_mtree_traverse(&lfs, &t,
&tag, &bptr);
assert(!err || err == LFS_ERR_NOENT);
if (err == LFS_ERR_NOENT) {
break;
}
if (tag == LFSR_TAG_MDIR) {
lfsr_mdir_t *mdir = (lfsr_mdir_t*)bptr.data.u.buffer;
printf("traversal: 0x%x mdir 0x{%x,%x}\n",
tag,
mdir->rbyd.blocks[0],
mdir->rbyd.blocks[1]);
// keep track of seen blocks
seen[mdir->rbyd.blocks[1] / 8] |= 1 << (mdir->rbyd.blocks[1] % 8);
seen[mdir->rbyd.blocks[0] / 8] |= 1 << (mdir->rbyd.blocks[0] % 8);
} else if (tag == LFSR_TAG_BRANCH) {
lfsr_rbyd_t *rbyd = (lfsr_rbyd_t*)bptr.data.u.buffer;
printf("traversal: 0x%x btree 0x%x.%x\n",
tag,
rbyd->blocks[0], rbyd->trunk);
// keep track of seen blocks
seen[rbyd->blocks[0] / 8] |= 1 << (rbyd->blocks[0] % 8);
} else {
// this shouldn't happen
printf("traversal: 0x%x\n", tag);
assert(false);
}
}
// if traversal worked, we should be able to clobber all other blocks
uint8_t clobber_buf[BLOCK_SIZE];
memset(clobber_buf, 0xcc, BLOCK_SIZE);
for (lfs_block_t block = 0; block < BLOCK_COUNT; block++) {
if (!(seen[block / 8] & (1 << (block % 8)))) {
CFG->erase(CFG, block) => 0;
CFG->prog(CFG, block, 0, clobber_buf, BLOCK_SIZE) => 0;
}
}
free(seen);
// and the tree should still work
// assert mdir was split correctly
assert(lfs.mtree.root.weight == (3 << lfs.mbits));
// assert mroot still has no entries
assert(lfs.mroot.rbyd.weight == 0);
// assert that our entries are still in the mtree
lfsr_mtree_lookup(&lfs, (0 << lfs.mbits)+1, &mdir) => 0;
assert(mdir.rbyd.weight == 2);
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_REG, NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, SIZE) => SIZE;
assert(buffer[1] == 'a');
lfsr_mtree_lookup(&lfs, (1 << lfs.mbits)+0, &mdir) => 0;
assert(mdir.rbyd.weight == 1);
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_REG, NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, SIZE) => SIZE;
assert(buffer[1] == 'b');
lfsr_mtree_lookup(&lfs, (2 << lfs.mbits)+0, &mdir) => 0;
assert(mdir.rbyd.weight == 1);
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_REG, NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, SIZE) => SIZE;
assert(buffer[1] == 'c');
// check things stay sane after remount
lfsr_unmount(&lfs) => 0;
lfsr_mount(&lfs, LFS_M_RDWR | M_FLAGS, CFG) => 0;
// assert mdir was split correctly
assert(lfs.mtree.root.weight == (3 << lfs.mbits));
// assert mroot still has no entries
assert(lfs.mroot.rbyd.weight == 0);
// assert that our entries are still in the mtree
lfsr_mtree_lookup(&lfs, (0 << lfs.mbits)+1, &mdir) => 0;
assert(mdir.rbyd.weight == 2);
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_REG, NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, SIZE) => SIZE;
assert(buffer[1] == 'a');
lfsr_mtree_lookup(&lfs, (1 << lfs.mbits)+0, &mdir) => 0;
assert(mdir.rbyd.weight == 1);
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_REG, NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, SIZE) => SIZE;
assert(buffer[1] == 'b');
lfsr_mtree_lookup(&lfs, (2 << lfs.mbits)+0, &mdir) => 0;
assert(mdir.rbyd.weight == 1);
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_REG, NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, SIZE) => SIZE;
assert(buffer[1] == 'c');
lfsr_unmount(&lfs) => 0;
'''
[cases.test_mtree_traversal_extend]
defines.CKMETA = [false, true]
# make it so blocks relocate every two compacts
defines.BLOCK_RECYCLES = 0
in = 'lfs.c'
code = '''
lfs_t lfs;
lfsr_format(&lfs, LFS_F_RDWR | F_FLAGS, CFG) => 0;
lfsr_mount(&lfs, LFS_M_RDWR | M_FLAGS, CFG) => 0;
lfs_alloc_ckpoint(&lfs);
// insert at least one entry
lfsr_mdir_t mdir;
lfsr_mtree_namelookup(&lfs, 0, "a", 1,
&mdir, NULL, NULL) => LFS_ERR_NOENT;
lfsr_mdir_commit(&lfs, &mdir, LFSR_RATTRS(
LFSR_RATTR_NAME(LFSR_TAG_REG, +1, 0, "a", 1))) => 0;
assert(mdir.rbyd.weight == 2);
// force mroot to compact twice, this should extend the mroot
lfsr_mdir_t old_mroot = lfs.mroot;
lfs.mroot.rbyd.eoff = -1;
lfsr_mdir_commit(&lfs, &lfs.mroot, NULL, 0) => 0;
lfs.mroot.rbyd.eoff = -1;
lfsr_mdir_commit(&lfs, &lfs.mroot, NULL, 0) => 0;
// assert we relocated
assert(lfsr_mdir_cmp(&old_mroot, &lfs.mroot) != 0);
// test that we can traverse the tree, keeping track of all blocks we see
uint8_t *seen = malloc((BLOCK_COUNT+7)/8);
memset(seen, 0, (BLOCK_COUNT+7)/8);
lfsr_traversal_t t;
lfsr_traversal_init(&t,
LFS_T_MTREEONLY
| ((CKMETA) ? LFS_T_CKMETA : 0));
for (lfs_block_t i = 0;; i++) {
// a bit hacky, but this catches infinite loops
assert(i < 2*BLOCK_COUNT);
lfsr_tag_t tag;
lfsr_bptr_t bptr;
int err = lfsr_mtree_traverse(&lfs, &t,
&tag, &bptr);
assert(!err || err == LFS_ERR_NOENT);
if (err == LFS_ERR_NOENT) {
break;
}
if (tag == LFSR_TAG_MDIR) {
lfsr_mdir_t *mdir = (lfsr_mdir_t*)bptr.data.u.buffer;
printf("traversal: 0x%x mdir 0x{%x,%x}\n",
tag,
mdir->rbyd.blocks[0],
mdir->rbyd.blocks[1]);
// keep track of seen blocks
seen[mdir->rbyd.blocks[1] / 8]
|= 1 << (mdir->rbyd.blocks[1] % 8);
seen[mdir->rbyd.blocks[0] / 8]
|= 1 << (mdir->rbyd.blocks[0] % 8);
} else if (tag == LFSR_TAG_BRANCH) {
lfsr_rbyd_t *rbyd = (lfsr_rbyd_t*)bptr.data.u.buffer;
printf("traversal: 0x%x btree 0x%x.%x\n",
tag,
rbyd->blocks[0], rbyd->trunk);
// keep track of seen blocks
seen[rbyd->blocks[0] / 8]
|= 1 << (rbyd->blocks[0] % 8);
} else {
// this shouldn't happen
printf("traversal: 0x%x\n", tag);
assert(false);
}
}
// if traversal worked, we should be able to clobber all other blocks
uint8_t clobber_buf[BLOCK_SIZE];
memset(clobber_buf, 0xcc, BLOCK_SIZE);
for (lfs_block_t block = 0; block < BLOCK_COUNT; block++) {
if (!(seen[block / 8] & (1 << (block % 8)))) {
CFG->erase(CFG, block) => 0;
CFG->prog(CFG, block, 0, clobber_buf, BLOCK_SIZE) => 0;
}
}
free(seen);
lfsr_data_t data;
// and the tree should still work
// assert that our entry is still in the mtree
uint8_t buffer[256];
lfsr_mtree_namelookup(&lfs, 0, "a", 1,
&mdir, NULL, NULL) => 0;
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_REG, NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, sizeof(buffer)) => 2;
assert(memcmp(buffer, "\0a", 2) == 0);
// check things stay sane after remount
lfsr_unmount(&lfs) => 0;
lfsr_mount(&lfs, LFS_M_RDWR | M_FLAGS, CFG) => 0;
// assert that our entry is still in the mtree
lfsr_mtree_namelookup(&lfs, 0, "a", 1,
&mdir, NULL, NULL) => 0;
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_REG, NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, sizeof(buffer)) => 2;
assert(memcmp(buffer, "\0a", 2) == 0);
lfsr_unmount(&lfs) => 0;
'''
# larger traversal tests
[cases.test_mtree_traversal_many]
defines.N = [5, 10, 20, 40, 80, 160, 320]
defines.CKMETA = [false, true]
defines.FORCE_COMPACTION = [false, true]
in = 'lfs.c'
code = '''
lfs_t lfs;
lfsr_format(&lfs, LFS_F_RDWR | F_FLAGS, CFG) => 0;
lfsr_mount(&lfs, LFS_M_RDWR | M_FLAGS, CFG) => 0;
lfs_alloc_ckpoint(&lfs);
// create entries
for (lfs_size_t i = 0; i < N; i++) {
char name[256];
name[0] = '\0';
sprintf(name+1, "%03x", i);
lfsr_mdir_t mdir;
lfsr_mtree_namelookup(&lfs, 0, name+1, 3,
&mdir, NULL, NULL) => LFS_ERR_NOENT;
// force a compaction?
if (FORCE_COMPACTION) {
lfs.mroot.rbyd.eoff = -1;
mdir.rbyd.eoff = -1;
}
lfsr_mdir_commit(&lfs, &mdir, LFSR_RATTRS(
LFSR_RATTR_NAME(LFSR_TAG_REG, +1, 0, name+1, 3))) => 0;
lfsr_data_t data;
uint8_t buffer[256];
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_REG, NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, sizeof(buffer)) => 4;
assert(memcmp(buffer, name, 4) == 0);
}
// test that we can traverse the tree, keeping track of all blocks we see
uint8_t *seen = malloc((BLOCK_COUNT+7)/8);
memset(seen, 0, (BLOCK_COUNT+7)/8);
lfsr_traversal_t t;
lfsr_traversal_init(&t,
LFS_T_MTREEONLY
| ((CKMETA) ? LFS_T_CKMETA : 0));
for (lfs_block_t i = 0;; i++) {
// a bit hacky, but this catches infinite loops
assert(i < 2*BLOCK_COUNT);
lfsr_tag_t tag;
lfsr_bptr_t bptr;
int err = lfsr_mtree_traverse(&lfs, &t,
&tag, &bptr);
assert(!err || err == LFS_ERR_NOENT);
if (err == LFS_ERR_NOENT) {
break;
}
if (tag == LFSR_TAG_MDIR) {
lfsr_mdir_t *mdir = (lfsr_mdir_t*)bptr.data.u.buffer;
printf("traversal: 0x%x mdir 0x{%x,%x}\n",
tag,
mdir->rbyd.blocks[0],
mdir->rbyd.blocks[1]);
// keep track of seen blocks
seen[mdir->rbyd.blocks[1] / 8]
|= 1 << (mdir->rbyd.blocks[1] % 8);
seen[mdir->rbyd.blocks[0] / 8]
|= 1 << (mdir->rbyd.blocks[0] % 8);
} else if (tag == LFSR_TAG_BRANCH) {
lfsr_rbyd_t *rbyd = (lfsr_rbyd_t*)bptr.data.u.buffer;
printf("traversal: 0x%x btree 0x%x.%x\n",
tag,
rbyd->blocks[0], rbyd->trunk);
// keep track of seen blocks
seen[rbyd->blocks[0] / 8]
|= 1 << (rbyd->blocks[0] % 8);
} else {
// this shouldn't happen
printf("traversal: 0x%x\n", tag);
assert(false);
}
}
// if traversal worked, we should be able to clobber all other blocks
uint8_t clobber_buf[BLOCK_SIZE];
memset(clobber_buf, 0xcc, BLOCK_SIZE);
for (lfs_block_t block = 0; block < BLOCK_COUNT; block++) {
if (!(seen[block / 8] & (1 << (block % 8)))) {
CFG->erase(CFG, block) => 0;
CFG->prog(CFG, block, 0, clobber_buf, BLOCK_SIZE) => 0;
}
}
free(seen);
// and the tree should still work
// try looking up each entry
lfsr_mdir_t mdir;
lfsr_mtree_lookup(&lfs, 0, &mdir) => 0;
lfsr_data_t data;
uint8_t buffer[256];
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_BOOKMARK, NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, sizeof(buffer)) => 1;
for (lfs_size_t i = 0; i < N; i++) {
char name[256];
name[0] = '\0';
sprintf(name+1, "%03x", i);
mdir.mid += 1;
if (lfsr_mrid(&lfs, mdir.mid) >= (lfsr_srid_t)mdir.rbyd.weight) {
lfsr_mtree_lookup(&lfs, lfsr_mbid(&lfs, mdir.mid) + 1,
&mdir) => 0;
}
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_REG, NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, sizeof(buffer)) => 4;
assert(memcmp(buffer, name, 4) == 0);
}
// check things stay sane after remount
lfsr_unmount(&lfs) => 0;
lfsr_mount(&lfs, LFS_M_RDWR | M_FLAGS, CFG) => 0;
// try looking up each entry
lfsr_mtree_lookup(&lfs, 0, &mdir) => 0;
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_BOOKMARK, NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, sizeof(buffer)) => 1;
for (lfs_size_t i = 0; i < N; i++) {
char name[256];
name[0] = '\0';
sprintf(name+1, "%03x", i);
mdir.mid += 1;
if (lfsr_mrid(&lfs, mdir.mid) >= (lfsr_srid_t)mdir.rbyd.weight) {
lfsr_mtree_lookup(&lfs, lfsr_mbid(&lfs, mdir.mid) + 1,
&mdir) => 0;
}
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_REG, NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, sizeof(buffer)) => 4;
assert(memcmp(buffer, name, 4) == 0);
}
lfsr_unmount(&lfs) => 0;
'''
[cases.test_mtree_traversal_fuzz]
defines.N = [5, 10, 20, 40, 80, 160]
defines.CKMETA = [false, true]
defines.FORCE_COMPACTION = [false, true]
defines.SEED = 'range(100)'
fuzz = 'SEED'
in = 'lfs.c'
code = '''
lfs_t lfs;
lfsr_format(&lfs, LFS_F_RDWR | F_FLAGS, CFG) => 0;
lfsr_mount(&lfs, LFS_M_RDWR | M_FLAGS, CFG) => 0;
lfs_alloc_ckpoint(&lfs);
bool sim[N];
for (lfs_size_t i = 0; i < N; i++) {
sim[i] = false;
}
uint32_t prng = SEED;
for (lfs_size_t i = 0; i < N; i++) {
// choose a pseudo-random name
lfs_size_t x = TEST_PRNG(&prng) % N;
// update sim
sim[x] = true;
// update mtree
char name[256];
name[0] = '\0';
sprintf(name+1, "%03x", x);
lfsr_mdir_t mdir;
int err = lfsr_mtree_namelookup(&lfs, 0, name+1, 3,
&mdir, NULL, NULL);
assert(!err || err == LFS_ERR_NOENT);
if (!err) {
continue;
}
// force a compaction?
if (FORCE_COMPACTION) {
lfs.mroot.rbyd.eoff = -1;
mdir.rbyd.eoff = -1;
}
lfsr_mdir_commit(&lfs, &mdir, LFSR_RATTRS(
LFSR_RATTR_NAME(LFSR_TAG_REG, +1, 0, name+1, 3))) => 0;
lfsr_data_t data;
// double check
uint8_t buffer[256];
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_REG, NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, sizeof(buffer)) => 4;
assert(memcmp(buffer, name, 4) == 0);
}
// test that we can traverse the tree, keeping track of all blocks
// we see
uint8_t *seen = malloc((BLOCK_COUNT+7)/8);
memset(seen, 0, (BLOCK_COUNT+7)/8);
lfsr_traversal_t t;
lfsr_traversal_init(&t,
LFS_T_MTREEONLY
| ((CKMETA) ? LFS_T_CKMETA : 0));
for (lfs_block_t i = 0;; i++) {
// a bit hacky, but this catches infinite loops
assert(i < 2*BLOCK_COUNT);
lfsr_tag_t tag;
lfsr_bptr_t bptr;
int err = lfsr_mtree_traverse(&lfs, &t,
&tag, &bptr);
assert(!err || err == LFS_ERR_NOENT);
if (err == LFS_ERR_NOENT) {
break;
}
if (tag == LFSR_TAG_MDIR) {
lfsr_mdir_t *mdir = (lfsr_mdir_t*)bptr.data.u.buffer;
printf("traversal: 0x%x mdir 0x{%x,%x}\n",
tag,
mdir->rbyd.blocks[0],
mdir->rbyd.blocks[1]);
// keep track of seen blocks
seen[mdir->rbyd.blocks[1] / 8]
|= 1 << (mdir->rbyd.blocks[1] % 8);
seen[mdir->rbyd.blocks[0] / 8]
|= 1 << (mdir->rbyd.blocks[0] % 8);
} else if (tag == LFSR_TAG_BRANCH) {
lfsr_rbyd_t *rbyd = (lfsr_rbyd_t*)bptr.data.u.buffer;
printf("traversal: 0x%x btree 0x%x.%x\n",
tag,
rbyd->blocks[0], rbyd->trunk);
// keep track of seen blocks
seen[rbyd->blocks[0] / 8]
|= 1 << (rbyd->blocks[0] % 8);
} else {
// this shouldn't happen
printf("traversal: 0x%x\n", tag);
assert(false);
}
}
// if traversal worked, we should be able to clobber all other blocks
uint8_t clobber_buf[BLOCK_SIZE];
memset(clobber_buf, 0xcc, BLOCK_SIZE);
for (lfs_block_t block = 0; block < BLOCK_COUNT; block++) {
if (!(seen[block / 8] & (1 << (block % 8)))) {
CFG->erase(CFG, block) => 0;
CFG->prog(CFG, block, 0, clobber_buf, BLOCK_SIZE) => 0;
}
}
free(seen);
// and the tree should still work
// try looking up each entry
lfsr_mdir_t mdir;
lfsr_mtree_lookup(&lfs, 0, &mdir) => 0;
lfsr_data_t data;
uint8_t buffer[256];
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_BOOKMARK, NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, sizeof(buffer)) => 1;
for (lfs_size_t i = 0; i < N; i++) {
char name[256];
name[0] = '\0';
sprintf(name+1, "%03x", i);
if (sim[i]) {
lfsr_mtree_namelookup(&lfs, 0, name+1, 3,
&mdir, NULL, NULL) => 0;
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_REG, NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, sizeof(buffer)) => 4;
assert(memcmp(buffer, name, 4) == 0);
} else {
lfsr_mtree_namelookup(&lfs, 0, name+1, 3,
&mdir, NULL, NULL) => LFS_ERR_NOENT;
}
}
// check things stay sane after remount
lfsr_unmount(&lfs) => 0;
lfsr_mount(&lfs, LFS_M_RDWR | M_FLAGS, CFG) => 0;
// try looking up each entry
lfsr_mtree_lookup(&lfs, 0, &mdir) => 0;
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_BOOKMARK, NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, sizeof(buffer)) => 1;
for (lfs_size_t i = 0; i < N; i++) {
char name[256];
name[0] = '\0';
sprintf(name+1, "%03x", i);
if (sim[i]) {
lfsr_mtree_namelookup(&lfs, 0, name+1, 3,
&mdir, NULL, NULL) => 0;
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_REG, NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, sizeof(buffer)) => 4;
assert(memcmp(buffer, name, 4) == 0);
} else {
lfsr_mtree_namelookup(&lfs, 0, name+1, 3,
&mdir, NULL, NULL) => LFS_ERR_NOENT;
}
}
lfsr_unmount(&lfs) => 0;
'''
## Cycle detection? ##
# test that our cycle detector at least works in common cases
[cases.test_mtree_traversal_mroot_cycle]
in = 'lfs.c'
code = '''
lfs_t lfs;
lfsr_format(&lfs, LFS_F_RDWR | F_FLAGS, CFG) => 0;
lfsr_mount(&lfs, LFS_M_RDWR | M_FLAGS, CFG) => 0;
lfs_alloc_ckpoint(&lfs);
lfsr_mdir_commit(&lfs, &lfs.mroot, LFSR_RATTRS(
LFSR_RATTR_MPTR(
LFSR_TAG_MROOT, 0,
LFSR_MPTR_MROOTANCHOR()))) => 0;
// technically, cycle detection only needs to work when we're validating
lfsr_traversal_t t;
lfsr_traversal_init(&t,
LFS_T_MTREEONLY | LFS_T_CKMETA);
for (lfs_block_t i = 0;; i++) {
// assert that we detect the cycle in a reasonable number of iterations
assert(i < 2*BLOCK_COUNT);
lfsr_tag_t tag;
lfsr_bptr_t bptr;
int err = lfsr_mtree_traverse(&lfs, &t,
&tag, &bptr);
assert(!err || err == LFS_ERR_CORRUPT);
if (err == LFS_ERR_CORRUPT) {
break;
}
if (tag == LFSR_TAG_MDIR) {
lfsr_mdir_t *mdir = (lfsr_mdir_t*)bptr.data.u.buffer;
printf("traversal: 0x%x mdir 0x{%x,%x}\n",
tag,
mdir->rbyd.blocks[0],
mdir->rbyd.blocks[1]);
} else if (tag == LFSR_TAG_BRANCH) {
lfsr_rbyd_t *rbyd = (lfsr_rbyd_t*)bptr.data.u.buffer;
printf("traversal: 0x%x btree 0x%x.%x\n",
tag,
rbyd->blocks[0], rbyd->trunk);
} else {
// this shouldn't happen
printf("traversal: 0x%x\n", tag);
assert(false);
}
}
lfsr_unmount(&lfs) => 0;
'''
## Truncate mroot tests ##
# test some that some tricky truncated tags are rejected correctly
[cases.test_mtree_truncated_tag]
defines.OVERFLOW = [-3, -2, -1, 0, 1, 2, 3, 4, 5]
in = 'lfs.c'
code = '''
// create a malformed mroot
uint8_t buffer[BLOCK_SIZE];
// fill with zeros to make parity checks easier
memset(buffer, 0, BLOCK_SIZE);
memcpy(&buffer[0], "evil", 4);
uint32_t cksum = lfs_crc32c(0, &buffer[0], 4);
// make sure we're not caught by magic checks
buffer[4+0] = ((uint8_t)lfs_parity(cksum) << 7)
| (uint8_t)(LFSR_TAG_MAGIC >> 8);
buffer[4+1] = (uint8_t)(LFSR_TAG_MAGIC >> 0);
buffer[4+2] = 0;
buffer[4+3] = 8;
memcpy(&buffer[4+4], "littlefs", 8);
cksum = lfs_crc32c(cksum ^ ((uint32_t)lfs_parity(cksum) << 7),
&buffer[4], 4+8);
// append a tag that overflows our block
lfs_size_t size = BLOCK_SIZE - (16+7) + OVERFLOW;
buffer[16+0] = ((uint8_t)lfs_parity(cksum) << 7)
| (uint8_t)(LFSR_TAG_ATTR >> 8);
buffer[16+1] = (uint8_t)(LFSR_TAG_ATTR >> 0);
buffer[16+2] = 0;
buffer[16+3] = 0x80 | (0x7f & (size >> 0));
buffer[16+4] = 0x80 | (0x7f & (size >> 7));
buffer[16+5] = 0x80 | (0x7f & (size >> 14));
buffer[16+6] = 0x00 | (0x7f & (size >> 21));
cksum = lfs_crc32c(cksum ^ ((uint32_t)lfs_parity(cksum) << 7),
&buffer[16], 7+size);
// make next tag look valid to make errors look more likely
if (OVERFLOW < 0) {
buffer[BLOCK_SIZE + OVERFLOW] = ((uint8_t)lfs_parity(cksum) << 7);
}
// write to both mroot blocks
for (int i = 0; i < 2; i++) {
CFG->erase(CFG, i) => 0;
CFG->prog(CFG, i, 0, buffer, BLOCK_SIZE) => 0;
}
// try to mount, this should fail
lfs_t lfs;
lfsr_mount(&lfs, LFS_M_RDWR | M_FLAGS, CFG) => LFS_ERR_CORRUPT;
'''
[cases.test_mtree_truncated_cksum]
defines.OVERFLOW = [1, 2, 3, 4]
defines.TRUNCATED_SIZE = [false, true]
in = 'lfs.c'
code = '''
// create a malformed mroot
uint8_t buffer[BLOCK_SIZE];
// fill with zeros to make parity checks easier
memset(buffer, 0, BLOCK_SIZE);
memcpy(&buffer[0], "evil", 4);
uint32_t cksum = lfs_crc32c(0, &buffer[0], 4);
// make sure we're not caught by magic checks
buffer[4+0] = ((uint8_t)lfs_parity(cksum) << 7)
| (uint8_t)(LFSR_TAG_MAGIC >> 8);
buffer[4+1] = (uint8_t)(LFSR_TAG_MAGIC >> 0);
buffer[4+2] = 0;
buffer[4+3] = 8;
memcpy(&buffer[4+4], "littlefs", 8);
cksum = lfs_crc32c(cksum ^ ((uint32_t)lfs_parity(cksum) << 7),
&buffer[4], 4+8);
// append a tag for padding
lfs_size_t size = BLOCK_SIZE - (16+7) - (7+4) + OVERFLOW;
buffer[16+0] = ((uint8_t)lfs_parity(cksum) << 7)
| (uint8_t)(LFSR_TAG_ATTR >> 8);
buffer[16+1] = (uint8_t)(LFSR_TAG_ATTR >> 0);
buffer[16+2] = 0;
buffer[16+3] = 0x80 | (0x7f & (size >> 0));
buffer[16+4] = 0x80 | (0x7f & (size >> 7));
buffer[16+5] = 0x80 | (0x7f & (size >> 14));
buffer[16+6] = 0x00 | (0x7f & (size >> 21));
cksum = lfs_crc32c(cksum ^ ((uint32_t)lfs_parity(cksum) << 7),
&buffer[16], 7+size);
// append a truncated cksum tag
lfs_off_t off = BLOCK_SIZE - (7+4) + OVERFLOW;
size = (TRUNCATED_SIZE) ? 4-OVERFLOW : 4;
buffer[off+0] = ((uint8_t)lfs_parity(cksum) << 7)
| (uint8_t)(LFSR_TAG_CKSUM >> 8);
buffer[off+1] = (uint8_t)(LFSR_TAG_CKSUM >> 0);
buffer[off+2] = 0;
buffer[off+3] = 0x80 | (0x7f & (size >> 0));
buffer[off+4] = 0x80 | (0x7f & (size >> 7));
buffer[off+5] = 0x80 | (0x7f & (size >> 14));
buffer[off+6] = 0x00 | (0x7f & (size >> 21));
// write to both mroot blocks
for (int i = 0; i < 2; i++) {
CFG->erase(CFG, i) => 0;
CFG->prog(CFG, i, 0, buffer, BLOCK_SIZE) => 0;
}
// try to mount, this should fail
lfs_t lfs;
lfsr_mount(&lfs, LFS_M_RDWR | M_FLAGS, CFG) => LFS_ERR_CORRUPT;
'''
[cases.test_mtree_truncated_ecksum]
defines.OVERFLOW = [-3, -2, -1, 0, 1, 2, 3, 4, 5]
defines.TRUNCATED_SIZE = [false, true]
in = 'lfs.c'
code = '''
// create a malformed mroot
uint8_t buffer[BLOCK_SIZE];
// fill with zeros to make parity checks easier
memset(buffer, 0, BLOCK_SIZE);
memcpy(&buffer[0], "evil", 4);
uint32_t cksum = lfs_crc32c(0, &buffer[0], 4);
// make sure we're not caught by magic checks
buffer[4+0] = ((uint8_t)lfs_parity(cksum) << 7)
| (uint8_t)(LFSR_TAG_MAGIC >> 8);
buffer[4+1] = (uint8_t)(LFSR_TAG_MAGIC >> 0);
buffer[4+2] = 0;
buffer[4+3] = 8;
memcpy(&buffer[4+4], "littlefs", 8);
cksum = lfs_crc32c(cksum ^ ((uint32_t)lfs_parity(cksum) << 7),
&buffer[4], 4+8);
// append a tag for padding
lfs_size_t size = BLOCK_SIZE - (16+7) - (7+5) + OVERFLOW;
buffer[16+0] = ((uint8_t)lfs_parity(cksum) << 7)
| (uint8_t)(LFSR_TAG_ATTR >> 8);
buffer[16+1] = (uint8_t)(LFSR_TAG_ATTR >> 0);
buffer[16+2] = 0;
buffer[16+3] = 0x80 | (0x7f & (size >> 0));
buffer[16+4] = 0x80 | (0x7f & (size >> 7));
buffer[16+5] = 0x80 | (0x7f & (size >> 14));
buffer[16+6] = 0x00 | (0x7f & (size >> 21));
cksum = lfs_crc32c(cksum ^ ((uint32_t)lfs_parity(cksum) << 7),
&buffer[16], 7+size);
// append a truncated ecksum tag
lfs_off_t off = BLOCK_SIZE - (7+5) + OVERFLOW;
size = (TRUNCATED_SIZE) ? 5-lfs_smax(OVERFLOW, 0) : 5;
buffer[off+0] = ((uint8_t)lfs_parity(cksum) << 7)
| (uint8_t)(LFSR_TAG_ECKSUM >> 8);
buffer[off+1] = (uint8_t)(LFSR_TAG_ECKSUM >> 0);
buffer[off+2] = 0;
buffer[off+3] = 0x80 | (0x7f & (size >> 0));
buffer[off+4] = 0x80 | (0x7f & (size >> 7));
buffer[off+5] = 0x80 | (0x7f & (size >> 14));
buffer[off+6] = 0x00 | (0x7f & (size >> 21));
cksum = lfs_crc32c(cksum ^ ((uint32_t)lfs_parity(cksum) << 7),
&buffer[16], 7+size);
// make next tag look valid to make errors look more likely
if (OVERFLOW < 0) {
buffer[BLOCK_SIZE + OVERFLOW] = ((uint8_t)lfs_parity(cksum) << 7);
}
// write to both mroot blocks
for (int i = 0; i < 2; i++) {
CFG->erase(CFG, i) => 0;
CFG->prog(CFG, i, 0, buffer, BLOCK_SIZE) => 0;
}
// try to mount, this should fail
lfs_t lfs;
lfsr_mount(&lfs, LFS_M_RDWR | M_FLAGS, CFG) => LFS_ERR_CORRUPT;
'''
[cases.test_mtree_truncated_gcksumdelta]
defines.OVERFLOW = [-3, -2, -1, 0, 1, 2, 3, 4]
defines.TRUNCATED_SIZE = [false, true]
in = 'lfs.c'
code = '''
// create a malformed mroot
uint8_t buffer[BLOCK_SIZE];
// fill with zeros to make parity checks easier
memset(buffer, 0, BLOCK_SIZE);
memcpy(&buffer[0], "evil", 4);
uint32_t cksum = lfs_crc32c(0, &buffer[0], 4);
// make sure we're not caught by magic checks
buffer[4+0] = ((uint8_t)lfs_parity(cksum) << 7)
| (uint8_t)(LFSR_TAG_MAGIC >> 8);
buffer[4+1] = (uint8_t)(LFSR_TAG_MAGIC >> 0);
buffer[4+2] = 0;
buffer[4+3] = 8;
memcpy(&buffer[4+4], "littlefs", 8);
cksum = lfs_crc32c(cksum ^ ((uint32_t)lfs_parity(cksum) << 7),
&buffer[4], 4+8);
// append a tag for padding
lfs_size_t size = BLOCK_SIZE - (16+7) - (7+4) + OVERFLOW;
buffer[16+0] = ((uint8_t)lfs_parity(cksum) << 7)
| (uint8_t)(LFSR_TAG_ATTR >> 8);
buffer[16+1] = (uint8_t)(LFSR_TAG_ATTR >> 0);
buffer[16+2] = 0;
buffer[16+3] = 0x80 | (0x7f & (size >> 0));
buffer[16+4] = 0x80 | (0x7f & (size >> 7));
buffer[16+5] = 0x80 | (0x7f & (size >> 14));
buffer[16+6] = 0x00 | (0x7f & (size >> 21));
cksum = lfs_crc32c(cksum ^ ((uint32_t)lfs_parity(cksum) << 7),
&buffer[16], 7+size);
// append a truncated gcksumdelta tag
lfs_off_t off = BLOCK_SIZE - (7+4) + OVERFLOW;
size = (TRUNCATED_SIZE) ? 4-lfs_smax(OVERFLOW, 0) : 4;
buffer[off+0] = ((uint8_t)lfs_parity(cksum) << 7)
| (uint8_t)(LFSR_TAG_GCKSUMDELTA >> 8);
buffer[off+1] = (uint8_t)(LFSR_TAG_GCKSUMDELTA >> 0);
buffer[off+2] = 0;
buffer[off+3] = 0x80 | (0x7f & (size >> 0));
buffer[off+4] = 0x80 | (0x7f & (size >> 7));
buffer[off+5] = 0x80 | (0x7f & (size >> 14));
buffer[off+6] = 0x00 | (0x7f & (size >> 21));
cksum = lfs_crc32c(cksum ^ ((uint32_t)lfs_parity(cksum) << 7),
&buffer[16], 7+size);
// make next tag look valid to make errors look more likely
if (OVERFLOW < 0) {
buffer[BLOCK_SIZE + OVERFLOW] = ((uint8_t)lfs_parity(cksum) << 7);
}
// write to both mroot blocks
for (int i = 0; i < 2; i++) {
CFG->erase(CFG, i) => 0;
CFG->prog(CFG, i, 0, buffer, BLOCK_SIZE) => 0;
}
// try to mount, this should fail
lfs_t lfs;
lfsr_mount(&lfs, LFS_M_RDWR | M_FLAGS, CFG) => LFS_ERR_CORRUPT;
'''
## Magic consistency ##
# make sure our magic string ("littlefs") shows up in the same place (off=8)
[cases.test_mtree_magic]
code = '''
lfs_t lfs;
lfsr_format(&lfs, LFS_F_RDWR | F_FLAGS, CFG) => 0;
// check our magic string
//
// note if we lose power we may not have the magic string in both blocks!
// but we don't lose power in this test so we can assert the magic string
// is present in both
uint8_t magic[LFS_MAX(16, READ_SIZE)];
CFG->read(CFG, 0, 0, magic, LFS_MAX(16, READ_SIZE)) => 0;
assert(memcmp(&magic[8], "littlefs", 8) == 0);
CFG->read(CFG, 1, 0, magic, LFS_MAX(16, READ_SIZE)) => 0;
assert(memcmp(&magic[8], "littlefs", 8) == 0);
'''
[cases.test_mtree_magic_extend]
# this should be set so only one entry can fit in a metadata block
defines.SIZE = 'BLOCK_SIZE / 4'
# make it so blocks relocate every two compacts
defines.BLOCK_RECYCLES = 0
in = 'lfs.c'
code = '''
lfs_t lfs;
lfsr_format(&lfs, LFS_F_RDWR | F_FLAGS, CFG) => 0;
lfsr_mount(&lfs, LFS_M_RDWR | M_FLAGS, CFG) => 0;
lfs_alloc_ckpoint(&lfs);
lfsr_data_t data;
// prepare mroot with an entry
uint8_t buffer[SIZE];
buffer[0] = '\0';
memset(buffer+1, 'a', SIZE-1);
lfsr_mdir_t mdir;
lfsr_mtree_namelookup(&lfs, 0, (const char*)buffer+1, SIZE-1,
&mdir, NULL, NULL) => LFS_ERR_NOENT;
lfsr_mdir_commit(&lfs, &mdir, LFSR_RATTRS(
LFSR_RATTR_NAME(
LFSR_TAG_REG, +1,
0, (const char*)buffer+1, SIZE-1))) => 0;
assert(mdir.rbyd.weight == 2);
// force mroot to compact twice, this should extend the mroot
lfsr_mdir_t old_mroot = lfs.mroot;
lfs.mroot.rbyd.eoff = -1;
lfsr_mdir_commit(&lfs, &lfs.mroot, NULL, 0) => 0;
lfs.mroot.rbyd.eoff = -1;
lfsr_mdir_commit(&lfs, &lfs.mroot, NULL, 0) => 0;
// assert we relocated
assert(lfsr_mdir_cmp(&old_mroot, &lfs.mroot) != 0);
// assert that our entry is still in the mroot
lfsr_mtree_lookup(&lfs, (0 << lfs.mbits)+1, &mdir) => 0;
assert(mdir.rbyd.weight == 2);
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_REG, NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, SIZE) => SIZE;
assert(buffer[1] == 'a');
lfsr_unmount(&lfs) => 0;
// check our magic string
//
// note if we lose power we may not have the magic string in both blocks!
// but we don't lose power in this test so we can assert the magic string
// is present in both
uint8_t magic[LFS_MAX(16, READ_SIZE)];
CFG->read(CFG, 0, 0, magic, LFS_MAX(16, READ_SIZE)) => 0;
assert(memcmp(&magic[8], "littlefs", 8) == 0);
CFG->read(CFG, 1, 0, magic, LFS_MAX(16, READ_SIZE)) => 0;
assert(memcmp(&magic[8], "littlefs", 8) == 0);
'''
[cases.test_mtree_magic_extend_twice]
# this should be set so only one entry can fit in a metadata block
defines.SIZE = 'BLOCK_SIZE / 4'
# make it so blocks relocate every two compacts
defines.BLOCK_RECYCLES = 0
# force our block to compact by setting prog_size=block_size, we don't have
# any way to indirectly force the intermediary mroots to compact otherwise
defines.PROG_SIZE = 'BLOCK_SIZE'
in = 'lfs.c'
code = '''
lfs_t lfs;
lfsr_format(&lfs, LFS_F_RDWR | F_FLAGS, CFG) => 0;
lfsr_mount(&lfs, LFS_M_RDWR | M_FLAGS, CFG) => 0;
lfs_alloc_ckpoint(&lfs);
lfsr_data_t data;
// prepare mroot with an entry
uint8_t buffer[SIZE];
buffer[0] = '\0';
memset(buffer+1, 'a', SIZE-1);
lfsr_mdir_t mdir;
lfsr_mtree_namelookup(&lfs, 0, (const char*)buffer+1, SIZE-1,
&mdir, NULL, NULL) => LFS_ERR_NOENT;
lfsr_mdir_commit(&lfs, &mdir, LFSR_RATTRS(
LFSR_RATTR_NAME(
LFSR_TAG_REG, +1,
0, (const char*)buffer+1, SIZE-1))) => 0;
assert(mdir.rbyd.weight == 2);
// force mroot to compact twice, this should extend the mroot
lfsr_mdir_t old_mroot = lfs.mroot;
lfs.mroot.rbyd.eoff = -1;
lfsr_mdir_commit(&lfs, &lfs.mroot, NULL, 0) => 0;
lfs.mroot.rbyd.eoff = -1;
lfsr_mdir_commit(&lfs, &lfs.mroot, NULL, 0) => 0;
// assert we relocated
assert(lfsr_mdir_cmp(&old_mroot, &lfs.mroot) != 0);
// force mroot to compact four times, this should relocate the mroot
// twice, forcing a second mroot extension
old_mroot = lfs.mroot;
lfs.mroot.rbyd.eoff = -1;
lfsr_mdir_commit(&lfs, &lfs.mroot, NULL, 0) => 0;
lfs.mroot.rbyd.eoff = -1;
lfsr_mdir_commit(&lfs, &lfs.mroot, NULL, 0) => 0;
lfs.mroot.rbyd.eoff = -1;
lfsr_mdir_commit(&lfs, &lfs.mroot, NULL, 0) => 0;
lfs.mroot.rbyd.eoff = -1;
lfsr_mdir_commit(&lfs, &lfs.mroot, NULL, 0) => 0;
// assert we relocated
assert(lfsr_mdir_cmp(&old_mroot, &lfs.mroot) != 0);
// assert that our rattr is still in the mroot
lfsr_mtree_lookup(&lfs, (0 << lfs.mbits)+1, &mdir) => 0;
assert(mdir.rbyd.weight == 2);
lfsr_mdir_lookup(&lfs, &mdir, LFSR_TAG_REG, NULL, &data) => 0;
lfsr_data_read(&lfs, &data, buffer, SIZE) => SIZE;
assert(buffer[1] == 'a');
lfsr_unmount(&lfs) => 0;
// check our magic string
//
// note if we lose power we may not have the magic string in both blocks!
// but we don't lose power in this test so we can assert the magic string
// is present in both
uint8_t magic[LFS_MAX(16, READ_SIZE)];
CFG->read(CFG, 0, 0, magic, LFS_MAX(16, READ_SIZE)) => 0;
assert(memcmp(&magic[8], "littlefs", 8) == 0);
CFG->read(CFG, 1, 0, magic, LFS_MAX(16, READ_SIZE)) => 0;
assert(memcmp(&magic[8], "littlefs", 8) == 0);
'''
View Git Blame Copy Permalink