[PATCH v2 0/2] read-cache: call verify_hdr() in a background thread

[PATCH v2 0/2] read-cache: call verify_hdr() in a background thread

[git]

From: Jeff Hostetler <jeffhost@microsoft.com>

Version 2 of this patch series simplifies this to just
turn off the hash verification.  Independent comments
from Linus and Peff suggested that we could just turn
this off and not worry about it.  So I've updated this
patch to do that.  I added a global variable to allow
the original code path to be used.  I also added a
t/helper command to demonstrate the differences.

On the Linux repo, the effect is rather trivial:

    $ ~/work/gfw/t/helper/test-skip-verify-index -c 3
    0.029884 0 [cache_nr 57994]
    0.031035 0 [cache_nr 57994]
    0.024308 0 [cache_nr 57994]
    0.028409 0 avg
    0.018359 1 [cache_nr 57994]
    0.017025 1 [cache_nr 57994]
    0.011087 1 [cache_nr 57994]
    0.015490 1 avg

On my Windows source tree (450MB index), I'm seeing a
savings of 0.6 seconds -- read_index() went from 1.2 to 0.6
seconds.

=====================

This patch contains a performance optimization to run
verify_hdr() in a background thread while the foreground
thread parses the index.  This allows do_read_index() to
complete faster.

This idea was recently discussed on the mailing list in:
https://public-inbox.org/git/85221b97-759f-b7a9-1256-21515d163cbf@jeffhostetler.com/
during a discussion on sha1dc.

