path.c: add_to_trie - possible global-buffer-overflow fixed

Commit Message

Rubén Justo Oct. 17, 2022, 6:12 a.m. UTC

Since 4e09cf2ac (path: optimize common dir checking, 2015-08-31) a trie
is used to search over the common_list array.  The trie is formed from a
well-known list of values.  With the current implementation there can be
problems if the current values are rearranged or new values are
introduced.

This is fine:

	static const struct common_dir common_list[] = {
		{ 1, 1, 1, "logs" },
		{ 1, 0, 0, "logs/HEAD" },
		...

But this will lead to a global-buffer-overflow:

	static const struct common_dir common_list[] = {
		{ 1, 0, 0, "logs/HEAD" },
		{ 1, 1, 1, "logs" },
		...

And this will confuse and is probably a bug:

	static const struct common_dir common_list[] = {
		{ 1, 1, 1, "logs" },
		{ 0, 0, 0, "logs" },
		...

Let's fix the former and throw an assert on the latter.

Signed-off-by: Rubén Justo <[e-mail]>
---
 path.c | 19 ++++++++-----------
 1 file changed, 8 insertions(+), 11 deletions(-)

Patch

diff --git a/path.c b/path.c
index a3cfcd8a6e..a925cf073b 100644
--- a/path.c
+++ b/path.c
@@ -185,13 +185,6 @@  static void *add_to_trie(struct trie *root, const char *key, void *value)
 	void *old;
 	int i;
 
-	if (!*key) {
-		/* we have reached the end of the key */
-		old = root->value;
-		root->value = value;
-		return old;
-	}
-
 	for (i = 0; i < root->len; i++) {
 		if (root->contents[i] == key[i])
 			continue;
@@ -209,15 +202,17 @@  static void *add_to_trie(struct trie *root, const char *key, void *value)
 						   child->len);
 		}
 		child->value = root->value;
-		root->value = NULL;
+		root->value = key[i]
+			? NULL /* Key splits the compressed section. */
+			: value; /* Key matches up to here. */
 		root->len = i;
 
 		memset(root->children, 0, sizeof(root->children));
 		root->children[(unsigned char)root->contents[i]] = child;
 
-		/* This is the newly-added child. */
-		root->children[(unsigned char)key[i]] =
-			make_trie_node(key + i + 1, value);
+		if (key[i])
+			root->children[(unsigned char)key[i]] =
+				make_trie_node(key + i + 1, value);
 		return NULL;
 	}
 
@@ -233,6 +228,8 @@  static void *add_to_trie(struct trie *root, const char *key, void *value)
 		}
 	}
 
+	/* We have matched the entire compressed section with the entire key */
+	assert(!root->value); /* Key already present in the trie? */
 	old = root->value;
 	root->value = value;
 	return old;