[PATCH 0/5] multithread traverse_commit_list (aka rev-list)

[PATCH 0/5] multithread traverse_commit_list (aka rev-list)

[Nguyễn Thái Ngọc Duy]

rev-list is quite cpu extensive. While there's better approach to
tackle this (e.g. Shawn's bitmap cache idea), I was curious if
making it parellel could give us anything. So this is a naive (and
failed) attempt at that. I post it anyway, so people, especially gsoc
students if the related proposal is chosen, might learn from it, or
learn to avoid it, or just laugh at my attempt to relieve stress.

While this series does not break rev-list (but breaks all external
commands, I don't care anyway), and it proves lock-free pack access
works, it does not improve rev-list performance. I suspect extensive
locking around "struct object *" may be the culprit.  Or maybe it's
just my dumb partition method. A better partition method that avoids
locking might improve it. We may split the object hash table into 4,
one for each object type and assign one thread for tree, one for blob.
Or something else..

Anyway I'll stop here to finish my ongoing topics for 1.7.11 and maybe
implement Shawn's idea if I still have more time. Effectively generating
the cache from index-pack could be challenging.

Nguyễn Thái Ngọc Duy (5):
  Remove global pointer "packed_git" in favor or set/get function pair
  sha1_file: stuff various pack reading variables into a struct
  Make lookup_*() functions thread-safe
  Teach traverse_commit_list callsites about new parameter, nr_threads
  Support multithread in traverse_commit_list and rev-list

 blob.c                   |   11 ++-
 builtin/count-objects.c  |    4 +-
 builtin/fsck.c           |    4 +-
 builtin/gc.c             |    2 +-
 builtin/pack-objects.c   |   12 +-
 builtin/pack-redundant.c |    4 +-
 builtin/rev-list.c       |    5 +-
 cache.h                  |    8 +-
 commit.c                 |   12 ++-
 git.c                    |    1 +
 list-objects.c           |  157 +++++++++++++++++++++++++-
 list-objects.h           |    2 +-
 object.c                 |    9 ++-
 object.h                 |    6 +
 pack-revindex.c          |    4 +-
 revision.c               |   16 +++
 revision.h               |    2 +
 server-info.c            |    4 +-
 sha1_file.c              |  276 ++++++++++++++++++++++++++++------------------
 sha1_name.c              |    2 +-
 tag.c                    |    9 +-
 tree.c                   |   18 +++-
 upload-pack.c            |    2 +-
 23 files changed, 419 insertions(+), 151 deletions(-)

-- 
1.7.8.36.g69ee2

[PATCH 1/5] Remove global pointer "packed_git" in favor or set/get function pair

[Nguyễn Thái Ngọc Duy]

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 builtin/count-objects.c  |    4 ++--
 builtin/fsck.c           |    4 ++--
 builtin/gc.c             |    2 +-
 builtin/pack-objects.c   |   10 +++++-----
 builtin/pack-redundant.c |    4 ++--
 cache.h                  |    7 +++++--
 pack-revindex.c          |    4 ++--
 server-info.c            |    4 ++--
 sha1_file.c              |   33 ++++++++++++++++++++++-----------
 sha1_name.c              |    2 +-
 10 files changed, 44 insertions(+), 30 deletions(-)

diff --git a/builtin/count-objects.c b/builtin/count-objects.c
index c37cb98..dc217db 100644
--- a/builtin/count-objects.c
+++ b/builtin/count-objects.c
@@ -104,9 +104,9 @@ int cmd_count_objects(int argc, const char **argv, const char *prefix)
 		struct packed_git *p;
 		unsigned long num_pack = 0;
 		off_t size_pack = 0;
-		if (!packed_git)
+		if (!get_packed_git())
 			prepare_packed_git();
-		for (p = packed_git; p; p = p->next) {
+		for (p = get_packed_git(); p; p = p->next) {
 			if (!p->pack_local)
 				continue;
 			if (open_pack_index(p))
diff --git a/builtin/fsck.c b/builtin/fsck.c
index 67eb553..9dbe6d8 100644
--- a/builtin/fsck.c
+++ b/builtin/fsck.c
@@ -669,7 +669,7 @@ int cmd_fsck(int argc, const char **argv, const char *prefix)
 		prepare_packed_git();
 
 		if (show_progress) {
-			for (p = packed_git; p; p = p->next) {
+			for (p = get_packed_git(); p; p = p->next) {
 				if (open_pack_index(p))
 					continue;
 				total += p->num_objects;
@@ -677,7 +677,7 @@ int cmd_fsck(int argc, const char **argv, const char *prefix)
 
 			progress = start_progress("Checking objects", total);
 		}
-		for (p = packed_git; p; p = p->next) {
+		for (p = get_packed_git(); p; p = p->next) {
 			/* verify gives error messages itself */
 			if (verify_pack(p, fsck_obj_buffer,
 					progress, count))
diff --git a/builtin/gc.c b/builtin/gc.c
index 271376d..3007650 100644
--- a/builtin/gc.c
+++ b/builtin/gc.c
@@ -130,7 +130,7 @@ static int too_many_packs(void)
 		return 0;
 
 	prepare_packed_git();
-	for (cnt = 0, p = packed_git; p; p = p->next) {
+	for (cnt = 0, p = get_packed_git(); p; p = p->next) {
 		if (!p->pack_local)
 			continue;
 		if (p->pack_keep)
diff --git a/builtin/pack-objects.c b/builtin/pack-objects.c
index 7b07c09..2f242c4 100644
--- a/builtin/pack-objects.c
+++ b/builtin/pack-objects.c
@@ -840,7 +840,7 @@ static int add_object_entry(const unsigned char *sha1, enum object_type type,
 	if (!exclude && local && has_loose_object_nonlocal(sha1))
 		return 0;
 
-	for (p = packed_git; p; p = p->next) {
+	for (p = get_packed_git(); p; p = p->next) {
 		off_t offset = find_pack_entry_one(sha1, p);
 		if (offset) {
 			if (!found_pack) {
@@ -2183,7 +2183,7 @@ static void add_objects_in_unpacked_packs(struct rev_info *revs)
 
 	memset(&in_pack, 0, sizeof(in_pack));
 
-	for (p = packed_git; p; p = p->next) {
+	for (p = get_packed_git(); p; p = p->next) {
 		const unsigned char *sha1;
 		struct object *o;
 
@@ -2221,7 +2221,7 @@ static int has_sha1_pack_kept_or_nonlocal(const unsigned char *sha1)
 	static struct packed_git *last_found = (void *)1;
 	struct packed_git *p;
 
-	p = (last_found != (void *)1) ? last_found : packed_git;
+	p = (last_found != (void *)1) ? last_found : get_packed_git();
 
 	while (p) {
 		if ((!p->pack_local || p->pack_keep) &&
@@ -2230,7 +2230,7 @@ static int has_sha1_pack_kept_or_nonlocal(const unsigned char *sha1)
 			return 1;
 		}
 		if (p == last_found)
-			p = packed_git;
+			p = get_packed_git();
 		else
 			p = p->next;
 		if (p == last_found)
@@ -2245,7 +2245,7 @@ static void loosen_unused_packed_objects(struct rev_info *revs)
 	uint32_t i;
 	const unsigned char *sha1;
 
-	for (p = packed_git; p; p = p->next) {
+	for (p = get_packed_git(); p; p = p->next) {
 		if (!p->pack_local || p->pack_keep)
 			continue;
 
diff --git a/builtin/pack-redundant.c b/builtin/pack-redundant.c
index f5c6afc..8fece6a 100644
--- a/builtin/pack-redundant.c
+++ b/builtin/pack-redundant.c
@@ -569,7 +569,7 @@ static struct pack_list * add_pack(struct packed_git *p)
 
 static struct pack_list * add_pack_file(const char *filename)
 {
-	struct packed_git *p = packed_git;
+	struct packed_git *p = get_packed_git();
 
 	if (strlen(filename) < 40)
 		die("Bad pack filename: %s", filename);
@@ -584,7 +584,7 @@ static struct pack_list * add_pack_file(const char *filename)
 
 static void load_all(void)
 {
-	struct packed_git *p = packed_git;
+	struct packed_git *p = get_packed_git();
 
 	while (p) {
 		add_pack(p);
diff --git a/cache.h b/cache.h
index e5e1aa4..26d14b4 100644
--- a/cache.h
+++ b/cache.h
@@ -975,7 +975,7 @@ struct pack_window {
 	unsigned int inuse_cnt;
 };
 
-extern struct packed_git {
+struct packed_git {
 	struct packed_git *next;
 	struct pack_window *windows;
 	off_t pack_size;
@@ -993,7 +993,10 @@ extern struct packed_git {
 	unsigned char sha1[20];
 	/* something like ".git/objects/pack/xxxxx.pack" */
 	char pack_name[FLEX_ARRAY]; /* more */
-} *packed_git;
+};
+
+extern struct packed_git *get_packed_git(void);
+extern void set_packed_git(struct packed_git *);
 
 struct pack_entry {
 	off_t offset;
diff --git a/pack-revindex.c b/pack-revindex.c
index 77a0465..636d35d 100644
--- a/pack-revindex.c
+++ b/pack-revindex.c
@@ -45,13 +45,13 @@ static void init_pack_revindex(void)
 	int num;
 	struct packed_git *p;
 
-	for (num = 0, p = packed_git; p; p = p->next)
+	for (num = 0, p = get_packed_git(); p; p = p->next)
 		num++;
 	if (!num)
 		return;
 	pack_revindex_hashsz = num * 11;
 	pack_revindex = xcalloc(sizeof(*pack_revindex), pack_revindex_hashsz);
-	for (p = packed_git; p; p = p->next) {
+	for (p = get_packed_git(); p; p = p->next) {
 		num = pack_revindex_ix(p);
 		num = - 1 - num;
 		pack_revindex[num].p = p;
diff --git a/server-info.c b/server-info.c
index 9ec744e..b7951ca 100644
--- a/server-info.c
+++ b/server-info.c
@@ -161,7 +161,7 @@ static void init_pack_info(const char *infofile, int force)
 	objdirlen = strlen(objdir);
 
 	prepare_packed_git();
-	for (p = packed_git; p; p = p->next) {
+	for (p = get_packed_git(); p; p = p->next) {
 		/* we ignore things on alternate path since they are
 		 * not available to the pullers in general.
 		 */
@@ -171,7 +171,7 @@ static void init_pack_info(const char *infofile, int force)
 	}
 	num_pack = i;
 	info = xcalloc(num_pack, sizeof(struct pack_info *));
-	for (i = 0, p = packed_git; p; p = p->next) {
+	for (i = 0, p = get_packed_git(); p; p = p->next) {
 		if (!p->pack_local)
 			continue;
 		info[i] = xcalloc(1, sizeof(struct pack_info));
diff --git a/sha1_file.c b/sha1_file.c
index 4f06a0e..4fd4e2c 100644
--- a/sha1_file.c
+++ b/sha1_file.c
@@ -33,6 +33,17 @@ static inline uintmax_t sz_fmt(size_t s) { return s; }
 
 const unsigned char null_sha1[20];
 
+static struct packed_git *packed_git_;
+struct packed_git *get_packed_git(void)
+{
+	return packed_git_;
+}
+void set_packed_git(struct packed_git *p)
+{
+	packed_git_ = p;
+}
+
+
 /*
  * This is meant to hold a *small* number of objects that you would
  * want read_sha1_file() to be able to return, but yet you do not want
@@ -618,7 +629,7 @@ static int unuse_one_window(struct packed_git *current, int keep_fd)
 
 	if (current)
 		scan_windows(current, &lru_p, &lru_w, &lru_l);
-	for (p = packed_git; p; p = p->next)
+	for (p = get_packed_git(); p; p = p->next)
 		scan_windows(p, &lru_p, &lru_w, &lru_l);
 	if (lru_p) {
 		munmap(lru_w->base, lru_w->len);
@@ -708,7 +719,7 @@ void close_pack_index(struct packed_git *p)
  */
 void free_pack_by_name(const char *pack_name)
 {
-	struct packed_git *p, **pp = &packed_git;
+	struct packed_git *p, **pp = &packed_git_;
 
 	while (*pp) {
 		p = *pp;
@@ -990,8 +1001,8 @@ void install_packed_git(struct packed_git *pack)
 	if (pack->pack_fd != -1)
 		pack_open_fds++;
 
-	pack->next = packed_git;
-	packed_git = pack;
+	pack->next = get_packed_git();
+	set_packed_git(pack);
 }
 
 static void prepare_packed_git_one(char *objdir, int local)
@@ -1026,7 +1037,7 @@ static void prepare_packed_git_one(char *objdir, int local)
 
 		/* Don't reopen a pack we already have. */
 		strcpy(path + len, de->d_name);
-		for (p = packed_git; p; p = p->next) {
+		for (p = get_packed_git(); p; p = p->next) {
 			if (!memcmp(path, p->pack_name, len + namelen - 4))
 				break;
 		}
@@ -1076,14 +1087,14 @@ static void rearrange_packed_git(void)
 	struct packed_git **ary, *p;
 	int i, n;
 
-	for (n = 0, p = packed_git; p; p = p->next)
+	for (n = 0, p = get_packed_git(); p; p = p->next)
 		n++;
 	if (n < 2)
 		return;
 
 	/* prepare an array of packed_git for easier sorting */
 	ary = xcalloc(n, sizeof(struct packed_git *));
-	for (n = 0, p = packed_git; p; p = p->next)
+	for (n = 0, p = get_packed_git(); p; p = p->next)
 		ary[n++] = p;
 
 	qsort(ary, n, sizeof(struct packed_git *), sort_pack);
@@ -1092,7 +1103,7 @@ static void rearrange_packed_git(void)
 	for (i = 0; i < n - 1; i++)
 		ary[i]->next = ary[i + 1];
 	ary[n - 1]->next = NULL;
-	packed_git = ary[0];
+	set_packed_git(ary[0]);
 
 	free(ary);
 }
@@ -1139,7 +1150,7 @@ static const struct packed_git *has_packed_and_bad(const unsigned char *sha1)
 	struct packed_git *p;
 	unsigned i;
 
-	for (p = packed_git; p; p = p->next)
+	for (p = get_packed_git(); p; p = p->next)
 		for (i = 0; i < p->num_bad_objects; i++)
 			if (!hashcmp(sha1, p->bad_object_sha1 + 20 * i))
 				return p;
@@ -2058,13 +2069,13 @@ static int find_pack_entry(const unsigned char *sha1, struct pack_entry *e)
 	struct packed_git *p;
 
 	prepare_packed_git();
-	if (!packed_git)
+	if (!get_packed_git())
 		return 0;
 
 	if (last_found_pack && fill_pack_entry(sha1, e, last_found_pack))
 		return 1;
 
-	for (p = packed_git; p; p = p->next) {
+	for (p = get_packed_git(); p; p = p->next) {
 		if (p == last_found_pack || !fill_pack_entry(sha1, e, p))
 			continue;
 
diff --git a/sha1_name.c b/sha1_name.c
index 03ffc2c..756b226 100644
--- a/sha1_name.c
+++ b/sha1_name.c
@@ -78,7 +78,7 @@ static int find_short_packed_object(int len, const unsigned char *match, unsigne
 	int found = 0;
 
 	prepare_packed_git();
-	for (p = packed_git; p && found < 2; p = p->next) {
+	for (p = get_packed_git(); p && found < 2; p = p->next) {
 		uint32_t num, last;
 		uint32_t first = 0;
 		open_pack_index(p);
-- 
1.7.8.36.g69ee2

[PATCH 2/5] sha1_file: stuff various pack reading variables into a struct

[Nguyễn Thái Ngọc Duy]

This requires any threads (including the main one) to call
init_pack_context() first. All pack data is per thread.

Original patch is written by Thomas Rast <trast@student.ethz.ch>

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 cache.h     |    1 +
 git.c       |    1 +
 sha1_file.c |  251 +++++++++++++++++++++++++++++++++++------------------------
 3 files changed, 152 insertions(+), 101 deletions(-)

diff --git a/cache.h b/cache.h
index 26d14b4..868ef48 100644
--- a/cache.h
+++ b/cache.h
@@ -997,6 +997,7 @@ struct packed_git {
 
 extern struct packed_git *get_packed_git(void);
 extern void set_packed_git(struct packed_git *);
+extern void init_pack_context(void);
 
 struct pack_entry {
 	off_t offset;
diff --git a/git.c b/git.c
index 3805616..7eee270 100644
--- a/git.c
+++ b/git.c
@@ -533,6 +533,7 @@ int main(int argc, const char **argv)
 	const char *cmd;
 
 	startup_info = &git_startup_info;
+	init_pack_context();
 
 	cmd = git_extract_argv0_path(argv[0]);
 	if (!cmd)
diff --git a/sha1_file.c b/sha1_file.c
index 4fd4e2c..170c0b1 100644
--- a/sha1_file.c
+++ b/sha1_file.c
@@ -33,16 +33,79 @@ static inline uintmax_t sz_fmt(size_t s) { return s; }
 
 const unsigned char null_sha1[20];
 
-static struct packed_git *packed_git_;
+#define MAX_DELTA_CACHE (256)
+
+struct delta_base_cache_lru_list {
+	struct delta_base_cache_lru_list *prev;
+	struct delta_base_cache_lru_list *next;
+};
+
+struct delta_base_cache_entry {
+	struct delta_base_cache_lru_list lru;
+	void *data;
+	struct packed_git *p;
+	off_t base_offset;
+	unsigned long size;
+	enum object_type type;
+};
+
+struct pack_context {
+	size_t delta_base_cached;
+	struct delta_base_cache_entry *delta_base_cache;
+	struct delta_base_cache_lru_list *delta_base_cache_lru;
+	struct packed_git *last_found_pack;
+
+	unsigned int pack_used_ctr;
+	unsigned int pack_mmap_calls;
+	unsigned int peak_pack_open_windows;
+	unsigned int pack_open_windows;
+	unsigned int pack_open_fds;
+	unsigned int pack_max_fds;
+	size_t peak_pack_mapped;
+	size_t pack_mapped;
+	struct packed_git *packed_git;
+	int prepare_packed_git_run_once;
+
+	char sha1_file_name_buf[PATH_MAX];
+	char *sha1_pack_name, *sha1_pack_base;
+	char *sha1_pack_index_name, *sha1_pack_index_base;
+};
+
+static pthread_key_t pack_key;
+struct pack_context *get_thread_pack_context(void)
+{
+	return pthread_getspecific(pack_key);
+}
+
 struct packed_git *get_packed_git(void)
 {
-	return packed_git_;
+	return get_thread_pack_context()->packed_git;
 }
 void set_packed_git(struct packed_git *p)
 {
-	packed_git_ = p;
+	get_thread_pack_context()->packed_git = p;
 }
 
+void init_pack_context(void)
+{
+	static int initialized = 0;
+	struct pack_context *ctx = xmalloc(sizeof(struct pack_context));
+
+	if (!initialized) {
+		pthread_key_create(&pack_key, NULL);
+		initialized = 1;
+	}
+
+	memset(ctx, 0, sizeof(*ctx));
+	ctx->delta_base_cached = 0;
+	ctx->delta_base_cache_lru = xmalloc(sizeof(struct delta_base_cache_lru_list));
+	ctx->delta_base_cache_lru->prev = ctx->delta_base_cache_lru;
+	ctx->delta_base_cache_lru->next = ctx->delta_base_cache_lru;
+	ctx->delta_base_cache = xcalloc(MAX_DELTA_CACHE, sizeof(struct delta_base_cache_entry));
+	ctx->last_found_pack = NULL;
+	ctx->packed_git = NULL;
+	pthread_setspecific(pack_key, ctx);
+}
 
 /*
  * This is meant to hold a *small* number of objects that you would
@@ -65,8 +128,6 @@ static struct cached_object empty_tree = {
 	0
 };
 
-static struct packed_git *last_found_pack;
-
 static struct cached_object *find_cached_object(const unsigned char *sha1)
 {
 	int i;
@@ -177,7 +238,7 @@ static void fill_sha1_path(char *pathbuf, const unsigned char *sha1)
  */
 char *sha1_file_name(const unsigned char *sha1)
 {
-	static char buf[PATH_MAX];
+	char *buf = get_thread_pack_context()->sha1_file_name_buf;
 	const char *objdir;
 	int len;
 
@@ -224,16 +285,14 @@ static char *sha1_get_pack_name(const unsigned char *sha1,
 
 char *sha1_pack_name(const unsigned char *sha1)
 {
-	static char *name, *base;
-
-	return sha1_get_pack_name(sha1, &name, &base, "pack");
+	struct pack_context *ctx = get_thread_pack_context();
+	return sha1_get_pack_name(sha1, &ctx->sha1_pack_name, &ctx->sha1_pack_base, "pack");
 }
 
 char *sha1_pack_index_name(const unsigned char *sha1)
 {
-	static char *name, *base;
-
-	return sha1_get_pack_name(sha1, &name, &base, "idx");
+	struct pack_context *ctx = get_thread_pack_context();
+	return sha1_get_pack_name(sha1, &ctx->sha1_pack_index_name, &ctx->sha1_pack_index_base, "idx");
 }
 
 struct alternate_object_database *alt_odb_list;
@@ -455,18 +514,10 @@ static int has_loose_object(const unsigned char *sha1)
 	       has_loose_object_nonlocal(sha1);
 }
 
-static unsigned int pack_used_ctr;
-static unsigned int pack_mmap_calls;
-static unsigned int peak_pack_open_windows;
-static unsigned int pack_open_windows;
-static unsigned int pack_open_fds;
-static unsigned int pack_max_fds;
-static size_t peak_pack_mapped;
-static size_t pack_mapped;
-struct packed_git *packed_git;
-
-void pack_report(void)
+void pack_report()
 {
+	struct pack_context *ctx = get_thread_pack_context();
+
 	fprintf(stderr,
 		"pack_report: getpagesize()            = %10" SZ_FMT "\n"
 		"pack_report: core.packedGitWindowSize = %10" SZ_FMT "\n"
@@ -480,10 +531,10 @@ void pack_report(void)
 		"pack_report: pack_open_windows        = %10u / %10u\n"
 		"pack_report: pack_mapped              = "
 			"%10" SZ_FMT " / %10" SZ_FMT "\n",
-		pack_used_ctr,
-		pack_mmap_calls,
-		pack_open_windows, peak_pack_open_windows,
-		sz_fmt(pack_mapped), sz_fmt(peak_pack_mapped));
+		ctx->pack_used_ctr,
+		ctx->pack_mmap_calls,
+		ctx->pack_open_windows, ctx->peak_pack_open_windows,
+		sz_fmt(ctx->pack_mapped), sz_fmt(ctx->peak_pack_mapped));
 }
 
 static int check_packed_git_idx(const char *path,  struct packed_git *p)
@@ -624,6 +675,7 @@ static void scan_windows(struct packed_git *p,
 
 static int unuse_one_window(struct packed_git *current, int keep_fd)
 {
+	struct pack_context *ctx = get_thread_pack_context();
 	struct packed_git *p, *lru_p = NULL;
 	struct pack_window *lru_w = NULL, *lru_l = NULL;
 
@@ -633,7 +685,7 @@ static int unuse_one_window(struct packed_git *current, int keep_fd)
 		scan_windows(p, &lru_p, &lru_w, &lru_l);
 	if (lru_p) {
 		munmap(lru_w->base, lru_w->len);
-		pack_mapped -= lru_w->len;
+		ctx->pack_mapped -= lru_w->len;
 		if (lru_l)
 			lru_l->next = lru_w->next;
 		else {
@@ -641,12 +693,12 @@ static int unuse_one_window(struct packed_git *current, int keep_fd)
 			if (!lru_p->windows && lru_p->pack_fd != -1
 				&& lru_p->pack_fd != keep_fd) {
 				close(lru_p->pack_fd);
-				pack_open_fds--;
+				ctx->pack_open_fds--;
 				lru_p->pack_fd = -1;
 			}
 		}
 		free(lru_w);
-		pack_open_windows--;
+		ctx->pack_open_windows--;
 		return 1;
 	}
 	return 0;
@@ -654,8 +706,9 @@ static int unuse_one_window(struct packed_git *current, int keep_fd)
 
 void release_pack_memory(size_t need, int fd)
 {
-	size_t cur = pack_mapped;
-	while (need >= (cur - pack_mapped) && unuse_one_window(NULL, fd))
+	struct pack_context *ctx = get_thread_pack_context();
+	size_t cur = ctx->pack_mapped;
+	while (need >= (cur - ctx->pack_mapped) && unuse_one_window(NULL, fd))
 		; /* nothing */
 }
 
@@ -676,6 +729,7 @@ void *xmmap(void *start, size_t length,
 
 void close_pack_windows(struct packed_git *p)
 {
+	struct pack_context *ctx = get_thread_pack_context();
 	while (p->windows) {
 		struct pack_window *w = p->windows;
 
@@ -683,8 +737,8 @@ void close_pack_windows(struct packed_git *p)
 			die("pack '%s' still has open windows to it",
 			    p->pack_name);
 		munmap(w->base, w->len);
-		pack_mapped -= w->len;
-		pack_open_windows--;
+		ctx->pack_mapped -= w->len;
+		ctx->pack_open_windows--;
 		p->windows = w->next;
 		free(w);
 	}
@@ -719,7 +773,8 @@ void close_pack_index(struct packed_git *p)
  */
 void free_pack_by_name(const char *pack_name)
 {
-	struct packed_git *p, **pp = &packed_git_;
+	struct pack_context *ctx = get_thread_pack_context();
+	struct packed_git *p, **pp = &ctx->packed_git;
 
 	while (*pp) {
 		p = *pp;
@@ -728,13 +783,13 @@ void free_pack_by_name(const char *pack_name)
 			close_pack_windows(p);
 			if (p->pack_fd != -1) {
 				close(p->pack_fd);
-				pack_open_fds--;
+				ctx->pack_open_fds--;
 			}
 			close_pack_index(p);
 			free(p->bad_object_sha1);
 			*pp = p->next;
-			if (last_found_pack == p)
-				last_found_pack = NULL;
+			if (ctx->last_found_pack == p)
+				ctx->last_found_pack = NULL;
 			free(p);
 			return;
 		}
@@ -748,6 +803,7 @@ void free_pack_by_name(const char *pack_name)
  */
 static int open_packed_git_1(struct packed_git *p)
 {
+	struct pack_context *ctx = get_thread_pack_context();
 	struct stat st;
 	struct pack_header hdr;
 	unsigned char sha1[20];
@@ -757,7 +813,7 @@ static int open_packed_git_1(struct packed_git *p)
 	if (!p->index_data && open_pack_index(p))
 		return error("packfile %s index unavailable", p->pack_name);
 
-	if (!pack_max_fds) {
+	if (!ctx->pack_max_fds) {
 		struct rlimit lim;
 		unsigned int max_fds;
 
@@ -768,18 +824,18 @@ static int open_packed_git_1(struct packed_git *p)
 
 		/* Save 3 for stdin/stdout/stderr, 22 for work */
 		if (25 < max_fds)
-			pack_max_fds = max_fds - 25;
+			ctx->pack_max_fds = max_fds - 25;
 		else
-			pack_max_fds = 1;
+			ctx->pack_max_fds = 1;
 	}
 
-	while (pack_max_fds <= pack_open_fds && unuse_one_window(NULL, -1))
+	while (ctx->pack_max_fds <= ctx->pack_open_fds && unuse_one_window(NULL, -1))
 		; /* nothing */
 
 	p->pack_fd = git_open_noatime(p->pack_name);
 	if (p->pack_fd < 0 || fstat(p->pack_fd, &st))
 		return -1;
-	pack_open_fds++;
+	ctx->pack_open_fds++;
 
 	/* If we created the struct before we had the pack we lack size. */
 	if (!p->pack_size) {
@@ -827,11 +883,12 @@ static int open_packed_git_1(struct packed_git *p)
 
 static int open_packed_git(struct packed_git *p)
 {
+	struct pack_context *ctx = get_thread_pack_context();
 	if (!open_packed_git_1(p))
 		return 0;
 	if (p->pack_fd != -1) {
 		close(p->pack_fd);
-		pack_open_fds--;
+		ctx->pack_open_fds--;
 		p->pack_fd = -1;
 	}
 	return -1;
@@ -855,6 +912,7 @@ unsigned char *use_pack(struct packed_git *p,
 		off_t offset,
 		unsigned long *left)
 {
+	struct pack_context *ctx = get_thread_pack_context();
 	struct pack_window *win = *w_cursor;
 
 	/* Since packfiles end in a hash of their content and it's
@@ -887,8 +945,8 @@ unsigned char *use_pack(struct packed_git *p,
 			if (len > packed_git_window_size)
 				len = packed_git_window_size;
 			win->len = (size_t)len;
-			pack_mapped += win->len;
-			while (packed_git_limit < pack_mapped
+			ctx->pack_mapped += win->len;
+			while (packed_git_limit < ctx->pack_mapped
 				&& unuse_one_window(p, p->pack_fd))
 				; /* nothing */
 			win->base = xmmap(NULL, win->len,
@@ -901,21 +959,21 @@ unsigned char *use_pack(struct packed_git *p,
 			if (!win->offset && win->len == p->pack_size
 				&& !p->do_not_close) {
 				close(p->pack_fd);
-				pack_open_fds--;
+				ctx->pack_open_fds--;
 				p->pack_fd = -1;
 			}
-			pack_mmap_calls++;
-			pack_open_windows++;
-			if (pack_mapped > peak_pack_mapped)
-				peak_pack_mapped = pack_mapped;
-			if (pack_open_windows > peak_pack_open_windows)
-				peak_pack_open_windows = pack_open_windows;
+			ctx->pack_mmap_calls++;
+			ctx->pack_open_windows++;
+			if (ctx->pack_mapped > ctx->peak_pack_mapped)
+				ctx->peak_pack_mapped = ctx->pack_mapped;
+			if (ctx->pack_open_windows > ctx->peak_pack_open_windows)
+				ctx->peak_pack_open_windows = ctx->pack_open_windows;
 			win->next = p->windows;
 			p->windows = win;
 		}
 	}
 	if (win != *w_cursor) {
-		win->last_used = pack_used_ctr++;
+		win->last_used = ctx->pack_used_ctr++;
 		win->inuse_cnt++;
 		*w_cursor = win;
 	}
@@ -998,8 +1056,9 @@ struct packed_git *parse_pack_index(unsigned char *sha1, const char *idx_path)
 
 void install_packed_git(struct packed_git *pack)
 {
+	struct pack_context *ctx = get_thread_pack_context();
 	if (pack->pack_fd != -1)
-		pack_open_fds++;
+		ctx->pack_open_fds++;
 
 	pack->next = get_packed_git();
 	set_packed_git(pack);
@@ -1108,12 +1167,12 @@ static void rearrange_packed_git(void)
 	free(ary);
 }
 
-static int prepare_packed_git_run_once = 0;
 void prepare_packed_git(void)
 {
 	struct alternate_object_database *alt;
+	struct pack_context *ctx = get_thread_pack_context();
 
-	if (prepare_packed_git_run_once)
+	if (ctx->prepare_packed_git_run_once)
 		return;
 	prepare_packed_git_one(get_object_directory(), 1);
 	prepare_alt_odb();
@@ -1123,13 +1182,14 @@ void prepare_packed_git(void)
 		alt->name[-1] = '/';
 	}
 	rearrange_packed_git();
-	prepare_packed_git_run_once = 1;
+	ctx->prepare_packed_git_run_once = 1;
 }
 
 void reprepare_packed_git(void)
 {
+	struct pack_context *ctx = get_thread_pack_context();
 	discard_revindex();
-	prepare_packed_git_run_once = 0;
+	ctx->prepare_packed_git_run_once = 0;
 	prepare_packed_git();
 }
 
@@ -1664,24 +1724,6 @@ static void *unpack_compressed_entry(struct packed_git *p,
 	return buffer;
 }
 
-#define MAX_DELTA_CACHE (256)
-
-static size_t delta_base_cached;
-
-static struct delta_base_cache_lru_list {
-	struct delta_base_cache_lru_list *prev;
-	struct delta_base_cache_lru_list *next;
-} delta_base_cache_lru = { &delta_base_cache_lru, &delta_base_cache_lru };
-
-static struct delta_base_cache_entry {
-	struct delta_base_cache_lru_list lru;
-	void *data;
-	struct packed_git *p;
-	off_t base_offset;
-	unsigned long size;
-	enum object_type type;
-} delta_base_cache[MAX_DELTA_CACHE];
-
 static unsigned long pack_entry_hash(struct packed_git *p, off_t base_offset)
 {
 	unsigned long hash;
@@ -1694,7 +1736,8 @@ static unsigned long pack_entry_hash(struct packed_git *p, off_t base_offset)
 static int in_delta_base_cache(struct packed_git *p, off_t base_offset)
 {
 	unsigned long hash = pack_entry_hash(p, base_offset);
-	struct delta_base_cache_entry *ent = delta_base_cache + hash;
+	struct delta_base_cache_entry *ent
+		= get_thread_pack_context()->delta_base_cache + hash;
 	return (ent->data && ent->p == p && ent->base_offset == base_offset);
 }
 
@@ -1703,7 +1746,8 @@ static void *cache_or_unpack_entry(struct packed_git *p, off_t base_offset,
 {
 	void *ret;
 	unsigned long hash = pack_entry_hash(p, base_offset);
-	struct delta_base_cache_entry *ent = delta_base_cache + hash;
+	struct pack_context *ctx = get_thread_pack_context();
+	struct delta_base_cache_entry *ent = ctx->delta_base_cache + hash;
 
 	ret = ent->data;
 	if (!ret || ent->p != p || ent->base_offset != base_offset)
@@ -1713,7 +1757,7 @@ static void *cache_or_unpack_entry(struct packed_git *p, off_t base_offset,
 		ent->data = NULL;
 		ent->lru.next->prev = ent->lru.prev;
 		ent->lru.prev->next = ent->lru.next;
-		delta_base_cached -= ent->size;
+		ctx->delta_base_cached -= ent->size;
 	} else {
 		ret = xmemdupz(ent->data, ent->size);
 	}
@@ -1722,48 +1766,52 @@ static void *cache_or_unpack_entry(struct packed_git *p, off_t base_offset,
 	return ret;
 }
 
-static inline void release_delta_base_cache(struct delta_base_cache_entry *ent)
+static inline void release_delta_base_cache(struct pack_context *ctx,
+					    struct delta_base_cache_entry *ent)
 {
 	if (ent->data) {
 		free(ent->data);
 		ent->data = NULL;
 		ent->lru.next->prev = ent->lru.prev;
 		ent->lru.prev->next = ent->lru.next;
-		delta_base_cached -= ent->size;
+		ctx->delta_base_cached -= ent->size;
 	}
 }
 
 void clear_delta_base_cache(void)
 {
 	unsigned long p;
+	struct pack_context *ctx = get_thread_pack_context();
+	struct delta_base_cache_entry *delta_base_cache = ctx->delta_base_cache;
 	for (p = 0; p < MAX_DELTA_CACHE; p++)
-		release_delta_base_cache(&delta_base_cache[p]);
+		release_delta_base_cache(ctx, &delta_base_cache[p]);
 }
 
 static void add_delta_base_cache(struct packed_git *p, off_t base_offset,
 	void *base, unsigned long base_size, enum object_type type)
 {
 	unsigned long hash = pack_entry_hash(p, base_offset);
-	struct delta_base_cache_entry *ent = delta_base_cache + hash;
+	struct pack_context *ctx = get_thread_pack_context();
+	struct delta_base_cache_entry *ent = ctx->delta_base_cache + hash;
 	struct delta_base_cache_lru_list *lru;
 
-	release_delta_base_cache(ent);
-	delta_base_cached += base_size;
+	release_delta_base_cache(ctx, ent);
+	ctx->delta_base_cached += base_size;
 
-	for (lru = delta_base_cache_lru.next;
-	     delta_base_cached > delta_base_cache_limit
-	     && lru != &delta_base_cache_lru;
+	for (lru = ctx->delta_base_cache_lru->next;
+	     ctx->delta_base_cached > delta_base_cache_limit
+	     && lru != ctx->delta_base_cache_lru;
 	     lru = lru->next) {
 		struct delta_base_cache_entry *f = (void *)lru;
 		if (f->type == OBJ_BLOB)
-			release_delta_base_cache(f);
+			release_delta_base_cache(ctx, f);
 	}
-	for (lru = delta_base_cache_lru.next;
-	     delta_base_cached > delta_base_cache_limit
-	     && lru != &delta_base_cache_lru;
+	for (lru = ctx->delta_base_cache_lru->next;
+	     ctx->delta_base_cached > delta_base_cache_limit
+	     && lru != ctx->delta_base_cache_lru;
 	     lru = lru->next) {
 		struct delta_base_cache_entry *f = (void *)lru;
-		release_delta_base_cache(f);
+		release_delta_base_cache(ctx, f);
 	}
 
 	ent->p = p;
@@ -1771,10 +1819,10 @@ static void add_delta_base_cache(struct packed_git *p, off_t base_offset,
 	ent->type = type;
 	ent->data = base;
 	ent->size = base_size;
-	ent->lru.next = &delta_base_cache_lru;
-	ent->lru.prev = delta_base_cache_lru.prev;
-	delta_base_cache_lru.prev->next = &ent->lru;
-	delta_base_cache_lru.prev = &ent->lru;
+	ent->lru.next = ctx->delta_base_cache_lru;
+	ent->lru.prev = ctx->delta_base_cache_lru->prev;
+	ctx->delta_base_cache_lru->prev->next = &ent->lru;
+	ctx->delta_base_cache_lru->prev = &ent->lru;
 }
 
 static void *read_object(const unsigned char *sha1, enum object_type *type,
@@ -2066,20 +2114,21 @@ static int fill_pack_entry(const unsigned char *sha1,
 
 static int find_pack_entry(const unsigned char *sha1, struct pack_entry *e)
 {
+	struct pack_context *ctx = get_thread_pack_context();
 	struct packed_git *p;
 
 	prepare_packed_git();
 	if (!get_packed_git())
 		return 0;
 
-	if (last_found_pack && fill_pack_entry(sha1, e, last_found_pack))
+	if (ctx->last_found_pack && fill_pack_entry(sha1, e, ctx->last_found_pack))
 		return 1;
 
 	for (p = get_packed_git(); p; p = p->next) {
-		if (p == last_found_pack || !fill_pack_entry(sha1, e, p))
+		if (p == ctx->last_found_pack || !fill_pack_entry(sha1, e, p))
 			continue;
 
-		last_found_pack = p;
+		ctx->last_found_pack = p;
 		return 1;
 	}
 	return 0;
-- 
1.7.8.36.g69ee2

[PATCH 3/5] Make lookup_*() functions thread-safe

[Nguyễn Thái Ngọc Duy]

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 blob.c         |   11 +++++++++--
 commit.c       |   12 +++++++++---
 list-objects.c |    2 ++
 object.c       |    9 ++++++++-
 object.h       |    6 ++++++
 tag.c          |    9 +++++++--
 tree.c         |   18 ++++++++++++++----
 7 files changed, 55 insertions(+), 12 deletions(-)

diff --git a/blob.c b/blob.c
index ae320bd..606e2be 100644
--- a/blob.c
+++ b/blob.c
@@ -6,8 +6,13 @@ const char *blob_type = "blob";
 struct blob *lookup_blob(const unsigned char *sha1)
 {
 	struct object *obj = lookup_object(sha1);
-	if (!obj)
-		return create_object(sha1, OBJ_BLOB, alloc_blob_node());
+	LOCK();
+	if (!obj) {
+		obj = create_object(sha1, OBJ_BLOB, alloc_blob_node());
+		UNLOCK();
+		return obj;
+	}
+	UNLOCK();
 	if (!obj->type)
 		obj->type = OBJ_BLOB;
 	if (obj->type != OBJ_BLOB) {
@@ -20,6 +25,8 @@ struct blob *lookup_blob(const unsigned char *sha1)
 
 int parse_blob_buffer(struct blob *item, void *buffer, unsigned long size)
 {
+	LOCK();
 	item->object.parsed = 1;
+	UNLOCK();
 	return 0;
 }
diff --git a/commit.c b/commit.c
index 4b39c19..f84152c 100644
--- a/commit.c
+++ b/commit.c
@@ -54,9 +54,15 @@ struct commit *lookup_commit_or_die(const unsigned char *sha1, const char *ref_n
 
 struct commit *lookup_commit(const unsigned char *sha1)
 {
-	struct object *obj = lookup_object(sha1);
-	if (!obj)
-		return create_object(sha1, OBJ_COMMIT, alloc_commit_node());
+	struct object *obj;
+	LOCK();
+	obj = lookup_object(sha1);
+	if (!obj) {
+		obj = create_object(sha1, OBJ_COMMIT, alloc_commit_node());
+		UNLOCK();
+		return (struct commit*)obj;
+	}
+	UNLOCK();
 	if (!obj->type)
 		obj->type = OBJ_COMMIT;
 	return check_commit(obj, sha1, 0);
diff --git a/list-objects.c b/list-objects.c
index 3dd4a96..2605b63 100644
--- a/list-objects.c
+++ b/list-objects.c
@@ -123,8 +123,10 @@ static void process_tree(struct rev_info *revs,
 				     cb_data);
 	}
 	strbuf_setlen(base, baselen);
+	LOCK();
 	free(tree->buffer);
 	tree->buffer = NULL;
+	UNLOCK();
 }
 
 static void mark_edge_parents_uninteresting(struct commit *commit,
diff --git a/object.c b/object.c
index 6b06297..05fb91f 100644
--- a/object.c
+++ b/object.c
@@ -8,6 +8,9 @@
 static struct object **obj_hash;
 static int nr_objs, obj_hash_size;
 
+int multithread_object_access;
+pthread_mutex_t mtx;
+
 unsigned int get_max_object_index(void)
 {
 	return obj_hash_size;
@@ -126,9 +129,13 @@ void *create_object(const unsigned char *sha1, int type, void *o)
 
 struct object *lookup_unknown_object(const unsigned char *sha1)
 {
-	struct object *obj = lookup_object(sha1);
+	struct object *obj;
+
+	LOCK();
+	obj = lookup_object(sha1);
 	if (!obj)
 		obj = create_object(sha1, OBJ_NONE, alloc_object_node());
+	UNLOCK();
 	return obj;
 }
 
diff --git a/object.h b/object.h
index b6618d9..17c7c65 100644
--- a/object.h
+++ b/object.h
@@ -32,6 +32,12 @@ struct object {
 	unsigned char sha1[20];
 };
 
+extern int multithread_object_access;
+extern pthread_mutex_t mtx;
+
+#define LOCK() { if (multithread_object_access) pthread_mutex_lock(&mtx); }
+#define UNLOCK() { if (multithread_object_access) pthread_mutex_unlock(&mtx); }
+
 extern const char *typename(unsigned int type);
 extern int type_from_string(const char *str);
 
diff --git a/tag.c b/tag.c
index 78d272b..4f16c5b 100644
--- a/tag.c
+++ b/tag.c
@@ -39,8 +39,13 @@ struct object *deref_tag_noverify(struct object *o)
 struct tag *lookup_tag(const unsigned char *sha1)
 {
 	struct object *obj = lookup_object(sha1);
-	if (!obj)
-		return create_object(sha1, OBJ_TAG, alloc_tag_node());
+	LOCK();
+	if (!obj) {
+		obj = create_object(sha1, OBJ_TAG, alloc_tag_node());
+		UNLOCK();
+		return obj;
+	}
+	UNLOCK();
 	if (!obj->type)
 		obj->type = OBJ_TAG;
 	if (obj->type != OBJ_TAG) {
diff --git a/tree.c b/tree.c
index 676e9f7..6d3c6a2 100644
--- a/tree.c
+++ b/tree.c
@@ -180,9 +180,15 @@ int read_tree(struct tree *tree, int stage, struct pathspec *match)
 
 struct tree *lookup_tree(const unsigned char *sha1)
 {
-	struct object *obj = lookup_object(sha1);
-	if (!obj)
-		return create_object(sha1, OBJ_TREE, alloc_tree_node());
+	struct object *obj;
+	LOCK();
+	obj = lookup_object(sha1);
+	if (!obj) {
+		obj = create_object(sha1, OBJ_TREE, alloc_tree_node());
+		UNLOCK();
+		return obj;
+	}
+	UNLOCK();
 	if (!obj->type)
 		obj->type = OBJ_TREE;
 	if (obj->type != OBJ_TREE) {
@@ -195,11 +201,15 @@ struct tree *lookup_tree(const unsigned char *sha1)
 
 int parse_tree_buffer(struct tree *item, void *buffer, unsigned long size)
 {
-	if (item->object.parsed)
+	LOCK();
+	if (item->object.parsed) {
+		UNLOCK();
 		return 0;
+	}
 	item->object.parsed = 1;
 	item->buffer = buffer;
 	item->size = size;
+	UNLOCK();
 
 	return 0;
 }
-- 
1.7.8.36.g69ee2

[PATCH 4/5] Teach traverse_commit_list callsites about new parameter, nr_threads

[Nguyễn Thái Ngọc Duy]

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 builtin/pack-objects.c |    2 +-
 builtin/rev-list.c     |    4 ++--
 list-objects.c         |    2 +-
 list-objects.h         |    2 +-
 upload-pack.c          |    2 +-
 5 files changed, 6 insertions(+), 6 deletions(-)

diff --git a/builtin/pack-objects.c b/builtin/pack-objects.c
index 2f242c4..0702cd1 100644
--- a/builtin/pack-objects.c
+++ b/builtin/pack-objects.c
@@ -2292,7 +2292,7 @@ static void get_object_list(int ac, const char **av)
 	if (prepare_revision_walk(&revs))
 		die("revision walk setup failed");
 	mark_edges_uninteresting(revs.commits, &revs, show_edge);
-	traverse_commit_list(&revs, show_commit, show_object, NULL);
+	traverse_commit_list(&revs, show_commit, show_object, NULL, 0);
 
 	if (keep_unreachable)
 		add_objects_in_unpacked_packs(&revs);
diff --git a/builtin/rev-list.c b/builtin/rev-list.c
index 4c4d404..e720561 100644
--- a/builtin/rev-list.c
+++ b/builtin/rev-list.c
@@ -290,7 +290,7 @@ static int show_bisect_vars(struct rev_list_info *info, int reaches, int all)
 		strcpy(hex, sha1_to_hex(revs->commits->item->object.sha1));
 
 	if (flags & BISECT_SHOW_ALL) {
-		traverse_commit_list(revs, show_commit, show_object, info);
+		traverse_commit_list(revs, show_commit, show_object, info, 0);
 		printf("------\n");
 	}
 
@@ -395,7 +395,7 @@ int cmd_rev_list(int argc, const char **argv, const char *prefix)
 			return show_bisect_vars(&info, reaches, all);
 	}
 
-	traverse_commit_list(&revs, show_commit, show_object, &info);
+	traverse_commit_list(&revs, show_commit, show_object, &info, 0);
 
 	if (revs.count) {
 		if (revs.left_right && revs.cherry_mark)
diff --git a/list-objects.c b/list-objects.c
index 2605b63..4f365e8 100644
--- a/list-objects.c
+++ b/list-objects.c
@@ -170,7 +170,7 @@ static void add_pending_tree(struct rev_info *revs, struct tree *tree)
 void traverse_commit_list(struct rev_info *revs,
 			  show_commit_fn show_commit,
 			  show_object_fn show_object,
-			  void *data)
+			  void *data, int nr_threads_)
 {
 	int i;
 	struct commit *commit;
diff --git a/list-objects.h b/list-objects.h
index 3db7bb6..aa604ba 100644
--- a/list-objects.h
+++ b/list-objects.h
@@ -3,7 +3,7 @@
 
 typedef void (*show_commit_fn)(struct commit *, void *);
 typedef void (*show_object_fn)(struct object *, const struct name_path *, const char *, void *);
-void traverse_commit_list(struct rev_info *, show_commit_fn, show_object_fn, void *);
+void traverse_commit_list(struct rev_info *, show_commit_fn, show_object_fn, void *, int);
 
 typedef void (*show_edge_fn)(struct commit *);
 void mark_edges_uninteresting(struct commit_list *, struct rev_info *, show_edge_fn);
diff --git a/upload-pack.c b/upload-pack.c
index bb08e2e..698f966 100644
--- a/upload-pack.c
+++ b/upload-pack.c
@@ -128,7 +128,7 @@ static int do_rev_list(int in, int out, void *user_data)
 		for (i = 0; i < extra_edge_obj.nr; i++)
 			fprintf(pack_pipe, "-%s\n", sha1_to_hex(
 					extra_edge_obj.objects[i].item->sha1));
-	traverse_commit_list(&revs, show_commit, show_object, NULL);
+	traverse_commit_list(&revs, show_commit, show_object, NULL, 0);
 	fflush(pack_pipe);
 	fclose(pack_pipe);
 	return 0;
-- 
1.7.8.36.g69ee2

[PATCH 5/5] Support multithread in traverse_commit_list and rev-list

[Nguyễn Thái Ngọc Duy]

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 builtin/rev-list.c |    3 +-
 list-objects.c     |  153 +++++++++++++++++++++++++++++++++++++++++++++++++--
 revision.c         |   16 ++++++
 revision.h         |    2 +
 4 files changed, 167 insertions(+), 7 deletions(-)

diff --git a/builtin/rev-list.c b/builtin/rev-list.c
index e720561..e07ba40 100644
--- a/builtin/rev-list.c
+++ b/builtin/rev-list.c
@@ -395,7 +395,8 @@ int cmd_rev_list(int argc, const char **argv, const char *prefix)
 			return show_bisect_vars(&info, reaches, all);
 	}
 
-	traverse_commit_list(&revs, show_commit, show_object, &info, 0);
+	traverse_commit_list(&revs, show_commit, show_object, &info,
+			     getenv("REV_LIST") ? 2 : 0);
 
 	if (revs.count) {
 		if (revs.left_right && revs.cherry_mark)
diff --git a/list-objects.c b/list-objects.c
index 4f365e8..59a7c33 100644
--- a/list-objects.c
+++ b/list-objects.c
@@ -7,6 +7,29 @@
 #include "tree-walk.h"
 #include "revision.h"
 #include "list-objects.h"
+#include "semaphore.h"
+
+struct thread_data {
+	pthread_t thread;
+	pthread_mutex_t mutex;
+	sem_t sem;
+
+	struct rev_info *revs;
+	struct tree *tree;
+	show_object_fn show;
+	struct name_path *path;
+	struct strbuf base;
+	const char *name;
+	void *cb_data;
+};
+
+static struct thread_data *threads;
+static int nr_threads;
+static pthread_mutex_t obj_lock;
+static int done;
+
+#define LOCK_OBJ() { if (nr_threads) pthread_mutex_lock(&obj_lock); }
+#define UNLOCK_OBJ() { if (nr_threads) pthread_mutex_unlock(&obj_lock); }
 
 static void process_blob(struct rev_info *revs,
 			 struct blob *blob,
@@ -21,10 +44,14 @@ static void process_blob(struct rev_info *revs,
 		return;
 	if (!obj)
 		die("bad blob object");
-	if (obj->flags & (UNINTERESTING | SEEN))
+	LOCK_OBJ();
+	if (obj->flags & (UNINTERESTING | SEEN)) {
+		UNLOCK_OBJ();
 		return;
+	}
 	obj->flags |= SEEN;
 	show(obj, path, name, cb_data);
+	UNLOCK_OBJ();
 }
 
 /*
@@ -79,12 +106,20 @@ static void process_tree(struct rev_info *revs,
 		return;
 	if (!obj)
 		die("bad tree object");
-	if (obj->flags & (UNINTERESTING | SEEN))
+
+	LOCK_OBJ();
+	if (obj->flags & (UNINTERESTING | SEEN)) {
+		UNLOCK_OBJ();
 		return;
+	}
+	obj->flags |= SEEN;
+	UNLOCK_OBJ();
 	if (parse_tree(tree) < 0)
 		die("bad tree object %s", sha1_to_hex(obj->sha1));
-	obj->flags |= SEEN;
+	LOCK_OBJ();
 	show(obj, path, name, cb_data);
+	UNLOCK_OBJ();
+
 	me.up = path;
 	me.elem = name;
 	me.elem_len = strlen(name);
@@ -167,6 +202,80 @@ static void add_pending_tree(struct rev_info *revs, struct tree *tree)
 	add_pending_object(revs, &tree->object, "");
 }
 
+static void *woodchipper(void *arg)
+{
+	struct thread_data *data = arg;
+	struct tree *tree;
+
+	init_pack_context();
+
+	while (!done) {
+		pthread_mutex_lock(&data->mutex);
+		tree = data->tree;
+		pthread_mutex_unlock(&data->mutex);
+		if (!tree) {
+			sem_wait(&data->sem);
+			continue;
+		}
+
+		process_tree(data->revs, tree, data->show, data->path,
+			     &data->base, data->name, data->cb_data);
+		free(data->path);
+		strbuf_reset(&data->base);
+
+		pthread_mutex_lock(&data->mutex);
+		data->tree = NULL;
+		pthread_mutex_unlock(&data->mutex);
+
+		sem_wait(&data->sem);
+	}
+	return NULL;
+}
+
+static void distribute_tree(struct rev_info *revs,
+			    struct tree *tree,
+			    show_object_fn show,
+			    struct name_path *path,
+			    struct strbuf *base,
+			    const char *name,
+			    void *cb_data)
+{
+	int i = 0;
+
+	while (nr_threads && i < nr_threads) {
+		struct tree *old_tree;
+		struct thread_data *thr = threads + i;
+		pthread_mutex_lock(&thr->mutex);
+		old_tree = thr->tree;
+		pthread_mutex_unlock(&thr->mutex);
+#if 0
+		if (old_tree) {
+			i = (i + 1) % nr_threads;
+			sched_yield();
+			continue;
+		}
+#else
+		if (old_tree) {
+			i++;
+			continue;
+		}
+#endif
+
+		/* the thread must be asleep, or going to sleep by now */
+		thr->revs = revs;
+		thr->tree = tree;
+		thr->show = show;
+		thr->path = dup_name_path(path);
+		strbuf_addbuf(&thr->base, base);
+		thr->name = name;
+		thr->cb_data = cb_data;
+		sem_post(&thr->sem);
+		return;
+	}
+
+	process_tree(revs, tree, show, path, base, name, cb_data);
+}
+
 void traverse_commit_list(struct rev_info *revs,
 			  show_commit_fn show_commit,
 			  show_object_fn show_object,
@@ -186,20 +295,45 @@ void traverse_commit_list(struct rev_info *revs,
 			add_pending_tree(revs, commit->tree);
 		show_commit(commit, data);
 	}
+
+	nr_threads = nr_threads_;
+	if (nr_threads) {
+		threads = xmalloc((sizeof*threads) * nr_threads);
+		memset(threads, 0, sizeof(*threads) * nr_threads);
+		pthread_mutex_init(&obj_lock, NULL);
+		done = 0;
+		for (i = 0; i < nr_threads; i++) {
+			threads[i].tree = NULL;
+			strbuf_init(&threads[i].base, PATH_MAX);
+			pthread_mutex_init(&threads[i].mutex, NULL);
+			sem_init(&threads[i].sem, 0, 0);
+			pthread_create(&threads[i].thread, NULL, woodchipper, threads + i);
+		}
+
+		pthread_mutex_init(&mtx, NULL);
+		multithread_object_access = 1;
+	}
+
 	for (i = 0; i < revs->pending.nr; i++) {
 		struct object_array_entry *pending = revs->pending.objects + i;
 		struct object *obj = pending->item;
 		const char *name = pending->name;
-		if (obj->flags & (UNINTERESTING | SEEN))
+		LOCK_OBJ();
+		if (obj->flags & (UNINTERESTING | SEEN)) {
+			UNLOCK_OBJ();
 			continue;
+		}
+		UNLOCK_OBJ();
 		if (obj->type == OBJ_TAG) {
+			LOCK_OBJ();
 			obj->flags |= SEEN;
 			show_object(obj, NULL, name, data);
+			UNLOCK_OBJ();
 			continue;
 		}
 		if (obj->type == OBJ_TREE) {
-			process_tree(revs, (struct tree *)obj, show_object,
-				     NULL, &base, name, data);
+			distribute_tree(revs, (struct tree *)obj, show_object,
+					NULL, &base, name, data);
 			continue;
 		}
 		if (obj->type == OBJ_BLOB) {
@@ -210,6 +344,13 @@ void traverse_commit_list(struct rev_info *revs,
 		die("unknown pending object %s (%s)",
 		    sha1_to_hex(obj->sha1), name);
 	}
+	if (nr_threads) {
+		done = 1;
+		for (i = 0; i < nr_threads; i++) {
+			sem_post(&threads[i].sem);
+			pthread_join(threads[i].thread, NULL);
+		}
+	}
 	if (revs->pending.nr) {
 		free(revs->pending.objects);
 		revs->pending.nr = 0;
diff --git a/revision.c b/revision.c
index b3554ed..40b6e15 100644
--- a/revision.c
+++ b/revision.c
@@ -40,6 +40,22 @@ char *path_name(const struct name_path *path, const char *name)
 	return n;
 }
 
+struct name_path *dup_name_path(const struct name_path *path)
+{
+	const struct name_path *src;
+	struct name_path *dup, *dst;
+	int len;
+	for (len = 0, src = path; src; src = src->up)
+		len++;
+	dup = xmalloc(sizeof(*dup) * len);
+	for (src = path, dst = dup; src; src = src->up, dst++) {
+		memcpy(dst, src, sizeof(*src));
+		if (dst > dup)
+			dst[-1].up = dst;
+	}
+	return dup;
+}
+
 static int show_path_component_truncated(FILE *out, const char *name, int len)
 {
 	int cnt;
diff --git a/revision.h b/revision.h
index b8e9223..0da4636 100644
--- a/revision.h
+++ b/revision.h
@@ -208,6 +208,8 @@ struct name_path {
 
 char *path_name(const struct name_path *path, const char *name);
 
+struct name_path *dup_name_path(const struct name_path *);
+
 extern void show_object_with_name(FILE *, struct object *, const struct name_path *, const char *);
 
 extern void add_object(struct object *obj,
-- 
1.7.8.36.g69ee2

Re: [PATCH 0/5] multithread traverse_commit_list (aka rev-list)

[Martin Fick]

On Tuesday, April 10, 2012 08:39:26 am Nguyễn Thái Ngọc Duy 
wrote:
> While this series does not break rev-list (but breaks all
> external commands, I don't care anyway), and it proves
> lock-free pack access works, it does not improve
> rev-list performance. I suspect extensive locking around
> "struct object *" may be the culprit.  

Or if it is memory contention and your threads share the 
same cache, it won't help much either,

-Martin

-- 
Employee of Qualcomm Innovation Center, Inc. which is a 
member of Code Aurora Forum