builtin / pack-objects.con commit Merge branch 'aw/gc-lockfile-fscanf-fix' into maint (14431c7)
   1#include "builtin.h"
   2#include "cache.h"
   3#include "config.h"
   4#include "attr.h"
   5#include "object.h"
   6#include "blob.h"
   7#include "commit.h"
   8#include "tag.h"
   9#include "tree.h"
  10#include "delta.h"
  11#include "pack.h"
  12#include "pack-revindex.h"
  13#include "csum-file.h"
  14#include "tree-walk.h"
  15#include "diff.h"
  16#include "revision.h"
  17#include "list-objects.h"
  18#include "pack-objects.h"
  19#include "progress.h"
  20#include "refs.h"
  21#include "streaming.h"
  22#include "thread-utils.h"
  23#include "pack-bitmap.h"
  24#include "reachable.h"
  25#include "sha1-array.h"
  26#include "argv-array.h"
  27#include "mru.h"
  28
  29static const char *pack_usage[] = {
  30        N_("git pack-objects --stdout [<options>...] [< <ref-list> | < <object-list>]"),
  31        N_("git pack-objects [<options>...] <base-name> [< <ref-list> | < <object-list>]"),
  32        NULL
  33};
  34
  35/*
  36 * Objects we are going to pack are collected in the `to_pack` structure.
  37 * It contains an array (dynamically expanded) of the object data, and a map
  38 * that can resolve SHA1s to their position in the array.
  39 */
  40static struct packing_data to_pack;
  41
  42static struct pack_idx_entry **written_list;
  43static uint32_t nr_result, nr_written;
  44
  45static int non_empty;
  46static int reuse_delta = 1, reuse_object = 1;
  47static int keep_unreachable, unpack_unreachable, include_tag;
  48static timestamp_t unpack_unreachable_expiration;
  49static int pack_loose_unreachable;
  50static int local;
  51static int have_non_local_packs;
  52static int incremental;
  53static int ignore_packed_keep;
  54static int allow_ofs_delta;
  55static struct pack_idx_option pack_idx_opts;
  56static const char *base_name;
  57static int progress = 1;
  58static int window = 10;
  59static unsigned long pack_size_limit;
  60static int depth = 50;
  61static int delta_search_threads;
  62static int pack_to_stdout;
  63static int num_preferred_base;
  64static struct progress *progress_state;
  65
  66static struct packed_git *reuse_packfile;
  67static uint32_t reuse_packfile_objects;
  68static off_t reuse_packfile_offset;
  69
  70static int use_bitmap_index_default = 1;
  71static int use_bitmap_index = -1;
  72static int write_bitmap_index;
  73static uint16_t write_bitmap_options;
  74
  75static unsigned long delta_cache_size = 0;
  76static unsigned long max_delta_cache_size = 256 * 1024 * 1024;
  77static unsigned long cache_max_small_delta_size = 1000;
  78
  79static unsigned long window_memory_limit = 0;
  80
  81/*
  82 * stats
  83 */
  84static uint32_t written, written_delta;
  85static uint32_t reused, reused_delta;
  86
  87/*
  88 * Indexed commits
  89 */
  90static struct commit **indexed_commits;
  91static unsigned int indexed_commits_nr;
  92static unsigned int indexed_commits_alloc;
  93
  94static void index_commit_for_bitmap(struct commit *commit)
  95{
  96        if (indexed_commits_nr >= indexed_commits_alloc) {
  97                indexed_commits_alloc = (indexed_commits_alloc + 32) * 2;
  98                REALLOC_ARRAY(indexed_commits, indexed_commits_alloc);
  99        }
 100
 101        indexed_commits[indexed_commits_nr++] = commit;
 102}
 103
 104static void *get_delta(struct object_entry *entry)
 105{
 106        unsigned long size, base_size, delta_size;
 107        void *buf, *base_buf, *delta_buf;
 108        enum object_type type;
 109
 110        buf = read_sha1_file(entry->idx.oid.hash, &type, &size);
 111        if (!buf)
 112                die("unable to read %s", oid_to_hex(&entry->idx.oid));
 113        base_buf = read_sha1_file(entry->delta->idx.oid.hash, &type,
 114                                  &base_size);
 115        if (!base_buf)
 116                die("unable to read %s",
 117                    oid_to_hex(&entry->delta->idx.oid));
 118        delta_buf = diff_delta(base_buf, base_size,
 119                               buf, size, &delta_size, 0);
 120        if (!delta_buf || delta_size != entry->delta_size)
 121                die("delta size changed");
 122        free(buf);
 123        free(base_buf);
 124        return delta_buf;
 125}
 126
 127static unsigned long do_compress(void **pptr, unsigned long size)
 128{
 129        git_zstream stream;
 130        void *in, *out;
 131        unsigned long maxsize;
 132
 133        git_deflate_init(&stream, pack_compression_level);
 134        maxsize = git_deflate_bound(&stream, size);
 135
 136        in = *pptr;
 137        out = xmalloc(maxsize);
 138        *pptr = out;
 139
 140        stream.next_in = in;
 141        stream.avail_in = size;
 142        stream.next_out = out;
 143        stream.avail_out = maxsize;
 144        while (git_deflate(&stream, Z_FINISH) == Z_OK)
 145                ; /* nothing */
 146        git_deflate_end(&stream);
 147
 148        free(in);
 149        return stream.total_out;
 150}
 151
 152static unsigned long write_large_blob_data(struct git_istream *st, struct sha1file *f,
 153                                           const unsigned char *sha1)
 154{
 155        git_zstream stream;
 156        unsigned char ibuf[1024 * 16];
 157        unsigned char obuf[1024 * 16];
 158        unsigned long olen = 0;
 159
 160        git_deflate_init(&stream, pack_compression_level);
 161
 162        for (;;) {
 163                ssize_t readlen;
 164                int zret = Z_OK;
 165                readlen = read_istream(st, ibuf, sizeof(ibuf));
 166                if (readlen == -1)
 167                        die(_("unable to read %s"), sha1_to_hex(sha1));
 168
 169                stream.next_in = ibuf;
 170                stream.avail_in = readlen;
 171                while ((stream.avail_in || readlen == 0) &&
 172                       (zret == Z_OK || zret == Z_BUF_ERROR)) {
 173                        stream.next_out = obuf;
 174                        stream.avail_out = sizeof(obuf);
 175                        zret = git_deflate(&stream, readlen ? 0 : Z_FINISH);
 176                        sha1write(f, obuf, stream.next_out - obuf);
 177                        olen += stream.next_out - obuf;
 178                }
 179                if (stream.avail_in)
 180                        die(_("deflate error (%d)"), zret);
 181                if (readlen == 0) {
 182                        if (zret != Z_STREAM_END)
 183                                die(_("deflate error (%d)"), zret);
 184                        break;
 185                }
 186        }
 187        git_deflate_end(&stream);
 188        return olen;
 189}
 190
 191/*
 192 * we are going to reuse the existing object data as is.  make
 193 * sure it is not corrupt.
 194 */
 195static int check_pack_inflate(struct packed_git *p,
 196                struct pack_window **w_curs,
 197                off_t offset,
 198                off_t len,
 199                unsigned long expect)
 200{
 201        git_zstream stream;
 202        unsigned char fakebuf[4096], *in;
 203        int st;
 204
 205        memset(&stream, 0, sizeof(stream));
 206        git_inflate_init(&stream);
 207        do {
 208                in = use_pack(p, w_curs, offset, &stream.avail_in);
 209                stream.next_in = in;
 210                stream.next_out = fakebuf;
 211                stream.avail_out = sizeof(fakebuf);
 212                st = git_inflate(&stream, Z_FINISH);
 213                offset += stream.next_in - in;
 214        } while (st == Z_OK || st == Z_BUF_ERROR);
 215        git_inflate_end(&stream);
 216        return (st == Z_STREAM_END &&
 217                stream.total_out == expect &&
 218                stream.total_in == len) ? 0 : -1;
 219}
 220
 221static void copy_pack_data(struct sha1file *f,
 222                struct packed_git *p,
 223                struct pack_window **w_curs,
 224                off_t offset,
 225                off_t len)
 226{
 227        unsigned char *in;
 228        unsigned long avail;
 229
 230        while (len) {
 231                in = use_pack(p, w_curs, offset, &avail);
 232                if (avail > len)
 233                        avail = (unsigned long)len;
 234                sha1write(f, in, avail);
 235                offset += avail;
 236                len -= avail;
 237        }
 238}
 239
 240/* Return 0 if we will bust the pack-size limit */
 241static unsigned long write_no_reuse_object(struct sha1file *f, struct object_entry *entry,
 242                                           unsigned long limit, int usable_delta)
 243{
 244        unsigned long size, datalen;
 245        unsigned char header[MAX_PACK_OBJECT_HEADER],
 246                      dheader[MAX_PACK_OBJECT_HEADER];
 247        unsigned hdrlen;
 248        enum object_type type;
 249        void *buf;
 250        struct git_istream *st = NULL;
 251
 252        if (!usable_delta) {
 253                if (entry->type == OBJ_BLOB &&
 254                    entry->size > big_file_threshold &&
 255                    (st = open_istream(entry->idx.oid.hash, &type, &size, NULL)) != NULL)
 256                        buf = NULL;
 257                else {
 258                        buf = read_sha1_file(entry->idx.oid.hash, &type,
 259                                             &size);
 260                        if (!buf)
 261                                die(_("unable to read %s"),
 262                                    oid_to_hex(&entry->idx.oid));
 263                }
 264                /*
 265                 * make sure no cached delta data remains from a
 266                 * previous attempt before a pack split occurred.
 267                 */
 268                FREE_AND_NULL(entry->delta_data);
 269                entry->z_delta_size = 0;
 270        } else if (entry->delta_data) {
 271                size = entry->delta_size;
 272                buf = entry->delta_data;
 273                entry->delta_data = NULL;
 274                type = (allow_ofs_delta && entry->delta->idx.offset) ?
 275                        OBJ_OFS_DELTA : OBJ_REF_DELTA;
 276        } else {
 277                buf = get_delta(entry);
 278                size = entry->delta_size;
 279                type = (allow_ofs_delta && entry->delta->idx.offset) ?
 280                        OBJ_OFS_DELTA : OBJ_REF_DELTA;
 281        }
 282
 283        if (st) /* large blob case, just assume we don't compress well */
 284                datalen = size;
 285        else if (entry->z_delta_size)
 286                datalen = entry->z_delta_size;
 287        else
 288                datalen = do_compress(&buf, size);
 289
 290        /*
 291         * The object header is a byte of 'type' followed by zero or
 292         * more bytes of length.
 293         */
 294        hdrlen = encode_in_pack_object_header(header, sizeof(header),
 295                                              type, size);
 296
 297        if (type == OBJ_OFS_DELTA) {
 298                /*
 299                 * Deltas with relative base contain an additional
 300                 * encoding of the relative offset for the delta
 301                 * base from this object's position in the pack.
 302                 */
 303                off_t ofs = entry->idx.offset - entry->delta->idx.offset;
 304                unsigned pos = sizeof(dheader) - 1;
 305                dheader[pos] = ofs & 127;
 306                while (ofs >>= 7)
 307                        dheader[--pos] = 128 | (--ofs & 127);
 308                if (limit && hdrlen + sizeof(dheader) - pos + datalen + 20 >= limit) {
 309                        if (st)
 310                                close_istream(st);
 311                        free(buf);
 312                        return 0;
 313                }
 314                sha1write(f, header, hdrlen);
 315                sha1write(f, dheader + pos, sizeof(dheader) - pos);
 316                hdrlen += sizeof(dheader) - pos;
 317        } else if (type == OBJ_REF_DELTA) {
 318                /*
 319                 * Deltas with a base reference contain
 320                 * an additional 20 bytes for the base sha1.
 321                 */
 322                if (limit && hdrlen + 20 + datalen + 20 >= limit) {
 323                        if (st)
 324                                close_istream(st);
 325                        free(buf);
 326                        return 0;
 327                }
 328                sha1write(f, header, hdrlen);
 329                sha1write(f, entry->delta->idx.oid.hash, 20);
 330                hdrlen += 20;
 331        } else {
 332                if (limit && hdrlen + datalen + 20 >= limit) {
 333                        if (st)
 334                                close_istream(st);
 335                        free(buf);
 336                        return 0;
 337                }
 338                sha1write(f, header, hdrlen);
 339        }
 340        if (st) {
 341                datalen = write_large_blob_data(st, f, entry->idx.oid.hash);
 342                close_istream(st);
 343        } else {
 344                sha1write(f, buf, datalen);
 345                free(buf);
 346        }
 347
 348        return hdrlen + datalen;
 349}
 350
 351/* Return 0 if we will bust the pack-size limit */
 352static off_t write_reuse_object(struct sha1file *f, struct object_entry *entry,
 353                                unsigned long limit, int usable_delta)
 354{
 355        struct packed_git *p = entry->in_pack;
 356        struct pack_window *w_curs = NULL;
 357        struct revindex_entry *revidx;
 358        off_t offset;
 359        enum object_type type = entry->type;
 360        off_t datalen;
 361        unsigned char header[MAX_PACK_OBJECT_HEADER],
 362                      dheader[MAX_PACK_OBJECT_HEADER];
 363        unsigned hdrlen;
 364
 365        if (entry->delta)
 366                type = (allow_ofs_delta && entry->delta->idx.offset) ?
 367                        OBJ_OFS_DELTA : OBJ_REF_DELTA;
 368        hdrlen = encode_in_pack_object_header(header, sizeof(header),
 369                                              type, entry->size);
 370
 371        offset = entry->in_pack_offset;
 372        revidx = find_pack_revindex(p, offset);
 373        datalen = revidx[1].offset - offset;
 374        if (!pack_to_stdout && p->index_version > 1 &&
 375            check_pack_crc(p, &w_curs, offset, datalen, revidx->nr)) {
 376                error("bad packed object CRC for %s",
 377                      oid_to_hex(&entry->idx.oid));
 378                unuse_pack(&w_curs);
 379                return write_no_reuse_object(f, entry, limit, usable_delta);
 380        }
 381
 382        offset += entry->in_pack_header_size;
 383        datalen -= entry->in_pack_header_size;
 384
 385        if (!pack_to_stdout && p->index_version == 1 &&
 386            check_pack_inflate(p, &w_curs, offset, datalen, entry->size)) {
 387                error("corrupt packed object for %s",
 388                      oid_to_hex(&entry->idx.oid));
 389                unuse_pack(&w_curs);
 390                return write_no_reuse_object(f, entry, limit, usable_delta);
 391        }
 392
 393        if (type == OBJ_OFS_DELTA) {
 394                off_t ofs = entry->idx.offset - entry->delta->idx.offset;
 395                unsigned pos = sizeof(dheader) - 1;
 396                dheader[pos] = ofs & 127;
 397                while (ofs >>= 7)
 398                        dheader[--pos] = 128 | (--ofs & 127);
 399                if (limit && hdrlen + sizeof(dheader) - pos + datalen + 20 >= limit) {
 400                        unuse_pack(&w_curs);
 401                        return 0;
 402                }
 403                sha1write(f, header, hdrlen);
 404                sha1write(f, dheader + pos, sizeof(dheader) - pos);
 405                hdrlen += sizeof(dheader) - pos;
 406                reused_delta++;
 407        } else if (type == OBJ_REF_DELTA) {
 408                if (limit && hdrlen + 20 + datalen + 20 >= limit) {
 409                        unuse_pack(&w_curs);
 410                        return 0;
 411                }
 412                sha1write(f, header, hdrlen);
 413                sha1write(f, entry->delta->idx.oid.hash, 20);
 414                hdrlen += 20;
 415                reused_delta++;
 416        } else {
 417                if (limit && hdrlen + datalen + 20 >= limit) {
 418                        unuse_pack(&w_curs);
 419                        return 0;
 420                }
 421                sha1write(f, header, hdrlen);
 422        }
 423        copy_pack_data(f, p, &w_curs, offset, datalen);
 424        unuse_pack(&w_curs);
 425        reused++;
 426        return hdrlen + datalen;
 427}
 428
 429/* Return 0 if we will bust the pack-size limit */
 430static off_t write_object(struct sha1file *f,
 431                          struct object_entry *entry,
 432                          off_t write_offset)
 433{
 434        unsigned long limit;
 435        off_t len;
 436        int usable_delta, to_reuse;
 437
 438        if (!pack_to_stdout)
 439                crc32_begin(f);
 440
 441        /* apply size limit if limited packsize and not first object */
 442        if (!pack_size_limit || !nr_written)
 443                limit = 0;
 444        else if (pack_size_limit <= write_offset)
 445                /*
 446                 * the earlier object did not fit the limit; avoid
 447                 * mistaking this with unlimited (i.e. limit = 0).
 448                 */
 449                limit = 1;
 450        else
 451                limit = pack_size_limit - write_offset;
 452
 453        if (!entry->delta)
 454                usable_delta = 0;       /* no delta */
 455        else if (!pack_size_limit)
 456               usable_delta = 1;        /* unlimited packfile */
 457        else if (entry->delta->idx.offset == (off_t)-1)
 458                usable_delta = 0;       /* base was written to another pack */
 459        else if (entry->delta->idx.offset)
 460                usable_delta = 1;       /* base already exists in this pack */
 461        else
 462                usable_delta = 0;       /* base could end up in another pack */
 463
 464        if (!reuse_object)
 465                to_reuse = 0;   /* explicit */
 466        else if (!entry->in_pack)
 467                to_reuse = 0;   /* can't reuse what we don't have */
 468        else if (entry->type == OBJ_REF_DELTA || entry->type == OBJ_OFS_DELTA)
 469                                /* check_object() decided it for us ... */
 470                to_reuse = usable_delta;
 471                                /* ... but pack split may override that */
 472        else if (entry->type != entry->in_pack_type)
 473                to_reuse = 0;   /* pack has delta which is unusable */
 474        else if (entry->delta)
 475                to_reuse = 0;   /* we want to pack afresh */
 476        else
 477                to_reuse = 1;   /* we have it in-pack undeltified,
 478                                 * and we do not need to deltify it.
 479                                 */
 480
 481        if (!to_reuse)
 482                len = write_no_reuse_object(f, entry, limit, usable_delta);
 483        else
 484                len = write_reuse_object(f, entry, limit, usable_delta);
 485        if (!len)
 486                return 0;
 487
 488        if (usable_delta)
 489                written_delta++;
 490        written++;
 491        if (!pack_to_stdout)
 492                entry->idx.crc32 = crc32_end(f);
 493        return len;
 494}
 495
 496enum write_one_status {
 497        WRITE_ONE_SKIP = -1, /* already written */
 498        WRITE_ONE_BREAK = 0, /* writing this will bust the limit; not written */
 499        WRITE_ONE_WRITTEN = 1, /* normal */
 500        WRITE_ONE_RECURSIVE = 2 /* already scheduled to be written */
 501};
 502
 503static enum write_one_status write_one(struct sha1file *f,
 504                                       struct object_entry *e,
 505                                       off_t *offset)
 506{
 507        off_t size;
 508        int recursing;
 509
 510        /*
 511         * we set offset to 1 (which is an impossible value) to mark
 512         * the fact that this object is involved in "write its base
 513         * first before writing a deltified object" recursion.
 514         */
 515        recursing = (e->idx.offset == 1);
 516        if (recursing) {
 517                warning("recursive delta detected for object %s",
 518                        oid_to_hex(&e->idx.oid));
 519                return WRITE_ONE_RECURSIVE;
 520        } else if (e->idx.offset || e->preferred_base) {
 521                /* offset is non zero if object is written already. */
 522                return WRITE_ONE_SKIP;
 523        }
 524
 525        /* if we are deltified, write out base object first. */
 526        if (e->delta) {
 527                e->idx.offset = 1; /* now recurse */
 528                switch (write_one(f, e->delta, offset)) {
 529                case WRITE_ONE_RECURSIVE:
 530                        /* we cannot depend on this one */
 531                        e->delta = NULL;
 532                        break;
 533                default:
 534                        break;
 535                case WRITE_ONE_BREAK:
 536                        e->idx.offset = recursing;
 537                        return WRITE_ONE_BREAK;
 538                }
 539        }
 540
 541        e->idx.offset = *offset;
 542        size = write_object(f, e, *offset);
 543        if (!size) {
 544                e->idx.offset = recursing;
 545                return WRITE_ONE_BREAK;
 546        }
 547        written_list[nr_written++] = &e->idx;
 548
 549        /* make sure off_t is sufficiently large not to wrap */
 550        if (signed_add_overflows(*offset, size))
 551                die("pack too large for current definition of off_t");
 552        *offset += size;
 553        return WRITE_ONE_WRITTEN;
 554}
 555
 556static int mark_tagged(const char *path, const struct object_id *oid, int flag,
 557                       void *cb_data)
 558{
 559        unsigned char peeled[20];
 560        struct object_entry *entry = packlist_find(&to_pack, oid->hash, NULL);
 561
 562        if (entry)
 563                entry->tagged = 1;
 564        if (!peel_ref(path, peeled)) {
 565                entry = packlist_find(&to_pack, peeled, NULL);
 566                if (entry)
 567                        entry->tagged = 1;
 568        }
 569        return 0;
 570}
 571
 572static inline void add_to_write_order(struct object_entry **wo,
 573                               unsigned int *endp,
 574                               struct object_entry *e)
 575{
 576        if (e->filled)
 577                return;
 578        wo[(*endp)++] = e;
 579        e->filled = 1;
 580}
 581
 582static void add_descendants_to_write_order(struct object_entry **wo,
 583                                           unsigned int *endp,
 584                                           struct object_entry *e)
 585{
 586        int add_to_order = 1;
 587        while (e) {
 588                if (add_to_order) {
 589                        struct object_entry *s;
 590                        /* add this node... */
 591                        add_to_write_order(wo, endp, e);
 592                        /* all its siblings... */
 593                        for (s = e->delta_sibling; s; s = s->delta_sibling) {
 594                                add_to_write_order(wo, endp, s);
 595                        }
 596                }
 597                /* drop down a level to add left subtree nodes if possible */
 598                if (e->delta_child) {
 599                        add_to_order = 1;
 600                        e = e->delta_child;
 601                } else {
 602                        add_to_order = 0;
 603                        /* our sibling might have some children, it is next */
 604                        if (e->delta_sibling) {
 605                                e = e->delta_sibling;
 606                                continue;
 607                        }
 608                        /* go back to our parent node */
 609                        e = e->delta;
 610                        while (e && !e->delta_sibling) {
 611                                /* we're on the right side of a subtree, keep
 612                                 * going up until we can go right again */
 613                                e = e->delta;
 614                        }
 615                        if (!e) {
 616                                /* done- we hit our original root node */
 617                                return;
 618                        }
 619                        /* pass it off to sibling at this level */
 620                        e = e->delta_sibling;
 621                }
 622        };
 623}
 624
 625static void add_family_to_write_order(struct object_entry **wo,
 626                                      unsigned int *endp,
 627                                      struct object_entry *e)
 628{
 629        struct object_entry *root;
 630
 631        for (root = e; root->delta; root = root->delta)
 632                ; /* nothing */
 633        add_descendants_to_write_order(wo, endp, root);
 634}
 635
 636static struct object_entry **compute_write_order(void)
 637{
 638        unsigned int i, wo_end, last_untagged;
 639
 640        struct object_entry **wo;
 641        struct object_entry *objects = to_pack.objects;
 642
 643        for (i = 0; i < to_pack.nr_objects; i++) {
 644                objects[i].tagged = 0;
 645                objects[i].filled = 0;
 646                objects[i].delta_child = NULL;
 647                objects[i].delta_sibling = NULL;
 648        }
 649
 650        /*
 651         * Fully connect delta_child/delta_sibling network.
 652         * Make sure delta_sibling is sorted in the original
 653         * recency order.
 654         */
 655        for (i = to_pack.nr_objects; i > 0;) {
 656                struct object_entry *e = &objects[--i];
 657                if (!e->delta)
 658                        continue;
 659                /* Mark me as the first child */
 660                e->delta_sibling = e->delta->delta_child;
 661                e->delta->delta_child = e;
 662        }
 663
 664        /*
 665         * Mark objects that are at the tip of tags.
 666         */
 667        for_each_tag_ref(mark_tagged, NULL);
 668
 669        /*
 670         * Give the objects in the original recency order until
 671         * we see a tagged tip.
 672         */
 673        ALLOC_ARRAY(wo, to_pack.nr_objects);
 674        for (i = wo_end = 0; i < to_pack.nr_objects; i++) {
 675                if (objects[i].tagged)
 676                        break;
 677                add_to_write_order(wo, &wo_end, &objects[i]);
 678        }
 679        last_untagged = i;
 680
 681        /*
 682         * Then fill all the tagged tips.
 683         */
 684        for (; i < to_pack.nr_objects; i++) {
 685                if (objects[i].tagged)
 686                        add_to_write_order(wo, &wo_end, &objects[i]);
 687        }
 688
 689        /*
 690         * And then all remaining commits and tags.
 691         */
 692        for (i = last_untagged; i < to_pack.nr_objects; i++) {
 693                if (objects[i].type != OBJ_COMMIT &&
 694                    objects[i].type != OBJ_TAG)
 695                        continue;
 696                add_to_write_order(wo, &wo_end, &objects[i]);
 697        }
 698
 699        /*
 700         * And then all the trees.
 701         */
 702        for (i = last_untagged; i < to_pack.nr_objects; i++) {
 703                if (objects[i].type != OBJ_TREE)
 704                        continue;
 705                add_to_write_order(wo, &wo_end, &objects[i]);
 706        }
 707
 708        /*
 709         * Finally all the rest in really tight order
 710         */
 711        for (i = last_untagged; i < to_pack.nr_objects; i++) {
 712                if (!objects[i].filled)
 713                        add_family_to_write_order(wo, &wo_end, &objects[i]);
 714        }
 715
 716        if (wo_end != to_pack.nr_objects)
 717                die("ordered %u objects, expected %"PRIu32, wo_end, to_pack.nr_objects);
 718
 719        return wo;
 720}
 721
 722static off_t write_reused_pack(struct sha1file *f)
 723{
 724        unsigned char buffer[8192];
 725        off_t to_write, total;
 726        int fd;
 727
 728        if (!is_pack_valid(reuse_packfile))
 729                die("packfile is invalid: %s", reuse_packfile->pack_name);
 730
 731        fd = git_open(reuse_packfile->pack_name);
 732        if (fd < 0)
 733                die_errno("unable to open packfile for reuse: %s",
 734                          reuse_packfile->pack_name);
 735
 736        if (lseek(fd, sizeof(struct pack_header), SEEK_SET) == -1)
 737                die_errno("unable to seek in reused packfile");
 738
 739        if (reuse_packfile_offset < 0)
 740                reuse_packfile_offset = reuse_packfile->pack_size - 20;
 741
 742        total = to_write = reuse_packfile_offset - sizeof(struct pack_header);
 743
 744        while (to_write) {
 745                int read_pack = xread(fd, buffer, sizeof(buffer));
 746
 747                if (read_pack <= 0)
 748                        die_errno("unable to read from reused packfile");
 749
 750                if (read_pack > to_write)
 751                        read_pack = to_write;
 752
 753                sha1write(f, buffer, read_pack);
 754                to_write -= read_pack;
 755
 756                /*
 757                 * We don't know the actual number of objects written,
 758                 * only how many bytes written, how many bytes total, and
 759                 * how many objects total. So we can fake it by pretending all
 760                 * objects we are writing are the same size. This gives us a
 761                 * smooth progress meter, and at the end it matches the true
 762                 * answer.
 763                 */
 764                written = reuse_packfile_objects *
 765                                (((double)(total - to_write)) / total);
 766                display_progress(progress_state, written);
 767        }
 768
 769        close(fd);
 770        written = reuse_packfile_objects;
 771        display_progress(progress_state, written);
 772        return reuse_packfile_offset - sizeof(struct pack_header);
 773}
 774
 775static const char no_split_warning[] = N_(
 776"disabling bitmap writing, packs are split due to pack.packSizeLimit"
 777);
 778
 779static void write_pack_file(void)
 780{
 781        uint32_t i = 0, j;
 782        struct sha1file *f;
 783        off_t offset;
 784        uint32_t nr_remaining = nr_result;
 785        time_t last_mtime = 0;
 786        struct object_entry **write_order;
 787
 788        if (progress > pack_to_stdout)
 789                progress_state = start_progress(_("Writing objects"), nr_result);
 790        ALLOC_ARRAY(written_list, to_pack.nr_objects);
 791        write_order = compute_write_order();
 792
 793        do {
 794                unsigned char sha1[20];
 795                char *pack_tmp_name = NULL;
 796
 797                if (pack_to_stdout)
 798                        f = sha1fd_throughput(1, "<stdout>", progress_state);
 799                else
 800                        f = create_tmp_packfile(&pack_tmp_name);
 801
 802                offset = write_pack_header(f, nr_remaining);
 803
 804                if (reuse_packfile) {
 805                        off_t packfile_size;
 806                        assert(pack_to_stdout);
 807
 808                        packfile_size = write_reused_pack(f);
 809                        offset += packfile_size;
 810                }
 811
 812                nr_written = 0;
 813                for (; i < to_pack.nr_objects; i++) {
 814                        struct object_entry *e = write_order[i];
 815                        if (write_one(f, e, &offset) == WRITE_ONE_BREAK)
 816                                break;
 817                        display_progress(progress_state, written);
 818                }
 819
 820                /*
 821                 * Did we write the wrong # entries in the header?
 822                 * If so, rewrite it like in fast-import
 823                 */
 824                if (pack_to_stdout) {
 825                        sha1close(f, sha1, CSUM_CLOSE);
 826                } else if (nr_written == nr_remaining) {
 827                        sha1close(f, sha1, CSUM_FSYNC);
 828                } else {
 829                        int fd = sha1close(f, sha1, 0);
 830                        fixup_pack_header_footer(fd, sha1, pack_tmp_name,
 831                                                 nr_written, sha1, offset);
 832                        close(fd);
 833                        if (write_bitmap_index) {
 834                                warning(_(no_split_warning));
 835                                write_bitmap_index = 0;
 836                        }
 837                }
 838
 839                if (!pack_to_stdout) {
 840                        struct stat st;
 841                        struct strbuf tmpname = STRBUF_INIT;
 842
 843                        /*
 844                         * Packs are runtime accessed in their mtime
 845                         * order since newer packs are more likely to contain
 846                         * younger objects.  So if we are creating multiple
 847                         * packs then we should modify the mtime of later ones
 848                         * to preserve this property.
 849                         */
 850                        if (stat(pack_tmp_name, &st) < 0) {
 851                                warning_errno("failed to stat %s", pack_tmp_name);
 852                        } else if (!last_mtime) {
 853                                last_mtime = st.st_mtime;
 854                        } else {
 855                                struct utimbuf utb;
 856                                utb.actime = st.st_atime;
 857                                utb.modtime = --last_mtime;
 858                                if (utime(pack_tmp_name, &utb) < 0)
 859                                        warning_errno("failed utime() on %s", pack_tmp_name);
 860                        }
 861
 862                        strbuf_addf(&tmpname, "%s-", base_name);
 863
 864                        if (write_bitmap_index) {
 865                                bitmap_writer_set_checksum(sha1);
 866                                bitmap_writer_build_type_index(written_list, nr_written);
 867                        }
 868
 869                        finish_tmp_packfile(&tmpname, pack_tmp_name,
 870                                            written_list, nr_written,
 871                                            &pack_idx_opts, sha1);
 872
 873                        if (write_bitmap_index) {
 874                                strbuf_addf(&tmpname, "%s.bitmap", sha1_to_hex(sha1));
 875
 876                                stop_progress(&progress_state);
 877
 878                                bitmap_writer_show_progress(progress);
 879                                bitmap_writer_reuse_bitmaps(&to_pack);
 880                                bitmap_writer_select_commits(indexed_commits, indexed_commits_nr, -1);
 881                                bitmap_writer_build(&to_pack);
 882                                bitmap_writer_finish(written_list, nr_written,
 883                                                     tmpname.buf, write_bitmap_options);
 884                                write_bitmap_index = 0;
 885                        }
 886
 887                        strbuf_release(&tmpname);
 888                        free(pack_tmp_name);
 889                        puts(sha1_to_hex(sha1));
 890                }
 891
 892                /* mark written objects as written to previous pack */
 893                for (j = 0; j < nr_written; j++) {
 894                        written_list[j]->offset = (off_t)-1;
 895                }
 896                nr_remaining -= nr_written;
 897        } while (nr_remaining && i < to_pack.nr_objects);
 898
 899        free(written_list);
 900        free(write_order);
 901        stop_progress(&progress_state);
 902        if (written != nr_result)
 903                die("wrote %"PRIu32" objects while expecting %"PRIu32,
 904                        written, nr_result);
 905}
 906
 907static int no_try_delta(const char *path)
 908{
 909        static struct attr_check *check;
 910
 911        if (!check)
 912                check = attr_check_initl("delta", NULL);
 913        if (git_check_attr(path, check))
 914                return 0;
 915        if (ATTR_FALSE(check->items[0].value))
 916                return 1;
 917        return 0;
 918}
 919
 920/*
 921 * When adding an object, check whether we have already added it
 922 * to our packing list. If so, we can skip. However, if we are
 923 * being asked to excludei t, but the previous mention was to include
 924 * it, make sure to adjust its flags and tweak our numbers accordingly.
 925 *
 926 * As an optimization, we pass out the index position where we would have
 927 * found the item, since that saves us from having to look it up again a
 928 * few lines later when we want to add the new entry.
 929 */
 930static int have_duplicate_entry(const unsigned char *sha1,
 931                                int exclude,
 932                                uint32_t *index_pos)
 933{
 934        struct object_entry *entry;
 935
 936        entry = packlist_find(&to_pack, sha1, index_pos);
 937        if (!entry)
 938                return 0;
 939
 940        if (exclude) {
 941                if (!entry->preferred_base)
 942                        nr_result--;
 943                entry->preferred_base = 1;
 944        }
 945
 946        return 1;
 947}
 948
 949static int want_found_object(int exclude, struct packed_git *p)
 950{
 951        if (exclude)
 952                return 1;
 953        if (incremental)
 954                return 0;
 955
 956        /*
 957         * When asked to do --local (do not include an object that appears in a
 958         * pack we borrow from elsewhere) or --honor-pack-keep (do not include
 959         * an object that appears in a pack marked with .keep), finding a pack
 960         * that matches the criteria is sufficient for us to decide to omit it.
 961         * However, even if this pack does not satisfy the criteria, we need to
 962         * make sure no copy of this object appears in _any_ pack that makes us
 963         * to omit the object, so we need to check all the packs.
 964         *
 965         * We can however first check whether these options can possible matter;
 966         * if they do not matter we know we want the object in generated pack.
 967         * Otherwise, we signal "-1" at the end to tell the caller that we do
 968         * not know either way, and it needs to check more packs.
 969         */
 970        if (!ignore_packed_keep &&
 971            (!local || !have_non_local_packs))
 972                return 1;
 973
 974        if (local && !p->pack_local)
 975                return 0;
 976        if (ignore_packed_keep && p->pack_local && p->pack_keep)
 977                return 0;
 978
 979        /* we don't know yet; keep looking for more packs */
 980        return -1;
 981}
 982
 983/*
 984 * Check whether we want the object in the pack (e.g., we do not want
 985 * objects found in non-local stores if the "--local" option was used).
 986 *
 987 * If the caller already knows an existing pack it wants to take the object
 988 * from, that is passed in *found_pack and *found_offset; otherwise this
 989 * function finds if there is any pack that has the object and returns the pack
 990 * and its offset in these variables.
 991 */
 992static int want_object_in_pack(const unsigned char *sha1,
 993                               int exclude,
 994                               struct packed_git **found_pack,
 995                               off_t *found_offset)
 996{
 997        struct mru_entry *entry;
 998        int want;
 999
1000        if (!exclude && local && has_loose_object_nonlocal(sha1))
1001                return 0;
1002
1003        /*
1004         * If we already know the pack object lives in, start checks from that
1005         * pack - in the usual case when neither --local was given nor .keep files
1006         * are present we will determine the answer right now.
1007         */
1008        if (*found_pack) {
1009                want = want_found_object(exclude, *found_pack);
1010                if (want != -1)
1011                        return want;
1012        }
1013
1014        for (entry = packed_git_mru->head; entry; entry = entry->next) {
1015                struct packed_git *p = entry->item;
1016                off_t offset;
1017
1018                if (p == *found_pack)
1019                        offset = *found_offset;
1020                else
1021                        offset = find_pack_entry_one(sha1, p);
1022
1023                if (offset) {
1024                        if (!*found_pack) {
1025                                if (!is_pack_valid(p))
1026                                        continue;
1027                                *found_offset = offset;
1028                                *found_pack = p;
1029                        }
1030                        want = want_found_object(exclude, p);
1031                        if (!exclude && want > 0)
1032                                mru_mark(packed_git_mru, entry);
1033                        if (want != -1)
1034                                return want;
1035                }
1036        }
1037
1038        return 1;
1039}
1040
1041static void create_object_entry(const unsigned char *sha1,
1042                                enum object_type type,
1043                                uint32_t hash,
1044                                int exclude,
1045                                int no_try_delta,
1046                                uint32_t index_pos,
1047                                struct packed_git *found_pack,
1048                                off_t found_offset)
1049{
1050        struct object_entry *entry;
1051
1052        entry = packlist_alloc(&to_pack, sha1, index_pos);
1053        entry->hash = hash;
1054        if (type)
1055                entry->type = type;
1056        if (exclude)
1057                entry->preferred_base = 1;
1058        else
1059                nr_result++;
1060        if (found_pack) {
1061                entry->in_pack = found_pack;
1062                entry->in_pack_offset = found_offset;
1063        }
1064
1065        entry->no_try_delta = no_try_delta;
1066}
1067
1068static const char no_closure_warning[] = N_(
1069"disabling bitmap writing, as some objects are not being packed"
1070);
1071
1072static int add_object_entry(const unsigned char *sha1, enum object_type type,
1073                            const char *name, int exclude)
1074{
1075        struct packed_git *found_pack = NULL;
1076        off_t found_offset = 0;
1077        uint32_t index_pos;
1078
1079        if (have_duplicate_entry(sha1, exclude, &index_pos))
1080                return 0;
1081
1082        if (!want_object_in_pack(sha1, exclude, &found_pack, &found_offset)) {
1083                /* The pack is missing an object, so it will not have closure */
1084                if (write_bitmap_index) {
1085                        warning(_(no_closure_warning));
1086                        write_bitmap_index = 0;
1087                }
1088                return 0;
1089        }
1090
1091        create_object_entry(sha1, type, pack_name_hash(name),
1092                            exclude, name && no_try_delta(name),
1093                            index_pos, found_pack, found_offset);
1094
1095        display_progress(progress_state, nr_result);
1096        return 1;
1097}
1098
1099static int add_object_entry_from_bitmap(const unsigned char *sha1,
1100                                        enum object_type type,
1101                                        int flags, uint32_t name_hash,
1102                                        struct packed_git *pack, off_t offset)
1103{
1104        uint32_t index_pos;
1105
1106        if (have_duplicate_entry(sha1, 0, &index_pos))
1107                return 0;
1108
1109        if (!want_object_in_pack(sha1, 0, &pack, &offset))
1110                return 0;
1111
1112        create_object_entry(sha1, type, name_hash, 0, 0, index_pos, pack, offset);
1113
1114        display_progress(progress_state, nr_result);
1115        return 1;
1116}
1117
1118struct pbase_tree_cache {
1119        unsigned char sha1[20];
1120        int ref;
1121        int temporary;
1122        void *tree_data;
1123        unsigned long tree_size;
1124};
1125
1126static struct pbase_tree_cache *(pbase_tree_cache[256]);
1127static int pbase_tree_cache_ix(const unsigned char *sha1)
1128{
1129        return sha1[0] % ARRAY_SIZE(pbase_tree_cache);
1130}
1131static int pbase_tree_cache_ix_incr(int ix)
1132{
1133        return (ix+1) % ARRAY_SIZE(pbase_tree_cache);
1134}
1135
1136static struct pbase_tree {
1137        struct pbase_tree *next;
1138        /* This is a phony "cache" entry; we are not
1139         * going to evict it or find it through _get()
1140         * mechanism -- this is for the toplevel node that
1141         * would almost always change with any commit.
1142         */
1143        struct pbase_tree_cache pcache;
1144} *pbase_tree;
1145
1146static struct pbase_tree_cache *pbase_tree_get(const unsigned char *sha1)
1147{
1148        struct pbase_tree_cache *ent, *nent;
1149        void *data;
1150        unsigned long size;
1151        enum object_type type;
1152        int neigh;
1153        int my_ix = pbase_tree_cache_ix(sha1);
1154        int available_ix = -1;
1155
1156        /* pbase-tree-cache acts as a limited hashtable.
1157         * your object will be found at your index or within a few
1158         * slots after that slot if it is cached.
1159         */
1160        for (neigh = 0; neigh < 8; neigh++) {
1161                ent = pbase_tree_cache[my_ix];
1162                if (ent && !hashcmp(ent->sha1, sha1)) {
1163                        ent->ref++;
1164                        return ent;
1165                }
1166                else if (((available_ix < 0) && (!ent || !ent->ref)) ||
1167                         ((0 <= available_ix) &&
1168                          (!ent && pbase_tree_cache[available_ix])))
1169                        available_ix = my_ix;
1170                if (!ent)
1171                        break;
1172                my_ix = pbase_tree_cache_ix_incr(my_ix);
1173        }
1174
1175        /* Did not find one.  Either we got a bogus request or
1176         * we need to read and perhaps cache.
1177         */
1178        data = read_sha1_file(sha1, &type, &size);
1179        if (!data)
1180                return NULL;
1181        if (type != OBJ_TREE) {
1182                free(data);
1183                return NULL;
1184        }
1185
1186        /* We need to either cache or return a throwaway copy */
1187
1188        if (available_ix < 0)
1189                ent = NULL;
1190        else {
1191                ent = pbase_tree_cache[available_ix];
1192                my_ix = available_ix;
1193        }
1194
1195        if (!ent) {
1196                nent = xmalloc(sizeof(*nent));
1197                nent->temporary = (available_ix < 0);
1198        }
1199        else {
1200                /* evict and reuse */
1201                free(ent->tree_data);
1202                nent = ent;
1203        }
1204        hashcpy(nent->sha1, sha1);
1205        nent->tree_data = data;
1206        nent->tree_size = size;
1207        nent->ref = 1;
1208        if (!nent->temporary)
1209                pbase_tree_cache[my_ix] = nent;
1210        return nent;
1211}
1212
1213static void pbase_tree_put(struct pbase_tree_cache *cache)
1214{
1215        if (!cache->temporary) {
1216                cache->ref--;
1217                return;
1218        }
1219        free(cache->tree_data);
1220        free(cache);
1221}
1222
1223static int name_cmp_len(const char *name)
1224{
1225        int i;
1226        for (i = 0; name[i] && name[i] != '\n' && name[i] != '/'; i++)
1227                ;
1228        return i;
1229}
1230
1231static void add_pbase_object(struct tree_desc *tree,
1232                             const char *name,
1233                             int cmplen,
1234                             const char *fullname)
1235{
1236        struct name_entry entry;
1237        int cmp;
1238
1239        while (tree_entry(tree,&entry)) {
1240                if (S_ISGITLINK(entry.mode))
1241                        continue;
1242                cmp = tree_entry_len(&entry) != cmplen ? 1 :
1243                      memcmp(name, entry.path, cmplen);
1244                if (cmp > 0)
1245                        continue;
1246                if (cmp < 0)
1247                        return;
1248                if (name[cmplen] != '/') {
1249                        add_object_entry(entry.oid->hash,
1250                                         object_type(entry.mode),
1251                                         fullname, 1);
1252                        return;
1253                }
1254                if (S_ISDIR(entry.mode)) {
1255                        struct tree_desc sub;
1256                        struct pbase_tree_cache *tree;
1257                        const char *down = name+cmplen+1;
1258                        int downlen = name_cmp_len(down);
1259
1260                        tree = pbase_tree_get(entry.oid->hash);
1261                        if (!tree)
1262                                return;
1263                        init_tree_desc(&sub, tree->tree_data, tree->tree_size);
1264
1265                        add_pbase_object(&sub, down, downlen, fullname);
1266                        pbase_tree_put(tree);
1267                }
1268        }
1269}
1270
1271static unsigned *done_pbase_paths;
1272static int done_pbase_paths_num;
1273static int done_pbase_paths_alloc;
1274static int done_pbase_path_pos(unsigned hash)
1275{
1276        int lo = 0;
1277        int hi = done_pbase_paths_num;
1278        while (lo < hi) {
1279                int mi = (hi + lo) / 2;
1280                if (done_pbase_paths[mi] == hash)
1281                        return mi;
1282                if (done_pbase_paths[mi] < hash)
1283                        hi = mi;
1284                else
1285                        lo = mi + 1;
1286        }
1287        return -lo-1;
1288}
1289
1290static int check_pbase_path(unsigned hash)
1291{
1292        int pos = done_pbase_path_pos(hash);
1293        if (0 <= pos)
1294                return 1;
1295        pos = -pos - 1;
1296        ALLOC_GROW(done_pbase_paths,
1297                   done_pbase_paths_num + 1,
1298                   done_pbase_paths_alloc);
1299        done_pbase_paths_num++;
1300        if (pos < done_pbase_paths_num)
1301                MOVE_ARRAY(done_pbase_paths + pos + 1, done_pbase_paths + pos,
1302                           done_pbase_paths_num - pos - 1);
1303        done_pbase_paths[pos] = hash;
1304        return 0;
1305}
1306
1307static void add_preferred_base_object(const char *name)
1308{
1309        struct pbase_tree *it;
1310        int cmplen;
1311        unsigned hash = pack_name_hash(name);
1312
1313        if (!num_preferred_base || check_pbase_path(hash))
1314                return;
1315
1316        cmplen = name_cmp_len(name);
1317        for (it = pbase_tree; it; it = it->next) {
1318                if (cmplen == 0) {
1319                        add_object_entry(it->pcache.sha1, OBJ_TREE, NULL, 1);
1320                }
1321                else {
1322                        struct tree_desc tree;
1323                        init_tree_desc(&tree, it->pcache.tree_data, it->pcache.tree_size);
1324                        add_pbase_object(&tree, name, cmplen, name);
1325                }
1326        }
1327}
1328
1329static void add_preferred_base(unsigned char *sha1)
1330{
1331        struct pbase_tree *it;
1332        void *data;
1333        unsigned long size;
1334        unsigned char tree_sha1[20];
1335
1336        if (window <= num_preferred_base++)
1337                return;
1338
1339        data = read_object_with_reference(sha1, tree_type, &size, tree_sha1);
1340        if (!data)
1341                return;
1342
1343        for (it = pbase_tree; it; it = it->next) {
1344                if (!hashcmp(it->pcache.sha1, tree_sha1)) {
1345                        free(data);
1346                        return;
1347                }
1348        }
1349
1350        it = xcalloc(1, sizeof(*it));
1351        it->next = pbase_tree;
1352        pbase_tree = it;
1353
1354        hashcpy(it->pcache.sha1, tree_sha1);
1355        it->pcache.tree_data = data;
1356        it->pcache.tree_size = size;
1357}
1358
1359static void cleanup_preferred_base(void)
1360{
1361        struct pbase_tree *it;
1362        unsigned i;
1363
1364        it = pbase_tree;
1365        pbase_tree = NULL;
1366        while (it) {
1367                struct pbase_tree *this = it;
1368                it = this->next;
1369                free(this->pcache.tree_data);
1370                free(this);
1371        }
1372
1373        for (i = 0; i < ARRAY_SIZE(pbase_tree_cache); i++) {
1374                if (!pbase_tree_cache[i])
1375                        continue;
1376                free(pbase_tree_cache[i]->tree_data);
1377                FREE_AND_NULL(pbase_tree_cache[i]);
1378        }
1379
1380        FREE_AND_NULL(done_pbase_paths);
1381        done_pbase_paths_num = done_pbase_paths_alloc = 0;
1382}
1383
1384static void check_object(struct object_entry *entry)
1385{
1386        if (entry->in_pack) {
1387                struct packed_git *p = entry->in_pack;
1388                struct pack_window *w_curs = NULL;
1389                const unsigned char *base_ref = NULL;
1390                struct object_entry *base_entry;
1391                unsigned long used, used_0;
1392                unsigned long avail;
1393                off_t ofs;
1394                unsigned char *buf, c;
1395
1396                buf = use_pack(p, &w_curs, entry->in_pack_offset, &avail);
1397
1398                /*
1399                 * We want in_pack_type even if we do not reuse delta
1400                 * since non-delta representations could still be reused.
1401                 */
1402                used = unpack_object_header_buffer(buf, avail,
1403                                                   &entry->in_pack_type,
1404                                                   &entry->size);
1405                if (used == 0)
1406                        goto give_up;
1407
1408                /*
1409                 * Determine if this is a delta and if so whether we can
1410                 * reuse it or not.  Otherwise let's find out as cheaply as
1411                 * possible what the actual type and size for this object is.
1412                 */
1413                switch (entry->in_pack_type) {
1414                default:
1415                        /* Not a delta hence we've already got all we need. */
1416                        entry->type = entry->in_pack_type;
1417                        entry->in_pack_header_size = used;
1418                        if (entry->type < OBJ_COMMIT || entry->type > OBJ_BLOB)
1419                                goto give_up;
1420                        unuse_pack(&w_curs);
1421                        return;
1422                case OBJ_REF_DELTA:
1423                        if (reuse_delta && !entry->preferred_base)
1424                                base_ref = use_pack(p, &w_curs,
1425                                                entry->in_pack_offset + used, NULL);
1426                        entry->in_pack_header_size = used + 20;
1427                        break;
1428                case OBJ_OFS_DELTA:
1429                        buf = use_pack(p, &w_curs,
1430                                       entry->in_pack_offset + used, NULL);
1431                        used_0 = 0;
1432                        c = buf[used_0++];
1433                        ofs = c & 127;
1434                        while (c & 128) {
1435                                ofs += 1;
1436                                if (!ofs || MSB(ofs, 7)) {
1437                                        error("delta base offset overflow in pack for %s",
1438                                              oid_to_hex(&entry->idx.oid));
1439                                        goto give_up;
1440                                }
1441                                c = buf[used_0++];
1442                                ofs = (ofs << 7) + (c & 127);
1443                        }
1444                        ofs = entry->in_pack_offset - ofs;
1445                        if (ofs <= 0 || ofs >= entry->in_pack_offset) {
1446                                error("delta base offset out of bound for %s",
1447                                      oid_to_hex(&entry->idx.oid));
1448                                goto give_up;
1449                        }
1450                        if (reuse_delta && !entry->preferred_base) {
1451                                struct revindex_entry *revidx;
1452                                revidx = find_pack_revindex(p, ofs);
1453                                if (!revidx)
1454                                        goto give_up;
1455                                base_ref = nth_packed_object_sha1(p, revidx->nr);
1456                        }
1457                        entry->in_pack_header_size = used + used_0;
1458                        break;
1459                }
1460
1461                if (base_ref && (base_entry = packlist_find(&to_pack, base_ref, NULL))) {
1462                        /*
1463                         * If base_ref was set above that means we wish to
1464                         * reuse delta data, and we even found that base
1465                         * in the list of objects we want to pack. Goodie!
1466                         *
1467                         * Depth value does not matter - find_deltas() will
1468                         * never consider reused delta as the base object to
1469                         * deltify other objects against, in order to avoid
1470                         * circular deltas.
1471                         */
1472                        entry->type = entry->in_pack_type;
1473                        entry->delta = base_entry;
1474                        entry->delta_size = entry->size;
1475                        entry->delta_sibling = base_entry->delta_child;
1476                        base_entry->delta_child = entry;
1477                        unuse_pack(&w_curs);
1478                        return;
1479                }
1480
1481                if (entry->type) {
1482                        /*
1483                         * This must be a delta and we already know what the
1484                         * final object type is.  Let's extract the actual
1485                         * object size from the delta header.
1486                         */
1487                        entry->size = get_size_from_delta(p, &w_curs,
1488                                        entry->in_pack_offset + entry->in_pack_header_size);
1489                        if (entry->size == 0)
1490                                goto give_up;
1491                        unuse_pack(&w_curs);
1492                        return;
1493                }
1494
1495                /*
1496                 * No choice but to fall back to the recursive delta walk
1497                 * with sha1_object_info() to find about the object type
1498                 * at this point...
1499                 */
1500                give_up:
1501                unuse_pack(&w_curs);
1502        }
1503
1504        entry->type = sha1_object_info(entry->idx.oid.hash, &entry->size);
1505        /*
1506         * The error condition is checked in prepare_pack().  This is
1507         * to permit a missing preferred base object to be ignored
1508         * as a preferred base.  Doing so can result in a larger
1509         * pack file, but the transfer will still take place.
1510         */
1511}
1512
1513static int pack_offset_sort(const void *_a, const void *_b)
1514{
1515        const struct object_entry *a = *(struct object_entry **)_a;
1516        const struct object_entry *b = *(struct object_entry **)_b;
1517
1518        /* avoid filesystem trashing with loose objects */
1519        if (!a->in_pack && !b->in_pack)
1520                return oidcmp(&a->idx.oid, &b->idx.oid);
1521
1522        if (a->in_pack < b->in_pack)
1523                return -1;
1524        if (a->in_pack > b->in_pack)
1525                return 1;
1526        return a->in_pack_offset < b->in_pack_offset ? -1 :
1527                        (a->in_pack_offset > b->in_pack_offset);
1528}
1529
1530/*
1531 * Drop an on-disk delta we were planning to reuse. Naively, this would
1532 * just involve blanking out the "delta" field, but we have to deal
1533 * with some extra book-keeping:
1534 *
1535 *   1. Removing ourselves from the delta_sibling linked list.
1536 *
1537 *   2. Updating our size/type to the non-delta representation. These were
1538 *      either not recorded initially (size) or overwritten with the delta type
1539 *      (type) when check_object() decided to reuse the delta.
1540 *
1541 *   3. Resetting our delta depth, as we are now a base object.
1542 */
1543static void drop_reused_delta(struct object_entry *entry)
1544{
1545        struct object_entry **p = &entry->delta->delta_child;
1546        struct object_info oi = OBJECT_INFO_INIT;
1547
1548        while (*p) {
1549                if (*p == entry)
1550                        *p = (*p)->delta_sibling;
1551                else
1552                        p = &(*p)->delta_sibling;
1553        }
1554        entry->delta = NULL;
1555        entry->depth = 0;
1556
1557        oi.sizep = &entry->size;
1558        oi.typep = &entry->type;
1559        if (packed_object_info(entry->in_pack, entry->in_pack_offset, &oi) < 0) {
1560                /*
1561                 * We failed to get the info from this pack for some reason;
1562                 * fall back to sha1_object_info, which may find another copy.
1563                 * And if that fails, the error will be recorded in entry->type
1564                 * and dealt with in prepare_pack().
1565                 */
1566                entry->type = sha1_object_info(entry->idx.oid.hash,
1567                                               &entry->size);
1568        }
1569}
1570
1571/*
1572 * Follow the chain of deltas from this entry onward, throwing away any links
1573 * that cause us to hit a cycle (as determined by the DFS state flags in
1574 * the entries).
1575 *
1576 * We also detect too-long reused chains that would violate our --depth
1577 * limit.
1578 */
1579static void break_delta_chains(struct object_entry *entry)
1580{
1581        /*
1582         * The actual depth of each object we will write is stored as an int,
1583         * as it cannot exceed our int "depth" limit. But before we break
1584         * changes based no that limit, we may potentially go as deep as the
1585         * number of objects, which is elsewhere bounded to a uint32_t.
1586         */
1587        uint32_t total_depth;
1588        struct object_entry *cur, *next;
1589
1590        for (cur = entry, total_depth = 0;
1591             cur;
1592             cur = cur->delta, total_depth++) {
1593                if (cur->dfs_state == DFS_DONE) {
1594                        /*
1595                         * We've already seen this object and know it isn't
1596                         * part of a cycle. We do need to append its depth
1597                         * to our count.
1598                         */
1599                        total_depth += cur->depth;
1600                        break;
1601                }
1602
1603                /*
1604                 * We break cycles before looping, so an ACTIVE state (or any
1605                 * other cruft which made its way into the state variable)
1606                 * is a bug.
1607                 */
1608                if (cur->dfs_state != DFS_NONE)
1609                        die("BUG: confusing delta dfs state in first pass: %d",
1610                            cur->dfs_state);
1611
1612                /*
1613                 * Now we know this is the first time we've seen the object. If
1614                 * it's not a delta, we're done traversing, but we'll mark it
1615                 * done to save time on future traversals.
1616                 */
1617                if (!cur->delta) {
1618                        cur->dfs_state = DFS_DONE;
1619                        break;
1620                }
1621
1622                /*
1623                 * Mark ourselves as active and see if the next step causes
1624                 * us to cycle to another active object. It's important to do
1625                 * this _before_ we loop, because it impacts where we make the
1626                 * cut, and thus how our total_depth counter works.
1627                 * E.g., We may see a partial loop like:
1628                 *
1629                 *   A -> B -> C -> D -> B
1630                 *
1631                 * Cutting B->C breaks the cycle. But now the depth of A is
1632                 * only 1, and our total_depth counter is at 3. The size of the
1633                 * error is always one less than the size of the cycle we
1634                 * broke. Commits C and D were "lost" from A's chain.
1635                 *
1636                 * If we instead cut D->B, then the depth of A is correct at 3.
1637                 * We keep all commits in the chain that we examined.
1638                 */
1639                cur->dfs_state = DFS_ACTIVE;
1640                if (cur->delta->dfs_state == DFS_ACTIVE) {
1641                        drop_reused_delta(cur);
1642                        cur->dfs_state = DFS_DONE;
1643                        break;
1644                }
1645        }
1646
1647        /*
1648         * And now that we've gone all the way to the bottom of the chain, we
1649         * need to clear the active flags and set the depth fields as
1650         * appropriate. Unlike the loop above, which can quit when it drops a
1651         * delta, we need to keep going to look for more depth cuts. So we need
1652         * an extra "next" pointer to keep going after we reset cur->delta.
1653         */
1654        for (cur = entry; cur; cur = next) {
1655                next = cur->delta;
1656
1657                /*
1658                 * We should have a chain of zero or more ACTIVE states down to
1659                 * a final DONE. We can quit after the DONE, because either it
1660                 * has no bases, or we've already handled them in a previous
1661                 * call.
1662                 */
1663                if (cur->dfs_state == DFS_DONE)
1664                        break;
1665                else if (cur->dfs_state != DFS_ACTIVE)
1666                        die("BUG: confusing delta dfs state in second pass: %d",
1667                            cur->dfs_state);
1668
1669                /*
1670                 * If the total_depth is more than depth, then we need to snip
1671                 * the chain into two or more smaller chains that don't exceed
1672                 * the maximum depth. Most of the resulting chains will contain
1673                 * (depth + 1) entries (i.e., depth deltas plus one base), and
1674                 * the last chain (i.e., the one containing entry) will contain
1675                 * whatever entries are left over, namely
1676                 * (total_depth % (depth + 1)) of them.
1677                 *
1678                 * Since we are iterating towards decreasing depth, we need to
1679                 * decrement total_depth as we go, and we need to write to the
1680                 * entry what its final depth will be after all of the
1681                 * snipping. Since we're snipping into chains of length (depth
1682                 * + 1) entries, the final depth of an entry will be its
1683                 * original depth modulo (depth + 1). Any time we encounter an
1684                 * entry whose final depth is supposed to be zero, we snip it
1685                 * from its delta base, thereby making it so.
1686                 */
1687                cur->depth = (total_depth--) % (depth + 1);
1688                if (!cur->depth)
1689                        drop_reused_delta(cur);
1690
1691                cur->dfs_state = DFS_DONE;
1692        }
1693}
1694
1695static void get_object_details(void)
1696{
1697        uint32_t i;
1698        struct object_entry **sorted_by_offset;
1699
1700        sorted_by_offset = xcalloc(to_pack.nr_objects, sizeof(struct object_entry *));
1701        for (i = 0; i < to_pack.nr_objects; i++)
1702                sorted_by_offset[i] = to_pack.objects + i;
1703        QSORT(sorted_by_offset, to_pack.nr_objects, pack_offset_sort);
1704
1705        for (i = 0; i < to_pack.nr_objects; i++) {
1706                struct object_entry *entry = sorted_by_offset[i];
1707                check_object(entry);
1708                if (big_file_threshold < entry->size)
1709                        entry->no_try_delta = 1;
1710        }
1711
1712        /*
1713         * This must happen in a second pass, since we rely on the delta
1714         * information for the whole list being completed.
1715         */
1716        for (i = 0; i < to_pack.nr_objects; i++)
1717                break_delta_chains(&to_pack.objects[i]);
1718
1719        free(sorted_by_offset);
1720}
1721
1722/*
1723 * We search for deltas in a list sorted by type, by filename hash, and then
1724 * by size, so that we see progressively smaller and smaller files.
1725 * That's because we prefer deltas to be from the bigger file
1726 * to the smaller -- deletes are potentially cheaper, but perhaps
1727 * more importantly, the bigger file is likely the more recent
1728 * one.  The deepest deltas are therefore the oldest objects which are
1729 * less susceptible to be accessed often.
1730 */
1731static int type_size_sort(const void *_a, const void *_b)
1732{
1733        const struct object_entry *a = *(struct object_entry **)_a;
1734        const struct object_entry *b = *(struct object_entry **)_b;
1735
1736        if (a->type > b->type)
1737                return -1;
1738        if (a->type < b->type)
1739                return 1;
1740        if (a->hash > b->hash)
1741                return -1;
1742        if (a->hash < b->hash)
1743                return 1;
1744        if (a->preferred_base > b->preferred_base)
1745                return -1;
1746        if (a->preferred_base < b->preferred_base)
1747                return 1;
1748        if (a->size > b->size)
1749                return -1;
1750        if (a->size < b->size)
1751                return 1;
1752        return a < b ? -1 : (a > b);  /* newest first */
1753}
1754
1755struct unpacked {
1756        struct object_entry *entry;
1757        void *data;
1758        struct delta_index *index;
1759        unsigned depth;
1760};
1761
1762static int delta_cacheable(unsigned long src_size, unsigned long trg_size,
1763                           unsigned long delta_size)
1764{
1765        if (max_delta_cache_size && delta_cache_size + delta_size > max_delta_cache_size)
1766                return 0;
1767
1768        if (delta_size < cache_max_small_delta_size)
1769                return 1;
1770
1771        /* cache delta, if objects are large enough compared to delta size */
1772        if ((src_size >> 20) + (trg_size >> 21) > (delta_size >> 10))
1773                return 1;
1774
1775        return 0;
1776}
1777
1778#ifndef NO_PTHREADS
1779
1780static pthread_mutex_t read_mutex;
1781#define read_lock()             pthread_mutex_lock(&read_mutex)
1782#define read_unlock()           pthread_mutex_unlock(&read_mutex)
1783
1784static pthread_mutex_t cache_mutex;
1785#define cache_lock()            pthread_mutex_lock(&cache_mutex)
1786#define cache_unlock()          pthread_mutex_unlock(&cache_mutex)
1787
1788static pthread_mutex_t progress_mutex;
1789#define progress_lock()         pthread_mutex_lock(&progress_mutex)
1790#define progress_unlock()       pthread_mutex_unlock(&progress_mutex)
1791
1792#else
1793
1794#define read_lock()             (void)0
1795#define read_unlock()           (void)0
1796#define cache_lock()            (void)0
1797#define cache_unlock()          (void)0
1798#define progress_lock()         (void)0
1799#define progress_unlock()       (void)0
1800
1801#endif
1802
1803static int try_delta(struct unpacked *trg, struct unpacked *src,
1804                     unsigned max_depth, unsigned long *mem_usage)
1805{
1806        struct object_entry *trg_entry = trg->entry;
1807        struct object_entry *src_entry = src->entry;
1808        unsigned long trg_size, src_size, delta_size, sizediff, max_size, sz;
1809        unsigned ref_depth;
1810        enum object_type type;
1811        void *delta_buf;
1812
1813        /* Don't bother doing diffs between different types */
1814        if (trg_entry->type != src_entry->type)
1815                return -1;
1816
1817        /*
1818         * We do not bother to try a delta that we discarded on an
1819         * earlier try, but only when reusing delta data.  Note that
1820         * src_entry that is marked as the preferred_base should always
1821         * be considered, as even if we produce a suboptimal delta against
1822         * it, we will still save the transfer cost, as we already know
1823         * the other side has it and we won't send src_entry at all.
1824         */
1825        if (reuse_delta && trg_entry->in_pack &&
1826            trg_entry->in_pack == src_entry->in_pack &&
1827            !src_entry->preferred_base &&
1828            trg_entry->in_pack_type != OBJ_REF_DELTA &&
1829            trg_entry->in_pack_type != OBJ_OFS_DELTA)
1830                return 0;
1831
1832        /* Let's not bust the allowed depth. */
1833        if (src->depth >= max_depth)
1834                return 0;
1835
1836        /* Now some size filtering heuristics. */
1837        trg_size = trg_entry->size;
1838        if (!trg_entry->delta) {
1839                max_size = trg_size/2 - 20;
1840                ref_depth = 1;
1841        } else {
1842                max_size = trg_entry->delta_size;
1843                ref_depth = trg->depth;
1844        }
1845        max_size = (uint64_t)max_size * (max_depth - src->depth) /
1846                                                (max_depth - ref_depth + 1);
1847        if (max_size == 0)
1848                return 0;
1849        src_size = src_entry->size;
1850        sizediff = src_size < trg_size ? trg_size - src_size : 0;
1851        if (sizediff >= max_size)
1852                return 0;
1853        if (trg_size < src_size / 32)
1854                return 0;
1855
1856        /* Load data if not already done */
1857        if (!trg->data) {
1858                read_lock();
1859                trg->data = read_sha1_file(trg_entry->idx.oid.hash, &type,
1860                                           &sz);
1861                read_unlock();
1862                if (!trg->data)
1863                        die("object %s cannot be read",
1864                            oid_to_hex(&trg_entry->idx.oid));
1865                if (sz != trg_size)
1866                        die("object %s inconsistent object length (%lu vs %lu)",
1867                            oid_to_hex(&trg_entry->idx.oid), sz,
1868                            trg_size);
1869                *mem_usage += sz;
1870        }
1871        if (!src->data) {
1872                read_lock();
1873                src->data = read_sha1_file(src_entry->idx.oid.hash, &type,
1874                                           &sz);
1875                read_unlock();
1876                if (!src->data) {
1877                        if (src_entry->preferred_base) {
1878                                static int warned = 0;
1879                                if (!warned++)
1880                                        warning("object %s cannot be read",
1881                                                oid_to_hex(&src_entry->idx.oid));
1882                                /*
1883                                 * Those objects are not included in the
1884                                 * resulting pack.  Be resilient and ignore
1885                                 * them if they can't be read, in case the
1886                                 * pack could be created nevertheless.
1887                                 */
1888                                return 0;
1889                        }
1890                        die("object %s cannot be read",
1891                            oid_to_hex(&src_entry->idx.oid));
1892                }
1893                if (sz != src_size)
1894                        die("object %s inconsistent object length (%lu vs %lu)",
1895                            oid_to_hex(&src_entry->idx.oid), sz,
1896                            src_size);
1897                *mem_usage += sz;
1898        }
1899        if (!src->index) {
1900                src->index = create_delta_index(src->data, src_size);
1901                if (!src->index) {
1902                        static int warned = 0;
1903                        if (!warned++)
1904                                warning("suboptimal pack - out of memory");
1905                        return 0;
1906                }
1907                *mem_usage += sizeof_delta_index(src->index);
1908        }
1909
1910        delta_buf = create_delta(src->index, trg->data, trg_size, &delta_size, max_size);
1911        if (!delta_buf)
1912                return 0;
1913
1914        if (trg_entry->delta) {
1915                /* Prefer only shallower same-sized deltas. */
1916                if (delta_size == trg_entry->delta_size &&
1917                    src->depth + 1 >= trg->depth) {
1918                        free(delta_buf);
1919                        return 0;
1920                }
1921        }
1922
1923        /*
1924         * Handle memory allocation outside of the cache
1925         * accounting lock.  Compiler will optimize the strangeness
1926         * away when NO_PTHREADS is defined.
1927         */
1928        free(trg_entry->delta_data);
1929        cache_lock();
1930        if (trg_entry->delta_data) {
1931                delta_cache_size -= trg_entry->delta_size;
1932                trg_entry->delta_data = NULL;
1933        }
1934        if (delta_cacheable(src_size, trg_size, delta_size)) {
1935                delta_cache_size += delta_size;
1936                cache_unlock();
1937                trg_entry->delta_data = xrealloc(delta_buf, delta_size);
1938        } else {
1939                cache_unlock();
1940                free(delta_buf);
1941        }
1942
1943        trg_entry->delta = src_entry;
1944        trg_entry->delta_size = delta_size;
1945        trg->depth = src->depth + 1;
1946
1947        return 1;
1948}
1949
1950static unsigned int check_delta_limit(struct object_entry *me, unsigned int n)
1951{
1952        struct object_entry *child = me->delta_child;
1953        unsigned int m = n;
1954        while (child) {
1955                unsigned int c = check_delta_limit(child, n + 1);
1956                if (m < c)
1957                        m = c;
1958                child = child->delta_sibling;
1959        }
1960        return m;
1961}
1962
1963static unsigned long free_unpacked(struct unpacked *n)
1964{
1965        unsigned long freed_mem = sizeof_delta_index(n->index);
1966        free_delta_index(n->index);
1967        n->index = NULL;
1968        if (n->data) {
1969                freed_mem += n->entry->size;
1970                FREE_AND_NULL(n->data);
1971        }
1972        n->entry = NULL;
1973        n->depth = 0;
1974        return freed_mem;
1975}
1976
1977static void find_deltas(struct object_entry **list, unsigned *list_size,
1978                        int window, int depth, unsigned *processed)
1979{
1980        uint32_t i, idx = 0, count = 0;
1981        struct unpacked *array;
1982        unsigned long mem_usage = 0;
1983
1984        array = xcalloc(window, sizeof(struct unpacked));
1985
1986        for (;;) {
1987                struct object_entry *entry;
1988                struct unpacked *n = array + idx;
1989                int j, max_depth, best_base = -1;
1990
1991                progress_lock();
1992                if (!*list_size) {
1993                        progress_unlock();
1994                        break;
1995                }
1996                entry = *list++;
1997                (*list_size)--;
1998                if (!entry->preferred_base) {
1999                        (*processed)++;
2000                        display_progress(progress_state, *processed);
2001                }
2002                progress_unlock();
2003
2004                mem_usage -= free_unpacked(n);
2005                n->entry = entry;
2006
2007                while (window_memory_limit &&
2008                       mem_usage > window_memory_limit &&
2009                       count > 1) {
2010                        uint32_t tail = (idx + window - count) % window;
2011                        mem_usage -= free_unpacked(array + tail);
2012                        count--;
2013                }
2014
2015                /* We do not compute delta to *create* objects we are not
2016                 * going to pack.
2017                 */
2018                if (entry->preferred_base)
2019                        goto next;
2020
2021                /*
2022                 * If the current object is at pack edge, take the depth the
2023                 * objects that depend on the current object into account
2024                 * otherwise they would become too deep.
2025                 */
2026                max_depth = depth;
2027                if (entry->delta_child) {
2028                        max_depth -= check_delta_limit(entry, 0);
2029                        if (max_depth <= 0)
2030                                goto next;
2031                }
2032
2033                j = window;
2034                while (--j > 0) {
2035                        int ret;
2036                        uint32_t other_idx = idx + j;
2037                        struct unpacked *m;
2038                        if (other_idx >= window)
2039                                other_idx -= window;
2040                        m = array + other_idx;
2041                        if (!m->entry)
2042                                break;
2043                        ret = try_delta(n, m, max_depth, &mem_usage);
2044                        if (ret < 0)
2045                                break;
2046                        else if (ret > 0)
2047                                best_base = other_idx;
2048                }
2049
2050                /*
2051                 * If we decided to cache the delta data, then it is best
2052                 * to compress it right away.  First because we have to do
2053                 * it anyway, and doing it here while we're threaded will
2054                 * save a lot of time in the non threaded write phase,
2055                 * as well as allow for caching more deltas within
2056                 * the same cache size limit.
2057                 * ...
2058                 * But only if not writing to stdout, since in that case
2059                 * the network is most likely throttling writes anyway,
2060                 * and therefore it is best to go to the write phase ASAP
2061                 * instead, as we can afford spending more time compressing
2062                 * between writes at that moment.
2063                 */
2064                if (entry->delta_data && !pack_to_stdout) {
2065                        entry->z_delta_size = do_compress(&entry->delta_data,
2066                                                          entry->delta_size);
2067                        cache_lock();
2068                        delta_cache_size -= entry->delta_size;
2069                        delta_cache_size += entry->z_delta_size;
2070                        cache_unlock();
2071                }
2072
2073                /* if we made n a delta, and if n is already at max
2074                 * depth, leaving it in the window is pointless.  we
2075                 * should evict it first.
2076                 */
2077                if (entry->delta && max_depth <= n->depth)
2078                        continue;
2079
2080                /*
2081                 * Move the best delta base up in the window, after the
2082                 * currently deltified object, to keep it longer.  It will
2083                 * be the first base object to be attempted next.
2084                 */
2085                if (entry->delta) {
2086                        struct unpacked swap = array[best_base];
2087                        int dist = (window + idx - best_base) % window;
2088                        int dst = best_base;
2089                        while (dist--) {
2090                                int src = (dst + 1) % window;
2091                                array[dst] = array[src];
2092                                dst = src;
2093                        }
2094                        array[dst] = swap;
2095                }
2096
2097                next:
2098                idx++;
2099                if (count + 1 < window)
2100                        count++;
2101                if (idx >= window)
2102                        idx = 0;
2103        }
2104
2105        for (i = 0; i < window; ++i) {
2106                free_delta_index(array[i].index);
2107                free(array[i].data);
2108        }
2109        free(array);
2110}
2111
2112#ifndef NO_PTHREADS
2113
2114static void try_to_free_from_threads(size_t size)
2115{
2116        read_lock();
2117        release_pack_memory(size);
2118        read_unlock();
2119}
2120
2121static try_to_free_t old_try_to_free_routine;
2122
2123/*
2124 * The main thread waits on the condition that (at least) one of the workers
2125 * has stopped working (which is indicated in the .working member of
2126 * struct thread_params).
2127 * When a work thread has completed its work, it sets .working to 0 and
2128 * signals the main thread and waits on the condition that .data_ready
2129 * becomes 1.
2130 */
2131
2132struct thread_params {
2133        pthread_t thread;
2134        struct object_entry **list;
2135        unsigned list_size;
2136        unsigned remaining;
2137        int window;
2138        int depth;
2139        int working;
2140        int data_ready;
2141        pthread_mutex_t mutex;
2142        pthread_cond_t cond;
2143        unsigned *processed;
2144};
2145
2146static pthread_cond_t progress_cond;
2147
2148/*
2149 * Mutex and conditional variable can't be statically-initialized on Windows.
2150 */
2151static void init_threaded_search(void)
2152{
2153        init_recursive_mutex(&read_mutex);
2154        pthread_mutex_init(&cache_mutex, NULL);
2155        pthread_mutex_init(&progress_mutex, NULL);
2156        pthread_cond_init(&progress_cond, NULL);
2157        old_try_to_free_routine = set_try_to_free_routine(try_to_free_from_threads);
2158}
2159
2160static void cleanup_threaded_search(void)
2161{
2162        set_try_to_free_routine(old_try_to_free_routine);
2163        pthread_cond_destroy(&progress_cond);
2164        pthread_mutex_destroy(&read_mutex);
2165        pthread_mutex_destroy(&cache_mutex);
2166        pthread_mutex_destroy(&progress_mutex);
2167}
2168
2169static void *threaded_find_deltas(void *arg)
2170{
2171        struct thread_params *me = arg;
2172
2173        while (me->remaining) {
2174                find_deltas(me->list, &me->remaining,
2175                            me->window, me->depth, me->processed);
2176
2177                progress_lock();
2178                me->working = 0;
2179                pthread_cond_signal(&progress_cond);
2180                progress_unlock();
2181
2182                /*
2183                 * We must not set ->data_ready before we wait on the
2184                 * condition because the main thread may have set it to 1
2185                 * before we get here. In order to be sure that new
2186                 * work is available if we see 1 in ->data_ready, it
2187                 * was initialized to 0 before this thread was spawned
2188                 * and we reset it to 0 right away.
2189                 */
2190                pthread_mutex_lock(&me->mutex);
2191                while (!me->data_ready)
2192                        pthread_cond_wait(&me->cond, &me->mutex);
2193                me->data_ready = 0;
2194                pthread_mutex_unlock(&me->mutex);
2195        }
2196        /* leave ->working 1 so that this doesn't get more work assigned */
2197        return NULL;
2198}
2199
2200static void ll_find_deltas(struct object_entry **list, unsigned list_size,
2201                           int window, int depth, unsigned *processed)
2202{
2203        struct thread_params *p;
2204        int i, ret, active_threads = 0;
2205
2206        init_threaded_search();
2207
2208        if (delta_search_threads <= 1) {
2209                find_deltas(list, &list_size, window, depth, processed);
2210                cleanup_threaded_search();
2211                return;
2212        }
2213        if (progress > pack_to_stdout)
2214                fprintf(stderr, "Delta compression using up to %d threads.\n",
2215                                delta_search_threads);
2216        p = xcalloc(delta_search_threads, sizeof(*p));
2217
2218        /* Partition the work amongst work threads. */
2219        for (i = 0; i < delta_search_threads; i++) {
2220                unsigned sub_size = list_size / (delta_search_threads - i);
2221
2222                /* don't use too small segments or no deltas will be found */
2223                if (sub_size < 2*window && i+1 < delta_search_threads)
2224                        sub_size = 0;
2225
2226                p[i].window = window;
2227                p[i].depth = depth;
2228                p[i].processed = processed;
2229                p[i].working = 1;
2230                p[i].data_ready = 0;
2231
2232                /* try to split chunks on "path" boundaries */
2233                while (sub_size && sub_size < list_size &&
2234                       list[sub_size]->hash &&
2235                       list[sub_size]->hash == list[sub_size-1]->hash)
2236                        sub_size++;
2237
2238                p[i].list = list;
2239                p[i].list_size = sub_size;
2240                p[i].remaining = sub_size;
2241
2242                list += sub_size;
2243                list_size -= sub_size;
2244        }
2245
2246        /* Start work threads. */
2247        for (i = 0; i < delta_search_threads; i++) {
2248                if (!p[i].list_size)
2249                        continue;
2250                pthread_mutex_init(&p[i].mutex, NULL);
2251                pthread_cond_init(&p[i].cond, NULL);
2252                ret = pthread_create(&p[i].thread, NULL,
2253                                     threaded_find_deltas, &p[i]);
2254                if (ret)
2255                        die("unable to create thread: %s", strerror(ret));
2256                active_threads++;
2257        }
2258
2259        /*
2260         * Now let's wait for work completion.  Each time a thread is done
2261         * with its work, we steal half of the remaining work from the
2262         * thread with the largest number of unprocessed objects and give
2263         * it to that newly idle thread.  This ensure good load balancing
2264         * until the remaining object list segments are simply too short
2265         * to be worth splitting anymore.
2266         */
2267        while (active_threads) {
2268                struct thread_params *target = NULL;
2269                struct thread_params *victim = NULL;
2270                unsigned sub_size = 0;
2271
2272                progress_lock();
2273                for (;;) {
2274                        for (i = 0; !target && i < delta_search_threads; i++)
2275                                if (!p[i].working)
2276                                        target = &p[i];
2277                        if (target)
2278                                break;
2279                        pthread_cond_wait(&progress_cond, &progress_mutex);
2280                }
2281
2282                for (i = 0; i < delta_search_threads; i++)
2283                        if (p[i].remaining > 2*window &&
2284                            (!victim || victim->remaining < p[i].remaining))
2285                                victim = &p[i];
2286                if (victim) {
2287                        sub_size = victim->remaining / 2;
2288                        list = victim->list + victim->list_size - sub_size;
2289                        while (sub_size && list[0]->hash &&
2290                               list[0]->hash == list[-1]->hash) {
2291                                list++;
2292                                sub_size--;
2293                        }
2294                        if (!sub_size) {
2295                                /*
2296                                 * It is possible for some "paths" to have
2297                                 * so many objects that no hash boundary
2298                                 * might be found.  Let's just steal the
2299                                 * exact half in that case.
2300                                 */
2301                                sub_size = victim->remaining / 2;
2302                                list -= sub_size;
2303                        }
2304                        target->list = list;
2305                        victim->list_size -= sub_size;
2306                        victim->remaining -= sub_size;
2307                }
2308                target->list_size = sub_size;
2309                target->remaining = sub_size;
2310                target->working = 1;
2311                progress_unlock();
2312
2313                pthread_mutex_lock(&target->mutex);
2314                target->data_ready = 1;
2315                pthread_cond_signal(&target->cond);
2316                pthread_mutex_unlock(&target->mutex);
2317
2318                if (!sub_size) {
2319                        pthread_join(target->thread, NULL);
2320                        pthread_cond_destroy(&target->cond);
2321                        pthread_mutex_destroy(&target->mutex);
2322                        active_threads--;
2323                }
2324        }
2325        cleanup_threaded_search();
2326        free(p);
2327}
2328
2329#else
2330#define ll_find_deltas(l, s, w, d, p)   find_deltas(l, &s, w, d, p)
2331#endif
2332
2333static void add_tag_chain(const struct object_id *oid)
2334{
2335        struct tag *tag;
2336
2337        /*
2338         * We catch duplicates already in add_object_entry(), but we'd
2339         * prefer to do this extra check to avoid having to parse the
2340         * tag at all if we already know that it's being packed (e.g., if
2341         * it was included via bitmaps, we would not have parsed it
2342         * previously).
2343         */
2344        if (packlist_find(&to_pack, oid->hash, NULL))
2345                return;
2346
2347        tag = lookup_tag(oid);
2348        while (1) {
2349                if (!tag || parse_tag(tag) || !tag->tagged)
2350                        die("unable to pack objects reachable from tag %s",
2351                            oid_to_hex(oid));
2352
2353                add_object_entry(tag->object.oid.hash, OBJ_TAG, NULL, 0);
2354
2355                if (tag->tagged->type != OBJ_TAG)
2356                        return;
2357
2358                tag = (struct tag *)tag->tagged;
2359        }
2360}
2361
2362static int add_ref_tag(const char *path, const struct object_id *oid, int flag, void *cb_data)
2363{
2364        struct object_id peeled;
2365
2366        if (starts_with(path, "refs/tags/") && /* is a tag? */
2367            !peel_ref(path, peeled.hash)    && /* peelable? */
2368            packlist_find(&to_pack, peeled.hash, NULL))      /* object packed? */
2369                add_tag_chain(oid);
2370        return 0;
2371}
2372
2373static void prepare_pack(int window, int depth)
2374{
2375        struct object_entry **delta_list;
2376        uint32_t i, nr_deltas;
2377        unsigned n;
2378
2379        get_object_details();
2380
2381        /*
2382         * If we're locally repacking then we need to be doubly careful
2383         * from now on in order to make sure no stealth corruption gets
2384         * propagated to the new pack.  Clients receiving streamed packs
2385         * should validate everything they get anyway so no need to incur
2386         * the additional cost here in that case.
2387         */
2388        if (!pack_to_stdout)
2389                do_check_packed_object_crc = 1;
2390
2391        if (!to_pack.nr_objects || !window || !depth)
2392                return;
2393
2394        ALLOC_ARRAY(delta_list, to_pack.nr_objects);
2395        nr_deltas = n = 0;
2396
2397        for (i = 0; i < to_pack.nr_objects; i++) {
2398                struct object_entry *entry = to_pack.objects + i;
2399
2400                if (entry->delta)
2401                        /* This happens if we decided to reuse existing
2402                         * delta from a pack.  "reuse_delta &&" is implied.
2403                         */
2404                        continue;
2405
2406                if (entry->size < 50)
2407                        continue;
2408
2409                if (entry->no_try_delta)
2410                        continue;
2411
2412                if (!entry->preferred_base) {
2413                        nr_deltas++;
2414                        if (entry->type < 0)
2415                                die("unable to get type of object %s",
2416                                    oid_to_hex(&entry->idx.oid));
2417                } else {
2418                        if (entry->type < 0) {
2419                                /*
2420                                 * This object is not found, but we
2421                                 * don't have to include it anyway.
2422                                 */
2423                                continue;
2424                        }
2425                }
2426
2427                delta_list[n++] = entry;
2428        }
2429
2430        if (nr_deltas && n > 1) {
2431                unsigned nr_done = 0;
2432                if (progress)
2433                        progress_state = start_progress(_("Compressing objects"),
2434                                                        nr_deltas);
2435                QSORT(delta_list, n, type_size_sort);
2436                ll_find_deltas(delta_list, n, window+1, depth, &nr_done);
2437                stop_progress(&progress_state);
2438                if (nr_done != nr_deltas)
2439                        die("inconsistency with delta count");
2440        }
2441        free(delta_list);
2442}
2443
2444static int git_pack_config(const char *k, const char *v, void *cb)
2445{
2446        if (!strcmp(k, "pack.window")) {
2447                window = git_config_int(k, v);
2448                return 0;
2449        }
2450        if (!strcmp(k, "pack.windowmemory")) {
2451                window_memory_limit = git_config_ulong(k, v);
2452                return 0;
2453        }
2454        if (!strcmp(k, "pack.depth")) {
2455                depth = git_config_int(k, v);
2456                return 0;
2457        }
2458        if (!strcmp(k, "pack.deltacachesize")) {
2459                max_delta_cache_size = git_config_int(k, v);
2460                return 0;
2461        }
2462        if (!strcmp(k, "pack.deltacachelimit")) {
2463                cache_max_small_delta_size = git_config_int(k, v);
2464                return 0;
2465        }
2466        if (!strcmp(k, "pack.writebitmaphashcache")) {
2467                if (git_config_bool(k, v))
2468                        write_bitmap_options |= BITMAP_OPT_HASH_CACHE;
2469                else
2470                        write_bitmap_options &= ~BITMAP_OPT_HASH_CACHE;
2471        }
2472        if (!strcmp(k, "pack.usebitmaps")) {
2473                use_bitmap_index_default = git_config_bool(k, v);
2474                return 0;
2475        }
2476        if (!strcmp(k, "pack.threads")) {
2477                delta_search_threads = git_config_int(k, v);
2478                if (delta_search_threads < 0)
2479                        die("invalid number of threads specified (%d)",
2480                            delta_search_threads);
2481#ifdef NO_PTHREADS
2482                if (delta_search_threads != 1) {
2483                        warning("no threads support, ignoring %s", k);
2484                        delta_search_threads = 0;
2485                }
2486#endif
2487                return 0;
2488        }
2489        if (!strcmp(k, "pack.indexversion")) {
2490                pack_idx_opts.version = git_config_int(k, v);
2491                if (pack_idx_opts.version > 2)
2492                        die("bad pack.indexversion=%"PRIu32,
2493                            pack_idx_opts.version);
2494                return 0;
2495        }
2496        return git_default_config(k, v, cb);
2497}
2498
2499static void read_object_list_from_stdin(void)
2500{
2501        char line[40 + 1 + PATH_MAX + 2];
2502        unsigned char sha1[20];
2503
2504        for (;;) {
2505                if (!fgets(line, sizeof(line), stdin)) {
2506                        if (feof(stdin))
2507                                break;
2508                        if (!ferror(stdin))
2509                                die("fgets returned NULL, not EOF, not error!");
2510                        if (errno != EINTR)
2511                                die_errno("fgets");
2512                        clearerr(stdin);
2513                        continue;
2514                }
2515                if (line[0] == '-') {
2516                        if (get_sha1_hex(line+1, sha1))
2517                                die("expected edge sha1, got garbage:\n %s",
2518                                    line);
2519                        add_preferred_base(sha1);
2520                        continue;
2521                }
2522                if (get_sha1_hex(line, sha1))
2523                        die("expected sha1, got garbage:\n %s", line);
2524
2525                add_preferred_base_object(line+41);
2526                add_object_entry(sha1, 0, line+41, 0);
2527        }
2528}
2529
2530#define OBJECT_ADDED (1u<<20)
2531
2532static void show_commit(struct commit *commit, void *data)
2533{
2534        add_object_entry(commit->object.oid.hash, OBJ_COMMIT, NULL, 0);
2535        commit->object.flags |= OBJECT_ADDED;
2536
2537        if (write_bitmap_index)
2538                index_commit_for_bitmap(commit);
2539}
2540
2541static void show_object(struct object *obj, const char *name, void *data)
2542{
2543        add_preferred_base_object(name);
2544        add_object_entry(obj->oid.hash, obj->type, name, 0);
2545        obj->flags |= OBJECT_ADDED;
2546}
2547
2548static void show_edge(struct commit *commit)
2549{
2550        add_preferred_base(commit->object.oid.hash);
2551}
2552
2553struct in_pack_object {
2554        off_t offset;
2555        struct object *object;
2556};
2557
2558struct in_pack {
2559        int alloc;
2560        int nr;
2561        struct in_pack_object *array;
2562};
2563
2564static void mark_in_pack_object(struct object *object, struct packed_git *p, struct in_pack *in_pack)
2565{
2566        in_pack->array[in_pack->nr].offset = find_pack_entry_one(object->oid.hash, p);
2567        in_pack->array[in_pack->nr].object = object;
2568        in_pack->nr++;
2569}
2570
2571/*
2572 * Compare the objects in the offset order, in order to emulate the
2573 * "git rev-list --objects" output that produced the pack originally.
2574 */
2575static int ofscmp(const void *a_, const void *b_)
2576{
2577        struct in_pack_object *a = (struct in_pack_object *)a_;
2578        struct in_pack_object *b = (struct in_pack_object *)b_;
2579
2580        if (a->offset < b->offset)
2581                return -1;
2582        else if (a->offset > b->offset)
2583                return 1;
2584        else
2585                return oidcmp(&a->object->oid, &b->object->oid);
2586}
2587
2588static void add_objects_in_unpacked_packs(struct rev_info *revs)
2589{
2590        struct packed_git *p;
2591        struct in_pack in_pack;
2592        uint32_t i;
2593
2594        memset(&in_pack, 0, sizeof(in_pack));
2595
2596        for (p = packed_git; p; p = p->next) {
2597                const unsigned char *sha1;
2598                struct object *o;
2599
2600                if (!p->pack_local || p->pack_keep)
2601                        continue;
2602                if (open_pack_index(p))
2603                        die("cannot open pack index");
2604
2605                ALLOC_GROW(in_pack.array,
2606                           in_pack.nr + p->num_objects,
2607                           in_pack.alloc);
2608
2609                for (i = 0; i < p->num_objects; i++) {
2610                        sha1 = nth_packed_object_sha1(p, i);
2611                        o = lookup_unknown_object(sha1);
2612                        if (!(o->flags & OBJECT_ADDED))
2613                                mark_in_pack_object(o, p, &in_pack);
2614                        o->flags |= OBJECT_ADDED;
2615                }
2616        }
2617
2618        if (in_pack.nr) {
2619                QSORT(in_pack.array, in_pack.nr, ofscmp);
2620                for (i = 0; i < in_pack.nr; i++) {
2621                        struct object *o = in_pack.array[i].object;
2622                        add_object_entry(o->oid.hash, o->type, "", 0);
2623                }
2624        }
2625        free(in_pack.array);
2626}
2627
2628static int add_loose_object(const struct object_id *oid, const char *path,
2629                            void *data)
2630{
2631        enum object_type type = sha1_object_info(oid->hash, NULL);
2632
2633        if (type < 0) {
2634                warning("loose object at %s could not be examined", path);
2635                return 0;
2636        }
2637
2638        add_object_entry(oid->hash, type, "", 0);
2639        return 0;
2640}
2641
2642/*
2643 * We actually don't even have to worry about reachability here.
2644 * add_object_entry will weed out duplicates, so we just add every
2645 * loose object we find.
2646 */
2647static void add_unreachable_loose_objects(void)
2648{
2649        for_each_loose_file_in_objdir(get_object_directory(),
2650                                      add_loose_object,
2651                                      NULL, NULL, NULL);
2652}
2653
2654static int has_sha1_pack_kept_or_nonlocal(const unsigned char *sha1)
2655{
2656        static struct packed_git *last_found = (void *)1;
2657        struct packed_git *p;
2658
2659        p = (last_found != (void *)1) ? last_found : packed_git;
2660
2661        while (p) {
2662                if ((!p->pack_local || p->pack_keep) &&
2663                        find_pack_entry_one(sha1, p)) {
2664                        last_found = p;
2665                        return 1;
2666                }
2667                if (p == last_found)
2668                        p = packed_git;
2669                else
2670                        p = p->next;
2671                if (p == last_found)
2672                        p = p->next;
2673        }
2674        return 0;
2675}
2676
2677/*
2678 * Store a list of sha1s that are should not be discarded
2679 * because they are either written too recently, or are
2680 * reachable from another object that was.
2681 *
2682 * This is filled by get_object_list.
2683 */
2684static struct oid_array recent_objects;
2685
2686static int loosened_object_can_be_discarded(const struct object_id *oid,
2687                                            timestamp_t mtime)
2688{
2689        if (!unpack_unreachable_expiration)
2690                return 0;
2691        if (mtime > unpack_unreachable_expiration)
2692                return 0;
2693        if (oid_array_lookup(&recent_objects, oid) >= 0)
2694                return 0;
2695        return 1;
2696}
2697
2698static void loosen_unused_packed_objects(struct rev_info *revs)
2699{
2700        struct packed_git *p;
2701        uint32_t i;
2702        struct object_id oid;
2703
2704        for (p = packed_git; p; p = p->next) {
2705                if (!p->pack_local || p->pack_keep)
2706                        continue;
2707
2708                if (open_pack_index(p))
2709                        die("cannot open pack index");
2710
2711                for (i = 0; i < p->num_objects; i++) {
2712                        nth_packed_object_oid(&oid, p, i);
2713                        if (!packlist_find(&to_pack, oid.hash, NULL) &&
2714                            !has_sha1_pack_kept_or_nonlocal(oid.hash) &&
2715                            !loosened_object_can_be_discarded(&oid, p->mtime))
2716                                if (force_object_loose(oid.hash, p->mtime))
2717                                        die("unable to force loose object");
2718                }
2719        }
2720}
2721
2722/*
2723 * This tracks any options which pack-reuse code expects to be on, or which a
2724 * reader of the pack might not understand, and which would therefore prevent
2725 * blind reuse of what we have on disk.
2726 */
2727static int pack_options_allow_reuse(void)
2728{
2729        return pack_to_stdout &&
2730               allow_ofs_delta &&
2731               !ignore_packed_keep &&
2732               (!local || !have_non_local_packs) &&
2733               !incremental;
2734}
2735
2736static int get_object_list_from_bitmap(struct rev_info *revs)
2737{
2738        if (prepare_bitmap_walk(revs) < 0)
2739                return -1;
2740
2741        if (pack_options_allow_reuse() &&
2742            !reuse_partial_packfile_from_bitmap(
2743                        &reuse_packfile,
2744                        &reuse_packfile_objects,
2745                        &reuse_packfile_offset)) {
2746                assert(reuse_packfile_objects);
2747                nr_result += reuse_packfile_objects;
2748                display_progress(progress_state, nr_result);
2749        }
2750
2751        traverse_bitmap_commit_list(&add_object_entry_from_bitmap);
2752        return 0;
2753}
2754
2755static void record_recent_object(struct object *obj,
2756                                 const char *name,
2757                                 void *data)
2758{
2759        oid_array_append(&recent_objects, &obj->oid);
2760}
2761
2762static void record_recent_commit(struct commit *commit, void *data)
2763{
2764        oid_array_append(&recent_objects, &commit->object.oid);
2765}
2766
2767static void get_object_list(int ac, const char **av)
2768{
2769        struct rev_info revs;
2770        char line[1000];
2771        int flags = 0;
2772
2773        init_revisions(&revs, NULL);
2774        save_commit_buffer = 0;
2775        setup_revisions(ac, av, &revs, NULL);
2776
2777        /* make sure shallows are read */
2778        is_repository_shallow();
2779
2780        while (fgets(line, sizeof(line), stdin) != NULL) {
2781                int len = strlen(line);
2782                if (len && line[len - 1] == '\n')
2783                        line[--len] = 0;
2784                if (!len)
2785                        break;
2786                if (*line == '-') {
2787                        if (!strcmp(line, "--not")) {
2788                                flags ^= UNINTERESTING;
2789                                write_bitmap_index = 0;
2790                                continue;
2791                        }
2792                        if (starts_with(line, "--shallow ")) {
2793                                struct object_id oid;
2794                                if (get_oid_hex(line + 10, &oid))
2795                                        die("not an SHA-1 '%s'", line + 10);
2796                                register_shallow(&oid);
2797                                use_bitmap_index = 0;
2798                                continue;
2799                        }
2800                        die("not a rev '%s'", line);
2801                }
2802                if (handle_revision_arg(line, &revs, flags, REVARG_CANNOT_BE_FILENAME))
2803                        die("bad revision '%s'", line);
2804        }
2805
2806        if (use_bitmap_index && !get_object_list_from_bitmap(&revs))
2807                return;
2808
2809        if (prepare_revision_walk(&revs))
2810                die("revision walk setup failed");
2811        mark_edges_uninteresting(&revs, show_edge);
2812        traverse_commit_list(&revs, show_commit, show_object, NULL);
2813
2814        if (unpack_unreachable_expiration) {
2815                revs.ignore_missing_links = 1;
2816                if (add_unseen_recent_objects_to_traversal(&revs,
2817                                unpack_unreachable_expiration))
2818                        die("unable to add recent objects");
2819                if (prepare_revision_walk(&revs))
2820                        die("revision walk setup failed");
2821                traverse_commit_list(&revs, record_recent_commit,
2822                                     record_recent_object, NULL);
2823        }
2824
2825        if (keep_unreachable)
2826                add_objects_in_unpacked_packs(&revs);
2827        if (pack_loose_unreachable)
2828                add_unreachable_loose_objects();
2829        if (unpack_unreachable)
2830                loosen_unused_packed_objects(&revs);
2831
2832        oid_array_clear(&recent_objects);
2833}
2834
2835static int option_parse_index_version(const struct option *opt,
2836                                      const char *arg, int unset)
2837{
2838        char *c;
2839        const char *val = arg;
2840        pack_idx_opts.version = strtoul(val, &c, 10);
2841        if (pack_idx_opts.version > 2)
2842                die(_("unsupported index version %s"), val);
2843        if (*c == ',' && c[1])
2844                pack_idx_opts.off32_limit = strtoul(c+1, &c, 0);
2845        if (*c || pack_idx_opts.off32_limit & 0x80000000)
2846                die(_("bad index version '%s'"), val);
2847        return 0;
2848}
2849
2850static int option_parse_unpack_unreachable(const struct option *opt,
2851                                           const char *arg, int unset)
2852{
2853        if (unset) {
2854                unpack_unreachable = 0;
2855                unpack_unreachable_expiration = 0;
2856        }
2857        else {
2858                unpack_unreachable = 1;
2859                if (arg)
2860                        unpack_unreachable_expiration = approxidate(arg);
2861        }
2862        return 0;
2863}
2864
2865int cmd_pack_objects(int argc, const char **argv, const char *prefix)
2866{
2867        int use_internal_rev_list = 0;
2868        int thin = 0;
2869        int shallow = 0;
2870        int all_progress_implied = 0;
2871        struct argv_array rp = ARGV_ARRAY_INIT;
2872        int rev_list_unpacked = 0, rev_list_all = 0, rev_list_reflog = 0;
2873        int rev_list_index = 0;
2874        struct option pack_objects_options[] = {
2875                OPT_SET_INT('q', "quiet", &progress,
2876                            N_("do not show progress meter"), 0),
2877                OPT_SET_INT(0, "progress", &progress,
2878                            N_("show progress meter"), 1),
2879                OPT_SET_INT(0, "all-progress", &progress,
2880                            N_("show progress meter during object writing phase"), 2),
2881                OPT_BOOL(0, "all-progress-implied",
2882                         &all_progress_implied,
2883                         N_("similar to --all-progress when progress meter is shown")),
2884                { OPTION_CALLBACK, 0, "index-version", NULL, N_("version[,offset]"),
2885                  N_("write the pack index file in the specified idx format version"),
2886                  0, option_parse_index_version },
2887                OPT_MAGNITUDE(0, "max-pack-size", &pack_size_limit,
2888                              N_("maximum size of each output pack file")),
2889                OPT_BOOL(0, "local", &local,
2890                         N_("ignore borrowed objects from alternate object store")),
2891                OPT_BOOL(0, "incremental", &incremental,
2892                         N_("ignore packed objects")),
2893                OPT_INTEGER(0, "window", &window,
2894                            N_("limit pack window by objects")),
2895                OPT_MAGNITUDE(0, "window-memory", &window_memory_limit,
2896                              N_("limit pack window by memory in addition to object limit")),
2897                OPT_INTEGER(0, "depth", &depth,
2898                            N_("maximum length of delta chain allowed in the resulting pack")),
2899                OPT_BOOL(0, "reuse-delta", &reuse_delta,
2900                         N_("reuse existing deltas")),
2901                OPT_BOOL(0, "reuse-object", &reuse_object,
2902                         N_("reuse existing objects")),
2903                OPT_BOOL(0, "delta-base-offset", &allow_ofs_delta,
2904                         N_("use OFS_DELTA objects")),
2905                OPT_INTEGER(0, "threads", &delta_search_threads,
2906                            N_("use threads when searching for best delta matches")),
2907                OPT_BOOL(0, "non-empty", &non_empty,
2908                         N_("do not create an empty pack output")),
2909                OPT_BOOL(0, "revs", &use_internal_rev_list,
2910                         N_("read revision arguments from standard input")),
2911                { OPTION_SET_INT, 0, "unpacked", &rev_list_unpacked, NULL,
2912                  N_("limit the objects to those that are not yet packed"),
2913                  PARSE_OPT_NOARG | PARSE_OPT_NONEG, NULL, 1 },
2914                { OPTION_SET_INT, 0, "all", &rev_list_all, NULL,
2915                  N_("include objects reachable from any reference"),
2916                  PARSE_OPT_NOARG | PARSE_OPT_NONEG, NULL, 1 },
2917                { OPTION_SET_INT, 0, "reflog", &rev_list_reflog, NULL,
2918                  N_("include objects referred by reflog entries"),
2919                  PARSE_OPT_NOARG | PARSE_OPT_NONEG, NULL, 1 },
2920                { OPTION_SET_INT, 0, "indexed-objects", &rev_list_index, NULL,
2921                  N_("include objects referred to by the index"),
2922                  PARSE_OPT_NOARG | PARSE_OPT_NONEG, NULL, 1 },
2923                OPT_BOOL(0, "stdout", &pack_to_stdout,
2924                         N_("output pack to stdout")),
2925                OPT_BOOL(0, "include-tag", &include_tag,
2926                         N_("include tag objects that refer to objects to be packed")),
2927                OPT_BOOL(0, "keep-unreachable", &keep_unreachable,
2928                         N_("keep unreachable objects")),
2929                OPT_BOOL(0, "pack-loose-unreachable", &pack_loose_unreachable,
2930                         N_("pack loose unreachable objects")),
2931                { OPTION_CALLBACK, 0, "unpack-unreachable", NULL, N_("time"),
2932                  N_("unpack unreachable objects newer than <time>"),
2933                  PARSE_OPT_OPTARG, option_parse_unpack_unreachable },
2934                OPT_BOOL(0, "thin", &thin,
2935                         N_("create thin packs")),
2936                OPT_BOOL(0, "shallow", &shallow,
2937                         N_("create packs suitable for shallow fetches")),
2938                OPT_BOOL(0, "honor-pack-keep", &ignore_packed_keep,
2939                         N_("ignore packs that have companion .keep file")),
2940                OPT_INTEGER(0, "compression", &pack_compression_level,
2941                            N_("pack compression level")),
2942                OPT_SET_INT(0, "keep-true-parents", &grafts_replace_parents,
2943                            N_("do not hide commits by grafts"), 0),
2944                OPT_BOOL(0, "use-bitmap-index", &use_bitmap_index,
2945                         N_("use a bitmap index if available to speed up counting objects")),
2946                OPT_BOOL(0, "write-bitmap-index", &write_bitmap_index,
2947                         N_("write a bitmap index together with the pack index")),
2948                OPT_END(),
2949        };
2950
2951        check_replace_refs = 0;
2952
2953        reset_pack_idx_option(&pack_idx_opts);
2954        git_config(git_pack_config, NULL);
2955
2956        progress = isatty(2);
2957        argc = parse_options(argc, argv, prefix, pack_objects_options,
2958                             pack_usage, 0);
2959
2960        if (argc) {
2961                base_name = argv[0];
2962                argc--;
2963        }
2964        if (pack_to_stdout != !base_name || argc)
2965                usage_with_options(pack_usage, pack_objects_options);
2966
2967        argv_array_push(&rp, "pack-objects");
2968        if (thin) {
2969                use_internal_rev_list = 1;
2970                argv_array_push(&rp, shallow
2971                                ? "--objects-edge-aggressive"
2972                                : "--objects-edge");
2973        } else
2974                argv_array_push(&rp, "--objects");
2975
2976        if (rev_list_all) {
2977                use_internal_rev_list = 1;
2978                argv_array_push(&rp, "--all");
2979        }
2980        if (rev_list_reflog) {
2981                use_internal_rev_list = 1;
2982                argv_array_push(&rp, "--reflog");
2983        }
2984        if (rev_list_index) {
2985                use_internal_rev_list = 1;
2986                argv_array_push(&rp, "--indexed-objects");
2987        }
2988        if (rev_list_unpacked) {
2989                use_internal_rev_list = 1;
2990                argv_array_push(&rp, "--unpacked");
2991        }
2992
2993        if (!reuse_object)
2994                reuse_delta = 0;
2995        if (pack_compression_level == -1)
2996                pack_compression_level = Z_DEFAULT_COMPRESSION;
2997        else if (pack_compression_level < 0 || pack_compression_level > Z_BEST_COMPRESSION)
2998                die("bad pack compression level %d", pack_compression_level);
2999
3000        if (!delta_search_threads)      /* --threads=0 means autodetect */
3001                delta_search_threads = online_cpus();
3002
3003#ifdef NO_PTHREADS
3004        if (delta_search_threads != 1)
3005                warning("no threads support, ignoring --threads");
3006#endif
3007        if (!pack_to_stdout && !pack_size_limit)
3008                pack_size_limit = pack_size_limit_cfg;
3009        if (pack_to_stdout && pack_size_limit)
3010                die("--max-pack-size cannot be used to build a pack for transfer.");
3011        if (pack_size_limit && pack_size_limit < 1024*1024) {
3012                warning("minimum pack size limit is 1 MiB");
3013                pack_size_limit = 1024*1024;
3014        }
3015
3016        if (!pack_to_stdout && thin)
3017                die("--thin cannot be used to build an indexable pack.");
3018
3019        if (keep_unreachable && unpack_unreachable)
3020                die("--keep-unreachable and --unpack-unreachable are incompatible.");
3021        if (!rev_list_all || !rev_list_reflog || !rev_list_index)
3022                unpack_unreachable_expiration = 0;
3023
3024        /*
3025         * "soft" reasons not to use bitmaps - for on-disk repack by default we want
3026         *
3027         * - to produce good pack (with bitmap index not-yet-packed objects are
3028         *   packed in suboptimal order).
3029         *
3030         * - to use more robust pack-generation codepath (avoiding possible
3031         *   bugs in bitmap code and possible bitmap index corruption).
3032         */
3033        if (!pack_to_stdout)
3034                use_bitmap_index_default = 0;
3035
3036        if (use_bitmap_index < 0)
3037                use_bitmap_index = use_bitmap_index_default;
3038
3039        /* "hard" reasons not to use bitmaps; these just won't work at all */
3040        if (!use_internal_rev_list || (!pack_to_stdout && write_bitmap_index) || is_repository_shallow())
3041                use_bitmap_index = 0;
3042
3043        if (pack_to_stdout || !rev_list_all)
3044                write_bitmap_index = 0;
3045
3046        if (progress && all_progress_implied)
3047                progress = 2;
3048
3049        prepare_packed_git();
3050        if (ignore_packed_keep) {
3051                struct packed_git *p;
3052                for (p = packed_git; p; p = p->next)
3053                        if (p->pack_local && p->pack_keep)
3054                                break;
3055                if (!p) /* no keep-able packs found */
3056                        ignore_packed_keep = 0;
3057        }
3058        if (local) {
3059                /*
3060                 * unlike ignore_packed_keep above, we do not want to
3061                 * unset "local" based on looking at packs, as it
3062                 * also covers non-local objects
3063                 */
3064                struct packed_git *p;
3065                for (p = packed_git; p; p = p->next) {
3066                        if (!p->pack_local) {
3067                                have_non_local_packs = 1;
3068                                break;
3069                        }
3070                }
3071        }
3072
3073        if (progress)
3074                progress_state = start_progress(_("Counting objects"), 0);
3075        if (!use_internal_rev_list)
3076                read_object_list_from_stdin();
3077        else {
3078                get_object_list(rp.argc, rp.argv);
3079                argv_array_clear(&rp);
3080        }
3081        cleanup_preferred_base();
3082        if (include_tag && nr_result)
3083                for_each_ref(add_ref_tag, NULL);
3084        stop_progress(&progress_state);
3085
3086        if (non_empty && !nr_result)
3087                return 0;
3088        if (nr_result)
3089                prepare_pack(window, depth);
3090        write_pack_file();
3091        if (progress)
3092                fprintf(stderr, "Total %"PRIu32" (delta %"PRIu32"),"
3093                        " reused %"PRIu32" (delta %"PRIu32")\n",
3094                        written, written_delta, reused, reused_delta);
3095        return 0;
3096}