Inode calculator: block pointers and file size

Enter the block size, the size of a block pointer (disk address) and how many direct, single, double and triple indirect pointers the inode has. Sizes can be written as plain bytes (4096), with units (4 KB, 1.5 GB) or as powers of two (2^32). The panel on the right gives the largest file the inode can describe; the diagram traces the pointers from the inode to the block holding the byte offset you enter, and counts the disk reads.

• If your exercise says the file is already open, set the inode to "Already in memory": the read count then leaves out the inode.
• Copy answer gives the working as text; Copy link reopens the same exercise.

In Unix file systems every file is described by an inode, a small fixed-size record holding the file's size, owner, permissions and timestamps, and the locations of its data blocks on disk. A directory is a list of names, each paired with an inode number, so a file's name is not part of its inode, and one inode can have several names (hard links).

The data itself is stored in fixed-size blocks, which need not be next to each other on disk. The inode has room for only a few block addresses, so a large file's addresses are kept in further blocks, called indirect blocks, that the inode points to.

The classic layout, used by ext2 and ext3, has 15 pointers in the inode. The first 12 are direct: each holds the address of one data block. The 13th points to a single indirect block, a block filled with addresses of data blocks. The 14th points to a double indirect block, whose entries point to single indirect blocks, and the 15th to a triple indirect block, one level deeper again.

If a block holds K pointers (the block size divided by the pointer size), the single indirect pointer reaches K data blocks, the double K² and the triple K³. Since most files are small, the direct pointers handle them with no extra reads, and only large files pay for the indirect levels. With 4 KB blocks and 4-byte pointers, K = 1,024:

The largest file is the number of data blocks the inode can reach times the block size: (12 + K + K² + K³) × block size for the ext2 layout. Operating Systems: Three Easy Pieces works the first step: with 12 direct pointers and one single indirect pointer, 4 KB blocks and 4-byte addresses, a file can grow to (12 + 1,024) × 4 KB = 4,144 KB, and adding a double indirect pointer takes it to 4.003 GiB. The calculator gives these maximums for the full ext2 layout:

To read byte X, divide by the block size to get the logical block number, then subtract the blocks each level covers until X falls inside one. Take byte 10 MB (10,485,760) on ext2 with 4 KB blocks. It is in logical block 2,560. The direct and single indirect pointers cover the first 1,036 blocks, so this one is in the double indirect range: double indirect pointer, then entry 1 points to a single indirect block, then entry 500 points to the data block, then byte 0 of the data block.

Reading it from a file that isn't open takes 4 disk reads: the inode, the double indirect block, the single indirect block and the data block. In general a byte costs one read per level of indirection plus one for the data, plus one for the inode unless it is already in memory. A real system caches inodes and indirect blocks, so reading a file from start to finish reads each indirect block only once.

A file needs ⌈size / block size⌉ data blocks plus the indirect blocks that point to them: one single indirect block once it passes the direct pointers, then a double indirect block and one more single indirect block for every K data blocks beyond that, and so on. For ext2 with 4 KB blocks:

• What KB means. Operating systems exercises nearly always mean 1,024 bytes; reading 4 KB as 4,000 bytes gives 1,000 pointers per block instead of 1,024 and a different answer.
• Whether the inode read counts. Some exercises assume the file is open and its inode cached; others count reading the inode.
• The number of direct pointers. ext2 and ext3 have 12; textbook exercises often use 10 or another number, and some give the inode two single indirect pointers.
• Units in the answer. The ext2 maximum with 4 KB blocks, 4,402,345,721,856 bytes, is 4.003 TiB; most answers round it to "about 4 TB".
• The disk limit. Some exercises also ask whether the pointer size or a file-size field limits the file before the pointer tree does.

A block map stores one address per block, even when a file's blocks lie one after another on disk. ext4 normally uses the same 60 bytes of the inode for the root of an extent tree instead. An extent records a starting block and a length, up to 32,768 blocks, and four extents fit in the inode itself, so a large file stored contiguously needs no indirect blocks at all. ext4 still reads files that use the old block map, which its documentation describes with the same 12 direct pointers and three indirect ones.

Creating a file changes several blocks at once: the inode, the free-block bitmap, the directory and the indirect blocks. A crash halfway through can leave them inconsistent, so ext3 and ext4 write the changes to a journal first and only then to their final places; after a crash the journal is replayed. Operating Systems: Three Easy Pieces covers this in its chapter on crash consistency.