lib/pack_index.c

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