1 /*
2  * Copyright (c) 2019 Ori Bernstein <ori@openbsd.org>
3  * Copyright (c) 2020 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/stat.h>
19 #include <sys/time.h>
20 #include <sys/types.h>
21 #include <sys/uio.h>
22 #include <sys/mman.h>
23 
24 #include <stdint.h>
25 #include <errno.h>
26 #include <limits.h>
27 #include <signal.h>
28 #include <stdio.h>
29 #include <stdlib.h>
30 #include <string.h>
31 #include <ctype.h>
32 #include <fcntl.h>
33 #include <unistd.h>
34 #include <zlib.h>
35 #include <err.h>
36 #include <assert.h>
37 #include <dirent.h>
38 
39 #include "got_error.h"
40 #include "got_object.h"
41 
42 #include "got_compat.h"
43 
44 #include "got_lib_sha1.h"
45 #include "got_lib_delta.h"
46 #include "got_lib_inflate.h"
47 #include "got_lib_object.h"
48 #include "got_lib_object_parse.h"
49 #include "got_lib_object_idset.h"
50 #include "got_lib_privsep.h"
51 #include "got_lib_pack.h"
52 #include "got_lib_delta_cache.h"
53 
54 #ifndef nitems
55 #define nitems(_a)	(sizeof((_a)) / sizeof((_a)[0]))
56 #endif
57 
58 struct got_indexed_object {
59 	struct got_object_id id;
60 
61 	/*
62 	 * Has this object been fully resolved?
63 	 * If so, we know its ID, otherwise we don't and 'id' is invalid.
64 	 */
65 	int valid;
66 
67 	/* Offset of type+size field for this object in pack file. */
68 	off_t off;
69 
70 	/* Type+size values parsed from pack file. */
71 	uint8_t type;
72 	uint64_t size;
73 
74 	/* Length of on-disk type+size data. */
75 	size_t tslen; 
76 
77 	/* Length of object data following type+size. */
78 	size_t len; 
79 
80 	uint32_t crc;
81 
82 	union {
83 		struct {
84 			/* For ref deltas. */
85 			struct got_object_id ref_id;
86 		} ref;
87 		struct {
88 			/* For offset deltas. */
89 			off_t base_offset;
90 			size_t base_offsetlen;
91 		} ofs;
92 	} delta;
93 };
94 
95 static void
96 putbe32(char *b, uint32_t n)
97 {
98 	b[0] = n >> 24;
99 	b[1] = n >> 16;
100 	b[2] = n >> 8;
101 	b[3] = n >> 0;
102 }
103 
104 static const struct got_error *
105 get_obj_type_label(const char **label, int obj_type)
106 {
107 	const struct got_error *err = NULL;
108 
109 	switch (obj_type) {
110 	case GOT_OBJ_TYPE_BLOB:
111 		*label = GOT_OBJ_LABEL_BLOB;
112 		break;
113 	case GOT_OBJ_TYPE_TREE:
114 		*label = GOT_OBJ_LABEL_TREE;
115 		break;
116 	case GOT_OBJ_TYPE_COMMIT:
117 		*label = GOT_OBJ_LABEL_COMMIT;
118 		break;
119 	case GOT_OBJ_TYPE_TAG:
120 		*label = GOT_OBJ_LABEL_TAG;
121 		break;
122 	default:
123 		*label = NULL;
124 		err = got_error(GOT_ERR_OBJ_TYPE);
125 		break;
126 	}
127 
128 	return err;
129 }
130 
131 static const struct got_error *
132 read_checksum(uint32_t *crc, SHA1_CTX *sha1_ctx, int fd, size_t len)
133 {
134 	uint8_t buf[8192];
135 	size_t n;
136 	ssize_t r;
137 
138 	for (n = len; n > 0; n -= r){
139 		r = read(fd, buf, n > sizeof(buf) ? sizeof(buf) : n);
140 		if (r == -1)
141 			return got_error_from_errno("read");
142 		if (r == 0)
143 			break;
144 		if (crc)
145 			*crc = crc32(*crc, buf, r);
146 		if (sha1_ctx)
147 			SHA1Update(sha1_ctx, buf, r);
148 	}
149 
150 	return NULL;
151 }
152 
153 static const struct got_error *
154 read_file_sha1(SHA1_CTX *ctx, FILE *f, size_t len)
155 {
156 	uint8_t buf[8192];
157 	size_t n, r;
158 
159 	for (n = len; n > 0; n -= r) {
160 		r = fread(buf, 1, n > sizeof(buf) ? sizeof(buf) : n, f);
161 		if (r == 0) {
162 			if (feof(f))
163 				return NULL;
164 			return got_ferror(f, GOT_ERR_IO);
165 		}
166 		SHA1Update(ctx, buf, r);
167 	}
168 
169 	return NULL;
170 }
171 
172 static const struct got_error *
173 read_packed_object(struct got_pack *pack, struct got_indexed_object *obj,
174     FILE *tmpfile, SHA1_CTX *pack_sha1_ctx)
175 {
176 	const struct got_error *err = NULL;
177 	SHA1_CTX ctx;
178 	uint8_t *data = NULL;
179 	size_t datalen = 0;
180 	ssize_t n;
181 	char *header;
182 	size_t headerlen;
183 	const char *obj_label;
184 	size_t mapoff = obj->off;
185 	struct got_inflate_checksum csum;
186 
187 	memset(&csum, 0, sizeof(csum));
188 	csum.input_sha1 = pack_sha1_ctx;
189 	csum.input_crc = &obj->crc;
190 
191 	err = got_pack_parse_object_type_and_size(&obj->type, &obj->size,
192 	    &obj->tslen, pack, obj->off);
193 	if (err)
194 		return err;
195 
196 	if (pack->map) {
197 		obj->crc = crc32(obj->crc, pack->map + mapoff, obj->tslen);
198 		SHA1Update(pack_sha1_ctx, pack->map + mapoff, obj->tslen);
199 		mapoff += obj->tslen;
200 	} else {
201 		/* XXX Seek back and get the CRC of on-disk type+size bytes. */
202 		if (lseek(pack->fd, obj->off, SEEK_SET) == -1)
203 			return got_error_from_errno("lseek");
204 		err = read_checksum(&obj->crc, pack_sha1_ctx,
205 		    pack->fd, obj->tslen);
206 		if (err)
207 			return err;
208 	}
209 
210 	switch (obj->type) {
211 	case GOT_OBJ_TYPE_BLOB:
212 	case GOT_OBJ_TYPE_COMMIT:
213 	case GOT_OBJ_TYPE_TREE:
214 	case GOT_OBJ_TYPE_TAG:
215 		if (obj->size > GOT_DELTA_RESULT_SIZE_CACHED_MAX) {
216 			if (fseek(tmpfile, 0L, SEEK_SET) == -1) {
217 				err = got_error_from_errno("fseek");
218 				break;
219 			}
220 			if (pack->map) {
221 				err = got_inflate_to_file_mmap(&datalen,
222 				    &obj->len, &csum, pack->map, mapoff,
223 				    pack->filesize - mapoff, tmpfile);
224 			} else {
225 				err = got_inflate_to_file_fd(&datalen,
226 				    &obj->len, &csum, pack->fd, tmpfile);
227 			}
228 		} else {
229 			if (pack->map) {
230 				err = got_inflate_to_mem_mmap(&data, &datalen,
231 				    &obj->len, &csum, pack->map, mapoff,
232 				    pack->filesize - mapoff);
233 			} else {
234 				err = got_inflate_to_mem_fd(&data, &datalen,
235 				    &obj->len, &csum, obj->size, pack->fd);
236 			}
237 		}
238 		if (err)
239 			break;
240 		SHA1Init(&ctx);
241 		err = get_obj_type_label(&obj_label, obj->type);
242 		if (err) {
243 			free(data);
244 			break;
245 		}
246 		if (asprintf(&header, "%s %lld", obj_label,
247 		    (long long)obj->size) == -1) {
248 			err = got_error_from_errno("asprintf");
249 			free(data);
250 			break;
251 		}
252 		headerlen = strlen(header) + 1;
253 		SHA1Update(&ctx, header, headerlen);
254 		if (obj->size > GOT_DELTA_RESULT_SIZE_CACHED_MAX) {
255 			err = read_file_sha1(&ctx, tmpfile, datalen);
256 			if (err)
257 				break;
258 		} else
259 			SHA1Update(&ctx, data, datalen);
260 		SHA1Final(obj->id.sha1, &ctx);
261 		free(header);
262 		free(data);
263 		break;
264 	case GOT_OBJ_TYPE_REF_DELTA:
265 		memset(obj->id.sha1, 0xff, SHA1_DIGEST_LENGTH);
266 		if (pack->map) {
267 			if (mapoff + SHA1_DIGEST_LENGTH >= pack->filesize) {
268 				err = got_error(GOT_ERR_BAD_PACKFILE);
269 				break;
270 			}
271 			memcpy(obj->delta.ref.ref_id.sha1, pack->map + mapoff,
272 			    SHA1_DIGEST_LENGTH);
273 			obj->crc = crc32(obj->crc, pack->map + mapoff,
274 			    SHA1_DIGEST_LENGTH);
275 			SHA1Update(pack_sha1_ctx, pack->map + mapoff,
276 			    SHA1_DIGEST_LENGTH);
277 			mapoff += SHA1_DIGEST_LENGTH;
278 			err = got_inflate_to_mem_mmap(NULL, &datalen,
279 			    &obj->len, &csum, pack->map, mapoff,
280 			    pack->filesize - mapoff);
281 			if (err)
282 				break;
283 		} else {
284 			n = read(pack->fd, obj->delta.ref.ref_id.sha1,
285 			    SHA1_DIGEST_LENGTH);
286 			if (n == -1) {
287 				err = got_error_from_errno("read");
288 				break;
289 			}
290 			if (n < sizeof(obj->id)) {
291 				err = got_error(GOT_ERR_BAD_PACKFILE);
292 				break;
293 			}
294 			obj->crc = crc32(obj->crc, obj->delta.ref.ref_id.sha1,
295 			    SHA1_DIGEST_LENGTH);
296 			SHA1Update(pack_sha1_ctx, obj->delta.ref.ref_id.sha1,
297 			    SHA1_DIGEST_LENGTH);
298 			err = got_inflate_to_mem_fd(NULL, &datalen, &obj->len,
299 			    &csum, obj->size, pack->fd);
300 			if (err)
301 				break;
302 		}
303 		obj->len += SHA1_DIGEST_LENGTH;
304 		break;
305 	case GOT_OBJ_TYPE_OFFSET_DELTA:
306 		memset(obj->id.sha1, 0xff, SHA1_DIGEST_LENGTH);
307 		err = got_pack_parse_offset_delta(&obj->delta.ofs.base_offset,
308 		    &obj->delta.ofs.base_offsetlen, pack, obj->off,
309 		    obj->tslen);
310 		if (err)
311 			break;
312 
313 		if (pack->map) {
314 			obj->crc = crc32(obj->crc, pack->map + mapoff,
315 			    obj->delta.ofs.base_offsetlen);
316 			SHA1Update(pack_sha1_ctx, pack->map + mapoff,
317 			    obj->delta.ofs.base_offsetlen);
318 			mapoff += obj->delta.ofs.base_offsetlen;
319 			err = got_inflate_to_mem_mmap(NULL, &datalen,
320 			    &obj->len, &csum, pack->map, mapoff,
321 			    pack->filesize - mapoff);
322 			if (err)
323 				break;
324 		} else {
325 			/*
326 			 * XXX Seek back and get CRC and SHA1 of on-disk
327 			 * offset bytes.
328 			 */
329 			if (lseek(pack->fd, obj->off + obj->tslen, SEEK_SET)
330 			    == -1) {
331 				err = got_error_from_errno("lseek");
332 				break;
333 			}
334 			err = read_checksum(&obj->crc, pack_sha1_ctx,
335 			    pack->fd, obj->delta.ofs.base_offsetlen);
336 			if (err)
337 				break;
338 
339 			err = got_inflate_to_mem_fd(NULL, &datalen, &obj->len,
340 			    &csum, obj->size, pack->fd);
341 			if (err)
342 				break;
343 		}
344 		obj->len += obj->delta.ofs.base_offsetlen;
345 		break;
346 	default:
347 		err = got_error(GOT_ERR_OBJ_TYPE);
348 		break;
349 	}
350 
351 	return err;
352 }
353 
354 static const struct got_error *
355 hwrite(int fd, void *buf, int len, SHA1_CTX *ctx)
356 {
357 	ssize_t w;
358 
359 	SHA1Update(ctx, buf, len);
360 
361 	w = write(fd, buf, len);
362 	if (w == -1)
363 		return got_error_from_errno("write");
364 	if (w != len)
365 		return got_error(GOT_ERR_IO);
366 
367 	return NULL;
368 }
369 
370 static const struct got_error *
371 resolve_deltified_object(struct got_pack *pack, struct got_packidx *packidx,
372     struct got_indexed_object *obj, FILE *tmpfile, FILE *delta_base_file,
373     FILE *delta_accum_file)
374 {
375 	const struct got_error *err = NULL;
376 	struct got_delta_chain deltas;
377 	struct got_delta *delta;
378 	uint8_t *buf = NULL;
379 	size_t len = 0;
380 	SHA1_CTX ctx;
381 	char *header = NULL;
382 	size_t headerlen;
383 	uint64_t max_size;
384 	int base_obj_type;
385 	const char *obj_label;
386 
387 	deltas.nentries = 0;
388 	STAILQ_INIT(&deltas.entries);
389 
390 	err = got_pack_resolve_delta_chain(&deltas, packidx, pack,
391 	    obj->off, obj->tslen, obj->type, obj->size,
392 	    GOT_DELTA_CHAIN_RECURSION_MAX);
393 	if (err)
394 		goto done;
395 
396 	err = got_pack_get_delta_chain_max_size(&max_size, &deltas, pack);
397 	if (err)
398 		goto done;
399 	if (max_size > GOT_DELTA_RESULT_SIZE_CACHED_MAX) {
400 		rewind(tmpfile);
401 		rewind(delta_base_file);
402 		rewind(delta_accum_file);
403 		err = got_pack_dump_delta_chain_to_file(&len, &deltas,
404 		    pack, tmpfile, delta_base_file, delta_accum_file);
405 		if (err)
406 			goto done;
407 	} else {
408 		err = got_pack_dump_delta_chain_to_mem(&buf, &len,
409 		    &deltas, pack);
410 	}
411 	if (err)
412 		goto done;
413 
414 	err = got_delta_chain_get_base_type(&base_obj_type, &deltas);
415 	if (err)
416 		goto done;
417 	err = get_obj_type_label(&obj_label, base_obj_type);
418 	if (err)
419 		goto done;
420 	if (asprintf(&header, "%s %zd", obj_label, len) == -1) {
421 		err = got_error_from_errno("asprintf");
422 		goto done;
423 	}
424 	headerlen = strlen(header) + 1;
425 	SHA1Init(&ctx);
426 	SHA1Update(&ctx, header, headerlen);
427 	if (max_size > GOT_DELTA_RESULT_SIZE_CACHED_MAX) {
428 		err = read_file_sha1(&ctx, tmpfile, len);
429 		if (err)
430 			goto done;
431 	} else
432 		SHA1Update(&ctx, buf, len);
433 	SHA1Final(obj->id.sha1, &ctx);
434 done:
435 	free(buf);
436 	free(header);
437 	while (!STAILQ_EMPTY(&deltas.entries)) {
438 		delta = STAILQ_FIRST(&deltas.entries);
439 		STAILQ_REMOVE_HEAD(&deltas.entries, entry);
440 		free(delta);
441 	}
442 	return err;
443 }
444 
445 /* Determine the slot in the pack index a given object ID should use. */
446 static int
447 find_object_idx(struct got_packidx *packidx, uint8_t *sha1)
448 {
449 	u_int8_t id0 = sha1[0];
450 	uint32_t nindexed = be32toh(packidx->hdr.fanout_table[0xff]);
451 	int left = 0, right = nindexed - 1;
452 	int cmp = 0, i = 0;
453 
454 	if (id0 > 0)
455 		left = be32toh(packidx->hdr.fanout_table[id0 - 1]);
456 
457 	while (left <= right) {
458 		struct got_packidx_object_id *oid;
459 
460 		i = ((left + right) / 2);
461 		oid = &packidx->hdr.sorted_ids[i];
462 
463 		cmp = memcmp(sha1, oid->sha1, SHA1_DIGEST_LENGTH);
464 		if (cmp == 0)
465 			return -1; /* object already indexed */
466 		else if (cmp > 0)
467 			left = i + 1;
468 		else if (cmp < 0)
469 			right = i - 1;
470 	}
471 
472 	return left;
473 }
474 
475 #if 0
476 static void
477 print_packidx(struct got_packidx *packidx)
478 {
479 	uint32_t nindexed = be32toh(packidx->hdr.fanout_table[0xff]);
480 	int i;
481 
482 	fprintf(stderr, "object IDs:\n");
483 	for (i = 0; i < nindexed; i++) {
484 		char hex[SHA1_DIGEST_STRING_LENGTH];
485 		got_sha1_digest_to_str(packidx->hdr.sorted_ids[i].sha1,
486 		    hex, sizeof(hex));
487 		fprintf(stderr, "%s\n", hex);
488 	}
489 	fprintf(stderr, "\n");
490 
491 	fprintf(stderr, "object offsets:\n");
492 	for (i = 0; i < nindexed; i++) {
493 		uint32_t offset = be32toh(packidx->hdr.offsets[i]);
494 		if (offset & GOT_PACKIDX_OFFSET_VAL_IS_LARGE_IDX) {
495 			int j = offset & GOT_PACKIDX_OFFSET_VAL_MASK;
496 			fprintf(stderr, "%u -> %llu\n", offset, 
497 			    be64toh(packidx->hdr.large_offsets[j]));
498 		} else
499 			fprintf(stderr, "%u\n", offset);
500 	}
501 	fprintf(stderr, "\n");
502 
503 	fprintf(stderr, "fanout table:");
504 	for (i = 0; i <= 0xff; i++)
505 		fprintf(stderr, " %u", be32toh(packidx->hdr.fanout_table[i]));
506 	fprintf(stderr, "\n");
507 }
508 #endif
509 
510 static void
511 add_indexed_object(struct got_packidx *packidx, uint32_t idx,
512     struct got_indexed_object *obj)
513 {
514 	int i;
515 
516 	memcpy(packidx->hdr.sorted_ids[idx].sha1, obj->id.sha1,
517 	    SHA1_DIGEST_LENGTH);
518 	packidx->hdr.crc32[idx] = htobe32(obj->crc);
519 	if (obj->off < GOT_PACKIDX_OFFSET_VAL_IS_LARGE_IDX)
520 		packidx->hdr.offsets[idx] = htobe32(obj->off);
521 	else {
522 		packidx->hdr.offsets[idx] = htobe32(packidx->nlargeobj |
523 		    GOT_PACKIDX_OFFSET_VAL_IS_LARGE_IDX);
524 		packidx->hdr.large_offsets[packidx->nlargeobj] =
525 		    htobe64(obj->off);
526 		packidx->nlargeobj++;
527 	}
528 
529 	for (i = obj->id.sha1[0]; i <= 0xff; i++) {
530 		uint32_t n = be32toh(packidx->hdr.fanout_table[i]);
531 		packidx->hdr.fanout_table[i] = htobe32(n + 1);
532 	}
533 }
534 
535 static int
536 indexed_obj_cmp(const void *pa, const void *pb)
537 {
538 	struct got_indexed_object *a, *b;
539 
540 	a = (struct got_indexed_object *)pa;
541 	b = (struct got_indexed_object *)pb;
542 	return got_object_id_cmp(&a->id, &b->id);
543 }
544 
545 static void
546 make_packidx(struct got_packidx *packidx, int nobj,
547     struct got_indexed_object *objects)
548 {
549 	struct got_indexed_object *obj;
550 	int i;
551 	uint32_t idx = 0;
552 
553 	qsort(objects, nobj, sizeof(struct got_indexed_object),
554 	    indexed_obj_cmp);
555 
556 	memset(packidx->hdr.fanout_table, 0,
557 	    GOT_PACKIDX_V2_FANOUT_TABLE_ITEMS * sizeof(uint32_t));
558 	packidx->nlargeobj = 0;
559 
560 	for (i = 0; i < nobj; i++) {
561 		obj = &objects[i];
562 		if (obj->valid)
563 			add_indexed_object(packidx, idx++, obj);
564 	}
565 }
566 
567 static void
568 update_packidx(struct got_packidx *packidx, int nobj,
569     struct got_indexed_object *obj)
570 {
571 	int idx;
572 	uint32_t nindexed = be32toh(packidx->hdr.fanout_table[0xff]);
573 
574 	idx = find_object_idx(packidx, obj->id.sha1);
575 	if (idx == -1) {
576 		char hex[SHA1_DIGEST_STRING_LENGTH];
577 		got_sha1_digest_to_str(obj->id.sha1, hex, sizeof(hex));
578 		return; /* object already indexed */
579 	}
580 
581 	memmove(&packidx->hdr.sorted_ids[idx + 1],
582 	    &packidx->hdr.sorted_ids[idx],
583 	    sizeof(struct got_packidx_object_id) * (nindexed - idx));
584 	memmove(&packidx->hdr.offsets[idx + 1], &packidx->hdr.offsets[idx],
585 	    sizeof(uint32_t) * (nindexed - idx));
586 
587 	add_indexed_object(packidx, idx, obj);
588 }
589 
590 static const struct got_error *
591 send_index_pack_progress(struct imsgbuf *ibuf, int nobj_total,
592     int nobj_indexed, int nobj_loose, int nobj_resolved)
593 {
594 	struct got_imsg_index_pack_progress iprogress;
595 
596 	iprogress.nobj_total = nobj_total;
597 	iprogress.nobj_indexed = nobj_indexed;
598 	iprogress.nobj_loose = nobj_loose;
599 	iprogress.nobj_resolved = nobj_resolved;
600 
601 	if (imsg_compose(ibuf, GOT_IMSG_IDXPACK_PROGRESS, 0, 0, -1,
602 	    &iprogress, sizeof(iprogress)) == -1)
603 		return got_error_from_errno("imsg_compose IDXPACK_PROGRESS");
604 
605 	return got_privsep_flush_imsg(ibuf);
606 }
607 
608 static const struct got_error *
609 send_index_pack_done(struct imsgbuf *ibuf)
610 {
611 	if (imsg_compose(ibuf, GOT_IMSG_IDXPACK_DONE, 0, 0, -1, NULL, 0) == -1)
612 		return got_error_from_errno("imsg_compose FETCH");
613 	return got_privsep_flush_imsg(ibuf);
614 }
615 
616 
617 static const struct got_error *
618 index_pack(struct got_pack *pack, int idxfd, FILE *tmpfile,
619     FILE *delta_base_file, FILE *delta_accum_file, uint8_t *pack_sha1_expected,
620     struct imsgbuf *ibuf)
621 {
622 	const struct got_error *err;
623 	struct got_packfile_hdr hdr;
624 	struct got_packidx packidx;
625 	char buf[8];
626 	char pack_sha1[SHA1_DIGEST_LENGTH];
627 	int nobj, nvalid, nloose, nresolved = 0, i;
628 	struct got_indexed_object *objects = NULL, *obj;
629 	SHA1_CTX ctx;
630 	uint8_t packidx_hash[SHA1_DIGEST_LENGTH];
631 	ssize_t r, w;
632 	int pass, have_ref_deltas = 0, first_delta_idx = -1;
633 	size_t mapoff = 0;
634 	int p_indexed = 0, last_p_indexed = -1;
635 	int p_resolved = 0, last_p_resolved = -1;
636 
637 	/* Require that pack file header and SHA1 trailer are present. */
638 	if (pack->filesize < sizeof(hdr) + SHA1_DIGEST_LENGTH)
639 		return got_error_msg(GOT_ERR_BAD_PACKFILE,
640 		    "short pack file");
641 
642 	if (pack->map) {
643 		memcpy(&hdr, pack->map, sizeof(hdr));
644 		mapoff += sizeof(hdr);
645 	} else {
646 		r = read(pack->fd, &hdr, sizeof(hdr));
647 		if (r == -1)
648 			return got_error_from_errno("read");
649 		if (r < sizeof(hdr))
650 			return got_error_msg(GOT_ERR_BAD_PACKFILE,
651 			    "short pack file");
652 	}
653 
654 	if (hdr.signature != htobe32(GOT_PACKFILE_SIGNATURE))
655 		return got_error_msg(GOT_ERR_BAD_PACKFILE,
656 		    "bad packfile signature");
657 	if (hdr.version != htobe32(GOT_PACKFILE_VERSION))
658 		return got_error_msg(GOT_ERR_BAD_PACKFILE,
659 		    "bad packfile version");
660 	nobj = be32toh(hdr.nobjects);
661 	if (nobj == 0)
662 		return got_error_msg(GOT_ERR_BAD_PACKFILE,
663 		    "bad packfile with zero objects");
664 
665 	/* We compute the SHA1 of pack file contents and verify later on. */
666 	SHA1Init(&ctx);
667 	SHA1Update(&ctx, (void *)&hdr, sizeof(hdr));
668 
669 	/*
670 	 * Create an in-memory pack index which will grow as objects
671 	 * IDs in the pack file are discovered. Only fields used to
672 	 * read deltified objects will be needed by the pack.c library
673 	 * code, so setting up just a pack index header is sufficient.
674 	 */
675 	memset(&packidx, 0, sizeof(packidx));
676 	packidx.hdr.magic = malloc(sizeof(uint32_t));
677 	if (packidx.hdr.magic == NULL)
678 		return got_error_from_errno("calloc");
679 	*packidx.hdr.magic = htobe32(GOT_PACKIDX_V2_MAGIC);
680 	packidx.hdr.version = malloc(sizeof(uint32_t));
681 	if (packidx.hdr.version == NULL) {
682 		err = got_error_from_errno("malloc");
683 		goto done;
684 	}
685 	*packidx.hdr.version = htobe32(GOT_PACKIDX_VERSION);
686 	packidx.hdr.fanout_table = calloc(GOT_PACKIDX_V2_FANOUT_TABLE_ITEMS,
687 	    sizeof(uint32_t));
688 	if (packidx.hdr.fanout_table == NULL) {
689 		err = got_error_from_errno("calloc");
690 		goto done;
691 	}
692 	packidx.hdr.sorted_ids = calloc(nobj,
693 	    sizeof(struct got_packidx_object_id));
694 	if (packidx.hdr.sorted_ids == NULL) {
695 		err = got_error_from_errno("calloc");
696 		goto done;
697 	}
698 	packidx.hdr.crc32 = calloc(nobj, sizeof(uint32_t));
699 	if (packidx.hdr.crc32 == NULL) {
700 		err = got_error_from_errno("calloc");
701 		goto done;
702 	}
703 	packidx.hdr.offsets = calloc(nobj, sizeof(uint32_t));
704 	if (packidx.hdr.offsets == NULL) {
705 		err = got_error_from_errno("calloc");
706 		goto done;
707 	}
708 	/* Large offsets table is empty for pack files < 2 GB. */
709 	if (pack->filesize >= GOT_PACKIDX_OFFSET_VAL_IS_LARGE_IDX) {
710 		packidx.hdr.large_offsets = calloc(nobj, sizeof(uint64_t));
711 		if (packidx.hdr.large_offsets == NULL) {
712 			err = got_error_from_errno("calloc");
713 			goto done;
714 		}
715 	}
716 
717 	nvalid = 0;
718 	nloose = 0;
719 	objects = calloc(nobj, sizeof(struct got_indexed_object));
720 	if (objects == NULL)
721 		return got_error_from_errno("calloc");
722 
723 	/*
724 	 * First pass: locate all objects and identify un-deltified objects.
725 	 *
726 	 * When this pass has completed we will know offset, type, size, and
727 	 * CRC information for all objects in this pack file. We won't know
728 	 * any of the actual object IDs of deltified objects yet since we
729 	 * will not yet attempt to combine deltas.
730 	 */
731 	pass = 1;
732 	for (i = 0; i < nobj; i++) {
733 		/* Don't send too many progress privsep messages. */
734 		p_indexed = ((i + 1) * 100) / nobj;
735 		if (p_indexed != last_p_indexed) {
736 			err = send_index_pack_progress(ibuf, nobj, i + 1,
737 			    nloose, 0);
738 			if (err)
739 				goto done;
740 			last_p_indexed = p_indexed;
741 		}
742 
743 		obj = &objects[i];
744 		obj->crc = crc32(0L, NULL, 0);
745 
746 		/* Store offset to type+size information for this object. */
747 		if (pack->map) {
748 			obj->off = mapoff;
749 		} else {
750 			obj->off = lseek(pack->fd, 0, SEEK_CUR);
751 			if (obj->off == -1) {
752 				err = got_error_from_errno("lseek");
753 				goto done;
754 			}
755 		}
756 
757 		err = read_packed_object(pack, obj, tmpfile, &ctx);
758 		if (err)
759 			goto done;
760 
761 		if (pack->map) {
762 			mapoff += obj->tslen + obj->len;
763 		} else {
764 			if (lseek(pack->fd, obj->off + obj->tslen + obj->len,
765 			    SEEK_SET) == -1) {
766 				err = got_error_from_errno("lseek");
767 				goto done;
768 			}
769 		}
770 
771 		if (obj->type == GOT_OBJ_TYPE_BLOB ||
772 		    obj->type == GOT_OBJ_TYPE_TREE ||
773 		    obj->type == GOT_OBJ_TYPE_COMMIT ||
774 		    obj->type == GOT_OBJ_TYPE_TAG) {
775 			obj->valid = 1;
776 			nloose++;
777 		} else {
778 			if (first_delta_idx == -1)
779 				first_delta_idx = i;
780 			if (obj->type == GOT_OBJ_TYPE_REF_DELTA)
781 				have_ref_deltas = 1;
782 		}
783 	}
784 	nvalid = nloose;
785 
786 	/*
787 	 * Having done a full pass over the pack file and can now
788 	 * verify its checksum.
789 	 */
790 	SHA1Final(pack_sha1, &ctx);
791 	if (memcmp(pack_sha1_expected, pack_sha1, SHA1_DIGEST_LENGTH) != 0) {
792 		err = got_error_msg(GOT_ERR_BAD_PACKFILE,
793 		    "pack file checksum mismatch");
794 		goto done;
795 	}
796 
797 	/* Verify the SHA1 checksum stored at the end of the pack file. */
798 	if (pack->map) {
799 		memcpy(pack_sha1_expected, pack->map +
800 		    pack->filesize - SHA1_DIGEST_LENGTH,
801 		    SHA1_DIGEST_LENGTH);
802 	} else {
803 		ssize_t n;
804 		if (lseek(pack->fd, -SHA1_DIGEST_LENGTH, SEEK_END) == -1) {
805 			err = got_error_from_errno("lseek");
806 			goto done;
807 		}
808 		n = read(pack->fd, pack_sha1_expected, SHA1_DIGEST_LENGTH);
809 		if (n == -1) {
810 			err = got_error_from_errno("read");
811 			goto done;
812 		}
813 		if (n != SHA1_DIGEST_LENGTH) {
814 			err = got_error(GOT_ERR_IO);
815 			goto done;
816 		}
817 	}
818 	if (memcmp(pack_sha1, pack_sha1_expected, SHA1_DIGEST_LENGTH) != 0) {
819 		err = got_error_msg(GOT_ERR_BAD_PACKFILE,
820 		    "bad checksum in pack file trailer");
821 		goto done;
822 	}
823 
824 	if (first_delta_idx == -1)
825 		first_delta_idx = 0;
826 
827 	/* In order to resolve ref deltas we need an in-progress pack index. */
828 	if (have_ref_deltas)
829 		make_packidx(&packidx, nobj, objects);
830 
831 	/*
832 	 * Second pass: We can now resolve deltas to compute the IDs of
833 	 * objects which appear in deltified form. Because deltas can be
834 	 * chained this pass may require a couple of iterations until all
835 	 * IDs of deltified objects have been discovered.
836 	 */
837 	pass++;
838 	while (nvalid != nobj) {
839 		int n = 0;
840 		/*
841 		 * This loop will only run once unless the pack file
842 		 * contains ref deltas which refer to objects located
843 		 * later in the pack file, which is unusual.
844 		 * Offset deltas can always be resolved in one pass
845 		 * unless the packfile is corrupt.
846 		 */
847 		for (i = first_delta_idx; i < nobj; i++) {
848 			obj = &objects[i];
849 			if (obj->type != GOT_OBJ_TYPE_REF_DELTA &&
850 			    obj->type != GOT_OBJ_TYPE_OFFSET_DELTA)
851 				continue;
852 
853 			if (obj->valid)
854 				continue;
855 
856 			if (pack->map == NULL && lseek(pack->fd,
857 			    obj->off + obj->tslen, SEEK_SET) == -1) {
858 				err = got_error_from_errno("lseek");
859 				goto done;
860 			}
861 
862 			err = resolve_deltified_object(pack, &packidx, obj,
863 			    tmpfile, delta_base_file, delta_accum_file);
864 			if (err) {
865 				if (err->code != GOT_ERR_NO_OBJ)
866 					goto done;
867 				/*
868 				 * We cannot resolve this object yet because
869 				 * a delta base is unknown. Try again later.
870 				 */
871 				continue;
872 			}
873 
874 			obj->valid = 1;
875 			n++;
876 			if (have_ref_deltas)
877 				update_packidx(&packidx, nobj, obj);
878 			/* Don't send too many progress privsep messages. */
879 			p_resolved = ((nresolved + n) * 100) / nobj;
880 			if (p_resolved != last_p_resolved) {
881 				err = send_index_pack_progress(ibuf, nobj,
882 				    nobj, nloose, nresolved + n);
883 				if (err)
884 					goto done;
885 				last_p_resolved = p_resolved;
886 			}
887 
888 		}
889 		if (pass++ > 3 && n == 0) {
890 			static char msg[64];
891 			snprintf(msg, sizeof(msg), "could not resolve "
892 			    "any of deltas; packfile could be corrupt");
893 			err = got_error_msg(GOT_ERR_BAD_PACKFILE, msg);
894 			goto done;
895 
896 		}
897 		nresolved += n;
898 		nvalid += nresolved;
899 	}
900 
901 	if (nloose + nresolved != nobj) {
902 		static char msg[64];
903 		snprintf(msg, sizeof(msg), "discovered only %d of %d objects",
904 		    nloose + nresolved, nobj);
905 		err = got_error_msg(GOT_ERR_BAD_PACKFILE, msg);
906 		goto done;
907 	}
908 
909 	err = send_index_pack_progress(ibuf, nobj, nobj, nloose, nresolved);
910 	if (err)
911 		goto done;
912 
913 	make_packidx(&packidx, nobj, objects);
914 
915 	free(objects);
916 	objects = NULL;
917 
918 	SHA1Init(&ctx);
919 	putbe32(buf, GOT_PACKIDX_V2_MAGIC);
920 	putbe32(buf + 4, GOT_PACKIDX_VERSION);
921 	err = hwrite(idxfd, buf, 8, &ctx);
922 	if (err)
923 		goto done;
924 	err = hwrite(idxfd, packidx.hdr.fanout_table,
925 	    GOT_PACKIDX_V2_FANOUT_TABLE_ITEMS * sizeof(uint32_t), &ctx);
926 	if (err)
927 		goto done;
928 	err = hwrite(idxfd, packidx.hdr.sorted_ids,
929 	    nobj * SHA1_DIGEST_LENGTH, &ctx);
930 	if (err)
931 		goto done;
932 	err = hwrite(idxfd, packidx.hdr.crc32, nobj * sizeof(uint32_t), &ctx);
933 	if (err)
934 		goto done;
935 	err = hwrite(idxfd, packidx.hdr.offsets, nobj * sizeof(uint32_t),
936 	    &ctx);
937 	if (err)
938 		goto done;
939 	if (packidx.nlargeobj > 0) {
940 		err = hwrite(idxfd, packidx.hdr.large_offsets,
941 		    packidx.nlargeobj * sizeof(uint64_t), &ctx);
942 		if (err)
943 			goto done;
944 	}
945 	err = hwrite(idxfd, pack_sha1, SHA1_DIGEST_LENGTH, &ctx);
946 	if (err)
947 		goto done;
948 
949 	SHA1Final(packidx_hash, &ctx);
950 	w = write(idxfd, packidx_hash, sizeof(packidx_hash));
951 	if (w == -1) {
952 		err = got_error_from_errno("write");
953 		goto done;
954 	}
955 	if (w != sizeof(packidx_hash)) {
956 		err = got_error(GOT_ERR_IO);
957 		goto done;
958 	}
959 done:
960 	free(objects);
961 	free(packidx.hdr.magic);
962 	free(packidx.hdr.version);
963 	free(packidx.hdr.fanout_table);
964 	free(packidx.hdr.sorted_ids);
965 	free(packidx.hdr.offsets);
966 	free(packidx.hdr.large_offsets);
967 	return err;
968 }
969 
970 int
971 main(int argc, char **argv)
972 {
973 	const struct got_error *err = NULL, *close_err;
974 	struct imsgbuf ibuf;
975 	struct imsg imsg;
976 	size_t i;
977 	int idxfd = -1, tmpfd = -1;
978 	FILE *tmpfiles[3];
979 	struct got_pack pack;
980 	uint8_t pack_hash[SHA1_DIGEST_LENGTH];
981 	off_t packfile_size;
982 #if 0
983 	static int attached;
984 	while (!attached)
985 		sleep(1);
986 #endif
987 
988 	for (i = 0; i < nitems(tmpfiles); i++)
989 		tmpfiles[i] = NULL;
990 
991 	memset(&pack, 0, sizeof(pack));
992 	pack.fd = -1;
993 	pack.delta_cache = got_delta_cache_alloc(500,
994 	    GOT_DELTA_RESULT_SIZE_CACHED_MAX);
995 	if (pack.delta_cache == NULL) {
996 		err = got_error_from_errno("got_delta_cache_alloc");
997 		goto done;
998 	}
999 
1000 	imsg_init(&ibuf, GOT_IMSG_FD_CHILD);
1001 #ifndef PROFILE
1002 	/* revoke access to most system calls */
1003 	if (pledge("stdio recvfd", NULL) == -1) {
1004 		err = got_error_from_errno("pledge");
1005 		got_privsep_send_error(&ibuf, err);
1006 		return 1;
1007 	}
1008 #endif
1009 	err = got_privsep_recv_imsg(&imsg, &ibuf, 0);
1010 	if (err)
1011 		goto done;
1012 	if (imsg.hdr.type == GOT_IMSG_STOP)
1013 		goto done;
1014 	if (imsg.hdr.type != GOT_IMSG_IDXPACK_REQUEST) {
1015 		err = got_error(GOT_ERR_PRIVSEP_MSG);
1016 		goto done;
1017 	}
1018 	if (imsg.hdr.len - IMSG_HEADER_SIZE != sizeof(pack_hash)) {
1019 		err = got_error(GOT_ERR_PRIVSEP_LEN);
1020 		goto done;
1021 	}
1022 	memcpy(pack_hash, imsg.data, sizeof(pack_hash));
1023 	pack.fd = imsg.fd;
1024 
1025 	err = got_privsep_recv_imsg(&imsg, &ibuf, 0);
1026 	if (err)
1027 		goto done;
1028 	if (imsg.hdr.type == GOT_IMSG_STOP)
1029 		goto done;
1030 	if (imsg.hdr.type != GOT_IMSG_IDXPACK_OUTFD) {
1031 		err = got_error(GOT_ERR_PRIVSEP_MSG);
1032 		goto done;
1033 	}
1034 	if (imsg.hdr.len - IMSG_HEADER_SIZE != 0) {
1035 		err = got_error(GOT_ERR_PRIVSEP_LEN);
1036 		goto done;
1037 	}
1038 	idxfd = imsg.fd;
1039 
1040 	for (i = 0; i < nitems(tmpfiles); i++) {
1041 		err = got_privsep_recv_imsg(&imsg, &ibuf, 0);
1042 		if (err)
1043 			goto done;
1044 		if (imsg.hdr.type == GOT_IMSG_STOP)
1045 			goto done;
1046 		if (imsg.hdr.type != GOT_IMSG_TMPFD) {
1047 			err = got_error(GOT_ERR_PRIVSEP_MSG);
1048 			goto done;
1049 		}
1050 		if (imsg.hdr.len - IMSG_HEADER_SIZE != 0) {
1051 			err = got_error(GOT_ERR_PRIVSEP_LEN);
1052 			goto done;
1053 		}
1054 		tmpfd = imsg.fd;
1055 		tmpfiles[i] = fdopen(tmpfd, "w+");
1056 		if (tmpfiles[i] == NULL) {
1057 			err = got_error_from_errno("fdopen");
1058 			goto done;
1059 		}
1060 		tmpfd = -1;
1061 	}
1062 
1063 	if (lseek(pack.fd, 0, SEEK_END) == -1) {
1064 		err = got_error_from_errno("lseek");
1065 		goto done;
1066 	}
1067 	packfile_size = lseek(pack.fd, 0, SEEK_CUR);
1068 	if (packfile_size == -1) {
1069 		err = got_error_from_errno("lseek");
1070 		goto done;
1071 	}
1072 	pack.filesize = packfile_size; /* XXX off_t vs size_t */
1073 
1074 	if (lseek(pack.fd, 0, SEEK_SET) == -1) {
1075 		err = got_error_from_errno("lseek");
1076 		goto done;
1077 	}
1078 
1079 #ifndef GOT_PACK_NO_MMAP
1080 	pack.map = mmap(NULL, pack.filesize, PROT_READ, MAP_PRIVATE,
1081 	    pack.fd, 0);
1082 	if (pack.map == MAP_FAILED)
1083 		pack.map = NULL; /* fall back to read(2) */
1084 #endif
1085 	err = index_pack(&pack, idxfd, tmpfiles[0], tmpfiles[1], tmpfiles[2],
1086 	    pack_hash, &ibuf);
1087 done:
1088 	close_err = got_pack_close(&pack);
1089 	if (close_err && err == NULL)
1090 		err = close_err;
1091 	if (idxfd != -1 && close(idxfd) == -1 && err == NULL)
1092 		err = got_error_from_errno("close");
1093 	if (tmpfd != -1 && close(tmpfd) == -1 && err == NULL)
1094 		err = got_error_from_errno("close");
1095 	for (i = 0; i < nitems(tmpfiles); i++) {
1096 		if (tmpfiles[i] != NULL && fclose(tmpfiles[i]) == EOF &&
1097 		    err == NULL)
1098 			err = got_error_from_errno("close");
1099 	}
1100 
1101 	if (err == NULL)
1102 		err = send_index_pack_done(&ibuf);
1103 	if (err) {
1104 		got_privsep_send_error(&ibuf, err);
1105 		fprintf(stderr, "%s: %s\n", getprogname(), err->msg);
1106 		got_privsep_send_error(&ibuf, err);
1107 		exit(1);
1108 	}
1109 
1110 	exit(0);
1111 }