IDTFS File Format

1. Introduction

Indexed Delegator Filesystem (IDTFS) is a kind of filesystem, which delegates accesses and modifications to files to one of some backing filesystems.

To determine the corresponding backing file of a given file path, an implementation has to lookup a mapping. The IDTFS file format is designed for representing and exchanging this kind of mapping tree.

What the Core Module defines is the most basic level of IDTFS which is a read-only filesystem and does not care about write transactions like item allocations.

2. Overview

The IDTFS file format consists of multiple modules, of which all implementers must implement all features of the Core Module.

IDTFS files are made up of blocks. The size of a block must be a power of 2 and the exponent must be greater than or equal to 8.

Tip	That is to say, the block size must be greater than or equal to 256, in order to reduce corner cases where the block size is too small and some fundamental structures like the superblock are placed across two or more blocks.

Note	For image creators, it is recommended to prefer to a larger block size by default, such as 4096.

IDTFS always stores integers in little endian format.

3. Superblock

An IDTFS image starts with a superblock and the superblock references other structures.

The superblock consists of two sections: a header and an attribute array.

3.1. Header

The header section is padded to 64 bytes using zero bytes.

Table 1. Structure of superblock headers
Offset	Size	Type	Name	Description
0x00	4	`u32`	`magic`	Must be set to `0x1DE0F577`.
0x04	4	`u32`	`checksum`	CRC32-C checksum of the superblock, including attributes. When calculating the checksum, value of the checksum field is assumed to be zero.
0x08	1	`u8`	`version`	Must be set to 1.
0x09	1	`u8`	`blksz_bits`	\(log_2(block\_size)\)
0x0A	2	`u16`	`sb_attrs`	Number of superblock attributes.
0x0C	4		reserved	Must be filled with 0.
0x10	16	`u8[]`	`uuid`	128-bit UUID of this volume.
0x20	8	`u64`	`creation_time`	Creation time of this filesystem in seconds since the UNIX epoch.
0x28	24		reserved	Must be filled with 0.

3.2. Attributes

The header is immediately followed by the attribute array which consists of sb.hdr.sb_attrs entries.

Table 2. Structure of superblock attribute entry
Offset	Size	Type	Name	Description
0x00	8	`u64`	`id`	Identifier of this attribute.
0x08	24		reserved	Reserved for attribute data.

An attribute is uniquely identified with its ID. ID range 0x00000000-0xFFFFFFFF and 0x80000000'00000000-0x80000000’FFFFFFFF are reserved for official modules.

Authors of extension modules may declare their own attribute ID. The ID for third-party modules should be picked randomly and must not conflict with the reserved range.

Tip	Authors of extension modules should introduce at least one new superblock attribute, if possible, even if the attribute data field is completely unused, as a "feature flag".

If the MSB of id is set, then the attribute is "incompatible" and implementations that do not support the attribute must refuse to load this file. Otherwise, implementations may ignore the attribute.

4. Volume Label

Volume labels can be found using a specific superblock attribute.

Table 3. Structure of volume label attribute (`compat:0:4B18`)
Offset	Size	Type	Name	Description
0x00	8	`u64`	`id`	Must be set to 0x4B18.
0x08	8	`u64`	`off`	Absolute byte-aligned offset of the volume label string in this file.
0x10	2	`u16`	`len`	Length of the label.
0x12	14		reserved	Must be filled with 0.

Tip	UTF-8 are recommended but not required. Same for file names.

5. Inode Sources Array

Inodes may be read from different kinds of sources. These sources are stored as an array whose location can be found in an superblock attribute.

Tip	For example, directory entry may be stored in an IDTFS file itself, while inodes of regular files may be read from other underlying filesystems if they are to be delegated. Inodes from different sources may have different ways to read their file data.

Table 4. Structure of inode sources attribute (`compat:0:D4EA`)
Offset	Size	Type	Name	Description
0x00	8	`u64`	`id`	Must be set to 0xD4EA.
0x08	8	`u64`	`off`	Image-relative byte-aligned offset of the inode sources array in this file.
0x10	2	`u16`	`len`	Number of inode sources
0x12	14		reserved	Must be filled with 0.

Table 5. Structure of inode source entry
Offset	Size	Type	Name	Description
0x00	2	`u16`	`type`	Type of the inode source.
0x02	30		reserved	Reserved for source parameters.

