git/list[1] front-page[2] threads[3] people[4] search[5] about
 

[PATCH 2/8] packfile: move the MRU list into the packfile store

From
Patrick Steinhardt <ps@pks.im>
Date
Oct 28, 2025, 11:08 UTC
Message-ID
<20251028-pks-packfiles-store-drop-list-v1-2-1a3b82030a7a@pks.im>
In-Reply-To
<20251028-pks-packfiles-store-drop-list-v1-0-1a3b82030a7a@pks.im>
Packfiles have two lists associated to them:
  - A list that keeps track of packfiles in the order that they were
    added to a packfile store.
  - A list that keeps track of packfiles in most-recently-used order so
    that packfiles that are more likely to contain a specific object are
    ordered towards the front.

Both of these lists are hosted by `struct packed_git` itself, So to identify all packfiles in a repository you simply need to grab the first packfile and then iterate the `->next` pointers or the MRU list. This pattern has the problem that all packfiles are part of the same list, regardless of whether or not they belong to the same object source.

With the upcoming pluggable object database effort this needs to change: packfiles should be contained by a single object source, and reading an object from any such packfile should use that source to look up the object. Consequently, we need to break up the global lists of packfiles into per-object-source lists.

A first step towards this goal is to move those lists ouf of `struct packed_git` and into the packfile store. While the packfile store is currently sitting on the `struct object_database` level, the intent is to push it down one level into the `struct odb_source` in a subsequent patch series.

Introduce a new `struct packfile_list` that is used to manage lists of packfiles and use it to store the list of most-recently-used packfiles in `struct packfile_store`. For now, the new list type is only used in a single spot, but we'll expand its usage in subsequent patches.

Signed-off-by: Patrick Steinhardt <ps@pks.im>
---
 builtin/pack-objects.c |  9 +++--
 midx.c                 |  2 +-
 packfile.c             | 92 +++++++++++++++++++++++++++++++++++++++++++++-----
 packfile.h             | 19 +++++++++--
 4 files changed, 104 insertions(+), 18 deletions(-)
