Gotweb

Blob

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