* [PATCH 0/1] Properly peel tags in can_all_from_reach_with_flags() @ 2018-09-12 14:22 Derrick Stolee via GitGitGadget 2018-09-12 14:22 ` [PATCH 1/1] commit-reach: properly peel tags Derrick Stolee via GitGitGadget 2018-09-13 16:10 ` [PATCH v2 0/1] Properly peel tags in can_all_from_reach_with_flags() Derrick Stolee via GitGitGadget 0 siblings, 2 replies; 25+ messages in thread From: Derrick Stolee via GitGitGadget @ 2018-09-12 14:22 UTC (permalink / raw) To: git; +Cc: peff, Junio C Hamano As Peff reported [1], the refactored can_all_from_reach_with_flags() method does not properly peel tags. Since the helper method can_all_from_reach() and code in t/helper/test-reach.c all peel tags before getting to this method, it is not super-simple to create a test that demonstrates this. I modified t/helper/test-reach.c to allow calling can_all_from_reach_with_flags() directly, and added a test in t6600-test-reach.sh that demonstrates the segfault without the fix. The fix in commit-reach.c is Peff's fix verbatim. [1] https://public-inbox.org/git/0bf9103c-9377-506b-7ad7-e5273d8e94fc@gmail.com/T/#u Derrick Stolee (1): commit-reach: properly peel tags commit-reach.c | 25 ++++++++++++++++++------- t/helper/test-reach.c | 22 +++++++++++++++++----- t/t6600-test-reach.sh | 30 ++++++++++++++++++++++++++++-- 3 files changed, 63 insertions(+), 14 deletions(-) base-commit: 6621c838743812aaba96e55cfec8524ea1144c2d Published-As: https://github.com/gitgitgadget/git/releases/tags/pr-39%2Fderrickstolee%2Ftag-fix-v1 Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-39/derrickstolee/tag-fix-v1 Pull-Request: https://github.com/gitgitgadget/git/pull/39 -- gitgitgadget ^ permalink raw reply [flat|nested] 25+ messages in thread
* [PATCH 1/1] commit-reach: properly peel tags 2018-09-12 14:22 [PATCH 0/1] Properly peel tags in can_all_from_reach_with_flags() Derrick Stolee via GitGitGadget @ 2018-09-12 14:22 ` Derrick Stolee via GitGitGadget 2018-09-12 19:41 ` Jeff King 2018-09-12 21:23 ` Junio C Hamano 2018-09-13 16:10 ` [PATCH v2 0/1] Properly peel tags in can_all_from_reach_with_flags() Derrick Stolee via GitGitGadget 1 sibling, 2 replies; 25+ messages in thread From: Derrick Stolee via GitGitGadget @ 2018-09-12 14:22 UTC (permalink / raw) To: git; +Cc: peff, Junio C Hamano, Derrick Stolee From: Derrick Stolee <dstolee@microsoft.com> The can_all_from_reach_with_flag() algorithm was refactored in 4fbcca4e "commit-reach: make can_all_from_reach... linear" but incorrectly assumed that all objects provided were commits. During a fetch negotiation, ok_to_give_up() in upload-pack.c may provide unpeeled tags to the 'from' array. The current code creates a segfault. Add a direct call to can_all_from_reach_with_flag() in 'test-tool reach' and add a test in t6600-test-reach.sh that demonstrates this segfault. Correct the issue by peeling tags when investigating the initial list of objects in the 'from' array. Signed-off-by: Jeff King <peff@peff.net> Signed-off-by: Derrick Stolee <dstolee@microsoft.com> --- commit-reach.c | 25 ++++++++++++++++++------- t/helper/test-reach.c | 22 +++++++++++++++++----- t/t6600-test-reach.sh | 30 ++++++++++++++++++++++++++++-- 3 files changed, 63 insertions(+), 14 deletions(-) diff --git a/commit-reach.c b/commit-reach.c index 86715c103c..6de72c6e03 100644 --- a/commit-reach.c +++ b/commit-reach.c @@ -544,20 +544,31 @@ int can_all_from_reach_with_flag(struct object_array *from, { struct commit **list = NULL; int i; + int nr_commits; int result = 1; ALLOC_ARRAY(list, from->nr); + nr_commits = 0; for (i = 0; i < from->nr; i++) { - list[i] = (struct commit *)from->objects[i].item; + struct object *from_one = from->objects[i].item; - if (parse_commit(list[i]) || - list[i]->generation < min_generation) - return 0; + from_one = deref_tag(the_repository, from_one, + "a from object", 0); + if (!from_one || from_one->type != OBJ_COMMIT) { + from->objects[i].item->flags |= assign_flag; + continue; + } + + list[nr_commits] = (struct commit *)from_one; + if (parse_commit(list[nr_commits]) || + list[nr_commits]->generation < min_generation) + return 0; /* is this a leak? */ + nr_commits++; } - QSORT(list, from->nr, compare_commits_by_gen); + QSORT(list, nr_commits, compare_commits_by_gen); - for (i = 0; i < from->nr; i++) { + for (i = 0; i < nr_commits; i++) { /* DFS from list[i] */ struct commit_list *stack = NULL; @@ -600,7 +611,7 @@ int can_all_from_reach_with_flag(struct object_array *from, } cleanup: - for (i = 0; i < from->nr; i++) { + for (i = 0; i < nr_commits; i++) { clear_commit_marks(list[i], RESULT); clear_commit_marks(list[i], assign_flag); } diff --git a/t/helper/test-reach.c b/t/helper/test-reach.c index eb21103998..08d2ea68e8 100644 --- a/t/helper/test-reach.c +++ b/t/helper/test-reach.c @@ -31,6 +31,7 @@ int cmd__reach(int ac, const char **av) struct object_id oid_A, oid_B; struct commit *A, *B; struct commit_list *X, *Y; + struct object_array X_obj = OBJECT_ARRAY_INIT; struct commit **X_array; int X_nr, X_alloc; struct strbuf buf = STRBUF_INIT; @@ -49,7 +50,8 @@ int cmd__reach(int ac, const char **av) while (strbuf_getline(&buf, stdin) != EOF) { struct object_id oid; - struct object *o; + struct object *orig; + struct object *peeled; struct commit *c; if (buf.len < 3) continue; @@ -57,14 +59,14 @@ int cmd__reach(int ac, const char **av) if (get_oid_committish(buf.buf + 2, &oid)) die("failed to resolve %s", buf.buf + 2); - o = parse_object(r, &oid); - o = deref_tag_noverify(o); + orig = parse_object(r, &oid); + peeled = deref_tag_noverify(orig); - if (!o) + if (!peeled) die("failed to load commit for input %s resulting in oid %s\n", buf.buf, oid_to_hex(&oid)); - c = object_as_type(r, o, OBJ_COMMIT, 0); + c = object_as_type(r, peeled, OBJ_COMMIT, 0); if (!c) die("failed to load commit for input %s resulting in oid %s\n", @@ -85,6 +87,7 @@ int cmd__reach(int ac, const char **av) commit_list_insert(c, &X); ALLOC_GROW(X_array, X_nr + 1, X_alloc); X_array[X_nr++] = c; + add_object_array(orig, NULL, &X_obj); break; case 'Y': @@ -113,6 +116,15 @@ int cmd__reach(int ac, const char **av) print_sorted_commit_ids(list); } else if (!strcmp(av[1], "can_all_from_reach")) { printf("%s(X,Y):%d\n", av[1], can_all_from_reach(X, Y, 1)); + } else if (!strcmp(av[1], "can_all_from_reach_with_flag")) { + struct commit_list *iter = Y; + + while (iter) { + iter->item->object.flags |= 2; + iter = iter->next; + } + + printf("%s(X,_,_,0,0):%d\n", av[1], can_all_from_reach_with_flag(&X_obj, 2, 4, 0, 0)); } else if (!strcmp(av[1], "commit_contains")) { struct ref_filter filter; struct contains_cache cache; diff --git a/t/t6600-test-reach.sh b/t/t6600-test-reach.sh index d139a00d1d..f7bf82290b 100755 --- a/t/t6600-test-reach.sh +++ b/t/t6600-test-reach.sh @@ -31,7 +31,8 @@ test_expect_success 'setup' ' for i in $(test_seq 1 10) do test_commit "1-$i" && - git branch -f commit-1-$i + git branch -f commit-1-$i && + git tag -a -m "1-$i" tag-1-$i commit-1-$i done && for j in $(test_seq 1 9) do @@ -39,11 +40,13 @@ test_expect_success 'setup' ' x=$(($j + 1)) && test_commit "$x-1" && git branch -f commit-$x-1 && + git tag -a -m "$x-1" tag-$x-1 commit-$x-1 && for i in $(test_seq 2 10) do git merge commit-$j-$i -m "$x-$i" && - git branch -f commit-$x-$i + git branch -f commit-$x-$i && + git tag -a -m "$x-$i" tag-$x-$i commit-$x-$i done done && git commit-graph write --reachable && @@ -205,6 +208,29 @@ test_expect_success 'can_all_from_reach:miss' ' test_three_modes can_all_from_reach ' +test_expect_success 'can_all_from_reach_with_flag: tags case' ' + cat >input <<-\EOF && + X:tag-2-10 + X:tag-3-9 + X:tag-4-8 + X:commit-5-7 + X:commit-6-6 + X:commit-7-5 + X:commit-8-4 + X:commit-9-3 + Y:tag-1-9 + Y:tag-2-8 + Y:tag-3-7 + Y:commit-4-6 + Y:commit-5-5 + Y:commit-6-4 + Y:commit-7-3 + Y:commit-8-1 + EOF + echo "can_all_from_reach_with_flag(X,_,_,0,0):1" >expect && + test_three_modes can_all_from_reach_with_flag +' + test_expect_success 'commit_contains:hit' ' cat >input <<-\EOF && A:commit-7-7 -- gitgitgadget ^ permalink raw reply related [flat|nested] 25+ messages in thread
* Re: [PATCH 1/1] commit-reach: properly peel tags 2018-09-12 14:22 ` [PATCH 1/1] commit-reach: properly peel tags Derrick Stolee via GitGitGadget @ 2018-09-12 19:41 ` Jeff King 2018-09-12 21:23 ` Junio C Hamano 1 sibling, 0 replies; 25+ messages in thread From: Jeff King @ 2018-09-12 19:41 UTC (permalink / raw) To: Derrick Stolee via GitGitGadget; +Cc: git, Junio C Hamano, Derrick Stolee On Wed, Sep 12, 2018 at 07:22:56AM -0700, Derrick Stolee via GitGitGadget wrote: > From: Derrick Stolee <dstolee@microsoft.com> > > The can_all_from_reach_with_flag() algorithm was refactored in 4fbcca4e > "commit-reach: make can_all_from_reach... linear" but incorrectly > assumed that all objects provided were commits. During a fetch > negotiation, ok_to_give_up() in upload-pack.c may provide unpeeled tags > to the 'from' array. The current code creates a segfault. > > Add a direct call to can_all_from_reach_with_flag() in 'test-tool reach' > and add a test in t6600-test-reach.sh that demonstrates this segfault. Thanks, that makes a lot of sense for reproducing. I almost wonder if the whole X_array of commits in test-reach could just go away, and we'd feed whatever list of objects the caller happens to send. That may make it simpler to include non-commit objects in a variety of tests. That said, I didn't look closely at other fallout in the program from that, so I'll defer to your judgement. > Correct the issue by peeling tags when investigating the initial list > of objects in the 'from' array. > > Signed-off-by: Jeff King <peff@peff.net> I'm not sure if this should just be Reported-by, since I don't know that I actually contributed any code. ;) But for anything I might have contributed, certainly you have my signoff. > for (i = 0; i < from->nr; i++) { > - list[i] = (struct commit *)from->objects[i].item; > + struct object *from_one = from->objects[i].item; > > - if (parse_commit(list[i]) || > - list[i]->generation < min_generation) > - return 0; > + from_one = deref_tag(the_repository, from_one, > + "a from object", 0); > + if (!from_one || from_one->type != OBJ_COMMIT) { > + from->objects[i].item->flags |= assign_flag; > + continue; > + } I didn't resurrect the comment from this conditional that was in the original code (mostly because I wasn't sure if the reasoning was still entirely valid, or what setting the flag here actually means). But it's probably worth saying something here to explain why it's OK to punt on this case, and what it means to just set the flag. > [...] The rest of the patch looks sane to me. I didn't go through the trouble to reproduce the segfault with the test, but it sounds like you did. -Peff ^ permalink raw reply [flat|nested] 25+ messages in thread
* Re: [PATCH 1/1] commit-reach: properly peel tags 2018-09-12 14:22 ` [PATCH 1/1] commit-reach: properly peel tags Derrick Stolee via GitGitGadget 2018-09-12 19:41 ` Jeff King @ 2018-09-12 21:23 ` Junio C Hamano 2018-09-12 21:34 ` Jeff King 1 sibling, 1 reply; 25+ messages in thread From: Junio C Hamano @ 2018-09-12 21:23 UTC (permalink / raw) To: Derrick Stolee via GitGitGadget; +Cc: git, peff, Derrick Stolee "Derrick Stolee via GitGitGadget" <gitgitgadget@gmail.com> writes: > diff --git a/commit-reach.c b/commit-reach.c > index 86715c103c..6de72c6e03 100644 > --- a/commit-reach.c > +++ b/commit-reach.c > @@ -544,20 +544,31 @@ int can_all_from_reach_with_flag(struct object_array *from, > { > struct commit **list = NULL; > int i; > + int nr_commits; > int result = 1; > > ALLOC_ARRAY(list, from->nr); > + nr_commits = 0; > for (i = 0; i < from->nr; i++) { > - list[i] = (struct commit *)from->objects[i].item; > + struct object *from_one = from->objects[i].item; > > - if (parse_commit(list[i]) || > - list[i]->generation < min_generation) > - return 0; > + from_one = deref_tag(the_repository, from_one, > + "a from object", 0); > + if (!from_one || from_one->type != OBJ_COMMIT) { > + from->objects[i].item->flags |= assign_flag; I wondered why this is not futzing with "from_one->flags"; by going back to the original from->objects[] array, the code is setting the flags on the original tag object and not the non-commit object that was pointed at by the tag. > + continue; > + } > + > + list[nr_commits] = (struct commit *)from_one; > + if (parse_commit(list[nr_commits]) || > + list[nr_commits]->generation < min_generation) > + return 0; /* is this a leak? */ > + nr_commits++; > } In the original code, the flags bits were left unchanged if the loop terminated by hitting a commit whose generation is too young (or parse_commit() returns non-zero). With this updated code, flags bit can be modified before the code notices the situation and leave the function, bypassing the "cleanup" we see below that clears the "assign_flag" bits. Would it be a problem that we return early without cleaning up? Even if we do not call this early return, the assign_flag bits added to the original tag in from->objects[i].item won't be cleaned in this new code, as "cleanup:" section now loops over the list[] that omits the object whose flags was smudged above before the "continue". Would it be a problem that we leave the assign_flags without cleaning up? > - QSORT(list, from->nr, compare_commits_by_gen); > + QSORT(list, nr_commits, compare_commits_by_gen); > > - for (i = 0; i < from->nr; i++) { > + for (i = 0; i < nr_commits; i++) { > /* DFS from list[i] */ > struct commit_list *stack = NULL; > > @@ -600,7 +611,7 @@ int can_all_from_reach_with_flag(struct object_array *from, > } > > cleanup: > - for (i = 0; i < from->nr; i++) { > + for (i = 0; i < nr_commits; i++) { > clear_commit_marks(list[i], RESULT); > clear_commit_marks(list[i], assign_flag); > } ^ permalink raw reply [flat|nested] 25+ messages in thread
* Re: [PATCH 1/1] commit-reach: properly peel tags 2018-09-12 21:23 ` Junio C Hamano @ 2018-09-12 21:34 ` Jeff King 0 siblings, 0 replies; 25+ messages in thread From: Jeff King @ 2018-09-12 21:34 UTC (permalink / raw) To: Junio C Hamano; +Cc: Derrick Stolee via GitGitGadget, git, Derrick Stolee On Wed, Sep 12, 2018 at 02:23:42PM -0700, Junio C Hamano wrote: > > diff --git a/commit-reach.c b/commit-reach.c > > index 86715c103c..6de72c6e03 100644 > > --- a/commit-reach.c > > +++ b/commit-reach.c > > @@ -544,20 +544,31 @@ int can_all_from_reach_with_flag(struct object_array *from, > > { > > struct commit **list = NULL; > > int i; > > + int nr_commits; > > int result = 1; > > > > ALLOC_ARRAY(list, from->nr); > > + nr_commits = 0; > > for (i = 0; i < from->nr; i++) { > > - list[i] = (struct commit *)from->objects[i].item; > > + struct object *from_one = from->objects[i].item; > > > > - if (parse_commit(list[i]) || > > - list[i]->generation < min_generation) > > - return 0; > > + from_one = deref_tag(the_repository, from_one, > > + "a from object", 0); > > + if (!from_one || from_one->type != OBJ_COMMIT) { > > + from->objects[i].item->flags |= assign_flag; > > I wondered why this is not futzing with "from_one->flags"; by going > back to the original from->objects[] array, the code is setting the > flags on the original tag object and not the non-commit object that > was pointed at by the tag. Note that from_one may even be NULL. > > + continue; > > + } > > + > > + list[nr_commits] = (struct commit *)from_one; > > + if (parse_commit(list[nr_commits]) || > > + list[nr_commits]->generation < min_generation) > > + return 0; /* is this a leak? */ > > + nr_commits++; > > } > > In the original code, the flags bits were left unchanged if the loop > terminated by hitting a commit whose generation is too young (or > parse_commit() returns non-zero). With this updated code, flags bit > can be modified before the code notices the situation and leave the > function, bypassing the "cleanup" we see below that clears the > "assign_flag" bits. > > Would it be a problem that we return early without cleaning up? > > Even if we do not call this early return, the assign_flag bits added > to the original tag in from->objects[i].item won't be cleaned in > this new code, as "cleanup:" section now loops over the list[] that > omits the object whose flags was smudged above before the "continue". > > Would it be a problem that we leave the assign_flags without > cleaning up? Yeah, I hadn't thought about the bit cleanup when making my original suggestion. In the original code (before 4fbcca4eff), I think we did set flags as we iterated through the loop, and we could still do an early return when we hit "!reachable(...)". But I don't see any cleanup of assign_flag there at all. So I guess I'm pretty confused about what the semantics are supposed to be. -Peff ^ permalink raw reply [flat|nested] 25+ messages in thread
* [PATCH v2 0/1] Properly peel tags in can_all_from_reach_with_flags() 2018-09-12 14:22 [PATCH 0/1] Properly peel tags in can_all_from_reach_with_flags() Derrick Stolee via GitGitGadget 2018-09-12 14:22 ` [PATCH 1/1] commit-reach: properly peel tags Derrick Stolee via GitGitGadget @ 2018-09-13 16:10 ` Derrick Stolee via GitGitGadget 2018-09-13 16:10 ` [PATCH v2 1/1] commit-reach: properly peel tags Derrick Stolee via GitGitGadget 2018-09-21 15:05 ` [PATCH v3 0/2] Properly peel tags in can_all_from_reach_with_flags() Derrick Stolee via GitGitGadget 1 sibling, 2 replies; 25+ messages in thread From: Derrick Stolee via GitGitGadget @ 2018-09-13 16:10 UTC (permalink / raw) To: git; +Cc: peff, Junio C Hamano As Peff reported [1], the refactored can_all_from_reach_with_flags() method does not properly peel tags. Since the helper method can_all_from_reach() and code in t/helper/test-reach.c all peel tags before getting to this method, it is not super-simple to create a test that demonstrates this. I modified t/helper/test-reach.c to allow calling can_all_from_reach_with_flags() directly, and added a test in t6600-test-reach.sh that demonstrates the segfault without the fix. For V2, I compared the loop that inspects the 'from' commits in commit ba3ca1edce "commit-reach: move can_all_from_reach_with_flags" to the version here and got the following diff: 3c3 < if (from_one->flags & assign_flag) --- > if (!from_one || from_one->flags & assign_flag) 5c5,7 < from_one = deref_tag(the_repository, from_one, "a from object", 0); --- > > from_one = deref_tag(the_repository, from_one, > "a from object", 0); 14a17,22 > > list[nr_commits] = (struct commit *)from_one; > if (parse_commit(list[nr_commits]) || > list[nr_commits]->generation < min_generation) > return 0; /* is this a leak? */ > nr_commits++; This diff includes the early termination we had before 'deref_tag' and the comment for why we can ignore non-commit objects. [1] https://public-inbox.org/git/0bf9103c-9377-506b-7ad7-e5273d8e94fc@gmail.com/T/#u Derrick Stolee (1): commit-reach: properly peel tags commit-reach.c | 33 ++++++++++++++++++++++++++------- t/helper/test-reach.c | 22 +++++++++++++++++----- t/t6600-test-reach.sh | 30 ++++++++++++++++++++++++++++-- 3 files changed, 71 insertions(+), 14 deletions(-) base-commit: 6621c838743812aaba96e55cfec8524ea1144c2d Published-As: https://github.com/gitgitgadget/git/releases/tags/pr-39%2Fderrickstolee%2Ftag-fix-v2 Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-39/derrickstolee/tag-fix-v2 Pull-Request: https://github.com/gitgitgadget/git/pull/39 Range-diff vs v1: 1: 948e222228 ! 1: 4bf21204dd commit-reach: properly peel tags @@ -36,9 +36,17 @@ - if (parse_commit(list[i]) || - list[i]->generation < min_generation) - return 0; ++ if (!from_one || from_one->flags & assign_flag) ++ continue; ++ + from_one = deref_tag(the_repository, from_one, + "a from object", 0); + if (!from_one || from_one->type != OBJ_COMMIT) { ++ /* no way to tell if this is reachable by ++ * looking at the ancestry chain alone, so ++ * leave a note to ourselves not to worry about ++ * this object anymore. ++ */ + from->objects[i].item->flags |= assign_flag; + continue; + } @@ -187,7 +195,7 @@ + echo "can_all_from_reach_with_flag(X,_,_,0,0):1" >expect && + test_three_modes can_all_from_reach_with_flag +' -+ ++ test_expect_success 'commit_contains:hit' ' cat >input <<-\EOF && A:commit-7-7 -- gitgitgadget ^ permalink raw reply [flat|nested] 25+ messages in thread
* [PATCH v2 1/1] commit-reach: properly peel tags 2018-09-13 16:10 ` [PATCH v2 0/1] Properly peel tags in can_all_from_reach_with_flags() Derrick Stolee via GitGitGadget @ 2018-09-13 16:10 ` Derrick Stolee via GitGitGadget 2018-09-13 16:38 ` Derrick Stolee 2018-09-21 15:05 ` [PATCH v3 0/2] Properly peel tags in can_all_from_reach_with_flags() Derrick Stolee via GitGitGadget 1 sibling, 1 reply; 25+ messages in thread From: Derrick Stolee via GitGitGadget @ 2018-09-13 16:10 UTC (permalink / raw) To: git; +Cc: peff, Junio C Hamano, Derrick Stolee From: Derrick Stolee <dstolee@microsoft.com> The can_all_from_reach_with_flag() algorithm was refactored in 4fbcca4e "commit-reach: make can_all_from_reach... linear" but incorrectly assumed that all objects provided were commits. During a fetch negotiation, ok_to_give_up() in upload-pack.c may provide unpeeled tags to the 'from' array. The current code creates a segfault. Add a direct call to can_all_from_reach_with_flag() in 'test-tool reach' and add a test in t6600-test-reach.sh that demonstrates this segfault. Correct the issue by peeling tags when investigating the initial list of objects in the 'from' array. Signed-off-by: Jeff King <peff@peff.net> Signed-off-by: Derrick Stolee <dstolee@microsoft.com> --- commit-reach.c | 33 ++++++++++++++++++++++++++------- t/helper/test-reach.c | 22 +++++++++++++++++----- t/t6600-test-reach.sh | 30 ++++++++++++++++++++++++++++-- 3 files changed, 71 insertions(+), 14 deletions(-) diff --git a/commit-reach.c b/commit-reach.c index 86715c103c..4048a2132a 100644 --- a/commit-reach.c +++ b/commit-reach.c @@ -544,20 +544,39 @@ int can_all_from_reach_with_flag(struct object_array *from, { struct commit **list = NULL; int i; + int nr_commits; int result = 1; ALLOC_ARRAY(list, from->nr); + nr_commits = 0; for (i = 0; i < from->nr; i++) { - list[i] = (struct commit *)from->objects[i].item; + struct object *from_one = from->objects[i].item; - if (parse_commit(list[i]) || - list[i]->generation < min_generation) - return 0; + if (!from_one || from_one->flags & assign_flag) + continue; + + from_one = deref_tag(the_repository, from_one, + "a from object", 0); + if (!from_one || from_one->type != OBJ_COMMIT) { + /* no way to tell if this is reachable by + * looking at the ancestry chain alone, so + * leave a note to ourselves not to worry about + * this object anymore. + */ + from->objects[i].item->flags |= assign_flag; + continue; + } + + list[nr_commits] = (struct commit *)from_one; + if (parse_commit(list[nr_commits]) || + list[nr_commits]->generation < min_generation) + return 0; /* is this a leak? */ + nr_commits++; } - QSORT(list, from->nr, compare_commits_by_gen); + QSORT(list, nr_commits, compare_commits_by_gen); - for (i = 0; i < from->nr; i++) { + for (i = 0; i < nr_commits; i++) { /* DFS from list[i] */ struct commit_list *stack = NULL; @@ -600,7 +619,7 @@ int can_all_from_reach_with_flag(struct object_array *from, } cleanup: - for (i = 0; i < from->nr; i++) { + for (i = 0; i < nr_commits; i++) { clear_commit_marks(list[i], RESULT); clear_commit_marks(list[i], assign_flag); } diff --git a/t/helper/test-reach.c b/t/helper/test-reach.c index eb21103998..08d2ea68e8 100644 --- a/t/helper/test-reach.c +++ b/t/helper/test-reach.c @@ -31,6 +31,7 @@ int cmd__reach(int ac, const char **av) struct object_id oid_A, oid_B; struct commit *A, *B; struct commit_list *X, *Y; + struct object_array X_obj = OBJECT_ARRAY_INIT; struct commit **X_array; int X_nr, X_alloc; struct strbuf buf = STRBUF_INIT; @@ -49,7 +50,8 @@ int cmd__reach(int ac, const char **av) while (strbuf_getline(&buf, stdin) != EOF) { struct object_id oid; - struct object *o; + struct object *orig; + struct object *peeled; struct commit *c; if (buf.len < 3) continue; @@ -57,14 +59,14 @@ int cmd__reach(int ac, const char **av) if (get_oid_committish(buf.buf + 2, &oid)) die("failed to resolve %s", buf.buf + 2); - o = parse_object(r, &oid); - o = deref_tag_noverify(o); + orig = parse_object(r, &oid); + peeled = deref_tag_noverify(orig); - if (!o) + if (!peeled) die("failed to load commit for input %s resulting in oid %s\n", buf.buf, oid_to_hex(&oid)); - c = object_as_type(r, o, OBJ_COMMIT, 0); + c = object_as_type(r, peeled, OBJ_COMMIT, 0); if (!c) die("failed to load commit for input %s resulting in oid %s\n", @@ -85,6 +87,7 @@ int cmd__reach(int ac, const char **av) commit_list_insert(c, &X); ALLOC_GROW(X_array, X_nr + 1, X_alloc); X_array[X_nr++] = c; + add_object_array(orig, NULL, &X_obj); break; case 'Y': @@ -113,6 +116,15 @@ int cmd__reach(int ac, const char **av) print_sorted_commit_ids(list); } else if (!strcmp(av[1], "can_all_from_reach")) { printf("%s(X,Y):%d\n", av[1], can_all_from_reach(X, Y, 1)); + } else if (!strcmp(av[1], "can_all_from_reach_with_flag")) { + struct commit_list *iter = Y; + + while (iter) { + iter->item->object.flags |= 2; + iter = iter->next; + } + + printf("%s(X,_,_,0,0):%d\n", av[1], can_all_from_reach_with_flag(&X_obj, 2, 4, 0, 0)); } else if (!strcmp(av[1], "commit_contains")) { struct ref_filter filter; struct contains_cache cache; diff --git a/t/t6600-test-reach.sh b/t/t6600-test-reach.sh index d139a00d1d..ae94b27f70 100755 --- a/t/t6600-test-reach.sh +++ b/t/t6600-test-reach.sh @@ -31,7 +31,8 @@ test_expect_success 'setup' ' for i in $(test_seq 1 10) do test_commit "1-$i" && - git branch -f commit-1-$i + git branch -f commit-1-$i && + git tag -a -m "1-$i" tag-1-$i commit-1-$i done && for j in $(test_seq 1 9) do @@ -39,11 +40,13 @@ test_expect_success 'setup' ' x=$(($j + 1)) && test_commit "$x-1" && git branch -f commit-$x-1 && + git tag -a -m "$x-1" tag-$x-1 commit-$x-1 && for i in $(test_seq 2 10) do git merge commit-$j-$i -m "$x-$i" && - git branch -f commit-$x-$i + git branch -f commit-$x-$i && + git tag -a -m "$x-$i" tag-$x-$i commit-$x-$i done done && git commit-graph write --reachable && @@ -205,6 +208,29 @@ test_expect_success 'can_all_from_reach:miss' ' test_three_modes can_all_from_reach ' +test_expect_success 'can_all_from_reach_with_flag: tags case' ' + cat >input <<-\EOF && + X:tag-2-10 + X:tag-3-9 + X:tag-4-8 + X:commit-5-7 + X:commit-6-6 + X:commit-7-5 + X:commit-8-4 + X:commit-9-3 + Y:tag-1-9 + Y:tag-2-8 + Y:tag-3-7 + Y:commit-4-6 + Y:commit-5-5 + Y:commit-6-4 + Y:commit-7-3 + Y:commit-8-1 + EOF + echo "can_all_from_reach_with_flag(X,_,_,0,0):1" >expect && + test_three_modes can_all_from_reach_with_flag +' + test_expect_success 'commit_contains:hit' ' cat >input <<-\EOF && A:commit-7-7 -- gitgitgadget ^ permalink raw reply related [flat|nested] 25+ messages in thread
* Re: [PATCH v2 1/1] commit-reach: properly peel tags 2018-09-13 16:10 ` [PATCH v2 1/1] commit-reach: properly peel tags Derrick Stolee via GitGitGadget @ 2018-09-13 16:38 ` Derrick Stolee 2018-09-13 21:06 ` Junio C Hamano 0 siblings, 1 reply; 25+ messages in thread From: Derrick Stolee @ 2018-09-13 16:38 UTC (permalink / raw) To: Derrick Stolee via GitGitGadget, git; +Cc: peff, Junio C Hamano, Derrick Stolee On 9/13/2018 12:10 PM, Derrick Stolee via GitGitGadget wrote: > From: Derrick Stolee <dstolee@microsoft.com> > > The can_all_from_reach_with_flag() algorithm was refactored in 4fbcca4e > "commit-reach: make can_all_from_reach... linear" but incorrectly > assumed that all objects provided were commits. During a fetch > negotiation, ok_to_give_up() in upload-pack.c may provide unpeeled tags > to the 'from' array. The current code creates a segfault. > > Add a direct call to can_all_from_reach_with_flag() in 'test-tool reach' > and add a test in t6600-test-reach.sh that demonstrates this segfault. > > Correct the issue by peeling tags when investigating the initial list > of objects in the 'from' array. > > Signed-off-by: Jeff King <peff@peff.net> > Signed-off-by: Derrick Stolee <dstolee@microsoft.com> > --- > commit-reach.c | 33 ++++++++++++++++++++++++++------- > t/helper/test-reach.c | 22 +++++++++++++++++----- > t/t6600-test-reach.sh | 30 ++++++++++++++++++++++++++++-- > 3 files changed, 71 insertions(+), 14 deletions(-) > > diff --git a/commit-reach.c b/commit-reach.c > index 86715c103c..4048a2132a 100644 > --- a/commit-reach.c > +++ b/commit-reach.c > @@ -544,20 +544,39 @@ int can_all_from_reach_with_flag(struct object_array *from, > { > struct commit **list = NULL; > int i; > + int nr_commits; > int result = 1; > > ALLOC_ARRAY(list, from->nr); > + nr_commits = 0; > for (i = 0; i < from->nr; i++) { > - list[i] = (struct commit *)from->objects[i].item; > + struct object *from_one = from->objects[i].item; > > - if (parse_commit(list[i]) || > - list[i]->generation < min_generation) > - return 0; > + if (!from_one || from_one->flags & assign_flag) > + continue; > + > + from_one = deref_tag(the_repository, from_one, > + "a from object", 0); > + if (!from_one || from_one->type != OBJ_COMMIT) { > + /* no way to tell if this is reachable by > + * looking at the ancestry chain alone, so > + * leave a note to ourselves not to worry about > + * this object anymore. > + */ > + from->objects[i].item->flags |= assign_flag; > + continue; > + } > + > + list[nr_commits] = (struct commit *)from_one; > + if (parse_commit(list[nr_commits]) || > + list[nr_commits]->generation < min_generation) > + return 0; /* is this a leak? */ Of course, after sending v2, I see this comment. This is a leak of 'list' and should be fixed. Not only is it a leak here, it is also a leak in the 'cleanup' section. I'll squash the following into v3, but I'll let v2 simmer for review before rerolling. diff --git a/commit-reach.c b/commit-reach.c index 4048a2132a..c457d8d85f 100644 --- a/commit-reach.c +++ b/commit-reach.c @@ -569,8 +569,11 @@ int can_all_from_reach_with_flag(struct object_array *from, list[nr_commits] = (struct commit *)from_one; if (parse_commit(list[nr_commits]) || - list[nr_commits]->generation < min_generation) - return 0; /* is this a leak? */ + list[nr_commits]->generation < min_generation) { + result = 0; + goto cleanup; + } + nr_commits++; } @@ -623,6 +626,7 @@ int can_all_from_reach_with_flag(struct object_array *from, clear_commit_marks(list[i], RESULT); clear_commit_marks(list[i], assign_flag); } + free(list); return result; } ^ permalink raw reply related [flat|nested] 25+ messages in thread
* Re: [PATCH v2 1/1] commit-reach: properly peel tags 2018-09-13 16:38 ` Derrick Stolee @ 2018-09-13 21:06 ` Junio C Hamano 0 siblings, 0 replies; 25+ messages in thread From: Junio C Hamano @ 2018-09-13 21:06 UTC (permalink / raw) To: Derrick Stolee; +Cc: Derrick Stolee via GitGitGadget, git, peff, Derrick Stolee Derrick Stolee <stolee@gmail.com> writes: >> + if (!from_one || from_one->type != OBJ_COMMIT) { >> + /* no way to tell if this is reachable by >> + * looking at the ancestry chain alone, so >> + * leave a note to ourselves not to worry about >> + * this object anymore. >> + */ >> + from->objects[i].item->flags |= assign_flag; >> + continue; >> + } >> + >> + list[nr_commits] = (struct commit *)from_one; >> + if (parse_commit(list[nr_commits]) || >> + list[nr_commits]->generation < min_generation) >> + return 0; /* is this a leak? */ > > Of course, after sending v2, I see this comment. This is a leak of > 'list' and should be fixed. > > Not only is it a leak here, it is also a leak in the 'cleanup' > section. I'll squash the following into v3, but I'll let v2 simmer for > review before rerolling. > > diff --git a/commit-reach.c b/commit-reach.c > index 4048a2132a..c457d8d85f 100644 > --- a/commit-reach.c > +++ b/commit-reach.c > @@ -569,8 +569,11 @@ int can_all_from_reach_with_flag(struct > object_array *from, > > list[nr_commits] = (struct commit *)from_one; > if (parse_commit(list[nr_commits]) || > - list[nr_commits]->generation < min_generation) > - return 0; /* is this a leak? */ > + list[nr_commits]->generation < min_generation) { > + result = 0; > + goto cleanup; > + } > + > nr_commits++; > } > > @@ -623,6 +626,7 @@ int can_all_from_reach_with_flag(struct > object_array *from, > clear_commit_marks(list[i], RESULT); > clear_commit_marks(list[i], assign_flag); > } > + free(list); > return result; > } With this, commit marks are cleared even when we do the "early return", but only for the objects that appear in the resulting list[]. Because the for() loop in the last hunk interates over list[], those non-commit objects that are smudged with assign_flag but never made to list[] will be left smudged when this function returns (this is true when there is no early return). Is that intended? ^ permalink raw reply [flat|nested] 25+ messages in thread
* [PATCH v3 0/2] Properly peel tags in can_all_from_reach_with_flags() 2018-09-13 16:10 ` [PATCH v2 0/1] Properly peel tags in can_all_from_reach_with_flags() Derrick Stolee via GitGitGadget 2018-09-13 16:10 ` [PATCH v2 1/1] commit-reach: properly peel tags Derrick Stolee via GitGitGadget @ 2018-09-21 15:05 ` Derrick Stolee via GitGitGadget 2018-09-21 15:05 ` [PATCH v3 1/2] commit-reach: properly peel tags Derrick Stolee via GitGitGadget ` (2 more replies) 1 sibling, 3 replies; 25+ messages in thread From: Derrick Stolee via GitGitGadget @ 2018-09-21 15:05 UTC (permalink / raw) To: git; +Cc: peff, Junio C Hamano As Peff reported [1], the refactored can_all_from_reach_with_flags() method does not properly peel tags. Since the helper method can_all_from_reach() and code in t/helper/test-reach.c all peel tags before getting to this method, it is not super-simple to create a test that demonstrates this. I modified t/helper/test-reach.c to allow calling can_all_from_reach_with_flags() directly, and added a test in t6600-test-reach.sh that demonstrates the segfault without the fix. For V2, I compared the loop that inspects the 'from' commits in commit ba3ca1edce "commit-reach: move can_all_from_reach_with_flags" to the version here and got the following diff: 3c3 < if (from_one->flags & assign_flag) --- > if (!from_one || from_one->flags & assign_flag) 5c5,7 < from_one = deref_tag(the_repository, from_one, "a from object", 0); --- > > from_one = deref_tag(the_repository, from_one, > "a from object", 0); 14a17,22 > > list[nr_commits] = (struct commit *)from_one; > if (parse_commit(list[nr_commits]) || > list[nr_commits]->generation < min_generation) > return 0; /* is this a leak? */ > nr_commits++; This diff includes the early termination we had before 'deref_tag' and the comment for why we can ignore non-commit objects. [1] https://public-inbox.org/git/0bf9103c-9377-506b-7ad7-e5273d8e94fc@gmail.com/T/#u Derrick Stolee (2): commit-reach: properly peel tags commit-reach: fix memory and flag leaks commit-reach.c | 41 ++++++++++++++++++++++++++++++++++------- t/helper/test-reach.c | 22 +++++++++++++++++----- t/t6600-test-reach.sh | 30 ++++++++++++++++++++++++++++-- 3 files changed, 79 insertions(+), 14 deletions(-) base-commit: 6621c838743812aaba96e55cfec8524ea1144c2d Published-As: https://github.com/gitgitgadget/git/releases/tags/pr-39%2Fderrickstolee%2Ftag-fix-v3 Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-39/derrickstolee/tag-fix-v3 Pull-Request: https://github.com/gitgitgadget/git/pull/39 Range-diff vs v2: 1: 4bf21204dd ! 1: 0a1e661271 commit-reach: properly peel tags @@ -53,8 +53,11 @@ + + list[nr_commits] = (struct commit *)from_one; + if (parse_commit(list[nr_commits]) || -+ list[nr_commits]->generation < min_generation) -+ return 0; /* is this a leak? */ ++ list[nr_commits]->generation < min_generation) { ++ result = 0; ++ goto cleanup; ++ } ++ + nr_commits++; } -: ---------- > 2: b2e0ee4978 commit-reach: fix memory and flag leaks -- gitgitgadget ^ permalink raw reply [flat|nested] 25+ messages in thread
* [PATCH v3 1/2] commit-reach: properly peel tags 2018-09-21 15:05 ` [PATCH v3 0/2] Properly peel tags in can_all_from_reach_with_flags() Derrick Stolee via GitGitGadget @ 2018-09-21 15:05 ` Derrick Stolee via GitGitGadget 2018-09-21 23:56 ` Jeff King 2018-09-21 15:05 ` [PATCH v3 2/2] commit-reach: fix memory and flag leaks Derrick Stolee via GitGitGadget 2018-09-24 20:57 ` [PATCH v4 0/1] Properly peel tags in can_all_from_reach_with_flags() Derrick Stolee via GitGitGadget 2 siblings, 1 reply; 25+ messages in thread From: Derrick Stolee via GitGitGadget @ 2018-09-21 15:05 UTC (permalink / raw) To: git; +Cc: peff, Junio C Hamano, Derrick Stolee From: Derrick Stolee <dstolee@microsoft.com> The can_all_from_reach_with_flag() algorithm was refactored in 4fbcca4e "commit-reach: make can_all_from_reach... linear" but incorrectly assumed that all objects provided were commits. During a fetch negotiation, ok_to_give_up() in upload-pack.c may provide unpeeled tags to the 'from' array. The current code creates a segfault. Add a direct call to can_all_from_reach_with_flag() in 'test-tool reach' and add a test in t6600-test-reach.sh that demonstrates this segfault. Correct the issue by peeling tags when investigating the initial list of objects in the 'from' array. Signed-off-by: Jeff King <peff@peff.net> Signed-off-by: Derrick Stolee <dstolee@microsoft.com> --- commit-reach.c | 36 +++++++++++++++++++++++++++++------- t/helper/test-reach.c | 22 +++++++++++++++++----- t/t6600-test-reach.sh | 30 ++++++++++++++++++++++++++++-- 3 files changed, 74 insertions(+), 14 deletions(-) diff --git a/commit-reach.c b/commit-reach.c index 86715c103c..e748414d04 100644 --- a/commit-reach.c +++ b/commit-reach.c @@ -544,20 +544,42 @@ int can_all_from_reach_with_flag(struct object_array *from, { struct commit **list = NULL; int i; + int nr_commits; int result = 1; ALLOC_ARRAY(list, from->nr); + nr_commits = 0; for (i = 0; i < from->nr; i++) { - list[i] = (struct commit *)from->objects[i].item; + struct object *from_one = from->objects[i].item; - if (parse_commit(list[i]) || - list[i]->generation < min_generation) - return 0; + if (!from_one || from_one->flags & assign_flag) + continue; + + from_one = deref_tag(the_repository, from_one, + "a from object", 0); + if (!from_one || from_one->type != OBJ_COMMIT) { + /* no way to tell if this is reachable by + * looking at the ancestry chain alone, so + * leave a note to ourselves not to worry about + * this object anymore. + */ + from->objects[i].item->flags |= assign_flag; + continue; + } + + list[nr_commits] = (struct commit *)from_one; + if (parse_commit(list[nr_commits]) || + list[nr_commits]->generation < min_generation) { + result = 0; + goto cleanup; + } + + nr_commits++; } - QSORT(list, from->nr, compare_commits_by_gen); + QSORT(list, nr_commits, compare_commits_by_gen); - for (i = 0; i < from->nr; i++) { + for (i = 0; i < nr_commits; i++) { /* DFS from list[i] */ struct commit_list *stack = NULL; @@ -600,7 +622,7 @@ int can_all_from_reach_with_flag(struct object_array *from, } cleanup: - for (i = 0; i < from->nr; i++) { + for (i = 0; i < nr_commits; i++) { clear_commit_marks(list[i], RESULT); clear_commit_marks(list[i], assign_flag); } diff --git a/t/helper/test-reach.c b/t/helper/test-reach.c index eb21103998..08d2ea68e8 100644 --- a/t/helper/test-reach.c +++ b/t/helper/test-reach.c @@ -31,6 +31,7 @@ int cmd__reach(int ac, const char **av) struct object_id oid_A, oid_B; struct commit *A, *B; struct commit_list *X, *Y; + struct object_array X_obj = OBJECT_ARRAY_INIT; struct commit **X_array; int X_nr, X_alloc; struct strbuf buf = STRBUF_INIT; @@ -49,7 +50,8 @@ int cmd__reach(int ac, const char **av) while (strbuf_getline(&buf, stdin) != EOF) { struct object_id oid; - struct object *o; + struct object *orig; + struct object *peeled; struct commit *c; if (buf.len < 3) continue; @@ -57,14 +59,14 @@ int cmd__reach(int ac, const char **av) if (get_oid_committish(buf.buf + 2, &oid)) die("failed to resolve %s", buf.buf + 2); - o = parse_object(r, &oid); - o = deref_tag_noverify(o); + orig = parse_object(r, &oid); + peeled = deref_tag_noverify(orig); - if (!o) + if (!peeled) die("failed to load commit for input %s resulting in oid %s\n", buf.buf, oid_to_hex(&oid)); - c = object_as_type(r, o, OBJ_COMMIT, 0); + c = object_as_type(r, peeled, OBJ_COMMIT, 0); if (!c) die("failed to load commit for input %s resulting in oid %s\n", @@ -85,6 +87,7 @@ int cmd__reach(int ac, const char **av) commit_list_insert(c, &X); ALLOC_GROW(X_array, X_nr + 1, X_alloc); X_array[X_nr++] = c; + add_object_array(orig, NULL, &X_obj); break; case 'Y': @@ -113,6 +116,15 @@ int cmd__reach(int ac, const char **av) print_sorted_commit_ids(list); } else if (!strcmp(av[1], "can_all_from_reach")) { printf("%s(X,Y):%d\n", av[1], can_all_from_reach(X, Y, 1)); + } else if (!strcmp(av[1], "can_all_from_reach_with_flag")) { + struct commit_list *iter = Y; + + while (iter) { + iter->item->object.flags |= 2; + iter = iter->next; + } + + printf("%s(X,_,_,0,0):%d\n", av[1], can_all_from_reach_with_flag(&X_obj, 2, 4, 0, 0)); } else if (!strcmp(av[1], "commit_contains")) { struct ref_filter filter; struct contains_cache cache; diff --git a/t/t6600-test-reach.sh b/t/t6600-test-reach.sh index d139a00d1d..ae94b27f70 100755 --- a/t/t6600-test-reach.sh +++ b/t/t6600-test-reach.sh @@ -31,7 +31,8 @@ test_expect_success 'setup' ' for i in $(test_seq 1 10) do test_commit "1-$i" && - git branch -f commit-1-$i + git branch -f commit-1-$i && + git tag -a -m "1-$i" tag-1-$i commit-1-$i done && for j in $(test_seq 1 9) do @@ -39,11 +40,13 @@ test_expect_success 'setup' ' x=$(($j + 1)) && test_commit "$x-1" && git branch -f commit-$x-1 && + git tag -a -m "$x-1" tag-$x-1 commit-$x-1 && for i in $(test_seq 2 10) do git merge commit-$j-$i -m "$x-$i" && - git branch -f commit-$x-$i + git branch -f commit-$x-$i && + git tag -a -m "$x-$i" tag-$x-$i commit-$x-$i done done && git commit-graph write --reachable && @@ -205,6 +208,29 @@ test_expect_success 'can_all_from_reach:miss' ' test_three_modes can_all_from_reach ' +test_expect_success 'can_all_from_reach_with_flag: tags case' ' + cat >input <<-\EOF && + X:tag-2-10 + X:tag-3-9 + X:tag-4-8 + X:commit-5-7 + X:commit-6-6 + X:commit-7-5 + X:commit-8-4 + X:commit-9-3 + Y:tag-1-9 + Y:tag-2-8 + Y:tag-3-7 + Y:commit-4-6 + Y:commit-5-5 + Y:commit-6-4 + Y:commit-7-3 + Y:commit-8-1 + EOF + echo "can_all_from_reach_with_flag(X,_,_,0,0):1" >expect && + test_three_modes can_all_from_reach_with_flag +' + test_expect_success 'commit_contains:hit' ' cat >input <<-\EOF && A:commit-7-7 -- gitgitgadget ^ permalink raw reply related [flat|nested] 25+ messages in thread
* Re: [PATCH v3 1/2] commit-reach: properly peel tags 2018-09-21 15:05 ` [PATCH v3 1/2] commit-reach: properly peel tags Derrick Stolee via GitGitGadget @ 2018-09-21 23:56 ` Jeff King 2018-09-24 11:48 ` Derrick Stolee 0 siblings, 1 reply; 25+ messages in thread From: Jeff King @ 2018-09-21 23:56 UTC (permalink / raw) To: Derrick Stolee via GitGitGadget; +Cc: git, Junio C Hamano, Derrick Stolee On Fri, Sep 21, 2018 at 08:05:26AM -0700, Derrick Stolee via GitGitGadget wrote: > diff --git a/commit-reach.c b/commit-reach.c > index 86715c103c..e748414d04 100644 > --- a/commit-reach.c > +++ b/commit-reach.c > @@ -544,20 +544,42 @@ int can_all_from_reach_with_flag(struct object_array *from, > { > struct commit **list = NULL; > int i; > + int nr_commits; > int result = 1; > > ALLOC_ARRAY(list, from->nr); > + nr_commits = 0; > for (i = 0; i < from->nr; i++) { > - list[i] = (struct commit *)from->objects[i].item; > + struct object *from_one = from->objects[i].item; > > - if (parse_commit(list[i]) || > - list[i]->generation < min_generation) > - return 0; > + if (!from_one || from_one->flags & assign_flag) > + continue; > + > + from_one = deref_tag(the_repository, from_one, > + "a from object", 0); > + if (!from_one || from_one->type != OBJ_COMMIT) { > + /* no way to tell if this is reachable by > + * looking at the ancestry chain alone, so > + * leave a note to ourselves not to worry about > + * this object anymore. > + */ A minor nit, but the original comment you restored here has a style violation. Might be worth fixing up (but certainly not worth a re-roll on its own). > + from->objects[i].item->flags |= assign_flag; OK, so here we mark the original tag with a flag... > + > + list[nr_commits] = (struct commit *)from_one; > + if (parse_commit(list[nr_commits]) || > + list[nr_commits]->generation < min_generation) { > + result = 0; > + goto cleanup; > + } And we jump to the cleanup here, but... > @@ -600,7 +622,7 @@ int can_all_from_reach_with_flag(struct object_array *from, > } > > cleanup: > - for (i = 0; i < from->nr; i++) { > + for (i = 0; i < nr_commits; i++) { > clear_commit_marks(list[i], RESULT); > clear_commit_marks(list[i], assign_flag); This walks over the items in the list array, which don't include the tag we marked. Did we decide that's OK? I think it's actually how the original code behaved, too, but it seems funny. At the least we might want to call it out in the commit message. Should we also be walking from->objects and clearing the flags from there (maybe not RESULT, but assign_flag)? It's not clear to me if it's unintentional for those to be marked after the function leaves or not. Also, a minor aside, but I think it would be slightly more efficient for those final two lines to do: clear_commit_marks(list[i], RESULT | assign_flag); Of course, that's totally orthogonal to this patch, but it may make you feel better to offset the other round of clearing I'm suggesting. ;) > diff --git a/t/helper/test-reach.c b/t/helper/test-reach.c > index eb21103998..08d2ea68e8 100644 > --- a/t/helper/test-reach.c > +++ b/t/helper/test-reach.c These bits all looked good to me. -Peff ^ permalink raw reply [flat|nested] 25+ messages in thread
* Re: [PATCH v3 1/2] commit-reach: properly peel tags 2018-09-21 23:56 ` Jeff King @ 2018-09-24 11:48 ` Derrick Stolee 0 siblings, 0 replies; 25+ messages in thread From: Derrick Stolee @ 2018-09-24 11:48 UTC (permalink / raw) To: Jeff King, Derrick Stolee via GitGitGadget Cc: git, Junio C Hamano, Derrick Stolee On 9/21/2018 7:56 PM, Jeff King wrote: > On Fri, Sep 21, 2018 at 08:05:26AM -0700, Derrick Stolee via GitGitGadget wrote: > + if (!from_one || from_one->type != OBJ_COMMIT) { > + /* no way to tell if this is reachable by > + * looking at the ancestry chain alone, so > + * leave a note to ourselves not to worry about > + * this object anymore. > + */ > A minor nit, but the original comment you restored here has a style > violation. Might be worth fixing up (but certainly not worth a re-roll > on its own). > >> @@ -600,7 +622,7 @@ int can_all_from_reach_with_flag(struct object_array *from, >> } >> >> cleanup: >> - for (i = 0; i < from->nr; i++) { >> + for (i = 0; i < nr_commits; i++) { >> clear_commit_marks(list[i], RESULT); >> clear_commit_marks(list[i], assign_flag); > Also, a minor aside, but I think it would be slightly more efficient for > those final two lines to do: > > clear_commit_marks(list[i], RESULT | assign_flag); > > Of course, that's totally orthogonal to this patch, but it may make you > feel better to offset the other round of clearing I'm suggesting. ;) This is definitely a better thing to do, and I'll make the change in v4, along with the comment style cleanup above. Thanks, -Stolee ^ permalink raw reply [flat|nested] 25+ messages in thread
* [PATCH v3 2/2] commit-reach: fix memory and flag leaks 2018-09-21 15:05 ` [PATCH v3 0/2] Properly peel tags in can_all_from_reach_with_flags() Derrick Stolee via GitGitGadget 2018-09-21 15:05 ` [PATCH v3 1/2] commit-reach: properly peel tags Derrick Stolee via GitGitGadget @ 2018-09-21 15:05 ` Derrick Stolee via GitGitGadget 2018-09-21 23:58 ` Jeff King 2018-09-24 20:57 ` [PATCH v4 0/1] Properly peel tags in can_all_from_reach_with_flags() Derrick Stolee via GitGitGadget 2 siblings, 1 reply; 25+ messages in thread From: Derrick Stolee via GitGitGadget @ 2018-09-21 15:05 UTC (permalink / raw) To: git; +Cc: peff, Junio C Hamano, Derrick Stolee From: Derrick Stolee <dstolee@microsoft.com> The can_all_from_reach_with_flag() method uses 'assign_flag' as a value we can use to mark objects temporarily during our commit walk. The intent is that these flags are removed from all objects before returning. However, this is not the case. The 'from' array could also contain objects that are not commits, and we mark those objects with 'assign_flag'. Add a loop to the 'cleanup' section that removes these markers. Also, we forgot to free() the memory for 'list', so add that to the 'cleanup' section. Signed-off-by: Derrick Stolee <dstolee@microsoft.com> --- commit-reach.c | 5 +++++ 1 file changed, 5 insertions(+) diff --git a/commit-reach.c b/commit-reach.c index e748414d04..5a845440a9 100644 --- a/commit-reach.c +++ b/commit-reach.c @@ -626,6 +626,11 @@ cleanup: clear_commit_marks(list[i], RESULT); clear_commit_marks(list[i], assign_flag); } + free(list); + + for (i = 0; i < from->nr; i++) + from->objects[i].item->flags &= ~assign_flag; + return result; } -- gitgitgadget ^ permalink raw reply related [flat|nested] 25+ messages in thread
* Re: [PATCH v3 2/2] commit-reach: fix memory and flag leaks 2018-09-21 15:05 ` [PATCH v3 2/2] commit-reach: fix memory and flag leaks Derrick Stolee via GitGitGadget @ 2018-09-21 23:58 ` Jeff King 2018-09-24 17:25 ` Derrick Stolee 0 siblings, 1 reply; 25+ messages in thread From: Jeff King @ 2018-09-21 23:58 UTC (permalink / raw) To: Derrick Stolee via GitGitGadget; +Cc: git, Junio C Hamano, Derrick Stolee On Fri, Sep 21, 2018 at 08:05:27AM -0700, Derrick Stolee via GitGitGadget wrote: > From: Derrick Stolee <dstolee@microsoft.com> > > The can_all_from_reach_with_flag() method uses 'assign_flag' as a > value we can use to mark objects temporarily during our commit walk. > The intent is that these flags are removed from all objects before > returning. However, this is not the case. > > The 'from' array could also contain objects that are not commits, and > we mark those objects with 'assign_flag'. Add a loop to the 'cleanup' > section that removes these markers. > > Also, we forgot to free() the memory for 'list', so add that to the > 'cleanup' section. Urgh, ignore most of my response to patch 1, then. I saw there was a patch 2, but thought it was just handling the free(). The flag-clearing here makes perfect sense. -Peff ^ permalink raw reply [flat|nested] 25+ messages in thread
* Re: [PATCH v3 2/2] commit-reach: fix memory and flag leaks 2018-09-21 23:58 ` Jeff King @ 2018-09-24 17:25 ` Derrick Stolee 2018-09-24 19:06 ` Jeff King 0 siblings, 1 reply; 25+ messages in thread From: Derrick Stolee @ 2018-09-24 17:25 UTC (permalink / raw) To: Jeff King, Derrick Stolee via GitGitGadget Cc: git, Junio C Hamano, Derrick Stolee On 9/21/2018 7:58 PM, Jeff King wrote: > On Fri, Sep 21, 2018 at 08:05:27AM -0700, Derrick Stolee via GitGitGadget wrote: > >> From: Derrick Stolee <dstolee@microsoft.com> >> >> The can_all_from_reach_with_flag() method uses 'assign_flag' as a >> value we can use to mark objects temporarily during our commit walk. >> The intent is that these flags are removed from all objects before >> returning. However, this is not the case. >> >> The 'from' array could also contain objects that are not commits, and >> we mark those objects with 'assign_flag'. Add a loop to the 'cleanup' >> section that removes these markers. >> >> Also, we forgot to free() the memory for 'list', so add that to the >> 'cleanup' section. > Urgh, ignore most of my response to patch 1, then. I saw there was a > patch 2, but thought it was just handling the free(). > > The flag-clearing here makes perfect sense. In my local branch, I ended up squashing this commit into the previous, because I discovered clear_commit_marks_many() making the cleanup section have this diff: @@ -600,10 +622,12 @@ int can_all_from_reach_with_flag(struct object_array *from, } cleanup: - for (i = 0; i < from->nr; i++) { - clear_commit_marks(list[i], RESULT); - clear_commit_marks(list[i], assign_flag); - } + clear_commit_marks_many(nr_commits, list, RESULT | assign_flag); + free(list); + + for (i = 0; i < from->nr; i++) + from->objects[i].item->flags &= ~assign_flag; + return result; } With the bigger change in the larger set, there is less reason to do separate commits. (Plus, it confused you during review.) Thanks, -Stolee ^ permalink raw reply [flat|nested] 25+ messages in thread
* Re: [PATCH v3 2/2] commit-reach: fix memory and flag leaks 2018-09-24 17:25 ` Derrick Stolee @ 2018-09-24 19:06 ` Jeff King 0 siblings, 0 replies; 25+ messages in thread From: Jeff King @ 2018-09-24 19:06 UTC (permalink / raw) To: Derrick Stolee Cc: Derrick Stolee via GitGitGadget, git, Junio C Hamano, Derrick Stolee On Mon, Sep 24, 2018 at 01:25:12PM -0400, Derrick Stolee wrote: > On 9/21/2018 7:58 PM, Jeff King wrote: > > On Fri, Sep 21, 2018 at 08:05:27AM -0700, Derrick Stolee via GitGitGadget wrote: > > > > > From: Derrick Stolee <dstolee@microsoft.com> > > > > > > The can_all_from_reach_with_flag() method uses 'assign_flag' as a > > > value we can use to mark objects temporarily during our commit walk. > > > The intent is that these flags are removed from all objects before > > > returning. However, this is not the case. > > > > > > The 'from' array could also contain objects that are not commits, and > > > we mark those objects with 'assign_flag'. Add a loop to the 'cleanup' > > > section that removes these markers. > > > > > > Also, we forgot to free() the memory for 'list', so add that to the > > > 'cleanup' section. > > Urgh, ignore most of my response to patch 1, then. I saw there was a > > patch 2, but thought it was just handling the free(). > > > > The flag-clearing here makes perfect sense. > > In my local branch, I ended up squashing this commit into the previous, > because I discovered clear_commit_marks_many() making the cleanup section > have this diff: > > @@ -600,10 +622,12 @@ int can_all_from_reach_with_flag(struct object_array > *from, > } > > cleanup: > - for (i = 0; i < from->nr; i++) { > - clear_commit_marks(list[i], RESULT); > - clear_commit_marks(list[i], assign_flag); > - } > + clear_commit_marks_many(nr_commits, list, RESULT | assign_flag); > + free(list); > + > + for (i = 0; i < from->nr; i++) > + from->objects[i].item->flags &= ~assign_flag; > + > return result; > } > > With the bigger change in the larger set, there is less reason to do > separate commits. (Plus, it confused you during review.) Yeah, that looks better still. Thanks! -Peff ^ permalink raw reply [flat|nested] 25+ messages in thread
* [PATCH v4 0/1] Properly peel tags in can_all_from_reach_with_flags() 2018-09-21 15:05 ` [PATCH v3 0/2] Properly peel tags in can_all_from_reach_with_flags() Derrick Stolee via GitGitGadget 2018-09-21 15:05 ` [PATCH v3 1/2] commit-reach: properly peel tags Derrick Stolee via GitGitGadget 2018-09-21 15:05 ` [PATCH v3 2/2] commit-reach: fix memory and flag leaks Derrick Stolee via GitGitGadget @ 2018-09-24 20:57 ` Derrick Stolee via GitGitGadget 2018-09-24 20:57 ` [PATCH v4 1/1] commit-reach: properly peel tags and clear flags Derrick Stolee via GitGitGadget 2018-09-25 13:27 ` [PATCH] commit-reach: cleanups in can_all_from_reach Derrick Stolee 2 siblings, 2 replies; 25+ messages in thread From: Derrick Stolee via GitGitGadget @ 2018-09-24 20:57 UTC (permalink / raw) To: git; +Cc: peff, Junio C Hamano As Peff reported [1], the refactored can_all_from_reach_with_flags() method does not properly peel tags. Since the helper method can_all_from_reach() and code in t/helper/test-reach.c all peel tags before getting to this method, it is not super-simple to create a test that demonstrates this. I modified t/helper/test-reach.c to allow calling can_all_from_reach_with_flags() directly, and added a test in t6600-test-reach.sh that demonstrates the segfault without the fix. For V2, I compared the loop that inspects the 'from' commits in commit ba3ca1edce "commit-reach: move can_all_from_reach_with_flags" to the version here and got the following diff: 3c3 < if (from_one->flags & assign_flag) --- > if (!from_one || from_one->flags & assign_flag) 5c5,7 < from_one = deref_tag(the_repository, from_one, "a from object", 0); --- > > from_one = deref_tag(the_repository, from_one, > "a from object", 0); 14a17,22 > > list[nr_commits] = (struct commit *)from_one; > if (parse_commit(list[nr_commits]) || > list[nr_commits]->generation < min_generation) > return 0; /* is this a leak? */ > nr_commits++; This diff includes the early termination we had before 'deref_tag' and the comment for why we can ignore non-commit objects. [1] https://public-inbox.org/git/0bf9103c-9377-506b-7ad7-e5273d8e94fc@gmail.com/T/#u Derrick Stolee (1): commit-reach: properly peel tags and clear flags commit-reach.c | 44 +++++++++++++++++++++++++++++++++---------- t/helper/test-reach.c | 22 +++++++++++++++++----- t/t6600-test-reach.sh | 30 +++++++++++++++++++++++++++-- 3 files changed, 79 insertions(+), 17 deletions(-) base-commit: 6621c838743812aaba96e55cfec8524ea1144c2d Published-As: https://github.com/gitgitgadget/git/releases/tags/pr-39%2Fderrickstolee%2Ftag-fix-v4 Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-39/derrickstolee/tag-fix-v4 Pull-Request: https://github.com/gitgitgadget/git/pull/39 Range-diff vs v3: 1: 0a1e661271 ! 1: a0a3cf0134 commit-reach: properly peel tags @@ -1,6 +1,6 @@ Author: Derrick Stolee <dstolee@microsoft.com> - commit-reach: properly peel tags + commit-reach: properly peel tags and clear flags The can_all_from_reach_with_flag() algorithm was refactored in 4fbcca4e "commit-reach: make can_all_from_reach... linear" but incorrectly @@ -14,6 +14,19 @@ Correct the issue by peeling tags when investigating the initial list of objects in the 'from' array. + The can_all_from_reach_with_flag() method uses 'assign_flag' as a + value we can use to mark objects temporarily during our commit walk. + The intent is that these flags are removed from all objects before + returning. However, this is not the case. + + The 'from' array could also contain objects that are not commits, and + we mark those objects with 'assign_flag'. Add a loop to the 'cleanup' + section that removes these markers. + + Also, we forgot to free() the memory for 'list', so add that to the + 'cleanup' section. Also, use a cleaner mechanism for clearing those + flags. + Signed-off-by: Jeff King <peff@peff.net> Signed-off-by: Derrick Stolee <dstolee@microsoft.com> @@ -74,10 +87,18 @@ cleanup: - for (i = 0; i < from->nr; i++) { -+ for (i = 0; i < nr_commits; i++) { - clear_commit_marks(list[i], RESULT); - clear_commit_marks(list[i], assign_flag); - } +- clear_commit_marks(list[i], RESULT); +- clear_commit_marks(list[i], assign_flag); +- } ++ clear_commit_marks_many(nr_commits, list, RESULT | assign_flag); ++ free(list); ++ ++ for (i = 0; i < from->nr; i++) ++ from->objects[i].item->flags &= ~assign_flag; ++ + return result; + } + diff --git a/t/helper/test-reach.c b/t/helper/test-reach.c --- a/t/helper/test-reach.c 2: b2e0ee4978 < -: ---------- commit-reach: fix memory and flag leaks -- gitgitgadget ^ permalink raw reply [flat|nested] 25+ messages in thread
* [PATCH v4 1/1] commit-reach: properly peel tags and clear flags 2018-09-24 20:57 ` [PATCH v4 0/1] Properly peel tags in can_all_from_reach_with_flags() Derrick Stolee via GitGitGadget @ 2018-09-24 20:57 ` Derrick Stolee via GitGitGadget 2018-09-24 21:09 ` Jeff King 2018-09-25 5:17 ` Eric Sunshine 2018-09-25 13:27 ` [PATCH] commit-reach: cleanups in can_all_from_reach Derrick Stolee 1 sibling, 2 replies; 25+ messages in thread From: Derrick Stolee via GitGitGadget @ 2018-09-24 20:57 UTC (permalink / raw) To: git; +Cc: peff, Junio C Hamano, Derrick Stolee From: Derrick Stolee <dstolee@microsoft.com> The can_all_from_reach_with_flag() algorithm was refactored in 4fbcca4e "commit-reach: make can_all_from_reach... linear" but incorrectly assumed that all objects provided were commits. During a fetch negotiation, ok_to_give_up() in upload-pack.c may provide unpeeled tags to the 'from' array. The current code creates a segfault. Add a direct call to can_all_from_reach_with_flag() in 'test-tool reach' and add a test in t6600-test-reach.sh that demonstrates this segfault. Correct the issue by peeling tags when investigating the initial list of objects in the 'from' array. The can_all_from_reach_with_flag() method uses 'assign_flag' as a value we can use to mark objects temporarily during our commit walk. The intent is that these flags are removed from all objects before returning. However, this is not the case. The 'from' array could also contain objects that are not commits, and we mark those objects with 'assign_flag'. Add a loop to the 'cleanup' section that removes these markers. Also, we forgot to free() the memory for 'list', so add that to the 'cleanup' section. Also, use a cleaner mechanism for clearing those flags. Signed-off-by: Jeff King <peff@peff.net> Signed-off-by: Derrick Stolee <dstolee@microsoft.com> --- commit-reach.c | 44 +++++++++++++++++++++++++++++++++---------- t/helper/test-reach.c | 22 +++++++++++++++++----- t/t6600-test-reach.sh | 30 +++++++++++++++++++++++++++-- 3 files changed, 79 insertions(+), 17 deletions(-) diff --git a/commit-reach.c b/commit-reach.c index 86715c103c..db84f85986 100644 --- a/commit-reach.c +++ b/commit-reach.c @@ -544,20 +544,42 @@ int can_all_from_reach_with_flag(struct object_array *from, { struct commit **list = NULL; int i; + int nr_commits; int result = 1; ALLOC_ARRAY(list, from->nr); + nr_commits = 0; for (i = 0; i < from->nr; i++) { - list[i] = (struct commit *)from->objects[i].item; + struct object *from_one = from->objects[i].item; - if (parse_commit(list[i]) || - list[i]->generation < min_generation) - return 0; + if (!from_one || from_one->flags & assign_flag) + continue; + + from_one = deref_tag(the_repository, from_one, + "a from object", 0); + if (!from_one || from_one->type != OBJ_COMMIT) { + /* no way to tell if this is reachable by + * looking at the ancestry chain alone, so + * leave a note to ourselves not to worry about + * this object anymore. + */ + from->objects[i].item->flags |= assign_flag; + continue; + } + + list[nr_commits] = (struct commit *)from_one; + if (parse_commit(list[nr_commits]) || + list[nr_commits]->generation < min_generation) { + result = 0; + goto cleanup; + } + + nr_commits++; } - QSORT(list, from->nr, compare_commits_by_gen); + QSORT(list, nr_commits, compare_commits_by_gen); - for (i = 0; i < from->nr; i++) { + for (i = 0; i < nr_commits; i++) { /* DFS from list[i] */ struct commit_list *stack = NULL; @@ -600,10 +622,12 @@ int can_all_from_reach_with_flag(struct object_array *from, } cleanup: - for (i = 0; i < from->nr; i++) { - clear_commit_marks(list[i], RESULT); - clear_commit_marks(list[i], assign_flag); - } + clear_commit_marks_many(nr_commits, list, RESULT | assign_flag); + free(list); + + for (i = 0; i < from->nr; i++) + from->objects[i].item->flags &= ~assign_flag; + return result; } diff --git a/t/helper/test-reach.c b/t/helper/test-reach.c index eb21103998..08d2ea68e8 100644 --- a/t/helper/test-reach.c +++ b/t/helper/test-reach.c @@ -31,6 +31,7 @@ int cmd__reach(int ac, const char **av) struct object_id oid_A, oid_B; struct commit *A, *B; struct commit_list *X, *Y; + struct object_array X_obj = OBJECT_ARRAY_INIT; struct commit **X_array; int X_nr, X_alloc; struct strbuf buf = STRBUF_INIT; @@ -49,7 +50,8 @@ int cmd__reach(int ac, const char **av) while (strbuf_getline(&buf, stdin) != EOF) { struct object_id oid; - struct object *o; + struct object *orig; + struct object *peeled; struct commit *c; if (buf.len < 3) continue; @@ -57,14 +59,14 @@ int cmd__reach(int ac, const char **av) if (get_oid_committish(buf.buf + 2, &oid)) die("failed to resolve %s", buf.buf + 2); - o = parse_object(r, &oid); - o = deref_tag_noverify(o); + orig = parse_object(r, &oid); + peeled = deref_tag_noverify(orig); - if (!o) + if (!peeled) die("failed to load commit for input %s resulting in oid %s\n", buf.buf, oid_to_hex(&oid)); - c = object_as_type(r, o, OBJ_COMMIT, 0); + c = object_as_type(r, peeled, OBJ_COMMIT, 0); if (!c) die("failed to load commit for input %s resulting in oid %s\n", @@ -85,6 +87,7 @@ int cmd__reach(int ac, const char **av) commit_list_insert(c, &X); ALLOC_GROW(X_array, X_nr + 1, X_alloc); X_array[X_nr++] = c; + add_object_array(orig, NULL, &X_obj); break; case 'Y': @@ -113,6 +116,15 @@ int cmd__reach(int ac, const char **av) print_sorted_commit_ids(list); } else if (!strcmp(av[1], "can_all_from_reach")) { printf("%s(X,Y):%d\n", av[1], can_all_from_reach(X, Y, 1)); + } else if (!strcmp(av[1], "can_all_from_reach_with_flag")) { + struct commit_list *iter = Y; + + while (iter) { + iter->item->object.flags |= 2; + iter = iter->next; + } + + printf("%s(X,_,_,0,0):%d\n", av[1], can_all_from_reach_with_flag(&X_obj, 2, 4, 0, 0)); } else if (!strcmp(av[1], "commit_contains")) { struct ref_filter filter; struct contains_cache cache; diff --git a/t/t6600-test-reach.sh b/t/t6600-test-reach.sh index d139a00d1d..ae94b27f70 100755 --- a/t/t6600-test-reach.sh +++ b/t/t6600-test-reach.sh @@ -31,7 +31,8 @@ test_expect_success 'setup' ' for i in $(test_seq 1 10) do test_commit "1-$i" && - git branch -f commit-1-$i + git branch -f commit-1-$i && + git tag -a -m "1-$i" tag-1-$i commit-1-$i done && for j in $(test_seq 1 9) do @@ -39,11 +40,13 @@ test_expect_success 'setup' ' x=$(($j + 1)) && test_commit "$x-1" && git branch -f commit-$x-1 && + git tag -a -m "$x-1" tag-$x-1 commit-$x-1 && for i in $(test_seq 2 10) do git merge commit-$j-$i -m "$x-$i" && - git branch -f commit-$x-$i + git branch -f commit-$x-$i && + git tag -a -m "$x-$i" tag-$x-$i commit-$x-$i done done && git commit-graph write --reachable && @@ -205,6 +208,29 @@ test_expect_success 'can_all_from_reach:miss' ' test_three_modes can_all_from_reach ' +test_expect_success 'can_all_from_reach_with_flag: tags case' ' + cat >input <<-\EOF && + X:tag-2-10 + X:tag-3-9 + X:tag-4-8 + X:commit-5-7 + X:commit-6-6 + X:commit-7-5 + X:commit-8-4 + X:commit-9-3 + Y:tag-1-9 + Y:tag-2-8 + Y:tag-3-7 + Y:commit-4-6 + Y:commit-5-5 + Y:commit-6-4 + Y:commit-7-3 + Y:commit-8-1 + EOF + echo "can_all_from_reach_with_flag(X,_,_,0,0):1" >expect && + test_three_modes can_all_from_reach_with_flag +' + test_expect_success 'commit_contains:hit' ' cat >input <<-\EOF && A:commit-7-7 -- gitgitgadget ^ permalink raw reply related [flat|nested] 25+ messages in thread
* Re: [PATCH v4 1/1] commit-reach: properly peel tags and clear flags 2018-09-24 20:57 ` [PATCH v4 1/1] commit-reach: properly peel tags and clear flags Derrick Stolee via GitGitGadget @ 2018-09-24 21:09 ` Jeff King 2018-09-25 5:17 ` Eric Sunshine 1 sibling, 0 replies; 25+ messages in thread From: Jeff King @ 2018-09-24 21:09 UTC (permalink / raw) To: Derrick Stolee via GitGitGadget; +Cc: git, Junio C Hamano, Derrick Stolee On Mon, Sep 24, 2018 at 01:57:52PM -0700, Derrick Stolee via GitGitGadget wrote: > From: Derrick Stolee <dstolee@microsoft.com> > > The can_all_from_reach_with_flag() algorithm was refactored in 4fbcca4e > "commit-reach: make can_all_from_reach... linear" but incorrectly > assumed that all objects provided were commits. During a fetch > negotiation, ok_to_give_up() in upload-pack.c may provide unpeeled tags > to the 'from' array. The current code creates a segfault. > [...] Thanks, this version looks good to me. -Peff ^ permalink raw reply [flat|nested] 25+ messages in thread
* Re: [PATCH v4 1/1] commit-reach: properly peel tags and clear flags 2018-09-24 20:57 ` [PATCH v4 1/1] commit-reach: properly peel tags and clear flags Derrick Stolee via GitGitGadget 2018-09-24 21:09 ` Jeff King @ 2018-09-25 5:17 ` Eric Sunshine 1 sibling, 0 replies; 25+ messages in thread From: Eric Sunshine @ 2018-09-25 5:17 UTC (permalink / raw) To: gitgitgadget; +Cc: Git List, Jeff King, Junio C Hamano, Derrick Stolee On Mon, Sep 24, 2018 at 4:58 PM Derrick Stolee via GitGitGadget <gitgitgadget@gmail.com> wrote: > diff --git a/commit-reach.c b/commit-reach.c > @@ -544,20 +544,42 @@ int can_all_from_reach_with_flag(struct object_array *from, > { > + from_one = deref_tag(the_repository, from_one, > + "a from object", 0); > + if (!from_one || from_one->type != OBJ_COMMIT) { > + /* no way to tell if this is reachable by > + * looking at the ancestry chain alone, so > + * leave a note to ourselves not to worry about > + * this object anymore. > + */ Style nit: /* * Multi-line comment * formatting. */ ^ permalink raw reply [flat|nested] 25+ messages in thread
* [PATCH] commit-reach: cleanups in can_all_from_reach... 2018-09-24 20:57 ` [PATCH v4 0/1] Properly peel tags in can_all_from_reach_with_flags() Derrick Stolee via GitGitGadget 2018-09-24 20:57 ` [PATCH v4 1/1] commit-reach: properly peel tags and clear flags Derrick Stolee via GitGitGadget @ 2018-09-25 13:27 ` Derrick Stolee 2018-09-25 18:06 ` Junio C Hamano 1 sibling, 1 reply; 25+ messages in thread From: Derrick Stolee @ 2018-09-25 13:27 UTC (permalink / raw) To: git; +Cc: peff, Derrick Stolee From: Derrick Stolee <dstolee@microsoft.com> Due to a regression introduced by 4fbcca4e "commit-reach: make can_all_from_reach... linear" the series including b67f6b26 "commit-reach: properly peel tags" was merged to master quickly. There were a few more cleanups left to apply in the series, which are included by this change: 1. Clean up a comment that is in the incorrect style. 2. Replace multiple calls to clear_commit_marks() with one call to clear_commit_marks_many(). Signed-off-by: Derrick Stolee <dstolee@microsoft.com> --- commit-reach.c | 8 +++----- 1 file changed, 3 insertions(+), 5 deletions(-) diff --git a/commit-reach.c b/commit-reach.c index 5a845440a9..66aa41262c 100644 --- a/commit-reach.c +++ b/commit-reach.c @@ -558,7 +558,8 @@ int can_all_from_reach_with_flag(struct object_array *from, from_one = deref_tag(the_repository, from_one, "a from object", 0); if (!from_one || from_one->type != OBJ_COMMIT) { - /* no way to tell if this is reachable by + /* + * no way to tell if this is reachable by * looking at the ancestry chain alone, so * leave a note to ourselves not to worry about * this object anymore. @@ -622,10 +623,7 @@ int can_all_from_reach_with_flag(struct object_array *from, } cleanup: - for (i = 0; i < nr_commits; i++) { - clear_commit_marks(list[i], RESULT); - clear_commit_marks(list[i], assign_flag); - } + clear_commit_marks_many(nr_commits, list, RESULT | assign_flag); free(list); for (i = 0; i < from->nr; i++) base-commit: 4067a64672f9db8ca38d5a2682a7cdba7938c18b -- 2.19.0 ^ permalink raw reply related [flat|nested] 25+ messages in thread
* Re: [PATCH] commit-reach: cleanups in can_all_from_reach... 2018-09-25 13:27 ` [PATCH] commit-reach: cleanups in can_all_from_reach Derrick Stolee @ 2018-09-25 18:06 ` Junio C Hamano 2018-09-25 18:13 ` Derrick Stolee 0 siblings, 1 reply; 25+ messages in thread From: Junio C Hamano @ 2018-09-25 18:06 UTC (permalink / raw) To: Derrick Stolee; +Cc: git, peff, Derrick Stolee Derrick Stolee <stolee@gmail.com> writes: > @@ -622,10 +623,7 @@ int can_all_from_reach_with_flag(struct object_array *from, > } > > cleanup: > - for (i = 0; i < nr_commits; i++) { > - clear_commit_marks(list[i], RESULT); > - clear_commit_marks(list[i], assign_flag); > - } > + clear_commit_marks_many(nr_commits, list, RESULT | assign_flag); > free(list); > > for (i = 0; i < from->nr; i++) > > base-commit: 4067a64672f9db8ca38d5a2682a7cdba7938c18b This change looks good to me. This is a tangent, but while re-reading clear_commit_marks() and its helpers to refresh my memory, I found that the bottom-most helper in the callchain was written in a very confusing way, but it is not a fault of this clean-up. I however suspect that it would not help us all that much to use clear_commit_marks_many() with its current implementation. It first clears all commits on the first-parent chain from each list[] element, while accumulating the parent commits that are yet to be processed in a commit_list in LIFO order, and then consumes these accumulated side parents the same way. We probably would benefit by rewriting clear_commit_marks_many() to traverse from all the tips given in list[] taking advantage of the generation numbers, using a prio queue to manage the commits yet-to-be-cleared, or something. ^ permalink raw reply [flat|nested] 25+ messages in thread
* Re: [PATCH] commit-reach: cleanups in can_all_from_reach... 2018-09-25 18:06 ` Junio C Hamano @ 2018-09-25 18:13 ` Derrick Stolee 2018-09-25 20:29 ` Junio C Hamano 0 siblings, 1 reply; 25+ messages in thread From: Derrick Stolee @ 2018-09-25 18:13 UTC (permalink / raw) To: Junio C Hamano; +Cc: git, peff, Derrick Stolee On 9/25/2018 2:06 PM, Junio C Hamano wrote: > Derrick Stolee <stolee@gmail.com> writes: > >> @@ -622,10 +623,7 @@ int can_all_from_reach_with_flag(struct object_array *from, >> } >> >> cleanup: >> - for (i = 0; i < nr_commits; i++) { >> - clear_commit_marks(list[i], RESULT); >> - clear_commit_marks(list[i], assign_flag); >> - } >> + clear_commit_marks_many(nr_commits, list, RESULT | assign_flag); >> free(list); >> >> for (i = 0; i < from->nr; i++) >> >> base-commit: 4067a64672f9db8ca38d5a2682a7cdba7938c18b > This change looks good to me. > > This is a tangent, but while re-reading clear_commit_marks() and its > helpers to refresh my memory, I found that the bottom-most helper in > the callchain was written in a very confusing way, but it is not a > fault of this clean-up. I however suspect that it would not help us > all that much to use clear_commit_marks_many() with its current > implementation. It first clears all commits on the first-parent > chain from each list[] element, while accumulating the parent > commits that are yet to be processed in a commit_list in LIFO order, > and then consumes these accumulated side parents the same way. We > probably would benefit by rewriting clear_commit_marks_many() to > traverse from all the tips given in list[] taking advantage of the > generation numbers, using a prio queue to manage the commits > yet-to-be-cleared, or something. Another commit walk that could be improved by generation numbers? It's like my bat-signal! Thanks for pointing me in that direction. I'll take a look. -Stolee ^ permalink raw reply [flat|nested] 25+ messages in thread
* Re: [PATCH] commit-reach: cleanups in can_all_from_reach... 2018-09-25 18:13 ` Derrick Stolee @ 2018-09-25 20:29 ` Junio C Hamano 0 siblings, 0 replies; 25+ messages in thread From: Junio C Hamano @ 2018-09-25 20:29 UTC (permalink / raw) To: Derrick Stolee; +Cc: git, peff, Derrick Stolee Derrick Stolee <stolee@gmail.com> writes: > Another commit walk that could be improved by generation numbers? It's > like my bat-signal! Ah, nevermind. The "traversal" done by these helper functions is the most stupid kind (not the algorthim, but the need). It's not like there is an opportunity to optimize by not traversing the remainder if we choose the order of traversal intelligently, so any algorithm that does not visit the same node twice and does not do the most naive recursion would work, and what we currently have there is just fine. ^ permalink raw reply [flat|nested] 25+ messages in thread
end of thread, other threads:[~2018-09-25 20:29 UTC | newest] Thread overview: 25+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2018-09-12 14:22 [PATCH 0/1] Properly peel tags in can_all_from_reach_with_flags() Derrick Stolee via GitGitGadget 2018-09-12 14:22 ` [PATCH 1/1] commit-reach: properly peel tags Derrick Stolee via GitGitGadget 2018-09-12 19:41 ` Jeff King 2018-09-12 21:23 ` Junio C Hamano 2018-09-12 21:34 ` Jeff King 2018-09-13 16:10 ` [PATCH v2 0/1] Properly peel tags in can_all_from_reach_with_flags() Derrick Stolee via GitGitGadget 2018-09-13 16:10 ` [PATCH v2 1/1] commit-reach: properly peel tags Derrick Stolee via GitGitGadget 2018-09-13 16:38 ` Derrick Stolee 2018-09-13 21:06 ` Junio C Hamano 2018-09-21 15:05 ` [PATCH v3 0/2] Properly peel tags in can_all_from_reach_with_flags() Derrick Stolee via GitGitGadget 2018-09-21 15:05 ` [PATCH v3 1/2] commit-reach: properly peel tags Derrick Stolee via GitGitGadget 2018-09-21 23:56 ` Jeff King 2018-09-24 11:48 ` Derrick Stolee 2018-09-21 15:05 ` [PATCH v3 2/2] commit-reach: fix memory and flag leaks Derrick Stolee via GitGitGadget 2018-09-21 23:58 ` Jeff King 2018-09-24 17:25 ` Derrick Stolee 2018-09-24 19:06 ` Jeff King 2018-09-24 20:57 ` [PATCH v4 0/1] Properly peel tags in can_all_from_reach_with_flags() Derrick Stolee via GitGitGadget 2018-09-24 20:57 ` [PATCH v4 1/1] commit-reach: properly peel tags and clear flags Derrick Stolee via GitGitGadget 2018-09-24 21:09 ` Jeff King 2018-09-25 5:17 ` Eric Sunshine 2018-09-25 13:27 ` [PATCH] commit-reach: cleanups in can_all_from_reach Derrick Stolee 2018-09-25 18:06 ` Junio C Hamano 2018-09-25 18:13 ` Derrick Stolee 2018-09-25 20:29 ` Junio C Hamano
Code repositories for project(s) associated with this public inbox https://80x24.org/mirrors/git.git This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).