Re: [PATCH v7 0/3] exfat: speed up file creation in large directories

[Namjae Jeon]

On Sun, Oct 4, 2026 at 10:57 PM Yang Wen <anmuxixixi@xxxxxxxxx> wrote:
>
> Negative name lookups and empty-entry allocation can repeatedly scan a
> directory from the beginning. Bulk creation in a large directory therefore
> approaches O(N^2).
>
> This series separates the optimization into three independently reviewable
> steps. Patch 1 adds the Bloom filter used to reject definite name misses.
> Patch 2 retains and correctly invalidates the next-empty-entry hint.
> Patch 3 adds the LRU and shrinker used to reclaim filters under memory
> pressure.
>
> Test environment:
>   QEMU TCG multi-thread, 4 vCPUs, 6 GiB RAM
>   4 GiB exFAT image, 32 KiB clusters
>
> The measured results were:
>
>                          Before          After
>   real                   589.48 s        30.09 s
>   user                     4.72 s         3.40 s
>   sys                    584.63 s        26.65 s
>
>
> Changes in v7:
> - Size each Bloom filter from the allocated directory size, using four bits
>   per on-disk entry and clamping the bitmap between 512 bytes and 4 MiB.
> - Track set bits and discard a filter when one third of its bits are set or
>   directory growth requires a larger bitmap. Rebuild it lazily after a
>   later complete negative lookup.
> - Account reclaimable filters in pages so shrinker accounting follows their
>   dynamic allocation sizes.
> - Preserve the shrinker core's scan budget and return SHRINK_STOP when the
>   LRU is already empty, preventing repeated no-progress scans.
>
> Changes in v6:
> - Invalidate the name filter when committing a new entry set fails, before
>   attempting rollback. Despite the reported write error, the new name may
>   already have reached disk.
> - Move rename/move error invalidation into the Bloom filter patch so that
>   each patch remains correct when applied independently.
>
> Changes in v5:
> - Rebase the series onto the exFAT maintainer's dev branch.
> - Treat every non-negative exfat_find_empty_entry() return value as a
>   successful allocation in the volume-label path.
> - Record the minimum entry-set size for which a saved empty-entry hint is
>   valid. A shorter entry set now rescans from the beginning and can reuse a
>   smaller hole that an earlier, longer entry set could not use.
>
> Changes in v4:
> - Publish the next-empty-entry hint only after the directory entry set is
>   successfully committed, so post-allocation failures cannot skip an unused
>   slot.
> - Invalidate the destination name filter when rename or move fails because
>   the new entry may already exist on disk.
>
> Changes in v3:
> - Split the change into Bloom filter, empty-entry hint, and shrinker
>   patches.
> - Accept filenames containing exactly 255 UTF-16 code units while building
>   the Bloom filter.
> - Invalidate the empty-entry hint in every path that can free directory
>   entries, preventing stale hints from skipping earlier holes.
>
> Changes in v2:
> - Move exfat_name_filter_free() to exfat_evict_inode() because
>   ->free_inode() may run from an RCU callback in softirq context.
>
> Yang Wen (3):
>   exfat: add a Bloom filter for negative name lookups
The removal of blank lines in unlink/rmdir/rename is unrelated to this
patch, and the code will be put back in that place in 2/3. It would be
better to drop it.

>   exfat: retain the next empty directory entry hint
>   exfat: reclaim name filters under memory pressure
Please check if Sashiko' review points are false alarms.

https://sashiko.dev/#/patchset/20261004135638.1888530-1-anmuxixixi%40gmail.com

Thanks!