Extended File System (ext) format

The Extended File System (ext) is one of the more common file system used in Linux.

There are multiple version of ext.

Overview

An Extended File System (ext) consists of:

• one or more block groups

Characteristics

Block group

A block group consists of:

• optional 1024 bytes of boot code or zero bytes (at offset: 0)
• optional superblock
• optional group descriptor table
• block bitmap
• inode bitmap
• allocated and unallocated blocks

The primary superblock is stored at offset 1024 relative from the start of the volume. Backup superblocks are stored at offset 1024 relative from the start of the block group if block size <= 1024 or otherwise at offset 0 from the start of the block group.

The group descriptor table is stored in the block after the superblock.

An ext2 file system with revision 0 stores a copy at the start of every block group, along with backups of the group descriptor table. Later revisions reduce the number of backup copies by only putting backups in specific groups (sparse superblock feature EXT2_FEATURE_RO_COMPAT_SPARSE_SUPER).

Not all values in a backup superblock and backup group descriptor tables match those of the primary superblock and group descriptor table.

Note that backup superblocks can be empty (filled with 0-byte values) or contain remnant data on an Android ext file system with sparse_super.

Flex block groups

Flex (or flexible) block groups are a set of block groups that treated as a single logical block group. Metadata such as the superblock, group descriptors, data block bitmaps spans the entire logical block group and not the individual block groups part of the set.

Meta block groups

Meta block groups (META_BG) are a set (or cluster) of block groups, for which its group descriptor structures can be stored in a single block.

The first meta block group value in the superblock indicates what the first

meta block group value is 256, and the number of group descriptors that can be stored in a single block 64, then the group descriptors for the block groups [0, 16383] are stored in the group descriptor table after the primary superblock and corresponding locations of backups.

Successive group descriptor tables, for example [16384, 16447], are stored in the first block group of a meta block group and backups in the second and last block groups of the meta block group.

Blocks

The volume is devided in blocks:

block offset = block number * block size

The block size is defined in the superblock.

Note that mke2fs indicates the maximum block size is 65536.

The superblock

The ext2 superblock

The ext2 superblock is 208 bytes in size and consists of:

The ext3 superblock

The ext3 superblock is 336 bytes in size and consists of:

The ext4 superblock

The superblock is 1024 bytes in size and consists of:

If checksum type is CRC-32C, the checksum is stored as 0xffffffff - CRC-32C.

Note that some versions of mkfs.ext set the file system creation time even for ext2 and when EXT3_FEATURE_COMPAT_HAS_JOURNAL is not set.

TODO: Is the only way to determine the file system version the compatibility and equivalent flags?

Checksum calculation

If checksum type is CRC-32C, the CRC32-C algorithm with the Castagnoli polynomial (0x1edc6f41) and initial value of 0 is used to calculate the checksum.

The checksum is calculated over the 1020 bytes of data of the suberblock.

Metadata checksum seed calculation

If checksum type is CRC-32C, the CRC32-C algorithm with the Castagnoli polynomial (0x1edc6f41) and initial value of 0 is used to calculate the checksum.

The checksum is calculated over:

• the 16 byte file system identifier in the superblock

If EXT4_FEATURE_INCOMPAT_CSUM_SEED is set the metadata checksum seed value stored in the superblock should be used instead of calculating it based on the file system identifier.

If checksum type is CRC-32C, the metadata checksum seed is stored as 0xffffffff - CRC-32C.

File system state flags

Error-handling status

Creator operating system

Format revision

Compatible feature flags

Note that EXT2_FEATURE_COMPAT_, EXT3_FEATURE_COMPAT_, EXT4_FEATURE_COMPAT_ and COMPAT_ can be used interchangeably.

Incompatible feature flags

Note that EXT2_FEATURE_INCOMPAT_, EXT3_FEATURE_INCOMPAT_, EXT4_FEATURE_INCOMPAT_ and INCOMPAT_ can be used interchangeably.

Read-only compatible feature flags

EXT2_FEATURE_RO_COMPAT_, EXT3_FEATURE_RO_COMPAT_, EXT4_FEATURE_RO_COMPAT_ and RO_COMPAT_ are used interchangeably.

Note that in some ext file systems used by ChromeOS it has been observed that the upper 8-bits of the read-only compatible feature flags are set as in 0xff000003. debugfs identifies these as FEATURE_R24 - FEATURE_R31.

