Part 4 of 7 · 5 min read
Finding an inode
Think of a hotel where room numbers go up the floors in order, 16 rooms to a floor. Room 100 is therefore on a floor that you can compute, at a place on that floor that you can also compute. The analogy stops in one place: a hotel has gaps in its numbering, while inode numbers have no gaps in the table.
In plain words: Inodes are stored in one array, in order of number, starting at inode 1. To find inode N, the file system takes the start of the inode table, and adds (N - 1) times the inode size. It needs no search. With 4 KiB blocks and 256-byte inodes, 16 inodes fit in a block, so the block is table start + (N - 1) / 16 and the offset in it is ((N - 1) mod 16) x 256. This is why a lookup of an inode by number is one read.
A worked example (made up to show the idea). On the test image the table starts at block 35. Inode 13 is in block 35 + 12 / 16 = 35, at the offset 12 x 256 = 3,072. A made-up inode 4,000 is in block 35 + 3,999 / 16 = 35 + 249 = 284, at the offset (3,999 mod 16) x 256 = 15 x 256 = 3,840. The program below reads the superblock, finds the table, and prints the facts of one inode.
The key lines.
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/* Read the superblock and one inode of an ext4 image directly, with no library.
All fields are little-endian, so a little-endian machine can copy them as they are. */
static uint8_t *at(FILE *f, long off, size_t n) {
uint8_t *b = malloc(n);
if (fseek(f, off, SEEK_SET) || fread(b, 1, n, f) != n) { perror("read"); exit(1); }
return b;
}
static uint32_t u32(const uint8_t *p) { uint32_t v; memcpy(&v, p, 4); return v; }
static uint16_t u16(const uint8_t *p) { uint16_t v; memcpy(&v, p, 2); return v; }
int main(int argc, char **argv) {
if (argc < 3) return 1;
FILE *f = fopen(argv[1], "rb");
unsigned ino = (unsigned)atoi(argv[2]);
uint8_t *sb = at(f, 1024, 1024); /* the superblock is at byte 1024 */
unsigned bsize = 1024u << u32(sb + 24); /* s_log_block_size */
unsigned per_group = u32(sb + 40), isize = u16(sb + 88); /* inodes per group, inode size */
printf("magic 0x%04x, block size %u, blocks %u, inodes %u, inode size %u\n",
u16(sb + 56), bsize, u32(sb + 4), u32(sb + 0), isize);
uint8_t *gd = at(f, bsize, 64); /* group descriptors: the block after the superblock's */
unsigned itable = u32(gd + 8); /* bg_inode_table_lo of group 0 */
unsigned idx = (ino - 1) % per_group;
long where = (long)itable * bsize + (long)idx * isize;
printf("inode table of group 0 starts at block %u\n", itable);
printf("inode %u is at byte %ld: block %u, offset %u\n", ino, where,
(unsigned)(where / bsize), (unsigned)(where % bsize));
uint8_t *in = at(f, where, isize);
printf("mode 0%o, size %u, links %u, 512-byte units %u\n",
u16(in + 0), u32(in + 4), u16(in + 26), u32(in + 28));
return 0;
}
Output for four inodes of the test image:
magic 0xef53, block size 4096, blocks 4096, inodes 4096, inode size 256
inode table of group 0 starts at block 35
inode 2 is at byte 143616: block 35, offset 256
mode 040755, size 4096, links 4, 512-byte units 8
inode 12 is at byte 146176: block 35, offset 2816
mode 0100644, size 1, links 1, 512-byte units 8
inode 13 is at byte 146432: block 35, offset 3072
mode 0100644, size 10000, links 1, 512-byte units 24
inode 14 is at byte 146688: block 35, offset 3328
mode 0100644, size 1048576, links 1, 512-byte units 2048
These values agree with debugfs. The mode 040755 starts with 04, the type of a directory, and 0100644 starts with 010, the type of a regular file. The root directory, inode 2, has 4 links, because it has the entries ., .. and the .. of its two subdirectories (lost+found and sub).
Inode table
The inode table is the array of all inode records of a block group, stored in order of inode number. The position of an inode is computed from its number, the start of the table and the inode size, so a lookup by number needs one block read.
Example: inode 13 is the 13th record, in block 35 at byte offset 3,072.
Check yourself: 1. How many 256-byte inodes fit in a 4 KiB block? 2. In which block and at which offset is inode 100 if the table starts at block 35? 3. Why does the root directory have 4 links on the test image?