{"thread":{"id":"20573","subject":"[PATCH 6/6 (v3)] support for path name caching of blobs/trees in rev-cache","startedAt":"2009-08-13T10:24:50Z","lastAt":"2009-08-13T10:24:50Z","messageCount":1,"participants":["Nick Edelen"],"isPatch":true,"patchVersion":3,"patchTotal":6},"messages":[{"id":"120502","messageId":"op.uyli7oeltdk399@sirnot.belkin","threadId":"20573","inReplyTo":null,"subject":"[PATCH 6/6 (v3)] support for path name caching of blobs/trees in rev-cache","fromName":"Nick Edelen","fromEmail":"sirnot@gmail.com","sentAt":"2009-08-13T10:24:50Z","receivedAt":"2009-08-13T10:24:50Z","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               |  307 +++++++++++++++++++++++++++++++++++++--------\n rev-cache.h               |   13 ++-\n revision.h                |    6 +-\n t/t6015-rev-cache-list.sh |    4 +-\n tree.h                    |    1 +\n 6 files changed, 274 insertions(+), 60 deletions(-)\n\ndiff --git a/builtin-rev-cache.c b/builtin-rev-cache.c\nindex 2db4a10..042cf08 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 \t\t\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 \t\t\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 \t\ndiff --git a/rev-cache.c b/rev-cache.c\nindex fae8544..f98b247 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+\t\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 *g_name_buffer;\n static struct strbuf *g_buffer;\n \n #define PATH_WIDTH\tRC_PATH_WIDTH\n@@ -46,6 +57,7 @@ static struct strbuf *g_buffer;\n \n #define ACTUAL_OBJECT_ENTRY_SIZE(e)\t\tRC_ACTUAL_OBJECT_ENTRY_SIZE(e)\n #define ENTRY_SIZE_OFFSET(e)\t\t\tRC_ENTRY_SIZE_OFFSET(e)\n+#define ENTRY_NAME_OFFSET(e)\t\t\tRC_ENTRY_NAME_OFFSET(e)\n \n #define SLOP\t\t\t5\n \n@@ -115,6 +127,12 @@ static void cleanup_cache_slices(void)\n \t\tidx_map = 0;\n \t}\n \t\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+\t\n }\n \n static int init_index(void)\n@@ -237,7 +255,7 @@ static void handle_noncommit(struct rev_info *revs, struct commit *commit, struc\n \tstruct blob *blob;\n \tstruct tree *tree;\n \tstruct object *obj;\n-\tunsigned long size;\n+\tunsigned long size, name_index;\n \t\n \tsize = decode_size((unsigned char *)entry + ENTRY_SIZE_OFFSET(entry), entry->size_size);\n \tswitch (entry->type) {\n@@ -270,9 +288,22 @@ static void handle_noncommit(struct rev_info *revs, struct commit *commit, struc\n \t\treturn;\n \t}\n \t\n+\tif (add_names && cur_name_list) {\n+\t\tname_index = decode_size((unsigned char *)entry + ENTRY_NAME_OFFSET(entry), entry->name_size);\n+\t\t\n+\t\tif (name_index >= cur_name_list->len)\n+\t\t\tname_index = 0;\n+\t} else name_index = 0;\n+\t\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+\t\t\n+\t\tif (name_index)\n+\t\t\tname = cur_name_list->buf + name_index;\n+\t\t\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@@ -622,15 +653,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+\t\n+\twhile (nl) {\n+\t\tif (!hashcmp(nl->sha1, head->sha1))\n+\t\t\tbreak;\n+\t\tnl = nl->next;\n+\t}\n+\t\n+\tif (nl)\n+\t\treturn nl;\n+\t\n+\tnl = xcalloc(1, sizeof(struct name_list) + head->name_size);\n+\tnl->len = head->name_size;\n+\thashcpy(nl->sha1, head->sha1);\n+\t\n+\tlseek(fd, head->size, SEEK_SET);\n+\tread_in_full(fd, nl->buf, head->name_size);\n+\t\n+\tnl->next = name_lists;\n+\tname_lists = nl;\n+\t\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 \t\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+\t\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 \t\n \tif (memcmp(head->signature, \"REVCACHE\", 8))\n \t\treturn -1;\n@@ -639,10 +699,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-\t\n-\thead->size = len;\n+\tif (head->size + head->name_size != len)\n+\t\treturn -5;\n \t\n \treturn 0;\n }\n@@ -694,7 +754,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@@ -710,26 +770,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 \t\n \tmemset(&head, 0, sizeof(struct rc_slice_header));\n+#\tdefine ERROR(x)\t\tdo { retval = (x); goto end; } while (0);\n \t\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 \t\n-\tmap = xmmap(0, fi.st_size, PROT_READ, MAP_PRIVATE, fd, 0);\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+\t\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 \t\n \tretval = traverse_cache_slice_1(&head, map, revs, commit, date_so_far, slop_so_far, queue, work);\n \t\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 \t\n@@ -737,6 +802,7 @@ end:\n \tif (retval)\n \t\tmark_bad_slice(cache_sha1);\n \t\n+#\tundef ERROR\n \treturn retval;\n }\n \n@@ -1021,23 +1087,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+\t\n+\twhile (*p) {\n+\t\thash ^= *p++;\n+\t\thash *= 16777619ul;\n+\t}\n+\t\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+\t\n+\twhile (entry && strcmp(g_name_buffer->buf + entry->ind, name))\n+\t\tentry = entry->next;\n+\t\n+\tif (entry)\n+\t\treturn entry->ind;\n+\t\n+\t/* add name to buffer and create hash reference */\n+\tentry = xcalloc(1, sizeof(struct name_list_hash));\n+\tentry->ind = g_name_buffer->len;\n+\tstrbuf_add(g_name_buffer, name, strlen(name) + 1);\n+\t\n+\tentry->next = nl_hash_table[h];\n+\tnl_hash_table[h] = entry;\n+\t\n+\tnl_hashes[h / 8] |= h % 8;\n+\t\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+\t\n+\tfor (i = 0; i < NL_HASH_NUMBER; i++) {\n+\t\tint j, ind = nl_hashes[i];\n+\t\t\n+\t\tif (!ind)\n+\t\t\tcontinue;\n+\t\t\n+\t\tfor (j = 0; j < 8; j++) {\n+\t\t\tstruct name_list_hash **entryp;\n+\t\t\t\n+\t\t\tif (!(ind & 1 << j))\n+\t\t\t\tcontinue;\n+\t\t\t\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+\t\t\t\t\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+\t\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 \t\n \tif (entryp)\n \t\tsha1 = entryp->sha1;\n \t\n-\t/* retrieve size data */\n-\tdata = read_sha1_file(sha1, &type, &size);\n-\t\n-\tif (data)\n-\t\tfree(data);\n+\tif (!size) {\n+\t\t/* retrieve size data */\n+\t\tdata = read_sha1_file(sha1, &type, &size);\n+\t\t\n+\t\tif (data)\n+\t\t\tfree(data);\n+\t}\n \t\n \t/* initialize! */\n \tif (!entryp) {\n@@ -1055,6 +1208,9 @@ static void add_object_entry(const unsigned char *sha1, struct rc_object_entry *\n \t\n \tentryp->size_size = encode_size(size, size_str);\n \t\n+\tif (name)\n+\t\tentryp->name_size = encode_size(name_in_list(name), name_str);\n+\t\n \t/* write the muvabitch */\n \tstrbuf_add(g_buffer, entryp, sizeof(entry));\n \t\n@@ -1064,6 +1220,9 @@ static void add_object_entry(const unsigned char *sha1, struct rc_object_entry *\n \t\tstrbuf_add(g_buffer, split_str->buf, split_str->len);\n \t\n \tstrbuf_add(g_buffer, size_str, entryp->size_size);\n+\t\n+\tif (name)\n+\t\tstrbuf_add(g_buffer, name_str, entryp->name_size);\n }\n \n /* returns non-zero to continue parsing, 0 to skip */\n@@ -1108,6 +1267,9 @@ continue_loop:\n static int dump_tree_callback(const unsigned char *sha1, const char *path, unsigned int mode)\n {\n \tstrbuf_add(g_buffer, sha1, 20);\n+\tstrbuf_add(g_buffer, (char *)&g_name_buffer->len, sizeof(size_t));\n+\t\n+\tstrbuf_add(g_name_buffer, path, strlen(path) + 1);\n \t\n \treturn 1;\n }\n@@ -1121,6 +1283,9 @@ static void tree_addremove(struct diff_options *options,\n \t\treturn;\n \t\n \tstrbuf_add(g_buffer, sha1, 20);\n+\tstrbuf_add(g_buffer, (char *)&g_name_buffer->len, sizeof(size_t));\n+\t\n+\tstrbuf_add(g_name_buffer, concatpath, strlen(concatpath) + 1);\n }\n \n static void tree_change(struct diff_options *options,\n@@ -1133,12 +1298,15 @@ static void tree_change(struct diff_options *options,\n \t\treturn;\n \t\n \tstrbuf_add(g_buffer, new_sha1, 20);\n+\tstrbuf_add(g_buffer, (char *)&g_name_buffer->len, sizeof(size_t));\n+\t\n+\tstrbuf_add(g_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@@ -1146,13 +1314,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 = g_buffer;\n+\torig_name_buf = g_name_buffer;\n+\tg_name_buffer = &names;\n \t\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 \t\n \t/* this is only called for non-ends (ie. all parents interesting) */\n \tfor (list = commit->parents; list; list = list->next) {\n@@ -1163,20 +1335,20 @@ static int add_unique_objects(struct commit *commit)\n \t\t\n \t\tstrbuf_setlen(g_buffer, 0);\n \t\tdiff_tree_sha1(list->item->tree->object.sha1, commit->tree->object.sha1, \"\", &opts);\n-\t\tqsort(g_buffer->buf, g_buffer->len / 20, 20, (int (*)(const void *, const void *))hashcmp);\n+\t\tqsort(g_buffer->buf, g_buffer->len / ENTRY_SIZE, ENTRY_SIZE, (int (*)(const void *, const void *))hashcmp);\n \t\t\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 \t\t\t\t\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 \t\t\t\t\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 \t\t\t\n \t\t\tif (next != i)\n@@ -1193,25 +1365,32 @@ static int add_unique_objects(struct commit *commit)\n \t\n \t/* the ordering of non-commit objects dosn't really matter, so we're not gonna bother */\n \tg_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+\tg_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 \t\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+\t\n+\tstrbuf_release(&ost);\n+\tstrbuf_release(&os);\n+\tstrbuf_release(&names);\n \t\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 = OE_CAST(map + *index);\n+\tunsigned long size;\n \t\n \ti += ACTUAL_OBJECT_ENTRY_SIZE(entry);\n \twhile (i < mapping->size) {\n-\t\tint pos = i;\n-\t\t\n+\t\tchar *name;\n+\t\tint name_index, pos = i;\n \t\tentry = OE_CAST(map + i);\n \t\ti += ACTUAL_OBJECT_ENTRY_SIZE(entry);\n \t\t\n@@ -1220,7 +1399,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 \t\t\n-\t\tstrbuf_add(g_buffer, map + pos, i - pos);\n+\t\tname_index = decode_size((unsigned char *)entry + 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+\t\t\n+\t\tsize = decode_size((unsigned char *)entry + ENTRY_SIZE_OFFSET(entry), entry->size_size);\n+\t\t\n+\t\tadd_object_entry(0, entry, 0, 0, name, size);\n \t\tobject_nr++;\n \t}\n \t\n@@ -1305,6 +1492,7 @@ void init_rev_cache_info(struct rev_cache_info *rci)\n \trci->overwrite_all = 0;\n \t\n \trci->add_to_pending = 1;\n+\trci->add_names = 1;\n \t\n \trci->ignore_size = 0;\n }\n@@ -1329,9 +1517,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 \t\n@@ -1346,7 +1534,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 \tg_buffer = &buffer;\n+\tg_name_buffer = &namelist;\n+\t\n+\tnull = 0;\n+\tstrbuf_add(&namelist, &null, 1);\n+\tinit_name_list_hash();\n \t\n \tif (!revs) {\n \t\trevs = &therevs;\n@@ -1414,7 +1608,7 @@ int make_cache_slice(struct rev_cache_info *rci,\n \t\t\n \t\tcommit->indegree = 0;\n \t\t\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 \t\t\n \t\tif (rci->objects && !object.is_end) {\n@@ -1440,10 +1634,16 @@ int make_cache_slice(struct rev_cache_info *rci,\n \t\ttotal_sz += buffer.len;\n \t}\n \t\n+\t/* write path name lookup list */\n+\thead.name_size = htonl(namelist.len);\n+\twrite_in_full(fd, namelist.buf, namelist.len);\n+\t\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@@ -1897,6 +2097,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 \t\t\n \t\tif (!map->size)\n@@ -1909,13 +2110,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 \t\t\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 \t\t\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+\t\t\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 \t\n \trci->make_index = 0;\n@@ -1932,6 +2140,7 @@ int fuse_cache_slices(struct rev_cache_info *rci, struct rev_info *revs)\n \t\tif (!map->size)\n \t\t\tcontinue;\n \t\t\n+\t\tfree(map->names);\n \t\tmunmap(map->map, map->size);\n \t}\n \tfree(rci->maps);\n@@ -1953,7 +2162,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 \t\n \tlen = strlen(slice_path);\n@@ -1968,17 +2176,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 \t\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 \t\n \tretval = 0;\n \t\n end:\n-\tif (map != MAP_FAILED)\n-\t\tmunmap(map, sizeof(head));\n \tif (fd > 0)\n \t\tclose(fd);\n \t\ndiff --git a/rev-cache.h b/rev-cache.h\nindex f0b7d57..0254db7 100644\n--- a/rev-cache.h\n+++ b/rev-cache.h\n@@ -13,9 +13,10 @@\n \n #define RC_OE_CAST(p)\t((struct rc_object_entry *)(p))\n #define RC_IE_CAST(p)\t((struct rc_index_entry *)(p))\n-\n-#define RC_ACTUAL_OBJECT_ENTRY_SIZE(e)\t\t(RC_OE_SIZE + RC_PATH_SIZE((e)->merge_nr + (e)->split_nr) + (e)->size_size)\n-#define RC_ENTRY_SIZE_OFFSET(e)\t\t\t(RC_ACTUAL_OBJECT_ENTRY_SIZE(e) - (e)->size_size)\n+\n+#define RC_ACTUAL_OBJECT_ENTRY_SIZE(e)\t\t(RC_OE_SIZE + RC_PATH_SIZE((e)->merge_nr + (e)->split_nr) + (e)->size_size + (e)->name_size)\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@@ -48,6 +49,8 @@ struct rc_slice_header {\n \tuint32_t size;\n \t\n \tunsigned char sha1[20];\n+\t\n+\tuint32_t name_size;\n };\n \n struct rc_object_entry {\n@@ -62,7 +65,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 \t\n \tuint32_t date;\n \tuint16_t path;\n@@ -70,6 +74,7 @@ struct rc_object_entry {\n \t/* merge paths */\n \t/* split paths */\n \t/* size */\n+\t/* name id */\n };\n \n \ndiff --git a/revision.h b/revision.h\nindex ec83aa0..a802c9b 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+\t\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 \t\n \t/* traversal flags */\n-\tunsigned add_to_pending : 1;\n+\tunsigned add_to_pending : 1, \n+\t\tadd_names : 1;\n \t\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 \ndiff --git a/tree.h b/tree.h\nindex 2ff01a4..6eb0cd0 100644\n--- a/tree.h\n+++ b/tree.h\n@@ -9,6 +9,7 @@ struct tree {\n \tstruct object object;\n \tvoid *buffer;\n \tunsigned long size;\n+\tchar *name;\n };\n \n struct tree *lookup_tree(const unsigned char *sha1);\n-- \ntg: (bc19f4a..) t/revcache/names (depends on: t/revcache/docs)\n"}]}