builtin / index-pack.con commit index-pack: show histogram when emulating "verify-pack -v" (d1a0ed1)
   1#include "cache.h"
   2#include "delta.h"
   3#include "pack.h"
   4#include "csum-file.h"
   5#include "blob.h"
   6#include "commit.h"
   7#include "tag.h"
   8#include "tree.h"
   9#include "progress.h"
  10#include "fsck.h"
  11#include "exec_cmd.h"
  12
  13static const char index_pack_usage[] =
  14"git index-pack [-v] [-o <index-file>] [--keep | --keep=<msg>] [--verify] [--strict] (<pack-file> | --stdin [--fix-thin] [<pack-file>])";
  15
  16struct object_entry
  17{
  18        struct pack_idx_entry idx;
  19        unsigned long size;
  20        unsigned int hdr_size;
  21        enum object_type type;
  22        enum object_type real_type;
  23        unsigned delta_depth;
  24        int base_object_no;
  25};
  26
  27union delta_base {
  28        unsigned char sha1[20];
  29        off_t offset;
  30};
  31
  32struct base_data {
  33        struct base_data *base;
  34        struct base_data *child;
  35        struct object_entry *obj;
  36        void *data;
  37        unsigned long size;
  38};
  39
  40/*
  41 * Even if sizeof(union delta_base) == 24 on 64-bit archs, we really want
  42 * to memcmp() only the first 20 bytes.
  43 */
  44#define UNION_BASE_SZ   20
  45
  46#define FLAG_LINK (1u<<20)
  47#define FLAG_CHECKED (1u<<21)
  48
  49struct delta_entry
  50{
  51        union delta_base base;
  52        int obj_no;
  53};
  54
  55static struct object_entry *objects;
  56static struct delta_entry *deltas;
  57static struct base_data *base_cache;
  58static size_t base_cache_used;
  59static int nr_objects;
  60static int nr_deltas;
  61static int nr_resolved_deltas;
  62
  63static int from_stdin;
  64static int strict;
  65static int verbose;
  66
  67static struct progress *progress;
  68
  69/* We always read in 4kB chunks. */
  70static unsigned char input_buffer[4096];
  71static unsigned int input_offset, input_len;
  72static off_t consumed_bytes;
  73static unsigned deepest_delta;
  74static git_SHA_CTX input_ctx;
  75static uint32_t input_crc32;
  76static int input_fd, output_fd, pack_fd;
  77
  78static int mark_link(struct object *obj, int type, void *data)
  79{
  80        if (!obj)
  81                return -1;
  82
  83        if (type != OBJ_ANY && obj->type != type)
  84                die("object type mismatch at %s", sha1_to_hex(obj->sha1));
  85
  86        obj->flags |= FLAG_LINK;
  87        return 0;
  88}
  89
  90/* The content of each linked object must have been checked
  91   or it must be already present in the object database */
  92static void check_object(struct object *obj)
  93{
  94        if (!obj)
  95                return;
  96
  97        if (!(obj->flags & FLAG_LINK))
  98                return;
  99
 100        if (!(obj->flags & FLAG_CHECKED)) {
 101                unsigned long size;
 102                int type = sha1_object_info(obj->sha1, &size);
 103                if (type != obj->type || type <= 0)
 104                        die("object of unexpected type");
 105                obj->flags |= FLAG_CHECKED;
 106                return;
 107        }
 108}
 109
 110static void check_objects(void)
 111{
 112        unsigned i, max;
 113
 114        max = get_max_object_index();
 115        for (i = 0; i < max; i++)
 116                check_object(get_indexed_object(i));
 117}
 118
 119
 120/* Discard current buffer used content. */
 121static void flush(void)
 122{
 123        if (input_offset) {
 124                if (output_fd >= 0)
 125                        write_or_die(output_fd, input_buffer, input_offset);
 126                git_SHA1_Update(&input_ctx, input_buffer, input_offset);
 127                memmove(input_buffer, input_buffer + input_offset, input_len);
 128                input_offset = 0;
 129        }
 130}
 131
 132/*
 133 * Make sure at least "min" bytes are available in the buffer, and
 134 * return the pointer to the buffer.
 135 */
 136static void *fill(int min)
 137{
 138        if (min <= input_len)
 139                return input_buffer + input_offset;
 140        if (min > sizeof(input_buffer))
 141                die("cannot fill %d bytes", min);
 142        flush();
 143        do {
 144                ssize_t ret = xread(input_fd, input_buffer + input_len,
 145                                sizeof(input_buffer) - input_len);
 146                if (ret <= 0) {
 147                        if (!ret)
 148                                die("early EOF");
 149                        die_errno("read error on input");
 150                }
 151                input_len += ret;
 152                if (from_stdin)
 153                        display_throughput(progress, consumed_bytes + input_len);
 154        } while (input_len < min);
 155        return input_buffer;
 156}
 157
 158static void use(int bytes)
 159{
 160        if (bytes > input_len)
 161                die("used more bytes than were available");
 162        input_crc32 = crc32(input_crc32, input_buffer + input_offset, bytes);
 163        input_len -= bytes;
 164        input_offset += bytes;
 165
 166        /* make sure off_t is sufficiently large not to wrap */
 167        if (signed_add_overflows(consumed_bytes, bytes))
 168                die("pack too large for current definition of off_t");
 169        consumed_bytes += bytes;
 170}
 171
 172static const char *open_pack_file(const char *pack_name)
 173{
 174        if (from_stdin) {
 175                input_fd = 0;
 176                if (!pack_name) {
 177                        static char tmpfile[PATH_MAX];
 178                        output_fd = odb_mkstemp(tmpfile, sizeof(tmpfile),
 179                                                "pack/tmp_pack_XXXXXX");
 180                        pack_name = xstrdup(tmpfile);
 181                } else
 182                        output_fd = open(pack_name, O_CREAT|O_EXCL|O_RDWR, 0600);
 183                if (output_fd < 0)
 184                        die_errno("unable to create '%s'", pack_name);
 185                pack_fd = output_fd;
 186        } else {
 187                input_fd = open(pack_name, O_RDONLY);
 188                if (input_fd < 0)
 189                        die_errno("cannot open packfile '%s'", pack_name);
 190                output_fd = -1;
 191                pack_fd = input_fd;
 192        }
 193        git_SHA1_Init(&input_ctx);
 194        return pack_name;
 195}
 196
 197static void parse_pack_header(void)
 198{
 199        struct pack_header *hdr = fill(sizeof(struct pack_header));
 200
 201        /* Header consistency check */
 202        if (hdr->hdr_signature != htonl(PACK_SIGNATURE))
 203                die("pack signature mismatch");
 204        if (!pack_version_ok(hdr->hdr_version))
 205                die("pack version %"PRIu32" unsupported",
 206                        ntohl(hdr->hdr_version));
 207
 208        nr_objects = ntohl(hdr->hdr_entries);
 209        use(sizeof(struct pack_header));
 210}
 211
 212static NORETURN void bad_object(unsigned long offset, const char *format,
 213                       ...) __attribute__((format (printf, 2, 3)));
 214
 215static void bad_object(unsigned long offset, const char *format, ...)
 216{
 217        va_list params;
 218        char buf[1024];
 219
 220        va_start(params, format);
 221        vsnprintf(buf, sizeof(buf), format, params);
 222        va_end(params);
 223        die("pack has bad object at offset %lu: %s", offset, buf);
 224}
 225
 226static void free_base_data(struct base_data *c)
 227{
 228        if (c->data) {
 229                free(c->data);
 230                c->data = NULL;
 231                base_cache_used -= c->size;
 232        }
 233}
 234
 235static void prune_base_data(struct base_data *retain)
 236{
 237        struct base_data *b;
 238        for (b = base_cache;
 239             base_cache_used > delta_base_cache_limit && b;
 240             b = b->child) {
 241                if (b->data && b != retain)
 242                        free_base_data(b);
 243        }
 244}
 245
 246static void link_base_data(struct base_data *base, struct base_data *c)
 247{
 248        if (base)
 249                base->child = c;
 250        else
 251                base_cache = c;
 252
 253        c->base = base;
 254        c->child = NULL;
 255        if (c->data)
 256                base_cache_used += c->size;
 257        prune_base_data(c);
 258}
 259
 260static void unlink_base_data(struct base_data *c)
 261{
 262        struct base_data *base = c->base;
 263        if (base)
 264                base->child = NULL;
 265        else
 266                base_cache = NULL;
 267        free_base_data(c);
 268}
 269
 270static void *unpack_entry_data(unsigned long offset, unsigned long size)
 271{
 272        int status;
 273        z_stream stream;
 274        void *buf = xmalloc(size);
 275
 276        memset(&stream, 0, sizeof(stream));
 277        git_inflate_init(&stream);
 278        stream.next_out = buf;
 279        stream.avail_out = size;
 280
 281        do {
 282                stream.next_in = fill(1);
 283                stream.avail_in = input_len;
 284                status = git_inflate(&stream, 0);
 285                use(input_len - stream.avail_in);
 286        } while (status == Z_OK);
 287        if (stream.total_out != size || status != Z_STREAM_END)
 288                bad_object(offset, "inflate returned %d", status);
 289        git_inflate_end(&stream);
 290        return buf;
 291}
 292
 293static void *unpack_raw_entry(struct object_entry *obj, union delta_base *delta_base)
 294{
 295        unsigned char *p;
 296        unsigned long size, c;
 297        off_t base_offset;
 298        unsigned shift;
 299        void *data;
 300
 301        obj->idx.offset = consumed_bytes;
 302        input_crc32 = crc32(0, Z_NULL, 0);
 303
 304        p = fill(1);
 305        c = *p;
 306        use(1);
 307        obj->type = (c >> 4) & 7;
 308        size = (c & 15);
 309        shift = 4;
 310        while (c & 0x80) {
 311                p = fill(1);
 312                c = *p;
 313                use(1);
 314                size += (c & 0x7f) << shift;
 315                shift += 7;
 316        }
 317        obj->size = size;
 318
 319        switch (obj->type) {
 320        case OBJ_REF_DELTA:
 321                hashcpy(delta_base->sha1, fill(20));
 322                use(20);
 323                break;
 324        case OBJ_OFS_DELTA:
 325                memset(delta_base, 0, sizeof(*delta_base));
 326                p = fill(1);
 327                c = *p;
 328                use(1);
 329                base_offset = c & 127;
 330                while (c & 128) {
 331                        base_offset += 1;
 332                        if (!base_offset || MSB(base_offset, 7))
 333                                bad_object(obj->idx.offset, "offset value overflow for delta base object");
 334                        p = fill(1);
 335                        c = *p;
 336                        use(1);
 337                        base_offset = (base_offset << 7) + (c & 127);
 338                }
 339                delta_base->offset = obj->idx.offset - base_offset;
 340                if (delta_base->offset <= 0 || delta_base->offset >= obj->idx.offset)
 341                        bad_object(obj->idx.offset, "delta base offset is out of bound");
 342                break;
 343        case OBJ_COMMIT:
 344        case OBJ_TREE:
 345        case OBJ_BLOB:
 346        case OBJ_TAG:
 347                break;
 348        default:
 349                bad_object(obj->idx.offset, "unknown object type %d", obj->type);
 350        }
 351        obj->hdr_size = consumed_bytes - obj->idx.offset;
 352
 353        data = unpack_entry_data(obj->idx.offset, obj->size);
 354        obj->idx.crc32 = input_crc32;
 355        return data;
 356}
 357
 358static void *get_data_from_pack(struct object_entry *obj)
 359{
 360        off_t from = obj[0].idx.offset + obj[0].hdr_size;
 361        unsigned long len = obj[1].idx.offset - from;
 362        unsigned char *data, *inbuf;
 363        z_stream stream;
 364        int status;
 365
 366        data = xmalloc(obj->size);
 367        inbuf = xmalloc((len < 64*1024) ? len : 64*1024);
 368
 369        memset(&stream, 0, sizeof(stream));
 370        git_inflate_init(&stream);
 371        stream.next_out = data;
 372        stream.avail_out = obj->size;
 373
 374        do {
 375                ssize_t n = (len < 64*1024) ? len : 64*1024;
 376                n = pread(pack_fd, inbuf, n, from);
 377                if (n < 0)
 378                        die_errno("cannot pread pack file");
 379                if (!n)
 380                        die("premature end of pack file, %lu bytes missing", len);
 381                from += n;
 382                len -= n;
 383                stream.next_in = inbuf;
 384                stream.avail_in = n;
 385                status = git_inflate(&stream, 0);
 386        } while (len && status == Z_OK && !stream.avail_in);
 387
 388        /* This has been inflated OK when first encountered, so... */
 389        if (status != Z_STREAM_END || stream.total_out != obj->size)
 390                die("serious inflate inconsistency");
 391
 392        git_inflate_end(&stream);
 393        free(inbuf);
 394        return data;
 395}
 396
 397static int compare_delta_bases(const union delta_base *base1,
 398                               const union delta_base *base2,
 399                               enum object_type type1,
 400                               enum object_type type2)
 401{
 402        int cmp = type1 - type2;
 403        if (cmp)
 404                return cmp;
 405        return memcmp(base1, base2, UNION_BASE_SZ);
 406}
 407
 408static int find_delta(const union delta_base *base, enum object_type type)
 409{
 410        int first = 0, last = nr_deltas;
 411
 412        while (first < last) {
 413                int next = (first + last) / 2;
 414                struct delta_entry *delta = &deltas[next];
 415                int cmp;
 416
 417                cmp = compare_delta_bases(base, &delta->base,
 418                                          type, objects[delta->obj_no].type);
 419                if (!cmp)
 420                        return next;
 421                if (cmp < 0) {
 422                        last = next;
 423                        continue;
 424                }
 425                first = next+1;
 426        }
 427        return -first-1;
 428}
 429
 430static void find_delta_children(const union delta_base *base,
 431                                int *first_index, int *last_index,
 432                                enum object_type type)
 433{
 434        int first = find_delta(base, type);
 435        int last = first;
 436        int end = nr_deltas - 1;
 437
 438        if (first < 0) {
 439                *first_index = 0;
 440                *last_index = -1;
 441                return;
 442        }
 443        while (first > 0 && !memcmp(&deltas[first - 1].base, base, UNION_BASE_SZ))
 444                --first;
 445        while (last < end && !memcmp(&deltas[last + 1].base, base, UNION_BASE_SZ))
 446                ++last;
 447        *first_index = first;
 448        *last_index = last;
 449}
 450
 451static void sha1_object(const void *data, unsigned long size,
 452                        enum object_type type, unsigned char *sha1)
 453{
 454        hash_sha1_file(data, size, typename(type), sha1);
 455        if (has_sha1_file(sha1)) {
 456                void *has_data;
 457                enum object_type has_type;
 458                unsigned long has_size;
 459                has_data = read_sha1_file(sha1, &has_type, &has_size);
 460                if (!has_data)
 461                        die("cannot read existing object %s", sha1_to_hex(sha1));
 462                if (size != has_size || type != has_type ||
 463                    memcmp(data, has_data, size) != 0)
 464                        die("SHA1 COLLISION FOUND WITH %s !", sha1_to_hex(sha1));
 465                free(has_data);
 466        }
 467        if (strict) {
 468                if (type == OBJ_BLOB) {
 469                        struct blob *blob = lookup_blob(sha1);
 470                        if (blob)
 471                                blob->object.flags |= FLAG_CHECKED;
 472                        else
 473                                die("invalid blob object %s", sha1_to_hex(sha1));
 474                } else {
 475                        struct object *obj;
 476                        int eaten;
 477                        void *buf = (void *) data;
 478
 479                        /*
 480                         * we do not need to free the memory here, as the
 481                         * buf is deleted by the caller.
 482                         */
 483                        obj = parse_object_buffer(sha1, type, size, buf, &eaten);
 484                        if (!obj)
 485                                die("invalid %s", typename(type));
 486                        if (fsck_object(obj, 1, fsck_error_function))
 487                                die("Error in object");
 488                        if (fsck_walk(obj, mark_link, NULL))
 489                                die("Not all child objects of %s are reachable", sha1_to_hex(obj->sha1));
 490
 491                        if (obj->type == OBJ_TREE) {
 492                                struct tree *item = (struct tree *) obj;
 493                                item->buffer = NULL;
 494                        }
 495                        if (obj->type == OBJ_COMMIT) {
 496                                struct commit *commit = (struct commit *) obj;
 497                                commit->buffer = NULL;
 498                        }
 499                        obj->flags |= FLAG_CHECKED;
 500                }
 501        }
 502}
 503
 504static int is_delta_type(enum object_type type)
 505{
 506        return (type == OBJ_REF_DELTA || type == OBJ_OFS_DELTA);
 507}
 508
 509static void *get_base_data(struct base_data *c)
 510{
 511        if (!c->data) {
 512                struct object_entry *obj = c->obj;
 513
 514                if (is_delta_type(obj->type)) {
 515                        void *base = get_base_data(c->base);
 516                        void *raw = get_data_from_pack(obj);
 517                        c->data = patch_delta(
 518                                base, c->base->size,
 519                                raw, obj->size,
 520                                &c->size);
 521                        free(raw);
 522                        if (!c->data)
 523                                bad_object(obj->idx.offset, "failed to apply delta");
 524                } else {
 525                        c->data = get_data_from_pack(obj);
 526                        c->size = obj->size;
 527                }
 528
 529                base_cache_used += c->size;
 530                prune_base_data(c);
 531        }
 532        return c->data;
 533}
 534
 535static void resolve_delta(struct object_entry *delta_obj,
 536                          struct base_data *base, struct base_data *result)
 537{
 538        void *base_data, *delta_data;
 539
 540        delta_obj->real_type = base->obj->real_type;
 541        delta_obj->delta_depth = base->obj->delta_depth + 1;
 542        if (deepest_delta < delta_obj->delta_depth)
 543                deepest_delta = delta_obj->delta_depth;
 544        delta_obj->base_object_no = base->obj - objects;
 545        delta_data = get_data_from_pack(delta_obj);
 546        base_data = get_base_data(base);
 547        result->obj = delta_obj;
 548        result->data = patch_delta(base_data, base->size,
 549                                   delta_data, delta_obj->size, &result->size);
 550        free(delta_data);
 551        if (!result->data)
 552                bad_object(delta_obj->idx.offset, "failed to apply delta");
 553        sha1_object(result->data, result->size, delta_obj->real_type,
 554                    delta_obj->idx.sha1);
 555        nr_resolved_deltas++;
 556}
 557
 558static void find_unresolved_deltas(struct base_data *base,
 559                                   struct base_data *prev_base)
 560{
 561        int i, ref_first, ref_last, ofs_first, ofs_last;
 562
 563        /*
 564         * This is a recursive function. Those brackets should help reducing
 565         * stack usage by limiting the scope of the delta_base union.
 566         */
 567        {
 568                union delta_base base_spec;
 569
 570                hashcpy(base_spec.sha1, base->obj->idx.sha1);
 571                find_delta_children(&base_spec,
 572                                    &ref_first, &ref_last, OBJ_REF_DELTA);
 573
 574                memset(&base_spec, 0, sizeof(base_spec));
 575                base_spec.offset = base->obj->idx.offset;
 576                find_delta_children(&base_spec,
 577                                    &ofs_first, &ofs_last, OBJ_OFS_DELTA);
 578        }
 579
 580        if (ref_last == -1 && ofs_last == -1) {
 581                free(base->data);
 582                return;
 583        }
 584
 585        link_base_data(prev_base, base);
 586
 587        for (i = ref_first; i <= ref_last; i++) {
 588                struct object_entry *child = objects + deltas[i].obj_no;
 589                struct base_data result;
 590
 591                assert(child->real_type == OBJ_REF_DELTA);
 592                resolve_delta(child, base, &result);
 593                if (i == ref_last && ofs_last == -1)
 594                        free_base_data(base);
 595                find_unresolved_deltas(&result, base);
 596        }
 597
 598        for (i = ofs_first; i <= ofs_last; i++) {
 599                struct object_entry *child = objects + deltas[i].obj_no;
 600                struct base_data result;
 601
 602                assert(child->real_type == OBJ_OFS_DELTA);
 603                resolve_delta(child, base, &result);
 604                if (i == ofs_last)
 605                        free_base_data(base);
 606                find_unresolved_deltas(&result, base);
 607        }
 608
 609        unlink_base_data(base);
 610}
 611
 612static int compare_delta_entry(const void *a, const void *b)
 613{
 614        const struct delta_entry *delta_a = a;
 615        const struct delta_entry *delta_b = b;
 616
 617        /* group by type (ref vs ofs) and then by value (sha-1 or offset) */
 618        return compare_delta_bases(&delta_a->base, &delta_b->base,
 619                                   objects[delta_a->obj_no].type,
 620                                   objects[delta_b->obj_no].type);
 621}
 622
 623/* Parse all objects and return the pack content SHA1 hash */
 624static void parse_pack_objects(unsigned char *sha1)
 625{
 626        int i;
 627        struct delta_entry *delta = deltas;
 628        struct stat st;
 629
 630        /*
 631         * First pass:
 632         * - find locations of all objects;
 633         * - calculate SHA1 of all non-delta objects;
 634         * - remember base (SHA1 or offset) for all deltas.
 635         */
 636        if (verbose)
 637                progress = start_progress(
 638                                from_stdin ? "Receiving objects" : "Indexing objects",
 639                                nr_objects);
 640        for (i = 0; i < nr_objects; i++) {
 641                struct object_entry *obj = &objects[i];
 642                void *data = unpack_raw_entry(obj, &delta->base);
 643                obj->real_type = obj->type;
 644                if (is_delta_type(obj->type)) {
 645                        nr_deltas++;
 646                        delta->obj_no = i;
 647                        delta++;
 648                } else
 649                        sha1_object(data, obj->size, obj->type, obj->idx.sha1);
 650                free(data);
 651                display_progress(progress, i+1);
 652        }
 653        objects[i].idx.offset = consumed_bytes;
 654        stop_progress(&progress);
 655
 656        /* Check pack integrity */
 657        flush();
 658        git_SHA1_Final(sha1, &input_ctx);
 659        if (hashcmp(fill(20), sha1))
 660                die("pack is corrupted (SHA1 mismatch)");
 661        use(20);
 662
 663        /* If input_fd is a file, we should have reached its end now. */
 664        if (fstat(input_fd, &st))
 665                die_errno("cannot fstat packfile");
 666        if (S_ISREG(st.st_mode) &&
 667                        lseek(input_fd, 0, SEEK_CUR) - input_len != st.st_size)
 668                die("pack has junk at the end");
 669
 670        if (!nr_deltas)
 671                return;
 672
 673        /* Sort deltas by base SHA1/offset for fast searching */
 674        qsort(deltas, nr_deltas, sizeof(struct delta_entry),
 675              compare_delta_entry);
 676
 677        /*
 678         * Second pass:
 679         * - for all non-delta objects, look if it is used as a base for
 680         *   deltas;
 681         * - if used as a base, uncompress the object and apply all deltas,
 682         *   recursively checking if the resulting object is used as a base
 683         *   for some more deltas.
 684         */
 685        if (verbose)
 686                progress = start_progress("Resolving deltas", nr_deltas);
 687        for (i = 0; i < nr_objects; i++) {
 688                struct object_entry *obj = &objects[i];
 689                struct base_data base_obj;
 690
 691                if (is_delta_type(obj->type))
 692                        continue;
 693                base_obj.obj = obj;
 694                base_obj.data = NULL;
 695                find_unresolved_deltas(&base_obj, NULL);
 696                display_progress(progress, nr_resolved_deltas);
 697        }
 698}
 699
 700static int write_compressed(struct sha1file *f, void *in, unsigned int size)
 701{
 702        z_stream stream;
 703        int status;
 704        unsigned char outbuf[4096];
 705
 706        memset(&stream, 0, sizeof(stream));
 707        deflateInit(&stream, zlib_compression_level);
 708        stream.next_in = in;
 709        stream.avail_in = size;
 710
 711        do {
 712                stream.next_out = outbuf;
 713                stream.avail_out = sizeof(outbuf);
 714                status = deflate(&stream, Z_FINISH);
 715                sha1write(f, outbuf, sizeof(outbuf) - stream.avail_out);
 716        } while (status == Z_OK);
 717
 718        if (status != Z_STREAM_END)
 719                die("unable to deflate appended object (%d)", status);
 720        size = stream.total_out;
 721        deflateEnd(&stream);
 722        return size;
 723}
 724
 725static struct object_entry *append_obj_to_pack(struct sha1file *f,
 726                               const unsigned char *sha1, void *buf,
 727                               unsigned long size, enum object_type type)
 728{
 729        struct object_entry *obj = &objects[nr_objects++];
 730        unsigned char header[10];
 731        unsigned long s = size;
 732        int n = 0;
 733        unsigned char c = (type << 4) | (s & 15);
 734        s >>= 4;
 735        while (s) {
 736                header[n++] = c | 0x80;
 737                c = s & 0x7f;
 738                s >>= 7;
 739        }
 740        header[n++] = c;
 741        crc32_begin(f);
 742        sha1write(f, header, n);
 743        obj[0].size = size;
 744        obj[0].hdr_size = n;
 745        obj[0].type = type;
 746        obj[0].real_type = type;
 747        obj[1].idx.offset = obj[0].idx.offset + n;
 748        obj[1].idx.offset += write_compressed(f, buf, size);
 749        obj[0].idx.crc32 = crc32_end(f);
 750        sha1flush(f);
 751        hashcpy(obj->idx.sha1, sha1);
 752        return obj;
 753}
 754
 755static int delta_pos_compare(const void *_a, const void *_b)
 756{
 757        struct delta_entry *a = *(struct delta_entry **)_a;
 758        struct delta_entry *b = *(struct delta_entry **)_b;
 759        return a->obj_no - b->obj_no;
 760}
 761
 762static void fix_unresolved_deltas(struct sha1file *f, int nr_unresolved)
 763{
 764        struct delta_entry **sorted_by_pos;
 765        int i, n = 0;
 766
 767        /*
 768         * Since many unresolved deltas may well be themselves base objects
 769         * for more unresolved deltas, we really want to include the
 770         * smallest number of base objects that would cover as much delta
 771         * as possible by picking the
 772         * trunc deltas first, allowing for other deltas to resolve without
 773         * additional base objects.  Since most base objects are to be found
 774         * before deltas depending on them, a good heuristic is to start
 775         * resolving deltas in the same order as their position in the pack.
 776         */
 777        sorted_by_pos = xmalloc(nr_unresolved * sizeof(*sorted_by_pos));
 778        for (i = 0; i < nr_deltas; i++) {
 779                if (objects[deltas[i].obj_no].real_type != OBJ_REF_DELTA)
 780                        continue;
 781                sorted_by_pos[n++] = &deltas[i];
 782        }
 783        qsort(sorted_by_pos, n, sizeof(*sorted_by_pos), delta_pos_compare);
 784
 785        for (i = 0; i < n; i++) {
 786                struct delta_entry *d = sorted_by_pos[i];
 787                enum object_type type;
 788                struct base_data base_obj;
 789
 790                if (objects[d->obj_no].real_type != OBJ_REF_DELTA)
 791                        continue;
 792                base_obj.data = read_sha1_file(d->base.sha1, &type, &base_obj.size);
 793                if (!base_obj.data)
 794                        continue;
 795
 796                if (check_sha1_signature(d->base.sha1, base_obj.data,
 797                                base_obj.size, typename(type)))
 798                        die("local object %s is corrupt", sha1_to_hex(d->base.sha1));
 799                base_obj.obj = append_obj_to_pack(f, d->base.sha1,
 800                                        base_obj.data, base_obj.size, type);
 801                find_unresolved_deltas(&base_obj, NULL);
 802                display_progress(progress, nr_resolved_deltas);
 803        }
 804        free(sorted_by_pos);
 805}
 806
 807static void final(const char *final_pack_name, const char *curr_pack_name,
 808                  const char *final_index_name, const char *curr_index_name,
 809                  const char *keep_name, const char *keep_msg,
 810                  unsigned char *sha1)
 811{
 812        const char *report = "pack";
 813        char name[PATH_MAX];
 814        int err;
 815
 816        if (!from_stdin) {
 817                close(input_fd);
 818        } else {
 819                fsync_or_die(output_fd, curr_pack_name);
 820                err = close(output_fd);
 821                if (err)
 822                        die_errno("error while closing pack file");
 823        }
 824
 825        if (keep_msg) {
 826                int keep_fd, keep_msg_len = strlen(keep_msg);
 827
 828                if (!keep_name)
 829                        keep_fd = odb_pack_keep(name, sizeof(name), sha1);
 830                else
 831                        keep_fd = open(keep_name, O_RDWR|O_CREAT|O_EXCL, 0600);
 832
 833                if (keep_fd < 0) {
 834                        if (errno != EEXIST)
 835                                die_errno("cannot write keep file '%s'",
 836                                          keep_name);
 837                } else {
 838                        if (keep_msg_len > 0) {
 839                                write_or_die(keep_fd, keep_msg, keep_msg_len);
 840                                write_or_die(keep_fd, "\n", 1);
 841                        }
 842                        if (close(keep_fd) != 0)
 843                                die_errno("cannot close written keep file '%s'",
 844                                    keep_name);
 845                        report = "keep";
 846                }
 847        }
 848
 849        if (final_pack_name != curr_pack_name) {
 850                if (!final_pack_name) {
 851                        snprintf(name, sizeof(name), "%s/pack/pack-%s.pack",
 852                                 get_object_directory(), sha1_to_hex(sha1));
 853                        final_pack_name = name;
 854                }
 855                if (move_temp_to_file(curr_pack_name, final_pack_name))
 856                        die("cannot store pack file");
 857        } else if (from_stdin)
 858                chmod(final_pack_name, 0444);
 859
 860        if (final_index_name != curr_index_name) {
 861                if (!final_index_name) {
 862                        snprintf(name, sizeof(name), "%s/pack/pack-%s.idx",
 863                                 get_object_directory(), sha1_to_hex(sha1));
 864                        final_index_name = name;
 865                }
 866                if (move_temp_to_file(curr_index_name, final_index_name))
 867                        die("cannot store index file");
 868        } else
 869                chmod(final_index_name, 0444);
 870
 871        if (!from_stdin) {
 872                printf("%s\n", sha1_to_hex(sha1));
 873        } else {
 874                char buf[48];
 875                int len = snprintf(buf, sizeof(buf), "%s\t%s\n",
 876                                   report, sha1_to_hex(sha1));
 877                write_or_die(1, buf, len);
 878
 879                /*
 880                 * Let's just mimic git-unpack-objects here and write
 881                 * the last part of the input buffer to stdout.
 882                 */
 883                while (input_len) {
 884                        err = xwrite(1, input_buffer + input_offset, input_len);
 885                        if (err <= 0)
 886                                break;
 887                        input_len -= err;
 888                        input_offset += err;
 889                }
 890        }
 891}
 892
 893static int git_index_pack_config(const char *k, const char *v, void *cb)
 894{
 895        struct pack_idx_option *opts = cb;
 896
 897        if (!strcmp(k, "pack.indexversion")) {
 898                opts->version = git_config_int(k, v);
 899                if (opts->version > 2)
 900                        die("bad pack.indexversion=%"PRIu32, opts->version);
 901                return 0;
 902        }
 903        return git_default_config(k, v, cb);
 904}
 905
 906static int cmp_uint32(const void *a_, const void *b_)
 907{
 908        uint32_t a = *((uint32_t *)a_);
 909        uint32_t b = *((uint32_t *)b_);
 910
 911        return (a < b) ? -1 : (a != b);
 912}
 913
 914static void read_v2_anomalous_offsets(struct packed_git *p,
 915                                      struct pack_idx_option *opts)
 916{
 917        const uint32_t *idx1, *idx2;
 918        uint32_t i;
 919
 920        /* The address of the 4-byte offset table */
 921        idx1 = (((const uint32_t *)p->index_data)
 922                + 2 /* 8-byte header */
 923                + 256 /* fan out */
 924                + 5 * p->num_objects /* 20-byte SHA-1 table */
 925                + p->num_objects /* CRC32 table */
 926                );
 927
 928        /* The address of the 8-byte offset table */
 929        idx2 = idx1 + p->num_objects;
 930
 931        for (i = 0; i < p->num_objects; i++) {
 932                uint32_t off = ntohl(idx1[i]);
 933                if (!(off & 0x80000000))
 934                        continue;
 935                off = off & 0x7fffffff;
 936                if (idx2[off * 2])
 937                        continue;
 938                /*
 939                 * The real offset is ntohl(idx2[off * 2]) in high 4
 940                 * octets, and ntohl(idx2[off * 2 + 1]) in low 4
 941                 * octets.  But idx2[off * 2] is Zero!!!
 942                 */
 943                ALLOC_GROW(opts->anomaly, opts->anomaly_nr + 1, opts->anomaly_alloc);
 944                opts->anomaly[opts->anomaly_nr++] = ntohl(idx2[off * 2 + 1]);
 945        }
 946
 947        if (1 < opts->anomaly_nr)
 948                qsort(opts->anomaly, opts->anomaly_nr, sizeof(uint32_t), cmp_uint32);
 949}
 950
 951static void read_idx_option(struct pack_idx_option *opts, const char *pack_name)
 952{
 953        struct packed_git *p = add_packed_git(pack_name, strlen(pack_name), 1);
 954
 955        if (!p)
 956                die("Cannot open existing pack file '%s'", pack_name);
 957        if (open_pack_index(p))
 958                die("Cannot open existing pack idx file for '%s'", pack_name);
 959
 960        /* Read the attributes from the existing idx file */
 961        opts->version = p->index_version;
 962
 963        if (opts->version == 2)
 964                read_v2_anomalous_offsets(p, opts);
 965
 966        /*
 967         * Get rid of the idx file as we do not need it anymore.
 968         * NEEDSWORK: extract this bit from free_pack_by_name() in
 969         * sha1_file.c, perhaps?  It shouldn't matter very much as we
 970         * know we haven't installed this pack (hence we never have
 971         * read anything from it).
 972         */
 973        close_pack_index(p);
 974        free(p);
 975}
 976
 977static void show_pack_info(int stat_only)
 978{
 979        int i, baseobjects = nr_objects - nr_deltas;
 980        unsigned long *chain_histogram = NULL;
 981
 982        if (deepest_delta)
 983                chain_histogram = xcalloc(deepest_delta, sizeof(unsigned long));
 984
 985        for (i = 0; i < nr_objects; i++) {
 986                struct object_entry *obj = &objects[i];
 987
 988                if (is_delta_type(obj->type))
 989                        chain_histogram[obj->delta_depth - 1]++;
 990                if (stat_only)
 991                        continue;
 992                printf("%s %-6s %lu %lu %"PRIuMAX,
 993                       sha1_to_hex(obj->idx.sha1),
 994                       typename(obj->real_type), obj->size,
 995                       (unsigned long)(obj[1].idx.offset - obj->idx.offset),
 996                       (uintmax_t)obj->idx.offset);
 997                if (is_delta_type(obj->type)) {
 998                        struct object_entry *bobj = &objects[obj->base_object_no];
 999                        printf(" %u %s", obj->delta_depth, sha1_to_hex(bobj->idx.sha1));
1000                }
1001                putchar('\n');
1002        }
1003
1004        if (baseobjects)
1005                printf("non delta: %d object%s\n",
1006                       baseobjects, baseobjects > 1 ? "s" : "");
1007        for (i = 0; i < deepest_delta; i++) {
1008                if (!chain_histogram[i])
1009                        continue;
1010                printf("chain length = %d: %lu object%s\n",
1011                       i + 1,
1012                       chain_histogram[i],
1013                       chain_histogram[i] > 1 ? "s" : "");
1014        }
1015}
1016
1017int cmd_index_pack(int argc, const char **argv, const char *prefix)
1018{
1019        int i, fix_thin_pack = 0, verify = 0, stat_only = 0, stat = 0;
1020        const char *curr_pack, *curr_index;
1021        const char *index_name = NULL, *pack_name = NULL;
1022        const char *keep_name = NULL, *keep_msg = NULL;
1023        char *index_name_buf = NULL, *keep_name_buf = NULL;
1024        struct pack_idx_entry **idx_objects;
1025        struct pack_idx_option opts;
1026        unsigned char pack_sha1[20];
1027
1028        if (argc == 2 && !strcmp(argv[1], "-h"))
1029                usage(index_pack_usage);
1030
1031        read_replace_refs = 0;
1032
1033        reset_pack_idx_option(&opts);
1034        git_config(git_index_pack_config, &opts);
1035        if (prefix && chdir(prefix))
1036                die("Cannot come back to cwd");
1037
1038        for (i = 1; i < argc; i++) {
1039                const char *arg = argv[i];
1040
1041                if (*arg == '-') {
1042                        if (!strcmp(arg, "--stdin")) {
1043                                from_stdin = 1;
1044                        } else if (!strcmp(arg, "--fix-thin")) {
1045                                fix_thin_pack = 1;
1046                        } else if (!strcmp(arg, "--strict")) {
1047                                strict = 1;
1048                        } else if (!strcmp(arg, "--verify")) {
1049                                verify = 1;
1050                        } else if (!strcmp(arg, "--verify-stat")) {
1051                                verify = 1;
1052                                stat = 1;
1053                        } else if (!strcmp(arg, "--verify-stat-only")) {
1054                                verify = 1;
1055                                stat = 1;
1056                                stat_only = 1;
1057                        } else if (!strcmp(arg, "--keep")) {
1058                                keep_msg = "";
1059                        } else if (!prefixcmp(arg, "--keep=")) {
1060                                keep_msg = arg + 7;
1061                        } else if (!prefixcmp(arg, "--pack_header=")) {
1062                                struct pack_header *hdr;
1063                                char *c;
1064
1065                                hdr = (struct pack_header *)input_buffer;
1066                                hdr->hdr_signature = htonl(PACK_SIGNATURE);
1067                                hdr->hdr_version = htonl(strtoul(arg + 14, &c, 10));
1068                                if (*c != ',')
1069                                        die("bad %s", arg);
1070                                hdr->hdr_entries = htonl(strtoul(c + 1, &c, 10));
1071                                if (*c)
1072                                        die("bad %s", arg);
1073                                input_len = sizeof(*hdr);
1074                        } else if (!strcmp(arg, "-v")) {
1075                                verbose = 1;
1076                        } else if (!strcmp(arg, "-o")) {
1077                                if (index_name || (i+1) >= argc)
1078                                        usage(index_pack_usage);
1079                                index_name = argv[++i];
1080                        } else if (!prefixcmp(arg, "--index-version=")) {
1081                                char *c;
1082                                opts.version = strtoul(arg + 16, &c, 10);
1083                                if (opts.version > 2)
1084                                        die("bad %s", arg);
1085                                if (*c == ',')
1086                                        opts.off32_limit = strtoul(c+1, &c, 0);
1087                                if (*c || opts.off32_limit & 0x80000000)
1088                                        die("bad %s", arg);
1089                        } else
1090                                usage(index_pack_usage);
1091                        continue;
1092                }
1093
1094                if (pack_name)
1095                        usage(index_pack_usage);
1096                pack_name = arg;
1097        }
1098
1099        if (!pack_name && !from_stdin)
1100                usage(index_pack_usage);
1101        if (fix_thin_pack && !from_stdin)
1102                die("--fix-thin cannot be used without --stdin");
1103        if (!index_name && pack_name) {
1104                int len = strlen(pack_name);
1105                if (!has_extension(pack_name, ".pack"))
1106                        die("packfile name '%s' does not end with '.pack'",
1107                            pack_name);
1108                index_name_buf = xmalloc(len);
1109                memcpy(index_name_buf, pack_name, len - 5);
1110                strcpy(index_name_buf + len - 5, ".idx");
1111                index_name = index_name_buf;
1112        }
1113        if (keep_msg && !keep_name && pack_name) {
1114                int len = strlen(pack_name);
1115                if (!has_extension(pack_name, ".pack"))
1116                        die("packfile name '%s' does not end with '.pack'",
1117                            pack_name);
1118                keep_name_buf = xmalloc(len);
1119                memcpy(keep_name_buf, pack_name, len - 5);
1120                strcpy(keep_name_buf + len - 5, ".keep");
1121                keep_name = keep_name_buf;
1122        }
1123        if (verify) {
1124                if (!index_name)
1125                        die("--verify with no packfile name given");
1126                read_idx_option(&opts, index_name);
1127                opts.flags |= WRITE_IDX_VERIFY;
1128        }
1129
1130        curr_pack = open_pack_file(pack_name);
1131        parse_pack_header();
1132        objects = xcalloc(nr_objects + 1, sizeof(struct object_entry));
1133        deltas = xcalloc(nr_objects, sizeof(struct delta_entry));
1134        parse_pack_objects(pack_sha1);
1135        if (nr_deltas == nr_resolved_deltas) {
1136                stop_progress(&progress);
1137                /* Flush remaining pack final 20-byte SHA1. */
1138                flush();
1139        } else {
1140                if (fix_thin_pack) {
1141                        struct sha1file *f;
1142                        unsigned char read_sha1[20], tail_sha1[20];
1143                        char msg[48];
1144                        int nr_unresolved = nr_deltas - nr_resolved_deltas;
1145                        int nr_objects_initial = nr_objects;
1146                        if (nr_unresolved <= 0)
1147                                die("confusion beyond insanity");
1148                        objects = xrealloc(objects,
1149                                           (nr_objects + nr_unresolved + 1)
1150                                           * sizeof(*objects));
1151                        f = sha1fd(output_fd, curr_pack);
1152                        fix_unresolved_deltas(f, nr_unresolved);
1153                        sprintf(msg, "completed with %d local objects",
1154                                nr_objects - nr_objects_initial);
1155                        stop_progress_msg(&progress, msg);
1156                        sha1close(f, tail_sha1, 0);
1157                        hashcpy(read_sha1, pack_sha1);
1158                        fixup_pack_header_footer(output_fd, pack_sha1,
1159                                                 curr_pack, nr_objects,
1160                                                 read_sha1, consumed_bytes-20);
1161                        if (hashcmp(read_sha1, tail_sha1) != 0)
1162                                die("Unexpected tail checksum for %s "
1163                                    "(disk corruption?)", curr_pack);
1164                }
1165                if (nr_deltas != nr_resolved_deltas)
1166                        die("pack has %d unresolved deltas",
1167                            nr_deltas - nr_resolved_deltas);
1168        }
1169        free(deltas);
1170        if (strict)
1171                check_objects();
1172
1173        if (stat)
1174                show_pack_info(stat_only);
1175
1176        idx_objects = xmalloc((nr_objects) * sizeof(struct pack_idx_entry *));
1177        for (i = 0; i < nr_objects; i++)
1178                idx_objects[i] = &objects[i].idx;
1179        curr_index = write_idx_file(index_name, idx_objects, nr_objects, &opts, pack_sha1);
1180        free(idx_objects);
1181
1182        if (!verify)
1183                final(pack_name, curr_pack,
1184                      index_name, curr_index,
1185                      keep_name, keep_msg,
1186                      pack_sha1);
1187        else
1188                close(input_fd);
1189        free(objects);
1190        free(index_name_buf);
1191        free(keep_name_buf);
1192        if (pack_name == NULL)
1193                free((void *) curr_pack);
1194        if (index_name == NULL)
1195                free((void *) curr_index);
1196
1197        return 0;
1198}