Chapter 33 of 38

File Allocation Methods

Think of a disk as a long row of numbered lockers, all the same size. A 10 KB file does not fit in one 4 KB locker, so it needs three. Which three? Side by side? Scattered anywhere? And once they are scattered, how do we remember which lockers belong to which file, in which order?

These questions are what file allocation methods answer.

A file allocation method is the strategy a file system uses to assign disk blocks to files and to record where each file's blocks are, so that the file can be read back in the right order.

In File Systems we saw that the inode (or File Control Block) records the "location" of a file's data. This chapter opens that box. We will study the three classic methods (contiguous, linked and indexed), the FAT and UNIX-inode variations that real systems use, and finally how the file system keeps track of free blocks.


The Basic Setup

The file system sees the disk as an array of blocks numbered 0, 1, 2, ... N-1. Every block has the same size, typically 4 KB today (older examples often use 512 bytes or 1 KB).

A file is split into logical blocks numbered from 0. Logical block 0 holds bytes 0 to 4095, logical block 1 holds bytes 4096 to 8191, and so on. The allocation method's job is to map:

logical block number (inside the file)  →  physical block number (on the disk)

byte offset 10,000 in a file with 4 KB blocks:
  logical block = 10000 / 4096 = 2      (integer division)
  offset inside = 10000 % 4096 = 1808

A good allocation method should:

  • Use space well: little wasted space, no unusable gaps.

  • Be fast for sequential access: reading a file from start to end.

  • Be fast for direct access: jumping to logical block i without reading 0 to i-1.

  • Let files grow easily.

No single method is best at everything. Each one trades some of these goals for others.


1. Contiguous Allocation

The simplest idea: give each file a set of consecutive blocks.

In contiguous allocation, each file occupies a contiguous run of blocks on the disk. The directory entry only needs the starting block and the length.

Directory
+-----------+-------+--------+
| File      | Start | Length |
+-----------+-------+--------+
| notes.txt |   2   |   3    |
| report    |  14   |   5    |
| song.mp3  |   6   |   6    |
+-----------+-------+--------+

Disk blocks
 0  1 [2  3  4] 5 [6  7  8  9  10 11] 12 13 [14 15 16 17 18] 19
       notes           song.mp3                  report

Finding a Block

Since the blocks are consecutive, finding any block is a single addition:

physical block = start + logical block number

report, byte 10,000:
  logical block = 10000 / 4096 = 2
  physical block = 14 + 2 = 16        (offset 1808 inside block 16)

One calculation, one disk read. That makes contiguous allocation excellent for both sequential and direct access. On a hard disk it is also the fastest possible layout for sequential reading, because the head hardly needs to move between blocks (see Disk Structure & Disk Scheduling).

The Problems

1. External fragmentation. As files are created and deleted, free space breaks into small holes between files. This is exactly the problem you saw with memory in Contiguous Memory Allocation & Fragmentation.

Suppose the other blocks are used by small files A, B, C, D:

 0  1   2  3  4   5   6 ... 11   12 13   14 15 16 17 18   19
[ A  ] [ notes  ] [B] [song.mp3] [ C  ] [    report    ] [D]

Now delete notes.txt and report:

[ A  ] [  free  ] [B] [song.mp3] [ C  ] [     free     ] [D]
         3 blocks                          5 blocks

Total free   = 3 + 5 = 8 blocks
Largest hole = 5 blocks
A new 6-block file does NOT fit, even though 8 blocks are free.

The file system can choose holes with first fit or best fit, but that only reduces the problem. The full cure is compaction (defragmentation): moving files to merge the holes, which is slow on a big disk.

2. Files cannot grow easily. When you create a file, how many blocks should you reserve? If report grows from 5 to 6 blocks, block 19 is already taken by file D, so the whole file would have to be copied to a bigger hole. Reserving extra space "just in case" wastes space instead.

Because of these problems, pure contiguous allocation is used mainly where files are written once and never change, for example CD-ROMs and DVDs (the ISO 9660 file system).


2. Linked Allocation

The opposite idea: let a file's blocks be anywhere, and chain them together like a linked list.

In linked allocation, each block contains a pointer to the next block of the file. The directory stores the first block (and often the last block).

Directory: report → start = 9, end = 25

 block 9          block 16         block 1          block 10         block 25
