zpaqfranz 65.4

Three headlines:

• l in a fraction of a second on huge archives (-filelist): the history of the archive is kept inside it, and l reads just that.
• l is faster anyway, even without -filelist: about 3 times on big listings.
• -tar: zpaqfranz as a tar on Linux, macOS, FreeBSD, OpenBSD and Solaris: owners, permissions, symlinks, hard links, FIFOs, devices, nanosecond times. Tested field by field against the original tree, and it keeps more than the tar of those systems.

Part one, what is new, for the user

1. -filelist: l in a fraction of a second
2. l is faster anyway
3. -tar: zpaqfranz as a tar (*nix)
4. -turbo N: how many threads
5. [Smaller things](#5-smaller-things)

1. -filelist: l in a fraction of a second

zpaqfranz a z:\backup.zpaq c:\data -filelist
zpaqfranz l z:\backup.zpaq

To know what an archive contains, l must read the index of every
version, from the first to the last: on an archive with thousands of
versions that takes seconds, or minutes. With -filelist, every a also
stores inside the archive the whole history of the file list (deduplicated,
so each a adds just its own part), and l reads only that.

• Ask for it once: from then on every a keeps it up to date by itself
  (-nofilelist to stop).
• It works on existing archives too, even those made by zpaq 7.15: the first
  a -filelist stores the history of all the versions already there.
• If anything does not add up (another program wrote to the archive
  afterwards, a damaged block...) l reads the archive the old way. The
  output is the same either way.
• l -nofilelist always reads the old way.

On a real archive (7.6 GB, 1,351 versions, 5.6 million records):

(Fedora, 4 cores; the old l -all needed more RAM than the machine had.)

2. l is faster anyway

Even without -filelist. How much depends on the system: on Linux, reading
the time zone for every line was the biggest cost.

The output is the same, byte for byte.

3. -tar: zpaqfranz as a tar (*nix)

zpaqfranz a /backup/srv.zpaq /srv -tar
zpaqfranz x /backup/srv.zpaq -to /restore/ -tar
zpaqfranz l /backup/srv.zpaq -tar

With -tar zpaqfranz keeps what tar keeps: owner and group (by number and
by name), permissions (setuid, setgid and sticky too), modification and
access time with nanoseconds, symbolic links (the link, not what it
points to), hard links, FIFOs, character and block devices. And
x -tar gives them back, as tar does: owners by name if that user exists
(-numeric: by number, as tar --numeric-owner).

Plus what tar does not have: deduplication, versions, a hash for every file.

On Linux, macOS, FreeBSD, OpenBSD and Solaris the copy comes back
identical, checked field by field; on the same tree, the tar of macOS and
FreeBSD loses the nanoseconds and more. What is not kept (extended
attributes, ACLs, SELinux labels, file flags) is listed in
[part two](#2--tar-what-is-not-kept-and-why).

Without -tar nothing changes: as always, only files and folders.

4. -turbo N: how many threads

zpaqfranz a z:\vm.zpaq c:\vm -turbo 8

-turbo alone uses as many threads as -t (up to 32) to cut and hash big
files; -turbo 8 uses 8. The archive is the same, byte for byte, whatever
the number.

5. Smaller things

• The ADS file list is gone (Windows): -filelist replaces it, and works
  everywhere. -ads now means "CRC-32 (-fasttxt) in the ADS";
  ads z:\*.zpaq -only zpaqlist -kill removes the old lists.
• x never writes through a link (*nix): where it has to write a file and
  finds a symlink, a FIFO or a device, that is removed first. Previously
  x -force over a FIFO waited forever, and over a symlink wrote where the
  symlink pointed.
• *Backslash in nix names: x no longer creates spurious folders for
  names like system-systemd\x2dmute.slice (systemd).
• Temporary folder (*nix): one per user (/tmp/_zpaqfranz_<uid>):
  a /tmp/_zpaqfranz made by root blocked every other user.
• -hashdeep: the temporary VFILE-l-hashdeep.txt is deleted at the end.
• -silent, -out, DLL printed %Z %K %H literally: now there is one
  formatter for all.

Part two, the details, for power users

1. -tar: what is kept, how it is given back
2. -tar: what is not kept, and why
3. -tar: the limits of each operating system
4. -tar: how it was tested
5. -filelist in practice
6. [-turbo N](https://github.com/fcorbelli/zpaqfranz/releases/new#6--turbo-n)

1. -tar: what is kept, how it is given back

What a -tar stores

A symlink is never followed, not even when it points to a folder: the
link is stored, and what it points to is stored only if it is in the tree
too. The same goes for a symlink given on the command line:
a x.zpaq /some/link -tar stores the link.

A hard link group is made of the files with the same device and inode
seen by one a: the first name (in order) is stored as a file, every other
one as "link to that name". The data are stored for every name anyway:
deduplication means they cost only a few bytes of index, and so each name
can still be extracted alone, or without -tar, or by zpaq 7.15, as a full
copy.

At the end:

02123: 42 +added, 0 -removed, 42 good metadata, 0 bad metadata.
02124: 1 socket(s) ignored, as tar does
02125$ 1 hard link(s) stored as copies (first name too long)

What x -tar does

Everything is first extracted as usual (a symlink as a small file holding
its target, a FIFO or a device as an empty file); then, once all the data
are written:

1. the files, in name order:
   • a symlink: the small file becomes the link;
   • a hard link: the copy becomes a link to the first name of its group
     (if that one was extracted, is a regular file, and is on the same
     filesystem; otherwise the copy stays, with a warning);
   • a FIFO: mkfifo(); a device: mknod() (root only);
   • then owner (root only), then mode (a chown drops setuid and setgid,
     so the order matters), then creation date, mtime and atime;
2. the folders, last, from the deepest: what is created inside no longer
   changes their dates, and a read-only folder does not stop the work (until
   then its owner can write inside, as with tar).

64404: -tar: metadata given back to 66,825 entries, 0 errors, 0 without metadata

Owners. By default by name: if the user (group) of the archive exists on
this machine, its uid (gid) here; otherwise the number in the archive. The
same default as GNU tar. With -numeric always the number: the right
choice when restoring a system from a live CD, whose /etc/passwd is not
the one of the backup.

Not as root, like tar: the files belong to whoever extracts them, devices
are not created, setuid/setgid/sticky are dropped where the kernel does not
allow them:

64405$ Not root: 35 owner(s), device(s) or setuid/setgid/sticky bit(s) not given back (as tar does)
64749$ Not root: cannot make the device /restore/dev/null

Over existing files (x -force on a folder already extracted): a
symlink, FIFO or device where a file goes is removed first, never written
through. A symlink could point anywhere (/etc/passwd), a device is a
device, a FIFO would block x forever. This holds for every x on *nix,
with or without -tar.

l -tar

2020-01-17 17:34:40    10   20% # /srv/f_0644
type:  '0' [Regular file] (65.4l+)
uid:   0 (root) gid: 0 (root)
mode:  0000644     (rw-r--r--)
mtime: 1579278880.207215789  (2020-01-17 17:34:40)
atime: 1790323007.305898641  (2026-09-25 09:56:47)
ctime: 1790323007  (2026-09-25 09:56:47)

A symlink shows link: (and "full target: the content" when it is longer
than the 215 bytes shown), a device device: major,minor, a hard link the
first name of its group. (65.4l+) marks what was written by 65.4l or later
(nanoseconds, full ids, devices).

Versions, incremental backups

A chmod, a chown, a new symlink target, a new name for a file (hard
link): each writes a new version of that entry; the data are read again only
if they changed. x -until N -tar gives back the owners, modes and links of
version N.

Use -tar always, or never, on a given archive: an a without -tar
does not see symlinks, FIFOs and devices (so they look deleted in that
version), and a file written again without -tar has no metadata in that
version.

With older versions

2. -tar: what is not kept, and why

3. -tar: the limits of each operating system

Measured on the test machines (bench/tar/oslimits.sh):

Windows: -tar does nothing (NTFS has other metadata: -windate for the
creation date). ESXi, Haiku and the NAS builds compile the -tar code, but
are not tested with it (Haiku has no device numbers).

4. -tar: how it was tested

A tree with every kind of entry: files with every mode (0000, 0444, 4755,
2755, 6750, 1644...), owners with 32-bit ids and 32-character names, ids
with no name, sticky and read-only folders (with links inside), symlinks
(relative, absolute, dangling, to a folder, 300 and 2,584 bytes long, with
spaces and accents), hard link groups (same folder, other folders, inside a
read-only folder, one with a first name of 250 bytes), FIFO, character and
block devices, a socket, a sparse file, nanosecond times.

Compared field by field with the original (bench/tar/tarcmp.py: type,
mode, owner, mtime and atime in nanoseconds, birth time, link target, device
numbers, hard link groups, content):

The last round was run on 65.4m, on Fedora and FreeBSD (after the latest
changes), plus the autotest on Fedora (everything OK) and a build on
Windows. The scripts are in bench/tar: tartest.sh and tartest2.sh
(Linux), tartest_mac.sh, tartest_bsd.sh (FreeBSD, OpenBSD, Solaris),
tarcmp.py (the comparison), oslimits.sh (the table above),
lastround.sh (all of it, on Fedora).

5. -filelist in practice

At the end of l the times show where they went:

Times (ms): find 1, blocks 99 (6, 87.028.510 bytes), join+hash 57, rebuild 4.528 | read 4.695, prepare 2.200, print 3.664, total 10.559

Existing archives. a -filelist on an archive without it (even one made
by zpaq 7.15) reads it the usual way, collects the history of every version,
and stores it; if there is nothing new to add, it writes a version with just
the history (65413).

When it is not used (and l silently reads the archive the old way):
another program (zpaq 7.15, an older zpaqfranz, a -nofilelist) wrote to the
archive after the last a -filelist; a block or the hash of the history
does not check out. The next a with a recent zpaqfranz rebuilds the
history (65405).

Not available with: -index, -chunk, the zpaq streaming methods, fake
writes.

Cost. The history of a version is the history of the previous one plus
the records of the new version, and it is deduplicated: each a stores
(after compression) about as much as its own index. On the 7.6 GB archive
above, the whole history of 1,351 versions is 141 MB before deduplication,
87 MB of it unique, before compression.

zpaq 7.15 reads and extracts these archives as always; its l -all
shows the pointer to the history as a "deleted" file named
VFILE-filelist:... in the last version.

6. -turbo N

-turbo alone: as many threads as -t (the cores), up to 32. -turbo N: N
threads for the fragmenter of add2(), whatever -t is (so -t can stay
high for the compressors). -turbo 1 is the plain loop, as with -t1. N is
taken only if it is made of digits: a x.zpaq -turbo 2024_photos adds the
folder 2024_photos. -verbose says how many threads were used (65392).

The archive is identical, byte for byte, whatever the number (checked with
1, 2, 4, 8, 16 threads, on Windows and on Linux). Windows, 32 threads, one
file of 7.6 GB, -m0 (best of two runs):

Past 8-16 threads the limit is the disk, and the single thread that stores
the fragments: more threads just cost more CPU. On a busy machine
-turbo 8 gives almost all the gain for a quarter of the threads. With a
slower method (-m1 and up) the compressors need the cores too: on a
4-core Linux machine -m1 went from 17.0 s to 16.6 s at best.

Part three, lo spiegone, for developers

1. Why l is slow on a zpaq archive
2. [Where to keep the answer: the options, and why this one](#2-where-to-keep-the-answer-the-options-and-why-this-one)
3. [The history](#3-the-history)
4. Deduplication: each a pays only for its tail
5. The pointer, and how l finds it
6. [Reading it back, and why the output is the same](#6-reading-it-back-and-why-the-output-is-the-same)
7. [The life of a history](#7-the-life-of-a-history)
8. [The 550 bytes ceiling](#8-the-550-bytes-ceiling)
9. -tar inside
10. l, where the time went

1. Why l is slow on a zpaq archive

A zpaq archive is a journal. Every a appends one transaction:

c  header: date, and the size of what follows (jmp)
d  data blocks: fragments, compressed
h  for each d block, the SHA-1 and size of its fragments
i  index: the files CHANGED in this version (name, date, attr, fragment list),
   date 0 for the deleted ones

Version N contains only what changed. So the list of the files of the
last version is not written anywhere: it is the result of replaying every
i block of every version, from the first. And the size of a file is not
in its record: it is the sum of the sizes of its fragments, which are in the
h blocks.

read_archive() does exactly that: from each c it jumps (jmp) over the
data to the h and i blocks of that version, decompresses them, and
replays them into dt (name → record). On an archive of 1,351 versions:
thousands of seeks spread over 7.6 GB, thousands of small decompressions,
5.6 million records. 15 seconds for l, and l -all (every version of every
file) needed 7.5 GB of RAM.

2. Where to keep the answer: the options, and why this one

The answer (the replayed history) is small and changes a little at every
a. Where to keep it?

Outside the archive: a file next to it, or (Windows) an alternate data
stream (the zpaqlist ADS of the previous versions). Rejected: it gets out
of date as soon as anything else writes to the archive; it is lost when the
archive is copied to another filesystem, uploaded, rsync-ed, sent to a NAS;
and ADS exist only on NTFS. A cache that can be wrong is worse than no
cache. Removed in 65.4k.

A new kind of block. The zpaq format knows c, d, h, i blocks, by
their names (jDC + date + type + number). A new type would break zpaq 7.15
and every other reader: out of the question, the archives must stay zpaq
archives.

A normal file inside the archive (like VFILE-l-filelist.txt): it would
be extracted and listed, and above all finding it needs the index, which
is exactly what l must not read.

What was done: the history goes into ordinary d blocks (any zpaq
reads them, and ignores fragments that no file uses), and a tiny pointer
goes into the last i block of the archive, as ordinary records of
deleted files (date 0), with the information in the name. l finds the
pointer by looking at the end of the file, without reading anything
else; from the pointer it knows which d blocks to decompress. Nothing new
in the format: zpaq 7.15 sees a few fragments nobody uses, and the deletion
of a file it never had.

3. The history

In memory (fl_blob) the history is "ZPFL" 1, then one chunk per version:

'V'  version  fdate  lastdate  offset  data_offset  jmp  dhsize  firstfragment
     namecount  (len name)...          only the names never seen before:
                                       the ID of a name is its order
     recordcount (ID date [na attr size ksize])...

Integers are LEB128 (fl_putv), the signed ones (jmp, size) zigzag
(fl_puts). A record is the record of the i block, with one change:
the fragment list is replaced by size (sum of the fragment sizes) and
ksize (estimated compressed size), computed exactly as read_archive()
computes them (fl_iblock, estimatedratio). The fragment lists are most
of the bytes of an index, and l does not need them (x does, and reads the
real index).

Names are stored once in the whole history: a file changed in 500 versions
has its name once and 500 records of a few bytes.

4. Deduplication: each a pays only for its tail

The history of version N is the history of N-1 plus a tail: chunks are
only appended. filelist_store() cuts the whole history into fragments with
zpaq's own content-defined algorithm (rolling hash with order-1
prediction, ZPAQFILELIST_FRAGMENT 6 = 64 KB on average), looks each
fragment up by SHA-1 in the archive (htinv), and writes only the new ones,
in d blocks of their own, compressed with -m1 (ZPAQFILELIST_METHOD):

• the cuts depend on the content, so the old part of the history gives the
  same fragments as last time: already in the archive, not stored;
• only the last fragment or two (where the old part ends and the new tail
  begins) and the tail are new.

So every a pays about the size of its own index, not the size of the whole
history. The history blocks are never mixed with file data: l decompresses
only them.

The offsets are logical (multipart archives: offset + position), the
fragment numbers are the global ones of the archive.

5. The pointer, and how l finds it

After the data and the history blocks, filelist_pointer() writes the very
last block of the transaction: an i block whose records are

date 0, name "VFILE-filelist:000000:<piece>"
date 0, name "VFILE-filelist:000001:<piece>"
...

The pieces (60,000 bytes each, numbered, so they can be joined in order)
make up the payload:

ZPFL1|versions|size|xxhash64|jmp|dhsize|offset:firstfragment,...|fragment-fragment,...

• versions, size, xxhash64: how many versions, how long the history is,
  its hash;
• jmp, dhsize: those of the current version. They cannot be inside
  the history, because the history is written inside the same transaction,
  before its end (and the jmp of a c block is known only when the
  transaction is closed);
• the list of the d blocks that hold fragments of the history (logical
  offset : first fragment), and the fragments, in order, as ranges.

Finding it (fl_findpointer): every zpaq block starts with the same
13-byte locator tag. l reads the last 64 KB of the file and looks for the
tag backwards; then 1 MB, then 16 MB if needed. The first block found from
the end must be a good i block made only of pointer records
(fl_parsepointer: name, comment, SHA-1, every record with date 0 and
VFILE-filelist:). If the last block is anything else (a normal index:
zpaq 7.15, an older zpaqfranz or -nofilelist wrote after it), the history
cannot be trusted and is not used: it describes the archive as it was,
not as it is. This is what makes the whole thing safe: there is no way to use
a stale history, because a newer version always ends with something else.

A "stop" pointer (VFILE-filelist:stop, from a -nofilelist) says: the
history ends here, do not turn it on again.

6. Reading it back, and why the output is the same

fl_readarchive():

1. finds and parses the pointer;
2. decompresses the listed d blocks in parallel (one thread per block
   group, each with its own file handle: fl_doblocks), keeping only the
   fragments of the history;
3. joins the fragments in the order of the ranges, checks the length, the
   xxhash64 and the magic ZPFL 1;
4. rebuilds dt and ver exactly as read_archive(..., 1) would:
   the same keys (with -all: version|$1name, and the version/ entries),
   the same DT fields, the same totals (dcsize, dhsize, usize of the
   versions), -until handled by stopping at that version, the selection
   (-only, -not, -range) applied the same way;
5. anything odd, anywhere (a record that does not parse, a version count that
   does not add up): everything is reset, 65403, and l reads the archive
   the old way.

Why rebuild dt instead of printing straight from the history? Because all
of l (filters, -orderby, -comment, -home, -n, -checksum, -tar,
the sizes of the folders, the totals) works on dt. One path after the
reading means the same output by construction; and it was checked, byte
by byte, on 15 combinations of switches, -key, multipart, -m0, -m5,
-m7, -turbo, archives made by zpaq 7.15 and continued, -tar archives.
The price is RAM (a DT is 440 bytes): see below.

Without -all only the last record of each name matters: the records
are scanned, and only the position of the last one of each name is kept;
the DT are built at the end, once, in name order (an insertion at the end
of the map, with a hint, instead of a search).

7. The life of a history

• Collecting: a reads the archive with read_archive() anyway (to
  deduplicate). With -filelist, or if the archive has a pointer at the end,
  hooks inside read_archive() (fl_beginversion, fl_hblock, fl_iblock)
  build the history while the index is replayed: no extra reading.
• An archive with a pointer, but not at the end (someone else wrote
  after it): the pointer is seen during the reading (fl_seen) but it is too
  late to collect: the archive is read a second time, collecting (65405).
• Keeping on: an archive with a history turns -filelist on by itself
  (65406), so the history never gets stale by mistake.
• Stopping: -nofilelist writes a stop pointer (65412).
• An existing archive, nothing to add: a -filelist writes a version
  with just the history (65413), otherwise it would never be there.
• Not available with -index (the index is elsewhere), -chunk
  (fixed-size pieces), streaming methods, fake writes (65407).

8. The 550 bytes ceiling

After the attributes of a file zpaqfranz writes its own "franz_block"
(hash, CRC-32, dates...). The biggest kind, the "V3 with posix" of -tar, is
FRANZOFFSETV3 = 550 bytes, and every zpaqfranz up to 65.4k reads a
franz_block into a buffer of exactly 550 bytes, copying it without a check
(an assert that does not exist in release builds).

So no franz_block can ever be longer than 550 bytes: an archive written
with a longer one would overflow the buffer of any older zpaqfranz reading
it. Everything new must fit in those 550 bytes, and with -tar they are
full. This is the root of every "no room" in the limits of -tar.

65.4l also found that the 550 bytes of a -tar block were read with a zero
after them, one byte past the buffer (read_archive, unz), and that
-filelist refused those blocks (so it was never used on -tar archives):
both fixed (the buffer is one byte longer, 550 is accepted).

How to go beyond, some day: a per-version file, like the history of
-filelist: a VFILE-tar with one record for every entry that needs more
(long hard link names, extended attributes, ACLs, SELinux labels,
capabilities, file flags, sparse maps). Stored as ordinary data, so with no
limit of size or kind, and older versions just see one more file. That is
how tar itself grew: the PAX extended headers, when the 512 bytes of the
ustar header were full.

9. -tar inside

The block

[0]       '4' = V3 with posix         [1]  hash type ('A' + FRANZO_*)
[2]       hash, as text (hashlen)     then 2 zeros
[+0]      CRC-32, as text (8)         then 2 zeros        (offsetcrc)
[+10]     ordered stream (4)          [+14] version (4)
[+18]     creation date (8)           [+26] access date (8)
[+34]     24 bytes: franz_tarext (zeros until 65.4k)
[+58]     struct franz_posix (360 bytes)
          ... up to 550 bytes in total

struct franz_posix, unchanged since it was introduced, so every version
reads it:

franz_tarext, the 24 bytes (little endian, 4 bytes each): mtime
nanoseconds, atime nanoseconds, device major, device minor, uid, gid. Older
versions wrote zeros there and never read them: the new content does not
affect them.

Why the target of a symlink is its content

linkname has 215 bytes; Linux allows 4,095. Storing the target as the data
of the entry costs nothing in the format (it is a small file), is
deduplicated like anything else, has no length limit, and makes an archive
that zpaq 7.15, or a zpaqfranz without -tar, can still extract, as small
files holding the target instead of nothing. add() and add2() never
open a special entry (a FIFO would block fopen() forever, a symlink would
give what it points to): the data come from readlink() (tar_content).

Hard links

scandir() records, for every regular file with more than one link, its
(device, inode) in g_tarinodes. tar_linkmasters(), before the index is
written, keeps for each group the names actually added in this a, sorts
them, and makes the first one the "master": the other names get
LNKTYPE with linkname = the master as it is named in the archive
(after -to / renaming), so x -to can find it through the same renaming.

A chown alone

The zpaq attr has the mode (so a chmod was always a change) but not the
owner. scandir() keeps the owner of each entry in the DT (taruid,
targid); tar_ownerchanged() compares it with the posix structure of the
same file in the archive, in the same three places where the attr is
compared: an owner change follows the very same path as an attribute change
(the data are not read again, the hash is carried over).

The order of the restore

tar_restore() works after every byte is written, for three reasons: a
symlink created earlier could be followed by a later write (the classic tar
attack: a link a -> /etc, then a file a/passwd); a hard link needs its
first name complete; a folder made read-only or dated would be changed by
what comes later. Files in name order, then folders from the deepest;
chown before chmod; the creation date before mtime (FreeBSD sets it
through a temporary older mtime).

10. l, where the time went

Profiled with perf on Linux, on 468,000 files:

• the date of every line: glibc's localtime() checks /etc/localtime
  (a stat()) at every call: 468,003 system calls. Now the offset from
  UTC is taken once per hour (fastutctolocal) and kept only if it is the
  same at both ends of that hour (the offset changes at most once in an
  hour), otherwise the slow way. Checked against the slow way on 33 million
  random dates in 11 time zones (DST, half hours, Lord Howe's half-hour DST,
  Chatham): no difference. Print time: 1,384 → 275 ms;
• the franz_block of every file was 550 bytes, zeroed (page faults);
  with -filelist it is only as big as needed (80, 192, 550), and without
  -tar a -tar block keeps just its 192-byte header;
• four passes over the map of 1 to 11 million entries (cache misses:
  about a second each at 11 million) became one;
• every piece of a line went through myprintf() (format parsing,
  prefix decoding): now it goes straight into the output buffer (list_out,
  same bytes), flushed every 1 MB when redirected.

What is left is RAM for l -all: one DT (440 bytes, built for a and x)
per record. A lean structure just for l is the next step.