File systems — theory with your IC2 practical folder, FAT, i-nodes and links (and the USB stick that refused my defence video)

The night before defending my IC2 practical I wanted to take everything on a USB stick: the practical folder and the recording of my rehearsal, a 4.3 GB video. The stick had 20 GB free. I drag, I wait… and Windows says: “The file is too large for the destination file system”. Too large? There were 15 GB to spare!

The problem was not space, it was how that stick stored files. It was formatted as FAT32, and FAT32 writes the size of each file in a 32-bit field: at most 2^32 − 1 = 4,294,967,295 bytes. My video had 4,300,000,000. It was 5 MB too big to be possible. Lesson: what you can store does not depend only on the free gigabytes, but on the structure the operating system builds on top of the disk.

This is the last topic of the IC2 theory (block T6, files). In Virtual memory you saw how the OS makes RAM look bigger by using the disk; today it is the turn of what lives on that disk: what a file is, how you see it (names, folders, links) and how the OS stores it inside (blocks, FAT, i-nodes). The running example is the IC2 practical folder on the laptop: practica.c, Makefile, datos.csv and informe.pdf. At the end you have a Python simulator and, after that, the exam-style exercises.

From a disk of blocks to a file

Secondary storage (hard disks, SSDs, USB sticks, cards) is cheaper and slower than RAM, but it is not volatile: what you save is still there when you switch off. That is where programs, your documents, backups and even the swap area of virtual memory live.

The kernel sees any storage device as something very simple: an array of fixed-size blocks, numbered from 0. To write, something like write_block(42, data). Can you imagine saving your practical like that? “Read blocks 357, 48 and 13 and glue them together”. Nobody works like that: we think in documents, photos, programs.

That is why the OS offers an abstraction closer to what you handle, the file:

The curious part is that the same file is a different thing depending on who looks at it. Look at the drawing with informe.pdf:

• For you (the user): a durable data structure, a document with its name.
• For the system call interface: a collection of bytes. read() does not care whether it is a PDF or a song (that is how Unix sees it).
• For the kernel: a collection of blocks, the logical unit of transfer, which is bigger than a disk sector.

Attributes, directory and “file system”

The attributes of a file

Besides its contents, every file carries a card with its characteristics. There are seven attributes you must know:

Attribute	What it stores	For informe.pdf
Name	The string you identify it with	informe.pdf
Type	Needed in systems that distinguish types	PDF
Location	Where its blocks are on the device	depends on the allocation method (see below)
Size	How many bytes it has	18,000 B
Protection	Who can do what	sergio reads and writes, laura only reads
Dates and times	Creation, modification, last access	—
Version	In systems that keep a history	—

Each OS chooses its set of attributes and their limits (for instance, the maximum name length… or the maximum size, as my video found out).

The directory: the disk’s index

When you open informe.pdf, how does the OS know it exists and where it is? With the directory (or table of contents): a structure with the catalogue of files. Each entry stores the attributes of one file and its location. And note: the directory also lives on the disk (at most, with a copy in RAM while it is used).

In the drawing, the directory says that practica.c starts at block 2, Makefile at 7, datos.csv at 8 and informe.pdf at 12. The difference they ask about in exams: the file is the group of blocks the user sees as a sequence; the directory is the structure of names the user sees.

The two faces of “file system”

The expression has two meanings, and the test can ask for both:

1. The operating system module that provides everything related to files and directories.
2. The information structure created on secondary storage to keep them (what you do when you format: ext4, NTFS, FAT32…).

Operations on files

There are six basic operations:

1. Create a file (and its directory entry).
2. Write.
3. Read.
4. Reposition: move the current position inside the file without reading or writing.
5. Delete: the entry and the contents disappear.
6. Truncate: only the contents are erased; the file and its attributes stay.

The difference between the last two comes up a lot:

Open and close: not going to the directory every time

Almost every operation needs the attributes and location of the file. If on every read() the OS had to search for the name in the directory on disk, it would be painfully slow. The solution:

• Opening a file stores its control information in main memory.
• Closing frees those resources from memory.

In Unix, each process has an open-file table, and the descriptor returned by open() is nothing more than the index of the entry reserved for that file (if you have programmed with system calls in C, it is the famous fd):

Why 3? Because 0, 1 and 2 are already taken by standard input, standard output and standard error.

File types

How does the OS know whether a file is a photo or a program?

• Windows: by the last letters of the name, the extension (.pdf, .exe).
• Unix: the OS does not recognise types; to it everything is bytes (programs interpret the contents).
• Mac (old versions): some attributes marked the type.

But there is one that every OS has to recognise: the executable file, because the OS must know how to load it and start it.

Access methods

Once it is open, how do you walk through the file’s blocks? There are three methods:

• Sequential — “the file is a tape”: you read or write from where you stopped and the position advances by itself; you can only move forward or go back (rewind). It is the basic model of Unix and Windows: open → read → read → ….
• Direct — “the file is an array of blocks”: each operation says which position it wants. In Unix it is done with lseek(), which moves the position before the next read().
• Indexed (ISAM) — “the file is a database table”: the records are sorted by a key and you search by it (or by record number).

In indexed access, the OS keeps one or more hidden index files so that searches are fast and every write keeps the order. Old systems had it (IBM OS/360, OpenVMS); today this is done outside the kernel, in databases.

Method	How you reach the data	Example
Sequential	Continuing from where you stopped	reading datos.csv line by line
Direct	Giving the position (lseek)	jumping to block 6 of a video
Indexed	By the value of a key	finding “Ruiz” in a list of marks

Directories: from a single drawer to a tree with shortcuts

A directory is a table of nodes with information about the files, and both directories and files reside in secondary memory. On a directory you can: search for a file by name, list, create an (empty) file, delete, rename, copy or move to another directory and traverse the file system.

The interesting part is how they are organised. There are five models, from simplest to most general: single level → two levels → tree → acyclic graph → general graph.

1. Single level

All files in one main directory (the volume table of contents):

Problems: it does not suit several users (name clashes, permissions) and, with many files, every search gets slower.

2. Two levels

The main directory (master directory) has no files, only one subdirectory per user (or per application, or for the system):

Advantages: better organisation, per-directory permissions and no name clashes. The concept of a path also appears: sergio:practica.c.

3. Tree

The generalisation: a directory can contain files and other directories, as deep as you like. It is what you use every day:

• The path (pathname) locates an object in the tree. The absolute one starts at the root: /home/sergio/ic2/practica/informe.pdf.
• The working directory is where you “are”; from there you can use a relative path: if you are in /home/sergio/ic2, practica/informe.pdf is enough.
• Deleting a directory raises a question: is its whole subtree deleted? (In the drawing, deleting practica would take the four files with it).

The drawback of the tree: it does not allow sharing. If laura and you want to work on the same datos.csv, each of you would have a copy.

4. Acyclic graph: links

The idea is that the same object (not a copy) is linked from several paths:

The directory stops being a tree and becomes an acyclic graph. There are two kinds of link, and their difference is a guaranteed question:

• Symbolic link (ln -s datos.csv atajo.csv): a pointer to the original file that stores its path. It can have different permissions and point to directories (Windows shortcuts are similar). If the original is deleted, the link points to nothing.
• Hard link (ln datos.csv copia-laura.csv, less common): another entry that shares the same i-node as the original. Files only, not directories.

Sharing brings two questions. What do we do when a shared object is deleted? If you just delete the data, dangling pointers remain (and worse: the space can be reused for another file, and the link would lead to it). The solution: delete the pointers one by one and the file only when the link counter reaches 0. And when traversing the graph? There are several paths to the same file: a program adding up used space could count it twice if it does not remember where it has been.

5. General graph: when cycles appear

What if I link to a directory higher up? A cycle forms:

Infinite paths appear (ic2/practica/atajo/practica/atajo/…) and a program that walks the tree without knowing it gets stuck. Solutions: allow links only to files, not to subdirectories; garbage collection (to free whatever becomes unreachable); or cycle-detection algorithms.

