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