diff --git a/builtin/pack-objects.c b/builtin/pack-objects.c
index b5454e5df13..5348aebbe9f 100644
--- a/builtin/pack-objects.c
+++ b/builtin/pack-objects.c
@@ -1706,8 +1706,8 @@ static int want_object_in_pack_mtime(const struct object_id *oid,
 				     uint32_t found_mtime)
 {
 	int want;
+	struct packfile_list_entry *e;
 	struct odb_source *source;
-	struct list_head *pos;
 
 	if (!exclude && local) {
 		/*
@@ -1748,12 +1748,11 @@ static int want_object_in_pack_mtime(const struct object_id *oid,
 		}
 	}
 
-	list_for_each(pos, packfile_store_get_packs_mru(the_repository->objects->packfiles)) {
-		struct packed_git *p = list_entry(pos, struct packed_git, mru);
+	for (e = the_repository->objects->packfiles->mru.head; e; e = e->next) {
+		struct packed_git *p = e->pack;
 		want = want_object_in_pack_one(p, oid, exclude, found_pack, found_offset, found_mtime);
 		if (!exclude && want > 0)
-			list_move(&p->mru,
-				  packfile_store_get_packs_mru(the_repository->objects->packfiles));
+			packfile_list_prepend(&the_repository->objects->packfiles->mru, p);
 		if (want != -1)
 			return want;
 	}
diff --git a/midx.c b/midx.c
index 1d6269f957e..8022be9a45e 100644
--- a/midx.c
+++ b/midx.c
@@ -463,7 +463,7 @@ int prepare_midx_pack(struct multi_pack_index *m,
 	p = packfile_store_load_pack(r->objects->packfiles,
 				     pack_name.buf, m->source->local);
 	if (p)
-		list_add_tail(&p->mru, &r->objects->packfiles->mru);
+		packfile_list_append(&m->source->odb->packfiles->mru, p);
 	strbuf_release(&pack_name);
 
 	if (!p) {
diff --git a/packfile.c b/packfile.c
index 04649e52920..4d2d3b674f3 100644
--- a/packfile.c
+++ b/packfile.c
@@ -47,6 +47,80 @@ static size_t pack_mapped;
 #define SZ_FMT PRIuMAX
 static inline uintmax_t sz_fmt(size_t s) { return s; }
 
+void packfile_list_clear(struct packfile_list *list)
+{
+	struct packfile_list_entry *e, *next;
+
+	for (e = list->head; e; e = next) {
+		next = e->next;
+		free(e);
+	}
+
+	list->head = list->tail = NULL;
+}
+
+static struct packfile_list_entry *packfile_list_remove_internal(struct packfile_list *list,
+								 struct packed_git *pack)
+{
+	struct packfile_list_entry *e, *prev;
+
+	for (e = list->head, prev = NULL; e; prev = e, e = e->next) {
+		if (e->pack != pack)
+			continue;
+
+		if (prev)
+			prev->next = e->next;
+		if (list->head == e)
+			list->head = e->next;
+		if (list->tail == e)
+			list->tail = prev;
+
+		return e;
+	}
+
+	return NULL;
+}
+
+void packfile_list_remove(struct packfile_list *list, struct packed_git *pack)
+{
+	free(packfile_list_remove_internal(list, pack));
+}
+
+void packfile_list_prepend(struct packfile_list *list, struct packed_git *pack)
+{
+	struct packfile_list_entry *entry;
+
+	entry = packfile_list_remove_internal(list, pack);
+	if (!entry) {
+		entry = xmalloc(sizeof(*entry));
+		entry->pack = pack;
+	}
+	entry->next = list->head;
+
+	list->head = entry;
+	if (!list->tail)
+		list->tail = entry;
+}
+
+void packfile_list_append(struct packfile_list *list, struct packed_git *pack)
+{
+	struct packfile_list_entry *entry;
+
+	entry = packfile_list_remove_internal(list, pack);
+	if (!entry) {
+		entry = xmalloc(sizeof(*entry));
+		entry->pack = pack;
+	}
+	entry->next = NULL;
+
+	if (list->tail) {
+		list->tail->next = entry;
+		list->tail = entry;
+	} else {
+		list->head = list->tail = entry;
+	}
+}
+
 void pack_report(struct repository *repo)
 {
 	fprintf(stderr,
@@ -995,10 +1069,10 @@ static void packfile_store_prepare_mru(struct packfile_store *store)
 {
 	struct packed_git *p;
 
-	INIT_LIST_HEAD(&store->mru);
+	packfile_list_clear(&store->mru);
 
 	for (p = store->packs; p; p = p->next)
-		list_add_tail(&p->mru, &store->mru);
+		packfile_list_append(&store->mru, p);
 }
 
 void packfile_store_prepare(struct packfile_store *store)
@@ -1040,10 +1114,10 @@ struct packed_git *packfile_store_get_packs(struct packfile_store *store)
 	return store->packs;
 }
 
-struct list_head *packfile_store_get_packs_mru(struct packfile_store *store)
+struct packfile_list_entry *packfile_store_get_packs_mru(struct packfile_store *store)
 {
 	packfile_store_prepare(store);
-	return &store->mru;
+	return store->mru.head;
 }
 
 /*
@@ -2048,7 +2122,7 @@ static int fill_pack_entry(const struct object_id *oid,
 
 int find_pack_entry(struct repository *r, const struct object_id *oid, struct pack_entry *e)
 {
-	struct list_head *pos;
+	struct packfile_list_entry *l;
 
 	packfile_store_prepare(r->objects->packfiles);
 
@@ -2059,10 +2133,11 @@ int find_pack_entry(struct repository *r, const struct object_id *oid, struct pa
 	if (!r->objects->packfiles->packs)
 		return 0;
 
-	list_for_each(pos, &r->objects->packfiles->mru) {
-		struct packed_git *p = list_entry(pos, struct packed_git, mru);
+	for (l = r->objects->packfiles->mru.head; l; l = l->next) {
+		struct packed_git *p = l->pack;
+
 		if (!p->multi_pack_index && fill_pack_entry(oid, e, p)) {
-			list_move(&p->mru, &r->objects->packfiles->mru);
+			packfile_list_prepend(&r->objects->packfiles->mru, p);
 			return 1;
 		}
 	}
@@ -2314,7 +2389,6 @@ struct packfile_store *packfile_store_new(struct object_database *odb)
 	struct packfile_store *store;
 	CALLOC_ARRAY(store, 1);
 	store->odb = odb;
-	INIT_LIST_HEAD(&store->mru);
 	strmap_init(&store->packs_by_path);
 	return store;
 }
diff --git a/packfile.h b/packfile.h
index 9da7f14317b..39ed1073e4a 100644
--- a/packfile.h
+++ b/packfile.h
@@ -12,7 +12,6 @@ struct object_info;
 
 struct packed_git {
 	struct packed_git *next;
-	struct list_head mru;
 	struct pack_window *windows;
 	off_t pack_size;
 	const void *index_data;
@@ -52,6 +51,20 @@ struct packed_git {
 	char pack_name[FLEX_ARRAY]; /* more */
 };
 
+struct packfile_list {
+	struct packfile_list_entry *head, *tail;
+};
+
+struct packfile_list_entry {
+	struct packfile_list_entry *next;
+	struct packed_git *pack;
+};
+
+void packfile_list_clear(struct packfile_list *list);
+void packfile_list_remove(struct packfile_list *list, struct packed_git *pack);
+void packfile_list_prepend(struct packfile_list *list, struct packed_git *pack);
+void packfile_list_append(struct packfile_list *list, struct packed_git *pack);
+
 /*
  * A store that manages packfiles for a given object database.
  */
@@ -79,7 +92,7 @@ struct packfile_store {
 	} kept_cache;
 
 	/* A most-recently-used ordered version of the packs list. */
-	struct list_head mru;
+	struct packfile_list mru;
 
 	/*
 	 * A map of packfile names to packed_git structs for tracking which
@@ -153,7 +166,7 @@ struct packed_git *packfile_store_get_packs(struct packfile_store *store);
 /*
  * Get all packs in most-recently-used order.
  */
-struct list_head *packfile_store_get_packs_mru(struct packfile_store *store);
+struct packfile_list_entry *packfile_store_get_packs_mru(struct packfile_store *store);
 
 /*
  * Open the packfile and add it to the store if it isn't yet known. Returns

-- 
2.51.2.997.g839fc31de9.dirty
Previous: Taylor BlauNext: Taylor Blau
Message 4 of 34 in “packfiles: track pack lists via the packfile store”
  1. 0/8 packfiles: track pack lists via the packfile storePatrick Steinhardt, Oct 28, 2025
  2. 1/8 packfile: use a `strmap` to store packs by namePatrick Steinhardt, Oct 28, 2025
  3. Taylor BlauOct 29, 2025
  4. 2/8 packfile: move the MRU list into the packfile storePatrick Steinhardt, Oct 28, 2025
  5. Taylor BlauOct 29, 2025
  6. Patrick SteinhardtOct 30, 2025
  7. 3/8 http: refactor subsystem to use `packfile_list`sPatrick Steinhardt, Oct 28, 2025
  8. Toon ClaesOct 29, 2025
  9. Patrick SteinhardtOct 30, 2025
  10. 4/8 packfile: fix approximation of object countsPatrick Steinhardt, Oct 28, 2025
  11. Taylor BlauOct 29, 2025
  12. Patrick SteinhardtOct 30, 2025
  13. 5/8 builtin/pack-objects: simplify logic to find kept or nonlocal objectsPatrick Steinhardt, Oct 28, 2025
  14. Toon ClaesOct 29, 2025
  15. Taylor BlauOct 29, 2025
  16. Patrick SteinhardtOct 30, 2025
  17. Taylor BlauOct 29, 2025
  18. Patrick SteinhardtOct 30, 2025
  19. Toon ClaesOct 30, 2025
  20. Patrick SteinhardtOct 30, 2025
  21. 6/8 packfile: move list of packs into the packfile storePatrick Steinhardt, Oct 28, 2025
  22. 7/8 packfile: always add packfiles to MRU when adding a packPatrick Steinhardt, Oct 28, 2025
  23. Taylor BlauOct 29, 2025
  24. Patrick SteinhardtOct 30, 2025
  25. 8/8 packfile: track packs via the MRU list exclusivelyPatrick Steinhardt, Oct 28, 2025
  26. 0/8 packfiles: track pack lists via the packfile storePatrick Steinhardt, Oct 30, 2025
  27. 1/8 packfile: use a `strmap` to store packs by namePatrick Steinhardt, Oct 30, 2025
  28. 2/8 packfile: move the MRU list into the packfile storePatrick Steinhardt, Oct 30, 2025
  29. 3/8 http: refactor subsystem to use `packfile_list`sPatrick Steinhardt, Oct 30, 2025
  30. 4/8 packfile: fix approximation of object countsPatrick Steinhardt, Oct 30, 2025
  31. 5/8 builtin/pack-objects: simplify logic to find kept or nonlocal objectsPatrick Steinhardt, Oct 30, 2025
  32. 6/8 packfile: move list of packs into the packfile storePatrick Steinhardt, Oct 30, 2025
  33. 7/8 packfile: always add packfiles to MRU when adding a packPatrick Steinhardt, Oct 30, 2025
  34. 8/8 packfile: track packs via the MRU list exclusivelyPatrick Steinhardt, Oct 30, 2025

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.