Practical 10 continued: a Simple File System

Linux uses indexed allocation, and the index is called the inode. A classical Unix inode holds twelve block numbers directly, then a pointer to a block of block numbers, then a pointer to a block of pointers to blocks of block numbers, and one more level after that. Small files need no indirection at all; large files pay for it. The program below is the first twelve, simplified to six.

The free space bitmap

The other half of the design: how does the file system know which blocks are free?

A bitmap is one bit per block, 1 for used and 0 for free. Finding a free block is a scan for a zero bit, which on real hardware is fast because whole words can be tested at once. Finding n consecutive free blocks is also easy, which matters for contiguous allocation. The cost is the size: a 1 terabyte disk with 4 kibibyte blocks needs 32 mebibytes of bitmap.

A free list is the alternative: each free block holds the number of the next free block. It costs no extra space at all, since the pointers live in blocks nobody is using, and it cannot find consecutive blocks without walking the whole list.

The program uses a bitmap and prints it as text, one character per block, so that the allocation can be watched.

The program

#include <stdio.h>
#include <string.h>

#define BLOCKS      32        /* blocks on our little disk            */
#define BLOCK_SIZE  16        /* bytes in one block                   */
#define FILES        8        /* entries the directory holds          */
#define NAME_LEN    12
#define INDEX_MAX    6        /* blocks one file may have             */

/* the disk: an array of blocks, which is what a real disk is to the
   file system: a numbered sequence of fixed-size pieces */
static char disk[BLOCKS][BLOCK_SIZE];

/* the free space bitmap: one character per block, '.' free, '#' used */
static char bitmap[BLOCKS + 1];

/* one directory entry, which in a real file system is the inode */
struct entry {
    char name[NAME_LEN];
    int  used;
    int  size;                     /* in bytes                        */
    int  count;                    /* how many blocks it holds        */
    int  index[INDEX_MAX];         /* the block numbers: the index block */
};

static struct entry directory[FILES];

static void format(void)
{
    memset(disk, 0, sizeof disk);
    memset(directory, 0, sizeof directory);
    for (int b = 0; b < BLOCKS; b++) bitmap[b] = '.';
    bitmap[BLOCKS] = '\0';
    bitmap[0] = '#';               /* block 0 is the directory itself */
    printf("formatted: %d blocks of %d bytes, %d directory entries\n",
           BLOCKS, BLOCK_SIZE, FILES);
}

static void show_bitmap(const char *why)
{
    int free_blocks = 0;
    for (int b = 0; b < BLOCKS; b++) if (bitmap[b] == '.') free_blocks++;
    printf("  bitmap %s  (%d of %d blocks free)\n", bitmap, free_blocks, BLOCKS);
    (void) why;
}

static int find(const char *name)
{
    for (int i = 0; i < FILES; i++)
        if (directory[i].used && strcmp(directory[i].name, name) == 0) return i;
    return -1;
}

static int allocate(void)
{
    for (int b = 1; b < BLOCKS; b++)
        if (bitmap[b] == '.') { bitmap[b] = '#'; return b; }
    return -1;
}

static int create(const char *name, const char *data)
{
    if (find(name) >= 0) {
        printf("create %s: a file of that name already exists\n", name);
        return -1;
    }
    int slot = -1;
    for (int i = 0; i < FILES; i++) if (!directory[i].used) { slot = i; break; }
    if (slot < 0) {
        printf("create %s: the directory is full\n", name);
        return -1;
    }

    int len = (int) strlen(data);
    int need = (len + BLOCK_SIZE - 1) / BLOCK_SIZE;   /* round UP */
    if (need == 0) need = 1;
    if (need > INDEX_MAX) {
        printf("create %s: %d bytes needs %d blocks and a file may hold %d\n",
               name, len, need, INDEX_MAX);
        return -1;
    }

    struct entry *e = &directory[slot];
    memset(e, 0, sizeof *e);
    for (int k = 0; k < need; k++) {
        int b = allocate();
        if (b < 0) {
            for (int j = 0; j < k; j++) bitmap[e->index[j]] = '.';  /* give it back */
            printf("create %s: the disk is full\n", name);
            return -1;
        }
        e->index[k] = b;
        int from = k * BLOCK_SIZE;
        int take = len - from;
        if (take > BLOCK_SIZE) take = BLOCK_SIZE;
        if (take > 0) memcpy(disk[b], data + from, (size_t) take);
    }
    snprintf(e->name, sizeof e->name, "%s", name);
    e->used = 1;
    e->size = len;
    e->count = need;

    printf("create %-9s %3d bytes in %d block(s):", name, len, need);
    for (int k = 0; k < need; k++) printf(" %d", e->index[k]);
    printf("\n");
    show_bitmap("after create");
    return slot;
}

