op public repos

Blob

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