# File Allocation and Inode Numericals — Max File Size, Disk Accesses, FAT and Bitmap Size

Source: https://skills101.in/learn/operating-systems/os-file-allocation-inode-numericals — Skills101 free tutorial (Operating Systems). Updated 2026-11-21.

Lesson 8 described the three ways to place a file on disk and introduced inodes. Exams turn this into arithmetic: **"What is the largest file this inode can describe?"**, **"How many disk reads to get block 50?"**, **"How big is the FAT?"** Every one of these needs only two numbers — the **block size** and the **pointer (disk address) size** — and a clear picture.

## 1. The three allocation methods in one picture

![A 16-block disk strip shown three times: contiguous allocation uses blocks 3 to 6; linked allocation uses blocks 1, 7, 10 and 14 joined by arrows; indexed allocation keeps the list 2, 5, 11, 13 in index block 9](https://skills101.in/learn-img/operating-systems/allocation-methods.svg)

| Method | Directory stores | Reach block i of the file | Main problem |
|---|---|---|---|
| **Contiguous** | start block, length | start + i → **1 read** | external fragmentation; hard to grow a file |
| **Linked** | first block (and last) | follow i pointers → **i + 1 reads** | slow random access; one bad pointer loses the rest |
| **Indexed** | index block number | read index block, then the data → **2 reads** | the index block itself uses space |

Counting convention: block numbers start at **0**, and the directory entry is already in memory. If a question numbers blocks from 1 or says the index block is cached, adjust the count.

**Example.** To read block 9 (the tenth block) of a file: contiguous = **1** read, linked = **10** reads (blocks 0 to 9 one after another), indexed = **2** reads.

**FAT** (File Allocation Table, used by FAT32 on pen drives) is linked allocation with all the "next" pointers moved into **one table**. If the table is held in RAM, following the chain costs no disk reads — reaching any block takes **1** disk read.

## 2. How an inode points to data

A Unix-style inode stores the file's details (owner, size, permissions, times) and a list of block pointers. A common layout is **12 direct pointers** plus one **single**, one **double** and one **triple indirect** pointer.

![An inode with 12 direct pointers going straight to data blocks, a single indirect pointer to one block of pointers, a double indirect pointer to a block of pointer blocks, and a triple indirect pointer three levels deep; with 4 KB blocks each pointer block holds 1024 pointers](https://skills101.in/learn-img/operating-systems/inode-pointers.svg)

- A **direct** pointer points to a data block.
- A **single indirect** pointer points to a block **full of pointers** to data blocks.
- **Double** indirect: a block of pointers to blocks of pointers to data. **Triple**: one more level.

The key number is **pointers per block = block size / pointer size**. With 4 KB blocks and 4-byte pointers: 4096 / 4 = **1024**.

## 3. Maximum file size

Count the data blocks each pointer can reach, add them, multiply by the block size:

**Max size = (direct + p + p² + p³) × block size**, where p = pointers per block.

With 4 KB blocks, 4-byte pointers, 12 direct:

| Part | Data blocks | Bytes |
|---|---|---|
| 12 direct | 12 | 48 KB |
| single indirect | 1024 | 4 MB |
| double indirect | 1024² = 1,048,576 | 4 GB |
| triple indirect | 1024³ = 1,073,741,824 | 4 TB |
| **total** | 1,074,791,436 | **about 4 TB** |

The triple indirect part is so large that it decides the answer; the others add only a few GB.

```python
KB, MB, GB, TB = 2**10, 2**20, 2**30, 2**40

def max_file_size(block, ptr, direct, single=1, double=1, triple=1):
    p = block // ptr                      # pointers that fit in one block
    blocks = direct + single * p + double * p**2 + triple * p**3
    return p, blocks, blocks * block

def show(n):
    for unit, name in ((TB, "TB"), (GB, "GB"), (MB, "MB"), (KB, "KB")):
        if n >= unit:
            return f"{n / unit:.2f} {name}"
    return f"{n} B"

for block, ptr, direct, d, t in [(4 * KB, 4, 12, 1, 1), (1 * KB, 4, 10, 1, 0)]:
    p, blocks, size = max_file_size(block, ptr, direct, double=d, triple=t)
    print(f"block {block // KB} KB, {ptr}-byte pointers: {p} per block, {blocks} data blocks, max file {show(size)}")
```

```text
block 4 KB, 4-byte pointers: 1024 per block, 1074791436 data blocks, max file 4.00 TB
block 1 KB, 4-byte pointers: 256 per block, 65802 data blocks, max file 64.26 MB
```

The second line is a typical exam variant: 1 KB blocks, 10 direct, one single and one double indirect pointer, no triple. p = 256, so the maximum is (10 + 256 + 65,536) × 1 KB = 65,802 KB ≈ **64.26 MB**.

## 4. Which pointer reaches a given byte?

*4 KB blocks, 4-byte pointers, 12 direct. Which pointer is used to read byte 5,000,000 of a file, and how many disk reads are needed (inode already in memory)?*

1. Logical block number = 5,000,000 ÷ 4096 = **1220** (integer division).
2. Blocks 0–11 are direct. Blocks 12 to 12 + 1023 = **1035** use the single indirect pointer.
3. 1220 > 1035, so it is in the **double indirect** range, at position 1220 − 1036 = 184 inside it.
4. Reads: the double indirect block → a second-level pointer block → the data block = **3 disk reads**.

General rule: direct = 1 read, single = 2, double = 3, triple = 4 (each level adds one pointer block).

This is why small files are fast on Unix-style systems: most files fit in the direct pointers, so one read after the inode gets the data.

## 5. Size of a FAT

*A 20 GB disk has 4 KB blocks. Each FAT entry is 4 bytes. How big is the FAT?*

1. Number of blocks = 20 GB / 4 KB = 20 × 2³⁰ / 2¹² = **5,242,880**.
2. FAT size = 5,242,880 × 4 bytes = **20 MB**.

Keeping a 20 MB table in RAM is the price of FAT's fast random access. For terabyte disks the table becomes very large, which is one reason modern systems use inodes or extents instead.

## 6. Free-space management: bitmap size

The OS must also remember which blocks are **free**. A **bitmap** uses **one bit per block** (1 = free, 0 = used, or the other way round).

For the same 20 GB disk: 5,242,880 bits ÷ 8 = 655,360 bytes = **640 KB**.

| Method | Idea | Strength |
|---|---|---|
| Bitmap | one bit per block | small; easy to find runs of free blocks |
| Free list | free blocks linked together | no extra space; slow to find many blocks |
| Grouping / counting | store "start block + count" runs | compact when free space is in big chunks |

## 7. Extents (what modern systems do)

File systems such as ext4 and NTFS describe a file as a few **extents**: "start at block 1000, length 300". It is contiguous allocation in pieces — fast like contiguous, but able to grow like indexed. You may see this as a one-line interview question: "How does ext4 store a large file efficiently?"

## Common mistakes

- Using the number of **bits** in a pointer as its size in bytes (a 32-bit pointer is 4 bytes).
- Forgetting the direct pointers when finding which range a block falls into.
- Counting the inode read when the question says the inode is already in memory (or the other way round).
- Mixing powers of 2 and 10: in these questions 1 KB = 1024 bytes and 1 GB = 2³⁰ bytes.
- For linked allocation, saying "1 read" — you must follow the chain.

## Quick recap

- Pointers per block p = block size / pointer size.
- Max file = (direct + p + p² + p³) × block size; with 4 KB blocks and 4-byte pointers it is about 4 TB.
- Reads to a data block: direct 1, single 2, double 3, triple 4 (inode in memory).
- Block i: contiguous 1 read, linked i + 1, indexed 2.
- FAT size = blocks × entry size; bitmap size = blocks / 8 bytes.


Practice quiz and free certificate: https://skills101.in/learn/operating-systems/os-file-allocation-inode-numericals