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 difference for "original" minus the offset of the first object of
 819          * this chunk in the generated packfile. */
 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(const struct object_id *oid, int exclude,
1192                              struct packed_git *p)
1193 {
1194         if (exclude)
1195                 return 1;
1196         if (incremental)
1197                 return 0;
1198
1199         /*
1200          * When asked to do --local (do not include an object that appears in a
1201          * pack we borrow from elsewhere) or --honor-pack-keep (do not include
1202          * an object that appears in a pack marked with .keep), finding a pack
1203          * that matches the criteria is sufficient for us to decide to omit it.
1204          * However, even if this pack does not satisfy the criteria, we need to
1205          * make sure no copy of this object appears in _any_ pack that makes us
1206          * to omit the object, so we need to check all the packs.
1207          *
1208          * We can however first check whether these options can possibly matter;
1209          * if they do not matter we know we want the object in generated pack.
1210          * Otherwise, we signal "-1" at the end to tell the caller that we do
1211          * not know either way, and it needs to check more packs.
1212          */
1213
1214         /*
1215          * Objects in packs borrowed from elsewhere are discarded regardless of
1216          * if they appear in other packs that weren't borrowed.
1217          */
1218         if (local && !p->pack_local)
1219                 return 0;
1220
1221         /*
1222          * Then handle .keep first, as we have a fast(er) path there.
1223          */
1224         if (ignore_packed_keep_on_disk || ignore_packed_keep_in_core) {
1225                 /*
1226                  * Set the flags for the kept-pack cache to be the ones we want
1227                  * to ignore.
1228                  *
1229                  * That is, if we are ignoring objects in on-disk keep packs,
1230                  * then we want to search through the on-disk keep and ignore
1231                  * the in-core ones.
1232                  */
1233                 unsigned flags = 0;
1234                 if (ignore_packed_keep_on_disk)
1235                         flags |= ON_DISK_KEEP_PACKS;
1236                 if (ignore_packed_keep_in_core)
1237                         flags |= IN_CORE_KEEP_PACKS;
1238
1239                 if (ignore_packed_keep_on_disk && p->pack_keep)
1240                         return 0;
1241                 if (ignore_packed_keep_in_core && p->pack_keep_in_core)
1242                         return 0;
1243                 if (has_object_kept_pack(oid, flags))
1244                         return 0;
1245         }
1246
1247         /*
1248          * At this point we know definitively that either we don't care about
1249          * keep-packs, or the object is not in one. Keep checking other
1250          * conditions...
1251          */
1252         if (!local || !have_non_local_packs)
1253                 return 1;
1254
1255         /* we don't know yet; keep looking for more packs */
1256         return -1;
1257 }
1258
1259 static int want_object_in_pack_one(struct packed_git *p,
1260                                    const struct object_id *oid,
1261                                    int exclude,
1262                                    struct packed_git **found_pack,
1263                                    off_t *found_offset)
1264 {
1265         off_t offset;
1266
1267         if (p == *found_pack)
1268                 offset = *found_offset;
1269         else
1270                 offset = find_pack_entry_one(oid->hash, p);
1271
1272         if (offset) {
1273                 if (!*found_pack) {
1274                         if (!is_pack_valid(p))
1275                                 return -1;
1276                         *found_offset = offset;
1277                         *found_pack = p;
1278                 }
1279                 return want_found_object(oid, exclude, p);
1280         }
1281         return -1;
1282 }
1283
1284 /*
1285  * Check whether we want the object in the pack (e.g., we do not want
1286  * objects found in non-local stores if the "--local" option was used).
1287  *
1288  * If the caller already knows an existing pack it wants to take the object
1289  * from, that is passed in *found_pack and *found_offset; otherwise this
1290  * function finds if there is any pack that has the object and returns the pack
1291  * and its offset in these variables.
1292  */
1293 static int want_object_in_pack(const struct object_id *oid,
1294                                int exclude,
1295                                struct packed_git **found_pack,
1296                                off_t *found_offset)
1297 {
1298         int want;
1299         struct list_head *pos;
1300         struct multi_pack_index *m;
1301
1302         if (!exclude && local && has_loose_object_nonlocal(oid))
1303                 return 0;
1304
1305         /*
1306          * If we already know the pack object lives in, start checks from that
1307          * pack - in the usual case when neither --local was given nor .keep files
1308          * are present we will determine the answer right now.
1309          */
1310         if (*found_pack) {
1311                 want = want_found_object(oid, exclude, *found_pack);
1312                 if (want != -1)
1313                         return want;
1314         }
1315
1316         for (m = get_multi_pack_index(the_repository); m; m = m->next) {
1317                 struct pack_entry e;
1318                 if (fill_midx_entry(the_repository, oid, &e, m)) {
1319                         want = want_object_in_pack_one(e.p, oid, exclude, found_pack, found_offset);
1320                         if (want != -1)
1321                                 return want;
1322                 }
1323         }
1324
1325         list_for_each(pos, get_packed_git_mru(the_repository)) {
1326                 struct packed_git *p = list_entry(pos, struct packed_git, mru);
1327                 want = want_object_in_pack_one(p, oid, exclude, found_pack, found_offset);
1328                 if (!exclude && want > 0)
1329                         list_move(&p->mru,
1330                                   get_packed_git_mru(the_repository));
1331                 if (want != -1)
1332                         return want;
1333         }
1334
1335         if (uri_protocols.nr) {
1336                 struct configured_exclusion *ex =
1337                         oidmap_get(&configured_exclusions, oid);
1338                 int i;
1339                 const char *p;
1340
1341                 if (ex) {
1342                         for (i = 0; i < uri_protocols.nr; i++) {
1343                                 if (skip_prefix(ex->uri,
1344                                                 uri_protocols.items[i].string,
1345                                                 &p) &&
1346                                     *p == ':') {
1347                                         oidset_insert(&excluded_by_config, oid);
1348                                         return 0;
1349                                 }
1350                         }
1351                 }
1352         }
1353
1354         return 1;
1355 }
1356
1357 static void create_object_entry(const struct object_id *oid,
1358                                 enum object_type type,
1359                                 uint32_t hash,
1360                                 int exclude,
1361                                 int no_try_delta,
1362                                 struct packed_git *found_pack,
1363                                 off_t found_offset)
1364 {
1365         struct object_entry *entry;
1366
1367         entry = packlist_alloc(&to_pack, oid);
1368         entry->hash = hash;
1369         oe_set_type(entry, type);
1370         if (exclude)
1371                 entry->preferred_base = 1;
1372         else
1373                 nr_result++;
1374         if (found_pack) {
1375                 oe_set_in_pack(&to_pack, entry, found_pack);
1376                 entry->in_pack_offset = found_offset;
1377         }
1378
1379         entry->no_try_delta = no_try_delta;
1380 }
1381
1382 static const char no_closure_warning[] = N_(
1383 "disabling bitmap writing, as some objects are not being packed"
1384 );
1385
1386 static int add_object_entry(const struct object_id *oid, enum object_type type,
1387                             const char *name, int exclude)
1388 {
1389         struct packed_git *found_pack = NULL;
1390         off_t found_offset = 0;
1391
1392         display_progress(progress_state, ++nr_seen);
1393
1394         if (have_duplicate_entry(oid, exclude))
1395                 return 0;
1396
1397         if (!want_object_in_pack(oid, exclude, &found_pack, &found_offset)) {
1398                 /* The pack is missing an object, so it will not have closure */
1399                 if (write_bitmap_index) {
1400                         if (write_bitmap_index != WRITE_BITMAP_QUIET)
1401                                 warning(_(no_closure_warning));
1402                         write_bitmap_index = 0;
1403                 }
1404                 return 0;
1405         }
1406
1407         create_object_entry(oid, type, pack_name_hash(name),
1408                             exclude, name && no_try_delta(name),
1409                             found_pack, found_offset);
1410         return 1;
1411 }
1412
1413 static int add_object_entry_from_bitmap(const struct object_id *oid,
1414                                         enum object_type type,
1415                                         int flags, uint32_t name_hash,
1416                                         struct packed_git *pack, off_t offset)
1417 {
1418         display_progress(progress_state, ++nr_seen);
1419
1420         if (have_duplicate_entry(oid, 0))
1421                 return 0;
1422
1423         if (!want_object_in_pack(oid, 0, &pack, &offset))
1424                 return 0;
1425
1426         create_object_entry(oid, type, name_hash, 0, 0, pack, offset);
1427         return 1;
1428 }
1429
1430 struct pbase_tree_cache {
1431         struct object_id oid;
1432         int ref;
1433         int temporary;
1434         void *tree_data;
1435         unsigned long tree_size;
1436 };
1437
1438 static struct pbase_tree_cache *(pbase_tree_cache[256]);
1439 static int pbase_tree_cache_ix(const struct object_id *oid)
1440 {
1441         return oid->hash[0] % ARRAY_SIZE(pbase_tree_cache);
1442 }
1443 static int pbase_tree_cache_ix_incr(int ix)
1444 {
1445         return (ix+1) % ARRAY_SIZE(pbase_tree_cache);
1446 }
1447
1448 static struct pbase_tree {
1449         struct pbase_tree *next;
1450         /* This is a phony "cache" entry; we are not
1451          * going to evict it or find it through _get()
1452          * mechanism -- this is for the toplevel node that
1453          * would almost always change with any commit.
1454          */
1455         struct pbase_tree_cache pcache;
1456 } *pbase_tree;
1457
1458 static struct pbase_tree_cache *pbase_tree_get(const struct object_id *oid)
1459 {
1460         struct pbase_tree_cache *ent, *nent;
1461         void *data;
1462         unsigned long size;
1463         enum object_type type;
1464         int neigh;
1465         int my_ix = pbase_tree_cache_ix(oid);
1466         int available_ix = -1;
1467
1468         /* pbase-tree-cache acts as a limited hashtable.
1469          * your object will be found at your index or within a few
1470          * slots after that slot if it is cached.
1471          */
1472         for (neigh = 0; neigh < 8; neigh++) {
1473                 ent = pbase_tree_cache[my_ix];
1474                 if (ent && oideq(&ent->oid, oid)) {
1475                         ent->ref++;
1476                         return ent;
1477                 }
1478                 else if (((available_ix < 0) && (!ent || !ent->ref)) ||
1479                          ((0 <= available_ix) &&
1480                           (!ent && pbase_tree_cache[available_ix])))
1481                         available_ix = my_ix;
1482                 if (!ent)
1483                         break;
1484                 my_ix = pbase_tree_cache_ix_incr(my_ix);
1485         }
1486
1487         /* Did not find one.  Either we got a bogus request or
1488          * we need to read and perhaps cache.
1489          */
1490         data = read_object_file(oid, &type, &size);
1491         if (!data)
1492                 return NULL;
1493         if (type != OBJ_TREE) {
1494                 free(data);
1495                 return NULL;
1496         }
1497
1498         /* We need to either cache or return a throwaway copy */
1499
1500         if (available_ix < 0)
1501                 ent = NULL;
1502         else {
1503                 ent = pbase_tree_cache[available_ix];
1504                 my_ix = available_ix;
1505         }
1506
1507         if (!ent) {
1508                 nent = xmalloc(sizeof(*nent));
1509                 nent->temporary = (available_ix < 0);
1510         }
1511         else {
1512                 /* evict and reuse */
1513                 free(ent->tree_data);
1514                 nent = ent;
1515         }
1516         oidcpy(&nent->oid, oid);
1517         nent->tree_data = data;
1518         nent->tree_size = size;
1519         nent->ref = 1;
1520         if (!nent->temporary)
1521                 pbase_tree_cache[my_ix] = nent;
1522         return nent;
1523 }
1524
1525 static void pbase_tree_put(struct pbase_tree_cache *cache)
1526 {
1527         if (!cache->temporary) {
1528                 cache->ref--;
1529                 return;
1530         }
1531         free(cache->tree_data);
1532         free(cache);
1533 }
1534
1535 static int name_cmp_len(const char *name)
1536 {
1537         int i;
1538         for (i = 0; name[i] && name[i] != '\n' && name[i] != '/'; i++)
1539                 ;
1540         return i;
1541 }
1542
1543 static void add_pbase_object(struct tree_desc *tree,
1544                              const char *name,
1545                              int cmplen,
1546                              const char *fullname)
1547 {
1548         struct name_entry entry;
1549         int cmp;
1550
1551         while (tree_entry(tree,&entry)) {
1552                 if (S_ISGITLINK(entry.mode))
1553                         continue;
1554                 cmp = tree_entry_len(&entry) != cmplen ? 1 :
1555                       memcmp(name, entry.path, cmplen);
1556                 if (cmp > 0)
1557                         continue;
1558                 if (cmp < 0)
1559                         return;
1560                 if (name[cmplen] != '/') {
1561                         add_object_entry(&entry.oid,
1562                                          object_type(entry.mode),
1563                                          fullname, 1);
1564                         return;
1565                 }
1566                 if (S_ISDIR(entry.mode)) {
1567                         struct tree_desc sub;
1568                         struct pbase_tree_cache *tree;
1569                         const char *down = name+cmplen+1;
1570                         int downlen = name_cmp_len(down);
1571
1572                         tree = pbase_tree_get(&entry.oid);
1573                         if (!tree)
1574                                 return;
1575                         init_tree_desc(&sub, tree->tree_data, tree->tree_size);
1576
1577                         add_pbase_object(&sub, down, downlen, fullname);
1578                         pbase_tree_put(tree);
1579                 }
1580         }
1581 }
1582
1583 static unsigned *done_pbase_paths;
1584 static int done_pbase_paths_num;
1585 static int done_pbase_paths_alloc;
1586 static int done_pbase_path_pos(unsigned hash)
1587 {
1588         int lo = 0;
1589         int hi = done_pbase_paths_num;
1590         while (lo < hi) {
1591                 int mi = lo + (hi - lo) / 2;
1592                 if (done_pbase_paths[mi] == hash)
1593                         return mi;
1594                 if (done_pbase_paths[mi] < hash)
1595                         hi = mi;
1596                 else
1597                         lo = mi + 1;
1598         }
1599         return -lo-1;
1600 }
1601
1602 static int check_pbase_path(unsigned hash)
1603 {
1604         int pos = done_pbase_path_pos(hash);
1605         if (0 <= pos)
1606                 return 1;
1607         pos = -pos - 1;
1608         ALLOC_GROW(done_pbase_paths,
1609                    done_pbase_paths_num + 1,
1610                    done_pbase_paths_alloc);
1611         done_pbase_paths_num++;
1612         if (pos < done_pbase_paths_num)
1613                 MOVE_ARRAY(done_pbase_paths + pos + 1, done_pbase_paths + pos,
1614                            done_pbase_paths_num - pos - 1);
1615         done_pbase_paths[pos] = hash;
1616         return 0;
1617 }
1618
1619 static void add_preferred_base_object(const char *name)
1620 {
1621         struct pbase_tree *it;
1622         int cmplen;
1623         unsigned hash = pack_name_hash(name);
1624
1625         if (!num_preferred_base || check_pbase_path(hash))
1626                 return;
1627
1628         cmplen = name_cmp_len(name);
1629         for (it = pbase_tree; it; it = it->next) {
1630                 if (cmplen == 0) {
1631                         add_object_entry(&it->pcache.oid, OBJ_TREE, NULL, 1);
1632                 }
1633                 else {
1634                         struct tree_desc tree;
1635                         init_tree_desc(&tree, it->pcache.tree_data, it->pcache.tree_size);
1636                         add_pbase_object(&tree, name, cmplen, name);
1637                 }
1638         }
1639 }
1640
1641 static void add_preferred_base(struct object_id *oid)
1642 {
1643         struct pbase_tree *it;
1644         void *data;
1645         unsigned long size;
1646         struct object_id tree_oid;
1647
1648         if (window <= num_preferred_base++)
1649                 return;
1650
1651         data = read_object_with_reference(the_repository, oid,
1652                                           tree_type, &size, &tree_oid);
1653         if (!data)
1654                 return;
1655
1656         for (it = pbase_tree; it; it = it->next) {
1657                 if (oideq(&it->pcache.oid, &tree_oid)) {
1658                         free(data);
1659                         return;
1660                 }
1661         }
1662
1663         CALLOC_ARRAY(it, 1);
1664         it->next = pbase_tree;
1665         pbase_tree = it;
1666
1667         oidcpy(&it->pcache.oid, &tree_oid);
1668         it->pcache.tree_data = data;
1669         it->pcache.tree_size = size;
1670 }
1671
1672 static void cleanup_preferred_base(void)
1673 {
1674         struct pbase_tree *it;
1675         unsigned i;
1676
1677         it = pbase_tree;
1678         pbase_tree = NULL;
1679         while (it) {
1680                 struct pbase_tree *tmp = it;
1681                 it = tmp->next;
1682                 free(tmp->pcache.tree_data);
1683                 free(tmp);
1684         }
1685
1686         for (i = 0; i < ARRAY_SIZE(pbase_tree_cache); i++) {
1687                 if (!pbase_tree_cache[i])
1688                         continue;
1689                 free(pbase_tree_cache[i]->tree_data);
1690                 FREE_AND_NULL(pbase_tree_cache[i]);
1691         }
1692
1693         FREE_AND_NULL(done_pbase_paths);
1694         done_pbase_paths_num = done_pbase_paths_alloc = 0;
1695 }
1696
1697 /*
1698  * Return 1 iff the object specified by "delta" can be sent
1699  * literally as a delta against the base in "base_sha1". If
1700  * so, then *base_out will point to the entry in our packing
1701  * list, or NULL if we must use the external-base list.
1702  *
1703  * Depth value does not matter - find_deltas() will
1704  * never consider reused delta as the base object to
1705  * deltify other objects against, in order to avoid
1706  * circular deltas.
1707  */
1708 static int can_reuse_delta(const struct object_id *base_oid,
1709                            struct object_entry *delta,
1710                            struct object_entry **base_out)
1711 {
1712         struct object_entry *base;
1713
1714         /*
1715          * First see if we're already sending the base (or it's explicitly in
1716          * our "excluded" list).
1717          */
1718         base = packlist_find(&to_pack, base_oid);
1719         if (base) {
1720                 if (!in_same_island(&delta->idx.oid, &base->idx.oid))
1721                         return 0;
1722                 *base_out = base;
1723                 return 1;
1724         }
1725
1726         /*
1727          * Otherwise, reachability bitmaps may tell us if the receiver has it,
1728          * even if it was buried too deep in history to make it into the
1729          * packing list.
1730          */
1731         if (thin && bitmap_has_oid_in_uninteresting(bitmap_git, base_oid)) {
1732                 if (use_delta_islands) {
1733                         if (!in_same_island(&delta->idx.oid, base_oid))
1734                                 return 0;
1735                 }
1736                 *base_out = NULL;
1737                 return 1;
1738         }
1739
1740         return 0;
1741 }
1742
1743 static void prefetch_to_pack(uint32_t object_index_start) {
1744         struct oid_array to_fetch = OID_ARRAY_INIT;
1745         uint32_t i;
1746
1747         for (i = object_index_start; i < to_pack.nr_objects; i++) {
1748                 struct object_entry *entry = to_pack.objects + i;
1749
1750                 if (!oid_object_info_extended(the_repository,
1751                                               &entry->idx.oid,
1752                                               NULL,
1753                                               OBJECT_INFO_FOR_PREFETCH))
1754                         continue;
1755                 oid_array_append(&to_fetch, &entry->idx.oid);
1756         }
1757         promisor_remote_get_direct(the_repository,
1758                                    to_fetch.oid, to_fetch.nr);
1759         oid_array_clear(&to_fetch);
1760 }
1761
1762 static void check_object(struct object_entry *entry, uint32_t object_index)
1763 {
1764         unsigned long canonical_size;
1765         enum object_type type;
1766         struct object_info oi = {.typep = &type, .sizep = &canonical_size};
1767
1768         if (IN_PACK(entry)) {
1769                 struct packed_git *p = IN_PACK(entry);
1770                 struct pack_window *w_curs = NULL;
1771                 int have_base = 0;
1772                 struct object_id base_ref;
1773                 struct object_entry *base_entry;
1774                 unsigned long used, used_0;
1775                 unsigned long avail;
1776                 off_t ofs;
1777                 unsigned char *buf, c;
1778                 enum object_type type;
1779                 unsigned long in_pack_size;
1780
1781                 buf = use_pack(p, &w_curs, entry->in_pack_offset, &avail);
1782
1783                 /*
1784                  * We want in_pack_type even if we do not reuse delta
1785                  * since non-delta representations could still be reused.
1786                  */
1787                 used = unpack_object_header_buffer(buf, avail,
1788                                                    &type,
1789                                                    &in_pack_size);
1790                 if (used == 0)
1791                         goto give_up;
1792
1793                 if (type < 0)
1794                         BUG("invalid type %d", type);
1795                 entry->in_pack_type = type;
1796
1797                 /*
1798                  * Determine if this is a delta and if so whether we can
1799                  * reuse it or not.  Otherwise let's find out as cheaply as
1800                  * possible what the actual type and size for this object is.
1801                  */
1802                 switch (entry->in_pack_type) {
1803                 default:
1804                         /* Not a delta hence we've already got all we need. */
1805                         oe_set_type(entry, entry->in_pack_type);
1806                         SET_SIZE(entry, in_pack_size);
1807                         entry->in_pack_header_size = used;
1808                         if (oe_type(entry) < OBJ_COMMIT || oe_type(entry) > OBJ_BLOB)
1809                                 goto give_up;
1810                         unuse_pack(&w_curs);
1811                         return;
1812                 case OBJ_REF_DELTA:
1813                         if (reuse_delta && !entry->preferred_base) {
1814                                 oidread(&base_ref,
1815                                         use_pack(p, &w_curs,
1816                                                  entry->in_pack_offset + used,
1817                                                  NULL));
1818                                 have_base = 1;
1819                         }
1820                         entry->in_pack_header_size = used + the_hash_algo->rawsz;
1821                         break;
1822                 case OBJ_OFS_DELTA:
1823                         buf = use_pack(p, &w_curs,
1824                                        entry->in_pack_offset + used, NULL);
1825                         used_0 = 0;
1826                         c = buf[used_0++];
1827                         ofs = c & 127;
1828                         while (c & 128) {
1829                                 ofs += 1;
1830                                 if (!ofs || MSB(ofs, 7)) {
1831                                         error(_("delta base offset overflow in pack for %s"),
1832                                               oid_to_hex(&entry->idx.oid));
1833                                         goto give_up;
1834                                 }
1835                                 c = buf[used_0++];
1836                                 ofs = (ofs << 7) + (c & 127);
1837                         }
1838                         ofs = entry->in_pack_offset - ofs;
1839                         if (ofs <= 0 || ofs >= entry->in_pack_offset) {
1840                                 error(_("delta base offset out of bound for %s"),
1841                                       oid_to_hex(&entry->idx.oid));
1842                                 goto give_up;
1843                         }
1844                         if (reuse_delta && !entry->preferred_base) {
1845                                 uint32_t pos;
1846                                 if (offset_to_pack_pos(p, ofs, &pos) < 0)
1847                                         goto give_up;
1848                                 if (!nth_packed_object_id(&base_ref, p,
1849                                                           pack_pos_to_index(p, pos)))
1850                                         have_base = 1;
1851                         }
1852                         entry->in_pack_header_size = used + used_0;
1853                         break;
1854                 }
1855
1856                 if (have_base &&
1857                     can_reuse_delta(&base_ref, entry, &base_entry)) {
1858                         oe_set_type(entry, entry->in_pack_type);
1859                         SET_SIZE(entry, in_pack_size); /* delta size */
1860                         SET_DELTA_SIZE(entry, in_pack_size);
1861
1862                         if (base_entry) {
1863                                 SET_DELTA(entry, base_entry);
1864                                 entry->delta_sibling_idx = base_entry->delta_child_idx;
1865                                 SET_DELTA_CHILD(base_entry, entry);
1866                         } else {
1867                                 SET_DELTA_EXT(entry, &base_ref);
1868                         }
1869
1870                         unuse_pack(&w_curs);
1871                         return;
1872                 }
1873
1874                 if (oe_type(entry)) {
1875                         off_t delta_pos;
1876
1877                         /*
1878                          * This must be a delta and we already know what the
1879                          * final object type is.  Let's extract the actual
1880                          * object size from the delta header.
1881                          */
1882                         delta_pos = entry->in_pack_offset + entry->in_pack_header_size;
1883                         canonical_size = get_size_from_delta(p, &w_curs, delta_pos);
1884                         if (canonical_size == 0)
1885                                 goto give_up;
1886                         SET_SIZE(entry, canonical_size);
1887                         unuse_pack(&w_curs);
1888                         return;
1889                 }
1890
1891                 /*
1892                  * No choice but to fall back to the recursive delta walk
1893                  * with oid_object_info() to find about the object type
1894                  * at this point...
1895                  */
1896                 give_up:
1897                 unuse_pack(&w_curs);
1898         }
1899
1900         if (oid_object_info_extended(the_repository, &entry->idx.oid, &oi,
1901                                      OBJECT_INFO_SKIP_FETCH_OBJECT | OBJECT_INFO_LOOKUP_REPLACE) < 0) {
1902                 if (has_promisor_remote()) {
1903                         prefetch_to_pack(object_index);
1904                         if (oid_object_info_extended(the_repository, &entry->idx.oid, &oi,
1905                                                      OBJECT_INFO_SKIP_FETCH_OBJECT | OBJECT_INFO_LOOKUP_REPLACE) < 0)
1906                                 type = -1;
1907                 } else {
1908                         type = -1;
1909                 }
1910         }
1911         oe_set_type(entry, type);
1912         if (entry->type_valid) {
1913                 SET_SIZE(entry, canonical_size);
1914         } else {
1915                 /*
1916                  * Bad object type is checked in prepare_pack().  This is
1917                  * to permit a missing preferred base object to be ignored
1918                  * as a preferred base.  Doing so can result in a larger
1919                  * pack file, but the transfer will still take place.
1920                  */
1921         }
1922 }
1923
1924 static int pack_offset_sort(const void *_a, const void *_b)
1925 {
1926         const struct object_entry *a = *(struct object_entry **)_a;
1927         const struct object_entry *b = *(struct object_entry **)_b;
1928         const struct packed_git *a_in_pack = IN_PACK(a);
1929         const struct packed_git *b_in_pack = IN_PACK(b);
1930
1931         /* avoid filesystem trashing with loose objects */
1932         if (!a_in_pack && !b_in_pack)
1933                 return oidcmp(&a->idx.oid, &b->idx.oid);
1934
1935         if (a_in_pack < b_in_pack)
1936                 return -1;
1937         if (a_in_pack > b_in_pack)
1938                 return 1;
1939         return a->in_pack_offset < b->in_pack_offset ? -1 :
1940                         (a->in_pack_offset > b->in_pack_offset);
1941 }
1942
1943 /*
1944  * Drop an on-disk delta we were planning to reuse. Naively, this would
1945  * just involve blanking out the "delta" field, but we have to deal
1946  * with some extra book-keeping:
1947  *
1948  *   1. Removing ourselves from the delta_sibling linked list.
1949  *
1950  *   2. Updating our size/type to the non-delta representation. These were
1951  *      either not recorded initially (size) or overwritten with the delta type
1952  *      (type) when check_object() decided to reuse the delta.
1953  *
1954  *   3. Resetting our delta depth, as we are now a base object.
1955  */
1956 static void drop_reused_delta(struct object_entry *entry)
1957 {
1958         unsigned *idx = &to_pack.objects[entry->delta_idx - 1].delta_child_idx;
1959         struct object_info oi = OBJECT_INFO_INIT;
1960         enum object_type type;
1961         unsigned long size;
1962
1963         while (*idx) {
1964                 struct object_entry *oe = &to_pack.objects[*idx - 1];
1965
1966                 if (oe == entry)
1967                         *idx = oe->delta_sibling_idx;
1968                 else
1969                         idx = &oe->delta_sibling_idx;
1970         }
1971         SET_DELTA(entry, NULL);
1972         entry->depth = 0;
1973
1974         oi.sizep = &size;
1975         oi.typep = &type;
1976         if (packed_object_info(the_repository, IN_PACK(entry), entry->in_pack_offset, &oi) < 0) {
1977                 /*
1978                  * We failed to get the info from this pack for some reason;
1979                  * fall back to oid_object_info, which may find another copy.
1980                  * And if that fails, the error will be recorded in oe_type(entry)
1981                  * and dealt with in prepare_pack().
1982                  */
1983                 oe_set_type(entry,
1984                             oid_object_info(the_repository, &entry->idx.oid, &size));
1985         } else {
1986                 oe_set_type(entry, type);
1987         }
1988         SET_SIZE(entry, size);
1989 }
1990
1991 /*
1992  * Follow the chain of deltas from this entry onward, throwing away any links
1993  * that cause us to hit a cycle (as determined by the DFS state flags in
1994  * the entries).
1995  *
1996  * We also detect too-long reused chains that would violate our --depth
1997  * limit.
1998  */
1999 static void break_delta_chains(struct object_entry *entry)
2000 {
2001         /*
2002          * The actual depth of each object we will write is stored as an int,
2003          * as it cannot exceed our int "depth" limit. But before we break
2004          * changes based no that limit, we may potentially go as deep as the
2005          * number of objects, which is elsewhere bounded to a uint32_t.
2006          */
2007         uint32_t total_depth;
2008         struct object_entry *cur, *next;
2009
2010         for (cur = entry, total_depth = 0;
2011              cur;
2012              cur = DELTA(cur), total_depth++) {
2013                 if (cur->dfs_state == DFS_DONE) {
2014                         /*
2015                          * We've already seen this object and know it isn't
2016                          * part of a cycle. We do need to append its depth
2017                          * to our count.
2018                          */
2019                         total_depth += cur->depth;
2020                         break;
2021                 }
2022
2023                 /*
2024                  * We break cycles before looping, so an ACTIVE state (or any
2025                  * other cruft which made its way into the state variable)
2026                  * is a bug.
2027                  */
2028                 if (cur->dfs_state != DFS_NONE)
2029                         BUG("confusing delta dfs state in first pass: %d",
2030                             cur->dfs_state);
2031
2032                 /*
2033                  * Now we know this is the first time we've seen the object. If
2034                  * it's not a delta, we're done traversing, but we'll mark it
2035                  * done to save time on future traversals.
2036                  */
2037                 if (!DELTA(cur)) {
2038                         cur->dfs_state = DFS_DONE;
2039                         break;
2040                 }
2041
2042                 /*
2043                  * Mark ourselves as active and see if the next step causes
2044                  * us to cycle to another active object. It's important to do
2045                  * this _before_ we loop, because it impacts where we make the
2046                  * cut, and thus how our total_depth counter works.
2047                  * E.g., We may see a partial loop like:
2048                  *
2049                  *   A -> B -> C -> D -> B
2050                  *
2051                  * Cutting B->C breaks the cycle. But now the depth of A is
2052                  * only 1, and our total_depth counter is at 3. The size of the
2053                  * error is always one less than the size of the cycle we
2054                  * broke. Commits C and D were "lost" from A's chain.
2055                  *
2056                  * If we instead cut D->B, then the depth of A is correct at 3.
2057                  * We keep all commits in the chain that we examined.
2058                  */
2059                 cur->dfs_state = DFS_ACTIVE;
2060                 if (DELTA(cur)->dfs_state == DFS_ACTIVE) {
2061                         drop_reused_delta(cur);
2062                         cur->dfs_state = DFS_DONE;
2063                         break;
2064                 }
2065         }
2066
2067         /*
2068          * And now that we've gone all the way to the bottom of the chain, we
2069          * need to clear the active flags and set the depth fields as
2070          * appropriate. Unlike the loop above, which can quit when it drops a
2071          * delta, we need to keep going to look for more depth cuts. So we need
2072          * an extra "next" pointer to keep going after we reset cur->delta.
2073          */
2074         for (cur = entry; cur; cur = next) {
2075                 next = DELTA(cur);
2076
2077                 /*
2078                  * We should have a chain of zero or more ACTIVE states down to
2079                  * a final DONE. We can quit after the DONE, because either it
2080                  * has no bases, or we've already handled them in a previous
2081                  * call.
2082                  */
2083                 if (cur->dfs_state == DFS_DONE)
2084                         break;
2085                 else if (cur->dfs_state != DFS_ACTIVE)
2086                         BUG("confusing delta dfs state in second pass: %d",
2087                             cur->dfs_state);
2088
2089                 /*
2090                  * If the total_depth is more than depth, then we need to snip
2091                  * the chain into two or more smaller chains that don't exceed
2092                  * the maximum depth. Most of the resulting chains will contain
2093                  * (depth + 1) entries (i.e., depth deltas plus one base), and
2094                  * the last chain (i.e., the one containing entry) will contain
2095                  * whatever entries are left over, namely
2096                  * (total_depth % (depth + 1)) of them.
2097                  *
2098                  * Since we are iterating towards decreasing depth, we need to
2099                  * decrement total_depth as we go, and we need to write to the
2100                  * entry what its final depth will be after all of the
2101                  * snipping. Since we're snipping into chains of length (depth
2102                  * + 1) entries, the final depth of an entry will be its
2103                  * original depth modulo (depth + 1). Any time we encounter an
2104                  * entry whose final depth is supposed to be zero, we snip it
2105                  * from its delta base, thereby making it so.
2106                  */
2107                 cur->depth = (total_depth--) % (depth + 1);
2108                 if (!cur->depth)
2109                         drop_reused_delta(cur);
2110
2111                 cur->dfs_state = DFS_DONE;
2112         }
2113 }
2114
2115 static void get_object_details(void)
2116 {
2117         uint32_t i;
2118         struct object_entry **sorted_by_offset;
2119
2120         if (progress)
2121                 progress_state = start_progress(_("Counting objects"),
2122                                                 to_pack.nr_objects);
2123
2124         CALLOC_ARRAY(sorted_by_offset, to_pack.nr_objects);
2125         for (i = 0; i < to_pack.nr_objects; i++)
2126                 sorted_by_offset[i] = to_pack.objects + i;
2127         QSORT(sorted_by_offset, to_pack.nr_objects, pack_offset_sort);
2128
2129         for (i = 0; i < to_pack.nr_objects; i++) {
2130                 struct object_entry *entry = sorted_by_offset[i];
2131                 check_object(entry, i);
2132                 if (entry->type_valid &&
2133                     oe_size_greater_than(&to_pack, entry, big_file_threshold))
2134                         entry->no_try_delta = 1;
2135                 display_progress(progress_state, i + 1);
2136         }
2137         stop_progress(&progress_state);
2138
2139         /*
2140          * This must happen in a second pass, since we rely on the delta
2141          * information for the whole list being completed.
2142          */
2143         for (i = 0; i < to_pack.nr_objects; i++)
2144                 break_delta_chains(&to_pack.objects[i]);
2145
2146         free(sorted_by_offset);
2147 }
2148
2149 /*
2150  * We search for deltas in a list sorted by type, by filename hash, and then
2151  * by size, so that we see progressively smaller and smaller files.
2152  * That's because we prefer deltas to be from the bigger file
2153  * to the smaller -- deletes are potentially cheaper, but perhaps
2154  * more importantly, the bigger file is likely the more recent
2155  * one.  The deepest deltas are therefore the oldest objects which are
2156  * less susceptible to be accessed often.
2157  */
2158 static int type_size_sort(const void *_a, const void *_b)
2159 {
2160         const struct object_entry *a = *(struct object_entry **)_a;
2161         const struct object_entry *b = *(struct object_entry **)_b;
2162         const enum object_type a_type = oe_type(a);
2163         const enum object_type b_type = oe_type(b);
2164         const unsigned long a_size = SIZE(a);
2165         const unsigned long b_size = SIZE(b);
2166
2167         if (a_type > b_type)
2168                 return -1;
2169         if (a_type < b_type)
2170                 return 1;
2171         if (a->hash > b->hash)
2172                 return -1;
2173         if (a->hash < b->hash)
2174                 return 1;
2175         if (a->preferred_base > b->preferred_base)
2176                 return -1;
2177         if (a->preferred_base < b->preferred_base)
2178                 return 1;
2179         if (use_delta_islands) {
2180                 const int island_cmp = island_delta_cmp(&a->idx.oid, &b->idx.oid);
2181                 if (island_cmp)
2182                         return island_cmp;
2183         }
2184         if (a_size > b_size)
2185                 return -1;
2186         if (a_size < b_size)
2187                 return 1;
2188         return a < b ? -1 : (a > b);  /* newest first */
2189 }
2190
2191 struct unpacked {
2192         struct object_entry *entry;
2193         void *data;
2194         struct delta_index *index;
2195         unsigned depth;
2196 };
2197
2198 static int delta_cacheable(unsigned long src_size, unsigned long trg_size,
2199                            unsigned long delta_size)
2200 {
2201         if (max_delta_cache_size && delta_cache_size + delta_size > max_delta_cache_size)
2202                 return 0;
2203
2204         if (delta_size < cache_max_small_delta_size)
2205                 return 1;
2206
2207         /* cache delta, if objects are large enough compared to delta size */
2208         if ((src_size >> 20) + (trg_size >> 21) > (delta_size >> 10))
2209                 return 1;
2210
2211         return 0;
2212 }
2213
2214 /* Protect delta_cache_size */
2215 static pthread_mutex_t cache_mutex;
2216 #define cache_lock()            pthread_mutex_lock(&cache_mutex)
2217 #define cache_unlock()          pthread_mutex_unlock(&cache_mutex)
2218
2219 /*
2220  * Protect object list partitioning (e.g. struct thread_param) and
2221  * progress_state
2222  */
2223 static pthread_mutex_t progress_mutex;
2224 #define progress_lock()         pthread_mutex_lock(&progress_mutex)
2225 #define progress_unlock()       pthread_mutex_unlock(&progress_mutex)
2226
2227 /*
2228  * Access to struct object_entry is unprotected since each thread owns
2229  * a portion of the main object list. Just don't access object entries
2230  * ahead in the list because they can be stolen and would need
2231  * progress_mutex for protection.
2232  */
2233
2234 /*
2235  * Return the size of the object without doing any delta
2236  * reconstruction (so non-deltas are true object sizes, but deltas
2237  * return the size of the delta data).
2238  */
2239 unsigned long oe_get_size_slow(struct packing_data *pack,
2240                                const struct object_entry *e)
2241 {
2242         struct packed_git *p;
2243         struct pack_window *w_curs;
2244         unsigned char *buf;
2245         enum object_type type;
2246         unsigned long used, avail, size;
2247
2248         if (e->type_ != OBJ_OFS_DELTA && e->type_ != OBJ_REF_DELTA) {
2249                 packing_data_lock(&to_pack);
2250                 if (oid_object_info(the_repository, &e->idx.oid, &size) < 0)
2251                         die(_("unable to get size of %s"),
2252                             oid_to_hex(&e->idx.oid));
2253                 packing_data_unlock(&to_pack);
2254                 return size;
2255         }
2256
2257         p = oe_in_pack(pack, e);
2258         if (!p)
2259                 BUG("when e->type is a delta, it must belong to a pack");
2260
2261         packing_data_lock(&to_pack);
2262         w_curs = NULL;
2263         buf = use_pack(p, &w_curs, e->in_pack_offset, &avail);
2264         used = unpack_object_header_buffer(buf, avail, &type, &size);
2265         if (used == 0)
2266                 die(_("unable to parse object header of %s"),
2267                     oid_to_hex(&e->idx.oid));
2268
2269         unuse_pack(&w_curs);
2270         packing_data_unlock(&to_pack);
2271         return size;
2272 }
2273
2274 static int try_delta(struct unpacked *trg, struct unpacked *src,
2275                      unsigned max_depth, unsigned long *mem_usage)
2276 {
2277         struct object_entry *trg_entry = trg->entry;
2278         struct object_entry *src_entry = src->entry;
2279         unsigned long trg_size, src_size, delta_size, sizediff, max_size, sz;
2280         unsigned ref_depth;
2281         enum object_type type;
2282         void *delta_buf;
2283
2284         /* Don't bother doing diffs between different types */
2285         if (oe_type(trg_entry) != oe_type(src_entry))
2286                 return -1;
2287
2288         /*
2289          * We do not bother to try a delta that we discarded on an
2290          * earlier try, but only when reusing delta data.  Note that
2291          * src_entry that is marked as the preferred_base should always
2292          * be considered, as even if we produce a suboptimal delta against
2293          * it, we will still save the transfer cost, as we already know
2294          * the other side has it and we won't send src_entry at all.
2295          */
2296         if (reuse_delta && IN_PACK(trg_entry) &&
2297             IN_PACK(trg_entry) == IN_PACK(src_entry) &&
2298             !src_entry->preferred_base &&
2299             trg_entry->in_pack_type != OBJ_REF_DELTA &&
2300             trg_entry->in_pack_type != OBJ_OFS_DELTA)
2301                 return 0;
2302
2303         /* Let's not bust the allowed depth. */
2304         if (src->depth >= max_depth)
2305                 return 0;
2306
2307         /* Now some size filtering heuristics. */
2308         trg_size = SIZE(trg_entry);
2309         if (!DELTA(trg_entry)) {
2310                 max_size = trg_size/2 - the_hash_algo->rawsz;
2311                 ref_depth = 1;
2312         } else {
2313                 max_size = DELTA_SIZE(trg_entry);
2314                 ref_depth = trg->depth;
2315         }
2316         max_size = (uint64_t)max_size * (max_depth - src->depth) /
2317                                                 (max_depth - ref_depth + 1);
2318         if (max_size == 0)
2319                 return 0;
2320         src_size = SIZE(src_entry);
2321         sizediff = src_size < trg_size ? trg_size - src_size : 0;
2322         if (sizediff >= max_size)
2323                 return 0;
2324         if (trg_size < src_size / 32)
2325                 return 0;
2326
2327         if (!in_same_island(&trg->entry->idx.oid, &src->entry->idx.oid))
2328                 return 0;
2329
2330         /* Load data if not already done */
2331         if (!trg->data) {
2332                 packing_data_lock(&to_pack);
2333                 trg->data = read_object_file(&trg_entry->idx.oid, &type, &sz);
2334                 packing_data_unlock(&to_pack);
2335                 if (!trg->data)
2336                         die(_("object %s cannot be read"),
2337                             oid_to_hex(&trg_entry->idx.oid));
2338                 if (sz != trg_size)
2339                         die(_("object %s inconsistent object length (%"PRIuMAX" vs %"PRIuMAX")"),
2340                             oid_to_hex(&trg_entry->idx.oid), (uintmax_t)sz,
2341                             (uintmax_t)trg_size);
2342                 *mem_usage += sz;
2343         }
2344         if (!src->data) {
2345                 packing_data_lock(&to_pack);
2346                 src->data = read_object_file(&src_entry->idx.oid, &type, &sz);
2347                 packing_data_unlock(&to_pack);
2348                 if (!src->data) {
2349                         if (src_entry->preferred_base) {
2350                                 static int warned = 0;
2351                                 if (!warned++)
2352                                         warning(_("object %s cannot be read"),
2353                                                 oid_to_hex(&src_entry->idx.oid));
2354                                 /*
2355                                  * Those objects are not included in the
2356                                  * resulting pack.  Be resilient and ignore
2357                                  * them if they can't be read, in case the
2358                                  * pack could be created nevertheless.
2359                                  */
2360                                 return 0;
2361                         }
2362                         die(_("object %s cannot be read"),
2363                             oid_to_hex(&src_entry->idx.oid));
2364                 }
2365                 if (sz != src_size)
2366                         die(_("object %s inconsistent object length (%"PRIuMAX" vs %"PRIuMAX")"),
2367                             oid_to_hex(&src_entry->idx.oid), (uintmax_t)sz,
2368                             (uintmax_t)src_size);
2369                 *mem_usage += sz;
2370         }
2371         if (!src->index) {
2372                 src->index = create_delta_index(src->data, src_size);
2373                 if (!src->index) {
2374                         static int warned = 0;
2375                         if (!warned++)
2376                                 warning(_("suboptimal pack - out of memory"));
2377                         return 0;
2378                 }
2379                 *mem_usage += sizeof_delta_index(src->index);
2380         }
2381
2382         delta_buf = create_delta(src->index, trg->data, trg_size, &delta_size, max_size);
2383         if (!delta_buf)
2384                 return 0;
2385
2386         if (DELTA(trg_entry)) {
2387                 /* Prefer only shallower same-sized deltas. */
2388                 if (delta_size == DELTA_SIZE(trg_entry) &&
2389                     src->depth + 1 >= trg->depth) {
2390                         free(delta_buf);
2391                         return 0;
2392                 }
2393         }
2394
2395         /*
2396          * Handle memory allocation outside of the cache
2397          * accounting lock.  Compiler will optimize the strangeness
2398          * away when NO_PTHREADS is defined.
2399          */
2400         free(trg_entry->delta_data);
2401         cache_lock();
2402         if (trg_entry->delta_data) {
2403                 delta_cache_size -= DELTA_SIZE(trg_entry);
2404                 trg_entry->delta_data = NULL;
2405         }
2406         if (delta_cacheable(src_size, trg_size, delta_size)) {
2407                 delta_cache_size += delta_size;
2408                 cache_unlock();
2409                 trg_entry->delta_data = xrealloc(delta_buf, delta_size);
2410         } else {
2411                 cache_unlock();
2412                 free(delta_buf);
2413         }
2414
2415         SET_DELTA(trg_entry, src_entry);
2416         SET_DELTA_SIZE(trg_entry, delta_size);
2417         trg->depth = src->depth + 1;
2418
2419         return 1;
2420 }
2421
2422 static unsigned int check_delta_limit(struct object_entry *me, unsigned int n)
2423 {
2424         struct object_entry *child = DELTA_CHILD(me);
2425         unsigned int m = n;
2426         while (child) {
2427                 const unsigned int c = check_delta_limit(child, n + 1);
2428                 if (m < c)
2429                         m = c;
2430                 child = DELTA_SIBLING(child);
2431         }
2432         return m;
2433 }
2434
2435 static unsigned long free_unpacked(struct unpacked *n)
2436 {
2437         unsigned long freed_mem = sizeof_delta_index(n->index);
2438         free_delta_index(n->index);
2439         n->index = NULL;
2440         if (n->data) {
2441                 freed_mem += SIZE(n->entry);
2442                 FREE_AND_NULL(n->data);
2443         }
2444         n->entry = NULL;
2445         n->depth = 0;
2446         return freed_mem;
2447 }
2448
2449 static void find_deltas(struct object_entry **list, unsigned *list_size,
2450                         int window, int depth, unsigned *processed)
2451 {
2452         uint32_t i, idx = 0, count = 0;
2453         struct unpacked *array;
2454         unsigned long mem_usage = 0;
2455
2456         CALLOC_ARRAY(array, window);
2457
2458         for (;;) {
2459                 struct object_entry *entry;
2460                 struct unpacked *n = array + idx;
2461                 int j, max_depth, best_base = -1;
2462
2463                 progress_lock();
2464                 if (!*list_size) {
2465                         progress_unlock();
2466                         break;
2467                 }
2468                 entry = *list++;
2469                 (*list_size)--;
2470                 if (!entry->preferred_base) {
2471                         (*processed)++;
2472                         display_progress(progress_state, *processed);
2473                 }
2474                 progress_unlock();
2475
2476                 mem_usage -= free_unpacked(n);
2477                 n->entry = entry;
2478
2479                 while (window_memory_limit &&
2480                        mem_usage > window_memory_limit &&
2481                        count > 1) {
2482                         const uint32_t tail = (idx + window - count) % window;
2483                         mem_usage -= free_unpacked(array + tail);
2484                         count--;
2485                 }
2486
2487                 /* We do not compute delta to *create* objects we are not
2488                  * going to pack.
2489                  */
2490                 if (entry->preferred_base)
2491                         goto next;
2492
2493                 /*
2494                  * If the current object is at pack edge, take the depth the
2495                  * objects that depend on the current object into account
2496                  * otherwise they would become too deep.
2497                  */
2498                 max_depth = depth;
2499                 if (DELTA_CHILD(entry)) {
2500                         max_depth -= check_delta_limit(entry, 0);
2501                         if (max_depth <= 0)
2502                                 goto next;
2503                 }
2504
2505                 j = window;
2506                 while (--j > 0) {
2507                         int ret;
2508                         uint32_t other_idx = idx + j;
2509                         struct unpacked *m;
2510                         if (other_idx >= window)
2511                                 other_idx -= window;
2512                         m = array + other_idx;
2513                         if (!m->entry)
2514                                 break;
2515                         ret = try_delta(n, m, max_depth, &mem_usage);
2516                         if (ret < 0)
2517                                 break;
2518                         else if (ret > 0)
2519                                 best_base = other_idx;
2520                 }
2521
2522                 /*
2523                  * If we decided to cache the delta data, then it is best
2524                  * to compress it right away.  First because we have to do
2525                  * it anyway, and doing it here while we're threaded will
2526                  * save a lot of time in the non threaded write phase,
2527                  * as well as allow for caching more deltas within
2528                  * the same cache size limit.
2529                  * ...
2530                  * But only if not writing to stdout, since in that case
2531                  * the network is most likely throttling writes anyway,
2532                  * and therefore it is best to go to the write phase ASAP
2533                  * instead, as we can afford spending more time compressing
2534                  * between writes at that moment.
2535                  */
2536                 if (entry->delta_data && !pack_to_stdout) {
2537                         unsigned long size;
2538
2539                         size = do_compress(&entry->delta_data, DELTA_SIZE(entry));
2540                         if (size < (1U << OE_Z_DELTA_BITS)) {
2541                                 entry->z_delta_size = size;
2542                                 cache_lock();
2543                                 delta_cache_size -= DELTA_SIZE(entry);
2544                                 delta_cache_size += entry->z_delta_size;
2545                                 cache_unlock();
2546                         } else {
2547                                 FREE_AND_NULL(entry->delta_data);
2548                                 entry->z_delta_size = 0;
2549                         }
2550                 }
2551
2552                 /* if we made n a delta, and if n is already at max
2553                  * depth, leaving it in the window is pointless.  we
2554                  * should evict it first.
2555                  */
2556                 if (DELTA(entry) && max_depth <= n->depth)
2557                         continue;
2558
2559                 /*
2560                  * Move the best delta base up in the window, after the
2561                  * currently deltified object, to keep it longer.  It will
2562                  * be the first base object to be attempted next.
2563                  */
2564                 if (DELTA(entry)) {
2565                         struct unpacked swap = array[best_base];
2566                         int dist = (window + idx - best_base) % window;
2567                         int dst = best_base;
2568                         while (dist--) {
2569                                 int src = (dst + 1) % window;
2570                                 array[dst] = array[src];
2571                                 dst = src;
2572                         }
2573                         array[dst] = swap;
2574                 }
2575
2576                 next:
2577                 idx++;
2578                 if (count + 1 < window)
2579                         count++;
2580                 if (idx >= window)
2581                         idx = 0;
2582         }
2583
2584         for (i = 0; i < window; ++i) {
2585                 free_delta_index(array[i].index);
2586                 free(array[i].data);
2587         }
2588         free(array);
2589 }
2590
2591 /*
2592  * The main object list is split into smaller lists, each is handed to
2593  * one worker.
2594  *
2595  * The main thread waits on the condition that (at least) one of the workers
2596  * has stopped working (which is indicated in the .working member of
2597  * struct thread_params).
2598  *
2599  * When a work thread has completed its work, it sets .working to 0 and
2600  * signals the main thread and waits on the condition that .data_ready
2601  * becomes 1.
2602  *
2603  * The main thread steals half of the work from the worker that has
2604  * most work left to hand it to the idle worker.
2605  */
2606
2607 struct thread_params {
2608         pthread_t thread;
2609         struct object_entry **list;
2610         unsigned list_size;
2611         unsigned remaining;
2612         int window;
2613         int depth;
2614         int working;
2615         int data_ready;
2616         pthread_mutex_t mutex;
2617         pthread_cond_t cond;
2618         unsigned *processed;
2619 };
2620
2621 static pthread_cond_t progress_cond;
2622
2623 /*
2624  * Mutex and conditional variable can't be statically-initialized on Windows.
2625  */
2626 static void init_threaded_search(void)
2627 {
2628         pthread_mutex_init(&cache_mutex, NULL);
2629         pthread_mutex_init(&progress_mutex, NULL);
2630         pthread_cond_init(&progress_cond, NULL);
2631 }
2632
2633 static void cleanup_threaded_search(void)
2634 {
2635         pthread_cond_destroy(&progress_cond);
2636         pthread_mutex_destroy(&cache_mutex);
2637         pthread_mutex_destroy(&progress_mutex);
2638 }
2639
2640 static void *threaded_find_deltas(void *arg)
2641 {
2642         struct thread_params *me = arg;
2643
2644         progress_lock();
2645         while (me->remaining) {
2646                 progress_unlock();
2647
2648                 find_deltas(me->list, &me->remaining,
2649                             me->window, me->depth, me->processed);
2650
2651                 progress_lock();
2652                 me->working = 0;
2653                 pthread_cond_signal(&progress_cond);
2654                 progress_unlock();
2655
2656                 /*
2657                  * We must not set ->data_ready before we wait on the
2658                  * condition because the main thread may have set it to 1
2659                  * before we get here. In order to be sure that new
2660                  * work is available if we see 1 in ->data_ready, it
2661                  * was initialized to 0 before this thread was spawned
2662                  * and we reset it to 0 right away.
2663                  */
2664                 pthread_mutex_lock(&me->mutex);
2665                 while (!me->data_ready)
2666                         pthread_cond_wait(&me->cond, &me->mutex);
2667                 me->data_ready = 0;
2668                 pthread_mutex_unlock(&me->mutex);
2669
2670                 progress_lock();
2671         }
2672         progress_unlock();
2673         /* leave ->working 1 so that this doesn't get more work assigned */
2674         return NULL;
2675 }
2676
2677 static void ll_find_deltas(struct object_entry **list, unsigned list_size,
2678                            int window, int depth, unsigned *processed)
2679 {
2680         struct thread_params *p;
2681         int i, ret, active_threads = 0;
2682
2683         init_threaded_search();
2684
2685         if (delta_search_threads <= 1) {
2686                 find_deltas(list, &list_size, window, depth, processed);
2687                 cleanup_threaded_search();
2688                 return;
2689         }
2690         if (progress > pack_to_stdout)
2691                 fprintf_ln(stderr, _("Delta compression using up to %d threads"),
2692                            delta_search_threads);
2693         CALLOC_ARRAY(p, delta_search_threads);
2694
2695         /* Partition the work amongst work threads. */
2696         for (i = 0; i < delta_search_threads; i++) {
2697                 unsigned sub_size = list_size / (delta_search_threads - i);
2698
2699                 /* don't use too small segments or no deltas will be found */
2700                 if (sub_size < 2*window && i+1 < delta_search_threads)
2701                         sub_size = 0;
2702
2703                 p[i].window = window;
2704                 p[i].depth = depth;
2705                 p[i].processed = processed;
2706                 p[i].working = 1;
2707                 p[i].data_ready = 0;
2708
2709                 /* try to split chunks on "path" boundaries */
2710                 while (sub_size && sub_size < list_size &&
2711                        list[sub_size]->hash &&
2712                        list[sub_size]->hash == list[sub_size-1]->hash)
2713                         sub_size++;
2714
2715                 p[i].list = list;
2716                 p[i].list_size = sub_size;
2717                 p[i].remaining = sub_size;
2718
2719                 list += sub_size;
2720                 list_size -= sub_size;
2721         }
2722
2723         /* Start work threads. */
2724         for (i = 0; i < delta_search_threads; i++) {
2725                 if (!p[i].list_size)
2726                         continue;
2727                 pthread_mutex_init(&p[i].mutex, NULL);
2728                 pthread_cond_init(&p[i].cond, NULL);
2729                 ret = pthread_create(&p[i].thread, NULL,
2730                                      threaded_find_deltas, &p[i]);
2731                 if (ret)
2732                         die(_("unable to create thread: %s"), strerror(ret));
2733                 active_threads++;
2734         }
2735
2736         /*
2737          * Now let's wait for work completion.  Each time a thread is done
2738          * with its work, we steal half of the remaining work from the
2739          * thread with the largest number of unprocessed objects and give
2740          * it to that newly idle thread.  This ensure good load balancing
2741          * until the remaining object list segments are simply too short
2742          * to be worth splitting anymore.
2743          */
2744         while (active_threads) {
2745                 struct thread_params *target = NULL;
2746                 struct thread_params *victim = NULL;
2747                 unsigned sub_size = 0;
2748
2749                 progress_lock();
2750                 for (;;) {
2751                         for (i = 0; !target && i < delta_search_threads; i++)
2752                                 if (!p[i].working)
2753                                         target = &p[i];
2754                         if (target)
2755                                 break;
2756                         pthread_cond_wait(&progress_cond, &progress_mutex);
2757                 }
2758
2759                 for (i = 0; i < delta_search_threads; i++)
2760                         if (p[i].remaining > 2*window &&
2761                             (!victim || victim->remaining < p[i].remaining))
2762                                 victim = &p[i];
2763                 if (victim) {
2764                         sub_size = victim->remaining / 2;
2765                         list = victim->list + victim->list_size - sub_size;
2766                         while (sub_size && list[0]->hash &&
2767                                list[0]->hash == list[-1]->hash) {
2768                                 list++;
2769                                 sub_size--;
2770                         }
2771                         if (!sub_size) {
2772                                 /*
2773                                  * It is possible for some "paths" to have
2774                                  * so many objects that no hash boundary
2775                                  * might be found.  Let's just steal the
2776                                  * exact half in that case.
2777                                  */
2778                                 sub_size = victim->remaining / 2;
2779                                 list -= sub_size;
2780                         }
2781                         target->list = list;
2782                         victim->list_size -= sub_size;
2783                         victim->remaining -= sub_size;
2784                 }
2785                 target->list_size = sub_size;
2786                 target->remaining = sub_size;
2787                 target->working = 1;
2788                 progress_unlock();
2789
2790                 pthread_mutex_lock(&target->mutex);
2791                 target->data_ready = 1;
2792                 pthread_cond_signal(&target->cond);
2793                 pthread_mutex_unlock(&target->mutex);
2794
2795                 if (!sub_size) {
2796                         pthread_join(target->thread, NULL);
2797                         pthread_cond_destroy(&target->cond);
2798                         pthread_mutex_destroy(&target->mutex);
2799                         active_threads--;
2800                 }
2801         }
2802         cleanup_threaded_search();
2803         free(p);
2804 }
2805
2806 static int obj_is_packed(const struct object_id *oid)
2807 {
2808         return packlist_find(&to_pack, oid) ||
2809                 (reuse_packfile_bitmap &&
2810                  bitmap_walk_contains(bitmap_git, reuse_packfile_bitmap, oid));
2811 }
2812
2813 static void add_tag_chain(const struct object_id *oid)
2814 {
2815         struct tag *tag;
2816
2817         /*
2818          * We catch duplicates already in add_object_entry(), but we'd
2819          * prefer to do this extra check to avoid having to parse the
2820          * tag at all if we already know that it's being packed (e.g., if
2821          * it was included via bitmaps, we would not have parsed it
2822          * previously).
2823          */
2824         if (obj_is_packed(oid))
2825                 return;
2826
2827         tag = lookup_tag(the_repository, oid);
2828         while (1) {
2829                 if (!tag || parse_tag(tag) || !tag->tagged)
2830                         die(_("unable to pack objects reachable from tag %s"),
2831                             oid_to_hex(oid));
2832
2833                 add_object_entry(&tag->object.oid, OBJ_TAG, NULL, 0);
2834
2835                 if (tag->tagged->type != OBJ_TAG)
2836                         return;
2837
2838                 tag = (struct tag *)tag->tagged;
2839         }
2840 }
2841
2842 static int add_ref_tag(const char *tag, const struct object_id *oid, int flag, void *cb_data)
2843 {
2844         struct object_id peeled;
2845
2846         if (!peel_iterated_oid(oid, &peeled) && obj_is_packed(&peeled))
2847                 add_tag_chain(oid);
2848         return 0;
2849 }
2850
2851 static void prepare_pack(int window, int depth)
2852 {
2853         struct object_entry **delta_list;
2854         uint32_t i, nr_deltas;
2855         unsigned n;
2856
2857         if (use_delta_islands)
2858                 resolve_tree_islands(the_repository, progress, &to_pack);
2859
2860         get_object_details();
2861
2862         /*
2863          * If we're locally repacking then we need to be doubly careful
2864          * from now on in order to make sure no stealth corruption gets
2865          * propagated to the new pack.  Clients receiving streamed packs
2866          * should validate everything they get anyway so no need to incur
2867          * the additional cost here in that case.
2868          */
2869         if (!pack_to_stdout)
2870                 do_check_packed_object_crc = 1;
2871
2872         if (!to_pack.nr_objects || !window || !depth)
2873                 return;
2874
2875         ALLOC_ARRAY(delta_list, to_pack.nr_objects);
2876         nr_deltas = n = 0;
2877
2878         for (i = 0; i < to_pack.nr_objects; i++) {
2879                 struct object_entry *entry = to_pack.objects + i;
2880
2881                 if (DELTA(entry))
2882                         /* This happens if we decided to reuse existing
2883                          * delta from a pack.  "reuse_delta &&" is implied.
2884                          */
2885                         continue;
2886
2887                 if (!entry->type_valid ||
2888                     oe_size_less_than(&to_pack, entry, 50))
2889                         continue;
2890
2891                 if (entry->no_try_delta)
2892                         continue;
2893
2894                 if (!entry->preferred_base) {
2895                         nr_deltas++;
2896                         if (oe_type(entry) < 0)
2897                                 die(_("unable to get type of object %s"),
2898                                     oid_to_hex(&entry->idx.oid));
2899                 } else {
2900                         if (oe_type(entry) < 0) {
2901                                 /*
2902                                  * This object is not found, but we
2903                                  * don't have to include it anyway.
2904                                  */
2905                                 continue;
2906                         }
2907                 }
2908
2909                 delta_list[n++] = entry;
2910         }
2911
2912         if (nr_deltas && n > 1) {
2913                 unsigned nr_done = 0;
2914
2915                 if (progress)
2916                         progress_state = start_progress(_("Compressing objects"),
2917                                                         nr_deltas);
2918                 QSORT(delta_list, n, type_size_sort);
2919                 ll_find_deltas(delta_list, n, window+1, depth, &nr_done);
2920                 stop_progress(&progress_state);
2921                 if (nr_done != nr_deltas)
2922                         die(_("inconsistency with delta count"));
2923         }
2924         free(delta_list);
2925 }
2926
2927 static int git_pack_config(const char *k, const char *v, void *cb)
2928 {
2929         if (!strcmp(k, "pack.window")) {
2930                 window = git_config_int(k, v);
2931                 return 0;
2932         }
2933         if (!strcmp(k, "pack.windowmemory")) {
2934                 window_memory_limit = git_config_ulong(k, v);
2935                 return 0;
2936         }
2937         if (!strcmp(k, "pack.depth")) {
2938                 depth = git_config_int(k, v);
2939                 return 0;
2940         }
2941         if (!strcmp(k, "pack.deltacachesize")) {
2942                 max_delta_cache_size = git_config_int(k, v);
2943                 return 0;
2944         }
2945         if (!strcmp(k, "pack.deltacachelimit")) {
2946                 cache_max_small_delta_size = git_config_int(k, v);
2947                 return 0;
2948         }
2949         if (!strcmp(k, "pack.writebitmaphashcache")) {
2950                 if (git_config_bool(k, v))
2951                         write_bitmap_options |= BITMAP_OPT_HASH_CACHE;
2952                 else
2953                         write_bitmap_options &= ~BITMAP_OPT_HASH_CACHE;
2954         }
2955         if (!strcmp(k, "pack.usebitmaps")) {
2956                 use_bitmap_index_default = git_config_bool(k, v);
2957                 return 0;
2958         }
2959         if (!strcmp(k, "pack.allowpackreuse")) {
2960                 allow_pack_reuse = git_config_bool(k, v);
2961                 return 0;
2962         }
2963         if (!strcmp(k, "pack.threads")) {
2964                 delta_search_threads = git_config_int(k, v);
2965                 if (delta_search_threads < 0)
2966                         die(_("invalid number of threads specified (%d)"),
2967                             delta_search_threads);
2968                 if (!HAVE_THREADS && delta_search_threads != 1) {
2969                         warning(_("no threads support, ignoring %s"), k);
2970                         delta_search_threads = 0;
2971                 }
2972                 return 0;
2973         }
2974         if (!strcmp(k, "pack.indexversion")) {
2975                 pack_idx_opts.version = git_config_int(k, v);
2976                 if (pack_idx_opts.version > 2)
2977                         die(_("bad pack.indexversion=%"PRIu32),
2978                             pack_idx_opts.version);
2979                 return 0;
2980         }
2981         if (!strcmp(k, "pack.writereverseindex")) {
2982                 if (git_config_bool(k, v))
2983                         pack_idx_opts.flags |= WRITE_REV;
2984                 else
2985                         pack_idx_opts.flags &= ~WRITE_REV;
2986                 return 0;
2987         }
2988         if (!strcmp(k, "uploadpack.blobpackfileuri")) {
2989                 struct configured_exclusion *ex = xmalloc(sizeof(*ex));
2990                 const char *oid_end, *pack_end;
2991                 /*
2992                  * Stores the pack hash. This is not a true object ID, but is
2993                  * of the same form.
2994                  */
2995                 struct object_id pack_hash;
2996
2997                 if (parse_oid_hex(v, &ex->e.oid, &oid_end) ||
2998                     *oid_end != ' ' ||
2999                     parse_oid_hex(oid_end + 1, &pack_hash, &pack_end) ||
3000                     *pack_end != ' ')
3001                         die(_("value of uploadpack.blobpackfileuri must be "
3002                               "of the form '<object-hash> <pack-hash> <uri>' (got '%s')"), v);
3003                 if (oidmap_get(&configured_exclusions, &ex->e.oid))
3004                         die(_("object already configured in another "
3005                               "uploadpack.blobpackfileuri (got '%s')"), v);
3006                 ex->pack_hash_hex = xcalloc(1, pack_end - oid_end);
3007                 memcpy(ex->pack_hash_hex, oid_end + 1, pack_end - oid_end - 1);
3008                 ex->uri = xstrdup(pack_end + 1);
3009                 oidmap_put(&configured_exclusions, ex);
3010         }
3011         return git_default_config(k, v, cb);
3012 }
3013
3014 /* Counters for trace2 output when in --stdin-packs mode. */
3015 static int stdin_packs_found_nr;
3016 static int stdin_packs_hints_nr;
3017
3018 static int add_object_entry_from_pack(const struct object_id *oid,
3019                                       struct packed_git *p,
3020                                       uint32_t pos,
3021                                       void *_data)
3022 {
3023         struct rev_info *revs = _data;
3024         struct object_info oi = OBJECT_INFO_INIT;
3025         off_t ofs;
3026         enum object_type type;
3027
3028         display_progress(progress_state, ++nr_seen);
3029
3030         if (have_duplicate_entry(oid, 0))
3031                 return 0;
3032
3033         ofs = nth_packed_object_offset(p, pos);
3034         if (!want_object_in_pack(oid, 0, &p, &ofs))
3035                 return 0;
3036
3037         oi.typep = &type;
3038         if (packed_object_info(the_repository, p, ofs, &oi) < 0)
3039                 die(_("could not get type of object %s in pack %s"),
3040                     oid_to_hex(oid), p->pack_name);
3041         else if (type == OBJ_COMMIT) {
3042                 /*
3043                  * commits in included packs are used as starting points for the
3044                  * subsequent revision walk
3045                  */
3046                 add_pending_oid(revs, NULL, oid, 0);
3047         }
3048
3049         stdin_packs_found_nr++;
3050
3051         create_object_entry(oid, type, 0, 0, 0, p, ofs);
3052
3053         return 0;
3054 }
3055
3056 static void show_commit_pack_hint(struct commit *commit, void *_data)
3057 {
3058         /* nothing to do; commits don't have a namehash */
3059 }
3060
3061 static void show_object_pack_hint(struct object *object, const char *name,
3062                                   void *_data)
3063 {
3064         struct object_entry *oe = packlist_find(&to_pack, &object->oid);
3065         if (!oe)
3066                 return;
3067
3068         /*
3069          * Our 'to_pack' list was constructed by iterating all objects packed in
3070          * included packs, and so doesn't have a non-zero hash field that you
3071          * would typically pick up during a reachability traversal.
3072          *
3073          * Make a best-effort attempt to fill in the ->hash and ->no_try_delta
3074          * here using a now in order to perhaps improve the delta selection
3075          * process.
3076          */
3077         oe->hash = pack_name_hash(name);
3078         oe->no_try_delta = name && no_try_delta(name);
3079
3080         stdin_packs_hints_nr++;
3081 }
3082
3083 static int pack_mtime_cmp(const void *_a, const void *_b)
3084 {
3085         struct packed_git *a = ((const struct string_list_item*)_a)->util;
3086         struct packed_git *b = ((const struct string_list_item*)_b)->util;
3087
3088         /*
3089          * order packs by descending mtime so that objects are laid out
3090          * roughly as newest-to-oldest
3091          */
3092         if (a->mtime < b->mtime)
3093                 return 1;
3094         else if (b->mtime < a->mtime)
3095                 return -1;
3096         else
3097                 return 0;
3098 }
3099
3100 static void read_packs_list_from_stdin(void)
3101 {
3102         struct strbuf buf = STRBUF_INIT;
3103         struct string_list include_packs = STRING_LIST_INIT_DUP;
3104         struct string_list exclude_packs = STRING_LIST_INIT_DUP;
3105         struct string_list_item *item = NULL;
3106
3107         struct packed_git *p;
3108         struct rev_info revs;
3109
3110         repo_init_revisions(the_repository, &revs, NULL);
3111         /*
3112          * Use a revision walk to fill in the namehash of objects in the include
3113          * packs. To save time, we'll avoid traversing through objects that are
3114          * in excluded packs.
3115          *
3116          * That may cause us to avoid populating all of the namehash fields of
3117          * all included objects, but our goal is best-effort, since this is only
3118          * an optimization during delta selection.
3119          */
3120         revs.no_kept_objects = 1;
3121         revs.keep_pack_cache_flags |= IN_CORE_KEEP_PACKS;
3122         revs.blob_objects = 1;
3123         revs.tree_objects = 1;
3124         revs.tag_objects = 1;
3125         revs.ignore_missing_links = 1;
3126
3127         while (strbuf_getline(&buf, stdin) != EOF) {
3128                 if (!buf.len)
3129                         continue;
3130
3131                 if (*buf.buf == '^')
3132                         string_list_append(&exclude_packs, buf.buf + 1);
3133                 else
3134                         string_list_append(&include_packs, buf.buf);
3135
3136                 strbuf_reset(&buf);
3137         }
3138
3139         string_list_sort(&include_packs);
3140         string_list_sort(&exclude_packs);
3141
3142         for (p = get_all_packs(the_repository); p; p = p->next) {
3143                 const char *pack_name = pack_basename(p);
3144
3145                 item = string_list_lookup(&include_packs, pack_name);
3146                 if (!item)
3147                         item = string_list_lookup(&exclude_packs, pack_name);
3148
3149                 if (item)
3150                         item->util = p;
3151         }
3152
3153         /*
3154          * First handle all of the excluded packs, marking them as kept in-core
3155          * so that later calls to add_object_entry() discards any objects that
3156          * are also found in excluded packs.
3157          */
3158         for_each_string_list_item(item, &exclude_packs) {
3159                 struct packed_git *p = item->util;
3160                 if (!p)
3161                         die(_("could not find pack '%s'"), item->string);
3162                 p->pack_keep_in_core = 1;
3163         }
3164
3165         /*
3166          * Order packs by ascending mtime; use QSORT directly to access the
3167          * string_list_item's ->util pointer, which string_list_sort() does not
3168          * provide.
3169          */
3170         QSORT(include_packs.items, include_packs.nr, pack_mtime_cmp);
3171
3172         for_each_string_list_item(item, &include_packs) {
3173                 struct packed_git *p = item->util;
3174                 if (!p)
3175                         die(_("could not find pack '%s'"), item->string);
3176                 for_each_object_in_pack(p,
3177                                         add_object_entry_from_pack,
3178                                         &revs,
3179                                         FOR_EACH_OBJECT_PACK_ORDER);
3180         }
3181
3182         if (prepare_revision_walk(&revs))
3183                 die(_("revision walk setup failed"));
3184         traverse_commit_list(&revs,
3185                              show_commit_pack_hint,
3186                              show_object_pack_hint,
3187                              NULL);
3188
3189         trace2_data_intmax("pack-objects", the_repository, "stdin_packs_found",
3190                            stdin_packs_found_nr);
3191         trace2_data_intmax("pack-objects", the_repository, "stdin_packs_hints",
3192                            stdin_packs_hints_nr);
3193
3194         strbuf_release(&buf);
3195         string_list_clear(&include_packs, 0);
3196         string_list_clear(&exclude_packs, 0);
3197 }
3198
3199 static void read_object_list_from_stdin(void)
3200 {
3201         char line[GIT_MAX_HEXSZ + 1 + PATH_MAX + 2];
3202         struct object_id oid;
3203         const char *p;
3204
3205         for (;;) {
3206                 if (!fgets(line, sizeof(line), stdin)) {
3207                         if (feof(stdin))
3208                                 break;
3209                         if (!ferror(stdin))
3210                                 die("BUG: fgets returned NULL, not EOF, not error!");
3211                         if (errno != EINTR)
3212                                 die_errno("fgets");
3213                         clearerr(stdin);
3214                         continue;
3215                 }
3216                 if (line[0] == '-') {
3217                         if (get_oid_hex(line+1, &oid))
3218                                 die(_("expected edge object ID, got garbage:\n %s"),
3219                                     line);
3220                         add_preferred_base(&oid);
3221                         continue;
3222                 }
3223                 if (parse_oid_hex(line, &oid, &p))
3224                         die(_("expected object ID, got garbage:\n %s"), line);
3225
3226                 add_preferred_base_object(p + 1);
3227                 add_object_entry(&oid, OBJ_NONE, p + 1, 0);
3228         }
3229 }
3230
3231 /* Remember to update object flag allocation in object.h */
3232 #define OBJECT_ADDED (1u<<20)
3233
3234 static void show_commit(struct commit *commit, void *data)
3235 {
3236         add_object_entry(&commit->object.oid, OBJ_COMMIT, NULL, 0);
3237         commit->object.flags |= OBJECT_ADDED;
3238
3239         if (write_bitmap_index)
3240                 index_commit_for_bitmap(commit);
3241
3242         if (use_delta_islands)
3243                 propagate_island_marks(commit);
3244 }
3245
3246 static void show_object(struct object *obj, const char *name, void *data)
3247 {
3248         add_preferred_base_object(name);
3249         add_object_entry(&obj->oid, obj->type, name, 0);
3250         obj->flags |= OBJECT_ADDED;
3251
3252         if (use_delta_islands) {
3253                 const char *p;
3254                 unsigned depth;
3255                 struct object_entry *ent;
3256
3257                 /* the empty string is a root tree, which is depth 0 */
3258                 depth = *name ? 1 : 0;
3259                 for (p = strchr(name, '/'); p; p = strchr(p + 1, '/'))
3260                         depth++;
3261
3262                 ent = packlist_find(&to_pack, &obj->oid);
3263                 if (ent && depth > oe_tree_depth(&to_pack, ent))
3264                         oe_set_tree_depth(&to_pack, ent, depth);
3265         }
3266 }
3267
3268 static void show_object__ma_allow_any(struct object *obj, const char *name, void *data)
3269 {
3270         assert(arg_missing_action == MA_ALLOW_ANY);
3271
3272         /*
3273          * Quietly ignore ALL missing objects.  This avoids problems with
3274          * staging them now and getting an odd error later.
3275          */
3276         if (!has_object(the_repository, &obj->oid, 0))
3277                 return;
3278
3279         show_object(obj, name, data);
3280 }
3281
3282 static void show_object__ma_allow_promisor(struct object *obj, const char *name, void *data)
3283 {
3284         assert(arg_missing_action == MA_ALLOW_PROMISOR);
3285
3286         /*
3287          * Quietly ignore EXPECTED missing objects.  This avoids problems with
3288          * staging them now and getting an odd error later.
3289          */
3290         if (!has_object(the_repository, &obj->oid, 0) && is_promisor_object(&obj->oid))
3291                 return;
3292
3293         show_object(obj, name, data);
3294 }
3295
3296 static int option_parse_missing_action(const struct option *opt,
3297                                        const char *arg, int unset)
3298 {
3299         assert(arg);
3300         assert(!unset);
3301
3302         if (!strcmp(arg, "error")) {
3303                 arg_missing_action = MA_ERROR;
3304                 fn_show_object = show_object;
3305                 return 0;
3306         }
3307
3308         if (!strcmp(arg, "allow-any")) {
3309                 arg_missing_action = MA_ALLOW_ANY;
3310                 fetch_if_missing = 0;
3311                 fn_show_object = show_object__ma_allow_any;
3312                 return 0;
3313         }
3314
3315         if (!strcmp(arg, "allow-promisor")) {
3316                 arg_missing_action = MA_ALLOW_PROMISOR;
3317                 fetch_if_missing = 0;
3318                 fn_show_object = show_object__ma_allow_promisor;
3319                 return 0;
3320         }
3321
3322         die(_("invalid value for --missing"));
3323         return 0;
3324 }
3325
3326 static void show_edge(struct commit *commit)
3327 {
3328         add_preferred_base(&commit->object.oid);
3329 }
3330
3331 struct in_pack_object {
3332         off_t offset;
3333         struct object *object;
3334 };
3335
3336 struct in_pack {
3337         unsigned int alloc;
3338         unsigned int nr;
3339         struct in_pack_object *array;
3340 };
3341
3342 static void mark_in_pack_object(struct object *object, struct packed_git *p, struct in_pack *in_pack)
3343 {
3344         in_pack->array[in_pack->nr].offset = find_pack_entry_one(object->oid.hash, p);
3345         in_pack->array[in_pack->nr].object = object;
3346         in_pack->nr++;
3347 }
3348
3349 /*
3350  * Compare the objects in the offset order, in order to emulate the
3351  * "git rev-list --objects" output that produced the pack originally.
3352  */
3353 static int ofscmp(const void *a_, const void *b_)
3354 {
3355         struct in_pack_object *a = (struct in_pack_object *)a_;
3356         struct in_pack_object *b = (struct in_pack_object *)b_;
3357
3358         if (a->offset < b->offset)
3359                 return -1;
3360         else if (a->offset > b->offset)
3361                 return 1;
3362         else
3363                 return oidcmp(&a->object->oid, &b->object->oid);
3364 }
3365
3366 static void add_objects_in_unpacked_packs(void)
3367 {
3368         struct packed_git *p;
3369         struct in_pack in_pack;
3370         uint32_t i;
3371
3372         memset(&in_pack, 0, sizeof(in_pack));
3373
3374         for (p = get_all_packs(the_repository); p; p = p->next) {
3375                 struct object_id oid;
3376                 struct object *o;
3377
3378                 if (!p->pack_local || p->pack_keep || p->pack_keep_in_core)
3379                         continue;
3380                 if (open_pack_index(p))
3381                         die(_("cannot open pack index"));
3382
3383                 ALLOC_GROW(in_pack.array,
3384                            in_pack.nr + p->num_objects,
3385                            in_pack.alloc);
3386
3387                 for (i = 0; i < p->num_objects; i++) {
3388                         nth_packed_object_id(&oid, p, i);
3389                         o = lookup_unknown_object(&oid);
3390                         if (!(o->flags & OBJECT_ADDED))
3391                                 mark_in_pack_object(o, p, &in_pack);
3392                         o->flags |= OBJECT_ADDED;
3393                 }
3394         }
3395
3396         if (in_pack.nr) {
3397                 QSORT(in_pack.array, in_pack.nr, ofscmp);
3398                 for (i = 0; i < in_pack.nr; i++) {
3399                         struct object *o = in_pack.array[i].object;
3400                         add_object_entry(&o->oid, o->type, "", 0);
3401                 }
3402         }
3403         free(in_pack.array);
3404 }
3405
3406 static int add_loose_object(const struct object_id *oid, const char *path,
3407                             void *data)
3408 {
3409         enum object_type type = oid_object_info(the_repository, oid, NULL);
3410
3411         if (type < 0) {
3412                 warning(_("loose object at %s could not be examined"), path);
3413                 return 0;
3414         }
3415
3416         add_object_entry(oid, type, "", 0);
3417         return 0;
3418 }
3419
3420 /*
3421  * We actually don't even have to worry about reachability here.
3422  * add_object_entry will weed out duplicates, so we just add every
3423  * loose object we find.
3424  */
3425 static void add_unreachable_loose_objects(void)
3426 {
3427         for_each_loose_file_in_objdir(get_object_directory(),
3428                                       add_loose_object,
3429                                       NULL, NULL, NULL);
3430 }
3431
3432 static int has_sha1_pack_kept_or_nonlocal(const struct object_id *oid)
3433 {
3434         static struct packed_git *last_found = (void *)1;
3435         struct packed_git *p;
3436
3437         p = (last_found != (void *)1) ? last_found :
3438                                         get_all_packs(the_repository);
3439
3440         while (p) {
3441                 if ((!p->pack_local || p->pack_keep ||
3442                                 p->pack_keep_in_core) &&
3443                         find_pack_entry_one(oid->hash, p)) {
3444                         last_found = p;
3445                         return 1;
3446                 }
3447                 if (p == last_found)
3448                         p = get_all_packs(the_repository);
3449                 else
3450                         p = p->next;
3451                 if (p == last_found)
3452                         p = p->next;
3453         }
3454         return 0;
3455 }
3456
3457 /*
3458  * Store a list of sha1s that are should not be discarded
3459  * because they are either written too recently, or are
3460  * reachable from another object that was.
3461  *
3462  * This is filled by get_object_list.
3463  */
3464 static struct oid_array recent_objects;
3465
3466 static int loosened_object_can_be_discarded(const struct object_id *oid,
3467                                             timestamp_t mtime)
3468 {
3469         if (!unpack_unreachable_expiration)
3470                 return 0;
3471         if (mtime > unpack_unreachable_expiration)
3472                 return 0;
3473         if (oid_array_lookup(&recent_objects, oid) >= 0)
3474                 return 0;
3475         return 1;
3476 }
3477
3478 static void loosen_unused_packed_objects(void)
3479 {
3480         struct packed_git *p;
3481         uint32_t i;
3482         struct object_id oid;
3483
3484         for (p = get_all_packs(the_repository); p; p = p->next) {
3485                 if (!p->pack_local || p->pack_keep || p->pack_keep_in_core)
3486                         continue;
3487
3488                 if (open_pack_index(p))
3489                         die(_("cannot open pack index"));
3490
3491                 for (i = 0; i < p->num_objects; i++) {
3492                         nth_packed_object_id(&oid, p, i);
3493                         if (!packlist_find(&to_pack, &oid) &&
3494                             !has_sha1_pack_kept_or_nonlocal(&oid) &&
3495                             !loosened_object_can_be_discarded(&oid, p->mtime))
3496                                 if (force_object_loose(&oid, p->mtime))
3497                                         die(_("unable to force loose object"));
3498                 }
3499         }
3500 }
3501
3502 /*
3503  * This tracks any options which pack-reuse code expects to be on, or which a
3504  * reader of the pack might not understand, and which would therefore prevent
3505  * blind reuse of what we have on disk.
3506  */
3507 static int pack_options_allow_reuse(void)
3508 {
3509         return allow_pack_reuse &&
3510                pack_to_stdout &&
3511                !ignore_packed_keep_on_disk &&
3512                !ignore_packed_keep_in_core &&
3513                (!local || !have_non_local_packs) &&
3514                !incremental;
3515 }
3516
3517 static int get_object_list_from_bitmap(struct rev_info *revs)
3518 {
3519         if (!(bitmap_git = prepare_bitmap_walk(revs, &filter_options)))
3520                 return -1;
3521
3522         if (pack_options_allow_reuse() &&
3523             !reuse_partial_packfile_from_bitmap(
3524                         bitmap_git,
3525                         &reuse_packfile,
3526                         &reuse_packfile_objects,
3527                         &reuse_packfile_bitmap)) {
3528                 assert(reuse_packfile_objects);
3529                 nr_result += reuse_packfile_objects;
3530                 display_progress(progress_state, nr_result);
3531         }
3532
3533         traverse_bitmap_commit_list(bitmap_git, revs,
3534                                     &add_object_entry_from_bitmap);
3535         return 0;
3536 }
3537
3538 static void record_recent_object(struct object *obj,
3539                                  const char *name,
3540                                  void *data)
3541 {
3542         oid_array_append(&recent_objects, &obj->oid);
3543 }
3544
3545 static void record_recent_commit(struct commit *commit, void *data)
3546 {
3547         oid_array_append(&recent_objects, &commit->object.oid);
3548 }
3549
3550 static void get_object_list(int ac, const char **av)
3551 {
3552         struct rev_info revs;
3553         struct setup_revision_opt s_r_opt = {
3554                 .allow_exclude_promisor_objects = 1,
3555         };
3556         char line[1000];
3557         int flags = 0;
3558         int save_warning;
3559
3560         repo_init_revisions(the_repository, &revs, NULL);
3561         save_commit_buffer = 0;
3562         setup_revisions(ac, av, &revs, &s_r_opt);
3563
3564         /* make sure shallows are read */
3565         is_repository_shallow(the_repository);
3566
3567         save_warning = warn_on_object_refname_ambiguity;
3568         warn_on_object_refname_ambiguity = 0;
3569
3570         while (fgets(line, sizeof(line), stdin) != NULL) {
3571                 int len = strlen(line);
3572                 if (len && line[len - 1] == '\n')
3573                         line[--len] = 0;
3574                 if (!len)
3575                         break;
3576                 if (*line == '-') {
3577                         if (!strcmp(line, "--not")) {
3578                                 flags ^= UNINTERESTING;
3579                                 write_bitmap_index = 0;
3580                                 continue;
3581                         }
3582                         if (starts_with(line, "--shallow ")) {
3583                                 struct object_id oid;
3584                                 if (get_oid_hex(line + 10, &oid))
3585                                         die("not an object name '%s'", line + 10);
3586                                 register_shallow(the_repository, &oid);
3587                                 use_bitmap_index = 0;
3588                                 continue;
3589                         }
3590                         die(_("not a rev '%s'"), line);
3591                 }
3592                 if (handle_revision_arg(line, &revs, flags, REVARG_CANNOT_BE_FILENAME))
3593                         die(_("bad revision '%s'"), line);
3594         }
3595
3596         warn_on_object_refname_ambiguity = save_warning;
3597
3598         if (use_bitmap_index && !get_object_list_from_bitmap(&revs))
3599                 return;
3600
3601         if (use_delta_islands)
3602                 load_delta_islands(the_repository, progress);
3603
3604         if (prepare_revision_walk(&revs))
3605                 die(_("revision walk setup failed"));
3606         mark_edges_uninteresting(&revs, show_edge, sparse);
3607
3608         if (!fn_show_object)
3609                 fn_show_object = show_object;
3610         traverse_commit_list_filtered(&filter_options, &revs,
3611                                       show_commit, fn_show_object, NULL,
3612                                       NULL);
3613
3614         if (unpack_unreachable_expiration) {
3615                 revs.ignore_missing_links = 1;
3616                 if (add_unseen_recent_objects_to_traversal(&revs,
3617                                 unpack_unreachable_expiration))
3618                         die(_("unable to add recent objects"));
3619                 if (prepare_revision_walk(&revs))
3620                         die(_("revision walk setup failed"));
3621                 traverse_commit_list(&revs, record_recent_commit,
3622                                      record_recent_object, NULL);
3623         }
3624
3625         if (keep_unreachable)
3626                 add_objects_in_unpacked_packs();
3627         if (pack_loose_unreachable)
3628                 add_unreachable_loose_objects();
3629         if (unpack_unreachable)
3630                 loosen_unused_packed_objects();
3631
3632         oid_array_clear(&recent_objects);
3633 }
3634
3635 static void add_extra_kept_packs(const struct string_list *names)
3636 {
3637         struct packed_git *p;
3638
3639         if (!names->nr)
3640                 return;
3641
3642         for (p = get_all_packs(the_repository); p; p = p->next) {
3643                 const char *name = basename(p->pack_name);
3644                 int i;
3645
3646                 if (!p->pack_local)
3647                         continue;
3648
3649                 for (i = 0; i < names->nr; i++)
3650                         if (!fspathcmp(name, names->items[i].string))
3651                                 break;
3652
3653                 if (i < names->nr) {
3654                         p->pack_keep_in_core = 1;
3655                         ignore_packed_keep_in_core = 1;
3656                         continue;
3657                 }
3658         }
3659 }
3660
3661 static int option_parse_index_version(const struct option *opt,
3662                                       const char *arg, int unset)
3663 {
3664         char *c;
3665         const char *val = arg;
3666
3667         BUG_ON_OPT_NEG(unset);
3668
3669         pack_idx_opts.version = strtoul(val, &c, 10);
3670         if (pack_idx_opts.version > 2)
3671                 die(_("unsupported index version %s"), val);
3672         if (*c == ',' && c[1])
3673                 pack_idx_opts.off32_limit = strtoul(c+1, &c, 0);
3674         if (*c || pack_idx_opts.off32_limit & 0x80000000)
3675                 die(_("bad index version '%s'"), val);
3676         return 0;
3677 }
3678
3679 static int option_parse_unpack_unreachable(const struct option *opt,
3680                                            const char *arg, int unset)
3681 {
3682         if (unset) {
3683                 unpack_unreachable = 0;
3684                 unpack_unreachable_expiration = 0;
3685         }
3686         else {
3687                 unpack_unreachable = 1;
3688                 if (arg)
3689                         unpack_unreachable_expiration = approxidate(arg);
3690         }
3691         return 0;
3692 }
3693
3694 int cmd_pack_objects(int argc, const char **argv, const char *prefix)
3695 {
3696         int use_internal_rev_list = 0;
3697         int shallow = 0;
3698         int all_progress_implied = 0;
3699         struct strvec rp = STRVEC_INIT;
3700         int rev_list_unpacked = 0, rev_list_all = 0, rev_list_reflog = 0;
3701         int rev_list_index = 0;
3702         int stdin_packs = 0;
3703         struct string_list keep_pack_list = STRING_LIST_INIT_NODUP;
3704         struct option pack_objects_options[] = {
3705                 OPT_SET_INT('q', "quiet", &progress,
3706                             N_("do not show progress meter"), 0),
3707                 OPT_SET_INT(0, "progress", &progress,
3708                             N_("show progress meter"), 1),
3709                 OPT_SET_INT(0, "all-progress", &progress,
3710                             N_("show progress meter during object writing phase"), 2),
3711                 OPT_BOOL(0, "all-progress-implied",
3712                          &all_progress_implied,
3713                          N_("similar to --all-progress when progress meter is shown")),
3714                 OPT_CALLBACK_F(0, "index-version", NULL, N_("<version>[,<offset>]"),
3715                   N_("write the pack index file in the specified idx format version"),
3716                   PARSE_OPT_NONEG, option_parse_index_version),
3717                 OPT_MAGNITUDE(0, "max-pack-size", &pack_size_limit,
3718                               N_("maximum size of each output pack file")),
3719                 OPT_BOOL(0, "local", &local,
3720                          N_("ignore borrowed objects from alternate object store")),
3721                 OPT_BOOL(0, "incremental", &incremental,
3722                          N_("ignore packed objects")),
3723                 OPT_INTEGER(0, "window", &window,
3724                             N_("limit pack window by objects")),
3725                 OPT_MAGNITUDE(0, "window-memory", &window_memory_limit,
3726                               N_("limit pack window by memory in addition to object limit")),
3727                 OPT_INTEGER(0, "depth", &depth,
3728                             N_("maximum length of delta chain allowed in the resulting pack")),
3729                 OPT_BOOL(0, "reuse-delta", &reuse_delta,
3730                          N_("reuse existing deltas")),
3731                 OPT_BOOL(0, "reuse-object", &reuse_object,
3732                          N_("reuse existing objects")),
3733                 OPT_BOOL(0, "delta-base-offset", &allow_ofs_delta,
3734                          N_("use OFS_DELTA objects")),
3735                 OPT_INTEGER(0, "threads", &delta_search_threads,
3736                             N_("use threads when searching for best delta matches")),
3737                 OPT_BOOL(0, "non-empty", &non_empty,
3738                          N_("do not create an empty pack output")),
3739                 OPT_BOOL(0, "revs", &use_internal_rev_list,
3740                          N_("read revision arguments from standard input")),
3741                 OPT_SET_INT_F(0, "unpacked", &rev_list_unpacked,
3742                               N_("limit the objects to those that are not yet packed"),
3743                               1, PARSE_OPT_NONEG),
3744                 OPT_SET_INT_F(0, "all", &rev_list_all,
3745                               N_("include objects reachable from any reference"),
3746                               1, PARSE_OPT_NONEG),
3747                 OPT_SET_INT_F(0, "reflog", &rev_list_reflog,
3748                               N_("include objects referred by reflog entries"),
3749                               1, PARSE_OPT_NONEG),
3750                 OPT_SET_INT_F(0, "indexed-objects", &rev_list_index,
3751                               N_("include objects referred to by the index"),
3752                               1, PARSE_OPT_NONEG),
3753                 OPT_BOOL(0, "stdin-packs", &stdin_packs,
3754                          N_("read packs from stdin")),
3755                 OPT_BOOL(0, "stdout", &pack_to_stdout,
3756                          N_("output pack to stdout")),
3757                 OPT_BOOL(0, "include-tag", &include_tag,
3758                          N_("include tag objects that refer to objects to be packed")),
3759                 OPT_BOOL(0, "keep-unreachable", &keep_unreachable,
3760                          N_("keep unreachable objects")),
3761                 OPT_BOOL(0, "pack-loose-unreachable", &pack_loose_unreachable,
3762                          N_("pack loose unreachable objects")),
3763                 OPT_CALLBACK_F(0, "unpack-unreachable", NULL, N_("time"),
3764                   N_("unpack unreachable objects newer than <time>"),
3765                   PARSE_OPT_OPTARG, option_parse_unpack_unreachable),
3766                 OPT_BOOL(0, "sparse", &sparse,
3767                          N_("use the sparse reachability algorithm")),
3768                 OPT_BOOL(0, "thin", &thin,
3769                          N_("create thin packs")),
3770                 OPT_BOOL(0, "shallow", &shallow,
3771                          N_("create packs suitable for shallow fetches")),
3772                 OPT_BOOL(0, "honor-pack-keep", &ignore_packed_keep_on_disk,
3773                          N_("ignore packs that have companion .keep file")),
3774                 OPT_STRING_LIST(0, "keep-pack", &keep_pack_list, N_("name"),
3775                                 N_("ignore this pack")),
3776                 OPT_INTEGER(0, "compression", &pack_compression_level,
3777                             N_("pack compression level")),
3778                 OPT_SET_INT(0, "keep-true-parents", &grafts_replace_parents,
3779                             N_("do not hide commits by grafts"), 0),
3780                 OPT_BOOL(0, "use-bitmap-index", &use_bitmap_index,
3781                          N_("use a bitmap index if available to speed up counting objects")),
3782                 OPT_SET_INT(0, "write-bitmap-index", &write_bitmap_index,
3783                             N_("write a bitmap index together with the pack index"),
3784                             WRITE_BITMAP_TRUE),
3785                 OPT_SET_INT_F(0, "write-bitmap-index-quiet",
3786                               &write_bitmap_index,
3787                               N_("write a bitmap index if possible"),
3788                               WRITE_BITMAP_QUIET, PARSE_OPT_HIDDEN),
3789                 OPT_PARSE_LIST_OBJECTS_FILTER(&filter_options),
3790                 OPT_CALLBACK_F(0, "missing", NULL, N_("action"),
3791                   N_("handling for missing objects"), PARSE_OPT_NONEG,
3792                   option_parse_missing_action),
3793                 OPT_BOOL(0, "exclude-promisor-objects", &exclude_promisor_objects,
3794                          N_("do not pack objects in promisor packfiles")),
3795                 OPT_BOOL(0, "delta-islands", &use_delta_islands,
3796                          N_("respect islands during delta compression")),
3797                 OPT_STRING_LIST(0, "uri-protocol", &uri_protocols,
3798                                 N_("protocol"),
3799                                 N_("exclude any configured uploadpack.blobpackfileuri with this protocol")),
3800                 OPT_END(),
3801         };
3802
3803         if (DFS_NUM_STATES > (1 << OE_DFS_STATE_BITS))
3804                 BUG("too many dfs states, increase OE_DFS_STATE_BITS");
3805
3806         read_replace_refs = 0;
3807
3808         sparse = git_env_bool("GIT_TEST_PACK_SPARSE", -1);
3809         prepare_repo_settings(the_repository);
3810         if (sparse < 0)
3811                 sparse = the_repository->settings.pack_use_sparse;
3812
3813         reset_pack_idx_option(&pack_idx_opts);
3814         git_config(git_pack_config, NULL);
3815         if (git_env_bool(GIT_TEST_WRITE_REV_INDEX, 0))
3816                 pack_idx_opts.flags |= WRITE_REV;
3817
3818         progress = isatty(2);
3819         argc = parse_options(argc, argv, prefix, pack_objects_options,
3820                              pack_usage, 0);
3821
3822         if (argc) {
3823                 base_name = argv[0];
3824                 argc--;
3825         }
3826         if (pack_to_stdout != !base_name || argc)
3827                 usage_with_options(pack_usage, pack_objects_options);
3828
3829         if (depth >= (1 << OE_DEPTH_BITS)) {
3830                 warning(_("delta chain depth %d is too deep, forcing %d"),
3831                         depth, (1 << OE_DEPTH_BITS) - 1);
3832                 depth = (1 << OE_DEPTH_BITS) - 1;
3833         }
3834         if (cache_max_small_delta_size >= (1U << OE_Z_DELTA_BITS)) {
3835                 warning(_("pack.deltaCacheLimit is too high, forcing %d"),
3836                         (1U << OE_Z_DELTA_BITS) - 1);
3837                 cache_max_small_delta_size = (1U << OE_Z_DELTA_BITS) - 1;
3838         }
3839
3840         strvec_push(&rp, "pack-objects");
3841         if (thin) {
3842                 use_internal_rev_list = 1;
3843                 strvec_push(&rp, shallow
3844                                 ? "--objects-edge-aggressive"
3845                                 : "--objects-edge");
3846         } else
3847                 strvec_push(&rp, "--objects");
3848
3849         if (rev_list_all) {
3850                 use_internal_rev_list = 1;
3851                 strvec_push(&rp, "--all");
3852         }
3853         if (rev_list_reflog) {
3854                 use_internal_rev_list = 1;
3855                 strvec_push(&rp, "--reflog");
3856         }
3857         if (rev_list_index) {
3858                 use_internal_rev_list = 1;
3859                 strvec_push(&rp, "--indexed-objects");
3860         }
3861         if (rev_list_unpacked && !stdin_packs) {
3862                 use_internal_rev_list = 1;
3863                 strvec_push(&rp, "--unpacked");
3864         }
3865
3866         if (exclude_promisor_objects) {
3867                 use_internal_rev_list = 1;
3868                 fetch_if_missing = 0;
3869                 strvec_push(&rp, "--exclude-promisor-objects");
3870         }
3871         if (unpack_unreachable || keep_unreachable || pack_loose_unreachable)
3872                 use_internal_rev_list = 1;
3873
3874         if (!reuse_object)
3875                 reuse_delta = 0;
3876         if (pack_compression_level == -1)
3877                 pack_compression_level = Z_DEFAULT_COMPRESSION;
3878         else if (pack_compression_level < 0 || pack_compression_level > Z_BEST_COMPRESSION)
3879                 die(_("bad pack compression level %d"), pack_compression_level);
3880
3881         if (!delta_search_threads)      /* --threads=0 means autodetect */
3882                 delta_search_threads = online_cpus();
3883
3884         if (!HAVE_THREADS && delta_search_threads != 1)
3885                 warning(_("no threads support, ignoring --threads"));
3886         if (!pack_to_stdout && !pack_size_limit)
3887                 pack_size_limit = pack_size_limit_cfg;
3888         if (pack_to_stdout && pack_size_limit)
3889                 die(_("--max-pack-size cannot be used to build a pack for transfer"));
3890         if (pack_size_limit && pack_size_limit < 1024*1024) {
3891                 warning(_("minimum pack size limit is 1 MiB"));
3892                 pack_size_limit = 1024*1024;
3893         }
3894
3895         if (!pack_to_stdout && thin)
3896                 die(_("--thin cannot be used to build an indexable pack"));
3897
3898         if (keep_unreachable && unpack_unreachable)
3899                 die(_("--keep-unreachable and --unpack-unreachable are incompatible"));
3900         if (!rev_list_all || !rev_list_reflog || !rev_list_index)
3901                 unpack_unreachable_expiration = 0;
3902
3903         if (filter_options.choice) {
3904                 if (!pack_to_stdout)
3905                         die(_("cannot use --filter without --stdout"));
3906                 if (stdin_packs)
3907                         die(_("cannot use --filter with --stdin-packs"));
3908         }
3909
3910         if (stdin_packs && use_internal_rev_list)
3911                 die(_("cannot use internal rev list with --stdin-packs"));
3912
3913         /*
3914          * "soft" reasons not to use bitmaps - for on-disk repack by default we want
3915          *
3916          * - to produce good pack (with bitmap index not-yet-packed objects are
3917          *   packed in suboptimal order).
3918          *
3919          * - to use more robust pack-generation codepath (avoiding possible
3920          *   bugs in bitmap code and possible bitmap index corruption).
3921          */
3922         if (!pack_to_stdout)
3923                 use_bitmap_index_default = 0;
3924
3925         if (use_bitmap_index < 0)
3926                 use_bitmap_index = use_bitmap_index_default;
3927
3928         /* "hard" reasons not to use bitmaps; these just won't work at all */
3929         if (!use_internal_rev_list || (!pack_to_stdout && write_bitmap_index) || is_repository_shallow(the_repository))
3930                 use_bitmap_index = 0;
3931
3932         if (pack_to_stdout || !rev_list_all)
3933                 write_bitmap_index = 0;
3934
3935         if (use_delta_islands)
3936                 strvec_push(&rp, "--topo-order");
3937
3938         if (progress && all_progress_implied)
3939                 progress = 2;
3940
3941         add_extra_kept_packs(&keep_pack_list);
3942         if (ignore_packed_keep_on_disk) {
3943                 struct packed_git *p;
3944                 for (p = get_all_packs(the_repository); p; p = p->next)
3945                         if (p->pack_local && p->pack_keep)
3946                                 break;
3947                 if (!p) /* no keep-able packs found */
3948                         ignore_packed_keep_on_disk = 0;
3949         }
3950         if (local) {
3951                 /*
3952                  * unlike ignore_packed_keep_on_disk above, we do not
3953                  * want to unset "local" based on looking at packs, as
3954                  * it also covers non-local objects
3955                  */
3956                 struct packed_git *p;
3957                 for (p = get_all_packs(the_repository); p; p = p->next) {
3958                         if (!p->pack_local) {
3959                                 have_non_local_packs = 1;
3960                                 break;
3961                         }
3962                 }
3963         }
3964
3965         trace2_region_enter("pack-objects", "enumerate-objects",
3966                             the_repository);
3967         prepare_packing_data(the_repository, &to_pack);
3968
3969         if (progress)
3970                 progress_state = start_progress(_("Enumerating objects"), 0);
3971         if (stdin_packs) {
3972                 /* avoids adding objects in excluded packs */
3973                 ignore_packed_keep_in_core = 1;
3974                 read_packs_list_from_stdin();
3975                 if (rev_list_unpacked)
3976                         add_unreachable_loose_objects();
3977         } else if (!use_internal_rev_list)
3978                 read_object_list_from_stdin();
3979         else {
3980                 get_object_list(rp.nr, rp.v);
3981                 strvec_clear(&rp);
3982         }
3983         cleanup_preferred_base();
3984         if (include_tag && nr_result)
3985                 for_each_tag_ref(add_ref_tag, NULL);
3986         stop_progress(&progress_state);
3987         trace2_region_leave("pack-objects", "enumerate-objects",
3988                             the_repository);
3989
3990         if (non_empty && !nr_result)
3991                 return 0;
3992         if (nr_result) {
3993                 trace2_region_enter("pack-objects", "prepare-pack",
3994                                     the_repository);
3995                 prepare_pack(window, depth);
3996                 trace2_region_leave("pack-objects", "prepare-pack",
3997                                     the_repository);
3998         }
3999
4000         trace2_region_enter("pack-objects", "write-pack-file", the_repository);
4001         write_excluded_by_configs();
4002         write_pack_file();
4003         trace2_region_leave("pack-objects", "write-pack-file", the_repository);
4004
4005         if (progress)
4006                 fprintf_ln(stderr,
4007                            _("Total %"PRIu32" (delta %"PRIu32"),"
4008                              " reused %"PRIu32" (delta %"PRIu32"),"
4009                              " pack-reused %"PRIu32),
4010                            written, written_delta, reused, reused_delta,
4011                            reuse_packfile_objects);
4012         return 0;
4013 }