[PATCH] squashfs: avoid thundering-herd cache wakeups

[PATCH] squashfs: avoid thundering-herd cache wakeups

[Usama Arif]

squashfs_cache_get() puts a task to sleep when its block is not cached and
every cache entry is busy.  Those sleeps are non-exclusive, so a single
squashfs_cache_put() makes every waiter runnable when one entry is freed.
A wakee returns to squashfs_cache_get() only if it observes cache->unused
before the entry is reclaimed.  Such tasks can rescan and share a block
published meanwhile; later wakees see zero and queue again inside
wait_event() without rescanning.

The waste is dramatic under load.  On a Meta production host serving a
Python web application from a packaged squashfs image, a 30-second trace
caught 1,045,132 cache-release wake calls and 19,511,556 remote wakeups:
18.7 per release, although each release added only one reusable cache
entry. This was causing significant spikes in CPU usage.

Simply making the waits exclusive (i.e. using
wait_event_state_exclusive()) is not enough.  A waiter can make
progress two ways, when an entry frees (capacity), or when another task
publishes the block it wants and it shares that entry.  The only wait
condition available is cache->unused, which captures capacity but not
publication, and wake-one can release just a single sharer at a time.  A
waiter woken for capacity may also find its block already published, share
it, and leave the freed entry unclaimed, so that wake must be handed on.
A block-targeted wake and that handoff need a custom wake callback with
per-waiter state; wait_event_state_exclusive() provides neither.

Wake selectively instead.  Waiters are exclusive and keyed by requested
block: freeing an entry wakes one waiter (capacity), publishing a block
wakes every waiter for that block (sharing), and a capacity waiter that
ends up sharing hands its wake to the next waiter.  Waiters enqueue while
holding cache->lock so lookup and publication are ordered against sleeping.

The result is an ~2x increase in throughput on stat and read.
Measured on a 32-CPU VM against a read-only squashfs (gzip, per-cpu
decompressor, default 8 metadata / 3 fragment cache entries) staged in tmpfs
with caches dropped each iteration to force cold decompression:

  elbencho, 64 threads
    metadata stat      700 ->  1320 files/s    1.9x
    small-file read     40 ->    60 MiB/s      1.6x

  filebench, 128 threads, open+read+stat+close (mean of 3x 30s)
    throughput       11,314 -> 25,186 ops/s    2.2x
    latency           11.30 ->   5.05 ms/op    2.2x lower
    sched:sched_wakeup 9.18M ->  3.44M         2.7x fewer
    context switches  12.62M ->  5.77M         2.2x fewer

The 2.7x cut in scheduler wakeups explains the results: it roughly doubles
throughput and halves latency under contention, and is a no-op on
workloads that never queue for a cache entry.

Signed-off-by: Usama Arif <usama.arif@linux.dev>
---
 fs/squashfs/cache.c | 66 ++++++++++++++++++++++++++++++++++++++++-----
 1 file changed, 60 insertions(+), 6 deletions(-)

diff --git a/fs/squashfs/cache.c b/fs/squashfs/cache.c
index 67abd4dff222..5c790c204a1a 100644
--- a/fs/squashfs/cache.c
+++ b/fs/squashfs/cache.c
@@ -45,6 +45,40 @@
 #include "squashfs.h"
 #include "page_actor.h"
 
+/*
+ * A NULL wake key selects one waiter for newly available capacity.  A block
+ * key selects every waiter which can share the newly published cache entry.
+ */
+struct squashfs_cache_wait {
+	wait_queue_entry_t wait;
+	u64 block;
+	bool capacity_wake;
+};
+
+static int squashfs_cache_wake_function(wait_queue_entry_t *wait,
+					unsigned int mode, int sync, void *key)
+{
+	struct squashfs_cache_wait *cache_wait =
+		container_of(wait, struct squashfs_cache_wait, wait);
+	u64 *block = key;
+	int ret;
+
+	if (block && cache_wait->block != *block)
+		return 0;
+
+	/* A failed wake remains queued, so finish_wait() sees the reset. */
+	WRITE_ONCE(cache_wait->capacity_wake, !block);
+	ret = autoremove_wake_function(wait, mode, sync, NULL);
+	if (!ret)
+		WRITE_ONCE(cache_wait->capacity_wake, false);
+	return ret;
+}
+
+static void squashfs_cache_wake_block(struct squashfs_cache *cache, u64 block)
+{
+	__wake_up(&cache->wait_queue, TASK_NORMAL, 0, &block);
+}
+
 /*
  * Look-up block in cache, and increment usage count.  If not in cache, read
  * and decompress it from disk.
@@ -54,6 +88,8 @@ struct squashfs_cache_entry *squashfs_cache_get(struct super_block *sb,
 {
 	int i, n;
 	struct squashfs_cache_entry *entry;
+	struct squashfs_cache_wait wait = { .block = block };
+	bool consumed, pending, wake_block, wake_next;
 
 	spin_lock(&cache->lock);
 
@@ -72,9 +108,16 @@ struct squashfs_cache_entry *squashfs_cache_get(struct super_block *sb,
 			 * go to sleep waiting for one to become available.
 			 */
 			if (cache->unused == 0) {
+				init_wait(&wait.wait);
+				wait.wait.func = squashfs_cache_wake_function;
 				cache->num_waiters++;
+				WRITE_ONCE(wait.capacity_wake, false);
+				/* Enqueue before dropping the lock to avoid missing publish. */
+				prepare_to_wait_exclusive(&cache->wait_queue,
+							  &wait.wait, TASK_UNINTERRUPTIBLE);
 				spin_unlock(&cache->lock);
-				wait_event(cache->wait_queue, cache->unused);
+				schedule();
+				finish_wait(&cache->wait_queue, &wait.wait);
 				spin_lock(&cache->lock);
 				cache->num_waiters--;
 				continue;
@@ -105,8 +148,12 @@ struct squashfs_cache_entry *squashfs_cache_get(struct super_block *sb,
 			entry->pending = 1;
 			entry->num_waiters = 0;
 			entry->error = 0;
+			wake_block = cache->num_waiters;
 			spin_unlock(&cache->lock);
 
+			if (wake_block)
+				squashfs_cache_wake_block(cache, block);
+
 			entry->length = squashfs_read_data(sb, block, length,
 				&entry->next_index, entry->actor);
 
@@ -138,7 +185,8 @@ struct squashfs_cache_entry *squashfs_cache_get(struct super_block *sb,
 		 * for reuse.
 		 */
 		entry = &cache->entry[i];
-		if (entry->refcount == 0)
+		consumed = entry->refcount == 0;
+		if (consumed)
 			cache->unused--;
 		entry->refcount++;
 
@@ -146,12 +194,18 @@ struct squashfs_cache_entry *squashfs_cache_get(struct super_block *sb,
 		 * If the entry is currently being filled in by another process
 		 * go to sleep waiting for it to become available.
 		 */
-		if (entry->pending) {
+		pending = entry->pending;
+		if (pending)
 			entry->num_waiters++;
-			spin_unlock(&cache->lock);
+		/* Pass on capacity if this waiter shared rather than consumed it. */
+		wake_next = READ_ONCE(wait.capacity_wake) && !consumed &&
+			cache->unused && cache->num_waiters;
+		spin_unlock(&cache->lock);
+
+		if (wake_next)
+			wake_up(&cache->wait_queue);
+		if (pending)
 			wait_event(entry->wait_queue, !entry->pending);
-		} else
-			spin_unlock(&cache->lock);
 
 		goto out;
 	}
-- 
2.53.0-Meta