packaging: Bump up version to 1.8.6

Signed-off-by: Dongwoo Lee <dwoo08.lee@samsung.com>

packaging: Enable some compression features

To use more compression alogrithm, add some options.
And libdeflate-devel is required to use libdeflate/libzstd at building
time.

Change-Id: Ie593374af4c216eee7ea42ec24e4d17aaf716a07
Signed-off-by: Jaehoon Chung <jh80.chung@samsung.com>

packaging: Add erofs-utils spec file

Add erofs-utils spec file to use the utils for Tizen.
This patch is packing only executable files.

Change-Id: I39e7572e849c16bae1f86a79064ee003c842b557
Signed-off-by: Jaehoon Chung <jh80.chung@samsung.com>

erofs-utils: release 1.8.6

Signed-off-by: Gao Xiang <xiang@kernel.org>

erofs-utils: lib: fix `fragmentoff` larger than 4GiB

The `EROFS_INODE_COMPRESSED_FULL` datalayout should be used forcibly.

Fixes: cf04b8b78f09 ("erofs-utils: mkfs: implement extent-based deduplication")
Signed-off-by: Gao Xiang <hsiangkao@linux.alibaba.com>
Link: https://lore.kernel.org/r/20250406034841.3931822-1-hsiangkao@linux.alibaba.com

erofs-utils: lib: fix two integer handling issues

Coverity-id: 548918
Coverity-id: 548919
Signed-off-by: Gao Xiang <hsiangkao@linux.alibaba.com>
Link: https://lore.kernel.org/r/20250405185707.3202298-4-hsiangkao@linux.alibaba.com

erofs-utils: lib: fix an API usage error

Coverity-id: 548920
Signed-off-by: Gao Xiang <hsiangkao@linux.alibaba.com>
Link: https://lore.kernel.org/r/20250405185707.3202298-3-hsiangkao@linux.alibaba.com

erofs-utils: lib: drop unused `ret` assignment

Coverity-id: 548921
Signed-off-by: Gao Xiang <hsiangkao@linux.alibaba.com>
Link: https://lore.kernel.org/r/20250405185707.3202298-2-hsiangkao@linux.alibaba.com

erofs-utils: lib: only apply `fix_dedupedfrag` to the last segment

Only the segment containing the fragment needs to be fixed.

Fixes: b8cc6a36b560 ("erofs-utils: mkfs: implement multi-threaded fragments")
Signed-off-by: Gao Xiang <hsiangkao@linux.alibaba.com>
Link: https://lore.kernel.org/r/20250405185707.3202298-1-hsiangkao@linux.alibaba.com

erofs-utils: lib: fix inappropriate initialization in cache.c

This patch fixes the inappropriate initialization of `dsunit` and
`bktmap` in cache.c.

Fixes: 8bb6de4e7c41 ("erofs-utils: mkfs: support data alignment")
Fixes: ca0f040f98b6 ("erofs-utils: lib: use bitmaps to accelerate bucket selection")
Signed-off-by: Hongzhen Luo <hongzhen@linux.alibaba.com>
Link: https://lore.kernel.org/r/20250303054253.1154648-1-hongzhen@linux.alibaba.com
Signed-off-by: Gao Xiang <hsiangkao@linux.alibaba.com>

erofs-utils: lib: use bitmaps to accelerate bucket selection

Instead of looping over bucket lists directly, maintain bitmaps
for more efficient greedy selection.

ILSVRC2012_img_train.tar (1,281,168 inodes) [1]
  uncompressed EROFS (vanilla):       147,059,949,568B  36m29.529s
  uncompressed EROFS (patched):       147,059,511,296B  1m14.920s

ILSVRC2012_img_val.tar (50,001 inodes)  6,744,924,160B [2]
  uncompressed EROFS (vanilla):         6,713,278,464B  29.998s
  uncompressed EROFS (patched):         6,713,188,352B  23.753s

[1] https://image-net.org/data/ILSVRC/2012/ILSVRC2012_img_train.tar
    $ mkdir train; tar -xOf ILSVRC2012_img_train.tar | tar -xi -C train

[2] https://image-net.org/data/ILSVRC/2012/ILSVRC2012_img_vol.tar
    $ mkfs.erofs --tar=f --sort none foo.erofs ILSVRC2012_img_vol.tar

Signed-off-by: Gao Xiang <hsiangkao@linux.alibaba.com>
Link: https://lore.kernel.org/r/20250103090338.740593-5-hsiangkao@linux.alibaba.com

erofs-utils: lib: optimize space allocation

Previously, only mapped buffers were kept in the form of bucket lists
for each type and for each possible used bytes in the last block.

Apply this to unmapped buffers as well for faster greedy selection.

Signed-off-by: Gao Xiang <hsiangkao@linux.alibaba.com>
Link: https://lore.kernel.org/r/20250103090338.740593-4-hsiangkao@linux.alibaba.com

erofs-utils: lib: rename `mapped_buckets` to `watermeter`

In order to prepare for the upcoming space allocation speedup.

Signed-off-by: Gao Xiang <hsiangkao@linux.alibaba.com>
Link: https://lore.kernel.org/r/20250103090338.740593-3-hsiangkao@linux.alibaba.com

erofs-utils: lib: use round_up() to avoid division

A hotspot identified by profiling.

Signed-off-by: Gao Xiang <hsiangkao@linux.alibaba.com>
Link: https://lore.kernel.org/r/20250103090338.740593-1-hsiangkao@linux.alibaba.com

erofs-utils: mkfs: support data alignment

The underlay block storage could work in a stripe-like manner to improve
performance and space efficiency.

EROFS on-disk layout is flexible enough for such use cases.

Cc: Changpeng Liu <changpeliu@tencent.com>
Signed-off-by: Gao Xiang <hsiangkao@linux.alibaba.com>
Link: https://lore.kernel.org/r/20241219064331.2223001-4-hsiangkao@linux.alibaba.com

erofs-utils: lib: support buffer block reservation

In order to support data alignment, add support for recording multiple
block reservations.

Signed-off-by: Gao Xiang <hsiangkao@linux.alibaba.com>
Link: https://lore.kernel.org/r/20241219064331.2223001-3-hsiangkao@linux.alibaba.com

erofs-utils: lib: move block boundary check into __erofs_battach()

It should be guaranteed when buffers are attached, rather than
scattered everywhere.

