{"thread":{"id":"17037","subject":"[PATCH/RFC v3 1/2] Optimised, faster, more effective symlink/directory detection","startedAt":"2009-01-07T13:24:47Z","lastAt":"2009-01-09T10:20:18Z","messageCount":4,"participants":["Kjetil Barvik","Pete Harlan"],"isPatch":true,"patchVersion":3,"patchTotal":2},"messages":[{"id":"99579","messageId":"1231334689-17135-1-git-send-email-barvik@broadpark.no","threadId":"17037","inReplyTo":null,"subject":"[PATCH/RFC v3 0/2] git checkout: optimise away lots of lstat() calls","fromName":"Kjetil Barvik","fromEmail":"barvik@broadpark.no","sentAt":"2009-01-07T13:24:47Z","receivedAt":"2009-01-07T13:24:47Z","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 2 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\nBoth patches is against git master, and the git 'make test' test suite\nstill passes after each patch.\n\nTo document the improvement, below is some numbers, which compares\nbefore and after the 2 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 2\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 2 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\nI have also noticed that inside the unlink_entry() function in file\nunpack-trees.c, one could often end up calling rmdir() lots and lots\nof times on none-empty directories.  Maybe one should schedule each\ndirectory for removal by an appropriate function, and then at the end\ncall a new function to clean all the directories at once?\n\nComments?\n\n----\n  Changes since v2:\n  = inside patch 1/2\n      [[Following is updates after comments from Linus Torvalds - Thanks!]]\n    - simplified the interface: introduce 2 static inline functions\n      has_symlink_leading_path() and has_symlink_or_noent_leading_path()\n    - similar, introduce 2 defines: clear_symlink_cache() and\n      clear_symlink_or_noent_cache()\n    - reorganise the patches: previous patch 2/4 and 4/4 is put into\n      this one\n    - update the commit message accordingly\n    - keep the symlinks.c file\n  = inside patch 2/2\n    - was patch 3/4 in v2\n    - always null terminate the dirs_path array\n    - update the patch with some of the comments regarding patch 1/4\n      from Junio C Hamano\n\n  Changes since v1:\n  = inside patch 1/4\n    - always null terminate the cache_path array\n    - added a paragraph to the commit message for this patch\n    - small cleanup on 2 comments, and a small line indentation change\n      [[Following is updates after comments from Junio C Hamano - Thanks!]]\n    - removed the 'static inline update_path_cache()' function\n    - replaced the else-part of the above inline function with a call\n      to the 'clear_lstat_cache()' function.\n    - deleted the '|| errno == ENOTDIR' part inside the big while-loop\n      inside check_lstat_cache(), and updated the named BIT-fields\n      accordingly\n  = inside patch 2/4\n    - moved a paragraph out from the commit message for this patch and\n      into this cover-letter\n      [[Following is updates after comments from Junio C Hamano - Thanks!]]\n    - Removed the '|LSTAT_NOTDIR' part from the call to lstat_cache()\n      inside function 'check_removed()' inside file diff-lib.c\n\n\nKjetil Barvik (2):\n  Optimised, faster, more effective symlink/directory detection\n  create_directories() inside entry.c: only check each directory once!\n\n builtin-add.c          |    1 +\n builtin-apply.c        |    1 +\n builtin-update-index.c |    1 +\n cache.h                |   23 +++++++++-\n diff-lib.c             |    1 +\n entry.c                |   82 +++++++++++++++++++++++++-------\n symlinks.c             |  123 +++++++++++++++++++++++++++++++-----------------\n unpack-trees.c         |    6 ++-\n 8 files changed, 173 insertions(+), 65 deletions(-)\n"},{"id":"99577","messageId":"1231334689-17135-2-git-send-email-barvik@broadpark.no","threadId":"17037","inReplyTo":"1231334689-17135-1-git-send-email-barvik@broadpark.no","subject":"[PATCH/RFC v3 1/2] Optimised, faster, more effective symlink/directory detection","fromName":"Kjetil Barvik","fromEmail":"barvik@broadpark.no","sentAt":"2009-01-07T13:24:48Z","receivedAt":"2009-01-07T13:24:48Z","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\" 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- 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 known that the paths \"A\", \"A/B\"\n  and \"A/B/C\" is real directories.  Since we now only store one single\n  path (the last one), we also get similar logic for free regarding\n  the new \"non-exsisting-directory-cache\".\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 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... 768ba38... M\tcache.h\n:100644 100644 ae96c64... c9caa0e... M\tdiff-lib.c\n:100644 100644 5a5e781... 2f025c8... M\tsymlinks.c\n:100644 100644 54f301d... 28e2759... M\tunpack-trees.c\n builtin-add.c          |    1 +\n builtin-apply.c        |    1 +\n builtin-update-index.c |    1 +\n cache.h                |   22 ++++++++-\n diff-lib.c             |    1 +\n symlinks.c             |  123 +++++++++++++++++++++++++++++++-----------------\n unpack-trees.c         |    5 +-\n 7 files changed, 107 insertions(+), 47 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..768ba3825f3015828381490b0c387177a4f71578 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -719,7 +719,27 @@ 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_DIR       (1u << 0)\n+#define LSTAT_NOENT     (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+extern void clear_lstat_cache(void);\n+static inline unsigned int has_symlink_leading_path(int len, const char *name)\n+{\n+\treturn check_lstat_cache(len, name, LSTAT_SYMLINK|LSTAT_DIR) &\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 check_lstat_cache(len, name, LSTAT_SYMLINK|LSTAT_NOENT|LSTAT_DIR) &\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/symlinks.c b/symlinks.c\nindex 5a5e781a15d7d9cb60797958433eca896b31ec85..2f025c87b0be0e713af7b1400e71284a22c25e9f 100644\n--- a/symlinks.c\n+++ b/symlinks.c\n@@ -1,64 +1,99 @@\n #include \"cache.h\"\n \n-struct pathname {\n-\tint len;\n-\tchar path[PATH_MAX];\n-};\n+static char         cache_path[PATH_MAX];\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\n+greatest_common_path_cache_prefix(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+\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 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-\tstatic struct pathname link, nonlink;\n-\tchar path[PATH_MAX];\n+\tint match_len, last_slash, max_len;\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-\tif (match_pathname(len, name, &link))\n-\t\treturn 1;\n+\tmatch_len = last_slash =\n+\t\tgreatest_common_path_cache_prefix(len, name);\n+\tmatch_flags =\n+\t\tcache_flags & track_flags & (LSTAT_NOENT|LSTAT_SYMLINK);\n+\tif (match_flags && match_len == cache_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-\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+\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(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 = 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\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 {\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 can be cached for the moment!\n+\t */\n+\tsave_flags = ret_flags & track_flags &\n+\t\t(LSTAT_NOENT|LSTAT_SYMLINK|LSTAT_DIR);\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 {\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..28e275981a21b033459ef9c7e420cce4bf7e5513 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@@ -584,7 +585,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":"99578","messageId":"1231334689-17135-3-git-send-email-barvik@broadpark.no","threadId":"17037","inReplyTo":"1231334689-17135-1-git-send-email-barvik@broadpark.no","subject":"[PATCH/RFC v3 2/2] create_directories() inside entry.c: only check each directory once!","fromName":"Kjetil Barvik","fromEmail":"barvik@broadpark.no","sentAt":"2009-01-07T13:24:49Z","receivedAt":"2009-01-07T13:24:49Z","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 768ba38... ec1297f... M\tcache.h\n:100644 100644 aa2ee46... 36d6f98... M\tentry.c\n:100644 100644 28e2759... 0a03e65... M\tunpack-trees.c\n cache.h        |    1 +\n entry.c        |   82 +++++++++++++++++++++++++++++++++++++++++++------------\n unpack-trees.c |    1 +\n 3 files changed, 66 insertions(+), 18 deletions(-)\n\ndiff --git a/cache.h b/cache.h\nindex 768ba3825f3015828381490b0c387177a4f71578..ec1297ff5621cc9eb7fce51cc025f18a030ac9ea 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 \n #define LSTAT_DIR       (1u << 0)\ndiff --git a/entry.c b/entry.c\nindex aa2ee46a84033585d8e07a585610c5a697af82c2..36d6f98c1f59a86a5e9c117e1181c1169208168f 100644\n--- a/entry.c\n+++ b/entry.c\n@@ -1,33 +1,67 @@\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-\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_path[0] = '\\0';\n+\tdirs_len     = 0;\n+}\n \n-\t\tif (len <= state->base_dir_len)\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+\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 +72,20 @@ 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+\t/* Update the cache of already created/checked directories */\n+\tif (last_slash > 0 && last_slash < PATH_MAX) {\n+\t\tdirs_path[last_slash] = '\\0';\n+\t\tdirs_len = last_slash;\n+\t} else {\n+\t\tclear_created_dirs_cache();\n+\t}\n }\n \n static void remove_subtree(const char *path)\n@@ -55,6 +95,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@@ -201,6 +246,7 @@ int checkout_entry(struct cache_entry *ce, const struct checkout *state, char *t\n \n \tmemcpy(path, state->base_dir, len);\n \tstrcpy(path + len, ce->name);\n+\tlen += 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 +275,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(len, path, state);\n \treturn write_entry(ce, path, state, 0);\n }\ndiff --git a/unpack-trees.c b/unpack-trees.c\nindex 28e275981a21b033459ef9c7e420cce4bf7e5513..0a03e65f9c9d869ab2d8b3c337f032ff2b8e7b2f 100644\n--- a/unpack-trees.c\n+++ b/unpack-trees.c\n@@ -119,6 +119,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":"99779","messageId":"496724E2.6010907@pcharlan.com","threadId":"17037","inReplyTo":"1231334689-17135-2-git-send-email-barvik@broadpark.no","subject":"Re: [PATCH/RFC v3 1/2] Optimised, faster, more effective symlink/directory detection","fromName":"Pete Harlan","fromEmail":"pgit@pcharlan.com","sentAt":"2009-01-09T10:20:18Z","receivedAt":"2009-01-09T10:20:18Z","isPatch":true,"sender":{"key":"pgit@pcharlan.com","avatar":null},"body":"Here are some suggestions for the commit message.\n\nKjetil Barvik wrote:\n> 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\" is already tested, and we only need to do an\n\nis -> are\n\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\nit's -> its\n\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\nseams -> seems\n\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 known that the paths \"A\", \"A/B\"\n\nknown -> knew\n\n>   and \"A/B/C\" is real directories.  Since we now only store one single\n\nis -> are\n\n>   path (the last one), we also get similar logic for free regarding\n>   the new \"non-exsisting-directory-cache\".\n> \n> - Avoid copying the first path components of the name 2 zillions times\n\nzillions -> zillion\n\n>   when we tests new path components.  Since we always cache/store the\n\ntests -> test\n\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\nan -> a\n\n> \n> - We also use less memory, that is PATH_MAX bytes less memory on the\n\nis -> is,\n\n>   stack and PATH_MAX bytes less memory on the heap.\n\nCheers,\n\n--Pete\n"}]}