{"thread":{"id":"54636","subject":"[PATCH 0/5] handling 4GB .idx files","startedAt":"2020-11-13T05:06:34Z","lastAt":"2020-12-03T15:24:56Z","messageCount":19,"participants":["Jeff King","Johannes Schindelin","Thomas Braun","Derrick Stolee","Taylor Blau"],"isPatch":true,"patchVersion":1,"patchTotal":5},"messages":[{"id":"409844","messageId":"20201113050631.GA744608@coredump.intra.peff.net","threadId":"54636","inReplyTo":null,"subject":"[PATCH 0/5] handling 4GB .idx files","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-11-13T05:06:31Z","receivedAt":"2020-11-13T05:06:34Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"I recently ran into a case where Git could not read the pack it had\nproduced via running \"git repack\". The culprit turned out to be an .idx\nfile which crossed the 4GB barrier (in bytes, not number of objects).\nThis series fixes the problems I saw, along with similar ones I couldn't\ntrigger in practice, and protects the .idx loading code against integer\noverflows that would fool the size checks.\n\n  [1/5]: compute pack .idx byte offsets using size_t\n  [2/5]: use size_t to store pack .idx byte offsets\n  [3/5]: fsck: correctly compute checksums on idx files larger than 4GB\n  [4/5]: block-sha1: take a size_t length parameter\n  [5/5]: packfile: detect overflow in .idx file size checks\n\n block-sha1/sha1.c        |  2 +-\n block-sha1/sha1.h        |  2 +-\n builtin/index-pack.c     |  2 +-\n builtin/pack-redundant.c |  6 +++---\n pack-check.c             | 10 +++++-----\n pack-revindex.c          |  2 +-\n packfile.c               | 14 +++++++-------\n 7 files changed, 19 insertions(+), 19 deletions(-)\n\n-Peff\n"},{"id":"409845","messageId":"20201113050648.GA744691@coredump.intra.peff.net","threadId":"54636","inReplyTo":"20201113050631.GA744608@coredump.intra.peff.net","subject":"[PATCH 1/5] compute pack .idx byte offsets using size_t","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-11-13T05:06:48Z","receivedAt":"2020-11-13T05:06:51Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"A pack and its matching .idx file are limited to 2^32 objects, because\nthe pack format contains a 32-bit field to store the number of objects.\nHence we use uint32_t in the code.\n\nBut the byte count of even a .idx file can be much larger than that,\nbecause it stores at least a hash and an offset for each object. So\nusing SHA-1, a v2 .idx file will cross the 4GB boundary at 153,391,650\nobjects. This confuses load_idx(), which computes the minimum size like\nthis:\n\n  unsigned long min_size = 8 + 4*256 + nr*(hashsz + 4 + 4) + hashsz + hashsz;\n\nEven though min_size will be big enough on most 64-bit platforms, the\nactual arithmetic is done as a uint32_t, resulting in a truncation. We\nactually exceed that min_size, but then we do:\n\n  unsigned long max_size = min_size;\n  if (nr)\n          max_size += (nr - 1)*8;\n\nto account for the variable-sized table. That computation doesn't\noverflow quite so low, but with the truncation for min_size, we end up\nwith a max_size that is much smaller than our actual size. So we\ncomplain that the idx is invalid, and can't find any of its objects.\n\nWe can fix this case by casting \"nr\" to a size_t, which will do the\nmultiplication in 64-bits (assuming you're on a 64-bit platform; this\nwill never work on a 32-bit system since we couldn't map the whole .idx\nanyway). Likewise, we don't have to worry about further additions,\nbecause adding a smaller number to a size_t will convert the other side\nto a size_t.\n\nA few notes:\n\n  - obviously we could just declare \"nr\" as a size_t in the first place\n    (and likewise, packed_git.num_objects).  But it's conceptually a\n    uint32_t because of the on-disk format, and we correctly treat it\n    that way in other contexts that don't need to compute byte offsets\n    (e.g., iterating over the set of objects should and generally does\n    use a uint32_t). Switching to size_t would make all of those other\n    cases look wrong.\n\n  - it could be argued that the proper type is off_t to represent the\n    file offset. But in practice the .idx file must fit within memory,\n    because we mmap the whole thing. And the rest of the code (including\n    the idx_size variable we're comparing against) uses size_t.\n\n  - we'll add the same cast to the max_size arithmetic line. Even though\n    we're adding to a larger type, which will convert our result, the\n    multiplication is still done as a 32-bit value and can itself\n    overflow. I didn't check this with my test case, since it would need\n    an even larger pack (~530M objects), but looking at compiler output\n    shows that it works this way. The standard should agree, but I\n    couldn't find anything explicit in 6.3.1.8 (\"usual arithmetic\n    conversions\").\n\nThe case in load_idx() was the most immediate one that I was able to\ntrigger. After fixing it, looking up actual objects (including the very\nlast one in sha1 order) works in a test repo with 153,725,110 objects.\nThat's because bsearch_hash() works with uint32_t entry indices, and the\nactual byte access:\n\n  int cmp = hashcmp(table + mi * stride, sha1);\n\nis done with \"stride\" as a size_t, causing the uint32_t \"mi\" to be\npromoted to a size_t. This is the way most code will access the index\ndata.\n\nHowever, I audited all of the other byte-wise accesses of\npacked_git.index_data, and many of the others are suspect (they are\nsimilar to the max_size one, where we are adding to a properly sized\noffset or directly to a pointer, but the multiplication in the\nsub-expression can overflow). I didn't trigger any of these in practice,\nbut I believe they're potential problems, and certainly adding in the\ncast is not going to hurt anything here.\n\nSigned-off-by: Jeff King <peff@peff.net>\n---\n builtin/index-pack.c |  2 +-\n pack-check.c         |  2 +-\n pack-revindex.c      |  2 +-\n packfile.c           | 12 ++++++------\n 4 files changed, 9 insertions(+), 9 deletions(-)\n\ndiff --git a/builtin/index-pack.c b/builtin/index-pack.c\nindex 0d03cb442d..4b8d86e0ad 100644\n--- a/builtin/index-pack.c\n+++ b/builtin/index-pack.c\n@@ -1597,7 +1597,7 @@ static void read_v2_anomalous_offsets(struct packed_git *p,\n \n \t/* The address of the 4-byte offset table */\n \tidx1 = (((const uint32_t *)((const uint8_t *)p->index_data + p->crc_offset))\n-\t\t+ p->num_objects /* CRC32 table */\n+\t\t+ (size_t)p->num_objects /* CRC32 table */\n \t\t);\n \n \t/* The address of the 8-byte offset table */\ndiff --git a/pack-check.c b/pack-check.c\nindex dad6d8ae7f..db3adf8781 100644\n--- a/pack-check.c\n+++ b/pack-check.c\n@@ -39,7 +39,7 @@ int check_pack_crc(struct packed_git *p, struct pack_window **w_curs,\n \t} while (len);\n \n \tindex_crc = p->index_data;\n-\tindex_crc += 2 + 256 + p->num_objects * (the_hash_algo->rawsz/4) + nr;\n+\tindex_crc += 2 + 256 + (size_t)p->num_objects * (the_hash_algo->rawsz/4) + nr;\n \n \treturn data_crc != ntohl(*index_crc);\n }\ndiff --git a/pack-revindex.c b/pack-revindex.c\nindex d28a7e43d0..ecdde39cf4 100644\n--- a/pack-revindex.c\n+++ b/pack-revindex.c\n@@ -130,7 +130,7 @@ static void create_pack_revindex(struct packed_git *p)\n \n \tif (p->index_version > 1) {\n \t\tconst uint32_t *off_32 =\n-\t\t\t(uint32_t *)(index + 8 + p->num_objects * (hashsz + 4));\n+\t\t\t(uint32_t *)(index + 8 + (size_t)p->num_objects * (hashsz + 4));\n \t\tconst uint32_t *off_64 = off_32 + p->num_objects;\n \t\tfor (i = 0; i < num_ent; i++) {\n \t\t\tconst uint32_t off = ntohl(*off_32++);\ndiff --git a/packfile.c b/packfile.c\nindex 0929ebe4fc..a72c2a261f 100644\n--- a/packfile.c\n+++ b/packfile.c\n@@ -148,7 +148,7 @@ int load_idx(const char *path, const unsigned int hashsz, void *idx_map,\n \t\t *  - hash of the packfile\n \t\t *  - file checksum\n \t\t */\n-\t\tif (idx_size != 4 * 256 + nr * (hashsz + 4) + hashsz + hashsz)\n+\t\tif (idx_size != 4 * 256 + (size_t)nr * (hashsz + 4) + hashsz + hashsz)\n \t\t\treturn error(\"wrong index v1 file size in %s\", path);\n \t} else if (version == 2) {\n \t\t/*\n@@ -164,10 +164,10 @@ int load_idx(const char *path, const unsigned int hashsz, void *idx_map,\n \t\t * variable sized table containing 8-byte entries\n \t\t * for offsets larger than 2^31.\n \t\t */\n-\t\tunsigned long min_size = 8 + 4*256 + nr*(hashsz + 4 + 4) + hashsz + hashsz;\n+\t\tunsigned long min_size = 8 + 4*256 + (size_t)nr*(hashsz + 4 + 4) + hashsz + hashsz;\n \t\tunsigned long max_size = min_size;\n \t\tif (nr)\n-\t\t\tmax_size += (nr - 1)*8;\n+\t\t\tmax_size += ((size_t)nr - 1)*8;\n \t\tif (idx_size < min_size || idx_size > max_size)\n \t\t\treturn error(\"wrong index v2 file size in %s\", path);\n \t\tif (idx_size != min_size &&\n@@ -1933,14 +1933,14 @@ off_t nth_packed_object_offset(const struct packed_git *p, uint32_t n)\n \tconst unsigned int hashsz = the_hash_algo->rawsz;\n \tindex += 4 * 256;\n \tif (p->index_version == 1) {\n-\t\treturn ntohl(*((uint32_t *)(index + (hashsz + 4) * n)));\n+\t\treturn ntohl(*((uint32_t *)(index + (hashsz + 4) * (size_t)n)));\n \t} else {\n \t\tuint32_t off;\n-\t\tindex += 8 + p->num_objects * (hashsz + 4);\n+\t\tindex += 8 + (size_t)p->num_objects * (hashsz + 4);\n \t\toff = ntohl(*((uint32_t *)(index + 4 * n)));\n \t\tif (!(off & 0x80000000))\n \t\t\treturn off;\n-\t\tindex += p->num_objects * 4 + (off & 0x7fffffff) * 8;\n+\t\tindex += (size_t)p->num_objects * 4 + (off & 0x7fffffff) * 8;\n \t\tcheck_pack_index_ptr(p, index);\n \t\treturn get_be64(index);\n \t}\n-- \n2.29.2.705.g306f91dc4e\n\n"},{"id":"409846","messageId":"20201113050701.GB744691@coredump.intra.peff.net","threadId":"54636","inReplyTo":"20201113050631.GA744608@coredump.intra.peff.net","subject":"[PATCH 2/5] use size_t to store pack .idx byte offsets","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-11-13T05:07:01Z","receivedAt":"2020-11-13T05:07:04Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"We sometimes store the offset into a pack .idx file as an \"unsigned\nlong\", but the mmap'd size of a pack .idx file can exceed 4GB. This is\nsufficient on LP64 systems like Linux, but will be too small on LLP64\nsystems like Windows, where \"unsigned long\" is still only 32 bits. Let's\nuse size_t, which is a better type for an offset into a memory buffer.\n\nSigned-off-by: Jeff King <peff@peff.net>\n---\n builtin/pack-redundant.c | 6 +++---\n packfile.c               | 4 ++--\n 2 files changed, 5 insertions(+), 5 deletions(-)\n\ndiff --git a/builtin/pack-redundant.c b/builtin/pack-redundant.c\nindex 178e3409b7..3e70f2a4c1 100644\n--- a/builtin/pack-redundant.c\n+++ b/builtin/pack-redundant.c\n@@ -236,7 +236,7 @@ static struct pack_list * pack_list_difference(const struct pack_list *A,\n \n static void cmp_two_packs(struct pack_list *p1, struct pack_list *p2)\n {\n-\tunsigned long p1_off = 0, p2_off = 0, p1_step, p2_step;\n+\tsize_t p1_off = 0, p2_off = 0, p1_step, p2_step;\n \tconst unsigned char *p1_base, *p2_base;\n \tstruct llist_item *p1_hint = NULL, *p2_hint = NULL;\n \tconst unsigned int hashsz = the_hash_algo->rawsz;\n@@ -280,7 +280,7 @@ static void cmp_two_packs(struct pack_list *p1, struct pack_list *p2)\n static size_t sizeof_union(struct packed_git *p1, struct packed_git *p2)\n {\n \tsize_t ret = 0;\n-\tunsigned long p1_off = 0, p2_off = 0, p1_step, p2_step;\n+\tsize_t p1_off = 0, p2_off = 0, p1_step, p2_step;\n \tconst unsigned char *p1_base, *p2_base;\n \tconst unsigned int hashsz = the_hash_algo->rawsz;\n \n@@ -499,7 +499,7 @@ static void scan_alt_odb_packs(void)\n static struct pack_list * add_pack(struct packed_git *p)\n {\n \tstruct pack_list l;\n-\tunsigned long off = 0, step;\n+\tsize_t off = 0, step;\n \tconst unsigned char *base;\n \n \tif (!p->pack_local && !(alt_odb || verbose))\ndiff --git a/packfile.c b/packfile.c\nindex a72c2a261f..63fe9ee8be 100644\n--- a/packfile.c\n+++ b/packfile.c\n@@ -164,8 +164,8 @@ int load_idx(const char *path, const unsigned int hashsz, void *idx_map,\n \t\t * variable sized table containing 8-byte entries\n \t\t * for offsets larger than 2^31.\n \t\t */\n-\t\tunsigned long min_size = 8 + 4*256 + (size_t)nr*(hashsz + 4 + 4) + hashsz + hashsz;\n-\t\tunsigned long max_size = min_size;\n+\t\tsize_t min_size = 8 + 4*256 + (size_t)nr*(hashsz + 4 + 4) + hashsz + hashsz;\n+\t\tsize_t max_size = min_size;\n \t\tif (nr)\n \t\t\tmax_size += ((size_t)nr - 1)*8;\n \t\tif (idx_size < min_size || idx_size > max_size)\n-- \n2.29.2.705.g306f91dc4e\n\n"},{"id":"409847","messageId":"20201113050714.GC744691@coredump.intra.peff.net","threadId":"54636","inReplyTo":"20201113050631.GA744608@coredump.intra.peff.net","subject":"[PATCH 3/5] fsck: correctly compute checksums on idx files larger than 4GB","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-11-13T05:07:14Z","receivedAt":"2020-11-13T05:07:16Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"When checking the trailing checksum hash of a .idx file, we pass the\nwhole buffer (minus the trailing hash) into a single call to\nthe_hash_algo->update_fn(). But we cast it to an \"unsigned int\". This\ncomes from c4001d92be (Use off_t when we really mean a file offset.,\n2007-03-06). That commit started storing the index_size variable as an\noff_t, but our mozilla-sha1 implementation from the time was limited to\na smaller size. Presumably the cast was a way of annotating that we\nexpected .idx files to be small, and so we didn't need to loop (as we do\nfor arbitrarily-large .pack files). Though as an aside it was still\nwrong, because the mozilla function actually took a signed int.\n\nThese days our hash-update functions are defined to take a size_t, so we\ncan pass the whole buffer in directly. The cast is actually causing a\nbuggy truncation!\n\nWhile we're here, though, let's drop the confusing off_t variable in the\nfirst place. We're getting the size not from the filesystem anyway, but\nfrom p->index_size, which is a size_t. In fact, we can make the code a\nbit more readable by dropping our local variable duplicating\np->index_size, and instead have one that stores the size of the actual\nindex data, minus the trailing hash.\n\nSigned-off-by: Jeff King <peff@peff.net>\n---\n pack-check.c | 8 ++++----\n 1 file changed, 4 insertions(+), 4 deletions(-)\n\ndiff --git a/pack-check.c b/pack-check.c\nindex db3adf8781..4b089fe8ec 100644\n--- a/pack-check.c\n+++ b/pack-check.c\n@@ -164,22 +164,22 @@ static int verify_packfile(struct repository *r,\n \n int verify_pack_index(struct packed_git *p)\n {\n-\toff_t index_size;\n+\tsize_t len;\n \tconst unsigned char *index_base;\n \tgit_hash_ctx ctx;\n \tunsigned char hash[GIT_MAX_RAWSZ];\n \tint err = 0;\n \n \tif (open_pack_index(p))\n \t\treturn error(\"packfile %s index not opened\", p->pack_name);\n-\tindex_size = p->index_size;\n \tindex_base = p->index_data;\n+\tlen = p->index_size - the_hash_algo->rawsz;\n \n \t/* Verify SHA1 sum of the index file */\n \tthe_hash_algo->init_fn(&ctx);\n-\tthe_hash_algo->update_fn(&ctx, index_base, (unsigned int)(index_size - the_hash_algo->rawsz));\n+\tthe_hash_algo->update_fn(&ctx, index_base, len);\n \tthe_hash_algo->final_fn(hash, &ctx);\n-\tif (!hasheq(hash, index_base + index_size - the_hash_algo->rawsz))\n+\tif (!hasheq(hash, index_base + len))\n \t\terr = error(\"Packfile index for %s hash mismatch\",\n \t\t\t    p->pack_name);\n \treturn err;\n-- \n2.29.2.705.g306f91dc4e\n\n"},{"id":"409848","messageId":"20201113050717.GD744691@coredump.intra.peff.net","threadId":"54636","inReplyTo":"20201113050631.GA744608@coredump.intra.peff.net","subject":"[PATCH 4/5] block-sha1: take a size_t length parameter","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-11-13T05:07:17Z","receivedAt":"2020-11-13T05:07:19Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"The block-sha1 implementation takes an \"unsigned long\" for the length of\na buffer to hash, but our hash algorithm wrappers take a size_t, as do\nother implementations we support like openssl or sha1dc. On many\nsystems, including Linux, these two are equivalent, but they are not on\nWindows (where only a \"long long\" is 64 bits). As a result, passing\nlarge chunks to a single the_hash_algo->update_fn() would produce wrong\nanswers there.\n\nNote that we don't need to update any other sizes outside of the\nfunction interface. We store the cumulative size in a \"long long\" (which\nwe must do since we hash things bigger than 4GB, like packfiles, even on\n32-bit platforms). And internally, we break that size_t len down into\n64-byte blocks to feed into the guts of the algorithm.\n\nSigned-off-by: Jeff King <peff@peff.net>\n---\n block-sha1/sha1.c | 2 +-\n block-sha1/sha1.h | 2 +-\n 2 files changed, 2 insertions(+), 2 deletions(-)\n\ndiff --git a/block-sha1/sha1.c b/block-sha1/sha1.c\nindex 22b125cf8c..8681031402 100644\n--- a/block-sha1/sha1.c\n+++ b/block-sha1/sha1.c\n@@ -203,7 +203,7 @@ void blk_SHA1_Init(blk_SHA_CTX *ctx)\n \tctx->H[4] = 0xc3d2e1f0;\n }\n \n-void blk_SHA1_Update(blk_SHA_CTX *ctx, const void *data, unsigned long len)\n+void blk_SHA1_Update(blk_SHA_CTX *ctx, const void *data, size_t len)\n {\n \tunsigned int lenW = ctx->size & 63;\n \ndiff --git a/block-sha1/sha1.h b/block-sha1/sha1.h\nindex 4df6747752..9fb0441b98 100644\n--- a/block-sha1/sha1.h\n+++ b/block-sha1/sha1.h\n@@ -13,7 +13,7 @@ typedef struct {\n } blk_SHA_CTX;\n \n void blk_SHA1_Init(blk_SHA_CTX *ctx);\n-void blk_SHA1_Update(blk_SHA_CTX *ctx, const void *dataIn, unsigned long len);\n+void blk_SHA1_Update(blk_SHA_CTX *ctx, const void *dataIn, size_t len);\n void blk_SHA1_Final(unsigned char hashout[20], blk_SHA_CTX *ctx);\n \n #define platform_SHA_CTX\tblk_SHA_CTX\n-- \n2.29.2.705.g306f91dc4e\n\n"},{"id":"409849","messageId":"20201113050719.GE744691@coredump.intra.peff.net","threadId":"54636","inReplyTo":"20201113050631.GA744608@coredump.intra.peff.net","subject":"[PATCH 5/5] packfile: detect overflow in .idx file size checks","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-11-13T05:07:19Z","receivedAt":"2020-11-13T05:07:21Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"In load_idx(), we check that the .idx file is sized appropriately for\nthe number of objects it claims to have. We recently fixed the case\nwhere the number of objects caused our expected size to overflow a\n32-bit unsigned int, and we switched to size_t.\n\nOn a 64-bit system, this is fine; our size_t covers any expected size.\nOn a 32-bit system, though, it won't. The file may claim to have 2^31\nobjects, which will overflow even a size_t.\n\nThis doesn't hurt us at all for a well-formed idx file. A 32-bit system\nwould already have failed to mmap such a file, since it would be too\nbig. But an .idx file which _claims_ to have 2^31 objects but is\nactually much smaller would fool our check.\n\nThis is a broken file, and for the most part we don't care that much\nwhat happens. But:\n\n  - it's a little friendlier to notice up front \"woah, this file is\n    broken\" than it is to get nonsense results\n\n  - later access of the data assumes that the loading function\n    sanity-checked that we have at least enough bytes for the regular\n    object-id table. A malformed .idx file could lead to an\n    out-of-bounds read.\n\nSo let's use our overflow-checking functions to make sure that we're not\nfooled by a malformed file.\n\nSigned-off-by: Jeff King <peff@peff.net>\n---\n packfile.c | 6 +++---\n 1 file changed, 3 insertions(+), 3 deletions(-)\n\ndiff --git a/packfile.c b/packfile.c\nindex 63fe9ee8be..9702b1218b 100644\n--- a/packfile.c\n+++ b/packfile.c\n@@ -148,7 +148,7 @@ int load_idx(const char *path, const unsigned int hashsz, void *idx_map,\n \t\t *  - hash of the packfile\n \t\t *  - file checksum\n \t\t */\n-\t\tif (idx_size != 4 * 256 + (size_t)nr * (hashsz + 4) + hashsz + hashsz)\n+\t\tif (idx_size != st_add(4 * 256 + hashsz + hashsz, st_mult(nr, hashsz + 4)))\n \t\t\treturn error(\"wrong index v1 file size in %s\", path);\n \t} else if (version == 2) {\n \t\t/*\n@@ -164,10 +164,10 @@ int load_idx(const char *path, const unsigned int hashsz, void *idx_map,\n \t\t * variable sized table containing 8-byte entries\n \t\t * for offsets larger than 2^31.\n \t\t */\n-\t\tsize_t min_size = 8 + 4*256 + (size_t)nr*(hashsz + 4 + 4) + hashsz + hashsz;\n+\t\tsize_t min_size = st_add(8 + 4*256 + hashsz + hashsz, st_mult(nr, hashsz + 4 + 4));\n \t\tsize_t max_size = min_size;\n \t\tif (nr)\n-\t\t\tmax_size += ((size_t)nr - 1)*8;\n+\t\t\tmax_size = st_add(max_size, st_mult(nr - 1, 8));\n \t\tif (idx_size < min_size || idx_size > max_size)\n \t\t\treturn error(\"wrong index v2 file size in %s\", path);\n \t\tif (idx_size != min_size &&\n-- \n2.29.2.705.g306f91dc4e\n"},{"id":"409866","messageId":"nycvar.QRO.7.76.6.2011131200460.18437@tvgsbejvaqbjf.bet","threadId":"54636","inReplyTo":"20201113050719.GE744691@coredump.intra.peff.net","subject":"Re: [PATCH 5/5] packfile: detect overflow in .idx file size checks","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2020-11-13T11:02:41Z","receivedAt":"2020-11-13T11:17:05Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi Peff,\n\nOn Fri, 13 Nov 2020, Jeff King wrote:\n\n> diff --git a/packfile.c b/packfile.c\n> index 63fe9ee8be..9702b1218b 100644\n> --- a/packfile.c\n> +++ b/packfile.c\n> @@ -148,7 +148,7 @@ int load_idx(const char *path, const unsigned int hashsz, void *idx_map,\n>  \t\t *  - hash of the packfile\n>  \t\t *  - file checksum\n>  \t\t */\n> -\t\tif (idx_size != 4 * 256 + (size_t)nr * (hashsz + 4) + hashsz + hashsz)\n> +\t\tif (idx_size != st_add(4 * 256 + hashsz + hashsz, st_mult(nr, hashsz + 4)))\n>  \t\t\treturn error(\"wrong index v1 file size in %s\", path);\n>  \t} else if (version == 2) {\n>  \t\t/*\n> @@ -164,10 +164,10 @@ int load_idx(const char *path, const unsigned int hashsz, void *idx_map,\n>  \t\t * variable sized table containing 8-byte entries\n>  \t\t * for offsets larger than 2^31.\n>  \t\t */\n> -\t\tsize_t min_size = 8 + 4*256 + (size_t)nr*(hashsz + 4 + 4) + hashsz + hashsz;\n> +\t\tsize_t min_size = st_add(8 + 4*256 + hashsz + hashsz, st_mult(nr, hashsz + 4 + 4));\n>  \t\tsize_t max_size = min_size;\n>  \t\tif (nr)\n> -\t\t\tmax_size += ((size_t)nr - 1)*8;\n> +\t\t\tmax_size = st_add(max_size, st_mult(nr - 1, 8));\n\nI wondered about these multiplications and whether we should use the\n`st_*()` helpers, when reading 1/5. And I am glad I read on!\n\nFWIW I like all five patches.\n\nThanks,\nDscho\n\n>  \t\tif (idx_size < min_size || idx_size > max_size)\n>  \t\t\treturn error(\"wrong index v2 file size in %s\", path);\n>  \t\tif (idx_size != min_size &&\n> --\n> 2.29.2.705.g306f91dc4e\n>\n"},{"id":"409973","messageId":"323fd904-a7ee-061d-d846-5da5afbc88b2@virtuell-zuhause.de","threadId":"54636","inReplyTo":"20201113050631.GA744608@coredump.intra.peff.net","subject":"Re: [PATCH 0/5] handling 4GB .idx files","fromName":"Thomas Braun","fromEmail":"thomas.braun@virtuell-zuhause.de","sentAt":"2020-11-15T14:43:39Z","receivedAt":"2020-11-15T14:44:07Z","isPatch":true,"sender":{"key":"thomas.braun@virtuell-zuhause.de","avatar":"https://avatars.githubusercontent.com/u/1185677?v=4"},"body":"On 13.11.2020 06:06, Jeff King wrote:\n> I recently ran into a case where Git could not read the pack it had\n> produced via running \"git repack\". The culprit turned out to be an .idx\n> file which crossed the 4GB barrier (in bytes, not number of objects).\n> This series fixes the problems I saw, along with similar ones I couldn't\n> trigger in practice, and protects the .idx loading code against integer\n> overflows that would fool the size checks.\n\nWould it be feasible to have a test case for this large index case? This\nshould very certainly have an EXPENSIVE tag, or might even not yet work\non windows. But hopefully someday I'll find some more time to push large\nobject support on windows forward, and these kind of tests would really\nhelp then.\n"},{"id":"409981","messageId":"20201116041051.GA883199@coredump.intra.peff.net","threadId":"54636","inReplyTo":"323fd904-a7ee-061d-d846-5da5afbc88b2@virtuell-zuhause.de","subject":"Re: [PATCH 0/5] handling 4GB .idx files","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-11-16T04:10:51Z","receivedAt":"2020-11-16T04:11:13Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sun, Nov 15, 2020 at 03:43:39PM +0100, Thomas Braun wrote:\n\n> On 13.11.2020 06:06, Jeff King wrote:\n> > I recently ran into a case where Git could not read the pack it had\n> > produced via running \"git repack\". The culprit turned out to be an .idx\n> > file which crossed the 4GB barrier (in bytes, not number of objects).\n> > This series fixes the problems I saw, along with similar ones I couldn't\n> > trigger in practice, and protects the .idx loading code against integer\n> > overflows that would fool the size checks.\n> \n> Would it be feasible to have a test case for this large index case? This\n> should very certainly have an EXPENSIVE tag, or might even not yet work\n> on windows. But hopefully someday I'll find some more time to push large\n> object support on windows forward, and these kind of tests would really\n> help then.\n\nI think it would be a level beyond what we usually consider even for\nEXPENSIVE. The cheapest I could come up with to generate the case is:\n\n  perl -e '\n\tfor (0..154_000_000) {\n\t\tprint \"blob\\n\";\n\t\tprint \"data <<EOF\\n\";\n\t\tprint \"$_\\n\";\n\t\tprint \"EOF\\n\";\n\t}\n  ' |\n  git fast-import\n\nwhich took almost 13 minutes of CPU to run, and peaked around 15GB of\nRAM (and takes about 6.7GB on disk).\n\nIn the resulting repo, the old code barfed on lookups:\n\n  $ blob=$(echo 0 | git hash-object --stdin)\n  $ git cat-file blob $blob\n  error: wrong index v2 file size in .git/objects/pack/pack-f8f43ae56c25c1c8ff49ad6320df6efb393f551e.idx\n  error: wrong index v2 file size in .git/objects/pack/pack-f8f43ae56c25c1c8ff49ad6320df6efb393f551e.idx\n  error: wrong index v2 file size in .git/objects/pack/pack-f8f43ae56c25c1c8ff49ad6320df6efb393f551e.idx\n  error: wrong index v2 file size in .git/objects/pack/pack-f8f43ae56c25c1c8ff49ad6320df6efb393f551e.idx\n  error: wrong index v2 file size in .git/objects/pack/pack-f8f43ae56c25c1c8ff49ad6320df6efb393f551e.idx\n  error: wrong index v2 file size in .git/objects/pack/pack-f8f43ae56c25c1c8ff49ad6320df6efb393f551e.idx\n  fatal: git cat-file 573541ac9702dd3969c9bc859d2b91ec1f7e6e56: bad file\n\nwhereas now it works:\n\n  $ git cat-file blob $blob\n  0\n\nThat's the most basic test I think you could do. More interesting is\nlooking at entries that are actually after the 4GB mark. That requires\ndumping the whole index:\n\n  final=$(git show-index <.git/objects/pack/*.idx | tail -1 | awk '{print $2}')\n  git cat-file blob $final\n\nThat takes ~35s to run. Curiously, it also allocates 5GB of heap. For\nsome reason it decides to make an internal copy of the entries table. I\nguess because it reads the file sequentially rather than mmap-ing it,\nand 64-bit offsets in v2 idx files can't be resolved until we've read\nthe whole entry table (and it wants to output the entries in sha1\norder).\n\nThe checksum bug requires running git-fsck on the repo. That's another 5\nminutes of CPU (and even higher peak memory; I think we create a \"struct\nblob\" for each one, and it seems to hit 20GB).\n\nHitting the other cases that I fixed but never triggered in practice\nwould need a repo about 4x as large. So figure an hour of CPU and 60GB\nof RAM.\n\nSo I dunno. I wouldn't be opposed to codifying some of that in a script,\nbut I can't imagine anybody ever running it unless they were working on\nthis specific problem.\n\n-Peff\n"},{"id":"410010","messageId":"42080870-1a92-e76f-d83a-f15642a96329@gmail.com","threadId":"54636","inReplyTo":"20201116041051.GA883199@coredump.intra.peff.net","subject":"Re: [PATCH 0/5] handling 4GB .idx files","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2020-11-16T13:30:34Z","receivedAt":"2020-11-16T13:31:05Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 11/15/2020 11:10 PM, Jeff King wrote:\n> On Sun, Nov 15, 2020 at 03:43:39PM +0100, Thomas Braun wrote:\n> \n>> On 13.11.2020 06:06, Jeff King wrote:\n>>> I recently ran into a case where Git could not read the pack it had\n>>> produced via running \"git repack\". The culprit turned out to be an .idx\n>>> file which crossed the 4GB barrier (in bytes, not number of objects).\n>>> This series fixes the problems I saw, along with similar ones I couldn't\n>>> trigger in practice, and protects the .idx loading code against integer\n>>> overflows that would fool the size checks.\n>>\n>> Would it be feasible to have a test case for this large index case? This\n>> should very certainly have an EXPENSIVE tag, or might even not yet work\n>> on windows. But hopefully someday I'll find some more time to push large\n>> object support on windows forward, and these kind of tests would really\n>> help then.\n> \n> I think it would be a level beyond what we usually consider even for\n> EXPENSIVE. The cheapest I could come up with to generate the case is:\n\nI agree that the cost of this test is more than I would expect for\nEXPENSIVE.\n\n>   perl -e '\n> \tfor (0..154_000_000) {\n> \t\tprint \"blob\\n\";\n> \t\tprint \"data <<EOF\\n\";\n> \t\tprint \"$_\\n\";\n> \t\tprint \"EOF\\n\";\n> \t}\n>   ' |\n>   git fast-import\n> \n> which took almost 13 minutes of CPU to run, and peaked around 15GB of\n> RAM (and takes about 6.7GB on disk).\n\nI was thinking that maybe the RAM requirements would be lower\nif we batched the fast-import calls and then repacked, but then\nthe repack would probably be just as expensive.\n\n> In the resulting repo, the old code barfed on lookups:\n> \n>   $ blob=$(echo 0 | git hash-object --stdin)\n>   $ git cat-file blob $blob\n>   error: wrong index v2 file size in .git/objects/pack/pack-f8f43ae56c25c1c8ff49ad6320df6efb393f551e.idx\n>   error: wrong index v2 file size in .git/objects/pack/pack-f8f43ae56c25c1c8ff49ad6320df6efb393f551e.idx\n>   error: wrong index v2 file size in .git/objects/pack/pack-f8f43ae56c25c1c8ff49ad6320df6efb393f551e.idx\n>   error: wrong index v2 file size in .git/objects/pack/pack-f8f43ae56c25c1c8ff49ad6320df6efb393f551e.idx\n>   error: wrong index v2 file size in .git/objects/pack/pack-f8f43ae56c25c1c8ff49ad6320df6efb393f551e.idx\n>   error: wrong index v2 file size in .git/objects/pack/pack-f8f43ae56c25c1c8ff49ad6320df6efb393f551e.idx\n>   fatal: git cat-file 573541ac9702dd3969c9bc859d2b91ec1f7e6e56: bad file\n> \n> whereas now it works:\n> \n>   $ git cat-file blob $blob\n>   0\n> \n> That's the most basic test I think you could do. More interesting is\n> looking at entries that are actually after the 4GB mark. That requires\n> dumping the whole index:\n> \n>   final=$(git show-index <.git/objects/pack/*.idx | tail -1 | awk '{print $2}')\n>   git cat-file blob $final\n\nCould you also (after running the test once) determine the largest\nSHA-1, at least up to unique short-SHA? Then run something like\n\n\tgit cat-file blob fffffe\n\nSince your loop is hard-coded, you could even use the largest full\nSHA-1.\n\nNaturally, nothing short of a full .idx verification would be\ncompletely sound, and we are already generating an enormous repo.\n\n> So I dunno. I wouldn't be opposed to codifying some of that in a script,\n> but I can't imagine anybody ever running it unless they were working on\n> this specific problem.\n\nIt would be good to have this available somewhere in the codebase to\nrun whenever testing .idx changes. Perhaps create a new prerequisite\nspecifically for EXPENSIVE_IDX tests, triggered only by a GIT_TEST_*\nenvironment variable?\n\nIt would be helpful to also write a multi-pack-index on top of this\n.idx to ensure we can handle that case, too.\n\nThanks,\n-Stolee\n"},{"id":"410048","messageId":"20201116234939.GA5051@coredump.intra.peff.net","threadId":"54636","inReplyTo":"42080870-1a92-e76f-d83a-f15642a96329@gmail.com","subject":"Re: [PATCH 0/5] handling 4GB .idx files","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-11-16T23:49:39Z","receivedAt":"2020-11-16T23:49:42Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Nov 16, 2020 at 08:30:34AM -0500, Derrick Stolee wrote:\n\n> > which took almost 13 minutes of CPU to run, and peaked around 15GB of\n> > RAM (and takes about 6.7GB on disk).\n> \n> I was thinking that maybe the RAM requirements would be lower\n> if we batched the fast-import calls and then repacked, but then\n> the repack would probably be just as expensive.\n\nI think it's even worse. Fast-import just holds enough data to create\nthe index (sha1, etc), but pack-objects is also holding data to support\nthe delta search, etc. A quick (well, quick to invoke, not to run):\n\n   git show-index <.git/objects/pack/pack-*.idx |\n   awk '{print $2}' |\n   git pack-objects foo --all-progress\n\non the fast-import pack seems to cap out around 27GB.\n\nI doubt you could do much better overall than fast-import in terms of\nCPU. The trick is really that you need to have a matching content/sha1\npair for 154M objects, and that's where most of the time goes. If we\nlied about what's in each object (just generating an index with sha1\n...0001, ...0002, etc), we could go much faster. But it's a much less\ninteresting test then.\n\n> > That's the most basic test I think you could do. More interesting is\n> > looking at entries that are actually after the 4GB mark. That requires\n> > dumping the whole index:\n> > \n> >   final=$(git show-index <.git/objects/pack/*.idx | tail -1 | awk '{print $2}')\n> >   git cat-file blob $final\n> \n> Could you also (after running the test once) determine the largest\n> SHA-1, at least up to unique short-SHA? Then run something like\n> \n> \tgit cat-file blob fffffe\n> \n> Since your loop is hard-coded, you could even use the largest full\n> SHA-1.\n\nThat $final is the highest sha1. We could hard-code it, yes (and the\nresulting lookup via cat-file is quite fast; it's the linear index dump\nthat's slow). We'd need the matching sha256 version, too. But it's\nreally the generation of the data that's the main issue.\n\n> Naturally, nothing short of a full .idx verification would be\n> completely sound, and we are already generating an enormous repo.\n\nYep.\n\n> > So I dunno. I wouldn't be opposed to codifying some of that in a script,\n> > but I can't imagine anybody ever running it unless they were working on\n> > this specific problem.\n> \n> It would be good to have this available somewhere in the codebase to\n> run whenever testing .idx changes. Perhaps create a new prerequisite\n> specifically for EXPENSIVE_IDX tests, triggered only by a GIT_TEST_*\n> environment variable?\n\nMy feeling is that anybody who's really interested in playing with this\ntopic can find this thread in the archive. I don't think they're really\nany worse off there than with a bit-rotting script in the repo that\nnobody ever runs.\n\nBut if somebody wants to write up a test script, I'm happy to review it.\n\n> It would be helpful to also write a multi-pack-index on top of this\n> .idx to ensure we can handle that case, too.\n\nI did run \"git multi-pack-index write\" on the resulting repo, which\ncompleted in a reasonable amount of time (maybe 30-60s). And then\nconfirmed that lookups in the midx work just fine.\n\n-Peff\n"},{"id":"411016","messageId":"1403797985.37893.1606777048311@ox.hosteurope.de","threadId":"54636","inReplyTo":"20201116041051.GA883199@coredump.intra.peff.net","subject":"Re: [PATCH 0/5] handling 4GB .idx files","fromName":"Thomas Braun","fromEmail":"thomas.braun@virtuell-zuhause.de","sentAt":"2020-11-30T22:57:27Z","receivedAt":"2020-11-30T22:58:13Z","isPatch":true,"sender":{"key":"thomas.braun@virtuell-zuhause.de","avatar":"https://avatars.githubusercontent.com/u/1185677?v=4"},"body":"> Jeff King <peff@peff.net> hat am 16.11.2020 05:10 geschrieben:\n\n[...]\n\n> So I dunno. I wouldn't be opposed to codifying some of that in \n> a script, but I can't imagine anybody ever running it unless they \n> were working on this specific problem.\n\nThanks for the pointers.\n\nBelow is what I came up with. It passes here. I've replaced awk with cut from the original draft, and also moved the perl script out of the test as I think the quoting is getting way too messy otherwise. And I've added --no-dangling to git fsck as otherwise it takes forever to output the obvious dangling blobs. The unpack limit is mostly for testing the test itself with a smaller amount of blobs. But I still think it is worthwile to force everything into a pack.\n\n--- a/t/t1600-index.sh\n+++ b/t/t1600-index.sh\n@@ -97,4 +97,34 @@ test_expect_success 'index version config precedence' '\n \ttest_index_version 0 true 2 2\n '\n \n+{\n+\techo \"#!$SHELL_PATH\"\n+\tcat <<'EOF'\n+\t   \"$PERL_PATH\" -e '\n+\t\tfor (0..154_000_000) {\n+\t\t\tprint \"blob\\n\";\n+\t\t\tprint \"data <<EOF\\n\";\n+\t\t\tprint \"$_\\n\";\n+\t\t\tprint \"EOF\\n\";\n+\t\t} '\n+EOF\n+\n+} >dump\n+chmod +x dump\n+\n+test_expect_success EXPENSIVE,PERL 'Test 4GB boundary for the index' '\n+\ttest_config fastimport.unpacklimit 0 &&\n+\t./dump | git fast-import &&\n+\tblob=$(echo 0 | git hash-object --stdin) &&\n+\tgit cat-file blob $blob >actual &&\n+\techo 0 >expect &&\n+\ttest_cmp expect actual &&\n+\tidx_pack=$(ls .git/objects/pack/*.idx) &&\n+\ttest_file_not_empty $idx_pack &&\n+\tfinal=$(git show-index <$idx_pack | tail -1 | cut -d \" \" -f2) &&\n+\tgit cat-file blob $final &&\n+\tgit cat-file blob fffffff &&\n+\tgit fsck --strict --no-dangling\n+'\n+\n test_done\n--\n"},{"id":"411056","messageId":"X8YnsGsUl53OKFno@coredump.intra.peff.net","threadId":"54636","inReplyTo":"1403797985.37893.1606777048311@ox.hosteurope.de","subject":"Re: [PATCH 0/5] handling 4GB .idx files","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-12-01T11:23:28Z","receivedAt":"2020-12-01T11:24:26Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Nov 30, 2020 at 11:57:27PM +0100, Thomas Braun wrote:\n\n> Below is what I came up with. It passes here. I've replaced awk with\n> cut from the original draft, and also moved the perl script out of the\n> test as I think the quoting is getting way too messy otherwise. And\n> I've added --no-dangling to git fsck as otherwise it takes forever to\n> output the obvious dangling blobs. The unpack limit is mostly for\n> testing the test itself with a smaller amount of blobs. But I still\n> think it is worthwile to force everything into a pack.\n\nI think you can get rid of some of the quoting by using perl directly as\nthe interpreter, rather than a shell script that only invokes it with\n-e. See below.\n\n> --- a/t/t1600-index.sh\n> +++ b/t/t1600-index.sh\n\nI don't think this should go in t1600; that's about testing the\n.git/index file, not a pack .idx. Probably t5302 would be more\nappropriate.\n\n> @@ -97,4 +97,34 @@ test_expect_success 'index version config precedence' '\n>  \ttest_index_version 0 true 2 2\n>  '\n>  \n> +{\n> +\techo \"#!$SHELL_PATH\"\n> +\tcat <<'EOF'\n> +\t   \"$PERL_PATH\" -e '\n> +\t\tfor (0..154_000_000) {\n> +\t\t\tprint \"blob\\n\";\n> +\t\t\tprint \"data <<EOF\\n\";\n> +\t\t\tprint \"$_\\n\";\n> +\t\t\tprint \"EOF\\n\";\n> +\t\t} '\n> +EOF\n> +\n> +} >dump\n> +chmod +x dump\n\nYou can simplify this a bit with write_script, as well. And we do prefer\nto put this stuff in a test block, so verbosity, etc, is handled\ncorrectly.\n\nI didn't let it run to completion, but something like this seems to\nwork:\n\ndiff --git a/t/t1600-index.sh b/t/t1600-index.sh\nindex 6d83aaf8a4..a4c1dc0f0a 100755\n--- a/t/t1600-index.sh\n+++ b/t/t1600-index.sh\n@@ -97,23 +97,16 @@ test_expect_success 'index version config precedence' '\n \ttest_index_version 0 true 2 2\n '\n \n-{\n-\techo \"#!$SHELL_PATH\"\n-\tcat <<'EOF'\n-\t   \"$PERL_PATH\" -e '\n-\t\tfor (0..154_000_000) {\n-\t\t\tprint \"blob\\n\";\n-\t\t\tprint \"data <<EOF\\n\";\n-\t\t\tprint \"$_\\n\";\n-\t\t\tprint \"EOF\\n\";\n-\t\t} '\n-EOF\n-\n-} >dump\n-chmod +x dump\n-\n test_expect_success EXPENSIVE,PERL 'Test 4GB boundary for the index' '\n \ttest_config fastimport.unpacklimit 0 &&\n+\twrite_script dump \"$PERL_PATH\" <<-\\EOF &&\n+\tfor (0..154_000_000) {\n+\t\tprint \"blob\\n\";\n+\t\tprint \"data <<EOF\\n\";\n+\t\tprint \"$_\\n\";\n+\t\tprint \"EOF\\n\";\n+\t}\n+\tEOF\n \t./dump | git fast-import &&\n \tblob=$(echo 0 | git hash-object --stdin) &&\n \tgit cat-file blob $blob >actual &&\n\n> +test_expect_success EXPENSIVE,PERL 'Test 4GB boundary for the index' '\n\nYou can drop the PERL prereq. Even without it set, we assume that we can\ndo basic perl one-liners that would work even in old versions of perl.\n\nI'm not sure if EXPENSIVE is the right ballpark, or if we'd want a\nVERY_EXPENSIVE. On my machine, the whole test suite for v2.29.0 takes 64\nseconds to run, and setting GIT_TEST_LONG=1 bumps that to 103s. It got a\nbit worse since then, as t7900 adds an EXPENSIVE test that takes ~200s\n(it's not strictly additive, since we can work in parallel on other\ntests for the first bit, but still, yuck).\n\nSo we're looking at 2-3x to run the expensive tests now. This new one\nwould be 20x or more. I'm not sure if anybody would care or not (i.e.,\nwhether anyone actually runs the whole suite with this flag). I thought\nwe did for some CI job, but it looks like it's just the one-off in\nt5608.\n\n> +\tgit cat-file blob $final &&\n> +\tgit cat-file blob fffffff &&\n\nThis final cat-file may be a problem when tested with SHA-256. You are\nrelying on the fact that there is exactly one object that matches seven\nf's as its prefix. That may be true for SHA-1, but if so it's mostly\nluck.  Seven hex digits is only 28 bits, which is ~260M. For 154M\nobjects, we'd expect an average of 0.57 objects per 7-digit prefix. So I\nwouldn't be at all surprised if there are two of them for SHA-256.\n\nI'm also not sure what it's testing that the $final one isn't.\n\n-Peff\n"},{"id":"411058","messageId":"X8YrbDpC9/EjRr95@coredump.intra.peff.net","threadId":"54636","inReplyTo":"X8YnsGsUl53OKFno@coredump.intra.peff.net","subject":"t7900's new expensive test","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-12-01T11:39:24Z","receivedAt":"2020-12-01T11:40:22Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Dec 01, 2020 at 06:23:28AM -0500, Jeff King wrote:\n\n> I'm not sure if EXPENSIVE is the right ballpark, or if we'd want a\n> VERY_EXPENSIVE. On my machine, the whole test suite for v2.29.0 takes 64\n> seconds to run, and setting GIT_TEST_LONG=1 bumps that to 103s. It got a\n> bit worse since then, as t7900 adds an EXPENSIVE test that takes ~200s\n> (it's not strictly additive, since we can work in parallel on other\n> tests for the first bit, but still, yuck).\n\nSince Stolee is on the cc and has already seen me complaining about his\ntest, I guess I should expand a bit. ;)\n\nThere are some small wins possible (e.g., using \"commit --quiet\" seems\nto shave off ~8s when we don't even think about writing a diff), but\nfundamentally the issue is that it just takes a long time to \"git add\"\nthe 5.2GB worth of random data. I almost wonder if it would be worth it\nto hard-coded the known sha1 and sha256 names of the blobs, and write\nthem straight into the appropriate loose object file. I guess that is\ntricky, though, because it actually needs to be a zlib stream, not just\nthe output of \"test-tool genrandom\".\n\nThough speaking of which, another easy win might be setting\ncore.compression to \"0\". We know the random data won't compress anyway,\nso there's no point in spending cycles on zlib.\n\nDoing this:\n\ndiff --git a/t/t7900-maintenance.sh b/t/t7900-maintenance.sh\nindex d9e68bb2bf..849c6d1361 100755\n--- a/t/t7900-maintenance.sh\n+++ b/t/t7900-maintenance.sh\n@@ -239,6 +239,8 @@ test_expect_success 'incremental-repack task' '\n '\n \n test_expect_success EXPENSIVE 'incremental-repack 2g limit' '\n+\ttest_config core.compression 0 &&\n+\n \tfor i in $(test_seq 1 5)\n \tdo\n \t\ttest-tool genrandom foo$i $((512 * 1024 * 1024 + 1)) >>big ||\n@@ -257,7 +259,7 @@ test_expect_success EXPENSIVE 'incremental-repack 2g limit' '\n \t\treturn 1\n \tdone &&\n \tgit add big &&\n-\tgit commit -m \"Add big file (2)\" &&\n+\tgit commit -qm \"Add big file (2)\" &&\n \n \t# ensure any possible loose objects are in a pack-file\n \tgit maintenance run --task=loose-objects &&\n\nseems to shave off ~140s from the test. I think we could get a little\nmore by cleaning up the enormous objects, too (they end up causing the\nsubsequent test to run slower, too, though perhaps it was intentional to\nimpact downstream tests).\n\n-Peff\n"},{"id":"411076","messageId":"X8aLDlzcNCwP699c@nand.local","threadId":"54636","inReplyTo":"X8YnsGsUl53OKFno@coredump.intra.peff.net","subject":"Re: [PATCH 0/5] handling 4GB .idx files","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2020-12-01T18:27:26Z","receivedAt":"2020-12-01T18:28:17Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Tue, Dec 01, 2020 at 06:23:28AM -0500, Jeff King wrote:\n> I'm not sure if EXPENSIVE is the right ballpark, or if we'd want a\n> VERY_EXPENSIVE. On my machine, the whole test suite for v2.29.0 takes 64\n> seconds to run, and setting GIT_TEST_LONG=1 bumps that to 103s. It got a\n> bit worse since then, as t7900 adds an EXPENSIVE test that takes ~200s\n> (it's not strictly additive, since we can work in parallel on other\n> tests for the first bit, but still, yuck).\n>\n> So we're looking at 2-3x to run the expensive tests now. This new one\n> would be 20x or more. I'm not sure if anybody would care or not (i.e.,\n> whether anyone actually runs the whole suite with this flag). I thought\n> we did for some CI job, but it looks like it's just the one-off in\n> t5608.\n\nI had written something similar yesterday before mutt crashed and I\ndecided to stop work for the day.\n\nI have a sense that probably very few people actually run GIT_TEST_LONG\nregularly, and that that group may vanish entirely if we added a test\nwhich increased the runtime of the suite by 20x in this mode.\n\nI have mixed feelings about VERY_EXPENSIVE. On one hand, having this\ntest checked in so that we can quickly refer back to it in the case of a\nregression is useful. On the other hand, what is it worth to have this\nin-tree if nobody ever runs it? I'm speculating about whether or not\npeople would run this, of course.\n\nMy hunch is that anybody who is interested enough to fix regressions in\nthis area would be able to refer back to the list archive to dig up this\nthread and recover the script.\n\nI don't feel strongly, really, but just noting some light objections to\nchecking this test into the suite.\n\nThanks,\nTaylor\n"},{"id":"411101","messageId":"373f3dfe-828b-430d-b88e-5e23302090cb@gmail.com","threadId":"54636","inReplyTo":"X8YrbDpC9/EjRr95@coredump.intra.peff.net","subject":"Re: t7900's new expensive test","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2020-12-01T20:55:00Z","receivedAt":"2020-12-01T20:55:44Z","isPatch":false,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 12/1/2020 6:39 AM, Jeff King wrote:\n> On Tue, Dec 01, 2020 at 06:23:28AM -0500, Jeff King wrote:\n> \n>> I'm not sure if EXPENSIVE is the right ballpark, or if we'd want a\n>> VERY_EXPENSIVE. On my machine, the whole test suite for v2.29.0 takes 64\n>> seconds to run, and setting GIT_TEST_LONG=1 bumps that to 103s. It got a\n>> bit worse since then, as t7900 adds an EXPENSIVE test that takes ~200s\n>> (it's not strictly additive, since we can work in parallel on other\n>> tests for the first bit, but still, yuck).\n> \n> Since Stolee is on the cc and has already seen me complaining about his\n> test, I guess I should expand a bit. ;)\n\nHa. I apologize for causing pain here. My thought was that GIT_TEST_LONG=1\nwas only used by someone really willing to wait, or someone specifically\ntrying to investigate a problem that only triggers on very large cases.\n\nIn that sense, it's not so much intended as a frequently-run regression\ntest, but a \"run this if you are messing with this area\" kind of thing.\nPerhaps there is a different pattern to use here?\n\n> There are some small wins possible (e.g., using \"commit --quiet\" seems\n> to shave off ~8s when we don't even think about writing a diff), but\n> fundamentally the issue is that it just takes a long time to \"git add\"\n> the 5.2GB worth of random data. I almost wonder if it would be worth it\n> to hard-coded the known sha1 and sha256 names of the blobs, and write\n> them straight into the appropriate loose object file. I guess that is\n> tricky, though, because it actually needs to be a zlib stream, not just\n> the output of \"test-tool genrandom\".\n>\n> Though speaking of which, another easy win might be setting\n> core.compression to \"0\". We know the random data won't compress anyway,\n> so there's no point in spending cycles on zlib.\n\nThe intention is mostly to expand the data beyond two gigabytes, so\ndropping compression to get there seems like a good idea. If we are\nnot compressing at all, then perhaps we can reliably cut ourselves\ncloser to the 2GB limit instead of overshooting as a precaution.\n \n> Doing this:\n> \n> diff --git a/t/t7900-maintenance.sh b/t/t7900-maintenance.sh\n> index d9e68bb2bf..849c6d1361 100755\n> --- a/t/t7900-maintenance.sh\n> +++ b/t/t7900-maintenance.sh\n> @@ -239,6 +239,8 @@ test_expect_success 'incremental-repack task' '\n>  '\n>  \n>  test_expect_success EXPENSIVE 'incremental-repack 2g limit' '\n> +\ttest_config core.compression 0 &&\n> +\n>  \tfor i in $(test_seq 1 5)\n>  \tdo\n>  \t\ttest-tool genrandom foo$i $((512 * 1024 * 1024 + 1)) >>big ||\n> @@ -257,7 +259,7 @@ test_expect_success EXPENSIVE 'incremental-repack 2g limit' '\n>  \t\treturn 1\n>  \tdone &&\n>  \tgit add big &&\n> -\tgit commit -m \"Add big file (2)\" &&\n> +\tgit commit -qm \"Add big file (2)\" &&\n>  \n>  \t# ensure any possible loose objects are in a pack-file\n>  \tgit maintenance run --task=loose-objects &&\n> \n> seems to shave off ~140s from the test. I think we could get a little\n> more by cleaning up the enormous objects, too (they end up causing the\n> subsequent test to run slower, too, though perhaps it was intentional to\n> impact downstream tests).\n\nCutting out 70% out seems like a great idea. I don't think it was super\nintentional to slow down those tests.\n\nThanks,\n-Stolee\n\n"},{"id":"411137","messageId":"X8cAXHJRm+Xz9PFM@coredump.intra.peff.net","threadId":"54636","inReplyTo":"373f3dfe-828b-430d-b88e-5e23302090cb@gmail.com","subject":"[PATCH] t7900: speed up expensive test","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-12-02T02:47:56Z","receivedAt":"2020-12-02T02:48:40Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Dec 01, 2020 at 03:55:00PM -0500, Derrick Stolee wrote:\n\n> > Since Stolee is on the cc and has already seen me complaining about his\n> > test, I guess I should expand a bit. ;)\n> \n> Ha. I apologize for causing pain here. My thought was that GIT_TEST_LONG=1\n> was only used by someone really willing to wait, or someone specifically\n> trying to investigate a problem that only triggers on very large cases.\n> \n> In that sense, it's not so much intended as a frequently-run regression\n> test, but a \"run this if you are messing with this area\" kind of thing.\n> Perhaps there is a different pattern to use here?\n\nNo, I think your interpretation is pretty reasonable. I definitely do\nnot run with GIT_TEST_LONG normally, but was only poking at it because\nof the other discussion.\n\n> > Though speaking of which, another easy win might be setting\n> > core.compression to \"0\". We know the random data won't compress anyway,\n> > so there's no point in spending cycles on zlib.\n> \n> The intention is mostly to expand the data beyond two gigabytes, so\n> dropping compression to get there seems like a good idea. If we are\n> not compressing at all, then perhaps we can reliably cut ourselves\n> closer to the 2GB limit instead of overshooting as a precaution.\n\nProbably, though I think at best we could save 20% of the test cost. I\ndidn't play much with it.\n\n> Cutting out 70% out seems like a great idea. I don't think it was super\n> intentional to slow down those tests.\n\nHere it is as a patch (the numbers are slightly different this time\nbecause I used my usual ramdisk, but the overall improvement is roughly\nthe same).\n\nI didn't look into whether it should be cleaning up (test 16 takes\nlonger, too, because of the extra on-disk bytes). I also noticed while\nrunning with \"-v\" that it complains of corrupted refs. I assume this is\nleftover cruft from earlier tests, and I didn't dig into it. But it may\nbe something worth cleaning up for somebody more familiar with these\ntests.\n\n-- >8 --\nSubject: [PATCH] t7900: speed up expensive test\n\nA test marked with EXPENSIVE creates two 2.5GB files and adds them to\nthe repository. This takes 194s to run on my machine, versus 2s when the\nEXPENSIVE prereq isn't set. We can trim this down a bit by doing two\nthings:\n\n  - use \"git commit --quiet\" to avoid spending time generating a diff\n    summary (this actually only helps for the second commit, but I've\n    added it here to both for consistency). This shaves off 8s.\n\n  - set core.compression to 0. We know these files are full of random\n    bytes, and so won't compress (that's the point of the test!).\n    Spending cycles on zlib is pointless. This shaves off 122s.\n\nAfter this, my total time to run the script is 64s. That won't help\nnormal runs without GIT_TEST_LONG set, of course, but it's easy enough\nto do.\n\nSigned-off-by: Jeff King <peff@peff.net>\n---\n t/t7900-maintenance.sh | 6 ++++--\n 1 file changed, 4 insertions(+), 2 deletions(-)\n\ndiff --git a/t/t7900-maintenance.sh b/t/t7900-maintenance.sh\nindex d9e68bb2bf..d9a02df686 100755\n--- a/t/t7900-maintenance.sh\n+++ b/t/t7900-maintenance.sh\n@@ -239,13 +239,15 @@ test_expect_success 'incremental-repack task' '\n '\n \n test_expect_success EXPENSIVE 'incremental-repack 2g limit' '\n+\ttest_config core.compression 0 &&\n+\n \tfor i in $(test_seq 1 5)\n \tdo\n \t\ttest-tool genrandom foo$i $((512 * 1024 * 1024 + 1)) >>big ||\n \t\treturn 1\n \tdone &&\n \tgit add big &&\n-\tgit commit -m \"Add big file (1)\" &&\n+\tgit commit -qm \"Add big file (1)\" &&\n \n \t# ensure any possible loose objects are in a pack-file\n \tgit maintenance run --task=loose-objects &&\n@@ -257,7 +259,7 @@ test_expect_success EXPENSIVE 'incremental-repack 2g limit' '\n \t\treturn 1\n \tdone &&\n \tgit add big &&\n-\tgit commit -m \"Add big file (2)\" &&\n+\tgit commit -qm \"Add big file (2)\" &&\n \n \t# ensure any possible loose objects are in a pack-file\n \tgit maintenance run --task=loose-objects &&\n-- \n2.29.2.894.g2dadb8c6b8\n\n"},{"id":"411162","messageId":"X8eS1Zrqk99AjKkD@coredump.intra.peff.net","threadId":"54636","inReplyTo":"X8aLDlzcNCwP699c@nand.local","subject":"Re: [PATCH 0/5] handling 4GB .idx files","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-12-02T13:12:53Z","receivedAt":"2020-12-02T13:13:49Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Dec 01, 2020 at 01:27:26PM -0500, Taylor Blau wrote:\n\n> I have a sense that probably very few people actually run GIT_TEST_LONG\n> regularly, and that that group may vanish entirely if we added a test\n> which increased the runtime of the suite by 20x in this mode.\n\nYeah, and if that's so, then I'm OK with calling it EXPENSIVE and moving\non with our lives. And I guess merging this is one way to find out, if\nanybody screams. The stakes are low enough that I don't mind doing that.\n\n> I have mixed feelings about VERY_EXPENSIVE. On one hand, having this\n> test checked in so that we can quickly refer back to it in the case of a\n> regression is useful. On the other hand, what is it worth to have this\n> in-tree if nobody ever runs it? I'm speculating about whether or not\n> people would run this, of course.\n> \n> My hunch is that anybody who is interested enough to fix regressions in\n> this area would be able to refer back to the list archive to dig up this\n> thread and recover the script.\n> \n> I don't feel strongly, really, but just noting some light objections to\n> checking this test into the suite.\n\nYeah, that about matches my feelings. But if Thomas wants to wrap it up\nas a patch, I don't mind seeing what happens (and I think with the\nsuggestions I gave earlier, it would be in good shape).\n\n-Peff\n"},{"id":"411224","messageId":"b3bfa8df-f750-3dc9-d4e5-1bbd6a636eeb@gmail.com","threadId":"54636","inReplyTo":"X8cAXHJRm+Xz9PFM@coredump.intra.peff.net","subject":"Re: [PATCH] t7900: speed up expensive test","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2020-12-03T15:23:57Z","receivedAt":"2020-12-03T15:24:56Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 12/1/2020 9:47 PM, Jeff King wrote:\n> Subject: [PATCH] t7900: speed up expensive test\n> \n> A test marked with EXPENSIVE creates two 2.5GB files and adds them to\n> the repository. This takes 194s to run on my machine, versus 2s when the\n> EXPENSIVE prereq isn't set. We can trim this down a bit by doing two\n> things:\n> \n>   - use \"git commit --quiet\" to avoid spending time generating a diff\n>     summary (this actually only helps for the second commit, but I've\n>     added it here to both for consistency). This shaves off 8s.\n> \n>   - set core.compression to 0. We know these files are full of random\n>     bytes, and so won't compress (that's the point of the test!).\n>     Spending cycles on zlib is pointless. This shaves off 122s.\n> \n> After this, my total time to run the script is 64s. That won't help\n> normal runs without GIT_TEST_LONG set, of course, but it's easy enough\n> to do.\n\nI'm happy with these easy fixes to make the test faster without\nchanging any of the important behavior. Thanks!\n\n> Signed-off-by: Jeff King <peff@peff.net>\n> ---\n>  t/t7900-maintenance.sh | 6 ++++--\n>  1 file changed, 4 insertions(+), 2 deletions(-)\n> \n> diff --git a/t/t7900-maintenance.sh b/t/t7900-maintenance.sh\n> index d9e68bb2bf..d9a02df686 100755\n> --- a/t/t7900-maintenance.sh\n> +++ b/t/t7900-maintenance.sh\n> @@ -239,13 +239,15 @@ test_expect_success 'incremental-repack task' '\n>  '\n>  \n>  test_expect_success EXPENSIVE 'incremental-repack 2g limit' '\n> +\ttest_config core.compression 0 &&\n> +\n>  \tfor i in $(test_seq 1 5)\n>  \tdo\n>  \t\ttest-tool genrandom foo$i $((512 * 1024 * 1024 + 1)) >>big ||\n>  \t\treturn 1\n>  \tdone &&\n>  \tgit add big &&\n> -\tgit commit -m \"Add big file (1)\" &&\n> +\tgit commit -qm \"Add big file (1)\" &&\n>  \n>  \t# ensure any possible loose objects are in a pack-file\n>  \tgit maintenance run --task=loose-objects &&\n> @@ -257,7 +259,7 @@ test_expect_success EXPENSIVE 'incremental-repack 2g limit' '\n>  \t\treturn 1\n>  \tdone &&\n>  \tgit add big &&\n> -\tgit commit -m \"Add big file (2)\" &&\n> +\tgit commit -qm \"Add big file (2)\" &&\n>  \n>  \t# ensure any possible loose objects are in a pack-file\n>  \tgit maintenance run --task=loose-objects &&\n> \n\n"}]}