Linux File System

Every Linux file system implements a basic set of common concepts derivated from the UNIX OS. Files are represented by inodes, and directories are simply files containing a list of entries and devices can be accessed by requesting I/O on special files. Inodes Each file is represented by a structure, called an inode. Each inode contains the description of the file: file type, access rights, owners, timestamps, size, pointers to data blocks. The addresses of data blocks allocated to a file are stored in its inode. When a user requests an I/O operation on the file, the kernel code converts the current offset to a block number, uses this number as an index in the block addresses table and reads or writes the physical block. This figure represents the structure of an inode: 　   Directories Directories are structured in a hierarchical tree. Each directory can contain files and subdirectories. Directories are implemented as a special type of files. Actually, a directory is a file containing a list of entries. Each entry contains an inode number and a file name. When a process uses a pathname, the kernel code searches in the directories to find the corresponding inode number. After the name has been converted to an inode number, the inode is loaded into memory and is used by subsequent requests. Links UNIX file systems implement the concept of link. Several names can be associated with an inode. The inode contains a field containing the number associated with the file. Adding a link simply consists of creating a directory entry, where the inode number points to the inode, and in incrementing the links count in the inode. When a link is deleted, i.e. when one uses the rm command to remove a filename, the kernel decrements the links count and deallocates the inode if this count becomes zero. This type of link is called a hard link and can only be used within a single file system: it is impossible to create cross-file system hard links. Moreover, hard links can only point on files: a directory hard link cannot be created to prevent the apparition of a cycle in the directory tree. Another kind of link exists in most UNIX file systems. Symbolic links are simply files which contain a filename. When the kernel encounters a symbolic link during a pathname to inode conversion, it replaces the name of the link by its contents, i.e. the name of the target file, and restarts the pathname interpretation. Since a symbolic link does not point to an inode, it is possible to create cross-file systems symbolic links. Symbolic links can point to any type of file, even on nonexistent files. Symbolic links are very useful because they don't have the limitations associated to hard links. However, they use some disk space, allocated for their inode and their data blocks, and cause an overhead in the pathname to inode conversion because the kernel has to restart the name interpretation when it encounters a symbolic link. Device Special Files In UNIX-like OSs, devices can be accessed via special files. A device special file does not use any space on the file system. It is only an access point to the device driver. Two types of special files exist: character and block special files. The former allows I/O operations in character mode while the later requires data to be written in block mode via the buffer cache functions. When an I/O request is made on a special file, it is forwarded to a (pseudo) device driver. A special file is referenced by a major number, which identifies the device type, and a minor number, which identifies the unit. The Virtual File System The Linux kernel contains a virtual file system layer which is used during system calls acting on files. The VFS is an indirection layer which handles the file oriented system calls and calls the necessary functions in the physical file system code to do the I/O. This indirection mechanism is frequently used in UNIX-like OSs to ease the integration and the use of several file system types. When a process issues a file oriented system call, the kernel calls a function contained in the VFS. This function handles the structure independent manipulations and redirects the call to a function contained in the physical file system code, which is responsible for handling the structure dependent operations. File system code uses the buffer cache functions to request I/O on devices. The VFS Structure The VFS defines a set of functions that every file system has to implement. This interface is made up of a set of operations associated to three kinds of objects: file systems, inodes, and open files. The VFS knows about file system types supported in the kernel. It uses a table defined during the kernel configuration. Each entry in this table describes a file system type: it contains the name of the file system type and a pointer on a function called during the mount operation. When a file system is to be mounted, the appropriate mount function is called. This function is responsible for reading the superblock from the disk, initializing its internal variables, and returning a mounted file system descriptor to the VFS. After the file system is mounted, the VFS functions can use this descriptor to access the physical file system routines. A mounted file system descriptor contains several kinds of data: information that is common to every file system type, pointers to functions provided by the physical file system kernel code, and private data maintained by the physical file system code. The function pointers contained in the file system descriptors allow the VFS to access the file system internal routines. Two other types of descriptors are used by the VFS: an inode descriptor and an open file descriptor. Each descriptor contains information related to files in use and a set of operations provided by the physical file system code. While the inode descriptor contains pointers to functions that can be used to act on any file (e.g., create, unlink), the file descriptors contains pointer to functions which can only act on open files (e.g., read, write). ExtX takes its design from UFS, which was designed to be fast and reliable. Copies of important data structures are stored throughout the file system, and all data associated with a file are localized so that the hard disk heads do not need to travel much when reading them. The layout of the file system starts with an optional reserved area, and the remainder of the file system is divided into sections, which are called block groups. All block groups, except for the last, contain the same number of blocks, which are used to store file names, metadata, and file content. The basic layout information of ExtX is stored in the superblock data structure, which is at the beginning of the file system. File content is stored in blocks, which are groups of consecutive sectors. The metadata for each file and directory are stored in a data structure called an inode, which has a fixed size and is located in an inode table. There is one inode table in each block group. The name of a file is stored in a directory entry structure, which is located in the blocks allocated to the file's parent directory. Directory entry structures are simple data structures that contain the name of the file and a pointer to the file's inode entry. ExtX has optional features that are organized into three categories based on what the operating system should do if it encounters a file system with a feature that it does not support. The first category is the compatible features, and if the OS does not support one of these features, it can still mount the file system and continue as normal. Examples of this include allocation methods, the existence of a file system journal, and extended attributes. There are also incompatible features, and if an OS encounters one of these, it should not mount the file system. An example of this includes compression. Lastly, a feature can be a read only compatible feature. When an OS encounters one of these features that it does not support, the file system should be mounted as read only. Examples of this include large file support and using B-trees to sort directories instead of an unsorted list. ExtX has many experimental components and features that have not been implemented into the major distributions of Linux. That is not to say that the computer you are investigating does not have the features installed. With Linux, the local administrator can add any kernel features that she wants to, so we cannot make assumptions about the OS. If you are investigating a Linux system that was used as a corporate server, it might have a more standard build. On the other hand, if you are investigating a Linux system that was the desktop system of a person suspected of breaking into other systems, it might have some experimental features.