Each inode source has an index, starting from zero. The address of an inode source structure can be calculated with offset = inode_srcs_attr.off + (32 * i) where i is the index.

Type code 0x0000-0x7FFF are reserved for official modules.

6. Root Inode Entry

Each image must have a root inode attribute which contains parameters of the root directory inode.

Table 6. Structure of inode sources attribute (`compat:0:5340`)
Offset	Size	Type	Name	Description
0x00	8	`u64`	`id`	Must be set to 0x5340.
0x08	8		reserved	Must be filled with 0.
0x10	16	directory entry record	`root_dent`	Directory entry record of the root directory. File name related fields are unused and ignored. File type code must be `DIR`.

7. Plain Inode Source

Plain source is used for inodes that are stored directly in the IDTFS file.

Table 7. Structure of plain inode source entry
Offset	Size	Type	Name	Description
0x00	2	`u16`	`type`	Must be set to 0x9AD0.
0x02	2		reserved	Must be filled with 0.
0x04	4	`u32`	`mtime_nsec`	Nanoseconds component in file modification time shared by all small inodes.
0x08	8	`u64`	`mtime`	File modification time shared by all small inodes in seconds since 00:00, Jan 1st, 1970 UTC.
0x10	16		reserved	Must be filled with 0.

Table 8. Structure of directory entry record using plain sources
Offset	Size	Type	Name	Description
0x00	2		reserved	Must be filled with 0.
0x02	8	`u64`	`nid`	Inode number.

7.1. Inode Structure

The absolute offset of an inode can be calculated using its inode number (nid) with inode_offset = nid * 32.

Each inode contains these parts:

inode header
extended attributes (xattr) info, only present if inode.flags.has_xattr is set.
xattr entries, if any
inlined data tail, if data layout requires one

There are two kinds of plain inode headers: small and extended. The small variant is smaller in size at the cost of smaller value ranges and losing per-file modification time.

Table 9. Structure of small plain inode header
Offset	Size	Type	Name	Description
0x00	2	`u16`	`flags`	Flags.
0x02	2	`u16`	`mode`	File permission mode.
0x04	4	`u32`	`data`	Data location.
0x08	8	`u64`	`size`	File size in bytes.
0x10	4	`u32`	`uid`	Owner UID.
0x14	4	`u32`	`gid`	Owner GID.
0x18	1	`u8`	`nlink`	Hard link count.
0x19	7		reserved	Must be filled with 0.

Table 10. Structure of extended plain inode header
Offset	Size	Type	Name	Description
0x00	2	`u16`	`flags`	Flags.
0x02	2	`u16`	`mode`	File permission mode.
0x04	4	`u32`	`data`	Data location.
0x08	8	`u64`	`size`	File size in bytes.
0x10	4	`u32`	`uid`	Owner UID.
0x14	4	`u32`	`gid`	Owner GID.
0x18	4	`u32`	`nlink`	Hard link count.
0x1C	4	`u32`	`mtime_nsec`	Nanoseconds component in file modification time.
0x20	8	`u64`	`mtime`	File modification time in seconds since 00:00, Jan 1st, 1970 UTC.
0x28	24		reserved	Must be filled with 0.

Table 11. Bit structure of plain inode flags
Bit	Width	Name	Description
0	2	`inode_version`	0 for small inode. 1 for extended inode. 2 and 3 are reserved.
2	4	`data_layout`	Interpretation method for the `data` in inode.
6	1	`has_xattr`	1 if the file has any extended attribute, 0 if it has no xattr.
7	9	reserved	Must be filled with 0.

Implementations must refuse unsupported or reserved values in plain inode flags.

Table 12. Values of data layout
Value	Name	Description
0	SPECIAL	For device files, the meaning of `inode.data` is platform-dependent. For IPC files (FIFO and sockets), it means that `inode.data` has no meaning.
1	FLAT	For data files, it means that file contents are stored in the image file at block offset `inode.data`. If the last block is not fully occupied by the contents, the unused region may be used for other data.
2	FLAT_INLINE	For data files, it means that file contents are stored in the image file at block offset `inode.data`. If the file size is not an integer multiple of the block size, the last `(inode.size % block_size)` bytes will not be stored in a separate block, but will be placed after the inode structure.

For empty files, inode.data is ignored and can be any value.

Data files include regular files, directories and symbolic links.

