{"thread":{"id":"42833","subject":"[RFC] Speed up git status via a file system daemon","startedAt":"2016-07-13T15:53:27Z","lastAt":"2016-07-13T15:53:27Z","messageCount":1,"participants":["Ben Peart"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"291355","messageId":"1468424317-5368-1-git-send-email-peartben@gmail.com","threadId":"42833","inReplyTo":null,"subject":"[RFC] Speed up git status via a file system daemon","fromName":"Ben Peart","fromEmail":"peartben@gmail.com","sentAt":"2016-07-13T15:38:37Z","receivedAt":"2016-07-13T15:53:27Z","isPatch":false,"sender":{"key":"benpeart@microsoft.com","avatar":"https://avatars.githubusercontent.com/u/15252029?v=4"},"body":"Idea taken and code refactored from [1]:\n\nThe intent of this patch series is to separate the index-helper logic\nfrom the Watchman logic.  With very large repos, the percentage of time\nrequired to read the index from disk becomes a much smaller percentage\nof the overall time.  The Watchman logic provides a huge performance win\nfor git status (8 seconds vs 12 minutes in our testing) vs the minimal\nbenefits index-helper provides (<1 second).\n\nThe current index-helper/watchman combination design requires two\ndaemons, IPC between git and the index-helper, IPC between the index\nhelper and Watchman, shared memory, adding a WAMA extension to the\nindex, etc.\n\nThe benefit of splitting these two efforts is a significantly simpler\nset of changes that give the benefits of utilizing a file system\nmonitoring daemon like Watchman without the additional complexity and\noverhead associated with index-helper.\n\nThe overall design of this refactored patch series is that when the\nindex is read from disk, a hook proc is called that returns the list of\npotentially changed files.  Git then uses this set of files to flag the\npotentially dirty index and untracked cache entries.\n\nThe logic to use this information to limit the scope of which files and\ndirectories need to be checked for changes is the largely the same as\nthe original patch series.\n\nOne benefit of the hook proc is that it provides a simple, platform \nindependent way to interface with the file system daemon.  It does not\nrequire another daemon to be running to act as an intermediary between\ngit and the file system daemon to support communicating via named pipes \nor sockets.\n\nThe prototype currently has no mechanism for saving the date/time of the\nquery into the index so the list of potentially changed files grows\nunbounded. Writing the additional 64 bit date/time data into an optional\nextension seems like a lot of overhead but changing the on disk index\nformat is expensive as well from a compatibility perspective.  Other\nideas or suggestions welcome.\n\nThanks,\n\nBen\n\n[1] http://article.gmane.org/gmane.comp.version-control.git/298243\n\n---\n cache.h      |   4 ++\n dir.c        |  14 ++++-\n dir.h        |   5 ++\n read-cache.c | 174 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-\n 4 files changed, 194 insertions(+), 3 deletions(-)\n\ndiff --git a/cache.h b/cache.h\nindex f1dc289..45c2eff 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -182,6 +182,8 @@ struct cache_entry {\n #define CE_VALID     (0x8000)\n #define CE_STAGESHIFT 12\n \n+#define CE_FSDAEMON_DIRTY  (0x0001)\n+\n /*\n  * Range 0xFFFF0FFF in ce_flags is divided into\n  * two parts: in-memory flags and on-disk ones.\n@@ -338,6 +340,8 @@ struct index_state {\n \tstruct hashmap dir_hash;\n \tunsigned char sha1[20];\n \tstruct untracked_cache *untracked;\n+\t/* BENPEART-TODO: persist last_update in the index, use gmtime? */\n+\ttime_t last_update;\n };\n \n extern struct index_state the_index;\ndiff --git a/dir.c b/dir.c\nindex 6172b34..bce921f 100644\n--- a/dir.c\n+++ b/dir.c\n@@ -584,7 +584,7 @@ static void trim_trailing_spaces(char *buf)\n  *\n  * If \"name\" has the trailing slash, it'll be excluded in the search.\n  */\n-static struct untracked_cache_dir *lookup_untracked(struct untracked_cache *uc,\n+struct untracked_cache_dir *lookup_untracked(struct untracked_cache *uc,\n \t\t\t\t\t\t    struct untracked_cache_dir *dir,\n \t\t\t\t\t\t    const char *name, int len)\n {\n@@ -1551,6 +1551,17 @@ static int valid_cached_dir(struct dir_struct *dir,\n \tif (!untracked)\n \t\treturn 0;\n \n+\tif (dir->untracked->use_fsdaemon) {\n+\t\t/*\n+\t\t * With file system daemon, we can trust the untracked cache's\n+\t\t * valid field.\n+\t\t */\n+\t\tif (untracked->valid)\n+\t\t\tgoto skip_stat;\n+\t\telse\n+\t\t\tinvalidate_directory(dir->untracked, untracked);\n+\t}\n+\n \tif (stat(path->len ? path->buf : \".\", &st)) {\n \t\tinvalidate_directory(dir->untracked, untracked);\n \t\tmemset(&untracked->stat_data, 0, sizeof(untracked->stat_data));\n@@ -1564,6 +1575,7 @@ static int valid_cached_dir(struct dir_struct *dir,\n \t\treturn 0;\n \t}\n \n+skip_stat:\n \tif (untracked->check_only != !!check_only) {\n \t\tinvalidate_directory(dir->untracked, untracked);\n \t\treturn 0;\ndiff --git a/dir.h b/dir.h\nindex bfde698..8b7b98a 100644\n--- a/dir.h\n+++ b/dir.h\n@@ -139,6 +139,8 @@ struct untracked_cache {\n \tint gitignore_invalidated;\n \tint dir_invalidated;\n \tint dir_opened;\n+\t/* file system daemon invalidation data */\n+\tunsigned int use_fsdaemon : 1;\n };\n \n struct dir_struct {\n@@ -308,4 +310,7 @@ struct untracked_cache *read_untracked_extension(const void *data, unsigned long\n void write_untracked_extension(struct strbuf *out, struct untracked_cache *untracked);\n void add_untracked_cache(struct index_state *istate);\n void remove_untracked_cache(struct index_state *istate);\n+struct untracked_cache_dir *lookup_untracked(struct untracked_cache *uc,\n+\t\t\t\t\t     struct untracked_cache_dir *dir,\n+\t\t\t\t\t     const char *name, int len);\n #endif\ndiff --git a/read-cache.c b/read-cache.c\nindex db27766..5478c49 100644\n--- a/read-cache.c\n+++ b/read-cache.c\n@@ -18,6 +18,7 @@\n #include \"varint.h\"\n #include \"split-index.h\"\n #include \"utf8.h\"\n+#include \"run-command.h\"\n \n static struct cache_entry *refresh_cache_entry(struct cache_entry *ce,\n \t\t\t\t\t       unsigned int options);\n@@ -1222,8 +1223,11 @@ int refresh_index(struct index_state *istate, unsigned int flags,\n \t\t\tcontinue;\n \n \t\tnew = refresh_cache_ent(istate, ce, options, &cache_errno, &changed);\n-\t\tif (new == ce)\n+\t\tif (new == ce) {\n+\t\t\tce->ce_flags &= ~CE_FSDAEMON_DIRTY;\n \t\t\tcontinue;\n+\t\t}\n+\n \t\tif (!new) {\n \t\t\tconst char *fmt;\n \n@@ -1367,6 +1371,30 @@ static int verify_hdr(struct cache_header *hdr, unsigned long size)\n \treturn 0;\n }\n \n+static struct untracked_cache_dir *find_untracked_cache_dir(\n+\tstruct untracked_cache *uc, struct untracked_cache_dir *ucd,\n+\tconst char *name)\n+{\n+\tint component_len;\n+\tconst char *end;\n+\tstruct untracked_cache_dir *dir;\n+\n+\tif (!*name)\n+\t\treturn ucd;\n+\n+\tend = strrchr(name, '/');\n+\tif (end)\n+\t\tcomponent_len = end - name;\n+\telse\n+\t\tcomponent_len = strlen(name);\n+\n+\tdir = lookup_untracked(uc, ucd, name, component_len);\n+\tif (dir)\n+\t\treturn find_untracked_cache_dir(uc, dir, name + component_len + 1);\n+\n+\treturn NULL;\n+}\n+\n static int read_index_extension(struct index_state *istate,\n \t\t\t\tconst char *ext, void *data, unsigned long sz)\n {\n@@ -1544,6 +1572,143 @@ static void post_read_index_from(struct index_state *istate)\n \ttweak_untracked_cache(istate);\n }\n \n+/*\n+* Call the query-fsdaemon hook passing the date time of the last saved results.\n+* Returns the list of files changed on success (may be empty) or NULL on error.\n+*/\n+struct string_list *query_fsdaemon(time_t last_update)\n+{\n+\tstruct child_process cp = CHILD_PROCESS_INIT;\n+\tchar date[64];\n+\tstruct strbuf buffer = STRBUF_INIT;\n+\tstruct string_list *res;\n+\tconst char *argv[3];\n+\tchar *buf, *entry;\n+\tint i, ret;\n+\n+\tif (!(argv[0] = find_hook(\"query-fsdaemon\")))\n+\t\treturn NULL;\n+\n+\tsnprintf(date, sizeof(date), \"%lu\", last_update);\n+\targv[1] = date;\n+\targv[2] = NULL;\n+\tcp.argv = argv;\n+\tcp.out = -1;\n+\n+\tret = capture_command(&cp, &buffer, 1024);\n+\tif (ret) {\n+\t\tstrbuf_release(&buffer);\n+\t\treturn NULL;\n+\t}\n+\n+\t/*\n+\t * Read the results into a string_list for easy processing\n+\t */\n+\tres = xcalloc(1, sizeof(struct string_list));\n+\tres->strdup_strings = 1;\n+\tbuf = entry = buffer.buf;\n+\tfor (i = 0; i < buffer.len; i++) {\n+\t\tif (buf[i] == '\\n') {\n+\t\t\tif (entry != buf + i) {\n+\t\t\t\tbuf[i - (i && buf[i - 1] == '\\r')] = 0;\n+\t\t\t\tstring_list_append(res, entry);\n+\t\t\t}\n+\t\t\tentry = buf + i + 1;\n+\t\t}\n+\t}\n+\n+\tstrbuf_release(&buffer);\n+\treturn res;\n+}\n+\n+static int update_istate(struct string_list_item *item, void *is)\n+{\n+\tstruct index_state *istate = is;\n+\tint pos;\n+\n+\t/*\n+\t * find it in the index and mark that entry as dirty\n+\t */\n+\tpos = index_name_pos(istate, item->string, strlen(item->string));\n+\tif (pos >= 0)\n+\t\tistate->cache[pos]->ce_flags |= CE_FSDAEMON_DIRTY;\n+\n+\t/*\n+\t * Find the corresponding directory in the untracked cache\n+\t * and mark it as invalid\n+\t */\n+\tif (istate->untracked) {\n+\t\tstruct untracked_cache_dir *dir;\n+\n+\t\tdir = find_untracked_cache_dir(istate->untracked, istate->untracked->root, item->string);\n+\t\tif (dir)\n+\t\t\tdir->valid = 0;\n+\t}\n+\n+\treturn 0;\n+}\n+\n+static void refresh_by_fsdaemon(struct index_state *istate)\n+{\n+\tstruct string_list *changes = NULL;\n+\ttime_t last_update;\n+\tint i;\n+\n+\t/*\n+\t * This could be racy so save the date/time now and the hook\n+\t * should be inclusive to ensure we don't miss potential changes.\n+\t */\n+\tlast_update = time(NULL);\n+\n+\tchanges = query_fsdaemon(istate->last_update);\n+\n+\t// if we can't update the cache, fall back to checking them all\n+\tif (!changes) {\n+\t\t/* let refresh clear them later */\n+\t\tfor (i = 0; i < istate->cache_nr; i++)\n+\t\t\tistate->cache[i]->ce_flags |= CE_FSDAEMON_DIRTY;\n+\n+\t\t/* mark all untracked cache entries as invalid */\n+\t\tif (istate->untracked)\n+\t\t\tistate->untracked->use_fsdaemon = 0;\n+\t\treturn;\n+\t}\n+\n+\t/* TODO: potential optimizations\n+\t *\t- dedupe entries via string_list_remove_duplicates\n+\t *  - build seperate list of directories for untracked cache\n+\t *    and dedupe it before marking them invalid\n+\t */\n+\n+\t/*\n+\t * Loop through list of changed files and mark all corresponding\n+\t * index entries and untracked cache directories as dirty.\n+\t */\n+\tfor_each_string_list(changes, update_istate, istate);\n+\n+\t/*\n+\t * Now that we've marked the invalid entries in the\n+\t * untracked-cache itself, we can mark the untracked cache for\n+\t * fsdaemon usage.\n+\t */\n+\tif (istate->untracked)\n+\t\tistate->untracked->use_fsdaemon = 1;\n+\n+\t/*\n+\t * Mark all clean entries up-to-date\n+\t */\n+\tfor (i = 0; i < istate->cache_nr; i++) {\n+\t\tstruct cache_entry *ce = istate->cache[i];\n+\t\tif (ce_stage(ce) || (ce->ce_flags & CE_FSDAEMON_DIRTY))\n+\t\t\tcontinue;\n+\t\tce_mark_uptodate(ce);\n+\t}\n+\tstring_list_clear(changes, 0);\n+\n+\t/* Now that we've updated istate, save the last_update time */\n+\tistate->last_update = last_update;\n+}\n+\n /* remember to discard_cache() before reading a different cache! */\n int do_read_index(struct index_state *istate, const char *path, int must_exist)\n {\n@@ -1651,7 +1816,7 @@ int read_index_from(struct index_state *istate, const char *path)\n \tsplit_index = istate->split_index;\n \tif (!split_index || is_null_sha1(split_index->base_sha1)) {\n \t\tpost_read_index_from(istate);\n-\t\treturn ret;\n+\t\tgoto done;\n \t}\n \n \tif (split_index->base)\n@@ -1669,6 +1834,11 @@ int read_index_from(struct index_state *istate, const char *path)\n \t\t    sha1_to_hex(split_index->base->sha1));\n \tmerge_base_index(istate);\n \tpost_read_index_from(istate);\n+\n+done:\n+\tif (ret > 0)\n+\t\trefresh_by_fsdaemon(istate);\n+\n \treturn ret;\n }\n \n-- \n2.8.2.windows.1.4.gdf2cc46.dirty\n\n"}]}