On Mon, Aug 04, 2025 at 05:30:38PM +0200, Stefan Sperling wrote:
> Pass an exact copy of queued IDs to got-read-pack during commit coloring.
> 
> This ensures that commit painting inside got-read-pack begins with an
> exact copy of the object ID list state which the main process has.
> 

The previous diff was incomplete. Here is a new diff which fixes more
bugs and seems to work in all corner cases I can think of and test.

Log messages from the 'paint3' branch which I have temporarily sent to
the main repo for easier coordination with Omar:

-----------------------------------------------
 add functions which transport object ID queues across the imsg layer
 
-----------------------------------------------
 pass an exact copy of queued IDs to got-read-pack during commit coloring
 
-----------------------------------------------
 sort commits not processed by got-read-pack properly
 
-----------------------------------------------
 hack for got_privsep_recv_painted_commits() to sort queue by color
 
-----------------------------------------------
 improve selection of pack files for pinning in the open pack file cache
 
 If two given pack files contain the same amount of requested commits,
 prefer the pack file which contains the larger amount of total objects
 to increase our chances of full history traversal.
 
 Also, require the first element of the list of requested commits to be
 present in the pack file since the caller will very likely try to process
 this commit immediately when we return.
 
 This fixes cases where offloading of commit coloring to got-read-pack was
 ineffective, causing us to take the slow path instead.
 
-----------------------------------------------
 do not let got-read-pack paint parent commits which are not in its pack file
 
 If any parent commit of the current commit is missing, stop iterating
 and return control to the main process. Fixes a case where offloading
 to got-read-pack resulted in an effectively endless loop.
 

Combined diff below.

ok?


M  lib/got_lib_privsep.h                  |   27+   0-
M  lib/pack_create.c                      |   27+  10-
M  lib/pack_create_privsep.c              |    6+  45-
M  lib/privsep.c                          |  128+   1-
M  libexec/got-read-pack/got-read-pack.c  |   21+  34-

5 files changed, 209 insertions(+), 90 deletions(-)

commit - d2e93380ff05d256e957190a35d23bf0ce63c31a
commit + c5dfdea5d3d15ba10bb5358e6bd4c2d252a62650
blob - a539f5cf968d5bec802bad6082fe43acfc4dc609
blob + bee307699142e88ce12f0d346090e26d9b6238d3
--- lib/got_lib_privsep.h
+++ lib/got_lib_privsep.h
@@ -205,6 +205,10 @@ enum got_imsg_type {
 	GOT_IMSG_OBJ_ID_LIST,
 	GOT_IMSG_OBJ_ID_LIST_DONE,
 
+	/* Transfer a queue of object IDs. */
+	GOT_IMSG_OBJ_ID_QUEUE,
+	GOT_IMSG_OBJ_ID_QUEUE_DONE,
+
 	/* Messages related to patch files. */
 	GOT_IMSG_PATCH_FILE,
 	GOT_IMSG_PATCH_HUNK,
@@ -573,6 +577,24 @@ struct got_imsg_object_idlist {
 	sizeof(struct got_imsg_object_idlist)) / sizeof(struct got_object_id))
 };
 