Model	What it adds	Its weak point
Single level	The simplest	Name clashes, slow with many files
Two levels	One directory per user, paths	No subfolders
Tree	Subdirectories, absolute and relative paths	No sharing
Acyclic graph	Links: sharing without copying	Deleting and traversing get harder
General graph	Unrestricted links	Cycles

Mounting a file system

Before using a file system you must mount it: its tree hangs from a directory of the existing tree, the mount point. That is what happens when you plug in a USB stick:

Protection

Many systems define privileges: each user can only perform certain operations. On a file you protect reading, writing, executing, appending and deleting; on a directory, listing, creating a file, renaming… The typical mechanisms:

• Access control lists (ACL): a list of <user, permissions> pairs per file.
• Passwords.
• Encryption: so that it cannot be read even if someone takes the physical device.

(The Unix rwx permissions you saw in Linux permissions are a compact version of this idea with three classes: owner, group and others).

How it is implemented: the layered file system

So far, what you see. Now, what the OS does underneath. The disk offers rewriting and random access, and transfers are done in blocks of sectors (usually 512 or 4096 bytes). On top of that row of blocks, the file system must achieve three things: allocate blocks to each file, manage free space and implement directories. It is organised in layers:

The file control block (in Unix, the i-node) is the structure that stores a file’s information, and the device driver is what talks to the hardware.

Space allocation: where each file’s blocks go

Each file needs a set of data blocks. Which ones? There are three basic techniques (contiguous, linked and indexed) and two special cases (the FAT, a variant of linked allocation, and contiguous with extents, used by NTFS).

To compare them, we will store the practical folder on the same disk with each technique. The disk has 32 blocks of 4 KiB, and some are already taken by other files:

The four files: practica.c (9,300 B), Makefile (410 B), datos.csv (12,288 B, exactly 3 × 4096) and informe.pdf (18,000 B). Blocks = size / 4096 rounding up: 3, 1, 3 and 5 (18,000 / 4096 = 4.39 → 5). Total: 12 blocks, and 18 are free. Does everything fit? It depends on the technique.

Contiguous allocation

Each file takes consecutive blocks. The directory only stores the first block and the length. We use the first hole where it fits:

practica.c goes from 2 to 4 (a hole of 3, exact); Makefile to 7; datos.csv from 8 to 10. And informe.pdf asks for 5 blocks in a row… and there is no hole of 5. There are 11 free blocks left, but the largest run has 4. That is external fragmentation, the same problem as contiguous memory allocation in Topic 9.

• Advantages: any access, sequential or direct, is very efficient (block k is at start + k) and, on magnetic disks, the heads barely move.
• Problems: fragmentation and growth: if datos.csv grows, where does it go? Do you reserve the maximum from the start (and waste space) or reserve as you go (and maybe it does not fit)?

Linked allocation

The blocks do not need to be contiguous: they form a linked list. Each block stores, at its end, the number of the next one. The directory stores the first block, the length and, sometimes, the last block (so that growing is easy):

Now informe.pdf fits with no trouble: 13 → 17 → 18 → 19 → 21. But look at the green box: with 4-byte links, each block only has 4092 useful bytes, and datos.csv, which fitted exactly in 3 blocks, needs 4 (3 × 4092 = 12,276 < 12,288). By 12 bytes.

• Advantage: external fragmentation and space reservation disappear at the root.
• Problems: direct access is expensive (to reach block k you must read the k blocks before it), space is spent on links and it is fragile: if a block in the middle of the file is damaged, everything after it is lost.

Variants to gain performance and robustness: double links (forwards and backwards) and a back link in every block pointing to the directory entry. Each extra link takes away useful bytes.

The FAT: all the links together

The FAT (File Allocation Table) is a variation of linked allocation born in MS-DOS that lives on in flash memory (VFAT, exFAT… and the FAT32 on my USB stick). The idea: take the links out of the blocks and gather them in a table at the start of the disk, with one entry per block. Entry b says which block follows b:

To read informe.pdf, the directory says “it starts at 12”; entry 12 says 13; entry 13 says 17… until a special end-of-file code. Since the blocks no longer store links, datos.csv takes 3 again.

• Advantages: access improves compared with linked allocation because the links can be cached; on small devices the whole FAT fits in RAM; and to walk a file you only need the FAT blocks that hold its links.
• Problem: if a block of the FAT is damaged, links of many files are lost at once. Solution: the disk keeps several copies of the FAT.

Indexed allocation

Another way to gather the links: each file has its own index block, and entry k of that block is the address of block k of the file. The directory stores the number of the index block (and the length, to know how many entries are in use):

• Advantages: no external fragmentation or space reservation, and direct access in constant time: index block + data block.
• Problems: an extra block per file, which hurts small files (Makefile, with 410 bytes, uses 2 blocks); one more access than contiguous (although the index block can be cached); and fragility: if the index block is damaged, the whole file is lost.

How many reads does block 4 of informe.pdf cost?

This is where the difference really shows. We want the fifth block (number 4, counting from 0):

Allocation	What the directory stores	Reads for block k	External fragmentation	If a block is damaged…
Contiguous	start and length	1 (start + k)	Yes	that block is lost
Linked	first (and last) block	k + 1	No	everything after it is lost
FAT	first block	1 if the FAT is in RAM	No	if it is a FAT block, many files
Indexed	index block	2	No	if it is the index block, the whole file

The Unix i-node: indexes on several levels

Indexed allocation has a catch: the block size limits how many indexes fit, and with it, the maximum file size. The example from the notes: 1 KiB blocks (1024 bytes) and 16-bit links (2 bytes). An index block holds 1024 / 2 = 512 entries, so a file has at most 512 blocks: 512 × 1 KiB = 512 KiB. Not even a short video.

Solutions? Indexes in several contiguous blocks (fragmentation is back), a linked list of index blocks (inefficient) or a multilevel structure: an index block that points to other index blocks. This was the Unix solution, and the structure that holds it is the i-node:

The i-node stores the attributes (mode, owners, timestamps, size, link count) and the pointers:

• 12 direct pointers: each one points to a data block. Small files (most of them) do not spend a single index block.
• Single indirect: points to an index block full of pointers to data.
• Double indirect: to an index block whose pointers lead to other index blocks.
• Triple indirect: one more level.

Working out the maximum size

The recipe: pointers per block N = block size / pointer size, and the maximum is (direct + N + N² + N³) × block size. With 4 KiB blocks and 4 B pointers, N = 4096 / 4 = 1024:

• Direct: 12 × 4 KiB = 48 KiB.
• Single: 1024 × 4 KiB = 4 MiB (cumulative: 4.05 MiB).
• Double: 1024² × 4 KiB = 2^20 × 2^12 B = 2^32 B = 4 GiB.
• Triple: 1024³ × 4 KiB = 2^30 × 2^12 B = 2^42 B = 4 TiB.

Notice that, with 1 KiB blocks (N = 256), the maximum drops to about 16 GiB: a big block wins on two fronts at once, more pointers per block and more bytes per block. And back to my USB stick: with i-nodes and 4 KiB blocks, the limit is in terabytes. FAT32’s limit did not come from the allocation method, but from the 32-bit field where it writes the size.

Which pointer leads to each block

With the i-node already in memory, each level of indirection is one more disk read. The direct pointers cover blocks 0-11; the single one, the next 1024 (12-1035); the double one, from 1036 to 1,049,611; and the triple one, the rest:

For block 50,000: 50,000 − 12 − 1024 = 48,964 → it is in the double level, so 3 reads (top index, bottom index and data). And a 300 MiB video is 300 × 2^20 / 2^12 = 76,800 data blocks, which spend 76 index blocks: 1 for the single and, in the double, the top one plus ⌈(76,800 − 1036) / 1024⌉ = 74 below.

Free-space management

