{"thread":{"id":"47137","subject":"[RFC] fastindex: parallelize index load","startedAt":"2017-11-08T14:43:26Z","lastAt":"2017-11-08T14:51:12Z","messageCount":3,"participants":["Ben Peart"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"332077","messageId":"20171108144253.34428-1-benpeart@microsoft.com","threadId":"47137","inReplyTo":null,"subject":"[RFC] fastindex: parallelize index load","fromName":"Ben Peart","fromEmail":"benpeart@microsoft.com","sentAt":"2017-11-08T14:42:53Z","receivedAt":"2017-11-08T14:43:26Z","isPatch":false,"sender":{"key":"benpeart@microsoft.com","avatar":"https://avatars.githubusercontent.com/u/15252029?v=4"},"body":"This patch will address the CPU cost of loading the index by adding\nadditional data to the index that will allow us to multi-thread the\nloading and conversion of cache entries.\n\nIt accomplishes this by adding an (optional) index extension that is a\ntable of offsets to blocks of cache entries in the index file.  With\nversion 2, 3 or even 4 indexes, we can utilize the Index Entry Offset Table\n(IEOT) to parallelize the loading and conversion of the cache entries\nacross all available CPU cores.\n\nTo make this work for V4 indexes, when writing the index, it periodically\n\"resets\" the compression by encoding the current entry as if the path\nname for the previous entry is completely different and saves the offset\nof that entry in the IEOT.  Basically, with V4 indexes, it generates\noffsets into blocks of prefix-compressed entries.\n\nTo enable reading the IEOT extension before reading all the variable\nlength cache entries and other extensions, the IEOT is written last,\nright before the trailing SHA1.\n\nThe format of that extension has the signature bytes and size at the\nbeginning (like a normal extension) as well as at the end in reverse\norder to enable parsing the extension by seeking back from the end of\nthe file.  See the diagram below for details.\n\nDuring index load, read the index header then seek to the end of the\nindex, back up past the trailing SHA1 and look for the IEOT extension\nsignature bytes.  If they exist, read the 32-bit size and seek back to\nthe extension header and verify the leading header and size bits.  If\nthey all match, we can be assured we have a valid IEOT extension.\n\nIf the IEOT extension is available, create multiple threads to divide\nthe work of loading and converting the cache entries across all\navailable CPU cores.  Once the cache entries are loaded, the rest of the\nextensions can be loaded and processed normally (skipping the IEOT entry\nas it has already been processed).  If the IEOT extension is not\navailable then parsing the index will proceed as usual with a single thread.\n\nThe on-disk format looks like this:\n\nIndex header\nCache entry 1\nCache entry 2\n.\n.\nExtension 1\nExtension 2\n.\n.\nIndex Entry Offset Table Extension (must be written last!)\nIEOT signature bytes\n32-bit size\n32-bit version\n32-bit Cache Entry Offset 1\n32-bit Cache Entry count\n32-bit Cache Entry Offset 2\n32-bit Cache Entry count\n.\n.\n32-bit version\n32-bit size\nIEOT signature bytes\nSHA1\n\nSigned-off-by: Ben Peart <benpeart@microsoft.com>\n---\n\nNotes:\n    Base Ref: v2.14.3.windows.1\n    Web-Diff: https://github.com/benpeart/git/commit/1e818c7835\n    Checkout: git fetch https://github.com/benpeart/git fastindex-v1 && git checkout 1e818c7835\n\n Makefile                  |   2 +\n cache.h                   |  18 +++\n config.c                  |  20 +++\n config.h                  |   1 +\n environment.c             |   3 +\n read-cache.c              | 340 +++++++++++++++++++++++++++++++++++++++++++---\n t/helper/test-dump-ieot.c |  78 +++++++++++\n t/helper/test-ieot.c      |  72 ++++++++++\n 8 files changed, 513 insertions(+), 21 deletions(-)\n create mode 100644 t/helper/test-dump-ieot.c\n create mode 100644 t/helper/test-ieot.c\n\ndiff --git a/Makefile b/Makefile\nindex ebd0a75d87..99fa8dd8d3 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -640,12 +640,14 @@ TEST_PROGRAMS_NEED_X += test-config\n TEST_PROGRAMS_NEED_X += test-date\n TEST_PROGRAMS_NEED_X += test-delta\n TEST_PROGRAMS_NEED_X += test-dump-cache-tree\n+TEST_PROGRAMS_NEED_X += test-dump-ieot\n TEST_PROGRAMS_NEED_X += test-dump-split-index\n TEST_PROGRAMS_NEED_X += test-dump-untracked-cache\n TEST_PROGRAMS_NEED_X += test-fake-ssh\n TEST_PROGRAMS_NEED_X += test-genrandom\n TEST_PROGRAMS_NEED_X += test-hashmap\n TEST_PROGRAMS_NEED_X += test-helper\n+TEST_PROGRAMS_NEED_X += test-ieot\n TEST_PROGRAMS_NEED_X += test-index-version\n TEST_PROGRAMS_NEED_X += test-lazy-init-name-hash\n TEST_PROGRAMS_NEED_X += test-line-buffer\ndiff --git a/cache.h b/cache.h\nindex 45597732d8..e9ec1bf41a 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -326,6 +326,7 @@ static inline unsigned int canon_mode(unsigned int mode)\n #define CACHE_TREE_CHANGED\t(1 << 5)\n #define SPLIT_INDEX_ORDERED\t(1 << 6)\n #define UNTRACKED_CHANGED\t(1 << 7)\n+#define IEOT_CHANGED\t\t(1 << 9)\n \n struct split_index;\n struct untracked_cache;\n@@ -770,6 +771,7 @@ extern char *git_replace_ref_base;\n \n extern int fsync_object_files;\n extern int core_preload_index;\n+extern int core_fast_index;\n extern int core_apply_sparse_checkout;\n extern int precomposed_unicode;\n extern int protect_hfs;\n@@ -2025,4 +2027,20 @@ void sleep_millisec(int millisec);\n  */\n void safe_create_dir(const char *dir, int share);\n \n+\n+#ifndef NO_PTHREADS\n+struct index_entry_offset\n+{\t// starting byte offset into index file, count of index entries in this block\n+\tint offset, nr;\n+};\n+\n+struct index_entry_offset_table\n+{\n+\tint nr;\t\t\t\t// number of ieot entries in array\n+\tstruct index_entry_offset entries[0];\n+};\n+\n+struct index_entry_offset_table *read_ieot_extension(void *mmap, size_t mmap_size);\n+#endif\n+\n #endif /* CACHE_H */\ndiff --git a/config.c b/config.c\nindex adcd2c2441..056c21b0c9 100644\n--- a/config.c\n+++ b/config.c\n@@ -1203,6 +1203,11 @@ static int git_default_core_config(const char *var, const char *value, void *cb)\n \t\treturn 0;\n \t}\n \n+\tif (!strcmp(var, \"core.fastindex\")) {\n+\t\tcore_fast_index = git_config_bool(var, value);\n+\t\treturn 0;\n+\t}\n+\n \tif (!strcmp(var, \"core.createobject\")) {\n \t\tif (!strcmp(value, \"rename\"))\n \t\t\tobject_creation_mode = OBJECT_CREATION_USES_RENAMES;\n@@ -2116,6 +2121,21 @@ int git_config_get_max_percent_split_change(void)\n \treturn -1; /* default value */\n }\n \n+int ignore_fast_index_config;\n+int git_config_get_fast_index(void)\n+{\n+\tint val;\n+\n+\t/* Hack for test programs like test-ieot */\n+\tif (ignore_fast_index_config)\n+\t\treturn core_fast_index;\n+\n+\tif (!git_config_get_maybe_bool(\"core.fastindex\", &val))\n+\t\treturn val;\n+\n+\treturn -1; /* default value */\n+}\n+\n NORETURN\n void git_die_config_linenr(const char *key, const char *filename, int linenr)\n {\ndiff --git a/config.h b/config.h\nindex 0352da117b..bb73c36e0a 100644\n--- a/config.h\n+++ b/config.h\n@@ -201,6 +201,7 @@ extern int git_config_get_pathname(const char *key, const char **dest);\n extern int git_config_get_untracked_cache(void);\n extern int git_config_get_split_index(void);\n extern int git_config_get_max_percent_split_change(void);\n+extern int git_config_get_fast_index(void);\n \n /* This dies if the configured or default date is in the future */\n extern int git_config_get_expiry(const char *key, const char **output);\ndiff --git a/environment.c b/environment.c\nindex c974bed180..bb8405cd91 100644\n--- a/environment.c\n+++ b/environment.c\n@@ -86,6 +86,9 @@ int auto_comment_line_char;\n /* Parallel index stat data preload? */\n int core_preload_index = 1;\n \n+/* Parallel index cache entry loading? */\n+int core_fast_index;\n+\n /*\n  * This is a hack for test programs like test-dump-untracked-cache to\n  * ensure that they do not modify the untracked cache when reading it.\ndiff --git a/read-cache.c b/read-cache.c\nindex bc925b6736..dc2fadb61f 100644\n--- a/read-cache.c\n+++ b/read-cache.c\n@@ -19,6 +19,7 @@\n #include \"varint.h\"\n #include \"split-index.h\"\n #include \"utf8.h\"\n+#include \"thread-utils.h\"\n \n #ifndef NO_PTHREADS\n #include <pthread.h>\n@@ -42,11 +43,12 @@\n #define CACHE_EXT_RESOLVE_UNDO 0x52455543 /* \"REUC\" */\n #define CACHE_EXT_LINK 0x6c696e6b\t  /* \"link\" */\n #define CACHE_EXT_UNTRACKED 0x554E5452\t  /* \"UNTR\" */\n+#define CACHE_EXT_FASTINDEX 0x49454F54\t  /* \"IEOT\" */\n \n /* changes that can be kept in $GIT_DIR/index (basically all extensions) */\n #define EXTMASK (RESOLVE_UNDO_CHANGED | CACHE_TREE_CHANGED | \\\n \t\t CE_ENTRY_ADDED | CE_ENTRY_REMOVED | CE_ENTRY_CHANGED | \\\n-\t\t SPLIT_INDEX_ORDERED | UNTRACKED_CHANGED)\n+\t\t SPLIT_INDEX_ORDERED | UNTRACKED_CHANGED | CACHE_EXT_FASTINDEX)\n \n struct index_state the_index;\n static const char *alternate_index_output;\n@@ -1581,6 +1583,9 @@ static int read_index_extension(struct index_state *istate,\n \tcase CACHE_EXT_UNTRACKED:\n \t\tistate->untracked = read_untracked_extension(data, sz);\n \t\tbreak;\n+\tcase CACHE_EXT_FASTINDEX:\n+\t\t/* already handled in do_read_index() */\n+\t\tbreak;\n \tdefault:\n \t\tif (*ext < 'A' || 'Z' < *ext)\n \t\t\treturn error(\"index uses %.4s extension, which we do not understand\",\n@@ -1634,10 +1639,12 @@ static struct cache_entry *cache_entry_from_ondisk(struct ondisk_cache_entry *on\n  * number of bytes to be stripped from the end of the previous name,\n  * and the bytes to append to the result, to come up with its name.\n  */\n-static unsigned long expand_name_field(struct strbuf *name, const char *cp_)\n+static unsigned long expand_name_field(struct strbuf *name, const char *cp_, int use_length)\n {\n \tconst unsigned char *ep, *cp = (const unsigned char *)cp_;\n \tsize_t len = decode_varint(&cp);\n+\tif (!use_length)\n+\t\tlen = name->len;\n \n \tif (name->len < len)\n \t\tdie(\"malformed name field in the index\");\n@@ -1648,9 +1655,10 @@ static unsigned long expand_name_field(struct strbuf *name, const char *cp_)\n \treturn (const char *)ep + 1 - cp_;\n }\n \n-static struct cache_entry *create_from_disk(struct ondisk_cache_entry *ondisk,\n+struct cache_entry *create_from_disk(struct ondisk_cache_entry *ondisk,\n \t\t\t\t\t    unsigned long *ent_size,\n-\t\t\t\t\t    struct strbuf *previous_name)\n+\t\t\t\t\t    struct strbuf *previous_name,\n+\t\t\t\t\t\tint use_length)\n {\n \tstruct cache_entry *ce;\n \tsize_t len;\n@@ -1684,7 +1692,7 @@ static struct cache_entry *create_from_disk(struct ondisk_cache_entry *ondisk,\n \t\t*ent_size = ondisk_ce_size(ce);\n \t} else {\n \t\tunsigned long consumed;\n-\t\tconsumed = expand_name_field(previous_name, name);\n+\t\tconsumed = expand_name_field(previous_name, name, use_length);\n \t\tce = cache_entry_from_ondisk(ondisk, flags,\n \t\t\t\t\t     previous_name->buf,\n \t\t\t\t\t     previous_name->len);\n@@ -1755,16 +1763,208 @@ static void post_read_index_from(struct index_state *istate)\n \ttweak_split_index(istate);\n }\n \n+static unsigned long load_cache_entries(struct index_state *istate, int offset, int nr, void *mmap, unsigned long start_offset)\n+{\n+\tint i;\n+\tunsigned long src_offset = start_offset;\n+\tstruct strbuf previous_name_buf = STRBUF_INIT, *previous_name;\n+\n+\tif (istate->version == 4)\n+\t\tprevious_name = &previous_name_buf;\n+\telse\n+\t\tprevious_name = NULL;\n+\n+\tfor (i = offset; i < offset + nr; i++) {\n+\t\tstruct ondisk_cache_entry *disk_ce;\n+\t\tstruct cache_entry *ce;\n+\t\tunsigned long consumed;\n+\n+\t\tdisk_ce = (struct ondisk_cache_entry *)((char *)mmap + src_offset);\n+\t\tce = create_from_disk(disk_ce, &consumed, previous_name, i == offset ? 0 : 1);\n+\t\tset_index_entry(istate, i, ce);\n+\n+\t\tsrc_offset += consumed;\n+\t}\n+\tstrbuf_release(&previous_name_buf);\n+\treturn src_offset - start_offset;\n+}\n+\n+#ifndef NO_PTHREADS\n+\n+/*\n+ * Mostly randomly chosen cache entries per thread (it works on my machine):\n+ * we want to have at least 7500 cache entries per thread for it to\n+ * be worth starting a thread.\n+ */\n+#define THREAD_COST\t\t(7500)\n+#define IEOT_VERSION\t(1)\n+\n+static int ce_write(git_SHA_CTX *context, int fd, void *data, unsigned int len);\n+\n+static int write_index_ext_header(git_SHA_CTX *context, int fd,\n+\tunsigned int ext, unsigned int sz);\n+\n+struct load_cache_entries_thread_data\n+{\n+\tpthread_t pthread;\n+\tstruct index_state *istate;\n+\tint offset;\t\t\t// starting index into the istate->cache array\n+\tvoid *mmap;\t\t\t// pointer to memory mapped index file\n+\tunsigned long consumed;\t// return # of bytes in index file processed\n+\tstruct index_entry_offset_table *ieot;\t// pointer to ieot\n+\tint ieot_offset;\t// starting index into the ieot array\n+\tint ieot_work;\t\t// count of ieot entries to process\n+};\n+\n+/*\n+ * A thread proc to run the load_cache_entries() computation\n+ * across multiple background threads.\n+ */\n+static void *load_cache_entries_thread(void *_data)\n+{\n+\tstruct load_cache_entries_thread_data *p = _data;\n+\tint i;\n+\n+\t// itterate across all ieot blocks assigned to this thread\n+\tfor (i = p->ieot_offset; i < p->ieot_offset + p->ieot_work; i++) {\n+\t\tp->consumed += load_cache_entries(p->istate, p->offset, p->ieot->entries[i].nr, p->mmap, p->ieot->entries[i].offset);\n+\t\tp->offset += p->ieot->entries[i].nr;\n+\t}\n+\treturn NULL;\n+}\n+\n+struct index_entry_offset_table *read_ieot_extension(void *mmap, size_t mmap_size)\n+{\n+\t/*\n+\t * The IEOT extension is guaranteed to be last so that it can be found\n+\t * by scanning backwards from the EOF.  In addition to the regular 4-byte\n+\t * extension name and 4-byte section length is network byte order, it\n+\t * also stores the 4-byte extension name and section length in reverse order\n+\t * at the end of the extension.\n+\t *\n+\t * IEOT\n+\t * 4-byte length\n+\t * 4-byte version\n+\t * variable length extension data...\n+\t * 4-byte version\n+\t * 4-byte length\n+\t * IEOT\n+\t * <SHA1>\n+\t *\n+\t * If both names and lengths match, the extension is assumed to be valid.\n+\t */\n+\tconst char *index;\n+\tuint32_t extsize_leading, extsize_trailing, ext_version;\n+\tstruct index_entry_offset_table *ieot;\n+\tint i, nr;\n+\n+\t/* validate the trailing extension signature */\n+\tindex = (const char *)mmap + mmap_size - 20 - 4;\n+\tif (CACHE_EXT(index) != CACHE_EXT_FASTINDEX)\n+\t\treturn NULL;\n+\tindex -= sizeof(uint32_t);\n+\n+\t/*\n+\t * Validate the offset we're going to look for the leading extension\n+\t * signature is past the index header.\n+\t */\n+\textsize_trailing = get_be32(index);\n+\tif ((index - extsize_trailing) < ((const char *)mmap + 12))\n+\t\treturn NULL;\n+\tindex -= sizeof(uint32_t);\n+\n+\t/* validate the trailing version is IEOT_VERSION */\n+\text_version = get_be32(index);\n+\tif (ext_version != IEOT_VERSION)\n+\t\treturn NULL;\n+\tindex -= (extsize_trailing - sizeof(uint32_t));\n+\n+\t/* validate the leading extension signature */\n+\tif (CACHE_EXT(index) != CACHE_EXT_FASTINDEX)\n+\t\treturn NULL;\n+\tindex += sizeof(uint32_t);\n+\n+\t/* validate the leading extension size */\n+\textsize_leading = get_be32(index);\n+\tif (extsize_leading != extsize_trailing)\n+\t\treturn NULL;\n+\tindex += sizeof(uint32_t);\n+\n+\t/* validate the leading version is IEOT_VERSION */\n+\text_version = get_be32(index);\n+\tif (ext_version != IEOT_VERSION)\n+\t\treturn NULL;\n+\tindex += sizeof(uint32_t);\n+\n+\t/* extension size - leading/trailing version bytes - trailing size - trailing signature / bytes per entry */\n+\tnr = (extsize_leading - sizeof(uint32_t) - sizeof(uint32_t) - sizeof(uint32_t) - 4) / (sizeof(uint32_t) + sizeof(uint32_t));\n+\tassert(nr);\n+\tieot = xmalloc(sizeof(struct index_entry_offset_table)\n+\t\t+ (nr * sizeof(struct index_entry_offset)));\n+\tieot->nr = nr;\n+\tfor (i = 0; i < nr; i++) {\n+\t\tieot->entries[i].offset = get_be32(index);\n+\t\tindex += sizeof(uint32_t);\n+\t\tieot->entries[i].nr = get_be32(index);\n+\t\tindex += sizeof(uint32_t);\n+\t}\n+\n+\treturn ieot;\n+}\n+\n+static int write_ieot_extension(git_SHA_CTX *context, int fd, struct index_entry_offset_table *ieot)\n+{\n+\tstruct strbuf sb = STRBUF_INIT;\n+\tuint32_t buffer;\n+\tint i, err;\n+\n+\t/* version */\n+\tput_be32(&buffer, IEOT_VERSION);\n+\tstrbuf_add(&sb, &buffer, sizeof(uint32_t));\n+\n+\t/* ieot */\n+\tfor (i = 0; i < ieot->nr; i++) {\n+\n+\t\t/* offset */\n+\t\tput_be32(&buffer, ieot->entries[i].offset);\n+\t\tstrbuf_add(&sb, &buffer, sizeof(uint32_t));\n+\n+\t\t/* count */\n+\t\tput_be32(&buffer, ieot->entries[i].nr);\n+\t\tstrbuf_add(&sb, &buffer, sizeof(uint32_t));\n+\t}\n+\n+\t/* version */\n+\tput_be32(&buffer, IEOT_VERSION);\n+\tstrbuf_add(&sb, &buffer, sizeof(uint32_t));\n+\n+\t/* size */\n+\tput_be32(&buffer, sb.len + sizeof(uint32_t) + 4);\n+\tstrbuf_add(&sb, &buffer, sizeof(uint32_t));\n+\n+\t/* signature */\n+\tput_be32(&buffer, CACHE_EXT_FASTINDEX);\n+\tstrbuf_add(&sb, &buffer, 4);\n+\n+\t/* leading signature and size + extension data */\n+\terr = write_index_ext_header(context, fd, CACHE_EXT_FASTINDEX, sb.len) < 0\n+\t\t|| ce_write(context, fd, sb.buf, sb.len) < 0;\n+\tstrbuf_release(&sb);\n+\n+\treturn err;\n+}\n+\n+#endif\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-\tint fd, i;\n+\tint fd;\n \tstruct stat st;\n \tunsigned long src_offset;\n \tstruct cache_header *hdr;\n \tvoid *mmap;\n \tsize_t mmap_size;\n-\tstruct strbuf previous_name_buf = STRBUF_INIT, *previous_name;\n #ifndef NO_PTHREADS\n \tstruct verify_hdr_thread_data verify_hdr_thread_data;\n #endif\n@@ -1819,24 +2019,71 @@ int do_read_index(struct index_state *istate, const char *path, int must_exist)\n \tistate->cache = xcalloc(istate->cache_alloc, sizeof(*istate->cache));\n \tistate->initialized = 1;\n \n-\tif (istate->version == 4)\n-\t\tprevious_name = &previous_name_buf;\n-\telse\n-\t\tprevious_name = NULL;\n-\n \tsrc_offset = sizeof(*hdr);\n-\tfor (i = 0; i < istate->cache_nr; i++) {\n-\t\tstruct ondisk_cache_entry *disk_ce;\n-\t\tstruct cache_entry *ce;\n-\t\tunsigned long consumed;\n+#ifdef NO_PTHREADS\n+\tsrc_offset += load_cache_entries(istate, 0, istate->cache_nr, mmap, src_offset);\n+#else\n+\tif (git_config_get_fast_index() != 1) {\n+\t\tsrc_offset += load_cache_entries(istate, 0, istate->cache_nr, mmap, src_offset);\n+\t} else {\n+\t\tstruct index_entry_offset_table *ieot;\n+\t\tint threads, cpus = online_cpus();\n \n-\t\tdisk_ce = (struct ondisk_cache_entry *)((char *)mmap + src_offset);\n-\t\tce = create_from_disk(disk_ce, &consumed, previous_name);\n-\t\tset_index_entry(istate, i, ce);\n+\t\tthreads = istate->cache_nr / THREAD_COST;\n+\t\tif (threads > cpus)\n+\t\t\tthreads = cpus;\n \n-\t\tsrc_offset += consumed;\n+\t\t/*\n+\t\t * Locate and read the fast index extension so that we can use it\n+\t\t * to multi-thread the reading of the cache entries.\n+\t\t */\n+\t\tieot = read_ieot_extension(mmap, mmap_size);\n+\t\tif (threads < 2 || !ieot) {\n+\t\t\tsrc_offset += load_cache_entries(istate, 0, istate->cache_nr, mmap, src_offset);\n+\t\t} else {\n+\t\t\tint i, offset, ieot_work, ieot_offset;\n+\t\t\tstruct load_cache_entries_thread_data *data;\n+\n+\t\t\t/* ensure we have no more threads than we have blocks to process */\n+\t\t\tif (threads > ieot->nr)\n+\t\t\t\tthreads = ieot->nr;\n+\t\t\tdata = xcalloc(threads * sizeof(struct load_cache_entries_thread_data), 1);\n+\n+\t\t\toffset = ieot_offset = 0;\n+\t\t\tieot_work = DIV_ROUND_UP(ieot->nr, threads);\n+\t\t\tfor (i = 0; i < threads; i++) {\n+\t\t\t\tstruct load_cache_entries_thread_data *p = &data[i];\n+\t\t\t\tint j;\n+\n+\t\t\t\tif (ieot_offset + ieot_work > ieot->nr)\n+\t\t\t\t\tieot_work = ieot->nr - ieot_offset;\n+\n+\t\t\t\tp->istate = istate;\n+\t\t\t\tp->offset = offset;\t\t\t\t// starting index into the istate->cache array\n+\t\t\t\tp->mmap = mmap;\t\t\t\t\t// pointer to memory mapped index file\n+\t\t\t\tp->ieot = ieot;\t\t\t\t\t// pointer to ieot\n+\t\t\t\tp->ieot_offset = ieot_offset;\t// starting index into the ieot array\n+\t\t\t\tp->ieot_work = ieot_work;\t\t// count of ieot entries to process\n+\t\t\t\tif (pthread_create(&p->pthread, NULL, load_cache_entries_thread, p))\n+\t\t\t\t\tdie(\"unable to create threaded load_cache_entries\");\n+\n+\t\t\t\t// increment by the number of cache entries in the ieot block being processed\n+\t\t\t\tfor (j = 0; j < ieot_work; j++)\n+\t\t\t\t\toffset += ieot->entries[ieot_offset + j].nr;\n+\t\t\t\tieot_offset += ieot_work;\n+\t\t\t}\n+\t\t\tfor (i = 0; i < threads; i++) {\n+\t\t\t\tstruct load_cache_entries_thread_data *p = data + i;\n+\t\t\t\tif (pthread_join(p->pthread, NULL))\n+\t\t\t\t\tdie(\"unable to join threaded load_cache_entries\");\n+\t\t\t\tsrc_offset += p->consumed;\t\t// # of bytes in index file processed\n+\t\t\t}\n+\t\t\tfree(data);\n+\t\t}\n+\t\tfree(ieot);\n \t}\n-\tstrbuf_release(&previous_name_buf);\n+#endif\n+\n \tistate->timestamp.sec = st.st_mtime;\n \tistate->timestamp.nsec = ST_MTIME_NSEC(st);\n \n@@ -2258,6 +2505,9 @@ static int do_write_index(struct index_state *istate, struct tempfile *tempfile,\n \tstruct stat st;\n \tstruct strbuf previous_name_buf = STRBUF_INIT, *previous_name;\n \tint drop_cache_tree = 0;\n+\tint ieot_work = 1;\n+\tstruct index_entry_offset_table *ieot = NULL;\n+\tint offset, nr;\n \n \tfor (i = removed = extended = 0; i < entries; i++) {\n \t\tif (cache[i]->ce_flags & CE_REMOVE)\n@@ -2291,6 +2541,22 @@ static int do_write_index(struct index_state *istate, struct tempfile *tempfile,\n \tif (ce_write(&c, newfd, &hdr, sizeof(hdr)) < 0)\n \t\treturn -1;\n \n+\tif (!strip_extensions && core_fast_index) {\n+\t\tint ieot_blocks, cpus = online_cpus();\n+\n+\t\tieot_blocks = istate->cache_nr / THREAD_COST;\n+\t\tif (ieot_blocks > cpus)\n+\t\t\tieot_blocks = cpus;\n+\t\tif (ieot_blocks >= 1) {\n+\t\t\tieot = xcalloc(sizeof(struct index_entry_offset_table)\n+\t\t\t\t+ (ieot_blocks * sizeof(struct index_entry_offset)), 1);\n+\t\t\tieot->nr = 0;\n+\t\t}\n+\t\tieot_work = DIV_ROUND_UP(entries, ieot_blocks);\n+\t}\n+\n+\toffset = lseek(newfd, 0, SEEK_CUR) + write_buffer_len;\n+\tnr = 0;\n \tprevious_name = (hdr_version == 4) ? &previous_name_buf : NULL;\n \tfor (i = 0; i < entries; i++) {\n \t\tstruct cache_entry *ce = cache[i];\n@@ -2311,8 +2577,28 @@ static int do_write_index(struct index_state *istate, struct tempfile *tempfile,\n \n \t\t\tdrop_cache_tree = 1;\n \t\t}\n+\t\tif (ieot && i && (i % ieot_work == 0)) {\n+\t\t\tieot->entries[ieot->nr].nr = nr;\n+\t\t\tieot->entries[ieot->nr].offset = offset;\n+\t\t\tieot->nr++;\n+\t\t\t/*\n+\t\t\t * If we have a V4 index, set the first byte to an invalid\n+\t\t\t * character to ensure there is nothing common with the previous\n+\t\t\t * entry\n+\t\t\t */\n+\t\t\tif (previous_name)\n+\t\t\t\tprevious_name->buf[0] = 0;\n+\t\t\tnr = 0;\n+\t\t\toffset = lseek(newfd, 0, SEEK_CUR) + write_buffer_len;\n+\t\t}\n \t\tif (ce_write_entry(&c, newfd, ce, previous_name) < 0)\n \t\t\treturn -1;\n+\t\tnr++;\n+\t}\n+\tif (ieot && nr) {\n+\t\tieot->entries[ieot->nr].nr = nr;\n+\t\tieot->entries[ieot->nr].offset = offset;\n+\t\tieot->nr++;\n \t}\n \tstrbuf_release(&previous_name_buf);\n \n@@ -2361,6 +2647,18 @@ static int do_write_index(struct index_state *istate, struct tempfile *tempfile,\n \t\t\treturn -1;\n \t}\n \n+\t/*\n+\t * CACHE_EXT_FASTINDEX must be written as the last entry before the SHA1\n+\t * so that it can be found and processed before all the index entries are\n+\t * read.\n+\t */\n+\tif (!strip_extensions && ieot) {\n+\t\terr = write_ieot_extension(&c, newfd, ieot);\n+\t\tfree(ieot);\n+\t\tif (err)\n+\t\t\treturn -1;\n+\t}\n+\n \tif (ce_flush(&c, newfd, istate->sha1))\n \t\treturn -1;\n \tif (close_tempfile(tempfile))\ndiff --git a/t/helper/test-dump-ieot.c b/t/helper/test-dump-ieot.c\nnew file mode 100644\nindex 0000000000..70aa31bb41\n--- /dev/null\n+++ b/t/helper/test-dump-ieot.c\n@@ -0,0 +1,78 @@\n+#include \"cache.h\"\n+\n+struct ondisk_cache_entry;\n+extern struct cache_entry *create_from_disk(struct ondisk_cache_entry *ondisk,\n+\tunsigned long *ent_size,\n+\tstruct strbuf *previous_name,\n+\tint use_length);\n+\n+int cmd_main(int ac, const char **av)\n+{\n+#ifndef NO_PTHREADS\n+\tconst char *path;\n+\tint fd, i;\n+\tstruct stat st;\n+\tvoid *mmap;\n+\tsize_t mmap_size;\n+\tstruct cache_header *hdr;\n+\tstruct index_entry_offset_table *ieot;\n+\tstruct strbuf previous_name_buf = STRBUF_INIT, *previous_name;\n+\n+\tsetup_git_directory();\n+\tpath = get_index_file();\n+\tfd = open(path, O_RDONLY);\n+\tif (fd < 0) {\n+\t\tdie_errno(\"%s: index file open failed\", path);\n+\t}\n+\n+\tif (fstat(fd, &st))\n+\t\tdie_errno(\"cannot stat the open index\");\n+\n+\tmmap_size = xsize_t(st.st_size);\n+\tif (mmap_size < sizeof(struct cache_header) + 20)\n+\t\tdie_errno(\"index file smaller than expected\");\n+\n+\tmmap = xmmap(NULL, mmap_size, PROT_READ, MAP_PRIVATE, fd, 0);\n+\tif (mmap == MAP_FAILED)\n+\t\tdie_errno(\"unable to map index file\");\n+\tclose(fd);\n+\n+\thdr = mmap;\n+\tif (ntohl(hdr->hdr_version) == 4)\n+\t\tprevious_name = &previous_name_buf;\n+\telse\n+\t\tprevious_name = NULL;\n+\n+\tieot = read_ieot_extension(mmap, mmap_size);\n+\tif (!ieot)\n+\t\tdie_errno(\"missing or invalid extension\");\n+\n+\tprintf(\"IEOT with %d entries\\n\", ieot->nr);\n+\tprintf(\"  Offset    Count Name\\n\");\n+\tprintf(\"-------- -------- ------------------------\\n\");\n+\tfor (i = 0; i < ieot->nr; i++) {\n+\t\tstruct ondisk_cache_entry *disk_ce;\n+\t\tstruct cache_entry *ce;\n+\t\tunsigned long consumed;\n+\n+\t\tdisk_ce = (struct ondisk_cache_entry *)((char *)mmap + ieot->entries[i].offset);\n+\t\tce = create_from_disk(disk_ce, &consumed, previous_name, 0);\n+\t\t/*\n+\t\t * If we have a V4 index, set the first byte to an invalid\n+\t\t * character to ensure there is nothing common with the previous\n+\t\t * entry\n+\t\t */\n+\t\tif (previous_name)\n+\t\t\tprevious_name->buf[0] = 0;\n+\t\tprintf(\"%8d %8d %.*s\\n\", ieot->entries[i].offset, ieot->entries[i].nr, ce->ce_namelen, ce->name);\n+\t\tfree(ce);\n+\t}\n+\n+\tfree(ieot);\n+\tmunmap(mmap, mmap_size);\n+\treturn 0;\n+#else\n+\tdie_errno(\"ieot only supported with PTHREADS\");\n+\treturn -1;\n+#endif\n+}\ndiff --git a/t/helper/test-ieot.c b/t/helper/test-ieot.c\nnew file mode 100644\nindex 0000000000..75f28db001\n--- /dev/null\n+++ b/t/helper/test-ieot.c\n@@ -0,0 +1,72 @@\n+#include \"cache.h\"\n+\n+int compare_ce(const struct cache_entry *ce1, const struct cache_entry *ce2)\n+{\n+//\tstruct hashmap_entry ent;\n+//\tstruct stat_data ce_stat_data;\n+\n+\tif (ce1->ce_mode != ce2->ce_mode) {\n+\t\tprintf(\"ce_mode: %d:%d\\n\", ce1->ce_mode, ce2->ce_mode);\n+\t\treturn 1;\n+\t}\n+\n+\tif (ce1->ce_flags != ce2->ce_flags) {\n+\t\tprintf(\"ce_flags: %d:%d\\n\", ce1->ce_flags, ce2->ce_flags);\n+\t\treturn 1;\n+\t}\n+\n+//\tunsigned int ce_namelen;\n+\n+\tif (ce1->index != ce2->index) {\n+\t\tprintf(\"index: %d:%d\\n\", ce1->index, ce2->index);\n+\t\treturn 1;\n+\t}\n+\n+\tif (oidcmp(&ce1->oid, &ce2->oid)) {\n+\t\tprintf(\"oid: %s:%s\\n\", oid_to_hex(&ce1->oid), oid_to_hex(&ce2->oid));\n+\t\treturn 1;\n+\t}\n+\n+\treturn 0;\n+}\n+\n+extern int ignore_fast_index_config;\n+\n+int cmd_main(int ac, const char **av)\n+{\n+#ifndef NO_PTHREADS\n+\tstatic struct index_state index;\n+\tstatic struct index_state ieot;\n+\tint i;\n+\n+\tsetup_git_directory();\n+\tignore_fast_index_config = 1;\n+\tcore_fast_index = 0;\n+\tread_index(&index);\n+\tcore_fast_index = 1;\n+\tread_index(&ieot);\n+\n+\tfor (i = 0; i < index.cache_nr; i++) {\n+\t\tif (compare_ce(index.cache[i], ieot.cache[i])) {\n+\t\t\tstruct cache_entry *ce;\n+\n+\t\t\tce = index.cache[i];\n+\t\t\tprintf(\"%06o %s %d\\t%s\\n\", ce->ce_mode,\n+\t\t\t\toid_to_hex(&ce->oid), ce_stage(ce), ce->name);\n+\t\t\tce = ieot.cache[i];\n+\t\t\tprintf(\"%06o %s %d\\t%s\\n\", ce->ce_mode,\n+\t\t\t\toid_to_hex(&ce->oid), ce_stage(ce), ce->name);\n+\n+\t\t\tdie_errno(\"cache entry %d does not match\", i);\n+\t\t}\n+\t}\n+\n+\tdiscard_index(&ieot);\n+\tdiscard_index(&index);\n+\tprintf(\"Cache entires are the same\\n\");\n+\treturn 0;\n+#else\n+\tdie_errno(\"ieot only supported with PTHREADS\");\n+\treturn -1;\n+#endif\n+}\n\nbase-commit: dbc8d81072630bc50324938b9ac950140669ced9\n-- \n2.15.0.windows.1\n\n"},{"id":"332078","messageId":"dcd4a9e6-dbaa-25ec-c898-d4242a8ce544@gmail.com","threadId":"47137","inReplyTo":"20171108144253.34428-1-benpeart@microsoft.com","subject":"Re: [RFC] fastindex: parallelize index load","fromName":"Ben Peart","fromEmail":"peartben@gmail.com","sentAt":"2017-11-08T14:50:38Z","receivedAt":"2017-11-08T14:50:49Z","isPatch":false,"sender":{"key":"benpeart@microsoft.com","avatar":"https://avatars.githubusercontent.com/u/15252029?v=4"},"body":"This is an RFC because it works but I've not done the code cleanup,\nadded tests, support in the update-index command to add/remove it, etc.\nAs a result, there is no reason to point out all the places I'm not\ncurrently following the git coding style. :)\n\nI wanted to get feedback on the concept first, especially as the way I'm\nadding the TOC information via an extension that can be read before the\nvariable length section of cache entries and other extensions is a bit\nof a clever hack, as is the resetting of the prefix encoding for V4\nindexes.  They are, however, entirely backwards compatible with older\nversions of git which can still properly read and use the index.\n\nThe effect can be seen using t/helper/test-read-cache:\n\n                                 fastindex\ntest            count   files   TRUE    FALSE     Savings\n------------------------------------------------------------------------\ntest-read-cache 500     100K    6.39    8.33      23.36%\ntest-read-cache 100     1M      12.49   18.68     33.12%\n\n\n\nOn 11/8/2017 9:42 AM, Ben Peart wrote:\n> This patch will address the CPU cost of loading the index by adding\n> additional data to the index that will allow us to multi-thread the\n> loading and conversion of cache entries.\n> \n> It accomplishes this by adding an (optional) index extension that is a\n> table of offsets to blocks of cache entries in the index file.  With\n> version 2, 3 or even 4 indexes, we can utilize the Index Entry Offset Table\n> (IEOT) to parallelize the loading and conversion of the cache entries\n> across all available CPU cores.\n> \n> To make this work for V4 indexes, when writing the index, it periodically\n> \"resets\" the compression by encoding the current entry as if the path\n> name for the previous entry is completely different and saves the offset\n> of that entry in the IEOT.  Basically, with V4 indexes, it generates\n> offsets into blocks of prefix-compressed entries.\n> \n> To enable reading the IEOT extension before reading all the variable\n> length cache entries and other extensions, the IEOT is written last,\n> right before the trailing SHA1.\n> \n> The format of that extension has the signature bytes and size at the\n> beginning (like a normal extension) as well as at the end in reverse\n> order to enable parsing the extension by seeking back from the end of\n> the file.  See the diagram below for details.\n> \n> During index load, read the index header then seek to the end of the\n> index, back up past the trailing SHA1 and look for the IEOT extension\n> signature bytes.  If they exist, read the 32-bit size and seek back to\n> the extension header and verify the leading header and size bits.  If\n> they all match, we can be assured we have a valid IEOT extension.\n> \n> If the IEOT extension is available, create multiple threads to divide\n> the work of loading and converting the cache entries across all\n> available CPU cores.  Once the cache entries are loaded, the rest of the\n> extensions can be loaded and processed normally (skipping the IEOT entry\n> as it has already been processed).  If the IEOT extension is not\n> available then parsing the index will proceed as usual with a single thread.\n> \n> The on-disk format looks like this:\n> \n> Index header\n> Cache entry 1\n> Cache entry 2\n> .\n> .\n> Extension 1\n> Extension 2\n> .\n> .\n> Index Entry Offset Table Extension (must be written last!)\n> IEOT signature bytes\n> 32-bit size\n> 32-bit version\n> 32-bit Cache Entry Offset 1\n> 32-bit Cache Entry count\n> 32-bit Cache Entry Offset 2\n> 32-bit Cache Entry count\n> .\n> .\n> 32-bit version\n> 32-bit size\n> IEOT signature bytes\n> SHA1\n> \n> Signed-off-by: Ben Peart <benpeart@microsoft.com>\n> ---\n> \n> Notes:\n>      Base Ref: v2.14.3.windows.1\n>      Web-Diff: https://github.com/benpeart/git/commit/1e818c7835\n>      Checkout: git fetch https://github.com/benpeart/git fastindex-v1 && git checkout 1e818c7835\n> \n>   Makefile                  |   2 +\n>   cache.h                   |  18 +++\n>   config.c                  |  20 +++\n>   config.h                  |   1 +\n>   environment.c             |   3 +\n>   read-cache.c              | 340 +++++++++++++++++++++++++++++++++++++++++++---\n>   t/helper/test-dump-ieot.c |  78 +++++++++++\n>   t/helper/test-ieot.c      |  72 ++++++++++\n>   8 files changed, 513 insertions(+), 21 deletions(-)\n>   create mode 100644 t/helper/test-dump-ieot.c\n>   create mode 100644 t/helper/test-ieot.c\n> \n> diff --git a/Makefile b/Makefile\n> index ebd0a75d87..99fa8dd8d3 100644\n> --- a/Makefile\n> +++ b/Makefile\n> @@ -640,12 +640,14 @@ TEST_PROGRAMS_NEED_X += test-config\n>   TEST_PROGRAMS_NEED_X += test-date\n>   TEST_PROGRAMS_NEED_X += test-delta\n>   TEST_PROGRAMS_NEED_X += test-dump-cache-tree\n> +TEST_PROGRAMS_NEED_X += test-dump-ieot\n>   TEST_PROGRAMS_NEED_X += test-dump-split-index\n>   TEST_PROGRAMS_NEED_X += test-dump-untracked-cache\n>   TEST_PROGRAMS_NEED_X += test-fake-ssh\n>   TEST_PROGRAMS_NEED_X += test-genrandom\n>   TEST_PROGRAMS_NEED_X += test-hashmap\n>   TEST_PROGRAMS_NEED_X += test-helper\n> +TEST_PROGRAMS_NEED_X += test-ieot\n>   TEST_PROGRAMS_NEED_X += test-index-version\n>   TEST_PROGRAMS_NEED_X += test-lazy-init-name-hash\n>   TEST_PROGRAMS_NEED_X += test-line-buffer\n> diff --git a/cache.h b/cache.h\n> index 45597732d8..e9ec1bf41a 100644\n> --- a/cache.h\n> +++ b/cache.h\n> @@ -326,6 +326,7 @@ static inline unsigned int canon_mode(unsigned int mode)\n>   #define CACHE_TREE_CHANGED\t(1 << 5)\n>   #define SPLIT_INDEX_ORDERED\t(1 << 6)\n>   #define UNTRACKED_CHANGED\t(1 << 7)\n> +#define IEOT_CHANGED\t\t(1 << 9)\n>   \n>   struct split_index;\n>   struct untracked_cache;\n> @@ -770,6 +771,7 @@ extern char *git_replace_ref_base;\n>   \n>   extern int fsync_object_files;\n>   extern int core_preload_index;\n> +extern int core_fast_index;\n>   extern int core_apply_sparse_checkout;\n>   extern int precomposed_unicode;\n>   extern int protect_hfs;\n> @@ -2025,4 +2027,20 @@ void sleep_millisec(int millisec);\n>    */\n>   void safe_create_dir(const char *dir, int share);\n>   \n> +\n> +#ifndef NO_PTHREADS\n> +struct index_entry_offset\n> +{\t// starting byte offset into index file, count of index entries in this block\n> +\tint offset, nr;\n> +};\n> +\n> +struct index_entry_offset_table\n> +{\n> +\tint nr;\t\t\t\t// number of ieot entries in array\n> +\tstruct index_entry_offset entries[0];\n> +};\n> +\n> +struct index_entry_offset_table *read_ieot_extension(void *mmap, size_t mmap_size);\n> +#endif\n> +\n>   #endif /* CACHE_H */\n> diff --git a/config.c b/config.c\n> index adcd2c2441..056c21b0c9 100644\n> --- a/config.c\n> +++ b/config.c\n> @@ -1203,6 +1203,11 @@ static int git_default_core_config(const char *var, const char *value, void *cb)\n>   \t\treturn 0;\n>   \t}\n>   \n> +\tif (!strcmp(var, \"core.fastindex\")) {\n> +\t\tcore_fast_index = git_config_bool(var, value);\n> +\t\treturn 0;\n> +\t}\n> +\n>   \tif (!strcmp(var, \"core.createobject\")) {\n>   \t\tif (!strcmp(value, \"rename\"))\n>   \t\t\tobject_creation_mode = OBJECT_CREATION_USES_RENAMES;\n> @@ -2116,6 +2121,21 @@ int git_config_get_max_percent_split_change(void)\n>   \treturn -1; /* default value */\n>   }\n>   \n> +int ignore_fast_index_config;\n> +int git_config_get_fast_index(void)\n> +{\n> +\tint val;\n> +\n> +\t/* Hack for test programs like test-ieot */\n> +\tif (ignore_fast_index_config)\n> +\t\treturn core_fast_index;\n> +\n> +\tif (!git_config_get_maybe_bool(\"core.fastindex\", &val))\n> +\t\treturn val;\n> +\n> +\treturn -1; /* default value */\n> +}\n> +\n>   NORETURN\n>   void git_die_config_linenr(const char *key, const char *filename, int linenr)\n>   {\n> diff --git a/config.h b/config.h\n> index 0352da117b..bb73c36e0a 100644\n> --- a/config.h\n> +++ b/config.h\n> @@ -201,6 +201,7 @@ extern int git_config_get_pathname(const char *key, const char **dest);\n>   extern int git_config_get_untracked_cache(void);\n>   extern int git_config_get_split_index(void);\n>   extern int git_config_get_max_percent_split_change(void);\n> +extern int git_config_get_fast_index(void);\n>   \n>   /* This dies if the configured or default date is in the future */\n>   extern int git_config_get_expiry(const char *key, const char **output);\n> diff --git a/environment.c b/environment.c\n> index c974bed180..bb8405cd91 100644\n> --- a/environment.c\n> +++ b/environment.c\n> @@ -86,6 +86,9 @@ int auto_comment_line_char;\n>   /* Parallel index stat data preload? */\n>   int core_preload_index = 1;\n>   \n> +/* Parallel index cache entry loading? */\n> +int core_fast_index;\n> +\n>   /*\n>    * This is a hack for test programs like test-dump-untracked-cache to\n>    * ensure that they do not modify the untracked cache when reading it.\n> diff --git a/read-cache.c b/read-cache.c\n> index bc925b6736..dc2fadb61f 100644\n> --- a/read-cache.c\n> +++ b/read-cache.c\n> @@ -19,6 +19,7 @@\n>   #include \"varint.h\"\n>   #include \"split-index.h\"\n>   #include \"utf8.h\"\n> +#include \"thread-utils.h\"\n>   \n>   #ifndef NO_PTHREADS\n>   #include <pthread.h>\n> @@ -42,11 +43,12 @@\n>   #define CACHE_EXT_RESOLVE_UNDO 0x52455543 /* \"REUC\" */\n>   #define CACHE_EXT_LINK 0x6c696e6b\t  /* \"link\" */\n>   #define CACHE_EXT_UNTRACKED 0x554E5452\t  /* \"UNTR\" */\n> +#define CACHE_EXT_FASTINDEX 0x49454F54\t  /* \"IEOT\" */\n>   \n>   /* changes that can be kept in $GIT_DIR/index (basically all extensions) */\n>   #define EXTMASK (RESOLVE_UNDO_CHANGED | CACHE_TREE_CHANGED | \\\n>   \t\t CE_ENTRY_ADDED | CE_ENTRY_REMOVED | CE_ENTRY_CHANGED | \\\n> -\t\t SPLIT_INDEX_ORDERED | UNTRACKED_CHANGED)\n> +\t\t SPLIT_INDEX_ORDERED | UNTRACKED_CHANGED | CACHE_EXT_FASTINDEX)\n>   \n>   struct index_state the_index;\n>   static const char *alternate_index_output;\n> @@ -1581,6 +1583,9 @@ static int read_index_extension(struct index_state *istate,\n>   \tcase CACHE_EXT_UNTRACKED:\n>   \t\tistate->untracked = read_untracked_extension(data, sz);\n>   \t\tbreak;\n> +\tcase CACHE_EXT_FASTINDEX:\n> +\t\t/* already handled in do_read_index() */\n> +\t\tbreak;\n>   \tdefault:\n>   \t\tif (*ext < 'A' || 'Z' < *ext)\n>   \t\t\treturn error(\"index uses %.4s extension, which we do not understand\",\n> @@ -1634,10 +1639,12 @@ static struct cache_entry *cache_entry_from_ondisk(struct ondisk_cache_entry *on\n>    * number of bytes to be stripped from the end of the previous name,\n>    * and the bytes to append to the result, to come up with its name.\n>    */\n> -static unsigned long expand_name_field(struct strbuf *name, const char *cp_)\n> +static unsigned long expand_name_field(struct strbuf *name, const char *cp_, int use_length)\n>   {\n>   \tconst unsigned char *ep, *cp = (const unsigned char *)cp_;\n>   \tsize_t len = decode_varint(&cp);\n> +\tif (!use_length)\n> +\t\tlen = name->len;\n>   \n>   \tif (name->len < len)\n>   \t\tdie(\"malformed name field in the index\");\n> @@ -1648,9 +1655,10 @@ static unsigned long expand_name_field(struct strbuf *name, const char *cp_)\n>   \treturn (const char *)ep + 1 - cp_;\n>   }\n>   \n> -static struct cache_entry *create_from_disk(struct ondisk_cache_entry *ondisk,\n> +struct cache_entry *create_from_disk(struct ondisk_cache_entry *ondisk,\n>   \t\t\t\t\t    unsigned long *ent_size,\n> -\t\t\t\t\t    struct strbuf *previous_name)\n> +\t\t\t\t\t    struct strbuf *previous_name,\n> +\t\t\t\t\t\tint use_length)\n>   {\n>   \tstruct cache_entry *ce;\n>   \tsize_t len;\n> @@ -1684,7 +1692,7 @@ static struct cache_entry *create_from_disk(struct ondisk_cache_entry *ondisk,\n>   \t\t*ent_size = ondisk_ce_size(ce);\n>   \t} else {\n>   \t\tunsigned long consumed;\n> -\t\tconsumed = expand_name_field(previous_name, name);\n> +\t\tconsumed = expand_name_field(previous_name, name, use_length);\n>   \t\tce = cache_entry_from_ondisk(ondisk, flags,\n>   \t\t\t\t\t     previous_name->buf,\n>   \t\t\t\t\t     previous_name->len);\n> @@ -1755,16 +1763,208 @@ static void post_read_index_from(struct index_state *istate)\n>   \ttweak_split_index(istate);\n>   }\n>   \n> +static unsigned long load_cache_entries(struct index_state *istate, int offset, int nr, void *mmap, unsigned long start_offset)\n> +{\n> +\tint i;\n> +\tunsigned long src_offset = start_offset;\n> +\tstruct strbuf previous_name_buf = STRBUF_INIT, *previous_name;\n> +\n> +\tif (istate->version == 4)\n> +\t\tprevious_name = &previous_name_buf;\n> +\telse\n> +\t\tprevious_name = NULL;\n> +\n> +\tfor (i = offset; i < offset + nr; i++) {\n> +\t\tstruct ondisk_cache_entry *disk_ce;\n> +\t\tstruct cache_entry *ce;\n> +\t\tunsigned long consumed;\n> +\n> +\t\tdisk_ce = (struct ondisk_cache_entry *)((char *)mmap + src_offset);\n> +\t\tce = create_from_disk(disk_ce, &consumed, previous_name, i == offset ? 0 : 1);\n> +\t\tset_index_entry(istate, i, ce);\n> +\n> +\t\tsrc_offset += consumed;\n> +\t}\n> +\tstrbuf_release(&previous_name_buf);\n> +\treturn src_offset - start_offset;\n> +}\n> +\n> +#ifndef NO_PTHREADS\n> +\n> +/*\n> + * Mostly randomly chosen cache entries per thread (it works on my machine):\n> + * we want to have at least 7500 cache entries per thread for it to\n> + * be worth starting a thread.\n> + */\n> +#define THREAD_COST\t\t(7500)\n> +#define IEOT_VERSION\t(1)\n> +\n> +static int ce_write(git_SHA_CTX *context, int fd, void *data, unsigned int len);\n> +\n> +static int write_index_ext_header(git_SHA_CTX *context, int fd,\n> +\tunsigned int ext, unsigned int sz);\n> +\n> +struct load_cache_entries_thread_data\n> +{\n> +\tpthread_t pthread;\n> +\tstruct index_state *istate;\n> +\tint offset;\t\t\t// starting index into the istate->cache array\n> +\tvoid *mmap;\t\t\t// pointer to memory mapped index file\n> +\tunsigned long consumed;\t// return # of bytes in index file processed\n> +\tstruct index_entry_offset_table *ieot;\t// pointer to ieot\n> +\tint ieot_offset;\t// starting index into the ieot array\n> +\tint ieot_work;\t\t// count of ieot entries to process\n> +};\n> +\n> +/*\n> + * A thread proc to run the load_cache_entries() computation\n> + * across multiple background threads.\n> + */\n> +static void *load_cache_entries_thread(void *_data)\n> +{\n> +\tstruct load_cache_entries_thread_data *p = _data;\n> +\tint i;\n> +\n> +\t// itterate across all ieot blocks assigned to this thread\n> +\tfor (i = p->ieot_offset; i < p->ieot_offset + p->ieot_work; i++) {\n> +\t\tp->consumed += load_cache_entries(p->istate, p->offset, p->ieot->entries[i].nr, p->mmap, p->ieot->entries[i].offset);\n> +\t\tp->offset += p->ieot->entries[i].nr;\n> +\t}\n> +\treturn NULL;\n> +}\n> +\n> +struct index_entry_offset_table *read_ieot_extension(void *mmap, size_t mmap_size)\n> +{\n> +\t/*\n> +\t * The IEOT extension is guaranteed to be last so that it can be found\n> +\t * by scanning backwards from the EOF.  In addition to the regular 4-byte\n> +\t * extension name and 4-byte section length is network byte order, it\n> +\t * also stores the 4-byte extension name and section length in reverse order\n> +\t * at the end of the extension.\n> +\t *\n> +\t * IEOT\n> +\t * 4-byte length\n> +\t * 4-byte version\n> +\t * variable length extension data...\n> +\t * 4-byte version\n> +\t * 4-byte length\n> +\t * IEOT\n> +\t * <SHA1>\n> +\t *\n> +\t * If both names and lengths match, the extension is assumed to be valid.\n> +\t */\n> +\tconst char *index;\n> +\tuint32_t extsize_leading, extsize_trailing, ext_version;\n> +\tstruct index_entry_offset_table *ieot;\n> +\tint i, nr;\n> +\n> +\t/* validate the trailing extension signature */\n> +\tindex = (const char *)mmap + mmap_size - 20 - 4;\n> +\tif (CACHE_EXT(index) != CACHE_EXT_FASTINDEX)\n> +\t\treturn NULL;\n> +\tindex -= sizeof(uint32_t);\n> +\n> +\t/*\n> +\t * Validate the offset we're going to look for the leading extension\n> +\t * signature is past the index header.\n> +\t */\n> +\textsize_trailing = get_be32(index);\n> +\tif ((index - extsize_trailing) < ((const char *)mmap + 12))\n> +\t\treturn NULL;\n> +\tindex -= sizeof(uint32_t);\n> +\n> +\t/* validate the trailing version is IEOT_VERSION */\n> +\text_version = get_be32(index);\n> +\tif (ext_version != IEOT_VERSION)\n> +\t\treturn NULL;\n> +\tindex -= (extsize_trailing - sizeof(uint32_t));\n> +\n> +\t/* validate the leading extension signature */\n> +\tif (CACHE_EXT(index) != CACHE_EXT_FASTINDEX)\n> +\t\treturn NULL;\n> +\tindex += sizeof(uint32_t);\n> +\n> +\t/* validate the leading extension size */\n> +\textsize_leading = get_be32(index);\n> +\tif (extsize_leading != extsize_trailing)\n> +\t\treturn NULL;\n> +\tindex += sizeof(uint32_t);\n> +\n> +\t/* validate the leading version is IEOT_VERSION */\n> +\text_version = get_be32(index);\n> +\tif (ext_version != IEOT_VERSION)\n> +\t\treturn NULL;\n> +\tindex += sizeof(uint32_t);\n> +\n> +\t/* extension size - leading/trailing version bytes - trailing size - trailing signature / bytes per entry */\n> +\tnr = (extsize_leading - sizeof(uint32_t) - sizeof(uint32_t) - sizeof(uint32_t) - 4) / (sizeof(uint32_t) + sizeof(uint32_t));\n> +\tassert(nr);\n> +\tieot = xmalloc(sizeof(struct index_entry_offset_table)\n> +\t\t+ (nr * sizeof(struct index_entry_offset)));\n> +\tieot->nr = nr;\n> +\tfor (i = 0; i < nr; i++) {\n> +\t\tieot->entries[i].offset = get_be32(index);\n> +\t\tindex += sizeof(uint32_t);\n> +\t\tieot->entries[i].nr = get_be32(index);\n> +\t\tindex += sizeof(uint32_t);\n> +\t}\n> +\n> +\treturn ieot;\n> +}\n> +\n> +static int write_ieot_extension(git_SHA_CTX *context, int fd, struct index_entry_offset_table *ieot)\n> +{\n> +\tstruct strbuf sb = STRBUF_INIT;\n> +\tuint32_t buffer;\n> +\tint i, err;\n> +\n> +\t/* version */\n> +\tput_be32(&buffer, IEOT_VERSION);\n> +\tstrbuf_add(&sb, &buffer, sizeof(uint32_t));\n> +\n> +\t/* ieot */\n> +\tfor (i = 0; i < ieot->nr; i++) {\n> +\n> +\t\t/* offset */\n> +\t\tput_be32(&buffer, ieot->entries[i].offset);\n> +\t\tstrbuf_add(&sb, &buffer, sizeof(uint32_t));\n> +\n> +\t\t/* count */\n> +\t\tput_be32(&buffer, ieot->entries[i].nr);\n> +\t\tstrbuf_add(&sb, &buffer, sizeof(uint32_t));\n> +\t}\n> +\n> +\t/* version */\n> +\tput_be32(&buffer, IEOT_VERSION);\n> +\tstrbuf_add(&sb, &buffer, sizeof(uint32_t));\n> +\n> +\t/* size */\n> +\tput_be32(&buffer, sb.len + sizeof(uint32_t) + 4);\n> +\tstrbuf_add(&sb, &buffer, sizeof(uint32_t));\n> +\n> +\t/* signature */\n> +\tput_be32(&buffer, CACHE_EXT_FASTINDEX);\n> +\tstrbuf_add(&sb, &buffer, 4);\n> +\n> +\t/* leading signature and size + extension data */\n> +\terr = write_index_ext_header(context, fd, CACHE_EXT_FASTINDEX, sb.len) < 0\n> +\t\t|| ce_write(context, fd, sb.buf, sb.len) < 0;\n> +\tstrbuf_release(&sb);\n> +\n> +\treturn err;\n> +}\n> +\n> +#endif\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> -\tint fd, i;\n> +\tint fd;\n>   \tstruct stat st;\n>   \tunsigned long src_offset;\n>   \tstruct cache_header *hdr;\n>   \tvoid *mmap;\n>   \tsize_t mmap_size;\n> -\tstruct strbuf previous_name_buf = STRBUF_INIT, *previous_name;\n>   #ifndef NO_PTHREADS\n>   \tstruct verify_hdr_thread_data verify_hdr_thread_data;\n>   #endif\n> @@ -1819,24 +2019,71 @@ int do_read_index(struct index_state *istate, const char *path, int must_exist)\n>   \tistate->cache = xcalloc(istate->cache_alloc, sizeof(*istate->cache));\n>   \tistate->initialized = 1;\n>   \n> -\tif (istate->version == 4)\n> -\t\tprevious_name = &previous_name_buf;\n> -\telse\n> -\t\tprevious_name = NULL;\n> -\n>   \tsrc_offset = sizeof(*hdr);\n> -\tfor (i = 0; i < istate->cache_nr; i++) {\n> -\t\tstruct ondisk_cache_entry *disk_ce;\n> -\t\tstruct cache_entry *ce;\n> -\t\tunsigned long consumed;\n> +#ifdef NO_PTHREADS\n> +\tsrc_offset += load_cache_entries(istate, 0, istate->cache_nr, mmap, src_offset);\n> +#else\n> +\tif (git_config_get_fast_index() != 1) {\n> +\t\tsrc_offset += load_cache_entries(istate, 0, istate->cache_nr, mmap, src_offset);\n> +\t} else {\n> +\t\tstruct index_entry_offset_table *ieot;\n> +\t\tint threads, cpus = online_cpus();\n>   \n> -\t\tdisk_ce = (struct ondisk_cache_entry *)((char *)mmap + src_offset);\n> -\t\tce = create_from_disk(disk_ce, &consumed, previous_name);\n> -\t\tset_index_entry(istate, i, ce);\n> +\t\tthreads = istate->cache_nr / THREAD_COST;\n> +\t\tif (threads > cpus)\n> +\t\t\tthreads = cpus;\n>   \n> -\t\tsrc_offset += consumed;\n> +\t\t/*\n> +\t\t * Locate and read the fast index extension so that we can use it\n> +\t\t * to multi-thread the reading of the cache entries.\n> +\t\t */\n> +\t\tieot = read_ieot_extension(mmap, mmap_size);\n> +\t\tif (threads < 2 || !ieot) {\n> +\t\t\tsrc_offset += load_cache_entries(istate, 0, istate->cache_nr, mmap, src_offset);\n> +\t\t} else {\n> +\t\t\tint i, offset, ieot_work, ieot_offset;\n> +\t\t\tstruct load_cache_entries_thread_data *data;\n> +\n> +\t\t\t/* ensure we have no more threads than we have blocks to process */\n> +\t\t\tif (threads > ieot->nr)\n> +\t\t\t\tthreads = ieot->nr;\n> +\t\t\tdata = xcalloc(threads * sizeof(struct load_cache_entries_thread_data), 1);\n> +\n> +\t\t\toffset = ieot_offset = 0;\n> +\t\t\tieot_work = DIV_ROUND_UP(ieot->nr, threads);\n> +\t\t\tfor (i = 0; i < threads; i++) {\n> +\t\t\t\tstruct load_cache_entries_thread_data *p = &data[i];\n> +\t\t\t\tint j;\n> +\n> +\t\t\t\tif (ieot_offset + ieot_work > ieot->nr)\n> +\t\t\t\t\tieot_work = ieot->nr - ieot_offset;\n> +\n> +\t\t\t\tp->istate = istate;\n> +\t\t\t\tp->offset = offset;\t\t\t\t// starting index into the istate->cache array\n> +\t\t\t\tp->mmap = mmap;\t\t\t\t\t// pointer to memory mapped index file\n> +\t\t\t\tp->ieot = ieot;\t\t\t\t\t// pointer to ieot\n> +\t\t\t\tp->ieot_offset = ieot_offset;\t// starting index into the ieot array\n> +\t\t\t\tp->ieot_work = ieot_work;\t\t// count of ieot entries to process\n> +\t\t\t\tif (pthread_create(&p->pthread, NULL, load_cache_entries_thread, p))\n> +\t\t\t\t\tdie(\"unable to create threaded load_cache_entries\");\n> +\n> +\t\t\t\t// increment by the number of cache entries in the ieot block being processed\n> +\t\t\t\tfor (j = 0; j < ieot_work; j++)\n> +\t\t\t\t\toffset += ieot->entries[ieot_offset + j].nr;\n> +\t\t\t\tieot_offset += ieot_work;\n> +\t\t\t}\n> +\t\t\tfor (i = 0; i < threads; i++) {\n> +\t\t\t\tstruct load_cache_entries_thread_data *p = data + i;\n> +\t\t\t\tif (pthread_join(p->pthread, NULL))\n> +\t\t\t\t\tdie(\"unable to join threaded load_cache_entries\");\n> +\t\t\t\tsrc_offset += p->consumed;\t\t// # of bytes in index file processed\n> +\t\t\t}\n> +\t\t\tfree(data);\n> +\t\t}\n> +\t\tfree(ieot);\n>   \t}\n> -\tstrbuf_release(&previous_name_buf);\n> +#endif\n> +\n>   \tistate->timestamp.sec = st.st_mtime;\n>   \tistate->timestamp.nsec = ST_MTIME_NSEC(st);\n>   \n> @@ -2258,6 +2505,9 @@ static int do_write_index(struct index_state *istate, struct tempfile *tempfile,\n>   \tstruct stat st;\n>   \tstruct strbuf previous_name_buf = STRBUF_INIT, *previous_name;\n>   \tint drop_cache_tree = 0;\n> +\tint ieot_work = 1;\n> +\tstruct index_entry_offset_table *ieot = NULL;\n> +\tint offset, nr;\n>   \n>   \tfor (i = removed = extended = 0; i < entries; i++) {\n>   \t\tif (cache[i]->ce_flags & CE_REMOVE)\n> @@ -2291,6 +2541,22 @@ static int do_write_index(struct index_state *istate, struct tempfile *tempfile,\n>   \tif (ce_write(&c, newfd, &hdr, sizeof(hdr)) < 0)\n>   \t\treturn -1;\n>   \n> +\tif (!strip_extensions && core_fast_index) {\n> +\t\tint ieot_blocks, cpus = online_cpus();\n> +\n> +\t\tieot_blocks = istate->cache_nr / THREAD_COST;\n> +\t\tif (ieot_blocks > cpus)\n> +\t\t\tieot_blocks = cpus;\n> +\t\tif (ieot_blocks >= 1) {\n> +\t\t\tieot = xcalloc(sizeof(struct index_entry_offset_table)\n> +\t\t\t\t+ (ieot_blocks * sizeof(struct index_entry_offset)), 1);\n> +\t\t\tieot->nr = 0;\n> +\t\t}\n> +\t\tieot_work = DIV_ROUND_UP(entries, ieot_blocks);\n> +\t}\n> +\n> +\toffset = lseek(newfd, 0, SEEK_CUR) + write_buffer_len;\n> +\tnr = 0;\n>   \tprevious_name = (hdr_version == 4) ? &previous_name_buf : NULL;\n>   \tfor (i = 0; i < entries; i++) {\n>   \t\tstruct cache_entry *ce = cache[i];\n> @@ -2311,8 +2577,28 @@ static int do_write_index(struct index_state *istate, struct tempfile *tempfile,\n>   \n>   \t\t\tdrop_cache_tree = 1;\n>   \t\t}\n> +\t\tif (ieot && i && (i % ieot_work == 0)) {\n> +\t\t\tieot->entries[ieot->nr].nr = nr;\n> +\t\t\tieot->entries[ieot->nr].offset = offset;\n> +\t\t\tieot->nr++;\n> +\t\t\t/*\n> +\t\t\t * If we have a V4 index, set the first byte to an invalid\n> +\t\t\t * character to ensure there is nothing common with the previous\n> +\t\t\t * entry\n> +\t\t\t */\n> +\t\t\tif (previous_name)\n> +\t\t\t\tprevious_name->buf[0] = 0;\n> +\t\t\tnr = 0;\n> +\t\t\toffset = lseek(newfd, 0, SEEK_CUR) + write_buffer_len;\n> +\t\t}\n>   \t\tif (ce_write_entry(&c, newfd, ce, previous_name) < 0)\n>   \t\t\treturn -1;\n> +\t\tnr++;\n> +\t}\n> +\tif (ieot && nr) {\n> +\t\tieot->entries[ieot->nr].nr = nr;\n> +\t\tieot->entries[ieot->nr].offset = offset;\n> +\t\tieot->nr++;\n>   \t}\n>   \tstrbuf_release(&previous_name_buf);\n>   \n> @@ -2361,6 +2647,18 @@ static int do_write_index(struct index_state *istate, struct tempfile *tempfile,\n>   \t\t\treturn -1;\n>   \t}\n>   \n> +\t/*\n> +\t * CACHE_EXT_FASTINDEX must be written as the last entry before the SHA1\n> +\t * so that it can be found and processed before all the index entries are\n> +\t * read.\n> +\t */\n> +\tif (!strip_extensions && ieot) {\n> +\t\terr = write_ieot_extension(&c, newfd, ieot);\n> +\t\tfree(ieot);\n> +\t\tif (err)\n> +\t\t\treturn -1;\n> +\t}\n> +\n>   \tif (ce_flush(&c, newfd, istate->sha1))\n>   \t\treturn -1;\n>   \tif (close_tempfile(tempfile))\n> diff --git a/t/helper/test-dump-ieot.c b/t/helper/test-dump-ieot.c\n> new file mode 100644\n> index 0000000000..70aa31bb41\n> --- /dev/null\n> +++ b/t/helper/test-dump-ieot.c\n> @@ -0,0 +1,78 @@\n> +#include \"cache.h\"\n> +\n> +struct ondisk_cache_entry;\n> +extern struct cache_entry *create_from_disk(struct ondisk_cache_entry *ondisk,\n> +\tunsigned long *ent_size,\n> +\tstruct strbuf *previous_name,\n> +\tint use_length);\n> +\n> +int cmd_main(int ac, const char **av)\n> +{\n> +#ifndef NO_PTHREADS\n> +\tconst char *path;\n> +\tint fd, i;\n> +\tstruct stat st;\n> +\tvoid *mmap;\n> +\tsize_t mmap_size;\n> +\tstruct cache_header *hdr;\n> +\tstruct index_entry_offset_table *ieot;\n> +\tstruct strbuf previous_name_buf = STRBUF_INIT, *previous_name;\n> +\n> +\tsetup_git_directory();\n> +\tpath = get_index_file();\n> +\tfd = open(path, O_RDONLY);\n> +\tif (fd < 0) {\n> +\t\tdie_errno(\"%s: index file open failed\", path);\n> +\t}\n> +\n> +\tif (fstat(fd, &st))\n> +\t\tdie_errno(\"cannot stat the open index\");\n> +\n> +\tmmap_size = xsize_t(st.st_size);\n> +\tif (mmap_size < sizeof(struct cache_header) + 20)\n> +\t\tdie_errno(\"index file smaller than expected\");\n> +\n> +\tmmap = xmmap(NULL, mmap_size, PROT_READ, MAP_PRIVATE, fd, 0);\n> +\tif (mmap == MAP_FAILED)\n> +\t\tdie_errno(\"unable to map index file\");\n> +\tclose(fd);\n> +\n> +\thdr = mmap;\n> +\tif (ntohl(hdr->hdr_version) == 4)\n> +\t\tprevious_name = &previous_name_buf;\n> +\telse\n> +\t\tprevious_name = NULL;\n> +\n> +\tieot = read_ieot_extension(mmap, mmap_size);\n> +\tif (!ieot)\n> +\t\tdie_errno(\"missing or invalid extension\");\n> +\n> +\tprintf(\"IEOT with %d entries\\n\", ieot->nr);\n> +\tprintf(\"  Offset    Count Name\\n\");\n> +\tprintf(\"-------- -------- ------------------------\\n\");\n> +\tfor (i = 0; i < ieot->nr; i++) {\n> +\t\tstruct ondisk_cache_entry *disk_ce;\n> +\t\tstruct cache_entry *ce;\n> +\t\tunsigned long consumed;\n> +\n> +\t\tdisk_ce = (struct ondisk_cache_entry *)((char *)mmap + ieot->entries[i].offset);\n> +\t\tce = create_from_disk(disk_ce, &consumed, previous_name, 0);\n> +\t\t/*\n> +\t\t * If we have a V4 index, set the first byte to an invalid\n> +\t\t * character to ensure there is nothing common with the previous\n> +\t\t * entry\n> +\t\t */\n> +\t\tif (previous_name)\n> +\t\t\tprevious_name->buf[0] = 0;\n> +\t\tprintf(\"%8d %8d %.*s\\n\", ieot->entries[i].offset, ieot->entries[i].nr, ce->ce_namelen, ce->name);\n> +\t\tfree(ce);\n> +\t}\n> +\n> +\tfree(ieot);\n> +\tmunmap(mmap, mmap_size);\n> +\treturn 0;\n> +#else\n> +\tdie_errno(\"ieot only supported with PTHREADS\");\n> +\treturn -1;\n> +#endif\n> +}\n> diff --git a/t/helper/test-ieot.c b/t/helper/test-ieot.c\n> new file mode 100644\n> index 0000000000..75f28db001\n> --- /dev/null\n> +++ b/t/helper/test-ieot.c\n> @@ -0,0 +1,72 @@\n> +#include \"cache.h\"\n> +\n> +int compare_ce(const struct cache_entry *ce1, const struct cache_entry *ce2)\n> +{\n> +//\tstruct hashmap_entry ent;\n> +//\tstruct stat_data ce_stat_data;\n> +\n> +\tif (ce1->ce_mode != ce2->ce_mode) {\n> +\t\tprintf(\"ce_mode: %d:%d\\n\", ce1->ce_mode, ce2->ce_mode);\n> +\t\treturn 1;\n> +\t}\n> +\n> +\tif (ce1->ce_flags != ce2->ce_flags) {\n> +\t\tprintf(\"ce_flags: %d:%d\\n\", ce1->ce_flags, ce2->ce_flags);\n> +\t\treturn 1;\n> +\t}\n> +\n> +//\tunsigned int ce_namelen;\n> +\n> +\tif (ce1->index != ce2->index) {\n> +\t\tprintf(\"index: %d:%d\\n\", ce1->index, ce2->index);\n> +\t\treturn 1;\n> +\t}\n> +\n> +\tif (oidcmp(&ce1->oid, &ce2->oid)) {\n> +\t\tprintf(\"oid: %s:%s\\n\", oid_to_hex(&ce1->oid), oid_to_hex(&ce2->oid));\n> +\t\treturn 1;\n> +\t}\n> +\n> +\treturn 0;\n> +}\n> +\n> +extern int ignore_fast_index_config;\n> +\n> +int cmd_main(int ac, const char **av)\n> +{\n> +#ifndef NO_PTHREADS\n> +\tstatic struct index_state index;\n> +\tstatic struct index_state ieot;\n> +\tint i;\n> +\n> +\tsetup_git_directory();\n> +\tignore_fast_index_config = 1;\n> +\tcore_fast_index = 0;\n> +\tread_index(&index);\n> +\tcore_fast_index = 1;\n> +\tread_index(&ieot);\n> +\n> +\tfor (i = 0; i < index.cache_nr; i++) {\n> +\t\tif (compare_ce(index.cache[i], ieot.cache[i])) {\n> +\t\t\tstruct cache_entry *ce;\n> +\n> +\t\t\tce = index.cache[i];\n> +\t\t\tprintf(\"%06o %s %d\\t%s\\n\", ce->ce_mode,\n> +\t\t\t\toid_to_hex(&ce->oid), ce_stage(ce), ce->name);\n> +\t\t\tce = ieot.cache[i];\n> +\t\t\tprintf(\"%06o %s %d\\t%s\\n\", ce->ce_mode,\n> +\t\t\t\toid_to_hex(&ce->oid), ce_stage(ce), ce->name);\n> +\n> +\t\t\tdie_errno(\"cache entry %d does not match\", i);\n> +\t\t}\n> +\t}\n> +\n> +\tdiscard_index(&ieot);\n> +\tdiscard_index(&index);\n> +\tprintf(\"Cache entires are the same\\n\");\n> +\treturn 0;\n> +#else\n> +\tdie_errno(\"ieot only supported with PTHREADS\");\n> +\treturn -1;\n> +#endif\n> +}\n> \n> base-commit: dbc8d81072630bc50324938b9ac950140669ced9\n> \n"},{"id":"332079","messageId":"8906812f-ae06-8540-8fd0-6c740441126c@gmail.com","threadId":"47137","inReplyTo":"20171108144253.34428-1-benpeart@microsoft.com","subject":"Re: [RFC] fastindex: parallelize index load","fromName":"Ben Peart","fromEmail":"peartben@gmail.com","sentAt":"2017-11-08T14:51:03Z","receivedAt":"2017-11-08T14:51:12Z","isPatch":false,"sender":{"key":"benpeart@microsoft.com","avatar":"https://avatars.githubusercontent.com/u/15252029?v=4"},"body":"This is an RFC because it works but I've not done the code cleanup,\nadded tests, support in the update-index command to add/remove it, etc.\nAs a result, there is no reason to point out all the places I'm not\ncurrently following the git coding style. :)\n\nI wanted to get feedback on the concept first, especially as the way I'm\nadding the TOC information via an extension that can be read before the\nvariable length section of cache entries and other extensions is a bit\nof a clever hack, as is the resetting of the prefix encoding for V4\nindexes.  They are, however, entirely backwards compatible with older\nversions of git which can still properly read and use the index.\n\nThe effect can be seen using t/helper/test-read-cache:\n\n                                 fastindex\ntest            count   files   TRUE    FALSE     Savings\n------------------------------------------------------------------------\ntest-read-cache 500     100K    6.39    8.33      23.36%\ntest-read-cache 100     1M      12.49   18.68     33.12%\n\n\nOn 11/8/2017 9:42 AM, Ben Peart wrote:\n> This patch will address the CPU cost of loading the index by adding\n> additional data to the index that will allow us to multi-thread the\n> loading and conversion of cache entries.\n> \n> It accomplishes this by adding an (optional) index extension that is a\n> table of offsets to blocks of cache entries in the index file.  With\n> version 2, 3 or even 4 indexes, we can utilize the Index Entry Offset Table\n> (IEOT) to parallelize the loading and conversion of the cache entries\n> across all available CPU cores.\n> \n> To make this work for V4 indexes, when writing the index, it periodically\n> \"resets\" the compression by encoding the current entry as if the path\n> name for the previous entry is completely different and saves the offset\n> of that entry in the IEOT.  Basically, with V4 indexes, it generates\n> offsets into blocks of prefix-compressed entries.\n> \n> To enable reading the IEOT extension before reading all the variable\n> length cache entries and other extensions, the IEOT is written last,\n> right before the trailing SHA1.\n> \n> The format of that extension has the signature bytes and size at the\n> beginning (like a normal extension) as well as at the end in reverse\n> order to enable parsing the extension by seeking back from the end of\n> the file.  See the diagram below for details.\n> \n> During index load, read the index header then seek to the end of the\n> index, back up past the trailing SHA1 and look for the IEOT extension\n> signature bytes.  If they exist, read the 32-bit size and seek back to\n> the extension header and verify the leading header and size bits.  If\n> they all match, we can be assured we have a valid IEOT extension.\n> \n> If the IEOT extension is available, create multiple threads to divide\n> the work of loading and converting the cache entries across all\n> available CPU cores.  Once the cache entries are loaded, the rest of the\n> extensions can be loaded and processed normally (skipping the IEOT entry\n> as it has already been processed).  If the IEOT extension is not\n> available then parsing the index will proceed as usual with a single thread.\n> \n> The on-disk format looks like this:\n> \n> Index header\n> Cache entry 1\n> Cache entry 2\n> .\n> .\n> Extension 1\n> Extension 2\n> .\n> .\n> Index Entry Offset Table Extension (must be written last!)\n> IEOT signature bytes\n> 32-bit size\n> 32-bit version\n> 32-bit Cache Entry Offset 1\n> 32-bit Cache Entry count\n> 32-bit Cache Entry Offset 2\n> 32-bit Cache Entry count\n> .\n> .\n> 32-bit version\n> 32-bit size\n> IEOT signature bytes\n> SHA1\n> \n> Signed-off-by: Ben Peart <benpeart@microsoft.com>\n> ---\n> \n> Notes:\n>      Base Ref: v2.14.3.windows.1\n>      Web-Diff: https://github.com/benpeart/git/commit/1e818c7835\n>      Checkout: git fetch https://github.com/benpeart/git fastindex-v1 && git checkout 1e818c7835\n> \n>   Makefile                  |   2 +\n>   cache.h                   |  18 +++\n>   config.c                  |  20 +++\n>   config.h                  |   1 +\n>   environment.c             |   3 +\n>   read-cache.c              | 340 +++++++++++++++++++++++++++++++++++++++++++---\n>   t/helper/test-dump-ieot.c |  78 +++++++++++\n>   t/helper/test-ieot.c      |  72 ++++++++++\n>   8 files changed, 513 insertions(+), 21 deletions(-)\n>   create mode 100644 t/helper/test-dump-ieot.c\n>   create mode 100644 t/helper/test-ieot.c\n> \n> diff --git a/Makefile b/Makefile\n> index ebd0a75d87..99fa8dd8d3 100644\n> --- a/Makefile\n> +++ b/Makefile\n> @@ -640,12 +640,14 @@ TEST_PROGRAMS_NEED_X += test-config\n>   TEST_PROGRAMS_NEED_X += test-date\n>   TEST_PROGRAMS_NEED_X += test-delta\n>   TEST_PROGRAMS_NEED_X += test-dump-cache-tree\n> +TEST_PROGRAMS_NEED_X += test-dump-ieot\n>   TEST_PROGRAMS_NEED_X += test-dump-split-index\n>   TEST_PROGRAMS_NEED_X += test-dump-untracked-cache\n>   TEST_PROGRAMS_NEED_X += test-fake-ssh\n>   TEST_PROGRAMS_NEED_X += test-genrandom\n>   TEST_PROGRAMS_NEED_X += test-hashmap\n>   TEST_PROGRAMS_NEED_X += test-helper\n> +TEST_PROGRAMS_NEED_X += test-ieot\n>   TEST_PROGRAMS_NEED_X += test-index-version\n>   TEST_PROGRAMS_NEED_X += test-lazy-init-name-hash\n>   TEST_PROGRAMS_NEED_X += test-line-buffer\n> diff --git a/cache.h b/cache.h\n> index 45597732d8..e9ec1bf41a 100644\n> --- a/cache.h\n> +++ b/cache.h\n> @@ -326,6 +326,7 @@ static inline unsigned int canon_mode(unsigned int mode)\n>   #define CACHE_TREE_CHANGED\t(1 << 5)\n>   #define SPLIT_INDEX_ORDERED\t(1 << 6)\n>   #define UNTRACKED_CHANGED\t(1 << 7)\n> +#define IEOT_CHANGED\t\t(1 << 9)\n>   \n>   struct split_index;\n>   struct untracked_cache;\n> @@ -770,6 +771,7 @@ extern char *git_replace_ref_base;\n>   \n>   extern int fsync_object_files;\n>   extern int core_preload_index;\n> +extern int core_fast_index;\n>   extern int core_apply_sparse_checkout;\n>   extern int precomposed_unicode;\n>   extern int protect_hfs;\n> @@ -2025,4 +2027,20 @@ void sleep_millisec(int millisec);\n>    */\n>   void safe_create_dir(const char *dir, int share);\n>   \n> +\n> +#ifndef NO_PTHREADS\n> +struct index_entry_offset\n> +{\t// starting byte offset into index file, count of index entries in this block\n> +\tint offset, nr;\n> +};\n> +\n> +struct index_entry_offset_table\n> +{\n> +\tint nr;\t\t\t\t// number of ieot entries in array\n> +\tstruct index_entry_offset entries[0];\n> +};\n> +\n> +struct index_entry_offset_table *read_ieot_extension(void *mmap, size_t mmap_size);\n> +#endif\n> +\n>   #endif /* CACHE_H */\n> diff --git a/config.c b/config.c\n> index adcd2c2441..056c21b0c9 100644\n> --- a/config.c\n> +++ b/config.c\n> @@ -1203,6 +1203,11 @@ static int git_default_core_config(const char *var, const char *value, void *cb)\n>   \t\treturn 0;\n>   \t}\n>   \n> +\tif (!strcmp(var, \"core.fastindex\")) {\n> +\t\tcore_fast_index = git_config_bool(var, value);\n> +\t\treturn 0;\n> +\t}\n> +\n>   \tif (!strcmp(var, \"core.createobject\")) {\n>   \t\tif (!strcmp(value, \"rename\"))\n>   \t\t\tobject_creation_mode = OBJECT_CREATION_USES_RENAMES;\n> @@ -2116,6 +2121,21 @@ int git_config_get_max_percent_split_change(void)\n>   \treturn -1; /* default value */\n>   }\n>   \n> +int ignore_fast_index_config;\n> +int git_config_get_fast_index(void)\n> +{\n> +\tint val;\n> +\n> +\t/* Hack for test programs like test-ieot */\n> +\tif (ignore_fast_index_config)\n> +\t\treturn core_fast_index;\n> +\n> +\tif (!git_config_get_maybe_bool(\"core.fastindex\", &val))\n> +\t\treturn val;\n> +\n> +\treturn -1; /* default value */\n> +}\n> +\n>   NORETURN\n>   void git_die_config_linenr(const char *key, const char *filename, int linenr)\n>   {\n> diff --git a/config.h b/config.h\n> index 0352da117b..bb73c36e0a 100644\n> --- a/config.h\n> +++ b/config.h\n> @@ -201,6 +201,7 @@ extern int git_config_get_pathname(const char *key, const char **dest);\n>   extern int git_config_get_untracked_cache(void);\n>   extern int git_config_get_split_index(void);\n>   extern int git_config_get_max_percent_split_change(void);\n> +extern int git_config_get_fast_index(void);\n>   \n>   /* This dies if the configured or default date is in the future */\n>   extern int git_config_get_expiry(const char *key, const char **output);\n> diff --git a/environment.c b/environment.c\n> index c974bed180..bb8405cd91 100644\n> --- a/environment.c\n> +++ b/environment.c\n> @@ -86,6 +86,9 @@ int auto_comment_line_char;\n>   /* Parallel index stat data preload? */\n>   int core_preload_index = 1;\n>   \n> +/* Parallel index cache entry loading? */\n> +int core_fast_index;\n> +\n>   /*\n>    * This is a hack for test programs like test-dump-untracked-cache to\n>    * ensure that they do not modify the untracked cache when reading it.\n> diff --git a/read-cache.c b/read-cache.c\n> index bc925b6736..dc2fadb61f 100644\n> --- a/read-cache.c\n> +++ b/read-cache.c\n> @@ -19,6 +19,7 @@\n>   #include \"varint.h\"\n>   #include \"split-index.h\"\n>   #include \"utf8.h\"\n> +#include \"thread-utils.h\"\n>   \n>   #ifndef NO_PTHREADS\n>   #include <pthread.h>\n> @@ -42,11 +43,12 @@\n>   #define CACHE_EXT_RESOLVE_UNDO 0x52455543 /* \"REUC\" */\n>   #define CACHE_EXT_LINK 0x6c696e6b\t  /* \"link\" */\n>   #define CACHE_EXT_UNTRACKED 0x554E5452\t  /* \"UNTR\" */\n> +#define CACHE_EXT_FASTINDEX 0x49454F54\t  /* \"IEOT\" */\n>   \n>   /* changes that can be kept in $GIT_DIR/index (basically all extensions) */\n>   #define EXTMASK (RESOLVE_UNDO_CHANGED | CACHE_TREE_CHANGED | \\\n>   \t\t CE_ENTRY_ADDED | CE_ENTRY_REMOVED | CE_ENTRY_CHANGED | \\\n> -\t\t SPLIT_INDEX_ORDERED | UNTRACKED_CHANGED)\n> +\t\t SPLIT_INDEX_ORDERED | UNTRACKED_CHANGED | CACHE_EXT_FASTINDEX)\n>   \n>   struct index_state the_index;\n>   static const char *alternate_index_output;\n> @@ -1581,6 +1583,9 @@ static int read_index_extension(struct index_state *istate,\n>   \tcase CACHE_EXT_UNTRACKED:\n>   \t\tistate->untracked = read_untracked_extension(data, sz);\n>   \t\tbreak;\n> +\tcase CACHE_EXT_FASTINDEX:\n> +\t\t/* already handled in do_read_index() */\n> +\t\tbreak;\n>   \tdefault:\n>   \t\tif (*ext < 'A' || 'Z' < *ext)\n>   \t\t\treturn error(\"index uses %.4s extension, which we do not understand\",\n> @@ -1634,10 +1639,12 @@ static struct cache_entry *cache_entry_from_ondisk(struct ondisk_cache_entry *on\n>    * number of bytes to be stripped from the end of the previous name,\n>    * and the bytes to append to the result, to come up with its name.\n>    */\n> -static unsigned long expand_name_field(struct strbuf *name, const char *cp_)\n> +static unsigned long expand_name_field(struct strbuf *name, const char *cp_, int use_length)\n>   {\n>   \tconst unsigned char *ep, *cp = (const unsigned char *)cp_;\n>   \tsize_t len = decode_varint(&cp);\n> +\tif (!use_length)\n> +\t\tlen = name->len;\n>   \n>   \tif (name->len < len)\n>   \t\tdie(\"malformed name field in the index\");\n> @@ -1648,9 +1655,10 @@ static unsigned long expand_name_field(struct strbuf *name, const char *cp_)\n>   \treturn (const char *)ep + 1 - cp_;\n>   }\n>   \n> -static struct cache_entry *create_from_disk(struct ondisk_cache_entry *ondisk,\n> +struct cache_entry *create_from_disk(struct ondisk_cache_entry *ondisk,\n>   \t\t\t\t\t    unsigned long *ent_size,\n> -\t\t\t\t\t    struct strbuf *previous_name)\n> +\t\t\t\t\t    struct strbuf *previous_name,\n> +\t\t\t\t\t\tint use_length)\n>   {\n>   \tstruct cache_entry *ce;\n>   \tsize_t len;\n> @@ -1684,7 +1692,7 @@ static struct cache_entry *create_from_disk(struct ondisk_cache_entry *ondisk,\n>   \t\t*ent_size = ondisk_ce_size(ce);\n>   \t} else {\n>   \t\tunsigned long consumed;\n> -\t\tconsumed = expand_name_field(previous_name, name);\n> +\t\tconsumed = expand_name_field(previous_name, name, use_length);\n>   \t\tce = cache_entry_from_ondisk(ondisk, flags,\n>   \t\t\t\t\t     previous_name->buf,\n>   \t\t\t\t\t     previous_name->len);\n> @@ -1755,16 +1763,208 @@ static void post_read_index_from(struct index_state *istate)\n>   \ttweak_split_index(istate);\n>   }\n>   \n> +static unsigned long load_cache_entries(struct index_state *istate, int offset, int nr, void *mmap, unsigned long start_offset)\n> +{\n> +\tint i;\n> +\tunsigned long src_offset = start_offset;\n> +\tstruct strbuf previous_name_buf = STRBUF_INIT, *previous_name;\n> +\n> +\tif (istate->version == 4)\n> +\t\tprevious_name = &previous_name_buf;\n> +\telse\n> +\t\tprevious_name = NULL;\n> +\n> +\tfor (i = offset; i < offset + nr; i++) {\n> +\t\tstruct ondisk_cache_entry *disk_ce;\n> +\t\tstruct cache_entry *ce;\n> +\t\tunsigned long consumed;\n> +\n> +\t\tdisk_ce = (struct ondisk_cache_entry *)((char *)mmap + src_offset);\n> +\t\tce = create_from_disk(disk_ce, &consumed, previous_name, i == offset ? 0 : 1);\n> +\t\tset_index_entry(istate, i, ce);\n> +\n> +\t\tsrc_offset += consumed;\n> +\t}\n> +\tstrbuf_release(&previous_name_buf);\n> +\treturn src_offset - start_offset;\n> +}\n> +\n> +#ifndef NO_PTHREADS\n> +\n> +/*\n> + * Mostly randomly chosen cache entries per thread (it works on my machine):\n> + * we want to have at least 7500 cache entries per thread for it to\n> + * be worth starting a thread.\n> + */\n> +#define THREAD_COST\t\t(7500)\n> +#define IEOT_VERSION\t(1)\n> +\n> +static int ce_write(git_SHA_CTX *context, int fd, void *data, unsigned int len);\n> +\n> +static int write_index_ext_header(git_SHA_CTX *context, int fd,\n> +\tunsigned int ext, unsigned int sz);\n> +\n> +struct load_cache_entries_thread_data\n> +{\n> +\tpthread_t pthread;\n> +\tstruct index_state *istate;\n> +\tint offset;\t\t\t// starting index into the istate->cache array\n> +\tvoid *mmap;\t\t\t// pointer to memory mapped index file\n> +\tunsigned long consumed;\t// return # of bytes in index file processed\n> +\tstruct index_entry_offset_table *ieot;\t// pointer to ieot\n> +\tint ieot_offset;\t// starting index into the ieot array\n> +\tint ieot_work;\t\t// count of ieot entries to process\n> +};\n> +\n> +/*\n> + * A thread proc to run the load_cache_entries() computation\n> + * across multiple background threads.\n> + */\n> +static void *load_cache_entries_thread(void *_data)\n> +{\n> +\tstruct load_cache_entries_thread_data *p = _data;\n> +\tint i;\n> +\n> +\t// itterate across all ieot blocks assigned to this thread\n> +\tfor (i = p->ieot_offset; i < p->ieot_offset + p->ieot_work; i++) {\n> +\t\tp->consumed += load_cache_entries(p->istate, p->offset, p->ieot->entries[i].nr, p->mmap, p->ieot->entries[i].offset);\n> +\t\tp->offset += p->ieot->entries[i].nr;\n> +\t}\n> +\treturn NULL;\n> +}\n> +\n> +struct index_entry_offset_table *read_ieot_extension(void *mmap, size_t mmap_size)\n> +{\n> +\t/*\n> +\t * The IEOT extension is guaranteed to be last so that it can be found\n> +\t * by scanning backwards from the EOF.  In addition to the regular 4-byte\n> +\t * extension name and 4-byte section length is network byte order, it\n> +\t * also stores the 4-byte extension name and section length in reverse order\n> +\t * at the end of the extension.\n> +\t *\n> +\t * IEOT\n> +\t * 4-byte length\n> +\t * 4-byte version\n> +\t * variable length extension data...\n> +\t * 4-byte version\n> +\t * 4-byte length\n> +\t * IEOT\n> +\t * <SHA1>\n> +\t *\n> +\t * If both names and lengths match, the extension is assumed to be valid.\n> +\t */\n> +\tconst char *index;\n> +\tuint32_t extsize_leading, extsize_trailing, ext_version;\n> +\tstruct index_entry_offset_table *ieot;\n> +\tint i, nr;\n> +\n> +\t/* validate the trailing extension signature */\n> +\tindex = (const char *)mmap + mmap_size - 20 - 4;\n> +\tif (CACHE_EXT(index) != CACHE_EXT_FASTINDEX)\n> +\t\treturn NULL;\n> +\tindex -= sizeof(uint32_t);\n> +\n> +\t/*\n> +\t * Validate the offset we're going to look for the leading extension\n> +\t * signature is past the index header.\n> +\t */\n> +\textsize_trailing = get_be32(index);\n> +\tif ((index - extsize_trailing) < ((const char *)mmap + 12))\n> +\t\treturn NULL;\n> +\tindex -= sizeof(uint32_t);\n> +\n> +\t/* validate the trailing version is IEOT_VERSION */\n> +\text_version = get_be32(index);\n> +\tif (ext_version != IEOT_VERSION)\n> +\t\treturn NULL;\n> +\tindex -= (extsize_trailing - sizeof(uint32_t));\n> +\n> +\t/* validate the leading extension signature */\n> +\tif (CACHE_EXT(index) != CACHE_EXT_FASTINDEX)\n> +\t\treturn NULL;\n> +\tindex += sizeof(uint32_t);\n> +\n> +\t/* validate the leading extension size */\n> +\textsize_leading = get_be32(index);\n> +\tif (extsize_leading != extsize_trailing)\n> +\t\treturn NULL;\n> +\tindex += sizeof(uint32_t);\n> +\n> +\t/* validate the leading version is IEOT_VERSION */\n> +\text_version = get_be32(index);\n> +\tif (ext_version != IEOT_VERSION)\n> +\t\treturn NULL;\n> +\tindex += sizeof(uint32_t);\n> +\n> +\t/* extension size - leading/trailing version bytes - trailing size - trailing signature / bytes per entry */\n> +\tnr = (extsize_leading - sizeof(uint32_t) - sizeof(uint32_t) - sizeof(uint32_t) - 4) / (sizeof(uint32_t) + sizeof(uint32_t));\n> +\tassert(nr);\n> +\tieot = xmalloc(sizeof(struct index_entry_offset_table)\n> +\t\t+ (nr * sizeof(struct index_entry_offset)));\n> +\tieot->nr = nr;\n> +\tfor (i = 0; i < nr; i++) {\n> +\t\tieot->entries[i].offset = get_be32(index);\n> +\t\tindex += sizeof(uint32_t);\n> +\t\tieot->entries[i].nr = get_be32(index);\n> +\t\tindex += sizeof(uint32_t);\n> +\t}\n> +\n> +\treturn ieot;\n> +}\n> +\n> +static int write_ieot_extension(git_SHA_CTX *context, int fd, struct index_entry_offset_table *ieot)\n> +{\n> +\tstruct strbuf sb = STRBUF_INIT;\n> +\tuint32_t buffer;\n> +\tint i, err;\n> +\n> +\t/* version */\n> +\tput_be32(&buffer, IEOT_VERSION);\n> +\tstrbuf_add(&sb, &buffer, sizeof(uint32_t));\n> +\n> +\t/* ieot */\n> +\tfor (i = 0; i < ieot->nr; i++) {\n> +\n> +\t\t/* offset */\n> +\t\tput_be32(&buffer, ieot->entries[i].offset);\n> +\t\tstrbuf_add(&sb, &buffer, sizeof(uint32_t));\n> +\n> +\t\t/* count */\n> +\t\tput_be32(&buffer, ieot->entries[i].nr);\n> +\t\tstrbuf_add(&sb, &buffer, sizeof(uint32_t));\n> +\t}\n> +\n> +\t/* version */\n> +\tput_be32(&buffer, IEOT_VERSION);\n> +\tstrbuf_add(&sb, &buffer, sizeof(uint32_t));\n> +\n> +\t/* size */\n> +\tput_be32(&buffer, sb.len + sizeof(uint32_t) + 4);\n> +\tstrbuf_add(&sb, &buffer, sizeof(uint32_t));\n> +\n> +\t/* signature */\n> +\tput_be32(&buffer, CACHE_EXT_FASTINDEX);\n> +\tstrbuf_add(&sb, &buffer, 4);\n> +\n> +\t/* leading signature and size + extension data */\n> +\terr = write_index_ext_header(context, fd, CACHE_EXT_FASTINDEX, sb.len) < 0\n> +\t\t|| ce_write(context, fd, sb.buf, sb.len) < 0;\n> +\tstrbuf_release(&sb);\n> +\n> +\treturn err;\n> +}\n> +\n> +#endif\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> -\tint fd, i;\n> +\tint fd;\n>   \tstruct stat st;\n>   \tunsigned long src_offset;\n>   \tstruct cache_header *hdr;\n>   \tvoid *mmap;\n>   \tsize_t mmap_size;\n> -\tstruct strbuf previous_name_buf = STRBUF_INIT, *previous_name;\n>   #ifndef NO_PTHREADS\n>   \tstruct verify_hdr_thread_data verify_hdr_thread_data;\n>   #endif\n> @@ -1819,24 +2019,71 @@ int do_read_index(struct index_state *istate, const char *path, int must_exist)\n>   \tistate->cache = xcalloc(istate->cache_alloc, sizeof(*istate->cache));\n>   \tistate->initialized = 1;\n>   \n> -\tif (istate->version == 4)\n> -\t\tprevious_name = &previous_name_buf;\n> -\telse\n> -\t\tprevious_name = NULL;\n> -\n>   \tsrc_offset = sizeof(*hdr);\n> -\tfor (i = 0; i < istate->cache_nr; i++) {\n> -\t\tstruct ondisk_cache_entry *disk_ce;\n> -\t\tstruct cache_entry *ce;\n> -\t\tunsigned long consumed;\n> +#ifdef NO_PTHREADS\n> +\tsrc_offset += load_cache_entries(istate, 0, istate->cache_nr, mmap, src_offset);\n> +#else\n> +\tif (git_config_get_fast_index() != 1) {\n> +\t\tsrc_offset += load_cache_entries(istate, 0, istate->cache_nr, mmap, src_offset);\n> +\t} else {\n> +\t\tstruct index_entry_offset_table *ieot;\n> +\t\tint threads, cpus = online_cpus();\n>   \n> -\t\tdisk_ce = (struct ondisk_cache_entry *)((char *)mmap + src_offset);\n> -\t\tce = create_from_disk(disk_ce, &consumed, previous_name);\n> -\t\tset_index_entry(istate, i, ce);\n> +\t\tthreads = istate->cache_nr / THREAD_COST;\n> +\t\tif (threads > cpus)\n> +\t\t\tthreads = cpus;\n>   \n> -\t\tsrc_offset += consumed;\n> +\t\t/*\n> +\t\t * Locate and read the fast index extension so that we can use it\n> +\t\t * to multi-thread the reading of the cache entries.\n> +\t\t */\n> +\t\tieot = read_ieot_extension(mmap, mmap_size);\n> +\t\tif (threads < 2 || !ieot) {\n> +\t\t\tsrc_offset += load_cache_entries(istate, 0, istate->cache_nr, mmap, src_offset);\n> +\t\t} else {\n> +\t\t\tint i, offset, ieot_work, ieot_offset;\n> +\t\t\tstruct load_cache_entries_thread_data *data;\n> +\n> +\t\t\t/* ensure we have no more threads than we have blocks to process */\n> +\t\t\tif (threads > ieot->nr)\n> +\t\t\t\tthreads = ieot->nr;\n> +\t\t\tdata = xcalloc(threads * sizeof(struct load_cache_entries_thread_data), 1);\n> +\n> +\t\t\toffset = ieot_offset = 0;\n> +\t\t\tieot_work = DIV_ROUND_UP(ieot->nr, threads);\n> +\t\t\tfor (i = 0; i < threads; i++) {\n> +\t\t\t\tstruct load_cache_entries_thread_data *p = &data[i];\n> +\t\t\t\tint j;\n> +\n> +\t\t\t\tif (ieot_offset + ieot_work > ieot->nr)\n> +\t\t\t\t\tieot_work = ieot->nr - ieot_offset;\n> +\n> +\t\t\t\tp->istate = istate;\n> +\t\t\t\tp->offset = offset;\t\t\t\t// starting index into the istate->cache array\n> +\t\t\t\tp->mmap = mmap;\t\t\t\t\t// pointer to memory mapped index file\n> +\t\t\t\tp->ieot = ieot;\t\t\t\t\t// pointer to ieot\n> +\t\t\t\tp->ieot_offset = ieot_offset;\t// starting index into the ieot array\n> +\t\t\t\tp->ieot_work = ieot_work;\t\t// count of ieot entries to process\n> +\t\t\t\tif (pthread_create(&p->pthread, NULL, load_cache_entries_thread, p))\n> +\t\t\t\t\tdie(\"unable to create threaded load_cache_entries\");\n> +\n> +\t\t\t\t// increment by the number of cache entries in the ieot block being processed\n> +\t\t\t\tfor (j = 0; j < ieot_work; j++)\n> +\t\t\t\t\toffset += ieot->entries[ieot_offset + j].nr;\n> +\t\t\t\tieot_offset += ieot_work;\n> +\t\t\t}\n> +\t\t\tfor (i = 0; i < threads; i++) {\n> +\t\t\t\tstruct load_cache_entries_thread_data *p = data + i;\n> +\t\t\t\tif (pthread_join(p->pthread, NULL))\n> +\t\t\t\t\tdie(\"unable to join threaded load_cache_entries\");\n> +\t\t\t\tsrc_offset += p->consumed;\t\t// # of bytes in index file processed\n> +\t\t\t}\n> +\t\t\tfree(data);\n> +\t\t}\n> +\t\tfree(ieot);\n>   \t}\n> -\tstrbuf_release(&previous_name_buf);\n> +#endif\n> +\n>   \tistate->timestamp.sec = st.st_mtime;\n>   \tistate->timestamp.nsec = ST_MTIME_NSEC(st);\n>   \n> @@ -2258,6 +2505,9 @@ static int do_write_index(struct index_state *istate, struct tempfile *tempfile,\n>   \tstruct stat st;\n>   \tstruct strbuf previous_name_buf = STRBUF_INIT, *previous_name;\n>   \tint drop_cache_tree = 0;\n> +\tint ieot_work = 1;\n> +\tstruct index_entry_offset_table *ieot = NULL;\n> +\tint offset, nr;\n>   \n>   \tfor (i = removed = extended = 0; i < entries; i++) {\n>   \t\tif (cache[i]->ce_flags & CE_REMOVE)\n> @@ -2291,6 +2541,22 @@ static int do_write_index(struct index_state *istate, struct tempfile *tempfile,\n>   \tif (ce_write(&c, newfd, &hdr, sizeof(hdr)) < 0)\n>   \t\treturn -1;\n>   \n> +\tif (!strip_extensions && core_fast_index) {\n> +\t\tint ieot_blocks, cpus = online_cpus();\n> +\n> +\t\tieot_blocks = istate->cache_nr / THREAD_COST;\n> +\t\tif (ieot_blocks > cpus)\n> +\t\t\tieot_blocks = cpus;\n> +\t\tif (ieot_blocks >= 1) {\n> +\t\t\tieot = xcalloc(sizeof(struct index_entry_offset_table)\n> +\t\t\t\t+ (ieot_blocks * sizeof(struct index_entry_offset)), 1);\n> +\t\t\tieot->nr = 0;\n> +\t\t}\n> +\t\tieot_work = DIV_ROUND_UP(entries, ieot_blocks);\n> +\t}\n> +\n> +\toffset = lseek(newfd, 0, SEEK_CUR) + write_buffer_len;\n> +\tnr = 0;\n>   \tprevious_name = (hdr_version == 4) ? &previous_name_buf : NULL;\n>   \tfor (i = 0; i < entries; i++) {\n>   \t\tstruct cache_entry *ce = cache[i];\n> @@ -2311,8 +2577,28 @@ static int do_write_index(struct index_state *istate, struct tempfile *tempfile,\n>   \n>   \t\t\tdrop_cache_tree = 1;\n>   \t\t}\n> +\t\tif (ieot && i && (i % ieot_work == 0)) {\n> +\t\t\tieot->entries[ieot->nr].nr = nr;\n> +\t\t\tieot->entries[ieot->nr].offset = offset;\n> +\t\t\tieot->nr++;\n> +\t\t\t/*\n> +\t\t\t * If we have a V4 index, set the first byte to an invalid\n> +\t\t\t * character to ensure there is nothing common with the previous\n> +\t\t\t * entry\n> +\t\t\t */\n> +\t\t\tif (previous_name)\n> +\t\t\t\tprevious_name->buf[0] = 0;\n> +\t\t\tnr = 0;\n> +\t\t\toffset = lseek(newfd, 0, SEEK_CUR) + write_buffer_len;\n> +\t\t}\n>   \t\tif (ce_write_entry(&c, newfd, ce, previous_name) < 0)\n>   \t\t\treturn -1;\n> +\t\tnr++;\n> +\t}\n> +\tif (ieot && nr) {\n> +\t\tieot->entries[ieot->nr].nr = nr;\n> +\t\tieot->entries[ieot->nr].offset = offset;\n> +\t\tieot->nr++;\n>   \t}\n>   \tstrbuf_release(&previous_name_buf);\n>   \n> @@ -2361,6 +2647,18 @@ static int do_write_index(struct index_state *istate, struct tempfile *tempfile,\n>   \t\t\treturn -1;\n>   \t}\n>   \n> +\t/*\n> +\t * CACHE_EXT_FASTINDEX must be written as the last entry before the SHA1\n> +\t * so that it can be found and processed before all the index entries are\n> +\t * read.\n> +\t */\n> +\tif (!strip_extensions && ieot) {\n> +\t\terr = write_ieot_extension(&c, newfd, ieot);\n> +\t\tfree(ieot);\n> +\t\tif (err)\n> +\t\t\treturn -1;\n> +\t}\n> +\n>   \tif (ce_flush(&c, newfd, istate->sha1))\n>   \t\treturn -1;\n>   \tif (close_tempfile(tempfile))\n> diff --git a/t/helper/test-dump-ieot.c b/t/helper/test-dump-ieot.c\n> new file mode 100644\n> index 0000000000..70aa31bb41\n> --- /dev/null\n> +++ b/t/helper/test-dump-ieot.c\n> @@ -0,0 +1,78 @@\n> +#include \"cache.h\"\n> +\n> +struct ondisk_cache_entry;\n> +extern struct cache_entry *create_from_disk(struct ondisk_cache_entry *ondisk,\n> +\tunsigned long *ent_size,\n> +\tstruct strbuf *previous_name,\n> +\tint use_length);\n> +\n> +int cmd_main(int ac, const char **av)\n> +{\n> +#ifndef NO_PTHREADS\n> +\tconst char *path;\n> +\tint fd, i;\n> +\tstruct stat st;\n> +\tvoid *mmap;\n> +\tsize_t mmap_size;\n> +\tstruct cache_header *hdr;\n> +\tstruct index_entry_offset_table *ieot;\n> +\tstruct strbuf previous_name_buf = STRBUF_INIT, *previous_name;\n> +\n> +\tsetup_git_directory();\n> +\tpath = get_index_file();\n> +\tfd = open(path, O_RDONLY);\n> +\tif (fd < 0) {\n> +\t\tdie_errno(\"%s: index file open failed\", path);\n> +\t}\n> +\n> +\tif (fstat(fd, &st))\n> +\t\tdie_errno(\"cannot stat the open index\");\n> +\n> +\tmmap_size = xsize_t(st.st_size);\n> +\tif (mmap_size < sizeof(struct cache_header) + 20)\n> +\t\tdie_errno(\"index file smaller than expected\");\n> +\n> +\tmmap = xmmap(NULL, mmap_size, PROT_READ, MAP_PRIVATE, fd, 0);\n> +\tif (mmap == MAP_FAILED)\n> +\t\tdie_errno(\"unable to map index file\");\n> +\tclose(fd);\n> +\n> +\thdr = mmap;\n> +\tif (ntohl(hdr->hdr_version) == 4)\n> +\t\tprevious_name = &previous_name_buf;\n> +\telse\n> +\t\tprevious_name = NULL;\n> +\n> +\tieot = read_ieot_extension(mmap, mmap_size);\n> +\tif (!ieot)\n> +\t\tdie_errno(\"missing or invalid extension\");\n> +\n> +\tprintf(\"IEOT with %d entries\\n\", ieot->nr);\n> +\tprintf(\"  Offset    Count Name\\n\");\n> +\tprintf(\"-------- -------- ------------------------\\n\");\n> +\tfor (i = 0; i < ieot->nr; i++) {\n> +\t\tstruct ondisk_cache_entry *disk_ce;\n> +\t\tstruct cache_entry *ce;\n> +\t\tunsigned long consumed;\n> +\n> +\t\tdisk_ce = (struct ondisk_cache_entry *)((char *)mmap + ieot->entries[i].offset);\n> +\t\tce = create_from_disk(disk_ce, &consumed, previous_name, 0);\n> +\t\t/*\n> +\t\t * If we have a V4 index, set the first byte to an invalid\n> +\t\t * character to ensure there is nothing common with the previous\n> +\t\t * entry\n> +\t\t */\n> +\t\tif (previous_name)\n> +\t\t\tprevious_name->buf[0] = 0;\n> +\t\tprintf(\"%8d %8d %.*s\\n\", ieot->entries[i].offset, ieot->entries[i].nr, ce->ce_namelen, ce->name);\n> +\t\tfree(ce);\n> +\t}\n> +\n> +\tfree(ieot);\n> +\tmunmap(mmap, mmap_size);\n> +\treturn 0;\n> +#else\n> +\tdie_errno(\"ieot only supported with PTHREADS\");\n> +\treturn -1;\n> +#endif\n> +}\n> diff --git a/t/helper/test-ieot.c b/t/helper/test-ieot.c\n> new file mode 100644\n> index 0000000000..75f28db001\n> --- /dev/null\n> +++ b/t/helper/test-ieot.c\n> @@ -0,0 +1,72 @@\n> +#include \"cache.h\"\n> +\n> +int compare_ce(const struct cache_entry *ce1, const struct cache_entry *ce2)\n> +{\n> +//\tstruct hashmap_entry ent;\n> +//\tstruct stat_data ce_stat_data;\n> +\n> +\tif (ce1->ce_mode != ce2->ce_mode) {\n> +\t\tprintf(\"ce_mode: %d:%d\\n\", ce1->ce_mode, ce2->ce_mode);\n> +\t\treturn 1;\n> +\t}\n> +\n> +\tif (ce1->ce_flags != ce2->ce_flags) {\n> +\t\tprintf(\"ce_flags: %d:%d\\n\", ce1->ce_flags, ce2->ce_flags);\n> +\t\treturn 1;\n> +\t}\n> +\n> +//\tunsigned int ce_namelen;\n> +\n> +\tif (ce1->index != ce2->index) {\n> +\t\tprintf(\"index: %d:%d\\n\", ce1->index, ce2->index);\n> +\t\treturn 1;\n> +\t}\n> +\n> +\tif (oidcmp(&ce1->oid, &ce2->oid)) {\n> +\t\tprintf(\"oid: %s:%s\\n\", oid_to_hex(&ce1->oid), oid_to_hex(&ce2->oid));\n> +\t\treturn 1;\n> +\t}\n> +\n> +\treturn 0;\n> +}\n> +\n> +extern int ignore_fast_index_config;\n> +\n> +int cmd_main(int ac, const char **av)\n> +{\n> +#ifndef NO_PTHREADS\n> +\tstatic struct index_state index;\n> +\tstatic struct index_state ieot;\n> +\tint i;\n> +\n> +\tsetup_git_directory();\n> +\tignore_fast_index_config = 1;\n> +\tcore_fast_index = 0;\n> +\tread_index(&index);\n> +\tcore_fast_index = 1;\n> +\tread_index(&ieot);\n> +\n> +\tfor (i = 0; i < index.cache_nr; i++) {\n> +\t\tif (compare_ce(index.cache[i], ieot.cache[i])) {\n> +\t\t\tstruct cache_entry *ce;\n> +\n> +\t\t\tce = index.cache[i];\n> +\t\t\tprintf(\"%06o %s %d\\t%s\\n\", ce->ce_mode,\n> +\t\t\t\toid_to_hex(&ce->oid), ce_stage(ce), ce->name);\n> +\t\t\tce = ieot.cache[i];\n> +\t\t\tprintf(\"%06o %s %d\\t%s\\n\", ce->ce_mode,\n> +\t\t\t\toid_to_hex(&ce->oid), ce_stage(ce), ce->name);\n> +\n> +\t\t\tdie_errno(\"cache entry %d does not match\", i);\n> +\t\t}\n> +\t}\n> +\n> +\tdiscard_index(&ieot);\n> +\tdiscard_index(&index);\n> +\tprintf(\"Cache entires are the same\\n\");\n> +\treturn 0;\n> +#else\n> +\tdie_errno(\"ieot only supported with PTHREADS\");\n> +\treturn -1;\n> +#endif\n> +}\n> \n> base-commit: dbc8d81072630bc50324938b9ac950140669ced9\n> \n"}]}