{"thread":{"id":"16993","subject":"[PATCH/RFC 0/4] git checkout: optimise away lots of lstat() calls","startedAt":"2009-01-05T13:09:57Z","lastAt":"2009-01-06T13:45:56Z","messageCount":12,"participants":["Kjetil Barvik","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":4},"messages":[{"id":"99356","messageId":"1231161001-32599-1-git-send-email-barvik@broadpark.no","threadId":"16993","inReplyTo":null,"subject":"[PATCH/RFC 0/4] git checkout: optimise away lots of lstat() calls","fromName":"Kjetil Barvik","fromEmail":"barvik@broadpark.no","sentAt":"2009-01-05T13:09:57Z","receivedAt":"2009-01-05T13:09:57Z","isPatch":true,"sender":{"key":"barvik@broadpark.no","avatar":null},"body":"I have just started to clone some interesting Linux git trees to watch\nthe development more closely, and therefore also started to use git. I\nnoticed that 'git checkout' takes some time, and especially that the\n'git checkout' command does lots and lots of lstat() calls.\n\nAfter some more investigation and thinking, I have made 4 patches and\nbeen able to optimise away over 42% of all lstat() calls in some cases\nfor the 'git checkout' command.  I have not tested other git porcelain\ncommands for reduced lstat() calls, but I would guess that the more\neffective 'lstat_cache()' compared to 'has_leading_symlink_cache()',\nshould also give better numbers in other cases.\n\nAll the 4 patches is against git master, and the git 'make test'\ntest suite still passes after each patch.\n\nTo document the improvement, below is some numbers, which compares\nbefore and after all 4 patches. To reproduce the numbers:\n\n- git clone the Linux git tree to be able to get the Linux tags\n  'v2.6.25' and 'v2.6.27'.\n- git checkout -b my-v2.6.27 v2.6.27\n- git checkout -b my-v2.6.25 v2.6.25\n\nThen, when the current branch is 'my-v2.6.25' do:\n\n  strace -o strace_to27 -T git checkout -q my-v2.6.27\n\nAnd then you pretty print and collect stats from the 'strace_to27'\nfile.  If someone wants a copy of the strace_stat.pl script, which I\nmade/used to do the pretty printing, then give me a hint.\n\nBelow is the stats/numbers from the current git version (before the 4\npatches).  Notice that we do an lstat() call on the \"arch\" directory\nover 6000 times!\n\nTOTAL      185151 100.000% OK:165544 NOT: 19607  11.136001 sec   60 usec/call\nlstat64    120954  65.327% OK:107013 NOT: 13941   5.388727 sec   45 usec/call\n  strings  120954 tot  30163 uniq   4.010 /uniq   5.388727 sec   45 usec/call\n  files     61491 tot  28712 uniq   2.142 /uniq   2.740520 sec   45 usec/call\n  dirs      45522 tot   1436 uniq  31.701 /uniq   1.994448 sec   44 usec/call\n  errors    13941 tot   5189 uniq   2.687 /uniq   0.653759 sec   47 usec/call\n             6297   5.206% OK:  6297 NOT:     0  \"arch\"\n             4544   3.757% OK:  4544 NOT:     0  \"drivers\"\n             1816   1.501% OK:  1816 NOT:     0  \"arch/arm\"\n             1499   1.239% OK:  1499 NOT:     0  \"include\"\n              912   0.754% OK:   912 NOT:     0  \"arch/powerpc\"\n              764   0.632% OK:   764 NOT:     0  \"fs\"\n              746   0.617% OK:   746 NOT:     0  \"drivers/net\"\n              662   0.547% OK:   662 NOT:     0  \"net\"\n              652   0.539% OK:   325 NOT:   327  \"arch/sparc/include\"\n              636   0.526% OK:   636 NOT:     0  \"drivers/media\"\n              606   0.501% OK:   606 NOT:     0  \"include/linux\"\n              533   0.441% OK:   533 NOT:     0  \"arch/sh\"\n              522   0.432% OK:   260 NOT:   262  \"arch/powerpc/include\"\n              488   0.403% OK:   243 NOT:   245  \"arch/sh/include\"\n              413   0.341% OK:   413 NOT:     0  \"arch/sparc\"\n              390   0.322% OK:   390 NOT:     0  \"arch/x86\"\n              383   0.317% OK:   383 NOT:     0  \"Documentation\"\n              370   0.306% OK:   184 NOT:   186  \"arch/ia64/include\"\n              366   0.303% OK:   366 NOT:     0  \"drivers/media/video\"\n              348   0.288% OK:   173 NOT:   175  \"arch/arm/include\"\n\nHere is the stats/numbers after applying the 4 patches.  Notice how\nnice the top 20 entries list now looks!\n\nTOTAL      133655 100.000% OK:121615 NOT: 12040  10.429999 sec   78 usec/call\nlstat64     69603  52.077% OK: 63218 NOT:  6385   3.419920 sec   49 usec/call\n  strings   69603 tot  30163 uniq   2.308 /uniq   3.419920 sec   49 usec/call\n  files     61491 tot  28712 uniq   2.142 /uniq   3.034869 sec   49 usec/call\n  dirs       1727 tot   1164 uniq   1.484 /uniq   0.075681 sec   44 usec/call\n  errors     6385 tot   5189 uniq   1.230 /uniq   0.309370 sec   48 usec/call\n                4   0.006% OK:     4 NOT:     0  \".gitignore\"\n                4   0.006% OK:     4 NOT:     0  \".mailmap\"\n                4   0.006% OK:     4 NOT:     0  \"CREDITS\"\n                4   0.006% OK:     4 NOT:     0  \"Documentation/00-INDEX\"\n                4   0.006% OK:     4 NOT:     0  \"Documentation/ABI/testing/sysfs-block\"\n                4   0.006% OK:     4 NOT:     0  \"Documentation/ABI/testing/sysfs-firmware-acpi\"\n                4   0.006% OK:     4 NOT:     0  \"Documentation/CodingStyle\"\n                4   0.006% OK:     4 NOT:     0  \"Documentation/DMA-API.txt\"\n                4   0.006% OK:     4 NOT:     0  \"Documentation/DMA-mapping.txt\"\n                4   0.006% OK:     4 NOT:     0  \"Documentation/DocBook/Makefile\"\n                4   0.006% OK:     4 NOT:     0  \"Documentation/DocBook/gadget.tmpl\"\n                4   0.006% OK:     4 NOT:     0  \"Documentation/DocBook/kernel-api.tmpl\"\n                4   0.006% OK:     4 NOT:     0  \"Documentation/DocBook/kernel-locking.tmpl\"\n                4   0.006% OK:     4 NOT:     0  \"Documentation/DocBook/procfs-guide.tmpl\"\n                4   0.006% OK:     4 NOT:     0  \"Documentation/DocBook/procfs_example.c\"\n                4   0.006% OK:     4 NOT:     0  \"Documentation/DocBook/rapidio.tmpl\"\n                4   0.006% OK:     4 NOT:     0  \"Documentation/DocBook/s390-drivers.tmpl\"\n                4   0.006% OK:     4 NOT:     0  \"Documentation/DocBook/uio-howto.tmpl\"\n                4   0.006% OK:     4 NOT:     0  \"Documentation/DocBook/videobook.tmpl\"\n                4   0.006% OK:     4 NOT:     0  \"Documentation/DocBook/writing_usb_driver.tmpl\"\n\nNote that the overall used system time as recorded from 'strace -T',\ndoes not drop so much that the reduced lstat() time should indicate\nfor _this_ particular test run.  This is because now each unlink()\ncall takes much more time, at least for me on an slow ide disk (using\next3) on a laptop.\n\nA simple test gives me an overall improvement of 2.937 seconds: real\ntime drops from 28.195s (best of 5 runs with 'time git ...'), to\n25.381s (best of 5 runs).\n\nComments?\n\nKjetil Barvik (4):\n  Optimised, faster, more effective symlink/directory detection\n  Use 'lstat_cache()' instead of 'has_symlink_leading_path()'\n  create_directories() inside entry.c: only check each directory once!\n  remove the old 'has_symlink_leading_path()' function\n\n Makefile               |    2 +-\n builtin-add.c          |    5 ++-\n builtin-apply.c        |    5 ++-\n builtin-update-index.c |    5 ++-\n cache.h                |   17 +++++++-\n diff-lib.c             |    5 ++-\n dir.c                  |    4 +-\n entry.c                |   86 +++++++++++++++++++++++++++++++--------\n lstat_cache.c          |  105 ++++++++++++++++++++++++++++++++++++++++++++++++\n symlinks.c             |   64 -----------------------------\n unpack-trees.c         |   10 ++++-\n 11 files changed, 217 insertions(+), 91 deletions(-)\n create mode 100644 lstat_cache.c\n delete mode 100644 symlinks.c\n"},{"id":"99357","messageId":"1231161001-32599-2-git-send-email-barvik@broadpark.no","threadId":"16993","inReplyTo":"1231161001-32599-1-git-send-email-barvik@broadpark.no","subject":"[PATCH/RFC 1/4] Optimised, faster, more effective symlink/directory detection","fromName":"Kjetil Barvik","fromEmail":"barvik@broadpark.no","sentAt":"2009-01-05T13:09:58Z","receivedAt":"2009-01-05T13:09:58Z","isPatch":true,"sender":{"key":"barvik@broadpark.no","avatar":null},"body":"This patch is work based on the following 2 commits:\n\nLinus Torvalds: c40641b77b0274186fd1b327d5dc3246f814aaaf\nJunio C Hamano: f859c846e90b385c7ef873df22403529208ade50\n\nChanges includes the following:\n\n- The cache functionality is more effective.  Previously when A/B/C/D\n  was in the cache and A/B/C/E/file.c was called for, there was no\n  match at all from the cache.  Now we use the fact that the paths\n  \"A\", \"A/B\" and \"A/B/C\" is already tested, and we only need to do an\n  lstat() call on \"A/B/C/E\".\n\n- We only cache/store the last path regardless of it's type.  Since the\n  cache functionality is always used with alphabetically sorted names\n  (at least it seams so for me), there is no need to store both the\n  last symlink-leading path and the last real-directory path.  Note\n  that if the cache is not called with (mostly) alphabetically sorted\n  names, neither the old, nor this new one, would be very effective.\n\n- We also can cache the fact that a directory does not exist.\n  Previously we could end up doing lots of lstat() calls for a removed\n  directory which previously contained lots of files.  Since we\n  already have simplified the cache functionality and only store the\n  last path (see above), this new functionality was easy to add.\n\n- Avoid copying the first path components of the name 2 zillions times\n  when we tests new path components.  Since we always cache/store the\n  last path, we can copy each component as we test those directly into\n  the cache.  Previously we ended up doing a memcpy() for the full\n  path/name right before each lstat() call, and when updating the\n  cache for each time we have tested an new path component.\n\n- We also use less memory, that is PATH_MAX bytes less memory on the\n  stack and PATH_MAX bytes less memory on the heap.\n\n- Introduce a 3rd argument, 'unsigned int track_flags', to the\n  cache-test function, check_lstat_cache().  This new argument can be\n  used to tell the cache functionality which types of directories\n  should be cached.\n\n- Also introduce a 'void clear_lstat_cache(void)' function, which\n  should be used to clean the cache before usage.  If for instance,\n  you have changed the types of directories which should be cached,\n  the cache could contain a path which was not wanted.\n\nSigned-off-by: Kjetil Barvik <barvik@broadpark.no>\n---\n:100644 100644 aabf013... 7449b10... M\tMakefile\n:100644 100644 231c06d... 7c246a4... M\tcache.h\n:000000 100644 0000000... 34f4e9a... A\tlstat_cache.c\n Makefile      |    1 +\n cache.h       |   15 ++++++++\n lstat_cache.c |  105 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++\n 3 files changed, 121 insertions(+), 0 deletions(-)\n create mode 100644 lstat_cache.c\n\ndiff --git a/Makefile b/Makefile\nindex aabf0130b99bee5204c8e668ba8f40caea77dae2..7449b105b03e862d53244d50ed035b4ddabef028 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -446,6 +446,7 @@ LIB_OBJS += list-objects.o\n LIB_OBJS += ll-merge.o\n LIB_OBJS += lockfile.o\n LIB_OBJS += log-tree.o\n+LIB_OBJS += lstat_cache.o\n LIB_OBJS += mailmap.o\n LIB_OBJS += match-trees.o\n LIB_OBJS += merge-file.o\ndiff --git a/cache.h b/cache.h\nindex 231c06d7726b575f6e522d5b0c0fe43557e8c651..7c246a42df3d60ac2c0f7431ff29ee8fb70235ce 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -721,6 +721,21 @@ struct checkout {\n extern int checkout_entry(struct cache_entry *ce, const struct checkout *state, char *topath);\n extern int has_symlink_leading_path(int len, const char *name);\n \n+#define LSTAT_DIR       (1u << 0)\n+#define LSTAT_NOTDIR    (1u << 1)\n+#define LSTAT_SYMLINK   (1u << 2)\n+#define LSTAT_LSTATERR  (1u << 3)\n+#define LSTAT_ERR       (1u << 4)\n+extern unsigned int check_lstat_cache(int len, const char *name,\n+\t\t\t\t      unsigned int track_flags);\n+static inline unsigned int lstat_cache(int len, const char *name,\n+\t\t\t\t       unsigned int track_flags,\n+\t\t\t\t       unsigned int mask_flags)\n+{\n+\treturn check_lstat_cache(len, name, track_flags) & mask_flags;\n+}\n+extern void clear_lstat_cache(void);\n+\n extern struct alternate_object_database {\n \tstruct alternate_object_database *next;\n \tchar *name;\ndiff --git a/lstat_cache.c b/lstat_cache.c\nnew file mode 100644\nindex 0000000000000000000000000000000000000000..34f4e9a003905323f45a4f739d2a354e02dbbe93\n--- /dev/null\n+++ b/lstat_cache.c\n@@ -0,0 +1,105 @@\n+#include \"cache.h\"\n+\n+static char         cache_path[PATH_MAX];\n+static int          cache_len   = 0;\n+static unsigned int cache_flags = 0;\n+\n+static inline int\n+greatest_common_path_cache_prefix(int len, const char *name)\n+{\n+\tint max_len, match_len = 0, i = 0;\n+\n+\tmax_len = len < cache_len ? len : cache_len;\n+\twhile (i < max_len && name[i] == cache_path[i]) {\n+\t\tif (name[i] == '/') match_len = i;\n+\t\ti++;\n+\t}\n+\tif (i == cache_len && len > cache_len && name[cache_len] == '/')\n+\t\tmatch_len = cache_len;\n+\treturn match_len;\n+}\n+\n+static inline void\n+update_path_cache(unsigned int ret_flags, unsigned int track_flags,\n+\t\t  int last_slash)\n+{\n+\t/* Max 3 different path types can be cached for the moment! */\n+\tunsigned int save_flags =\n+\t\tret_flags & track_flags & (LSTAT_DIR|\n+\t\t\t\t\t   LSTAT_NOTDIR|\n+\t\t\t\t\t   LSTAT_SYMLINK);\n+\tif (save_flags && last_slash > 0 && last_slash < PATH_MAX) {\n+\t\tcache_flags = save_flags;\n+\t\tcache_len   = last_slash;\n+\t} else {\n+\t\tcache_flags = 0;\n+\t\tcache_len   = 0;\n+\t}\n+}\n+\n+/*\n+ * Check if name 'name' of length 'len' has a symlink leading\n+ * component, or if the directory exists and is real, or not.\n+ *\n+ * To speed up the check, some information is allowed to be cached.\n+ * This is indicated by the 'track_flags' argument.\n+ */\n+unsigned int\n+check_lstat_cache(int len, const char *name, unsigned int track_flags)\n+{\n+\tint match_len, last_slash, max_len;\n+\tunsigned int match_flags, ret_flags;\n+\tstruct stat st;\n+\n+\t/* Check if match from the cache for 2 \"excluding\" path types.\n+\t */\n+\tmatch_len = last_slash =\n+\t\tgreatest_common_path_cache_prefix(len, name);\n+\tmatch_flags =\n+\t\tcache_flags & track_flags & (LSTAT_NOTDIR|\n+\t\t\t\t\t     LSTAT_SYMLINK);\n+\tif (match_flags && match_len == cache_len)\n+\t\treturn match_flags;\n+\n+\t/* Okay, no match from the cache so far, so now we have to\n+\t * check the rest of the path components and update the cache.\n+\t */\n+\tret_flags = LSTAT_DIR;\n+\tmax_len = len < PATH_MAX ? len : PATH_MAX;\n+\twhile (match_len < max_len) {\n+\t\tdo {\n+\t\t\tcache_path[match_len] = name[match_len];\n+\t\t\tmatch_len++;\n+\t\t} while (match_len < max_len && name[match_len] != '/');\n+\t\tif (match_len >= max_len)\n+\t\t\tbreak;\n+\t\tlast_slash = match_len;\n+\t\tcache_path[last_slash] = '\\0';\n+\n+\t\tif (lstat(cache_path, &st)) {\n+\t\t\tret_flags = LSTAT_LSTATERR;\n+\t\t\tif (errno == ENOENT || errno == ENOTDIR)\n+\t\t\t\tret_flags |= LSTAT_NOTDIR;\n+\t\t} else if (S_ISDIR(st.st_mode)) {\n+\t\t\tcontinue;\n+\t\t} else if (S_ISLNK(st.st_mode)) {\n+\t\t\tret_flags = LSTAT_SYMLINK;\n+\t\t} else {\n+\t\t\tret_flags = LSTAT_ERR;\n+\t\t}\n+\t\tbreak;\n+\t}\n+\tupdate_path_cache(ret_flags, track_flags, last_slash);\n+\treturn ret_flags;\n+}\n+\n+/*\n+ * Before usage of the check_lstat_cache() function one should call\n+ * clear_lstat_cache() (at an appropriate place) to make sure that the\n+ * cache is clean before first call to check_lstat_cache().\n+ */\n+void clear_lstat_cache(void)\n+{\n+\tcache_flags = 0;\n+\tcache_len   = 0;\n+}\n-- \n1.6.1.rc1.49.g7f705\n"},{"id":"99358","messageId":"1231161001-32599-3-git-send-email-barvik@broadpark.no","threadId":"16993","inReplyTo":"1231161001-32599-1-git-send-email-barvik@broadpark.no","subject":"[PATCH/RFC 2/4] Use 'lstat_cache()' instead of 'has_symlink_leading_path()'","fromName":"Kjetil Barvik","fromEmail":"barvik@broadpark.no","sentAt":"2009-01-05T13:09:59Z","receivedAt":"2009-01-05T13:09:59Z","isPatch":true,"sender":{"key":"barvik@broadpark.no","avatar":null},"body":"Start using the optimised, faster and more effective symlink/directory\ncache.  The previously used call:\n\n   has_symlink_leading_path(len, name);\n\nshould be identically with the following call to lstat_cache():\n\n   lstat_cache(len, name,\n               LSTAT_SYMLINK|LSTAT_DIR,\n               LSTAT_SYMLINK);\n\nThe primary reason for the new name of the function (instead of using\nthe old name and add 2 extra arguments), is that it is now more\ngeneral, for instance, it now also can cache the fact that a directory\ndoes not exists.\n\nI noticed that inside the unlink_entry() function in unpack-trees.c,\none could often end up calling rmdir() lots and lots of times on\nnone-empty directories.  Maybe one should schedule each directory for\nremoval by an appropriate function, and then at the end call a new\nfunction to clean all the directories at once?\n\nSigned-off-by: Kjetil Barvik <barvik@broadpark.no>\n---\n:100644 100644 719de8b... 152c52c... M\tbuiltin-add.c\n:100644 100644 a8f75ed... 0eb2b21... M\tbuiltin-apply.c\n:100644 100644 65d5775... fa7d994... M\tbuiltin-update-index.c\n:100644 100644 ae96c64... 127bdf2... M\tdiff-lib.c\n:100644 100644 0131983... 9f2a1b1... M\tdir.c\n:100644 100644 54f301d... 93923db... M\tunpack-trees.c\n builtin-add.c          |    5 ++++-\n builtin-apply.c        |    5 ++++-\n builtin-update-index.c |    5 ++++-\n diff-lib.c             |    5 ++++-\n dir.c                  |    4 +++-\n unpack-trees.c         |    9 +++++++--\n 6 files changed, 26 insertions(+), 7 deletions(-)\n\ndiff --git a/builtin-add.c b/builtin-add.c\nindex 719de8b0f2d2d831f326d948aa18700e5c474950..152c52c0f22b3e71931b2a5629e1472602817785 100644\n--- a/builtin-add.c\n+++ b/builtin-add.c\n@@ -121,7 +121,9 @@ static const char **validate_pathspec(int argc, const char **argv, const char *p\n \tif (pathspec) {\n \t\tconst char **p;\n \t\tfor (p = pathspec; *p; p++) {\n-\t\t\tif (has_symlink_leading_path(strlen(*p), *p)) {\n+\t\t\tif (lstat_cache(strlen(*p), *p,\n+\t\t\t\t\tLSTAT_SYMLINK|LSTAT_DIR,\n+\t\t\t\t\tLSTAT_SYMLINK)) {\n \t\t\t\tint len = prefix ? strlen(prefix) : 0;\n \t\t\t\tdie(\"'%s' is beyond a symbolic link\", *p + len);\n \t\t\t}\n@@ -225,6 +227,7 @@ int cmd_add(int argc, const char **argv, const char *prefix)\n \n \targc = parse_options(argc, argv, builtin_add_options,\n \t\t\t  builtin_add_usage, 0);\n+\tclear_lstat_cache();\n \tif (patch_interactive)\n \t\tadd_interactive = 1;\n \tif (add_interactive)\ndiff --git a/builtin-apply.c b/builtin-apply.c\nindex a8f75ed3ed411d8cf7a3ec9dfefef7407c50f447..0eb2b21ee245919189c780a64cc494ca35f7934a 100644\n--- a/builtin-apply.c\n+++ b/builtin-apply.c\n@@ -2354,7 +2354,9 @@ static int check_to_create_blob(const char *new_name, int ok_if_exists)\n \t\t * In such a case, path \"new_name\" does not exist as\n \t\t * far as git is concerned.\n \t\t */\n-\t\tif (has_symlink_leading_path(strlen(new_name), new_name))\n+\t\tif (lstat_cache(strlen(new_name), new_name,\n+\t\t\t\tLSTAT_SYMLINK|LSTAT_DIR,\n+\t\t\t\tLSTAT_SYMLINK))\n \t\t\treturn 0;\n \n \t\treturn error(\"%s: already exists in working directory\", new_name);\n@@ -3154,6 +3156,7 @@ int cmd_apply(int argc, const char **argv, const char *unused_prefix)\n \tif (apply_default_whitespace)\n \t\tparse_whitespace_option(apply_default_whitespace);\n \n+\tclear_lstat_cache();\n \tfor (i = 1; i < argc; i++) {\n \t\tconst char *arg = argv[i];\n \t\tchar *end;\ndiff --git a/builtin-update-index.c b/builtin-update-index.c\nindex 65d5775107f9013526cc5b288a80a00b449e8814..fa7d994b3cfe7343c1a181f4c6f6a4c6ee6cea75 100644\n--- a/builtin-update-index.c\n+++ b/builtin-update-index.c\n@@ -195,7 +195,9 @@ static int process_path(const char *path)\n \tstruct stat st;\n \n \tlen = strlen(path);\n-\tif (has_symlink_leading_path(len, path))\n+\tif (lstat_cache(len, path,\n+\t\t\tLSTAT_SYMLINK|LSTAT_DIR,\n+\t\t\tLSTAT_SYMLINK))\n \t\treturn error(\"'%s' is beyond a symbolic link\", path);\n \n \t/*\n@@ -581,6 +583,7 @@ int cmd_update_index(int argc, const char **argv, const char *prefix)\n \tif (entries < 0)\n \t\tdie(\"cache corrupted\");\n \n+\tclear_lstat_cache();\n \tfor (i = 1 ; i < argc; i++) {\n \t\tconst char *path = argv[i];\n \t\tconst char *p;\ndiff --git a/diff-lib.c b/diff-lib.c\nindex ae96c64ca209f4df9008198e8a04b160bed618c7..127bdf2dfbeb3538fa01e500ed8bcd3f4c8d422b 100644\n--- a/diff-lib.c\n+++ b/diff-lib.c\n@@ -31,7 +31,9 @@ static int check_removed(const struct cache_entry *ce, struct stat *st)\n \t\t\treturn -1;\n \t\treturn 1;\n \t}\n-\tif (has_symlink_leading_path(ce_namelen(ce), ce->name))\n+\tif (lstat_cache(ce_namelen(ce), ce->name,\n+\t\t\tLSTAT_SYMLINK|LSTAT_NOTDIR|LSTAT_DIR,\n+\t\t\tLSTAT_SYMLINK))\n \t\treturn 1;\n \tif (S_ISDIR(st->st_mode)) {\n \t\tunsigned char sub[20];\n@@ -69,6 +71,7 @@ int run_diff_files(struct rev_info *revs, unsigned int option)\n \t\tdiff_unmerged_stage = 2;\n \tentries = active_nr;\n \tsymcache[0] = '\\0';\n+\tclear_lstat_cache();\n \tfor (i = 0; i < entries; i++) {\n \t\tstruct stat st;\n \t\tunsigned int oldmode, newmode;\ndiff --git a/dir.c b/dir.c\nindex 0131983dfbc143ce5dae77e067663bb2e7d5f126..9f2a1b1f245c3f1d4f12d54d45bb193c53fa15b5 100644\n--- a/dir.c\n+++ b/dir.c\n@@ -719,7 +719,9 @@ int read_directory(struct dir_struct *dir, const char *path, const char *base, i\n {\n \tstruct path_simplify *simplify;\n \n-\tif (has_symlink_leading_path(strlen(path), path))\n+\tif (lstat_cache(strlen(path), path,\n+\t\t\tLSTAT_SYMLINK|LSTAT_DIR,\n+\t\t\tLSTAT_SYMLINK))\n \t\treturn dir->nr;\n \n \tsimplify = create_simplify(pathspec);\ndiff --git a/unpack-trees.c b/unpack-trees.c\nindex 54f301da67be879c80426bc21776427fdd38c02e..93923dbbc6ab80deadfd737aa9975f6e5a4d1e89 100644\n--- a/unpack-trees.c\n+++ b/unpack-trees.c\n@@ -61,7 +61,9 @@ static void unlink_entry(struct cache_entry *ce)\n \tchar *cp, *prev;\n \tchar *name = ce->name;\n \n-\tif (has_symlink_leading_path(ce_namelen(ce), ce->name))\n+\tif (lstat_cache(ce_namelen(ce), ce->name,\n+\t\t\tLSTAT_SYMLINK|LSTAT_NOTDIR|LSTAT_DIR,\n+\t\t\tLSTAT_SYMLINK|LSTAT_NOTDIR))\n \t\treturn;\n \tif (unlink(name))\n \t\treturn;\n@@ -105,6 +107,7 @@ static int check_updates(struct unpack_trees_options *o)\n \t\tcnt = 0;\n \t}\n \n+\tclear_lstat_cache();\n \tfor (i = 0; i < index->cache_nr; i++) {\n \t\tstruct cache_entry *ce = index->cache[i];\n \n@@ -584,7 +587,9 @@ static int verify_absent(struct cache_entry *ce, const char *action,\n \tif (o->index_only || o->reset || !o->update)\n \t\treturn 0;\n \n-\tif (has_symlink_leading_path(ce_namelen(ce), ce->name))\n+\tif (lstat_cache(ce_namelen(ce), ce->name,\n+\t\t\tLSTAT_SYMLINK|LSTAT_NOTDIR|LSTAT_DIR,\n+\t\t\tLSTAT_SYMLINK|LSTAT_NOTDIR))\n \t\treturn 0;\n \n \tif (!lstat(ce->name, &st)) {\n-- \n1.6.1.rc1.49.g7f705\n"},{"id":"99359","messageId":"1231161001-32599-4-git-send-email-barvik@broadpark.no","threadId":"16993","inReplyTo":"1231161001-32599-1-git-send-email-barvik@broadpark.no","subject":"[PATCH/RFC 3/4] create_directories() inside entry.c: only check each directory once!","fromName":"Kjetil Barvik","fromEmail":"barvik@broadpark.no","sentAt":"2009-01-05T13:10:00Z","receivedAt":"2009-01-05T13:10:00Z","isPatch":true,"sender":{"key":"barvik@broadpark.no","avatar":null},"body":"When we do an 'git checkout' after some time we end up in the\n'checkout_entry()' function inside entry.c, and from here we call the\n'create_directories()' function to make sure the all the directories\nexists for the possible new file or entry.\n\nThe 'create_directories()' function happily started to check that all\npath component exists.  This resulted in tons and tons of calls to\nlstat() or stat() when we checkout files nested deep inside a\ndirectory.\n\nWe try to avoid this by remembering the last checked and possible\nnewly created directory.\n\nSigned-off-by: Kjetil Barvik <barvik@broadpark.no>\n---\n:100644 100644 7c246a4... 8d0228c... M\tcache.h\n:100644 100644 aa2ee46... 666a8ce... M\tentry.c\n:100644 100644 93923db... 7a2219d... M\tunpack-trees.c\n cache.h        |    1 +\n entry.c        |   86 ++++++++++++++++++++++++++++++++++++++++++++------------\n unpack-trees.c |    1 +\n 3 files changed, 70 insertions(+), 18 deletions(-)\n\ndiff --git a/cache.h b/cache.h\nindex 7c246a42df3d60ac2c0f7431ff29ee8fb70235ce..8d0228c857ab9d8e31585ad5aa6838403adef3a2 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -718,6 +718,7 @@ struct checkout {\n \t\t refresh_cache:1;\n };\n \n+extern void clear_created_dirs_cache(void);\n extern int checkout_entry(struct cache_entry *ce, const struct checkout *state, char *topath);\n extern int has_symlink_leading_path(int len, const char *name);\n \ndiff --git a/entry.c b/entry.c\nindex aa2ee46a84033585d8e07a585610c5a697af82c2..666a8ce3a132e85a45b0828521f3c2119c77833e 100644\n--- a/entry.c\n+++ b/entry.c\n@@ -1,33 +1,76 @@\n #include \"cache.h\"\n #include \"blob.h\"\n \n-static void create_directories(const char *path, const struct checkout *state)\n+static char dirs_path[PATH_MAX];\n+static int  dirs_len = 0;\n+\n+static inline int\n+greatest_common_created_dirs_prefix(int len, const char *name)\n {\n-\tint len = strlen(path);\n-\tchar *buf = xmalloc(len + 1);\n-\tconst char *slash = path;\n+\tint max_len, match_len = 0, i = 0;\n \n-\twhile ((slash = strchr(slash+1, '/')) != NULL) {\n-\t\tstruct stat st;\n-\t\tint stat_status;\n+\tmax_len = len < dirs_len ? len : dirs_len;\n+\twhile (i < max_len && name[i] == dirs_path[i]) {\n+\t\tif (name[i] == '/') match_len = i;\n+\t\ti++;\n+\t}\n+\tif (i == dirs_len && len > dirs_len && name[dirs_len] == '/')\n+\t\tmatch_len = dirs_len;\n+\treturn match_len;\n+}\n+\n+static inline void\n+update_created_dirs_cache(int last_slash)\n+{\n+\tif (last_slash > 0 && last_slash < PATH_MAX) {\n+\t\tdirs_len = last_slash;\n+\t} else {\n+\t\tdirs_len = 0;\n+\t}\n+}\n \n-\t\tlen = slash - path;\n-\t\tmemcpy(buf, path, len);\n-\t\tbuf[len] = 0;\n+void clear_created_dirs_cache(void)\n+{\n+\tdirs_len = 0;\n+}\n+\n+static void\n+create_directories(int len, const char *path, const struct checkout *state)\n+{\n+\tint i, max_len, last_slash, stat_status;\n+\tstruct stat st;\n+\n+\t/* Check the cache for previously checked or created\n+\t * directories (and components) within this function.  There\n+\t * is no need to check or re-create directory components more\n+\t * than once!\n+\t */\n+\tmax_len = len < PATH_MAX ? len : PATH_MAX;\n+\ti = last_slash = greatest_common_created_dirs_prefix(max_len, path);\n \n-\t\tif (len <= state->base_dir_len)\n+\twhile (i < max_len) {\n+\t\tdo {\n+\t\t\tdirs_path[i] = path[i];\n+\t\t\ti++;\n+\t\t} while (i < max_len && path[i] != '/');\n+\t\tif (i >= max_len)\n+\t\t\tbreak;\n+\t\tlast_slash = i;\n+\t\tdirs_path[last_slash] = '\\0';\n+\n+\t\tif (last_slash <= state->base_dir_len)\n \t\t\t/*\n \t\t\t * checkout-index --prefix=<dir>; <dir> is\n \t\t\t * allowed to be a symlink to an existing\n \t\t\t * directory.\n \t\t\t */\n-\t\t\tstat_status = stat(buf, &st);\n+\t\t\tstat_status = stat(dirs_path, &st);\n \t\telse\n \t\t\t/*\n \t\t\t * if there currently is a symlink, we would\n \t\t\t * want to replace it with a real directory.\n \t\t\t */\n-\t\t\tstat_status = lstat(buf, &st);\n+\t\t\tstat_status = lstat(dirs_path, &st);\n \n \t\tif (!stat_status && S_ISDIR(st.st_mode))\n \t\t\tcontinue; /* ok, it is already a directory. */\n@@ -38,14 +81,14 @@ static void create_directories(const char *path, const struct checkout *state)\n \t\t * error codepath; we do not care, as we unlink and\n \t\t * mkdir again in such a case.\n \t\t */\n-\t\tif (mkdir(buf, 0777)) {\n+\t\tif (mkdir(dirs_path, 0777)) {\n \t\t\tif (errno == EEXIST && state->force &&\n-\t\t\t    !unlink(buf) && !mkdir(buf, 0777))\n+\t\t\t    !unlink(dirs_path) && !mkdir(dirs_path, 0777))\n \t\t\t\tcontinue;\n-\t\t\tdie(\"cannot create directory at %s\", buf);\n+\t\t\tdie(\"cannot create directory at %s\", dirs_path);\n \t\t}\n \t}\n-\tfree(buf);\n+\tupdate_created_dirs_cache(last_slash);\n }\n \n static void remove_subtree(const char *path)\n@@ -55,6 +98,11 @@ static void remove_subtree(const char *path)\n \tchar pathbuf[PATH_MAX];\n \tchar *name;\n \n+\t/* To be utterly safe we invalidate the cache of the\n+\t * previously created directories.\n+\t */\n+\tclear_created_dirs_cache();\n+\n \tif (!dir)\n \t\tdie(\"cannot opendir %s (%s)\", path, strerror(errno));\n \tstrcpy(pathbuf, path);\n@@ -195,12 +243,14 @@ int checkout_entry(struct cache_entry *ce, const struct checkout *state, char *t\n \tstatic char path[PATH_MAX + 1];\n \tstruct stat st;\n \tint len = state->base_dir_len;\n+\tint path_len;\n \n \tif (topath)\n \t\treturn write_entry(ce, topath, state, 1);\n \n \tmemcpy(path, state->base_dir, len);\n \tstrcpy(path + len, ce->name);\n+\tpath_len = len + ce_namelen(ce);\n \n \tif (!lstat(path, &st)) {\n \t\tunsigned changed = ce_match_stat(ce, &st, CE_MATCH_IGNORE_VALID);\n@@ -229,6 +279,6 @@ int checkout_entry(struct cache_entry *ce, const struct checkout *state, char *t\n \t\t\treturn error(\"unable to unlink old '%s' (%s)\", path, strerror(errno));\n \t} else if (state->not_new)\n \t\treturn 0;\n-\tcreate_directories(path, state);\n+\tcreate_directories(path_len, path, state);\n \treturn write_entry(ce, path, state, 0);\n }\ndiff --git a/unpack-trees.c b/unpack-trees.c\nindex 93923dbbc6ab80deadfd737aa9975f6e5a4d1e89..7a2219d14d19b80e67c01d051e57c341f60f455c 100644\n--- a/unpack-trees.c\n+++ b/unpack-trees.c\n@@ -121,6 +121,7 @@ static int check_updates(struct unpack_trees_options *o)\n \t\t}\n \t}\n \n+\tclear_created_dirs_cache();\n \tfor (i = 0; i < index->cache_nr; i++) {\n \t\tstruct cache_entry *ce = index->cache[i];\n \n-- \n1.6.1.rc1.49.g7f705\n"},{"id":"99360","messageId":"1231161001-32599-5-git-send-email-barvik@broadpark.no","threadId":"16993","inReplyTo":"1231161001-32599-1-git-send-email-barvik@broadpark.no","subject":"[PATCH/RFC 4/4] remove the old 'has_symlink_leading_path()' function","fromName":"Kjetil Barvik","fromEmail":"barvik@broadpark.no","sentAt":"2009-01-05T13:10:01Z","receivedAt":"2009-01-05T13:10:01Z","isPatch":true,"sender":{"key":"barvik@broadpark.no","avatar":null},"body":"It has been replaced by the more cache effective 'lstat_cache()'\nfunction.  see lstat_cache.c\n\nSigned-off-by: Kjetil Barvik <barvik@broadpark.no>\n---\n:100644 100644 7449b10... edd4798... M\tMakefile\n:100644 100644 8d0228c... dc5c383... M\tcache.h\n:100644 000000 5a5e781... 0000000... D\tsymlinks.c\n Makefile   |    1 -\n cache.h    |    1 -\n symlinks.c |   64 ------------------------------------------------------------\n 3 files changed, 0 insertions(+), 66 deletions(-)\n delete mode 100644 symlinks.c\n\ndiff --git a/Makefile b/Makefile\nindex 7449b105b03e862d53244d50ed035b4ddabef028..edd4798429ad3828f5b9dcff20f73c6a7269520e 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -483,7 +483,6 @@ LIB_OBJS += sha1_name.o\n LIB_OBJS += shallow.o\n LIB_OBJS += sideband.o\n LIB_OBJS += strbuf.o\n-LIB_OBJS += symlinks.o\n LIB_OBJS += tag.o\n LIB_OBJS += trace.o\n LIB_OBJS += transport.o\ndiff --git a/cache.h b/cache.h\nindex 8d0228c857ab9d8e31585ad5aa6838403adef3a2..dc5c3833d789a6012f9ce05522c8840f01ddc027 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -720,7 +720,6 @@ struct checkout {\n \n extern void clear_created_dirs_cache(void);\n extern int checkout_entry(struct cache_entry *ce, const struct checkout *state, char *topath);\n-extern int has_symlink_leading_path(int len, const char *name);\n \n #define LSTAT_DIR       (1u << 0)\n #define LSTAT_NOTDIR    (1u << 1)\ndiff --git a/symlinks.c b/symlinks.c\ndeleted file mode 100644\nindex 5a5e781a15d7d9cb60797958433eca896b31ec85..0000000000000000000000000000000000000000\n--- a/symlinks.c\n+++ /dev/null\n@@ -1,64 +0,0 @@\n-#include \"cache.h\"\n-\n-struct pathname {\n-\tint len;\n-\tchar path[PATH_MAX];\n-};\n-\n-/* Return matching pathname prefix length, or zero if not matching */\n-static inline int match_pathname(int len, const char *name, struct pathname *match)\n-{\n-\tint match_len = match->len;\n-\treturn (len > match_len &&\n-\t\tname[match_len] == '/' &&\n-\t\t!memcmp(name, match->path, match_len)) ? match_len : 0;\n-}\n-\n-static inline void set_pathname(int len, const char *name, struct pathname *match)\n-{\n-\tif (len < PATH_MAX) {\n-\t\tmatch->len = len;\n-\t\tmemcpy(match->path, name, len);\n-\t\tmatch->path[len] = 0;\n-\t}\n-}\n-\n-int has_symlink_leading_path(int len, const char *name)\n-{\n-\tstatic struct pathname link, nonlink;\n-\tchar path[PATH_MAX];\n-\tstruct stat st;\n-\tchar *sp;\n-\tint known_dir;\n-\n-\t/*\n-\t * See if the last known symlink cache matches.\n-\t */\n-\tif (match_pathname(len, name, &link))\n-\t\treturn 1;\n-\n-\t/*\n-\t * Get rid of the last known directory part\n-\t */\n-\tknown_dir = match_pathname(len, name, &nonlink);\n-\n-\twhile ((sp = strchr(name + known_dir + 1, '/')) != NULL) {\n-\t\tint thislen = sp - name ;\n-\t\tmemcpy(path, name, thislen);\n-\t\tpath[thislen] = 0;\n-\n-\t\tif (lstat(path, &st))\n-\t\t\treturn 0;\n-\t\tif (S_ISDIR(st.st_mode)) {\n-\t\t\tset_pathname(thislen, path, &nonlink);\n-\t\t\tknown_dir = thislen;\n-\t\t\tcontinue;\n-\t\t}\n-\t\tif (S_ISLNK(st.st_mode)) {\n-\t\t\tset_pathname(thislen, path, &link);\n-\t\t\treturn 1;\n-\t\t}\n-\t\tbreak;\n-\t}\n-\treturn 0;\n-}\n-- \n1.6.1.rc1.49.g7f705\n"},{"id":"99445","messageId":"7vprj0j181.fsf@gitster.siamese.dyndns.org","threadId":"16993","inReplyTo":"1231161001-32599-2-git-send-email-barvik@broadpark.no","subject":"Re: [PATCH/RFC 1/4] Optimised, faster, more effective symlink/directory detection","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2009-01-06T08:19:26Z","receivedAt":"2009-01-06T08:19:26Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Kjetil Barvik <barvik@broadpark.no> writes:\n\n> +static inline void\n> +update_path_cache(unsigned int ret_flags, unsigned int track_flags,\n> +\t\t  int last_slash)\n> +{\n> +\t/* Max 3 different path types can be cached for the moment! */\n> +\tunsigned int save_flags =\n> +\t\tret_flags & track_flags & (LSTAT_DIR|\n> +\t\t\t\t\t   LSTAT_NOTDIR|\n> +\t\t\t\t\t   LSTAT_SYMLINK);\n> +\tif (save_flags && last_slash > 0 && last_slash < PATH_MAX) {\n> +\t\tcache_flags = save_flags;\n> +\t\tcache_len   = last_slash;\n> +\t} else {\n> +\t\tcache_flags = 0;\n> +\t\tcache_len   = 0;\n> +\t}\n> +}\n\nI personally found this inline function with a single call site\ndistracting in following the logic.  It does not make the indentation\nlevel shallower, either.  Also, the else part should probably call\nclear_lstat_cache() to protect it from possible future enhancements to add\nmore state variables.\n\n> +\n> +/*\n> + * Check if name 'name' of length 'len' has a symlink leading\n> + * component, or if the directory exists and is real, or not.\n> + *\n> + * To speed up the check, some information is allowed to be cached.\n> + * This is indicated by the 'track_flags' argument.\n> + */\n> +unsigned int\n> +check_lstat_cache(int len, const char *name, unsigned int track_flags)\n> +{\n> +\tint match_len, last_slash, max_len;\n> +\tunsigned int match_flags, ret_flags;\n> +\tstruct stat st;\n> +\n> +\t/* Check if match from the cache for 2 \"excluding\" path types.\n> +\t */\n> +\tmatch_len = last_slash =\n> +\t\tgreatest_common_path_cache_prefix(len, name);\n> +\tmatch_flags =\n> +\t\tcache_flags & track_flags & (LSTAT_NOTDIR|\n> +\t\t\t\t\t     LSTAT_SYMLINK);\n> +\tif (match_flags && match_len == cache_len)\n> +\t\treturn match_flags;\n\nLet me see if I understand the logic behind this caching.  When you have\nchecked A/B/C earlier and you already know B is a symlink, you remember\nthat A/B was a symlink..  You can fill a request to check A/B/$whatever\n(assuming A/B does not change --- otherwise the caller should clear the\ncache) from the cached data, because no matter what $whatever is, it will\nresult in the same \"has-leading-symlink\".\n\nSimilarly, if you know A/B is not a directory from an earlier test, you\nknow that a request to check A/B/$whatever will result in the same ENOTDIR\nno matter what $whatever is, so you can return early.\n\nThe above \"return match_flags\" will not trigger if the cached path does\nnot have any leading symlink.  So we know the matched part are all good\ndirectories when we start lstat() loop.\n\nAm I following you so far?\n\n> +\t/* Okay, no match from the cache so far, so now we have to\n> +\t * check the rest of the path components and update the cache.\n> +\t */\n> +\tret_flags = LSTAT_DIR;\n> +\tmax_len = len < PATH_MAX ? len : PATH_MAX;\n> +\twhile (match_len < max_len) {\n> +\t\tdo {\n> +\t\t\tcache_path[match_len] = name[match_len];\n> +\t\t\tmatch_len++;\n> +\t\t} while (match_len < max_len && name[match_len] != '/');\n\nYou take one component from the input, and append it to the part that is\nalready known to be true directory (i.e. cached part and the part earlier\niteration of the loop checked so far), to be tested by lstat()...\n\n> +\t\tif (match_len >= max_len)\n> +\t\t\tbreak;\n\n... but you are not interested in the full input.  We are only checking\nthe leading path (e.g. check for \"A/B/C\" may lstat() \"A\", \"A/B\" but not\n\"A/B/C\").\n\n> +\t\tlast_slash = match_len;\n> +\t\tcache_path[last_slash] = '\\0';\n> +\n> +\t\tif (lstat(cache_path, &st)) {\n> +\t\t\tret_flags = LSTAT_LSTATERR;\n> +\t\t\tif (errno == ENOENT || errno == ENOTDIR)\n> +\t\t\t\tret_flags |= LSTAT_NOTDIR;\n\nIf you tested \"A/B\" here and got ENOENT back, you know \"A/B\" does not\nexist; you cache this knowledge as \"A/B is not a directory\" (I also think\nyou could use it as a cached knowledge that \"A exists and is a directory\".\nI am not sure if you are taking advantage of that).\n\nWhat I do not understand about this code is the ENOTDIR case.  If you\ntested \"A/B\" and got ENOTDIR back, what you know is that \"A\" is not a\ndirectory (if the path tested this round were deeper like \"X/Y/A/B\", you\nknow \"X/Y/A\" is not a directory, and you know \"X\" and \"X/Y\" are true\ndirectories; otherwise the loop would have exited before this round when\nyou tested \"X\" or \"X/Y\" in the earlier rounds).\n\nSo as far as I can think of, ENOENT case and ENOTDIR case would give you\ndifferent information (ENOENT would say \"A is a dir, A/B is not\"; ENOTDIR\nwould say \"A is not a dir\").  I am confused how you can cache the same\npath and same flag between these two cases here.\n\n> +\t\t} else if (S_ISDIR(st.st_mode)) {\n> +\t\t\tcontinue;\n> +\t\t} else if (S_ISLNK(st.st_mode)) {\n> +\t\t\tret_flags = LSTAT_SYMLINK;\n> +\t\t} else {\n> +\t\t\tret_flags = LSTAT_ERR;\n> +\t\t}\n> +\t\tbreak;\n> +\t}\n> +\tupdate_path_cache(ret_flags, track_flags, last_slash);\n> +\treturn ret_flags;\n> +}\n> +\n> +/*\n> + * Before usage of the check_lstat_cache() function one should call\n> + * clear_lstat_cache() (at an appropriate place) to make sure that the\n> + * cache is clean before first call to check_lstat_cache().\n> + */\n> +void clear_lstat_cache(void)\n> +{\n> +\tcache_flags = 0;\n> +\tcache_len   = 0;\n> +}\n> -- \n> 1.6.1.rc1.49.g7f705\n"},{"id":"99444","messageId":"7vk598j17u.fsf@gitster.siamese.dyndns.org","threadId":"16993","inReplyTo":"1231161001-32599-3-git-send-email-barvik@broadpark.no","subject":"Re: [PATCH/RFC 2/4] Use 'lstat_cache()' instead of 'has_symlink_leading_path()'","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2009-01-06T08:19:33Z","receivedAt":"2009-01-06T08:19:33Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Kjetil Barvik <barvik@broadpark.no> writes:\n\n> Start using the optimised, faster and more effective symlink/directory\n> cache.  The previously used call:\n>\n>    has_symlink_leading_path(len, name);\n>\n> should be identically with the following call to lstat_cache():\n>\n>    lstat_cache(len, name,\n>                LSTAT_SYMLINK|LSTAT_DIR,\n>                LSTAT_SYMLINK);\n> ...\n\nCare to enlighten why some of callers use the above, but not others?\nNamely, check_removed() in diff-lib.c and callers in unpack-trees.c care\nabout NOTDIR unlike others, even though the original code checked for\nexactly the same condition.\n\nDoes this mean that some callers of has_symlink_leading_path() checked\nonly for leading symlinks when they should also have checked for a leading\nnon-directory, and this patch is also a bugfix?\n"},{"id":"99450","messageId":"7v3afwizi7.fsf@gitster.siamese.dyndns.org","threadId":"16993","inReplyTo":"7vprj0j181.fsf@gitster.siamese.dyndns.org","subject":"Re: [PATCH/RFC 1/4] Optimised, faster, more effective symlink/directory detection","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2009-01-06T08:56:32Z","receivedAt":"2009-01-06T08:56:32Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano <gitster@pobox.com> writes:\n\n> Let me see if I understand the logic behind this caching....\n> ...\n>> +\t\tlast_slash = match_len;\n>> +\t\tcache_path[last_slash] = '\\0';\n>> +\n>> +\t\tif (lstat(cache_path, &st)) {\n>> +\t\t\tret_flags = LSTAT_LSTATERR;\n>> +\t\t\tif (errno == ENOENT || errno == ENOTDIR)\n>> +\t\t\t\tret_flags |= LSTAT_NOTDIR;\n>\n> If you tested \"A/B\" here and got ENOENT back, you know \"A/B\" does not\n> exist; you cache this knowledge as \"A/B is not a directory\" (I also think\n> you could use it as a cached knowledge that \"A exists and is a directory\".\n> I am not sure if you are taking advantage of that).\n>\n> What I do not understand about this code is the ENOTDIR case.  If you\n> tested \"A/B\" and got ENOTDIR back, what you know is that \"A\" is not a\n> directory (if the path tested this round were deeper like \"X/Y/A/B\", you\n> know \"X/Y/A\" is not a directory, and you know \"X\" and \"X/Y\" are true\n> directories; otherwise the loop would have exited before this round when\n> you tested \"X\" or \"X/Y\" in the earlier rounds).\n>\n> So as far as I can think of, ENOENT case and ENOTDIR case would give you\n> different information (ENOENT would say \"A is a dir, A/B is not\"; ENOTDIR\n> would say \"A is not a dir\").  I am confused how you can cache the same\n> path and same flag between these two cases here.\n\nI take 1/4 of the above back.\n\nIf everything is working correctly, I do not think you will ever have a\nsituation where you check \"A/B\" here and get ENOTDIR back.  lstat(\"A/B\")\nwould yield ENOTDIR if \"A\" is not a directory, but:\n\n (1) If you did test \"A\" in the earlier round in the loop, you would have\n     already found it is not a directory and would have exited the loop\n     with LSTAT_ERR.  You cannot test \"A/B\" in such a case;\n\n (2) If you did not test \"A\" in the loop, that has to be because you had a\n     cached information for it, and the caching logic would have returned\n     early if \"A\" was a non-directory without entering the loop; in other\n     words, you would test \"A/B\" here without testing \"A\" in the loop only\n     when the cache says \"A\" was a directory.  You cannot get ENOTDIR in\n     such a case.\n\nIn any case, my main puzzlement still stands.  I think ENOTDIR case should\nbehave differently from ENOENT case.\n\nAnd I think it is an indication of a grave error, either this code is\nracing with an external process that is actively mucking with the work\ntree to make your cached information unusable, or somebody forgot to call\nclear_lstat_cache().\n\nHmm?\n"},{"id":"99455","messageId":"86fxjwlqro.fsf@broadpark.no","threadId":"16993","inReplyTo":"7vprj0j181.fsf@gitster.siamese.dyndns.org","subject":"Re: [PATCH/RFC 1/4] Optimised, faster, more effective symlink/directory detection","fromName":"Kjetil Barvik","fromEmail":"barvik@broadpark.no","sentAt":"2009-01-06T09:36:59Z","receivedAt":"2009-01-06T09:36:59Z","isPatch":true,"sender":{"key":"barvik@broadpark.no","avatar":null},"body":"Junio C Hamano <gitster@pobox.com> writes:\n\n> Kjetil Barvik <barvik@broadpark.no> writes:\n>\n>> +static inline void\n>> +update_path_cache(unsigned int ret_flags, unsigned int track_flags,\n>> +\t\t  int last_slash)\n>> +{\n>> +\t/* Max 3 different path types can be cached for the moment! */\n>> +\tunsigned int save_flags =\n>> +\t\tret_flags & track_flags & (LSTAT_DIR|\n>> +\t\t\t\t\t   LSTAT_NOTDIR|\n>> +\t\t\t\t\t   LSTAT_SYMLINK);\n>> +\tif (save_flags && last_slash > 0 && last_slash < PATH_MAX) {\n>> +\t\tcache_flags = save_flags;\n>> +\t\tcache_len   = last_slash;\n>> +\t} else {\n>> +\t\tcache_flags = 0;\n>> +\t\tcache_len   = 0;\n>> +\t}\n>> +}\n>\n> I personally found this inline function with a single call site\n> distracting in following the logic.  It does not make the indentation\n> level shallower, either.  Also, the else part should probably call\n> clear_lstat_cache() to protect it from possible future enhancements to add\n> more state variables.\n\n  Ok, I will remove the function and update the else-part.\n\n>> +\n>> +/*\n>> + * Check if name 'name' of length 'len' has a symlink leading\n>> + * component, or if the directory exists and is real, or not.\n>> + *\n>> + * To speed up the check, some information is allowed to be cached.\n>> + * This is indicated by the 'track_flags' argument.\n>> + */\n>> +unsigned int\n>> +check_lstat_cache(int len, const char *name, unsigned int track_flags)\n>> +{\n>> +\tint match_len, last_slash, max_len;\n>> +\tunsigned int match_flags, ret_flags;\n>> +\tstruct stat st;\n>> +\n>> +\t/* Check if match from the cache for 2 \"excluding\" path types.\n>> +\t */\n>> +\tmatch_len = last_slash =\n>> +\t\tgreatest_common_path_cache_prefix(len, name);\n>> +\tmatch_flags =\n>> +\t\tcache_flags & track_flags & (LSTAT_NOTDIR|\n>> +\t\t\t\t\t     LSTAT_SYMLINK);\n>> +\tif (match_flags && match_len == cache_len)\n>> +\t\treturn match_flags;\n>\n> Let me see if I understand the logic behind this caching.  When you have\n> checked A/B/C earlier and you already know B is a symlink, you remember\n> that A/B was a symlink..  You can fill a request to check A/B/$whatever\n> (assuming A/B does not change --- otherwise the caller should clear the\n> cache) from the cached data, because no matter what $whatever is, it will\n> result in the same \"has-leading-symlink\".\n>\n> Similarly, if you know A/B is not a directory from an earlier test, you\n> know that a request to check A/B/$whatever will result in the same ENOTDIR\n> no matter what $whatever is, so you can return early.\n>\n> The above \"return match_flags\" will not trigger if the cached path does\n> not have any leading symlink.  So we know the matched part are all good\n> directories when we start lstat() loop.\n>\n> Am I following you so far?\n\n  Yes you do!\n\n>> +\t/* Okay, no match from the cache so far, so now we have to\n>> +\t * check the rest of the path components and update the cache.\n>> +\t */\n>> +\tret_flags = LSTAT_DIR;\n>> +\tmax_len = len < PATH_MAX ? len : PATH_MAX;\n>> +\twhile (match_len < max_len) {\n>> +\t\tdo {\n>> +\t\t\tcache_path[match_len] = name[match_len];\n>> +\t\t\tmatch_len++;\n>> +\t\t} while (match_len < max_len && name[match_len] != '/');\n>\n> You take one component from the input, and append it to the part that is\n> already known to be true directory (i.e. cached part and the part earlier\n> iteration of the loop checked so far), to be tested by lstat()...\n>\n>> +\t\tif (match_len >= max_len)\n>> +\t\t\tbreak;\n>\n> ... but you are not interested in the full input.  \n\n  If the lengt of name is larger than PATH_MAX all lstat() calls would\n  fail with an ENAMETOOLONG error, at least on my Linux box, so I\n  thought that it was not nessarry to test further.  But maybe we should\n  emdiatly return an error if name is too long?\n\n> We are only checking the leading path (e.g. check for \"A/B/C\" may\n> lstat() \"A\", \"A/B\" but not \"A/B/C\").\n\n  That is correct, and it is the same logic as in the\n  has_symlink_leading_path() function.\n\n>> +\t\tlast_slash = match_len;\n>> +\t\tcache_path[last_slash] = '\\0';\n>> +\n>> +\t\tif (lstat(cache_path, &st)) {\n>> +\t\t\tret_flags = LSTAT_LSTATERR;\n>> +\t\t\tif (errno == ENOENT || errno == ENOTDIR)\n>> +\t\t\t\tret_flags |= LSTAT_NOTDIR;\n>\n> If you tested \"A/B\" here and got ENOENT back, you know \"A/B\" does not\n> exist; you cache this knowledge as \"A/B is not a directory\" \n\n  Correct.\n\n> (I also think you could use it as a cached knowledge that \"A exists\n> and is a directory\".  I am not sure if you are taking advantage of\n> that).\n\n  It does take adavantage of this fact.  It will also do simmilar things\n  with a symlink cached path.\n\n> What I do not understand about this code is the ENOTDIR case.  If you\n> tested \"A/B\" and got ENOTDIR back, what you know is that \"A\" is not a\n> directory (if the path tested this round were deeper like \"X/Y/A/B\", you\n> know \"X/Y/A\" is not a directory, and you know \"X\" and \"X/Y\" are true\n> directories; otherwise the loop would have exited before this round when\n> you tested \"X\" or \"X/Y\" in the earlier rounds).\n\n  Since the cache is supoosed to start from a known existing directory,\n  and is testing each path component when the lstat(\"A/B\") calls returns\n  ENOTDIR, we should know the fact that the directory \"A\" exists, and\n  that \"A/B/\" does not exists.\n  \n> So as far as I can think of, ENOENT case and ENOTDIR case would give you\n> different information (ENOENT would say \"A is a dir, A/B is not\"; ENOTDIR\n> would say \"A is not a dir\").  I am confused how you can cache the same\n> path and same flag between these two cases here.\n\n  I admit that I used copy-and-paste from other similar test's from the\n  sourcecode:\n\nkjetil@localhost ~/git/git $ grep -Hn ENOENT.*ENOTDIR *.c\nbuiltin-apply.c:2364:\telse if ((errno != ENOENT) && (errno != ENOTDIR))\nbuiltin-update-index.c:74: *  - missing file (ENOENT or ENOTDIR). That's ok if we're\nbuiltin-update-index.c:81:\tif (err == ENOENT || err == ENOTDIR)\ndiff-lib.c:30:\t\tif (errno != ENOENT && errno != ENOTDIR)\nlstat_cache.c:81:\t\t\tif (errno == ENOENT || errno == ENOTDIR)\nsetup.c:191:\tif (errno != ENOENT && errno != ENOTDIR)\n\n  From the 'man lstat' page I read the following for this 2 error codes:\n\n    ENOENT    A component of the path _path_ does not exist, or the path is an empty string.\n    ENOTDIR   A component of the path is not a directory.\n\n  I would have guessed that for what we is looking for, it would be\n  correct to threat both these error codes as the same.  Is this wrong?\n\n  -- kjetil\n"},{"id":"99458","messageId":"86bpuklpul.fsf@broadpark.no","threadId":"16993","inReplyTo":"7v3afwizi7.fsf@gitster.siamese.dyndns.org","subject":"Re: [PATCH/RFC 1/4] Optimised, faster, more effective symlink/directory detection","fromName":"Kjetil Barvik","fromEmail":"barvik@broadpark.no","sentAt":"2009-01-06T09:56:50Z","receivedAt":"2009-01-06T09:56:50Z","isPatch":true,"sender":{"key":"barvik@broadpark.no","avatar":null},"body":"Junio C Hamano <gitster@pobox.com> writes:\n <snipp>\n> If everything is working correctly, I do not think you will ever have a\n> situation where you check \"A/B\" here and get ENOTDIR back.  lstat(\"A/B\")\n> would yield ENOTDIR if \"A\" is not a directory, but:\n>\n>  (1) If you did test \"A\" in the earlier round in the loop, you would have\n>      already found it is not a directory and would have exited the loop\n>      with LSTAT_ERR.  You cannot test \"A/B\" in such a case;\n\n  No, if the test lstat(\"A\") already returned -1 it would then have set\n  errno to ENOTDIR in this case, I think.  So in this case the cache\n  would have only stored \"A\".\n\n>  (2) If you did not test \"A\" in the loop, that has to be because you had a\n>      cached information for it, and the caching logic would have returned\n>      early if \"A\" was a non-directory without entering the loop; in other\n>      words, you would test \"A/B\" here without testing \"A\" in the loop only\n>      when the cache says \"A\" was a directory.  You cannot get ENOTDIR in\n>      such a case.\n>\n> In any case, my main puzzlement still stands.  I think ENOTDIR case should\n> behave differently from ENOENT case.\n>\n> And I think it is an indication of a grave error, either this code is\n> racing with an external process that is actively mucking with the work\n> tree to make your cached information unusable, or somebody forgot to call\n> clear_lstat_cache().\n>\n> Hmm?\n\n  I think that you do not see that the when the lstat() function returns\n  errno =\n\n    ENOENT   A component of the path path does not exist, or the path is\n             an empty string.\n    ENOTDIR  A component of the path is not a directory.\n\n  the cache logic will/must assume that the component we got an error on\n  will/must always be the _last_ component in the path.\n\n> I take 1/4 of the above back.\n\n  Will this means that I do not have to update the patch to version 2?\n\n  Note, one thing what I personally do not like with this patch so far,\n  is that it makes a new file, and then it kinda hides the comments from\n  Linus which talks aboth extending the logic.  It would maybe be better\n  to have reused the same file (symlinks.c), but then the function name\n  ('lstat_cache()') and the filename would not match.\n\n  -- kjetil\n"},{"id":"99466","messageId":"86r63gk381.fsf@broadpark.no","threadId":"16993","inReplyTo":"7vk598j17u.fsf@gitster.siamese.dyndns.org","subject":"Re: [PATCH/RFC 2/4] Use 'lstat_cache()' instead of 'has_symlink_leading_path()'","fromName":"Kjetil Barvik","fromEmail":"barvik@broadpark.no","sentAt":"2009-01-06T12:50:54Z","receivedAt":"2009-01-06T12:50:54Z","isPatch":true,"sender":{"key":"barvik@broadpark.no","avatar":null},"body":"Junio C Hamano <gitster@pobox.com> writes:\n\n> Kjetil Barvik <barvik@broadpark.no> writes:\n>\n>> Start using the optimised, faster and more effective symlink/directory\n>> cache.  The previously used call:\n>>\n>>    has_symlink_leading_path(len, name);\n>>\n>> should be identically with the following call to lstat_cache():\n>>\n>>    lstat_cache(len, name,\n>>                LSTAT_SYMLINK|LSTAT_DIR,\n>>                LSTAT_SYMLINK);\n>> ...\n>\n> Care to enlighten why some of callers use the above, but not others?\n> Namely, check_removed() in diff-lib.c \n\n  I though that first it would be a good thing to introduce as little\n  changes as possible, and then later on do some cleanups.  Regarding\n  the 'check_removed()' function, I though that it could later have been\n  written something like this after cleanups:\n\n[....]\nstatic int check_removed(const struct cache_entry *ce, struct stat *st)\n{\n\tunsigned int ret_flags =\n\t\tcheck_lstat_cache(ce_namelen(ce), ce->name,\n\t\t\t\t  LSTAT_SYMLINK|LSTAT_NOTDIR|LSTAT_DIR);\n\n\tif (ret_flags & (LSTAT_SYMLINK|LSTAT_NOTDIR))\n\t\treturn 1;\n\tif (ret_flags & LSTAT_LSTATERR)\n\t\treturn -1;\n\n\tif (ret_flags & LSTAT_DIR) {\n\t\tunsigned char sub[20];\n[....]\n\n  This would have saved one more lstat() call in some cases.  But after\n  a test, I now see that it does not work.  The reason is that it does\n  not set the 'struct stat *st' parameter and/or that for the moment you\n  can not tell the 'lstat_cache()' function to also always test the last\n  path component.  It could be extended to do this, if someone ask for\n  it and if it would be useful to extend the lstat_cache() for this\n  fact.\n\n  I will remove the '|LSTAT_NOTDIR' part from the call to lstat_cache()\n  in 'check_removed()' in the next version of the patch.\n\n> and callers in unpack-trees.c care about NOTDIR unlike others, even\n> though the original code checked for exactly the same condition.\n\n  Regarding the 'verify_absent()' function in unpack-trees.c, the\n  '|LSTAT_NOTDIR' part of the call to lstat_cache() helps to avoid 16047\n  lstat() calls for the given test case mentioned in the cover-letter.\n  And from the source code:\n\n  [...]\n\tif (lstat_cache(ce_namelen(ce), ce->name,\n\t\t\tLSTAT_SYMLINK|LSTAT_NOTDIR|LSTAT_DIR,\n\t\t\tLSTAT_SYMLINK|LSTAT_NOTDIR))\n\t\treturn 0;\n\n\tif (!lstat(ce->name, &st)) {\n  [...]\n\n  it should be easy to see that if we from the lstat_cache() could\n  already spot that some path component of ce->name does not exists,\n  then we can avoid the following lstat() call, as it then should known\n  to be failing.\n\n  regarding the 'unlink_entry()' function in unpack-trees.c, the\n  '|LSTAT_NOTDIR' part of the call to lstat_cache() does not for the\n  moment helps to avoid any lstat() calls, as far as I can see.  But,\n  again, from the source code:\n\n  [..]\n\tchar *name = ce->name;\n\n\tif (lstat_cache(ce_namelen(ce), ce->name,\n\t\t\tLSTAT_SYMLINK|LSTAT_NOTDIR|LSTAT_DIR,\n\t\t\tLSTAT_SYMLINK|LSTAT_NOTDIR))\n\t\treturn;\n\tif (unlink(name))\n\t\treturn;\n  [...]\n\n  it should be correct, since if we already know that some path\n  component of ce-name does not exist, the call to unlink(name) would\n  always fail (with ENOENT).\n\n> Does this mean that some callers of has_symlink_leading_path() checked\n> only for leading symlinks when they should also have checked for a leading\n> non-directory, and this patch is also a bugfix?\n\n  Yes, as indicated above, has_symlink_leading_path() should have\n  checked for leading non-directories when called from for the\n  'verify_absent()' function to be able to optimise away some more\n  lstat() calls.\n\n  I admit that I do not know the source code good enough to decide if\n  this is an indication of a bug somewhere, or just an optimisation.\n\n  -- kjetil\n"},{"id":"99471","messageId":"86mye4k0ob.fsf@broadpark.no","threadId":"16993","inReplyTo":"7v3afwizi7.fsf@gitster.siamese.dyndns.org","subject":"Re: [PATCH/RFC 1/4] Optimised, faster, more effective symlink/directory detection","fromName":"Kjetil Barvik","fromEmail":"barvik@broadpark.no","sentAt":"2009-01-06T13:45:56Z","receivedAt":"2009-01-06T13:45:56Z","isPatch":true,"sender":{"key":"barvik@broadpark.no","avatar":null},"body":"Junio C Hamano <gitster@pobox.com> writes:\n <snipp>\n> If everything is working correctly, I do not think you will ever have a\n> situation where you check \"A/B\" here and get ENOTDIR back.  lstat(\"A/B\")\n> would yield ENOTDIR if \"A\" is not a directory, but:\n>\n>  (1) If you did test \"A\" in the earlier round in the loop, you would have\n>      already found it is not a directory and would have exited the loop\n>      with LSTAT_ERR.  You cannot test \"A/B\" in such a case;\n>\n>  (2) If you did not test \"A\" in the loop, that has to be because you had a\n>      cached information for it, and the caching logic would have returned\n>      early if \"A\" was a non-directory without entering the loop; in other\n>      words, you would test \"A/B\" here without testing \"A\" in the loop only\n>      when the cache says \"A\" was a directory.  You cannot get ENOTDIR in\n>      such a case.\n>\n> In any case, my main puzzlement still stands.  I think ENOTDIR case should\n> behave differently from ENOENT case.\n>\n> And I think it is an indication of a grave error, either this code is\n> racing with an external process that is actively mucking with the work\n> tree to make your cached information unusable, or somebody forgot to call\n> clear_lstat_cache().\n>\n> Hmm?\n\n  I have looked at this once more, and I have to admit that what you\n  have said is correct.  Sorry for being confusing!  I will update the\n  patch by removing the 'errno == ENOTDIR' part from the if-test.\n\n  -- kjetil\n"}]}