static void read_file(const char *name)
{
    int i = find(name);
    if (i < 0) {
        printf("read %s: no such file\n", name);
        return;
    }
    struct entry *e = &directory[i];
    printf("read   %-9s [", name);
    int left = e->size;
    for (int k = 0; k < e->count; k++) {
        int take = left > BLOCK_SIZE ? BLOCK_SIZE : left;
        printf("%.*s", take, disk[e->index[k]]);
        left -= take;
    }
    printf("]\n");
}

static void delete_file(const char *name)
{
    int i = find(name);
    if (i < 0) {
        printf("delete %s: no such file\n", name);
        return;
    }
    struct entry *e = &directory[i];
    printf("delete %-9s freeing block(s):", name);
    for (int k = 0; k < e->count; k++) {
        printf(" %d", e->index[k]);
        bitmap[e->index[k]] = '.';
        memset(disk[e->index[k]], 0, BLOCK_SIZE);
    }
    printf("\n");
    memset(e, 0, sizeof *e);
    show_bitmap("after delete");
}

static void list(void)
{
    printf("directory\n");
    printf("  name        bytes blocks  block numbers\n");
    int files = 0, used = 0;
    for (int i = 0; i < FILES; i++) {
        if (!directory[i].used) continue;
        struct entry *e = &directory[i];
        printf("  %-11s %5d %6d ", e->name, e->size, e->count);
        for (int k = 0; k < e->count; k++) printf(" %d", e->index[k]);
        printf("\n");
        files++;
        used += e->count;
    }
    if (files == 0) printf("  (empty)\n");
    printf("  %d file(s), %d block(s) of data\n", files, used);
}

int main(void)
{
    format();
    show_bitmap("after format");
    printf("\n");

    create("notes.txt", "Computer Science Practical 3, Module 1");
    create("roll.txt",  "2331");
    create("marks.csv", "maths,78\nphysics,65\nchem,92\n");
    printf("\n");

    list();
    printf("\n");

    read_file("notes.txt");
    read_file("marks.csv");
    read_file("absent.txt");
    printf("\n");

    delete_file("roll.txt");
    printf("\n");

    create("new.txt", "this one reuses the block roll.txt gave back");
    printf("\n");

    list();
    return 0;
}

Reading the output, which is where the design shows

The bitmap starts with block 0 already used. Block 0 is the directory itself. Every real file system reserves its first blocks for its own structures, and a student who allocates block 0 to a file has overwritten the directory.

38 bytes took 3 blocks. The blocks are 16 bytes, and 38 bytes needs three of them: two full and one with 6 bytes in it. The arithmetic is worth writing out, because getting it wrong is the commonest bug in this exercise:

int need = (len + BLOCK_SIZE - 1) / BLOCK_SIZE;    /* rounds UP */

38 / 16 in C is 2, because integer division throws the remainder away, and a program that uses it loses the last 6 bytes of every file. Adding BLOCK_SIZE - 1 first rounds up: 38 + 15 is 53, and 53 divided by 16 is 3 and a bit, which integer division cuts to 3.

Note the form that is written there. Putting an equals sign between 53 over 16 and 3 would be wrong, because 53 over 16 is 3.3125; what is true is that C's integer division of 53 by 16 gives

1. The distinction matters in a journal, and the arithmetic checker on this book refused two

earlier drafts of this paragraph for exactly that reason.

The last block is not full, and that space is lost. Three blocks of 16 bytes is 48 bytes of disk for a 38 byte file, so 48 - 38 = 10 bytes are wasted. That is internal fragmentation, and it is unavoidable with fixed blocks. For new.txt it is 48 - 44 = 4 bytes. On a real file system with 4 kibibyte blocks, a thousand files of one byte each occupy 4 megabytes.

