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

[Yang Wen]

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

                         Previous baseline   Patched v8
  real                   589.48 s            30.27 s
  user                     4.72 s             3.40 s
  sys                    584.63 s            26.83 s

The unpatched baseline is a previously recorded result and was not rerun.
The patched run created 20,000 files; fsck.exfat reported a clean image.

Changes in v8:
- Rebase the series onto exfat/dev at 8e431c3bce0b.
- Drop unrelated blank-line changes from the Bloom-filter patch.
- Discard empty-entry hints collected by positive name lookups, since a
  lookup can start at hint_stat and return before scanning the directory
  prefix.
- Track the remaining root-directory chain length during volume-label scans
  so their empty-entry hints remain valid across cluster boundaries.
- Remove a reclaimed filter from the LRU before clearing the inode pointer,
  so the lockless free fast path cannot observe a linked but pointerless
  filter during teardown.

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
  exfat: retain the next empty directory entry hint
  exfat: reclaim name filters under memory pressure

 fs/exfat/dir.c      | 363 +++++++++++++++++++++++++++++++++++++++++++-
 fs/exfat/exfat_fs.h |  30 +++-
 fs/exfat/inode.c    |   1 +
 fs/exfat/namei.c    |  87 ++++++++++-
 fs/exfat/super.c    |   9 ++
 5 files changed, 478 insertions(+), 12 deletions(-)

base-commit: 8e431c3bce0bb51802fc79b10225cc90a15f15d1
-- 
2.34.1