diff options
author | Christopher Haster <chaster@utexas.edu> | 2017-03-25 17:42:51 +0300 |
---|---|---|
committer | Christopher Haster <chaster@utexas.edu> | 2017-03-26 03:04:21 +0300 |
commit | f5668462234a5b216c3ed018efb22048146d5047 (patch) | |
tree | 91a30cef977877498552019fa485101af5e1b547 /lfs.h | |
parent | ed674e8414273b9989c131f84087422e65de6feb (diff) |
Revised free-list structure to adopt a lazy scanning allocator of sorts
The free-list structure, while efficient for allocations, had one big
issue: complexity. Storing free blocks as a simple fifo made sense
when dealing with a single file, but as soon as you have two files
open for writing, updating the free list atomicly when the two files
can not necessarily even be written atomicly proved problematic. It's a
solvable problem, but requires many writes to keep track of everything.
Now changing direction to pursue a more "drop it on the floor" strategy.
Since allocated blocks are tracked by the filesystem, we can simply
subtract from all available blocks the blocks we know of to allocate new
blocks. This is very expensive (O(blocks in use * blocks on device)),
but greatly simplifies any interactions that result in deallocated
blocks.
Additionally, it's impossible to corrupt the free list structure
during a power failure. Anything blocks that aren't tracked are simply
"dropped on the floor", and can be allocated later.
There's still a bit of work around the actually allocator to make it
run in a somewhat reasonable frame of time while still avoiding
dynamic allocations. Currently looking at a bit-vector of free
blocks so at least strides of blocks can be skipped in a single
filesystem iteration.
Diffstat (limited to 'lfs.h')
-rw-r--r-- | lfs.h | 9 |
1 files changed, 2 insertions, 7 deletions
@@ -19,6 +19,7 @@ enum lfs_error { LFS_ERROR_EXISTS = -5, LFS_ERROR_NOT_DIR = -6, LFS_ERROR_INVALID = -7, + LFS_ERROR_NO_SPACE = -8, }; enum lfs_type { @@ -38,14 +39,8 @@ enum lfs_open_flags { }; typedef struct lfs_free { - lfs_word_t begin; - lfs_word_t off; - lfs_word_t end; - lfs_disk_struct lfs_disk_free { - lfs_word_t rev; - lfs_ino_t head; - lfs_word_t off; + lfs_word_t begin; lfs_word_t end; } d; } lfs_free_t; |