threads / patch / 45521

v2, 2 partsread-cache: call verify_hdr() in a background thread

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

## tl;dr

10 messages between Mar 27, 2017 and Mar 28, 2017. Diffs are folded; open one to read it.

replies: 9people: 3as markdown or json

git@jeffhostetler.com· Mar 27, 2017, 21:09 UTC · lore
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
git@jeffhostetler.com· Mar 27, 2017, 21:09 UTC · re: git@jeffhostetler.com · lore

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

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(+)
Show changes to 2 files +11 −0

cache.h, read-cache.c

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
Jeff King· Mar 27, 2017, 22:44 UTC · re: git@jeffhostetler.com · lore

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

On Mon, Mar 27, 2017 at 09:09:38PM +0000, git@jeffhostetler.com wrote:
Show 15 quoted lines
> 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
Jonathan Nieder· Mar 27, 2017, 23:32 UTC · re: Jeff King · lore

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

Jeff King wrote:
Show 14 quoted lines
> 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

Jeff King· Mar 27, 2017, 23:39 UTC · re: Jonathan Nieder · lore

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

On Mon, Mar 27, 2017 at 04:32:10PM -0700, Jonathan Nieder wrote:
Show 21 quoted lines
> 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
Jeff Hostetler· Mar 28, 2017, 15:27 UTC · re: Jeff King · lore

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

On 3/27/2017 6:44 PM, Jeff King wrote:
Show 21 quoted lines
> 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.

Show 14 quoted lines
>
> 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
Jeff King· Mar 28, 2017, 15:37 UTC · re: Jeff Hostetler · lore

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

On Tue, Mar 28, 2017 at 11:27:19AM -0400, Jeff Hostetler wrote:
Show 13 quoted lines
> > 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:
Show changes to read-cache.c +11 −6
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
git@jeffhostetler.com· Mar 27, 2017, 21:09 UTC · re: git@jeffhostetler.com · lore

[PATCH v2 2/2] skip_verify_index: helper test

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
Show changes to 3 files +75 −0

Makefile, t/helper/.gitignore, 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
Jeff King· Mar 27, 2017, 22:45 UTC · re: git@jeffhostetler.com · lore

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

On Mon, Mar 27, 2017 at 09:09:37PM +0000, git@jeffhostetler.com wrote:
Show 25 quoted lines
> 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
Jeff Hostetler· Mar 28, 2017, 15:30 UTC · re: Jeff King · lore

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

On 3/27/2017 6:45 PM, Jeff King wrote:
Show 33 quoted lines
> 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

← back to recent threads