DWARFS-FORMAT(5)

📦
version 0.15.8 · 2 versions
, in nixpkgs unstable

✨ NAME ✨

dwarfs-format — okay bestie, this is the whole entire DwarFS File System Format, version 2.5 💅

🦋 DESCRIPTION 🦋

So this doc is literally describing the DwarFS file system format, version 2.5. That's it, that's the vibe. Everything you're about to read is about how the bytes are arranged, no cap 🫶

🎀 TERMINOLOGY 🎀

Before we get into it — the vocabulary list. Learn these and everything else is a slay ✨

💖 High-Level Terms 💖

  • DwarFS image (or DwarFS file system image) — a file that contains a DwarFS file system. People also call it a DwarFS archive, and honestly that's a super common term too, iykyk.
  • Section — a contiguous part of a DwarFS image that holds either file system data or metadata. Every single section has a header rocking a magic, a version number, a type, a length, and hashes for integrity checking 🕵️‍♀️
  • Header — an optional, arbitrary prefix that sits before the first section of a DwarFS image. Usually it's a shell script or some other executable that intends to use the bundled DwarFS image inside it. The DwarFS binary tools use an efficient algorithm to automatically skip this header, so you don't gotta worry about it 🔥
  • Block — a section of type BLOCK that contains file data. There can be an arbitrary number of BLOCK sections in a DwarFS image, like, as many as you want 👑
  • Metadata — a section of type METADATA_V2 that contains all the metadata needed to interpret the file system. And listen — without the metadata the structure of the file system is completely lost, and all you're left with is a collection of shredded bits and pieces of file data with no association to the original files. Absolutely devoured. Do not lose the metadata 😭💀
  • Inode — an entry in the inodes list in the metadata. Each inode represents a file system object, i.e. a directory, regular file, symlink, device, socket or pipe 🧚
  • Directory Entry — an entry in the dir_entries list in the metadata. Each directory entry associates a name with an inode number. Directory entries are grouped by directory using the directories list. Also, within a single directory, the entries are sorted asciibetically by name — yes, asciibetically, that's the actual word 🍓
  • Chunk — a part of a file that references a contiguous range of bytes in a single BLOCK. Each regular file inode references a list of chunks that, when concatenated, make up the contents of the file. Literally just vibes glued together 💜
  • Shared File — a regular file that shares its contents with one or more other regular files. It's similar to hardlinks, but on a "file level" instead of an "inode level". Each shared file has its own inode, but the inodes reference the same list of chunks through the shared_files_table 🌈

🧚 Internal Terms and Types 🧚

  • file_view — an abstraction representing a single file in a file system that lets you read access its contents. The exact mechanism to access the file contents is implementation-defined, and different implementations have different trade-offs in terms of memory usage, speed and error handling. For example:
    • the default on 64-bit systems is to memory-map the entire file. While this is usually extremely fast, there are no means for gracefully handling I/O errors, and they will typically result in the process crashing with a bus error (SIGBUS). Not cute 💀
    • on 32-bit systems, the default is to only memory-map "segments" of the file at a time. This limits the amount of address space used, but uses more system calls and is thus slower 🐢
    • on either platform, it's also possible to use an implementation that reads data into allocated buffers. This is the slowest option and the one that will use the most process memory, but it is the only option that allows for graceful handling of I/O errors 🫶
  • file_extent — using a file_view, you can iterate over the "extents" of a file. Extents are contiguous ranges of either data or holes. In sparse files, holes are ranges of zeros that do not actually occupy any space in the file system. This allows the code to efficiently skip over these holes if possible ⭐
  • file_segment — a contiguous range of data within a file. You can get a file_segment either directly from a file_view (using offset and size), or by using file_extent::segments() to iterate over a range of segments given the preferred segment size and an optional overlap between segments. A file_segment is always backed by contiguous memory representing the corresponding range of data in the file 🎀
  • Fragments — contiguous ranges of categorized file data. A categorizer can split each file into a sequence of fragments, each of which will be assigned a category. For example, the pcmaudio_categorizer will typically split an audio file into a pcmaudio/metadata fragment at the start, followed by a pcmaudio/waveform fragment, optionally followed by pcmaudio/metadata if there's any trailing metadata. The fragments from each category will be processed as separate streams: that is, all pcmaudio/metadata fragments will be ordered (e.g. by similarity) and then fed into the segmenter, which will further split each fragment into "chunks" — and these are the chunks that will eventually be stored in the chunk_table in the metadata. Iconic pipeline honestly 👑
  • Chunks — the smallest entity of contiguous file data that DwarFS manages. The segmenter splits data into chunks, adding references to data it has already seen if possible. Deduplication queen behavior fr fr 🔥