When an implementation encounters an invalid or unsupported data layout or a invalid or unsupported combination of data layout and file type, operations that need to interact with file contents must fail.

7.2. Inline Data Layout

To speed up file IO, inline data layout (FLAT_INLINE) places the last (inode.size % block_size) bytes ("tail chunk") of file contents right after the inode structure.

If the size of the tail chunk is 0, this layout behaves the same as the FLAT layout.

The tail chunk must be located in the same block as the last byte of the inode structure. Otherwise implementations may refuse IO operations.

If the file is smaller than one block (i.e. all data are within the tail chunk), inode.data is unused and can be any value.

7.3. Device Files

Character device and block device files use the SPECIAL layout only. inode.data is interpreted as platform-dependent device number and inode.size must be 0.

On Linux, the device number consists of major and minor device numbers that can be extracted as follows:

Table 13. Bit structure of device number on Linux
Bit	Width	Name	Description
0	20	`minor`	Minor device number.
20	12	`major`	Major device number.

7.4. IPC Files

Both FIFO (named pipe) and socket files are IPC files and use the SPECIAL layout only. inode.size and inode.data must be 0.

7.5. Extended Attributes

Table 14. Structure of extended attributes header
Offset	Size	Type	Name	Description
0x00	2	`u16`	`size`	Size of xattr entry region logically shifted right by 2 bits.
0x02	2		reserved	Must be filled with 0.
0x04	4		reserved	Must be filled with 0.

Table 15. Structure of xattr entry
Offset	Size	Type	Name	Description
0x00	1	`u8`	`name_prefix`	Name prefix index.
0x01	1	`u8`	`name_size`	Byte-size of name suffix.
0x02	2	`u16`	`value_size`	Byte-size of xattr value.
		`u8[]`	`name`	Bytes of xattr name suffix.
		`u8[]`	`value`	Bytes of xattr value.
			padding	Realigns the xattr entry to 4-byte-aligned.

Table 16. Values of xattr name prefix index
Value	Name	Prefix
0	NONE	No prefix.
1	USER	`user.`
2	SYS	`system.`
3	TRUSTED	`trusted.`
4	SECURITY	`security.`
5	SYS_POSIX_ACL_ACC	`system.posix_acl_access`
6	SYS_POSIX_ACL_DEF	`system.posix_acl_default`

8. Directories

The contents of a directory file consists of directory blocks, each block starts with an array of directory entry records.

Size of a directory file may be image-block-size-aligned. If not, the last file_size % block_size bytes are considered as a directory block ("tail block") whose size is not the image block size. The size of tail blocks is implementation-defined but must be greater than file_size % block_size

Tip	As the tail block size is implementation-defined, references (such as `entry.name_off`) to bytes after `file_size % block_size` are undefined behavior.

Table 17. Structure of directory entry record
Offset	Size	Type	Name	Description
0x00	2	`u16`	`name_off`	Offset of the file name within this directory block.
0x02	2	`u16`	`name_len`	Byte-size of the file name.
0x04	1	`u8`	`flags`	Entry flags and file type code.
0x05	1	`u8`	`inode_src`	Index of inode source.
0x06	10	inode parameters	`inode_parm`	Reserved for inode sources.

File name strings must be in the same directory block as the entry. The name of the first entry record in the array must be placed immediately after the last entry.

Tip	That is to say, the number of entries in a single directory block is `entries[0].name_off >> 4`.

Table 18. Bit structure of directory entry flags
Bit	Width	Name	Description
0	3	`file_type`	File type code.
3	5	reserved	Must be filled with 0.

Table 19. Values of file type code
Value	Name	Description
0	REG_FILE	Regular files.
1	DIR	Directories.
2	CHRDEV	Character devices.
3	BLKDEV	Block devices.
4	FIFO	Named pipe.
5	SOCK	Socket file.
6	SYMLINK	Symbolic link.

For all directory entries referring to the same inode, flags.file_type must be the same. If not, the behavior is implementation-defined.

9. Delegation Inode Source

Delegation source is used to delegate accesses to inodes to an backing filesystem.

Table 20. Structure of delegation inode source entry
Offset	Size	Type	Name	Description
0x00	2	`u16`	`type`	Must be set to 0x605B.
0x02	1	`u8`	`mode`	Backing filesystem lookup mode.
0x03	29		reserved	Reserved

