{"thread":{"id":"23343","subject":"[PATCH 4/7 (v5)] administrative api and tools","startedAt":"2010-04-05T19:58:22Z","lastAt":"2010-04-05T19:58:22Z","messageCount":1,"participants":["Nick Edelen"],"isPatch":true,"patchVersion":5,"patchTotal":7},"messages":[{"id":"138670","messageId":"4BBA40DE.1090102@gmail.com","threadId":"23343","inReplyTo":null,"subject":"[PATCH 4/7 (v5)] administrative api and tools","fromName":"Nick Edelen","fromEmail":"sirnot@gmail.com","sentAt":"2010-04-05T19:58:22Z","receivedAt":"2010-04-05T19:58:22Z","isPatch":true,"sender":{"key":"sirnot@gmail.com","avatar":null},"body":"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 |   80 ++++++-\n rev-cache.c         |  725 +++++++++++++++++++++++++++++++++++++++++++++------\n rev-cache.h         |    9 +-\n revision.h          |   18 ++-\n 5 files changed, 755 insertions(+), 86 deletions(-)\n\ndiff --git a/builtin/gc.c b/builtin/gc.c\nindex c304638..8e0e748 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@@ -247,6 +253,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 e322467..d6cd57b 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\") || !strcmp(argv[i], \"--incremental\"))\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\") || !strcmp(argv[i], \"--close\"))\n@@ -151,6 +153,60 @@ 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 t, 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\tt = 1;\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\t(t = !strncmp(argv[i], \"--keep-size\", 11))) {\n+\t\t\tunsigned long sz;\n+\n+\t\t\tt = t ? 13 : 11;\n+\t\t\tif (argv[i][t] == '=')\n+\t\t\t\tgit_parse_ulong(argv[i] + t + 1, &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@@ -183,12 +239,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@@ -199,8 +271,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 d4b7e16..27e3b40 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@@ -319,27 +326,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@@ -462,7 +487,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@@ -496,6 +521,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@@ -635,6 +662,47 @@ 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\tif (read(fd, &ptr.version, 1) != 1 || ptr.version > SUPPORTED_REVCOPTR_VERSION)\n+\t\t\tgoto end;\n+\n+\t\tif (read_in_full(fd, ptr.path, sizeof(ptr.path)) != sizeof(ptr.path))\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@@ -658,7 +726,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 < SLICE_HEADER_SIZE)\n@@ -685,6 +753,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@@ -873,31 +1003,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), OBJECT_ENTRY_SIZE);\n+\tentryp->size_size = encode_size(size, size_str);\n+\n+\t/* write the muvabitch */\n+\tstrbuf_add(acc_buffer, to_disked_rc_object_entry(entryp, 0), OBJECT_ENTRY_SIZE);\n \n-\tif (merge_str && merge_str->len)\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@@ -941,12 +1116,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@@ -956,15 +1126,7 @@ static void tree_addremove(struct diff_options *options,\n \tconst unsigned char *sha1,\n \tconst char *concatpath, unsigned dirty_sub)\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@@ -974,26 +1136,7 @@ static void tree_change(struct diff_options *options,\n \tconst char *concatpath,\n \tunsigned old_dirty_sub, unsigned new_dirty_sub)\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@@ -1004,6 +1147,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@@ -1023,20 +1167,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@@ -1045,25 +1189,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-\tstrbuf_release(&ost);\n-\tstrbuf_release(&os);\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+\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+\t\tstrbuf_add(acc_buffer, map + pos, i - pos);\n+\t\tobject_nr++;\n+\t}\n \n-\treturn i / 21 + 1;\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@@ -1078,9 +1299,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@@ -1161,9 +1387,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@@ -1192,12 +1422,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@@ -1332,6 +1567,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@@ -1397,7 +1634,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@@ -1451,8 +1688,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@@ -1468,6 +1704,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@@ -1477,3 +1725,316 @@ 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+\t/* tread carefully with structures... */\n+\twrite(fd, ptr.signature, sizeof(ptr.signature));\n+\twrite(fd, &ptr.version, 1);\n+\twrite_in_full(fd, ptr.path, sizeof(ptr.path));\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 75c3c71..6e3a895 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(2 * (x))\n \n@@ -10,6 +11,7 @@\n #define RC_OBTAIN_INDEX_ENTRY(p)\t\t\tfrom_disked_rc_index_entry((unsigned char *)(p), 0)\n \n #define RC_ACTUAL_OBJECT_ENTRY_SIZE(e)\t\t(OBJECT_ENTRY_SIZE + 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@@ -89,6 +91,7 @@ struct rc_object_entry *from_disked_rc_object_entry(unsigned char *src, struct r\n unsigned char *to_disked_rc_object_entry(struct rc_object_entry *src, unsigned char **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@@ -101,6 +104,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 0662c8c..825a9dd 100644\n--- a/revision.h\n+++ b/revision.h\n@@ -24,17 +24,31 @@ struct rev_info;\n struct log_info;\n struct string_list;\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@@ -149,7 +163,7 @@ struct rev_info {\n \n \t/* notes-specific options: which refs to show */\n \tstruct display_notes_opt notes_opt;\n-\t\n+\n \t/* caching info, used ONLY by traverse_cache_slice */\n \tstruct rev_cache_info rev_cache_info;\n };\n-- \ntg: (00928d8..) t/rc/misc (depends on: t/rc/objects)\n"}]}