Notes for CSC 256/456, 15 March 2000 ff reading assignment: chapters 10 and 11, and section 17.6.2 (NFS). skim rest of chap. 17. =============================== FILE SYSTEMS Overview What is a file? extension of the address space of a process beyond what you can comfortably put in your address space -- TEMPORARY FILES non-volatile sotrage that survives the execution of an individual program -- PERSISTENT FILES because they have names in a global name space, both temporary and persistent files are useful for inter-process sharing Files typically support the following operations: create - associate a name with a file delete - remove the file rename - associate a new name with a file (may or may not be semantically equivalent to creating a new file, copying to it, and destroying the old one -- certainly will be faster) open - create cached context that is associated implicitly with future reads and writes write - store data in a file read - access the data associated with a file close - discard cached context seek - random access to any record or byte within a file generally affects cached 'open' context map - put into address space, where available for ordinary loads and stores. Advantages: convenience, speed (avoidance of kernel overhead, esp. for random access), use of pointers. Disadvantages: semantic problems with lengths that aren't a multiple of the page size, appending to files, consistency with open/read/write interface, consistency during sharing, multitude of problems once pointers appear in files. File system issues: naming - A file that is to be used by a process other than its creator has to have a name so it can be distinguished from all other files. (Note similarity to naming processes for IPC.) intra-file structure - The system might choose to impose structure on the collection of data within a file. (Note similarity to strongly-typed programming languages, in which data is organized into type classes.) FS organization - what implementation do we use that makes efficient use of the disk in the presence of a particular organization? concurrent access - A file can be accessed by more than one process at a time. Some mechanism is needed to ensure that each process gets a consistent view of the file. (Concurrency control problems for files are similar to the problems of concurrent access to shared data.) recovery - Sometimes files are accidentally removed. There should be some mechanism for recovering from such accidents. (Note similarity to the problem of recovering from accidental process destruction when a processor fails.) protection - Not all files can be accessed by all processes. Some mechanism is needed to decide which processes may access which files. (Note similarity to mechanisms that help decide with processes may affect, eg destroy, other processes.) File system software organization open files represented by in-core data structure pointers to structures found in per-process tables processes refer to open files using indices into those tables these are "file descriptors" -- small integers several modern OSes (Unix variants, NT) support multiple file system types via a vnode (virtual node) interface: file system and open file data structure contains vtables with pointers to the kernel functions implementing (open, delete, rename, ...) and (read, write, seek, ...). Exists mechanism to install code for a new file system w/out access to full kernel source. Allows you to, say, plus AFS into Solaris if you want. ------------------------ Naming Files Using Directory Structures Directory - maps names to files. Directories may themselves be files. Single level (flat) directories: one master directory is used for all files. No two files may have the same name. Restrictions can be mitigated to some degree by giving file name multiple components, at least one of which is userid. (This approach was used in Exec-8 on Univac 1100 series.) Entire directory must be searched to find a file. Dynamic reordering can help, but finding all files with particular attribute requires exhaustive search. Satisfactory for small disks containing few files (CP/M). Two level directories: each user is assigned a private single level (flat) directory. Complete names for a file consist of a user name and file name. Isolates processes along user boundaries only. Users with large numbers of files have all the problems of the single level directory. Hierarchical directories: a generalization of the two-level directory. Each file system is assigned the root of a tree. Users are assigned subtrees, within which they may create their own subdirectories (Unix, MacOS, VMS, Windows). Each entry within a directory has a bit to distinguish files from other directories. File names may be relative (to the current directory or some specified directory) or absolute (from the root of the tree). Acyclic graph directories: generalization of hierarchical directories that allows sharing of files. In a strict tree, two directories could not contain the same file since it would then have two parents. Copying the file does not really solve the problem (both for space reasons and the fact that changes are not visible in both copies). One implementation uses "symbolic (soft) links" (Unix) or "aliases" (Mac), special directory entries that actually refer to another directory entry. In this case, the original and the copy can be distinguished. Another implementation duplicates a directory entry in two places. In this case, the two are not distinguishable. [Example: "real" or "hard" links in Unix. No longer used much; can't cross file systems. Symbolic links are slower, though if you use them often a good file system will tend to have them cached. Hard and soft links have different semantics. Sometimes it matters. If you delete and then re-write a file that had hard links, the other names don't see your changes. They do if you use symlinks. This causes problems in Unix for RCS. Tanenbaum notes that you can get charged for a file in some systems even after you delete it if somebody else has a hard link. Unix doesn't allow hard links to directories (except for . and ..), to prevent cycles. Symlinks can lead to cycles. Unix assumes it has a cycle if it follows more than 8 symlinks in translating a path name. ------------------------ File Types Files may be typed or untyped. Being typed means you aren't allowed to do certain things to certain files -- e.g. compile data files. Enforcing file types in the OS is can make certain things easier, especially for beginners, but it makes life harder for "power users", and leads to some semantic complications (E.g. a pascal program may be text, source, or data, depending on what you want to do with it.) TOPS-20 had typed files -- the "extension" part of the file name determined what the OS would let you do. Unix and VMS use extensions as *coventions* only. MacOS doesn't use extensions, but has an "owner" and "type" for each file, to help control things like what happens when you double-click on the file's icon. Also, since MacOS is an open system, it lets you change the type and owner, though none of the Apple-provided software does that; you have to use something that "disobeys" the rules. Files may be structured or unstructured. Unix files are unstructured -- a file is just a sequence of bytes, though device drivers usually read and write entire physical blocks, for efficiency reasons. A CP/M file is a sequence of 80-character records. Some mainframes use sequences of variable-size records, often with indices. Non-indexed files generally do not permit insertions or deletions in the middle. MacOS and BeOS files have two "forks," one of which contains unstructured data; the other of which contains a collection of structured "resources." Files may be accessed sequentially, randomly (by index), or by key. Sequential access (magnetic tapes): the file is read/written sequentially, record 1, 2, 3... Files are written at the end (append). The rewind operation allows a file to be read again. The position in the file to be read or written is implicitly the current position based on previous operations. Some (very few) tape drivers permit writing in the middle of the tape. Direct (random) access (disks): read/write operations may be applied to any of the addressable units in a file (bytes or records). The position in the file may be implicit (based on previous operations) or explicitly provided. Indexed sequential access (IBM's ISAM): a master index is maintained for each file containing pointers to a secondary index. The secondary index contains pointers to actual file blocks. Each file is sorted on some key. A binary search on the master index yields the correct secondary index; a binary search on that index yields the correct block. The block is searched sequentially for the correct record. This is a B-tree with a maximum depth of 2. B-trees are generally great for indexed files because they're so fat -- they minimize the number of disk accesses you have to do to find something. You can build this sort of index structure in user space, on top of simpler files, but you'll have to make several kernel calls to achieve the effect of a single ISAM operation, so it probably won't be as fast. On the other hand, most database experts don't like kernel-implemented indexing: it's never quite what they want, and working around its not-quite-right-ness is slower than doing it all yourself. ------------------------ Device Space Management General principles Disk blocks are numbered => complex structures can be created using disk block numbers as pointers Each file must have a readily available handle for its related complex structures Redundant information stored on the disk allows the system to recover from "confused" states caused by system crashes Even though the basic unit is the block, entire tracks or cylinders can be allocated to ensure a file is stored contiguously on the disk Consecutive blocks of a file need not be stored in consecutive sectors to reduce rotational delay (skewing), though this matters most on devices without full-track buffers Disk structure information can be cached in memory for efficient allocation and search Hints can be used for efficient operation; checking hints must be fast, but incorrect hints may require time to recover the truth Choosing the size of an allocation unit (block size) The size of a sector (hardware) is a reasonable minimum block size for the file system but need not be the actual block size By reading and writing sectors in groups of a fixed size, we can implement any (rough magnitude) block size we like, thereby increasing throughput, but decreasing space utilization (ie, internal fragmentation results) Free block allocation using bit maps Bit maps can be constructed for any unit of allocation: cylinder, track, block. CONTIGUOUS FILES: If we know the size of a file and want to maximize clustering then we can allocate entire tracks or cylinders to the file and allocate the file consecutively on the disk maintain a cylinder bit map and a separate track bit map files that need a cylinder or more, go to the cylinder map fine grain allocation marks the cylinder map and uses the track map no structure is needed since a file resides in consecutive tracks directories only need to know start and length random access computations are simple clustering is perfect wastes space if many files need less than an allocation unit average file size in unix env is 1K common track size is > 32K file growth may require copying the file to new disk area SCATTERED FILES: If files grow or space is at a premium, we can allocate storage using the smallest addressable unit, the block. each block has an entry in the bit map files need not be allocated consecutive blocks it must be possible (efficiently) to determine the address of each block files can grow without copying, since blocks are allocated anywhere internal (track) fragmentation is reduced 8G disk with 4KB blocks needs 2M bits = 256K bytes of bit map prefered method IF map fits in memory Unix ffs and Linux ext2 use bit maps, but try to find groups of nearby bits to allocate to the same file. Bit vector grows with size of disk. MacOS HFS uses bit maps. When you go to big disks it uses big blocks to avoid making the map bigger. Leads to terrible internal fragmentation, hence the need for HFS+. Free block allocation using a free list A free list of all unallocated blocks on the disk is kept. if kept in core, may require more space than a bit map UNLESS disk is nearly full (you may think "most disks ARE nearly full", but they have to be REALLY REALLY full to hit the cross-over point) free list is usually kept on disk the first few nodes of the free list are cached in memory most requests can be satisfied from the memory cache. typically the list is two-level: first free block is an index containing pointers to N free blocks and to second free index block. (note tension with desire to allocate *old* free blocks, in order to minimize confusion in the event of a crash) File block organization Once blocks are allocated to files, how do we organize the blocks? Linked list A file is represented by a pointer to its first block. Each block contains a pointer to the next block in the file. random access is expensive data blocks not a power of 2 (pointer takes space in disk block) File Allocation Table (FAT) Each disk partition has an associated table (FAT) describing it. Table (stored in memory) contains an entry for each block. A file is represented by the block number of its first block. Each entry gives the block number of the next block in the same file (ie, the linked list is used, but stored in memory, organized by blocks). random access is still a little slow, but not as bad as before FAT's for large disks take up too much space in memory pointers for all files are mixed into one table Unix inode structure Build a index structure for each file. number of links to file owner's uid, gid times: access, modification, inode modification file size 12 disk block numbers single indirect pointer double indirect pointer triple indirect pointer Inodes are fetched from disk on an "open" and kept in memory until the file is "closed". Inodes are pre-allocated on disk (fixed in number), and spread around so we can usually find one close to the data blocks it's going to reference. Any file of size 12 blocks or less can be referenced using just the inode. Larger files (depending on file block size and disk address size) can be referenced indirectly using the single indirect pointer to a block of disk block numbers. Files larger still require 2 levels of indirection. The triple indirect pointer handles files up to 16GB (assuming 4K disk blocks). Directory lookups start at the FS root, which is at a known location on the disk (and is usually cached in memory). To look up a file /u/scott/courses/456/Lecture_notes/10-files, we start at /. The root directory contains a set of entries corresponding to files and directories under root. From this we find the i-node for /u. Looking in the inode tells us the block in which to find the dir /u. Using that block/dir, we look up scott. This gives us the inode for /u/scott. We repeat the process, until we find the inode for the file 10-files. This inode is kept in memory until we close the file. Most OSes contain a cache of path names. If you delete or rename a file you have to trash any entries in the cache that are invalidated by the change. Sharing Files Sharing among directories. Recall discussion of hard and soft links, above. In most systems directory entries do not contain information about where the file is stored on disk. That information is maintained in a separate structure pointed to by the directory entry (such as an inode). With hard links, two different directory entries can point to the same structure. dangling references can occur if the file is deleted referencing counting inodes works, but screws up accounting since a file's owner may have deleted the file but it remains allocated until the reference count reaches zero A symlink, on the other hand, is a special file containing the path name of the real file. The OS must translate access operations on the LINK file into access operations on the real file. only the owner knows the inode only the owner can remove the file removing the symbolic link has no effect on the file extra overhead is needed for each use of the symbolic link Sharing among simultaneous users. What happens when two people try to access a file simultaneously, at least one of them to write? Systems differ a lot wrt consistency semantics. Often it is assumed that concurrent access to a file undergoing modification is a programming/usage error. Tools like RCS are designed to prevent it. Database systems introduce locking protocols to control it. Memory-mapped interfaces sometimes (e.g. in Unix) have an explicit 'synch' operation to force consistency (c.f. flush). Maintaining Consistency On a crash, data that hasn't been written to disk can be lost (unless you have battery-backed RAM or something). Systems that really care about data integrity don't allow an operation to complete until the data is written to stable (redundant, non-volatile) storage. Other systems just lose data. Unix, for example, flushes everything to disk once every 30 seconds, so you can lost up to 30 sec of data. Even if you're willing to lose data in a crash, you generally aren't willing to lose the organizational integrity of the file system. You have to be able to make sense out of things when you re-boot. The problem File system operations usually require that several blocks be read, modified, and written together. A file system can become inconsistent if the system crashes when part of the modifications have been written, but others have not. Observation File systems contain redundant information. For example, a free block is (a) on the free list and (b) not in any file. The opposite holds for a data block. Scanning the entire disk checking redundant info helps to find any inconsistencies. Utilities: Windows/DOS ScanDisk; MacOS Disk First Aid or Norton Disk Doctor; Unix fsck One solution Block consistency: Search all inodes and count occurrences of each block in a file Search free list and count occurrences of each block (1) blocks not marked free or in a file return to free list (2) block marked both free and in a file remove from free list (3) block marked in a file multiple times make new copies of the block and change inode entries (4) block marked free multiple times (can happen if your free list is really a list of blocks containing pointers to free blocks. This is a common representation; it allows you to identify a bunch of free blocks with a minimum of disk operations) rebuild free list File consistency Search all directories to reconstruct link counters for inodes For each file, increment counter associated with its inode Compare computed link count with value in inode (1) link count too high could result in wasted space (unclaimed inodes) so reset link count to lower value (2) link count too low could result in dangling reference to inode so reset link count to higher value Backups periodic full dumps more frequent (e.g. daily) incremental dumps off-site storage distributed file systems issues reliability availability consistency, esp. given partitions, disconnected operation, partial failures heterogeneity performance NSF -- Sun. Ad-hoc standard. Essentially stateless. Correctness problems. Performance problems. AFS -- CMU, Transarc. Whole file caching (replication). More general protection scheme. Sprite -- Berkeley. Partial file caching. Good performance. Coda -- CMU. Specifically addresses disconnected operation (e.g. of notebook computers). Tries to anticipate working sets, merges updates upon re-connection. I'll spend more time on this subject later if time permits.