Re: [PATCH] rebuild: prevent quadratic snapshot merges on wide directories

[Gao Xiang <xiang@kernel.org>]

Hi Chris,

On Sun, Aug 09, 2026 at 05:44:08PM -0400, Chris Ayoub wrote:
> Directory entry merging currently performs a linear search of the
> destination directory for each source entry. Repeating this operation
> for wide directories makes snapshot rebuilding quadratic.
> 
> Add a temporary hashmap keyed by the parent inode and entry name during
> rebuild. Use the index to find existing children while preserving the
> existing merge and replacement behavior, and release it when rebuilding
> finishes.
> 
> In the original reproducer, merging 129 layers containing approximately
> 2.4 million entries did not finish after 1195 seconds. With the index,
> the same merge completed in 1.40 seconds. The widest directories
> contained 65,212 and 83,318 entries.
> 
> Assisted-by: Codex:gpt-5
> Signed-off-by: Chris Ayoub <cayoub@openai.com>
> ---
> Snapshot rebuild currently performs a linear directory search for every
> entry being merged.  This becomes prohibitively expensive for container
> images with very wide directories.
> 
> The patch adds a temporary rebuild-only hashmap keyed by parent inode and
> entry name.  It preserves the existing merge and replacement behavior and
> releases the index after all source trees have been loaded.
> 
> The original workload merged 129 layers containing approximately 2.4
> million entries.  The unmodified rebuild did not finish after 1195 seconds;
> with the index, it completed in 1.40 seconds.  The widest directories had
> 65,212 and 83,318 entries.
> 
> Validation against current dev (v1.9.3) on arm64 Ubuntu 24.04:
> 
> - Full build with LZ4, LZMA, FUSE, and Zstd enabled
> - make check
> - Byte-identical output versus unmodified v1.9.3 for file replacement,
>   whiteout and opaque-directory handling, and an 8,000-entry directory
> - Extracted-tree checks for replacement, whiteout, and opaque semantics
> - 8,000-entry local rebuild: 0.23 seconds before, 0.01 seconds after

Yes, it's a known issue, but could you avoid using `hashmap` in
erofs-utils (we could just use `struct list_head hash[xxx] instead.`).

I'd like to get rid of `hashmap` since it's out of git codebase and
the license is GPL only.

Thanks,
Gao Xiang