Re: [PATCH 01/02/RFC] implement a stat cache

From: Linus Torvalds <torvalds@linux-foundation.org>
Date: Apr 20, 2008, 23:07 UTC
Message-ID: <alpine.LFD.1.10.0804201556290.2779@woody.linux-foundation.org>
In-Reply-To: <alpine.LFD.1.10.0804201520370.2779@woody.linux-foundation.org>

On Sun, 20 Apr 2008, Linus Torvalds wrote:

Show 5 quoted lines

> 
> I do agree that actually actively removing stat calls requires a lot more 
> subtle interactions. We almost always *have* the stat information in the 
> index, but the problem with "git status ." is that we re-read the index so 
> many times (and then have to re-validate the stat info).

Actually, looking closer, one of the issues seems to be not just the fact that we throw out the index by re-reading it, but run_diff_files() does

		...
                if (ce_uptodate(ce))
                        continue;

                changed = check_work_tree_entity(ce, &st, symcache);
                if (changed) {
			...

where that "check_work_tree_entity()" check is very expensive for deep directory structures, because it ends up checking the stat() information fo every single directory leading up to it.

There's some bug there, because it really shouldn't do that.

This causes lstat() patterns like

	..
	lstat("JavaScriptCore/tests/mozilla/ecma/Boolean/15.6.4.2-2.js", {st_mode=S_IFREG|0664, st_size=3197, ...}) = 0
	lstat("JavaScriptCore", {st_mode=S_IFDIR|0775, st_size=4096, ...}) = 0
	lstat("JavaScriptCore/tests", {st_mode=S_IFDIR|0775, st_size=4096, ...}) = 0
	lstat("JavaScriptCore/tests/mozilla", {st_mode=S_IFDIR|0775, st_size=4096, ...}) = 0
	lstat("JavaScriptCore/tests/mozilla/ecma", {st_mode=S_IFDIR|0775, st_size=4096, ...}) = 0
	lstat("JavaScriptCore/tests/mozilla/ecma/Boolean", {st_mode=S_IFDIR|0775, st_size=4096, ...}) = 0
	..

ie instead of doing just *one* lstat (on that file), it does six: the file itself, and the five directories leading up to it!

This is the *real* cause of WebKit having ~7 lstat's per file in the repository - if it wasn't for this braindamage, we'd have just three lstat's per file for "git status .".

What's really sad is how we do this for every file in a directory, so the pattern actually ends up looking like

	...
	lstat("JavaScriptCore/tests/mozilla/ecma/Boolean/15.6.4.1.js", {st_mode=S_IFREG|0664, st_size=2164, ...}) = 0
	lstat("JavaScriptCore", {st_mode=S_IFDIR|0775, st_size=4096, ...}) = 0
	lstat("JavaScriptCore/tests", {st_mode=S_IFDIR|0775, st_size=4096, ...}) = 0
	lstat("JavaScriptCore/tests/mozilla", {st_mode=S_IFDIR|0775, st_size=4096, ...}) = 0
	lstat("JavaScriptCore/tests/mozilla/ecma", {st_mode=S_IFDIR|0775, st_size=4096, ...}) = 0
	lstat("JavaScriptCore/tests/mozilla/ecma/Boolean", {st_mode=S_IFDIR|0775, st_size=4096, ...}) = 0
	lstat("JavaScriptCore/tests/mozilla/ecma/Boolean/15.6.4.2-1.js", {st_mode=S_IFREG|0664, st_size=5219, ...}) = 0
	lstat("JavaScriptCore", {st_mode=S_IFDIR|0775, st_size=4096, ...}) = 0
	lstat("JavaScriptCore/tests", {st_mode=S_IFDIR|0775, st_size=4096, ...}) = 0
	lstat("JavaScriptCore/tests/mozilla", {st_mode=S_IFDIR|0775, st_size=4096, ...}) = 0
	lstat("JavaScriptCore/tests/mozilla/ecma", {st_mode=S_IFDIR|0775, st_size=4096, ...}) = 0
	lstat("JavaScriptCore/tests/mozilla/ecma/Boolean", {st_mode=S_IFDIR|0775, st_size=4096, ...}) = 0
	lstat("JavaScriptCore/tests/mozilla/ecma/Boolean/15.6.4.2-2.js", {st_mode=S_IFREG|0664, st_size=3197, ...}) = 0
	lstat("JavaScriptCore", {st_mode=S_IFDIR|0775, st_size=4096, ...}) = 0
	lstat("JavaScriptCore/tests", {st_mode=S_IFDIR|0775, st_size=4096, ...}) = 0
	lstat("JavaScriptCore/tests/mozilla", {st_mode=S_IFDIR|0775, st_size=4096, ...}) = 0
	lstat("JavaScriptCore/tests/mozilla/ecma", {st_mode=S_IFDIR|0775, st_size=4096, ...}) = 0
	lstat("JavaScriptCore/tests/mozilla/ecma/Boolean", {st_mode=S_IFDIR|0775, st_size=4096, ...}) = 0
	...

ie for deep directories with lots of files in them, we end up doing an lstat() on all the directories leading up to that directory oevr and over and over again - for each file in that directory.

Oops.

We're supposed to have that "char *symcache" thing to not do that, but it doesn't actually work that way.

Junio, what was the logic for that whole "has_symlink_leading_path()" thing? I forget. Whatever, it's broken.

		Linus