Skip to content

Latest commit

 

History

History
839 lines (683 loc) · 40.5 KB

mkdwarfs.md

File metadata and controls

839 lines (683 loc) · 40.5 KB
Raw

mkdwarfs(1) -- create highly compressed read-only file systems

SYNOPSIS

mkdwarfs -i path -o file|- [options...]
mkdwarfs --input-list=file|- -o file|- [options...]
mkdwarfs -i file -o file|- --recompress [options...]

DESCRIPTION

mkdwarfs allows you to create highly compressed, read-only file systems in the DwarFS format. DwarFS is similar to file systems like SquashFS, cramfs or CromFS, but it has some distinct features. For more detail, see dwarfs(1).

In its simplest usage form, you can create a file system containing the full contents of /path/dir with:

mkdwarfs -i /path/dir -o image.dwarfs

After that, you can mount it using dwarfs(1):

dwarfs image.dwarfs /path/to/mountpoint

OPTIONS

There are two mandatory options for specifying the input and output:

  • -i, --input=path|file: Path to the root directory containing the files from which you want to build a file system. If the --recompress option is given, this argument is the source filesystem.

  • --input-list=file|-: Read list of file paths to add to the file system from this file or from stdin. The path names will be interpreted relative to the path given with --input. If --input is omitted, the path names will be interpreted relative to the current directory. If you want files to be stored in the exact same order as read from this list (because, for example, you have already sorted them by similarity or access frequency), you must also pass --order=none. This option implicitly enables both --with-devices and --with-specials.

  • -o, --output=file|-: File name of the output filesystem or - to write the filesystem to stdout.

  • -f, --force: Force the output file to be overwritten if it already exists.