(more parts coming, don't go anywhere bestie 💖)

🌸 FILE STRUCTURE 🌸

okay so bestie, a DwarFS file system image is literally just a sequence of sections, and it may be prefixed by a "header" — which is usually some kind of shell script or other executable that's planning to use the "bundled" DwarFS image. cute, right? 💅

Every single section in a DwarFS image looks like this:

            ┌───┬───┬───┬───┬───┬───┬───┬───┐
       0x00 │'D'│'W'│'A'│'R'│'F'│'S'│MAJ│MIN│  MAJ=0x02, MIN=0x05 for v2.5
            ├───┴───┴───┴───┴───┴───┴───┴───┤
       0x08 │                               │  Used for full (slow) integrity
            ├─ SHA-512/256 integrity hash  ─┤  check with `dwarfsck`.
       0x10 │  over the remainder of the    │
            ├─ section data, starting at   ─┤
       0x18 │  offset 0x28.                 │
            ├─                             ─┤
       0x20 │                               │
            ├───────────────────────────────┤
       0x28 │  XXH3-64 hash over remainder  │  Used for fast integrity check.
            ├───────────────┬───────┬───────┤
       0x30 │Section Number │SecType│CompAlg│  All integer fields are in LE
            ├───────────────┴───────┴───────┤  byte order.
       0x38 │   Length of remaining data    │
            ├───────────────────────────────┤
       0x40 │                               │
            │ Section data compressed using │
            │ CompAlg algorithm.            │
            │                               │
            │                               │
            │                               │
            └───────────────────────────────┘

✨ A couple of notes ✨

  • No padding is added between sections. zero. none. we don't do that here 💅
  • the list of sections is so easy to traverse — you just use the length field to skip straight to the start of the next section. it's giving effortless 🦋
  • corruption? caught instantly with the XXH3-64 hash. computing this hash is so fast that it's actually checked every single time a file system section is loaded. no cap, every time 🔥
  • and you can furthermore check integrity with the SHA-512/256 hash — much slower, but you should rarely ever need it 🐢
  • all header fields, except for the magic and version number, are protected by the hashes 🔒
  • worst case, corruption happens and sections can still be retrieved by scanning for the magic. the version number gets recovered by looking at all sections and choosing the majority 🗳️. the explicit section number helps recover data if multiple sections are missing — iconic recovery behaviour 👑
  • a major version number change renders the format incompatible 🚫
  • a minor version number change stays backwards compatible, i.e. an old program will refuse to read a file system with a minor version larger than the one it supports. but a new program can still read all file systems with a smaller minor version number, although very old versions may at some point no longer be supported. iykyk 🧚

🎀 Header Detection 🎀

so to actually access the file system data when it's prefixed by a header, you gotta know the header size. two options, bestie:

  • you can hand it over to the tools or the FUSE driver explicitly — using e.g. the --image-offset or -o offset options
  • or let it be determined automatically, by passing auto as the argument to those same options ✨

automatic detection works by scanning the file for the section header magic (DWARFS) and validating the match by looking up the second section header using the length of the first section — and checking its magic too. it's rather unlikely that a file gets created accidentally that would pass this check… although one could be crafted manually without any problems 🙈 (so like, don't treat it as security, mkay?)

💖 Section Types 💖

currently, these are the section types that are defined:

  • BLOCK (0) — a block of data. this is where all the file data lives. there can be an arbitrary number of sections of this type. the file data in these BLOCKs can only be interpreted using the metadata section — the metadata holds a list of chunks for each file, and each chunk references a small part of the data in a single BLOCK 🧩
  • METADATA_V2_SCHEMA (7) — the schema ../frozen/thrift/lib/thrift/frozen.thrift used to layout the METADATA_V2 section contents. it's stored in "compact" thrift encoding. the metadata cannot be read without the schema, because it defines the exact bit widths used to store each metadata field 😭
  • METADATA_V2 (8) — this section contains the bulk of the metadata. it's essentially just a collection of bit-packed arrays and structures. the exact layout of each list and structure depends on the actual data and is stored separately in METADATA_V2_SCHEMA. the metadata format is defined in metadata.thrift ../thrift/metadata.thrift, and the binary format that derives from that definition uses Frozen2 ../frozen/thrift/lib/cpp2/frozen/Frozen.h. Frozen2 isn't just extremely space efficient — it also lets you access huge data structures directly through memory-mapping. obsessed 😍
  • SECTION_INDEX (9) — the section index is, well… an index of all sections in the file system 💅. if present (you can suppress creation of the index with --no-section-index), this is required to be the last section. each entry in the section index is a 64-bit value: upper 16 bits = the section type, lower 48 bits = the offset relative to the first section. meaning the section index is independent of whether or not a header is present before the first section. the whole point of the section index is to avoid having to build an index by visiting all section headers. and since the offsets in the index are sorted, the section index is always stored uncompressed, and the section index must be the last section, you can find the start of the section index by reading the last 64-bit value from the image file, checking if the upper 16 bits match the SECTION_INDEX type, and then adding the image offset (header size) to the lower 48 bits. at that position in the file, you should find a valid section header for the section index 🔍
  • HISTORY (10) — file system history information as defined in thrift/history.thrift. stored in "compact" thrift encoding. zero or more history sections are supported. this section type is purely informational and not needed to read the DwarFS image 🦋

