The objective of this section is to show how to implement a complete file system. First, we show the overall organization of a file system, and the logical steps of the implementation. Next, we present a base file system to help the reader get started. Then we organize the implementation steps as a series of programming projects for the reader to complete. It is believed that such an experience would be beneficial to any computer science student.
1. File System Organization
Figure 11.7 shows the internal organization of an EXT2 file system. The organization diagram is
explained by the labels (1) to (5).
- is the PROC structure of the current running proces s. As in a real system, every file operation is due to the current executing process. Each PROC has a cwd, which points to the in-memory INODE of the PROC’s Current Working Directory (CWD). It also has an array of file descriptors, fd[], which point to opened file instances.
- is the root pointer of the file system. It points to the in-memory root INODE. When the system starts, one of the devices is chosen as the root device, which must be a valid EXT2 file system. The root INODE (inode #2) of the root device is loaded into memory as the root (/) of the file system. This operation is known as “mount root file system”
- is an openTable entry. When a process opens a file, an entry of the PROC’s fd array points to an openTable, which points to the in-memory INODE of the opened file.
- is an in-memory INODE. Whenever a file is needed, its INODE is loaded into a minode slot for reference. Since INODEs are unique, only one copy of each INODE can be in memory at any time. In the minode, (dev, ino) identify where the INODE came from, for writing the INODE back to disk if modified. The refCount field records the number of processes that are using the minode.
The dirty field indicates whether the INODE has been modified. The mounted flag indicates whether the INODE has been mounted on and, if so, the mntabPtr points to the mount table entry of the mounted file system. The lock field is to ensure that an in-memory INODE can only be accessed by one process at a time, e.g. when modifying the INODE or during a read/write operation.
- is a table of mounted file systems. For each mounted file system, an entry in the mount table is used to record the mounted file system information, e.g. the mounted file system device number. In the in-memory INODE of the mount point, the mounted flag is turned on and the mntabPtr points to the mount table entry. In the mount table entry, mntPointPtr points back to the in-memory INODE of the mount point. As will be shown later, these doubly-linked pointers allow us to cross mount points when traversing the file system tree. In addition, a mount table entry may also contain other information of the mounted file system, such as values from the superblock, group descriptor, bitmaps and inodes start block, etc. for quick access. If any of these cached items are modified, they must be written back to the device when the device is umounted.
2. Files System Levels
Implementation of the file system is divided into three levels. Each level deals with a distinct part of the file system. This makes the implementation process modular and easier to understand. In the file system implementation, the FS directory contains files which implement the EXT2 file system. The files are organized as follows.
————— Common files of FS ——————————
type.h : EXT2 data structure types
global.c: global variables of FS
util.c : common utility functions: getino(), iget(), iput(), search (), etc.
allocate_deallocate.c : inodes/blocks management functions
Level-1 implements the basic file system tree. It contains the following files, which implement the indicated functions.
—————-Level-1 of FS ——————-
mkdir_creat.c : make directory, create regular file
ls_cd_pwd.c : list directory, change directory, get CWD path
rmdir.c : remove directory
link_unlink.c : hard link and unlink files
symlink_readlink.c: symbolic link files
stat.c : return file information
misc1.c : access, chmod, chown, utime, etc.
User command programs which use the level-1 FS functions include
mkdir, creat, mknod, rmdir, link, unlink, symlink, rm, ls, cd and pwd, etc.
Level-2 implements functions for reading/writing file contents.
——————— Level-2 of FS —————————–
open_close_lseek.c : open file for READ|WRITE|APPEND, close file and lseek
read.c : read from file descriptor of an opened regular file
write.c : write to file descriptor of an opened regular file
opendir_readdir.c : open and read directory
Level-3 implements mount, umount file systems and file protection.
Source: Wang K.C. (2018), Systems Programming in Unix/Linux, Springer; 1st ed. 2018 edition.