1 /*
2  * Copyright (c) 2020 Ori Bernstein
3  * Copyright (c) 2021 Stefan Sperling <stsp@openbsd.org>
4  *
5  * Permission to use, copy, modify, and distribute this software for any
6  * purpose with or without fee is hereby granted, provided that the above
7  * copyright notice and this permission notice appear in all copies.
8  *
9  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
10  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
11  * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
12  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
13  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
14  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
15  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
16  */
17 
18 #include <sys/types.h>
19 #include <sys/uio.h>
20 #include <sys/stat.h>
21 #include <sys/time.h>
22 #include <sys/mman.h>
23 
24 #include <errno.h>
25 #include <stdint.h>
26 #include <stdio.h>
27 #include <stdlib.h>
28 #include <string.h>
29 #include <time.h>
30 #include <unistd.h>
31 #include <limits.h>
32 #include <zlib.h>
33 
34 #if defined(__FreeBSD__)
35 #include <unistd.h>
36 #endif
37 
38 #include "got_error.h"
39 #include "got_cancel.h"
40 #include "got_object.h"
41 #include "got_path.h"
42 #include "got_reference.h"
43 #include "got_repository_admin.h"
44 #include "got_opentemp.h"
45 
46 #include "got_lib_deltify.h"
47 #include "got_lib_delta.h"
48 #include "got_lib_object.h"
49 #include "got_lib_object_idset.h"
50 #include "got_lib_object_cache.h"
51 #include "got_lib_deflate.h"
52 #include "got_lib_pack.h"
53 #include "got_lib_privsep.h"
54 #include "got_lib_repository.h"
55 #include "got_lib_ratelimit.h"
56 #include "got_lib_inflate.h"
57 
58 #ifndef MIN
59 #define	MIN(_a,_b) ((_a) < (_b) ? (_a) : (_b))
60 #endif
61 
62 #ifndef MAX
63 #define	MAX(_a,_b) ((_a) > (_b) ? (_a) : (_b))
64 #endif
65 
66 #ifndef nitems
67 #define nitems(_a)	(sizeof((_a)) / sizeof((_a)[0]))
68 #endif
69 
70 struct got_pack_meta {
71 	struct got_object_id id;
72 	char	*path;
73 	int	obj_type;
74 	off_t	size;
75 	time_t	mtime;
76 
77 	/* The best delta we picked */
78 	struct got_pack_meta *head;
79 	struct got_pack_meta *prev;
80 	unsigned char *delta_buf; /* if encoded in memory (compressed) */
81 	off_t	delta_offset;	/* offset in delta cache file (compressed) */
82 	off_t	delta_len;	/* encoded delta length */
83 	off_t	delta_compressed_len; /* encoded+compressed delta length */
84 	int	nchain;
85 
86 	int	have_reused_delta;
87 	off_t   reused_delta_offset; /* offset of delta in reused pack file */
88 	struct got_object_id *base_obj_id;
89 
90 	/* Only used for delta window */
91 	struct got_delta_table *dtab;
92 
93 	/* Only used for writing offset deltas */
94 	off_t	off;
95 };
96 
97 struct got_pack_metavec {
98 	struct got_pack_meta **meta;
99 	int nmeta;
100 	int metasz;
101 };
102 
103 static const struct got_error *
104 alloc_meta(struct got_pack_meta **new, struct got_object_id *id,
105     const char *path, int obj_type, time_t mtime)
106 {
107 	const struct got_error *err = NULL;
108 	struct got_pack_meta *m;
109 
110 	*new = NULL;
111 
112 	m = calloc(1, sizeof(*m));
113 	if (m == NULL)
114 		return got_error_from_errno("calloc");
115 
116 	memcpy(&m->id, id, sizeof(m->id));
117 
118 	m->path = strdup(path);
119 	if (m->path == NULL) {
120 		err = got_error_from_errno("strdup");
121 		free(m);
122 		return err;
123 	}
124 
125 	m->obj_type = obj_type;
126 	m->mtime = mtime;
127 	*new = m;
128 	return NULL;
129 }
130 
131 static void
132 clear_meta(struct got_pack_meta *meta)
133 {
134 	if (meta == NULL)
135 		return;
136 	free(meta->path);
137 	meta->path = NULL;
138 	free(meta->delta_buf);
139 	meta->delta_buf = NULL;
140 	free(meta->base_obj_id);
141 	meta->base_obj_id = NULL;
142 }
143 
144 static void
145 free_nmeta(struct got_pack_meta **meta, int nmeta)
146 {
147 	int i;
148 
149 	for (i = 0; i < nmeta; i++)
150 		clear_meta(meta[i]);
151 	free(meta);
152 }
153 
154 static int
155 delta_order_cmp(const void *pa, const void *pb)
156 {
157 	struct got_pack_meta *a, *b;
158 	int cmp;
159 
160 	a = *(struct got_pack_meta **)pa;
161 	b = *(struct got_pack_meta **)pb;
162 
163 	if (a->obj_type != b->obj_type)
164 		return a->obj_type - b->obj_type;
165 	cmp = strcmp(a->path, b->path);
166 	if (cmp != 0)
167 		return cmp;
168 	if (a->mtime < b->mtime)
169 		return -1;
170 	if (a->mtime > b->mtime)
171 		return 1;
172 	return got_object_id_cmp(&a->id, &b->id);
173 }
174 
175 static off_t
176 delta_size(struct got_delta_instruction *deltas, int ndeltas)
177 {
178 	int i;
179 	off_t size = 32;
180 	for (i = 0; i < ndeltas; i++) {
181 		if (deltas[i].copy)
182 			size += GOT_DELTA_SIZE_SHIFT;
183 		else
184 			size += deltas[i].len + 1;
185 	}
186 	return size;
187 }
188 
189 static const struct got_error *
190 append(unsigned char **p, size_t *len, off_t *sz, void *seg, int nseg)
191 {
192 	char *n;
193 
194 	if (*len + nseg >= *sz) {
195 		while (*len + nseg >= *sz)
196 			*sz += *sz / 2;
197 		n = realloc(*p, *sz);
198 		if (n == NULL)
199 			return got_error_from_errno("realloc");
200 		*p = n;
201 	}
202 	memcpy(*p + *len, seg, nseg);
203 	*len += nseg;
204 	return NULL;
205 }
206 
207 static const struct got_error *
208 encode_delta_in_mem(struct got_pack_meta *m, struct got_raw_object *o,
209     struct got_delta_instruction *deltas, int ndeltas,
210     off_t delta_size, off_t base_size)
211 {
212 	const struct got_error *err;
213 	unsigned char buf[16], *bp;
214 	int i, j;
215 	size_t len = 0, compressed_len;
216 	off_t bufsize = delta_size;
217 	off_t n;
218 	struct got_delta_instruction *d;
219 	uint8_t *delta_buf;
220 
221 	delta_buf = malloc(bufsize);
222 	if (delta_buf == NULL)
223 		return got_error_from_errno("malloc");
224 
225 	/* base object size */
226 	buf[0] = base_size & GOT_DELTA_SIZE_VAL_MASK;
227 	n = base_size >> GOT_DELTA_SIZE_SHIFT;
228 	for (i = 1; n > 0; i++) {
229 		buf[i - 1] |= GOT_DELTA_SIZE_MORE;
230 		buf[i] = n & GOT_DELTA_SIZE_VAL_MASK;
231 		n >>= GOT_DELTA_SIZE_SHIFT;
232 	}
233 	err = append(&delta_buf, &len, &bufsize, buf, i);
234 	if (err)
235 		goto done;
236 
237 	/* target object size */
238 	buf[0] = o->size & GOT_DELTA_SIZE_VAL_MASK;
239 	n = o->size >> GOT_DELTA_SIZE_SHIFT;
240 	for (i = 1; n > 0; i++) {
241 		buf[i - 1] |= GOT_DELTA_SIZE_MORE;
242 		buf[i] = n & GOT_DELTA_SIZE_VAL_MASK;
243 		n >>= GOT_DELTA_SIZE_SHIFT;
244 	}
245 	err = append(&delta_buf, &len, &bufsize, buf, i);
246 	if (err)
247 		goto done;
248 
249 	for (j = 0; j < ndeltas; j++) {
250 		d = &deltas[j];
251 		if (d->copy) {
252 			n = d->offset;
253 			bp = &buf[1];
254 			buf[0] = GOT_DELTA_BASE_COPY;
255 			for (i = 0; i < 4; i++) {
256 				/* DELTA_COPY_OFF1 ... DELTA_COPY_OFF4 */
257 				buf[0] |= 1 << i;
258 				*bp++ = n & 0xff;
259 				n >>= 8;
260 				if (n == 0)
261 					break;
262 			}
263 
264 			n = d->len;
265 			if (n != GOT_DELTA_COPY_DEFAULT_LEN) {
266 				/* DELTA_COPY_LEN1 ... DELTA_COPY_LEN3 */
267 				for (i = 0; i < 3 && n > 0; i++) {
268 					buf[0] |= 1 << (i + 4);
269 					*bp++ = n & 0xff;
270 					n >>= 8;
271 				}
272 			}
273 			err = append(&delta_buf, &len, &bufsize,
274 			    buf, bp - buf);
275 			if (err)
276 				goto done;
277 		} else if (o->f == NULL) {
278 			n = 0;
279 			while (n != d->len) {
280 				buf[0] = (d->len - n < 127) ? d->len - n : 127;
281 				err = append(&delta_buf, &len, &bufsize,
282 				    buf, 1);
283 				if (err)
284 					goto done;
285 				err = append(&delta_buf, &len, &bufsize,
286 				    o->data + o->hdrlen + d->offset + n,
287 				    buf[0]);
288 				if (err)
289 					goto done;
290 				n += buf[0];
291 			}
292 		} else {
293 			char content[128];
294 			size_t r;
295 			if (fseeko(o->f, o->hdrlen + d->offset, SEEK_SET) == -1) {
296 				err = got_error_from_errno("fseeko");
297 				goto done;
298 			}
299 			n = 0;
300 			while (n != d->len) {
301 				buf[0] = (d->len - n < 127) ? d->len - n : 127;
302 				err = append(&delta_buf, &len, &bufsize,
303 				    buf, 1);
304 				if (err)
305 					goto done;
306 				r = fread(content, 1, buf[0], o->f);
307 				if (r != buf[0]) {
308 					err = got_ferror(o->f, GOT_ERR_IO);
309 					goto done;
310 				}
311 				err = append(&delta_buf, &len, &bufsize,
312 				    content, buf[0]);
313 				if (err)
314 					goto done;
315 				n += buf[0];
316 			}
317 		}
318 	}
319 
320 	err = got_deflate_to_mem_mmap(&m->delta_buf, &compressed_len,
321 	    NULL, NULL, delta_buf, 0, len);
322 	if (err)
323 		goto done;
324 
325 	m->delta_len = len;
326 	m->delta_compressed_len = compressed_len;
327 done:
328 	free(delta_buf);
329 	return err;
330 }
331 
332 static const struct got_error *
333 encode_delta(struct got_pack_meta *m, struct got_raw_object *o,
334     struct got_delta_instruction *deltas, int ndeltas,
335     off_t base_size, FILE *f)
336 {
337 	const struct got_error *err;
338 	unsigned char buf[16], *bp;
339 	int i, j;
340 	off_t n;
341 	struct got_deflate_buf zb;
342 	struct got_delta_instruction *d;
343 	off_t delta_len = 0, compressed_len = 0;
344 
345 	err = got_deflate_init(&zb, NULL, GOT_DEFLATE_BUFSIZE);
346 	if (err)
347 		return err;
348 
349 	/* base object size */
350 	buf[0] = base_size & GOT_DELTA_SIZE_VAL_MASK;
351 	n = base_size >> GOT_DELTA_SIZE_SHIFT;
352 	for (i = 1; n > 0; i++) {
353 		buf[i - 1] |= GOT_DELTA_SIZE_MORE;
354 		buf[i] = n & GOT_DELTA_SIZE_VAL_MASK;
355 		n >>= GOT_DELTA_SIZE_SHIFT;
356 	}
357 
358 	err = got_deflate_append_to_file_mmap(&zb, &compressed_len,
359 	    buf, 0, i, f, NULL);
360 	if (err)
361 		goto done;
362 	delta_len += i;
363 
364 	/* target object size */
365 	buf[0] = o->size & GOT_DELTA_SIZE_VAL_MASK;
366 	n = o->size >> GOT_DELTA_SIZE_SHIFT;
367 	for (i = 1; n > 0; i++) {
368 		buf[i - 1] |= GOT_DELTA_SIZE_MORE;
369 		buf[i] = n & GOT_DELTA_SIZE_VAL_MASK;
370 		n >>= GOT_DELTA_SIZE_SHIFT;
371 	}
372 
373 	err = got_deflate_append_to_file_mmap(&zb, &compressed_len,
374 	    buf, 0, i, f, NULL);
375 	if (err)
376 		goto done;
377 	delta_len += i;
378 
379 	for (j = 0; j < ndeltas; j++) {
380 		d = &deltas[j];
381 		if (d->copy) {
382 			n = d->offset;
383 			bp = &buf[1];
384 			buf[0] = GOT_DELTA_BASE_COPY;
385 			for (i = 0; i < 4; i++) {
386 				/* DELTA_COPY_OFF1 ... DELTA_COPY_OFF4 */
387 				buf[0] |= 1 << i;
388 				*bp++ = n & 0xff;
389 				n >>= 8;
390 				if (n == 0)
391 					break;
392 			}
393 			n = d->len;
394 			if (n != GOT_DELTA_COPY_DEFAULT_LEN) {
395 				/* DELTA_COPY_LEN1 ... DELTA_COPY_LEN3 */
396 				for (i = 0; i < 3 && n > 0; i++) {
397 					buf[0] |= 1 << (i + 4);
398 					*bp++ = n & 0xff;
399 					n >>= 8;
400 				}
401 			}
402 			err = got_deflate_append_to_file_mmap(&zb,
403 			    &compressed_len, buf, 0, bp - buf, f, NULL);
404 			if (err)
405 				goto done;
406 			delta_len += (bp - buf);
407 		} else if (o->f == NULL) {
408 			n = 0;
409 			while (n != d->len) {
410 				buf[0] = (d->len - n < 127) ? d->len - n : 127;
411 				err = got_deflate_append_to_file_mmap(&zb,
412 				    &compressed_len, buf, 0, 1, f, NULL);
413 				if (err)
414 					goto done;
415 				delta_len++;
416 				err = got_deflate_append_to_file_mmap(&zb,
417 				    &compressed_len,
418 				    o->data + o->hdrlen + d->offset + n, 0,
419 				    buf[0], f, NULL);
420 				if (err)
421 					goto done;
422 				delta_len += buf[0];
423 				n += buf[0];
424 			}
425 		} else {
426 			char content[128];
427 			size_t r;
428 			if (fseeko(o->f, o->hdrlen + d->offset, SEEK_SET) == -1) {
429 				err = got_error_from_errno("fseeko");
430 				goto done;
431 			}
432 			n = 0;
433 			while (n != d->len) {
434 				buf[0] = (d->len - n < 127) ? d->len - n : 127;
435 				err = got_deflate_append_to_file_mmap(&zb,
436 				    &compressed_len, buf, 0, 1, f, NULL);
437 				if (err)
438 					goto done;
439 				delta_len++;
440 				r = fread(content, 1, buf[0], o->f);
441 				if (r != buf[0]) {
442 					err = got_ferror(o->f, GOT_ERR_IO);
443 					goto done;
444 				}
445 				err = got_deflate_append_to_file_mmap(&zb,
446 				    &compressed_len, content, 0, buf[0], f,
447 				    NULL);
448 				if (err)
449 					goto done;
450 				delta_len += buf[0];
451 				n += buf[0];
452 			}
453 		}
454 	}
455 
456 	err = got_deflate_flush(&zb, f, NULL, &compressed_len);
457 	if (err)
458 		goto done;
459 
460 	/* sanity check */
461 	if (compressed_len != ftello(f) - m->delta_offset) {
462 		err = got_error(GOT_ERR_COMPRESSION);
463 		goto done;
464 	}
465 
466 	m->delta_len = delta_len;
467 	m->delta_compressed_len = compressed_len;
468 done:
469 	got_deflate_end(&zb);
470 	return err;
471 }
472 
473 static const struct got_error *
474 report_progress(got_pack_progress_cb progress_cb, void *progress_arg,
475     struct got_ratelimit *rl, int ncolored, int nfound, int ntrees,
476     off_t packfile_size, int ncommits, int nobj_total, int obj_deltify,
477     int nobj_written)
478 {
479 	const struct got_error *err;
480 	int elapsed;
481 
482 	if (progress_cb == NULL)
483 		return NULL;
484 
485 	err = got_ratelimit_check(&elapsed, rl);
486 	if (err || !elapsed)
487 		return err;
488 
489 	return progress_cb(progress_arg, ncolored, nfound, ntrees,
490 	    packfile_size, ncommits, nobj_total, obj_deltify, nobj_written);
491 }
492 
493 static const struct got_error *
494 add_meta(struct got_pack_meta *m, struct got_pack_metavec *v)
495 {
496 	if (v->nmeta == v->metasz){
497 		size_t newsize = 2 * v->metasz;
498 		struct got_pack_meta **new;
499 		new = reallocarray(v->meta, newsize, sizeof(*new));
500 		if (new == NULL)
501 			return got_error_from_errno("reallocarray");
502 		v->meta = new;
503 		v->metasz = newsize; 
504 	}
505 
506 	v->meta[v->nmeta++] = m;
507 	return NULL;
508 }
509 
510 static const struct got_error *
511 find_pack_for_reuse(struct got_packidx **best_packidx,
512     struct got_repository *repo)
513 {
514 	const struct got_error *err = NULL;
515 	struct got_pathlist_entry *pe;
516 	const char *best_packidx_path = NULL;
517 	int nobj_max = 0;
518 
519 	*best_packidx = NULL;
520 
521 	TAILQ_FOREACH(pe, &repo->packidx_paths, entry) {
522 		const char *path_packidx = pe->path;
523 		struct got_packidx *packidx;
524 		int nobj;
525 
526 		err = got_repo_get_packidx(&packidx, path_packidx, repo);
527 		if (err)
528 			break;
529 
530 		nobj = be32toh(packidx->hdr.fanout_table[0xff]);
531 		if (nobj > nobj_max) {
532 			best_packidx_path = path_packidx;
533 			nobj_max = nobj;
534 		}
535 	}
536 
537 	if (best_packidx_path) {
538 		err = got_repo_get_packidx(best_packidx, best_packidx_path,
539 		    repo);
540 	}
541 
542 	return err;
543 }
544 
545 struct send_id_arg {
546 	struct imsgbuf *ibuf;
547 	struct got_object_id *ids[GOT_IMSG_OBJ_ID_LIST_MAX_NIDS];
548 	size_t nids;
549 };
550 
551 static const struct got_error *
552 send_id(struct got_object_id *id, void *data, void *arg)
553 {
554 	const struct got_error *err = NULL;
555 	struct send_id_arg *a = arg;
556 
557 	a->ids[a->nids++] = id;
558 
559 	if (a->nids >= GOT_IMSG_OBJ_ID_LIST_MAX_NIDS) {
560 		err = got_privsep_send_object_idlist(a->ibuf, a->ids, a->nids);
561 		if (err)
562 			return err;
563 		a->nids = 0;
564 	}
565 
566 	return NULL;
567 }
568 
569 static const struct got_error *
570 recv_reused_delta(struct got_imsg_reused_delta *delta,
571     struct got_object_idset *idset, struct got_pack_metavec *v)
572 {
573 	struct got_pack_meta *m, *base;
574 
575 	if (delta->delta_offset + delta->delta_size < delta->delta_offset ||
576 	    delta->delta_offset +
577 	    delta->delta_compressed_size < delta->delta_offset)
578 		return got_error(GOT_ERR_BAD_PACKFILE);
579 
580 	m = got_object_idset_get(idset, &delta->id);
581 	if (m == NULL)
582 		return got_error(GOT_ERR_NO_OBJ);
583 
584 	base = got_object_idset_get(idset, &delta->base_id);
585 	if (base == NULL)
586 		return got_error(GOT_ERR_NO_OBJ);
587 
588 	m->delta_len = delta->delta_size;
589 	m->delta_compressed_len = delta->delta_compressed_size;
590 	m->delta_offset = delta->delta_out_offset;
591 	m->prev = base;
592 	m->size = delta->result_size;
593 	m->have_reused_delta = 1;
594 	m->reused_delta_offset = delta->delta_offset;
595 	m->base_obj_id = got_object_id_dup(&delta->base_id);
596 	if (m->base_obj_id == NULL)
597 		return got_error_from_errno("got_object_id_dup");
598 
599 	return add_meta(m, v);
600 }
601 
602 static const struct got_error *
603 search_deltas(struct got_pack_metavec *v, struct got_object_idset *idset,
604     int delta_cache_fd, int ncolored, int nfound, int ntrees, int ncommits,
605     struct got_repository *repo,
606     got_pack_progress_cb progress_cb, void *progress_arg,
607     struct got_ratelimit *rl, got_cancel_cb cancel_cb, void *cancel_arg)
608 {
609 	const struct got_error *err = NULL;
610 	struct got_packidx *packidx;
611 	struct got_pack *pack;
612 	struct send_id_arg sia;
613 	struct got_imsg_reused_delta deltas[GOT_IMSG_REUSED_DELTAS_MAX_NDELTAS];
614 	size_t ndeltas, i;
615 
616 	err = find_pack_for_reuse(&packidx, repo);
617 	if (err)
618 		return err;
619 
620 	if (packidx == NULL)
621 		return NULL;
622 
623 	err = got_object_prepare_delta_reuse(&pack, packidx,
624 	    delta_cache_fd, repo);
625 	if (err)
626 		return err;
627 
628 	memset(&sia, 0, sizeof(sia));
629 	sia.ibuf = pack->privsep_child->ibuf;
630 	err = got_object_idset_for_each(idset, send_id, &sia);
631 	if (err)
632 		return err;
633 	if (sia.nids > 0) {
634 		err = got_privsep_send_object_idlist(pack->privsep_child->ibuf,
635 		    sia.ids, sia.nids);
636 		if (err)
637 			return err;
638 	}
639 	err = got_privsep_send_object_idlist_done(pack->privsep_child->ibuf);
640 	if (err)
641 		return err;
642 
643 	for (;;) {
644 		int done = 0;
645 
646 		if (cancel_cb) {
647 			err = (*cancel_cb)(cancel_arg);
648 			if (err)
649 				break;
650 		}
651 
652 		err = got_privsep_recv_reused_deltas(&done, deltas, &ndeltas,
653 		    pack->privsep_child->ibuf);
654 		if (err || done)
655 			break;
656 
657 		for (i = 0; i < ndeltas; i++) {
658 			struct got_imsg_reused_delta *delta = &deltas[i];
659 			err = recv_reused_delta(delta, idset, v);
660 			if (err)
661 				goto done;
662 		}
663 
664 		err = report_progress(progress_cb, progress_arg, rl,
665 		    ncolored, nfound, ntrees, 0L, ncommits,
666 		    got_object_idset_num_elements(idset), v->nmeta, 0);
667 		if (err)
668 			break;
669 	}
670 done:
671 	return err;
672 }
673 
674 static const struct got_error *
675 pick_deltas(struct got_pack_meta **meta, int nmeta, int ncolored,
676     int nfound, int ntrees, int ncommits, int nreused, FILE *delta_cache,
677     struct got_repository *repo,
678     got_pack_progress_cb progress_cb, void *progress_arg,
679     struct got_ratelimit *rl, got_cancel_cb cancel_cb, void *cancel_arg)
680 {
681 	const struct got_error *err = NULL;
682 	struct got_pack_meta *m = NULL, *base = NULL;
683 	struct got_raw_object *raw = NULL, *base_raw = NULL;
684 	struct got_delta_instruction *deltas = NULL, *best_deltas = NULL;
685 	int i, j, ndeltas, best_ndeltas;
686 	off_t size, best_size;
687 	const int max_base_candidates = 3;
688 	size_t delta_memsize = 0;
689 	const size_t max_delta_memsize = 25 * GOT_DELTA_RESULT_SIZE_CACHED_MAX;
690 	int outfd = -1;
691 
692 	qsort(meta, nmeta, sizeof(struct got_pack_meta *), delta_order_cmp);
693 	for (i = 0; i < nmeta; i++) {
694 		if (cancel_cb) {
695 			err = (*cancel_cb)(cancel_arg);
696 			if (err)
697 				break;
698 		}
699 		err = report_progress(progress_cb, progress_arg, rl,
700 		    ncolored, nfound, ntrees, 0L, ncommits, nreused + nmeta,
701 		    nreused + i, 0);
702 		if (err)
703 			goto done;
704 		m = meta[i];
705 
706 		if (m->obj_type == GOT_OBJ_TYPE_COMMIT ||
707 		    m->obj_type == GOT_OBJ_TYPE_TAG)
708 			continue;
709 
710 		err = got_object_raw_open(&raw, &outfd, repo, &m->id);
711 		if (err)
712 			goto done;
713 		m->size = raw->size;
714 
715 		if (raw->f == NULL) {
716 			err = got_deltify_init_mem(&m->dtab, raw->data,
717 			    raw->hdrlen, raw->size + raw->hdrlen);
718 		} else {
719 			err = got_deltify_init(&m->dtab, raw->f, raw->hdrlen,
720 			    raw->size + raw->hdrlen);
721 		}
722 		if (err)
723 			goto done;
724 
725 		if (i > max_base_candidates) {
726 			struct got_pack_meta *n = NULL;
727 			n = meta[i - (max_base_candidates + 1)];
728 			got_deltify_free(n->dtab);
729 			n->dtab = NULL;
730 		}
731 
732 		best_size = raw->size;
733 		best_ndeltas = 0;
734 		for (j = MAX(0, i - max_base_candidates); j < i; j++) {
735 			if (cancel_cb) {
736 				err = (*cancel_cb)(cancel_arg);
737 				if (err)
738 					goto done;
739 			}
740 			base = meta[j];
741 			/* long chains make unpacking slow, avoid such bases */
742 			if (base->nchain >= 128 ||
743 			    base->obj_type != m->obj_type)
744 				continue;
745 
746 			err = got_object_raw_open(&base_raw, &outfd, repo,
747 			    &base->id);
748 			if (err)
749 				goto done;
750 
751 			if (raw->f == NULL && base_raw->f == NULL) {
752 				err = got_deltify_mem_mem(&deltas, &ndeltas,
753 				    raw->data, raw->hdrlen,
754 				    raw->size + raw->hdrlen,
755 				    base->dtab, base_raw->data,
756 				    base_raw->hdrlen,
757 				    base_raw->size + base_raw->hdrlen);
758 			} else if (raw->f == NULL) {
759 				err = got_deltify_mem_file(&deltas, &ndeltas,
760 				    raw->data, raw->hdrlen,
761 				    raw->size + raw->hdrlen,
762 				    base->dtab, base_raw->f,
763 				    base_raw->hdrlen,
764 				    base_raw->size + base_raw->hdrlen);
765 			} else if (base_raw->f == NULL) {
766 				err = got_deltify_file_mem(&deltas, &ndeltas,
767 				    raw->f, raw->hdrlen,
768 				    raw->size + raw->hdrlen,
769 				    base->dtab, base_raw->data,
770 				    base_raw->hdrlen,
771 				    base_raw->size + base_raw->hdrlen);
772 			} else {
773 				err = got_deltify(&deltas, &ndeltas,
774 				    raw->f, raw->hdrlen,
775 				    raw->size + raw->hdrlen,
776 				    base->dtab, base_raw->f, base_raw->hdrlen,
777 				    base_raw->size + base_raw->hdrlen);
778 			}
779 			got_object_raw_close(base_raw);
780 			base_raw = NULL;
781 			if (err)
782 				goto done;
783 
784 			size = delta_size(deltas, ndeltas);
785 			if (size + 32 < best_size){
786 				/*
787 				 * if we already picked a best delta,
788 				 * replace it.
789 				 */
790 				best_size = size;
791 				free(best_deltas);
792 				best_deltas = deltas;
793 				best_ndeltas = ndeltas;
794 				deltas = NULL;
795 				m->nchain = base->nchain + 1;
796 				m->prev = base;
797 				m->head = base->head;
798 				if (m->head == NULL)
799 					m->head = base;
800 			} else {
801 				free(deltas);
802 				deltas = NULL;
803 				ndeltas = 0;
804 			}
805 		}
806 
807 		if (best_ndeltas > 0) {
808 			if (best_size <= GOT_DELTA_RESULT_SIZE_CACHED_MAX &&
809 			    delta_memsize + best_size <= max_delta_memsize) {
810 				delta_memsize += best_size;
811 				err = encode_delta_in_mem(m, raw, best_deltas,
812 				    best_ndeltas, best_size, m->prev->size);
813 			} else {
814 				m->delta_offset = ftello(delta_cache);
815 				err = encode_delta(m, raw, best_deltas,
816 				    best_ndeltas, m->prev->size, delta_cache);
817 			}
818 			free(best_deltas);
819 			best_deltas = NULL;
820 			best_ndeltas = 0;
821 			if (err)
822 				goto done;
823 		}
824 
825 		got_object_raw_close(raw);
826 		raw = NULL;
827 	}
828 done:
829 	for (i = MAX(0, nmeta - max_base_candidates); i < nmeta; i++) {
830 		got_deltify_free(meta[i]->dtab);
831 		meta[i]->dtab = NULL;
832 	}
833 	if (raw)
834 		got_object_raw_close(raw);
835 	if (base_raw)
836 		got_object_raw_close(base_raw);
837 	if (outfd != -1 && close(outfd) == -1 && err == NULL)
838 		err = got_error_from_errno("close");
839 	free(deltas);
840 	free(best_deltas);
841 	return err;
842 }
843 
844 static const struct got_error *
845 search_packidx(int *found, struct got_object_id *id,
846     struct got_repository *repo)
847 {
848 	const struct got_error *err = NULL;
849 	struct got_packidx *packidx = NULL;
850 	int idx;
851 
852 	*found = 0;
853 
854 	err = got_repo_search_packidx(&packidx, &idx, repo, id);
855 	if (err == NULL)
856 		*found = 1; /* object is already packed */
857 	else if (err->code == GOT_ERR_NO_OBJ)
858 		err = NULL;
859 	return err;
860 }
861 
862 static const struct got_error *
863 add_object(int want_meta, struct got_object_idset *idset,
864     struct got_object_id *id, const char *path, int obj_type,
865     time_t mtime, int loose_obj_only, struct got_repository *repo,
866     int *ncolored, int *nfound, int *ntrees,
867     got_pack_progress_cb progress_cb, void *progress_arg,
868     struct got_ratelimit *rl)
869 {
870 	const struct got_error *err;
871 	struct got_pack_meta *m = NULL;
872 
873 	if (loose_obj_only) {
874 		int is_packed;
875 		err = search_packidx(&is_packed, id, repo);
876 		if (err)
877 			return err;
878 		if (is_packed && want_meta)
879 			return NULL;
880 	}
881 
882 	if (want_meta) {
883 		err = alloc_meta(&m, id, path, obj_type, mtime);
884 		if (err)
885 			return err;
886 
887 		(*nfound)++;
888 		err = report_progress(progress_cb, progress_arg, rl,
889 		    *ncolored, *nfound, *ntrees, 0L, 0, 0, 0, 0);
890 		if (err) {
891 			clear_meta(m);
892 			free(m);
893 			return err;
894 		}
895 	}
896 
897 	err = got_object_idset_add(idset, id, m);
898 	if (err) {
899 		clear_meta(m);
900 		free(m);
901 	}
902 	return err;
903 }
904 
905 static const struct got_error *
906 load_tree_entries(struct got_object_id_queue *ids, int want_meta,
907     struct got_object_idset *idset, struct got_object_idset *idset_exclude,
908     struct got_object_id *tree_id,
909     const char *dpath, time_t mtime, struct got_repository *repo,
910     int loose_obj_only, int *ncolored, int *nfound, int *ntrees,
911     got_pack_progress_cb progress_cb, void *progress_arg,
912     struct got_ratelimit *rl, got_cancel_cb cancel_cb, void *cancel_arg)
913 {
914 	const struct got_error *err;
915 	struct got_tree_object *tree;
916 	char *p = NULL;
917 	int i;
918 
919 	err = got_object_open_as_tree(&tree, repo, tree_id);
920 	if (err)
921 		return err;
922 
923 	(*ntrees)++;
924 	err = report_progress(progress_cb, progress_arg, rl,
925 	    *ncolored, *nfound, *ntrees, 0L, 0, 0, 0, 0);
926 	if (err)
927 		return err;
928 
929 	for (i = 0; i < got_object_tree_get_nentries(tree); i++) {
930 		struct got_tree_entry *e = got_object_tree_get_entry(tree, i);
931 		struct got_object_id *id = got_tree_entry_get_id(e);
932 		mode_t mode = got_tree_entry_get_mode(e);
933 
934 		if (cancel_cb) {
935 			err = (*cancel_cb)(cancel_arg);
936 			if (err)
937 				break;
938 		}
939 
940 		if (got_object_tree_entry_is_submodule(e) ||
941 		    got_object_idset_contains(idset, id) ||
942 		    got_object_idset_contains(idset_exclude, id))
943 			continue;
944 		
945 		if (asprintf(&p, "%s%s%s", dpath, dpath[0] != '\0' ? "/" : "",
946 		    got_tree_entry_get_name(e)) == -1) {
947 			err = got_error_from_errno("asprintf");
948 			break;
949 		}
950 
951 		if (S_ISDIR(mode)) {
952 			struct got_object_qid *qid;
953 			err = got_object_qid_alloc(&qid, id);
954 			if (err)
955 				break;
956 			STAILQ_INSERT_TAIL(ids, qid, entry);
957 		} else if (S_ISREG(mode) || S_ISLNK(mode)) {
958 			err = add_object(want_meta,
959 			    want_meta ? idset : idset_exclude, id, p,
960 			    GOT_OBJ_TYPE_BLOB, mtime, loose_obj_only, repo,
961 			    ncolored, nfound, ntrees,
962 			    progress_cb, progress_arg, rl);
963 			if (err)
964 				break;
965 		}
966 		free(p);
967 		p = NULL;
968 	}
969 
970 	got_object_tree_close(tree);
971 	free(p);
972 	return err;
973 }
974 
975 static const struct got_error *
976 load_tree(int want_meta, struct got_object_idset *idset,
977     struct got_object_idset *idset_exclude,
978     struct got_object_id *tree_id, const char *dpath, time_t mtime,
979     struct got_repository *repo, int loose_obj_only,
980     int *ncolored, int *nfound, int *ntrees,
981     got_pack_progress_cb progress_cb, void *progress_arg,
982     struct got_ratelimit *rl, got_cancel_cb cancel_cb, void *cancel_arg)
983 {
984 	const struct got_error *err = NULL;
985 	struct got_object_id_queue tree_ids;
986 	struct got_object_qid *qid;
987 
988 	if (got_object_idset_contains(idset, tree_id) ||
989 	    got_object_idset_contains(idset_exclude, tree_id))
990 		return NULL;
991 
992 	err = got_object_qid_alloc(&qid, tree_id);
993 	if (err)
994 		return err;
995 
996 	STAILQ_INIT(&tree_ids);
997 	STAILQ_INSERT_TAIL(&tree_ids, qid, entry);
998 
999 	while (!STAILQ_EMPTY(&tree_ids)) {
1000 		if (cancel_cb) {
1001 			err = (*cancel_cb)(cancel_arg);
1002 			if (err)
1003 				break;
1004 		}
1005 
1006 		qid = STAILQ_FIRST(&tree_ids);
1007 		STAILQ_REMOVE_HEAD(&tree_ids, entry);
1008 
1009 		if (got_object_idset_contains(idset, &qid->id) ||
1010 		    got_object_idset_contains(idset_exclude, &qid->id)) {
1011 			got_object_qid_free(qid);
1012 			continue;
1013 		}
1014 
1015 		err = add_object(want_meta, want_meta ? idset : idset_exclude,
1016 		    &qid->id, dpath, GOT_OBJ_TYPE_TREE,
1017 		    mtime, loose_obj_only, repo,
1018 		    ncolored, nfound, ntrees, progress_cb, progress_arg, rl);
1019 		if (err) {
1020 			got_object_qid_free(qid);
1021 			break;
1022 		}
1023 
1024 		err = load_tree_entries(&tree_ids, want_meta, idset,
1025 		    idset_exclude, &qid->id,
1026 		    dpath, mtime, repo, loose_obj_only, ncolored, nfound,
1027 		    ntrees, progress_cb, progress_arg, rl,
1028 		    cancel_cb, cancel_arg);
1029 		got_object_qid_free(qid);
1030 		if (err)
1031 			break;
1032 	}
1033 
1034 	got_object_id_queue_free(&tree_ids);
1035 	return err;
1036 }
1037 
1038 static const struct got_error *
1039 load_commit(int want_meta, struct got_object_idset *idset,
1040     struct got_object_idset *idset_exclude,
1041     struct got_object_id *id, struct got_repository *repo, int loose_obj_only,
1042     int *ncolored, int *nfound, int *ntrees,
1043     got_pack_progress_cb progress_cb, void *progress_arg,
1044     struct got_ratelimit *rl, got_cancel_cb cancel_cb, void *cancel_arg)
1045 {
1046 	const struct got_error *err;
1047 	struct got_commit_object *commit;
1048 
1049 	if (got_object_idset_contains(idset, id) ||
1050 	    got_object_idset_contains(idset_exclude, id))
1051 		return NULL;
1052 
1053 	if (loose_obj_only) {
1054 		int is_packed;
1055 		err = search_packidx(&is_packed, id, repo);
1056 		if (err)
1057 			return err;
1058 		if (is_packed && want_meta)
1059 			return NULL;
1060 	}
1061 
1062 	err = got_object_open_as_commit(&commit, repo, id);
1063 	if (err)
1064 		return err;
1065 
1066 	err = add_object(want_meta, want_meta ? idset : idset_exclude,
1067 	    id, "", GOT_OBJ_TYPE_COMMIT,
1068 	    got_object_commit_get_committer_time(commit),
1069 	    loose_obj_only, repo,
1070 	    ncolored, nfound, ntrees, progress_cb, progress_arg, rl);
1071 	if (err)
1072 		goto done;
1073 
1074 	err = load_tree(want_meta, idset, idset_exclude,
1075 	    got_object_commit_get_tree_id(commit),
1076 	    "", got_object_commit_get_committer_time(commit),
1077 	    repo, loose_obj_only, ncolored, nfound, ntrees,
1078 	    progress_cb, progress_arg, rl, cancel_cb, cancel_arg);
1079 done:
1080 	got_object_commit_close(commit);
1081 	return err;
1082 }
1083 
1084 static const struct got_error *
1085 load_tag(int want_meta, struct got_object_idset *idset,
1086     struct got_object_idset *idset_exclude,
1087     struct got_object_id *id, struct got_repository *repo, int loose_obj_only,
1088     int *ncolored, int *nfound, int *ntrees,
1089     got_pack_progress_cb progress_cb, void *progress_arg,
1090     struct got_ratelimit *rl, got_cancel_cb cancel_cb, void *cancel_arg)
1091 {
1092 	const struct got_error *err;
1093 	struct got_tag_object *tag = NULL;
1094 
1095 	if (got_object_idset_contains(idset, id) ||
1096 	    got_object_idset_contains(idset_exclude, id))
1097 		return NULL;
1098 
1099 	if (loose_obj_only) {
1100 		int is_packed;
1101 		err = search_packidx(&is_packed, id, repo);
1102 		if (err)
1103 			return err;
1104 		if (is_packed && want_meta)
1105 			return NULL;
1106 	}
1107 
1108 	err = got_object_open_as_tag(&tag, repo, id);
1109 	if (err)
1110 		return err;
1111 
1112 	err = add_object(want_meta, want_meta ? idset : idset_exclude,
1113 	    id, "", GOT_OBJ_TYPE_TAG,
1114 	    got_object_tag_get_tagger_time(tag), loose_obj_only, repo,
1115 	    ncolored, nfound, ntrees, progress_cb, progress_arg, rl);
1116 	if (err)
1117 		goto done;
1118 
1119 	switch (got_object_tag_get_object_type(tag)) {
1120 	case GOT_OBJ_TYPE_COMMIT:
1121 		err = load_commit(want_meta, idset, idset_exclude,
1122 		    got_object_tag_get_object_id(tag), repo, loose_obj_only,
1123 		    ncolored, nfound, ntrees, progress_cb, progress_arg, rl,
1124 		    cancel_cb, cancel_arg);
1125 		break;
1126 	case GOT_OBJ_TYPE_TREE:
1127 		err = load_tree(want_meta, idset, idset_exclude,
1128 		    got_object_tag_get_object_id(tag), "",
1129 		    got_object_tag_get_tagger_time(tag), repo, loose_obj_only,
1130 		    ncolored, nfound, ntrees, progress_cb, progress_arg, rl,
1131 		    cancel_cb, cancel_arg);
1132 		break;
1133 	default:
1134 		break;
1135 	}
1136 
1137 done:
1138 	got_object_tag_close(tag);
1139 	return err;
1140 }
1141 
1142 enum findtwixt_color {
1143 	COLOR_KEEP = 0,
1144 	COLOR_DROP,
1145 	COLOR_BLANK,
1146 	COLOR_SKIP,
1147 };
1148 
1149 static const int findtwixt_colors[] = {
1150 	COLOR_KEEP,
1151 	COLOR_DROP,
1152 	COLOR_BLANK,
1153 	COLOR_SKIP,
1154 };
1155 
1156 static const struct got_error *
1157 paint_commit(struct got_object_qid *qid, int color)
1158 {
1159 	if (color < 0 || color >= nitems(findtwixt_colors))
1160 		return got_error(GOT_ERR_RANGE);
1161 
1162 	qid->data = (void *)&findtwixt_colors[color];
1163 	return NULL;
1164 }
1165 
1166 static const struct got_error *
1167 queue_commit_id(struct got_object_id_queue *ids, struct got_object_id *id,
1168     int color, struct got_repository *repo)
1169 {
1170 	const struct got_error *err;
1171 	struct got_object_qid *qid;
1172 
1173 	err = got_object_qid_alloc(&qid, id);
1174 	if (err)
1175 		return err;
1176 
1177 	STAILQ_INSERT_TAIL(ids, qid, entry);
1178 	return paint_commit(qid, color);
1179 }
1180 
1181 struct append_id_arg {
1182 	struct got_object_id **array;
1183 	int idx;
1184 	struct got_object_idset *drop;
1185 	struct got_object_idset *skip;
1186 };
1187 
1188 static const struct got_error *
1189 append_id(struct got_object_id *id, void *data, void *arg)
1190 {
1191 	struct append_id_arg *a = arg;
1192 
1193 	if (got_object_idset_contains(a->skip, id) ||
1194 	    got_object_idset_contains(a->drop, id))
1195 		return NULL;
1196 
1197 	a->array[++a->idx] = got_object_id_dup(id);
1198 	if (a->array[a->idx] == NULL)
1199 		return got_error_from_errno("got_object_id_dup");
1200 
1201 	return NULL;
1202 }
1203 
1204 static const struct got_error *
1205 queue_commit_or_tag_id(struct got_object_id *id, int color,
1206     struct got_object_id_queue *ids, struct got_repository *repo)
1207 {
1208 	const struct got_error *err;
1209 	struct got_tag_object *tag = NULL;
1210 	int obj_type;
1211 
1212 	err = got_object_get_type(&obj_type, repo, id);
1213 	if (err)
1214 		return err;
1215 
1216 	if (obj_type == GOT_OBJ_TYPE_TAG) {
1217 		err = got_object_open_as_tag(&tag, repo, id);
1218 		if (err)
1219 			return err;
1220 		obj_type = got_object_tag_get_object_type(tag);
1221 		id = got_object_tag_get_object_id(tag);
1222 	}
1223 
1224 	if (obj_type == GOT_OBJ_TYPE_COMMIT) {
1225 		err = queue_commit_id(ids, id, color, repo);
1226 		if (err)
1227 			goto done;
1228 	}
1229 done:
1230 	if (tag)
1231 		got_object_tag_close(tag);
1232 	return err;
1233 }
1234 
1235 static const struct got_error *
1236 paint_commits(int *ncolored, struct got_object_id_queue *ids, int nids,
1237     struct got_object_idset *keep, struct got_object_idset *drop,
1238     struct got_object_idset *skip, struct got_repository *repo,
1239     got_pack_progress_cb progress_cb, void *progress_arg,
1240     struct got_ratelimit *rl, got_cancel_cb cancel_cb, void *cancel_arg)
1241 {
1242 	const struct got_error *err = NULL;
1243 	struct got_commit_object *commit = NULL;
1244 	const struct got_object_id_queue *parents;
1245 	struct got_object_qid *qid;
1246 	int nqueued = nids, nskip = 0;
1247 
1248 	while (!STAILQ_EMPTY(ids) && nskip != nqueued) {
1249 		int color;
1250 
1251 		if (cancel_cb) {
1252 			err = cancel_cb(cancel_arg);
1253 			if (err)
1254 				break;
1255 		}
1256 
1257 		qid = STAILQ_FIRST(ids);
1258 		STAILQ_REMOVE_HEAD(ids, entry);
1259 		nqueued--;
1260 		color = *((int *)qid->data);
1261 		if (color == COLOR_SKIP)
1262 			nskip--;
1263 
1264 		if (got_object_idset_contains(skip, &qid->id)) {
1265 			got_object_qid_free(qid);
1266 			continue;
1267 		}
1268 
1269 		switch (color) {
1270 		case COLOR_KEEP:
1271 			if (got_object_idset_contains(keep, &qid->id)) {
1272 				got_object_qid_free(qid);
1273 				continue;
1274 			}
1275 			if (got_object_idset_contains(drop, &qid->id)) {
1276 				err = paint_commit(qid, COLOR_SKIP);
1277 				if (err)
1278 					goto done;
1279 				nskip++;
1280 			} else
1281 				(*ncolored)++;
1282 			err = got_object_idset_add(keep, &qid->id, NULL);
1283 			if (err)
1284 				goto done;
1285 			break;
1286 		case COLOR_DROP:
1287 			if (got_object_idset_contains(drop, &qid->id)) {
1288 				got_object_qid_free(qid);
1289 				continue;
1290 			}
1291 			if (got_object_idset_contains(keep, &qid->id)) {
1292 				err = paint_commit(qid, COLOR_SKIP);
1293 				if (err)
1294 					goto done;
1295 				nskip++;
1296 			} else
1297 				(*ncolored)++;
1298 			err = got_object_idset_add(drop, &qid->id, NULL);
1299 			if (err)
1300 				goto done;
1301 			break;
1302 		case COLOR_SKIP:
1303 			if (!got_object_idset_contains(skip, &qid->id)) {
1304 				err = got_object_idset_add(skip, &qid->id,
1305 				    NULL);
1306 				if (err)
1307 					goto done;
1308 			}
1309 			break;
1310 		default:
1311 			/* should not happen */
1312 			err = got_error_fmt(GOT_ERR_NOT_IMPL,
1313 			    "%s invalid commit color %d", __func__, color);
1314 			goto done;
1315 		}
1316 
1317 		err = report_progress(progress_cb, progress_arg, rl,
1318 		    *ncolored, 0, 0, 0L, 0, 0, 0, 0);
1319 		if (err)
1320 			break;
1321 
1322 
1323 		err = got_object_open_as_commit(&commit, repo, &qid->id);
1324 		if (err)
1325 			break;
1326 
1327 		parents = got_object_commit_get_parent_ids(commit);
1328 		if (parents) {
1329 			struct got_object_qid *pid;
1330 			color = *((int *)qid->data);
1331 			STAILQ_FOREACH(pid, parents, entry) {
1332 				err = queue_commit_id(ids, &pid->id, color,
1333 				    repo);
1334 				if (err)
1335 					break;
1336 				nqueued++;
1337 				if (color == COLOR_SKIP)
1338 					nskip++;
1339 			}
1340 		}
1341 
1342 		got_object_commit_close(commit);
1343 		commit = NULL;
1344 		got_object_qid_free(qid);
1345 	}
1346 done:
1347 	if (commit)
1348 		got_object_commit_close(commit);
1349 	return err;
1350 }
1351 
1352 static const struct got_error *
1353 findtwixt(struct got_object_id ***res, int *nres, int *ncolored,
1354     struct got_object_id **head, int nhead,
1355     struct got_object_id **tail, int ntail,
1356     struct got_repository *repo,
1357     got_pack_progress_cb progress_cb, void *progress_arg,
1358     struct got_ratelimit *rl, got_cancel_cb cancel_cb, void *cancel_arg)
1359 {
1360 	const struct got_error *err = NULL;
1361 	struct got_object_id_queue ids;
1362 	struct got_object_idset *keep, *drop, *skip = NULL;
1363 	int i, nkeep;
1364 
1365 	STAILQ_INIT(&ids);
1366 	*res = NULL;
1367 	*nres = 0;
1368 	*ncolored = 0;
1369 
1370 	keep = got_object_idset_alloc();
1371 	if (keep == NULL)
1372 		return got_error_from_errno("got_object_idset_alloc");
1373 
1374 	drop = got_object_idset_alloc();
1375 	if (drop == NULL) {
1376 		err = got_error_from_errno("got_object_idset_alloc");
1377 		goto done;
1378 	}
1379 
1380 	skip = got_object_idset_alloc();
1381 	if (skip == NULL) {
1382 		err = got_error_from_errno("got_object_idset_alloc");
1383 		goto done;
1384 	}
1385 
1386 	for (i = 0; i < nhead; i++) {
1387 		struct got_object_id *id = head[i];
1388 		if (id == NULL)
1389 			continue;
1390 		err = queue_commit_or_tag_id(id, COLOR_KEEP, &ids, repo);
1391 		if (err)
1392 			goto done;
1393 	}		
1394 
1395 	for (i = 0; i < ntail; i++) {
1396 		struct got_object_id *id = tail[i];
1397 		if (id == NULL)
1398 			continue;
1399 		err = queue_commit_or_tag_id(id, COLOR_DROP, &ids, repo);
1400 		if (err)
1401 			goto done;
1402 	}
1403 
1404 	err = paint_commits(ncolored, &ids, nhead + ntail,
1405 	    keep, drop, skip, repo, progress_cb, progress_arg, rl,
1406 	    cancel_cb, cancel_arg);
1407 	if (err)
1408 		goto done;
1409 
1410 	nkeep = got_object_idset_num_elements(keep);
1411 	if (nkeep > 0) {
1412 		struct append_id_arg arg;
1413 		arg.array = calloc(nkeep, sizeof(struct got_object_id *));
1414 		if (arg.array == NULL) {
1415 			err = got_error_from_errno("calloc");
1416 			goto done;
1417 		}
1418 		arg.idx = -1;
1419 		arg.skip = skip;
1420 		arg.drop = drop;
1421 		err = got_object_idset_for_each(keep, append_id, &arg);
1422 		if (err) {
1423 			free(arg.array);
1424 			goto done;
1425 		}
1426 		*res = arg.array;
1427 		*nres = arg.idx + 1;
1428 	}
1429 done:
1430 	got_object_idset_free(keep);
1431 	got_object_idset_free(drop);
1432 	if (skip)
1433 		got_object_idset_free(skip);
1434 	got_object_id_queue_free(&ids);
1435 	return err;
1436 }
1437 
1438 static const struct got_error *
1439 load_object_ids(int *ncolored, int *nfound, int *ntrees,
1440     struct got_object_idset *idset, struct got_object_id **theirs, int ntheirs,
1441     struct got_object_id **ours, int nours, struct got_repository *repo,
1442     int loose_obj_only, got_pack_progress_cb progress_cb, void *progress_arg,
1443     struct got_ratelimit *rl, got_cancel_cb cancel_cb, void *cancel_arg)
1444 {
1445 	const struct got_error *err = NULL;
1446 	struct got_object_id **ids = NULL;
1447 	int i, nobj = 0, obj_type;
1448 	struct got_object_idset *idset_exclude;
1449 
1450 	idset_exclude = got_object_idset_alloc();
1451 	if (idset_exclude == NULL)
1452 		return got_error_from_errno("got_object_idset_alloc");
1453 
1454 	*ncolored = 0;
1455 	*nfound = 0;
1456 	*ntrees = 0;
1457 
1458 	err = findtwixt(&ids, &nobj, ncolored, ours, nours, theirs, ntheirs,
1459 	    repo, progress_cb, progress_arg, rl, cancel_cb, cancel_arg);
1460 	if (err)
1461 		goto done;
1462 
1463 	for (i = 0; i < ntheirs; i++) {
1464 		struct got_object_id *id = theirs[i];
1465 		if (id == NULL)
1466 			continue;
1467 		err = got_object_get_type(&obj_type, repo, id);
1468 		if (err)
1469 			return err;
1470 		if (obj_type == GOT_OBJ_TYPE_COMMIT) {
1471 			err = load_commit(0, idset, idset_exclude, id, repo,
1472 			    loose_obj_only, ncolored, nfound, ntrees,
1473 			    progress_cb, progress_arg, rl,
1474 			    cancel_cb, cancel_arg);
1475 			if (err)
1476 				goto done;
1477 		} else if (obj_type == GOT_OBJ_TYPE_TAG) {
1478 			err = load_tag(0, idset, idset_exclude, id, repo,
1479 			    loose_obj_only, ncolored, nfound, ntrees,
1480 			    progress_cb, progress_arg, rl,
1481 			    cancel_cb, cancel_arg);
1482 			if (err)
1483 				goto done;
1484 		}
1485 	}
1486 
1487 	for (i = 0; i < nobj; i++) {
1488 		err = load_commit(1, idset, idset_exclude,
1489 		    ids[i], repo, loose_obj_only, ncolored, nfound, ntrees,
1490 		    progress_cb, progress_arg, rl, cancel_cb, cancel_arg);
1491 		if (err)
1492 			goto done;
1493 	}
1494 
1495 	for (i = 0; i < nours; i++) {
1496 		struct got_object_id *id = ours[i];
1497 		struct got_pack_meta *m;
1498 		if (id == NULL)
1499 			continue;
1500 		m = got_object_idset_get(idset, id);
1501 		if (m == NULL) {
1502 			err = got_object_get_type(&obj_type, repo, id);
1503 			if (err)
1504 				goto done;
1505 		} else
1506 			obj_type = m->obj_type;
1507 		if (obj_type != GOT_OBJ_TYPE_TAG)
1508 			continue;
1509 		err = load_tag(1, idset, idset_exclude, id, repo,
1510 		    loose_obj_only, ncolored, nfound, ntrees,
1511 		    progress_cb, progress_arg, rl, cancel_cb, cancel_arg);
1512 		if (err)
1513 			goto done;
1514 	}
1515 done:
1516 	for (i = 0; i < nobj; i++) {
1517 		free(ids[i]);
1518 	}
1519 	free(ids);
1520 	got_object_idset_free(idset_exclude);
1521 	return err;
1522 }
1523 
1524 const struct got_error *
1525 hwrite(FILE *f, void *buf, off_t len, SHA1_CTX *ctx)
1526 {
1527 	size_t n;
1528 
1529 	SHA1Update(ctx, buf, len);
1530 	n = fwrite(buf, 1, len, f);
1531 	if (n != len)
1532 		return got_ferror(f, GOT_ERR_IO);
1533 	return NULL;
1534 }
1535 
1536 const struct got_error *
1537 hcopy(FILE *fsrc, FILE *fdst, off_t len, SHA1_CTX *ctx)
1538 {
1539 	unsigned char buf[65536];
1540 	off_t remain = len;
1541 	size_t n;
1542 
1543 	while (remain > 0) {
1544 		size_t copylen = MIN(sizeof(buf), remain);
1545 		n = fread(buf, 1, copylen, fsrc);
1546 		if (n != copylen)
1547 			return got_ferror(fsrc, GOT_ERR_IO);
1548 		SHA1Update(ctx, buf, copylen);
1549 		n = fwrite(buf, 1, copylen, fdst);
1550 		if (n != copylen)
1551 			return got_ferror(fdst, GOT_ERR_IO);
1552 		remain -= copylen;
1553 	}
1554 
1555 	return NULL;
1556 }
1557 
1558 const struct got_error *
1559 hcopy_mmap(uint8_t *src, off_t src_offset, size_t src_size,
1560     FILE *fdst, off_t len, SHA1_CTX *ctx)
1561 {
1562 	size_t n;
1563 
1564 	if (src_offset + len > src_size)
1565 		return got_error(GOT_ERR_RANGE);
1566 
1567 	SHA1Update(ctx, src + src_offset, len);
1568 	n = fwrite(src + src_offset, 1, len, fdst);
1569 	if (n != len)
1570 		return got_ferror(fdst, GOT_ERR_IO);
1571 
1572 	return NULL;
1573 }
1574 
1575 static void
1576 putbe32(char *b, uint32_t n)
1577 {
1578 	b[0] = n >> 24;
1579 	b[1] = n >> 16;
1580 	b[2] = n >> 8;
1581 	b[3] = n >> 0;
1582 }
1583 
1584 static int
1585 write_order_cmp(const void *pa, const void *pb)
1586 {
1587 	struct got_pack_meta *a, *b, *ahd, *bhd;
1588 
1589 	a = *(struct got_pack_meta **)pa;
1590 	b = *(struct got_pack_meta **)pb;
1591 	ahd = (a->head == NULL) ? a : a->head;
1592 	bhd = (b->head == NULL) ? b : b->head;
1593 	if (bhd->mtime < ahd->mtime)
1594 		return -1;
1595 	if (bhd->mtime > ahd->mtime)
1596 		return 1;
1597 	if (bhd < ahd)
1598 		return -1;
1599 	if (bhd > ahd)
1600 		return 1;
1601 	if (a->nchain != b->nchain)
1602 		return a->nchain - b->nchain;
1603 	if (a->mtime < b->mtime)
1604 		return -1;
1605 	if (a->mtime > b->mtime)
1606 		return 1;
1607 	return got_object_id_cmp(&a->id, &b->id);
1608 }
1609 
1610 static int
1611 reuse_write_order_cmp(const void *pa, const void *pb)
1612 {
1613 	struct got_pack_meta *a, *b;
1614 
1615 	a = *(struct got_pack_meta **)pa;
1616 	b = *(struct got_pack_meta **)pb;
1617 
1618 	if (a->reused_delta_offset < b->reused_delta_offset)
1619 		return -1;
1620 	if (a->reused_delta_offset > b->reused_delta_offset)
1621 		return 1;
1622 	return 0;
1623 }
1624 
1625 static const struct got_error *
1626 packhdr(int *hdrlen, char *hdr, size_t bufsize, int obj_type, size_t len)
1627 {
1628 	size_t i;
1629 
1630 	*hdrlen = 0;
1631 
1632 	hdr[0] = obj_type << 4;
1633 	hdr[0] |= len & 0xf;
1634 	len >>= 4;
1635 	for (i = 1; len != 0; i++){
1636 		if (i >= bufsize)
1637 			return got_error(GOT_ERR_NO_SPACE);
1638 		hdr[i - 1] |= GOT_DELTA_SIZE_MORE;
1639 		hdr[i] = len & GOT_DELTA_SIZE_VAL_MASK;
1640 		len >>= GOT_DELTA_SIZE_SHIFT;
1641 	}
1642 
1643 	*hdrlen = i;
1644 	return NULL;
1645 }
1646 
1647 static int
1648 packoff(char *hdr, off_t off)
1649 {
1650 	int i, j;
1651 	char rbuf[8];
1652 
1653 	rbuf[0] = off & GOT_DELTA_SIZE_VAL_MASK;
1654 	for (i = 1; (off >>= GOT_DELTA_SIZE_SHIFT) != 0; i++) {
1655 		rbuf[i] = (--off & GOT_DELTA_SIZE_VAL_MASK) |
1656 		    GOT_DELTA_SIZE_MORE;
1657 	}
1658 
1659 	j = 0;
1660 	while (i > 0)
1661 		hdr[j++] = rbuf[--i];
1662 	return j;
1663 }
1664 
1665 static const struct got_error *
1666 deltahdr(off_t *packfile_size, SHA1_CTX *ctx, FILE *packfile,
1667     struct got_pack_meta *m)
1668 {
1669 	const struct got_error *err;
1670 	char buf[32];
1671 	int nh;
1672 
1673 	if (m->prev->off != 0) {
1674 		err = packhdr(&nh, buf, sizeof(buf),
1675 		    GOT_OBJ_TYPE_OFFSET_DELTA, m->delta_len);
1676 		if (err)
1677 			return err;
1678 		nh += packoff(buf + nh, m->off - m->prev->off);
1679 		err = hwrite(packfile, buf, nh, ctx);
1680 		if (err)
1681 			return err;
1682 		*packfile_size += nh;
1683 	} else {
1684 		err = packhdr(&nh, buf, sizeof(buf),
1685 		    GOT_OBJ_TYPE_REF_DELTA, m->delta_len);
1686 		if (err)
1687 			return err;
1688 		err = hwrite(packfile, buf, nh, ctx);
1689 		if (err)
1690 			return err;
1691 		*packfile_size += nh;
1692 		err = hwrite(packfile, m->prev->id.sha1,
1693 		    sizeof(m->prev->id.sha1), ctx);
1694 		if (err)
1695 			return err;
1696 		*packfile_size += sizeof(m->prev->id.sha1);
1697 	}
1698 
1699 	return NULL;
1700 }
1701 
1702 static const struct got_error *
1703 write_packed_object(off_t *packfile_size, FILE *packfile,
1704     FILE *delta_cache, uint8_t *delta_cache_map, size_t delta_cache_size,
1705     struct got_pack_meta *m, int *outfd, SHA1_CTX *ctx,
1706     struct got_repository *repo)
1707 {
1708 	const struct got_error *err = NULL;
1709 	struct got_deflate_checksum csum;
1710 	char buf[32];
1711 	int nh;
1712 	struct got_raw_object *raw = NULL;
1713 	off_t outlen;
1714 
1715 	csum.output_sha1 = ctx;
1716 	csum.output_crc = NULL;
1717 
1718 	m->off = ftello(packfile);
1719 	if (m->delta_len == 0) {
1720 		err = got_object_raw_open(&raw, outfd, repo, &m->id);
1721 		if (err)
1722 			goto done;
1723 		err = packhdr(&nh, buf, sizeof(buf),
1724 		    m->obj_type, raw->size);
1725 		if (err)
1726 			goto done;
1727 		err = hwrite(packfile, buf, nh, ctx);
1728 		if (err)
1729 			goto done;
1730 		*packfile_size += nh;
1731 		if (raw->f == NULL) {
1732 			err = got_deflate_to_file_mmap(&outlen,
1733 			    raw->data + raw->hdrlen, 0, raw->size,
1734 			    packfile, &csum);
1735 			if (err)
1736 				goto done;
1737 		} else {
1738 			if (fseeko(raw->f, raw->hdrlen, SEEK_SET)
1739 			    == -1) {
1740 				err = got_error_from_errno("fseeko");
1741 				goto done;
1742 			}
1743 			err = got_deflate_to_file(&outlen, raw->f,
1744 			    raw->size, packfile, &csum);
1745 			if (err)
1746 				goto done;
1747 		}
1748 		*packfile_size += outlen;
1749 		got_object_raw_close(raw);
1750 		raw = NULL;
1751 	} else if (m->delta_buf) {
1752 		err = deltahdr(packfile_size, ctx, packfile, m);
1753 		if (err)
1754 			goto done;
1755 		err = hwrite(packfile, m->delta_buf,
1756 		    m->delta_compressed_len, ctx);
1757 		if (err)
1758 			goto done;
1759 		*packfile_size += m->delta_compressed_len;
1760 		free(m->delta_buf);
1761 		m->delta_buf = NULL;
1762 	} else if (delta_cache_map) {
1763 		err = deltahdr(packfile_size, ctx, packfile, m);
1764 		if (err)
1765 			goto done;
1766 		err = hcopy_mmap(delta_cache_map, m->delta_offset,
1767 		    delta_cache_size, packfile, m->delta_compressed_len,
1768 		    ctx);
1769 		if (err)
1770 			goto done;
1771 		*packfile_size += m->delta_compressed_len;
1772 	} else {
1773 		if (fseeko(delta_cache, m->delta_offset, SEEK_SET)
1774 		    == -1) {
1775 			err = got_error_from_errno("fseeko");
1776 			goto done;
1777 		}
1778 		err = deltahdr(packfile_size, ctx, packfile, m);
1779 		if (err)
1780 			goto done;
1781 		err = hcopy(delta_cache, packfile,
1782 		    m->delta_compressed_len, ctx);
1783 		if (err)
1784 			goto done;
1785 		*packfile_size += m->delta_compressed_len;
1786 	}
1787 done:
1788 	if (raw)
1789 		got_object_raw_close(raw);
1790 	return err;
1791 }
1792 
1793 static const struct got_error *
1794 genpack(uint8_t *pack_sha1, FILE *packfile, FILE *delta_cache,
1795     struct got_pack_meta **deltify, int ndeltify,
1796     struct got_pack_meta **reuse, int nreuse,
1797     int ncolored, int nfound, int ntrees, int nours,
1798     struct got_repository *repo,
1799     got_pack_progress_cb progress_cb, void *progress_arg,
1800     struct got_ratelimit *rl,
1801     got_cancel_cb cancel_cb, void *cancel_arg)
1802 {
1803 	const struct got_error *err = NULL;
1804 	int i;
1805 	SHA1_CTX ctx;
1806 	struct got_pack_meta *m;
1807 	char buf[32];
1808 	size_t n;
1809 	off_t packfile_size = 0;
1810 	int outfd = -1;
1811 	int delta_cache_fd = -1;
1812 	uint8_t *delta_cache_map = NULL;
1813 	size_t delta_cache_size = 0;
1814 
1815 	SHA1Init(&ctx);
1816 
1817 #ifndef GOT_PACK_NO_MMAP
1818 	delta_cache_fd = dup(fileno(delta_cache));
1819 	if (delta_cache_fd != -1) {
1820 		struct stat sb;
1821 		if (fstat(delta_cache_fd, &sb) == -1) {
1822 			err = got_error_from_errno("fstat");
1823 			goto done;
1824 		}
1825 		if (sb.st_size > 0 && sb.st_size <= SIZE_MAX) {
1826 			delta_cache_map = mmap(NULL, sb.st_size,
1827 			    PROT_READ, MAP_PRIVATE, delta_cache_fd, 0);
1828 			if (delta_cache_map == MAP_FAILED) {
1829 				if (errno != ENOMEM) {
1830 					err = got_error_from_errno("mmap");
1831 					goto done;
1832 				}
1833 				delta_cache_map = NULL; /* fallback on stdio */
1834 			} else
1835 				delta_cache_size = (size_t)sb.st_size;
1836 		}
1837 	}
1838 #endif
1839 	err = hwrite(packfile, "PACK", 4, &ctx);
1840 	if (err)
1841 		goto done;
1842 	putbe32(buf, GOT_PACKFILE_VERSION);
1843 	err = hwrite(packfile, buf, 4, &ctx);
1844 	if (err)
1845 		goto done;
1846 	putbe32(buf, ndeltify + nreuse);
1847 	err = hwrite(packfile, buf, 4, &ctx);
1848 	if (err)
1849 		goto done;
1850 
1851 	qsort(deltify, ndeltify, sizeof(struct got_pack_meta *),
1852 	    write_order_cmp);
1853 	for (i = 0; i < ndeltify; i++) {
1854 		err = report_progress(progress_cb, progress_arg, rl,
1855 		    ncolored, nfound, ntrees, packfile_size, nours,
1856 		    ndeltify + nreuse, ndeltify + nreuse, i);
1857 		if (err)
1858 			goto done;
1859 		m = deltify[i];
1860 		err = write_packed_object(&packfile_size, packfile,
1861 		    delta_cache, delta_cache_map, delta_cache_size,
1862 		    m, &outfd, &ctx, repo);
1863 		if (err)
1864 			goto done;
1865 	}
1866 
1867 	qsort(reuse, nreuse, sizeof(struct got_pack_meta *),
1868 	    reuse_write_order_cmp);
1869 	for (i = 0; i < nreuse; i++) {
1870 		err = report_progress(progress_cb, progress_arg, rl,
1871 		    ncolored, nfound, ntrees, packfile_size, nours,
1872 		    ndeltify + nreuse, ndeltify + nreuse, ndeltify + i);
1873 		if (err)
1874 			goto done;
1875 		m = reuse[i];
1876 		err = write_packed_object(&packfile_size, packfile,
1877 		    delta_cache, delta_cache_map, delta_cache_size,
1878 		    m, &outfd, &ctx, repo);
1879 		if (err)
1880 			goto done;
1881 	}
1882 
1883 	SHA1Final(pack_sha1, &ctx);
1884 	n = fwrite(pack_sha1, 1, SHA1_DIGEST_LENGTH, packfile);
1885 	if (n != SHA1_DIGEST_LENGTH)
1886 		err = got_ferror(packfile, GOT_ERR_IO);
1887 	packfile_size += SHA1_DIGEST_LENGTH;
1888 	packfile_size += sizeof(struct got_packfile_hdr);
1889 	if (progress_cb) {
1890 		err = progress_cb(progress_arg, ncolored, nfound, ntrees,
1891 		    packfile_size, nours, ndeltify + nreuse,
1892 		    ndeltify + nreuse, ndeltify + nreuse);
1893 		if (err)
1894 			goto done;
1895 	}
1896 done:
1897 	if (outfd != -1 && close(outfd) == -1 && err == NULL)
1898 		err = got_error_from_errno("close");
1899 	if (delta_cache_map && munmap(delta_cache_map, delta_cache_size) == -1)
1900 		err = got_error_from_errno("munmap");
1901 	if (delta_cache_fd != -1 && close(delta_cache_fd) == -1 && err == NULL)
1902 		err = got_error_from_errno("close");
1903 	return err;
1904 }
1905 
1906 static const struct got_error *
1907 add_meta_idset_cb(struct got_object_id *id, void *data, void *arg)
1908 {
1909 	struct got_pack_meta *m = data;
1910 	struct got_pack_metavec *v = arg;
1911 
1912 	if (m->have_reused_delta)
1913 		return NULL;
1914 
1915 	return add_meta(m, v);
1916 }
1917 
1918 const struct got_error *
1919 got_pack_create(uint8_t *packsha1, FILE *packfile,
1920     struct got_object_id **theirs, int ntheirs,
1921     struct got_object_id **ours, int nours,
1922     struct got_repository *repo, int loose_obj_only, int allow_empty,
1923     got_pack_progress_cb progress_cb, void *progress_arg,
1924     got_cancel_cb cancel_cb, void *cancel_arg)
1925 {
1926 	const struct got_error *err;
1927 	int delta_cache_fd = -1;
1928 	FILE *delta_cache = NULL;
1929 	struct got_object_idset *idset;
1930 	struct got_ratelimit rl;
1931 	struct got_pack_metavec deltify, reuse;
1932 	int ncolored = 0, nfound = 0, ntrees = 0;
1933 	size_t ndeltify;
1934 
1935 	memset(&deltify, 0, sizeof(deltify));
1936 	memset(&reuse, 0, sizeof(reuse));
1937 
1938 	got_ratelimit_init(&rl, 0, 500);
1939 
1940 	idset = got_object_idset_alloc();
1941 	if (idset == NULL)
1942 		return got_error_from_errno("got_object_idset_alloc");
1943 
1944 	err = load_object_ids(&ncolored, &nfound, &ntrees, idset, theirs,
1945 	    ntheirs, ours, nours, repo, loose_obj_only,
1946 	    progress_cb, progress_arg, &rl, cancel_cb, cancel_arg);
1947 	if (err)
1948 		return err;
1949 
1950 	if (progress_cb) {
1951 		err = progress_cb(progress_arg, ncolored, nfound, ntrees,
1952 		    0L, nours, got_object_idset_num_elements(idset), 0, 0);
1953 		if (err)
1954 			goto done;
1955 	}
1956 
1957 	if (got_object_idset_num_elements(idset) == 0 && !allow_empty) {
1958 		err = got_error(GOT_ERR_CANNOT_PACK);
1959 		goto done;
1960 	}
1961 
1962 	delta_cache_fd = got_opentempfd();
1963 	if (delta_cache_fd == -1) {
1964 		err = got_error_from_errno("got_opentemp");
1965 		goto done;
1966 	}
1967 
1968 	reuse.metasz = 64;
1969 	reuse.meta = calloc(reuse.metasz,
1970 	    sizeof(struct got_pack_meta *));
1971 	if (reuse.meta == NULL) {
1972 		err = got_error_from_errno("calloc");
1973 		goto done;
1974 	}
1975 
1976 	err = search_deltas(&reuse, idset, delta_cache_fd, ncolored, nfound,
1977 	    ntrees, nours, repo, progress_cb, progress_arg, &rl,
1978 	    cancel_cb, cancel_arg);
1979 	if (err)
1980 		goto done;
1981 
1982 	delta_cache = fdopen(delta_cache_fd, "a+");
1983 	if (delta_cache == NULL) {
1984 		err = got_error_from_errno("fdopen");
1985 		goto done;
1986 	}
1987 	delta_cache_fd = -1;
1988 
1989 	if (fseeko(delta_cache, 0L, SEEK_END) == -1) {
1990 		err = got_error_from_errno("fseeko");
1991 		goto done;
1992 	}
1993 
1994 	ndeltify = got_object_idset_num_elements(idset) - reuse.nmeta;
1995 	if (ndeltify > 0) {
1996 		deltify.meta = calloc(ndeltify, sizeof(struct got_pack_meta *));
1997 		if (deltify.meta == NULL) {
1998 			err = got_error_from_errno("calloc");
1999 			goto done;
2000 		}
2001 		deltify.metasz = ndeltify;
2002 
2003 		err = got_object_idset_for_each(idset, add_meta_idset_cb,
2004 		    &deltify);
2005 		if (err)
2006 			goto done;
2007 		if (deltify.nmeta > 0) {
2008 			err = pick_deltas(deltify.meta, deltify.nmeta,
2009 			    ncolored, nfound, ntrees, nours, reuse.nmeta,
2010 			    delta_cache, repo, progress_cb, progress_arg, &rl,
2011 			    cancel_cb, cancel_arg);
2012 			if (err)
2013 				goto done;
2014 		}
2015 	}
2016 
2017 	if (fflush(delta_cache) == EOF) {
2018 		err = got_error_from_errno("fflush");
2019 		goto done;
2020 	}
2021 	err = genpack(packsha1, packfile, delta_cache, deltify.meta,
2022 	    deltify.nmeta, reuse.meta, reuse.nmeta, ncolored, nfound, ntrees,
2023 	    nours, repo, progress_cb, progress_arg, &rl,
2024 	    cancel_cb, cancel_arg);
2025 	if (err)
2026 		goto done;
2027 done:
2028 	free_nmeta(deltify.meta, deltify.nmeta);
2029 	free_nmeta(reuse.meta, reuse.nmeta);
2030 	got_object_idset_free(idset);
2031 	if (delta_cache_fd != -1 && close(delta_cache_fd) == -1 && err == NULL)
2032 		err = got_error_from_errno("close");
2033 	if (delta_cache && fclose(delta_cache) == EOF && err == NULL)
2034 		err = got_error_from_errno("fclose");
2035 	return err;
2036 }