Gotweb

Blob

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