diff options
Diffstat (limited to 'experiments/bsfs')
| -rw-r--r-- | experiments/bsfs | 120 |
1 files changed, 120 insertions, 0 deletions
diff --git a/experiments/bsfs b/experiments/bsfs new file mode 100644 index 0000000..d60f048 --- /dev/null +++ b/experiments/bsfs @@ -0,0 +1,120 @@ +<h3>bsfs is a filesystem for my systems</h3> + +<p><em>bsfs</em> (bs filesystem) is a simple filesystem format inspired by Plan 9 and Unix. It was created out of my will to have an OS development toolchain that's convenient to use on all the platforms that I may have to develop my environment on. My first candidate was FAT but I found that the available tools to create and manipulate FAT partitions didn't fit my needs, so I would have to create one anyways. I figured out that I could just start working on my own filesystem and its formatting utility right away.</p> + +<p>It wasn't the first time that I experimented with the concept of filesystems, thus the process of designing it wasn't too foreign, I got a prototype working in about a week.</p> + +<h3>Intro</h3> +<p>Filesystems are a type of datastructure that hold resources in terms of <em>files</em>. A file is an abstraction over the concept of resource, with the goal of providing a common interface similar to the following: +<ul> +<li>being read</li> +<li>being read at an offset</li> +<li>havind data be written to +<li>having data be written to at an offset</li> +<li>being deleted</li> +<li>...</li> +</ul> +</p> + +<p>Filesystems also typically allow for files to be arranged in a certain hierarchy thanks to directories.</p> + +<p>Additionally, many filesystems allow for files and directories to have metadata, which can be useful for the user or even the operating system itself. Some of the data that a file could have is: +<ul> +<li>creation date</li> +<li>modification date</li> +<li>access permissions</li> +<li>owning user</li> +<li>owning group</li> +<li>special attributes</li> +<li>...</li> +</ul> +</p> + +<p>bsfs is a kind of unix and plan 9 inspired filesystem. Files have permissions and attributes and are organized into a hierarchical tree thanks to directories, which are themselves files. Metadata about a file are stored in structures called <em>inodes</em>. Inodes can be seen as a kind of portal to the file.</p> + +<h3>Disk organization</h3> +<p>For ease of memory allocation, bsfs disks are split into boundary-aligned - meaning that the boundary of the chunks are aligned on muliple of the chunk's size - chunks of memory called <em>blocks</em>. Blocks can be of various sizes that must be powers of two; this size is specified in the bootsector structure. A typical size for the blocks is 4096 bytes; this is the size that I often use.</p> + +<p>A block is notably caracterized with its block number, which is its address divided by the size of a block.</p> + + +<h3>Storage allocation</h3> + +<p>When the filesystem needs to allocate a block of memory for its needs, whether it be for file content, inodes, or other internal needs, two things can happen: +<ul> +<li>The block freelist is empty, the allocator pops a new block out of the free region</li> +<li>The block freelist has free blocks, the allocators pops a block out of the freelist</li> +</ul> +</p> + +<p>When a deallocation is requested, the block is put back into the block freelist</p> + +<p>Another level of allocation exists for the inodes. Inodes are 64 bytes in size and many can co-exist into a same block; thus a similar system of freelist is put in place per inode-containing block, and then, those blocks are linked to each other globally. (Or at least, that's what should be done. In the current implementations, the inode freelist is global, meaning that it is not easily possible to reuse a block that has been used to hold inodes for other things.)<p> + +<h3>Bootsector</h3> +<p>Essential informations about the current state and configuration of the filesystem are stored in a 512 bytes structure located at the first block of the disk. This structure is meant to be compatible with an <a href="https://en.wikipedia.org/wiki/Master_boot_record">IBM PC bootsector</a>. As such, disks formatted with bsfs can be made bootable without the need for a partitioning scheme to be put in place. This has proven particularly useful for me for prototyping my bootloader</p> + +<p>The bootsector structure is defined as follows +<pre><code>struct bs_bootsec { + u8 bootstrap[446]; + u16 signature; + u64 freeblk; + u64 nextblk; + u64 rsvdblks; + u64 nextin; + u64 freein; + u64 rootin; + u8 blksz; + u8 pad2[13]; + u16 magic; +};</code></pre> +</p> + +<ul> +<li><code>signature</code> is the bsfs signature, <code>0xCAAA</code>.</li> +<li><code>freeblk</code> is the block number of the first block in the block freelist, it is set to 0 if the freelist is empty</li> +<li><code>nextblk</code> is the next block to be popped off of the free +<li><code>rsvdblks</code> is the number of blocks to skip from the beginning of the disk before the beginning of the usable blocks region</li> +<li><code>blksz</code> is the log2 of the size of one block</li> +<li><code>rootin</code> is the inode number of the root directory</li> +</ul> + +(note, things related to inodes in the bootsector are going to be changed) + +<h3>File mapping</h3> +<p>Since I wanted to avoid having a O(n) random seeking time for files, I decided to have offsets in a file be resolved in a system similar to paging in x86_64. Basically, each resource has a mapping root and a mapping level. The queried offset is then split in a series of indices (based on the size of a block) which corresponds to offsets in successive mapping structures. The physical address of the offset in the file is then calculated by traversing the successive mapping structures by having the address of the <code>mapping_structure[i+1]</code> be taken from <code>mapping_structure[i][indices[i]]</code> and so on, until the level 0 is reached meaning that the final offset in the file is reached.</p> + +<p>I found <a href="https://os.phil-opp.com/paging-introduction/">this post</a> to be a particularly good explanation of x86_64 paging.</p> + +<h3>Inodes</h3> +<p>The metadata of the files are stored in a structure called the <em>inode</em> of the file. An inode is caracterized by its <em>inode number</em> which is its address divided by the size of one inode, as well as its contents.</p> + +<p>The bsfs inode structure is +<pre><code>struct bs_inode { + u64 blk; + u64 size; + u64 modif; + u8 owner[17]; + u8 group[17]; + u16 refs; + u8 perms; + u8 attr; + u8 level; + u8 rsvd; +};</code></pre></p> + +<ul> +<li><code>blk</code> is the block number of the mapping root of the file</li> +<li><code>size</code> is the size of the file contents, in bytes</li> +<li><code>modif</code> is the last modification timestamp</li> +<li><code>owner, group</code> are the owner user and group names, utf-8</li> +<li><code>refs</code> is the amount links with the inode throughout the filesystem</li> +<li><code>perms</code> is the permissions, <code>RW-RW-RW</code>. I intend all files to be executable by default.</li> +<li><code>attr</code> are the attributes of the files, bit 0 indicates whether the file is a directory</li> +<li><code>level</code> is the mapping level of the file</li> +</ul> + +<h3>Directories</h3> +<p>Directories are a type of file with a particular attribute set (the bit 0)</p> + +<p>The contents of a directory consist in a list of <em>links</em>. A link is an association between a name and an inode</p>
\ No newline at end of file |