{"thread":{"id":"54093","subject":"[PATCH] Avoid infinite loop in malformed packfiles","startedAt":"2020-08-23T00:59:33Z","lastAt":"2020-08-31T19:23:10Z","messageCount":20,"participants":["Ori Bernstein","ori@eigenstate.org","Eric Sunshine","René Scharfe","Junio C Hamano","Jeff King"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"404265","messageId":"20200823005236.10386-1-ori@eigenstate.org","threadId":"54093","inReplyTo":null,"subject":"[PATCH] Avoid infinite loop in malformed packfiles","fromName":"Ori Bernstein","fromEmail":"ori@eigenstate.org","sentAt":"2020-08-23T00:52:36Z","receivedAt":"2020-08-23T00:59:33Z","isPatch":true,"sender":{"key":"ori@eigenstate.org","avatar":null},"body":"In packfile.c:1680, there's an infinite loop that tries to get\nto the base of a packfile. With offset deltas, the offset needs\nto be greater than 0, so it's always walking backwards, and the\nsearch is guaranteed to terminate.\n\nWith reference deltas, there's no check for a cycle in the\nreferences, so a cyclic reference will cause git to loop\ninfinitely, growing the delta_stack infinitely, which will\ncause it to consume all available memory as as a full CPU\ncore.\n\nThis change puts an arbitrary limit of 10,000 on the number\nof iterations we make when chasing down a base commit, to\nprevent looping forever, using all available memory growing\nthe delta stack.\n---\n packfile.c | 7 +++++++\n 1 file changed, 7 insertions(+)\n\ndiff --git a/packfile.c b/packfile.c\nindex 6ab5233613..321e002c50 100644\n--- a/packfile.c\n+++ b/packfile.c\n@@ -1633,6 +1633,7 @@ static void write_pack_access_log(struct packed_git *p, off_t obj_offset)\n \n int do_check_packed_object_crc;\n \n+#define UNPACK_ENTRY_STACK_LIMIT 10000\n #define UNPACK_ENTRY_STACK_PREALLOC 64\n struct unpack_entry_stack_ent {\n \toff_t obj_offset;\n@@ -1715,6 +1716,12 @@ void *unpack_entry(struct repository *r, struct packed_git *p, off_t obj_offset,\n \t\t\tbreak;\n \t\t}\n \n+\t\tif (delta_stack_nr > UNPACK_ENTRY_STACK_LIMIT) {\n+\t\t\terror(\"overlong delta chain at offset %jd from %s\",\n+\t\t\t (uintmax_t)curpos, p->pack_name);\n+\t\t\tgoto out;\n+\t\t}\n+\n \t\t/* push object, proceed to base */\n \t\tif (delta_stack_nr >= delta_stack_alloc\n \t\t && delta_stack == small_delta_stack) {\n-- \n2.27.0\n\n"},{"id":"404266","messageId":"5374D56FBAB7F3BCD976B433934DEFCA@eigenstate.org","threadId":"54093","inReplyTo":"20200823005236.10386-1-ori@eigenstate.org","subject":"Re: [PATCH] Avoid infinite loop in malformed packfiles","fromName":"","fromEmail":"ori@eigenstate.org","sentAt":"2020-08-23T02:52:35Z","receivedAt":"2020-08-23T02:52:39Z","isPatch":true,"sender":{"key":"ori@eigenstate.org","avatar":null},"body":"> In packfile.c:1680, there's an infinite loop that tries to get\n> to the base of a packfile. With offset deltas, the offset needs\n> to be greater than 0, so it's always walking backwards, and the\n> search is guaranteed to terminate.\n> \n> With reference deltas, there's no check for a cycle in the\n> references, so a cyclic reference will cause git to loop\n> infinitely, growing the delta_stack infinitely, which will\n> cause it to consume all available memory as as a full CPU\n> core.\n> \n> This change puts an arbitrary limit of 10,000 on the number\n> of iterations we make when chasing down a base commit, to\n> prevent looping forever, using all available memory growing\n> the delta stack.\n\nFor context, I discovered this accidentally when I\nintroduced a bug in pack deltification in git9 (my\nimplementation of git for plan 9). An example of a\npackfile and index that will reproduce this issue\nis available here:\n\nhttps://eigenstate.org/tmp/95a0f4f3f3f21d723d501552eaf22ff4055e13a4.pack\nhttps://eigenstate.org/tmp/95a0f4f3f3f21d723d501552eaf22ff4055e13a4.idx\n\nThe suggestion to just cap the depth instead of\ndoing full cycle detection came from Jeff King\n(peff@peff.net)\n\n"},{"id":"404267","messageId":"CAPig+cRjBXEx4ZKRiXOMKhigv6i=uds=DHc8mxSEtqtJOqkN-Q@mail.gmail.com","threadId":"54093","inReplyTo":"20200823005236.10386-1-ori@eigenstate.org","subject":"Re: [PATCH] Avoid infinite loop in malformed packfiles","fromName":"Eric Sunshine","fromEmail":"sunshine@sunshineco.com","sentAt":"2020-08-23T03:08:06Z","receivedAt":"2020-08-23T03:08:27Z","isPatch":true,"sender":{"key":"sunshine@sunshineco.com","avatar":"https://avatars.githubusercontent.com/u/163641?v=4"},"body":"On Sat, Aug 22, 2020 at 8:59 PM Ori Bernstein wrote:\n> In packfile.c:1680, there's an infinite loop that tries to get\n> to the base of a packfile. With offset deltas, the offset needs\n> to be greater than 0, so it's always walking backwards, and the\n> search is guaranteed to terminate.\n>\n> With reference deltas, there's no check for a cycle in the\n> references, so a cyclic reference will cause git to loop\n> infinitely, growing the delta_stack infinitely, which will\n> cause it to consume all available memory as as a full CPU\n> core.\n>\n> This change puts an arbitrary limit of 10,000 on the number\n> of iterations we make when chasing down a base commit, to\n> prevent looping forever, using all available memory growing\n> the delta stack.\n> ---\n\nMissing sign-off.\n"},{"id":"404268","messageId":"20200823031151.10985-1-ori@eigenstate.org","threadId":"54093","inReplyTo":"20200823005236.10386-1-ori@eigenstate.org","subject":"[PATCH] Avoid infinite loop in malformed packfiles","fromName":"Ori Bernstein","fromEmail":"ori@eigenstate.org","sentAt":"2020-08-23T03:11:52Z","receivedAt":"2020-08-23T03:12:15Z","isPatch":true,"sender":{"key":"ori@eigenstate.org","avatar":null},"body":"In packfile.c:1680, there's an infinite loop that tries to get\nto the base of a packfile. With offset deltas, the offset needs\nto be greater than 0, so it's always walking backwards, and the\nsearch is guaranteed to terminate.\n\nWith reference deltas, there's no check for a cycle in the\nreferences, so a cyclic reference will cause git to loop\ninfinitely, growing the delta_stack infinitely, which will\ncause it to consume all available memory as as a full CPU\ncore.\n\nThis change puts an arbitrary limit of 10,000 on the number\nof iterations we make when chasing down a base commit, to\nprevent looping forever, using all available memory growing\nthe delta stack.\n\nSigned-off-by: Ori Bernstein \n---\n packfile.c | 7 +++++++\n 1 file changed, 7 insertions(+)\n\ndiff --git a/packfile.c b/packfile.c\nindex 6ab5233613..321e002c50 100644\n--- a/packfile.c\n+++ b/packfile.c\n@@ -1633,6 +1633,7 @@ static void write_pack_access_log(struct packed_git *p, off_t obj_offset)\n \n int do_check_packed_object_crc;\n \n+#define UNPACK_ENTRY_STACK_LIMIT 10000\n #define UNPACK_ENTRY_STACK_PREALLOC 64\n struct unpack_entry_stack_ent {\n \toff_t obj_offset;\n@@ -1715,6 +1716,12 @@ void *unpack_entry(struct repository *r, struct packed_git *p, off_t obj_offset,\n \t\t\tbreak;\n \t\t}\n \n+\t\tif (delta_stack_nr > UNPACK_ENTRY_STACK_LIMIT) {\n+\t\t\terror(\"overlong delta chain at offset %jd from %s\",\n+\t\t\t (uintmax_t)curpos, p->pack_name);\n+\t\t\tgoto out;\n+\t\t}\n+\n \t\t/* push object, proceed to base */\n \t\tif (delta_stack_nr >= delta_stack_alloc\n \t\t && delta_stack == small_delta_stack) {\n-- \n2.27.0\n\n"},{"id":"404269","messageId":"672843a1-b98c-7567-a078-a2dacd4b7074@web.de","threadId":"54093","inReplyTo":"20200823031151.10985-1-ori@eigenstate.org","subject":"Re: [PATCH] Avoid infinite loop in malformed packfiles","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2020-08-23T06:26:14Z","receivedAt":"2020-08-23T06:26:29Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 23.08.20 um 05:11 schrieb Ori Bernstein:\n> In packfile.c:1680, there's an infinite loop that tries to get\n> to the base of a packfile. With offset deltas, the offset needs\n> to be greater than 0, so it's always walking backwards, and the\n> search is guaranteed to terminate.\n>\n> With reference deltas, there's no check for a cycle in the\n> references, so a cyclic reference will cause git to loop\n> infinitely, growing the delta_stack infinitely, which will\n> cause it to consume all available memory as as a full CPU\n> core.\n\n\"as as\"? Perhaps \"and\"?\n\n> This change puts an arbitrary limit of 10,000 on the number\n> of iterations we make when chasing down a base commit, to\n> prevent looping forever, using all available memory growing\n> the delta stack.\n>\n> Signed-off-by: Ori Bernstein \n> ---\n> packfile.c | 7 +++++++\n> 1 file changed, 7 insertions(+)\n>\n> diff --git a/packfile.c b/packfile.c\n> index 6ab5233613..321e002c50 100644\n> --- a/packfile.c\n> +++ b/packfile.c\n> @@ -1633,6 +1633,7 @@ static void write_pack_access_log(struct packed_git *p, off_t obj_offset)\n>\n> int do_check_packed_object_crc;\n>\n> +#define UNPACK_ENTRY_STACK_LIMIT 10000\n\nb5c0cbd8083 (pack-objects: use bitfield for object_entry::depth,\n2018-04-14) limited the delta depth for new packs to 4095, so 10000\nseems reasonable. Users with unreasonable packs would need to repack\nthem with an older version of Git, though. Not sure if that would\naffect anyone in practice.\n\n> #define UNPACK_ENTRY_STACK_PREALLOC 64\n\nHmm, setting a hard limit may allow to allocate the whole stack on the,\nehm, stack. That would get rid of the hybrid stack/heap allocation and\nthus simplify the code a bit. 10000 entries with 24 bytes each would be\nquite big, though, but that might be OK without recursion. (And not in\nthis patch anyway, of course.)\n\n> struct unpack_entry_stack_ent {\n> \toff_t obj_offset;\n> @@ -1715,6 +1716,12 @@ void *unpack_entry(struct repository *r, struct packed_git *p, off_t obj_offset,\n> \t\t\tbreak;\n> \t\t}\n>\n> +\t\tif (delta_stack_nr > UNPACK_ENTRY_STACK_LIMIT) {\n> +\t\t\terror(\"overlong delta chain at offset %jd from %s\",\n> +\t\t\t (uintmax_t)curpos, p->pack_name);\n> +\t\t\tgoto out;\n> +\t\t}\n\nOther error handlers in this loop set data to NULL. That's actually\nunnecessary because it's NULL to begin with and the loop is exited after\nsetting it to some other value. So not doing it here is fine. (And a\nseparate cleanup patch could remove the dead stores in the other\nhandlers.)\n\n> +\n> \t\t/* push object, proceed to base */\n> \t\tif (delta_stack_nr >= delta_stack_alloc\n> \t\t && delta_stack == small_delta_stack) {\n>\n\n"},{"id":"404302","messageId":"20200823134144.d57c80322f479eb554bab9d1@eigenstate.org","threadId":"54093","inReplyTo":"672843a1-b98c-7567-a078-a2dacd4b7074@web.de","subject":"Re: [PATCH] Avoid infinite loop in malformed packfiles","fromName":"Ori Bernstein","fromEmail":"ori@eigenstate.org","sentAt":"2020-08-23T20:41:44Z","receivedAt":"2020-08-23T20:41:47Z","isPatch":true,"sender":{"key":"ori@eigenstate.org","avatar":null},"body":"On Sun, 23 Aug 2020 08:26:14 +0200, René Scharfe wrote:\n\n> Am 23.08.20 um 05:11 schrieb Ori Bernstein:\n> > In packfile.c:1680, there's an infinite loop that tries to get\n> > to the base of a packfile. With offset deltas, the offset needs\n> > to be greater than 0, so it's always walking backwards, and the\n> > search is guaranteed to terminate.\n> >\n> > With reference deltas, there's no check for a cycle in the\n> > references, so a cyclic reference will cause git to loop\n> > infinitely, growing the delta_stack infinitely, which will\n> > cause it to consume all available memory as as a full CPU\n> > core.\n> \n> \"as as\"? Perhaps \"and\"?\n\nI think I meant 'As well as' -- will fix.\n \n> \n> b5c0cbd8083 (pack-objects: use bitfield for object_entry::depth,\n> 2018-04-14) limited the delta depth for new packs to 4095, so 10000\n> seems reasonable. Users with unreasonable packs would need to repack\n> them with an older version of Git, though. Not sure if that would\n> affect anyone in practice.\n> \n> > #define UNPACK_ENTRY_STACK_PREALLOC 64\n> \n> Hmm, setting a hard limit may allow to allocate the whole stack on the,\n> ehm, stack. That would get rid of the hybrid stack/heap allocation and\n> thus simplify the code a bit. 10000 entries with 24 bytes each would be\n> quite big, though, but that might be OK without recursion. (And not in\n> this patch anyway, of course.)\n> \n> > struct unpack_entry_stack_ent {\n> > \toff_t obj_offset;\n> > @@ -1715,6 +1716,12 @@ void *unpack_entry(struct repository *r, struct packed_git *p, off_t obj_offset,\n> > \t\t\tbreak;\n> > \t\t}\n> >\n> > +\t\tif (delta_stack_nr > UNPACK_ENTRY_STACK_LIMIT) {\n> > +\t\t\terror(\"overlong delta chain at offset %jd from %s\",\n> > +\t\t\t (uintmax_t)curpos, p->pack_name);\n> > +\t\t\tgoto out;\n> > +\t\t}\n> \n> Other error handlers in this loop set data to NULL. That's actually\n> unnecessary because it's NULL to begin with and the loop is exited after\n> setting it to some other value. So not doing it here is fine. (And a\n> separate cleanup patch could remove the dead stores in the other\n> handlers.)\n\nIs there anything you'd like me to do in this patch, other than fixing\nthe typo?\n\n-- \n Ori Bernstein\n"},{"id":"404327","messageId":"ef92391d-09ef-4c27-e6dd-ec7b907174fa@web.de","threadId":"54093","inReplyTo":"20200823134144.d57c80322f479eb554bab9d1@eigenstate.org","subject":"Re: [PATCH] Avoid infinite loop in malformed packfiles","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2020-08-24T16:06:27Z","receivedAt":"2020-08-24T16:06:55Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 23.08.20 um 22:41 schrieb Ori Bernstein:\n> On Sun, 23 Aug 2020 08:26:14 +0200, René Scharfe wrote:\n>\n>> Am 23.08.20 um 05:11 schrieb Ori Bernstein:\n>>> In packfile.c:1680, there's an infinite loop that tries to get\n>>> to the base of a packfile. With offset deltas, the offset needs\n>>> to be greater than 0, so it's always walking backwards, and the\n>>> search is guaranteed to terminate.\n>>>\n>>> With reference deltas, there's no check for a cycle in the\n>>> references, so a cyclic reference will cause git to loop\n>>> infinitely, growing the delta_stack infinitely, which will\n>>> cause it to consume all available memory as as a full CPU\n>>> core.\n>>\n>> \"as as\"? Perhaps \"and\"?\n>\n> I think I meant 'As well as' -- will fix.\n>\n>>\n>> b5c0cbd8083 (pack-objects: use bitfield for object_entry::depth,\n>> 2018-04-14) limited the delta depth for new packs to 4095, so 10000\n>> seems reasonable. Users with unreasonable packs would need to repack\n>> them with an older version of Git, though. Not sure if that would\n>> affect anyone in practice.\n\n> Is there anything you'd like me to do in this patch, other than fixing\n> the typo?\n\nPlease explain in the commit message why 10000 is a good choice for that\nnew limit, and what users who happen to exceed it can do to regain\naccess to their packed data.\n\nRené\n"},{"id":"404330","messageId":"xmqqsgcc54pq.fsf@gitster.c.googlers.com","threadId":"54093","inReplyTo":"20200823031151.10985-1-ori@eigenstate.org","subject":"Re: [PATCH] Avoid infinite loop in malformed packfiles","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2020-08-24T17:33:21Z","receivedAt":"2020-08-24T17:33:48Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Ori Bernstein writes:\n\n> diff --git a/packfile.c b/packfile.c\n> index 6ab5233613..321e002c50 100644\n> --- a/packfile.c\n> +++ b/packfile.c\n> @@ -1715,6 +1716,12 @@ void *unpack_entry(struct repository *r, struct packed_git *p, off_t obj_offset,\n> \t\t\tbreak;\n> \t\t}\n> \n> +\t\tif (delta_stack_nr > UNPACK_ENTRY_STACK_LIMIT) {\n> +\t\t\terror(\"overlong delta chain at offset %jd from %s\",\n> +\t\t\t (uintmax_t)curpos, p->pack_name);\n\nThe \"j\" length field is not used anywhere in the codebase for\nportability concerns, I think. \"d\" is for signed, but curpos\nis an unsigned off_t. I think\n\n\t\"... %\"PRIuMAX\" from %s\", (uintmax_t)curpos, ...\n\nwould match how we write this kind of thing everywhere else in the\ncode, e.g. showing obj_offset in packed_to_object_type() in the same\nfile in an error message.\n\n> @@ -1633,6 +1633,7 @@ static void write_pack_access_log(struct packed_git *p, off_t obj_offset)\n> \n> int do_check_packed_object_crc;\n> \n> +#define UNPACK_ENTRY_STACK_LIMIT 10000\n> #define UNPACK_ENTRY_STACK_PREALLOC 64\n> struct unpack_entry_stack_ent {\n> \toff_t obj_offset;\n\nWhat escape hatch would the end-users have when they have a\nlegitimate packfile that has a truly deep delta chain, by the way?\n\nThanks.\n"},{"id":"404368","messageId":"20200824201208.GA706849@coredump.intra.peff.net","threadId":"54093","inReplyTo":"ef92391d-09ef-4c27-e6dd-ec7b907174fa@web.de","subject":"Re: [PATCH] Avoid infinite loop in malformed packfiles","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-08-24T20:12:08Z","receivedAt":"2020-08-24T20:12:16Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Aug 24, 2020 at 06:06:27PM +0200, René Scharfe wrote:\n\n> > Is there anything you'd like me to do in this patch, other than fixing\n> > the typo?\n> \n> Please explain in the commit message why 10000 is a good choice for that\n> new limit, and what users who happen to exceed it can do to regain\n> access to their packed data.\n\nI think it may be worth making this a configurable value\n(core.maxDeltaDepth or something). Nobody would generally need to tweak\nit, but it would give an escape hatch for getting people out of a broken\nsituation (\"git -c core.maxDeltaDepth=50000 repack\" or similar).\n\n-Peff\n"},{"id":"404372","messageId":"xmqq7dtn4wie.fsf@gitster.c.googlers.com","threadId":"54093","inReplyTo":"20200823005236.10386-1-ori@eigenstate.org","subject":"Re: [PATCH] Avoid infinite loop in malformed packfiles","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2020-08-24T20:30:33Z","receivedAt":"2020-08-24T20:30:42Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Ori Bernstein writes:\n\n> Subject: Re: [PATCH] Avoid infinite loop in malformed packfiles\n\nDocumentation/SubmittingPatches[[summary-section]]. Perhaps\n\n packfile: avoid infinite loop with malformed packfiles\n\n> In packfile.c:1680, there's an infinite loop that tries to get\n\nThe line numbers can easily change. \"In packfile.c::unpack_entry(),\nthere is...\" may be more change-resistant.\n\n"},{"id":"404373","messageId":"xmqq5z974w50.fsf@gitster.c.googlers.com","threadId":"54093","inReplyTo":"20200824201208.GA706849@coredump.intra.peff.net","subject":"Re: [PATCH] Avoid infinite loop in malformed packfiles","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2020-08-24T20:38:35Z","receivedAt":"2020-08-24T20:38:41Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> I think it may be worth making this a configurable value\n> (core.maxDeltaDepth or something). Nobody would generally need to tweak\n> it, but it would give an escape hatch for getting people out of a broken\n> situation (\"git -c core.maxDeltaDepth=50000 repack\" or similar).\n\n... meaning \"the pack I have has overlong delta chains to read, and\nI am running repack to cut these chains down to more manageable\nlevel\"? Makes sense.\n\nAs it may be a bit tricky to figure out where we should read such a\nconfiguration for those who are new to our codebase, here is an\nillustration to give a starting point. Docs and tests are probably\nneeded, too.\n\n cache.h | 1 +\n config.c | 5 +++++\n environment.c | 1 +\n packfile.c | 6 ++++++\n 4 files changed, 13 insertions(+)\n\ndiff --git a/cache.h b/cache.h\nindex 0290849c19..b59d43f0ec 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -919,6 +919,7 @@ extern int minimum_abbrev, default_abbrev;\n extern int ignore_case;\n extern int assume_unchanged;\n extern int prefer_symlink_refs;\n+extern int max_allowed_delta_depth;\n extern int warn_ambiguous_refs;\n extern int warn_on_object_refname_ambiguity;\n extern const char *apply_default_whitespace;\ndiff --git a/config.c b/config.c\nindex 2b79fe76ad..5f9114f847 100644\n--- a/config.c\n+++ b/config.c\n@@ -1197,6 +1197,11 @@ static int git_default_core_config(const char *var, const char *value, void *cb)\n \t\treturn 0;\n \t}\n \n+\tif (!strcmp(var, \"core.maxalloweddeltadepth\")) {\n+\t\tmax_allowed_delta_depth = git_config_int(var, value);\n+\t\treturn 0;\n+\t}\n+\n \tif (!strcmp(var, \"core.logallrefupdates\")) {\n \t\tif (value && !strcasecmp(value, \"always\"))\n \t\t\tlog_all_ref_updates = LOG_REFS_ALWAYS;\ndiff --git a/environment.c b/environment.c\nindex 52e0c979ba..d3f9a10799 100644\n--- a/environment.c\n+++ b/environment.c\n@@ -27,6 +27,7 @@ int minimum_abbrev = 4, default_abbrev = -1;\n int ignore_case;\n int assume_unchanged;\n int prefer_symlink_refs;\n+int max_allowed_delta_depth = 10000;\n int is_bare_repository_cfg = -1; /* unspecified */\n int warn_ambiguous_refs = 1;\n int warn_on_object_refname_ambiguity = 1;\ndiff --git a/packfile.c b/packfile.c\nindex 6ab5233613..2ea24a19dd 100644\n--- a/packfile.c\n+++ b/packfile.c\n@@ -1715,6 +1715,12 @@ void *unpack_entry(struct repository *r, struct packed_git *p, off_t obj_offset,\n \t\t\tbreak;\n \t\t}\n \n+\t\tif (max_allowed_delta_depth < delta_stack_nr) {\n+\t\t\terror(\"overlong delta chain at offset %\"PRIuMAX\" from %s\",\n+\t\t\t (uintmax_t)curpos, p->pack_name);\n+\t\t\tgoto out;\n+\t\t}\n+\n \t\t/* push object, proceed to base */\n \t\tif (delta_stack_nr >= delta_stack_alloc\n \t\t && delta_stack == small_delta_stack) {\n\n\n\n\n\n"},{"id":"404376","messageId":"20200824205231.GA787628@coredump.intra.peff.net","threadId":"54093","inReplyTo":"xmqq5z974w50.fsf@gitster.c.googlers.com","subject":"Re: [PATCH] Avoid infinite loop in malformed packfiles","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-08-24T20:52:31Z","receivedAt":"2020-08-24T20:52:34Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Aug 24, 2020 at 01:38:35PM -0700, Junio C Hamano wrote:\n\n> Jeff King writes:\n> \n> > I think it may be worth making this a configurable value\n> > (core.maxDeltaDepth or something). Nobody would generally need to tweak\n> > it, but it would give an escape hatch for getting people out of a broken\n> > situation (\"git -c core.maxDeltaDepth=50000 repack\" or similar).\n> \n> ... meaning \"the pack I have has overlong delta chains to read, and\n> I am running repack to cut these chains down to more manageable\n> level\"? Makes sense.\n\nExactly.\n\n> As it may be a bit tricky to figure out where we should read such a\n> configuration for those who are new to our codebase, here is an\n> illustration to give a starting point. Docs and tests are probably\n> needed, too.\n\nIt may be hard to test, as I suspect modern versions of Git are not\nhappy to create such a deep chain. We could test with a lowered value of\nthe config option, though.\n\nIt may also be worth introducing a true cycle using non-git commands.\nThere's some coverage there in t/t5309-pack-delta-cycles.sh. I think we\nwere mainly concerned there with how index-pack treats them, and it\nwould be nice to see how other commands react. Though I guess that\ncreates another testing difficulty: those other commands would need a\npack index, and we'd refuse to create one. :) So I think it would\nrequire adding code to manually create a bogus idx file (or I guess\nshipping one as a fixture).\n\n-Peff\n"},{"id":"404381","messageId":"xmqqft8b3fj4.fsf@gitster.c.googlers.com","threadId":"54093","inReplyTo":"20200824205231.GA787628@coredump.intra.peff.net","subject":"Re: [PATCH] Avoid infinite loop in malformed packfiles","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2020-08-24T21:22:39Z","receivedAt":"2020-08-24T21:22:44Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> It may be hard to test, as I suspect modern versions of Git are not\n> happy to create such a deep chain. We could test with a lowered value of\n> the config option, though.\n\nYes, that was what I meant. Start from a 1KB text, create 50\nrevisions of the file by adding a single line at its end at a time,\npack with depth limit of 100, and then see \"git log -p\" die when the\nallowed max lowered to 10, or something like that.\n\n"},{"id":"404763","messageId":"A1CA9D499EDDACBA275BA61E114645F0@eigenstate.org","threadId":"54093","inReplyTo":"xmqqft8b3fj4.fsf@gitster.c.googlers.com","subject":"Re: [PATCH] Avoid infinite loop in malformed packfiles","fromName":"","fromEmail":"ori@eigenstate.org","sentAt":"2020-08-30T03:33:54Z","receivedAt":"2020-08-30T03:33:58Z","isPatch":true,"sender":{"key":"ori@eigenstate.org","avatar":null},"body":"> Jeff King writes:\n> \n>> It may be hard to test, as I suspect modern versions of Git are not\n>> happy to create such a deep chain. We could test with a lowered value of\n>> the config option, though.\n> \n> Yes, that was what I meant. Start from a 1KB text, create 50\n> revisions of the file by adding a single line at its end at a time,\n> pack with depth limit of 100, and then see \"git log -p\" die when the\n> allowed max lowered to 10, or something like that.\n\nSorry about the delay -- most of my time to poke at this is over the weekend.\n\nWill that work? I'd expect that modern pack files end up being\noffset deltas, rather than reference deltas.\n\n"},{"id":"404768","messageId":"59efeeab-49de-17e7-8b1c-355d6ef31b5d@web.de","threadId":"54093","inReplyTo":"A1CA9D499EDDACBA275BA61E114645F0@eigenstate.org","subject":"Re: [PATCH] Avoid infinite loop in malformed packfiles","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2020-08-30T10:56:11Z","receivedAt":"2020-08-30T10:58:41Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 30.08.20 um 05:33 schrieb ori@eigenstate.org:\n>> Jeff King writes:\n>>\n>>> It may be hard to test, as I suspect modern versions of Git are not\n>>> happy to create such a deep chain. We could test with a lowered value of\n>>> the config option, though.\n>>\n>> Yes, that was what I meant. Start from a 1KB text, create 50\n>> revisions of the file by adding a single line at its end at a time,\n>> pack with depth limit of 100, and then see \"git log -p\" die when the\n>> allowed max lowered to 10, or something like that.\n>\n> Sorry about the delay -- most of my time to poke at this is over the weekend.\n>\n> Will that work? I'd expect that modern pack files end up being\n> offset deltas, rather than reference deltas.\n\nTrue, but going down all the way would work:\n\ndiff --git a/t/t5316-pack-delta-depth.sh b/t/t5316-pack-delta-depth.sh\nindex 0f06c40eb1..7fd21cd3ce 100755\n--- a/t/t5316-pack-delta-depth.sh\n+++ b/t/t5316-pack-delta-depth.sh\n@@ -94,4 +94,15 @@ test_expect_success '--depth limits depth' '\n \ttest_i18ncmp expect actual\n '\n\n+test_expect_success 'maxAllowedDeltaDepth is respected' '\n+\tgit clone . clone1 &&\n+\t(\n+\t\tcd clone1 &&\n+\t\tgit repack -a -d &&\n+\t\ttest_config core.maxAllowedDeltaDepth 0 &&\n+\t\ttest_must_fail git fsck 2>err &&\n+\t\ttest_i18ngrep \"overlong delta chain\" err\n+\t)\n+'\n+\n test_done\n\n\n"},{"id":"404769","messageId":"xmqqwo1gglf5.fsf@gitster.c.googlers.com","threadId":"54093","inReplyTo":"59efeeab-49de-17e7-8b1c-355d6ef31b5d@web.de","subject":"Re: [PATCH] Avoid infinite loop in malformed packfiles","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2020-08-30T16:15:10Z","receivedAt":"2020-08-30T16:15:18Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"René Scharfe writes:\n\n>> Will that work? I'd expect that modern pack files end up being\n>> offset deltas, rather than reference deltas.\n>\n> True, but going down all the way would work:\n\nPerhaps, but I'd rather use pack-objects to prepare the repository\nwith no-delta-base-offset to force ref deltas.\n\n> diff --git a/t/t5316-pack-delta-depth.sh b/t/t5316-pack-delta-depth.sh\n> index 0f06c40eb1..7fd21cd3ce 100755\n> --- a/t/t5316-pack-delta-depth.sh\n> +++ b/t/t5316-pack-delta-depth.sh\n> @@ -94,4 +94,15 @@ test_expect_success '--depth limits depth' '\n> \ttest_i18ncmp expect actual\n> '\n>\n> +test_expect_success 'maxAllowedDeltaDepth is respected' '\n> +\tgit clone . clone1 &&\n> +\t(\n> +\t\tcd clone1 &&\n> +\t\tgit repack -a -d &&\n> +\t\ttest_config core.maxAllowedDeltaDepth 0 &&\n> +\t\ttest_must_fail git fsck 2>err &&\n> +\t\ttest_i18ngrep \"overlong delta chain\" err\n> +\t)\n> +'\n> +\n> test_done\n"},{"id":"404794","messageId":"20200831092946.GA2812764@coredump.intra.peff.net","threadId":"54093","inReplyTo":"xmqqwo1gglf5.fsf@gitster.c.googlers.com","subject":"Re: [PATCH] Avoid infinite loop in malformed packfiles","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-08-31T09:29:46Z","receivedAt":"2020-08-31T09:29:50Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sun, Aug 30, 2020 at 09:15:10AM -0700, Junio C Hamano wrote:\n\n> René Scharfe writes:\n> \n> >> Will that work? I'd expect that modern pack files end up being\n> >> offset deltas, rather than reference deltas.\n> >\n> > True, but going down all the way would work:\n> \n> Perhaps, but I'd rather use pack-objects to prepare the repository\n> with no-delta-base-offset to force ref deltas.\n\nYeah, that seems like a much better test setup.\n\nIt does raise an interesting question, though. I had imagined we would\nlimit the depth of all delta chains here, not just ref-deltas. But it is\ntrue that ofs deltas can't cycle. Without cycles, neither type can go on\nindefinitely (they are limited by the number of entries in the\npackfile). I could see arguments going either way:\n\n - ofs deltas cannot cycle, so we do not need a counter that limits\n them (and which _could_ find a false positive). So we should not\n limit them.\n\n - a counter is preventing us from following cycles indefinitely, but\n also hardening us against misbehavior due to bugs or insanely large\n delta chains (intentional or not). So we should include ofs deltas\n in our limit.\n\nA related point is that delta chains might be composed of both types. If\nwe don't differentiate between the two types, then the limit is clearly\ntotal chain length. If we do, then is the limit the total number of\nref-deltas found in the current lookup, or is it the number of\nconsecutive ref-deltas? I guess it would have to be the former if our\ngoal is to catch cycles (since a cycle could include an ofs-delta, as\nlong as a ref-delta is the part that forms the loop).\n\n-Peff\n"},{"id":"404814","messageId":"xmqqk0xehj38.fsf@gitster.c.googlers.com","threadId":"54093","inReplyTo":"20200831092946.GA2812764@coredump.intra.peff.net","subject":"Re: [PATCH] Avoid infinite loop in malformed packfiles","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2020-08-31T16:32:27Z","receivedAt":"2020-08-31T16:32:34Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> It does raise an interesting question, though. I had imagined we would\n> limit the depth of all delta chains here, not just ref-deltas. But it is\n> true that ofs deltas can't cycle. Without cycles, neither type can go on\n> indefinitely (they are limited by the number of entries in the\n> packfile). I could see arguments going either way:\n>\n> - ofs deltas cannot cycle, so we do not need a counter that limits\n> them (and which _could_ find a false positive). So we should not\n> limit them.\n>\n> - a counter is preventing us from following cycles indefinitely, but\n> also hardening us against misbehavior due to bugs or insanely large\n> delta chains (intentional or not). So we should include ofs deltas\n> in our limit.\n\nA chain can have both types, so I am fuzzy how the counting would\ngo. We just do not count ofs_delta at all and only count ref_delta\nwe've seen during the recursion?\n\n> A related point is that delta chains might be composed of both types. If\n> we don't differentiate between the two types, then the limit is clearly\n> total chain length. If we do, then is the limit the total number of\n> ref-deltas found in the current lookup, or is it the number of\n> consecutive ref-deltas? I guess it would have to be the former if our\n> goal is to catch cycles (since a cycle could include an ofs-delta, as\n> long as a ref-delta is the part that forms the loop).\n\nAh, OK, you've thought about it already.\n\nI wonder we can just count both and limit the chain length to the\ntotal number of objects in the pack we are currently looking at? It\nguarantees to catch any cycle as long as pack is not thin, but is\nthat too lenient and likely to bust the stack while counting? On\nthe other side of the coin, we saw 10000 as a hard-coded limit in\nthe patch, but do we know 10000 is low enough that most boxes have\nno trouble recursing that deep?\n\nThanks.\n"},{"id":"404815","messageId":"C9978BD24477BD4A7FE2D3A014436D8D@eigenstate.org","threadId":"54093","inReplyTo":"20200831092946.GA2812764@coredump.intra.peff.net","subject":"Re: [PATCH] Avoid infinite loop in malformed packfiles","fromName":"","fromEmail":"ori@eigenstate.org","sentAt":"2020-08-31T16:50:18Z","receivedAt":"2020-08-31T16:50:22Z","isPatch":true,"sender":{"key":"ori@eigenstate.org","avatar":null},"body":"> On Sun, Aug 30, 2020 at 09:15:10AM -0700, Junio C Hamano wrote:\n> \n>> René Scharfe writes:\n>> \n>> >> Will that work? I'd expect that modern pack files end up being\n>> >> offset deltas, rather than reference deltas.\n>> >\n>> > True, but going down all the way would work:\n>> \n>> Perhaps, but I'd rather use pack-objects to prepare the repository\n>> with no-delta-base-offset to force ref deltas.\n> \n> Yeah, that seems like a much better test setup.\n> \n> It does raise an interesting question, though. I had imagined we would\n> limit the depth of all delta chains here, not just ref-deltas. But it is\n> true that ofs deltas can't cycle. Without cycles, neither type can go on\n> indefinitely (they are limited by the number of entries in the\n> packfile). I could see arguments going either way:\n\nYeah -- that's what I'd implemented. I was just thinking that I'd want to\ntest the issue that caused the problem in the first place, but it's the\nsame code path either way.\n\nI like the idea of limiting to the total number of objects in the\npack. If we do that, we don't need a knob at all, since if we need\nmore objects in the stack than are in the pack, it's obviously\ninvalid.\n\nThat does eliminate an obvious way to test things, and we'd need\nto provide in an invalid pack file.\n\n"},{"id":"404827","messageId":"20200831192302.GA2819760@coredump.intra.peff.net","threadId":"54093","inReplyTo":"xmqqk0xehj38.fsf@gitster.c.googlers.com","subject":"Re: [PATCH] Avoid infinite loop in malformed packfiles","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-08-31T19:23:02Z","receivedAt":"2020-08-31T19:23:10Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Aug 31, 2020 at 09:32:27AM -0700, Junio C Hamano wrote:\n\n> > A related point is that delta chains might be composed of both types. If\n> > we don't differentiate between the two types, then the limit is clearly\n> > total chain length. If we do, then is the limit the total number of\n> > ref-deltas found in the current lookup, or is it the number of\n> > consecutive ref-deltas? I guess it would have to be the former if our\n> > goal is to catch cycles (since a cycle could include an ofs-delta, as\n> > long as a ref-delta is the part that forms the loop).\n> \n> Ah, OK, you've thought about it already.\n> \n> I wonder we can just count both and limit the chain length to the\n> total number of objects in the pack we are currently looking at? \n\nThat's an interesting suggestion. Within a single pack, it does prevent\ncycles, and it does so without needing a separate knob, which is nice.\n\nAs you note, it only works as long as packs aren't thin. That shouldn't\nmatter for the current scheme (where all on-disk packs are\nself-contained with respect to deltas), but I do wonder if we'll\neventually want to support on-disk thin packs (coupled with a\nmulti-pack-index, that eliminates most of the reason that one needs\nrepack existing objects; it's probably a necessary step in scaling to\nrepos with hundreds of millions of objects). We could still auto-bound\nit with the total number of packed objects in the repository, though.\n\n> It\n> guarantees to catch any cycle as long as pack is not thin, but is\n> that too lenient and likely to bust the stack while counting? On\n> the other side of the coin, we saw 10000 as a hard-coded limit in\n> the patch, but do we know 10000 is low enough that most boxes have\n> no trouble recursing that deep?\n\nI don't think we have to worry about stack size. We already ran into\nstack-busting problems with non-broken cases. ;) That led to 790d96c023\n(sha1_file: remove recursion in packed_object_info, 2013-03-25) using\nits own stack.\n\nI do wonder about CPU, though. We might have tens of millions of objects\nin a single pack file. How long does it take to convince ourselves we're\ncycling (even if the cycle itself might only involve a handful of\nobjects)? I'm not sure we care too much about this being a fast\noperation (after all, the point is that it should never happen and we're\njust trying not to spin forever). But if it takes 60 minutes to detect\nthe cycle, from a user's perspective that might not be any different\nthan an infinite loop.\n\n-Peff\n"}]}