🔥 Compression Algorithms 🔥

DwarFS supports a wide range of section compression algorithms, some of which need additional metadata. the full list of supported algorithms is defined in dwarfs/compression.h ../include/dwarfs/compression.h 📚

for compression algorithms with metadata, the metadata is defined in thrift/compression.thrift ../thrift/compression.thrift. it's stored in "compact" thrift encoding at the beginning of the section, just after the header ✨

🌈 METADATA FORMAT 🌈

here's a high-level overview of how all the bits and pieces relate to each other 👇

here's the whole thing laid out, take a sec, it's giving ✨encyclopedia✨:

           ═════════════           ┌─────────────────────────────────────────────────────────────────────────┐
            DwarFS v2.5            │                                                                         │
           ═════════════           │         ┌───────────────────────────────────────────┐                   │
                                   │         │                                           │                   │
                     dir_entries[] ▼         │              inodes[]                     │   directories[]   │
           ╔════╗   ┌────────────────┐       │  S_IFDIR ──►┌───────────────────┐         │  ┌────────────────┴─┐
           ║root╟──►│ name_index:  0 │       │             │ mode_index:     0 ├──────┐  └─►│ parent_entry:  0 │
           ╚════╝   │ inode_num:   0 ├───────┴────────────►│ owner_index:    0 │      │     │ first_entry:   1 │
                    ├────────────────┤                     │ group_index:    0 │      │     | self_entry:    0 |
                ┌───┤ name_index:  2 │                     │ *time_offset: 417 │      │     ├──────────────────┤
           ┌────┼───┤ inode_num:   5 ├───────┐             │ *time_subsec:  13 │      │     │ parent_entry:  0 │
           │    │   ├────────────────┤       │             │ nlink_minus_1:  0 │      │     │ first_entry:  11 │
           │ ┌──┼───┤ name_index:  3 │       │             ├───────────────────┤      │     | self_entry:    1 |
           │ │  │   │ inode_num:   9 ├────┐  │             │        ...        │      │     ├──────────────────┤
           │ │  │   ├────────────────┤    │  │  S_IFLNK ──►├───────────────────┤      │     │ parent_entry:  5 │
           │ │  │   │                │    │  │             │ mode_index:     2 │      │     │ first_entry:  12 │
           │ │  │   │      ...       │    │  └────────────►│ owner_index:    2 │      │     | self_entry:    7 |
           │ │  │   │                │    │                │ group_index:    0 │      │     ├──────────────────┤
           │ │  │   └────────────────┘    │                │ *time_offset: 298 │      │     │       ...        │
           │ │  │                         │                │ *time_subsec:  88 │      │     └──────────────────┘
           │ │  │                         │                │ nlink_minus_1:  0 │      │
           │ │  │    names[]              │                ├───────────────────┤      │      modes[]
           │ │  │   ┌────────────┐        │                │        ...        │      │     ┌─────────────┐
           │ │  │   │ "lib"      │        │     S_IFREG ──►├───────────────────┤      └────►│   0040775   │
           │ │  │   ├────────────┤        │     (unique)   │ mode_index:     1 │            ├─────────────┤
           │ │  │   │ "ls"       │        ├───────────────►│ owner_index:    0 ├──────┐     │   0100644   │
           │ │  │   ├────────────┤        │                │ group_index:    0 │      │     ├─────────────┤
           │ │  └──►│ "share"    │        │                │ *time_offset: 298 │      │     │     ...     │
           │ │      ├────────────┤        │                │ *time_subsec:  94 │      │     └─────────────┘
           │ └─────►│ "usr"      │        │                │ nlink_minus_1:  2 │      │
           │        ├────────────┤        │                ├───────────────────┤      │      uids[]
           │        │ "words"    │        │                │        ...        │      │     ┌─────────────┐
           │        ├────────────┤        │     S_IFREG ──►├───────────────────┤      └────►│       0     │
           │        │    ...     │        │  ┌──(shared)   │ mode_index:     4 │            ├─────────────┤
           ▼        └────────────┘        │  │             │ owner_index:    2 │            │    1000     │
           (inode-off)                    │  │             │ group_index:    1 ├──────┐     ├─────────────┤
           │                              │  │             │ *time_offset: 298 │      │     │     ...     │
           │         symlink_table[]      │  │             │ *time_subsec:  38 │      │     └─────────────┘
           │        ┌────────────┐        │  │             │ nlink_minus_1:  0 │      │
           │        │      1     ├───┐    │  │             ├───────────────────┤      │      gids[]
           │        ├────────────┤   │    │  │             │        ...        │      │     ┌─────────────┐
           └───────►│      0     │   │    │  │  S_IFBLK ──►├───────────────────┤      │     │       0     │
                    ├────────────┤   │    │  │  S_IFCHR    │                   │      │     ├─────────────┤
                    │    ...     │   │  ┌─┼──┼─────────────┤        ...        │      └────►│     100     │
                    └────────────┘   │  │ │  │             │                   │            ├─────────────┤
                                     │  │ │  │ S_IFSOCK ──►├───────────────────┤            │     ...     │
                                     │  │ │  │  S_IFIFO    │                   │            └─────────────┘
                     symlinks[]      │  │ │  │             │        ...        │
                    ┌────────────┐   │  │ │  │             │                   │
                    │ "../foo"   │   │  │ │  │             └───────────────────┘                 chunks[]
                    ├────────────┤   │  │ │  │                                                  ┌──────────────┐
                    │ "foo/bar"  │◄──┘  │ │  │                                            ┌────►│ block:     0 │
                    ├────────────┤      │ └──┼──────────►(inode-off)                      │     │ offset: 1698 │
                    │    ...     │      │    │                │            chunk_table[]  │     │ size:   1012 │
                    └────────────┘      ▼    ▼                │           ┌─────────────┐ │     ├──────────────┤
                              (inode-off)    (inode-off)      └──────────►│      0      ├─┘ ┌──►│ block:     0 │
                                        │    │                            ├─────────────┤   │   │ offset: 1604 │
                     devices[]          │    │      shared_files_table[]  │      1      ├───┘   │ size:     94 │
                    ┌────────────┐      │    │     ┌───────────┐          ├─────────────┤       ├──────────────┤
                    │   0x0107   │      │    └────►│     0     ├───┬─────►│      2      ├───┬──►│ block:     0 │
                    ├────────────┤      │          ├───────────┤   │      ├─────────────┤   │   │ offset:    0 │
                    │   0x0502   │◄─────┘          │     0     ├───┘      │      2      ├───┘   │ size:   1517 │
                    ├────────────┤                 ├───────────┤          ├─────────────┤       ├──────────────┤
                    │    ...     │                 │    ...    │          │     ...     │       │     ...      │
                    └────────────┘                 └───────────┘          └─────────────┘       └──────────────┘