Most other options are concerned with compression tuning:

  • -l, --compress-level=value: Compression level to use for the filesystem. If you are unsure, please stick to the default level of 7. This is intended to provide some sensible defaults and will depend on which compression libraries were available at build time. The default level has been chosen to provide you with the best possible compression while still keeping the file system very fast to access. Levels 8 and 9 will switch to LZMA compression (when available), which will likely reduce the file system image size, but will make it about an order of magnitude slower to access, so reserve these levels for cases where you only need to access the data infrequently. This -l option is meant to be the "easy" interface to configure mkdwarfs, and it will actually pick defaults for seven distinct options: --block-size-bits, --compression, --schema-compression, --metadata-compression, --window-size, --window-step and --order. See the output of mkdwarfs --help for a table listing the exact defaults used for each compression level.

  • --categorize[=categorizer[,...]]: Enable one or more categorizers in the given order. See CATEGORIZERS for more details.

  • -S, --block-size-bits=value: The block size used for the compressed filesystem. The actual block size is two to the power of this value. Larger block sizes will offer better overall compression ratios, but will be slower and consume more memory when actually using the filesystem, as blocks will have to be fully or at least partially decompressed into memory. Values between 20 and 26, i.e. between 1MiB and 64MiB, usually work quite well.

  • -N, --num-workers=value: Number of worker threads used for building the filesystem. This defaults to the number of processors available on your system. Use this option if you want to limit the resources used by mkdwarfs or to optimize build speed. This option affects only the compression phase. During the compression phase, the worker threads are used to compress the individual filesystem blocks in the background. Ordering, segmenting and block building are single-threaded and run independently.

  • --compress-niceness=value: Set the niceness of compression worker threads. Defaults to 5. This ensures the ordering and segmenting threads are prioritised over compression as they provide the data to the compression workers. On Windows, the values are mapped as follows: 0 (zero) is mapped to "normal" priority, 1 to 5 are mapped to "below normal" priority, 6 to 10 are mapped to "lowest" priority and values greater than 10 are mapped to "background" priority.

  • --num-scanner-workers=value: Number of worker threads used for scanning the filesystem. Use this option if you want to limit the resources used by mkdwarfs or to optimize build speed. This option affects only the scanning phase. By default, the same value is used as for --num-workers. In the scanning phase, the worker threads are used to scan files in the background as they are discovered. File scanning includes checksumming for de-duplication as well as (optionally) checksumming for similarity computation, depending on the --order option. File discovery itself is single-threaded and runs independently from the scanning threads.

  • --num-segmenter-workers=value: Number of worker threads used for segmenting the input data. By default, the same value is used as for --num-workers. Segmenting the input data is one of the most time consuming tasks when building a file system, and cannot easily be parallelized. However, when using the categorizer, a separate segmenter will be used for each category (and subcategory, if present). This option controls how many segmenters can run simultaneously. When --compress-niceness is set to the default, segmenter threads will always have a higher priority than compression threads, making sure that compression doesn't slow down segmentation. This option also controls the number of threads used for ordering the input to the segmenter.

  • -B, --max-lookback-blocks=[*category*::]value: Specify how many of the most recent blocks to scan for duplicate segments. By default, only the current block will be scanned. The larger this number, the more duplicate segments will likely be found, which may further improve compression. Impact on compression speed is minimal, but this could cause resulting filesystem to be slightly less efficient to use, as single small files can now potentially span multiple filesystem blocks. Passing -B0 will completely disable duplicate segment search.

  • -W, --window-size=[*category*::]value: Window size of cyclic hash used for segmenting. This is an exponent to a base of two. Cyclic hashes are used by mkdwarfs for finding identical segments across multiple files. This is done on top of duplicate file detection. If a reasonable amount of duplicate segments is found, this means less blocks will be used in the filesystem and potentially less memory will be used when accessing the filesystem. It doesn't necessarily mean that the filesystem will be much smaller, as this removes redundancy that cannot be exploited by the block compression any longer. But it shouldn't make the resulting filesystem any bigger. This option is used along with --window-step to determine how extensive this segment search will be. The smaller the window sizes, the more segments will obviously be found. However, this also means files will become more fragmented and thus the filesystem can be slower to use and metadata size will grow. Passing -W0 will completely disable duplicate segment search.

  • -w, --window-step=[*category*::]value: This option specifies how often cyclic hash values are stored for lookup. It is specified relative to the window size, as a base-2 exponent that divides the window size. As a concrete example, if --window-size=16 and --window-step=1, then a cyclic hash across 65536 bytes will be stored at every 32768 bytes of input data. If --window-step=2, then a hash value will be stored at every 16384 bytes. This means that not every possible 65536-byte duplicate segment will be detected, but it is guaranteed that all duplicate segments of (window_size + window_step) bytes or more will be detected (unless they span across block boundaries, of course). If you use a larger value for this option, the increments become smaller, and mkdwarfs will be slightly slower and use more memory.

  • --bloom-filter-size=[category::]value: The segmenting algorithm uses a bloom filter to determine quickly if there is no match at a given position. This will filter out more than 90% of bad matches quickly with the default bloom filter size. The default is pretty much where the sweet spot lies. If you have copious amounts of RAM and CPU power, feel free to increase this by one or two and you might be able to see some improvement. If your system is tight on memory, then decreasing this will potentially save a few MiBs.

  • -L, --memory-limit=value: Approximately how much memory you want mkdwarfs to use during filesystem creation. Note that currently this will only affect the block manager component, i.e. the number of filesystem blocks that are in flight but haven't been compressed and written to the output file yet. So the memory used by mkdwarfs can certainly be larger than this limit, but it's a good option when building large filesystems with expensive compression algorithms. Also note that most memory is likely used by the compression algorithms, so if you're short on memory it might be worth tweaking the compression options.

  • -C, --compression=[category::]algorithm[:algopt[=value][:...]]: The compression algorithm and configuration used for file system data. The value for this option is a colon-separated list. The first item is the compression algorithm, the remaining item are its options. Options can be either boolean or have a value. For details on which algorithms and options are available, see the output of mkdwarfs --help. zstd will give you the best compression while still keeping decompression very fast. lzma will compress even better, but decompression will be around ten times slower.

  • --schema-compression=algorithm[:algopt[=value][,...]]: The compression algorithm and configuration used for the metadata schema. Takes the same arguments as --compression above. The schema is very small, in the hundreds of bytes, so this is only relevant for extremely small file systems. The default (zstd) has shown to provide considerably better results than any other algorithms.

  • --metadata-compression=algorithm[:algopt[=value][,...]]: The compression algorithm and configuration used for the metadata. Takes the same arguments as --compression above. The metadata has been optimized for very little redundancy and leaving it uncompressed, the default for all levels below 7, has the benefit that it can be mapped to memory and used directly. This improves mount time for large file systems compared to e.g. an lzma compressed metadata block. If you don't care about mount time, you can safely choose lzma compression here, as the data will only have to be decompressed once when mounting the image.

  • --history-compression=algorithm[:algopt[=value][,...]]: The compression algorithm and configuration used for the file system history. Takes the same arguments as --compression above. Like the schema, history blocks are typically very small, so the default is the same as for schema compression. This is irrelevant if --no-history is present.

  • --recompress[=all|=block|=metadata|=none]: Take an existing DwarFS file system and recompress it using different compression algorithms. If no argument or all is given, all sections in the file system image will be recompressed. Note that only the compression algorithms, i.e. the --compression, --schema-compression and --metadata-compression options, have an impact on how the new file system is written. Other options, e.g. --block-size-bits or --order, have no impact. If none is given as an argument, none of the sections will be recompressed, but the file system is still rewritten in the latest file system format. This is an easy way of upgrading an old file system image to a new format. If block or metadata is given, only the block sections (i.e. the actual file data) or the metadata sections are recompressed. This can be useful if you want to switch from compressed metadata to uncompressed metadata without having to rebuild or recompress all the other data.

  • --recompress-categories=[!]category[,...]: When --recompress is set to all or block, this option controls which categories of blocks will be recompressed. Adding a ! in front of the list allows you to specify which categories will not be recompressed.

  • -P, --pack-metadata=auto|none|[all|chunk_table|directories|shared_files|names|names_index|symlinks|symlinks_index|force|plain[,...]]: Which metadata information to store in packed format. This is primarily useful when storing metadata uncompressed, as it allows for smaller metadata block size without having to turn on compression. Keep in mind, though, that most of the packed data must be unpacked into memory when reading the file system. If you want a purely memory-mappable metadata block, leave this at the default (auto), which will turn on names and symlinks packing if these actually help save data. Tweaking these options is mostly interesting when dealing with file systems that contain hundreds of thousands of files. See Metadata Packing for more details.

  • --set-owner=uid: Set the owner for all entities in the file system. This can reduce the size of the file system. If the input only has a single owner already, setting this won't make any difference.

  • --set-group=gid: Set the group for all entities in the file system. This can reduce the size of the file system. If the input only has a single group already, setting this won't make any difference.

  • --set-time=now|iso-8601-string|unix-timestamp: Set the time stamps for all entities to this value. This can significantly reduce the size of the file system. You can pass the string now for the current time, an ISO 8601 string, or a unix timestamp (seconds since epoch). The ISO 8601 string supports a space character instead of the T between date and time and supports dashes as separators. Seconds or the full time part may be omitted as long as this doesn't turn the whole string into a single number (i.e. 2008-03-17 is supported, but 20080317 is not).

  • --keep-all-times: As of release 0.3.0, by default, mkdwarfs will only save the contents of the mtime field in order to save metadata space. If you want to save atime and ctime as well, use this option.

  • --time-resolution=sec|sec|min|hour|day: Specify the resolution with which time stamps are stored. By default, time stamps are stored with second resolution. You can specify "odd" resolutions as well, e.g. something like 15 second resolution is entirely possible. Moving from second to minute resolution, for example, will save roughly 6 bits per file system entry in the metadata block.

  • --chmod=mode[,mode]...|norm: Recursively changes the mode bits of all entries in the generated file system. Accepts the same mode specifications as the chmod utility and additionally supports the D and F modifiers to limit a specification to directories or non-directories. As a special case, you can pass --chmod=norm to "normalize" the permissions across the file system; this is equivalent to using --chmod=ug-st,=Xr.

  • --order=[category::]none|path|revpath|similarity|nilsimsa[:opt[=value][:...]]: The order in which inodes will be written to the file system. Choosing none, the inodes will be stored in the order in which they are discovered. With path, they will be sorted asciibetically by path name of the first file representing this inode. With revpath, they will also be ordered by path name, but the path is being traversed from the leaf to the root, i.e. files with the same name will be sorted next to each other. With similarity, they will be ordered using a simple, yet fast and efficient, similarity hash function. nilsimsa ordering uses a more sophisticated similarity function that is typically better than similarity, but can be significantly slower to determine a good ordering. However, the new implementation of this algorithm can be parallelized and will perform much better on huge numbers of files. nilsimsa ordering can be tweaked by specifying max-children and max-cluster-size. In general, larger values for max-cluster-size tend to result in better compression, but will slow down the algorithm quadratically. There is no point in setting max-cluster-size larger than the number of files in the input. Unlike the old implementation, nilsimsa ordering is now completely deterministic. See Nilsimsa Ordering for a detailed description of the algorithm.

  • --max-similarity-size=value: Don't perform similarity ordering for fragments (or files if they are not split into fragments by a categorizer) larger than this size. This helps speed up scanning, especially on slow file systems. For large fragments, the gains from similarity ordering are relatively small. When this option is set to a non-zero value, fragments larger than the limit will be stored first, ordered by size in descending order.

  • -F, --filter=rule: Add a filter rule. This option can be specified multiple times. See FILTER RULES for more details.

  • --debug-filter[=all|=excluded|=excluded-files|=files|=included|=included-files]: Show the effect of the filter rules without creating a file system. If no argument is passed to the option, all included/excluded files and directories are shown (same as with all). files will omit all directories. included and excluded will only show the corresponding set of files/directories. included-files and excluded-files work as before, but again omit all directories.

  • --remove-empty-dirs: Removes all empty directories from the output file system, recursively. This is particularly useful when using scripts that filter out a lot of file system entries.

  • --with-devices: Include character and block devices in the output file system. These are not included by default, and due to security measures in FUSE, they will never work in the mounted file system. However, they can still be copied out of the mounted file system, for example using rsync.

  • --with-specials: Include named fifos and sockets in the output file system. These are not included by default.

  • --header=file: Read header from file and place it before the output filesystem image. Can be used with --recompress to add or replace a header.

  • --remove-header: Remove header from a filesystem image. Only useful with --recompress.

  • --no-section-index: Don't add section index to file system. The section index is usually tiny and is used to speed up mount times for large file systems, as it avoids a full scan through the file system blocks to figure out their location.

  • --no-history: Don't add any history information to a file system.

  • --no-history-timestamps: Don't add timestamps to history entries. This is necessary, along with --no-create-timestamp, when trying to produce bit-identical file system images.

  • --no-history-command-line: Don't record command line arguments in history entries.

  • --no-create-timestamp: Don't add a creation timestamp. This is useful when bit-identical file system images are required to be produced from the same input.

  • --file-hash=none|name: Select the hashing function to be used for file deduplication. If none is chosen, file deduplication is disabled. By default, the built-in XXH3-128 hash is used. This is not a secure hash function, but it is significantly faster. The full list of supported hash function depends on the version of OpenSSL that the binary is linked against and is shown in the output of mkdwarfs -h.

  • --log-level=name: Specify a logging level.

  • --log-with-context: Enable logging context regardless of level. By default, context is enabled if the level is verbose, debug or trace.

  • --no-progress: Don't show progress output while building filesystem.

  • --progress=none|simple|ascii|unicode: Choosing none is equivalent to specifying --no-progress. simple will print a single line of progress information whenever the progress has significantly changed, but at most once every 2 seconds. This is also the default when the output is not a tty. unicode is the default behaviour, which shows a nice progress bar and lots of additional information. If your terminal cannot deal with unicode characters, you can switch to ascii, which is like unicode, but looks less fancy.

  • --incompressible-min-input-size=value: The minimum size of a file to be checked for incompressibility when the incompressible categorizer is active.

  • --incompressible-block-size=value: The block size used to test data for compressibility. This will also be the size of the fragments when --incompressible-fragments is used.

  • --incompressible-fragments: Categorize individual fragments of a file as incompressible instead of only the file as a whole.

  • --incompressible-ratio=value: The ratio above which a file or fragment is categorized as incompressible.

  • --incompressible-zstd-level=value: The ZSTD compression level used for incompressible categorization.

  • -h, --help: Show usage and the most common basic options.

  • -H, --long-help: Show full usage with all options, including defaults, compression level detail and supported compression algorithms.

  • --man: If the project was built with support for built-in manual pages, this option will show the manual page. If supported by the terminal and a suitable pager (e.g. less) is found, the manual page is displayed in the pager.

