On Mon, Jun 27, 2022 at 11:53:49PM -0600, Tracey Emery wrote:
> On Mon, Jun 27, 2022 at 11:12:30PM +0200, Stefan Sperling wrote:
> > This patch offloads parts of findtwixt() into got-read-pack if possible.
> > This significantly speeds up commit coloring if a large pack file is
> > available.
> > 
> > I have one some light testing, packing and got send still work as
> > expected for me. More testing would be welcome.
> > 
> > ok?
> > 
> 
> Ok with a couple of things below. If I've missed anything, and I
> probably have, because my normal daily-lack-of-sleep-pattern has now
> resumed, we can fix it in the tree.

There was a bug in pinned pack handling where we could end up
sending a commit painting requests to a non-pinned got-read-pack
process, resulting in an unexpected privsep message error.
I found this during 'got send'.

This bug was fixed at the spot where we move a cached pack to the
front of the cache.

+		if (repo->pinned_pack == 0)
+			repo->pinned_pack = i;

becomes:

+		if (repo->pinned_pack == 0)
+			repo->pinned_pack = i;
+		else if (repo->pinned_pack == i)
+			repo->pinned_pack = 0;

And we now store the PID of the pinned got-read-pack helper.
The PID isn't really used for anything, but was very helpful
for debugging and won't hurt, so I decided to leave it in.

diff refs/heads/main refs/heads/findtwixt-pack
commit - 3d589bee0bbbe812bb91f3b0284fbf2596304132
commit + 7105b92e16596bdb1e37984d3ac5e04a91195984
blob - 8ae16da40c07f4dcb3133f9ff08328a10605722b
blob + 22a9264b9f8d0c0b20b48895dd8ea59708e61d48
--- include/got_error.h
+++ include/got_error.h
@@ -168,6 +168,7 @@
 #define GOT_ERR_HUNK_FAILED	150
 #define GOT_ERR_PATCH_FAILED	151
 #define GOT_ERR_FILEIDX_DUP_ENTRY 152