okay so the headline here is the bit-packing 💅 and honestly it ate. Fields that are unused, or that only ever hold a single (zero) value — think a group_index that's, like, always zero because every single file belongs to the same group — do not occupy any space in the metadata section. not one byte. iconic.

And because we need reproducibility — meaning you can generate bit-identical file system images when you run mkdwarfs multiple times on the same input 🫶 — the names, symlinks, modes, uids, and gids tables are always sorted in ascending order. no vibes, no shuffle, strict ascending. the order of the remaining tables is still deterministic, but it depends on the ordering algorithm used when building the file system image.

✨ Features ✨

okay storytime 📖 — up until v0.7.2, the DwarFS format's minor version got bumped pretty regularly. and like, that was a bit annoying, because it meant you couldn't upgrade mkdwarfs without also upgrading the FUSE driver — an old driver would just straight up reject new file system images 😭 gatekeeping behaviour, honestly. the v0.7.3 release made two changes to address this:

  • Any new section types would be ignored as long as the minor version number is unchanged. Which literally means new features that need new sections can get added without breaking backwards compatibility. Queen behavior honestly. 👑
  • New features — even the compatibility-breaking ones — can be added without bumping the minor version number, by dropping a feature flag into the metadata (the features set). Each release knows which features it can support, and if it bumps into a feature it doesn't recognize, it will refuse to mount the file system. Gatekeeping, but make it safety. 💅

Okay so there's one small version gap we gotta mention for completeness, because we're thorough like that. Since v0.7.3 did not increment the minor version, releases v0.7.0 to v0.7.2 will accept file system images with any features set. In practice though? They'll probably bail out anyway, because those releases don't accept unknown section types, and by default mkdwarfs has been adding HISTORY sections since v0.7.3. In hindsight we should've bumped the accepted minor version in v0.7.3, but kept the written minor version the same until actually adding a feature. v0.14.0 finally increments the accepted minor version, and v0.16.0 will increment the written minor version, so long term this gap gets closed. Growth. 🌱

🌸 Determining Inode Offsets 🌸

