Features

XFS uses B+ trees extensively in place of traditional linear file system structures. B+ trees provide an efficient indexing method that is used to rapidly locate free space, to index directory entries, to manage file extents, and to keep track of the locations of file index information within the file system. XFS is a fully 64-bit file system. Most of the global counters in the system are 64-bits in length, as are the addresses used for each disk block and the unique number assigned to each file (the inode number). A single file system can theoretically be as large as 18 million terabytes. The file system is partitioned into regions called Allocation Groups (AG). Like UFS cylinder groups, each AG manages its own free space and inodes. The primary purpose of Allocation Groups is to provide scalability and parallelism within the file system. This partitioning also limits the size of the structures needed to track this information and allows the internal pointers to be 32-bits. AGs typically range in size from 0.5 to 4GB. Files and directories are not limited to allocating space within a single AG.

XFS has a variety of sophisticated support utilities to enhance its usability. These include fast mkfs (make a file system), dump and restore utilities for backup, xfsdb (XFS debug), xfscheck (XFS check), and xfsrepair to perform file system checking and repairing. The xfs fsr utility defragments existing XFS file systems. The xfs bmap utility can be used to interpret the metadata layouts for an XFS file system. The growfs utility allows XFS file systems to be enlarged on-line.

Architecture

The high level structure of XFS is similar to a conventional file system with the addition of a transaction manager. XFS supports all of the standard Unix file interfaces and is entirely POSIX- and XPG4-compliant. It sits below the vnode interface in the IRIX kernel and takes full advantage of services provided by the kernel, including the buffer/page cache, the directory name lookup cache, and the dynamic vnode cache.

XFS is modularized into several parts, each of which is responsible for a separate piece of the file system's functionality. The central and most important piece of the file system is the space manager. This module manages the file system free space, the allocation of inodes, and the allocation of space within individual files. The I/O manager is responsible for satisfying file I/O requests and depends on the space manager for allocating and keeping track of space for files. The directory manager implements the XFS file system name space. The buffer cache is used by all of these pieces to cache the contents of frequently accessed blocks from the underlying volume in memory. It is an integrated page and file cache shared by all file systems in the kernel. The transaction manager is used by the other pieces of the file system to make all updates to the metadata of the file system atomic. This enables the quick recovery of the file system after a crash. While the XFS implementation is modular, it is also large and complex. The current implementation is over 110,000 lines of C code (not including the buffer cache or user-level XFS utilities); in contrast, the EFS implementation is approximately 12,000 lines.

Journaling

XFS journals metadata updates by first writing them to an in-core log buffer, then asynchronously writing log buffers to the on-disk log. The on-disk log is a circular buffer: new log entries are written to the head of the log, and old log entries are removed from the tail once the inplace metadata updates occur. After a crash, the on-disk log is read by the recovery code which is called during a mount operation. XFS metadata modifications use transactions: create, remove, link, unlink, allocate, truncate, and rename operations all require transactions. This means the operation, from the standpoint of the file system on-disk metadata, either never starts or always completes. These operations are never partially completed on-disk: they either happened or they didn't. Transactional semantics are required for databases, but until recently have not been considered necessary for file systems. This is likely to change, as huge disks and file systems require the fast recovery and good performance journaling can provide. An important aspect of journaling is write-ahead logging: metadata objects are pinned in kernel memory while the transaction is being committed to the on-disk log. The metadata is unpinned once the in-core log has been written to the on-disk log. Note that multiple transactions may be in each in-core log buffer. Multiple in-core log buffers allow for transactions when another buffer is being written. Each transaction requires space reservation from the log system (i.e., the maximum number of blocks this transaction may need to write). All metadata objects modified by an operation, e.g., create, must be contained in one transaction.

The vnode/vfs interface in IRIX

The vnode/vfs file system interface was developed in the mid-80s to allow the UNIX kernel to support multiple file systems simultaneously. Up to that time, UNIX kernels typically supported a single file system that was bolted directly into the kernel internals. With the advent of local area networks in the mid-80s, file sharing across networks became possible, and it was necessary to allow multiple file system types to be installed into the kernel. The vnode/vfs interface separates the file-system-independent vnode from the file-system-dependent inode. This separation allows new file systems to re-use existing file-system-independent code, and, at least in theory, to be developed independently from the internal kernel data structures. IRIX and XFS use the following major structures to interface between the file system and the rest of the IRIX OS components:

The vnode structure points at the first behavior in the chain of file systems handling the file associated with this vnode. The behavior also points to the function vector, xfs vnodeops, which contains all the file-system-specific routines at the file level. In IRIX, the vnodeops contains more than 57 routines which can be invoked on a "file". These routines cover many functions such as create, remove, read, write, open, close, and others.

Mapping the vnode/vfs interface to Linux

