Too many 'stat' calls by git-status on Windows

Too many 'stat' calls by git-status on Windows

[Dmitry Potapov]

I have used the Cygwin version of Git on one Windows computer and
noticed that git-status is sluggish. So, I have run the Process Monitor
to see what is going on.

The below, you can see the result of testing on Windows and Linux on the
same repository using the same version of Git. It is rather easy to
compare if you notice that the following match between syscalls:

Windows         Linux

QueryOpen       lstat or fstat
CreateFile      open
CloseFile       close
QueryDirectory  getdents

I have also tested git-diff to verify that the number of system calls
matches pretty well. (In fact, I got practical identical list for stat
syscalls for files inside of the working directory on Windows and Linux
when ran git-diff.) But something strange is going on with git-status.
The beginning of the log is identical on Windows and Linux, but then I
see more 'stat's in the Windows log that did not happen on Linux.  In
total, I see about 3 times increase of 'stat' calls, with all files
being stat twice and directories (which are numerous) being stat 3 and
more times (some of them as many 39 times...) It seems that every
directory is stat as many times as the number of subdirectories it has
plus 3.

It appears that the second 'stat' for files on Windows caused by lack
of d_type in dirent. When I recompiled the Linux version with
NO_D_TYPE_IN_DIRENT = YesPlease, I got the same result for files.
(Still I am not sure what caused those extra stat calls for
directory, maybe, it is Cygwin specific...)

The question is whether it is possible to avoid this redundant 'stat'
for files on system that do not have d_type in dirent or that would
require too much modification? Is it possible to use the cache where
d_stat is not available provided that the entry is marked as uptodate?


==== Git on Windows (CYGWIN) =====

$ wc -l git-diff.csv  git-status.csv
   5186 git-diff.csv
  21694 git-status.csv

$ csvtool col 5 git-diff.csv | sort | uniq -c | sort -nr | head -10
   4656 QueryOpen
    100 CreateFile
     94 CloseFile
     80 QuerySecurityFile
     61 ReadFile
     30 QueryInformationVolume
     28 QueryAllInformationFile
     26 RegOpenKey
     24 RegCloseKey
     20 QueryStandardInformationFile

$ csvtool col 5 git-status.csv | sort | uniq -c | sort -nr | head -10
  12984 QueryOpen
   3086 CreateFile
   2103 CloseFile
   1984 QueryDirectory
    988 QueryFileInternalInformationFile
    132 QuerySecurityFile
    100 ReadFile
     77 WriteFile
     55 QueryInformationVolume
     53 QueryAllInformationFile

Successful open:
$ csvtool col 5,7,8 git-diff.csv | grep CreateFile,SUCCESS, | wc -l
94
$ csvtool col 5,7,8 git-status.csv | grep CreateFile,SUCCESS, | wc -l
2103

Successful open for directories:
$ csvtool col 5,7,8 git-diff.csv | grep CreateFile,SUCCESS,.*Options:.*Directory | wc -l
37
$ csvtool col 5,7,8 git-status.csv | grep CreateFile,SUCCESS,.*Options:.*Directory | wc -l
1024

Not successful attempts to open
$ csvtool col 5,7,8 git-diff.csv | grep CreateFile | grep -v ,SUCCESS, | wc -l
6
$ csvtool col 5,7,8 git-status.csv | grep CreateFile | grep -v ,SUCCESS, | wc -l
983

Attempts to open .gitignore
$ csvtool col 5,6 git-diff.csv | grep 'CreateFile,.*\\\.gitignore' | wc -l
0
$ csvtool col 5,6 git-status.csv | grep 'CreateFile,.*\\\.gitignore' | wc -l
986

=== GIT on Linux ===

$ wc -l linux-git-*
   4674 linux-git-diff.log
   9807 linux-git-status.log

$ sed -e 's/(.*//' < linux-git-diff.log  | sort | uniq -c | sort -rn | head -10
   4237 lstat
     88 mmap
     56 open
     50 close
     50 access
     48 fstat
     45 mprotect
     43 read
     15 stat
     13 munmap

The number of lstat+fstat is equal 4285 for git-diff

$ sed -e 's/(.*//' < linux-git-status.log  | sort | uniq -c | sort -rn | head -10
   3279 lstat
   2048 open
   1976 getdents
   1062 close
   1058 fstat
     97 mmap
     67 read
     48 access
     45 mprotect
     40 write

The number of lstat+fstat is equal 4337 for git-status.

Successful open:
$ grep -c '^open(.*= [^-]' linux-*
linux-git-diff.log:50
linux-git-status.log:1064

Successful open for directories:
$ grep -c '^open(.*O_DIRECTORY.*= [^-]' linux-*
linux-git-diff.log:1
linux-git-status.log:989

Not successful attempts to open:
$ grep -c '^open(.*= -1' linux-*
linux-git-diff.log:6
linux-git-status.log:984

Attempts to open .gitignore:
$ grep -c '^open(.*.\.gitignore"' linux-*
linux-git-diff.log:0
linux-git-status.log:987

=== Linux with NO_D_TYPE_IN_DIRENT = YesPlease ===

$ wc -l linux-git-*no-dtype.log
   4674 linux-git-diff-no-dtype.log
  14040 linux-git-status-no-dtype.log

$ sed -e 's/(.*//' < linux-git-diff-no-dtype.log  | sort | uniq -c | sort -rn | head -10

   4237 lstat
     88 mmap
     56 open
     50 close
     50 access
     48 fstat
     45 mprotect
     43 read
     15 stat
     13 munmap

The number of lstat+fstat is equal 4285 for git-diff

$ sed -e 's/(.*//' < linux-git-status-no-dtype.log  | sort | uniq -c | sort -rn | head -10

   7512 lstat
   2048 open
   1976 getdents
   1062 close
   1058 fstat
     97 mmap
     67 read
     48 access
     45 mprotect
     40 write

The number of lstat+fstat is equal 8570 for git-status.

Successful open:
$ grep -c '^open(.*= [^-]' linux-*-no-dtype.log
linux-git-diff-no-dtype.log:50
linux-git-status-no-dtype.log:1064

Successful open for directories:
$ grep -c '^open(.*O_DIRECTORY.*= [^-]' linux-*-no-dtype.log
linux-git-diff-no-dtype.log:1
linux-git-status-no-dtype.log:989

Not successful attempts to open:
$ grep -c '^open(.*= -1' linux-*-no-dtype.log
linux-git-diff-no-dtype.log:6
linux-git-status-no-dtype.log:984

Attempts to open .gitignore:
$ grep -c '^open(.*.\.gitignore"' linux-*-no-dtype.log
linux-git-diff-no-dtype.log:0
linux-git-status-no-dtype.log:987

=======

Dmitry

Re: Too many 'stat' calls by git-status on Windows

[Ramsay Jones]

Dmitry Potapov wrote:
[snip]
> It appears that the second 'stat' for files on Windows caused by lack
> of d_type in dirent. When I recompiled the Linux version with
> NO_D_TYPE_IN_DIRENT = YesPlease, I got the same result for files.

I believe that the next version of cygwin, currently in beta, will have
the d_type field in dirent.  I know that's not much help now...
(I don't think it would be a good idea to try and reto-fit d_type,
ala compat/mingw.[ch], since cygwin does some funky stuff behind the
scenes).

Nice profiling BTW.

ATB,
Ramsay Jones

Re: Too many 'stat' calls by git-status on Windows

[Linus Torvalds]

On Tue, 7 Jul 2009, Dmitry Potapov wrote:
> 
> It appears that the second 'stat' for files on Windows caused by lack
> of d_type in dirent. When I recompiled the Linux version with
> NO_D_TYPE_IN_DIRENT = YesPlease, I got the same result for files.
> (Still I am not sure what caused those extra stat calls for
> directory, maybe, it is Cygwin specific...)
> 
> The question is whether it is possible to avoid this redundant 'stat'
> for files on system that do not have d_type in dirent or that would
> require too much modification? Is it possible to use the cache where
> d_stat is not available provided that the entry is marked as uptodate?

Hmm. Sure. Something like this?

		Linus

---
 dir.c |   14 +++++++++-----
 1 files changed, 9 insertions(+), 5 deletions(-)