Bestie, before you can even start traversing the metadata, you gotta figure out the offsets for symlinks, regular files, devices, etc. inside the inodes list. The index into this list is the inode_num from dir_entries, but you can do direct lookups based on the inode number too, iykyk.

The inodes list is strictly in this order, no exceptions:

  • directory inodes (S_IFDIR)
  • symlink inodes (S_IFLNK)
  • regular unique file inodes (S_IFREG)
  • regular shared file inodes (S_IFREG)
  • character/block device inodes (S_IFCHR, S_IFBLK)
  • socket/pipe inodes (S_IFSOCK, S_IFIFO)

So the offsets can be found by running a binary search with a predicate on the inode mode. And the shared file offset? That's found by subtracting the length of shared_files_table from the total number of regular files. Math ate, fr fr. 🧮✨

🦋 Unique and Shared File Inodes 🦋

The whole difference between unique and shared file inodes is this: there's only one unique file inode that references a particular index in the chunk_table, whereas there are multiple shared file inodes referencing that same index. That's literally how DwarFS does file-level de-duplication beyond hardlinks. Slay.

Hardlinks share the same inode. Duplicate files that are not hardlinked each get their own unique inode, but they still reference the same content through the chunk_table.

The shared_files_table is the indirection that maps a shared file inode to a chunk_table index. It's giving matchmaker. 🫶

🎀 Sparse Files 🎀

DwarFS can optionally support sparse files since v0.14.0. But — heads up, bestie — images created with sparse file support will not be backwards compatible. ⚠️

Sparse file data is stored as usual. Holes get stored in the chunk_table using a "special" block index. In a file system with N blocks, the highest valid block index is N-1. Holes are stored using the block index N. This is cheaper than allocating an extra bit per chunk just to say whether it's a data chunk or a hole chunk. The block index used to encode a hole chunk is stored in the metadata as hole_block_index.

Since holes can get pretty large, their size is encoded in both the size and offset fields of the corresponding chunk_table entry. And here's the vibe: while offset field values are typically randomly distributed, the size field value distribution is usually skewed towards small values. So it makes sense to store the hole size like this:

chunk.offset = hole_size % BLOCK_SIZE
chunk.size   = hole_size / BLOCK_SIZE

With large BLOCK_SIZE values, the chunk.size field will usually occupy a few bits less than the chunk.offset field. And to prevent a single large hole from excessively widening the storage used for chunk.size, we use a separate list large_hole_size to store the sizes of holes larger than a certain threshold (derived from the block size). The index into this list gets stored in chunk.size, indicated by setting chunk.offset to BLOCK_SIZE - 1. Iconic little encoding trick, no cap. 💅

✨ Traversing the Metadata ✨

You typically start at the root directory, which lives at dir_entries[0], inodes[0] and directories[0]. Note that the root directory implicitly has no name, so dir_entries[0].name_index should not be used. 🙈

To determine what's inside a directory, we find the range of entries from directories[inode_num].first_entry to directories[inode_num + 1].first_entry. If both values are equal, the directory is empty. Otherwise, we can look up the entries in dir_entries[].

So for directory inodes, you can directly index into directories using the inode number. Easy.

For link inodes, you can index into symlink_table, but you gotta adjust the index for the link inode offset you determined before:

link_index = symlink_table[inode_num - link_inode_offset]

And with that, you can look up the contents of the symlink:

contents = symlinks[link_index]

For unique regular file inodes, you can index into chunk_table after adjusting the index:

chunk_index = inode_num - file_inode_offset

For shared regular file inodes, you can index into the (unpacked) shared_files_table:

shared_index = shared_files[inode_num - file_inode_offset - num_unique_files]

Then you can index into chunk_table, but you need to adjust the index once more:

chunk_index = shared_index + num_unique_files

The range of chunks that make up a regular file inode is chunk_table[chunk_index] to chunk_table[chunk_index + 1]. If those values are equal, the file is empty. Otherwise you need to look up the range of chunks in chunks.

Each chunk references a range of bytes in one file system BLOCK. Concatenate them and boom, you've got the file contents. 🧚

Both chunk_table and directories have a sentinel entry at the end, so you can always perform range lookups for all indices. Safety net supremacy.

Last but not least — to read the device id for a device inode, you can index into devices:

device_id = devices[inode_num - device_inode_offset]

🌈 OPTIONALLY PACKED STRUCTURES 🌈

The overview above assumes metadata with no additional packing, which you can produce with:

mkdwarfs --pack-metadata=none,plain

But that's not the default, bestie, and parts of the metadata are likely stored in a packed format. The good news? They're mostly easy to unpack. 🫶

💜 Shared Files Table Packing 💜

