[PATCH] midx: traverse the local MIDX first

[Taylor Blau <me@ttaylorr.com>]

When a repository has an alternate object directory configured, callers
can traverse through each alternate's MIDX by walking the '->next'
pointer.

But, when 'prepare_multi_pack_index_one()' loads multiple MIDXs, it
places the new ones at the front of this pointer chain, not at the end.
This can be confusing for callers such as 'git repack -ad', causing test
failures like in t7700.6 with 'GIT_TEST_MULTI_PACK_INDEX=1'.

The occurs when dropping a pack known to the local MIDX with alternates
configured that have their own MIDX. Since the alternate's MIDX is
returned via 'get_multi_pack_index()', 'midx_contains_pack()' returns
true (which is correct, since it traverses through the '->next' pointer
to find the MIDX in the chain that does contain the requested object).
But, we call 'clear_midx_file()' on 'the_repository', which drops the
MIDX at the path of the first MIDX in the chain, which (in the case of
t7700.6 is the one in the alternate).

This patch bandaids that situation by trying to place the local MIDX
first in the chain when calling 'prepare_multi_pack_index_one()'.
Specifically, it always inserts all MIDXs loads subsequent to the local
one as the head of the tail of the MIDX chain. This makes it so that we
don't have a quadratic insertion while still keeping the local MIDX at
the front of the list. Likewise, it avoids an 'O(m*n)' lookup in
'remove_redundant_pack()' where 'm' is the number of redundant packs and
'n' is the number of alternates.

Protect 'remove_redundant_pack()' against a case where alternates with
MIDXs exist, but no local MIDX exists by first checking that 'm->local'
before asking whether or not it contains the requested pack.

This invariant is only preserved by the insertion order in
'prepare_packed_git()', which traverses through the ODB's '->next'
pointer, meaning we visit the local object store first. This fragility
makes this an undesirable long-term solution, but it is acceptable for
now since this is the only caller.

Signed-off-by: Taylor Blau <me@ttaylorr.com>
---
This is kind of a hack, but the order that we call
'prepare_multi_pack_index_one()' from 'prepare_packed_git()' makes it
acceptable, at least in my own assessment.

It is fixing a breakage in 'next', so I'd be inclined to merge this up.
But, if this is too gross, I'd just as soon revert what's in 'next' and
try again later.

 builtin/repack.c | 2 +-
 midx.c           | 8 ++++++--
 2 files changed, 7 insertions(+), 3 deletions(-)

diff --git a/builtin/repack.c b/builtin/repack.c
index 98fac03946..5661d69c16 100644
--- a/builtin/repack.c
+++ b/builtin/repack.c
@@ -135,7 +135,7 @@ static void remove_redundant_pack(const char *dir_name, const char *base_name)
 	struct strbuf buf = STRBUF_INIT;
 	struct multi_pack_index *m = get_multi_pack_index(the_repository);
 	strbuf_addf(&buf, "%s.pack", base_name);
-	if (m && midx_contains_pack(m, buf.buf))
+	if (m && m->local && midx_contains_pack(m, buf.buf))
 		clear_midx_file(the_repository);
 	strbuf_insertf(&buf, 0, "%s/", dir_name);
 	unlink_pack_path(buf.buf, 1);
diff --git a/midx.c b/midx.c
index e9b2e1253a..cc19b66152 100644
--- a/midx.c
+++ b/midx.c
@@ -416,8 +416,12 @@ int prepare_multi_pack_index_one(struct repository *r, const char *object_dir, i
 	m = load_multi_pack_index(object_dir, local);

 	if (m) {
-		m->next = r->objects->multi_pack_index;
-		r->objects->multi_pack_index = m;
+		struct multi_pack_index *mp = r->objects->multi_pack_index;
+		if (mp) {
+			m->next = mp->next;
+			mp->next = m;
+		} else
+			r->objects->multi_pack_index = m;
 		return 1;
 	}

--
2.28.0.338.g87a3b7a5a2.dirty