3023aace4d8725374f935dd92b63aa34154dc191
   1#include "builtin.h"
   2#include "cache.h"
   3#include "object.h"
   4#include "blob.h"
   5#include "commit.h"
   6#include "tag.h"
   7#include "tree.h"
   8#include "delta.h"
   9#include "pack.h"
  10#include "csum-file.h"
  11#include "tree-walk.h"
  12#include "diff.h"
  13#include "revision.h"
  14#include "list-objects.h"
  15#include "progress.h"
  16
  17static const char pack_usage[] = "\
  18git-pack-objects [{ -q | --progress | --all-progress }] \n\
  19        [--local] [--incremental] [--window=N] [--depth=N] \n\
  20        [--no-reuse-delta] [--no-reuse-object] [--delta-base-offset] \n\
  21        [--non-empty] [--revs [--unpacked | --all]*] [--reflog] \n\
  22        [--stdout | base-name] [<ref-list | <object-list]";
  23
  24struct object_entry {
  25        unsigned char sha1[20];
  26        uint32_t crc32;         /* crc of raw pack data for this object */
  27        off_t offset;           /* offset into the final pack file */
  28        unsigned long size;     /* uncompressed size */
  29        unsigned int hash;      /* name hint hash */
  30        unsigned int depth;     /* delta depth */
  31        struct packed_git *in_pack;     /* already in pack */
  32        off_t in_pack_offset;
  33        struct object_entry *delta;     /* delta base object */
  34        struct object_entry *delta_child; /* deltified objects who bases me */
  35        struct object_entry *delta_sibling; /* other deltified objects who
  36                                             * uses the same base as me
  37                                             */
  38        unsigned long delta_size;       /* delta data size (uncompressed) */
  39        enum object_type type;
  40        enum object_type in_pack_type;  /* could be delta */
  41        unsigned char in_pack_header_size;
  42        unsigned char preferred_base; /* we do not pack this, but is available
  43                                       * to be used as the base objectto delta
  44                                       * objects against.
  45                                       */
  46};
  47
  48/*
  49 * Objects we are going to pack are collected in objects array (dynamically
  50 * expanded).  nr_objects & nr_alloc controls this array.  They are stored
  51 * in the order we see -- typically rev-list --objects order that gives us
  52 * nice "minimum seek" order.
  53 */
  54static struct object_entry *objects;
  55static struct object_entry **written_list;
  56static uint32_t nr_objects, nr_alloc, nr_result, nr_written;
  57
  58static int non_empty;
  59static int no_reuse_delta, no_reuse_object;
  60static int local;
  61static int incremental;
  62static int allow_ofs_delta;
  63static const char *pack_tmp_name, *idx_tmp_name;
  64static char tmpname[PATH_MAX];
  65static const char *base_name;
  66static unsigned char pack_file_sha1[20];
  67static int progress = 1;
  68static int window = 10;
  69static uint32_t pack_size_limit;
  70static int depth = 50;
  71static int pack_to_stdout;
  72static int num_preferred_base;
  73static struct progress progress_state;
  74static int pack_compression_level = Z_DEFAULT_COMPRESSION;
  75static int pack_compression_seen;
  76
  77/*
  78 * The object names in objects array are hashed with this hashtable,
  79 * to help looking up the entry by object name.
  80 * This hashtable is built after all the objects are seen.
  81 */
  82static int *object_ix;
  83static int object_ix_hashsz;
  84
  85/*
  86 * Pack index for existing packs give us easy access to the offsets into
  87 * corresponding pack file where each object's data starts, but the entries
  88 * do not store the size of the compressed representation (uncompressed
  89 * size is easily available by examining the pack entry header).  It is
  90 * also rather expensive to find the sha1 for an object given its offset.
  91 *
  92 * We build a hashtable of existing packs (pack_revindex), and keep reverse
  93 * index here -- pack index file is sorted by object name mapping to offset;
  94 * this pack_revindex[].revindex array is a list of offset/index_nr pairs
  95 * ordered by offset, so if you know the offset of an object, next offset
  96 * is where its packed representation ends and the index_nr can be used to
  97 * get the object sha1 from the main index.
  98 */
  99struct revindex_entry {
 100        off_t offset;
 101        unsigned int nr;
 102};
 103struct pack_revindex {
 104        struct packed_git *p;
 105        struct revindex_entry *revindex;
 106};
 107static struct  pack_revindex *pack_revindex;
 108static int pack_revindex_hashsz;
 109
 110/*
 111 * stats
 112 */
 113static uint32_t written, written_delta;
 114static uint32_t reused, reused_delta;
 115
 116static int pack_revindex_ix(struct packed_git *p)
 117{
 118        unsigned long ui = (unsigned long)p;
 119        int i;
 120
 121        ui = ui ^ (ui >> 16); /* defeat structure alignment */
 122        i = (int)(ui % pack_revindex_hashsz);
 123        while (pack_revindex[i].p) {
 124                if (pack_revindex[i].p == p)
 125                        return i;
 126                if (++i == pack_revindex_hashsz)
 127                        i = 0;
 128        }
 129        return -1 - i;
 130}
 131
 132static void prepare_pack_ix(void)
 133{
 134        int num;
 135        struct packed_git *p;
 136        for (num = 0, p = packed_git; p; p = p->next)
 137                num++;
 138        if (!num)
 139                return;
 140        pack_revindex_hashsz = num * 11;
 141        pack_revindex = xcalloc(sizeof(*pack_revindex), pack_revindex_hashsz);
 142        for (p = packed_git; p; p = p->next) {
 143                num = pack_revindex_ix(p);
 144                num = - 1 - num;
 145                pack_revindex[num].p = p;
 146        }
 147        /* revindex elements are lazily initialized */
 148}
 149
 150static int cmp_offset(const void *a_, const void *b_)
 151{
 152        const struct revindex_entry *a = a_;
 153        const struct revindex_entry *b = b_;
 154        return (a->offset < b->offset) ? -1 : (a->offset > b->offset) ? 1 : 0;
 155}
 156
 157/*
 158 * Ordered list of offsets of objects in the pack.
 159 */
 160static void prepare_pack_revindex(struct pack_revindex *rix)
 161{
 162        struct packed_git *p = rix->p;
 163        int num_ent = p->num_objects;
 164        int i;
 165        const char *index = p->index_data;
 166
 167        rix->revindex = xmalloc(sizeof(*rix->revindex) * (num_ent + 1));
 168        index += 4 * 256;
 169
 170        if (p->index_version > 1) {
 171                const uint32_t *off_32 =
 172                        (uint32_t *)(index + 8 + p->num_objects * (20 + 4));
 173                const uint32_t *off_64 = off_32 + p->num_objects;
 174                for (i = 0; i < num_ent; i++) {
 175                        uint32_t off = ntohl(*off_32++);
 176                        if (!(off & 0x80000000)) {
 177                                rix->revindex[i].offset = off;
 178                        } else {
 179                                rix->revindex[i].offset =
 180                                        ((uint64_t)ntohl(*off_64++)) << 32;
 181                                rix->revindex[i].offset |=
 182                                        ntohl(*off_64++);
 183                        }
 184                        rix->revindex[i].nr = i;
 185                }
 186        } else {
 187                for (i = 0; i < num_ent; i++) {
 188                        uint32_t hl = *((uint32_t *)(index + 24 * i));
 189                        rix->revindex[i].offset = ntohl(hl);
 190                        rix->revindex[i].nr = i;
 191                }
 192        }
 193
 194        /* This knows the pack format -- the 20-byte trailer
 195         * follows immediately after the last object data.
 196         */
 197        rix->revindex[num_ent].offset = p->pack_size - 20;
 198        rix->revindex[num_ent].nr = -1;
 199        qsort(rix->revindex, num_ent, sizeof(*rix->revindex), cmp_offset);
 200}
 201
 202static struct revindex_entry * find_packed_object(struct packed_git *p,
 203                                                  off_t ofs)
 204{
 205        int num;
 206        int lo, hi;
 207        struct pack_revindex *rix;
 208        struct revindex_entry *revindex;
 209        num = pack_revindex_ix(p);
 210        if (num < 0)
 211                die("internal error: pack revindex uninitialized");
 212        rix = &pack_revindex[num];
 213        if (!rix->revindex)
 214                prepare_pack_revindex(rix);
 215        revindex = rix->revindex;
 216        lo = 0;
 217        hi = p->num_objects + 1;
 218        do {
 219                int mi = (lo + hi) / 2;
 220                if (revindex[mi].offset == ofs) {
 221                        return revindex + mi;
 222                }
 223                else if (ofs < revindex[mi].offset)
 224                        hi = mi;
 225                else
 226                        lo = mi + 1;
 227        } while (lo < hi);
 228        die("internal error: pack revindex corrupt");
 229}
 230
 231static const unsigned char *find_packed_object_name(struct packed_git *p,
 232                                                    off_t ofs)
 233{
 234        struct revindex_entry *entry = find_packed_object(p, ofs);
 235        return nth_packed_object_sha1(p, entry->nr);
 236}
 237
 238static void *delta_against(void *buf, unsigned long size, struct object_entry *entry)
 239{
 240        unsigned long othersize, delta_size;
 241        enum object_type type;
 242        void *otherbuf = read_sha1_file(entry->delta->sha1, &type, &othersize);
 243        void *delta_buf;
 244
 245        if (!otherbuf)
 246                die("unable to read %s", sha1_to_hex(entry->delta->sha1));
 247        delta_buf = diff_delta(otherbuf, othersize,
 248                               buf, size, &delta_size, 0);
 249        if (!delta_buf || delta_size != entry->delta_size)
 250                die("delta size changed");
 251        free(buf);
 252        free(otherbuf);
 253        return delta_buf;
 254}
 255
 256/*
 257 * The per-object header is a pretty dense thing, which is
 258 *  - first byte: low four bits are "size", then three bits of "type",
 259 *    and the high bit is "size continues".
 260 *  - each byte afterwards: low seven bits are size continuation,
 261 *    with the high bit being "size continues"
 262 */
 263static int encode_header(enum object_type type, unsigned long size, unsigned char *hdr)
 264{
 265        int n = 1;
 266        unsigned char c;
 267
 268        if (type < OBJ_COMMIT || type > OBJ_REF_DELTA)
 269                die("bad type %d", type);
 270
 271        c = (type << 4) | (size & 15);
 272        size >>= 4;
 273        while (size) {
 274                *hdr++ = c | 0x80;
 275                c = size & 0x7f;
 276                size >>= 7;
 277                n++;
 278        }
 279        *hdr = c;
 280        return n;
 281}
 282
 283/*
 284 * we are going to reuse the existing object data as is.  make
 285 * sure it is not corrupt.
 286 */
 287static int check_pack_inflate(struct packed_git *p,
 288                struct pack_window **w_curs,
 289                off_t offset,
 290                off_t len,
 291                unsigned long expect)
 292{
 293        z_stream stream;
 294        unsigned char fakebuf[4096], *in;
 295        int st;
 296
 297        memset(&stream, 0, sizeof(stream));
 298        inflateInit(&stream);
 299        do {
 300                in = use_pack(p, w_curs, offset, &stream.avail_in);
 301                stream.next_in = in;
 302                stream.next_out = fakebuf;
 303                stream.avail_out = sizeof(fakebuf);
 304                st = inflate(&stream, Z_FINISH);
 305                offset += stream.next_in - in;
 306        } while (st == Z_OK || st == Z_BUF_ERROR);
 307        inflateEnd(&stream);
 308        return (st == Z_STREAM_END &&
 309                stream.total_out == expect &&
 310                stream.total_in == len) ? 0 : -1;
 311}
 312
 313static int check_pack_crc(struct packed_git *p, struct pack_window **w_curs,
 314                          off_t offset, off_t len, unsigned int nr)
 315{
 316        const uint32_t *index_crc;
 317        uint32_t data_crc = crc32(0, Z_NULL, 0);
 318
 319        do {
 320                unsigned int avail;
 321                void *data = use_pack(p, w_curs, offset, &avail);
 322                if (avail > len)
 323                        avail = len;
 324                data_crc = crc32(data_crc, data, avail);
 325                offset += avail;
 326                len -= avail;
 327        } while (len);
 328
 329        index_crc = p->index_data;
 330        index_crc += 2 + 256 + p->num_objects * (20/4) + nr;
 331
 332        return data_crc != ntohl(*index_crc);
 333}
 334
 335static void copy_pack_data(struct sha1file *f,
 336                struct packed_git *p,
 337                struct pack_window **w_curs,
 338                off_t offset,
 339                off_t len)
 340{
 341        unsigned char *in;
 342        unsigned int avail;
 343
 344        while (len) {
 345                in = use_pack(p, w_curs, offset, &avail);
 346                if (avail > len)
 347                        avail = (unsigned int)len;
 348                sha1write(f, in, avail);
 349                offset += avail;
 350                len -= avail;
 351        }
 352}
 353
 354static unsigned long write_object(struct sha1file *f,
 355                                  struct object_entry *entry,
 356                                  off_t write_offset)
 357{
 358        unsigned long size;
 359        enum object_type type;
 360        void *buf;
 361        unsigned char header[10];
 362        unsigned char dheader[10];
 363        unsigned hdrlen;
 364        off_t datalen;
 365        enum object_type obj_type;
 366        int to_reuse = 0;
 367        /* write limit if limited packsize and not first object */
 368        unsigned long limit = pack_size_limit && nr_written ?
 369                                pack_size_limit - write_offset : 0;
 370                                /* no if no delta */
 371        int usable_delta =      !entry->delta ? 0 :
 372                                /* yes if unlimited packfile */
 373                                !pack_size_limit ? 1 :
 374                                /* no if base written to previous pack */
 375                                entry->delta->offset == (off_t)-1 ? 0 :
 376                                /* otherwise double-check written to this
 377                                 * pack,  like we do below
 378                                 */
 379                                entry->delta->offset ? 1 : 0;
 380
 381        if (!pack_to_stdout)
 382                crc32_begin(f);
 383
 384        obj_type = entry->type;
 385        if (no_reuse_object)
 386                to_reuse = 0;   /* explicit */
 387        else if (!entry->in_pack)
 388                to_reuse = 0;   /* can't reuse what we don't have */
 389        else if (obj_type == OBJ_REF_DELTA || obj_type == OBJ_OFS_DELTA)
 390                                /* check_object() decided it for us ... */
 391                to_reuse = usable_delta;
 392                                /* ... but pack split may override that */
 393        else if (obj_type != entry->in_pack_type)
 394                to_reuse = 0;   /* pack has delta which is unusable */
 395        else if (entry->delta)
 396                to_reuse = 0;   /* we want to pack afresh */
 397        else
 398                to_reuse = 1;   /* we have it in-pack undeltified,
 399                                 * and we do not need to deltify it.
 400                                 */
 401
 402        if (!to_reuse) {
 403                z_stream stream;
 404                unsigned long maxsize;
 405                void *out;
 406                buf = read_sha1_file(entry->sha1, &type, &size);
 407                if (!buf)
 408                        die("unable to read %s", sha1_to_hex(entry->sha1));
 409                if (size != entry->size)
 410                        die("object %s size inconsistency (%lu vs %lu)",
 411                            sha1_to_hex(entry->sha1), size, entry->size);
 412                if (usable_delta) {
 413                        buf = delta_against(buf, size, entry);
 414                        size = entry->delta_size;
 415                        obj_type = (allow_ofs_delta && entry->delta->offset) ?
 416                                OBJ_OFS_DELTA : OBJ_REF_DELTA;
 417                } else {
 418                        /*
 419                         * recover real object type in case
 420                         * check_object() wanted to re-use a delta,
 421                         * but we couldn't since base was in previous split pack
 422                         */
 423                        obj_type = type;
 424                }
 425                /* compress the data to store and put compressed length in datalen */
 426                memset(&stream, 0, sizeof(stream));
 427                deflateInit(&stream, pack_compression_level);
 428                maxsize = deflateBound(&stream, size);
 429                out = xmalloc(maxsize);
 430                /* Compress it */
 431                stream.next_in = buf;
 432                stream.avail_in = size;
 433                stream.next_out = out;
 434                stream.avail_out = maxsize;
 435                while (deflate(&stream, Z_FINISH) == Z_OK)
 436                        /* nothing */;
 437                deflateEnd(&stream);
 438                datalen = stream.total_out;
 439                deflateEnd(&stream);
 440                /*
 441                 * The object header is a byte of 'type' followed by zero or
 442                 * more bytes of length.
 443                 */
 444                hdrlen = encode_header(obj_type, size, header);
 445
 446                if (obj_type == OBJ_OFS_DELTA) {
 447                        /*
 448                         * Deltas with relative base contain an additional
 449                         * encoding of the relative offset for the delta
 450                         * base from this object's position in the pack.
 451                         */
 452                        off_t ofs = entry->offset - entry->delta->offset;
 453                        unsigned pos = sizeof(dheader) - 1;
 454                        dheader[pos] = ofs & 127;
 455                        while (ofs >>= 7)
 456                                dheader[--pos] = 128 | (--ofs & 127);
 457                        if (limit && hdrlen + sizeof(dheader) - pos + datalen + 20 >= limit) {
 458                                free(out);
 459                                free(buf);
 460                                return 0;
 461                        }
 462                        sha1write(f, header, hdrlen);
 463                        sha1write(f, dheader + pos, sizeof(dheader) - pos);
 464                        hdrlen += sizeof(dheader) - pos;
 465                } else if (obj_type == OBJ_REF_DELTA) {
 466                        /*
 467                         * Deltas with a base reference contain
 468                         * an additional 20 bytes for the base sha1.
 469                         */
 470                        if (limit && hdrlen + 20 + datalen + 20 >= limit) {
 471                                free(out);
 472                                free(buf);
 473                                return 0;
 474                        }
 475                        sha1write(f, header, hdrlen);
 476                        sha1write(f, entry->delta->sha1, 20);
 477                        hdrlen += 20;
 478                } else {
 479                        if (limit && hdrlen + datalen + 20 >= limit) {
 480                                free(out);
 481                                free(buf);
 482                                return 0;
 483                        }
 484                        sha1write(f, header, hdrlen);
 485                }
 486                sha1write(f, out, datalen);
 487                free(out);
 488                free(buf);
 489        }
 490        else {
 491                struct packed_git *p = entry->in_pack;
 492                struct pack_window *w_curs = NULL;
 493                struct revindex_entry *revidx;
 494                off_t offset;
 495
 496                if (entry->delta) {
 497                        obj_type = (allow_ofs_delta && entry->delta->offset) ?
 498                                OBJ_OFS_DELTA : OBJ_REF_DELTA;
 499                        reused_delta++;
 500                }
 501                hdrlen = encode_header(obj_type, entry->size, header);
 502                offset = entry->in_pack_offset;
 503                revidx = find_packed_object(p, offset);
 504                datalen = revidx[1].offset - offset;
 505                if (!pack_to_stdout && p->index_version > 1 &&
 506                    check_pack_crc(p, &w_curs, offset, datalen, revidx->nr))
 507                        die("bad packed object CRC for %s", sha1_to_hex(entry->sha1));
 508                offset += entry->in_pack_header_size;
 509                datalen -= entry->in_pack_header_size;
 510                if (obj_type == OBJ_OFS_DELTA) {
 511                        off_t ofs = entry->offset - entry->delta->offset;
 512                        unsigned pos = sizeof(dheader) - 1;
 513                        dheader[pos] = ofs & 127;
 514                        while (ofs >>= 7)
 515                                dheader[--pos] = 128 | (--ofs & 127);
 516                        if (limit && hdrlen + sizeof(dheader) - pos + datalen + 20 >= limit)
 517                                return 0;
 518                        sha1write(f, header, hdrlen);
 519                        sha1write(f, dheader + pos, sizeof(dheader) - pos);
 520                        hdrlen += sizeof(dheader) - pos;
 521                } else if (obj_type == OBJ_REF_DELTA) {
 522                        if (limit && hdrlen + 20 + datalen + 20 >= limit)
 523                                return 0;
 524                        sha1write(f, header, hdrlen);
 525                        sha1write(f, entry->delta->sha1, 20);
 526                        hdrlen += 20;
 527                } else {
 528                        if (limit && hdrlen + datalen + 20 >= limit)
 529                                return 0;
 530                        sha1write(f, header, hdrlen);
 531                }
 532
 533                if (!pack_to_stdout && p->index_version == 1 &&
 534                    check_pack_inflate(p, &w_curs, offset, datalen, entry->size))
 535                        die("corrupt packed object for %s", sha1_to_hex(entry->sha1));
 536                copy_pack_data(f, p, &w_curs, offset, datalen);
 537                unuse_pack(&w_curs);
 538                reused++;
 539        }
 540        if (usable_delta)
 541                written_delta++;
 542        written++;
 543        if (!pack_to_stdout)
 544                entry->crc32 = crc32_end(f);
 545        return hdrlen + datalen;
 546}
 547
 548static off_t write_one(struct sha1file *f,
 549                               struct object_entry *e,
 550                               off_t offset)
 551{
 552        unsigned long size;
 553
 554        /* offset is non zero if object is written already. */
 555        if (e->offset || e->preferred_base)
 556                return offset;
 557
 558        /* if we are deltified, write out base object first. */
 559        if (e->delta) {
 560                offset = write_one(f, e->delta, offset);
 561                if (!offset)
 562                        return 0;
 563        }
 564
 565        e->offset = offset;
 566        size = write_object(f, e, offset);
 567        if (!size) {
 568                e->offset = 0;
 569                return 0;
 570        }
 571
 572        /* make sure off_t is sufficiently large not to wrap */
 573        if (offset > offset + size)
 574                die("pack too large for current definition of off_t");
 575        return offset + size;
 576}
 577
 578static int open_object_dir_tmp(const char *path)
 579{
 580    snprintf(tmpname, sizeof(tmpname), "%s/%s", get_object_directory(), path);
 581    return mkstemp(tmpname);
 582}
 583
 584/* forward declarations for write_pack_file */
 585static void write_index_file(off_t last_obj_offset, unsigned char *sha1);
 586static int adjust_perm(const char *path, mode_t mode);
 587
 588static void write_pack_file(void)
 589{
 590        uint32_t i;
 591        struct sha1file *f;
 592        off_t offset, last_obj_offset = 0;
 593        struct pack_header hdr;
 594        int do_progress = progress;
 595
 596        if (pack_to_stdout) {
 597                f = sha1fd(1, "<stdout>");
 598                do_progress >>= 1;
 599        } else {
 600                int fd = open_object_dir_tmp("tmp_pack_XXXXXX");
 601                if (fd < 0)
 602                        die("unable to create %s: %s\n", tmpname, strerror(errno));
 603                pack_tmp_name = xstrdup(tmpname);
 604                f = sha1fd(fd, pack_tmp_name);
 605        }
 606
 607        if (do_progress)
 608                start_progress(&progress_state, "Writing %u objects...", "", nr_result);
 609
 610        hdr.hdr_signature = htonl(PACK_SIGNATURE);
 611        hdr.hdr_version = htonl(PACK_VERSION);
 612        hdr.hdr_entries = htonl(nr_result);
 613        sha1write(f, &hdr, sizeof(hdr));
 614        offset = sizeof(hdr);
 615        if (!nr_result)
 616                goto done;
 617        for (i = 0; i < nr_objects; i++) {
 618                last_obj_offset = offset;
 619                offset = write_one(f, objects + i, offset);
 620                if (do_progress)
 621                        display_progress(&progress_state, written);
 622        }
 623        if (do_progress)
 624                stop_progress(&progress_state);
 625 done:
 626        if (written != nr_result)
 627                die("wrote %u objects while expecting %u", written, nr_result);
 628        sha1close(f, pack_file_sha1, 1);
 629
 630        if (!pack_to_stdout) {
 631                        unsigned char object_list_sha1[20];
 632                        mode_t mode = umask(0);
 633
 634                        umask(mode);
 635                        mode = 0444 & ~mode;
 636
 637                        write_index_file(last_obj_offset, object_list_sha1);
 638                        snprintf(tmpname, sizeof(tmpname), "%s-%s.pack",
 639                                 base_name, sha1_to_hex(object_list_sha1));
 640                        if (adjust_perm(pack_tmp_name, mode))
 641                                die("unable to make temporary pack file readable: %s",
 642                                    strerror(errno));
 643                        if (rename(pack_tmp_name, tmpname))
 644                                die("unable to rename temporary pack file: %s",
 645                                    strerror(errno));
 646                        snprintf(tmpname, sizeof(tmpname), "%s-%s.idx",
 647                                 base_name, sha1_to_hex(object_list_sha1));
 648                        if (adjust_perm(idx_tmp_name, mode))
 649                                die("unable to make temporary index file readable: %s",
 650                                    strerror(errno));
 651                        if (rename(idx_tmp_name, tmpname))
 652                                die("unable to rename temporary index file: %s",
 653                                    strerror(errno));
 654                        puts(sha1_to_hex(object_list_sha1));
 655        }
 656}
 657
 658static int sha1_sort(const void *_a, const void *_b)
 659{
 660        const struct object_entry *a = *(struct object_entry **)_a;
 661        const struct object_entry *b = *(struct object_entry **)_b;
 662        return hashcmp(a->sha1, b->sha1);
 663}
 664
 665static uint32_t index_default_version = 1;
 666static uint32_t index_off32_limit = 0x7fffffff;
 667
 668static void write_index_file(off_t last_obj_offset, unsigned char *sha1)
 669{
 670        struct sha1file *f;
 671        struct object_entry **sorted_by_sha, **list, **last;
 672        uint32_t array[256];
 673        uint32_t i, index_version;
 674        SHA_CTX ctx;
 675
 676        int fd = open_object_dir_tmp("tmp_idx_XXXXXX");
 677        if (fd < 0)
 678                die("unable to create %s: %s\n", tmpname, strerror(errno));
 679        idx_tmp_name = xstrdup(tmpname);
 680        f = sha1fd(fd, idx_tmp_name);
 681
 682        if (nr_result) {
 683                uint32_t j = 0;
 684                sorted_by_sha =
 685                        xcalloc(nr_result, sizeof(struct object_entry *));
 686                for (i = 0; i < nr_objects; i++)
 687                        if (!objects[i].preferred_base)
 688                                sorted_by_sha[j++] = objects + i;
 689                if (j != nr_result)
 690                        die("listed %u objects while expecting %u", j, nr_result);
 691                qsort(sorted_by_sha, nr_result, sizeof(*sorted_by_sha), sha1_sort);
 692                list = sorted_by_sha;
 693                last = sorted_by_sha + nr_result;
 694        } else
 695                sorted_by_sha = list = last = NULL;
 696
 697        /* if last object's offset is >= 2^31 we should use index V2 */
 698        index_version = (last_obj_offset >> 31) ? 2 : index_default_version;
 699
 700        /* index versions 2 and above need a header */
 701        if (index_version >= 2) {
 702                struct pack_idx_header hdr;
 703                hdr.idx_signature = htonl(PACK_IDX_SIGNATURE);
 704                hdr.idx_version = htonl(index_version);
 705                sha1write(f, &hdr, sizeof(hdr));
 706        }
 707
 708        /*
 709         * Write the first-level table (the list is sorted,
 710         * but we use a 256-entry lookup to be able to avoid
 711         * having to do eight extra binary search iterations).
 712         */
 713        for (i = 0; i < 256; i++) {
 714                struct object_entry **next = list;
 715                while (next < last) {
 716                        struct object_entry *entry = *next;
 717                        if (entry->sha1[0] != i)
 718                                break;
 719                        next++;
 720                }
 721                array[i] = htonl(next - sorted_by_sha);
 722                list = next;
 723        }
 724        sha1write(f, array, 256 * 4);
 725
 726        /* Compute the SHA1 hash of sorted object names. */
 727        SHA1_Init(&ctx);
 728
 729        /* Write the actual SHA1 entries. */
 730        list = sorted_by_sha;
 731        for (i = 0; i < nr_result; i++) {
 732                struct object_entry *entry = *list++;
 733                if (index_version < 2) {
 734                        uint32_t offset = htonl(entry->offset);
 735                        sha1write(f, &offset, 4);
 736                }
 737                sha1write(f, entry->sha1, 20);
 738                SHA1_Update(&ctx, entry->sha1, 20);
 739        }
 740
 741        if (index_version >= 2) {
 742                unsigned int nr_large_offset = 0;
 743
 744                /* write the crc32 table */
 745                list = sorted_by_sha;
 746                for (i = 0; i < nr_objects; i++) {
 747                        struct object_entry *entry = *list++;
 748                        uint32_t crc32_val = htonl(entry->crc32);
 749                        sha1write(f, &crc32_val, 4);
 750                }
 751
 752                /* write the 32-bit offset table */
 753                list = sorted_by_sha;
 754                for (i = 0; i < nr_objects; i++) {
 755                        struct object_entry *entry = *list++;
 756                        uint32_t offset = (entry->offset <= index_off32_limit) ?
 757                                entry->offset : (0x80000000 | nr_large_offset++);
 758                        offset = htonl(offset);
 759                        sha1write(f, &offset, 4);
 760                }
 761
 762                /* write the large offset table */
 763                list = sorted_by_sha;
 764                while (nr_large_offset) {
 765                        struct object_entry *entry = *list++;
 766                        uint64_t offset = entry->offset;
 767                        if (offset > index_off32_limit) {
 768                                uint32_t split[2];
 769                                split[0]        = htonl(offset >> 32);
 770                                split[1] = htonl(offset & 0xffffffff);
 771                                sha1write(f, split, 8);
 772                                nr_large_offset--;
 773                        }
 774                }
 775        }
 776
 777        sha1write(f, pack_file_sha1, 20);
 778        sha1close(f, NULL, 1);
 779        free(sorted_by_sha);
 780        SHA1_Final(sha1, &ctx);
 781}
 782
 783static int locate_object_entry_hash(const unsigned char *sha1)
 784{
 785        int i;
 786        unsigned int ui;
 787        memcpy(&ui, sha1, sizeof(unsigned int));
 788        i = ui % object_ix_hashsz;
 789        while (0 < object_ix[i]) {
 790                if (!hashcmp(sha1, objects[object_ix[i] - 1].sha1))
 791                        return i;
 792                if (++i == object_ix_hashsz)
 793                        i = 0;
 794        }
 795        return -1 - i;
 796}
 797
 798static struct object_entry *locate_object_entry(const unsigned char *sha1)
 799{
 800        int i;
 801
 802        if (!object_ix_hashsz)
 803                return NULL;
 804
 805        i = locate_object_entry_hash(sha1);
 806        if (0 <= i)
 807                return &objects[object_ix[i]-1];
 808        return NULL;
 809}
 810
 811static void rehash_objects(void)
 812{
 813        uint32_t i;
 814        struct object_entry *oe;
 815
 816        object_ix_hashsz = nr_objects * 3;
 817        if (object_ix_hashsz < 1024)
 818                object_ix_hashsz = 1024;
 819        object_ix = xrealloc(object_ix, sizeof(int) * object_ix_hashsz);
 820        memset(object_ix, 0, sizeof(int) * object_ix_hashsz);
 821        for (i = 0, oe = objects; i < nr_objects; i++, oe++) {
 822                int ix = locate_object_entry_hash(oe->sha1);
 823                if (0 <= ix)
 824                        continue;
 825                ix = -1 - ix;
 826                object_ix[ix] = i + 1;
 827        }
 828}
 829
 830static unsigned name_hash(const char *name)
 831{
 832        unsigned char c;
 833        unsigned hash = 0;
 834
 835        /*
 836         * This effectively just creates a sortable number from the
 837         * last sixteen non-whitespace characters. Last characters
 838         * count "most", so things that end in ".c" sort together.
 839         */
 840        while ((c = *name++) != 0) {
 841                if (isspace(c))
 842                        continue;
 843                hash = (hash >> 2) + (c << 24);
 844        }
 845        return hash;
 846}
 847
 848static int add_object_entry(const unsigned char *sha1, enum object_type type,
 849                            unsigned hash, int exclude)
 850{
 851        struct object_entry *entry;
 852        struct packed_git *p, *found_pack = NULL;
 853        off_t found_offset = 0;
 854        int ix;
 855
 856        ix = nr_objects ? locate_object_entry_hash(sha1) : -1;
 857        if (ix >= 0) {
 858                if (exclude) {
 859                        entry = objects + object_ix[ix] - 1;
 860                        if (!entry->preferred_base)
 861                                nr_result--;
 862                        entry->preferred_base = 1;
 863                }
 864                return 0;
 865        }
 866
 867        for (p = packed_git; p; p = p->next) {
 868                off_t offset = find_pack_entry_one(sha1, p);
 869                if (offset) {
 870                        if (!found_pack) {
 871                                found_offset = offset;
 872                                found_pack = p;
 873                        }
 874                        if (exclude)
 875                                break;
 876                        if (incremental)
 877                                return 0;
 878                        if (local && !p->pack_local)
 879                                return 0;
 880                }
 881        }
 882
 883        if (nr_objects >= nr_alloc) {
 884                nr_alloc = (nr_alloc  + 1024) * 3 / 2;
 885                objects = xrealloc(objects, nr_alloc * sizeof(*entry));
 886        }
 887
 888        entry = objects + nr_objects++;
 889        memset(entry, 0, sizeof(*entry));
 890        hashcpy(entry->sha1, sha1);
 891        entry->hash = hash;
 892        if (type)
 893                entry->type = type;
 894        if (exclude)
 895                entry->preferred_base = 1;
 896        else
 897                nr_result++;
 898        if (found_pack) {
 899                entry->in_pack = found_pack;
 900                entry->in_pack_offset = found_offset;
 901        }
 902
 903        if (object_ix_hashsz * 3 <= nr_objects * 4)
 904                rehash_objects();
 905        else
 906                object_ix[-1 - ix] = nr_objects;
 907
 908        if (progress)
 909                display_progress(&progress_state, nr_objects);
 910
 911        return 1;
 912}
 913
 914struct pbase_tree_cache {
 915        unsigned char sha1[20];
 916        int ref;
 917        int temporary;
 918        void *tree_data;
 919        unsigned long tree_size;
 920};
 921
 922static struct pbase_tree_cache *(pbase_tree_cache[256]);
 923static int pbase_tree_cache_ix(const unsigned char *sha1)
 924{
 925        return sha1[0] % ARRAY_SIZE(pbase_tree_cache);
 926}
 927static int pbase_tree_cache_ix_incr(int ix)
 928{
 929        return (ix+1) % ARRAY_SIZE(pbase_tree_cache);
 930}
 931
 932static struct pbase_tree {
 933        struct pbase_tree *next;
 934        /* This is a phony "cache" entry; we are not
 935         * going to evict it nor find it through _get()
 936         * mechanism -- this is for the toplevel node that
 937         * would almost always change with any commit.
 938         */
 939        struct pbase_tree_cache pcache;
 940} *pbase_tree;
 941
 942static struct pbase_tree_cache *pbase_tree_get(const unsigned char *sha1)
 943{
 944        struct pbase_tree_cache *ent, *nent;
 945        void *data;
 946        unsigned long size;
 947        enum object_type type;
 948        int neigh;
 949        int my_ix = pbase_tree_cache_ix(sha1);
 950        int available_ix = -1;
 951
 952        /* pbase-tree-cache acts as a limited hashtable.
 953         * your object will be found at your index or within a few
 954         * slots after that slot if it is cached.
 955         */
 956        for (neigh = 0; neigh < 8; neigh++) {
 957                ent = pbase_tree_cache[my_ix];
 958                if (ent && !hashcmp(ent->sha1, sha1)) {
 959                        ent->ref++;
 960                        return ent;
 961                }
 962                else if (((available_ix < 0) && (!ent || !ent->ref)) ||
 963                         ((0 <= available_ix) &&
 964                          (!ent && pbase_tree_cache[available_ix])))
 965                        available_ix = my_ix;
 966                if (!ent)
 967                        break;
 968                my_ix = pbase_tree_cache_ix_incr(my_ix);
 969        }
 970
 971        /* Did not find one.  Either we got a bogus request or
 972         * we need to read and perhaps cache.
 973         */
 974        data = read_sha1_file(sha1, &type, &size);
 975        if (!data)
 976                return NULL;
 977        if (type != OBJ_TREE) {
 978                free(data);
 979                return NULL;
 980        }
 981
 982        /* We need to either cache or return a throwaway copy */
 983
 984        if (available_ix < 0)
 985                ent = NULL;
 986        else {
 987                ent = pbase_tree_cache[available_ix];
 988                my_ix = available_ix;
 989        }
 990
 991        if (!ent) {
 992                nent = xmalloc(sizeof(*nent));
 993                nent->temporary = (available_ix < 0);
 994        }
 995        else {
 996                /* evict and reuse */
 997                free(ent->tree_data);
 998                nent = ent;
 999        }
1000        hashcpy(nent->sha1, sha1);
1001        nent->tree_data = data;
1002        nent->tree_size = size;
1003        nent->ref = 1;
1004        if (!nent->temporary)
1005                pbase_tree_cache[my_ix] = nent;
1006        return nent;
1007}
1008
1009static void pbase_tree_put(struct pbase_tree_cache *cache)
1010{
1011        if (!cache->temporary) {
1012                cache->ref--;
1013                return;
1014        }
1015        free(cache->tree_data);
1016        free(cache);
1017}
1018
1019static int name_cmp_len(const char *name)
1020{
1021        int i;
1022        for (i = 0; name[i] && name[i] != '\n' && name[i] != '/'; i++)
1023                ;
1024        return i;
1025}
1026
1027static void add_pbase_object(struct tree_desc *tree,
1028                             const char *name,
1029                             int cmplen,
1030                             const char *fullname)
1031{
1032        struct name_entry entry;
1033        int cmp;
1034
1035        while (tree_entry(tree,&entry)) {
1036                cmp = tree_entry_len(entry.path, entry.sha1) != cmplen ? 1 :
1037                      memcmp(name, entry.path, cmplen);
1038                if (cmp > 0)
1039                        continue;
1040                if (cmp < 0)
1041                        return;
1042                if (name[cmplen] != '/') {
1043                        unsigned hash = name_hash(fullname);
1044                        add_object_entry(entry.sha1,
1045                                         S_ISDIR(entry.mode) ? OBJ_TREE : OBJ_BLOB,
1046                                         hash, 1);
1047                        return;
1048                }
1049                if (S_ISDIR(entry.mode)) {
1050                        struct tree_desc sub;
1051                        struct pbase_tree_cache *tree;
1052                        const char *down = name+cmplen+1;
1053                        int downlen = name_cmp_len(down);
1054
1055                        tree = pbase_tree_get(entry.sha1);
1056                        if (!tree)
1057                                return;
1058                        init_tree_desc(&sub, tree->tree_data, tree->tree_size);
1059
1060                        add_pbase_object(&sub, down, downlen, fullname);
1061                        pbase_tree_put(tree);
1062                }
1063        }
1064}
1065
1066static unsigned *done_pbase_paths;
1067static int done_pbase_paths_num;
1068static int done_pbase_paths_alloc;
1069static int done_pbase_path_pos(unsigned hash)
1070{
1071        int lo = 0;
1072        int hi = done_pbase_paths_num;
1073        while (lo < hi) {
1074                int mi = (hi + lo) / 2;
1075                if (done_pbase_paths[mi] == hash)
1076                        return mi;
1077                if (done_pbase_paths[mi] < hash)
1078                        hi = mi;
1079                else
1080                        lo = mi + 1;
1081        }
1082        return -lo-1;
1083}
1084
1085static int check_pbase_path(unsigned hash)
1086{
1087        int pos = (!done_pbase_paths) ? -1 : done_pbase_path_pos(hash);
1088        if (0 <= pos)
1089                return 1;
1090        pos = -pos - 1;
1091        if (done_pbase_paths_alloc <= done_pbase_paths_num) {
1092                done_pbase_paths_alloc = alloc_nr(done_pbase_paths_alloc);
1093                done_pbase_paths = xrealloc(done_pbase_paths,
1094                                            done_pbase_paths_alloc *
1095                                            sizeof(unsigned));
1096        }
1097        done_pbase_paths_num++;
1098        if (pos < done_pbase_paths_num)
1099                memmove(done_pbase_paths + pos + 1,
1100                        done_pbase_paths + pos,
1101                        (done_pbase_paths_num - pos - 1) * sizeof(unsigned));
1102        done_pbase_paths[pos] = hash;
1103        return 0;
1104}
1105
1106static void add_preferred_base_object(const char *name, unsigned hash)
1107{
1108        struct pbase_tree *it;
1109        int cmplen;
1110
1111        if (!num_preferred_base || check_pbase_path(hash))
1112                return;
1113
1114        cmplen = name_cmp_len(name);
1115        for (it = pbase_tree; it; it = it->next) {
1116                if (cmplen == 0) {
1117                        add_object_entry(it->pcache.sha1, OBJ_TREE, 0, 1);
1118                }
1119                else {
1120                        struct tree_desc tree;
1121                        init_tree_desc(&tree, it->pcache.tree_data, it->pcache.tree_size);
1122                        add_pbase_object(&tree, name, cmplen, name);
1123                }
1124        }
1125}
1126
1127static void add_preferred_base(unsigned char *sha1)
1128{
1129        struct pbase_tree *it;
1130        void *data;
1131        unsigned long size;
1132        unsigned char tree_sha1[20];
1133
1134        if (window <= num_preferred_base++)
1135                return;
1136
1137        data = read_object_with_reference(sha1, tree_type, &size, tree_sha1);
1138        if (!data)
1139                return;
1140
1141        for (it = pbase_tree; it; it = it->next) {
1142                if (!hashcmp(it->pcache.sha1, tree_sha1)) {
1143                        free(data);
1144                        return;
1145                }
1146        }
1147
1148        it = xcalloc(1, sizeof(*it));
1149        it->next = pbase_tree;
1150        pbase_tree = it;
1151
1152        hashcpy(it->pcache.sha1, tree_sha1);
1153        it->pcache.tree_data = data;
1154        it->pcache.tree_size = size;
1155}
1156
1157static void check_object(struct object_entry *entry)
1158{
1159        if (entry->in_pack) {
1160                struct packed_git *p = entry->in_pack;
1161                struct pack_window *w_curs = NULL;
1162                const unsigned char *base_ref = NULL;
1163                struct object_entry *base_entry;
1164                unsigned long used, used_0;
1165                unsigned int avail;
1166                off_t ofs;
1167                unsigned char *buf, c;
1168
1169                buf = use_pack(p, &w_curs, entry->in_pack_offset, &avail);
1170
1171                /*
1172                 * We want in_pack_type even if we do not reuse delta
1173                 * since non-delta representations could still be reused.
1174                 */
1175                used = unpack_object_header_gently(buf, avail,
1176                                                   &entry->in_pack_type,
1177                                                   &entry->size);
1178
1179                /*
1180                 * Determine if this is a delta and if so whether we can
1181                 * reuse it or not.  Otherwise let's find out as cheaply as
1182                 * possible what the actual type and size for this object is.
1183                 */
1184                switch (entry->in_pack_type) {
1185                default:
1186                        /* Not a delta hence we've already got all we need. */
1187                        entry->type = entry->in_pack_type;
1188                        entry->in_pack_header_size = used;
1189                        unuse_pack(&w_curs);
1190                        return;
1191                case OBJ_REF_DELTA:
1192                        if (!no_reuse_delta && !entry->preferred_base)
1193                                base_ref = use_pack(p, &w_curs,
1194                                                entry->in_pack_offset + used, NULL);
1195                        entry->in_pack_header_size = used + 20;
1196                        break;
1197                case OBJ_OFS_DELTA:
1198                        buf = use_pack(p, &w_curs,
1199                                       entry->in_pack_offset + used, NULL);
1200                        used_0 = 0;
1201                        c = buf[used_0++];
1202                        ofs = c & 127;
1203                        while (c & 128) {
1204                                ofs += 1;
1205                                if (!ofs || MSB(ofs, 7))
1206                                        die("delta base offset overflow in pack for %s",
1207                                            sha1_to_hex(entry->sha1));
1208                                c = buf[used_0++];
1209                                ofs = (ofs << 7) + (c & 127);
1210                        }
1211                        if (ofs >= entry->in_pack_offset)
1212                                die("delta base offset out of bound for %s",
1213                                    sha1_to_hex(entry->sha1));
1214                        ofs = entry->in_pack_offset - ofs;
1215                        if (!no_reuse_delta && !entry->preferred_base)
1216                                base_ref = find_packed_object_name(p, ofs);
1217                        entry->in_pack_header_size = used + used_0;
1218                        break;
1219                }
1220
1221                if (base_ref && (base_entry = locate_object_entry(base_ref))) {
1222                        /*
1223                         * If base_ref was set above that means we wish to
1224                         * reuse delta data, and we even found that base
1225                         * in the list of objects we want to pack. Goodie!
1226                         *
1227                         * Depth value does not matter - find_deltas() will
1228                         * never consider reused delta as the base object to
1229                         * deltify other objects against, in order to avoid
1230                         * circular deltas.
1231                         */
1232                        entry->type = entry->in_pack_type;
1233                        entry->delta = base_entry;
1234                        entry->delta_sibling = base_entry->delta_child;
1235                        base_entry->delta_child = entry;
1236                        unuse_pack(&w_curs);
1237                        return;
1238                }
1239
1240                if (entry->type) {
1241                        /*
1242                         * This must be a delta and we already know what the
1243                         * final object type is.  Let's extract the actual
1244                         * object size from the delta header.
1245                         */
1246                        entry->size = get_size_from_delta(p, &w_curs,
1247                                        entry->in_pack_offset + entry->in_pack_header_size);
1248                        unuse_pack(&w_curs);
1249                        return;
1250                }
1251
1252                /*
1253                 * No choice but to fall back to the recursive delta walk
1254                 * with sha1_object_info() to find about the object type
1255                 * at this point...
1256                 */
1257                unuse_pack(&w_curs);
1258        }
1259
1260        entry->type = sha1_object_info(entry->sha1, &entry->size);
1261        if (entry->type < 0)
1262                die("unable to get type of object %s",
1263                    sha1_to_hex(entry->sha1));
1264}
1265
1266static int pack_offset_sort(const void *_a, const void *_b)
1267{
1268        const struct object_entry *a = *(struct object_entry **)_a;
1269        const struct object_entry *b = *(struct object_entry **)_b;
1270
1271        /* avoid filesystem trashing with loose objects */
1272        if (!a->in_pack && !b->in_pack)
1273                return hashcmp(a->sha1, b->sha1);
1274
1275        if (a->in_pack < b->in_pack)
1276                return -1;
1277        if (a->in_pack > b->in_pack)
1278                return 1;
1279        return a->in_pack_offset < b->in_pack_offset ? -1 :
1280                        (a->in_pack_offset > b->in_pack_offset);
1281}
1282
1283static void get_object_details(void)
1284{
1285        uint32_t i;
1286        struct object_entry **sorted_by_offset;
1287
1288        sorted_by_offset = xcalloc(nr_objects, sizeof(struct object_entry *));
1289        for (i = 0; i < nr_objects; i++)
1290                sorted_by_offset[i] = objects + i;
1291        qsort(sorted_by_offset, nr_objects, sizeof(*sorted_by_offset), pack_offset_sort);
1292
1293        prepare_pack_ix();
1294        for (i = 0; i < nr_objects; i++)
1295                check_object(sorted_by_offset[i]);
1296        free(sorted_by_offset);
1297}
1298
1299static int type_size_sort(const void *_a, const void *_b)
1300{
1301        const struct object_entry *a = *(struct object_entry **)_a;
1302        const struct object_entry *b = *(struct object_entry **)_b;
1303
1304        if (a->type < b->type)
1305                return -1;
1306        if (a->type > b->type)
1307                return 1;
1308        if (a->hash < b->hash)
1309                return -1;
1310        if (a->hash > b->hash)
1311                return 1;
1312        if (a->preferred_base < b->preferred_base)
1313                return -1;
1314        if (a->preferred_base > b->preferred_base)
1315                return 1;
1316        if (a->size < b->size)
1317                return -1;
1318        if (a->size > b->size)
1319                return 1;
1320        return a > b ? -1 : (a < b);  /* newest last */
1321}
1322
1323struct unpacked {
1324        struct object_entry *entry;
1325        void *data;
1326        struct delta_index *index;
1327};
1328
1329/*
1330 * We search for deltas _backwards_ in a list sorted by type and
1331 * by size, so that we see progressively smaller and smaller files.
1332 * That's because we prefer deltas to be from the bigger file
1333 * to the smaller - deletes are potentially cheaper, but perhaps
1334 * more importantly, the bigger file is likely the more recent
1335 * one.
1336 */
1337static int try_delta(struct unpacked *trg, struct unpacked *src,
1338                     unsigned max_depth)
1339{
1340        struct object_entry *trg_entry = trg->entry;
1341        struct object_entry *src_entry = src->entry;
1342        unsigned long trg_size, src_size, delta_size, sizediff, max_size, sz;
1343        enum object_type type;
1344        void *delta_buf;
1345
1346        /* Don't bother doing diffs between different types */
1347        if (trg_entry->type != src_entry->type)
1348                return -1;
1349
1350        /* We do not compute delta to *create* objects we are not
1351         * going to pack.
1352         */
1353        if (trg_entry->preferred_base)
1354                return -1;
1355
1356        /*
1357         * We do not bother to try a delta that we discarded
1358         * on an earlier try, but only when reusing delta data.
1359         */
1360        if (!no_reuse_delta && trg_entry->in_pack &&
1361            trg_entry->in_pack == src_entry->in_pack &&
1362            trg_entry->in_pack_type != OBJ_REF_DELTA &&
1363            trg_entry->in_pack_type != OBJ_OFS_DELTA)
1364                return 0;
1365
1366        /* Let's not bust the allowed depth. */
1367        if (src_entry->depth >= max_depth)
1368                return 0;
1369
1370        /* Now some size filtering heuristics. */
1371        trg_size = trg_entry->size;
1372        max_size = trg_size/2 - 20;
1373        max_size = max_size * (max_depth - src_entry->depth) / max_depth;
1374        if (max_size == 0)
1375                return 0;
1376        if (trg_entry->delta && trg_entry->delta_size <= max_size)
1377                max_size = trg_entry->delta_size-1;
1378        src_size = src_entry->size;
1379        sizediff = src_size < trg_size ? trg_size - src_size : 0;
1380        if (sizediff >= max_size)
1381                return 0;
1382
1383        /* Load data if not already done */
1384        if (!trg->data) {
1385                trg->data = read_sha1_file(trg_entry->sha1, &type, &sz);
1386                if (sz != trg_size)
1387                        die("object %s inconsistent object length (%lu vs %lu)",
1388                            sha1_to_hex(trg_entry->sha1), sz, trg_size);
1389        }
1390        if (!src->data) {
1391                src->data = read_sha1_file(src_entry->sha1, &type, &sz);
1392                if (sz != src_size)
1393                        die("object %s inconsistent object length (%lu vs %lu)",
1394                            sha1_to_hex(src_entry->sha1), sz, src_size);
1395        }
1396        if (!src->index) {
1397                src->index = create_delta_index(src->data, src_size);
1398                if (!src->index)
1399                        die("out of memory");
1400        }
1401
1402        delta_buf = create_delta(src->index, trg->data, trg_size, &delta_size, max_size);
1403        if (!delta_buf)
1404                return 0;
1405
1406        trg_entry->delta = src_entry;
1407        trg_entry->delta_size = delta_size;
1408        trg_entry->depth = src_entry->depth + 1;
1409        free(delta_buf);
1410        return 1;
1411}
1412
1413static unsigned int check_delta_limit(struct object_entry *me, unsigned int n)
1414{
1415        struct object_entry *child = me->delta_child;
1416        unsigned int m = n;
1417        while (child) {
1418                unsigned int c = check_delta_limit(child, n + 1);
1419                if (m < c)
1420                        m = c;
1421                child = child->delta_sibling;
1422        }
1423        return m;
1424}
1425
1426static void find_deltas(struct object_entry **list, int window, int depth)
1427{
1428        uint32_t i = nr_objects, idx = 0, processed = 0;
1429        unsigned int array_size = window * sizeof(struct unpacked);
1430        struct unpacked *array;
1431        int max_depth;
1432
1433        if (!nr_objects)
1434                return;
1435        array = xmalloc(array_size);
1436        memset(array, 0, array_size);
1437        if (progress)
1438                start_progress(&progress_state, "Deltifying %u objects...", "", nr_result);
1439
1440        do {
1441                struct object_entry *entry = list[--i];
1442                struct unpacked *n = array + idx;
1443                int j;
1444
1445                if (!entry->preferred_base)
1446                        processed++;
1447
1448                if (progress)
1449                        display_progress(&progress_state, processed);
1450
1451                if (entry->delta)
1452                        /* This happens if we decided to reuse existing
1453                         * delta from a pack.  "!no_reuse_delta &&" is implied.
1454                         */
1455                        continue;
1456
1457                if (entry->size < 50)
1458                        continue;
1459                free_delta_index(n->index);
1460                n->index = NULL;
1461                free(n->data);
1462                n->data = NULL;
1463                n->entry = entry;
1464
1465                /*
1466                 * If the current object is at pack edge, take the depth the
1467                 * objects that depend on the current object into account
1468                 * otherwise they would become too deep.
1469                 */
1470                max_depth = depth;
1471                if (entry->delta_child) {
1472                        max_depth -= check_delta_limit(entry, 0);
1473                        if (max_depth <= 0)
1474                                goto next;
1475                }
1476
1477                j = window;
1478                while (--j > 0) {
1479                        uint32_t other_idx = idx + j;
1480                        struct unpacked *m;
1481                        if (other_idx >= window)
1482                                other_idx -= window;
1483                        m = array + other_idx;
1484                        if (!m->entry)
1485                                break;
1486                        if (try_delta(n, m, max_depth) < 0)
1487                                break;
1488                }
1489
1490                /* if we made n a delta, and if n is already at max
1491                 * depth, leaving it in the window is pointless.  we
1492                 * should evict it first.
1493                 */
1494                if (entry->delta && depth <= entry->depth)
1495                        continue;
1496
1497                next:
1498                idx++;
1499                if (idx >= window)
1500                        idx = 0;
1501        } while (i > 0);
1502
1503        if (progress)
1504                stop_progress(&progress_state);
1505
1506        for (i = 0; i < window; ++i) {
1507                free_delta_index(array[i].index);
1508                free(array[i].data);
1509        }
1510        free(array);
1511}
1512
1513static void prepare_pack(int window, int depth)
1514{
1515        struct object_entry **delta_list;
1516        uint32_t i;
1517
1518        get_object_details();
1519
1520        if (!window || !depth)
1521                return;
1522
1523        delta_list = xmalloc(nr_objects * sizeof(*delta_list));
1524        for (i = 0; i < nr_objects; i++)
1525                delta_list[i] = objects + i;
1526        qsort(delta_list, nr_objects, sizeof(*delta_list), type_size_sort);
1527        find_deltas(delta_list, window+1, depth);
1528        free(delta_list);
1529}
1530
1531static int git_pack_config(const char *k, const char *v)
1532{
1533        if(!strcmp(k, "pack.window")) {
1534                window = git_config_int(k, v);
1535                return 0;
1536        }
1537        if(!strcmp(k, "pack.depth")) {
1538                depth = git_config_int(k, v);
1539                return 0;
1540        }
1541        if (!strcmp(k, "pack.compression")) {
1542                int level = git_config_int(k, v);
1543                if (level == -1)
1544                        level = Z_DEFAULT_COMPRESSION;
1545                else if (level < 0 || level > Z_BEST_COMPRESSION)
1546                        die("bad pack compression level %d", level);
1547                pack_compression_level = level;
1548                pack_compression_seen = 1;
1549                return 0;
1550        }
1551        return git_default_config(k, v);
1552}
1553
1554static void read_object_list_from_stdin(void)
1555{
1556        char line[40 + 1 + PATH_MAX + 2];
1557        unsigned char sha1[20];
1558        unsigned hash;
1559
1560        for (;;) {
1561                if (!fgets(line, sizeof(line), stdin)) {
1562                        if (feof(stdin))
1563                                break;
1564                        if (!ferror(stdin))
1565                                die("fgets returned NULL, not EOF, not error!");
1566                        if (errno != EINTR)
1567                                die("fgets: %s", strerror(errno));
1568                        clearerr(stdin);
1569                        continue;
1570                }
1571                if (line[0] == '-') {
1572                        if (get_sha1_hex(line+1, sha1))
1573                                die("expected edge sha1, got garbage:\n %s",
1574                                    line);
1575                        add_preferred_base(sha1);
1576                        continue;
1577                }
1578                if (get_sha1_hex(line, sha1))
1579                        die("expected sha1, got garbage:\n %s", line);
1580
1581                hash = name_hash(line+41);
1582                add_preferred_base_object(line+41, hash);
1583                add_object_entry(sha1, 0, hash, 0);
1584        }
1585}
1586
1587static void show_commit(struct commit *commit)
1588{
1589        add_object_entry(commit->object.sha1, OBJ_COMMIT, 0, 0);
1590}
1591
1592static void show_object(struct object_array_entry *p)
1593{
1594        unsigned hash = name_hash(p->name);
1595        add_preferred_base_object(p->name, hash);
1596        add_object_entry(p->item->sha1, p->item->type, hash, 0);
1597}
1598
1599static void show_edge(struct commit *commit)
1600{
1601        add_preferred_base(commit->object.sha1);
1602}
1603
1604static void get_object_list(int ac, const char **av)
1605{
1606        struct rev_info revs;
1607        char line[1000];
1608        int flags = 0;
1609
1610        init_revisions(&revs, NULL);
1611        save_commit_buffer = 0;
1612        track_object_refs = 0;
1613        setup_revisions(ac, av, &revs, NULL);
1614
1615        while (fgets(line, sizeof(line), stdin) != NULL) {
1616                int len = strlen(line);
1617                if (line[len - 1] == '\n')
1618                        line[--len] = 0;
1619                if (!len)
1620                        break;
1621                if (*line == '-') {
1622                        if (!strcmp(line, "--not")) {
1623                                flags ^= UNINTERESTING;
1624                                continue;
1625                        }
1626                        die("not a rev '%s'", line);
1627                }
1628                if (handle_revision_arg(line, &revs, flags, 1))
1629                        die("bad revision '%s'", line);
1630        }
1631
1632        prepare_revision_walk(&revs);
1633        mark_edges_uninteresting(revs.commits, &revs, show_edge);
1634        traverse_commit_list(&revs, show_commit, show_object);
1635}
1636
1637static int adjust_perm(const char *path, mode_t mode)
1638{
1639        if (chmod(path, mode))
1640                return -1;
1641        return adjust_shared_perm(path);
1642}
1643
1644int cmd_pack_objects(int argc, const char **argv, const char *prefix)
1645{
1646        int use_internal_rev_list = 0;
1647        int thin = 0;
1648        uint32_t i;
1649        const char **rp_av;
1650        int rp_ac_alloc = 64;
1651        int rp_ac;
1652
1653        rp_av = xcalloc(rp_ac_alloc, sizeof(*rp_av));
1654
1655        rp_av[0] = "pack-objects";
1656        rp_av[1] = "--objects"; /* --thin will make it --objects-edge */
1657        rp_ac = 2;
1658
1659        git_config(git_pack_config);
1660        if (!pack_compression_seen && core_compression_seen)
1661                pack_compression_level = core_compression_level;
1662
1663        progress = isatty(2);
1664        for (i = 1; i < argc; i++) {
1665                const char *arg = argv[i];
1666
1667                if (*arg != '-')
1668                        break;
1669
1670                if (!strcmp("--non-empty", arg)) {
1671                        non_empty = 1;
1672                        continue;
1673                }
1674                if (!strcmp("--local", arg)) {
1675                        local = 1;
1676                        continue;
1677                }
1678                if (!strcmp("--incremental", arg)) {
1679                        incremental = 1;
1680                        continue;
1681                }
1682                if (!prefixcmp(arg, "--compression=")) {
1683                        char *end;
1684                        int level = strtoul(arg+14, &end, 0);
1685                        if (!arg[14] || *end)
1686                                usage(pack_usage);
1687                        if (level == -1)
1688                                level = Z_DEFAULT_COMPRESSION;
1689                        else if (level < 0 || level > Z_BEST_COMPRESSION)
1690                                die("bad pack compression level %d", level);
1691                        pack_compression_level = level;
1692                        continue;
1693                }
1694                if (!prefixcmp(arg, "--window=")) {
1695                        char *end;
1696                        window = strtoul(arg+9, &end, 0);
1697                        if (!arg[9] || *end)
1698                                usage(pack_usage);
1699                        continue;
1700                }
1701                if (!prefixcmp(arg, "--depth=")) {
1702                        char *end;
1703                        depth = strtoul(arg+8, &end, 0);
1704                        if (!arg[8] || *end)
1705                                usage(pack_usage);
1706                        continue;
1707                }
1708                if (!strcmp("--progress", arg)) {
1709                        progress = 1;
1710                        continue;
1711                }
1712                if (!strcmp("--all-progress", arg)) {
1713                        progress = 2;
1714                        continue;
1715                }
1716                if (!strcmp("-q", arg)) {
1717                        progress = 0;
1718                        continue;
1719                }
1720                if (!strcmp("--no-reuse-delta", arg)) {
1721                        no_reuse_delta = 1;
1722                        continue;
1723                }
1724                if (!strcmp("--no-reuse-object", arg)) {
1725                        no_reuse_object = no_reuse_delta = 1;
1726                        continue;
1727                }
1728                if (!strcmp("--delta-base-offset", arg)) {
1729                        allow_ofs_delta = 1;
1730                        continue;
1731                }
1732                if (!strcmp("--stdout", arg)) {
1733                        pack_to_stdout = 1;
1734                        continue;
1735                }
1736                if (!strcmp("--revs", arg)) {
1737                        use_internal_rev_list = 1;
1738                        continue;
1739                }
1740                if (!strcmp("--unpacked", arg) ||
1741                    !prefixcmp(arg, "--unpacked=") ||
1742                    !strcmp("--reflog", arg) ||
1743                    !strcmp("--all", arg)) {
1744                        use_internal_rev_list = 1;
1745                        if (rp_ac >= rp_ac_alloc - 1) {
1746                                rp_ac_alloc = alloc_nr(rp_ac_alloc);
1747                                rp_av = xrealloc(rp_av,
1748                                                 rp_ac_alloc * sizeof(*rp_av));
1749                        }
1750                        rp_av[rp_ac++] = arg;
1751                        continue;
1752                }
1753                if (!strcmp("--thin", arg)) {
1754                        use_internal_rev_list = 1;
1755                        thin = 1;
1756                        rp_av[1] = "--objects-edge";
1757                        continue;
1758                }
1759                if (!prefixcmp(arg, "--index-version=")) {
1760                        char *c;
1761                        index_default_version = strtoul(arg + 16, &c, 10);
1762                        if (index_default_version > 2)
1763                                die("bad %s", arg);
1764                        if (*c == ',')
1765                                index_off32_limit = strtoul(c+1, &c, 0);
1766                        if (*c || index_off32_limit & 0x80000000)
1767                                die("bad %s", arg);
1768                        continue;
1769                }
1770                usage(pack_usage);
1771        }
1772
1773        /* Traditionally "pack-objects [options] base extra" failed;
1774         * we would however want to take refs parameter that would
1775         * have been given to upstream rev-list ourselves, which means
1776         * we somehow want to say what the base name is.  So the
1777         * syntax would be:
1778         *
1779         * pack-objects [options] base <refs...>
1780         *
1781         * in other words, we would treat the first non-option as the
1782         * base_name and send everything else to the internal revision
1783         * walker.
1784         */
1785
1786        if (!pack_to_stdout)
1787                base_name = argv[i++];
1788
1789        if (pack_to_stdout != !base_name)
1790                usage(pack_usage);
1791
1792        if (!pack_to_stdout && thin)
1793                die("--thin cannot be used to build an indexable pack.");
1794
1795        prepare_packed_git();
1796
1797        if (progress)
1798                start_progress(&progress_state, "Generating pack...",
1799                               "Counting objects: ", 0);
1800        if (!use_internal_rev_list)
1801                read_object_list_from_stdin();
1802        else {
1803                rp_av[rp_ac] = NULL;
1804                get_object_list(rp_ac, rp_av);
1805        }
1806        if (progress) {
1807                stop_progress(&progress_state);
1808                fprintf(stderr, "Done counting %u objects.\n", nr_objects);
1809        }
1810
1811        if (non_empty && !nr_result)
1812                return 0;
1813        if (progress && (nr_objects != nr_result))
1814                fprintf(stderr, "Result has %u objects.\n", nr_result);
1815        if (nr_result)
1816                prepare_pack(window, depth);
1817        write_pack_file();
1818        if (progress)
1819                fprintf(stderr, "Total %u (delta %u), reused %u (delta %u)\n",
1820                        written, written_delta, reused, reused_delta);
1821        return 0;
1822}