"GOT", but the "O" is a cute, smiling pufferfish. Index | Thread | Search

From:
Stefan Sperling <stsp@stsp.name>
Subject:
faster history traversal for 'got blame'
To:
gameoftrees@openbsd.org
Date:
Mon, 6 Jan 2020 17:57:56 +0100

Download raw body.

Thread
This non-trivial patch adds history traversal support to got-read-pack.
The goal is to speed up 'got blame'.

Commits which do not change the blamed file do not need to be sent
to the main process. Instead got-read-pack can send a list of commit
IDs it has already traversed, followed by the final commit it found.
This is sufficient for the commit graph to detect duplicates during
traversal. And it saves a lot of syscalls for going back and forth
over the imsg pipe to request individual commits.

The cost is that we duplicate some code in got-read-pack in order
to detect changed trees in that process. It does not use the same
data structures as the main process so this code cannot be shared.

This feature is restricted to first-parent traversal which means
only 'got blame' and 'got log -f' will use this new code.
And obviously it will only help with packed repositories.
Run 'git repack -a' first if in doubt.

Numbers from a DEBUG="-O2" build on a Matebook X (i5-7200U, NVME SSD):

Before:
$ for i in 1 2 3; do time got blame sys/kern/kern_tc.c >/dev/null; done
    0m25.09s real     0m22.08s user     0m06.33s system
    0m24.79s real     0m20.20s user     0m07.51s system
    0m23.05s real     0m20.77s user     0m05.82s system

After:
$ for i in 1 2 3; do time got blame sys/kern/kern_tc.c >/dev/null; done
    0m14.30s real     0m13.25s user     0m00.81s system
    0m14.04s real     0m13.22s user     0m00.77s system
    0m13.69s real     0m12.87s user     0m00.84s system

This could probably be faster if we also added a cache of parsed
tree objects to got-read-pack, but the diff is already large enough.
And I haven't been super careful about avoiding unnecessary malloc
and free calls since I wanted to focus on getting correctly working
code for now.

But it's already an improvement.

Any comments or tests? OK?

diff refs/heads/master refs/heads/pack-history-traversal
blob - d2d7bd81d20a0bc7fb36411f186d28e28e4ce1e5
blob + 2fc90fed4ad980cb7f43ac5bd7828f424d079ac5
--- lib/commit_graph.c
+++ lib/commit_graph.c
@@ -40,9 +40,9 @@
 
 struct got_commit_graph_node {
 	struct got_object_id id;
-	time_t timestamp;
 
-	/* Used during graph iteration. */
+	/* Used only during iteration. */
+	time_t timestamp;
 	TAILQ_ENTRY(got_commit_graph_node) entry;
 };
 
