Git performance on OS X

Git performance on OS X

[Pieter de Bie]

Hi Git mailing list,

I have done some tests regarding git's performance on the OS X platform. We
noticed that mercurial is a lot faster than git in the "git status" command,
especially on the webkit repository. This repository has 45k files, so one
would expect it to be slow because of OS X's slow lstat. However, mercurial is
a lot faster (usually 6.2 seconds for git vs ~4 seconds for hg).

For a reference to the statistics below, `git status' in the webkit repo takes
about 6.21 seconds with a std dev of 0.26.

1. 10k empty files

First off, I started with the most simple case: a repository with 10k empty
files in a flat repo.

Git add times

It appears that on large initial imports, git add * is a lot slower than git
add .. This test was performed on a directory with 10000 empty files in it.

Results
=========================================================
Command                               Mean     Std
rm -rf .git && git init && git add .  0.617    0.153
rm -rf .git && git init && git add *  43.383   0.419
rm -rf .hg && hg init && hg add .     0.926    0.027
rm -rf .hg && hg init && hg add *     4.312    0.013
=========================================================

Sampling this, it appears that git add spends a lot of time in fnmatch.
top function calls in 4 second sample:

        fnmatch$UNIX2003  2452
        fnmatch1          310
        strlen            292
        mbrtowc_l         188

probably because git is performing its own glob expansion. This is expensive
on 10,000 supplied files. Of course, this is an uncommon scenario, but still
Mercurial seems to do things differently (I don't know how to sample python,
unfortunately).

Git status on these 10k files takes about 0.111 seconds:

Results
================================================
Command                     Mean     Std
git status                   0.112    0.006
hg status                    0.317    0.005
================================================

This all seems very acceptable. Now we scale up to 50,000 files.

2. 50k empty files

Unfortunately, this was too much for my system to pass as arguments:

  sh: /opt/local/bin/hg: Argument list too long

Therefore, only part of the git adds can be compared

Results
======================================================================
Command                                            Mean     Std    
rm -rf .git .hg && git init && git add .           6.239   0.184
rm -rf .hg .git && hg init && hg add .             11.059  0.342
======================================================================

Git is still faster than Mercurial on adding files.. so far so good. Now the
git / hg status test:

Results
======================================================================
Command                                            Mean     Std    
hg status                                          4.984  0.249
git status                                         3.709  0.150
======================================================================

So, git takes a bit less time than hg in this case. These are mostly system
calls:

    Vienna:perf pieter$ time git status
    # On branch master
    nothing to commit (working directory clean)

    real  0m3.705s
    user  0m0.212s
    sys   0m3.256s
    
So it's not git's fault here that the status is slow.


3. A more complex directory structure.

We now use Webkit's directory and file structure and see what happens. This
test repository has exactly the same files and structure as the webkit repo,
but all files are empty.

Results
======================================================================
Command                                            Mean     Std    
rm -rf .git .hg && git init && git add .           6.014  0.523
rm -rf .git .hg && git init && git add *           6.198  0.228
rm -rf .hg .git && hg init && hg add .             7.707  0.519
rm -rf .hg .git && hg init && hg add *             7.632  0.405
======================================================================

Funnily enough, Mercurial is faster with this structure than with the
one-directory structure. Git shows linear scaling. Also, with a real
structure, the * vs . problem in git goes away.

Now we can look at the "git status" commands and compare them to the actual
status' of the actual webkit repository.

Results
======================================================================
Command                                            Mean     Std    
git status                                         4.573  0.514
git status .                                       13.515  0.448
hg status                                          4.411  1.594
hg status .                                        4.903  0.171
======================================================================

There's no significant difference between the git and hg status things.
Remember that in the webkit repo, "git status" takes about 6.2 seconds, which
is a lot slower than we see here.

Therefore, it is interesting to look at what happens if we import the whole
webkit branch.

4. A new webkit repository

This test was done by creating a new clone of the webkit repository.
Basically, I did a git archive | tar x and did a git add on that.

This is where some interesting stuff happens. I haven't done the git add
thing, as that should be clear by now and takes a lot of time. The status
command, however:

Results
======================================================================
Command                                            Mean     Std    
git status                                         4.428   0.486
git status .                                       13.508  1.451
hg status                                          4.285   1.681
hg status .                                        4.930   0.165
======================================================================

Again, git shows similar performance to mercurial. Furthermore, the status
time hasn't changed since last time. Apparently, the increased file size and
increased number of objects didn't matter. So, why is there such a big
difference between the real webkit repository and this fresh one?

5. A repacked shallow webkit repo

One thing that could be it is that the webkit repo is heavily packed. To test
this, I created a new clone and repacked this one and (21 minutes later):

Results
======================================================================
Command                                            Mean     Std    
(Pre-GC): git status                               4.470   0.423
(Pre-GC): git status .                             13.355  1.025
(Post-GC): git status                              4.910   0.324
(Post-GC): git status .                            11.265  0.222
======================================================================

When run with 10 tests in the pre and post case, there is a significant
difference according to a t-test (df=18, p << 0.01). Therefore, I compared the
real, user and system times pre and post of git status. I also included the
real webkit again, and also a shallow clone of that repository.

          Pre-GC       Post-GC      (shallow)   (real webkit) 
real     4.36 (0.06)   4.61 (0.06)  5.72 (0.25)  6.21 (0.28)  
user     0.39 (0.01)   0.37 (0.00)  0.36 (0.00)  0.39 (0.00)  
sys      3.28 (0.04)   2.86 (0.03)  3.21 (0.09)  2.90 (0.01)  

The system time seems to jump up and down sometimes, but the real times
definitely keep getting higher. This isn't due to system or user time. Where
does this extra time come from?

I hope anyone can explain this. I tried profiling the commands, but `sample'
often doesn't want to show symbols (sometimes it does, though) and gprof
doesn't show most functions. My profiling skills aren't that high, so if
anyone has suggestions, I'll be glad to help.

- Pieter

Re: Git performance on OS X

[Linus Torvalds]

On Sat, 19 Apr 2008, Pieter de Bie wrote:
> 
> It appears that on large initial imports, git add * is a lot slower than git
> add .

"git add *" is actually fundamentally different from "git add .", and 
yeah, you should generally use the latter.

The reason? The argument list is actually something different from what 
you think it is. For git, it's a "pathspec", so what actualy happens is 
that in *both* cases, it will really traverse the whole tree, and then 
match every file it finds against the pathspec.

So think of the arguments not as a file list, but as a random bunch of 
patterns to match against the files you have!

Which is why the cost is actually approximately O(n*m), where "n" is the 
size of the working tree, and "m" is the number of pathspecs.

So the reason "git add ." is fast is actually that "m" in that case is 
just 1 (just one trivial pattern), and then "git add *" is slow because 
"m" is large (lots of complicated patterns). In both cases, 'n' is the 
same (== the whole set of files in your working tree).

Now, it has some trivial optimizations, so that if the all the patterns in 
the pathspec begin with the same base directory, it will only look at that 
base directory, which is why

	git add drivers/block/*

is much faster than

	git add *

even though they both have a fair number of pattners (ie 'm' is roughly 
the same, but now it has basically artificially limited 'n' to just a 
subset of the tree). When you do "git add *", there is obviously no 
such trivial subset - '*' is not going to limit the pattern space to just 
a small part of the subtree!

I do agree that the git behavior is kind of odd, but it's very consistent 
with all the other uses of pathspecs in git, and we've never optimized it 
a lot simply because nobody normally _should_ do "git add *" with a lot of 
files.

If you want to see the worst-case, do

	git add $(git ls-files)

which basically means that it's O(n^2) in the number of files we track 
(regardless of depth). Because remember: the arguments to git add are not 
something we just iterate over - we always iterate over the whole tree, 
and then the arguments are just patterns that we then match that tree 
against.

And yeah, we could create a few other optimization heuristics that would 
almost certainly speed up those worst cases by a huge amount. The logic is 
all in "match_pathspec()" (where the "prefix" count is just the common 
prefix that we don't even need to match because of the trivial "under this 
tree" optimization).

Notice how match_pathspec() just walks over the whole pathspec (that's 
your argument list), and how we call this for every single file we find 
(after we've done .gitignore handling etc).

Anyway, here's a trivial patch that doesn't change this fundamental fact, 
but that avoids doing anything *expensive* until we've done some cheap 
initial tests. It may or may not help your test-case, but it's pretty 
simple and it matches the other git optimizations in this area (ie 
"conceptually handle the general case, but optimize the simple cases where 
we can exit early")

Notice how this patch doesn' actually change the fundamental O(n^2) 
behaviour, but it makes it much cheaper by generally avoiding the 
expensive 'fnmatch' and 'strlen/strncmp' when they are obviously not 
needed.

		Linus

---
 dir.c |   22 ++++++++++++++++++++--
 1 files changed, 20 insertions(+), 2 deletions(-)

diff --git a/dir.c b/dir.c
index 63715c9..8d45321 100644
--- a/dir.c
+++ b/dir.c
@@ -52,6 +52,11 @@ int common_prefix(const char **pathspec)
 	return prefix;
 }
 
+static inline int special_char(unsigned char c1)
+{
+	return !c1 || c1 == '*' || c1 == '[' || c1 == '?';
+}
+
 /*
  * Does 'match' matches the given name?
  * A match is found if
@@ -69,14 +74,27 @@ static int match_one(const char *match, const char *name, int namelen)
 	int matchlen;
 
 	/* If the match was just the prefix, we matched */
-	matchlen = strlen(match);
-	if (!matchlen)
+	if (!*match)
 		return MATCHED_RECURSIVELY;
 
+	for (;;) {
+		unsigned char c1 = *match;
+		unsigned char c2 = *name;
+		if (special_char(c1))
+			break;
+		if (c1 != c2)
+			return 0;
+		match++;
+		name++;
+		namelen--;
+	}
+	
+
 	/*
 	 * If we don't match the matchstring exactly,
 	 * we need to match by fnmatch
 	 */
+	matchlen = strlen(match);
 	if (strncmp(match, name, matchlen))
 		return !fnmatch(match, name, 0) ? MATCHED_FNMATCH : 0;
 

Re: Git performance on OS X

[Linus Torvalds]

On Sat, 19 Apr 2008, Linus Torvalds wrote:
> 
> Notice how this patch doesn' actually change the fundamental O(n^2) 
> behaviour, but it makes it much cheaper by generally avoiding the 
> expensive 'fnmatch' and 'strlen/strncmp' when they are obviously not 
> needed.

Side note: on the kenrel tree, it makes the (insane!) operation 

	git add $(git ls-files)

go from 49 seconds down to 17 sec. So it does make a huge difference for 
me, but I also want to point out that this really isn't a sane operation 
to do (I also think that 17 sec is totally unacceptable, but I cannot find 
it in me to care, since I don't think this is an operation that anybody 
should ever do!)

The optimization is probably worth doing just to avoid the bad worst case, 
but we should teach people not to do "git add *" (or that insane ls-files 
thing), and instead do "git add ." and "git add -u".

But in the absense of teaching people that, the patch should at least 
makes that bad pattern behavior be slightly more acceptable for git, even 
if it's still not very nice.

(Btw, we need to stop using "fnmatch()" entirely some day, if only because 
we can't ever use it for case-insensitive stuff. That patch doesn't help 
us with that, but it doesn't hurt either, and conceptually it's moving in 
the direction of doing more in "native" git code than in "fnmatch()")

				Linus

Re: Git performance on OS X

[Linus Torvalds]

Btw, the "git status" issue is totally different.

On Sat, 19 Apr 2008, Pieter de Bie wrote:
>
> Now we can look at the "git status" commands and compare them to the actual
> status' of the actual webkit repository.
> 
> Results
> ======================================================================
> Command                                            Mean     Std    
> git status                                         4.573  0.514
> git status .                                       13.515  0.448
> hg status                                          4.411  1.594
> hg status .                                        4.903  0.171

The reason "git status ." is slower has nothing to do with the pathspec 
matching, and everything to do with the fact that "git status" with a 
pathspec means soemthing different again.

Remember: "git status" is basically shorthand for "what would happen if I 
did a "git commit" with these arguments.

Which means that "git status ." basically is something similar to a 
private invocation of "git add -u ." in addition to the regular git 
status.