new.txt got blocks 4, 7 and 8, which are not consecutive. Block 4 is the one roll.txt gave back when it was deleted, and blocks 7 and 8 were the next free ones. That is indexed allocation working: the file is scattered and the index block records where the pieces are, so nothing has to be moved and no space is left unusable. Under contiguous allocation the single free block at 4 would have been too small for this file and would have stayed empty.

Deleting freed the blocks and cleared the entry. The bitmap went from seven used blocks to six, with a gap in the middle: ####.##. The blocks are also wiped, which a real file system usually does not do, and that is why deleted files can often be recovered.

Reading a missing file says so. read absent.txt: no such file, rather than crashing or printing rubbish. Every operation in the program checks first, and there are five such checks: the name already exists, the directory is full, the file is too large for its index, the disk is full, and the file does not exist.

The rollback in create, which is worth copying

If the disk fills up halfway through allocating a file, the blocks already taken must be given back:

int b = allocate();
if (b < 0) {
    for (int j = 0; j < k; j++) bitmap[e->index[j]] = '.';   /* give them back */
    printf("create %s: the disk is full\n", name);
    return -1;
}

Without those two lines a failed create leaks blocks: they are marked used, no file owns them, and nothing will ever free them. It is exactly the leak of a shared memory segment in [Practical 1: Process Communication using Shared Memory], and the same principle applies: an operation that fails halfway must undo what it has already done.

The directory, which is also the inode here

In this program one structure holds both the name and the block numbers:

struct entry {
    char name[NAME_LEN];
    int  used, size, count;
    int  index[INDEX_MAX];     /* the index block, inline */
};

Unix splits those two things, and knowing why is worth a mark. A directory entry holds only the name and an inode number; the inode holds the size, the permissions, the times and the block numbers. The split is what makes a hard link possible: two names in two directories pointing at one inode, so the file has two names and one set of blocks. The inode keeps a count of how many names point at it, and the blocks are freed only when that count reaches zero.

That is why rm on a file with two hard links does not free any space, and why the system call is called unlink and not delete.

What a real file system adds

The program is about eighty lines and a real one is hundreds of thousands. The differences worth naming:

The two most important of those are the last two but one.

A journal. Creating a file changes three things: the bitmap, the directory and the data. If the machine loses power between the first and the second, the disk is inconsistent: a block is marked used and no file owns it. A journalling file system writes what it is about to do into a log first, so that after a crash the log can be replayed or undone. ext4 does this, which is why a Linux machine that loses power usually comes back in seconds instead of running a long check.

The cache. Every read in this program goes to the array. In a real system it goes to the page cache in memory first, and reaches the disk only if it is not there. That is why reading the same file twice is far faster the second time, and it is the reason the page replacement algorithms of [Practical 9: Memory Management, FIFO and LRU Page Replacement] apply to file data as well as to program memory.

Procedure

1. Write the program. Compile with gcc -Wall -Wextra -o fs fs.c and run it.
2. Follow the bitmap through the run and write down which blocks each file holds.
3. Work out the internal fragmentation for each of the four files: blocks times 16, minus the

size.

1. Change the rounding to len / BLOCK_SIZE and run it again. Read the end of notes.txt and see

what was lost.

1. Create files until the directory is full, and then until the disk is full, and check that both

messages appear and that no blocks are leaked. Print the bitmap afterwards to be sure.

1. Add a write operation that appends to an existing file, allocating another block when the

last one is full.

1. Add a second directory, so that a file has a path of two parts. That is the step from a flat

file system to a tree.

Result

A file system was designed and implemented over a simulated disk of 32 blocks of 16 bytes, with a free space bitmap, a flat directory of 8 entries, and indexed allocation of up to 6 blocks a file. Create, read, list and delete were implemented, each with its error cases checked. A 38 byte file was seen to occupy three 16 byte blocks with 10 bytes of internal fragmentation, and a file created after a deletion was seen to reuse the freed block and two others that were not adjacent to it, which is indexed allocation doing what contiguous allocation cannot.

Where marks are lost

• Integer division for the block count. 38 / 16 is 2 and the last bytes of every file are

lost. It must round up.

