File systems: concepts and directories

Why it exists

Programs and users need to keep data after the program ends and to share it. The operating system provides the file, a named collection of related bytes, and the directory, a structure that names files. It hides the disk: nobody asks for "block 4172 of the third cylinder", they ask for /home/ann/notes.txt. This page covers what a file is and what operations exist, how directories are organised and how path names are resolved, how links and protection work, and how a file system is layered. The next page, file allocation, covers how a file's blocks are placed on disk.

Prerequisites

No other concept page is needed. File operations are reached through system calls (open, read, write, close), and the files live on a disk whose requests are scheduled as in disk scheduling.

Precise definitions

File. A named collection of related information on secondary storage; to the user the smallest unit of logical storage. The OS sees a file as a sequence of bytes (or records) and does not interpret it, except for a few types (directories, executables).

File attributes (metadata, kept in the directory entry or in an inode): name (the human-readable form), identifier (a unique number, such as the inode number), type, location (where its blocks are), size, protection (who may read, write, execute), and times (creation, last modification, last access), and the owner.

File operations. The OS provides: create (find space, make a directory entry), write and read (at the current file position, which the system keeps as a file pointer per open file), reposition (seek), delete (release the space and remove the entry), truncate (erase the contents, keep the attributes).

Open-file tables. To avoid searching the directory on every access, a file is opened first. The system keeps:

• a system-wide open-file table: one entry per open file, with a copy of its inode and an open count (the number of processes that have it open), so that the entry is removed when the count falls to zero;
• a per-process open-file table: an entry for each file the process has open, with the file pointer, the access mode, and a pointer to the system-wide entry. The index in this table is the file descriptor.

Access methods.

• Sequential access: information is processed in order, one record after another; the file pointer advances automatically. Read next, write next, rewind.
• Direct (relative) access: a file is a set of fixed-size records numbered $0, 1, \ldots$; any record can be read or written by number, in any order. For records of $r$ bytes, record number $n$ starts at byte $n \cdot r$ (or $(n - 1) \cdot r$ if numbering starts at 1). This is the model for databases.
• Indexed access: an index (a small file) maps keys to records, and the data are found through it.

Directory. A file that holds the entries (name, attributes or inode number) of the files it contains. Operations: search, create, delete, list, rename, traverse. Structures:

Path names. An absolute path starts at the root (/home/ann/notes.txt); a relative path starts at the current directory of the process (notes.txt, ../ann/todo). The special names . (this directory) and .. (the parent) are entries in every directory.

Resolving a path name. To open /a/b/c the system starts at the root directory and, for each component, reads the data of the current directory to find the component's inode number and then reads that inode. If directories fit in one block, each component costs two disk accesses (the directory block, then the inode) and, with the root inode already in memory, reading the first data block of the file adds one: a path of $d$ components costs $2d + 1$ disk accesses (without caching). A relative path starts from the current directory and saves the components above it.

Links. A hard link is an additional directory entry that points to the same inode; all names are equal, the inode keeps a link count, and the file's data are freed only when the count falls to 0. A hard link cannot cross file systems and normally cannot name a directory. A symbolic (soft) link is a small file that contains a path name; opening it follows the path. If the target is removed, the link dangles (it points to nothing); removing the link does not affect the target.

Protection. Controlling who may do what to a file. Access-control list (ACL): for each file, the list of users and the access they have. Unix permission bits: three groups of three bits (read, write, execute) for the owner, the group and others, written in octal: the mode 0755 means rwxr-xr-x (owner all, others read and execute); 0640 is rw-r-----. For a directory, read lets you list, write lets you create and delete entries, execute lets you pass through it.

Mounting. Attaching a file system to a point (the mount point, an existing directory) of the tree; the root of the mounted file system then appears there.

Layers of a file system. From the top: the application programs; the logical file system (directories, names, protection, file control blocks); the file-organisation module (maps logical blocks to physical blocks and manages free space); the basic file system (issues generic read and write commands to the device driver for a block address); I/O control (device drivers and interrupt handlers); the devices.

Directory implementation. A linear list of entries (simple, searching is $O(n)$) or a hash table (fast lookup, collisions to handle, fixed size problems).

