@@ -100,48 +100,63 @@ static struct rev_name *create_or_update_name(struct commit *commit,
return NULL;
}
-static void name_rev(struct commit *commit,
+static void name_rev(struct commit *start_commit,
const char *tip_name, timestamp_t taggerdate,
int from_tag)
{
- struct rev_name *name = get_commit_rev_name(commit);
- struct commit_list *parents;
- int parent_number = 1;
-
- for (parents = commit->parents;
- parents;
- parents = parents->next, parent_number++) {
- struct commit *parent = parents->item;
- const char *new_name;
- int generation, distance;
-
- parse_commit(parent);
- if (parent->date < cutoff)
- continue;
+ struct commit_list *list = NULL;
+
+ commit_list_insert(start_commit, &list);
+
+ while (list) {
+ struct commit *commit = pop_commit(&list);
+ struct rev_name *name = get_commit_rev_name(commit);
+ struct commit_list *parents, *new_parents = NULL;
+ struct commit_list **last_new_parent = &new_parents;
+ int parent_number = 1;
+
+ for (parents = commit->parents;
+ parents;
+ parents = parents->next, parent_number++) {
+ struct commit *parent = parents->item;
+ const char *new_name;
+ int generation, distance;
+
+ parse_commit(parent);
+ if (parent->date < cutoff)
+ continue;
- if (parent_number > 1) {
- size_t len;
+ if (parent_number > 1) {
+ size_t len;
+
+ strip_suffix(name->tip_name, "^0", &len);
+ if (name->generation > 0)
+ new_name = xstrfmt("%.*s~%d^%d",
+ (int)len,
+ name->tip_name,
+ name->generation,
+ parent_number);
+ else
+ new_name = xstrfmt("%.*s^%d", (int)len,
+ name->tip_name,
+ parent_number);
+ generation = 0;
+ distance = name->distance + MERGE_TRAVERSAL_WEIGHT;
+ } else {
+ new_name = name->tip_name;
+ generation = name->generation + 1;
+ distance = name->distance + 1;
+ }
- strip_suffix(tip_name, "^0", &len);
- if (name->generation > 0)
- new_name = xstrfmt("%.*s~%d^%d", (int)len, tip_name,
- name->generation,
- parent_number);
- else
- new_name = xstrfmt("%.*s^%d", (int)len, tip_name,
- parent_number);
- generation = 0;
- distance = name->distance + MERGE_TRAVERSAL_WEIGHT;
- } else {
- new_name = tip_name;
- generation = name->generation + 1;
- distance = name->distance + 1;
+ if (create_or_update_name(parent, new_name, taggerdate,
+ generation, distance,
+ from_tag))
+ last_new_parent = commit_list_append(parent,
+ last_new_parent);
}
- if (create_or_update_name(parent, new_name, taggerdate,
- generation, distance,
- from_tag))
- name_rev(parent, new_name, taggerdate, from_tag);
+ *last_new_parent = list;
+ list = new_parents;
}
}
@@ -379,7 +379,7 @@ test_expect_success 'describe tag object' '
test_i18ngrep "fatal: test-blob-1 is neither a commit nor blob" actual
'
-test_expect_failure ULIMIT_STACK_SIZE 'name-rev works in a deep repo' '
+test_expect_success ULIMIT_STACK_SIZE 'name-rev works in a deep repo' '
i=1 &&
while test $i -lt 8000
do
The name_rev() function calls itself recursively for each interesting parent of the commit it got as parameter, and, consequently, it can segfault when processing a deep history if it exhausts the available stack space. E.g. running 'git name-rev --all' and 'git name-rev HEAD~100000' in the gcc, gecko-dev, llvm, and WebKit repositories results in segfaults on my machine. Eliminate the recursion by inserting the interesting parents into a 'commit_list' and iteratating until the list becomes empty. Note that the order in which the parent commits are added to that list is important: they must be inserted at the beginning of the list, and their relative order must be kept as well, because otherwise performance suffers. The stacksize-limited test 'name-rev works in a deep repo' in 't6120-describe.sh' demonstrated this issue and expected failure. Now the recursion is gone, so flip it to expect success. Also gone are the dmesg entries logging the segfault of the git process on every execution of the test suite. Unfortunately, eliminating the recursion comes with a performance penaly: 'git name-rev --all' tends to be between 15-20% slower than before. Note that this slightly changes the order of lines in the output of 'git name-rev --all', usually swapping two lines every 35 lines in git.git or every 150 lines in linux.git. This shouldn't matter in practice, because the output has always been unordered anyway. This patch is best viewed with '--ignore-all-space'. Signed-off-by: SZEDER Gábor <szeder.dev@gmail.com> --- builtin/name-rev.c | 85 ++++++++++++++++++++++++++------------------- t/t6120-describe.sh | 2 +- 2 files changed, 51 insertions(+), 36 deletions(-)