git.oblomov.eu Git - git/blob - builtin/pack-objects.c

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