File System Hints

[distantvoices]

This one is not meant as a question and answer thread, but as a thread where hints and tricks about File system implementation can be put. my examples and indications refer to the ext2 fs.

Here comes my first and very obvious one - 'thou' I stumbled over it - it took me three days to get the clue (*wham*):

You need your floppy/hard disk driver to be able to read consecutive/adjacent sectors and deliver them to a supplied buffer. You pass it the start block and the number of blocks and a location where to put the data, and then have it set off and do the rest.

The second one: It is not so obvious for one who is not used to reading file system spec's and has trouble with this block/sector thing - f. ex. floppy: The super block is always located at Block 1. On the floppy, it starts at sector 2. You read 2 adjacent sectors, so in the end, you have 1024 bytes for the superblock.

The block adjacent to the superblock is the group descriptor block. It is block 2, starts at sector 4 ... you know the rest already.

From this one you can see: you have to multiply the logical block number with the sectors_per_block constant you can calculate from several values in the superblock.

in the group descriptors you find the location of: block allocation bitmap, inode allocation bitmap and start of the inode table per group (several consecutive blocks: you can calculate how many by: total amount of inodes in file system/inodes per block)

that's it for now. It will be continued.

[distantvoices]

Lets go on with File system implementation on basis of EXT2. It is neat, handy and quite easy to access, once one 's got the nitty gritty done:

what we need further, once we've got the ability to fetch the blocks from disk:
List management code, either dedicated functions or general functions with wrappers around which take care about detail handling for the list in question. Lists for: block cache/Block hash. I prefer to use a combination of typedefs: one for the data part of the list, one for the Head/Tail part of it. say

Code: Select all

 typedef struct block{...}block_t; typedef struct blocklist{block_t *head; block_t *tail} blocklist_t;

something similar can be done for the hashlist.
then you need a function getblock and a function putblock.

getblock tries to fetch a block from the cache. If it is not there, it goes on, fetches the block from disk, adds it to the cache queue and to the hash chain it belongs to, initializes some fields and returns it to the caller.

putblock returns a used block to the cache, either in state clean or dirty. If the block is dirty, it is written back to disk and marked as clean. If the block is on the tail of the cache,and a arbitrary number of cached blocks (say 100) is exceeded, it is removed from the cache as well as from the hash chain.

I for my part have decided to use an odd way for "hash-chaining blocks" I chain them together by the number of the inode they belong to. It's probably not the best method to do so, but I think, it helps to fetch blocks in a quicker way too.

All flesystem related blocks: superblock, groupdescriptor block, the inode and block alloc tables and the inode tables are chained together by inode number 0. These have to be flushed to disk at each change and not at SYNC().

to be continued...