{"thread":{"id":"55262","subject":"[PATCH 0/5] clean-ups to geometric repacking","startedAt":"2021-03-05T15:22:11Z","lastAt":"2021-03-10T21:01:47Z","messageCount":12,"participants":["Taylor Blau","Junio C Hamano","Jeff King"],"isPatch":true,"patchVersion":1,"patchTotal":5},"messages":[{"id":"418313","messageId":"cover.1614957681.git.me@ttaylorr.com","threadId":"55262","inReplyTo":null,"subject":"[PATCH 0/5] clean-ups to geometric repacking","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2021-03-05T15:21:31Z","receivedAt":"2021-03-05T15:22:11Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"I was reading Junio's comments on my patch to implement a '--geometric' option\nfor 'git repack' here:\n\n    https://lore.kernel.org/git/xmqqv9ahxddp.fsf@gitster.g/\n\nand felt that all of the suggestions therein would make for good clean-up. Since\nthe original series is already on next, this follow-up series is sent separately\n(and can be cleanly applied on top of tb/geometric-repack).\n\nThese are all fairly straightforward clean-ups, although I could do with or\nwithout the fourth patch. It adds a lot of verbosity in exchanged for checking\nunsigned overflows, but I'm not sure how likely it is that we'd run into it. So,\nI would be fine if that patch were dropped.\n\nI applied Junio's sign-off to the last patch, since it was written by him in\nthe above mail, and I merely added a patch message. I hope that that's OK; if it\nisn't, please don't hesitate to drop it (or I can resend it with my authorship\nand sign-off).\n\nJunio C Hamano (1):\n  builtin/repack.c: reword comment around pack-objects flags\n\nTaylor Blau (4):\n  builtin/repack.c: do not repack single packs with --geometric\n  t7703: test --geometric repack with loose objects\n  builtin/repack.c: assign pack split later\n  builtin/repack.c: be more conservative with unsigned overflows\n\n builtin/repack.c            | 46 ++++++++++++++++++++++++++-----------\n t/t7703-repack-geometric.sh | 46 +++++++++++++++++++++++++++++++++++++\n 2 files changed, 79 insertions(+), 13 deletions(-)\n\n-- \n2.30.0.667.g81c0cbc6fd\n"},{"id":"418314","messageId":"80bc7fa8397491d015b80a39168813d2019e262d.1614957681.git.me@ttaylorr.com","threadId":"55262","inReplyTo":"cover.1614957681.git.me@ttaylorr.com","subject":"[PATCH 1/5] builtin/repack.c: do not repack single packs with --geometric","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2021-03-05T15:21:37Z","receivedAt":"2021-03-05T15:22:42Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"In 0fabafd0b9 (builtin/repack.c: add '--geometric' option, 2021-02-22),\nthe 'git repack --geometric' code aborts early when there is zero or one\npack.\n\nWhen there are no packs, this code does the right thing by placing the\nsplit at \"0\". But when there is exactly one pack, the split is placed at\n\"1\", which means that \"git repack --geometric\" (with any factor)\nrepacks all of the objects in a single pack.\n\nThis is wasteful, and the remaining code in split_pack_geometry() does\nthe right thing (not repacking the objects in a single pack) even when\nonly one pack is present.\n\nLoosen the guard to only stop when there aren't any packs, and let the\nrest of the code do the right thing. Add a test to ensure that this is\nthe case.\n\nNoticed-by: Junio C Hamano <gitster@pobox.com>\nSigned-off-by: Taylor Blau <me@ttaylorr.com>\n---\n builtin/repack.c            |  2 +-\n t/t7703-repack-geometric.sh | 15 +++++++++++++++\n 2 files changed, 16 insertions(+), 1 deletion(-)\n\ndiff --git a/builtin/repack.c b/builtin/repack.c\nindex bcf280b10d..4ca2f647b4 100644\n--- a/builtin/repack.c\n+++ b/builtin/repack.c\n@@ -351,7 +351,7 @@ static void split_pack_geometry(struct pack_geometry *geometry, int factor)\n \tuint32_t split;\n \toff_t total_size = 0;\n \n-\tif (geometry->pack_nr <= 1) {\n+\tif (!geometry->pack_nr) {\n \t\tgeometry->split = geometry->pack_nr;\n \t\treturn;\n \t}\ndiff --git a/t/t7703-repack-geometric.sh b/t/t7703-repack-geometric.sh\nindex 96917fc163..4a1952a054 100755\n--- a/t/t7703-repack-geometric.sh\n+++ b/t/t7703-repack-geometric.sh\n@@ -20,6 +20,21 @@ test_expect_success '--geometric with no packs' '\n \t)\n '\n \n+test_expect_success '--geometric with one pack' '\n+\tgit init geometric &&\n+\ttest_when_finished \"rm -fr geometric\" &&\n+\t(\n+\t\tcd geometric &&\n+\n+\t\ttest_commit \"base\" &&\n+\t\tgit repack -d &&\n+\n+\t\tgit repack --geometric 2 >out &&\n+\n+\t\ttest_i18ngrep \"Nothing new to pack\" out\n+\t)\n+'\n+\n test_expect_success '--geometric with an intact progression' '\n \tgit init geometric &&\n \ttest_when_finished \"rm -fr geometric\" &&\n-- \n2.30.0.667.g81c0cbc6fd\n\n"},{"id":"418315","messageId":"ad516e78690913843416b22d184a04fc0362a24d.1614957681.git.me@ttaylorr.com","threadId":"55262","inReplyTo":"cover.1614957681.git.me@ttaylorr.com","subject":"[PATCH 2/5] t7703: test --geometric repack with loose objects","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2021-03-05T15:21:43Z","receivedAt":"2021-03-05T15:22:42Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"We don't currently have a test that demonstrates the non-idempotent\nbehavior of 'git repack --geometric' with loose objects, so add one here\nto make sure we don't regress in this area.\n\nSigned-off-by: Taylor Blau <me@ttaylorr.com>\n---\n t/t7703-repack-geometric.sh | 31 +++++++++++++++++++++++++++++++\n 1 file changed, 31 insertions(+)\n\ndiff --git a/t/t7703-repack-geometric.sh b/t/t7703-repack-geometric.sh\nindex 4a1952a054..5ccaa440e0 100755\n--- a/t/t7703-repack-geometric.sh\n+++ b/t/t7703-repack-geometric.sh\n@@ -54,6 +54,37 @@ test_expect_success '--geometric with an intact progression' '\n \t)\n '\n \n+test_expect_success '--geometric with loose objects' '\n+\tgit init geometric &&\n+\ttest_when_finished \"rm -fr geometric\" &&\n+\t(\n+\t\tcd geometric &&\n+\n+\t\t# These packs already form a geometric progression.\n+\t\ttest_commit_bulk --start=1 1 && # 3 objects\n+\t\ttest_commit_bulk --start=2 2 && # 6 objects\n+\t\t# The loose objects are packed together, breaking the\n+\t\t# progression.\n+\t\ttest_commit loose && # 3 objects\n+\n+\t\tfind $objdir/pack -name \"*.pack\" | sort >before &&\n+\t\tgit repack --geometric 2 -d &&\n+\t\tfind $objdir/pack -name \"*.pack\" | sort >after &&\n+\n+\t\tcomm -13 before after >new &&\n+\t\tcomm -23 before after >removed &&\n+\n+\t\ttest_line_count = 1 new &&\n+\t\ttest_must_be_empty removed &&\n+\n+\t\tgit repack --geometric 2 -d &&\n+\t\tfind $objdir/pack -name \"*.pack\" | sort >after &&\n+\n+\t\t# The progression (3, 3, 6) is combined into one new pack.\n+\t\ttest_line_count = 1 after\n+\t)\n+'\n+\n test_expect_success '--geometric with small-pack rollup' '\n \tgit init geometric &&\n \ttest_when_finished \"rm -fr geometric\" &&\n-- \n2.30.0.667.g81c0cbc6fd\n\n"},{"id":"418316","messageId":"d55324f7a256fce491a29a1debf142f817eb01d3.1614957681.git.me@ttaylorr.com","threadId":"55262","inReplyTo":"cover.1614957681.git.me@ttaylorr.com","subject":"[PATCH 4/5] builtin/repack.c: be more conservative with unsigned overflows","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2021-03-05T15:21:56Z","receivedAt":"2021-03-05T15:22:43Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"There are a number of places in the geometric repack code where we\nmultiply the number of objects in a pack by another unsigned value. We\ntrust that the number of objects in a pack is always representable by a\nuint32_t, but we don't necessarily trust that that number can be\nmultiplied without overflow.\n\nSprinkle some unsigned_add_overflows() and unsigned_mult_overflows() in\nsplit_pack_geometry() to check that we never overflow any unsigned types\nwhen adding or multiplying them.\n\nArguably these checks are a little too conservative, and certainly they\ndo not help the readability of this function. But they are serving a\nuseful purpose, so I think they are worthwhile overall.\n\nSuggested-by: Junio C Hamano <gitster@pobox.com>\nSigned-off-by: Taylor Blau <me@ttaylorr.com>\n---\n builtin/repack.c | 24 ++++++++++++++++++++++--\n 1 file changed, 22 insertions(+), 2 deletions(-)\n\ndiff --git a/builtin/repack.c b/builtin/repack.c\nindex 21a5778e73..677c6b75c1 100644\n--- a/builtin/repack.c\n+++ b/builtin/repack.c\n@@ -363,6 +363,12 @@ static void split_pack_geometry(struct pack_geometry *geometry, int factor)\n \tfor (i = geometry->pack_nr - 1; i > 0; i--) {\n \t\tstruct packed_git *ours = geometry->pack[i];\n \t\tstruct packed_git *prev = geometry->pack[i - 1];\n+\n+\t\tif (unsigned_mult_overflows(factor, geometry_pack_weight(prev)))\n+\t\t\tdie(_(\"pack %s too large to consider in geometric \"\n+\t\t\t      \"progression\"),\n+\t\t\t    prev->pack_name);\n+\n \t\tif (geometry_pack_weight(ours) < factor * geometry_pack_weight(prev))\n \t\t\tbreak;\n \t}\n@@ -388,11 +394,25 @@ static void split_pack_geometry(struct pack_geometry *geometry, int factor)\n \t * packs in the heavy half need to be joined into it (if any) to restore\n \t * the geometric progression.\n \t */\n-\tfor (i = 0; i < split; i++)\n-\t\ttotal_size += geometry_pack_weight(geometry->pack[i]);\n+\tfor (i = 0; i < split; i++) {\n+\t\tstruct packed_git *p = geometry->pack[i];\n+\n+\t\tif (unsigned_add_overflows(total_size, geometry_pack_weight(p)))\n+\t\t\tdie(_(\"pack %s too large to roll up\"), p->pack_name);\n+\t\ttotal_size += geometry_pack_weight(p);\n+\t}\n \tfor (i = split; i < geometry->pack_nr; i++) {\n \t\tstruct packed_git *ours = geometry->pack[i];\n+\n+\t\tif (unsigned_mult_overflows(factor, total_size))\n+\t\t\tdie(_(\"pack %s too large to roll up\"), ours->pack_name);\n+\n \t\tif (geometry_pack_weight(ours) < factor * total_size) {\n+\t\t\tif (unsigned_add_overflows(total_size,\n+\t\t\t\t\t\t   geometry_pack_weight(ours)))\n+\t\t\t\tdie(_(\"pack %s too large to roll up\"),\n+\t\t\t\t    ours->pack_name);\n+\n \t\t\tsplit++;\n \t\t\ttotal_size += geometry_pack_weight(ours);\n \t\t} else\n-- \n2.30.0.667.g81c0cbc6fd\n\n"},{"id":"418317","messageId":"de4715c7c75e36c446782107f3194a3eedaffdde.1614957681.git.me@ttaylorr.com","threadId":"55262","inReplyTo":"cover.1614957681.git.me@ttaylorr.com","subject":"[PATCH 5/5] builtin/repack.c: reword comment around pack-objects flags","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2021-03-05T15:22:02Z","receivedAt":"2021-03-05T15:22:43Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"From: Junio C Hamano <gitster@pobox.com>\n\nThe comment in this block is meant to indicate that passing '--all',\n'--reflog', and so on aren't necessary when repacking with the\n'--geometric' option.\n\nBut, it has two problems: first, it is factually incorrect ('--all' is\n*not* incompatible with '--stdin-packs' as the comment suggests);\nsecond, it is quite focused on the geometric case for a block that is\nguarding against it.\n\nReword this comment to address both issues.\n\nSigned-off-by: Junio C Hamano <gitster@pobox.com>\nSigned-off-by: Taylor Blau <me@ttaylorr.com>\n---\n builtin/repack.c | 12 +++++++-----\n 1 file changed, 7 insertions(+), 5 deletions(-)\n\ndiff --git a/builtin/repack.c b/builtin/repack.c\nindex 677c6b75c1..6ce2556c9e 100644\n--- a/builtin/repack.c\n+++ b/builtin/repack.c\n@@ -545,12 +545,14 @@ int cmd_repack(int argc, const char **argv, const char *prefix)\n \tstrvec_push(&cmd.args, \"--non-empty\");\n \tif (!geometry) {\n \t\t/*\n-\t\t * 'git pack-objects' will up all objects loose or packed\n-\t\t * (either rolling them up or leaving them alone), so don't pass\n-\t\t * these options.\n+\t\t * We need to grab all reachable objects, including those that\n+\t\t * are reachable from reflogs and the index.\n \t\t *\n-\t\t * The implementation of 'git pack-objects --stdin-packs'\n-\t\t * makes them redundant (and the two are incompatible).\n+\t\t * When repacking into a geometric progression of packs,\n+\t\t * however, we ask 'git pack-objects --stdin-packs', and it is\n+\t\t * not about packing objects based on reachability but about\n+\t\t * repacking all the objects in specified packs and loose ones\n+\t\t * (indeed, --stdin-packs is incompatible with these options).\n \t\t */\n \t\tstrvec_push(&cmd.args, \"--all\");\n \t\tstrvec_push(&cmd.args, \"--reflog\");\n-- \n2.30.0.667.g81c0cbc6fd\n"},{"id":"418318","messageId":"60f13524bd602517c41554898b213161e9d603ce.1614957681.git.me@ttaylorr.com","threadId":"55262","inReplyTo":"cover.1614957681.git.me@ttaylorr.com","subject":"[PATCH 3/5] builtin/repack.c: assign pack split later","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2021-03-05T15:21:50Z","receivedAt":"2021-03-05T15:22:43Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"To determine the where to place the split when repacking with the\n'--geometric' option, split_pack_geometry() assigns the \"split\" variable\nand then decrements it in a loop.\n\nIt would be equivalent (and more readable) to assign the split to the\nloop position after exiting the loop, so do that instead.\n\nSuggested-by: Junio C Hamano <gitster@pobox.com>\nSigned-off-by: Taylor Blau <me@ttaylorr.com>\n---\n builtin/repack.c | 8 +++-----\n 1 file changed, 3 insertions(+), 5 deletions(-)\n\ndiff --git a/builtin/repack.c b/builtin/repack.c\nindex 4ca2f647b4..21a5778e73 100644\n--- a/builtin/repack.c\n+++ b/builtin/repack.c\n@@ -356,8 +356,6 @@ static void split_pack_geometry(struct pack_geometry *geometry, int factor)\n \t\treturn;\n \t}\n \n-\tsplit = geometry->pack_nr - 1;\n-\n \t/*\n \t * First, count the number of packs (in descending order of size) which\n \t * already form a geometric progression.\n@@ -365,12 +363,12 @@ static void split_pack_geometry(struct pack_geometry *geometry, int factor)\n \tfor (i = geometry->pack_nr - 1; i > 0; i--) {\n \t\tstruct packed_git *ours = geometry->pack[i];\n \t\tstruct packed_git *prev = geometry->pack[i - 1];\n-\t\tif (geometry_pack_weight(ours) >= factor * geometry_pack_weight(prev))\n-\t\t\tsplit--;\n-\t\telse\n+\t\tif (geometry_pack_weight(ours) < factor * geometry_pack_weight(prev))\n \t\t\tbreak;\n \t}\n \n+\tsplit = i;\n+\n \tif (split) {\n \t\t/*\n \t\t * Move the split one to the right, since the top element in the\n-- \n2.30.0.667.g81c0cbc6fd\n\n"},{"id":"418334","messageId":"xmqqv9a59ztd.fsf@gitster.c.googlers.com","threadId":"55262","inReplyTo":"80bc7fa8397491d015b80a39168813d2019e262d.1614957681.git.me@ttaylorr.com","subject":"Re: [PATCH 1/5] builtin/repack.c: do not repack single packs with --geometric","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2021-03-05T19:15:58Z","receivedAt":"2021-03-05T19:16:40Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Taylor Blau <me@ttaylorr.com> writes:\n\n> Loosen the guard to only stop when there aren't any packs, and let the\n> rest of the code do the right thing. Add a test to ensure that this is\n> the case.\n>\n> Noticed-by: Junio C Hamano <gitster@pobox.com>\n\nI do not think I \"noticed\" anything, though.\n\n> -\tif (geometry->pack_nr <= 1) {\n> +\tif (!geometry->pack_nr) {\n>  \t\tgeometry->split = geometry->pack_nr;\n>  \t\treturn;\n>  \t}\n\nWhen pack_nr is 0, split is set to 0.  Otherwise we compute the\nsplit the usual way in the new code.  Let's see the post-context of\nthe above code and figure out what happens when pack_nr is 1.\n\n\tsplit = geometry->pack_nr - 1;\n\nsplit set to 0 here.\n\n\t/*\n\t * First, count the number of packs (in descending order of size) which\n\t * already form a geometric progression.\n\t */\n\tfor (i = geometry->pack_nr - 1; i > 0; i--) {\n\nIterate from i = 0 while i is positive, which means this entire loop\nis skipped.\n\n\t\tstruct packed_git *ours = geometry->pack[i];\n\t\tstruct packed_git *prev = geometry->pack[i - 1];\n\t\tif (geometry_pack_weight(ours) >= factor * geometry_pack_weight(prev))\n\t\t\tsplit--;\n\t\telse\n\t\t\tbreak;\n\t}\n\n\tif (split) {\n\t\t/*\n\t\t * Move the split one to the right, since the top element in the\n\t\t * last-compared pair can't be in the progression. Only do this\n\t\t * when we split in the middle of the array (otherwise if we got\n\t\t * to the end, then the split is in the right place).\n\t\t */\n\t\tsplit++;\n\t}\n\nAnd split is still 0.\n\n\n\t/*\n\t * Then, anything to the left of 'split' must be in a new pack. But,\n\t * creating that new pack may cause packs in the heavy half to no longer\n\t * form a geometric progression.\n\t *\n\t * Compute an expected size of the new pack, and then determine how many\n\t * packs in the heavy half need to be joined into it (if any) to restore\n\t * the geometric progression.\n\t */\n\tfor (i = 0; i < split; i++)\n\t\ttotal_size += geometry_pack_weight(geometry->pack[i]);\n\nThe loop is skipped, as split is 0.\n\n\tfor (i = split; i < geometry->pack_nr; i++) {\n\nIterate from i = 0 and for just once.\n\n\t\tstruct packed_git *ours = geometry->pack[i];\n\t\tif (geometry_pack_weight(ours) < factor * total_size) {\n\nBut total_size is 0 so split is not incremented.\n\n\t\t\tsplit++;\n\t\t\ttotal_size += geometry_pack_weight(ours);\n\t\t} else\n\t\t\tbreak;\n\t}\n\n\tgeometry->split = split;\n\nHence we assign 0 to .split member.\n\nI however wonder if it expresses the intent more clearly if you did\nthis upfront, instead of forcing the readers to go through the code.\n\n\tif (geometry->pack_nr <= 1) {\n-\t\tgeometry->split = geometry->pack_nr;\n+\t\tgeometry->split = 0;\n \t\treturn;\n \t}\n\nThat is, \"when there is no existing packs, or just one pack, we\nsplit at 0\"\n\nThe code that gets affected by the setting of \"split\" is this piece\nin the caller, cmd_repack():\n\n\tif (geometry) {\n\t\tFILE *in = xfdopen(cmd.in, \"w\");\n\t\tfor (i = 0; i < geometry->split; i++)\n\t\t\tfprintf(in, \"%s\\n\", pack_basename(geometry->pack[i]));\n\t\tfor (i = geometry->split; i < geometry->pack_nr; i++)\n\t\t\tfprintf(in, \"^%s\\n\", pack_basename(geometry->pack[i]));\n\t\tfclose(in);\n\t}\n\nWhen split == 0, we end up feeding no positive packs and all\nnegative packs, which results in nothing to pack.  I wonder if we\ncan optimize out the spawning of the pack-object process, but that\nis probalby optimizing for a wrong case.\n\n> diff --git a/t/t7703-repack-geometric.sh b/t/t7703-repack-geometric.sh\n> index 96917fc163..4a1952a054 100755\n> --- a/t/t7703-repack-geometric.sh\n> +++ b/t/t7703-repack-geometric.sh\n> @@ -20,6 +20,21 @@ test_expect_success '--geometric with no packs' '\n>  \t)\n>  '\n>  \n> +test_expect_success '--geometric with one pack' '\n> +\tgit init geometric &&\n> +\ttest_when_finished \"rm -fr geometric\" &&\n> +\t(\n> +\t\tcd geometric &&\n> +\n> +\t\ttest_commit \"base\" &&\n> +\t\tgit repack -d &&\n> +\n> +\t\tgit repack --geometric 2 >out &&\n> +\n> +\t\ttest_i18ngrep \"Nothing new to pack\" out\n> +\t)\n> +'\n> +\n>  test_expect_success '--geometric with an intact progression' '\n>  \tgit init geometric &&\n>  \ttest_when_finished \"rm -fr geometric\" &&\n"},{"id":"418335","messageId":"YEKGLfUM1DSHk74B@nand.local","threadId":"55262","inReplyTo":"xmqqv9a59ztd.fsf@gitster.c.googlers.com","subject":"Re: [PATCH 1/5] builtin/repack.c: do not repack single packs with --geometric","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2021-03-05T19:27:41Z","receivedAt":"2021-03-05T19:28:23Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Fri, Mar 05, 2021 at 11:15:58AM -0800, Junio C Hamano wrote:\n> Taylor Blau <me@ttaylorr.com> writes:\n>\n> > Loosen the guard to only stop when there aren't any packs, and let the\n> > rest of the code do the right thing. Add a test to ensure that this is\n> > the case.\n> >\n> > Noticed-by: Junio C Hamano <gitster@pobox.com>\n>\n> I do not think I \"noticed\" anything, though.\n\nWell, I clearly didn't notice it, so I'm happy to pass the buck to you.\n\n> > -\tif (geometry->pack_nr <= 1) {\n> > +\tif (!geometry->pack_nr) {\n> >  \t\tgeometry->split = geometry->pack_nr;\n> >  \t\treturn;\n> >  \t}\n>\n> When pack_nr is 0, split is set to 0.  Otherwise we compute the\n> split the usual way in the new code.  Let's see the post-context of\n> the above code and figure out what happens when pack_nr is 1.\n>\n> [snip]\n>\n> I however wonder if it expresses the intent more clearly if you did\n> this upfront, instead of forcing the readers to go through the code.\n>\n> \tif (geometry->pack_nr <= 1) {\n> -\t\tgeometry->split = geometry->pack_nr;\n> +\t\tgeometry->split = 0;\n>  \t\treturn;\n>  \t}\n>\n> That is, \"when there is no existing packs, or just one pack, we\n> split at 0\"\n\nHmm. I originally wrote the patch as:\n\n    if (geometry->pack_nr <= 1) {\n      geometry->split = 0;\n      return;\n    }\n\ninstead of only when geometry->pack_nr == 0. But I was pretty sure that\nthe code below was doing the right thing even for geometry->pack_nr ==\n1, and so I decided to avoid making this non-special case \"special\" by\nreturning early.\n\nI could see arguments in both directions. But I may be biased as the\nauthor, so I'd rather defer to your judgement instead.\n\n> The code that gets affected by the setting of \"split\" is this piece\n> in the caller, cmd_repack():\n>\n> \tif (geometry) {\n> \t\tFILE *in = xfdopen(cmd.in, \"w\");\n> \t\tfor (i = 0; i < geometry->split; i++)\n> \t\t\tfprintf(in, \"%s\\n\", pack_basename(geometry->pack[i]));\n> \t\tfor (i = geometry->split; i < geometry->pack_nr; i++)\n> \t\t\tfprintf(in, \"^%s\\n\", pack_basename(geometry->pack[i]));\n> \t\tfclose(in);\n> \t}\n>\n> When split == 0, we end up feeding no positive packs and all\n> negative packs, which results in nothing to pack.  I wonder if we\n> can optimize out the spawning of the pack-object process, but that\n> is probalby optimizing for a wrong case.\n\nYeah, I think the earlier optimization (avoiding repacking the contents\nof a single pack) is more important than not opening pack objects here.\n\nBut the next patch demonstrates why we can't do this: we care about\nloose objects, which we may still pick up even if split == 0.\n\nThanks,\nTaylor\n"},{"id":"418337","messageId":"YEKG5XtNxArQe/xH@nand.local","threadId":"55262","inReplyTo":"YEKGLfUM1DSHk74B@nand.local","subject":"Re: [PATCH 1/5] builtin/repack.c: do not repack single packs with --geometric","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2021-03-05T19:30:45Z","receivedAt":"2021-03-05T19:31:36Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Fri, Mar 05, 2021 at 02:27:41PM -0500, Taylor Blau wrote:\n> instead of only when geometry->pack_nr == 0. But I was pretty sure that\n> the code below was doing the right thing even for geometry->pack_nr ==\n> 1, and so I decided to avoid making this non-special case \"special\" by\n> returning early.\n\nAfter \"I was pretty sure that the code was doing the right\", I should\nnote that I did the same thing you did in my head, and then confirmed\nmy thinking by running the tests in t5326.\n\nRe-reading my response, I am worried that I gave the impression of being\nlackadaisical about testing.\n"},{"id":"418338","messageId":"xmqqr1kt9z12.fsf@gitster.c.googlers.com","threadId":"55262","inReplyTo":"d55324f7a256fce491a29a1debf142f817eb01d3.1614957681.git.me@ttaylorr.com","subject":"Re: [PATCH 4/5] builtin/repack.c: be more conservative with unsigned overflows","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2021-03-05T19:32:57Z","receivedAt":"2021-03-05T19:33:44Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Taylor Blau <me@ttaylorr.com> writes:\n\n> There are a number of places in the geometric repack code where we\n> multiply the number of objects in a pack by another unsigned value. We\n> trust that the number of objects in a pack is always representable by a\n> uint32_t, but we don't necessarily trust that that number can be\n> multiplied without overflow.\n>\n> Sprinkle some unsigned_add_overflows() and unsigned_mult_overflows() in\n> split_pack_geometry() to check that we never overflow any unsigned types\n> when adding or multiplying them.\n>\n> Arguably these checks are a little too conservative, and certainly they\n> do not help the readability of this function. But they are serving a\n> useful purpose, so I think they are worthwhile overall.\n>\n> Suggested-by: Junio C Hamano <gitster@pobox.com>\n\nI do not deserve this for my idle thinking-out-aloud speculation.\nYou did all the thinking and work.\n\nI do not know if just dying is a useful thing to do, though.  These\nall happen in the \"discover where the split point is, to figure out\nwhich packs to coalesce\" phase where we haven't touched anything on\ndisk, so in that sense it is safe to die, but what recourse do users\nhave after seeing these errors?\n\nFor example, in the first overflow check in hunk -388,11, presumably\nwhen total_size for a given set of packfiles does not fit in\nint32_t, it won't be fruitful to attempt to coalesce such a set of\npacks into one, so perhaps a better fix may be to shift the split\npoint earlier to find a point that lets us to pack as many as we\ncould?\n\nI do not offhand know what a sensible and gentler fallback position\nwould be for the factor multiplication, but presumably, if the right\nhand side of this ...\n\n>  \t\tif (geometry_pack_weight(ours) < factor * total_size) {\n\n... overflows, we can say it would definitely be larger than our\nweight and continue, instead of \"no, we cannot multiply total with\nfactor, as that would give us too big a number\", I guess.\n\nI am OK to either (1) leave the code as-is without this patch, because\nthe overflow would only affect the largest of packs and would be rare,\nand people who would notice when they hit it would probably are the ones\nwith enough resource to diagnose, report and even give us a fix ;-)\nor (2) apply this patch as-is, because the only people who will see\nthe die() would be the same ones affected by (1) above anyway.\n\nAnd applying this patch as-is would give better chance than (1) for\nthe overflow to be noticed.\n\nSo, let's queue the patch as-is.\n\nThanks.\n"},{"id":"418339","messageId":"YEKJTmbdZqdMx2j0@nand.local","threadId":"55262","inReplyTo":"xmqqr1kt9z12.fsf@gitster.c.googlers.com","subject":"Re: [PATCH 4/5] builtin/repack.c: be more conservative with unsigned overflows","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2021-03-05T19:41:02Z","receivedAt":"2021-03-05T19:41:51Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Fri, Mar 05, 2021 at 11:32:57AM -0800, Junio C Hamano wrote:\n> > Suggested-by: Junio C Hamano <gitster@pobox.com>\n>\n> I do not deserve this for my idle thinking-out-aloud speculation.\n> You did all the thinking and work.\n\nYou're selling yourself short ;-).\n\n> I do not offhand know what a sensible and gentler fallback position\n> would be for the factor multiplication, but presumably, if the right\n> hand side of this ...\n>\n> >  \t\tif (geometry_pack_weight(ours) < factor * total_size) {\n>\n> ... overflows, we can say it would definitely be larger than our\n> weight and continue, instead of \"no, we cannot multiply total with\n> factor, as that would give us too big a number\", I guess.\n\nTo answer your question about whether or not dying is sensible, I think\nthat there are a couple of options. You could say, \"I can no longer\nmultiply total_size by factor without overflowing, so I'm not even going\nto bother considering additional packs\". I guess that makes some\nprogress in condensing packs, but that's as good as it would get, since\nthe subsequent repack would also overflow instead of making further\nprogress, so it would just get stuck.\n\nWhich makes me think that the other option, dying, is more sensible. But\nI think that this is all a moot point as you seem to indicate anyway,\nbecause having a large enough pack that we are verging on overflowing is\nlikely not a real-world problem that we are going to deal with (at least\nright away).\n\n> I am OK to either (1) leave the code as-is without this patch, because\n> the overflow would only affect the largest of packs and would be rare,\n> and people who would notice when they hit it would probably are the ones\n> with enough resource to diagnose, report and even give us a fix ;-)\n> or (2) apply this patch as-is, because the only people who will see\n> the die() would be the same ones affected by (1) above anyway.\n>\n> And applying this patch as-is would give better chance than (1) for\n> the overflow to be noticed.\n>\n> So, let's queue the patch as-is.\n\nGreat, I'm fine with that. Thanks.\n\n> Thanks.\n\nTaylor\n"},{"id":"418737","messageId":"YEkzgeuqkgF4RvaF@coredump.intra.peff.net","threadId":"55262","inReplyTo":"d55324f7a256fce491a29a1debf142f817eb01d3.1614957681.git.me@ttaylorr.com","subject":"Re: [PATCH 4/5] builtin/repack.c: be more conservative with unsigned overflows","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2021-03-10T21:00:49Z","receivedAt":"2021-03-10T21:01:47Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Mar 05, 2021 at 10:21:56AM -0500, Taylor Blau wrote:\n\n> There are a number of places in the geometric repack code where we\n> multiply the number of objects in a pack by another unsigned value. We\n> trust that the number of objects in a pack is always representable by a\n> uint32_t, but we don't necessarily trust that that number can be\n> multiplied without overflow.\n> \n> Sprinkle some unsigned_add_overflows() and unsigned_mult_overflows() in\n> split_pack_geometry() to check that we never overflow any unsigned types\n> when adding or multiplying them.\n> \n> Arguably these checks are a little too conservative, and certainly they\n> do not help the readability of this function. But they are serving a\n> useful purpose, so I think they are worthwhile overall.\n\nHmm. My initial reaction was: how close might we reasonably come to the\nlimit? Packfiles are limited to uint32_t, and:\n\n  - you'd have a pretty hard time approaching that; pack-objects needs\n    at least 100 bytes of heap per object for its internal book-keeping.\n    So you're looking at 200GB-400GB of RAM to generate such a packfile.\n\n  - I'm pretty sure the rest of the repack code would die horribly and\n    unpredictably if it were allowed to have that much RAM.\n\nWhich isn't an argument against such protections, but I wonder if it\nmight give people a false sense that we are in any way prepared for\nrepositories of this scale.\n\nHowever, at least one of these looks to be multiplying the user-provided\nscale factor. I can't imagine a scale factor beyond \"2\" is all that\nuseful, but conceptually somebody could provide a big number there.\n\nLooking at the code, though...\n\n> diff --git a/builtin/repack.c b/builtin/repack.c\n> index 21a5778e73..677c6b75c1 100644\n> --- a/builtin/repack.c\n> +++ b/builtin/repack.c\n> @@ -363,6 +363,12 @@ static void split_pack_geometry(struct pack_geometry *geometry, int factor)\n>  \tfor (i = geometry->pack_nr - 1; i > 0; i--) {\n>  \t\tstruct packed_git *ours = geometry->pack[i];\n>  \t\tstruct packed_git *prev = geometry->pack[i - 1];\n> +\n> +\t\tif (unsigned_mult_overflows(factor, geometry_pack_weight(prev)))\n> +\t\t\tdie(_(\"pack %s too large to consider in geometric \"\n> +\t\t\t      \"progression\"),\n> +\t\t\t    prev->pack_name);\n\nThis says \"unsigned_mult_overflows\", but \"factor\" is a signed int. This\nwill generally be cast to unsigned in the actual multiplication, but it\ndepends on the size of the operands.\n\nIf int is larger than uint32_t, we'd do the multiplication as a signed\nint. But the overflow check would be against an unsigned int (since our\nmacro only looks at the type of the first argument). So it would be\noverly permissive with the final bit. I suspect it would also be wrong\nif \"factor\" is negative.\n\nIf int is smaller than 32 bits, then we'd be too conservative (it would\nget promoted to uint32_t for the actual multiplication). Also, you\nshould get a better computer in that case.\n\nIt's probably OK in practice, as int tends to just be 32 bits. But if\nthe point is to be careful, we should probably just take \"factor\" as a\nuint32_t in the first place.\n\n> @@ -388,11 +394,25 @@ static void split_pack_geometry(struct pack_geometry *geometry, int factor)\n>  \t * packs in the heavy half need to be joined into it (if any) to restore\n>  \t * the geometric progression.\n>  \t */\n> -\tfor (i = 0; i < split; i++)\n> -\t\ttotal_size += geometry_pack_weight(geometry->pack[i]);\n> +\tfor (i = 0; i < split; i++) {\n> +\t\tstruct packed_git *p = geometry->pack[i];\n> +\n> +\t\tif (unsigned_add_overflows(total_size, geometry_pack_weight(p)))\n> +\t\t\tdie(_(\"pack %s too large to roll up\"), p->pack_name);\n> +\t\ttotal_size += geometry_pack_weight(p);\n> +\t}\n\nThis one seems even less likely to overflow. total_size is an off_t, so\nunless you're on a really lame system, we should be able to fit a lot of\nuint32_t's in there.\n\n(It actually feels a little weird for it to be an off_t in the first\nplace; we're still dealing in units of \"number of objects\", which the\nrest of Git generally considers to be in the realm of a uint32_t).\n\n>  \tfor (i = split; i < geometry->pack_nr; i++) {\n>  \t\tstruct packed_git *ours = geometry->pack[i];\n> +\n> +\t\tif (unsigned_mult_overflows(factor, total_size))\n> +\t\t\tdie(_(\"pack %s too large to roll up\"), ours->pack_name);\n\nThis one is wrong in the same way as the earlier multiplication, except\nthis time we're pretty sure that total_size actually is much bigger. So\nwe'll complain about overflowing an int, but the multiplication will\nactually be done as an off_t. And of course it has the same problems\nwith negative values.\n\nShould total_size just be a uint32_t? Or perhaps any of these factor\nmultiplication results should just be uint64_t, which would be the\nobviously-large-enough type. Then you wouldn't have these ugly overflow\nchecks. :)\n\n-Peff\n"}]}