So try it out: change some file (let's say the top-level Makefile) and do 
the two operations, and see how the _output_ is totally different:

Without the ".", you should see something like:

	# On branch master
	# Changed but not updated:
	#   (use "git add <file>..." to update what will be committed)
	#
	#       modified:   Makefile
	#
	no changes added to commit (use "git add" and/or "git commit -a")

ie there is nothing to commit, but Makefile is modified and _could_ be 
committed.

Now, don't look down at the answer, but instead try to think it through: 
what is "git status ." going to say?

Answer: it's going to show something totally different, because "git 
commit ." is going to add that changed Makefile to the commit, so by the 
logic that "git status" is supposed to show what commit will do, you'll 
*not* see that "no changes" line at all, but instead you'll see

	# On branch master
	# Changes to be committed:
	#   (use "git reset HEAD <file>..." to unstage)
	#
	#       modified:   Makefile

ie now we *would* commit that Makefile change!

So the reason "git status ." is more expensive is that it's doing 
something else.

I don't know what "hg status ." means, but I suspect that it's more of a 
"same thing as 'hg status', but limited to '.'".

And yes, most of the time in "git status ." is going to be the lstat() 
calls. Which are expensive on OS X. And yes, we do too many of them. I'll 
look at seeing if we can avoid some.

		Linus

Re: Git performance on OS X

[Pieter de Bie]

On 19 apr 2008, at 23:54, Linus Torvalds wrote:
>
>
> Btw, the "git status" issue is totally different.
>

Yes, I was aware of that, but still found it interesting to test.
>
> And yes, most of the time in "git status ." is going to be the lstat()
> calls. Which are expensive on OS X. And yes, we do too many of them.  
> I'll
> look at seeing if we can avoid some.

I just tested this. "git status ." does 428815 (400k!) lstats, almost  
10x as many as there are files in the repository. I'd agree that this  
is the reason it's slow on OS X :).

- Pieter

Re: Git performance on OS X

[Pieter de Bie]

On 19 apr 2008, at 23:29, Linus Torvalds wrote:
> Side note: on the kenrel tree, it makes the (insane!) operation
>
> 	git add $(git ls-files)
>
> go from 49 seconds down to 17 sec. So it does make a huge difference  
> for
> me, but I also want to point out that this really isn't a sane  
> operation
> to do (I also think that 17 sec is totally unacceptable, but I  
> cannot find
> it in me to care, since I don't think this is an operation that  
> anybody
> should ever do!)

Yes, using the patch decreases the time for my from ~40 seconds to  
just about 4 seconds.

- Pieter

Re: Git performance on OS X

[Linus Torvalds]

On Sun, 20 Apr 2008, Pieter de Bie wrote:
>
> I just tested this. "git status ." does 428815 (400k!) lstats, almost 10x as
> many as there are files in the repository. I'd agree that this is the reason
> it's slow on OS X :).

Yeah. I didn't look any further, but we do a total of *nine* 'lstat()' 
calls for each file we know about that is dirty, and *seven* when they are 
clean. Plus maybe a few more.

I had some patches that cut that down a lot, but some of it had to be 
reverted because of the subtle interactions with different internal copies 
of the index, and I think the case with a partial commit (which is what 
you have when using a pathspec) was the case that got reverted.

Maybe I should revisit it, now that we have internal support for actually 
keeping multiple indexes in place and being able to merge them.

Appended, in case somebody is interested, are the callchains for the 
different lstat() callers (for the case of a single file that was clean).

(This is with a non-pristine git source-base, so the line numbers may not 
match 100%, but the changes are pretty small, so it should still be an 
interesting set of callers)

At least two of them are due to ce_smudge_racily_clean_entry(), which in 
turn is because we trigger the is_racy_timestamp() test. Hmm.

And four of them are because of two cases of the pattern

	if (file_exists())
		add_file_to_cache(p->path, 0);

where the "file_exists()" first does an lstat() to see if it exists, and 
then "add_file_to_cache()" does an lstat() to get the stat info..

			Linus

---
First:
	#1  0x0000000000481fd7 in file_exists (f=0x1ac3f10 "Makefile") at dir.c:742
	#2  0x00000000004196bd in add_remove_files (list=0x7fff87223310) at builtin-commit.c:179
	#3  0x0000000000419aa1 in prepare_index (argc=1, argv=0x7fff872235d0, prefix=0x0) at builtin-commit.c:308
	#4  0x000000000041b3b2 in cmd_status (argc=1, argv=0x7fff872235d0, prefix=0x0) at builtin-commit.c:781
	#5  0x000000000040482e in run_command (p=0x704eb8, argc=2, argv=0x7fff872235d0) at git.c:264
	#6  0x00000000004049db in handle_internal_command (argc=2, argv=0x7fff872235d0) at git.c:394
	#7  0x0000000000404b47 in main (argc=2, argv=0x7fff872235d0) at git.c:458

Second:
	#1  0x00000000004973a0 in add_file_to_index (istate=0x7494c0, path=0x1ac3f10 "Makefile", verbose=0) at read-cache.c:471
	#2  0x00000000004196d7 in add_remove_files (list=0x7fff87223310) at builtin-commit.c:180
	#3  0x0000000000419aa1 in prepare_index (argc=1, argv=0x7fff872235d0, prefix=0x0) at builtin-commit.c:308
	#4  0x000000000041b3b2 in cmd_status (argc=1, argv=0x7fff872235d0, prefix=0x0) at builtin-commit.c:781
	#5  0x000000000040482e in run_command (p=0x704eb8, argc=2, argv=0x7fff872235d0) at git.c:264
	#6  0x00000000004049db in handle_internal_command (argc=2, argv=0x7fff872235d0) at git.c:394
	#7  0x0000000000404b47 in main (argc=2, argv=0x7fff872235d0) at git.c:458

Third:
	#1  0x00000000004992a4 in ce_smudge_racily_clean_entry (ce=0x1ac4000) at read-cache.c:1267
	#2  0x000000000049956d in write_index (istate=0x7494c0, newfd=6) at read-cache.c:1348
	#3  0x0000000000419ac7 in prepare_index (argc=1, argv=0x7fff872235d0, prefix=0x0) at builtin-commit.c:310
	#4  0x000000000041b3b2 in cmd_status (argc=1, argv=0x7fff872235d0, prefix=0x0) at builtin-commit.c:781
	#5  0x000000000040482e in run_command (p=0x704eb8, argc=2, argv=0x7fff872235d0) at git.c:264
	#6  0x00000000004049db in handle_internal_command (argc=2, argv=0x7fff872235d0) at git.c:394
	#7  0x0000000000404b47 in main (argc=2, argv=0x7fff872235d0) at git.c:458

Fourth:
	#1  0x0000000000481fd7 in file_exists (f=0x1ac3f10 "Makefile") at dir.c:742
	#2  0x00000000004196bd in add_remove_files (list=0x7fff87223310) at builtin-commit.c:179
	#3  0x0000000000419b21 in prepare_index (argc=1, argv=0x7fff872235d0, prefix=0x0) at builtin-commit.c:318
	#4  0x000000000041b3b2 in cmd_status (argc=1, argv=0x7fff872235d0, prefix=0x0) at builtin-commit.c:781
	#5  0x000000000040482e in run_command (p=0x704eb8, argc=2, argv=0x7fff872235d0) at git.c:264
	#6  0x00000000004049db in handle_internal_command (argc=2, argv=0x7fff872235d0) at git.c:394
	#7  0x0000000000404b47 in main (argc=2, argv=0x7fff872235d0) at git.c:458

Fifth:
	#1  0x00000000004973a0 in add_file_to_index (istate=0x7494c0, path=0x1ac3f10 "Makefile", verbose=0) at read-cache.c:471
	#2  0x00000000004196d7 in add_remove_files (list=0x7fff87223310) at builtin-commit.c:180
	#3  0x0000000000419b21 in prepare_index (argc=1, argv=0x7fff872235d0, prefix=0x0) at builtin-commit.c:318
	#4  0x000000000041b3b2 in cmd_status (argc=1, argv=0x7fff872235d0, prefix=0x0) at builtin-commit.c:781
	#5  0x000000000040482e in run_command (p=0x704eb8, argc=2, argv=0x7fff872235d0) at git.c:264
	#6  0x00000000004049db in handle_internal_command (argc=2, argv=0x7fff872235d0) at git.c:394
	#7  0x0000000000404b47 in main (argc=2, argv=0x7fff872235d0) at git.c:458

Sixth:
	#1  0x00000000004992a4 in ce_smudge_racily_clean_entry (ce=0x1ac4740) at read-cache.c:1267
	#2  0x000000000049956d in write_index (istate=0x7494c0, newfd=6) at read-cache.c:1348
	#3  0x0000000000419b47 in prepare_index (argc=1, argv=0x7fff872235d0, prefix=0x0) at builtin-commit.c:321
	#4  0x000000000041b3b2 in cmd_status (argc=1, argv=0x7fff872235d0, prefix=0x0) at builtin-commit.c:781
	#5  0x000000000040482e in run_command (p=0x704eb8, argc=2, argv=0x7fff872235d0) at git.c:264
	#6  0x00000000004049db in handle_internal_command (argc=2, argv=0x7fff872235d0) at git.c:394
	#7  0x0000000000404b47 in main (argc=2, argv=0x7fff872235d0) at git.c:458

Seventh:
	#1  0x0000000000475a37 in check_work_tree_entity (ce=0x1ac4870, st=0x7fff87221ea0, symcache=0x7fff87221f30 "") at diff-lib.c:343
	#2  0x0000000000475eab in run_diff_files (revs=0x7fff87222fc0, option=0) at diff-lib.c:466
	#3  0x00000000004bd62e in wt_status_print_changed (s=0x7fff872232f0) at wt-status.c:220
	#4  0x00000000004bdb1d in wt_status_print (s=0x7fff872232f0) at wt-status.c:310
	#5  0x0000000000419c0b in run_status (fp=0x37d8751760, index_file=0x711ef1 "/home/torvalds/git-test/.git/next-index-14646.lock", prefix=0x0, 
	    nowarn=0) at builtin-commit.c:349
	#6  0x000000000041b3cf in cmd_status (argc=1, argv=0x7fff872235d0, prefix=0x0) at builtin-commit.c:783
	#7  0x000000000040482e in run_command (p=0x704eb8, argc=2, argv=0x7fff872235d0) at git.c:264
	#8  0x00000000004049db in handle_internal_command (argc=2, argv=0x7fff872235d0) at git.c:394
	#9  0x0000000000404b47 in main (argc=2, argv=0x7fff872235d0) at git.c:458

Re: Git performance on OS X

[Jakub Narebski]

Pieter de Bie <pdebie@ai.rug.nl> writes:

> On 19 apr 2008, at 23:54, Linus Torvalds wrote:
> >
> > And yes, most of the time in "git status ." is going to be the lstat()
> > calls. Which are expensive on OS X. And yes, we do too many of them.
> > I'll
> > look at seeing if we can avoid some.
> 
> I just tested this. "git status ." does 428815 (400k!) lstats, almost
> 10x as many as there are files in the repository. I'd agree that this
> is the reason it's slow on OS X :).

By the way, what version of git do you use? Because in RelNotes for
1.5.5 there is:

 * "git commit" does not run lstat(2) more than necessary
   anymore.

which I guess also apply to git status.  This change was written by
Linus if I remember correctly...

-- 
Jakub Narebski
Poland
ShadeHawk on #git

Re: Git performance on OS X

[Linus Torvalds]

On Sat, 19 Apr 2008, Jakub Narebski wrote:
> 
> By the way, what version of git do you use? Because in RelNotes for
> 1.5.5 there is:
> 
>  * "git commit" does not run lstat(2) more than necessary
>    anymore.
> 
> which I guess also apply to git status.  This change was written by
> Linus if I remember correctly...

That's only true for a plain "git status" (and even there it does *one* 
superfluous lstat()).

If you do "git status ." it still does a _lot_ of unnecessary commits.

This patch will help. It removes the one superfluous lstat() from "git 
status", and for "git status ." it removes two of them. Basically the old 
pattern

	if (file_exists(..))
		add_file_to_cache(..)

now uses just one lstat() and shares the data between the two.

		Linus

---
 builtin-commit.c |    6 ++++--
 cache.h          |    2 ++
 read-cache.c     |   29 +++++++++++++++++------------
 3 files changed, 23 insertions(+), 14 deletions(-)

diff --git a/builtin-commit.c b/builtin-commit.c
index bcb7aaa..fb3e359 100644
--- a/builtin-commit.c
+++ b/builtin-commit.c
@@ -175,9 +175,11 @@ static void add_remove_files(struct path_list *list)
 {
 	int i;
 	for (i = 0; i < list->nr; i++) {
+		struct stat st;
 		struct path_list_item *p = &(list->items[i]);
-		if (file_exists(p->path))
-			add_file_to_cache(p->path, 0);
+
+		if (!lstat(p->path, &st))
+			add_to_cache(p->path, &st, 0);
 		else
 			remove_file_from_cache(p->path);
 	}
diff --git a/cache.h b/cache.h
index 1b66cc0..c058125 100644
--- a/cache.h
+++ b/cache.h
@@ -261,6 +261,7 @@ static inline void remove_name_hash(struct cache_entry *ce)
 #define add_cache_entry(ce, option) add_index_entry(&the_index, (ce), (option))
 #define remove_cache_entry_at(pos) remove_index_entry_at(&the_index, (pos))
 #define remove_file_from_cache(path) remove_file_from_index(&the_index, (path))
+#define add_to_cache(path, st, verbose) add_to_index(&the_index, (path), (st), (verbose))
 #define add_file_to_cache(path, verbose) add_file_to_index(&the_index, (path), (verbose))
 #define refresh_cache(flags) refresh_index(&the_index, (flags), NULL, NULL)
 #define ce_match_stat(ce, st, options) ie_match_stat(&the_index, (ce), (st), (options))
@@ -364,6 +365,7 @@ extern int add_index_entry(struct index_state *, struct cache_entry *ce, int opt
 extern struct cache_entry *refresh_cache_entry(struct cache_entry *ce, int really);
 extern int remove_index_entry_at(struct index_state *, int pos);
 extern int remove_file_from_index(struct index_state *, const char *path);
+extern int add_to_index(struct index_state *, const char *path, struct stat *, int verbose);
 extern int add_file_to_index(struct index_state *, const char *path, int verbose);
 extern struct cache_entry *make_cache_entry(unsigned int mode, const unsigned char *sha1, const char *path, int stage, int refresh);
 extern int ce_same_name(struct cache_entry *a, struct cache_entry *b);
diff --git a/read-cache.c b/read-cache.c
index 15d3d72..4c1a9f4 100644
--- a/read-cache.c
+++ b/read-cache.c
@@ -461,21 +461,18 @@ static struct cache_entry *create_alias_ce(struct cache_entry *ce, struct cache_
 	return new;
 }
 
-int add_file_to_index(struct index_state *istate, const char *path, int verbose)
+int add_to_index(struct index_state *istate, const char *path, struct stat *st, int verbose)
 {
 	int size, namelen;
-	struct stat st;
+	mode_t st_mode = st->st_mode;
 	struct cache_entry *ce, *alias;
 	unsigned ce_option = CE_MATCH_IGNORE_VALID|CE_MATCH_RACY_IS_DIRTY;
 
-	if (lstat(path, &st))
-		die("%s: unable to stat (%s)", path, strerror(errno));
-
-	if (!S_ISREG(st.st_mode) && !S_ISLNK(st.st_mode) && !S_ISDIR(st.st_mode))
+	if (!S_ISREG(st_mode) && !S_ISLNK(st_mode) && !S_ISDIR(st_mode))
 		die("%s: can only add regular files, symbolic links or git-directories", path);
 
 	namelen = strlen(path);
-	if (S_ISDIR(st.st_mode)) {
+	if (S_ISDIR(st_mode)) {
 		while (namelen && path[namelen-1] == '/')
 			namelen--;
 	}
@@ -483,10 +480,10 @@ int add_file_to_index(struct index_state *istate, const char *path, int verbose)
 	ce = xcalloc(1, size);
 	memcpy(ce->name, path, namelen);
 	ce->ce_flags = namelen;
-	fill_stat_cache_info(ce, &st);
+	fill_stat_cache_info(ce, st);
 
 	if (trust_executable_bit && has_symlinks)
-		ce->ce_mode = create_ce_mode(st.st_mode);
+		ce->ce_mode = create_ce_mode(st_mode);
 	else {
 		/* If there is an existing entry, pick the mode bits and type
 		 * from it, otherwise assume unexecutable regular file.
@@ -495,18 +492,18 @@ int add_file_to_index(struct index_state *istate, const char *path, int verbose)
 		int pos = index_name_pos_also_unmerged(istate, path, namelen);
 
 		ent = (0 <= pos) ? istate->cache[pos] : NULL;
-		ce->ce_mode = ce_mode_from_stat(ent, st.st_mode);
+		ce->ce_mode = ce_mode_from_stat(ent, st_mode);
 	}
 
 	alias = index_name_exists(istate, ce->name, ce_namelen(ce), ignore_case);
-	if (alias && !ce_stage(alias) && !ie_match_stat(istate, alias, &st, ce_option)) {
+	if (alias && !ce_stage(alias) && !ie_match_stat(istate, alias, st, ce_option)) {
 		/* Nothing changed, really */
 		free(ce);
 		ce_mark_uptodate(alias);
 		alias->ce_flags |= CE_ADDED;
 		return 0;
 	}
-	if (index_path(ce->sha1, path, &st, 1))
+	if (index_path(ce->sha1, path, st, 1))
 		die("unable to index file %s", path);
 	if (ignore_case && alias && different_name(ce, alias))
 		ce = create_alias_ce(ce, alias);
@@ -518,6 +515,14 @@ int add_file_to_index(struct index_state *istate, const char *path, int verbose)
 	return 0;
 }
 
+int add_file_to_index(struct index_state *istate, const char *path, int verbose)
+{
+	struct stat st;
+	if (lstat(path, &st))
+		die("%s: unable to stat (%s)", path, strerror(errno));
+	return add_to_index(istate, path, &st, verbose);
+}
+
 struct cache_entry *make_cache_entry(unsigned int mode,
 		const unsigned char *sha1, const char *path, int stage,
 		int refresh)

Re: Git performance on OS X

[Linus Torvalds]

On Sat, 19 Apr 2008, Linus Torvalds wrote:
> 
> This patch will help.

Pieter? Assuming the lstat() cost is the dominant one, it should cut down 
your "git status ." cost by about 15-20% or so. Can you confirm?

		Linus

Re: Git performance on OS X

[Linus Torvalds]

On Sat, 19 Apr 2008, Linus Torvalds wrote:
> 
> If you do "git status ." it still does a _lot_ of unnecessary commits.
                                                                ^^^^^^^

I meant 'lstat()'s, of course.

I think I need to take my alzheimer medication now.

			Linus

Re: Git performance on OS X

[Pieter de Bie]

On 20 apr 2008, at 00:54, Linus Torvalds wrote:
> Pieter? Assuming the lstat() cost is the dominant one, it should cut  
> down
> your "git status ." cost by about 15-20% or so. Can you confirm?

The number of lstats are cut down by your patch: 428761 vs. 338091.  
Funnily enough, there is no significant difference in run-time:

Command                                            Mean     Std
git status .                                       13.970  1.298
/Users/pieter/projects/External/git/git-status .   13.759  0.321


System times are also approximately the same (10.79s vs 10.43s).

- Pieter

Re: Git performance on OS X

[Linus Torvalds]

On Sun, 20 Apr 2008, Pieter de Bie wrote:
> 
> The number of lstats are cut down by your patch: 428761 vs. 338091. Funnily
> enough, there is no significant difference in run-time:

It may be that the problem with OS X is a sucky pathname cache mechanism.

The trivial patch cut down the number of stat() calls by a fair amount, 
but the calls that got removed were all of the "do two 'lstat()' calls on 
the exact same pathname consecutively" type.

Maybe OS X has some very limited pathname caching that catches that, or 
even if not, it just ends up being very nice in the D$, so it's not a big 
deal. And then the real suckiness happens only with bigger workloads.

It may also be that the bulk of the OS X cost isn't in lstat() at all, but 
in the VM. That was true for some other OS X load.

> Command                                            Mean     Std
> git status .                                       13.970  1.298
> /Users/pieter/projects/External/git/git-status .   13.759  0.321

This is the WebKit archive, right?

For me, doing a "time git status ." on the WebKit thing I just cloned from 
git://git.webkit.org/WebKit.git is much faster: 1.264s (and it goes down 
by maybe 5-10% with my lstat-avoidance patch).

Is there any system-level profiler for OS X to get a clue where that cost 
is, in case it's not the lstat() at all?

			Linus

Re: Git performance on OS X

[Roman Shaposhnik]

On Apr 19, 2008, at 4:26 PM, Linus Torvalds wrote:
> This is the WebKit archive, right?
>
> For me, doing a "time git status ." on the WebKit thing I just  
> cloned from
> git://git.webkit.org/WebKit.git is much faster: 1.264s (and it goes  
> down
> by maybe 5-10% with my lstat-avoidance patch).
>
> Is there any system-level profiler for OS X to get a clue where  
> that cost
> is, in case it's not the lstat() at all?

If it happens on Leopard, DTrace would be a perfect way to query the  
system:

   $ dtrace -n 'syscall::*:entry /pid==$target/ { @[probefunc] = count 
(); }' -c "git <do stuff>"