To allocate blocks, the OS needs to know which ones are free. Three structures:

• Bitmap: a table in a fixed area of the disk with one bit per block (free or taken). It is what traditional Unix used. (Which value means “free” depends on the system: here we use 1 = taken).
• Linked list: the OS keeps a pointer to the first free block, which points to the next free one, and so on. Variant: the first free block acts as an index block listing the others.
• FAT: if a block is free, its FAT entry says so. The FAT itself is the free-space structure.

Size calculations: everything in powers of 2

In the exam they ask how big these structures are. The trick is to turn everything into powers of 2: 1 KiB = 2^10, 1 MiB = 2^20, 1 GiB = 2^30, 1 TiB = 2^40.

A 2 TiB disk with 32 KiB blocks:

• Blocks: 2^41 / 2^15 = 2^26 = 67,108,864.
• Bitmap: 2^26 bits = 2^26 / 2^3 = 2^23 bytes = 8 MiB.
• FAT with 4-byte entries: 2^26 × 2^2 = 2^28 bytes = 256 MiB (32 times the bitmap, because each entry has 32 bits instead of 1).

And the number of blocks of a file with linked allocation: a 2 MiB file (2,097,152 B) with 1 KiB blocks and 4 B links has 1020 useful bytes per block: 2,097,152 / 1020 = 2056.03 → 2057 blocks. With FAT or contiguous it would be exactly 2048.

Directory implementation

One question left: how is the list of names and attributes of a directory stored?

• Linear list: names with their pointers to the blocks and other attributes. Simple (a table), but performance is disastrous with thousands of entries: searching means comparing one by one.
• Hash table: the slot is computed from the name and you go straight there.
• B-trees (NTFS, ext4…): they work very well with many entries and, although they are more complex, they do not penalise space or kernel complexity much.

Common mistakes

Check it with Python

Two simulators with the article’s data, nothing to type in. Copy them into a .py file and run them.

Simulator 1: the same folder with the four allocation methods

# The IC2 practical folder on a 32-block disk: contiguous, linked, FAT and indexed
B, P = 4096, 4                         # 4 KiB block and 4-byte link
free_blocks = [2, 3, 4, 7, 8, 9, 10, 12, 13, 17, 18, 19, 21, 22, 23, 24, 28, 29]   # the rest are taken
files = {'practica.c': 9300, 'Makefile': 410, 'datos.csv': 12288, 'informe.pdf': 18000}
K = 4                                  # we will read block 4 (the fifth) of informe.pdf