Table 21. Values of backing filesystem lookup mode
Value	Name	Description
0	HASH	Hash path lookup, such as `/store/d2/f1e6b33fbc4ca08c1cc110236e6dba/`.
1	PATH	Custom path lookup, such as `/store/example-class/example/`.
2	EXTERNAL_OPTS	Passes all backing FS paths through mount options.

9.1. Hash mode

Table 22. Structure of delegation inode source entry using hash lookup mode.
Offset	Size	Type	Name	Description
0x00	2	`u16`	`type`	Must be set to 0x605B.
0x02	1	`u8`	`mode`	Must be set to 0.
0x03	1		reserved	Must be filled with 0.
0x04	4	`u32`	`path_blkoff`	Block-offset to the backing FS array.
0x08	2	`u16`	`fs_count`	Count of backing filesystems.
0x0A	1	`u8`	`path_len`	Byte-size of each path.
0x0B	1	`u8`	`sep_pos`	Segmentation offset.
0x0A	20		reserved	Reserved

The backing filesystem path can be computed using the following steps:

Load the fixed-length hash string at image-relative offset (path_blkoff << blksz_bits) + (path_len * i) where i is the backing FS index (0 ⇐ i < fs_count). The length of the string is path_len.
If sep_pos is non-zero, separate the path into two components and concatenate them. path = string_concat(raw_path[0..sep_pos], PATH_SEPARATOR, raw_path[sep_pos..]).

9.2. Custom Path Mode

Table 23. Structure of delegation inode source entry using custom paths lookup mode
Offset	Size	Type	Name	Description
0x00	2	`u16`	`type`	Must be set to 0x605B.
0x02	1	`u8`	`mode`	Must be set to 1.
0x03	1		reserved	Must be filled with 0.
0x04	4	`u32`	`path_blkoff`	Block-offset to the backing path data.
0x08	4	`u32`	`path_size`	Byte-size of the backing path data. Must be greater than or equal to `8 * fs_count`.
0x0C	2	`u16`	`fs_count`	Count of backing filesystems.
0x0E	16		reserved	Reserved

Table 24. Structure of delegation backing FS path slice
Offset	Size	Type	Name	Description
0x00	4	`u32`	`off`	Backing-path-data-relative offset to the path string. Must be less than or equal to `path_size`.
0x04	4	`u32`	`len`	Byte-size of the string.

The backing filesystem path can be computed using the following steps:

Load the path slice structure at image-relative offset (path_blkoff << blksz_bits) + (8 * i) where i is the backing FS index (0 ⇐ i < fs_count).
Load the path string at image-relative offset (path_blkoff << blksz_bits) + slice.off.

9.3. External Options Mode

Table 25. Structure of delegation inode source entry using external options lookup mode
Offset	Size	Type	Name	Description
0x00	2	`u16`	`type`	Must be set to 0x605B.
0x02	1	`u8`	`mode`	Must be set to 2.
0x03	1		reserved	Must be filled with 0.
0x04	2	`u16`	`fs_count`	Length of the backing FS array.
0x06	26		reserved	Reserved

9.4. Directory Entry Record

Table 26. Structure of inode parameters using delegation sources and extended backing file name
Offset	Size	Type	Name	Description
0x00	2	`u16`	`fs`	Index of backing filesystem.
0x02	2	`u16`	`backing_name_off`	Offset of the backing file name within this directory block.
0x04	2	`u16`	`backing_name_len`	Byte-size of the backing file name.
0x06	4		reserved	Must be filled with 0.

Table 27. Structure of inode parameters using delegation sources and compact backing file name
Offset	Size	Type	Name	Description
0x00	2	`u16`	`fs`	Index of backing filesystem.
0x02	2	`u16`	`backing_name_off`	Must be set to 0.
0x04	2		reserved	Must be filled with 0.
0x06	4	`u32`	`backing_file_idx`	Index of the backing file.

Backing file name strings must be in the same directory block as the entry.

For entries using compact backing file names, the backing file name is backing_file_idx encoded in lowercase ASCII hexadecimal and added "0"-s to the left to align to 8 characters.

Backing file names are relative to the root of the backing filesystem selected by fs.

10. Acknowledgements

This section is non-normative.

During the drafting of this specification, many previous projects like EROFS and SquashFS provided valuable design references. The authors gratefully acknowledge them.