Changing XFS to fit directly into the Linux VFS interface would require significant changes to a large portion of the XFS codebase. The current source code organization would need to be significantly changed and code charing between the IRIX and Linux versions of XFS would become much more difficult. The alternative is to integrate the vnode and vfs object as private file-system-dependent data in the struct inode and struct super block data in Linux. This approach introduces a translation layer between the XFS code and the Linux VFS interface which translate Linux VFS calls into the equivalent XFS vnode operations. The XFS vnode itself is attached to the private data area of the Linux inode, while the XFS vfs object is attached to the private data area of the Linux superblock.

In the initial Linux port of XFS the vnode and vfs operations remained almost unchanged from IRIX and the translation layer, called linvfs, had to do a certain amount of argument and semantics remapping. For example in IRIX the read/write entry points use the uio structures that allow to pass multiple I/O requests in one call to the filesystems while the Linux read/write entry points use a much simpler scheme with one I/O request per call. In later revisions of XFS for Linux some vnode/vfs operations where changed to fit the Linux model better. For example the lookup, create and rename VOPs now pass down the Linux dentry structure that describes a directory entry in all it's details instead of just the name as in IRIX. This allows getting rid of superfluous internal lookup calls and access/race checks already handled in the generic Linux code. A result of these changes is that more than 2,000 lines of code that were required on IRIX could be removed from the Linux XFS.

Another example are the already mentioned read/write entry points that got simplified to match their Linux counterparts.

fcntl Versus ioctl in IRIX and Linux

In IRIX, XFS supports approximately 20 special fcntl interfaces used for space pre-allocation, extent retrieval, extended file information, etc. In addition, IRIX XFS has about a dozen special system call interfaces, all implemented via the special syssgi system call. These interfaces are used for operations such as growing the file system or retrieving internal file system information.

The Linux file system interface has no fcntl operation. The only supported fcntl calls on Linux are file locking calls. We proposed to the Linux community that a fnctl file operation be added. After extensive discussion, it was decided to use the existing ioctl operation, linvfs_ioctl, and all of the fcntl and syssgi usages have been converted into ioctls. A shortcoming to the ioctl approach is in the semantics of an ioctl to block or character special devices which reside within the file system: In these cases, the device driver's ioctl routine will be used rather than the file system's. Outside of that, porting the fcntl and syssgi interfaces to ioctl's has been straightforward.

IRIX XFS creds and Linux

In older UNIX systems, the file system code used the current process's data structures to determine the user's credentials such as uid, gid, capabilities, etc. The VFS/vnode interface removed this code and introduced a cred structure which is passed to certain file system operations such as create and lookup. The file system uses this information to determine permissions and ownership.

XFS was written using the VOP/vnode interface, so it regularly uses cred structures. One of the more prevalent cred usages on IRIX XFS is get_current_cred, which returns this structure for the current process.

Linux is similar to older UNIX implementations in that file systems are expected to look directly at the task structure to determine the current process's credentials. Linux does not utilize a cred structure.

In porting XFS to Linux, we first attempted to map the various cred fields onto the corresponding task fields. This had the undesired side-effect of producing code that utilized a cred pointer that in actuality was pointing at a task. This was determined to be unacceptable.

We then considered implementing a complete cred infrastructure, which would include a pool of active creds, cred setup, teardown, lookup, etc. It was determined that this would require too much overhead.

In looking at the Linux code, we saw that all of the access/permission work occurs above the file system dependent code, so having a cred is important only on creation. We then examined our own internal usage of cred fields in XFS, and found that more often than not, a cred was passed down through a VOP_, and never used. The few places that did use a cred field were changed to use the current task structure in Linux.

Early versions of the XFS Linux port still passed a cred address on the VOPs, but we changed the linvfs later to always pass NULL into the cred arguments.

In addition to these cred changes, we have removed many access checks from the XFS code since these are now performed at a higher layer and are redundant in the file system dependent code

The pagebuf Module

Our approach to porting XFS has included adding pagebuf, a layered buffer cache module on top of the Linux page cache. This allows XFS to act on extent-sized aggregates. Key to this approach is the pagebuf structure, which is the major structure of the pagebuf layer. The pagebuf objects implemented by this module include a list of physical pages associated with the pagebuf, plus the device information needed to perform I/O.

In earlier versions of XFS for Linux we were experimenting with a new device request interface, so that we can queue one of these pagebuf objects directly to a device, rather than having to create and queue a large number of single-block buffer_head objects for each logical I/O request. These extensions have been superceeded by the Linux 2.5 block layer rewrite that allows the submission of multi-page bio requests; current XFS versions for Linux 2.4 create and queue buffer_head objects to perform pagebuf I/O.

A key goal for the layered buffer cache module is that its objects be strictly temporary, so that they are discarded when released by the file system, with all persistent data held purely in the page cache. This avoids creating yet another class of permanent system object, with separate locking and resource management issues. The IRIX buffer cache implementation has about 11000 lines of very complex code. By relying purely on the page cache for buffering, we avoid most of the complexity, particularly in regard to locking and resource management, of hybrid page and buffer caches, at the cost of having to pay careful attention to efficient algorithms for assembling large buffers from pages.

