{"thread":{"id":"46993","subject":"[PATCH v1] read_index_from(): Skip verification of the cache entry order to speed index loading","startedAt":"2017-10-18T14:28:56Z","lastAt":"2017-11-01T06:09:50Z","messageCount":18,"participants":["Ben Peart","Junio C Hamano","Jeff King","Stefan Beller","Johannes Schindelin","Alex Vandiver"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"330601","messageId":"20171018142725.10948-1-benpeart@microsoft.com","threadId":"46993","inReplyTo":null,"subject":"[PATCH v1] read_index_from(): Skip verification of the cache entry order to speed index loading","fromName":"Ben Peart","fromEmail":"benpeart@microsoft.com","sentAt":"2017-10-18T14:27:25Z","receivedAt":"2017-10-18T14:28:56Z","isPatch":true,"sender":{"key":"benpeart@microsoft.com","avatar":"https://avatars.githubusercontent.com/u/15252029?v=4"},"body":"There is code in post_read_index_from() to catch out of order entries\nwhen reading an index file.  This order verification is ~13% of the cost\nof every call to read_index_from().\n\nUpdate check_ce_order() so that it skips this verification unless the\n\"verify_ce_order\" global variable is set.\n\nTeach fsck to force this verification.\n\nThe effect can be seen using t/perf/p0002-read-cache.sh:\n\nTest                                          HEAD              HEAD~1\n--------------------------------------------------------------------------------------\n0002.1: read_cache/discard_cache 1000 times   0.41(0.04+0.04)   0.50(0.00+0.10) +22.0%\n\nSigned-off-by: Ben Peart <benpeart@microsoft.com>\n---\n\nNotes:\n    Base Ref:\n    Web-Diff: https://github.com/benpeart/git/commit/54fa9cf954\n    Checkout: git fetch https://github.com/benpeart/git verify_ce_order-v1 && git checkout 54fa9cf954\n\n builtin/fsck.c | 1 +\n cache.h        | 1 +\n read-cache.c   | 6 ++++++\n 3 files changed, 8 insertions(+)\n\ndiff --git a/builtin/fsck.c b/builtin/fsck.c\nindex d18244ab54..81cc5ad78d 100644\n--- a/builtin/fsck.c\n+++ b/builtin/fsck.c\n@@ -763,6 +763,7 @@ int cmd_fsck(int argc, const char **argv, const char *prefix)\n \n \tif (keep_cache_objects) {\n \t\tverify_index_checksum = 1;\n+\t\tverify_ce_order = 1;\n \t\tread_cache();\n \t\tfor (i = 0; i < active_nr; i++) {\n \t\t\tunsigned int mode;\ndiff --git a/cache.h b/cache.h\nindex 5e2c9512ff..4a4f879061 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -721,6 +721,7 @@ extern int hold_locked_index(struct lock_file *, int);\n extern void set_alternate_index_output(const char *);\n \n extern int verify_index_checksum;\n+extern int verify_ce_order;\n \n /* Environment bits from configuration mechanism */\n extern int trust_executable_bit;\ndiff --git a/read-cache.c b/read-cache.c\nindex b64610c400..32743da157 100644\n--- a/read-cache.c\n+++ b/read-cache.c\n@@ -1513,6 +1513,9 @@ struct ondisk_cache_entry_extended {\n /* Allow fsck to force verification of the index checksum. */\n int verify_index_checksum;\n \n+/* Allow fsck to force verification of the cache entry order. */\n+int verify_ce_order;\n+\n static int verify_hdr(struct cache_header *hdr, unsigned long size)\n {\n \tgit_SHA_CTX c;\n@@ -1698,6 +1701,9 @@ static void check_ce_order(struct index_state *istate)\n {\n \tunsigned int i;\n \n+\tif (!verify_ce_order)\n+\t\treturn;\n+\n \tfor (i = 1; i < istate->cache_nr; i++) {\n \t\tstruct cache_entry *ce = istate->cache[i - 1];\n \t\tstruct cache_entry *next_ce = istate->cache[i];\n\nbase-commit: 46309c695b080648f8c0ea5e2d1fd7387ee7f044\n-- \n2.14.1.windows.1.1034.g0776750557\n\n"},{"id":"330622","messageId":"xmqq4lqvk8ze.fsf@gitster.mtv.corp.google.com","threadId":"46993","inReplyTo":"20171018142725.10948-1-benpeart@microsoft.com","subject":"Re: [PATCH v1] read_index_from(): Skip verification of the cache entry order to speed index loading","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2017-10-19T05:22:13Z","receivedAt":"2017-10-19T05:22:22Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Ben Peart <benpeart@microsoft.com> writes:\n\n> There is code in post_read_index_from() to catch out of order entries\n> when reading an index file.  This order verification is ~13% of the cost\n> of every call to read_index_from().\n\nI find this a bit over-generalized claim---wouldn't the overhead\ndepend on various conditions, e.g. the size of the index and if\nsplit-index is in effect?\n\nIn general, I get very skeptical towards any change that makes the\nintegrity of the data less certain based only on microbenchmarks,\nand prefer to see a solution that can absorb the overhead in some\nother way.\n\nWhen we are using split-index, the current code is not validating\nthe two input files from the disk. Because merge_base_index()\ndepends on the base to be properly sorted before the overriding\nentries are added into it, if the input from disk is in a wrong\norder, we are screwed already, and the order check in post\nprocessing is pointless.  If we want to do this order validation, I\nthink we should be doing it in do_read_index() where it does\ncreate_from_disk() and the set_index_entry(), instead of having it\nas a separate phase that scans a potentially large index array one\nmore time.  And doing so will not penalize the case where we do not\nuse split-index, either.\n\nSo, I think I like the direction of getting rid of the order\nvalidation in post_read_index_from(), not only during the normal\noperation but also in fsck.  I think it makes more sense to do so\nincrementally inside do_read_index() all the time and see how fast\nwe can make it do so.\n"},{"id":"330639","messageId":"db8da340-f8f5-0114-392d-e415b5564993@gmail.com","threadId":"46993","inReplyTo":"xmqq4lqvk8ze.fsf@gitster.mtv.corp.google.com","subject":"Re: [PATCH v1] read_index_from(): Skip verification of the cache entry order to speed index loading","fromName":"Ben Peart","fromEmail":"peartben@gmail.com","sentAt":"2017-10-19T15:12:03Z","receivedAt":"2017-10-19T15:12:14Z","isPatch":true,"sender":{"key":"benpeart@microsoft.com","avatar":"https://avatars.githubusercontent.com/u/15252029?v=4"},"body":"\n\nOn 10/19/2017 1:22 AM, Junio C Hamano wrote:\n> Ben Peart <benpeart@microsoft.com> writes:\n> \n>> There is code in post_read_index_from() to catch out of order entries\n>> when reading an index file.  This order verification is ~13% of the cost\n>> of every call to read_index_from().\n> \n> I find this a bit over-generalized claim---wouldn't the overhead\n> depend on various conditions, e.g. the size of the index and if\n> split-index is in effect?\n> \n\nI tested it against 10K, 100K and 1,000K files and the absolute time \nvaries with different sized indexes, but the percentage is relatively \nconsistent (after doing multiple runs and averaging the results to \nreduce noise).  I didn't measure it with split index so can't say how \nthat would impact performance.\n\n> In general, I get very skeptical towards any change that makes the\n> integrity of the data less certain based only on microbenchmarks,\n> and prefer to see a solution that can absorb the overhead in some\n> other way.\n> \n> When we are using split-index, the current code is not validating\n> the two input files from the disk. Because merge_base_index()\n> depends on the base to be properly sorted before the overriding\n> entries are added into it, if the input from disk is in a wrong\n> order, we are screwed already, and the order check in post\n> processing is pointless.  \n\nThe original commit message doesn't say *why* this test was added so I \nhave to make some educated guesses.  Given no attempt is made to recover \nor continue and instead we just die when an out-of-order entry is \ndetected, I'm assuming check_ce_order() is protecting against buggy code \nthat incorrectly wrote out an invalid index (the sha check would have \ndetected file corruption or torn writes).\n\nIf we are guarding against \"git\" writing out an invalid index, we can \nmove this into an assert so that only git developers pay the cost of \nvalidating they haven't created a new bug.  I think this is better than \njust adding a new test case as a new test case would not achieve the \nsame coverage.  This is my preferred solution.\n\nIf we are guarding against \"some other application\" writing out an \ninvalid index, then everyone will have to pay the cost as we can't \ninsert the test into \"some other applications.\"  Without user reports of \nit happening or any telemetry saying it has happened I really have no \nidea if it every actually happens in the wild anymore and whether the \ncost on every index load is still justified.\n\n> If we want to do this order validation, I\n> think we should be doing it in do_read_index() where it does\n> create_from_disk() and the set_index_entry(), instead of having it\n> as a separate phase that scans a potentially large index array one\n> more time.  And doing so will not penalize the case where we do not\n> use split-index, either.\n> \n> So, I think I like the direction of getting rid of the order\n> validation in post_read_index_from(), not only during the normal\n> operation but also in fsck.  I think it makes more sense to do so\n> incrementally inside do_read_index() all the time and see how fast\n> we can make it do so.\n> \n\nUnfortunately, all the cost is in the strcmp() - the other tests are \nnegligible so moving it to be done incrementally inside do_read_index() \nwon't reduce the cost, it just moves it and makes it harder to identify.\n\nThe only idea I could come up with for reducing the cost to our end \nusers is to keep it separate and split the test across multiple threads \nwith some minimum index size threshold as we have done elsewhere.  This \nadds code and complexity that we'll have to maintain forever so is less \npreferred than making it an assert.\n\n"},{"id":"330641","messageId":"20171019160532.54teojqnhkeo2yfv@sigill.intra.peff.net","threadId":"46993","inReplyTo":"db8da340-f8f5-0114-392d-e415b5564993@gmail.com","subject":"Re: [PATCH v1] read_index_from(): Skip verification of the cache entry order to speed index loading","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2017-10-19T16:05:32Z","receivedAt":"2017-10-19T16:05:39Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Oct 19, 2017 at 11:12:03AM -0400, Ben Peart wrote:\n\n> > So, I think I like the direction of getting rid of the order\n> > validation in post_read_index_from(), not only during the normal\n> > operation but also in fsck.  I think it makes more sense to do so\n> > incrementally inside do_read_index() all the time and see how fast\n> > we can make it do so.\n> \n> Unfortunately, all the cost is in the strcmp() - the other tests are\n> negligible so moving it to be done incrementally inside do_read_index()\n> won't reduce the cost, it just moves it and makes it harder to identify.\n\nIt's plausible that doing the strcmp() closer to where we are otherwise\nmanipulating the data may show an improvement due to memory cache\neffects.\n\nIt should be easy enough to check that; the patch below implements it.\nI couldn't measure any speedup with it running \"git ls-files >/dev/null\"\non linux.git (60k files). But nor could I get any by dropping the check\nentirely.\n\nThis is mostly just a curiosity to me. For the record, I have no real\nproblem with dropping this kind of on-disk data-structure validation\nwhen it's expensive. After all, we do not check the sort on pack .idx\nfiles on each run (nor pack sha1 checksums, etc) because it's too\nexpensive to do so.\n\n---\ndiff --git a/read-cache.c b/read-cache.c\nindex 65f4fe8375..ac8c8d2e93 100644\n--- a/read-cache.c\n+++ b/read-cache.c\n@@ -1664,25 +1664,19 @@ static struct cache_entry *create_from_disk(struct ondisk_cache_entry *ondisk,\n \treturn ce;\n }\n \n-static void check_ce_order(struct index_state *istate)\n-{\n-\tunsigned int i;\n-\n-\tfor (i = 1; i < istate->cache_nr; i++) {\n-\t\tstruct cache_entry *ce = istate->cache[i - 1];\n-\t\tstruct cache_entry *next_ce = istate->cache[i];\n-\t\tint name_compare = strcmp(ce->name, next_ce->name);\n-\n-\t\tif (0 < name_compare)\n-\t\t\tdie(\"unordered stage entries in index\");\n-\t\tif (!name_compare) {\n-\t\t\tif (!ce_stage(ce))\n-\t\t\t\tdie(\"multiple stage entries for merged file '%s'\",\n-\t\t\t\t    ce->name);\n-\t\t\tif (ce_stage(ce) > ce_stage(next_ce))\n-\t\t\t\tdie(\"unordered stage entries for '%s'\",\n-\t\t\t\t    ce->name);\n-\t\t}\n+static void check_ce_order(struct cache_entry *ce, struct cache_entry *next_ce)\n+{\n+\tint name_compare = strcmp(ce->name, next_ce->name);\n+\n+\tif (0 < name_compare)\n+\t\tdie(\"unordered stage entries in index\");\n+\tif (!name_compare) {\n+\t\tif (!ce_stage(ce))\n+\t\t\tdie(\"multiple stage entries for merged file '%s'\",\n+\t\t\t    ce->name);\n+\t\tif (ce_stage(ce) > ce_stage(next_ce))\n+\t\t\tdie(\"unordered stage entries for '%s'\",\n+\t\t\t    ce->name);\n \t}\n }\n \n@@ -1720,7 +1714,6 @@ static void tweak_split_index(struct index_state *istate)\n \n static void post_read_index_from(struct index_state *istate)\n {\n-\tcheck_ce_order(istate);\n \ttweak_untracked_cache(istate);\n \ttweak_split_index(istate);\n }\n@@ -1784,6 +1777,8 @@ int do_read_index(struct index_state *istate, const char *path, int must_exist)\n \n \t\tdisk_ce = (struct ondisk_cache_entry *)((char *)mmap + src_offset);\n \t\tce = create_from_disk(disk_ce, &consumed, previous_name);\n+\t\tif (i > 0)\n+\t\t\tcheck_ce_order(istate->cache[i - 1], ce);\n \t\tset_index_entry(istate, i, ce);\n \n \t\tsrc_offset += consumed;\n"},{"id":"330696","messageId":"CAGZ79kZfw7Cb8Qs4BKuESukBL8rCgmYh0=BcNYm9mXJ1LYCg0g@mail.gmail.com","threadId":"46993","inReplyTo":"db8da340-f8f5-0114-392d-e415b5564993@gmail.com","subject":"Re: [PATCH v1] read_index_from(): Skip verification of the cache entry order to speed index loading","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2017-10-19T22:14:12Z","receivedAt":"2017-10-19T22:14:18Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"On Thu, Oct 19, 2017 at 8:12 AM, Ben Peart <peartben@gmail.com> wrote:\n\n> If we are guarding against \"git\" writing out an invalid index, we can move\n> this into an assert so that only git developers pay the cost of validating\n> they haven't created a new bug.  I think this is better than just adding a\n> new test case as a new test case would not achieve the same coverage.  This\n> is my preferred solution.\n>\n> If we are guarding against \"some other application\" writing out an invalid\n> index, then everyone will have to pay the cost as we can't insert the test\n> into \"some other applications.\"  Without user reports of it happening or any\n> telemetry saying it has happened I really have no idea if it every actually\n> happens in the wild anymore and whether the cost on every index load is\n> still justified.\n\nHow well does this play out in the security realm?, c.f.\nhttps://public-inbox.org/git/20171002234517.GV19555@aiede.mtv.corp.google.com/\n"},{"id":"330706","messageId":"xmqqh8uuipsv.fsf@gitster.mtv.corp.google.com","threadId":"46993","inReplyTo":"20171019160532.54teojqnhkeo2yfv@sigill.intra.peff.net","subject":"Re: [PATCH v1] read_index_from(): Skip verification of the cache entry order to speed index loading","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2017-10-20T01:14:08Z","receivedAt":"2017-10-20T01:14:15Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King <peff@peff.net> writes:\n\n> It should be easy enough to check that; the patch below implements it.\n> I couldn't measure any speedup with it running \"git ls-files >/dev/null\"\n> on linux.git (60k files). But nor could I get any by dropping the check\n> entirely.\n\nI would expect that the speedup (due to possible cache effect)\nwouldn't be measurable if the overhead of the existing check itself\nis unmeasuably not-expensive.  No suprise here.\n\n> This is mostly just a curiosity to me. For the record, I have no real\n> problem with dropping this kind of on-disk data-structure validation\n> when it's expensive. After all, we do not check the sort on pack .idx\n> files on each run (nor pack sha1 checksums, etc) because it's too\n> expensive to do so.\n\nYes, I agree with that stance, too.  If this were expensive in the\noverall picture to be measurable, I think we are OK omitting when\nthe index is read, especially if we make sure we are not writing out\nnonsense trees out of it.  Local damage to the index is very\ncontained as long as we do not spread breakages to trees and\ncommits.\n"},{"id":"330725","messageId":"alpine.DEB.2.21.1.1710201444590.40514@virtualbox","threadId":"46993","inReplyTo":"CAGZ79kZfw7Cb8Qs4BKuESukBL8rCgmYh0=BcNYm9mXJ1LYCg0g@mail.gmail.com","subject":"Re: [PATCH v1] read_index_from(): Skip verification of the cache entry order to speed index loading","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2017-10-20T12:47:56Z","receivedAt":"2017-10-20T12:53:21Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi Stefan,\n\nOn Thu, 19 Oct 2017, Stefan Beller wrote:\n\n> On Thu, Oct 19, 2017 at 8:12 AM, Ben Peart <peartben@gmail.com> wrote:\n> \n> > If we are guarding against \"git\" writing out an invalid index, we can move\n> > this into an assert so that only git developers pay the cost of validating\n> > they haven't created a new bug.  I think this is better than just adding a\n> > new test case as a new test case would not achieve the same coverage.  This\n> > is my preferred solution.\n> >\n> > If we are guarding against \"some other application\" writing out an invalid\n> > index, then everyone will have to pay the cost as we can't insert the test\n> > into \"some other applications.\"  Without user reports of it happening or any\n> > telemetry saying it has happened I really have no idea if it every actually\n> > happens in the wild anymore and whether the cost on every index load is\n> > still justified.\n> \n> How well does this play out in the security realm?, c.f.\n> https://public-inbox.org/git/20171002234517.GV19555@aiede.mtv.corp.google.com/\n\nThat link talks about security implications from administrators accessing\nGit repositories with maliciously crafted hooks/pagers.\n\nBen's original mail talks about integrity checks of the index file, and\nhow expensive they get when you talk about any decent-sized index (read:\n*a lot* larger than Git or even Linux developers will see regularly).\n\nThe text you quoted talks about our talking out of our rear ends when we\ntalk about typical user schenarios because we simply have no telemetry or\notherwise reliable statistics.\n\nNow, I fail to see any relationship between Jonathan's mail and either of\nBen's statements.\n\nCare to enlighten me?\n\nCiao,\nDscho\n"},{"id":"330737","messageId":"CAGZ79kZ_WjnH-vM84C8cE-jS=V=p4tGSiwXX3cKwbDOUvUs_dA@mail.gmail.com","threadId":"46993","inReplyTo":"alpine.DEB.2.21.1.1710201444590.40514@virtualbox","subject":"Re: [PATCH v1] read_index_from(): Skip verification of the cache entry order to speed index loading","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2017-10-20T18:53:25Z","receivedAt":"2017-10-20T18:53:31Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"> Ben's original mail talks about integrity checks of the index file, and\n> how expensive they get when you talk about any decent-sized index (read:\n> *a lot* larger than Git or even Linux developers will see regularly).\n\nI am quite aware of your situation.\n\n> The text you quoted talks about our talking out of our rear ends when we\n> talk about typical user schenarios because we simply have no telemetry or\n> otherwise reliable statistics.\n>\n> Now, I fail to see any relationship between Jonathan's mail and either of\n> Ben's statements.\n>\n> Care to enlighten me?\n\nThere was a recent thread (which I assumed was the one I linked), that talked\nabout security implications as soon as we loose the rather strict \"git\nis to be used\nin a posix world\", e.g. sharing your repo over NFS/Dropbox. The\nspecific question\nthat Peff asked was how the internal formats can be exploited. (Can a malicious\nindex file be crafted such that it is not just a segfault, but a\n'remote' code execution,\ngiven that you deploy the maliciously crafted file via NFS. Removing checks that\nwe already have made me a bit suspicious that it *may* be helping an\nattacker here,\nthough I have no hard data to show)\n\nSorry for the confusion,\n\nThanks,\nStefan\n"},{"id":"330760","messageId":"xmqqbml1gt7h.fsf@gitster.mtv.corp.google.com","threadId":"46993","inReplyTo":"CAGZ79kZ_WjnH-vM84C8cE-jS=V=p4tGSiwXX3cKwbDOUvUs_dA@mail.gmail.com","subject":"Re: [PATCH v1] read_index_from(): Skip verification of the cache entry order to speed index loading","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2017-10-21T01:55:46Z","receivedAt":"2017-10-21T01:55:54Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Stefan Beller <sbeller@google.com> writes:\n\n> There was a recent thread (which I assumed was the one I linked), that talked\n> about security implications as soon as we loose the rather strict \"git\n> is to be used\n> in a posix world\", e.g. sharing your repo over NFS/Dropbox. The\n> specific question\n> that Peff asked was how the internal formats can be exploited. (Can a malicious\n> index file be crafted such that it is not just a segfault, but a\n> 'remote' code execution,\n> given that you deploy the maliciously crafted file via NFS. Removing checks that\n> we already have made me a bit suspicious that it *may* be helping an\n> attacker here,\n> though I have no hard data to show)\n>\n> Sorry for the confusion,\n\nThanks for an explanation, as I had the same reaction as Dscho\ninitially.  I'd assumed that the worst would be to create a wrong\nstate (e.g. the same path registered twice with different contents\nin the index, a malformed tree written out of it, etc.), but that's\nmerely an assumption not the result of an audit.\n\n"},{"id":"330913","messageId":"20171024144544.7544-1-benpeart@microsoft.com","threadId":"46993","inReplyTo":"20171018142725.10948-1-benpeart@microsoft.com","subject":"[PATCH v2] read_index_from(): Skip verification of the cache entry order to speed index loading","fromName":"Ben Peart","fromEmail":"benpeart@microsoft.com","sentAt":"2017-10-24T14:45:44Z","receivedAt":"2017-10-24T14:46:14Z","isPatch":true,"sender":{"key":"benpeart@microsoft.com","avatar":"https://avatars.githubusercontent.com/u/15252029?v=4"},"body":"There is code in post_read_index_from() to detect out of order cache\nentries when reading an index file.  This order verification adds cost\nto read_index_from() that grows with the size of the index.\n\nPut this on-disk data-structure validation code behind an #ifdef DEBUG\nso only debug builds have to pay the cost.\n\nThe effect can be seen using t/perf/p0002-read-cache.sh:\n\nTest w/git repo                       HEAD            HEAD~1\n----------------------------------------------------------------------------\nread_cache/discard_cache 1000 times   0.42(0.01+0.09) 0.48(0.01+0.09) +14.3%\nread_cache/discard_cache 1000 times   0.41(0.03+0.04) 0.49(0.00+0.10) +19.5%\nread_cache/discard_cache 1000 times   0.42(0.03+0.06) 0.49(0.06+0.04) +16.7%\n\nTest w/10K files                      HEAD            HEAD~1\n---------------------------------------------------------------------------\nread_cache/discard_cache 1000 times   1.58(0.04+0.00) 1.71(0.00+0.07) +8.2%\nread_cache/discard_cache 1000 times   1.64(0.01+0.07) 1.76(0.01+0.09) +7.3%\nread_cache/discard_cache 1000 times   1.62(0.03+0.04) 1.71(0.00+0.04) +5.6%\n\nTest w/100K files                     HEAD             HEAD~1\n-----------------------------------------------------------------------------\nread_cache/discard_cache 1000 times   25.85(0.00+0.06) 27.35(0.01+0.06) +5.8%\nread_cache/discard_cache 1000 times   25.82(0.01+0.07) 27.25(0.01+0.07) +5.5%\nread_cache/discard_cache 1000 times   26.00(0.01+0.07) 27.36(0.06+0.03) +5.2%\n\nTest with 1,000K files                HEAD              HEAD~1\n-------------------------------------------------------------------------------\nread_cache/discard_cache 1000 times   200.61(0.01+0.07) 218.23(0.03+0.06) +8.8%\nread_cache/discard_cache 1000 times   201.62(0.03+0.06) 217.86(0.03+0.06) +8.1%\nread_cache/discard_cache 1000 times   201.64(0.01+0.09) 217.89(0.03+0.07) +8.1%\n\nSigned-off-by: Ben Peart <benpeart@microsoft.com>\nSigned-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>\n---\n\nNotes:\n    Base Ref: master\n    Web-Diff: https://github.com/benpeart/git/commit/95e20f17ff\n    Checkout: git fetch https://github.com/benpeart/git no_ce_order-v2 && git checkout 95e20f17ff\n    \n    ### Interdiff (v1..v2):\n    \n    ### Patches\n\n read-cache.c | 4 ++++\n 1 file changed, 4 insertions(+)\n\ndiff --git a/read-cache.c b/read-cache.c\nindex 65f4fe8375..fc90ec0fce 100644\n--- a/read-cache.c\n+++ b/read-cache.c\n@@ -1664,6 +1664,7 @@ static struct cache_entry *create_from_disk(struct ondisk_cache_entry *ondisk,\n \treturn ce;\n }\n \n+#ifdef DEBUG\n static void check_ce_order(struct index_state *istate)\n {\n \tunsigned int i;\n@@ -1685,6 +1686,7 @@ static void check_ce_order(struct index_state *istate)\n \t\t}\n \t}\n }\n+#endif\n \n static void tweak_untracked_cache(struct index_state *istate)\n {\n@@ -1720,7 +1722,9 @@ static void tweak_split_index(struct index_state *istate)\n \n static void post_read_index_from(struct index_state *istate)\n {\n+#ifdef DEBUG\n \tcheck_ce_order(istate);\n+#endif\n \ttweak_untracked_cache(istate);\n \ttweak_split_index(istate);\n }\n\nbase-commit: c52ca88430e6ec7c834af38720295070d8a1e330\n-- \n2.14.1.windows.1.1034.g0776750557\n\n"},{"id":"331354","messageId":"11666ccf-6406-d585-f519-7a1934c2973a@gmail.com","threadId":"46993","inReplyTo":"20171024144544.7544-1-benpeart@microsoft.com","subject":"Re: [PATCH v2] read_index_from(): Skip verification of the cache entry order to speed index loading","fromName":"Ben Peart","fromEmail":"peartben@gmail.com","sentAt":"2017-10-30T12:48:48Z","receivedAt":"2017-10-30T12:48:58Z","isPatch":true,"sender":{"key":"benpeart@microsoft.com","avatar":"https://avatars.githubusercontent.com/u/15252029?v=4"},"body":"Any updates or thoughts on this one?  While the patch has become quite \ntrivial, it does results in a savings of 5%-15% in index load time.\n\nI thought the compromise of having this test only run when DEBUG is \ndefined should limit it to developer builds (hopefully everyone \ndeveloping on git is running DEBUG builds :)).  Since the test is trying \nto detect buggy code when writing the index, I thought that was the \nright time to test/catch any issues.\n\nI am working on other, more substantial savings for index load times \n(stay tuned) but this seemed like a small simple way to help speed \nthings up.\n\nOn 10/24/2017 10:45 AM, Ben Peart wrote:\n> There is code in post_read_index_from() to detect out of order cache\n> entries when reading an index file.  This order verification adds cost\n> to read_index_from() that grows with the size of the index.\n> \n> Put this on-disk data-structure validation code behind an #ifdef DEBUG\n> so only debug builds have to pay the cost.\n> \n> The effect can be seen using t/perf/p0002-read-cache.sh:\n> \n> Test w/git repo                       HEAD            HEAD~1\n> ----------------------------------------------------------------------------\n> read_cache/discard_cache 1000 times   0.42(0.01+0.09) 0.48(0.01+0.09) +14.3%\n> read_cache/discard_cache 1000 times   0.41(0.03+0.04) 0.49(0.00+0.10) +19.5%\n> read_cache/discard_cache 1000 times   0.42(0.03+0.06) 0.49(0.06+0.04) +16.7%\n> \n> Test w/10K files                      HEAD            HEAD~1\n> ---------------------------------------------------------------------------\n> read_cache/discard_cache 1000 times   1.58(0.04+0.00) 1.71(0.00+0.07) +8.2%\n> read_cache/discard_cache 1000 times   1.64(0.01+0.07) 1.76(0.01+0.09) +7.3%\n> read_cache/discard_cache 1000 times   1.62(0.03+0.04) 1.71(0.00+0.04) +5.6%\n> \n> Test w/100K files                     HEAD             HEAD~1\n> -----------------------------------------------------------------------------\n> read_cache/discard_cache 1000 times   25.85(0.00+0.06) 27.35(0.01+0.06) +5.8%\n> read_cache/discard_cache 1000 times   25.82(0.01+0.07) 27.25(0.01+0.07) +5.5%\n> read_cache/discard_cache 1000 times   26.00(0.01+0.07) 27.36(0.06+0.03) +5.2%\n> \n> Test with 1,000K files                HEAD              HEAD~1\n> -------------------------------------------------------------------------------\n> read_cache/discard_cache 1000 times   200.61(0.01+0.07) 218.23(0.03+0.06) +8.8%\n> read_cache/discard_cache 1000 times   201.62(0.03+0.06) 217.86(0.03+0.06) +8.1%\n> read_cache/discard_cache 1000 times   201.64(0.01+0.09) 217.89(0.03+0.07) +8.1%\n> \n> Signed-off-by: Ben Peart <benpeart@microsoft.com>\n> Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>\n> ---\n> \n> Notes:\n>      Base Ref: master\n>      Web-Diff: https://github.com/benpeart/git/commit/95e20f17ff\n>      Checkout: git fetch https://github.com/benpeart/git no_ce_order-v2 && git checkout 95e20f17ff\n>      \n>      ### Interdiff (v1..v2):\n>      \n>      ### Patches\n> \n>   read-cache.c | 4 ++++\n>   1 file changed, 4 insertions(+)\n> \n> diff --git a/read-cache.c b/read-cache.c\n> index 65f4fe8375..fc90ec0fce 100644\n> --- a/read-cache.c\n> +++ b/read-cache.c\n> @@ -1664,6 +1664,7 @@ static struct cache_entry *create_from_disk(struct ondisk_cache_entry *ondisk,\n>   \treturn ce;\n>   }\n>   \n> +#ifdef DEBUG\n>   static void check_ce_order(struct index_state *istate)\n>   {\n>   \tunsigned int i;\n> @@ -1685,6 +1686,7 @@ static void check_ce_order(struct index_state *istate)\n>   \t\t}\n>   \t}\n>   }\n> +#endif\n>   \n>   static void tweak_untracked_cache(struct index_state *istate)\n>   {\n> @@ -1720,7 +1722,9 @@ static void tweak_split_index(struct index_state *istate)\n>   \n>   static void post_read_index_from(struct index_state *istate)\n>   {\n> +#ifdef DEBUG\n>   \tcheck_ce_order(istate);\n> +#endif\n>   \ttweak_untracked_cache(istate);\n>   \ttweak_split_index(istate);\n>   }\n> \n> base-commit: c52ca88430e6ec7c834af38720295070d8a1e330\n> \n"},{"id":"331398","messageId":"20171030180334.ddursnmj5wqgimqu@sigill.intra.peff.net","threadId":"46993","inReplyTo":"11666ccf-6406-d585-f519-7a1934c2973a@gmail.com","subject":"Re: [PATCH v2] read_index_from(): Skip verification of the cache entry order to speed index loading","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2017-10-30T18:03:34Z","receivedAt":"2017-10-30T18:03:48Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Oct 30, 2017 at 08:48:48AM -0400, Ben Peart wrote:\n\n> Any updates or thoughts on this one?  While the patch has become quite\n> trivial, it does results in a savings of 5%-15% in index load time.\n\nI like the general direction of avoiding the check during each read.\nBut...\n\n> I thought the compromise of having this test only run when DEBUG is defined\n> should limit it to developer builds (hopefully everyone developing on git is\n> running DEBUG builds :)).  Since the test is trying to detect buggy code\n> when writing the index, I thought that was the right time to test/catch any\n> issues.\n\nI certainly don't build with DEBUG. It traditionally hasn't done\nanything useful. But I'm also not convinced that this is a likely way to\nfind bugs in the first place, so I'm OK missing out on it.\n\nBut what we probably _do_ need is to make sure that \"git fsck\" would\ndetect such an out-of-order index. So that developers and users alike\ncan diagnose suspected problems.\n\n-Peff\n"},{"id":"331426","messageId":"alpine.DEB.2.10.1710301727160.10801@alexmv-linux","threadId":"46993","inReplyTo":"20171030180334.ddursnmj5wqgimqu@sigill.intra.peff.net","subject":"Re: [PATCH v2] read_index_from(): Skip verification of the cache entry order to speed index loading","fromName":"Alex Vandiver","fromEmail":"alexmv@dropbox.com","sentAt":"2017-10-31T00:33:39Z","receivedAt":"2017-10-31T00:33:54Z","isPatch":true,"sender":{"key":"alexmv@dropbox.com","avatar":null},"body":"On Mon, 30 Oct 2017, Jeff King wrote:\n> On Mon, Oct 30, 2017 at 08:48:48AM -0400, Ben Peart wrote:\n> \n> > Any updates or thoughts on this one?  While the patch has become quite\n> > trivial, it does results in a savings of 5%-15% in index load time.\n> \n> I like the general direction of avoiding the check during each read.\n\nSame -- the savings here are well worth it, IMHO.\n\n> > I thought the compromise of having this test only run when DEBUG is defined\n> > should limit it to developer builds (hopefully everyone developing on git is\n> > running DEBUG builds :)).  Since the test is trying to detect buggy code\n> > when writing the index, I thought that was the right time to test/catch any\n> > issues.\n> \n> I certainly don't build with DEBUG. It traditionally hasn't done\n> anything useful. But I'm also not convinced that this is a likely way to\n> find bugs in the first place, so I'm OK missing out on it.\n\nI also don't compile with DEBUG -- there's no documentation that\nmentions it, and I don't think I'd considered going poking for what\nwas `#ifdef`d.  I think it'd be reasonable to provide some\nconfigure-time setting that adds `CFLAGS=\"-ggdb3 -O0 -DDEBUG\"` or\nsimilar, but that seems possibly moot for this particular change (see\nbelow).\n\n> But what we probably _do_ need is to make sure that \"git fsck\" would\n> detect such an out-of-order index. So that developers and users alike\n> can diagnose suspected problems.\n\nAgree -- that seems like a better home for this logic.\n\n> > I am working on other, more substantial savings for index load times\n> > (stay tuned) but this seemed like a small simple way to help speed\n> > things up.\n\nI'm interested to hear more about what direction you're looking in here.\n - Alex\n"},{"id":"331438","messageId":"xmqq8tfs3x3m.fsf@gitster.mtv.corp.google.com","threadId":"46993","inReplyTo":"11666ccf-6406-d585-f519-7a1934c2973a@gmail.com","subject":"Re: [PATCH v2] read_index_from(): Skip verification of the cache entry order to speed index loading","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2017-10-31T01:49:33Z","receivedAt":"2017-10-31T01:49:50Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Ben Peart <peartben@gmail.com> writes:\n\n> Any updates or thoughts on this one?  While the patch has become quite\n> trivial, it does results in a savings of 5%-15% in index load time.\n>\n> I thought the compromise of having this test only run when DEBUG is\n> defined should limit it to developer builds (hopefully everyone\n> developing on git is running DEBUG builds :)).  Since the test is\n> trying to detect buggy code when writing the index, I thought that was\n> the right time to test/catch any issues.\n\nThis check is more about catching a possible breakage (and a\nmalicious repository) early before we go too far into the operation.\nI do not think this check is about debugging the implementation of\nGit.  How would it be useful to turn it on in DEBUG build?\n\nWhile I do think pursuing any runtime improvements better than a\ncouple of percents is worth it, I do not think the approach taken by\nthis iteration makes much sense; the previous one that at least\nallowed fsck to catch breakage may have been already too leaky to\ncatch real issues (i.e. when you are asked to visit and look at an\nunknown repository, you wouldn't start your session with \"git fsck\"\nto protect yourself), and this round makes it much worse.\n\nBesides, I see no -DDEBUG from \"grep -e '-D[A-Z]*DEBUG' Makefile\".\nIf this check were about allowing us easier time debugging the\nbinary (which I do not think it is), this probably should be\n'#ifndef NDEBUG' instead.\n"},{"id":"331469","messageId":"8e268809-b596-fd1c-1f39-e040743596cb@gmail.com","threadId":"46993","inReplyTo":"xmqq8tfs3x3m.fsf@gitster.mtv.corp.google.com","subject":"Re: [PATCH v2] read_index_from(): Skip verification of the cache entry order to speed index loading","fromName":"Ben Peart","fromEmail":"peartben@gmail.com","sentAt":"2017-10-31T12:51:59Z","receivedAt":"2017-10-31T12:52:11Z","isPatch":true,"sender":{"key":"benpeart@microsoft.com","avatar":"https://avatars.githubusercontent.com/u/15252029?v=4"},"body":"\n\nOn 10/30/2017 9:49 PM, Junio C Hamano wrote:\n> Ben Peart <peartben@gmail.com> writes:\n> \n>> Any updates or thoughts on this one?  While the patch has become quite\n>> trivial, it does results in a savings of 5%-15% in index load time.\n>>\n>> I thought the compromise of having this test only run when DEBUG is\n>> defined should limit it to developer builds (hopefully everyone\n>> developing on git is running DEBUG builds :)).  Since the test is\n>> trying to detect buggy code when writing the index, I thought that was\n>> the right time to test/catch any issues.\n> \n> This check is more about catching a possible breakage (and a\n> malicious repository) early before we go too far into the operation.\n> I do not think this check is about debugging the implementation of\n> Git.  How would it be useful to turn it on in DEBUG build?\n> \n> While I do think pursuing any runtime improvements better than a\n> couple of percents is worth it, I do not think the approach taken by\n> this iteration makes much sense; the previous one that at least\n> allowed fsck to catch breakage may have been already too leaky to\n> catch real issues (i.e. when you are asked to visit and look at an\n> unknown repository, you wouldn't start your session with \"git fsck\"\n> to protect yourself), and this round makes it much worse.\n> \n> Besides, I see no -DDEBUG from \"grep -e '-D[A-Z]*DEBUG' Makefile\".\n> If this check were about allowing us easier time debugging the\n> binary (which I do not think it is), this probably should be\n> '#ifndef NDEBUG' instead.\n> \n\nI've tried 3 different ways to remove the overhead of this call from \nregular git operations.\n\nThe first was version 1 of the patch which had fsck catch breakage but \nremoved it from other commands that read the index.  Since that version \nwas not accepted, I took the feedback \"I think I like the direction of \ngetting rid of the order in post_read_index_from(), not only during the \nnormal but also in fsck\" to come up with a version 2.\n\nI was hesitant to remove the code completely as I did believe it had \nsome value in detecting invalid indexes so went looking for a macro I \ncould use to have it 1) not happen during regular user commands but 2) \nstill happen for developers.\n\nThe NDEBUG macro is guaranteed by the C89 standard \n(http://port70.net/~nsz/c/c89/c89-draft.html#4.1.2 ) to guard the code \nthat is only necessary when assertions are in effect so seemed like a \ngood choice.  When I used it however, I discovered that the git Makefile \ndoes not define NDEBUG so using this macro did not have any effect thus \nmaking the patch useless as the code continues to run in all cases.\n\nOn a side note, there are 434 instances of assert which up until this \nexperience I believed were being removed in released builds.  As far as \nI can tell, that is not the case.  If removing them is the \ndesired/expected behavior, we need to fix our Makefile as it only \ncurrently defines NDEBUG if USE_NED_ALLOCATOR is defined.\n\nI then searched the code and found 47 instances where the macro DEBUG \nwas used.  I (incorrectly) assumed that meant it must be used by other \ngit developers.  I personally have a build alias that adds \"-j12 \nCFLAGS=-DDEBUG\" to my make command but apparently I'm in the minority. :)\n\nThis assumption led me to the patch version 2 (guarding the code with \n#ifdef DEBUG) as it does meet the request to remove it during normal but \nalso fsck and does so with regular/release builds as they are currently \ndefined.\n\nIt seems that the current round of feedback is more in favor of leaving \nthe test in fsck but removing it for other commands.  If that is the \ndesired behavior, please use version 1 of the patch.\n\nI'm also happy to flip this to \"#ifndef NDEBUG\" but that only makes \nsense if the released builds actually set NDEBUG which (I believe) will \nrequire a patch to Makefile.\n\n"},{"id":"331470","messageId":"f671ea09-d4aa-64aa-8225-c1fbf2eac175@gmail.com","threadId":"46993","inReplyTo":"alpine.DEB.2.10.1710301727160.10801@alexmv-linux","subject":"Re: [PATCH v2] read_index_from(): Skip verification of the cache entry order to speed index loading","fromName":"Ben Peart","fromEmail":"peartben@gmail.com","sentAt":"2017-10-31T13:01:45Z","receivedAt":"2017-10-31T13:01:55Z","isPatch":true,"sender":{"key":"benpeart@microsoft.com","avatar":"https://avatars.githubusercontent.com/u/15252029?v=4"},"body":"\n\nOn 10/30/2017 8:33 PM, Alex Vandiver wrote:\n> On Mon, 30 Oct 2017, Jeff King wrote:\n>> On Mon, Oct 30, 2017 at 08:48:48AM -0400, Ben Peart wrote:\n>>\n>>> Any updates or thoughts on this one?  While the patch has become quite\n>>> trivial, it does results in a savings of 5%-15% in index load time.\n>>\n>> I like the general direction of avoiding the check during each read.\n> \n> Same -- the savings here are well worth it, IMHO.\n> \n>>> I thought the compromise of having this test only run when DEBUG is defined\n>>> should limit it to developer builds (hopefully everyone developing on git is\n>>> running DEBUG builds :)).  Since the test is trying to detect buggy code\n>>> when writing the index, I thought that was the right time to test/catch any\n>>> issues.\n>>\n>> I certainly don't build with DEBUG. It traditionally hasn't done\n>> anything useful. But I'm also not convinced that this is a likely way to\n>> find bugs in the first place, so I'm OK missing out on it.\n> \n> I also don't compile with DEBUG -- there's no documentation that\n> mentions it, and I don't think I'd considered going poking for what\n> was `#ifdef`d.  I think it'd be reasonable to provide some\n> configure-time setting that adds `CFLAGS=\"-ggdb3 -O0 -DDEBUG\"` or\n> similar, but that seems possibly moot for this particular change (see\n> below).\n> \n>> But what we probably _do_ need is to make sure that \"git fsck\" would\n>> detect such an out-of-order index. So that developers and users alike\n>> can diagnose suspected problems.\n> \n> Agree -- that seems like a better home for this logic.\n\nThat is how version 1 of this patch worked but the feedback to that \npatch was to remove it \"not only during the normal operation but also in \nfsck.\"\n\n> \n>>> I am working on other, more substantial savings for index load times\n>>> (stay tuned) but this seemed like a small simple way to help speed\n>>> things up.\n> \n> I'm interested to hear more about what direction you're looking in here.\n>   - Alex\n> \n\nI'm working on parallelizing the index load process across multiple \nthreads/cpu cores.  Specifically the loop that calls create_from_disk() \nand set_index_entry().  The serial nature of the index formats makes \nthat difficult but I believe I've come up with a way to make it work \nacross all existing index formats.\n"},{"id":"331482","messageId":"20171031171058.vs5aau5x26ebx7kq@sigill.intra.peff.net","threadId":"46993","inReplyTo":"f671ea09-d4aa-64aa-8225-c1fbf2eac175@gmail.com","subject":"Re: [PATCH v2] read_index_from(): Skip verification of the cache entry order to speed index loading","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2017-10-31T17:10:59Z","receivedAt":"2017-10-31T17:11:06Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Oct 31, 2017 at 09:01:45AM -0400, Ben Peart wrote:\n\n> > > But what we probably _do_ need is to make sure that \"git fsck\" would\n> > > detect such an out-of-order index. So that developers and users alike\n> > > can diagnose suspected problems.\n> > \n> > Agree -- that seems like a better home for this logic.\n> \n> That is how version 1 of this patch worked but the feedback to that patch\n> was to remove it \"not only during the normal operation but also in fsck.\"\n\nSorry for the mixed messages (I think they are mixed between different\npeople, and not mixed _just_ from me ;) ).\n\nFor what it's worth, I like your v1, but can live with either approach.\n\n-Peff\n"},{"id":"331545","messageId":"xmqqo9omttr2.fsf@gitster.mtv.corp.google.com","threadId":"46993","inReplyTo":"20171031171058.vs5aau5x26ebx7kq@sigill.intra.peff.net","subject":"Re: [PATCH v2] read_index_from(): Skip verification of the cache entry order to speed index loading","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2017-11-01T06:09:37Z","receivedAt":"2017-11-01T06:09:50Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King <peff@peff.net> writes:\n\n> On Tue, Oct 31, 2017 at 09:01:45AM -0400, Ben Peart wrote:\n>\n>> > > But what we probably _do_ need is to make sure that \"git fsck\" would\n>> > > detect such an out-of-order index. So that developers and users alike\n>> > > can diagnose suspected problems.\n>> > \n>> > Agree -- that seems like a better home for this logic.\n>> \n>> That is how version 1 of this patch worked but the feedback to that patch\n>> was to remove it \"not only during the normal operation but also in fsck.\"\n>\n> Sorry for the mixed messages (I think they are mixed between different\n> people, and not mixed _just_ from me ;) ).\n>\n> For what it's worth, I like your v1, but can live with either approach.\n\nI agree that v1 is the less bad one between the two.\n\nTo be honest, if the original code were done in that way (i.e. the\nstate with v1 applied), I probably would have had a very hard time\nto justify accepting a patch to \"make it safer by always checking at\nruntime\" (i.e. a reverse of v1 patch).\n\nSo, let's go with v1.  Thanks, all.\n\n"}]}