Gotweb

Blob

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