{"thread":{"id":"59640","subject":"[PATCH v1] negotiator/default.c: avoid stack overflow","startedAt":"2023-04-24T02:23:59Z","lastAt":"2023-05-02T15:51:27Z","messageCount":20,"participants":["Han Xin","Derrick Stolee","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"475906","messageId":"20230424022318.80469-1-hanxin.hx@bytedance.com","threadId":"59640","inReplyTo":null,"subject":"[PATCH v1] negotiator/default.c: avoid stack overflow","fromName":"Han Xin","fromEmail":"hanxin.hx@bytedance.com","sentAt":"2023-04-24T02:23:18Z","receivedAt":"2023-04-24T02:23:59Z","isPatch":true,"sender":{"key":"hanxin.hx@bytedance.com","avatar":"https://avatars.githubusercontent.com/u/16610542?v=4"},"body":"mark_common() in negotiator/default.c may overflow the stack due to\nrecursive function calls. Avoid this by instead recursing using a\nheap-allocated data structure.\n\nThis is the same case as [1].\n\n1. https://lore.kernel.org/git/20221025232934.1504445-1-jonathantanmy@google.com/\n\nReported-by: Xin Xing <xingxin.xx@bytedance.com>\nSigned-off-by: Han Xin <hanxin.hx@bytedance.com>\n---\n negotiator/default.c  | 16 ++++++++++++----\n negotiator/skipping.c |  2 ++\n 2 files changed, 14 insertions(+), 4 deletions(-)\n\ndiff --git a/negotiator/default.c b/negotiator/default.c\nindex f4b78eb47d..6ab7f11409 100644\n--- a/negotiator/default.c\n+++ b/negotiator/default.c\n@@ -55,9 +55,15 @@ static int clear_marks(const char *refname, const struct object_id *oid,\n static void mark_common(struct negotiation_state *ns, struct commit *commit,\n \t\tint ancestors_only, int dont_parse)\n {\n-\tif (commit != NULL && !(commit->object.flags & COMMON)) {\n+\tstruct prio_queue queue = { NULL };\n+\n+\tprio_queue_put(&queue, commit);\n+\twhile ((commit = prio_queue_get(&queue))) {\n \t\tstruct object *o = (struct object *)commit;\n \n+\t\tif (commit == NULL || (commit->object.flags & COMMON))\n+\t\t\tcontinue;\n+\n \t\tif (!ancestors_only)\n \t\t\to->flags |= COMMON;\n \n@@ -70,15 +76,17 @@ static void mark_common(struct negotiation_state *ns, struct commit *commit,\n \t\t\t\tns->non_common_revs--;\n \t\t\tif (!o->parsed && !dont_parse)\n \t\t\t\tif (repo_parse_commit(the_repository, commit))\n-\t\t\t\t\treturn;\n+\t\t\t\t\tcontinue;\n \n+\t\t\tancestors_only = 0;\n \t\t\tfor (parents = commit->parents;\n \t\t\t\t\tparents;\n \t\t\t\t\tparents = parents->next)\n-\t\t\t\tmark_common(ns, parents->item, 0,\n-\t\t\t\t\t    dont_parse);\n+\t\t\t\tprio_queue_put(&queue, parents->item);\n \t\t}\n \t}\n+\n+\tclear_prio_queue(&queue);\n }\n \n /*\ndiff --git a/negotiator/skipping.c b/negotiator/skipping.c\nindex c7d6ab39bc..3d262b3533 100644\n--- a/negotiator/skipping.c\n+++ b/negotiator/skipping.c\n@@ -108,6 +108,8 @@ static void mark_common(struct data *data, struct commit *seen_commit)\n \t\t\t\tprio_queue_put(&queue, p->item);\n \t\t}\n \t}\n+\n+\tclear_prio_queue(&queue);\n }\n \n /*\n-- \n2.40.0\n\n"},{"id":"475918","messageId":"2bcaeba9-20bc-1ca8-849b-ac54342c71e3@github.com","threadId":"59640","inReplyTo":"20230424022318.80469-1-hanxin.hx@bytedance.com","subject":"Re: [PATCH v1] negotiator/default.c: avoid stack overflow","fromName":"Derrick Stolee","fromEmail":"derrickstolee@github.com","sentAt":"2023-04-24T14:44:38Z","receivedAt":"2023-04-24T14:44:51Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 4/23/2023 10:23 PM, Han Xin wrote:\n> mark_common() in negotiator/default.c may overflow the stack due to\n> recursive function calls. Avoid this by instead recursing using a\n> heap-allocated data structure.\n\nI'm really happy to see that since you could replace the if statement\nwith a while statement, most of the existing logic could stay without\na bunch of whitespace changes.\n \n> This is the same case as [1].\n> \n> 1. https://lore.kernel.org/git/20221025232934.1504445-1-jonathantanmy@google.com/\n\nThanks for the link, though this could be replaced with\n\n  4654134976f (negotiator/skipping: avoid stack overflow, 2022-10-25)\n\nnow that the change exists in the commit history.\n\nOne thing that is missing from that change is a test, and such a test\ncould be generalized to apply to all negotiators. This could maybe\nhelp any potential future negotiator avoid this bug. Did you think\nabout what such a test could look like? Perhaps test_commit_bulk\ncould help, but we'd probably need to create so many commits that the\ntest would need to be marked as expensive. That's probably a major\nreason to not include a test and rely on avoiding recursion when\npossible.\n\n> -\tif (commit != NULL && !(commit->object.flags & COMMON)) {\n> +\tstruct prio_queue queue = { NULL };\n> +\n> +\tprio_queue_put(&queue, commit);\n\nShould we check the conditions what were removed? The COMMON flag\nis likely only useful for the recursion, but prio_queue_put() is\nnot careful about NULL values. However, no callers should be\nproviding NULL commits here.\n\nCouldn't hurt to add\n\t\n\tif (!commit)\n\t\treturn;\n\nbefore the prio_queue_put().\n\n> +\twhile ((commit = prio_queue_get(&queue))) {\n>  \t\tstruct object *o = (struct object *)commit;\n>  \n> +\t\tif (commit == NULL || (commit->object.flags & COMMON))\n> +\t\t\tcontinue;\n\nThe NULL condition is definitely unnecessary here as it is checked\nby the while condition. The \"& COMMON\" is helpful if the commit\ngained the COMMON flag after being inserted into the queue.\n\n>  \t\tif (!ancestors_only)\n>  \t\t\to->flags |= COMMON;\n>  \n\n\n> @@ -70,15 +76,17 @@ static void mark_common(struct negotiation_state *ns, struct commit *commit,\n>  \t\t\t\tns->non_common_revs--;\n>  \t\t\tif (!o->parsed && !dont_parse)\n>  \t\t\t\tif (repo_parse_commit(the_repository, commit))\n> -\t\t\t\t\treturn;\n> +\t\t\t\t\tcontinue;\n>  \n> +\t\t\tancestors_only = 0;\n\nThis caught me off guard, but this flag essentially says \"should\nI mark the first commit as common or not?\". It would probably be\nclearer if this was done before the loop, and then was ignored\nwithin the loop, setting the flag on each parent in this loop:\n\n>  \t\t\tfor (parents = commit->parents;\n>  \t\t\t\t\tparents;\n>  \t\t\t\t\tparents = parents->next)\n> -\t\t\t\tmark_common(ns, parents->item, 0,\n> -\t\t\t\t\t    dont_parse);\n> +\t\t\t\tprio_queue_put(&queue, parents->item);\n\nIt would have an extra benefit: your walk may duplicate objects in the\npriority queue (there is no duplicate protection in prio_queue_put).\nBut, we could use\n\n\tif (!(parents->item->object.flags & COMMON)) {\n\t\tparents->item->object.flags |= COMMON;\n\t\tprio_queue_put(&queue, parents->item);\n\t}\n\nas duplicate protection _and_ a clearer way to demonstrate what\nancestors_only is doing. Without this protection, it is possible\nto have exponential growth in the priority queue using simple\nmerge commits.\n\nYou'd need this at the beginning:\n\n\tif (!commit)\n\t\treturn;\n\n\tprio_queue_put(&queue, commit);\n\tif (!ancestors_only)\n\t\tcommit->object.flags |= COMMON;\n> diff --git a/negotiator/skipping.c b/negotiator/skipping.c\n> index c7d6ab39bc..3d262b3533 100644\n> --- a/negotiator/skipping.c\n> +++ b/negotiator/skipping.c\n> @@ -108,6 +108,8 @@ static void mark_common(struct data *data, struct commit *seen_commit)\n>  \t\t\t\tprio_queue_put(&queue, p->item);\n>  \t\t}\n>  \t}\n> +\n> +\tclear_prio_queue(&queue);\n\nThis memory leak cleanup in the skipping negotiator is good to\ndo, but should be split into its own change.\n\nIn addition, the mark_common() method there seems to have a few\nproblems:\n\n 1. It does not do duplicate protection before prio_queue_put().\n    (The COMMON bit would work here, too.)\n 2. When it translated from recursive to iterative it kept \"return\"\n    statements that should probably be \"continue\" statements.\n 3. It does not attempt to parse commits, and instead returns\n    immediately when finding an unparsed commit. This is something\n    that it did in its original version, so maybe it is by design,\n    but it doesn't match the doc comment for the method.\n\nConsider fixing these issues while you are here.\n\nThanks,\n-Stolee\n"},{"id":"476000","messageId":"CAKgqsWUEnbmhLL3p9+_P4yH_=A+hz+bBPqmfb8FyRUeW-u7_gw@mail.gmail.com","threadId":"59640","inReplyTo":"2bcaeba9-20bc-1ca8-849b-ac54342c71e3@github.com","subject":"Re: [External] Re: [PATCH v1] negotiator/default.c: avoid stack overflow","fromName":"Han Xin","fromEmail":"hanxin.hx@bytedance.com","sentAt":"2023-04-25T03:02:54Z","receivedAt":"2023-04-25T03:03:37Z","isPatch":true,"sender":{"key":"hanxin.hx@bytedance.com","avatar":"https://avatars.githubusercontent.com/u/16610542?v=4"},"body":"On Mon, Apr 24, 2023 at 10:44 PM Derrick Stolee\n<derrickstolee@github.com> wrote:\n>\n> > This is the same case as [1].\n> >\n> > 1. https://lore.kernel.org/git/20221025232934.1504445-1-jonathantanmy@google.com/\n>\n> Thanks for the link, though this could be replaced with\n>\n>   4654134976f (negotiator/skipping: avoid stack overflow, 2022-10-25)\n>\n> now that the change exists in the commit history.\n\nmake sense.\n\n>\n> One thing that is missing from that change is a test, and such a test\n> could be generalized to apply to all negotiators. This could maybe\n> help any potential future negotiator avoid this bug. Did you think\n> about what such a test could look like? Perhaps test_commit_bulk\n> could help, but we'd probably need to create so many commits that the\n> test would need to be marked as expensive. That's probably a major\n> reason to not include a test and rely on avoiding recursion when\n> possible.\n\nI first found this issue in a large repository with numerous merge commits.\nTo address it, I added a test case which fast-imports 10,000 commits and\nruns them through run_with_limited_stack(). Although expensive, this\napproach was successful in executing the test case without any issues.\n\n>\n> > -     if (commit != NULL && !(commit->object.flags & COMMON)) {\n> > +     struct prio_queue queue = { NULL };\n> > +\n> > +     prio_queue_put(&queue, commit);\n>\n> Should we check the conditions what were removed? The COMMON flag\n> is likely only useful for the recursion, but prio_queue_put() is\n> not careful about NULL values. However, no callers should be\n> providing NULL commits here.\n>\n> Couldn't hurt to add\n>\n>         if (!commit)\n>                 return;\n\nmake sense.\n\n>\n> before the prio_queue_put().\n>\n> > +     while ((commit = prio_queue_get(&queue))) {\n> >               struct object *o = (struct object *)commit;\n> >\n> > +             if (commit == NULL || (commit->object.flags & COMMON))\n> > +                     continue;\n>\n> The NULL condition is definitely unnecessary here as it is checked\n> by the while condition. The \"& COMMON\" is helpful if the commit\n> gained the COMMON flag after being inserted into the queue.\n>\n> >               if (!ancestors_only)\n> >                       o->flags |= COMMON;\n> >\n>\n>\n> > @@ -70,15 +76,17 @@ static void mark_common(struct negotiation_state *ns, struct commit *commit,\n> >                               ns->non_common_revs--;\n> >                       if (!o->parsed && !dont_parse)\n> >                               if (repo_parse_commit(the_repository, commit))\n> > -                                     return;\n> > +                                     continue;\n> >\n> > +                     ancestors_only = 0;\n>\n> This caught me off guard, but this flag essentially says \"should\n> I mark the first commit as common or not?\". It would probably be\n> clearer if this was done before the loop, and then was ignored\n> within the loop, setting the flag on each parent in this loop:\n>\n> >                       for (parents = commit->parents;\n> >                                       parents;\n> >                                       parents = parents->next)\n> > -                             mark_common(ns, parents->item, 0,\n> > -                                         dont_parse);\n> > +                             prio_queue_put(&queue, parents->item);\n>\n\nI'll think about how to optimize this again.\n\nancestors_only is used multiple times in the original logic:\n1.\n              if (!ancestors_only)\n                     o->flags |= COMMON;\n2.\n             if (!(o->flags & SEEN))\n                     rev_list_push(ns, commit, SEEN);\n             else {\n                     struct commit_list *parents;\n\n                     if (!ancestors_only && !(o->flags & POPPED))\n                             ns->non_common_revs--;\n\nShould we use this ?\n\n             if (!ancestors_only) {\n                    commit->object.flags |= COMMON;\n\n                    if ((commit->object.flags & SEEN) &&\n!(commit->object.flags & POPPED))\n                             ns->non_common_revs--;\n             }\n\nand\n\n                   for (parents = commit->parents;\n                             parents;\n                             parents = parents->next) {\n                             if (parents->item->object.flags & COMMON)\n                                      continue;\n\n                            parents->item->object.flags |= COMMON;\n\n                            if ((parents->item->object.flags & SEEN)\n                                     && !(parents->item->object.flags & POPPED))\n                                      ns->non_common_revs--;\n\n                            prio_queue_put(&queue, parents->item);\n                   }\n\n> It would have an extra benefit: your walk may duplicate objects in the\n> priority queue (there is no duplicate protection in prio_queue_put).\n> But, we could use\n>\n>         if (!(parents->item->object.flags & COMMON)) {\n>                 parents->item->object.flags |= COMMON;\n>                 prio_queue_put(&queue, parents->item);\n>         }\n>\n> as duplicate protection _and_ a clearer way to demonstrate what\n> ancestors_only is doing. Without this protection, it is possible\n> to have exponential growth in the priority queue using simple\n> merge commits.\n>\n> You'd need this at the beginning:\n>\n>         if (!commit)\n>                 return;\n>\n>         prio_queue_put(&queue, commit);\n>         if (!ancestors_only)\n>                 commit->object.flags |= COMMON;\n\nMake sense.\n\n> > diff --git a/negotiator/skipping.c b/negotiator/skipping.c\n> > index c7d6ab39bc..3d262b3533 100644\n> > --- a/negotiator/skipping.c\n> > +++ b/negotiator/skipping.c\n> > @@ -108,6 +108,8 @@ static void mark_common(struct data *data, struct commit *seen_commit)\n> >                               prio_queue_put(&queue, p->item);\n> >               }\n> >       }\n> > +\n> > +     clear_prio_queue(&queue);\n>\n> This memory leak cleanup in the skipping negotiator is good to\n> do, but should be split into its own change.\n>\n> In addition, the mark_common() method there seems to have a few\n> problems:\n>\n>  1. It does not do duplicate protection before prio_queue_put().\n>     (The COMMON bit would work here, too.)\n>  2. When it translated from recursive to iterative it kept \"return\"\n>     statements that should probably be \"continue\" statements.\n>  3. It does not attempt to parse commits, and instead returns\n>     immediately when finding an unparsed commit. This is something\n>     that it did in its original version, so maybe it is by design,\n>     but it doesn't match the doc comment for the method.\n>\n> Consider fixing these issues while you are here.\n>\n\nMake sense.\n\nThanks.\n-Han Xin\n"},{"id":"476020","messageId":"4ddb4030-0789-5ed4-448d-96f6afb48334@github.com","threadId":"59640","inReplyTo":"CAKgqsWUEnbmhLL3p9+_P4yH_=A+hz+bBPqmfb8FyRUeW-u7_gw@mail.gmail.com","subject":"Re: [External] Re: [PATCH v1] negotiator/default.c: avoid stack overflow","fromName":"Derrick Stolee","fromEmail":"derrickstolee@github.com","sentAt":"2023-04-25T13:34:38Z","receivedAt":"2023-04-25T13:35:19Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 4/24/2023 11:02 PM, Han Xin wrote:\n> On Mon, Apr 24, 2023 at 10:44 PM Derrick Stolee\n> <derrickstolee@github.com> wrote:\n\n>>> @@ -70,15 +76,17 @@ static void mark_common(struct negotiation_state *ns, struct commit *commit,\n>>>                               ns->non_common_revs--;\n>>>                       if (!o->parsed && !dont_parse)\n>>>                               if (repo_parse_commit(the_repository, commit))\n>>> -                                     return;\n>>> +                                     continue;\n>>>\n>>> +                     ancestors_only = 0;\n>>\n>> This caught me off guard, but this flag essentially says \"should\n>> I mark the first commit as common or not?\". It would probably be\n>> clearer if this was done before the loop, and then was ignored\n>> within the loop, setting the flag on each parent in this loop:\n>>\n>>>                       for (parents = commit->parents;\n>>>                                       parents;\n>>>                                       parents = parents->next)\n>>> -                             mark_common(ns, parents->item, 0,\n>>> -                                         dont_parse);\n>>> +                             prio_queue_put(&queue, parents->item);\n>>\n> \n> I'll think about how to optimize this again.\n> \n> ancestors_only is used multiple times in the original logic:\n> 1.\n>               if (!ancestors_only)\n>                      o->flags |= COMMON;\n> 2.\n>              if (!(o->flags & SEEN))\n>                      rev_list_push(ns, commit, SEEN);\n>              else {\n>                      struct commit_list *parents;\n> \n>                      if (!ancestors_only && !(o->flags & POPPED))\n>                              ns->non_common_revs--;\n\nGood point. Thanks for checking.\n \n> Should we use this ?\n> \n>              if (!ancestors_only) {\n>                     commit->object.flags |= COMMON;\n> \n>                     if ((commit->object.flags & SEEN) &&\n> !(commit->object.flags & POPPED))\n>                              ns->non_common_revs--;\n>              }\n\nThis seems correct, although your email seems to have done a strange\nline wrap that I'm sure you'll fix in the actual patch.\n\n> and\n> \n>                    for (parents = commit->parents;\n>                              parents;\n>                              parents = parents->next) {\n>                              if (parents->item->object.flags & COMMON)\n>                                       continue;\n> \n>                             parents->item->object.flags |= COMMON;\n\nThanks, this part avoids duplicate additions to the queue.\n\n>                             if ((parents->item->object.flags & SEEN)\n>                                      && !(parents->item->object.flags & POPPED))\n>                                       ns->non_common_revs--;\n\nAnd this matches the non_common_revs part.\n\nIf you want this code to be a little cleaner, you could add\n\n\tstruct commit *p = parents->item;\n\nat the start of the loop and then s/parents->item/p/ for the rest\nof the uses in the loop.\n\n>                             prio_queue_put(&queue, parents->item);\n>                    }\n\n>> In addition, the mark_common() method there seems to have a few\n>> problems:\n...\n>> Consider fixing these issues while you are here.\n>>\n> \n> Make sense.\n\nI'm looking forward to your v2!\n\nThanks,\n-Stolee\n"},{"id":"476085","messageId":"abbb1bc0b35d03e13249ec2e5bb8229a0a123685.1682473718.git.hanxin.hx@bytedance.com","threadId":"59640","inReplyTo":"cover.1682473718.git.hanxin.hx@bytedance.com","subject":"[PATCH v2 2/2] negotiator/skipping: fix some problems in mark_common()","fromName":"Han Xin","fromEmail":"hanxin.hx@bytedance.com","sentAt":"2023-04-26T04:05:23Z","receivedAt":"2023-04-26T04:05:54Z","isPatch":true,"sender":{"key":"hanxin.hx@bytedance.com","avatar":"https://avatars.githubusercontent.com/u/16610542?v=4"},"body":"Fixed the following problems:\n\n1. prio_queue() should be used with clear_prio_queue(), otherwise there\n   will be a memory leak.\n2. It does not do duplicate protection before prio_queue_put().\n   (The COMMON bit would work here, too.)\n3. When it translated from recursive to iterative it kept \"return\"\n   statements that should probably be \"continue\" statements.\n4. It does not attempt to parse commits, and instead returns\n   immediately when finding an unparsed commit. This is something\n   that it did in its original version, so maybe it is by design,\n   but it doesn't match the doc comment for the method.\n\nHelped-by: Derrick Stolee <derrickstolee@github.com>\nSigned-off-by: Han Xin <hanxin.hx@bytedance.com>\n---\n negotiator/skipping.c | 10 ++++++----\n 1 file changed, 6 insertions(+), 4 deletions(-)\n\ndiff --git a/negotiator/skipping.c b/negotiator/skipping.c\nindex c7d6ab39bc..b06dcb197b 100644\n--- a/negotiator/skipping.c\n+++ b/negotiator/skipping.c\n@@ -85,7 +85,7 @@ static int clear_marks(const char *refname, const struct object_id *oid,\n }\n \n /*\n- * Mark this SEEN commit and all its SEEN ancestors as COMMON.\n+ * Mark this SEEN commit and all its parsed SEEN ancestors as COMMON.\n  */\n static void mark_common(struct data *data, struct commit *seen_commit)\n {\n@@ -96,18 +96,20 @@ static void mark_common(struct data *data, struct commit *seen_commit)\n \twhile ((c = prio_queue_get(&queue))) {\n \t\tstruct commit_list *p;\n \t\tif (c->object.flags & COMMON)\n-\t\t\treturn;\n+\t\t\tcontinue;\n \t\tc->object.flags |= COMMON;\n \t\tif (!(c->object.flags & POPPED))\n \t\t\tdata->non_common_revs--;\n \n \t\tif (!c->object.parsed)\n-\t\t\treturn;\n+\t\t\tcontinue;\n \t\tfor (p = c->parents; p; p = p->next) {\n-\t\t\tif (p->item->object.flags & SEEN)\n+\t\t\tif (p->item->object.flags & SEEN || p->item->object.flags & COMMON)\n \t\t\t\tprio_queue_put(&queue, p->item);\n \t\t}\n \t}\n+\n+\tclear_prio_queue(&queue);\n }\n \n /*\n-- \n2.40.0\n\n"},{"id":"476086","messageId":"cover.1682473718.git.hanxin.hx@bytedance.com","threadId":"59640","inReplyTo":"20230424022318.80469-1-hanxin.hx@bytedance.com","subject":"[PATCH v2 0/2] negotiator/default: avoid stack overflow","fromName":"Han Xin","fromEmail":"hanxin.hx@bytedance.com","sentAt":"2023-04-26T04:05:21Z","receivedAt":"2023-04-26T04:06:09Z","isPatch":true,"sender":{"key":"hanxin.hx@bytedance.com","avatar":"https://avatars.githubusercontent.com/u/16610542?v=4"},"body":"This series avoid stack overflow in negotiator/default.c and memory leak\nin negotiator/skipping.c.\n\nChanges since v1:\n* Add duplicate protection in negotiator/default.c and\n  negotiator/skipping.c.\n* Split the memory leak cleanup in negotiator/skipping.c into its own\n  change and fix some other problems sugguested by Derrick Stolee.\n* Minor grammar/comment etc. fixes throughout.\n\nHan Xin (2):\n  negotiator/default: avoid stack overflow\n  negotiator/skipping: fix some problems in mark_common()\n\n negotiator/default.c  | 39 +++++++++++++++++++++++++++++----------\n negotiator/skipping.c | 10 ++++++----\n 2 files changed, 35 insertions(+), 14 deletions(-)\n\nRange-diff against v1:\n1:  a0a1473f5e < -:  ---------- negotiator/default.c: avoid stack overflow\n-:  ---------- > 1:  935be72eb9 negotiator/default: avoid stack overflow\n-:  ---------- > 2:  abbb1bc0b3 negotiator/skipping: fix some problems in mark_common()\n-- \n2.40.0\n\n"},{"id":"476087","messageId":"935be72eb92cd2eda7aff43c8cc2306b78b2a146.1682473718.git.hanxin.hx@bytedance.com","threadId":"59640","inReplyTo":"cover.1682473718.git.hanxin.hx@bytedance.com","subject":"[PATCH v2 1/2] negotiator/default: avoid stack overflow","fromName":"Han Xin","fromEmail":"hanxin.hx@bytedance.com","sentAt":"2023-04-26T04:05:22Z","receivedAt":"2023-04-26T04:06:14Z","isPatch":true,"sender":{"key":"hanxin.hx@bytedance.com","avatar":"https://avatars.githubusercontent.com/u/16610542?v=4"},"body":"mark_common() in negotiator/default.c may overflow the stack due to\nrecursive function calls. Avoid this by instead recursing using a\nheap-allocated data structure.\n\nThis is the same case as [1].\n\n1. 4654134976f (negotiator/skipping: avoid stack overflow, 2022-10-25)\n\nReported-by: Xin Xing <xingxin.xx@bytedance.com>\nSigned-off-by: Han Xin <hanxin.hx@bytedance.com>\n---\n negotiator/default.c | 39 +++++++++++++++++++++++++++++----------\n 1 file changed, 29 insertions(+), 10 deletions(-)\n\ndiff --git a/negotiator/default.c b/negotiator/default.c\nindex f4b78eb47d..635cdd6483 100644\n--- a/negotiator/default.c\n+++ b/negotiator/default.c\n@@ -55,30 +55,49 @@ static int clear_marks(const char *refname, const struct object_id *oid,\n static void mark_common(struct negotiation_state *ns, struct commit *commit,\n \t\tint ancestors_only, int dont_parse)\n {\n-\tif (commit != NULL && !(commit->object.flags & COMMON)) {\n-\t\tstruct object *o = (struct object *)commit;\n+\tstruct prio_queue queue = { NULL };\n+\n+\tif (!commit || (commit->object.flags & COMMON))\n+\t\treturn;\n+\n+\tprio_queue_put(&queue, commit);\n+\tif (!ancestors_only) {\n+\t\tcommit->object.flags |= COMMON;\n \n-\t\tif (!ancestors_only)\n-\t\t\to->flags |= COMMON;\n+\t\tif ((commit->object.flags & SEEN) && !(commit->object.flags & POPPED))\n+\t\t\tns->non_common_revs--;\n+\t}\n+\twhile ((commit = prio_queue_get(&queue))) {\n+\t\tstruct object *o = (struct object *)commit;\n \n \t\tif (!(o->flags & SEEN))\n \t\t\trev_list_push(ns, commit, SEEN);\n \t\telse {\n \t\t\tstruct commit_list *parents;\n \n-\t\t\tif (!ancestors_only && !(o->flags & POPPED))\n-\t\t\t\tns->non_common_revs--;\n \t\t\tif (!o->parsed && !dont_parse)\n \t\t\t\tif (repo_parse_commit(the_repository, commit))\n-\t\t\t\t\treturn;\n+\t\t\t\t\tcontinue;\n \n \t\t\tfor (parents = commit->parents;\n \t\t\t\t\tparents;\n-\t\t\t\t\tparents = parents->next)\n-\t\t\t\tmark_common(ns, parents->item, 0,\n-\t\t\t\t\t    dont_parse);\n+\t\t\t\t\tparents = parents->next) {\n+\t\t\t\tstruct commit *p = parents->item;\n+\n+\t\t\t\tif (p->object.flags & COMMON)\n+\t\t\t\t\tcontinue;\n+\n+\t\t\t\tp->object.flags |= COMMON;\n+\n+\t\t\t\tif ((p->object.flags & SEEN) && !(p->object.flags & POPPED))\n+\t\t\t\t\tns->non_common_revs--;\n+\n+\t\t\t\tprio_queue_put(&queue, parents->item);\n+\t\t\t}\n \t\t}\n \t}\n+\n+\tclear_prio_queue(&queue);\n }\n \n /*\n-- \n2.40.0\n\n"},{"id":"476097","messageId":"41273b5d-f4f8-2dce-94d1-37a9b56ed1ea@github.com","threadId":"59640","inReplyTo":"abbb1bc0b35d03e13249ec2e5bb8229a0a123685.1682473718.git.hanxin.hx@bytedance.com","subject":"Re: [PATCH v2 2/2] negotiator/skipping: fix some problems in mark_common()","fromName":"Derrick Stolee","fromEmail":"derrickstolee@github.com","sentAt":"2023-04-26T11:08:54Z","receivedAt":"2023-04-26T11:09:00Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 4/26/2023 12:05 AM, Han Xin wrote:\n> Fixed the following problems:\n\nThis might be a good time to reference the change from recursive to\niterative:\n\n  The mark_common() method in negotiator/skipping.c was converted\n  from recursive to iterative in 4654134976f (negotiator/skipping:\n  avoid stack overflow, 2022-10-25), but there is some more work\n  to do:\n \n> 1. prio_queue() should be used with clear_prio_queue(), otherwise there\n>    will be a memory leak.\n> 2. It does not do duplicate protection before prio_queue_put().\n>    (The COMMON bit would work here, too.)\n> 3. When it translated from recursive to iterative it kept \"return\"\n>    statements that should probably be \"continue\" statements.\n> 4. It does not attempt to parse commits, and instead returns\n>    immediately when finding an unparsed commit. This is something\n>    that it did in its original version, so maybe it is by design,\n>    but it doesn't match the doc comment for the method.\n> \n> Helped-by: Derrick Stolee <derrickstolee@github.com>\n> Signed-off-by: Han Xin <hanxin.hx@bytedance.com>\n> ---\n>  negotiator/skipping.c | 10 ++++++----\n>  1 file changed, 6 insertions(+), 4 deletions(-)\n> \n> diff --git a/negotiator/skipping.c b/negotiator/skipping.c\n> index c7d6ab39bc..b06dcb197b 100644\n> --- a/negotiator/skipping.c\n> +++ b/negotiator/skipping.c\n> @@ -85,7 +85,7 @@ static int clear_marks(const char *refname, const struct object_id *oid,\n>  }\n>  \n>  /*\n> - * Mark this SEEN commit and all its SEEN ancestors as COMMON.\n> + * Mark this SEEN commit and all its parsed SEEN ancestors as COMMON.\n\nOk, the doc comment is updated here instead of starting to parse\ncommits. Since this is the behavior since it was first introduced\nin 42cc7485a2e (negotiator/skipping: skip commits during fetch,\n2018-07-16), this is the best thing to do.\n\nI notice from a second glance that we are only walking the commits\nthat are marked SEEN, so we are only visiting commits with respect\nto a previous walk of some kind, which provides some explanation.\n\n>  \twhile ((c = prio_queue_get(&queue))) {\n>  \t\tstruct commit_list *p;\n>  \t\tif (c->object.flags & COMMON)\n> -\t\t\treturn;\n> +\t\t\tcontinue;\n>  \t\tc->object.flags |= COMMON;\n>  \t\tif (!(c->object.flags & POPPED))\n>  \t\t\tdata->non_common_revs--;\n>  \n>  \t\tif (!c->object.parsed)\n> -\t\t\treturn;\n> +\t\t\tcontinue;\n>  \t\tfor (p = c->parents; p; p = p->next) {\n> -\t\t\tif (p->item->object.flags & SEEN)\n> +\t\t\tif (p->item->object.flags & SEEN || p->item->object.flags & COMMON)\n>  \t\t\t\tprio_queue_put(&queue, p->item);\n\nThis is the incorrect check for the COMMON bit, because it is\na positive check (we add the common bit after we pop a commit\nfrom the queue) _and_ because we could add a commit multiple\ntimes before it is first popped and that bit is added.\n\nInstead, we need\n\n\t\t\tif ((p->item->object.flags & SEEN) &&\n\t\t\t    !(p->item->object.flags & COMMON)) {\n\t\t\t\tp->item->object.flags |= COMMON;\n\t\t\t\tprio_queue_put(&queue, p->item);\n\t\t\t}\n\nand at the start of the loop we need to add the COMMON bit to\nthe starting commit. We also need to remove this bit from the\nmain section of the loop:\n\n  \t\tif (c->object.flags & COMMON)\n\t\t\tcontinue;\n \t\tc->object.flags |= COMMON;\n\nbecause it does nothing if the COMMON bit is added before\nbeing added to the queue.\n\nI'm very suspicious that this change did not trigger a test\nfailure, since the behavior is quite different from the previous\nversion. Of course, the recursive-to-iterative change was first\nto change the behavior, so I'm not surprised that it isn't caught\nby tests. What kind of tests can we introduce to harden our\ncoverage here?\n\n>  \t\t}\n>  \t}\n> +\n> +\tclear_prio_queue(&queue);\n\nGood to clean up this queue.\n\nThanks,\n-Stolee\n\n"},{"id":"476098","messageId":"bf45bfe7-4a29-38d6-b8d7-811581aec82b@github.com","threadId":"59640","inReplyTo":"935be72eb92cd2eda7aff43c8cc2306b78b2a146.1682473718.git.hanxin.hx@bytedance.com","subject":"Re: [PATCH v2 1/2] negotiator/default: avoid stack overflow","fromName":"Derrick Stolee","fromEmail":"derrickstolee@github.com","sentAt":"2023-04-26T11:13:15Z","receivedAt":"2023-04-26T11:13:23Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 4/26/2023 12:05 AM, Han Xin wrote:\n> mark_common() in negotiator/default.c may overflow the stack due to\n> recursive function calls. Avoid this by instead recursing using a\n> heap-allocated data structure.\n> \n> This is the same case as [1].\n> \n> 1. 4654134976f (negotiator/skipping: avoid stack overflow, 2022-10-25)\n\nWe would typically write this inline, such as:\n\n  This is the same case as 4654134976f (negotiator/skipping: avoid\n  stack overflow, 2022-10-25)\n\n> -\tif (commit != NULL && !(commit->object.flags & COMMON)) {\n> -\t\tstruct object *o = (struct object *)commit;\n> +\tstruct prio_queue queue = { NULL };\n> +\n> +\tif (!commit || (commit->object.flags & COMMON))\n> +\t\treturn;\n> +\n> +\tprio_queue_put(&queue, commit);\n> +\tif (!ancestors_only) {\n> +\t\tcommit->object.flags |= COMMON;\n>  \n> -\t\tif (!ancestors_only)\n> -\t\t\to->flags |= COMMON;\n> +\t\tif ((commit->object.flags & SEEN) && !(commit->object.flags & POPPED))\n> +\t\t\tns->non_common_revs--;\n> +\t}\n> +\twhile ((commit = prio_queue_get(&queue))) {\n> +\t\tstruct object *o = (struct object *)commit;\n>  \n>  \t\tif (!(o->flags & SEEN))\n>  \t\t\trev_list_push(ns, commit, SEEN);\n>  \t\telse {\n>  \t\t\tstruct commit_list *parents;\n>  \n> -\t\t\tif (!ancestors_only && !(o->flags & POPPED))\n> -\t\t\t\tns->non_common_revs--;\n>  \t\t\tif (!o->parsed && !dont_parse)\n>  \t\t\t\tif (repo_parse_commit(the_repository, commit))\n> -\t\t\t\t\treturn;\n> +\t\t\t\t\tcontinue;\n>  \n>  \t\t\tfor (parents = commit->parents;\n>  \t\t\t\t\tparents;\n> -\t\t\t\t\tparents = parents->next)\n> -\t\t\t\tmark_common(ns, parents->item, 0,\n> -\t\t\t\t\t    dont_parse);\n> +\t\t\t\t\tparents = parents->next) {\n> +\t\t\t\tstruct commit *p = parents->item;\n> +\n> +\t\t\t\tif (p->object.flags & COMMON)\n> +\t\t\t\t\tcontinue;\n> +\n> +\t\t\t\tp->object.flags |= COMMON;\n> +\n> +\t\t\t\tif ((p->object.flags & SEEN) && !(p->object.flags & POPPED))\n> +\t\t\t\t\tns->non_common_revs--;\n> +\n> +\t\t\t\tprio_queue_put(&queue, parents->item);\n> +\t\t\t}\n>  \t\t}\n>  \t}\n> +\n> +\tclear_prio_queue(&queue);\n\nThanks for this version. It looks like an identical set of actions\nin the commit walk, but the change from DFS to priority queue is\na welcome change.\n\n-Stolee\n"},{"id":"476101","messageId":"CAKgqsWV==tgyz8EOs61_06+bX4Eq+0Su1bocZ+-s4oe+e0DdJA@mail.gmail.com","threadId":"59640","inReplyTo":"bf45bfe7-4a29-38d6-b8d7-811581aec82b@github.com","subject":"Re: [External] Re: [PATCH v2 1/2] negotiator/default: avoid stack overflow","fromName":"Han Xin","fromEmail":"hanxin.hx@bytedance.com","sentAt":"2023-04-26T11:40:35Z","receivedAt":"2023-04-26T11:41:15Z","isPatch":true,"sender":{"key":"hanxin.hx@bytedance.com","avatar":"https://avatars.githubusercontent.com/u/16610542?v=4"},"body":"On Wed, Apr 26, 2023 at 7:13 PM Derrick Stolee <derrickstolee@github.com> wrote:\n>\n> On 4/26/2023 12:05 AM, Han Xin wrote:\n> > mark_common() in negotiator/default.c may overflow the stack due to\n> > recursive function calls. Avoid this by instead recursing using a\n> > heap-allocated data structure.\n> >\n> > This is the same case as [1].\n> >\n> > 1. 4654134976f (negotiator/skipping: avoid stack overflow, 2022-10-25)\n>\n> We would typically write this inline, such as:\n>\n>   This is the same case as 4654134976f (negotiator/skipping: avoid\n>   stack overflow, 2022-10-25)\n>\n\nMake sense.\n\nThanks\n-Han Xin\n"},{"id":"476102","messageId":"CAKgqsWXU0ZCuQtCPA+O+g-36SkF7w2vsgPxS4iQ7gu5V+XCHhQ@mail.gmail.com","threadId":"59640","inReplyTo":"41273b5d-f4f8-2dce-94d1-37a9b56ed1ea@github.com","subject":"Re: [External] Re: [PATCH v2 2/2] negotiator/skipping: fix some problems in mark_common()","fromName":"Han Xin","fromEmail":"hanxin.hx@bytedance.com","sentAt":"2023-04-26T11:55:49Z","receivedAt":"2023-04-26T11:56:35Z","isPatch":true,"sender":{"key":"hanxin.hx@bytedance.com","avatar":"https://avatars.githubusercontent.com/u/16610542?v=4"},"body":"On Wed, Apr 26, 2023 at 7:09 PM Derrick Stolee <derrickstolee@github.com> wrote:\n>\n> On 4/26/2023 12:05 AM, Han Xin wrote:\n> > Fixed the following problems:\n>\n> This might be a good time to reference the change from recursive to\n> iterative:\n>\n>   The mark_common() method in negotiator/skipping.c was converted\n>   from recursive to iterative in 4654134976f (negotiator/skipping:\n>   avoid stack overflow, 2022-10-25), but there is some more work\n>   to do:\n>\n\nMake sense.\n\n> >       while ((c = prio_queue_get(&queue))) {\n> >               struct commit_list *p;\n> >               if (c->object.flags & COMMON)\n> > -                     return;\n> > +                     continue;\n> >               c->object.flags |= COMMON;\n> >               if (!(c->object.flags & POPPED))\n> >                       data->non_common_revs--;\n> >\n> >               if (!c->object.parsed)\n> > -                     return;\n> > +                     continue;\n> >               for (p = c->parents; p; p = p->next) {\n> > -                     if (p->item->object.flags & SEEN)\n> > +                     if (p->item->object.flags & SEEN || p->item->object.flags & COMMON)\n> >                               prio_queue_put(&queue, p->item);\n>\n> This is the incorrect check for the COMMON bit, because it is\n> a positive check (we add the common bit after we pop a commit\n> from the queue) _and_ because we could add a commit multiple\n> times before it is first popped and that bit is added.\n>\n\nYes, I introduced a silly thing.\n\n> Instead, we need\n>\n>                         if ((p->item->object.flags & SEEN) &&\n>                             !(p->item->object.flags & COMMON)) {\n>                                 p->item->object.flags |= COMMON;\n>                                 prio_queue_put(&queue, p->item);\n>                         }\n>\n> and at the start of the loop we need to add the COMMON bit to\n> the starting commit. We also need to remove this bit from the\n> main section of the loop:\n>\n>                 if (c->object.flags & COMMON)\n>                         continue;\n>                 c->object.flags |= COMMON;\n>\n> because it does nothing if the COMMON bit is added before\n> being added to the queue.\n>\n\nMake sense.\nAnd with this, we should do return before loop:\n\n                if (seen_commit->object.flags & COMMON)\n                        return;\n\n                prio_queue_put(&queue, seen_commit);\n                while ((c = prio_queue_get(&queue))) {\n\n> I'm very suspicious that this change did not trigger a test\n> failure, since the behavior is quite different from the previous\n> version. Of course, the recursive-to-iterative change was first\n> to change the behavior, so I'm not surprised that it isn't caught\n> by tests. What kind of tests can we introduce to harden our\n> coverage here?\n>\n\nWith \"p->item->object.flags & COMMON\", it takes more meaningless\nwalking, but doesn't seem to introduce any errors. I haven't found any\ngood way to avoid similar problems.\n\nThanks\n-Han Xin\n"},{"id":"476103","messageId":"cover.1682513384.git.hanxin.hx@bytedance.com","threadId":"59640","inReplyTo":"cover.1682473718.git.hanxin.hx@bytedance.com","subject":"[PATCH v2 0/2] negotiator/default: avoid stack overflow","fromName":"Han Xin","fromEmail":"hanxin.hx@bytedance.com","sentAt":"2023-04-26T13:15:02Z","receivedAt":"2023-04-26T13:15:41Z","isPatch":true,"sender":{"key":"hanxin.hx@bytedance.com","avatar":"https://avatars.githubusercontent.com/u/16610542?v=4"},"body":"This series avoid stack overflow in negotiator/default.c and memory leak\nin negotiator/skipping.c.\n\nChanges since v2:\n* Rewrite the commit link in the typical format.\n* Fix the incorrect check for the COMMON bit introduced in v2.\n\nHan Xin (2):\n  negotiator/default: avoid stack overflow\n  negotiator/skipping: fix some problems in mark_common()\n\n negotiator/default.c  | 39 +++++++++++++++++++++++++++++----------\n negotiator/skipping.c | 22 +++++++++++++++-------\n 2 files changed, 44 insertions(+), 17 deletions(-)\n\nRange-diff against v2:\n1:  935be72eb9 ! 1:  0e69d70805 negotiator/default: avoid stack overflow\n    @@ Commit message\n         recursive function calls. Avoid this by instead recursing using a\n         heap-allocated data structure.\n     \n    -    This is the same case as [1].\n    -\n    -    1. 4654134976f (negotiator/skipping: avoid stack overflow, 2022-10-25)\n    +    This is the same case as 4654134976f (negotiator/skipping: avoid\n    +    stack overflow, 2022-10-25)\n     \n         Reported-by: Xin Xing <xingxin.xx@bytedance.com>\n         Signed-off-by: Han Xin <hanxin.hx@bytedance.com>\n2:  abbb1bc0b3 ! 2:  8b5c92a4d5 negotiator/skipping: fix some problems in mark_common()\n    @@ Metadata\n      ## Commit message ##\n         negotiator/skipping: fix some problems in mark_common()\n     \n    -    Fixed the following problems:\n    +    The mark_common() method in negotiator/skipping.c was converted\n    +    from recursive to iterative in 4654134976f (negotiator/skipping:\n    +    avoid stack overflow, 2022-10-25), but there is some more work\n    +    to do:\n     \n         1. prio_queue() should be used with clear_prio_queue(), otherwise there\n            will be a memory leak.\n    @@ negotiator/skipping.c: static int clear_marks(const char *refname, const struct\n       */\n      static void mark_common(struct data *data, struct commit *seen_commit)\n      {\n    -@@ negotiator/skipping.c: static void mark_common(struct data *data, struct commit *seen_commit)\n    + \tstruct prio_queue queue = { NULL };\n    + \tstruct commit *c;\n    + \n    ++\tif (seen_commit->object.flags & COMMON)\n    ++\t\treturn;\n    ++\n    + \tprio_queue_put(&queue, seen_commit);\n    ++\tseen_commit->object.flags |= COMMON;\n      \twhile ((c = prio_queue_get(&queue))) {\n      \t\tstruct commit_list *p;\n    - \t\tif (c->object.flags & COMMON)\n    +-\t\tif (c->object.flags & COMMON)\n     -\t\t\treturn;\n    -+\t\t\tcontinue;\n    - \t\tc->object.flags |= COMMON;\n    +-\t\tc->object.flags |= COMMON;\n    ++\n      \t\tif (!(c->object.flags & POPPED))\n      \t\t\tdata->non_common_revs--;\n      \n    @@ negotiator/skipping.c: static void mark_common(struct data *data, struct commit\n     +\t\t\tcontinue;\n      \t\tfor (p = c->parents; p; p = p->next) {\n     -\t\t\tif (p->item->object.flags & SEEN)\n    -+\t\t\tif (p->item->object.flags & SEEN || p->item->object.flags & COMMON)\n    - \t\t\t\tprio_queue_put(&queue, p->item);\n    +-\t\t\t\tprio_queue_put(&queue, p->item);\n    ++\t\t\tif (!(p->item->object.flags & SEEN) ||\n    ++\t\t\t    (p->item->object.flags & COMMON))\n    ++\t\t\t\tcontinue;\n    ++\n    ++\t\t\tp->item->object.flags |= COMMON;\n    ++\t\t\tprio_queue_put(&queue, p->item);\n      \t\t}\n      \t}\n     +\n-- \n2.40.0\n\n"},{"id":"476104","messageId":"0e69d70805e6da684e6e17642a1cf0d59a03dfc0.1682513384.git.hanxin.hx@bytedance.com","threadId":"59640","inReplyTo":"cover.1682513384.git.hanxin.hx@bytedance.com","subject":"[PATCH v3 1/2] negotiator/default: avoid stack overflow","fromName":"Han Xin","fromEmail":"hanxin.hx@bytedance.com","sentAt":"2023-04-26T13:15:03Z","receivedAt":"2023-04-26T13:15:45Z","isPatch":true,"sender":{"key":"hanxin.hx@bytedance.com","avatar":"https://avatars.githubusercontent.com/u/16610542?v=4"},"body":"mark_common() in negotiator/default.c may overflow the stack due to\nrecursive function calls. Avoid this by instead recursing using a\nheap-allocated data structure.\n\nThis is the same case as 4654134976f (negotiator/skipping: avoid\nstack overflow, 2022-10-25)\n\nReported-by: Xin Xing <xingxin.xx@bytedance.com>\nSigned-off-by: Han Xin <hanxin.hx@bytedance.com>\n---\n negotiator/default.c | 39 +++++++++++++++++++++++++++++----------\n 1 file changed, 29 insertions(+), 10 deletions(-)\n\ndiff --git a/negotiator/default.c b/negotiator/default.c\nindex f4b78eb47d..635cdd6483 100644\n--- a/negotiator/default.c\n+++ b/negotiator/default.c\n@@ -55,30 +55,49 @@ static int clear_marks(const char *refname, const struct object_id *oid,\n static void mark_common(struct negotiation_state *ns, struct commit *commit,\n \t\tint ancestors_only, int dont_parse)\n {\n-\tif (commit != NULL && !(commit->object.flags & COMMON)) {\n-\t\tstruct object *o = (struct object *)commit;\n+\tstruct prio_queue queue = { NULL };\n+\n+\tif (!commit || (commit->object.flags & COMMON))\n+\t\treturn;\n+\n+\tprio_queue_put(&queue, commit);\n+\tif (!ancestors_only) {\n+\t\tcommit->object.flags |= COMMON;\n \n-\t\tif (!ancestors_only)\n-\t\t\to->flags |= COMMON;\n+\t\tif ((commit->object.flags & SEEN) && !(commit->object.flags & POPPED))\n+\t\t\tns->non_common_revs--;\n+\t}\n+\twhile ((commit = prio_queue_get(&queue))) {\n+\t\tstruct object *o = (struct object *)commit;\n \n \t\tif (!(o->flags & SEEN))\n \t\t\trev_list_push(ns, commit, SEEN);\n \t\telse {\n \t\t\tstruct commit_list *parents;\n \n-\t\t\tif (!ancestors_only && !(o->flags & POPPED))\n-\t\t\t\tns->non_common_revs--;\n \t\t\tif (!o->parsed && !dont_parse)\n \t\t\t\tif (repo_parse_commit(the_repository, commit))\n-\t\t\t\t\treturn;\n+\t\t\t\t\tcontinue;\n \n \t\t\tfor (parents = commit->parents;\n \t\t\t\t\tparents;\n-\t\t\t\t\tparents = parents->next)\n-\t\t\t\tmark_common(ns, parents->item, 0,\n-\t\t\t\t\t    dont_parse);\n+\t\t\t\t\tparents = parents->next) {\n+\t\t\t\tstruct commit *p = parents->item;\n+\n+\t\t\t\tif (p->object.flags & COMMON)\n+\t\t\t\t\tcontinue;\n+\n+\t\t\t\tp->object.flags |= COMMON;\n+\n+\t\t\t\tif ((p->object.flags & SEEN) && !(p->object.flags & POPPED))\n+\t\t\t\t\tns->non_common_revs--;\n+\n+\t\t\t\tprio_queue_put(&queue, parents->item);\n+\t\t\t}\n \t\t}\n \t}\n+\n+\tclear_prio_queue(&queue);\n }\n \n /*\n-- \n2.40.0\n\n"},{"id":"476105","messageId":"8b5c92a4d5d0927320f1e5fdb0136952f41be21c.1682513384.git.hanxin.hx@bytedance.com","threadId":"59640","inReplyTo":"cover.1682513384.git.hanxin.hx@bytedance.com","subject":"[PATCH v3 2/2] negotiator/skipping: fix some problems in mark_common()","fromName":"Han Xin","fromEmail":"hanxin.hx@bytedance.com","sentAt":"2023-04-26T13:15:04Z","receivedAt":"2023-04-26T13:15:55Z","isPatch":true,"sender":{"key":"hanxin.hx@bytedance.com","avatar":"https://avatars.githubusercontent.com/u/16610542?v=4"},"body":"The mark_common() method in negotiator/skipping.c was converted\nfrom recursive to iterative in 4654134976f (negotiator/skipping:\navoid stack overflow, 2022-10-25), but there is some more work\nto do:\n\n1. prio_queue() should be used with clear_prio_queue(), otherwise there\n   will be a memory leak.\n2. It does not do duplicate protection before prio_queue_put().\n   (The COMMON bit would work here, too.)\n3. When it translated from recursive to iterative it kept \"return\"\n   statements that should probably be \"continue\" statements.\n4. It does not attempt to parse commits, and instead returns\n   immediately when finding an unparsed commit. This is something\n   that it did in its original version, so maybe it is by design,\n   but it doesn't match the doc comment for the method.\n\nHelped-by: Derrick Stolee <derrickstolee@github.com>\nSigned-off-by: Han Xin <hanxin.hx@bytedance.com>\n---\n negotiator/skipping.c | 22 +++++++++++++++-------\n 1 file changed, 15 insertions(+), 7 deletions(-)\n\ndiff --git a/negotiator/skipping.c b/negotiator/skipping.c\nindex c7d6ab39bc..6a5450b460 100644\n--- a/negotiator/skipping.c\n+++ b/negotiator/skipping.c\n@@ -85,29 +85,37 @@ static int clear_marks(const char *refname, const struct object_id *oid,\n }\n \n /*\n- * Mark this SEEN commit and all its SEEN ancestors as COMMON.\n+ * Mark this SEEN commit and all its parsed SEEN ancestors as COMMON.\n  */\n static void mark_common(struct data *data, struct commit *seen_commit)\n {\n \tstruct prio_queue queue = { NULL };\n \tstruct commit *c;\n \n+\tif (seen_commit->object.flags & COMMON)\n+\t\treturn;\n+\n \tprio_queue_put(&queue, seen_commit);\n+\tseen_commit->object.flags |= COMMON;\n \twhile ((c = prio_queue_get(&queue))) {\n \t\tstruct commit_list *p;\n-\t\tif (c->object.flags & COMMON)\n-\t\t\treturn;\n-\t\tc->object.flags |= COMMON;\n+\n \t\tif (!(c->object.flags & POPPED))\n \t\t\tdata->non_common_revs--;\n \n \t\tif (!c->object.parsed)\n-\t\t\treturn;\n+\t\t\tcontinue;\n \t\tfor (p = c->parents; p; p = p->next) {\n-\t\t\tif (p->item->object.flags & SEEN)\n-\t\t\t\tprio_queue_put(&queue, p->item);\n+\t\t\tif (!(p->item->object.flags & SEEN) ||\n+\t\t\t    (p->item->object.flags & COMMON))\n+\t\t\t\tcontinue;\n+\n+\t\t\tp->item->object.flags |= COMMON;\n+\t\t\tprio_queue_put(&queue, p->item);\n \t\t}\n \t}\n+\n+\tclear_prio_queue(&queue);\n }\n \n /*\n-- \n2.40.0\n\n"},{"id":"476120","messageId":"xmqqedo6tvkj.fsf@gitster.g","threadId":"59640","inReplyTo":"0e69d70805e6da684e6e17642a1cf0d59a03dfc0.1682513384.git.hanxin.hx@bytedance.com","subject":"Re: [PATCH v3 1/2] negotiator/default: avoid stack overflow","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2023-04-26T17:14:20Z","receivedAt":"2023-04-26T17:14:35Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Han Xin <hanxin.hx@bytedance.com> writes:\n\n> mark_common() in negotiator/default.c may overflow the stack due to\n> recursive function calls. Avoid this by instead recursing using a\n> heap-allocated data structure.\n>\n> This is the same case as 4654134976f (negotiator/skipping: avoid\n> stack overflow, 2022-10-25)\n>\n> Reported-by: Xin Xing <xingxin.xx@bytedance.com>\n> Signed-off-by: Han Xin <hanxin.hx@bytedance.com>\n> ---\n>  negotiator/default.c | 39 +++++++++++++++++++++++++++++----------\n>  1 file changed, 29 insertions(+), 10 deletions(-)\n>\n> diff --git a/negotiator/default.c b/negotiator/default.c\n> index f4b78eb47d..635cdd6483 100644\n> --- a/negotiator/default.c\n> +++ b/negotiator/default.c\n> @@ -55,30 +55,49 @@ static int clear_marks(const char *refname, const struct object_id *oid,\n>  static void mark_common(struct negotiation_state *ns, struct commit *commit,\n>  \t\tint ancestors_only, int dont_parse)\n>  {\n> -\tif (commit != NULL && !(commit->object.flags & COMMON)) {\n> -\t\tstruct object *o = (struct object *)commit;\n> +\tstruct prio_queue queue = { NULL };\n> +\n> +\tif (!commit || (commit->object.flags & COMMON))\n> +\t\treturn;\n\nThe original naive recursive marker had a large if block guarded by\nthe opposite condition around the whole thing, which amounts to the\nsame as this early return.  Good.\n\n> +\tprio_queue_put(&queue, commit);\n\nAnd the code now uses on-stack priority queue here, and bootstraps\nthe machinery by placing the first element here.  OK.\n\n> +\tif (!ancestors_only) {\n> +\t\tcommit->object.flags |= COMMON;\n>  \n> -\t\tif (!ancestors_only)\n> -\t\t\to->flags |= COMMON;\n\nThese two are equivalent, which is good.\n\n> +\t\tif ((commit->object.flags & SEEN) && !(commit->object.flags & POPPED))\n> +\t\t\tns->non_common_revs--;\n\nHmph, this is a bit unexpected to duplicate the non_common_revs\ncounting logic here.  In the original, this piece of code was there\njust after we decided to continue digging into the parents, and even\nif this patch changes the mechanism with which \"digging into the\nparents\" from recursion to priority queue, it is not obvious why we\ncan keep doing the decrementing for the current commit we are\nlooking at, instead of doing that for parents of the commit like\nthis patch does.  In other words, it is not clear why it needs to be\nchanged while going from recursive to iterative.\n\nIs it because ancestors_only is not usable inside the loop in the\niterative version?  That is, if ancestors_only is not set, we do\npaint the initial commit as COMMON just as the parents we discover\nin the loop, but when ancestors_only is set, we need to skip painting\nthe initial commit as COMMON, so the patch moves that logic?\n\nIt may solve the issue of special casing the initial commit, but it\nfeels backwards in that the resulting loop becomes harder to\nunderstand by making it necessary to process the initial commit\noutside the loop only halfway.\n\nIt may make it easier to understand if we had another local\nvariable, \"struct commit *skip_commit\", that is NULL by default but\nis set to the initial commit when ancestors_only is set, and do the\npainting with COMMON and counting of non_common_revs all inside the\nloop for the current commit that is being processed (instead of the\nparents the loop discovered).  I dunno.  It would avoid duplicating\nthe logic and implements the \"ancestors_only, do not paint or count\nthe initial commit\" in a more readable and straight-forward way, no?\n\nThanks.\n\n> +\t}\n> +\twhile ((commit = prio_queue_get(&queue))) {\n> +\t\tstruct object *o = (struct object *)commit;\n>  \n>  \t\tif (!(o->flags & SEEN))\n>  \t\t\trev_list_push(ns, commit, SEEN);\n>  \t\telse {\n>  \t\t\tstruct commit_list *parents;\n>  \n> -\t\t\tif (!ancestors_only && !(o->flags & POPPED))\n> -\t\t\t\tns->non_common_revs--;\n>  \t\t\tif (!o->parsed && !dont_parse)\n>  \t\t\t\tif (repo_parse_commit(the_repository, commit))\n> -\t\t\t\t\treturn;\n> +\t\t\t\t\tcontinue;\n>  \n>  \t\t\tfor (parents = commit->parents;\n>  \t\t\t\t\tparents;\n> -\t\t\t\t\tparents = parents->next)\n> -\t\t\t\tmark_common(ns, parents->item, 0,\n> -\t\t\t\t\t    dont_parse);\n> +\t\t\t\t\tparents = parents->next) {\n> +\t\t\t\tstruct commit *p = parents->item;\n> +\n> +\t\t\t\tif (p->object.flags & COMMON)\n> +\t\t\t\t\tcontinue;\n> +\n> +\t\t\t\tp->object.flags |= COMMON;\n> +\n> +\t\t\t\tif ((p->object.flags & SEEN) && !(p->object.flags & POPPED))\n> +\t\t\t\t\tns->non_common_revs--;\n> +\n> +\t\t\t\tprio_queue_put(&queue, parents->item);\n> +\t\t\t}\n>  \t\t}\n>  \t}\n> +\n> +\tclear_prio_queue(&queue);\n>  }\n>  \n>  /*\n"},{"id":"476123","messageId":"49695ce0-b9f9-0fc7-ed16-093dc7f12b7e@github.com","threadId":"59640","inReplyTo":"xmqqedo6tvkj.fsf@gitster.g","subject":"Re: [PATCH v3 1/2] negotiator/default: avoid stack overflow","fromName":"Derrick Stolee","fromEmail":"derrickstolee@github.com","sentAt":"2023-04-26T17:30:21Z","receivedAt":"2023-04-26T17:30:47Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 4/26/2023 1:14 PM, Junio C Hamano wrote:\n> Han Xin <hanxin.hx@bytedance.com> writes:\n\n>> +\t\tif ((commit->object.flags & SEEN) && !(commit->object.flags & POPPED))\n>> +\t\t\tns->non_common_revs--;\n> \n> Hmph, this is a bit unexpected to duplicate the non_common_revs\n> counting logic here.  In the original, this piece of code was there\n> just after we decided to continue digging into the parents, and even\n> if this patch changes the mechanism with which \"digging into the\n> parents\" from recursion to priority queue, it is not obvious why we\n> can keep doing the decrementing for the current commit we are\n> looking at, instead of doing that for parents of the commit like\n> this patch does.  In other words, it is not clear why it needs to be\n> changed while going from recursive to iterative.\n> \n> Is it because ancestors_only is not usable inside the loop in the\n> iterative version?  That is, if ancestors_only is not set, we do\n> paint the initial commit as COMMON just as the parents we discover\n> in the loop, but when ancestors_only is set, we need to skip painting\n> the initial commit as COMMON, so the patch moves that logic?\n> \n> It may solve the issue of special casing the initial commit, but it\n> feels backwards in that the resulting loop becomes harder to\n> understand by making it necessary to process the initial commit\n> outside the loop only halfway.\n\nThe \"ancestors_only\" parameter is about treating the initial commit\ndifferently than the ancestors. Since we add the initial commit to\nthe priority queue, the only way to know we are dealing with an\nancestor and not the initial commit is to do the processing when\nvisiting a parent for the first time.\n\n> It may make it easier to understand if we had another local\n> variable, \"struct commit *skip_commit\", that is NULL by default but\n> is set to the initial commit when ancestors_only is set,\n\nThis is an interesting idea and could reduce the duplicated logic\nfor nw->common_revs.\n\n> and do the\n> painting with COMMON and counting of non_common_revs all inside the\n> loop for the current commit that is being processed (instead of the\n> parents the loop discovered).  I dunno.  It would avoid duplicating\n> the logic and implements the \"ancestors_only, do not paint or count\n> the initial commit\" in a more readable and straight-forward way, no?\n\nHowever, we need to do the painting with COMMON when visiting a\nparent in order to avoid adding duplicate entries to the priority\nqueue (and potentially growing exponentially).\n\nSince we need to examine and modify a parent before adding it to\nthe queue, it is natural to do other \"we are visiting a commit\"\nlogic in that same place.\n\nIt is unfortunate that the logic for nw->common_revs is duplicated,\nbut I think this is a cleaner approach than other considered\napproaches.\n\nThanks,\n-Stolee\n"},{"id":"476125","messageId":"xmqq354mtugc.fsf@gitster.g","threadId":"59640","inReplyTo":"49695ce0-b9f9-0fc7-ed16-093dc7f12b7e@github.com","subject":"Re: [PATCH v3 1/2] negotiator/default: avoid stack overflow","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2023-04-26T17:38:27Z","receivedAt":"2023-04-26T17:38:31Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Derrick Stolee <derrickstolee@github.com> writes:\n\n> It is unfortunate that the logic for nw->common_revs is duplicated,\n> but I think this is a cleaner approach than other considered\n> approaches.\n\nIt is subjective and as long as the result works correctly, I am\nfine with it ;-).\n\nThanks.\n"},{"id":"476388","messageId":"xmqqildb3dnn.fsf@gitster.g","threadId":"59640","inReplyTo":"cover.1682513384.git.hanxin.hx@bytedance.com","subject":"Re: [PATCH v2 0/2] negotiator/default: avoid stack overflow","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2023-05-01T22:11:40Z","receivedAt":"2023-05-01T22:11:44Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Han Xin <hanxin.hx@bytedance.com> writes:\n\n> This series avoid stack overflow in negotiator/default.c and memory leak\n> in negotiator/skipping.c.\n>\n> Changes since v2:\n> * Rewrite the commit link in the typical format.\n> * Fix the incorrect check for the COMMON bit introduced in v2.\n\nI see Derrick pointed out a logic error during the review of v2 and\nthis round corrects it.  Is everybody happy with this iteration and\nconsiders it safe to merge it to 'next'?\n\nThanks.\n\n"},{"id":"476399","messageId":"9ad5f246-e21f-0a13-1a53-1ae3307c3f0e@github.com","threadId":"59640","inReplyTo":"xmqqildb3dnn.fsf@gitster.g","subject":"Re: [PATCH v2 0/2] negotiator/default: avoid stack overflow","fromName":"Derrick Stolee","fromEmail":"derrickstolee@github.com","sentAt":"2023-05-02T01:49:14Z","receivedAt":"2023-05-02T01:49:24Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 5/1/2023 6:11 PM, Junio C Hamano wrote:\n> Han Xin <hanxin.hx@bytedance.com> writes:\n> \n>> This series avoid stack overflow in negotiator/default.c and memory leak\n>> in negotiator/skipping.c.\n>>\n>> Changes since v2:\n>> * Rewrite the commit link in the typical format.\n>> * Fix the incorrect check for the COMMON bit introduced in v2.\n> \n> I see Derrick pointed out a logic error during the review of v2 and\n> this round corrects it.  Is everybody happy with this iteration and\n> considers it safe to merge it to 'next'?\n\nSorry for the lack of confirmation on that. I do think the v3\npatches are good (the cover letter says v2).\n\nThanks,\n-Stolee\n"},{"id":"476425","messageId":"xmqqv8ha20ln.fsf@gitster.g","threadId":"59640","inReplyTo":"9ad5f246-e21f-0a13-1a53-1ae3307c3f0e@github.com","subject":"Re: [PATCH v2 0/2] negotiator/default: avoid stack overflow","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2023-05-02T15:51:16Z","receivedAt":"2023-05-02T15:51:27Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Derrick Stolee <derrickstolee@github.com> writes:\n\n>>> Changes since v2:\n>>> * Rewrite the commit link in the typical format.\n>>> * Fix the incorrect check for the COMMON bit introduced in v2.\n>> \n>> I see Derrick pointed out a logic error during the review of v2 and\n>> this round corrects it.  Is everybody happy with this iteration and\n>> considers it safe to merge it to 'next'?\n>\n> Sorry for the lack of confirmation on that. I do think the v3\n> patches are good (the cover letter says v2).\n\nThanks.  Will mark the topic for 'next', then.\n"}]}