diff options
author | Christopher Haster <chaster@utexas.edu> | 2018-09-10 01:48:11 +0300 |
---|---|---|
committer | Christopher Haster <chaster@utexas.edu> | 2018-10-18 18:00:49 +0300 |
commit | c67a41af7a68390b9898b9f596e29879fe846e7d (patch) | |
tree | 0aea3b587ebcc3764ea3abfd632383f01278a71a /lfs.h | |
parent | 6046d85e6ed53b6ddc1232cd56f788add8a1d44b (diff) |
Added support for deleting attributes
littlefs has a mechanism for deleting file entries, but it doesn't have
a mechanism for deleting individual tags. This _is_ sufficient for a
filesystem, but limits our flexibility. Deleting attributes would be
useful in the custom attribute API and for future improvements (hint the
child pointers in B-trees).
However, deleteing attributes is tricky. We can't just omit the
attribute, since we can only add new tags. Additionally, we need a way
to track what attributes have been deleted during compaction, which
currently relies on writing out attributes to disk.
The solution here is pretty nifty. First we have to come up with a way
to represent a "deleted" attribute. Rather than adding an additional
bit to the already squished tag structure, we use a -1 length field,
specifically 0xfff. Now we can commit a delete attribute, and this
deleted tag acts as a place holder during compacts.
However our delete tag will never leave our metadata log. We need some
way to discard our delete tag if we know it's the only representation of
that tag on the metadata log. Ah! We know it's the only tag if it's in
the first commit on the metadata log. So we add an additional bit to the
CRC entry to indicate if we're on the first commit, and use that to
decide if we need to keep delete tags around.
Now we have working tag deletion.
Interestingly enough, tag deletion is actually indirectly more efficient
than entry deletion, since compacting entries requires multiple passes,
whereas tag deletion gets cleaned up lazily. However we can't adopt the
same strategy in entry deletion because of the compact ordering of
entries. Tag deletion works because tag types are unique and static.
Managing entry deletion in this manner would require static id
allocation, which would cause problems when creating files, running out
of space, and disallow arbitrary insertions of files.
Diffstat (limited to 'lfs.h')
-rw-r--r-- | lfs.h | 4 |
1 files changed, 2 insertions, 2 deletions
@@ -49,7 +49,7 @@ typedef uint32_t lfs_block_t; // to <= 0xfff. Stored in superblock and must be respected by other // littlefs drivers. #ifndef LFS_ATTR_MAX -#define LFS_ATTR_MAX 0xfff +#define LFS_ATTR_MAX 0xffe #endif // Maximum name size in bytes, may be redefined to reduce the size of the @@ -64,7 +64,7 @@ typedef uint32_t lfs_block_t; // block. Limited to <= LFS_ATTR_MAX and <= cache_size. Stored in superblock // and must be respected by other littlefs drivers. #ifndef LFS_INLINE_MAX -#define LFS_INLINE_MAX 0xfff +#define LFS_INLINE_MAX 0xffe #endif // Possible error codes, these are negative to allow |