Unix File System

SMM:05-2 A Fast File System forUNIX TABLE OF CONTENTS 1. Introduction 2. Oldfile system 3. Newfile system organization 3.1. Optimizing storage utilization 3.2. File system parameterization 3.3. Layout policies 4. Performance 5. File system functional enhancements 5.1. Longfile names 5.2. File locking 5.3. Symbolic links 5.4. Rename 5.5. Quotas Acknowledgements References 1. Introduction This paper describes the changes from the original 512 byte UNIX file system to the new one released 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 new implementation. 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 available to 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 and all operations are made to appear synchronous. All transfers to the disk are in 512 byte blocks, which can be placed arbitrarily within the data area of the file system. Virtually no constraints other than available disk space are placed on file growth [Ritchie74], [Thompson78]. When used on the VAX-11 together with other UNIX enhancements, the original 512 byte UNIX file system 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 needed by programs that map files from the file system into large virtual address spaces. Paging data in and out of the 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 disk bandwidth 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 UNIX file system interface is well understood and not inherently slow, this development retained the abstraction and simply changed the underlying implementation to increase its throughput. Consequently, users of the system 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 forUNIXSMM:05-3 operating 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 is described in [Pechura83]. 2. Old File System In the file system developed at Bell Laboratories (the ‘‘traditional’’file system), each disk drive is divided into one or more partitions. Each of these disk partitions may contain one file system. Afile sys- tem never spans multiple partitions.† Afile system is described by its super-block, which contains the basic parameters of the file system. These include the number of data blocks in the file system, a count of the maximum number of files, and a pointer to thefree 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 to files that may themselve