thodg/libgit2/src

Diff

  • Show log

    Commit

  • Hash : f2694635
    Author : Patrick Steinhardt
    Date : 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.

kmx.io     mail     discord kmxgit v0.4.0