EXIT CODES

Upon successful completion, mkdwarfs will exit with exit code 0. If an unrecoverable error occurs (i.e. no valid file system image has been produced), it will exit with exit code 1. If any errors have occurred (e.g. not all input files could be read), the exit code will be 2.

CATEGORIZERS

Categorizers will inspect the input files in the scanning phase and try to assign them a category. Each categorizer can define a set of categories, and each of these categories can optionally support subcategories.

Running mkdwarfs with the -H or --long-help option will display the list of available categorizers and the categories they emit. At the moment, mkdwarfs supports two categorizers, incompressible and pcmaudio. The incompressible categorizer comes with its own set of options while the pcmaudio categorizer doesn't need any further configuration.

Categorizers are only useful if at least some of the mkdwarfs configuration is category-dependent. The options that can be configured per category are --compression, --order, --max-lookback-blocks, --window-size, --window-step, and --bloom-filter-size.

The resulting configuration matrix can be quite overwhelming, which is why mkdwarfs will run with a reasonable set of defaults if you specify the --categorize option with no arguments. These defaults are also dependent on the chosen compression level.

Note that in case of the pcmaudio categorizer, you can override each option per category (in this case pcmaudio/waveform and pcmaudio/metadata).

It's also worth noting that the order in which the categorizers are given is important. The first categorizer that will successfully categorize a file wins and, if possible, no other categorizers will run on the same file.