+--------+---+   +--------+---+   +--------+---+   +--------+---+   +--------+----+
| data 0 |16 |→  | data 1 | 1 |→  | data 2 |10 |→  | data 3 |25 |→  | data 4 | -1 |
+--------+---+   +--------+---+   +--------+---+   +--------+---+   +--------+----+
                                                                          end of file

What It Fixes

  • No external fragmentation. Any free block anywhere can be used, so the 6-block file from before fits, because 8 blocks are free in total.

  • Files grow easily. To append, take any free block, write it, and link it from the old last block.

  • No need to know the file size in advance.

What It Breaks

1. Direct access is slow. To reach logical block 3, you must follow the chain:

read block 9   → pointer says 16
read block 16  → pointer says 1
read block 1   → pointer says 10
read block 10  → this is logical block 3

Reading logical block i needs i + 1 disk reads.

For a 10,000-block file, reading the last block means 10,000 disk reads. Linked allocation is really only good for sequential access.

2. Pointer overhead. Each block loses some bytes to the pointer. With 512-byte blocks and 4-byte pointers, only 508 bytes per block hold data, about 0.78% lost. A common fix is to allocate clusters of several blocks and keep one pointer per cluster, at the cost of more internal fragmentation.

3. Reliability. If one pointer is damaged by a bad sector or a bug, the rest of the file is lost, or worse, the chain jumps into another file's blocks.

4. Seeks. On a hard disk, scattered blocks mean the head jumps around even for sequential reading.


FAT: Linked Allocation, Done Smarter

The File Allocation Table (FAT), used by MS-DOS and still used today on USB drives and SD cards (FAT32, exFAT), keeps the linked-list idea but moves all the pointers out of the data blocks into one table at the start of the volume.

The FAT has one entry per block (cluster). The entry for block b holds the number of the next block of the same file, an end-of-file marker, or 0 if the block is free.

The same report file in a FAT:

Directory entry: report, first block = 9

     FAT
 index  value
   0     ...
   1     10        ← block 1 is followed by block 10
   2     0  (free)
   ...
   9     16        ← start: 9 → 16
  10     25
  ...
  16     1
  ...
  25     EOF       ← last block
  ...

Chain: 9 → 16 → 1 → 10 → 25 → EOF

Why is this a big improvement?

  • The FAT is small enough to be cached in memory. Following the chain to logical block i then means i lookups in RAM, which is cheap, and then one disk read for the data. Direct access becomes practical.

  • Data blocks hold only data, so a block is a clean power of two in size.

  • Free blocks are simply the entries that hold 0, so the FAT also acts as the free-space list.

The cost is the table itself. FAT32 uses a 4-byte entry per cluster (28 of the 32 bits are used for the cluster number). A 1 TB volume (240 bytes) with 32 KB clusters has 240 / 215 = 33,554,432 clusters, so one copy of the FAT is 128 MB. Big tables cost memory, and the FAT is a single point of failure, which is why FAT file systems normally keep two copies of the table.


3. Indexed Allocation

Linked allocation scattered the pointers through the file. FAT gathered every file's pointers into one global table. Indexed allocation gives each file its own table.

In indexed allocation, each file has an index block: an array of disk-block addresses. Entry i of the index block holds the address of logical block i. The directory (or inode) points to the index block.

Directory: report → index block = 19

 index block 19
+----+
|  9 |  → logical block 0
| 16 |  → logical block 1
|  1 |  → logical block 2
| 10 |  → logical block 3
| 25 |  → logical block 4
| -1 |  (unused)
| -1 |
+----+

Logical block 3?  Read index block 19, entry 3 = block 10. Read block 10.

Indexed allocation gives us:

  • Direct access: at most two reads (index block, then data block), or one if the index block is already cached.

  • No external fragmentation: any free block can be used.

  • Easy growth, up to the size of the index block.

The costs:

  • Wasted index space for small files. A 1-block file still needs a whole index block. With 4 KB blocks, a tiny file costs 8 KB on disk.

  • Maximum file size. One 4 KB index block with 4-byte addresses holds 4096 / 4 = 1024 entries, so a file can have at most 1024 blocks = 4 MB. Far too small.

Making Index Blocks Scale

Three ways to handle large files:

  • Linked scheme: when an index block fills up, its last entry points to another index block.

  • Multilevel index: a first-level index block points to second-level index blocks, which point to data. With 1024 entries per block, two levels give 1024 × 1024 blocks = 4 GB.

  • Combined scheme: the clever mix used by UNIX, explained next.