+#define GOT_ERR_PIN_PACK	153
 
 struct got_error {
         int code;
blob - 29541c0234b7f96a4638157fdd9017888571a76c
blob + 8decec3748ea2448a4255cba6eccf77ced9fab2a
--- lib/error.c
+++ lib/error.c
@@ -216,6 +216,7 @@ static const struct got_error got_errors[] = {
 	{ GOT_ERR_HUNK_FAILED, "hunk failed to apply" },
 	{ GOT_ERR_PATCH_FAILED, "patch failed to apply" },
 	{ GOT_ERR_FILEIDX_DUP_ENTRY, "duplicate file index entry" },
+	{ GOT_ERR_PIN_PACK, "could not pin pack file" },
 };
 
 static struct got_custom_error {
blob - bfee6f4277cb3046739bccf25fc842f391a9b670
blob + 24c7c68b7574559306b53c587c4f7d5e5374d02d
--- lib/got_lib_pack.h
+++ lib/got_lib_pack.h
@@ -218,5 +218,3 @@ const struct got_error *got_packfile_extract_object_to
 const struct got_error *got_packfile_extract_raw_delta(uint8_t **, size_t *,
     size_t *, off_t *, off_t *, struct got_object_id *, uint64_t *, uint64_t *,
     struct got_pack *, struct got_packidx *, int);
-struct got_pack *got_repo_get_cached_pack(struct got_repository *,
-    const char *);
blob - 8e99bbe74f6769ad1550cbcbe10d5ff1368d116d
blob + 6ffe646e98676cf9a0d19fe3ad27f3e63ab04fcc
--- lib/got_lib_privsep.h
+++ lib/got_lib_privsep.h
@@ -194,6 +194,12 @@ enum got_imsg_type {
 	GOT_IMSG_REUSED_DELTAS,
 	GOT_IMSG_DELTA_REUSE_DONE,
 
+	/* Commit coloring in got-read-pack. */
+	GOT_IMSG_COMMIT_PAINTING_INIT,
+	GOT_IMSG_COMMIT_PAINTING_REQUEST,
+	GOT_IMSG_PAINTED_COMMITS,
+	GOT_IMSG_COMMIT_PAINTING_DONE,
+
 	/* Transfer a list of object IDs. */
 	GOT_IMSG_OBJ_ID_LIST,
 	GOT_IMSG_OBJ_ID_LIST_DONE,
@@ -344,6 +350,27 @@ struct got_imsg_reused_deltas {
 	/ sizeof(struct got_imsg_reused_delta))
 };
 
+/* Structure for GOT_IMSG_COMMIT_PAINTING_REQUEST. */
+struct got_imsg_commit_painting_request {
+	uint8_t id[SHA1_DIGEST_LENGTH];
+	int idx;
+	int color;
+} __attribute__((__packed__));
+
+/* Structure for GOT_IMSG_PAINTED_COMMITS. */
+struct got_imsg_painted_commit {
+	uint8_t id[SHA1_DIGEST_LENGTH];
+	intptr_t color;
+} __attribute__((__packed__));
+
+struct got_imsg_painted_commits {
+	int ncommits;
+	int present_in_pack;
+	/*
+	 * Followed by ncommits * struct got_imsg_painted_commit.
+	 */
+} __attribute__((__packed__));
+
 /* Structure for GOT_IMSG_TAG data. */
 struct got_imsg_tag_object {
 	uint8_t id[SHA1_DIGEST_LENGTH];
@@ -782,4 +809,16 @@ const struct got_error *got_privsep_send_reused_deltas
 const struct got_error *got_privsep_recv_reused_deltas(int *, 
     struct got_imsg_reused_delta *, size_t *, struct imsgbuf *);
 
+const struct got_error *got_privsep_init_commit_painting(struct imsgbuf *);
+const struct got_error *got_privsep_send_painting_request(struct imsgbuf *,
+    int, struct got_object_id *, intptr_t);
+typedef const struct got_error *(*got_privsep_recv_painted_commit_cb)(void *,
+    struct got_object_id *, intptr_t);
+const struct got_error *got_privsep_send_painted_commits(struct imsgbuf *,
+    struct got_object_id_queue *, int *, int, int);
+const struct got_error *got_privsep_send_painting_commits_done(struct imsgbuf *);
+const struct got_error *got_privsep_recv_painted_commits(
+    struct got_object_id_queue *, got_privsep_recv_painted_commit_cb, void *,
+    struct imsgbuf *);
+
 void got_privsep_exec_child(int[2], const char *, const char *);
blob - c75567b209bd9f2ce134e3ca05a66884b8dcbc04
blob + 02b998107e294bc2eca6ffb21a128c5973771755
--- lib/got_lib_repository.h
+++ lib/got_lib_repository.h
@@ -72,6 +72,16 @@ struct got_repository {
 	 */
 	int pack_cache_size;
 
+	/*
+	 * Index to cache entries which are pinned to avoid eviction.
+	 * This may be used to keep one got-index-pack process alive
+	 * across searches for arbitrary objects which may be stored
+	 * in other pack files.
+	 */
+	int pinned_pack;
+	pid_t pinned_pid;
+	int pinned_packidx;
+
 	/* Handles to child processes for reading loose objects. */
 	struct got_privsep_child privsep_children[5];
 #define GOT_REPO_PRIVSEP_CHILD_OBJECT	0
@@ -134,3 +144,10 @@ const struct got_error *got_repo_get_packidx(struct go
     struct got_repository *);
 const struct got_error *got_repo_cache_pack(struct got_pack **,
     struct got_repository *, const char *, struct got_packidx *);
+struct got_pack *got_repo_get_cached_pack(struct got_repository *,
+    const char *);
+const struct got_error *got_repo_pin_pack(struct got_repository *,
+    struct got_packidx *, struct got_pack *);
+struct got_pack *got_repo_get_pinned_pack(struct got_repository *);
+void got_repo_unpin_pack(struct got_repository *);
+
blob - 16d1a758fc03fec245de789888abc9cb072f408d
blob + 4ab652c3f6cf093947a9bbce2173c764fb9cb44e
--- lib/pack_create.c
+++ lib/pack_create.c
@@ -563,6 +563,28 @@ send_id(struct got_object_id *id, void *data, void *ar
 }
 
 static const struct got_error *
+send_idset(struct imsgbuf *ibuf, struct got_object_idset *idset)
+{
+	const struct got_error *err;
+	struct send_id_arg sia;
+
+	memset(&sia, 0, sizeof(sia));
+	sia.ibuf = ibuf;
+	err = got_object_idset_for_each(idset, send_id, &sia);
+	if (err)
+		return err;
+
+	if (sia.nids > 0) {
+		err = got_privsep_send_object_idlist(ibuf, sia.ids, sia.nids);
+		if (err)
+			return err;
+	}
+
+	return got_privsep_send_object_idlist_done(ibuf);
+}
+
+
+static const struct got_error *
 recv_reused_delta(struct got_imsg_reused_delta *delta,
     struct got_object_idset *idset, struct got_pack_metavec *v)
 {
@@ -595,10 +617,10 @@ recv_reused_delta(struct got_imsg_reused_delta *delta,
 }
 
 static const struct got_error *
-prepare_delta_reuse(struct got_pack **pack, struct got_packidx *packidx,
-    int delta_outfd, struct got_repository *repo)
+cache_pack_for_packidx(struct got_pack **pack, struct got_packidx *packidx,
+    struct got_repository *repo)
 {
-	const struct got_error *err = NULL;
+	const struct got_error *err;
 	char *path_packfile = NULL;
 
 	err = got_packidx_get_packfile_path(&path_packfile,
@@ -617,8 +639,18 @@ prepare_delta_reuse(struct got_pack **pack, struct got
 		if (err)
 			goto done;
 	}
+done:
+	free(path_packfile);
+	return NULL;
+}
 
-	if (!(*pack)->child_has_delta_outfd) {
+static const struct got_error *
+prepare_delta_reuse(struct got_pack *pack, struct got_packidx *packidx,
+    int delta_outfd, struct got_repository *repo)
+{
+	const struct got_error *err = NULL;
+
+	if (!pack->child_has_delta_outfd) {
 		int outfd_child;
 		outfd_child = dup(delta_outfd);
 		if (outfd_child == -1) {
@@ -626,15 +658,14 @@ prepare_delta_reuse(struct got_pack **pack, struct got
 			goto done;
 		}
 		err = got_privsep_send_raw_delta_outfd(
-		    (*pack)->privsep_child->ibuf, outfd_child);
+		    pack->privsep_child->ibuf, outfd_child);
 		if (err)
 			goto done;
-		(*pack)->child_has_delta_outfd = 1;
+		pack->child_has_delta_outfd = 1;
 	}
 
-	err = got_privsep_send_delta_reuse_req((*pack)->privsep_child->ibuf);
+	err = got_privsep_send_delta_reuse_req(pack->privsep_child->ibuf);
 done:
-	free(path_packfile);
 	return err;
 }
 
@@ -649,7 +680,6 @@ search_deltas(struct got_pack_metavec *v, struct got_o
 	const struct got_error *err = NULL;
 	struct got_packidx *packidx;
 	struct got_pack *pack;
-	struct send_id_arg sia;
 	struct got_imsg_reused_delta deltas[GOT_IMSG_REUSED_DELTAS_MAX_NDELTAS];
 	size_t ndeltas, i;
 
@@ -660,22 +690,15 @@ search_deltas(struct got_pack_metavec *v, struct got_o
 	if (packidx == NULL)
 		return NULL;
 
-	err = prepare_delta_reuse(&pack, packidx, delta_cache_fd, repo);
+	err = cache_pack_for_packidx(&pack, packidx, repo);
 	if (err)
 		return err;
 
-	memset(&sia, 0, sizeof(sia));
-	sia.ibuf = pack->privsep_child->ibuf;
-	err = got_object_idset_for_each(idset, send_id, &sia);
+	err = prepare_delta_reuse(pack, packidx, delta_cache_fd, repo);
 	if (err)
 		return err;
-	if (sia.nids > 0) {
-		err = got_privsep_send_object_idlist(pack->privsep_child->ibuf,
-		    sia.ids, sia.nids);
-		if (err)
-			return err;
-	}
-	err = got_privsep_send_object_idlist_done(pack->privsep_child->ibuf);
+
+	err = send_idset(pack->privsep_child->ibuf, idset);
 	if (err)
 		return err;
 
@@ -1217,30 +1240,23 @@ done:
 enum findtwixt_color {
 	COLOR_KEEP = 0,
 	COLOR_DROP,
-	COLOR_BLANK,
 	COLOR_SKIP,
+	COLOR_MAX,
 };
 
-static const int findtwixt_colors[] = {
-	COLOR_KEEP,
-	COLOR_DROP,
-	COLOR_BLANK,
-	COLOR_SKIP,
-};
-
 static const struct got_error *
-paint_commit(struct got_object_qid *qid, int color)
+paint_commit(struct got_object_qid *qid, intptr_t color)
 {
-	if (color < 0 || color >= nitems(findtwixt_colors))
+	if (color < 0 || color >= COLOR_MAX)
 		return got_error(GOT_ERR_RANGE);
 
-	qid->data = (void *)&findtwixt_colors[color];
+	qid->data = (void *)color;
 	return NULL;
 }
 
 static const struct got_error *
 queue_commit_id(struct got_object_id_queue *ids, struct got_object_id *id,
-    int color, struct got_repository *repo)
+    intptr_t color, struct got_repository *repo)
 {
 	const struct got_error *err;
 	struct got_object_qid *qid;
@@ -1277,7 +1293,7 @@ append_id(struct got_object_id *id, void *data, void *
 }
 
 static const struct got_error *
-queue_commit_or_tag_id(struct got_object_id *id, int color,
+queue_commit_or_tag_id(struct got_object_id *id, intptr_t color,
     struct got_object_id_queue *ids, struct got_repository *repo)
 {
 	const struct got_error *err;
@@ -1307,7 +1323,197 @@ done:
 	return err;
 }
 
+struct recv_painted_commit_arg {
+	int *ncolored;
+	int *nqueued;
+	int *nskip;
+	struct got_object_id_queue *ids;
+	struct got_object_idset *keep;
+	struct got_object_idset *drop;
+	struct got_object_idset *skip;
+	got_pack_progress_cb progress_cb;
+	void *progress_arg;
+	struct got_ratelimit *rl;
+	got_cancel_cb cancel_cb;
+	void *cancel_arg;
+};
+
 static const struct got_error *
+recv_painted_commit(void *arg, struct got_object_id *id, intptr_t color)
+{
+	const struct got_error *err = NULL;
+	struct recv_painted_commit_arg *a = arg;
+	struct got_object_qid *qid, *tmp;
+
+	if (a->cancel_cb) {
+		err = a->cancel_cb(a->cancel_arg);
+		if (err)
+			return err;
+	}
+
+	switch (color) {
+	case COLOR_KEEP:
+		err = got_object_idset_add(a->keep, id, NULL);
+		if (err)
+			return err;
+		(*a->ncolored)++;
+		break;
+	case COLOR_DROP:
+		err = got_object_idset_add(a->drop, id, NULL);
+		if (err)
+			return err;
+		(*a->ncolored)++;
+		break;
+	case COLOR_SKIP:
+		err = got_object_idset_add(a->skip, id, NULL);
+		if (err)
+			return err;
+		break;
+	default:
+		/* should not happen */
+		return got_error_fmt(GOT_ERR_NOT_IMPL,
+		    "%s invalid commit color %d", __func__, color);
+	}
+
+	STAILQ_FOREACH_SAFE(qid, a->ids, entry, tmp) {
+		if (got_object_id_cmp(&qid->id, id) != 0)
+			continue;
+		STAILQ_REMOVE(a->ids, qid, got_object_qid, entry);
+		color = (intptr_t)qid->data;
+		got_object_qid_free(qid);
+		(*a->nqueued)--;
+		if (color == COLOR_SKIP)
+			(*a->nskip)--;
+		break;
+	}
+
+	return report_progress(a->progress_cb, a->progress_arg, a->rl,
+	    *a->ncolored, 0, 0, 0L, 0, 0, 0, 0);
+}
+
+static const struct got_error *
+paint_packed_commits(struct got_pack *pack, struct got_object_id *id,
+    int idx, intptr_t color, int *ncolored, int *nqueued, int *nskip,
+    struct got_object_id_queue *ids,
+    struct got_object_idset *keep, struct got_object_idset *drop,
+    struct got_object_idset *skip, struct got_repository *repo,
+    got_pack_progress_cb progress_cb, void *progress_arg,
+    struct got_ratelimit *rl, got_cancel_cb cancel_cb, void *cancel_arg)
+{
+	const struct got_error *err = NULL;
+	struct got_object_id_queue next_ids;
+	struct got_object_qid *qid, *tmp;
+	struct recv_painted_commit_arg arg;
+
+	STAILQ_INIT(&next_ids);
+
+	err = got_privsep_send_painting_request(pack->privsep_child->ibuf,
+	    idx, id, color);
+	if (err)
+		return err;
+
+	arg.ncolored = ncolored;
+	arg.nqueued = nqueued;
+	arg.nskip = nskip;
+	arg.ids = ids;
+	arg.keep = keep;
+	arg.drop = drop;
+	arg.skip = skip;
+	arg.progress_cb = progress_cb;
+	arg.progress_arg = progress_arg;
+	arg.rl = rl;
+	arg.cancel_cb = cancel_cb;
+	arg.cancel_arg = cancel_arg;
+	err = got_privsep_recv_painted_commits(&next_ids,
+	    recv_painted_commit, &arg, pack->privsep_child->ibuf);
+	if (err)
+		return err;
+
+	STAILQ_FOREACH_SAFE(qid, &next_ids, entry, tmp) {
+		struct got_object_qid *old_id;
+		intptr_t qcolor, ocolor;
+		STAILQ_FOREACH(old_id, ids, entry) {
+			if (got_object_id_cmp(&qid->id, &old_id->id))
+				continue;
+			qcolor = (intptr_t)qid->data;
+			ocolor = (intptr_t)old_id->data;
+			STAILQ_REMOVE(&next_ids, qid, got_object_qid, entry);
+			got_object_qid_free(qid);
+			qid = NULL;
+			if (qcolor != ocolor) {
+				paint_commit(old_id, qcolor);
+				if (ocolor == COLOR_SKIP)
+					(*nskip)--;
+				else if (qcolor == COLOR_SKIP)
+					(*nskip)++;
+			}
+			break;
+		}
+	}
+	while (!STAILQ_EMPTY(&next_ids)) {
+		qid = STAILQ_FIRST(&next_ids);
+		STAILQ_REMOVE_HEAD(&next_ids, entry);
+		paint_commit(qid, color);
+		STAILQ_INSERT_TAIL(ids, qid, entry);
+		(*nqueued)++;
+		if (color == COLOR_SKIP)
+			(*nskip)++;
+	}
+
+	return err;
+}
+
+static const struct got_error *
+find_pack_for_commit_painting(struct got_packidx **best_packidx,
+    struct got_object_id_queue *ids, int nids, struct got_repository *repo)
+{
+	const struct got_error *err = NULL;
+	struct got_pathlist_entry *pe;
+	const char *best_packidx_path = NULL;
+	int nobj_max = 0;
+	int ncommits_max = 0;
+
+	*best_packidx = NULL;
+
+	/*
+	 * Find the largest pack which contains at least some of the
+	 * commits we are interested in.
+	 */
+	TAILQ_FOREACH(pe, &repo->packidx_paths, entry) {
+		const char *path_packidx = pe->path;
+		struct got_packidx *packidx;
+		int nobj, idx, ncommits = 0;
+		struct got_object_qid *qid;
+
+		err = got_repo_get_packidx(&packidx, path_packidx, repo);
+		if (err)
+			break;
+
+		nobj = be32toh(packidx->hdr.fanout_table[0xff]);
+		if (nobj <= nobj_max)
+			continue;
+
+		STAILQ_FOREACH(qid, ids, entry) {
+			idx = got_packidx_get_object_idx(packidx, &qid->id);
+			if (idx != -1)
+				ncommits++;
+		}
+		if (ncommits > ncommits_max) {
+			best_packidx_path = path_packidx;
+			nobj_max = nobj;
+			ncommits_max = ncommits;
+		}
+	}
+
+	if (best_packidx_path && err == NULL) {
+		err = got_repo_get_packidx(best_packidx, best_packidx_path,
+		    repo);
+	}
+
+	return err;
+}
+
+static const struct got_error *
 paint_commits(int *ncolored, struct got_object_id_queue *ids, int nids,
     struct got_object_idset *keep, struct got_object_idset *drop,
     struct got_object_idset *skip, struct got_repository *repo,
@@ -1316,12 +1522,15 @@ paint_commits(int *ncolored, struct got_object_id_queu
 {
 	const struct got_error *err = NULL;
 	struct got_commit_object *commit = NULL;
+	struct got_packidx *packidx = NULL;
+	struct got_pack *pack = NULL;
 	const struct got_object_id_queue *parents;
-	struct got_object_qid *qid;
+	struct got_object_qid *qid = NULL;
 	int nqueued = nids, nskip = 0;
+	int idx;
 
 	while (!STAILQ_EMPTY(ids) && nskip != nqueued) {
-		int color;
+		intptr_t color;
 
 		if (cancel_cb) {
 			err = cancel_cb(cancel_arg);
@@ -1332,21 +1541,49 @@ paint_commits(int *ncolored, struct got_object_id_queu
 		qid = STAILQ_FIRST(ids);
 		STAILQ_REMOVE_HEAD(ids, entry);
 		nqueued--;
-		color = *((int *)qid->data);
+		color = (intptr_t)qid->data;
 		if (color == COLOR_SKIP)
 			nskip--;
 
 		if (got_object_idset_contains(skip, &qid->id)) {
 			got_object_qid_free(qid);
+			qid = NULL;
 			continue;
 		}
+		if (color == COLOR_KEEP &&
+		    got_object_idset_contains(keep, &qid->id)) {
+			got_object_qid_free(qid);
+			qid = NULL;
+			continue;
+		}
+		if (color == COLOR_DROP &&
+		    got_object_idset_contains(drop, &qid->id)) {
+			got_object_qid_free(qid);
+			qid = NULL;
+			continue;
+		}
 
+		/* Pinned pack may have moved to different cache slot. */
+		pack = got_repo_get_pinned_pack(repo);
+
+		if (packidx && pack) {
+			idx = got_packidx_get_object_idx(packidx, &qid->id);
+			if (idx != -1) {
+				err = paint_packed_commits(pack, &qid->id,
+				    idx, color, ncolored, &nqueued, &nskip,
+				    ids, keep, drop, skip, repo,
+				    progress_cb, progress_arg, rl,
+				    cancel_cb, cancel_arg);
+				if (err)
+					break;
+				got_object_qid_free(qid);
+				qid = NULL;
+				continue;
+			}
+		}
+
 		switch (color) {
 		case COLOR_KEEP:
-			if (got_object_idset_contains(keep, &qid->id)) {
-				got_object_qid_free(qid);
-				continue;
-			}
 			if (got_object_idset_contains(drop, &qid->id)) {
 				err = paint_commit(qid, COLOR_SKIP);
 				if (err)
@@ -1358,10 +1595,6 @@ paint_commits(int *ncolored, struct got_object_id_queu
 				goto done;
 			break;
 		case COLOR_DROP:
-			if (got_object_idset_contains(drop, &qid->id)) {
-				got_object_qid_free(qid);
-				continue;
-			}
 			if (got_object_idset_contains(keep, &qid->id)) {
 				err = paint_commit(qid, COLOR_SKIP);
 				if (err)
@@ -1392,7 +1625,6 @@ paint_commits(int *ncolored, struct got_object_id_queu
 		if (err)
 			break;
 
-
 		err = got_object_open_as_commit(&commit, repo, &qid->id);
 		if (err)
 			break;
@@ -1400,10 +1632,10 @@ paint_commits(int *ncolored, struct got_object_id_queu
 		parents = got_object_commit_get_parent_ids(commit);
 		if (parents) {
 			struct got_object_qid *pid;
-			color = *((int *)qid->data);
+			color = (intptr_t)qid->data;
 			STAILQ_FOREACH(pid, parents, entry) {
-				err = queue_commit_id(ids, &pid->id, color,
-				    repo);
+				err = queue_commit_id(ids, &pid->id,
+				    color, repo);
 				if (err)
 					break;
 				nqueued++;
@@ -1412,13 +1644,56 @@ paint_commits(int *ncolored, struct got_object_id_queu
 			}
 		}
 
+		if (pack == NULL && (commit->flags & GOT_COMMIT_FLAG_PACKED)) {
+			if (packidx == NULL) {
+				err = find_pack_for_commit_painting(&packidx,
+				    ids, nqueued, repo);
+				if (err)
+					goto done;
+			}
+			if (packidx != NULL) {
+				err = cache_pack_for_packidx(&pack, packidx,
+				    repo);
+				if (err)
+					goto done;
+				err = got_privsep_init_commit_painting(
+				    pack->privsep_child->ibuf);
+				if (err)
+					goto done;
+				err = send_idset(pack->privsep_child->ibuf,
+				    keep);
+				if (err)
+					goto done;
+				err = send_idset(pack->privsep_child->ibuf, drop);
+				if (err)
+					goto done;
+				err = send_idset(pack->privsep_child->ibuf, skip);
+				if (err)
+					goto done;
+				err = got_repo_pin_pack(repo, packidx, pack);
+				if (err)
+					goto done;
+			}
+		}
+
 		got_object_commit_close(commit);
 		commit = NULL;
+
 		got_object_qid_free(qid);
+		qid = NULL;
 	}
 done:
+	if (pack) {
+		const struct got_error *pack_err;
+		pack_err = got_privsep_send_painting_commits_done(
+		    pack->privsep_child->ibuf);
+		if (err == NULL)
+			err = pack_err;
+	}
 	if (commit)
 		got_object_commit_close(commit);
+	got_object_qid_free(qid);
+	got_repo_unpin_pack(repo);
 	return err;
 }
 
blob - 70eb167c5ee71b29c045bdae0de5c7b7859403f7
blob + c0bdac7221a79c5ec97d1728e862406152d51eb9
--- lib/privsep.c
+++ lib/privsep.c
@@ -3328,6 +3328,182 @@ got_privsep_recv_reused_deltas(int *done, struct got_i
 }
 
 const struct got_error *
+got_privsep_init_commit_painting(struct imsgbuf *ibuf)
+{
+	if (imsg_compose(ibuf, GOT_IMSG_COMMIT_PAINTING_INIT,
+	    0, 0, -1, NULL, 0)
+	    == -1)
+		return got_error_from_errno("imsg_compose "
+		    "COMMIT_PAINTING_INIT");
+
+	return flush_imsg(ibuf);
+}
+
+const struct got_error *
+got_privsep_send_painting_request(struct imsgbuf *ibuf, int idx,
+    struct got_object_id *id, intptr_t color)
+{
+	struct got_imsg_commit_painting_request ireq;
+
+	memset(&ireq, 0, sizeof(ireq));
+	memcpy(ireq.id, id->sha1, sizeof(ireq.id));
+	ireq.idx = idx;
+	ireq.color = color;
+
+	if (imsg_compose(ibuf, GOT_IMSG_COMMIT_PAINTING_REQUEST, 0, 0, -1,
+	    &ireq, sizeof(ireq)) == -1)
+		return got_error_from_errno("imsg_compose "
+		    "COMMIT_PAINTING_REQUEST");
+
+	return flush_imsg(ibuf);
+}
+
+static const struct got_error *
+send_painted_commits(struct got_object_id_queue *ids, int *nids,
+    size_t remain, int present_in_pack, struct imsgbuf *ibuf)
+{
+	const struct got_error *err = NULL;
+	struct ibuf *wbuf = NULL;
+	struct got_object_qid *qid;
+	size_t msglen;
+	int ncommits;
+	intptr_t color;
+
+	msglen = MIN(remain, MAX_IMSGSIZE - IMSG_HEADER_SIZE);
+	ncommits = (msglen - sizeof(struct got_imsg_painted_commits)) /
+	    sizeof(struct got_imsg_painted_commit);
+
+	wbuf = imsg_create(ibuf, GOT_IMSG_PAINTED_COMMITS, 0, 0, msglen);
+	if (wbuf == NULL) {
+		err = got_error_from_errno("imsg_create PAINTED_COMMITS");
+		return err;
+	}
+
+	/* Keep in sync with struct got_imsg_painted_commits! */
+	if (imsg_add(wbuf, &ncommits, sizeof(ncommits)) == -1)
+		return got_error_from_errno("imsg_add PAINTED_COMMITS");
+	if (imsg_add(wbuf, &present_in_pack, sizeof(present_in_pack)) == -1)
+		return got_error_from_errno("imsg_add PAINTED_COMMITS");
+
+	while (ncommits > 0) {
+		qid = STAILQ_FIRST(ids);
+		STAILQ_REMOVE_HEAD(ids, entry);
+		ncommits--;
+		(*nids)--;
+		color = (intptr_t)qid->data;
+
+		/* Keep in sync with struct got_imsg_painted_commit! */
+		if (imsg_add(wbuf, qid->id.sha1, SHA1_DIGEST_LENGTH) == -1)
+			return got_error_from_errno("imsg_add PAINTED_COMMITS");
+		if (imsg_add(wbuf, &color, sizeof(color)) == -1)
+			return got_error_from_errno("imsg_add PAINTED_COMMITS");
+
+		got_object_qid_free(qid);
+	}
+
+	wbuf->fd = -1;
+	imsg_close(ibuf, wbuf);
+
+	return flush_imsg(ibuf);
+}
+
+const struct got_error *
+got_privsep_send_painted_commits(struct imsgbuf *ibuf,
+    struct got_object_id_queue *ids, int *nids,
+    int present_in_pack, int flush)
+{
+	const struct got_error *err;
+	size_t remain;
+
+	if (*nids <= 0)
+		return NULL;
+
+	do {
+		remain = (sizeof(struct got_imsg_painted_commits)) +
+		    *nids * sizeof(struct got_imsg_painted_commit);
+		if (flush || remain >= MAX_IMSGSIZE - IMSG_HEADER_SIZE) {
+			err = send_painted_commits(ids, nids, remain,
+			    present_in_pack, ibuf);
+			if (err)
+				return err;
+		}
+	} while (flush && *nids > 0);
+
+	return NULL;
+}
+
+const struct got_error *
+got_privsep_send_painting_commits_done(struct imsgbuf *ibuf)
+{
+	if (imsg_compose(ibuf, GOT_IMSG_COMMIT_PAINTING_DONE,
+	    0, 0, -1, NULL, 0)
+	    == -1)
+		return got_error_from_errno("imsg_compose "
+		    "COMMIT_PAINTING_DONE");
+
+	return flush_imsg(ibuf);
+}
+
+const struct got_error *
+got_privsep_recv_painted_commits(struct got_object_id_queue *new_ids,
+    got_privsep_recv_painted_commit_cb cb, void *cb_arg, struct imsgbuf *ibuf)
+{
+	const struct got_error *err = NULL;
+	struct imsg imsg;
+	struct got_imsg_painted_commits icommits;
+	struct got_imsg_painted_commit icommit;
+	size_t datalen;
+	int i;
+
+	for (;;) {
+		err = got_privsep_recv_imsg(&imsg, ibuf, 0);
+		if (err)
+			return err;
+
+		datalen = imsg.hdr.len - IMSG_HEADER_SIZE;
+		if (imsg.hdr.type == GOT_IMSG_COMMIT_PAINTING_DONE)
+			break;
+		if (imsg.hdr.type != GOT_IMSG_PAINTED_COMMITS)
+			return got_error(GOT_ERR_PRIVSEP_MSG);
+
+		if (datalen < sizeof(icommits))
+			return got_error(GOT_ERR_PRIVSEP_LEN);
+		memcpy(&icommits, imsg.data, sizeof(icommits));
+		if (icommits.ncommits * sizeof(icommit) < icommits.ncommits ||
+		    datalen < sizeof(icommits) +
+		    icommits.ncommits * sizeof(icommit))
+			return got_error(GOT_ERR_PRIVSEP_LEN);
+
+		for (i = 0; i < icommits.ncommits; i++) {
+			memcpy(&icommit,
+			    (uint8_t *)imsg.data + sizeof(icommits) + i * sizeof(icommit),
+			    sizeof(icommit));
+
+			if (icommits.present_in_pack) {
+				struct got_object_id id;
+				memcpy(id.sha1, icommit.id, SHA1_DIGEST_LENGTH);
+				err = cb(cb_arg, &id, icommit.color);
+				if (err)
+					break;
+			} else {
+				struct got_object_qid *qid;
+				err = got_object_qid_alloc_partial(&qid);
+				if (err)
+					break;
+				memcpy(qid->id.sha1, icommit.id,
+				    SHA1_DIGEST_LENGTH);
+				qid->data = (void *)icommit.color;
+				STAILQ_INSERT_TAIL(new_ids, qid, entry);
+			}
+		}
+
+		imsg_free(&imsg);
+	}
+
+	return err;
+}
+
+const struct got_error *
 got_privsep_unveil_exec_helpers(void)
 {
 	const char *helpers[] = {
blob - 4aba251d6858a54219d51424919806df0ad2b260
blob + 4c93c601016c47cab8439703f5925c65095b4b7e
--- lib/repository.c
+++ lib/repository.c
@@ -752,6 +752,9 @@ got_repo_open(struct got_repository **repop, const cha
 			repo->packs[i].accumfd = -1;
 		}
 	}
+	repo->pinned_pack = -1;
+	repo->pinned_packidx = -1;
+	repo->pinned_pid = 0;
 
 	repo_path = realpath(path, NULL);
 	if (repo_path == NULL) {
@@ -1035,7 +1038,10 @@ cache_packidx(struct got_repository *repo, struct got_
 		}
 	}
 	if (i == repo->pack_cache_size) {
-		i = repo->pack_cache_size - 1;
+		do {
+			i--;
+		} while (i > 0 && repo->pinned_packidx >= 0 &&
+		    i == repo->pinned_packidx);
 		err = got_packidx_close(repo->packidx_cache[i]);
 		if (err)
 			return err;
@@ -1171,6 +1177,11 @@ got_repo_search_packidx(struct got_packidx **packidx, 
 				    &repo->packidx_cache[0],
 				    i * sizeof(repo->packidx_cache[0]));
 				repo->packidx_cache[0] = *packidx;
+				if (repo->pinned_packidx >= 0 &&
+				    repo->pinned_packidx < i)
+					repo->pinned_packidx++;
+				else if (repo->pinned_packidx == i)
+					repo->pinned_packidx = 0;
 			}
 			return NULL;
 		}
@@ -1375,17 +1386,25 @@ got_repo_cache_pack(struct got_pack **packp, struct go
 
 	if (i == repo->pack_cache_size) {
 		struct got_pack tmp;
-		err = got_pack_close(&repo->packs[i - 1]);
+		do {
+			i--;
+		} while (i > 0 && repo->pinned_pack >= 0 &&
+		    i == repo->pinned_pack);
+		err = got_pack_close(&repo->packs[i]);
 		if (err)
 			return err;
-		if (ftruncate(repo->packs[i - 1].basefd, 0L) == -1)
+		if (ftruncate(repo->packs[i].basefd, 0L) == -1)
 			return got_error_from_errno("ftruncate");
-		if (ftruncate(repo->packs[i - 1].accumfd, 0L) == -1)
+		if (ftruncate(repo->packs[i].accumfd, 0L) == -1)
 			return got_error_from_errno("ftruncate");
-		memcpy(&tmp, &repo->packs[i - 1], sizeof(tmp)); 
-		memcpy(&repo->packs[i - 1], &repo->packs[0],
-		    sizeof(repo->packs[i - 1]));
+		memcpy(&tmp, &repo->packs[i], sizeof(tmp)); 
+		memcpy(&repo->packs[i], &repo->packs[0],
+		    sizeof(repo->packs[i]));
 		memcpy(&repo->packs[0], &tmp, sizeof(repo->packs[0]));
+		if (repo->pinned_pack == 0)
+			repo->pinned_pack = i;
+		else if (repo->pinned_pack == i)
+			repo->pinned_pack = 0;
 		i = 0;
 	}
 
@@ -1449,6 +1468,51 @@ got_repo_get_cached_pack(struct got_repository *repo, 
 }
 
 const struct got_error *
+got_repo_pin_pack(struct got_repository *repo, struct got_packidx *packidx,
+    struct got_pack *pack)
+{
+	size_t i;
+	int pinned_pack = -1, pinned_packidx = -1;
+
+	for (i = 0; i < repo->pack_cache_size; i++) {
+		if (repo->packidx_cache[i] &&
+		    strcmp(repo->packidx_cache[i]->path_packidx,
+		    packidx->path_packidx) == 0)
+			pinned_packidx = i;
+		if (repo->packs[i].path_packfile &&
+		    strcmp(repo->packs[i].path_packfile,
+		    pack->path_packfile) == 0)
+			pinned_pack = i;
+	}
+
+	if (pinned_packidx == -1 || pinned_pack == -1)
+		return got_error(GOT_ERR_PIN_PACK);
+
+	repo->pinned_pack = pinned_pack;
+	repo->pinned_packidx = pinned_packidx;
+	repo->pinned_pid = repo->packs[pinned_pack].privsep_child->pid;
+	return NULL;
+}
+
+struct got_pack *
+got_repo_get_pinned_pack(struct got_repository *repo)
+{
+	if (repo->pinned_pack >= 0 &&
+	    repo->pinned_pack < repo->pack_cache_size)
+		return &repo->packs[repo->pinned_pack];
+
+	return NULL;
+}
+
+void
+got_repo_unpin_pack(struct got_repository *repo)
+{
+	repo->pinned_packidx = -1;
+	repo->pinned_pack = -1;
+	repo->pinned_pid = 0;
+}
+
+const struct got_error *
 got_repo_init(const char *repo_path)
 {
 	const struct got_error *err = NULL;
blob - 71fcef93a4f835b8c00eda8b486c0c1a7aef8fe8
blob + 30401fee605c3b7937f25d1f3c8f216c945c9525
--- libexec/got-read-pack/got-read-pack.c
+++ libexec/got-read-pack/got-read-pack.c
@@ -45,6 +45,10 @@
 #include "got_lib_privsep.h"
 #include "got_lib_pack.h"
 
+#ifndef nitems
+#define nitems(_a)	(sizeof((_a)) / sizeof((_a)[0]))
+#endif
+
 static volatile sig_atomic_t sigint_received;
 
 static void
@@ -1540,7 +1544,273 @@ done:
 	return err;
 }
 
+enum findtwixt_color {
+	COLOR_KEEP = 0,
+	COLOR_DROP,
+	COLOR_SKIP,
+	COLOR_MAX,
+};
+
 static const struct got_error *
+paint_commit(struct got_object_qid *qid, intptr_t color)
+{
+	if (color < 0 || color >= COLOR_MAX)
+		return got_error(GOT_ERR_RANGE);
+
+	qid->data = (void *)color;
+	return NULL;
+}
+
+static const struct got_error *
+queue_commit_id(struct got_object_id_queue *ids, struct got_object_id *id,
+    intptr_t color)
+{
+	const struct got_error *err;
+	struct got_object_qid *qid;
+
+	err = got_object_qid_alloc_partial(&qid);
+	if (err)
+		return err;
+
+	memcpy(&qid->id, id, sizeof(qid->id));
+	STAILQ_INSERT_TAIL(ids, qid, entry);
+	return paint_commit(qid, color);
+}
+
+static const struct got_error *
+paint_commits(struct got_object_id_queue *ids, int *nids,
+    struct got_object_idset *keep, struct got_object_idset *drop,
+    struct got_object_idset *skip, struct got_pack *pack,
+    struct got_packidx *packidx, struct imsgbuf *ibuf,
+    struct got_object_cache *objcache)
+{
+	const struct got_error *err = NULL;
+	struct got_commit_object *commit = NULL;
+	struct got_object_id_queue painted;
+	const struct got_object_id_queue *parents;
+	struct got_object_qid *qid = NULL;
+	int nqueued = *nids, nskip = 0, npainted = 0;
+
+	STAILQ_INIT(&painted);
+
+	while (!STAILQ_EMPTY(ids) && nskip != nqueued) {
+		int idx;
+		intptr_t color;
+
+		if (sigint_received) {
+			err = got_error(GOT_ERR_CANCELLED);
+			goto done;
+		}
+
+		qid = STAILQ_FIRST(ids);
+		idx = got_packidx_get_object_idx(packidx, &qid->id);
+		if (idx == -1) {
+			qid = NULL;
+			break;
+		}
+
+		STAILQ_REMOVE_HEAD(ids, entry);
+		nqueued--;
+		color = (intptr_t)qid->data;
+		if (color == COLOR_SKIP)
+			nskip--;
+
+		if (got_object_idset_contains(skip, &qid->id)) {
+			got_object_qid_free(qid);
+			qid = NULL;
+			continue;
+		}
+
+		switch (color) {
+		case COLOR_KEEP:
+			if (got_object_idset_contains(keep, &qid->id)) {
+				got_object_qid_free(qid);
+				qid = NULL;
+				continue;
+			}
+			if (got_object_idset_contains(drop, &qid->id)) {
+				err = paint_commit(qid, COLOR_SKIP);
+				if (err)
+					goto done;
+			}
+			err = got_object_idset_add(keep, &qid->id, NULL);
+			if (err)
+				goto done;
+			break;
+		case COLOR_DROP:
+			if (got_object_idset_contains(drop, &qid->id)) {
+				got_object_qid_free(qid);
+				qid = NULL;
+				continue;
+			}
+			if (got_object_idset_contains(keep, &qid->id)) {
+				err = paint_commit(qid, COLOR_SKIP);
+				if (err)
+					goto done;
+			}
+			err = got_object_idset_add(drop, &qid->id, NULL);
+			if (err)
+				goto done;
+			break;
+		case COLOR_SKIP:
+			if (!got_object_idset_contains(skip, &qid->id)) {
+				err = got_object_idset_add(skip, &qid->id,
+				    NULL);
+				if (err)
+					goto done;
+			}
+			break;
+		default:
+			/* should not happen */
+			err = got_error_fmt(GOT_ERR_NOT_IMPL,
+			    "%s invalid commit color %d", __func__, color);
+			goto done;
+		}
+
+		err = open_commit(&commit, pack, packidx, idx, &qid->id,
+		    objcache);
+		if (err)
+			goto done;
+
+		parents = got_object_commit_get_parent_ids(commit);
+		if (parents) {
+			struct got_object_qid *pid;
+			color = (intptr_t)qid->data;
+			STAILQ_FOREACH(pid, parents, entry) {
+				err = queue_commit_id(ids, &pid->id, color);
+				if (err)
+					goto done;
+				nqueued++;
+				if (color == COLOR_SKIP)
+					nskip++;
+			}
+		}
+
+		got_object_commit_close(commit);
+		commit = NULL;
+
+		STAILQ_INSERT_TAIL(&painted, qid, entry);
+		qid = NULL;
+		npainted++;
+
+		err = got_privsep_send_painted_commits(ibuf, &painted,
+		    &npainted, 1, 0);
+		if (err)
+			goto done;
+	}
+
+	err = got_privsep_send_painted_commits(ibuf, &painted, &npainted, 1, 1);
+	if (err)
+		goto done;
+
+	*nids = nqueued;
+done:
+	if (commit)
+		got_object_commit_close(commit);
+	got_object_qid_free(qid);
+	return err;
+}
+
+static void
+commit_painting_free(struct got_object_idset **keep,
+    struct got_object_idset **drop,
+    struct got_object_idset **skip)
+{
+	if (*keep) {
+		got_object_idset_free(*keep);
+		*keep = NULL;
+	}
+	if (*drop) {
+		got_object_idset_free(*drop);
+		*drop = NULL;
+	}
+	if (*skip) {
+		got_object_idset_free(*skip); 
+		*skip = NULL;
+	}
+}
+
+static const struct got_error *
+commit_painting_init(struct imsgbuf *ibuf, struct got_object_idset **keep,
+    struct got_object_idset **drop, struct got_object_idset **skip)
+{
+	const struct got_error *err = NULL;
+
+	*keep = got_object_idset_alloc();
+	if (*keep == NULL) {
+		err = got_error_from_errno("got_object_idset_alloc");
+		goto done;
+	}
+	*drop = got_object_idset_alloc();
+	if (*drop == NULL) {
+		err = got_error_from_errno("got_object_idset_alloc");
+		goto done;
+	}
+	*skip = got_object_idset_alloc();
+	if (*skip == NULL) {
+		err = got_error_from_errno("got_object_idset_alloc");
+		goto done;
+	}
+
+	err = recv_object_ids(*keep, ibuf);
+	if (err)
+		goto done;
+	err = recv_object_ids(*drop, ibuf);
+	if (err)
+		goto done;
+	err = recv_object_ids(*skip, ibuf);
+	if (err)
+		goto done;
+
+done:
+	if (err)
+		commit_painting_free(keep, drop, skip);
+
+	return err;
+}
+
+static const struct got_error *
+commit_painting_request(struct imsg *imsg, struct imsgbuf *ibuf,
+    struct got_pack *pack, struct got_packidx *packidx,
+    struct got_object_cache *objcache, struct got_object_idset *keep,
+    struct got_object_idset *drop, struct got_object_idset *skip)
+{
+	const struct got_error *err = NULL;
+	struct got_imsg_commit_painting_request ireq;
+	struct got_object_id id;
+	size_t datalen;
+	struct got_object_id_queue ids;
+	int nids = 0;
+
+	STAILQ_INIT(&ids);
+
+	datalen = imsg->hdr.len - IMSG_HEADER_SIZE;
+	if (datalen != sizeof(ireq))
+		return got_error(GOT_ERR_PRIVSEP_LEN);
+	memcpy(&ireq, imsg->data, sizeof(ireq));
+	memcpy(id.sha1, ireq.id, SHA1_DIGEST_LENGTH);
+
+	err = queue_commit_id(&ids, &id, ireq.color);
+	if (err)
+		return err;
+	nids = 1;
+
+	err = paint_commits(&ids, &nids, keep, drop, skip,
+	    pack, packidx, ibuf, objcache);
+	if (err)
+		goto done;
+
+	err = got_privsep_send_painted_commits(ibuf, &ids, &nids, 0, 1);
+	if (err)
+		goto done;
+
+	err = got_privsep_send_painting_commits_done(ibuf);
+done:
+	got_object_id_queue_free(&ids);
+	return err;
+}
+
+static const struct got_error *
 receive_pack(struct got_pack **packp, struct imsgbuf *ibuf)
 {
 	const struct got_error *err = NULL;
@@ -1625,6 +1895,7 @@ main(int argc, char *argv[])
 	struct got_pack *pack = NULL;
 	struct got_object_cache objcache;
 	FILE *basefile = NULL, *accumfile = NULL, *delta_outfile = NULL;
+	struct got_object_idset *keep = NULL, *drop = NULL, *skip = NULL;
 
 	//static int attached;
 	//while (!attached) sleep(1);
@@ -1754,6 +2025,21 @@ main(int argc, char *argv[])
 			err = enumeration_request(&imsg, &ibuf, pack,
 			    packidx, &objcache);
 			break;
+		case GOT_IMSG_COMMIT_PAINTING_INIT:
+			commit_painting_free(&keep, &drop, &skip);
+			err = commit_painting_init(&ibuf, &keep, &drop, &skip);
+			break;
+		case GOT_IMSG_COMMIT_PAINTING_REQUEST:
+			if (keep == NULL || drop == NULL || skip == NULL) {
+				err = got_error(GOT_ERR_PRIVSEP_MSG);
+				break;
+			}
+			err = commit_painting_request(&imsg, &ibuf, pack,
+			    packidx, &objcache, keep, drop, skip);
+			break;
+		case GOT_IMSG_COMMIT_PAINTING_DONE:
+			commit_painting_free(&keep, &drop, &skip);
+			break;
 		default:
 			err = got_error(GOT_ERR_PRIVSEP_MSG);
 			break;
@@ -1766,6 +2052,7 @@ main(int argc, char *argv[])
 			break;
 	}
 
+	commit_painting_free(&keep, &drop, &skip);
 	if (packidx)
 		got_packidx_close(packidx);
 	if (pack)