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

[PATCH 12/15] name-rev: eliminate recursion in name_rev()

From
SZEDER Gábor <szeder.dev@gmail.com>
Date
Sep 19, 2019, 21:47 UTC
Message-ID
<20190919214712.7348-13-szeder.dev@gmail.com>
In-Reply-To
<20190919214712.7348-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.

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(-)
diff --git a/builtin/name-rev.c b/builtin/name-rev.c
index f2198a8bc3..b6fa495340 100644
--- a/builtin/name-rev.c
+++ b/builtin/name-rev.c
@@ -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;
 	}
 }
 
diff --git a/t/t6120-describe.sh b/t/t6120-describe.sh
index 2a0f2204c4..e37f02d21c 100755
--- a/t/t6120-describe.sh
+++ b/t/t6120-describe.sh
@@ -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

-- 
2.23.0.331.g4e51dcdf11
Previous: SZEDER GáborNext: SZEDER Gábor
Message 49 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.