Reference-level disk format documentations?

[oxalica]

Hi, developers. Thanks for all of your works. I'm using dwarfs for archival use, and it turns out to be super space efficient and easy to access with FUSE.

I'm interested in the detail design about the on-disk dwarfs image format and want to write my own reader/decompressor. I think having more alternative reader implementations is also good for the community of a file-format. How hard would it be?

IIUC, the file format is open sourced in MIT license and should be publicly usable. The only documentation I found is doc/dwarfs-format.md which contains basic block definitions and high-level structures. But it does not define all fine details and I have a few questions:

• Where is each CompAlgo value? I found a list in this script but it's not explicitly documented elsewhere. Is that authentic and up-to-date?

  There is also a compression.thrift, how is it related to the CompAlgo in the block header? Is there nested compression?

• What is "File system history information" HISTORY? The thrift seems to indicate it's mainly about the metadata of program creating this image. So it can be simply ignored by reader, right?

• What's the data of METADATA_V2 blocks?
  The thrift struct metadata said "This is the root structure for all file system metadata." so I think it means there is a globally unique "metadata" struct. It's also said "METADATA_V2 (8): This section contains the bulk of the metadata" indicating there the struct is somehow sharded into multiple pieces? How can I parse the full metadata struct from a image?

• What's METADATA_V2_SCHEMA and what's its block data format?
  "This is stored in "compact" thrift encoding." The thrift encoding of which struct? I cannot found anything related to "schema" in metadata.thrift file.

• From inspecting mkdwarfs output, there is exactly one METADATA_V2 and one METADATA_V2_SCHEMA at (almost) the end of image before HISTORY and SECTION_INDEX. Is this true for all images?

[mhx]

Hi and thanks for your feedback!

I've already tried to update dwarfs-format.md based on some of your questions.

I think having more alternative reader implementations is also good for the community of a file-format.

I agree that this would be desirable.

How hard would it be?

That depends on how much of the code you want to re-implement.

The most complex part is very likely going to be reading the metadata. This uses Frozen2, which is a very space-efficient, memory-mappable representation of Thrift data structures. The exact layout of the representation is defined by the "schema", which you've already come across.

You can actually inspect the schema using dwarfsck:

$ dwarfsck image.dwarfs -d frozen_analysis,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
[...]

You can also get a full dump of the metadata:

$ dwarfsck image.dwarfs -d metadata_full_dump
created by: libdwarfs v0.6.2
metadata {
  1: chunks (list) = list<struct>[17] {
    [0] = chunk {
      1: block (i32) = 0,
      2: offset (i32) = 2726,
      3: size (i32) = 2,
    },
    [1] = chunk {
      1: block (i32) = 0,
      2: offset (i32) = 2710,
      3: size (i32) = 2,
    },
    [2] = chunk {
      1: block (i32) = 0,
      2: offset (i32) = 181,
      3: size (i32) = 1012,
    },
[...]

Having a Frozen2-compatible reader/writer for these data structures that is independent from fbthrift would certainly be desirable, but this is definitely not for the faint of heart.

Once you can read the metadata, parts of it may require further unpacking. DwarFS gives you the choice to optimize the stored metadata for size or for "memory-mappability". In the former case, parts of the metadata need to be unpacked, in the latter case, it is directly usable.

As also mentioned in dwarfs-format.md, file names and symlinks can be stored using FSST, which preserves memory-mappability and random-access, but requires an addition step to decode each individual name/link.

The only documentation I found is doc/dwarfs-format.md which contains basic block definitions and high-level structures. But it does not define all fine details

Definitely let me know if there's something missing in dwarfs-format.md. I'm trying to keep this as up-to-date as possible, but I sometimes miss things.

Where is each CompAlgo value? I found a list in this script but it's not explicitly documented elsewhere. Is that authentic and up-to-date?

That hasn't been touched in a while and it's not up-to-date. I've added some details to dwarfs-format.md, the definition of the compression types can be found here.

There is also a compression.thrift, how is it related to the CompAlgo in the block header? Is there nested compression?

I've also described this in dwarfs-format.md now. This is additional metadata for the FLAC and RICEPP compression types that is stored just after the section header.

What is "File system history information" HISTORY? The thrift seems to indicate it's mainly about the metadata of program creating this image. So it can be simply ignored by reader, right?

Yes, HISTORY sections can be completely ignored. (Also pointed out in dwarfs-format.md now.)

What's the data of METADATA_V2 blocks? The thrift struct metadata said "This is the root structure for all file system metadata." so I think it means there is a globally unique "metadata" struct. It's also said "METADATA_V2 (8): This section contains the bulk of the metadata" indicating there the struct is somehow sharded into multiple pieces? How can I parse the full metadata struct from a image?

See above. METADATA_V2 stores the metadata thrift struct in Frozen2 format. The easiest way to parse this is using the code from fbthrift. Otherwise you'll have to dig into the details of how the Frozen2 format is serialized.

What's METADATA_V2_SCHEMA and what's its block data format? "This is stored in "compact" thrift encoding." The thrift encoding of which struct? I cannot found anything related to "schema" in metadata.thrift file.

This is also linked in dwarfs-format.md now. This is the definition of the schema.

From inspecting mkdwarfs output, there is exactly one METADATA_V2 and one METADATA_V2_SCHEMA at (almost) the end of image before HISTORY and SECTION_INDEX. Is this true for all images?

This is currently true. However, the only requirement is that the SECTION_INDEX is the last section in an image. Future versions may have multiple METADATA_V2_SCHEMA and METADATA_V2 sections (this is for the incremental update use case I have in mind).

Let me know if you need more information.

[oxalica]

I finally made my metadata parser work!

I wrote my own mini fbthrift parser just enough to parse schema in ~300LoC Rust with 0 dependency (smaller than I thought!), because 1. the format is incompatible with Apache Thrift parser, and 2. fbthrift's (Rust) binding does nothing high-level and using it is as complex as writing my own one.

At the end of the day, Frozen2 isn't rocket science. But it's a pretty amazing library, and I haven't seen anything else like it yet. I've been using it a lot in the past (I know the person who conceived it) and it really has been a game changer in a few projects.

The update dwarfs-format.md really helps for understanding Frozen2. This format is quite self-contained and has nothing to do with Thrift encoding at all. It just "borrows" the Thrift DSL for defining structures. By comparing output of dwarfsck -d metadata_full_dump and some reverse engineering, I'm finally able to parse the whole metadata struct. 🎉
Some additional notes worth mentioning:

1. optional T is stored as a struct { 1: bool is_some, 2: T inner }
2. string is stored as a struct { 1: u64 distance, 2: u64 byte_length }, similar to list but without the thrid field.
3. map<K, V> is stored as a sorted list<pair<K, V>> where struct pair<K, V> { 1: K key, 2: V value }.
4. set<T> is stored as a sorted list<T>.
5. distance in collection types (list, map) are unsigned byte offset from the beginning of current layout base, which is the sum of all distances in ancestor collection types. Eg. in struct A { list<struct B { b: string }> a }, the string data is located at byte offset 0 + distance_of_outer_list + distance_of_inner_string regardless the in-struct bit-offset of field a, b, or the element index inside the list.

I'll open source my parser later when it's more polished.

[mhx]

I finally made my metadata parser work!

Yay!

I wrote my own mini fbthrift parser just enough to parse schema in ~300LoC Rust with 0 dependency (smaller than I thought!), because 1. the format is incompatible with Apache Thrift parser, and 2. fbthrift's (Rust) binding does nothing high-level and using it is as complex as writing my own one.

At the end of the day, Frozen2 isn't rocket science. But it's a pretty amazing library, and I haven't seen anything else like it yet. I've been using it a lot in the past (I know the person who conceived it) and it really has been a game changer in a few projects.

The update dwarfs-format.md really helps for understanding Frozen2. This format is quite self-contained and has nothing to do with Thrift encoding at all. It just "borrows" the Thrift DSL for defining structures.

Indeed, it doesn't rely on anything from "legacy" Thrift.

By comparing output of dwarfsck -d metadata_full_dump and some reverse engineering, I'm finally able to parse the whole metadata struct. 🎉 Some additional notes worth mentioning:

1. optional T is stored as a struct { 1: bool is_some, 2: T inner }
2. string is stored as a struct { 1: u64 distance, 2: u64 byte_length }, similar to list but without the thrid field.
3. map<K, V> is stored as a sorted list<pair<K, V>> where struct pair<K, V> { 1: K key, 2: V value }.
4. set<T> is stored as a sorted list<T>.

Frozen2 actually supports both sorted map/set representations with binary-search lookups as well as hash table representations that offer faster lookups at the expense of using more space. But since all sets/maps used in the DwarFS metadata are small and rarely used, there's no need to use hash tables.

5. distance in collection types (list, map) are unsigned byte offset from the beginning of current layout base, which is the sum of all distances in ancestor collection types. Eg. in struct A { list<struct B { b: string }> a }, the string data is located at byte offset 0 + distance_of_outer_list + distance_of_inner_string regardless the in-struct bit-offset of field a, b, or the element index inside the list.

I'll open source my parser later when it's more polished.

Nice!

[mhx]

FWIW, the v0.12.4 release includes the new dwarfsck features.

[oxalica]

I'll open source my parser later when it's more polished.

As an update, here's my DwarFS reader library in Rust: https://github.com/oxalica/dwarfs-rs
It's also available on crates.io named dwarfs.

I tested it with several GiB of my .dwarfs archives produced by mkdwarfs, it works quite well and a tree dump gives identical result from dwarfsextract. It's hard to say about performance because it's only a framework library not a binary, and does not come with built-in multi-threaded support. But it should be easy to do multi-theaded or implement FUSE on the top of it, if someone finds it interesting XD

Thanks again for your help. ❤️

[mhx]

That's pretty cool!

I think it's really helpful to have an implementation that is as simple as possible and doesn't rely on any third party code.

Thanks for being the first person (that I know of) to do a deep-dive into the DwarFS format!