Gotweb

Blob

Date:: Fri Oct 15 19:22:03 2021 UTC
Message:: reuse temporary files which were not used by got_object_raw_open()
Actions:: History | Blame | Raw File
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 
24 #include <stdint.h>
25 #include <stdio.h>
26 #include <stdlib.h>
27 #include <string.h>
28 #include <limits.h>
29 #include <zlib.h>
30 
31 #include "got_error.h"
32 #include "got_cancel.h"
33 #include "got_object.h"
34 #include "got_path.h"
35 #include "got_reference.h"
36 #include "got_repository_admin.h"
37 #include "got_opentemp.h"
38 
39 #include "got_lib_deltify.h"
40 #include "got_lib_delta.h"
41 #include "got_lib_object.h"
42 #include "got_lib_object_idset.h"
43 #include "got_lib_object_cache.h"
44 #include "got_lib_deflate.h"
45 #include "got_lib_pack.h"
46 #include "got_lib_privsep.h"
47 #include "got_lib_repository.h"
48 
49 #ifndef MAX
50 #define	MAX(_a,_b) ((_a) > (_b) ? (_a) : (_b))
51 #endif
52 
53 struct got_pack_meta {
54 	struct got_object_id id;
55 	char	*path;
56 	int	obj_type;
57 	off_t	size;
58 	time_t	mtime;
59 
60 	/* The best delta we picked */
61 	struct got_pack_meta *head;
62 	struct got_pack_meta *prev;
63 	struct got_delta_instruction *deltas;
64 	int	ndeltas;
65 	int	nchain;
66 
67 	/* Only used for delta window */
68 	struct got_delta_table *dtab;
69 
70 	/* Only used for writing offset deltas */
71 	off_t	off;
72 };
73 
74 struct got_pack_metavec {
75 	struct got_pack_meta **meta;
76 	int nmeta;
77 	int metasz;
78 };
79 
80 static const struct got_error *
81 alloc_meta(struct got_pack_meta **new, struct got_object_id *id,
82     const char *path, int obj_type, time_t mtime)
83 {
84 	const struct got_error *err = NULL;
85 	struct got_pack_meta *m;
86 
87 	*new = NULL;
88 
89 	m = calloc(1, sizeof(*m));
90 	if (m == NULL)
91 		return got_error_from_errno("calloc");
92 
93 	memcpy(&m->id, id, sizeof(m->id));
94 
95 	m->path = strdup(path);
96 	if (m->path == NULL) {
97 		err = got_error_from_errno("strdup");
98 		free(m);
99 		return err;
100 	}
101 
102 	m->obj_type = obj_type;
103 	m->mtime = mtime;
104 	*new = m;
105 	return NULL;
106 }
107 
108 static void
109 clear_meta(struct got_pack_meta *meta)
110 {
111 	if (meta == NULL)
112 		return;
113 	free(meta->deltas);
114 	meta->deltas = NULL;
115 	free(meta->path);
116 	meta->path = NULL;
117 }
118 
119 static void
120 free_nmeta(struct got_pack_meta **meta, int nmeta)
121 {
122 	int i;
123 
124 	for (i = 0; i < nmeta; i++)
125 		clear_meta(meta[i]);
126 	free(meta);
127 }
128 
129 static int
130 delta_order_cmp(const void *pa, const void *pb)
131 {
132 	struct got_pack_meta *a, *b;
133 	int cmp;
134 
135 	a = *(struct got_pack_meta **)pa;
136 	b = *(struct got_pack_meta **)pb;
137 
138 	if (a->obj_type != b->obj_type)
139 		return a->obj_type - b->obj_type;
140 	cmp = strcmp(a->path, b->path);
141 	if (cmp != 0)
142 		return cmp;
143 	if (a->mtime != b->mtime)
144 		return a->mtime - b->mtime;
145 	return got_object_id_cmp(&a->id, &b->id);
146 }
147 
148 static int
149 delta_size(struct got_delta_instruction *deltas, int ndeltas)
150 {
151 	int i, size = 32;
152 	for (i = 0; i < ndeltas; i++) {
153 		if (deltas[i].copy)
154 			size += GOT_DELTA_SIZE_SHIFT;
155 		else
156 			size += deltas[i].len + 1;
157 	}
158 	return size;
159 }
160 
161 
162 static const struct got_error *
163 pick_deltas(struct got_pack_meta **meta, int nmeta, int nours,
164     struct got_repository *repo,
165     got_pack_progress_cb progress_cb, void *progress_arg,
166     got_cancel_cb cancel_cb, void *cancel_arg)
167 {
168 	const struct got_error *err = NULL;
169 	struct got_pack_meta *m = NULL, *base = NULL;
170 	struct got_raw_object *raw = NULL, *base_raw = NULL;
171 	struct got_delta_instruction *deltas;
172 	int i, j, size, ndeltas, best;
173 	const int max_base_candidates = 10;
174 	int outfd = -1;
175 
176 	qsort(meta, nmeta, sizeof(struct got_pack_meta *), delta_order_cmp);
177 	for (i = 0; i < nmeta; i++) {
178 		if (cancel_cb) {
179 			err = (*cancel_cb)(cancel_arg);
180 			if (err)
181 				break;
182 		}
183 		if (progress_cb) {
184 			err = progress_cb(progress_arg, 0L, nours, nmeta, i, 0);
185 			if (err)
186 				goto done;
187 		}
188 		m = meta[i];
189 		m->deltas = NULL;
190 		m->ndeltas = 0;
191 
192 		if (m->obj_type == GOT_OBJ_TYPE_COMMIT ||
193 		    m->obj_type == GOT_OBJ_TYPE_TAG)
194 			continue;
195 
196 		if (outfd == -1) {
197 			outfd = got_opentempfd();
198 			if (outfd == -1) {
199 				err = got_error_from_errno("got_opentempfd");
200 				goto done;
201 			}
202 		}
203 		err = got_object_raw_open(&raw, outfd, repo, &m->id, 8192);
204 		if (err)
205 			goto done;
206 		if (raw->data == NULL)
207 			outfd = -1; /* outfd is now raw->f */
208 		m->size = raw->size;
209 
210 		err = got_deltify_init(&m->dtab, raw->f, raw->hdrlen,
211 		    raw->size + raw->hdrlen);
212 		if (err)
213 			goto done;
214 
215 		if (i > max_base_candidates) {
216 			struct got_pack_meta *n = NULL;
217 			n = meta[i - (max_base_candidates + 1)];
218 			got_deltify_free(n->dtab);
219 			n->dtab = NULL;
220 		}
221 
222 		best = raw->size;
223 		for (j = MAX(0, i - max_base_candidates); j < i; j++) {
224 			if (cancel_cb) {
225 				err = (*cancel_cb)(cancel_arg);
226 				if (err)
227 					goto done;
228 			}
229 			base = meta[j];
230 			/* long chains make unpacking slow, avoid such bases */
231 			if (base->nchain >= 128 ||
232 			    base->obj_type != m->obj_type)
233 				continue;
234 
235 			if (outfd == -1) {
236 				outfd = got_opentempfd();
237 				if (outfd == -1) {
238 					err = got_error_from_errno(
239 					    "got_opentempfd");
240 					goto done;
241 				}
242 			}
243 			err = got_object_raw_open(&base_raw, outfd, repo,
244 			    &base->id, 8192);
245 			if (err)
246 				goto done;
247 			if (base_raw->data == NULL)
248 				outfd = -1; /* outfd is now base_raw->f */
249 			err = got_deltify(&deltas, &ndeltas,
250 			    raw->f, raw->hdrlen, raw->size + raw->hdrlen,
251 			    base->dtab, base_raw->f, base_raw->hdrlen,
252 			    base_raw->size + base_raw->hdrlen);
253 			got_object_raw_close(base_raw);
254 			base_raw = NULL;
255 			if (err)
256 				goto done;
257 
258 			size = delta_size(deltas, ndeltas);
259 			if (size + 32 < best){
260 				/*
261 				 * if we already picked a best delta,
262 				 * replace it.
263 				 */
264 				free(m->deltas);
265 				best = size;
266 				m->deltas = deltas;
267 				m->ndeltas = ndeltas;
268 				m->nchain = base->nchain + 1;
269 				m->prev = base;
270 				m->head = base->head;
271 				if (m->head == NULL)
272 					m->head = base;
273 			} else {
274 				free(deltas);
275 				deltas = NULL;
276 				ndeltas = 0;
277 			}
278 		}
279 
280 		got_object_raw_close(raw);
281 		raw = NULL;
282 	}
283 done:
284 	for (i = MAX(0, nmeta - max_base_candidates); i < nmeta; i++) {
285 		got_deltify_free(meta[i]->dtab);
286 		meta[i]->dtab = NULL;
287 	}
288 	if (raw)
289 		got_object_raw_close(raw);
290 	if (base_raw)
291 		got_object_raw_close(base_raw);
292 	if (outfd != -1 && close(outfd) == -1 && err == NULL)
293 		err = got_error_from_errno("close");
294 	return err;
295 }
296 
297 static const struct got_error *
298 search_packidx(int *found, struct got_object_id *id,
299     struct got_repository *repo)
300 {
301 	const struct got_error *err = NULL;
302 	struct got_packidx *packidx = NULL;
303 	int idx;
304 
305 	*found = 0;
306 
307 	err = got_repo_search_packidx(&packidx, &idx, repo, id);
308 	if (err == NULL)
309 		*found = 1; /* object is already packed */
310 	else if (err->code == GOT_ERR_NO_OBJ)
311 		err = NULL;
312 	return err;
313 }
314 
315 static const int obj_types[] = {
316 	GOT_OBJ_TYPE_ANY,
317 	GOT_OBJ_TYPE_COMMIT,
318 	GOT_OBJ_TYPE_TREE,
319 	GOT_OBJ_TYPE_BLOB,
320 	GOT_OBJ_TYPE_TAG,
321 	GOT_OBJ_TYPE_OFFSET_DELTA,
322 	GOT_OBJ_TYPE_REF_DELTA
323 };
324 
325 static const struct got_error *
326 add_meta(struct got_pack_metavec *v, struct got_object_idset *idset,
327     struct got_object_id *id, const char *path, int obj_type,
328     time_t mtime, int loose_obj_only, struct got_repository *repo)
329 {
330 	const struct got_error *err;
331 	struct got_pack_meta *m;
332 
333 	if (loose_obj_only) {
334 		int is_packed;
335 		err = search_packidx(&is_packed, id, repo);
336 		if (err)
337 			return err;
338 		if (is_packed)
339 			return NULL;
340 	}
341 
342 	err = got_object_idset_add(idset, id, (void *)&obj_types[obj_type]);
343 	if (err)
344 		return err;
345 
346 	if (v == NULL)
347 		return NULL;
348 
349 	err = alloc_meta(&m, id, path, obj_type, mtime);
350 	if (err)
351 		goto done;
352 
353 	if (v->nmeta == v->metasz){
354 		size_t newsize = 2 * v->metasz;
355 		struct got_pack_meta **new;
356 		new = reallocarray(v->meta, newsize, sizeof(*new));
357 		if (new == NULL) {
358 			err = got_error_from_errno("reallocarray");
359 			goto done;
360 		}
361 		v->meta = new;
362 		v->metasz = newsize; 
363 	}
364 done:
365 	if (err) {
366 		clear_meta(m);
367 		free(m);
368 	} else
369 		v->meta[v->nmeta++] = m;
370 
371 	return err;
372 }
373 
374 static const struct got_error *
375 load_tree_entries(struct got_object_id_queue *ids, struct got_pack_metavec *v,
376     struct got_object_idset *idset, struct got_object_id *tree_id,
377     const char *dpath, time_t mtime, struct got_repository *repo,
378     int loose_obj_only, got_cancel_cb cancel_cb, void *cancel_arg)
379 {
380 	const struct got_error *err;
381 	struct got_tree_object *tree;
382 	char *p = NULL;
383 	int i;
384 
385 	err = got_object_open_as_tree(&tree, repo, tree_id);
386 	if (err)
387 		return err;
388 
389 	for (i = 0; i < got_object_tree_get_nentries(tree); i++) {
390 		struct got_tree_entry *e = got_object_tree_get_entry(tree, i);
391 		struct got_object_id *id = got_tree_entry_get_id(e);
392 		mode_t mode = got_tree_entry_get_mode(e);
393 
394 		if (cancel_cb) {
395 			err = (*cancel_cb)(cancel_arg);
396 			if (err)
397 				break;
398 		}
399 
400 		if (got_object_tree_entry_is_submodule(e) ||
401 		    got_object_idset_contains(idset, id))
402 			continue;
403 		
404 		if (asprintf(&p, "%s%s%s", dpath, dpath[0] != '\0' ? "/" : "",
405 		    got_tree_entry_get_name(e)) == -1) {
406 			err = got_error_from_errno("asprintf");
407 			break;
408 		}
409 
410 		if (S_ISDIR(mode)) {
411 			struct got_object_qid *qid;
412 			err = got_object_qid_alloc(&qid, id);
413 			if (err)
414 				break;
415 			STAILQ_INSERT_TAIL(ids, qid, entry);
416 		} else if (S_ISREG(mode) || S_ISLNK(mode)) {
417 			err = add_meta(v, idset, id, p, GOT_OBJ_TYPE_BLOB,
418 			    mtime, loose_obj_only, repo);
419 			if (err)
420 				break;
421 		}
422 		free(p);
423 		p = NULL;
424 	}
425 
426 	got_object_tree_close(tree);
427 	free(p);
428 	return err;
429 }
430 
431 static const struct got_error *
432 load_tree(struct got_pack_metavec *v, struct got_object_idset *idset,
433     struct got_object_id *tree_id, const char *dpath, time_t mtime,
434     int loose_obj_only, struct got_repository *repo,
435     got_cancel_cb cancel_cb, void *cancel_arg)
436 {
437 	const struct got_error *err = NULL;
438 	struct got_object_id_queue tree_ids;
439 	struct got_object_qid *qid;
440 
441 	if (got_object_idset_contains(idset, tree_id))
442 		return NULL;
443 
444 	err = got_object_qid_alloc(&qid, tree_id);
445 	if (err)
446 		return err;
447 
448 	STAILQ_INIT(&tree_ids);
449 	STAILQ_INSERT_TAIL(&tree_ids, qid, entry);
450 
451 	while (!STAILQ_EMPTY(&tree_ids)) {
452 		if (cancel_cb) {
453 			err = (*cancel_cb)(cancel_arg);
454 			if (err)
455 				break;
456 		}
457 
458 		qid = STAILQ_FIRST(&tree_ids);
459 		STAILQ_REMOVE_HEAD(&tree_ids, entry);
460 
461 		if (got_object_idset_contains(idset, qid->id)) {
462 			got_object_qid_free(qid);
463 			continue;
464 		}
465 
466 		err = add_meta(v, idset, qid->id, dpath, GOT_OBJ_TYPE_TREE,
467 		    mtime, loose_obj_only, repo);
468 		if (err) {
469 			got_object_qid_free(qid);
470 			break;
471 		}
472 
473 		err = load_tree_entries(&tree_ids, v, idset, qid->id, dpath,
474 		    mtime, repo, loose_obj_only, cancel_cb, cancel_arg);
475 		got_object_qid_free(qid);
476 		if (err)
477 			break;
478 	}
479 
480 	got_object_id_queue_free(&tree_ids);
481 	return err;
482 }
483 
484 static const struct got_error *
485 load_commit(struct got_pack_metavec *v, struct got_object_idset *idset,
486     struct got_object_id *id, struct got_repository *repo, int loose_obj_only,
487     got_cancel_cb cancel_cb, void *cancel_arg)
488 {
489 	const struct got_error *err;
490 	struct got_commit_object *commit;
491 
492 	if (got_object_idset_contains(idset, id))
493 		return NULL;
494 
495 	if (loose_obj_only) {
496 		int is_packed;
497 		err = search_packidx(&is_packed, id, repo);
498 		if (err)
499 			return err;
500 		if (is_packed)
501 			return NULL;
502 	}
503 
504 	err = got_object_open_as_commit(&commit, repo, id);
505 	if (err)
506 		return err;
507 
508 	err = add_meta(v, idset, id, "", GOT_OBJ_TYPE_COMMIT,
509 	    got_object_commit_get_committer_time(commit),
510 	    loose_obj_only, repo);
511 	if (err)
512 		goto done;
513 
514 	err = load_tree(v, idset, got_object_commit_get_tree_id(commit),
515 	    "", got_object_commit_get_committer_time(commit),
516 	    loose_obj_only, repo, cancel_cb, cancel_arg);
517 done:
518 	got_object_commit_close(commit);
519 	return err;
520 }
521 
522 static const struct got_error *
523 load_tag(struct got_pack_metavec *v, struct got_object_idset *idset,
524     struct got_object_id *id, struct got_repository *repo, int loose_obj_only,
525     got_cancel_cb cancel_cb, void *cancel_arg)
526 {
527 	const struct got_error *err;
528 	struct got_tag_object *tag = NULL;
529 
530 	if (got_object_idset_contains(idset, id))
531 		return NULL;
532 
533 	if (loose_obj_only) {
534 		int is_packed;
535 		err = search_packidx(&is_packed, id, repo);
536 		if (err)
537 			return err;
538 		if (is_packed)
539 			return NULL;
540 	}
541 
542 	err = got_object_open_as_tag(&tag, repo, id);
543 	if (err)
544 		return err;
545 
546 	err = add_meta(v, idset, id, "", GOT_OBJ_TYPE_TAG,
547 	    got_object_tag_get_tagger_time(tag),
548 	    loose_obj_only, repo);
549 	if (err)
550 		goto done;
551 
552 	switch (got_object_tag_get_object_type(tag)) {
553 	case GOT_OBJ_TYPE_COMMIT:
554 		err = load_commit(v, idset,
555 		    got_object_tag_get_object_id(tag), repo,
556 		    loose_obj_only, cancel_cb, cancel_arg);
557 		break;
558 	case GOT_OBJ_TYPE_TREE:
559 		err = load_tree(v, idset, got_object_tag_get_object_id(tag),
560 		    "", got_object_tag_get_tagger_time(tag),
561 		    loose_obj_only, repo, cancel_cb, cancel_arg);
562 		break;
563 	default:
564 		break;
565 	}
566 
567 done:
568 	got_object_tag_close(tag);
569 	return err;
570 }
571 
572 enum findtwixt_color {
573 	COLOR_KEEP = 0,
574 	COLOR_DROP,
575 	COLOR_BLANK,
576 };
577 static const int findtwixt_colors[] = {
578 	COLOR_KEEP,
579 	COLOR_DROP,
580 	COLOR_BLANK
581 };
582 
583 static const struct got_error *
584 queue_commit_id(struct got_object_id_queue *ids, struct got_object_id *id,
585     int color, struct got_repository *repo)
586 {
587 	const struct got_error *err;
588 	struct got_object_qid *qid;
589 
590 	err = got_object_qid_alloc(&qid, id);
591 	if (err)
592 		return err;
593 
594 	STAILQ_INSERT_TAIL(ids, qid, entry);
595 	qid->data = (void *)&findtwixt_colors[color];
596 	return NULL;
597 }
598 
599 static const struct got_error *
600 drop_commit(struct got_object_idset *keep, struct got_object_idset *drop,
601     struct got_object_id *id, struct got_repository *repo,
602     got_cancel_cb cancel_cb, void *cancel_arg)
603 {
604 	const struct got_error *err = NULL;
605 	struct got_commit_object *commit;
606 	const struct got_object_id_queue *parents;
607 	struct got_object_id_queue ids;
608 	struct got_object_qid *qid;
609 
610 	STAILQ_INIT(&ids);
611 
612 	err = got_object_qid_alloc(&qid, id);
613 	if (err)
614 		return err;
615 	STAILQ_INSERT_HEAD(&ids, qid, entry);
616 
617 	while (!STAILQ_EMPTY(&ids)) {
618 		if (cancel_cb) {
619 			err = (*cancel_cb)(cancel_arg);
620 			if (err)
621 				break;
622 		}
623 
624 		qid = STAILQ_FIRST(&ids);
625 		STAILQ_REMOVE_HEAD(&ids, entry);
626 
627 		if (got_object_idset_contains(drop, qid->id)) {
628 			got_object_qid_free(qid);
629 			continue;
630 		}
631 
632 		err = got_object_idset_add(drop, qid->id,
633 		    (void *)&obj_types[GOT_OBJ_TYPE_COMMIT]);
634 		if (err) {
635 			got_object_qid_free(qid);
636 			break;
637 		}
638 
639 		if (!got_object_idset_contains(keep, qid->id)) {
640 			got_object_qid_free(qid);
641 			continue;
642 		}
643 
644 		err = got_object_open_as_commit(&commit, repo, qid->id);
645 		got_object_qid_free(qid);
646 		if (err)
647 			break;
648 
649 		parents = got_object_commit_get_parent_ids(commit);
650 		if (parents) {
651 			err = got_object_id_queue_copy(parents, &ids);
652 			if (err) {
653 				got_object_commit_close(commit);
654 				break;
655 			}
656 		}
657 		got_object_commit_close(commit);
658 	}
659 
660 	got_object_id_queue_free(&ids);
661 	return err;
662 }
663 
664 struct append_id_arg {
665 	struct got_object_id **array;
666 	int idx;
667 };
668 
669 static const struct got_error *
670 append_id(struct got_object_id *id, void *data, void *arg)
671 {
672 	struct append_id_arg *a = arg;
673 
674 	a->array[a->idx] = got_object_id_dup(id);
675 	if (a->array[a->idx] == NULL)
676 		return got_error_from_errno("got_object_id_dup");
677 
678 	a->idx++;
679 	return NULL;
680 }
681 
682 static const struct got_error *
683 findtwixt(struct got_object_id ***res, int *nres,
684     struct got_object_id **head, int nhead,
685     struct got_object_id **tail, int ntail,
686     struct got_repository *repo,
687     got_cancel_cb cancel_cb, void *cancel_arg)
688 {
689 	const struct got_error *err = NULL;
690 	struct got_object_id_queue ids;
691 	struct got_object_idset *keep, *drop;
692 	struct got_object_qid *qid;
693 	int i, ncolor, nkeep, obj_type;
694 
695 	STAILQ_INIT(&ids);
696 	*res = NULL;
697 	*nres = 0;
698 
699 	keep = got_object_idset_alloc();
700 	if (keep == NULL)
701 		return got_error_from_errno("got_object_idset_alloc");
702 
703 	drop = got_object_idset_alloc();
704 	if (drop == NULL) {
705 		err = got_error_from_errno("got_object_idset_alloc");
706 		goto done;
707 	}
708 
709 	for (i = 0; i < nhead; i++) {
710 		struct got_object_id *id = head[i];
711 		if (id == NULL)
712 			continue;
713 		err = got_object_get_type(&obj_type, repo, id);
714 		if (err)
715 			return err;
716 		if (obj_type != GOT_OBJ_TYPE_COMMIT)
717 			continue;
718 		err = queue_commit_id(&ids, id, COLOR_KEEP, repo);
719 		if (err)
720 			goto done;
721 	}		
722 	for (i = 0; i < ntail; i++) {
723 		struct got_object_id *id = tail[i];
724 		if (id == NULL)
725 			continue;
726 		err = got_object_get_type(&obj_type, repo, id);
727 		if (err)
728 			return err;
729 		if (obj_type != GOT_OBJ_TYPE_COMMIT)
730 			continue;
731 		err = queue_commit_id(&ids, id, COLOR_DROP, repo);
732 		if (err)
733 			goto done;
734 	}
735 
736 	while (!STAILQ_EMPTY(&ids)) {
737 		int qcolor;
738 		qid = STAILQ_FIRST(&ids);
739 		qcolor = *((int *)qid->data);
740 
741 		if (got_object_idset_contains(drop, qid->id))
742 			ncolor = COLOR_DROP;
743 		else if (got_object_idset_contains(keep, qid->id))
744 			ncolor = COLOR_KEEP;
745 		else
746 			ncolor = COLOR_BLANK;
747 
748 		if (ncolor == COLOR_DROP || (ncolor == COLOR_KEEP &&
749 		    qcolor == COLOR_KEEP)) {
750 			STAILQ_REMOVE_HEAD(&ids, entry);
751 			got_object_qid_free(qid);
752 			continue;
753 		}
754 
755 		if (ncolor == COLOR_KEEP && qcolor == COLOR_DROP) {
756 			err = drop_commit(keep, drop, qid->id, repo,
757 			    cancel_cb, cancel_arg);
758 			if (err)
759 				goto done;
760 		} else if (ncolor == COLOR_BLANK) {
761 			struct got_commit_object *commit;
762 			struct got_object_id *id;
763 			const struct got_object_id_queue *parents;
764 			struct got_object_qid *pid;
765 
766 			id = got_object_id_dup(qid->id);
767 			if (id == NULL) {
768 				err = got_error_from_errno("got_object_id_dup");
769 				goto done;
770 			}
771 			if (qcolor == COLOR_KEEP)
772 				err = got_object_idset_add(keep, id,
773 				    (void *)&obj_types[GOT_OBJ_TYPE_COMMIT]);
774 			else
775 				err = got_object_idset_add(drop, id,
776 				    (void *)&obj_types[GOT_OBJ_TYPE_COMMIT]);
777 			if (err) {
778 				free(id);
779 				goto done;
780 			}
781 
782 			err = got_object_open_as_commit(&commit, repo, id);
783 			if (err) {
784 				free(id);
785 				goto done;
786 			}
787 			parents = got_object_commit_get_parent_ids(commit);
788 			if (parents) {
789 				STAILQ_FOREACH(pid, parents, entry) {
790 					err = queue_commit_id(&ids, pid->id,
791 					    qcolor, repo);
792 					if (err) {
793 						free(id);
794 						goto done;
795 					}
796 				}
797 			}
798 			got_object_commit_close(commit);
799 			commit = NULL;
800 		} else {
801 			/* should not happen */
802 			err = got_error_fmt(GOT_ERR_NOT_IMPL,
803 			    "%s ncolor=%d qcolor=%d", __func__, ncolor, qcolor);
804 			goto done;
805 		}
806 
807 		STAILQ_REMOVE_HEAD(&ids, entry);
808 		got_object_qid_free(qid);
809 	}
810 
811 	nkeep = got_object_idset_num_elements(keep);
812 	if (nkeep > 0) {
813 		struct append_id_arg arg;
814 		arg.array = calloc(nkeep, sizeof(struct got_object_id *));
815 		if (arg.array == NULL) {
816 			err = got_error_from_errno("calloc");
817 			goto done;
818 		}
819 		arg.idx = 0;
820 		err = got_object_idset_for_each(keep, append_id, &arg);
821 		if (err) {
822 			free(arg.array);
823 			goto done;
824 		}
825 		*res = arg.array;
826 		*nres = nkeep;
827 	}
828 done:
829 	got_object_idset_free(keep);
830 	got_object_idset_free(drop);
831 	got_object_id_queue_free(&ids);
832 	return err;
833 }
834 
835 static const struct got_error *
836 read_meta(struct got_pack_meta ***meta, int *nmeta,
837     struct got_object_id **theirs, int ntheirs,
838     struct got_object_id **ours, int nours, struct got_repository *repo,
839     int loose_obj_only, got_pack_progress_cb progress_cb, void *progress_arg,
840     got_cancel_cb cancel_cb, void *cancel_arg)
841 {
842 	const struct got_error *err = NULL;
843 	struct got_object_id **ids = NULL;
844 	struct got_object_idset *idset;
845 	int i, nobj = 0, obj_type;
846 	struct got_pack_metavec v;
847 
848 	*meta = NULL;
849 	*nmeta = 0;
850 
851 	idset = got_object_idset_alloc();
852 	if (idset == NULL)
853 		return got_error_from_errno("got_object_idset_alloc");
854 
855 	v.nmeta = 0;
856 	v.metasz = 64;
857 	v.meta = calloc(v.metasz, sizeof(struct got_pack_meta *));
858 	if (v.meta == NULL) {
859 		err = got_error_from_errno("calloc");
860 		goto done;
861 	}
862 
863 	err = findtwixt(&ids, &nobj, ours, nours, theirs, ntheirs, repo,
864 	    cancel_cb, cancel_arg);
865 	if (err || nobj == 0)
866 		goto done;
867 
868 	for (i = 0; i < ntheirs; i++) {
869 		struct got_object_id *id = theirs[i];
870 		if (id == NULL)
871 			continue;
872 		err = got_object_get_type(&obj_type, repo, id);
873 		if (err)
874 			return err;
875 		if (obj_type != GOT_OBJ_TYPE_COMMIT)
876 			continue;
877 		err = load_commit(NULL, idset, id, repo,
878 		    loose_obj_only, cancel_cb, cancel_arg);
879 		if (err)
880 			goto done;
881 		if (progress_cb) {
882 			err = progress_cb(progress_arg, 0L, nours,
883 			    v.nmeta, 0, 0);
884 			if (err)
885 				goto done;
886 		}
887 	}
888 
889 	for (i = 0; i < ntheirs; i++) {
890 		struct got_object_id *id = theirs[i];
891 		int *cached_type;
892 		if (id == NULL)
893 			continue;
894 		cached_type = got_object_idset_get(idset, id);
895 		if (cached_type == NULL) {
896 			err = got_object_get_type(&obj_type, repo, id);
897 			if (err)
898 				goto done;
899 		} else
900 			obj_type = *cached_type;
901 		if (obj_type != GOT_OBJ_TYPE_TAG)
902 			continue;
903 		err = load_tag(NULL, idset, id, repo,
904 		    loose_obj_only, cancel_cb, cancel_arg);
905 		if (err)
906 			goto done;
907 		if (progress_cb) {
908 			err = progress_cb(progress_arg, 0L, nours,
909 			    v.nmeta, 0, 0);
910 			if (err)
911 				goto done;
912 		}
913 	}
914 
915 	for (i = 0; i < nobj; i++) {
916 		err = load_commit(&v, idset, ids[i], repo,
917 		    loose_obj_only, cancel_cb, cancel_arg);
918 		if (err)
919 			goto done;
920 		if (progress_cb) {
921 			err = progress_cb(progress_arg, 0L, nours,
922 			    v.nmeta, 0, 0);
923 			if (err)
924 				goto done;
925 		}
926 	}
927 
928 	for (i = 0; i < nours; i++) {
929 		struct got_object_id *id = ours[i];
930 		int *cached_type;
931 		if (id == NULL)
932 			continue;
933 		cached_type = got_object_idset_get(idset, id);
934 		if (cached_type == NULL) {
935 			err = got_object_get_type(&obj_type, repo, id);
936 			if (err)
937 				goto done;
938 		} else
939 			obj_type = *cached_type;
940 		if (obj_type != GOT_OBJ_TYPE_TAG)
941 			continue;
942 		err = load_tag(&v, idset, id, repo,
943 		    loose_obj_only, cancel_cb, cancel_arg);
944 		if (err)
945 			goto done;
946 		if (progress_cb) {
947 			err = progress_cb(progress_arg, 0L, nours,
948 			    v.nmeta, 0, 0);
949 			if (err)
950 				goto done;
951 		}
952 	}
953 
954 done:
955 	for (i = 0; i < nobj; i++) {
956 		free(ids[i]);
957 	}
958 	free(ids);
959 	got_object_idset_free(idset);
960 	if (err == NULL) {
961 		*meta = v.meta;
962 		*nmeta = v.nmeta;
963 	} else
964 		free(v.meta);
965 
966 	return err;
967 }
968 
969 const struct got_error *
970 hwrite(FILE *f, void *buf, int len, SHA1_CTX *ctx)
971 {
972 	size_t n;
973 
974 	SHA1Update(ctx, buf, len);
975 	n = fwrite(buf, 1, len, f);
976 	if (n != len)
977 		return got_ferror(f, GOT_ERR_IO);
978 	return NULL;
979 }
980 
981 static void
982 putbe32(char *b, uint32_t n)
983 {
984 	b[0] = n >> 24;
985 	b[1] = n >> 16;
986 	b[2] = n >> 8;
987 	b[3] = n >> 0;
988 }
989 
990 static int
991 write_order_cmp(const void *pa, const void *pb)
992 {
993 	struct got_pack_meta *a, *b, *ahd, *bhd;
994 
995 	a = *(struct got_pack_meta **)pa;
996 	b = *(struct got_pack_meta **)pb;
997 	ahd = (a->head == NULL) ? a : a->head;
998 	bhd = (b->head == NULL) ? b : b->head;
999 	if (ahd->mtime != bhd->mtime)
1000 		return bhd->mtime - ahd->mtime;
1001 	if (ahd != bhd)
1002 		return (uintptr_t)bhd - (uintptr_t)ahd;
1003 	if (a->nchain != b->nchain)
1004 		return a->nchain - b->nchain;
1005 	return a->mtime - b->mtime;
1006 }
1007 
1008 static const struct got_error *
1009 packhdr(int *hdrlen, char *hdr, size_t bufsize, int obj_type, size_t len)
1010 {
1011 	size_t i;
1012 
1013 	*hdrlen = 0;
1014 
1015 	hdr[0] = obj_type << 4;
1016 	hdr[0] |= len & 0xf;
1017 	len >>= 4;
1018 	for (i = 1; len != 0; i++){
1019 		if (i >= bufsize)
1020 			return got_error(GOT_ERR_NO_SPACE);
1021 		hdr[i - 1] |= GOT_DELTA_SIZE_MORE;
1022 		hdr[i] = len & GOT_DELTA_SIZE_VAL_MASK;
1023 		len >>= GOT_DELTA_SIZE_SHIFT;
1024 	}
1025 
1026 	*hdrlen = i;
1027 	return NULL;
1028 }
1029 
1030 static const struct got_error *
1031 encodedelta(struct got_pack_meta *m, struct got_raw_object *o,
1032     off_t base_size, FILE *f)
1033 {
1034 	unsigned char buf[16], *bp;
1035 	int i, j;
1036 	off_t n;
1037 	size_t w;
1038 	struct got_delta_instruction *d;
1039 
1040 	/* base object size */
1041 	buf[0] = base_size & GOT_DELTA_SIZE_VAL_MASK;
1042 	n = base_size >> GOT_DELTA_SIZE_SHIFT;
1043 	for (i = 1; n > 0; i++) {
1044 		buf[i - 1] |= GOT_DELTA_SIZE_MORE;
1045 		buf[i] = n & GOT_DELTA_SIZE_VAL_MASK;
1046 		n >>= GOT_DELTA_SIZE_SHIFT;
1047 	}
1048 	w = fwrite(buf, 1, i, f);
1049 	if (w != i)
1050 		return got_ferror(f, GOT_ERR_IO);
1051 
1052 	/* target object size */
1053 	buf[0] = o->size & GOT_DELTA_SIZE_VAL_MASK;
1054 	n = o->size >> GOT_DELTA_SIZE_SHIFT;
1055 	for (i = 1; n > 0; i++) {
1056 		buf[i - 1] |= GOT_DELTA_SIZE_MORE;
1057 		buf[i] = n & GOT_DELTA_SIZE_VAL_MASK;
1058 		n >>= GOT_DELTA_SIZE_SHIFT;
1059 	}
1060 	w = fwrite(buf, 1, i, f);
1061 	if (w != i)
1062 		return got_ferror(f, GOT_ERR_IO);
1063 
1064 	for (j = 0; j < m->ndeltas; j++) {
1065 		d = &m->deltas[j];
1066 		if (d->copy) {
1067 			n = d->offset;
1068 			bp = &buf[1];
1069 			buf[0] = GOT_DELTA_BASE_COPY;
1070 			for (i = 0; i < 4; i++) {
1071 				/* DELTA_COPY_OFF1 ... DELTA_COPY_OFF4 */
1072 				buf[0] |= 1 << i;
1073 				*bp++ = n & 0xff;
1074 				n >>= 8;
1075 				if (n == 0)
1076 					break;
1077 			}
1078 
1079 			n = d->len;
1080 			if (n != GOT_DELTA_COPY_DEFAULT_LEN) {
1081 				/* DELTA_COPY_LEN1 ... DELTA_COPY_LEN3 */
1082 				for (i = 0; i < 3 && n > 0; i++) {
1083 					buf[0] |= 1 << (i + 4);
1084 					*bp++ = n & 0xff;
1085 					n >>= 8;
1086 				}
1087 			}
1088 			w = fwrite(buf, 1, bp - buf, f);
1089 			if (w != bp - buf)
1090 				return got_ferror(f, GOT_ERR_IO);
1091 		} else {
1092 			char content[128];
1093 			size_t r;
1094 			if (fseeko(o->f, o->hdrlen + d->offset, SEEK_SET) == -1)
1095 				return got_error_from_errno("fseeko");
1096 			n = 0;
1097 			while (n != d->len) {
1098 				buf[0] = (d->len - n < 127) ? d->len - n : 127;
1099 				w = fwrite(buf, 1, 1, f);
1100 				if (w != 1)
1101 					return got_ferror(f, GOT_ERR_IO);
1102 				r = fread(content, 1, buf[0], o->f);
1103 				if (r != buf[0])
1104 					return got_ferror(o->f, GOT_ERR_IO);
1105 				w = fwrite(content, 1, buf[0], f);
1106 				if (w != buf[0])
1107 					return got_ferror(f, GOT_ERR_IO);
1108 				n += buf[0];
1109 			}
1110 		}
1111 	}
1112 
1113 	return NULL;
1114 }
1115 
1116 static int
1117 packoff(char *hdr, off_t off)
1118 {
1119 	int i, j;
1120 	char rbuf[8];
1121 
1122 	rbuf[0] = off & GOT_DELTA_SIZE_VAL_MASK;
1123 	for (i = 1; (off >>= GOT_DELTA_SIZE_SHIFT) != 0; i++) {
1124 		rbuf[i] = (--off & GOT_DELTA_SIZE_VAL_MASK) |
1125 		    GOT_DELTA_SIZE_MORE;
1126 	}
1127 
1128 	j = 0;
1129 	while (i > 0)
1130 		hdr[j++] = rbuf[--i];
1131 	return j;
1132 }
1133 
1134 static const struct got_error *
1135 genpack(uint8_t *pack_sha1, FILE *packfile,
1136     struct got_pack_meta **meta, int nmeta, int nours,
1137     int use_offset_deltas, struct got_repository *repo,
1138     got_pack_progress_cb progress_cb, void *progress_arg,
1139     got_cancel_cb cancel_cb, void *cancel_arg)
1140 {
1141 	const struct got_error *err = NULL;
1142 	int i, nh;
1143 	off_t nd;
1144 	SHA1_CTX ctx;
1145 	struct got_pack_meta *m;
1146 	struct got_raw_object *raw = NULL;
1147 	FILE *delta_file = NULL;
1148 	char buf[32];
1149 	size_t outlen, n;
1150 	struct got_deflate_checksum csum;
1151 	off_t packfile_size = 0;
1152 	int outfd = -1;
1153 
1154 	SHA1Init(&ctx);
1155 	csum.output_sha1 = &ctx;
1156 	csum.output_crc = NULL;
1157 
1158 	err = hwrite(packfile, "PACK", 4, &ctx);
1159 	if (err)
1160 		return err;
1161 	putbe32(buf, GOT_PACKFILE_VERSION);
1162 	err = hwrite(packfile, buf, 4, &ctx);
1163 	if (err)
1164 		goto done;
1165 	putbe32(buf, nmeta);
1166 	err = hwrite(packfile, buf, 4, &ctx);
1167 	if (err)
1168 		goto done;
1169 	qsort(meta, nmeta, sizeof(struct got_pack_meta *), write_order_cmp);
1170 	for (i = 0; i < nmeta; i++) {
1171 		if (progress_cb) {
1172 			err = progress_cb(progress_arg, packfile_size, nours,
1173 			    nmeta, nmeta, i);
1174 			if (err)
1175 				goto done;
1176 		}
1177 		m = meta[i];
1178 		m->off = ftello(packfile);
1179 		if (outfd == -1) {
1180 			outfd = got_opentempfd();
1181 			if (outfd == -1) {
1182 				err = got_error_from_errno("got_opentempfd");
1183 				goto done;
1184 			}
1185 		}
1186 		err = got_object_raw_open(&raw, outfd, repo, &m->id, 8192);
1187 		if (err)
1188 			goto done;
1189 		if (raw->data == NULL)
1190 			outfd = -1; /* outfd is now raw->f */
1191 		if (m->deltas == NULL) {
1192 			err = packhdr(&nh, buf, sizeof(buf),
1193 			    m->obj_type, raw->size);
1194 			if (err)
1195 				goto done;
1196 			err = hwrite(packfile, buf, nh, &ctx);
1197 			if (err)
1198 				goto done;
1199 			packfile_size += nh;
1200 			if (fseeko(raw->f, raw->hdrlen, SEEK_SET) == -1) {
1201 				err = got_error_from_errno("fseeko");
1202 				goto done;
1203 			}
1204 			err = got_deflate_to_file(&outlen, raw->f, packfile,
1205 			    &csum);
1206 			if (err)
1207 				goto done;
1208 			packfile_size += outlen;
1209 		} else {
1210 			if (delta_file == NULL) {
1211 				delta_file = got_opentemp();
1212 				if (delta_file == NULL) {
1213 					err = got_error_from_errno(
1214 					    "got_opentemp");
1215 					goto done;
1216 				}
1217 			}
1218 			if (ftruncate(fileno(delta_file), 0L) == -1) {
1219 				err = got_error_from_errno("ftruncate");
1220 				goto done;
1221 			}
1222 			if (fseeko(delta_file, 0L, SEEK_SET) == -1) {
1223 				err = got_error_from_errno("fseeko");
1224 				goto done;
1225 			}
1226 			err = encodedelta(m, raw, m->prev->size, delta_file);
1227 			if (err)
1228 				goto done;
1229 			nd = ftello(delta_file);
1230 			if (fseeko(delta_file, 0L, SEEK_SET) == -1) {
1231 				err = got_error_from_errno("fseeko");
1232 				goto done;
1233 			}
1234 			if (use_offset_deltas && m->prev->off != 0) {
1235 				err = packhdr(&nh, buf, sizeof(buf),
1236 				    GOT_OBJ_TYPE_OFFSET_DELTA, nd);
1237 				if (err)
1238 					goto done;
1239 				nh += packoff(buf + nh,
1240 				    m->off - m->prev->off);
1241 				err = hwrite(packfile, buf, nh, &ctx);
1242 				if (err)
1243 					goto done;
1244 				packfile_size += nh;
1245 			} else {
1246 				err = packhdr(&nh, buf, sizeof(buf),
1247 				    GOT_OBJ_TYPE_REF_DELTA, nd);
1248 				err = hwrite(packfile, buf, nh, &ctx);
1249 				if (err)
1250 					goto done;
1251 				packfile_size += nh;
1252 				err = hwrite(packfile, m->prev->id.sha1,
1253 				    sizeof(m->prev->id.sha1), &ctx);
1254 				packfile_size += sizeof(m->prev->id.sha1);
1255 				if (err)
1256 					goto done;
1257 			}
1258 			err = got_deflate_to_file(&outlen, delta_file,
1259 			    packfile, &csum);
1260 			if (err)
1261 				goto done;
1262 			packfile_size += outlen;
1263 		}
1264 		got_object_raw_close(raw);
1265 		raw = NULL;
1266 	}
1267 	SHA1Final(pack_sha1, &ctx);
1268 	n = fwrite(pack_sha1, 1, SHA1_DIGEST_LENGTH, packfile);
1269 	if (n != SHA1_DIGEST_LENGTH)
1270 		err = got_ferror(packfile, GOT_ERR_IO);
1271 	packfile_size += SHA1_DIGEST_LENGTH;
1272 	packfile_size += sizeof(struct got_packfile_hdr);
1273 	err = progress_cb(progress_arg, packfile_size, nours,
1274 	    nmeta, nmeta, nmeta);
1275 	if (err)
1276 		goto done;
1277 done:
1278 	if (delta_file && fclose(delta_file) == EOF && err == NULL)
1279 		err = got_error_from_errno("fclose");
1280 	if (raw)
1281 		got_object_raw_close(raw);
1282 	if (outfd != -1 && close(outfd) == -1 && err == NULL)
1283 		err = got_error_from_errno("close");
1284 	return err;
1285 }
1286 
1287 const struct got_error *
1288 got_pack_create(uint8_t *packsha1, FILE *packfile,
1289     struct got_object_id **theirs, int ntheirs,
1290     struct got_object_id **ours, int nours,
1291     struct got_repository *repo, int loose_obj_only, int allow_empty,
1292     got_pack_progress_cb progress_cb, void *progress_arg,
1293     got_cancel_cb cancel_cb, void *cancel_arg)
1294 {
1295 	const struct got_error *err;
1296 	struct got_pack_meta **meta;
1297 	int nmeta;
1298 
1299 	err = read_meta(&meta, &nmeta, theirs, ntheirs, ours, nours, repo,
1300 	    loose_obj_only, progress_cb, progress_arg, cancel_cb, cancel_arg);
1301 	if (err)
1302 		return err;
1303 
1304 	if (nmeta == 0 && !allow_empty) {
1305 		err = got_error(GOT_ERR_CANNOT_PACK);
1306 		goto done;
1307 	}
1308 	if (nmeta > 0) {
1309 		err = pick_deltas(meta, nmeta, nours, repo,
1310 		    progress_cb, progress_arg, cancel_cb, cancel_arg);
1311 		if (err)
1312 			goto done;
1313 	}
1314 
1315 	err = genpack(packsha1, packfile, meta, nmeta, nours, 1, repo,
1316 	    progress_cb, progress_arg, cancel_cb, cancel_arg);
1317 	if (err)
1318 		goto done;
1319 done:
1320 	free_nmeta(meta, nmeta);
1321 	return err;
1322 }