libexec/got-index-pack/got-index-pack.c

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