Delayed Allocation of Disk Space for Cached Writes

Allocating space when appending to a file slows down writes, since reliable metadata updates (to record extent allocations) result in extra writes. Also, incremental allocations can produce too-small extents, if new extents are allocated each time a small amount of data is appended to a file (as when many processes append to a log file). Delayed allocation reserves disk space for a write but does not allocate any particular space; it simply buffers the write in the page cache. Later, when pages are flushed to disk, the page writing path must ask the file system to do the actual allocation. Also, to allow for optimal extent allocations and optimal write performance, the page writing path must collect adjacent dirty pages ("cluster" them) and write them as a unit.

Since allocation of disk space may be required in the page writing path when delayed allocation is present, and such allocation may require the use of temporary storage for metadata I/O operations, some provision must be made to avoid memory deadlocks. The delayed allocation path for writes must make use of a main memory reservation system, which will limit the aggregate amount of memory used for dirty pages for which disk space has not been allocated, so that there will always be some minimum amount of space free to allow allocations to proceed. Any other non-preemptible memory allocations, such as kernel working storage pages, must be counted against the reservation limit, so that the remaining memory is genuinely available.

File I/O

Early versions of XFS for Linux used an I/O path different from the normal Linux filesystems, basically a stripped down version of the IRIX XFS I/O code sitting ontop of the pagebuf layer. In the XFS/Linux 1.2 release the buffered I/O path has been completely rewritten to use the generic Linux I/O path as much as possible but still providing XFS-unique features such as delayed allocated writes and clustered writeout.

XFS is now using the generic read/write entry points for pagecache-based filesystems (generic_file_read/generic_file_write) but wraps them with XFS-specific functionality such as dealing with DMAPI callbacks and XFS-specific locking. This means all hard work for file I/O is done by the address_space operations where XFS against uses the generic versions for the readpage (read pages into memory), prepare_write and commit_write (copy file data into the pagecache and mark it for flushing) operations. The writepage operation that is responsible for flushing pagecache data to disk is the heart of the XFS I/O path and completely different from the generic code to handle delayed allocated writes and clustered writeout.

A problem in Linux 2.4 is that the buffer layer directly writes out the buffers on it's LRU list to disk without any filesystem interaction, which makes the delayed disk block allocation and clustered writeout features of XFS impossible.

To address this issue the Linux buffer layer has been modified to call back into the filesystems writepage method for a buffer marked for delayed allocation instead of directly writing it out. These changes are localized to one file (fs/buffer.c) and provide XFS-compatible semantics with minimal intrusion.

Linux 2.5 already performs all pagecache writeout through the filesystems writepage (or writepages) entry points so no modification was nessecary.

Direct I/O

Small files which are frequently referenced are best kept in cache. Huge files, such as image and streaming media files and scientific data files, are best not cached, since blocks will always be replaced before being reused. Direct I/O is raw I/O for files: I/O directly to or from user buffers, with no data copying. The page cache must cooperate with direct I/O, so that any pages, which are cached and are modified, are read from memory, and so that writes update cached pages.

Direct I/O and raw I/O avoid copying, by addressing user pages directly. The application promises not to change the buffer during a write. The physical pages are locked in place for the duration of the I/O, via Linux kernel methods (kiobufs in 2.4, get_user_pages in 2.5).

Any dirty pages in the page cache must be flushed to disk before issuing direct I/O. The normal case will find no pages in the cache, and this can be efficiently tested by checking the inode. Once the pagebuf is assembled, the I/O path is largely common with the normal file I/O path, except that the write is never delayed and allocation is never delayed.

Direct I/O is indicated at open( ) time by using the O_DIRECT flag. Usually the needed space for the file is pre-allocated using an XFS ioctl call to ensure maximum performance.

Unlike other Linux filesystems XFS allows multiple O_DIRECT writes to the same inode to happen in parallel.

The Encumbrance Review Process

We were faced with making comparisons across several large code bases, and in particular UNIX System V Release 4.2-MP, BSD4.3 NET/2, BSD4.4-lite and the open source version of XFS. We performed the following tasks:

In all of the steps above, the outcome was a list of possible matches. For each match, it was necessary to establish in the context of the matches (in one or more files), if there was a real encumbrance issue. We used a modified version of the tkdiff tool to graphically highlight the areas of the "match" without the visual confusion of all of the minutiae of the line-by-line differences. However, the classification of the matches was ultimately a manual process, based on the professional and technical skills of the engineers.

Encumbrance Relief

Especially in view of the size of the XFS source, a very small number of real encumbrance issues were identified. In all cases the relief was relatively straightforward, with removal of code required for IRIX, but not for Linux, being the most common technique.