On-disk layout (a Unix-style file system). A boot block (code to start the operating system), the superblock (the size of the file system, the numbers of inodes and blocks, free-block information), the inode list (an array of inodes), and the data blocks (file data and directory data).

How it works

The animation resolves path names against a small file system: the inode table (inode number, type, first data block) and the contents of four directory blocks. The root is inode 2 and is already in memory. Each component costs one directory-block read (the highlighted directory row) and one inode read (the highlighted inode row). Three paths are resolved: /home/ann/notes.txt takes 7 disk accesses ($2 \times 3 + 1$); /home/bob/todo fails after 3 accesses because the directory block of /home has no entry bob; and the relative path notes.txt from the current directory (/home/ann) takes just 3.

Worked examples

#define _POSIX_C_SOURCE 200809L
#include <fcntl.h>
#include <stdio.h>
#include <string.h>
#include <sys/stat.h>
#include <unistd.h>
 
/* real file system calls in a fresh temporary directory: names are directory entries that point to an inode */
static void show(const char *what, const char *path) {
    struct stat st;
    if (stat(path, &st) != 0) { printf("%-32s -> does not exist (or points to nothing)\n", what); return; }
    printf("%-32s -> link count %d, size %ld\n", what, (int)st.st_nlink, (long)st.st_size);
}
 
int main(void) {
    char dir[64];
    snprintf(dir, sizeof dir, "/tmp/fsdemo%ld", (long)getpid());
    if (mkdir(dir, 0700) != 0) return 1;
    char file[256], hard[256], soft[256];
    snprintf(file, sizeof file, "%s/notes.txt", dir);
    snprintf(hard, sizeof hard, "%s/todo", dir);
    snprintf(soft, sizeof soft, "%s/soft", dir);
    int fd = open(file, O_CREAT | O_WRONLY, 0600);
    if (fd < 0 || write(fd, "hello", 5) != 5) return 1;
    close(fd);
    show("after creating notes.txt", file);
    if (link(file, hard) != 0 || symlink(file, soft) != 0) return 1;
    struct stat a, b, c;
    stat(file, &a); stat(hard, &b); lstat(soft, &c);
    printf("hard link shares the inode: %d; symbolic link has its own inode: %d\n", a.st_ino == b.st_ino, c.st_ino != a.st_ino);
    show("after link(notes.txt, todo)", file);
    unlink(file);
    show("after unlink(notes.txt): todo", hard);
    show("after unlink(notes.txt): soft", soft);
    chmod(hard, 0640);
    stat(hard, &a);
    printf("permission bits after chmod 0640: %o (owner rw-, group r--, others ---)\n", (unsigned)(a.st_mode & 0777));
    unlink(hard); unlink(soft); rmdir(dir);
    /* disk accesses to open a file by path name: a directory block and an inode for each component, plus the first data block */
    const char *paths[3] = {"/home/ann/notes.txt", "/usr/lib/libc.so", "/a/b/c/d/e"};
    for (int i = 0; i < 3; i++) {
        int comps = 0;
        for (const char *p = paths[i]; *p; p++) if (*p == '/') comps++;
        printf("%s: %d components, %d disk accesses\n", paths[i], comps, 2 * comps + 1);
    }
    return 0;
}

after creating notes.txt         -> link count 1, size 5
hard link shares the inode: 1; symbolic link has its own inode: 1
after link(notes.txt, todo)      -> link count 2, size 5
after unlink(notes.txt): todo    -> link count 1, size 5
after unlink(notes.txt): soft    -> does not exist (or points to nothing)
permission bits after chmod 0640: 640 (owner rw-, group r--, others ---)
/home/ann/notes.txt: 3 components, 7 disk accesses
/usr/lib/libc.so: 3 components, 7 disk accesses
/a/b/c/d/e: 5 components, 11 disk accesses

Cheat box

Traps and GATE patterns

Connections

Reading and writing a file are system calls; the open-file tables belong to the process and the system, like the PCB of a process. How the blocks of a file are found on the disk is file allocation, and the order in which disk requests are served is disk scheduling.

PYQs

Consider
a
linear
list
based
directory
implementation in a file system. Each directory is a
list of nodes, where each node contains the file
name along with the file metadata, such as the list
of pointers to the data blocks. Consider a given
directory foo.
 Which of the following operations will necessarily
require a full scan of foo for successful completion?

Self-check

Revision card

References