msuozzo · Oct 11, 2026
diff --git a/src/libgit2/pack.c b/src/libgit2/pack.c
@@ -103,6 +103,30 @@ static int cache_init(git_pack_cache *cache)
 	return 0;
 }
 
+static void lru_unlink(git_pack_cache *cache, git_pack_cache_entry *e)
+{
+	if (e->prev)
+		e->prev->next = e->next;
+	else
+		cache->head = e->next;
+	if (e->next)
+		e->next->prev = e->prev;
+	else
+		cache->tail = e->prev;
+	e->prev = e->next = NULL;
+}
+
+static void lru_push(git_pack_cache *cache, git_pack_cache_entry *e)
+{
+	e->prev = NULL;
+	e->next = cache->head;
+	if (cache->head)
+		cache->head->prev = e;
+	else
+		cache->tail = e;
+	cache->head = e;
+}
+
 static git_pack_cache_entry *cache_get(git_pack_cache *cache, off64_t offset)
 {
 	git_pack_cache_entry *entry = NULL;
@@ -112,28 +136,34 @@ static git_pack_cache_entry *cache_get(git_pack_cache *cache, off64_t offset)
 
 	if (git_pack_offsetmap_get(&entry, &cache->entries, offset) == 0) {
 		git_atomic32_inc(&entry->refcount);
-		entry->last_usage = cache->use_ctr++;
+		lru_unlink(cache, entry);
+		lru_push(cache, entry);
 	}
 
 	git_mutex_unlock(&cache->lock);
 
 	return entry;
 }
 
