Distributed File System
A) General principles
As most POSIX compliant operating systems, ALMOS-MKH sees the external storage device as an array of clusters, where each clusters can store one page of 4 Kbytes. Each cluster occupies eight 512 bytes physical sectors, and is indexed by a cluster identifier, calledd cluster_id.
To support various File System types, ALMOS-MKH defines a generic Virtual File System API defined in the almos-mkh/kernel/fs/vfs.c, and almos-mkh/kernel/fs/vfs.h files.
All supported file systems are supposed to have a hierarchical tree_based structure, where some special directory files contain links to other files that can be directory files, or terminal files. Therefore, any file X in the file system can be unambiguously defined by a pathname describing the path from the VFS root to the X file. A directory file has only on single path name, but a terminal file can have several parent directories, defining several pathnames for one single file.
Any cluster_id can be allocated to any file (terminal or directory). For all supported file systems, the ordered set of clusters allocated to a given file is supposed to be registered in a structure called File Allocation Table (FAT).
As a general rule, the file system makes no assumption on a terminal file, but each file system defines its own directory file format, and its own FAT format.
Therefore, any file system stores three types of informations:
- some clusters are used to store the terminal files,
- other clusters are used to store the directory files,
- specific clusters are used to store the FAT.
As all UNIX or Microsoft operating systems ALMOS-MKH implements a File System Cache, that is a partial copy - in kernel memory - of the file system on device. The VFS is actually the implementation of this generic File System Cache.
The file systems currently supported by ALMOS-MKH are
- the FATFS respects the Microsoft FAT32 format,
- the DEVFS describes all peripheral devices available in the hardware architecture,
- the RAMFS is entirely implemented in physical memory, to avoid access to an external block device.
B) VFS implementation
To reduce the memory footprint of this File System Cache, ALMOS-MKH uses two methods:
- For the directory files, only a subset or the directory entries contained is copied in the File System Cache.
- For the terminal files, only the pages that have been actually accessed are copied in the File System Cache.
This File System Cache is therefore dynamically extended by the OS to satisfy the user processes requests. The physical memory allocated to this cache is only released when a file is removed from the file system on device.
B.1 The Inodes Tree
The Inode Tree (that is not a tree, but is actually a Directed Acyclic Graph) represent a subset of file system on device. It is modeled as a bi_party graph, containing two types of nodes are the inodes and the dentries:
- an inode represents a file, that can be a directory file or a terminal file. It is implemented by the vas_inode_t structure.
- a dentry represents a link from a directory file to another file contained in this directory. It is implemented by the vfs_dentry_t structure.
The main informations registered in the vfs_inode_t structure are a type, and a mapper, that implement a cache for the file content. It contains also a set of pointers on the directory entries (only for a directory file), implemented as an hash table, and another set of pointers on the parent directories (only for a terminal file), implemented as a linked list. The main information registered in the vfs_dentry_t structure are a local name identifying the linked file. Two dentries in the same directory cannot have the same name, because the pathname identifying a file X is defined by the sequence of local names in the path from the root inode to the inode repesenting the X file. It contains a pointer on the child (linked) inode, and another pointer on the parent directory.
B.2 The Mappers
A mapper_t structure is attached to each inode. This structure implements an expandable file cache, and contains a partial copy in kernel memory of the file content on device. As a file is stored on device as an ordered set of 4 Kbytes pages, this cache is implemented as a 3 levels radix-tree, indexed by the page index in file. Each entry in this radix-tree is a pointer on a physical page.
- for a terminal file, ALMOS MKH implements an on-demand policy: it introduces a new physical page in mapper and initializes if from device only when this page is accessed for read or write.
- for a directory file, ALMOS-MKH implements a prefetch policy: all the pages are copied from device to mapper at the first access to the directory.
The FAT itself is copied in the kernel memory, as a dedicated mapper - not attached to a specific inode - contains the pages corresponding to the FAT. ALMOS-MKH implements the "on-demand" policy for this FAT mapper.
When a file (terminal or directory) is modified, or when the FAT itself is modified, the modification is always done in the corresponding mapper, but the device update policy depends on the mapper type:
- For a directory mapper, or for the FAT mapper, the device is immediately updated (write-through policy).
- for a terminal mapper, the device in not immediately updated. It is only updated when the mapper is destroyed, or after an explicit sync() user sys call (write-back policy).
B.3 The File Descriptors
TBD...
