{"thread":{"id":"63485","subject":"[PATCH 0/4] midx repack: fix overflow on 32 bit systems","startedAt":"2025-05-20T15:04:41Z","lastAt":"2025-05-27T15:42:38Z","messageCount":25,"participants":["Phillip Wood","Taylor Blau","D. Ben Knoble","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":4},"messages":[{"id":"518493","messageId":"cover.1747753388.git.phillip.wood@dunelm.org.uk","threadId":"63485","inReplyTo":null,"subject":"[PATCH 0/4] midx repack: fix overflow on 32 bit systems","fromName":"Phillip Wood","fromEmail":"phillip.wood123@gmail.com","sentAt":"2025-05-20T15:04:23Z","receivedAt":"2025-05-20T15:04:41Z","isPatch":true,"sender":{"key":"phillip.wood@dunelm.org.uk","avatar":null},"body":"From: Phillip Wood \n\nThis series fixes an overflow when running \"git multi-pack-index\nrepack\" on an old raspberry pi and a couple of other small issues I\nnoticed while reading the code. I'm unsure how realistic the example\nof integer overflow on 64 bit systems in patch 2 is. I'm happy to drop\nit if people who work with large repositories think its not worth\nworrying about.\n\nBase-Commit: cb96e1697ad6e54d11fc920c95f82977f8e438f8\nPublished-As: https://github.com/phillipwood/git/releases/tag/pw%2Fmidx-repack-overflow%2Fv1\nView-Changes-At: https://github.com/phillipwood/git/compare/cb96e1697...29769df1c\nFetch-It-Via: git fetch https://github.com/phillipwood/git pw/midx-repack-overflow/v1\n\n\nPhillip Wood (4):\n midx repack: avoid integer overflow on 32 bit systems\n midx repack: avoid potential integer overflow on 64 bit systems\n midx: avoid negative array index\n midx docs: clarify tie breaking\n\n Documentation/git-multi-pack-index.adoc | 6 ++++--\n git-compat-util.h | 16 ++++++++++++++++\n midx-write.c | 22 ++++++++++++++++------\n 3 files changed, 36 insertions(+), 8 deletions(-)\n\n-- \n2.49.0.897.gfad3eb7d210\n\n"},{"id":"518494","messageId":"cbc5e69b908cef3800569abe79cb9c107f72bfec.1747753388.git.phillip.wood@dunelm.org.uk","threadId":"63485","inReplyTo":"cover.1747753388.git.phillip.wood@dunelm.org.uk","subject":"[PATCH 1/4] midx repack: avoid integer overflow on 32 bit systems","fromName":"Phillip Wood","fromEmail":"phillip.wood123@gmail.com","sentAt":"2025-05-20T15:04:24Z","receivedAt":"2025-05-20T15:04:42Z","isPatch":true,"sender":{"key":"phillip.wood@dunelm.org.uk","avatar":null},"body":"From: Phillip Wood \n\nOn a 32 bit system \"git multi-pack-index --repack --batch-size=120M\"\nfailed with\n\n fatal: size_t overflow: 6038786 * 1289\n\nThe calculation to estimated size of the objects in the pack referenced\nby the multi-pack-index uses st_mult() to multiply the pack size by the\nnumber of referenced objects before dividing by the total number of\nobjects in the pack. As size_t is 32 bits on 32 bit systems this\ncalculation easily overflows. Fix this by using 64bit arithmetic instead.\n\nAlso fix a potential overflow when caluculating the total size of the\nobjects referenced by the multipack index with a batch size larger\nthan SIZE_MAX / 2. In that case\n\n total_size += estimated_size\n\ncan overflow as both total_size and estimated_size can be greater that\nSIZE_MAX / 2. This is addressed by using saturating arithmetic for the\naddition.\n\nSigned-off-by: Phillip Wood \n---\n git-compat-util.h | 16 ++++++++++++++++\n midx-write.c | 12 ++++++++----\n 2 files changed, 24 insertions(+), 4 deletions(-)\n\ndiff --git a/git-compat-util.h b/git-compat-util.h\nindex 36b9577c8d4..4678e21c4cb 100644\n--- a/git-compat-util.h\n+++ b/git-compat-util.h\n@@ -668,6 +668,22 @@ static inline int cast_size_t_to_int(size_t a)\n \treturn (int)a;\n }\n \n+static inline uint64_t u64_mult(uint64_t a, uint64_t b)\n+{\n+\tif (unsigned_mult_overflows(a, b))\n+\t\tdie(\"uint64_t overflow: %\"PRIuMAX\" * %\"PRIuMAX,\n+\t\t (uintmax_t)a, (uintmax_t)b);\n+\treturn a * b;\n+}\n+\n+static inline uint64_t u64_add(uint64_t a, uint64_t b)\n+{\n+\tif (unsigned_add_overflows(a, b))\n+\t\tdie(\"uint64_t overflow: %\"PRIuMAX\" + %\"PRIuMAX,\n+\t\t (uintmax_t)a, (uintmax_t)b);\n+\treturn a + b;\n+}\n+\n /*\n * Limit size of IO chunks, because huge chunks only cause pain. OS X\n * 64-bit is buggy, returning EINVAL if len >= INT_MAX; and even in\ndiff --git a/midx-write.c b/midx-write.c\nindex dd3b3070e55..c7cb2315431 100644\n--- a/midx-write.c\n+++ b/midx-write.c\n@@ -1699,19 +1699,23 @@ static void fill_included_packs_batch(struct repository *r,\n \tfor (i = 0; total_size < batch_size && i < m->num_packs; i++) {\n \t\tint pack_int_id = pack_info[i].pack_int_id;\n \t\tstruct packed_git *p = m->packs[pack_int_id];\n-\t\tsize_t expected_size;\n+\t\tuint64_t expected_size;\n \n \t\tif (!want_included_pack(r, m, pack_kept_objects, pack_int_id))\n \t\t\tcontinue;\n \n-\t\texpected_size = st_mult(p->pack_size,\n-\t\t\t\t\tpack_info[i].referenced_objects);\n+\t\texpected_size = uint64_mult(p->pack_size,\n+\t\t\t\t\t pack_info[i].referenced_objects);\n \t\texpected_size /= p->num_objects;\n \n \t\tif (expected_size >= batch_size)\n \t\t\tcontinue;\n \n-\t\ttotal_size += expected_size;\n+\t\tif (unsigned_add_overflows (total_size, (size_t)expected_size))\n+\t\t\ttotal_size = SIZE_MAX;\n+\t\telse\n+\t\t\ttotal_size += expected_size;\n+\n \t\tinclude_pack[pack_int_id] = 1;\n \t}\n \n-- \n2.49.0.897.gfad3eb7d210\n\n"},{"id":"518495","messageId":"9f07da4fe71d21b14226d8f0132cd3c8600fba13.1747753388.git.phillip.wood@dunelm.org.uk","threadId":"63485","inReplyTo":"cover.1747753388.git.phillip.wood@dunelm.org.uk","subject":"[PATCH 2/4] midx repack: avoid potential integer overflow on 64 bit systems","fromName":"Phillip Wood","fromEmail":"phillip.wood123@gmail.com","sentAt":"2025-05-20T15:04:25Z","receivedAt":"2025-05-20T15:04:43Z","isPatch":true,"sender":{"key":"phillip.wood@dunelm.org.uk","avatar":null},"body":"From: Phillip Wood \n\nOn a 64 bit system the calculation\n\n p->pack_size * pack_info[i].referenced_objects\n\ncould overflow. If a pack file contains 2^28 objects with an average\ncompressed size of 1KB then the pack size will be 2^38B. If all of the\nobjects are referenced by the multi-pack index the sum above will\noverflow. Avoid this by using shifted integer arithmetic and changing\nthe order of the calculation so that the pack size is divided by the\ntotal number of objects in the pack before multiplying by the number of\nobjects referenced by the multi-pack index. Using a shift of 14 bits\nshould give reasonable accuracy while avoiding overflow for pack sizes\nless that 1PB.\n\nSigned-off-by: Phillip Wood \n---\n midx-write.c | 10 ++++++++--\n 1 file changed, 8 insertions(+), 2 deletions(-)\n\ndiff --git a/midx-write.c b/midx-write.c\nindex c7cb2315431..2ee381e8fcd 100644\n--- a/midx-write.c\n+++ b/midx-write.c\n@@ -1704,9 +1704,15 @@ static void fill_included_packs_batch(struct repository *r,\n \t\tif (!want_included_pack(r, m, pack_kept_objects, pack_int_id))\n \t\t\tcontinue;\n \n-\t\texpected_size = uint64_mult(p->pack_size,\n-\t\t\t\t\t pack_info[i].referenced_objects);\n+\t\t/*\n+\t\t * Use shifted integer arithmetic to calculate the\n+\t\t * expected pack size to ~4 significant digits without\n+\t\t * overflow for packsizes less that 1PB.\n+\t\t */\n+\t\texpected_size = (uint64_t)pack_info[i].referenced_objects << 14;\n \t\texpected_size /= p->num_objects;\n+\t\texpected_size = u64_mult(expected_size, p->pack_size);\n+\t\texpected_size = u64_add(expected_size, 1u << 13) >> 14;\n \n \t\tif (expected_size >= batch_size)\n \t\t\tcontinue;\n-- \n2.49.0.897.gfad3eb7d210\n\n"},{"id":"518496","messageId":"688b0273604179b5bebe3748445158e09a7bf1a0.1747753388.git.phillip.wood@dunelm.org.uk","threadId":"63485","inReplyTo":"cover.1747753388.git.phillip.wood@dunelm.org.uk","subject":"[PATCH 3/4] midx: avoid negative array index","fromName":"Phillip Wood","fromEmail":"phillip.wood123@gmail.com","sentAt":"2025-05-20T15:04:26Z","receivedAt":"2025-05-20T15:04:44Z","isPatch":true,"sender":{"key":"phillip.wood@dunelm.org.uk","avatar":null},"body":"From: Phillip Wood \n\nnth_midxed_pack_int_id() returns the index of the pack file in the multi\npack index's list of packfiles that the specified object. The index is\nreturned as a uint32_t. Storing this in an int will make the index\nnegative if the most significant bit is set. Fix this by using uint32_t\nas the rest of the code does. This is unlikely to be a practical problem\nas it requires the multipack index to reference 2^31 packfiles.\n\nSigned-off-by: Phillip Wood \n---\n midx-write.c | 4 ++--\n 1 file changed, 2 insertions(+), 2 deletions(-)\n\ndiff --git a/midx-write.c b/midx-write.c\nindex 2ee381e8fcd..38a458d7322 100644\n--- a/midx-write.c\n+++ b/midx-write.c\n@@ -1566,7 +1566,7 @@ int expire_midx_packs(struct repository *r, const char *object_dir, unsigned fla\n \t\t\t\t\t _(\"Counting referenced objects\"),\n \t\t\t\t\t m->num_objects);\n \tfor (i = 0; i < m->num_objects; i++) {\n-\t\tint pack_int_id = nth_midxed_pack_int_id(m, i);\n+\t\tuint32_t pack_int_id = nth_midxed_pack_int_id(m, i);\n \t\tcount[pack_int_id]++;\n \t\tdisplay_progress(progress, i + 1);\n \t}\n@@ -1697,7 +1697,7 @@ static void fill_included_packs_batch(struct repository *r,\n \n \ttotal_size = 0;\n \tfor (i = 0; total_size < batch_size && i < m->num_packs; i++) {\n-\t\tint pack_int_id = pack_info[i].pack_int_id;\n+\t\tuint32_t pack_int_id = pack_info[i].pack_int_id;\n \t\tstruct packed_git *p = m->packs[pack_int_id];\n \t\tuint64_t expected_size;\n \n-- \n2.49.0.897.gfad3eb7d210\n\n"},{"id":"518497","messageId":"29769df1c601c77031a27f3b3e5b571d5d7d043e.1747753388.git.phillip.wood@dunelm.org.uk","threadId":"63485","inReplyTo":"cover.1747753388.git.phillip.wood@dunelm.org.uk","subject":"[PATCH 4/4] midx docs: clarify tie breaking","fromName":"Phillip Wood","fromEmail":"phillip.wood123@gmail.com","sentAt":"2025-05-20T15:04:27Z","receivedAt":"2025-05-20T15:04:45Z","isPatch":true,"sender":{"key":"phillip.wood@dunelm.org.uk","avatar":null},"body":"From: Phillip Wood \n\nClarify what happens when an object exists in more than one pack, but\nnot in the preferred pack. If the user does not pass a preferred pack\nthen the pack with the lowest mtime is chosen as the preferred pack. For\nobjects that are not in the preferred pack the pack with the highest\nmtime is used. \"git multi-pack-index repack\" relies on this behavior. If\nties were resolved in favor of the oldest pack as the current\ndocumentation suggests the multi-pack index would not reference any of\nthe objects in the pack created by \"git multi-pack-index repack\".\n\nSigned-off-by: Phillip Wood \n---\n Documentation/git-multi-pack-index.adoc | 6 ++++--\n 1 file changed, 4 insertions(+), 2 deletions(-)\n\ndiff --git a/Documentation/git-multi-pack-index.adoc b/Documentation/git-multi-pack-index.adoc\nindex 631d5c7d15c..1f016b2f682 100644\n--- a/Documentation/git-multi-pack-index.adoc\n+++ b/Documentation/git-multi-pack-index.adoc\n@@ -40,8 +40,10 @@ write::\n \t--preferred-pack=::\n \t\tOptionally specify the tie-breaking pack used when\n \t\tmultiple packs contain the same object. `` must\n-\t\tcontain at least one object. If not given, ties are\n-\t\tbroken in favor of the pack with the lowest mtime.\n+\t\tcontain at least one object. If not given the pack with\n+\t\tthe lowest mtime is used as the preferred pack. Ties\n+\t\tfor objects that are not contained in the preferred\n+\t\tare resolved in favor of the pack with the newest mtime.\n \n \t--[no-]bitmap::\n \t\tControl whether or not a multi-pack bitmap is written.\n-- \n2.49.0.897.gfad3eb7d210\n\n"},{"id":"518508","messageId":"aCzBvvZDS2OFJ30h@nand.local","threadId":"63485","inReplyTo":"cbc5e69b908cef3800569abe79cb9c107f72bfec.1747753388.git.phillip.wood@dunelm.org.uk","subject":"Re: [PATCH 1/4] midx repack: avoid integer overflow on 32 bit systems","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2025-05-20T17:54:06Z","receivedAt":"2025-05-20T17:54:09Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Tue, May 20, 2025 at 04:04:24PM +0100, Phillip Wood wrote:\n> diff --git a/midx-write.c b/midx-write.c\n> index dd3b3070e55..c7cb2315431 100644\n> --- a/midx-write.c\n> +++ b/midx-write.c\n> @@ -1699,19 +1699,23 @@ static void fill_included_packs_batch(struct repository *r,\n> \tfor (i = 0; total_size < batch_size && i < m->num_packs; i++) {\n> \t\tint pack_int_id = pack_info[i].pack_int_id;\n> \t\tstruct packed_git *p = m->packs[pack_int_id];\n> -\t\tsize_t expected_size;\n> +\t\tuint64_t expected_size;\n>\n> \t\tif (!want_included_pack(r, m, pack_kept_objects, pack_int_id))\n> \t\t\tcontinue;\n>\n> -\t\texpected_size = st_mult(p->pack_size,\n> -\t\t\t\t\tpack_info[i].referenced_objects);\n> +\t\texpected_size = uint64_mult(p->pack_size,\n> +\t\t\t\t\t pack_info[i].referenced_objects);\n\nMakes sense.\n\n> \t\texpected_size /= p->num_objects;\n>\n> \t\tif (expected_size >= batch_size)\n> \t\t\tcontinue;\n>\n> -\t\ttotal_size += expected_size;\n> +\t\tif (unsigned_add_overflows (total_size, (size_t)expected_size))\n> +\t\t\ttotal_size = SIZE_MAX;\n> +\t\telse\n> +\t\t\ttotal_size += expected_size;\n> +\n\nBut this part I am not totally following. Here we have 'total_size'\ndeclared as a size_t, and 'expected_size' as a uint64_t, and (on 32-bit\nsystems) down-cast to a 32-bit unsigned value.\n\nSo if 'expected_size' is larger than SIZE_MAX, we should set\n'total_size' to SIZE_MAX. But that may not happen, say if\n'expected_size' is (2^32-1<<32). Should total_size also be declared as a\nuint64_t here?\n\nI wondered if it might be easier to count down from the given batch_size\ninstead of adding up to it (requiring the second\nunsigned_add_overflows() check). I tried it out and got this instead:\n\n--- 8< ---\ndiff --git a/midx-write.c b/midx-write.c\nindex 48a4dc5e94..f81dd9ff6d 100644\n--- a/midx-write.c\n+++ b/midx-write.c\n@@ -1671,7 +1671,7 @@ static void fill_included_packs_batch(struct repository *r,\n \t\t\t\t size_t batch_size)\n {\n \tuint32_t i;\n-\tsize_t total_size;\n+\tuint64_t remaining = batch_size;\n \tstruct repack_info *pack_info;\n \tint pack_kept_objects = 0;\n\n@@ -1695,23 +1695,23 @@ static void fill_included_packs_batch(struct repository *r,\n\n \tQSORT(pack_info, m->num_packs, compare_by_mtime);\n\n-\ttotal_size = 0;\n-\tfor (i = 0; total_size < batch_size && i < m->num_packs; i++) {\n+\tfor (i = 0; i < m->num_packs; i++) {\n \t\tint pack_int_id = pack_info[i].pack_int_id;\n \t\tstruct packed_git *p = m->packs[pack_int_id];\n-\t\tsize_t expected_size;\n+\t\tuint64_t expected_size, factor;\n\n \t\tif (!want_included_pack(r, m, pack_kept_objects, pack_int_id))\n \t\t\tcontinue;\n\n-\t\texpected_size = st_mult(p->pack_size,\n-\t\t\t\t\tpack_info[i].referenced_objects);\n-\t\texpected_size /= p->num_objects;\n+\t\tfactor = pack_info[i].referenced_objects / p->num_objects;\n+\t\tif (p->pack_size > UINT64_MAX / factor)\n+\t\t\tdie(...);\n\n-\t\tif (expected_size >= batch_size)\n-\t\t\tcontinue;\n+\t\texpected_size = p->pack_size * factor;\n+\t\tif (expected_size > remaining)\n+\t\t\tbreak;\n\n-\t\ttotal_size += expected_size;\n+\t\tremaining -= expected_size;\n \t\tinclude_pack[pack_int_id] = 1;\n \t}\n--- >8 ---\n\nThat reduces the two overflow checks down to one, and avoids the need to\nintroduce a uint64_t-specific variant of the st_add() function.\n\nThanks,\nTaylor\n"},{"id":"518511","messageId":"aCzCsv61ET4u7JOK@nand.local","threadId":"63485","inReplyTo":"688b0273604179b5bebe3748445158e09a7bf1a0.1747753388.git.phillip.wood@dunelm.org.uk","subject":"Re: [PATCH 3/4] midx: avoid negative array index","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2025-05-20T17:58:10Z","receivedAt":"2025-05-20T17:58:12Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Tue, May 20, 2025 at 04:04:26PM +0100, Phillip Wood wrote:\n> From: Phillip Wood \n>\n> nth_midxed_pack_int_id() returns the index of the pack file in the multi\n> pack index's list of packfiles that the specified object. The index is\n> returned as a uint32_t. Storing this in an int will make the index\n> negative if the most significant bit is set. Fix this by using uint32_t\n> as the rest of the code does. This is unlikely to be a practical problem\n> as it requires the multipack index to reference 2^31 packfiles.\n>\n> Signed-off-by: Phillip Wood \n> ---\n> midx-write.c | 4 ++--\n> 1 file changed, 2 insertions(+), 2 deletions(-)\n>\n> diff --git a/midx-write.c b/midx-write.c\n> index 2ee381e8fcd..38a458d7322 100644\n> --- a/midx-write.c\n> +++ b/midx-write.c\n> @@ -1566,7 +1566,7 @@ int expire_midx_packs(struct repository *r, const char *object_dir, unsigned fla\n> \t\t\t\t\t _(\"Counting referenced objects\"),\n> \t\t\t\t\t m->num_objects);\n> \tfor (i = 0; i < m->num_objects; i++) {\n> -\t\tint pack_int_id = nth_midxed_pack_int_id(m, i);\n> +\t\tuint32_t pack_int_id = nth_midxed_pack_int_id(m, i);\n> \t\tcount[pack_int_id]++;\n> \t\tdisplay_progress(progress, i + 1);\n> \t}\n> @@ -1697,7 +1697,7 @@ static void fill_included_packs_batch(struct repository *r,\n>\n> \ttotal_size = 0;\n> \tfor (i = 0; total_size < batch_size && i < m->num_packs; i++) {\n> -\t\tint pack_int_id = pack_info[i].pack_int_id;\n> +\t\tuint32_t pack_int_id = pack_info[i].pack_int_id;\n> \t\tstruct packed_git *p = m->packs[pack_int_id];\n> \t\tuint64_t expected_size;\n>\n> --\n> 2.49.0.897.gfad3eb7d210\n>\n\nThanks for catching these. I was going to comment on it as something I\nnoticed while reading the first patch, but I'm glad that you addressed\nit here.\n\nIt looks like these two declarations date back to:\n\n - 19575c7c8e (multi-pack-index: implement 'expire' subcommand, 2019-06-10)\n - ce1e4a105b (midx: implement midx_repack(), 2019-06-10)\n\n(both of which were merged via 4308d81d45 (Merge branch\n'ds/midx-expire-repack', 2019-07-19)). But I think these have always had\nthe wrong type, since the pack_int_id field comes from commit fe1ed56f5e\n(midx: sort and deduplicate objects from packfiles, 2018-07-12), where\nit was first introduced as a uint32_t.\n\nI actually think these all should size_t's since they're indexing into\nan array, but that can be dealt with outside of this series, since this\nis an obvious improvement.\n\nThanks,\nTaylor\n"},{"id":"518517","messageId":"aCzDCEK7OhCYyAZa@nand.local","threadId":"63485","inReplyTo":"9f07da4fe71d21b14226d8f0132cd3c8600fba13.1747753388.git.phillip.wood@dunelm.org.uk","subject":"Re: [PATCH 2/4] midx repack: avoid potential integer overflow on 64 bit systems","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2025-05-20T17:59:36Z","receivedAt":"2025-05-20T17:59:39Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Tue, May 20, 2025 at 04:04:25PM +0100, Phillip Wood wrote:\n> From: Phillip Wood \n>\n> On a 64 bit system the calculation\n>\n> p->pack_size * pack_info[i].referenced_objects\n>\n> could overflow. If a pack file contains 2^28 objects with an average\n> compressed size of 1KB then the pack size will be 2^38B. If all of the\n> objects are referenced by the multi-pack index the sum above will\n> overflow. Avoid this by using shifted integer arithmetic and changing\n> the order of the calculation so that the pack size is divided by the\n> total number of objects in the pack before multiplying by the number of\n> objects referenced by the multi-pack index. Using a shift of 14 bits\n> should give reasonable accuracy while avoiding overflow for pack sizes\n> less that 1PB.\n\nAhhh, this renders some of comments on the previous patch moot. I think\nthat this is a not-unreasonable concern to be addressing even on modern\n64-bit systems, since I have definitely encountered packs that have on\nthe order of ~2^28 objects in them.\n\nI like this approach quite a bit, thanks!\n\nThanks,\nTaylor\n"},{"id":"518518","messageId":"aCzE58GaA0uviPSs@nand.local","threadId":"63485","inReplyTo":"29769df1c601c77031a27f3b3e5b571d5d7d043e.1747753388.git.phillip.wood@dunelm.org.uk","subject":"Re: [PATCH 4/4] midx docs: clarify tie breaking","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2025-05-20T18:07:35Z","receivedAt":"2025-05-20T18:07:37Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Tue, May 20, 2025 at 04:04:27PM +0100, Phillip Wood wrote:\n> From: Phillip Wood \n>\n> Clarify what happens when an object exists in more than one pack, but\n> not in the preferred pack. If the user does not pass a preferred pack\n> then the pack with the lowest mtime is chosen as the preferred pack. For\n> objects that are not in the preferred pack the pack with the highest\n> mtime is used. \"git multi-pack-index repack\" relies on this behavior. If\n> ties were resolved in favor of the oldest pack as the current\n> documentation suggests the multi-pack index would not reference any of\n> the objects in the pack created by \"git multi-pack-index repack\".\n\nThis commit message could likely be shortened since it is repeating some\ninformation from the patch content itself, but I don't have a strong\nopinion here.\n\n> Signed-off-by: Phillip Wood \n> ---\n> Documentation/git-multi-pack-index.adoc | 6 ++++--\n> 1 file changed, 4 insertions(+), 2 deletions(-)\n>\n> diff --git a/Documentation/git-multi-pack-index.adoc b/Documentation/git-multi-pack-index.adoc\n> index 631d5c7d15c..1f016b2f682 100644\n> --- a/Documentation/git-multi-pack-index.adoc\n> +++ b/Documentation/git-multi-pack-index.adoc\n> @@ -40,8 +40,10 @@ write::\n> \t--preferred-pack=::\n> \t\tOptionally specify the tie-breaking pack used when\n> \t\tmultiple packs contain the same object. `` must\n> -\t\tcontain at least one object. If not given, ties are\n> -\t\tbroken in favor of the pack with the lowest mtime.\n> +\t\tcontain at least one object. If not given the pack with\n> +\t\tthe lowest mtime is used as the preferred pack. Ties\n> +\t\tfor objects that are not contained in the preferred\n> +\t\tare resolved in favor of the pack with the newest mtime.\n\nI think the clarification here is good, but the structure makes it a\nlittle difficult to follow. The above reads to me like:\n\n 1. What does --preferred-pack do?\n 2. What restrictions are there on the pack?\n 3. What happens if --preferred-pack is not given?\n 4. What happens if the preferred pack does not contain the object?\n\nBut I think it might be clearer to structure this like:\n\n 1. What does --preferred-pack do for objects in the preferred pack?\n 2. What happens if the preferred pack does not contain the object?\n 3. What happens if --preferred-pack is not given?\n 4. What restrictions are there on the pack?\n\nI tried to write something like this below:\n\n When specified, break ties in favor of this pack when there are\n additional copies of its objects in other packs. Ties for objects\n not found in the preferred pack are resolved in favor of the copy in\n the pack with the highest mtime. If unspecified, the pack with the\n lowest mtime is used by default. The preferred pack must have at\n least one object.\n\nI think that the result here is a little easier to follow than what's\nproposed above, but I am obviously biased ;-). If you think the two are\nequivalent or mine is less clear than yours, feel free to ignore this.\n\nThanks,\nTaylor\n"},{"id":"518563","messageId":"CALnO6CAMqVvHbY2sR_+dt8vYHxDn4S7f4B2jq+HcMEXx7SLj9Q@mail.gmail.com","threadId":"63485","inReplyTo":"cbc5e69b908cef3800569abe79cb9c107f72bfec.1747753388.git.phillip.wood@dunelm.org.uk","subject":"Re: [PATCH 1/4] midx repack: avoid integer overflow on 32 bit systems","fromName":"D. Ben Knoble","fromEmail":"ben.knoble@gmail.com","sentAt":"2025-05-21T13:10:58Z","receivedAt":"2025-05-21T13:11:17Z","isPatch":true,"sender":{"key":"ben.knoble@gmail.com","avatar":"https://avatars.githubusercontent.com/u/22802209?v=4"},"body":"On Tue, May 20, 2025 at 11:05 AM Phillip Wood wrote:\n>\n> From: Phillip Wood \n>\n> On a 32 bit system \"git multi-pack-index --repack --batch-size=120M\"\n> failed with\n>\n> fatal: size_t overflow: 6038786 * 1289\n>\n> The calculation to estimated size of the objects in the pack referenced\n> by the multi-pack-index uses st_mult() to multiply the pack size by the\n> number of referenced objects before dividing by the total number of\n> objects in the pack. As size_t is 32 bits on 32 bit systems this\n> calculation easily overflows. Fix this by using 64bit arithmetic instead.\n>\n> Also fix a potential overflow when caluculating the total size of the\n> objects referenced by the multipack index with a batch size larger\n> than SIZE_MAX / 2. In that case\n>\n> total_size += estimated_size\n>\n> can overflow as both total_size and estimated_size can be greater that\n> SIZE_MAX / 2. This is addressed by using saturating arithmetic for the\n> addition.\n>\n> Signed-off-by: Phillip Wood \n> ---\n> git-compat-util.h | 16 ++++++++++++++++\n> midx-write.c | 12 ++++++++----\n> 2 files changed, 24 insertions(+), 4 deletions(-)\n>\n> diff --git a/git-compat-util.h b/git-compat-util.h\n> index 36b9577c8d4..4678e21c4cb 100644\n> --- a/git-compat-util.h\n> +++ b/git-compat-util.h\n> @@ -668,6 +668,22 @@ static inline int cast_size_t_to_int(size_t a)\n> return (int)a;\n> }\n>\n> +static inline uint64_t u64_mult(uint64_t a, uint64_t b)\n> +{\n> + if (unsigned_mult_overflows(a, b))\n> + die(\"uint64_t overflow: %\"PRIuMAX\" * %\"PRIuMAX,\n> + (uintmax_t)a, (uintmax_t)b);\n> + return a * b;\n> +}\n> +\n> +static inline uint64_t u64_add(uint64_t a, uint64_t b)\n> +{\n> + if (unsigned_add_overflows(a, b))\n> + die(\"uint64_t overflow: %\"PRIuMAX\" + %\"PRIuMAX,\n> + (uintmax_t)a, (uintmax_t)b);\n> + return a + b;\n> +}\n> +\n> /*\n> * Limit size of IO chunks, because huge chunks only cause pain. OS X\n> * 64-bit is buggy, returning EINVAL if len >= INT_MAX; and even in\n> diff --git a/midx-write.c b/midx-write.c\n> index dd3b3070e55..c7cb2315431 100644\n> --- a/midx-write.c\n> +++ b/midx-write.c\n> @@ -1699,19 +1699,23 @@ static void fill_included_packs_batch(struct repository *r,\n> for (i = 0; total_size < batch_size && i < m->num_packs; i++) {\n> int pack_int_id = pack_info[i].pack_int_id;\n> struct packed_git *p = m->packs[pack_int_id];\n> - size_t expected_size;\n> + uint64_t expected_size;\n>\n> if (!want_included_pack(r, m, pack_kept_objects, pack_int_id))\n> continue;\n>\n> - expected_size = st_mult(p->pack_size,\n> - pack_info[i].referenced_objects);\n> + expected_size = uint64_mult(p->pack_size,\n> + pack_info[i].referenced_objects);\n> expected_size /= p->num_objects;\n>\n> if (expected_size >= batch_size)\n> continue;\n>\n> - total_size += expected_size;\n> + if (unsigned_add_overflows (total_size, (size_t)expected_size))\n\nStyle nit (only in case Taylor's approach doesn't prove better): I\nwasn't expecting a space between the function and its argument list.\n\n> + total_size = SIZE_MAX;\n> + else\n> + total_size += expected_size;\n> +\n> include_pack[pack_int_id] = 1;\n> }\n>\n> --\n> 2.49.0.897.gfad3eb7d210\n>\n>\n\n\n-- \nD. Ben Knoble\n"},{"id":"518566","messageId":"CALnO6CCAUjd=x2bJALyoPMBGeheQ=KMvc4MPx2TmNt1znxVosQ@mail.gmail.com","threadId":"63485","inReplyTo":"29769df1c601c77031a27f3b3e5b571d5d7d043e.1747753388.git.phillip.wood@dunelm.org.uk","subject":"Re: [PATCH 4/4] midx docs: clarify tie breaking","fromName":"D. Ben Knoble","fromEmail":"ben.knoble@gmail.com","sentAt":"2025-05-21T13:14:14Z","receivedAt":"2025-05-21T13:14:31Z","isPatch":true,"sender":{"key":"ben.knoble@gmail.com","avatar":"https://avatars.githubusercontent.com/u/22802209?v=4"},"body":"On Tue, May 20, 2025 at 11:15 AM Phillip Wood wrote:\n>\n> From: Phillip Wood \n>\n> Clarify what happens when an object exists in more than one pack, but\n> not in the preferred pack. If the user does not pass a preferred pack\n> then the pack with the lowest mtime is chosen as the preferred pack. For\n> objects that are not in the preferred pack the pack with the highest\n> mtime is used. \"git multi-pack-index repack\" relies on this behavior. If\n> ties were resolved in favor of the oldest pack as the current\n> documentation suggests the multi-pack index would not reference any of\n> the objects in the pack created by \"git multi-pack-index repack\".\n>\n> Signed-off-by: Phillip Wood \n> ---\n> Documentation/git-multi-pack-index.adoc | 6 ++++--\n> 1 file changed, 4 insertions(+), 2 deletions(-)\n>\n> diff --git a/Documentation/git-multi-pack-index.adoc b/Documentation/git-multi-pack-index.adoc\n> index 631d5c7d15c..1f016b2f682 100644\n> --- a/Documentation/git-multi-pack-index.adoc\n> +++ b/Documentation/git-multi-pack-index.adoc\n> @@ -40,8 +40,10 @@ write::\n> --preferred-pack=::\n> Optionally specify the tie-breaking pack used when\n> multiple packs contain the same object. `` must\n> - contain at least one object. If not given, ties are\n> - broken in favor of the pack with the lowest mtime.\n> + contain at least one object. If not given the pack with\n> + the lowest mtime is used as the preferred pack. Ties\n> + for objects that are not contained in the preferred\n> + are resolved in favor of the pack with the newest mtime.\n\nI think Taylor's reword caught this already: \"preferred [what] are\nresolved …\"? (Probably \"pack\".)\n\n>\n> --[no-]bitmap::\n> Control whether or not a multi-pack bitmap is written.\n> --\n> 2.49.0.897.gfad3eb7d210\n>\n>\n\n\n-- \nD. Ben Knoble\n"},{"id":"518585","messageId":"xmqqh61ec8j7.fsf@gitster.g","threadId":"63485","inReplyTo":"CALnO6CAMqVvHbY2sR_+dt8vYHxDn4S7f4B2jq+HcMEXx7SLj9Q@mail.gmail.com","subject":"Re: [PATCH 1/4] midx repack: avoid integer overflow on 32 bit systems","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2025-05-21T15:01:32Z","receivedAt":"2025-05-21T15:01:35Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"D. Ben Knoble\" writes:\n\n>> + if (unsigned_add_overflows (total_size, (size_t)expected_size))\n>\n> Style nit (only in case Taylor's approach doesn't prove better): I\n> wasn't expecting a space between the function and its argument list.\n\nGood eyes. I didn't notice it myself.\n\n"},{"id":"518588","messageId":"a87e6f8f-e6b3-4d91-8b0a-312962819eb4@gmail.com","threadId":"63485","inReplyTo":"aCzBvvZDS2OFJ30h@nand.local","subject":"Re: [PATCH 1/4] midx repack: avoid integer overflow on 32 bit systems","fromName":"Phillip Wood","fromEmail":"phillip.wood123@gmail.com","sentAt":"2025-05-21T15:19:59Z","receivedAt":"2025-05-21T15:20:08Z","isPatch":true,"sender":{"key":"phillip.wood@dunelm.org.uk","avatar":null},"body":"Hi Taylor\n\nOn 20/05/2025 18:54, Taylor Blau wrote:\n> On Tue, May 20, 2025 at 04:04:24PM +0100, Phillip Wood wrote:\n>> diff --git a/midx-write.c b/midx-write.c\n>> index dd3b3070e55..c7cb2315431 100644\n>> --- a/midx-write.c\n>> +++ b/midx-write.c\n>> @@ -1699,19 +1699,23 @@ static void fill_included_packs_batch(struct repository *r,\n>> \tfor (i = 0; total_size < batch_size && i < m->num_packs; i++) {\n>> \t\tint pack_int_id = pack_info[i].pack_int_id;\n>> \t\tstruct packed_git *p = m->packs[pack_int_id];\n>> -\t\tsize_t expected_size;\n>> +\t\tuint64_t expected_size;\n>>\n>> \t\tif (!want_included_pack(r, m, pack_kept_objects, pack_int_id))\n>> \t\t\tcontinue;\n>>\n>> -\t\texpected_size = st_mult(p->pack_size,\n>> -\t\t\t\t\tpack_info[i].referenced_objects);\n>> +\t\texpected_size = uint64_mult(p->pack_size,\n>> +\t\t\t\t\t pack_info[i].referenced_objects);\n> \n> Makes sense.\n> \n>> \t\texpected_size /= p->num_objects;\n>>\n>> \t\tif (expected_size >= batch_size)\n>> \t\t\tcontinue;\n>>\n>> -\t\ttotal_size += expected_size;\n>> +\t\tif (unsigned_add_overflows (total_size, (size_t)expected_size))\n>> +\t\t\ttotal_size = SIZE_MAX;\n>> +\t\telse\n>> +\t\t\ttotal_size += expected_size;\n>> +\n> \n> But this part I am not totally following. Here we have 'total_size'\n> declared as a size_t, and 'expected_size' as a uint64_t, and (on 32-bit\n> systems) down-cast to a 32-bit unsigned value.\n> \n> So if 'expected_size' is larger than SIZE_MAX, we should set\n> 'total_size' to SIZE_MAX. But that may not happen, say if\n> 'expected_size' is (2^32-1<<32). Should total_size also be declared as a\n> uint64_t here?\n\nBy this point we know that expected_size < SIZE_MAX due to the test in \nthe context lines above this change. batch_size is declared as size_t \nand to get here expected_size < batch_size. I'll add a sentence to the \ncommit message to make that clearer.\n\n> I wondered if it might be easier to count down from the given batch_size\n> instead of adding up to it (requiring the second\n> unsigned_add_overflows() check). I tried it out and got this instead:\n\nI think you're right that we if we counted down we'd need one less \ncomparison but I'm not sure if it is worth the churn. In the diff below\n\n factor = pack_info[i].referenced_objects / p->num_objects;\n\ncan only ever be zero or one as factor is declared as uint64_t so I \ndon't think it works as-is. If you're happy with the shifted-integer \napproach in the next patch I'd rather just stick with that.\n\nThanks\n\nPhillip\n\n> --- 8< ---\n> diff --git a/midx-write.c b/midx-write.c\n> index 48a4dc5e94..f81dd9ff6d 100644\n> --- a/midx-write.c\n> +++ b/midx-write.c\n> @@ -1671,7 +1671,7 @@ static void fill_included_packs_batch(struct repository *r,\n> \t\t\t\t size_t batch_size)\n> {\n> \tuint32_t i;\n> -\tsize_t total_size;\n> +\tuint64_t remaining = batch_size;\n> \tstruct repack_info *pack_info;\n> \tint pack_kept_objects = 0;\n> \n> @@ -1695,23 +1695,23 @@ static void fill_included_packs_batch(struct repository *r,\n> \n> \tQSORT(pack_info, m->num_packs, compare_by_mtime);\n> \n> -\ttotal_size = 0;\n> -\tfor (i = 0; total_size < batch_size && i < m->num_packs; i++) {\n> +\tfor (i = 0; i < m->num_packs; i++) {\n> \t\tint pack_int_id = pack_info[i].pack_int_id;\n> \t\tstruct packed_git *p = m->packs[pack_int_id];\n> -\t\tsize_t expected_size;\n> +\t\tuint64_t expected_size, factor;\n> \n> \t\tif (!want_included_pack(r, m, pack_kept_objects, pack_int_id))\n> \t\t\tcontinue;\n> \n> -\t\texpected_size = st_mult(p->pack_size,\n> -\t\t\t\t\tpack_info[i].referenced_objects);\n> -\t\texpected_size /= p->num_objects;\n> +\t\tfactor = pack_info[i].referenced_objects / p->num_objects;\n> +\t\tif (p->pack_size > UINT64_MAX / factor)\n> +\t\t\tdie(...);\n> \n> -\t\tif (expected_size >= batch_size)\n> -\t\t\tcontinue;\n> +\t\texpected_size = p->pack_size * factor;\n> +\t\tif (expected_size > remaining)\n> +\t\t\tbreak;\n> \n> -\t\ttotal_size += expected_size;\n> +\t\tremaining -= expected_size;\n> \t\tinclude_pack[pack_int_id] = 1;\n> \t}\n> --- >8 ---\n> \n> That reduces the two overflow checks down to one, and avoids the need to\n> introduce a uint64_t-specific variant of the st_add() function.\n> \n> Thanks,\n> Taylor\n"},{"id":"518589","messageId":"7302bdf8-f713-43eb-aa78-759bb1e1b6b6@gmail.com","threadId":"63485","inReplyTo":"aCzDCEK7OhCYyAZa@nand.local","subject":"Re: [PATCH 2/4] midx repack: avoid potential integer overflow on 64 bit systems","fromName":"Phillip Wood","fromEmail":"phillip.wood123@gmail.com","sentAt":"2025-05-21T15:20:27Z","receivedAt":"2025-05-21T15:20:35Z","isPatch":true,"sender":{"key":"phillip.wood@dunelm.org.uk","avatar":null},"body":"On 20/05/2025 18:59, Taylor Blau wrote:\n> On Tue, May 20, 2025 at 04:04:25PM +0100, Phillip Wood wrote:\n>> From: Phillip Wood \n>>\n>> On a 64 bit system the calculation\n>>\n>> p->pack_size * pack_info[i].referenced_objects\n>>\n>> could overflow. If a pack file contains 2^28 objects with an average\n>> compressed size of 1KB then the pack size will be 2^38B. If all of the\n>> objects are referenced by the multi-pack index the sum above will\n>> overflow. Avoid this by using shifted integer arithmetic and changing\n>> the order of the calculation so that the pack size is divided by the\n>> total number of objects in the pack before multiplying by the number of\n>> objects referenced by the multi-pack index. Using a shift of 14 bits\n>> should give reasonable accuracy while avoiding overflow for pack sizes\n>> less that 1PB.\n> \n> Ahhh, this renders some of comments on the previous patch moot. I think\n> that this is a not-unreasonable concern to be addressing even on modern\n> 64-bit systems, since I have definitely encountered packs that have on\n> the order of ~2^28 objects in them.\n\nThanks, that's good to know\n\nPhillip\n\n> I like this approach quite a bit, thanks!\n> \n> Thanks,\n> Taylor\n"},{"id":"518591","messageId":"00b03411-3a23-474a-bad3-c0c7a12d7802@gmail.com","threadId":"63485","inReplyTo":"aCzE58GaA0uviPSs@nand.local","subject":"Re: [PATCH 4/4] midx docs: clarify tie breaking","fromName":"Phillip Wood","fromEmail":"phillip.wood123@gmail.com","sentAt":"2025-05-21T15:20:33Z","receivedAt":"2025-05-21T15:20:42Z","isPatch":true,"sender":{"key":"phillip.wood@dunelm.org.uk","avatar":null},"body":"On 20/05/2025 19:07, Taylor Blau wrote:\n> On Tue, May 20, 2025 at 04:04:27PM +0100, Phillip Wood wrote:\n>> From: Phillip Wood \n>>\n>> Clarify what happens when an object exists in more than one pack, but\n>> not in the preferred pack. If the user does not pass a preferred pack\n>> then the pack with the lowest mtime is chosen as the preferred pack. For\n>> objects that are not in the preferred pack the pack with the highest\n>> mtime is used. \"git multi-pack-index repack\" relies on this behavior. If\n>> ties were resolved in favor of the oldest pack as the current\n>> documentation suggests the multi-pack index would not reference any of\n>> the objects in the pack created by \"git multi-pack-index repack\".\n> \n> This commit message could likely be shortened since it is repeating some\n> information from the patch content itself, but I don't have a strong\n> opinion here.\n\nYes there is a bit a repetition. The thing I wanted to get across is \nthat \"git multi-pack-index repack\" relies on favoring the newest pack if \nan object is not in the preferred pack.\n\n>> Signed-off-by: Phillip Wood \n>> ---\n>> Documentation/git-multi-pack-index.adoc | 6 ++++--\n>> 1 file changed, 4 insertions(+), 2 deletions(-)\n>>\n>> diff --git a/Documentation/git-multi-pack-index.adoc b/Documentation/git-multi-pack-index.adoc\n>> index 631d5c7d15c..1f016b2f682 100644\n>> --- a/Documentation/git-multi-pack-index.adoc\n>> +++ b/Documentation/git-multi-pack-index.adoc\n>> @@ -40,8 +40,10 @@ write::\n>> \t--preferred-pack=::\n>> \t\tOptionally specify the tie-breaking pack used when\n>> \t\tmultiple packs contain the same object. `` must\n>> -\t\tcontain at least one object. If not given, ties are\n>> -\t\tbroken in favor of the pack with the lowest mtime.\n>> +\t\tcontain at least one object. If not given the pack with\n>> +\t\tthe lowest mtime is used as the preferred pack. Ties\n>> +\t\tfor objects that are not contained in the preferred\n>> +\t\tare resolved in favor of the pack with the newest mtime.\n> \n> I think the clarification here is good, but the structure makes it a\n> little difficult to follow. The above reads to me like:\n> \n> 1. What does --preferred-pack do?\n> 2. What restrictions are there on the pack?\n> 3. What happens if --preferred-pack is not given?\n> 4. What happens if the preferred pack does not contain the object?\n> \n> But I think it might be clearer to structure this like:\n> \n> 1. What does --preferred-pack do for objects in the preferred pack?\n> 2. What happens if the preferred pack does not contain the object?\n> 3. What happens if --preferred-pack is not given?\n> 4. What restrictions are there on the pack?\n> \n> I tried to write something like this below:\n> \n> When specified, break ties in favor of this pack when there are\n> additional copies of its objects in other packs. Ties for objects\n> not found in the preferred pack are resolved in favor of the copy in\n\nI'm tempted to say \"are always resolved\" here to make it clear that the \nbehavior does not depend on --preferred-pack\n\n> the pack with the highest mtime. If unspecified, the pack with the\n> lowest mtime is used by default. The preferred pack must have at\n> least one object.\n> \n> I think that the result here is a little easier to follow than what's\n> proposed above, but I am obviously biased ;-). If you think the two are\n> equivalent or mine is less clear than yours, feel free to ignore this.\n\nWith the tweak above I like your version\n\nThanks\n\nPhillip\n"},{"id":"518592","messageId":"46161e73-f875-4d9d-a344-94dca2a7b01a@gmail.com","threadId":"63485","inReplyTo":"CALnO6CAMqVvHbY2sR_+dt8vYHxDn4S7f4B2jq+HcMEXx7SLj9Q@mail.gmail.com","subject":"Re: [PATCH 1/4] midx repack: avoid integer overflow on 32 bit systems","fromName":"Phillip Wood","fromEmail":"phillip.wood123@gmail.com","sentAt":"2025-05-21T15:20:49Z","receivedAt":"2025-05-21T15:20:57Z","isPatch":true,"sender":{"key":"phillip.wood@dunelm.org.uk","avatar":null},"body":"Hi Ben\n\nOn 21/05/2025 14:10, D. Ben Knoble wrote:\n> On Tue, May 20, 2025 at 11:05 AM Phillip Wood wrote:\n>> + if (unsigned_add_overflows (total_size, (size_t)expected_size))\n> \n> Style nit (only in case Taylor's approach doesn't prove better): I\n> wasn't expecting a space between the function and its argument list.\n\nGood catch, I'll fix that\n\nThanks\n\nPhillip\n"},{"id":"518663","messageId":"cover.1747929225.git.phillip.wood@dunelm.org.uk","threadId":"63485","inReplyTo":"cover.1747753388.git.phillip.wood@dunelm.org.uk","subject":"[PATCH v2 0/4] midx repack: fix overflow on 32 bit systems","fromName":"Phillip Wood","fromEmail":"phillip.wood123@gmail.com","sentAt":"2025-05-22T15:55:19Z","receivedAt":"2025-05-22T15:55:45Z","isPatch":true,"sender":{"key":"phillip.wood@dunelm.org.uk","avatar":null},"body":"From: Phillip Wood \n\nThanks to Taylor and Ben for their comments on V1.\nChanges since V1:\n\n - Patch 1: style fix and clarified commit message\n - Patch 4: reworded commit message and documentation\n\nCover Letter for V1:\n\nThis series fixes an overflow when running \"git multi-pack-index\nrepack\" on an old raspberry pi and a couple of other small issues I\nnoticed while reading the code. I'm unsure how realistic the example\nof integer overflow on 64 bit systems in patch 2 is. I'm happy to drop\nit if people who work with large repositories think its not worth\nworrying about.\n\nBase-Commit: cb96e1697ad6e54d11fc920c95f82977f8e438f8\nPublished-As: https://github.com/phillipwood/git/releases/tag/pw%2Fmidx-repack-overflow%2Fv2\nView-Changes-At: https://github.com/phillipwood/git/compare/cb96e1697...a140181bd\nFetch-It-Via: git fetch https://github.com/phillipwood/git pw/midx-repack-overflow/v2\n\n\nPhillip Wood (4):\n midx repack: avoid integer overflow on 32 bit systems\n midx repack: avoid potential integer overflow on 64 bit systems\n midx: avoid negative array index\n midx docs: clarify tie breaking\n\n Documentation/git-multi-pack-index.adoc | 11 +++++++----\n git-compat-util.h | 16 ++++++++++++++++\n midx-write.c | 22 ++++++++++++++++------\n 3 files changed, 39 insertions(+), 10 deletions(-)\n\nRange-diff against v1:\n1: cbc5e69b908 ! 1: 9a1e6c81688 midx repack: avoid integer overflow on 32 bit systems\n @@ Commit message\n \n can overflow as both total_size and estimated_size can be greater that\n SIZE_MAX / 2. This is addressed by using saturating arithmetic for the\n - addition.\n + addition. Although estimated_size is of type uint64_t by the time we\n + reach this sum it is bounded by the batch size which is of type size_t\n + and so casting estimated_size to size_t does not truncate the value.\n \n Signed-off-by: Phillip Wood \n \n @@ midx-write.c: static void fill_included_packs_batch(struct repository *r,\n \t\t\tcontinue;\n \n -\t\ttotal_size += expected_size;\n -+\t\tif (unsigned_add_overflows (total_size, (size_t)expected_size))\n ++\t\tif (unsigned_add_overflows(total_size, (size_t)expected_size))\n +\t\t\ttotal_size = SIZE_MAX;\n +\t\telse\n +\t\t\ttotal_size += expected_size;\n2: 9f07da4fe71 = 2: 54303d96c31 midx repack: avoid potential integer overflow on 64 bit systems\n3: 688b0273604 = 3: 5b6cfb9d212 midx: avoid negative array index\n4: 29769df1c60 ! 4: a140181bd57 midx docs: clarify tie breaking\n @@ Commit message\n midx docs: clarify tie breaking\n \n Clarify what happens when an object exists in more than one pack, but\n - not in the preferred pack. If the user does not pass a preferred pack\n - then the pack with the lowest mtime is chosen as the preferred pack. For\n - objects that are not in the preferred pack the pack with the highest\n - mtime is used. \"git multi-pack-index repack\" relies on this behavior. If\n - ties were resolved in favor of the oldest pack as the current\n - documentation suggests the multi-pack index would not reference any of\n - the objects in the pack created by \"git multi-pack-index repack\".\n + not in the preferred pack. \"git multi-pack-index repack\" relies on ties\n + for objects that are not in the preferred pack being resolved in favor\n + of the newest pack that contains a copy of the object. If ties were\n + resolved in favor of the oldest pack as the current documentation\n + suggests the multi-pack index would not reference any of the objects in\n + the pack created by \"git multi-pack-index repack\".\n \n + Helped-by: Taylor Blau \n Signed-off-by: Phillip Wood \n \n ## Documentation/git-multi-pack-index.adoc ##\n @@ Documentation/git-multi-pack-index.adoc: write::\n + +\n + --\n \t--preferred-pack=::\n - \t\tOptionally specify the tie-breaking pack used when\n - \t\tmultiple packs contain the same object. `` must\n +-\t\tOptionally specify the tie-breaking pack used when\n +-\t\tmultiple packs contain the same object. `` must\n -\t\tcontain at least one object. If not given, ties are\n -\t\tbroken in favor of the pack with the lowest mtime.\n -+\t\tcontain at least one object. If not given the pack with\n -+\t\tthe lowest mtime is used as the preferred pack. Ties\n -+\t\tfor objects that are not contained in the preferred\n -+\t\tare resolved in favor of the pack with the newest mtime.\n ++\t\tWhen specified, break ties in favor of this pack when\n ++\t\tthere are additional copies of its objects in other\n ++\t\tpacks. Ties for objects not found in the preferred\n ++\t\tpack are always resolved in favor of the copy in the\n ++\t\tpack with the highest mtime. If unspecified, the pack\n ++\t\twith the lowest mtime is used by default. The\n ++\t\tpreferred pack must have at least one object.\n \n \t--[no-]bitmap::\n \t\tControl whether or not a multi-pack bitmap is written.\n-- \n2.49.0.897.gfad3eb7d210\n\n"},{"id":"518664","messageId":"54303d96c31fcfde2b6db0043ee45b17223a1696.1747929225.git.phillip.wood@dunelm.org.uk","threadId":"63485","inReplyTo":"cover.1747929225.git.phillip.wood@dunelm.org.uk","subject":"[PATCH v2 2/4] midx repack: avoid potential integer overflow on 64 bit systems","fromName":"Phillip Wood","fromEmail":"phillip.wood123@gmail.com","sentAt":"2025-05-22T15:55:21Z","receivedAt":"2025-05-22T15:55:46Z","isPatch":true,"sender":{"key":"phillip.wood@dunelm.org.uk","avatar":null},"body":"From: Phillip Wood \n\nOn a 64 bit system the calculation\n\n p->pack_size * pack_info[i].referenced_objects\n\ncould overflow. If a pack file contains 2^28 objects with an average\ncompressed size of 1KB then the pack size will be 2^38B. If all of the\nobjects are referenced by the multi-pack index the sum above will\noverflow. Avoid this by using shifted integer arithmetic and changing\nthe order of the calculation so that the pack size is divided by the\ntotal number of objects in the pack before multiplying by the number of\nobjects referenced by the multi-pack index. Using a shift of 14 bits\nshould give reasonable accuracy while avoiding overflow for pack sizes\nless that 1PB.\n\nSigned-off-by: Phillip Wood \n---\n midx-write.c | 10 ++++++++--\n 1 file changed, 8 insertions(+), 2 deletions(-)\n\ndiff --git a/midx-write.c b/midx-write.c\nindex 105014a2792..8121e96f4fd 100644\n--- a/midx-write.c\n+++ b/midx-write.c\n@@ -1704,9 +1704,15 @@ static void fill_included_packs_batch(struct repository *r,\n \t\tif (!want_included_pack(r, m, pack_kept_objects, pack_int_id))\n \t\t\tcontinue;\n \n-\t\texpected_size = uint64_mult(p->pack_size,\n-\t\t\t\t\t pack_info[i].referenced_objects);\n+\t\t/*\n+\t\t * Use shifted integer arithmetic to calculate the\n+\t\t * expected pack size to ~4 significant digits without\n+\t\t * overflow for packsizes less that 1PB.\n+\t\t */\n+\t\texpected_size = (uint64_t)pack_info[i].referenced_objects << 14;\n \t\texpected_size /= p->num_objects;\n+\t\texpected_size = u64_mult(expected_size, p->pack_size);\n+\t\texpected_size = u64_add(expected_size, 1u << 13) >> 14;\n \n \t\tif (expected_size >= batch_size)\n \t\t\tcontinue;\n-- \n2.49.0.897.gfad3eb7d210\n\n"},{"id":"518665","messageId":"9a1e6c8168876d93c0184523cb467d22e391bf07.1747929225.git.phillip.wood@dunelm.org.uk","threadId":"63485","inReplyTo":"cover.1747929225.git.phillip.wood@dunelm.org.uk","subject":"[PATCH v2 1/4] midx repack: avoid integer overflow on 32 bit systems","fromName":"Phillip Wood","fromEmail":"phillip.wood123@gmail.com","sentAt":"2025-05-22T15:55:20Z","receivedAt":"2025-05-22T15:55:46Z","isPatch":true,"sender":{"key":"phillip.wood@dunelm.org.uk","avatar":null},"body":"From: Phillip Wood \n\nOn a 32 bit system \"git multi-pack-index --repack --batch-size=120M\"\nfailed with\n\n fatal: size_t overflow: 6038786 * 1289\n\nThe calculation to estimated size of the objects in the pack referenced\nby the multi-pack-index uses st_mult() to multiply the pack size by the\nnumber of referenced objects before dividing by the total number of\nobjects in the pack. As size_t is 32 bits on 32 bit systems this\ncalculation easily overflows. Fix this by using 64bit arithmetic instead.\n\nAlso fix a potential overflow when caluculating the total size of the\nobjects referenced by the multipack index with a batch size larger\nthan SIZE_MAX / 2. In that case\n\n total_size += estimated_size\n\ncan overflow as both total_size and estimated_size can be greater that\nSIZE_MAX / 2. This is addressed by using saturating arithmetic for the\naddition. Although estimated_size is of type uint64_t by the time we\nreach this sum it is bounded by the batch size which is of type size_t\nand so casting estimated_size to size_t does not truncate the value.\n\nSigned-off-by: Phillip Wood \n---\n git-compat-util.h | 16 ++++++++++++++++\n midx-write.c | 12 ++++++++----\n 2 files changed, 24 insertions(+), 4 deletions(-)\n\ndiff --git a/git-compat-util.h b/git-compat-util.h\nindex 36b9577c8d4..4678e21c4cb 100644\n--- a/git-compat-util.h\n+++ b/git-compat-util.h\n@@ -668,6 +668,22 @@ static inline int cast_size_t_to_int(size_t a)\n \treturn (int)a;\n }\n \n+static inline uint64_t u64_mult(uint64_t a, uint64_t b)\n+{\n+\tif (unsigned_mult_overflows(a, b))\n+\t\tdie(\"uint64_t overflow: %\"PRIuMAX\" * %\"PRIuMAX,\n+\t\t (uintmax_t)a, (uintmax_t)b);\n+\treturn a * b;\n+}\n+\n+static inline uint64_t u64_add(uint64_t a, uint64_t b)\n+{\n+\tif (unsigned_add_overflows(a, b))\n+\t\tdie(\"uint64_t overflow: %\"PRIuMAX\" + %\"PRIuMAX,\n+\t\t (uintmax_t)a, (uintmax_t)b);\n+\treturn a + b;\n+}\n+\n /*\n * Limit size of IO chunks, because huge chunks only cause pain. OS X\n * 64-bit is buggy, returning EINVAL if len >= INT_MAX; and even in\ndiff --git a/midx-write.c b/midx-write.c\nindex dd3b3070e55..105014a2792 100644\n--- a/midx-write.c\n+++ b/midx-write.c\n@@ -1699,19 +1699,23 @@ static void fill_included_packs_batch(struct repository *r,\n \tfor (i = 0; total_size < batch_size && i < m->num_packs; i++) {\n \t\tint pack_int_id = pack_info[i].pack_int_id;\n \t\tstruct packed_git *p = m->packs[pack_int_id];\n-\t\tsize_t expected_size;\n+\t\tuint64_t expected_size;\n \n \t\tif (!want_included_pack(r, m, pack_kept_objects, pack_int_id))\n \t\t\tcontinue;\n \n-\t\texpected_size = st_mult(p->pack_size,\n-\t\t\t\t\tpack_info[i].referenced_objects);\n+\t\texpected_size = uint64_mult(p->pack_size,\n+\t\t\t\t\t pack_info[i].referenced_objects);\n \t\texpected_size /= p->num_objects;\n \n \t\tif (expected_size >= batch_size)\n \t\t\tcontinue;\n \n-\t\ttotal_size += expected_size;\n+\t\tif (unsigned_add_overflows(total_size, (size_t)expected_size))\n+\t\t\ttotal_size = SIZE_MAX;\n+\t\telse\n+\t\t\ttotal_size += expected_size;\n+\n \t\tinclude_pack[pack_int_id] = 1;\n \t}\n \n-- \n2.49.0.897.gfad3eb7d210\n\n"},{"id":"518666","messageId":"5b6cfb9d212552918a827626cfd9065d40be30f4.1747929225.git.phillip.wood@dunelm.org.uk","threadId":"63485","inReplyTo":"cover.1747929225.git.phillip.wood@dunelm.org.uk","subject":"[PATCH v2 3/4] midx: avoid negative array index","fromName":"Phillip Wood","fromEmail":"phillip.wood123@gmail.com","sentAt":"2025-05-22T15:55:22Z","receivedAt":"2025-05-22T15:55:47Z","isPatch":true,"sender":{"key":"phillip.wood@dunelm.org.uk","avatar":null},"body":"From: Phillip Wood \n\nnth_midxed_pack_int_id() returns the index of the pack file in the multi\npack index's list of packfiles that the specified object. The index is\nreturned as a uint32_t. Storing this in an int will make the index\nnegative if the most significant bit is set. Fix this by using uint32_t\nas the rest of the code does. This is unlikely to be a practical problem\nas it requires the multipack index to reference 2^31 packfiles.\n\nSigned-off-by: Phillip Wood \n---\n midx-write.c | 4 ++--\n 1 file changed, 2 insertions(+), 2 deletions(-)\n\ndiff --git a/midx-write.c b/midx-write.c\nindex 8121e96f4fd..ba4a94950a8 100644\n--- a/midx-write.c\n+++ b/midx-write.c\n@@ -1566,7 +1566,7 @@ int expire_midx_packs(struct repository *r, const char *object_dir, unsigned fla\n \t\t\t\t\t _(\"Counting referenced objects\"),\n \t\t\t\t\t m->num_objects);\n \tfor (i = 0; i < m->num_objects; i++) {\n-\t\tint pack_int_id = nth_midxed_pack_int_id(m, i);\n+\t\tuint32_t pack_int_id = nth_midxed_pack_int_id(m, i);\n \t\tcount[pack_int_id]++;\n \t\tdisplay_progress(progress, i + 1);\n \t}\n@@ -1697,7 +1697,7 @@ static void fill_included_packs_batch(struct repository *r,\n \n \ttotal_size = 0;\n \tfor (i = 0; total_size < batch_size && i < m->num_packs; i++) {\n-\t\tint pack_int_id = pack_info[i].pack_int_id;\n+\t\tuint32_t pack_int_id = pack_info[i].pack_int_id;\n \t\tstruct packed_git *p = m->packs[pack_int_id];\n \t\tuint64_t expected_size;\n \n-- \n2.49.0.897.gfad3eb7d210\n\n"},{"id":"518667","messageId":"a140181bd575a867801d9c410ed614b1dfc7d377.1747929225.git.phillip.wood@dunelm.org.uk","threadId":"63485","inReplyTo":"cover.1747929225.git.phillip.wood@dunelm.org.uk","subject":"[PATCH v2 4/4] midx docs: clarify tie breaking","fromName":"Phillip Wood","fromEmail":"phillip.wood123@gmail.com","sentAt":"2025-05-22T15:55:23Z","receivedAt":"2025-05-22T15:55:48Z","isPatch":true,"sender":{"key":"phillip.wood@dunelm.org.uk","avatar":null},"body":"From: Phillip Wood \n\nClarify what happens when an object exists in more than one pack, but\nnot in the preferred pack. \"git multi-pack-index repack\" relies on ties\nfor objects that are not in the preferred pack being resolved in favor\nof the newest pack that contains a copy of the object. If ties were\nresolved in favor of the oldest pack as the current documentation\nsuggests the multi-pack index would not reference any of the objects in\nthe pack created by \"git multi-pack-index repack\".\n\nHelped-by: Taylor Blau \nSigned-off-by: Phillip Wood \n---\n Documentation/git-multi-pack-index.adoc | 11 +++++++----\n 1 file changed, 7 insertions(+), 4 deletions(-)\n\ndiff --git a/Documentation/git-multi-pack-index.adoc b/Documentation/git-multi-pack-index.adoc\nindex 631d5c7d15c..b6cd0d7f855 100644\n--- a/Documentation/git-multi-pack-index.adoc\n+++ b/Documentation/git-multi-pack-index.adoc\n@@ -38,10 +38,13 @@ write::\n +\n --\n \t--preferred-pack=::\n-\t\tOptionally specify the tie-breaking pack used when\n-\t\tmultiple packs contain the same object. `` must\n-\t\tcontain at least one object. If not given, ties are\n-\t\tbroken in favor of the pack with the lowest mtime.\n+\t\tWhen specified, break ties in favor of this pack when\n+\t\tthere are additional copies of its objects in other\n+\t\tpacks. Ties for objects not found in the preferred\n+\t\tpack are always resolved in favor of the copy in the\n+\t\tpack with the highest mtime. If unspecified, the pack\n+\t\twith the lowest mtime is used by default. The\n+\t\tpreferred pack must have at least one object.\n \n \t--[no-]bitmap::\n \t\tControl whether or not a multi-pack bitmap is written.\n-- \n2.49.0.897.gfad3eb7d210\n\n"},{"id":"518735","messageId":"aC/CmFzz397p7hFz@nand.local","threadId":"63485","inReplyTo":"a87e6f8f-e6b3-4d91-8b0a-312962819eb4@gmail.com","subject":"Re: [PATCH 1/4] midx repack: avoid integer overflow on 32 bit systems","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2025-05-23T00:34:32Z","receivedAt":"2025-05-23T00:34:45Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Wed, May 21, 2025 at 04:19:59PM +0100, Phillip Wood wrote:\n> > > \t\texpected_size /= p->num_objects;\n> > >\n> > > \t\tif (expected_size >= batch_size)\n> > > \t\t\tcontinue;\n> > >\n> > > -\t\ttotal_size += expected_size;\n> > > +\t\tif (unsigned_add_overflows (total_size, (size_t)expected_size))\n> > > +\t\t\ttotal_size = SIZE_MAX;\n> > > +\t\telse\n> > > +\t\t\ttotal_size += expected_size;\n> > > +\n> >\n> > But this part I am not totally following. Here we have 'total_size'\n> > declared as a size_t, and 'expected_size' as a uint64_t, and (on 32-bit\n> > systems) down-cast to a 32-bit unsigned value.\n> >\n> > So if 'expected_size' is larger than SIZE_MAX, we should set\n> > 'total_size' to SIZE_MAX. But that may not happen, say if\n> > 'expected_size' is (2^32-1<<32). Should total_size also be declared as a\n> > uint64_t here?\n>\n> By this point we know that expected_size < SIZE_MAX due to the test in the\n> context lines above this change. batch_size is declared as size_t and to get\n> here expected_size < batch_size. I'll add a sentence to the commit message\n> to make that clearer.\n\nAhh... makes sense. I don't think a comment is necessary, this should\nhave been obvious. The check you're referring to gives us the fact that\n\n expected_size < batch_size <= SIZE_MAX\n\nSo we're OK here; sorry for missing that!\n\nThanks,\nTaylor\n"},{"id":"518736","messageId":"aC/C9oQrcx/RiyP1@nand.local","threadId":"63485","inReplyTo":"cover.1747929225.git.phillip.wood@dunelm.org.uk","subject":"Re: [PATCH v2 0/4] midx repack: fix overflow on 32 bit systems","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2025-05-23T00:36:06Z","receivedAt":"2025-05-23T00:36:08Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Thu, May 22, 2025 at 04:55:19PM +0100, Phillip Wood wrote:\n> Phillip Wood (4):\n> midx repack: avoid integer overflow on 32 bit systems\n> midx repack: avoid potential integer overflow on 64 bit systems\n> midx: avoid negative array index\n> midx docs: clarify tie breaking\n>\n> Documentation/git-multi-pack-index.adoc | 11 +++++++----\n> git-compat-util.h | 16 ++++++++++++++++\n> midx-write.c | 22 ++++++++++++++++------\n> 3 files changed, 39 insertions(+), 10 deletions(-)\n>\n> Range-diff against v1:\n\nThanks, the range-diff and patches look great to me.\n\nThanks,\nTaylor\n"},{"id":"518964","messageId":"7b6ebd22-78d9-486a-8be8-3da475015a8e@gmail.com","threadId":"63485","inReplyTo":"aC/C9oQrcx/RiyP1@nand.local","subject":"Re: [PATCH v2 0/4] midx repack: fix overflow on 32 bit systems","fromName":"Phillip Wood","fromEmail":"phillip.wood123@gmail.com","sentAt":"2025-05-27T08:26:24Z","receivedAt":"2025-05-27T08:26:29Z","isPatch":true,"sender":{"key":"phillip.wood@dunelm.org.uk","avatar":null},"body":"On 23/05/2025 01:36, Taylor Blau wrote:\n> On Thu, May 22, 2025 at 04:55:19PM +0100, Phillip Wood wrote:\n>> Phillip Wood (4):\n>> midx repack: avoid integer overflow on 32 bit systems\n>> midx repack: avoid potential integer overflow on 64 bit systems\n>> midx: avoid negative array index\n>> midx docs: clarify tie breaking\n>>\n>> Documentation/git-multi-pack-index.adoc | 11 +++++++----\n>> git-compat-util.h | 16 ++++++++++++++++\n>> midx-write.c | 22 ++++++++++++++++------\n>> 3 files changed, 39 insertions(+), 10 deletions(-)\n>>\n>> Range-diff against v1:\n> \n> Thanks, the range-diff and patches look great to me.\n\nThat's great, thank you for you comments and suggestions especially with \nregard to large repositories.\n\nThanks\n\nPhillip\n"},{"id":"518997","messageId":"xmqqbjreqcut.fsf@gitster.g","threadId":"63485","inReplyTo":"7b6ebd22-78d9-486a-8be8-3da475015a8e@gmail.com","subject":"Re: [PATCH v2 0/4] midx repack: fix overflow on 32 bit systems","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2025-05-27T15:42:34Z","receivedAt":"2025-05-27T15:42:38Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Phillip Wood writes:\n\n> On 23/05/2025 01:36, Taylor Blau wrote:\n>> On Thu, May 22, 2025 at 04:55:19PM +0100, Phillip Wood wrote:\n>>> Phillip Wood (4):\n>>> midx repack: avoid integer overflow on 32 bit systems\n>>> midx repack: avoid potential integer overflow on 64 bit systems\n>>> midx: avoid negative array index\n>>> midx docs: clarify tie breaking\n>>>\n>>> Documentation/git-multi-pack-index.adoc | 11 +++++++----\n>>> git-compat-util.h | 16 ++++++++++++++++\n>>> midx-write.c | 22 ++++++++++++++++------\n>>> 3 files changed, 39 insertions(+), 10 deletions(-)\n>>>\n>>> Range-diff against v1:\n>> Thanks, the range-diff and patches look great to me.\n>\n> That's great, thank you for you comments and suggestions especially\n> with regard to large repositories.\n\nThanks, both. Let's mark the topic for next.\n\n\n"}]}