E.g.:

$ dtrace -n 'syscall::*:entry /pid==$target/ { @[probefunc] = count 
(); }' -c "echo Hello World"
dtrace: description 'syscall::*:entry ' matched 234 probes
Hello World
dtrace: pid 1325 has exited

   fstat64                                                           1
   getpid                                                            1
   getrlimit                                                         1
   ioctl                                                             1
   mmap                                                              1
   munmap                                                            1
   rexit                                                             1
   sysi86                                                            1
   setcontext                                                        2
   write                                                             2


Thanks,
Roman.

Re: Git performance on OS X

[Pieter de Bie]

On 20 apr 2008, at 01:26, Linus Torvalds wrote:
>
> It may be that the problem with OS X is a sucky pathname cache  
> mechanism.
>
> The trivial patch cut down the number of stat() calls by a fair  
> amount,
> but the calls that got removed were all of the "do two 'lstat()'  
> calls on
> the exact same pathname consecutively" type.
>
> Maybe OS X has some very limited pathname caching that catches that,  
> or
> even if not, it just ends up being very nice in the D$, so it's not  
> a big
> deal. And then the real suckiness happens only with bigger workloads.
>

Yes, I just tested this.

	for (int i = 0; i < 50000; i++) {
		sprintf(s, "/Users/pieter/test/perf/%i", i);
		int ret = lstat(s, a);
	}

This loop needs about 3 seconds to  run. Replacing the i with 10 in  
the sprintf reduces it to 0.24seconds.

>> Command                                            Mean     Std
>> git status .                                       13.970  1.298
>> /Users/pieter/projects/External/git/git-status .   13.759  0.321
>
> This is the WebKit archive, right?
>
> For me, doing a "time git status ." on the WebKit thing I just  
> cloned from
> git://git.webkit.org/WebKit.git is much faster: 1.264s (and it goes  
> down
> by maybe 5-10% with my lstat-avoidance patch).
>
> Is there any system-level profiler for OS X to get a clue where that  
> cost
> is, in case it's not the lstat() at all?

Yes, that was the webkit repo (the test above was in a dir with 50k  
files).

Alas, I tried to create a nice profiling for the "git status .". In  
the Instruments application I can create a sampler, but I see no way  
to export it. The option to export the script as a dtrace script is  
greyed out in the menu.

 From the sampler, it appears that the lstat calls still account for  
most of the time. I have uploaded a screenshot to http://ss.frim.nl/==759.png 
. It actually shows quite nicely when the lstats are being done --  
it's when the CPU is idle. Next to the lstats, the read_tree_recursive  
is also called often.

- Pieter

Re: Git performance on OS X

[Pieter de Bie]

On 20 apr 2008, at 01:35, Roman Shaposhnik wrote:
> If it happens on Leopard, DTrace would be a perfect way to query the  
> system:
>
>  $ dtrace -n 'syscall::*:entry /pid==$target/ { @[probefunc] =  
> count(); }' -c "git <do stuff>"

Yes, but this only shows syscalls and only entries. If you have enough  
dtrace-fu to create a script that samples all functions (and thus  
shows which functions are being active most of the time), I will  
gladly run it.

- Pieter

Re: Git performance on OS X

[Linus Torvalds]

On Sat, 19 Apr 2008, Roman Shaposhnik wrote:
> > 
> > Is there any system-level profiler for OS X to get a clue where that cost
> > is, in case it's not the lstat() at all?
> 
> If it happens on Leopard, DTrace would be a perfect way to query the system:

Well, I'd really like to see a traditional _time_ profile, not system 
call counts.

The system call profile is trivial - it's generally going to be pretty 
similar under OS X and Linux (modulo library differences, but git doesn't 
really use any really complex libraries that would do system calls).

The problem we've had in the past is that Linux is simply an order of 
magnitude faster (sometimes more) at some operations than OS X is, so 
issues that show up on OS X don't even show up on Linux.

This was the case for doing lots of small "mmap()/munmap()" calls, for 
example, where we literally had a load where OS X was two orders of 
magnitude slower. We switched over to reading the files with "pread()" 
instead of mmap(), and that fixed that particular issue.

So a real system profile would be nice.

			Linus

Re: Git performance on OS X

[Roman Shaposhnik]

On Apr 19, 2008, at 5:06 PM, Linus Torvalds wrote:
> On Sat, 19 Apr 2008, Roman Shaposhnik wrote:
>>>
>>> Is there any system-level profiler for OS X to get a clue where  
>>> that cost
>>> is, in case it's not the lstat() at all?
>>
>> If it happens on Leopard, DTrace would be a perfect way to query  
>> the system:
>
> Well, I'd really like to see a traditional _time_ profile, not system
> call counts.

Good point. I just thought your original question was simply about  
confirming
a hunch of an enormous # of lstat syscalls. Now, if by _time_ profile
you mean how much time gets spent in each syscall than the following
should help (time is in nanoseconds):

$ dtrace -n 'syscall::*:entry /pid==$target/ { self->ts=timestamp; }  
syscall::*:return /pid==$target/ { @[probefunc]=sum(timestamp-self- 
 >ts); }' -c "echo Hello World"
dtrace: description 'syscall::*:entry ' matched 468 probes
Hello World
dtrace: pid 1400 has exited

   getpid                                                         1392
   sysi86                                                         2799
   getrlimit                                                      2918
   setcontext                                                     4273
   fstat64                                                        6220
   mmap                                                          15419
   munmap                                                        22593
   write                                                         27860
   ioctl                                                         30750

The script can be modified slightly to also profile all of the libc.

On the other hand, if by real system profile you mean a full fledged
sampling of the application itself than I can suggest running Git
under Shark, and not under Instruments. Although I'm extremly
curious about *why* would you need a full fledged *application*
level profile of Git as opposed to a profile of how Git interacts
with an OS.

> The system call profile is trivial - it's generally going to be pretty
> similar under OS X and Linux (modulo library differences, but git  
> doesn't
> really use any really complex libraries that would do system calls).
>
> The problem we've had in the past is that Linux is simply an order of
> magnitude faster (sometimes more) at some operations than OS X is, so
> issues that show up on OS X don't even show up on Linux.
>
> This was the case for doing lots of small "mmap()/munmap()" calls, for
> example, where we literally had a load where OS X was two orders of
> magnitude slower. We switched over to reading the files with "pread()"
> instead of mmap(), and that fixed that particular issue.

Totally understood!

Thanks,
Roman.

Re: Git performance on OS X

[Linus Torvalds]

On Sun, 20 Apr 2008, Pieter de Bie wrote:
> 
> Yes, I just tested this.
> 
> 	for (int i = 0; i < 50000; i++) {
> 		sprintf(s, "/Users/pieter/test/perf/%i", i);
> 		int ret = lstat(s, a);
> 	}
> 
> This loop needs about 3 seconds to  run. Replacing the i with 10 in the
> sprintf reduces it to 0.24seconds.

Ok.

On my machine, that's

	real    0m0.090s

with the 50,000 different files, and with the same filename it's

	real    0m0.081s

so yes, we're looking at another case of Linux performance just being in a 
class of its own.

Taking three seconds for the warm-cache case for just 50,000 files is 
ludicrous. That's about an order-and-a-half slower than what I see.

Maybe my CPU is faster too (2.66GHz Core 2), but the thing is, Linux 
really does tend to outperform others at a lot of these kinds of loads. 
System calls are fast to begin with, and the Linux directory cache kicks 
ass, if I do say so myself.

OS X doth suck. 

			Linus

Re: Git performance on OS X

[Dmitry Potapov]

On Sat, Apr 19, 2008 at 05:31:41PM -0700, Linus Torvalds wrote:
> 
> Maybe my CPU is faster too (2.66GHz Core 2), but the thing is, Linux 
> really does tend to outperform others at a lot of these kinds of loads. 
> System calls are fast to begin with, and the Linux directory cache kicks 
> ass, if I do say so myself.

Yes, Linux is really fast. Even with relatively old AMD Sempron 1.8 GHz,
I got the following numbers:
real    0m0.177s
real    0m0.154s

Dmitry

Re: Git performance on OS X

[Junio C Hamano]

Linus Torvalds <torvalds@linux-foundation.org> writes:

> At least two of them are due to ce_smudge_racily_clean_entry(), which in
> turn is because we trigger the is_racy_timestamp() test. Hmm.

There is one change that has been held back in 'next' for quite some time.
Perhaps it would help?

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

[Luciano Rocha]

An implementation of stat(2) and lstat(2) caching. Both the return code
and returned information are cached.

Signed-off-by: Luciano Rocha <strange@nsk.no-ip.org>
---
On Sat, Apr 19, 2008 at 03:39:37PM -0700, Linus Torvalds wrote:
> Yeah. I didn't look any further, but we do a total of *nine* 'lstat()' 
> calls for each file we know about that is dirty, and *seven* when they are 
> clean. Plus maybe a few more.

That's a lot. Why not use a stat cache?

With these changes, my git status . in WebKit changes from 28.215s to
15.414s.

 stat-cache.c |   69 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 stat-cache.h |    9 +++++++
 2 files changed, 78 insertions(+), 0 deletions(-)
 create mode 100644 stat-cache.c
 create mode 100644 stat-cache.h

diff --git a/stat-cache.c b/stat-cache.c
new file mode 100644
index 0000000..6a33cec
--- /dev/null
+++ b/stat-cache.c
@@ -0,0 +1,69 @@
+/*
+ * Cache (l)stat operations
+ */
+
+#include "stat-cache.h"
+#include "hash.h"
+#include "path-list.h";
+
+static struct hash_table stat_cache;
+static struct hash_table lstat_cache;
+
+struct stat_result {
+	struct stat st;
+	int ret;
+};
+
+/* based on hash_name from read_cache.c */
+static unsigned int hash_path(const char *path)
+{
+	unsigned int hash = 0x123;
+
+	while (*path)
+		hash = hash*101 + *path++;
+	return hash;
+}
+
+/* cache is HASH->PATH-LIST->(return code, struct stat) */
+static int cached_stat(int (*f)(const char *, struct stat *),
+		struct hash_table *ht, const char *path, struct stat *buf)
+{
+	unsigned int hash;
+	struct path_list *list;
+	struct path_list_item *cached;
+	struct stat_result *result;
+
+	hash = hash_path(path);
+
+	list = lookup_hash(hash, ht);
+
+	if (!list) {
+		list = xcalloc(1, sizeof *list);
+		list->strdup_paths = 1;
+		insert_hash(hash, list, ht);
+	}
+
+	cached = path_list_lookup(path, list);
+
+	if (cached) {
+		result = cached->util;
+	} else {
+		result = xmalloc(sizeof *result);
+		result->ret = f(path, &result->st);
+		path_list_insert(path, list)->util = result;
+	}
+
+	if (result->ret == 0)
+		memcpy(buf, &result->st, sizeof *buf);
+	return result->ret;
+}
+
+int cstat(const char *path, struct stat *buf)
+{
+	return cached_stat(stat, &stat_cache, path, buf);
+}
+
+int clstat(const char *path, struct stat *buf)
+{
+	return cached_stat(lstat, &lstat_cache, path, buf);
+}
diff --git a/stat-cache.h b/stat-cache.h
new file mode 100644
index 0000000..754348f
--- /dev/null
+++ b/stat-cache.h
@@ -0,0 +1,9 @@
+#ifndef STAT_CACHE_H
+#define STAT_CACHE_H
+
+#include "git-compat-util.h"
+
+int cstat(const char *path, struct stat *buf);
+int clstat(const char *path, struct stat *buf);
+
+#endif /* STAT_CACHE_H */
-- 
1.5.5.76.gbb45.dirty

[PATCH 02/02/RFC] make use of the stat cache

[Luciano Rocha]

Replace stat/lstat calls with cstat/clstat.

Signed-off-by: Luciano Rocha <strange@nsk.no-ip.org>

---
 Makefile                  |    2 ++
 builtin-apply.c           |   13 +++++++------
 builtin-blame.c           |    7 ++++---
 builtin-clean.c           |    3 ++-
 builtin-commit.c          |    7 ++++---
 builtin-count-objects.c   |    3 ++-
 builtin-diff.c            |    3 ++-
 builtin-fetch-pack.c      |    5 +++--
 builtin-grep.c            |    3 ++-
 builtin-init-db.c         |   11 ++++++-----
 builtin-ls-files.c        |    3 ++-
 builtin-mailsplit.c       |    3 ++-
 builtin-merge-recursive.c |    3 ++-
 builtin-mv.c              |    9 +++++----
 builtin-pack-objects.c    |    3 ++-
 builtin-prune.c           |    5 +++--
 builtin-rerere.c          |   15 ++++++++-------
 builtin-rm.c              |    3 ++-
 builtin-update-index.c    |    3 ++-
 check-racy.c              |    3 ++-
 combine-diff.c            |    3 ++-
 daemon.c                  |    3 ++-
 diff-lib.c                |    5 +++--
 diff.c                    |    9 +++++----
 dir.c                     |    7 ++++---
 entry.c                   |   11 ++++++-----
 help.c                    |    5 +++--
 http-push.c               |    3 ++-
 http-walker.c             |    3 ++-
 path.c                    |    9 +++++----
 read-cache.c              |    7 ++++---
 refs.c                    |   11 ++++++-----
 setup.c                   |    5 +++--
 sha1_file.c               |   15 ++++++++-------
 sha1_name.c               |    5 +++--
 symlinks.c                |    3 ++-
 test-chmtime.c            |    3 ++-
 transport.c               |    3 ++-
 unpack-trees.c            |    7 ++++---
 xdiff-interface.c         |    3 ++-
 40 files changed, 134 insertions(+), 93 deletions(-)

diff --git a/Makefile b/Makefile
index 2cf38f0..7f01b71 100644
--- a/Makefile
+++ b/Makefile
@@ -374,6 +374,7 @@ LIB_H += tree.h
 LIB_H += tree-walk.h
 LIB_H += unpack-trees.h
 LIB_H += utf8.h
+LIB_H += stat-cache.h
 
 LIB_OBJS += alias.o
 LIB_OBJS += alloc.o
@@ -465,6 +466,7 @@ LIB_OBJS += write_or_die.o
 LIB_OBJS += ws.o
 LIB_OBJS += wt-status.o
 LIB_OBJS += xdiff-interface.o
+LIB_OBJS += stat-cache.o
 
 BUILTIN_OBJS += builtin-add.o
 BUILTIN_OBJS += builtin-annotate.o
diff --git a/builtin-apply.c b/builtin-apply.c
index caa3f2a..bedc7f4 100644
--- a/builtin-apply.c
+++ b/builtin-apply.c
@@ -12,6 +12,7 @@
 #include "blob.h"
 #include "delta.h"
 #include "builtin.h"
