A Fast File System for UNIX*Marshall Kirk McKusick, William N. Joy†,Samuel J. Leffler‡, Robert S. FabryComputer Systems Research GroupComputer Science DivisionDepartment of Electrical Engineering and Computer ScienceUniversity of California, BerkeleyBerkeley, CA 94720ABSTRACTA reimplementation of the UNIX file system is described. The reimplementationprovides substantially higher throughput rates by using more flexible allocation policiesthat allow better locality of reference and can be adapted to a wide range of peripheraland processor characteristics. The new file system clusters data that is sequentiallyaccessed and provides two block sizes to allow fast access to large files while not wastinglarge amounts of space for small files. File access rates of up to ten times faster than thetraditional UNIX file system are experienced. Long needed enhancements to the pro-grammers’ interface are discussed. These include a mechanism to place advisory lockson files, extensions of the name space across file systems, the ability to use long filenames, and provisions for administrative control of resource usage.Revised February 18, 1984CR Categories and Subject Descriptors: D.4.3 [Operating Systems]: File Systems Management − fileorganization, directory structures, access methods; D.4.2 [Operating Systems]: Storage Management −allocation/deallocation strategies, secondary storage devices; D.4.8 [Operating Systems]: Performance −measurements, operational analysis; H.3.2 [Information Systems]: Information Storage − file organizationAdditional Keywords and Phrases: UNIX, file system organization, file system performance, file systemdesign, application program interface.General Terms: file system, measurement, performance.* UNIX is a trademark of Bell Laboratories.† William N. Joy is currently employed by: Sun Microsystems, Inc, 2550 Garcia Avenue, Mountain View, CA94043‡ Samuel J. Leffler is currently employed by: Lucasfilm Ltd., PO Box 2009, San Rafael, CA 94912This work was done under grants from the National Science Foundation under grant MCS80-05144, and theDefense Advance Research Projects Agency (DoD) under ARPA Order No. 4031 monitored by Naval Elec-tronic System Command under Contract No. N00039-82-C-0235.SMM:05-2 A Fast File System for UNIXTABLE OF CONTENTS1. Introduction2. Old file system3. New file system organization3.1. Optimizing storage utilization3.2. File system parameterization3.3. Layout policies4. Performance5. File system functional enhancements5.1. Long fi le names5.2. File locking5.3. Symbolic links5.4. Rename5.5. QuotasAcknowledgementsReferences1. IntroductionThis paper describes the changes from the original 512 byte UNIX file system to the new onereleased with the 4.2 Berkeley Software Distribution. It presents the motivations for the changes, the meth-ods used to effect these changes, the rationale behind the design decisions, and a description of the newimplementation. This discussion is followed by a summary of the results that have been obtained, direc-tions for future work, and the additions and changes that have been made to the facilities that are availableto programmers.The original UNIX system that runs on the PDP-11† has simple and elegant file system facilities.File system input/output is buffered by the kernel; there are no alignment constraints on data transfers andall operations are made to appear synchronous. All transfers to the disk are in 512 byte blocks, which canbe placed arbitrarily within the data area of the file system. Virtually no constraints other than availabledisk space are placed on file growth [Ritchie74], [Thompson78].*When used on the VAX-11 together with other UNIX enhancements, the original 512 byte UNIX filesystem is incapable of providing the data throughput rates that many applications require. For example,applications such as VLSI design and image processing do a small amount of processing on a large quanti-ties of data and need to have a high throughput from the file system. High throughput rates are also neededby programs that map files from the file system into large virtual address spaces. Paging data in and out ofthe file system is likely to occur frequently [Ferrin82b]. This requires a file system providing higher band-width than the original 512 byte UNIX one that provides only about two percent of the maximum diskbandwidth or about 20 kilobytes per second per arm [White80], [Smith81b].Modifications have been made to the UNIX file system to improve its performance. Since the UNIXfile system interface is well understood and not inherently slow, this development retained the abstractionand simply changed the underlying implementation to increase its throughput. Consequently, users of thesystem have not been faced with massive software conversion.Problems with file system performance have been dealt with extensively in the literature; see[Smith81a] for a survey. Previous work to improve the UNIX file system performance has been done by[Ferrin82a]. The UNIX operating system drew many of its ideas from Multics, a large, high performance† DEC, PDP, VAX, MASSBUS, and UNIBUS are trademarks of Digital Equipment Corporation.* In practice, a file’s size is constrained to be less than about one gigabyte.A Fast File System for UNIX SMM:05-3operating system [Feiertag71]. Other work includes Hydra [Almes78], Spice [Thompson80], and a file sys-tem for a LISP environment [Symbolics81]. A good introduction to the physical latencies of disks isdescribed in [Pechura83].2. Old File SystemIn the file system developed at Bell Laboratories (the ‘‘traditional’’ file system), each disk drive isdivided into one or more partitions. Each of these disk partitions may contain one file system. A file sys-tem never spans multiple partitions.† A file system is described by its super-block, which contains thebasic parameters of the file system. These include the number of data blocks in the file system, a count ofthe maximum number of files, and a pointer to the free list, a linked list of all the free blocks in the file sys-tem.Within the file system are files. Certain files are distinguished as directories and contain pointers tofiles that may themselves be directories. Every file has a descriptor associated with it called an inode.Aninode contains information describing ownership of the file, time stamps marking last modification andaccess times for the file, and an array of indices that point to the data