Signed-off-by: Gao Xiang <hsiangkao@linux.alibaba.com>
Link: https://lore.kernel.org/r/20241219064331.2223001-2-hsiangkao@linux.alibaba.com

erofs-utils: lib: cache: get rid of required_ext

It's never used and doesn't have clear meanings.

Signed-off-by: Gao Xiang <hsiangkao@linux.alibaba.com>
Link: https://lore.kernel.org/r/20241219064331.2223001-1-hsiangkao@linux.alibaba.com

erofs-utils: lib: fix btype for the data tails of directories

It should be DIRA instead of DATA for directories.

Signed-off-by: Gao Xiang <hsiangkao@linux.alibaba.com>
Link: https://lore.kernel.org/r/20241225070454.750271-1-hsiangkao@linux.alibaba.com

erofs-utils: stress: add support for dumping inconsistent data

... dump inconsistent data for further analysis during stress tests.

Signed-off-by: Gao Xiang <hsiangkao@linux.alibaba.com>
Link: https://lore.kernel.org/r/20250316084533.1446186-1-hsiangkao@linux.alibaba.com

erofs-utils: lib: use atomic operations for `vi->flags`

Since `vi->flags` can be accessed by multiple threads.

Signed-off-by: Gao Xiang <hsiangkao@linux.alibaba.com>
Link: https://lore.kernel.org/r/20250405133937.2665477-2-hsiangkao@linux.alibaba.com

erofs-utils: allocate `struct erofs_inode` with zeroed memory

The kernel implementation has the same constraint, so the code can
be shared.

Fixes: 9fd2a2250fa9 ("erofs-utils: fuse: switch to FUSE 2/3 lowlevel APIs")
Fixes: f44043561491 ("erofs-utils: introduce fsck.erofs")
Signed-off-by: Gao Xiang <hsiangkao@linux.alibaba.com>
Link: https://lore.kernel.org/r/20250405133937.2665477-1-hsiangkao@linux.alibaba.com

erofs-utils: mkfs: implement extent-based deduplication

Currently, only rolling-hash deduplication could be used for
compressed data, and it is still single-threaded for now.

Before applying multi-threaded compression to that, let's allow
extent-based compressed data deduplication if `-Efragments` is on.

This feature will only work if multi-threaded compression is active.

Signed-off-by: Gao Xiang <hsiangkao@linux.alibaba.com>
Link: https://lore.kernel.org/r/20250403081403.2671077-3-hsiangkao@linux.alibaba.com

erofs-utils: lib: move buffer allocation into z_erofs_write_indexes()

Just used to prepare for extent-based metadata.  No logic changes.

Signed-off-by: Gao Xiang <hsiangkao@linux.alibaba.com>
Link: https://lore.kernel.org/r/20250403081403.2671077-2-hsiangkao@linux.alibaba.com

erofs-utils: lib: use compressed offsets in `struct z_erofs_inmem_extent`

... to prepare for the new on-disk encoded extents.

Signed-off-by: Gao Xiang <hsiangkao@linux.alibaba.com>
Link: https://lore.kernel.org/r/20250403081403.2671077-1-hsiangkao@linux.alibaba.com

erofs-utils: mkfs: implement multi-threaded fragments

Currently, only `-Eall-fragments` is allowed for multi-threaded
compression.  However, in many cases, we don't want the entire file
merged into the packed inode, as it may impact runtime performance.

Let's implement multi-threaded compression for `-Efragments` now,
although it's still not very fast and need to optimize performance
even further for this option.

Note that the image sizes could be larger without `-Ededupe` compared
to `-Eall-fragments` since the head parts aren't deduplicated for now.

Signed-off-by: Gao Xiang <hsiangkao@linux.alibaba.com>
Link: https://lore.kernel.org/r/20250323043451.2907228-1-hsiangkao@linux.alibaba.com

erofs-utils: fix heap-buffer-overflow in fragment cache

Allocated sizes are slightly smaller because the bitmap is `unsigned
long *` instead of `unsigned char *`.

Fixes: f511cfbbc0da ("erofs-utils: introduce fragment cache")
Fixes: b763022c1c98 ("erofs-utils: lib: fix insufficient fragment cache bitmap")
Signed-off-by: Gao Xiang <hsiangkao@linux.alibaba.com>
Link: https://lore.kernel.org/r/20250321092600.3703493-1-hsiangkao@linux.alibaba.com

erofs-utils: lib: fix insufficient fragment cache bitmap

.. should round up to the nearest byte instead of down.

Fixes: f511cfbbc0da ("erofs-utils: introduce fragment cache")
Signed-off-by: Gao Xiang <hsiangkao@linux.alibaba.com>
Link: https://lore.kernel.org/r/20250308173523.3696606-1-hsiangkao@linux.alibaba.com

erofs-utils: lib: error out if fragment_off is crafted

Found in some fuzzed images.

Fixes: f511cfbbc0da ("erofs-utils: introduce fragment cache")
Signed-off-by: Gao Xiang <hsiangkao@linux.alibaba.com>
Link: https://lore.kernel.org/r/20250307123718.1535556-1-hsiangkao@linux.alibaba.com

erofs-utils: cleanup redundant logic in erofs_iflush()

No logic changes.

Signed-off-by: Gao Xiang <hsiangkao@linux.alibaba.com>
Link: https://lore.kernel.org/r/20250305173930.2223550-2-hsiangkao@linux.alibaba.com

erofs-utils: lib: simplify erofs_read_inode_from_disk()

Source kernel commit: 914fa861e3d7803c9bbafc229652c2a69edb8b60

Signed-off-by: Gao Xiang <hsiangkao@linux.alibaba.com>
Link: https://lore.kernel.org/r/20250305173930.2223550-1-hsiangkao@linux.alibaba.com

erofs-utils: tar: handle empty filenames correctly

Tar entries with empty filenames are unusual but shouldn't
cause a crash.  Handle this by following `tar` behavior:
substitute `.` for the empty filenames.

Reproducible image (base64-encoded gzipped blob):
H4sICL2XwGcAA3Rlc3RfcmVhZF9mb3JtYXRfdGFyX2VtcHR5X2ZpbGVuYW1lLnRhcgBjY
KA9MDAwMDc3VQDShuamBiAaBGA0hGNoaGBgZGJsaAZUaADiGDIomNLBbQylxSWJRUCnlG
Tm4lVXnpGamoNHHtVTClR14ygYBaNgFNAAAAAE6urMAAYAAA==