diff --git a/dir.c b/dir.c
index 74b3bbf..aaf269b 100644
--- a/dir.c
+++ b/dir.c
@@ -17,7 +17,7 @@ struct path_simplify {
 static int read_directory_recursive(struct dir_struct *dir,
 	const char *path, const char *base, int baselen,
 	int check_only, const struct path_simplify *simplify);
-static int get_dtype(struct dirent *de, const char *path);
+static int get_dtype(struct dirent *de, const char *path, int pathlen);
 
 int common_prefix(const char **pathspec)
 {
@@ -307,7 +307,7 @@ static int excluded_1(const char *pathname,
 
 			if (x->flags & EXC_FLAG_MUSTBEDIR) {
 				if (*dtype == DT_UNKNOWN)
-					*dtype = get_dtype(NULL, pathname);
+					*dtype = get_dtype(NULL, pathname, pathlen);
 				if (*dtype != DT_DIR)
 					continue;
 			}
@@ -547,14 +547,18 @@ static int in_pathspec(const char *path, int len, const struct path_simplify *si
 	return 0;
 }
 
-static int get_dtype(struct dirent *de, const char *path)
+static int get_dtype(struct dirent *de, const char *path, int pathlen)
 {
 	int dtype = de ? DTYPE(de) : DT_UNKNOWN;
+	struct cache_entry *ce;
 	struct stat st;
 
 	if (dtype != DT_UNKNOWN)
 		return dtype;
-	if (lstat(path, &st))
+	ce = cache_name_exists(path, pathlen, 0);
+	if (ce && ce_uptodate(ce))
+		st.st_mode = ce->ce_mode;
+	else if (lstat(path, &st))
 		return dtype;
 	if (S_ISREG(st.st_mode))
 		return DT_REG;
@@ -613,7 +617,7 @@ static int read_directory_recursive(struct dir_struct *dir, const char *path, co
 				continue;
 
 			if (dtype == DT_UNKNOWN)
-				dtype = get_dtype(de, fullname);
+				dtype = get_dtype(de, fullname, baselen + len);
 
 			/*
 			 * Do we want to see just the ignored files?

Re: Too many 'stat' calls by git-status on Windows

[Linus Torvalds]

On Wed, 8 Jul 2009, Linus Torvalds wrote:
> 
> Hmm. Sure. Something like this?

Ok, so having done some testing on it, it seems to work.

And we might as well clean up some of dir.c at the same time. I'll reply 
to this email with a series of three patches: two cleanup ones, and then a 
new version of this one (I hated how it looked to have those duplicated 
"baselen+len" things in read_directory_recursive()).

		Linus

[PATCH 1/3] Add 'fill_directory()' helper function for directory traversal

[Linus Torvalds]

From: Linus Torvalds <torvalds@linux-foundation.org>
Date: Thu, 14 May 2009 13:22:36 -0700
Subject: [PATCH 1/3] Add 'fill_directory()' helper function for directory traversal

Most of the users of "read_directory()" actually want a much simpler
interface than the whole complex (but rather powerful) one.

In fact 'git add' had already largely abstracted out the core interface
issues into a private "fill_directory()" function that was largely
applicable almost as-is to a number of callers.  Yes, 'git add' wants to
do some extra work of its own, specific to the add semantics, but we can
easily split that out, and use the core as a generic function.

This function does exactly that, and now that much simplified
'fill_directory()' function can be shared with a number of callers,
while also ensuring that the rather more complex calling conventions of
read_directory() are used by fewer call-sites.

This also makes the 'common_prefix()' helper function private to dir.c,
since all callers are now in that file.

Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
---

This is a cleaned-up version of a patch that I had done earlier for the 
pathname character set conversion series. It's basically a cleanup of 
b99acc690de27aaf437676c9e3077493a885b642 in 'pu'.

 builtin-add.c      |   45 ++++++++++++++-------------------------------
 builtin-clean.c    |   12 +-----------
 builtin-ls-files.c |    7 +------
 dir.c              |   23 ++++++++++++++++++++++-
 dir.h              |    3 +--
 wt-status.c        |    2 +-
 6 files changed, 40 insertions(+), 52 deletions(-)

diff --git a/builtin-add.c b/builtin-add.c
index 78989da..581a2a1 100644
--- a/builtin-add.c
+++ b/builtin-add.c
@@ -97,35 +97,6 @@ static void treat_gitlinks(const char **pathspec)
 	}
 }
 
-static void fill_directory(struct dir_struct *dir, const char **pathspec,
-		int ignored_too)
-{
-	const char *path, *base;
-	int baselen;
-
-	/* Set up the default git porcelain excludes */
-	memset(dir, 0, sizeof(*dir));
-	if (!ignored_too) {
-		dir->flags |= DIR_COLLECT_IGNORED;
-		setup_standard_excludes(dir);
-	}
-
-	/*
-	 * Calculate common prefix for the pathspec, and
-	 * use that to optimize the directory walk
-	 */
-	baselen = common_prefix(pathspec);
-	path = ".";
-	base = "";
-	if (baselen)
-		path = base = xmemdupz(*pathspec, baselen);
-
-	/* Read the directory and prune it */
-	read_directory(dir, path, base, baselen, pathspec);
-	if (pathspec)
-		prune_directory(dir, pathspec, baselen);
-}
-
 static void refresh(int verbose, const char **pathspec)
 {
 	char *seen;
@@ -343,9 +314,21 @@ int cmd_add(int argc, const char **argv, const char *prefix)
 		die("index file corrupt");
 	treat_gitlinks(pathspec);
 
-	if (add_new_files)
+	if (add_new_files) {
+		int baselen;
+
+		/* Set up the default git porcelain excludes */
+		memset(&dir, 0, sizeof(dir));
+		if (!ignored_too) {
+			dir.flags |= DIR_COLLECT_IGNORED;
+			setup_standard_excludes(&dir);
+		}
+
 		/* This picks up the paths that are not tracked */
-		fill_directory(&dir, pathspec, ignored_too);
+		baselen = fill_directory(&dir, pathspec);
+		if (pathspec)
+			prune_directory(&dir, pathspec, baselen);
+	}
 
 	if (refresh_only) {
 		refresh(verbose, pathspec);
diff --git a/builtin-clean.c b/builtin-clean.c
index 1c1b6d2..2d8c735 100644
--- a/builtin-clean.c
+++ b/builtin-clean.c
@@ -33,7 +33,6 @@ int cmd_clean(int argc, const char **argv, const char *prefix)
 	int ignored_only = 0, baselen = 0, config_set = 0, errors = 0;
 	struct strbuf directory = STRBUF_INIT;
 	struct dir_struct dir;
-	const char *path, *base;
 	static const char **pathspec;
 	struct strbuf buf = STRBUF_INIT;
 	const char *qname;
@@ -78,16 +77,7 @@ int cmd_clean(int argc, const char **argv, const char *prefix)
 	pathspec = get_pathspec(prefix, argv);
 	read_cache();
 
-	/*
-	 * Calculate common prefix for the pathspec, and
-	 * use that to optimize the directory walk
-	 */
-	baselen = common_prefix(pathspec);
-	path = ".";
-	base = "";
-	if (baselen)
-		path = base = xmemdupz(*pathspec, baselen);
-	read_directory(&dir, path, base, baselen, pathspec);
+	fill_directory(&dir, pathspec);
 
 	if (pathspec)
 		seen = xmalloc(argc > 0 ? argc : 1);
diff --git a/builtin-ls-files.c b/builtin-ls-files.c
index 2312866..f473220 100644
--- a/builtin-ls-files.c
+++ b/builtin-ls-files.c
@@ -161,12 +161,7 @@ static void show_files(struct dir_struct *dir, const char *prefix)
 
 	/* For cached/deleted files we don't need to even do the readdir */
 	if (show_others || show_killed) {
-		const char *path = ".", *base = "";
-		int baselen = prefix_len;
-
-		if (baselen)
-			path = base = prefix;
-		read_directory(dir, path, base, baselen, pathspec);
+		fill_directory(dir, pathspec);
 		if (show_others)
 			show_other_files(dir);
 		if (show_killed)
diff --git a/dir.c b/dir.c
index 74b3bbf..0c8553b 100644
--- a/dir.c
+++ b/dir.c
@@ -19,7 +19,7 @@ static int read_directory_recursive(struct dir_struct *dir,
 	int check_only, const struct path_simplify *simplify);
 static int get_dtype(struct dirent *de, const char *path);
 
-int common_prefix(const char **pathspec)
+static int common_prefix(const char **pathspec)
 {
 	const char *path, *slash, *next;
 	int prefix;
@@ -52,6 +52,27 @@ int common_prefix(const char **pathspec)
 	return prefix;
 }
 
+int fill_directory(struct dir_struct *dir, const char **pathspec)
+{
+	const char *path, *base;
+	int baselen;
+
+	/*
+	 * Calculate common prefix for the pathspec, and
+	 * use that to optimize the directory walk
+	 */
+	baselen = common_prefix(pathspec);
+	path = "";
+	base = "";
+
+	if (baselen)
+		path = base = xmemdupz(*pathspec, baselen);
+
+	/* Read the directory and prune it */
+	read_directory(dir, path, base, baselen, pathspec);
+	return baselen;
+}
+
 /*
  * Does 'match' match the given name?
  * A match is found if
diff --git a/dir.h b/dir.h
index 541286a..f9d69dd 100644
--- a/dir.h
+++ b/dir.h
@@ -61,13 +61,12 @@ struct dir_struct {
 	char basebuf[PATH_MAX];
 };
 
-extern int common_prefix(const char **pathspec);
-
 #define MATCHED_RECURSIVELY 1
 #define MATCHED_FNMATCH 2
 #define MATCHED_EXACTLY 3
 extern int match_pathspec(const char **pathspec, const char *name, int namelen, int prefix, char *seen);
 
+extern int fill_directory(struct dir_struct *dir, const char **pathspec);
 extern int read_directory(struct dir_struct *, const char *path, const char *base, int baselen, const char **pathspec);
 
 extern int excluded(struct dir_struct *, const char *, int *);
diff --git a/wt-status.c b/wt-status.c
index 0ca4b13..47735d8 100644
--- a/wt-status.c
+++ b/wt-status.c
@@ -255,7 +255,7 @@ static void wt_status_print_untracked(struct wt_status *s)
 			DIR_SHOW_OTHER_DIRECTORIES | DIR_HIDE_EMPTY_DIRECTORIES;
 	setup_standard_excludes(&dir);
 
-	read_directory(&dir, ".", "", 0, NULL);
+	fill_directory(&dir, NULL);
 	for(i = 0; i < dir.nr; i++) {
 		struct dir_entry *ent = dir.entries[i];
 		if (!cache_name_is_other(ent->name, ent->len))
-- 
1.6.3.3.412.gf581d

[PATCH 2/3] Simplify read_directory[_recursive]() arguments

[Linus Torvalds]

From: Linus Torvalds <torvalds@linux-foundation.org>
Date: Wed, 8 Jul 2009 19:24:39 -0700
Subject: [PATCH 2/3] Simplify read_directory[_recursive]() arguments

Stop the insanity with separate 'path' and 'base' arguments that must
match.  We don't need that crazy interface any more, since we cleaned up
handling of 'path' in commit da4b3e8c28b1dc2b856d2555ac7bb47ab712598c.

Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
---

The diffstat says it only removes a single line, but it _simplifies_ a lot 
of them, and gets rid of the horrible confusion about what 'path' vs 
'base' means.

 dir.c          |   57 +++++++++++++++++++++++++++----------------------------
 dir.h          |    2 +-
 unpack-trees.c |    2 +-
 3 files changed, 30 insertions(+), 31 deletions(-)

diff --git a/dir.c b/dir.c
index 0c8553b..b0671f5 100644
--- a/dir.c
+++ b/dir.c
@@ -14,8 +14,7 @@ struct path_simplify {
 	const char *path;
 };
 
-static int read_directory_recursive(struct dir_struct *dir,
-	const char *path, const char *base, int baselen,
+static int read_directory_recursive(struct dir_struct *dir, const char *path, int len,
 	int check_only, const struct path_simplify *simplify);
 static int get_dtype(struct dirent *de, const char *path);
 
@@ -54,23 +53,22 @@ static int common_prefix(const char **pathspec)
 
 int fill_directory(struct dir_struct *dir, const char **pathspec)
 {
-	const char *path, *base;
-	int baselen;
+	const char *path;
+	int len;
 
 	/*
 	 * Calculate common prefix for the pathspec, and
 	 * use that to optimize the directory walk
 	 */
-	baselen = common_prefix(pathspec);
+	len = common_prefix(pathspec);
 	path = "";
-	base = "";
 
-	if (baselen)
-		path = base = xmemdupz(*pathspec, baselen);
+	if (len)
+		path = xmemdupz(*pathspec, len);
 
 	/* Read the directory and prune it */
-	read_directory(dir, path, base, baselen, pathspec);
-	return baselen;
+	read_directory(dir, path, len, pathspec);
+	return len;
 }
 
 /*
@@ -526,7 +524,7 @@ static enum directory_treatment treat_directory(struct dir_struct *dir,
 	/* This is the "show_other_directories" case */
 	if (!(dir->flags & DIR_HIDE_EMPTY_DIRECTORIES))
 		return show_directory;
-	if (!read_directory_recursive(dir, dirname, dirname, len, 1, simplify))
+	if (!read_directory_recursive(dir, dirname, len, 1, simplify))
 		return ignore_directory;
 	return show_directory;
 }
@@ -595,15 +593,15 @@ static int get_dtype(struct dirent *de, const char *path)
  * Also, we ignore the name ".git" (even if it is not a directory).
  * That likely will not change.
  */
-static int read_directory_recursive(struct dir_struct *dir, const char *path, const char *base, int baselen, int check_only, const struct path_simplify *simplify)
+static int read_directory_recursive(struct dir_struct *dir, const char *base, int baselen, int check_only, const struct path_simplify *simplify)
 {
-	DIR *fdir = opendir(*path ? path : ".");
+	DIR *fdir = opendir(*base ? base : ".");
 	int contents = 0;
 
 	if (fdir) {
 		struct dirent *de;
-		char fullname[PATH_MAX + 1];
-		memcpy(fullname, base, baselen);
+		char path[PATH_MAX + 1];
+		memcpy(path, base, baselen);
 
 		while ((de = readdir(fdir)) != NULL) {
 			int len, dtype;
@@ -614,17 +612,18 @@ static int read_directory_recursive(struct dir_struct *dir, const char *path, co
 				continue;
 			len = strlen(de->d_name);
 			/* Ignore overly long pathnames! */
-			if (len + baselen + 8 > sizeof(fullname))
+			if (len + baselen + 8 > sizeof(path))
 				continue;
-			memcpy(fullname + baselen, de->d_name, len+1);
-			if (simplify_away(fullname, baselen + len, simplify))
+			memcpy(path + baselen, de->d_name, len+1);
+			len = baselen + len;
+			if (simplify_away(path, len, simplify))
 				continue;
 
 			dtype = DTYPE(de);
-			exclude = excluded(dir, fullname, &dtype);
+			exclude = excluded(dir, path, &dtype);
 			if (exclude && (dir->flags & DIR_COLLECT_IGNORED)
-			    && in_pathspec(fullname, baselen + len, simplify))
-				dir_add_ignored(dir, fullname, baselen + len);
+			    && in_pathspec(path, len, simplify))
+				dir_add_ignored(dir, path,len);
 
 			/*
 			 * Excluded? If we don't explicitly want to show
@@ -634,7 +633,7 @@ static int read_directory_recursive(struct dir_struct *dir, const char *path, co
 				continue;
 
 			if (dtype == DT_UNKNOWN)
-				dtype = get_dtype(de, fullname);
+				dtype = get_dtype(de, path);
 
 			/*
 			 * Do we want to see just the ignored files?
@@ -651,9 +650,9 @@ static int read_directory_recursive(struct dir_struct *dir, const char *path, co
 			default:
 				continue;
 			case DT_DIR:
-				memcpy(fullname + baselen + len, "/", 2);
+				memcpy(path + len, "/", 2);
 				len++;
-				switch (treat_directory(dir, fullname, baselen + len, simplify)) {
+				switch (treat_directory(dir, path, len, simplify)) {
 				case show_directory:
 					if (exclude != !!(dir->flags
 							& DIR_SHOW_IGNORED))
@@ -661,7 +660,7 @@ static int read_directory_recursive(struct dir_struct *dir, const char *path, co
 					break;
 				case recurse_into_directory:
 					contents += read_directory_recursive(dir,
-						fullname, fullname, baselen + len, 0, simplify);
+						path, len, 0, simplify);
 					continue;
 				case ignore_directory:
 					continue;
@@ -675,7 +674,7 @@ static int read_directory_recursive(struct dir_struct *dir, const char *path, co
 			if (check_only)
 				goto exit_early;
 			else
-				dir_add_name(dir, fullname, baselen + len);
+				dir_add_name(dir, path, len);
 		}
 exit_early:
 		closedir(fdir);
@@ -738,15 +737,15 @@ static void free_simplify(struct path_simplify *simplify)
 	free(simplify);
 }
 
-int read_directory(struct dir_struct *dir, const char *path, const char *base, int baselen, const char **pathspec)
+int read_directory(struct dir_struct *dir, const char *path, int len, const char **pathspec)
 {
 	struct path_simplify *simplify;
 
-	if (has_symlink_leading_path(path, strlen(path)))
+	if (has_symlink_leading_path(path, len))
 		return dir->nr;
 
 	simplify = create_simplify(pathspec);
-	read_directory_recursive(dir, path, base, baselen, 0, simplify);
+	read_directory_recursive(dir, path, len, 0, simplify);
 	free_simplify(simplify);
 	qsort(dir->entries, dir->nr, sizeof(struct dir_entry *), cmp_name);
 	qsort(dir->ignored, dir->ignored_nr, sizeof(struct dir_entry *), cmp_name);
diff --git a/dir.h b/dir.h
index f9d69dd..a631446 100644
--- a/dir.h
+++ b/dir.h
@@ -67,7 +67,7 @@ struct dir_struct {
 extern int match_pathspec(const char **pathspec, const char *name, int namelen, int prefix, char *seen);
 
 extern int fill_directory(struct dir_struct *dir, const char **pathspec);
-extern int read_directory(struct dir_struct *, const char *path, const char *base, int baselen, const char **pathspec);
+extern int read_directory(struct dir_struct *, const char *path, int len, const char **pathspec);
 
 extern int excluded(struct dir_struct *, const char *, int *);
 extern void add_excludes_from_file(struct dir_struct *, const char *fname);
diff --git a/unpack-trees.c b/unpack-trees.c
index 05d0bb1..42c7d7d 100644
--- a/unpack-trees.c
+++ b/unpack-trees.c
@@ -551,7 +551,7 @@ static int verify_clean_subdirectory(struct cache_entry *ce, const char *action,
 	memset(&d, 0, sizeof(d));
 	if (o->dir)
 		d.exclude_per_dir = o->dir->exclude_per_dir;
-	i = read_directory(&d, ce->name, pathbuf, namelen+1, NULL);
+	i = read_directory(&d, pathbuf, namelen+1, NULL);
 	if (i)
 		return o->gently ? -1 :
 			error(ERRORMSG(o, not_uptodate_dir), ce->name);
-- 
1.6.3.3.412.gf581d

[PATCH 3/3] Avoid doing extra 'lstat()'s for d_type if we have an up-to-date cache entry

[Linus Torvalds]

From: Linus Torvalds <torvalds@linux-foundation.org>
Date: Wed, 8 Jul 2009 19:31:49 -0700
Subject: [PATCH 3/3] Avoid doing extra 'lstat()'s for d_type if we have an up-to-date cache entry

On filesystems without d_type, we can look at the cache entry first.
Doing an lstat() can be expensive.

Reported by Dmitry Potapov for Cygwin.

Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
---

This is the same patch I already sent Dmitry, but now it applies on top of 
the cleaned-up read_directory_recursive() code.

 dir.c |   14 +++++++++-----
 1 files changed, 9 insertions(+), 5 deletions(-)

diff --git a/dir.c b/dir.c
index b0671f5..8a9e7d8 100644
--- a/dir.c
+++ b/dir.c
@@ -16,7 +16,7 @@ struct path_simplify {
 
 static int read_directory_recursive(struct dir_struct *dir, const char *path, int len,
 	int check_only, const struct path_simplify *simplify);
-static int get_dtype(struct dirent *de, const char *path);
+static int get_dtype(struct dirent *de, const char *path, int len);
 
 static int common_prefix(const char **pathspec)
 {
@@ -326,7 +326,7 @@ static int excluded_1(const char *pathname,
 
 			if (x->flags & EXC_FLAG_MUSTBEDIR) {
 				if (*dtype == DT_UNKNOWN)
-					*dtype = get_dtype(NULL, pathname);
+					*dtype = get_dtype(NULL, pathname, pathlen);
 				if (*dtype != DT_DIR)
 					continue;
 			}
@@ -566,14 +566,18 @@ static int in_pathspec(const char *path, int len, const struct path_simplify *si
 	return 0;
 }
 
-static int get_dtype(struct dirent *de, const char *path)
+static int get_dtype(struct dirent *de, const char *path, int len)
 {
 	int dtype = de ? DTYPE(de) : DT_UNKNOWN;
+	struct cache_entry *ce;
 	struct stat st;
 
 	if (dtype != DT_UNKNOWN)
 		return dtype;
-	if (lstat(path, &st))
+	ce = cache_name_exists(path, len, 0);
+	if (ce && ce_uptodate(ce))
+		st.st_mode = ce->ce_mode;
+	else if (lstat(path, &st))
 		return dtype;
 	if (S_ISREG(st.st_mode))
 		return DT_REG;
@@ -633,7 +637,7 @@ static int read_directory_recursive(struct dir_struct *dir, const char *base, in
 				continue;
 
 			if (dtype == DT_UNKNOWN)
-				dtype = get_dtype(de, path);
+				dtype = get_dtype(de, path, len);
 
 			/*
 			 * Do we want to see just the ignored files?
-- 
1.6.3.3.412.gf581d

Re: [PATCH 3/3] Avoid doing extra 'lstat()'s for d_type if we have an up-to-date cache entry

[Junio C Hamano]

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

> From: Linus Torvalds <torvalds@linux-foundation.org>
> Date: Wed, 8 Jul 2009 19:31:49 -0700
> Subject: [PATCH 3/3] Avoid doing extra 'lstat()'s for d_type if we have an up-to-date cache entry
>
> On filesystems without d_type, we can look at the cache entry first.
> Doing an lstat() can be expensive.

Thanks.

I was wondering if we could also say that D exists as a directory when we
know there is D/F in the index and is up to date.

Re: [PATCH 3/3] Avoid doing extra 'lstat()'s for d_type if we have an up-to-date cache entry

[Linus Torvalds]

On Thu, 9 Jul 2009, Junio C Hamano wrote:
> 
> I was wondering if we could also say that D exists as a directory when we
> know there is D/F in the index and is up to date.

Yeah, that would probably be a good thing, but is slightly slower to look 
up (we have the name hashing for the case-ignoring code anyway, but that 
only works for exact names, so you can't look up directories that way).

You'd have to use the regular binary search for that (or we'd have to 
change it to hash directories too - which we might want to do for other 
reasons, but don't do now).

Something like this?

		Linus

---
 dir.c |   39 ++++++++++++++++++++++++++++++++++-----
 1 files changed, 34 insertions(+), 5 deletions(-)

diff --git a/dir.c b/dir.c
index 8a9e7d8..fb7432e 100644
--- a/dir.c
+++ b/dir.c
@@ -566,18 +566,47 @@ static int in_pathspec(const char *path, int len, const struct path_simplify *si
 	return 0;
 }
 
+static int get_index_mode(const char *path, int len)
+{
+	int pos;
+	struct cache_entry *ce;
+
+	ce = cache_name_exists(path, len, 0);
+	if (ce) {
+		if (ce_uptodate(ce))
+			return ce->ce_mode;
+		return 0;
+	}
+
+	/* Try to look it up as a directory */
+	pos = cache_name_pos(path, len);
+	if (pos >= 0)
+		return 0;
+	pos = -pos-1;
+	while (pos < active_nr) {
+		ce = active_cache[pos++];
+		if (strncmp(ce->name, path, len))
+			break;
+		if (ce->name[len] > '/')
+			break;
+		if (ce->name[len] < '/')
+			continue;
+		if (!ce_uptodate(ce))
+			break;	/* continue? */
+		return S_IFDIR;
+	}
+	return 0;
+}
+
 static int get_dtype(struct dirent *de, const char *path, int len)
 {
 	int dtype = de ? DTYPE(de) : DT_UNKNOWN;
-	struct cache_entry *ce;
 	struct stat st;
 
 	if (dtype != DT_UNKNOWN)
 		return dtype;
-	ce = cache_name_exists(path, len, 0);
-	if (ce && ce_uptodate(ce))
-		st.st_mode = ce->ce_mode;
-	else if (lstat(path, &st))
+	st.st_mode = get_index_mode(path, len);
+	if (!st.st_mode && lstat(path, &st))
 		return dtype;
 	if (S_ISREG(st.st_mode))
 		return DT_REG;

Re: [PATCH 3/3] Avoid doing extra 'lstat()'s for d_type if we have an up-to-date cache entry

[Junio C Hamano]

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

> On Thu, 9 Jul 2009, Junio C Hamano wrote:
>> 
>> I was wondering if we could also say that D exists as a directory when we
>> know there is D/F in the index and is up to date.
>
> Yeah, that would probably be a good thing, but is slightly slower to look 
> up (we have the name hashing for the case-ignoring code anyway, but that 
> only works for exact names, so you can't look up directories that way).
>
> You'd have to use the regular binary search for that (or we'd have to 
> change it to hash directories too - which we might want to do for other 
> reasons, but don't do now).
>
> Something like this?

Yeah, in Dmitry's response that crossed with this update patch from you,
he says lstat() on directories are still problem---it would be interesting to
hear what he sees after applying this patch and retesting.

> +static int get_index_mode(const char *path, int len)
> +{
> +	int pos;
> +	struct cache_entry *ce;
> +
> +	ce = cache_name_exists(path, len, 0);
> +	if (ce) {
> +		if (ce_uptodate(ce))
> +			return ce->ce_mode;

You return ce->ce_mode for up-to-date entries.  I do not remember what
ce_uptodate(ce) says for gitlinks, but ce->ce_mode for them would be
160000 that is not very kosher to give to S_ISDIR().  I realize that this
worry actually applies to your patch from yesterday, the one Dmitry
already tested.

> +		return 0;
> +	}
> +
> +	/* Try to look it up as a directory */
> +	pos = cache_name_pos(path, len);
> +	if (pos >= 0)
> +		return 0;

How can this find an exact entry for the path?  Assuming that the name
hash cache_name_exists() is not out of sync?  Shouldn't this be a BUG()
instead of "It somehow exists as a blob or submodule, and we'll let the
regular lstat() codepath take care of it by returning 0"?

> +	pos = -pos-1;
> +	while (pos < active_nr) {
> +		ce = active_cache[pos++];
> +		if (strncmp(ce->name, path, len))
> +			break;
> +		if (ce->name[len] > '/')
> +			break;
> +		if (ce->name[len] < '/')
> +			continue;
> +		if (!ce_uptodate(ce))
> +			break;	/* continue? */

I think this should be continue, as the directory D you are interested in
may have two files, one modified, the other uptodate.

> +		return S_IFDIR;
> +	}
> +	return 0;
> +}
> +
>  static int get_dtype(struct dirent *de, const char *path, int len)
>  {
>  	int dtype = de ? DTYPE(de) : DT_UNKNOWN;
> -	struct cache_entry *ce;
>  	struct stat st;
>  
>  	if (dtype != DT_UNKNOWN)
>  		return dtype;
> -	ce = cache_name_exists(path, len, 0);
> -	if (ce && ce_uptodate(ce))
> -		st.st_mode = ce->ce_mode;
> -	else if (lstat(path, &st))
> +	st.st_mode = get_index_mode(path, len);
> +	if (!st.st_mode && lstat(path, &st))
>  		return dtype;
>  	if (S_ISREG(st.st_mode))
>  		return DT_REG;

Re: [PATCH 3/3] Avoid doing extra 'lstat()'s for d_type if we have an up-to-date cache entry

[Linus Torvalds]

On Thu, 9 Jul 2009, Junio C Hamano wrote:
> > +
> > +	/* Try to look it up as a directory */
> > +	pos = cache_name_pos(path, len);
> > +	if (pos >= 0)
> > +		return 0;
> 
> How can this find an exact entry for the path?  Assuming that the name
> hash cache_name_exists() is not out of sync?

Hopefully it would never trigger. But I'd rather write robust code that 
doesn't make any fancy assumptions. Keep it simple - and keep it working 
even if surprising things happen. 

> > +		if (!ce_uptodate(ce))
> > +			break;	/* continue? */
> 
> I think this should be continue, as the directory D you are interested in
> may have two files, one modified, the other uptodate.

The thing is, the directory may have subdirectories, and there may be 
tens of thousands of files there. And maybe this gets called by code that 
hasn't done any cache preloading at all, so nothing will be up-to-date.

Do we want to loop over thousands of entries? Or do we want to loop as 
little as possible, and just say "most of the time the first entry will be 
representative".

But I did put the 'continue' in a comment, because it's not a correctness 
issue, it's a gut feel. 

			Linus

Re: [PATCH 3/3] Avoid doing extra 'lstat()'s for d_type if we have an up-to-date cache entry

[Junio C Hamano]

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

>> > +		if (!ce_uptodate(ce))
>> > +			break;	/* continue? */
>> 
>> I think this should be continue, as the directory D you are interested in
>> may have two files, one modified, the other uptodate.
>
> The thing is, the directory may have subdirectories, and there may be 
> tens of thousands of files there. And maybe this gets called by code that 
> hasn't done any cache preloading at all, so nothing will be up-to-date.
>
> Do we want to loop over thousands of entries? Or do we want to loop as 
> little as possible, and just say "most of the time the first entry will be 
> representative".

Ah, I see.

It depends on how expensive it is to iterate over an in-core array to
check a single bit (that may not even have been updated) in the cache
entries, compared to an extra lstat().  Perhaps we could autotune that,
but it probably is not worth it. ;-)

Re: [PATCH 3/3] Avoid doing extra 'lstat()'s for d_type if we have an up-to-date cache entry

[Linus Torvalds]

> > +	ce = cache_name_exists(path, len, 0);
> > +	if (ce) {
> > +		if (ce_uptodate(ce))
> > +			return ce->ce_mode;
> 
> You return ce->ce_mode for up-to-date entries.  I do not remember what
> ce_uptodate(ce) says for gitlinks, but ce->ce_mode for them would be
> 160000 that is not very kosher to give to S_ISDIR().  I realize that this
> worry actually applies to your patch from yesterday, the one Dmitry
> already tested.

Yeah. I guess we don't have a lot of coverage for subprojects.

Here's an alternative version that just makes the thing return the DT_xyz 
flag rather than the mode (and it returns DT_REG for symlinks too, because 
it knows nobody cares - we only really care about "directory or not")

		Linus

---
 dir.c |   47 ++++++++++++++++++++++++++++++++++++++++++-----
 1 files changed, 42 insertions(+), 5 deletions(-)

diff --git a/dir.c b/dir.c
index 8a9e7d8..e05b850 100644
--- a/dir.c
+++ b/dir.c
@@ -566,18 +566,55 @@ static int in_pathspec(const char *path, int len, const struct path_simplify *si
 	return 0;
 }
 
+static int get_index_dtype(const char *path, int len)
+{
+	int pos;
+	struct cache_entry *ce;
+
+	ce = cache_name_exists(path, len, 0);
+	if (ce) {
+		if (!ce_uptodate(ce))
+			return DT_UNKNOWN;
+		if (S_ISGITLINK(ce->ce_mode))
+			return DT_DIR;
+		/*
+		 * Nobody actually cares about the
+		 * difference between DT_LNK and DT_REG
+		 */
+		return DT_REG;
+	}
+
+	/* Try to look it up as a directory */
+	pos = cache_name_pos(path, len);
+	if (pos >= 0)
+		return DT_UNKNOWN;
+	pos = -pos-1;
+	while (pos < active_nr) {
+		ce = active_cache[pos++];
+		if (strncmp(ce->name, path, len))
+			break;
+		if (ce->name[len] > '/')
+			break;
+		if (ce->name[len] < '/')
+			continue;
+		if (!ce_uptodate(ce))
+			break;	/* continue? */
+		return DT_DIR;
+	}
+	return DT_UNKNOWN;
+}
+
 static int get_dtype(struct dirent *de, const char *path, int len)
 {
 	int dtype = de ? DTYPE(de) : DT_UNKNOWN;
-	struct cache_entry *ce;
 	struct stat st;
 
 	if (dtype != DT_UNKNOWN)
 		return dtype;
-	ce = cache_name_exists(path, len, 0);
-	if (ce && ce_uptodate(ce))
-		st.st_mode = ce->ce_mode;
-	else if (lstat(path, &st))
+	dtype = get_index_dtype(path, len);
+	if (dtype != DT_UNKNOWN)
+		return dtype;
+	if (lstat(path, &st))
 		return dtype;
 	if (S_ISREG(st.st_mode))
 		return DT_REG;

Re: [PATCH 3/3] Avoid doing extra 'lstat()'s for d_type if we have an up-to-date cache entry

[Linus Torvalds]

On Thu, 9 Jul 2009, Linus Torvalds wrote:
> 
> Here's an alternative version that just makes the thing return the DT_xyz 
> flag rather than the mode (and it returns DT_REG for symlinks too, because 
> it knows nobody cares - we only really care about "directory or not")

Btw, I'm wondering whether this "look if 'dir/file' exists in index and is 
up-to-date" is really safe.

We don't really verify the whole path when we mark things ce_uptodate(). 
Part of what read_directory() does is to find directory entries, and in 
the process things like "git add" will notice if there's a conflict with 
existing index entries.

So if a directory has changed into a symlink to a directory, this 
particular optimization will actually hide that, I suspect. I haven't 
tested, though. But it might be worth-while to see what happens when you 
had a directory structure, and then do

	mkdir dir
	touch dir/a
	touch dir/b
	git add dir

	mv dir new-dir
	ln -s new-dir dir
	git status

Quite frankly, I'd personally be perfectly ok with git _not_ noticing 
subtle things like this automatically, but..

		Linus

Re: [PATCH 3/3] Avoid doing extra 'lstat()'s for d_type if we have an up-to-date cache entry

[Junio C Hamano]

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

> We don't really verify the whole path when we mark things ce_uptodate(). 
> Part of what read_directory() does is to find directory entries, and in 
> the process things like "git add" will notice if there's a conflict with 
> existing index entries.
>
> So if a directory has changed into a symlink to a directory, this 
> particular optimization will actually hide that, I suspect. I haven't 
> tested, though. But it might be worth-while to see what happens when you 
> had a directory structure, and then do
>
> 	mkdir dir
> 	touch dir/a
> 	touch dir/b
> 	git add dir
>
> 	mv dir new-dir
> 	ln -s new-dir dir
> 	git status

In existing codepaths, we have "has_symlink_leading_path()" checks to
notice that tracked dir/[ab] have disappeared.  "git diff" before or after
"git status" in the above sequence does notice what you did.

Would dir/a be marked as uptodate in the index, if somebody preloads the
index, after the above sequence?  I hope not.

Re: [PATCH 3/3] Avoid doing extra 'lstat()'s for d_type if we have an up-to-date cache entry

[Linus Torvalds]

On Thu, 9 Jul 2009, Junio C Hamano wrote:
> 
> Would dir/a be marked as uptodate in the index, if somebody preloads the
> index, after the above sequence?  I hope not.

Index preloading does not care about directories. It does the standard

	if (ie_match_stat(index, ce, &st, CE_MATCH_RACY_IS_DIRTY))
		continue;

and since it's all threaded (and the whole _point_ is that it's threaded), 
it can't do anything fancier. Our lstat cache is _not_ thread-safe.

But preloading isn't even the only thing to do that. All the merge logics 
also just do "ie_match_stat()", as does git checkout, although maybe the 
directory gets validated separately for those cases before recursion.

Looking at "ce_mark_uptodate()", I think diff-lib.c is the only one that 
actually does that whole "has_symlink_leading_path()" thing (in 
"check_removed()").

I guess we could make out lstat cache thread-safe, and have the callers 
pass in a per-thread "struct cache_def *". That would work well enough for 
preloading (and everybody else could just use some random static one and 
pass that in).

Added Kjetil to cc.

			Linus

[PATCH 4/3] Avoid using 'lstat()' to figure out directories

[Linus Torvalds]

From: Linus Torvalds <torvalds@linux-foundation.org>
Date: Thu, 9 Jul 2009 13:14:28 -0700
Subject: [PATCH 4/3] Avoid using 'lstat()' to figure out directories

If we have an up-to-date index entry for a file in that directory, we
can know that the directories leading up to that file must be
directories.  No need to do an lstat() on the directory.

Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
---

This is the patch I already sent out earlier. Now it's just numbered. 
There's going to be an additional three patches to actually give the right 
behavior for index preloading, so that we can really say "if CE_UPTODATE 
is set, then the whole directory structure is valid".

 dir.c |   47 ++++++++++++++++++++++++++++++++++++++++++-----
 1 files changed, 42 insertions(+), 5 deletions(-)

diff --git a/dir.c b/dir.c
index 8a9e7d8..e05b850 100644
--- a/dir.c
+++ b/dir.c
@@ -566,18 +566,55 @@ static int in_pathspec(const char *path, int len, const struct path_simplify *si
 	return 0;
 }
 
+static int get_index_dtype(const char *path, int len)
+{
+	int pos;
+	struct cache_entry *ce;
+
+	ce = cache_name_exists(path, len, 0);
+	if (ce) {
+		if (!ce_uptodate(ce))
+			return DT_UNKNOWN;
+		if (S_ISGITLINK(ce->ce_mode))
+			return DT_DIR;
+		/*
+		 * Nobody actually cares about the
+		 * difference between DT_LNK and DT_REG
+		 */
+		return DT_REG;
+	}
+
+	/* Try to look it up as a directory */
+	pos = cache_name_pos(path, len);
+	if (pos >= 0)
+		return DT_UNKNOWN;
+	pos = -pos-1;
+	while (pos < active_nr) {
+		ce = active_cache[pos++];
+		if (strncmp(ce->name, path, len))
+			break;
+		if (ce->name[len] > '/')
+			break;
+		if (ce->name[len] < '/')
+			continue;
+		if (!ce_uptodate(ce))
+			break;	/* continue? */
+		return DT_DIR;
+	}
+	return DT_UNKNOWN;
+}
+
 static int get_dtype(struct dirent *de, const char *path, int len)
 {
 	int dtype = de ? DTYPE(de) : DT_UNKNOWN;
-	struct cache_entry *ce;
 	struct stat st;
 
 	if (dtype != DT_UNKNOWN)
 		return dtype;
-	ce = cache_name_exists(path, len, 0);
-	if (ce && ce_uptodate(ce))
-		st.st_mode = ce->ce_mode;
-	else if (lstat(path, &st))
+	dtype = get_index_dtype(path, len);
+	if (dtype != DT_UNKNOWN)
+		return dtype;
+	if (lstat(path, &st))
 		return dtype;
 	if (S_ISREG(st.st_mode))
 		return DT_REG;
-- 
1.6.3.3.415.ga8877

[PATCH 5/3] Prepare symlink caching for thread-safety

[Linus Torvalds]

From: Linus Torvalds <torvalds@linux-foundation.org>
Date: Thu, 9 Jul 2009 13:23:59 -0700
Subject: [PATCH 5/3] Prepare symlink caching for thread-safety

This doesn't actually change the external interfaces, so they are still
thread-unsafe, but it makes the code internally pass a pointer to a
local 'struct cache_def' around, so that the core code can be made
thread-safe.

The threaded index preloading will want to verify that the paths leading
up to a pathname are all real directories.

Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
---

No real changes, but I renamed the static 'cache' data structure 
'default_cache', and made all the internal functions take a pointer 
instead of using the static version.

The functions with external linkage are left semantically unchanged by 
just making them do a simple

	struct cache_def *cache = &default_cache;

and then using that.

 symlinks.c |   75 ++++++++++++++++++++++++++++++++----------------------------
 1 files changed, 40 insertions(+), 35 deletions(-)

diff --git a/symlinks.c b/symlinks.c
index 8dcd632..08ad353 100644
--- a/symlinks.c
+++ b/symlinks.c
@@ -38,13 +38,13 @@ static struct cache_def {
 	int flags;
 	int track_flags;
 	int prefix_len_stat_func;
-} cache;
+} default_cache;
 
-static inline void reset_lstat_cache(void)
+static inline void reset_lstat_cache(struct cache_def *cache)
 {
-	cache.path[0] = '\0';
-	cache.len = 0;
-	cache.flags = 0;
+	cache->path[0] = '\0';
+	cache->len = 0;
+	cache->flags = 0;
 	/*
 	 * The track_flags and prefix_len_stat_func members is only
 	 * set by the safeguard rule inside lstat_cache()
@@ -70,23 +70,23 @@ static inline void reset_lstat_cache(void)
  * of the prefix, where the cache should use the stat() function
  * instead of the lstat() function to test each path component.
  */
-static int lstat_cache(const char *name, int len,
+static int lstat_cache(struct cache_def *cache, const char *name, int len,
 		       int track_flags, int prefix_len_stat_func)
 {
 	int match_len, last_slash, last_slash_dir, previous_slash;
 	int match_flags, ret_flags, save_flags, max_len, ret;
 	struct stat st;
 
-	if (cache.track_flags != track_flags ||
-	    cache.prefix_len_stat_func != prefix_len_stat_func) {
+	if (cache->track_flags != track_flags ||
+	    cache->prefix_len_stat_func != prefix_len_stat_func) {
 		/*
 		 * As a safeguard rule we clear the cache if the
 		 * values of track_flags and/or prefix_len_stat_func
 		 * does not match with the last supplied values.
 		 */
-		reset_lstat_cache();
-		cache.track_flags = track_flags;
-		cache.prefix_len_stat_func = prefix_len_stat_func;
+		reset_lstat_cache(cache);
+		cache->track_flags = track_flags;
+		cache->prefix_len_stat_func = prefix_len_stat_func;
 		match_len = last_slash = 0;
 	} else {
 		/*
@@ -94,10 +94,10 @@ static int lstat_cache(const char *name, int len,
 		 * the 2 "excluding" path types.
 		 */
 		match_len = last_slash =
-			longest_path_match(name, len, cache.path, cache.len,
+			longest_path_match(name, len, cache->path, cache->len,
 					   &previous_slash);
-		match_flags = cache.flags & track_flags & (FL_NOENT|FL_SYMLINK);
-		if (match_flags && match_len == cache.len)
+		match_flags = cache->flags & track_flags & (FL_NOENT|FL_SYMLINK);
+		if (match_flags && match_len == cache->len)
 			return match_flags;
 		/*
 		 * If we now have match_len > 0, we would know that
@@ -121,18 +121,18 @@ static int lstat_cache(const char *name, int len,
 	max_len = len < PATH_MAX ? len : PATH_MAX;
 	while (match_len < max_len) {
 		do {
-			cache.path[match_len] = name[match_len];
+			cache->path[match_len] = name[match_len];
 			match_len++;
 		} while (match_len < max_len && name[match_len] != '/');
 		if (match_len >= max_len && !(track_flags & FL_FULLPATH))
 			break;
 		last_slash = match_len;
-		cache.path[last_slash] = '\0';
+		cache->path[last_slash] = '\0';
 
 		if (last_slash <= prefix_len_stat_func)
-			ret = stat(cache.path, &st);
+			ret = stat(cache->path, &st);
 		else
-			ret = lstat(cache.path, &st);
+			ret = lstat(cache->path, &st);
 
 		if (ret) {
 			ret_flags = FL_LSTATERR;
@@ -156,9 +156,9 @@ static int lstat_cache(const char *name, int len,
 	 */
 	save_flags = ret_flags & track_flags & (FL_NOENT|FL_SYMLINK);
 	if (save_flags && last_slash > 0 && last_slash <= PATH_MAX) {
-		cache.path[last_slash] = '\0';
-		cache.len = last_slash;
-		cache.flags = save_flags;
+		cache->path[last_slash] = '\0';
+		cache->len = last_slash;
+		cache->flags = save_flags;
 	} else if ((track_flags & FL_DIR) &&
 		   last_slash_dir > 0 && last_slash_dir <= PATH_MAX) {
 		/*
@@ -172,11 +172,11 @@ static int lstat_cache(const char *name, int len,
 		 * can still cache the path components before the last
 		 * one (the found symlink or non-existing component).
 		 */
-		cache.path[last_slash_dir] = '\0';
-		cache.len = last_slash_dir;
-		cache.flags = FL_DIR;
+		cache->path[last_slash_dir] = '\0';
+		cache->len = last_slash_dir;
+		cache->flags = FL_DIR;
 	} else {
-		reset_lstat_cache();
+		reset_lstat_cache(cache);
 	}
 	return ret_flags;
 }
@@ -188,16 +188,17 @@ static int lstat_cache(const char *name, int len,
 void invalidate_lstat_cache(const char *name, int len)
 {
 	int match_len, previous_slash;
+	struct cache_def *cache = &default_cache;	/* FIXME */
 
-	match_len = longest_path_match(name, len, cache.path, cache.len,
+	match_len = longest_path_match(name, len, cache->path, cache->len,
 				       &previous_slash);
 	if (len == match_len) {
-		if ((cache.track_flags & FL_DIR) && previous_slash > 0) {
-			cache.path[previous_slash] = '\0';
-			cache.len = previous_slash;
-			cache.flags = FL_DIR;
+		if ((cache->track_flags & FL_DIR) && previous_slash > 0) {
+			cache->path[previous_slash] = '\0';
+			cache->len = previous_slash;
+			cache->flags = FL_DIR;
 		} else {
-			reset_lstat_cache();
+			reset_lstat_cache(cache);
 		}
 	}
 }
@@ -207,7 +208,8 @@ void invalidate_lstat_cache(const char *name, int len)
  */
 void clear_lstat_cache(void)
 {
-	reset_lstat_cache();
+	struct cache_def *cache = &default_cache;	/* FIXME */
+	reset_lstat_cache(cache);
 }
 
 #define USE_ONLY_LSTAT  0
@@ -217,7 +219,8 @@ void clear_lstat_cache(void)
  */
 int has_symlink_leading_path(const char *name, int len)
 {
-	return lstat_cache(name, len,
+	struct cache_def *cache = &default_cache;	/* FIXME */
+	return lstat_cache(cache, name, len,
 			   FL_SYMLINK|FL_DIR, USE_ONLY_LSTAT) &
 		FL_SYMLINK;
 }
@@ -228,7 +231,8 @@ int has_symlink_leading_path(const char *name, int len)
  */
 int has_symlink_or_noent_leading_path(const char *name, int len)
 {
-	return lstat_cache(name, len,
+	struct cache_def *cache = &default_cache;	/* FIXME */
+	return lstat_cache(cache, name, len,
 			   FL_SYMLINK|FL_NOENT|FL_DIR, USE_ONLY_LSTAT) &
 		(FL_SYMLINK|FL_NOENT);
 }
@@ -242,7 +246,8 @@ int has_symlink_or_noent_leading_path(const char *name, int len)
  */
 int has_dirs_only_path(const char *name, int len, int prefix_len)
 {
-	return lstat_cache(name, len,
+	struct cache_def *cache = &default_cache;	/* FIXME */
+	return lstat_cache(cache, name, len,
 			   FL_DIR|FL_FULLPATH, prefix_len) &
 		FL_DIR;
 }
-- 
1.6.3.3.415.ga8877

[PATCH 6/3] Export thread-safe version of 'has_symlink_leading_path()'

[Linus Torvalds]

From: Linus Torvalds <torvalds@linux-foundation.org>
Date: Thu, 9 Jul 2009 13:35:31 -0700
Subject: [PATCH 6/3] Export thread-safe version of 'has_symlink_leading_path()'

The threaded index preloading will want it, so that it can avoid
locking by simply using a per-thread symlink/directory cache.

Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
---
This just exposes a thread-safe version of the symlink checking by 
allowing a caller to pass in its own local 'struct cache_def' to the 
function.

No users of this yet, but the next step is trivial and obvious..

 cache.h    |   10 ++++++++++
 symlinks.c |   21 ++++++++++-----------
 2 files changed, 20 insertions(+), 11 deletions(-)

diff --git a/cache.h b/cache.h
index 871c984..f1e5ede 100644
--- a/cache.h
+++ b/cache.h
@@ -744,7 +744,17 @@ struct checkout {
 };
 
 extern int checkout_entry(struct cache_entry *ce, const struct checkout *state, char *topath);
+
+struct cache_def {
+	char path[PATH_MAX + 1];
+	int len;
+	int flags;
+	int track_flags;
+	int prefix_len_stat_func;
+};
+
 extern int has_symlink_leading_path(const char *name, int len);
+extern int threaded_has_symlink_leading_path(struct cache_def *, const char *, int);
 extern int has_symlink_or_noent_leading_path(const char *name, int len);
 extern int has_dirs_only_path(const char *name, int len, int prefix_len);
 extern void invalidate_lstat_cache(const char *name, int len);
diff --git a/symlinks.c b/symlinks.c
index 08ad353..4bdded3 100644
--- a/symlinks.c
+++ b/symlinks.c
@@ -32,13 +32,7 @@ static int longest_path_match(const char *name_a, int len_a,
 	return match_len;
 }
 
-static struct cache_def {
-	char path[PATH_MAX + 1];
-	int len;
-	int flags;
-	int track_flags;
-	int prefix_len_stat_func;
-} default_cache;
+static struct cache_def default_cache;
 
 static inline void reset_lstat_cache(struct cache_def *cache)
 {
@@ -217,12 +211,17 @@ void clear_lstat_cache(void)
 /*
  * Return non-zero if path 'name' has a leading symlink component
  */
+int threaded_has_symlink_leading_path(struct cache_def *cache, const char *name, int len)
+{
+	return lstat_cache(cache, name, len, FL_SYMLINK|FL_DIR, USE_ONLY_LSTAT) & FL_SYMLINK;
+}
+
+/*
+ * Return non-zero if path 'name' has a leading symlink component
+ */
 int has_symlink_leading_path(const char *name, int len)
 {
-	struct cache_def *cache = &default_cache;	/* FIXME */
-	return lstat_cache(cache, name, len,
-			   FL_SYMLINK|FL_DIR, USE_ONLY_LSTAT) &
-		FL_SYMLINK;
+	return threaded_has_symlink_leading_path(&default_cache, name, len);
 }
 
 /*
-- 
1.6.3.3.415.ga8877

[PATCH 7/3] Make index preloading check the whole path to the file

[Linus Torvalds]

From: Linus Torvalds <torvalds@linux-foundation.org>
Date: Thu, 9 Jul 2009 13:37:02 -0700
Subject: [PATCH 7/3] Make index preloading check the whole path to the file

This uses the new thread-safe 'threaded_has_symlink_leading_path()'
function to efficiently verify that the whole path leading up to the
filename is a proper path, and does not contain symlinks.

This makes 'ce_uptodate()' a much stronger guarantee: it no longer just
guarantees that the 'lstat()' of the path would match, it also means
that we know that people haven't played games with moving directories
around and covered it up with symlinks.

Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
---

Totally trivial, now that we have a thread-safe symlink checker.

If we have leading symlinks in the cache-entry path, we will refuse to 
mark it up-to-date. There's no need to even try to stat anything under 
that directory.

 preload-index.c |    3 +++
 1 files changed, 3 insertions(+), 0 deletions(-)

diff --git a/preload-index.c b/preload-index.c
index 88edc5f..c3462dc 100644
--- a/preload-index.c
+++ b/preload-index.c
@@ -34,6 +34,7 @@ static void *preload_thread(void *_data)
 	struct thread_data *p = _data;
 	struct index_state *index = p->index;
 	struct cache_entry **cep = index->cache + p->offset;
+	struct cache_def cache;
 
 	nr = p->nr;
 	if (nr + p->offset > index->cache_nr)
@@ -49,6 +50,8 @@ static void *preload_thread(void *_data)
 			continue;
 		if (!ce_path_match(ce, p->pathspec))
 			continue;
+		if (threaded_has_symlink_leading_path(&cache, ce->name, ce_namelen(ce)))
+			continue;
 		if (lstat(ce->name, &st))
 			continue;
 		if (ie_match_stat(index, ce, &st, CE_MATCH_RACY_IS_DIRTY))
-- 
1.6.3.3.415.ga8877

Re: [PATCH 7/3] Make index preloading check the whole path to the file

[Linus Torvalds]

Ok, with these patches, the strace of the index preload looks very clean, 
and has the required tests for the directory components too:

	...
	26504 lstat("connect.c", {st_mode=S_IFREG|0664, st_size=14312, ...}) = 0
	26504 lstat("contrib", {st_mode=S_IFDIR|0775, st_size=4096, ...}) = 0
	26504 lstat("contrib/README", {st_mode=S_IFREG|0664, st_size=2113, ...}) = 0
	26504 lstat("contrib/blameview", {st_mode=S_IFDIR|0775, st_size=4096, ...}) = 0
	26504 lstat("contrib/blameview/blameview.perl", {st_mode=S_IFREG|0775, st_size=3776, ...}) = 0
	...

ie now it actualyl verifies that the directories leading up to filenames 
are really directories by doing lstat() on them. And the symlink cache 
means that it doesn't do it for every single pathname, only for the first 
lookup per thread and directory.

Maybe Kjetil wants to check the changes, but quite frankly, it looked 
pretty trivial to make that whole has_symlink_leading_path() be 
thread-safe.

			Linus

Re: [PATCH 7/3] Make index preloading check the whole path to the file

[Junio C Hamano]

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

> From: Linus Torvalds <torvalds@linux-foundation.org>
> Date: Thu, 9 Jul 2009 13:37:02 -0700
> Subject: [PATCH 7/3] Make index preloading check the whole path to the file
>
> This uses the new thread-safe 'threaded_has_symlink_leading_path()'
> function to efficiently verify that the whole path leading up to the
> filename is a proper path, and does not contain symlinks.
>
> This makes 'ce_uptodate()' a much stronger guarantee: it no longer just
> guarantees that the 'lstat()' of the path would match, it also means
> that we know that people haven't played games with moving directories
> around and covered it up with symlinks.
>
> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
> ---
>
> Totally trivial, now that we have a thread-safe symlink checker.
>
> If we have leading symlinks in the cache-entry path, we will refuse to 
> mark it up-to-date. There's no need to even try to stat anything under 
> that directory.
>
>  preload-index.c |    3 +++
>  1 files changed, 3 insertions(+), 0 deletions(-)
>
> diff --git a/preload-index.c b/preload-index.c
> index 88edc5f..c3462dc 100644
> --- a/preload-index.c
> +++ b/preload-index.c
> @@ -34,6 +34,7 @@ static void *preload_thread(void *_data)
>  	struct thread_data *p = _data;
>  	struct index_state *index = p->index;
>  	struct cache_entry **cep = index->cache + p->offset;
> +	struct cache_def cache;
>  
>  	nr = p->nr;
>  	if (nr + p->offset > index->cache_nr)
> @@ -49,6 +50,8 @@ static void *preload_thread(void *_data)
>  			continue;
>  		if (!ce_path_match(ce, p->pathspec))
>  			continue;
> +		if (threaded_has_symlink_leading_path(&cache, ce->name, ce_namelen(ce)))
> +			continue;

I must be missing something very obvious, but how would this call behave
on an uninitialized cache defined above, or do we need reset_lstat_cache()
on it before the first use?

>  		if (lstat(ce->name, &st))
>  			continue;
>  		if (ie_match_stat(index, ce, &st, CE_MATCH_RACY_IS_DIRTY))
> -- 
> 1.6.3.3.415.ga8877

Re: [PATCH 7/3] Make index preloading check the whole path to the file

[Linus Torvalds]

On Thu, 9 Jul 2009, Junio C Hamano wrote:
> 
> I must be missing something very obvious, but how would this call behave
> on an uninitialized cache defined above, or do we need reset_lstat_cache()
> on it before the first use?

Neither.

It should be memset() to zero. Good catch.

			Linus

Re: [PATCH 7/3] Make index preloading check the whole path to the file

[Linus Torvalds]

On Thu, 9 Jul 2009, Linus Torvalds wrote:
> 
> It should be memset() to zero. Good catch.

IOW, just this on top. It's the same initialization  that 'default_cache' 
has, except in the case of default_cahe it was implicit in the "static", 
which is why I missed it when I did the "obvious" version.

		Linus
---
 preload-index.c |    1 +
 1 files changed, 1 insertions(+), 0 deletions(-)

diff --git a/preload-index.c b/preload-index.c
index c3462dc..14d5281 100644
--- a/preload-index.c
+++ b/preload-index.c
@@ -36,6 +36,7 @@ static void *preload_thread(void *_data)
 	struct cache_entry **cep = index->cache + p->offset;
 	struct cache_def cache;
 
+	memset(&cache, 0, sizeof(cache));
 	nr = p->nr;
 	if (nr + p->offset > index->cache_nr)
 		nr = index->cache_nr - p->offset;

Re: [PATCH 7/3] Make index preloading check the whole path to the file

[Junio C Hamano]

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

> On Thu, 9 Jul 2009, Junio C Hamano wrote:
>> 
>> I must be missing something very obvious, but how would this call behave
>> on an uninitialized cache defined above, or do we need reset_lstat_cache()
>> on it before the first use?
>
> Neither.
>
> It should be memset() to zero. Good catch.

I actually was hoping to hear "Didn't you notice that this is the first
function run by the pthread and its stack is zeroed by thread creation" or
something clever like that ;-)

Squashed in.  Thanks.

Re: [PATCH 7/3] Make index preloading check the whole path to the file

[Linus Torvalds]

On Fri, 10 Jul 2009, Junio C Hamano wrote:
> 
> I actually was hoping to hear "Didn't you notice that this is the first
> function run by the pthread and its stack is zeroed by thread creation" or
> something clever like that ;-)

It's probably true that it is often zero in practice. I certainly saw no 
problems in my testing, even though I do have preloading on (partly for 
testing, partly because it actually helps a bit on my machine).

I also suspect that the way the whole 'cache_def' thing works, even if 
it's initialized with random crud, you'll probably never notice. There are 
all those safety rules that check that 'cache->track_flags' has to match 
the new value etc in order for the cache to be used. And even when it is 
used, it has no pointers in it, it has that static array and the lengths.

So I don't think you really even need to have the "it was zeroed by 
accident" explanation. It's probably as simple as "even if it is totally 
uninitialized, that will basically never trigger anything odd in 
practice".

Not to mention that the whole new index preloading addition was just a new 
safety feature that we didn't even use to have before - and one that only 
impacted an _optimization_ that didn't change semantics. So in the end: 
even in the really unlikely situation that the cache would have triggered, 
and returned an incorrect return value, the worst that would have happened 
would be that the preloading wasn't quite as efficient.

End result: you did well by noticing the lack of initializers, but I 
_really_ don't think it could probably ever possibly have mattered in 
practice.

			Linus

Re: [PATCH 6/3] Export thread-safe version of 'has_symlink_leading_path()'

[Kjetil Barvik]

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

> From: Linus Torvalds <torvalds@linux-foundation.org>
> Date: Thu, 9 Jul 2009 13:35:31 -0700
> Subject: [PATCH 6/3] Export thread-safe version of 'has_symlink_leading_path()'
>
> The threaded index preloading will want it, so that it can avoid
> locking by simply using a per-thread symlink/directory cache.
>
> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
> ---
> This just exposes a thread-safe version of the symlink checking by 
> allowing a caller to pass in its own local 'struct cache_def' to the 
> function.
>
> No users of this yet, but the next step is trivial and obvious..
>
>  cache.h    |   10 ++++++++++
>  symlinks.c |   21 ++++++++++-----------
>  2 files changed, 20 insertions(+), 11 deletions(-)
>
> diff --git a/cache.h b/cache.h
> index 871c984..f1e5ede 100644
> --- a/cache.h
> +++ b/cache.h
> @@ -744,7 +744,17 @@ struct checkout {
>  };
>  
>  extern int checkout_entry(struct cache_entry *ce, const struct checkout *state, char *topath);
> +
> +struct cache_def {
> +	char path[PATH_MAX + 1];
> +	int len;
> +	int flags;
> +	int track_flags;
> +	int prefix_len_stat_func;
> +};
> +
>  extern int has_symlink_leading_path(const char *name, int len);
> +extern int threaded_has_symlink_leading_path(struct cache_def *, const char *, int);
>  extern int has_symlink_or_noent_leading_path(const char *name, int len);
>  extern int has_dirs_only_path(const char *name, int len, int prefix_len);
>  extern void invalidate_lstat_cache(const char *name, int len);
> diff --git a/symlinks.c b/symlinks.c
> index 08ad353..4bdded3 100644
> --- a/symlinks.c
> +++ b/symlinks.c
> @@ -32,13 +32,7 @@ static int longest_path_match(const char *name_a, int len_a,
>  	return match_len;
>  }
>  
> -static struct cache_def {
> -	char path[PATH_MAX + 1];
> -	int len;
> -	int flags;
> -	int track_flags;
> -	int prefix_len_stat_func;
> -} default_cache;
> +static struct cache_def default_cache;
>  
>  static inline void reset_lstat_cache(struct cache_def *cache)
>  {
> @@ -217,12 +211,17 @@ void clear_lstat_cache(void)
>  /*
>   * Return non-zero if path 'name' has a leading symlink component
>   */
> +int threaded_has_symlink_leading_path(struct cache_def *cache, const char *name, int len)
> +{
> +	return lstat_cache(cache, name, len, FL_SYMLINK|FL_DIR, USE_ONLY_LSTAT) & FL_SYMLINK;

  OK, to follow the style the 3 previous lstat_cache() calls was made
  with (and also let the line length be less than 80), it should have
  been written like this:

     	return lstat_cache(cache, name, len,
			   FL_SYMLINK|FL_DIR, USE_ONLY_LSTAT) &
		FL_SYMLINK;

  Notice that the parmeters which is just copied as arguments to l_c()
  is in the same order and on the first line for it self.  The next line
  contains the rest of the arguments, and the &-part is also on it
  a separate line.

  Stylefix only, so not a big deal.

> +}
> +
> +/*
> + * Return non-zero if path 'name' has a leading symlink component
> + */
>  int has_symlink_leading_path(const char *name, int len)
>  {
> -	struct cache_def *cache = &default_cache;	/* FIXME */

   This would make it inconsistent with the 2 has_*_() functions below,
   which both have such a line.  Only stylefix, no change in semantics.

   I personally liked this line, since it will then be easier to
   "threadify" the function with an extra parameter named "cache".

> -	return lstat_cache(cache, name, len,
> -			   FL_SYMLINK|FL_DIR, USE_ONLY_LSTAT) &
> -		FL_SYMLINK;
> +	return threaded_has_symlink_leading_path(&default_cache, name, len);
>  }
>  
>  /*

  I have looked at and tested (the version from the origin/pu branch, so
  it contains the memset() line squashed in) patch 5/3, 6/3 and 7/3, and
  all 3 patches looks correct, so you can add

     Reviewed-and-tested-by: Kjetil Barvik

  if you want to.

  But, I guess it is me which is a litle late to comment things, since I
  already see that all 3 patches is in the pu, next and master branches
  already, less than 3 days after beeing posted to the malinglist.

  But, would'nt it be a good thing to let all patches at least be in the
  pu branch for minimum x days before entering next and master?  Or: let
  it go minimum x days after beeing posted to the list before entering
  the next and master branch?  x = 4?

  Since the patches is already in master and next, I guess it is not as
  easy as if the patche(es) has been in pu to make a new version of a
  patch, since both master and next is expected to be fast-forward
  branches.

  -- kjetil, which was too late this time, too  :-)

Re: [PATCH 6/3] Export thread-safe version of 'has_symlink_leading_path()'

[Junio C Hamano]

Kjetil Barvik <barvik@broadpark.no> writes:

>   I have looked at and tested (the version from the origin/pu branch, so
>   it contains the memset() line squashed in) patch 5/3, 6/3 and 7/3, and
>   all 3 patches looks correct, so you can add
>
>      Reviewed-and-tested-by: Kjetil Barvik
>
>   if you want to.

Thanks.

>   But, I guess it is me which is a litle late to comment things, since I
>   already see that all 3 patches is in the pu, next and master branches
>   already, less than 3 days after beeing posted to the malinglist.
>
>   But, would'nt it be a good thing to let all patches at least be in the
>   pu branch for minimum x days before entering next and master?  Or: let
>   it go minimum x days after beeing posted to the list before entering
>   the next and master branch?  x = 4?

That number x depends on the quality of the patches and to a great extent
how well I know the area of the code affected by the patch.

Re: [PATCH 4/3] Avoid using 'lstat()' to figure out directories

[Paolo Bonzini]

> +		if (ce->name[len]>  '/')
> +			break;
> +		if (ce->name[len]<  '/')
> +			continue;

What about

	if (ce->name[len] < '/') {
		if (strchr(ce->name + len + 1, '/'))
			break;
		else
			continue;
	}

to just punt if we'd go into a directory?  I'm not much worried about 
accessing foo-0001, foo-0002, foo-0003 while looking for foo/a (that 
would be O(number of files in a directory), which is bearable), but 
risking to go down a huge subtree is not very nice.

Paolo

Re: [PATCH 4/3] Avoid using 'lstat()' to figure out directories

[Linus Torvalds]

On Fri, 10 Jul 2009, Paolo Bonzini wrote:
> 
> I'm not much worried about accessing foo-0001, foo-0002, foo-0003 while 
> looking for foo/a (that would be O(number of files in a directory), 
> which is bearable), but risking to go down a huge subtree is not very 
> nice.

That sounds rather unlikely, and the thing is, even if it were to happen, 
it really wouldn't be that slow. Our data structures are pretty efficient, 
and it wouldn't be _that_ slow to traverse them.

That said, I don't love that loop. It would be better to do that whole 
cache_name_pos() call with the '/' simply appended to the path, and then 
we'd do the binary search directly to the first entry.

Of course, since 'path' is a 'const char *', we'd need to either do a 
silly copy, or we'd need to change a whole lot of the code to make it 
clear that we can actually add a slash to the end (which we can: I think 
it's already always going to be an array that we _will_ add a slash to in 
case it turns out to be a directory).

So there's definitely room for improvement there. I just think that the 
improvement isn't the patch you suggest.

			Linus

Re: [PATCH 4/3] Avoid using 'lstat()' to figure out directories

[Linus Torvalds]

On Thu, 9 Jul 2009, Linus Torvalds wrote:
>
> Of course, since 'path' is a 'const char *', we'd need to either do a 
> silly copy, or we'd need to change a whole lot of the code to make it 
> clear that we can actually add a slash to the end (which we can: I think 
> it's already always going to be an array that we _will_ add a slash to in 
> case it turns out to be a directory).

No, I was wrong. We really do give it an array that we can't change 
through the 'excluded()' function.

So we'd need to do the whole "copy name and add '/' at the end" thing. But 
the upside would then be that after that, we'd not need any looping to 
find the right ce. So it might be the right thing to do despite the 
extra copy.

			Linus

Re: [PATCH 4/3] Avoid using 'lstat()' to figure out directories

[Linus Torvalds]

On Thu, 9 Jul 2009, Linus Torvalds wrote:
> 
> So we'd need to do the whole "copy name and add '/' at the end" thing. But 
> the upside would then be that after that, we'd not need any looping to 
> find the right ce. So it might be the right thing to do despite the 
> extra copy.

Naah. I did the numbers. For any normal repository, the 'loop' is going to 
hit exactly once. Trying to be smarter about the initial binary search 
isn't going to help, and copying the pathname around is only going to 
hurt.

In the Linux repo, there's a small handful of cases like this, eg

 - "arch/x86/vdso32"
	arch/x86/vdso/vdso32-setup.c
	arch/x86/vdso/vdso32.S
	arch/x86/vdso/vdsp32/
 - "drivers/scsi/megaraid"
	drivers/scsi/megaraid.c
	drivers/scsi/megaraid.h
	drivers/scsi/megaraid/
 - "include/linux/i2c"
	include/linux/i2c-algo-bit.h
	include/linux/i2c-algo-pca.h
	include/linux/i2c-algo-pcf.h
	include/linux/i2c-dev.h
	include/linux/i2c-gpio.h
	include/linux/i2c-id.h
	include/linux/i2c-ocores.h
	include/linux/i2c-pca-platform.h
	include/linux/i2c-pnx.h
	include/linux/i2c-pxa.h
	include/linux/i2c.h
	include/linux/i2c/

etc (for a total of 45 cases in the whole kernel, if I did my script 
right), where we'd loop a few times. But we'd spend more effort trying to 
avoid looping than we spend now on the loop.

		Linus

Re: [PATCH 4/3] Avoid using 'lstat()' to figure out directories

[Junio C Hamano]

Paolo Bonzini <bonzini@gnu.org> writes:

>> +		if (ce->name[len]>  '/')
>> +			break;
>> +		if (ce->name[len]<  '/')
>> +			continue;
>
> What about
>
> 	if (ce->name[len] < '/') {
> 		if (strchr(ce->name + len + 1, '/'))
> 			break;
> 		else
> 			continue;
> 	}
>
> to just punt if we'd go into a directory?  I'm not much worried about
> accessing foo-0001, foo-0002, foo-0003 while looking for foo/a (that
> would be O(number of files in a directory), which is bearable), but
> risking to go down a huge subtree is not very nice.

I am not so sure about "go down" part.  After all, what the loop does is
to scan an array of pointers to cache entries and the "continue" causes
the loop to iterate until you find a path that is in the directory in
question.  It is all in userspace code walking on a flat namespace and
there is no "we are going down into a subdirectory and need to open
another directory node" kind of overhead associated with it.

How expensive is it to do this, compared to an lstat() on a system that
does not have dtype in "struct stat" (which means "lstat() is very cheap
on Linux" does not even get into the picture)?  IOW, how many cache
entries can we afford to check their names with strncmp, before the cost
of doing so gets more expensive than a single lstat() on say Cygwin?

I am hoping that the userland is userland and even on Windows it will run
at full CPU speed, while lstat() may need to pay penalty on Windows due to
POSIXy emulation layer, so the tradeoff might turn out to be that we can
afford to test quite many cache entries and still win if we can save a
single lstat().

Re: [PATCH 3/3] Avoid doing extra 'lstat()'s for d_type if we have an up-to-date cache entry

[Dmitry Potapov]

On Thu, Jul 09, 2009 at 09:32:03AM -0700, Junio C Hamano wrote:
> 
> Yeah, in Dmitry's response that crossed with this update patch from you,
> he says lstat() on directories are still problem---it would be interesting to
> hear what he sees after applying this patch and retesting.

With this patch, I see one 'stat' less for each directory, which on my
repo resulted in about 10.7% less 'stat' or 4.8% less of the total
number of syscalls. The total run time decreased by 4.6%.

Still, there are many stats for directories -- for each directory I see
2 + number of subdirectories it has, but I am not sure about its cause.

There is one strange thing though. Before that patch the number of
'open' for each directory was always the same in each run. But after
that patch, it slightly differs in each run... Comparing with results
without this patch, the number of open for some directories in some
be less by one... which is puzzling...


Dmitry

Re: [PATCH 3/3] Avoid doing extra 'lstat()'s for d_type if we have an up-to-date cache entry

[Eric Blake]

Dmitry Potapov <dpotapov <at> gmail.com> writes:

> With this patch, I see one 'stat' less for each directory, which on my
> repo resulted in about 10.7% less 'stat' or 4.8% less of the total
> number of syscalls. The total run time decreased by 4.6%.
> 
> Still, there are many stats for directories -- for each directory I see
> 2 + number of subdirectories it has, but I am not sure about its cause.

That would probably be the fact that in cygwin 1.5, a stat() of a directory
results in querying all the contents of the directory so as to correctly
populate the st_link member based on the number of subdirectories.  In cygwin
1.7, in addition to adding the d_type member to readdir, stat was also changed
to blindly return st_link of 1 for all directories rather than wasting time
populating the st_link member (since Windows provides no efficient way of
accessing that number).

-- 
Eric Blake

Re: [PATCH 3/3] Avoid doing extra 'lstat()'s for d_type if we have?an up-to-date cache entry

[Dmitry Potapov]

On Thu, Jul 09, 2009 at 09:52:24PM +0000, Eric Blake wrote:
> Dmitry Potapov <dpotapov <at> gmail.com> writes:
> 
> > With this patch, I see one 'stat' less for each directory, which on my
> > repo resulted in about 10.7% less 'stat' or 4.8% less of the total
> > number of syscalls. The total run time decreased by 4.6%.
> > 
> > Still, there are many stats for directories -- for each directory I see
> > 2 + number of subdirectories it has, but I am not sure about its cause.
> 
> That would probably be the fact that in cygwin 1.5, a stat() of a directory
> results in querying all the contents of the directory so as to correctly
> populate the st_link member based on the number of subdirectories.

We do not use lstat or fstat provided by Cygwin. Instead of it, we use
their fast and dirty analogues, which you can find in compat/cygwin.c
(they do not provide all information that normal functions provide, but
this information is sufficient for Git.

But we still use readdir() from Cygwin and that may be source of extra
syscalls that I observe...

Dmitry

Re: [PATCH 3/3] Avoid doing extra 'lstat()'s for d_type if we have?an up-to-date cache entry

[Dmitry Potapov]

On Fri, Jul 10, 2009 at 03:30:24AM +0400, Dmitry Potapov wrote:
> 
> But we still use readdir() from Cygwin and that may be source of extra
> syscalls that I observe...

opendir gives an extra 'stat' before opening directory
readdir produces one more extra 'stat' on the parent directory before
        returning '..'
open(.gitignore) does one extra 'stat' on the directory where it tries
        to open .gitignore (it did not exist in my tests)

So, the number of 'stat' on each directory is 2 plus the number of
subidectories that it has. Thus, the total number of 'stat' for all
directories is 3 multiple the number of directories in your repo. All
those 'stat' are artifacts of Cygwin. Also, you have 2 open per each
directory and one of them are redundant (at least, for Git purposes).
Overall (including syscalls for .gitignore), you have the following
number of syscalls for each directory in your repo:
  5 - QueryOpen (stat)
  3 - CreateFile (open)
  2 - CloseFile (close)
  1 - QueryFileInternalInformationFile

Here is the detail listing of testing of read_directory_recursive:
=====
opendir(.)
	QueryOpen,E:\dpotapov\repo
	CreateFile,E:\dpotapov\repo
first readdir call
	QueryDirectory,E:\dpotapov\repo
second readdir call that returns '..'
	QueryOpen,E:\dpotapov
	CreateFile,E:\dpotapov
	QueryFileInternalInformationFile,E:\dpotapov
	CloseFile,E:\dpotapov
open(.gitignore) -- .gitignore does not exist
	QueryOpen,E:\dpotapov\repo\.gitignore
	QueryOpen,E:\dpotapov\repo\.gitignore.lnk
	QueryOpen,E:\dpotapov\repo
	CreateFile,E:\dpotapov\repo\.gitignore
stat for untracked file
	QueryOpen,E:\dpotapov\repo\bar
opendir(dir1)
	QueryOpen,E:\dpotapov\repo\dir1
	CreateFile,E:\dpotapov\repo\dir1
first readdir call
	QueryDirectory,E:\dpotapov\repo\dir1
second readdir call that returns '..'
	QueryOpen,E:\dpotapov\repo
	CreateFile,E:\dpotapov\repo
	QueryFileInternalInformationFile,E:\dpotapov\repo
	CloseFile,E:\dpotapov\repo
open(.gitignore) -- .gitignore does not exist
	QueryOpen,E:\dpotapov\repo\dir1\.gitignore
	QueryOpen,E:\dpotapov\repo\dir1\.gitignore.lnk
	QueryOpen,E:\dpotapov\repo\dir1
	CreateFile,E:\dpotapov\repo\dir1\.gitignore
last readdir call that returns NULL
	QueryDirectory,E:\dpotapov\repo\dir1
closedir
	CloseFile,E:\dpotapov\repo\dir1
stat for some modified file
	QueryOpen,E:\dpotapov\repo\foo
last readdir call that returns NULL
	QueryDirectory,E:\dpotapov\repo
closedir
	CloseFile,E:\dpotapov\repo
=====

Dmitry

Re: [PATCH 3/3] Avoid doing extra 'lstat()'s for d_type if we have an up-to-date cache entry

[Dmitry Potapov]

On Fri, Jul 10, 2009 at 01:05:13AM +0400, Dmitry Potapov wrote:
> 
> There is one strange thing though. Before that patch the number of
> 'open' for each directory was always the same in each run. But after
> that patch, it slightly differs in each run... Comparing with results
> without this patch, the number of open for some directories in some
> be less by one... which is puzzling...

It appears that is a purely Windows thing... It seems extra opens for
directories inside of the working tree are caused by Windows Prefetcher.
http://en.wikipedia.org/wiki/Prefetcher

Accordingly to the Process Monitor, during start-up, it opens and reads
most directories in the repo that have subdirectories but sometimes it
skips some of them... So, the patch works as expected... Perhaps, I
should disable this prefetcher for testing to get more reproduceable
results. Anyway, this prefetecher does not issue QueryOpen (stat) for
files in the repo, so my numbers for 'stat' are not affected by it.


Dmitry

Re: [PATCH 3/3] Avoid doing extra 'lstat()'s for d_type if we have an up-to-date cache entry

[Dmitry Potapov]

On Wed, Jul 08, 2009 at 07:43:50PM -0700, Linus Torvalds wrote:
> 
> On filesystems without d_type, we can look at the cache entry first.
> Doing an lstat() can be expensive.
> 
> Reported by Dmitry Potapov for Cygwin.

I have tested it on Cygwin. The number of 'stat' for files is now 1, so
it works fine :)

I still have the same large number of 'stat' calls for directories, but I
suspect that due to that due to some Cygwin specific. I will investigate
that issue later when I have more time.

Because the repositoty on which I did testing has too many directories
(one directory per each 3.5 files) the effect was not as prominent as
it would be otherwise. Yet, it is 24.9% decrease of the number of 'stat'
or 14.8% descreased of the total number of syscalls. And my measurement
shows 14% descrease of run-time. So, it appears that on Windows the run
time almost directly proportional of the total number of syscalls...

BTW, I believe that this patch should help MinGW too, because AFAIK
MinGW does not have d_type either.


Thanks,
Dmitry