pack-objects.con commit Merge git://git.kernel.org/pub/scm/gitk/gitk (521a3f6)
   1#include "cache.h"
   2#include "object.h"
   3#include "blob.h"
   4#include "commit.h"
   5#include "tag.h"
   6#include "tree.h"
   7#include "delta.h"
   8#include "pack.h"
   9#include "csum-file.h"
  10#include "tree-walk.h"
  11#include <sys/time.h>
  12#include <signal.h>
  13
  14static const char pack_usage[] = "git-pack-objects [-q] [--no-reuse-delta] [--non-empty] [--local] [--incremental] [--window=N] [--depth=N] {--stdout | base-name} < object-list";
  15
  16struct object_entry {
  17        unsigned char sha1[20];
  18        unsigned long size;     /* uncompressed size */
  19        unsigned long offset;   /* offset into the final pack file;
  20                                 * nonzero if already written.
  21                                 */
  22        unsigned int depth;     /* delta depth */
  23        unsigned int delta_limit;       /* base adjustment for in-pack delta */
  24        unsigned int hash;      /* name hint hash */
  25        enum object_type type;
  26        enum object_type in_pack_type;  /* could be delta */
  27        unsigned long delta_size;       /* delta data size (uncompressed) */
  28        struct object_entry *delta;     /* delta base object */
  29        struct packed_git *in_pack;     /* already in pack */
  30        unsigned int in_pack_offset;
  31        struct object_entry *delta_child; /* delitified objects who bases me */
  32        struct object_entry *delta_sibling; /* other deltified objects who
  33                                             * uses the same base as me
  34                                             */
  35        int preferred_base;     /* we do not pack this, but is encouraged to
  36                                 * be used as the base objectto delta huge
  37                                 * objects against.
  38                                 */
  39};
  40
  41/*
  42 * Objects we are going to pack are colected in objects array (dynamically
  43 * expanded).  nr_objects & nr_alloc controls this array.  They are stored
  44 * in the order we see -- typically rev-list --objects order that gives us
  45 * nice "minimum seek" order.
  46 *
  47 * sorted-by-sha ans sorted-by-type are arrays of pointers that point at
  48 * elements in the objects array.  The former is used to build the pack
  49 * index (lists object names in the ascending order to help offset lookup),
  50 * and the latter is used to group similar things together by try_delta()
  51 * heuristics.
  52 */
  53
  54static unsigned char object_list_sha1[20];
  55static int non_empty = 0;
  56static int no_reuse_delta = 0;
  57static int local = 0;
  58static int incremental = 0;
  59static struct object_entry **sorted_by_sha, **sorted_by_type;
  60static struct object_entry *objects = NULL;
  61static int nr_objects = 0, nr_alloc = 0, nr_result = 0;
  62static const char *base_name;
  63static unsigned char pack_file_sha1[20];
  64static int progress = 1;
  65static volatile sig_atomic_t progress_update = 0;
  66
  67/*
  68 * The object names in objects array are hashed with this hashtable,
  69 * to help looking up the entry by object name.  Binary search from
  70 * sorted_by_sha is also possible but this was easier to code and faster.
  71 * This hashtable is built after all the objects are seen.
  72 */
  73static int *object_ix = NULL;
  74static int object_ix_hashsz = 0;
  75
  76/*
  77 * Pack index for existing packs give us easy access to the offsets into
  78 * corresponding pack file where each object's data starts, but the entries
  79 * do not store the size of the compressed representation (uncompressed
  80 * size is easily available by examining the pack entry header).  We build
  81 * a hashtable of existing packs (pack_revindex), and keep reverse index
  82 * here -- pack index file is sorted by object name mapping to offset; this
  83 * pack_revindex[].revindex array is an ordered list of offsets, so if you
  84 * know the offset of an object, next offset is where its packed
  85 * representation ends.
  86 */
  87struct pack_revindex {
  88        struct packed_git *p;
  89        unsigned long *revindex;
  90} *pack_revindex = NULL;
  91static int pack_revindex_hashsz = 0;
  92
  93/*
  94 * stats
  95 */
  96static int written = 0;
  97static int written_delta = 0;
  98static int reused = 0;
  99static int reused_delta = 0;
 100
 101static int pack_revindex_ix(struct packed_git *p)
 102{
 103        unsigned long ui = (unsigned long)p;
 104        int i;
 105
 106        ui = ui ^ (ui >> 16); /* defeat structure alignment */
 107        i = (int)(ui % pack_revindex_hashsz);
 108        while (pack_revindex[i].p) {
 109                if (pack_revindex[i].p == p)
 110                        return i;
 111                if (++i == pack_revindex_hashsz)
 112                        i = 0;
 113        }
 114        return -1 - i;
 115}
 116
 117static void prepare_pack_ix(void)
 118{
 119        int num;
 120        struct packed_git *p;
 121        for (num = 0, p = packed_git; p; p = p->next)
 122                num++;
 123        if (!num)
 124                return;
 125        pack_revindex_hashsz = num * 11;
 126        pack_revindex = xcalloc(sizeof(*pack_revindex), pack_revindex_hashsz);
 127        for (p = packed_git; p; p = p->next) {
 128                num = pack_revindex_ix(p);
 129                num = - 1 - num;
 130                pack_revindex[num].p = p;
 131        }
 132        /* revindex elements are lazily initialized */
 133}
 134
 135static int cmp_offset(const void *a_, const void *b_)
 136{
 137        unsigned long a = *(unsigned long *) a_;
 138        unsigned long b = *(unsigned long *) b_;
 139        if (a < b)
 140                return -1;
 141        else if (a == b)
 142                return 0;
 143        else
 144                return 1;
 145}
 146
 147/*
 148 * Ordered list of offsets of objects in the pack.
 149 */
 150static void prepare_pack_revindex(struct pack_revindex *rix)
 151{
 152        struct packed_git *p = rix->p;
 153        int num_ent = num_packed_objects(p);
 154        int i;
 155        void *index = p->index_base + 256;
 156
 157        rix->revindex = xmalloc(sizeof(unsigned long) * (num_ent + 1));
 158        for (i = 0; i < num_ent; i++) {
 159                long hl = *((long *)(index + 24 * i));
 160                rix->revindex[i] = ntohl(hl);
 161        }
 162        /* This knows the pack format -- the 20-byte trailer
 163         * follows immediately after the last object data.
 164         */
 165        rix->revindex[num_ent] = p->pack_size - 20;
 166        qsort(rix->revindex, num_ent, sizeof(unsigned long), cmp_offset);
 167}
 168
 169static unsigned long find_packed_object_size(struct packed_git *p,
 170                                             unsigned long ofs)
 171{
 172        int num;
 173        int lo, hi;
 174        struct pack_revindex *rix;
 175        unsigned long *revindex;
 176        num = pack_revindex_ix(p);
 177        if (num < 0)
 178                die("internal error: pack revindex uninitialized");
 179        rix = &pack_revindex[num];
 180        if (!rix->revindex)
 181                prepare_pack_revindex(rix);
 182        revindex = rix->revindex;
 183        lo = 0;
 184        hi = num_packed_objects(p) + 1;
 185        do {
 186                int mi = (lo + hi) / 2;
 187                if (revindex[mi] == ofs) {
 188                        return revindex[mi+1] - ofs;
 189                }
 190                else if (ofs < revindex[mi])
 191                        hi = mi;
 192                else
 193                        lo = mi + 1;
 194        } while (lo < hi);
 195        die("internal error: pack revindex corrupt");
 196}
 197
 198static void *delta_against(void *buf, unsigned long size, struct object_entry *entry)
 199{
 200        unsigned long othersize, delta_size;
 201        char type[10];
 202        void *otherbuf = read_sha1_file(entry->delta->sha1, type, &othersize);
 203        void *delta_buf;
 204
 205        if (!otherbuf)
 206                die("unable to read %s", sha1_to_hex(entry->delta->sha1));
 207        delta_buf = diff_delta(otherbuf, othersize,
 208                               buf, size, &delta_size, 0);
 209        if (!delta_buf || delta_size != entry->delta_size)
 210                die("delta size changed");
 211        free(buf);
 212        free(otherbuf);
 213        return delta_buf;
 214}
 215
 216/*
 217 * The per-object header is a pretty dense thing, which is
 218 *  - first byte: low four bits are "size", then three bits of "type",
 219 *    and the high bit is "size continues".
 220 *  - each byte afterwards: low seven bits are size continuation,
 221 *    with the high bit being "size continues"
 222 */
 223static int encode_header(enum object_type type, unsigned long size, unsigned char *hdr)
 224{
 225        int n = 1;
 226        unsigned char c;
 227
 228        if (type < OBJ_COMMIT || type > OBJ_DELTA)
 229                die("bad type %d", type);
 230
 231        c = (type << 4) | (size & 15);
 232        size >>= 4;
 233        while (size) {
 234                *hdr++ = c | 0x80;
 235                c = size & 0x7f;
 236                size >>= 7;
 237                n++;
 238        }
 239        *hdr = c;
 240        return n;
 241}
 242
 243static unsigned long write_object(struct sha1file *f,
 244                                  struct object_entry *entry)
 245{
 246        unsigned long size;
 247        char type[10];
 248        void *buf;
 249        unsigned char header[10];
 250        unsigned hdrlen, datalen;
 251        enum object_type obj_type;
 252        int to_reuse = 0;
 253
 254        if (entry->preferred_base)
 255                return 0;
 256
 257        obj_type = entry->type;
 258        if (! entry->in_pack)
 259                to_reuse = 0;   /* can't reuse what we don't have */
 260        else if (obj_type == OBJ_DELTA)
 261                to_reuse = 1;   /* check_object() decided it for us */
 262        else if (obj_type != entry->in_pack_type)
 263                to_reuse = 0;   /* pack has delta which is unusable */
 264        else if (entry->delta)
 265                to_reuse = 0;   /* we want to pack afresh */
 266        else
 267                to_reuse = 1;   /* we have it in-pack undeltified,
 268                                 * and we do not need to deltify it.
 269                                 */
 270
 271        if (! to_reuse) {
 272                buf = read_sha1_file(entry->sha1, type, &size);
 273                if (!buf)
 274                        die("unable to read %s", sha1_to_hex(entry->sha1));
 275                if (size != entry->size)
 276                        die("object %s size inconsistency (%lu vs %lu)",
 277                            sha1_to_hex(entry->sha1), size, entry->size);
 278                if (entry->delta) {
 279                        buf = delta_against(buf, size, entry);
 280                        size = entry->delta_size;
 281                        obj_type = OBJ_DELTA;
 282                }
 283                /*
 284                 * The object header is a byte of 'type' followed by zero or
 285                 * more bytes of length.  For deltas, the 20 bytes of delta
 286                 * sha1 follows that.
 287                 */
 288                hdrlen = encode_header(obj_type, size, header);
 289                sha1write(f, header, hdrlen);
 290
 291                if (entry->delta) {
 292                        sha1write(f, entry->delta, 20);
 293                        hdrlen += 20;
 294                }
 295                datalen = sha1write_compressed(f, buf, size);
 296                free(buf);
 297        }
 298        else {
 299                struct packed_git *p = entry->in_pack;
 300                use_packed_git(p);
 301
 302                datalen = find_packed_object_size(p, entry->in_pack_offset);
 303                buf = p->pack_base + entry->in_pack_offset;
 304                sha1write(f, buf, datalen);
 305                unuse_packed_git(p);
 306                hdrlen = 0; /* not really */
 307                if (obj_type == OBJ_DELTA)
 308                        reused_delta++;
 309                reused++;
 310        }
 311        if (obj_type == OBJ_DELTA)
 312                written_delta++;
 313        written++;
 314        return hdrlen + datalen;
 315}
 316
 317static unsigned long write_one(struct sha1file *f,
 318                               struct object_entry *e,
 319                               unsigned long offset)
 320{
 321        if (e->offset)
 322                /* offset starts from header size and cannot be zero
 323                 * if it is written already.
 324                 */
 325                return offset;
 326        e->offset = offset;
 327        offset += write_object(f, e);
 328        /* if we are deltified, write out its base object. */
 329        if (e->delta)
 330                offset = write_one(f, e->delta, offset);
 331        return offset;
 332}
 333
 334static void write_pack_file(void)
 335{
 336        int i;
 337        struct sha1file *f;
 338        unsigned long offset;
 339        struct pack_header hdr;
 340        unsigned last_percent = 999;
 341        int do_progress = 0;
 342
 343        if (!base_name)
 344                f = sha1fd(1, "<stdout>");
 345        else {
 346                f = sha1create("%s-%s.%s", base_name,
 347                               sha1_to_hex(object_list_sha1), "pack");
 348                do_progress = progress;
 349        }
 350        if (do_progress)
 351                fprintf(stderr, "Writing %d objects.\n", nr_result);
 352
 353        hdr.hdr_signature = htonl(PACK_SIGNATURE);
 354        hdr.hdr_version = htonl(PACK_VERSION);
 355        hdr.hdr_entries = htonl(nr_result);
 356        sha1write(f, &hdr, sizeof(hdr));
 357        offset = sizeof(hdr);
 358        if (!nr_result)
 359                goto done;
 360        for (i = 0; i < nr_objects; i++) {
 361                offset = write_one(f, objects + i, offset);
 362                if (do_progress) {
 363                        unsigned percent = written * 100 / nr_result;
 364                        if (progress_update || percent != last_percent) {
 365                                fprintf(stderr, "%4u%% (%u/%u) done\r",
 366                                        percent, written, nr_result);
 367                                progress_update = 0;
 368                                last_percent = percent;
 369                        }
 370                }
 371        }
 372        if (do_progress)
 373                fputc('\n', stderr);
 374 done:
 375        sha1close(f, pack_file_sha1, 1);
 376}
 377
 378static void write_index_file(void)
 379{
 380        int i;
 381        struct sha1file *f = sha1create("%s-%s.%s", base_name,
 382                                        sha1_to_hex(object_list_sha1), "idx");
 383        struct object_entry **list = sorted_by_sha;
 384        struct object_entry **last = list + nr_result;
 385        unsigned int array[256];
 386
 387        /*
 388         * Write the first-level table (the list is sorted,
 389         * but we use a 256-entry lookup to be able to avoid
 390         * having to do eight extra binary search iterations).
 391         */
 392        for (i = 0; i < 256; i++) {
 393                struct object_entry **next = list;
 394                while (next < last) {
 395                        struct object_entry *entry = *next;
 396                        if (entry->sha1[0] != i)
 397                                break;
 398                        next++;
 399                }
 400                array[i] = htonl(next - sorted_by_sha);
 401                list = next;
 402        }
 403        sha1write(f, array, 256 * sizeof(int));
 404
 405        /*
 406         * Write the actual SHA1 entries..
 407         */
 408        list = sorted_by_sha;
 409        for (i = 0; i < nr_result; i++) {
 410                struct object_entry *entry = *list++;
 411                unsigned int offset = htonl(entry->offset);
 412                sha1write(f, &offset, 4);
 413                sha1write(f, entry->sha1, 20);
 414        }
 415        sha1write(f, pack_file_sha1, 20);
 416        sha1close(f, NULL, 1);
 417}
 418
 419static int locate_object_entry_hash(const unsigned char *sha1)
 420{
 421        int i;
 422        unsigned int ui;
 423        memcpy(&ui, sha1, sizeof(unsigned int));
 424        i = ui % object_ix_hashsz;
 425        while (0 < object_ix[i]) {
 426                if (!memcmp(sha1, objects[object_ix[i]-1].sha1, 20))
 427                        return i;
 428                if (++i == object_ix_hashsz)
 429                        i = 0;
 430        }
 431        return -1 - i;
 432}
 433
 434static struct object_entry *locate_object_entry(const unsigned char *sha1)
 435{
 436        int i;
 437
 438        if (!object_ix_hashsz)
 439                return NULL;
 440
 441        i = locate_object_entry_hash(sha1);
 442        if (0 <= i)
 443                return &objects[object_ix[i]-1];
 444        return NULL;
 445}
 446
 447static void rehash_objects(void)
 448{
 449        int i;
 450        struct object_entry *oe;
 451
 452        object_ix_hashsz = nr_objects * 3;
 453        if (object_ix_hashsz < 1024)
 454                object_ix_hashsz = 1024;
 455        object_ix = xrealloc(object_ix, sizeof(int) * object_ix_hashsz);
 456        object_ix = memset(object_ix, 0, sizeof(int) * object_ix_hashsz);
 457        for (i = 0, oe = objects; i < nr_objects; i++, oe++) {
 458                int ix = locate_object_entry_hash(oe->sha1);
 459                if (0 <= ix)
 460                        continue;
 461                ix = -1 - ix;
 462                object_ix[ix] = i + 1;
 463        }
 464}
 465
 466struct name_path {
 467        struct name_path *up;
 468        const char *elem;
 469        int len;
 470};
 471
 472#define DIRBITS 12
 473
 474static unsigned name_hash(struct name_path *path, const char *name)
 475{
 476        struct name_path *p = path;
 477        const char *n = name + strlen(name);
 478        unsigned hash = 0, name_hash = 0, name_done = 0;
 479
 480        if (n != name && n[-1] == '\n')
 481                n--;
 482        while (name <= --n) {
 483                unsigned char c = *n;
 484                if (c == '/' && !name_done) {
 485                        name_hash = hash;
 486                        name_done = 1;
 487                        hash = 0;
 488                }
 489                hash = hash * 11 + c;
 490        }
 491        if (!name_done) {
 492                name_hash = hash;
 493                hash = 0;
 494        }
 495        for (p = path; p; p = p->up) {
 496                hash = hash * 11 + '/';
 497                n = p->elem + p->len;
 498                while (p->elem <= --n) {
 499                        unsigned char c = *n;
 500                        hash = hash * 11 + c;
 501                }
 502        }
 503        /*
 504         * Make sure "Makefile" and "t/Makefile" are hashed separately
 505         * but close enough.
 506         */
 507        hash = (name_hash<<DIRBITS) | (hash & ((1U<<DIRBITS )-1));
 508
 509        if (0) { /* debug */
 510                n = name + strlen(name);
 511                if (n != name && n[-1] == '\n')
 512                        n--;
 513                while (name <= --n)
 514                        fputc(*n, stderr);
 515                for (p = path; p; p = p->up) {
 516                        fputc('/', stderr);
 517                        n = p->elem + p->len;
 518                        while (p->elem <= --n)
 519                                fputc(*n, stderr);
 520                }
 521                fprintf(stderr, "\t%08x\n", hash);
 522        }
 523        return hash;
 524}
 525
 526static int add_object_entry(const unsigned char *sha1, unsigned hash, int exclude)
 527{
 528        unsigned int idx = nr_objects;
 529        struct object_entry *entry;
 530        struct packed_git *p;
 531        unsigned int found_offset = 0;
 532        struct packed_git *found_pack = NULL;
 533        int ix, status = 0;
 534
 535        if (!exclude) {
 536                for (p = packed_git; p; p = p->next) {
 537                        struct pack_entry e;
 538                        if (find_pack_entry_one(sha1, &e, p)) {
 539                                if (incremental)
 540                                        return 0;
 541                                if (local && !p->pack_local)
 542                                        return 0;
 543                                if (!found_pack) {
 544                                        found_offset = e.offset;
 545                                        found_pack = e.p;
 546                                }
 547                        }
 548                }
 549        }
 550        if ((entry = locate_object_entry(sha1)) != NULL)
 551                goto already_added;
 552
 553        if (idx >= nr_alloc) {
 554                unsigned int needed = (idx + 1024) * 3 / 2;
 555                objects = xrealloc(objects, needed * sizeof(*entry));
 556                nr_alloc = needed;
 557        }
 558        entry = objects + idx;
 559        nr_objects = idx + 1;
 560        memset(entry, 0, sizeof(*entry));
 561        memcpy(entry->sha1, sha1, 20);
 562        entry->hash = hash;
 563
 564        if (object_ix_hashsz * 3 <= nr_objects * 4)
 565                rehash_objects();
 566        else {
 567                ix = locate_object_entry_hash(entry->sha1);
 568                if (0 <= ix)
 569                        die("internal error in object hashing.");
 570                object_ix[-1 - ix] = idx + 1;
 571        }
 572        status = 1;
 573
 574 already_added:
 575        if (progress_update) {
 576                fprintf(stderr, "Counting objects...%d\r", nr_objects);
 577                progress_update = 0;
 578        }
 579        if (exclude)
 580                entry->preferred_base = 1;
 581        else {
 582                if (found_pack) {
 583                        entry->in_pack = found_pack;
 584                        entry->in_pack_offset = found_offset;
 585                }
 586        }
 587        return status;
 588}
 589
 590static void add_pbase_tree(struct tree_desc *tree, struct name_path *up)
 591{
 592        while (tree->size) {
 593                const unsigned char *sha1;
 594                const char *name;
 595                unsigned mode, hash;
 596                unsigned long size;
 597                char type[20];
 598
 599                sha1 = tree_entry_extract(tree, &name, &mode);
 600                update_tree_entry(tree);
 601                if (!has_sha1_file(sha1))
 602                        continue;
 603                if (sha1_object_info(sha1, type, &size))
 604                        continue;
 605
 606                hash = name_hash(up, name);
 607                if (!add_object_entry(sha1, hash, 1))
 608                        continue;
 609
 610                if (!strcmp(type, tree_type)) {
 611                        struct tree_desc sub;
 612                        void *elem;
 613                        struct name_path me;
 614
 615                        elem = read_sha1_file(sha1, type, &sub.size);
 616                        sub.buf = elem;
 617                        if (sub.buf) {
 618                                me.up = up;
 619                                me.elem = name;
 620                                me.len = strlen(name);
 621                                add_pbase_tree(&sub, &me);
 622                                free(elem);
 623                        }
 624                }
 625        }
 626}
 627
 628static void add_preferred_base(unsigned char *sha1)
 629{
 630        struct tree_desc tree;
 631        void *elem;
 632
 633        elem = read_object_with_reference(sha1, tree_type, &tree.size, NULL);
 634        tree.buf = elem;
 635        if (!tree.buf)
 636                return;
 637        if (add_object_entry(sha1, name_hash(NULL, ""), 1))
 638                add_pbase_tree(&tree, NULL);
 639        free(elem);
 640}
 641
 642static void check_object(struct object_entry *entry)
 643{
 644        char type[20];
 645
 646        if (entry->in_pack && !entry->preferred_base) {
 647                unsigned char base[20];
 648                unsigned long size;
 649                struct object_entry *base_entry;
 650
 651                /* We want in_pack_type even if we do not reuse delta.
 652                 * There is no point not reusing non-delta representations.
 653                 */
 654                check_reuse_pack_delta(entry->in_pack,
 655                                       entry->in_pack_offset,
 656                                       base, &size,
 657                                       &entry->in_pack_type);
 658
 659                /* Check if it is delta, and the base is also an object
 660                 * we are going to pack.  If so we will reuse the existing
 661                 * delta.
 662                 */
 663                if (!no_reuse_delta &&
 664                    entry->in_pack_type == OBJ_DELTA &&
 665                    (base_entry = locate_object_entry(base)) &&
 666                    (!base_entry->preferred_base)) {
 667
 668                        /* Depth value does not matter - find_deltas()
 669                         * will never consider reused delta as the
 670                         * base object to deltify other objects
 671                         * against, in order to avoid circular deltas.
 672                         */
 673
 674                        /* uncompressed size of the delta data */
 675                        entry->size = entry->delta_size = size;
 676                        entry->delta = base_entry;
 677                        entry->type = OBJ_DELTA;
 678
 679                        entry->delta_sibling = base_entry->delta_child;
 680                        base_entry->delta_child = entry;
 681
 682                        return;
 683                }
 684                /* Otherwise we would do the usual */
 685        }
 686
 687        if (sha1_object_info(entry->sha1, type, &entry->size))
 688                die("unable to get type of object %s",
 689                    sha1_to_hex(entry->sha1));
 690
 691        if (!strcmp(type, commit_type)) {
 692                entry->type = OBJ_COMMIT;
 693        } else if (!strcmp(type, tree_type)) {
 694                entry->type = OBJ_TREE;
 695        } else if (!strcmp(type, blob_type)) {
 696                entry->type = OBJ_BLOB;
 697        } else if (!strcmp(type, tag_type)) {
 698                entry->type = OBJ_TAG;
 699        } else
 700                die("unable to pack object %s of type %s",
 701                    sha1_to_hex(entry->sha1), type);
 702}
 703
 704static unsigned int check_delta_limit(struct object_entry *me, unsigned int n)
 705{
 706        struct object_entry *child = me->delta_child;
 707        unsigned int m = n;
 708        while (child) {
 709                unsigned int c = check_delta_limit(child, n + 1);
 710                if (m < c)
 711                        m = c;
 712                child = child->delta_sibling;
 713        }
 714        return m;
 715}
 716
 717static void get_object_details(void)
 718{
 719        int i;
 720        struct object_entry *entry;
 721
 722        prepare_pack_ix();
 723        for (i = 0, entry = objects; i < nr_objects; i++, entry++)
 724                check_object(entry);
 725
 726        if (nr_objects == nr_result) {
 727                /*
 728                 * Depth of objects that depend on the entry -- this
 729                 * is subtracted from depth-max to break too deep
 730                 * delta chain because of delta data reusing.
 731                 * However, we loosen this restriction when we know we
 732                 * are creating a thin pack -- it will have to be
 733                 * expanded on the other end anyway, so do not
 734                 * artificially cut the delta chain and let it go as
 735                 * deep as it wants.
 736                 */
 737                for (i = 0, entry = objects; i < nr_objects; i++, entry++)
 738                        if (!entry->delta && entry->delta_child)
 739                                entry->delta_limit =
 740                                        check_delta_limit(entry, 1);
 741        }
 742}
 743
 744typedef int (*entry_sort_t)(const struct object_entry *, const struct object_entry *);
 745
 746static entry_sort_t current_sort;
 747
 748static int sort_comparator(const void *_a, const void *_b)
 749{
 750        struct object_entry *a = *(struct object_entry **)_a;
 751        struct object_entry *b = *(struct object_entry **)_b;
 752        return current_sort(a,b);
 753}
 754
 755static struct object_entry **create_sorted_list(entry_sort_t sort)
 756{
 757        struct object_entry **list = xmalloc(nr_objects * sizeof(struct object_entry *));
 758        int i;
 759
 760        for (i = 0; i < nr_objects; i++)
 761                list[i] = objects + i;
 762        current_sort = sort;
 763        qsort(list, nr_objects, sizeof(struct object_entry *), sort_comparator);
 764        return list;
 765}
 766
 767static int sha1_sort(const struct object_entry *a, const struct object_entry *b)
 768{
 769        return memcmp(a->sha1, b->sha1, 20);
 770}
 771
 772static struct object_entry **create_final_object_list(void)
 773{
 774        struct object_entry **list;
 775        int i, j;
 776
 777        for (i = nr_result = 0; i < nr_objects; i++)
 778                if (!objects[i].preferred_base)
 779                        nr_result++;
 780        list = xmalloc(nr_result * sizeof(struct object_entry *));
 781        for (i = j = 0; i < nr_objects; i++) {
 782                if (!objects[i].preferred_base)
 783                        list[j++] = objects + i;
 784        }
 785        current_sort = sha1_sort;
 786        qsort(list, nr_result, sizeof(struct object_entry *), sort_comparator);
 787        return list;
 788}
 789
 790static int type_size_sort(const struct object_entry *a, const struct object_entry *b)
 791{
 792        if (a->type < b->type)
 793                return -1;
 794        if (a->type > b->type)
 795                return 1;
 796        if (a->hash < b->hash)
 797                return -1;
 798        if (a->hash > b->hash)
 799                return 1;
 800        if (a->preferred_base < b->preferred_base)
 801                return -1;
 802        if (a->preferred_base > b->preferred_base)
 803                return 1;
 804        if (a->size < b->size)
 805                return -1;
 806        if (a->size > b->size)
 807                return 1;
 808        return a < b ? -1 : (a > b);
 809}
 810
 811struct unpacked {
 812        struct object_entry *entry;
 813        void *data;
 814};
 815
 816/*
 817 * We search for deltas _backwards_ in a list sorted by type and
 818 * by size, so that we see progressively smaller and smaller files.
 819 * That's because we prefer deltas to be from the bigger file
 820 * to the smaller - deletes are potentially cheaper, but perhaps
 821 * more importantly, the bigger file is likely the more recent
 822 * one.
 823 */
 824static int try_delta(struct unpacked *cur, struct unpacked *old, unsigned max_depth)
 825{
 826        struct object_entry *cur_entry = cur->entry;
 827        struct object_entry *old_entry = old->entry;
 828        unsigned long size, oldsize, delta_size, sizediff;
 829        long max_size;
 830        void *delta_buf;
 831
 832        /* Don't bother doing diffs between different types */
 833        if (cur_entry->type != old_entry->type)
 834                return -1;
 835
 836        /* We do not compute delta to *create* objects we are not
 837         * going to pack.
 838         */
 839        if (cur_entry->preferred_base)
 840                return -1;
 841
 842        /* If the current object is at pack edge, take the depth the
 843         * objects that depend on the current object into account --
 844         * otherwise they would become too deep.
 845         */
 846        if (cur_entry->delta_child) {
 847                if (max_depth <= cur_entry->delta_limit)
 848                        return 0;
 849                max_depth -= cur_entry->delta_limit;
 850        }
 851
 852        size = cur_entry->size;
 853        oldsize = old_entry->size;
 854        sizediff = oldsize > size ? oldsize - size : size - oldsize;
 855
 856        if (size < 50)
 857                return -1;
 858        if (old_entry->depth >= max_depth)
 859                return 0;
 860
 861        /*
 862         * NOTE!
 863         *
 864         * We always delta from the bigger to the smaller, since that's
 865         * more space-efficient (deletes don't have to say _what_ they
 866         * delete).
 867         */
 868        max_size = size / 2 - 20;
 869        if (cur_entry->delta)
 870                max_size = cur_entry->delta_size-1;
 871        if (sizediff >= max_size)
 872                return -1;
 873        delta_buf = diff_delta(old->data, oldsize,
 874                               cur->data, size, &delta_size, max_size);
 875        if (!delta_buf)
 876                return 0;
 877        cur_entry->delta = old_entry;
 878        cur_entry->delta_size = delta_size;
 879        cur_entry->depth = old_entry->depth + 1;
 880        free(delta_buf);
 881        return 0;
 882}
 883
 884static void progress_interval(int signum)
 885{
 886        progress_update = 1;
 887}
 888
 889static void find_deltas(struct object_entry **list, int window, int depth)
 890{
 891        int i, idx;
 892        unsigned int array_size = window * sizeof(struct unpacked);
 893        struct unpacked *array = xmalloc(array_size);
 894        unsigned processed = 0;
 895        unsigned last_percent = 999;
 896
 897        memset(array, 0, array_size);
 898        i = nr_objects;
 899        idx = 0;
 900        if (progress)
 901                fprintf(stderr, "Deltifying %d objects.\n", nr_result);
 902
 903        while (--i >= 0) {
 904                struct object_entry *entry = list[i];
 905                struct unpacked *n = array + idx;
 906                unsigned long size;
 907                char type[10];
 908                int j;
 909
 910                if (!entry->preferred_base)
 911                        processed++;
 912
 913                if (progress) {
 914                        unsigned percent = processed * 100 / nr_result;
 915                        if (percent != last_percent || progress_update) {
 916                                fprintf(stderr, "%4u%% (%u/%u) done\r",
 917                                        percent, processed, nr_result);
 918                                progress_update = 0;
 919                                last_percent = percent;
 920                        }
 921                }
 922
 923                if (entry->delta)
 924                        /* This happens if we decided to reuse existing
 925                         * delta from a pack.  "!no_reuse_delta &&" is implied.
 926                         */
 927                        continue;
 928
 929                free(n->data);
 930                n->entry = entry;
 931                n->data = read_sha1_file(entry->sha1, type, &size);
 932                if (size != entry->size)
 933                        die("object %s inconsistent object length (%lu vs %lu)", sha1_to_hex(entry->sha1), size, entry->size);
 934
 935                j = window;
 936                while (--j > 0) {
 937                        unsigned int other_idx = idx + j;
 938                        struct unpacked *m;
 939                        if (other_idx >= window)
 940                                other_idx -= window;
 941                        m = array + other_idx;
 942                        if (!m->entry)
 943                                break;
 944                        if (try_delta(n, m, depth) < 0)
 945                                break;
 946                }
 947#if 0
 948                /* if we made n a delta, and if n is already at max
 949                 * depth, leaving it in the window is pointless.  we
 950                 * should evict it first.
 951                 * ... in theory only; somehow this makes things worse.
 952                 */
 953                if (entry->delta && depth <= entry->depth)
 954                        continue;
 955#endif
 956                idx++;
 957                if (idx >= window)
 958                        idx = 0;
 959        }
 960
 961        if (progress)
 962                fputc('\n', stderr);
 963
 964        for (i = 0; i < window; ++i)
 965                free(array[i].data);
 966        free(array);
 967}
 968
 969static void prepare_pack(int window, int depth)
 970{
 971        get_object_details();
 972        sorted_by_type = create_sorted_list(type_size_sort);
 973        if (window && depth)
 974                find_deltas(sorted_by_type, window+1, depth);
 975}
 976
 977static int reuse_cached_pack(unsigned char *sha1, int pack_to_stdout)
 978{
 979        static const char cache[] = "pack-cache/pack-%s.%s";
 980        char *cached_pack, *cached_idx;
 981        int ifd, ofd, ifd_ix = -1;
 982
 983        cached_pack = git_path(cache, sha1_to_hex(sha1), "pack");
 984        ifd = open(cached_pack, O_RDONLY);
 985        if (ifd < 0)
 986                return 0;
 987
 988        if (!pack_to_stdout) {
 989                cached_idx = git_path(cache, sha1_to_hex(sha1), "idx");
 990                ifd_ix = open(cached_idx, O_RDONLY);
 991                if (ifd_ix < 0) {
 992                        close(ifd);
 993                        return 0;
 994                }
 995        }
 996
 997        if (progress)
 998                fprintf(stderr, "Reusing %d objects pack %s\n", nr_objects,
 999                        sha1_to_hex(sha1));
1000
1001        if (pack_to_stdout) {
1002                if (copy_fd(ifd, 1))
1003                        exit(1);
1004                close(ifd);
1005        }
1006        else {
1007                char name[PATH_MAX];
1008                snprintf(name, sizeof(name),
1009                         "%s-%s.%s", base_name, sha1_to_hex(sha1), "pack");
1010                ofd = open(name, O_CREAT | O_EXCL | O_WRONLY, 0666);
1011                if (ofd < 0)
1012                        die("unable to open %s (%s)", name, strerror(errno));
1013                if (copy_fd(ifd, ofd))
1014                        exit(1);
1015                close(ifd);
1016
1017                snprintf(name, sizeof(name),
1018                         "%s-%s.%s", base_name, sha1_to_hex(sha1), "idx");
1019                ofd = open(name, O_CREAT | O_EXCL | O_WRONLY, 0666);
1020                if (ofd < 0)
1021                        die("unable to open %s (%s)", name, strerror(errno));
1022                if (copy_fd(ifd_ix, ofd))
1023                        exit(1);
1024                close(ifd_ix);
1025                puts(sha1_to_hex(sha1));
1026        }
1027
1028        return 1;
1029}
1030
1031static void setup_progress_signal(void)
1032{
1033        struct sigaction sa;
1034        struct itimerval v;
1035
1036        memset(&sa, 0, sizeof(sa));
1037        sa.sa_handler = progress_interval;
1038        sigemptyset(&sa.sa_mask);
1039        sa.sa_flags = SA_RESTART;
1040        sigaction(SIGALRM, &sa, NULL);
1041
1042        v.it_interval.tv_sec = 1;
1043        v.it_interval.tv_usec = 0;
1044        v.it_value = v.it_interval;
1045        setitimer(ITIMER_REAL, &v, NULL);
1046}
1047
1048int main(int argc, char **argv)
1049{
1050        SHA_CTX ctx;
1051        char line[PATH_MAX + 20];
1052        int window = 10, depth = 10, pack_to_stdout = 0;
1053        struct object_entry **list;
1054        int i;
1055
1056        setup_git_directory();
1057
1058        for (i = 1; i < argc; i++) {
1059                const char *arg = argv[i];
1060
1061                if (*arg == '-') {
1062                        if (!strcmp("--non-empty", arg)) {
1063                                non_empty = 1;
1064                                continue;
1065                        }
1066                        if (!strcmp("--local", arg)) {
1067                                local = 1;
1068                                continue;
1069                        }
1070                        if (!strcmp("--incremental", arg)) {
1071                                incremental = 1;
1072                                continue;
1073                        }
1074                        if (!strncmp("--window=", arg, 9)) {
1075                                char *end;
1076                                window = strtoul(arg+9, &end, 0);
1077                                if (!arg[9] || *end)
1078                                        usage(pack_usage);
1079                                continue;
1080                        }
1081                        if (!strncmp("--depth=", arg, 8)) {
1082                                char *end;
1083                                depth = strtoul(arg+8, &end, 0);
1084                                if (!arg[8] || *end)
1085                                        usage(pack_usage);
1086                                continue;
1087                        }
1088                        if (!strcmp("-q", arg)) {
1089                                progress = 0;
1090                                continue;
1091                        }
1092                        if (!strcmp("--no-reuse-delta", arg)) {
1093                                no_reuse_delta = 1;
1094                                continue;
1095                        }
1096                        if (!strcmp("--stdout", arg)) {
1097                                pack_to_stdout = 1;
1098                                continue;
1099                        }
1100                        usage(pack_usage);
1101                }
1102                if (base_name)
1103                        usage(pack_usage);
1104                base_name = arg;
1105        }
1106
1107        if (pack_to_stdout != !base_name)
1108                usage(pack_usage);
1109
1110        prepare_packed_git();
1111
1112        if (progress) {
1113                fprintf(stderr, "Generating pack...\n");
1114                setup_progress_signal();
1115        }
1116
1117        for (;;) {
1118                unsigned char sha1[20];
1119
1120                if (!fgets(line, sizeof(line), stdin)) {
1121                        if (feof(stdin))
1122                                break;
1123                        if (!ferror(stdin))
1124                                die("fgets returned NULL, not EOF, not error!");
1125                        if (errno != EINTR)
1126                                die("fgets: %s", strerror(errno));
1127                        clearerr(stdin);
1128                        continue;
1129                }
1130
1131                if (line[0] == '-') {
1132                        if (get_sha1_hex(line+1, sha1))
1133                                die("expected edge sha1, got garbage:\n %s",
1134                                    line+1);
1135                        add_preferred_base(sha1);
1136                        continue;
1137                }
1138                if (get_sha1_hex(line, sha1))
1139                        die("expected sha1, got garbage:\n %s", line);
1140                add_object_entry(sha1, name_hash(NULL, line+41), 0);
1141        }
1142        if (progress)
1143                fprintf(stderr, "Done counting %d objects.\n", nr_objects);
1144        sorted_by_sha = create_final_object_list();
1145        if (non_empty && !nr_result)
1146                return 0;
1147
1148        SHA1_Init(&ctx);
1149        list = sorted_by_sha;
1150        for (i = 0; i < nr_result; i++) {
1151                struct object_entry *entry = *list++;
1152                SHA1_Update(&ctx, entry->sha1, 20);
1153        }
1154        SHA1_Final(object_list_sha1, &ctx);
1155        if (progress && (nr_objects != nr_result))
1156                fprintf(stderr, "Result has %d objects.\n", nr_result);
1157
1158        if (reuse_cached_pack(object_list_sha1, pack_to_stdout))
1159                ;
1160        else {
1161                if (nr_result)
1162                        prepare_pack(window, depth);
1163                if (progress && pack_to_stdout) {
1164                        /* the other end usually displays progress itself */
1165                        struct itimerval v = {{0,},};
1166                        setitimer(ITIMER_REAL, &v, NULL);
1167                        signal(SIGALRM, SIG_IGN );
1168                        progress_update = 0;
1169                }
1170                write_pack_file();
1171                if (!pack_to_stdout) {
1172                        write_index_file();
1173                        puts(sha1_to_hex(object_list_sha1));
1174                }
1175        }
1176        if (progress)
1177                fprintf(stderr, "Total %d, written %d (delta %d), reused %d (delta %d)\n",
1178                        nr_result, written, written_delta, reused, reused_delta);
1179        return 0;
1180}