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

["Nguyễn Thái Ngọc Duy" <pclouds@gmail.com>]

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