config_file: fix quadratic behaviour when adding config multivars

In case where we add multiple configuration entries with the same key to
a diskfile backend, we always need to iterate the list of this key to
find the last entry due to the list being a singly-linked list. This
is obviously quadratic behaviour, and this has sure enough been found by
oss-fuzz by generating a configuration file with 50k lines, where most
of them have the same key. While the issue will not arise with "sane"
configuration files, an adversary may trigger it by providing a crafted
".gitmodules" file, which is delivered as part of the repo and also
parsed by the configuration parser.

The fix is trivial: store a pointer to the last entry of the list in its
head. As there are only two locations now where we append to this data
structure, mainting this pointer is trivial, too. We can also optimize
retrieval of a single value via `config_get`, where we previously had to
chase the `next` pointer to find the last entry that was added.

Using our configuration file fozzur with a corpus that has a single file
with 50000 "-=" lines previously took around 21s. With this optimization
the same file scans in about 0.053s, which is a nearly 400-fold
improvement. But in most cases with a "normal" amount of same-named keys
it's not going to matter anyway.

1 files changed, 17 insertions, 12 deletions

diff --git a/src/config_file.c b/src/config_file.c
index 050bcfc92..26bc200df 100644
--- a/src/config_file.c
+++ b/src/config_file.c
@@ -25,6 +25,7 @@
 
 typedef struct config_entry_list {
 	struct config_entry_list *next;
+	struct config_entry_list *last;
 	git_config_entry *entry;
 } config_entry_list;
 
@@ -131,15 +132,11 @@ int git_config_file_normalize_section(char *start, char *end)
 
 static void config_entry_list_append(config_entry_list **list, config_entry_list *entry)
 {
-	config_entry_list *head = *list;
-
-	if (head) {
-		while (head->next != NULL)
-			head = head->next;
-		head->next = entry;
-	} else {
+	if (*list)
+		(*list)->last->next = entry;
+	else
 		*list = entry;
-	}
+	(*list)->last = entry;
 }
 
 /* Add or append the new config option */
@@ -155,6 +152,17 @@ static int diskfile_entries_append(diskfile_entries *entries, git_config_entry *
 
 	pos = git_strmap_lookup_index(entries->map, entry->name);
 	if (!git_strmap_valid_index(entries->map, pos)) {
+		/*
+		 * We only ever inspect `last` from the first config
+		 * entry in a multivar. In case where this new entry is
+		 * the first one in the entry map, it will also be the
+		 * last one at the time of adding it, which is
+		 * why we set `last` here to itself. Otherwise we
+		 * do not have to set `last` and leave it set to
+		 * `NULL`.
+		 */
+		var->last = var;
+
 		git_strmap_insert(entries->map, entry->name, var, &error);
 
 		if (error > 0)
@@ -517,10 +525,7 @@ static int config_get(git_config_backend *cfg, const char *key, git_config_entry
 	}
 
 	var = git_strmap_value_at(entry_map, pos);
-	while (var->next)
-		var = var->next;
-
-	*out = var->entry;
+	*out = var->last->entry;
 	(*out)->free = free_diskfile_entry;
 	(*out)->payload = entries;