{"thread":{"id":"36355","subject":"[PATCH] describe: rewrite name_rev() iteratively","startedAt":"2014-04-06T22:47:14Z","lastAt":"2014-04-08T18:50:47Z","messageCount":3,"participants":["Dragos Foianu","Eric Sunshine","Jeff King"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"238407","messageId":"1396824434-31672-1-git-send-email-dragos.foianu@gmail.com","threadId":"36355","inReplyTo":null,"subject":"[PATCH] describe: rewrite name_rev() iteratively","fromName":"Dragos Foianu","fromEmail":"dragos.foianu@gmail.com","sentAt":"2014-04-06T22:47:14Z","receivedAt":"2014-04-06T22:47:14Z","isPatch":true,"sender":{"key":"dragos.foianu@gmail.com","avatar":null},"body":"The \"git describe --contains\" command uses the name_rev() function which\nis currently a recursive function. This causes a Stack Overflow when the\nhistory is large enough.\n\nRewrite name_rev iteratively using a stack on the heap. This slightly\nreduces performance due to the extra operations on the heap, but the\nfunction no longer overflows the stack.\n\nReported-by: Sylvestre Ledru <sylvestre@mozilla.com>\nSigned-off-by: Dragos Foianu <dragos.foianu@gmail.com>\n---\n builtin/name-rev.c |  176 ++++++++++++++++++++++++++++++++++++++--------------\n 1 file changed, 128 insertions(+), 48 deletions(-)\n\ndiff --git a/builtin/name-rev.c b/builtin/name-rev.c\nindex c824d4e..5848d81 100644\n--- a/builtin/name-rev.c\n+++ b/builtin/name-rev.c\n@@ -19,66 +19,146 @@ static long cutoff = LONG_MAX;\n /* How many generations are maximally preferred over _one_ merge traversal? */\n #define MERGE_TRAVERSAL_WEIGHT 65535\n \n+typedef struct rev_data {\n+\tstruct commit *commit;\n+\tconst char *tip_name;\n+\tint generation;\n+\tint distance;\n+\tint deref;\n+} *rev_data;\n+\n+typedef struct rev_stack {\n+\tstruct rev_data *rev;\n+\tstruct rev_stack *next;\n+} *rev_stack;\n+\n+static void stack_push(rev_stack *stack, rev_data data) {\n+\trev_stack new_node = xmalloc(sizeof(*new_node));\n+\n+\tnew_node->rev = data;\n+\tnew_node->next = *stack;\n+\t*stack = new_node;\n+}\n+\n+static void stack_push_end(rev_stack *stack, rev_data data) {\n+\trev_stack new_node = xmalloc(sizeof(*new_node));\n+\n+\twhile (*stack != NULL)\n+\t\tstack = &(*stack)->next;\n+\tnew_node->rev = data;\n+\tnew_node->next = *stack;\n+\t*stack = new_node;\n+}\n+\n+static rev_data stack_pop(rev_stack *stack) {\n+\trev_stack next = (*stack)->next;\n+\trev_data rev = (*stack)->rev;\n+\tfree(*stack);\n+\n+\t*stack = next;\n+\treturn rev;\n+}\n+\n+static rev_data make_rev_data(struct commit *commit,\n+\t\tconst char* tip_name, int generation, int distance,\n+\t\tint deref)\n+{\n+\trev_data data = xmalloc(sizeof(*data));\n+\n+\tdata->commit = commit;\n+\tdata->tip_name = tip_name;\n+\tdata->generation = generation;\n+\tdata->distance = distance;\n+\tdata->deref = deref;\n+\n+\treturn data;\n+}\n+\n static void name_rev(struct commit *commit,\n \t\tconst char *tip_name, int generation, int distance,\n \t\tint deref)\n {\n-\tstruct rev_name *name = (struct rev_name *)commit->util;\n-\tstruct commit_list *parents;\n-\tint parent_number = 1;\n+\trev_stack stack = NULL;\n+\trev_data data, next_rev;\n \n-\tparse_commit(commit);\n+\tdata = make_rev_data(commit, tip_name, generation, distance, deref);\n+\tstack_push(&stack, data);\n \n-\tif (commit->date < cutoff)\n-\t\treturn;\n+\twhile (stack != NULL) {\n+\t\trev_data rev = stack_pop(&stack);\n \n-\tif (deref) {\n-\t\tchar *new_name = xmalloc(strlen(tip_name)+3);\n-\t\tstrcpy(new_name, tip_name);\n-\t\tstrcat(new_name, \"^0\");\n-\t\ttip_name = new_name;\n+\t\tstruct rev_name *name = (struct rev_name *) rev->commit->util;\n+\t\tstruct commit_list *parents;\n+\t\tint parent_number = 1;\n \n-\t\tif (generation)\n-\t\t\tdie(\"generation: %d, but deref?\", generation);\n-\t}\n+\t\tparse_commit(rev->commit);\n+\n+\t\tif (rev->commit->date < cutoff)\n+\t\t\tcontinue;\n+\n+\t\tif (rev->deref) {\n+\t\t\tchar *new_name = xmalloc(strlen(rev->tip_name) + 3);\n+\t\t\tstrcpy(new_name, rev->tip_name);\n+\t\t\tstrcat(new_name, \"^0\");\n+\t\t\trev->tip_name = new_name;\n \n-\tif (name == NULL) {\n-\t\tname = xmalloc(sizeof(rev_name));\n-\t\tcommit->util = name;\n-\t\tgoto copy_data;\n-\t} else if (name->distance > distance) {\n+\t\t\tif (rev->generation)\n+\t\t\t\tdie(\"generation: %d, but deref?\",\n+\t\t\t\t\trev->generation);\n+\t\t}\n+\n+\t\tif (name == NULL) {\n+\t\t\tname = xmalloc(sizeof(rev_name));\n+\t\t\trev->commit->util = name;\n+\t\t\tgoto copy_data;\n+\t\t} else if (name->distance > rev->distance) {\n copy_data:\n-\t\tname->tip_name = tip_name;\n-\t\tname->generation = generation;\n-\t\tname->distance = distance;\n-\t} else\n-\t\treturn;\n-\n-\tfor (parents = commit->parents;\n-\t\t\tparents;\n-\t\t\tparents = parents->next, parent_number++) {\n-\t\tif (parent_number > 1) {\n-\t\t\tint len = strlen(tip_name);\n-\t\t\tchar *new_name = xmalloc(len +\n-\t\t\t\t1 + decimal_length(generation) +  /* ~<n> */\n-\t\t\t\t1 + 2 +\t\t\t\t  /* ^NN */\n-\t\t\t\t1);\n-\n-\t\t\tif (len > 2 && !strcmp(tip_name + len - 2, \"^0\"))\n-\t\t\t\tlen -= 2;\n-\t\t\tif (generation > 0)\n-\t\t\t\tsprintf(new_name, \"%.*s~%d^%d\", len, tip_name,\n-\t\t\t\t\t\tgeneration, parent_number);\n-\t\t\telse\n-\t\t\t\tsprintf(new_name, \"%.*s^%d\", len, tip_name,\n-\t\t\t\t\t\tparent_number);\n+\t\t\tname->tip_name = rev->tip_name;\n+\t\t\tname->generation = rev->generation;\n+\t\t\tname->distance = rev->distance;\n+\t\t} else\n+\t\t\tcontinue;\n \n-\t\t\tname_rev(parents->item, new_name, 0,\n-\t\t\t\tdistance + MERGE_TRAVERSAL_WEIGHT, 0);\n-\t\t} else {\n-\t\t\tname_rev(parents->item, tip_name, generation + 1,\n-\t\t\t\tdistance + 1, 0);\n+\t\tfor (parents = rev->commit->parents;\n+\t\t\t\tparents;\n+\t\t\t\tparents = parents->next, parent_number++) {\n+\t\t\tif (parent_number > 1) {\n+\t\t\t\tint len = strlen(rev->tip_name);\n+\t\t\t\tchar *new_name = xmalloc(len +\n+\t\t\t\t\t/* ~<n> */\n+\t\t\t\t\t1 + decimal_length(rev->generation) +\n+\t\t\t\t\t/* ^NN */\n+\t\t\t\t\t1 + 2 +\n+\t\t\t\t\t1);\n+\n+\t\t\t\tif (len > 2 &&\n+\t\t\t\t\t!strcmp(rev->tip_name + len - 2, \"^0\"))\n+\t\t\t\t\tlen -= 2;\n+\n+\t\t\t\tif (rev->generation > 0)\n+\t\t\t\t\tsprintf(new_name, \"%.*s~%d^%d\", len,\n+\t\t\t\t\t\trev->tip_name, rev->generation,\n+\t\t\t\t\t\tparent_number);\n+\t\t\t\telse\n+\t\t\t\t\tsprintf(new_name, \"%.*s^%d\", len,\n+\t\t\t\t\t\trev->tip_name, parent_number);\n+\n+\t\t\t\tnext_rev = make_rev_data(parents->item,\n+\t\t\t\t\tnew_name, 0,\n+\t\t\t\t\trev->distance + MERGE_TRAVERSAL_WEIGHT,\n+\t\t\t\t\t0);\n+\n+\t\t\t\tstack_push_end(&stack, next_rev);\n+\t\t\t} else {\n+\t\t\t\tnext_rev = make_rev_data(parents->item,\n+\t\t\t\t\trev->tip_name, rev->generation + 1,\n+\t\t\t\t\trev->distance + 1, 0);\n+\n+\t\t\t\tstack_push(&stack, next_rev);\n+\t\t\t}\n \t\t}\n+\n+\t\tfree(rev);\n \t}\n }\n \n-- \n1.7.10.4\n"},{"id":"238525","messageId":"CAPig+cR+gVSU+kthiZc3pwEjBDfeu_Do0NTD3Cw=xPtMUDY8Kw@mail.gmail.com","threadId":"36355","inReplyTo":"1396824434-31672-1-git-send-email-dragos.foianu@gmail.com","subject":"Re: [PATCH] describe: rewrite name_rev() iteratively","fromName":"Eric Sunshine","fromEmail":"sunshine@sunshineco.com","sentAt":"2014-04-08T07:41:17Z","receivedAt":"2014-04-08T07:41:17Z","isPatch":true,"sender":{"key":"sunshine@sunshineco.com","avatar":"https://avatars.githubusercontent.com/u/163641?v=4"},"body":"[cc: Sylvestre Ledru <sylvestre@mozilla.com>]\n\nOn Sun, Apr 6, 2014 at 6:47 PM, Dragos Foianu <dragos.foianu@gmail.com> wrote:\n> The \"git describe --contains\" command uses the name_rev() function which\n> is currently a recursive function. This causes a Stack Overflow when the\n> history is large enough.\n\nNo need to capitalize \"stack overflow\".\n\nIt might be helpful if you provide a link to the original problem\nreport by Sylvestre [1] for context.\n\n[1]: http://thread.gmane.org/gmane.comp.version-control.git/244430\n\n> Rewrite name_rev iteratively using a stack on the heap. This slightly\n> reduces performance due to the extra operations on the heap, but the\n> function no longer overflows the stack.\n>\n> Reported-by: Sylvestre Ledru <sylvestre@mozilla.com>\n\nIt's a good idea to cc: the original reporter of the problem so that\nhe can test the fix. (And, generally speaking, it's good etiquette to\ncc: people who commented on the issue.)\n\n> Signed-off-by: Dragos Foianu <dragos.foianu@gmail.com>\n> ---\n>  builtin/name-rev.c |  176 ++++++++++++++++++++++++++++++++++++++--------------\n>  1 file changed, 128 insertions(+), 48 deletions(-)\n>\n> diff --git a/builtin/name-rev.c b/builtin/name-rev.c\n> index c824d4e..5848d81 100644\n> --- a/builtin/name-rev.c\n> +++ b/builtin/name-rev.c\n> @@ -19,66 +19,146 @@ static long cutoff = LONG_MAX;\n>  /* How many generations are maximally preferred over _one_ merge traversal? */\n>  #define MERGE_TRAVERSAL_WEIGHT 65535\n>\n> +typedef struct rev_data {\n\nOn this project, \"typedef struct\" is almost universally avoided. Just\nsay \"struct rev_data\" when needed.\n\n> +       struct commit *commit;\n> +       const char *tip_name;\n> +       int generation;\n> +       int distance;\n> +       int deref;\n\n'deref' may be true only for the initial call to name_rev(); all\nrecursive invocations unconditionally pass false, so including it in\nthe structure is superfluous and potentially confusing for readers.\n\nMore below.\n\n> +} *rev_data;\n> +\n> +typedef struct rev_stack {\n> +       struct rev_data *rev;\n> +       struct rev_stack *next;\n> +} *rev_stack;\n> +\n> +static void stack_push(rev_stack *stack, rev_data data) {\n> +       rev_stack new_node = xmalloc(sizeof(*new_node));\n> +\n> +       new_node->rev = data;\n> +       new_node->next = *stack;\n> +       *stack = new_node;\n> +}\n> +\n> +static void stack_push_end(rev_stack *stack, rev_data data) {\n> +       rev_stack new_node = xmalloc(sizeof(*new_node));\n> +\n> +       while (*stack != NULL)\n> +               stack = &(*stack)->next;\n> +       new_node->rev = data;\n> +       new_node->next = *stack;\n> +       *stack = new_node;\n> +}\n> +\n> +static rev_data stack_pop(rev_stack *stack) {\n> +       rev_stack next = (*stack)->next;\n> +       rev_data rev = (*stack)->rev;\n> +       free(*stack);\n> +\n> +       *stack = next;\n> +       return rev;\n> +}\n> +\n> +static rev_data make_rev_data(struct commit *commit,\n> +               const char* tip_name, int generation, int distance,\n> +               int deref)\n> +{\n> +       rev_data data = xmalloc(sizeof(*data));\n> +\n> +       data->commit = commit;\n> +       data->tip_name = tip_name;\n> +       data->generation = generation;\n> +       data->distance = distance;\n> +       data->deref = deref;\n> +\n> +       return data;\n> +}\n> +\n>  static void name_rev(struct commit *commit,\n>                 const char *tip_name, int generation, int distance,\n>                 int deref)\n>  {\n> -       struct rev_name *name = (struct rev_name *)commit->util;\n> -       struct commit_list *parents;\n> -       int parent_number = 1;\n> +       rev_stack stack = NULL;\n> +       rev_data data, next_rev;\n>\n> -       parse_commit(commit);\n> +       data = make_rev_data(commit, tip_name, generation, distance, deref);\n> +       stack_push(&stack, data);\n>\n> -       if (commit->date < cutoff)\n> -               return;\n> +       while (stack != NULL) {\n> +               rev_data rev = stack_pop(&stack);\n>\n> -       if (deref) {\n> -               char *new_name = xmalloc(strlen(tip_name)+3);\n> -               strcpy(new_name, tip_name);\n> -               strcat(new_name, \"^0\");\n> -               tip_name = new_name;\n> +               struct rev_name *name = (struct rev_name *) rev->commit->util;\n> +               struct commit_list *parents;\n> +               int parent_number = 1;\n>\n> -               if (generation)\n> -                       die(\"generation: %d, but deref?\", generation);\n> -       }\n> +               parse_commit(rev->commit);\n> +\n> +               if (rev->commit->date < cutoff)\n> +                       continue;\n> +\n> +               if (rev->deref) {\n> +                       char *new_name = xmalloc(strlen(rev->tip_name) + 3);\n> +                       strcpy(new_name, rev->tip_name);\n> +                       strcat(new_name, \"^0\");\n> +                       rev->tip_name = new_name;\n\nAs mentioned above, 'deref' may be true only upon the first call;\nrecursive invocations always set it to false, so the entire 'if\n(deref)' conditional can be promoted out of your 'while (stack !=\nNULL)' loop.\n\n(In fact, this deref processing could be promoted out of this function\naltogether since its only ever done for the first commit visited, but\nsuch a change is likely fodder for a separate cleanup patch.)\n\nMore below.\n\n> -       if (name == NULL) {\n> -               name = xmalloc(sizeof(rev_name));\n> -               commit->util = name;\n> -               goto copy_data;\n> -       } else if (name->distance > distance) {\n> +                       if (rev->generation)\n> +                               die(\"generation: %d, but deref?\",\n> +                                       rev->generation);\n> +               }\n> +\n> +               if (name == NULL) {\n> +                       name = xmalloc(sizeof(rev_name));\n> +                       rev->commit->util = name;\n> +                       goto copy_data;\n> +               } else if (name->distance > rev->distance) {\n>  copy_data:\n> -               name->tip_name = tip_name;\n> -               name->generation = generation;\n> -               name->distance = distance;\n> -       } else\n> -               return;\n> -\n> -       for (parents = commit->parents;\n> -                       parents;\n> -                       parents = parents->next, parent_number++) {\n> -               if (parent_number > 1) {\n> -                       int len = strlen(tip_name);\n> -                       char *new_name = xmalloc(len +\n> -                               1 + decimal_length(generation) +  /* ~<n> */\n> -                               1 + 2 +                           /* ^NN */\n> -                               1);\n> -\n> -                       if (len > 2 && !strcmp(tip_name + len - 2, \"^0\"))\n> -                               len -= 2;\n> -                       if (generation > 0)\n> -                               sprintf(new_name, \"%.*s~%d^%d\", len, tip_name,\n> -                                               generation, parent_number);\n> -                       else\n> -                               sprintf(new_name, \"%.*s^%d\", len, tip_name,\n> -                                               parent_number);\n> +                       name->tip_name = rev->tip_name;\n> +                       name->generation = rev->generation;\n> +                       name->distance = rev->distance;\n> +               } else\n> +                       continue;\n>\n> -                       name_rev(parents->item, new_name, 0,\n> -                               distance + MERGE_TRAVERSAL_WEIGHT, 0);\n> -               } else {\n> -                       name_rev(parents->item, tip_name, generation + 1,\n> -                               distance + 1, 0);\n> +               for (parents = rev->commit->parents;\n> +                               parents;\n> +                               parents = parents->next, parent_number++) {\n> +                       if (parent_number > 1) {\n> +                               int len = strlen(rev->tip_name);\n> +                               char *new_name = xmalloc(len +\n> +                                       /* ~<n> */\n> +                                       1 + decimal_length(rev->generation) +\n> +                                       /* ^NN */\n> +                                       1 + 2 +\n> +                                       1);\n> +\n> +                               if (len > 2 &&\n> +                                       !strcmp(rev->tip_name + len - 2, \"^0\"))\n> +                                       len -= 2;\n> +\n> +                               if (rev->generation > 0)\n> +                                       sprintf(new_name, \"%.*s~%d^%d\", len,\n> +                                               rev->tip_name, rev->generation,\n> +                                               parent_number);\n> +                               else\n> +                                       sprintf(new_name, \"%.*s^%d\", len,\n> +                                               rev->tip_name, parent_number);\n> +\n> +                               next_rev = make_rev_data(parents->item,\n> +                                       new_name, 0,\n> +                                       rev->distance + MERGE_TRAVERSAL_WEIGHT,\n> +                                       0);\n> +\n> +                               stack_push_end(&stack, next_rev);\n> +                       } else {\n> +                               next_rev = make_rev_data(parents->item,\n> +                                       rev->tip_name, rev->generation + 1,\n> +                                       rev->distance + 1, 0);\n> +\n> +                               stack_push(&stack, next_rev);\n> +                       }\n\nThis logic changes the order in which the commits are visited. Given a\nhistory, such as:\n\n    --D--B---A\n    --E-/   /\n    --F--C-/\n    --G-/\n\nwhere A's parents are (B,C), B's parents are (D,E), and C's parents\nare (F,G), the original code traverses commits in this order:\n\n    A B D E C F G\n\nbut, with your patch, they are traversed in this order:\n\n    A B D C F E G\n\n>                 }\n> +\n> +               free(rev);\n>         }\n>  }\n>\n> --\n> 1.7.10.4\n"},{"id":"238555","messageId":"20140408185047.GA7073@sigill.intra.peff.net","threadId":"36355","inReplyTo":"1396824434-31672-1-git-send-email-dragos.foianu@gmail.com","subject":"Re: [PATCH] describe: rewrite name_rev() iteratively","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2014-04-08T18:50:47Z","receivedAt":"2014-04-08T18:50:47Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Apr 07, 2014 at 01:47:14AM +0300, Dragos Foianu wrote:\n\n> The \"git describe --contains\" command uses the name_rev() function which\n> is currently a recursive function. This causes a Stack Overflow when the\n> history is large enough.\n> \n> Rewrite name_rev iteratively using a stack on the heap. This slightly\n> reduces performance due to the extra operations on the heap, but the\n> function no longer overflows the stack.\n\nYou can avoid the heap overhead by using an array for your stack, and\nonly resizing it when necessary. Like this:\n\n    struct rev_stack {\n            int nr, alloc;\n            struct rev_data *data;\n    };\n\n    static struct rev_data *rev_stack_push(struct rev_stack *stack)\n    {\n            ALLOC_GROW(stack->data, stack->nr + 1, stack->alloc);\n            return &stack->data[stack->nr++];\n    }\n\n    static void rev_stack_pop(struct rev_stack *stack)\n    {\n            stack->nr--;\n    }\n\n    static void rev_stack_init(struct rev_stack *stack)\n    {\n            stack->nr = stack->alloc = 0;\n            stack->data = NULL;\n    }\n\n    static void rev_stack_release(struct rev_stack *stack)\n    {\n            free(stack->data);\n            rev_stack_init(stack);\n    }\n\nUsage would be something like:\n\n    struct rev_data *data = rev_stack_push(&stack);\n    data->commit = commit;\n    data->tip_name = tip_name;\n    ...\n\nIOW, you push first to allocate the space, and then do your\nmake_rev_data, rather than the other way around.\n\nThe downside is that your allocation is always as big as the deepest\nrecursion so far, so you hold on to the memory a little longer than\nnecessary. I think that's a good tradeoff versus an extra malloc() for\nevery commit.\n\n-Peff\n"}]}