{"thread":{"id":"17064","subject":"[PATCH/RFC v5 1/1] more cache effective symlink/directory detection","startedAt":"2009-01-09T19:05:53Z","lastAt":"2009-01-11T08:26:14Z","messageCount":5,"participants":["Kjetil Barvik","René Scharfe","Junio C Hamano"],"isPatch":true,"patchVersion":5,"patchTotal":1},"messages":[{"id":"99809","messageId":"1231527954-868-1-git-send-email-barvik@broadpark.no","threadId":"17064","inReplyTo":null,"subject":"[PATCH/RFC v5 0/1] git checkout: optimise away lots of lstat() calls","fromName":"Kjetil Barvik","fromEmail":"barvik@broadpark.no","sentAt":"2009-01-09T19:05:53Z","receivedAt":"2009-01-09T19:05:53Z","isPatch":true,"sender":{"key":"barvik@broadpark.no","avatar":null},"body":"Changes since version 4:\n\n- After looking at the changes in create_directories() inside entry.c\n  for some more time, I got the idea to just use the lstat_cache()\n  instead of almost use a separate cache implementation of its own.\n\n- To be able to implement that, I had to be able to tell the cache to\n  test the full length of input 'name'.  I also had to be able to tell\n  the cache to use the stat() function instead of the lstat() function\n  for a given prefix length.\n\n- Fixed a missed cache optimisation where you is not able to cache a\n  symlink or a none existing directory, but still wants to cache the\n  real directory part.  Fixed a second missed cache optimisation where\n  the 'name' argument is a (complete) substring of the cache on a path\n  component basis.\n\n- The cache can now also return LSTAT_REG for a regular file, but\n  please note that it can only cache the directory part of that file.\n\n- Since the changes made to the create_directories() function now is\n  small and simple (just had to change an if-test, remove 2 unused\n  variables and update the comments), patch 2/2 is gone and included\n  into patch 1/1.\n\n- More updates to the comments in the source code.\n\n- Thanks to Pete Harlan for spelling fixes to the commit message!\n\nI think that the patch starts to be in a good shape now, but please\ncomment on it, even if it is just a rename of a variable/function name\nto increase the readability or a spelling fix!\n\nFor the fun of it, I did a test with 'git chekcout-index -q --all\n--prefix=<a path containing 29 components>' from the my-v2.6.27 Linux\nbranch, and the savings was really huge: the numbers of lstat() and\nstat() calls dropped from 778 145 to 26 674, and the real time also\ndropped from 52 to 32 seconds on my laptop!  :-)\n\n-----\n\nI 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 1 patch and\nbeen able to optimise away over 40% of all lstat() calls in some cases\nfor the 'git checkout' command.  Also, if you use a large path to the\n'--prefix' argument to the 'git checkout-index' command, and you have\nlots of files, the savings can be really huge!\n\nThe patch is against git master, and the git 'make test' test suite\nstill passes after the patch.  To document the improvement, below is\nsome numbers, which compares before and after the patch. To reproduce\nthe 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 pretty print the 'strace_to27' file.  Below is the numbers\nfrom the current git version (before the patch).  Notice that we do an\nlstat() call on the \"arch\" directory over 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 numbers after applying the patch.  Notice how nice the top\n20 entries list now looks!\n\nTOTAL      134155 100.000% OK:122102 NOT: 12053  11.069389 sec   83 usec/call\nlstat64     69876  52.086% OK: 63491 NOT:  6385   3.410007 sec   49 usec/call\n  strings   69876 tot  30163 uniq   2.317 /uniq   3.410007 sec   49 usec/call\n  files     61491 tot  28712 uniq   2.142 /uniq   3.023238 sec   49 usec/call\n  dirs       2000 tot   1436 uniq   1.393 /uniq   0.085953 sec   43 usec/call\n  errors     6385 tot   5189 uniq   1.230 /uniq   0.300816 sec   47 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\nComments?\n\n\nKjetil Barvik (1):\n  more cache effective symlink/directory detection\n\n builtin-add.c          |    1 +\n builtin-apply.c        |    1 +\n builtin-update-index.c |    1 +\n cache.h                |   24 +++++++-\n diff-lib.c             |    1 +\n entry.c                |   39 +++++-------\n symlinks.c             |  158 +++++++++++++++++++++++++++++++++++-------------\n unpack-trees.c         |    6 +-\n 8 files changed, 162 insertions(+), 69 deletions(-)\n"},{"id":"99808","messageId":"1231527954-868-2-git-send-email-barvik@broadpark.no","threadId":"17064","inReplyTo":"1231527954-868-1-git-send-email-barvik@broadpark.no","subject":"[PATCH/RFC v5 1/1] more cache effective symlink/directory detection","fromName":"Kjetil Barvik","fromEmail":"barvik@broadpark.no","sentAt":"2009-01-09T19:05:54Z","receivedAt":"2009-01-09T19:05:54Z","isPatch":true,"sender":{"key":"barvik@broadpark.no","avatar":null},"body":"Changes 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\" are 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 its type.  Since the\n  cache functionality is always used with alphabetically sorted names\n  (at least it seems 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- Previously, when symlink A/B/C/S was cached/stored in the\n  symlink-leading path, and A/B/C/file.c was called for, it was not\n  easy to use the fact that we already knew that the paths \"A\", \"A/B\"\n  and \"A/B/C\" are real directories.  Since we now only store one\n  single path (the last one), we also get similar logic for free\n  regarding the new \"non-existing-directory-cache\".\n\n- Avoid copying the first path components of the name 2 zillion times\n  when we test 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 a 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.  This argument can also be used to tell the cache\n  to always test the complete length of 'name' (add 'LSTAT_FULLPATH').\n\n- Introduce a 4th argument, 'prefix_len_stat_func', which tells the\n  length of a prefix, where the cache should use the stat() function\n  instead of the lstat() function to test each path component.  This\n  can for instance be useful at some places in the source code to\n  handle the --prefix argument to the 'git checkout-index' command.\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\nWe also start to use the lstat_cache() function inside the\n'create_directories()' function inside entry.c, and we save really\nhuge amounts of calls to the stat()/lstat() functions in some cases.\n\nSigned-off-by: Kjetil Barvik <barvik@broadpark.no>\n---\n:100644 100644 719de8b... 870961e... M\tbuiltin-add.c\n:100644 100644 a8f75ed... d3d001a... M\tbuiltin-apply.c\n:100644 100644 5604977... 8907219... M\tbuiltin-update-index.c\n:100644 100644 231c06d... 0bf31d3... M\tcache.h\n:100644 100644 ae96c64... c9caa0e... M\tdiff-lib.c\n:100644 100644 aa2ee46... 293400c... M\tentry.c\n:100644 100644 5a5e781... 314ba4f... M\tsymlinks.c\n:100644 100644 54f301d... c3d1429... M\tunpack-trees.c\n builtin-add.c          |    1 +\n builtin-apply.c        |    1 +\n builtin-update-index.c |    1 +\n cache.h                |   24 +++++++-\n diff-lib.c             |    1 +\n entry.c                |   39 +++++-------\n symlinks.c             |  158 +++++++++++++++++++++++++++++++++++-------------\n unpack-trees.c         |    6 +-\n 8 files changed, 162 insertions(+), 69 deletions(-)\n\ndiff --git a/builtin-add.c b/builtin-add.c\nindex 719de8b0f2d2d831f326d948aa18700e5c474950..870961e8ca4e3d6f9333020083d0a232bccd542c 100644\n--- a/builtin-add.c\n+++ b/builtin-add.c\n@@ -225,6 +225,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_symlink_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..d3d001a96be6e502d6338af4467f7c313370d78e 100644\n--- a/builtin-apply.c\n+++ b/builtin-apply.c\n@@ -3154,6 +3154,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_symlink_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 560497750586ec61be4e34de6dedd9c307129817..8907219fb9cb438113e29ee17854edb5dd4baa4d 100644\n--- a/builtin-update-index.c\n+++ b/builtin-update-index.c\n@@ -581,6 +581,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_symlink_cache();\n \tfor (i = 1 ; i < argc; i++) {\n \t\tconst char *path = argv[i];\n \t\tconst char *p;\ndiff --git a/cache.h b/cache.h\nindex 231c06d7726b575f6e522d5b0c0fe43557e8c651..0bf31d3e8903a658927938f6da45c77dd289c94a 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -719,7 +719,29 @@ struct checkout {\n };\n \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_REG      (1u << 0)\n+#define LSTAT_DIR      (1u << 1)\n+#define LSTAT_NOENT    (1u << 2)\n+#define LSTAT_SYMLINK  (1u << 3)\n+#define LSTAT_LSTATERR (1u << 4)\n+#define LSTAT_ERR      (1u << 5)\n+#define LSTAT_FULLPATH (1u << 6)\n+extern unsigned int lstat_cache(int len, const char *name,\n+\t\t\t\tunsigned int track_flags, int prefix_len_stat_func);\n+extern void clear_lstat_cache(void);\n+static inline unsigned int has_symlink_leading_path(int len, const char *name)\n+{\n+\treturn lstat_cache(len, name, LSTAT_SYMLINK|LSTAT_DIR, -1) &\n+\t\tLSTAT_SYMLINK;\n+}\n+#define clear_symlink_cache() clear_lstat_cache()\n+static inline unsigned int has_symlink_or_noent_leading_path(int len, const char *name)\n+{\n+\treturn lstat_cache(len, name, LSTAT_SYMLINK|LSTAT_NOENT|LSTAT_DIR, -1) &\n+\t\t(LSTAT_SYMLINK|LSTAT_NOENT);\n+}\n+#define clear_symlink_or_noent_cache() clear_lstat_cache()\n \n extern struct alternate_object_database {\n \tstruct alternate_object_database *next;\ndiff --git a/diff-lib.c b/diff-lib.c\nindex ae96c64ca209f4df9008198e8a04b160bed618c7..c9caa0e6ef0f4a8ee8b850869ef6d0f52b712385 100644\n--- a/diff-lib.c\n+++ b/diff-lib.c\n@@ -69,6 +69,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_symlink_cache();\n \tfor (i = 0; i < entries; i++) {\n \t\tstruct stat st;\n \t\tunsigned int oldmode, newmode;\ndiff --git a/entry.c b/entry.c\nindex aa2ee46a84033585d8e07a585610c5a697af82c2..293400cf5be63fd66b797a68e17bf953c600fe99 100644\n--- a/entry.c\n+++ b/entry.c\n@@ -8,35 +8,28 @@ static void create_directories(const char *path, const struct checkout *state)\n \tconst char *slash = path;\n \n \twhile ((slash = strchr(slash+1, '/')) != NULL) {\n-\t\tstruct stat st;\n-\t\tint stat_status;\n-\n \t\tlen = slash - path;\n \t\tmemcpy(buf, path, len);\n \t\tbuf[len] = 0;\n \n-\t\tif (len <= 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\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-\n-\t\tif (!stat_status && S_ISDIR(st.st_mode))\n+\t\t/* For 'checkout-index --prefix=<dir>', <dir> is\n+\t\t * allowed to be a symlink to an existing directory,\n+\t\t * therefore we must give 'state->base_dir_len' to the\n+\t\t * cache, such that we test path components of the\n+\t\t * prefix with stat() instead of lstat()\n+\t\t *\n+\t\t * We must also tell the cache to test the complete\n+\t\t * length of the buffer (the '|LSTAT_FULLPATH' part).\n+\t\t */\n+\t\tif (lstat_cache(len, buf, LSTAT_DIR|LSTAT_FULLPATH,\n+\t\t\t\tstate->base_dir_len) &\n+\t\t    LSTAT_DIR)\n \t\t\tcontinue; /* ok, it is already a directory. */\n \n-\t\t/*\n-\t\t * We know stat_status == 0 means something exists\n-\t\t * there and this mkdir would fail, but that is an\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/* If this mkdir() would fail, it could be that there\n+\t\t * is already a symlink or something else exists\n+\t\t * there, therefore we then try to unlink it and try\n+\t\t * one more time to create the directory.\n \t\t */\n \t\tif (mkdir(buf, 0777)) {\n \t\t\tif (errno == EEXIST && state->force &&\ndiff --git a/symlinks.c b/symlinks.c\nindex 5a5e781a15d7d9cb60797958433eca896b31ec85..314ba4f273f9f776a130b5e5b48c5bda0ca9beed 100644\n--- a/symlinks.c\n+++ b/symlinks.c\n@@ -1,64 +1,136 @@\n #include \"cache.h\"\n \n-struct pathname {\n-\tint len;\n-\tchar path[PATH_MAX];\n-};\n+static char         cache_path[PATH_MAX + 2];\n+static int          cache_len   = 0;\n+static unsigned int cache_flags = 0;\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+static inline int greatest_match_lstat_cache(int len, const char *name)\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+\tint max_len, match_len = 0, i = 0;\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+\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+\telse if (i == len && len < cache_len && cache_path[len] == '/')\n+\t\tmatch_len = len;\n+\telse if (i == len && i == cache_len)\n+\t\tmatch_len = len;\n+\treturn match_len;\n }\n \n-int has_symlink_leading_path(int len, const char *name)\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 can be indicated by the 'track_flags' argument, which also\n+ * can be used to indicate that we should always check the full path.\n+ *\n+ * The 'prefix_len_stat_func' parameter can be used to set the length\n+ * of the prefix, where the cache should use the stat() function\n+ * instead of the lstat() function to test each path component.\n+ */\n+unsigned int lstat_cache(int len, const char *name,\n+\t\t\t unsigned int track_flags, int prefix_len_stat_func)\n {\n-\tstatic struct pathname link, nonlink;\n-\tchar path[PATH_MAX];\n+\tint match_len, last_slash, last_slash_dir, max_len, ret;\n+\tunsigned int match_flags, ret_flags, save_flags;\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/* Check if match from the cache for 2 \"excluding\" path types.\n+\t */\n+\tmatch_len = last_slash = greatest_match_lstat_cache(len, name);\n+\tmatch_flags = cache_flags & track_flags & (LSTAT_NOENT|LSTAT_SYMLINK);\n+\tif (match_flags && match_len == cache_len)\n+\t\treturn match_flags;\n+\n+\t/* If 'name' is a substring of the cache on a path component\n+\t * basis, and a directory is cached, we return immediately.\n \t */\n-\tif (match_pathname(len, name, &link))\n-\t\treturn 1;\n+\tmatch_flags = cache_flags & track_flags & LSTAT_DIR;\n+\tif (match_flags && match_len == len)\n+\t\treturn match_flags;\n \n-\t/*\n-\t * Get rid of the last known directory part\n+\t/* Okay, no match from the cache so far, so now we have to\n+\t * check the rest of the path components.\n \t */\n-\tknown_dir = match_pathname(len, name, &nonlink);\n+\tret_flags = LSTAT_DIR;\n+\tlast_slash_dir = last_slash;\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 && !(track_flags & LSTAT_FULLPATH))\n+\t\t\tbreak;\n+\t\tlast_slash = match_len;\n+\t\tcache_path[last_slash] = '\\0';\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+\t\tif (last_slash <= prefix_len_stat_func)\n+\t\t\tret = stat(cache_path, &st);\n+\t\telse\n+\t\t\tret = lstat(cache_path, &st);\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\tif (ret) {\n+\t\t\tret_flags = LSTAT_LSTATERR;\n+\t\t\tif (errno == ENOENT)\n+\t\t\t\tret_flags |= LSTAT_NOENT;\n+\t\t} else if (S_ISDIR(st.st_mode)) {\n+\t\t\tlast_slash_dir = last_slash;\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} else if (S_ISLNK(st.st_mode)) {\n+\t\t\tret_flags = LSTAT_SYMLINK;\n+\t\t} else if (S_ISREG(st.st_mode)) {\n+\t\t\tret_flags = LSTAT_REG;\n+\t\t} else {\n+\t\t\tret_flags = LSTAT_ERR;\n \t\t}\n \t\tbreak;\n \t}\n-\treturn 0;\n+\n+\t/* At the end update the cache.  Note that max 3 different\n+\t * path types, LSTAT_NOENT, LSTAT_SYMLINK and LSTAT_DIR, can\n+\t * be cached for the moment!\n+\t */\n+\tsave_flags = ret_flags & track_flags & (LSTAT_NOENT|LSTAT_SYMLINK);\n+\tif (save_flags && last_slash > 0 && last_slash <= PATH_MAX) {\n+\t\tcache_path[last_slash] = '\\0';\n+\t\tcache_len   = last_slash;\n+\t\tcache_flags = save_flags;\n+\t} else if (track_flags & LSTAT_DIR &&\n+\t\t   last_slash_dir > 0 && last_slash_dir <= PATH_MAX) {\n+\t\t/* We have separate test for the directory case, since\n+\t\t * it could be that we have found a symlink or none\n+\t\t * existing directory, and the track_flags says that\n+\t\t * we can not cache this fact, and the cache would\n+\t\t * then have been empty in this case.\n+\t\t *\n+\t\t * But, if we is allowed to track real directories, we\n+\t\t * can still cache the path components before the last\n+\t\t * one (the found symlink or none existing component).\n+\t\t */\n+\t\tcache_path[last_slash_dir] = '\\0';\n+\t\tcache_len   = last_slash_dir;\n+\t\tcache_flags = LSTAT_DIR;\n+\t} else {\n+\t\tclear_lstat_cache();\n+\t}\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.\n+ */\n+void clear_lstat_cache(void)\n+{\n+\tcache_path[0] = '\\0';\n+\tcache_len     = 0;\n+\tcache_flags   = 0;\n }\ndiff --git a/unpack-trees.c b/unpack-trees.c\nindex 54f301da67be879c80426bc21776427fdd38c02e..c3d14294aaaefb9e40c99f174b4f5f41e5fad635 100644\n--- a/unpack-trees.c\n+++ b/unpack-trees.c\n@@ -61,7 +61,7 @@ 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 (has_symlink_or_noent_leading_path(ce_namelen(ce), ce->name))\n \t\treturn;\n \tif (unlink(name))\n \t\treturn;\n@@ -105,6 +105,7 @@ static int check_updates(struct unpack_trees_options *o)\n \t\tcnt = 0;\n \t}\n \n+\tclear_symlink_or_noent_cache();\n \tfor (i = 0; i < index->cache_nr; i++) {\n \t\tstruct cache_entry *ce = index->cache[i];\n \n@@ -118,6 +119,7 @@ static int check_updates(struct unpack_trees_options *o)\n \t\t}\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 +586,7 @@ 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 (has_symlink_or_noent_leading_path(ce_namelen(ce), ce->name))\n \t\treturn 0;\n \n \tif (!lstat(ce->name, &st)) {\n-- \n1.6.1.rc1.49.g7f705\n"},{"id":"99860","messageId":"49687440.5090506@lsrfire.ath.cx","threadId":"17064","inReplyTo":"1231527954-868-2-git-send-email-barvik@broadpark.no","subject":"Re: [PATCH/RFC v5 1/1] more cache effective symlink/directory detection","fromName":"René Scharfe","fromEmail":"rene.scharfe@lsrfire.ath.cx","sentAt":"2009-01-10T10:11:12Z","receivedAt":"2009-01-10T10:11:12Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Kjetil Barvik schrieb:\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\nIs it possible to make the cache detect these situations automatically\nby saving track_flags along with the cache contents?  Not having to\nclear the cache manually would be a major feature.\n\n> --- a/cache.h\n> +++ b/cache.h\n> @@ -719,7 +719,29 @@ struct checkout {\n>  };\n>  \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_REG      (1u << 0)\n> +#define LSTAT_DIR      (1u << 1)\n> +#define LSTAT_NOENT    (1u << 2)\n> +#define LSTAT_SYMLINK  (1u << 3)\n> +#define LSTAT_LSTATERR (1u << 4)\n> +#define LSTAT_ERR      (1u << 5)\n> +#define LSTAT_FULLPATH (1u << 6)\n> +extern unsigned int lstat_cache(int len, const char *name,\n> +\t\t\t\tunsigned int track_flags, int prefix_len_stat_func);\n> +extern void clear_lstat_cache(void);\n> +static inline unsigned int has_symlink_leading_path(int len, const char *name)\n> +{\n> +\treturn lstat_cache(len, name, LSTAT_SYMLINK|LSTAT_DIR, -1) &\n> +\t\tLSTAT_SYMLINK;\n> +}\n> +#define clear_symlink_cache() clear_lstat_cache()\n> +static inline unsigned int has_symlink_or_noent_leading_path(int len, const char *name)\n> +{\n> +\treturn lstat_cache(len, name, LSTAT_SYMLINK|LSTAT_NOENT|LSTAT_DIR, -1) &\n> +\t\t(LSTAT_SYMLINK|LSTAT_NOENT);\n> +}\n> +#define clear_symlink_or_noent_cache() clear_lstat_cache()\n\nWhat's the advantage of inlining the wrappers (expressed in units of\nspace and/or time)?  The interface would be much nicer if you exported\nthe wrappers, only, and not all those constants along with them.\n\nAnd why define aliases for clear_lstat_cache()?\n\n> diff --git a/entry.c b/entry.c\n> index aa2ee46a84033585d8e07a585610c5a697af82c2..293400cf5be63fd66b797a68e17bf953c600fe99 100644\n> --- a/entry.c\n> +++ b/entry.c\n> @@ -8,35 +8,28 @@ static void create_directories(const char *path, const struct checkout *state)\n>  \tconst char *slash = path;\n>  \n>  \twhile ((slash = strchr(slash+1, '/')) != NULL) {\n> -\t\tstruct stat st;\n> -\t\tint stat_status;\n> -\n>  \t\tlen = slash - path;\n>  \t\tmemcpy(buf, path, len);\n>  \t\tbuf[len] = 0;\n>  \n> -\t\tif (len <= 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\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> -\n> -\t\tif (!stat_status && S_ISDIR(st.st_mode))\n> +\t\t/* For 'checkout-index --prefix=<dir>', <dir> is\n> +\t\t * allowed to be a symlink to an existing directory,\n> +\t\t * therefore we must give 'state->base_dir_len' to the\n> +\t\t * cache, such that we test path components of the\n> +\t\t * prefix with stat() instead of lstat()\n> +\t\t *\n> +\t\t * We must also tell the cache to test the complete\n> +\t\t * length of the buffer (the '|LSTAT_FULLPATH' part).\n> +\t\t */\n> +\t\tif (lstat_cache(len, buf, LSTAT_DIR|LSTAT_FULLPATH,\n> +\t\t\t\tstate->base_dir_len) &\n> +\t\t    LSTAT_DIR)\n>  \t\t\tcontinue; /* ok, it is already a directory. */\n\nI'd say this usage is worth another wrapper.\n\nAlso, it's probably worth to split this patch up again.  First switching\nto your improved implementation of has_symlink_leading_path(), then\nintroducing has_symlink_or_noent_leading_path() and finally adding\nLSTAT_FULLPATH and the fourth parameter of lstat_cache() etc. and using\nthis feature in entry.c seems like a nice incremental progression.\n\nRené\n"},{"id":"99926","messageId":"7vljtivfao.fsf@gitster.siamese.dyndns.org","threadId":"17064","inReplyTo":"49687440.5090506@lsrfire.ath.cx","subject":"Re: [PATCH/RFC v5 1/1] more cache effective symlink/directory detection","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2009-01-11T00:48:15Z","receivedAt":"2009-01-11T00:48:15Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"René Scharfe <rene.scharfe@lsrfire.ath.cx> writes:\n\n> Kjetil Barvik schrieb:\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>\n> Is it possible to make the cache detect these situations automatically\n> by saving track_flags along with the cache contents?  Not having to\n> clear the cache manually would be a major feature.\n\n> Also, it's probably worth to split this patch up again.  First switching\n> to your improved implementation of has_symlink_leading_path(), then\n> introducing has_symlink_or_noent_leading_path() and finally adding\n> LSTAT_FULLPATH and the fourth parameter of lstat_cache() etc. and using\n> this feature in entry.c seems like a nice incremental progression.\n\nBoth are reasonable suggestions.  Thanks.\n"},{"id":"99935","messageId":"86vdsm8d09.fsf@broadpark.no","threadId":"17064","inReplyTo":"7vljtivfao.fsf@gitster.siamese.dyndns.org","subject":"Re: [PATCH/RFC v5 1/1] more cache effective symlink/directory detection","fromName":"Kjetil Barvik","fromEmail":"barvik@broadpark.no","sentAt":"2009-01-11T08:26:14Z","receivedAt":"2009-01-11T08:26:14Z","isPatch":true,"sender":{"key":"barvik@broadpark.no","avatar":null},"body":"Junio C Hamano <gitster@pobox.com> writes:\n\n> René Scharfe <rene.scharfe@lsrfire.ath.cx> writes:\n>\n>> Kjetil Barvik schrieb:\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>>\n>> Is it possible to make the cache detect these situations automatically\n>> by saving track_flags along with the cache contents?  Not having to\n>> clear the cache manually would be a major feature.\n>\n>> Also, it's probably worth to split this patch up again.  First switching\n>> to your improved implementation of has_symlink_leading_path(), then\n>> introducing has_symlink_or_noent_leading_path() and finally adding\n>> LSTAT_FULLPATH and the fourth parameter of lstat_cache() etc. and using\n>> this feature in entry.c seems like a nice incremental progression.\n>\n> Both are reasonable suggestions.  Thanks.\n\n  Ok!  Thanks for comments!  Version 6 will follow shortly!\n\n  -- kjetil\n"}]}