The shared_files_table can be stored in a packed format that only encodes the number of shared links to a chunk_table index. Since the minimum number of links is always 2 (otherwise it wouldn't be shared at all), the numbers in the packed format are additionally offset by 2. So for example, a packed table like

[0, 3, 1, 0, 1]

would unpack to:

[0, 0, 1, 1, 1, 1, 1, 2, 2, 2, 3, 3, 4, 4, 4]

The packed format is used when options.packed_shared_files_table is true. Look at that compression, it ate. 🔥

🍓 Directories Packing 🍓

The directories table, when stored in packed format, omits all parent_entry fields and uses delta compression for the first_entry fields.

So to unpack all the info, you first delta-decompress the first_entry fields, then traverse the whole directory tree once to fill in the parent_entry fields. Sounds like a lot of work, right? It's actually reasonably fast. For example, for a file system with 15 million entries in 90,000 directories, reconstructing the directories takes only about 50 milliseconds. Literally faster than you can say "bestie". ⚡

The packed format is used when options.packed_directories is true.

⭐ Chunk Table Packing ⭐

The chunk_table can also be stored delta-compressed, and must be unpacked accordingly.

The packed format is used when options.packed_chunk_table is true.

Okay this one isn't really "packing" per se, it's more of an optimization, but we're covering it here anyway because it matters.

Hardlink counts (i.e. stat.st_nlink) can always be reconstructed by traversing the dir_entries and counting how many times each inode is referenced. That's reasonably fast, but it can still cause a noticeable delay when mounting file systems with millions of entries (like, about 300ms for 10 million entries). It also uses 4 bytes per inode temporarily to store these counts.

But correct hardlink counts are necessary — otherwise the fact that two directory entries reference the same inode can be super confusing to applications. 😭

So by default, unless --no-hardlink-table is passed to mkdwarfs, the nlink_minus_one field will be populated for each inode. The inodes_have_nlink option signals whether or not this field is valid. If it's not valid, the hardlink count table gets built every single time the file system is mounted.

And why is the field called nlink_minus_one? Because inodes must have at least one link, and storing only zeroes for a field requires no space at all. So if the input to mkdwarfs has no hardlinks, there's zero metadata overhead. (And that's exactly what the inodes_have_nlink option is for: it helps you figure out whether the fields are all zero because they were never set, or because the hardlink counts are actually all one.) Big brain energy honestly. 🧠✨

Both the names and symlinks tables can be stored in a packed format, in compact_names and compact_symlinks.

There are two separate packing schemes, and they can be combined. If neither scheme is active, the difference between, say, names and compact_names is that the former is stored as a "proper" list, whereas the latter is stored as a single string plus an index of offsets. Since lists of strings store both offset and length for each element, this already saves you the storage for the length fields — those can easily be determined from the offsets at run-time. 💅

If the packed_index scheme is used in addition, the index is stored delta-compressed.

