{"thread":{"id":"20468","subject":"[PATCH 4/6 (v2)] administrative functions for rev-cache, and start of integration into git","startedAt":"2009-08-08T07:31:50Z","lastAt":"2009-08-16T22:42:02Z","messageCount":4,"participants":["Nick Edelen","Junio C Hamano"],"isPatch":true,"patchVersion":2,"patchTotal":6},"messages":[{"id":"119965","messageId":"op.uyb1vcvytdk399@sirnot.private","threadId":"20468","inReplyTo":null,"subject":"[PATCH 4/6 (v2)] administrative functions for rev-cache, and start of integration into git","fromName":"Nick Edelen","fromEmail":"sirnot@gmail.com","sentAt":"2009-08-08T07:31:50Z","receivedAt":"2009-08-08T07:31:50Z","isPatch":true,"sender":{"key":"sirnot@gmail.com","avatar":null},"body":"This patch contains miscellaneous (maintenance) features:\n - support for cache slice fusion, index regeneration and object size caching\n - extra 'size' field added to commit, tag and blob objects, initialized in \n   parse_* functions and cache traversal\n - non-commit object generation refactored to take advantage of 'size' field\n - porcelain updated to support feature additions\n\nThe beginnings of integration into git are present in this patch, mainly \ncentered on caching object size; the object generation is refactored to more \nelegantly exploit this.  Fusion allows smaller (incremental) slices to be \ncoagulated into a larger slice, reducing overhead, while index regeneration \nenables repair or cleaning of the cache index.\n\nNote that tests for these features are included in the following patch, as they \ntake advantage of the rev-cache's integration into the revision walker.\n\nSigned-off-by: Nick Edelen <sirnot@gmail.com>\n\n---\n4/5 previously.  Small adjustment in parsing of --ignore-size field in porcelain.\n\n blob.c              |    1 +\n blob.h              |    1 +\n builtin-rev-cache.c |   73 +++++++++-\n commit.c            |    1 +\n commit.h            |    1 +\n rev-cache.c         |  417 +++++++++++++++++++++++++++++++++++++++++---------\n revision.h          |    4 +-\n 7 files changed, 421 insertions(+), 77 deletions(-)\n\ndiff --git a/blob.c b/blob.c\nindex bd7d078..e1bab3f 100644\n--- a/blob.c\n+++ b/blob.c\n@@ -21,6 +21,7 @@ struct blob *lookup_blob(const unsigned char *sha1)\n int parse_blob_buffer(struct blob *item, void *buffer, unsigned long size)\n {\n \titem->object.parsed = 1;\n+\titem->size = size;\n \treturn 0;\n }\n \ndiff --git a/blob.h b/blob.h\nindex ea5d9e9..d8db96a 100644\n--- a/blob.h\n+++ b/blob.h\n@@ -7,6 +7,7 @@ extern const char *blob_type;\n \n struct blob {\n \tstruct object object;\n+\tunsigned long size;\n };\n \n struct blob *lookup_blob(const unsigned char *sha1);\ndiff --git a/builtin-rev-cache.c b/builtin-rev-cache.c\nindex 2338871..532ec9f 100755\n--- a/builtin-rev-cache.c\n+++ b/builtin-rev-cache.c\n@@ -4,6 +4,8 @@\n #include \"diff.h\"\n #include \"revision.h\"\n \n+#define DEFAULT_IGNORE_SLICE_SIZE\t\t\"30mb\"\n+\n /* porcelain for rev-cache.c */\n static int handle_add(int argc, const char *argv[]) /* args beyond this command */\n {\n@@ -21,7 +23,7 @@ static int handle_add(int argc, const char *argv[]) /* args beyond this command\n \t\tif (!strcmp(argv[i], \"--stdin\"))\n \t\t\tdostdin = 1;\n \t\telse if (!strcmp(argv[i], \"--fresh\"))\n-\t\t\tstarts_from_slices(&revs, UNINTERESTING);\n+\t\t\tstarts_from_slices(&revs, UNINTERESTING, 0, 0);\n \t\telse if (!strcmp(argv[i], \"--not\"))\n \t\t\tflags ^= UNINTERESTING;\n \t\telse if (!strcmp(argv[i], \"--legs\"))\n@@ -141,6 +143,71 @@ static int handle_walk(int argc, const char *argv[])\n \treturn 0;\n }\n \n+static unsigned int parse_size(const char *name)\n+{\n+\tunsigned int size;\n+\tchar *p;\n+\t\n+\tsize = strtol(name, &p, 10);\n+\tswitch (*p) {\n+\tcase 'k' : \n+\tcase 'K' : \n+\t\tsize *= 0x400;\n+\t\tbreak;\n+\tcase 'm' : \n+\tcase 'M' : \n+\t\tsize *= 0x100000;\n+\t\tbreak;\n+\tdefault : \n+\t\tbreak;\n+\t}\n+\t\n+\treturn size;\n+}\n+\n+static int handle_fuse(int argc, const char *argv[])\n+{\n+\tstruct rev_info revs;\n+\tstruct rev_cache_info rci;\n+\tconst char *args[5];\n+\tint i, argn = 0;\n+\tchar add_all = 0;\n+\t\n+\tinit_revisions(&revs, 0);\n+\tinit_rci(&rci);\n+\targs[argn++] = \"rev-list\";\n+\t\n+\tfor (i = 0; i < argc; i++) {\n+\t\tif (!strcmp(argv[i], \"--all\")) {\n+\t\t\targs[argn++] = \"--all\";\n+\t\t\tsetup_revisions(argn, args, &revs, 0);\n+\t\t\tadd_all = 1;\n+\t\t} else if (!strcmp(argv[i], \"--noobjects\")) \n+\t\t\trci.objects = 0;\n+\t\telse if (!strncmp(argv[i], \"--ignore-size\", 13)) {\n+\t\t\tunsigned int sz;\n+\t\t\t\n+\t\t\tif (argv[i][13] == '=')\n+\t\t\t\tsz = parse_size(argv[i] + 14);\n+\t\t\telse\n+\t\t\t\tsz = parse_size(DEFAULT_IGNORE_SLICE_SIZE);\n+\t\t\t\n+\t\t\trci.ignore_size = sz;\n+\t\t} else \n+\t\t\tcontinue;\n+\t}\n+\t\n+\tif (!add_all)\n+\t\tstarts_from_slices(&revs, 0, 0, 0);\n+\t\n+\treturn coagulate_cache_slices(&rci, &revs);\n+}\n+\n+static int handle_index(int argc, const char *argv[])\n+{\n+\treturn regenerate_cache_index(0);\n+}\n+\n static int handle_help(void)\n {\n \tchar *usage = \"\\\n@@ -186,8 +253,12 @@ int cmd_rev_cache(int argc, const char *argv[], const char *prefix)\n \targv += 2;\n \tif (!strcmp(arg, \"add\"))\n \t\tr = handle_add(argc, argv);\n+\telse if (!strcmp(arg, \"fuse\"))\n+\t\tr = handle_fuse(argc, argv);\n \telse if (!strcmp(arg, \"walk\"))\n \t\tr = handle_walk(argc, argv);\n+\telse if (!strcmp(arg, \"index\"))\n+\t\tr = handle_index(argc, argv);\n \telse\n \t\treturn handle_help();\n \t\ndiff --git a/commit.c b/commit.c\nindex 65d223e..afe504f 100644\n--- a/commit.c\n+++ b/commit.c\n@@ -243,6 +243,7 @@ int parse_commit_buffer(struct commit *item, void *buffer, unsigned long size)\n \tif (item->object.parsed)\n \t\treturn 0;\n \titem->object.parsed = 1;\n+\titem->size = size;\n \ttail += size;\n \tif (tail <= bufptr + 46 || memcmp(bufptr, \"tree \", 5) || bufptr[45] != '\\n')\n \t\treturn error(\"bogus commit object %s\", sha1_to_hex(item->object.sha1));\ndiff --git a/commit.h b/commit.h\nindex ba9f638..0529fcf 100644\n--- a/commit.h\n+++ b/commit.h\n@@ -19,6 +19,7 @@ struct commit {\n \tstruct commit_list *parents;\n \tstruct tree *tree;\n \tchar *buffer;\n+\tunsigned long size;\n };\n \n extern int save_commit_buffer;\ndiff --git a/rev-cache.c b/rev-cache.c\nindex cd618cf..1d29f8e 100755\n--- a/rev-cache.c\n+++ b/rev-cache.c\n@@ -8,6 +8,7 @@\n #include \"diff.h\"\n #include \"revision.h\"\n #include \"run-command.h\"\n+#include \"string-list.h\"\n \n \n /* single index maps objects to cache files */\n@@ -88,6 +89,7 @@ static struct strbuf *g_buffer;\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 \n #define SLOP\t\t5\n \n@@ -219,7 +221,6 @@ unsigned char *get_cache_slice(struct commit *commit)\n \t\treturn 0;\n \t\n \tie = search_index(commit->object.sha1);\n-\t\n \tif (ie && ie->cache_index < idx_head.cache_nr)\n \t\treturn idx_caches + ie->cache_index * 20;\n \t\n@@ -229,27 +230,46 @@ unsigned char *get_cache_slice(struct commit *commit)\n \n /* traversal */\n \n-static void handle_noncommit(struct rev_info *revs, struct object_entry *entry)\n+static unsigned long decode_size(unsigned char *str, int len);\n+\n+static void handle_noncommit(struct rev_info *revs, struct commit *commit, struct object_entry *entry)\n {\n-\tstruct object *obj = 0;\n+\tstruct blob *blob;\n+\tstruct tree *tree;\n+\tstruct object *obj;\n+\tunsigned long size;\n \t\n+\tsize = decode_size((unsigned char *)entry + ENTRY_SIZE_OFFSET(entry), entry->size_size);\n \tswitch (entry->type) {\n \tcase OBJ_TREE : \n-\t\tif (revs->tree_objects)\n-\t\t\tobj = (struct object *)lookup_tree(entry->sha1);\n+\t\tif (!revs->tree_objects)\n+\t\t\treturn;\n+\t\t\n+\t\ttree = lookup_tree(entry->sha1);\n+\t\tif (!tree)\n+\t\t\treturn;\n+\t\t\n+\t\ttree->size = size;\n+\t\tcommit->tree = tree;\n+\t\tobj = (struct object *)tree;\n \t\tbreak;\n+\t\n \tcase OBJ_BLOB : \n-\t\tif (revs->blob_objects)\n-\t\t\tobj = (struct object *)lookup_blob(entry->sha1);\n-\t\tbreak;\n-\tcase OBJ_TAG : \n-\t\tif (revs->tag_objects)\n-\t\t\tobj = (struct object *)lookup_tag(entry->sha1);\n+\t\tif (!revs->blob_objects)\n+\t\t\treturn;\n+\t\t\n+\t\tblob = lookup_blob(entry->sha1);\n+\t\tif (!blob)\n+\t\t\treturn;\n+\t\t\n+\t\tblob->size = size;\n+\t\tobj = (struct object *)blob;\n \t\tbreak;\n-\t}\n-\t\n-\tif (!obj)\n+\t\t\n+\tdefault : \n+\t\t/* tag objects aren't really supposed to be here */\n \t\treturn;\n+\t}\n \t\n \tobj->flags |= FACE_VALUE;\n \tadd_pending_object(revs, obj, \"\");\n@@ -262,7 +282,6 @@ static int setup_traversal(struct cache_slice_header *head, unsigned char *map,\n \tstruct commit_list *prev, *wp, **wpp;\n \tint retval;\n \t\n-\t/* printf(\"adding %s\\n\", sha1_to_hex(commit->object.sha1)); */\n \tiep = search_index(commit->object.sha1);\n \toep = OE_CAST(map + ntohl(iep->pos));\n \toep->include = 1;\n@@ -338,7 +357,7 @@ static int traverse_cache_slice_1(struct cache_slice_header *head, unsigned char\n \t\t/* add extra objects if necessary */\n \t\tif (entry->type != OBJ_COMMIT) {\n \t\t\tif (consume_children)\n-\t\t\t\thandle_noncommit(revs, entry);\n+\t\t\t\thandle_noncommit(revs, co, entry);\n \t\t\t\n \t\t\tcontinue;\n \t\t} else\n@@ -372,6 +391,8 @@ static int traverse_cache_slice_1(struct cache_slice_header *head, unsigned char\n \t\t\tif (last_objects[path]) {\n \t\t\t\tparse_commit(last_objects[path]);\n \t\t\t\t\n+\t\t\t\t/* we needn't worry about the unique field; that will be valid as \n+\t\t\t\t * long as we're not a end entry */\n \t\t\t\tlast_objects[path]->object.flags &= ~FACE_VALUE;\n \t\t\t\tlast_objects[path] = 0;\n \t\t\t}\n@@ -554,6 +575,68 @@ end:\n \n /* generation */\n \n+static int is_endpoint(struct commit *commit)\n+{\n+\tstruct commit_list *list = commit->parents;\n+\t\n+\twhile (list) {\n+\t\tif (!(list->item->object.flags & UNINTERESTING))\n+\t\t\treturn 0;\n+\t\t\n+\t\tlist = list->next;\n+\t}\n+\t\n+\treturn 1;\n+}\n+\n+/* ensures branch is self-contained: parents are either all interesting or all uninteresting */\n+static void make_legs(struct rev_info *revs)\n+{\n+\tstruct commit_list *list, **plist;\n+\tint total = 0;\n+\t\n+\t/* attach plist to end of commits list */\n+\tlist = revs->commits;\n+\twhile (list && list->next)\n+\t\tlist = list->next;\n+\t\n+\tif (list)\n+\t\tplist = &list->next;\n+\telse\n+\t\treturn;\n+\t\n+\t/* duplicates don't matter, as get_revision() ignores them */\n+\tfor (list = revs->commits; list; list = list->next) {\n+\t\tstruct commit *item = list->item;\n+\t\tstruct commit_list *parents = item->parents;\n+\t\t\n+\t\tif (item->object.flags & UNINTERESTING)\n+\t\t\tcontinue;\n+\t\tif (is_endpoint(item))\n+\t\t\tcontinue;\n+\t\t\n+\t\twhile (parents) {\n+\t\t\tstruct commit *p = parents->item;\n+\t\t\tparents = parents->next;\n+\t\t\t\n+\t\t\tif (!(p->object.flags & UNINTERESTING))\n+\t\t\t\tcontinue;\n+\t\t\t\n+\t\t\tp->object.flags &= ~UNINTERESTING;\n+\t\t\tparse_commit(p);\n+\t\t\tplist = &commit_list_insert(p, plist)->next;\n+\t\t\t\n+\t\t\tif (!(p->object.flags & SEEN))\n+\t\t\t\ttotal++;\n+\t\t}\n+\t}\n+\t\n+\tif (total)\n+\t\tsort_in_topological_order(&revs->commits, 1);\n+\t\n+}\n+\n+\n struct path_track {\n \tstruct commit *commit;\n \tint path; /* for decrementing paths */\n@@ -768,31 +851,97 @@ static void handle_paths(struct commit *commit, struct object_entry *object, str\n }\n \n \n-static void add_object_entry(const unsigned char *sha1, int type, struct object_entry *nothisone, \n+static int encode_size(unsigned long size, unsigned char *out)\n+{\n+\tint len = 0;\n+\t\n+\twhile (size) {\n+\t\t*out++ = (unsigned char)(size & 0xff);\n+\t\tsize >>= 8;\n+\t\tlen++;\n+\t}\n+\t\n+\treturn len;\n+}\n+\n+static unsigned long decode_size(unsigned char *str, int len)\n+{\n+\tunsigned long size = 0;\n+\tint shift = 0;\n+\t\n+\twhile (len--) {\n+\t\tsize |= (unsigned long)*str << shift;\n+\t\tshift += 8;\n+\t\tstr++;\n+\t}\n+\t\n+\treturn size;\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 {\n-\tstruct object_entry object;\n+\tstruct object_entry entry;\n+\tstruct object *obj;\n+\tunsigned char size_str[7];\n+\tunsigned long size;\n+\tenum object_type type;\n+\t\n+\tif (entryp)\n+\t\tsha1 = entryp->sha1;\n+\t\n+\tobj = lookup_object(sha1);\n+\tif (obj) {\n+\t\t/* it'd be smoother to have the size in the object... */\n+\t\tswitch (obj->type) {\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\tdefault : \n+\t\t\t/* tags are potentially dynamic metadata; they don't really belong here */\n+\t\t\treturn;\n+\t\t}\n+\t\t\n+\t\ttype = obj->type;\n+\t}\n \t\n-\tif (!nothisone) {\n-\t\tmemset(&object, 0, sizeof(object));\n-\t\thashcpy(object.sha1, sha1);\n-\t\tobject.type = type;\n+\tif (!obj || !size) {\n+\t\tvoid *data = read_sha1_file(sha1, &type, &size);\n+\t\t\n+\t\tif (data)\n+\t\t\tfree(data);\n+\t}\n+\t\n+\tif (!entryp) {\n+\t\tmemset(&entry, 0, sizeof(entry));\n+\t\thashcpy(entry.sha1, sha1);\n+\t\tentry.type = type;\n \t\t\n \t\tif (merge_str)\n-\t\t\tobject.merge_nr = merge_str->len / PATH_WIDTH;\n+\t\t\tentry.merge_nr = merge_str->len / PATH_WIDTH;\n \t\tif (split_str)\n-\t\t\tobject.split_nr = split_str->len / PATH_WIDTH;\n+\t\t\tentry.split_nr = split_str->len / PATH_WIDTH;\n \t\t\n-\t\tnothisone = &object;\n+\t\tentryp = &entry;\n \t}\n \t\n-\tstrbuf_add(g_buffer, nothisone, sizeof(object));\n+\tentryp->size_size = encode_size(size, size_str);\n+\t\n+\t/* write the muvabitch */\n+\tstrbuf_add(g_buffer, entryp, sizeof(entry));\n \t\n-\tif (merge_str && merge_str->len)\n+\tif (merge_str)\n \t\tstrbuf_add(g_buffer, merge_str->buf, merge_str->len);\n-\tif (split_str && split_str->len)\n+\tif (split_str)\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 }\n \n /* returns non-zero to continue parsing, 0 to skip */\n@@ -836,12 +985,7 @@ continue_loop:\n \n static int dump_tree_callback(const unsigned char *sha1, const char *path, unsigned int mode)\n {\n-\tunsigned char data[21];\n-\t\n-\thashcpy(data, sha1);\n-\tdata[20] = !!S_ISDIR(mode);\n-\t\n-\tstrbuf_add(g_buffer, data, 21);\n+\tstrbuf_add(g_buffer, sha1, 20);\n \t\n \treturn 1;\n }\n@@ -851,15 +995,10 @@ static void tree_addremove(struct diff_options *options,\n \tconst unsigned char *sha1,\n \tconst char *concatpath)\n {\n-\tunsigned char data[21];\n-\t\n \tif (whatnow != '+')\n \t\treturn;\n \t\n-\thashcpy(data, sha1);\n-\tdata[20] = !!S_ISDIR(mode);\n-\t\n-\tstrbuf_add(g_buffer, data, 21);\n+\tstrbuf_add(g_buffer, sha1, 20);\n }\n \n static void tree_change(struct diff_options *options,\n@@ -868,26 +1007,10 @@ static void tree_change(struct diff_options *options,\n \tconst unsigned char *new_sha1,\n \tconst char *concatpath)\n {\n-\tunsigned char data[21];\n-\t\n \tif (!hashcmp(old_sha1, new_sha1))\n \t\treturn;\n \t\n-\thashcpy(data, new_sha1);\n-\tdata[20] = !!S_ISDIR(new_mode);\n-\t\n-\tstrbuf_add(g_buffer, data, 21);\n-}\n-\n-static int sort_type_hash(const void *a, const void *b)\n-{\n-\tconst unsigned char *sa = (const unsigned char *)a, \n-\t\t*sb = (const unsigned char *)b;\n-\t\n-\tif (sa[20] == sb[20])\n-\t\treturn hashcmp(sa, sb);\n-\t\n-\treturn sa[20] > sb[20] ? -1 : 1;\n+\tstrbuf_add(g_buffer, new_sha1, 20);\n }\n \n static int add_unique_objects(struct commit *commit)\n@@ -898,6 +1021,7 @@ static int add_unique_objects(struct commit *commit)\n \tint i, j, next;\n \tchar is_first = 1;\n \t\n+\t/* ...no, calculate unique objects */\n \tstrbuf_init(&os, 0);\n \tstrbuf_init(&ost, 0);\n \torig_buf = g_buffer;\n@@ -917,20 +1041,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 / 21, 21, (int (*)(const void *, const void *))hashcmp);\n+\t\tqsort(g_buffer->buf, g_buffer->len / 20, 20, (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 += 21) {\n+\t\t\tfor (next = i = j = 0; i < os.len; i += 20) {\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 += 21;\n+\t\t\t\t\tj += 20;\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, 21);\n-\t\t\t\tnext += 21;\n+\t\t\t\t\tmemcpy(os.buf + next, os.buf + i, 20);\n+\t\t\t\tnext += 20;\n \t\t\t}\n \t\t\t\n \t\t\tif (next != i)\n@@ -939,22 +1063,21 @@ static int add_unique_objects(struct commit *commit)\n \t\t\tis_first = 0;\n \t}\n \t\n+\t/* no parents (!) */\n \tif (is_first) {\n \t\tg_buffer = &os;\n \t\tdump_tree(commit->tree, dump_tree_callback);\n \t}\n \t\n-\tif (os.len)\n-\t\tqsort(os.buf, os.len / 21, 21, sort_type_hash);\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 += 21)\n-\t\tadd_object_entry((unsigned char *)(os.buf + i), os.buf[i + 20] ? OBJ_TREE : OBJ_BLOB, 0, 0, 0);\n+\tfor (i = 0; i < os.len; i += 20)\n+\t\tadd_object_entry((unsigned char *)(os.buf + i), 0, 0, 0);\n \t\n \tstrbuf_release(&ost);\n \tstrbuf_release(&os);\n \t\n-\treturn 0;\n+\treturn i / 20;\n }\n \n static void init_revcache_directory(void)\n@@ -1046,6 +1169,9 @@ int make_cache_slice(struct rev_cache_info *rci,\n \tif (prepare_revision_walk(revs))\n \t\tdie(\"died preparing revision walk\");\n \t\n+\tif (rci->legs)\n+\t\tmake_legs(revs);\n+\t\n \tobject_nr = total_sz = 0;\n \twhile ((commit = get_revision(revs)) != 0) {\n \t\tstruct object_entry object;\n@@ -1067,12 +1193,12 @@ 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, 0, &object, &merge_paths, &split_paths);\n+\t\tadd_object_entry(0, &object, &merge_paths, &split_paths);\n \t\tobject_nr++;\n \t\t\n-\t\tif (!(commit->object.flags & TREESAME)) {\n+\t\tif (rci->objects && !(commit->object.flags & TREESAME)) {\n \t\t\t/* add all unique children for this commit */\n-\t\t\tadd_object_entry(commit->tree->object.sha1, OBJ_TREE, 0, 0, 0);\n+\t\t\tadd_object_entry(commit->tree->object.sha1, 0, 0, 0);\n \t\t\tobject_nr++;\n \t\t\t\n \t\t\tif (!object.is_end)\n@@ -1260,7 +1386,7 @@ int make_cache_index(struct rev_cache_info *rci, unsigned char *cache_sha1,\n \t\t * should we allow more intelligent overriding? */\n \t\tdate = ntohl(object_entry->date);\n \t\tif (date > idx_head.max_date) {\n- \t\t\tentry = 0;\n+\t\t\tentry = 0;\n \t\t\tif (date > max_date)\n \t\t\t\tmax_date = date;\n \t\t} else\n@@ -1316,8 +1442,7 @@ int make_cache_index(struct rev_cache_info *rci, unsigned char *cache_sha1,\n }\n \n \n-/* add start-commits from each cache slice (uninterestingness will be propogated) */\n-void starts_from_slices(struct rev_info *revs, unsigned int flags)\n+void starts_from_slices(struct rev_info *revs, unsigned int flags, unsigned char *which, int n)\n {\n \tstruct commit *commit;\n \tint i;\n@@ -1327,13 +1452,24 @@ void starts_from_slices(struct rev_info *revs, unsigned int flags)\n \tif (!idx_map)\n \t\treturn;\n \t\n-\t/* haven't implemented which yet; no need really... */\n \tfor (i = idx_head.ofs_objects; i < idx_size; i += IE_SIZE) {\n \t\tstruct index_entry *entry = IE_CAST(idx_map + i);\n \t\t\n \t\tif (!entry->is_start)\n \t\t\tcontinue;\n \t\t\n+\t\t/* only include entries in 'which' slices */\n+\t\tif (n) {\n+\t\t\tint j;\n+\t\t\t\n+\t\t\tfor (j = 0; j < n; j++)\n+\t\t\t\tif (!hashcmp(idx_caches + entry->cache_index * 20, which + j * 20))\n+\t\t\t\t\tbreak;\n+\t\t\t\n+\t\t\tif (j == n)\n+\t\t\t\tcontinue;\n+\t\t}\n+\t\t\n \t\tcommit = lookup_commit(entry->sha1);\n \t\tif (!commit)\n \t\t\tcontinue;\n@@ -1343,3 +1479,134 @@ void starts_from_slices(struct rev_info *revs, unsigned int flags)\n \t}\n \t\n }\n+\n+\n+/* the most work-intensive attributes in the cache are the unique objects and size, both \n+ * of which can be re-used.  although path structures will be isomorphic, path generation is \n+ * not particularly expensive, and at any rate we need to re-sort the commits */\n+int coagulate_cache_slices(struct rev_cache_info *rci, struct rev_info *revs)\n+{\n+\tunsigned char cache_sha1[20];\n+\tchar base[PATH_MAX];\n+\tint fd, baselen, i;\n+\tstruct stat fi;\n+\tstruct string_list files = {0, 0, 0, 1}; /* dup */\n+\tstruct strbuf ignore;\n+\tDIR *dirh;\n+\t\n+\tstrbuf_init(&ignore, 0);\n+\tstrncpy(base, git_path(\"rev-cache\"), sizeof(base));\n+\tbaselen = strlen(base);\n+\t\n+\t/* enumerate files */\n+\tdirh = opendir(base);\n+\tif (dirh) {\n+\t\tstruct dirent *de;\n+\t\t\n+\t\twhile ((de = readdir(dirh))) {\n+\t\t\tif (de->d_name[0] == '.')\n+\t\t\t\tcontinue;\n+\t\t\t\n+\t\t\tbase[baselen] = '/';\n+\t\t\tstrncpy(base + baselen + 1, de->d_name, sizeof(base) - baselen - 1);\n+\t\t\t\n+\t\t\t/* _theoretically_ it is possible a slice < ignore_size to map objects not covered by, yet reachable from, \n+\t\t\t * a slice >= ignore_size, meaning that we could potentially delete an 'unfused' slice; but if that \n+\t\t\t * ever *did* happen their cache structure'd be so fucked up they might as well refuse the entire thing.\n+\t\t\t * and at any rate the worst it'd do is make rev-list revert to standard walking in that (small) bit.\n+\t\t\t */\n+\t\t\tif (rci->ignore_size) {\n+\t\t\t\tunsigned char sha1[20];\n+\t\t\t\t\n+\t\t\t\tif (stat(base, &fi))\n+\t\t\t\t\twarning(\"can't query file %s\\n\", base);\n+\t\t\t\telse if (fi.st_size >= rci->ignore_size && !get_sha1_hex(de->d_name, sha1)) {\n+\t\t\t\t\tstrbuf_add(&ignore, sha1, 20);\n+\t\t\t\t\tcontinue;\n+\t\t\t\t}\n+\t\t\t}\n+\t\t\t\n+\t\t\tstring_list_insert(base, &files);\n+\t\t}\n+\t\t\n+\t\tclosedir(dirh);\n+\t}\n+\t\n+\tif (ignore.len) {\n+\t\tstarts_from_slices(revs, UNINTERESTING, (unsigned char *)ignore.buf, ignore.len / 20);\n+\t\tstrbuf_release(&ignore);\n+\t}\n+\t\n+\trci->make_index = 0;\n+\tif (make_cache_slice(rci, revs, 0, 0, cache_sha1) < 0)\n+\t\tdie(\"can't make cache slice\");\n+\t\n+\t/* clean up time! */\n+\tcleanup_cache_slices();\n+\t\n+\tfor (i = 0; i < files.nr; i++) {\n+\t\tchar *name = files.items[i].string;\n+\t\t\n+\t\tfprintf(stderr, \"removing %s\\n\", name);\n+\t\tunlink_or_warn(name);\n+\t}\n+\t\n+\tstring_list_clear(&files, 0);\n+\t\n+\tfd = open(git_path(\"rev-cache/%s\", sha1_to_hex(cache_sha1)), O_RDWR);\n+\tif (fd < 0 || fstat(fd, &fi))\n+\t\tdie(\"what?  I can't open/query the cache I just generated\");\n+\t\n+\tif (make_cache_index(rci, cache_sha1, fd, fi.st_size) < 0)\n+\t\tdie(\"can't make new index\");\n+\t\n+\tclose(fd);\n+\t\n+\treturn 0;\n+}\n+\n+int regenerate_cache_index(struct rev_cache_info *rci)\n+{\n+\tDIR *dirh;\n+\tchar base[PATH_MAX];\n+\tint baselen;\n+\t\n+\t/* first remove old index if it exists */\n+\tunlink_or_warn(git_path(\"rev-cache/index\"));\n+\t\n+\tstrncpy(base, git_path(\"rev-cache\"), sizeof(base));\n+\tbaselen = strlen(base);\n+\t\n+\tdirh = opendir(base);\n+\tif (dirh) {\n+\t\tstruct dirent *de;\n+\t\tstruct stat fi;\n+\t\tint fd;\n+\t\tunsigned char sha1[20];\n+\t\t\n+\t\twhile ((de = readdir(dirh))) {\n+\t\t\tif (de->d_name[0] == '.')\n+\t\t\t\tcontinue;\n+\t\t\t\n+\t\t\tif (get_sha1_hex(de->d_name, sha1))\n+\t\t\t\tcontinue;\n+\t\t\t\n+\t\t\tbase[baselen] = '/';\n+\t\t\tstrncpy(base + baselen + 1, de->d_name, sizeof(base) - baselen - 1);\n+\t\t\t\n+\t\t\t/* open with RDWR because of mmap call in make_cache_index() */\n+\t\t\tfd = open(base, O_RDWR);\n+\t\t\tif (fd < 0 || fstat(fd, &fi))\n+\t\t\t\twarning(\"bad cache found [%s]; fuse recommended\", de->d_name);\n+\t\t\t\n+\t\t\tif (make_cache_index(rci, sha1, fd, fi.st_size) < 0)\n+\t\t\t\tdie(\"error writing cache\");\n+\t\t\t\n+\t\t\tclose(fd);\n+\t\t}\n+\t\t\n+\t\tclosedir(dirh);\n+\t}\n+\t\n+\treturn 0;\n+}\n\\ No newline at end of file\ndiff --git a/revision.h b/revision.h\nindex 200042a..d97ac8c 100644\n--- a/revision.h\n+++ b/revision.h\n@@ -207,6 +207,8 @@ extern int make_cache_slice(struct rev_cache_info *rci,\n extern int make_cache_index(struct rev_cache_info *rci, unsigned char *cache_sha1, \n \tint fd, unsigned int size);\n \n-extern void starts_from_slices(struct rev_info *revs, unsigned int flags);\n+extern void starts_from_slices(struct rev_info *revs, unsigned int flags, unsigned char *which, int n);\n+extern int coagulate_cache_slices(struct rev_cache_info *rci, struct rev_info *revs);\n+extern int regenerate_cache_index(struct rev_cache_info *rci);\n \n #endif\n-- \ntg: (9861015..) t/revcache/misc (depends on: t/revcache/objects)\n"},{"id":"120071","messageId":"7vtz0g7s1p.fsf@alter.siamese.dyndns.org","threadId":"20468","inReplyTo":"op.uyb1vcvytdk399@sirnot.private","subject":"Re: [PATCH 4/6 (v2)] administrative functions for rev-cache, and start of integration into git","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2009-08-09T18:36:50Z","receivedAt":"2009-08-09T18:36:50Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Nick Edelen\" <sirnot@gmail.com> writes:\n\nNote that I didn't read the entire patch, so the parts I did not comment\non in this message may or may not have problematic parts.\n\n>  - extra 'size' field added to commit, tag and blob objects, initialized in \n>    parse_* functions and cache traversal\n\nIt is unclear which \"size\" this field refers to without comment.\n\nI do not know if this change is justifiable.  We (mostly Linus) spent\nconsiderble effort to shrink the memory footprint of struct commit (and\nstruct object in general) exactly because revision traversal needs to\ninspect tons of them.\n\n> +static unsigned int parse_size(const char *name)\n> +{\n> +\tunsigned int size;\n> +\tchar *p;\n> +\t\n> +\tsize = strtol(name, &p, 10);\n> +\tswitch (*p) {\n> +\tcase 'k' : \n> +\tcase 'K' : \n> +\t\tsize *= 0x400;\n> +\t\tbreak;\n> +\tcase 'm' : \n> +\tcase 'M' : \n> +\t\tsize *= 0x100000;\n> +\t\tbreak;\n> +\tdefault : \n> +\t\tbreak;\n> +\t}\n> +\t\n> +\treturn size;\n> +}\n\nLooks vaguely familiar.\n\nThe configuration parser already knows about these size suffixes when told\nto read \"int\".  Can't that code, e.g. git_parse_ulong(), be reused here?\n\n> @@ -219,7 +221,6 @@ unsigned char *get_cache_slice(struct commit *commit)\n>  \t\treturn 0;\n>  \t\n>  \tie = search_index(commit->object.sha1);\n> -\t\n>  \tif (ie && ie->cache_index < idx_head.cache_nr)\n>  \t\treturn idx_caches + ie->cache_index * 20;\n\n\"Oops, fix an earlier mistake\"...\n\n> @@ -262,7 +282,6 @@ static int setup_traversal(struct cache_slice_header *head, unsigned char *map,\n>  \tstruct commit_list *prev, *wp, **wpp;\n>  \tint retval;\n>  \t\n> -\t/* printf(\"adding %s\\n\", sha1_to_hex(commit->object.sha1)); */\n\nLikewise.\n"},{"id":"120244","messageId":"c77435a80908110249y1ce82dd4n77b3b81e532daeea@mail.gmail.com","threadId":"20468","inReplyTo":"7vtz0g7s1p.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH 4/6 (v2)] administrative functions for rev-cache, and start of integration into git","fromName":"Nick Edelen","fromEmail":"sirnot@gmail.com","sentAt":"2009-08-11T09:49:49Z","receivedAt":"2009-08-11T09:49:49Z","isPatch":true,"sender":{"key":"sirnot@gmail.com","avatar":null},"body":"> It is unclear which \"size\" this field refers to without comment.\n>\n> I do not know if this change is justifiable.  We (mostly Linus) spent\n> considerble effort to shrink the memory footprint of struct commit (and\n> struct object in general) exactly because revision traversal needs to\n> inspect tons of them.\n\nI originally added a `size` field to objects, a `unique` field to\ncommits and `name` ones to blobs/trees.  This was (I reasoned) partly\nfor applications to take fuller advantage of rev-cache's abilities,\nbut largely to ease re-use of its information in slice regeneration.\n\nHowever, in retrospect I think you're probably right.  Not only do I\nnot really need to load the information into memory to re-use it, but\napplications using rev-cache would probably have sufficiently\nspecialized needs to warrant direct access.  In light of this I've\nrewritten the fuse command to re-use data directly from the slice,\nrather than requiring it to be loaded into memory first (hence\neliminating the all those extra fields).  Furthermore I'll put all the\n(renamed) structures and definitions in a seperate header, to allow\neasy direct access to slices by third-parties.\n\n> Looks vaguely familiar.\n>\n> The configuration parser already knows about these size suffixes when told\n> to read \"int\".  Can't that code, e.g. git_parse_ulong(), be reused here?\n\nYou're also right here.  I wrote it fast and hadn't checked if git had\nalready implemented it.  I've changed it to use git_parse_ulong().\n\nSorry I haven't uploaded anything yet.  I keep seeing new things that\ncould updated or revised; so far I've\n - rewritten and added much to the documentation\n - added support for an alternates-like mechanism\n - changed --noobjects to --no-objects\n - changed init_rci to init_rev_cache_info\n - modified make_cache_slice to return actual start/end commits\n - changed coagulate_ to fuse_\n - added an (admittedly crude) escape plan in case of obscenely large\nmerges/branches\n - cleaned up path generation\n - replace parse_size with git_parse_ulong\n - rewritten fuse to reuse objects verbatim, rather than via memory access\n\nAnd on my todo list I've still got things such as renaming all the\nstructures/definitions, adding a more portable _ondisk version of\nbitfield'ed structs and obviously cleanup the patchset (eliminating\nfixes of earlier patches, etc.).\n\nI hope to get everything finished in the next couple days, and upload\na v3 by friday at the latest.\n\n - Nick\n"},{"id":"120795","messageId":"op.uyr1ccsitdk399@sirnot.private","threadId":"20468","inReplyTo":"op.uyb1vcvytdk399@sirnot.private","subject":"Re: [PATCH 4/6 (v2)] administrative functions for rev-cache, and start of integration into git","fromName":"Nick Edelen","fromEmail":"sirnot@gmail.com","sentAt":"2009-08-16T22:42:02Z","receivedAt":"2009-08-16T22:42:02Z","isPatch":true,"sender":{"key":"sirnot@gmail.com","avatar":null},"body":"This patch, fourth, contains miscellaneous (maintenance) features:\n - support for cache slice fusion, index regeneration and object size caching\n - non-commit object generation refactored to take advantage of 'size' field\n - porcelain updated to support feature additions\n\nThe beginnings of integration into git are present in this patch, mainly \ncentered on caching object size; the object generation is refactored to more \nelegantly exploit this.  Fusion allows smaller (incremental) slices to be \ncoagulated into a larger slice, reducing overhead, while index regeneration \nenables repair or cleaning of the cache index.\n\nNote that tests for these features are included in the following patch, as they \ntake advantage of the rev-cache's integration into the revision walker.\n\nSigned-off-by: Nick Edelen <sirnot@gmail.com>\n\n---\n builtin-gc.c        |    9 +\n builtin-rev-cache.c |   77 ++++++-\n rev-cache.c         |  717 +++++++++++++++++++++++++++++++++++++++++++++------\n rev-cache.h         |    9 +-\n revision.h          |   16 +-\n 5 files changed, 749 insertions(+), 79 deletions(-)\n\ndiff --git a/builtin-gc.c b/builtin-gc.c\nindex 7d3e9cc..c92511a 100644\n--- a/builtin-gc.c\n+++ b/builtin-gc.c\n@@ -22,6 +22,7 @@ static const char * const builtin_gc_usage[] = {\n \tNULL\n };\n \n+static char do_rev_cache = 0;\n static int pack_refs = 1;\n static int aggressive_window = 250;\n static int gc_auto_threshold = 6700;\n@@ -34,9 +35,14 @@ static const char *argv_reflog[] = {\"reflog\", \"expire\", \"--all\", NULL};\n static const char *argv_repack[MAX_ADD] = {\"repack\", \"-d\", \"-l\", NULL};\n static const char *argv_prune[] = {\"prune\", \"--expire\", NULL, NULL};\n static const char *argv_rerere[] = {\"rerere\", \"gc\", NULL};\n+static const char *argv_rev_cache[] = {\"rev-cache\", \"fuse\", \"--all\", \"--ignore-size\", NULL};\n \n static int gc_config(const char *var, const char *value, void *cb)\n {\n+\tif (!strcmp(var, \"gc.revcache\")) {\n+\t\tdo_rev_cache = 1;\n+\t\treturn 0;\n+\t}\n \tif (!strcmp(var, \"gc.packrefs\")) {\n \t\tif (value && !strcmp(value, \"notbare\"))\n \t\t\tpack_refs = -1;\n@@ -244,6 +250,9 @@ int cmd_gc(int argc, const char **argv, const char *prefix)\n \tif (run_command_v_opt(argv_rerere, RUN_GIT_CMD))\n \t\treturn error(FAILED_RUN, argv_rerere[0]);\n \n+\tif (do_rev_cache && run_command_v_opt(argv_rev_cache, RUN_GIT_CMD))\n+\t\treturn error(FAILED_RUN, argv_rev_cache[0]);\n+\n \tif (auto_gc && too_many_loose_objects())\n \t\twarning(\"There are too many unreachable loose objects; \"\n \t\t\t\"run 'git prune' to remove them.\");\ndiff --git a/builtin-rev-cache.c b/builtin-rev-cache.c\nindex c27e0f3..7ca39c4 100644\n--- a/builtin-rev-cache.c\n+++ b/builtin-rev-cache.c\n@@ -5,6 +5,8 @@\n #include \"revision.h\"\n #include \"rev-cache.h\"\n \n+unsigned long default_ignore_size = 50 * 1024 * 1024; /* 50mb */\n+\n /* porcelain for rev-cache.c */\n static int handle_add(int argc, const char *argv[]) /* args beyond this command */\n {\n@@ -24,7 +26,7 @@ static int handle_add(int argc, const char *argv[]) /* args beyond this command\n \t\tif (!strcmp(argv[i], \"--stdin\"))\n \t\t\tdostdin = 1;\n \t\telse if (!strcmp(argv[i], \"--fresh\"))\n-\t\t\tstarts_from_slices(&revs, UNINTERESTING);\n+\t\t\tstarts_from_slices(&revs, UNINTERESTING, 0, 0);\n \t\telse if (!strcmp(argv[i], \"--not\"))\n \t\t\tflags ^= UNINTERESTING;\n \t\telse if (!strcmp(argv[i], \"--legs\"))\n@@ -150,6 +152,57 @@ static int handle_walk(int argc, const char *argv[])\n \treturn 0;\n }\n \n+static int handle_fuse(int argc, const char *argv[])\n+{\n+\tstruct rev_info revs;\n+\tstruct rev_cache_info rci;\n+\tconst char *args[5];\n+\tint i, argn = 0;\n+\tchar add_all = 0;\n+\n+\tinit_revisions(&revs, 0);\n+\tinit_rev_cache_info(&rci);\n+\targs[argn++] = \"rev-list\";\n+\n+\tfor (i = 0; i < argc; i++) {\n+\t\tif (!strcmp(argv[i], \"--all\")) {\n+\t\t\targs[argn++] = \"--all\";\n+\t\t\tsetup_revisions(argn, args, &revs, 0);\n+\t\t\tadd_all = 1;\n+\t\t} else if (!strcmp(argv[i], \"--no-objects\"))\n+\t\t\trci.objects = 0;\n+\t\telse if (!strncmp(argv[i], \"--ignore-size\", 13)) {\n+\t\t\tunsigned long sz;\n+\n+\t\t\tif (argv[i][13] == '=')\n+\t\t\t\tgit_parse_ulong(argv[i] + 14, &sz);\n+\t\t\telse\n+\t\t\t\tsz = default_ignore_size;\n+\n+\t\t\trci.ignore_size = sz;\n+\t\t} else\n+\t\t\tcontinue;\n+\t}\n+\n+\tif (!add_all)\n+\t\tstarts_from_slices(&revs, 0, 0, 0);\n+\n+\treturn fuse_cache_slices(&rci, &revs);\n+}\n+\n+static int handle_index(int argc, const char *argv[])\n+{\n+\treturn regenerate_cache_index(0);\n+}\n+\n+static int handle_alt(int argc, const char *argv[])\n+{\n+\tif (argc < 1)\n+\t\treturn -1;\n+\n+\treturn make_cache_slice_pointer(0, argv[0]);\n+}\n+\n static int handle_help(void)\n {\n \tchar *usage = \"\\\n@@ -179,12 +232,28 @@ commands:\\n\\\n \treturn 0;\n }\n \n+static int rev_cache_config(const char *k, const char *v, void *cb)\n+{\n+\t/* this could potentially be related to pack.windowmemory, but we want a max around 50mb,\n+\t * and .windowmemory is often >700mb, with *large* variations */\n+\tif (!strcmp(k, \"revcache.ignoresize\")) {\n+\t\tint t;\n+\n+\t\tt = git_config_ulong(k, v);\n+\t\tif (t)\n+\t\t\tdefault_ignore_size = t;\n+\t}\n+\n+\treturn 0;\n+}\n+\n int cmd_rev_cache(int argc, const char *argv[], const char *prefix)\n {\n \tconst char *arg;\n \tint r;\n \n \tgit_config(git_default_config, NULL);\n+\tgit_config(rev_cache_config, NULL);\n \n \tif (argc > 1)\n \t\targ = argv[1];\n@@ -195,8 +264,14 @@ int cmd_rev_cache(int argc, const char *argv[], const char *prefix)\n \targv += 2;\n \tif (!strcmp(arg, \"add\"))\n \t\tr = handle_add(argc, argv);\n+\telse if (!strcmp(arg, \"fuse\"))\n+\t\tr = handle_fuse(argc, argv);\n \telse if (!strcmp(arg, \"walk\"))\n \t\tr = handle_walk(argc, argv);\n+\telse if (!strcmp(arg, \"index\"))\n+\t\tr = handle_index(argc, argv);\n+\telse if (!strcmp(arg, \"alt\"))\n+\t\tr = handle_alt(argc, argv);\n \telse\n \t\treturn handle_help();\n \ndiff --git a/rev-cache.c b/rev-cache.c\nindex ddcc596..8eac1f0 100644\n--- a/rev-cache.c\n+++ b/rev-cache.c\n@@ -9,6 +9,13 @@\n #include \"revision.h\"\n #include \"rev-cache.h\"\n #include \"run-command.h\"\n+#include \"string-list.h\"\n+\n+struct cache_slice_pointer {\n+\tchar signature[8]; /* REVCOPTR */\n+\tchar version;\n+\tchar path[PATH_MAX + 1];\n+};\n \n /* list resembles pack index format */\n static uint32_t fanout[0xff + 2];\n@@ -257,27 +264,45 @@ unsigned char *get_cache_slice(struct commit *commit)\n \n /* traversal */\n \n-static void handle_noncommit(struct rev_info *revs, unsigned char *ptr, struct rc_object_entry *entry)\n+static unsigned long decode_size(unsigned char *str, int len);\n+\n+static void handle_noncommit(struct rev_info *revs, struct commit *commit, unsigned char *ptr, struct rc_object_entry *entry)\n {\n-\tstruct object *obj = 0;\n+\tstruct blob *blob;\n+\tstruct tree *tree;\n+\tstruct object *obj;\n+\tunsigned long size;\n \n+\tsize = decode_size(ptr + RC_ENTRY_SIZE_OFFSET(entry), entry->size_size);\n \tswitch (entry->type) {\n \tcase OBJ_TREE :\n-\t\tif (revs->tree_objects)\n-\t\t\tobj = (struct object *)lookup_tree(entry->sha1);\n+\t\tif (!revs->tree_objects)\n+\t\t\treturn;\n+\n+\t\ttree = lookup_tree(entry->sha1);\n+\t\tif (!tree)\n+\t\t\treturn;\n+\n+\t\ttree->size = size;\n+\t\tcommit->tree = tree;\n+\t\tobj = (struct object *)tree;\n \t\tbreak;\n+\n \tcase OBJ_BLOB :\n-\t\tif (revs->blob_objects)\n-\t\t\tobj = (struct object *)lookup_blob(entry->sha1);\n-\t\tbreak;\n-\tcase OBJ_TAG :\n-\t\tif (revs->tag_objects)\n-\t\t\tobj = (struct object *)lookup_tag(entry->sha1);\n+\t\tif (!revs->blob_objects)\n+\t\t\treturn;\n+\n+\t\tblob = lookup_blob(entry->sha1);\n+\t\tif (!blob)\n+\t\t\treturn;\n+\n+\t\tobj = (struct object *)blob;\n \t\tbreak;\n-\t}\n \n-\tif (!obj)\n+\tdefault :\n+\t\t/* tag objects aren't really supposed to be here */\n \t\treturn;\n+\t}\n \n \tobj->flags |= FACE_VALUE;\n \tadd_pending_object(revs, obj, \"\");\n@@ -373,7 +398,7 @@ static int traverse_cache_slice_1(struct rc_slice_header *head, unsigned char *m\n \t\t/* add extra objects if necessary */\n \t\tif (entry->type != OBJ_COMMIT) {\n \t\t\tif (consume_children)\n-\t\t\t\thandle_noncommit(revs, map + index, entry);\n+\t\t\t\thandle_noncommit(revs, co, map + index, entry);\n \n \t\t\tcontinue;\n \t\t} else\n@@ -407,6 +432,8 @@ static int traverse_cache_slice_1(struct rc_slice_header *head, unsigned char *m\n \t\t\tif (last_objects[path]) {\n \t\t\t\tparse_commit(last_objects[path]);\n \n+\t\t\t\t/* we needn't worry about the unique field; that will be valid as\n+\t\t\t\t * long as we're not a end entry */\n \t\t\t\tlast_objects[path]->object.flags &= ~FACE_VALUE;\n \t\t\t\tlast_objects[path] = 0;\n \t\t\t}\n@@ -539,6 +566,48 @@ static int get_cache_slice_header(unsigned char *cache_sha1, unsigned char *map,\n \treturn 0;\n }\n \n+int open_cache_slice(unsigned char *sha1, int flags)\n+{\n+\tint fd;\n+\tchar signature[8];\n+\n+\tfd = open(git_path(\"rev-cache/%s\", sha1_to_hex(sha1)), flags);\n+\tif (fd <= 0)\n+\t\tgoto end;\n+\n+\tif (read(fd, signature, 8) != 8)\n+\t\tgoto end;\n+\n+\t/* a normal revision slice */\n+\tif (!memcmp(signature, \"REVCACHE\", 8)) {\n+\t\tlseek(fd, 0, SEEK_SET);\n+\t\treturn fd;\n+\t}\n+\n+\t/* slice pointer */\n+\tif (!memcmp(signature, \"REVCOPTR\", 8)) {\n+\t\tstruct cache_slice_pointer ptr;\n+\n+\t\tlseek(fd, 0, SEEK_SET);\n+\t\tif (read_in_full(fd, &ptr, sizeof(ptr)) != sizeof(ptr))\n+\t\t\tgoto end;\n+\n+\t\tif (ptr.version != SUPPORTED_REVCOPTR_VERSION)\n+\t\t\tgoto end;\n+\n+\t\tclose(fd);\n+\t\tfd = open(ptr.path, flags);\n+\n+\t\treturn fd;\n+\t}\n+\n+end:\n+\tif (fd > 0)\n+\t\tclose(fd);\n+\n+\treturn -1;\n+}\n+\n int traverse_cache_slice(struct rev_info *revs,\n \tunsigned char *cache_sha1, struct commit *commit,\n \tunsigned long *date_so_far, int *slop_so_far,\n@@ -562,7 +631,7 @@ int traverse_cache_slice(struct rev_info *revs,\n \n \tmemset(&head, 0, sizeof(struct rc_slice_header));\n \n-\tfd = open(git_path(\"rev-cache/%s\", sha1_to_hex(cache_sha1)), O_RDONLY);\n+\tfd = open_cache_slice(cache_sha1, O_RDONLY);\n \tif (fd == -1)\n \t\tgoto end;\n \tif (fstat(fd, &fi) || fi.st_size < sizeof(struct rc_slice_header))\n@@ -589,6 +658,68 @@ end:\n \n /* generation */\n \n+static int is_endpoint(struct commit *commit)\n+{\n+\tstruct commit_list *list = commit->parents;\n+\n+\twhile (list) {\n+\t\tif (!(list->item->object.flags & UNINTERESTING))\n+\t\t\treturn 0;\n+\n+\t\tlist = list->next;\n+\t}\n+\n+\treturn 1;\n+}\n+\n+/* ensures branch is self-contained: parents are either all interesting or all uninteresting */\n+static void make_legs(struct rev_info *revs)\n+{\n+\tstruct commit_list *list, **plist;\n+\tint total = 0;\n+\n+\t/* attach plist to end of commits list */\n+\tlist = revs->commits;\n+\twhile (list && list->next)\n+\t\tlist = list->next;\n+\n+\tif (list)\n+\t\tplist = &list->next;\n+\telse\n+\t\treturn;\n+\n+\t/* duplicates don't matter, as get_revision() ignores them */\n+\tfor (list = revs->commits; list; list = list->next) {\n+\t\tstruct commit *item = list->item;\n+\t\tstruct commit_list *parents = item->parents;\n+\n+\t\tif (item->object.flags & UNINTERESTING)\n+\t\t\tcontinue;\n+\t\tif (is_endpoint(item))\n+\t\t\tcontinue;\n+\n+\t\twhile (parents) {\n+\t\t\tstruct commit *p = parents->item;\n+\t\t\tparents = parents->next;\n+\n+\t\t\tif (!(p->object.flags & UNINTERESTING))\n+\t\t\t\tcontinue;\n+\n+\t\t\tp->object.flags &= ~UNINTERESTING;\n+\t\t\tparse_commit(p);\n+\t\t\tplist = &commit_list_insert(p, plist)->next;\n+\n+\t\t\tif (!(p->object.flags & SEEN))\n+\t\t\t\ttotal++;\n+\t\t}\n+\t}\n+\n+\tif (total)\n+\t\tsort_in_topological_order(&revs->commits, 1);\n+\n+}\n+\n+\n struct path_track {\n \tstruct commit *commit;\n \tint path; /* for keeping track of children */\n@@ -777,31 +908,76 @@ static void handle_paths(struct commit *commit, struct rc_object_entry *object,\n }\n \n \n-static void add_object_entry(const unsigned char *sha1, int type, struct rc_object_entry *nothisone,\n+static int encode_size(unsigned long size, unsigned char *out)\n+{\n+\tint len = 0;\n+\n+\twhile (size) {\n+\t\t*out++ = (unsigned char)(size & 0xff);\n+\t\tsize >>= 8;\n+\t\tlen++;\n+\t}\n+\n+\treturn len;\n+}\n+\n+static unsigned long decode_size(unsigned char *str, int len)\n+{\n+\tunsigned long size = 0;\n+\tint shift = 0;\n+\n+\twhile (len--) {\n+\t\tsize |= (unsigned long)*str << shift;\n+\t\tshift += 8;\n+\t\tstr++;\n+\t}\n+\n+\treturn size;\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 {\n-\tstruct rc_object_entry object;\n+\tstruct rc_object_entry entry;\n+\tunsigned char size_str[7];\n+\tunsigned long size;\n+\tenum object_type type;\n+\tvoid *data;\n \n-\tif (!nothisone) {\n-\t\tmemset(&object, 0, sizeof(object));\n-\t\tobject.sha1 = (unsigned char *)sha1;\n-\t\tobject.type = type;\n+\tif (entryp)\n+\t\tsha1 = entryp->sha1;\n+\n+\t/* retrieve size data */\n+\tdata = read_sha1_file(sha1, &type, &size);\n+\n+\tif (data)\n+\t\tfree(data);\n+\n+\t/* initialize! */\n+\tif (!entryp) {\n+\t\tmemset(&entry, 0, sizeof(entry));\n+\t\tentry.sha1 = (unsigned char *)sha1;\n+\t\tentry.type = type;\n \n \t\tif (merge_str)\n-\t\t\tobject.merge_nr = merge_str->len / sizeof(uint16_t);\n+\t\t\tentry.merge_nr = merge_str->len / sizeof(uint16_t);\n \t\tif (split_str)\n-\t\t\tobject.split_nr = split_str->len / sizeof(uint16_t);\n+\t\t\tentry.split_nr = split_str->len / sizeof(uint16_t);\n \n-\t\tnothisone = &object;\n+\t\tentryp = &entry;\n \t}\n \n-\tstrbuf_add(acc_buffer, to_disked_rc_object_entry(nothisone, 0), sizeof(struct rc_object_entry_ondisk));\n+\tentryp->size_size = encode_size(size, size_str);\n \n-\tif (merge_str && merge_str->len)\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+\tif (merge_str)\n \t\tstrbuf_add(acc_buffer, merge_str->buf, merge_str->len);\n-\tif (split_str && split_str->len)\n+\tif (split_str)\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 \n /* returns non-zero to continue parsing, 0 to skip */\n@@ -845,12 +1021,7 @@ continue_loop:\n \n static int dump_tree_callback(const unsigned char *sha1, const char *path, unsigned int mode)\n {\n-\tunsigned char data[21];\n-\n-\thashcpy(data, sha1);\n-\tdata[20] = !!S_ISDIR(mode);\n-\n-\tstrbuf_add(acc_buffer, data, 21);\n+\tstrbuf_add(acc_buffer, sha1, 20);\n \n \treturn 1;\n }\n@@ -860,15 +1031,10 @@ static void tree_addremove(struct diff_options *options,\n \tconst unsigned char *sha1,\n \tconst char *concatpath)\n {\n-\tunsigned char data[21];\n-\n \tif (whatnow != '+')\n \t\treturn;\n \n-\thashcpy(data, sha1);\n-\tdata[20] = !!S_ISDIR(mode);\n-\n-\tstrbuf_add(acc_buffer, data, 21);\n+\tstrbuf_add(acc_buffer, sha1, 20);\n }\n \n static void tree_change(struct diff_options *options,\n@@ -877,26 +1043,10 @@ static void tree_change(struct diff_options *options,\n \tconst unsigned char *new_sha1,\n \tconst char *concatpath)\n {\n-\tunsigned char data[21];\n-\n \tif (!hashcmp(old_sha1, new_sha1))\n \t\treturn;\n \n-\thashcpy(data, new_sha1);\n-\tdata[20] = !!S_ISDIR(new_mode);\n-\n-\tstrbuf_add(acc_buffer, data, 21);\n-}\n-\n-static int sort_type_hash(const void *a, const void *b)\n-{\n-\tconst unsigned char *sa = (const unsigned char *)a,\n-\t\t*sb = (const unsigned char *)b;\n-\n-\tif (sa[20] == sb[20])\n-\t\treturn hashcmp(sa, sb);\n-\n-\treturn sa[20] > sb[20] ? -1 : 1;\n+\tstrbuf_add(acc_buffer, new_sha1, 20);\n }\n \n static int add_unique_objects(struct commit *commit)\n@@ -907,6 +1057,7 @@ static int add_unique_objects(struct commit *commit)\n \tint i, j, next;\n \tchar is_first = 1;\n \n+\t/* ...no, calculate unique objects */\n \tstrbuf_init(&os, 0);\n \tstrbuf_init(&ost, 0);\n \torig_buf = acc_buffer;\n@@ -926,20 +1077,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 / 21, 21, (int (*)(const void *, const void *))hashcmp);\n+\t\tqsort(acc_buffer->buf, acc_buffer->len / 20, 20, (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 += 21) {\n+\t\t\tfor (next = i = j = 0; i < os.len; i += 20) {\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 += 21;\n+\t\t\t\t\tj += 20;\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, 21);\n-\t\t\t\tnext += 21;\n+\t\t\t\t\tmemcpy(os.buf + next, os.buf + i, 20);\n+\t\t\t\tnext += 20;\n \t\t\t}\n \n \t\t\tif (next != i)\n@@ -948,25 +1099,102 @@ static int add_unique_objects(struct commit *commit)\n \t\t\tis_first = 0;\n \t}\n \n+\t/* no parents (!) */\n \tif (is_first) {\n \t\tacc_buffer = &os;\n \t\tdump_tree(commit->tree, dump_tree_callback);\n \t}\n \n-\tif (os.len)\n-\t\tqsort(os.buf, os.len / 21, 21, sort_type_hash);\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 += 21)\n-\t\tadd_object_entry((unsigned char *)(os.buf + i), os.buf[i + 20] ? OBJ_TREE : OBJ_BLOB, 0, 0, 0);\n+\tfor (i = 0; i < os.len; i += 20)\n+\t\tadd_object_entry((unsigned char *)(os.buf + i), 0, 0, 0);\n \n \t/* last but not least, the main tree */\n-\tadd_object_entry(commit->tree->object.sha1, OBJ_TREE, 0, 0, 0);\n+\tadd_object_entry(commit->tree->object.sha1, 0, 0, 0);\n+\n+\treturn i / 20 + 1;\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+\tstruct rc_object_entry *entry = RC_OBTAIN_OBJECT_ENTRY(map + i);\n+\n+\ti += RC_ACTUAL_OBJECT_ENTRY_SIZE(entry);\n+\twhile (i < mapping->size) {\n+\t\tint pos = i;\n \n-\tstrbuf_release(&ost);\n-\tstrbuf_release(&os);\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+\t\t\t*index = pos;\n+\t\t\treturn object_nr;\n+\t\t}\n \n-\treturn i / 21 + 1;\n+\t\tstrbuf_add(acc_buffer, map + pos, i - pos);\n+\t\tobject_nr++;\n+\t}\n+\n+\t*index = 0;\n+\treturn object_nr;\n+}\n+\n+static int add_objects_verbatim(struct rev_cache_info *rci, struct commit *commit)\n+{\n+\tstruct rev_cache_slice_map *map;\n+\tchar found = 0;\n+\tstruct rc_index_entry *ie;\n+\tstruct rc_object_entry *entry;\n+\tint object_nr, i;\n+\n+\tif (!rci->maps)\n+\t\treturn -1;\n+\n+\t/* check if we can continue where we left off */\n+\tmap = rci->last_map;\n+\tif (!map)\n+\t\tgoto search_me;\n+\n+\ti = map->last_index;\n+\tentry = RC_OBTAIN_OBJECT_ENTRY(map->map + i);\n+\tif (hashcmp(entry->sha1, commit->object.sha1))\n+\t\tgoto search_me;\n+\n+\tfound = 1;\n+\n+search_me:\n+\tif (!found) {\n+\t\tie = search_index(commit->object.sha1);\n+\t\tif (!ie || ie->cache_index >= idx_head.cache_nr)\n+\t\t\treturn -2;\n+\n+\t\tmap = rci->maps + ie->cache_index;\n+\t\tif (!map->size)\n+\t\t\treturn -3;\n+\n+\t\ti = ie->pos;\n+\t\tentry = RC_OBTAIN_OBJECT_ENTRY(map->map + i);\n+\t\tif (entry->type != OBJ_COMMIT || hashcmp(entry->sha1, commit->object.sha1))\n+\t\t\treturn -4;\n+\t}\n+\n+\t/* can't handle end commits */\n+\tif (entry->is_end)\n+\t\treturn -5;\n+\n+\tobject_nr = add_objects_verbatim_1(map, &i);\n+\n+\t/* remember this */\n+\tif (i) {\n+\t\trci->last_map = map;\n+\t\tmap->last_index = i;\n+\t} else\n+\t\trci->last_map = 0;\n+\n+\treturn object_nr;\n }\n \n static void init_revcache_directory(void)\n@@ -981,9 +1209,14 @@ static void init_revcache_directory(void)\n \n void init_rev_cache_info(struct rev_cache_info *rci)\n {\n+\tmemset(rci, 0, sizeof(struct rev_cache_info));\n+\n \trci->objects = 1;\n \trci->legs = 0;\n \trci->make_index = 1;\n+\trci->fuse_me = 0;\n+\n+\trci->overwrite_all = 0;\n \n \trci->add_to_pending = 1;\n \n@@ -1063,9 +1296,13 @@ int make_cache_slice(struct rev_cache_info *rci,\n \tif (prepare_revision_walk(revs))\n \t\tdie(\"died preparing revision walk\");\n \n+\tif (rci->legs)\n+\t\tmake_legs(revs);\n+\n \tobject_nr = total_sz = 0;\n \twhile ((commit = get_revision(revs)) != 0) {\n \t\tstruct rc_object_entry object;\n+\t\tint t;\n \n \t\tstrbuf_setlen(&merge_paths, 0);\n \t\tstrbuf_setlen(&split_paths, 0);\n@@ -1091,12 +1328,17 @@ int make_cache_slice(struct rev_cache_info *rci,\n \n \t\tcommit->indegree = 0;\n \n-\t\tadd_object_entry(0, 0, &object, &merge_paths, &split_paths);\n+\t\tadd_object_entry(0, &object, &merge_paths, &split_paths);\n \t\tobject_nr++;\n \n-\t\t/* add all unique children for this commit */\n-\t\tif (rci->objects && !object.is_end)\n-\t\t\tobject_nr += add_unique_objects(commit);\n+\t\tif (rci->objects && !object.is_end) {\n+\t\t\tif (rci->fuse_me && (t = add_objects_verbatim(rci, commit)) >= 0)\n+\t\t\t\t/* yay!  we did it! */\n+\t\t\t\tobject_nr += t;\n+\t\t\telse\n+\t\t\t\t/* add all unique children for this commit */\n+\t\t\t\tobject_nr += add_unique_objects(commit);\n+\t\t}\n \n \t\t/* print every ~1MB or so */\n \t\tif (buffer.len > 1000000) {\n@@ -1221,6 +1463,8 @@ int make_cache_index(struct rev_cache_info *rci, unsigned char *cache_sha1,\n \tunsigned char *map;\n \tunsigned long max_date;\n \n+\tmaybe_fill_with_defaults(rci);\n+\n \tif (!idx_map)\n \t\tinit_index();\n \n@@ -1285,7 +1529,7 @@ int make_cache_index(struct rev_cache_info *rci, unsigned char *cache_sha1,\n \t\t} else\n \t\t\tdisked_entry = search_index_1(object_entry->sha1);\n \n-\t\tif (disked_entry && !object_entry->is_start)\n+\t\tif (disked_entry && !object_entry->is_start && !rci->overwrite_all)\n \t\t\tcontinue;\n \t\telse if (disked_entry) {\n \t\t\t/* mmm, pointer arithmetic... tasty */  /* (entry - idx_map = offset, so cast is valid) */\n@@ -1339,8 +1583,7 @@ int make_cache_index(struct rev_cache_info *rci, unsigned char *cache_sha1,\n }\n \n \n-/* add start-commits from each cache slice (uninterestingness will be propogated) */\n-void starts_from_slices(struct rev_info *revs, unsigned int flags)\n+void starts_from_slices(struct rev_info *revs, unsigned int flags, unsigned char *which, int n)\n {\n \tstruct commit *commit;\n \tint i;\n@@ -1356,6 +1599,18 @@ void starts_from_slices(struct rev_info *revs, unsigned int flags)\n \t\tif (!entry->is_start)\n \t\t\tcontinue;\n \n+\t\t/* only include entries in 'which' slices */\n+\t\tif (n) {\n+\t\t\tint j;\n+\n+\t\t\tfor (j = 0; j < n; j++)\n+\t\t\t\tif (!hashcmp(idx_caches + entry->cache_index * 20, which + j * 20))\n+\t\t\t\t\tbreak;\n+\n+\t\t\tif (j == n)\n+\t\t\t\tcontinue;\n+\t\t}\n+\n \t\tcommit = lookup_commit(entry->sha1);\n \t\tif (!commit)\n \t\t\tcontinue;\n@@ -1365,3 +1620,313 @@ void starts_from_slices(struct rev_info *revs, unsigned int flags)\n \t}\n \n }\n+\n+\n+struct slice_fd_time {\n+\tunsigned char sha1[20];\n+\tint fd;\n+\tstruct stat fi;\n+};\n+\n+int slice_time_sort(const void *a, const void *b)\n+{\n+\tunsigned long at, bt;\n+\n+\tat = ((struct slice_fd_time *)a)->fi.st_ctime;\n+\tbt = ((struct slice_fd_time *)b)->fi.st_ctime;\n+\n+\tif (at == bt)\n+\t\treturn 0;\n+\n+\treturn at > bt ? 1 : -1;\n+}\n+\n+int regenerate_cache_index(struct rev_cache_info *rci)\n+{\n+\tDIR *dirh;\n+\tint i;\n+\tstruct slice_fd_time info;\n+\tstruct strbuf slices;\n+\n+\t/* first remove old index if it exists */\n+\tunlink_or_warn(git_path(\"rev-cache/index\"));\n+\n+\tstrbuf_init(&slices, 0);\n+\n+\tdirh = opendir(git_path(\"rev-cache\"));\n+\tif (dirh) {\n+\t\tstruct dirent *de;\n+\t\tstruct stat fi;\n+\t\tint fd;\n+\t\tunsigned char sha1[20];\n+\n+\t\twhile ((de = readdir(dirh))) {\n+\t\t\tif (de->d_name[0] == '.')\n+\t\t\t\tcontinue;\n+\n+\t\t\tif (get_sha1_hex(de->d_name, sha1))\n+\t\t\t\tcontinue;\n+\n+\t\t\t/* open with RDWR because of mmap call in make_cache_index() */\n+\t\t\tfd = open_cache_slice(sha1, O_RDONLY);\n+\t\t\tif (fd < 0 || fstat(fd, &fi)) {\n+\t\t\t\twarning(\"bad cache found [%s]; fuse recommended\", de->d_name);\n+\t\t\t\tif (fd > 0)\n+\t\t\t\t\tclose(fd);\n+\t\t\t\tcontinue;\n+\t\t\t}\n+\n+\t\t\thashcpy(info.sha1, sha1);\n+\t\t\tinfo.fd = fd;\n+\t\t\tmemcpy(&info.fi, &fi, sizeof(struct stat));\n+\n+\t\t\tstrbuf_add(&slices, &info, sizeof(info));\n+\t\t}\n+\n+\t\tclosedir(dirh);\n+\t}\n+\n+\t/* we want oldest first -> upon overlap, older slices are more likely to have a larger section,\n+\t * as of the overlapped commit */\n+\tqsort(slices.buf, slices.len / sizeof(info), sizeof(info), slice_time_sort);\n+\n+\tfor (i = 0; i < slices.len; i += sizeof(info)) {\n+\t\tstruct slice_fd_time *infop = (struct slice_fd_time *)(slices.buf + i);\n+\t\tstruct stat *fip = &infop->fi;\n+\t\tint fd = infop->fd;\n+\n+\t\tif (make_cache_index(rci, infop->sha1, fd, fip->st_size) < 0)\n+\t\t\tdie(\"error writing cache\");\n+\n+\t\tclose(fd);\n+\t}\n+\n+\tstrbuf_release(&slices);\n+\n+\treturn 0;\n+}\n+\n+static int add_slices_for_fuse(struct rev_cache_info *rci, struct string_list *files, struct strbuf *ignore)\n+{\n+\tunsigned char sha1[20];\n+\tchar base[PATH_MAX];\n+\tint baselen, i, slice_nr = 0;\n+\tstruct stat fi;\n+\tDIR *dirh;\n+\tstruct dirent *de;\n+\n+\tstrncpy(base, git_path(\"rev-cache\"), sizeof(base));\n+\tbaselen = strlen(base);\n+\n+\tdirh = opendir(base);\n+\tif (!dirh)\n+\t\treturn 0;\n+\n+\twhile ((de = readdir(dirh))) {\n+\t\tif (de->d_name[0] == '.')\n+\t\t\tcontinue;\n+\n+\t\tbase[baselen] = '/';\n+\t\tstrncpy(base + baselen + 1, de->d_name, sizeof(base) - baselen - 1);\n+\n+\t\tif (get_sha1_hex(de->d_name, sha1)) {\n+\t\t\t/* whatever it is, we don't need it... */\n+\t\t\tstring_list_insert(base, files);\n+\t\t\tcontinue;\n+\t\t}\n+\n+\t\t/* _theoretically_ it is possible a slice < ignore_size to map objects not covered by, yet reachable from,\n+\t\t * a slice >= ignore_size, meaning that we could potentially delete an 'unfused' slice; but if that\n+\t\t * ever *did* happen their cache structure'd be so fucked up they might as well refuse the entire thing.\n+\t\t * and at any rate the worst it'd do is make rev-list revert to standard walking in that (small) bit.\n+\t\t */\n+\t\tif (rci->ignore_size) {\n+\t\t\tif (stat(base, &fi))\n+\t\t\t\twarning(\"can't query file %s\\n\", base);\n+\t\t\telse if (fi.st_size >= rci->ignore_size) {\n+\t\t\t\tstrbuf_add(ignore, sha1, 20);\n+\t\t\t\tcontinue;\n+\t\t\t}\n+\t\t} else {\n+\t\t\t/* check if a pointer */\n+\t\t\tstruct cache_slice_pointer ptr;\n+\t\t\tint fd = open(base, O_RDONLY);\n+\n+\t\t\tif (fd < 0)\n+\t\t\t\tgoto dont_save;\n+\t\t\tif (sizeof(ptr) != read_in_full(fd, &ptr, sizeof(ptr)))\n+\t\t\t\tgoto dont_save;\n+\n+\t\t\tclose(fd);\n+\t\t\tif (!strcmp(ptr.signature, \"REVCOPTR\")) {\n+\t\t\t\tstrbuf_add(ignore, sha1, 20);\n+\t\t\t\tcontinue;\n+\t\t\t}\n+\t\t}\n+\n+dont_save:\n+\t\tfor (i = idx_head.cache_nr - 1; i >= 0; i--) {\n+\t\t\tif (!hashcmp(idx_caches + i * 20, sha1))\n+\t\t\t\tbreak;\n+\t\t}\n+\n+\t\tif (i >= 0)\n+\t\t\trci->maps[i].size = 1;\n+\n+\t\tstring_list_insert(base, files);\n+\t\tslice_nr++;\n+\t}\n+\n+\tclosedir(dirh);\n+\n+\treturn slice_nr;\n+}\n+\n+/* the most work-intensive attributes in the cache are the unique objects and size, both\n+ * of which can be re-used.  although path structures will be isomorphic, path generation is\n+ * not particularly expensive, and at any rate we need to re-sort the commits */\n+int fuse_cache_slices(struct rev_cache_info *rci, struct rev_info *revs)\n+{\n+\tunsigned char cache_sha1[20];\n+\tstruct string_list files = {0, 0, 0, 1}; /* dup */\n+\tstruct strbuf ignore;\n+\tint i;\n+\n+\tmaybe_fill_with_defaults(rci);\n+\n+\tif (!idx_map)\n+\t\tinit_index();\n+\tif (!idx_map)\n+\t\treturn -1;\n+\n+\tstrbuf_init(&ignore, 0);\n+\trci->maps = xcalloc(idx_head.cache_nr, sizeof(struct rev_cache_slice_map));\n+\tif (add_slices_for_fuse(rci, &files, &ignore) <= 1) {\n+\t\tprintf(\"nothing to fuse\\n\");\n+\t\treturn 1;\n+\t}\n+\n+\tif (ignore.len) {\n+\t\tstarts_from_slices(revs, UNINTERESTING, (unsigned char *)ignore.buf, ignore.len / 20);\n+\t\tstrbuf_release(&ignore);\n+\t}\n+\n+\t/* initialize mappings */\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\tint fd;\n+\n+\t\tif (!map->size)\n+\t\t\tcontinue;\n+\t\tmap->size = 0;\n+\n+\t\t/* pointers are never fused, so we can use open directly */\n+\t\tfd = open(git_path(\"rev-cache/%s\", sha1_to_hex(idx_caches + i * 20)), O_RDONLY);\n+\t\tif (fd <= 0 || fstat(fd, &fi))\n+\t\t\tcontinue;\n+\t\tif (fi.st_size < sizeof(struct rc_slice_header))\n+\t\t\tcontinue;\n+\n+\t\tmap->map = xmmap(0, fi.st_size, PROT_READ, MAP_PRIVATE, fd, 0);\n+\t\tif (map->map == MAP_FAILED)\n+\t\t\tcontinue;\n+\n+\t\tclose(fd);\n+\t\tmap->size = fi.st_size;\n+\t}\n+\n+\trci->make_index = 0;\n+\trci->fuse_me = 1;\n+\tif (make_cache_slice(rci, revs, 0, 0, cache_sha1) < 0)\n+\t\tdie(\"can't make cache slice\");\n+\n+\tprintf(\"%s\\n\", sha1_to_hex(cache_sha1));\n+\n+\t/* clean up time! */\n+\tfor (i = idx_head.cache_nr - 1; i >= 0; i--) {\n+\t\tstruct rev_cache_slice_map *map = rci->maps + i;\n+\n+\t\tif (!map->size)\n+\t\t\tcontinue;\n+\n+\t\tmunmap(map->map, map->size);\n+\t}\n+\tfree(rci->maps);\n+\tcleanup_cache_slices();\n+\n+\tfor (i = 0; i < files.nr; i++) {\n+\t\tchar *name = files.items[i].string;\n+\n+\t\tfprintf(stderr, \"removing %s\\n\", name);\n+\t\tunlink_or_warn(name);\n+\t}\n+\n+\tstring_list_clear(&files, 0);\n+\n+\treturn regenerate_cache_index(rci);\n+}\n+\n+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+\tif (len < 40)\n+\t\treturn -2;\n+\tif (get_sha1_hex(slice_path + len - 40, sha1))\n+\t\treturn -3;\n+\n+\tfd = open(slice_path, O_RDONLY);\n+\tif (fd == -1)\n+\t\tgoto end;\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+\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+\n+\treturn retval;\n+}\n+\n+int make_cache_slice_pointer(struct rev_cache_info *rci, const char *slice_path)\n+{\n+\tstruct cache_slice_pointer ptr;\n+\tint fd;\n+\tunsigned char sha1[20];\n+\n+\tmaybe_fill_with_defaults(rci);\n+\trci->overwrite_all = 1;\n+\n+\tif (verify_cache_slice(slice_path, sha1) < 0)\n+\t\treturn -1;\n+\n+\tstrcpy(ptr.signature, \"REVCOPTR\");\n+\tptr.version = SUPPORTED_REVCOPTR_VERSION;\n+\tstrcpy(ptr.path, make_nonrelative_path(slice_path));\n+\n+\tfd = open(git_path(\"rev-cache/%s\", sha1_to_hex(sha1)), O_RDWR | O_CREAT | O_TRUNC, 0666);\n+\tif (fd < 0)\n+\t\treturn -2;\n+\n+\twrite_in_full(fd, &ptr, sizeof(ptr));\n+\tmake_cache_index(rci, sha1, fd, sizeof(ptr));\n+\n+\tclose(fd);\n+\n+\treturn 0;\n+}\ndiff --git a/rev-cache.h b/rev-cache.h\nindex a471fbf..14437d8 100644\n--- a/rev-cache.h\n+++ b/rev-cache.h\n@@ -3,6 +3,7 @@\n \n #define SUPPORTED_REVCACHE_VERSION \t\t1\n #define SUPPORTED_REVINDEX_VERSION\t\t1\n+#define SUPPORTED_REVCOPTR_VERSION\t\t1\n \n #define RC_PATH_SIZE(x)\t(sizeof(uint16_t) * (x))\n \n@@ -10,6 +11,7 @@\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 \n /* single index maps objects to cache files */\n struct rc_index_header {\n@@ -90,6 +92,7 @@ struct rc_object_entry *from_disked_rc_object_entry(struct rc_object_entry_ondis\n struct rc_object_entry_ondisk *to_disked_rc_object_entry(struct rc_object_entry *src, struct rc_object_entry_ondisk *dst);\n \n extern unsigned char *get_cache_slice(struct commit *commit);\n+extern int open_cache_slice(unsigned char *sha1, int flags);\n extern int traverse_cache_slice(struct rev_info *revs,\n \tunsigned char *cache_sha1, struct commit *commit,\n \tunsigned long *date_so_far, int *slop_so_far,\n@@ -102,6 +105,10 @@ extern int make_cache_slice(struct rev_cache_info *rci,\n extern int make_cache_index(struct rev_cache_info *rci, unsigned char *cache_sha1,\n \tint fd, unsigned int size);\n \n-extern void starts_from_slices(struct rev_info *revs, unsigned int flags);\n+extern void starts_from_slices(struct rev_info *revs, unsigned int flags, unsigned char *which, int n);\n+extern int fuse_cache_slices(struct rev_cache_info *rci, struct rev_info *revs);\n+extern int regenerate_cache_index(struct rev_cache_info *rci);\n+extern int make_cache_slice_pointer(struct rev_cache_info *rci, const char *slice_path);\n \n #endif\n+\ndiff --git a/revision.h b/revision.h\nindex e767a43..c3ec1b3 100644\n--- a/revision.h\n+++ b/revision.h\n@@ -19,17 +19,31 @@\n struct rev_info;\n struct log_info;\n \n+struct rev_cache_slice_map {\n+\tunsigned char *map;\n+\tint size;\n+\tint last_index;\n+};\n+\n struct rev_cache_info {\n \t/* generation flags */\n \tunsigned objects : 1,\n \t\tlegs : 1,\n-\t\tmake_index : 1;\n+\t\tmake_index : 1,\n+\t\tfuse_me : 1;\n+\n+\t/* index inclusion */\n+\tunsigned overwrite_all : 1;\n \n \t/* traversal flags */\n \tunsigned add_to_pending : 1;\n \n \t/* fuse options */\n \tunsigned int ignore_size;\n+\n+\t/* reserved */\n+\tstruct rev_cache_slice_map *maps,\n+\t\t*last_map;\n };\n \n struct rev_info {\n-- \ntg: (e07ed0b..) t/revcache/misc (depends on: t/revcache/objects)\n"}]}