<title>
   Files (CS 4410, Summer 2015)
  </title><link href=../style.css rel=stylesheet><link href=threads.css rel=stylesheet><body><div id=body><h1 id=lecture-18-files>Lecture 18: Files</h1><ul><li>Filesystem API <ul><li>directories, paths, symbolic (soft) vs. hard links<li>virtual filesystems (mounting)<li>opening files, sequential vs. random access, file descriptors</ul><li>Filesystem implementations <ul><li>Blocks, Linked-list file structure, FAT, UFS (Inodes, directories)</ul></ul><h2 id=filesystem-api>Filesystem API</h2><h3 id=files>Files</h3><p><strong> Files </strong> are an abstraction that the OS provides to applications for persistent storage of large amounts of data (typically on a disk).<p>The most common interface is that a file is a unstructured array of bytes optimized for sequential reading or writing. However, some filesystems can provide a sequence-of-records style of interface so that applications can store, retrieve, and query structured data.<p>Most filesystems store some additional <strong> metadata </strong> , such as the length of the file, the file permissions (which users may read, write, or execute which files?), various timestamps (when was the file created, read, or modified?), tags (user-specified hints that make it easier to organize and retrieve files), and many other features.<h3 id=naming-and-directories>Naming and directories</h3><p>Filesystems also need some kind of <strong> naming </strong> scheme, so that persistent data can be located after it is stored. Some filesystems (especially distributed file systems like the Google File System or Amazon's S3) provide a <strong> flat naming </strong> system, in which each file has a unique name.<p>However most filesystems provide a <strong> directory </strong> structure: a directory is a collection of files and other directories, so that the filesystem has a tree structure. Names of files and directories only need be unique within a directory. Files can be identified using an <strong> absolute path </strong> : for example the unix path "/home/mdgeorge/4410/grades.txt" refers to a file called "grades.txt" which is contained in the "4410" directory, which is itself contained in the "mdgeorge" directory, which in turn is contained in the "home" directory, which is in turn contained in the global <strong> "root directory" </strong> (simply called "/").<p>File names in a directory structure can also be specified using a <strong> relative path </strong> if a particular parent directory is clear from context. For example, if my "working directory" is "/home/mdgeorge", then I can refer to the file "4410/grades.txt" instead of the more verbose "/home/mdgeorge/4410/grades.txt".<p>Some filesystems provide the ability to give the same file two different paths, effectively turning the tree-structured filesystem into a graph-structured] filesystem. There are two techniques for this:<ul><li><p>one can create multiple <strong> hard links </strong> to the file; there is no distinction between the "original file" and the links. The file is literally in both directories. If any of the links (including the original) to the file is removed or renamed, the other links are unaffected. The file is only actually deleted when the last hard link is removed. In unix, one can create a hard link using the "ln" command.</p><li><p>one can create <strong> soft links </strong> to an existing file. A soft link contains only the name of the file being linked to; the filesystem knows that operations (such as reading and writing) to the link should instead be performed on the file being linked to. If the target file is moved or removed, the soft link becomes broken, and will cause an error if accessed. Windows calls soft links "shortcuts"; in UNIX, soft links can be created with the "ln -s" command.</p></ul><h3 id=virtual-filesystems>Virtual filesystems</h3><p>Many operating systems provide support for multiple distinct filesystems using the same file API. In UNIX, all filesystems are accessed using a single global directory structure. New filesystems are " <strong> mounted </strong> " at particular paths, and the operating system maintains a table mapping paths to filesystem drivers.<p>When an application accesses a file within a mounted path, the request is handled by the appropriate driver. For example, I may have a Windows filesystem stored on a USB key, containing the files "/happycat.jpg" and "/grumpycat.jpg". I can mount the USB key filesystem to the directory "/media/usb_key" of my laptop's filesystem. When I try to display "/media/usb_key/happycat.jpg", the OS will realize that the folder "/media/usb_key" should be handled by the USB and Windows file system drivers, and forward the request as appropriate.<p>This technology makes it easy to implement <strong> Virtual File Systems </strong> : file systems that are not connected to a disk at all. We have already seen the "/proc" filesystem which provides an interface for traversing the set of PCBs. There are no actual files on a disk anywhere; the virtual files in /proc are generated on the fly by the procfs driver.<p>Virtual filesystems are also useful for handling network drives, temporary files stored in RAM, and even interfaces to some applications.<p>On UNIX, you can see the table of mounted file systems using the "mount" command with no arguments. The mount command can also be used to mount additional filesystems.<h3 id=file-api>File API</h3><p>Since files are conceptually large arrays of bytes, we might imagine an API that takes a file name, a position in the file, and some data, and writes the data into the file (or reads the data out of the file).<p>This would be inefficient for two reasons:<ul><li><p>There is significant overhead involved in finding the file in the filesystem and checking the permissions.</p><li><p>Because of the characteristics of disks, random accesses are much more expensive then sequential accesses, so an API that encourages sequential accesses is preferred.</p></ul><p>For this reason, most file APIs require you to <strong> open </strong> a file before you read or write to it, and maintain a position within the file from which reads or writes proceed.<p>The open system call typically takes in a file name, and a "mode": whether to open the file for reading, writing, appending, etc. It then<ul><li>locates the file in the file system<li>checks that the process has privileges to access the file<li>creates an entry in the process's list of open files containing a reference to the file, the mode it was opened with, and the current position within the file (initially 0).<li>returns a <strong> file descriptor </strong> : the integer index into the table.</ul><p>Subsequent calls to the read or write system calls only pass in the file descriptor. These operations will access the file starting at the current position in the file, and will advance the current position.<p>Typically file system APIs also provide a <strong> seek </strong> operation to move the reading/writing position to a different part of the file.<p>On unix, you can see the set of open file descriptors in the <code>
     fd
    </code> folder in the <code>
     /proc
    </code> entry for the process.<h2 id=implementing-files>Implementing files</h2><p>Files can have arbitrary sizes, but are stored in the sectors of disks, which have a fixed size (such as 512 bytes). For this reason, large files are broken into many <strong> blocks </strong> of data, each the same size as a sector. As an analogy, blocks are to sectors as pages are to frames (but these are very different concepts, don't confuse them!).<p>There are various strategies for connecting multiple blocks together into a file, described below:<ul><li><strong> contiguous allocation </strong><li><strong> linked list </strong><li><strong> file allocation table (FAT) </strong><li><strong> indexed allocation (e.g. inodes) </strong></ul><h3 id=contiguous-allocation>contiguous allocation</h3><p>Store an entire file across many contiguous blocks. Suffers from external fragmentation. Prevents expanding a file once allocated (appending to a file is a common operation)<h3 id=linked-list-allocation>Linked list allocation</h3><p>In addition to containing data, each block contains a pointer to the next block in the file. Makes seek very expensive, because all previous blocks of the file must be read to find any given block.<p>This also prevents applications from using entire blocks to store data, so that (for example) a 1kB file would span 3 blocks instead of two (because the two pointers would take up a few bytes each, pushing it over the sector size).<h3 id=file-allocation-table-fat>File allocation table (FAT)</h3><p>A file allocation table (or FAT) is used by older MS-DOS filesystems, which is often used as a "lowest common denominator" filesystem for interoperation between different operating systems.<p>A FAT filesystem takes the pointers from a linked list structure and puts them all into a single, large table (the FAT). The file allocation table contains one entry for each sector of the entire disk, the entry contains the location of the next block.<p>Because a FAT only contains a few bytes per sector, it is reasonable to cache the FAT for a small disk entirely in memory. This makes it possible to seek (because the entire linked list of a file can be traversed without any disk reads).<p>This is a common pattern seen when talking about disk: by making a data structure (a linked list in this case) more compact, we can cache them entirely in memory. On the timescales involved in disk accesses, operations that do not access the disk (such as traversing a large in-memory linked list) are basically free.<p>The primary downside to FAT is that the FAT scales in the size of the disk; a large disk (which all disks are these days) will have a prohibitively large FAT.<h3 id=indexed-files-unix-files-system-inodes>Indexed files (UNIX files system, inodes)</h3><p>The UNIX File System (UFS) uses a data structure called an index node (inode), and is similar to the schemes used by most modern filesystems.<p>In UFS, each file has a single block called an inode that contains:<ul><li>the metadata for the file, including <ul><li>file length<li>permissions<li>access timestamps<li>bits indicating whether a file is a directory or a soft link<li>a reference count of the number of hard links to the file. The file is removed from the filesystem if this count becomes zero.</ul><li>a small, fixed number of references to <strong> direct blocks </strong> containing the data in the file<li>a small, fixed number of references to <strong> single indirect blocks </strong> . Single indirect blocks are blocks that are entirely filled with references to data blocks.<li>a small, fixed number of <strong> double indirect blocks </strong> which contain references to blocks of references to blocks of data.<li>a small, fixed number of <strong> triple indirect blocks </strong> .</ul><p>This scheme allows the beginnings of files to be accessed using only a small number of disk reads (one for the inode, one for the data), while also supporting large files using indirect blocks.<h2 id=directories-in-ufs>Directories in UFS</h2><p>In the UNIX file system, directories are files: each directory contains an inode and some number of data blocks.<p>The "data" of a directory contains a mapping from file names to inode addresses. This mapping could be stored as a hashtable, an array of fixed-sized entries (if the filesystem only supports fixed-size file names), a list of entries, or a sorted array or list. Because the data can span many blocks, UFS supports directories containing many files or files with very long names.<p>The downside of this design choice is that locating a file in a directory requires at least two disk reads, and potentially more if the directory contains many files.</div>