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