{"thread":{"id":"29733","subject":"[PATCH 0/4] index-pack improvements","startedAt":"2012-02-25T10:56:12Z","lastAt":"2012-02-25T10:56:16Z","messageCount":5,"participants":["Nguyễn Thái Ngọc Duy"],"isPatch":true,"patchVersion":1,"patchTotal":4},"messages":[{"id":"185412","messageId":"1330167376-24859-1-git-send-email-pclouds@gmail.com","threadId":"29733","inReplyTo":null,"subject":"[PATCH 0/4] index-pack improvements","fromName":"Nguyễn Thái Ngọc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2012-02-25T10:56:12Z","receivedAt":"2012-02-25T10:56:12Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"The first two patches are posted already, which help keep memory usage\ndown in the present of large blobs. The forth patch attempts to\nresolve deltas in parallel.\n\n$ time ./git index-pack --threads=1 --verify -v XXXX\nIndexing objects: 100% (165375/165375), done.\nResolving deltas: 100% (124749/124749), done.\n\nreal    1m15.470s\nuser    1m14.899s\nsys     0m0.552s\n\n$ time ./git index-pack --threads=2 --verify -v XXXX\nIndexing objects: 100% (165375/165375), done.\nResolving deltas: 100% (124749/124749), done.\n\nreal    0m41.339s\nuser    1m15.116s\nsys     0m0.680s\n\n$ time ./git index-pack --threads=3 --verify -v XXXX\nIndexing objects: 100% (165375/165375), done.\nResolving deltas: 100% (124749/124749), done.\n\nreal    0m37.008s\nuser    1m35.742s\nsys     0m0.803s\n\n$ time ./git index-pack --verify -v XXXX   # four core machine\nIndexing objects: 100% (165375/165375), done.\nResolving deltas: 100% (124749/124749), done.\n\nreal    0m33.701s\nuser    1m51.316s\nsys     0m0.768s\n\n$ time ./git index-pack --threads=8 --verify -v XXXX\nIndexing objects: 100% (165375/165375), done.\nResolving deltas: 100% (124749/124749), done.\n\nreal    0m33.638s\nuser    1m51.783s\nsys     0m0.773s\n\nSo there's improvement from user persepective, but overhead is too\nhigh (user time from 1m14 to 1m51). Making threaded_second_pass to\nprocess 512 consecutive objects each iteration to reduce contention on\nwork_mutex does not help. Any ideas?\n\nNguyễn Thái Ngọc Duy (4):\n  index-pack --verify: skip sha-1 collision test\n  index-pack: reduce memory usage when the pack has large blobs\n  index-pack: move second pass code into separate function\n  index-pack: support multithreaded delta resolving\n\n Documentation/config.txt         |    4 +\n Documentation/git-index-pack.txt |   10 ++\n Makefile                         |    2 +-\n builtin/index-pack.c             |  298 +++++++++++++++++++++++++++++++-------\n 4 files changed, 260 insertions(+), 54 deletions(-)\n\n-- \n1.7.8.36.g69ee2\n"},{"id":"185413","messageId":"1330167376-24859-2-git-send-email-pclouds@gmail.com","threadId":"29733","inReplyTo":"1330167376-24859-1-git-send-email-pclouds@gmail.com","subject":"[PATCH 1/4] index-pack --verify: skip sha-1 collision test","fromName":"Nguyễn Thái Ngọc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2012-02-25T10:56:13Z","receivedAt":"2012-02-25T10:56:13Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"index-pack --verify (or verify-pack) is about verifying the pack\nitself. SHA-1 collision test is about outside (probably malicious)\nobjects with the same SHA-1 entering current repo.\n\nSHA-1 collision test is currently done unconditionally. Which means if\nyou verify an in-repo pack, all objects from the pack will be checked\nagainst objects in repo, which are themselves.\n\nSkip this test for --verify, unless --strict is also specified.\n\nlinux-2.6 $ ls -sh .git/objects/pack/pack-e7732c98a8d54840add294c3c562840f78764196.pack\n401M .git/objects/pack/pack-e7732c98a8d54840add294c3c562840f78764196.pack\n\nWithout the patch (and with another patch to cut out second pass in\nindex-pack):\n\nlinux-2.6 $ time ~/w/git/old index-pack -v --verify .git/objects/pack/pack-e7732c98a8d54840add294c3c562840f78764196.pack\nIndexing objects: 100% (1944656/1944656), done.\nfatal: pack has 1617280 unresolved deltas\n\nreal    1m1.223s\nuser    0m55.028s\nsys     0m0.828s\n\nWith the patch:\n\nlinux-2.6 $ time ~/w/git/git index-pack -v --verify .git/objects/pack/pack-e7732c98a8d54840add294c3c562840f78764196.pack\nIndexing objects: 100% (1944656/1944656), done.\nfatal: pack has 1617280 unresolved deltas\n\nreal    0m41.714s\nuser    0m40.994s\nsys     0m0.550s\n\nSigned-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>\n---\n builtin/index-pack.c |    5 +++--\n 1 files changed, 3 insertions(+), 2 deletions(-)\n\ndiff --git a/builtin/index-pack.c b/builtin/index-pack.c\nindex dd1c5c9..cee83b9 100644\n--- a/builtin/index-pack.c\n+++ b/builtin/index-pack.c\n@@ -62,6 +62,7 @@ static int nr_resolved_deltas;\n \n static int from_stdin;\n static int strict;\n+static int verify;\n static int verbose;\n \n static struct progress *progress;\n@@ -461,7 +462,7 @@ static void sha1_object(const void *data, unsigned long size,\n \t\t\tenum object_type type, unsigned char *sha1)\n {\n \thash_sha1_file(data, size, typename(type), sha1);\n-\tif (has_sha1_file(sha1)) {\n+\tif ((strict || !verify) && has_sha1_file(sha1)) {\n \t\tvoid *has_data;\n \t\tenum object_type has_type;\n \t\tunsigned long has_size;\n@@ -1078,7 +1079,7 @@ static void show_pack_info(int stat_only)\n \n int cmd_index_pack(int argc, const char **argv, const char *prefix)\n {\n-\tint i, fix_thin_pack = 0, verify = 0, stat_only = 0, stat = 0;\n+\tint i, fix_thin_pack = 0, stat_only = 0, stat = 0;\n \tconst char *curr_pack, *curr_index;\n \tconst char *index_name = NULL, *pack_name = NULL;\n \tconst char *keep_name = NULL, *keep_msg = NULL;\n-- \n1.7.8.36.g69ee2\n"},{"id":"185415","messageId":"1330167376-24859-3-git-send-email-pclouds@gmail.com","threadId":"29733","inReplyTo":"1330167376-24859-1-git-send-email-pclouds@gmail.com","subject":"[PATCH 2/4] index-pack: reduce memory usage when the pack has large blobs","fromName":"Nguyễn Thái Ngọc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2012-02-25T10:56:14Z","receivedAt":"2012-02-25T10:56:14Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"This command unpacks every non-delta objects in order to:\n\n1. calculate sha-1\n2. do byte-to-byte sha-1 collision test if we happen to have objects\n   with the same sha-1\n3. validate object content in strict mode\n\nAll this requires the entire object to stay in memory, a bad news for\ngiant blobs. This patch lowers memory consumption by not saving the\nobject in memory whenever possible, calculating SHA-1 while unpacking\nthe object.\n\nThis patch assumes that the collision test is rarely needed. The\ncollision test will be done later in second pass if necessary, which\nputs the entire object back to memory again (We could even do the\ncollision test without putting the entire object back in memory, by\ncomparing as we unpack it).\n\nIn strict mode, it always keeps non-blob objects in memory for\nvalidation (blobs do not need data validation). \"--strict --verify\"\nalso keeps blobs in memory.\n\nSigned-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>\n---\n builtin/index-pack.c |   74 +++++++++++++++++++++++++++++++++++++++++---------\n 1 files changed, 61 insertions(+), 13 deletions(-)\n\ndiff --git a/builtin/index-pack.c b/builtin/index-pack.c\nindex cee83b9..ab24dd8 100644\n--- a/builtin/index-pack.c\n+++ b/builtin/index-pack.c\n@@ -277,30 +277,60 @@ static void unlink_base_data(struct base_data *c)\n \tfree_base_data(c);\n }\n \n-static void *unpack_entry_data(unsigned long offset, unsigned long size)\n+static void *unpack_entry_data(unsigned long offset, unsigned long size,\n+\t\t\t       enum object_type type, unsigned char *sha1)\n {\n+\tstatic char fixed_buf[8192];\n \tint status;\n \tgit_zstream stream;\n-\tvoid *buf = xmalloc(size);\n+\tvoid *buf;\n+\tgit_SHA_CTX c;\n+\n+\tif (sha1) {\t\t/* do hash_sha1_file internally */\n+\t\tchar hdr[32];\n+\t\tint hdrlen = sprintf(hdr, \"%s %lu\", typename(type), size)+1;\n+\t\tgit_SHA1_Init(&c);\n+\t\tgit_SHA1_Update(&c, hdr, hdrlen);\n+\n+\t\tbuf = fixed_buf;\n+\t} else {\n+\t\tbuf = xmalloc(size);\n+\t}\n \n \tmemset(&stream, 0, sizeof(stream));\n \tgit_inflate_init(&stream);\n \tstream.next_out = buf;\n-\tstream.avail_out = size;\n+\tstream.avail_out = buf == fixed_buf ? sizeof(fixed_buf) : size;\n \n \tdo {\n \t\tstream.next_in = fill(1);\n \t\tstream.avail_in = input_len;\n \t\tstatus = git_inflate(&stream, 0);\n \t\tuse(input_len - stream.avail_in);\n+\t\tif (sha1) {\n+\t\t\tgit_SHA1_Update(&c, buf, stream.next_out - (unsigned char *)buf);\n+\t\t\tstream.next_out = buf;\n+\t\t\tstream.avail_out = sizeof(fixed_buf);\n+\t\t}\n \t} while (status == Z_OK);\n \tif (stream.total_out != size || status != Z_STREAM_END)\n \t\tbad_object(offset, \"inflate returned %d\", status);\n \tgit_inflate_end(&stream);\n+\tif (sha1) {\n+\t\tgit_SHA1_Final(sha1, &c);\n+\t\tbuf = NULL;\n+\t}\n \treturn buf;\n }\n \n-static void *unpack_raw_entry(struct object_entry *obj, union delta_base *delta_base)\n+static int is_delta_type(enum object_type type)\n+{\n+\treturn (type == OBJ_REF_DELTA || type == OBJ_OFS_DELTA);\n+}\n+\n+static void *unpack_raw_entry(struct object_entry *obj,\n+\t\t\t      union delta_base *delta_base,\n+\t\t\t      unsigned char *sha1)\n {\n \tunsigned char *p;\n \tunsigned long size, c;\n@@ -360,7 +390,17 @@ static void *unpack_raw_entry(struct object_entry *obj, union delta_base *delta_\n \t}\n \tobj->hdr_size = consumed_bytes - obj->idx.offset;\n \n-\tdata = unpack_entry_data(obj->idx.offset, obj->size);\n+\t/*\n+\t * --verify --strict: sha1_object() does all collision test\n+\t *          --strict: sha1_object() does all except blobs,\n+\t *                    blobs tested in second pass\n+\t * --verify         : no collision test\n+\t *                  : all in second pass\n+\t */\n+\tif (is_delta_type(obj->type) ||\n+\t    (strict && (verify || obj->type != OBJ_BLOB)))\n+\t\tsha1 = NULL;\t/* save unpacked object */\n+\tdata = unpack_entry_data(obj->idx.offset, obj->size, obj->type, sha1);\n \tobj->idx.crc32 = input_crc32;\n \treturn data;\n }\n@@ -461,8 +501,9 @@ static void find_delta_children(const union delta_base *base,\n static void sha1_object(const void *data, unsigned long size,\n \t\t\tenum object_type type, unsigned char *sha1)\n {\n-\thash_sha1_file(data, size, typename(type), sha1);\n-\tif ((strict || !verify) && has_sha1_file(sha1)) {\n+\tif (data)\n+\t\thash_sha1_file(data, size, typename(type), sha1);\n+\tif (data && (strict || !verify) && has_sha1_file(sha1)) {\n \t\tvoid *has_data;\n \t\tenum object_type has_type;\n \t\tunsigned long has_size;\n@@ -511,11 +552,6 @@ static void sha1_object(const void *data, unsigned long size,\n \t}\n }\n \n-static int is_delta_type(enum object_type type)\n-{\n-\treturn (type == OBJ_REF_DELTA || type == OBJ_OFS_DELTA);\n-}\n-\n /*\n  * This function is part of find_unresolved_deltas(). There are two\n  * walkers going in the opposite ways.\n@@ -702,7 +738,7 @@ static void parse_pack_objects(unsigned char *sha1)\n \t\t\t\tnr_objects);\n \tfor (i = 0; i < nr_objects; i++) {\n \t\tstruct object_entry *obj = &objects[i];\n-\t\tvoid *data = unpack_raw_entry(obj, &delta->base);\n+\t\tvoid *data = unpack_raw_entry(obj, &delta->base, obj->idx.sha1);\n \t\tobj->real_type = obj->type;\n \t\tif (is_delta_type(obj->type)) {\n \t\t\tnr_deltas++;\n@@ -744,6 +780,9 @@ static void parse_pack_objects(unsigned char *sha1)\n \t * - if used as a base, uncompress the object and apply all deltas,\n \t *   recursively checking if the resulting object is used as a base\n \t *   for some more deltas.\n+\t * - if the same object exists in repository and we're not in strict\n+\t *   mode, we skipped the sha-1 collision test in the first pass.\n+\t *   Do it now.\n \t */\n \tif (verbose)\n \t\tprogress = start_progress(\"Resolving deltas\", nr_deltas);\n@@ -753,6 +792,15 @@ static void parse_pack_objects(unsigned char *sha1)\n \n \t\tif (is_delta_type(obj->type))\n \t\t\tcontinue;\n+\n+\t\tif (((!strict && !verify) ||\n+\t\t     (strict && !verify && obj->type == OBJ_BLOB)) &&\n+\t\t    has_sha1_file(obj->idx.sha1)) {\n+\t\t\tvoid *data = get_data_from_pack(obj);\n+\t\t\tsha1_object(data, obj->size, obj->type, obj->idx.sha1);\n+\t\t\tfree(data);\n+\t\t}\n+\n \t\tbase_obj->obj = obj;\n \t\tbase_obj->data = NULL;\n \t\tfind_unresolved_deltas(base_obj);\n-- \n1.7.8.36.g69ee2\n"},{"id":"185414","messageId":"1330167376-24859-4-git-send-email-pclouds@gmail.com","threadId":"29733","inReplyTo":"1330167376-24859-1-git-send-email-pclouds@gmail.com","subject":"[PATCH 3/4] index-pack: move second pass code into separate function","fromName":"Nguyễn Thái Ngọc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2012-02-25T10:56:15Z","receivedAt":"2012-02-25T10:56:15Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"\nSigned-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>\n---\n builtin/index-pack.c |   54 +++++++++++++++++++++++++++----------------------\n 1 files changed, 30 insertions(+), 24 deletions(-)\n\ndiff --git a/builtin/index-pack.c b/builtin/index-pack.c\nindex ab24dd8..e1e858a 100644\n--- a/builtin/index-pack.c\n+++ b/builtin/index-pack.c\n@@ -719,6 +719,35 @@ static int compare_delta_entry(const void *a, const void *b)\n \t\t\t\t   objects[delta_b->obj_no].type);\n }\n \n+/*\n+ * Second pass:\n+ * - for all non-delta objects, look if it is used as a base for\n+ *   deltas;\n+ * - if used as a base, uncompress the object and apply all deltas,\n+ *   recursively checking if the resulting object is used as a base\n+ *   for some more deltas.\n+ * - if the same object exists in repository and we're not in strict\n+ *   mode, we skipped the sha-1 collision test in the first pass.\n+ *   Do it now.\n+ */\n+static void second_pass(struct object_entry *obj)\n+{\n+\tstruct base_data *base_obj = alloc_base_data();\n+\n+\tif (((!strict && !verify) ||\n+\t     (strict && !verify && obj->type == OBJ_BLOB)) &&\n+\t    has_sha1_file(obj->idx.sha1)) {\n+\t\tvoid *data = get_data_from_pack(obj);\n+\t\tsha1_object(data, obj->size, obj->type, obj->idx.sha1);\n+\t\tfree(data);\n+\t}\n+\n+\tbase_obj->obj = obj;\n+\tbase_obj->data = NULL;\n+\tfind_unresolved_deltas(base_obj);\n+\tdisplay_progress(progress, nr_resolved_deltas);\n+}\n+\n /* Parse all objects and return the pack content SHA1 hash */\n static void parse_pack_objects(unsigned char *sha1)\n {\n@@ -773,38 +802,15 @@ static void parse_pack_objects(unsigned char *sha1)\n \tqsort(deltas, nr_deltas, sizeof(struct delta_entry),\n \t      compare_delta_entry);\n \n-\t/*\n-\t * Second pass:\n-\t * - for all non-delta objects, look if it is used as a base for\n-\t *   deltas;\n-\t * - if used as a base, uncompress the object and apply all deltas,\n-\t *   recursively checking if the resulting object is used as a base\n-\t *   for some more deltas.\n-\t * - if the same object exists in repository and we're not in strict\n-\t *   mode, we skipped the sha-1 collision test in the first pass.\n-\t *   Do it now.\n-\t */\n \tif (verbose)\n \t\tprogress = start_progress(\"Resolving deltas\", nr_deltas);\n \tfor (i = 0; i < nr_objects; i++) {\n \t\tstruct object_entry *obj = &objects[i];\n-\t\tstruct base_data *base_obj = alloc_base_data();\n \n \t\tif (is_delta_type(obj->type))\n \t\t\tcontinue;\n \n-\t\tif (((!strict && !verify) ||\n-\t\t     (strict && !verify && obj->type == OBJ_BLOB)) &&\n-\t\t    has_sha1_file(obj->idx.sha1)) {\n-\t\t\tvoid *data = get_data_from_pack(obj);\n-\t\t\tsha1_object(data, obj->size, obj->type, obj->idx.sha1);\n-\t\t\tfree(data);\n-\t\t}\n-\n-\t\tbase_obj->obj = obj;\n-\t\tbase_obj->data = NULL;\n-\t\tfind_unresolved_deltas(base_obj);\n-\t\tdisplay_progress(progress, nr_resolved_deltas);\n+\t\tsecond_pass(obj);\n \t}\n }\n \n-- \n1.7.8.36.g69ee2\n"},{"id":"185416","messageId":"1330167376-24859-5-git-send-email-pclouds@gmail.com","threadId":"29733","inReplyTo":"1330167376-24859-1-git-send-email-pclouds@gmail.com","subject":"[PATCH 4/4] index-pack: support multithreaded delta resolving","fromName":"Nguyễn Thái Ngọc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2012-02-25T10:56:16Z","receivedAt":"2012-02-25T10:56:16Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"\nSigned-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>\n---\n Documentation/config.txt         |    4 +\n Documentation/git-index-pack.txt |   10 ++\n Makefile                         |    2 +-\n builtin/index-pack.c             |  197 ++++++++++++++++++++++++++++++++------\n 4 files changed, 182 insertions(+), 31 deletions(-)\n\ndiff --git a/Documentation/config.txt b/Documentation/config.txt\nindex e55dae1..965304b 100644\n--- a/Documentation/config.txt\n+++ b/Documentation/config.txt\n@@ -445,6 +445,10 @@ for all users/operating systems, except on the largest projects.\n You probably do not need to adjust this value.\n +\n Common unit suffixes of 'k', 'm', or 'g' are supported.\n++\n+When gitlink:git-index-pack[1] runs on more than one thread, this\n+value is applied per thread so the total amount of used memory depends\n+on how many threads are used.\n \n core.bigFileThreshold::\n \tFiles larger than this size are stored deflated, without\ndiff --git a/Documentation/git-index-pack.txt b/Documentation/git-index-pack.txt\nindex 909687f..7e5f61b 100644\n--- a/Documentation/git-index-pack.txt\n+++ b/Documentation/git-index-pack.txt\n@@ -74,6 +74,16 @@ OPTIONS\n --strict::\n \tDie, if the pack contains broken objects or links.\n \n+--threads=<n>::\n+\tSpecifies the number of threads to spawn when resolving\n+\tdeltas. This requires that index-pack be compiled with\n+\tpthreads otherwise this option is ignored with a warning.\n+\tThis is meant to reduce packing time on multiprocessor\n+\tmachines. The required amount of memory for the delta search\n+\twindow is however multiplied by the number of threads.\n+\tSpecifying 0 will cause git to auto-detect the number of CPU's\n+\tand set the number of threads accordingly.\n+\n \n Note\n ----\ndiff --git a/Makefile b/Makefile\nindex 1fb1705..5fae875 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -2159,7 +2159,7 @@ builtin/branch.o builtin/checkout.o builtin/clone.o builtin/reset.o branch.o tra\n builtin/bundle.o bundle.o transport.o: bundle.h\n builtin/bisect--helper.o builtin/rev-list.o bisect.o: bisect.h\n builtin/clone.o builtin/fetch-pack.o transport.o: fetch-pack.h\n-builtin/grep.o builtin/pack-objects.o transport-helper.o thread-utils.o: thread-utils.h\n+builtin/index-pack.o builtin/grep.o builtin/pack-objects.o transport-helper.o thread-utils.o: thread-utils.h\n builtin/send-pack.o transport.o: send-pack.h\n builtin/log.o builtin/shortlog.o: shortlog.h\n builtin/prune.o builtin/reflog.o reachable.o: reachable.h\ndiff --git a/builtin/index-pack.c b/builtin/index-pack.c\nindex e1e858a..120195a 100644\n--- a/builtin/index-pack.c\n+++ b/builtin/index-pack.c\n@@ -9,6 +9,7 @@\n #include \"progress.h\"\n #include \"fsck.h\"\n #include \"exec_cmd.h\"\n+#include \"thread-utils.h\"\n \n static const char index_pack_usage[] =\n \"git index-pack [-v] [-o <index-file>] [--keep | --keep=<msg>] [--verify] [--strict] (<pack-file> | --stdin [--fix-thin] [<pack-file>])\";\n@@ -38,6 +39,15 @@ struct base_data {\n \tint ofs_first, ofs_last;\n };\n \n+struct thread_local {\n+#ifndef NO_PTHREADS\n+\tpthread_t thread;\n+#endif\n+\tstruct base_data *base_cache;\n+\tsize_t base_cache_used;\n+\tint nr_resolved_deltas;\n+};\n+\n /*\n  * Even if sizeof(union delta_base) == 24 on 64-bit archs, we really want\n  * to memcmp() only the first 20 bytes.\n@@ -54,11 +64,12 @@ struct delta_entry {\n \n static struct object_entry *objects;\n static struct delta_entry *deltas;\n-static struct base_data *base_cache;\n-static size_t base_cache_used;\n+static struct thread_local *thread_data;\n static int nr_objects;\n+static int nr_processed;\n static int nr_deltas;\n static int nr_resolved_deltas;\n+static int nr_threads;\n \n static int from_stdin;\n static int strict;\n@@ -76,6 +87,42 @@ static git_SHA_CTX input_ctx;\n static uint32_t input_crc32;\n static int input_fd, output_fd, pack_fd;\n \n+#ifndef NO_PTHREADS\n+\n+static pthread_mutex_t read_mutex;\n+#define read_lock()\t\tpthread_mutex_lock(&read_mutex)\n+#define read_unlock()\t\tpthread_mutex_unlock(&read_mutex)\n+\n+static pthread_mutex_t work_mutex;\n+#define work_lock()\t\tpthread_mutex_lock(&work_mutex)\n+#define work_unlock()\t\tpthread_mutex_unlock(&work_mutex)\n+\n+/*\n+ * Mutex and conditional variable can't be statically-initialized on Windows.\n+ */\n+static void init_thread(void)\n+{\n+\tinit_recursive_mutex(&read_mutex);\n+\tpthread_mutex_init(&work_mutex, NULL);\n+}\n+\n+static void cleanup_thread(void)\n+{\n+\tpthread_mutex_destroy(&read_mutex);\n+\tpthread_mutex_destroy(&work_mutex);\n+}\n+\n+#else\n+\n+#define read_lock()\n+#define read_unlock()\n+\n+#define work_lock()\n+#define work_unlock()\n+\n+#endif\n+\n+\n static int mark_link(struct object *obj, int type, void *data)\n {\n \tif (!obj)\n@@ -224,6 +271,18 @@ static NORETURN void bad_object(unsigned long offset, const char *format, ...)\n \tdie(\"pack has bad object at offset %lu: %s\", offset, buf);\n }\n \n+static struct thread_local *get_thread_data()\n+{\n+#ifndef NO_PTHREADS\n+\tint i;\n+\tpthread_t self = pthread_self();\n+\tfor (i = 1; i < nr_threads; i++)\n+\t\tif (self == thread_data[i].thread)\n+\t\t\treturn &thread_data[i];\n+#endif\n+\treturn &thread_data[0];\n+}\n+\n static struct base_data *alloc_base_data(void)\n {\n \tstruct base_data *base = xmalloc(sizeof(struct base_data));\n@@ -238,15 +297,16 @@ static void free_base_data(struct base_data *c)\n \tif (c->data) {\n \t\tfree(c->data);\n \t\tc->data = NULL;\n-\t\tbase_cache_used -= c->size;\n+\t\tget_thread_data()->base_cache_used -= c->size;\n \t}\n }\n \n static void prune_base_data(struct base_data *retain)\n {\n \tstruct base_data *b;\n-\tfor (b = base_cache;\n-\t     base_cache_used > delta_base_cache_limit && b;\n+\tstruct thread_local *data = get_thread_data();\n+\tfor (b = data->base_cache;\n+\t     data->base_cache_used > delta_base_cache_limit && b;\n \t     b = b->child) {\n \t\tif (b->data && b != retain)\n \t\t\tfree_base_data(b);\n@@ -258,22 +318,23 @@ static void link_base_data(struct base_data *base, struct base_data *c)\n \tif (base)\n \t\tbase->child = c;\n \telse\n-\t\tbase_cache = c;\n+\t\tget_thread_data()->base_cache = c;\n \n \tc->base = base;\n \tc->child = NULL;\n \tif (c->data)\n-\t\tbase_cache_used += c->size;\n+\t\tget_thread_data()->base_cache_used += c->size;\n \tprune_base_data(c);\n }\n \n static void unlink_base_data(struct base_data *c)\n {\n-\tstruct base_data *base = c->base;\n+\tstruct base_data *base;\n+\tbase = c->base;\n \tif (base)\n \t\tbase->child = NULL;\n \telse\n-\t\tbase_cache = NULL;\n+\t\tget_thread_data()->base_cache = NULL;\n \tfree_base_data(c);\n }\n \n@@ -503,19 +564,25 @@ static void sha1_object(const void *data, unsigned long size,\n {\n \tif (data)\n \t\thash_sha1_file(data, size, typename(type), sha1);\n-\tif (data && (strict || !verify) && has_sha1_file(sha1)) {\n-\t\tvoid *has_data;\n-\t\tenum object_type has_type;\n-\t\tunsigned long has_size;\n-\t\thas_data = read_sha1_file(sha1, &has_type, &has_size);\n-\t\tif (!has_data)\n-\t\t\tdie(\"cannot read existing object %s\", sha1_to_hex(sha1));\n-\t\tif (size != has_size || type != has_type ||\n-\t\t    memcmp(data, has_data, size) != 0)\n-\t\t\tdie(\"SHA1 COLLISION FOUND WITH %s !\", sha1_to_hex(sha1));\n-\t\tfree(has_data);\n+\tif (data && (strict || !verify)) {\n+\t\tread_lock();\n+\t\tif (has_sha1_file(sha1)) {\n+\t\t\tvoid *has_data;\n+\t\t\tenum object_type has_type;\n+\t\t\tunsigned long has_size;\n+\t\t\thas_data = read_sha1_file(sha1, &has_type, &has_size);\n+\t\t\tread_unlock();\n+\t\t\tif (!has_data)\n+\t\t\t\tdie(\"cannot read existing object %s\", sha1_to_hex(sha1));\n+\t\t\tif (size != has_size || type != has_type ||\n+\t\t\t    memcmp(data, has_data, size) != 0)\n+\t\t\t\tdie(\"SHA1 COLLISION FOUND WITH %s !\", sha1_to_hex(sha1));\n+\t\t\tfree(has_data);\n+\t\t} else\n+\t\t\tread_unlock();\n \t}\n \tif (strict) {\n+\t\tread_lock();\n \t\tif (type == OBJ_BLOB) {\n \t\t\tstruct blob *blob = lookup_blob(sha1);\n \t\t\tif (blob)\n@@ -549,6 +616,7 @@ static void sha1_object(const void *data, unsigned long size,\n \t\t\t}\n \t\t\tobj->flags |= FLAG_CHECKED;\n \t\t}\n+\t\tread_unlock();\n \t}\n }\n \n@@ -589,7 +657,7 @@ static void *get_base_data(struct base_data *c)\n \t\tif (!delta_nr) {\n \t\t\tc->data = get_data_from_pack(obj);\n \t\t\tc->size = obj->size;\n-\t\t\tbase_cache_used += c->size;\n+\t\t\tget_thread_data()->base_cache_used += c->size;\n \t\t\tprune_base_data(c);\n \t\t}\n \t\tfor (; delta_nr > 0; delta_nr--) {\n@@ -605,7 +673,7 @@ static void *get_base_data(struct base_data *c)\n \t\t\tfree(raw);\n \t\t\tif (!c->data)\n \t\t\t\tbad_object(obj->idx.offset, \"failed to apply delta\");\n-\t\t\tbase_cache_used += c->size;\n+\t\t\tget_thread_data()->base_cache_used += c->size;\n \t\t\tprune_base_data(c);\n \t\t}\n \t\tfree(delta);\n@@ -633,7 +701,7 @@ static void resolve_delta(struct object_entry *delta_obj,\n \t\tbad_object(delta_obj->idx.offset, \"failed to apply delta\");\n \tsha1_object(result->data, result->size, delta_obj->real_type,\n \t\t    delta_obj->idx.sha1);\n-\tnr_resolved_deltas++;\n+\tget_thread_data()->nr_resolved_deltas++;\n }\n \n static struct base_data *find_unresolved_deltas_1(struct base_data *base,\n@@ -745,7 +813,30 @@ static void second_pass(struct object_entry *obj)\n \tbase_obj->obj = obj;\n \tbase_obj->data = NULL;\n \tfind_unresolved_deltas(base_obj);\n-\tdisplay_progress(progress, nr_resolved_deltas);\n+}\n+\n+static void *threaded_second_pass(void *arg)\n+{\n+\tstruct thread_local *data = get_thread_data();\n+\tfor (;;) {\n+\t\tint i;\n+\t\twork_lock();\n+\t\tnr_resolved_deltas += data->nr_resolved_deltas;\n+\t\tdisplay_progress(progress, nr_resolved_deltas);\n+\t\tdata->nr_resolved_deltas = 0;\n+\t\twhile (nr_processed < nr_objects &&\n+\t\t       is_delta_type(objects[nr_processed].type))\n+\t\t\tnr_processed++;\n+\t\tif (nr_processed == nr_objects) {\n+\t\t\twork_unlock();\n+\t\t\tbreak;\n+\t\t}\n+\t\ti = nr_processed++;\n+\t\twork_unlock();\n+\n+\t\tsecond_pass(&objects[i]);\n+\t}\n+\treturn NULL;\n }\n \n /* Parse all objects and return the pack content SHA1 hash */\n@@ -804,14 +895,26 @@ static void parse_pack_objects(unsigned char *sha1)\n \n \tif (verbose)\n \t\tprogress = start_progress(\"Resolving deltas\", nr_deltas);\n-\tfor (i = 0; i < nr_objects; i++) {\n-\t\tstruct object_entry *obj = &objects[i];\n-\n-\t\tif (is_delta_type(obj->type))\n-\t\t\tcontinue;\n \n-\t\tsecond_pass(obj);\n+\tnr_processed = 0;\n+#ifndef NO_PTHREADS\n+\tif (nr_threads > 1) {\n+\t\tinit_thread();\n+\t\tfor (i = 1; i < nr_threads; i++) {\n+\t\t\tint ret = pthread_create(&thread_data[i].thread, NULL,\n+\t\t\t\t\t\t threaded_second_pass, NULL);\n+\t\t\tif (ret)\n+\t\t\t\tdie(\"unable to create thread: %s\", strerror(ret));\n+\t\t}\n+\t\tfor (i = 1; i < nr_threads; i++) {\n+\t\t\tpthread_join(thread_data[i].thread, NULL);\n+\t\t\tthread_data[i].thread = 0;\n+\t\t}\n+\t\tcleanup_thread();\n+\t\treturn;\n \t}\n+#endif\n+\tthreaded_second_pass(thread_data);\n }\n \n static int write_compressed(struct sha1file *f, void *in, unsigned int size)\n@@ -1017,6 +1120,17 @@ static int git_index_pack_config(const char *k, const char *v, void *cb)\n \t\t\tdie(\"bad pack.indexversion=%\"PRIu32, opts->version);\n \t\treturn 0;\n \t}\n+\tif (!strcmp(k, \"pack.threads\")) {\n+\t\tnr_threads = git_config_int(k, v);\n+\t\tif (nr_threads < 0)\n+\t\t\tdie(\"invalid number of threads specified (%d)\",\n+\t\t\t    nr_threads);\n+#ifdef NO_PTHREADS\n+\t\tif (nr_threads != 1)\n+\t\t\twarning(\"no threads support, ignoring %s\", k);\n+#endif\n+\t\treturn 0;\n+\t}\n \treturn git_default_config(k, v, cb);\n }\n \n@@ -1175,6 +1289,16 @@ int cmd_index_pack(int argc, const char **argv, const char *prefix)\n \t\t\t\tkeep_msg = \"\";\n \t\t\t} else if (!prefixcmp(arg, \"--keep=\")) {\n \t\t\t\tkeep_msg = arg + 7;\n+\t\t\t} else if (!prefixcmp(arg, \"--threads=\")) {\n+\t\t\t\tchar *end;\n+\t\t\t\tnr_threads = strtoul(arg+10, &end, 0);\n+\t\t\t\tif (!arg[10] || *end || nr_threads < 0)\n+\t\t\t\t\tusage(index_pack_usage);\n+#ifdef NO_PTHREADS\n+\t\t\t\tif (nr_threads != 1)\n+\t\t\t\t\twarning(\"no threads support, \"\n+\t\t\t\t\t\t\"ignoring %s\", arg);\n+#endif\n \t\t\t} else if (!prefixcmp(arg, \"--pack_header=\")) {\n \t\t\t\tstruct pack_header *hdr;\n \t\t\t\tchar *c;\n@@ -1246,6 +1370,19 @@ int cmd_index_pack(int argc, const char **argv, const char *prefix)\n \tif (strict)\n \t\topts.flags |= WRITE_IDX_STRICT;\n \n+#ifndef NO_PTHREADS\n+\tif (!nr_threads)\n+\t\tnr_threads = online_cpus();\n+\t/* reserve thread_data[0] for the main thread */\n+\tif (nr_threads > 1)\n+\t\tnr_threads++;\n+#else\n+\tif (nr_threads != 1)\n+\t\twarning(\"no threads support, ignoring --threads\");\n+\tnr_threads = 1;\n+#endif\n+\tthread_data = xcalloc(nr_threads, sizeof(*thread_data));\n+\n \tcurr_pack = open_pack_file(pack_name);\n \tparse_pack_header();\n \tobjects = xcalloc(nr_objects + 1, sizeof(struct object_entry));\n-- \n1.7.8.36.g69ee2\n"}]}