KModel - Disk Layout
 

The KModel file system is modelled after an early Unix file system. The physical storage for the file system is treated as an array of 512-byte blocks. The array is subdivided into four regions: the super block, the boot area, the inode area and the data area. Blocks are addressed by logical block number (LBN).

All multi-byte integer values are assumed to use little-endian order.

Disk layout

The super block contains information about the rest of the disk:

• the file-system version
• the number of blocks on the disk
• the number of inodes
• the block number of the first inode block
• the block number of the first free-space block
• the index of the first free inode.

The boot area resides between the super block and the first inode block. It is variable in size and is often empty.

The inode blocks each contain a number of fixed-size data structures that describe individual files. The first inode describes the root directory of the file system. 

Free Space

Free space is managed by a blocked linked list. Any free block can be pressed into service as a master free block to hold pointers to other free blocks. The master free blocks are linked into a list. The super block contains the block number of the first master free block in the list.

The disk layout is shown in Figure 1.

Figure 1: Disk Layout

The free-space scheme is illustrated by the diagram in Figure 2. Each 512-byte block contains 128 4-byte integers. The first is used to indicate the number of blocks described by the master block. Its value indexes the first unused entry in an array of LBNs that begins with the third integer. The second integer contains the LBN of the next master block. The array of LBNs can contain up to 126 entries.

Figure 2: Free-space Layout

To allocate a block, the master block referenced by the LBN of the first free-space block (stored in the super block) is used. The block count is decremented and used to locate the LBN of a free block. However, if the block count was initially zero, the master block itself is allocated and the free-block LBN in the super block is updated to contain the LBN from master block's link field.

To deallocate a block, the master block referenced from the super block is also used. The LBN of the deallocated block is stored in the LBN array entry indicated by the block-count field and the count field is then incremented. However, if the block-count field contained the maximum value, the deallocated block is pressed into service as a new master block and inserted into the chain between the super block and the former first master block.

Inode

The fields of an inode are shown in Figure 3.

Figure 3 Inode fields

 An inode describes a file on the disk. It consists of a number of fixed fields followed by an asymmetric tree structure that describes the space used by the file.

The fixed fields contain the following information

• mode: the protection bits and the file type
• link: the number of directory entries that contain references to this inode
• length: the number of bytes in the file
• uid: the id of file's owner
• gid: the id of the file's group
• nBlk: the number of blocks occupied by the file's data. 
• ctime: date and time when the file was created
• mtime: date and time when the file was last modified
• atime: date and time when the file was last accessed

The date and time fields are 8 bytes each.

Data Storage

In a simple implementation, the nBlk field is ceil(length/512). However, an implementation can use zero for LBNs that reference blocks that contain entirely zeros. Thus the nBlk field can vary from zero to the value given by the expression ceil(length/512).

20 block pointers are sufficient to describe a file that only contains 10K bytes. To improve on this, the third-last block pointer contains a reference to a block similar to the master free block, except that the count and next fields are unnecessary. The count field can be derived from the length of the file. The next field is not required because the blocks are not linked. The resulting single level of indirection allows the third-last block pointer to describe up to 128 blocks, or 2⁷ x 2⁹ = 2¹⁶ =64KB of data.

Figure 4 Direct and indirect block pointers

The second-last block pointer uses double indirection. It's value references a block that contains 128 pointers to blocks that each contain 128 pointers to data blocks. That is, it describes up to 2⁷ x 2⁷ x 2⁹ = 2²³ = 8MB of data.

The last block pointer uses triple indirection. It describes up to 2⁷ x 2⁷ x 2⁷ x 2⁹ = 2³⁰ = 2GB of data.

Directories

Directories are distinguished from regular files by a value in the mode field. A directory contains a sequence of ordered pairs of inode numbers and file-name strings. 

A file name is variable in length, has no intrinsic length limit and is terminated by a zero-byte. A file-name can appear at most once in the sequence. 

An inode number is a 4-byte integer value. 

Directories use the same data-storage technique as regular files for holding their data. There is no intrinsic limit on the size of a directory.

Directories will normally contain references to themselves (file name is ".") and their parent (file name is ".."). 

The same inode value can appear more than once in the directories that make up the file system. The same inode can be used more than once even in the same directory. Indeed, this is the case for ".." when the directory is the root. 

Hard Links 

A directory is a collection of inodes and names. The link field of an inode contains the number of times the inode appears in a directory. Normally a file or directory appears to reside in exactly one directory. However, every directory contains a reference to itself. In this case, the link count would be 2. The file system allows a file to appear in any number of directories and even allows a file to appear more than once within the same directory, albeit with different names. The link field can contain arbitrarily large numbers. 

When a link count goes to zero, it is because the file appears in no directories and can be deleted. Indeed, an earlier name for the Unix rm command was "unlink". This command removes a file from a directory and decrements its link count. However, the storage for the file cannot be recycled until the last open instance of the file is closed.

Another use for the link count is temporary files. Since a file cannot be deleted until all open instances of the file are closed, the check for a zero link count must necessarily occur at close time. When the last instance is closed and the link count is zero, the file's storage and inode can be recycled. One way to implement unlink is to open the file, decrement it's link count and close the file. For temporary files that must be deleted when a program ends, the file can be created and unlinked. Then when the process ends, normal end-of-process run down would close the file, detect the link count and remove the file. Errors in program logic that might bypass end-of-program cleanup code would have no ill effect.

Symbolic Links

Symbolic links are files that contain as their sole data the pathname of another file. Such files are marked with a special value in their inode so the file systems knows about them. When opening a symbolic link, the file system follows the link and opens the target. Of course, the target may itself by a symbolic link and the links may form a cycle. Most implementations of this file-system feature break the cycle by measuring it against some threshold value and indicating failure when the threshold is reached.