B-Trees and Refactoring: Week 4 of VoreStation Development
2023-09-10
written by Niko Chow-Stuart (Lead Developer)
so, depending on how many people reading this are experienced in either filesystem design or osdev in
general, some of you may have seen this coming. i've decided to scrap the "infinite indirect blocks" design
as it was way too complex and was adding a lot of hard-to-read code to the implementation. instead, i've
gone with a more conventional design of having a fixed number of indirect blocks.
within each inode, there are 32 fields for direct blocks, single indirect blocks (pointer to a block of u64
pointers that point to datablocks), and double indirect blocks (pointer to a block of u64 pointers that
point to single indirect blocks), followed by triple, quadruple, quintuple, and sextuple indirect blocks
(which i hopefully don't need to explain). this means that the maximum file size (assuming the minimum
block size of 2048 bytes, where each block can contain 256 (2048/8) addresses) is roughly
(32 + 256 + 256^2 + 256^3 + 256^4 + 256^5 + 256^6) * 2048 bytes, or 526300 terabytes.
although this is a phrase that many in the past have said and regretted, i think that's probably a good
enough maximum file size.
this has massively simplified the codebase, and while my implementation of this design is a bit rushed,
it is way more readable than the previous design and can more easily be refactored later on to simplify the
code. one of the main ideas for refactoring later on would be to add an iterator for list blocks so that
i wouldn't need to copy-paste the same code for reading/writing a series of blocks, as this is currently
one of the main sources of code length in the filesystem (which can be seen by the amount of enclosing
brackets used so that i can collapse those sections in my IDE). this would likely be either preceded
or followed by an update to move a lot of stuff out of the main `lib.rs` file, as this file is way too long
and not easily readable.
the main other thing that was worked on in the last two weeks was the implementation of b-trees. very
early on, i made the decision to separate the b-tree code from the filesystem as that would greatly
simplify running tests on the b-tree code during development, as well as allowing for said code to be
easily reused if needed. the b-tree code is currently quite simple, being heavily based upon the example
code from geeksforgeeks.org (which i believe is either public domain or CCBY-SA, i'm not sure as their
website is awful to browse if you don't want to make an account, and their legal information is spread out
weirdly). currently, the b-tree implementation only supports insertion, searching, deleting, and ordered
listing. this should hopefully be enough for the filesystem, however i'll likely need to either add more
functionality in the future, or at least refactor the code to be less C++-like (as quite a bit of it is -
as stated before - a somewhat hacky manual conversion of the C++ code from geeksforgeeks.org).
i've also started to hook the b-tree code into the filesystem code somewhat, it is still very much a
work-in-progress effort as i started writing it before i had finished the b-tree code, and as such, i
have not added a deletion wrapper yet. this will likely be done in the coming weeks, and hopefully
shouldn't take too long. hopefully, i may even be able to get a basic FUSE demo running within that
timeframe as well, as i feel like i've spent way too long working on this filesystem driver and haven't
even written a single blog post about anything else. once the filesystem is complete, i'll likely start
working on both ELF binary loading and basic memory management for the vap kernel, which means that i'll
probably be able to get a somewhat bootable operating system soon!
by the time this blog post is up, the updated source code for the filesystem should be available on our
git server, and hopefully the b-tree code should be posted
as well!
filesystem git
b-tree git
and that's about it! very big thanks to the person who donated $20 to us on LiberaPay this week, it's
very much appreciated! if you want to donate to us, you can do so on our LiberaPay here:
other than that, i'll see you all next week! happy voring!
image made by @cathodegaytube!