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