Indexed Allocation, and What a Real File System Does

About four terabytes, and the shape of the scheme is the point: a small file needs no index block at all, because its blocks fit in the twelve direct pointers, and a file of forty eight kilobytes or less is read in one access per block. The cost rises only for the parts of a file that are large.

Which pointer holds logical block 5,000

The standard sum. The ranges first:

Block 5,000 is in the double indirect range. Its position inside it:

Entry 3 of the double indirect block, then entry 892 of the index block it names, then the data block: three accesses, and the arithmetic is a subtraction and a division.

Note the direction of the sum, because it is the mistake to avoid: subtract the start of the range first, then divide. Dividing 5,000 by 1024 without subtracting gives the wrong entry.

What a real file system does

ext4 does not keep a list of block pointers at all. It keeps extents: a run of consecutive blocks recorded as a start and a length, exactly Chapter one hundred seven's contiguous allocation, in a tree when there are many of them.

The four inode pointers of the combined scheme are still the right thing to learn, because they are what the paper asks for and because the arithmetic is the same idea: the cost of reaching a block rises with how far into the file it is.

A file that occupies no blocks at all

One last measurement, and it shows what a pointer of zero means. Two files of a hundred kilobytes are written into the image: one of random bytes, one of zeros.

$ mkfs.ext4 -q -F -b 1024 -I 256 -O ^has_journal sparse.fs 8192 2>&1 | grep -v deprecated
Creating regular file sparse.fs
$ dd if=/dev/urandom of=solid.dat bs=1024 count=100 status=none
$ dd if=/dev/zero of=holey.dat bs=1024 count=100 status=none
$ debugfs -w -R "write solid.dat solid.dat" sparse.fs > /dev/null 2>&1; debugfs -w -R "write holey.dat holey.dat" sparse.fs > /dev/null 2>&1; echo both written
both written
$ debugfs -R "stat <12>" sparse.fs 2>/dev/null | awk '/Size:/ {print "the file of random bytes is", $NF, "bytes"; exit}'
the file of random bytes is 102400 bytes
$ debugfs -R "stat <12>" sparse.fs 2>/dev/null | awk '/^Links/ {print "and it holds", $4, "units of 512 bytes"}'
and it holds 200 units of 512 bytes
$ debugfs -R "stat <13>" sparse.fs 2>/dev/null | awk '/Size:/ {print "the file of zeros is", $NF, "bytes"; exit}'
the file of zeros is 102400 bytes
$ debugfs -R "stat <13>" sparse.fs 2>/dev/null | awk '/^Links/ {print "and it holds", $4, "units of 512 bytes"}'
and it holds 0 units of 512 bytes

Two files of 102,400 bytes: one occupies 200 units of 512 bytes, which is the hundred kilobytes, and the other occupies none.

A file with no blocks that is a hundred kilobytes long is called a sparse file, and the hole is a pointer of zero. A read of a hole returns zeros without any disk access; a write into a hole allocates a block then. It follows directly from indexed allocation: a pointer can say "no block", and nothing in the scheme has to change. It is how a database file of a terabyte can sit on a disk of a gigabyte, and it is why the size of a file and the space it uses are two different numbers, as Chapter ninety eight first showed with six bytes in 4,096.

Distinctions that carry marks

What it does not mean

An index block is not the inode. The inode points at it; on UNIX the first fifteen pointers are in the inode itself.

The combined scheme is not three schemes. It is one, with the cost of reaching a block rising with its position.

Indexed allocation does not give constant time access. It gives one access per level, and the deepest level is four.

A sparse file is not compressed. Nothing is encoded: the pointers simply say there is no block.

Extents are not a fourth method. They are contiguous allocation applied run by run, recorded in a tree.

Quick revision

• Indexed allocation: an index block of pointers, so no external fragmentation, free

growth, and direct access in two accesses. It wastes a whole block on a small file and limits the file to the block's pointer count.

• 1024 byte blocks and 4 byte pointers give 256 pointers, so one index block limits a file to

256 × 1024 = 262,144 bytes.

• Bigger indexes: linked index blocks, a multilevel index (256 × 256, which is

65,536 blocks, 64 megabytes, three accesses), or the combined scheme.

• The UNIX inode: 12 direct, single, double and triple indirect. With 4096

byte blocks and 4 byte pointers, 1024 pointers a block: 48 kilobytes, 4 megabytes, 4 gigabytes and 4 terabytes, at 1, 2, 3 and 4 accesses.

• Ranges: 0 to 11 direct, 12 to 1035 single indirect, 1036 to 1,049,611 double

indirect.

• Block 5,000: 5000 - 1036 = 3964, then dividing 3964 by 1024 gives 3 remainder 892,

so entry 3 then entry 892. Subtract the start of the range before dividing.

• ext4 uses extents, one entry per run of consecutive blocks, in a tree.
• Measured: two files of 102,400 bytes, one holding 200 units of 512 bytes and the other

0. A sparse file's hole is a pointer of zero: a read returns zeros with no disk access.

Test yourself

1. What does indexed allocation keep, and what does direct access cost? An index block

holding the pointers to all the file's data blocks; direct access costs two accesses, the index and the data, or one if the index is cached.

1. Give the two objections to a single index block. A whole block of pointers is used even by

a tiny file, and the file can have no more blocks than the index block has pointers.

1. With 1024 byte blocks and 4 byte pointers, how large a file can one index block describe?

256 pointers, so 256 × 1024 = 262,144 bytes. 4. Name the three ways of enlarging the index, and the largest file a two level index gives with 256 pointers a block. Linked index blocks, a multilevel index, and the combined scheme; two levels give 256 × 256, which is 65,536 blocks, 64 megabytes. 5. Give the four parts of the UNIX combined scheme and what each reaches with 4 kilobyte blocks. Twelve direct pointers reaching 48 kilobytes; a single indirect reaching 4 megabytes; a double indirect reaching 4 gigabytes; a triple indirect reaching 4 terabytes.

1. How many accesses does a read from the double indirect part need? Three: the double

indirect block, the index block it names, and the data block.

1. Which pointer reaches logical block 5,000, and which entries? The double indirect:

5000 - 1036 = 3964, and dividing 3964 by 1024 gives 3 remainder 892, so entry 3 of the double indirect block and entry 892 of the index block it names.

1. What does ext4 keep instead of block pointers? Extents: one entry for each run of

consecutive blocks, held in a tree when there are many.

1. Two files are both 102,400 bytes and one occupies no blocks. Explain. The second is

sparse: its pointers say there is no block, so a read of those parts returns zeros without any disk access and a write allocates a block at that moment.