Fixes: 95d315fd7958 ("erofs-utils: introduce tarerofs")
Signed-off-by: Gao Xiang <hsiangkao@linux.alibaba.com>
Link: https://lore.kernel.org/r/20250228045426.81099-1-hsiangkao@linux.alibaba.com

erofs-utils: contrib: add stress test

Just import it as an in-tree component for tests.

Signed-off-by: Gao Xiang <xiang@kernel.org>
Link: https://lore.kernel.org/r/20250206035722.716849-1-hsiangkao@linux.alibaba.com

erofs-utils: fsck: fix stack-overflow due to directory loops

Just record all parent directories to address this issue as
a trivial solution for now.

Closes: https://github.com/erofs/erofs-utils/issues/15
Signed-off-by: Gao Xiang <hsiangkao@linux.alibaba.com>
Link: https://lore.kernel.org/r/20250227025639.2160988-1-hsiangkao@linux.alibaba.com

erofs-utils: lib: fix an API usage error

  CID 541574:  API usage errors  (PRINTF_ARGS)
  Argument "rc" to format specifier "%d" was expected to have type "int" but has type "long".

Coverity-id: 541574
Signed-off-by: Gao Xiang <hsiangkao@linux.alibaba.com>
Link: https://lore.kernel.org/r/20250217024929.66658-2-hsiangkao@linux.alibaba.com

erofs-utils: fix potential buffer overrun in __erofs_io_write()

.. due to short write, but it's almost impossible for most fses.

Coverity-id: 541575
Signed-off-by: Gao Xiang <hsiangkao@linux.alibaba.com>
Link: https://lore.kernel.org/r/20250217024929.66658-1-hsiangkao@linux.alibaba.com

erofs-utils: lib: shorten EROFS_FRAGMENT_INMEM_SZ_MAX

EROFS_CONFIG_COMPR_MAX_SZ (currently 4MiB) is too large and could
cause OOM kills on small setups.

Signed-off-by: Gao Xiang <hsiangkao@linux.alibaba.com>
Link: https://lore.kernel.org/r/20250214062407.3281416-3-hsiangkao@linux.alibaba.com

erofs-utils: avoid overly large temporary buffers for compressed data

... and use `EROFS_MAX_BLOCK_SIZE * 2` to avoid potential issues
with buggy compressors.

Signed-off-by: Gao Xiang <hsiangkao@linux.alibaba.com>
Link: https://lore.kernel.org/r/20250214163621.4109215-2-hsiangkao@linux.alibaba.com

erofs-utils: mkfs: add per-segment reaper for multi-threaded compression

Replace the old per-inode reaper to avoid unnecessary memory overhead.
It also speeds up the multithreaded compression a bit.

Signed-off-by: Gao Xiang <hsiangkao@linux.alibaba.com>
Link: https://lore.kernel.org/r/20250214163621.4109215-1-hsiangkao@linux.alibaba.com

erofs-utils: lib: get rid of tmpfile()

Currently, `tmpfile()` is problematic:

 - It uses `FILE *` instead of `fd`;
 - It may not leverage `$TMPDIR`, see `__gen_tempfd()`:
   https://sourceware.org/git?p=glibc.git;a=blob;f=stdio-common/tmpfile.c;hb=glibc-2.41

Switch to `erofs_tmpfile()` throughout the codebase.

Signed-off-by: Gao Xiang <hsiangkao@linux.alibaba.com>
Link: https://lore.kernel.org/r/20250214062407.3281416-2-hsiangkao@linux.alibaba.com

erofs-utils: mkfs: add missing `errno = 0` before strto[u]l

strtoull(3) says:

```
Since strtoul() can legitimately return 0 or ULONG_MAX (ULLONG_MAX for
strtoull()) on both success and failure, the calling program should set
errno to 0 before the call, and then determine if an error occurred by
checking whether errno has a nonzero value after the call.
```

Otherwise, `--workers=` could exit with `invalid worker number`.

Fixes: 7894301e1a80 ("erofs-utils: mkfs: add `--workers=#` parameter")
Fixes: 0132cb5ea7d0 ("erofs-utils: mkfs: add `--zfeature-bits` option")
Fixes: 7550a30c332c ("erofs-utils: enable incremental builds")
Signed-off-by: Gao Xiang <hsiangkao@linux.alibaba.com>
Link: https://lore.kernel.org/r/20250214062407.3281416-1-hsiangkao@linux.alibaba.com

erofs-utils: mkfs: reduce default dict size for LZMA

Change the default dictionary size to 4 times the pcluster size.
This will halve the LZMA internal dictionary size to a maximum of
4MiB per LZMA worker (one worker per CPU in the kernel implementation
unless the module parameter `lzma_streams=` is given.)

It has a very slight impact on the final image sizes, yet users can
always use `-zlzma,dictsize=` to specify a custom value.

  _________________________________________________________________________
 |______ Testset _____|_______ Vanilla _________|_________ After __________| Command Line
 |  CoreOS            |   741978112 (708 MiB)   |   742293504 (708 MiB)    | -zlzma,6 -Eall-fragments,fragdedupe=inode -C8192
 |                    |   687501312 (656 MiB)   |   687652864 (656 MiB)    | -zlzma,6 -Eall-fragments,fragdedupe=inode -C131072
 |____________________|__ 658485248 (628 MiB) __|__ 658698240 (629 MiB)  __| -zlzma,6 -Eall-fragments,fragdedupe=inode -C1048576
 |  Fedora KIWI       |  2974957568 (2838 MiB)  |  2977394688 (2840 MiB)   | -zlzma,6 -Eall-fragments,fragdedupe=inode -C8192
 |                    |  2684272640 (2560 MiB)  |  2686750720 (2563 MiB)   | -zlzma,6 -Eall-fragments,fragdedupe=inode -C131072
 |____________________|_ 2550800384 (2433 MiB) _|_ 2553278464 (2435 MiB) __| -zlzma,6 -Eall-fragments,fragdedupe=inode -C1048576
 |  AOSP system       |   432562176 (413 MiB)   |   432738304 (413 MiB)    | -zlzma,6 -Eall-fragments,fragdedupe=inode -C8192
 |  partition         |   393277440 (376 MiB)   |   393351168 (376 MiB)    | -zlzma,6 -Eall-fragments,fragdedupe=inode -C131072
 |____________________|__ 379260928 (362 MiB) __|__ 379285504 (362 MiB)  __| -zlzma,6 -Eall-fragments,fragdedupe=inode -C1048576

