{"thread":{"id":"45788","subject":"[PATCH 0/2] perf: show that wildmatch() regressed for pathological cases in v2.0","startedAt":"2017-04-24T21:13:13Z","lastAt":"2017-04-24T22:45:53Z","messageCount":5,"participants":["Ævar Arnfjörð Bjarmason","Brandon Williams"],"isPatch":true,"patchVersion":1,"patchTotal":2},"messages":[{"id":"317722","messageId":"20170424211249.28553-1-avarab@gmail.com","threadId":"45788","inReplyTo":null,"subject":"[PATCH 0/2] perf: show that wildmatch() regressed for pathological cases in v2.0","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2017-04-24T21:12:47Z","receivedAt":"2017-04-24T21:13:13Z","isPatch":true,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"Russ Cox just published an article about how various glob()\nimplementations suffer from pathological performance when fed certain\npathological patterns like \"a*a*a*a*b\" given a file like \"aaaaaaa...\":\nhttps://research.swtch.com/glob\n\nI was curious to see if this impacted git. It turns out it does. This\nused to be a per-platform issue with git, since globbing was\nimplemented via fnmatch() by default before v1.8.4, and support for\nusing the OS fnmatch() was removed entirely in v2.0.0.\n\nThis performance test shows the regression:\n\n    $ GIT_PERF_REPEAT_COUNT=1 GIT_PERF_MAKE_OPTS=\"[...]NO_WILDMATCH=YesPlease[...]\" ./run v1.9.5 v2.0.0 v2.12.0 p0100-globbing.sh\n    [...]\n    Test                                                       v1.9.5            v2.0.0                    v2.12.0\n    ------------------------------------------------------------------------------------------------------------------------------\n    [...]\n    0100.7: fileglob((a*)^nb) against file (a^100).t; n = 1    0.01(0.00+0.00)   0.00(0.00+0.00) -100.0%   0.01(0.00+0.00) +0.0%\n    0100.8: fileglob((a*)^nb) against file (a^100).t; n = 2    0.01(0.00+0.00)   0.00(0.00+0.00) -100.0%   0.01(0.00+0.00) +0.0%\n    0100.9: fileglob((a*)^nb) against file (a^100).t; n = 3    0.00(0.00+0.00)   0.00(0.00+0.00) =         0.01(0.00+0.00) +inf\n    0100.10: fileglob((a*)^nb) against file (a^100).t; n = 4   0.00(0.00+0.00)   0.01(0.01+0.00) +inf      0.02(0.02+0.00) +inf\n    0100.11: fileglob((a*)^nb) against file (a^100).t; n = 5   0.00(0.00+0.00)   0.20(0.19+0.00) +inf      0.24(0.23+0.00) +inf\n    0100.12: fileglob((a*)^nb) against file (a^100).t; n = 6   0.00(0.00+0.00)   3.03(3.00+0.00) +inf      3.08(3.05+0.00) +inf\n\nAnd here's a one-liner to do the same:\n\n    $ time (rm -rf test; git init -q test && (cd test && touch $(perl -e 'print \"a\" x 100').t && git add a* && git commit -q -m\"test\" && git ls-files 'a*a*a*a*a*a*a*b'))\n\nAdd or remove \"a*\"'s to adjust the runtime. With 6 that executes in 3\nseconds on my system, 40 seconds with 7 etc.\n\nI don't think this is something we need to worry much about, if you\nhave a file like this and feed Git insane patterns you probably\ndeserve what you get.\n\nThe real concern is if we have behavior like this and ever e.g. expose\nglobbing over the network, e.g. in some future upload-pack protocol.\n\nThere are probably some web-based programs built on top of git that\nare vulnerable to DoS attacks as a result of this, e.g. if they take\nuser-supplied globs and feed them to ls-files.\n\nÆvar Arnfjörð Bjarmason (2):\n  perf: add function to setup a fresh test repo\n  perf: add test showing exponential growth in path globbing\n\n t/perf/README            |  1 +\n t/perf/p0100-globbing.sh | 48 ++++++++++++++++++++++++++++++++++++++++++++++++\n t/perf/perf-lib.sh       | 17 +++++++++++++----\n 3 files changed, 62 insertions(+), 4 deletions(-)\n create mode 100755 t/perf/p0100-globbing.sh\n\n-- \n2.11.0\n\n"},{"id":"317723","messageId":"20170424211249.28553-2-avarab@gmail.com","threadId":"45788","inReplyTo":"20170424211249.28553-1-avarab@gmail.com","subject":"[PATCH 1/2] perf: add function to setup a fresh test repo","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2017-04-24T21:12:48Z","receivedAt":"2017-04-24T21:13:19Z","isPatch":true,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"Add a function to setup a fresh test repo via 'git init' to compliment\nthe existing functions to copy over a normal & large repo.\n\nSome performance tests don't need any existing repository data at all\nto be significant, e.g. tests which stress glob matches against\nrevisions or files, which I'm about to add in a subsequent commit.\n\nSigned-off-by: Ævar Arnfjörð Bjarmason <avarab@gmail.com>\n---\n t/perf/README      |  1 +\n t/perf/perf-lib.sh | 17 +++++++++++++----\n 2 files changed, 14 insertions(+), 4 deletions(-)\n\ndiff --git a/t/perf/README b/t/perf/README\nindex 49ea4349be..de2fe15696 100644\n--- a/t/perf/README\n+++ b/t/perf/README\n@@ -106,6 +106,7 @@ sources perf-lib.sh:\n \n After that you will want to use some of the following:\n \n+\ttest_perf_fresh_repo    # sets up an empty repository\n \ttest_perf_default_repo  # sets up a \"normal\" repository\n \ttest_perf_large_repo    # sets up a \"large\" repository\n \ndiff --git a/t/perf/perf-lib.sh b/t/perf/perf-lib.sh\nindex ab4b8b06ae..f51fc773e8 100644\n--- a/t/perf/perf-lib.sh\n+++ b/t/perf/perf-lib.sh\n@@ -78,6 +78,10 @@ if test -z \"$GIT_PERF_LARGE_REPO\"; then\n \tGIT_PERF_LARGE_REPO=$TEST_DIRECTORY/..\n fi\n \n+test_perf_do_repo_symlink_config_ () {\n+\ttest_have_prereq SYMLINKS || git config core.symlinks false\n+}\n+\n test_perf_create_repo_from () {\n \ttest \"$#\" = 2 ||\n \terror \"bug in the test script: not 2 parameters to test-create-repo\"\n@@ -102,15 +106,20 @@ test_perf_create_repo_from () {\n \t) &&\n \t(\n \t\tcd \"$repo\" &&\n-\t\t\"$MODERN_GIT\" init -q && {\n-\t\t\ttest_have_prereq SYMLINKS ||\n-\t\t\tgit config core.symlinks false\n-\t\t} &&\n+\t\t\"$MODERN_GIT\" init -q &&\n+\t\ttest_perf_do_repo_symlink_config_ &&\n \t\tmv .git/hooks .git/hooks-disabled 2>/dev/null\n \t) || error \"failed to copy repository '$source' to '$repo'\"\n }\n \n # call at least one of these to establish an appropriately-sized repository\n+test_perf_fresh_repo () {\n+\trepo=\"${1:-$TRASH_DIRECTORY}\"\n+\t\"$MODERN_GIT\" init -q \"$repo\" &&\n+\tcd \"$repo\" &&\n+\ttest_perf_do_repo_symlink_config_\n+}\n+\n test_perf_default_repo () {\n \ttest_perf_create_repo_from \"${1:-$TRASH_DIRECTORY}\" \"$GIT_PERF_REPO\"\n }\n-- \n2.11.0\n\n"},{"id":"317724","messageId":"20170424211249.28553-3-avarab@gmail.com","threadId":"45788","inReplyTo":"20170424211249.28553-1-avarab@gmail.com","subject":"[PATCH 2/2] perf: add test showing exponential growth in path globbing","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2017-04-24T21:12:49Z","receivedAt":"2017-04-24T21:13:21Z","isPatch":true,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"Add a test showing that ls-files times grow exponentially in the face\nof some pathological globs, whereas refglobs via for-each-ref don't in\npractice suffer from the same issue.\n\nAs noted in the test description this is a test to see whether Git\nsuffers from the issue noted in an article Russ Cox posted today about\ncommon bugs in various glob implementations:\nhttps://research.swtch.com/glob\n\nThe pathological git-ls-files globbing is done by wildmatch() in\nwildmatch.c. The for-each-ref codepath also uses wildmatch(), but will\nalways match against e.g. \"refs/tags/aaa...\", not \"aaa..\" as\ngit-ls-files will.\n\nI'm unsure why the pathological case isn't triggered by for-each-ref,\nbut in any case, now we have a performance test for it.\n\nSigned-off-by: Ævar Arnfjörð Bjarmason <avarab@gmail.com>\n---\n t/perf/p0100-globbing.sh | 48 ++++++++++++++++++++++++++++++++++++++++++++++++\n 1 file changed, 48 insertions(+)\n create mode 100755 t/perf/p0100-globbing.sh\n\ndiff --git a/t/perf/p0100-globbing.sh b/t/perf/p0100-globbing.sh\nnew file mode 100755\nindex 0000000000..e98fd7ce4b\n--- /dev/null\n+++ b/t/perf/p0100-globbing.sh\n@@ -0,0 +1,48 @@\n+#!/bin/sh\n+\n+test_description=\"Tests pathalogical globbing performance\n+\n+Shows how Git's globbing performance performs when given the sort of\n+pathalogical patterns described in at https://research.swtch.com/glob\n+\"\n+\n+. ./perf-lib.sh\n+\n+test_globs_big='10 25 50 75 100'\n+test_globs_small='1 2 3 4 5 6'\n+\n+test_perf_fresh_repo\n+\n+test_expect_success 'setup' '\n+\tfor i in $(test_seq 1 100)\n+\tdo\n+\t\tprintf \"a\" >>refname &&\n+\t\tfor j in $(test_seq 1 $i)\n+\t\tdo\n+\t\t\tprintf \"a*\" >>refglob.$i\n+\t\tdone &&\n+\t\techo b >>refglob.$i\n+\tdone &&\n+\ttest_commit $(cat refname) &&\n+\tfor i in $(test_seq 1 100)\n+\tdo\n+\techo\tgit tag $(cat refname)-$i\n+\tdone &&\n+\ttest_commit hello\n+'\n+\n+for i in $test_globs_big\n+do\n+\ttest_perf \"refglob((a*)^nb) against tag a^100; n = $i\" '\n+\t\tgit for-each-ref \"refs/tags/$(cat refglob.'$i')b\"\n+\t'\n+done\n+\n+for i in $test_globs_small\n+do\n+\ttest_perf \"fileglob((a*)^nb) against file (a^100).t; n = $i\" '\n+\t\tgit ls-files \"$(cat refglob.'$i')b\"\n+\t'\n+done\n+\n+test_done\n-- \n2.11.0\n\n"},{"id":"317725","messageId":"20170424213428.GA105623@google.com","threadId":"45788","inReplyTo":"20170424211249.28553-1-avarab@gmail.com","subject":"Re: [PATCH 0/2] perf: show that wildmatch() regressed for pathological cases in v2.0","fromName":"Brandon Williams","fromEmail":"bmwill@google.com","sentAt":"2017-04-24T21:34:28Z","receivedAt":"2017-04-24T21:35:20Z","isPatch":true,"sender":{"key":"bwilliams.eng@gmail.com","avatar":null},"body":"On 04/24, Ævar Arnfjörð Bjarmason wrote:\n> Russ Cox just published an article about how various glob()\n> implementations suffer from pathological performance when fed certain\n> pathological patterns like \"a*a*a*a*b\" given a file like \"aaaaaaa...\":\n> https://research.swtch.com/glob\n> \n> I was curious to see if this impacted git. It turns out it does. This\n> used to be a per-platform issue with git, since globbing was\n> implemented via fnmatch() by default before v1.8.4, and support for\n> using the OS fnmatch() was removed entirely in v2.0.0.\n> \n> This performance test shows the regression:\n> \n>     $ GIT_PERF_REPEAT_COUNT=1 GIT_PERF_MAKE_OPTS=\"[...]NO_WILDMATCH=YesPlease[...]\" ./run v1.9.5 v2.0.0 v2.12.0 p0100-globbing.sh\n>     [...]\n>     Test                                                       v1.9.5            v2.0.0                    v2.12.0\n>     ------------------------------------------------------------------------------------------------------------------------------\n>     [...]\n>     0100.7: fileglob((a*)^nb) against file (a^100).t; n = 1    0.01(0.00+0.00)   0.00(0.00+0.00) -100.0%   0.01(0.00+0.00) +0.0%\n>     0100.8: fileglob((a*)^nb) against file (a^100).t; n = 2    0.01(0.00+0.00)   0.00(0.00+0.00) -100.0%   0.01(0.00+0.00) +0.0%\n>     0100.9: fileglob((a*)^nb) against file (a^100).t; n = 3    0.00(0.00+0.00)   0.00(0.00+0.00) =         0.01(0.00+0.00) +inf\n>     0100.10: fileglob((a*)^nb) against file (a^100).t; n = 4   0.00(0.00+0.00)   0.01(0.01+0.00) +inf      0.02(0.02+0.00) +inf\n>     0100.11: fileglob((a*)^nb) against file (a^100).t; n = 5   0.00(0.00+0.00)   0.20(0.19+0.00) +inf      0.24(0.23+0.00) +inf\n>     0100.12: fileglob((a*)^nb) against file (a^100).t; n = 6   0.00(0.00+0.00)   3.03(3.00+0.00) +inf      3.08(3.05+0.00) +inf\n> \n> And here's a one-liner to do the same:\n> \n>     $ time (rm -rf test; git init -q test && (cd test && touch $(perl -e 'print \"a\" x 100').t && git add a* && git commit -q -m\"test\" && git ls-files 'a*a*a*a*a*a*a*b'))\n> \n> Add or remove \"a*\"'s to adjust the runtime. With 6 that executes in 3\n> seconds on my system, 40 seconds with 7 etc.\n> \n> I don't think this is something we need to worry much about, if you\n> have a file like this and feed Git insane patterns you probably\n> deserve what you get.\n> \n> The real concern is if we have behavior like this and ever e.g. expose\n> globbing over the network, e.g. in some future upload-pack protocol.\n> \n> There are probably some web-based programs built on top of git that\n> are vulnerable to DoS attacks as a result of this, e.g. if they take\n> user-supplied globs and feed them to ls-files.\n\nI was taking a look at wildmatch a few months ago and have an unfinished\npatch to do some cleanup there.  I noticed this was inefficient but\ndidn't expect those kinds of numbers.  I wonder how difficult it would\nbe to rewrite it so that we don't have this issue.\n\n-- \nBrandon Williams\n"},{"id":"317733","messageId":"CACBZZX60f9aSOEcjiJpd2uXM4JHgye3F5bZHpA=6RDfMEiv+yg@mail.gmail.com","threadId":"45788","inReplyTo":"20170424213428.GA105623@google.com","subject":"Re: [PATCH 0/2] perf: show that wildmatch() regressed for pathological cases in v2.0","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2017-04-24T22:45:27Z","receivedAt":"2017-04-24T22:45:53Z","isPatch":true,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"On Mon, Apr 24, 2017 at 11:34 PM, Brandon Williams <bmwill@google.com> wrote:\n> On 04/24, Ęvar Arnfjörš Bjarmason wrote:\n>> Russ Cox just published an article about how various glob()\n>> implementations suffer from pathological performance when fed certain\n>> pathological patterns like \"a*a*a*a*b\" given a file like \"aaaaaaa...\":\n>> https://research.swtch.com/glob\n>>\n>> I was curious to see if this impacted git. It turns out it does. This\n>> used to be a per-platform issue with git, since globbing was\n>> implemented via fnmatch() by default before v1.8.4, and support for\n>> using the OS fnmatch() was removed entirely in v2.0.0.\n>>\n>> This performance test shows the regression:\n>>\n>>     $ GIT_PERF_REPEAT_COUNT=1 GIT_PERF_MAKE_OPTS=\"[...]NO_WILDMATCH=YesPlease[...]\" ./run v1.9.5 v2.0.0 v2.12.0 p0100-globbing.sh\n>>     [...]\n>>     Test                                                       v1.9.5            v2.0.0                    v2.12.0\n>>     ------------------------------------------------------------------------------------------------------------------------------\n>>     [...]\n>>     0100.7: fileglob((a*)^nb) against file (a^100).t; n = 1    0.01(0.00+0.00)   0.00(0.00+0.00) -100.0%   0.01(0.00+0.00) +0.0%\n>>     0100.8: fileglob((a*)^nb) against file (a^100).t; n = 2    0.01(0.00+0.00)   0.00(0.00+0.00) -100.0%   0.01(0.00+0.00) +0.0%\n>>     0100.9: fileglob((a*)^nb) against file (a^100).t; n = 3    0.00(0.00+0.00)   0.00(0.00+0.00) =         0.01(0.00+0.00) +inf\n>>     0100.10: fileglob((a*)^nb) against file (a^100).t; n = 4   0.00(0.00+0.00)   0.01(0.01+0.00) +inf      0.02(0.02+0.00) +inf\n>>     0100.11: fileglob((a*)^nb) against file (a^100).t; n = 5   0.00(0.00+0.00)   0.20(0.19+0.00) +inf      0.24(0.23+0.00) +inf\n>>     0100.12: fileglob((a*)^nb) against file (a^100).t; n = 6   0.00(0.00+0.00)   3.03(3.00+0.00) +inf      3.08(3.05+0.00) +inf\n>>\n>> And here's a one-liner to do the same:\n>>\n>>     $ time (rm -rf test; git init -q test && (cd test && touch $(perl -e 'print \"a\" x 100').t && git add a* && git commit -q -m\"test\" && git ls-files 'a*a*a*a*a*a*a*b'))\n>>\n>> Add or remove \"a*\"'s to adjust the runtime. With 6 that executes in 3\n>> seconds on my system, 40 seconds with 7 etc.\n>>\n>> I don't think this is something we need to worry much about, if you\n>> have a file like this and feed Git insane patterns you probably\n>> deserve what you get.\n>>\n>> The real concern is if we have behavior like this and ever e.g. expose\n>> globbing over the network, e.g. in some future upload-pack protocol.\n>>\n>> There are probably some web-based programs built on top of git that\n>> are vulnerable to DoS attacks as a result of this, e.g. if they take\n>> user-supplied globs and feed them to ls-files.\n>\n> I was taking a look at wildmatch a few months ago and have an unfinished\n> patch to do some cleanup there.  I noticed this was inefficient but\n> didn't expect those kinds of numbers.  I wonder how difficult it would\n> be to rewrite it so that we don't have this issue.\n\nSomething I've started hacking on as part of a post-PCRE v2 series I'm\nworking on, which I'll submit after PCRE v2 support is merged, is to\nreplace various parts of regex / matching machinery with PCRE under\nthe hood if it's available, even when the user doesn't ask or care\nthat we're using PCRE.\n\nThe thing I'm working on now is to replace fixed-string grep/log\nsearches that we currently do via kwset with PCRE v2. It's quite a bit\nfaster than kwset, and allows us to fix a bunch of outstanding grep\nTODO items.\n\nIt would similarly be interesting to replace wildmatch() with a shimmy\nwrapper for PCRE that translates glob patterns to regexes. Not that we\nneed PCRE for that, we could probably just use regcomp(), but PCRE\nwould almost certainly be faster than wildmatch().\n\nOf course the use-cases are different. For the kwset replacement we'd\njust use PCRE under the hood because it's faster, whereas the reason\nwe integrated wildmatch() in the first place was to get consistent\nbehavior across all platforms, and PCRE is currently an optional\ndependency.\n\nI think it might make sense to solve this general class of problem by\neventually making PCRE a mandatory dependency of Git. Right now we\nhave copy/pasted versions of whatever the last GPLv2 version was of\nkwset/wildmatch, which we then have to maintain.\n\nBetween kwset/wildmatch/various code in grep.c & diffcore-pickaxe.c we\nprobably have 2-3k lines of very tricky string matching code which\ncould be replaced by relatively trivial calls into PCRE.\n"}]}