The Virtual File System (VFS) layer [1] provides a uniform interface for the kernel to deal with various I/O requests and specifies a standard interface that each file system must support. Through this layer, one kernel can mount several different types of file systems (e.g. EXT2FS, ISO9660FS, NFS, ...) into the same tree structure. We worked with version 2.2.12 of the Linux kernel and confined our changes to the VFS layer. By doing all of our changes in the VFS layer we kept our predictive prefetching totally independent of the underlying file system.
Arguably, the most important service the VFS layer provides is a uniform I/O data cache. Linux maintains four caches of I/O data: page cache, i-node cache, buffer cache and directory cache. Figure 5 shows these caches and how they interact with the kernel, each other and user level programs. The page cache combines virtual memory and file data. The i-node cache keeps recently accessed file i-nodes. The buffer cache interfaces with block devices, and caches recently used meta-data disk blocks. The Linux kernel reads file data through the buffer cache, but keeps the data in the page cache for reuse on future reads. The directory cache (d-cache) keeps in memory a tree that represents a portion of the file system's directory structure. This tree maps a file's path name to an i-node structure and speeds up file path name look up. The basic element of the d-cache is a structure called the d-entry.
We implemented our methods of modeling file access patterns by adding one field to the d-entry structure. The various models would attach their modeling data structure to this pointer. For the last successor model this consisted of just a device and inode number. For the partitioned models this was a pointer to the partition that began with the file that the d-entry identified. After each file access the model would update its predictions. The prefetch engine was then called and would use these predictions to prefetch file data.
