builtin-pack-objects.con commit tests: update tests that used to fail (df3dac3)
   1#include "builtin.h"
   2#include "cache.h"
   3#include "attr.h"
   4#include "object.h"
   5#include "blob.h"
   6#include "commit.h"
   7#include "tag.h"
   8#include "tree.h"
   9#include "delta.h"
  10#include "pack.h"
  11#include "pack-revindex.h"
  12#include "csum-file.h"
  13#include "tree-walk.h"
  14#include "diff.h"
  15#include "revision.h"
  16#include "list-objects.h"
  17#include "progress.h"
  18#include "refs.h"
  19
  20#ifdef THREADED_DELTA_SEARCH
  21#include "thread-utils.h"
  22#include <pthread.h>
  23#endif
  24
  25static const char pack_usage[] =
  26  "git pack-objects [{ -q | --progress | --all-progress }]\n"
  27  "        [--all-progress-implied]\n"
  28  "        [--max-pack-size=N] [--local] [--incremental]\n"
  29  "        [--window=N] [--window-memory=N] [--depth=N]\n"
  30  "        [--no-reuse-delta] [--no-reuse-object] [--delta-base-offset]\n"
  31  "        [--threads=N] [--non-empty] [--revs [--unpacked | --all]*]\n"
  32  "        [--reflog] [--stdout | base-name] [--include-tag]\n"
  33  "        [--keep-unreachable | --unpack-unreachable \n"
  34  "        [<ref-list | <object-list]";
  35
  36struct object_entry {
  37        struct pack_idx_entry idx;
  38        unsigned long size;     /* uncompressed size */
  39        struct packed_git *in_pack;     /* already in pack */
  40        off_t in_pack_offset;
  41        struct object_entry *delta;     /* delta base object */
  42        struct object_entry *delta_child; /* deltified objects who bases me */
  43        struct object_entry *delta_sibling; /* other deltified objects who
  44                                             * uses the same base as me
  45                                             */
  46        void *delta_data;       /* cached delta (uncompressed) */
  47        unsigned long delta_size;       /* delta data size (uncompressed) */
  48        unsigned long z_delta_size;     /* delta data size (compressed) */
  49        unsigned int hash;      /* name hint hash */
  50        enum object_type type;
  51        enum object_type in_pack_type;  /* could be delta */
  52        unsigned char in_pack_header_size;
  53        unsigned char preferred_base; /* we do not pack this, but is available
  54                                       * to be used as the base object to delta
  55                                       * objects against.
  56                                       */
  57        unsigned char no_try_delta;
  58};
  59
  60/*
  61 * Objects we are going to pack are collected in objects array (dynamically
  62 * expanded).  nr_objects & nr_alloc controls this array.  They are stored
  63 * in the order we see -- typically rev-list --objects order that gives us
  64 * nice "minimum seek" order.
  65 */
  66static struct object_entry *objects;
  67static struct pack_idx_entry **written_list;
  68static uint32_t nr_objects, nr_alloc, nr_result, nr_written;
  69
  70static int non_empty;
  71static int reuse_delta = 1, reuse_object = 1;
  72static int keep_unreachable, unpack_unreachable, include_tag;
  73static int local;
  74static int incremental;
  75static int ignore_packed_keep;
  76static int allow_ofs_delta;
  77static const char *base_name;
  78static int progress = 1;
  79static int window = 10;
  80static uint32_t pack_size_limit, pack_size_limit_cfg;
  81static int depth = 50;
  82static int delta_search_threads;
  83static int pack_to_stdout;
  84static int num_preferred_base;
  85static struct progress *progress_state;
  86static int pack_compression_level = Z_DEFAULT_COMPRESSION;
  87static int pack_compression_seen;
  88
  89static unsigned long delta_cache_size = 0;
  90static unsigned long max_delta_cache_size = 256 * 1024 * 1024;
  91static unsigned long cache_max_small_delta_size = 1000;
  92
  93static unsigned long window_memory_limit = 0;
  94
  95/*
  96 * The object names in objects array are hashed with this hashtable,
  97 * to help looking up the entry by object name.
  98 * This hashtable is built after all the objects are seen.
  99 */
 100static int *object_ix;
 101static int object_ix_hashsz;
 102
 103/*
 104 * stats
 105 */
 106static uint32_t written, written_delta;
 107static uint32_t reused, reused_delta;
 108
 109
 110static void *get_delta(struct object_entry *entry)
 111{
 112        unsigned long size, base_size, delta_size;
 113        void *buf, *base_buf, *delta_buf;
 114        enum object_type type;
 115
 116        buf = read_sha1_file(entry->idx.sha1, &type, &size);
 117        if (!buf)
 118                die("unable to read %s", sha1_to_hex(entry->idx.sha1));
 119        base_buf = read_sha1_file(entry->delta->idx.sha1, &type, &base_size);
 120        if (!base_buf)
 121                die("unable to read %s", sha1_to_hex(entry->delta->idx.sha1));
 122        delta_buf = diff_delta(base_buf, base_size,
 123                               buf, size, &delta_size, 0);
 124        if (!delta_buf || delta_size != entry->delta_size)
 125                die("delta size changed");
 126        free(buf);
 127        free(base_buf);
 128        return delta_buf;
 129}
 130
 131static unsigned long do_compress(void **pptr, unsigned long size)
 132{
 133        z_stream stream;
 134        void *in, *out;
 135        unsigned long maxsize;
 136
 137        memset(&stream, 0, sizeof(stream));
 138        deflateInit(&stream, pack_compression_level);
 139        maxsize = deflateBound(&stream, size);
 140
 141        in = *pptr;
 142        out = xmalloc(maxsize);
 143        *pptr = out;
 144
 145        stream.next_in = in;
 146        stream.avail_in = size;
 147        stream.next_out = out;
 148        stream.avail_out = maxsize;
 149        while (deflate(&stream, Z_FINISH) == Z_OK)
 150                ; /* nothing */
 151        deflateEnd(&stream);
 152
 153        free(in);
 154        return stream.total_out;
 155}
 156
 157/*
 158 * The per-object header is a pretty dense thing, which is
 159 *  - first byte: low four bits are "size", then three bits of "type",
 160 *    and the high bit is "size continues".
 161 *  - each byte afterwards: low seven bits are size continuation,
 162 *    with the high bit being "size continues"
 163 */
 164static int encode_header(enum object_type type, unsigned long size, unsigned char *hdr)
 165{
 166        int n = 1;
 167        unsigned char c;
 168
 169        if (type < OBJ_COMMIT || type > OBJ_REF_DELTA)
 170                die("bad type %d", type);
 171
 172        c = (type << 4) | (size & 15);
 173        size >>= 4;
 174        while (size) {
 175                *hdr++ = c | 0x80;
 176                c = size & 0x7f;
 177                size >>= 7;
 178                n++;
 179        }
 180        *hdr = c;
 181        return n;
 182}
 183
 184/*
 185 * we are going to reuse the existing object data as is.  make
 186 * sure it is not corrupt.
 187 */
 188static int check_pack_inflate(struct packed_git *p,
 189                struct pack_window **w_curs,
 190                off_t offset,
 191                off_t len,
 192                unsigned long expect)
 193{
 194        z_stream stream;
 195        unsigned char fakebuf[4096], *in;
 196        int st;
 197
 198        memset(&stream, 0, sizeof(stream));
 199        git_inflate_init(&stream);
 200        do {
 201                in = use_pack(p, w_curs, offset, &stream.avail_in);
 202                stream.next_in = in;
 203                stream.next_out = fakebuf;
 204                stream.avail_out = sizeof(fakebuf);
 205                st = git_inflate(&stream, Z_FINISH);
 206                offset += stream.next_in - in;
 207        } while (st == Z_OK || st == Z_BUF_ERROR);
 208        git_inflate_end(&stream);
 209        return (st == Z_STREAM_END &&
 210                stream.total_out == expect &&
 211                stream.total_in == len) ? 0 : -1;
 212}
 213
 214static void copy_pack_data(struct sha1file *f,
 215                struct packed_git *p,
 216                struct pack_window **w_curs,
 217                off_t offset,
 218                off_t len)
 219{
 220        unsigned char *in;
 221        unsigned int avail;
 222
 223        while (len) {
 224                in = use_pack(p, w_curs, offset, &avail);
 225                if (avail > len)
 226                        avail = (unsigned int)len;
 227                sha1write(f, in, avail);
 228                offset += avail;
 229                len -= avail;
 230        }
 231}
 232
 233static unsigned long write_object(struct sha1file *f,
 234                                  struct object_entry *entry,
 235                                  off_t write_offset)
 236{
 237        unsigned long size, limit, datalen;
 238        void *buf;
 239        unsigned char header[10], dheader[10];
 240        unsigned hdrlen;
 241        enum object_type type;
 242        int usable_delta, to_reuse;
 243
 244        if (!pack_to_stdout)
 245                crc32_begin(f);
 246
 247        type = entry->type;
 248
 249        /* write limit if limited packsize and not first object */
 250        if (!pack_size_limit || !nr_written)
 251                limit = 0;
 252        else if (pack_size_limit <= write_offset)
 253                /*
 254                 * the earlier object did not fit the limit; avoid
 255                 * mistaking this with unlimited (i.e. limit = 0).
 256                 */
 257                limit = 1;
 258        else
 259                limit = pack_size_limit - write_offset;
 260
 261        if (!entry->delta)
 262                usable_delta = 0;       /* no delta */
 263        else if (!pack_size_limit)
 264               usable_delta = 1;        /* unlimited packfile */
 265        else if (entry->delta->idx.offset == (off_t)-1)
 266                usable_delta = 0;       /* base was written to another pack */
 267        else if (entry->delta->idx.offset)
 268                usable_delta = 1;       /* base already exists in this pack */
 269        else
 270                usable_delta = 0;       /* base could end up in another pack */
 271
 272        if (!reuse_object)
 273                to_reuse = 0;   /* explicit */
 274        else if (!entry->in_pack)
 275                to_reuse = 0;   /* can't reuse what we don't have */
 276        else if (type == OBJ_REF_DELTA || type == OBJ_OFS_DELTA)
 277                                /* check_object() decided it for us ... */
 278                to_reuse = usable_delta;
 279                                /* ... but pack split may override that */
 280        else if (type != entry->in_pack_type)
 281                to_reuse = 0;   /* pack has delta which is unusable */
 282        else if (entry->delta)
 283                to_reuse = 0;   /* we want to pack afresh */
 284        else
 285                to_reuse = 1;   /* we have it in-pack undeltified,
 286                                 * and we do not need to deltify it.
 287                                 */
 288
 289        if (!to_reuse) {
 290                no_reuse:
 291                if (!usable_delta) {
 292                        buf = read_sha1_file(entry->idx.sha1, &type, &size);
 293                        if (!buf)
 294                                die("unable to read %s", sha1_to_hex(entry->idx.sha1));
 295                        /*
 296                         * make sure no cached delta data remains from a
 297                         * previous attempt before a pack split occurred.
 298                         */
 299                        free(entry->delta_data);
 300                        entry->delta_data = NULL;
 301                        entry->z_delta_size = 0;
 302                } else if (entry->delta_data) {
 303                        size = entry->delta_size;
 304                        buf = entry->delta_data;
 305                        entry->delta_data = NULL;
 306                        type = (allow_ofs_delta && entry->delta->idx.offset) ?
 307                                OBJ_OFS_DELTA : OBJ_REF_DELTA;
 308                } else {
 309                        buf = get_delta(entry);
 310                        size = entry->delta_size;
 311                        type = (allow_ofs_delta && entry->delta->idx.offset) ?
 312                                OBJ_OFS_DELTA : OBJ_REF_DELTA;
 313                }
 314
 315                if (entry->z_delta_size)
 316                        datalen = entry->z_delta_size;
 317                else
 318                        datalen = do_compress(&buf, size);
 319
 320                /*
 321                 * The object header is a byte of 'type' followed by zero or
 322                 * more bytes of length.
 323                 */
 324                hdrlen = encode_header(type, size, header);
 325
 326                if (type == OBJ_OFS_DELTA) {
 327                        /*
 328                         * Deltas with relative base contain an additional
 329                         * encoding of the relative offset for the delta
 330                         * base from this object's position in the pack.
 331                         */
 332                        off_t ofs = entry->idx.offset - entry->delta->idx.offset;
 333                        unsigned pos = sizeof(dheader) - 1;
 334                        dheader[pos] = ofs & 127;
 335                        while (ofs >>= 7)
 336                                dheader[--pos] = 128 | (--ofs & 127);
 337                        if (limit && hdrlen + sizeof(dheader) - pos + datalen + 20 >= limit) {
 338                                free(buf);
 339                                return 0;
 340                        }
 341                        sha1write(f, header, hdrlen);
 342                        sha1write(f, dheader + pos, sizeof(dheader) - pos);
 343                        hdrlen += sizeof(dheader) - pos;
 344                } else if (type == OBJ_REF_DELTA) {
 345                        /*
 346                         * Deltas with a base reference contain
 347                         * an additional 20 bytes for the base sha1.
 348                         */
 349                        if (limit && hdrlen + 20 + datalen + 20 >= limit) {
 350                                free(buf);
 351                                return 0;
 352                        }
 353                        sha1write(f, header, hdrlen);
 354                        sha1write(f, entry->delta->idx.sha1, 20);
 355                        hdrlen += 20;
 356                } else {
 357                        if (limit && hdrlen + datalen + 20 >= limit) {
 358                                free(buf);
 359                                return 0;
 360                        }
 361                        sha1write(f, header, hdrlen);
 362                }
 363                sha1write(f, buf, datalen);
 364                free(buf);
 365        }
 366        else {
 367                struct packed_git *p = entry->in_pack;
 368                struct pack_window *w_curs = NULL;
 369                struct revindex_entry *revidx;
 370                off_t offset;
 371
 372                if (entry->delta)
 373                        type = (allow_ofs_delta && entry->delta->idx.offset) ?
 374                                OBJ_OFS_DELTA : OBJ_REF_DELTA;
 375                hdrlen = encode_header(type, entry->size, header);
 376
 377                offset = entry->in_pack_offset;
 378                revidx = find_pack_revindex(p, offset);
 379                datalen = revidx[1].offset - offset;
 380                if (!pack_to_stdout && p->index_version > 1 &&
 381                    check_pack_crc(p, &w_curs, offset, datalen, revidx->nr)) {
 382                        error("bad packed object CRC for %s", sha1_to_hex(entry->idx.sha1));
 383                        unuse_pack(&w_curs);
 384                        goto no_reuse;
 385                }
 386
 387                offset += entry->in_pack_header_size;
 388                datalen -= entry->in_pack_header_size;
 389                if (!pack_to_stdout && p->index_version == 1 &&
 390                    check_pack_inflate(p, &w_curs, offset, datalen, entry->size)) {
 391                        error("corrupt packed object for %s", sha1_to_hex(entry->idx.sha1));
 392                        unuse_pack(&w_curs);
 393                        goto no_reuse;
 394                }
 395
 396                if (type == OBJ_OFS_DELTA) {
 397                        off_t ofs = entry->idx.offset - entry->delta->idx.offset;
 398                        unsigned pos = sizeof(dheader) - 1;
 399                        dheader[pos] = ofs & 127;
 400                        while (ofs >>= 7)
 401                                dheader[--pos] = 128 | (--ofs & 127);
 402                        if (limit && hdrlen + sizeof(dheader) - pos + datalen + 20 >= limit) {
 403                                unuse_pack(&w_curs);
 404                                return 0;
 405                        }
 406                        sha1write(f, header, hdrlen);
 407                        sha1write(f, dheader + pos, sizeof(dheader) - pos);
 408                        hdrlen += sizeof(dheader) - pos;
 409                        reused_delta++;
 410                } else if (type == OBJ_REF_DELTA) {
 411                        if (limit && hdrlen + 20 + datalen + 20 >= limit) {
 412                                unuse_pack(&w_curs);
 413                                return 0;
 414                        }
 415                        sha1write(f, header, hdrlen);
 416                        sha1write(f, entry->delta->idx.sha1, 20);
 417                        hdrlen += 20;
 418                        reused_delta++;
 419                } else {
 420                        if (limit && hdrlen + datalen + 20 >= limit) {
 421                                unuse_pack(&w_curs);
 422                                return 0;
 423                        }
 424                        sha1write(f, header, hdrlen);
 425                }
 426                copy_pack_data(f, p, &w_curs, offset, datalen);
 427                unuse_pack(&w_curs);
 428                reused++;
 429        }
 430        if (usable_delta)
 431                written_delta++;
 432        written++;
 433        if (!pack_to_stdout)
 434                entry->idx.crc32 = crc32_end(f);
 435        return hdrlen + datalen;
 436}
 437
 438static int write_one(struct sha1file *f,
 439                               struct object_entry *e,
 440                               off_t *offset)
 441{
 442        unsigned long size;
 443
 444        /* offset is non zero if object is written already. */
 445        if (e->idx.offset || e->preferred_base)
 446                return 1;
 447
 448        /* if we are deltified, write out base object first. */
 449        if (e->delta && !write_one(f, e->delta, offset))
 450                return 0;
 451
 452        e->idx.offset = *offset;
 453        size = write_object(f, e, *offset);
 454        if (!size) {
 455                e->idx.offset = 0;
 456                return 0;
 457        }
 458        written_list[nr_written++] = &e->idx;
 459
 460        /* make sure off_t is sufficiently large not to wrap */
 461        if (*offset > *offset + size)
 462                die("pack too large for current definition of off_t");
 463        *offset += size;
 464        return 1;
 465}
 466
 467/* forward declaration for write_pack_file */
 468static int adjust_perm(const char *path, mode_t mode);
 469
 470static void write_pack_file(void)
 471{
 472        uint32_t i = 0, j;
 473        struct sha1file *f;
 474        off_t offset;
 475        struct pack_header hdr;
 476        uint32_t nr_remaining = nr_result;
 477        time_t last_mtime = 0;
 478
 479        if (progress > pack_to_stdout)
 480                progress_state = start_progress("Writing objects", nr_result);
 481        written_list = xmalloc(nr_objects * sizeof(*written_list));
 482
 483        do {
 484                unsigned char sha1[20];
 485                char *pack_tmp_name = NULL;
 486
 487                if (pack_to_stdout) {
 488                        f = sha1fd_throughput(1, "<stdout>", progress_state);
 489                } else {
 490                        char tmpname[PATH_MAX];
 491                        int fd;
 492                        fd = odb_mkstemp(tmpname, sizeof(tmpname),
 493                                         "pack/tmp_pack_XXXXXX");
 494                        pack_tmp_name = xstrdup(tmpname);
 495                        f = sha1fd(fd, pack_tmp_name);
 496                }
 497
 498                hdr.hdr_signature = htonl(PACK_SIGNATURE);
 499                hdr.hdr_version = htonl(PACK_VERSION);
 500                hdr.hdr_entries = htonl(nr_remaining);
 501                sha1write(f, &hdr, sizeof(hdr));
 502                offset = sizeof(hdr);
 503                nr_written = 0;
 504                for (; i < nr_objects; i++) {
 505                        if (!write_one(f, objects + i, &offset))
 506                                break;
 507                        display_progress(progress_state, written);
 508                }
 509
 510                /*
 511                 * Did we write the wrong # entries in the header?
 512                 * If so, rewrite it like in fast-import
 513                 */
 514                if (pack_to_stdout) {
 515                        sha1close(f, sha1, CSUM_CLOSE);
 516                } else if (nr_written == nr_remaining) {
 517                        sha1close(f, sha1, CSUM_FSYNC);
 518                } else {
 519                        int fd = sha1close(f, sha1, 0);
 520                        fixup_pack_header_footer(fd, sha1, pack_tmp_name,
 521                                                 nr_written, sha1, offset);
 522                        close(fd);
 523                }
 524
 525                if (!pack_to_stdout) {
 526                        mode_t mode = umask(0);
 527                        struct stat st;
 528                        const char *idx_tmp_name;
 529                        char tmpname[PATH_MAX];
 530
 531                        umask(mode);
 532                        mode = 0444 & ~mode;
 533
 534                        idx_tmp_name = write_idx_file(NULL, written_list,
 535                                                      nr_written, sha1);
 536
 537                        snprintf(tmpname, sizeof(tmpname), "%s-%s.pack",
 538                                 base_name, sha1_to_hex(sha1));
 539                        free_pack_by_name(tmpname);
 540                        if (adjust_perm(pack_tmp_name, mode))
 541                                die_errno("unable to make temporary pack file readable");
 542                        if (rename(pack_tmp_name, tmpname))
 543                                die_errno("unable to rename temporary pack file");
 544
 545                        /*
 546                         * Packs are runtime accessed in their mtime
 547                         * order since newer packs are more likely to contain
 548                         * younger objects.  So if we are creating multiple
 549                         * packs then we should modify the mtime of later ones
 550                         * to preserve this property.
 551                         */
 552                        if (stat(tmpname, &st) < 0) {
 553                                warning("failed to stat %s: %s",
 554                                        tmpname, strerror(errno));
 555                        } else if (!last_mtime) {
 556                                last_mtime = st.st_mtime;
 557                        } else {
 558                                struct utimbuf utb;
 559                                utb.actime = st.st_atime;
 560                                utb.modtime = --last_mtime;
 561                                if (utime(tmpname, &utb) < 0)
 562                                        warning("failed utime() on %s: %s",
 563                                                tmpname, strerror(errno));
 564                        }
 565
 566                        snprintf(tmpname, sizeof(tmpname), "%s-%s.idx",
 567                                 base_name, sha1_to_hex(sha1));
 568                        if (adjust_perm(idx_tmp_name, mode))
 569                                die_errno("unable to make temporary index file readable");
 570                        if (rename(idx_tmp_name, tmpname))
 571                                die_errno("unable to rename temporary index file");
 572
 573                        free((void *) idx_tmp_name);
 574                        free(pack_tmp_name);
 575                        puts(sha1_to_hex(sha1));
 576                }
 577
 578                /* mark written objects as written to previous pack */
 579                for (j = 0; j < nr_written; j++) {
 580                        written_list[j]->offset = (off_t)-1;
 581                }
 582                nr_remaining -= nr_written;
 583        } while (nr_remaining && i < nr_objects);
 584
 585        free(written_list);
 586        stop_progress(&progress_state);
 587        if (written != nr_result)
 588                die("wrote %"PRIu32" objects while expecting %"PRIu32,
 589                        written, nr_result);
 590        /*
 591         * We have scanned through [0 ... i).  Since we have written
 592         * the correct number of objects,  the remaining [i ... nr_objects)
 593         * items must be either already written (due to out-of-order delta base)
 594         * or a preferred base.  Count those which are neither and complain if any.
 595         */
 596        for (j = 0; i < nr_objects; i++) {
 597                struct object_entry *e = objects + i;
 598                j += !e->idx.offset && !e->preferred_base;
 599        }
 600        if (j)
 601                die("wrote %"PRIu32" objects as expected but %"PRIu32
 602                        " unwritten", written, j);
 603}
 604
 605static int locate_object_entry_hash(const unsigned char *sha1)
 606{
 607        int i;
 608        unsigned int ui;
 609        memcpy(&ui, sha1, sizeof(unsigned int));
 610        i = ui % object_ix_hashsz;
 611        while (0 < object_ix[i]) {
 612                if (!hashcmp(sha1, objects[object_ix[i] - 1].idx.sha1))
 613                        return i;
 614                if (++i == object_ix_hashsz)
 615                        i = 0;
 616        }
 617        return -1 - i;
 618}
 619
 620static struct object_entry *locate_object_entry(const unsigned char *sha1)
 621{
 622        int i;
 623
 624        if (!object_ix_hashsz)
 625                return NULL;
 626
 627        i = locate_object_entry_hash(sha1);
 628        if (0 <= i)
 629                return &objects[object_ix[i]-1];
 630        return NULL;
 631}
 632
 633static void rehash_objects(void)
 634{
 635        uint32_t i;
 636        struct object_entry *oe;
 637
 638        object_ix_hashsz = nr_objects * 3;
 639        if (object_ix_hashsz < 1024)
 640                object_ix_hashsz = 1024;
 641        object_ix = xrealloc(object_ix, sizeof(int) * object_ix_hashsz);
 642        memset(object_ix, 0, sizeof(int) * object_ix_hashsz);
 643        for (i = 0, oe = objects; i < nr_objects; i++, oe++) {
 644                int ix = locate_object_entry_hash(oe->idx.sha1);
 645                if (0 <= ix)
 646                        continue;
 647                ix = -1 - ix;
 648                object_ix[ix] = i + 1;
 649        }
 650}
 651
 652static unsigned name_hash(const char *name)
 653{
 654        unsigned c, hash = 0;
 655
 656        if (!name)
 657                return 0;
 658
 659        /*
 660         * This effectively just creates a sortable number from the
 661         * last sixteen non-whitespace characters. Last characters
 662         * count "most", so things that end in ".c" sort together.
 663         */
 664        while ((c = *name++) != 0) {
 665                if (isspace(c))
 666                        continue;
 667                hash = (hash >> 2) + (c << 24);
 668        }
 669        return hash;
 670}
 671
 672static void setup_delta_attr_check(struct git_attr_check *check)
 673{
 674        static struct git_attr *attr_delta;
 675
 676        if (!attr_delta)
 677                attr_delta = git_attr("delta");
 678
 679        check[0].attr = attr_delta;
 680}
 681
 682static int no_try_delta(const char *path)
 683{
 684        struct git_attr_check check[1];
 685
 686        setup_delta_attr_check(check);
 687        if (git_checkattr(path, ARRAY_SIZE(check), check))
 688                return 0;
 689        if (ATTR_FALSE(check->value))
 690                return 1;
 691        return 0;
 692}
 693
 694static int add_object_entry(const unsigned char *sha1, enum object_type type,
 695                            const char *name, int exclude)
 696{
 697        struct object_entry *entry;
 698        struct packed_git *p, *found_pack = NULL;
 699        off_t found_offset = 0;
 700        int ix;
 701        unsigned hash = name_hash(name);
 702
 703        ix = nr_objects ? locate_object_entry_hash(sha1) : -1;
 704        if (ix >= 0) {
 705                if (exclude) {
 706                        entry = objects + object_ix[ix] - 1;
 707                        if (!entry->preferred_base)
 708                                nr_result--;
 709                        entry->preferred_base = 1;
 710                }
 711                return 0;
 712        }
 713
 714        if (!exclude && local && has_loose_object_nonlocal(sha1))
 715                return 0;
 716
 717        for (p = packed_git; p; p = p->next) {
 718                off_t offset = find_pack_entry_one(sha1, p);
 719                if (offset) {
 720                        if (!found_pack) {
 721                                found_offset = offset;
 722                                found_pack = p;
 723                        }
 724                        if (exclude)
 725                                break;
 726                        if (incremental)
 727                                return 0;
 728                        if (local && !p->pack_local)
 729                                return 0;
 730                        if (ignore_packed_keep && p->pack_local && p->pack_keep)
 731                                return 0;
 732                }
 733        }
 734
 735        if (nr_objects >= nr_alloc) {
 736                nr_alloc = (nr_alloc  + 1024) * 3 / 2;
 737                objects = xrealloc(objects, nr_alloc * sizeof(*entry));
 738        }
 739
 740        entry = objects + nr_objects++;
 741        memset(entry, 0, sizeof(*entry));
 742        hashcpy(entry->idx.sha1, sha1);
 743        entry->hash = hash;
 744        if (type)
 745                entry->type = type;
 746        if (exclude)
 747                entry->preferred_base = 1;
 748        else
 749                nr_result++;
 750        if (found_pack) {
 751                entry->in_pack = found_pack;
 752                entry->in_pack_offset = found_offset;
 753        }
 754
 755        if (object_ix_hashsz * 3 <= nr_objects * 4)
 756                rehash_objects();
 757        else
 758                object_ix[-1 - ix] = nr_objects;
 759
 760        display_progress(progress_state, nr_objects);
 761
 762        if (name && no_try_delta(name))
 763                entry->no_try_delta = 1;
 764
 765        return 1;
 766}
 767
 768struct pbase_tree_cache {
 769        unsigned char sha1[20];
 770        int ref;
 771        int temporary;
 772        void *tree_data;
 773        unsigned long tree_size;
 774};
 775
 776static struct pbase_tree_cache *(pbase_tree_cache[256]);
 777static int pbase_tree_cache_ix(const unsigned char *sha1)
 778{
 779        return sha1[0] % ARRAY_SIZE(pbase_tree_cache);
 780}
 781static int pbase_tree_cache_ix_incr(int ix)
 782{
 783        return (ix+1) % ARRAY_SIZE(pbase_tree_cache);
 784}
 785
 786static struct pbase_tree {
 787        struct pbase_tree *next;
 788        /* This is a phony "cache" entry; we are not
 789         * going to evict it nor find it through _get()
 790         * mechanism -- this is for the toplevel node that
 791         * would almost always change with any commit.
 792         */
 793        struct pbase_tree_cache pcache;
 794} *pbase_tree;
 795
 796static struct pbase_tree_cache *pbase_tree_get(const unsigned char *sha1)
 797{
 798        struct pbase_tree_cache *ent, *nent;
 799        void *data;
 800        unsigned long size;
 801        enum object_type type;
 802        int neigh;
 803        int my_ix = pbase_tree_cache_ix(sha1);
 804        int available_ix = -1;
 805
 806        /* pbase-tree-cache acts as a limited hashtable.
 807         * your object will be found at your index or within a few
 808         * slots after that slot if it is cached.
 809         */
 810        for (neigh = 0; neigh < 8; neigh++) {
 811                ent = pbase_tree_cache[my_ix];
 812                if (ent && !hashcmp(ent->sha1, sha1)) {
 813                        ent->ref++;
 814                        return ent;
 815                }
 816                else if (((available_ix < 0) && (!ent || !ent->ref)) ||
 817                         ((0 <= available_ix) &&
 818                          (!ent && pbase_tree_cache[available_ix])))
 819                        available_ix = my_ix;
 820                if (!ent)
 821                        break;
 822                my_ix = pbase_tree_cache_ix_incr(my_ix);
 823        }
 824
 825        /* Did not find one.  Either we got a bogus request or
 826         * we need to read and perhaps cache.
 827         */
 828        data = read_sha1_file(sha1, &type, &size);
 829        if (!data)
 830                return NULL;
 831        if (type != OBJ_TREE) {
 832                free(data);
 833                return NULL;
 834        }
 835
 836        /* We need to either cache or return a throwaway copy */
 837
 838        if (available_ix < 0)
 839                ent = NULL;
 840        else {
 841                ent = pbase_tree_cache[available_ix];
 842                my_ix = available_ix;
 843        }
 844
 845        if (!ent) {
 846                nent = xmalloc(sizeof(*nent));
 847                nent->temporary = (available_ix < 0);
 848        }
 849        else {
 850                /* evict and reuse */
 851                free(ent->tree_data);
 852                nent = ent;
 853        }
 854        hashcpy(nent->sha1, sha1);
 855        nent->tree_data = data;
 856        nent->tree_size = size;
 857        nent->ref = 1;
 858        if (!nent->temporary)
 859                pbase_tree_cache[my_ix] = nent;
 860        return nent;
 861}
 862
 863static void pbase_tree_put(struct pbase_tree_cache *cache)
 864{
 865        if (!cache->temporary) {
 866                cache->ref--;
 867                return;
 868        }
 869        free(cache->tree_data);
 870        free(cache);
 871}
 872
 873static int name_cmp_len(const char *name)
 874{
 875        int i;
 876        for (i = 0; name[i] && name[i] != '\n' && name[i] != '/'; i++)
 877                ;
 878        return i;
 879}
 880
 881static void add_pbase_object(struct tree_desc *tree,
 882                             const char *name,
 883                             int cmplen,
 884                             const char *fullname)
 885{
 886        struct name_entry entry;
 887        int cmp;
 888
 889        while (tree_entry(tree,&entry)) {
 890                if (S_ISGITLINK(entry.mode))
 891                        continue;
 892                cmp = tree_entry_len(entry.path, entry.sha1) != cmplen ? 1 :
 893                      memcmp(name, entry.path, cmplen);
 894                if (cmp > 0)
 895                        continue;
 896                if (cmp < 0)
 897                        return;
 898                if (name[cmplen] != '/') {
 899                        add_object_entry(entry.sha1,
 900                                         object_type(entry.mode),
 901                                         fullname, 1);
 902                        return;
 903                }
 904                if (S_ISDIR(entry.mode)) {
 905                        struct tree_desc sub;
 906                        struct pbase_tree_cache *tree;
 907                        const char *down = name+cmplen+1;
 908                        int downlen = name_cmp_len(down);
 909
 910                        tree = pbase_tree_get(entry.sha1);
 911                        if (!tree)
 912                                return;
 913                        init_tree_desc(&sub, tree->tree_data, tree->tree_size);
 914
 915                        add_pbase_object(&sub, down, downlen, fullname);
 916                        pbase_tree_put(tree);
 917                }
 918        }
 919}
 920
 921static unsigned *done_pbase_paths;
 922static int done_pbase_paths_num;
 923static int done_pbase_paths_alloc;
 924static int done_pbase_path_pos(unsigned hash)
 925{
 926        int lo = 0;
 927        int hi = done_pbase_paths_num;
 928        while (lo < hi) {
 929                int mi = (hi + lo) / 2;
 930                if (done_pbase_paths[mi] == hash)
 931                        return mi;
 932                if (done_pbase_paths[mi] < hash)
 933                        hi = mi;
 934                else
 935                        lo = mi + 1;
 936        }
 937        return -lo-1;
 938}
 939
 940static int check_pbase_path(unsigned hash)
 941{
 942        int pos = (!done_pbase_paths) ? -1 : done_pbase_path_pos(hash);
 943        if (0 <= pos)
 944                return 1;
 945        pos = -pos - 1;
 946        if (done_pbase_paths_alloc <= done_pbase_paths_num) {
 947                done_pbase_paths_alloc = alloc_nr(done_pbase_paths_alloc);
 948                done_pbase_paths = xrealloc(done_pbase_paths,
 949                                            done_pbase_paths_alloc *
 950                                            sizeof(unsigned));
 951        }
 952        done_pbase_paths_num++;
 953        if (pos < done_pbase_paths_num)
 954                memmove(done_pbase_paths + pos + 1,
 955                        done_pbase_paths + pos,
 956                        (done_pbase_paths_num - pos - 1) * sizeof(unsigned));
 957        done_pbase_paths[pos] = hash;
 958        return 0;
 959}
 960
 961static void add_preferred_base_object(const char *name)
 962{
 963        struct pbase_tree *it;
 964        int cmplen;
 965        unsigned hash = name_hash(name);
 966
 967        if (!num_preferred_base || check_pbase_path(hash))
 968                return;
 969
 970        cmplen = name_cmp_len(name);
 971        for (it = pbase_tree; it; it = it->next) {
 972                if (cmplen == 0) {
 973                        add_object_entry(it->pcache.sha1, OBJ_TREE, NULL, 1);
 974                }
 975                else {
 976                        struct tree_desc tree;
 977                        init_tree_desc(&tree, it->pcache.tree_data, it->pcache.tree_size);
 978                        add_pbase_object(&tree, name, cmplen, name);
 979                }
 980        }
 981}
 982
 983static void add_preferred_base(unsigned char *sha1)
 984{
 985        struct pbase_tree *it;
 986        void *data;
 987        unsigned long size;
 988        unsigned char tree_sha1[20];
 989
 990        if (window <= num_preferred_base++)
 991                return;
 992
 993        data = read_object_with_reference(sha1, tree_type, &size, tree_sha1);
 994        if (!data)
 995                return;
 996
 997        for (it = pbase_tree; it; it = it->next) {
 998                if (!hashcmp(it->pcache.sha1, tree_sha1)) {
 999                        free(data);
1000                        return;
1001                }
1002        }
1003
1004        it = xcalloc(1, sizeof(*it));
1005        it->next = pbase_tree;
1006        pbase_tree = it;
1007
1008        hashcpy(it->pcache.sha1, tree_sha1);
1009        it->pcache.tree_data = data;
1010        it->pcache.tree_size = size;
1011}
1012
1013static void cleanup_preferred_base(void)
1014{
1015        struct pbase_tree *it;
1016        unsigned i;
1017
1018        it = pbase_tree;
1019        pbase_tree = NULL;
1020        while (it) {
1021                struct pbase_tree *this = it;
1022                it = this->next;
1023                free(this->pcache.tree_data);
1024                free(this);
1025        }
1026
1027        for (i = 0; i < ARRAY_SIZE(pbase_tree_cache); i++) {
1028                if (!pbase_tree_cache[i])
1029                        continue;
1030                free(pbase_tree_cache[i]->tree_data);
1031                free(pbase_tree_cache[i]);
1032                pbase_tree_cache[i] = NULL;
1033        }
1034
1035        free(done_pbase_paths);
1036        done_pbase_paths = NULL;
1037        done_pbase_paths_num = done_pbase_paths_alloc = 0;
1038}
1039
1040static void check_object(struct object_entry *entry)
1041{
1042        if (entry->in_pack) {
1043                struct packed_git *p = entry->in_pack;
1044                struct pack_window *w_curs = NULL;
1045                const unsigned char *base_ref = NULL;
1046                struct object_entry *base_entry;
1047                unsigned long used, used_0;
1048                unsigned int avail;
1049                off_t ofs;
1050                unsigned char *buf, c;
1051
1052                buf = use_pack(p, &w_curs, entry->in_pack_offset, &avail);
1053
1054                /*
1055                 * We want in_pack_type even if we do not reuse delta
1056                 * since non-delta representations could still be reused.
1057                 */
1058                used = unpack_object_header_buffer(buf, avail,
1059                                                   &entry->in_pack_type,
1060                                                   &entry->size);
1061                if (used == 0)
1062                        goto give_up;
1063
1064                /*
1065                 * Determine if this is a delta and if so whether we can
1066                 * reuse it or not.  Otherwise let's find out as cheaply as
1067                 * possible what the actual type and size for this object is.
1068                 */
1069                switch (entry->in_pack_type) {
1070                default:
1071                        /* Not a delta hence we've already got all we need. */
1072                        entry->type = entry->in_pack_type;
1073                        entry->in_pack_header_size = used;
1074                        if (entry->type < OBJ_COMMIT || entry->type > OBJ_BLOB)
1075                                goto give_up;
1076                        unuse_pack(&w_curs);
1077                        return;
1078                case OBJ_REF_DELTA:
1079                        if (reuse_delta && !entry->preferred_base)
1080                                base_ref = use_pack(p, &w_curs,
1081                                                entry->in_pack_offset + used, NULL);
1082                        entry->in_pack_header_size = used + 20;
1083                        break;
1084                case OBJ_OFS_DELTA:
1085                        buf = use_pack(p, &w_curs,
1086                                       entry->in_pack_offset + used, NULL);
1087                        used_0 = 0;
1088                        c = buf[used_0++];
1089                        ofs = c & 127;
1090                        while (c & 128) {
1091                                ofs += 1;
1092                                if (!ofs || MSB(ofs, 7)) {
1093                                        error("delta base offset overflow in pack for %s",
1094                                              sha1_to_hex(entry->idx.sha1));
1095                                        goto give_up;
1096                                }
1097                                c = buf[used_0++];
1098                                ofs = (ofs << 7) + (c & 127);
1099                        }
1100                        ofs = entry->in_pack_offset - ofs;
1101                        if (ofs <= 0 || ofs >= entry->in_pack_offset) {
1102                                error("delta base offset out of bound for %s",
1103                                      sha1_to_hex(entry->idx.sha1));
1104                                goto give_up;
1105                        }
1106                        if (reuse_delta && !entry->preferred_base) {
1107                                struct revindex_entry *revidx;
1108                                revidx = find_pack_revindex(p, ofs);
1109                                if (!revidx)
1110                                        goto give_up;
1111                                base_ref = nth_packed_object_sha1(p, revidx->nr);
1112                        }
1113                        entry->in_pack_header_size = used + used_0;
1114                        break;
1115                }
1116
1117                if (base_ref && (base_entry = locate_object_entry(base_ref))) {
1118                        /*
1119                         * If base_ref was set above that means we wish to
1120                         * reuse delta data, and we even found that base
1121                         * in the list of objects we want to pack. Goodie!
1122                         *
1123                         * Depth value does not matter - find_deltas() will
1124                         * never consider reused delta as the base object to
1125                         * deltify other objects against, in order to avoid
1126                         * circular deltas.
1127                         */
1128                        entry->type = entry->in_pack_type;
1129                        entry->delta = base_entry;
1130                        entry->delta_size = entry->size;
1131                        entry->delta_sibling = base_entry->delta_child;
1132                        base_entry->delta_child = entry;
1133                        unuse_pack(&w_curs);
1134                        return;
1135                }
1136
1137                if (entry->type) {
1138                        /*
1139                         * This must be a delta and we already know what the
1140                         * final object type is.  Let's extract the actual
1141                         * object size from the delta header.
1142                         */
1143                        entry->size = get_size_from_delta(p, &w_curs,
1144                                        entry->in_pack_offset + entry->in_pack_header_size);
1145                        if (entry->size == 0)
1146                                goto give_up;
1147                        unuse_pack(&w_curs);
1148                        return;
1149                }
1150
1151                /*
1152                 * No choice but to fall back to the recursive delta walk
1153                 * with sha1_object_info() to find about the object type
1154                 * at this point...
1155                 */
1156                give_up:
1157                unuse_pack(&w_curs);
1158        }
1159
1160        entry->type = sha1_object_info(entry->idx.sha1, &entry->size);
1161        /*
1162         * The error condition is checked in prepare_pack().  This is
1163         * to permit a missing preferred base object to be ignored
1164         * as a preferred base.  Doing so can result in a larger
1165         * pack file, but the transfer will still take place.
1166         */
1167}
1168
1169static int pack_offset_sort(const void *_a, const void *_b)
1170{
1171        const struct object_entry *a = *(struct object_entry **)_a;
1172        const struct object_entry *b = *(struct object_entry **)_b;
1173
1174        /* avoid filesystem trashing with loose objects */
1175        if (!a->in_pack && !b->in_pack)
1176                return hashcmp(a->idx.sha1, b->idx.sha1);
1177
1178        if (a->in_pack < b->in_pack)
1179                return -1;
1180        if (a->in_pack > b->in_pack)
1181                return 1;
1182        return a->in_pack_offset < b->in_pack_offset ? -1 :
1183                        (a->in_pack_offset > b->in_pack_offset);
1184}
1185
1186static void get_object_details(void)
1187{
1188        uint32_t i;
1189        struct object_entry **sorted_by_offset;
1190
1191        sorted_by_offset = xcalloc(nr_objects, sizeof(struct object_entry *));
1192        for (i = 0; i < nr_objects; i++)
1193                sorted_by_offset[i] = objects + i;
1194        qsort(sorted_by_offset, nr_objects, sizeof(*sorted_by_offset), pack_offset_sort);
1195
1196        for (i = 0; i < nr_objects; i++)
1197                check_object(sorted_by_offset[i]);
1198
1199        free(sorted_by_offset);
1200}
1201
1202/*
1203 * We search for deltas in a list sorted by type, by filename hash, and then
1204 * by size, so that we see progressively smaller and smaller files.
1205 * That's because we prefer deltas to be from the bigger file
1206 * to the smaller -- deletes are potentially cheaper, but perhaps
1207 * more importantly, the bigger file is likely the more recent
1208 * one.  The deepest deltas are therefore the oldest objects which are
1209 * less susceptible to be accessed often.
1210 */
1211static int type_size_sort(const void *_a, const void *_b)
1212{
1213        const struct object_entry *a = *(struct object_entry **)_a;
1214        const struct object_entry *b = *(struct object_entry **)_b;
1215
1216        if (a->type > b->type)
1217                return -1;
1218        if (a->type < b->type)
1219                return 1;
1220        if (a->hash > b->hash)
1221                return -1;
1222        if (a->hash < b->hash)
1223                return 1;
1224        if (a->preferred_base > b->preferred_base)
1225                return -1;
1226        if (a->preferred_base < b->preferred_base)
1227                return 1;
1228        if (a->size > b->size)
1229                return -1;
1230        if (a->size < b->size)
1231                return 1;
1232        return a < b ? -1 : (a > b);  /* newest first */
1233}
1234
1235struct unpacked {
1236        struct object_entry *entry;
1237        void *data;
1238        struct delta_index *index;
1239        unsigned depth;
1240};
1241
1242static int delta_cacheable(unsigned long src_size, unsigned long trg_size,
1243                           unsigned long delta_size)
1244{
1245        if (max_delta_cache_size && delta_cache_size + delta_size > max_delta_cache_size)
1246                return 0;
1247
1248        if (delta_size < cache_max_small_delta_size)
1249                return 1;
1250
1251        /* cache delta, if objects are large enough compared to delta size */
1252        if ((src_size >> 20) + (trg_size >> 21) > (delta_size >> 10))
1253                return 1;
1254
1255        return 0;
1256}
1257
1258#ifdef THREADED_DELTA_SEARCH
1259
1260static pthread_mutex_t read_mutex;
1261#define read_lock()             pthread_mutex_lock(&read_mutex)
1262#define read_unlock()           pthread_mutex_unlock(&read_mutex)
1263
1264static pthread_mutex_t cache_mutex;
1265#define cache_lock()            pthread_mutex_lock(&cache_mutex)
1266#define cache_unlock()          pthread_mutex_unlock(&cache_mutex)
1267
1268static pthread_mutex_t progress_mutex;
1269#define progress_lock()         pthread_mutex_lock(&progress_mutex)
1270#define progress_unlock()       pthread_mutex_unlock(&progress_mutex)
1271
1272#else
1273
1274#define read_lock()             (void)0
1275#define read_unlock()           (void)0
1276#define cache_lock()            (void)0
1277#define cache_unlock()          (void)0
1278#define progress_lock()         (void)0
1279#define progress_unlock()       (void)0
1280
1281#endif
1282
1283static int try_delta(struct unpacked *trg, struct unpacked *src,
1284                     unsigned max_depth, unsigned long *mem_usage)
1285{
1286        struct object_entry *trg_entry = trg->entry;
1287        struct object_entry *src_entry = src->entry;
1288        unsigned long trg_size, src_size, delta_size, sizediff, max_size, sz;
1289        unsigned ref_depth;
1290        enum object_type type;
1291        void *delta_buf;
1292
1293        /* Don't bother doing diffs between different types */
1294        if (trg_entry->type != src_entry->type)
1295                return -1;
1296
1297        /*
1298         * We do not bother to try a delta that we discarded
1299         * on an earlier try, but only when reusing delta data.
1300         */
1301        if (reuse_delta && trg_entry->in_pack &&
1302            trg_entry->in_pack == src_entry->in_pack &&
1303            trg_entry->in_pack_type != OBJ_REF_DELTA &&
1304            trg_entry->in_pack_type != OBJ_OFS_DELTA)
1305                return 0;
1306
1307        /* Let's not bust the allowed depth. */
1308        if (src->depth >= max_depth)
1309                return 0;
1310
1311        /* Now some size filtering heuristics. */
1312        trg_size = trg_entry->size;
1313        if (!trg_entry->delta) {
1314                max_size = trg_size/2 - 20;
1315                ref_depth = 1;
1316        } else {
1317                max_size = trg_entry->delta_size;
1318                ref_depth = trg->depth;
1319        }
1320        max_size = (uint64_t)max_size * (max_depth - src->depth) /
1321                                                (max_depth - ref_depth + 1);
1322        if (max_size == 0)
1323                return 0;
1324        src_size = src_entry->size;
1325        sizediff = src_size < trg_size ? trg_size - src_size : 0;
1326        if (sizediff >= max_size)
1327                return 0;
1328        if (trg_size < src_size / 32)
1329                return 0;
1330
1331        /* Load data if not already done */
1332        if (!trg->data) {
1333                read_lock();
1334                trg->data = read_sha1_file(trg_entry->idx.sha1, &type, &sz);
1335                read_unlock();
1336                if (!trg->data)
1337                        die("object %s cannot be read",
1338                            sha1_to_hex(trg_entry->idx.sha1));
1339                if (sz != trg_size)
1340                        die("object %s inconsistent object length (%lu vs %lu)",
1341                            sha1_to_hex(trg_entry->idx.sha1), sz, trg_size);
1342                *mem_usage += sz;
1343        }
1344        if (!src->data) {
1345                read_lock();
1346                src->data = read_sha1_file(src_entry->idx.sha1, &type, &sz);
1347                read_unlock();
1348                if (!src->data)
1349                        die("object %s cannot be read",
1350                            sha1_to_hex(src_entry->idx.sha1));
1351                if (sz != src_size)
1352                        die("object %s inconsistent object length (%lu vs %lu)",
1353                            sha1_to_hex(src_entry->idx.sha1), sz, src_size);
1354                *mem_usage += sz;
1355        }
1356        if (!src->index) {
1357                src->index = create_delta_index(src->data, src_size);
1358                if (!src->index) {
1359                        static int warned = 0;
1360                        if (!warned++)
1361                                warning("suboptimal pack - out of memory");
1362                        return 0;
1363                }
1364                *mem_usage += sizeof_delta_index(src->index);
1365        }
1366
1367        delta_buf = create_delta(src->index, trg->data, trg_size, &delta_size, max_size);
1368        if (!delta_buf)
1369                return 0;
1370
1371        if (trg_entry->delta) {
1372                /* Prefer only shallower same-sized deltas. */
1373                if (delta_size == trg_entry->delta_size &&
1374                    src->depth + 1 >= trg->depth) {
1375                        free(delta_buf);
1376                        return 0;
1377                }
1378        }
1379
1380        /*
1381         * Handle memory allocation outside of the cache
1382         * accounting lock.  Compiler will optimize the strangeness
1383         * away when THREADED_DELTA_SEARCH is not defined.
1384         */
1385        free(trg_entry->delta_data);
1386        cache_lock();
1387        if (trg_entry->delta_data) {
1388                delta_cache_size -= trg_entry->delta_size;
1389                trg_entry->delta_data = NULL;
1390        }
1391        if (delta_cacheable(src_size, trg_size, delta_size)) {
1392                delta_cache_size += delta_size;
1393                cache_unlock();
1394                trg_entry->delta_data = xrealloc(delta_buf, delta_size);
1395        } else {
1396                cache_unlock();
1397                free(delta_buf);
1398        }
1399
1400        trg_entry->delta = src_entry;
1401        trg_entry->delta_size = delta_size;
1402        trg->depth = src->depth + 1;
1403
1404        return 1;
1405}
1406
1407static unsigned int check_delta_limit(struct object_entry *me, unsigned int n)
1408{
1409        struct object_entry *child = me->delta_child;
1410        unsigned int m = n;
1411        while (child) {
1412                unsigned int c = check_delta_limit(child, n + 1);
1413                if (m < c)
1414                        m = c;
1415                child = child->delta_sibling;
1416        }
1417        return m;
1418}
1419
1420static unsigned long free_unpacked(struct unpacked *n)
1421{
1422        unsigned long freed_mem = sizeof_delta_index(n->index);
1423        free_delta_index(n->index);
1424        n->index = NULL;
1425        if (n->data) {
1426                freed_mem += n->entry->size;
1427                free(n->data);
1428                n->data = NULL;
1429        }
1430        n->entry = NULL;
1431        n->depth = 0;
1432        return freed_mem;
1433}
1434
1435static void find_deltas(struct object_entry **list, unsigned *list_size,
1436                        int window, int depth, unsigned *processed)
1437{
1438        uint32_t i, idx = 0, count = 0;
1439        struct unpacked *array;
1440        unsigned long mem_usage = 0;
1441
1442        array = xcalloc(window, sizeof(struct unpacked));
1443
1444        for (;;) {
1445                struct object_entry *entry;
1446                struct unpacked *n = array + idx;
1447                int j, max_depth, best_base = -1;
1448
1449                progress_lock();
1450                if (!*list_size) {
1451                        progress_unlock();
1452                        break;
1453                }
1454                entry = *list++;
1455                (*list_size)--;
1456                if (!entry->preferred_base) {
1457                        (*processed)++;
1458                        display_progress(progress_state, *processed);
1459                }
1460                progress_unlock();
1461
1462                mem_usage -= free_unpacked(n);
1463                n->entry = entry;
1464
1465                while (window_memory_limit &&
1466                       mem_usage > window_memory_limit &&
1467                       count > 1) {
1468                        uint32_t tail = (idx + window - count) % window;
1469                        mem_usage -= free_unpacked(array + tail);
1470                        count--;
1471                }
1472
1473                /* We do not compute delta to *create* objects we are not
1474                 * going to pack.
1475                 */
1476                if (entry->preferred_base)
1477                        goto next;
1478
1479                /*
1480                 * If the current object is at pack edge, take the depth the
1481                 * objects that depend on the current object into account
1482                 * otherwise they would become too deep.
1483                 */
1484                max_depth = depth;
1485                if (entry->delta_child) {
1486                        max_depth -= check_delta_limit(entry, 0);
1487                        if (max_depth <= 0)
1488                                goto next;
1489                }
1490
1491                j = window;
1492                while (--j > 0) {
1493                        int ret;
1494                        uint32_t other_idx = idx + j;
1495                        struct unpacked *m;
1496                        if (other_idx >= window)
1497                                other_idx -= window;
1498                        m = array + other_idx;
1499                        if (!m->entry)
1500                                break;
1501                        ret = try_delta(n, m, max_depth, &mem_usage);
1502                        if (ret < 0)
1503                                break;
1504                        else if (ret > 0)
1505                                best_base = other_idx;
1506                }
1507
1508                /*
1509                 * If we decided to cache the delta data, then it is best
1510                 * to compress it right away.  First because we have to do
1511                 * it anyway, and doing it here while we're threaded will
1512                 * save a lot of time in the non threaded write phase,
1513                 * as well as allow for caching more deltas within
1514                 * the same cache size limit.
1515                 * ...
1516                 * But only if not writing to stdout, since in that case
1517                 * the network is most likely throttling writes anyway,
1518                 * and therefore it is best to go to the write phase ASAP
1519                 * instead, as we can afford spending more time compressing
1520                 * between writes at that moment.
1521                 */
1522                if (entry->delta_data && !pack_to_stdout) {
1523                        entry->z_delta_size = do_compress(&entry->delta_data,
1524                                                          entry->delta_size);
1525                        cache_lock();
1526                        delta_cache_size -= entry->delta_size;
1527                        delta_cache_size += entry->z_delta_size;
1528                        cache_unlock();
1529                }
1530
1531                /* if we made n a delta, and if n is already at max
1532                 * depth, leaving it in the window is pointless.  we
1533                 * should evict it first.
1534                 */
1535                if (entry->delta && max_depth <= n->depth)
1536                        continue;
1537
1538                /*
1539                 * Move the best delta base up in the window, after the
1540                 * currently deltified object, to keep it longer.  It will
1541                 * be the first base object to be attempted next.
1542                 */
1543                if (entry->delta) {
1544                        struct unpacked swap = array[best_base];
1545                        int dist = (window + idx - best_base) % window;
1546                        int dst = best_base;
1547                        while (dist--) {
1548                                int src = (dst + 1) % window;
1549                                array[dst] = array[src];
1550                                dst = src;
1551                        }
1552                        array[dst] = swap;
1553                }
1554
1555                next:
1556                idx++;
1557                if (count + 1 < window)
1558                        count++;
1559                if (idx >= window)
1560                        idx = 0;
1561        }
1562
1563        for (i = 0; i < window; ++i) {
1564                free_delta_index(array[i].index);
1565                free(array[i].data);
1566        }
1567        free(array);
1568}
1569
1570#ifdef THREADED_DELTA_SEARCH
1571
1572/*
1573 * The main thread waits on the condition that (at least) one of the workers
1574 * has stopped working (which is indicated in the .working member of
1575 * struct thread_params).
1576 * When a work thread has completed its work, it sets .working to 0 and
1577 * signals the main thread and waits on the condition that .data_ready
1578 * becomes 1.
1579 */
1580
1581struct thread_params {
1582        pthread_t thread;
1583        struct object_entry **list;
1584        unsigned list_size;
1585        unsigned remaining;
1586        int window;
1587        int depth;
1588        int working;
1589        int data_ready;
1590        pthread_mutex_t mutex;
1591        pthread_cond_t cond;
1592        unsigned *processed;
1593};
1594
1595static pthread_cond_t progress_cond;
1596
1597/*
1598 * Mutex and conditional variable can't be statically-initialized on Windows.
1599 */
1600static void init_threaded_search(void)
1601{
1602        pthread_mutex_init(&read_mutex, NULL);
1603        pthread_mutex_init(&cache_mutex, NULL);
1604        pthread_mutex_init(&progress_mutex, NULL);
1605        pthread_cond_init(&progress_cond, NULL);
1606}
1607
1608static void cleanup_threaded_search(void)
1609{
1610        pthread_cond_destroy(&progress_cond);
1611        pthread_mutex_destroy(&read_mutex);
1612        pthread_mutex_destroy(&cache_mutex);
1613        pthread_mutex_destroy(&progress_mutex);
1614}
1615
1616static void *threaded_find_deltas(void *arg)
1617{
1618        struct thread_params *me = arg;
1619
1620        while (me->remaining) {
1621                find_deltas(me->list, &me->remaining,
1622                            me->window, me->depth, me->processed);
1623
1624                progress_lock();
1625                me->working = 0;
1626                pthread_cond_signal(&progress_cond);
1627                progress_unlock();
1628
1629                /*
1630                 * We must not set ->data_ready before we wait on the
1631                 * condition because the main thread may have set it to 1
1632                 * before we get here. In order to be sure that new
1633                 * work is available if we see 1 in ->data_ready, it
1634                 * was initialized to 0 before this thread was spawned
1635                 * and we reset it to 0 right away.
1636                 */
1637                pthread_mutex_lock(&me->mutex);
1638                while (!me->data_ready)
1639                        pthread_cond_wait(&me->cond, &me->mutex);
1640                me->data_ready = 0;
1641                pthread_mutex_unlock(&me->mutex);
1642        }
1643        /* leave ->working 1 so that this doesn't get more work assigned */
1644        return NULL;
1645}
1646
1647static void ll_find_deltas(struct object_entry **list, unsigned list_size,
1648                           int window, int depth, unsigned *processed)
1649{
1650        struct thread_params *p;
1651        int i, ret, active_threads = 0;
1652
1653        init_threaded_search();
1654
1655        if (!delta_search_threads)      /* --threads=0 means autodetect */
1656                delta_search_threads = online_cpus();
1657        if (delta_search_threads <= 1) {
1658                find_deltas(list, &list_size, window, depth, processed);
1659                cleanup_threaded_search();
1660                return;
1661        }
1662        if (progress > pack_to_stdout)
1663                fprintf(stderr, "Delta compression using up to %d threads.\n",
1664                                delta_search_threads);
1665        p = xcalloc(delta_search_threads, sizeof(*p));
1666
1667        /* Partition the work amongst work threads. */
1668        for (i = 0; i < delta_search_threads; i++) {
1669                unsigned sub_size = list_size / (delta_search_threads - i);
1670
1671                /* don't use too small segments or no deltas will be found */
1672                if (sub_size < 2*window && i+1 < delta_search_threads)
1673                        sub_size = 0;
1674
1675                p[i].window = window;
1676                p[i].depth = depth;
1677                p[i].processed = processed;
1678                p[i].working = 1;
1679                p[i].data_ready = 0;
1680
1681                /* try to split chunks on "path" boundaries */
1682                while (sub_size && sub_size < list_size &&
1683                       list[sub_size]->hash &&
1684                       list[sub_size]->hash == list[sub_size-1]->hash)
1685                        sub_size++;
1686
1687                p[i].list = list;
1688                p[i].list_size = sub_size;
1689                p[i].remaining = sub_size;
1690
1691                list += sub_size;
1692                list_size -= sub_size;
1693        }
1694
1695        /* Start work threads. */
1696        for (i = 0; i < delta_search_threads; i++) {
1697                if (!p[i].list_size)
1698                        continue;
1699                pthread_mutex_init(&p[i].mutex, NULL);
1700                pthread_cond_init(&p[i].cond, NULL);
1701                ret = pthread_create(&p[i].thread, NULL,
1702                                     threaded_find_deltas, &p[i]);
1703                if (ret)
1704                        die("unable to create thread: %s", strerror(ret));
1705                active_threads++;
1706        }
1707
1708        /*
1709         * Now let's wait for work completion.  Each time a thread is done
1710         * with its work, we steal half of the remaining work from the
1711         * thread with the largest number of unprocessed objects and give
1712         * it to that newly idle thread.  This ensure good load balancing
1713         * until the remaining object list segments are simply too short
1714         * to be worth splitting anymore.
1715         */
1716        while (active_threads) {
1717                struct thread_params *target = NULL;
1718                struct thread_params *victim = NULL;
1719                unsigned sub_size = 0;
1720
1721                progress_lock();
1722                for (;;) {
1723                        for (i = 0; !target && i < delta_search_threads; i++)
1724                                if (!p[i].working)
1725                                        target = &p[i];
1726                        if (target)
1727                                break;
1728                        pthread_cond_wait(&progress_cond, &progress_mutex);
1729                }
1730
1731                for (i = 0; i < delta_search_threads; i++)
1732                        if (p[i].remaining > 2*window &&
1733                            (!victim || victim->remaining < p[i].remaining))
1734                                victim = &p[i];
1735                if (victim) {
1736                        sub_size = victim->remaining / 2;
1737                        list = victim->list + victim->list_size - sub_size;
1738                        while (sub_size && list[0]->hash &&
1739                               list[0]->hash == list[-1]->hash) {
1740                                list++;
1741                                sub_size--;
1742                        }
1743                        if (!sub_size) {
1744                                /*
1745                                 * It is possible for some "paths" to have
1746                                 * so many objects that no hash boundary
1747                                 * might be found.  Let's just steal the
1748                                 * exact half in that case.
1749                                 */
1750                                sub_size = victim->remaining / 2;
1751                                list -= sub_size;
1752                        }
1753                        target->list = list;
1754                        victim->list_size -= sub_size;
1755                        victim->remaining -= sub_size;
1756                }
1757                target->list_size = sub_size;
1758                target->remaining = sub_size;
1759                target->working = 1;
1760                progress_unlock();
1761
1762                pthread_mutex_lock(&target->mutex);
1763                target->data_ready = 1;
1764                pthread_cond_signal(&target->cond);
1765                pthread_mutex_unlock(&target->mutex);
1766
1767                if (!sub_size) {
1768                        pthread_join(target->thread, NULL);
1769                        pthread_cond_destroy(&target->cond);
1770                        pthread_mutex_destroy(&target->mutex);
1771                        active_threads--;
1772                }
1773        }
1774        cleanup_threaded_search();
1775        free(p);
1776}
1777
1778#else
1779#define ll_find_deltas(l, s, w, d, p)   find_deltas(l, &s, w, d, p)
1780#endif
1781
1782static int add_ref_tag(const char *path, const unsigned char *sha1, int flag, void *cb_data)
1783{
1784        unsigned char peeled[20];
1785
1786        if (!prefixcmp(path, "refs/tags/") && /* is a tag? */
1787            !peel_ref(path, peeled)        && /* peelable? */
1788            !is_null_sha1(peeled)          && /* annotated tag? */
1789            locate_object_entry(peeled))      /* object packed? */
1790                add_object_entry(sha1, OBJ_TAG, NULL, 0);
1791        return 0;
1792}
1793
1794static void prepare_pack(int window, int depth)
1795{
1796        struct object_entry **delta_list;
1797        uint32_t i, nr_deltas;
1798        unsigned n;
1799
1800        get_object_details();
1801
1802        /*
1803         * If we're locally repacking then we need to be doubly careful
1804         * from now on in order to make sure no stealth corruption gets
1805         * propagated to the new pack.  Clients receiving streamed packs
1806         * should validate everything they get anyway so no need to incur
1807         * the additional cost here in that case.
1808         */
1809        if (!pack_to_stdout)
1810                do_check_packed_object_crc = 1;
1811
1812        if (!nr_objects || !window || !depth)
1813                return;
1814
1815        delta_list = xmalloc(nr_objects * sizeof(*delta_list));
1816        nr_deltas = n = 0;
1817
1818        for (i = 0; i < nr_objects; i++) {
1819                struct object_entry *entry = objects + i;
1820
1821                if (entry->delta)
1822                        /* This happens if we decided to reuse existing
1823                         * delta from a pack.  "reuse_delta &&" is implied.
1824                         */
1825                        continue;
1826
1827                if (entry->size < 50)
1828                        continue;
1829
1830                if (entry->no_try_delta)
1831                        continue;
1832
1833                if (!entry->preferred_base) {
1834                        nr_deltas++;
1835                        if (entry->type < 0)
1836                                die("unable to get type of object %s",
1837                                    sha1_to_hex(entry->idx.sha1));
1838                } else {
1839                        if (entry->type < 0) {
1840                                /*
1841                                 * This object is not found, but we
1842                                 * don't have to include it anyway.
1843                                 */
1844                                continue;
1845                        }
1846                }
1847
1848                delta_list[n++] = entry;
1849        }
1850
1851        if (nr_deltas && n > 1) {
1852                unsigned nr_done = 0;
1853                if (progress)
1854                        progress_state = start_progress("Compressing objects",
1855                                                        nr_deltas);
1856                qsort(delta_list, n, sizeof(*delta_list), type_size_sort);
1857                ll_find_deltas(delta_list, n, window+1, depth, &nr_done);
1858                stop_progress(&progress_state);
1859                if (nr_done != nr_deltas)
1860                        die("inconsistency with delta count");
1861        }
1862        free(delta_list);
1863}
1864
1865static int git_pack_config(const char *k, const char *v, void *cb)
1866{
1867        if (!strcmp(k, "pack.window")) {
1868                window = git_config_int(k, v);
1869                return 0;
1870        }
1871        if (!strcmp(k, "pack.windowmemory")) {
1872                window_memory_limit = git_config_ulong(k, v);
1873                return 0;
1874        }
1875        if (!strcmp(k, "pack.depth")) {
1876                depth = git_config_int(k, v);
1877                return 0;
1878        }
1879        if (!strcmp(k, "pack.compression")) {
1880                int level = git_config_int(k, v);
1881                if (level == -1)
1882                        level = Z_DEFAULT_COMPRESSION;
1883                else if (level < 0 || level > Z_BEST_COMPRESSION)
1884                        die("bad pack compression level %d", level);
1885                pack_compression_level = level;
1886                pack_compression_seen = 1;
1887                return 0;
1888        }
1889        if (!strcmp(k, "pack.deltacachesize")) {
1890                max_delta_cache_size = git_config_int(k, v);
1891                return 0;
1892        }
1893        if (!strcmp(k, "pack.deltacachelimit")) {
1894                cache_max_small_delta_size = git_config_int(k, v);
1895                return 0;
1896        }
1897        if (!strcmp(k, "pack.threads")) {
1898                delta_search_threads = git_config_int(k, v);
1899                if (delta_search_threads < 0)
1900                        die("invalid number of threads specified (%d)",
1901                            delta_search_threads);
1902#ifndef THREADED_DELTA_SEARCH
1903                if (delta_search_threads != 1)
1904                        warning("no threads support, ignoring %s", k);
1905#endif
1906                return 0;
1907        }
1908        if (!strcmp(k, "pack.indexversion")) {
1909                pack_idx_default_version = git_config_int(k, v);
1910                if (pack_idx_default_version > 2)
1911                        die("bad pack.indexversion=%"PRIu32,
1912                                pack_idx_default_version);
1913                return 0;
1914        }
1915        if (!strcmp(k, "pack.packsizelimit")) {
1916                pack_size_limit_cfg = git_config_ulong(k, v);
1917                return 0;
1918        }
1919        return git_default_config(k, v, cb);
1920}
1921
1922static void read_object_list_from_stdin(void)
1923{
1924        char line[40 + 1 + PATH_MAX + 2];
1925        unsigned char sha1[20];
1926
1927        for (;;) {
1928                if (!fgets(line, sizeof(line), stdin)) {
1929                        if (feof(stdin))
1930                                break;
1931                        if (!ferror(stdin))
1932                                die("fgets returned NULL, not EOF, not error!");
1933                        if (errno != EINTR)
1934                                die_errno("fgets");
1935                        clearerr(stdin);
1936                        continue;
1937                }
1938                if (line[0] == '-') {
1939                        if (get_sha1_hex(line+1, sha1))
1940                                die("expected edge sha1, got garbage:\n %s",
1941                                    line);
1942                        add_preferred_base(sha1);
1943                        continue;
1944                }
1945                if (get_sha1_hex(line, sha1))
1946                        die("expected sha1, got garbage:\n %s", line);
1947
1948                add_preferred_base_object(line+41);
1949                add_object_entry(sha1, 0, line+41, 0);
1950        }
1951}
1952
1953#define OBJECT_ADDED (1u<<20)
1954
1955static void show_commit(struct commit *commit, void *data)
1956{
1957        add_object_entry(commit->object.sha1, OBJ_COMMIT, NULL, 0);
1958        commit->object.flags |= OBJECT_ADDED;
1959}
1960
1961static void show_object(struct object *obj, const struct name_path *path, const char *last)
1962{
1963        char *name = path_name(path, last);
1964
1965        add_preferred_base_object(name);
1966        add_object_entry(obj->sha1, obj->type, name, 0);
1967        obj->flags |= OBJECT_ADDED;
1968
1969        /*
1970         * We will have generated the hash from the name,
1971         * but not saved a pointer to it - we can free it
1972         */
1973        free((char *)name);
1974}
1975
1976static void show_edge(struct commit *commit)
1977{
1978        add_preferred_base(commit->object.sha1);
1979}
1980
1981struct in_pack_object {
1982        off_t offset;
1983        struct object *object;
1984};
1985
1986struct in_pack {
1987        int alloc;
1988        int nr;
1989        struct in_pack_object *array;
1990};
1991
1992static void mark_in_pack_object(struct object *object, struct packed_git *p, struct in_pack *in_pack)
1993{
1994        in_pack->array[in_pack->nr].offset = find_pack_entry_one(object->sha1, p);
1995        in_pack->array[in_pack->nr].object = object;
1996        in_pack->nr++;
1997}
1998
1999/*
2000 * Compare the objects in the offset order, in order to emulate the
2001 * "git rev-list --objects" output that produced the pack originally.
2002 */
2003static int ofscmp(const void *a_, const void *b_)
2004{
2005        struct in_pack_object *a = (struct in_pack_object *)a_;
2006        struct in_pack_object *b = (struct in_pack_object *)b_;
2007
2008        if (a->offset < b->offset)
2009                return -1;
2010        else if (a->offset > b->offset)
2011                return 1;
2012        else
2013                return hashcmp(a->object->sha1, b->object->sha1);
2014}
2015
2016static void add_objects_in_unpacked_packs(struct rev_info *revs)
2017{
2018        struct packed_git *p;
2019        struct in_pack in_pack;
2020        uint32_t i;
2021
2022        memset(&in_pack, 0, sizeof(in_pack));
2023
2024        for (p = packed_git; p; p = p->next) {
2025                const unsigned char *sha1;
2026                struct object *o;
2027
2028                if (!p->pack_local || p->pack_keep)
2029                        continue;
2030                if (open_pack_index(p))
2031                        die("cannot open pack index");
2032
2033                ALLOC_GROW(in_pack.array,
2034                           in_pack.nr + p->num_objects,
2035                           in_pack.alloc);
2036
2037                for (i = 0; i < p->num_objects; i++) {
2038                        sha1 = nth_packed_object_sha1(p, i);
2039                        o = lookup_unknown_object(sha1);
2040                        if (!(o->flags & OBJECT_ADDED))
2041                                mark_in_pack_object(o, p, &in_pack);
2042                        o->flags |= OBJECT_ADDED;
2043                }
2044        }
2045
2046        if (in_pack.nr) {
2047                qsort(in_pack.array, in_pack.nr, sizeof(in_pack.array[0]),
2048                      ofscmp);
2049                for (i = 0; i < in_pack.nr; i++) {
2050                        struct object *o = in_pack.array[i].object;
2051                        add_object_entry(o->sha1, o->type, "", 0);
2052                }
2053        }
2054        free(in_pack.array);
2055}
2056
2057static int has_sha1_pack_kept_or_nonlocal(const unsigned char *sha1)
2058{
2059        static struct packed_git *last_found = (void *)1;
2060        struct packed_git *p;
2061
2062        p = (last_found != (void *)1) ? last_found : packed_git;
2063
2064        while (p) {
2065                if ((!p->pack_local || p->pack_keep) &&
2066                        find_pack_entry_one(sha1, p)) {
2067                        last_found = p;
2068                        return 1;
2069                }
2070                if (p == last_found)
2071                        p = packed_git;
2072                else
2073                        p = p->next;
2074                if (p == last_found)
2075                        p = p->next;
2076        }
2077        return 0;
2078}
2079
2080static void loosen_unused_packed_objects(struct rev_info *revs)
2081{
2082        struct packed_git *p;
2083        uint32_t i;
2084        const unsigned char *sha1;
2085
2086        for (p = packed_git; p; p = p->next) {
2087                if (!p->pack_local || p->pack_keep)
2088                        continue;
2089
2090                if (open_pack_index(p))
2091                        die("cannot open pack index");
2092
2093                for (i = 0; i < p->num_objects; i++) {
2094                        sha1 = nth_packed_object_sha1(p, i);
2095                        if (!locate_object_entry(sha1) &&
2096                                !has_sha1_pack_kept_or_nonlocal(sha1))
2097                                if (force_object_loose(sha1, p->mtime))
2098                                        die("unable to force loose object");
2099                }
2100        }
2101}
2102
2103static void get_object_list(int ac, const char **av)
2104{
2105        struct rev_info revs;
2106        char line[1000];
2107        int flags = 0;
2108
2109        init_revisions(&revs, NULL);
2110        save_commit_buffer = 0;
2111        setup_revisions(ac, av, &revs, NULL);
2112
2113        while (fgets(line, sizeof(line), stdin) != NULL) {
2114                int len = strlen(line);
2115                if (len && line[len - 1] == '\n')
2116                        line[--len] = 0;
2117                if (!len)
2118                        break;
2119                if (*line == '-') {
2120                        if (!strcmp(line, "--not")) {
2121                                flags ^= UNINTERESTING;
2122                                continue;
2123                        }
2124                        die("not a rev '%s'", line);
2125                }
2126                if (handle_revision_arg(line, &revs, flags, 1))
2127                        die("bad revision '%s'", line);
2128        }
2129
2130        if (prepare_revision_walk(&revs))
2131                die("revision walk setup failed");
2132        mark_edges_uninteresting(revs.commits, &revs, show_edge);
2133        traverse_commit_list(&revs, show_commit, show_object, NULL);
2134
2135        if (keep_unreachable)
2136                add_objects_in_unpacked_packs(&revs);
2137        if (unpack_unreachable)
2138                loosen_unused_packed_objects(&revs);
2139}
2140
2141static int adjust_perm(const char *path, mode_t mode)
2142{
2143        if (chmod(path, mode))
2144                return -1;
2145        return adjust_shared_perm(path);
2146}
2147
2148int cmd_pack_objects(int argc, const char **argv, const char *prefix)
2149{
2150        int use_internal_rev_list = 0;
2151        int thin = 0;
2152        int all_progress_implied = 0;
2153        uint32_t i;
2154        const char **rp_av;
2155        int rp_ac_alloc = 64;
2156        int rp_ac;
2157
2158        read_replace_refs = 0;
2159
2160        rp_av = xcalloc(rp_ac_alloc, sizeof(*rp_av));
2161
2162        rp_av[0] = "pack-objects";
2163        rp_av[1] = "--objects"; /* --thin will make it --objects-edge */
2164        rp_ac = 2;
2165
2166        git_config(git_pack_config, NULL);
2167        if (!pack_compression_seen && core_compression_seen)
2168                pack_compression_level = core_compression_level;
2169
2170        progress = isatty(2);
2171        for (i = 1; i < argc; i++) {
2172                const char *arg = argv[i];
2173
2174                if (*arg != '-')
2175                        break;
2176
2177                if (!strcmp("--non-empty", arg)) {
2178                        non_empty = 1;
2179                        continue;
2180                }
2181                if (!strcmp("--local", arg)) {
2182                        local = 1;
2183                        continue;
2184                }
2185                if (!strcmp("--incremental", arg)) {
2186                        incremental = 1;
2187                        continue;
2188                }
2189                if (!strcmp("--honor-pack-keep", arg)) {
2190                        ignore_packed_keep = 1;
2191                        continue;
2192                }
2193                if (!prefixcmp(arg, "--compression=")) {
2194                        char *end;
2195                        int level = strtoul(arg+14, &end, 0);
2196                        if (!arg[14] || *end)
2197                                usage(pack_usage);
2198                        if (level == -1)
2199                                level = Z_DEFAULT_COMPRESSION;
2200                        else if (level < 0 || level > Z_BEST_COMPRESSION)
2201                                die("bad pack compression level %d", level);
2202                        pack_compression_level = level;
2203                        continue;
2204                }
2205                if (!prefixcmp(arg, "--max-pack-size=")) {
2206                        char *end;
2207                        pack_size_limit_cfg = 0;
2208                        pack_size_limit = strtoul(arg+16, &end, 0) * 1024 * 1024;
2209                        if (!arg[16] || *end)
2210                                usage(pack_usage);
2211                        continue;
2212                }
2213                if (!prefixcmp(arg, "--window=")) {
2214                        char *end;
2215                        window = strtoul(arg+9, &end, 0);
2216                        if (!arg[9] || *end)
2217                                usage(pack_usage);
2218                        continue;
2219                }
2220                if (!prefixcmp(arg, "--window-memory=")) {
2221                        if (!git_parse_ulong(arg+16, &window_memory_limit))
2222                                usage(pack_usage);
2223                        continue;
2224                }
2225                if (!prefixcmp(arg, "--threads=")) {
2226                        char *end;
2227                        delta_search_threads = strtoul(arg+10, &end, 0);
2228                        if (!arg[10] || *end || delta_search_threads < 0)
2229                                usage(pack_usage);
2230#ifndef THREADED_DELTA_SEARCH
2231                        if (delta_search_threads != 1)
2232                                warning("no threads support, "
2233                                        "ignoring %s", arg);
2234#endif
2235                        continue;
2236                }
2237                if (!prefixcmp(arg, "--depth=")) {
2238                        char *end;
2239                        depth = strtoul(arg+8, &end, 0);
2240                        if (!arg[8] || *end)
2241                                usage(pack_usage);
2242                        continue;
2243                }
2244                if (!strcmp("--progress", arg)) {
2245                        progress = 1;
2246                        continue;
2247                }
2248                if (!strcmp("--all-progress", arg)) {
2249                        progress = 2;
2250                        continue;
2251                }
2252                if (!strcmp("--all-progress-implied", arg)) {
2253                        all_progress_implied = 1;
2254                        continue;
2255                }
2256                if (!strcmp("-q", arg)) {
2257                        progress = 0;
2258                        continue;
2259                }
2260                if (!strcmp("--no-reuse-delta", arg)) {
2261                        reuse_delta = 0;
2262                        continue;
2263                }
2264                if (!strcmp("--no-reuse-object", arg)) {
2265                        reuse_object = reuse_delta = 0;
2266                        continue;
2267                }
2268                if (!strcmp("--delta-base-offset", arg)) {
2269                        allow_ofs_delta = 1;
2270                        continue;
2271                }
2272                if (!strcmp("--stdout", arg)) {
2273                        pack_to_stdout = 1;
2274                        continue;
2275                }
2276                if (!strcmp("--revs", arg)) {
2277                        use_internal_rev_list = 1;
2278                        continue;
2279                }
2280                if (!strcmp("--keep-unreachable", arg)) {
2281                        keep_unreachable = 1;
2282                        continue;
2283                }
2284                if (!strcmp("--unpack-unreachable", arg)) {
2285                        unpack_unreachable = 1;
2286                        continue;
2287                }
2288                if (!strcmp("--include-tag", arg)) {
2289                        include_tag = 1;
2290                        continue;
2291                }
2292                if (!strcmp("--unpacked", arg) ||
2293                    !strcmp("--reflog", arg) ||
2294                    !strcmp("--all", arg)) {
2295                        use_internal_rev_list = 1;
2296                        if (rp_ac >= rp_ac_alloc - 1) {
2297                                rp_ac_alloc = alloc_nr(rp_ac_alloc);
2298                                rp_av = xrealloc(rp_av,
2299                                                 rp_ac_alloc * sizeof(*rp_av));
2300                        }
2301                        rp_av[rp_ac++] = arg;
2302                        continue;
2303                }
2304                if (!strcmp("--thin", arg)) {
2305                        use_internal_rev_list = 1;
2306                        thin = 1;
2307                        rp_av[1] = "--objects-edge";
2308                        continue;
2309                }
2310                if (!prefixcmp(arg, "--index-version=")) {
2311                        char *c;
2312                        pack_idx_default_version = strtoul(arg + 16, &c, 10);
2313                        if (pack_idx_default_version > 2)
2314                                die("bad %s", arg);
2315                        if (*c == ',')
2316                                pack_idx_off32_limit = strtoul(c+1, &c, 0);
2317                        if (*c || pack_idx_off32_limit & 0x80000000)
2318                                die("bad %s", arg);
2319                        continue;
2320                }
2321                if (!strcmp(arg, "--keep-true-parents")) {
2322                        grafts_replace_parents = 0;
2323                        continue;
2324                }
2325                usage(pack_usage);
2326        }
2327
2328        /* Traditionally "pack-objects [options] base extra" failed;
2329         * we would however want to take refs parameter that would
2330         * have been given to upstream rev-list ourselves, which means
2331         * we somehow want to say what the base name is.  So the
2332         * syntax would be:
2333         *
2334         * pack-objects [options] base <refs...>
2335         *
2336         * in other words, we would treat the first non-option as the
2337         * base_name and send everything else to the internal revision
2338         * walker.
2339         */
2340
2341        if (!pack_to_stdout)
2342                base_name = argv[i++];
2343
2344        if (pack_to_stdout != !base_name)
2345                usage(pack_usage);
2346
2347        if (!pack_to_stdout && !pack_size_limit)
2348                pack_size_limit = pack_size_limit_cfg;
2349
2350        if (pack_to_stdout && pack_size_limit)
2351                die("--max-pack-size cannot be used to build a pack for transfer.");
2352
2353        if (!pack_to_stdout && thin)
2354                die("--thin cannot be used to build an indexable pack.");
2355
2356        if (keep_unreachable && unpack_unreachable)
2357                die("--keep-unreachable and --unpack-unreachable are incompatible.");
2358
2359        if (progress && all_progress_implied)
2360                progress = 2;
2361
2362        prepare_packed_git();
2363
2364        if (progress)
2365                progress_state = start_progress("Counting objects", 0);
2366        if (!use_internal_rev_list)
2367                read_object_list_from_stdin();
2368        else {
2369                rp_av[rp_ac] = NULL;
2370                get_object_list(rp_ac, rp_av);
2371        }
2372        cleanup_preferred_base();
2373        if (include_tag && nr_result)
2374                for_each_ref(add_ref_tag, NULL);
2375        stop_progress(&progress_state);
2376
2377        if (non_empty && !nr_result)
2378                return 0;
2379        if (nr_result)
2380                prepare_pack(window, depth);
2381        write_pack_file();
2382        if (progress)
2383                fprintf(stderr, "Total %"PRIu32" (delta %"PRIu32"),"
2384                        " reused %"PRIu32" (delta %"PRIu32")\n",
2385                        written, written_delta, reused, reused_delta);
2386        return 0;
2387}