Link: https://lore.kernel.org/r/20250212191545.580768-1-hsiangkao@linux.alibaba.com
Signed-off-by: Gao Xiang <hsiangkao@linux.alibaba.com>

erofs-utils: mkfs: fragment: gracefully exit if temporary storage is low

Currently, EROFS keeps all fragments into a temporary file for later
packed inode compression.  However, this could trigger an unexpected
segfault if temporary storage runs low.

Print a proper error message and gracefully exit.

Closes: https://github.com/erofs/erofs-utils/issues/13
Link: https://lore.kernel.org/r/20250212123633.40004-1-hsiangkao@linux.alibaba.com
Signed-off-by: Gao Xiang <hsiangkao@linux.alibaba.com>

erofs-utils: release 1.8.5

Signed-off-by: Gao Xiang <xiang@kernel.org>

erofs-utils: lib: restrict pcluster size limitations

Source kernel commit: 7c3ca1838a7831855cbf2e6927a10e0e4723edf6

Signed-off-by: Gao Xiang <hsiangkao@linux.alibaba.com>
Link: https://lore.kernel.org/r/20250209143808.2984785-1-hsiangkao@linux.alibaba.com

erofs-utils: lib: tar: keep non-existent directories with their parents

To avoid lack of basic permissions for now.

Signed-off-by: Gao Xiang <hsiangkao@linux.alibaba.com>
Link: https://lore.kernel.org/r/20250209035124.2168333-1-hsiangkao@linux.alibaba.com

erofs-utils: lib: clean up z_erofs_extent_lookback

Source kernel commit: ab474fccd04509db89fde8d3b28c39aa9a47db64

Signed-off-by: Gao Xiang <hsiangkao@linux.alibaba.com>
Link: https://lore.kernel.org/r/20250206125034.1462966-9-hsiangkao@linux.alibaba.com

erofs-utils: lib: refine z_erofs_get_extent_compressedlen()

Source kernel commit: 8f9530aeeb4f756bdfa70510b40e5d28ea3c742e

Signed-off-by: Gao Xiang <hsiangkao@linux.alibaba.com>
Link: https://lore.kernel.org/r/20250206125034.1462966-8-hsiangkao@linux.alibaba.com

erofs-utils: lib: simplify z_erofs_load_compact_lcluster()

Source kernel commit: 2a810ea79cd7a6d5f134ea69ca2ba726e600cbc4

Signed-off-by: Gao Xiang <hsiangkao@linux.alibaba.com>
Link: https://lore.kernel.org/r/20250206125034.1462966-7-hsiangkao@linux.alibaba.com

erofs-utils: lib: handle NONHEAD !delta[1] lclusters gracefully

Source kernel commit: 0bc8061ffc733a0a246b8689b2d32a3e9204f43c

Signed-off-by: Gao Xiang <hsiangkao@linux.alibaba.com>
Link: https://lore.kernel.org/r/20250206125034.1462966-6-hsiangkao@linux.alibaba.com

erofs-utils: lib: sync up zmap.c

commit 31da107fdb0a ("erofs: fold in z_erofs_reload_indexes()")
commit 53a7f9961cdd ("erofs: clean up unnecessary code and comments")
commit 9ff471800b74 ("erofs: get rid of a useless DBG_BUGON")
commit cc4efd3dd2ac ("erofs: stop parsing non-compact HEAD index if clusterofs is invalid")
commit 118a8cf504d7 ("erofs: fix inconsistent per-file compression format")
commit 9b32b063be10 ("erofs: ensure m_llen is reset to 0 if metadata is invalid")

Signed-off-by: Gao Xiang <hsiangkao@linux.alibaba.com>
Link: https://lore.kernel.org/r/20250206125034.1462966-5-hsiangkao@linux.alibaba.com

erofs-utils: lib: introduce the secondary compression head

Source kernel commit: 72bb52620fdffca95a14ee52188a33cd84e574e2

Signed-off-by: Gao Xiang <hsiangkao@linux.alibaba.com>
Link: https://lore.kernel.org/r/20250206125034.1462966-4-hsiangkao@linux.alibaba.com

erofs-utils: lib: get rid of z_erofs_fill_inode()

Source kernel commit: 4fdadd5b0f0c723c812842454f8cca1619f2e731

Signed-off-by: Gao Xiang <hsiangkao@linux.alibaba.com>
Link: https://lore.kernel.org/r/20250206125034.1462966-3-hsiangkao@linux.alibaba.com

erofs-utils: lib: get rid of z_erofs_do_map_blocks() forward declaration

Source kernel commit: 999f2f9a63f475192d837a2b8595eb0962984d21

Signed-off-by: Gao Xiang <hsiangkao@linux.alibaba.com>
Link: https://lore.kernel.org/r/20250206125034.1462966-2-hsiangkao@linux.alibaba.com

erofs-utils: lib: sync up with the latest erofs_fs.h

Mainly commit 745ed7d77834 ("erofs: cleanup i_format-related stuffs")
and commit 7c3ca1838a78 ("erofs: restrict pcluster size limitations")

Signed-off-by: Gao Xiang <hsiangkao@linux.alibaba.com>
Link: https://lore.kernel.org/r/20250206125034.1462966-1-hsiangkao@linux.alibaba.com

erofs-utils: manpages: update new option of mkfs.erofs

Add `-E fragdedupe` and revise some descriptions.

Signed-off-by: Gao Xiang <hsiangkao@linux.alibaba.com>
Link: https://lore.kernel.org/r/20250124024711.2320620-1-hsiangkao@linux.alibaba.com

erofs-utils: fsck: don't dump packed inode data if unneeded

It was a vain attempt.

Signed-off-by: Gao Xiang <hsiangkao@linux.alibaba.com>
Link: https://lore.kernel.org/r/20250124090628.2865088-2-hsiangkao@linux.alibaba.com

erofs-utils: fsck: keep S{U,G}ID bits properly on extraction

As chown(2) explained, "
When the owner or group of an executable file are changed by an
unprivileged user the S_ISUID and S_ISGID mode bits are cleared.
POSIX does not specify whether this also should happen when root does
the chown(); the Linux behavior depends on the kernel version."