+#include "stat-cache.h"
 
 /*
  *  --check turns on checking that the working tree matches the
@@ -2237,7 +2238,7 @@ static int apply_data(struct patch *patch, struct stat *st, struct cache_entry *
 static int check_to_create_blob(const char *new_name, int ok_if_exists)
 {
 	struct stat nst;
-	if (!lstat(new_name, &nst)) {
+	if (!clstat(new_name, &nst)) {
 		if (S_ISDIR(nst.st_mode) || ok_if_exists)
 			return 0;
 		/*
@@ -2289,7 +2290,7 @@ static int check_patch(struct patch *patch, struct patch *prev_patch)
 		unsigned st_mode = 0;
 
 		if (!cached)
-			stat_ret = lstat(old_name, &st);
+			stat_ret = clstat(old_name, &st);
 		if (check_index) {
 			int pos = cache_name_pos(old_name, strlen(old_name));
 			if (pos < 0)
@@ -2311,7 +2312,7 @@ static int check_patch(struct patch *patch, struct patch *prev_patch)
 				if (checkout_entry(ce,
 						   &costate,
 						   NULL) ||
-				    lstat(old_name, &st))
+				    clstat(old_name, &st))
 					return -1;
 			}
 			if (!cached && verify_index_match(ce, &st))
@@ -2632,7 +2633,7 @@ static void add_index_file(const char *path, unsigned mode, void *buf, unsigned
 			die("corrupt patch for subproject %s", path);
 	} else {
 		if (!cached) {
-			if (lstat(path, &st) < 0)
+			if (clstat(path, &st) < 0)
 				die("unable to stat newly created file %s",
 				    path);
 			fill_stat_cache_info(ce, &st);
@@ -2651,7 +2652,7 @@ static int try_create_file(const char *path, unsigned int mode, const char *buf,
 
 	if (S_ISGITLINK(mode)) {
 		struct stat st;
-		if (!lstat(path, &st) && S_ISDIR(st.st_mode))
+		if (!clstat(path, &st) && S_ISDIR(st.st_mode))
 			return 0;
 		return mkdir(path, 0777);
 	}
@@ -2703,7 +2704,7 @@ static void create_one_file(char *path, unsigned mode, const char *buf, unsigned
 		 * used to be.
 		 */
 		struct stat st;
-		if (!lstat(path, &st) && (!S_ISDIR(st.st_mode) || !rmdir(path)))
+		if (!clstat(path, &st) && (!S_ISDIR(st.st_mode) || !rmdir(path)))
 			errno = EEXIST;
 	}
 
diff --git a/builtin-blame.c b/builtin-blame.c
index bfd562d..ca52fa8 100644
--- a/builtin-blame.c
+++ b/builtin-blame.c
@@ -18,6 +18,7 @@
 #include "cache-tree.h"
 #include "path-list.h"
 #include "mailmap.h"
+#include "stat-cache.h"
 
 static char blame_usage[] =
 "git-blame [-c] [-b] [-l] [--root] [-t] [-f] [-n] [-s] [-p] [-w] [-L n,m] [-S <revs-file>] [-M] [-C] [-C] [--contents <filename>] [--incremental] [commit] [--] file\n"
@@ -1879,7 +1880,7 @@ static void sanity_check_refcnt(struct scoreboard *sb)
 static int has_path_in_work_tree(const char *path)
 {
 	struct stat st;
-	return !lstat(path, &st);
+	return !clstat(path, &st);
 }
 
 static unsigned parse_score(const char *arg)
