File System Interface and Directory Structure

A file is a named collection of related information kept on secondary storage. To the user it is the smallest unit of storage: data reach the disk only inside files. The file system gives files names, organises them in directories, controls who may use them, and maps them onto blocks of the storage device.

Programs and users see file attributes and operations, access methods, directory structures from single-level to general graphs, links, path resolution, mounting and protection. Behind open(), the kernel keeps the per-process and system-wide open-file tables. How files are laid out on disk, and how free space is tracked, is in File Allocation Methods and Free-Space Management.

In UNIX-like systems everything except the name is kept in the file's inode (index node); the directory entry maps a name to an inode number. In FAT-style systems the attributes sit in the directory entry itself.

The basic operations are create, write, read, reposition within the file (seek), delete and truncate, plus open and close. open() searches the directory once, copies the file's control block into memory and returns a small integer (a file descriptor); later calls use that descriptor instead of searching by name again.

Three in-memory tables support this:

Independent opens of the same inode create separate descriptions and therefore independent offsets. fork() and dup() share a description, offset and status flags, increasing its reference count. Closing one descriptor drops that reference; the description is released when no references remain, not simply on every close of the file identity.

File locks. A shared lock lets several readers in; an exclusive lock admits one writer. With mandatory locking the OS enforces the lock on every access; with advisory locking, programs must check it themselves (UNIX uses advisory locks by default).

Systems recognise types by extension (.c, .o, .exe) or by a magic number at the start of the file (UNIX executables and scripts). The OS uses the type for executables and archives; for other files the type is mostly a convention kept by applications.

For direct access with fixed-size records of $r$ bytes packed into blocks of $B$ bytes, without letting a record span two blocks, each block holds $\lfloor B / r \rfloor$ records, and record $n$ (counting from 0) is in block $\lfloor n / \lfloor B/r \rfloor \rfloor$.

Example. Records of 120 bytes in 4,096-byte blocks: $\lfloor 4096/120 \rfloor = 34$ records per block, with 16 bytes unused at the end of each block. Record 1,000 is in block $\lfloor 1000/34 \rfloor = 29$, at position 14 within the block, both counted from 0.

An absolute path starts at the root (/home/sumit/notes/os.txt); a relative path starts at the current working directory (from /home/sumit, the same file is notes/os.txt). The entries . and .. name the directory itself and its parent.

Example. Create f (link count 1). ln f g adds a hard link (count 2). ln -s f s creates a symbolic link (count still 2). rm f removes one name (count 1): the data survive and are still reachable as g, but s now dangles and opening it fails.

If links may create cycles, a traversal must remember visited directories or it may never end, and a cycle that is no longer reachable from the root keeps nonzero link counts although nobody can reach it, so its space can be reclaimed only by garbage collection (mark everything reachable, free the rest), which is very slow on a large disk. Forbidding links to directories, or checking for a cycle whenever a link is added, avoids this.

A file system must be mounted before use: attached at a mount point, an existing directory in the already-accessible tree. After mount /dev/sdb1 /mnt/usb, the root of the new file system appears as /mnt/usb, and whatever the directory held before is hidden until the file system is unmounted (Silberschatz 15.2).

Assume an ordinary path with no symbolic links, mount crossings or extra metadata operations, and all intermediate components directories. Nothing is cached, every directory fits in one block, and reading an inode or a block costs one disk access each. For a symbolic link, expand its target and count the extra traversal and any symlink-content reads separately.

A path of $k$ components needs $2k + 1$ accesses to reach the file's inode. For /home/sumit/notes/os.txt ($k = 4$) that is 9 accesses, and reading the first data block makes 10. If the root inode is already in memory, as it usually is, subtract 1. Real systems cache directory entries and inodes, which removes most of these accesses.

Example. Directory entries of 32 bytes in 4 KB blocks: 128 entries per block. A directory of 1,000 files fills 8 blocks (7 full, the last with 104 entries). A lookup of a name that is absent reads all 8 blocks; a lookup of a present name, every name equally likely, reads on average $(128 \times (1 + 2 + \dots + 7) + 104 \times 8)/1000 = 4.416$ blocks.

Access can be controlled per operation: read, write, execute, append, delete, list. An access-control list (ACL) names, for each file, the users and their permitted operations; it is precise but long. UNIX condenses it to three classes, owner, group and others, with three bits each, read (4), write (2) and execute (1).

For a directory, read permits listing the names, write permits creating and deleting entries, and execute (search) permits using the directory in a path. Deleting a file therefore needs write and execute permission on the directory, not on the file. In a sticky directory such as /tmp, an unprivileged user can delete or rename an entry only if they also own the file or the directory (Linux inode(7); chmod(1)); a privileged process (root, or one with CAP_FOWNER on Linux) can still do so.

Common misconceptions.