• Allocating block 0, which in this design holds the directory.
• Not freeing the blocks on delete, so the disk fills with blocks nothing owns.
• Not rolling back a failed create, which leaks blocks the same way.
• No check for a duplicate name, so two directory entries claim the same name and only one can

ever be found.

• Not checking that the file fits in the index. With six block numbers the largest file is 96

bytes here, and a program that writes a seventh number writes past the end of the array.

• Printing the whole last block on read, including the bytes after the end of the file. The

size in the directory is what says where the file stops.

• Confusing internal with external fragmentation. Internal is the unused tail of the last

block; external is free space broken into pieces too small to use, which indexed allocation does not suffer from.

For the journal

Write the aim, MU's own wording, and the design first: the block size, the number of blocks, the layout of a directory entry, and which block holds the directory. Then the program, and the whole run with the bitmap after every operation, because the bitmap is the evidence that the allocation works. Add the internal fragmentation for each file as a subtraction, and one sentence on why new.txt got blocks 4, 7 and 8 rather than three consecutive ones. The conclusion: a file system is a free space map, a directory and a rule for recording which blocks a file owns, and indexed allocation lets a file be scattered so that no free space is wasted.

Quick revision

• To a file system a disk is a numbered sequence of fixed-size blocks.
• Four parts: the data blocks, the free space map, the directory, and the metadata about the disk

itself, which in Unix is the superblock.

• Contiguous allocation: fast, cannot grow, external fragmentation. Linked: grows freely, no

direct access. Indexed: an index block per file, direct access and growth, at the cost of the index.

• Linux uses indexed allocation and calls the index the inode: twelve direct block numbers

then three levels of indirection.

• Free space is tracked by a bitmap, one bit a block, or by a free list threaded through the free

blocks themselves. A bitmap can find consecutive blocks; a free list cannot.

• The block count rounds up: (len + BLOCK_SIZE - 1) / BLOCK_SIZE.
• Internal fragmentation is the unused tail of the last block, and is unavoidable. External

fragmentation is free space broken into unusable pieces, and indexed allocation avoids it.

• A create that fails halfway must give back the blocks it has already taken.
• A directory entry holds a name and an inode number; the inode holds everything else. That split

is what makes hard links possible, and why the system call is unlink.

• Deleting a file frees its blocks and usually does not wipe them, which is why deleted files can

often be recovered.

• A real file system adds a tree of directories, permissions, times, a journal against crashes and

a page cache.

Questions you should be able to answer

1. How many 16 byte blocks does a 38 byte file need, and how is that computed? Three. Add BLOCK_SIZE - 1 to the length first: 38 + 15 is 53, and C's integer division of 53 by 16 gives 3. Plain 38 / 16 gives 2 and loses the last six bytes.

2. What is internal fragmentation, and how much is there in that file? The unused part of the last block. Three blocks of 16 bytes is 48, the file is 38, so 48 - 38 = 10 bytes are wasted.

3. Give the three allocation methods and one disadvantage of each. Contiguous: a file cannot grow and free space suffers external fragmentation. Linked: there is no direct access to the middle of a file, and one damaged block loses the rest. Indexed: the index block is overhead and limits how large a file can be.

4. Which does Linux use, and what is its index called? Indexed allocation. The index is the inode, which holds twelve direct block numbers and then single, double and triple indirect blocks.

5. Why did the file created after a deletion get blocks 4, 7 and 8? Because block 4 had just been freed and was the first free block, and 7 and 8 were the next. Under indexed allocation the blocks need not be adjacent, so a single freed block in the middle of the disk is usable.

6. What is the difference between a bitmap and a free list? A bitmap is one bit per block, costs space proportional to the disk and can find consecutive free blocks quickly. A free list threads the free blocks together, costs no extra space and cannot find consecutive blocks without walking it.

7. What must a create do if the disk fills up halfway through? Free the blocks it has already allocated before reporting the failure, or they are leaked: marked used with no file owning them.

8. Why is the system call to remove a file called unlink? Because it removes one name from one directory. An inode may have several names, and its blocks are freed only when the last one goes.

9. What does a journalling file system protect against? An interrupted write leaving the disk inconsistent, for example a block marked used with no file owning it. The intended change is written to a log first, so it can be replayed or undone after a crash.