Our testing on Windows showed that verifying the SHA1 hash
on the index file takes approximately the same amount of time
as parsing the file and building the array of cache_entries.
(It could also be that having 2 threads better ammortizes the
page faults of reading from the mmap'd file.)

An earlier version of this change has been in use in GfW since December:
https://github.com/git-for-windows/git/pull/978

Jeff Hostetler (2):
  read-cache: skip index SHA verification
  skip_verify_index: helper test

 Makefile                          |  1 +
 cache.h                           |  5 +++
 read-cache.c                      |  6 ++++
 t/helper/.gitignore               |  1 +
 t/helper/test-skip-verify-index.c | 73 +++++++++++++++++++++++++++++++++++++++
 5 files changed, 86 insertions(+)
 create mode 100644 t/helper/test-skip-verify-index.c

-- 
2.7.4

[PATCH v2 1/2] read-cache: skip index SHA verification

[git]

From: Jeff Hostetler <jeffhost@microsoft.com>

Teach git to skip verification of the index SHA in read_index().

This is a performance optimization.  The index file SHA verification
can be considered an ancient relic from the early days of git and only
useful for detecting disk corruption.  For small repositories, this
SHA calculation is not that significant, but for gigantic repositories
this calculation adds significant time to every command.

I added a global "skip_verify_index" variable to control this and
allow it to be tested.

I did not create a config setting for this because of chicken-n-egg
problems with the loading the config and the index.

Signed-off-by: Jeff Hostetler <jeffhost@microsoft.com>
---
 cache.h      | 5 +++++
 read-cache.c | 6 ++++++
 2 files changed, 11 insertions(+)

diff --git a/cache.h b/cache.h
index 80b6372..4e9182f 100644
--- a/cache.h
+++ b/cache.h
@@ -740,6 +740,11 @@ extern int protect_ntfs;
 extern int git_db_env, git_index_env, git_graft_env, git_common_dir_env;
 
 /*
+ * When set, skip verification of the index SHA in read_index().
+ */
+extern int skip_verify_index;
+
+/*
  * Include broken refs in all ref iterations, which will
  * generally choke dangerous operations rather than letting
  * them silently proceed without taking the broken ref into
diff --git a/read-cache.c b/read-cache.c
index 9054369..1ca69c3 100644
--- a/read-cache.c
+++ b/read-cache.c
@@ -46,6 +46,8 @@
 struct index_state the_index;
 static const char *alternate_index_output;
 
+int skip_verify_index = 1;
+
 static void set_index_entry(struct index_state *istate, int nr, struct cache_entry *ce)
 {
 	istate->cache[nr] = ce;
@@ -1382,6 +1384,10 @@ static int verify_hdr(struct cache_header *hdr, unsigned long size)
 	hdr_version = ntohl(hdr->hdr_version);
 	if (hdr_version < INDEX_FORMAT_LB || INDEX_FORMAT_UB < hdr_version)
 		return error("bad index version %d", hdr_version);
+
+	if (skip_verify_index)
+		return 0;
+
 	git_SHA1_Init(&c);
 	git_SHA1_Update(&c, hdr, size - 20);
 	git_SHA1_Final(sha1, &c);
-- 
2.7.4

[PATCH v2 2/2] skip_verify_index: helper test

[git]

From: Jeff Hostetler <jeffhost@microsoft.com>

Created test to measure read_index() with and without
skip_verify_index set and report performance differences.

Signed-off-by: Jeff Hostetler <jeffhost@microsoft.com>
---
 Makefile                          |  1 +
 t/helper/.gitignore               |  1 +
 t/helper/test-skip-verify-index.c | 73 +++++++++++++++++++++++++++++++++++++++
 3 files changed, 75 insertions(+)
 create mode 100644 t/helper/test-skip-verify-index.c

diff --git a/Makefile b/Makefile
index 9ec6065..e4932b6 100644
--- a/Makefile
+++ b/Makefile
@@ -631,6 +631,7 @@ TEST_PROGRAMS_NEED_X += test-scrap-cache-tree
 TEST_PROGRAMS_NEED_X += test-sha1
 TEST_PROGRAMS_NEED_X += test-sha1-array
 TEST_PROGRAMS_NEED_X += test-sigchain
+TEST_PROGRAMS_NEED_X += test-skip-verify-index
 TEST_PROGRAMS_NEED_X += test-string-list
 TEST_PROGRAMS_NEED_X += test-submodule-config
 TEST_PROGRAMS_NEED_X += test-subprocess
diff --git a/t/helper/.gitignore b/t/helper/.gitignore
index d6e8b36..4d2ed3c 100644
--- a/t/helper/.gitignore
+++ b/t/helper/.gitignore
@@ -25,6 +25,7 @@
 /test-sha1
 /test-sha1-array
 /test-sigchain
+/test-skip-verify-index
 /test-string-list
 /test-submodule-config
 /test-subprocess
diff --git a/t/helper/test-skip-verify-index.c b/t/helper/test-skip-verify-index.c
new file mode 100644
index 0000000..ec2db27
--- /dev/null
+++ b/t/helper/test-skip-verify-index.c
@@ -0,0 +1,73 @@
+#include "cache.h"
+#include "parse-options.h"
+
+uint64_t time_runs(int count)
+{
+	uint64_t t0, t1;
+	uint64_t sum = 0;
+	uint64_t avg;
+	int i;
+
+	for (i = 0; i < count; i++) {
+		t0 = getnanotime();
+		read_cache();
+		t1 = getnanotime();
+
+		sum += (t1 - t0);
+
+		printf("%f %d [cache_nr %d]\n",
+			   ((double)(t1 - t0))/1000000000,
+			   skip_verify_index,
+			   the_index.cache_nr);
+		fflush(stdout);
+
+		discard_cache();
+	}
+
+	avg = sum / count;
+	if (count > 1) {
+		printf("%f %d avg\n",
+			   (double)avg/1000000000,
+			   skip_verify_index);
+		fflush(stdout);
+	}
+
+	return avg;
+}
+
+int cmd_main(int argc, const char **argv)
+{
+	int count = 1;
+	const char *usage[] = {
+		"test-core-verify-index",
+		NULL
+	};
+	struct option options[] = {
+		OPT_INTEGER('c', "count", &count, "number of passes"),
+		OPT_END(),
+	};
+	const char *prefix;
+	uint64_t avg_no_skip, avg_skip;
+
+	prefix = setup_git_directory();
+	argc = parse_options(argc, argv, prefix, options, usage, 0);
+
+	if (count < 1)
+		die("count must greater than zero");
+
+	/* throw away call to get the index in the disk cache */
+	read_cache();
+	discard_cache();
+
+	/* disable index SHA verification */
+	skip_verify_index = 0;
+	avg_no_skip = time_runs(count);
+
+	/* enable index SHA verification */
+	skip_verify_index = 1;
+	avg_skip = time_runs(count);
+
+	if (avg_skip > avg_no_skip)
+		die("skipping index SHA verification did not help");
+	return 0;
+}
-- 
2.7.4