Checksum types

The group descriptor table

The group descriptor table is stored in the block following the superblock.

The group descriptor table consist of:

• one or more group descriptors

The ext2 and ext3 group descriptor

The ext2 and ext3 group descriptor is 32 bytes in size and consists of:

Note that it has been observed that implementations that support ext4 can set a value in the padding. It is currently assumed that this value contains block group flags.

The ext4 group descriptor

The ext4 group descriptor is 68 bytes in size and consists of:

If checksum type is CRC-32C, the checksum is stored as the lower 16-bits of 0xffffffff - CRC-32C, otherwise the checksum is stored as a CRC-16.

Checksum calculation

If checksum type is CRC-32C, the CRC32-C algorithm with the Castagnoli polynomial (0x1edc6f41) and initial value of 0 is used to calculate the checksum.

The checksum is calculated over:

• the 16 byte file system identifier in the superblock
• the group number as a 32-bit little-endian integer
• the data of the group descriptor with the checksum set to 0-byte values

TODO: describe the block bitmap checksum calculation: crc32c(s_uuid+grp_num+bbitmap)

TODO: describe the inode bitmap checksum calculation: crc32c(s_uuid+grp_num+ibitmap)

Block group flags

Direct and indirect blocks

Direct blocks are blocks that part of the data stream of a file entry.

A direct block number is 0 that is part of the data stream represents a sparse data block.

Indirect blocks are blocks that refer to blocks containing direct or indirect block numbers. There are multiple levels of indirect block:

• indirect blocks (level 1), that refer to direct blocks
• double indirect blocks (level 2), that refer to indirect blocks
• triple indirect blocks (level 3), that refer to double indirect blocks

An indirect block number is 0 that is part of the data stream represents sparse data blocks.

Extents

Extents were introduced in ext4 and are controlled by EXT4_FEATURE_INCOMPAT_EXTENTS.

Extents form an extent B-Tree, where:

• extent indexes are stored in the branch nodes and
• extent descriptors are stored in the leaf nodes.

An extents B-tree node consists of:

• extents header
• extents entries
• extents footer

Note that inodes can have an implicit last sparse extent if the the inode data size is greater than the total data size defined by the extent descriptors.

The ext4 extents header

The ext4 extents header (ext4_extent_header) is 12 bytes in size and consists of:

The ext4 extent descriptor

The ext4 extent descriptor (ext4_extent) is 12 bytes in size and consists of:

If number of blocks > 32768 the extent is considered “uninitialized” which is (as far as currently known) comparable to extent being sparse. The number of blocks of the sparse extent can be determined as following:

sparse_number_of_blocks = number_of_blocks - 32768

Sparse extents can exist between the extent descriptors. In such a case the logical block number will not align with the information from the previous extent descriptors.

Note that the native Linux ext implementation expects the extents to be stored in order of logical block number.

The ext4 extents index

The ext4 extent index (ext4_extent_idx) is 12 bytes in size and consists of:

The ext4 extents footer

The ext4 extents footer (ext4_extent_tail) is 4 bytes in size and consists of:

The inode

The size of the inode is defined in the superblock when dynamic inode information is present.

Note that the ext4 inode format can be used on ext2 formatted file system. This was observed in combination with format revision 1 and inode size > 128 created by mkfs.ext2.

The ext2 inode

The ext2 inode is 128 bytes in size and consists of:

Note that for a character and block device the first 2 bytes of the array of direct block numbers contain the minor and major device number respectively.

If the inode size is larger than 128 bytes, the additional data can be stored using an ext4 inode extension.

The ext3 inode

The ext3 inode is 132 bytes in size and consists of:

Note that for a character and block device the first 2 bytes of the array of direct block numbers contain the minor and major device number respectively.

If the inode size is larger than 128 bytes, the additional data can be stored using an ext4 inode extension.

The ext4 inode

The ext4 inode is 160 bytes in size and consists of:

If checksum type is CRC-32C, the checksum is stored as 0xffffffff - CRC-32C.

Note that for a character and block device the first 2 bytes of the array of direct block numbers contain the minor and major device number respectively.

Checksum calculation

If checksum type is CRC-32C, the CRC32-C algorithm with the Castagnoli polynomial (0x1edc6f41) and initial value of 0 is used to calculate the checksum.

The checksum is calculated from:

• the 16 byte file system identifier in the superblock
• the inode number as a 32-bit little-endian integer
• the NFS generation number in the inode as a 32-bit little-endian integer
• the data of the inode with the lower and upper part of the checksum set to 0-byte values.

Extra precision

The ext4 extra precision is 4 bytes in size and consists of:

The 34 bits extra precision timestamp (in number of seconds) can be calculated as following:

extra_precision_timestamp = (extra_epoch_value * 0x100000000) + timestamp

Notes

It has been observed that when EXT4_EA_INODE_FL is set the (last) modification time can contain a valid timestamp.

According to The Linux Kernel documentation

For backward compatibility with older versions of this feature, the i_mtime/i_generation may store a back-reference to the inode number and i_generation of the one owning inode (in cases where the EA inode is not referenced by multiple inodes) to verify that the EA inode is the correct one being accessed.

File mode

Inode flags

Reserved inode numbers

Inline data

ext4 supports storing file entry data inline when the inode flag EXT4_INLINE_DATA_FL is set.

Note that inodes can have an implicit last sparse extent if the the inode data size is greater than 60 bytes.

Huge files

TODO: complete section

Directory entries

Directories entries are stored in the data blocks of a directory inode. The directory entries can be stored in multiple ways:

• as linear directory entries
• as inline data directory entries
• as hash-tree directory entries

Linear directory entries

Linear directories entries are stored in a series of allocation blocks.

Linear directory entries contain:

• directory entry for “.” (self)
• directory entry for “..” (parent)
• directory entry for other file system entries

The directory entry

The directory entry is of variable size, at most 263 bytes, and consists of:

Older directory entry structures considered the name size a 16-bit value, but the upper byte was never used.

The name can contain any character value except the path segment separator (‘/’) and the NUL-character (‘\0’).

File types

Inline data directory entries

ext4 supports storing the directory entries as inline data when the inode flag EXT4_INLINE_DATA_FL is set.

The inline data directory entries is of variable size, at most 60 bytes, and consists of:

Hash tree directory entries

The data of the hash tree (HTree) is stored in the data blocs or extent defined by the directory inode. The hash-indexed directory entries are read-compatible with the linear directory entry.

Hash tree root

The hash tree root consists of:

• dx_root
  • directory entry for “.” (self)
  • directory entry for “..” (parent)
  • dx_root_info
  • Array of dx_entry
• directory entry for other file system entries

dx_root_info

dx_entry

TODO: complete section

struct dx_entry
{
        __le32 hash;
        __le32 block;
};

Symbolic links

If the target path of a symbolic link is less than 60 characters long, it is stored in the 60 bytes in the inode that are normally used for the 12 direct and 3 indirect block numbers. If the target path is longer than 60 characters, a block is allocated, and the block contains the target path. The inode data size contains the length of the target path.

Extended attributes

Extended attributes can be stored:

• in the inode block after the inode data
• in the block referenced by the file ACL (or extended attributes) block number, if not 0

Note that both should be read to get the all the extended attributes.

Extended attributes consists of:

• An extended attributes header
• Extended attributes entries with a terminator

The extended attributes inode header

The extended attributes inode header (ext2_xattr_ibody_header, ext3_xattr_ibody_header, ext4_xattr_ibody_header) is 4 bytes in size and consists of:

The extended attributes block header

The ext2 and ext3 extended attributes block header

The ext2 and ext3 extended attributes block header (ext2_xattr_header, ext3_xattr_header) is 32 bytes in size and consists of:

The ext4 extended attributes block header

The ext4 extended attributes block header (ext4_xattr_header) is 32 bytes of size and consists of:

The extended attributes entry

The extended attributes entry (ext2_xattr_entry, ext3_xattr_entry, ext4_xattr_entry) is of variable size and consists of:

The last extended attributes entry has the first 4 values set to 0 (8 bytes) and is used as a terminator.

Note that some implementations of older Android versions of ext appear to only set the first 4 bytes to 0 for the terminator.

The extended attribute name index

The name index indicates the prefix of the extended attribute name.

Journal

The journal was introduced in ext3.

TODO: complete section

Exclude bitmap

TODO: complete section

Note that the excluded bitmap is used for snapshots.

Corruption scenarios

File entry with invalid extents header signature

File content inaccessible but file entry metadata and extended attributes accessible.

References

• ext4 Data Structures and Algorithms, by the Linux kernel documentation