The UNIX Inode: The Combined Scheme

Most files are small, and a few are huge. The UNIX file systems (UFS, ext2, ext3) handle both cases with one structure. The inode contains 15 block pointers:

  • 12 direct pointers: point straight at data blocks.

  • 1 single indirect pointer: points to a block full of pointers to data blocks.

  • 1 double indirect pointer: points to a block of pointers to single-indirect blocks.

  • 1 triple indirect pointer: one more level.

          inode
   +-------------------+
   | mode, owner, size |
   | timestamps, ...   |
   +-------------------+
   | direct 0          | ──→ data
   | direct 1          | ──→ data
   | ...               |
   | direct 11         | ──→ data
   +-------------------+
   | single indirect   | ──→ [ptr ptr ... ptr] ──→ data
   +-------------------+
   | double indirect   | ──→ [ptr ...] ──→ [ptr ...] ──→ data
   +-------------------+
   | triple indirect   | ──→ [ptr ...] ──→ [ptr ...] ──→ [ptr ...] ──→ data
   +-------------------+

Small files (up to 12 blocks) are reached directly from the inode, with no extra index blocks at all. Only big files pay for the indirect levels.

Numerical 1: Maximum File Size

Block size 4 KB, block address 4 bytes, 12 direct pointers plus single, double and triple indirect.

Pointers per block  = 4096 / 4 = 1024

Direct            12 × 4 KB              =         48 KB
Single indirect   1024 × 4 KB            =          4 MB
Double indirect   1024² × 4 KB           =          4 GB
Triple indirect   1024³ × 4 KB           =          4 TB
                                           ----------------
Maximum           (12 + 1024 + 1024² + 1024³) × 4 KB
                = 1,074,791,436 blocks × 4096 bytes
                = 4,402,345,721,856 bytes  ≈ 4 TB

Notice that the triple-indirect part completely dominates. In exams you can usually write "about 4 TB" with the working shown. (Real ext2/ext3 have other limits too, such as the width of the size fields, so their practical maximum can be lower. This calculation is about the pointer structure.)

Numerical 2: Which Pointer Holds a Byte?

Block size 1 KB, 4-byte addresses, 10 direct pointers, then single, double and triple indirect. Which pointer is used to read byte 300,000, and how many disk reads are needed (inode already in memory)?

Pointers per block = 1024 / 4 = 256

Logical block of byte 300,000 = 300000 / 1024 = 292   (offset 992)

Direct           covers logical blocks   0 .. 9
Single indirect  covers logical blocks  10 .. 265        (256 blocks)
Double indirect  covers logical blocks 266 .. 65,801     (256² = 65,536 blocks)

292 is in the double-indirect range.
Position inside that range: 292 - 266 = 26
  first-level entry  = 26 / 256 = 0
  second-level entry = 26 % 256 = 26

Disk reads: double-indirect block + one single-indirect block + data block = 3

Maximum file size for this setup: (10 + 256 + 256² + 256³) × 1 KB = 17,247,250,432 bytes, about 16 GB.


Extents: What Modern File Systems Do

The inode scheme stores one pointer per block. A 1 GB file with 4 KB blocks needs 262,144 pointers, even if the blocks are all next to each other. That is wasteful.

Modern file systems (ext4, XFS, NTFS, Btrfs, APFS) combine the best of contiguous and indexed allocation with extents.

An extent is a run of contiguous blocks, described by (starting logical block, starting physical block, length). A file is a list (or tree) of extents.

A file stored in one contiguous run needs only one extent, no matter how big it is. If the file is fragmented, it simply has more extents. In ext4, one extent can describe up to 32,768 blocks (128 MB with 4 KB blocks), the inode itself holds up to four extents, and larger files use a small tree of extents.

Seeing Extents on Linux

The filefrag -v command shows how a file is laid out. Real output on an ext4 file system (WSL Linux), for a 300,000-byte file:

head -c 300000 /dev/urandom > photo.bin
filefrag -v photo.bin
Filesystem type is: ef53
File size of photo.bin is 300000 (74 blocks of 4096 bytes)
 ext:     logical_offset:        physical_offset: length:   expected: flags:
   0:        0..      73:    2304896..   2304969:     74:             last,eof
photo.bin: 1 extent found

300,000 / 4096 = 73.2, so the file needs 74 blocks (the last block is only partly used). All 74 sit in one run, physical blocks 2,304,896 to 2,304,969: one extent. The old inode scheme would have needed 74 pointers, including a single-indirect block.

