{"thread":{"id":"20471","subject":"[PATCH 6/6 (v2)] support for path name caching of blobs/trees in rev-cache","startedAt":"2009-08-08T07:32:06Z","lastAt":"2009-08-16T22:42:11Z","messageCount":2,"participants":["Nick Edelen"],"isPatch":true,"patchVersion":2,"patchTotal":6},"messages":[{"id":"119968","messageId":"op.uyb1vs0htdk399@sirnot.private","threadId":"20471","inReplyTo":null,"subject":"[PATCH 6/6 (v2)] support for path name caching of blobs/trees in rev-cache","fromName":"Nick Edelen","fromEmail":"sirnot@gmail.com","sentAt":"2009-08-08T07:32:06Z","receivedAt":"2009-08-08T07:32: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\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---\nThis is a totally new patch to the series.  I had somehow missed name caching \nearlier.\n\n blob.h                    |    1 +\n builtin-rev-cache.c       |    3 +-\n rev-cache.c               |  293 ++++++++++++++++++++++++++++++++++++++-------\n revision.h                |    3 +-\n t/t6015-rev-cache-list.sh |    4 +-\n tree.h                    |    1 +\n 6 files changed, 259 insertions(+), 46 deletions(-)\n\ndiff --git a/blob.h b/blob.h\nindex d8db96a..e6a46f3 100644\n--- a/blob.h\n+++ b/blob.h\n@@ -8,6 +8,7 @@ extern const char *blob_type;\n struct blob {\n \tstruct object object;\n \tunsigned long size;\n+\tchar *name;\n };\n \n struct blob *lookup_blob(const unsigned char *sha1);\ndiff --git a/builtin-rev-cache.c b/builtin-rev-cache.c\nindex 4a02af6..5f88214 100755\n--- a/builtin-rev-cache.c\n+++ b/builtin-rev-cache.c\n@@ -168,13 +168,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\tchar *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 e6808e7..347e005 100755\n--- a/rev-cache.c\n+++ b/rev-cache.c\n@@ -42,6 +42,8 @@ struct cache_slice_header {\n \tuint32_t size;\n \t\n \tunsigned char sha1[20];\n+\t\n+\tuint32_t name_size;\n };\n \n struct object_entry {\n@@ -56,6 +58,8 @@ struct object_entry {\n \tunsigned merge_nr : 6;\n \tunsigned split_nr : 7;\n \tunsigned size_size : 3;\n+\tunsigned name_size : 3;\n+\tunsigned what_to_do : 5; /* unused */\n \t\n \tuint32_t date;\n \tuint16_t path;\n@@ -63,6 +67,7 @@ struct object_entry {\n \t/* merge paths */\n \t/* split paths */\n \t/* size */\n+\t/* name id */\n };\n \n struct bad_slice {\n@@ -70,16 +75,27 @@ 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 /* list resembles pack index format */\n static uint32_t fanout[0xff + 2];\n \n static unsigned char *idx_map;\n static int idx_size;\n static struct index_header idx_head;\n-static char no_idx, save_unique, add_to_pending;\n-static struct bad_slice *bad_slices;\n+static char no_idx, save_unique, 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 SUPPORTED_REVCACHE_VERSION \t\t1\n@@ -94,8 +110,9 @@ static struct strbuf *g_buffer;\n #define OE_CAST(p)\t((struct object_entry *)(p))\n #define IE_CAST(p)\t((struct index_entry *)(p))\n \n-#define ACTUAL_OBJECT_ENTRY_SIZE(e)\t\t(OE_SIZE + PATH_SIZE((e)->merge_nr + (e)->split_nr) + (e)->size_size)\n-#define ENTRY_SIZE_OFFSET(e)\t\t\t(ACTUAL_OBJECT_ENTRY_SIZE(e) - (e)->size_size)\n+#define ACTUAL_OBJECT_ENTRY_SIZE(e)\t\t(OE_SIZE + PATH_SIZE((e)->merge_nr + (e)->split_nr) + (e)->size_size + (e)->name_size)\n+#define ENTRY_NAME_OFFSET(e)\t\t\t(ACTUAL_OBJECT_ENTRY_SIZE(e) - (e)->name_size)\n+#define ENTRY_SIZE_OFFSET(e)\t\t\t(ENTRY_NAME_OFFSET(e) - (e)->size_size)\n \n #define SLOP\t\t\t5\n \n@@ -167,6 +184,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@@ -296,7 +319,8 @@ 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+\tchar **namep = 0;\n \t\n \tsize = decode_size((unsigned char *)entry + ENTRY_SIZE_OFFSET(entry), entry->size_size);\n \tswitch (entry->type) {\n@@ -309,6 +333,7 @@ static void handle_noncommit(struct rev_info *revs, struct commit *commit, struc\n \t\t\treturn;\n \t\t\n \t\ttree->size = size;\n+\t\tnamep = &tree->name;\n \t\tcommit->tree = tree;\n \t\tobj = (struct object *)tree;\n \t\tbreak;\n@@ -322,6 +347,7 @@ static void handle_noncommit(struct rev_info *revs, struct commit *commit, struc\n \t\t\treturn;\n \t\t\n \t\tblob->size = size;\n+\t\tnamep = &blob->name;\n \t\tobj = (struct object *)blob;\n \t\tbreak;\n \t\t\n@@ -330,6 +356,13 @@ 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 \t/* add to unique list if we're not an end */\n \tif (save_unique && (commit->object.flags & FACE_VALUE)) {\n \t\tif (last_commit != commit) {\n@@ -344,9 +377,20 @@ static void handle_noncommit(struct rev_info *revs, struct commit *commit, struc\n \t\tlast_unique = &(*last_unique)->next;\n \t}\n \t\n+\t/* add cached name */\n+\tif (name_index && namep) {\n+\t\t*namep = cur_name_list->buf + name_index;\n+\t}\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 cache_slice_header *head, unsigned char *map, struct commit *commit, struct commit_list **work, \n@@ -696,15 +740,44 @@ end:\n \treturn retval;\n }\n \n-static int get_cache_slice_header(unsigned char *cache_sha1, unsigned char *map, int len, struct cache_slice_header *head)\n+static struct name_list *get_cache_slice_name_list(struct cache_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 cache_slice_header *head)\n {\n \tint t;\n \t\n-\tmemcpy(head, map, sizeof(struct cache_slice_header));\n+\tif (xread(fd, head, sizeof(struct cache_slice_header)) != sizeof(struct cache_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@@ -713,10 +786,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 cache_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@@ -726,7 +799,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 cache_slice_header head;\n \tstruct rev_cache_info *rci;\n@@ -743,26 +816,31 @@ int traverse_cache_slice(struct rev_info *revs,\n \trci = &revs->rev_cache_info;\n \tsave_unique = rci->save_unique;\n \tadd_to_pending = rci->add_to_pending;\n+\tadd_names = rci->add_names;\n \t\n \tmemset(&head, 0, sizeof(struct cache_slice_header));\n+#\tdefine ERROR(x)\t\tdo { retval = (x); goto end; } while (0);\n \t\n \tfd = open(git_path(\"rev-cache/%s\", sha1_to_hex(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 cache_slice_header))\n-\t\tgoto end;\n+\t\tERROR(-2);\n+\t\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, 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 \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@@ -770,6 +848,7 @@ end:\n \tif (retval)\n \t\tmark_bad_slice(cache_sha1);\n \t\n+#\tundef ERROR\n \treturn retval;\n }\n \n@@ -1081,12 +1160,100 @@ static unsigned long decode_size(unsigned char *str, int len)\n \treturn size;\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+\tchar *ptr;\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(char *name)\n+{\n+\tunsigned int hash = 2166136261ul;\n+\tchar *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(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(entry->ptr, 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+\t\n+\tstrbuf_add(g_name_buffer, name, strlen(name) + 1);\n+\tentry->ptr = g_name_buffer->buf + entry->ind;\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 object_entry *entryp, \n-\tstruct strbuf *merge_str, struct strbuf *split_str)\n+\tstruct strbuf *merge_str, struct strbuf *split_str, char *name)\n {\n \tstruct object_entry entry;\n \tstruct object *obj;\n-\tunsigned char size_str[7];\n+\tunsigned char size_str[7], name_str[7];\n \tunsigned long size;\n \tenum object_type type;\n \t\n@@ -1100,12 +1267,18 @@ static void add_object_entry(const unsigned char *sha1, struct object_entry *ent\n \t\tcase OBJ_COMMIT : \n \t\t\tsize = ((struct commit *)obj)->size;\n \t\t\tbreak;\n-\t\tcase OBJ_TREE : \n-\t\t\tsize = ((struct tree *)obj)->size;\n-\t\t\tbreak;\n-\t\tcase OBJ_BLOB : \n-\t\t\tsize = ((struct blob *)obj)->size;\n-\t\t\tbreak;\n+\t\tcase OBJ_TREE : {\n+\t\t\tstruct tree *tree = (struct tree *)obj;\n+\t\t\tsize = tree->size;\n+\t\t\tif (!name)\n+\t\t\t\tname = tree->name;\n+\t\t} break;\n+\t\tcase OBJ_BLOB : {\n+\t\t\tstruct blob *blob = (struct blob *)obj;\n+\t\t\tsize = blob->size;\n+\t\t\tif (!name)\n+\t\t\t\tname = blob->name;\n+\t\t} break;\n \t\tdefault : \n \t\t\t/* tags are potentially dynamic metadata; they don't really belong here */\n \t\t\treturn;\n@@ -1136,6 +1309,9 @@ static void add_object_entry(const unsigned char *sha1, struct object_entry *ent\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@@ -1145,6 +1321,9 @@ static void add_object_entry(const unsigned char *sha1, struct object_entry *ent\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@@ -1189,6 +1368,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@@ -1202,6 +1384,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@@ -1214,12 +1399,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@@ -1231,7 +1419,7 @@ static int add_unique_objects(struct commit *commit)\n \t\tolist = commit->unique;\n \t\ti = 0;\n \t\twhile (olist) {\n-\t\t\tadd_object_entry(olist->item->sha1, 0, 0, 0);\n+\t\t\tadd_object_entry(olist->item->sha1, 0, 0, 0, 0 /* retrieved with size in function */);\n \t\t\ti++;\n \t\t\tolist = olist->next;\n \t\t}\n@@ -1242,13 +1430,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@@ -1259,20 +1451,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@@ -1289,16 +1481,19 @@ 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));\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);\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 void init_revcache_directory(void)\n@@ -1319,6 +1514,7 @@ void init_rci(struct rev_cache_info *rci)\n \t\n \trci->save_unique = 0;\n \trci->add_to_pending = 1;\n+\trci->add_names = 1;\n \t\n \trci->ignore_size = 0;\n }\n@@ -1333,9 +1529,9 @@ int make_cache_slice(struct rev_cache_info *rci,\n \tstruct cache_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], *newfile, null;\n \tstruct rev_cache_info *trci, def_rci;\n \tgit_SHA_CTX ctx;\n \t\n@@ -1353,7 +1549,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@@ -1384,6 +1586,7 @@ int make_cache_slice(struct rev_cache_info *rci,\n \ttrci = &revs->rev_cache_info;\n \tinit_rci(trci);\n \ttrci->save_unique = 1;\n+\ttrci->add_names = 1;\n \ttrci->add_to_pending = 0;\n \t\n \tsetup_revisions(0, 0, revs, 0);\n@@ -1414,7 +1617,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);\n \t\tobject_nr++;\n \t\t\n \t\tif (rci->objects && !(commit->object.flags & TREESAME) && !object.is_end)\n@@ -1434,10 +1637,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)\ndiff --git a/revision.h b/revision.h\nindex d97ac8c..5114208 100644\n--- a/revision.h\n+++ b/revision.h\n@@ -27,7 +27,8 @@ struct rev_cache_info {\n \t\n \t/* traversal flags */\n \tunsigned save_unique : 1, \n-\t\tadd_to_pending : 1;\n+\t\tadd_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 561810f..3836596 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: (c47593c..) t/revcache/names (depends on: t/revcache/docs)\n"},{"id":"120796","messageId":"op.uyr1clpjtdk399@sirnot.private","threadId":"20471","inReplyTo":"op.uyb1vs0htdk399@sirnot.private","subject":"Re: [PATCH 6/6 (v2)] support for path name caching of blobs/trees in rev-cache","fromName":"Nick Edelen","fromEmail":"sirnot@gmail.com","sentAt":"2009-08-16T22:42:11Z","receivedAt":"2009-08-16T22:42:11Z","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: (e6091b4..) t/revcache/names (depends on: t/revcache/docs)\n"}]}