Fix it by chown() first.

Fixes: 412c8f908132 ("erofs-utils: fsck: add --extract=X support to extract to path X")
Signed-off-by: Gao Xiang <hsiangkao@linux.alibaba.com>
Link: https://lore.kernel.org/r/20250124090628.2865088-1-hsiangkao@linux.alibaba.com

erofs-utils: mkfs: keep one-block uncompressed data for deduplication

Otherwise, the deduplication rate will be impacted, but it doesn't
matter since `-Ededupe` is still single-threaded.

Fixes: 341d23a878a2 ("erofs-utils: mkfs: speed up uncompressed data handling")
Signed-off-by: Gao Xiang <hsiangkao@linux.alibaba.com>
Link: https://lore.kernel.org/r/20250121165622.2095470-1-hsiangkao@linux.alibaba.com

erofs-utils: introduce fragment cache

Difference from the previous Yiyan's version [1], it just uses
a tmpfile to keep all decompressed data for fragments.

Dataset: linux 5.4.140
mkfs.erofs command line:
mkfs.erofs -zlzma -C131072 -T0 -Eall-fragments,fragdedupe=inode foo.erofs <dir>
Test command line:
hyperfine -p "echo 3 > /proc/sys/vm/drop_caches; sleep 1" "fsck/fsck.erofs --extract foo.erofs"

Vanilla:
  Time (mean ± σ):     362.309 s ±  0.406 s   [User: 360.298 s, System: 0.956 s]

After:
  Time (mean ± σ):     20.880 s ±  0.026 s    [User: 19.751 s, System: 1.058 s]

An in-memory LRU cache could also be implemented later to meet
different needs.

[1] https://lore.kernel.org/r/20231023071528.1912105-1-lyy0627@sjtu.edu.cn

Cc: Li Yiyan <lyy0627@sjtu.edu.cn>
Signed-off-by: Gao Xiang <hsiangkao@linux.alibaba.com>
Link: https://lore.kernel.org/r/20250120023538.3156606-1-hsiangkao@linux.alibaba.com

erofs-utils: lib: add some bit operations

Introduce following bitmap helpers:
erofs_test_bit
__erofs_set_bit
__erofs_clear_bit
erofs_find_next_bit

[1] https://lore.kernel.org/r/20230802091750.74181-3-jefflexu@linux.alibaba.com

Signed-off-by: Jingbo Xu <jefflexu@linux.alibaba.com> [1]
Signed-off-by: Hongzhen Luo <hongzhen@linux.alibaba.com>
Signed-off-by: Gao Xiang <hsiangkao@linux.alibaba.com>
Link: https://lore.kernel.org/r/20250103090338.740593-2-hsiangkao@linux.alibaba.com

erofs-utils: mkfs: fix inefficient fragment deduplication

Currently, long fragment comparisons could cause suboptimal results,
leading to final image sizes still larger than expected:
 _________________________________________________________________________
|______ Testset _____|_______ Vanilla _________|_________ After __________| Command Line
|  CoreOS [1]        |   802107392 (765 MiB)   |   687501312 (656 MiB)    | -zlzma,6 -Eall-fragments,fragdedupe=inode -C131072
|____________________|__ 771715072 (736 MiB) __|__ 658485248 (628 MiB)  __| -zlzma,6 -Eall-fragments,fragdedupe=inode -C1048576
|  Fedora KIWI [2]   |_ 2584076288 (2465 MiB) _|_ 2550837248 (2433 MiB) __| -zlzma,6 -Eall-fragments,fragdedupe=inode -C1048576
|____________________|_ 2843598848 (2712 MiB) _|_ 2810359808 (2681 MiB) __| (Fedora-KDE-Desktop-Live-Rawhide.0.x86_64.iso)

Almost all images that use `-Eall-fragments` could benefit from this.

[1] https://builds.coreos.fedoraproject.org/prod/streams/stable/builds/41.20241215.3.0/x86_64/fedora-coreos-41.20241215.3.0-live.x86_64.iso
[2] https://pagure.io/fedora-kiwi-descriptions.git

Signed-off-by: Gao Xiang <hsiangkao@linux.alibaba.com>
Link: https://lore.kernel.org/r/20250121143400.1857269-1-hsiangkao@linux.alibaba.com

erofs-utils: lib: rework per-sb fragment generator

It's also used for the upcoming fragment cache.

Signed-off-by: Gao Xiang <hsiangkao@linux.alibaba.com>
Link: https://lore.kernel.org/r/20250117074602.2223094-2-hsiangkao@linux.alibaba.com

erofs-utils: lib: use erofs_map_blocks() for all datalayouts

It simplifies the codebase a bit.

Signed-off-by: Gao Xiang <hsiangkao@linux.alibaba.com>
Link: https://lore.kernel.org/r/20250117074602.2223094-1-hsiangkao@linux.alibaba.com

erofs-utils: lib: dynamically sized `struct erofs_dentry`

 - Reduced memory footprints;

 - Optimize dname sorting and strlen(dname).

Signed-off-by: Gao Xiang <hsiangkao@linux.alibaba.com>
Link: https://lore.kernel.org/r/20250115022720.2204033-1-hsiangkao@linux.alibaba.com

erofs-utils: lib: limit NONHEAD delta1 for compact indexes

Otherwise it could be identified as a CBLKCNT lcluster.

It actually has no real impact for 4 KiB lclusters (blocks) since
EROFS_CONFIG_COMPR_MAX_SZ == 4 MiB and Z_EROFS_LI_D0_CBLKCNT means
2048 * 4KiB == 8 MiB.

Fixes: 0917ff150846 ("erofs-utils: fix delta[1] out-of-bound of compact indexes")
Fixes: 2f871035cca6 ("erofs-utils: mkfs: support compact indexes for bigpcluster")
Signed-off-by: Gao Xiang <hsiangkao@linux.alibaba.com>
Link: https://lore.kernel.org/r/20250121130825.1722009-1-hsiangkao@linux.alibaba.com

erofs-utils: dump: Add --cat flag to show file contents

This patch adds a new '--cat' flag to the 'dump.erofs' command. When
used it will write to the standard output the content of the file
indicated by the '--path' or '--nid' options. For example, if there is a
'/mydir/myfile.txt' file containg the text 'mytext':

    $ dump.erofs --cat --path=/mydir/myfile.txt myimage.erofs
    mytext