Now a file that grew slowly while another file was also growing. We appended 4 KB to a.log, then 400 KB to b.log, and repeated six times, forcing a write to disk each time:

File size of a.log is 24576 (6 blocks of 4096 bytes)
 ext:     logical_offset:        physical_offset: length:   expected: flags:
   0:        0..       1:    2763266..   2763267:      2:
   1:        2..       3:    2776066..   2776067:      2:    2763268:
   2:        4..       5:    2770972..   2770973:      2:    2776068: last,eof
a.log: 3 extents found

This 6-block file is fragmented into 3 extents. The expected column shows where the next block would have been if the file had stayed contiguous (2,763,268), but that spot was taken, so the file system had to start a new extent elsewhere. (Your block numbers and extent count will differ; ext4 tries hard, using delayed allocation and preallocation, to avoid exactly this.)

Bonus: Sparse Files

Because extents only describe blocks that exist, a file can have holes: ranges that were never written and use no disk space. Reading a hole returns zeros.

truncate -s 1G sparse.img                                   # 1 GB size, no data
printf X | dd of=sparse.img bs=1 seek=500000000 conv=notrunc  # write 1 byte in the middle
du -h --apparent-size sparse.img; du -h sparse.img
filefrag -v sparse.img
1.0G	sparse.img
4.0K	sparse.img
...
File size of sparse.img is 1073741824 (262144 blocks of 4096 bytes)
 ext:     logical_offset:        physical_offset: length:   expected: flags:
   0:   122070..  122070:    2839766..   2839766:      1:     122070: last
sparse.img: 1 extent found

The file's size is 1 GB, but it uses just one 4 KB block: logical block 122,070 (500,000,000 / 4096 = 122,070). Virtual machine disk images and database files use sparse files a lot.


Comparing the Methods

Assume the file's directory entry or inode is already in memory, and count disk reads needed to read logical block i (counting from 0).

Method

Reads for block i

Sequential access

Direct access

External fragmentation

File growth

Contiguous

1

Excellent

Excellent

Yes

Hard

Linked

i + 1

Good

Very poor

No

Easy

FAT (table cached)

1

Good

Good

No

Easy

Indexed (one index block)

2 (1 if index cached)

Good

Good

No

Easy, up to index size

UNIX inode (combined)

1 to 4, depending on level

Good

Good

No

Easy

Extents

Usually 1

Excellent

Good

Reduced (more extents)

Easy

Where each one is used:

  • Contiguous: CD/DVD file systems, and as the goal of extent-based file systems.

  • Linked via FAT: FAT32 and exFAT on USB drives, SD cards, cameras.

  • Indexed (combined): classic UNIX file systems, ext2 and ext3.

  • Extents: ext4, XFS, NTFS, Btrfs, APFS.


Free-Space Management

Allocating blocks requires knowing which blocks are free. When a file is deleted, its blocks go back to the free pool. The file system keeps a free-space list, which despite the name can be stored in several ways.

We will use one example: a 16-block disk where blocks 1, 2, 5, 6, 7, 11 and 14 are free.

1. Bit Vector (Bitmap)

One bit per block. In the convention used by most textbooks, 1 = free and 0 = allocated:

block:  0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
bit:    0 1 1 0 0 1 1 1 0 0  0  1  0  0  1  0

bitmap = 0110011100010010