Re: [PATCH v2 1/2] read-cache: skip index SHA verification

[Jeff King]

On Mon, Mar 27, 2017 at 09:09:38PM +0000, git@jeffhostetler.com wrote:

> From: Jeff Hostetler <jeffhost@microsoft.com>
> 
> Teach git to skip verification of the index SHA in read_index().
> 
> This is a performance optimization.  The index file SHA verification
> can be considered an ancient relic from the early days of git and only
> useful for detecting disk corruption.  For small repositories, this
> SHA calculation is not that significant, but for gigantic repositories
> this calculation adds significant time to every command.
> 
> I added a global "skip_verify_index" variable to control this and
> allow it to be tested.
> 
> I did not create a config setting for this because of chicken-n-egg
> problems with the loading the config and the index.

Hrm, there shouldn't be any dependency of the config on the index (and
there are a handful of options which impact the index already). Did you
try it and run into problems?

In general, I'd much rather see us either:

  1. Rip the code out entirely if it is not meant to be configurable,
     and cannot be triggered by the actual git binary.

or

  2. Make it configurable, even if most people wouldn't use it. And then
     have a test to exercise it using a git command (unlike the one-off
     test helper, which isn't run at all).

-Peff

Re: [PATCH v2 0/2] read-cache: call verify_hdr() in a background thread

[Jeff King]

On Mon, Mar 27, 2017 at 09:09:37PM +0000, git@jeffhostetler.com wrote:

> From: Jeff Hostetler <jeffhost@microsoft.com>
> 
> Version 2 of this patch series simplifies this to just
> turn off the hash verification.  Independent comments
> from Linus and Peff suggested that we could just turn
> this off and not worry about it.  So I've updated this
> patch to do that.  I added a global variable to allow
> the original code path to be used.  I also added a
> t/helper command to demonstrate the differences.
> 
> On the Linux repo, the effect is rather trivial:
> 
>     $ ~/work/gfw/t/helper/test-skip-verify-index -c 3
>     0.029884 0 [cache_nr 57994]
>     0.031035 0 [cache_nr 57994]
>     0.024308 0 [cache_nr 57994]
>     0.028409 0 avg
>     0.018359 1 [cache_nr 57994]
>     0.017025 1 [cache_nr 57994]
>     0.011087 1 [cache_nr 57994]
>     0.015490 1 avg
> 
> On my Windows source tree (450MB index), I'm seeing a
> savings of 0.6 seconds -- read_index() went from 1.2 to 0.6
> seconds.

Very satisfying. I assume that was with OpenSSL as the SHA-1
implementation (sha1dc would have been much slower on 450MB, I think).

-Peff

Re: [PATCH v2 1/2] read-cache: skip index SHA verification

[Jonathan Nieder]

Jeff King wrote:

> Hrm, there shouldn't be any dependency of the config on the index (and
> there are a handful of options which impact the index already). Did you
> try it and run into problems?
>
> In general, I'd much rather see us either:
>
>   1. Rip the code out entirely if it is not meant to be configurable,
>      and cannot be triggered by the actual git binary.
>
> or
>
>   2. Make it configurable, even if most people wouldn't use it. And then
>      have a test to exercise it using a git command (unlike the one-off
>      test helper, which isn't run at all).

Agreed with this, leaning toward (1).

If "git fsck" verifies the .git/index file then I don't see any need
for other commands to.

Thanks and hope that helps,
Jonathan

Re: [PATCH v2 1/2] read-cache: skip index SHA verification

[Jeff King]

On Mon, Mar 27, 2017 at 04:32:10PM -0700, Jonathan Nieder wrote:

> Jeff King wrote:
> 
> > Hrm, there shouldn't be any dependency of the config on the index (and
> > there are a handful of options which impact the index already). Did you
> > try it and run into problems?
> >
> > In general, I'd much rather see us either:
> >
> >   1. Rip the code out entirely if it is not meant to be configurable,
> >      and cannot be triggered by the actual git binary.
> >
> > or
> >
> >   2. Make it configurable, even if most people wouldn't use it. And then
> >      have a test to exercise it using a git command (unlike the one-off
> >      test helper, which isn't run at all).
> 
> Agreed with this, leaning toward (1).
> 
> If "git fsck" verifies the .git/index file then I don't see any need
> for other commands to.

Yeah, code that _can_ be run but almost nobody does is possibly worse
than code that can't be run. :)

I agree that it would make sense for fsck to check it, though (just like
it checks the actual pack trailer checksums, even though normal
operations do not).

-Peff

Re: [PATCH v2 1/2] read-cache: skip index SHA verification

[Jeff Hostetler]

On 3/27/2017 6:44 PM, Jeff King wrote:
> On Mon, Mar 27, 2017 at 09:09:38PM +0000, git@jeffhostetler.com wrote:
>
>> From: Jeff Hostetler <jeffhost@microsoft.com>
>>
>> Teach git to skip verification of the index SHA in read_index().
>>
>> This is a performance optimization.  The index file SHA verification
>> can be considered an ancient relic from the early days of git and only
>> useful for detecting disk corruption.  For small repositories, this
>> SHA calculation is not that significant, but for gigantic repositories
>> this calculation adds significant time to every command.
>>
>> I added a global "skip_verify_index" variable to control this and
>> allow it to be tested.
>>
>> I did not create a config setting for this because of chicken-n-egg
>> problems with the loading the config and the index.
>
> Hrm, there shouldn't be any dependency of the config on the index (and
> there are a handful of options which impact the index already). Did you
> try it and run into problems?