"incompressible" Categorizer

The incompressible categorizer will try to compress each input with a very fast compression algorithm (zstd using a negative compression level by default). If it turns out that this doesn't reduce the size of the input significantly, the input will be categorized as incompressible.

You can use the incompressible categorizer in two modes: whole-file or fragmented categorization. In the former, the whole input file will be categorized, whereas in the latter, each file can be further broken down into compressible and incompressible fragments. The size of these fragments will be equal to the block size used for categorization.

It makes sense to use this categorizer as the last in a list of multiple categorizers. Not only because it'll likely have the biggest overhead, but also because it can wrongly classify data as incompressible that can be compressed properly with a specialized algorithm (e.g. audio data).

"pcmaudio" Categorizer

The pcmaudio categorizer can identify and categorize a wide range of uncompressed audio data such as .wav, .aiff and more obscure formats.

It produces two different categories: pcmaudio/waveform for the actual waveform data, and pcmaudio/metadata for all other data in the file such as the file header. The pcmaudio/waveform category is again divided into many subcategories depending on the type of waveform data (e.g. number of channels, bit depth, byte order, etc.).

In order to efficiently compress pcmaudio/waveform data, a suitable compression algorithm must be selected for this category. mkdwarfs currently supports flac compression, which offers the best ratio of compression speed and achievable compression ratio.