def blocks_for(size, useful):          # round up: half a block takes a whole block
    return -(-size // useful)

def runs(remaining):                   # groups the free blocks into contiguous holes [start, length]
    h = []
    for b in remaining:
        if h and h[-1][0] + h[-1][1] == b:
            h[-1][1] += 1              # b follows the previous hole: extend it
        else:
            h.append([b, 1])           # b starts a new hole
    return h

print('CONTIGUOUS (first hole that fits)')
holes = runs(free_blocks)
for n, size in files.items():
    k = blocks_for(size, B)
    x = next((x for x in holes if x[1] >= k), None)
    if x:                              # it fits: take the start of the hole
        print(f'  {n:<12} start {x[0]:>2}  blocks {k}  wasted {k * B - size:>4} B')
        x[0] += k; x[1] -= k
    else:                              # there is room in total, but not in a row
        print(f'  {n:<12} DOES NOT FIT: needs {k}, largest hole {max(x[1] for x in holes)},'
              f' free {sum(x[1] for x in holes)}')
# linked: each block stores the link (4 B less data); FAT: the links live in the table
for name, useful, index, reads in (('LINKED', B - P, 0, K + 1), ('FAT', B, 0, 1), ('INDEXED', B, 1, 2)):
    remaining = list(free_blocks); print(name)
    for n, size in files.items():
        k = blocks_for(size, useful) + index    # indexed also spends an index block
        bs, remaining = remaining[:k], remaining[k:]
        print(f'  {n:<12} ' + (f'index {bs[0]:>2} | ' if index else '') + ' -> '.join(map(str, bs[index:])))
        if n == 'informe.pdf':
            read_info = f'  block {K} of {n}: disk {bs[index + K]}, reads {reads}'
    print(f'  used {len(free_blocks) - len(remaining)}, free {len(remaining)}'); print(read_info)

The hardest function to read is runs(), which turns the list of free blocks into holes [start, length]:

def runs(remaining):                  # groups the free blocks into contiguous holes [start, length]
    h = []
    for b in remaining:
        if h and h[-1][0] + h[-1][1] == b:
            h[-1][1] += 1             # b follows the previous hole: extend it
        else:
            h.append([b, 1])          # b starts a new hole
    return h

It walks the free blocks in order: if block b is exactly the next one after the end of the last hole (start + length == b), it extends that hole; otherwise it starts a new one. With 2, 3, 4, 7… you get [2, 3], then [7, …], and so on. This is the real output:

CONTIGUOUS (first hole that fits)
  practica.c   start  2  blocks 3  wasted 2988 B
  Makefile     start  7  blocks 1  wasted 3686 B
  datos.csv    start  8  blocks 3  wasted    0 B
  informe.pdf  DOES NOT FIT: needs 5, largest hole 4, free 11
LINKED
  practica.c   2 -> 3 -> 4
  Makefile     7
  datos.csv    8 -> 9 -> 10 -> 12
  informe.pdf  13 -> 17 -> 18 -> 19 -> 21
  used 13, free 5
  block 4 of informe.pdf: disk 21, reads 5
FAT
  practica.c   2 -> 3 -> 4
  Makefile     7
  datos.csv    8 -> 9 -> 10
  informe.pdf  12 -> 13 -> 17 -> 18 -> 19
  used 12, free 6
  block 4 of informe.pdf: disk 19, reads 1
INDEXED
  practica.c   index  2 | 3 -> 4 -> 7
  Makefile     index  8 | 9
  datos.csv    index 10 | 12 -> 13 -> 17
  informe.pdf  index 18 | 19 -> 21 -> 22 -> 23 -> 24
  used 16, free 2
  block 4 of informe.pdf: disk 24, reads 2

What to look at:

1. Contiguous allocation fails with free space: informe.pdf asks for 5, the largest hole is 4 and 11 are free. External fragmentation in its purest form.
2. The link eats bytes: with linked allocation, datos.csv goes from 3 blocks to 4 (8 -> 9 -> 10 -> 12) and 13 blocks are used in total against 12 with the FAT.
3. Indexed allocation spends one block per file: 16 used (12 of data + 4 of index); Makefile takes 2 blocks for 410 bytes.
4. The same logical block lives in different places: block 4 of informe.pdf is disk block 21, 19 or 24 depending on the technique, and costs 5, 1 or 2 reads.
5. The wasted column is internal fragmentation: Makefile wastes 3686 of its 4096 bytes.

Simulator 2: the maximum size with an i-node

# Maximum file size with an i-node: 12 direct pointers + single, double and triple indirect
P, D = 4, 12                           # 4-byte pointer and 12 direct pointers

def readable(b):                       # bytes -> the largest binary unit that is not too big
    for u, e in (('TiB', 40), ('GiB', 30), ('MiB', 20), ('KiB', 10)):
        if b >= 2 ** e:
            return f'{b / 2 ** e:.2f} {u}'
    return f'{b} B'

def levels(B):                         # data blocks reached by each i-node pointer
    N = B // P                         # pointers that fit in an index block
    return [('direct', D), ('single', N), ('double', N ** 2), ('triple', N ** 3)]

for B in (1024, 4096):
    print(f'Block size {B} B -> {B // P} pointers per index block')
    total = 0
    for name, n in levels(B):
        total += n                     # the maximum is the sum of the four levels
        print(f'  {name:<9}{n:>14} blocks  cumulative {readable(total * B):>11}')

B, N = 4096, 1024
def path_to(k):                        # which pointer leads to logical block k and how many reads it costs
    for reads, (name, n) in enumerate(levels(B), start=1):
        if k < n:
            return name, reads         # with the i-node in RAM: 1 + one index block per level
        k -= n                         # k is not in this level: move on to the next

print('Block size 4096 B, i-node already in memory:')
for k in (5, 500, 50000, 2000000):
    name, reads = path_to(k)
    print(f'  block {k:>7}: pointer {name:<9} reads {reads}')
data = -(-300 * 2 ** 20 // B)          # a 300 MiB video of the practical defence
rest, index_blocks = data - D, 0
if rest > 0:
    index_blocks += 1; rest -= N       # the single indirect: one index block
if rest > 0:                           # the double: the top block + as many as needed below
    index_blocks += 1 + -(-min(rest, N * N) // N); rest -= N * N
print(f'Video of 300 MiB: {data} data blocks + {index_blocks} index blocks ({readable(index_blocks * B)})')

levels() returns how many data blocks each pointer reaches (12, N, N², N³), and path_to() keeps subtracting levels until it finds the one block k falls in: the same method as the hint above. Real output:

Block size 1024 B -> 256 pointers per index block
  direct               12 blocks  cumulative   12.00 KiB
  single              256 blocks  cumulative  268.00 KiB
  double            65536 blocks  cumulative   64.26 MiB
  triple         16777216 blocks  cumulative   16.06 GiB
Block size 4096 B -> 1024 pointers per index block
  direct               12 blocks  cumulative   48.00 KiB
  single             1024 blocks  cumulative    4.05 MiB
  double          1048576 blocks  cumulative    4.00 GiB
  triple       1073741824 blocks  cumulative    4.00 TiB
Block size 4096 B, i-node already in memory:
  block       5: pointer direct    reads 1
  block     500: pointer single    reads 2
  block   50000: pointer double    reads 3
  block 2000000: pointer triple    reads 4
Video of 300 MiB: 76800 data blocks + 76 index blocks (304.00 KiB)

What to look at:

1. With 1 KiB, the triple level reaches 16.06 GiB; with 4 KiB, 4.00 TiB: quadrupling the block multiplies the maximum by about 256.
2. The direct pointers add almost nothing (48 KiB) but they spare small files from needing index blocks.
3. Reads go up one at a time with each level: 1, 2, 3 and 4.
4. The video’s 76 index blocks take 304 KiB: less than 0.1 % of its 300 MiB.

Summary

Concept	The essentials
File	Named object that stores persistent information; 7 attributes
Operations	Create, write, read, reposition, delete, truncate; open/close so as not to go to the directory every time
Access	Sequential (tape), direct (lseek), indexed (key)
Directories	Single level → two levels → tree → acyclic graph (links) → general graph (cycles)
Links	Hard: same i-node and counter; symbolic: stores the path, breaks when the original is deleted
Allocation	Contiguous (fragmentation), linked (expensive direct access), FAT (links in a table), indexed (extra block)
i-node	12 direct + single + double + triple; maximum = (12 + N + N² + N³) × block
Free space	Bitmap, linked list or the FAT itself
Directories inside	Linear list, hash table, B-tree

Three ideas to take away:

1. A file is an abstraction: you see a name, the API sees bytes and the kernel sees blocks.
2. Each allocation technique decides where the links live (in the directory, in the blocks, in a table or in an index block), and direct access, fragmentation and fragility depend on that.
3. Calculations always work the same way: everything in powers of 2, subtract what is not data and round up.

This is the end of the IC2 theory. Now it is time to practice. First, in the file systems guided practice we solve i-node calculations and how many blocks have to be read, step by step; then, in the file systems exercises you have a test with every exam format, calculations of blocks, i-nodes and bitmaps with self-marking boxes, open questions and the cheat sheet. See you there!

Next step: practiceFile systems — practice with guided problems step by step: blocks and internal fragmentation, reads by allocation method, the i-node and an exercise in the exam format (and the block I counted from 1)

Did this article help you? Here is how you can support SergioLearns →