@@ -147,10 +147,12 @@ done:
 
 static void
 add_node_to_iter_list(struct got_commit_graph *graph,
-    struct got_commit_graph_node *node)
+    struct got_commit_graph_node *node, time_t committer_time)
 {
 	struct got_commit_graph_node *n, *next;
 
+	node->timestamp = committer_time;
+
 	n = TAILQ_FIRST(&graph->iter_list);
 	while (n) {
 		next = TAILQ_NEXT(n, entry);
@@ -164,6 +166,79 @@ add_node_to_iter_list(struct got_commit_graph *graph,
 }
 
 static const struct got_error *
+add_node(struct got_commit_graph_node **new_node,
+    struct got_commit_graph *graph, struct got_object_id *commit_id,
+    struct got_repository *repo)
+{
+	const struct got_error *err = NULL;
+	struct got_commit_graph_node *node;
+
+	*new_node = NULL;
+
+	node = calloc(1, sizeof(*node));
+	if (node == NULL)
+		return got_error_from_errno("calloc");
+
+	memcpy(&node->id, commit_id, sizeof(node->id));
+	err = got_object_idset_add(graph->node_ids, &node->id, NULL);
+	if (err)
+		free(node);
+	else
+		*new_node = node;
+	return err;
+}
+
+/*
+ * Ask got-read-pack to traverse first-parent history until a commit is
+ * encountered which modified graph->path, or until the pack file runs
+ * out of relevant commits. This is faster than sending an individual
+ * request for each commit stored in the pack file.
+ */
+static const struct got_error *
+packed_first_parent_traversal(int *ncommits_traversed,
+    struct got_commit_graph *graph, struct got_object_id *commit_id,
+    struct got_repository *repo)
+{
+	const struct got_error *err = NULL;
+	struct got_object_id_queue traversed_commits;
+	struct got_object_qid *qid;
+
+	SIMPLEQ_INIT(&traversed_commits);
+	*ncommits_traversed = 0;
+
+	err = got_traverse_packed_commits(&traversed_commits,
+	    commit_id, graph->path, repo);
+	if (err)
+		return err;
+
+	/* Add all traversed commits to the graph... */
+	SIMPLEQ_FOREACH(qid, &traversed_commits, entry) {
+		struct got_commit_graph_node *node;
+
+		if (got_object_idset_contains(graph->open_branches, qid->id))
+			continue;
+		if (got_object_idset_contains(graph->node_ids, qid->id))
+			continue;
+
+		(*ncommits_traversed)++;
+
+		/* ... except the last commit is the new branch tip. */
+		if (SIMPLEQ_NEXT(qid, entry) == NULL) {
+			err = got_object_idset_add(graph->open_branches,
+			    qid->id, NULL);
+			break;
+		}
+
+		err = add_node(&node, graph, qid->id, repo);
+		if (err)
+			break;
+	}
+
+	got_object_id_queue_free(&traversed_commits);
+	return err;
+}
+
+static const struct got_error *
 close_branch(struct got_commit_graph *graph, struct got_object_id *commit_id)
 {
 	const struct got_error *err;
@@ -190,6 +265,22 @@ advance_branch(struct got_commit_graph *graph, struct 
 		if (qid == NULL ||
 		    got_object_idset_contains(graph->open_branches, qid->id))
 			return NULL;
+		/*
+		 * The root directory always changes by definition, and when
+		 * logging the root we want to traverse consecutive commits
+		 * even if they point at the same tree.
+		 * But if we are looking for a specific path then we can avoid
+		 * fetching packed commits which did not modify the path and
+		 * only fetch their IDs. This speeds up 'got blame'.
+		 */
+		if (!got_path_is_root_dir(graph->path) &&
+		    (commit->flags & GOT_COMMIT_FLAG_PACKED)) {
+			int ncommits = 0;
+			err = packed_first_parent_traversal(&ncommits,
+			    graph, qid->id, repo);
+			if (err || ncommits > 0)
+				return err;
+		}
 		return got_object_idset_add(graph->open_branches,
 		    qid->id, NULL);
 	}
@@ -284,33 +375,6 @@ advance_branch(struct got_commit_graph *graph, struct 
 	return NULL;
 }
 
-static const struct got_error *
-add_node(struct got_commit_graph_node **new_node,
-    struct got_commit_graph *graph,
-    struct got_object_id *commit_id,
-    struct got_commit_object *commit,
-    struct got_repository *repo)
-{
-	const struct got_error *err = NULL;
-	struct got_commit_graph_node *node;
-
-	*new_node = NULL;
-
-	node = calloc(1, sizeof(*node));
-	if (node == NULL)
-		return got_error_from_errno("calloc");
-
-	memcpy(&node->id, commit_id, sizeof(node->id));
-	node->timestamp = commit->committer_time;
-
-	err = got_object_idset_add(graph->node_ids, &node->id, NULL);
-	if (err)
-		free(node);
-	else
-		*new_node = node;
-	return err;
-}
-
 const struct got_error *
 got_commit_graph_open(struct got_commit_graph **graph,
     const char *path, int first_parent_traversal)
@@ -370,7 +434,7 @@ add_branch_tip(struct got_object_id *commit_id, void *
 	if (err)
 		return err;
 
-	err = add_node(&new_node, a->graph, commit_id, commit, a->repo);
+	err = add_node(&new_node, a->graph, commit_id, a->repo);
 	if (err)
 		return err;
 
@@ -444,7 +508,8 @@ fetch_commits_from_open_branches(struct got_commit_gra
 			continue;
 		}
 		if (changed)
-			add_node_to_iter_list(graph, new_node);
+			add_node_to_iter_list(graph, new_node,
+			    got_object_commit_get_committer_time(commit));
 		err = advance_branch(graph, commit_id, commit, repo);
 		if (err)
 			break;
blob - 2c568ecd216c5246df49102f9a2d25674eafd482
blob + 9e9ce8d3c0d8d192cb9f47b998f876604147daf7
--- lib/got_lib_object.h
+++ lib/got_lib_object.h
@@ -47,6 +47,9 @@ struct got_commit_object {
 	time_t committer_gmtoff;
 	char *logmsg;
 	int refcnt;		/* > 0 if open and/or cached */
+
+	int flags;
+#define GOT_COMMIT_FLAG_PACKED		0x01
 };
 
 struct got_tree_entry {
@@ -102,3 +105,7 @@ const struct got_error *got_object_tag_open(struct got
     struct got_repository *, struct got_object *);
 const struct got_error *got_object_tree_entry_dup(struct got_tree_entry **,
     struct got_tree_entry *);
+
+const struct got_error *got_traverse_packed_commits(
+    struct got_object_id_queue *, struct got_object_id *, const char *,
+    struct got_repository *);
blob - f1f994a6a41a9c16744f389369f3692b13da72e4
blob + 97e8c952bd0721d6cfb6a89756a0194cc24f0adc
--- lib/got_lib_pack.h
+++ lib/got_lib_pack.h
@@ -162,6 +162,7 @@ const struct got_error *got_packidx_init_hdr(struct go
 const struct got_error *got_packidx_open(struct got_packidx **,
     const char *, int);
 const struct got_error *got_packidx_close(struct got_packidx *);
+int got_packidx_get_object_idx_sha1(struct got_packidx *, uint8_t *);
 int got_packidx_get_object_idx(struct got_packidx *, struct got_object_id *);
 const struct got_error *got_packidx_match_id_str_prefix(
     struct got_object_id_queue *, struct got_packidx *, const char *);
blob - b27325da498aa72413f8377303ba76d4012c7813
blob + 063cf499f590153399327ba078c745eb35358565
--- lib/got_lib_privsep.h
+++ lib/got_lib_privsep.h
@@ -102,6 +102,9 @@ enum got_imsg_type {
 	GOT_IMSG_PACKIDX,
 	GOT_IMSG_PACK,
 	GOT_IMSG_PACKED_OBJECT_REQUEST,
+	GOT_IMSG_COMMIT_TRAVERSAL_REQUEST,
+	GOT_IMSG_TRAVERSED_COMMITS,
+	GOT_IMSG_COMMIT_TRAVERSAL_DONE,
 
 	/* Message sending file descriptor to a temporary file. */
 	GOT_IMSG_TMPFD,
@@ -232,6 +235,20 @@ struct got_imsg_packed_object {
 	int idx;
 } __attribute__((__packed__));
 
+/* Structure for GOT_IMSG_COMMIT_TRAVERSAL_REQUEST  */
+struct got_imsg_commit_traversal_request {
+	uint8_t id[SHA1_DIGEST_LENGTH];
+	int idx;
+	size_t path_len;
+	/* Followed by path_len bytes of path data */
+} __attribute__((__packed__));
+
+/* Structure for GOT_IMSG_TRAVERSED_COMMITS  */
+struct got_imsg_traversed_commits {
+	size_t ncommits;
+	/* Followed by ncommit IDs of SHA1_DIGEST_LENGTH each */
+} __attribute__((__packed__));
+
 /*
  * Structure for GOT_IMSG_GITCONFIG_REMOTE data.
  */
@@ -253,6 +270,7 @@ struct got_remote_repo;
 struct got_pack;
 struct got_packidx;
 struct got_pathlist_head;
+struct got_parsed_tree_entry;
 
 const struct got_error *got_privsep_wait_for_child(pid_t);
 const struct got_error *got_privsep_send_stop(int);
@@ -318,5 +336,15 @@ const struct got_error *got_privsep_send_gitconfig_rem
     struct got_remote_repo *, int);
 const struct got_error *got_privsep_recv_gitconfig_remotes(
     struct got_remote_repo **, int *, struct imsgbuf *);
+
+const struct got_error *got_privsep_send_commit_traversal_request(
+    struct imsgbuf *, struct got_object_id *, int, const char *);
+const struct got_error *got_privsep_recv_traversed_commits(
+    struct got_commit_object **, struct got_object_id **,
+    struct got_object_id_queue *, struct imsgbuf *);
+const struct got_error *got_privsep_send_traversed_commits(
+    struct got_object_id *, size_t, struct imsgbuf *);
+const struct got_error *got_privsep_send_commit_traversal_done(
+    struct imsgbuf *);
 
 void got_privsep_exec_child(int[2], const char *, const char *);
blob - 4aaeb8a3199435ce3b95f7218a552f6375558752
blob + 4f98167915dd8661414656d1b92c2624248f1519
--- lib/object.c
+++ lib/object.c
@@ -58,18 +58,6 @@
 #endif
 
 struct got_object_id *
-got_object_id_dup(struct got_object_id *id1)
-{
-	struct got_object_id *id2;
-
-	id2 = malloc(sizeof(*id2));
-	if (id2 == NULL)
-		return NULL;
-	memcpy(id2, id1, sizeof(*id2));
-	return id2;
-}
-
-struct got_object_id *
 got_object_get_id(struct got_object *obj)
 {
 	return &obj->id;
@@ -480,7 +468,12 @@ request_packed_commit(struct got_commit_object **commi
 	if (err)
 		return err;
 
-	return got_privsep_recv_commit(commit, pack->privsep_child->ibuf);
+	err = got_privsep_recv_commit(commit, pack->privsep_child->ibuf);
+	if (err)
+		return err;
+
+	(*commit)->flags |= GOT_COMMIT_FLAG_PACKED;
+	return NULL;
 }
 
 static const struct got_error *
@@ -1748,4 +1741,67 @@ int
 got_object_tree_entry_is_submodule(struct got_tree_entry *te)
 {
 	return (te->mode & S_IFMT) == (S_IFDIR | S_IFLNK);
+}
+
+const struct got_error *
+got_traverse_packed_commits(struct got_object_id_queue *traversed_commits,
+    struct got_object_id *commit_id, const char *path,
+    struct got_repository *repo)
+{
+	const struct got_error *err = NULL;
+	struct got_pack *pack = NULL;
+	struct got_packidx *packidx = NULL;
+	char *path_packfile = NULL;
+	struct got_commit_object *changed_commit = NULL;
+	struct got_object_id *changed_commit_id = NULL;
+	int idx;
+
+	err = got_repo_search_packidx(&packidx, &idx, repo, commit_id);
+	if (err) {
+		if (err->code != GOT_ERR_NO_OBJ)
+			return err;
+		return NULL;
+	}
+
+	err = get_packfile_path(&path_packfile, packidx);
+	if (err)
+		return err;
+
+	pack = got_repo_get_cached_pack(repo, path_packfile);
+	if (pack == NULL) {
+		err = got_repo_cache_pack(&pack, repo, path_packfile, packidx);
+		if (err)
+			goto done;
+	}
+
+	if (pack->privsep_child == NULL) {
+		err = start_pack_privsep_child(pack, packidx);
+		if (err)
+			goto done;
+	}
+
+	err = got_privsep_send_commit_traversal_request(
+	    pack->privsep_child->ibuf, commit_id, idx, path);
+	if (err)
+		goto done;
+
+	err = got_privsep_recv_traversed_commits(&changed_commit,
+	    &changed_commit_id, traversed_commits, pack->privsep_child->ibuf);
+	if (err)
+		goto done;
+
+	if (changed_commit) {
+		/*
+		 * Cache the commit in which the path was changed.
+		 * This commit might be opened again soon.
+		 */
+		changed_commit->refcnt++;
+		err = got_repo_cache_commit(repo, changed_commit_id,
+		    changed_commit);
+		got_object_commit_close(changed_commit);
+	}
+done:
+	free(path_packfile);
+	free(changed_commit_id);
+	return err;
 }
blob - b13f1011f3dfd2ab3e4c7cd0746c6969d926402a
blob + 88a921c0ec935b5ccea04f9dd25080cd35c5e2fc
--- lib/object_parse.c
+++ lib/object_parse.c
@@ -55,6 +55,18 @@
 #define nitems(_a) (sizeof(_a) / sizeof((_a)[0]))
 #endif
 
+struct got_object_id *
+got_object_id_dup(struct got_object_id *id1)
+{
+	struct got_object_id *id2;
+
+	id2 = malloc(sizeof(*id2));
+	if (id2 == NULL)
+		return NULL;
+	memcpy(id2, id1, sizeof(*id2));
+	return id2;
+}
+
 int
 got_object_id_cmp(const struct got_object_id *id1,
     const struct got_object_id *id2)
blob - a9b1b6eb48b0924daa65c5a355d80f0d8ad91a14
blob + 75ffa3acf9d448557e42796d6fc751703872b702
--- lib/pack.c
+++ lib/pack.c
@@ -430,9 +430,9 @@ get_object_offset(struct got_packidx *packidx, int idx
 }
 
 int
-got_packidx_get_object_idx(struct got_packidx *packidx, struct got_object_id *id)
+got_packidx_get_object_idx_sha1(struct got_packidx *packidx, uint8_t *sha1)
 {
-	u_int8_t id0 = id->sha1[0];
+	u_int8_t id0 = sha1[0];
 	uint32_t totobj = betoh32(packidx->hdr.fanout_table[0xff]);
 	int left = 0, right = totobj - 1;
 
@@ -445,7 +445,7 @@ got_packidx_get_object_idx(struct got_packidx *packidx
 
 		i = ((left + right) / 2);
 		oid = &packidx->hdr.sorted_ids[i];
-		cmp = memcmp(id->sha1, oid->sha1, SHA1_DIGEST_LENGTH);
+		cmp = memcmp(sha1, oid->sha1, SHA1_DIGEST_LENGTH);
 		if (cmp == 0)
 			return i;
 		else if (cmp > 0)
@@ -455,6 +455,12 @@ got_packidx_get_object_idx(struct got_packidx *packidx
 	}
 
 	return -1;
+}
+
+int
+got_packidx_get_object_idx(struct got_packidx *packidx, struct got_object_id *id)
+{
+	return got_packidx_get_object_idx_sha1(packidx, id->sha1);
 }
 
 const struct got_error *
blob - 16a5ac4351dea09e00f0fbc94fd1626bc70327d4
blob + 65a9c11d796285778835976348dba7c477ed2eb1
--- lib/privsep.c
+++ lib/privsep.c
@@ -549,143 +549,155 @@ done:
 	return err;
 }
 
-const struct got_error *
-got_privsep_recv_commit(struct got_commit_object **commit, struct imsgbuf *ibuf)
+static const struct got_error *
+get_commit_from_imsg(struct got_commit_object **commit,
+    struct imsg *imsg, size_t datalen, struct imsgbuf *ibuf)
 {
 	const struct got_error *err = NULL;
-	struct imsg imsg;
 	struct got_imsg_commit_object *icommit;
-	size_t len, datalen;
+	size_t len = 0;
 	int i;
-	const size_t min_datalen =
-	    MIN(sizeof(struct got_imsg_error),
-	    sizeof(struct got_imsg_commit_object));
 
-	*commit = NULL;
+	if (datalen < sizeof(*icommit))
+		return got_error(GOT_ERR_PRIVSEP_LEN);
 
-	err = got_privsep_recv_imsg(&imsg, ibuf, min_datalen);
-	if (err)
-		return err;
+	icommit = imsg->data;
+	if (datalen != sizeof(*icommit) + icommit->author_len +
+	    icommit->committer_len +
+	    icommit->nparents * SHA1_DIGEST_LENGTH)
+		return got_error(GOT_ERR_PRIVSEP_LEN);
 
-	datalen = imsg.hdr.len - IMSG_HEADER_SIZE;
-	len = 0;
+	if (icommit->nparents < 0)
+		return got_error(GOT_ERR_PRIVSEP_LEN);
 
-	switch (imsg.hdr.type) {
-	case GOT_IMSG_COMMIT:
-		if (datalen < sizeof(*icommit)) {
-			err = got_error(GOT_ERR_PRIVSEP_LEN);
-			break;
+	len += sizeof(*icommit);
+
+	*commit = got_object_commit_alloc_partial();
+	if (*commit == NULL)
+		return got_error_from_errno(
+		    "got_object_commit_alloc_partial");
+
+	memcpy((*commit)->tree_id->sha1, icommit->tree_id,
+	    SHA1_DIGEST_LENGTH);
+	(*commit)->author_time = icommit->author_time;
+	(*commit)->author_gmtoff = icommit->author_gmtoff;
+	(*commit)->committer_time = icommit->committer_time;
+	(*commit)->committer_gmtoff = icommit->committer_gmtoff;
+
+	if (icommit->author_len == 0) {
+		(*commit)->author = strdup("");
+		if ((*commit)->author == NULL) {
+			err = got_error_from_errno("strdup");
+			goto done;
 		}
-		icommit = imsg.data;
-		if (datalen != sizeof(*icommit) + icommit->author_len +
-		    icommit->committer_len +
-		    icommit->nparents * SHA1_DIGEST_LENGTH) {
-			err = got_error(GOT_ERR_PRIVSEP_LEN);
-			break;
+	} else {
+		(*commit)->author = malloc(icommit->author_len + 1);
+		if ((*commit)->author == NULL) {
+			err = got_error_from_errno("malloc");
+			goto done;
 		}
-		if (icommit->nparents < 0) {
-			err = got_error(GOT_ERR_PRIVSEP_LEN);
-			break;
+		memcpy((*commit)->author, imsg->data + len,
+		    icommit->author_len);
+		(*commit)->author[icommit->author_len] = '\0';
+	}
+	len += icommit->author_len;
+
+	if (icommit->committer_len == 0) {
+		(*commit)->committer = strdup("");
+		if ((*commit)->committer == NULL) {
+			err = got_error_from_errno("strdup");
+			goto done;
 		}
-		len += sizeof(*icommit);
+	} else {
+		(*commit)->committer =
+		    malloc(icommit->committer_len + 1);
+		if ((*commit)->committer == NULL) {
+			err = got_error_from_errno("malloc");
+			goto done;
+		}
+		memcpy((*commit)->committer, imsg->data + len,
+		    icommit->committer_len);
+		(*commit)->committer[icommit->committer_len] = '\0';
+	}
+	len += icommit->committer_len;
 
-		*commit = got_object_commit_alloc_partial();
-		if (*commit == NULL) {
-			err = got_error_from_errno(
-			    "got_object_commit_alloc_partial");
-			break;
+	if (icommit->logmsg_len == 0) {
+		(*commit)->logmsg = strdup("");
+		if ((*commit)->logmsg == NULL) {
+			err = got_error_from_errno("strdup");
+			goto done;
 		}
+	} else {
+		size_t offset = 0, remain = icommit->logmsg_len;
 
-		memcpy((*commit)->tree_id->sha1, icommit->tree_id,
-		    SHA1_DIGEST_LENGTH);
-		(*commit)->author_time = icommit->author_time;
-		(*commit)->author_gmtoff = icommit->author_gmtoff;
-		(*commit)->committer_time = icommit->committer_time;
-		(*commit)->committer_gmtoff = icommit->committer_gmtoff;
-
-		if (icommit->author_len == 0) {
-			(*commit)->author = strdup("");
-			if ((*commit)->author == NULL) {
-				err = got_error_from_errno("strdup");
-				break;
-			}
-		} else {
-			(*commit)->author = malloc(icommit->author_len + 1);
-			if ((*commit)->author == NULL) {
-				err = got_error_from_errno("malloc");
-				break;
-			}
-			memcpy((*commit)->author, imsg.data + len,
-			    icommit->author_len);
-			(*commit)->author[icommit->author_len] = '\0';
+		(*commit)->logmsg = malloc(icommit->logmsg_len + 1);
+		if ((*commit)->logmsg == NULL) {
+			err = got_error_from_errno("malloc");
+			goto done;
 		}
-		len += icommit->author_len;
+		while (remain > 0) {
+			struct imsg imsg_log;
+			size_t n = MIN(MAX_IMSGSIZE - IMSG_HEADER_SIZE,
+			    remain);
 
-		if (icommit->committer_len == 0) {
-			(*commit)->committer = strdup("");
-			if ((*commit)->committer == NULL) {
-				err = got_error_from_errno("strdup");
-				break;
+			err = got_privsep_recv_imsg(&imsg_log, ibuf, n);
+			if (err)
+				goto done;
+
+			if (imsg_log.hdr.type != GOT_IMSG_COMMIT_LOGMSG) {
+				err = got_error(GOT_ERR_PRIVSEP_MSG);
+				goto done;
 			}
-		} else {
-			(*commit)->committer =
-			    malloc(icommit->committer_len + 1);
-			if ((*commit)->committer == NULL) {
-				err = got_error_from_errno("malloc");
-				break;
-			}
-			memcpy((*commit)->committer, imsg.data + len,
-			    icommit->committer_len);
-			(*commit)->committer[icommit->committer_len] = '\0';
+
+			memcpy((*commit)->logmsg + offset,
+			    imsg_log.data, n);
+			imsg_free(&imsg_log);
+			offset += n;
+			remain -= n;
 		}
-		len += icommit->committer_len;
+		(*commit)->logmsg[icommit->logmsg_len] = '\0';
+	}
 
-		if (icommit->logmsg_len == 0) {
-			(*commit)->logmsg = strdup("");
-			if ((*commit)->logmsg == NULL) {
-				err = got_error_from_errno("strdup");
-				break;
-			}
-		} else {
-			size_t offset = 0, remain = icommit->logmsg_len;
+	for (i = 0; i < icommit->nparents; i++) {
+		struct got_object_qid *qid;
 
-			(*commit)->logmsg = malloc(icommit->logmsg_len + 1);
-			if ((*commit)->logmsg == NULL) {
-				err = got_error_from_errno("malloc");
-				break;
-			}
-			while (remain > 0) {
-				struct imsg imsg_log;
-				size_t n = MIN(MAX_IMSGSIZE - IMSG_HEADER_SIZE,
-				    remain);
+		err = got_object_qid_alloc_partial(&qid);
+		if (err)
+			break;
+		memcpy(qid->id, imsg->data + len +
+		    i * SHA1_DIGEST_LENGTH, sizeof(*qid->id));
+		SIMPLEQ_INSERT_TAIL(&(*commit)->parent_ids, qid, entry);
+		(*commit)->nparents++;
+	}
+done:
+	if (err) {
+		got_object_commit_close(*commit);
+		*commit = NULL;
+	}
+	return err;
+}
 
-				err = got_privsep_recv_imsg(&imsg_log, ibuf, n);
-				if (err)
-					return err;
+const struct got_error *
+got_privsep_recv_commit(struct got_commit_object **commit, struct imsgbuf *ibuf)
+{
+	const struct got_error *err = NULL;
+	struct imsg imsg;
+	size_t datalen;
+	const size_t min_datalen =
+	    MIN(sizeof(struct got_imsg_error),
+	    sizeof(struct got_imsg_commit_object));
 
-				if (imsg_log.hdr.type != GOT_IMSG_COMMIT_LOGMSG)
-					return got_error(GOT_ERR_PRIVSEP_MSG);
+	*commit = NULL;
 
-				memcpy((*commit)->logmsg + offset,
-				    imsg_log.data, n);
-				imsg_free(&imsg_log);
-				offset += n;
-				remain -= n;
-			}
-			(*commit)->logmsg[icommit->logmsg_len] = '\0';
-		}
+	err = got_privsep_recv_imsg(&imsg, ibuf, min_datalen);
+	if (err)
+		return err;
 
-		for (i = 0; i < icommit->nparents; i++) {
-			struct got_object_qid *qid;
+	datalen = imsg.hdr.len - IMSG_HEADER_SIZE;
 
-			err = got_object_qid_alloc_partial(&qid);
-			if (err)
-				break;
-			memcpy(qid->id, imsg.data + len +
-			    i * SHA1_DIGEST_LENGTH, sizeof(*qid->id));
-			SIMPLEQ_INSERT_TAIL(&(*commit)->parent_ids, qid, entry);
-			(*commit)->nparents++;
-		}
+	switch (imsg.hdr.type) {
+	case GOT_IMSG_COMMIT:
+		err = get_commit_from_imsg(commit, &imsg, datalen, ibuf);
 		break;
 	default:
 		err = got_error(GOT_ERR_PRIVSEP_MSG);
@@ -1545,6 +1557,162 @@ got_privsep_recv_gitconfig_remotes(struct got_remote_r
 		*nremotes = 0;
 	}
 	return err;
+}
+
+const struct got_error *
+got_privsep_send_commit_traversal_request(struct imsgbuf *ibuf,
+     struct got_object_id *id, int idx, const char *path)
+{
+	const struct got_error *err = NULL;
+	struct ibuf *wbuf;
+	size_t path_len = strlen(path) + 1;
+
+	wbuf = imsg_create(ibuf, GOT_IMSG_COMMIT_TRAVERSAL_REQUEST, 0, 0,
+	    sizeof(struct got_imsg_commit_traversal_request) + path_len);
+	if (wbuf == NULL)
+		return got_error_from_errno(
+		    "imsg_create COMMIT_TRAVERSAL_REQUEST");
+	if (imsg_add(wbuf, id->sha1, SHA1_DIGEST_LENGTH) == -1) {
+		err = got_error_from_errno("imsg_add COMMIT_TRAVERSAL_REQUEST");
+		ibuf_free(wbuf);
+		return err;
+	}
+	if (imsg_add(wbuf, &idx, sizeof(idx)) == -1) {
+		err = got_error_from_errno("imsg_add COMMIT_TRAVERSAL_REQUEST");
+		ibuf_free(wbuf);
+		return err;
+	}
+	if (imsg_add(wbuf, path, path_len) == -1) {
+		err = got_error_from_errno("imsg_add COMMIT_TRAVERSAL_REQUEST");
+		ibuf_free(wbuf);
+		return err;
+	}
+
+	wbuf->fd = -1;
+	imsg_close(ibuf, wbuf);
+
+	return flush_imsg(ibuf);
+}
+
+const struct got_error *
+got_privsep_send_traversed_commits(struct got_object_id *commit_ids, 
+    size_t ncommits, struct imsgbuf *ibuf)
+{
+	const struct got_error *err;
+	struct ibuf *wbuf;
+	int i;
+
+	wbuf = imsg_create(ibuf, GOT_IMSG_TRAVERSED_COMMITS, 0, 0,
+	    sizeof(struct got_imsg_traversed_commits) +
+	    ncommits * SHA1_DIGEST_LENGTH);
+	if (wbuf == NULL)
+		return got_error_from_errno("imsg_create TRAVERSED_COMMITS");
+
+	if (imsg_add(wbuf, &ncommits, sizeof(ncommits)) == -1) {
+		err = got_error_from_errno("imsg_add TRAVERSED_COMMITS");
+		ibuf_free(wbuf);
+		return err;
+	}
+	for (i = 0; i < ncommits; i++) {
+		struct got_object_id *id = &commit_ids[i];
+		if (imsg_add(wbuf, id->sha1, SHA1_DIGEST_LENGTH) == -1) {
+			err = got_error_from_errno(
+			    "imsg_add TRAVERSED_COMMITS");
+			ibuf_free(wbuf);
+			return err;
+		}
+	}
+
+	wbuf->fd = -1;
+	imsg_close(ibuf, wbuf);
+
+	return flush_imsg(ibuf);
+}
+
+const struct got_error *
+got_privsep_recv_traversed_commits(struct got_commit_object **changed_commit,
+    struct got_object_id **changed_commit_id,
+    struct got_object_id_queue *commit_ids, struct imsgbuf *ibuf)
+{
+	const struct got_error *err = NULL;
+	struct imsg imsg;
+	struct got_imsg_traversed_commits *icommits;
+	size_t datalen;
+	int i, done = 0;
+
+	*changed_commit = NULL;
+	*changed_commit_id = NULL;
+
+	while (!done) {
+		err = got_privsep_recv_imsg(&imsg, ibuf, 0);
+		if (err)
+			return err;
+
+		datalen = imsg.hdr.len - IMSG_HEADER_SIZE;
+		switch (imsg.hdr.type) {
+		case GOT_IMSG_TRAVERSED_COMMITS:
+			icommits = imsg.data;
+			if (datalen != sizeof(*icommits) +
+			    icommits->ncommits * SHA1_DIGEST_LENGTH) {
+				err = got_error(GOT_ERR_PRIVSEP_LEN);
+				break;
+			}
+			for (i = 0; i < icommits->ncommits; i++) {
+				struct got_object_qid *qid;
+				uint8_t *sha1 = (uint8_t *)imsg.data +
+				    sizeof(*icommits) + i * SHA1_DIGEST_LENGTH;
+				err = got_object_qid_alloc_partial(&qid);
+				if (err)
+					break;
+				memcpy(qid->id->sha1, sha1, SHA1_DIGEST_LENGTH);
+				SIMPLEQ_INSERT_TAIL(commit_ids, qid, entry);
+
+				/* The last commit may contain a change. */
+				if (i == icommits->ncommits - 1) {
+					*changed_commit_id =
+					    got_object_id_dup(qid->id);
+					if (*changed_commit_id == NULL) {
+						err = got_error_from_errno(
+						    "got_object_id_dup");
+						break;
+					}
+				}
+			}
+			break;
+		case GOT_IMSG_COMMIT:
+			if (*changed_commit_id == NULL) {
+				err = got_error(GOT_ERR_PRIVSEP_MSG);
+				break;
+			}
+			err = get_commit_from_imsg(changed_commit, &imsg,
+			    datalen, ibuf);
+			break;
+		case GOT_IMSG_COMMIT_TRAVERSAL_DONE:
+			done = 1;
+			break;
+		default:
+			err = got_error(GOT_ERR_PRIVSEP_MSG);
+			break;
+		}
+
+		imsg_free(&imsg);
+		if (err)
+			break;
+	}
+
+	if (err)
+		got_object_id_queue_free(commit_ids);
+	return err;
+}
+
+const struct got_error *
+got_privsep_send_commit_traversal_done(struct imsgbuf *ibuf)
+{
+	if (imsg_compose(ibuf, GOT_IMSG_COMMIT_TRAVERSAL_DONE, 0, 0, -1,
+	    NULL, 0) == -1)
+		return got_error_from_errno("imsg_compose TRAVERSAL_DONE");
+
+	return flush_imsg(ibuf);
 }
 
 const struct got_error *
blob - 72b14bc04cbff71ec15b9bc157c38742415aa509
blob + 6c83e415d5e68c3e34d24f007f6ff49214810d65
--- libexec/got-read-pack/got-read-pack.c
+++ libexec/got-read-pack/got-read-pack.c
@@ -106,30 +106,23 @@ done:
 	return err;
 }
 
-static const struct got_error *
-commit_request(struct imsg *imsg, struct imsgbuf *ibuf, struct got_pack *pack,
-    struct got_packidx *packidx, struct got_object_cache *objcache)
+const struct got_error *
+open_commit(struct got_commit_object **commit, struct got_pack *pack,
+    struct got_packidx *packidx, int obj_idx, struct got_object_id *id,
+    struct got_object_cache *objcache)
 {
 	const struct got_error *err = NULL;
-	struct got_imsg_packed_object iobj;
 	struct got_object *obj = NULL;
-	struct got_commit_object *commit = NULL;
 	uint8_t *buf = NULL;
 	size_t len;
-	struct got_object_id id;
-	size_t datalen;
 
-	datalen = imsg->hdr.len - IMSG_HEADER_SIZE;
-	if (datalen != sizeof(iobj))
-		return got_error(GOT_ERR_PRIVSEP_LEN);
-	memcpy(&iobj, imsg->data, sizeof(iobj));
-	memcpy(id.sha1, iobj.id, SHA1_DIGEST_LENGTH);
+	*commit = NULL;
 
-	obj = got_object_cache_get(objcache, &id);
+	obj = got_object_cache_get(objcache, id);
 	if (obj) {
 		obj->refcnt++;
 	} else {
-		err = open_object(&obj, pack, packidx, iobj.idx, &id,
+		err = open_object(&obj, pack, packidx, obj_idx, id,
 		    objcache);
 		if (err)
 			return err;
@@ -140,14 +133,36 @@ commit_request(struct imsg *imsg, struct imsgbuf *ibuf
 		goto done;
 
 	obj->size = len;
-	err = got_object_parse_commit(&commit, buf, len);
+
+	err = got_object_parse_commit(commit, buf, len);
+done:
+	got_object_close(obj);
+	free(buf);
+	return err;
+}
+
+static const struct got_error *
+commit_request(struct imsg *imsg, struct imsgbuf *ibuf, struct got_pack *pack,
+    struct got_packidx *packidx, struct got_object_cache *objcache)
+{
+	const struct got_error *err = NULL;
+	struct got_imsg_packed_object iobj;
+	struct got_commit_object *commit = NULL;
+	struct got_object_id id;
+	size_t datalen;
+
+	datalen = imsg->hdr.len - IMSG_HEADER_SIZE;
+	if (datalen != sizeof(iobj))
+		return got_error(GOT_ERR_PRIVSEP_LEN);
+	memcpy(&iobj, imsg->data, sizeof(iobj));
+	memcpy(id.sha1, iobj.id, SHA1_DIGEST_LENGTH);
+
+	err = open_commit(&commit, pack, packidx, iobj.idx, &id, objcache);
 	if (err)
 		goto done;
 
 	err = got_privsep_send_commit(ibuf, commit);
 done:
-	free(buf);
-	got_object_close(obj);
 	if (commit)
 		got_object_commit_close(commit);
 	if (err) {
@@ -160,17 +175,53 @@ done:
 	return err;
 }
 
+const struct got_error *
+open_tree(uint8_t **buf, struct got_pathlist_head *entries, int *nentries,
+    struct got_pack *pack, struct got_packidx *packidx, int obj_idx,
+    struct got_object_id *id, struct got_object_cache *objcache)
+{
+	const struct got_error *err = NULL;
+	struct got_object *obj = NULL;
+	size_t len;
+
+	*buf = NULL;
+	*nentries = 0;
+
+	obj = got_object_cache_get(objcache, id);
+	if (obj) {
+		obj->refcnt++;
+	} else {
+		err = open_object(&obj, pack, packidx, obj_idx, id,
+		    objcache);
+		if (err)
+			return err;
+	}
+
+	err = got_packfile_extract_object_to_mem(buf, &len, obj, pack);
+	if (err)
+		goto done;
+
+	obj->size = len;
+
+	err = got_object_parse_tree(entries, nentries, *buf, len);
+done:
+	got_object_close(obj);
+	if (err) {
+		free(*buf);
+		*buf = NULL;
+	}
+	return err;
+}
+
 static const struct got_error *
 tree_request(struct imsg *imsg, struct imsgbuf *ibuf, struct got_pack *pack,
     struct got_packidx *packidx, struct got_object_cache *objcache)
 {
 	const struct got_error *err = NULL;
 	struct got_imsg_packed_object iobj;
-	struct got_object *obj = NULL;
 	struct got_pathlist_head entries;
 	int nentries = 0;
 	uint8_t *buf = NULL;
-	size_t len;
 	struct got_object_id id;
 	size_t datalen;
 
@@ -182,30 +233,14 @@ tree_request(struct imsg *imsg, struct imsgbuf *ibuf, 
 	memcpy(&iobj, imsg->data, sizeof(iobj));
 	memcpy(id.sha1, iobj.id, SHA1_DIGEST_LENGTH);
 
-	obj = got_object_cache_get(objcache, &id);
-	if (obj) {
-		obj->refcnt++;
-	} else {
-		err = open_object(&obj, pack, packidx, iobj.idx, &id,
-		    objcache);
-		if (err)
-			return err;
-	}
-
-	err = got_packfile_extract_object_to_mem(&buf, &len, obj, pack);
+	err = open_tree(&buf, &entries, &nentries, pack, packidx, iobj.idx,
+	     &id, objcache);
 	if (err)
-		goto done;
+		return err;
 
-	obj->size = len;
-	err = got_object_parse_tree(&entries, &nentries, buf, len);
-	if (err)
-		goto done;
-
 	err = got_privsep_send_tree(ibuf, &entries, nentries);
-done:
 	got_object_parsed_tree_entries_free(&entries);
 	free(buf);
-	got_object_close(obj);
 	if (err) {
 		if (err->code == GOT_ERR_PRIVSEP_PIPE)
 			err = NULL;
@@ -378,7 +413,326 @@ done:
 	return err;
 }
 
+static struct got_parsed_tree_entry *
+find_entry_by_name(struct got_pathlist_head *entries, int nentries,
+    const char *name, size_t len)
+{
+	struct got_pathlist_entry *pe;
+
+	/* Note that tree entries are sorted in strncmp() order. */
+	TAILQ_FOREACH(pe, entries, entry) {
+		int cmp = strncmp(pe->path, name, len);
+		if (cmp < 0)
+			continue;
+		if (cmp > 0)
+			break;
+		if (pe->path[len] == '\0')
+			return (struct got_parsed_tree_entry *)pe->data;
+	}
+	return NULL;
+}
+
+const struct got_error *
+tree_path_changed(int *changed, uint8_t **buf1, uint8_t **buf2,
+    struct got_pathlist_head *entries1, int *nentries1,
+    struct got_pathlist_head *entries2, int *nentries2,
+    const char *path, struct got_pack *pack, struct got_packidx *packidx,
+    struct imsgbuf *ibuf, struct got_object_cache *objcache)
+{
+	const struct got_error *err = NULL;
+	struct got_parsed_tree_entry *pte1 = NULL, *pte2 = NULL;
+	const char *seg, *s;
+	size_t seglen;
+
+	*changed = 0;
+
+	/* We are expecting an absolute in-repository path. */
+	if (path[0] != '/')
+		return got_error(GOT_ERR_NOT_ABSPATH);
+
+	/* We not do support comparing the root path. */
+	if (path[1] == '\0')
+		return got_error(GOT_ERR_BAD_PATH);
+
+	s = path;
+	s++; /* skip leading '/' */
+	seg = s;
+	seglen = 0;
+	while (*s) {
+		if (*s != '/') {
+			s++;
+			seglen++;
+			if (*s)
+				continue;
+		}
+
+		pte1 = find_entry_by_name(entries1, *nentries1, seg, seglen);
+		if (pte1 == NULL) {
+			err = got_error(GOT_ERR_NO_OBJ);
+			break;
+		}
+
+		pte2 = find_entry_by_name(entries2, *nentries2, seg, seglen);
+		if (pte2 == NULL) {
+			*changed = 1;
+			break;
+		}
+
+		if (pte1->mode != pte2->mode) {
+			*changed = 1;
+			break;
+		}
+
+		if (memcmp(pte1->id, pte2->id, SHA1_DIGEST_LENGTH) == 0) {
+			*changed = 0;
+			break;
+		}
+
+		if (*s == '\0') { /* final path element */
+			*changed = 1;
+			break;
+		}
+
+		seg = s + 1;
+		s++;
+		seglen = 0;
+		if (*s) {
+			struct got_object_id id1, id2;
+			int idx;
+
+			idx = got_packidx_get_object_idx_sha1(packidx,
+			    pte1->id);
+			if (idx == -1) {
+				err = got_error(GOT_ERR_NO_OBJ);
+				break;
+			}
+			memcpy(id1.sha1, pte1->id, SHA1_DIGEST_LENGTH);
+			got_object_parsed_tree_entries_free(entries1);
+			*nentries1 = 0;
+			free(*buf1);
+			*buf1 = NULL;
+			err = open_tree(buf1, entries1, nentries1, pack,
+			    packidx, idx, &id1, objcache);
+			pte1 = NULL;
+			if (err)
+				break;
+
+			idx = got_packidx_get_object_idx_sha1(packidx,
+			    pte2->id);
+			if (idx == -1) {
+				err = got_error(GOT_ERR_NO_OBJ);
+				break;
+			}
+			memcpy(id2.sha1, pte2->id, SHA1_DIGEST_LENGTH);
+			got_object_parsed_tree_entries_free(entries2);
+			*nentries2 = 0;
+			free(*buf2);
+			*buf2 = NULL;
+			err = open_tree(buf2, entries2, nentries2, pack,
+			    packidx, idx, &id2, objcache);
+			pte2 = NULL;
+			if (err)
+				break;
+		}
+	}
+
+	return err;
+}
+
 static const struct got_error *
+commit_traversal_request(struct imsg *imsg, struct imsgbuf *ibuf,
+    struct got_pack *pack, struct got_packidx *packidx,
+    struct got_object_cache *objcache)
+{
+	const struct got_error *err = NULL;
+	struct got_imsg_packed_object iobj;
+	struct got_object_qid *pid;
+	struct got_commit_object *commit = NULL, *pcommit = NULL;
+	struct got_pathlist_head entries, pentries;
+	int nentries = 0, pnentries = 0;
+	struct got_object_id id;
+	size_t datalen, path_len;
+	char *path = NULL;
+	const int min_alloc = 64;
+	int changed = 0, ncommits = 0, nallocated = 0;
+	struct got_object_id *commit_ids = NULL;
+
+	TAILQ_INIT(&entries);
+	TAILQ_INIT(&pentries);
+
+	datalen = imsg->hdr.len - IMSG_HEADER_SIZE;
+	if (datalen < sizeof(iobj))
+		return got_error(GOT_ERR_PRIVSEP_LEN);
+	memcpy(&iobj, imsg->data, sizeof(iobj));
+	memcpy(id.sha1, iobj.id, SHA1_DIGEST_LENGTH);
+
+	path_len = datalen - sizeof(iobj) - 1;
+	if (path_len < 0)
+		return got_error(GOT_ERR_PRIVSEP_LEN);
+	if (path_len > 0) {
+		path = imsg->data + sizeof(iobj);
+		if (path[path_len] != '\0')
+			return got_error(GOT_ERR_PRIVSEP_LEN);
+	}
+
+	nallocated = min_alloc;
+	commit_ids = reallocarray(NULL, nallocated, sizeof(*commit_ids));
+	if (commit_ids == NULL)
+		return got_error_from_errno("reallocarray");
+
+	do {
+		const size_t max_datalen = MAX_IMSGSIZE - IMSG_HEADER_SIZE;
+		int idx;
+
+		if (sigint_received) {
+			err = got_error(GOT_ERR_CANCELLED);
+			goto done;
+		}
+	
+		if (commit == NULL) {
+			idx = got_packidx_get_object_idx(packidx, &id);
+			if (idx == -1)
+				break;
+			err = open_commit(&commit, pack, packidx,
+			    idx, &id, objcache);
+			if (err) {
+				if (err->code != GOT_ERR_NO_OBJ)
+					goto done;
+				err = NULL;
+				break;
+			}
+		}
+
+		if (sizeof(struct got_imsg_traversed_commits) +
+		    ncommits * SHA1_DIGEST_LENGTH >= max_datalen) {
+			err = got_privsep_send_traversed_commits(commit_ids,
+			    ncommits, ibuf);
+			if (err)
+				goto done;
+			ncommits = 0;
+		}
+		ncommits++;
+		if (ncommits > nallocated) {
+			struct got_object_id *new;
+			nallocated += min_alloc;
+			new = reallocarray(commit_ids, nallocated,
+			    sizeof(*commit_ids));
+			if (new == NULL) {
+				err = got_error_from_errno("reallocarray");
+				goto done;
+			}
+			commit_ids = new;
+		}
+		memcpy(commit_ids[ncommits - 1].sha1, id.sha1,
+		    SHA1_DIGEST_LENGTH);
+
+		pid = SIMPLEQ_FIRST(&commit->parent_ids);
+		if (pid == NULL)
+			break;
+
+		idx = got_packidx_get_object_idx(packidx, pid->id);
+		if (idx == -1)
+			break;
+
+		err = open_commit(&pcommit, pack, packidx, idx, pid->id,
+		    objcache);
+		if (err) {
+			if (err->code != GOT_ERR_NO_OBJ)
+				goto done;
+			err = NULL;
+			break;
+		}
+
+		if (path[0] == '/' && path[1] == '\0') {
+			if (got_object_id_cmp(pcommit->tree_id,
+			    commit->tree_id) != 0) {
+				changed = 1;
+				break;
+			}
+		} else {
+			int pidx;
+			uint8_t *buf = NULL, *pbuf = NULL;
+
+			idx = got_packidx_get_object_idx(packidx,
+			    commit->tree_id);
+			if (idx == -1)
+				break;
+			pidx = got_packidx_get_object_idx(packidx,
+			    pcommit->tree_id);
+			if (pidx == -1)
+				break;
+
+			err = open_tree(&buf, &entries, &nentries, pack,
+			    packidx, idx, commit->tree_id, objcache);
+			if (err)
+				goto done;
+			err = open_tree(&pbuf, &pentries, &pnentries, pack,
+			    packidx, pidx, pcommit->tree_id, objcache);
+			if (err) {
+				free(buf);
+				goto done;
+			}
+
+			err = tree_path_changed(&changed, &buf, &pbuf,
+			    &entries, &nentries, &pentries, &pnentries, path,
+			    pack, packidx, ibuf, objcache);
+
+			got_object_parsed_tree_entries_free(&entries);
+			nentries = 0;
+			free(buf);
+			got_object_parsed_tree_entries_free(&pentries);
+			pnentries = 0;
+			free(pbuf);
+			if (err) {
+				if (err->code != GOT_ERR_NO_OBJ)
+					goto done;
+				err = NULL;
+				break;
+			}
+		}
+
+		if (!changed) {
+			memcpy(id.sha1, pid->id->sha1, SHA1_DIGEST_LENGTH);
+			got_object_commit_close(commit);
+			commit = pcommit;
+			pcommit = NULL;
+		}
+	} while (!changed);
+
+	if (ncommits > 0) {
+		err = got_privsep_send_traversed_commits(commit_ids,
+		    ncommits, ibuf);
+		if (err)
+			goto done;
+
+		if (changed) {
+			err = got_privsep_send_commit(ibuf, commit);
+			if (err)
+				goto done;
+		}
+	}
+	err = got_privsep_send_commit_traversal_done(ibuf);
+done:
+	free(commit_ids);
+	if (commit)
+		got_object_commit_close(commit);
+	if (pcommit)
+		got_object_commit_close(pcommit);
+	if (nentries != 0)
+		got_object_parsed_tree_entries_free(&entries);
+	if (pnentries != 0)
+		got_object_parsed_tree_entries_free(&pentries);
+	if (err) {
+		if (err->code == GOT_ERR_PRIVSEP_PIPE)
+			err = NULL;
+		else
+			got_privsep_send_error(ibuf, err);
+	}
+
+	return err;
+}
+
+static const struct got_error *
 receive_packidx(struct got_packidx **packidx, struct imsgbuf *ibuf)
 {
 	const struct got_error *err = NULL;
@@ -605,6 +959,10 @@ main(int argc, char *argv[])
 		case GOT_IMSG_TAG_REQUEST:
 			err = tag_request(&imsg, &ibuf, pack, packidx,
 			   &objcache);
+			break;
+		case GOT_IMSG_COMMIT_TRAVERSAL_REQUEST:
+			err = commit_traversal_request(&imsg, &ibuf, pack,
+			    packidx, &objcache);
 			break;
 		default:
 			err = got_error(GOT_ERR_PRIVSEP_MSG);