Model for handling ownership/pointers for a file system

#1

I am working on a Rust driver for the Apple HFS+ Filesystem, however, due to the complexity of file systems, I’m finding it difficult to arrange the model for who owns what data and how to handle references between the structures. I currently have a working prototype in Python that can dump all the files/directories and their attributes so the challenge here is simply designing a proper model of this for Rust. I’m currently writing it single-threaded, but I would like to eventually update it to handle multi-threading, one per file, and perhaps a longer-term goal of implementing write support.

To explain my conundrum, I think a brief description of the file system is needed. File contents are stored in forks in the filesystem. A fork is simply a list of extents or contiguous regions of the underlying disk. To find a file, there is a special file called the catalog file. It’s contents are a B-Tree structure that allows for a quick look-up of any file and in the information about the fork containing the files data. The catalog is kept in it’s own fork stored in the volume header. Along with the catalog special file is the extents overflow file. That contains extent information for files more than a few extents long (including, possibly, the catalog file, but not the overflow file itself). The Extents Overflow file is also organized as a BTree like the Catalog file.

From this, I envision three major structures, Forks, BTrees, and a single Volume Header containing references to the two special forks among other mostly static data about the volume.

A fork is logically one contiguous stream of data with a known size, though it may be physically broken up into multiple extents on disk. It will need a Read and Seek trait, and, in the future, a Write trait.

A BTree needs a method to lookup a key and return it’s value (or error). In the distant future, it will also have insert, update, and delete key/value. A BTree is backed by a Fork and, once the BTree is instantiated, I will never directly refer to the Fork. Should the BTree own the fork?

Lastly, the Volume header which contains several fields of static information needed by the Fork and BTree structures along with references to the catalog extents forks/btrees.

When reading through the catalog or user file forks, they might need to refer to the extents forks/b-tree to find more extents that are a part of the file. Ultimately, I’m having trouble figuring how to link all this data together and handle structure ownership. What’s a good method for this kind of complex relationship?

0 Likes