Yeah, I tried adding a new "core.verifyindex" property and the
corresponding global variable.  But read_index() and verify_hdr()
was being called BEFORE the config was loaded.  And it wasn't clear
how best to solve that.

The issue was in "git status" where cmd_status() called
status_init_config() which called gitmodules_config() before
git_config().  but gitmodules_config() called read_index(),
so my settings weren't loaded yet in verify_hdr().

I tried switching the order in status_init_config(), but
that caused errors in t7508 with submodules not being handled
properly.

https://github.com/jeffhostetler/git/commits/upstream/core_verify_index

At this point I decided that it wasn't that important to have
this config setting, since we'll probably default it to be faster
and be done with it.

>
> In general, I'd much rather see us either:
>
>   1. Rip the code out entirely if it is not meant to be configurable,
>      and cannot be triggered by the actual git binary.
>
> or
>
>   2. Make it configurable, even if most people wouldn't use it. And then
>      have a test to exercise it using a git command (unlike the one-off
>      test helper, which isn't run at all).
>
> -Peff
>

I'm OK with (1) if everyone else is.

Jeff

Re: [PATCH v2 0/2] read-cache: call verify_hdr() in a background thread

[Jeff Hostetler]

On 3/27/2017 6:45 PM, Jeff King wrote:
> On Mon, Mar 27, 2017 at 09:09:37PM +0000, git@jeffhostetler.com wrote:
>
>> From: Jeff Hostetler <jeffhost@microsoft.com>
>>
>> Version 2 of this patch series simplifies this to just
>> turn off the hash verification.  Independent comments
>> from Linus and Peff suggested that we could just turn
>> this off and not worry about it.  So I've updated this
>> patch to do that.  I added a global variable to allow
>> the original code path to be used.  I also added a
>> t/helper command to demonstrate the differences.
>>
>> On the Linux repo, the effect is rather trivial:
>>
>>     $ ~/work/gfw/t/helper/test-skip-verify-index -c 3
>>     0.029884 0 [cache_nr 57994]
>>     0.031035 0 [cache_nr 57994]
>>     0.024308 0 [cache_nr 57994]
>>     0.028409 0 avg
>>     0.018359 1 [cache_nr 57994]
>>     0.017025 1 [cache_nr 57994]
>>     0.011087 1 [cache_nr 57994]
>>     0.015490 1 avg
>>
>> On my Windows source tree (450MB index), I'm seeing a
>> savings of 0.6 seconds -- read_index() went from 1.2 to 0.6
>> seconds.
>
> Very satisfying. I assume that was with OpenSSL as the SHA-1
> implementation (sha1dc would have been much slower on 450MB, I think).
>
> -Peff
>

Yes, this was with the OpenSSL SHA-1 code in a GfW build.
I haven't played with the sha1dc code yet.

$ $/work/gh_gfw/t/helper/test-skip-verify-index.exe -c 5
1.276485 0 [cache_nr 3077831]
1.261164 0 [cache_nr 3077831]
1.256012 0 [cache_nr 3077831]
1.261411 0 [cache_nr 3077831]
1.266174 0 [cache_nr 3077831]
1.264249 0 avg
0.672057 1 [cache_nr 3077831]
0.666968 1 [cache_nr 3077831]
0.668725 1 [cache_nr 3077831]
0.675879 1 [cache_nr 3077831]
0.670213 1 [cache_nr 3077831]
0.670768 1 avg

Jeff

Re: [PATCH v2 1/2] read-cache: skip index SHA verification

[Jeff King]

On Tue, Mar 28, 2017 at 11:27:19AM -0400, Jeff Hostetler wrote:

> > Hrm, there shouldn't be any dependency of the config on the index (and
> > there are a handful of options which impact the index already). Did you
> > try it and run into problems?
> 
> Yeah, I tried adding a new "core.verifyindex" property and the
> corresponding global variable.  But read_index() and verify_hdr()
> was being called BEFORE the config was loaded.  And it wasn't clear
> how best to solve that.
> 
> The issue was in "git status" where cmd_status() called
> status_init_config() which called gitmodules_config() before
> git_config().  but gitmodules_config() called read_index(),
> so my settings weren't loaded yet in verify_hdr().

