diff options
author | Stephan Beyer <s-beyer@gmx.net> | 2016-04-10 15:19:03 +0200 |
---|---|---|
committer | Junio C Hamano <gitster@pobox.com> | 2016-04-15 12:27:29 -0700 |
commit | c1efbd980a6d23f7b80ae2e93a1ee63bcea2d70c (patch) | |
tree | 63667d9db0791221045857dfb35e53eded12b2e3 | |
parent | fee69a87e7937865dce79e0ee31ea24672291246 (diff) | |
download | git-c1efbd980a6d23f7b80ae2e93a1ee63bcea2d70c.tar.gz |
bisect: get rid of recursion in count_distance()
Large repositories with a huge amount of merge commits in the
bisection process could lead to stack overflows in git bisect.
In order to prevent this, this commit uses an *iterative* version
for counting the number of ancestors of a commit.
Signed-off-by: Stephan Beyer <s-beyer@gmx.net>
-rw-r--r-- | bisect.c | 55 |
1 files changed, 22 insertions, 33 deletions
@@ -26,33 +26,23 @@ static const char *term_good; /* Remember to update object flag allocation in object.h */ #define COUNTED (1u<<16) -/* - * This is a truly stupid algorithm, but it's only - * used for bisection, and we just don't care enough. - * - * We care just barely enough to avoid recursing for - * non-merge entries. - */ static int count_distance(struct commit_list *entry) { int nr = 0; + struct commit_list *todo = NULL; + commit_list_append(entry->item, &todo); - while (entry) { - struct commit *commit = entry->item; - struct commit_list *p; + while (todo) { + struct commit *commit = pop_commit(&todo); - if (commit->object.flags & (UNINTERESTING | COUNTED)) - break; - if (!(commit->object.flags & TREESAME)) - nr++; - commit->object.flags |= COUNTED; - p = commit->parents; - entry = p; - if (p) { - p = p->next; - while (p) { - nr += count_distance(p); - p = p->next; + if (!(commit->object.flags & (UNINTERESTING | COUNTED))) { + struct commit_list *p; + if (!(commit->object.flags & TREESAME)) + nr++; + commit->object.flags |= COUNTED; + + for (p = commit->parents; p; p = p->next) { + commit_list_insert(p->item, &todo); } } } @@ -287,7 +277,7 @@ static struct commit_list *do_find_bisection(struct commit_list *list, * can reach. So we do not have to run the expensive * count_distance() for single strand of pearls. * - * However, if you have more than one parents, you cannot + * However, if you have more than one parent, you cannot * just add their distance and one for yourself, since * they usually reach the same ancestor and you would * end up counting them twice that way. @@ -296,17 +286,16 @@ static struct commit_list *do_find_bisection(struct commit_list *list, * way, and then fill the blanks using cheaper algorithm. */ for (p = list; p; p = p->next) { - if (p->item->object.flags & UNINTERESTING) - continue; - if (weight(p) != -2) - continue; - weight_set(p, count_distance(p)); - clear_distance(list); + if (!(p->item->object.flags & UNINTERESTING) + && (weight(p) == -2)) { + weight_set(p, count_distance(p)); + clear_distance(list); - /* Does it happen to be at exactly half-way? */ - if (!find_all && halfway(p, nr)) - return p; - counted++; + /* Does it happen to be at exactly half-way? */ + if (!find_all && halfway(p, nr)) + return p; + counted++; + } } show_list("bisection 2 count_distance", counted, nr, list); |