Notes for CSC 2/456, 3-22-2000ff ------------------------------- BDS4.4 File System Case Study Most of this is not in textbook. For further info, see chapters 6-8 of "The Design and Implementation of the 4.4BSD Operating System." McKusick, Bostic, Karels, and Quarterman. Addison Wesley, 1996. This is a good, well-documented (set of) file system(s). Solaris and Linux bear a strong resemblance to it. ------------- Simplified view of FS software layering in BSD: system call interface active file entries (accessed through file descriptor tables) vnode layer hierarchical naming (UFS) filestore FFS (the "fast file system") LFS (log-structured file system) MFS (memory-resident file system [for /tmp]) buffer cache block device driver hardware vnode interface distinguishes between file system (hierarchical naming, e.g. from UFS), and filestore (e.g. FFS, LFS) Idea is that implementors typically want to build new filestore, not file system. About 60% of the 4.3BSD code became the file system; only 40% is filestore. When you build a new filestore, it has the vnode interface above (accessed both by kernel-call-handling code and by UFS) and the buffer cache interface below. Both interfaces are exported. Below we explore the levels one at a time. ------------- Open file entry Data structure with, among other things, the current file pointer. File descriptor tables point to open file entries. A file open in more than one process, or with more than one descriptor in the same process, may have a single file entry or multiple ones, depending on whether you want the current file pointer to be shared. Unix semantics say it is shared in the case of dup calls and inheritance through fork; non-shared otherwise. File entries are reference counted so they can be reclaimed on the last close. Provides function indirection through a vtable so that files and sockets can share the same interface. Two mechanisms for locking, one for whole files, another for byte ranges within files (for databases). The former is older. The latter is for POSIX compliance. The 4.4 designers don't like it: close does implicit release of byte-range locks. ------------- Vnodes Function indirection through vtable, so you can plug in your own filestore. BSD vnode interface is extensible: even the set of operations can be expanded. (Set of operations is fixed in most Unix variants.) 4.4BSD implements *stackable* filesystems: functions in a vnode interface can be provided by another vnode interface underneath. Handy for creating new filestores or filesystems that resemble existing ones, but with a few special wrinkles. Examples nullfs passes all operations on; can be used to mount subtree at another point in name hierarchy umapfs changes user ids; great for mounting remote file system with different uid and gid databases. union overlays one file system on top of another (underlying one is read only) portal puts a process at a mount point. Any access that gets that far causes the process to run, with the rest of the path name as input, and service all operations on the "open" "file". procfs provides /proc fdesc provides /dev/fd; allows you to refer to your own open files as /dev/fd/0, /dev/fd/1, etc. kernfs provides /kern, containing configuration data cd9660 allows ISO-compliant CDs to be mounted [ skip over filesystem and filestore temporarily] ------------- Buffer pool Serves two purposes: staging of I/O requests and caching of recently-used blocks. Merged with VM page management in many OSes, but not, I think, in BSD. (Merged in Linux 2.3, but not in 2.2.) Caching role allows 85% of I/O operations to avoid going to disk. A buffer currently being used for staging is said to be "locked". A locked buffer can only be used by one process at a time. A buffer not being used for staging is said to be "free", i.e. not being used by a device. Free buffers are useful, though, for caching purposes. Every free buffer is linked onto two chains. One is the bucket chain of a hash table indexed by vnode number and block number. The other is one of four global lists: LOCKED (overloaded term; all caps version means:) cannot be flushed (used by LFS) LRU has been used by a process and might be used again; kept sorted in LRU order AGE contains data from a deleted file (first choice when you need a free buffer), or pre-fetched (read-ahead) data that might or might not be used (second choice when you need a free buffer) EMPTY consists of only a header; space has been stolen for another buffer buffer header separate from data, so data can change size and so that data can be mapped in and out to avoid copying (buffer data can vary in size, from 0.5K to 64K) header contains hash and list links, flags (useful? inuse? dirty?), device #, block #, byte count, buffer size (small, if fragment), buffer data pointer Kernel keeps dirty buffers on a list. Once every 30 seconds a user-level daemon called 'update' does a 'synch' kernel call to force these out to disk. If you crash, you can lose up to 30 seconds of data. ------------- Device driver Uses C-LOOK scheduling. All BSD disks required to include a "disk label" in block 0, with standard layout, giving physical configuration information (including number and size of sectors, tracks, and cylinders). ------------- UFS (standard UNIX hierarchical naming) Pathname lookup goes through the vnode interface, so you can traverse mount points and automatically change filestores. UFS code (above vnode interface) calls through vnode interface to read first directory on path. Gets back a ptr. to vnode of second directory, which could be in a different filestore. Repeats until finds file. Name cache is a dictionary mapping whole path names to vnodes. Holds both positive and negative information. The negative information is especially important for $path searching by shells ("no, program my_256_assignment is not in /usr/bin"). Information has to be selectively flushed or invalidated whenever directory contents change. To make this faster (and to avoid need to increment vnode reference count for cache entries), BSD uses a lock-and-key technique similar to the common Pascal mechanism to avoid dangling references into the heap. Every vnode gets a new serial number. If we run out of serial numbers (about once a year, for a system that stays up that long) we flush the whole name cache. Inode structure defined in previous set of notes. Provided by UFS. Contains pointers to blocks, but does NOT determine layout of those blocks on disk. That's the responsibility of the filestore. Note that file name is not in inode, but rather in directory, so a file can have multiple names. Memory-resident inodes are linked into two chains: one for bucket of hash table (keyed by < device number, inode number> pair) another for LRU or free list Inodes are also reference-counted (how many vnodes point to me?) Vnodes that go unused for a long time are reclaimed. This decrements the reference count; if it hits zero the inode is reclaimed. A directory may fill an arbitrary number of blocks, called chunks. Each chunk is self-contained, so the disk isn't corrupted in the event of a crash. The first word is the inode number. The rest is directory entries. Each entry consists of entry length name length (may be less than entry length; free space is represented as unused length in preceding entry) name (up to 255 bytes) UFS remembers last directory and offset accessed by each process. If process is going through a directory sequentially (read all names and now is stat-ing each of them), we can get the next one in constant time. Downside is that a single unsuccessful search requires two calls into underlying code, one to search from current spot to end, another from beginning to (old) current spot. ------------- Filestore FFS was designed in the early 1980s, on the assumption that buffer space was modest, and it was important to minimize read latency. LFS was designed in the early 1990s, on the assumption that buffer space was generous, and it was important to maximize write bandwidth. Gregoris will describe LFS on W 29 March. I'll do FFS today. Organization superblocks each file system is described by a superblock number of data blocks in the file system count of maximum number of files (inodes are statically allocated) file block size rotational layout table: vector of lists of block indices within an (arbitrary) cylinder group that have the same rotational position (not applicable to disks with full-track buffering; see below) superblocks are replicated for reliability spiral allocation avoids single point failures in tracks, cylinders, or platters superblock is immutable: no multi-copy coherence problems FS pays serious attention to rotation on disks without full-track buffers. On disks that have such buffers, it does contiguous allocation. Contiguity is good for reads, but bad for writes if the kernel writes one block at a time. Therefore 4.4 attempts to "cluster" writes by noticing when writes are consecutive and issuing them (at the 30-second synch mark) as a single operation. file system blocks 4096 bytes each (minimum) fragements of 1/2, 1/4, or 1/8 block reduces internal fragmentation Without fragments, >40% of disk would be wasted in typical Unix system requires at most 2 levels of indirection for files up to 2^32 bytes uses triple indirection for larger files (64-bit offsets supported in 4.4) different file systems (superblocks) can have different block size cylinder groups one or more consecutive cylinders on a disk where possible, files are allocated space within a cylinder group principal purpose: keep the data near the inode, to avoid long seeks between the two each group contains bookkeeping information superblock copy inode space bit map for blocks/fragments in cylinder group b adjacent bits represent the fragments of a block no hierarchical bit map; no all-at-once allocation of multi-block regions; rather use rotational layout table to find a block in the same cylinder or cylinder group that has the same rotational position as the preferred next block, if that prefered block is not available. summary count of number of free blocks and fragments of various sizes within the cylinder group at each rotational position kernel has an auxilliary static lookup table indexed by bit pattern that indicates whether the pattern represents a block in a bitmap with free fragments of various sizes bit map for a 2G disk in a system with 1K-byte fragments takes 2M bits = 256K bytes. But that's an on-disk structure; it doesn't have to be in-core at once; the parts of it in active use will reside in the buffer cache. File expansion sufficient space in last fragment/block write the data into that fragment/block file has fragments that can't hold the data, data + fragments > block copy fragments to new block and append data => most efficient user-level writes are a block at a time except at the end of a file; short writes on the part of the user can result in excessive copying; good programs do block-size writes; file system interface exports that size no fragments are used for files with indirect blocks: not worth it files are allowed to have holes; they are defined to hold zeros, but consume no space other than any necessary indirect blocks. During a file operation requested by a single system call, the in-core inode is locked, so the whole operation appears atomic to other processes, even if multiple disk operations are required. Any other process attempting to use the file will block. Layout of inodes and data blocks reserve of 10% free space (default) is maintained to allow flexibility in layout all inodes of files within a dir are kept in same cylinder group if possible new dirs are placed in cylinder groups with smallest number of other directories above average number of free blocks data blocks for a file appear in same cylinder group if possible, at rotationally optimal positions, if applicable filling a cylinder group is bad because all subsequent writes to that file spill to new cylinders all other files in the cylinder must also spill to another heuristic: move to new cylinder group when current file has consumed 25% of current group. No built-in defragmentation mechanism. Studies by Seltzer at Harvard show maximum 30% performance loss to fragmentation after 3 years of continuous service, worst case (news server).