| Message ID | 67c8c5f797833a9a35f4805059d7e759020f54bd.1741275245.git.me@ttaylorr.com (mailing list archive) |
|---|---|
| State | New |
| Headers | show |
| Series | refs: a couple of --exclude fixes | expand |
Taylor Blau <me@ttaylorr.com> writes: > So there is a subtle bug with '--exclude' which is that in the > packed-refs backend we will consider "refs/heads/bar" to be a pattern > match against "refs/heads/ba" when we shouldn't. Likewise, the reftable > backend (which in this case is bug-compatible with the packed backend) > exhibits the same broken behavior. > ... > There is some minor test fallout in the "overlapping excluded regions" > test, which happens to use 'refs/ba' as an exclude pattern, and expects > references under the "refs/heads/bar/*" and "refs/heads/baz/*" > hierarchies to be excluded from the results. > > ... test (since the range is no longer > overlapping under the stricter interpretation of --exclude patterns > presented here). The code change, reasoning, and the tests look all good. It just leaves a bit awkward aftertaste. In general, I think our "we have a tree-like structure with patterns to match paths" code paths, like pathspec matching, are structured in such a way that the low level is expected to merely cull candidates early as a performance optimization measure (in other words, they are allowed false positives and say something matches when they do not, but not allowed false negatives) and leave the upper level to further reject the ones that do not match the pattern. If packed-refs backend was too loose in its matching and erroneously considered that refs/heads/bar matched refs/heads/ba pattern, I would naïvely expect that the upper layer would catch and reject that refs/heads/bar as not matching. Apparently that was not happening and that is why we need this fix? Is the excluded region optimization expected to be powerful enough to cover all our needs so that we do not need to post-process what it passes? Thanks.
On Thu, Mar 06, 2025 at 09:27:21AM -0800, Junio C Hamano wrote: > Taylor Blau <me@ttaylorr.com> writes: > > > So there is a subtle bug with '--exclude' which is that in the > > packed-refs backend we will consider "refs/heads/bar" to be a pattern > > match against "refs/heads/ba" when we shouldn't. Likewise, the reftable > > backend (which in this case is bug-compatible with the packed backend) > > exhibits the same broken behavior. > > ... > > There is some minor test fallout in the "overlapping excluded regions" > > test, which happens to use 'refs/ba' as an exclude pattern, and expects > > references under the "refs/heads/bar/*" and "refs/heads/baz/*" > > hierarchies to be excluded from the results. > > > > ... test (since the range is no longer > > overlapping under the stricter interpretation of --exclude patterns > > presented here). > > The code change, reasoning, and the tests look all good. It just > leaves a bit awkward aftertaste. > > In general, I think our "we have a tree-like structure with patterns > to match paths" code paths, like pathspec matching, are structured > in such a way that the low level is expected to merely cull > candidates early as a performance optimization measure (in other > words, they are allowed false positives and say something matches > when they do not, but not allowed false negatives) and leave the > upper level to further reject the ones that do not match the > pattern. If packed-refs backend was too loose in its matching and > erroneously considered that refs/heads/bar matched refs/heads/ba > pattern, I would naïvely expect that the upper layer would catch and > reject that refs/heads/bar as not matching. I think you've swapped things around a bit by accident. The problem is that the patterns were being matched too loosely by the underlying backends, which had the consequence that the backends marked too many refs as excluded. As a result, those reference won't ever be yielded to the upper layer at all. So the upper layer doesn't even have a chance to correct such a mistake at all: it cannot correct what it doesn't know. There isn't really a way to implement such a safety net, either (or at least I cannot think of any): the whole point of making backends handle the exclude patterns is that they can skip whole regions entirely and not even try to read them. > Apparently that was not happening and that is why we need this fix? > > Is the excluded region optimization expected to be powerful enough > to cover all our needs so that we do not need to post-process what > it passes? No, it's not. But we can only correct false negatives, not false positives: - A false negative is a ref that matches an exclude pattern but that we yield regardless from the backend, and those do get handled by the upper layer. - A false positive is a ref that does not match an exclude pattern but is still treated as matching by the backend. We thus don't yield them, and thus the upper layer cannot rectify the bug. The fix at hand fixes false positives. What makes me feel a bit uneasy is that for the "files" backend the optimization depends on the packed state, which is quite awkward overall as our tests may not uncover issues only because we didn't pack refs. I don't really see a way to address this potential test gap generically though. The "reftable" backend doesn't have the same issue as it does not have the same split between packed and loose refs, so the optimization always kicks in. Patrick
Patrick Steinhardt <ps@pks.im> writes: > I think you've swapped things around a bit by accident. The problem is > that the patterns were being matched too loosely by the underlying > backends, which had the consequence that the backends marked too many > refs as excluded. OK, I agree it is confusing. As a selection mechanism for refs to be shown or processed, exclusion should be "we omit it because we clearly know this one should not be in the final result, but we may pass questionable ones, relying on our caller to have the final say". As a selection mechanism for refs to be excluded, the logic should be the other way around, so false positive and false negative are going to be swapped. We want the exclusion at the lower layer to only say "this ref clearly matches with given exclusion pattern", but we used to claim matches for refs that shouldn't match. OK. Thanks for straightening me out. > What makes me feel a bit uneasy is that for the "files" backend the > optimization depends on the packed state, which is quite awkward overall > as our tests may not uncover issues only because we didn't pack refs. I > don't really see a way to address this potential test gap generically > though. True. An obvious optimization for "files" _might_ be to lazily walk the directory hierarchy and skip recursive readdir when a directory clearly matches the given exclusion pattern, but the result of such an optimization (in other words, what would seep through the sieve) to be filtered out at the upper layer would be different from what the "packed-refs" backend does for its optimization, and they would be different for reftable or any other future backends. But I think that is the nature of lower-level optimization---each backend takes advantage of intimately knowing how it organizes the underlying data, and how they can omit without looking into a bulk of the section of data deeply would be different. Thanks.
On Thu, Mar 6, 2025 at 7:34 AM Taylor Blau <me@ttaylorr.com> wrote: > > In the packed-refs backend, our implementation of '--exclude' (dating > back to 59c35fac54 (refs/packed-backend.c: implement jump lists to avoid > excluded pattern(s), 2023-07-10)) considers, for example: > > $ git for-each-ref --exclude=refs/heads/ba > > to exclude "refs/heads/bar", "refs/heads/baz", and so on. > > The files backend, which does not implement '--exclude' (and relies on > the caller to cull out results that don't match) naturally will > enumerate "refs/heads/bar" and so on. > > So in the above example, 'for-each-ref' will try and see if > "refs/heads/ba" matches "refs/heads/bar" (since the files backend simply > enumerated every loose reference), and, realizing that it does not > match, output the reference as expected. (A caller that did want to > exclude "refs/heads/bar" and "refs/heads/baz" might instead run "git > for-each-ref --exclude='refs/heads/ba*'"). > > This can lead to strange behavior, like seeing a different set of > references advertised via 'upload-pack' depending on what set of > references were loose versus packed. > > So there is a subtle bug with '--exclude' which is that in the > packed-refs backend we will consider "refs/heads/bar" to be a pattern > match against "refs/heads/ba" when we shouldn't. Likewise, the reftable > backend (which in this case is bug-compatible with the packed backend) > exhibits the same broken behavior. Yuck; nice to see this being addressed. > There are a few ways to fix this. One is to tighten the rules in > cmp_record_to_refname(), which is used to determine the start/end-points > of the jump list used by the packed backend. In this new "strict" mode, > the comparison function would handle the case where we've reached the > end of the pattern by introducing a new check like so: > > while (1) { > if (*r1 == '\n') > return *r2 ? -1 : 0; > if (!*r2) > if (strict && *r1 != '/') /* <- here */ > return 1; > return start ? 1 : -1; > if (*r1 != *r2) > return (unsigned char)*r1 < (unsigned char)*r2 ? -1 : +1; > r1++; > r2++; > } > > (eliding out the rest of cmp_record_to_refname()). Equivalently, we > could teach refs/packed-backend::populate_excluded_jump_list() to append > a trailing '/' if one does not already exist, forcing an exclude pattern > like "refs/heads/ba" to only match "refs/heads/ba/abc" and so forth. > > But since the same problem exists in reftable, we can fix both at once > by performing this pre-processing step one layer up in refs.c at the > common entrypoint for the two, which is 'refs_ref_iterator_begin()'. > > Since that solution is both the simplest and only requires modification > in one spot, let's normalize exclude patterns so that they end with a > trailing slash. This causes us to unify the behavior between all three > backends. :-) > There is some minor test fallout in the "overlapping excluded regions" > test, which happens to use 'refs/ba' as an exclude pattern, and expects > references under the "refs/heads/bar/*" and "refs/heads/baz/*" > hierarchies to be excluded from the results. > > But that test fallout is expected, because the test was codifying the > buggy behavior to begin with, and should have never been written that > way. Split that into its own test (since the range is no longer > overlapping under the stricter interpretation of --exclude patterns > presented here). Create a new test which does have overlapping > regions by using a refs/heads/bar/4/... hierarchy and excluding both > "refs/heads/bar" and "refs/heads/bar/4". Always nice to see tests corrected. > Reported-by: SURA <surak8806@gmail.com> > Helped-by: Jeff King <peff@peff.net> > Signed-off-by: Taylor Blau <me@ttaylorr.com> > --- > refs.c | 6 +++++- > t/t1419-exclude-refs.sh | 16 ++++++++++++++-- > 2 files changed, 19 insertions(+), 3 deletions(-) > > diff --git a/refs.c b/refs.c > index 17d3840aff..2d9a1b51f4 100644 > --- a/refs.c > +++ b/refs.c > @@ -1708,7 +1708,11 @@ struct ref_iterator *refs_ref_iterator_begin( > if (!len) > continue; > > - strvec_push(&normalized_exclude_patterns, pattern); > + if (pattern[len - 1] == '/') > + strvec_push(&normalized_exclude_patterns, pattern); > + else > + strvec_pushf(&normalized_exclude_patterns, "%s/", > + pattern); Doesn't this mean that if the user requested to exclude "refs/heads/bar" and "refs/heads/bar" exists, that we won't exclude it because it doesn't have a trailing slash? From reading other comments in this thread, I guess that ends up being okay, because we only promise to filter out what we can cheaply filter, and we rely on our caller to double-check everything and do the real filtering. ...but it gives me some ugly dir.c vibes, reminding me of 95c11ecc73f2 (Fix error-prone fill_directory() API; make it only return matches, 2020-04-01) and a slew of related bugs preceding it. Granted, dir.c had this tri-state to deal with (tracked, untracked-but-ignored, untracked-and-not-ignored) and simplifying of whole directories, which don't apply here, so maybe the similarity of "fast-filtering-only-and-rely-on-caller" won't be a problem since the upper level filtering is so much more straightforward. Should this at least be called out in the commit message, though? > } > > exclude_patterns = normalized_exclude_patterns.v; > diff --git a/t/t1419-exclude-refs.sh b/t/t1419-exclude-refs.sh > index fd58260a24..04797aee59 100755 > --- a/t/t1419-exclude-refs.sh > +++ b/t/t1419-exclude-refs.sh > @@ -46,6 +46,10 @@ test_expect_success 'setup' ' > echo "create refs/heads/$name/$i $base" || return 1 > done || return 1 > done >in && > + for i in 5 6 7 > + do > + echo "create refs/heads/bar/4/$i $base" || return 1 > + done >>in && > echo "delete refs/heads/main" >>in && > > git update-ref --stdin <in && > @@ -99,9 +103,17 @@ test_expect_success 'adjacent, non-overlapping excluded regions' ' > esac > ' > > -test_expect_success 'overlapping excluded regions' ' > +test_expect_success 'non-directory excluded regions' ' > for_each_ref__exclude refs/heads refs/heads/ba refs/heads/baz >actual 2>perf && > - for_each_ref refs/heads/foo refs/heads/quux >expect && > + for_each_ref refs/heads/bar refs/heads/foo refs/heads/quux >expect && > + > + test_cmp expect actual && > + assert_jumps 1 perf > +' > + > +test_expect_success 'overlapping excluded regions' ' > + for_each_ref__exclude refs/heads refs/heads/bar refs/heads/bar/4 >actual 2>perf && > + for_each_ref refs/heads/baz refs/heads/foo refs/heads/quux >expect && > > test_cmp expect actual && > assert_jumps 1 perf > -- > 2.49.0.rc1.2.g67c8c5f7978 Other than the one surprise noted above, looks good to me.
On Fri, Mar 07, 2025 at 09:31:17AM -0800, Junio C Hamano wrote: > Patrick Steinhardt <ps@pks.im> writes: > > > I think you've swapped things around a bit by accident. The problem is > > that the patterns were being matched too loosely by the underlying > > backends, which had the consequence that the backends marked too many > > refs as excluded. > > OK, I agree it is confusing. As a selection mechanism for refs to > be shown or processed, exclusion should be "we omit it because we > clearly know this one should not be in the final result, but we may > pass questionable ones, relying on our caller to have the final > say". As a selection mechanism for refs to be excluded, the logic > should be the other way around, so false positive and false negative > are going to be swapped. We want the exclusion at the lower layer > to only say "this ref clearly matches with given exclusion pattern", > but we used to claim matches for refs that shouldn't match. > > OK. Thanks for straightening me out. Yes, Patrick is exactly right here. Thanks, Patrick, for beating me to the punch ;-). > > What makes me feel a bit uneasy is that for the "files" backend the > > optimization depends on the packed state, which is quite awkward overall > > as our tests may not uncover issues only because we didn't pack refs. I > > don't really see a way to address this potential test gap generically > > though. > > True. An obvious optimization for "files" _might_ be to lazily walk > the directory hierarchy and skip recursive readdir when a directory > clearly matches the given exclusion pattern, but the result of such > an optimization (in other words, what would seep through the sieve) > to be filtered out at the upper layer would be different from what > the "packed-refs" backend does for its optimization, and they would > be different for reftable or any other future backends. I had considered doing this back when I wrote 59c35fac54 (refs/packed-backend.c: implement jump lists to avoid excluded pattern(s), 2023-07-10). But I decided against it for a couple of reasons. First, it's a little more complicated than the packed backend's implementation, since we have to consider the additional context of what layer of the $GIT_DIR/refs directory we're in to construct the full prefix in order to even perform the match. But the second reason was that we should never have so many loose references sitting around for this optimization to even matter. If we're in a case where it does, then the repository in question should "git pack-refs --all" to take advantage of the optimization. > But I think that is the nature of lower-level optimization---each > backend takes advantage of intimately knowing how it organizes the > underlying data, and how they can omit without looking into a bulk > of the section of data deeply would be different. Yep. Thanks, Taylor
On Fri, Mar 07, 2025 at 01:31:31PM -0800, Elijah Newren wrote: > > diff --git a/refs.c b/refs.c > > index 17d3840aff..2d9a1b51f4 100644 > > --- a/refs.c > > +++ b/refs.c > > @@ -1708,7 +1708,11 @@ struct ref_iterator *refs_ref_iterator_begin( > > if (!len) > > continue; > > > > - strvec_push(&normalized_exclude_patterns, pattern); > > + if (pattern[len - 1] == '/') > > + strvec_push(&normalized_exclude_patterns, pattern); > > + else > > + strvec_pushf(&normalized_exclude_patterns, "%s/", > > + pattern); > > Doesn't this mean that if the user requested to exclude > "refs/heads/bar" and "refs/heads/bar" exists, that we won't exclude it > because it doesn't have a trailing slash? > > >From reading other comments in this thread, I guess that ends up being > okay, because we only promise to filter out what we can cheaply > filter, and we rely on our caller to double-check everything and do > the real filtering. > > ...but it gives me some ugly dir.c vibes, reminding me of 95c11ecc73f2 > (Fix error-prone fill_directory() API; make it only return matches, > 2020-04-01) and a slew of related bugs preceding it. Granted, dir.c > had this tri-state to deal with (tracked, untracked-but-ignored, > untracked-and-not-ignored) and simplifying of whole directories, which > don't apply here, so maybe the similarity of > "fast-filtering-only-and-rely-on-caller" won't be a problem since the > upper level filtering is so much more straightforward. > > Should this at least be called out in the commit message, though? Yeah, I think that we don't have a tri-state here to deal with as was the case in 95c11ecc732 makes this a little easier to reason about. And you're right: if we have a pattern like "refs/heads/bar" and we see a leaf in our reference hierarchy called "refs/heads/bar", the packed backend will not exclude it. This is OK because the exclude pattern stuff is all considered "best-effort" and callers are expected to do their own filtering. Note that the exclude patterns (at least in the packed backend) don't know how to handle meta-characters (there's a big comment in refs/packed-backend.c explaining why). So we can't guarantee the absence of false positives without performing the same post-processing as the caller would. Even prior to this commit, a literal match in the excluded patterns would result in a region whose start- and end-points are the same, and we'd throw it out before it made its way into the jump list. Thanks, Taylor
diff --git a/refs.c b/refs.c index 17d3840aff..2d9a1b51f4 100644 --- a/refs.c +++ b/refs.c @@ -1708,7 +1708,11 @@ struct ref_iterator *refs_ref_iterator_begin( if (!len) continue; - strvec_push(&normalized_exclude_patterns, pattern); + if (pattern[len - 1] == '/') + strvec_push(&normalized_exclude_patterns, pattern); + else + strvec_pushf(&normalized_exclude_patterns, "%s/", + pattern); } exclude_patterns = normalized_exclude_patterns.v; diff --git a/t/t1419-exclude-refs.sh b/t/t1419-exclude-refs.sh index fd58260a24..04797aee59 100755 --- a/t/t1419-exclude-refs.sh +++ b/t/t1419-exclude-refs.sh @@ -46,6 +46,10 @@ test_expect_success 'setup' ' echo "create refs/heads/$name/$i $base" || return 1 done || return 1 done >in && + for i in 5 6 7 + do + echo "create refs/heads/bar/4/$i $base" || return 1 + done >>in && echo "delete refs/heads/main" >>in && git update-ref --stdin <in && @@ -99,9 +103,17 @@ test_expect_success 'adjacent, non-overlapping excluded regions' ' esac ' -test_expect_success 'overlapping excluded regions' ' +test_expect_success 'non-directory excluded regions' ' for_each_ref__exclude refs/heads refs/heads/ba refs/heads/baz >actual 2>perf && - for_each_ref refs/heads/foo refs/heads/quux >expect && + for_each_ref refs/heads/bar refs/heads/foo refs/heads/quux >expect && + + test_cmp expect actual && + assert_jumps 1 perf +' + +test_expect_success 'overlapping excluded regions' ' + for_each_ref__exclude refs/heads refs/heads/bar refs/heads/bar/4 >actual 2>perf && + for_each_ref refs/heads/baz refs/heads/foo refs/heads/quux >expect && test_cmp expect actual && assert_jumps 1 perf
In the packed-refs backend, our implementation of '--exclude' (dating back to 59c35fac54 (refs/packed-backend.c: implement jump lists to avoid excluded pattern(s), 2023-07-10)) considers, for example: $ git for-each-ref --exclude=refs/heads/ba to exclude "refs/heads/bar", "refs/heads/baz", and so on. The files backend, which does not implement '--exclude' (and relies on the caller to cull out results that don't match) naturally will enumerate "refs/heads/bar" and so on. So in the above example, 'for-each-ref' will try and see if "refs/heads/ba" matches "refs/heads/bar" (since the files backend simply enumerated every loose reference), and, realizing that it does not match, output the reference as expected. (A caller that did want to exclude "refs/heads/bar" and "refs/heads/baz" might instead run "git for-each-ref --exclude='refs/heads/ba*'"). This can lead to strange behavior, like seeing a different set of references advertised via 'upload-pack' depending on what set of references were loose versus packed. So there is a subtle bug with '--exclude' which is that in the packed-refs backend we will consider "refs/heads/bar" to be a pattern match against "refs/heads/ba" when we shouldn't. Likewise, the reftable backend (which in this case is bug-compatible with the packed backend) exhibits the same broken behavior. There are a few ways to fix this. One is to tighten the rules in cmp_record_to_refname(), which is used to determine the start/end-points of the jump list used by the packed backend. In this new "strict" mode, the comparison function would handle the case where we've reached the end of the pattern by introducing a new check like so: while (1) { if (*r1 == '\n') return *r2 ? -1 : 0; if (!*r2) if (strict && *r1 != '/') /* <- here */ return 1; return start ? 1 : -1; if (*r1 != *r2) return (unsigned char)*r1 < (unsigned char)*r2 ? -1 : +1; r1++; r2++; } (eliding out the rest of cmp_record_to_refname()). Equivalently, we could teach refs/packed-backend::populate_excluded_jump_list() to append a trailing '/' if one does not already exist, forcing an exclude pattern like "refs/heads/ba" to only match "refs/heads/ba/abc" and so forth. But since the same problem exists in reftable, we can fix both at once by performing this pre-processing step one layer up in refs.c at the common entrypoint for the two, which is 'refs_ref_iterator_begin()'. Since that solution is both the simplest and only requires modification in one spot, let's normalize exclude patterns so that they end with a trailing slash. This causes us to unify the behavior between all three backends. There is some minor test fallout in the "overlapping excluded regions" test, which happens to use 'refs/ba' as an exclude pattern, and expects references under the "refs/heads/bar/*" and "refs/heads/baz/*" hierarchies to be excluded from the results. But that test fallout is expected, because the test was codifying the buggy behavior to begin with, and should have never been written that way. Split that into its own test (since the range is no longer overlapping under the stricter interpretation of --exclude patterns presented here). Create a new test which does have overlapping regions by using a refs/heads/bar/4/... hierarchy and excluding both "refs/heads/bar" and "refs/heads/bar/4". Reported-by: SURA <surak8806@gmail.com> Helped-by: Jeff King <peff@peff.net> Signed-off-by: Taylor Blau <me@ttaylorr.com> --- refs.c | 6 +++++- t/t1419-exclude-refs.sh | 16 ++++++++++++++-- 2 files changed, 19 insertions(+), 3 deletions(-)