@@ -2038,12 +2039,12 @@ static struct commit *fake_working_tree_commit(const char *path, const char *con
 		unsigned long fin_size;
 
 		if (contents_from) {
-			if (stat(contents_from, &st) < 0)
+			if (cstat(contents_from, &st) < 0)
 				die("Cannot stat %s", contents_from);
 			read_from = contents_from;
 		}
 		else {
-			if (lstat(path, &st) < 0)
+			if (clstat(path, &st) < 0)
 				die("Cannot lstat %s", path);
 			read_from = path;
 		}
diff --git a/builtin-clean.c b/builtin-clean.c
index 6778a03..97a8ec6 100644
--- a/builtin-clean.c
+++ b/builtin-clean.c
@@ -11,6 +11,7 @@
 #include "dir.h"
 #include "parse-options.h"
 #include "quote.h"
+#include "stat-cache.h"
 
 static int force = -1; /* unset */
 
@@ -123,7 +124,7 @@ int cmd_clean(int argc, const char **argv, const char *prefix)
 		 * recursive directory removal, so lstat() here could
 		 * fail with ENOENT.
 		 */
-		if (lstat(ent->name, &st))
+		if (clstat(ent->name, &st))
 			continue;
 
 		if (pathspec) {
diff --git a/builtin-commit.c b/builtin-commit.c
index bcb7aaa..f5ce6f1 100644
--- a/builtin-commit.c
+++ b/builtin-commit.c
@@ -23,6 +23,7 @@
 #include "parse-options.h"
 #include "path-list.h"
 #include "unpack-trees.h"
+#include "stat-cache.h"
 
 static const char * const builtin_commit_usage[] = {
 	"git-commit [options] [--] <filepattern>...",
@@ -430,15 +431,15 @@ static int prepare_to_commit(const char *index_file, const char *prefix)
 		strbuf_add(&sb, buffer + 2, strlen(buffer + 2));
 		hook_arg1 = "commit";
 		hook_arg2 = use_message;
-	} else if (!stat(git_path("MERGE_MSG"), &statbuf)) {
+	} else if (!cstat(git_path("MERGE_MSG"), &statbuf)) {
 		if (strbuf_read_file(&sb, git_path("MERGE_MSG"), 0) < 0)
 			die("could not read MERGE_MSG: %s", strerror(errno));
 		hook_arg1 = "merge";
-	} else if (!stat(git_path("SQUASH_MSG"), &statbuf)) {
+	} else if (!cstat(git_path("SQUASH_MSG"), &statbuf)) {
 		if (strbuf_read_file(&sb, git_path("SQUASH_MSG"), 0) < 0)
 			die("could not read SQUASH_MSG: %s", strerror(errno));
 		hook_arg1 = "squash";
-	} else if (template_file && !stat(template_file, &statbuf)) {
+	} else if (template_file && !cstat(template_file, &statbuf)) {
 		if (strbuf_read_file(&sb, template_file, 0) < 0)
 			die("could not read %s: %s",
 			    template_file, strerror(errno));
diff --git a/builtin-count-objects.c b/builtin-count-objects.c
index f00306f..fd4832e 100644
--- a/builtin-count-objects.c
+++ b/builtin-count-objects.c
@@ -7,6 +7,7 @@
 #include "cache.h"
 #include "builtin.h"
 #include "parse-options.h"
+#include "stat-cache.h"
 
 static void count_objects(DIR *d, char *path, int len, int verbose,
 			  unsigned long *loose,
@@ -40,7 +41,7 @@ static void count_objects(DIR *d, char *path, int len, int verbose,
 			memcpy(path + len + 3, ent->d_name, 38);
 			path[len + 2] = '/';
 			path[len + 41] = 0;
-			if (lstat(path, &st) || !S_ISREG(st.st_mode))
+			if (clstat(path, &st) || !S_ISREG(st.st_mode))
 				bad = 1;
 			else
 				(*loose_size) += xsize_t(st.st_blocks);
diff --git a/builtin-diff.c b/builtin-diff.c
index 7c2a841..fab2f79 100644
--- a/builtin-diff.c
+++ b/builtin-diff.c
@@ -13,6 +13,7 @@
 #include "revision.h"
 #include "log-tree.h"
 #include "builtin.h"
+#include "stat-cache.h"
 
 struct blobinfo {
 	unsigned char sha1[20];
@@ -69,7 +70,7 @@ static int builtin_diff_b_f(struct rev_info *revs,
 	if (argc > 1)
 		usage(builtin_diff_usage);
 
-	if (lstat(path, &st))
+	if (clstat(path, &st))
 		die("'%s': %s", path, strerror(errno));
 	if (!(S_ISREG(st.st_mode) || S_ISLNK(st.st_mode)))
 		die("'%s': not a regular file or symlink", path);
diff --git a/builtin-fetch-pack.c b/builtin-fetch-pack.c
index 65350ca..b3aba25 100644
--- a/builtin-fetch-pack.c
+++ b/builtin-fetch-pack.c
@@ -9,6 +9,7 @@
 #include "fetch-pack.h"
 #include "remote.h"
 #include "run-command.h"
+#include "stat-cache.h"
 
 static int transfer_unpack_limit = -1;
 static int fetch_unpack_limit = -1;
@@ -780,7 +781,7 @@ struct ref *fetch_pack(struct fetch_pack_args *my_args,
 	fetch_pack_setup();
 	memcpy(&args, my_args, sizeof(args));
 	if (args.depth > 0) {
-		if (stat(git_path("shallow"), &st))
+		if (cstat(git_path("shallow"), &st))
 			st.st_mtime = 0;
 	}
 
@@ -801,7 +802,7 @@ struct ref *fetch_pack(struct fetch_pack_args *my_args,
 #ifdef USE_NSEC
 		mtime.usec = st.st_mtim.usec;
 #endif
-		if (stat(shallow, &st)) {
+		if (cstat(shallow, &st)) {
 			if (mtime.sec)
 				die("shallow file was removed during fetch");
 		} else if (st.st_mtime != mtime.sec
diff --git a/builtin-grep.c b/builtin-grep.c
index ef29910..1fd1c58 100644
--- a/builtin-grep.c
+++ b/builtin-grep.c
@@ -11,6 +11,7 @@
 #include "tree-walk.h"
 #include "builtin.h"
 #include "grep.h"
+#include "stat-cache.h"
 
 #ifndef NO_EXTERNAL_GREP
 #ifdef __unix__
@@ -132,7 +133,7 @@ static int grep_file(struct grep_opt *opt, const char *filename)
 	char *data;
 	size_t sz;
 
-	if (lstat(filename, &st) < 0) {
+	if (clstat(filename, &st) < 0) {
 	err_ret:
 		if (errno != ENOENT)
 			error("'%s': %s", filename, strerror(errno));
diff --git a/builtin-init-db.c b/builtin-init-db.c
index 2854868..3060c1a 100644
--- a/builtin-init-db.c
+++ b/builtin-init-db.c
@@ -6,6 +6,7 @@
 #include "cache.h"
 #include "builtin.h"
 #include "exec_cmd.h"
+#include "stat-cache.h"
 
 #ifndef DEFAULT_GIT_TEMPLATE_DIR
 #define DEFAULT_GIT_TEMPLATE_DIR "/usr/share/git-core/templates"
@@ -56,14 +57,14 @@ static void copy_templates_1(char *path, int baselen,
 			die("insanely long template name %s", de->d_name);
 		memcpy(path + baselen, de->d_name, namelen+1);
 		memcpy(template + template_baselen, de->d_name, namelen+1);
-		if (lstat(path, &st_git)) {
+		if (clstat(path, &st_git)) {
 			if (errno != ENOENT)
 				die("cannot stat %s", path);
 		}
 		else
 			exists = 1;
 
-		if (lstat(template, &st_template))
+		if (clstat(template, &st_template))
 			die("cannot stat template %s", template);
 
 		if (S_ISDIR(st_template.st_mode)) {
@@ -235,10 +236,10 @@ static int create_default_files(const char *git_dir, const char *template_path)
 
 	/* Check filemode trustability */
 	filemode = TEST_FILEMODE;
-	if (TEST_FILEMODE && !lstat(path, &st1)) {
+	if (TEST_FILEMODE && !clstat(path, &st1)) {
 		struct stat st2;
 		filemode = (!chmod(path, st1.st_mode ^ S_IXUSR) &&
-				!lstat(path, &st2) &&
+				!clstat(path, &st2) &&
 				st1.st_mode != st2.st_mode);
 	}
 	git_config_set("core.filemode", filemode ? "true" : "false");
@@ -262,7 +263,7 @@ static int create_default_files(const char *git_dir, const char *template_path)
 		if (!close(xmkstemp(path)) &&
 		    !unlink(path) &&
 		    !symlink("testing", path) &&
-		    !lstat(path, &st1) &&
+		    !clstat(path, &st1) &&
 		    S_ISLNK(st1.st_mode))
 			unlink(path); /* good */
 		else
diff --git a/builtin-ls-files.c b/builtin-ls-files.c
index dc7eab8..be4a0fa 100644
--- a/builtin-ls-files.c
+++ b/builtin-ls-files.c
@@ -10,6 +10,7 @@
 #include "dir.h"
 #include "builtin.h"
 #include "tree.h"
+#include "stat-cache.h"
 
 static int abbrev;
 static int show_deleted;
@@ -256,7 +257,7 @@ static void show_files(struct dir_struct *dir, const char *prefix)
 			int dtype = ce_to_dtype(ce);
 			if (excluded(dir, ce->name, &dtype) != dir->show_ignored)
 				continue;
-			err = lstat(ce->name, &st);
+			err = clstat(ce->name, &st);
 			if (show_deleted && err)
 				show_ce_entry(tag_removed, ce);
 			if (show_modified && ce_modified(ce, &st, 0))
diff --git a/builtin-mailsplit.c b/builtin-mailsplit.c
index 46b27cd..838c52f 100644
--- a/builtin-mailsplit.c
+++ b/builtin-mailsplit.c
@@ -7,6 +7,7 @@
 #include "cache.h"
 #include "builtin.h"
 #include "path-list.h"
+#include "stat-cache.h"
 
 static const char git_mailsplit_usage[] =
 "git-mailsplit [-d<prec>] [-f<n>] [-b] -o<directory> <mbox>|<Maildir>...";
@@ -278,7 +279,7 @@ int cmd_mailsplit(int argc, const char **argv, const char *prefix)
 			continue;
 		}
 
-		if (stat(arg, &argstat) == -1) {
+		if (cstat(arg, &argstat) == -1) {
 			error("cannot stat %s (%s)", arg, strerror(errno));
 			return 1;
 		}
diff --git a/builtin-merge-recursive.c b/builtin-merge-recursive.c
index 910c0d2..5eb2407 100644
--- a/builtin-merge-recursive.c
+++ b/builtin-merge-recursive.c
@@ -19,6 +19,7 @@
 #include "interpolate.h"
 #include "attr.h"
 #include "merge-recursive.h"
+#include "stat-cache.h"
 
 static int subtree_merge;
 
@@ -470,7 +471,7 @@ static char *unique_path(const char *path, const char *branch)
 			*p = '_';
 	while (path_list_has_path(&current_file_set, newpath) ||
 	       path_list_has_path(&current_directory_set, newpath) ||
-	       lstat(newpath, &st) == 0)
+	       clstat(newpath, &st) == 0)
 		sprintf(p, "_%d", suffix++);
 
 	path_list_insert(newpath, &current_file_set);
diff --git a/builtin-mv.c b/builtin-mv.c
index 94f6dd2..807984a 100644
--- a/builtin-mv.c
+++ b/builtin-mv.c
@@ -9,6 +9,7 @@
 #include "cache-tree.h"
 #include "path-list.h"
 #include "parse-options.h"
+#include "stat-cache.h"
 
 static const char * const builtin_mv_usage[] = {
 	"git-mv [options] <source>... <destination>",
@@ -98,7 +99,7 @@ int cmd_mv(int argc, const char **argv, const char *prefix)
 	if (dest_path[0][0] == '\0')
 		/* special case: "." was normalized to "" */
 		destination = copy_pathspec(dest_path[0], argv, argc, 1);
-	else if (!lstat(dest_path[0], &st) &&
+	else if (!clstat(dest_path[0], &st) &&
 			S_ISDIR(st.st_mode)) {
 		dest_path[0] = add_slash(dest_path[0]);
 		destination = copy_pathspec(dest_path[0], argv, argc, 1);
@@ -118,13 +119,13 @@ int cmd_mv(int argc, const char **argv, const char *prefix)
 			printf("Checking rename of '%s' to '%s'\n", src, dst);
 
 		length = strlen(src);
-		if (lstat(src, &st) < 0)
+		if (clstat(src, &st) < 0)
 			bad = "bad source";
 		else if (!strncmp(src, dst, length) &&
 				(dst[length] == 0 || dst[length] == '/')) {
 			bad = "can not move directory into itself";
 		} else if ((src_is_dir = S_ISDIR(st.st_mode))
-				&& lstat(dst, &st) == 0)
+				&& clstat(dst, &st) == 0)
 			bad = "cannot move directory over file";
 		else if (src_is_dir) {
 			const char *src_w_slash = add_slash(src);
@@ -177,7 +178,7 @@ int cmd_mv(int argc, const char **argv, const char *prefix)
 				}
 				argc += last - first;
 			}
-		} else if (lstat(dst, &st) == 0) {
+		} else if (clstat(dst, &st) == 0) {
 			bad = "destination exists";
 			if (force) {
 				/*
diff --git a/builtin-pack-objects.c b/builtin-pack-objects.c
index 777f272..50da2fa 100644
--- a/builtin-pack-objects.c
+++ b/builtin-pack-objects.c
@@ -16,6 +16,7 @@
 #include "list-objects.h"
 #include "progress.h"
 #include "refs.h"
+#include "stat-cache.h"
 
 #ifdef THREADED_DELTA_SEARCH
 #include "thread-utils.h"
@@ -530,7 +531,7 @@ static void write_pack_file(void)
 			 * packs then we should modify the mtime of later ones
 			 * to preserve this property.
 			 */
-			if (stat(tmpname, &st) < 0) {
+			if (cstat(tmpname, &st) < 0) {
 				warning("failed to stat %s: %s",
 					tmpname, strerror(errno));
 			} else if (!last_mtime) {
diff --git a/builtin-prune.c b/builtin-prune.c
index 25f9304..ca4f636 100644
--- a/builtin-prune.c
+++ b/builtin-prune.c
@@ -5,6 +5,7 @@
 #include "builtin.h"
 #include "reachable.h"
 #include "parse-options.h"
+#include "stat-cache.h"
 
 static const char * const prune_usage[] = {
 	"git-prune [-n] [--expire <time>] [--] [<head>...]",
@@ -18,7 +19,7 @@ static int prune_object(char *path, const char *filename, const unsigned char *s
 	const char *fullpath = mkpath("%s/%s", path, filename);
 	if (expire) {
 		struct stat st;
-		if (lstat(fullpath, &st))
+		if (clstat(fullpath, &st))
 			return error("Could not stat '%s'", fullpath);
 		if (st.st_mtime > expire)
 			return 0;
@@ -114,7 +115,7 @@ static void remove_temporary_files(void)
 				continue;
 			if (expire) {
 				struct stat st;
-				if (stat(name, &st) != 0 || st.st_mtime >= expire)
+				if (cstat(name, &st) != 0 || st.st_mtime >= expire)
 					continue;
 			}
 			printf("Removing stale temporary file %s\n", name);
diff --git a/builtin-rerere.c b/builtin-rerere.c
index c607aad..ff18ea9 100644
--- a/builtin-rerere.c
+++ b/builtin-rerere.c
@@ -3,6 +3,7 @@
 #include "path-list.h"
 #include "xdiff/xdiff.h"
 #include "xdiff-interface.h"
+#include "stat-cache.h"
 
 #include <time.h>
 
@@ -219,11 +220,11 @@ static void garbage_collect(struct path_list *rr)
 			continue;
 		i = snprintf(buf + len, sizeof(buf) - len, "%s", name);
 		strlcpy(buf + len + i, "/preimage", sizeof(buf) - len - i);
-		if (stat(buf, &st))
+		if (cstat(buf, &st))
 			continue;
 		then = st.st_mtime;
 		strlcpy(buf + len + i, "/postimage", sizeof(buf) - len - i);
-		cutoff = stat(buf, &st) ? cutoff_noresolve : cutoff_resolve;
+		cutoff = cstat(buf, &st) ? cutoff_noresolve : cutoff_resolve;
 		if (then < now - cutoff * 86400) {
 			buf[len + i] = '\0';
 			path_list_insert(xstrdup(name), &to_remove);
@@ -311,8 +312,8 @@ static int do_plain_rerere(struct path_list *rr, int fd)
 		const char *path = rr->items[i].path;
 		const char *name = (const char *)rr->items[i].util;
 
-		if (!stat(rr_path(name, "preimage"), &st) &&
-				!stat(rr_path(name, "postimage"), &st)) {
+		if (!cstat(rr_path(name, "preimage"), &st) &&
+				!cstat(rr_path(name, "postimage"), &st)) {
 			if (!merge(name, path)) {
 				fprintf(stderr, "Resolved '%s' using "
 						"previous resolution.\n", path);
@@ -362,7 +363,7 @@ static int is_rerere_enabled(void)
 		return 0;
 
 	rr_cache = git_path("rr-cache");
-	rr_cache_exists = !stat(rr_cache, &st) && S_ISDIR(st.st_mode);
+	rr_cache_exists = !cstat(rr_cache, &st) && S_ISDIR(st.st_mode);
 	if (rerere_enabled < 0)
 		return rr_cache_exists;
 
@@ -412,9 +413,9 @@ int cmd_rerere(int argc, const char **argv, const char *prefix)
 		for (i = 0; i < merge_rr.nr; i++) {
 			struct stat st;
 			const char *name = (const char *)merge_rr.items[i].util;
-			if (!stat(git_path("rr-cache/%s", name), &st) &&
+			if (!cstat(git_path("rr-cache/%s", name), &st) &&
 					S_ISDIR(st.st_mode) &&
-					stat(rr_path(name, "postimage"), &st))
+					cstat(rr_path(name, "postimage"), &st))
 				unlink_rr_item(name);
 		}
 		unlink(merge_rr_path);
diff --git a/builtin-rm.c b/builtin-rm.c
index c0a8bb6..4039a44 100644
--- a/builtin-rm.c
+++ b/builtin-rm.c
@@ -9,6 +9,7 @@
 #include "cache-tree.h"
 #include "tree-walk.h"
 #include "parse-options.h"
+#include "stat-cache.h"
 
 static const char * const builtin_rm_usage[] = {
 	"git-rm [options] [--] <file>...",
@@ -76,7 +77,7 @@ static int check_local_mod(unsigned char *head, int index_only)
 			continue; /* removing unmerged entry */
 		ce = active_cache[pos];
 
-		if (lstat(ce->name, &st) < 0) {
+		if (clstat(ce->name, &st) < 0) {
 			if (errno != ENOENT)
 				fprintf(stderr, "warning: '%s': %s",
 					ce->name, strerror(errno));
diff --git a/builtin-update-index.c b/builtin-update-index.c
index a8795d3..e88cd95 100644
--- a/builtin-update-index.c
+++ b/builtin-update-index.c
@@ -9,6 +9,7 @@
 #include "tree-walk.h"
 #include "builtin.h"
 #include "refs.h"
+#include "stat-cache.h"
 
 /*
  * Default to not allowing changes to the list of files. The
@@ -198,7 +199,7 @@ static int process_path(const char *path)
 	 * First things first: get the stat information, to decide
 	 * what to do about the pathname!
 	 */
-	if (lstat(path, &st) < 0)
+	if (clstat(path, &st) < 0)
 		return process_lstat_error(path, errno);
 
 	len = strlen(path);
diff --git a/check-racy.c b/check-racy.c
index 00d92a1..a33029f 100644
--- a/check-racy.c
+++ b/check-racy.c
@@ -1,4 +1,5 @@
 #include "cache.h"
+#include "stat-cache.h"
 
 int main(int ac, char **av)
 {
@@ -11,7 +12,7 @@ int main(int ac, char **av)
 		struct cache_entry *ce = active_cache[i];
 		struct stat st;
 
-		if (lstat(ce->name, &st)) {
+		if (clstat(ce->name, &st)) {
 			error("lstat(%s): %s", ce->name, strerror(errno));
 			continue;
 		}
diff --git a/combine-diff.c b/combine-diff.c
index 0e19cba..1e0af00 100644
--- a/combine-diff.c
+++ b/combine-diff.c
@@ -6,6 +6,7 @@
 #include "quote.h"
 #include "xdiff-interface.h"
 #include "log-tree.h"
+#include "stat-cache.h"
 
 static struct combine_diff_path *intersect_paths(struct combine_diff_path *curr, int n, int num_parent)
 {
@@ -683,7 +684,7 @@ static void show_patch_diff(struct combine_diff_path *elem, int num_parent,
 		struct stat st;
 		int fd = -1;
 
-		if (lstat(elem->path, &st) < 0)
+		if (clstat(elem->path, &st) < 0)
 			goto deleted_file;
 
 		if (S_ISLNK(st.st_mode)) {
diff --git a/daemon.c b/daemon.c
index 2b4a6f1..ac4943b 100644
--- a/daemon.c
+++ b/daemon.c
@@ -2,6 +2,7 @@
 #include "pkt-line.h"
 #include "exec_cmd.h"
 #include "interpolate.h"
+#include "stat-cache.h"
 
 #include <syslog.h>
 
@@ -1187,7 +1188,7 @@ int main(int argc, char **argv)
 	if (base_path) {
 		struct stat st;
 
-		if (stat(base_path, &st) || !S_ISDIR(st.st_mode))
+		if (cstat(base_path, &st) || !S_ISDIR(st.st_mode))
 			die("base-path '%s' does not exist or "
 			    "is not a directory", base_path);
 	}
diff --git a/diff-lib.c b/diff-lib.c
index 069e450..be594ba 100644
--- a/diff-lib.c
+++ b/diff-lib.c
@@ -11,6 +11,7 @@
 #include "path-list.h"
 #include "unpack-trees.h"
 #include "refs.h"
+#include "stat-cache.h"
 
 /*
  * diff-files
@@ -40,7 +41,7 @@ static int get_mode(const char *path, int *mode)
 		*mode = 0;
 	else if (!strcmp(path, "-"))
 		*mode = create_ce_mode(0666);
-	else if (stat(path, &st))
+	else if (cstat(path, &st))
 		return error("Could not access '%s'", path);
 	else
 		*mode = st.st_mode;
@@ -340,7 +341,7 @@ int run_diff_files_cmd(struct rev_info *revs, int argc, const char **argv)
  */
 static int check_work_tree_entity(const struct cache_entry *ce, struct stat *st, char *symcache)
 {
-	if (lstat(ce->name, st) < 0) {
+	if (clstat(ce->name, st) < 0) {
 		if (errno != ENOENT && errno != ENOTDIR)
 			return -1;
 		return 1;
diff --git a/diff.c b/diff.c
index 8022e67..4508000 100644
--- a/diff.c
+++ b/diff.c
@@ -11,6 +11,7 @@
 #include "attr.h"
 #include "run-command.h"
 #include "utf8.h"
+#include "stat-cache.h"
 
 #ifdef NO_FAST_WORKING_DIRECTORY
 #define FAST_WORKING_DIRECTORY 0
@@ -1624,7 +1625,7 @@ static int reuse_worktree_file(const char *name, const unsigned char *sha1, int
 	 * If ce matches the file in the work tree, we can reuse it.
 	 */
 	if (ce_uptodate(ce) ||
-	    (!lstat(name, &st) && !ce_match_stat(ce, &st, 0)))
+	    (!clstat(name, &st) && !ce_match_stat(ce, &st, 0)))
 		return 1;
 
 	return 0;
@@ -1694,7 +1695,7 @@ int diff_populate_filespec(struct diff_filespec *s, int size_only)
 		if (!strcmp(s->path, "-"))
 			return populate_from_stdin(s);
 
-		if (lstat(s->path, &st) < 0) {
+		if (clstat(s->path, &st) < 0) {
 			if (errno == ENOENT) {
 			err_empty:
 				err = -1;
@@ -1810,7 +1811,7 @@ static void prepare_temp_file(const char *name,
 	if (!one->sha1_valid ||
 	    reuse_worktree_file(name, one->sha1, 1)) {
 		struct stat st;
-		if (lstat(name, &st) < 0) {
+		if (clstat(name, &st) < 0) {
 			if (errno == ENOENT)
 				goto not_a_valid_file;
 			die("stat(%s): %s", name, strerror(errno));
@@ -1996,7 +1997,7 @@ static void diff_fill_sha1_info(struct diff_filespec *one)
 				hashcpy(one->sha1, null_sha1);
 				return;
 			}
-			if (lstat(one->path, &st) < 0)
+			if (clstat(one->path, &st) < 0)
 				die("stat %s", one->path);
 			if (index_path(one->sha1, one->path, &st, 0))
 				die("cannot hash %s\n", one->path);
diff --git a/dir.c b/dir.c
index d79762c..6bdab38 100644
--- a/dir.c
+++ b/dir.c
@@ -8,6 +8,7 @@
 #include "cache.h"
 #include "dir.h"
 #include "refs.h"
+#include "stat-cache.h"
 
 struct path_simplify {
 	int len;
@@ -538,7 +539,7 @@ static int get_dtype(struct dirent *de, const char *path)
 
 	if (dtype != DT_UNKNOWN)
 		return dtype;
-	if (lstat(path, &st))
+	if (clstat(path, &st))
 		return dtype;
 	if (S_ISREG(st.st_mode))
 		return DT_REG;
@@ -721,7 +722,7 @@ int read_directory(struct dir_struct *dir, const char *path, const char *base, i
 int file_exists(const char *f)
 {
 	struct stat sb;
-	return lstat(f, &sb) == 0;
+	return clstat(f, &sb) == 0;
 }
 
 /*
@@ -788,7 +789,7 @@ int remove_dir_recursively(struct strbuf *path, int only_empty)
 
 		strbuf_setlen(path, len);
 		strbuf_addstr(path, e->d_name);
-		if (lstat(path->buf, &st))
+		if (clstat(path->buf, &st))
 			; /* fall thru */
 		else if (S_ISDIR(st.st_mode)) {
 			if (!remove_dir_recursively(path, only_empty))
diff --git a/entry.c b/entry.c
index 222aaa3..6d31ac3 100644
--- a/entry.c
+++ b/entry.c
@@ -1,5 +1,6 @@
 #include "cache.h"
 #include "blob.h"
+#include "stat-cache.h"
 
 static void create_directories(const char *path, const struct checkout *state)
 {
@@ -21,13 +22,13 @@ static void create_directories(const char *path, const struct checkout *state)
 			 * allowed to be a symlink to an existing
 			 * directory.
 			 */
-			stat_status = stat(buf, &st);
+			stat_status = cstat(buf, &st);
 		else
 			/*
 			 * if there currently is a symlink, we would
 			 * want to replace it with a real directory.
 			 */
-			stat_status = lstat(buf, &st);
+			stat_status = clstat(buf, &st);
 
 		if (!stat_status && S_ISDIR(st.st_mode))
 			continue; /* ok, it is already a directory. */
@@ -67,7 +68,7 @@ static void remove_subtree(const char *path)
 		     ((de->d_name[1] == '.') && de->d_name[2] == 0)))
 			continue;
 		strcpy(name, de->d_name);
-		if (lstat(pathbuf, &st))
+		if (clstat(pathbuf, &st))
 			die("cannot lstat %s (%s)", pathbuf, strerror(errno));
 		if (S_ISDIR(st.st_mode))
 			remove_subtree(pathbuf);
@@ -184,7 +185,7 @@ static int write_entry(struct cache_entry *ce, char *path, const struct checkout
 
 	if (state->refresh_cache) {
 		struct stat st;
-		lstat(ce->name, &st);
+		clstat(ce->name, &st);
 		fill_stat_cache_info(ce, &st);
 	}
 	return 0;
@@ -202,7 +203,7 @@ int checkout_entry(struct cache_entry *ce, const struct checkout *state, char *t
 	memcpy(path, state->base_dir, len);
 	strcpy(path + len, ce->name);
 
-	if (!lstat(path, &st)) {
+	if (!clstat(path, &st)) {
 		unsigned changed = ce_match_stat(ce, &st, CE_MATCH_IGNORE_VALID);
 		if (!changed)
 			return 0;
diff --git a/help.c b/help.c
index 10298fb..6616f25 100644
--- a/help.c
+++ b/help.c
@@ -9,6 +9,7 @@
 #include "common-cmds.h"
 #include "parse-options.h"
 #include "run-command.h"
+#include "stat-cache.h"
 
 static struct man_viewer_list {
 	void (*exec)(const char *);
@@ -299,7 +300,7 @@ static unsigned int list_commands_in_dir(struct cmdnames *cmds,
 		if (prefixcmp(de->d_name, prefix))
 			continue;
 
-		if (stat(de->d_name, &st) || /* stat, not lstat */
+		if (cstat(de->d_name, &st) || /* stat, not lstat */
 		    !S_ISREG(st.st_mode) ||
 		    !(st.st_mode & S_IXUSR))
 			continue;
@@ -479,7 +480,7 @@ static void get_html_page_path(struct strbuf *page_path, const char *page)
 	struct stat st;
 
 	/* Check that we have a git documentation directory. */
-	if (stat(GIT_HTML_PATH "/git.html", &st) || !S_ISREG(st.st_mode))
+	if (cstat(GIT_HTML_PATH "/git.html", &st) || !S_ISREG(st.st_mode))
 		die("'%s': not a documentation directory.", GIT_HTML_PATH);
 
 	strbuf_init(page_path, 0);
diff --git a/http-push.c b/http-push.c
index 5b23038..f536a8b 100644
--- a/http-push.c
+++ b/http-push.c
@@ -9,6 +9,7 @@
 #include "revision.h"
 #include "exec_cmd.h"
 #include "remote.h"
+#include "stat-cache.h"
 
 #include <expat.h>
 
@@ -732,7 +733,7 @@ static void finish_request(struct transfer_request *request)
 
 		if (request->curl_result != CURLE_OK &&
 		    request->http_code != 416) {
-			if (stat(request->tmpfile, &st) == 0) {
+			if (cstat(request->tmpfile, &st) == 0) {
 				if (st.st_size == 0)
 					unlink(request->tmpfile);
 			}
diff --git a/http-walker.c b/http-walker.c
index 7bda34d..cd16036 100644
--- a/http-walker.c
+++ b/http-walker.c
@@ -3,6 +3,7 @@
 #include "pack.h"
 #include "walker.h"
 #include "http.h"
+#include "stat-cache.h"
 
 #define PREV_BUF_SIZE 4096
 #define RANGE_HEADER_SIZE 30
@@ -237,7 +238,7 @@ static void finish_object_request(struct object_request *obj_req)
 	if (obj_req->http_code == 416) {
 		fprintf(stderr, "Warning: requested range invalid; we may already have all the data.\n");
 	} else if (obj_req->curl_result != CURLE_OK) {
-		if (stat(obj_req->tmpfile, &st) == 0)
+		if (cstat(obj_req->tmpfile, &st) == 0)
 			if (st.st_size == 0)
 				unlink(obj_req->tmpfile);
 		return;
diff --git a/path.c b/path.c
index f4ed979..401ab0f 100644
--- a/path.c
+++ b/path.c
@@ -11,6 +11,7 @@
  * which is what it's designed for.
  */
 #include "cache.h"
+#include "stat-cache.h"
 
 static char bad_path[] = "/bad-path/";
 
@@ -93,7 +94,7 @@ int validate_headref(const char *path)
 	unsigned char sha1[20];
 	int len, fd;
 
-	if (lstat(path, &st) < 0)
+	if (clstat(path, &st) < 0)
 		return -1;
 
 	/* Make sure it is a "refs/.." symlink */
@@ -263,7 +264,7 @@ int adjust_shared_perm(const char *path)
 
 	if (!shared_repository)
 		return 0;
-	if (lstat(path, &st) < 0)
+	if (clstat(path, &st) < 0)
 		return -1;
 	mode = st.st_mode;
 	if (mode & S_IRUSR)
@@ -306,7 +307,7 @@ const char *make_absolute_path(const char *path)
 		die ("Too long path: %.*s", 60, path);
 
 	while (depth--) {
-		if (stat(buf, &st) || !S_ISDIR(st.st_mode)) {
+		if (cstat(buf, &st) || !S_ISDIR(st.st_mode)) {
 			char *last_slash = strrchr(buf, '/');
 			if (last_slash) {
 				*last_slash = '\0';
@@ -338,7 +339,7 @@ const char *make_absolute_path(const char *path)
 			last_elem = NULL;
 		}
 
-		if (!lstat(buf, &st) && S_ISLNK(st.st_mode)) {
+		if (!clstat(buf, &st) && S_ISLNK(st.st_mode)) {
 			len = readlink(buf, next_buf, PATH_MAX);
 			if (len < 0)
 				die ("Invalid symlink: %s", buf);
diff --git a/read-cache.c b/read-cache.c
index a92b25b..a80af56 100644
--- a/read-cache.c
+++ b/read-cache.c
@@ -8,6 +8,7 @@
 #include "cache-tree.h"
 #include "refs.h"
 #include "dir.h"
+#include "stat-cache.h"
 
 /* Index extensions.
  *
@@ -495,7 +496,7 @@ int add_file_to_index(struct index_state *istate, const char *path, int verbose)
 	struct cache_entry *ce;
 	unsigned ce_option = CE_MATCH_IGNORE_VALID|CE_MATCH_RACY_IS_DIRTY;
 
-	if (lstat(path, &st))
+	if (clstat(path, &st))
 		die("%s: unable to stat (%s)", path, strerror(errno));
 
 	if (!S_ISREG(st.st_mode) && !S_ISLNK(st.st_mode) && !S_ISDIR(st.st_mode))
@@ -902,7 +903,7 @@ static struct cache_entry *refresh_cache_ent(struct index_state *istate,
 	if (ce_uptodate(ce))
 		return ce;
 
-	if (lstat(ce->name, &st) < 0) {
+	if (clstat(ce->name, &st) < 0) {
 		if (err)
 			*err = errno;
 		return NULL;
@@ -1290,7 +1291,7 @@ static void ce_smudge_racily_clean_entry(struct cache_entry *ce)
 	 */
 	struct stat st;
 
-	if (lstat(ce->name, &st) < 0)
+	if (clstat(ce->name, &st) < 0)
 		return;
 	if (ce_match_stat_basic(ce, &st))
 		return;
diff --git a/refs.c b/refs.c
index 1b0050e..35d2f2b 100644
--- a/refs.c
+++ b/refs.c
@@ -3,6 +3,7 @@
 #include "object.h"
 #include "tag.h"
 #include "dir.h"
+#include "stat-cache.h"
 
 /* ISSYMREF=01 and ISPACKED=02 are public interfaces */
 #define REF_KNOWS_PEELED 04
@@ -256,7 +257,7 @@ static struct ref_list *get_ref_dir(const char *base, struct ref_list *list)
 			if (has_extension(de->d_name, ".lock"))
 				continue;
 			memcpy(ref + baselen, de->d_name, namelen+1);
-			if (stat(git_path("%s", ref), &st) < 0)
+			if (cstat(git_path("%s", ref), &st) < 0)
 				continue;
 			if (S_ISDIR(st.st_mode)) {
 				list = get_ref_dir(ref, list);
@@ -391,7 +392,7 @@ const char *resolve_ref(const char *ref, unsigned char *sha1, int reading, int *
 		 * born.  It is NOT OK if we are resolving for
 		 * reading.
 		 */
-		if (lstat(path, &st) < 0) {
+		if (clstat(path, &st) < 0) {
 			struct ref_list *list = get_packed_refs();
 			while (list) {
 				if (!strcmp(ref, list->name)) {
@@ -805,7 +806,7 @@ static struct ref_lock *lock_ref_sha1_basic(const char *ref, const unsigned char
 	lock->ref_name = xstrdup(ref);
 	lock->orig_ref_name = xstrdup(orig_ref);
 	ref_file = git_path("%s", ref);
-	if (lstat(ref_file, &st) && errno == ENOENT)
+	if (clstat(ref_file, &st) && errno == ENOENT)
 		lock->force_write = 1;
 	if ((flags & REF_NODEREF) && (type & REF_ISSYMREF))
 		lock->force_write = 1;
@@ -924,7 +925,7 @@ int rename_ref(const char *oldref, const char *newref, const char *logmsg)
 	int flag = 0, logmoved = 0;
 	struct ref_lock *lock;
 	struct stat loginfo;
-	int log = !lstat(git_path("logs/%s", oldref), &loginfo);
+	int log = !clstat(git_path("logs/%s", oldref), &loginfo);
 
 	if (S_ISLNK(loginfo.st_mode))
 		return error("reflog for %s is a symlink", oldref);
@@ -1465,7 +1466,7 @@ static int do_for_each_reflog(const char *base, each_ref_fn fn, void *cb_data)
 			if (has_extension(de->d_name, ".lock"))
 				continue;
 			memcpy(log + baselen, de->d_name, namelen+1);
-			if (stat(git_path("logs/%s", log), &st) < 0)
+			if (cstat(git_path("logs/%s", log), &st) < 0)
 				continue;
 			if (S_ISDIR(st.st_mode)) {
 				retval = do_for_each_reflog(log, fn, cb_data);
diff --git a/setup.c b/setup.c
index 3d2d958..e72b48e 100644
--- a/setup.c
+++ b/setup.c
@@ -1,5 +1,6 @@
 #include "cache.h"
 #include "dir.h"
+#include "stat-cache.h"
 
 static int inside_git_dir = -1;
 static int inside_work_tree = -1;
@@ -148,7 +149,7 @@ void verify_filename(const char *prefix, const char *arg)
 	if (*arg == '-')
 		die("bad flag '%s' used after filename", arg);
 	name = prefix ? prefix_filename(prefix, strlen(prefix), arg) : arg;
-	if (!lstat(name, &st))
+	if (!clstat(name, &st))
 		return;
 	if (errno == ENOENT)
 		die("ambiguous argument '%s': unknown revision or path not in the working tree.\n"
@@ -171,7 +172,7 @@ void verify_non_filename(const char *prefix, const char *arg)
 	if (*arg == '-')
 		return; /* flag */
 	name = prefix ? prefix_filename(prefix, strlen(prefix), arg) : arg;
-	if (!lstat(name, &st))
+	if (!clstat(name, &st))
 		die("ambiguous argument '%s': both revision and filename\n"
 		    "Use '--' to separate filenames from revisions", arg);
 	if (errno != ENOENT && errno != ENOTDIR)
diff --git a/sha1_file.c b/sha1_file.c
index 445a871..777f47d 100644
--- a/sha1_file.c
+++ b/sha1_file.c
@@ -15,6 +15,7 @@
 #include "tree.h"
 #include "refs.h"
 #include "pack-revindex.h"
+#include "stat-cache.h"
 
 #ifndef O_NOATIME
 #if defined(__linux__) && (defined(__i386__) || defined(__PPC__))
@@ -97,7 +98,7 @@ int safe_create_leading_directories(char *path)
 		if (!pos)
 			break;
 		*pos = 0;
-		if (!stat(path, &st)) {
+		if (!cstat(path, &st)) {
 			/* path exists */
 			if (!S_ISDIR(st.st_mode)) {
 				*pos = '/';
@@ -278,7 +279,7 @@ static int link_alt_odb_entry(const char * entry, int len, const char * relative
 	ent->base[pfxlen] = ent->base[entlen-1] = 0;
 
 	/* Detect cases where alternate disappeared */
-	if (stat(ent->base, &st) || !S_ISDIR(st.st_mode)) {
+	if (cstat(ent->base, &st) || !S_ISDIR(st.st_mode)) {
 		error("object directory %s does not exist; "
 		      "check .git/objects/info/alternates.",
 		      ent->base);
@@ -400,13 +401,13 @@ static char *find_sha1_file(const unsigned char *sha1, struct stat *st)
 	char *name = sha1_file_name(sha1);
 	struct alternate_object_database *alt;
 
-	if (!stat(name, st))
+	if (!cstat(name, st))
 		return name;
 	prepare_alt_odb();
 	for (alt = alt_odb_list; alt; alt = alt->next) {
 		name = alt->name;
 		fill_sha1_path(name, sha1);
-		if (!stat(alt->base, st))
+		if (!cstat(alt->base, st))
 			return alt->base;
 	}
 	return NULL;
@@ -804,7 +805,7 @@ struct packed_git *add_packed_git(const char *path, int path_len, int local)
 		return NULL;
 	memcpy(p->pack_name, path, path_len);
 	strcpy(p->pack_name + path_len, ".pack");
-	if (stat(p->pack_name, &st) || !S_ISREG(st.st_mode)) {
+	if (cstat(p->pack_name, &st) || !S_ISREG(st.st_mode)) {
 		free(p);
 		return NULL;
 	}
@@ -2303,7 +2304,7 @@ int write_sha1_from_fd(const unsigned char *sha1, int fd, char *buffer,
 int has_pack_index(const unsigned char *sha1)
 {
 	struct stat st;
-	if (stat(sha1_pack_index_name(sha1), &st))
+	if (cstat(sha1_pack_index_name(sha1), &st))
 		return 0;
 	return 1;
 }
@@ -2311,7 +2312,7 @@ int has_pack_index(const unsigned char *sha1)
 int has_pack_file(const unsigned char *sha1)
 {
 	struct stat st;
-	if (stat(sha1_pack_name(sha1), &st))
+	if (cstat(sha1_pack_name(sha1), &st))
 		return 0;
 	return 1;
 }
diff --git a/sha1_name.c b/sha1_name.c
index 491d2e7..df8b36c 100644
--- a/sha1_name.c
+++ b/sha1_name.c
@@ -5,6 +5,7 @@
 #include "blob.h"
 #include "tree-walk.h"
 #include "refs.h"
+#include "stat-cache.h"
 
 static int find_short_object_filename(int len, const char *name, unsigned char *sha1)
 {
@@ -276,11 +277,11 @@ int dwim_log(const char *str, int len, unsigned char *sha1, char **log)
 		ref = resolve_ref(path, hash, 0, NULL);
 		if (!ref)
 			continue;
-		if (!stat(git_path("logs/%s", path), &st) &&
+		if (!cstat(git_path("logs/%s", path), &st) &&
 		    S_ISREG(st.st_mode))
 			it = path;
 		else if (strcmp(ref, path) &&
-			 !stat(git_path("logs/%s", ref), &st) &&
+			 !cstat(git_path("logs/%s", ref), &st) &&
 			 S_ISREG(st.st_mode))
 			it = ref;
 		else
diff --git a/symlinks.c b/symlinks.c
index be9ace6..2a167a2 100644
--- a/symlinks.c
+++ b/symlinks.c
@@ -1,4 +1,5 @@
 #include "cache.h"
+#include "stat-cache.h"
 
 int has_symlink_leading_path(const char *name, char *last_symlink)
 {
@@ -32,7 +33,7 @@ int has_symlink_leading_path(const char *name, char *last_symlink)
 		memcpy(dp, sp, len);
 		dp[len] = 0;
 
-		if (lstat(path, &st))
+		if (clstat(path, &st))
 			return 0;
 		if (S_ISLNK(st.st_mode)) {
 			if (last_symlink)
diff --git a/test-chmtime.c b/test-chmtime.c
index 90da448..fec5ae2 100644
--- a/test-chmtime.c
+++ b/test-chmtime.c
@@ -1,4 +1,5 @@
 #include "git-compat-util.h"
+#include "stat-cache.h"
 #include <utime.h>
 
 static const char usage_str[] = "(+|=|=+|=-|-)<seconds> <file>...";
@@ -37,7 +38,7 @@ int main(int argc, const char *argv[])
 		struct stat sb;
 		struct utimbuf utb;
 
-		if (stat(argv[i], &sb) < 0) {
+		if (cstat(argv[i], &sb) < 0) {
 			fprintf(stderr, "Failed to stat %s: %s\n",
 			        argv[i], strerror(errno));
 			return -1;
diff --git a/transport.c b/transport.c
index 393e0e8..aace948 100644
--- a/transport.c
+++ b/transport.c
@@ -11,6 +11,7 @@
 #include "bundle.h"
 #include "dir.h"
 #include "refs.h"
+#include "stat-cache.h"
 
 /* rsync support */
 
@@ -703,7 +704,7 @@ static int is_local(const char *url)
 static int is_file(const char *url)
 {
 	struct stat buf;
-	if (stat(url, &buf))
+	if (cstat(url, &buf))
 		return 0;
 	return S_ISREG(buf.st_mode);
 }
diff --git a/unpack-trees.c b/unpack-trees.c
index a59f475..ef7ac26 100644
--- a/unpack-trees.c
+++ b/unpack-trees.c
@@ -7,6 +7,7 @@
 #include "unpack-trees.h"
 #include "progress.h"
 #include "refs.h"
+#include "stat-cache.h"
 
 static void add_entry(struct unpack_trees_options *o, struct cache_entry *ce,
 	unsigned int set, unsigned int clear)
@@ -409,7 +410,7 @@ static int verify_uptodate(struct cache_entry *ce,
 	if (o->index_only || o->reset)
 		return 0;
 
-	if (!lstat(ce->name, &st)) {
+	if (!clstat(ce->name, &st)) {
 		unsigned changed = ie_match_stat(o->src_index, ce, &st, CE_MATCH_IGNORE_VALID);
 		if (!changed)
 			return 0;
@@ -535,7 +536,7 @@ static int verify_absent(struct cache_entry *ce, const char *action,
 	if (has_symlink_leading_path(ce->name, NULL))
 		return 0;
 
-	if (!lstat(ce->name, &st)) {
+	if (!clstat(ce->name, &st)) {
 		int cnt;
 		int dtype = ce_to_dtype(ce);
 
@@ -931,7 +932,7 @@ int oneway_merge(struct cache_entry **src, struct unpack_trees_options *o)
 		int update = 0;
 		if (o->reset) {
 			struct stat st;
-			if (lstat(old->name, &st) ||
+			if (clstat(old->name, &st) ||
 			    ie_match_stat(o->src_index, old, &st, CE_MATCH_IGNORE_VALID))
 				update |= CE_UPDATE;
 		}
diff --git a/xdiff-interface.c b/xdiff-interface.c
index 61dc5c5..7eb4a9e 100644
--- a/xdiff-interface.c
+++ b/xdiff-interface.c
@@ -1,5 +1,6 @@
 #include "cache.h"
 #include "xdiff-interface.h"
+#include "stat-cache.h"
 
 static int parse_num(char **cp_p, int *num_p)
 {
@@ -147,7 +148,7 @@ int read_mmfile(mmfile_t *ptr, const char *filename)
 	FILE *f;
 	size_t sz;
 
-	if (stat(filename, &st))
+	if (cstat(filename, &st))
 		return error("Could not stat %s", filename);
 	if ((f = fopen(filename, "rb")) == NULL)
 		return error("Could not open %s", filename);
-- 
1.5.5.76.gbb45.dirty

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

[Luciano Rocha]

[-- Attachment #1: Type: text/plain, Size: 818 bytes --]

On Sun, Apr 20, 2008 at 12:13:46PM +0100, Luciano Rocha wrote:
> An implementation of stat(2) and lstat(2) caching. Both the return code
> and returned information are cached.
> 
> Signed-off-by: Luciano Rocha <strange@nsk.no-ip.org>
> ---
> On Sat, Apr 19, 2008 at 03:39:37PM -0700, Linus Torvalds wrote:
> > Yeah. I didn't look any further, but we do a total of *nine* 'lstat()' 
> > calls for each file we know about that is dirty, and *seven* when they are 
> > clean. Plus maybe a few more.
> 
> That's a lot. Why not use a stat cache?
> 
> With these changes, my git status . in WebKit changes from 28.215s to
> 15.414s.

git status . in git changes from 0.477s to 0.412s.

All tests under OS X.

-- 
Luciano Rocha <luciano@eurotux.com>
Eurotux Informática, S.A. <http://www.eurotux.com/>

[-- Attachment #2: Type: application/pgp-signature, Size: 189 bytes --]

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

[Linus Torvalds]

On Sun, 20 Apr 2008, Luciano Rocha wrote:
> 
> That's a lot. Why not use a stat cache?

Well, the thing is, the OS _does_ a stat cache for us, and the one that 
the OS maintains is a lot better, in that it works across processes and is 
coherent with other processes changing things.

And the thing is, your stat cache makes the *common* cases slower. I 
didn't do a whole lot of testing, but on my machine, doing just a "git 
status" with and without your stat cache shows

	Current git 'master':
		real    0m0.302s
		real    0m0.308s
		real    0m0.314s

	With your patch:
		real    0m0.352s
		real    0m0.354s
		real    0m0.355s

iow, it slowed down the case that I think matters more (the one you're 
*supposed* to use, and people most commonly do) by 15%.

Now, admittedly, I also do think that we should generally optimize the 
slow cases more than we should care about things that are already very 
fast, so I do not think that it's wrong to say "ok, let's make the really 
fast case a bit slower, in order to not be so slow in the bad case", so in 
that sense I do not think the slowdown is disastrous.

BUT. 

I really dislike adding a cache that is there just because we do something 
stupid. We can fix the over-abundance of lstat() calls by just being 
smarter. And the smarter we are, the less the cache will help, and the 
more it will hurt. Which is the real reason why I think the cache is a 
really really bad idea: it optimizes for the wrong kind of behavior.

So we have other caches and hashes we use, like the index itself, or the 
name lookup hash into the index, or the delta cache. Maintaining those 
caches takes some effort too, but those caches aren't there because we're 
doing something stupid, they are there because they allow us to do 
something smart.

For example, the index itself actually has really important semantic 
characteristics. And while the name hashing actually improves on index 
lookup performance, I'd never have implemented it if it wasn't for the 
fact that it was also designed to allow us to do case-insensitive lookups. 
And the delta cache is not hiding stupidity, it's literally avoiding very 
expensive work that we can't avoid by being smarter.

So the stat cache is not horribly bad, but I think it's the wrong path to 
go down. 

> With these changes, my git status . in WebKit changes from 28.215s to
> 15.414s.

Of course, one reason I don't think it's such a great idea is that on 
Linux, your stat cache doesn't even then end up helping _nearly_ as much 
as it does on OS X. You see an almost 50% improvement, so the 15% 
*deprovement* may not sound like much to you. But under Linux, the numbers 
are quite different:

"git status ." with your patch:

	real    0m1.043s
	real    0m1.009s
	real    0m0.972s

With my trivial patch that just removed 2 of the 9 lstat calls:

	real    0m1.116s
	real    0m1.115s
	real    0m1.119s

IOW, it does help the "." case on Linux, but only by a fairly small 
amount. In fact, the improvement seems slightly smaller than the 
peformance degradation (~12% vs ~15%), but that is probably within the 
margin of noise, so...

So another reason to avoid the stat cache is that it's really just working 
around an OS X deficiency.

I'd rather work at avoiding more lstat calls. I know we can do it.

			Linus

Re: Git performance on OS X

[David Kastrup]

Linus Torvalds <torvalds@linux-foundation.org> writes:

> On Sat, 19 Apr 2008, Linus Torvalds wrote:
>> 
>> Notice how this patch doesn' actually change the fundamental O(n^2) 
>> behaviour, but it makes it much cheaper by generally avoiding the 
>> expensive 'fnmatch' and 'strlen/strncmp' when they are obviously not 
>> needed.
>
> Side note: on the kenrel tree, it makes the (insane!) operation 
>
> 	git add $(git ls-files)
>
> go from 49 seconds down to 17 sec. So it does make a huge difference
> for me, but I also want to point out that this really isn't a sane
> operation to do (I also think that 17 sec is totally unacceptable, but
> I cannot find it in me to care, since I don't think this is an
> operation that anybody should ever do!)

It is my opinion that git should likely presort the patterns (not just
here), and should traverse the trees alphabetically.  In that case, a
merge-like algorithm will pretty much do the trick in O(n), with O(n lg
n) preprocessing cost.

Presorting can only be done approximately in the case of wildcards: for
those, we have two relevant points in the sort order: one where it can
start matching, one where it can't match anymore.

The easiest way to make this more efficient would be to retain the
O(n*m) algorithm, but presort the patterns and let them trickle
head-first into the O(m) pattern list only when they start having a
chance of matching, and remove them from the O(m) list once a non-match
has passed them alphabetically for good.

-- 
David Kastrup, Kriemhildstr. 15, 44793 Bochum

Re: Git performance on OS X

[David Kastrup]

Linus Torvalds <torvalds@linux-foundation.org> writes:

> Taking three seconds for the warm-cache case for just 50,000 files is 
> ludicrous. That's about an order-and-a-half slower than what I see.
>
> Maybe my CPU is faster too (2.66GHz Core 2), but the thing is, Linux 
> really does tend to outperform others at a lot of these kinds of loads. 
> System calls are fast to begin with, and the Linux directory cache kicks 
> ass, if I do say so myself.
>
> OS X doth suck. 

Oh, but OS X does utf8 unification and case folding: so it is actually
doing quite a bit more than Linux.

Of course, doing that sucks for even more reasons, but it is not an
accident.  It is intentional brain damage.

-- 
David Kastrup, Kriemhildstr. 15, 44793 Bochum

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

[Luciano Rocha]

[-- Attachment #1: Type: text/plain, Size: 1932 bytes --]

On Sun, Apr 20, 2008 at 09:03:13AM -0700, Linus Torvalds wrote:
> 
> 
> On Sun, 20 Apr 2008, Luciano Rocha wrote:
> > 
> > That's a lot. Why not use a stat cache?
> 
> Well, the thing is, the OS _does_ a stat cache for us, and the one that 
> the OS maintains is a lot better, in that it works across processes and is 
> coherent with other processes changing things.

Sure. I am even unsure if the cache didn't break any sanity check (did a
file change after ...? Did someone chdir(2)?).

> And the thing is, your stat cache makes the *common* cases slower. I 
> didn't do a whole lot of testing, but on my machine, doing just a "git 
> status" with and without your stat cache shows
<snip>

Well, it can be improved. The memcpy can be avoided by using the stored
data directly, and a _or_die can be added for the common case.

> Now, admittedly, I also do think that we should generally optimize the 
> slow cases more than we should care about things that are already very 
> fast, so I do not think that it's wrong to say "ok, let's make the really 
> fast case a bit slower, in order to not be so slow in the bad case", so in 
> that sense I do not think the slowdown is disastrous.
> 
> BUT. 
> 
> I really dislike adding a cache that is there just because we do something 
> stupid. We can fix the over-abundance of lstat() calls by just being 
> smarter. And the smarter we are, the less the cache will help, and the 
> more it will hurt. Which is the real reason why I think the cache is a 
> really really bad idea: it optimizes for the wrong kind of behavior.

I agree completly. If we can reduce the number of (l)stat calls to a
single one per file, then we'll all be happier. But that kind of change
is beyond my current understanding of git internals. ;)

Regards,
Luciano Rocha

-- 
Luciano Rocha <luciano@eurotux.com>
Eurotux Informática, S.A. <http://www.eurotux.com/>

[-- Attachment #2: Type: application/pgp-signature, Size: 189 bytes --]

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

[Linus Torvalds]

On Sun, 20 Apr 2008, Luciano Rocha wrote:
> 
> Well, it can be improved. The memcpy can be avoided by using the stored
> data directly, and a _or_die can be added for the common case.

Agreed. I think a big part of the overhead is also the allocation cost, 
and that can probably be obliterated (or at least minimized) by using a 
special and much faster allocator (see "alloc.c") since none of the 
allocations will ever be free'd.

The one thing I liked about your patch was that I think we could be better 
off with wrapping "lstat()" for other reasons - the same way we wrap 
read/write calls in our own "write_in_full()" simplified library 
functions. I hate tracing them, for example, and a wrapper around lstat() 
would have helped my efforts to avoid some of the unnecessary ones.

So I do think your stat cache could be improved, but for the reasons I 
outlined I would much prefer to make it unimportant instead.

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).

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

[Linus Torvalds]

On Sun, 20 Apr 2008, Linus Torvalds wrote:
> 
> 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

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

[Dmitry Potapov]

On Sun, Apr 20, 2008 at 04:07:35PM -0700, Linus Torvalds wrote:
>
> Junio, what was the logic for that whole "has_symlink_leading_path()"
> thing? I forget. Whatever, it's broken.

===
commit f859c846e90b385c7ef873df22403529208ade50
Author: Junio C Hamano <junkio@cox.net>
Date:   Fri May 11 22:11:07 2007 -0700

    Add has_symlink_leading_path() function.

    When we are applying a patch that creates a blob at a path, or
    when we are switching from a branch that does not have a blob at
    the path to another branch that has one, we need to make sure
    that there is nothing at the path in the working tree, as such a
    file is a local modification made by the user that would be lost
    by the operation.

    Normally, lstat() on the path and making sure ENOENT is returned
    is good enough for that purpose.  However there is a twist.  We
    may be creating a regular file arch/x86_64/boot/Makefile, while
    removing an existing symbolic link at arch/x86_64/boot that
    points at existing ../i386/boot directory that has Makefile in
    it.  We always first check without touching filesystem and then
    perform the actual operation, so when we verify the new file,
    arch/x86_64/boot/Makefile, does not exist, we haven't removed
    the symbolic link arc/x86_64/boot symbolic link yet.  lstat() on
    the file sees through the symbolic link and reports the file is
    there, which is not what we want.

    The function has_symlink_leading_path() function takes a path,
    and sees if any of the leading directory component is a symbolic
    link.

    When files in a new directory are created, we tend to process
    them together because both index and tree are sorted.  The
    function takes advantage of this and allows the caller to cache
    and reuse which symbolic link on the filesystem caused the
    function to return true.

    The calling sequence would be:

        char last_symlink[PATH_MAX];

            *last_symlink = '\0';
            for each index entry {
                if (!lose)
                        continue;
                if (lstat(it))
                        if (errno == ENOENT)
                                ; /* happy */
                        else
                                error;
                else if (has_symlink_leading_path(it, last_symlink))
                        ; /* happy */
                else
                        error; /* would lose local changes */
                unlink_entry(it, last_symlink);
        }
===

And there are some cases where stat() on path is desirable:
http://www.spinics.net/lists/git/msg63988.html

So while stat information for regular files is cached in the index,
stat information for directories is not cached, and that appears to
be wrong. Maybe, Lucano's cache makes sense if it stores only stat
information for directories.

IIRC, some time ago, an otherwise reasonable patch for .gitignore was
rejected just because it would drive the number calls to lstat() up as
these calls on directories are not cached in the index.

Dmitry

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

[Junio C Hamano]

Linus Torvalds <torvalds@linux-foundation.org> writes:

> Junio, what was the logic for that whole "has_symlink_leading_path()" 
> thing?

If you have a tracked path a/b/c/d/e, and you changed your work tree to
make a/b to a symlink that points at a random directory, potentially
even outside work tree, that has c/d/e in it, we should not be fooled by
the fact that lstat("a/b/c/d/e") says "yup, the file exists".  As far as
git is concerned, that path does _not_ exist, as "a/b" is a symlink now.

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

[Linus Torvalds]

On Sun, 20 Apr 2008, Junio C Hamano wrote:
> Linus Torvalds <torvalds@linux-foundation.org> writes:
> 
> > Junio, what was the logic for that whole "has_symlink_leading_path()" 
> > thing?
> 
> If you have a tracked path a/b/c/d/e, and you changed your work tree to
> make a/b to a symlink that points at a random directory, potentially
> even outside work tree, that has c/d/e in it, we should not be fooled by
> the fact that lstat("a/b/c/d/e") says "yup, the file exists".  As far as
> git is concerned, that path does _not_ exist, as "a/b" is a symlink now.

Ok, I can see the logic behind that, but the code is really dense and hard 
to read. And obviously very inefficient.

Here's a trial balloon patch that totally revamps how that whole function 
works. Instead of passing in a "symlink_cache" thing that it modifies for 
the caller, it just has its totally *internal* cache of where it found the 
last symlink, and what the last directory it found last time was.

So now the logic becomes:

 - if a pathname that is passed in matches the last known symlink prefix, 
   we don't even need to do anything else - it is known to have a symlink 
   prefix.

 - if the pathname that is passed in matches the last known directory 
   prefix, we start looking just from that point onward (since we know 
   that the leading part is a directory without symlinks)

and this not only speeds things up regardless, it also cuts down lstat() 
calls by a huge amount.

On that WebKit repo, and a "git status .", it used to do 338132 lstat() 
calls. With this patch, it only does 141411. Which is still three per 
pathname we know about, plus roughly one per directory we look at, but 
that's a *lot* better.

It also improves performance from 1.125s to under one second for me on 
Linux. 

But more fundamentally, I think it's more readable.

Caveat: I do think we should add a way to invalidate the pathname caches 
when we turn a symlink into a directory or vice versa, so this patch isn't 
really complete as-is, but I think it's a good start.

And once we do that, I think the code is actually understandable. It was 
really hard to see what the point of that "last_symlink" thing was.

Hmm?

		Linus
---
 builtin-apply.c |    2 +-
 cache.h         |    2 +-
 diff-lib.c      |   10 +++---
 symlinks.c      |   78 +++++++++++++++++++++++++++++++++----------------------
 unpack-trees.c  |   12 +++-----
 5 files changed, 59 insertions(+), 45 deletions(-)

diff --git a/builtin-apply.c b/builtin-apply.c
index caa3f2a..1103625 100644
--- a/builtin-apply.c
+++ b/builtin-apply.c
@@ -2247,7 +2247,7 @@ static int check_to_create_blob(const char *new_name, int ok_if_exists)
 		 * In such a case, path "new_name" does not exist as
 		 * far as git is concerned.
 		 */
-		if (has_symlink_leading_path(new_name, NULL))
+		if (has_symlink_leading_path(strlen(new_name), new_name))
 			return 0;
 
 		return error("%s: already exists in working directory", new_name);
diff --git a/cache.h b/cache.h
index c058125..6dc6543 100644
--- a/cache.h
+++ b/cache.h
@@ -587,7 +587,7 @@ struct checkout {
 };
 
 extern int checkout_entry(struct cache_entry *ce, const struct checkout *state, char *topath);
-extern int has_symlink_leading_path(const char *name, char *last_symlink);
+extern int has_symlink_leading_path(int len, const char *name);
 
 extern struct alternate_object_database {
 	struct alternate_object_database *next;
diff --git a/diff-lib.c b/diff-lib.c
index 069e450..6a26b53 100644
--- a/diff-lib.c
+++ b/diff-lib.c
@@ -338,14 +338,14 @@ int run_diff_files_cmd(struct rev_info *revs, int argc, const char **argv)
  * See if work tree has an entity that can be staged.  Return 0 if so,
  * return 1 if not and return -1 if error.
  */
-static int check_work_tree_entity(const struct cache_entry *ce, struct stat *st, char *symcache)
+static int check_work_tree_entity(const struct cache_entry *ce, struct stat *st)
 {
 	if (lstat(ce->name, st) < 0) {
 		if (errno != ENOENT && errno != ENOTDIR)
 			return -1;
 		return 1;
 	}
-	if (has_symlink_leading_path(ce->name, symcache))
+	if (has_symlink_leading_path(ce_namelen(ce), ce->name))
 		return 1;
 	if (S_ISDIR(st->st_mode)) {
 		unsigned char sub[20];
@@ -399,7 +399,7 @@ int run_diff_files(struct rev_info *revs, unsigned int option)
 			memset(&(dpath->parent[0]), 0,
 			       sizeof(struct combine_diff_parent)*5);
 
-			changed = check_work_tree_entity(ce, &st, symcache);
+			changed = check_work_tree_entity(ce, &st);
 			if (!changed)
 				dpath->mode = ce_mode_from_stat(ce, st.st_mode);
 			else {
@@ -463,7 +463,7 @@ int run_diff_files(struct rev_info *revs, unsigned int option)
 		if (ce_uptodate(ce))
 			continue;
 
-		changed = check_work_tree_entity(ce, &st, symcache);
+		changed = check_work_tree_entity(ce, &st);
 		if (changed) {
 			if (changed < 0) {
 				perror(ce->name);
@@ -521,7 +521,7 @@ static int get_stat_data(struct cache_entry *ce,
 	if (!cached) {
 		int changed;
 		struct stat st;
-		changed = check_work_tree_entity(ce, &st, cbdata->symcache);
+		changed = check_work_tree_entity(ce, &st);
 		if (changed < 0)
 			return -1;
 		else if (changed) {
diff --git a/symlinks.c b/symlinks.c
index be9ace6..04ce2d4 100644
--- a/symlinks.c
+++ b/symlinks.c
@@ -1,48 +1,64 @@
 #include "cache.h"
 
-int has_symlink_leading_path(const char *name, char *last_symlink)
-{
+struct pathname {
+	int len;
 	char path[PATH_MAX];
-	const char *sp, *ep;
-	char *dp;
+};
 
-	sp = name;
-	dp = path;
+/* Return matching pathname prefix length, or zero if not matching */
+static inline int match_pathname(int len, const char *name, struct pathname *match)
+{
+	int match_len = match->len;
+	return (len > match_len &&
+		name[match_len] == '/' &&
+		!memcmp(name, match->path, match_len)) ? match_len : 0;
+}
 
-	if (last_symlink && *last_symlink) {
-		size_t last_len = strlen(last_symlink);
-		size_t len = strlen(name);
-		if (last_len < len &&
-		    !strncmp(name, last_symlink, last_len) &&
-		    name[last_len] == '/')
-			return 1;
-		*last_symlink = '\0';
+static inline void set_pathname(int len, const char *name, struct pathname *match)
+{
+	if (len < PATH_MAX) {
+		match->len = len;
+		memcpy(match->path, name, len);
+		match->path[len] = 0;
 	}
+}
 
-	while (1) {
-		size_t len;
-		struct stat st;
+int has_symlink_leading_path(int len, const char *name)
+{
+	static struct pathname link, nonlink;
+	char path[PATH_MAX];
+	struct stat st;
+	char *sp;
+	int known_dir;
+
+	/*
+	 * See if the last known symlink cache matches.
+	 */
+	if (match_pathname(len, name, &link))
+		return 1;
 
-		ep = strchr(sp, '/');
-		if (!ep)
-			break;
-		len = ep - sp;
-		if (PATH_MAX <= dp + len - path + 2)
-			return 0; /* new name is longer than that??? */
-		memcpy(dp, sp, len);
-		dp[len] = 0;
+	/*
+	 * Get rid of the last known directory part
+	 */
+	known_dir = match_pathname(len, name, &nonlink);
+	    	
+	while ((sp = strchr(name + known_dir + 1, '/')) != NULL) {
+		int thislen = sp - name ;
+		memcpy(path, name, thislen);
+		path[thislen] = 0;
 
 		if (lstat(path, &st))
 			return 0;
+		if (S_ISDIR(st.st_mode)) {
+			set_pathname(thislen, path, &nonlink);
+			known_dir = thislen;
+			continue;
+		}
 		if (S_ISLNK(st.st_mode)) {
-			if (last_symlink)
-				strcpy(last_symlink, path);
+			set_pathname(thislen, path, &link);
 			return 1;
 		}
-
-		dp[len++] = '/';
-		dp = dp + len;
-		sp = ep + 1;
+		break;
 	}
 	return 0;
 }
diff --git a/unpack-trees.c b/unpack-trees.c
index feae846..1ab28fd 100644
--- a/unpack-trees.c
+++ b/unpack-trees.c
@@ -26,11 +26,12 @@ static void add_entry(struct unpack_trees_options *o, struct cache_entry *ce,
  * directories, in case this unlink is the removal of the
  * last entry in the directory -- empty directories are removed.
  */
-static void unlink_entry(char *name, char *last_symlink)
+static void unlink_entry(struct cache_entry *ce)
 {
 	char *cp, *prev;
+	char *name = ce->name;
 
-	if (has_symlink_leading_path(name, last_symlink))
+	if (has_symlink_leading_path(ce_namelen(ce), ce->name))
 		return;
 	if (unlink(name))
 		return;
@@ -58,7 +59,6 @@ static int check_updates(struct unpack_trees_options *o)
 {
 	unsigned cnt = 0, total = 0;
 	struct progress *progress = NULL;
-	char last_symlink[PATH_MAX];
 	struct index_state *index = &o->result;
 	int i;
 	int errs = 0;
@@ -75,14 +75,13 @@ static int check_updates(struct unpack_trees_options *o)
 		cnt = 0;
 	}
 
-	*last_symlink = '\0';
 	for (i = 0; i < index->cache_nr; i++) {
 		struct cache_entry *ce = index->cache[i];
 
 		if (ce->ce_flags & CE_REMOVE) {
 			display_progress(progress, ++cnt);
 			if (o->update)
-				unlink_entry(ce->name, last_symlink);
+				unlink_entry(ce);
 			remove_index_entry_at(&o->result, i);
 			i--;
 			continue;
@@ -97,7 +96,6 @@ static int check_updates(struct unpack_trees_options *o)
 			ce->ce_flags &= ~CE_UPDATE;
 			if (o->update) {
 				errs |= checkout_entry(ce, &state, NULL);
-				*last_symlink = '\0';
 			}
 		}
 	}
@@ -553,7 +551,7 @@ static int verify_absent(struct cache_entry *ce, const char *action,
 	if (o->index_only || o->reset || !o->update)
 		return 0;
 
-	if (has_symlink_leading_path(ce->name, NULL))
+	if (has_symlink_leading_path(ce_namelen(ce), ce->name))
 		return 0;
 
 	if (!lstat(ce->name, &st)) {

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

[Linus Torvalds]

On Sun, 20 Apr 2008, Linus Torvalds wrote:
> On Sun, 20 Apr 2008, Junio C Hamano wrote:
> > 
> > If you have a tracked path a/b/c/d/e, and you changed your work tree to
> > make a/b to a symlink that points at a random directory, potentially
> > even outside work tree, that has c/d/e in it, we should not be fooled by
> > the fact that lstat("a/b/c/d/e") says "yup, the file exists".  As far as
> > git is concerned, that path does _not_ exist, as "a/b" is a symlink now.
> 
> Ok, I can see the logic behind that, but the code is really dense and hard 
> to read. And obviously very inefficient.

One more note: I think that if we really care about this, we should do 
this inside "ce_match_stat()", so that we catch it in *all* the cases 
where we match against the stat information. 

As it is, the "diff" mechanism (and "apply") knows to check whether a 
directory has changed into a symlink, but it looks like doing a simple 
"git update-index --refresh" will never even test it, so it will never 
notice that the index isn't actually up-to-date if a directory has been 
moved and the old directory has been replaced by a symlink to the new 
location.

Hmm?

		Linus

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

[Johan Herland]

On Monday 21 April 2008, Dmitry Potapov wrote:
> On Sun, Apr 20, 2008 at 04:07:35PM -0700, Linus Torvalds wrote:
> > Junio, what was the logic for that whole "has_symlink_leading_path()"
> > thing? I forget. Whatever, it's broken.
> 
> ===
> commit f859c846e90b385c7ef873df22403529208ade50
> Author: Junio C Hamano <junkio@cox.net>
> Date:   Fri May 11 22:11:07 2007 -0700
> 
[snip snip]
> ===
> 
> And there are some cases where stat() on path is desirable:
> http://www.spinics.net/lists/git/msg63988.html
> 
> So while stat information for regular files is cached in the index,
> stat information for directories is not cached, and that appears to
> be wrong. Maybe, Lucano's cache makes sense if it stores only stat
> information for directories.
> 
> IIRC, some time ago, an otherwise reasonable patch for .gitignore was
> rejected just because it would drive the number calls to lstat() up as
> these calls on directories are not cached in the index.

Pardon me for butting in (and I'm honestly NOT trying to start a flamewar),
but I'm wondering if this could be solved by tracking directories in the
index. AFAICS it would:

- Help bring the number of lstat() calls down (since we can cache the
  lstat() results for directories like we currently do for regular files)

- More easily detect complicated cases like "add across symlinks" (see
  Junio's email at the spinics.net link above)

- (less important) When discussing empty directory support several months
  ago, ISTR one of the biggest hurdles being that directories were not
  tracked in the index


I don't know much about how the index is implemented (few do, I think), so
if there is a glaringly obvious reason why tracking directories in the
index is a bad idea, please enlighten me.


...Johan

-- 
Johan Herland, <johan@herland.net>
www.herland.net

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

[David Kastrup]

Linus Torvalds <torvalds@linux-foundation.org> writes:

> So I do think your stat cache could be improved, but for the reasons I
> outlined I would much prefer to make it unimportant instead.

Using a cache for a single algorithmic task is probably a mistake: a
cache tries to keep some data around on the assumption that it might get
used.  So it tends to either waste lots of memory or keep the wrong
data.  And the reloads increase with the size of the processed data.

Using a sorted-traverse-and-merge algorithm instead never needs to
reload data and relinquishes it as soon as it is no longer needed.

A stat cache is fine for an operating system which has no clue about
what access patterns to except next.

But in this case, our application has the whole task outlines in
advance, and it makes sense organizing it in the best manner.

-- 
David Kastrup, Kriemhildstr. 15, 44793 Bochum

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

[Junio C Hamano]

Linus Torvalds <torvalds@linux-foundation.org> writes:

> Here's a trial balloon patch that totally revamps how that whole function 
> works. Instead of passing in a "symlink_cache" thing that it modifies for 
> the caller, it just has its totally *internal* cache of where it found the 
> last symlink, and what the last directory it found last time was.
>
> So now the logic becomes:
>
>  - if a pathname that is passed in matches the last known symlink prefix, 
>    we don't even need to do anything else - it is known to have a symlink 
>    prefix.
>
>  - if the pathname that is passed in matches the last known directory 
>    prefix, we start looking just from that point onward (since we know 
>    that the leading part is a directory without symlinks)

That makes sense.

> Caveat: I do think we should add a way to invalidate the pathname caches 
> when we turn a symlink into a directory or vice versa, so this patch isn't 
> really complete as-is, but I think it's a good start.

True.

There are a few patches in flight that are not in 'master' (Dmitry quoted
one of them), that use more has_symlink_leading_path() calls.  In
retrospect, the function was misnamed.  It describes what it checks
(i.e. "does the path have leading component that is a symlink?") but I
probably should have named it after what it really wants to tell
(i.e. "lstat(2) says this exists, but does it really, from the point of
view of git?")

Doesn't it become very tempting to replace lstat() calls we make to check
the status of a work tree path, with a function git_wtstat() that is:

        int git_wtstat(const char *path, struct stat *st)
        {
                int status = lstat(path, st);

                if (status)
                        return status;

                if (!has_symlink_leading_path(path, strlen(path)))
                        return 0;

                /*
                 * As far as git is concerned, this does not exist in
                 * the work tree!
                 */
                errno = ENOENT;
                return -1;
        }

This unfortunately is not enough to hide the need for has_symlink calls
from outside callers.  When we check out a new path "a/b/c/d/e", for
example, if we naively checked if we creat(2) "a/b/c/d/e" (and otherwise
we try the equivalent of "mkdir -p"), we would be tricked by a symlink
"a/b" that points at some random place that has "c/d" subdirectory in it,
and we need to unlink "a/b" first, and the above git_wtstat() does not
really help such codepath.

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

[Linus Torvalds]

On Mon, 21 Apr 2008, Junio C Hamano wrote:
> 
> Doesn't it become very tempting to replace lstat() calls we make to check
> the status of a work tree path, with a function git_wtstat() that is:

Yes.

That looks like a very good abstraction.

>                 /*
>                  * As far as git is concerned, this does not exist in
>                  * the work tree!
>                  */
>                 errno = ENOENT;
>                 return -1;
>         }

Well, how about returning something else than "ENOENT" here? 

As you point out, git doesn't actually think this is a "does not exist" 
case, but something else that may require more work:

> This unfortunately is not enough to hide the need for has_symlink calls
> from outside callers.  When we check out a new path "a/b/c/d/e", for
> example, if we naively checked if we creat(2) "a/b/c/d/e" (and otherwise
> we try the equivalent of "mkdir -p"), we would be tricked by a symlink
> "a/b" that points at some random place that has "c/d" subdirectory in it,
> and we need to unlink "a/b" first, and the above git_wtstat() does not
> really help such codepath.

Maybe ENOTDIR would be a better error return? That would conceptually be 
what an OS that refuses to follow symlinks at path walk time (because it 
doesn't support symlinks as such) would return: the symlink component 
would not be a directory, so it's as if you were trying to use a path 
a/b/c/d/e where "a/b" isn't even a directory.

In fact, even on Linux, ENOTDIR is what an lstat() would return if "b" had 
been turned from a directory into a regular file - which is conceptually 
(for git) _exactly_ the same as "b" being a symlink.

No?

			Linus

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

[Junio C Hamano]

Linus Torvalds <torvalds@linux-foundation.org> writes:

> On Mon, 21 Apr 2008, Junio C Hamano wrote:
>> 
>> Doesn't it become very tempting to replace lstat() calls we make to check
>> the status of a work tree path, with a function git_wtstat() that is:
>
> Yes.
>
> That looks like a very good abstraction.
>
>>                 /*
>>                  * As far as git is concerned, this does not exist in
>>                  * the work tree!
>>                  */
>>                 errno = ENOENT;
>>                 return -1;
>>         }
>
> Well, how about returning something else than "ENOENT" here? 
>
> As you point out, git doesn't actually think this is a "does not exist" 
> case, but something else that may require more work:
>
>> This unfortunately is not enough to hide the need for has_symlink calls
>> from outside callers.  When we check out a new path "a/b/c/d/e", for
>> example, if we naively checked if we creat(2) "a/b/c/d/e" (and otherwise
>> we try the equivalent of "mkdir -p"), we would be tricked by a symlink
>> "a/b" that points at some random place that has "c/d" subdirectory in it,
>> and we need to unlink "a/b" first, and the above git_wtstat() does not
>> really help such codepath.
>
> Maybe ENOTDIR would be a better error return?

Yeah, and we could return which component in the given path is the
offending one at the same time.

In the above example, we would say "No, a/b/c/d/e does not exist because
a/b is a symlink".  But would that be enough, I have to wonder.  lstat(2)
may have already said "There is no a/b/c/d/f" in the same example, but we
still need to know "a/b" is an unwanted symbolic link if the reason we are
asking that question is because we would want to check out "a/b/c/d/f".

So the answer need to be "a/b/c/d/f" (does not exist|exists in the work
tree), and it cannot exist because "a/b" is a symlink for such a caller.

But when we are trying to git-add, we simply do not care such
distinction.