| lists.openwall.net | lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC | |
|
Open Source and information security mailing list archives
| ||
|
Message-ID: <175798161081.389252.792881872242373984.stgit@frogsfrogsfrogs>
Date: Mon, 15 Sep 2025 17:55:04 -0700
From: "Darrick J. Wong" <djwong@...nel.org>
To: tytso@....edu
Cc: miklos@...redi.hu, neal@...pa.dev, amir73il@...il.com,
linux-fsdevel@...r.kernel.org, linux-ext4@...r.kernel.org, John@...ves.net,
bernd@...ernd.com, joannelkoong@...il.com
Subject: [PATCH 17/21] cache: implement automatic shrinking
From: Darrick J. Wong <djwong@...nel.org>
Shrink the cache whenever maxcount has been expanded beyond its initial
value, we release a cached object to one of the mru lists and the number
of objects sitting on the mru is enough to drop the cache count down a
level. This enables a cache to reduce its memory consumption after a
spike in which reclamation wasn't possible.
Signed-off-by: "Darrick J. Wong" <djwong@...nel.org>
---
lib/support/cache.h | 17 ++++++-
lib/support/cache.c | 118 ++++++++++++++++++++++++++++++++++++++++++++++++---
2 files changed, 126 insertions(+), 9 deletions(-)
diff --git a/lib/support/cache.h b/lib/support/cache.h
index ae37945c545f46..cd738b6cd3a460 100644
--- a/lib/support/cache.h
+++ b/lib/support/cache.h
@@ -16,6 +16,9 @@
*/
#define CACHE_MISCOMPARE_PURGE (1 << 0)
+/* Automatically shrink the cache's max_count when possible. */
+#define CACHE_CAN_SHRINK (1U << 1)
+
/*
* cache object campare return values
*/
@@ -67,12 +70,18 @@ typedef unsigned int (*cache_bulk_relse_t)(struct cache *, struct list_head *);
typedef int (*cache_node_get_t)(struct cache *c, struct cache_node *cn);
typedef void (*cache_node_put_t)(struct cache *c, struct cache_node *cn);
typedef unsigned int (*cache_node_resize_t)(const struct cache *c,
- unsigned int curr_size);
+ unsigned int curr_size,
+ int dir);
static inline unsigned int cache_gradual_resize(const struct cache *cache,
- unsigned int curr_size)
+ unsigned int curr_size,
+ int dir)
{
- return curr_size * 5 / 4;
+ if (dir < 0)
+ return curr_size * 9 / 10;
+ else if (dir > 0)
+ return curr_size * 5 / 4;
+ return curr_size;
}
struct cache_operations {
@@ -111,6 +120,7 @@ struct cache_node {
struct cache {
int c_flags; /* behavioural flags */
+ unsigned int c_orig_max; /* original max cache nodes */
unsigned int c_maxcount; /* max cache nodes */
unsigned int c_count; /* count of nodes */
pthread_mutex_t c_mutex; /* node count mutex */
@@ -143,6 +153,7 @@ void cache_destroy(struct cache *cache);
void cache_walk(struct cache *cache, cache_walk_t fn, void *data);
void cache_purge(struct cache *);
bool cache_flush(struct cache *cache);
+void cache_shrink(struct cache *cache);
/* don't allocate a new node */
#define CACHE_GET_INCORE (1U << 0)
diff --git a/lib/support/cache.c b/lib/support/cache.c
index dbaddc1bd36d3d..7e1ddc3cc8788d 100644
--- a/lib/support/cache.c
+++ b/lib/support/cache.c
@@ -53,6 +53,7 @@ cache_init(
cache->c_hits = 0;
cache->c_misses = 0;
cache->c_maxcount = maxcount;
+ cache->c_orig_max = maxcount;
cache->hash = cache_operations->hash;
cache->alloc = cache_operations->alloc;
cache->flush = cache_operations->flush;
@@ -95,7 +96,7 @@ cache_expand(
pthread_mutex_lock(&cache->c_mutex);
if (cache->resize)
- new_size = cache->resize(cache, cache->c_maxcount);
+ new_size = cache->resize(cache, cache->c_maxcount, 1);
if (new_size <= cache->c_maxcount)
new_size = cache->c_maxcount * 2;
#ifdef CACHE_DEBUG
@@ -226,7 +227,8 @@ static unsigned int
cache_shake(
struct cache * cache,
unsigned int priority,
- bool purge)
+ bool purge,
+ unsigned int nr_to_shake)
{
struct cache_mru *mru;
struct cache_hash *hash;
@@ -274,7 +276,7 @@ cache_shake(
pthread_mutex_unlock(&node->cn_mutex);
count++;
- if (!purge && count == CACHE_SHAKE_COUNT)
+ if (!purge && count == nr_to_shake)
break;
}
pthread_mutex_unlock(&mru->cm_mutex);
@@ -287,7 +289,7 @@ cache_shake(
pthread_mutex_unlock(&cache->c_mutex);
}
- return (count == CACHE_SHAKE_COUNT) ? priority : ++priority;
+ return (count == nr_to_shake) ? priority : ++priority;
}
/*
@@ -477,7 +479,7 @@ cache_node_get(
node = cache_node_allocate(cache, key);
if (node)
break;
- priority = cache_shake(cache, priority, false);
+ priority = cache_shake(cache, priority, false, CACHE_SHAKE_COUNT);
/*
* We start at 0; if we free CACHE_SHAKE_COUNT we get
* back the same priority, if not we get back priority+1.
@@ -507,12 +509,112 @@ cache_node_get(
return 1;
}
+static unsigned int cache_mru_count(const struct cache *cache)
+{
+ const struct cache_mru *mru = cache->c_mrus;
+ unsigned int mru_count = 0;
+ unsigned int i;
+
+ for (i = 0; i < CACHE_NR_PRIORITIES; i++, mru++)
+ mru_count += mru->cm_count;
+
+ return mru_count;
+}
+
+
+void cache_shrink(struct cache *cache)
+{
+ unsigned int mru_count = 0;
+ unsigned int threshold = 0;
+ unsigned int priority = 0;
+ unsigned int new_size;
+
+ pthread_mutex_lock(&cache->c_mutex);
+ /* Don't shrink below the original cache size */
+ if (cache->c_maxcount <= cache->c_orig_max)
+ goto out_unlock;
+
+ mru_count = cache_mru_count(cache);
+
+ /*
+ * If there's not even a batch of nodes on the MRU to try to free,
+ * don't bother with the rest.
+ */
+ if (mru_count < CACHE_SHAKE_COUNT)
+ goto out_unlock;
+
+ /*
+ * Figure out the next step down in size, but don't go below the
+ * original size.
+ */
+ if (cache->resize)
+ new_size = cache->resize(cache, cache->c_maxcount, -1);
+ else
+ new_size = cache->c_maxcount / 2;
+ if (new_size >= cache->c_maxcount)
+ goto out_unlock;
+ if (new_size < cache->c_orig_max)
+ new_size = cache->c_orig_max;
+
+ /*
+ * If we can't purge enough nodes to get the node count below new_size,
+ * don't resize the cache.
+ */
+ if (cache->c_count - mru_count >= new_size)
+ goto out_unlock;
+
+#ifdef CACHE_DEBUG
+ fprintf(stderr, "decreasing cache max size from %u to %u (currently %u)\n",
+ cache->c_maxcount, new_size, cache->c_count);
+#endif
+ cache->c_maxcount = new_size;
+
+ /* Try to reduce the number of cached objects. */
+ do {
+ unsigned int new_priority;
+
+ /*
+ * The threshold is the amount we need to purge to get c_count
+ * below the new maxcount. Try to free some objects off the
+ * MRU. Drop c_mutex because cache_shake will take it.
+ */
+ threshold = cache->c_count - new_size;
+ pthread_mutex_unlock(&cache->c_mutex);
+
+ new_priority = cache_shake(cache, priority, false, threshold);
+
+ /* Either we made no progress or we ran out of MRU levels */
+ if (new_priority == priority ||
+ new_priority > CACHE_MAX_PRIORITY)
+ return;
+ priority = new_priority;
+
+ pthread_mutex_lock(&cache->c_mutex);
+ /*
+ * Someone could have walked in and changed the cache maxsize
+ * again while we had the lock dropped. If that happened, stop
+ * clearing.
+ */
+ if (cache->c_maxcount != new_size)
+ goto out_unlock;
+
+ mru_count = cache_mru_count(cache);
+ if (cache->c_count - mru_count >= new_size)
+ goto out_unlock;
+ } while (1);
+
+out_unlock:
+ pthread_mutex_unlock(&cache->c_mutex);
+ return;
+}
+
void
cache_node_put(
struct cache * cache,
struct cache_node * node)
{
struct cache_mru * mru;
+ bool was_put = false;
pthread_mutex_lock(&node->cn_mutex);
#ifdef CACHE_DEBUG
@@ -528,6 +630,7 @@ cache_node_put(
}
#endif
node->cn_count--;
+ was_put = (node->cn_count == 0);
if (node->cn_count == 0 && cache->put)
cache->put(cache, node);
@@ -541,6 +644,9 @@ cache_node_put(
}
pthread_mutex_unlock(&node->cn_mutex);
+
+ if (was_put && (cache->c_flags & CACHE_CAN_SHRINK))
+ cache_shrink(cache);
}
void
@@ -632,7 +738,7 @@ cache_purge(
int i;
for (i = 0; i <= CACHE_DIRTY_PRIORITY; i++)
- cache_shake(cache, i, true);
+ cache_shake(cache, i, true, CACHE_SHAKE_COUNT);
#ifdef CACHE_DEBUG
if (cache->c_count != 0) {
Powered by blists - more mailing lists