diff options
author | Christopher Haster <chaster@utexas.edu> | 2018-10-04 22:49:34 +0300 |
---|---|---|
committer | Christopher Haster <chaster@utexas.edu> | 2018-10-18 18:00:49 +0300 |
commit | aeca7667b32097c109b4ce84a2f3adb2949643ab (patch) | |
tree | 1704c1c67f8373e85b500294bd85df40e09a9230 /lfs.h | |
parent | 7af8b81b81a7e294b902a859b73b9400e771b114 (diff) |
Switched to strongly ordered directories
Instead of storing files in an arbitrary order, we now store files in
ascending lexicographical order by filename.
Although a big change, this actually has little impact on how littlefs
works internally. We need to support file insertion, and compare file
names to find our position. But since we already need to scan the entire
directory block, this adds relatively little overhead.
What this does allow, is the potential to add B-tree support in the
future in a backwards compatible manner.
How could you add B-trees to littlefs?
1. Add an optional "child" tag with a pointer that allows you to skip to
a position in the metadata-pair list that composes the directory
2. When splitting a metadata-pair (sound familiar?), we either insert a
second child tag in our parent, or we create a new root containing
the child tags.
3. Each layer needs a bit stored in the tail-pointer to indicate if
we're going to the next layer. This can be created trivially when we
create a new root.
4. During lookup we keep two pointers containing the bounds of our
search. We may need to iterate through multiple metadata-pairs in our
linked-list, but this gives us a O(log n) lookup cost in a balanced
tree.
5. During deletion we also delete any children pointers. Note that
children pointers must come before the actual file entry.
This gives us a B-tree implementation that is compatible with the
current directory layout (assuming the files are ordered). This means
that B-trees could be supported by a host PC and ignored on a small
device. And during power-loss, we never end up with a broken filesystem,
just a less-than-optimal tree.
Note that we don't handle removes, so it's possible for a tree to become
unbalanced. But worst case that's the same as the current linked-list
implementation.
All we need to do now is keep directories ordered. If we decide to drop
B-tree support in the future or the B-tree implementation turns out
inherently flawed, we can just drop the ordered requirement without
breaking compatibility and recover the code cost.
Diffstat (limited to 'lfs.h')
-rw-r--r-- | lfs.h | 2 |
1 files changed, 1 insertions, 1 deletions
@@ -92,7 +92,7 @@ enum lfs_type { LFS_TYPE_DIR = 0x003, // internally used types - LFS_TYPE_USER = 0x100, + LFS_TYPE_USERATTR = 0x100, LFS_TYPE_NAME = 0x000, LFS_TYPE_DELETE = 0x020, LFS_TYPE_STRUCT = 0x040, |