-/* Run with the cache lock held */
-static void free_lowest_entry(git_pack_cache *cache)
+/*
+ * Frees unreferenced entries, least recently used first, until `len` more
+ * bytes fit, and returns whether they do. Run with the cache lock held.
+ */
+static bool cache_make_room(git_pack_cache *cache, size_t len)
 {
-	git_hashmap_iter_t iter = GIT_HASHMAP_ITER_INIT;
-	git_pack_cache_entry *entry;
-	off64_t offset;
+	git_pack_cache_entry *e = cache->tail, *prev;
 
-	while (git_pack_offsetmap_iterate(&iter, &offset, &entry, &cache->entries) == 0) {
-		if (entry && git_atomic32_get(&entry->refcount) == 0) {
-			cache->memory_used -= entry->raw.len;
-			git_pack_offsetmap_remove(&cache->entries, offset);
-			free_cache_object(entry);
-		}
+	for (; e && cache->memory_used + len > cache->memory_limit; e = prev) {
+		prev = e->prev;
+		if (git_atomic32_get(&e->refcount) != 0)
+			continue;
+		lru_unlink(cache, e);
+		cache->memory_used -= e->raw.len;
+		git_pack_offsetmap_remove(&cache->entries, e->offset);
+		free_cache_object(e);
 	}
+
+	return cache->memory_used + len <= cache->memory_limit;
 }
 
 static int cache_add(
@@ -143,7 +173,7 @@ static int cache_add(
 		off64_t offset)
 {
 	git_pack_cache_entry *entry;
-	int exists;
+	bool added = false;
 
 	if (base->len > GIT_PACK_CACHE_SIZE_LIMIT)
 		return -1;
@@ -155,20 +185,20 @@ static int cache_add(
 			git__free(entry);
 			return -1;
 		}
-		/* Add it to the cache if nobody else has */
-		exists = git_pack_offsetmap_contains(&cache->entries, offset);
-		if (!exists) {
-			while (cache->memory_used + base->len > cache->memory_limit)
-				free_lowest_entry(cache);
-
-			git_pack_offsetmap_put(&cache->entries, offset, entry);
+		/* Add it to the cache if nobody else has and it fits */
+		if (!git_pack_offsetmap_contains(&cache->entries, offset) &&
+		    cache_make_room(cache, base->len) &&
+		    git_pack_offsetmap_put(&cache->entries, offset, entry) == 0) {
+			entry->offset = offset;
+			lru_push(cache, entry);
 			cache->memory_used += entry->raw.len;
 
 			*cached_out = entry;
+			added = true;
 		}
 		git_mutex_unlock(&cache->lock);
-		/* Somebody beat us to adding it into the cache */
-		if (exists) {
+
+		if (!added) {
 			git__free(entry);
 			return -1;
 		}

diff --git a/src/libgit2/pack.h b/src/libgit2/pack.h
@@ -69,7 +69,9 @@ struct git_pack_idx_header {
 };
 
 typedef struct git_pack_cache_entry {
-	size_t last_usage; /* enough? */
+	/* Neighbors in the cache's LRU list, most recently used first. */
+	struct git_pack_cache_entry *prev, *next;
+	off64_t offset;
 	git_atomic32 refcount;
 	git_rawobj raw;
 } git_pack_cache_entry;
@@ -100,7 +102,7 @@ GIT_HASHMAP_OID_PROTOTYPES(git_pack_oidmap, struct git_pack_entry *);
 typedef struct {
 	size_t memory_used;
 	size_t memory_limit;
-	size_t use_ctr;
+	git_pack_cache_entry *head, *tail; /* LRU list */
 	git_mutex lock;
 	git_pack_offsetmap entries;
 } git_pack_cache;

diff --git a/tests/libgit2/pack/cache.c b/tests/libgit2/pack/cache.c
@@ -0,0 +1,113 @@
+#include "clar_libgit2.h"
+#include "mwindow.h"
+#include "pack.h"
+
+/* A copy of the pack, so that no other test has it open already. */
+#define PACK_IDX "testrepo.git/objects/pack/pack-a81e489679b7d3418f9ab594bda8ceb37dd4c695.idx"
+
+static struct git_pack_file *pack;
+static git_array_t(git_oid) ids;
+
+void test_pack_cache__initialize(void)
+{
+	cl_fixture_sandbox("testrepo.git");
+}
+
+void test_pack_cache__cleanup(void)
+{
+	if (pack) {
+		git_mwindow_put_pack(pack);
+		pack = NULL;
+	}
+	git_array_clear(ids);
+	cl_fixture_cleanup("testrepo.git");
+}
+
+static int collect_id(const git_oid *id, void *payload)
+{
+	git_oid *out = git_array_alloc(ids);
+
+	GIT_UNUSED(payload);
+	GIT_ERROR_CHECK_ALLOC(out);
+	git_oid_cpy(out, id);
+	return 0;
+}
+
+static void open_pack(void)
+{
+	cl_git_pass(git_mwindow_get_pack(&pack, PACK_IDX, GIT_OID_SHA1));
+	git_array_clear(ids);
+	cl_git_pass(git_pack_foreach_entry(pack, collect_id, NULL));
+	cl_assert(git_array_size(ids) > 0);
+}
+
+static void close_pack(void)
+{
+	git_mwindow_put_pack(pack);
+	pack = NULL;
+}
+
+static void read_all(void)
+{
+	size_t i;
+
+	for (i = 0; i < git_array_size(ids); i++) {
+		struct git_pack_entry e;
+		git_rawobj raw;
+
+		cl_git_pass(git_pack_entry_find(&e, pack, git_array_get(ids, i), GIT_OID_SHA1_HEXSIZE));
+		cl_git_pass(git_packfile_unpack(&raw, pack, &e.offset));
+		git__free(raw.data);
+	}
+}
+
+/*
+ * Every entry in the map is on the LRU list once, no entry is still in
+ * use, and the cache counts exactly the memory its entries hold.
+ */
+static void assert_cache_consistent(git_pack_cache *cache)
+{
+	git_pack_cache_entry *e, *prev = NULL;
+	size_t count = 0, used = 0;
+
+	for (e = cache->head; e; prev = e, e = e->next) {
+		cl_assert(e->prev == prev);
+		cl_assert_equal_i(0, git_atomic32_get(&e->refcount));
+		used += e->raw.len;
+		count++;
+	}
+
+	cl_assert(cache->tail == prev);
+	cl_assert_equal_sz(cache->entries.size, count);
+	cl_assert_equal_sz(cache->memory_used, used);
+	cl_assert(cache->memory_used <= cache->memory_limit);
+}
+
+void test_pack_cache__holds_bases(void)
+{
+	open_pack();
+	read_all();
+
+	cl_assert(pack->bases.memory_used > 0);
+	assert_cache_consistent(&pack->bases);
+}
+
+void test_pack_cache__evicts_to_stay_within_limit(void)
+{
+	size_t unlimited;
+
+	/* how much the cache holds when nothing has to be evicted */
+	open_pack();
+	read_all();
+	unlimited = pack->bases.memory_used;
+	close_pack();
+
+	/* half of that can only be kept by evicting */
+	open_pack();
+	pack->bases.memory_limit = unlimited / 2;
+	read_all();
+	read_all();
+
+	cl_assert(pack->bases.memory_used > 0);
+	assert_cache_consistent(&pack->bases);
+}