vore microcomputers logo

B-Trees and Refactoring: Week 4 of VoreStation Development


written by Niko Chow-Stuart (Lead Developer)

drawing of the vap mascot laying on their stomach, watching a tree sapling grow

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 of xenia, an anthropomorphic fox who was a contender for the linux mascot image made by @cathodegaytube!