Ugh, yeah, the callback-oriented interface suffers from these kind of
dependency cycles. You can fix it by doing a limited "basic config that
should always be loaded" git_config() call before anything else, and
then following up with the application-level config.

For something low-level that should _always_ be respected, even in
plumbing programs, I think we're better off lazy-loading the config
inside the function. The configset cache makes them more or less free.

I.e., something like:

diff --git a/read-cache.c b/read-cache.c
index e44775182..89bbf8d1e 100644
--- a/read-cache.c
+++ b/read-cache.c
@@ -1376,17 +1376,23 @@ static int verify_hdr(struct cache_header *hdr, unsigned long size)
 	git_SHA_CTX c;
 	unsigned char sha1[20];
 	int hdr_version;
+	int do_checksum = 0;
 
 	if (hdr->hdr_signature != htonl(CACHE_SIGNATURE))
 		return error("bad signature");
 	hdr_version = ntohl(hdr->hdr_version);
 	if (hdr_version < INDEX_FORMAT_LB || INDEX_FORMAT_UB < hdr_version)
 		return error("bad index version %d", hdr_version);
-	git_SHA1_Init(&c);
-	git_SHA1_Update(&c, hdr, size - 20);
-	git_SHA1_Final(sha1, &c);
-	if (hashcmp(sha1, (unsigned char *)hdr + size - 20))
-		return error("bad index file sha1 signature");
+
+	git_config_get_bool("core.checksumindex", &do_checksum);
+	if (do_checksum) {
+		git_SHA1_Init(&c);
+		git_SHA1_Update(&c, hdr, size - 20);
+		git_SHA1_Final(sha1, &c);
+		if (hashcmp(sha1, (unsigned char *)hdr + size - 20))
+			return error("bad index file sha1 signature");
+	}
+
 	return 0;
 }

-Peff