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