Signed-off-by: Juan Hernandez <jhernand@redhat.com>
Link: https://lore.kernel.org/r/20250109105611.178398-1-jhernand@redhat.com
Signed-off-by: Gao Xiang <hsiangkao@linux.alibaba.com>

erofs-utils: mkfs: fix crash when failing to build tree

For example: It crashes instead of cleanly erroring out if there's
a file for which it doesn't have permissions to read (e.g. /etc/gshadow
has mode 000).

Reported-by: Jonathan Lebon <jonathan@jlebon.com>
Fixes: 6a8e395ae4fd ("erofs-utils: fix up root inode for incremental builds")
Signed-off-by: Gao Xiang <hsiangkao@linux.alibaba.com>
Link: https://lore.kernel.org/r/20250109050514.3836023-1-hsiangkao@linux.alibaba.com

erofs-utils: mkfs: support `-Efragdedupe=inode`

If the entire inode can be deduplicated against an existing fragment,
simply reuse it.

Multi-threading can still be applied for `-Efragdedupe=inode` with
the current codebase:

Fedora Linux 39 (Workstation Edition) LiveCD results:
 -zlzma,level=6,dictsize=131072 -C65536 -Eall-fragments

   `-E^fragdedupe`         2,003,587,072 bytes (1911 MiB)
   `-Efragdedupe=inode`    1,970,577,408 bytes (1880 MiB)

Signed-off-by: Gao Xiang <hsiangkao@linux.alibaba.com>
Link: https://lore.kernel.org/r/20250103024011.198163-1-hsiangkao@linux.alibaba.com

erofs-utils: release 1.8.4

Signed-off-by: Gao Xiang <xiang@kernel.org>

erofs-utils: fix -Ededupe crash without fragments enabled

