| Message ID | 20200823031151.10985-1-ori@eigenstate.org (mailing list archive) |
|---|---|
| State | New, archived |
| Headers | show |
| Series | Avoid infinite loop in malformed packfiles | expand |
Am 23.08.20 um 05:11 schrieb Ori Bernstein: > In packfile.c:1680, there's an infinite loop that tries to get > to the base of a packfile. With offset deltas, the offset needs > to be greater than 0, so it's always walking backwards, and the > search is guaranteed to terminate. > > With reference deltas, there's no check for a cycle in the > references, so a cyclic reference will cause git to loop > infinitely, growing the delta_stack infinitely, which will > cause it to consume all available memory as as a full CPU > core. "as as"? Perhaps "and"? > This change puts an arbitrary limit of 10,000 on the number > of iterations we make when chasing down a base commit, to > prevent looping forever, using all available memory growing > the delta stack. > > Signed-off-by: Ori Bernstein <ori@eigenstate.org> > --- > packfile.c | 7 +++++++ > 1 file changed, 7 insertions(+) > > diff --git a/packfile.c b/packfile.c > index 6ab5233613..321e002c50 100644 > --- a/packfile.c > +++ b/packfile.c > @@ -1633,6 +1633,7 @@ static void write_pack_access_log(struct packed_git *p, off_t obj_offset) > > int do_check_packed_object_crc; > > +#define UNPACK_ENTRY_STACK_LIMIT 10000 b5c0cbd8083 (pack-objects: use bitfield for object_entry::depth, 2018-04-14) limited the delta depth for new packs to 4095, so 10000 seems reasonable. Users with unreasonable packs would need to repack them with an older version of Git, though. Not sure if that would affect anyone in practice. > #define UNPACK_ENTRY_STACK_PREALLOC 64 Hmm, setting a hard limit may allow to allocate the whole stack on the, ehm, stack. That would get rid of the hybrid stack/heap allocation and thus simplify the code a bit. 10000 entries with 24 bytes each would be quite big, though, but that might be OK without recursion. (And not in this patch anyway, of course.) > struct unpack_entry_stack_ent { > off_t obj_offset; > @@ -1715,6 +1716,12 @@ void *unpack_entry(struct repository *r, struct packed_git *p, off_t obj_offset, > break; > } > > + if (delta_stack_nr > UNPACK_ENTRY_STACK_LIMIT) { > + error("overlong delta chain at offset %jd from %s", > + (uintmax_t)curpos, p->pack_name); > + goto out; > + } Other error handlers in this loop set data to NULL. That's actually unnecessary because it's NULL to begin with and the loop is exited after setting it to some other value. So not doing it here is fine. (And a separate cleanup patch could remove the dead stores in the other handlers.) > + > /* push object, proceed to base */ > if (delta_stack_nr >= delta_stack_alloc > && delta_stack == small_delta_stack) { >
On Sun, 23 Aug 2020 08:26:14 +0200, René Scharfe <l.s.r@web.de> wrote: > Am 23.08.20 um 05:11 schrieb Ori Bernstein: > > In packfile.c:1680, there's an infinite loop that tries to get > > to the base of a packfile. With offset deltas, the offset needs > > to be greater than 0, so it's always walking backwards, and the > > search is guaranteed to terminate. > > > > With reference deltas, there's no check for a cycle in the > > references, so a cyclic reference will cause git to loop > > infinitely, growing the delta_stack infinitely, which will > > cause it to consume all available memory as as a full CPU > > core. > > "as as"? Perhaps "and"? I think I meant 'As well as' -- will fix. > > b5c0cbd8083 (pack-objects: use bitfield for object_entry::depth, > 2018-04-14) limited the delta depth for new packs to 4095, so 10000 > seems reasonable. Users with unreasonable packs would need to repack > them with an older version of Git, though. Not sure if that would > affect anyone in practice. > > > #define UNPACK_ENTRY_STACK_PREALLOC 64 > > Hmm, setting a hard limit may allow to allocate the whole stack on the, > ehm, stack. That would get rid of the hybrid stack/heap allocation and > thus simplify the code a bit. 10000 entries with 24 bytes each would be > quite big, though, but that might be OK without recursion. (And not in > this patch anyway, of course.) > > > struct unpack_entry_stack_ent { > > off_t obj_offset; > > @@ -1715,6 +1716,12 @@ void *unpack_entry(struct repository *r, struct packed_git *p, off_t obj_offset, > > break; > > } > > > > + if (delta_stack_nr > UNPACK_ENTRY_STACK_LIMIT) { > > + error("overlong delta chain at offset %jd from %s", > > + (uintmax_t)curpos, p->pack_name); > > + goto out; > > + } > > Other error handlers in this loop set data to NULL. That's actually > unnecessary because it's NULL to begin with and the loop is exited after > setting it to some other value. So not doing it here is fine. (And a > separate cleanup patch could remove the dead stores in the other > handlers.) Is there anything you'd like me to do in this patch, other than fixing the typo?
Am 23.08.20 um 22:41 schrieb Ori Bernstein: > On Sun, 23 Aug 2020 08:26:14 +0200, René Scharfe <l.s.r@web.de> wrote: > >> Am 23.08.20 um 05:11 schrieb Ori Bernstein: >>> In packfile.c:1680, there's an infinite loop that tries to get >>> to the base of a packfile. With offset deltas, the offset needs >>> to be greater than 0, so it's always walking backwards, and the >>> search is guaranteed to terminate. >>> >>> With reference deltas, there's no check for a cycle in the >>> references, so a cyclic reference will cause git to loop >>> infinitely, growing the delta_stack infinitely, which will >>> cause it to consume all available memory as as a full CPU >>> core. >> >> "as as"? Perhaps "and"? > > I think I meant 'As well as' -- will fix. > >> >> b5c0cbd8083 (pack-objects: use bitfield for object_entry::depth, >> 2018-04-14) limited the delta depth for new packs to 4095, so 10000 >> seems reasonable. Users with unreasonable packs would need to repack >> them with an older version of Git, though. Not sure if that would >> affect anyone in practice. > Is there anything you'd like me to do in this patch, other than fixing > the typo? Please explain in the commit message why 10000 is a good choice for that new limit, and what users who happen to exceed it can do to regain access to their packed data. René
Ori Bernstein <ori@eigenstate.org> writes: > diff --git a/packfile.c b/packfile.c > index 6ab5233613..321e002c50 100644 > --- a/packfile.c > +++ b/packfile.c > @@ -1715,6 +1716,12 @@ void *unpack_entry(struct repository *r, struct packed_git *p, off_t obj_offset, > break; > } > > + if (delta_stack_nr > UNPACK_ENTRY_STACK_LIMIT) { > + error("overlong delta chain at offset %jd from %s", > + (uintmax_t)curpos, p->pack_name); The "j" length field is not used anywhere in the codebase for portability concerns, I think. "d" is for signed, but curpos is an unsigned off_t. I think "... %"PRIuMAX" from %s", (uintmax_t)curpos, ... would match how we write this kind of thing everywhere else in the code, e.g. showing obj_offset in packed_to_object_type() in the same file in an error message. > @@ -1633,6 +1633,7 @@ static void write_pack_access_log(struct packed_git *p, off_t obj_offset) > > int do_check_packed_object_crc; > > +#define UNPACK_ENTRY_STACK_LIMIT 10000 > #define UNPACK_ENTRY_STACK_PREALLOC 64 > struct unpack_entry_stack_ent { > off_t obj_offset; What escape hatch would the end-users have when they have a legitimate packfile that has a truly deep delta chain, by the way? Thanks.
On Mon, Aug 24, 2020 at 06:06:27PM +0200, René Scharfe wrote: > > Is there anything you'd like me to do in this patch, other than fixing > > the typo? > > Please explain in the commit message why 10000 is a good choice for that > new limit, and what users who happen to exceed it can do to regain > access to their packed data. I think it may be worth making this a configurable value (core.maxDeltaDepth or something). Nobody would generally need to tweak it, but it would give an escape hatch for getting people out of a broken situation ("git -c core.maxDeltaDepth=50000 repack" or similar). -Peff
Jeff King <peff@peff.net> writes: > I think it may be worth making this a configurable value > (core.maxDeltaDepth or something). Nobody would generally need to tweak > it, but it would give an escape hatch for getting people out of a broken > situation ("git -c core.maxDeltaDepth=50000 repack" or similar). ... meaning "the pack I have has overlong delta chains to read, and I am running repack to cut these chains down to more manageable level"? Makes sense. As it may be a bit tricky to figure out where we should read such a configuration for those who are new to our codebase, here is an illustration to give a starting point. Docs and tests are probably needed, too. cache.h | 1 + config.c | 5 +++++ environment.c | 1 + packfile.c | 6 ++++++ 4 files changed, 13 insertions(+) diff --git a/cache.h b/cache.h index 0290849c19..b59d43f0ec 100644 --- a/cache.h +++ b/cache.h @@ -919,6 +919,7 @@ extern int minimum_abbrev, default_abbrev; extern int ignore_case; extern int assume_unchanged; extern int prefer_symlink_refs; +extern int max_allowed_delta_depth; extern int warn_ambiguous_refs; extern int warn_on_object_refname_ambiguity; extern const char *apply_default_whitespace; diff --git a/config.c b/config.c index 2b79fe76ad..5f9114f847 100644 --- a/config.c +++ b/config.c @@ -1197,6 +1197,11 @@ static int git_default_core_config(const char *var, const char *value, void *cb) return 0; } + if (!strcmp(var, "core.maxalloweddeltadepth")) { + max_allowed_delta_depth = git_config_int(var, value); + return 0; + } + if (!strcmp(var, "core.logallrefupdates")) { if (value && !strcasecmp(value, "always")) log_all_ref_updates = LOG_REFS_ALWAYS; diff --git a/environment.c b/environment.c index 52e0c979ba..d3f9a10799 100644 --- a/environment.c +++ b/environment.c @@ -27,6 +27,7 @@ int minimum_abbrev = 4, default_abbrev = -1; int ignore_case; int assume_unchanged; int prefer_symlink_refs; +int max_allowed_delta_depth = 10000; int is_bare_repository_cfg = -1; /* unspecified */ int warn_ambiguous_refs = 1; int warn_on_object_refname_ambiguity = 1; diff --git a/packfile.c b/packfile.c index 6ab5233613..2ea24a19dd 100644 --- a/packfile.c +++ b/packfile.c @@ -1715,6 +1715,12 @@ void *unpack_entry(struct repository *r, struct packed_git *p, off_t obj_offset, break; } + if (max_allowed_delta_depth < delta_stack_nr) { + error("overlong delta chain at offset %"PRIuMAX" from %s", + (uintmax_t)curpos, p->pack_name); + goto out; + } + /* push object, proceed to base */ if (delta_stack_nr >= delta_stack_alloc && delta_stack == small_delta_stack) {
On Mon, Aug 24, 2020 at 01:38:35PM -0700, Junio C Hamano wrote: > Jeff King <peff@peff.net> writes: > > > I think it may be worth making this a configurable value > > (core.maxDeltaDepth or something). Nobody would generally need to tweak > > it, but it would give an escape hatch for getting people out of a broken > > situation ("git -c core.maxDeltaDepth=50000 repack" or similar). > > ... meaning "the pack I have has overlong delta chains to read, and > I am running repack to cut these chains down to more manageable > level"? Makes sense. Exactly. > As it may be a bit tricky to figure out where we should read such a > configuration for those who are new to our codebase, here is an > illustration to give a starting point. Docs and tests are probably > needed, too. It may be hard to test, as I suspect modern versions of Git are not happy to create such a deep chain. We could test with a lowered value of the config option, though. It may also be worth introducing a true cycle using non-git commands. There's some coverage there in t/t5309-pack-delta-cycles.sh. I think we were mainly concerned there with how index-pack treats them, and it would be nice to see how other commands react. Though I guess that creates another testing difficulty: those other commands would need a pack index, and we'd refuse to create one. :) So I think it would require adding code to manually create a bogus idx file (or I guess shipping one as a fixture). -Peff
Jeff King <peff@peff.net> writes: > It may be hard to test, as I suspect modern versions of Git are not > happy to create such a deep chain. We could test with a lowered value of > the config option, though. Yes, that was what I meant. Start from a 1KB text, create 50 revisions of the file by adding a single line at its end at a time, pack with depth limit of 100, and then see "git log -p" die when the allowed max lowered to 10, or something like that.
> Jeff King <peff@peff.net> writes: > >> It may be hard to test, as I suspect modern versions of Git are not >> happy to create such a deep chain. We could test with a lowered value of >> the config option, though. > > Yes, that was what I meant. Start from a 1KB text, create 50 > revisions of the file by adding a single line at its end at a time, > pack with depth limit of 100, and then see "git log -p" die when the > allowed max lowered to 10, or something like that. Sorry about the delay -- most of my time to poke at this is over the weekend. Will that work? I'd expect that modern pack files end up being offset deltas, rather than reference deltas.
Am 30.08.20 um 05:33 schrieb ori@eigenstate.org: >> Jeff King <peff@peff.net> writes: >> >>> It may be hard to test, as I suspect modern versions of Git are not >>> happy to create such a deep chain. We could test with a lowered value of >>> the config option, though. >> >> Yes, that was what I meant. Start from a 1KB text, create 50 >> revisions of the file by adding a single line at its end at a time, >> pack with depth limit of 100, and then see "git log -p" die when the >> allowed max lowered to 10, or something like that. > > Sorry about the delay -- most of my time to poke at this is over the weekend. > > Will that work? I'd expect that modern pack files end up being > offset deltas, rather than reference deltas. True, but going down all the way would work: diff --git a/t/t5316-pack-delta-depth.sh b/t/t5316-pack-delta-depth.sh index 0f06c40eb1..7fd21cd3ce 100755 --- a/t/t5316-pack-delta-depth.sh +++ b/t/t5316-pack-delta-depth.sh @@ -94,4 +94,15 @@ test_expect_success '--depth limits depth' ' test_i18ncmp expect actual ' +test_expect_success 'maxAllowedDeltaDepth is respected' ' + git clone . clone1 && + ( + cd clone1 && + git repack -a -d && + test_config core.maxAllowedDeltaDepth 0 && + test_must_fail git fsck 2>err && + test_i18ngrep "overlong delta chain" err + ) +' + test_done
René Scharfe <l.s.r@web.de> writes: >> Will that work? I'd expect that modern pack files end up being >> offset deltas, rather than reference deltas. > > True, but going down all the way would work: Perhaps, but I'd rather use pack-objects to prepare the repository with no-delta-base-offset to force ref deltas. > diff --git a/t/t5316-pack-delta-depth.sh b/t/t5316-pack-delta-depth.sh > index 0f06c40eb1..7fd21cd3ce 100755 > --- a/t/t5316-pack-delta-depth.sh > +++ b/t/t5316-pack-delta-depth.sh > @@ -94,4 +94,15 @@ test_expect_success '--depth limits depth' ' > test_i18ncmp expect actual > ' > > +test_expect_success 'maxAllowedDeltaDepth is respected' ' > + git clone . clone1 && > + ( > + cd clone1 && > + git repack -a -d && > + test_config core.maxAllowedDeltaDepth 0 && > + test_must_fail git fsck 2>err && > + test_i18ngrep "overlong delta chain" err > + ) > +' > + > test_done
On Sun, Aug 30, 2020 at 09:15:10AM -0700, Junio C Hamano wrote: > René Scharfe <l.s.r@web.de> writes: > > >> Will that work? I'd expect that modern pack files end up being > >> offset deltas, rather than reference deltas. > > > > True, but going down all the way would work: > > Perhaps, but I'd rather use pack-objects to prepare the repository > with no-delta-base-offset to force ref deltas. Yeah, that seems like a much better test setup. It does raise an interesting question, though. I had imagined we would limit the depth of all delta chains here, not just ref-deltas. But it is true that ofs deltas can't cycle. Without cycles, neither type can go on indefinitely (they are limited by the number of entries in the packfile). I could see arguments going either way: - ofs deltas cannot cycle, so we do not need a counter that limits them (and which _could_ find a false positive). So we should not limit them. - a counter is preventing us from following cycles indefinitely, but also hardening us against misbehavior due to bugs or insanely large delta chains (intentional or not). So we should include ofs deltas in our limit. A related point is that delta chains might be composed of both types. If we don't differentiate between the two types, then the limit is clearly total chain length. If we do, then is the limit the total number of ref-deltas found in the current lookup, or is it the number of consecutive ref-deltas? I guess it would have to be the former if our goal is to catch cycles (since a cycle could include an ofs-delta, as long as a ref-delta is the part that forms the loop). -Peff
Jeff King <peff@peff.net> writes: > It does raise an interesting question, though. I had imagined we would > limit the depth of all delta chains here, not just ref-deltas. But it is > true that ofs deltas can't cycle. Without cycles, neither type can go on > indefinitely (they are limited by the number of entries in the > packfile). I could see arguments going either way: > > - ofs deltas cannot cycle, so we do not need a counter that limits > them (and which _could_ find a false positive). So we should not > limit them. > > - a counter is preventing us from following cycles indefinitely, but > also hardening us against misbehavior due to bugs or insanely large > delta chains (intentional or not). So we should include ofs deltas > in our limit. A chain can have both types, so I am fuzzy how the counting would go. We just do not count ofs_delta at all and only count ref_delta we've seen during the recursion? > A related point is that delta chains might be composed of both types. If > we don't differentiate between the two types, then the limit is clearly > total chain length. If we do, then is the limit the total number of > ref-deltas found in the current lookup, or is it the number of > consecutive ref-deltas? I guess it would have to be the former if our > goal is to catch cycles (since a cycle could include an ofs-delta, as > long as a ref-delta is the part that forms the loop). Ah, OK, you've thought about it already. I wonder we can just count both and limit the chain length to the total number of objects in the pack we are currently looking at? It guarantees to catch any cycle as long as pack is not thin, but is that too lenient and likely to bust the stack while counting? On the other side of the coin, we saw 10000 as a hard-coded limit in the patch, but do we know 10000 is low enough that most boxes have no trouble recursing that deep? Thanks.
> On Sun, Aug 30, 2020 at 09:15:10AM -0700, Junio C Hamano wrote: > >> René Scharfe <l.s.r@web.de> writes: >> >> >> Will that work? I'd expect that modern pack files end up being >> >> offset deltas, rather than reference deltas. >> > >> > True, but going down all the way would work: >> >> Perhaps, but I'd rather use pack-objects to prepare the repository >> with no-delta-base-offset to force ref deltas. > > Yeah, that seems like a much better test setup. > > It does raise an interesting question, though. I had imagined we would > limit the depth of all delta chains here, not just ref-deltas. But it is > true that ofs deltas can't cycle. Without cycles, neither type can go on > indefinitely (they are limited by the number of entries in the > packfile). I could see arguments going either way: Yeah -- that's what I'd implemented. I was just thinking that I'd want to test the issue that caused the problem in the first place, but it's the same code path either way. I like the idea of limiting to the total number of objects in the pack. If we do that, we don't need a knob at all, since if we need more objects in the stack than are in the pack, it's obviously invalid. That does eliminate an obvious way to test things, and we'd need to provide in an invalid pack file.
On Mon, Aug 31, 2020 at 09:32:27AM -0700, Junio C Hamano wrote: > > A related point is that delta chains might be composed of both types. If > > we don't differentiate between the two types, then the limit is clearly > > total chain length. If we do, then is the limit the total number of > > ref-deltas found in the current lookup, or is it the number of > > consecutive ref-deltas? I guess it would have to be the former if our > > goal is to catch cycles (since a cycle could include an ofs-delta, as > > long as a ref-delta is the part that forms the loop). > > Ah, OK, you've thought about it already. > > I wonder we can just count both and limit the chain length to the > total number of objects in the pack we are currently looking at? That's an interesting suggestion. Within a single pack, it does prevent cycles, and it does so without needing a separate knob, which is nice. As you note, it only works as long as packs aren't thin. That shouldn't matter for the current scheme (where all on-disk packs are self-contained with respect to deltas), but I do wonder if we'll eventually want to support on-disk thin packs (coupled with a multi-pack-index, that eliminates most of the reason that one needs repack existing objects; it's probably a necessary step in scaling to repos with hundreds of millions of objects). We could still auto-bound it with the total number of packed objects in the repository, though. > It > guarantees to catch any cycle as long as pack is not thin, but is > that too lenient and likely to bust the stack while counting? On > the other side of the coin, we saw 10000 as a hard-coded limit in > the patch, but do we know 10000 is low enough that most boxes have > no trouble recursing that deep? I don't think we have to worry about stack size. We already ran into stack-busting problems with non-broken cases. ;) That led to 790d96c023 (sha1_file: remove recursion in packed_object_info, 2013-03-25) using its own stack. I do wonder about CPU, though. We might have tens of millions of objects in a single pack file. How long does it take to convince ourselves we're cycling (even if the cycle itself might only involve a handful of objects)? I'm not sure we care too much about this being a fast operation (after all, the point is that it should never happen and we're just trying not to spin forever). But if it takes 60 minutes to detect the cycle, from a user's perspective that might not be any different than an infinite loop. -Peff
diff --git a/packfile.c b/packfile.c index 6ab5233613..321e002c50 100644 --- a/packfile.c +++ b/packfile.c @@ -1633,6 +1633,7 @@ static void write_pack_access_log(struct packed_git *p, off_t obj_offset) int do_check_packed_object_crc; +#define UNPACK_ENTRY_STACK_LIMIT 10000 #define UNPACK_ENTRY_STACK_PREALLOC 64 struct unpack_entry_stack_ent { off_t obj_offset; @@ -1715,6 +1716,12 @@ void *unpack_entry(struct repository *r, struct packed_git *p, off_t obj_offset, break; } + if (delta_stack_nr > UNPACK_ENTRY_STACK_LIMIT) { + error("overlong delta chain at offset %jd from %s", + (uintmax_t)curpos, p->pack_name); + goto out; + } + /* push object, proceed to base */ if (delta_stack_nr >= delta_stack_alloc && delta_stack == small_delta_stack) {
In packfile.c:1680, there's an infinite loop that tries to get to the base of a packfile. With offset deltas, the offset needs to be greater than 0, so it's always walking backwards, and the search is guaranteed to terminate. With reference deltas, there's no check for a cycle in the references, so a cyclic reference will cause git to loop infinitely, growing the delta_stack infinitely, which will cause it to consume all available memory as as a full CPU core. This change puts an arbitrary limit of 10,000 on the number of iterations we make when chasing down a base commit, to prevent looping forever, using all available memory growing the delta stack. Signed-off-by: Ori Bernstein <ori@eigenstate.org> --- packfile.c | 7 +++++++ 1 file changed, 7 insertions(+)