{"thread":{"id":"20632","subject":"[PATCH 6/6 (v4)] support for path name caching in rev-cache","startedAt":"2009-08-17T12:31:34Z","lastAt":"2009-10-19T20:31:12Z","messageCount":13,"participants":["Nick Edelen","Nicolas Pitre","Johannes Schindelin"],"isPatch":true,"patchVersion":4,"patchTotal":6},"messages":[{"id":"120876","messageId":"op.uys3qwlmtdk399@sirnot.private","threadId":"20632","inReplyTo":null,"subject":"[PATCH 6/6 (v4)] support for path name caching in rev-cache","fromName":"Nick Edelen","fromEmail":"sirnot@gmail.com","sentAt":"2009-08-17T12:31:34Z","receivedAt":"2009-08-17T12:31:34Z","isPatch":true,"sender":{"key":"sirnot@gmail.com","avatar":null},"body":"An update to caching mechanism, allowing path names to be cached for blob and \ntree objects.  A list of names appearing in each cache slice is appended to the \nend of the slice, which is referenced by variable-sized indexes per entry.  \nThis allows pack-objects to more intelligently schedule unpacked/poorly packed \nobject, and enables proper duplication of rev-list's behaivor.\n\nSigned-off-by: Nick Edelen <sirnot@gmail.com>\n\n---\n builtin-rev-cache.c       |    3 +-\n rev-cache.c               |  314 +++++++++++++++++++++++++++++++++++++--------\n rev-cache.h               |   16 ++-\n revision.h                |    6 +-\n t/t6015-rev-cache-list.sh |    4 +-\n 5 files changed, 282 insertions(+), 61 deletions(-)\n\ndiff --git a/builtin-rev-cache.c b/builtin-rev-cache.c\nindex a3489ce..5ea5c6b 100644\n--- a/builtin-rev-cache.c\n+++ b/builtin-rev-cache.c\n@@ -177,13 +177,14 @@ static int handle_walk(int argc, const char *argv[])\n \tfprintf(stderr, \"pending:\\n\");\n \tfor (i = 0; i < revs.pending.nr; i++) {\n \t\tstruct object *obj = revs.pending.objects[i].item;\n+\t\tconst char *name = revs.pending.objects[i].name;\n \n \t\t/* unfortunately, despite our careful generation, object duplication *is* a possibility...\n \t\t * (eg. same object introduced into two different branches) */\n \t\tif (obj->flags & SEEN)\n \t\t\tcontinue;\n \n-\t\tprintf(\"%s\\n\", sha1_to_hex(revs.pending.objects[i].item->sha1));\n+\t\tprintf(\"%s %s\\n\", sha1_to_hex(revs.pending.objects[i].item->sha1), name);\n \t\tobj->flags |= SEEN;\n \t}\n \ndiff --git a/rev-cache.c b/rev-cache.c\nindex 7eefd3c..1db5578 100644\n--- a/rev-cache.c\n+++ b/rev-cache.c\n@@ -17,6 +17,14 @@ struct bad_slice {\n \tstruct bad_slice *next;\n };\n \n+struct name_list {\n+\tunsigned char sha1[20];\n+\tunsigned int len;\n+\tstruct name_list *next;\n+\n+\tchar buf[FLEX_ARRAY];\n+};\n+\n struct cache_slice_pointer {\n \tchar signature[8]; /* REVCOPTR */\n \tchar version;\n@@ -29,10 +37,13 @@ static uint32_t fanout[0xff + 2];\n static unsigned char *idx_map;\n static int idx_size;\n static struct rc_index_header idx_head;\n-static char no_idx, add_to_pending;\n-static struct bad_slice *bad_slices;\n+static char no_idx, add_to_pending, add_names;\n static unsigned char *idx_caches;\n \n+static struct bad_slice *bad_slices;\n+static struct name_list *name_lists, *cur_name_list;\n+\n+static struct strbuf *acc_name_buffer;\n static struct strbuf *acc_buffer;\n \n #define SLOP\t\t\t5\n@@ -78,7 +89,7 @@ struct rc_object_entry *from_disked_rc_object_entry(struct rc_object_entry_ondis\n \tif (!dst)\n \t\tdst = &entry[cur++ & 0x3];\n \n-\tdst->type = src->flags >> 5;\n+\tdst->type = src->flags >> 5 & 0x03;\n \tdst->is_end = !!(src->flags & 0x10);\n \tdst->is_start = !!(src->flags & 0x08);\n \tdst->uninteresting = !!(src->flags & 0x04);\n@@ -89,8 +100,9 @@ struct rc_object_entry *from_disked_rc_object_entry(struct rc_object_entry_ondis\n \tdst->merge_nr = src->merge_nr;\n \tdst->split_nr = src->split_nr;\n \n-\tdst->size_size = src->sizes >> 5;\n-\tdst->padding = src->sizes & 0x1f;\n+\tdst->size_size = src->sizes >> 5 & 0x03;\n+\tdst->name_size = src->sizes >> 2 & 0x03;\n+\tdst->padding = src->sizes & 0x02;\n \n \tdst->date = ntohl(src->date);\n \tdst->path = ntohs(src->path);\n@@ -118,6 +130,7 @@ struct rc_object_entry_ondisk *to_disked_rc_object_entry(struct rc_object_entry\n \tdst->split_nr = src->split_nr;\n \n \tdst->sizes  = (unsigned char)src->size_size << 5;\n+\tdst->sizes |= (unsigned char)src->name_size << 2;\n \tdst->sizes |= (unsigned char)src->padding;\n \n \tdst->date = htonl(src->date);\n@@ -190,6 +203,12 @@ static void cleanup_cache_slices(void)\n \t\tidx_map = 0;\n \t}\n \n+\twhile (name_lists) {\n+\t\tstruct name_list *nl = name_lists->next;\n+\t\tfree(name_lists);\n+\t\tname_lists = nl;\n+\t}\n+\n }\n \n static int init_index(void)\n@@ -322,7 +341,7 @@ static void handle_noncommit(struct rev_info *revs, struct commit *commit, unsig\n \tstruct blob *blob;\n \tstruct tree *tree;\n \tstruct object *obj;\n-\tunsigned long size;\n+\tunsigned long size, name_index;\n \n \tsize = decode_size(ptr + RC_ENTRY_SIZE_OFFSET(entry), entry->size_size);\n \tswitch (entry->type) {\n@@ -355,9 +374,22 @@ static void handle_noncommit(struct rev_info *revs, struct commit *commit, unsig\n \t\treturn;\n \t}\n \n+\tif (add_names && cur_name_list) {\n+\t\tname_index = decode_size(ptr + RC_ENTRY_NAME_OFFSET(entry), entry->name_size);\n+\n+\t\tif (name_index >= cur_name_list->len)\n+\t\t\tname_index = 0;\n+\t} else name_index = 0;\n+\n \tobj->flags |= FACE_VALUE;\n-\tif (add_to_pending)\n-\t\tadd_pending_object(revs, obj, \"\");\n+\tif (add_to_pending) {\n+\t\tchar *name = \"\";\n+\n+\t\tif (name_index)\n+\t\t\tname = cur_name_list->buf + name_index;\n+\n+\t\tadd_pending_object(revs, obj, name);\n+\t}\n }\n \n static int setup_traversal(struct rc_slice_header *head, unsigned char *map, struct commit *commit, struct commit_list **work,\n@@ -712,15 +744,44 @@ end:\n \treturn retval;\n }\n \n-static int get_cache_slice_header(unsigned char *cache_sha1, unsigned char *map, int len, struct rc_slice_header *head)\n+static struct name_list *get_cache_slice_name_list(struct rc_slice_header *head, int fd)\n+{\n+\tstruct name_list *nl = name_lists;\n+\n+\twhile (nl) {\n+\t\tif (!hashcmp(nl->sha1, head->sha1))\n+\t\t\tbreak;\n+\t\tnl = nl->next;\n+\t}\n+\n+\tif (nl)\n+\t\treturn nl;\n+\n+\tnl = xcalloc(1, sizeof(struct name_list) + head->name_size);\n+\tnl->len = head->name_size;\n+\thashcpy(nl->sha1, head->sha1);\n+\n+\tlseek(fd, head->size, SEEK_SET);\n+\tread_in_full(fd, nl->buf, head->name_size);\n+\n+\tnl->next = name_lists;\n+\tname_lists = nl;\n+\n+\treturn nl;\n+}\n+\n+static int get_cache_slice_header(int fd, unsigned char *cache_sha1, int len, struct rc_slice_header *head)\n {\n \tint t;\n \n-\tmemcpy(head, map, sizeof(struct rc_slice_header));\n+\tif (xread(fd, head, sizeof(struct rc_slice_header)) != sizeof(struct rc_slice_header))\n+\t\treturn -1;\n+\n \thead->ofs_objects = ntohl(head->ofs_objects);\n \thead->object_nr = ntohl(head->object_nr);\n \thead->size = ntohl(head->size);\n \thead->path_nr = ntohs(head->path_nr);\n+\thead->name_size = ntohl(head->name_size);\n \n \tif (memcmp(head->signature, \"REVCACHE\", 8))\n \t\treturn -1;\n@@ -729,10 +790,10 @@ static int get_cache_slice_header(unsigned char *cache_sha1, unsigned char *map,\n \tif (hashcmp(head->sha1, cache_sha1))\n \t\treturn -3;\n \tt = sizeof(struct rc_slice_header);\n-\tif (t != head->ofs_objects || t >= len)\n+\tif (t != head->ofs_objects)\n \t\treturn -4;\n-\n-\thead->size = len;\n+\tif (head->size + head->name_size != len)\n+\t\treturn -5;\n \n \treturn 0;\n }\n@@ -784,7 +845,7 @@ int traverse_cache_slice(struct rev_info *revs,\n \tunsigned long *date_so_far, int *slop_so_far,\n \tstruct commit_list ***queue, struct commit_list **work)\n {\n-\tint fd = -1, retval = -3;\n+\tint fd = -1, t, retval;\n \tstruct stat fi;\n \tstruct rc_slice_header head;\n \tstruct rev_cache_info *rci;\n@@ -800,26 +861,31 @@ int traverse_cache_slice(struct rev_info *revs,\n \t/* load options */\n \trci = &revs->rev_cache_info;\n \tadd_to_pending = rci->add_to_pending;\n+\tadd_names = rci->add_names;\n \n \tmemset(&head, 0, sizeof(struct rc_slice_header));\n+#\tdefine ERROR(x)\t\tdo { retval = (x); goto end; } while (0);\n \n \tfd = open_cache_slice(cache_sha1, O_RDONLY);\n \tif (fd == -1)\n-\t\tgoto end;\n+\t\tERROR(-1);\n \tif (fstat(fd, &fi) || fi.st_size < sizeof(struct rc_slice_header))\n-\t\tgoto end;\n+\t\tERROR(-2);\n+\n+\tif ((t = get_cache_slice_header(fd, cache_sha1, fi.st_size, &head)) < 0)\n+\t\tERROR(-t);\n+\tif (add_names)\n+\t\tcur_name_list = get_cache_slice_name_list(&head, fd);\n \n-\tmap = xmmap(0, fi.st_size, PROT_READ, MAP_PRIVATE, fd, 0);\n+\tmap = xmmap(0, head.size, PROT_READ, MAP_PRIVATE, fd, 0);\n \tif (map == MAP_FAILED)\n-\t\tgoto end;\n-\tif (get_cache_slice_header(cache_sha1, map, fi.st_size, &head))\n-\t\tgoto end;\n+\t\tERROR(-3);\n \n \tretval = traverse_cache_slice_1(&head, map, revs, commit, date_so_far, slop_so_far, queue, work);\n \n end:\n \tif (map != MAP_FAILED)\n-\t\tmunmap(map, fi.st_size);\n+\t\tmunmap(map, head.size);\n \tif (fd != -1)\n \t\tclose(fd);\n \n@@ -827,6 +893,7 @@ end:\n \tif (retval)\n \t\tmark_bad_slice(cache_sha1);\n \n+#\tundef ERROR\n \treturn retval;\n }\n \n@@ -1111,23 +1178,110 @@ static unsigned long decode_size(unsigned char *str, int len)\n \treturn size;\n }\n \n+\n+#define NL_HASH_TABLE_SIZE\t\t(0xffff + 1)\n+#define NL_HASH_NUMBER\t\t\t(NL_HASH_TABLE_SIZE >> 3)\n+\n+struct name_list_hash {\n+\tint ind;\n+\tstruct name_list_hash *next;\n+};\n+\n+static struct name_list_hash **nl_hash_table;\n+static unsigned char *nl_hashes;\n+\n+/* FNV-1a hash */\n+static unsigned int hash_name(const char *name)\n+{\n+\tunsigned int hash = 2166136261ul;\n+\tconst char *p = name;\n+\n+\twhile (*p) {\n+\t\thash ^= *p++;\n+\t\thash *= 16777619ul;\n+\t}\n+\n+\treturn hash & 0xffff;\n+}\n+\n+static int name_in_list(const char *name)\n+{\n+\tunsigned int h = hash_name(name);\n+\tstruct name_list_hash *entry = nl_hash_table[h];\n+\n+\twhile (entry && strcmp(acc_name_buffer->buf + entry->ind, name))\n+\t\tentry = entry->next;\n+\n+\tif (entry)\n+\t\treturn entry->ind;\n+\n+\t/* add name to buffer and create hash reference */\n+\tentry = xcalloc(1, sizeof(struct name_list_hash));\n+\tentry->ind = acc_name_buffer->len;\n+\tstrbuf_add(acc_name_buffer, name, strlen(name) + 1);\n+\n+\tentry->next = nl_hash_table[h];\n+\tnl_hash_table[h] = entry;\n+\n+\tnl_hashes[h / 8] |= h % 8;\n+\n+\treturn entry->ind;\n+}\n+\n+static void init_name_list_hash(void)\n+{\n+\tnl_hash_table = xcalloc(NL_HASH_TABLE_SIZE, sizeof(struct name_list_hash));\n+\tnl_hashes = xcalloc(NL_HASH_NUMBER, 1);\n+}\n+\n+static void cleanup_name_list_hash(void)\n+{\n+\tint i;\n+\n+\tfor (i = 0; i < NL_HASH_NUMBER; i++) {\n+\t\tint j, ind = nl_hashes[i];\n+\n+\t\tif (!ind)\n+\t\t\tcontinue;\n+\n+\t\tfor (j = 0; j < 8; j++) {\n+\t\t\tstruct name_list_hash **entryp;\n+\n+\t\t\tif (!(ind & 1 << j))\n+\t\t\t\tcontinue;\n+\n+\t\t\tentryp = &nl_hash_table[i * 8 + j];\n+\t\t\twhile (*entryp) {\n+\t\t\t\tstruct name_list_hash *t = (*entryp)->next;\n+\n+\t\t\t\tfree(*entryp);\n+\t\t\t\t*entryp = t;\n+\t\t\t}\n+\t\t}\n+\t} /* code overhang! */\n+\n+\tfree(nl_hashes);\n+\tfree(nl_hash_table);\n+}\n+\n static void add_object_entry(const unsigned char *sha1, struct rc_object_entry *entryp,\n-\tstruct strbuf *merge_str, struct strbuf *split_str)\n+\tstruct strbuf *merge_str, struct strbuf *split_str, char *name, unsigned long size)\n {\n \tstruct rc_object_entry entry;\n-\tunsigned char size_str[7];\n-\tunsigned long size;\n+\tunsigned char size_str[7], name_str[7];\n \tenum object_type type;\n \tvoid *data;\n \n \tif (entryp)\n \t\tsha1 = entryp->sha1;\n \n-\t/* retrieve size data */\n-\tdata = read_sha1_file(sha1, &type, &size);\n+\tif (!size) {\n+\t\t/* retrieve size data */\n+\t\tdata = read_sha1_file(sha1, &type, &size);\n \n-\tif (data)\n-\t\tfree(data);\n+\t\tif (data)\n+\t\t\tfree(data);\n+\t}\n \n \t/* initialize! */\n \tif (!entryp) {\n@@ -1145,6 +1299,9 @@ static void add_object_entry(const unsigned char *sha1, struct rc_object_entry *\n \n \tentryp->size_size = encode_size(size, size_str);\n \n+\tif (name)\n+\t\tentryp->name_size = encode_size(name_in_list(name), name_str);\n+\n \t/* write the muvabitch */\n \tstrbuf_add(acc_buffer, to_disked_rc_object_entry(entryp, 0), sizeof(struct rc_object_entry_ondisk));\n \n@@ -1154,6 +1311,9 @@ static void add_object_entry(const unsigned char *sha1, struct rc_object_entry *\n \t\tstrbuf_add(acc_buffer, split_str->buf, split_str->len);\n \n \tstrbuf_add(acc_buffer, size_str, entryp->size_size);\n+\n+\tif (name)\n+\t\tstrbuf_add(acc_buffer, name_str, entryp->name_size);\n }\n \n /* returns non-zero to continue parsing, 0 to skip */\n@@ -1198,6 +1358,9 @@ continue_loop:\n static int dump_tree_callback(const unsigned char *sha1, const char *path, unsigned int mode)\n {\n \tstrbuf_add(acc_buffer, sha1, 20);\n+\tstrbuf_add(acc_buffer, (char *)&acc_name_buffer->len, sizeof(size_t));\n+\n+\tstrbuf_add(acc_name_buffer, path, strlen(path) + 1);\n \n \treturn 1;\n }\n@@ -1211,6 +1374,9 @@ static void tree_addremove(struct diff_options *options,\n \t\treturn;\n \n \tstrbuf_add(acc_buffer, sha1, 20);\n+\tstrbuf_add(acc_buffer, (char *)&acc_name_buffer->len, sizeof(size_t));\n+\n+\tstrbuf_add(acc_name_buffer, concatpath, strlen(concatpath) + 1);\n }\n \n static void tree_change(struct diff_options *options,\n@@ -1223,12 +1389,15 @@ static void tree_change(struct diff_options *options,\n \t\treturn;\n \n \tstrbuf_add(acc_buffer, new_sha1, 20);\n+\tstrbuf_add(acc_buffer, (char *)&acc_name_buffer->len, sizeof(size_t));\n+\n+\tstrbuf_add(acc_name_buffer, concatpath, strlen(concatpath) + 1);\n }\n \n static int add_unique_objects(struct commit *commit)\n {\n \tstruct commit_list *list;\n-\tstruct strbuf os, ost, *orig_buf;\n+\tstruct strbuf os, ost, names, *orig_name_buf, *orig_buf;\n \tstruct diff_options opts;\n \tint i, j, next;\n \tchar is_first = 1;\n@@ -1236,13 +1405,17 @@ static int add_unique_objects(struct commit *commit)\n \t/* ...no, calculate unique objects */\n \tstrbuf_init(&os, 0);\n \tstrbuf_init(&ost, 0);\n+\tstrbuf_init(&names, 0);\n \torig_buf = acc_buffer;\n+\torig_name_buf = acc_name_buffer;\n+\tacc_name_buffer = &names;\n \n \tdiff_setup(&opts);\n \tDIFF_OPT_SET(&opts, RECURSIVE);\n \tDIFF_OPT_SET(&opts, TREE_IN_RECURSIVE);\n \topts.change = tree_change;\n \topts.add_remove = tree_addremove;\n+#\tdefine ENTRY_SIZE (20 + sizeof(size_t))\n \n \t/* this is only called for non-ends (ie. all parents interesting) */\n \tfor (list = commit->parents; list; list = list->next) {\n@@ -1253,20 +1426,20 @@ static int add_unique_objects(struct commit *commit)\n \n \t\tstrbuf_setlen(acc_buffer, 0);\n \t\tdiff_tree_sha1(list->item->tree->object.sha1, commit->tree->object.sha1, \"\", &opts);\n-\t\tqsort(acc_buffer->buf, acc_buffer->len / 20, 20, (int (*)(const void *, const void *))hashcmp);\n+\t\tqsort(acc_buffer->buf, acc_buffer->len / ENTRY_SIZE, ENTRY_SIZE, (int (*)(const void *, const void *))hashcmp);\n \n \t\t/* take intersection */\n \t\tif (!is_first) {\n-\t\t\tfor (next = i = j = 0; i < os.len; i += 20) {\n+\t\t\tfor (next = i = j = 0; i < os.len; i += ENTRY_SIZE) {\n \t\t\t\twhile (j < ost.len && hashcmp((unsigned char *)(ost.buf + j), (unsigned char *)(os.buf + i)) < 0)\n-\t\t\t\t\tj += 20;\n+\t\t\t\t\tj += ENTRY_SIZE;\n \n \t\t\t\tif (j >= ost.len || hashcmp((unsigned char *)(ost.buf + j), (unsigned char *)(os.buf + i)))\n \t\t\t\t\tcontinue;\n \n \t\t\t\tif (next != i)\n-\t\t\t\t\tmemcpy(os.buf + next, os.buf + i, 20);\n-\t\t\t\tnext += 20;\n+\t\t\t\t\tmemcpy(os.buf + next, os.buf + i, ENTRY_SIZE);\n+\t\t\t\tnext += ENTRY_SIZE;\n \t\t\t}\n \n \t\t\tif (next != i)\n@@ -1283,26 +1456,34 @@ static int add_unique_objects(struct commit *commit)\n \n \t/* the ordering of non-commit objects dosn't really matter, so we're not gonna bother */\n \tacc_buffer = orig_buf;\n-\tfor (i = 0; i < os.len; i += 20)\n-\t\tadd_object_entry((unsigned char *)(os.buf + i), 0, 0, 0);\n+\tacc_name_buffer = orig_name_buf;\n+\tfor (i = 0; i < os.len; i += ENTRY_SIZE)\n+\t\tadd_object_entry((unsigned char *)(os.buf + i), 0, 0, 0, names.buf + *(size_t *)(os.buf + i + 20), 0);\n \n \t/* last but not least, the main tree */\n-\tadd_object_entry(commit->tree->object.sha1, 0, 0, 0);\n+\tadd_object_entry(commit->tree->object.sha1, 0, 0, 0, 0, 0);\n+\n+\tstrbuf_release(&ost);\n+\tstrbuf_release(&os);\n+\tstrbuf_release(&names);\n \n-\treturn i / 20 + 1;\n+\treturn i / ENTRY_SIZE + 1;\n+#\tundef ENTRY_SIZE\n }\n \n static int add_objects_verbatim_1(struct rev_cache_slice_map *mapping, int *index)\n {\n-\tunsigned char *map = mapping->map;\n \tint i = *index, object_nr = 0;\n+\tunsigned char *map = mapping->map;\n \tstruct rc_object_entry *entry = RC_OBTAIN_OBJECT_ENTRY(map + i);\n+\tunsigned long size;\n \n \ti += RC_ACTUAL_OBJECT_ENTRY_SIZE(entry);\n \twhile (i < mapping->size) {\n-\t\tint pos = i;\n+\t\tchar *name;\n+\t\tint name_index, pos = i;\n \n-\t\tentry = RC_OBTAIN_OBJECT_ENTRY(map + i;\n+\t\tentry = RC_OBTAIN_OBJECT_ENTRY(map + i);\n \t\ti += RC_ACTUAL_OBJECT_ENTRY_SIZE(entry);\n \n \t\tif (entry->type == OBJ_COMMIT) {\n@@ -1310,7 +1491,15 @@ static int add_objects_verbatim_1(struct rev_cache_slice_map *mapping, int *inde\n \t\t\treturn object_nr;\n \t\t}\n \n-\t\tstrbuf_add(acc_buffer, map + pos, i - pos);\n+\t\tname_index = decode_size(map + pos + RC_ENTRY_NAME_OFFSET(entry), entry->name_size);\n+\t\tif (name_index && name_index < mapping->name_size)\n+\t\t\tname = mapping->names + name_index;\n+\t\telse\n+\t\t\tname = 0;\n+\n+\t\tsize = decode_size(map + pos + RC_ENTRY_SIZE_OFFSET(entry), entry->size_size);\n+\n+\t\tadd_object_entry(0, entry, 0, 0, name, size);\n \t\tobject_nr++;\n \t}\n \n@@ -1395,6 +1584,7 @@ void init_rev_cache_info(struct rev_cache_info *rci)\n \trci->overwrite_all = 0;\n \n \trci->add_to_pending = 1;\n+\trci->add_names = 1;\n \n \trci->ignore_size = 0;\n }\n@@ -1419,9 +1609,9 @@ int make_cache_slice(struct rev_cache_info *rci,\n \tstruct rc_slice_header head;\n \tstruct commit *commit;\n \tunsigned char sha1[20];\n-\tstruct strbuf merge_paths, split_paths;\n+\tstruct strbuf merge_paths, split_paths, namelist;\n \tint object_nr, total_sz, fd;\n-\tchar file[PATH_MAX], *newfile;\n+\tchar file[PATH_MAX], null, *newfile;\n \tstruct rev_cache_info *trci;\n \tgit_SHA_CTX ctx;\n \n@@ -1436,7 +1626,13 @@ int make_cache_slice(struct rev_cache_info *rci,\n \tstrbuf_init(&endlist, 0);\n \tstrbuf_init(&merge_paths, 0);\n \tstrbuf_init(&split_paths, 0);\n+\tstrbuf_init(&namelist, 0);\n \tacc_buffer = &buffer;\n+\tacc_name_buffer = &namelist;\n+\n+\tnull = 0;\n+\tstrbuf_add(&namelist, &null, 1);\n+\tinit_name_list_hash();\n \n \tif (!revs) {\n \t\trevs = &therevs;\n@@ -1467,6 +1663,7 @@ int make_cache_slice(struct rev_cache_info *rci,\n \ttrci = &revs->rev_cache_info;\n \tinit_rev_cache_info(trci);\n \ttrci->add_to_pending = 0;\n+\ttrci->add_names = 0;\n \n \tsetup_revisions(0, 0, revs, 0);\n \tif (prepare_revision_walk(revs))\n@@ -1504,7 +1701,7 @@ int make_cache_slice(struct rev_cache_info *rci,\n \n \t\tcommit->indegree = 0;\n \n-\t\tadd_object_entry(0, &object, &merge_paths, &split_paths);\n+\t\tadd_object_entry(0, &object, &merge_paths, &split_paths, 0, 0);\n \t\tobject_nr++;\n \n \t\tif (rci->objects && !object.is_end) {\n@@ -1530,10 +1727,16 @@ int make_cache_slice(struct rev_cache_info *rci,\n \t\ttotal_sz += buffer.len;\n \t}\n \n+\t/* write path name lookup list */\n+\thead.name_size = htonl(namelist.len);\n+\twrite_in_full(fd, namelist.buf, namelist.len);\n+\n \t/* go ahead a free some stuff... */\n \tstrbuf_release(&buffer);\n \tstrbuf_release(&merge_paths);\n \tstrbuf_release(&split_paths);\n+\tstrbuf_release(&namelist);\n+\tcleanup_name_list_hash();\n \tif (path_sz)\n \t\tfree(paths);\n \twhile (path_track_alloc)\n@@ -1991,6 +2194,7 @@ int fuse_cache_slices(struct rev_cache_info *rci, struct rev_info *revs)\n \tfor (i = idx_head.cache_nr - 1; i >= 0; i--) {\n \t\tstruct rev_cache_slice_map *map = rci->maps + i;\n \t\tstruct stat fi;\n+\t\tstruct rc_slice_header head;\n \t\tint fd;\n \n \t\tif (!map->size)\n@@ -2003,13 +2207,20 @@ int fuse_cache_slices(struct rev_cache_info *rci, struct rev_info *revs)\n \t\t\tcontinue;\n \t\tif (fi.st_size < sizeof(struct rc_slice_header))\n \t\t\tcontinue;\n+\t\tif (get_cache_slice_header(fd, idx_caches + i * 20, fi.st_size, &head))\n+\t\t\tcontinue;\n \n-\t\tmap->map = xmmap(0, fi.st_size, PROT_READ, MAP_PRIVATE, fd, 0);\n+\t\tmap->map = xmmap(0, head.size, PROT_READ, MAP_PRIVATE, fd, 0);\n \t\tif (map->map == MAP_FAILED)\n \t\t\tcontinue;\n \n+\t\tlseek(fd, head.size, SEEK_SET);\n+\t\tmap->names = xcalloc(head.name_size, 1);\n+\t\tread_in_full(fd, map->names, head.name_size);\n+\n \t\tclose(fd);\n-\t\tmap->size = fi.st_size;\n+\t\tmap->size = head.size;\n+\t\tmap->name_size = head.name_size;\n \t}\n \n \trci->make_index = 0;\n@@ -2026,6 +2237,7 @@ int fuse_cache_slices(struct rev_cache_info *rci, struct rev_info *revs)\n \t\tif (!map->size)\n \t\t\tcontinue;\n \n+\t\tfree(map->names);\n \t\tmunmap(map->map, map->size);\n \t}\n \tfree(rci->maps);\n@@ -2047,7 +2259,6 @@ static int verify_cache_slice(const char *slice_path, unsigned char *sha1)\n {\n \tstruct rc_slice_header head;\n \tint fd, len, retval = -1;\n-\tunsigned char *map = MAP_FAILED;\n \tstruct stat fi;\n \n \tlen = strlen(slice_path);\n@@ -2062,17 +2273,12 @@ static int verify_cache_slice(const char *slice_path, unsigned char *sha1)\n \tif (fstat(fd, &fi) || fi.st_size < sizeof(head))\n \t\tgoto end;\n \n-\tmap = xmmap(0, sizeof(head), PROT_READ, MAP_PRIVATE, fd, 0);\n-\tif (map == MAP_FAILED)\n-\t\tgoto end;\n-\tif (get_cache_slice_header(sha1, map, fi.st_size, &head))\n+\tif (get_cache_slice_header(fd, sha1, fi.st_size, &head))\n \t\tgoto end;\n \n \tretval = 0;\n \n end:\n-\tif (map != MAP_FAILED)\n-\t\tmunmap(map, sizeof(head));\n \tif (fd > 0)\n \t\tclose(fd);\n \ndiff --git a/rev-cache.h b/rev-cache.h\nindex 14437d8..c88ceae 100644\n--- a/rev-cache.h\n+++ b/rev-cache.h\n@@ -10,8 +10,14 @@\n #define RC_OBTAIN_OBJECT_ENTRY(p)\t\t\tfrom_disked_rc_object_entry((struct rc_object_entry_ondisk *)(p), 0)\n #define RC_OBTAIN_INDEX_ENTRY(p)\t\t\tfrom_disked_rc_index_entry((struct rc_index_entry_ondisk *)(p), 0)\n \n-#define RC_ACTUAL_OBJECT_ENTRY_SIZE(e)\t\t(sizeof(struct rc_object_entry_ondisk) + RC_PATH_SIZE((e)->merge_nr + (e)->split_nr) + (e)->size_size)\n-#define RC_ENTRY_SIZE_OFFSET(e)\t\t\t\t(RC_ACTUAL_OBJECT_ENTRY_SIZE(e) - (e)->size_size)\n+#define RC_ACTUAL_OBJECT_ENTRY_SIZE(e)\t(\\\n+\tsizeof(struct rc_object_entry_ondisk) + \\\n+\tRC_PATH_SIZE((e)->merge_nr + (e)->split_nr) + \\\n+\t(e)->size_size + \\\n+\t(e)->name_size\\\n+)\n+#define RC_ENTRY_SIZE_OFFSET(e)\t\t\t(RC_ACTUAL_OBJECT_ENTRY_SIZE(e) - (e)->name_size - (e)->size_size)\n+#define RC_ENTRY_NAME_OFFSET(e)\t\t\t(RC_ACTUAL_OBJECT_ENTRY_SIZE(e) - (e)->name_size)\n \n /* single index maps objects to cache files */\n struct rc_index_header {\n@@ -50,6 +56,8 @@ struct rc_slice_header {\n \tuint32_t size;\n \n \tunsigned char sha1[20];\n+\n+\tuint32_t name_size;\n };\n \n struct rc_object_entry_ondisk {\n@@ -76,7 +84,8 @@ struct rc_object_entry {\n \tunsigned char merge_nr; /* : 7 */\n \tunsigned char split_nr; /* : 7 */\n \tunsigned size_size : 3;\n-\tunsigned padding : 5;\n+\tunsigned name_size : 3;\n+\tunsigned padding : 2;\n \n \tuint32_t date;\n \tuint16_t path;\n@@ -84,6 +93,7 @@ struct rc_object_entry {\n \t/* merge paths */\n \t/* split paths */\n \t/* size */\n+\t/* name id */\n };\n \n struct rc_index_entry *from_disked_rc_index_entry(struct rc_index_entry_ondisk *src, struct rc_index_entry *dst);\ndiff --git a/revision.h b/revision.h\nindex c3ec1b3..b2d5834 100644\n--- a/revision.h\n+++ b/revision.h\n@@ -23,6 +23,9 @@ struct rev_cache_slice_map {\n \tunsigned char *map;\n \tint size;\n \tint last_index;\n+\n+\tchar *names;\n+\tint name_size;\n };\n \n struct rev_cache_info {\n@@ -36,7 +39,8 @@ struct rev_cache_info {\n \tunsigned overwrite_all : 1;\n \n \t/* traversal flags */\n-\tunsigned add_to_pending : 1;\n+\tunsigned add_to_pending : 1,\n+\t\tadd_names : 1;\n \n \t/* fuse options */\n \tunsigned int ignore_size;\ndiff --git a/t/t6015-rev-cache-list.sh b/t/t6015-rev-cache-list.sh\nindex fa6df21..ff36881 100755\n--- a/t/t6015-rev-cache-list.sh\n+++ b/t/t6015-rev-cache-list.sh\n@@ -4,8 +4,8 @@ test_description='git rev-cache tests'\n . ./test-lib.sh\n \n test_cmp_sorted() {\n-\tgrep -io \"[a-f0-9]*\" $1 | sort >.tmpfile1 && \n-\tgrep -io \"[a-f0-9]*\" $2 | sort >.tmpfile2 && \n+\tsort $1 >.tmpfile1 && \n+\tsort $2 >.tmpfile2 && \n \ttest_cmp .tmpfile1 .tmpfile2\n }\n \n-- \ntg: (e2ef004..) t/revcache/names (depends on: t/revcache/docs)\n"},{"id":"121048","messageId":"alpine.LFD.2.00.0908172235360.6044@xanadu.home","threadId":"20632","inReplyTo":"op.uys3qwlmtdk399@sirnot.private","subject":"Re: [PATCH 6/6 (v4)] support for path name caching in rev-cache","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2009-08-18T03:24:09Z","receivedAt":"2009-08-18T03:24:09Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Mon, 17 Aug 2009, Nick Edelen wrote:\n\n> An update to caching mechanism, allowing path names to be cached for blob and \n> tree objects.  A list of names appearing in each cache slice is appended to the \n> end of the slice, which is referenced by variable-sized indexes per entry.  \n> This allows pack-objects to more intelligently schedule unpacked/poorly packed \n> object, and enables proper duplication of rev-list's behaivor.\n> \n> Signed-off-by: Nick Edelen <sirnot@gmail.com>\n\n[...]\n\nWell, OK.  Let's try it out for myself.\n\nI'm applying the whole series on top of current \"next\" as of now.\n\nApplying the first patch, git-am tells me: \n\n|warning: 70 lines add whitespace errors.\n\nYou might want to fix those.\n\nThen build+install.  Things still work fine so far.  I'm using git's own \ngit repository.  So let's get real:\n\n|$ git rev-cache add --all\n|fatal: Unable to create temporary file: Permission denied\n\nHmmm... why? Not good for a start.  Using strace:\n\n|$ strace git rev-cache add --all\n[...]\n|stat(\".git/rev-cache\", {st_mode=S_IFDIR|0664, st_size=4096, ...}) = 0 \n|open(\".git/rev-cache/MGhgcp\", O_RDWR|O_CREAT|O_EXCL, 0600) = -1 EACCES (Permission denied)\n|write(2, \"fatal: Unable to create temporary\"..., 58) = 58 \n|exit_group(128)                         = ?\n\nOK, so attempting .git/rev-cache/MGhgcp fails with EACCES.  Let's see:\n\n|$ ls -ld .git/rev-cache/\n|drw-rw-r-- 2 nico nico 4096 2009-08-17 22:47 .git/rev-cache/\n\nThere is no directory execute permission at all.  Indeed, looking at \nrev-cache.c line 2314, the mode passed to mkdir() is 0x666.  This should \nrather be 0777.  Which brings the question: how could this ever work for \nyou?  Are you testing your code as root?\n\n|$ chmod +x .git/rev-cache\n|$ git]$ git rev-cache add --all\n|objects: 115733\n|paths: 1535\n|62e497619dbb2f8b783c89084054864965bb00d8\n|endpoints:\n|S 1cae2b588249e8b45239faebc658c7fa45948932\n|S 4aec0d2391eb569776e332d9c15b354cd50a64c5\n|S 1ff19ffed62bb581cd8eb635fe6e65ffca7ba1d0\n|S fcd8ea7a91ad55d094a78c826083ebac149d81e5\n|S 181301656f7a1086adcc41c3661551f190635003\n|S 2898400a882bfb3c475fc2b53330912edc8a81f8\n|S 7c7f2ebdb98f4844347f68b6e64c4968fa7f38e5\n|S 1d9d1698ceb7b553f3cb1fdaa3150f0e85ab9cca\n|S 348f73cc1db2d7b1412c40eba72319855e2959ff\n|S fedc7d5458bd8e2e9589567041228a24a8d7eb4c\n|S 0f57bf3ae8f0000de83907f0a674d70a879f7753\n|S 7354ca323e31aa2d469498d06feebdcea137e93a\n|S d47e28a143f40ad31b88e6d7b9b18bae60d21b01\n|S 991ab5ed8769cd1a425b96b92772c89244bc957c\n|S 07827905813bce9cadb9db2faac5848a61c7e69f\n|S aff6ae5e2f10c4a8e399bf5aa446a58d74444aba\n|S 6849908a55d0e7a95fa715310f739cfab4dd8def\n|S ac34f56d4cf6a737f7d8cb56a9b57448f8d6e190\n|S 740f1f8651561ee3f31d11cde492eedc77272ff1\n|S 38b9118536279dd923e7d5c7444f5869b7f709b1\n|S 13354f5377d82baee4d8c930df824c8dbeda396d\n|S d82c2e2835dd1aca1a0b6b1fc9f6213ad0e0ae9c\n|final return value: 0\n\nGood, making progress.  By the way, is that output useful?  If so, is it \ndocumented somewhere?  Surely the \"final return value\" is probably not \nthat useful...\n\nNow I want to see how fast rev-list has become.\n\n|$ git rev-list --all --objects > /dev/null\n|Segmentation fault\n\nBOOM!  :-(  And now half of the git commands are just as helpful with \nsegmentation faults, including 'git log'.\n\nHere's a backtrace from gdb:\n\n|(gdb) bt\n|#0  0x0000000000493c33 in to_disked_rc_object_entry (src=0x72d6e0,\n|    dst=0x7ffff548c034) at rev-cache.c:121\n|#1  0x00000000004957f0 in setup_traversal () at rev-cache.c:412\n|#2  traverse_cache_slice_1 () at rev-cache.c:487\n|#3  traverse_cache_slice (revs=0x7fffffffe010,\n|    cache_sha1=0x7739b0 \"b\\227a\\235/\\213x<\\211\\b@T\\206Ie\",\n|    commit=<value optimized out>, date_so_far=0x0, slop_so_far=0x0,\n|    queue=0x7fffffffdef8, work=0x7fffffffe010) at rev-cache.c:884\n|#4  0x000000000049a4e7 in get_revision_1 (revs=0x7fffffffe010)\n|    at revision.c:1763\n|#5  0x000000000049a55b in get_revision_internal (revs=0x7fffffffe010)\n|    at revision.c:1886\n|#6  0x000000000049a7c1 in get_revision (revs=0x7fffffffe010) at revision.c:1967\n|#7  0x00000000004790a7 in traverse_commit_list (revs=0x7fffffffe010,\n|    show_commit=0x4477d0 <show_commit>, show_object=0x447ba0 <show_object>,\n|    data=0x7fffffffe3f0) at list-objects.c:164\n|#8  0x000000000044808c in cmd_rev_list (argc=1, argv=0x7fffffffe680,\n|    prefix=0x0) at builtin-rev-list.c:398\n|#9  0x0000000000403d13 in run_builtin () at git.c:246\n|#10 handle_internal_command (argc=3, argv=0x7fffffffe680) at git.c:391\n|#11 0x0000000000403ebd in run_argv () at git.c:433\n|#12 main (argc=3, argv=0x7fffffffe680) at git.c:504\n\n\nNicolas\n"},{"id":"121082","messageId":"c77435a80908180431k2f91e1ffye25aa8895908ddb7@mail.gmail.com","threadId":"20632","inReplyTo":"alpine.LFD.2.00.0908172235360.6044@xanadu.home","subject":"Re: [PATCH 6/6 (v4)] support for path name caching in rev-cache","fromName":"Nick Edelen","fromEmail":"sirnot@gmail.com","sentAt":"2009-08-18T11:31:49Z","receivedAt":"2009-08-18T11:31:49Z","isPatch":true,"sender":{"key":"sirnot@gmail.com","avatar":null},"body":"AARGH scheissgepoops I'm so sorry :-(\n\n> BOOM!  :-(  And now half of the git commands are just as helpful with\n> segmentation faults, including 'git log'.\n>\n> Here's a backtrace from gdb:\n\nI swear I must've been on drugs or something b/c I managed removed the\nPROT_WRITE access permission from mmap :-/  cygwin didn't seem to\nnotice either.  And there's also your explanation of my idiotic\ndirectory permissions choice.\n\nYou're also right about the command output; I've added a bit in the\ndocs explaining the output of each command.\n\nI'll reply to *these* posts with everything fixed.  Then after that\nhopefully I can just make patches for the patchset (yo dawg) and save\neveryone a lot of bandwidth.\n\n - Nick\n"},{"id":"121087","messageId":"op.uyuwkwjotdk399@sirnot.private","threadId":"20632","inReplyTo":"op.uys3qwlmtdk399@sirnot.private","subject":"Re: [PATCH 6/6 (v4)] support for path name caching in rev-cache","fromName":"Nick Edelen","fromEmail":"sirnot@gmail.com","sentAt":"2009-08-18T11:51:58Z","receivedAt":"2009-08-18T11:51:58Z","isPatch":true,"sender":{"key":"sirnot@gmail.com","avatar":null},"body":"An update to caching mechanism, allowing path names to be cached for blob and\ntree objects.  A list of names appearing in each cache slice is appended to the\nend of the slice, which is referenced by variable-sized indexes per entry.\nThis allows pack-objects to more intelligently schedule unpacked/poorly packed\nobject, and enables proper duplication of rev-list's behaivor.\n\nSigned-off-by: Nick Edelen <sirnot@gmail.com>\n\n---\n builtin-rev-cache.c       |    3 +-\n rev-cache.c               |  314 +++++++++++++++++++++++++++++++++++++--------\n rev-cache.h               |   16 ++-\n revision.h                |    6 +-\n t/t6015-rev-cache-list.sh |    6 +-\n 5 files changed, 283 insertions(+), 62 deletions(-)\n\ndiff --git a/builtin-rev-cache.c b/builtin-rev-cache.c\nindex 8f41123..4c1766d 100644\n--- a/builtin-rev-cache.c\n+++ b/builtin-rev-cache.c\n@@ -177,13 +177,14 @@ static int handle_walk(int argc, const char *argv[])\n \tfprintf(stderr, \"pending:\\n\");\n \tfor (i = 0; i < revs.pending.nr; i++) {\n \t\tstruct object *obj = revs.pending.objects[i].item;\n+\t\tconst char *name = revs.pending.objects[i].name;\n \n \t\t/* unfortunately, despite our careful generation, object duplication *is* a possibility...\n \t\t * (eg. same object introduced into two different branches) */\n \t\tif (obj->flags & SEEN)\n \t\t\tcontinue;\n \n-\t\tprintf(\"%s\\n\", sha1_to_hex(revs.pending.objects[i].item->sha1));\n+\t\tprintf(\"%s %s\\n\", sha1_to_hex(revs.pending.objects[i].item->sha1), name);\n \t\tobj->flags |= SEEN;\n \t}\n \ndiff --git a/rev-cache.c b/rev-cache.c\nindex 04a9b02..8801794 100644\n--- a/rev-cache.c\n+++ b/rev-cache.c\n@@ -17,6 +17,14 @@ struct bad_slice {\n \tstruct bad_slice *next;\n };\n \n+struct name_list {\n+\tunsigned char sha1[20];\n+\tunsigned int len;\n+\tstruct name_list *next;\n+\n+\tchar buf[FLEX_ARRAY];\n+};\n+\n struct cache_slice_pointer {\n \tchar signature[8]; /* REVCOPTR */\n \tchar version;\n@@ -29,10 +37,13 @@ static uint32_t fanout[0xff + 2];\n static unsigned char *idx_map;\n static int idx_size;\n static struct rc_index_header idx_head;\n-static char no_idx, add_to_pending;\n-static struct bad_slice *bad_slices;\n+static char no_idx, add_to_pending, add_names;\n static unsigned char *idx_caches;\n \n+static struct bad_slice *bad_slices;\n+static struct name_list *name_lists, *cur_name_list;\n+\n+static struct strbuf *acc_name_buffer;\n static struct strbuf *acc_buffer;\n \n #define SLOP\t\t\t5\n@@ -79,7 +90,7 @@ struct rc_object_entry *from_disked_rc_object_entry(struct rc_object_entry_ondis\n \tif (!dst)\n \t\tdst = &entry[cur++ & 0x3];\n \n-\tdst->type = src->flags >> 5;\n+\tdst->type = src->flags >> 5 & 0x03;\n \tdst->is_end = !!(src->flags & 0x10);\n \tdst->is_start = !!(src->flags & 0x08);\n \tdst->uninteresting = !!(src->flags & 0x04);\n@@ -90,8 +101,9 @@ struct rc_object_entry *from_disked_rc_object_entry(struct rc_object_entry_ondis\n \tdst->merge_nr = src->merge_nr;\n \tdst->split_nr = src->split_nr;\n \n-\tdst->size_size = src->sizes >> 5;\n-\tdst->padding = src->sizes & 0x1f;\n+\tdst->size_size = src->sizes >> 5 & 0x03;\n+\tdst->name_size = src->sizes >> 2 & 0x03;\n+\tdst->padding = src->sizes & 0x02;\n \n \tdst->date = ntohl(src->date);\n \tdst->path = ntohs(src->path);\n@@ -120,6 +132,7 @@ struct rc_object_entry_ondisk *to_disked_rc_object_entry(struct rc_object_entry\n \tdst->split_nr = src->split_nr;\n \n \tdst->sizes  = (unsigned char)src->size_size << 5;\n+\tdst->sizes |= (unsigned char)src->name_size << 2;\n \tdst->sizes |= (unsigned char)src->padding;\n \n \tdst->date = htonl(src->date);\n@@ -192,6 +205,12 @@ static void cleanup_cache_slices(void)\n \t\tidx_map = 0;\n \t}\n \n+\twhile (name_lists) {\n+\t\tstruct name_list *nl = name_lists->next;\n+\t\tfree(name_lists);\n+\t\tname_lists = nl;\n+\t}\n+\n }\n \n static int init_index(void)\n@@ -324,7 +343,7 @@ static void handle_noncommit(struct rev_info *revs, struct commit *commit, unsig\n \tstruct blob *blob;\n \tstruct tree *tree;\n \tstruct object *obj;\n-\tunsigned long size;\n+\tunsigned long size, name_index;\n \n \tsize = decode_size(ptr + RC_ENTRY_SIZE_OFFSET(entry), entry->size_size);\n \tswitch (entry->type) {\n@@ -357,9 +376,22 @@ static void handle_noncommit(struct rev_info *revs, struct commit *commit, unsig\n \t\treturn;\n \t}\n \n+\tif (add_names && cur_name_list) {\n+\t\tname_index = decode_size(ptr + RC_ENTRY_NAME_OFFSET(entry), entry->name_size);\n+\n+\t\tif (name_index >= cur_name_list->len)\n+\t\t\tname_index = 0;\n+\t} else name_index = 0;\n+\n \tobj->flags |= FACE_VALUE;\n-\tif (add_to_pending)\n-\t\tadd_pending_object(revs, obj, \"\");\n+\tif (add_to_pending) {\n+\t\tchar *name = \"\";\n+\n+\t\tif (name_index)\n+\t\t\tname = cur_name_list->buf + name_index;\n+\n+\t\tadd_pending_object(revs, obj, name);\n+\t}\n }\n \n static int setup_traversal(struct rc_slice_header *head, unsigned char *map, struct commit *commit, struct commit_list **work,\n@@ -714,15 +746,44 @@ end:\n \treturn retval;\n }\n \n-static int get_cache_slice_header(unsigned char *cache_sha1, unsigned char *map, int len, struct rc_slice_header *head)\n+static struct name_list *get_cache_slice_name_list(struct rc_slice_header *head, int fd)\n+{\n+\tstruct name_list *nl = name_lists;\n+\n+\twhile (nl) {\n+\t\tif (!hashcmp(nl->sha1, head->sha1))\n+\t\t\tbreak;\n+\t\tnl = nl->next;\n+\t}\n+\n+\tif (nl)\n+\t\treturn nl;\n+\n+\tnl = xcalloc(1, sizeof(struct name_list) + head->name_size);\n+\tnl->len = head->name_size;\n+\thashcpy(nl->sha1, head->sha1);\n+\n+\tlseek(fd, head->size, SEEK_SET);\n+\tread_in_full(fd, nl->buf, head->name_size);\n+\n+\tnl->next = name_lists;\n+\tname_lists = nl;\n+\n+\treturn nl;\n+}\n+\n+static int get_cache_slice_header(int fd, unsigned char *cache_sha1, int len, struct rc_slice_header *head)\n {\n \tint t;\n \n-\tmemcpy(head, map, sizeof(struct rc_slice_header));\n+\tif (xread(fd, head, sizeof(struct rc_slice_header)) != sizeof(struct rc_slice_header))\n+\t\treturn -1;\n+\n \thead->ofs_objects = ntohl(head->ofs_objects);\n \thead->object_nr = ntohl(head->object_nr);\n \thead->size = ntohl(head->size);\n \thead->path_nr = ntohs(head->path_nr);\n+\thead->name_size = ntohl(head->name_size);\n \n \tif (memcmp(head->signature, \"REVCACHE\", 8))\n \t\treturn -1;\n@@ -731,10 +792,10 @@ static int get_cache_slice_header(unsigned char *cache_sha1, unsigned char *map,\n \tif (hashcmp(head->sha1, cache_sha1))\n \t\treturn -3;\n \tt = sizeof(struct rc_slice_header);\n-\tif (t != head->ofs_objects || t >= len)\n+\tif (t != head->ofs_objects)\n \t\treturn -4;\n-\n-\thead->size = len;\n+\tif (head->size + head->name_size != len)\n+\t\treturn -5;\n \n \treturn 0;\n }\n@@ -786,7 +847,7 @@ int traverse_cache_slice(struct rev_info *revs,\n \tunsigned long *date_so_far, int *slop_so_far,\n \tstruct commit_list ***queue, struct commit_list **work)\n {\n-\tint fd = -1, retval = -3;\n+\tint fd = -1, t, retval;\n \tstruct stat fi;\n \tstruct rc_slice_header head;\n \tstruct rev_cache_info *rci;\n@@ -802,26 +863,31 @@ int traverse_cache_slice(struct rev_info *revs,\n \t/* load options */\n \trci = &revs->rev_cache_info;\n \tadd_to_pending = rci->add_to_pending;\n+\tadd_names = rci->add_names;\n \n \tmemset(&head, 0, sizeof(struct rc_slice_header));\n+#\tdefine ERROR(x)\t\tdo { retval = (x); goto end; } while (0);\n \n \tfd = open_cache_slice(cache_sha1, O_RDONLY);\n \tif (fd == -1)\n-\t\tgoto end;\n+\t\tERROR(-1);\n \tif (fstat(fd, &fi) || fi.st_size < sizeof(struct rc_slice_header))\n-\t\tgoto end;\n+\t\tERROR(-2);\n+\n+\tif ((t = get_cache_slice_header(fd, cache_sha1, fi.st_size, &head)) < 0)\n+\t\tERROR(-t);\n+\tif (add_names)\n+\t\tcur_name_list = get_cache_slice_name_list(&head, fd);\n \n-\tmap = xmmap(0, fi.st_size, PROT_READ | PROT_WRITE, MAP_PRIVATE, fd, 0);\n+\tmap = xmmap(0, head.size, PROT_READ | PROT_WRITE, MAP_PRIVATE, fd, 0);\n \tif (map == MAP_FAILED)\n-\t\tgoto end;\n-\tif (get_cache_slice_header(cache_sha1, map, fi.st_size, &head))\n-\t\tgoto end;\n+\t\tERROR(-3);\n \n \tretval = traverse_cache_slice_1(&head, map, revs, commit, date_so_far, slop_so_far, queue, work);\n \n end:\n \tif (map != MAP_FAILED)\n-\t\tmunmap(map, fi.st_size);\n+\t\tmunmap(map, head.size);\n \tif (fd != -1)\n \t\tclose(fd);\n \n@@ -829,6 +895,7 @@ end:\n \tif (retval)\n \t\tmark_bad_slice(cache_sha1);\n \n+#\tundef ERROR\n \treturn retval;\n }\n \n@@ -1113,23 +1180,110 @@ static unsigned long decode_size(unsigned char *str, int len)\n \treturn size;\n }\n \n+\n+#define NL_HASH_TABLE_SIZE\t\t(0xffff + 1)\n+#define NL_HASH_NUMBER\t\t\t(NL_HASH_TABLE_SIZE >> 3)\n+\n+struct name_list_hash {\n+\tint ind;\n+\tstruct name_list_hash *next;\n+};\n+\n+static struct name_list_hash **nl_hash_table;\n+static unsigned char *nl_hashes;\n+\n+/* FNV-1a hash */\n+static unsigned int hash_name(const char *name)\n+{\n+\tunsigned int hash = 2166136261ul;\n+\tconst char *p = name;\n+\n+\twhile (*p) {\n+\t\thash ^= *p++;\n+\t\thash *= 16777619ul;\n+\t}\n+\n+\treturn hash & 0xffff;\n+}\n+\n+static int name_in_list(const char *name)\n+{\n+\tunsigned int h = hash_name(name);\n+\tstruct name_list_hash *entry = nl_hash_table[h];\n+\n+\twhile (entry && strcmp(acc_name_buffer->buf + entry->ind, name))\n+\t\tentry = entry->next;\n+\n+\tif (entry)\n+\t\treturn entry->ind;\n+\n+\t/* add name to buffer and create hash reference */\n+\tentry = xcalloc(1, sizeof(struct name_list_hash));\n+\tentry->ind = acc_name_buffer->len;\n+\tstrbuf_add(acc_name_buffer, name, strlen(name) + 1);\n+\n+\tentry->next = nl_hash_table[h];\n+\tnl_hash_table[h] = entry;\n+\n+\tnl_hashes[h / 8] |= h % 8;\n+\n+\treturn entry->ind;\n+}\n+\n+static void init_name_list_hash(void)\n+{\n+\tnl_hash_table = xcalloc(NL_HASH_TABLE_SIZE, sizeof(struct name_list_hash));\n+\tnl_hashes = xcalloc(NL_HASH_NUMBER, 1);\n+}\n+\n+static void cleanup_name_list_hash(void)\n+{\n+\tint i;\n+\n+\tfor (i = 0; i < NL_HASH_NUMBER; i++) {\n+\t\tint j, ind = nl_hashes[i];\n+\n+\t\tif (!ind)\n+\t\t\tcontinue;\n+\n+\t\tfor (j = 0; j < 8; j++) {\n+\t\t\tstruct name_list_hash **entryp;\n+\n+\t\t\tif (!(ind & 1 << j))\n+\t\t\t\tcontinue;\n+\n+\t\t\tentryp = &nl_hash_table[i * 8 + j];\n+\t\t\twhile (*entryp) {\n+\t\t\t\tstruct name_list_hash *t = (*entryp)->next;\n+\n+\t\t\t\tfree(*entryp);\n+\t\t\t\t*entryp = t;\n+\t\t\t}\n+\t\t}\n+\t} /* code overhang! */\n+\n+\tfree(nl_hashes);\n+\tfree(nl_hash_table);\n+}\n+\n static void add_object_entry(const unsigned char *sha1, struct rc_object_entry *entryp,\n-\tstruct strbuf *merge_str, struct strbuf *split_str)\n+\tstruct strbuf *merge_str, struct strbuf *split_str, char *name, unsigned long size)\n {\n \tstruct rc_object_entry entry;\n-\tunsigned char size_str[7];\n-\tunsigned long size;\n+\tunsigned char size_str[7], name_str[7];\n \tenum object_type type;\n \tvoid *data;\n \n \tif (entryp)\n \t\tsha1 = entryp->sha1;\n \n-\t/* retrieve size data */\n-\tdata = read_sha1_file(sha1, &type, &size);\n+\tif (!size) {\n+\t\t/* retrieve size data */\n+\t\tdata = read_sha1_file(sha1, &type, &size);\n \n-\tif (data)\n-\t\tfree(data);\n+\t\tif (data)\n+\t\t\tfree(data);\n+\t}\n \n \t/* initialize! */\n \tif (!entryp) {\n@@ -1147,6 +1301,9 @@ static void add_object_entry(const unsigned char *sha1, struct rc_object_entry *\n \n \tentryp->size_size = encode_size(size, size_str);\n \n+\tif (name)\n+\t\tentryp->name_size = encode_size(name_in_list(name), name_str);\n+\n \t/* write the muvabitch */\n \tstrbuf_add(acc_buffer, to_disked_rc_object_entry(entryp, 0), sizeof(struct rc_object_entry_ondisk));\n \n@@ -1156,6 +1313,9 @@ static void add_object_entry(const unsigned char *sha1, struct rc_object_entry *\n \t\tstrbuf_add(acc_buffer, split_str->buf, split_str->len);\n \n \tstrbuf_add(acc_buffer, size_str, entryp->size_size);\n+\n+\tif (name)\n+\t\tstrbuf_add(acc_buffer, name_str, entryp->name_size);\n }\n \n /* returns non-zero to continue parsing, 0 to skip */\n@@ -1200,6 +1360,9 @@ continue_loop:\n static int dump_tree_callback(const unsigned char *sha1, const char *path, unsigned int mode)\n {\n \tstrbuf_add(acc_buffer, sha1, 20);\n+\tstrbuf_add(acc_buffer, (char *)&acc_name_buffer->len, sizeof(size_t));\n+\n+\tstrbuf_add(acc_name_buffer, path, strlen(path) + 1);\n \n \treturn 1;\n }\n@@ -1213,6 +1376,9 @@ static void tree_addremove(struct diff_options *options,\n \t\treturn;\n \n \tstrbuf_add(acc_buffer, sha1, 20);\n+\tstrbuf_add(acc_buffer, (char *)&acc_name_buffer->len, sizeof(size_t));\n+\n+\tstrbuf_add(acc_name_buffer, concatpath, strlen(concatpath) + 1);\n }\n \n static void tree_change(struct diff_options *options,\n@@ -1225,12 +1391,15 @@ static void tree_change(struct diff_options *options,\n \t\treturn;\n \n \tstrbuf_add(acc_buffer, new_sha1, 20);\n+\tstrbuf_add(acc_buffer, (char *)&acc_name_buffer->len, sizeof(size_t));\n+\n+\tstrbuf_add(acc_name_buffer, concatpath, strlen(concatpath) + 1);\n }\n \n static int add_unique_objects(struct commit *commit)\n {\n \tstruct commit_list *list;\n-\tstruct strbuf os, ost, *orig_buf;\n+\tstruct strbuf os, ost, names, *orig_name_buf, *orig_buf;\n \tstruct diff_options opts;\n \tint i, j, next;\n \tchar is_first = 1;\n@@ -1238,13 +1407,17 @@ static int add_unique_objects(struct commit *commit)\n \t/* ...no, calculate unique objects */\n \tstrbuf_init(&os, 0);\n \tstrbuf_init(&ost, 0);\n+\tstrbuf_init(&names, 0);\n \torig_buf = acc_buffer;\n+\torig_name_buf = acc_name_buffer;\n+\tacc_name_buffer = &names;\n \n \tdiff_setup(&opts);\n \tDIFF_OPT_SET(&opts, RECURSIVE);\n \tDIFF_OPT_SET(&opts, TREE_IN_RECURSIVE);\n \topts.change = tree_change;\n \topts.add_remove = tree_addremove;\n+#\tdefine ENTRY_SIZE (20 + sizeof(size_t))\n \n \t/* this is only called for non-ends (ie. all parents interesting) */\n \tfor (list = commit->parents; list; list = list->next) {\n@@ -1255,20 +1428,20 @@ static int add_unique_objects(struct commit *commit)\n \n \t\tstrbuf_setlen(acc_buffer, 0);\n \t\tdiff_tree_sha1(list->item->tree->object.sha1, commit->tree->object.sha1, \"\", &opts);\n-\t\tqsort(acc_buffer->buf, acc_buffer->len / 20, 20, (int (*)(const void *, const void *))hashcmp);\n+\t\tqsort(acc_buffer->buf, acc_buffer->len / ENTRY_SIZE, ENTRY_SIZE, (int (*)(const void *, const void *))hashcmp);\n \n \t\t/* take intersection */\n \t\tif (!is_first) {\n-\t\t\tfor (next = i = j = 0; i < os.len; i += 20) {\n+\t\t\tfor (next = i = j = 0; i < os.len; i += ENTRY_SIZE) {\n \t\t\t\twhile (j < ost.len && hashcmp((unsigned char *)(ost.buf + j), (unsigned char *)(os.buf + i)) < 0)\n-\t\t\t\t\tj += 20;\n+\t\t\t\t\tj += ENTRY_SIZE;\n \n \t\t\t\tif (j >= ost.len || hashcmp((unsigned char *)(ost.buf + j), (unsigned char *)(os.buf + i)))\n \t\t\t\t\tcontinue;\n \n \t\t\t\tif (next != i)\n-\t\t\t\t\tmemcpy(os.buf + next, os.buf + i, 20);\n-\t\t\t\tnext += 20;\n+\t\t\t\t\tmemcpy(os.buf + next, os.buf + i, ENTRY_SIZE);\n+\t\t\t\tnext += ENTRY_SIZE;\n \t\t\t}\n \n \t\t\tif (next != i)\n@@ -1285,26 +1458,34 @@ static int add_unique_objects(struct commit *commit)\n \n \t/* the ordering of non-commit objects dosn't really matter, so we're not gonna bother */\n \tacc_buffer = orig_buf;\n-\tfor (i = 0; i < os.len; i += 20)\n-\t\tadd_object_entry((unsigned char *)(os.buf + i), 0, 0, 0);\n+\tacc_name_buffer = orig_name_buf;\n+\tfor (i = 0; i < os.len; i += ENTRY_SIZE)\n+\t\tadd_object_entry((unsigned char *)(os.buf + i), 0, 0, 0, names.buf + *(size_t *)(os.buf + i + 20), 0);\n \n \t/* last but not least, the main tree */\n-\tadd_object_entry(commit->tree->object.sha1, 0, 0, 0);\n+\tadd_object_entry(commit->tree->object.sha1, 0, 0, 0, 0, 0);\n+\n+\tstrbuf_release(&ost);\n+\tstrbuf_release(&os);\n+\tstrbuf_release(&names);\n \n-\treturn i / 20 + 1;\n+\treturn i / ENTRY_SIZE + 1;\n+#\tundef ENTRY_SIZE\n }\n \n static int add_objects_verbatim_1(struct rev_cache_slice_map *mapping, int *index)\n {\n-\tunsigned char *map = mapping->map;\n \tint i = *index, object_nr = 0;\n+\tunsigned char *map = mapping->map;\n \tstruct rc_object_entry *entry = RC_OBTAIN_OBJECT_ENTRY(map + i);\n+\tunsigned long size;\n \n \ti += RC_ACTUAL_OBJECT_ENTRY_SIZE(entry);\n \twhile (i < mapping->size) {\n-\t\tint pos = i;\n+\t\tchar *name;\n+\t\tint name_index, pos = i;\n \n-\t\tentry = RC_OBTAIN_OBJECT_ENTRY(map + i;\n+\t\tentry = RC_OBTAIN_OBJECT_ENTRY(map + i);\n \t\ti += RC_ACTUAL_OBJECT_ENTRY_SIZE(entry);\n \n \t\tif (entry->type == OBJ_COMMIT) {\n@@ -1312,7 +1493,15 @@ static int add_objects_verbatim_1(struct rev_cache_slice_map *mapping, int *inde\n \t\t\treturn object_nr;\n \t\t}\n \n-\t\tstrbuf_add(acc_buffer, map + pos, i - pos);\n+\t\tname_index = decode_size(map + pos + RC_ENTRY_NAME_OFFSET(entry), entry->name_size);\n+\t\tif (name_index && name_index < mapping->name_size)\n+\t\t\tname = mapping->names + name_index;\n+\t\telse\n+\t\t\tname = 0;\n+\n+\t\tsize = decode_size(map + pos + RC_ENTRY_SIZE_OFFSET(entry), entry->size_size);\n+\n+\t\tadd_object_entry(0, entry, 0, 0, name, size);\n \t\tobject_nr++;\n \t}\n \n@@ -1397,6 +1586,7 @@ void init_rev_cache_info(struct rev_cache_info *rci)\n \trci->overwrite_all = 0;\n \n \trci->add_to_pending = 1;\n+\trci->add_names = 1;\n \n \trci->ignore_size = 0;\n }\n@@ -1421,9 +1611,9 @@ int make_cache_slice(struct rev_cache_info *rci,\n \tstruct rc_slice_header head;\n \tstruct commit *commit;\n \tunsigned char sha1[20];\n-\tstruct strbuf merge_paths, split_paths;\n+\tstruct strbuf merge_paths, split_paths, namelist;\n \tint object_nr, total_sz, fd;\n-\tchar file[PATH_MAX], *newfile;\n+\tchar file[PATH_MAX], null, *newfile;\n \tstruct rev_cache_info *trci;\n \tgit_SHA_CTX ctx;\n \n@@ -1438,7 +1628,13 @@ int make_cache_slice(struct rev_cache_info *rci,\n \tstrbuf_init(&endlist, 0);\n \tstrbuf_init(&merge_paths, 0);\n \tstrbuf_init(&split_paths, 0);\n+\tstrbuf_init(&namelist, 0);\n \tacc_buffer = &buffer;\n+\tacc_name_buffer = &namelist;\n+\n+\tnull = 0;\n+\tstrbuf_add(&namelist, &null, 1);\n+\tinit_name_list_hash();\n \n \tif (!revs) {\n \t\trevs = &therevs;\n@@ -1469,6 +1665,7 @@ int make_cache_slice(struct rev_cache_info *rci,\n \ttrci = &revs->rev_cache_info;\n \tinit_rev_cache_info(trci);\n \ttrci->add_to_pending = 0;\n+\ttrci->add_names = 0;\n \n \tsetup_revisions(0, 0, revs, 0);\n \tif (prepare_revision_walk(revs))\n@@ -1506,7 +1703,7 @@ int make_cache_slice(struct rev_cache_info *rci,\n \n \t\tcommit->indegree = 0;\n \n-\t\tadd_object_entry(0, &object, &merge_paths, &split_paths);\n+\t\tadd_object_entry(0, &object, &merge_paths, &split_paths, 0, 0);\n \t\tobject_nr++;\n \n \t\tif (rci->objects && !object.is_end) {\n@@ -1532,10 +1729,16 @@ int make_cache_slice(struct rev_cache_info *rci,\n \t\ttotal_sz += buffer.len;\n \t}\n \n+\t/* write path name lookup list */\n+\thead.name_size = htonl(namelist.len);\n+\twrite_in_full(fd, namelist.buf, namelist.len);\n+\n \t/* go ahead a free some stuff... */\n \tstrbuf_release(&buffer);\n \tstrbuf_release(&merge_paths);\n \tstrbuf_release(&split_paths);\n+\tstrbuf_release(&namelist);\n+\tcleanup_name_list_hash();\n \tif (path_sz)\n \t\tfree(paths);\n \twhile (path_track_alloc)\n@@ -1993,6 +2196,7 @@ int fuse_cache_slices(struct rev_cache_info *rci, struct rev_info *revs)\n \tfor (i = idx_head.cache_nr - 1; i >= 0; i--) {\n \t\tstruct rev_cache_slice_map *map = rci->maps + i;\n \t\tstruct stat fi;\n+\t\tstruct rc_slice_header head;\n \t\tint fd;\n \n \t\tif (!map->size)\n@@ -2005,13 +2209,20 @@ int fuse_cache_slices(struct rev_cache_info *rci, struct rev_info *revs)\n \t\t\tcontinue;\n \t\tif (fi.st_size < sizeof(struct rc_slice_header))\n \t\t\tcontinue;\n+\t\tif (get_cache_slice_header(fd, idx_caches + i * 20, fi.st_size, &head))\n+\t\t\tcontinue;\n \n-\t\tmap->map = xmmap(0, fi.st_size, PROT_READ, MAP_PRIVATE, fd, 0);\n+\t\tmap->map = xmmap(0, head.size, PROT_READ, MAP_PRIVATE, fd, 0);\n \t\tif (map->map == MAP_FAILED)\n \t\t\tcontinue;\n \n+\t\tlseek(fd, head.size, SEEK_SET);\n+\t\tmap->names = xcalloc(head.name_size, 1);\n+\t\tread_in_full(fd, map->names, head.name_size);\n+\n \t\tclose(fd);\n-\t\tmap->size = fi.st_size;\n+\t\tmap->size = head.size;\n+\t\tmap->name_size = head.name_size;\n \t}\n \n \trci->make_index = 0;\n@@ -2028,6 +2239,7 @@ int fuse_cache_slices(struct rev_cache_info *rci, struct rev_info *revs)\n \t\tif (!map->size)\n \t\t\tcontinue;\n \n+\t\tfree(map->names);\n \t\tmunmap(map->map, map->size);\n \t}\n \tfree(rci->maps);\n@@ -2049,7 +2261,6 @@ static int verify_cache_slice(const char *slice_path, unsigned char *sha1)\n {\n \tstruct rc_slice_header head;\n \tint fd, len, retval = -1;\n-\tunsigned char *map = MAP_FAILED;\n \tstruct stat fi;\n \n \tlen = strlen(slice_path);\n@@ -2064,17 +2275,12 @@ static int verify_cache_slice(const char *slice_path, unsigned char *sha1)\n \tif (fstat(fd, &fi) || fi.st_size < sizeof(head))\n \t\tgoto end;\n \n-\tmap = xmmap(0, sizeof(head), PROT_READ, MAP_PRIVATE, fd, 0);\n-\tif (map == MAP_FAILED)\n-\t\tgoto end;\n-\tif (get_cache_slice_header(sha1, map, fi.st_size, &head))\n+\tif (get_cache_slice_header(fd, sha1, fi.st_size, &head))\n \t\tgoto end;\n \n \tretval = 0;\n \n end:\n-\tif (map != MAP_FAILED)\n-\t\tmunmap(map, sizeof(head));\n \tif (fd > 0)\n \t\tclose(fd);\n \ndiff --git a/rev-cache.h b/rev-cache.h\nindex 14437d8..c88ceae 100644\n--- a/rev-cache.h\n+++ b/rev-cache.h\n@@ -10,8 +10,14 @@\n #define RC_OBTAIN_OBJECT_ENTRY(p)\t\t\tfrom_disked_rc_object_entry((struct rc_object_entry_ondisk *)(p), 0)\n #define RC_OBTAIN_INDEX_ENTRY(p)\t\t\tfrom_disked_rc_index_entry((struct rc_index_entry_ondisk *)(p), 0)\n \n-#define RC_ACTUAL_OBJECT_ENTRY_SIZE(e)\t\t(sizeof(struct rc_object_entry_ondisk) + RC_PATH_SIZE((e)->merge_nr + (e)->split_nr) + (e)->size_size)\n-#define RC_ENTRY_SIZE_OFFSET(e)\t\t\t\t(RC_ACTUAL_OBJECT_ENTRY_SIZE(e) - (e)->size_size)\n+#define RC_ACTUAL_OBJECT_ENTRY_SIZE(e)\t(\\\n+\tsizeof(struct rc_object_entry_ondisk) + \\\n+\tRC_PATH_SIZE((e)->merge_nr + (e)->split_nr) + \\\n+\t(e)->size_size + \\\n+\t(e)->name_size\\\n+)\n+#define RC_ENTRY_SIZE_OFFSET(e)\t\t\t(RC_ACTUAL_OBJECT_ENTRY_SIZE(e) - (e)->name_size - (e)->size_size)\n+#define RC_ENTRY_NAME_OFFSET(e)\t\t\t(RC_ACTUAL_OBJECT_ENTRY_SIZE(e) - (e)->name_size)\n \n /* single index maps objects to cache files */\n struct rc_index_header {\n@@ -50,6 +56,8 @@ struct rc_slice_header {\n \tuint32_t size;\n \n \tunsigned char sha1[20];\n+\n+\tuint32_t name_size;\n };\n \n struct rc_object_entry_ondisk {\n@@ -76,7 +84,8 @@ struct rc_object_entry {\n \tunsigned char merge_nr; /* : 7 */\n \tunsigned char split_nr; /* : 7 */\n \tunsigned size_size : 3;\n-\tunsigned padding : 5;\n+\tunsigned name_size : 3;\n+\tunsigned padding : 2;\n \n \tuint32_t date;\n \tuint16_t path;\n@@ -84,6 +93,7 @@ struct rc_object_entry {\n \t/* merge paths */\n \t/* split paths */\n \t/* size */\n+\t/* name id */\n };\n \n struct rc_index_entry *from_disked_rc_index_entry(struct rc_index_entry_ondisk *src, struct rc_index_entry *dst);\ndiff --git a/revision.h b/revision.h\nindex c3ec1b3..b2d5834 100644\n--- a/revision.h\n+++ b/revision.h\n@@ -23,6 +23,9 @@ struct rev_cache_slice_map {\n \tunsigned char *map;\n \tint size;\n \tint last_index;\n+\n+\tchar *names;\n+\tint name_size;\n };\n \n struct rev_cache_info {\n@@ -36,7 +39,8 @@ struct rev_cache_info {\n \tunsigned overwrite_all : 1;\n \n \t/* traversal flags */\n-\tunsigned add_to_pending : 1;\n+\tunsigned add_to_pending : 1,\n+\t\tadd_names : 1;\n \n \t/* fuse options */\n \tunsigned int ignore_size;\ndiff --git a/t/t6015-rev-cache-list.sh b/t/t6015-rev-cache-list.sh\nindex 065f214..e603f85 100755\n--- a/t/t6015-rev-cache-list.sh\n+++ b/t/t6015-rev-cache-list.sh\n@@ -4,8 +4,8 @@ test_description='git rev-cache tests'\n . ./test-lib.sh\n \n test_cmp_sorted() {\n-\tgrep -io \"[a-f0-9]*\" $1 | sort >.tmpfile1 &&\n-\tgrep -io \"[a-f0-9]*\" $2 | sort >.tmpfile2 &&\n+\tsort $1 >.tmpfile1 &&\n+\tsort $2 >.tmpfile2 &&\n \ttest_cmp .tmpfile1 .tmpfile2\n }\n \n@@ -75,7 +75,7 @@ test_expect_success 'init repo' '\n \tsleep 2 &&\n \tgit checkout master &&\n \tgit merge -m \"triple merge\" b1 b11 &&\n-\tgit rm -r d1 && \n+\tgit rm -r d1 &&\n \tsleep 2 &&\n \tgit commit -a -m \"oh noes\"\n '\n-- \ntg: (635e0b5..) t/revcache/names (depends on: t/revcache/docs)\n"},{"id":"121090","messageId":"alpine.DEB.1.00.0908181353410.4680@intel-tinevez-2-302","threadId":"20632","inReplyTo":"alpine.LFD.2.00.0908172235360.6044@xanadu.home","subject":"Re: [PATCH 6/6 (v4)] support for path name caching in rev-cache","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2009-08-18T11:54:12Z","receivedAt":"2009-08-18T11:54:12Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Mon, 17 Aug 2009, Nicolas Pitre wrote:\n\n> |$ ls -ld .git/rev-cache/\n> |drw-rw-r-- 2 nico nico 4096 2009-08-17 22:47 .git/rev-cache/\n> \n> There is no directory execute permission at all.  Indeed, looking at \n> rev-cache.c line 2314, the mode passed to mkdir() is 0x666.  This should \n> rather be 0777.  Which brings the question: how could this ever work for \n> you?  Are you testing your code as root?\n\nNo: Nick is on Windows.\n\nCiao,\nDscho\n"},{"id":"121206","messageId":"alpine.LFD.2.00.0908182313100.6044@xanadu.home","threadId":"20632","inReplyTo":"c77435a80908180431k2f91e1ffye25aa8895908ddb7@mail.gmail.com","subject":"Re: [PATCH 6/6 (v4)] support for path name caching in rev-cache","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2009-08-19T03:52:57Z","receivedAt":"2009-08-19T03:52:57Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Tue, 18 Aug 2009, Nick Edelen wrote:\n\n> I'll reply to *these* posts with everything fixed.  Then after that\n> hopefully I can just make patches for the patchset (yo dawg) and save\n> everyone a lot of bandwidth.\n\nWe have bandwidth to spare.  The bandwidth is cheaper than the time \nneeded to reconstruct a patch series using a previous series and having \nto modify it with additional patches.  In other words, always make it \neasier for the people willing to review and test your stuff.\n\nNow... testing your latest series looks promising.  The speed increase \nis really there which is good.\n\nHowever, there are still some issues:\n\n|$ rm -rf .git/rev-cache/\n|$ git rev-list --all --objects > /tmp/l1\n|$ git rev-cache add --all\n|objects: 115789\n|paths: 1535\n|f0cb1f09e309ee426c307cb85bb870467877de77\n|endpoints:\n|S 1cae2b588249e8b45239faebc658c7fa45948932\n|S 4aec0d2391eb569776e332d9c15b354cd50a64c5\n|S 1ff19ffed62bb581cd8eb635fe6e65ffca7ba1d0\n|S fcd8ea7a91ad55d094a78c826083ebac149d81e5\n|S 181301656f7a1086adcc41c3661551f190635003\n|S 2898400a882bfb3c475fc2b53330912edc8a81f8\n|S 7c7f2ebdb98f4844347f68b6e64c4968fa7f38e5\n|S 1d9d1698ceb7b553f3cb1fdaa3150f0e85ab9cca\n|S 348f73cc1db2d7b1412c40eba72319855e2959ff\n|S fedc7d5458bd8e2e9589567041228a24a8d7eb4c\n|S 0f57bf3ae8f0000de83907f0a674d70a879f7753\n|S 7354ca323e31aa2d469498d06feebdcea137e93a\n|S d47e28a143f40ad31b88e6d7b9b18bae60d21b01\n|S 991ab5ed8769cd1a425b96b92772c89244bc957c\n|S 07827905813bce9cadb9db2faac5848a61c7e69f\n|S aff6ae5e2f10c4a8e399bf5aa446a58d74444aba\n|S 6849908a55d0e7a95fa715310f739cfab4dd8def\n|S f073bf0b423cf6a2ee5a5e9b5e70be3b91897a7f\n|S b9376927508a2401c20bdb5c5c0608797f822524\n|S 9d412d627575478ffdda4209eca9babde061fe2f\n|S d187b5de2c2895f6cb4a544e78fcbc1ecf3ba172\n|final return value: 0\n|$ git rev-list --all --objects > /tmp/l2\n|$ wc -l -c /tmp/l1 /tmp/l2\n|  109382  5525988 /tmp/l1\n|  109382  5473891 /tmp/l2\n\nResult with the rev-cache populated returns the same number of \nrevisions, but not the same amount of data.\n\n|$ diff -u /tmp/l1 /tmp/l2\n|--- /tmp/l1     2009-08-18 23:22:03.000000000 -0400\n|+++ /tmp/l2     2009-08-18 23:25:02.000000000 -0400\n|@@ -4,221 +4,38 @@\n| ff212f80287ab15162035d39bac511f6edacca00\n| 69527b0cc148b5fa320cce68e82216f0ba7117d9\n| fdbe5cf05690accc4d701e2e8d8c69baccf76812\n|-9d412d627575478ffdda4209eca9babde061fe2f\n|-b9376927508a2401c20bdb5c5c0608797f822524\n|-f073bf0b423cf6a2ee5a5e9b5e70be3b91897a7f\n|-fd31906d2285fb914e51a2fb78de6683b481951b\n|-7415dcd3bc6a6103d532d75b77897399af2bc015\n|-397b844013068a658e2c4dbea05fb57559433f6e\n|-15173bda08b5481c2014f04228b95f90f1e500e6\n|-d6758648e1ff1f7ace2ddb3682a8189ec634925b\n|-7475ee6d358167e2e4dcdea6c7a67f3619c35315\n|-83bf4a2869721ba728c5c8b0bdb8ad9a3a43b94b\n|-5f50d92cc49150a83e8fa7b352cb9e14ae4d6570\n[...]\n\nThe object order appears to be rather different.  Why so?\n\n|$ sort /tmp/l1 > /tmp/l1_sorted\n|$ sort /tmp/l2 > /tmp/l2_sorted\n|$ diff -u /tmp/l1_sorted  /tmp/l2_sorted\n|--- /tmp/l1_sorted      2009-08-18 23:35:48.000000000 -0400\n|+++ /tmp/l2_sorted      2009-08-18 23:36:23.000000000 -0400\n|@@ -1,7 +1,7 @@\n| 000079a2eaef17b7eae70e1f0f635557ea67b644\n| 00013cafe6980411aa6fdd940784917b5ff50f0a man1/git-merge-base.1\n| 000147bbe4a00525d68efb1358c013812e10dcca contrib/thunderbird-patch-inline/README\n|-0001710072c5f0f708323d99e1bb632d7911c842 Documentation/git-peek-remote.txt\n|+0001710072c5f0f708323d99e1bb632d7911c842 git-peek-remote.txt\n| 000182eacf99cde27d5916aa415921924b82972c\n| 0002d8a2fb6add585184350d11284840293dea4d git-daemon.html\n| 0003692409f153dd725b3455dfc2e128276cfbe2\n|@@ -29,7 +29,7 @@\n| 0012954b6f795d75d442f4c58f29dc194888d022 remote.c\n| 0012ba2108aa42947dedf19f3db2de73a67cc4f5\n| 00133ed4f910f42ae7aaba32bcda1c1e261bc776 man1/git-update-server-info.1\n|-001503205b24d5c20ec10792c4ab6c4c7221bcb7 Documentation/diff-format.txt\n|+001503205b24d5c20ec10792c4ab6c4c7221bcb7 diff-format.txt\n| 0016a48251abefed11efc919703d980a21c95f2c\n| 00183cbb3d0f60852d7286e766c9b631c0c1f952\n| 00188e33e825c8000dee8e3f4209a264615ce8a1\n[...]\n\nSo... Why is the leading path component dropped sometimes?  That \nexplains the output size difference.  And the drop is not coherent \neither:\n\n|$ grep \"diff-format.txt\" /tmp/l2\n|b71712473ed13020bca3f133ea4a28c5081b7f9e diff-format.txt\n|1eeb1c76838c1911fc4d57b36a16dece0538809a diff-format.txt\n|aafd3a394126e4718b593eb5727412e16d2334e4 diff-format.txt\n|400cbb3b1c120b93278472678ee7bdb87a74f95b diff-format.txt\n|2c3a4c433b2a6d2b0846243a4f1dbebeed45236e diff-format.txt\n|9709c35c98bc678d1f2e339c8e2d4bbcd7e6231f diff-format.txt\n|001503205b24d5c20ec10792c4ab6c4c7221bcb7 diff-format.txt\n|18d49d2c3baa81983b19a938598eb091fb7809ef diff-format.txt\n|e38a1f14056b2e3cfe3c281eb7df7e5b44d520db diff-format.txt\n|378e72f38f37eef50135c3907ccd605652f4fd96 diff-format.txt\n|883c1bb0a638d97278cdb66e288bc766a32626af diff-format.txt\n|e4520e28e53661159454e02c703be772d43bbc09 diff-format.txt\n|ed4ebcbab76c23e599a3f3d62072e16d2cbe7cb1 diff-format.txt\n|617d8f526f914360c612d2e2822f1c883c9f5115 diff-format.txt\n|0398b408c05d2dccb9806c0add6d1acd13871d74 diff-format.txt\n|97756ec03086614051d5780b00825e24ee5ef56f diff-format.txt\n|2060ae2fcb9935ed11ecb71a093ad22c661339bf Documentation/diff-format.txt\n|174d63a1ee4238aac88c76daee6f3f1bead0d6b5 Documentation/diff-format.txt\n|b426a14f5e5fa29bfdb8f026d995dc182930073d Documentation/diff-format.txt\n|d1d0d2d3dc8760a8030313de3dd14a942d0fc2bf Documentation/diff-format.txt\n|bfe634dcd3664d0e3b18b212db2f3f16b63a385b Documentation/diff-format.txt\n|dacd8fb53488fadd7ebb6c1964e60a60072eae80 Documentation/diff-format.txt\n|6e9fa8cdb70faead4649f71aea4fff8f50d17271 Documentation/diff-format.txt\n|424e75a1c2d4747226ac1b55caac90b544f8f273 Documentation/diff-format.txt\n|811d143808a13034de41c1cdcc834ef838d01ce8 Documentation/diff-format.txt\n|9298d79e51bf87ccff66357227c7df4db4c820c4 Documentation/diff-format.txt\n|d6ce035419081e3fbfc2375ac667517f5f52c980 Documentation/diff-format.txt\n|6748761ef61cf35473ee304bc8bd44134cdccaf4 Documentation/diff-format.txt\n|1d92a01a02543e55d0feb3541ee594fbc638136c Documentation/diff-format.txt\n|f85a605f0a336f506cf5cf46476a43e4c56b3e66 Documentation/diff-format.txt\n|7e9a515ad74b16c3f82eba71a9503c6696c77503 Documentation/diff-format.txt\n|9e645399752e9b18f097840906fc640a1121d982 Documentation/diff-format.txt\n|1a99e85ee58bfc47192e3e3cd409af948c989f80 Documentation/diff-format.txt\n|3af197cd2c62f990f7a67ac52277ccf0521d268e Documentation/diff-format.txt\n\nI think you'll have to fix those issues.\n\n\nNicolas\n"},{"id":"121323","messageId":"c77435a80908200543h74fdb07dm7f30cee4fedef8c5@mail.gmail.com","threadId":"20632","inReplyTo":"alpine.LFD.2.00.0908182313100.6044@xanadu.home","subject":"Re: [PATCH 6/6 (v4)] support for path name caching in rev-cache","fromName":"Nick Edelen","fromEmail":"sirnot@gmail.com","sentAt":"2009-08-20T12:43:53Z","receivedAt":"2009-08-20T12:43:53Z","isPatch":true,"sender":{"key":"sirnot@gmail.com","avatar":null},"body":"> Result with the rev-cache populated returns the same number of\n> revisions, but not the same amount of data.\n> [...]\n> So... Why is the leading path component dropped sometimes?  That\n> explains the output size difference.  And the drop is not coherent\n> either:\n\nIt looks like I didn't realize that tree_entry() returns only the\nentry name, and not the full path, which seems like a case of not\nthinking, just being logical.  The unit tests didn't catch it b/c it\nonly occurs for root commits, and none of the root commits in the test\nhad directories involved.\n\n> The object order appears to be rather different.  Why so?\n\nThe non-commit object order has to be different because they're added\nin a different way.  It's sorta like vanilla rev-list ordering, except\nobjects are /only/ appended that are introduced per current commit,\nrather than all that haven't been seen yet.  It's still a coherent\nordering, and despite the different mechanism I've still enforced the\ntag-tree-blob ordering of the normal rev-list.\n\nI've fixed the name issue and added that scenario to the unit tests.\nI'll re-upload this last patch in a bit (either minutes if my flight\ndosn't leave soon or hours if so).\n\n - Nick\n"},{"id":"121366","messageId":"c77435a80908201622o7d69681ftda0ca63c5a915f4b@mail.gmail.com","threadId":"20632","inReplyTo":"c77435a80908200543h74fdb07dm7f30cee4fedef8c5@mail.gmail.com","subject":"Re: [PATCH 6/6 (v4)] support for path name caching in rev-cache","fromName":"Nick Edelen","fromEmail":"sirnot@gmail.com","sentAt":"2009-08-20T23:22:35Z","receivedAt":"2009-08-20T23:22:35Z","isPatch":true,"sender":{"key":"sirnot@gmail.com","avatar":null},"body":"Ok we actually have a small problem, semi-related to the object\nlisting.  By default rev-list will list everything not seen in each\ntree, whereas rev-cache will only list object introduced in a given\ncommit.  This becomes problematic if you have two different files with\nthe same content in the same tree: rev-cache will show the name of the\nyoungest file; vanilla rev-list will list the name soonest encountered\nin the tree (which can even change if, e.g., a subdir is renamed so as\nto be list in a different order).\n\nIn fact, even if they're not in the same tree we could have a similar\nproblem.  Commits are stored topologically in cache slices, so output\nis always in topo order.  If the same object is introduced in parallel\nbranches under different names, the outputted name with `rev-list\n--all --objects` (vanilla) could be different from `rev-list --all\n--objects` (cached) could be different from `rev-list --all\n--topo-order --objects`.\n\nThis isn't feasably changable in rev-cache, as a) the cached position\n(and hence final output order) is effectively unrelated to tree\nstructure, and b) commits _have_ to be ordered topologically for\nrev-cache to function.\n\nThe descrepency strikes me as something of a non-issue with\npack-objects' deltafication, as the object will fit with either of its\nnames.  It will mean that the (already sorta finicky) object names\nwon't have garuanteed consistency between cached/non-cached calls to\nrev-list.  This is something of a corner case and dosn't strike me as\na huge issue, but I figured I should consult you all before presuming\nthings about git's interface.\n\n - Nick\n"},{"id":"121370","messageId":"alpine.LFD.2.00.0908201958010.6044@xanadu.home","threadId":"20632","inReplyTo":"c77435a80908201622o7d69681ftda0ca63c5a915f4b@mail.gmail.com","subject":"Re: [PATCH 6/6 (v4)] support for path name caching in rev-cache","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2009-08-21T00:05:46Z","receivedAt":"2009-08-21T00:05:46Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Fri, 21 Aug 2009, Nick Edelen wrote:\n\n> Ok we actually have a small problem, semi-related to the object\n> listing.  By default rev-list will list everything not seen in each\n> tree, whereas rev-cache will only list object introduced in a given\n> commit.  This becomes problematic if you have two different files with\n> the same content in the same tree: rev-cache will show the name of the\n> youngest file; vanilla rev-list will list the name soonest encountered\n> in the tree (which can even change if, e.g., a subdir is renamed so as\n> to be list in a different order).\n> \n> In fact, even if they're not in the same tree we could have a similar\n> problem.  Commits are stored topologically in cache slices, so output\n> is always in topo order.  If the same object is introduced in parallel\n> branches under different names, the outputted name with `rev-list\n> --all --objects` (vanilla) could be different from `rev-list --all\n> --objects` (cached) could be different from `rev-list --all\n> --topo-order --objects`.\n> \n> This isn't feasably changable in rev-cache, as a) the cached position\n> (and hence final output order) is effectively unrelated to tree\n> structure, and b) commits _have_ to be ordered topologically for\n> rev-cache to function.\n> \n> The descrepency strikes me as something of a non-issue with\n> pack-objects' deltafication, as the object will fit with either of its\n> names.  It will mean that the (already sorta finicky) object names\n> won't have garuanteed consistency between cached/non-cached calls to\n> rev-list.  This is something of a corner case and dosn't strike me as\n> a huge issue, but I figured I should consult you all before presuming\n> things about git's interface.\n\nThe name is actually used only as a clue to delta similar objects \ntogether.  So this is indeed a non issue, as long as the discrepency is \nwell understood and, more importantly, properly documented.  The above \nis certainly a good start.\n\n\nNicolas\n"},{"id":"121378","messageId":"op.uyzwyho5tdk399@sirnot","threadId":"20632","inReplyTo":"op.uyuwkwjotdk399@sirnot.private","subject":"Re: [PATCH 6/6 (v4)] support for path name caching in rev-cache","fromName":"Nick Edelen","fromEmail":"sirnot@gmail.com","sentAt":"2009-08-21T04:48:07Z","receivedAt":"2009-08-21T04:48:07Z","isPatch":true,"sender":{"key":"sirnot@gmail.com","avatar":null},"body":"An update to caching mechanism, allowing path names to be cached for blob and \ntree objects.  A list of names appearing in each cache slice is appended to the \nend of the slice, which is referenced by variable-sized indexes per entry.  \nThis allows pack-objects to more intelligently schedule unpacked/poorly packed \nobject, and enables proper duplication of rev-list's behaivor.\n\nSigned-off-by: Nick Edelen <sirnot@gmail.com>\n\n---\nfixed name caching issues, added unit test for error.\n\n builtin-rev-cache.c       |    3 +-\n rev-cache.c               |  333 +++++++++++++++++++++++++++++++++++++--------\n rev-cache.h               |   16 ++-\n revision.h                |    6 +-\n t/t6015-rev-cache-list.sh |    8 +-\n 5 files changed, 300 insertions(+), 66 deletions(-)\n\ndiff --git a/builtin-rev-cache.c b/builtin-rev-cache.c\nindex 8f41123..4c1766d 100644\n--- a/builtin-rev-cache.c\n+++ b/builtin-rev-cache.c\n@@ -177,13 +177,14 @@ static int handle_walk(int argc, const char *argv[])\n \tfprintf(stderr, \"pending:\\n\");\n \tfor (i = 0; i < revs.pending.nr; i++) {\n \t\tstruct object *obj = revs.pending.objects[i].item;\n+\t\tconst char *name = revs.pending.objects[i].name;\n \n \t\t/* unfortunately, despite our careful generation, object duplication *is* a possibility...\n \t\t * (eg. same object introduced into two different branches) */\n \t\tif (obj->flags & SEEN)\n \t\t\tcontinue;\n \n-\t\tprintf(\"%s\\n\", sha1_to_hex(revs.pending.objects[i].item->sha1));\n+\t\tprintf(\"%s %s\\n\", sha1_to_hex(revs.pending.objects[i].item->sha1), name);\n \t\tobj->flags |= SEEN;\n \t}\n \ndiff --git a/rev-cache.c b/rev-cache.c\nindex 04a9b02..3595f66 100644\n--- a/rev-cache.c\n+++ b/rev-cache.c\n@@ -17,6 +17,14 @@ struct bad_slice {\n \tstruct bad_slice *next;\n };\n \n+struct name_list {\n+\tunsigned char sha1[20];\n+\tunsigned int len;\n+\tstruct name_list *next;\n+\n+\tchar buf[FLEX_ARRAY];\n+};\n+\n struct cache_slice_pointer {\n \tchar signature[8]; /* REVCOPTR */\n \tchar version;\n@@ -29,10 +37,13 @@ static uint32_t fanout[0xff + 2];\n static unsigned char *idx_map;\n static int idx_size;\n static struct rc_index_header idx_head;\n-static char no_idx, add_to_pending;\n-static struct bad_slice *bad_slices;\n+static char no_idx, add_to_pending, add_names;\n static unsigned char *idx_caches;\n \n+static struct bad_slice *bad_slices;\n+static struct name_list *name_lists, *cur_name_list;\n+\n+static struct strbuf *acc_name_buffer;\n static struct strbuf *acc_buffer;\n \n #define SLOP\t\t\t5\n@@ -79,7 +90,7 @@ struct rc_object_entry *from_disked_rc_object_entry(struct rc_object_entry_ondis\n \tif (!dst)\n \t\tdst = &entry[cur++ & 0x3];\n \n-\tdst->type = src->flags >> 5;\n+\tdst->type = src->flags >> 5 & 0x03;\n \tdst->is_end = !!(src->flags & 0x10);\n \tdst->is_start = !!(src->flags & 0x08);\n \tdst->uninteresting = !!(src->flags & 0x04);\n@@ -90,8 +101,9 @@ struct rc_object_entry *from_disked_rc_object_entry(struct rc_object_entry_ondis\n \tdst->merge_nr = src->merge_nr;\n \tdst->split_nr = src->split_nr;\n \n-\tdst->size_size = src->sizes >> 5;\n-\tdst->padding = src->sizes & 0x1f;\n+\tdst->size_size = src->sizes >> 5 & 0x03;\n+\tdst->name_size = src->sizes >> 2 & 0x03;\n+\tdst->padding = src->sizes & 0x02;\n \n \tdst->date = ntohl(src->date);\n \tdst->path = ntohs(src->path);\n@@ -120,6 +132,7 @@ struct rc_object_entry_ondisk *to_disked_rc_object_entry(struct rc_object_entry\n \tdst->split_nr = src->split_nr;\n \n \tdst->sizes  = (unsigned char)src->size_size << 5;\n+\tdst->sizes |= (unsigned char)src->name_size << 2;\n \tdst->sizes |= (unsigned char)src->padding;\n \n \tdst->date = htonl(src->date);\n@@ -192,6 +205,12 @@ static void cleanup_cache_slices(void)\n \t\tidx_map = 0;\n \t}\n \n+\twhile (name_lists) {\n+\t\tstruct name_list *nl = name_lists->next;\n+\t\tfree(name_lists);\n+\t\tname_lists = nl;\n+\t}\n+\n }\n \n static int init_index(void)\n@@ -324,7 +343,7 @@ static void handle_noncommit(struct rev_info *revs, struct commit *commit, unsig\n \tstruct blob *blob;\n \tstruct tree *tree;\n \tstruct object *obj;\n-\tunsigned long size;\n+\tunsigned long size, name_index;\n \n \tsize = decode_size(ptr + RC_ENTRY_SIZE_OFFSET(entry), entry->size_size);\n \tswitch (entry->type) {\n@@ -357,9 +376,22 @@ static void handle_noncommit(struct rev_info *revs, struct commit *commit, unsig\n \t\treturn;\n \t}\n \n+\tif (add_names && cur_name_list) {\n+\t\tname_index = decode_size(ptr + RC_ENTRY_NAME_OFFSET(entry), entry->name_size);\n+\n+\t\tif (name_index >= cur_name_list->len)\n+\t\t\tname_index = 0;\n+\t} else name_index = 0;\n+\n \tobj->flags |= FACE_VALUE;\n-\tif (add_to_pending)\n-\t\tadd_pending_object(revs, obj, \"\");\n+\tif (add_to_pending) {\n+\t\tchar *name = \"\";\n+\n+\t\tif (name_index)\n+\t\t\tname = cur_name_list->buf + name_index;\n+\n+\t\tadd_pending_object(revs, obj, name);\n+\t}\n }\n \n static int setup_traversal(struct rc_slice_header *head, unsigned char *map, struct commit *commit, struct commit_list **work,\n@@ -714,15 +746,44 @@ end:\n \treturn retval;\n }\n \n-static int get_cache_slice_header(unsigned char *cache_sha1, unsigned char *map, int len, struct rc_slice_header *head)\n+static struct name_list *get_cache_slice_name_list(struct rc_slice_header *head, int fd)\n+{\n+\tstruct name_list *nl = name_lists;\n+\n+\twhile (nl) {\n+\t\tif (!hashcmp(nl->sha1, head->sha1))\n+\t\t\tbreak;\n+\t\tnl = nl->next;\n+\t}\n+\n+\tif (nl)\n+\t\treturn nl;\n+\n+\tnl = xcalloc(1, sizeof(struct name_list) + head->name_size);\n+\tnl->len = head->name_size;\n+\thashcpy(nl->sha1, head->sha1);\n+\n+\tlseek(fd, head->size, SEEK_SET);\n+\tread_in_full(fd, nl->buf, head->name_size);\n+\n+\tnl->next = name_lists;\n+\tname_lists = nl;\n+\n+\treturn nl;\n+}\n+\n+static int get_cache_slice_header(int fd, unsigned char *cache_sha1, int len, struct rc_slice_header *head)\n {\n \tint t;\n \n-\tmemcpy(head, map, sizeof(struct rc_slice_header));\n+\tif (xread(fd, head, sizeof(struct rc_slice_header)) != sizeof(struct rc_slice_header))\n+\t\treturn -1;\n+\n \thead->ofs_objects = ntohl(head->ofs_objects);\n \thead->object_nr = ntohl(head->object_nr);\n \thead->size = ntohl(head->size);\n \thead->path_nr = ntohs(head->path_nr);\n+\thead->name_size = ntohl(head->name_size);\n \n \tif (memcmp(head->signature, \"REVCACHE\", 8))\n \t\treturn -1;\n@@ -731,10 +792,10 @@ static int get_cache_slice_header(unsigned char *cache_sha1, unsigned char *map,\n \tif (hashcmp(head->sha1, cache_sha1))\n \t\treturn -3;\n \tt = sizeof(struct rc_slice_header);\n-\tif (t != head->ofs_objects || t >= len)\n+\tif (t != head->ofs_objects)\n \t\treturn -4;\n-\n-\thead->size = len;\n+\tif (head->size + head->name_size != len)\n+\t\treturn -5;\n \n \treturn 0;\n }\n@@ -786,7 +847,7 @@ int traverse_cache_slice(struct rev_info *revs,\n \tunsigned long *date_so_far, int *slop_so_far,\n \tstruct commit_list ***queue, struct commit_list **work)\n {\n-\tint fd = -1, retval = -3;\n+\tint fd = -1, t, retval;\n \tstruct stat fi;\n \tstruct rc_slice_header head;\n \tstruct rev_cache_info *rci;\n@@ -802,26 +863,31 @@ int traverse_cache_slice(struct rev_info *revs,\n \t/* load options */\n \trci = &revs->rev_cache_info;\n \tadd_to_pending = rci->add_to_pending;\n+\tadd_names = rci->add_names;\n \n \tmemset(&head, 0, sizeof(struct rc_slice_header));\n+#\tdefine ERROR(x)\t\tdo { retval = (x); goto end; } while (0);\n \n \tfd = open_cache_slice(cache_sha1, O_RDONLY);\n \tif (fd == -1)\n-\t\tgoto end;\n+\t\tERROR(-1);\n \tif (fstat(fd, &fi) || fi.st_size < sizeof(struct rc_slice_header))\n-\t\tgoto end;\n+\t\tERROR(-2);\n+\n+\tif ((t = get_cache_slice_header(fd, cache_sha1, fi.st_size, &head)) < 0)\n+\t\tERROR(-t);\n+\tif (add_names)\n+\t\tcur_name_list = get_cache_slice_name_list(&head, fd);\n \n-\tmap = xmmap(0, fi.st_size, PROT_READ | PROT_WRITE, MAP_PRIVATE, fd, 0);\n+\tmap = xmmap(0, head.size, PROT_READ | PROT_WRITE, MAP_PRIVATE, fd, 0);\n \tif (map == MAP_FAILED)\n-\t\tgoto end;\n-\tif (get_cache_slice_header(cache_sha1, map, fi.st_size, &head))\n-\t\tgoto end;\n+\t\tERROR(-3);\n \n \tretval = traverse_cache_slice_1(&head, map, revs, commit, date_so_far, slop_so_far, queue, work);\n \n end:\n \tif (map != MAP_FAILED)\n-\t\tmunmap(map, fi.st_size);\n+\t\tmunmap(map, head.size);\n \tif (fd != -1)\n \t\tclose(fd);\n \n@@ -829,6 +895,7 @@ end:\n \tif (retval)\n \t\tmark_bad_slice(cache_sha1);\n \n+#\tundef ERROR\n \treturn retval;\n }\n \n@@ -1113,23 +1180,110 @@ static unsigned long decode_size(unsigned char *str, int len)\n \treturn size;\n }\n \n+\n+#define NL_HASH_TABLE_SIZE\t\t(0xffff + 1)\n+#define NL_HASH_NUMBER\t\t\t(NL_HASH_TABLE_SIZE >> 3)\n+\n+struct name_list_hash {\n+\tint ind;\n+\tstruct name_list_hash *next;\n+};\n+\n+static struct name_list_hash **nl_hash_table;\n+static unsigned char *nl_hashes;\n+\n+/* FNV-1a hash */\n+static unsigned int hash_name(const char *name)\n+{\n+\tunsigned int hash = 2166136261ul;\n+\tconst char *p = name;\n+\n+\twhile (*p) {\n+\t\thash ^= *p++;\n+\t\thash *= 16777619ul;\n+\t}\n+\n+\treturn hash & 0xffff;\n+}\n+\n+static int name_in_list(const char *name)\n+{\n+\tunsigned int h = hash_name(name);\n+\tstruct name_list_hash *entry = nl_hash_table[h];\n+\n+\twhile (entry && strcmp(acc_name_buffer->buf + entry->ind, name))\n+\t\tentry = entry->next;\n+\n+\tif (entry)\n+\t\treturn entry->ind;\n+\n+\t/* add name to buffer and create hash reference */\n+\tentry = xcalloc(1, sizeof(struct name_list_hash));\n+\tentry->ind = acc_name_buffer->len;\n+\tstrbuf_add(acc_name_buffer, name, strlen(name) + 1);\n+\n+\tentry->next = nl_hash_table[h];\n+\tnl_hash_table[h] = entry;\n+\n+\tnl_hashes[h / 8] |= h % 8;\n+\n+\treturn entry->ind;\n+}\n+\n+static void init_name_list_hash(void)\n+{\n+\tnl_hash_table = xcalloc(NL_HASH_TABLE_SIZE, sizeof(struct name_list_hash));\n+\tnl_hashes = xcalloc(NL_HASH_NUMBER, 1);\n+}\n+\n+static void cleanup_name_list_hash(void)\n+{\n+\tint i;\n+\n+\tfor (i = 0; i < NL_HASH_NUMBER; i++) {\n+\t\tint j, ind = nl_hashes[i];\n+\n+\t\tif (!ind)\n+\t\t\tcontinue;\n+\n+\t\tfor (j = 0; j < 8; j++) {\n+\t\t\tstruct name_list_hash **entryp;\n+\n+\t\t\tif (!(ind & 1 << j))\n+\t\t\t\tcontinue;\n+\n+\t\t\tentryp = &nl_hash_table[i * 8 + j];\n+\t\t\twhile (*entryp) {\n+\t\t\t\tstruct name_list_hash *t = (*entryp)->next;\n+\n+\t\t\t\tfree(*entryp);\n+\t\t\t\t*entryp = t;\n+\t\t\t}\n+\t\t}\n+\t} /* code overhang! */\n+\n+\tfree(nl_hashes);\n+\tfree(nl_hash_table);\n+}\n+\n static void add_object_entry(const unsigned char *sha1, struct rc_object_entry *entryp,\n-\tstruct strbuf *merge_str, struct strbuf *split_str)\n+\tstruct strbuf *merge_str, struct strbuf *split_str, char *name, unsigned long size)\n {\n \tstruct rc_object_entry entry;\n-\tunsigned char size_str[7];\n-\tunsigned long size;\n+\tunsigned char size_str[7], name_str[7];\n \tenum object_type type;\n \tvoid *data;\n \n \tif (entryp)\n \t\tsha1 = entryp->sha1;\n \n-\t/* retrieve size data */\n-\tdata = read_sha1_file(sha1, &type, &size);\n+\tif (!size) {\n+\t\t/* retrieve size data */\n+\t\tdata = read_sha1_file(sha1, &type, &size);\n \n-\tif (data)\n-\t\tfree(data);\n+\t\tif (data)\n+\t\t\tfree(data);\n+\t}\n \n \t/* initialize! */\n \tif (!entryp) {\n@@ -1147,6 +1301,9 @@ static void add_object_entry(const unsigned char *sha1, struct rc_object_entry *\n \n \tentryp->size_size = encode_size(size, size_str);\n \n+\tif (name)\n+\t\tentryp->name_size = encode_size(name_in_list(name), name_str);\n+\n \t/* write the muvabitch */\n \tstrbuf_add(acc_buffer, to_disked_rc_object_entry(entryp, 0), sizeof(struct rc_object_entry_ondisk));\n \n@@ -1156,25 +1313,36 @@ static void add_object_entry(const unsigned char *sha1, struct rc_object_entry *\n \t\tstrbuf_add(acc_buffer, split_str->buf, split_str->len);\n \n \tstrbuf_add(acc_buffer, size_str, entryp->size_size);\n+\n+\tif (name)\n+\t\tstrbuf_add(acc_buffer, name_str, entryp->name_size);\n }\n \n /* returns non-zero to continue parsing, 0 to skip */\n typedef int (*dump_tree_fn)(const unsigned char *, const char *, unsigned int); /* sha1, path, mode */\n \n /* we need to walk the trees by hash, so unfortunately we can't use traverse_trees in tree-walk.c */\n-static int dump_tree(struct tree *tree, dump_tree_fn fn)\n+static int dump_tree(struct tree *tree, dump_tree_fn fn, char *base)\n {\n \tstruct tree_desc desc;\n \tstruct name_entry entry;\n \tstruct tree *subtree;\n-\tint r;\n+\tchar concatpath[PATH_MAX];\n+\tint r, baselen;\n \n \tif (parse_tree(tree))\n \t\treturn -1;\n \n+\tbaselen = strlen(base);\n+\tstrcpy(concatpath, base);\n+\n \tinit_tree_desc(&desc, tree->buffer, tree->size);\n \twhile (tree_entry(&desc, &entry)) {\n-\t\tswitch (fn(entry.sha1, entry.path, entry.mode)) {\n+\t\tif (baselen + strlen(entry.path) + 1 >= PATH_MAX)\n+\t\t\tdie(\"we have a problem: %s%s is too big for me to handle\", base, entry.path);\n+\t\tstrcpy(concatpath + baselen, entry.path);\n+\n+\t\tswitch (fn(entry.sha1, concatpath, entry.mode)) {\n \t\tcase 0 :\n \t\t\tgoto continue_loop;\n \t\tdefault :\n@@ -1186,7 +1354,8 @@ static int dump_tree(struct tree *tree, dump_tree_fn fn)\n \t\t\tif (!subtree)\n \t\t\t\treturn -2;\n \n-\t\t\tif ((r = dump_tree(subtree, fn)) < 0)\n+\t\t\tstrcat(concatpath, \"/\");\n+\t\t\tif ((r = dump_tree(subtree, fn, concatpath)) < 0)\n \t\t\t\treturn r;\n \t\t}\n \n@@ -1200,6 +1369,9 @@ continue_loop:\n static int dump_tree_callback(const unsigned char *sha1, const char *path, unsigned int mode)\n {\n \tstrbuf_add(acc_buffer, sha1, 20);\n+\tstrbuf_add(acc_buffer, (char *)&acc_name_buffer->len, sizeof(size_t));\n+\n+\tstrbuf_add(acc_name_buffer, path, strlen(path) + 1);\n \n \treturn 1;\n }\n@@ -1213,6 +1385,9 @@ static void tree_addremove(struct diff_options *options,\n \t\treturn;\n \n \tstrbuf_add(acc_buffer, sha1, 20);\n+\tstrbuf_add(acc_buffer, (char *)&acc_name_buffer->len, sizeof(size_t));\n+\n+\tstrbuf_add(acc_name_buffer, concatpath, strlen(concatpath) + 1);\n }\n \n static void tree_change(struct diff_options *options,\n@@ -1225,12 +1400,15 @@ static void tree_change(struct diff_options *options,\n \t\treturn;\n \n \tstrbuf_add(acc_buffer, new_sha1, 20);\n+\tstrbuf_add(acc_buffer, (char *)&acc_name_buffer->len, sizeof(size_t));\n+\n+\tstrbuf_add(acc_name_buffer, concatpath, strlen(concatpath) + 1);\n }\n \n static int add_unique_objects(struct commit *commit)\n {\n \tstruct commit_list *list;\n-\tstruct strbuf os, ost, *orig_buf;\n+\tstruct strbuf os, ost, names, *orig_name_buf, *orig_buf;\n \tstruct diff_options opts;\n \tint i, j, next;\n \tchar is_first = 1;\n@@ -1238,13 +1416,17 @@ static int add_unique_objects(struct commit *commit)\n \t/* ...no, calculate unique objects */\n \tstrbuf_init(&os, 0);\n \tstrbuf_init(&ost, 0);\n+\tstrbuf_init(&names, 0);\n \torig_buf = acc_buffer;\n+\torig_name_buf = acc_name_buffer;\n+\tacc_name_buffer = &names;\n \n \tdiff_setup(&opts);\n \tDIFF_OPT_SET(&opts, RECURSIVE);\n \tDIFF_OPT_SET(&opts, TREE_IN_RECURSIVE);\n \topts.change = tree_change;\n \topts.add_remove = tree_addremove;\n+#\tdefine ENTRY_SIZE (20 + sizeof(size_t))\n \n \t/* this is only called for non-ends (ie. all parents interesting) */\n \tfor (list = commit->parents; list; list = list->next) {\n@@ -1255,20 +1437,20 @@ static int add_unique_objects(struct commit *commit)\n \n \t\tstrbuf_setlen(acc_buffer, 0);\n \t\tdiff_tree_sha1(list->item->tree->object.sha1, commit->tree->object.sha1, \"\", &opts);\n-\t\tqsort(acc_buffer->buf, acc_buffer->len / 20, 20, (int (*)(const void *, const void *))hashcmp);\n+\t\tqsort(acc_buffer->buf, acc_buffer->len / ENTRY_SIZE, ENTRY_SIZE, (int (*)(const void *, const void *))hashcmp);\n \n \t\t/* take intersection */\n \t\tif (!is_first) {\n-\t\t\tfor (next = i = j = 0; i < os.len; i += 20) {\n+\t\t\tfor (next = i = j = 0; i < os.len; i += ENTRY_SIZE) {\n \t\t\t\twhile (j < ost.len && hashcmp((unsigned char *)(ost.buf + j), (unsigned char *)(os.buf + i)) < 0)\n-\t\t\t\t\tj += 20;\n+\t\t\t\t\tj += ENTRY_SIZE;\n \n \t\t\t\tif (j >= ost.len || hashcmp((unsigned char *)(ost.buf + j), (unsigned char *)(os.buf + i)))\n \t\t\t\t\tcontinue;\n \n \t\t\t\tif (next != i)\n-\t\t\t\t\tmemcpy(os.buf + next, os.buf + i, 20);\n-\t\t\t\tnext += 20;\n+\t\t\t\t\tmemcpy(os.buf + next, os.buf + i, ENTRY_SIZE);\n+\t\t\t\tnext += ENTRY_SIZE;\n \t\t\t}\n \n \t\t\tif (next != i)\n@@ -1280,31 +1462,39 @@ static int add_unique_objects(struct commit *commit)\n \t/* no parents (!) */\n \tif (is_first) {\n \t\tacc_buffer = &os;\n-\t\tdump_tree(commit->tree, dump_tree_callback);\n+\t\tdump_tree(commit->tree, dump_tree_callback, \"\");\n \t}\n \n \t/* the ordering of non-commit objects dosn't really matter, so we're not gonna bother */\n \tacc_buffer = orig_buf;\n-\tfor (i = 0; i < os.len; i += 20)\n-\t\tadd_object_entry((unsigned char *)(os.buf + i), 0, 0, 0);\n+\tacc_name_buffer = orig_name_buf;\n+\tfor (i = 0; i < os.len; i += ENTRY_SIZE)\n+\t\tadd_object_entry((unsigned char *)(os.buf + i), 0, 0, 0, names.buf + *(size_t *)(os.buf + i + 20), 0);\n \n \t/* last but not least, the main tree */\n-\tadd_object_entry(commit->tree->object.sha1, 0, 0, 0);\n+\tadd_object_entry(commit->tree->object.sha1, 0, 0, 0, 0, 0);\n \n-\treturn i / 20 + 1;\n+\tstrbuf_release(&ost);\n+\tstrbuf_release(&os);\n+\tstrbuf_release(&names);\n+\n+\treturn i / ENTRY_SIZE + 1;\n+#\tundef ENTRY_SIZE\n }\n \n static int add_objects_verbatim_1(struct rev_cache_slice_map *mapping, int *index)\n {\n-\tunsigned char *map = mapping->map;\n \tint i = *index, object_nr = 0;\n+\tunsigned char *map = mapping->map;\n \tstruct rc_object_entry *entry = RC_OBTAIN_OBJECT_ENTRY(map + i);\n+\tunsigned long size;\n \n \ti += RC_ACTUAL_OBJECT_ENTRY_SIZE(entry);\n \twhile (i < mapping->size) {\n-\t\tint pos = i;\n+\t\tchar *name;\n+\t\tint name_index, pos = i;\n \n-\t\tentry = RC_OBTAIN_OBJECT_ENTRY(map + i;\n+\t\tentry = RC_OBTAIN_OBJECT_ENTRY(map + i);\n \t\ti += RC_ACTUAL_OBJECT_ENTRY_SIZE(entry);\n \n \t\tif (entry->type == OBJ_COMMIT) {\n@@ -1312,7 +1502,15 @@ static int add_objects_verbatim_1(struct rev_cache_slice_map *mapping, int *inde\n \t\t\treturn object_nr;\n \t\t}\n \n-\t\tstrbuf_add(acc_buffer, map + pos, i - pos);\n+\t\tname_index = decode_size(map + pos + RC_ENTRY_NAME_OFFSET(entry), entry->name_size);\n+\t\tif (name_index && name_index < mapping->name_size)\n+\t\t\tname = mapping->names + name_index;\n+\t\telse\n+\t\t\tname = 0;\n+\n+\t\tsize = decode_size(map + pos + RC_ENTRY_SIZE_OFFSET(entry), entry->size_size);\n+\n+\t\tadd_object_entry(0, entry, 0, 0, name, size);\n \t\tobject_nr++;\n \t}\n \n@@ -1397,6 +1595,7 @@ void init_rev_cache_info(struct rev_cache_info *rci)\n \trci->overwrite_all = 0;\n \n \trci->add_to_pending = 1;\n+\trci->add_names = 1;\n \n \trci->ignore_size = 0;\n }\n@@ -1421,9 +1620,9 @@ int make_cache_slice(struct rev_cache_info *rci,\n \tstruct rc_slice_header head;\n \tstruct commit *commit;\n \tunsigned char sha1[20];\n-\tstruct strbuf merge_paths, split_paths;\n+\tstruct strbuf merge_paths, split_paths, namelist;\n \tint object_nr, total_sz, fd;\n-\tchar file[PATH_MAX], *newfile;\n+\tchar file[PATH_MAX], null, *newfile;\n \tstruct rev_cache_info *trci;\n \tgit_SHA_CTX ctx;\n \n@@ -1438,7 +1637,13 @@ int make_cache_slice(struct rev_cache_info *rci,\n \tstrbuf_init(&endlist, 0);\n \tstrbuf_init(&merge_paths, 0);\n \tstrbuf_init(&split_paths, 0);\n+\tstrbuf_init(&namelist, 0);\n \tacc_buffer = &buffer;\n+\tacc_name_buffer = &namelist;\n+\n+\tnull = 0;\n+\tstrbuf_add(&namelist, &null, 1);\n+\tinit_name_list_hash();\n \n \tif (!revs) {\n \t\trevs = &therevs;\n@@ -1469,6 +1674,7 @@ int make_cache_slice(struct rev_cache_info *rci,\n \ttrci = &revs->rev_cache_info;\n \tinit_rev_cache_info(trci);\n \ttrci->add_to_pending = 0;\n+\ttrci->add_names = 0;\n \n \tsetup_revisions(0, 0, revs, 0);\n \tif (prepare_revision_walk(revs))\n@@ -1506,7 +1712,7 @@ int make_cache_slice(struct rev_cache_info *rci,\n \n \t\tcommit->indegree = 0;\n \n-\t\tadd_object_entry(0, &object, &merge_paths, &split_paths);\n+\t\tadd_object_entry(0, &object, &merge_paths, &split_paths, 0, 0);\n \t\tobject_nr++;\n \n \t\tif (rci->objects && !object.is_end) {\n@@ -1532,10 +1738,16 @@ int make_cache_slice(struct rev_cache_info *rci,\n \t\ttotal_sz += buffer.len;\n \t}\n \n+\t/* write path name lookup list */\n+\thead.name_size = htonl(namelist.len);\n+\twrite_in_full(fd, namelist.buf, namelist.len);\n+\n \t/* go ahead a free some stuff... */\n \tstrbuf_release(&buffer);\n \tstrbuf_release(&merge_paths);\n \tstrbuf_release(&split_paths);\n+\tstrbuf_release(&namelist);\n+\tcleanup_name_list_hash();\n \tif (path_sz)\n \t\tfree(paths);\n \twhile (path_track_alloc)\n@@ -1993,6 +2205,7 @@ int fuse_cache_slices(struct rev_cache_info *rci, struct rev_info *revs)\n \tfor (i = idx_head.cache_nr - 1; i >= 0; i--) {\n \t\tstruct rev_cache_slice_map *map = rci->maps + i;\n \t\tstruct stat fi;\n+\t\tstruct rc_slice_header head;\n \t\tint fd;\n \n \t\tif (!map->size)\n@@ -2005,13 +2218,20 @@ int fuse_cache_slices(struct rev_cache_info *rci, struct rev_info *revs)\n \t\t\tcontinue;\n \t\tif (fi.st_size < sizeof(struct rc_slice_header))\n \t\t\tcontinue;\n+\t\tif (get_cache_slice_header(fd, idx_caches + i * 20, fi.st_size, &head))\n+\t\t\tcontinue;\n \n-\t\tmap->map = xmmap(0, fi.st_size, PROT_READ, MAP_PRIVATE, fd, 0);\n+\t\tmap->map = xmmap(0, head.size, PROT_READ, MAP_PRIVATE, fd, 0);\n \t\tif (map->map == MAP_FAILED)\n \t\t\tcontinue;\n \n+\t\tlseek(fd, head.size, SEEK_SET);\n+\t\tmap->names = xcalloc(head.name_size, 1);\n+\t\tread_in_full(fd, map->names, head.name_size);\n+\n \t\tclose(fd);\n-\t\tmap->size = fi.st_size;\n+\t\tmap->size = head.size;\n+\t\tmap->name_size = head.name_size;\n \t}\n \n \trci->make_index = 0;\n@@ -2028,6 +2248,7 @@ int fuse_cache_slices(struct rev_cache_info *rci, struct rev_info *revs)\n \t\tif (!map->size)\n \t\t\tcontinue;\n \n+\t\tfree(map->names);\n \t\tmunmap(map->map, map->size);\n \t}\n \tfree(rci->maps);\n@@ -2049,7 +2270,6 @@ static int verify_cache_slice(const char *slice_path, unsigned char *sha1)\n {\n \tstruct rc_slice_header head;\n \tint fd, len, retval = -1;\n-\tunsigned char *map = MAP_FAILED;\n \tstruct stat fi;\n \n \tlen = strlen(slice_path);\n@@ -2064,17 +2284,12 @@ static int verify_cache_slice(const char *slice_path, unsigned char *sha1)\n \tif (fstat(fd, &fi) || fi.st_size < sizeof(head))\n \t\tgoto end;\n \n-\tmap = xmmap(0, sizeof(head), PROT_READ, MAP_PRIVATE, fd, 0);\n-\tif (map == MAP_FAILED)\n-\t\tgoto end;\n-\tif (get_cache_slice_header(sha1, map, fi.st_size, &head))\n+\tif (get_cache_slice_header(fd, sha1, fi.st_size, &head))\n \t\tgoto end;\n \n \tretval = 0;\n \n end:\n-\tif (map != MAP_FAILED)\n-\t\tmunmap(map, sizeof(head));\n \tif (fd > 0)\n \t\tclose(fd);\n \ndiff --git a/rev-cache.h b/rev-cache.h\nindex 14437d8..c88ceae 100644\n--- a/rev-cache.h\n+++ b/rev-cache.h\n@@ -10,8 +10,14 @@\n #define RC_OBTAIN_OBJECT_ENTRY(p)\t\t\tfrom_disked_rc_object_entry((struct rc_object_entry_ondisk *)(p), 0)\n #define RC_OBTAIN_INDEX_ENTRY(p)\t\t\tfrom_disked_rc_index_entry((struct rc_index_entry_ondisk *)(p), 0)\n \n-#define RC_ACTUAL_OBJECT_ENTRY_SIZE(e)\t\t(sizeof(struct rc_object_entry_ondisk) + RC_PATH_SIZE((e)->merge_nr + (e)->split_nr) + (e)->size_size)\n-#define RC_ENTRY_SIZE_OFFSET(e)\t\t\t\t(RC_ACTUAL_OBJECT_ENTRY_SIZE(e) - (e)->size_size)\n+#define RC_ACTUAL_OBJECT_ENTRY_SIZE(e)\t(\\\n+\tsizeof(struct rc_object_entry_ondisk) + \\\n+\tRC_PATH_SIZE((e)->merge_nr + (e)->split_nr) + \\\n+\t(e)->size_size + \\\n+\t(e)->name_size\\\n+)\n+#define RC_ENTRY_SIZE_OFFSET(e)\t\t\t(RC_ACTUAL_OBJECT_ENTRY_SIZE(e) - (e)->name_size - (e)->size_size)\n+#define RC_ENTRY_NAME_OFFSET(e)\t\t\t(RC_ACTUAL_OBJECT_ENTRY_SIZE(e) - (e)->name_size)\n \n /* single index maps objects to cache files */\n struct rc_index_header {\n@@ -50,6 +56,8 @@ struct rc_slice_header {\n \tuint32_t size;\n \n \tunsigned char sha1[20];\n+\n+\tuint32_t name_size;\n };\n \n struct rc_object_entry_ondisk {\n@@ -76,7 +84,8 @@ struct rc_object_entry {\n \tunsigned char merge_nr; /* : 7 */\n \tunsigned char split_nr; /* : 7 */\n \tunsigned size_size : 3;\n-\tunsigned padding : 5;\n+\tunsigned name_size : 3;\n+\tunsigned padding : 2;\n \n \tuint32_t date;\n \tuint16_t path;\n@@ -84,6 +93,7 @@ struct rc_object_entry {\n \t/* merge paths */\n \t/* split paths */\n \t/* size */\n+\t/* name id */\n };\n \n struct rc_index_entry *from_disked_rc_index_entry(struct rc_index_entry_ondisk *src, struct rc_index_entry *dst);\ndiff --git a/revision.h b/revision.h\nindex c3ec1b3..b2d5834 100644\n--- a/revision.h\n+++ b/revision.h\n@@ -23,6 +23,9 @@ struct rev_cache_slice_map {\n \tunsigned char *map;\n \tint size;\n \tint last_index;\n+\n+\tchar *names;\n+\tint name_size;\n };\n \n struct rev_cache_info {\n@@ -36,7 +39,8 @@ struct rev_cache_info {\n \tunsigned overwrite_all : 1;\n \n \t/* traversal flags */\n-\tunsigned add_to_pending : 1;\n+\tunsigned add_to_pending : 1,\n+\t\tadd_names : 1;\n \n \t/* fuse options */\n \tunsigned int ignore_size;\ndiff --git a/t/t6015-rev-cache-list.sh b/t/t6015-rev-cache-list.sh\nindex f2e34b1..3286560 100755\n--- a/t/t6015-rev-cache-list.sh\n+++ b/t/t6015-rev-cache-list.sh\n@@ -4,8 +4,10 @@ test_description='git rev-cache tests'\n . ./test-lib.sh\n \n test_cmp_sorted() {\n-\tgrep -io \"[a-f0-9]*\" $1 | sort >.tmpfile1 &&\n-\tgrep -io \"[a-f0-9]*\" $2 | sort >.tmpfile2 &&\n+# note that we're tip-toeing around the corner case of two objects/names\n+# for the same SHA-1 => discrepencies between cached and non-cached walks\n+\tsort $1 >.tmpfile1 &&\n+\tsort $2 >.tmpfile2 &&\n \ttest_cmp .tmpfile1 .tmpfile2\n }\n \n@@ -15,6 +17,8 @@ test_cmp_sorted() {\n # reuse\n test_expect_success 'init repo' '\n \techo bla >file &&\n+\tmkdir amaindir &&\n+\techo watskeburt >amaindir/file &&\n \tgit add . &&\n \tgit commit -m \"bla\" &&\n \n-- \ntg: (3e3bb6a..) t/revcache/names (depends on: t/revcache/docs)\n"},{"id":"122625","messageId":"op.uzv4cs0rtdk399@sirnot.private","threadId":"20632","inReplyTo":"op.uyzwyho5tdk399@sirnot","subject":"Re: [PATCH 6/6 (v4)] support for path name caching in rev-cache","fromName":"Nick Edelen","fromEmail":"sirnot@gmail.com","sentAt":"2009-09-07T14:11:06Z","receivedAt":"2009-09-07T14:11:06Z","isPatch":true,"sender":{"key":"sirnot@gmail.com","avatar":null},"body":"An update to caching mechanism, allowing path names to be cached for blob and \ntree objects.  A list of names appearing in each cache slice is appended to the \nend of the slice, which is referenced by variable-sized indexes per entry.  \nThis allows pack-objects to more intelligently schedule unpacked/poorly packed \nobject, and enables proper duplication of rev-list's behaivor.\n\nSigned-off-by: Nick Edelen <sirnot@gmail.com>\n\n---\n builtin-rev-cache.c       |    3 +-\n rev-cache.c               |  331 +++++++++++++++++++++++++++++++++++++--------\n rev-cache.h               |   16 ++-\n revision.h                |    6 +-\n t/t6017-rev-cache-list.sh |    8 +-\n 5 files changed, 299 insertions(+), 65 deletions(-)\n\ndiff --git a/builtin-rev-cache.c b/builtin-rev-cache.c\nindex 8f41123..4c1766d 100644\n--- a/builtin-rev-cache.c\n+++ b/builtin-rev-cache.c\n@@ -177,13 +177,14 @@ static int handle_walk(int argc, const char *argv[])\n \tfprintf(stderr, \"pending:\\n\");\n \tfor (i = 0; i < revs.pending.nr; i++) {\n \t\tstruct object *obj = revs.pending.objects[i].item;\n+\t\tconst char *name = revs.pending.objects[i].name;\n \n \t\t/* unfortunately, despite our careful generation, object duplication *is* a possibility...\n \t\t * (eg. same object introduced into two different branches) */\n \t\tif (obj->flags & SEEN)\n \t\t\tcontinue;\n \n-\t\tprintf(\"%s\\n\", sha1_to_hex(revs.pending.objects[i].item->sha1));\n+\t\tprintf(\"%s %s\\n\", sha1_to_hex(revs.pending.objects[i].item->sha1), name);\n \t\tobj->flags |= SEEN;\n \t}\n \ndiff --git a/rev-cache.c b/rev-cache.c\nindex 6becd4b..3595f66 100644\n--- a/rev-cache.c\n+++ b/rev-cache.c\n@@ -17,6 +17,14 @@ struct bad_slice {\n \tstruct bad_slice *next;\n };\n \n+struct name_list {\n+\tunsigned char sha1[20];\n+\tunsigned int len;\n+\tstruct name_list *next;\n+\n+\tchar buf[FLEX_ARRAY];\n+};\n+\n struct cache_slice_pointer {\n \tchar signature[8]; /* REVCOPTR */\n \tchar version;\n@@ -29,10 +37,13 @@ static uint32_t fanout[0xff + 2];\n static unsigned char *idx_map;\n static int idx_size;\n static struct rc_index_header idx_head;\n-static char no_idx, add_to_pending;\n-static struct bad_slice *bad_slices;\n+static char no_idx, add_to_pending, add_names;\n static unsigned char *idx_caches;\n \n+static struct bad_slice *bad_slices;\n+static struct name_list *name_lists, *cur_name_list;\n+\n+static struct strbuf *acc_name_buffer;\n static struct strbuf *acc_buffer;\n \n #define SLOP\t\t\t5\n@@ -79,7 +90,7 @@ struct rc_object_entry *from_disked_rc_object_entry(struct rc_object_entry_ondis\n \tif (!dst)\n \t\tdst = &entry[cur++ & 0x3];\n \n-\tdst->type = src->flags >> 5;\n+\tdst->type = src->flags >> 5 & 0x03;\n \tdst->is_end = !!(src->flags & 0x10);\n \tdst->is_start = !!(src->flags & 0x08);\n \tdst->uninteresting = !!(src->flags & 0x04);\n@@ -90,8 +101,9 @@ struct rc_object_entry *from_disked_rc_object_entry(struct rc_object_entry_ondis\n \tdst->merge_nr = src->merge_nr;\n \tdst->split_nr = src->split_nr;\n \n-\tdst->size_size = src->sizes >> 5;\n-\tdst->padding = src->sizes & 0x1f;\n+\tdst->size_size = src->sizes >> 5 & 0x03;\n+\tdst->name_size = src->sizes >> 2 & 0x03;\n+\tdst->padding = src->sizes & 0x02;\n \n \tdst->date = ntohl(src->date);\n \tdst->path = ntohs(src->path);\n@@ -120,6 +132,7 @@ struct rc_object_entry_ondisk *to_disked_rc_object_entry(struct rc_object_entry\n \tdst->split_nr = src->split_nr;\n \n \tdst->sizes  = (unsigned char)src->size_size << 5;\n+\tdst->sizes |= (unsigned char)src->name_size << 2;\n \tdst->sizes |= (unsigned char)src->padding;\n \n \tdst->date = htonl(src->date);\n@@ -192,6 +205,12 @@ static void cleanup_cache_slices(void)\n \t\tidx_map = 0;\n \t}\n \n+\twhile (name_lists) {\n+\t\tstruct name_list *nl = name_lists->next;\n+\t\tfree(name_lists);\n+\t\tname_lists = nl;\n+\t}\n+\n }\n \n static int init_index(void)\n@@ -324,7 +343,7 @@ static void handle_noncommit(struct rev_info *revs, struct commit *commit, unsig\n \tstruct blob *blob;\n \tstruct tree *tree;\n \tstruct object *obj;\n-\tunsigned long size;\n+\tunsigned long size, name_index;\n \n \tsize = decode_size(ptr + RC_ENTRY_SIZE_OFFSET(entry), entry->size_size);\n \tswitch (entry->type) {\n@@ -357,9 +376,22 @@ static void handle_noncommit(struct rev_info *revs, struct commit *commit, unsig\n \t\treturn;\n \t}\n \n+\tif (add_names && cur_name_list) {\n+\t\tname_index = decode_size(ptr + RC_ENTRY_NAME_OFFSET(entry), entry->name_size);\n+\n+\t\tif (name_index >= cur_name_list->len)\n+\t\t\tname_index = 0;\n+\t} else name_index = 0;\n+\n \tobj->flags |= FACE_VALUE;\n-\tif (add_to_pending)\n-\t\tadd_pending_object(revs, obj, \"\");\n+\tif (add_to_pending) {\n+\t\tchar *name = \"\";\n+\n+\t\tif (name_index)\n+\t\t\tname = cur_name_list->buf + name_index;\n+\n+\t\tadd_pending_object(revs, obj, name);\n+\t}\n }\n \n static int setup_traversal(struct rc_slice_header *head, unsigned char *map, struct commit *commit, struct commit_list **work,\n@@ -714,15 +746,44 @@ end:\n \treturn retval;\n }\n \n-static int get_cache_slice_header(unsigned char *cache_sha1, unsigned char *map, int len, struct rc_slice_header *head)\n+static struct name_list *get_cache_slice_name_list(struct rc_slice_header *head, int fd)\n+{\n+\tstruct name_list *nl = name_lists;\n+\n+\twhile (nl) {\n+\t\tif (!hashcmp(nl->sha1, head->sha1))\n+\t\t\tbreak;\n+\t\tnl = nl->next;\n+\t}\n+\n+\tif (nl)\n+\t\treturn nl;\n+\n+\tnl = xcalloc(1, sizeof(struct name_list) + head->name_size);\n+\tnl->len = head->name_size;\n+\thashcpy(nl->sha1, head->sha1);\n+\n+\tlseek(fd, head->size, SEEK_SET);\n+\tread_in_full(fd, nl->buf, head->name_size);\n+\n+\tnl->next = name_lists;\n+\tname_lists = nl;\n+\n+\treturn nl;\n+}\n+\n+static int get_cache_slice_header(int fd, unsigned char *cache_sha1, int len, struct rc_slice_header *head)\n {\n \tint t;\n \n-\tmemcpy(head, map, sizeof(struct rc_slice_header));\n+\tif (xread(fd, head, sizeof(struct rc_slice_header)) != sizeof(struct rc_slice_header))\n+\t\treturn -1;\n+\n \thead->ofs_objects = ntohl(head->ofs_objects);\n \thead->object_nr = ntohl(head->object_nr);\n \thead->size = ntohl(head->size);\n \thead->path_nr = ntohs(head->path_nr);\n+\thead->name_size = ntohl(head->name_size);\n \n \tif (memcmp(head->signature, \"REVCACHE\", 8))\n \t\treturn -1;\n@@ -731,10 +792,10 @@ static int get_cache_slice_header(unsigned char *cache_sha1, unsigned char *map,\n \tif (hashcmp(head->sha1, cache_sha1))\n \t\treturn -3;\n \tt = sizeof(struct rc_slice_header);\n-\tif (t != head->ofs_objects || t >= len)\n+\tif (t != head->ofs_objects)\n \t\treturn -4;\n-\n-\thead->size = len;\n+\tif (head->size + head->name_size != len)\n+\t\treturn -5;\n \n \treturn 0;\n }\n@@ -786,7 +847,7 @@ int traverse_cache_slice(struct rev_info *revs,\n \tunsigned long *date_so_far, int *slop_so_far,\n \tstruct commit_list ***queue, struct commit_list **work)\n {\n-\tint fd = -1, retval = -3;\n+\tint fd = -1, t, retval;\n \tstruct stat fi;\n \tstruct rc_slice_header head;\n \tstruct rev_cache_info *rci;\n@@ -802,26 +863,31 @@ int traverse_cache_slice(struct rev_info *revs,\n \t/* load options */\n \trci = &revs->rev_cache_info;\n \tadd_to_pending = rci->add_to_pending;\n+\tadd_names = rci->add_names;\n \n \tmemset(&head, 0, sizeof(struct rc_slice_header));\n+#\tdefine ERROR(x)\t\tdo { retval = (x); goto end; } while (0);\n \n \tfd = open_cache_slice(cache_sha1, O_RDONLY);\n \tif (fd == -1)\n-\t\tgoto end;\n+\t\tERROR(-1);\n \tif (fstat(fd, &fi) || fi.st_size < sizeof(struct rc_slice_header))\n-\t\tgoto end;\n+\t\tERROR(-2);\n+\n+\tif ((t = get_cache_slice_header(fd, cache_sha1, fi.st_size, &head)) < 0)\n+\t\tERROR(-t);\n+\tif (add_names)\n+\t\tcur_name_list = get_cache_slice_name_list(&head, fd);\n \n-\tmap = xmmap(0, fi.st_size, PROT_READ | PROT_WRITE, MAP_PRIVATE, fd, 0);\n+\tmap = xmmap(0, head.size, PROT_READ | PROT_WRITE, MAP_PRIVATE, fd, 0);\n \tif (map == MAP_FAILED)\n-\t\tgoto end;\n-\tif (get_cache_slice_header(cache_sha1, map, fi.st_size, &head))\n-\t\tgoto end;\n+\t\tERROR(-3);\n \n \tretval = traverse_cache_slice_1(&head, map, revs, commit, date_so_far, slop_so_far, queue, work);\n \n end:\n \tif (map != MAP_FAILED)\n-\t\tmunmap(map, fi.st_size);\n+\t\tmunmap(map, head.size);\n \tif (fd != -1)\n \t\tclose(fd);\n \n@@ -829,6 +895,7 @@ end:\n \tif (retval)\n \t\tmark_bad_slice(cache_sha1);\n \n+#\tundef ERROR\n \treturn retval;\n }\n \n@@ -1113,23 +1180,110 @@ static unsigned long decode_size(unsigned char *str, int len)\n \treturn size;\n }\n \n+\n+#define NL_HASH_TABLE_SIZE\t\t(0xffff + 1)\n+#define NL_HASH_NUMBER\t\t\t(NL_HASH_TABLE_SIZE >> 3)\n+\n+struct name_list_hash {\n+\tint ind;\n+\tstruct name_list_hash *next;\n+};\n+\n+static struct name_list_hash **nl_hash_table;\n+static unsigned char *nl_hashes;\n+\n+/* FNV-1a hash */\n+static unsigned int hash_name(const char *name)\n+{\n+\tunsigned int hash = 2166136261ul;\n+\tconst char *p = name;\n+\n+\twhile (*p) {\n+\t\thash ^= *p++;\n+\t\thash *= 16777619ul;\n+\t}\n+\n+\treturn hash & 0xffff;\n+}\n+\n+static int name_in_list(const char *name)\n+{\n+\tunsigned int h = hash_name(name);\n+\tstruct name_list_hash *entry = nl_hash_table[h];\n+\n+\twhile (entry && strcmp(acc_name_buffer->buf + entry->ind, name))\n+\t\tentry = entry->next;\n+\n+\tif (entry)\n+\t\treturn entry->ind;\n+\n+\t/* add name to buffer and create hash reference */\n+\tentry = xcalloc(1, sizeof(struct name_list_hash));\n+\tentry->ind = acc_name_buffer->len;\n+\tstrbuf_add(acc_name_buffer, name, strlen(name) + 1);\n+\n+\tentry->next = nl_hash_table[h];\n+\tnl_hash_table[h] = entry;\n+\n+\tnl_hashes[h / 8] |= h % 8;\n+\n+\treturn entry->ind;\n+}\n+\n+static void init_name_list_hash(void)\n+{\n+\tnl_hash_table = xcalloc(NL_HASH_TABLE_SIZE, sizeof(struct name_list_hash));\n+\tnl_hashes = xcalloc(NL_HASH_NUMBER, 1);\n+}\n+\n+static void cleanup_name_list_hash(void)\n+{\n+\tint i;\n+\n+\tfor (i = 0; i < NL_HASH_NUMBER; i++) {\n+\t\tint j, ind = nl_hashes[i];\n+\n+\t\tif (!ind)\n+\t\t\tcontinue;\n+\n+\t\tfor (j = 0; j < 8; j++) {\n+\t\t\tstruct name_list_hash **entryp;\n+\n+\t\t\tif (!(ind & 1 << j))\n+\t\t\t\tcontinue;\n+\n+\t\t\tentryp = &nl_hash_table[i * 8 + j];\n+\t\t\twhile (*entryp) {\n+\t\t\t\tstruct name_list_hash *t = (*entryp)->next;\n+\n+\t\t\t\tfree(*entryp);\n+\t\t\t\t*entryp = t;\n+\t\t\t}\n+\t\t}\n+\t} /* code overhang! */\n+\n+\tfree(nl_hashes);\n+\tfree(nl_hash_table);\n+}\n+\n static void add_object_entry(const unsigned char *sha1, struct rc_object_entry *entryp,\n-\tstruct strbuf *merge_str, struct strbuf *split_str)\n+\tstruct strbuf *merge_str, struct strbuf *split_str, char *name, unsigned long size)\n {\n \tstruct rc_object_entry entry;\n-\tunsigned char size_str[7];\n-\tunsigned long size;\n+\tunsigned char size_str[7], name_str[7];\n \tenum object_type type;\n \tvoid *data;\n \n \tif (entryp)\n \t\tsha1 = entryp->sha1;\n \n-\t/* retrieve size data */\n-\tdata = read_sha1_file(sha1, &type, &size);\n+\tif (!size) {\n+\t\t/* retrieve size data */\n+\t\tdata = read_sha1_file(sha1, &type, &size);\n \n-\tif (data)\n-\t\tfree(data);\n+\t\tif (data)\n+\t\t\tfree(data);\n+\t}\n \n \t/* initialize! */\n \tif (!entryp) {\n@@ -1147,6 +1301,9 @@ static void add_object_entry(const unsigned char *sha1, struct rc_object_entry *\n \n \tentryp->size_size = encode_size(size, size_str);\n \n+\tif (name)\n+\t\tentryp->name_size = encode_size(name_in_list(name), name_str);\n+\n \t/* write the muvabitch */\n \tstrbuf_add(acc_buffer, to_disked_rc_object_entry(entryp, 0), sizeof(struct rc_object_entry_ondisk));\n \n@@ -1156,25 +1313,36 @@ static void add_object_entry(const unsigned char *sha1, struct rc_object_entry *\n \t\tstrbuf_add(acc_buffer, split_str->buf, split_str->len);\n \n \tstrbuf_add(acc_buffer, size_str, entryp->size_size);\n+\n+\tif (name)\n+\t\tstrbuf_add(acc_buffer, name_str, entryp->name_size);\n }\n \n /* returns non-zero to continue parsing, 0 to skip */\n typedef int (*dump_tree_fn)(const unsigned char *, const char *, unsigned int); /* sha1, path, mode */\n \n /* we need to walk the trees by hash, so unfortunately we can't use traverse_trees in tree-walk.c */\n-static int dump_tree(struct tree *tree, dump_tree_fn fn)\n+static int dump_tree(struct tree *tree, dump_tree_fn fn, char *base)\n {\n \tstruct tree_desc desc;\n \tstruct name_entry entry;\n \tstruct tree *subtree;\n-\tint r;\n+\tchar concatpath[PATH_MAX];\n+\tint r, baselen;\n \n \tif (parse_tree(tree))\n \t\treturn -1;\n \n+\tbaselen = strlen(base);\n+\tstrcpy(concatpath, base);\n+\n \tinit_tree_desc(&desc, tree->buffer, tree->size);\n \twhile (tree_entry(&desc, &entry)) {\n-\t\tswitch (fn(entry.sha1, entry.path, entry.mode)) {\n+\t\tif (baselen + strlen(entry.path) + 1 >= PATH_MAX)\n+\t\t\tdie(\"we have a problem: %s%s is too big for me to handle\", base, entry.path);\n+\t\tstrcpy(concatpath + baselen, entry.path);\n+\n+\t\tswitch (fn(entry.sha1, concatpath, entry.mode)) {\n \t\tcase 0 :\n \t\t\tgoto continue_loop;\n \t\tdefault :\n@@ -1186,7 +1354,8 @@ static int dump_tree(struct tree *tree, dump_tree_fn fn)\n \t\t\tif (!subtree)\n \t\t\t\treturn -2;\n \n-\t\t\tif ((r = dump_tree(subtree, fn)) < 0)\n+\t\t\tstrcat(concatpath, \"/\");\n+\t\t\tif ((r = dump_tree(subtree, fn, concatpath)) < 0)\n \t\t\t\treturn r;\n \t\t}\n \n@@ -1200,6 +1369,9 @@ continue_loop:\n static int dump_tree_callback(const unsigned char *sha1, const char *path, unsigned int mode)\n {\n \tstrbuf_add(acc_buffer, sha1, 20);\n+\tstrbuf_add(acc_buffer, (char *)&acc_name_buffer->len, sizeof(size_t));\n+\n+\tstrbuf_add(acc_name_buffer, path, strlen(path) + 1);\n \n \treturn 1;\n }\n@@ -1213,6 +1385,9 @@ static void tree_addremove(struct diff_options *options,\n \t\treturn;\n \n \tstrbuf_add(acc_buffer, sha1, 20);\n+\tstrbuf_add(acc_buffer, (char *)&acc_name_buffer->len, sizeof(size_t));\n+\n+\tstrbuf_add(acc_name_buffer, concatpath, strlen(concatpath) + 1);\n }\n \n static void tree_change(struct diff_options *options,\n@@ -1225,12 +1400,15 @@ static void tree_change(struct diff_options *options,\n \t\treturn;\n \n \tstrbuf_add(acc_buffer, new_sha1, 20);\n+\tstrbuf_add(acc_buffer, (char *)&acc_name_buffer->len, sizeof(size_t));\n+\n+\tstrbuf_add(acc_name_buffer, concatpath, strlen(concatpath) + 1);\n }\n \n static int add_unique_objects(struct commit *commit)\n {\n \tstruct commit_list *list;\n-\tstruct strbuf os, ost, *orig_buf;\n+\tstruct strbuf os, ost, names, *orig_name_buf, *orig_buf;\n \tstruct diff_options opts;\n \tint i, j, next;\n \tchar is_first = 1;\n@@ -1238,13 +1416,17 @@ static int add_unique_objects(struct commit *commit)\n \t/* ...no, calculate unique objects */\n \tstrbuf_init(&os, 0);\n \tstrbuf_init(&ost, 0);\n+\tstrbuf_init(&names, 0);\n \torig_buf = acc_buffer;\n+\torig_name_buf = acc_name_buffer;\n+\tacc_name_buffer = &names;\n \n \tdiff_setup(&opts);\n \tDIFF_OPT_SET(&opts, RECURSIVE);\n \tDIFF_OPT_SET(&opts, TREE_IN_RECURSIVE);\n \topts.change = tree_change;\n \topts.add_remove = tree_addremove;\n+#\tdefine ENTRY_SIZE (20 + sizeof(size_t))\n \n \t/* this is only called for non-ends (ie. all parents interesting) */\n \tfor (list = commit->parents; list; list = list->next) {\n@@ -1255,20 +1437,20 @@ static int add_unique_objects(struct commit *commit)\n \n \t\tstrbuf_setlen(acc_buffer, 0);\n \t\tdiff_tree_sha1(list->item->tree->object.sha1, commit->tree->object.sha1, \"\", &opts);\n-\t\tqsort(acc_buffer->buf, acc_buffer->len / 20, 20, (int (*)(const void *, const void *))hashcmp);\n+\t\tqsort(acc_buffer->buf, acc_buffer->len / ENTRY_SIZE, ENTRY_SIZE, (int (*)(const void *, const void *))hashcmp);\n \n \t\t/* take intersection */\n \t\tif (!is_first) {\n-\t\t\tfor (next = i = j = 0; i < os.len; i += 20) {\n+\t\t\tfor (next = i = j = 0; i < os.len; i += ENTRY_SIZE) {\n \t\t\t\twhile (j < ost.len && hashcmp((unsigned char *)(ost.buf + j), (unsigned char *)(os.buf + i)) < 0)\n-\t\t\t\t\tj += 20;\n+\t\t\t\t\tj += ENTRY_SIZE;\n \n \t\t\t\tif (j >= ost.len || hashcmp((unsigned char *)(ost.buf + j), (unsigned char *)(os.buf + i)))\n \t\t\t\t\tcontinue;\n \n \t\t\t\tif (next != i)\n-\t\t\t\t\tmemcpy(os.buf + next, os.buf + i, 20);\n-\t\t\t\tnext += 20;\n+\t\t\t\t\tmemcpy(os.buf + next, os.buf + i, ENTRY_SIZE);\n+\t\t\t\tnext += ENTRY_SIZE;\n \t\t\t}\n \n \t\t\tif (next != i)\n@@ -1280,29 +1462,37 @@ static int add_unique_objects(struct commit *commit)\n \t/* no parents (!) */\n \tif (is_first) {\n \t\tacc_buffer = &os;\n-\t\tdump_tree(commit->tree, dump_tree_callback);\n+\t\tdump_tree(commit->tree, dump_tree_callback, \"\");\n \t}\n \n \t/* the ordering of non-commit objects dosn't really matter, so we're not gonna bother */\n \tacc_buffer = orig_buf;\n-\tfor (i = 0; i < os.len; i += 20)\n-\t\tadd_object_entry((unsigned char *)(os.buf + i), 0, 0, 0);\n+\tacc_name_buffer = orig_name_buf;\n+\tfor (i = 0; i < os.len; i += ENTRY_SIZE)\n+\t\tadd_object_entry((unsigned char *)(os.buf + i), 0, 0, 0, names.buf + *(size_t *)(os.buf + i + 20), 0);\n \n \t/* last but not least, the main tree */\n-\tadd_object_entry(commit->tree->object.sha1, 0, 0, 0);\n+\tadd_object_entry(commit->tree->object.sha1, 0, 0, 0, 0, 0);\n \n-\treturn i / 20 + 1;\n+\tstrbuf_release(&ost);\n+\tstrbuf_release(&os);\n+\tstrbuf_release(&names);\n+\n+\treturn i / ENTRY_SIZE + 1;\n+#\tundef ENTRY_SIZE\n }\n \n static int add_objects_verbatim_1(struct rev_cache_slice_map *mapping, int *index)\n {\n-\tunsigned char *map = mapping->map;\n \tint i = *index, object_nr = 0;\n+\tunsigned char *map = mapping->map;\n \tstruct rc_object_entry *entry = RC_OBTAIN_OBJECT_ENTRY(map + i);\n+\tunsigned long size;\n \n \ti += RC_ACTUAL_OBJECT_ENTRY_SIZE(entry);\n \twhile (i < mapping->size) {\n-\t\tint pos = i;\n+\t\tchar *name;\n+\t\tint name_index, pos = i;\n \n \t\tentry = RC_OBTAIN_OBJECT_ENTRY(map + i);\n \t\ti += RC_ACTUAL_OBJECT_ENTRY_SIZE(entry);\n@@ -1312,7 +1502,15 @@ static int add_objects_verbatim_1(struct rev_cache_slice_map *mapping, int *inde\n \t\t\treturn object_nr;\n \t\t}\n \n-\t\tstrbuf_add(acc_buffer, map + pos, i - pos);\n+\t\tname_index = decode_size(map + pos + RC_ENTRY_NAME_OFFSET(entry), entry->name_size);\n+\t\tif (name_index && name_index < mapping->name_size)\n+\t\t\tname = mapping->names + name_index;\n+\t\telse\n+\t\t\tname = 0;\n+\n+\t\tsize = decode_size(map + pos + RC_ENTRY_SIZE_OFFSET(entry), entry->size_size);\n+\n+\t\tadd_object_entry(0, entry, 0, 0, name, size);\n \t\tobject_nr++;\n \t}\n \n@@ -1397,6 +1595,7 @@ void init_rev_cache_info(struct rev_cache_info *rci)\n \trci->overwrite_all = 0;\n \n \trci->add_to_pending = 1;\n+\trci->add_names = 1;\n \n \trci->ignore_size = 0;\n }\n@@ -1421,9 +1620,9 @@ int make_cache_slice(struct rev_cache_info *rci,\n \tstruct rc_slice_header head;\n \tstruct commit *commit;\n \tunsigned char sha1[20];\n-\tstruct strbuf merge_paths, split_paths;\n+\tstruct strbuf merge_paths, split_paths, namelist;\n \tint object_nr, total_sz, fd;\n-\tchar file[PATH_MAX], *newfile;\n+\tchar file[PATH_MAX], null, *newfile;\n \tstruct rev_cache_info *trci;\n \tgit_SHA_CTX ctx;\n \n@@ -1438,7 +1637,13 @@ int make_cache_slice(struct rev_cache_info *rci,\n \tstrbuf_init(&endlist, 0);\n \tstrbuf_init(&merge_paths, 0);\n \tstrbuf_init(&split_paths, 0);\n+\tstrbuf_init(&namelist, 0);\n \tacc_buffer = &buffer;\n+\tacc_name_buffer = &namelist;\n+\n+\tnull = 0;\n+\tstrbuf_add(&namelist, &null, 1);\n+\tinit_name_list_hash();\n \n \tif (!revs) {\n \t\trevs = &therevs;\n@@ -1469,6 +1674,7 @@ int make_cache_slice(struct rev_cache_info *rci,\n \ttrci = &revs->rev_cache_info;\n \tinit_rev_cache_info(trci);\n \ttrci->add_to_pending = 0;\n+\ttrci->add_names = 0;\n \n \tsetup_revisions(0, 0, revs, 0);\n \tif (prepare_revision_walk(revs))\n@@ -1506,7 +1712,7 @@ int make_cache_slice(struct rev_cache_info *rci,\n \n \t\tcommit->indegree = 0;\n \n-\t\tadd_object_entry(0, &object, &merge_paths, &split_paths);\n+\t\tadd_object_entry(0, &object, &merge_paths, &split_paths, 0, 0);\n \t\tobject_nr++;\n \n \t\tif (rci->objects && !object.is_end) {\n@@ -1532,10 +1738,16 @@ int make_cache_slice(struct rev_cache_info *rci,\n \t\ttotal_sz += buffer.len;\n \t}\n \n+\t/* write path name lookup list */\n+\thead.name_size = htonl(namelist.len);\n+\twrite_in_full(fd, namelist.buf, namelist.len);\n+\n \t/* go ahead a free some stuff... */\n \tstrbuf_release(&buffer);\n \tstrbuf_release(&merge_paths);\n \tstrbuf_release(&split_paths);\n+\tstrbuf_release(&namelist);\n+\tcleanup_name_list_hash();\n \tif (path_sz)\n \t\tfree(paths);\n \twhile (path_track_alloc)\n@@ -1993,6 +2205,7 @@ int fuse_cache_slices(struct rev_cache_info *rci, struct rev_info *revs)\n \tfor (i = idx_head.cache_nr - 1; i >= 0; i--) {\n \t\tstruct rev_cache_slice_map *map = rci->maps + i;\n \t\tstruct stat fi;\n+\t\tstruct rc_slice_header head;\n \t\tint fd;\n \n \t\tif (!map->size)\n@@ -2005,13 +2218,20 @@ int fuse_cache_slices(struct rev_cache_info *rci, struct rev_info *revs)\n \t\t\tcontinue;\n \t\tif (fi.st_size < sizeof(struct rc_slice_header))\n \t\t\tcontinue;\n+\t\tif (get_cache_slice_header(fd, idx_caches + i * 20, fi.st_size, &head))\n+\t\t\tcontinue;\n \n-\t\tmap->map = xmmap(0, fi.st_size, PROT_READ, MAP_PRIVATE, fd, 0);\n+\t\tmap->map = xmmap(0, head.size, PROT_READ, MAP_PRIVATE, fd, 0);\n \t\tif (map->map == MAP_FAILED)\n \t\t\tcontinue;\n \n+\t\tlseek(fd, head.size, SEEK_SET);\n+\t\tmap->names = xcalloc(head.name_size, 1);\n+\t\tread_in_full(fd, map->names, head.name_size);\n+\n \t\tclose(fd);\n-\t\tmap->size = fi.st_size;\n+\t\tmap->size = head.size;\n+\t\tmap->name_size = head.name_size;\n \t}\n \n \trci->make_index = 0;\n@@ -2028,6 +2248,7 @@ int fuse_cache_slices(struct rev_cache_info *rci, struct rev_info *revs)\n \t\tif (!map->size)\n \t\t\tcontinue;\n \n+\t\tfree(map->names);\n \t\tmunmap(map->map, map->size);\n \t}\n \tfree(rci->maps);\n@@ -2049,7 +2270,6 @@ static int verify_cache_slice(const char *slice_path, unsigned char *sha1)\n {\n \tstruct rc_slice_header head;\n \tint fd, len, retval = -1;\n-\tunsigned char *map = MAP_FAILED;\n \tstruct stat fi;\n \n \tlen = strlen(slice_path);\n@@ -2064,17 +2284,12 @@ static int verify_cache_slice(const char *slice_path, unsigned char *sha1)\n \tif (fstat(fd, &fi) || fi.st_size < sizeof(head))\n \t\tgoto end;\n \n-\tmap = xmmap(0, sizeof(head), PROT_READ, MAP_PRIVATE, fd, 0);\n-\tif (map == MAP_FAILED)\n-\t\tgoto end;\n-\tif (get_cache_slice_header(sha1, map, fi.st_size, &head))\n+\tif (get_cache_slice_header(fd, sha1, fi.st_size, &head))\n \t\tgoto end;\n \n \tretval = 0;\n \n end:\n-\tif (map != MAP_FAILED)\n-\t\tmunmap(map, sizeof(head));\n \tif (fd > 0)\n \t\tclose(fd);\n \ndiff --git a/rev-cache.h b/rev-cache.h\nindex 14437d8..c88ceae 100644\n--- a/rev-cache.h\n+++ b/rev-cache.h\n@@ -10,8 +10,14 @@\n #define RC_OBTAIN_OBJECT_ENTRY(p)\t\t\tfrom_disked_rc_object_entry((struct rc_object_entry_ondisk *)(p), 0)\n #define RC_OBTAIN_INDEX_ENTRY(p)\t\t\tfrom_disked_rc_index_entry((struct rc_index_entry_ondisk *)(p), 0)\n \n-#define RC_ACTUAL_OBJECT_ENTRY_SIZE(e)\t\t(sizeof(struct rc_object_entry_ondisk) + RC_PATH_SIZE((e)->merge_nr + (e)->split_nr) + (e)->size_size)\n-#define RC_ENTRY_SIZE_OFFSET(e)\t\t\t\t(RC_ACTUAL_OBJECT_ENTRY_SIZE(e) - (e)->size_size)\n+#define RC_ACTUAL_OBJECT_ENTRY_SIZE(e)\t(\\\n+\tsizeof(struct rc_object_entry_ondisk) + \\\n+\tRC_PATH_SIZE((e)->merge_nr + (e)->split_nr) + \\\n+\t(e)->size_size + \\\n+\t(e)->name_size\\\n+)\n+#define RC_ENTRY_SIZE_OFFSET(e)\t\t\t(RC_ACTUAL_OBJECT_ENTRY_SIZE(e) - (e)->name_size - (e)->size_size)\n+#define RC_ENTRY_NAME_OFFSET(e)\t\t\t(RC_ACTUAL_OBJECT_ENTRY_SIZE(e) - (e)->name_size)\n \n /* single index maps objects to cache files */\n struct rc_index_header {\n@@ -50,6 +56,8 @@ struct rc_slice_header {\n \tuint32_t size;\n \n \tunsigned char sha1[20];\n+\n+\tuint32_t name_size;\n };\n \n struct rc_object_entry_ondisk {\n@@ -76,7 +84,8 @@ struct rc_object_entry {\n \tunsigned char merge_nr; /* : 7 */\n \tunsigned char split_nr; /* : 7 */\n \tunsigned size_size : 3;\n-\tunsigned padding : 5;\n+\tunsigned name_size : 3;\n+\tunsigned padding : 2;\n \n \tuint32_t date;\n \tuint16_t path;\n@@ -84,6 +93,7 @@ struct rc_object_entry {\n \t/* merge paths */\n \t/* split paths */\n \t/* size */\n+\t/* name id */\n };\n \n struct rc_index_entry *from_disked_rc_index_entry(struct rc_index_entry_ondisk *src, struct rc_index_entry *dst);\ndiff --git a/revision.h b/revision.h\nindex cc5c259..c62e85b 100644\n--- a/revision.h\n+++ b/revision.h\n@@ -26,6 +26,9 @@ struct rev_cache_slice_map {\n \tunsigned char *map;\n \tint size;\n \tint last_index;\n+\n+\tchar *names;\n+\tint name_size;\n };\n \n struct rev_cache_info {\n@@ -39,7 +42,8 @@ struct rev_cache_info {\n \tunsigned overwrite_all : 1;\n \n \t/* traversal flags */\n-\tunsigned add_to_pending : 1;\n+\tunsigned add_to_pending : 1,\n+\t\tadd_names : 1;\n \n \t/* fuse options */\n \tunsigned int ignore_size;\ndiff --git a/t/t6017-rev-cache-list.sh b/t/t6017-rev-cache-list.sh\nindex f2e34b1..3286560 100755\n--- a/t/t6017-rev-cache-list.sh\n+++ b/t/t6017-rev-cache-list.sh\n@@ -4,8 +4,10 @@ test_description='git rev-cache tests'\n . ./test-lib.sh\n \n test_cmp_sorted() {\n-\tgrep -io \"[a-f0-9]*\" $1 | sort >.tmpfile1 &&\n-\tgrep -io \"[a-f0-9]*\" $2 | sort >.tmpfile2 &&\n+# note that we're tip-toeing around the corner case of two objects/names\n+# for the same SHA-1 => discrepencies between cached and non-cached walks\n+\tsort $1 >.tmpfile1 &&\n+\tsort $2 >.tmpfile2 &&\n \ttest_cmp .tmpfile1 .tmpfile2\n }\n \n@@ -15,6 +17,8 @@ test_cmp_sorted() {\n # reuse\n test_expect_success 'init repo' '\n \techo bla >file &&\n+\tmkdir amaindir &&\n+\techo watskeburt >amaindir/file &&\n \tgit add . &&\n \tgit commit -m \"bla\" &&\n \n-- \ntg: (716470e..) t/revcache/names (depends on: t/revcache/docs)\n"},{"id":"124155","messageId":"op.u061bmq1tdk399@sirnot.ed.ac.uk","threadId":"20632","inReplyTo":"op.uyuwkwjotdk399@sirnot.private","subject":"Re: [PATCH 6/6 (v4)] support for path name caching in rev-cache","fromName":"Nick Edelen","fromEmail":"sirnot@gmail.com","sentAt":"2009-10-02T22:12:48Z","receivedAt":"2009-10-02T22:12:48Z","isPatch":true,"sender":{"key":"sirnot@gmail.com","avatar":null},"body":"An update to caching mechanism, allowing path names to be cached for blob and\ntree objects.  A list of names appearing in each cache slice is appended to the\nend of the slice, which is referenced by variable-sized indexes per entry.\nThis allows pack-objects to more intelligently schedule unpacked/poorly packed\nobject, and enables proper duplication of rev-list's behaivor.\n\nSigned-off-by: Nick Edelen <sirnot@gmail.com>\n\n---\n  builtin-rev-cache.c       |    3 +-\n  rev-cache.c               |  332 +++++++++++++++++++++++++++++++++++++--------\n  rev-cache.h               |   16 ++-\n  revision.h                |    6 +-\n  t/t6017-rev-cache-list.sh |    8 +-\n  5 files changed, 300 insertions(+), 65 deletions(-)\n\ndiff --git a/builtin-rev-cache.c b/builtin-rev-cache.c\nindex 8f41123..4c1766d 100644\n--- a/builtin-rev-cache.c\n+++ b/builtin-rev-cache.c\n@@ -177,13 +177,14 @@ static int handle_walk(int argc, const char *argv[])\n  \tfprintf(stderr, \"pending:\\n\");\n  \tfor (i = 0; i < revs.pending.nr; i++) {\n  \t\tstruct object *obj = revs.pending.objects[i].item;\n+\t\tconst char *name = revs.pending.objects[i].name;\n\n  \t\t/* unfortunately, despite our careful generation, object duplication *is* a possibility...\n  \t\t * (eg. same object introduced into two different branches) */\n  \t\tif (obj->flags & SEEN)\n  \t\t\tcontinue;\n\n-\t\tprintf(\"%s\\n\", sha1_to_hex(revs.pending.objects[i].item->sha1));\n+\t\tprintf(\"%s %s\\n\", sha1_to_hex(revs.pending.objects[i].item->sha1), name);\n  \t\tobj->flags |= SEEN;\n  \t}\n\ndiff --git a/rev-cache.c b/rev-cache.c\nindex 4ef5287..6c96297 100644\n--- a/rev-cache.c\n+++ b/rev-cache.c\n@@ -17,6 +17,14 @@ struct bad_slice {\n  \tstruct bad_slice *next;\n  };\n\n+struct name_list {\n+\tunsigned char sha1[20];\n+\tunsigned int len;\n+\tstruct name_list *next;\n+\n+\tchar buf[FLEX_ARRAY];\n+};\n+\n  struct cache_slice_pointer {\n  \tchar signature[8]; /* REVCOPTR */\n  \tchar version;\n@@ -29,10 +37,13 @@ static uint32_t fanout[0xff + 2];\n  static unsigned char *idx_map;\n  static int idx_size;\n  static struct rc_index_header idx_head;\n-static char no_idx, add_to_pending;\n-static struct bad_slice *bad_slices;\n+static char no_idx, add_to_pending, add_names;\n  static unsigned char *idx_caches;\n\n+static struct bad_slice *bad_slices;\n+static struct name_list *name_lists, *cur_name_list;\n+\n+static struct strbuf *acc_name_buffer;\n  static struct strbuf *acc_buffer;\n\n  #define SLOP\t\t\t5\n@@ -79,7 +90,7 @@ struct rc_object_entry *from_disked_rc_object_entry(struct rc_object_entry_ondis\n  \tif (!dst)\n  \t\tdst = &entry[cur++ & 0x3];\n\n-\tdst->type = src->flags >> 5;\n+\tdst->type = src->flags >> 5 & 0x03;\n  \tdst->is_end = !!(src->flags & 0x10);\n  \tdst->is_start = !!(src->flags & 0x08);\n  \tdst->uninteresting = !!(src->flags & 0x04);\n@@ -90,8 +101,9 @@ struct rc_object_entry *from_disked_rc_object_entry(struct rc_object_entry_ondis\n  \tdst->merge_nr = src->merge_nr;\n  \tdst->split_nr = src->split_nr;\n\n-\tdst->size_size = src->sizes >> 5;\n-\tdst->padding = src->sizes & 0x1f;\n+\tdst->size_size = src->sizes >> 5 & 0x03;\n+\tdst->name_size = src->sizes >> 2 & 0x03;\n+\tdst->padding = src->sizes & 0x02;\n\n  \tdst->date = ntohl(src->date);\n  \tdst->path = ntohs(src->path);\n@@ -120,6 +132,7 @@ struct rc_object_entry_ondisk *to_disked_rc_object_entry(struct rc_object_entry\n  \tdst->split_nr = src->split_nr;\n\n  \tdst->sizes  = (unsigned char)src->size_size << 5;\n+\tdst->sizes |= (unsigned char)src->name_size << 2;\n  \tdst->sizes |= (unsigned char)src->padding;\n\n  \tdst->date = htonl(src->date);\n@@ -192,6 +205,12 @@ static void cleanup_cache_slices(void)\n  \t\tidx_map = 0;\n  \t}\n\n+\twhile (name_lists) {\n+\t\tstruct name_list *nl = name_lists->next;\n+\t\tfree(name_lists);\n+\t\tname_lists = nl;\n+\t}\n+\n  }\n\n  static int init_index(void)\n@@ -324,7 +343,7 @@ static void handle_noncommit(struct rev_info *revs, struct commit *commit, unsig\n  \tstruct blob *blob;\n  \tstruct tree *tree;\n  \tstruct object *obj;\n-\tunsigned long size;\n+\tunsigned long size, name_index;\n\n  \tsize = decode_size(ptr + RC_ENTRY_SIZE_OFFSET(entry), entry->size_size);\n  \tswitch (entry->type) {\n@@ -357,9 +376,23 @@ static void handle_noncommit(struct rev_info *revs, struct commit *commit, unsig\n  \t\treturn;\n  \t}\n\n+\tif (add_names && cur_name_list) {\n+\t\tname_index = decode_size(ptr + RC_ENTRY_NAME_OFFSET(entry), entry->name_size);\n+\n+\t\tif (name_index >= cur_name_list->len)\n+\t\t\tname_index = 0;\n+\t} else\n+\t\tname_index = 0;\n+\n  \tobj->flags |= FACE_VALUE;\n-\tif (add_to_pending)\n-\t\tadd_pending_object(revs, obj, \"\");\n+\tif (add_to_pending) {\n+\t\tchar *name = \"\";\n+\n+\t\tif (name_index)\n+\t\t\tname = cur_name_list->buf + name_index;\n+\n+\t\tadd_pending_object(revs, obj, name);\n+\t}\n  }\n\n  static int setup_traversal(struct rc_slice_header *head, unsigned char *map, struct commit *commit, struct commit_list **work,\n@@ -713,15 +746,44 @@ end:\n  \treturn retval;\n  }\n\n-static int get_cache_slice_header(unsigned char *cache_sha1, unsigned char *map, int len, struct rc_slice_header *head)\n+static struct name_list *get_cache_slice_name_list(struct rc_slice_header *head, int fd)\n+{\n+\tstruct name_list *nl = name_lists;\n+\n+\twhile (nl) {\n+\t\tif (!hashcmp(nl->sha1, head->sha1))\n+\t\t\tbreak;\n+\t\tnl = nl->next;\n+\t}\n+\n+\tif (nl)\n+\t\treturn nl;\n+\n+\tnl = xcalloc(1, sizeof(struct name_list) + head->name_size);\n+\tnl->len = head->name_size;\n+\thashcpy(nl->sha1, head->sha1);\n+\n+\tlseek(fd, head->size, SEEK_SET);\n+\tread_in_full(fd, nl->buf, head->name_size);\n+\n+\tnl->next = name_lists;\n+\tname_lists = nl;\n+\n+\treturn nl;\n+}\n+\n+static int get_cache_slice_header(int fd, unsigned char *cache_sha1, int len, struct rc_slice_header *head)\n  {\n  \tint t;\n\n-\tmemcpy(head, map, sizeof(struct rc_slice_header));\n+\tif (xread(fd, head, sizeof(struct rc_slice_header)) != sizeof(struct rc_slice_header))\n+\t\treturn -1;\n+\n  \thead->ofs_objects = ntohl(head->ofs_objects);\n  \thead->object_nr = ntohl(head->object_nr);\n  \thead->size = ntohl(head->size);\n  \thead->path_nr = ntohs(head->path_nr);\n+\thead->name_size = ntohl(head->name_size);\n\n  \tif (memcmp(head->signature, \"REVCACHE\", 8))\n  \t\treturn -1;\n@@ -730,10 +792,10 @@ static int get_cache_slice_header(unsigned char *cache_sha1, unsigned char *map,\n  \tif (hashcmp(head->sha1, cache_sha1))\n  \t\treturn -3;\n  \tt = sizeof(struct rc_slice_header);\n-\tif (t != head->ofs_objects || t >= len)\n+\tif (t != head->ofs_objects)\n  \t\treturn -4;\n-\n-\thead->size = len;\n+\tif (head->size + head->name_size != len)\n+\t\treturn -5;\n\n  \treturn 0;\n  }\n@@ -785,7 +847,7 @@ int traverse_cache_slice(struct rev_info *revs,\n  \tunsigned long *date_so_far, int *slop_so_far,\n  \tstruct commit_list ***queue, struct commit_list **work)\n  {\n-\tint fd = -1, retval = -3;\n+\tint fd = -1, t, retval;\n  \tstruct stat fi;\n  \tstruct rc_slice_header head;\n  \tstruct rev_cache_info *rci;\n@@ -801,26 +863,31 @@ int traverse_cache_slice(struct rev_info *revs,\n  \t/* load options */\n  \trci = &revs->rev_cache_info;\n  \tadd_to_pending = rci->add_to_pending;\n+\tadd_names = rci->add_names;\n\n  \tmemset(&head, 0, sizeof(struct rc_slice_header));\n+#\tdefine ERROR(x)\t\tdo { retval = (x); goto end; } while (0);\n\n  \tfd = open_cache_slice(cache_sha1, O_RDONLY);\n  \tif (fd == -1)\n-\t\tgoto end;\n+\t\tERROR(-1);\n  \tif (fstat(fd, &fi) || fi.st_size < sizeof(struct rc_slice_header))\n-\t\tgoto end;\n+\t\tERROR(-2);\n+\n+\tif ((t = get_cache_slice_header(fd, cache_sha1, fi.st_size, &head)) < 0)\n+\t\tERROR(-t);\n+\tif (add_names)\n+\t\tcur_name_list = get_cache_slice_name_list(&head, fd);\n\n-\tmap = xmmap(0, fi.st_size, PROT_READ | PROT_WRITE, MAP_PRIVATE, fd, 0);\n+\tmap = xmmap(0, head.size, PROT_READ | PROT_WRITE, MAP_PRIVATE, fd, 0);\n  \tif (map == MAP_FAILED)\n-\t\tgoto end;\n-\tif (get_cache_slice_header(cache_sha1, map, fi.st_size, &head))\n-\t\tgoto end;\n+\t\tERROR(-3);\n\n  \tretval = traverse_cache_slice_1(&head, map, revs, commit, date_so_far, slop_so_far, queue, work);\n\n  end:\n  \tif (map != MAP_FAILED)\n-\t\tmunmap(map, fi.st_size);\n+\t\tmunmap(map, head.size);\n  \tif (fd != -1)\n  \t\tclose(fd);\n\n@@ -828,6 +895,7 @@ end:\n  \tif (retval)\n  \t\tmark_bad_slice(cache_sha1);\n\n+#\tundef ERROR\n  \treturn retval;\n  }\n\n@@ -1112,23 +1180,110 @@ static unsigned long decode_size(unsigned char *str, int len)\n  \treturn size;\n  }\n\n+\n+#define NL_HASH_TABLE_SIZE\t\t(0xffff + 1)\n+#define NL_HASH_NUMBER\t\t\t(NL_HASH_TABLE_SIZE >> 3)\n+\n+struct name_list_hash {\n+\tint ind;\n+\tstruct name_list_hash *next;\n+};\n+\n+static struct name_list_hash **nl_hash_table;\n+static unsigned char *nl_hashes;\n+\n+/* FNV-1a hash */\n+static unsigned int hash_name(const char *name)\n+{\n+\tunsigned int hash = 2166136261ul;\n+\tconst char *p = name;\n+\n+\twhile (*p) {\n+\t\thash ^= *p++;\n+\t\thash *= 16777619ul;\n+\t}\n+\n+\treturn hash & 0xffff;\n+}\n+\n+static int name_in_list(const char *name)\n+{\n+\tunsigned int h = hash_name(name);\n+\tstruct name_list_hash *entry = nl_hash_table[h];\n+\n+\twhile (entry && strcmp(acc_name_buffer->buf + entry->ind, name))\n+\t\tentry = entry->next;\n+\n+\tif (entry)\n+\t\treturn entry->ind;\n+\n+\t/* add name to buffer and create hash reference */\n+\tentry = xcalloc(1, sizeof(struct name_list_hash));\n+\tentry->ind = acc_name_buffer->len;\n+\tstrbuf_add(acc_name_buffer, name, strlen(name) + 1);\n+\n+\tentry->next = nl_hash_table[h];\n+\tnl_hash_table[h] = entry;\n+\n+\tnl_hashes[h / 8] |= h % 8;\n+\n+\treturn entry->ind;\n+}\n+\n+static void init_name_list_hash(void)\n+{\n+\tnl_hash_table = xcalloc(NL_HASH_TABLE_SIZE, sizeof(struct name_list_hash));\n+\tnl_hashes = xcalloc(NL_HASH_NUMBER, 1);\n+}\n+\n+static void cleanup_name_list_hash(void)\n+{\n+\tint i;\n+\n+\tfor (i = 0; i < NL_HASH_NUMBER; i++) {\n+\t\tint j, ind = nl_hashes[i];\n+\n+\t\tif (!ind)\n+\t\t\tcontinue;\n+\n+\t\tfor (j = 0; j < 8; j++) {\n+\t\t\tstruct name_list_hash **entryp;\n+\n+\t\t\tif (!(ind & 1 << j))\n+\t\t\t\tcontinue;\n+\n+\t\t\tentryp = &nl_hash_table[i * 8 + j];\n+\t\t\twhile (*entryp) {\n+\t\t\t\tstruct name_list_hash *t = (*entryp)->next;\n+\n+\t\t\t\tfree(*entryp);\n+\t\t\t\t*entryp = t;\n+\t\t\t}\n+\t\t}\n+\t} /* code overhang! */\n+\n+\tfree(nl_hashes);\n+\tfree(nl_hash_table);\n+}\n+\n  static void add_object_entry(const unsigned char *sha1, struct rc_object_entry *entryp,\n-\tstruct strbuf *merge_str, struct strbuf *split_str)\n+\tstruct strbuf *merge_str, struct strbuf *split_str, char *name, unsigned long size)\n  {\n  \tstruct rc_object_entry entry;\n-\tunsigned char size_str[7];\n-\tunsigned long size;\n+\tunsigned char size_str[7], name_str[7];\n  \tenum object_type type;\n  \tvoid *data;\n\n  \tif (entryp)\n  \t\tsha1 = entryp->sha1;\n\n-\t/* retrieve size data */\n-\tdata = read_sha1_file(sha1, &type, &size);\n+\tif (!size) {\n+\t\t/* retrieve size data */\n+\t\tdata = read_sha1_file(sha1, &type, &size);\n\n-\tif (data)\n-\t\tfree(data);\n+\t\tif (data)\n+\t\t\tfree(data);\n+\t}\n\n  \t/* initialize! */\n  \tif (!entryp) {\n@@ -1146,6 +1301,9 @@ static void add_object_entry(const unsigned char *sha1, struct rc_object_entry *\n\n  \tentryp->size_size = encode_size(size, size_str);\n\n+\tif (name)\n+\t\tentryp->name_size = encode_size(name_in_list(name), name_str);\n+\n  \t/* write the muvabitch */\n  \tstrbuf_add(acc_buffer, to_disked_rc_object_entry(entryp, 0), sizeof(struct rc_object_entry_ondisk));\n\n@@ -1155,25 +1313,36 @@ static void add_object_entry(const unsigned char *sha1, struct rc_object_entry *\n  \t\tstrbuf_add(acc_buffer, split_str->buf, split_str->len);\n\n  \tstrbuf_add(acc_buffer, size_str, entryp->size_size);\n+\n+\tif (name)\n+\t\tstrbuf_add(acc_buffer, name_str, entryp->name_size);\n  }\n\n  /* returns non-zero to continue parsing, 0 to skip */\n  typedef int (*dump_tree_fn)(const unsigned char *, const char *, unsigned int); /* sha1, path, mode */\n\n  /* we need to walk the trees by hash, so unfortunately we can't use traverse_trees in tree-walk.c */\n-static int dump_tree(struct tree *tree, dump_tree_fn fn)\n+static int dump_tree(struct tree *tree, dump_tree_fn fn, char *base)\n  {\n  \tstruct tree_desc desc;\n  \tstruct name_entry entry;\n  \tstruct tree *subtree;\n-\tint r;\n+\tchar concatpath[PATH_MAX];\n+\tint r, baselen;\n\n  \tif (parse_tree(tree))\n  \t\treturn -1;\n\n+\tbaselen = strlen(base);\n+\tstrcpy(concatpath, base);\n+\n  \tinit_tree_desc(&desc, tree->buffer, tree->size);\n  \twhile (tree_entry(&desc, &entry)) {\n-\t\tswitch (fn(entry.sha1, entry.path, entry.mode)) {\n+\t\tif (baselen + strlen(entry.path) + 1 >= PATH_MAX)\n+\t\t\tdie(\"we have a problem: %s%s is too big for me to handle\", base, entry.path);\n+\t\tstrcpy(concatpath + baselen, entry.path);\n+\n+\t\tswitch (fn(entry.sha1, concatpath, entry.mode)) {\n  \t\tcase 0:\n  \t\t\tgoto continue_loop;\n  \t\tdefault:\n@@ -1185,7 +1354,8 @@ static int dump_tree(struct tree *tree, dump_tree_fn fn)\n  \t\t\tif (!subtree)\n  \t\t\t\treturn -2;\n\n-\t\t\tif ((r = dump_tree(subtree, fn)) < 0)\n+\t\t\tstrcat(concatpath, \"/\");\n+\t\t\tif ((r = dump_tree(subtree, fn, concatpath)) < 0)\n  \t\t\t\treturn r;\n  \t\t}\n\n@@ -1199,6 +1369,9 @@ continue_loop:\n  static int dump_tree_callback(const unsigned char *sha1, const char *path, unsigned int mode)\n  {\n  \tstrbuf_add(acc_buffer, sha1, 20);\n+\tstrbuf_add(acc_buffer, (char *)&acc_name_buffer->len, sizeof(size_t));\n+\n+\tstrbuf_add(acc_name_buffer, path, strlen(path) + 1);\n\n  \treturn 1;\n  }\n@@ -1212,6 +1385,9 @@ static void tree_addremove(struct diff_options *options,\n  \t\treturn;\n\n  \tstrbuf_add(acc_buffer, sha1, 20);\n+\tstrbuf_add(acc_buffer, (char *)&acc_name_buffer->len, sizeof(size_t));\n+\n+\tstrbuf_add(acc_name_buffer, concatpath, strlen(concatpath) + 1);\n  }\n\n  static void tree_change(struct diff_options *options,\n@@ -1224,12 +1400,15 @@ static void tree_change(struct diff_options *options,\n  \t\treturn;\n\n  \tstrbuf_add(acc_buffer, new_sha1, 20);\n+\tstrbuf_add(acc_buffer, (char *)&acc_name_buffer->len, sizeof(size_t));\n+\n+\tstrbuf_add(acc_name_buffer, concatpath, strlen(concatpath) + 1);\n  }\n\n  static int add_unique_objects(struct commit *commit)\n  {\n  \tstruct commit_list *list;\n-\tstruct strbuf os, ost, *orig_buf;\n+\tstruct strbuf os, ost, names, *orig_name_buf, *orig_buf;\n  \tstruct diff_options opts;\n  \tint i, j, next;\n  \tchar is_first = 1;\n@@ -1237,13 +1416,17 @@ static int add_unique_objects(struct commit *commit)\n  \t/* ...no, calculate unique objects */\n  \tstrbuf_init(&os, 0);\n  \tstrbuf_init(&ost, 0);\n+\tstrbuf_init(&names, 0);\n  \torig_buf = acc_buffer;\n+\torig_name_buf = acc_name_buffer;\n+\tacc_name_buffer = &names;\n\n  \tdiff_setup(&opts);\n  \tDIFF_OPT_SET(&opts, RECURSIVE);\n  \tDIFF_OPT_SET(&opts, TREE_IN_RECURSIVE);\n  \topts.change = tree_change;\n  \topts.add_remove = tree_addremove;\n+#\tdefine ENTRY_SIZE (20 + sizeof(size_t))\n\n  \t/* this is only called for non-ends (ie. all parents interesting) */\n  \tfor (list = commit->parents; list; list = list->next) {\n@@ -1254,20 +1437,20 @@ static int add_unique_objects(struct commit *commit)\n\n  \t\tstrbuf_setlen(acc_buffer, 0);\n  \t\tdiff_tree_sha1(list->item->tree->object.sha1, commit->tree->object.sha1, \"\", &opts);\n-\t\tqsort(acc_buffer->buf, acc_buffer->len / 20, 20, (int (*)(const void *, const void *))hashcmp);\n+\t\tqsort(acc_buffer->buf, acc_buffer->len / ENTRY_SIZE, ENTRY_SIZE, (int (*)(const void *, const void *))hashcmp);\n\n  \t\t/* take intersection */\n  \t\tif (!is_first) {\n-\t\t\tfor (next = i = j = 0; i < os.len; i += 20) {\n+\t\t\tfor (next = i = j = 0; i < os.len; i += ENTRY_SIZE) {\n  \t\t\t\twhile (j < ost.len && hashcmp((unsigned char *)(ost.buf + j), (unsigned char *)(os.buf + i)) < 0)\n-\t\t\t\t\tj += 20;\n+\t\t\t\t\tj += ENTRY_SIZE;\n\n  \t\t\t\tif (j >= ost.len || hashcmp((unsigned char *)(ost.buf + j), (unsigned char *)(os.buf + i)))\n  \t\t\t\t\tcontinue;\n\n  \t\t\t\tif (next != i)\n-\t\t\t\t\tmemcpy(os.buf + next, os.buf + i, 20);\n-\t\t\t\tnext += 20;\n+\t\t\t\t\tmemcpy(os.buf + next, os.buf + i, ENTRY_SIZE);\n+\t\t\t\tnext += ENTRY_SIZE;\n  \t\t\t}\n\n  \t\t\tif (next != i)\n@@ -1279,29 +1462,37 @@ static int add_unique_objects(struct commit *commit)\n  \t/* no parents (!) */\n  \tif (is_first) {\n  \t\tacc_buffer = &os;\n-\t\tdump_tree(commit->tree, dump_tree_callback);\n+\t\tdump_tree(commit->tree, dump_tree_callback, \"\");\n  \t}\n\n  \t/* the ordering of non-commit objects dosn't really matter, so we're not gonna bother */\n  \tacc_buffer = orig_buf;\n-\tfor (i = 0; i < os.len; i += 20)\n-\t\tadd_object_entry((unsigned char *)(os.buf + i), 0, 0, 0);\n+\tacc_name_buffer = orig_name_buf;\n+\tfor (i = 0; i < os.len; i += ENTRY_SIZE)\n+\t\tadd_object_entry((unsigned char *)(os.buf + i), 0, 0, 0, names.buf + *(size_t *)(os.buf + i + 20), 0);\n\n  \t/* last but not least, the main tree */\n-\tadd_object_entry(commit->tree->object.sha1, 0, 0, 0);\n+\tadd_object_entry(commit->tree->object.sha1, 0, 0, 0, 0, 0);\n\n-\treturn i / 20 + 1;\n+\tstrbuf_release(&ost);\n+\tstrbuf_release(&os);\n+\tstrbuf_release(&names);\n+\n+\treturn i / ENTRY_SIZE + 1;\n+#\tundef ENTRY_SIZE\n  }\n\n  static int add_objects_verbatim_1(struct rev_cache_slice_map *mapping, int *index)\n  {\n-\tunsigned char *map = mapping->map;\n  \tint i = *index, object_nr = 0;\n+\tunsigned char *map = mapping->map;\n  \tstruct rc_object_entry *entry = RC_OBTAIN_OBJECT_ENTRY(map + i);\n+\tunsigned long size;\n\n  \ti += RC_ACTUAL_OBJECT_ENTRY_SIZE(entry);\n  \twhile (i < mapping->size) {\n-\t\tint pos = i;\n+\t\tchar *name;\n+\t\tint name_index, pos = i;\n\n  \t\tentry = RC_OBTAIN_OBJECT_ENTRY(map + i);\n  \t\ti += RC_ACTUAL_OBJECT_ENTRY_SIZE(entry);\n@@ -1311,7 +1502,15 @@ static int add_objects_verbatim_1(struct rev_cache_slice_map *mapping, int *inde\n  \t\t\treturn object_nr;\n  \t\t}\n\n-\t\tstrbuf_add(acc_buffer, map + pos, i - pos);\n+\t\tname_index = decode_size(map + pos + RC_ENTRY_NAME_OFFSET(entry), entry->name_size);\n+\t\tif (name_index && name_index < mapping->name_size)\n+\t\t\tname = mapping->names + name_index;\n+\t\telse\n+\t\t\tname = 0;\n+\n+\t\tsize = decode_size(map + pos + RC_ENTRY_SIZE_OFFSET(entry), entry->size_size);\n+\n+\t\tadd_object_entry(0, entry, 0, 0, name, size);\n  \t\tobject_nr++;\n  \t}\n\n@@ -1396,6 +1595,7 @@ void init_rev_cache_info(struct rev_cache_info *rci)\n  \trci->overwrite_all = 0;\n\n  \trci->add_to_pending = 1;\n+\trci->add_names = 1;\n\n  \trci->ignore_size = 0;\n  }\n@@ -1420,9 +1620,9 @@ int make_cache_slice(struct rev_cache_info *rci,\n  \tstruct rc_slice_header head;\n  \tstruct commit *commit;\n  \tunsigned char sha1[20];\n-\tstruct strbuf merge_paths, split_paths;\n+\tstruct strbuf merge_paths, split_paths, namelist;\n  \tint object_nr, total_sz, fd;\n-\tchar file[PATH_MAX], *newfile;\n+\tchar file[PATH_MAX], null, *newfile;\n  \tstruct rev_cache_info *trci;\n  \tgit_SHA_CTX ctx;\n\n@@ -1437,7 +1637,13 @@ int make_cache_slice(struct rev_cache_info *rci,\n  \tstrbuf_init(&endlist, 0);\n  \tstrbuf_init(&merge_paths, 0);\n  \tstrbuf_init(&split_paths, 0);\n+\tstrbuf_init(&namelist, 0);\n  \tacc_buffer = &buffer;\n+\tacc_name_buffer = &namelist;\n+\n+\tnull = 0;\n+\tstrbuf_add(&namelist, &null, 1);\n+\tinit_name_list_hash();\n\n  \tif (!revs) {\n  \t\trevs = &therevs;\n@@ -1468,6 +1674,7 @@ int make_cache_slice(struct rev_cache_info *rci,\n  \ttrci = &revs->rev_cache_info;\n  \tinit_rev_cache_info(trci);\n  \ttrci->add_to_pending = 0;\n+\ttrci->add_names = 0;\n\n  \tsetup_revisions(0, 0, revs, 0);\n  \tif (prepare_revision_walk(revs))\n@@ -1505,7 +1712,7 @@ int make_cache_slice(struct rev_cache_info *rci,\n\n  \t\tcommit->indegree = 0;\n\n-\t\tadd_object_entry(0, &object, &merge_paths, &split_paths);\n+\t\tadd_object_entry(0, &object, &merge_paths, &split_paths, 0, 0);\n  \t\tobject_nr++;\n\n  \t\tif (rci->objects && !object.is_end) {\n@@ -1531,10 +1738,16 @@ int make_cache_slice(struct rev_cache_info *rci,\n  \t\ttotal_sz += buffer.len;\n  \t}\n\n+\t/* write path name lookup list */\n+\thead.name_size = htonl(namelist.len);\n+\twrite_in_full(fd, namelist.buf, namelist.len);\n+\n  \t/* go ahead a free some stuff... */\n  \tstrbuf_release(&buffer);\n  \tstrbuf_release(&merge_paths);\n  \tstrbuf_release(&split_paths);\n+\tstrbuf_release(&namelist);\n+\tcleanup_name_list_hash();\n  \tif (path_sz)\n  \t\tfree(paths);\n  \twhile (path_track_alloc)\n@@ -1992,6 +2205,7 @@ int fuse_cache_slices(struct rev_cache_info *rci, struct rev_info *revs)\n  \tfor (i = idx_head.cache_nr - 1; i >= 0; i--) {\n  \t\tstruct rev_cache_slice_map *map = rci->maps + i;\n  \t\tstruct stat fi;\n+\t\tstruct rc_slice_header head;\n  \t\tint fd;\n\n  \t\tif (!map->size)\n@@ -2004,13 +2218,20 @@ int fuse_cache_slices(struct rev_cache_info *rci, struct rev_info *revs)\n  \t\t\tcontinue;\n  \t\tif (fi.st_size < sizeof(struct rc_slice_header))\n  \t\t\tcontinue;\n+\t\tif (get_cache_slice_header(fd, idx_caches + i * 20, fi.st_size, &head))\n+\t\t\tcontinue;\n\n-\t\tmap->map = xmmap(0, fi.st_size, PROT_READ, MAP_PRIVATE, fd, 0);\n+\t\tmap->map = xmmap(0, head.size, PROT_READ, MAP_PRIVATE, fd, 0);\n  \t\tif (map->map == MAP_FAILED)\n  \t\t\tcontinue;\n\n+\t\tlseek(fd, head.size, SEEK_SET);\n+\t\tmap->names = xcalloc(head.name_size, 1);\n+\t\tread_in_full(fd, map->names, head.name_size);\n+\n  \t\tclose(fd);\n-\t\tmap->size = fi.st_size;\n+\t\tmap->size = head.size;\n+\t\tmap->name_size = head.name_size;\n  \t}\n\n  \trci->make_index = 0;\n@@ -2027,6 +2248,7 @@ int fuse_cache_slices(struct rev_cache_info *rci, struct rev_info *revs)\n  \t\tif (!map->size)\n  \t\t\tcontinue;\n\n+\t\tfree(map->names);\n  \t\tmunmap(map->map, map->size);\n  \t}\n  \tfree(rci->maps);\n@@ -2048,7 +2270,6 @@ static int verify_cache_slice(const char *slice_path, unsigned char *sha1)\n  {\n  \tstruct rc_slice_header head;\n  \tint fd, len, retval = -1;\n-\tunsigned char *map = MAP_FAILED;\n  \tstruct stat fi;\n\n  \tlen = strlen(slice_path);\n@@ -2063,17 +2284,12 @@ static int verify_cache_slice(const char *slice_path, unsigned char *sha1)\n  \tif (fstat(fd, &fi) || fi.st_size < sizeof(head))\n  \t\tgoto end;\n\n-\tmap = xmmap(0, sizeof(head), PROT_READ, MAP_PRIVATE, fd, 0);\n-\tif (map == MAP_FAILED)\n-\t\tgoto end;\n-\tif (get_cache_slice_header(sha1, map, fi.st_size, &head))\n+\tif (get_cache_slice_header(fd, sha1, fi.st_size, &head))\n  \t\tgoto end;\n\n  \tretval = 0;\n\n  end:\n-\tif (map != MAP_FAILED)\n-\t\tmunmap(map, sizeof(head));\n  \tif (fd > 0)\n  \t\tclose(fd);\n\ndiff --git a/rev-cache.h b/rev-cache.h\nindex a1af337..0fa9b44 100644\n--- a/rev-cache.h\n+++ b/rev-cache.h\n@@ -10,8 +10,14 @@\n  #define RC_OBTAIN_OBJECT_ENTRY(p)\t\t\tfrom_disked_rc_object_entry((struct rc_object_entry_ondisk *)(p), 0)\n  #define RC_OBTAIN_INDEX_ENTRY(p)\t\t\tfrom_disked_rc_index_entry((struct rc_index_entry_ondisk *)(p), 0)\n\n-#define RC_ACTUAL_OBJECT_ENTRY_SIZE(e)\t\t(sizeof(struct rc_object_entry_ondisk) + RC_PATH_SIZE((e)->merge_nr + (e)->split_nr) + (e)->size_size)\n-#define RC_ENTRY_SIZE_OFFSET(e)\t\t\t\t(RC_ACTUAL_OBJECT_ENTRY_SIZE(e) - (e)->size_size)\n+#define RC_ACTUAL_OBJECT_ENTRY_SIZE(e)\t(\\\n+\tsizeof(struct rc_object_entry_ondisk) + \\\n+\tRC_PATH_SIZE((e)->merge_nr + (e)->split_nr) + \\\n+\t(e)->size_size + \\\n+\t(e)->name_size\\\n+)\n+#define RC_ENTRY_SIZE_OFFSET(e)\t\t\t(RC_ACTUAL_OBJECT_ENTRY_SIZE(e) - (e)->name_size - (e)->size_size)\n+#define RC_ENTRY_NAME_OFFSET(e)\t\t\t(RC_ACTUAL_OBJECT_ENTRY_SIZE(e) - (e)->name_size)\n\n  /* single index maps objects to cache files */\n  struct rc_index_header {\n@@ -50,6 +56,8 @@ struct rc_slice_header {\n  \tuint32_t size;\n\n  \tunsigned char sha1[20];\n+\n+\tuint32_t name_size;\n  };\n\n  struct rc_object_entry_ondisk {\n@@ -76,7 +84,8 @@ struct rc_object_entry {\n  \tunsigned char merge_nr; /* : 7 */\n  \tunsigned char split_nr; /* : 7 */\n  \tunsigned size_size:3;\n-\tunsigned padding:5;\n+\tunsigned name_size:3;\n+\tunsigned padding:2;\n\n  \tuint32_t date;\n  \tuint16_t path;\n@@ -84,6 +93,7 @@ struct rc_object_entry {\n  \t/* merge paths */\n  \t/* split paths */\n  \t/* size */\n+\t/* name id */\n  };\n\n  struct rc_index_entry *from_disked_rc_index_entry(struct rc_index_entry_ondisk *src, struct rc_index_entry *dst);\ndiff --git a/revision.h b/revision.h\nindex cc5c259..c62e85b 100644\n--- a/revision.h\n+++ b/revision.h\n@@ -26,6 +26,9 @@ struct rev_cache_slice_map {\n  \tunsigned char *map;\n  \tint size;\n  \tint last_index;\n+\n+\tchar *names;\n+\tint name_size;\n  };\n\n  struct rev_cache_info {\n@@ -39,7 +42,8 @@ struct rev_cache_info {\n  \tunsigned overwrite_all : 1;\n\n  \t/* traversal flags */\n-\tunsigned add_to_pending : 1;\n+\tunsigned add_to_pending : 1,\n+\t\tadd_names : 1;\n\n  \t/* fuse options */\n  \tunsigned int ignore_size;\ndiff --git a/t/t6017-rev-cache-list.sh b/t/t6017-rev-cache-list.sh\nindex 982fb15..f0f3bcf 100755\n--- a/t/t6017-rev-cache-list.sh\n+++ b/t/t6017-rev-cache-list.sh\n@@ -4,8 +4,10 @@ test_description='git rev-cache tests'\n  . ./test-lib.sh\n\n  test_cmp_sorted() {\n-\tgrep -io \"[a-f0-9]*\" $1 | sort >.tmpfile1 &&\n-\tgrep -io \"[a-f0-9]*\" $2 | sort >.tmpfile2 &&\n+# note that we're tip-toeing around the corner case of two objects/names\n+# for the same SHA-1 => discrepencies between cached and non-cached walks\n+\tsort $1 >.tmpfile1 &&\n+\tsort $2 >.tmpfile2 &&\n  \ttest_cmp .tmpfile1 .tmpfile2\n  }\n\n@@ -15,6 +17,8 @@ test_cmp_sorted() {\n  # reuse\n  test_expect_success 'init repo' '\n  \techo bla >file &&\n+\tmkdir amaindir &&\n+\techo watskeburt >amaindir/file &&\n  \tgit add . &&\n  \tgit commit -m \"bla\" &&\n\n-- \ntg: (2b7d538..) t/revcache/names (depends on: t/revcache/docs)\n"},{"id":"125421","messageId":"4ADCCC90.60203@gmail.com","threadId":"20632","inReplyTo":"op.uys3qwlmtdk399@sirnot.private","subject":"Re: [PATCH 6/6 (v4)] support for path name caching in rev-cache","fromName":"Nick Edelen","fromEmail":"sirnot@gmail.com","sentAt":"2009-10-19T20:31:12Z","receivedAt":"2009-10-19T20:31:12Z","isPatch":true,"sender":{"key":"sirnot@gmail.com","avatar":null},"body":"An update to caching mechanism, allowing path names to be cached for blob and \ntree objects.  A list of names appearing in each cache slice is appended to the \nend of the slice, which is referenced by variable-sized indexes per entry.  \nThis allows pack-objects to more intelligently schedule unpacked/poorly packed \nobject, and enables proper duplication of rev-list's behaivor.\n\nThe mechanism for this involves adding a 'name' field to blob and tree objects, \nmainly to facilitate reuse of caches during maintenence (like the 'unique' \nfield).\n\nSigned-off-by: Nick Edelen <sirnot@gmail.com>\n\n---\n builtin-rev-cache.c       |    3 +-\n rev-cache.c               |  332 +++++++++++++++++++++++++++++++++++++--------\n rev-cache.h               |   16 ++-\n revision.h                |    6 +-\n t/t6017-rev-cache-list.sh |    8 +-\n 5 files changed, 300 insertions(+), 65 deletions(-)\n\ndiff --git a/builtin-rev-cache.c b/builtin-rev-cache.c\nindex 8f41123..4c1766d 100644\n--- a/builtin-rev-cache.c\n+++ b/builtin-rev-cache.c\n@@ -177,13 +177,14 @@ static int handle_walk(int argc, const char *argv[])\n \tfprintf(stderr, \"pending:\\n\");\n \tfor (i = 0; i < revs.pending.nr; i++) {\n \t\tstruct object *obj = revs.pending.objects[i].item;\n+\t\tconst char *name = revs.pending.objects[i].name;\n \n \t\t/* unfortunately, despite our careful generation, object duplication *is* a possibility...\n \t\t * (eg. same object introduced into two different branches) */\n \t\tif (obj->flags & SEEN)\n \t\t\tcontinue;\n \n-\t\tprintf(\"%s\\n\", sha1_to_hex(revs.pending.objects[i].item->sha1));\n+\t\tprintf(\"%s %s\\n\", sha1_to_hex(revs.pending.objects[i].item->sha1), name);\n \t\tobj->flags |= SEEN;\n \t}\n \ndiff --git a/rev-cache.c b/rev-cache.c\nindex 4ef5287..6c96297 100644\n--- a/rev-cache.c\n+++ b/rev-cache.c\n@@ -17,6 +17,14 @@ struct bad_slice {\n \tstruct bad_slice *next;\n };\n \n+struct name_list {\n+\tunsigned char sha1[20];\n+\tunsigned int len;\n+\tstruct name_list *next;\n+\n+\tchar buf[FLEX_ARRAY];\n+};\n+\n struct cache_slice_pointer {\n \tchar signature[8]; /* REVCOPTR */\n \tchar version;\n@@ -29,10 +37,13 @@ static uint32_t fanout[0xff + 2];\n static unsigned char *idx_map;\n static int idx_size;\n static struct rc_index_header idx_head;\n-static char no_idx, add_to_pending;\n-static struct bad_slice *bad_slices;\n+static char no_idx, add_to_pending, add_names;\n static unsigned char *idx_caches;\n \n+static struct bad_slice *bad_slices;\n+static struct name_list *name_lists, *cur_name_list;\n+\n+static struct strbuf *acc_name_buffer;\n static struct strbuf *acc_buffer;\n \n #define SLOP\t\t\t5\n@@ -79,7 +90,7 @@ struct rc_object_entry *from_disked_rc_object_entry(struct rc_object_entry_ondis\n \tif (!dst)\n \t\tdst = &entry[cur++ & 0x3];\n \n-\tdst->type = src->flags >> 5;\n+\tdst->type = src->flags >> 5 & 0x03;\n \tdst->is_end = !!(src->flags & 0x10);\n \tdst->is_start = !!(src->flags & 0x08);\n \tdst->uninteresting = !!(src->flags & 0x04);\n@@ -90,8 +101,9 @@ struct rc_object_entry *from_disked_rc_object_entry(struct rc_object_entry_ondis\n \tdst->merge_nr = src->merge_nr;\n \tdst->split_nr = src->split_nr;\n \n-\tdst->size_size = src->sizes >> 5;\n-\tdst->padding = src->sizes & 0x1f;\n+\tdst->size_size = src->sizes >> 5 & 0x03;\n+\tdst->name_size = src->sizes >> 2 & 0x03;\n+\tdst->padding = src->sizes & 0x02;\n \n \tdst->date = ntohl(src->date);\n \tdst->path = ntohs(src->path);\n@@ -120,6 +132,7 @@ struct rc_object_entry_ondisk *to_disked_rc_object_entry(struct rc_object_entry\n \tdst->split_nr = src->split_nr;\n \n \tdst->sizes  = (unsigned char)src->size_size << 5;\n+\tdst->sizes |= (unsigned char)src->name_size << 2;\n \tdst->sizes |= (unsigned char)src->padding;\n \n \tdst->date = htonl(src->date);\n@@ -192,6 +205,12 @@ static void cleanup_cache_slices(void)\n \t\tidx_map = 0;\n \t}\n \n+\twhile (name_lists) {\n+\t\tstruct name_list *nl = name_lists->next;\n+\t\tfree(name_lists);\n+\t\tname_lists = nl;\n+\t}\n+\n }\n \n static int init_index(void)\n@@ -324,7 +343,7 @@ static void handle_noncommit(struct rev_info *revs, struct commit *commit, unsig\n \tstruct blob *blob;\n \tstruct tree *tree;\n \tstruct object *obj;\n-\tunsigned long size;\n+\tunsigned long size, name_index;\n \n \tsize = decode_size(ptr + RC_ENTRY_SIZE_OFFSET(entry), entry->size_size);\n \tswitch (entry->type) {\n@@ -357,9 +376,23 @@ static void handle_noncommit(struct rev_info *revs, struct commit *commit, unsig\n \t\treturn;\n \t}\n \n+\tif (add_names && cur_name_list) {\n+\t\tname_index = decode_size(ptr + RC_ENTRY_NAME_OFFSET(entry), entry->name_size);\n+\n+\t\tif (name_index >= cur_name_list->len)\n+\t\t\tname_index = 0;\n+\t} else\n+\t\tname_index = 0;\n+\n \tobj->flags |= FACE_VALUE;\n-\tif (add_to_pending)\n-\t\tadd_pending_object(revs, obj, \"\");\n+\tif (add_to_pending) {\n+\t\tchar *name = \"\";\n+\n+\t\tif (name_index)\n+\t\t\tname = cur_name_list->buf + name_index;\n+\n+\t\tadd_pending_object(revs, obj, name);\n+\t}\n }\n \n static int setup_traversal(struct rc_slice_header *head, unsigned char *map, struct commit *commit, struct commit_list **work,\n@@ -713,15 +746,44 @@ end:\n \treturn retval;\n }\n \n-static int get_cache_slice_header(unsigned char *cache_sha1, unsigned char *map, int len, struct rc_slice_header *head)\n+static struct name_list *get_cache_slice_name_list(struct rc_slice_header *head, int fd)\n+{\n+\tstruct name_list *nl = name_lists;\n+\n+\twhile (nl) {\n+\t\tif (!hashcmp(nl->sha1, head->sha1))\n+\t\t\tbreak;\n+\t\tnl = nl->next;\n+\t}\n+\n+\tif (nl)\n+\t\treturn nl;\n+\n+\tnl = xcalloc(1, sizeof(struct name_list) + head->name_size);\n+\tnl->len = head->name_size;\n+\thashcpy(nl->sha1, head->sha1);\n+\n+\tlseek(fd, head->size, SEEK_SET);\n+\tread_in_full(fd, nl->buf, head->name_size);\n+\n+\tnl->next = name_lists;\n+\tname_lists = nl;\n+\n+\treturn nl;\n+}\n+\n+static int get_cache_slice_header(int fd, unsigned char *cache_sha1, int len, struct rc_slice_header *head)\n {\n \tint t;\n \n-\tmemcpy(head, map, sizeof(struct rc_slice_header));\n+\tif (xread(fd, head, sizeof(struct rc_slice_header)) != sizeof(struct rc_slice_header))\n+\t\treturn -1;\n+\n \thead->ofs_objects = ntohl(head->ofs_objects);\n \thead->object_nr = ntohl(head->object_nr);\n \thead->size = ntohl(head->size);\n \thead->path_nr = ntohs(head->path_nr);\n+\thead->name_size = ntohl(head->name_size);\n \n \tif (memcmp(head->signature, \"REVCACHE\", 8))\n \t\treturn -1;\n@@ -730,10 +792,10 @@ static int get_cache_slice_header(unsigned char *cache_sha1, unsigned char *map,\n \tif (hashcmp(head->sha1, cache_sha1))\n \t\treturn -3;\n \tt = sizeof(struct rc_slice_header);\n-\tif (t != head->ofs_objects || t >= len)\n+\tif (t != head->ofs_objects)\n \t\treturn -4;\n-\n-\thead->size = len;\n+\tif (head->size + head->name_size != len)\n+\t\treturn -5;\n \n \treturn 0;\n }\n@@ -785,7 +847,7 @@ int traverse_cache_slice(struct rev_info *revs,\n \tunsigned long *date_so_far, int *slop_so_far,\n \tstruct commit_list ***queue, struct commit_list **work)\n {\n-\tint fd = -1, retval = -3;\n+\tint fd = -1, t, retval;\n \tstruct stat fi;\n \tstruct rc_slice_header head;\n \tstruct rev_cache_info *rci;\n@@ -801,26 +863,31 @@ int traverse_cache_slice(struct rev_info *revs,\n \t/* load options */\n \trci = &revs->rev_cache_info;\n \tadd_to_pending = rci->add_to_pending;\n+\tadd_names = rci->add_names;\n \n \tmemset(&head, 0, sizeof(struct rc_slice_header));\n+#\tdefine ERROR(x)\t\tdo { retval = (x); goto end; } while (0);\n \n \tfd = open_cache_slice(cache_sha1, O_RDONLY);\n \tif (fd == -1)\n-\t\tgoto end;\n+\t\tERROR(-1);\n \tif (fstat(fd, &fi) || fi.st_size < sizeof(struct rc_slice_header))\n-\t\tgoto end;\n+\t\tERROR(-2);\n+\n+\tif ((t = get_cache_slice_header(fd, cache_sha1, fi.st_size, &head)) < 0)\n+\t\tERROR(-t);\n+\tif (add_names)\n+\t\tcur_name_list = get_cache_slice_name_list(&head, fd);\n \n-\tmap = xmmap(0, fi.st_size, PROT_READ | PROT_WRITE, MAP_PRIVATE, fd, 0);\n+\tmap = xmmap(0, head.size, PROT_READ | PROT_WRITE, MAP_PRIVATE, fd, 0);\n \tif (map == MAP_FAILED)\n-\t\tgoto end;\n-\tif (get_cache_slice_header(cache_sha1, map, fi.st_size, &head))\n-\t\tgoto end;\n+\t\tERROR(-3);\n \n \tretval = traverse_cache_slice_1(&head, map, revs, commit, date_so_far, slop_so_far, queue, work);\n \n end:\n \tif (map != MAP_FAILED)\n-\t\tmunmap(map, fi.st_size);\n+\t\tmunmap(map, head.size);\n \tif (fd != -1)\n \t\tclose(fd);\n \n@@ -828,6 +895,7 @@ end:\n \tif (retval)\n \t\tmark_bad_slice(cache_sha1);\n \n+#\tundef ERROR\n \treturn retval;\n }\n \n@@ -1112,23 +1180,110 @@ static unsigned long decode_size(unsigned char *str, int len)\n \treturn size;\n }\n \n+\n+#define NL_HASH_TABLE_SIZE\t\t(0xffff + 1)\n+#define NL_HASH_NUMBER\t\t\t(NL_HASH_TABLE_SIZE >> 3)\n+\n+struct name_list_hash {\n+\tint ind;\n+\tstruct name_list_hash *next;\n+};\n+\n+static struct name_list_hash **nl_hash_table;\n+static unsigned char *nl_hashes;\n+\n+/* FNV-1a hash */\n+static unsigned int hash_name(const char *name)\n+{\n+\tunsigned int hash = 2166136261ul;\n+\tconst char *p = name;\n+\n+\twhile (*p) {\n+\t\thash ^= *p++;\n+\t\thash *= 16777619ul;\n+\t}\n+\n+\treturn hash & 0xffff;\n+}\n+\n+static int name_in_list(const char *name)\n+{\n+\tunsigned int h = hash_name(name);\n+\tstruct name_list_hash *entry = nl_hash_table[h];\n+\n+\twhile (entry && strcmp(acc_name_buffer->buf + entry->ind, name))\n+\t\tentry = entry->next;\n+\n+\tif (entry)\n+\t\treturn entry->ind;\n+\n+\t/* add name to buffer and create hash reference */\n+\tentry = xcalloc(1, sizeof(struct name_list_hash));\n+\tentry->ind = acc_name_buffer->len;\n+\tstrbuf_add(acc_name_buffer, name, strlen(name) + 1);\n+\n+\tentry->next = nl_hash_table[h];\n+\tnl_hash_table[h] = entry;\n+\n+\tnl_hashes[h / 8] |= h % 8;\n+\n+\treturn entry->ind;\n+}\n+\n+static void init_name_list_hash(void)\n+{\n+\tnl_hash_table = xcalloc(NL_HASH_TABLE_SIZE, sizeof(struct name_list_hash));\n+\tnl_hashes = xcalloc(NL_HASH_NUMBER, 1);\n+}\n+\n+static void cleanup_name_list_hash(void)\n+{\n+\tint i;\n+\n+\tfor (i = 0; i < NL_HASH_NUMBER; i++) {\n+\t\tint j, ind = nl_hashes[i];\n+\n+\t\tif (!ind)\n+\t\t\tcontinue;\n+\n+\t\tfor (j = 0; j < 8; j++) {\n+\t\t\tstruct name_list_hash **entryp;\n+\n+\t\t\tif (!(ind & 1 << j))\n+\t\t\t\tcontinue;\n+\n+\t\t\tentryp = &nl_hash_table[i * 8 + j];\n+\t\t\twhile (*entryp) {\n+\t\t\t\tstruct name_list_hash *t = (*entryp)->next;\n+\n+\t\t\t\tfree(*entryp);\n+\t\t\t\t*entryp = t;\n+\t\t\t}\n+\t\t}\n+\t} /* code overhang! */\n+\n+\tfree(nl_hashes);\n+\tfree(nl_hash_table);\n+}\n+\n static void add_object_entry(const unsigned char *sha1, struct rc_object_entry *entryp,\n-\tstruct strbuf *merge_str, struct strbuf *split_str)\n+\tstruct strbuf *merge_str, struct strbuf *split_str, char *name, unsigned long size)\n {\n \tstruct rc_object_entry entry;\n-\tunsigned char size_str[7];\n-\tunsigned long size;\n+\tunsigned char size_str[7], name_str[7];\n \tenum object_type type;\n \tvoid *data;\n \n \tif (entryp)\n \t\tsha1 = entryp->sha1;\n \n-\t/* retrieve size data */\n-\tdata = read_sha1_file(sha1, &type, &size);\n+\tif (!size) {\n+\t\t/* retrieve size data */\n+\t\tdata = read_sha1_file(sha1, &type, &size);\n \n-\tif (data)\n-\t\tfree(data);\n+\t\tif (data)\n+\t\t\tfree(data);\n+\t}\n \n \t/* initialize! */\n \tif (!entryp) {\n@@ -1146,6 +1301,9 @@ static void add_object_entry(const unsigned char *sha1, struct rc_object_entry *\n \n \tentryp->size_size = encode_size(size, size_str);\n \n+\tif (name)\n+\t\tentryp->name_size = encode_size(name_in_list(name), name_str);\n+\n \t/* write the muvabitch */\n \tstrbuf_add(acc_buffer, to_disked_rc_object_entry(entryp, 0), sizeof(struct rc_object_entry_ondisk));\n \n@@ -1155,25 +1313,36 @@ static void add_object_entry(const unsigned char *sha1, struct rc_object_entry *\n \t\tstrbuf_add(acc_buffer, split_str->buf, split_str->len);\n \n \tstrbuf_add(acc_buffer, size_str, entryp->size_size);\n+\n+\tif (name)\n+\t\tstrbuf_add(acc_buffer, name_str, entryp->name_size);\n }\n \n /* returns non-zero to continue parsing, 0 to skip */\n typedef int (*dump_tree_fn)(const unsigned char *, const char *, unsigned int); /* sha1, path, mode */\n \n /* we need to walk the trees by hash, so unfortunately we can't use traverse_trees in tree-walk.c */\n-static int dump_tree(struct tree *tree, dump_tree_fn fn)\n+static int dump_tree(struct tree *tree, dump_tree_fn fn, char *base)\n {\n \tstruct tree_desc desc;\n \tstruct name_entry entry;\n \tstruct tree *subtree;\n-\tint r;\n+\tchar concatpath[PATH_MAX];\n+\tint r, baselen;\n \n \tif (parse_tree(tree))\n \t\treturn -1;\n \n+\tbaselen = strlen(base);\n+\tstrcpy(concatpath, base);\n+\n \tinit_tree_desc(&desc, tree->buffer, tree->size);\n \twhile (tree_entry(&desc, &entry)) {\n-\t\tswitch (fn(entry.sha1, entry.path, entry.mode)) {\n+\t\tif (baselen + strlen(entry.path) + 1 >= PATH_MAX)\n+\t\t\tdie(\"we have a problem: %s%s is too big for me to handle\", base, entry.path);\n+\t\tstrcpy(concatpath + baselen, entry.path);\n+\n+\t\tswitch (fn(entry.sha1, concatpath, entry.mode)) {\n \t\tcase 0:\n \t\t\tgoto continue_loop;\n \t\tdefault:\n@@ -1185,7 +1354,8 @@ static int dump_tree(struct tree *tree, dump_tree_fn fn)\n \t\t\tif (!subtree)\n \t\t\t\treturn -2;\n \n-\t\t\tif ((r = dump_tree(subtree, fn)) < 0)\n+\t\t\tstrcat(concatpath, \"/\");\n+\t\t\tif ((r = dump_tree(subtree, fn, concatpath)) < 0)\n \t\t\t\treturn r;\n \t\t}\n \n@@ -1199,6 +1369,9 @@ continue_loop:\n static int dump_tree_callback(const unsigned char *sha1, const char *path, unsigned int mode)\n {\n \tstrbuf_add(acc_buffer, sha1, 20);\n+\tstrbuf_add(acc_buffer, (char *)&acc_name_buffer->len, sizeof(size_t));\n+\n+\tstrbuf_add(acc_name_buffer, path, strlen(path) + 1);\n \n \treturn 1;\n }\n@@ -1212,6 +1385,9 @@ static void tree_addremove(struct diff_options *options,\n \t\treturn;\n \n \tstrbuf_add(acc_buffer, sha1, 20);\n+\tstrbuf_add(acc_buffer, (char *)&acc_name_buffer->len, sizeof(size_t));\n+\n+\tstrbuf_add(acc_name_buffer, concatpath, strlen(concatpath) + 1);\n }\n \n static void tree_change(struct diff_options *options,\n@@ -1224,12 +1400,15 @@ static void tree_change(struct diff_options *options,\n \t\treturn;\n \n \tstrbuf_add(acc_buffer, new_sha1, 20);\n+\tstrbuf_add(acc_buffer, (char *)&acc_name_buffer->len, sizeof(size_t));\n+\n+\tstrbuf_add(acc_name_buffer, concatpath, strlen(concatpath) + 1);\n }\n \n static int add_unique_objects(struct commit *commit)\n {\n \tstruct commit_list *list;\n-\tstruct strbuf os, ost, *orig_buf;\n+\tstruct strbuf os, ost, names, *orig_name_buf, *orig_buf;\n \tstruct diff_options opts;\n \tint i, j, next;\n \tchar is_first = 1;\n@@ -1237,13 +1416,17 @@ static int add_unique_objects(struct commit *commit)\n \t/* ...no, calculate unique objects */\n \tstrbuf_init(&os, 0);\n \tstrbuf_init(&ost, 0);\n+\tstrbuf_init(&names, 0);\n \torig_buf = acc_buffer;\n+\torig_name_buf = acc_name_buffer;\n+\tacc_name_buffer = &names;\n \n \tdiff_setup(&opts);\n \tDIFF_OPT_SET(&opts, RECURSIVE);\n \tDIFF_OPT_SET(&opts, TREE_IN_RECURSIVE);\n \topts.change = tree_change;\n \topts.add_remove = tree_addremove;\n+#\tdefine ENTRY_SIZE (20 + sizeof(size_t))\n \n \t/* this is only called for non-ends (ie. all parents interesting) */\n \tfor (list = commit->parents; list; list = list->next) {\n@@ -1254,20 +1437,20 @@ static int add_unique_objects(struct commit *commit)\n \n \t\tstrbuf_setlen(acc_buffer, 0);\n \t\tdiff_tree_sha1(list->item->tree->object.sha1, commit->tree->object.sha1, \"\", &opts);\n-\t\tqsort(acc_buffer->buf, acc_buffer->len / 20, 20, (int (*)(const void *, const void *))hashcmp);\n+\t\tqsort(acc_buffer->buf, acc_buffer->len / ENTRY_SIZE, ENTRY_SIZE, (int (*)(const void *, const void *))hashcmp);\n \n \t\t/* take intersection */\n \t\tif (!is_first) {\n-\t\t\tfor (next = i = j = 0; i < os.len; i += 20) {\n+\t\t\tfor (next = i = j = 0; i < os.len; i += ENTRY_SIZE) {\n \t\t\t\twhile (j < ost.len && hashcmp((unsigned char *)(ost.buf + j), (unsigned char *)(os.buf + i)) < 0)\n-\t\t\t\t\tj += 20;\n+\t\t\t\t\tj += ENTRY_SIZE;\n \n \t\t\t\tif (j >= ost.len || hashcmp((unsigned char *)(ost.buf + j), (unsigned char *)(os.buf + i)))\n \t\t\t\t\tcontinue;\n \n \t\t\t\tif (next != i)\n-\t\t\t\t\tmemcpy(os.buf + next, os.buf + i, 20);\n-\t\t\t\tnext += 20;\n+\t\t\t\t\tmemcpy(os.buf + next, os.buf + i, ENTRY_SIZE);\n+\t\t\t\tnext += ENTRY_SIZE;\n \t\t\t}\n \n \t\t\tif (next != i)\n@@ -1279,29 +1462,37 @@ static int add_unique_objects(struct commit *commit)\n \t/* no parents (!) */\n \tif (is_first) {\n \t\tacc_buffer = &os;\n-\t\tdump_tree(commit->tree, dump_tree_callback);\n+\t\tdump_tree(commit->tree, dump_tree_callback, \"\");\n \t}\n \n \t/* the ordering of non-commit objects dosn't really matter, so we're not gonna bother */\n \tacc_buffer = orig_buf;\n-\tfor (i = 0; i < os.len; i += 20)\n-\t\tadd_object_entry((unsigned char *)(os.buf + i), 0, 0, 0);\n+\tacc_name_buffer = orig_name_buf;\n+\tfor (i = 0; i < os.len; i += ENTRY_SIZE)\n+\t\tadd_object_entry((unsigned char *)(os.buf + i), 0, 0, 0, names.buf + *(size_t *)(os.buf + i + 20), 0);\n \n \t/* last but not least, the main tree */\n-\tadd_object_entry(commit->tree->object.sha1, 0, 0, 0);\n+\tadd_object_entry(commit->tree->object.sha1, 0, 0, 0, 0, 0);\n \n-\treturn i / 20 + 1;\n+\tstrbuf_release(&ost);\n+\tstrbuf_release(&os);\n+\tstrbuf_release(&names);\n+\n+\treturn i / ENTRY_SIZE + 1;\n+#\tundef ENTRY_SIZE\n }\n \n static int add_objects_verbatim_1(struct rev_cache_slice_map *mapping, int *index)\n {\n-\tunsigned char *map = mapping->map;\n \tint i = *index, object_nr = 0;\n+\tunsigned char *map = mapping->map;\n \tstruct rc_object_entry *entry = RC_OBTAIN_OBJECT_ENTRY(map + i);\n+\tunsigned long size;\n \n \ti += RC_ACTUAL_OBJECT_ENTRY_SIZE(entry);\n \twhile (i < mapping->size) {\n-\t\tint pos = i;\n+\t\tchar *name;\n+\t\tint name_index, pos = i;\n \n \t\tentry = RC_OBTAIN_OBJECT_ENTRY(map + i);\n \t\ti += RC_ACTUAL_OBJECT_ENTRY_SIZE(entry);\n@@ -1311,7 +1502,15 @@ static int add_objects_verbatim_1(struct rev_cache_slice_map *mapping, int *inde\n \t\t\treturn object_nr;\n \t\t}\n \n-\t\tstrbuf_add(acc_buffer, map + pos, i - pos);\n+\t\tname_index = decode_size(map + pos + RC_ENTRY_NAME_OFFSET(entry), entry->name_size);\n+\t\tif (name_index && name_index < mapping->name_size)\n+\t\t\tname = mapping->names + name_index;\n+\t\telse\n+\t\t\tname = 0;\n+\n+\t\tsize = decode_size(map + pos + RC_ENTRY_SIZE_OFFSET(entry), entry->size_size);\n+\n+\t\tadd_object_entry(0, entry, 0, 0, name, size);\n \t\tobject_nr++;\n \t}\n \n@@ -1396,6 +1595,7 @@ void init_rev_cache_info(struct rev_cache_info *rci)\n \trci->overwrite_all = 0;\n \n \trci->add_to_pending = 1;\n+\trci->add_names = 1;\n \n \trci->ignore_size = 0;\n }\n@@ -1420,9 +1620,9 @@ int make_cache_slice(struct rev_cache_info *rci,\n \tstruct rc_slice_header head;\n \tstruct commit *commit;\n \tunsigned char sha1[20];\n-\tstruct strbuf merge_paths, split_paths;\n+\tstruct strbuf merge_paths, split_paths, namelist;\n \tint object_nr, total_sz, fd;\n-\tchar file[PATH_MAX], *newfile;\n+\tchar file[PATH_MAX], null, *newfile;\n \tstruct rev_cache_info *trci;\n \tgit_SHA_CTX ctx;\n \n@@ -1437,7 +1637,13 @@ int make_cache_slice(struct rev_cache_info *rci,\n \tstrbuf_init(&endlist, 0);\n \tstrbuf_init(&merge_paths, 0);\n \tstrbuf_init(&split_paths, 0);\n+\tstrbuf_init(&namelist, 0);\n \tacc_buffer = &buffer;\n+\tacc_name_buffer = &namelist;\n+\n+\tnull = 0;\n+\tstrbuf_add(&namelist, &null, 1);\n+\tinit_name_list_hash();\n \n \tif (!revs) {\n \t\trevs = &therevs;\n@@ -1468,6 +1674,7 @@ int make_cache_slice(struct rev_cache_info *rci,\n \ttrci = &revs->rev_cache_info;\n \tinit_rev_cache_info(trci);\n \ttrci->add_to_pending = 0;\n+\ttrci->add_names = 0;\n \n \tsetup_revisions(0, 0, revs, 0);\n \tif (prepare_revision_walk(revs))\n@@ -1505,7 +1712,7 @@ int make_cache_slice(struct rev_cache_info *rci,\n \n \t\tcommit->indegree = 0;\n \n-\t\tadd_object_entry(0, &object, &merge_paths, &split_paths);\n+\t\tadd_object_entry(0, &object, &merge_paths, &split_paths, 0, 0);\n \t\tobject_nr++;\n \n \t\tif (rci->objects && !object.is_end) {\n@@ -1531,10 +1738,16 @@ int make_cache_slice(struct rev_cache_info *rci,\n \t\ttotal_sz += buffer.len;\n \t}\n \n+\t/* write path name lookup list */\n+\thead.name_size = htonl(namelist.len);\n+\twrite_in_full(fd, namelist.buf, namelist.len);\n+\n \t/* go ahead a free some stuff... */\n \tstrbuf_release(&buffer);\n \tstrbuf_release(&merge_paths);\n \tstrbuf_release(&split_paths);\n+\tstrbuf_release(&namelist);\n+\tcleanup_name_list_hash();\n \tif (path_sz)\n \t\tfree(paths);\n \twhile (path_track_alloc)\n@@ -1992,6 +2205,7 @@ int fuse_cache_slices(struct rev_cache_info *rci, struct rev_info *revs)\n \tfor (i = idx_head.cache_nr - 1; i >= 0; i--) {\n \t\tstruct rev_cache_slice_map *map = rci->maps + i;\n \t\tstruct stat fi;\n+\t\tstruct rc_slice_header head;\n \t\tint fd;\n \n \t\tif (!map->size)\n@@ -2004,13 +2218,20 @@ int fuse_cache_slices(struct rev_cache_info *rci, struct rev_info *revs)\n \t\t\tcontinue;\n \t\tif (fi.st_size < sizeof(struct rc_slice_header))\n \t\t\tcontinue;\n+\t\tif (get_cache_slice_header(fd, idx_caches + i * 20, fi.st_size, &head))\n+\t\t\tcontinue;\n \n-\t\tmap->map = xmmap(0, fi.st_size, PROT_READ, MAP_PRIVATE, fd, 0);\n+\t\tmap->map = xmmap(0, head.size, PROT_READ, MAP_PRIVATE, fd, 0);\n \t\tif (map->map == MAP_FAILED)\n \t\t\tcontinue;\n \n+\t\tlseek(fd, head.size, SEEK_SET);\n+\t\tmap->names = xcalloc(head.name_size, 1);\n+\t\tread_in_full(fd, map->names, head.name_size);\n+\n \t\tclose(fd);\n-\t\tmap->size = fi.st_size;\n+\t\tmap->size = head.size;\n+\t\tmap->name_size = head.name_size;\n \t}\n \n \trci->make_index = 0;\n@@ -2027,6 +2248,7 @@ int fuse_cache_slices(struct rev_cache_info *rci, struct rev_info *revs)\n \t\tif (!map->size)\n \t\t\tcontinue;\n \n+\t\tfree(map->names);\n \t\tmunmap(map->map, map->size);\n \t}\n \tfree(rci->maps);\n@@ -2048,7 +2270,6 @@ static int verify_cache_slice(const char *slice_path, unsigned char *sha1)\n {\n \tstruct rc_slice_header head;\n \tint fd, len, retval = -1;\n-\tunsigned char *map = MAP_FAILED;\n \tstruct stat fi;\n \n \tlen = strlen(slice_path);\n@@ -2063,17 +2284,12 @@ static int verify_cache_slice(const char *slice_path, unsigned char *sha1)\n \tif (fstat(fd, &fi) || fi.st_size < sizeof(head))\n \t\tgoto end;\n \n-\tmap = xmmap(0, sizeof(head), PROT_READ, MAP_PRIVATE, fd, 0);\n-\tif (map == MAP_FAILED)\n-\t\tgoto end;\n-\tif (get_cache_slice_header(sha1, map, fi.st_size, &head))\n+\tif (get_cache_slice_header(fd, sha1, fi.st_size, &head))\n \t\tgoto end;\n \n \tretval = 0;\n \n end:\n-\tif (map != MAP_FAILED)\n-\t\tmunmap(map, sizeof(head));\n \tif (fd > 0)\n \t\tclose(fd);\n \ndiff --git a/rev-cache.h b/rev-cache.h\nindex a1af337..0fa9b44 100644\n--- a/rev-cache.h\n+++ b/rev-cache.h\n@@ -10,8 +10,14 @@\n #define RC_OBTAIN_OBJECT_ENTRY(p)\t\t\tfrom_disked_rc_object_entry((struct rc_object_entry_ondisk *)(p), 0)\n #define RC_OBTAIN_INDEX_ENTRY(p)\t\t\tfrom_disked_rc_index_entry((struct rc_index_entry_ondisk *)(p), 0)\n \n-#define RC_ACTUAL_OBJECT_ENTRY_SIZE(e)\t\t(sizeof(struct rc_object_entry_ondisk) + RC_PATH_SIZE((e)->merge_nr + (e)->split_nr) + (e)->size_size)\n-#define RC_ENTRY_SIZE_OFFSET(e)\t\t\t\t(RC_ACTUAL_OBJECT_ENTRY_SIZE(e) - (e)->size_size)\n+#define RC_ACTUAL_OBJECT_ENTRY_SIZE(e)\t(\\\n+\tsizeof(struct rc_object_entry_ondisk) + \\\n+\tRC_PATH_SIZE((e)->merge_nr + (e)->split_nr) + \\\n+\t(e)->size_size + \\\n+\t(e)->name_size\\\n+)\n+#define RC_ENTRY_SIZE_OFFSET(e)\t\t\t(RC_ACTUAL_OBJECT_ENTRY_SIZE(e) - (e)->name_size - (e)->size_size)\n+#define RC_ENTRY_NAME_OFFSET(e)\t\t\t(RC_ACTUAL_OBJECT_ENTRY_SIZE(e) - (e)->name_size)\n \n /* single index maps objects to cache files */\n struct rc_index_header {\n@@ -50,6 +56,8 @@ struct rc_slice_header {\n \tuint32_t size;\n \n \tunsigned char sha1[20];\n+\n+\tuint32_t name_size;\n };\n \n struct rc_object_entry_ondisk {\n@@ -76,7 +84,8 @@ struct rc_object_entry {\n \tunsigned char merge_nr; /* : 7 */\n \tunsigned char split_nr; /* : 7 */\n \tunsigned size_size:3;\n-\tunsigned padding:5;\n+\tunsigned name_size:3;\n+\tunsigned padding:2;\n \n \tuint32_t date;\n \tuint16_t path;\n@@ -84,6 +93,7 @@ struct rc_object_entry {\n \t/* merge paths */\n \t/* split paths */\n \t/* size */\n+\t/* name id */\n };\n \n struct rc_index_entry *from_disked_rc_index_entry(struct rc_index_entry_ondisk *src, struct rc_index_entry *dst);\ndiff --git a/revision.h b/revision.h\nindex d160e14..dd51d27 100644\n--- a/revision.h\n+++ b/revision.h\n@@ -26,6 +26,9 @@ struct rev_cache_slice_map {\n \tunsigned char *map;\n \tint size;\n \tint last_index;\n+\n+\tchar *names;\n+\tint name_size;\n };\n \n struct rev_cache_info {\n@@ -39,7 +42,8 @@ struct rev_cache_info {\n \tunsigned overwrite_all : 1;\n \n \t/* traversal flags */\n-\tunsigned add_to_pending : 1;\n+\tunsigned add_to_pending : 1,\n+\t\tadd_names : 1;\n \n \t/* fuse options */\n \tunsigned int ignore_size;\ndiff --git a/t/t6017-rev-cache-list.sh b/t/t6017-rev-cache-list.sh\nindex 982fb15..f0f3bcf 100755\n--- a/t/t6017-rev-cache-list.sh\n+++ b/t/t6017-rev-cache-list.sh\n@@ -4,8 +4,10 @@ test_description='git rev-cache tests'\n . ./test-lib.sh\n \n test_cmp_sorted() {\n-\tgrep -io \"[a-f0-9]*\" $1 | sort >.tmpfile1 &&\n-\tgrep -io \"[a-f0-9]*\" $2 | sort >.tmpfile2 &&\n+# note that we're tip-toeing around the corner case of two objects/names\n+# for the same SHA-1 => discrepencies between cached and non-cached walks\n+\tsort $1 >.tmpfile1 &&\n+\tsort $2 >.tmpfile2 &&\n \ttest_cmp .tmpfile1 .tmpfile2\n }\n \n@@ -15,6 +17,8 @@ test_cmp_sorted() {\n # reuse\n test_expect_success 'init repo' '\n \techo bla >file &&\n+\tmkdir amaindir &&\n+\techo watskeburt >amaindir/file &&\n \tgit add . &&\n \tgit commit -m \"bla\" &&\n \n-- \ntg: (9e5164a..) t/revcache/names (depends on: t/revcache/docs)\n"}]}