Simple File System
On three or four occasions over the past 4 years, I had a use for simple file system spec. Either to teach people about file systems, or to have a simple file system to implement to learn the idiosyncracies of an operating system’s VFS layer. This is what I came up with back in 2011 when helping a friend learn about file systems.
Simple File System
The structure is really simple. All multi-byte integers are stored as big endian.
A disk is a linear sequence of blocks. Each block is 512 bytes long. You can read/write a block at a time. The first block on the disk is number 0, the second is 1, etc.
The following is the file system structure. First of all, the file system uses 1024 byte blocks, and therefore you need to issue two disk I/Os to process a file system block worth of data.
The first fs block (disk blocks 0 & 1) is reserved, you should not change it in any way.
The second block contains the superblock:
struct superblock {
uint32_t magic; /* == 0x42420374 */
uint32_t root_inode; /* the disk block containing the root inode */
uint32_t nblocks; /* number of block on the disk */
uint32_t _pad[253]; /* unused (should be '\0' filled) */
};
Starting at the third block is the block allocation map. The most significant bit of the first byte of this block represents fs block 0. The next bit represents block 1, etc.
Each file is represented by an inode. The inode contains a number of data block pointers. The first pointer (blocks[0]) contains the first 1024 bytes of the file, blocks[1] the second, etc. The timestamps are in microseconds since 00:00:00 Jan 1, 1900 UTC.
sturct inode {
uint32_t size; /* file length in bytes */
uint32_t _pad0; /* unused (should be 0) */
uint64_t ctime; /* creation time stamp */
uint64_t mtime; /* last modification time stamp */
uint16_t nblocks; /* number of data blocks in this file */
uint16_t _pad1; /* unused (should be 0) */
uint32_t _pad2; /* unused (should be 0) */
uint32_t blocks[248]; /* file block ptrs */
};
The root directory is represented by an inode, the data pointed to by this inode’s blocks[] have a special format. They should be treated as arrays of directory entries. The filename is space padded (so, “foo.txt” would be stored as “foo.txt ”).
struct direntry {
char fname[28]; /* the filename */
uint32_t inode; /* the inode block ptr */
};
So, graphically, the file system looks something like:
sb -> rootinode
|-> direntries
| |-> <"foo.txt", inodeptr>
| | \-> inode
| | |-> data
| | |-> data
| | \-> data
| |-> <"bar.txt", inodeptr>
| | \-> inode
| | |-> data
| | |-> data
| | \-> data
| | .
| | .
| | .
| \-> <"xyz.txt", inodeptr>
| \-> inode
| |-> data
| |-> data
| \-> data
| .
| .
| .
\-> direntries
|-> <"aaa.txt", inodeptr>
| \-> inode
| |-> data
| |-> data
| \-> data
|-> <"bbb.txt", inodeptr>
| \-> inode
| |-> data
| |-> data
| \-> data
| .
| .
| .
\-> <"ccc.txt", inodeptr>
\-> inode
|-> data
|-> data
\-> data
Amdahl’s law
