I have just started to clone some interesting Linux git trees to watch
the development more closely, and therefore also started to use git. I
noticed that 'git checkout' takes some time, and especially that the
'git checkout' command does lots and lots of lstat() calls.
After some more investigation and thinking, I have made 4 patches and
been able to optimise away over 42% of all lstat() calls in some cases
for the 'git checkout' command. I have not tested other git porcelain
commands for reduced lstat() calls, but I would guess that the more
effective 'lstat_cache()' compared to 'has_leading_symlink_cache()',
should also give better numbers in other cases.
All the 4 patches is against git master, and the git 'make test'
test suite still passes after each patch.
To document the improvement, below is some numbers, which compares
before and after all 4 patches. To reproduce the numbers:
- git clone the Linux git tree to be able to get the Linux tags
'v2.6.25' and 'v2.6.27'.
- git checkout -b my-v2.6.27 v2.6.27
- git checkout -b my-v2.6.25 v2.6.25
Then, when the current branch is 'my-v2.6.25' do:
strace -o strace_to27 -T git checkout -q my-v2.6.27
And then you pretty print and collect stats from the 'strace_to27'
file. If someone wants a copy of the strace_stat.pl script, which I
made/used to do the pretty printing, then give me a hint.
Below is the stats/numbers from the current git version (before the 4
patches). Notice that we do an lstat() call on the "arch" directory
over 6000 times!
TOTAL 185151 100.000% OK:165544 NOT: 19607 11.136001 sec 60 usec/call
lstat64 120954 65.327% OK:107013 NOT: 13941 5.388727 sec 45 usec/call
strings 120954 tot 30163 uniq 4.010 /uniq 5.388727 sec 45 usec/call
files 61491 tot 28712 uniq 2.142 /uniq 2.740520 sec 45 usec/call
dirs 45522 tot 1436 uniq 31.701 /uniq 1.994448 sec 44 usec/call
errors 13941 tot 5189 uniq 2.687 /uniq 0.653759 sec 47 usec/call
6297 5.206% OK: 6297 NOT: 0 "arch"
4544 3.757% OK: 4544 NOT: 0 "drivers"
1816 1.501% OK: 1816 NOT: 0 "arch/arm"
1499 1.239% OK: 1499 NOT: 0 "include"
912 0.754% OK: 912 NOT: 0 "arch/powerpc"
764 0.632% OK: 764 NOT: 0 "fs"
746 0.617% OK: 746 NOT: 0 "drivers/net"
662 0.547% OK: 662 NOT: 0 "net"
652 0.539% OK: 325 NOT: 327 "arch/sparc/include"
636 0.526% OK: 636 NOT: 0 "drivers/media"
606 0.501% OK: 606 NOT: 0 "include/linux"
533 0.441% OK: 533 NOT: 0 "arch/sh"
522 0.432% OK: 260 NOT: 262 "arch/powerpc/include"
488 0.403% OK: 243 NOT: 245 "arch/sh/include"
413 0.341% OK: 413 NOT: 0 "arch/sparc"
390 0.322% OK: 390 NOT: 0 "arch/x86"
383 0.317% OK: 383 NOT: 0 "Documentation"
370 0.306% OK: 184 NOT: 186 "arch/ia64/include"
366 0.303% OK: 366 NOT: 0 "drivers/media/video"
348 0.288% OK: 173 NOT: 175 "arch/arm/include"
Here is the stats/numbers after applying the 4 patches. Notice how
nice the top 20 entries list now looks!
TOTAL 133655 100.000% OK:121615 NOT: 12040 10.429999 sec 78 usec/call
lstat64 69603 52.077% OK: 63218 NOT: 6385 3.419920 sec 49 usec/call
strings 69603 tot 30163 uniq 2.308 /uniq 3.419920 sec 49 usec/call
files 61491 tot 28712 uniq 2.142 /uniq 3.034869 sec 49 usec/call
dirs 1727 tot 1164 uniq 1.484 /uniq 0.075681 sec 44 usec/call
errors 6385 tot 5189 uniq 1.230 /uniq 0.309370 sec 48 usec/call
4 0.006% OK: 4 NOT: 0 ".gitignore"
4 0.006% OK: 4 NOT: 0 ".mailmap"
4 0.006% OK: 4 NOT: 0 "CREDITS"
4 0.006% OK: 4 NOT: 0 "Documentation/00-INDEX"
4 0.006% OK: 4 NOT: 0 "Documentation/ABI/testing/sysfs-block"
4 0.006% OK: 4 NOT: 0 "Documentation/ABI/testing/sysfs-firmware-acpi"
4 0.006% OK: 4 NOT: 0 "Documentation/CodingStyle"
4 0.006% OK: 4 NOT: 0 "Documentation/DMA-API.txt"
4 0.006% OK: 4 NOT: 0 "Documentation/DMA-mapping.txt"
4 0.006% OK: 4 NOT: 0 "Documentation/DocBook/Makefile"
4 0.006% OK: 4 NOT: 0 "Documentation/DocBook/gadget.tmpl"
4 0.006% OK: 4 NOT: 0 "Documentation/DocBook/kernel-api.tmpl"
4 0.006% OK: 4 NOT: 0 "Documentation/DocBook/kernel-locking.tmpl"
4 0.006% OK: 4 NOT: 0 "Documentation/DocBook/procfs-guide.tmpl"
4 0.006% OK: 4 NOT: 0 "Documentation/DocBook/procfs_example.c"
4 0.006% OK: 4 NOT: 0 "Documentation/DocBook/rapidio.tmpl"
4 0.006% OK: 4 NOT: 0 "Documentation/DocBook/s390-drivers.tmpl"
4 0.006% OK: 4 NOT: 0 "Documentation/DocBook/uio-howto.tmpl"
4 0.006% OK: 4 NOT: 0 "Documentation/DocBook/videobook.tmpl"
4 0.006% OK: 4 NOT: 0 "Documentation/DocBook/writing_usb_driver.tmpl"
Note that the overall used system time as recorded from 'strace -T',
does not drop so much that the reduced lstat() time should indicate
for _this_ particular test run. This is because now each unlink()
call takes much more time, at least for me on an slow ide disk (using
ext3) on a laptop.
A simple test gives me an overall improvement of 2.937 seconds: real
time drops from 28.195s (best of 5 runs with 'time git ...'), to
25.381s (best of 5 runs).
Comments?
Kjetil Barvik (4):
Optimised, faster, more effective symlink/directory detection
Use 'lstat_cache()' instead of 'has_symlink_leading_path()'
create_directories() inside entry.c: only check each directory once!
remove the old 'has_symlink_leading_path()' function
Makefile | 2 +-
builtin-add.c | 5 ++-
builtin-apply.c | 5 ++-
builtin-update-index.c | 5 ++-
cache.h | 17 +++++++-
diff-lib.c | 5 ++-
dir.c | 4 +-
entry.c | 86 +++++++++++++++++++++++++++++++--------
lstat_cache.c | 105 ++++++++++++++++++++++++++++++++++++++++++++++++
symlinks.c | 64 -----------------------------
unpack-trees.c | 10 ++++-
11 files changed, 217 insertions(+), 91 deletions(-)
create mode 100644 lstat_cache.c
delete mode 100644 symlinks.c
This patch is work based on the following 2 commits:
Linus Torvalds: c40641b77b0274186fd1b327d5dc3246f814aaaf
Junio C Hamano: f859c846e90b385c7ef873df22403529208ade50
Changes includes the following:
- The cache functionality is more effective. Previously when A/B/C/D
was in the cache and A/B/C/E/file.c was called for, there was no
match at all from the cache. Now we use the fact that the paths
"A", "A/B" and "A/B/C" is already tested, and we only need to do an
lstat() call on "A/B/C/E".
- We only cache/store the last path regardless of it's type. Since the
cache functionality is always used with alphabetically sorted names
(at least it seams so for me), there is no need to store both the
last symlink-leading path and the last real-directory path. Note
that if the cache is not called with (mostly) alphabetically sorted
names, neither the old, nor this new one, would be very effective.
- We also can cache the fact that a directory does not exist.
Previously we could end up doing lots of lstat() calls for a removed
directory which previously contained lots of files. Since we
already have simplified the cache functionality and only store the
last path (see above), this new functionality was easy to add.
- Avoid copying the first path components of the name 2 zillions times
when we tests new path components. Since we always cache/store the
last path, we can copy each component as we test those directly into
the cache. Previously we ended up doing a memcpy() for the full
path/name right before each lstat() call, and when updating the
cache for each time we have tested an new path component.
- We also use less memory, that is PATH_MAX bytes less memory on the
stack and PATH_MAX bytes less memory on the heap.
- Introduce a 3rd argument, 'unsigned int track_flags', to the
cache-test function, check_lstat_cache(). This new argument can be
used to tell the cache functionality which types of directories
should be cached.
- Also introduce a 'void clear_lstat_cache(void)' function, which
should be used to clean the cache before usage. If for instance,
you have changed the types of directories which should be cached,
the cache could contain a path which was not wanted.
Signed-off-by: Kjetil Barvik <redacted>
---
:100644 100644 aabf013... 7449b10... M Makefile
:100644 100644 231c06d... 7c246a4... M cache.h
:000000 100644 0000000... 34f4e9a... A lstat_cache.c
Makefile | 1 +
cache.h | 15 ++++++++
lstat_cache.c | 105 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++
3 files changed, 121 insertions(+), 0 deletions(-)
create mode 100644 lstat_cache.c
@@ -0,0 +1,105 @@+#include"cache.h"++staticcharcache_path[PATH_MAX];+staticintcache_len=0;+staticunsignedintcache_flags=0;++staticinlineint+greatest_common_path_cache_prefix(intlen,constchar*name)+{+intmax_len,match_len=0,i=0;++max_len=len<cache_len?len:cache_len;+while(i<max_len&&name[i]==cache_path[i]){+if(name[i]=='/')match_len=i;+i++;+}+if(i==cache_len&&len>cache_len&&name[cache_len]=='/')+match_len=cache_len;+returnmatch_len;+}++staticinlinevoid+update_path_cache(unsignedintret_flags,unsignedinttrack_flags,+intlast_slash)+{+/* Max 3 different path types can be cached for the moment! */+unsignedintsave_flags=+ret_flags&track_flags&(LSTAT_DIR|+LSTAT_NOTDIR|+LSTAT_SYMLINK);+if(save_flags&&last_slash>0&&last_slash<PATH_MAX){+cache_flags=save_flags;+cache_len=last_slash;+}else{+cache_flags=0;+cache_len=0;+}+}++/*+*Checkifname'name'oflength'len'hasasymlinkleading+*component,orifthedirectoryexistsandisreal,ornot.+*+*Tospeedupthecheck,someinformationisallowedtobecached.+*Thisisindicatedbythe'track_flags'argument.+*/+unsignedint+check_lstat_cache(intlen,constchar*name,unsignedinttrack_flags)+{+intmatch_len,last_slash,max_len;+unsignedintmatch_flags,ret_flags;+structstatst;++/* Check if match from the cache for 2 "excluding" path types.+*/+match_len=last_slash=+greatest_common_path_cache_prefix(len,name);+match_flags=+cache_flags&track_flags&(LSTAT_NOTDIR|+LSTAT_SYMLINK);+if(match_flags&&match_len==cache_len)+returnmatch_flags;++/* Okay, no match from the cache so far, so now we have to+*checktherestofthepathcomponentsandupdatethecache.+*/+ret_flags=LSTAT_DIR;+max_len=len<PATH_MAX?len:PATH_MAX;+while(match_len<max_len){+do{+cache_path[match_len]=name[match_len];+match_len++;+}while(match_len<max_len&&name[match_len]!='/');+if(match_len>=max_len)+break;+last_slash=match_len;+cache_path[last_slash]='\0';++if(lstat(cache_path,&st)){+ret_flags=LSTAT_LSTATERR;+if(errno==ENOENT||errno==ENOTDIR)+ret_flags|=LSTAT_NOTDIR;+}elseif(S_ISDIR(st.st_mode)){+continue;+}elseif(S_ISLNK(st.st_mode)){+ret_flags=LSTAT_SYMLINK;+}else{+ret_flags=LSTAT_ERR;+}+break;+}+update_path_cache(ret_flags,track_flags,last_slash);+returnret_flags;+}++/*+*Beforeusageofthecheck_lstat_cache()functiononeshouldcall+*clear_lstat_cache()(atanappropriateplace)tomakesurethatthe+*cacheiscleanbeforefirstcalltocheck_lstat_cache().+*/+voidclear_lstat_cache(void)+{+cache_flags=0;+cache_len=0;+}
Start using the optimised, faster and more effective symlink/directory
cache. The previously used call:
has_symlink_leading_path(len, name);
should be identically with the following call to lstat_cache():
lstat_cache(len, name,
LSTAT_SYMLINK|LSTAT_DIR,
LSTAT_SYMLINK);
The primary reason for the new name of the function (instead of using
the old name and add 2 extra arguments), is that it is now more
general, for instance, it now also can cache the fact that a directory
does not exists.
I noticed that inside the unlink_entry() function in unpack-trees.c,
one could often end up calling rmdir() lots and lots of times on
none-empty directories. Maybe one should schedule each directory for
removal by an appropriate function, and then at the end call a new
function to clean all the directories at once?
Signed-off-by: Kjetil Barvik <redacted>
---
:100644 100644 719de8b... 152c52c... M builtin-add.c
:100644 100644 a8f75ed... 0eb2b21... M builtin-apply.c
:100644 100644 65d5775... fa7d994... M builtin-update-index.c
:100644 100644 ae96c64... 127bdf2... M diff-lib.c
:100644 100644 0131983... 9f2a1b1... M dir.c
:100644 100644 54f301d... 93923db... M unpack-trees.c
builtin-add.c | 5 ++++-
builtin-apply.c | 5 ++++-
builtin-update-index.c | 5 ++++-
diff-lib.c | 5 ++++-
dir.c | 4 +++-
unpack-trees.c | 9 +++++++--
6 files changed, 26 insertions(+), 7 deletions(-)
@@ -2354,7 +2354,9 @@ static int check_to_create_blob(const char *new_name, int ok_if_exists)*Insuchacase,path"new_name"doesnotexistas*farasgitisconcerned.*/-if(has_symlink_leading_path(strlen(new_name),new_name))+if(lstat_cache(strlen(new_name),new_name,+LSTAT_SYMLINK|LSTAT_DIR,+LSTAT_SYMLINK))return0;returnerror("%s: already exists in working directory",new_name);
@@ -195,7 +195,9 @@ static int process_path(const char *path)structstatst;len=strlen(path);-if(has_symlink_leading_path(len,path))+if(lstat_cache(len,path,+LSTAT_SYMLINK|LSTAT_DIR,+LSTAT_SYMLINK))returnerror("'%s' is beyond a symbolic link",path);/*
When we do an 'git checkout' after some time we end up in the
'checkout_entry()' function inside entry.c, and from here we call the
'create_directories()' function to make sure the all the directories
exists for the possible new file or entry.
The 'create_directories()' function happily started to check that all
path component exists. This resulted in tons and tons of calls to
lstat() or stat() when we checkout files nested deep inside a
directory.
We try to avoid this by remembering the last checked and possible
newly created directory.
Signed-off-by: Kjetil Barvik <redacted>
---
:100644 100644 7c246a4... 8d0228c... M cache.h
:100644 100644 aa2ee46... 666a8ce... M entry.c
:100644 100644 93923db... 7a2219d... M unpack-trees.c
cache.h | 1 +
entry.c | 86 ++++++++++++++++++++++++++++++++++++++++++++------------
unpack-trees.c | 1 +
3 files changed, 70 insertions(+), 18 deletions(-)
@@ -1,33 +1,76 @@#include"cache.h"#include"blob.h"-staticvoidcreate_directories(constchar*path,conststructcheckout*state)+staticchardirs_path[PATH_MAX];+staticintdirs_len=0;++staticinlineint+greatest_common_created_dirs_prefix(intlen,constchar*name){-intlen=strlen(path);-char*buf=xmalloc(len+1);-constchar*slash=path;+intmax_len,match_len=0,i=0;-while((slash=strchr(slash+1,'/'))!=NULL){-structstatst;-intstat_status;+max_len=len<dirs_len?len:dirs_len;+while(i<max_len&&name[i]==dirs_path[i]){+if(name[i]=='/')match_len=i;+i++;+}+if(i==dirs_len&&len>dirs_len&&name[dirs_len]=='/')+match_len=dirs_len;+returnmatch_len;+}++staticinlinevoid+update_created_dirs_cache(intlast_slash)+{+if(last_slash>0&&last_slash<PATH_MAX){+dirs_len=last_slash;+}else{+dirs_len=0;+}+}-len=slash-path;-memcpy(buf,path,len);-buf[len]=0;+voidclear_created_dirs_cache(void)+{+dirs_len=0;+}++staticvoid+create_directories(intlen,constchar*path,conststructcheckout*state)+{+inti,max_len,last_slash,stat_status;+structstatst;++/* Check the cache for previously checked or created+*directories(andcomponents)withinthisfunction.There+*isnoneedtocheckorre-createdirectorycomponentsmore+*thanonce!+*/+max_len=len<PATH_MAX?len:PATH_MAX;+i=last_slash=greatest_common_created_dirs_prefix(max_len,path);-if(len<=state->base_dir_len)+while(i<max_len){+do{+dirs_path[i]=path[i];+i++;+}while(i<max_len&&path[i]!='/');+if(i>=max_len)+break;+last_slash=i;+dirs_path[last_slash]='\0';++if(last_slash<=state->base_dir_len)/**checkout-index--prefix=<dir>;<dir>is*allowedtobeasymlinktoanexisting*directory.*/-stat_status=stat(buf,&st);+stat_status=stat(dirs_path,&st);else/**iftherecurrentlyisasymlink,wewould*wanttoreplaceitwitharealdirectory.*/-stat_status=lstat(buf,&st);+stat_status=lstat(dirs_path,&st);if(!stat_status&&S_ISDIR(st.st_mode))continue;/* ok, it is already a directory. */
@@ -55,6 +98,11 @@ static void remove_subtree(const char *path)charpathbuf[PATH_MAX];char*name;+/* To be utterly safe we invalidate the cache of the+*previouslycreateddirectories.+*/+clear_created_dirs_cache();+if(!dir)die("cannot opendir %s (%s)",path,strerror(errno));strcpy(pathbuf,path);
From: Junio C Hamano <hidden> Date: 2016-06-15 22:45:52
Kjetil Barvik [off-list ref] writes:
Start using the optimised, faster and more effective symlink/directory
cache. The previously used call:
has_symlink_leading_path(len, name);
should be identically with the following call to lstat_cache():
lstat_cache(len, name,
LSTAT_SYMLINK|LSTAT_DIR,
LSTAT_SYMLINK);
...
Care to enlighten why some of callers use the above, but not others?
Namely, check_removed() in diff-lib.c and callers in unpack-trees.c care
about NOTDIR unlike others, even though the original code checked for
exactly the same condition.
Does this mean that some callers of has_symlink_leading_path() checked
only for leading symlinks when they should also have checked for a leading
non-directory, and this patch is also a bugfix?
From: Junio C Hamano <hidden> Date: 2016-06-15 22:45:52
Kjetil Barvik [off-list ref] writes:
+static inline void
+update_path_cache(unsigned int ret_flags, unsigned int track_flags,
+ int last_slash)
+{
+ /* Max 3 different path types can be cached for the moment! */
+ unsigned int save_flags =
+ ret_flags & track_flags & (LSTAT_DIR|
+ LSTAT_NOTDIR|
+ LSTAT_SYMLINK);
+ if (save_flags && last_slash > 0 && last_slash < PATH_MAX) {
+ cache_flags = save_flags;
+ cache_len = last_slash;
+ } else {
+ cache_flags = 0;
+ cache_len = 0;
+ }
+}
I personally found this inline function with a single call site
distracting in following the logic. It does not make the indentation
level shallower, either. Also, the else part should probably call
clear_lstat_cache() to protect it from possible future enhancements to add
more state variables.
+
+/*
+ * Check if name 'name' of length 'len' has a symlink leading
+ * component, or if the directory exists and is real, or not.
+ *
+ * To speed up the check, some information is allowed to be cached.
+ * This is indicated by the 'track_flags' argument.
+ */
+unsigned int
+check_lstat_cache(int len, const char *name, unsigned int track_flags)
+{
+ int match_len, last_slash, max_len;
+ unsigned int match_flags, ret_flags;
+ struct stat st;
+
+ /* Check if match from the cache for 2 "excluding" path types.
+ */
+ match_len = last_slash =
+ greatest_common_path_cache_prefix(len, name);
+ match_flags =
+ cache_flags & track_flags & (LSTAT_NOTDIR|
+ LSTAT_SYMLINK);
+ if (match_flags && match_len == cache_len)
+ return match_flags;
Let me see if I understand the logic behind this caching. When you have
checked A/B/C earlier and you already know B is a symlink, you remember
that A/B was a symlink.. You can fill a request to check A/B/$whatever
(assuming A/B does not change --- otherwise the caller should clear the
cache) from the cached data, because no matter what $whatever is, it will
result in the same "has-leading-symlink".
Similarly, if you know A/B is not a directory from an earlier test, you
know that a request to check A/B/$whatever will result in the same ENOTDIR
no matter what $whatever is, so you can return early.
The above "return match_flags" will not trigger if the cached path does
not have any leading symlink. So we know the matched part are all good
directories when we start lstat() loop.
Am I following you so far?
+ /* Okay, no match from the cache so far, so now we have to
+ * check the rest of the path components and update the cache.
+ */
+ ret_flags = LSTAT_DIR;
+ max_len = len < PATH_MAX ? len : PATH_MAX;
+ while (match_len < max_len) {
+ do {
+ cache_path[match_len] = name[match_len];
+ match_len++;
+ } while (match_len < max_len && name[match_len] != '/');
You take one component from the input, and append it to the part that is
already known to be true directory (i.e. cached part and the part earlier
iteration of the loop checked so far), to be tested by lstat()...
+ if (match_len >= max_len)
+ break;
... but you are not interested in the full input. We are only checking
the leading path (e.g. check for "A/B/C" may lstat() "A", "A/B" but not
"A/B/C").
If you tested "A/B" here and got ENOENT back, you know "A/B" does not
exist; you cache this knowledge as "A/B is not a directory" (I also think
you could use it as a cached knowledge that "A exists and is a directory".
I am not sure if you are taking advantage of that).
What I do not understand about this code is the ENOTDIR case. If you
tested "A/B" and got ENOTDIR back, what you know is that "A" is not a
directory (if the path tested this round were deeper like "X/Y/A/B", you
know "X/Y/A" is not a directory, and you know "X" and "X/Y" are true
directories; otherwise the loop would have exited before this round when
you tested "X" or "X/Y" in the earlier rounds).
So as far as I can think of, ENOENT case and ENOTDIR case would give you
different information (ENOENT would say "A is a dir, A/B is not"; ENOTDIR
would say "A is not a dir"). I am confused how you can cache the same
path and same flag between these two cases here.
+ } else if (S_ISDIR(st.st_mode)) {
+ continue;
+ } else if (S_ISLNK(st.st_mode)) {
+ ret_flags = LSTAT_SYMLINK;
+ } else {
+ ret_flags = LSTAT_ERR;
+ }
+ break;
+ }
+ update_path_cache(ret_flags, track_flags, last_slash);
+ return ret_flags;
+}
+
+/*
+ * Before usage of the check_lstat_cache() function one should call
+ * clear_lstat_cache() (at an appropriate place) to make sure that the
+ * cache is clean before first call to check_lstat_cache().
+ */
+void clear_lstat_cache(void)
+{
+ cache_flags = 0;
+ cache_len = 0;
+}
--
1.6.1.rc1.49.g7f705
+static inline void
+update_path_cache(unsigned int ret_flags, unsigned int track_flags,
+ int last_slash)
+{
+ /* Max 3 different path types can be cached for the moment! */
+ unsigned int save_flags =
+ ret_flags & track_flags & (LSTAT_DIR|
+ LSTAT_NOTDIR|
+ LSTAT_SYMLINK);
+ if (save_flags && last_slash > 0 && last_slash < PATH_MAX) {
+ cache_flags = save_flags;
+ cache_len = last_slash;
+ } else {
+ cache_flags = 0;
+ cache_len = 0;
+ }
+}
I personally found this inline function with a single call site
distracting in following the logic. It does not make the indentation
level shallower, either. Also, the else part should probably call
clear_lstat_cache() to protect it from possible future enhancements to add
more state variables.
Ok, I will remove the function and update the else-part.
quoted
+
+/*
+ * Check if name 'name' of length 'len' has a symlink leading
+ * component, or if the directory exists and is real, or not.
+ *
+ * To speed up the check, some information is allowed to be cached.
+ * This is indicated by the 'track_flags' argument.
+ */
+unsigned int
+check_lstat_cache(int len, const char *name, unsigned int track_flags)
+{
+ int match_len, last_slash, max_len;
+ unsigned int match_flags, ret_flags;
+ struct stat st;
+
+ /* Check if match from the cache for 2 "excluding" path types.
+ */
+ match_len = last_slash =
+ greatest_common_path_cache_prefix(len, name);
+ match_flags =
+ cache_flags & track_flags & (LSTAT_NOTDIR|
+ LSTAT_SYMLINK);
+ if (match_flags && match_len == cache_len)
+ return match_flags;
Let me see if I understand the logic behind this caching. When you have
checked A/B/C earlier and you already know B is a symlink, you remember
that A/B was a symlink.. You can fill a request to check A/B/$whatever
(assuming A/B does not change --- otherwise the caller should clear the
cache) from the cached data, because no matter what $whatever is, it will
result in the same "has-leading-symlink".
Similarly, if you know A/B is not a directory from an earlier test, you
know that a request to check A/B/$whatever will result in the same ENOTDIR
no matter what $whatever is, so you can return early.
The above "return match_flags" will not trigger if the cached path does
not have any leading symlink. So we know the matched part are all good
directories when we start lstat() loop.
Am I following you so far?
Yes you do!
quoted
+ /* Okay, no match from the cache so far, so now we have to
+ * check the rest of the path components and update the cache.
+ */
+ ret_flags = LSTAT_DIR;
+ max_len = len < PATH_MAX ? len : PATH_MAX;
+ while (match_len < max_len) {
+ do {
+ cache_path[match_len] = name[match_len];
+ match_len++;
+ } while (match_len < max_len && name[match_len] != '/');
You take one component from the input, and append it to the part that is
already known to be true directory (i.e. cached part and the part earlier
iteration of the loop checked so far), to be tested by lstat()...
quoted
+ if (match_len >= max_len)
+ break;
... but you are not interested in the full input.
If the lengt of name is larger than PATH_MAX all lstat() calls would
fail with an ENAMETOOLONG error, at least on my Linux box, so I
thought that it was not nessarry to test further. But maybe we should
emdiatly return an error if name is too long?
We are only checking the leading path (e.g. check for "A/B/C" may
lstat() "A", "A/B" but not "A/B/C").
That is correct, and it is the same logic as in the
has_symlink_leading_path() function.
If you tested "A/B" here and got ENOENT back, you know "A/B" does not
exist; you cache this knowledge as "A/B is not a directory"
Correct.
(I also think you could use it as a cached knowledge that "A exists
and is a directory". I am not sure if you are taking advantage of
that).
It does take adavantage of this fact. It will also do simmilar things
with a symlink cached path.
What I do not understand about this code is the ENOTDIR case. If you
tested "A/B" and got ENOTDIR back, what you know is that "A" is not a
directory (if the path tested this round were deeper like "X/Y/A/B", you
know "X/Y/A" is not a directory, and you know "X" and "X/Y" are true
directories; otherwise the loop would have exited before this round when
you tested "X" or "X/Y" in the earlier rounds).
Since the cache is supoosed to start from a known existing directory,
and is testing each path component when the lstat("A/B") calls returns
ENOTDIR, we should know the fact that the directory "A" exists, and
that "A/B/" does not exists.
So as far as I can think of, ENOENT case and ENOTDIR case would give you
different information (ENOENT would say "A is a dir, A/B is not"; ENOTDIR
would say "A is not a dir"). I am confused how you can cache the same
path and same flag between these two cases here.
I admit that I used copy-and-paste from other similar test's from the
sourcecode:
kjetil@localhost ~/git/git $ grep -Hn ENOENT.*ENOTDIR *.c
builtin-apply.c:2364: else if ((errno != ENOENT) && (errno != ENOTDIR))
builtin-update-index.c:74: * - missing file (ENOENT or ENOTDIR). That's ok if we're
builtin-update-index.c:81: if (err == ENOENT || err == ENOTDIR)
diff-lib.c:30: if (errno != ENOENT && errno != ENOTDIR)
lstat_cache.c:81: if (errno == ENOENT || errno == ENOTDIR)
setup.c:191: if (errno != ENOENT && errno != ENOTDIR)
From the 'man lstat' page I read the following for this 2 error codes:
ENOENT A component of the path _path_ does not exist, or the path is an empty string.
ENOTDIR A component of the path is not a directory.
I would have guessed that for what we is looking for, it would be
correct to threat both these error codes as the same. Is this wrong?
-- kjetil
Start using the optimised, faster and more effective symlink/directory
cache. The previously used call:
has_symlink_leading_path(len, name);
should be identically with the following call to lstat_cache():
lstat_cache(len, name,
LSTAT_SYMLINK|LSTAT_DIR,
LSTAT_SYMLINK);
...
Care to enlighten why some of callers use the above, but not others?
Namely, check_removed() in diff-lib.c
I though that first it would be a good thing to introduce as little
changes as possible, and then later on do some cleanups. Regarding
the 'check_removed()' function, I though that it could later have been
written something like this after cleanups:
[....]
static int check_removed(const struct cache_entry *ce, struct stat *st)
{
unsigned int ret_flags =
check_lstat_cache(ce_namelen(ce), ce->name,
LSTAT_SYMLINK|LSTAT_NOTDIR|LSTAT_DIR);
if (ret_flags & (LSTAT_SYMLINK|LSTAT_NOTDIR))
return 1;
if (ret_flags & LSTAT_LSTATERR)
return -1;
if (ret_flags & LSTAT_DIR) {
unsigned char sub[20];
[....]
This would have saved one more lstat() call in some cases. But after
a test, I now see that it does not work. The reason is that it does
not set the 'struct stat *st' parameter and/or that for the moment you
can not tell the 'lstat_cache()' function to also always test the last
path component. It could be extended to do this, if someone ask for
it and if it would be useful to extend the lstat_cache() for this
fact.
I will remove the '|LSTAT_NOTDIR' part from the call to lstat_cache()
in 'check_removed()' in the next version of the patch.
and callers in unpack-trees.c care about NOTDIR unlike others, even
though the original code checked for exactly the same condition.
Regarding the 'verify_absent()' function in unpack-trees.c, the
'|LSTAT_NOTDIR' part of the call to lstat_cache() helps to avoid 16047
lstat() calls for the given test case mentioned in the cover-letter.
And from the source code:
[...]
if (lstat_cache(ce_namelen(ce), ce->name,
LSTAT_SYMLINK|LSTAT_NOTDIR|LSTAT_DIR,
LSTAT_SYMLINK|LSTAT_NOTDIR))
return 0;
if (!lstat(ce->name, &st)) {
[...]
it should be easy to see that if we from the lstat_cache() could
already spot that some path component of ce->name does not exists,
then we can avoid the following lstat() call, as it then should known
to be failing.
regarding the 'unlink_entry()' function in unpack-trees.c, the
'|LSTAT_NOTDIR' part of the call to lstat_cache() does not for the
moment helps to avoid any lstat() calls, as far as I can see. But,
again, from the source code:
[..]
char *name = ce->name;
if (lstat_cache(ce_namelen(ce), ce->name,
LSTAT_SYMLINK|LSTAT_NOTDIR|LSTAT_DIR,
LSTAT_SYMLINK|LSTAT_NOTDIR))
return;
if (unlink(name))
return;
[...]
it should be correct, since if we already know that some path
component of ce-name does not exist, the call to unlink(name) would
always fail (with ENOENT).
Does this mean that some callers of has_symlink_leading_path() checked
only for leading symlinks when they should also have checked for a leading
non-directory, and this patch is also a bugfix?
Yes, as indicated above, has_symlink_leading_path() should have
checked for leading non-directories when called from for the
'verify_absent()' function to be able to optimise away some more
lstat() calls.
I admit that I do not know the source code good enough to decide if
this is an indication of a bug somewhere, or just an optimisation.
-- kjetil