{"thread":{"id":"17144","subject":"[PATCH/RFC v7 0/5] git checkout: optimise away lots of lstat() calls","startedAt":"2009-01-13T12:29:03Z","lastAt":"2009-01-13T20:17:48Z","messageCount":7,"participants":["Kjetil Barvik","Junio C Hamano"],"isPatch":true,"patchVersion":7,"patchTotal":5},"messages":[{"id":"100268","messageId":"1231849748-8244-1-git-send-email-barvik@broadpark.no","threadId":"17144","inReplyTo":null,"subject":"[PATCH/RFC v7 0/5] git checkout: optimise away lots of lstat() calls","fromName":"Kjetil Barvik","fromEmail":"barvik@broadpark.no","sentAt":"2009-01-13T12:29:03Z","receivedAt":"2009-01-13T12:29:03Z","isPatch":true,"sender":{"key":"barvik@broadpark.no","avatar":null},"body":"Changes since version 6:\n\na) The patch-split was not correct for patch 3/3.  In v6 it could look\n   like the lines:\n\n-\tchar path[PATH_MAX];\n+\tchar path[PATH_MAX + 1];\n\n   was a random bugfix.  In this version for patch 3/5 we also change\n   \"&& last_slash < PATH_MAX\" into \"&& last_slash <= PATH_MAX\" (and\n   similar for the else-if part).  This could also make the intro-\n   duction of the 'FL_FULLPATH' flag more readable for this patch.\n\nb) Cleanup and added 3 comments to 'greatest_match_lstat_cache()'\n\nc) Introduction of the 'invalidate_lstat_cache()' function.  How does\n   the interface look?  good?  bad?  Does the function do what people\n   expect it to do?\n\nd) Reintroduction of the 'clear_lstat_cache()' function.\n\nJunio, I hope it is possible to use patches 1/5, 2/5 and 3/5 from this\nversion instead of 1/3, 2/3 and 3/3 from version 6, for the possible\nfuture in origin/pu?  See also a) above.  Thanks in advance!\n\nIn general, are we allowed to redesign the patch-series while the\npatches is inside origin/pu?\n\n\nKjetil Barvik (5):\n  lstat_cache(): more cache effective symlink/directory detection\n  lstat_cache(): introduce has_symlink_or_noent_leading_path() function\n  lstat_cache(): introduce has_dirs_only_path() function\n  lstat_cache(): introduce invalidate_lstat_cache() function\n  lstat_cache(): introduce clear_lstat_cache() function\n\n cache.h        |    4 +\n entry.c        |   34 +++-----\n symlinks.c     |  249 ++++++++++++++++++++++++++++++++++++++++++++++----------\n unpack-trees.c |    4 +-\n 4 files changed, 222 insertions(+), 69 deletions(-)\n"},{"id":"100271","messageId":"1231849748-8244-2-git-send-email-barvik@broadpark.no","threadId":"17144","inReplyTo":"1231849748-8244-1-git-send-email-barvik@broadpark.no","subject":"[PATCH/RFC v7 1/5] lstat_cache(): more cache effective symlink/directory detection","fromName":"Kjetil Barvik","fromEmail":"barvik@broadpark.no","sentAt":"2009-01-13T12:29:04Z","receivedAt":"2009-01-13T12:29:04Z","isPatch":true,"sender":{"key":"barvik@broadpark.no","avatar":null},"body":"Make the cache functionality more effective.  Previously when A/B/C/D\nwas in the cache and A/B/C/E/file.c was called for, there was no match\nat all from the cache.  Now we use the fact that the paths \"A\", \"A/B\"\nand \"A/B/C\" are already tested, and we only need to do an lstat() call\non \"A/B/C/E\".\n\nWe only cache/store the last path regardless of its type.  Since the\ncache functionality is always used with alphabetically sorted names\n(at least it seems so for me), there is no need to store both the last\nsymlink-leading path and the last real-directory path.  Note that if\nthe cache is not called with (mostly) alphabetically sorted names,\nneither the old, nor this new one, would be very effective.\n\nPreviously, when symlink A/B/C/S was cached/stored in the symlink-\nleading path, and A/B/C/file.c was called for, it was not easy to use\nthe fact that we already knew that the paths \"A\", \"A/B\" and \"A/B/C\"\nare real directories.\n\nAvoid copying the first path components of the name 2 zillion times\nwhen we test new path components.  Since we always cache/store the\nlast path, we can copy each component as we test those directly into\nthe cache.  Previously we ended up doing a memcpy() for the full\npath/name right before each lstat() call, and when updating the cache\nfor each time we have tested a new path component.\n\nWe also use less memory, that is, PATH_MAX bytes less memory on the\nstack and PATH_MAX bytes less memory on the heap.\n\nThanks to Junio C Hamano, Linus Torvalds and Rene Scharfe for valuable\ncomments to this patch!\n\nSigned-off-by: Kjetil Barvik <barvik@broadpark.no>\n---\n symlinks.c |  157 ++++++++++++++++++++++++++++++++++++++++++++---------------\n 1 files changed, 117 insertions(+), 40 deletions(-)\n\ndiff --git a/symlinks.c b/symlinks.c\nindex 5a5e781..b17e4b3 100644\n--- a/symlinks.c\n+++ b/symlinks.c\n@@ -1,64 +1,141 @@\n #include \"cache.h\"\n \n-struct pathname {\n-\tint len;\n+static struct cache_def {\n \tchar path[PATH_MAX];\n-};\n+\tint len;\n+\tint flags;\n+} cache;\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+/* Returns the length (on a path component basis) of the longest\n+ * common prefix match of 'name' and the cached path string.\n+ */\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+\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] == '/')\n+\t\t\tmatch_len = i;\n+\t\ti++;\n+\t}\n+\t/* Is the cached path string a substring of 'name'? */\n+\tif (i == cache.len && len > cache.len && name[cache.len] == '/')\n+\t\tmatch_len = cache.len;\n+\t/* Is 'name' a substring of the cached path string? */\n+\telse if ((i == len && len < cache.len && cache.path[len] == '/') ||\n+\t\t (i == len && len == cache.len))\n+\t\tmatch_len = len;\n+\treturn match_len;\n }\n \n-static inline void set_pathname(int len, const char *name, struct pathname *match)\n+static inline void reset_lstat_cache(void)\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+\tcache.path[0] = '\\0';\n+\tcache.len   = 0;\n+\tcache.flags = 0;\n }\n \n-int has_symlink_leading_path(int len, const char *name)\n+#define FL_DIR      (1 << 0)\n+#define FL_SYMLINK  (1 << 1)\n+#define FL_LSTATERR (1 << 2)\n+#define FL_ERR      (1 << 3)\n+\n+/*\n+ * Check if name 'name' of length 'len' has a symlink leading\n+ * component, or if the directory exists and is real.\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.\n+ */\n+static int lstat_cache(int len, const char *name,\n+\t\t       int track_flags)\n {\n-\tstatic struct pathname link, nonlink;\n-\tchar path[PATH_MAX];\n+\tint match_len, last_slash, last_slash_dir;\n+\tint match_flags, ret_flags, save_flags, max_len;\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 to see if we have a match from the cache for the\n+\t * symlink path type.\n \t */\n-\tif (match_pathname(len, name, &link))\n-\t\treturn 1;\n-\n+\tmatch_len = last_slash = greatest_match_lstat_cache(len, name);\n+\tmatch_flags = cache.flags & track_flags & FL_SYMLINK;\n+\tif (match_flags && match_len == cache.len)\n+\t\treturn match_flags;\n \t/*\n-\t * Get rid of the last known directory part\n+\t * If 'name' is a substring of the cache on a path component\n+\t * basis, and a directory is cached, we can return\n+\t * immediately.\n \t */\n-\tknown_dir = match_pathname(len, name, &nonlink);\n+\tmatch_flags = cache.flags & track_flags & FL_DIR;\n+\tif (match_flags && match_len == len)\n+\t\treturn match_flags;\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/* 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+\tret_flags = FL_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)\n+\t\t\tbreak;\n+\t\tlast_slash = match_len;\n+\t\tcache.path[last_slash] = '\\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\tif (lstat(cache.path, &st)) {\n+\t\t\tret_flags = FL_LSTATERR;\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 = FL_SYMLINK;\n+\t\t} else {\n+\t\t\tret_flags = FL_ERR;\n \t\t}\n \t\tbreak;\n \t}\n-\treturn 0;\n+\n+\t/* At the end update the cache.  Note that max 2 different\n+\t * path types, FL_SYMLINK and FL_DIR, can be cached for the\n+\t * moment!\n+\t */\n+\tsave_flags = ret_flags & track_flags & FL_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 & FL_DIR &&\n+\t\t   last_slash_dir > 0 && last_slash_dir < PATH_MAX) {\n+\t\t/* We have a separate test for the directory case,\n+\t\t * since it could be that we have found a symlink and\n+\t\t * the track_flags says that we can not cache this\n+\t\t * fact, so the cache would then have been left empty\n+\t\t * 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 component).\n+\t\t */\n+\t\tcache.path[last_slash_dir] = '\\0';\n+\t\tcache.len   = last_slash_dir;\n+\t\tcache.flags = FL_DIR;\n+\t} else {\n+\t\treset_lstat_cache();\n+\t}\n+\treturn ret_flags;\n+}\n+\n+/* Return non-zero if path 'name' has a leading symlink component.\n+ */\n+int has_symlink_leading_path(int len, const char *name)\n+{\n+\treturn lstat_cache(len, name,\n+\t\t\t   FL_SYMLINK|FL_DIR) &\n+\t\tFL_SYMLINK;\n }\n-- \n1.6.0.2.GIT\n"},{"id":"100269","messageId":"1231849748-8244-3-git-send-email-barvik@broadpark.no","threadId":"17144","inReplyTo":"1231849748-8244-1-git-send-email-barvik@broadpark.no","subject":"[PATCH/RFC v7 2/5] lstat_cache(): introduce has_symlink_or_noent_leading_path() function","fromName":"Kjetil Barvik","fromEmail":"barvik@broadpark.no","sentAt":"2009-01-13T12:29:05Z","receivedAt":"2009-01-13T12:29:05Z","isPatch":true,"sender":{"key":"barvik@broadpark.no","avatar":null},"body":"In some cases, especially inside the unpack-trees.c file, and inside\nthe verify_absent() function, we can avoid some unnecessary calls to\nlstat(), if the lstat_cache() function can also be told to keep track\nof none existing directories.\n\nSo we update the lstat_cache() function to handle this new fact,\nintroduce a new wrapper function, and the result is that we save lots\nof lstat() calls for a removed directory which previously contained\nlots of files, when we call this new wrapper of lstat_cache() instead\nof the old one.\n\nWe do similar changes inside the unlink_entry() function, since if we\ncan already say that the leading directory component of a pathname\ndoes not exist, it is not necessary to try to remove a pathname below\nit!\n\nThanks to Junio C Hamano, Linus Torvalds and Rene Scharfe for valuable\ncomments to this patch!\n\nSigned-off-by: Kjetil Barvik <barvik@broadpark.no>\n---\n cache.h        |    1 +\n symlinks.c     |   87 ++++++++++++++++++++++++++++++++++++--------------------\n unpack-trees.c |    4 +-\n 3 files changed, 59 insertions(+), 33 deletions(-)\n\ndiff --git a/cache.h b/cache.h\nindex 231c06d..11181aa 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -720,6 +720,7 @@ struct checkout {\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+extern int has_symlink_or_noent_leading_path(int len, const char *name);\n \n extern struct alternate_object_database {\n \tstruct alternate_object_database *next;\ndiff --git a/symlinks.c b/symlinks.c\nindex b17e4b3..52b3b0e 100644\n--- a/symlinks.c\n+++ b/symlinks.c\n@@ -4,6 +4,7 @@ static struct cache_def {\n \tchar path[PATH_MAX];\n \tint len;\n \tint flags;\n+\tint track_flags;\n } cache;\n \n /* Returns the length (on a path component basis) of the longest\n@@ -29,21 +30,23 @@ static inline int greatest_match_lstat_cache(int len, const char *name)\n \treturn match_len;\n }\n \n-static inline void reset_lstat_cache(void)\n+static inline void reset_lstat_cache(int track_flags)\n {\n \tcache.path[0] = '\\0';\n \tcache.len   = 0;\n \tcache.flags = 0;\n+\tcache.track_flags = track_flags;\n }\n \n #define FL_DIR      (1 << 0)\n-#define FL_SYMLINK  (1 << 1)\n-#define FL_LSTATERR (1 << 2)\n-#define FL_ERR      (1 << 3)\n+#define FL_NOENT    (1 << 1)\n+#define FL_SYMLINK  (1 << 2)\n+#define FL_LSTATERR (1 << 3)\n+#define FL_ERR      (1 << 4)\n \n /*\n  * Check if name 'name' of length 'len' has a symlink leading\n- * component, or if the directory exists and is real.\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.\n@@ -55,22 +58,32 @@ static int lstat_cache(int len, const char *name,\n \tint match_flags, ret_flags, save_flags, max_len;\n \tstruct stat st;\n \n-\t/*\n-\t * Check to see if we have a match from the cache for the\n-\t * symlink path type.\n-\t */\n-\tmatch_len = last_slash = greatest_match_lstat_cache(len, name);\n-\tmatch_flags = cache.flags & track_flags & FL_SYMLINK;\n-\tif (match_flags && match_len == cache.len)\n-\t\treturn match_flags;\n-\t/*\n-\t * If 'name' is a substring of the cache on a path component\n-\t * basis, and a directory is cached, we can return\n-\t * immediately.\n-\t */\n-\tmatch_flags = cache.flags & track_flags & FL_DIR;\n-\tif (match_flags && match_len == len)\n-\t\treturn match_flags;\n+\tif (cache.track_flags != track_flags) {\n+\t\t/*\n+\t\t * As a safeguard we clear the cache if the value of\n+\t\t * track_flags does not match with the last supplied\n+\t\t * value.\n+\t\t */\n+\t\treset_lstat_cache(track_flags);\n+\t\tmatch_len = last_slash = 0;\n+\t} else {\n+\t\t/*\n+\t\t * Check to see if we have a match from the cache for\n+\t\t * the 2 \"excluding\" path types.\n+\t\t */\n+\t\tmatch_len = last_slash = greatest_match_lstat_cache(len, name);\n+\t\tmatch_flags = cache.flags & track_flags & (FL_NOENT|FL_SYMLINK);\n+\t\tif (match_flags && match_len == cache.len)\n+\t\t\treturn match_flags;\n+\t\t/*\n+\t\t * If 'name' is a substring of the cache on a path\n+\t\t * component basis, and a directory is cached, we\n+\t\t * can return immediately.\n+\t\t */\n+\t\tmatch_flags = cache.flags & track_flags & FL_DIR;\n+\t\tif (match_flags && match_len == len)\n+\t\t\treturn match_flags;\n+\t}\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.\n@@ -90,6 +103,8 @@ static int lstat_cache(int len, const char *name,\n \n \t\tif (lstat(cache.path, &st)) {\n \t\t\tret_flags = FL_LSTATERR;\n+\t\t\tif (errno == ENOENT)\n+\t\t\t\tret_flags |= FL_NOENT;\n \t\t} else if (S_ISDIR(st.st_mode)) {\n \t\t\tlast_slash_dir = last_slash;\n \t\t\tcontinue;\n@@ -101,11 +116,11 @@ static int lstat_cache(int len, const char *name,\n \t\tbreak;\n \t}\n \n-\t/* At the end update the cache.  Note that max 2 different\n-\t * path types, FL_SYMLINK and FL_DIR, can be cached for the\n-\t * moment!\n+\t/* At the end update the cache.  Note that max 3 different\n+\t * path types, FL_NOENT, FL_SYMLINK and FL_DIR, can be cached\n+\t * for the moment!\n \t */\n-\tsave_flags = ret_flags & track_flags & FL_SYMLINK;\n+\tsave_flags = ret_flags & track_flags & (FL_NOENT|FL_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@@ -113,20 +128,20 @@ static int lstat_cache(int len, const char *name,\n \t} else if (track_flags & FL_DIR &&\n \t\t   last_slash_dir > 0 && last_slash_dir < PATH_MAX) {\n \t\t/* We have a separate test for the directory case,\n-\t\t * since it could be that we have found a symlink and\n-\t\t * the track_flags says that we can not cache this\n-\t\t * fact, so the cache would then have been left empty\n-\t\t * in this case.\n+\t\t * since it could be that we have found a symlink or a\n+\t\t * none existing directory and the track_flags says\n+\t\t * that we can not cache this fact, so the cache would\n+\t\t * then have been left 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 component).\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 = FL_DIR;\n \t} else {\n-\t\treset_lstat_cache();\n+\t\treset_lstat_cache(track_flags);\n \t}\n \treturn ret_flags;\n }\n@@ -139,3 +154,13 @@ int has_symlink_leading_path(int len, const char *name)\n \t\t\t   FL_SYMLINK|FL_DIR) &\n \t\tFL_SYMLINK;\n }\n+\n+/* Return non-zero if path 'name' has a leading symlink component or\n+ * if some leading path component does not exists.\n+ */\n+int has_symlink_or_noent_leading_path(int len, const char *name)\n+{\n+\treturn lstat_cache(len, name,\n+\t\t\t   FL_SYMLINK|FL_NOENT|FL_DIR) &\n+\t\t(FL_SYMLINK|FL_NOENT);\n+}\ndiff --git a/unpack-trees.c b/unpack-trees.c\nindex 54f301d..a3fd383 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@@ -584,7 +584,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.0.2.GIT\n"},{"id":"100272","messageId":"1231849748-8244-4-git-send-email-barvik@broadpark.no","threadId":"17144","inReplyTo":"1231849748-8244-1-git-send-email-barvik@broadpark.no","subject":"[PATCH/RFC v7 3/5] lstat_cache(): introduce has_dirs_only_path() function","fromName":"Kjetil Barvik","fromEmail":"barvik@broadpark.no","sentAt":"2009-01-13T12:29:06Z","receivedAt":"2009-01-13T12:29:06Z","isPatch":true,"sender":{"key":"barvik@broadpark.no","avatar":null},"body":"Inside the create_directories() function inside entry.c we currently\ndo an stat() or lstat() call for each path component of the pathname\n'path' each and every time called.  For the 'git checkout' command,\nthis function is called on each file for which we must do an update\n(ce->ce_flags & CE_UPDATE), so we get lots and lots of calls...\n\nTo fix this, we make a new wrapper to the lstat_cache() function, and\ncall the wrapper function instead of the calls to the stat() or the\nlstat() functions.  Since the paths given to the create_directories()\nfunction, is sorted alphabetically, the new wrapper would be very\ncache effective in this situation.\n\nTo support it we must update the lstat_cache() function to be able to\nsay that \"pleace test the complete length of 'name'\", and also to give\nit the length of a prefix, where the cache should use the stat()\nfunction instead of the lstat() function to test each path component.\n\nThanks to Junio C Hamano, Linus Torvalds and Rene Scharfe for valuable\ncomments to this patch!\n\nSigned-off-by: Kjetil Barvik <barvik@broadpark.no>\n---\n cache.h    |    1 +\n entry.c    |   34 ++++++++++---------------------\n symlinks.c |   63 +++++++++++++++++++++++++++++++++++++++++++----------------\n 3 files changed, 58 insertions(+), 40 deletions(-)\n\ndiff --git a/cache.h b/cache.h\nindex 11181aa..7c8c8e4 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -721,6 +721,7 @@ 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 extern int has_symlink_or_noent_leading_path(int len, const char *name);\n+extern int has_dirs_only_path(int len, const char *name, int prefix_len);\n \n extern struct alternate_object_database {\n \tstruct alternate_object_database *next;\ndiff --git a/entry.c b/entry.c\nindex aa2ee46..b0295bd 100644\n--- a/entry.c\n+++ b/entry.c\n@@ -8,35 +8,23 @@ 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 * and we set 'state->base_dir_len' below, such that\n+\t\t * we test the path components of the prefix with the\n+\t\t * stat() function instead of the lstat() function.\n+\t\t */\n+\t\tif (has_dirs_only_path(len, buf, state->base_dir_len))\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 52b3b0e..f9d1821 100644\n--- a/symlinks.c\n+++ b/symlinks.c\n@@ -1,10 +1,11 @@\n #include \"cache.h\"\n \n static struct cache_def {\n-\tchar path[PATH_MAX];\n+\tchar path[PATH_MAX + 1];\n \tint len;\n \tint flags;\n \tint track_flags;\n+\tint prefix_len_stat_func;\n } cache;\n \n /* Returns the length (on a path component basis) of the longest\n@@ -30,12 +31,13 @@ static inline int greatest_match_lstat_cache(int len, const char *name)\n \treturn match_len;\n }\n \n-static inline void reset_lstat_cache(int track_flags)\n+static inline void reset_lstat_cache(int track_flags, int prefix_len_stat_func)\n {\n \tcache.path[0] = '\\0';\n \tcache.len   = 0;\n \tcache.flags = 0;\n \tcache.track_flags = track_flags;\n+\tcache.prefix_len_stat_func = prefix_len_stat_func;\n }\n \n #define FL_DIR      (1 << 0)\n@@ -43,28 +45,35 @@ static inline void reset_lstat_cache(int track_flags)\n #define FL_SYMLINK  (1 << 2)\n #define FL_LSTATERR (1 << 3)\n #define FL_ERR      (1 << 4)\n+#define FL_FULLPATH (1 << 5)\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 can be indicated by the 'track_flags' argument.\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 static int lstat_cache(int len, const char *name,\n-\t\t       int track_flags)\n+\t\t       int track_flags, int prefix_len_stat_func)\n {\n \tint match_len, last_slash, last_slash_dir;\n-\tint match_flags, ret_flags, save_flags, max_len;\n+\tint match_flags, ret_flags, save_flags, max_len, ret;\n \tstruct stat st;\n \n-\tif (cache.track_flags != track_flags) {\n+\tif (cache.track_flags != track_flags ||\n+\t    cache.prefix_len_stat_func != prefix_len_stat_func) {\n \t\t/*\n-\t\t * As a safeguard we clear the cache if the value of\n-\t\t * track_flags does not match with the last supplied\n-\t\t * value.\n+\t\t * As a safeguard we clear the cache if the values of\n+\t\t * track_flags and/or prefix_len_stat_func does not\n+\t\t * match with the last supplied values.\n \t\t */\n-\t\treset_lstat_cache(track_flags);\n+\t\treset_lstat_cache(track_flags, prefix_len_stat_func);\n \t\tmatch_len = last_slash = 0;\n \t} else {\n \t\t/*\n@@ -96,12 +105,17 @@ static int lstat_cache(int len, const char *name,\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\tif (match_len >= max_len && !(track_flags & FL_FULLPATH))\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\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 (ret) {\n \t\t\tret_flags = FL_LSTATERR;\n \t\t\tif (errno == ENOENT)\n \t\t\t\tret_flags |= FL_NOENT;\n@@ -121,12 +135,12 @@ static int lstat_cache(int len, const char *name,\n \t * for the moment!\n \t */\n \tsave_flags = ret_flags & track_flags & (FL_NOENT|FL_SYMLINK);\n-\tif (save_flags && last_slash > 0 && last_slash < PATH_MAX) {\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 & FL_DIR &&\n-\t\t   last_slash_dir > 0 && last_slash_dir < PATH_MAX) {\n+\t\t   last_slash_dir > 0 && last_slash_dir <= PATH_MAX) {\n \t\t/* We have a separate test for the directory case,\n \t\t * since it could be that we have found a symlink or a\n \t\t * none existing directory and the track_flags says\n@@ -141,17 +155,19 @@ static int lstat_cache(int len, const char *name,\n \t\tcache.len   = last_slash_dir;\n \t\tcache.flags = FL_DIR;\n \t} else {\n-\t\treset_lstat_cache(track_flags);\n+\t\treset_lstat_cache(track_flags, prefix_len_stat_func);\n \t}\n \treturn ret_flags;\n }\n \n+#define USE_ONLY_LSTAT  0\n+\n /* Return non-zero if path 'name' has a leading symlink component.\n  */\n int has_symlink_leading_path(int len, const char *name)\n {\n \treturn lstat_cache(len, name,\n-\t\t\t   FL_SYMLINK|FL_DIR) &\n+\t\t\t   FL_SYMLINK|FL_DIR, USE_ONLY_LSTAT) &\n \t\tFL_SYMLINK;\n }\n \n@@ -161,6 +177,19 @@ int has_symlink_leading_path(int len, const char *name)\n int has_symlink_or_noent_leading_path(int len, const char *name)\n {\n \treturn lstat_cache(len, name,\n-\t\t\t   FL_SYMLINK|FL_NOENT|FL_DIR) &\n+\t\t\t   FL_SYMLINK|FL_NOENT|FL_DIR, USE_ONLY_LSTAT) &\n \t\t(FL_SYMLINK|FL_NOENT);\n }\n+\n+/* Return non-zero if all path components of 'name' exists as a\n+ * directory.  If prefix_len > 0, we will test with the stat()\n+ * function instead of the lstat() function for a prefix length of\n+ * 'prefix_len', thus we then allow for symlink(s) in the prefix part\n+ * as long as those points to real existing directories.\n+ */\n+int has_dirs_only_path(int len, const char *name, int prefix_len)\n+{\n+\treturn lstat_cache(len, name,\n+\t\t\t   FL_DIR|FL_FULLPATH, prefix_len) &\n+\t\tFL_DIR;\n+}\n-- \n1.6.0.2.GIT\n"},{"id":"100270","messageId":"1231849748-8244-5-git-send-email-barvik@broadpark.no","threadId":"17144","inReplyTo":"1231849748-8244-1-git-send-email-barvik@broadpark.no","subject":"[PATCH/RFC v7 4/5] lstat_cache(): introduce invalidate_lstat_cache() function","fromName":"Kjetil Barvik","fromEmail":"barvik@broadpark.no","sentAt":"2009-01-13T12:29:07Z","receivedAt":"2009-01-13T12:29:07Z","isPatch":true,"sender":{"key":"barvik@broadpark.no","avatar":null},"body":"In some cases it could maybe be necessary to say to the cache that\n\"Hey, I deleted this directory and if you currently has it inside your\ncache, you should deleted it\".  This patch introduce a function which\nsupport this.\n\nSigned-off-by: Kjetil Barvik <barvik@broadpark.no>\n---\n cache.h    |    1 +\n symlinks.c |   39 +++++++++++++++++++++++++++++++--------\n 2 files changed, 32 insertions(+), 8 deletions(-)\n\ndiff --git a/cache.h b/cache.h\nindex 7c8c8e4..f4452a8 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -722,6 +722,7 @@ extern int checkout_entry(struct cache_entry *ce, const struct checkout *state,\n extern int has_symlink_leading_path(int len, const char *name);\n extern int has_symlink_or_noent_leading_path(int len, const char *name);\n extern int has_dirs_only_path(int len, const char *name, int prefix_len);\n+extern void invalidate_lstat_cache(int len, const char *name);\n \n extern struct alternate_object_database {\n \tstruct alternate_object_database *next;\ndiff --git a/symlinks.c b/symlinks.c\nindex f9d1821..3b1c3da 100644\n--- a/symlinks.c\n+++ b/symlinks.c\n@@ -11,23 +11,30 @@ static struct cache_def {\n /* Returns the length (on a path component basis) of the longest\n  * common prefix match of 'name' and the cached path string.\n  */\n-static inline int greatest_match_lstat_cache(int len, const char *name)\n+static inline int greatest_match_lstat_cache(int len, const char *name,\n+\t\t\t\t\t     int *previous_slash)\n {\n-\tint max_len, match_len = 0, i = 0;\n+\tint max_len, match_len = 0, match_len_prev = 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] == '/')\n+\t\tif (name[i] == '/') {\n+\t\t\tmatch_len_prev = match_len;\n \t\t\tmatch_len = i;\n+\t\t}\n \t\ti++;\n \t}\n \t/* Is the cached path string a substring of 'name'? */\n-\tif (i == cache.len && len > cache.len && name[cache.len] == '/')\n+\tif (i == cache.len && len > cache.len && name[cache.len] == '/') {\n+\t\tmatch_len_prev = match_len;\n \t\tmatch_len = cache.len;\n \t/* Is 'name' a substring of the cached path string? */\n-\telse if ((i == len && len < cache.len && cache.path[len] == '/') ||\n-\t\t (i == len && len == cache.len))\n+\t} else if ((i == len && len < cache.len && cache.path[len] == '/') ||\n+\t\t   (i == len && len == cache.len)) {\n+\t\tmatch_len_prev = match_len;\n \t\tmatch_len = len;\n+\t}\n+\t*previous_slash = match_len_prev;\n \treturn match_len;\n }\n \n@@ -62,7 +69,7 @@ static inline void reset_lstat_cache(int track_flags, int prefix_len_stat_func)\n static int lstat_cache(int len, const char *name,\n \t\t       int track_flags, int prefix_len_stat_func)\n {\n-\tint match_len, last_slash, last_slash_dir;\n+\tint match_len, last_slash, last_slash_dir, previous_slash;\n \tint match_flags, ret_flags, save_flags, max_len, ret;\n \tstruct stat st;\n \n@@ -80,7 +87,8 @@ static int lstat_cache(int len, const char *name,\n \t\t * Check to see if we have a match from the cache for\n \t\t * the 2 \"excluding\" path types.\n \t\t */\n-\t\tmatch_len = last_slash = greatest_match_lstat_cache(len, name);\n+\t\tmatch_len = last_slash =\n+\t\t\tgreatest_match_lstat_cache(len, name, &previous_slash);\n \t\tmatch_flags = cache.flags & track_flags & (FL_NOENT|FL_SYMLINK);\n \t\tif (match_flags && match_len == cache.len)\n \t\t\treturn match_flags;\n@@ -160,6 +168,21 @@ static int lstat_cache(int len, const char *name,\n \treturn ret_flags;\n }\n \n+/* Invalidate the given 'name' from the cache, if 'name' matches\n+ * completely with the cache.\n+ */\n+void invalidate_lstat_cache(int len, const char *name)\n+{\n+\tint match_len, previous_slash;\n+\n+\tmatch_len = greatest_match_lstat_cache(len, name, &previous_slash);\n+\tif (match_len == len) {\n+\t\tcache.path[previous_slash] = '\\0';\n+\t\tcache.len   = previous_slash;\n+\t\tcache.flags = previous_slash ? FL_DIR : 0;\n+\t}\n+}\n+\n #define USE_ONLY_LSTAT  0\n \n /* Return non-zero if path 'name' has a leading symlink component.\n-- \n1.6.0.2.GIT\n"},{"id":"100273","messageId":"1231849748-8244-6-git-send-email-barvik@broadpark.no","threadId":"17144","inReplyTo":"1231849748-8244-1-git-send-email-barvik@broadpark.no","subject":"[PATCH/RFC v7 5/5] lstat_cache(): introduce clear_lstat_cache() function","fromName":"Kjetil Barvik","fromEmail":"barvik@broadpark.no","sentAt":"2009-01-13T12:29:08Z","receivedAt":"2009-01-13T12:29:08Z","isPatch":true,"sender":{"key":"barvik@broadpark.no","avatar":null},"body":"If you want to completely clear the contents of the lstat_cache(), then\ncall this new function.\n\nSigned-off-by: Kjetil Barvik <barvik@broadpark.no>\n---\n cache.h    |    1 +\n symlinks.c |    7 +++++++\n 2 files changed, 8 insertions(+), 0 deletions(-)\n\ndiff --git a/cache.h b/cache.h\nindex f4452a8..468daf6 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -723,6 +723,7 @@ extern int has_symlink_leading_path(int len, const char *name);\n extern int has_symlink_or_noent_leading_path(int len, const char *name);\n extern int has_dirs_only_path(int len, const char *name, int prefix_len);\n extern void invalidate_lstat_cache(int len, const char *name);\n+extern void clear_lstat_cache(void);\n \n extern struct alternate_object_database {\n \tstruct alternate_object_database *next;\ndiff --git a/symlinks.c b/symlinks.c\nindex 3b1c3da..7a634cb 100644\n--- a/symlinks.c\n+++ b/symlinks.c\n@@ -183,6 +183,13 @@ void invalidate_lstat_cache(int len, const char *name)\n \t}\n }\n \n+/* Completely clear the contents of the cache!\n+ */\n+void clear_lstat_cache(void)\n+{\n+\treset_lstat_cache(0, 0);\n+}\n+\n #define USE_ONLY_LSTAT  0\n \n /* Return non-zero if path 'name' has a leading symlink component.\n-- \n1.6.0.2.GIT\n"},{"id":"100308","messageId":"7viqoj6jv7.fsf@gitster.siamese.dyndns.org","threadId":"17144","inReplyTo":"1231849748-8244-1-git-send-email-barvik@broadpark.no","subject":"Re: [PATCH/RFC v7 0/5] git checkout: optimise away lots of lstat() calls","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2009-01-13T20:17:48Z","receivedAt":"2009-01-13T20:17:48Z","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> Junio, I hope it is possible to use patches 1/5, 2/5 and 3/5 from this\n> version instead of 1/3, 2/3 and 3/3 from version 6, for the possible\n> future in origin/pu?  See also a) above.  Thanks in advance!\n>\n> In general, are we allowed to redesign the patch-series while the\n> patches is inside origin/pu?\n\nYou won't be too far off if you thought of 'pu' branch nothing more than\nmy bookmarks into the list archive.  They are interesting enough to keep\nan eye on their evolution but not yet stable enough to go into initial\nround of wider testing and incremental development which starts to happen\nwhen they hit 'next'.\n\nSo yes, while you are not yet confident that the series does not need\nmajor redesign, please keep sending replacements (not incremental\nupdates), making it clear that you still have reservations and I'll keep\nthem in 'pu', until the initial barrage of \"Oh, I think this way is\nbetter\", \"The previous review comments were valuable, and this round\ncontains all of them\" is over and things seem to stabilize into a testable\nshape.\n\nPersonally I felt your v5 and later ones were already 'next' material, and\nthe only reason why the series haven't landed on 'next' was because you\nkept sending updates before I sat down in the evening and said \"Ok, this\nlooks good---let's merge it to 'next'\".  Instead I ended up saying \"Hmph,\nI thought it looked good already but the author seems not satisfied yet;\nthere is another round of update to replace the previous one.  Let's queue\nit in 'pu', as it may be updated again, and I have to also look at series\nfrom other people.' ;-)\n"}]}