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

[PATCH 09/10] tree-diff: respect max_allowed_tree_depth

From
Jeff King <peff@peff.net>
Date
Aug 31, 2023, 06:22 UTC
Message-ID
<20230831062208.GI3185325@coredump.intra.peff.net>
In-Reply-To
<20230831061735.GA2702156@coredump.intra.peff.net>

When diffing trees, we recurse to handle subtrees. That means we may run out of stack space and segfault. Let's teach this code path about core.maxTreeDepth in order to fail more gracefully.

As with the previous patch, we have no way to return an error (and other tree-loading problems would just cause us to die()). So we'll likewise call die() if we exceed the maximum depth.

Signed-off-by: Jeff King <peff@peff.net>
---
 t/t6700-tree-depth.sh |  9 +++++++++
 tree-diff.c           | 23 +++++++++++++++--------
 2 files changed, 24 insertions(+), 8 deletions(-)
diff --git a/t/t6700-tree-depth.sh b/t/t6700-tree-depth.sh
index f5d284b16e..e410c41234 100755
--- a/t/t6700-tree-depth.sh
+++ b/t/t6700-tree-depth.sh
@@ -81,4 +81,13 @@ test_expect_success 'default limit for rev-list fails gracefully' '
 	test_must_fail git rev-list --objects big >/dev/null
 '
 
+test_expect_success 'limit recursion of diff-tree -r' '
+	git $small_ok diff-tree -r $EMPTY_TREE small &&
+	test_must_fail git $small_no diff-tree -r $EMPTY_TREE small
+'
+
+test_expect_success 'default limit for diff-tree fails gracefully' '
+	test_must_fail git diff-tree -r $EMPTY_TREE big
+'
+
 test_done
diff --git a/tree-diff.c b/tree-diff.c
index 8fc159b86e..46107772d1 100644
--- a/tree-diff.c
+++ b/tree-diff.c
@@ -7,6 +7,7 @@
 #include "hash.h"
 #include "tree.h"
 #include "tree-walk.h"
+#include "environment.h"
 
 /*
  * Some mode bits are also used internally for computations.
@@ -45,7 +46,8 @@
 static struct combine_diff_path *ll_diff_tree_paths(
 	struct combine_diff_path *p, const struct object_id *oid,
 	const struct object_id **parents_oid, int nparent,
-	struct strbuf *base, struct diff_options *opt);
+	struct strbuf *base, struct diff_options *opt,
+	int depth);
 static void ll_diff_tree_oid(const struct object_id *old_oid,
 			     const struct object_id *new_oid,
 			     struct strbuf *base, struct diff_options *opt);
@@ -196,7 +198,7 @@ static struct combine_diff_path *path_appendnew(struct combine_diff_path *last,
 static struct combine_diff_path *emit_path(struct combine_diff_path *p,
 	struct strbuf *base, struct diff_options *opt, int nparent,
 	struct tree_desc *t, struct tree_desc *tp,
-	int imin)
+	int imin, int depth)
 {
 	unsigned short mode;
 	const char *path;
@@ -302,7 +304,8 @@ static struct combine_diff_path *emit_path(struct combine_diff_path *p,
 
 		strbuf_add(base, path, pathlen);
 		strbuf_addch(base, '/');
-		p = ll_diff_tree_paths(p, oid, parents_oid, nparent, base, opt);
+		p = ll_diff_tree_paths(p, oid, parents_oid, nparent, base, opt,
+				       depth + 1);
 		FAST_ARRAY_FREE(parents_oid, nparent);
 	}
 
@@ -423,12 +426,16 @@ static inline void update_tp_entries(struct tree_desc *tp, int nparent)
 static struct combine_diff_path *ll_diff_tree_paths(
 	struct combine_diff_path *p, const struct object_id *oid,
 	const struct object_id **parents_oid, int nparent,
-	struct strbuf *base, struct diff_options *opt)
+	struct strbuf *base, struct diff_options *opt,
+	int depth)
 {
 	struct tree_desc t, *tp;
 	void *ttree, **tptree;
 	int i;
 
+	if (depth > max_allowed_tree_depth)
+		die("exceeded maximum allowed tree depth");
+
 	FAST_ARRAY_ALLOC(tp, nparent);
 	FAST_ARRAY_ALLOC(tptree, nparent);
 
@@ -522,7 +529,7 @@ static struct combine_diff_path *ll_diff_tree_paths(
 
 			/* D += {δ(t,pi) if pi=p[imin];  "+a" if pi > p[imin]} */
 			p = emit_path(p, base, opt, nparent,
-					&t, tp, imin);
+					&t, tp, imin, depth);
 
 		skip_emit_t_tp:
 			/* t↓,  ∀ pi=p[imin]  pi↓ */
@@ -534,7 +541,7 @@ static struct combine_diff_path *ll_diff_tree_paths(
 		else if (cmp < 0) {
 			/* D += "+t" */
 			p = emit_path(p, base, opt, nparent,
-					&t, /*tp=*/NULL, -1);
+					&t, /*tp=*/NULL, -1, depth);
 
 			/* t↓ */
 			update_tree_entry(&t);
@@ -550,7 +557,7 @@ static struct combine_diff_path *ll_diff_tree_paths(
 			}
 
 			p = emit_path(p, base, opt, nparent,
-					/*t=*/NULL, tp, imin);
+					/*t=*/NULL, tp, imin, depth);
 
 		skip_emit_tp:
 			/* ∀ pi=p[imin]  pi↓ */
@@ -572,7 +579,7 @@ struct combine_diff_path *diff_tree_paths(
 	const struct object_id **parents_oid, int nparent,
 	struct strbuf *base, struct diff_options *opt)
 {
-	p = ll_diff_tree_paths(p, oid, parents_oid, nparent, base, opt);
+	p = ll_diff_tree_paths(p, oid, parents_oid, nparent, base, opt, 0);
 
 	/*
 	 * free pre-allocated last element, if any

-- 
2.42.0.561.gaa987ecc69
Previous: Jeff KingNext: Jeff King
Message 10 of 16 in “tree name and depth limits”
  1. 0/10 tree name and depth limitsJeff King, Aug 31, 2023
  2. 01/10 tree-walk: reduce stack size for recursive functionsJeff King, Aug 31, 2023
  3. 02/10 tree-walk: drop MAX_TRAVERSE_TREES macroJeff King, Aug 31, 2023
  4. 03/10 tree-walk: rename "error" variableJeff King, Aug 31, 2023
  5. 04/10 fsck: detect very large tree pathnamesJeff King, Aug 31, 2023
  6. 05/10 add core.maxTreeDepth configJeff King, Aug 31, 2023
  7. 06/10 traverse_trees(): respect max_allowed_tree_depthJeff King, Aug 31, 2023
  8. 07/10 read_tree(): respect max_allowed_tree_depthJeff King, Aug 31, 2023
  9. 08/10 list-objects: respect max_allowed_tree_depthJeff King, Aug 31, 2023
  10. 09/10 tree-diff: respect max_allowed_tree_depthJeff King, Aug 31, 2023
  11. 10/10 lower core.maxTreeDepth default to 2048Jeff King, Aug 31, 2023
  12. Oswald BuddenhagenAug 31, 2023
  13. Jeff KingAug 31, 2023
  14. Junio C HamanoAug 31, 2023
  15. rsbecker@nexbridge.comAug 31, 2023
  16. Jeff KingAug 31, 2023

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.