The root cause is the same as commit d9baceba7026 ("erofs-utils:
fix -Ededupe crash without fragments enabled").

In fact, the fragment manager should be reworked in the next major
erofs-utils version to avoid those dirty hacks.

Fixes: fc880e31b7c7 ("erofs-utils: mkfs: minor cleanup & rearrangement")
Signed-off-by: Gao Xiang <hsiangkao@linux.alibaba.com>
Link: https://lore.kernel.org/r/20250102113418.3246744-1-hsiangkao@linux.alibaba.com

erofs-utils: mkfs: fix `-Eall-fragments` for multi-threaded compression

`may_packing` in __z_erofs_compress_one() is still bypassed when
multi-threaded compression is enabled, which is unexpected.

Furthermore, multi-threaded `-Eall-fragments,ztailpacking` can
sometimes corrupt images.  Let's fix it.

Fixes: 882ad1c3157f ("erofs-utils: mkfs: fix `-Eall-fragments` for multi-threaded compression")
Fixes: 10c1590c0920 ("erofs-utils: enable multi-threaded support for `-Eall-fragments`")
Signed-off-by: Gao Xiang <hsiangkao@linux.alibaba.com>
Link: https://lore.kernel.org/r/20250102024225.2433419-1-hsiangkao@linux.alibaba.com

erofs-utils: mkfs: allow disabling fragment deduplication

Currently, although fragment inode compression is already
multi-threaded, the data parts of inodes prior to their own fragments
are still single-threaded if fragment deduplication is on.  This can
greatly slow down `-Eall-fragments` image building at least for
the current mkfs codebase.

Let's add an extended option `-E^fragdedupe` to explicitly disable it.

After this commit, the Fedora Kiwi builds I'm testing can be reduced
from 1148s (3,096,842,240 bytes, 2.9G) to 137s (2,969,956,352 bytes,
2.8G) with `-Eall-fragments,^fragdedupe -C524288 -z lzma,level=6,
dictsize=524288` on Intel(R) Xeon(R) Platinum 8269CY CPU @ 2.50GHz with
32 cores.

Cc: Neal Gompa <ngompa13@gmail.com>
Signed-off-by: Gao Xiang <hsiangkao@linux.alibaba.com>
Link: https://lore.kernel.org/r/20241223094031.1534175-1-hsiangkao@linux.alibaba.com

erofs-utils: mkfs: speed up uncompressed data handling

Currently, it only writes one uncompressed block (typically 4 KiB) and
then tries to recompress the remaining part if the entire data was
compressed and proven to be incompressible.

This is wasteful of CPU resources and slow, as such incompressible data
could be skipped entirely.

The LZMA build time for large pclusters (e.g., 512K, 1M) can be greatly
reduced if there is a significant amount of uncompressed data.

Signed-off-by: Gao Xiang <hsiangkao@linux.alibaba.com>
Link: https://lore.kernel.org/r/20241220143859.643175-2-hsiangkao@linux.alibaba.com

erofs-utils: lib: get rid of `len` in z_erofs_compress_one()

More than one extent could be emitted in __z_erofs_compress_one()
later.

Signed-off-by: Gao Xiang <hsiangkao@linux.alibaba.com>
Link: https://lore.kernel.org/r/20241220143859.643175-1-hsiangkao@linux.alibaba.com

erofs-utils: lib: tar: fix LIBARCHIVE.xattr URL-encoded keys

As tar(5) [1] mentioned: `The key value is URL-encoded: All non-ASCII
characters and the two special characters "=" and "%" are encoded as
"%" followed by two uppercase hexadecimal digits.`

Fix it now.

[1] https://man.freebsd.org/cgi/man.cgi?tar(5)

Fixes: c0063a73b01b ("erofs-utils: lib: support importing xattrs from tarerofs")
Signed-off-by: Gao Xiang <hsiangkao@linux.alibaba.com>
Link: https://lore.kernel.org/r/20241226045808.95101-3-hsiangkao@linux.alibaba.com

erofs-utils: lib: tar: fix LIBARCHIVE.xattr base64 decoding

Base64 is described in RFC1521 [1], except that LIBARCHIVE.xattr base64
may not have padding at the end of the data using the '=' character.

[1] https://datatracker.ietf.org/doc/html/rfc1521#section-5.2

Fixes: c0063a73b01b ("erofs-utils: lib: support importing xattrs from tarerofs")
Signed-off-by: Gao Xiang <hsiangkao@linux.alibaba.com>
Link: https://lore.kernel.org/r/20241226045808.95101-2-hsiangkao@linux.alibaba.com

erofs-utils: lib: tar: ignore useless fields of PAX extended headers

Since some unknown writer just leaves zero-filled mtime, e.g.
registry.k8s.io/pause:3.6  --platform windows

Layer sha256: bc8517709e9cfff223cb034ff5be8fcbfa5409de286cdac9ae1b8878ebea6b84

Fixes: 95d315fd7958 ("erofs-utils: introduce tarerofs")
Signed-off-by: Gao Xiang <hsiangkao@linux.alibaba.com>
Link: https://lore.kernel.org/r/20241226045808.95101-1-hsiangkao@linux.alibaba.com

erofs-utils: use external xxhash library if possible

It's expected to be faster than the internal one.

Signed-off-by: Gao Xiang <hsiangkao@linux.alibaba.com>
Link: https://lore.kernel.org/r/20241220144139.648210-1-hsiangkao@linux.alibaba.com

erofs-utils: release 1.8.3

Signed-off-by: Gao Xiang <xiang@kernel.org>

erofs-utils: lib: correct erofsfuse build script

Some of the symbols required by erofsfuse are provided by liberofs.
When option 'enable-static-fuse' is set, all these object file should be
exported to liberofsfuse.a

Signed-off-by: ComixHe <heyuming@deepin.org>
Link: https://lore.kernel.org/r/8725A28257A20420+20241213063250.314786-1-heyuming@deepin.org
Signed-off-by: Gao Xiang <hsiangkao@linux.alibaba.com>

erofs-utils: add --hard-dereference option

Add option --hard-dereference to dereference hardlinks when
creating an image. Instead of reusing the inode, hardlinks are added
as separate inodes. This is useful for reproducible builds, when the
rootfs is space-optimized using hardlinks on some machines, but not on
others.

Co-authored-by: Leonard Cohnen <leonard.cohnen@gmail.com>
Signed-off-by: Paul Meyer <katexochen0@gmail.com>
Link: https://lore.kernel.org/r/20241212165550.58756-1-katexochen0@gmail.com
Signed-off-by: Gao Xiang <hsiangkao@linux.alibaba.com>

erofs-utils: mkfs: add `-U <clear|random>` support

To match `mke2fs`.

Signed-off-by: Gao Xiang <hsiangkao@linux.alibaba.com>
Link: https://lore.kernel.org/r/20241211092704.4008111-1-hsiangkao@linux.alibaba.com

erofs-utils: lib: get rid of pthread_cancel() for workqueue

Since bionic (Android's libc) does not have pthread_cancel(),
call erofs_destroy_workqueue() when initialization fails.

Reviewed-by: Yifan Zhao <zhaoyifan@sjtu.edu.cn>
Cc: Kelvin Zhang <zhangkelvin@google.com>
Signed-off-by: Gao Xiang <hsiangkao@linux.alibaba.com>
Link: https://lore.kernel.org/r/20241211025009.3393476-1-hsiangkao@linux.alibaba.com

erofs-utils: use pkg-config for lz4 configuration

Also obsolete those `LZ4_HC_STATIC_LINKING_ONLY` versions since it's
too complicated to be maintained.

Signed-off-by: Gao Xiang <hsiangkao@linux.alibaba.com>
Link: https://lore.kernel.org/r/20241205030846.70656-1-hsiangkao@linux.alibaba.com

erofs-utils: lib: add missing dependencies

Add the missing ${libdeflate_CFLAGS} and ${libzstd_CFLAGS} to avoid
compilation errors.

Signed-off-by: Gao Xiang <hsiangkao@linux.alibaba.com>
Link: https://lore.kernel.org/r/20241205020915.966196-1-hsiangkao@linux.alibaba.com

erofs-utils: mkfs: make output stable

The iteration order of opendir/readdir depends on filesystem
implementation. Initializng inode->i_ino[0] in the loop causes the
output unstable even though the entries are sorted in
erofs_prepare_dir_file().

In this change,  inode->i_ino[0] is initialized in
erofs_prepare_inode_buffer() instead to make the output stable. (not
affected by readdir())

  # should generate the same output

Test: mkfs.erofs ... inputdir(ext3)
Test: mkfs.erofs ... inputdir(tmpfs)
Signed-off-by: Jooyung Han <jooyung@google.com>
Link: https://lore.kernel.org/r/20241203074531.3728133-1-jooyung@google.com
Signed-off-by: Gao Xiang <hsiangkao@linux.alibaba.com>

erofs-utils: lib: fix user-after-free in xattr.c

Currently, put_xattritem() does not remove the `item`
from the hash table after freeing it, which may lead
to a user-after-free issue.

This patch fixes it.

Fixes: 47d6895a5ff9 ("erofs-utils: introduce inline xattr support")
Signed-off-by: Hongzhen Luo <hongzhen@linux.alibaba.com>
Reviewed-by: Sandeep Dhavale <dhavale@google.com>
Link: https://lore.kernel.org/r/20241202024019.85901-1-hongzhen@linux.alibaba.com
Signed-off-by: Gao Xiang <hsiangkao@linux.alibaba.com>

erofs-utils: rebuild: set the appropriate `dev` field for dirs

Currently, setting a default `dev` value (i.e., 0) for directories
during parsing tar files can lead to the following error:

<E> erofs: bogus i_mode (0) @ nid 0
<E> erofs: failed to read inode @ 0

Consider the following incremental build scenario, where the path
"dir1/dir2" is currently being parsed in tarerofs_parse_tar() and
the directory "dir1" has never appeared before.
`erofs_rebuild_get_dentry()` will call erofs_rebuild_mkdir() to
allocate a new inode for "dir1", with its `dev` field set to 0 by
default.

During the dump tree phase, since `dir1->dev` matches `sbi->dev`
(both are 0), erofs_rebuild_load_basedir() will be called to read
the contents of directory "dir1" from the disk. However, since
there is no information for the new directory "dir1" on the disk,
the above error occurs.

This patch resolves the above issue by setting the appropriate value
for the directory's `dev` field during the tar file parsing phase.

Fixes: f64d9d02576b ("erofs-utils: introduce incremental builds")
Signed-off-by: Hongzhen Luo <hongzhen@linux.alibaba.com>
Link: https://lore.kernel.org/r/20241127111346.49290-1-hongzhen@linux.alibaba.com
Signed-off-by: Gao Xiang <hsiangkao@linux.alibaba.com>

erofs-utils: avoid silent corruption caused by `c_root_xattr_isize`

When `c_root_xattr_isize` is too large, `i_xattr_icount` will overflow,
resulting in silent corruption of the filesystem image. This patch performs
checks in advance and reports errors.

Fixes: 8f93c2f83962 ("erofs-utils: mkfs: support inline xattr reservation for rootdirs")
Signed-off-by: Hongzhen Luo <hongzhen@linux.alibaba.com>
Link: https://lore.kernel.org/r/20241127092825.4105724-1-hongzhen@linux.alibaba.com
Signed-off-by: Gao Xiang <hsiangkao@linux.alibaba.com>

erofs-utils: lib: clean up z_erofs_load_full_lcluster()

Let's keep in sync with kernel commit d69189428d50 ("erofs: clean up
z_erofs_load_full_lcluster()").

Signed-off-by: Gao Xiang <hsiangkao@linux.alibaba.com>
Link: https://lore.kernel.org/r/20241121023517.581040-1-hsiangkao@linux.alibaba.com

erofs-utils: lib: clean up zmap.c

Let's keep in sync with kernel commit 8241fdd3cdfe ("erofs: clean up
zmap.c").

Signed-off-by: Gao Xiang <hsiangkao@linux.alibaba.com>
Link: https://lore.kernel.org/r/20241119085427.1672789-1-hsiangkao@linux.alibaba.com

erofs-utils: fix `Not a directory` error for incremental builds

If an incremental layer contains a directory but the same path in
the base layer is a non-directory, it will fail unexpectedly.

Fix it now.

Reported-by: Hongzhen Luo <hongzhen@linux.alibaba.com>
Co-developped-by: Hongzhen Luo <hongzhen@linux.alibaba.com>
Fixes: f64d9d02576b ("erofs-utils: introduce incremental builds")
Signed-off-by: Gao Xiang <hsiangkao@linux.alibaba.com>
Link: https://lore.kernel.org/r/20241122075659.2869515-1-hsiangkao@linux.alibaba.com

erofs-utils: lib: capture errors from {mkfs,rebuild}_handle_inode()

Currently, the error code returned by erofs_{mkfs,rebuild}_handle_inode()
in erofs_mkfs_dump_tree() may be ignored. This patch introduces `err2` to
capture errors from {mkfs,rebuild}_handle_inode().

Signed-off-by: Hongzhen Luo <hongzhen@linux.alibaba.com>
Link: https://lore.kernel.org/r/20241112020830.849210-1-hongzhen@linux.alibaba.com
Signed-off-by: Gao Xiang <hsiangkao@linux.alibaba.com>

erofs-utils: lib: rearrange struct erofs_configure

Move the fields controlled by the NDEBUG macro to the end
to maintain a consistent layout for preceding variables.

It addresses cases where a third-party application does not define
NDEBUG while erofs-utils does.  Ideally, third-party applications
should use the same macros as erofs-utils to get a unique
`struct erofs_configure`. However, since NDEBUG enables unnecessary
assertions, restructuring the layout resolves such inconsistencies.

Fixes: ad6c80dc168d ("erofs-utils: lib: add erofs_get_configure()")
Signed-off-by: Hongzhen Luo <hongzhen@linux.alibaba.com>
Link: https://lore.kernel.org/r/20241111095715.3814956-1-hongzhen@linux.alibaba.com
Signed-off-by: Gao Xiang <hsiangkao@linux.alibaba.com>

erofs-utils: mkfs: Fix input offset counting in headerball mode

When using --tar=headerball, most files included in the headerball are
not included in the EROFS image. mkfs.erofs typically exits prematurely,
having processed non-USTAR blocks as USTAR and believing they are
end-of-archive markers. (Other failure modes are probably also possible
if the input stream doesn't look like end-of-archive markers at the
locations that are being read.)

This is because we lost correct count of bytes that are read from the
input stream when in headerball (or ddtaridx) modes. We were assuming that
in these modes no data would be read following the ustar block, but in
case of things like PAX headers, lots more data may be read without
incrementing tar->offset.

This corrects by always incrementing the offset counter, and then
decrementing it again in the one case where headerballs differ -
regular file data blocks are not present.

Signed-off-by: Mike Baynton <mike@mbaynton.com>
Link: https://lore.kernel.org/r/20241111164819.560567-1-mike@mbaynton.com
Signed-off-by: Gao Xiang <hsiangkao@linux.alibaba.com>

erofs-utils: avoid allocating large arrays on the stack

The default pthread stack size of bionic is 1M. Use malloc to avoid
stack overflow.

Signed-off-by: Jianan Huang <huangjianan@xiaomi.com>
Link: https://lore.kernel.org/r/20241025015246.649209-1-huangjianan@xiaomi.com
Reviewed-by: Sandeep Dhavale <dhavale@google.com>
Signed-off-by: Gao Xiang <hsiangkao@linux.alibaba.com>

erofs-utils: lib: report leftovers for partially filled blocks

3rd-party applications may need the exact zeroed size for each
partial filesystem block to populate remote data.

Signed-off-by: Gao Xiang <hsiangkao@linux.alibaba.com>
Link: https://lore.kernel.org/r/20241018062417.2297930-1-hsiangkao@linux.alibaba.com

erofs-utils: mkfs: fix unexpected errors for chunk-based images

mkfs.erofs may fail because copy_file_range() returns the number of
bytes which could be less than the length originally requested.

Fixes: 03cbf7b8f7f7 ("erofs-utils: mkfs: support chunk-based uncompressed files")
Signed-off-by: Gao Xiang <hsiangkao@linux.alibaba.com>
Link: https://lore.kernel.org/r/20241016074849.2862282-1-hsiangkao@linux.alibaba.com

erofs-utils: mkfs: fix `-Eall-fragments` for multi-threaded compression

If `-Eall-fragments` is specified when multi-threaded compression is
enabled, it should only apply to the packed inode instead of other
real inodes for now.

Fixes: 10c1590c0920 ("erofs-utils: enable multi-threaded support for `-Eall-fragments`")
Signed-off-by: Gao Xiang <hsiangkao@linux.alibaba.com>
Link: https://lore.kernel.org/r/20241012035213.3729725-1-hsiangkao@linux.alibaba.com