Commit f26946358f0ddf106f54e4a9d7eaaf7b60a2c20f
2018-09-06T14:17:54
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 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62
diff --git a/src/config_file.c b/src/config_file.c
index 050bcfc..26bc200 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;