It is worth noting that options such as --window-size will operate on sample granularity instead of byte granularity when processing pcmaudio/waveform data, where sample granularity means one sample for each channel. For example, a 16-bit stereo file would have a granularity of 4 bytes and thus --window-size=10 would refer to a 4 KiB window instead of a 1 KiB windows.

TIPS & TRICKS

Compression Ratio vs Decompression Speed

If high compression ratio is your primary goal, definitely go for lzma compression. However, I've found that it's only about 10% better than zstd at the highest level. The big advantage of zstd over lzma is that its decompression speed is about an order of magnitude faster. So if you're extensively using the compressed file system, you'll probably find that it's much faster with zstd.

Block, Schema and Metadata Compression

DwarFS filesystems consist of three distinct parts of data: A potentially large number of blocks, which store actual file data and are decompressed on demand, as well as one schema and one metadata section. The schema is tiny, typically less than 1000 bytes, and holds the details for how to interpret the metadata. The schema needs to be read into memory once and is subsequently never accessed again. The metadata itself is compressed by default, but it doesn't have to be. Actually, if you drop the compression level from 7 (the default) to 6, the only difference is that the metadata is left uncompressed. This can be useful if mounting speed of the file system is important, as the uncompressed metadata part of the file can then simply be mapped into memory.