And last but not least, the individual strings can be compressed too. The fsst library (https://github.com/cwida/fsst) allows compression of short strings with random access, and is typically able to reduce the overall size of the string tables by 50%, using a dictionary that's only a few hundred bytes long. If a symtab is set for the string table, this compression is used. Note that in this case, the index refers to the position and length in the compressed string.

It's recommended to decompress the strings using the official FSST code, which is highly optimized and very fast. The rest of this section explains how to decompress the names manually, just to document all parts of the DwarFS format — so you can skip right to the next section if you're using the fsst library. No pressure bestie. 🦋

Decoding an FSST compressed string is honestly so simple, bestie — the vibes are immaculate ✨. Each byte is a code, and codes 00 to FE are an index into a string table. Each entry in that table is a string 1-8 bytes long, and those bytes get copied into the target buffer. Code FF is the escape character, meaning the following byte should be copied into the target buffer as-is. For example, if the contents of the string table were ["FS", "war", "!", "D"], the byte sequence 03 01 00 02 decodes to "DwarFS!". Slay 💅.

The string table is constructed from the symtab record like this:

  • Bytes 0 to 7 are the header and are of the form 01 ll xx xx 0A 14 34 01; bytes 2 and 3 store encoder parameters; they can be ignored. Byte 1 (ll) stores the number of codes, this information is redundant and can also be ignored, but it could be used as an additional sanity check if so desired. The rest is fixed and if any of those bytes are different, symtab should be considered to be corrupt.
  • Byte 8 should always be 00. If it's 01, it means the data was compressed as zero-terminated strings and requires slightly different decoding of symtab (described at the end of this section for completeness); DwarFS doesn't use zero-terminated strings; hence, in the following paragraphs we assume it's zero.
  • Bytes 9 to 16 are the histogram of string lengths in the string table: byte 9 is the number of 1-byte strings, byte 10 the number of 2-byte strings and so on. The sum of those values is always identical to byte 1 in the header.
  • The remaining bytes are the contents of the string table, but it starts with all the 2-byte strings concatenated, followed by all 3-byte strings, and so on until the 8-byte strings are followed by all 1-byte strings. The indices are assigned sequentially: the first entry read gets index 0, the second index 1, and so on.

For example, the string table used earlier would be stored as follows: the histogram would start with 02 01 01 with the rest being zeros, followed by the ASCII string "FSwar!D". Iconic 🎀.

This concludes the description of FSST decompression. As mentioned earlier, byte 8 in the header should always be 00, but if it were 01, there are only 2 differences that need to be noted: entry zero in the string table is fixed to the 1-byte "\0" string, and that value is not stored in the symtab. However it is still counted in the histogram; so to construct the string table, the first code assigned has to be 1, not 0 and the first entry in the histogram has to be decremented by 1.

💾 Binary Metadata Format Details 💾

The binary metadata is stored using Frozen2 ../frozen/thrift/lib/cpp2/frozen/Frozen.h. This format is, unfortunately, not really documented. Also, as of now, there is only a C++ implementation to read or write this format. Ngl, it's giving "trust me bro" energy, but we move 😭.

To interpret the binary data in the METADATA_V2 section, both the thrift definitions in metadata.thrift ../thrift/metadata.thrift and the schema ../frozen/thrift/lib/thrift/frozen.thrift from the METADATA_V2_SCHEMA section are needed.

You can inspect the schema using dwarfsck in two different ways. First, as a "raw" schema dump:

           $ dwarfsck image.dwarfs -d schema_raw_dump
           Schema {
             4: fileVersion (i32) = 1,
             1: relaxTypeChecks (bool) = true,
             2: layouts (map) = map<i16,struct>[44] {
               0 -> Layout {
                 1: size (i32) = 0,
                 2: bits (i16) = 6,
                 3: fields (map) = map<i16,struct>[0] {
                 },
                 4: typeName (string) = "",
               },
               1 -> Layout {
                 1: size (i32) = 0,
                 2: bits (i16) = 5,
                 3: fields (map) = map<i16,struct>[0] {
                 },
                 4: typeName (string) = "",
               },
               2 -> Layout {
                 1: size (i32) = 0,
                 2: bits (i16) = 12,
                 3: fields (map) = map<i16,struct>[0] {
                 },
                 4: typeName (string) = "",
               },
               3 -> Layout {
                 1: size (i32) = 0,
                 2: bits (i16) = 11,
                 3: fields (map) = map<i16,struct>[0] {
                 },
                 4: typeName (string) = "",
               },
               4 -> Layout {
                 1: size (i32) = 0,
                 2: bits (i16) = 23,
                 3: fields (map) = map<i16,struct>[2] {
                   2 -> Field {
                     1: layoutId (i16) = 2,
                     2: offset (i16) = 0,
                   },
                   3 -> Field {
                     1: layoutId (i16) = 3,
                     2: offset (i16) = -12,
                   },
                 },
                 4: typeName (string) = "",
               },
               5 -> Layout {
                 1: size (i32) = 0,
                 2: bits (i16) = 11,
                 3: fields (map) = map<i16,struct>[3] {
                   1 -> Field {
                     1: layoutId (i16) = 0,
                     2: offset (i16) = -5,
                   },
                   2 -> Field {
                     1: layoutId (i16) = 1,
                     2: offset (i16) = 0,
                   },
                   3 -> Field {
                     1: layoutId (i16) = 4,
                     2: offset (i16) = 0,
                   },
                 },
                 4: typeName (string) = "",
               },
           [...]
               43 -> Layout {
                 1: size (i32) = 36,
                 2: bits (i16) = 282,
                 3: fields (map) = map<i16,struct>[19] {
                   1 -> Field {
                     1: layoutId (i16) = 5,
                     2: offset (i16) = 0,
                   },
                   2 -> Field {
                     1: layoutId (i16) = 8,
                     2: offset (i16) = -11,
                   },
                   3 -> Field {
                     1: layoutId (i16) = 12,
                     2: offset (i16) = -23,
                   },
           [...]
                 },
                 4: typeName (string) = "",
               },
             },
             3: rootLayout (i16) = 43,
           }

To make any sense of this, you need to look at the metadata.thrift ../thrift/metadata.thrift with the explicit knowledge that the rootLayout in the schema refers to the struct metadata in the thrift IDL. With that in mind, you can now see that the struct metadata itself uses 36 bytes (or 282 bits) of storage. By definition, these bytes are located at the start of the METADATA_V2 section data. Note that these sizes are solely defined by the schema; another DwarFS image may store the struct metadata in fewer or more bits. Lowkey obsessed with how precise this is 🫶.

You can also line up the fields map in the Layout of struct metadata with the fields from the thrift IDL. While the names of the struct members can change, the numeric id never changes. So you can see that field 1 refers to the chunks member. You can also see that the layout for that field is 5, which can be looked up again in the layouts map of the schema.

The tricky bit is that layout 5 does not refer to the struct chunk in the IDL, but actually to the list<chunk>. A list (or an ArrayLayout in Frozen2) is represented using 3 fields: distance (1), count (2) and item (3). count is just the actual length of the list/array/vector. distance is the offset at which the data for the list starts. And item finally refers to the layout for the struct chunk, in this case 4.

Layout 4 contains 2 out of the 3 members of struct chunk: offset (2) and size (3). The first member, block, is missing simply because there is only one block in the DwarFS image we're looking at. Thus, no bits are used to represent the block member in struct chunk. For offset, 12 bits are allocated per item and for size, 11 bits are allocated.

Now, if we look at a hex dump of the METADATA_V2 section, we have enough context to navigate the data:

                       v offset 0
                       91 ac 55 b6  3e 2b 1a b2 c8 24 69 92  |......U.>+...$i.|
                        |  |
                        |  `-- 0b10101100
                        |     vvv     ^^^ -> 0b100100 = distance = 36
                        `-- 0b10010001
                                 ^^^^^ count = 17

           be 82 f7 0b 00 00 73 fa  c3 2e db 6e 4b 7e 17 3e  |......s....nK~.>|

                                    v offset 36
           6c 0d 77 b9 51 ef eb 02  a6 2a 00 4b 15 40 2d d0  |l.w.Q....*.K.@-.|
                                     |  |  |
                                     |  |  `- 0b00000000
                                     |  `---- 0b00101010  0b00000000010 = size = 2
                                     `------- 0b10100110  0b101010100110 = offset = 2726

           0f 53 05 80 aa 02 70 55  04 88 aa 00 3c 55 00 aa  |.S....pU....<U..|

The bits are read starting from the LSB of the first byte (i.e. little-endian). We know that the data starts with the root layout, and the root layout starts with the ArrayLayout for list<chunk>. We know that the count is represented using 5 bits starting at offset 0. Reading the actual bits, we find that there are 17 chunks stored in the metadata. Reading the 6 distance bits starting at an offset of 5 bits (negative offsets are "bits", while positive offsets are "bytes"), we find that the 17 chunks are stored starting at the 36th byte.

If we move to that location and read 12 bits for the chunk offset and 11 bits of the chunk size, we find that the first chunk is 2 bytes from offset 2726 in block 0. Fr fr, the little-endian bit math is eating and leaving no crumbs 🔥.

Another option to look at the schema is via frozen_layout:

           $ dwarfsck image.dwarfs -d frozen_layout
           36 byte (with 282 bits) ::dwarfs::thrift::metadata::metadata
             chunks @ start
               11 bit range of std::vector<dwarfs::thrift::metadata::chunk, std::allocator<dwarfs::thrift::metadata::chunk> >
                 distance @ bit 5
                   6 bit packed unsigned unsigned long
                 count @ start
                   5 bit packed unsigned unsigned long
                 item @ start
                   23 bit ::dwarfs::thrift::metadata::chunk
                     block @ start
                       empty packed unsigned unsigned int
                     offset @ start
                       12 bit packed unsigned unsigned int
                     size @ bit 12
                       11 bit packed unsigned unsigned int
             directories @ bit 11
               12 bit range of std::vector<dwarfs::thrift::metadata::directory, std::allocator<dwarfs::thrift::metadata::directory> >
                 distance @ bit 5
                   7 bit packed unsigned unsigned long
                 count @ start
                   5 bit packed unsigned unsigned long
                 item @ start
                   12 bit ::dwarfs::thrift::metadata::directory
                     parent_entry @ start
                       6 bit packed unsigned unsigned int
                     first_entry @ bit 6
                       6 bit packed unsigned unsigned int
                     self_entry @ start
                       empty packed unsigned unsigned int
           [...]

Okay so this finally clicks once you've already seen the raw schema dump up top — because this representation is literally already doing the matchmaking for you, pairing up the types from the thrift IDL with the actual layouts in the schema. Like, the vibes are pre-aligned. 💖

💌 AUTHOR

Written by Marcus Holland-Moritz. Respect the author, bestie — they built the whole thing. 👑

Copyright (C) Marcus Holland-Moritz. That's the whole line, no cap. 🎀

👀 SEE ALSO

Go read those next, they're the whole friend group 🫶

and that's the whole page, bestie!! 💅✨ You just read DWARFS-FORMAT(5), dated January 1980 — iconic date, no notes. Now go forth and read some dwarfs 🧚💜

📦 where this page comes from