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

[Yang Wen <anmuxixixi@gmail.com>]

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

Creating 20,000 empty files improved from 589.48 seconds to 5.33 seconds,
which is a 110.6-fold speedup.

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      | 279 ++++++++++++++++++++++++++++++++++++++++++++
 fs/exfat/exfat_fs.h |  23 ++++
 fs/exfat/inode.c    |   1 +
 fs/exfat/namei.c    |  58 ++++++++-
 fs/exfat/super.c    |   9 ++
 5 files changed, 369 insertions(+), 1 deletion(-)

-- 
2.34.1