+/*
+ * Structure for GOT_IMSG_OBJ_ID_QUEUE data.
+ * Multiple such messages may be sent back-to-back, where each message
+ * contains a chunk of IDs. The entire list must be terminated with a
+ * GOT_IMSG_OBJ_ID_QUEUE_DONE message.
+ */
+struct got_imsg_object_id_queue {
+	size_t nids;
+
+	/*
+	 * Followed by nids * struct got_object_qid.
+	 */
+
+#define GOT_IMSG_OBJ_ID_QUEUE_MAX_NIDS \
+	((MAX_IMSGSIZE - IMSG_HEADER_SIZE - \
+	sizeof(struct got_imsg_object_id_queue)) / sizeof(struct got_object_qid))
+};
+
 /* Structure for GOT_IMSG_COMMIT_TRAVERSAL_REQUEST  */
 struct got_imsg_commit_traversal_request {
 	struct got_imsg_packed_object iobj;
@@ -818,6 +840,11 @@ const struct got_error *got_privsep_send_object_idlist
 const struct got_error *got_privsep_recv_object_idlist(int *,
     struct got_object_id **, size_t *, struct imsgbuf *);
 
+const struct got_error *got_privsep_send_object_id_queue(struct imsgbuf *ibuf,
+    struct got_object_id_queue *, size_t);
+const struct got_error *got_privsep_recv_object_id_queue(int *,
+    struct got_object_id_queue *, size_t *, struct imsgbuf *);
+
 const struct got_error *got_privsep_send_delta_reuse_req(struct imsgbuf *);
 const struct got_error *got_privsep_send_reused_deltas(struct imsgbuf *,
     struct got_imsg_reused_delta *, size_t);
blob - 4b84755e2c4557df4a09e1117470fc18cf23bcd9
blob + b0aa5bc15b2f5adb37972b7c68f53df5bbe8485d
--- lib/pack_create.c
+++ lib/pack_create.c
@@ -1143,8 +1143,8 @@ got_pack_find_pack_for_commit_painting(struct got_pack
 	*best_packidx = NULL;
 
 	/*
-	 * Find the largest pack which contains at least some of the
-	 * commits we are interested in.
+	 * Find the largest pack which contains the commit at the head
+	 * of the queue and some other commits we are interested in.
 	 */
 	RB_FOREACH(pe, got_pathlist_head, &repo->packidx_paths) {
 		const char *path_packidx = pe->path;
@@ -1157,15 +1157,24 @@ got_pack_find_pack_for_commit_painting(struct got_pack
 			break;
 
 		nobj = be32toh(packidx->hdr.fanout_table[0xff]);
-		if (nobj <= nobj_max)
+		if (nobj < nobj_max)
 			continue;
 
-		STAILQ_FOREACH(qid, ids, entry) {
+		qid = STAILQ_FIRST(ids);
+		idx = got_packidx_get_object_idx(packidx, &qid->id);
+		if (idx == -1)
+			continue;
+		ncommits++;
+
+		qid = STAILQ_NEXT(qid, entry);
+		while (qid) {
 			idx = got_packidx_get_object_idx(packidx, &qid->id);
 			if (idx != -1)
 				ncommits++;
+			qid = STAILQ_NEXT(qid, entry);
 		}
-		if (ncommits > ncommits_max) {
+
+		if (ncommits >= ncommits_max) {
 			best_packidx_path = path_packidx;
 			nobj_max = nobj;
 			ncommits_max = ncommits;
@@ -1280,9 +1289,12 @@ find_pack_for_enumeration(struct got_packidx **best_pa
 
 	*best_packidx = NULL;
 
+	if (nids == 0)
+		return NULL;
+
 	/*
-	 * Find the largest pack which contains at least some of the
-	 * commits and tags we are interested in.
+	 * Find the largest pack which contains the commit at the head
+	 * of the queue and some other commits we are interested in.
 	 */
 	RB_FOREACH(pe, got_pathlist_head, &repo->packidx_paths) {
 		const char *path_packidx = pe->path;
@@ -1294,15 +1306,20 @@ find_pack_for_enumeration(struct got_packidx **best_pa
 			break;
 
 		nobj = be32toh(packidx->hdr.fanout_table[0xff]);
-		if (nobj <= nobj_max)
+		if (nobj < nobj_max)
 			continue;
 
-		for (i = 0; i < nids; i++) {
+		idx = got_packidx_get_object_idx(packidx, ids[0]);
+		if (idx == -1)
+			continue;
+		ncommits++;
+
+		for (i = 1; i < nids; i++) {
 			idx = got_packidx_get_object_idx(packidx, ids[i]);
 			if (idx != -1)
 				ncommits++;
 		}
-		if (ncommits > ncommits_max) {
+		if (ncommits >= ncommits_max) {
 			best_packidx_path = path_packidx;
 			nobj_max = nobj;
 			ncommits_max = ncommits;
blob - 2a41e8fd7c124e45e9207604dc32308d4979cd05
blob + 9afa74d1d08cfdfe6e45e1bd1911a37c1585184b
--- lib/pack_create_privsep.c
+++ lib/pack_create_privsep.c
@@ -96,38 +96,6 @@ send_idset(struct imsgbuf *ibuf, struct got_object_ids
 }
 
 static const struct got_error *
-send_filtered_id_queue(struct imsgbuf *ibuf, struct got_object_id_queue *ids,
-    uintptr_t color)
-{
-	const struct got_error *err = NULL;
-	struct got_object_qid *qid;
-	struct got_object_id *filtered_ids[GOT_IMSG_OBJ_ID_LIST_MAX_NIDS];
-	int nids = 0;
-
-	STAILQ_FOREACH(qid, ids, entry) {
-		if (color != (intptr_t)qid->data)
-			continue;
-
-		filtered_ids[nids++] = &qid->id;
-		if (nids >= GOT_IMSG_OBJ_ID_LIST_MAX_NIDS) {
-			err = got_privsep_send_object_idlist(ibuf,
-			    filtered_ids, nids);
-			if (err)
-				return err;
-			nids = 0;
-		}
-	}
-
-	if (nids > 0) {
-		err = got_privsep_send_object_idlist(ibuf, filtered_ids, 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)
 {
@@ -326,21 +294,11 @@ paint_packed_commits(struct got_object_qid **qid0,
 	if (err)
 		return err;
 
-	err = send_filtered_id_queue(pack->privsep_child->ibuf, ids,
-	    COLOR_KEEP);
+	err = got_privsep_send_object_id_queue(pack->privsep_child->ibuf,
+	    ids, *nqueued);
 	if (err)
 		return err;
 
-	err = send_filtered_id_queue(pack->privsep_child->ibuf, ids,
-	    COLOR_DROP);
-	if (err)
-		return err;
-
-	err = send_filtered_id_queue(pack->privsep_child->ibuf, ids,
-	    COLOR_SKIP);
-	if (err)
-		return err;
-
 	arg.ncolored = ncolored;
 	arg.nqueued = nqueued;
 	arg.nskip = nskip;
@@ -384,7 +342,10 @@ paint_packed_commits(struct got_object_qid **qid0,
 		qid = STAILQ_FIRST(&next_ids);
 		STAILQ_REMOVE_HEAD(&next_ids, entry);
 		got_pack_paint_commit(qid, color);
-		STAILQ_INSERT_TAIL(ids, qid, entry);
+		if (color == COLOR_KEEP)
+			STAILQ_INSERT_TAIL(ids, qid, entry);
+		else
+			STAILQ_INSERT_HEAD(ids, qid, entry);
 		(*nqueued)++;
 		if (color == COLOR_SKIP)
 			(*nskip)++;
blob - 460ebb155dc401a8750ca217414e546ddad73c5a
blob + e580803b5171ab0806bd69d4818151fa6fdd24af
--- lib/privsep.c
+++ lib/privsep.c
@@ -3271,7 +3271,131 @@ got_privsep_recv_object_idlist(int *done, struct got_o
 	return err;
 }
 
+static const struct got_error *
+send_qidlist(struct imsgbuf *ibuf, struct got_object_qid **qids, size_t nids)
+{
+	const struct got_error *err = NULL;
+	struct got_imsg_object_id_queue idqueue;
+	struct ibuf *wbuf;
+	size_t i;
+
+	memset(&idqueue, 0, sizeof(idqueue));
+
+	if (nids > GOT_IMSG_OBJ_ID_QUEUE_MAX_NIDS)
+		return got_error(GOT_ERR_NO_SPACE);
+
+	wbuf = imsg_create(ibuf, GOT_IMSG_OBJ_ID_QUEUE, 0, 0,
+	    sizeof(idqueue) + nids * sizeof(struct got_object_qid));
+	if (wbuf == NULL) {
+		err = got_error_from_errno("imsg_create OBJ_ID_QUEUE");
+		return err;
+	}
+
+	idqueue.nids = nids;
+	if (imsg_add(wbuf, &idqueue, sizeof(idqueue)) == -1)
+		return got_error_from_errno("imsg_add OBJ_ID_QUEUE");
+
+	for (i = 0; i < nids; i++) {
+		struct got_object_qid *qid = qids[i];
+		if (imsg_add(wbuf, qid, sizeof(*qid)) == -1)
+			return got_error_from_errno("imsg_add OBJ_ID_LIST");
+	}
+
+	imsg_close(ibuf, wbuf);
+
+	return flush_imsg(ibuf);
+}
+
 const struct got_error *
+got_privsep_send_object_id_queue(struct imsgbuf *ibuf,
+    struct got_object_id_queue *ids, size_t nids)
+{
+	const struct got_error *err = NULL;
+	struct got_object_qid *qid, *qidlist[GOT_IMSG_OBJ_ID_QUEUE_MAX_NIDS];
+	int i, queued = 0;
+
+	qid = STAILQ_FIRST(ids);
+	for (i = 0; qid && i < nids; i++) {
+		qidlist[i % nitems(qidlist)] = qid;
+		queued++;
+		if (queued >= nitems(qidlist)) {
+			err = send_qidlist(ibuf, qidlist, queued);
+			if (err)
+				return err;
+			queued = 0;
+		}
+		qid = STAILQ_NEXT(qid, entry);
+	}
+
+	if (queued > 0) {
+		err = send_qidlist(ibuf, qidlist, queued);
+		if (err)
+			return err;
+	}
+
+	if (imsg_compose(ibuf, GOT_IMSG_OBJ_ID_QUEUE_DONE, 0, 0, -1, NULL, 0)
+	    == -1)
+		return got_error_from_errno("imsg_compose OBJ_ID_QUEUE_DONE");
+
+	return flush_imsg(ibuf);
+}
+
+const struct got_error *
+got_privsep_recv_object_id_queue(int *done, struct got_object_id_queue *ids,
+    size_t *nids, struct imsgbuf *ibuf)
+{
+	const struct got_error *err = NULL;
+	struct imsg imsg;
+	struct got_imsg_object_id_queue *qidlist;
+	struct got_object_qid *qid, *iqid;
+	size_t datalen;
+
+	*done = 0;
+	*nids = 0;
+
+	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_OBJ_ID_QUEUE:
+		if (datalen < sizeof(*qidlist)) {
+			err = got_error(GOT_ERR_PRIVSEP_LEN);
+			break;
+		}
+		qidlist = imsg.data;
+		if (qidlist->nids > GOT_IMSG_OBJ_ID_LIST_MAX_NIDS ||
+		    qidlist->nids * sizeof(struct got_object_qid) !=
+		    datalen - sizeof(*qidlist)) {
+			err = got_error(GOT_ERR_PRIVSEP_LEN);
+			break;
+		}
+		iqid = (struct got_object_qid *)(imsg.data + sizeof(*qidlist));
+		while (*nids < qidlist->nids) {
+			err = got_object_qid_alloc_partial(&qid);
+			if (err)
+				break;
+			memcpy(qid, iqid, sizeof(*qid));
+			STAILQ_INSERT_TAIL(ids, qid, entry);
+			(*nids)++;
+			iqid++;
+		}
+		break;
+	case GOT_IMSG_OBJ_ID_QUEUE_DONE:
+		*done = 1;
+		break;
+	default:
+		err = got_error(GOT_ERR_PRIVSEP_MSG);
+		break;
+	}
+
+	imsg_free(&imsg);
+
+	return err;
+}
+
+const struct got_error *
 got_privsep_send_delta_reuse_req(struct imsgbuf *ibuf)
 {
 	if (imsg_compose(ibuf, GOT_IMSG_DELTA_REUSE_REQUEST, 0, 0, -1, NULL, 0)
@@ -3537,7 +3661,10 @@ got_privsep_recv_painted_commits(struct got_object_id_
 				memcpy(&qid->id, &icommit.id,
 				    sizeof(qid->id));
 				qid->data = (void *)icommit.color;
-				STAILQ_INSERT_TAIL(new_ids, qid, entry);
+				if (icommit.color == 0 /* COLOR_KEEP */)
+					STAILQ_INSERT_TAIL(new_ids, qid, entry);
+				else
+					STAILQ_INSERT_HEAD(new_ids, qid, entry);
 			}
 		}
 
blob - 3e11305bebb5cfea0725ac4325aca4c560b97c10
blob + 21cff52d4c0895389b584790bfbe4f39a23dbf99
--- libexec/got-read-pack/got-read-pack.c
+++ libexec/got-read-pack/got-read-pack.c
@@ -1798,6 +1798,13 @@ paint_commits(struct got_object_id_queue *ids, int *ni
 		parents = got_object_commit_get_parent_ids(commit);
 		if (parents) {
 			struct got_object_qid *pid;
+
+			STAILQ_FOREACH(pid, parents, entry) {
+				if (got_packidx_get_object_idx(packidx,
+				    &pid->id) == -1)
+					goto send;
+			}
+
 			color = (intptr_t)qid->data;
 			STAILQ_FOREACH(pid, parents, entry) {
 				err = queue_commit_id(ids, &pid->id, color);
@@ -1821,7 +1828,7 @@ paint_commits(struct got_object_id_queue *ids, int *ni
 		if (err)
 			goto done;
 	}
-
+send:
 	err = got_privsep_send_painted_commits(ibuf, &painted, &npainted, 1, 1);
 	if (err)
 		goto done;
@@ -1901,9 +1908,8 @@ commit_painting_request(struct imsg *imsg, struct imsg
 	const struct got_error *err = NULL;
 	size_t datalen;
 	struct got_object_id_queue ids;
-	size_t nkeep = 0, ndrop = 0, nskip = 0;
-	int nids = 0;
-	uintptr_t color;
+	size_t nids;
+	int nqueued = 0, done = 0;
 
 	STAILQ_INIT(&ids);
 
@@ -1911,42 +1917,23 @@ commit_painting_request(struct imsg *imsg, struct imsg
 	if (datalen != 0)
 		return got_error(GOT_ERR_PRIVSEP_LEN);
 
-	color = COLOR_KEEP;
-	err = recv_object_id_queue(&nkeep, &ids, (void *)color, NULL, ibuf);
-	if (err)
-		goto done;
-	if (nids + nkeep > INT_MAX) {
-		err = got_error(GOT_ERR_PRIVSEP_LEN);
-		goto done;
+	while (!done) {
+		err = got_privsep_recv_object_id_queue(&done, &ids, &nids, ibuf);
+		if (err)
+			goto done;
+		if (nqueued + nids > INT_MAX) {
+			err = got_error(GOT_ERR_PRIVSEP_LEN);
+			goto done;
+		}
+		nqueued += nids;
 	}
-	nids += nkeep;
 
-	color = COLOR_DROP;
-	err = recv_object_id_queue(&ndrop, &ids, (void *)color, NULL, ibuf);
-	if (err)
-		goto done;
-	if (nids + ndrop > INT_MAX) {
-		err = got_error(GOT_ERR_PRIVSEP_LEN);
-		goto done;
-	}
-	nids += ndrop;
-
-	color = COLOR_SKIP;
-	err = recv_object_id_queue(&nskip, &ids, (void *)color, NULL, ibuf);
-	if (err)
-		goto done;
-	if (nids + nskip > INT_MAX) {
-		err = got_error(GOT_ERR_PRIVSEP_LEN);
-		goto done;
-	}
-	nids += nskip;
-
-	err = paint_commits(&ids, &nids, keep, drop, skip,
+	err = paint_commits(&ids, &nqueued, keep, drop, skip,
 	    pack, packidx, ibuf, objcache);
 	if (err)
 		goto done;
 
-	err = got_privsep_send_painted_commits(ibuf, &ids, &nids, 0, 1);
+	err = got_privsep_send_painted_commits(ibuf, &ids, &nqueued, 0, 1);
 	if (err)
 		goto done;