Metadata Packing

The filesystem metadata is stored in Frozen, a library that allows serialization of structures defined in Thrift IDL into an extremely compact representation that can be used in-place without the need for deserialization. It is very well suited for persistent, memory-mappable data. With Frozen, you essentially only "pay for what you use": if fields are defined in the IDL, but they always hold the same value (or are not used at all), not a single bit will be allocated for this field even if you have a list of millions of items.

Frozen metadata has relatively low redundancy and doesn't compress well, but you can still save around 30-50% by enabling compression. However, this means that upon reading the filesystem, you will first have to fully decompress the metadata block and keep it in memory. An uncompressed block could simply be mapped into memory and would be instantly usable. So, if e.g. mounting speed is a concern, it would make sense to disable metadata compression, in particular for large filesystems.

However, there are several options to choose from that allow you to further reduce metadata size without having to compress the metadata. These options are controlled by the --pack-metadata option.

  • auto: This is the default. It will enable both names and symlinks.

  • none: Don't enable any packing. However, string tables (i.e. names and symlinks) will still be stored in "compact" rather than "plain" format. In order to force storage in plain format, use plain.

  • all: Enable all packing options. This does not force packing of string tables (i.e. names and symlinks) if the packing would actually increase the size, which can happen if the string tables are actually small. In order to force string table packing, use all,force.

  • chunk_table: Delta-compress chunk tables. This can reduce the size of the chunk tables for large file systems and help compression, however, it will likely require a lot of memory when unpacking the tables again. Only use this if you know what you're doing.

  • directories: Pack directories table by storing first entry pointers delta- compressed and completely removing parent directory pointers. The parent directory pointers can be rebuilt by tree traversal when the filesystem is loaded. If you have a large number of directories, this can reduce the metadata size, however, it will likely require a lot of memory when unpacking the tables again. Only use this if you know what you're doing.

  • shared_files: Pack shared files table. This is only useful if the filesystem contains lots of non-hardlinked duplicates. It gets more efficient the more copies of a file are in the filesystem.

  • names,symlinks: Compress the names and symlink targets using the fsst compression scheme. This compresses each individual entry separately using a small, custom symbol table, and it's surprisingly efficient. It is not uncommon for names to make up for 50-70% of the metadata, and fsst compression typically reduces the size by a factor of two. The entries can be decompressed individually, so no extra memory is used when accessing the filesystem (except for the symbol table, which is only a few hundred bytes). This is enabled by default. For small filesystems, it's possible that the compressed strings plus symbol table are actually larger than the uncompressed strings. If this is the case, the strings will be stored uncompressed, unless force is also specified.

  • names_index,symlinks_index: Delta-compress the names and symlink targets indices. The same caveats apply as for chunk_table.

  • force: Forces the compression of the names and symlinks tables, even if that would make them use more memory than the uncompressed tables. This is really only useful for testing and development.

  • plain: Store string tables in "plain" format. The plain format uses Frozen thrift arrays and was used in earlier metadata versions. It is useful for debugging, but wastes up to one byte per string.

