{"thread":{"id":"14364","subject":"[PATCH 1/3] cherry: cache patch-ids to avoid repeating work","startedAt":"2008-07-09T03:53:05Z","lastAt":"2008-07-16T07:22:30Z","messageCount":21,"participants":["Geoffrey Irving","Junio C Hamano","Johannes Schindelin","Karl Hasselström","Johan Herland"],"isPatch":true,"patchVersion":1,"patchTotal":3},"messages":[{"id":"82673","messageId":"7f9d599f0807082053w4603d0bbgfead9127c33b78b5@mail.gmail.com","threadId":"14364","inReplyTo":null,"subject":"[PATCH 1/3] cherry: cache patch-ids to avoid repeating work","fromName":"Geoffrey Irving","fromEmail":"irving@naml.us","sentAt":"2008-07-09T03:53:05Z","receivedAt":"2008-07-09T03:53:05Z","isPatch":true,"sender":{"key":"irving@naml.us","avatar":"https://gravatar.com/avatar/52d7452fcd134aac0fa12f57a3bb7ef5f3f7e73ca0ab36736d06c6a6132de718?d=mp&s=160"},"body":">From a3afd1455d215a541e1481e0f064df743d9219cc Mon Sep 17 00:00:00 2001\nFrom: Geoffrey Irving \nDate: Sat, 7 Jun 2008 16:03:49 -0700\nSubject: [PATCH 1/3] cherry: cache patch-ids to avoid repeating work\n\nAdded cached-sha-map.[hc] implementing a persistent hash map from sha1 to\nsha1. The map is read with mmap, and completely rewritten if any entries\nchange. It would be good to add incremental update to handle the usual case\nwhere only a few entries change.\n\nThis structure is used by patch-ids.c to cache the mapping from commit to\npatch-id into $GIT_DIR/patch-id-cache. In the one case I've tested so far,\nthis speeds up the second invocation of git-cherry by two orders of\nmagnitude.\n\nOriginal code cannibalized from Johannes Schindelin's notes-index structure.\n---\n\nHere's another (hopefully final) version of the patch-id-cache code,\nsince I finally got around to updating it with Dscho's suggestions.\n\n Makefile | 2 +\n cached-sha1-map.c | 182 +++++++++++++++++++++++++++++++++++++++++++++++++++++\n cached-sha1-map.h | 45 +++++++++++++\n patch-ids.c | 18 +++++-\n 4 files changed, 246 insertions(+), 1 deletions(-)\n create mode 100644 cached-sha1-map.c\n create mode 100644 cached-sha1-map.h\n\ndiff --git a/Makefile b/Makefile\nindex 4796565..f7360e1 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -356,6 +356,7 @@ LIB_H += pack-refs.h\n LIB_H += pack-revindex.h\n LIB_H += parse-options.h\n LIB_H += patch-ids.h\n+LIB_H += cached-sha1-map.h\n LIB_H += path-list.h\n LIB_H += pkt-line.h\n LIB_H += progress.h\n@@ -436,6 +437,7 @@ LIB_OBJS += pager.o\n LIB_OBJS += parse-options.o\n LIB_OBJS += patch-delta.o\n LIB_OBJS += patch-ids.o\n+LIB_OBJS += cached-sha1-map.o\n LIB_OBJS += path-list.o\n LIB_OBJS += path.o\n LIB_OBJS += pkt-line.o\ndiff --git a/cached-sha1-map.c b/cached-sha1-map.c\nnew file mode 100644\nindex 0000000..e363745\n--- /dev/null\n+++ b/cached-sha1-map.c\n@@ -0,0 +1,182 @@\n+#include \"cached-sha1-map.h\"\n+\n+union cached_sha1_map_header {\n+\tstruct {\n+\t\tchar signature[4]; /* HASH */\n+\t\toff_t count, size;\n+\t};\n+\tstruct cached_sha1_entry padding; /* pad header out to 40 bytes */\n+};\n+\n+static const char *signature = \"HASH\";\n+\n+static void init_empty_map(struct cached_sha1_map *cache, size_t size)\n+{\n+\tcache->count = 0;\n+\tcache->size = size;\n+\tcache->initialized = 1;\n+\tcache->dirty = 1;\n+\tcache->mmapped = 0;\n+\tcache->entries = xcalloc(size, sizeof(struct cached_sha1_entry));\n+}\n+\n+static void grow_map(struct cached_sha1_map *cache)\n+{\n+\tstruct cached_sha1_map new_cache;\n+\tsize_t i;\n+\n+\t/* allocate cache with twice the size */\n+\tnew_cache.filename = cache->filename;\n+\tinit_empty_map(&new_cache, cache->size * 2);\n+\n+\t/* reinsert all entries */\n+ \tfor (i = 0; i < cache->size; i++)\n+\t\tif (!is_null_sha1(cache->entries[i].key))\n+\t\t\tset_cached_sha1_entry(&new_cache,\n+\t\t\t\tcache->entries[i].key, cache->entries[i].value);\n+\t/* finish */\n+\tfree_cached_sha1_map(cache);\n+\t*cache = new_cache;\n+}\n+\n+static void init_cached_sha1_map(struct cached_sha1_map *cache)\n+{\n+\tint fd;\n+\tunion cached_sha1_map_header header;\n+\n+\tif (cache->initialized)\n+\t\treturn;\n+\n+\tfd = open(git_path(cache->filename), O_RDONLY);\n+\tif (fd < 0) {\n+\t\tinit_empty_map(cache, 64);\n+\t\treturn;\n+\t}\n+\n+\tif (read_in_full(fd, &header, sizeof(header)) != sizeof(header))\n+\t\tdie(\"cannot read %s header\", cache->filename);\n+\n+\tif (memcmp(header.signature, signature, 4))\n+\t\tdie(\"%s has invalid header\", cache->filename);\n+\n+\tif (header.size & (header.size-1))\n+\t\tdie(\"%s size %lld is not a power of two\", cache->filename,\n+\t\t\t(long long)header.size);\n+\n+\tcache->count = header.count;\n+\tcache->size = header.size;\n+\tcache->dirty = 0;\n+\tcache->initialized = 1;\n+\tcache->mmapped = 1;\n+\n+\t/* check off_t to size_t conversion */\n+\tif (cache->count != header.count || cache->size != header.size)\n+\t\tdie(\"%s is too large to hold in memory\", cache->filename);\n+\n+\t/* mmap entire file so that file / memory blocks are aligned */\n+\tcache->entries = xmmap(NULL,\n+\t\tsizeof(struct cached_sha1_entry) * (header.size + 1),\n+\t\tPROT_READ | PROT_WRITE, MAP_PRIVATE, fd, 0);\n+\tcache->entries += 1; /* skip header */\n+\tclose(fd);\n+}\n+\n+int write_cached_sha1_map(struct cached_sha1_map *cache)\n+{\n+\tunion cached_sha1_map_header header;\n+\tstruct lock_file update_lock;\n+\tint fd;\n+\tsize_t entry_size;\n+\n+\tif (!cache->initialized || !cache->dirty)\n+\t\treturn 0;\n+\n+\tfd = hold_lock_file_for_update(&update_lock,\n+\t\t\tgit_path(cache->filename), 0);\n+\n+\tif (fd < 0)\n+\t\treturn error(\"could not construct %s\", cache->filename);\n+\n+\tmemcpy(header.signature, signature, 4);\n+\theader.count = cache->count;\n+\theader.size = cache->size;\n+\tentry_size = sizeof(struct cached_sha1_entry) * cache->size;\n+\tif (write_in_full(fd, &header, sizeof(header)) != sizeof(header)\n+\t\t|| write_in_full(fd, cache->entries, entry_size) != entry_size)\n+\t\treturn error(\"could not write %s\", cache->filename);\n+\n+\tif (commit_lock_file(&update_lock) < 0)\n+\t\treturn error(\"could not write %s\", cache->filename);\n+\n+\tcache->dirty = 0;\n+\treturn 0;\n+}\n+\n+void free_cached_sha1_map(struct cached_sha1_map *cache)\n+{\n+\tif (!cache->initialized)\n+\t\treturn;\n+\n+\tif (cache->mmapped)\n+\t\tmunmap(cache->entries - 1,\n+\t\t\tsizeof(struct cached_sha1_entry) * (cache->size + 1));\n+\telse\n+\t\tfree(cache->entries);\n+}\n+\n+static size_t get_hash_index(const unsigned char *sha1)\n+{\n+\treturn ntohl(*(size_t*)sha1);\n+}\n+\n+int get_cached_sha1_entry(struct cached_sha1_map *cache,\n+\tconst unsigned char *key, unsigned char *value)\n+{\n+\tsize_t i, mask;\n+\n+\tif (!cache->initialized)\n+\t\tinit_cached_sha1_map(cache);\n+\n+\tmask = cache->size - 1;\n+\n+\tfor (i = get_hash_index(key) & mask; ; i = (i+1) & mask) {\n+\t\tif (!hashcmp(key, cache->entries[i].key)) {\n+\t\t\thashcpy(value, cache->entries[i].value);\n+\t\t\treturn 0;\n+\t\t} else if (is_null_sha1(cache->entries[i].key))\n+\t\t\treturn -1;\n+\t}\n+}\n+\n+void set_cached_sha1_entry(struct cached_sha1_map *cache,\n+\tconst unsigned char *key, const unsigned char *value)\n+{\n+\tsize_t i, mask;\n+\tstruct cached_sha1_entry *entry;\n+\n+\tif (!cache->initialized)\n+\t\tinit_cached_sha1_map(cache);\n+\n+\tif (4*cache->count >= 3*cache->size)\n+\t\tgrow_map(cache);\n+\n+\tmask = cache->size - 1;\n+\n+\tfor (i = get_hash_index(key) & mask; ; i = (i+1) & mask) {\n+\t\tentry = cache->entries+i;\n+\n+\t\tif (is_null_sha1(entry->key)) {\n+\t\t\thashcpy(entry->key, key);\n+\t\t\thashcpy(entry->value, value);\n+\t\t\tcache->count++;\n+\t\t\tcache->dirty = 1;\n+\t\t\treturn;\n+\t\t} else if(!hashcmp(key, entry->key)) {\n+\t\t\tif (hashcmp(value, entry->value)) {\n+\t\t\t\thashcpy(entry->value, value);\n+\t\t\t\tcache->dirty = 1;\n+\t\t\t}\n+\t\t\treturn;\n+\t\t}\n+\t}\n+}\ndiff --git a/cached-sha1-map.h b/cached-sha1-map.h\nnew file mode 100644\nindex 0000000..f592d07\n--- /dev/null\n+++ b/cached-sha1-map.h\n@@ -0,0 +1,45 @@\n+#ifndef CACHED_SHA1_MAP_H\n+#define CACHED_SHA1_MAP_H\n+\n+#include \"cache.h\"\n+\n+/*\n+ * A cached-sha1-map is a file storing a hash map from sha1 to sha1.\n+ *\n+ * The file is mmap'ed, updated in memory during operation, and flushed\n+ * back to disk when freed. Currently the entire file is rewritten for\n+ * any change. This could be a significant bottleneck for common uses,\n+ * so it would be good to fix this later if possible.\n+ *\n+ * The performance of a hash map depends highly on a good hashing\n+ * algorithm, to avoid collisions. Lucky us! SHA-1 is a pretty good\n+ * hashing algorithm.\n+ */\n+\n+struct cached_sha1_entry {\n+\tunsigned char key[20];\n+\tunsigned char value[20];\n+};\n+\n+struct cached_sha1_map {\n+\tconst char *filename; /* relative to GIT_DIR */\n+\n+\t/* rest is for internal use */\n+\tsize_t count, size;\n+\tunsigned int initialized : 1;\n+\tunsigned int dirty : 1;\n+\tunsigned int mmapped : 1;\n+\tstruct cached_sha1_entry *entries; /* pointer to mmap'ed memory + 1 */\n+};\n+\n+extern int get_cached_sha1_entry(struct cached_sha1_map *cache,\n+\tconst unsigned char *key,unsigned char *value);\n+\n+extern void set_cached_sha1_entry(struct cached_sha1_map *cache,\n+\tconst unsigned char *key, const unsigned char *value);\n+\n+extern int write_cached_sha1_map(struct cached_sha1_map *cache);\n+\n+extern void free_cached_sha1_map(struct cached_sha1_map *cache);\n+\n+#endif\ndiff --git a/patch-ids.c b/patch-ids.c\nindex 3be5d31..36332f3 100644\n--- a/patch-ids.c\n+++ b/patch-ids.c\n@@ -2,17 +2,31 @@\n #include \"diff.h\"\n #include \"commit.h\"\n #include \"patch-ids.h\"\n+#include \"cached-sha1-map.h\"\n+\n+struct cached_sha1_map patch_id_cache;\n\n static int commit_patch_id(struct commit *commit, struct diff_options *options,\n \t\t unsigned char *sha1)\n {\n+\t/* pull patch-id out of the cache if possible */\n+\tpatch_id_cache.filename = \"patch-id-cache\";\n+\tif (!get_cached_sha1_entry(&patch_id_cache, commit->object.sha1, sha1))\n+\t\treturn 0;\n+\n \tif (commit->parents)\n \t\tdiff_tree_sha1(commit->parents->item->object.sha1,\n \t\t commit->object.sha1, \"\", options);\n \telse\n \t\tdiff_root_tree_sha1(commit->object.sha1, \"\", options);\n \tdiffcore_std(options);\n-\treturn diff_flush_patch_id(options, sha1);\n+\tint ret = diff_flush_patch_id(options, sha1);\n+\tif (ret)\n+\t\treturn ret;\n+\n+\t/* record commit, patch-id pair in cache */\n+\tset_cached_sha1_entry(&patch_id_cache, commit->object.sha1, sha1);\n+\treturn 0;\n }\n\n static uint32_t take2(const unsigned char *id)\n@@ -136,6 +150,8 @@ int free_patch_ids(struct patch_ids *ids)\n \t\tnext = patches->next;\n \t\tfree(patches);\n \t}\n+\n+\twrite_cached_sha1_map(&patch_id_cache);\n \treturn 0;\n }\n\n-- \n1.5.6.2.258.g7a51a\n"},{"id":"82683","messageId":"7vfxqjmyg2.fsf@gitster.siamese.dyndns.org","threadId":"14364","inReplyTo":"7f9d599f0807082053w4603d0bbgfead9127c33b78b5@mail.gmail.com","subject":"Re: [PATCH 1/3] cherry: cache patch-ids to avoid repeating work","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2008-07-09T05:14:05Z","receivedAt":"2008-07-09T05:14:05Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Geoffrey Irving\" writes:\n\n> From a3afd1455d215a541e1481e0f064df743d9219cc Mon Sep 17 00:00:00 2001\n\nPlease drop this line.\n\n> From: Geoffrey Irving \n> Date: Sat, 7 Jun 2008 16:03:49 -0700\n> Subject: [PATCH 1/3] cherry: cache patch-ids to avoid repeating work\n\nThese are Ok _if_ the difference between them and what you have in your\ne-mail header really matter (e.g. you are forwarding somebody else's\npatch). I don't think it is in this case, though.\n\n> Added cached-sha-map.[hc] implementing a persistent hash map from sha1 to\n> sha1.\n\n\"Add cached-sha1-map.[ch]\" (imperative mood), not \"(here is what I) _did_\".\n\n> diff --git a/cached-sha1-map.c b/cached-sha1-map.c\n> new file mode 100644\n> index 0000000..e363745\n> --- /dev/null\n> +++ b/cached-sha1-map.c\n> @@ -0,0 +1,182 @@\n> +#include \"cached-sha1-map.h\"\n> +\n> +union cached_sha1_map_header {\n> +\tstruct {\n> +\t\tchar signature[4]; /* HASH */\n> +\t\toff_t count, size;\n> +\t};\n> +\tstruct cached_sha1_entry padding; /* pad header out to 40 bytes */\n> +};\n> +\n> +static const char *signature = \"HASH\";\n\nThat sounds a bit too generic, doesn't it, to protect ourselves from\ngetting confused by some other filetype?\n\n> +static void init_cached_sha1_map(struct cached_sha1_map *cache)\n> +{\n> +\tint fd;\n> +\tunion cached_sha1_map_header header;\n> +\n> +\tif (cache->initialized)\n> +\t\treturn;\n> +\n> +\tfd = open(git_path(cache->filename), O_RDONLY);\n> +\tif (fd < 0) {\n> +\t\tinit_empty_map(cache, 64);\n> +\t\treturn;\n\nCheck errno and do this only when ENOENT. Other errors should be caught\nand reported.\n\n> +\t}\n> +\n> +\tif (read_in_full(fd, &header, sizeof(header)) != sizeof(header))\n> +\t\tdie(\"cannot read %s header\", cache->filename);\n> +\n> +\tif (memcmp(header.signature, signature, 4))\n> +\t\tdie(\"%s has invalid header\", cache->filename);\n> +\n> +\tif (header.size & (header.size-1))\n> +\t\tdie(\"%s size %lld is not a power of two\", cache->filename,\n> +\t\t\t(long long)header.size);\n\nTwo issues and a half:\n\n - Isn't it gcc extension to be able to say header.signature, bypassing\n the anonymous structure inside the union that the \"header\" itself is?\n\n - The signature header (count and size) is defined to be off_t, which\n makes the cached file unusable across architectures. The map header\n structure should be specified with explicit size:\n\n\tunion {\n\t\tstruct {\n\t char sig[4];\n\t\t\tuint32_t version;\n uint32_t count;\n unit32_t size;\n\t\t} u;\n struct cached_sha1_entry pad;\n };\n\n the uint32_t fields should be treated as network byte order integers,\n e.g.\n\n\tcache->count = ntohl(header.u.count);\n header.u.size = htonl(cache->size);\n\n - If this file is truly intended as \"cache\", shouldn't corruption of it\n be detected, reported but otherwise ignored, so that the lookup would\n continue in degraded uncached mode?\n\n> +\t/* check off_t to size_t conversion */\n> +\tif (cache->count != header.count || cache->size != header.size)\n> +\t\tdie(\"%s is too large to hold in memory\", cache->filename);\n\nThis does not make sense to me. What you are checking does not match the\nerror message.\n\nIf you are making the file format architecture dependent (which I would\nsuggest strongly against), you can use the same type and be done with it.\nOtherwise, if you are making the format portable across architectures,\nthen you would know how large the on-disk integer will be, so as long as\nyou use appropriate type that is large enough for cache->count you should\nbe Ok.\n\nWhat you may want to check is that (header.u.size + 1) * sizeof(entry)\ndoes not wrap around, but you don't.\n\n> +\t/* mmap entire file so that file / memory blocks are aligned */\n> +\tcache->entries = xmmap(NULL,\n> +\t\tsizeof(struct cached_sha1_entry) * (header.size + 1),\n> +\t\tPROT_READ | PROT_WRITE, MAP_PRIVATE, fd, 0);\n\nI think this will die() if the file is too large to map. Ideally you\nwould want to allow this mmap to fail if the cache is too large, in which\ncase you can gracefully degrade to cacheless mode of operation, but that\ncan probably be left to 47th round.\n\n> +int write_cached_sha1_map(struct cached_sha1_map *cache)\n> +{\n> +\tunion cached_sha1_map_header header;\n> +\tstruct lock_file update_lock;\n> +\tint fd;\n> +\tsize_t entry_size;\n> +\n> +\tif (!cache->initialized || !cache->dirty)\n> +\t\treturn 0;\n> +\n> +\tfd = hold_lock_file_for_update(&update_lock,\n> +\t\t\tgit_path(cache->filename), 0);\n> +\n> +\tif (fd < 0)\n> +\t\treturn error(\"could not construct %s\", cache->filename);\n\nUse a \"const char *\" to hold git_path(cache->filename) upfront in the\nfunction, use it to obtain lock _and_ for reporting.\n\n> +\tmemcpy(header.signature, signature, 4);\n> +\theader.count = cache->count;\n> +\theader.size = cache->size;\n\nAnd here will be htonl().\n\n> +\tentry_size = sizeof(struct cached_sha1_entry) * cache->size;\n\nTypically \"entry_size\" means the size of individual entry; this is the\nsize of the whole thing.\n\n> +\tif (write_in_full(fd, &header, sizeof(header)) != sizeof(header)\n> +\t\t|| write_in_full(fd, cache->entries, entry_size) != entry_size)\n> +\t\treturn error(\"could not write %s\", cache->filename);\n> +\n> +\tif (commit_lock_file(&update_lock) < 0)\n> +\t\treturn error(\"could not write %s\", cache->filename);\n> +\n> +\tcache->dirty = 0;\n> +\treturn 0;\n> +}\n\nBut it is good that you used this intermediate variable; the above\nwrite_in_full() is much easier to read than the xmmap() above at the end\nof init_cached_sha1_map() function.\n\n> +static size_t get_hash_index(const unsigned char *sha1)\n> +{\n> +\treturn ntohl(*(size_t*)sha1);\n> +}\n\nTwo issues:\n\n - I do not see any guarantee that sha1 is suitably aligned for reading\n size_t bytes off of;\n\n - size_t is architecture dependent, so you would get different hash value\n depending on the architecture, which again makes this file format\n unportable.\n\n> diff --git a/patch-ids.c b/patch-ids.c\n> index 3be5d31..36332f3 100644\n> --- a/patch-ids.c\n> +++ b/patch-ids.c\n> @@ -2,17 +2,31 @@\n> #include \"diff.h\"\n> #include \"commit.h\"\n> #include \"patch-ids.h\"\n> +#include \"cached-sha1-map.h\"\n> +\n> +struct cached_sha1_map patch_id_cache;\n\nDoes this have to be extern?\n\n> static int commit_patch_id(struct commit *commit, struct diff_options *options,\n> \t\t unsigned char *sha1)\n> {\n> +\t/* pull patch-id out of the cache if possible */\n> +\tpatch_id_cache.filename = \"patch-id-cache\";\n> +\tif (!get_cached_sha1_entry(&patch_id_cache, commit->object.sha1, sha1))\n> +\t\treturn 0;\n> +\n> \tif (commit->parents)\n> \t\tdiff_tree_sha1(commit->parents->item->object.sha1,\n> \t\t commit->object.sha1, \"\", options);\n> \telse\n> \t\tdiff_root_tree_sha1(commit->object.sha1, \"\", options);\n> \tdiffcore_std(options);\n> -\treturn diff_flush_patch_id(options, sha1);\n> +\tint ret = diff_flush_patch_id(options, sha1);\n\nDecl-after-statement.\n\n> +\tif (ret)\n> +\t\treturn ret;\n> +\n> +\t/* record commit, patch-id pair in cache */\n> +\tset_cached_sha1_entry(&patch_id_cache, commit->object.sha1, sha1);\n> +\treturn 0;\n> }\n"},{"id":"82685","messageId":"7f9d599f0807082226oee83bedrf13d254ae12be274@mail.gmail.com","threadId":"14364","inReplyTo":"7vfxqjmyg2.fsf@gitster.siamese.dyndns.org","subject":"Re: [PATCH 1/3] cherry: cache patch-ids to avoid repeating work","fromName":"Geoffrey Irving","fromEmail":"irving@naml.us","sentAt":"2008-07-09T05:26:17Z","receivedAt":"2008-07-09T05:26:17Z","isPatch":true,"sender":{"key":"irving@naml.us","avatar":"https://gravatar.com/avatar/52d7452fcd134aac0fa12f57a3bb7ef5f3f7e73ca0ab36736d06c6a6132de718?d=mp&s=160"},"body":"On Tue, Jul 8, 2008 at 10:14 PM, Junio C Hamano wrote:\n> \"Geoffrey Irving\" writes:\n>\n>> From a3afd1455d215a541e1481e0f064df743d9219cc Mon Sep 17 00:00:00 2001\n>\n> Please drop this line.\n>\n>> From: Geoffrey Irving \n>> Date: Sat, 7 Jun 2008 16:03:49 -0700\n>> Subject: [PATCH 1/3] cherry: cache patch-ids to avoid repeating work\n>\n> These are Ok _if_ the difference between them and what you have in your\n> e-mail header really matter (e.g. you are forwarding somebody else's\n> patch). I don't think it is in this case, though.\n>\n>> Added cached-sha-map.[hc] implementing a persistent hash map from sha1 to\n>> sha1.\n>\n> \"Add cached-sha1-map.[ch]\" (imperative mood), not \"(here is what I) _did_\".\n>\n>> diff --git a/cached-sha1-map.c b/cached-sha1-map.c\n>> new file mode 100644\n>> index 0000000..e363745\n>> --- /dev/null\n>> +++ b/cached-sha1-map.c\n>> @@ -0,0 +1,182 @@\n>> +#include \"cached-sha1-map.h\"\n>> +\n>> +union cached_sha1_map_header {\n>> + struct {\n>> + char signature[4]; /* HASH */\n>> + off_t count, size;\n>> + };\n>> + struct cached_sha1_entry padding; /* pad header out to 40 bytes */\n>> +};\n>> +\n>> +static const char *signature = \"HASH\";\n>\n> That sounds a bit too generic, doesn't it, to protect ourselves from\n> getting confused by some other filetype?\n>\n>> +static void init_cached_sha1_map(struct cached_sha1_map *cache)\n>> +{\n>> + int fd;\n>> + union cached_sha1_map_header header;\n>> +\n>> + if (cache->initialized)\n>> + return;\n>> +\n>> + fd = open(git_path(cache->filename), O_RDONLY);\n>> + if (fd < 0) {\n>> + init_empty_map(cache, 64);\n>> + return;\n>\n> Check errno and do this only when ENOENT. Other errors should be caught\n> and reported.\n>\n>> + }\n>> +\n>> + if (read_in_full(fd, &header, sizeof(header)) != sizeof(header))\n>> + die(\"cannot read %s header\", cache->filename);\n>> +\n>> + if (memcmp(header.signature, signature, 4))\n>> + die(\"%s has invalid header\", cache->filename);\n>> +\n>> + if (header.size & (header.size-1))\n>> + die(\"%s size %lld is not a power of two\", cache->filename,\n>> + (long long)header.size);\n>\n> Two issues and a half:\n>\n> - Isn't it gcc extension to be able to say header.signature, bypassing\n> the anonymous structure inside the union that the \"header\" itself is?\n>\n> - The signature header (count and size) is defined to be off_t, which\n> makes the cached file unusable across architectures. The map header\n> structure should be specified with explicit size:\n>\n> union {\n> struct {\n> char sig[4];\n> uint32_t version;\n> uint32_t count;\n> unit32_t size;\n> } u;\n> struct cached_sha1_entry pad;\n> };\n>\n> the uint32_t fields should be treated as network byte order integers,\n> e.g.\n>\n> cache->count = ntohl(header.u.count);\n> header.u.size = htonl(cache->size);\n>\n> - If this file is truly intended as \"cache\", shouldn't corruption of it\n> be detected, reported but otherwise ignored, so that the lookup would\n> continue in degraded uncached mode?\n>\n>> + /* check off_t to size_t conversion */\n>> + if (cache->count != header.count || cache->size != header.size)\n>> + die(\"%s is too large to hold in memory\", cache->filename);\n>\n> This does not make sense to me. What you are checking does not match the\n> error message.\n>\n> If you are making the file format architecture dependent (which I would\n> suggest strongly against), you can use the same type and be done with it.\n> Otherwise, if you are making the format portable across architectures,\n> then you would know how large the on-disk integer will be, so as long as\n> you use appropriate type that is large enough for cache->count you should\n> be Ok.\n>\n> What you may want to check is that (header.u.size + 1) * sizeof(entry)\n> does not wrap around, but you don't.\n>\n>> + /* mmap entire file so that file / memory blocks are aligned */\n>> + cache->entries = xmmap(NULL,\n>> + sizeof(struct cached_sha1_entry) * (header.size + 1),\n>> + PROT_READ | PROT_WRITE, MAP_PRIVATE, fd, 0);\n>\n> I think this will die() if the file is too large to map. Ideally you\n> would want to allow this mmap to fail if the cache is too large, in which\n> case you can gracefully degrade to cacheless mode of operation, but that\n> can probably be left to 47th round.\n>\n>> +int write_cached_sha1_map(struct cached_sha1_map *cache)\n>> +{\n>> + union cached_sha1_map_header header;\n>> + struct lock_file update_lock;\n>> + int fd;\n>> + size_t entry_size;\n>> +\n>> + if (!cache->initialized || !cache->dirty)\n>> + return 0;\n>> +\n>> + fd = hold_lock_file_for_update(&update_lock,\n>> + git_path(cache->filename), 0);\n>> +\n>> + if (fd < 0)\n>> + return error(\"could not construct %s\", cache->filename);\n>\n> Use a \"const char *\" to hold git_path(cache->filename) upfront in the\n> function, use it to obtain lock _and_ for reporting.\n>\n>> + memcpy(header.signature, signature, 4);\n>> + header.count = cache->count;\n>> + header.size = cache->size;\n>\n> And here will be htonl().\n>\n>> + entry_size = sizeof(struct cached_sha1_entry) * cache->size;\n>\n> Typically \"entry_size\" means the size of individual entry; this is the\n> size of the whole thing.\n>\n>> + if (write_in_full(fd, &header, sizeof(header)) != sizeof(header)\n>> + || write_in_full(fd, cache->entries, entry_size) != entry_size)\n>> + return error(\"could not write %s\", cache->filename);\n>> +\n>> + if (commit_lock_file(&update_lock) < 0)\n>> + return error(\"could not write %s\", cache->filename);\n>> +\n>> + cache->dirty = 0;\n>> + return 0;\n>> +}\n>\n> But it is good that you used this intermediate variable; the above\n> write_in_full() is much easier to read than the xmmap() above at the end\n> of init_cached_sha1_map() function.\n>\n>> +static size_t get_hash_index(const unsigned char *sha1)\n>> +{\n>> + return ntohl(*(size_t*)sha1);\n>> +}\n>\n> Two issues:\n>\n> - I do not see any guarantee that sha1 is suitably aligned for reading\n> size_t bytes off of;\n>\n> - size_t is architecture dependent, so you would get different hash value\n> depending on the architecture, which again makes this file format\n> unportable.\n>\n>> diff --git a/patch-ids.c b/patch-ids.c\n>> index 3be5d31..36332f3 100644\n>> --- a/patch-ids.c\n>> +++ b/patch-ids.c\n>> @@ -2,17 +2,31 @@\n>> #include \"diff.h\"\n>> #include \"commit.h\"\n>> #include \"patch-ids.h\"\n>> +#include \"cached-sha1-map.h\"\n>> +\n>> +struct cached_sha1_map patch_id_cache;\n>\n> Does this have to be extern?\n>\n>> static int commit_patch_id(struct commit *commit, struct diff_options *options,\n>> unsigned char *sha1)\n>> {\n>> + /* pull patch-id out of the cache if possible */\n>> + patch_id_cache.filename = \"patch-id-cache\";\n>> + if (!get_cached_sha1_entry(&patch_id_cache, commit->object.sha1, sha1))\n>> + return 0;\n>> +\n>> if (commit->parents)\n>> diff_tree_sha1(commit->parents->item->object.sha1,\n>> commit->object.sha1, \"\", options);\n>> else\n>> diff_root_tree_sha1(commit->object.sha1, \"\", options);\n>> diffcore_std(options);\n>> - return diff_flush_patch_id(options, sha1);\n>> + int ret = diff_flush_patch_id(options, sha1);\n>\n> Decl-after-statement.\n>\n>> + if (ret)\n>> + return ret;\n>> +\n>> + /* record commit, patch-id pair in cache */\n>> + set_cached_sha1_entry(&patch_id_cache, commit->object.sha1, sha1);\n>> + return 0;\n>> }\n\nThanks. I'll fix these in the next few days.\n\nShould I rewrite the patch sequence to incorporate these changes into\nthe first commit, or add them as a forth commit off the end?\n\nGeoffrey\n"},{"id":"82690","messageId":"7vprpnlglh.fsf@gitster.siamese.dyndns.org","threadId":"14364","inReplyTo":"7f9d599f0807082226oee83bedrf13d254ae12be274@mail.gmail.com","subject":"Re: [PATCH 1/3] cherry: cache patch-ids to avoid repeating work","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2008-07-09T06:24:58Z","receivedAt":"2008-07-09T06:24:58Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Geoffrey Irving\" writes:\n\n> On Tue, Jul 8, 2008 at 10:14 PM, Junio C Hamano wrote:\n> ...\n>>> }\n\nPlease don't quote the whole thing without trimming if you do not have any\ninterspersed comments/responses to quoted part.\n\n> Should I rewrite the patch sequence to incorporate these changes into\n> the first commit, or add them as a forth commit off the end?\n\nI strongly encourage the latter. We try not to keep early mistakes in the\nhistory (see my comments on your [2/3]).\n\nIt is not unusal for any sizeable new code to go through a few round of\nreview cycle without even queued to 'pu', and the general rule is until\nthe series hits 'next', it is either \"rejected (dropped on the floor),\nplease resend an improved version\" or \"ok now it is good, will queue\".\nAfter queued in 'next', improvements will continue incrementally.\n\nThink of this procedure as giving a chance for you to hide early\nembarrassment under the rug ;-)\n"},{"id":"82715","messageId":"alpine.DEB.1.00.0807091416480.5277@eeepc-johanness","threadId":"14364","inReplyTo":"7vprpnlglh.fsf@gitster.siamese.dyndns.org","subject":"Re: [PATCH 1/3] cherry: cache patch-ids to avoid repeating work","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2008-07-09T12:18:20Z","receivedAt":"2008-07-09T12:18:20Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Tue, 8 Jul 2008, Junio C Hamano wrote:\n\n> Think of this procedure as giving a chance for you to hide early \n> embarrassment under the rug ;-)\n\nFurther, as Shawn pointed out to me (and you will all be able to hear it \nfor yourselves soon), these patch iterations give you the chance to apply \nall the wisdom of the combined developers on this list to your patch, and \nin the end put your name on it :-)\n\nCiao,\nDscho\n"},{"id":"82774","messageId":"7f9d599f0807092034n438f0976pf44d4c9305871087@mail.gmail.com","threadId":"14364","inReplyTo":"7vprpnlglh.fsf@gitster.siamese.dyndns.org","subject":"[PATCH] cherry: cache patch-ids to avoid repeating work","fromName":"Geoffrey Irving","fromEmail":"irving@naml.us","sentAt":"2008-07-10T03:34:14Z","receivedAt":"2008-07-10T03:34:14Z","isPatch":true,"sender":{"key":"irving@naml.us","avatar":"https://gravatar.com/avatar/52d7452fcd134aac0fa12f57a3bb7ef5f3f7e73ca0ab36736d06c6a6132de718?d=mp&s=160"},"body":"Add cached-sha-map.[ch] implementing a persistent hash map from sha1 to\nsha1. The map is read with mmap, and completely rewritten if any entries\nchange. It would be good to add incremental update to handle the usual case\nwhere only a few entries change.\n\nThis structure is used by patch-ids.c to cache the mapping from commit to\npatch-id into $GIT_DIR/patch-id-cache. In the one case I've tested so far,\nthis speeds up the second invocation of git-cherry by two orders of\nmagnitude. The caching can be disabled by setting cherry.cachepatchids to\nfalse.\n\nOriginal code cannibalized from Johannes Schindelin's notes-index structure.\n\nSigned-off-by: Geoffrey Irving \n---\n\nNote: there are at least two \"holes\" in this code. First, it is impossible\nto verify the validity of the entries (this is impossible to fix). Second,\nit is possible to write a malicious patch-id-cache file that causes git-cherry\nto go into an infinite loop. Fixing the loop requires either traversing every\nentry on load (bad) or adding a second loop termination condition to\nfind_helper. Since looping forever is better than returning incorrect\nresults, I figured fixing the weaker hole would just result in a false sense\nof security.\n\nI'll await the next round of comments. :)\n\n Documentation/config.txt | 5 +\n Makefile | 2 +\n builtin-log.c | 12 ++\n cached-sha1-map.c | 269 ++++++++++++++++++++++++++++++++++++++++++++++\n cached-sha1-map.h | 45 ++++++++\n patch-ids.c | 26 +++++-\n patch-ids.h | 2 +\n 7 files changed, 360 insertions(+), 1 deletions(-)\n create mode 100644 cached-sha1-map.c\n create mode 100644 cached-sha1-map.h\n\ndiff --git a/Documentation/config.txt b/Documentation/config.txt\nindex 838794d..02b8113 100644\n--- a/Documentation/config.txt\n+++ b/Documentation/config.txt\n@@ -468,6 +468,11 @@ browser..path::\n \tbrowse HTML help (see '-w' option in linkgit:git-help[1]) or a\n \tworking repository in gitweb (see linkgit:git-instaweb[1]).\n\n+cherry.cachepatchids::\n+\tIf true, linkgit:git-cherry will store a cache of computed patch-ids\n+\tin $GIT_DIR/patch-id-cache in order to make repeated invocations faster.\n+\tDefaults to true.\n+\n clean.requireForce::\n \tA boolean to make git-clean do nothing unless given -f\n \tor -n. Defaults to true.\ndiff --git a/Makefile b/Makefile\nindex 4796565..f7360e1 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -356,6 +356,7 @@ LIB_H += pack-refs.h\n LIB_H += pack-revindex.h\n LIB_H += parse-options.h\n LIB_H += patch-ids.h\n+LIB_H += cached-sha1-map.h\n LIB_H += path-list.h\n LIB_H += pkt-line.h\n LIB_H += progress.h\n@@ -436,6 +437,7 @@ LIB_OBJS += pager.o\n LIB_OBJS += parse-options.o\n LIB_OBJS += patch-delta.o\n LIB_OBJS += patch-ids.o\n+LIB_OBJS += cached-sha1-map.o\n LIB_OBJS += path-list.o\n LIB_OBJS += path.o\n LIB_OBJS += pkt-line.o\ndiff --git a/builtin-log.c b/builtin-log.c\nindex 430d876..fbfefbd 100644\n--- a/builtin-log.c\n+++ b/builtin-log.c\n@@ -1081,6 +1081,16 @@ static int add_pending_commit(const char *arg,\nstruct rev_info *revs, int flags)\n \treturn -1;\n }\n\n+static int git_cherry_config(const char *var, const char *value, void *cb)\n+{\n+\tif (!strcmp(var, \"cherry.cachepatchids\")) {\n+\t\tcache_patch_ids = git_config_bool(var, value);\n+\t\treturn 0;\n+\t}\n+\n+\treturn 0;\n+}\n+\n static const char cherry_usage[] =\n \"git-cherry [-v] [] []\";\n int cmd_cherry(int argc, const char **argv, const char *prefix)\n@@ -1094,6 +1104,8 @@ int cmd_cherry(int argc, const char **argv,\nconst char *prefix)\n \tconst char *limit = NULL;\n \tint verbose = 0;\n\n+\tgit_config(git_cherry_config, NULL);\n+\n \tif (argc > 1 && !strcmp(argv[1], \"-v\")) {\n \t\tverbose = 1;\n \t\targc--;\ndiff --git a/cached-sha1-map.c b/cached-sha1-map.c\nnew file mode 100644\nindex 0000000..3ac5474\n--- /dev/null\n+++ b/cached-sha1-map.c\n@@ -0,0 +1,269 @@\n+#include \"cached-sha1-map.h\"\n+\n+union cached_sha1_map_header {\n+\tstruct {\n+\t\tchar signature[4]; /* CS1M */\n+\t\tuint32_t version;\n+\t\tuint32_t count;\n+\t\tuint32_t size;\n+\t} u;\n+\tstruct cached_sha1_entry pad; /* pad header out to 40 bytes */\n+};\n+\n+static const char *signature = \"CS1M\";\n+static const uint32_t version = 1;\n+\n+static int init_empty_map(struct cached_sha1_map *cache, uint32_t size)\n+{\n+\tcache->count = 0;\n+\tcache->size = size;\n+\tcache->initialized = 1;\n+\tcache->mmapped = 0;\n+\tcache->dirty = 1;\n+\n+\tcache->entries = calloc(size, sizeof(struct cached_sha1_entry));\n+\tif (!cache->entries) {\n+\t\twarning(\"failed to allocate empty map of size %\"PRIu32\" for %s\",\n+\t\t\tsize, git_path(cache->filename));\n+\t\tcache->size = 0;\n+\t\tcache->dirty = 0;\n+\t\treturn -1;\n+\t}\n+\treturn 0;\n+}\n+\n+static int grow_map(struct cached_sha1_map *cache)\n+{\n+\tstruct cached_sha1_map new_cache;\n+\tuint32_t i;\n+\n+\tif (cache->size * 2 == 0) {\n+\t\twarning(\"%s overflowed, so resetting to empty\",\n+\t\t\tgit_path(cache->filename));\n+\t\treturn init_empty_map(cache, 64);\n+\t}\n+\n+\t/* allocate cache with twice the size */\n+\tnew_cache.filename = cache->filename;\n+\tif (init_empty_map(&new_cache, cache->size * 2)) {\n+\t\twarning(\"failed to grow %s to size %\"PRIu32,\n+\t\t\tgit_path(cache->filename), cache->size * 2);\n+\t\treturn init_empty_map(cache, 64);\n+\t}\n+\n+\t/* reinsert all entries */\n+ \tfor (i = 0; i < cache->size; i++)\n+\t\tif (!is_null_sha1(cache->entries[i].key))\n+\t\t\tset_cached_sha1_entry(&new_cache,\n+\t\t\t\tcache->entries[i].key, cache->entries[i].value);\n+\t/* finish */\n+\tfree_cached_sha1_map(cache);\n+\t*cache = new_cache;\n+\treturn 0;\n+}\n+\n+/* Any errors that occur result in the cache being initialized to empty */\n+static int init_cached_sha1_map(struct cached_sha1_map *cache)\n+{\n+\tint fd;\n+\tunion cached_sha1_map_header header;\n+\tconst char *filename;\n+\tsize_t map_size;\n+\n+\tif (cache->initialized)\n+\t\treturn cache->size ? 0 : -1;\n+\n+\tfilename = git_path(cache->filename);\n+\tfd = open(filename, O_RDONLY);\n+\tif (fd < 0) {\n+\t\tif (errno != ENOENT)\n+\t\t\twarning(\"failed to read '%s': %s\", filename,\n+\t\t\t\tstrerror(errno));\n+\t\tgoto empty;\n+\t}\n+\n+\tif (read_in_full(fd, &header, sizeof(header)) != sizeof(header))\n+\t{\n+\t\twarning(\"cannot read %s header\", filename);\n+\t\tgoto empty;\n+\t}\n+\n+\tif (memcmp(header.u.signature, signature, 4))\n+\t{\n+\t\twarning(\"%s has invalid header\", filename);\n+\t\tgoto empty;\n+\t}\n+\n+\tif (ntohl(header.u.version) != version)\n+\t{\n+\t\twarning(\"%s has unrecognized version %\"PRIu32, filename,\n+\t\t\tntohl(header.u.version));\n+\t\tgoto empty;\n+\t}\n+\n+\tcache->count = ntohl(header.u.count);\n+\tcache->size = ntohl(header.u.size);\n+\n+\tif (cache->size & (cache->size-1))\n+\t{\n+\t\twarning(\"%s is corrupt: size %\"PRIu32\" is not a power of two\",\n+\t\t\tfilename, cache->size);\n+\t\tgoto empty;\n+\t}\n+\n+\tif (cache->count >= cache->size)\n+\t{\n+\t\twarning(\"%s is corrupt: count %\"PRIu32\" >= size %\"PRIu32,\n+\t\t\tfilename, cache->count, cache->size);\n+\t\tgoto empty;\n+\t}\n+\n+\tcache->dirty = 0;\n+\tcache->initialized = 1;\n+\tcache->mmapped = 1;\n+\n+\t/* mmap entire file so that file / memory blocks are aligned */\n+\tmap_size = sizeof(struct cached_sha1_entry) * (cache->size + 1);\n+\tcache->entries = mmap(NULL, map_size,\n+\t\tPROT_READ | PROT_WRITE, MAP_PRIVATE, fd, 0);\n+\tif (cache->entries == MAP_FAILED) {\n+\t\t/* this is just a cache, so don't free pack memory and retry */\n+\t\twarning(\"%s mmap failed: %s\", filename, strerror(errno));\n+\t\tgoto empty;\n+\t}\n+\tcache->entries += 1; /* skip header */\n+\treturn 0;\n+\n+empty:\n+\tif (fd >= 0)\n+\t\tclose(fd);\n+\treturn init_empty_map(cache, 64);\n+}\n+\n+int write_cached_sha1_map(struct cached_sha1_map *cache)\n+{\n+\tunion cached_sha1_map_header header;\n+\tstruct lock_file update_lock;\n+\tint fd;\n+\tsize_t map_size;\n+\tconst char *filename;\n+\n+\tif (!cache->initialized || !cache->dirty)\n+\t\treturn 0;\n+\n+\tfilename = git_path(cache->filename);\n+\tfd = hold_lock_file_for_update(&update_lock, filename, 0);\n+\n+\tif (fd < 0)\n+\t{\n+\t\twarning(\"could not construct %s\", filename);\n+\t\treturn -1;\n+\t}\n+\n+\tmemcpy(header.u.signature, signature, 4);\n+\theader.u.version = htonl(version);\n+\theader.u.count = htonl(cache->count);\n+\theader.u.size = htonl(cache->size);\n+\tmap_size = sizeof(struct cached_sha1_entry) * cache->size;\n+\tif (write_in_full(fd, &header, sizeof(header)) != sizeof(header)\n+\t\t|| write_in_full(fd, cache->entries, map_size) != map_size)\n+\t{\n+\t\twarning(\"could not write %s\", filename);\n+\t\treturn -1;\n+\t}\n+\n+\tif (commit_lock_file(&update_lock) < 0)\n+\t{\n+\t\twarning(\"could not write %s\", filename);\n+\t\treturn -1;\n+\t}\n+\n+\tcache->dirty = 0;\n+\treturn 0;\n+}\n+\n+void free_cached_sha1_map(struct cached_sha1_map *cache)\n+{\n+\tif (!cache->initialized)\n+\t\treturn;\n+\n+\tif (cache->mmapped)\n+\t\tmunmap(cache->entries - 1,\n+\t\t\tsizeof(struct cached_sha1_entry) * (cache->size + 1));\n+\telse\n+\t\tfree(cache->entries);\n+}\n+\n+/* The fact that size is a power of two means count-1 <= INT32_MAX, so it\n+ * is safe to return signed integers here. */\n+static int32_t get_hash_index(const unsigned char *sha1)\n+{\n+\t/* this is alignment safe since 40 is a multiple of 4 */\n+\treturn ntohl(*(uint32_t*)sha1);\n+}\n+\n+/*\n+ * Returns the index if the entry exists, and the complemented index of\n+ * the next free entry otherwise.\n+ */\n+static int32_t find_helper(struct cached_sha1_map *cache,\n+\tconst unsigned char *key)\n+{\n+\tint32_t i, mask;\n+\n+\tmask = cache->size - 1;\n+\n+\tfor (i = get_hash_index(key) & mask; ; i = (i+1) & mask) {\n+\t\tif (!hashcmp(key, cache->entries[i].key))\n+\t\t\treturn i;\n+\t\telse if (is_null_sha1(cache->entries[i].key))\n+\t\t\treturn ~i;\n+\t}\n+}\n+\n+int get_cached_sha1_entry(struct cached_sha1_map *cache,\n+\tconst unsigned char *key, unsigned char *value)\n+{\n+\tint32_t i;\n+\n+\tif (init_cached_sha1_map(cache))\n+\t\treturn -1;\n+\n+\ti = find_helper(cache, key);\n+\tif(i < 0)\n+\t\treturn -1;\n+\n+\t/* entry found, return value */\n+\thashcpy(value, cache->entries[i].value);\n+\treturn 0;\n+}\n+\n+int set_cached_sha1_entry(struct cached_sha1_map *cache,\n+\tconst unsigned char *key, const unsigned char *value)\n+{\n+\tint32_t i;\n+\tstruct cached_sha1_entry *entry;\n+\n+\tif (init_cached_sha1_map(cache))\n+\t\treturn -1;\n+\n+\ti = find_helper(cache, key);\n+\n+\tif (i < 0) { /* write new entry */\n+\t\tentry = cache->entries + ~i;\n+\t\thashcpy(entry->key, key);\n+\t\thashcpy(entry->value, value);\n+\t\tcache->count++;\n+\t\tcache->dirty = 1;\n+\t} else { /* overwrite existing entry */\n+\t\tentry = cache->entries + i;\n+\t\tif (hashcmp(value, entry->value)) {\n+\t\t\thashcpy(entry->value, value);\n+\t\t\tcache->dirty = 1;\n+\t\t}\n+\t}\n+\n+\tif (4*cache->count >= 3*cache->size)\n+\t\treturn grow_map(cache);\n+\treturn 0;\n+}\ndiff --git a/cached-sha1-map.h b/cached-sha1-map.h\nnew file mode 100644\nindex 0000000..296c17c\n--- /dev/null\n+++ b/cached-sha1-map.h\n@@ -0,0 +1,45 @@\n+#ifndef CACHED_SHA1_MAP_H\n+#define CACHED_SHA1_MAP_H\n+\n+#include \"cache.h\"\n+\n+/*\n+ * A cached-sha1-map is a file storing a hash map from sha1 to sha1.\n+ *\n+ * The file is mmap'ed, updated in memory during operation, and flushed\n+ * back to disk when freed. Currently the entire file is rewritten for\n+ * any change. This could be a significant bottleneck for common uses,\n+ * so it would be good to fix this later if possible.\n+ *\n+ * The performance of a hash map depends highly on a good hashing\n+ * algorithm, to avoid collisions. Lucky us! SHA-1 is a pretty good\n+ * hashing algorithm.\n+ */\n+\n+struct cached_sha1_entry {\n+\tunsigned char key[20];\n+\tunsigned char value[20];\n+};\n+\n+struct cached_sha1_map {\n+\tconst char *filename; /* relative to GIT_DIR */\n+\n+\t/* rest is for internal use */\n+\tuint32_t count, size;\n+\tunsigned int initialized : 1;\n+\tunsigned int dirty : 1;\n+\tunsigned int mmapped : 1;\n+\tstruct cached_sha1_entry *entries; /* pointer to mmap'ed memory + 1 */\n+};\n+\n+extern int get_cached_sha1_entry(struct cached_sha1_map *cache,\n+\tconst unsigned char *key,unsigned char *value);\n+\n+extern int set_cached_sha1_entry(struct cached_sha1_map *cache,\n+\tconst unsigned char *key, const unsigned char *value);\n+\n+extern int write_cached_sha1_map(struct cached_sha1_map *cache);\n+\n+extern void free_cached_sha1_map(struct cached_sha1_map *cache);\n+\n+#endif\ndiff --git a/patch-ids.c b/patch-ids.c\nindex 3be5d31..663ffee 100644\n--- a/patch-ids.c\n+++ b/patch-ids.c\n@@ -2,17 +2,36 @@\n #include \"diff.h\"\n #include \"commit.h\"\n #include \"patch-ids.h\"\n+#include \"cached-sha1-map.h\"\n+\n+int cache_patch_ids = 1;\n+static struct cached_sha1_map patch_id_cache;\n\n static int commit_patch_id(struct commit *commit, struct diff_options *options,\n \t\t unsigned char *sha1)\n {\n+\tint ret;\n+\n+\t/* pull patch-id out of the cache if possible */\n+\tpatch_id_cache.filename = \"patch-id-cache\";\n+\tif (cache_patch_ids && !get_cached_sha1_entry(&patch_id_cache,\n+\t\t\tcommit->object.sha1, sha1))\n+\t\treturn 0;\n+\n \tif (commit->parents)\n \t\tdiff_tree_sha1(commit->parents->item->object.sha1,\n \t\t commit->object.sha1, \"\", options);\n \telse\n \t\tdiff_root_tree_sha1(commit->object.sha1, \"\", options);\n \tdiffcore_std(options);\n-\treturn diff_flush_patch_id(options, sha1);\n+\tret = diff_flush_patch_id(options, sha1);\n+\tif (ret)\n+\t\treturn ret;\n+\n+\t/* record commit, patch-id pair in cache */\n+\tif (cache_patch_ids)\n+\t\tset_cached_sha1_entry(&patch_id_cache, commit->object.sha1, sha1);\n+\treturn 0;\n }\n\n static uint32_t take2(const unsigned char *id)\n@@ -136,6 +155,11 @@ int free_patch_ids(struct patch_ids *ids)\n \t\tnext = patches->next;\n \t\tfree(patches);\n \t}\n+\n+\t/* write cached patch-ids and ignore any errors that arise\n+\t * (e.g. if the repository is write protected) */\n+\tif (cache_patch_ids)\n+\t\twrite_cached_sha1_map(&patch_id_cache);\n \treturn 0;\n }\n\ndiff --git a/patch-ids.h b/patch-ids.h\nindex c8c7ca1..c0ebdc1 100644\n--- a/patch-ids.h\n+++ b/patch-ids.h\n@@ -18,4 +18,6 @@ int free_patch_ids(struct patch_ids *);\n struct patch_id *add_commit_patch_id(struct commit *, struct patch_ids *);\n struct patch_id *has_commit_patch_id(struct commit *, struct patch_ids *);\n\n+extern int cache_patch_ids;\n+\n #endif /* PATCH_IDS_H */\n-- \n1.5.6.2.256.g47cb9.dirty\n"},{"id":"82810","messageId":"7f9d599f0807100709u778f0ab1y28776d7efb831b61@mail.gmail.com","threadId":"14364","inReplyTo":"7f9d599f0807092034n438f0976pf44d4c9305871087@mail.gmail.com","subject":"Re: [PATCH] cherry: cache patch-ids to avoid repeating work","fromName":"Geoffrey Irving","fromEmail":"irving@naml.us","sentAt":"2008-07-10T14:09:14Z","receivedAt":"2008-07-10T14:09:14Z","isPatch":true,"sender":{"key":"irving@naml.us","avatar":"https://gravatar.com/avatar/52d7452fcd134aac0fa12f57a3bb7ef5f3f7e73ca0ab36736d06c6a6132de718?d=mp&s=160"},"body":"On Wed, Jul 9, 2008 at 8:34 PM, Geoffrey Irving wrote:\n> Add cached-sha-map.[ch] implementing a persistent hash map from sha1 to\n> sha1. The map is read with mmap, and completely rewritten if any entries\n> change. It would be good to add incremental update to handle the usual case\n> where only a few entries change.\n>\n> This structure is used by patch-ids.c to cache the mapping from commit to\n> patch-id into $GIT_DIR/patch-id-cache. In the one case I've tested so far,\n> this speeds up the second invocation of git-cherry by two orders of\n> magnitude. The caching can be disabled by setting cherry.cachepatchids to\n> false.\n>\n> Original code cannibalized from Johannes Schindelin's notes-index structure.\n>\n> Signed-off-by: Geoffrey Irving \n> ---\n>\n> Note: there are at least two \"holes\" in this code. First, it is impossible\n> to verify the validity of the entries (this is impossible to fix). Second,\n> it is possible to write a malicious patch-id-cache file that causes git-cherry\n> to go into an infinite loop. Fixing the loop requires either traversing every\n> entry on load (bad) or adding a second loop termination condition to\n> find_helper. Since looping forever is better than returning incorrect\n> results, I figured fixing the weaker hole would just result in a false sense\n> of security.\n\nOops: avoiding the infinite loop only requires reading expected O(1)\nentries on load, so I can fix that if you like. It would only be all\nof them if it actually did detect the infinite loop.\n\nGeoffrey\n"},{"id":"82813","messageId":"alpine.DEB.1.00.0807101526380.18205@racer","threadId":"14364","inReplyTo":"7f9d599f0807100709u778f0ab1y28776d7efb831b61@mail.gmail.com","subject":"Re: [PATCH] cherry: cache patch-ids to avoid repeating work","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2008-07-10T14:28:31Z","receivedAt":"2008-07-10T14:28:31Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Thu, 10 Jul 2008, Geoffrey Irving wrote:\n\n> On Wed, Jul 9, 2008 at 8:34 PM, Geoffrey Irving wrote:\n>\n> > Note: there are at least two \"holes\" in this code. First, it is \n> > impossible to verify the validity of the entries (this is impossible \n> > to fix). Second, it is possible to write a malicious patch-id-cache \n> > file that causes git-cherry to go into an infinite loop. Fixing the \n> > loop requires either traversing every entry on load (bad) or adding a \n> > second loop termination condition to find_helper. Since looping \n> > forever is better than returning incorrect results, I figured fixing \n> > the weaker hole would just result in a false sense of security.\n> \n> Oops: avoiding the infinite loop only requires reading expected O(1) \n> entries on load, so I can fix that if you like. It would only be all of \n> them if it actually did detect the infinite loop.\n\nI have to admit that you lost me there. AFAIR the patch-id cache is a \nsimple commit->patch_id store, right? Then there should be no way to get \nan infinite loop.\n\nBesides, this is a purely local cache, no? Never to be transmitted... So \nnot much chance of a malicious attack, except if you allow write access to \nyour local repository, in which case you are endangered no matter what.\n\nCiao,\nDscho\n"},{"id":"82815","messageId":"7f9d599f0807100733s4435a9bga89749f2f6e10cf@mail.gmail.com","threadId":"14364","inReplyTo":"alpine.DEB.1.00.0807101526380.18205@racer","subject":"Re: [PATCH] cherry: cache patch-ids to avoid repeating work","fromName":"Geoffrey Irving","fromEmail":"irving@naml.us","sentAt":"2008-07-10T14:33:55Z","receivedAt":"2008-07-10T14:33:55Z","isPatch":true,"sender":{"key":"irving@naml.us","avatar":"https://gravatar.com/avatar/52d7452fcd134aac0fa12f57a3bb7ef5f3f7e73ca0ab36736d06c6a6132de718?d=mp&s=160"},"body":"On Thu, Jul 10, 2008 at 7:28 AM, Johannes Schindelin\n wrote:\n> Hi,\n>\n> On Thu, 10 Jul 2008, Geoffrey Irving wrote:\n>\n>> On Wed, Jul 9, 2008 at 8:34 PM, Geoffrey Irving wrote:\n>>\n>> > Note: there are at least two \"holes\" in this code. First, it is\n>> > impossible to verify the validity of the entries (this is impossible\n>> > to fix). Second, it is possible to write a malicious patch-id-cache\n>> > file that causes git-cherry to go into an infinite loop. Fixing the\n>> > loop requires either traversing every entry on load (bad) or adding a\n>> > second loop termination condition to find_helper. Since looping\n>> > forever is better than returning incorrect results, I figured fixing\n>> > the weaker hole would just result in a false sense of security.\n>>\n>> Oops: avoiding the infinite loop only requires reading expected O(1)\n>> entries on load, so I can fix that if you like. It would only be all of\n>> them if it actually did detect the infinite loop.\n>\n> I have to admit that you lost me there. AFAIR the patch-id cache is a\n> simple commit->patch_id store, right? Then there should be no way to get\n> an infinite loop.\n\nIf every entry is nonnull, find_helper loops forever.\n\n> Besides, this is a purely local cache, no? Never to be transmitted... So\n> not much chance of a malicious attack, except if you allow write access to\n> your local repository, in which case you are endangered no matter what.\n\nYep, that's why it's only a hole in quotes, and why I didn't fix it.\n\nGeoffrey\n"},{"id":"82825","messageId":"alpine.DEB.1.00.0807101655440.18205@racer","threadId":"14364","inReplyTo":"7f9d599f0807100733s4435a9bga89749f2f6e10cf@mail.gmail.com","subject":"Re: [PATCH] cherry: cache patch-ids to avoid repeating work","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2008-07-10T15:56:32Z","receivedAt":"2008-07-10T15:56:32Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Thu, 10 Jul 2008, Geoffrey Irving wrote:\n\n> On Thu, Jul 10, 2008 at 7:28 AM, Johannes Schindelin\n> wrote:\n>\n> > On Thu, 10 Jul 2008, Geoffrey Irving wrote:\n> >\n> >> On Wed, Jul 9, 2008 at 8:34 PM, Geoffrey Irving wrote:\n> >>\n> >> > Note: there are at least two \"holes\" in this code. First, it is \n> >> > impossible to verify the validity of the entries (this is \n> >> > impossible to fix). Second, it is possible to write a malicious \n> >> > patch-id-cache file that causes git-cherry to go into an infinite \n> >> > loop. Fixing the loop requires either traversing every entry on \n> >> > load (bad) or adding a second loop termination condition to \n> >> > find_helper. Since looping forever is better than returning \n> >> > incorrect results, I figured fixing the weaker hole would just \n> >> > result in a false sense of security.\n> >>\n> >> Oops: avoiding the infinite loop only requires reading expected O(1) \n> >> entries on load, so I can fix that if you like. It would only be all \n> >> of them if it actually did detect the infinite loop.\n> >\n> > I have to admit that you lost me there. AFAIR the patch-id cache is a \n> > simple commit->patch_id store, right? Then there should be no way to \n> > get an infinite loop.\n> \n> If every entry is nonnull, find_helper loops forever.\n\nAh, that is because you did not use that part of my implementation. My \nhash did not wrap.\n\n> > Besides, this is a purely local cache, no? Never to be transmitted... \n> > So not much chance of a malicious attack, except if you allow write \n> > access to your local repository, in which case you are endangered no \n> > matter what.\n> \n> Yep, that's why it's only a hole in quotes, and why I didn't fix it.\n\nThen it is not a hole.\n\nCiao,\nDscho\n"},{"id":"82924","messageId":"7v3amglxmb.fsf@gitster.siamese.dyndns.org","threadId":"14364","inReplyTo":"7f9d599f0807100733s4435a9bga89749f2f6e10cf@mail.gmail.com","subject":"Re: [PATCH] cherry: cache patch-ids to avoid repeating work","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2008-07-11T06:54:04Z","receivedAt":"2008-07-11T06:54:04Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Geoffrey Irving\" writes:\n\n>>> Oops: avoiding the infinite loop only requires reading expected O(1)\n>>> entries on load, so I can fix that if you like. It would only be all of\n>>> them if it actually did detect the infinite loop.\n>>\n>> I have to admit that you lost me there. AFAIR the patch-id cache is a\n>> simple commit->patch_id store, right? Then there should be no way to get\n>> an infinite loop.\n>\n> If every entry is nonnull, find_helper loops forever.\n\nIsn't it sufficient to make this part check the condition as well?\n\n+\tif (cache->count >= cache->size)\n+\t{\n+\t\twarning(\"%s is corrupt: count %\"PRIu32\" >= size %\"PRIu32,\n+\t\t\tfilename, cache->count, cache->size);\n+\t\tgoto empty;\n+\t}\n\nAt runtime you keep the invariants that hashtable always has at most 3/4\nfull and whoever wrote the file you are reading must have honored that as\nwell, or there is something fishy going on.\n\n>> Besides, this is a purely local cache, no? Never to be transmitted... So\n>> not much chance of a malicious attack, except if you allow write access to\n>> your local repository, in which case you are endangered no matter what.\n>\n> Yep, that's why it's only a hole in quotes, and why I didn't fix it.\n\nYou might want to protect yourself against file corruption, though.\nChecksumming the whole file and checking it at opening defeats the point\nof mmap'ed access, but at least the header may want to be checksummed?\n"},{"id":"82963","messageId":"7f9d599f0807110758y6c4ea7bepd726daf4fe5f074c@mail.gmail.com","threadId":"14364","inReplyTo":"7v3amglxmb.fsf@gitster.siamese.dyndns.org","subject":"Re: [PATCH] cherry: cache patch-ids to avoid repeating work","fromName":"Geoffrey Irving","fromEmail":"irving@naml.us","sentAt":"2008-07-11T14:58:20Z","receivedAt":"2008-07-11T14:58:20Z","isPatch":true,"sender":{"key":"irving@naml.us","avatar":"https://gravatar.com/avatar/52d7452fcd134aac0fa12f57a3bb7ef5f3f7e73ca0ab36736d06c6a6132de718?d=mp&s=160"},"body":"On Thu, Jul 10, 2008 at 11:54 PM, Junio C Hamano wrote:\n> \"Geoffrey Irving\" writes:\n>\n>>>> Oops: avoiding the infinite loop only requires reading expected O(1)\n>>>> entries on load, so I can fix that if you like. It would only be all of\n>>>> them if it actually did detect the infinite loop.\n>>>\n>>> I have to admit that you lost me there. AFAIR the patch-id cache is a\n>>> simple commit->patch_id store, right? Then there should be no way to get\n>>> an infinite loop.\n>>\n>> If every entry is nonnull, find_helper loops forever.\n>\n> Isn't it sufficient to make this part check the condition as well?\n>\n> + if (cache->count >= cache->size)\n> + {\n> + warning(\"%s is corrupt: count %\"PRIu32\" >= size %\"PRIu32,\n> + filename, cache->count, cache->size);\n> + goto empty;\n> + }\n>\n> At runtime you keep the invariants that hashtable always has at most 3/4\n> full and whoever wrote the file you are reading must have honored that as\n> well, or there is something fishy going on.\n\nGood point. There's no reason not to check the 3/4 condition. It\nisn't sufficient to avoid the infinite loop, though, since we don't\nverify that count is accurate.\n\nAnother route would to eliminate the count field entirely, and replace\nthe count >= size/4*3 check with a statistical one based on the\nentries seen so far. The main advantage of that would be to make\nincremental writes simpler by avoiding the need to update the header.\nThe disadvantage is that there would be a small chance that the map\nwould grow in size despite being almost empty. Thoughts on whether we\nshould do that?\n\n>>> Besides, this is a purely local cache, no? Never to be transmitted... So\n>>> not much chance of a malicious attack, except if you allow write access to\n>>> your local repository, in which case you are endangered no matter what.\n>>\n>> Yep, that's why it's only a hole in quotes, and why I didn't fix it.\n>\n> You might want to protect yourself against file corruption, though.\n> Checksumming the whole file and checking it at opening defeats the point\n> of mmap'ed access, but at least the header may want to be checksummed?\n\nOkay. I imagine I should use sha1 as the sum?\n\nGeoffrey\n"},{"id":"82966","messageId":"alpine.DEB.1.00.0807111635400.8950@racer","threadId":"14364","inReplyTo":"7f9d599f0807110758y6c4ea7bepd726daf4fe5f074c@mail.gmail.com","subject":"Re: [PATCH] cherry: cache patch-ids to avoid repeating work","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2008-07-11T15:36:10Z","receivedAt":"2008-07-11T15:36:10Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Fri, 11 Jul 2008, Geoffrey Irving wrote:\n\n> On Thu, Jul 10, 2008 at 11:54 PM, Junio C Hamano wrote:\n> > \"Geoffrey Irving\" writes:\n> >\n> >>>> Oops: avoiding the infinite loop only requires reading expected O(1)\n> >>>> entries on load, so I can fix that if you like. It would only be all of\n> >>>> them if it actually did detect the infinite loop.\n> >>>\n> >>> I have to admit that you lost me there. AFAIR the patch-id cache is a\n> >>> simple commit->patch_id store, right? Then there should be no way to get\n> >>> an infinite loop.\n> >>\n> >> If every entry is nonnull, find_helper loops forever.\n> >\n> > Isn't it sufficient to make this part check the condition as well?\n> >\n> > + if (cache->count >= cache->size)\n> > + {\n> > + warning(\"%s is corrupt: count %\"PRIu32\" >= size %\"PRIu32,\n> > + filename, cache->count, cache->size);\n> > + goto empty;\n> > + }\n> >\n> > At runtime you keep the invariants that hashtable always has at most 3/4\n> > full and whoever wrote the file you are reading must have honored that as\n> > well, or there is something fishy going on.\n> \n> Good point. There's no reason not to check the 3/4 condition. It isn't \n> sufficient to avoid the infinite loop, though, since we don't verify \n> that count is accurate.\n\nWhy so complicated? I mean, you can count in that \"infinite\" loop \nyourself, no?\n\nCiao,\nDscho\n"},{"id":"82967","messageId":"7f9d599f0807110841r329dfb95g786a576bd981dd1b@mail.gmail.com","threadId":"14364","inReplyTo":"alpine.DEB.1.00.0807111635400.8950@racer","subject":"Re: [PATCH] cherry: cache patch-ids to avoid repeating work","fromName":"Geoffrey Irving","fromEmail":"irving@naml.us","sentAt":"2008-07-11T15:41:36Z","receivedAt":"2008-07-11T15:41:36Z","isPatch":true,"sender":{"key":"irving@naml.us","avatar":"https://gravatar.com/avatar/52d7452fcd134aac0fa12f57a3bb7ef5f3f7e73ca0ab36736d06c6a6132de718?d=mp&s=160"},"body":"On Fri, Jul 11, 2008 at 8:36 AM, Johannes Schindelin\n wrote:\n> Hi,\n>\n> On Fri, 11 Jul 2008, Geoffrey Irving wrote:\n>\n>> On Thu, Jul 10, 2008 at 11:54 PM, Junio C Hamano wrote:\n>> > \"Geoffrey Irving\" writes:\n>> >\n>> >>>> Oops: avoiding the infinite loop only requires reading expected O(1)\n>> >>>> entries on load, so I can fix that if you like. It would only be all of\n>> >>>> them if it actually did detect the infinite loop.\n>> >>>\n>> >>> I have to admit that you lost me there. AFAIR the patch-id cache is a\n>> >>> simple commit->patch_id store, right? Then there should be no way to get\n>> >>> an infinite loop.\n>> >>\n>> >> If every entry is nonnull, find_helper loops forever.\n>> >\n>> > Isn't it sufficient to make this part check the condition as well?\n>> >\n>> > + if (cache->count >= cache->size)\n>> > + {\n>> > + warning(\"%s is corrupt: count %\"PRIu32\" >= size %\"PRIu32,\n>> > + filename, cache->count, cache->size);\n>> > + goto empty;\n>> > + }\n>> >\n>> > At runtime you keep the invariants that hashtable always has at most 3/4\n>> > full and whoever wrote the file you are reading must have honored that as\n>> > well, or there is something fishy going on.\n>>\n>> Good point. There's no reason not to check the 3/4 condition. It isn't\n>> sufficient to avoid the infinite loop, though, since we don't verify\n>> that count is accurate.\n>\n> Why so complicated? I mean, you can count in that \"infinite\" loop\n> yourself, no?\n\nYeah, I was just trying to avoid the extra termination condition,\nbecause I don't think it adds any real safety.\n\nGeoffrey\n"},{"id":"82969","messageId":"alpine.DEB.1.00.0807111647080.8950@racer","threadId":"14364","inReplyTo":"7f9d599f0807110841r329dfb95g786a576bd981dd1b@mail.gmail.com","subject":"Re: [PATCH] cherry: cache patch-ids to avoid repeating work","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2008-07-11T15:48:27Z","receivedAt":"2008-07-11T15:48:27Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Fri, 11 Jul 2008, Geoffrey Irving wrote:\n\n> On Fri, Jul 11, 2008 at 8:36 AM, Johannes Schindelin\n> wrote:\n>\n> > Why so complicated? I mean, you can count in that \"infinite\" loop \n> > yourself, no?\n> \n> Yeah, I was just trying to avoid the extra termination condition, \n> because I don't think it adds any real safety.\n\nSorry. You absolutely lost me. While doing the loop over the entries, \ntrying to find an entry, adding a counter, and exiting when the counter \nreaches the total number of slots does not add any real safety?\n\nPuzzled,\nDscho\n"},{"id":"83121","messageId":"7f9d599f0807122014y5190463j62d106a01bf31c86@mail.gmail.com","threadId":"14364","inReplyTo":"7vej60jln6.fsf@gitster.siamese.dyndns.org","subject":"Re: [PATCH] cherry: cache patch-ids to avoid repeating work","fromName":"Geoffrey Irving","fromEmail":"irving@naml.us","sentAt":"2008-07-13T03:14:51Z","receivedAt":"2008-07-13T03:14:51Z","isPatch":true,"sender":{"key":"irving@naml.us","avatar":"https://gravatar.com/avatar/52d7452fcd134aac0fa12f57a3bb7ef5f3f7e73ca0ab36736d06c6a6132de718?d=mp&s=160"},"body":"Add cached-sha-map.[ch] implementing a persistent hash map from sha1 to\nsha1. The map is read with mmap, and completely rewritten if any entries\nchange. It would be good to add incremental update to handle the usual case\nwhere only a few entries change.\n\nThis structure is used by patch-ids.c to cache the mapping from commit to\npatch-id into $GIT_DIR/patch-id-cache. In the one case I've tested so far,\nthis speeds up the second invocation of git-cherry by two orders of\nmagnitude. The caching can be disabled by setting cherry.cachepatchids to\nfalse.\n\nOriginal code cannibalized from Johannes Schindelin's notes-index structure.\n\nSigned-off-by: Geoffrey Irving \n---\n\nHere's an updated version that avoids infinite loops and adds a sha1\nchecksum of the header. It is still vastly more likely that this code\nwill return incorrect results due to disk corruption than that the old\nversion would infinite loop. If we want to be even more paranoid, we\ncould add a checksum for every 511 entries, but I'm hoping that isn't\nrequired. :)\n\nYour version of the infinite loop avoidance didn't quite work, since\nI'm already using every 32 bit return value in find_helper.\n\nI also fixed the 4/3 check to not overflow.\n\n Documentation/config.txt | 5 +\n Makefile | 2 +\n builtin-log.c | 12 ++\n cached-sha1-map.c | 293 ++++++++++++++++++++++++++++++++++++++++++++++\n cached-sha1-map.h | 45 +++++++\n patch-ids.c | 26 ++++-\n patch-ids.h | 2 +\n 7 files changed, 384 insertions(+), 1 deletions(-)\n create mode 100644 cached-sha1-map.c\n create mode 100644 cached-sha1-map.h\n\ndiff --git a/Documentation/config.txt b/Documentation/config.txt\nindex 838794d..02b8113 100644\n--- a/Documentation/config.txt\n+++ b/Documentation/config.txt\n@@ -468,6 +468,11 @@ browser..path::\n \tbrowse HTML help (see '-w' option in linkgit:git-help[1]) or a\n \tworking repository in gitweb (see linkgit:git-instaweb[1]).\n\n+cherry.cachepatchids::\n+\tIf true, linkgit:git-cherry will store a cache of computed patch-ids\n+\tin $GIT_DIR/patch-id-cache in order to make repeated invocations faster.\n+\tDefaults to true.\n+\n clean.requireForce::\n \tA boolean to make git-clean do nothing unless given -f\n \tor -n. Defaults to true.\ndiff --git a/Makefile b/Makefile\nindex 4796565..f7360e1 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -356,6 +356,7 @@ LIB_H += pack-refs.h\n LIB_H += pack-revindex.h\n LIB_H += parse-options.h\n LIB_H += patch-ids.h\n+LIB_H += cached-sha1-map.h\n LIB_H += path-list.h\n LIB_H += pkt-line.h\n LIB_H += progress.h\n@@ -436,6 +437,7 @@ LIB_OBJS += pager.o\n LIB_OBJS += parse-options.o\n LIB_OBJS += patch-delta.o\n LIB_OBJS += patch-ids.o\n+LIB_OBJS += cached-sha1-map.o\n LIB_OBJS += path-list.o\n LIB_OBJS += path.o\n LIB_OBJS += pkt-line.o\ndiff --git a/builtin-log.c b/builtin-log.c\nindex 430d876..fbfefbd 100644\n--- a/builtin-log.c\n+++ b/builtin-log.c\n@@ -1081,6 +1081,16 @@ static int add_pending_commit(const char *arg,\nstruct rev_info *revs, int flags)\n \treturn -1;\n }\n\n+static int git_cherry_config(const char *var, const char *value, void *cb)\n+{\n+\tif (!strcmp(var, \"cherry.cachepatchids\")) {\n+\t\tcache_patch_ids = git_config_bool(var, value);\n+\t\treturn 0;\n+\t}\n+\n+\treturn 0;\n+}\n+\n static const char cherry_usage[] =\n \"git-cherry [-v] [] []\";\n int cmd_cherry(int argc, const char **argv, const char *prefix)\n@@ -1094,6 +1104,8 @@ int cmd_cherry(int argc, const char **argv,\nconst char *prefix)\n \tconst char *limit = NULL;\n \tint verbose = 0;\n\n+\tgit_config(git_cherry_config, NULL);\n+\n \tif (argc > 1 && !strcmp(argv[1], \"-v\")) {\n \t\tverbose = 1;\n \t\targc--;\ndiff --git a/cached-sha1-map.c b/cached-sha1-map.c\nnew file mode 100644\nindex 0000000..9cf7252\n--- /dev/null\n+++ b/cached-sha1-map.c\n@@ -0,0 +1,293 @@\n+#include \"cached-sha1-map.h\"\n+\n+union cached_sha1_map_header {\n+\tstruct {\n+\t\tchar signature[4]; /* CS1M */\n+\t\tuint32_t version;\n+\t\tuint32_t count;\n+\t\tuint32_t size;\n+\t\tuint32_t pad; /* pad to 20 bytes */\n+\t} u;\n+\t/* pad header out to 40 bytes. As a consistency\n+\t * check, pad.value stores the sha1 of pad.key. */\n+\tstruct cached_sha1_entry pad;\n+};\n+\n+static const char *signature = \"CS1M\";\n+static const uint32_t version = 1;\n+\n+static int init_empty_map(struct cached_sha1_map *cache, uint32_t size)\n+{\n+\tcache->count = 0;\n+\tcache->size = size;\n+\tcache->initialized = 1;\n+\tcache->mmapped = 0;\n+\tcache->dirty = 1;\n+\n+\tcache->entries = calloc(size, sizeof(struct cached_sha1_entry));\n+\tif (!cache->entries) {\n+\t\twarning(\"failed to allocate empty map of size %\"PRIu32\" for %s\",\n+\t\t\tsize, git_path(cache->filename));\n+\t\tcache->size = 0;\n+\t\tcache->dirty = 0;\n+\t\treturn -1;\n+\t}\n+\treturn 0;\n+}\n+\n+static int grow_map(struct cached_sha1_map *cache)\n+{\n+\tstruct cached_sha1_map new_cache;\n+\tuint32_t i;\n+\n+\tif (cache->size * 2 == 0) {\n+\t\twarning(\"%s overflowed, so resetting to empty\",\n+\t\t\tgit_path(cache->filename));\n+\t\treturn init_empty_map(cache, 64);\n+\t}\n+\n+\t/* allocate cache with twice the size */\n+\tnew_cache.filename = cache->filename;\n+\tif (init_empty_map(&new_cache, cache->size * 2)) {\n+\t\twarning(\"failed to grow %s to size %\"PRIu32,\n+\t\t\tgit_path(cache->filename), cache->size * 2);\n+\t\treturn init_empty_map(cache, 64);\n+\t}\n+\n+\t/* reinsert all entries */\n+ \tfor (i = 0; i < cache->size; i++)\n+\t\tif (!is_null_sha1(cache->entries[i].key))\n+\t\t\tset_cached_sha1_entry(&new_cache,\n+\t\t\t\tcache->entries[i].key, cache->entries[i].value);\n+\t/* finish */\n+\tfree_cached_sha1_map(cache);\n+\t*cache = new_cache;\n+\treturn 0;\n+}\n+\n+/* Any errors that occur result in the cache being initialized to empty */\n+static int init_cached_sha1_map(struct cached_sha1_map *cache)\n+{\n+\tint fd;\n+\tunion cached_sha1_map_header header;\n+\tconst char *filename;\n+\tsize_t map_size;\n+\tSHA_CTX ctx;\n+\n+\tif (cache->initialized)\n+\t\treturn cache->size ? 0 : -1;\n+\n+\tfilename = git_path(cache->filename);\n+\tfd = open(filename, O_RDONLY);\n+\tif (fd < 0) {\n+\t\tif (errno != ENOENT)\n+\t\t\twarning(\"failed to read '%s': %s\", filename,\n+\t\t\t\tstrerror(errno));\n+\t\tgoto empty;\n+\t}\n+\n+\tif (read_in_full(fd, &header, sizeof(header)) != sizeof(header)) {\n+\t\twarning(\"cannot read %s header\", filename);\n+\t\tgoto empty;\n+\t}\n+\n+\tif (memcmp(header.u.signature, signature, 4)) {\n+\t\twarning(\"%s has invalid header\", filename);\n+\t\tgoto empty;\n+\t}\n+\n+\tif (ntohl(header.u.version) != version) {\n+\t\twarning(\"%s has unrecognized version %\"PRIu32, filename,\n+\t\t\tntohl(header.u.version));\n+\t\tgoto empty;\n+\t}\n+\n+\tcache->count = ntohl(header.u.count);\n+\tcache->size = ntohl(header.u.size);\n+\n+\tif (cache->size & (cache->size-1)) {\n+\t\twarning(\"%s is corrupt: size %\"PRIu32\" is not a power of two\",\n+\t\t\tfilename, cache->size);\n+\t\tgoto empty;\n+\t}\n+\n+\tif (cache->count >= cache->size) {\n+\t\twarning(\"%s is corrupt: count %\"PRIu32\" >= size %\"PRIu32,\n+\t\t\tfilename, cache->count, cache->size);\n+\t\tgoto empty;\n+\t}\n+\n+\tSHA1_Init(&ctx);\n+\tSHA1_Update(&ctx, header.pad.key, 20);\n+\tSHA1_Final(header.pad.key, &ctx); /* reuse pad.key to store its sha1 */\n+\tif (hashcmp(header.pad.key, header.pad.value)) {\n+\t\twarning(\"%s header has invalid sha1\", filename);\n+\t\tgoto empty;\n+\t}\n+\n+\tcache->dirty = 0;\n+\tcache->initialized = 1;\n+\tcache->mmapped = 1;\n+\n+\t/* mmap entire file so that file / memory blocks are aligned */\n+\tmap_size = sizeof(struct cached_sha1_entry) * (cache->size + 1);\n+\tcache->entries = mmap(NULL, map_size,\n+\t\tPROT_READ | PROT_WRITE, MAP_PRIVATE, fd, 0);\n+\tif (cache->entries == MAP_FAILED) {\n+\t\t/* this is just a cache, so don't free pack memory and retry */\n+\t\twarning(\"%s mmap failed: %s\", filename, strerror(errno));\n+\t\tgoto empty;\n+\t}\n+\tcache->entries += 1; /* skip header */\n+\treturn 0;\n+\n+empty:\n+\tif (fd >= 0)\n+\t\tclose(fd);\n+\treturn init_empty_map(cache, 64);\n+}\n+\n+int write_cached_sha1_map(struct cached_sha1_map *cache)\n+{\n+\tunion cached_sha1_map_header header;\n+\tstruct lock_file update_lock;\n+\tint fd;\n+\tsize_t map_size;\n+\tconst char *filename;\n+\tSHA_CTX ctx;\n+\n+\tif (!cache->initialized || !cache->dirty)\n+\t\treturn 0;\n+\n+\tfilename = git_path(cache->filename);\n+\tfd = hold_lock_file_for_update(&update_lock, filename, 0);\n+\n+\tif (fd < 0)\n+\t{\n+\t\twarning(\"could not construct %s\", filename);\n+\t\treturn -1;\n+\t}\n+\n+\t/* initialize header */\n+\tmemcpy(header.u.signature, signature, 4);\n+\theader.u.version = htonl(version);\n+\theader.u.count = htonl(cache->count);\n+\theader.u.size = htonl(cache->size);\n+\theader.u.pad = 0; /* make header deterministic */\n+\n+\t/* compute header sha1 */\n+\tSHA1_Init(&ctx);\n+\tSHA1_Update(&ctx, header.pad.key, 20);\n+\tSHA1_Final(header.pad.value, &ctx);\n+\n+\tmap_size = sizeof(struct cached_sha1_entry) * cache->size;\n+\tif (write_in_full(fd, &header, sizeof(header)) != sizeof(header)\n+\t\t|| write_in_full(fd, cache->entries, map_size) != map_size)\n+\t{\n+\t\twarning(\"could not write %s\", filename);\n+\t\treturn -1;\n+\t}\n+\n+\tif (commit_lock_file(&update_lock) < 0)\n+\t{\n+\t\twarning(\"could not write %s\", filename);\n+\t\treturn -1;\n+\t}\n+\n+\tcache->dirty = 0;\n+\treturn 0;\n+}\n+\n+void free_cached_sha1_map(struct cached_sha1_map *cache)\n+{\n+\tif (!cache->initialized)\n+\t\treturn;\n+\n+\tif (cache->mmapped)\n+\t\tmunmap(cache->entries - 1,\n+\t\t\tsizeof(struct cached_sha1_entry) * (cache->size + 1));\n+\telse\n+\t\tfree(cache->entries);\n+}\n+\n+/* The fact that size is a power of two means count-1 <= INT32_MAX, so it\n+ * is safe to return signed integers here. */\n+static int32_t get_hash_index(const unsigned char *sha1)\n+{\n+\t/* this is alignment safe since 40 is a multiple of 4 */\n+\treturn ntohl(*(uint32_t*)sha1);\n+}\n+\n+/*\n+ * Returns the index if the entry exists, and the complemented index of\n+ * the next free entry otherwise. If the hash is full, returns the\n+ * complement of a nonfree entry and sets count = size (this happens\n+ * only if the file is corrupt).\n+ */\n+static int32_t find_helper(struct cached_sha1_map *cache,\n+\tconst unsigned char *key)\n+{\n+\tint32_t i, mask, full;\n+\n+\tmask = cache->size - 1;\n+\ti = get_hash_index(key) & mask;\n+\tfull = (i-1) & mask;\n+\n+\tfor (; ; i = (i+1) & mask) {\n+\t\tif (!hashcmp(key, cache->entries[i].key))\n+\t\t\treturn i;\n+\t\telse if (is_null_sha1(cache->entries[i].key) || i == full)\n+\t\t\treturn ~i;\n+\t\tif (i == full) {\n+\t\t\tcache->count = cache->size; /* fix count */\n+\t\t\treturn ~1;\n+\t\t}\n+\t}\n+}\n+\n+int get_cached_sha1_entry(struct cached_sha1_map *cache,\n+\tconst unsigned char *key, unsigned char *value)\n+{\n+\tint32_t i;\n+\n+\tif (init_cached_sha1_map(cache))\n+\t\treturn -1;\n+\n+\ti = find_helper(cache, key);\n+\tif(i < 0)\n+\t\treturn -1;\n+\n+\t/* entry found, return value */\n+\thashcpy(value, cache->entries[i].value);\n+\treturn 0;\n+}\n+\n+int set_cached_sha1_entry(struct cached_sha1_map *cache,\n+\tconst unsigned char *key, const unsigned char *value)\n+{\n+\tint32_t i;\n+\tstruct cached_sha1_entry *entry;\n+\n+\tif (init_cached_sha1_map(cache))\n+\t\treturn -1;\n+\n+\ti = find_helper(cache, key);\n+\n+\tif (i < 0) { /* write new entry */\n+\t\tentry = cache->entries + ~i;\n+\t\thashcpy(entry->key, key);\n+\t\thashcpy(entry->value, value);\n+\t\tcache->count++;\n+\t\tcache->dirty = 1;\n+\t} else { /* overwrite existing entry */\n+\t\tentry = cache->entries + i;\n+\t\tif (hashcmp(value, entry->value)) {\n+\t\t\thashcpy(entry->value, value);\n+\t\t\tcache->dirty = 1;\n+\t\t}\n+\t}\n+\n+\tif (cache->count >= cache->size/4*3)\n+\t\treturn grow_map(cache);\n+\treturn 0;\n+}\ndiff --git a/cached-sha1-map.h b/cached-sha1-map.h\nnew file mode 100644\nindex 0000000..296c17c\n--- /dev/null\n+++ b/cached-sha1-map.h\n@@ -0,0 +1,45 @@\n+#ifndef CACHED_SHA1_MAP_H\n+#define CACHED_SHA1_MAP_H\n+\n+#include \"cache.h\"\n+\n+/*\n+ * A cached-sha1-map is a file storing a hash map from sha1 to sha1.\n+ *\n+ * The file is mmap'ed, updated in memory during operation, and flushed\n+ * back to disk when freed. Currently the entire file is rewritten for\n+ * any change. This could be a significant bottleneck for common uses,\n+ * so it would be good to fix this later if possible.\n+ *\n+ * The performance of a hash map depends highly on a good hashing\n+ * algorithm, to avoid collisions. Lucky us! SHA-1 is a pretty good\n+ * hashing algorithm.\n+ */\n+\n+struct cached_sha1_entry {\n+\tunsigned char key[20];\n+\tunsigned char value[20];\n+};\n+\n+struct cached_sha1_map {\n+\tconst char *filename; /* relative to GIT_DIR */\n+\n+\t/* rest is for internal use */\n+\tuint32_t count, size;\n+\tunsigned int initialized : 1;\n+\tunsigned int dirty : 1;\n+\tunsigned int mmapped : 1;\n+\tstruct cached_sha1_entry *entries; /* pointer to mmap'ed memory + 1 */\n+};\n+\n+extern int get_cached_sha1_entry(struct cached_sha1_map *cache,\n+\tconst unsigned char *key,unsigned char *value);\n+\n+extern int set_cached_sha1_entry(struct cached_sha1_map *cache,\n+\tconst unsigned char *key, const unsigned char *value);\n+\n+extern int write_cached_sha1_map(struct cached_sha1_map *cache);\n+\n+extern void free_cached_sha1_map(struct cached_sha1_map *cache);\n+\n+#endif\ndiff --git a/patch-ids.c b/patch-ids.c\nindex 3be5d31..663ffee 100644\n--- a/patch-ids.c\n+++ b/patch-ids.c\n@@ -2,17 +2,36 @@\n #include \"diff.h\"\n #include \"commit.h\"\n #include \"patch-ids.h\"\n+#include \"cached-sha1-map.h\"\n+\n+int cache_patch_ids = 1;\n+static struct cached_sha1_map patch_id_cache;\n\n static int commit_patch_id(struct commit *commit, struct diff_options *options,\n \t\t unsigned char *sha1)\n {\n+\tint ret;\n+\n+\t/* pull patch-id out of the cache if possible */\n+\tpatch_id_cache.filename = \"patch-id-cache\";\n+\tif (cache_patch_ids && !get_cached_sha1_entry(&patch_id_cache,\n+\t\t\tcommit->object.sha1, sha1))\n+\t\treturn 0;\n+\n \tif (commit->parents)\n \t\tdiff_tree_sha1(commit->parents->item->object.sha1,\n \t\t commit->object.sha1, \"\", options);\n \telse\n \t\tdiff_root_tree_sha1(commit->object.sha1, \"\", options);\n \tdiffcore_std(options);\n-\treturn diff_flush_patch_id(options, sha1);\n+\tret = diff_flush_patch_id(options, sha1);\n+\tif (ret)\n+\t\treturn ret;\n+\n+\t/* record commit, patch-id pair in cache */\n+\tif (cache_patch_ids)\n+\t\tset_cached_sha1_entry(&patch_id_cache, commit->object.sha1, sha1);\n+\treturn 0;\n }\n\n static uint32_t take2(const unsigned char *id)\n@@ -136,6 +155,11 @@ int free_patch_ids(struct patch_ids *ids)\n \t\tnext = patches->next;\n \t\tfree(patches);\n \t}\n+\n+\t/* write cached patch-ids and ignore any errors that arise\n+\t * (e.g. if the repository is write protected) */\n+\tif (cache_patch_ids)\n+\t\twrite_cached_sha1_map(&patch_id_cache);\n \treturn 0;\n }\n\ndiff --git a/patch-ids.h b/patch-ids.h\nindex c8c7ca1..c0ebdc1 100644\n--- a/patch-ids.h\n+++ b/patch-ids.h\n@@ -18,4 +18,6 @@ int free_patch_ids(struct patch_ids *);\n struct patch_id *add_commit_patch_id(struct commit *, struct patch_ids *);\n struct patch_id *has_commit_patch_id(struct commit *, struct patch_ids *);\n\n+extern int cache_patch_ids;\n+\n #endif /* PATCH_IDS_H */\n-- \n1.5.6.2.256.g33ad.dirty\n"},{"id":"83416","messageId":"7f9d599f0807150957o78d46204x280668c763fba2bf@mail.gmail.com","threadId":"14364","inReplyTo":"7f9d599f0807122014y5190463j62d106a01bf31c86@mail.gmail.com","subject":"[PATCH] cherry: cache patch-ids to avoid repeating work","fromName":"Geoffrey Irving","fromEmail":"irving@naml.us","sentAt":"2008-07-15T16:57:14Z","receivedAt":"2008-07-15T16:57:14Z","isPatch":true,"sender":{"key":"irving@naml.us","avatar":"https://gravatar.com/avatar/52d7452fcd134aac0fa12f57a3bb7ef5f3f7e73ca0ab36736d06c6a6132de718?d=mp&s=160"},"body":"Add cached-sha-map.[ch] implementing a persistent hash map from sha1 to\nsha1. The map is read with mmap, and completely rewritten if any entries\nchange. It would be good to add incremental update to handle the usual case\nwhere only a few entries change.\n\nThis structure is used by patch-ids.c to cache the mapping from commit to\npatch-id into $GIT_DIR/patch-id-cache. In the one case I've tested so far,\nthis speeds up the second invocation of git-cherry by two orders of\nmagnitude. The caching can be disabled by setting cherry.cachepatchids to\nfalse. Only patch-ids with default diff options are cached.\n\nOriginal code cannibalized from Johannes Schindelin's notes-index structure.\n\nSigned-off-by: Geoffrey Irving \n---\n\nHere's a version of the patch fixing the test breakage. Only\npatch-ids.c differs from the previous version.\n\n Documentation/config.txt | 5 +\n Makefile | 2 +\n builtin-log.c | 12 ++\n cached-sha1-map.c | 293 ++++++++++++++++++++++++++++++++++++++++++++++\n cached-sha1-map.h | 45 +++++++\n patch-ids.c | 40 ++++++-\n patch-ids.h | 2 +\n 7 files changed, 398 insertions(+), 1 deletions(-)\n create mode 100644 cached-sha1-map.c\n create mode 100644 cached-sha1-map.h\n\ndiff --git a/Documentation/config.txt b/Documentation/config.txt\nindex 838794d..02b8113 100644\n--- a/Documentation/config.txt\n+++ b/Documentation/config.txt\n@@ -468,6 +468,11 @@ browser..path::\n \tbrowse HTML help (see '-w' option in linkgit:git-help[1]) or a\n \tworking repository in gitweb (see linkgit:git-instaweb[1]).\n\n+cherry.cachepatchids::\n+\tIf true, linkgit:git-cherry will store a cache of computed patch-ids\n+\tin $GIT_DIR/patch-id-cache in order to make repeated invocations faster.\n+\tDefaults to true.\n+\n clean.requireForce::\n \tA boolean to make git-clean do nothing unless given -f\n \tor -n. Defaults to true.\ndiff --git a/Makefile b/Makefile\nindex 4796565..f7360e1 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -356,6 +356,7 @@ LIB_H += pack-refs.h\n LIB_H += pack-revindex.h\n LIB_H += parse-options.h\n LIB_H += patch-ids.h\n+LIB_H += cached-sha1-map.h\n LIB_H += path-list.h\n LIB_H += pkt-line.h\n LIB_H += progress.h\n@@ -436,6 +437,7 @@ LIB_OBJS += pager.o\n LIB_OBJS += parse-options.o\n LIB_OBJS += patch-delta.o\n LIB_OBJS += patch-ids.o\n+LIB_OBJS += cached-sha1-map.o\n LIB_OBJS += path-list.o\n LIB_OBJS += path.o\n LIB_OBJS += pkt-line.o\ndiff --git a/builtin-log.c b/builtin-log.c\nindex 430d876..fbfefbd 100644\n--- a/builtin-log.c\n+++ b/builtin-log.c\n@@ -1081,6 +1081,16 @@ static int add_pending_commit(const char *arg,\nstruct rev_info *revs, int flags)\n \treturn -1;\n }\n\n+static int git_cherry_config(const char *var, const char *value, void *cb)\n+{\n+\tif (!strcmp(var, \"cherry.cachepatchids\")) {\n+\t\tcache_patch_ids = git_config_bool(var, value);\n+\t\treturn 0;\n+\t}\n+\n+\treturn 0;\n+}\n+\n static const char cherry_usage[] =\n \"git-cherry [-v] [] []\";\n int cmd_cherry(int argc, const char **argv, const char *prefix)\n@@ -1094,6 +1104,8 @@ int cmd_cherry(int argc, const char **argv,\nconst char *prefix)\n \tconst char *limit = NULL;\n \tint verbose = 0;\n\n+\tgit_config(git_cherry_config, NULL);\n+\n \tif (argc > 1 && !strcmp(argv[1], \"-v\")) {\n \t\tverbose = 1;\n \t\targc--;\ndiff --git a/cached-sha1-map.c b/cached-sha1-map.c\nnew file mode 100644\nindex 0000000..9cf7252\n--- /dev/null\n+++ b/cached-sha1-map.c\n@@ -0,0 +1,293 @@\n+#include \"cached-sha1-map.h\"\n+\n+union cached_sha1_map_header {\n+\tstruct {\n+\t\tchar signature[4]; /* CS1M */\n+\t\tuint32_t version;\n+\t\tuint32_t count;\n+\t\tuint32_t size;\n+\t\tuint32_t pad; /* pad to 20 bytes */\n+\t} u;\n+\t/* pad header out to 40 bytes. As a consistency\n+\t * check, pad.value stores the sha1 of pad.key. */\n+\tstruct cached_sha1_entry pad;\n+};\n+\n+static const char *signature = \"CS1M\";\n+static const uint32_t version = 1;\n+\n+static int init_empty_map(struct cached_sha1_map *cache, uint32_t size)\n+{\n+\tcache->count = 0;\n+\tcache->size = size;\n+\tcache->initialized = 1;\n+\tcache->mmapped = 0;\n+\tcache->dirty = 1;\n+\n+\tcache->entries = calloc(size, sizeof(struct cached_sha1_entry));\n+\tif (!cache->entries) {\n+\t\twarning(\"failed to allocate empty map of size %\"PRIu32\" for %s\",\n+\t\t\tsize, git_path(cache->filename));\n+\t\tcache->size = 0;\n+\t\tcache->dirty = 0;\n+\t\treturn -1;\n+\t}\n+\treturn 0;\n+}\n+\n+static int grow_map(struct cached_sha1_map *cache)\n+{\n+\tstruct cached_sha1_map new_cache;\n+\tuint32_t i;\n+\n+\tif (cache->size * 2 == 0) {\n+\t\twarning(\"%s overflowed, so resetting to empty\",\n+\t\t\tgit_path(cache->filename));\n+\t\treturn init_empty_map(cache, 64);\n+\t}\n+\n+\t/* allocate cache with twice the size */\n+\tnew_cache.filename = cache->filename;\n+\tif (init_empty_map(&new_cache, cache->size * 2)) {\n+\t\twarning(\"failed to grow %s to size %\"PRIu32,\n+\t\t\tgit_path(cache->filename), cache->size * 2);\n+\t\treturn init_empty_map(cache, 64);\n+\t}\n+\n+\t/* reinsert all entries */\n+ \tfor (i = 0; i < cache->size; i++)\n+\t\tif (!is_null_sha1(cache->entries[i].key))\n+\t\t\tset_cached_sha1_entry(&new_cache,\n+\t\t\t\tcache->entries[i].key, cache->entries[i].value);\n+\t/* finish */\n+\tfree_cached_sha1_map(cache);\n+\t*cache = new_cache;\n+\treturn 0;\n+}\n+\n+/* Any errors that occur result in the cache being initialized to empty */\n+static int init_cached_sha1_map(struct cached_sha1_map *cache)\n+{\n+\tint fd;\n+\tunion cached_sha1_map_header header;\n+\tconst char *filename;\n+\tsize_t map_size;\n+\tSHA_CTX ctx;\n+\n+\tif (cache->initialized)\n+\t\treturn cache->size ? 0 : -1;\n+\n+\tfilename = git_path(cache->filename);\n+\tfd = open(filename, O_RDONLY);\n+\tif (fd < 0) {\n+\t\tif (errno != ENOENT)\n+\t\t\twarning(\"failed to read '%s': %s\", filename,\n+\t\t\t\tstrerror(errno));\n+\t\tgoto empty;\n+\t}\n+\n+\tif (read_in_full(fd, &header, sizeof(header)) != sizeof(header)) {\n+\t\twarning(\"cannot read %s header\", filename);\n+\t\tgoto empty;\n+\t}\n+\n+\tif (memcmp(header.u.signature, signature, 4)) {\n+\t\twarning(\"%s has invalid header\", filename);\n+\t\tgoto empty;\n+\t}\n+\n+\tif (ntohl(header.u.version) != version) {\n+\t\twarning(\"%s has unrecognized version %\"PRIu32, filename,\n+\t\t\tntohl(header.u.version));\n+\t\tgoto empty;\n+\t}\n+\n+\tcache->count = ntohl(header.u.count);\n+\tcache->size = ntohl(header.u.size);\n+\n+\tif (cache->size & (cache->size-1)) {\n+\t\twarning(\"%s is corrupt: size %\"PRIu32\" is not a power of two\",\n+\t\t\tfilename, cache->size);\n+\t\tgoto empty;\n+\t}\n+\n+\tif (cache->count >= cache->size) {\n+\t\twarning(\"%s is corrupt: count %\"PRIu32\" >= size %\"PRIu32,\n+\t\t\tfilename, cache->count, cache->size);\n+\t\tgoto empty;\n+\t}\n+\n+\tSHA1_Init(&ctx);\n+\tSHA1_Update(&ctx, header.pad.key, 20);\n+\tSHA1_Final(header.pad.key, &ctx); /* reuse pad.key to store its sha1 */\n+\tif (hashcmp(header.pad.key, header.pad.value)) {\n+\t\twarning(\"%s header has invalid sha1\", filename);\n+\t\tgoto empty;\n+\t}\n+\n+\tcache->dirty = 0;\n+\tcache->initialized = 1;\n+\tcache->mmapped = 1;\n+\n+\t/* mmap entire file so that file / memory blocks are aligned */\n+\tmap_size = sizeof(struct cached_sha1_entry) * (cache->size + 1);\n+\tcache->entries = mmap(NULL, map_size,\n+\t\tPROT_READ | PROT_WRITE, MAP_PRIVATE, fd, 0);\n+\tif (cache->entries == MAP_FAILED) {\n+\t\t/* this is just a cache, so don't free pack memory and retry */\n+\t\twarning(\"%s mmap failed: %s\", filename, strerror(errno));\n+\t\tgoto empty;\n+\t}\n+\tcache->entries += 1; /* skip header */\n+\treturn 0;\n+\n+empty:\n+\tif (fd >= 0)\n+\t\tclose(fd);\n+\treturn init_empty_map(cache, 64);\n+}\n+\n+int write_cached_sha1_map(struct cached_sha1_map *cache)\n+{\n+\tunion cached_sha1_map_header header;\n+\tstruct lock_file update_lock;\n+\tint fd;\n+\tsize_t map_size;\n+\tconst char *filename;\n+\tSHA_CTX ctx;\n+\n+\tif (!cache->initialized || !cache->dirty)\n+\t\treturn 0;\n+\n+\tfilename = git_path(cache->filename);\n+\tfd = hold_lock_file_for_update(&update_lock, filename, 0);\n+\n+\tif (fd < 0)\n+\t{\n+\t\twarning(\"could not construct %s\", filename);\n+\t\treturn -1;\n+\t}\n+\n+\t/* initialize header */\n+\tmemcpy(header.u.signature, signature, 4);\n+\theader.u.version = htonl(version);\n+\theader.u.count = htonl(cache->count);\n+\theader.u.size = htonl(cache->size);\n+\theader.u.pad = 0; /* make header deterministic */\n+\n+\t/* compute header sha1 */\n+\tSHA1_Init(&ctx);\n+\tSHA1_Update(&ctx, header.pad.key, 20);\n+\tSHA1_Final(header.pad.value, &ctx);\n+\n+\tmap_size = sizeof(struct cached_sha1_entry) * cache->size;\n+\tif (write_in_full(fd, &header, sizeof(header)) != sizeof(header)\n+\t\t|| write_in_full(fd, cache->entries, map_size) != map_size)\n+\t{\n+\t\twarning(\"could not write %s\", filename);\n+\t\treturn -1;\n+\t}\n+\n+\tif (commit_lock_file(&update_lock) < 0)\n+\t{\n+\t\twarning(\"could not write %s\", filename);\n+\t\treturn -1;\n+\t}\n+\n+\tcache->dirty = 0;\n+\treturn 0;\n+}\n+\n+void free_cached_sha1_map(struct cached_sha1_map *cache)\n+{\n+\tif (!cache->initialized)\n+\t\treturn;\n+\n+\tif (cache->mmapped)\n+\t\tmunmap(cache->entries - 1,\n+\t\t\tsizeof(struct cached_sha1_entry) * (cache->size + 1));\n+\telse\n+\t\tfree(cache->entries);\n+}\n+\n+/* The fact that size is a power of two means count-1 <= INT32_MAX, so it\n+ * is safe to return signed integers here. */\n+static int32_t get_hash_index(const unsigned char *sha1)\n+{\n+\t/* this is alignment safe since 40 is a multiple of 4 */\n+\treturn ntohl(*(uint32_t*)sha1);\n+}\n+\n+/*\n+ * Returns the index if the entry exists, and the complemented index of\n+ * the next free entry otherwise. If the hash is full, returns the\n+ * complement of a nonfree entry and sets count = size (this happens\n+ * only if the file is corrupt).\n+ */\n+static int32_t find_helper(struct cached_sha1_map *cache,\n+\tconst unsigned char *key)\n+{\n+\tint32_t i, mask, full;\n+\n+\tmask = cache->size - 1;\n+\ti = get_hash_index(key) & mask;\n+\tfull = (i-1) & mask;\n+\n+\tfor (; ; i = (i+1) & mask) {\n+\t\tif (!hashcmp(key, cache->entries[i].key))\n+\t\t\treturn i;\n+\t\telse if (is_null_sha1(cache->entries[i].key) || i == full)\n+\t\t\treturn ~i;\n+\t\tif (i == full) {\n+\t\t\tcache->count = cache->size; /* fix count */\n+\t\t\treturn ~1;\n+\t\t}\n+\t}\n+}\n+\n+int get_cached_sha1_entry(struct cached_sha1_map *cache,\n+\tconst unsigned char *key, unsigned char *value)\n+{\n+\tint32_t i;\n+\n+\tif (init_cached_sha1_map(cache))\n+\t\treturn -1;\n+\n+\ti = find_helper(cache, key);\n+\tif(i < 0)\n+\t\treturn -1;\n+\n+\t/* entry found, return value */\n+\thashcpy(value, cache->entries[i].value);\n+\treturn 0;\n+}\n+\n+int set_cached_sha1_entry(struct cached_sha1_map *cache,\n+\tconst unsigned char *key, const unsigned char *value)\n+{\n+\tint32_t i;\n+\tstruct cached_sha1_entry *entry;\n+\n+\tif (init_cached_sha1_map(cache))\n+\t\treturn -1;\n+\n+\ti = find_helper(cache, key);\n+\n+\tif (i < 0) { /* write new entry */\n+\t\tentry = cache->entries + ~i;\n+\t\thashcpy(entry->key, key);\n+\t\thashcpy(entry->value, value);\n+\t\tcache->count++;\n+\t\tcache->dirty = 1;\n+\t} else { /* overwrite existing entry */\n+\t\tentry = cache->entries + i;\n+\t\tif (hashcmp(value, entry->value)) {\n+\t\t\thashcpy(entry->value, value);\n+\t\t\tcache->dirty = 1;\n+\t\t}\n+\t}\n+\n+\tif (cache->count >= cache->size/4*3)\n+\t\treturn grow_map(cache);\n+\treturn 0;\n+}\ndiff --git a/cached-sha1-map.h b/cached-sha1-map.h\nnew file mode 100644\nindex 0000000..296c17c\n--- /dev/null\n+++ b/cached-sha1-map.h\n@@ -0,0 +1,45 @@\n+#ifndef CACHED_SHA1_MAP_H\n+#define CACHED_SHA1_MAP_H\n+\n+#include \"cache.h\"\n+\n+/*\n+ * A cached-sha1-map is a file storing a hash map from sha1 to sha1.\n+ *\n+ * The file is mmap'ed, updated in memory during operation, and flushed\n+ * back to disk when freed. Currently the entire file is rewritten for\n+ * any change. This could be a significant bottleneck for common uses,\n+ * so it would be good to fix this later if possible.\n+ *\n+ * The performance of a hash map depends highly on a good hashing\n+ * algorithm, to avoid collisions. Lucky us! SHA-1 is a pretty good\n+ * hashing algorithm.\n+ */\n+\n+struct cached_sha1_entry {\n+\tunsigned char key[20];\n+\tunsigned char value[20];\n+};\n+\n+struct cached_sha1_map {\n+\tconst char *filename; /* relative to GIT_DIR */\n+\n+\t/* rest is for internal use */\n+\tuint32_t count, size;\n+\tunsigned int initialized : 1;\n+\tunsigned int dirty : 1;\n+\tunsigned int mmapped : 1;\n+\tstruct cached_sha1_entry *entries; /* pointer to mmap'ed memory + 1 */\n+};\n+\n+extern int get_cached_sha1_entry(struct cached_sha1_map *cache,\n+\tconst unsigned char *key,unsigned char *value);\n+\n+extern int set_cached_sha1_entry(struct cached_sha1_map *cache,\n+\tconst unsigned char *key, const unsigned char *value);\n+\n+extern int write_cached_sha1_map(struct cached_sha1_map *cache);\n+\n+extern void free_cached_sha1_map(struct cached_sha1_map *cache);\n+\n+#endif\ndiff --git a/patch-ids.c b/patch-ids.c\nindex 3be5d31..5ba12fb 100644\n--- a/patch-ids.c\n+++ b/patch-ids.c\n@@ -2,17 +2,49 @@\n #include \"diff.h\"\n #include \"commit.h\"\n #include \"patch-ids.h\"\n+#include \"cached-sha1-map.h\"\n+\n+int cache_patch_ids = 1;\n+static struct cached_sha1_map patch_id_cache;\n+\n+static struct diff_options default_options;\n+#define IGNORED_DIFF_OPTS (DIFF_OPT_HAS_CHANGES | DIFF_OPT_CHECK_FAILED)\n\n static int commit_patch_id(struct commit *commit, struct diff_options *options,\n \t\t unsigned char *sha1)\n {\n+\tint use_cache = 0;\n+\tint ret;\n+\n+\t/* only cache if diff options are defaults */\n+\tif (cache_patch_ids) {\n+\t\tdefault_options.found_changes = options->found_changes;\n+\t\tdefault_options.flags = (options->flags & IGNORED_DIFF_OPTS)\n+\t\t\t| (default_options.flags & ~IGNORED_DIFF_OPTS);\n+\t\tuse_cache = !memcmp(options, &default_options,\n+\t\t\t\t sizeof(struct diff_options));\n+\t}\n+\n+\t/* pull patch-id out of the cache if possible */\n+\tpatch_id_cache.filename = \"patch-id-cache\";\n+\tif (use_cache && !get_cached_sha1_entry(&patch_id_cache,\n+\t\t\tcommit->object.sha1, sha1))\n+\t\treturn 0;\n+\n \tif (commit->parents)\n \t\tdiff_tree_sha1(commit->parents->item->object.sha1,\n \t\t commit->object.sha1, \"\", options);\n \telse\n \t\tdiff_root_tree_sha1(commit->object.sha1, \"\", options);\n \tdiffcore_std(options);\n-\treturn diff_flush_patch_id(options, sha1);\n+\tret = diff_flush_patch_id(options, sha1);\n+\tif (ret)\n+\t\treturn ret;\n+\n+\t/* record commit, patch-id pair in cache */\n+\tif (use_cache)\n+\t\tset_cached_sha1_entry(&patch_id_cache, commit->object.sha1, sha1);\n+\treturn 0;\n }\n\n static uint32_t take2(const unsigned char *id)\n@@ -124,6 +156,7 @@ int init_patch_ids(struct patch_ids *ids)\n \tDIFF_OPT_SET(&ids->diffopts, RECURSIVE);\n \tif (diff_setup_done(&ids->diffopts) < 0)\n \t\treturn error(\"diff_setup_done failed\");\n+\tdefault_options = ids->diffopts; /* remember defaults */\n \treturn 0;\n }\n\n@@ -136,6 +169,11 @@ int free_patch_ids(struct patch_ids *ids)\n \t\tnext = patches->next;\n \t\tfree(patches);\n \t}\n+\n+\t/* write cached patch-ids and ignore any errors that arise\n+\t * (e.g. if the repository is write protected) */\n+\tif (cache_patch_ids)\n+\t\twrite_cached_sha1_map(&patch_id_cache);\n \treturn 0;\n }\n\ndiff --git a/patch-ids.h b/patch-ids.h\nindex c8c7ca1..c0ebdc1 100644\n--- a/patch-ids.h\n+++ b/patch-ids.h\n@@ -18,4 +18,6 @@ int free_patch_ids(struct patch_ids *);\n struct patch_id *add_commit_patch_id(struct commit *, struct patch_ids *);\n struct patch_id *has_commit_patch_id(struct commit *, struct patch_ids *);\n\n+extern int cache_patch_ids;\n+\n #endif /* PATCH_IDS_H */\n-- \n1.5.6.2.256.g3ef05.dirty\n"},{"id":"83439","messageId":"alpine.DEB.1.00.0807152255020.2990@eeepc-johanness","threadId":"14364","inReplyTo":"7f9d599f0807150957o78d46204x280668c763fba2bf@mail.gmail.com","subject":"Re: [PATCH] cherry: cache patch-ids to avoid repeating work","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2008-07-15T21:52:22Z","receivedAt":"2008-07-15T21:52:22Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOkay, it seems like I never have time to review this, so I'll just \ntake a few minutes to comment on some aspects:\n\nOn Tue, 15 Jul 2008, Geoffrey Irving wrote:\n\n> +static int git_cherry_config(const char *var, const char *value, void *cb)\n> +{\n> +\tif (!strcmp(var, \"cherry.cachepatchids\")) {\n> +\t\tcache_patch_ids = git_config_bool(var, value);\n> +\t\treturn 0;\n> +\t}\n> +\n> +\treturn 0;\n> +}\n> +\n> static const char cherry_usage[] =\n> \"git-cherry [-v] [] []\";\n> int cmd_cherry(int argc, const char **argv, const char *prefix)\n> @@ -1094,6 +1104,8 @@ int cmd_cherry(int argc, const char **argv,\n> const char *prefix)\n> \tconst char *limit = NULL;\n> \tint verbose = 0;\n> \n> +\tgit_config(git_cherry_config, NULL);\n> +\n> \tif (argc > 1 && !strcmp(argv[1], \"-v\")) {\n> \t\tverbose = 1;\n> \t\targc--;\n\nIs this really purely for cherry, and not at all for \"log --cherry-pick\"? \nMaybe it should be \"cache.patchIds\" to begin with.\n\n> diff --git a/cached-sha1-map.c b/cached-sha1-map.c\n> new file mode 100644\n> index 0000000..9cf7252\n> --- /dev/null\n> +++ b/cached-sha1-map.c\n> @@ -0,0 +1,293 @@\n> +#include \"cached-sha1-map.h\"\n> +\n> +union cached_sha1_map_header {\n> +\tstruct {\n> +\t\tchar signature[4]; /* CS1M */\n> +\t\tuint32_t version;\n> +\t\tuint32_t count;\n> +\t\tuint32_t size;\n> +\t\tuint32_t pad; /* pad to 20 bytes */\n> +\t} u;\n> +\t/* pad header out to 40 bytes. As a consistency\n> +\t * check, pad.value stores the sha1 of pad.key. */\n> +\tstruct cached_sha1_entry pad;\n\nWhy does it have to be a union?\n\n> +};\n> +\n> +static const char *signature = \"CS1M\";\n\nCarrie Scr*ws 1 Man?\n\n> +static int init_empty_map(struct cached_sha1_map *cache, uint32_t size)\n> +{\n> +\tcache->count = 0;\n> +\tcache->size = size;\n\nWe seem to call this \"alloc\" (almost) everywhere else.\n\n> +\tcache->initialized = 1;\n\nMaybe we do not need that: when size is != 0, it was initialized.\n\n> +\tcache->mmapped = 0;\n> +\tcache->dirty = 1;\n\nIs it already dirty? I don't think so.\n\n> +\tcache->entries = calloc(size, sizeof(struct cached_sha1_entry));\n> +\tif (!cache->entries) {\n> +\t\twarning(\"failed to allocate empty map of size %\"PRIu32\" for %s\",\n> +\t\t\tsize, git_path(cache->filename));\n\nxcalloc() to the rescue.\n\n> +static int grow_map(struct cached_sha1_map *cache)\n> +{\n> +\tstruct cached_sha1_map new_cache;\n> +\tuint32_t i;\n> +\n> +\tif (cache->size * 2 == 0) {\n> +\t\twarning(\"%s overflowed, so resetting to empty\",\n> +\t\t\tgit_path(cache->filename));\n\nIMHO we can safely ignore that case: If that is true, we have seen at \nleast 2^32 objects. However, each object takes more than 4 bytes, so that \nis a literal impossibility.\n\nI'd rather not bother with this case.\n\n> +\t/* allocate cache with twice the size */\n> +\tnew_cache.filename = cache->filename;\n> +\tif (init_empty_map(&new_cache, cache->size * 2)) {\n\nReally, I think that these checks should be _made_ unnecessary, by \nrestricting the size of the cache. IMO Caching more than 2^10 patch ids \n(completely made up on the spot) is probably even detrimental, and it \nmight be better to just scratch them all and start with a new cache then.\n\nBesides, the file would have a substantial size by then.\n\n> +static int init_cached_sha1_map(struct cached_sha1_map *cache)\n> +{\n>\n> [...]\n>\n> +\tSHA1_Init(&ctx);\n> +\tSHA1_Update(&ctx, header.pad.key, 20);\n> +\tSHA1_Final(header.pad.key, &ctx); /* reuse pad.key to store its sha1 */\n> +\tif (hashcmp(header.pad.key, header.pad.value)) {\n> +\t\twarning(\"%s header has invalid sha1\", filename);\n> +\t\tgoto empty;\n> +\t}\n\nI do not think that it is worth checking that. If you do not trust your \nhard disk, you might just as well jump out the window.\n\nChecking just takes too much time.\n\n> +\t/* mmap entire file so that file / memory blocks are aligned */\n> +\tmap_size = sizeof(struct cached_sha1_entry) * (cache->size + 1);\n> +\tcache->entries = mmap(NULL, map_size,\n> +\t\tPROT_READ | PROT_WRITE, MAP_PRIVATE, fd, 0);\n\nAFAIR there were _serious_ performance issues with mmap() on non-Linux \nplatforms. I chose pread() in my original implementation for a reason.\n\n> +static int32_t find_helper(struct cached_sha1_map *cache,\n> +\tconst unsigned char *key)\n> +{\n> +\tint32_t i, mask, full;\n> +\n> +\tmask = cache->size - 1;\n> +\ti = get_hash_index(key) & mask;\n> +\tfull = (i-1) & mask;\n> +\n> +\tfor (; ; i = (i+1) & mask) {\n\nWow, that is ugly.\n\n> +struct cached_sha1_map {\n> +\tconst char *filename; /* relative to GIT_DIR */\n\nWhy does the map need to know its name? The index does not.\n\n> +static struct diff_options default_options;\n> +#define IGNORED_DIFF_OPTS (DIFF_OPT_HAS_CHANGES | DIFF_OPT_CHECK_FAILED)\n> \n> static int commit_patch_id(struct commit *commit, struct diff_options *options,\n> \t\t unsigned char *sha1)\n> {\n> +\tint use_cache = 0;\n> +\tint ret;\n> +\n> +\t/* only cache if diff options are defaults */\n> +\tif (cache_patch_ids) {\n> +\t\tdefault_options.found_changes = options->found_changes;\n> +\t\tdefault_options.flags = (options->flags & IGNORED_DIFF_OPTS)\n> +\t\t\t| (default_options.flags & ~IGNORED_DIFF_OPTS);\n> +\t\tuse_cache = !memcmp(options, &default_options,\n> +\t\t\t\t sizeof(struct diff_options));\n> +\t}\n\nHmm.\n\nI'd rather set \"revs.diff\" late, and unset \"cache_patch_ids\" if it is set. \nIOW let the rev_opt parser decide.\n\nUnfortunately, I do not have time to look into your patch in more detail, \neven if I like the idea.\n\nCiao,\nDscho\n"},{"id":"83446","messageId":"7vod4yztf5.fsf@gitster.siamese.dyndns.org","threadId":"14364","inReplyTo":"alpine.DEB.1.00.0807152255020.2990@eeepc-johanness","subject":"Re: [PATCH] cherry: cache patch-ids to avoid repeating work","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2008-07-15T22:14:38Z","receivedAt":"2008-07-15T22:14:38Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Johannes Schindelin writes:\n\n> Okay, it seems like I never have time to review this, so I'll just \n> take a few minutes to comment on some aspects:\n>\n>> @@ -1094,6 +1104,8 @@ int cmd_cherry(int argc, const char **argv,\n>> const char *prefix)\n>> \tconst char *limit = NULL;\n>> \tint verbose = 0;\n>> \n>> +\tgit_config(git_cherry_config, NULL);\n>> +\n>> \tif (argc > 1 && !strcmp(argv[1], \"-v\")) {\n>> \t\tverbose = 1;\n>> \t\targc--;\n>\n> Is this really purely for cherry, and not at all for \"log --cherry-pick\"? \n> Maybe it should be \"cache.patchIds\" to begin with.\n\nWhat other things would we want caches for?\n\nAs a general rule, I'd prefer keeping these unproven new features opt\nin (i.e. default to false unless explicitly asked for).\n\n>> +union cached_sha1_map_header {\n>> +\tstruct {\n>> +\t\tchar signature[4]; /* CS1M */\n>> +\t\tuint32_t version;\n>> +\t\tuint32_t count;\n>> +\t\tuint32_t size;\n>> +\t\tuint32_t pad; /* pad to 20 bytes */\n>> +\t} u;\n>> +\t/* pad header out to 40 bytes. As a consistency\n>> +\t * check, pad.value stores the sha1 of pad.key. */\n>> +\tstruct cached_sha1_entry pad;\n>\n> Why does it have to be a union?\n\nHmm. I think you are right.\n\n\tstruct cached_sha1_map_header {\n \tchar signature[4];\n uint32_t version;\n uint32_t count;\n uint32_t size;\n uint32_t unused;\n\t\tunsigned char csum[20];\n\t};\n\nwould equally be good, as long as we assume the struct is naturally\npacked. I do agree with you that it may not worth checking only the\nheader, though. \n\n>> +static const char *signature = \"CS1M\";\n>\n> Carrie Scr*ws 1 Man?\n\nNo Idea ;-)\n\n>> +\tcache->mmapped = 0;\n>> +\tcache->dirty = 1;\n>\n> Is it already dirty? I don't think so.\n\nThis flag is more about \"do we need to write it back to file\", and when it\nstarts out without reading from an existing file, we always need to as\nlong as the table contains something at the end of the processing.\n\nYou could instead check (!cache->mmapped && cache->count) for that, I\nguess.\n\n>> +\tcache->entries = calloc(size, sizeof(struct cached_sha1_entry));\n>> +\tif (!cache->entries) {\n>> +\t\twarning(\"failed to allocate empty map of size %\"PRIu32\" for %s\",\n>> +\t\t\tsize, git_path(cache->filename));\n>\n> xcalloc() to the rescue.\n\nThis is purely optional cache and we would want to degrade to operate\nwithout it if any of these fails. xcalloc() won't let you do so.\n\n> Really, I think that these checks should be _made_ unnecessary, by \n> restricting the size of the cache. IMO Caching more than 2^10 patch ids \n> (completely made up on the spot) is probably even detrimental, and it \n> might be better to just scratch them all and start with a new cache then.\n\nProbably. Or fall back on uncached operation.\n\n>> +static int init_cached_sha1_map(struct cached_sha1_map *cache)\n>> +{\n>>\n>> [...]\n>>\n>> +\tSHA1_Init(&ctx);\n>> +\tSHA1_Update(&ctx, header.pad.key, 20);\n>> +\tSHA1_Final(header.pad.key, &ctx); /* reuse pad.key to store its sha1 */\n>> +\tif (hashcmp(header.pad.key, header.pad.value)) {\n>> +\t\twarning(\"%s header has invalid sha1\", filename);\n>> +\t\tgoto empty;\n>> +\t}\n>\n> I do not think that it is worth checking that. If you do not trust your \n> hard disk, you might just as well jump out the window.\n>\n> Checking just takes too much time.\n\nThis is only checking the header, so it won't take much time, but I tend\nto doubt the value of this.\n\n>> +\t/* mmap entire file so that file / memory blocks are aligned */\n>> +\tmap_size = sizeof(struct cached_sha1_entry) * (cache->size + 1);\n>> +\tcache->entries = mmap(NULL, map_size,\n>> +\t\tPROT_READ | PROT_WRITE, MAP_PRIVATE, fd, 0);\n>\n> AFAIR there were _serious_ performance issues with mmap() on non-Linux \n> platforms. I chose pread() in my original implementation for a reason.\n\nThat is not a reason to punish users on platforms with working mmap(2) ;-).\n"},{"id":"83482","messageId":"20080716065733.GB32617@diana.vm.bytemark.co.uk","threadId":"14364","inReplyTo":"7vod4yztf5.fsf@gitster.siamese.dyndns.org","subject":"Re: [PATCH] cherry: cache patch-ids to avoid repeating work","fromName":"Karl Hasselström","fromEmail":"kha@treskal.com","sentAt":"2008-07-16T06:57:33Z","receivedAt":"2008-07-16T06:57:33Z","isPatch":true,"sender":{"key":"kha@treskal.com","avatar":"https://gravatar.com/avatar/f0120c734b5279b345075a28521e1ac66acb20c9913ffe9bf6ae97e53f7f3f13?d=mp&s=160"},"body":"On 2008-07-15 15:14:38 -0700, Junio C Hamano wrote:\n\n> Johannes Schindelin writes:\n>\n> > > +static const char *signature = \"CS1M\";\n> >\n> > Carrie Scr*ws 1 Man?\n>\n> No Idea ;-)\n\nGiven the \"cached_sha1_map_header\" union (or struct) earlier in the\npatch, I know what my guess is. :-)\n\n-- \nKarl Hasselström, kha@treskal.com\n www.treskal.com/kalle\n"},{"id":"83486","messageId":"200807160922.30275.johan@herland.net","threadId":"14364","inReplyTo":"7vod4yztf5.fsf@gitster.siamese.dyndns.org","subject":"Re: [PATCH] cherry: cache patch-ids to avoid repeating work","fromName":"Johan Herland","fromEmail":"johan@herland.net","sentAt":"2008-07-16T07:22:30Z","receivedAt":"2008-07-16T07:22:30Z","isPatch":true,"sender":{"key":"johan@herland.net","avatar":"https://avatars.githubusercontent.com/u/547031?v=4"},"body":"On Wednesday 16 July 2008, Junio C Hamano wrote:\n> Johannes Schindelin writes:\n> > Okay, it seems like I never have time to review this, so I'll just\n> >\n> > take a few minutes to comment on some aspects:\n> >> @@ -1094,6 +1104,8 @@ int cmd_cherry(int argc, const char **argv,\n> >> const char *prefix)\n> >> \tconst char *limit = NULL;\n> >> \tint verbose = 0;\n> >>\n> >> +\tgit_config(git_cherry_config, NULL);\n> >> +\n> >> \tif (argc > 1 && !strcmp(argv[1], \"-v\")) {\n> >> \t\tverbose = 1;\n> >> \t\targc--;\n> >\n> > Is this really purely for cherry, and not at all for \"log\n> > --cherry-pick\"? Maybe it should be \"cache.patchIds\" to begin with.\n>\n> What other things would we want caches for?\n\nThis should be fairly obvious:\n\n- git-notes (uses sha1-to-sha1 cache for storing commit-to-note\n relationship)\n\n- integrated bug trackers (uses sha1-to-sha1 cache for storing\n commit-to-bugreport (or similar) relationships)\n\n- ...any other mechanism that want to quickly map from a git object to some\n associated data\n\nThere are probably plenty more ideas and use cases if people start looking.\n\nAFAICS, each different use case would keep its cache in a separate file.\n\nFor local-repo-only caches the cache is kept within $GIT_DIR, and for shared \ncaches (IF that makes sense in any of the use cases) the cache could be \nlocated in the working tree (either as a .git_foo file on relevant \nbranches, or as a file on a separate domain-specific branch).\n\n\nHave fun! :)\n\n...Johan\n\n-- \nJohan Herland, \nwww.herland.net\n"}]}