(Real file systems may use the opposite convention. ext4's block bitmap uses 1 = in use. The idea is the same.)

Why bitmaps are popular:

  • Finding a free block is fast: scan the bitmap one machine word at a time, skip words that are all "allocated", and find the first set bit inside the first useful word. Most CPUs have an instruction for that last step.

  • Finding n consecutive free blocks is easy: look for n consecutive 1s. This helps keep files contiguous.

The cost is the size of the bitmap, which grows with the disk:

2 TB disk, 4 KB blocks:
  blocks = 2^41 / 2^12 = 2^29 = 536,870,912
  bitmap = 2^29 bits = 2^26 bytes = 64 MB

That is fine to keep on disk, but too much to keep fully in memory on small systems. ext4 splits the bitmap into one piece per block group and loads only the pieces it needs.

2. Linked List of Free Blocks

Each free block holds a pointer to the next free block. The file system only remembers the first one.

free head → 1 → 2 → 5 → 6 → 7 → 11 → 14 → null

No extra space is needed (the pointers live inside blocks that are free anyway), and allocating one block is easy: take the head. But walking the list requires a disk read per block, and finding contiguous free space is impractical. FAT effectively uses this idea, except that the "list" is just the zero entries in the table.

3. Grouping

An improvement on the linked list: the first free block stores the addresses of the next n free blocks. The last of those n holds the addresses of another n, and so on. One disk read now gives you n free block numbers instead of one.

4. Counting

Free blocks often come in runs. Instead of listing each one, store (first block, count) pairs:

(1, 2)   → blocks 1, 2
(5, 3)   → blocks 5, 6, 7
(11, 1)  → block 11
(14, 1)  → block 14

This is the same idea as extents, applied to free space. XFS keeps free space as extents in B+ trees, so it can quickly find a run of a requested size.

Method

Space needed

Find one free block

Find contiguous run

Bitmap

1 bit per block

Fast (word scan)

Easy

Linked list

Almost none (inside free blocks)

Fast (head)

Impractical

Grouping

Inside free blocks

Fast, n at a time

Hard

Counting

Small when runs are long

Fast

Easy

A Note on SSDs: TRIM

When a file is deleted, the file system only marks its blocks free in its own bitmap. The SSD does not know those blocks are now garbage, and it keeps copying them around internally. The TRIM command (called discard on Linux, UNMAP on SCSI) lets the file system tell the SSD which blocks are free, so the SSD can erase them in the background. On Linux this is usually done periodically with fstrim.


Common Mistakes

  • Saying linked allocation has external fragmentation. It does not. Any free block can be used. It has poor direct access instead.

  • Saying indexed allocation needs 1 read for any block. It needs the index block too, unless the index block is cached.

  • Forgetting that FAT is linked allocation. The links just live in a table instead of in the blocks.

  • Off-by-one in inode numericals. With 10 direct pointers, logical blocks 0 to 9 are direct and the single indirect starts at block 10. Always write the ranges down.

  • Using 1000 instead of 1024 for "pointers per block". 1 KB / 4 bytes = 256, not 250.

  • Confusing file size with blocks used. A sparse 1 GB file can use 4 KB, and a 5-byte file still uses a 4 KB block.

  • Assuming bit 1 always means free. It depends on the file system. State your convention in the exam.


Interview Questions

What are the three main file allocation methods?

Contiguous (consecutive blocks; start and length), linked (each block points to the next), and indexed (an index block lists all the file's blocks).

Why is contiguous allocation fast but rarely used alone?

Any block is found with one addition and sequential reads need few seeks, but it suffers external fragmentation and files cannot grow easily.

Why is direct access slow with linked allocation?

To reach block i you must read blocks 0 to i-1 to follow the pointers, so it takes i + 1 disk reads.

How does FAT improve on linked allocation?

It moves all next-block pointers into one table that can be cached in memory, so following a chain is done in RAM and only the target data block is read from disk.

What is the disadvantage of indexed allocation for small files?

Each file needs a whole index block, which is mostly empty for a small file, wasting space.

Why does the UNIX inode use direct and indirect pointers?

Most files are small and are served by direct pointers with no extra reads; large files use single, double and triple indirect blocks, so the same structure supports very large files.

What is an extent?

A contiguous run of blocks described by a start and a length. Extent-based file systems (ext4, XFS, NTFS) describe large contiguous files with very little metadata.

How does a bitmap manage free space?

One bit per block marks it free or used. It allows fast searches for free blocks and contiguous runs, at the cost of one bit per block of space.

What is TRIM?

A command that tells an SSD which blocks the file system no longer uses, so the SSD can erase them in advance and avoid copying stale data.


The Main Idea

Contiguous  → start + length; fastest; external fragmentation, hard to grow
Linked      → next-pointer in each block; no fragmentation; sequential only
FAT         → linked, but pointers in a cached table; direct access OK
Indexed     → per-file index block; direct access; index overhead
UNIX inode  → 12 direct + single + double + triple indirect
Extents     → (start, length) runs; contiguous speed with flexibility
Free space  → bitmap, linked list, grouping, counting

Every allocation method answers the same question, "where is block i of this file?", and each trades speed, space and flexibility differently.

We now know how a file's blocks are found once we have its inode. But how does the OS get from a name like /home/riya/notes.txt to that inode? That is the job of directories, the topic of the next chapter, Directory Structure.