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