To give you an idea of the metadata size using different packing options, here's the size of the metadata block for the Ubuntu 20.04.2.0 Desktop ISO image. There are just over 200,000 files in this image. The ZSTD and LZMA columns show to what fraction it is possible to reduce the metadata size by additional compression. That fraction is relative to the corresponding packing option.

---------|---------------|-----------|---------|---------
 Packing | Metadata Size | Relative  | ZSTD    | LZMA
---------|---------------|-----------|---------|---------
 auto    |     5,301,177 |   100.00% |  57.33% |  49.29%
 all     |     4,952,859 |    93.43% |  50.46% |  46.45%
 none    |     6,337,294 |   119.55% |  47.70% |  41.37%
 plain   |     6,430,275 |   121.30% |  48.36% |  41.37%
---------|---------------|-----------|---------|---------

So, the default (auto) is roughly 20% smaller than not using any packing (none or plain). Enabling all packing options doesn't reduce the size much more. However, it does help if you want to further compress the block. So, if you're really desperately trying to reduce the image size, enabling all packing would be an option at the cost of using a lot more memory when using the filesystem.

Producing bit-identical images

By default, images produced by mkdwarfs will not be identical over multiple runs. This is due to time stamps that are being added to the file system image.

In order to produce bit-identical images, you need to pass --no-create-timestamp and either --no-history-timestamps or --no-history.

FILTER RULES

The filter rules have been inspired by the rsync utility. These look very similar, though there are differences. These rules are quite powerful, yet they're somewhat hard to get used to.

There are only 3 different kinds of rules:

  • + pattern: An "include" rule.

  • - pattern: An "exclude" rule.

  • . file: A merge file rule. Rules are read (recursively) from the specified file.

Ultimately, only include and exclude rules remain in the rule set as file rules are merged in at the place where they occur.

The most important rule to remember when building a rule set is that all rules are applied strictly in order and processing stops at the first matching rule. If no rules match, the default is to include the entry.

Patterns can be anchored or floating. Anchored patterns are patterns that start with a /. These patterns match relative to the file system root (i.e. the --input path). Floating patterns match in any directory in the hierarchy.

Patterns ending with a / only match directories. All other patterns only match non-directories.

Note that regardless of the preferred native directory separator, filter rules will always use UNIX-style directory separators (/).

Patterns support ? and * wildcards matching a single character and any number of characters, respectively. These patterns don't match across directory separators (/).

Patterns also support the ** wildcard, which matches across directory separators.

Patterns also support character classes.

Here's an exemplary rule set:

+ File/Spec/[EM]*.pm
- unicore/**.pl
+ *.pl
- *

This set of rules will include all files matching File/Spec/[EM]*.pm anywhere in the hierarchy. It will also include all *.pl files, except for those anywhere below a unicore directory. The last rule excludes all other files.

This will likely leave a lot of empty directories around, but these can be removed using --remove-empty-dirs.

You can use the --debug-filter option to show the sets of included and excluded files without building an actual file system.

INTERNAL OPERATION

Internally, mkdwarfs runs in two completely separate phases. The first phase is scanning the input data, the second phase is building the file system. Both phases try to do as little work as possible, and try to run as much of the remaining work as possible in parallel, while still making sure that the file system images produced are reproducible (see the --order option documentation for details on reproducible images).

Scanning

The scanning process is driven by the main thread which traverses the input directory recursively and builds an internal representation of the directory structure. Traversal is breadth-first and single-threaded. Filter rules as specified by --filter are handled immediately during traversal.

When a regular file is discovered, its hardlink count is checked and if greater than one, its inode is looked up in a hardlink cache. Another lookup is performed to see if this is the first file/inode of a particular size. If it's the first file, we just keep track of the file. If it's not the first file, we add a job to a pool of --num-scanner-workers worker threads to compute a hash (which hash function is used is determined by the the --file-hash option) of the file. We also add a hash-computing job for the first file we found with this size earlier. These hashes will then be used for de-duplicating files. If --order is set to one of the similarity order modes, for each unique file, a further job is added to the pool to compute a similarity hash. This happens immediately for each inode of a unique size, but it is guaranteed that duplicates don't trigger another similarity hash scan (the implementation for this is actually a bit tricky).

Once all file contents have been scanned by the worker threads, all unique files will be assigned an internal inode number.

This behaviour can be customized. When using --file-hash=none, de-duplication is completely disabled. Using --max-similarity-size, it is possible to prevent computation of similarity hashes for huge files. These huge files will then be stored separately before all other files in the image.

Building

Building the filesystem image uses a --num-workers separate threads.

If nilsimsa ordering is selected, the ordering algorithm runs in its own thread and continuously emits file inodes. These will be picked up by the segmenter thread, which scans the inode contents using a cyclic hash and determines overlapping segments between previously written data and new incoming data. The segmenter will look at up to --max-lookback-blocks previous filesystem blocks to find overlaps.

Once the segmenter has produced enough data to fill a filesystem block, the block is added to a queue where from which the blocks will be picked up by a pool of --num-workers worker threads whose only job is to compress the block using the --compression algorithm.

Blocks that have been compressed will be added to the next queue, in the original order, and will be picked up by the filesystem writer thread that will ultimately produce the final filesystem image.

When all data has been segmented, the filesystem metadata is being finalized and frozen into a compact representation. If metadata compression is enabled, the metadata is sent to the worker thread pool for compression.

When using different ordering schemes, the file inodes will be either sorted upfront, or just sent to the segmenter in the order in which they were discovered.

Nilsimsa Ordering

The actual ordering step for nilsimsa ordering uses a recursive divide-and-conquer approach in order for the algorithm to be both parallelizable and deterministic. In the following description, a "node" is typically equivalent to a "unique file", although that's not a requirement for the algorithm.

  1. Nodes are clustered by distance to centroids into up to max-children clusters. With max-children set to 1, all nodes end up in the same cluster. If max-children is larger than 1, a new cluster is created as soon as all existing clusters are further away than a "maximum distance" that gets smaller as recursion depth increases.

  2. After the nodes have been clustered, each cluster that is larger than max-cluster-size is recursively clustered again with a smaller "maximum distance" as per (1). These recursive clustering steps can potentially run in parallel.

  3. As soon as a cluster is smaller than max-cluster-size, its nodes will be ordered by performing a nearest neighbour search. Note that this only happens for leaf clusters in the tree. The ordering of each leaf cluster can also run parallel with clustering / ordering of other clusters.

  4. Once all clustering / ordering is done, the nodes are "collected" from the clusters in the tree. There is currently no similarity ordering between individual clusters, but this is something that can be explored further in the future.

By setting max-children to 1 and max-cluster-size to a really large number, only a single cluster will be created and the nearest neighbour search will be performed on the set of all nodes. Since the algorithm is O(n^2), this does not scale well for max-cluster-size beyond a few 100,000. Also, since the algorithm does not minimize the global distance between all nodes, there's no guarantee that the result will be better if you use only a single cluster.

AUTHOR

Written by Marcus Holland-Moritz.

COPYRIGHT

Copyright (C) Marcus Holland-Moritz.

SEE ALSO

dwarfs(1), dwarfsextract(1), dwarfsck(1), dwarfs-format(5)