{"thread":{"id":"54154","subject":"[PATCH] midx: traverse the local MIDX first","startedAt":"2020-08-28T18:06:34Z","lastAt":"2020-08-28T21:19:34Z","messageCount":10,"participants":["Taylor Blau","Derrick Stolee","Jeff King"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"404714","messageId":"20200828180621.GA9036@nand.nand.local","threadId":"54154","inReplyTo":null,"subject":"[PATCH] midx: traverse the local MIDX first","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2020-08-28T18:06:21Z","receivedAt":"2020-08-28T18:06:34Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"When a repository has an alternate object directory configured, callers\ncan traverse through each alternate's MIDX by walking the '->next'\npointer.\n\nBut, when 'prepare_multi_pack_index_one()' loads multiple MIDXs, it\nplaces the new ones at the front of this pointer chain, not at the end.\nThis can be confusing for callers such as 'git repack -ad', causing test\nfailures like in t7700.6 with 'GIT_TEST_MULTI_PACK_INDEX=1'.\n\nThe occurs when dropping a pack known to the local MIDX with alternates\nconfigured that have their own MIDX. Since the alternate's MIDX is\nreturned via 'get_multi_pack_index()', 'midx_contains_pack()' returns\ntrue (which is correct, since it traverses through the '->next' pointer\nto find the MIDX in the chain that does contain the requested object).\nBut, we call 'clear_midx_file()' on 'the_repository', which drops the\nMIDX at the path of the first MIDX in the chain, which (in the case of\nt7700.6 is the one in the alternate).\n\nThis patch bandaids that situation by trying to place the local MIDX\nfirst in the chain when calling 'prepare_multi_pack_index_one()'.\nSpecifically, it always inserts all MIDXs loads subsequent to the local\none as the head of the tail of the MIDX chain. This makes it so that we\ndon't have a quadratic insertion while still keeping the local MIDX at\nthe front of the list. Likewise, it avoids an 'O(m*n)' lookup in\n'remove_redundant_pack()' where 'm' is the number of redundant packs and\n'n' is the number of alternates.\n\nProtect 'remove_redundant_pack()' against a case where alternates with\nMIDXs exist, but no local MIDX exists by first checking that 'm->local'\nbefore asking whether or not it contains the requested pack.\n\nThis invariant is only preserved by the insertion order in\n'prepare_packed_git()', which traverses through the ODB's '->next'\npointer, meaning we visit the local object store first. This fragility\nmakes this an undesirable long-term solution, but it is acceptable for\nnow since this is the only caller.\n\nSigned-off-by: Taylor Blau <me@ttaylorr.com>\n---\nThis is kind of a hack, but the order that we call\n'prepare_multi_pack_index_one()' from 'prepare_packed_git()' makes it\nacceptable, at least in my own assessment.\n\nIt is fixing a breakage in 'next', so I'd be inclined to merge this up.\nBut, if this is too gross, I'd just as soon revert what's in 'next' and\ntry again later.\n\n builtin/repack.c | 2 +-\n midx.c           | 8 ++++++--\n 2 files changed, 7 insertions(+), 3 deletions(-)\n\ndiff --git a/builtin/repack.c b/builtin/repack.c\nindex 98fac03946..5661d69c16 100644\n--- a/builtin/repack.c\n+++ b/builtin/repack.c\n@@ -135,7 +135,7 @@ static void remove_redundant_pack(const char *dir_name, const char *base_name)\n \tstruct strbuf buf = STRBUF_INIT;\n \tstruct multi_pack_index *m = get_multi_pack_index(the_repository);\n \tstrbuf_addf(&buf, \"%s.pack\", base_name);\n-\tif (m && midx_contains_pack(m, buf.buf))\n+\tif (m && m->local && midx_contains_pack(m, buf.buf))\n \t\tclear_midx_file(the_repository);\n \tstrbuf_insertf(&buf, 0, \"%s/\", dir_name);\n \tunlink_pack_path(buf.buf, 1);\ndiff --git a/midx.c b/midx.c\nindex e9b2e1253a..cc19b66152 100644\n--- a/midx.c\n+++ b/midx.c\n@@ -416,8 +416,12 @@ int prepare_multi_pack_index_one(struct repository *r, const char *object_dir, i\n \tm = load_multi_pack_index(object_dir, local);\n\n \tif (m) {\n-\t\tm->next = r->objects->multi_pack_index;\n-\t\tr->objects->multi_pack_index = m;\n+\t\tstruct multi_pack_index *mp = r->objects->multi_pack_index;\n+\t\tif (mp) {\n+\t\t\tm->next = mp->next;\n+\t\t\tmp->next = m;\n+\t\t} else\n+\t\t\tr->objects->multi_pack_index = m;\n \t\treturn 1;\n \t}\n\n--\n2.28.0.338.g87a3b7a5a2.dirty\n"},{"id":"404716","messageId":"9a599bb5-fb6f-1e35-6e02-d62703ebc420@gmail.com","threadId":"54154","inReplyTo":"20200828180621.GA9036@nand.nand.local","subject":"Re: [PATCH] midx: traverse the local MIDX first","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2020-08-28T18:27:53Z","receivedAt":"2020-08-28T18:27:58Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 8/28/2020 2:06 PM, Taylor Blau wrote:\n> This invariant is only preserved by the insertion order in\n> 'prepare_packed_git()', which traverses through the ODB's '->next'\n> pointer, meaning we visit the local object store first. This fragility\n> makes this an undesirable long-term solution, but it is acceptable for\n> now since this is the only caller.\n> \n> Signed-off-by: Taylor Blau <me@ttaylorr.com>\n> ---\n> This is kind of a hack, but the order that we call\n> 'prepare_multi_pack_index_one()' from 'prepare_packed_git()' makes it\n> acceptable, at least in my own assessment.\n\nThe natural alternative would be to scan the list _after_ all are\ninserted and pull any MIDX marked \"local\" to the front of the list.\nSuch a check would need to happen in the same method that iterates\nover all alternates, so that seems a bit redundant.\n\nWhile perhaps a bit hack-ish, I think this is a sound approach.\nAnd, we have a test that will detect change in behavior here!\n\nThanks,\n-Stolee\n\n"},{"id":"404718","messageId":"20200828185039.GA2171353@coredump.intra.peff.net","threadId":"54154","inReplyTo":"20200828180621.GA9036@nand.nand.local","subject":"Re: [PATCH] midx: traverse the local MIDX first","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-08-28T18:50:39Z","receivedAt":"2020-08-28T18:50:44Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Aug 28, 2020 at 02:06:21PM -0400, Taylor Blau wrote:\n\n> The occurs when dropping a pack known to the local MIDX with alternates\n> configured that have their own MIDX. Since the alternate's MIDX is\n> returned via 'get_multi_pack_index()', 'midx_contains_pack()' returns\n> true (which is correct, since it traverses through the '->next' pointer\n> to find the MIDX in the chain that does contain the requested object).\n> But, we call 'clear_midx_file()' on 'the_repository', which drops the\n> MIDX at the path of the first MIDX in the chain, which (in the case of\n> t7700.6 is the one in the alternate).\n\nOK, that makes sense for what we're seeing.\n\n> This patch bandaids that situation by trying to place the local MIDX\n> first in the chain when calling 'prepare_multi_pack_index_one()'.\n> Specifically, it always inserts all MIDXs loads subsequent to the local\n> one as the head of the tail of the MIDX chain. This makes it so that we\n> don't have a quadratic insertion while still keeping the local MIDX at\n> the front of the list. Likewise, it avoids an 'O(m*n)' lookup in\n> 'remove_redundant_pack()' where 'm' is the number of redundant packs and\n> 'n' is the number of alternates.\n> \n> Protect 'remove_redundant_pack()' against a case where alternates with\n> MIDXs exist, but no local MIDX exists by first checking that 'm->local'\n> before asking whether or not it contains the requested pack.\n\nIt seems like the root of the problem is that get_multi_pack_index() is\nbeing used for two different things:\n\n  - most callers want to iterate over all of the possible midx files,\n    because they're trying to look up an object.\n\n  - this caller wants the single midx for the local repository (I\n    wondered if there might be more of these that we just never noticed\n    because the test suite doesn't use alternates, but having just\n    audited them all, the answer is no).\n\nSo I'd be tempted to say that the latter callers should be using a\nseparate function that gives them what they want. That lets them avoid\nbeing too intimate with the details of how we order things.\n\nThe patch below illustrates that.  It also changes the existing function\nname to avoid confusion and to help audit the existing callers, but\nthat's optional and maybe not worth it.\n\nIt does do the linear lookup, so it has the O(m*n) you mentioned. But\nthe number of alternates is generally small, and I'd be shocked if this\nwas the first m*n loop over the number of alternates. However, we could\nstill do the ordering thing and just keep the details inside the new\nfunction.\n\n---\ndiff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\nindex 7016b28485..a9be7480df 100644\n--- a/builtin/pack-objects.c\n+++ b/builtin/pack-objects.c\n@@ -1246,7 +1246,7 @@ static int want_object_in_pack(const struct object_id *oid,\n \t\t\treturn want;\n \t}\n \n-\tfor (m = get_multi_pack_index(the_repository); m; m = m->next) {\n+\tfor (m = get_all_multi_pack_index(the_repository); m; m = m->next) {\n \t\tstruct pack_entry e;\n \t\tif (fill_midx_entry(the_repository, oid, &e, m)) {\n \t\t\tstruct packed_git *p = e.p;\ndiff --git a/builtin/repack.c b/builtin/repack.c\nindex f10f52779c..60cb196956 100644\n--- a/builtin/repack.c\n+++ b/builtin/repack.c\n@@ -133,7 +133,7 @@ static void get_non_kept_pack_filenames(struct string_list *fname_list,\n static void remove_redundant_pack(const char *dir_name, const char *base_name)\n {\n \tstruct strbuf buf = STRBUF_INIT;\n-\tstruct multi_pack_index *m = get_multi_pack_index(the_repository);\n+\tstruct multi_pack_index *m = get_local_multi_pack_index(the_repository);\n \tstrbuf_addf(&buf, \"%s.pack\", base_name);\n \tif (m && midx_contains_pack(m, buf.buf))\n \t\tclear_midx_file(the_repository);\ndiff --git a/packfile.c b/packfile.c\nindex 6ab5233613..ece317642a 100644\n--- a/packfile.c\n+++ b/packfile.c\n@@ -915,7 +915,7 @@ unsigned long repo_approximate_object_count(struct repository *r)\n \n \t\tprepare_packed_git(r);\n \t\tcount = 0;\n-\t\tfor (m = get_multi_pack_index(r); m; m = m->next)\n+\t\tfor (m = get_all_multi_pack_index(r); m; m = m->next)\n \t\t\tcount += m->num_objects;\n \t\tfor (p = r->objects->packed_git; p; p = p->next) {\n \t\t\tif (open_pack_index(p))\n@@ -1021,12 +1021,24 @@ struct packed_git *get_packed_git(struct repository *r)\n \treturn r->objects->packed_git;\n }\n \n-struct multi_pack_index *get_multi_pack_index(struct repository *r)\n+struct multi_pack_index *get_all_multi_pack_index(struct repository *r)\n {\n \tprepare_packed_git(r);\n \treturn r->objects->multi_pack_index;\n }\n \n+struct multi_pack_index *get_local_multi_pack_index(struct repository *r)\n+{\n+\tstruct multi_pack_index *m;\n+\n+\tfor (m = get_all_multi_pack_index(r); m; m = m->next) {\n+\t\tif (m->local)\n+\t\t\tbreak;\n+\t}\n+\n+\treturn m;\n+}\n+\n struct packed_git *get_all_packs(struct repository *r)\n {\n \tstruct multi_pack_index *m;\ndiff --git a/packfile.h b/packfile.h\nindex 240aa73b95..2516eb4667 100644\n--- a/packfile.h\n+++ b/packfile.h\n@@ -56,7 +56,8 @@ void install_packed_git(struct repository *r, struct packed_git *pack);\n \n struct packed_git *get_packed_git(struct repository *r);\n struct list_head *get_packed_git_mru(struct repository *r);\n-struct multi_pack_index *get_multi_pack_index(struct repository *r);\n+struct multi_pack_index *get_all_multi_pack_index(struct repository *r);\n+struct multi_pack_index *get_local_multi_pack_index(struct repository *r);\n struct packed_git *get_all_packs(struct repository *r);\n \n /*\ndiff --git a/sha1-name.c b/sha1-name.c\nindex 0b8cb5247a..be6b675953 100644\n--- a/sha1-name.c\n+++ b/sha1-name.c\n@@ -184,7 +184,7 @@ static void find_short_packed_object(struct disambiguate_state *ds)\n \tstruct multi_pack_index *m;\n \tstruct packed_git *p;\n \n-\tfor (m = get_multi_pack_index(ds->repo); m && !ds->ambiguous;\n+\tfor (m = get_all_multi_pack_index(ds->repo); m && !ds->ambiguous;\n \t     m = m->next)\n \t\tunique_in_midx(m, ds);\n \tfor (p = get_packed_git(ds->repo); p && !ds->ambiguous;\n@@ -660,7 +660,7 @@ static void find_abbrev_len_packed(struct min_abbrev_data *mad)\n \tstruct multi_pack_index *m;\n \tstruct packed_git *p;\n \n-\tfor (m = get_multi_pack_index(mad->repo); m; m = m->next)\n+\tfor (m = get_all_multi_pack_index(mad->repo); m; m = m->next)\n \t\tfind_abbrev_len_for_midx(m, mad);\n \tfor (p = get_packed_git(mad->repo); p; p = p->next)\n \t\tfind_abbrev_len_for_pack(p, mad);\n"},{"id":"404719","messageId":"20200828185531.GB2171353@coredump.intra.peff.net","threadId":"54154","inReplyTo":"20200828185039.GA2171353@coredump.intra.peff.net","subject":"Re: [PATCH] midx: traverse the local MIDX first","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-08-28T18:55:31Z","receivedAt":"2020-08-28T18:55:33Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Aug 28, 2020 at 02:50:39PM -0400, Jeff King wrote:\n\n> So I'd be tempted to say that the latter callers should be using a\n> separate function that gives them what they want. That lets them avoid\n> being too intimate with the details of how we order things.\n> \n> The patch below illustrates that.  It also changes the existing function\n> name to avoid confusion and to help audit the existing callers, but\n> that's optional and maybe not worth it.\n\nAnd here's the same concept as a more minimal change, suitable for\nsquashing into yours. The advantage is that it keeps the \"the local one\ngoes first\" logic in one abstracted spot.\n\ndiff --git a/builtin/repack.c b/builtin/repack.c\nindex 28b0c1bf1b..60cb196956 100644\n--- a/builtin/repack.c\n+++ b/builtin/repack.c\n@@ -133,9 +133,9 @@ static void get_non_kept_pack_filenames(struct string_list *fname_list,\n static void remove_redundant_pack(const char *dir_name, const char *base_name)\n {\n \tstruct strbuf buf = STRBUF_INIT;\n-\tstruct multi_pack_index *m = get_multi_pack_index(the_repository);\n+\tstruct multi_pack_index *m = get_local_multi_pack_index(the_repository);\n \tstrbuf_addf(&buf, \"%s.pack\", base_name);\n-\tif (m && m->local && midx_contains_pack(m, buf.buf))\n+\tif (m && midx_contains_pack(m, buf.buf))\n \t\tclear_midx_file(the_repository);\n \tstrbuf_insertf(&buf, 0, \"%s/\", dir_name);\n \tunlink_pack_path(buf.buf, 1);\ndiff --git a/packfile.c b/packfile.c\nindex 6ab5233613..9ef27508f2 100644\n--- a/packfile.c\n+++ b/packfile.c\n@@ -1027,6 +1027,17 @@ struct multi_pack_index *get_multi_pack_index(struct repository *r)\n \treturn r->objects->multi_pack_index;\n }\n \n+struct multi_pack_index *get_local_multi_pack_index(struct repository *r)\n+{\n+\tstruct multi_pack_index *m = get_multi_pack_index(r);\n+\n+\t/* no need to iterate; we always put the local one first (if any) */\n+\tif (m && m->local)\n+\t\treturn m;\n+\n+\treturn NULL;\n+}\n+\n struct packed_git *get_all_packs(struct repository *r)\n {\n \tstruct multi_pack_index *m;\ndiff --git a/packfile.h b/packfile.h\nindex 240aa73b95..a58fc738e0 100644\n--- a/packfile.h\n+++ b/packfile.h\n@@ -57,6 +57,7 @@ void install_packed_git(struct repository *r, struct packed_git *pack);\n struct packed_git *get_packed_git(struct repository *r);\n struct list_head *get_packed_git_mru(struct repository *r);\n struct multi_pack_index *get_multi_pack_index(struct repository *r);\n+struct multi_pack_index *get_local_multi_pack_index(struct repository *r);\n struct packed_git *get_all_packs(struct repository *r);\n \n /*\n"},{"id":"404720","messageId":"20200828185557.GC19328@nand.nand.local","threadId":"54154","inReplyTo":"20200828185039.GA2171353@coredump.intra.peff.net","subject":"Re: [PATCH] midx: traverse the local MIDX first","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2020-08-28T18:55:57Z","receivedAt":"2020-08-28T18:56:09Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Fri, Aug 28, 2020 at 02:50:39PM -0400, Jeff King wrote:\n> On Fri, Aug 28, 2020 at 02:06:21PM -0400, Taylor Blau wrote:\n> [ snip ]\n>\n> > This patch bandaids that situation by trying to place the local MIDX\n> > first in the chain when calling 'prepare_multi_pack_index_one()'.\n> > Specifically, it always inserts all MIDXs loads subsequent to the local\n> > one as the head of the tail of the MIDX chain. This makes it so that we\n> > don't have a quadratic insertion while still keeping the local MIDX at\n> > the front of the list. Likewise, it avoids an 'O(m*n)' lookup in\n> > 'remove_redundant_pack()' where 'm' is the number of redundant packs and\n> > 'n' is the number of alternates.\n> >\n> > Protect 'remove_redundant_pack()' against a case where alternates with\n> > MIDXs exist, but no local MIDX exists by first checking that 'm->local'\n> > before asking whether or not it contains the requested pack.\n>\n> It seems like the root of the problem is that get_multi_pack_index() is\n> being used for two different things:\n>\n>   - most callers want to iterate over all of the possible midx files,\n>     because they're trying to look up an object.\n>\n>   - this caller wants the single midx for the local repository (I\n>     wondered if there might be more of these that we just never noticed\n>     because the test suite doesn't use alternates, but having just\n>     audited them all, the answer is no).\n>\n> So I'd be tempted to say that the latter callers should be using a\n> separate function that gives them what they want. That lets them avoid\n> being too intimate with the details of how we order things.\n>\n> The patch below illustrates that.  It also changes the existing function\n> name to avoid confusion and to help audit the existing callers, but\n> that's optional and maybe not worth it.\n>\n> It does do the linear lookup, so it has the O(m*n) you mentioned. But\n> the number of alternates is generally small, and I'd be shocked if this\n> was the first m*n loop over the number of alternates. However, we could\n> still do the ordering thing and just keep the details inside the new\n> function.\n\nI'd be much happier with this patch.\n\nIf you wanted to go further, we could do both, and tighten up the\ninsertion code to make sure that the local MIDX is always first from the\nperspective of 'r->objects->multi_pack_index' so that the linear lookup\ndrops to constant.\n\nBut, it might be overkill, since I also tend to think that the number of\nalternates is small, and we're not even talking about a difference of\nmilliseconds here.\n\nSo, I'm happy to clean it up for you and forge your sign-off with\npermission, or otherwise you're welcome to do so, too.\n\nThanks,\nTaylor\n"},{"id":"404721","messageId":"80ba7515-dc6c-3acd-4b53-c60cbdab1633@gmail.com","threadId":"54154","inReplyTo":"20200828185531.GB2171353@coredump.intra.peff.net","subject":"Re: [PATCH] midx: traverse the local MIDX first","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2020-08-28T19:03:09Z","receivedAt":"2020-08-28T19:03:14Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 8/28/2020 2:55 PM, Jeff King wrote:\n> On Fri, Aug 28, 2020 at 02:50:39PM -0400, Jeff King wrote:\n> \n>> So I'd be tempted to say that the latter callers should be using a\n>> separate function that gives them what they want. That lets them avoid\n>> being too intimate with the details of how we order things.\n>>\n>> The patch below illustrates that.  It also changes the existing function\n>> name to avoid confusion and to help audit the existing callers, but\n>> that's optional and maybe not worth it.\n> \n> And here's the same concept as a more minimal change, suitable for\n> squashing into yours. The advantage is that it keeps the \"the local one\n> goes first\" logic in one abstracted spot.\n\nThis is nice because it is more future-proof: if we needed to\nchange the order of the midx list, then we could update the\nimplementation of this method instead of every caller.\n\nPersonally, I prefer this one (squashed).\n\nThanks,\n-Stolee\n"},{"id":"404722","messageId":"20200828190752.GD19328@nand.nand.local","threadId":"54154","inReplyTo":"80ba7515-dc6c-3acd-4b53-c60cbdab1633@gmail.com","subject":"Re: [PATCH] midx: traverse the local MIDX first","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2020-08-28T19:07:52Z","receivedAt":"2020-08-28T19:08:00Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Fri, Aug 28, 2020 at 03:03:09PM -0400, Derrick Stolee wrote:\n> On 8/28/2020 2:55 PM, Jeff King wrote:\n> > On Fri, Aug 28, 2020 at 02:50:39PM -0400, Jeff King wrote:\n> >\n> >> So I'd be tempted to say that the latter callers should be using a\n> >> separate function that gives them what they want. That lets them avoid\n> >> being too intimate with the details of how we order things.\n> >>\n> >> The patch below illustrates that.  It also changes the existing function\n> >> name to avoid confusion and to help audit the existing callers, but\n> >> that's optional and maybe not worth it.\n> >\n> > And here's the same concept as a more minimal change, suitable for\n> > squashing into yours. The advantage is that it keeps the \"the local one\n> > goes first\" logic in one abstracted spot.\n>\n> This is nice because it is more future-proof: if we needed to\n> change the order of the midx list, then we could update the\n> implementation of this method instead of every caller.\n>\n> Personally, I prefer this one (squashed).\n\nDitto. Peff and I crossed emails, so I was talking about tidying up his\nearlier patch before I even had seen the second one.\n\nPeff -- any objections to me squashing this into mine and sending that\nfor queueing?\n\n> Thanks,\n> -Stolee\n\nThanks,\nTaylor\n"},{"id":"404723","messageId":"20200828195128.GA2187386@coredump.intra.peff.net","threadId":"54154","inReplyTo":"20200828190752.GD19328@nand.nand.local","subject":"Re: [PATCH] midx: traverse the local MIDX first","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-08-28T19:51:28Z","receivedAt":"2020-08-28T19:51:33Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Aug 28, 2020 at 03:07:52PM -0400, Taylor Blau wrote:\n\n> Ditto. Peff and I crossed emails, so I was talking about tidying up his\n> earlier patch before I even had seen the second one.\n> \n> Peff -- any objections to me squashing this into mine and sending that\n> for queueing?\n\nNope, please do (and feel free to forge my signoff).\n\n-Peff\n"},{"id":"404725","messageId":"20200828202213.GA24009@nand.local","threadId":"54154","inReplyTo":"20200828180621.GA9036@nand.nand.local","subject":"[PATCH v2] midx: traverse the local MIDX first","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2020-08-28T20:22:13Z","receivedAt":"2020-08-28T20:22:24Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"When a repository has an alternate object directory configured, callers\ncan traverse through each alternate's MIDX by walking the '->next'\npointer.\n\nBut, when 'prepare_multi_pack_index_one()' loads multiple MIDXs, it\nplaces the new ones at the front of this pointer chain, not at the end.\nThis can be confusing for callers such as 'git repack -ad', causing test\nfailures like in t7700.6 with 'GIT_TEST_MULTI_PACK_INDEX=1'.\n\nThe occurs when dropping a pack known to the local MIDX with alternates\nconfigured that have their own MIDX. Since the alternate's MIDX is\nreturned via 'get_multi_pack_index()', 'midx_contains_pack()' returns\ntrue (which is correct, since it traverses through the '->next' pointer\nto find the MIDX in the chain that does contain the requested object).\nBut, we call 'clear_midx_file()' on 'the_repository', which drops the\nMIDX at the path of the first MIDX in the chain, which (in the case of\nt7700.6 is the one in the alternate).\n\nThis patch addresses that by:\n\n  - placing the local MIDX first in the chain when calling\n    'prepare_multi_pack_index_one()', and\n\n  - introducing a new 'get_local_multi_pack_index()', which explicitly\n    returns the repository-local MIDX, if any.\n\nDon't impose an additional order on the MIDX's '->next' pointer beyond\nthat the first item in the chain must be local if one exists so that we\navoid a quadratic insertion.\n\nLikewise, use 'get_local_multi_pack_index()' in\n'remove_redundant_pack()' to fix the formerly broken t7700.6 when run\nwith 'GIT_TEST_MULTI_PACK_INDEX=1'.\n\nFinally, note that the MIDX ordering invariant is only preserved by the\ninsertion order in 'prepare_packed_git()', which traverses through the\nODB's '->next' pointer, meaning we visit the local object store first.\nThis fragility makes this an undesirable long-term solution if more\ncallers are added, but it is acceptable for now since this is the only\ncaller.\n\nHelped-by: Jeff King <peff@peff.net>\nSigned-off-by: Jeff King <peff@peff.net>\nSigned-off-by: Taylor Blau <me@ttaylorr.com>\n---\n builtin/repack.c |  2 +-\n midx.c           |  8 ++++++--\n packfile.c       | 11 +++++++++++\n packfile.h       |  1 +\n 4 files changed, 19 insertions(+), 3 deletions(-)\n\ndiff --git a/builtin/repack.c b/builtin/repack.c\nindex 98fac03946..01e7767c79 100644\n--- a/builtin/repack.c\n+++ b/builtin/repack.c\n@@ -133,7 +133,7 @@ static void get_non_kept_pack_filenames(struct string_list *fname_list,\n static void remove_redundant_pack(const char *dir_name, const char *base_name)\n {\n \tstruct strbuf buf = STRBUF_INIT;\n-\tstruct multi_pack_index *m = get_multi_pack_index(the_repository);\n+\tstruct multi_pack_index *m = get_local_multi_pack_index(the_repository);\n \tstrbuf_addf(&buf, \"%s.pack\", base_name);\n \tif (m && midx_contains_pack(m, buf.buf))\n \t\tclear_midx_file(the_repository);\ndiff --git a/midx.c b/midx.c\nindex e9b2e1253a..cc19b66152 100644\n--- a/midx.c\n+++ b/midx.c\n@@ -416,8 +416,12 @@ int prepare_multi_pack_index_one(struct repository *r, const char *object_dir, i\n \tm = load_multi_pack_index(object_dir, local);\n \n \tif (m) {\n-\t\tm->next = r->objects->multi_pack_index;\n-\t\tr->objects->multi_pack_index = m;\n+\t\tstruct multi_pack_index *mp = r->objects->multi_pack_index;\n+\t\tif (mp) {\n+\t\t\tm->next = mp->next;\n+\t\t\tmp->next = m;\n+\t\t} else\n+\t\t\tr->objects->multi_pack_index = m;\n \t\treturn 1;\n \t}\n \ndiff --git a/packfile.c b/packfile.c\nindex 6ab5233613..9ef27508f2 100644\n--- a/packfile.c\n+++ b/packfile.c\n@@ -1027,6 +1027,17 @@ struct multi_pack_index *get_multi_pack_index(struct repository *r)\n \treturn r->objects->multi_pack_index;\n }\n \n+struct multi_pack_index *get_local_multi_pack_index(struct repository *r)\n+{\n+\tstruct multi_pack_index *m = get_multi_pack_index(r);\n+\n+\t/* no need to iterate; we always put the local one first (if any) */\n+\tif (m && m->local)\n+\t\treturn m;\n+\n+\treturn NULL;\n+}\n+\n struct packed_git *get_all_packs(struct repository *r)\n {\n \tstruct multi_pack_index *m;\ndiff --git a/packfile.h b/packfile.h\nindex 240aa73b95..a58fc738e0 100644\n--- a/packfile.h\n+++ b/packfile.h\n@@ -57,6 +57,7 @@ void install_packed_git(struct repository *r, struct packed_git *pack);\n struct packed_git *get_packed_git(struct repository *r);\n struct list_head *get_packed_git_mru(struct repository *r);\n struct multi_pack_index *get_multi_pack_index(struct repository *r);\n+struct multi_pack_index *get_local_multi_pack_index(struct repository *r);\n struct packed_git *get_all_packs(struct repository *r);\n \n /*\n-- \n2.28.0.338.g87a3b7a5a2.dirty\n"},{"id":"404732","messageId":"20200828211931.GA2190002@coredump.intra.peff.net","threadId":"54154","inReplyTo":"20200828202213.GA24009@nand.local","subject":"Re: [PATCH v2] midx: traverse the local MIDX first","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-08-28T21:19:31Z","receivedAt":"2020-08-28T21:19:34Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Aug 28, 2020 at 04:22:13PM -0400, Taylor Blau wrote:\n\n> This patch addresses that by:\n> \n>   - placing the local MIDX first in the chain when calling\n>     'prepare_multi_pack_index_one()', and\n> \n>   - introducing a new 'get_local_multi_pack_index()', which explicitly\n>     returns the repository-local MIDX, if any.\n> \n> Don't impose an additional order on the MIDX's '->next' pointer beyond\n> that the first item in the chain must be local if one exists so that we\n> avoid a quadratic insertion.\n\nThis version looks fine to me.\n\nThinking on it a bit more, we probably want this \"local one is first\"\nbehavior even without it fixing this bug. For normal packs, we always\nprefer local copies over alternates, under the assumption that\nalternates are likely to be more expensive to access (e.g., shared nfs).\n\nOf course that somewhat goes out the window since we re-order lookups\nthese days based on where we've found previous objects (my mru stuff,\nbut even before that the single \"last pack\" variable). But it makes\nsense to at least start with the local ones being given priority.\n\nI don't think we do any mru tricks with the midx list, so it would stay\nin local-first mode always, which is reasonable (you probably don't have\nso many midx's that any reordering is worth it anyway).\n\nIt does mean we may consult an alternates midx before any local non-midx\npacks, which _could_ be slower. But since this is all guesses and\nheuristics anyway, I'd wait until somebody has a concrete case where\nthey can demonstrate a different ordering scheme works better.\n\n-Peff\n"}]}