Re: [PATCH v2 00/13] name-rev: eliminate recursion

> 'git name-rev' is implemented using a recursive algorithm, and,
> consequently, it can segfault in deep histories (e.g. WebKit), and
> thanks to a test case demonstrating this limitation every test run
> results in a dmesg entry logging the segfaulting git process.
>
> This patch series eliminates the recursion.
>
> Patches 1-5 are while-at-it cleanups I noticed on the way, and patch 6
> improves test coverage.  Patches 7-11 are preparatory refactorings
> that are supposed to make this series easier to follow, and make patch
> 12, the one finally eliminating the recursion, somewhat shorter, and
> even much shorter when viewed with '--ignore-all-space'.  Patch 13
> cleans up after those preparatory steps.
>
> Changes since v1:
>
>   - Patch 12 now eliminates the recursion using a LIFO 'prio_queue'
>     instead of a 'commit_list' to avoid any performance penalty.
>
>   - Commit message updates, clarifications, typofixes, missing
>     signoffs, etc., most notably in patches 6 and 12.
>
>   - Updated ASCII art history graphs.
>
>   - Replaced the strbuf_suffix() cleanup in patch 3 with René's
>     suggestion; now that patch needs his signoff.
>
>   - Dropped the last two patches plugging memory leaks; René's plan
>     to clean up memory ownership looked more promising, and that
>     would make these two dropped patches moot anyway.
>
> v1: https://public-inbox.org/git/20190919214712.7348-1-szeder.dev@gmail.com/T/#u
>
> René Scharfe (1):
>   name-rev: use strbuf_strip_suffix() in get_rev_name()
>
> SZEDER Gábor (12):
>   t6120-describe: correct test repo history graph in comment
>   t6120-describe: modernize the 'check_describe' helper
>   name-rev: avoid unnecessary cast in name_ref()
>   name-rev: use sizeof(*ptr) instead of sizeof(type) in allocation
>   t6120: add a test to cover inner conditions in 'git name-rev's
>     name_rev()
>   name-rev: extract creating/updating a 'struct name_rev' into a helper
>   name-rev: pull out deref handling from the recursion
>   name-rev: restructure parsing commits and applying date cutoff
>   name-rev: restructure creating/updating 'struct rev_name' instances
>   name-rev: drop name_rev()'s 'generation' and 'distance' parameters
>   name-rev: eliminate recursion in name_rev()
>   name-rev: cleanup name_ref()
>
>  builtin/name-rev.c  | 147 +++++++++++++++++++++++++++++---------------
>  t/t6120-describe.sh |  72 +++++++++++++++++-----
>  2 files changed, 153 insertions(+), 66 deletions(-)
>
> Range-diff:
>  1:  673da20e3d !  1:  8d70ed050d t6120-describe: correct test repo history graph in comment
>     @@ t/t6120-describe.sh
>      -test_description='test describe
>      +test_description='test describe'
>      +
>     -+#       ,---o----o----o-----.
>     -+#      /   D,R   e           \
>     -+#  o--o-----o-------------o---o----x
>     -+#      \    B            /
>     -+#       `---o----o----o-'
>     -+#                A    c
>     ++#  o---o-----o----o----o-------o----x
>     ++#       \   D,R   e           /
>     ++#        \---o-------------o-'
>     ++#         \  B            /
>     ++#          `-o----o----o-'
>     ++#                 A    c
>     ++#
>     ++# First parent of a merge commit is on the same line, second parent below.
>
>      -                       B
>      -        .--------------o----o----o----x
>  2:  05df899693 =  2:  3720b6859d t6120-describe: modernize the 'check_describe' helper
>  3:  7b0227cfea !  3:  ad2f2eee68 name-rev: use strip_suffix() in get_rev_name()
>     @@
>       ## Metadata ##
>     -Author: SZEDER Gábor <szeder.dev@gmail.com>
>     +Author: René Scharfe <l.s.r@web.de>
>
>       ## Commit message ##
>     -    name-rev: use strip_suffix() in get_rev_name()
>     +    name-rev: use strbuf_strip_suffix() in get_rev_name()
>
>     -    Use strip_suffix() instead of open-coding it, making the code more
>     -    idiomatic.
>     +    get_name_rev() basically open-codes strip_suffix() before adding a
>     +    string to a strbuf.
>
>     +    Let's use the strbuf right from the beginning, i.e. add the whole
>     +    string to the strbuf and then use strbuf_strip_suffix(), making the
>     +    code more idiomatic.
>     +
>     +    [TODO: René's signoff!]
>          Signed-off-by: SZEDER Gábor <szeder.dev@gmail.com>
>
>       ## builtin/name-rev.c ##
>     @@ builtin/name-rev.c: static const char *get_rev_name(const struct object *o, stru
>      -		int len = strlen(n->tip_name);
>      -		if (len > 2 && !strcmp(n->tip_name + len - 2, "^0"))
>      -			len -= 2;
>     -+		size_t len;
>     -+		strip_suffix(n->tip_name, "^0", &len);
>       		strbuf_reset(buf);
>      -		strbuf_addf(buf, "%.*s~%d", len, n->tip_name, n->generation);
>     -+		strbuf_addf(buf, "%.*s~%d", (int) len, n->tip_name,
>     -+			    n->generation);
>     ++		strbuf_addstr(buf, n->tip_name);
>     ++		strbuf_strip_suffix(buf, "^0");
>     ++		strbuf_addf(buf, "~%d", n->generation);
>       		return buf->buf;
>       	}
>       }
>  4:  40faecdc2a =  4:  c86a2ae2d0 name-rev: avoid unnecessary cast in name_ref()
>  5:  c71df3dadf =  5:  4fc960cc05 name-rev: use sizeof(*ptr) instead of sizeof(type) in allocation
>  6:  1dcb76072f !  6:  1493cb4484 t6120: add a test to cover inner conditions in 'git name-rev's name_rev()
>     @@ Commit message
>          looks like this:
>
>            if (parent_number > 1) {
>     -        if (generation > 0)
>     -          // do stuff #1
>     -        else
>     -          // do stuff #2
>     +          if (generation > 0)
>     +              // branch #1
>     +              new_name = ...
>     +          else
>     +              // branch #2
>     +              new_name = ...
>     +          name_rev(parent, new_name, ...);
>            } else {
>     -         // do stuff #3
>     +          // branch #3
>     +          name_rev(...);
>            }
>
>          These conditions are not covered properly in the test suite.  As far
>     @@ Commit message
>          command's output, because the repository used in that test script
>          contains several branches and tags pointing somewhere into the middle
>          of the commit DAG, and thus result in a better name for the
>     -    to-be-named commit.  In an early version of this patch series I
>     -    managed to mess up those conditions (every single one of them at
>     -    once!), but the whole test suite still passed successfully.
>     +    to-be-named commit.  This can hide bugs: e.g. by replacing the
>     +    'new_name' parameter of the first recursive name_rev() call with
>     +    'tip_name' (effectively making both branch #1 and #2 a noop) 'git
>     +    name-rev --all' shows thousands of bogus names in the Git repository,
>     +    but the whole test suite still passes successfully.  In an early
>     +    version of a later patch in this series I managed to mess up all three
>     +    branches (at once!), but the test suite still passed.
>
>          So add a new test case that operates on the following history:
>
>     -        -----------master
>     -       /          /
>     -      A----------M2
>     -       \        /
>     -        \---M1-C
>     -         \ /
>     -          B
>     +      A--------------master
>     +       \            /
>     +        \----------M2
>     +         \        /
>     +          \---M1-C
>     +           \ /
>     +            B
>
>     -    and names the commit 'B', where:
>     +    and names the commit 'B' to make sure that all three branches are
>     +    crucial to determine 'B's name:
>
>     -      - The merge commit at master makes sure that the 'do stuff #3'
>     -        affects the final name.
>     +      - There is only a single ref, so all names are based on 'master',
>     +        without any undesired interference from other refs.
>
>     -      - The merge commit M2 make sure that the 'do stuff #1' part
>     -        affects the final name.
>     +      - Each time name_rev() follows the second parent of a merge commit,
>     +        it appends "^2" to the name.  Following 'master's second parent
>     +        right at the start ensures that all commits on the ancestry path
>     +        from 'master' to 'B' have a different base name from the original
>     +        'tip_name' of the very first name_rev() invocation.  Currently,
>     +        while name_rev() is recursive, it doesn't matter, but it will be
>     +        necessary to properly cover all three branches after the recursion
>     +        is eliminated later in this series.
>
>     -      - And M1 makes sure that the 'do stuff #2' part affects the final
>     -        name.
>     +      - Following 'M2's second parent makes sure that branch #2 (i.e. when
>     +        'generation = 0') affects 'B's name.
>     +
>     +      - Following the only parent of the non-merge commit 'C' ensures that
>     +        branch #3 affects 'B's name, and that it increments 'generation'.
>     +
>     +      - Coming from 'C' 'generation' is 1, thus following 'M1's second
>     +        parent makes sure that branch #1 affects 'B's name.
>
>          Signed-off-by: SZEDER Gábor <szeder.dev@gmail.com>
>
>       ## t/t6120-describe.sh ##
>     -@@ t/t6120-describe.sh: test_expect_success 'describe complains about missing object' '
>     - 	test_must_fail git describe $ZERO_OID
>     +@@ t/t6120-describe.sh: test_expect_success 'name-rev a rev shortly after epoch' '
>     + 	test_cmp expect actual
>       '
>
>     -+#   -----------master
>     -+#  /          /
>     -+# A----------M2
>     -+#  \        /
>     -+#   \---M1-C
>     -+#    \ /
>     -+#     B
>     -+test_expect_success 'test' '
>     ++# A--------------master
>     ++#  \            /
>     ++#   \----------M2
>     ++#    \        /
>     ++#     \---M1-C
>     ++#      \ /
>     ++#       B
>     ++test_expect_success 'name-rev covers all conditions while looking at parents' '
>      +	git init repo &&
>      +	(
>      +		cd repo &&
>     @@ t/t6120-describe.sh: test_expect_success 'describe complains about missing objec
>      +		git checkout master &&
>      +		git merge --no-ff HEAD@{1} &&
>      +
>     -+		git log --graph --oneline &&
>     -+
>      +		echo "$B master^2^2~1^2" >expect &&
>      +		git name-rev $B >actual &&
>      +
>  7:  bdd8378b06 =  7:  fc842e578b name-rev: extract creating/updating a 'struct name_rev' into a helper
>  8:  ce21c351f9 !  8:  7f182503e2 name-rev: pull out deref handling from the recursion
>     @@ Commit message
>          Extract this condition from the recursion into name_rev()'s caller and
>          drop the function's 'deref' parameter.  This makes eliminating the
>          recursion a bit easier to follow, and it will be moved back into
>     -    name_rev() after the recursion is elminated.
>     +    name_rev() after the recursion is eliminated.
>
>          Furthermore, drop the condition that die()s when both 'deref' and
>          'generation' are non-null (which should have been a BUG() to begin
>     @@ Commit message
>
>          Note that this change reintroduces the memory leak that was plugged in
>          in commit 5308224633 (name-rev: avoid leaking memory in the `deref`
>     -    case, 2017-05-04), but a later patch in this series will plug it in
>     -    again.
>     +    case, 2017-05-04), but a later patch (name-rev: restructure
>     +    creating/updating 'struct rev_name' instances) in this series will
>     +    plug it in again.
>
>          Signed-off-by: SZEDER Gábor <szeder.dev@gmail.com>
>
>  9:  c8acc6b597 !  9:  0cdd40b75b name-rev: restructure parsing commits and applying date cutoff
>     @@ Commit message
>          name_rev() and name_rev() itself as it iterates over the parent
>          commits.
>
>     -    This makes eliminating the recursion a bit easier to follow, and it
>     -    will be moved back to name_rev() after the recursion is eliminated.
>     +    This makes eliminating the recursion a bit easier to follow, and the
>     +    condition moved to name_ref() will be moved back to name_rev() after
>     +    the recursion is eliminated.
>
>          Signed-off-by: SZEDER Gábor <szeder.dev@gmail.com>
>
> 10:  c731f27158 ! 10:  e1733e3c56 name-rev: restructure creating/updating 'struct rev_name' instances
>     @@ Commit message
>          At the beginning of the recursive name_rev() function it creates a new
>          'struct rev_name' instance for each previously unvisited commit or, if
>          this visit results in better name for an already visited commit, then
>     -    updates the 'struct rev_name' instance attached to to the commit, or
>     +    updates the 'struct rev_name' instance attached to the commit, or
>          returns early.
>
>          Restructure this so it's caller creates or updates the 'struct
>     @@ Commit message
>          parameter, i.e. both name_ref() before calling name_rev() and
>          name_rev() itself as it iterates over the parent commits.
>
>     -    This makes eliminating the recursion a bit easier to follow, and it
>     -    will be moved back to name_rev() after the recursion is eliminated.
>     +    This makes eliminating the recursion a bit easier to follow, and the
>     +    condition moved to name_ref() will be moved back to name_rev() after
>     +    the recursion is eliminated.
>
>          This change also plugs the memory leak that was temporarily unplugged
>          in the earlier "name-rev: pull out deref handling from the recursion"
> 11:  ba14bde230 ! 11:  bd6e2e6d87 name-rev: drop name_rev()'s 'generation' and 'distance' parameters
>     @@ Commit message
>          'taggerdate' and 'from_tag' parameters as well, but those parameters
>          will be necessary later, after the recursion is eliminated.
>
>     -    Drop name_rev()'s 'generation' and 'distance' parameters.
>     +    Signed-off-by: SZEDER Gábor <szeder.dev@gmail.com>
>
>       ## builtin/name-rev.c ##
>      @@ builtin/name-rev.c: static struct rev_name *create_or_update_name(struct commit *commit,
> 12:  2d03ac11f3 ! 12:  0cf63c6d64 name-rev: eliminate recursion in name_rev()
>     @@ Commit message
>          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.
>     +    results in segfaults on my machine ('ulimit -s' reports 8192kB of
>     +    stack size limit), and nowadays the former segfaults in the Linux repo
>     +    as well (it reached the necessasry depth sometime between v5.3-rc4 and
>     +    -rc5).
>
>          Eliminate the recursion by inserting the interesting parents into a
>     -    'commit_list' and iteratating until the list becomes empty.
>     +    LIFO 'prio_queue' [1] and iterating until the queue 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.
>     +    Note that the parent commits must be added in reverse order to the
>     +    LIFO 'prio_queue', so their relative order is preserved during
>     +    processing, i.e. the first parent should come out first from the
>     +    queue, because otherwise performance greatly suffers on mergy
>     +    histories [2].
>
>          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.
>     +    the recursion is gone, so flip it to expect success.  Also gone are
>     +    the dmesg entries logging the segfault of that segfaulting 'git
>     +    name-rev' process on every execution of the test suite.
>
>          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
>     @@ Commit message
>
>          This patch is best viewed with '--ignore-all-space'.
>
>     +    [1] Early versions of this patch used a 'commit_list', resulting in
>     +        ~15% performance penalty for 'git name-rev --all' in 'linux.git',
>     +        presumably because of the memory allocation and release for each
>     +        insertion and removal. Using a LIFO 'prio_queue' has basically no
>     +        effect on performance.
>     +
>     +    [2] We prefer shorter names, i.e. 'v0.1~234' is preferred over
>     +        'v0.1^2~5', meaning that usually following the first parent of a
>     +        merge results in the best name for its ancestors.  So when later
>     +        we follow the remaining parent(s) of a merge, and reach an already
>     +        named commit, then we usually find that we can't give that commit
>     +        a better name, and thus we don't have to visit any of its
>     +        ancestors again.
>     +
>     +        OTOH, if we were to follow the Nth parent of the merge first, then
>     +        the name of all its ancestors would include a corresponding '^N'.
>     +        Those are not the best names for those commits, so when later we
>     +        reach an already named commit following the first parent of that
>     +        merge, then we would have to update the name of that commit and
>     +        the names of all of its ancestors as well.  Consequently, we would
>     +        have to visit many commits several times, resulting in a
>     +        significant slowdown.
>     +
>          Signed-off-by: SZEDER Gábor <szeder.dev@gmail.com>
>
>       ## builtin/name-rev.c ##
>     +@@
>     + #include "tag.h"
>     + #include "refs.h"
>     + #include "parse-options.h"
>     ++#include "prio-queue.h"
>     + #include "sha1-lookup.h"
>     + #include "commit-slab.h"
>     +
>      @@ builtin/name-rev.c: static struct rev_name *create_or_update_name(struct commit *commit,
>       		return NULL;
>       }
>     @@ builtin/name-rev.c: static struct rev_name *create_or_update_name(struct commit
>      -		parse_commit(parent);
>      -		if (parent->date < cutoff)
>      -			continue;
>     -+	struct commit_list *list = NULL;
>     ++	struct prio_queue queue;
>     ++	struct commit *commit;
>     ++	struct commit **parents_to_queue = NULL;
>     ++	size_t parents_to_queue_nr, parents_to_queue_alloc = 0;
>      +
>     -+	commit_list_insert(start_commit, &list);
>     ++	memset(&queue, 0, sizeof(queue)); /* Use the prio_queue as LIFO */
>     ++	prio_queue_put(&queue, start_commit);
>      +
>     -+	while (list) {
>     -+		struct commit *commit = pop_commit(&list);
>     ++	while ((commit = prio_queue_get(&queue))) {
>      +		struct rev_name *name = get_commit_rev_name(commit);
>     -+		struct commit_list *parents, *new_parents = NULL;
>     -+		struct commit_list **last_new_parent = &new_parents;
>     ++		struct commit_list *parents;
>      +		int parent_number = 1;
>      +
>     ++		parents_to_queue_nr = 0;
>     ++
>      +		for (parents = commit->parents;
>      +				parents;
>      +				parents = parents->next, parent_number++) {
>     @@ builtin/name-rev.c: static struct rev_name *create_or_update_name(struct commit
>      -			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);
>     ++						  from_tag)) {
>     ++				ALLOC_GROW(parents_to_queue,
>     ++					   parents_to_queue_nr + 1,
>     ++					   parents_to_queue_alloc);
>     ++				parents_to_queue[parents_to_queue_nr] = parent;
>     ++				parents_to_queue_nr++;
>     ++			}
>       		}
>
>      -		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;
>     ++		/* The first parent must come out first from the prio_queue */
>     ++		while (parents_to_queue_nr)
>     ++			prio_queue_put(&queue,
>     ++				       parents_to_queue[--parents_to_queue_nr]);
>       	}
>     ++
>     ++	clear_prio_queue(&queue);
>     ++	free(parents_to_queue);
>       }
>
>     + static int subpath_matches(const char *path, const char *filter)
>
>       ## t/t6120-describe.sh ##
>      @@ t/t6120-describe.sh: test_expect_success 'describe tag object' '
> 13:  1ef69550ca ! 13:  316f7af43c name-rev: cleanup name_ref()
>     @@ builtin/name-rev.c: static struct rev_name *create_or_update_name(struct commit
>      -		int from_tag)
>      +		int from_tag, int deref)
>       {
>     - 	struct commit_list *list = NULL;
>     + 	struct prio_queue queue;
>     + 	struct commit *commit;
>     + 	struct commit **parents_to_queue = NULL;
>     + 	size_t parents_to_queue_nr, parents_to_queue_alloc = 0;
>      +	char *to_free = NULL;
>      +
>      +	parse_commit(start_commit);
>     @@ builtin/name-rev.c: static struct rev_name *create_or_update_name(struct commit
>      +		return;
>      +	}
>
>     - 	commit_list_insert(start_commit, &list);
>     -
>     + 	memset(&queue, 0, sizeof(queue)); /* Use the prio_queue as LIFO */
>     + 	prio_queue_put(&queue, start_commit);
>      @@ builtin/name-rev.c: static int name_ref(const char *path, const struct object_id *oid, int flags, vo
>       		if (taggerdate == TIME_MAX)
>       			taggerdate = commit->date;
> 14:  9d513b3092 <  -:  ---------- name-rev: plug a memory leak in name_rev()
> 15:  8489abb62e <  -:  ---------- name-rev: plug a memory leak in name_rev() in the deref case
> --
> 2.24.0.388.gde53c094ea
>
>