git/list[1] front-page[2] threads[3] people[4] search[5] about
 

[PATCH v3 13/14] name-rev: eliminate recursion in name_rev()

From
SZEDER Gábor <szeder.dev@gmail.com>
Date
Dec 9, 2019, 11:52 UTC
Message-ID
<20191209115258.9281-14-szeder.dev@gmail.com>
In-Reply-To
<20191209115258.9281-1-szeder.dev@gmail.com>

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 ('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 LIFO 'prio_queue' [1] and iterating until the queue becomes empty.

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 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 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'.
[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  | 102 +++++++++++++++++++++++++++-----------------
 t/t6120-describe.sh |   2 +-
 2 files changed, 65 insertions(+), 39 deletions(-)
diff --git a/builtin/name-rev.c b/builtin/name-rev.c
index 6c1e6e9868..a3b796eac4 100644
--- a/builtin/name-rev.c
+++ b/builtin/name-rev.c
@@ -6,6 +6,7 @@
 #include "tag.h"
 #include "refs.h"
 #include "parse-options.h"
+#include "prio-queue.h"
 #include "sha1-lookup.h"
 #include "commit-slab.h"
 
@@ -104,52 +105,77 @@ 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 prio_queue queue;
+	struct commit *commit;
+	struct commit **parents_to_queue = NULL;
+	size_t parents_to_queue_nr, parents_to_queue_alloc = 0;
+
+	memset(&queue, 0, sizeof(queue)); /* Use the prio_queue as LIFO */
+	prio_queue_put(&queue, start_commit);
+
+	while ((commit = prio_queue_get(&queue))) {
+		struct rev_name *name = get_commit_rev_name(commit);
+		struct commit_list *parents;
+		int parent_number = 1;
+
+		parents_to_queue_nr = 0;
+
+		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(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;
+			if (create_or_update_name(parent, new_name, taggerdate,
+						  generation, distance,
+						  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);
+		/* 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)
diff --git a/t/t6120-describe.sh b/t/t6120-describe.sh
index 0d119e9652..09c50f3f04 100755
--- a/t/t6120-describe.sh
+++ b/t/t6120-describe.sh
@@ -381,7 +381,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

-- 
2.24.0.801.g241c134b8d
Previous: SZEDER GáborNext: Derrick Stolee
Message 96 of 98 in “name-rev: eliminate recursion”
  1. 00/15 name-rev: eliminate recursionSZEDER Gábor, Sep 19, 2019
  2. 01/15 t6120-describe: correct test repo history graph in commentSZEDER Gábor, Sep 19, 2019
  3. Junio C HamanoSep 20, 2019
  4. SZEDER GáborSep 20, 2019
  5. Junio C HamanoSep 28, 2019
  6. 02/15 t6120-describe: modernize the 'check_describe' helperSZEDER Gábor, Sep 19, 2019
  7. Junio C HamanoSep 20, 2019
  8. 03/15 name-rev: use strip_suffix() in get_rev_name()SZEDER Gábor, Sep 19, 2019
  9. René ScharfeSep 20, 2019
  10. SZEDER GáborSep 20, 2019
  11. 05/15 name-rev: use sizeof(*ptr) instead of sizeof(type) in allocationSZEDER Gábor, Sep 19, 2019
  12. Derrick StoleeSep 20, 2019
  13. SZEDER GáborSep 20, 2019
  14. René ScharfeSep 20, 2019
  15. 06/15 t6120: add a test to cover inner conditions in 'git name-rev's name_rev()SZEDER Gábor, Sep 19, 2019
  16. Derrick StoleeSep 20, 2019
  17. SZEDER GáborSep 20, 2019
  18. 04/15 name-rev: avoid unnecessary cast in name_ref()SZEDER Gábor, Sep 19, 2019
  19. René ScharfeSep 20, 2019
  20. 10/15 name-rev: restructure creating/updating 'struct rev_name' instancesSZEDER Gábor, Sep 19, 2019
  21. Derrick StoleeSep 20, 2019
  22. SZEDER GáborSep 20, 2019
  23. 08/15 name-rev: pull out deref handling from the recursionSZEDER Gábor, Sep 19, 2019
  24. Derrick StoleeSep 20, 2019
  25. SZEDER GáborSep 20, 2019
  26. René ScharfeSep 20, 2019
  27. SZEDER GáborSep 20, 2019
  28. SZEDER GáborSep 20, 2019
  29. SZEDER GáborSep 21, 2019
  30. René ScharfeSep 21, 2019
  31. SZEDER GáborSep 22, 2019
  32. René ScharfeSep 23, 2019
  33. SZEDER GáborSep 23, 2019
  34. René ScharfeSep 23, 2019
  35. SZEDER GáborSep 23, 2019
  36. René ScharfeSep 24, 2019
  37. SZEDER GáborSep 26, 2019
  38. René ScharfeSep 21, 2019
  39. SZEDER GáborSep 21, 2019
  40. René ScharfeSep 21, 2019
  41. 09/15 name-rev: restructure parsing commits and applying date cutoffSZEDER Gábor, Sep 19, 2019
  42. René ScharfeSep 21, 2019
  43. 07/15 name-rev: extract creating/updating a 'struct name_rev' into a helperSZEDER Gábor, Sep 19, 2019
  44. Derrick StoleeSep 20, 2019
  45. name-rev: rewrite create_or_update_name()Martin Ågren, Sep 22, 2019
  46. SZEDER GáborDec 9, 2019
  47. 11/15 name-rev: drop name_rev()'s 'generation' and 'distance' parametersSZEDER Gábor, Sep 19, 2019
  48. 13/15 name-rev: cleanup name_ref()SZEDER Gábor, Sep 19, 2019
  49. 12/15 name-rev: eliminate recursion in name_rev()SZEDER Gábor, Sep 19, 2019
  50. 14/15 name-rev: plug a memory leak in name_rev()SZEDER Gábor, Sep 19, 2019
  51. 15/15 name-rev: plug a memory leak in name_rev() in the deref caseSZEDER Gábor, Sep 19, 2019
  52. Derrick StoleeSep 20, 2019
  53. 14/15 name-rev: plug memory leak in name_rev() in the deref caseSZEDER Gábor, Sep 19, 2019
  54. SZEDER GáborSep 19, 2019
  55. 15/15 name-rev: plug memory leak in name_rev()SZEDER Gábor, Sep 19, 2019
  56. SZEDER GáborSep 19, 2019
  57. Derrick StoleeSep 20, 2019
  58. SZEDER GáborSep 20, 2019
  59. 00/13 name-rev: eliminate recursionSZEDER Gábor, Nov 12, 2019
  60. 01/13 t6120-describe: correct test repo history graph in commentSZEDER Gábor, Nov 12, 2019
  61. 03/13 name-rev: use strbuf_strip_suffix() in get_rev_name()SZEDER Gábor, Nov 12, 2019
  62. René ScharfeNov 12, 2019
  63. 02/13 t6120-describe: modernize the 'check_describe' helperSZEDER Gábor, Nov 12, 2019
  64. Jonathan TanNov 27, 2019
  65. 07/13 name-rev: extract creating/updating a 'struct name_rev' into a helperSZEDER Gábor, Nov 12, 2019
  66. 05/13 name-rev: use sizeof(*ptr) instead of sizeof(type) in allocationSZEDER Gábor, Nov 12, 2019
  67. 08/13 name-rev: pull out deref handling from the recursionSZEDER Gábor, Nov 12, 2019
  68. 06/13 t6120: add a test to cover inner conditions in 'git name-rev's name_rev()SZEDER Gábor, Nov 12, 2019
  69. 09/13 name-rev: restructure parsing commits and applying date cutoffSZEDER Gábor, Nov 12, 2019
  70. 04/13 name-rev: avoid unnecessary cast in name_ref()SZEDER Gábor, Nov 12, 2019
  71. 11/13 name-rev: drop name_rev()'s 'generation' and 'distance' parametersSZEDER Gábor, Nov 12, 2019
  72. Jonathan TanNov 27, 2019
  73. 13/13 name-rev: cleanup name_ref()SZEDER Gábor, Nov 12, 2019
  74. Jonathan TanNov 27, 2019
  75. SZEDER GáborDec 9, 2019
  76. 10/13 name-rev: restructure creating/updating 'struct rev_name' instancesSZEDER Gábor, Nov 12, 2019
  77. 12/13 name-rev: eliminate recursion in name_rev()SZEDER Gábor, Nov 12, 2019
  78. Jonathan TanNov 27, 2019
  79. SZEDER GáborDec 9, 2019
  80. Johannes SchindelinNov 12, 2019
  81. Sebastiaan DammannNov 13, 2019
  82. 00/14 name-rev: eliminate recursionSZEDER Gábor, Dec 9, 2019
  83. 01/14 t6120-describe: correct test repo history graph in commentSZEDER Gábor, Dec 9, 2019
  84. 02/14 t6120-describe: modernize the 'check_describe' helperSZEDER Gábor, Dec 9, 2019
  85. 03/14 name-rev: use strbuf_strip_suffix() in get_rev_name()SZEDER Gábor, Dec 9, 2019
  86. 04/14 name-rev: avoid unnecessary cast in name_ref()SZEDER Gábor, Dec 9, 2019
  87. 05/14 name-rev: use sizeof(*ptr) instead of sizeof(type) in allocationSZEDER Gábor, Dec 9, 2019
  88. 07/14 name-rev: extract creating/updating a 'struct name_rev' into a helperSZEDER Gábor, Dec 9, 2019
  89. 06/14 t6120: add a test to cover inner conditions in 'git name-rev's name_rev()SZEDER Gábor, Dec 9, 2019
  90. 08/14 name-rev: pull out deref handling from the recursionSZEDER Gábor, Dec 9, 2019
  91. 11/14 name-rev: drop name_rev()'s 'generation' and 'distance' parametersSZEDER Gábor, Dec 9, 2019
  92. 12/14 name-rev: use 'name->tip_name' instead of 'tip_name'SZEDER Gábor, Dec 9, 2019
  93. 10/14 name-rev: restructure creating/updating 'struct rev_name' instancesSZEDER Gábor, Dec 9, 2019
  94. 09/14 name-rev: restructure parsing commits and applying date cutoffSZEDER Gábor, Dec 9, 2019
  95. 14/14 name-rev: cleanup name_ref()SZEDER Gábor, Dec 9, 2019
  96. 13/14 name-rev: eliminate recursion in name_rev()SZEDER Gábor, Dec 9, 2019
  97. Derrick StoleeDec 9, 2019
  98. Junio C HamanoDec 11, 2019

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.