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

   1 #include "builtin.h"
   2 #include "cache.h"
   3 #include "object.h"
   4 #include "blob.h"
   5 #include "commit.h"
   6 #include "tag.h"
   7 #include "tree.h"
   8 #include "delta.h"
   9 #include "pack.h"
  10 #include "csum-file.h"
  11 #include "tree-walk.h"
  12 #include "diff.h"
  13 #include "revision.h"
  14 #include "list-objects.h"
  15 #include "progress.h"
  16
  17 static const char pack_usage[] = "\
  18 git-pack-objects [{ -q | --progress | --all-progress }] [--max-pack-size=N] \n\
  19         [--local] [--incremental] [--window=N] [--depth=N] \n\
  20         [--no-reuse-delta] [--no-reuse-object] [--delta-base-offset] \n\
  21         [--non-empty] [--revs [--unpacked | --all]*] [--reflog] \n\
  22         [--stdout | base-name] [<ref-list | <object-list]";
  23
  24 struct object_entry {
  25         unsigned char sha1[20];
  26         uint32_t crc32;         /* crc of raw pack data for this object */
  27         off_t offset;           /* offset into the final pack file */
  28         unsigned long size;     /* uncompressed size */
  29         unsigned int hash;      /* name hint hash */
  30         unsigned int depth;     /* delta depth */
  31         struct packed_git *in_pack;     /* already in pack */
  32         off_t in_pack_offset;
  33         struct object_entry *delta;     /* delta base object */
  34         struct object_entry *delta_child; /* deltified objects who bases me */
  35         struct object_entry *delta_sibling; /* other deltified objects who
  36                                              * uses the same base as me
  37                                              */
  38         unsigned long delta_size;       /* delta data size (uncompressed) */
  39         enum object_type type;
  40         enum object_type in_pack_type;  /* could be delta */
  41         unsigned char in_pack_header_size;
  42         unsigned char preferred_base; /* we do not pack this, but is available
  43                                        * to be used as the base objectto delta
  44                                        * objects against.
  45                                        */
  46 };
  47
  48 /*
  49  * Objects we are going to pack are collected in objects array (dynamically
  50  * expanded).  nr_objects & nr_alloc controls this array.  They are stored
  51  * in the order we see -- typically rev-list --objects order that gives us
  52  * nice "minimum seek" order.
  53  */
  54 static struct object_entry *objects;
  55 static struct object_entry **written_list;
  56 static uint32_t nr_objects, nr_alloc, nr_result, nr_written;
  57
  58 static int non_empty;
  59 static int no_reuse_delta, no_reuse_object;
  60 static int local;
  61 static int incremental;
  62 static int allow_ofs_delta;
  63 static const char *pack_tmp_name, *idx_tmp_name;
  64 static char tmpname[PATH_MAX];
  65 static const char *base_name;
  66 static unsigned char pack_file_sha1[20];
  67 static int progress = 1;
  68 static int window = 10;
  69 static uint32_t pack_size_limit;
  70 static int depth = 50;
  71 static int pack_to_stdout;
  72 static int num_preferred_base;
  73 static struct progress progress_state;
  74 static int pack_compression_level = Z_DEFAULT_COMPRESSION;
  75 static int pack_compression_seen;
  76
  77 /*
  78  * The object names in objects array are hashed with this hashtable,
  79  * to help looking up the entry by object name.
  80  * This hashtable is built after all the objects are seen.
  81  */
  82 static int *object_ix;
  83 static int object_ix_hashsz;
  84
  85 /*
  86  * Pack index for existing packs give us easy access to the offsets into
  87  * corresponding pack file where each object's data starts, but the entries
  88  * do not store the size of the compressed representation (uncompressed
  89  * size is easily available by examining the pack entry header).  It is
  90  * also rather expensive to find the sha1 for an object given its offset.
  91  *
  92  * We build a hashtable of existing packs (pack_revindex), and keep reverse
  93  * index here -- pack index file is sorted by object name mapping to offset;
  94  * this pack_revindex[].revindex array is a list of offset/index_nr pairs
  95  * ordered by offset, so if you know the offset of an object, next offset
  96  * is where its packed representation ends and the index_nr can be used to
  97  * get the object sha1 from the main index.
  98  */
  99 struct revindex_entry {
 100         off_t offset;
 101         unsigned int nr;
 102 };
 103 struct pack_revindex {
 104         struct packed_git *p;
 105         struct revindex_entry *revindex;
 106 };
 107 static struct  pack_revindex *pack_revindex;
 108 static int pack_revindex_hashsz;
 109
 110 /*
 111  * stats
 112  */
 113 static uint32_t written, written_delta;
 114 static uint32_t reused, reused_delta;
 115
 116 static int pack_revindex_ix(struct packed_git *p)
 117 {
 118         unsigned long ui = (unsigned long)p;
 119         int i;
 120
 121         ui = ui ^ (ui >> 16); /* defeat structure alignment */
 122         i = (int)(ui % pack_revindex_hashsz);
 123         while (pack_revindex[i].p) {
 124                 if (pack_revindex[i].p == p)
 125                         return i;
 126                 if (++i == pack_revindex_hashsz)
 127                         i = 0;
 128         }
 129         return -1 - i;
 130 }
 131
 132 static void prepare_pack_ix(void)
 133 {
 134         int num;
 135         struct packed_git *p;
 136         for (num = 0, p = packed_git; p; p = p->next)
 137                 num++;
 138         if (!num)
 139                 return;
 140         pack_revindex_hashsz = num * 11;
 141         pack_revindex = xcalloc(sizeof(*pack_revindex), pack_revindex_hashsz);
 142         for (p = packed_git; p; p = p->next) {
 143                 num = pack_revindex_ix(p);
 144                 num = - 1 - num;
 145                 pack_revindex[num].p = p;
 146         }
 147         /* revindex elements are lazily initialized */
 148 }
 149
 150 static int cmp_offset(const void *a_, const void *b_)
 151 {
 152         const struct revindex_entry *a = a_;
 153         const struct revindex_entry *b = b_;
 154         return (a->offset < b->offset) ? -1 : (a->offset > b->offset) ? 1 : 0;
 155 }
 156
 157 /*
 158  * Ordered list of offsets of objects in the pack.
 159  */
 160 static void prepare_pack_revindex(struct pack_revindex *rix)
 161 {
 162         struct packed_git *p = rix->p;
 163         int num_ent = p->num_objects;
 164         int i;
 165         const char *index = p->index_data;
 166
 167         rix->revindex = xmalloc(sizeof(*rix->revindex) * (num_ent + 1));
 168         index += 4 * 256;
 169
 170         if (p->index_version > 1) {
 171                 const uint32_t *off_32 =
 172                         (uint32_t *)(index + 8 + p->num_objects * (20 + 4));
 173                 const uint32_t *off_64 = off_32 + p->num_objects;
 174                 for (i = 0; i < num_ent; i++) {
 175                         uint32_t off = ntohl(*off_32++);
 176                         if (!(off & 0x80000000)) {
 177                                 rix->revindex[i].offset = off;
 178                         } else {
 179                                 rix->revindex[i].offset =
 180                                         ((uint64_t)ntohl(*off_64++)) << 32;
 181                                 rix->revindex[i].offset |=
 182                                         ntohl(*off_64++);
 183                         }
 184                         rix->revindex[i].nr = i;
 185                 }
 186         } else {
 187                 for (i = 0; i < num_ent; i++) {
 188                         uint32_t hl = *((uint32_t *)(index + 24 * i));
 189                         rix->revindex[i].offset = ntohl(hl);
 190                         rix->revindex[i].nr = i;
 191                 }
 192         }
 193
 194         /* This knows the pack format -- the 20-byte trailer
 195          * follows immediately after the last object data.
 196          */
 197         rix->revindex[num_ent].offset = p->pack_size - 20;
 198         rix->revindex[num_ent].nr = -1;
 199         qsort(rix->revindex, num_ent, sizeof(*rix->revindex), cmp_offset);
 200 }
 201
 202 static struct revindex_entry * find_packed_object(struct packed_git *p,
 203                                                   off_t ofs)
 204 {
 205         int num;
 206         int lo, hi;
 207         struct pack_revindex *rix;
 208         struct revindex_entry *revindex;
 209         num = pack_revindex_ix(p);
 210         if (num < 0)
 211                 die("internal error: pack revindex uninitialized");
 212         rix = &pack_revindex[num];
 213         if (!rix->revindex)
 214                 prepare_pack_revindex(rix);
 215         revindex = rix->revindex;
 216         lo = 0;
 217         hi = p->num_objects + 1;
 218         do {
 219                 int mi = (lo + hi) / 2;
 220                 if (revindex[mi].offset == ofs) {
 221                         return revindex + mi;
 222                 }
 223                 else if (ofs < revindex[mi].offset)
 224                         hi = mi;
 225                 else
 226                         lo = mi + 1;
 227         } while (lo < hi);
 228         die("internal error: pack revindex corrupt");
 229 }
 230
 231 static const unsigned char *find_packed_object_name(struct packed_git *p,
 232                                                     off_t ofs)
 233 {
 234         struct revindex_entry *entry = find_packed_object(p, ofs);
 235         return nth_packed_object_sha1(p, entry->nr);
 236 }
 237
 238 static void *delta_against(void *buf, unsigned long size, struct object_entry *entry)
 239 {
 240         unsigned long othersize, delta_size;
 241         enum object_type type;
 242         void *otherbuf = read_sha1_file(entry->delta->sha1, &type, &othersize);
 243         void *delta_buf;
 244
 245         if (!otherbuf)
 246                 die("unable to read %s", sha1_to_hex(entry->delta->sha1));
 247         delta_buf = diff_delta(otherbuf, othersize,
 248                                buf, size, &delta_size, 0);
 249         if (!delta_buf || delta_size != entry->delta_size)
 250                 die("delta size changed");
 251         free(buf);
 252         free(otherbuf);
 253         return delta_buf;
 254 }
 255
 256 /*
 257  * The per-object header is a pretty dense thing, which is
 258  *  - first byte: low four bits are "size", then three bits of "type",
 259  *    and the high bit is "size continues".
 260  *  - each byte afterwards: low seven bits are size continuation,
 261  *    with the high bit being "size continues"
 262  */
 263 static int encode_header(enum object_type type, unsigned long size, unsigned char *hdr)
 264 {
 265         int n = 1;
 266         unsigned char c;
 267
 268         if (type < OBJ_COMMIT || type > OBJ_REF_DELTA)
 269                 die("bad type %d", type);
 270
 271         c = (type << 4) | (size & 15);
 272         size >>= 4;
 273         while (size) {
 274                 *hdr++ = c | 0x80;
 275                 c = size & 0x7f;
 276                 size >>= 7;
 277                 n++;
 278         }
 279         *hdr = c;
 280         return n;
 281 }
 282
 283 /*
 284  * we are going to reuse the existing object data as is.  make
 285  * sure it is not corrupt.
 286  */
 287 static int check_pack_inflate(struct packed_git *p,
 288                 struct pack_window **w_curs,
 289                 off_t offset,
 290                 off_t len,
 291                 unsigned long expect)
 292 {
 293         z_stream stream;
 294         unsigned char fakebuf[4096], *in;
 295         int st;
 296
 297         memset(&stream, 0, sizeof(stream));
 298         inflateInit(&stream);
 299         do {
 300                 in = use_pack(p, w_curs, offset, &stream.avail_in);
 301                 stream.next_in = in;
 302                 stream.next_out = fakebuf;
 303                 stream.avail_out = sizeof(fakebuf);
 304                 st = inflate(&stream, Z_FINISH);
 305                 offset += stream.next_in - in;
 306         } while (st == Z_OK || st == Z_BUF_ERROR);
 307         inflateEnd(&stream);
 308         return (st == Z_STREAM_END &&
 309                 stream.total_out == expect &&
 310                 stream.total_in == len) ? 0 : -1;
 311 }
 312
 313 static int check_pack_crc(struct packed_git *p, struct pack_window **w_curs,
 314                           off_t offset, off_t len, unsigned int nr)
 315 {
 316         const uint32_t *index_crc;
 317         uint32_t data_crc = crc32(0, Z_NULL, 0);
 318
 319         do {
 320                 unsigned int avail;
 321                 void *data = use_pack(p, w_curs, offset, &avail);
 322                 if (avail > len)
 323                         avail = len;
 324                 data_crc = crc32(data_crc, data, avail);
 325                 offset += avail;
 326                 len -= avail;
 327         } while (len);
 328
 329         index_crc = p->index_data;
 330         index_crc += 2 + 256 + p->num_objects * (20/4) + nr;
 331
 332         return data_crc != ntohl(*index_crc);
 333 }
 334
 335 static void copy_pack_data(struct sha1file *f,
 336                 struct packed_git *p,
 337                 struct pack_window **w_curs,
 338                 off_t offset,
 339                 off_t len)
 340 {
 341         unsigned char *in;
 342         unsigned int avail;
 343
 344         while (len) {
 345                 in = use_pack(p, w_curs, offset, &avail);
 346                 if (avail > len)
 347                         avail = (unsigned int)len;
 348                 sha1write(f, in, avail);
 349                 offset += avail;
 350                 len -= avail;
 351         }
 352 }
 353
 354 static unsigned long write_object(struct sha1file *f,
 355                                   struct object_entry *entry,
 356                                   off_t write_offset)
 357 {
 358         unsigned long size;
 359         enum object_type type;
 360         void *buf;
 361         unsigned char header[10];
 362         unsigned char dheader[10];
 363         unsigned hdrlen;
 364         off_t datalen;
 365         enum object_type obj_type;
 366         int to_reuse = 0;
 367         /* write limit if limited packsize and not first object */
 368         unsigned long limit = pack_size_limit && nr_written ?
 369                                 pack_size_limit - write_offset : 0;
 370                                 /* no if no delta */
 371         int usable_delta =      !entry->delta ? 0 :
 372                                 /* yes if unlimited packfile */
 373                                 !pack_size_limit ? 1 :
 374                                 /* no if base written to previous pack */
 375                                 entry->delta->offset == (off_t)-1 ? 0 :
 376                                 /* otherwise double-check written to this
 377                                  * pack,  like we do below
 378                                  */
 379                                 entry->delta->offset ? 1 : 0;
 380
 381         if (!pack_to_stdout)
 382                 crc32_begin(f);
 383
 384         obj_type = entry->type;
 385         if (no_reuse_object)
 386                 to_reuse = 0;   /* explicit */
 387         else if (!entry->in_pack)
 388                 to_reuse = 0;   /* can't reuse what we don't have */
 389         else if (obj_type == OBJ_REF_DELTA || obj_type == OBJ_OFS_DELTA)
 390                                 /* check_object() decided it for us ... */
 391                 to_reuse = usable_delta;
 392                                 /* ... but pack split may override that */
 393         else if (obj_type != entry->in_pack_type)
 394                 to_reuse = 0;   /* pack has delta which is unusable */
 395         else if (entry->delta)
 396                 to_reuse = 0;   /* we want to pack afresh */
 397         else
 398                 to_reuse = 1;   /* we have it in-pack undeltified,
 399                                  * and we do not need to deltify it.
 400                                  */
 401
 402         if (!to_reuse) {
 403                 z_stream stream;
 404                 unsigned long maxsize;
 405                 void *out;
 406                 buf = read_sha1_file(entry->sha1, &type, &size);
 407                 if (!buf)
 408                         die("unable to read %s", sha1_to_hex(entry->sha1));
 409                 if (size != entry->size)
 410                         die("object %s size inconsistency (%lu vs %lu)",
 411                             sha1_to_hex(entry->sha1), size, entry->size);
 412                 if (usable_delta) {
 413                         buf = delta_against(buf, size, entry);
 414                         size = entry->delta_size;
 415                         obj_type = (allow_ofs_delta && entry->delta->offset) ?
 416                                 OBJ_OFS_DELTA : OBJ_REF_DELTA;
 417                 } else {
 418                         /*
 419                          * recover real object type in case
 420                          * check_object() wanted to re-use a delta,
 421                          * but we couldn't since base was in previous split pack
 422                          */
 423                         obj_type = type;
 424                 }
 425                 /* compress the data to store and put compressed length in datalen */
 426                 memset(&stream, 0, sizeof(stream));
 427                 deflateInit(&stream, pack_compression_level);
 428                 maxsize = deflateBound(&stream, size);
 429                 out = xmalloc(maxsize);
 430                 /* Compress it */
 431                 stream.next_in = buf;
 432                 stream.avail_in = size;
 433                 stream.next_out = out;
 434                 stream.avail_out = maxsize;
 435                 while (deflate(&stream, Z_FINISH) == Z_OK)
 436                         /* nothing */;
 437                 deflateEnd(&stream);
 438                 datalen = stream.total_out;
 439                 deflateEnd(&stream);
 440                 /*
 441                  * The object header is a byte of 'type' followed by zero or
 442                  * more bytes of length.
 443                  */
 444                 hdrlen = encode_header(obj_type, size, header);
 445
 446                 if (obj_type == OBJ_OFS_DELTA) {
 447                         /*
 448                          * Deltas with relative base contain an additional
 449                          * encoding of the relative offset for the delta
 450                          * base from this object's position in the pack.
 451                          */
 452                         off_t ofs = entry->offset - entry->delta->offset;
 453                         unsigned pos = sizeof(dheader) - 1;
 454                         dheader[pos] = ofs & 127;
 455                         while (ofs >>= 7)
 456                                 dheader[--pos] = 128 | (--ofs & 127);
 457                         if (limit && hdrlen + sizeof(dheader) - pos + datalen + 20 >= limit) {
 458                                 free(out);
 459                                 free(buf);
 460                                 return 0;
 461                         }
 462                         sha1write(f, header, hdrlen);
 463                         sha1write(f, dheader + pos, sizeof(dheader) - pos);
 464                         hdrlen += sizeof(dheader) - pos;
 465                 } else if (obj_type == OBJ_REF_DELTA) {
 466                         /*
 467                          * Deltas with a base reference contain
 468                          * an additional 20 bytes for the base sha1.
 469                          */
 470                         if (limit && hdrlen + 20 + datalen + 20 >= limit) {
 471                                 free(out);
 472                                 free(buf);
 473                                 return 0;
 474                         }
 475                         sha1write(f, header, hdrlen);
 476                         sha1write(f, entry->delta->sha1, 20);
 477                         hdrlen += 20;
 478                 } else {
 479                         if (limit && hdrlen + datalen + 20 >= limit) {
 480                                 free(out);
 481                                 free(buf);
 482                                 return 0;
 483                         }
 484                         sha1write(f, header, hdrlen);
 485                 }
 486                 sha1write(f, out, datalen);
 487                 free(out);
 488                 free(buf);
 489         }
 490         else {
 491                 struct packed_git *p = entry->in_pack;
 492                 struct pack_window *w_curs = NULL;
 493                 struct revindex_entry *revidx;
 494                 off_t offset;
 495
 496                 if (entry->delta) {
 497                         obj_type = (allow_ofs_delta && entry->delta->offset) ?
 498                                 OBJ_OFS_DELTA : OBJ_REF_DELTA;
 499                         reused_delta++;
 500                 }
 501                 hdrlen = encode_header(obj_type, entry->size, header);
 502                 offset = entry->in_pack_offset;
 503                 revidx = find_packed_object(p, offset);
 504                 datalen = revidx[1].offset - offset;
 505                 if (!pack_to_stdout && p->index_version > 1 &&
 506                     check_pack_crc(p, &w_curs, offset, datalen, revidx->nr))
 507                         die("bad packed object CRC for %s", sha1_to_hex(entry->sha1));
 508                 offset += entry->in_pack_header_size;
 509                 datalen -= entry->in_pack_header_size;
 510                 if (obj_type == OBJ_OFS_DELTA) {
 511                         off_t ofs = entry->offset - entry->delta->offset;
 512                         unsigned pos = sizeof(dheader) - 1;
 513                         dheader[pos] = ofs & 127;
 514                         while (ofs >>= 7)
 515                                 dheader[--pos] = 128 | (--ofs & 127);
 516                         if (limit && hdrlen + sizeof(dheader) - pos + datalen + 20 >= limit)
 517                                 return 0;
 518                         sha1write(f, header, hdrlen);
 519                         sha1write(f, dheader + pos, sizeof(dheader) - pos);
 520                         hdrlen += sizeof(dheader) - pos;
 521                 } else if (obj_type == OBJ_REF_DELTA) {
 522                         if (limit && hdrlen + 20 + datalen + 20 >= limit)
 523                                 return 0;
 524                         sha1write(f, header, hdrlen);
 525                         sha1write(f, entry->delta->sha1, 20);
 526                         hdrlen += 20;
 527                 } else {
 528                         if (limit && hdrlen + datalen + 20 >= limit)
 529                                 return 0;
 530                         sha1write(f, header, hdrlen);
 531                 }
 532
 533                 if (!pack_to_stdout && p->index_version == 1 &&
 534                     check_pack_inflate(p, &w_curs, offset, datalen, entry->size))
 535                         die("corrupt packed object for %s", sha1_to_hex(entry->sha1));
 536                 copy_pack_data(f, p, &w_curs, offset, datalen);
 537                 unuse_pack(&w_curs);
 538                 reused++;
 539         }
 540         if (usable_delta)
 541                 written_delta++;
 542         written++;
 543         if (!pack_to_stdout)
 544                 entry->crc32 = crc32_end(f);
 545         return hdrlen + datalen;
 546 }
 547
 548 static off_t write_one(struct sha1file *f,
 549                                struct object_entry *e,
 550                                off_t offset)
 551 {
 552         unsigned long size;
 553
 554         /* offset is non zero if object is written already. */
 555         if (e->offset || e->preferred_base)
 556                 return offset;
 557
 558         /* if we are deltified, write out base object first. */
 559         if (e->delta) {
 560                 offset = write_one(f, e->delta, offset);
 561                 if (!offset)
 562                         return 0;
 563         }
 564
 565         e->offset = offset;
 566         size = write_object(f, e, offset);
 567         if (!size) {
 568                 e->offset = 0;
 569                 return 0;
 570         }
 571         written_list[nr_written++] = e;
 572
 573         /* make sure off_t is sufficiently large not to wrap */
 574         if (offset > offset + size)
 575                 die("pack too large for current definition of off_t");
 576         return offset + size;
 577 }
 578
 579 static int open_object_dir_tmp(const char *path)
 580 {
 581     snprintf(tmpname, sizeof(tmpname), "%s/%s", get_object_directory(), path);
 582     return mkstemp(tmpname);
 583 }
 584
 585 /* forward declarations for write_pack_file */
 586 static void write_index_file(off_t last_obj_offset, unsigned char *sha1);
 587 static int adjust_perm(const char *path, mode_t mode);
 588
 589 static void write_pack_file(void)
 590 {
 591         uint32_t i = 0, j;
 592         struct sha1file *f;
 593         off_t offset, offset_one, last_obj_offset = 0;
 594         struct pack_header hdr;
 595         int do_progress = progress >> pack_to_stdout;
 596         uint32_t nr_remaining = nr_result;
 597
 598         if (do_progress)
 599                 start_progress(&progress_state, "Writing %u objects...", "", nr_result);
 600         written_list = xmalloc(nr_objects * sizeof(struct object_entry *));
 601
 602         do {
 603                 if (pack_to_stdout) {
 604                         f = sha1fd(1, "<stdout>");
 605                 } else {
 606                         int fd = open_object_dir_tmp("tmp_pack_XXXXXX");
 607                         if (fd < 0)
 608                                 die("unable to create %s: %s\n", tmpname, strerror(errno));
 609                         pack_tmp_name = xstrdup(tmpname);
 610                         f = sha1fd(fd, pack_tmp_name);
 611                 }
 612
 613                 hdr.hdr_signature = htonl(PACK_SIGNATURE);
 614                 hdr.hdr_version = htonl(PACK_VERSION);
 615                 hdr.hdr_entries = htonl(nr_remaining);
 616                 sha1write(f, &hdr, sizeof(hdr));
 617                 offset = sizeof(hdr);
 618                 nr_written = 0;
 619                 for (; i < nr_objects; i++) {
 620                         last_obj_offset = offset;
 621                         offset_one = write_one(f, objects + i, offset);
 622                         if (!offset_one)
 623                                 break;
 624                         offset = offset_one;
 625                         if (do_progress)
 626                                 display_progress(&progress_state, written);
 627                 }
 628
 629                 /*
 630                  * Did we write the wrong # entries in the header?
 631                  * If so, rewrite it like in fast-import
 632                  */
 633                 if (pack_to_stdout || nr_written == nr_remaining) {
 634                         sha1close(f, pack_file_sha1, 1);
 635                 } else {
 636                         sha1close(f, pack_file_sha1, 0);
 637                         fixup_pack_header_footer(f->fd, pack_file_sha1, pack_tmp_name, nr_written);
 638                         close(f->fd);
 639                 }
 640
 641                 if (!pack_to_stdout) {
 642                         unsigned char object_list_sha1[20];
 643                         mode_t mode = umask(0);
 644
 645                         umask(mode);
 646                         mode = 0444 & ~mode;
 647
 648                         write_index_file(last_obj_offset, object_list_sha1);
 649                         snprintf(tmpname, sizeof(tmpname), "%s-%s.pack",
 650                                  base_name, sha1_to_hex(object_list_sha1));
 651                         if (adjust_perm(pack_tmp_name, mode))
 652                                 die("unable to make temporary pack file readable: %s",
 653                                     strerror(errno));
 654                         if (rename(pack_tmp_name, tmpname))
 655                                 die("unable to rename temporary pack file: %s",
 656                                     strerror(errno));
 657                         snprintf(tmpname, sizeof(tmpname), "%s-%s.idx",
 658                                  base_name, sha1_to_hex(object_list_sha1));
 659                         if (adjust_perm(idx_tmp_name, mode))
 660                                 die("unable to make temporary index file readable: %s",
 661                                     strerror(errno));
 662                         if (rename(idx_tmp_name, tmpname))
 663                                 die("unable to rename temporary index file: %s",
 664                                     strerror(errno));
 665                         puts(sha1_to_hex(object_list_sha1));
 666                 }
 667
 668                 /* mark written objects as written to previous pack */
 669                 for (j = 0; j < nr_written; j++) {
 670                         written_list[j]->offset = (off_t)-1;
 671                 }
 672                 nr_remaining -= nr_written;
 673         } while (nr_remaining && i < nr_objects);
 674
 675         free(written_list);
 676         if (do_progress)
 677                 stop_progress(&progress_state);
 678         if (written != nr_result)
 679                 die("wrote %u objects while expecting %u", written, nr_result);
 680         for (j = 0; i < nr_objects; i++) {
 681                 struct object_entry *e = objects + i;
 682                 j += !e->offset && !e->preferred_base;
 683         }
 684         if (j)
 685                 die("wrote %u objects as expected but %u unwritten", written, j);
 686 }
 687
 688 static int sha1_sort(const void *_a, const void *_b)
 689 {
 690         const struct object_entry *a = *(struct object_entry **)_a;
 691         const struct object_entry *b = *(struct object_entry **)_b;
 692         return hashcmp(a->sha1, b->sha1);
 693 }
 694
 695 static uint32_t index_default_version = 1;
 696 static uint32_t index_off32_limit = 0x7fffffff;
 697
 698 static void write_index_file(off_t last_obj_offset, unsigned char *sha1)
 699 {
 700         struct sha1file *f;
 701         struct object_entry **sorted_by_sha, **list, **last;
 702         uint32_t array[256];
 703         uint32_t i, index_version;
 704         SHA_CTX ctx;
 705
 706         int fd = open_object_dir_tmp("tmp_idx_XXXXXX");
 707         if (fd < 0)
 708                 die("unable to create %s: %s\n", tmpname, strerror(errno));
 709         idx_tmp_name = xstrdup(tmpname);
 710         f = sha1fd(fd, idx_tmp_name);
 711
 712         if (nr_written) {
 713                 sorted_by_sha = written_list;
 714                 qsort(sorted_by_sha, nr_written, sizeof(*sorted_by_sha), sha1_sort);
 715                 list = sorted_by_sha;
 716                 last = sorted_by_sha + nr_written;
 717         } else
 718                 sorted_by_sha = list = last = NULL;
 719
 720         /* if last object's offset is >= 2^31 we should use index V2 */
 721         index_version = (last_obj_offset >> 31) ? 2 : index_default_version;
 722
 723         /* index versions 2 and above need a header */
 724         if (index_version >= 2) {
 725                 struct pack_idx_header hdr;
 726                 hdr.idx_signature = htonl(PACK_IDX_SIGNATURE);
 727                 hdr.idx_version = htonl(index_version);
 728                 sha1write(f, &hdr, sizeof(hdr));
 729         }
 730
 731         /*
 732          * Write the first-level table (the list is sorted,
 733          * but we use a 256-entry lookup to be able to avoid
 734          * having to do eight extra binary search iterations).
 735          */
 736         for (i = 0; i < 256; i++) {
 737                 struct object_entry **next = list;
 738                 while (next < last) {
 739                         struct object_entry *entry = *next;
 740                         if (entry->sha1[0] != i)
 741                                 break;
 742                         next++;
 743                 }
 744                 array[i] = htonl(next - sorted_by_sha);
 745                 list = next;
 746         }
 747         sha1write(f, array, 256 * 4);
 748
 749         /* Compute the SHA1 hash of sorted object names. */
 750         SHA1_Init(&ctx);
 751
 752         /* Write the actual SHA1 entries. */
 753         list = sorted_by_sha;
 754         for (i = 0; i < nr_written; i++) {
 755                 struct object_entry *entry = *list++;
 756                 if (index_version < 2) {
 757                         uint32_t offset = htonl(entry->offset);
 758                         sha1write(f, &offset, 4);
 759                 }
 760                 sha1write(f, entry->sha1, 20);
 761                 SHA1_Update(&ctx, entry->sha1, 20);
 762         }
 763
 764         if (index_version >= 2) {
 765                 unsigned int nr_large_offset = 0;
 766
 767                 /* write the crc32 table */
 768                 list = sorted_by_sha;
 769                 for (i = 0; i < nr_written; i++) {
 770                         struct object_entry *entry = *list++;
 771                         uint32_t crc32_val = htonl(entry->crc32);
 772                         sha1write(f, &crc32_val, 4);
 773                 }
 774
 775                 /* write the 32-bit offset table */
 776                 list = sorted_by_sha;
 777                 for (i = 0; i < nr_written; i++) {
 778                         struct object_entry *entry = *list++;
 779                         uint32_t offset = (entry->offset <= index_off32_limit) ?
 780                                 entry->offset : (0x80000000 | nr_large_offset++);
 781                         offset = htonl(offset);
 782                         sha1write(f, &offset, 4);
 783                 }
 784
 785                 /* write the large offset table */
 786                 list = sorted_by_sha;
 787                 while (nr_large_offset) {
 788                         struct object_entry *entry = *list++;
 789                         uint64_t offset = entry->offset;
 790                         if (offset > index_off32_limit) {
 791                                 uint32_t split[2];
 792                                 split[0]        = htonl(offset >> 32);
 793                                 split[1] = htonl(offset & 0xffffffff);
 794                                 sha1write(f, split, 8);
 795                                 nr_large_offset--;
 796                         }
 797                 }
 798         }
 799
 800         sha1write(f, pack_file_sha1, 20);
 801         sha1close(f, NULL, 1);
 802         SHA1_Final(sha1, &ctx);
 803 }
 804
 805 static int locate_object_entry_hash(const unsigned char *sha1)
 806 {
 807         int i;
 808         unsigned int ui;
 809         memcpy(&ui, sha1, sizeof(unsigned int));
 810         i = ui % object_ix_hashsz;
 811         while (0 < object_ix[i]) {
 812                 if (!hashcmp(sha1, objects[object_ix[i] - 1].sha1))
 813                         return i;
 814                 if (++i == object_ix_hashsz)
 815                         i = 0;
 816         }
 817         return -1 - i;
 818 }
 819
 820 static struct object_entry *locate_object_entry(const unsigned char *sha1)
 821 {
 822         int i;
 823
 824         if (!object_ix_hashsz)
 825                 return NULL;
 826
 827         i = locate_object_entry_hash(sha1);
 828         if (0 <= i)
 829                 return &objects[object_ix[i]-1];
 830         return NULL;
 831 }
 832
 833 static void rehash_objects(void)
 834 {
 835         uint32_t i;
 836         struct object_entry *oe;
 837
 838         object_ix_hashsz = nr_objects * 3;
 839         if (object_ix_hashsz < 1024)
 840                 object_ix_hashsz = 1024;
 841         object_ix = xrealloc(object_ix, sizeof(int) * object_ix_hashsz);
 842         memset(object_ix, 0, sizeof(int) * object_ix_hashsz);
 843         for (i = 0, oe = objects; i < nr_objects; i++, oe++) {
 844                 int ix = locate_object_entry_hash(oe->sha1);
 845                 if (0 <= ix)
 846                         continue;
 847                 ix = -1 - ix;
 848                 object_ix[ix] = i + 1;
 849         }
 850 }
 851
 852 static unsigned name_hash(const char *name)
 853 {
 854         unsigned char c;
 855         unsigned hash = 0;
 856
 857         /*
 858          * This effectively just creates a sortable number from the
 859          * last sixteen non-whitespace characters. Last characters
 860          * count "most", so things that end in ".c" sort together.
 861          */
 862         while ((c = *name++) != 0) {
 863                 if (isspace(c))
 864                         continue;
 865                 hash = (hash >> 2) + (c << 24);
 866         }
 867         return hash;
 868 }
 869
 870 static int add_object_entry(const unsigned char *sha1, enum object_type type,
 871                             unsigned hash, int exclude)
 872 {
 873         struct object_entry *entry;
 874         struct packed_git *p, *found_pack = NULL;
 875         off_t found_offset = 0;
 876         int ix;
 877
 878         ix = nr_objects ? locate_object_entry_hash(sha1) : -1;
 879         if (ix >= 0) {
 880                 if (exclude) {
 881                         entry = objects + object_ix[ix] - 1;
 882                         if (!entry->preferred_base)
 883                                 nr_result--;
 884                         entry->preferred_base = 1;
 885                 }
 886                 return 0;
 887         }
 888
 889         for (p = packed_git; p; p = p->next) {
 890                 off_t offset = find_pack_entry_one(sha1, p);
 891                 if (offset) {
 892                         if (!found_pack) {
 893                                 found_offset = offset;
 894                                 found_pack = p;
 895                         }
 896                         if (exclude)
 897                                 break;
 898                         if (incremental)
 899                                 return 0;
 900                         if (local && !p->pack_local)
 901                                 return 0;
 902                 }
 903         }
 904
 905         if (nr_objects >= nr_alloc) {
 906                 nr_alloc = (nr_alloc  + 1024) * 3 / 2;
 907                 objects = xrealloc(objects, nr_alloc * sizeof(*entry));
 908         }
 909
 910         entry = objects + nr_objects++;
 911         memset(entry, 0, sizeof(*entry));
 912         hashcpy(entry->sha1, sha1);
 913         entry->hash = hash;
 914         if (type)
 915                 entry->type = type;
 916         if (exclude)
 917                 entry->preferred_base = 1;
 918         else
 919                 nr_result++;
 920         if (found_pack) {
 921                 entry->in_pack = found_pack;
 922                 entry->in_pack_offset = found_offset;
 923         }
 924
 925         if (object_ix_hashsz * 3 <= nr_objects * 4)
 926                 rehash_objects();
 927         else
 928                 object_ix[-1 - ix] = nr_objects;
 929
 930         if (progress)
 931                 display_progress(&progress_state, nr_objects);
 932
 933         return 1;
 934 }
 935
 936 struct pbase_tree_cache {
 937         unsigned char sha1[20];
 938         int ref;
 939         int temporary;
 940         void *tree_data;
 941         unsigned long tree_size;
 942 };
 943
 944 static struct pbase_tree_cache *(pbase_tree_cache[256]);
 945 static int pbase_tree_cache_ix(const unsigned char *sha1)
 946 {
 947         return sha1[0] % ARRAY_SIZE(pbase_tree_cache);
 948 }
 949 static int pbase_tree_cache_ix_incr(int ix)
 950 {
 951         return (ix+1) % ARRAY_SIZE(pbase_tree_cache);
 952 }
 953
 954 static struct pbase_tree {
 955         struct pbase_tree *next;
 956         /* This is a phony "cache" entry; we are not
 957          * going to evict it nor find it through _get()
 958          * mechanism -- this is for the toplevel node that
 959          * would almost always change with any commit.
 960          */
 961         struct pbase_tree_cache pcache;
 962 } *pbase_tree;
 963
 964 static struct pbase_tree_cache *pbase_tree_get(const unsigned char *sha1)
 965 {
 966         struct pbase_tree_cache *ent, *nent;
 967         void *data;
 968         unsigned long size;
 969         enum object_type type;
 970         int neigh;
 971         int my_ix = pbase_tree_cache_ix(sha1);
 972         int available_ix = -1;
 973
 974         /* pbase-tree-cache acts as a limited hashtable.
 975          * your object will be found at your index or within a few
 976          * slots after that slot if it is cached.
 977          */
 978         for (neigh = 0; neigh < 8; neigh++) {
 979                 ent = pbase_tree_cache[my_ix];
 980                 if (ent && !hashcmp(ent->sha1, sha1)) {
 981                         ent->ref++;
 982                         return ent;
 983                 }
 984                 else if (((available_ix < 0) && (!ent || !ent->ref)) ||
 985                          ((0 <= available_ix) &&
 986                           (!ent && pbase_tree_cache[available_ix])))
 987                         available_ix = my_ix;
 988                 if (!ent)
 989                         break;
 990                 my_ix = pbase_tree_cache_ix_incr(my_ix);
 991         }
 992
 993         /* Did not find one.  Either we got a bogus request or
 994          * we need to read and perhaps cache.
 995          */
 996         data = read_sha1_file(sha1, &type, &size);
 997         if (!data)
 998                 return NULL;
 999         if (type != OBJ_TREE) {
1000                 free(data);
1001                 return NULL;
1002         }
1003
1004         /* We need to either cache or return a throwaway copy */
1005
1006         if (available_ix < 0)
1007                 ent = NULL;
1008         else {
1009                 ent = pbase_tree_cache[available_ix];
1010                 my_ix = available_ix;
1011         }
1012
1013         if (!ent) {
1014                 nent = xmalloc(sizeof(*nent));
1015                 nent->temporary = (available_ix < 0);
1016         }
1017         else {
1018                 /* evict and reuse */
1019                 free(ent->tree_data);
1020                 nent = ent;
1021         }
1022         hashcpy(nent->sha1, sha1);
1023         nent->tree_data = data;
1024         nent->tree_size = size;
1025         nent->ref = 1;
1026         if (!nent->temporary)
1027                 pbase_tree_cache[my_ix] = nent;
1028         return nent;
1029 }
1030
1031 static void pbase_tree_put(struct pbase_tree_cache *cache)
1032 {
1033         if (!cache->temporary) {
1034                 cache->ref--;
1035                 return;
1036         }
1037         free(cache->tree_data);
1038         free(cache);
1039 }
1040
1041 static int name_cmp_len(const char *name)
1042 {
1043         int i;
1044         for (i = 0; name[i] && name[i] != '\n' && name[i] != '/'; i++)
1045                 ;
1046         return i;
1047 }
1048
1049 static void add_pbase_object(struct tree_desc *tree,
1050                              const char *name,
1051                              int cmplen,
1052                              const char *fullname)
1053 {
1054         struct name_entry entry;
1055         int cmp;
1056
1057         while (tree_entry(tree,&entry)) {
1058                 cmp = tree_entry_len(entry.path, entry.sha1) != cmplen ? 1 :
1059                       memcmp(name, entry.path, cmplen);
1060                 if (cmp > 0)
1061                         continue;
1062                 if (cmp < 0)
1063                         return;
1064                 if (name[cmplen] != '/') {
1065                         unsigned hash = name_hash(fullname);
1066                         add_object_entry(entry.sha1,
1067                                          S_ISDIR(entry.mode) ? OBJ_TREE : OBJ_BLOB,
1068                                          hash, 1);
1069                         return;
1070                 }
1071                 if (S_ISDIR(entry.mode)) {
1072                         struct tree_desc sub;
1073                         struct pbase_tree_cache *tree;
1074                         const char *down = name+cmplen+1;
1075                         int downlen = name_cmp_len(down);
1076
1077                         tree = pbase_tree_get(entry.sha1);
1078                         if (!tree)
1079                                 return;
1080                         init_tree_desc(&sub, tree->tree_data, tree->tree_size);
1081
1082                         add_pbase_object(&sub, down, downlen, fullname);
1083                         pbase_tree_put(tree);
1084                 }
1085         }
1086 }
1087
1088 static unsigned *done_pbase_paths;
1089 static int done_pbase_paths_num;
1090 static int done_pbase_paths_alloc;
1091 static int done_pbase_path_pos(unsigned hash)
1092 {
1093         int lo = 0;
1094         int hi = done_pbase_paths_num;
1095         while (lo < hi) {
1096                 int mi = (hi + lo) / 2;
1097                 if (done_pbase_paths[mi] == hash)
1098                         return mi;
1099                 if (done_pbase_paths[mi] < hash)
1100                         hi = mi;
1101                 else
1102                         lo = mi + 1;
1103         }
1104         return -lo-1;
1105 }
1106
1107 static int check_pbase_path(unsigned hash)
1108 {
1109         int pos = (!done_pbase_paths) ? -1 : done_pbase_path_pos(hash);
1110         if (0 <= pos)
1111                 return 1;
1112         pos = -pos - 1;
1113         if (done_pbase_paths_alloc <= done_pbase_paths_num) {
1114                 done_pbase_paths_alloc = alloc_nr(done_pbase_paths_alloc);
1115                 done_pbase_paths = xrealloc(done_pbase_paths,
1116                                             done_pbase_paths_alloc *
1117                                             sizeof(unsigned));
1118         }
1119         done_pbase_paths_num++;
1120         if (pos < done_pbase_paths_num)
1121                 memmove(done_pbase_paths + pos + 1,
1122                         done_pbase_paths + pos,
1123                         (done_pbase_paths_num - pos - 1) * sizeof(unsigned));
1124         done_pbase_paths[pos] = hash;
1125         return 0;
1126 }
1127
1128 static void add_preferred_base_object(const char *name, unsigned hash)
1129 {
1130         struct pbase_tree *it;
1131         int cmplen;
1132
1133         if (!num_preferred_base || check_pbase_path(hash))
1134                 return;
1135
1136         cmplen = name_cmp_len(name);
1137         for (it = pbase_tree; it; it = it->next) {
1138                 if (cmplen == 0) {
1139                         add_object_entry(it->pcache.sha1, OBJ_TREE, 0, 1);
1140                 }
1141                 else {
1142                         struct tree_desc tree;
1143                         init_tree_desc(&tree, it->pcache.tree_data, it->pcache.tree_size);
1144                         add_pbase_object(&tree, name, cmplen, name);
1145                 }
1146         }
1147 }
1148
1149 static void add_preferred_base(unsigned char *sha1)
1150 {
1151         struct pbase_tree *it;
1152         void *data;
1153         unsigned long size;
1154         unsigned char tree_sha1[20];
1155
1156         if (window <= num_preferred_base++)
1157                 return;
1158
1159         data = read_object_with_reference(sha1, tree_type, &size, tree_sha1);
1160         if (!data)
1161                 return;
1162
1163         for (it = pbase_tree; it; it = it->next) {
1164                 if (!hashcmp(it->pcache.sha1, tree_sha1)) {
1165                         free(data);
1166                         return;
1167                 }
1168         }
1169
1170         it = xcalloc(1, sizeof(*it));
1171         it->next = pbase_tree;
1172         pbase_tree = it;
1173
1174         hashcpy(it->pcache.sha1, tree_sha1);
1175         it->pcache.tree_data = data;
1176         it->pcache.tree_size = size;
1177 }
1178
1179 static void check_object(struct object_entry *entry)
1180 {
1181         if (entry->in_pack) {
1182                 struct packed_git *p = entry->in_pack;
1183                 struct pack_window *w_curs = NULL;
1184                 const unsigned char *base_ref = NULL;
1185                 struct object_entry *base_entry;
1186                 unsigned long used, used_0;
1187                 unsigned int avail;
1188                 off_t ofs;
1189                 unsigned char *buf, c;
1190
1191                 buf = use_pack(p, &w_curs, entry->in_pack_offset, &avail);
1192
1193                 /*
1194                  * We want in_pack_type even if we do not reuse delta
1195                  * since non-delta representations could still be reused.
1196                  */
1197                 used = unpack_object_header_gently(buf, avail,
1198                                                    &entry->in_pack_type,
1199                                                    &entry->size);
1200
1201                 /*
1202                  * Determine if this is a delta and if so whether we can
1203                  * reuse it or not.  Otherwise let's find out as cheaply as
1204                  * possible what the actual type and size for this object is.
1205                  */
1206                 switch (entry->in_pack_type) {
1207                 default:
1208                         /* Not a delta hence we've already got all we need. */
1209                         entry->type = entry->in_pack_type;
1210                         entry->in_pack_header_size = used;
1211                         unuse_pack(&w_curs);
1212                         return;
1213                 case OBJ_REF_DELTA:
1214                         if (!no_reuse_delta && !entry->preferred_base)
1215                                 base_ref = use_pack(p, &w_curs,
1216                                                 entry->in_pack_offset + used, NULL);
1217                         entry->in_pack_header_size = used + 20;
1218                         break;
1219                 case OBJ_OFS_DELTA:
1220                         buf = use_pack(p, &w_curs,
1221                                        entry->in_pack_offset + used, NULL);
1222                         used_0 = 0;
1223                         c = buf[used_0++];
1224                         ofs = c & 127;
1225                         while (c & 128) {
1226                                 ofs += 1;
1227                                 if (!ofs || MSB(ofs, 7))
1228                                         die("delta base offset overflow in pack for %s",
1229                                             sha1_to_hex(entry->sha1));
1230                                 c = buf[used_0++];
1231                                 ofs = (ofs << 7) + (c & 127);
1232                         }
1233                         if (ofs >= entry->in_pack_offset)
1234                                 die("delta base offset out of bound for %s",
1235                                     sha1_to_hex(entry->sha1));
1236                         ofs = entry->in_pack_offset - ofs;
1237                         if (!no_reuse_delta && !entry->preferred_base)
1238                                 base_ref = find_packed_object_name(p, ofs);
1239                         entry->in_pack_header_size = used + used_0;
1240                         break;
1241                 }
1242
1243                 if (base_ref && (base_entry = locate_object_entry(base_ref))) {
1244                         /*
1245                          * If base_ref was set above that means we wish to
1246                          * reuse delta data, and we even found that base
1247                          * in the list of objects we want to pack. Goodie!
1248                          *
1249                          * Depth value does not matter - find_deltas() will
1250                          * never consider reused delta as the base object to
1251                          * deltify other objects against, in order to avoid
1252                          * circular deltas.
1253                          */
1254                         entry->type = entry->in_pack_type;
1255                         entry->delta = base_entry;
1256                         entry->delta_sibling = base_entry->delta_child;
1257                         base_entry->delta_child = entry;
1258                         unuse_pack(&w_curs);
1259                         return;
1260                 }
1261
1262                 if (entry->type) {
1263                         /*
1264                          * This must be a delta and we already know what the
1265                          * final object type is.  Let's extract the actual
1266                          * object size from the delta header.
1267                          */
1268                         entry->size = get_size_from_delta(p, &w_curs,
1269                                         entry->in_pack_offset + entry->in_pack_header_size);
1270                         unuse_pack(&w_curs);
1271                         return;
1272                 }
1273
1274                 /*
1275                  * No choice but to fall back to the recursive delta walk
1276                  * with sha1_object_info() to find about the object type
1277                  * at this point...
1278                  */
1279                 unuse_pack(&w_curs);
1280         }
1281
1282         entry->type = sha1_object_info(entry->sha1, &entry->size);
1283         if (entry->type < 0)
1284                 die("unable to get type of object %s",
1285                     sha1_to_hex(entry->sha1));
1286 }
1287
1288 static int pack_offset_sort(const void *_a, const void *_b)
1289 {
1290         const struct object_entry *a = *(struct object_entry **)_a;
1291         const struct object_entry *b = *(struct object_entry **)_b;
1292
1293         /* avoid filesystem trashing with loose objects */
1294         if (!a->in_pack && !b->in_pack)
1295                 return hashcmp(a->sha1, b->sha1);
1296
1297         if (a->in_pack < b->in_pack)
1298                 return -1;
1299         if (a->in_pack > b->in_pack)
1300                 return 1;
1301         return a->in_pack_offset < b->in_pack_offset ? -1 :
1302                         (a->in_pack_offset > b->in_pack_offset);
1303 }
1304
1305 static void get_object_details(void)
1306 {
1307         uint32_t i;
1308         struct object_entry **sorted_by_offset;
1309
1310         sorted_by_offset = xcalloc(nr_objects, sizeof(struct object_entry *));
1311         for (i = 0; i < nr_objects; i++)
1312                 sorted_by_offset[i] = objects + i;
1313         qsort(sorted_by_offset, nr_objects, sizeof(*sorted_by_offset), pack_offset_sort);
1314
1315         prepare_pack_ix();
1316         for (i = 0; i < nr_objects; i++)
1317                 check_object(sorted_by_offset[i]);
1318         free(sorted_by_offset);
1319 }
1320
1321 static int type_size_sort(const void *_a, const void *_b)
1322 {
1323         const struct object_entry *a = *(struct object_entry **)_a;
1324         const struct object_entry *b = *(struct object_entry **)_b;
1325
1326         if (a->type < b->type)
1327                 return -1;
1328         if (a->type > b->type)
1329                 return 1;
1330         if (a->hash < b->hash)
1331                 return -1;
1332         if (a->hash > b->hash)
1333                 return 1;
1334         if (a->preferred_base < b->preferred_base)
1335                 return -1;
1336         if (a->preferred_base > b->preferred_base)
1337                 return 1;
1338         if (a->size < b->size)
1339                 return -1;
1340         if (a->size > b->size)
1341                 return 1;
1342         return a > b ? -1 : (a < b);  /* newest last */
1343 }
1344
1345 struct unpacked {
1346         struct object_entry *entry;
1347         void *data;
1348         struct delta_index *index;
1349 };
1350
1351 /*
1352  * We search for deltas _backwards_ in a list sorted by type and
1353  * by size, so that we see progressively smaller and smaller files.
1354  * That's because we prefer deltas to be from the bigger file
1355  * to the smaller - deletes are potentially cheaper, but perhaps
1356  * more importantly, the bigger file is likely the more recent
1357  * one.
1358  */
1359 static int try_delta(struct unpacked *trg, struct unpacked *src,
1360                      unsigned max_depth)
1361 {
1362         struct object_entry *trg_entry = trg->entry;
1363         struct object_entry *src_entry = src->entry;
1364         unsigned long trg_size, src_size, delta_size, sizediff, max_size, sz;
1365         enum object_type type;
1366         void *delta_buf;
1367
1368         /* Don't bother doing diffs between different types */
1369         if (trg_entry->type != src_entry->type)
1370                 return -1;
1371
1372         /* We do not compute delta to *create* objects we are not
1373          * going to pack.
1374          */
1375         if (trg_entry->preferred_base)
1376                 return -1;
1377
1378         /*
1379          * We do not bother to try a delta that we discarded
1380          * on an earlier try, but only when reusing delta data.
1381          */
1382         if (!no_reuse_delta && trg_entry->in_pack &&
1383             trg_entry->in_pack == src_entry->in_pack &&
1384             trg_entry->in_pack_type != OBJ_REF_DELTA &&
1385             trg_entry->in_pack_type != OBJ_OFS_DELTA)
1386                 return 0;
1387
1388         /* Let's not bust the allowed depth. */
1389         if (src_entry->depth >= max_depth)
1390                 return 0;
1391
1392         /* Now some size filtering heuristics. */
1393         trg_size = trg_entry->size;
1394         max_size = trg_size/2 - 20;
1395         max_size = max_size * (max_depth - src_entry->depth) / max_depth;
1396         if (max_size == 0)
1397                 return 0;
1398         if (trg_entry->delta && trg_entry->delta_size <= max_size)
1399                 max_size = trg_entry->delta_size-1;
1400         src_size = src_entry->size;
1401         sizediff = src_size < trg_size ? trg_size - src_size : 0;
1402         if (sizediff >= max_size)
1403                 return 0;
1404
1405         /* Load data if not already done */
1406         if (!trg->data) {
1407                 trg->data = read_sha1_file(trg_entry->sha1, &type, &sz);
1408                 if (sz != trg_size)
1409                         die("object %s inconsistent object length (%lu vs %lu)",
1410                             sha1_to_hex(trg_entry->sha1), sz, trg_size);
1411         }
1412         if (!src->data) {
1413                 src->data = read_sha1_file(src_entry->sha1, &type, &sz);
1414                 if (sz != src_size)
1415                         die("object %s inconsistent object length (%lu vs %lu)",
1416                             sha1_to_hex(src_entry->sha1), sz, src_size);
1417         }
1418         if (!src->index) {
1419                 src->index = create_delta_index(src->data, src_size);
1420                 if (!src->index)
1421                         die("out of memory");
1422         }
1423
1424         delta_buf = create_delta(src->index, trg->data, trg_size, &delta_size, max_size);
1425         if (!delta_buf)
1426                 return 0;
1427
1428         trg_entry->delta = src_entry;
1429         trg_entry->delta_size = delta_size;
1430         trg_entry->depth = src_entry->depth + 1;
1431         free(delta_buf);
1432         return 1;
1433 }
1434
1435 static unsigned int check_delta_limit(struct object_entry *me, unsigned int n)
1436 {
1437         struct object_entry *child = me->delta_child;
1438         unsigned int m = n;
1439         while (child) {
1440                 unsigned int c = check_delta_limit(child, n + 1);
1441                 if (m < c)
1442                         m = c;
1443                 child = child->delta_sibling;
1444         }
1445         return m;
1446 }
1447
1448 static void find_deltas(struct object_entry **list, int window, int depth)
1449 {
1450         uint32_t i = nr_objects, idx = 0, processed = 0;
1451         unsigned int array_size = window * sizeof(struct unpacked);
1452         struct unpacked *array;
1453         int max_depth;
1454
1455         if (!nr_objects)
1456                 return;
1457         array = xmalloc(array_size);
1458         memset(array, 0, array_size);
1459         if (progress)
1460                 start_progress(&progress_state, "Deltifying %u objects...", "", nr_result);
1461
1462         do {
1463                 struct object_entry *entry = list[--i];
1464                 struct unpacked *n = array + idx;
1465                 int j;
1466
1467                 if (!entry->preferred_base)
1468                         processed++;
1469
1470                 if (progress)
1471                         display_progress(&progress_state, processed);
1472
1473                 if (entry->delta)
1474                         /* This happens if we decided to reuse existing
1475                          * delta from a pack.  "!no_reuse_delta &&" is implied.
1476                          */
1477                         continue;
1478
1479                 if (entry->size < 50)
1480                         continue;
1481                 free_delta_index(n->index);
1482                 n->index = NULL;
1483                 free(n->data);
1484                 n->data = NULL;
1485                 n->entry = entry;
1486
1487                 /*
1488                  * If the current object is at pack edge, take the depth the
1489                  * objects that depend on the current object into account
1490                  * otherwise they would become too deep.
1491                  */
1492                 max_depth = depth;
1493                 if (entry->delta_child) {
1494                         max_depth -= check_delta_limit(entry, 0);
1495                         if (max_depth <= 0)
1496                                 goto next;
1497                 }
1498
1499                 j = window;
1500                 while (--j > 0) {
1501                         uint32_t other_idx = idx + j;
1502                         struct unpacked *m;
1503                         if (other_idx >= window)
1504                                 other_idx -= window;
1505                         m = array + other_idx;
1506                         if (!m->entry)
1507                                 break;
1508                         if (try_delta(n, m, max_depth) < 0)
1509                                 break;
1510                 }
1511
1512                 /* if we made n a delta, and if n is already at max
1513                  * depth, leaving it in the window is pointless.  we
1514                  * should evict it first.
1515                  */
1516                 if (entry->delta && depth <= entry->depth)
1517                         continue;
1518
1519                 next:
1520                 idx++;
1521                 if (idx >= window)
1522                         idx = 0;
1523         } while (i > 0);
1524
1525         if (progress)
1526                 stop_progress(&progress_state);
1527
1528         for (i = 0; i < window; ++i) {
1529                 free_delta_index(array[i].index);
1530                 free(array[i].data);
1531         }
1532         free(array);
1533 }
1534
1535 static void prepare_pack(int window, int depth)
1536 {
1537         struct object_entry **delta_list;
1538         uint32_t i;
1539
1540         get_object_details();
1541
1542         if (!window || !depth)
1543                 return;
1544
1545         delta_list = xmalloc(nr_objects * sizeof(*delta_list));
1546         for (i = 0; i < nr_objects; i++)
1547                 delta_list[i] = objects + i;
1548         qsort(delta_list, nr_objects, sizeof(*delta_list), type_size_sort);
1549         find_deltas(delta_list, window+1, depth);
1550         free(delta_list);
1551 }
1552
1553 static int git_pack_config(const char *k, const char *v)
1554 {
1555         if(!strcmp(k, "pack.window")) {
1556                 window = git_config_int(k, v);
1557                 return 0;
1558         }
1559         if(!strcmp(k, "pack.depth")) {
1560                 depth = git_config_int(k, v);
1561                 return 0;
1562         }
1563         if (!strcmp(k, "pack.compression")) {
1564                 int level = git_config_int(k, v);
1565                 if (level == -1)
1566                         level = Z_DEFAULT_COMPRESSION;
1567                 else if (level < 0 || level > Z_BEST_COMPRESSION)
1568                         die("bad pack compression level %d", level);
1569                 pack_compression_level = level;
1570                 pack_compression_seen = 1;
1571                 return 0;
1572         }
1573         return git_default_config(k, v);
1574 }
1575
1576 static void read_object_list_from_stdin(void)
1577 {
1578         char line[40 + 1 + PATH_MAX + 2];
1579         unsigned char sha1[20];
1580         unsigned hash;
1581
1582         for (;;) {
1583                 if (!fgets(line, sizeof(line), stdin)) {
1584                         if (feof(stdin))
1585                                 break;
1586                         if (!ferror(stdin))
1587                                 die("fgets returned NULL, not EOF, not error!");
1588                         if (errno != EINTR)
1589                                 die("fgets: %s", strerror(errno));
1590                         clearerr(stdin);
1591                         continue;
1592                 }
1593                 if (line[0] == '-') {
1594                         if (get_sha1_hex(line+1, sha1))
1595                                 die("expected edge sha1, got garbage:\n %s",
1596                                     line);
1597                         add_preferred_base(sha1);
1598                         continue;
1599                 }
1600                 if (get_sha1_hex(line, sha1))
1601                         die("expected sha1, got garbage:\n %s", line);
1602
1603                 hash = name_hash(line+41);
1604                 add_preferred_base_object(line+41, hash);
1605                 add_object_entry(sha1, 0, hash, 0);
1606         }
1607 }
1608
1609 static void show_commit(struct commit *commit)
1610 {
1611         add_object_entry(commit->object.sha1, OBJ_COMMIT, 0, 0);
1612 }
1613
1614 static void show_object(struct object_array_entry *p)
1615 {
1616         unsigned hash = name_hash(p->name);
1617         add_preferred_base_object(p->name, hash);
1618         add_object_entry(p->item->sha1, p->item->type, hash, 0);
1619 }
1620
1621 static void show_edge(struct commit *commit)
1622 {
1623         add_preferred_base(commit->object.sha1);
1624 }
1625
1626 static void get_object_list(int ac, const char **av)
1627 {
1628         struct rev_info revs;
1629         char line[1000];
1630         int flags = 0;
1631
1632         init_revisions(&revs, NULL);
1633         save_commit_buffer = 0;
1634         track_object_refs = 0;
1635         setup_revisions(ac, av, &revs, NULL);
1636
1637         while (fgets(line, sizeof(line), stdin) != NULL) {
1638                 int len = strlen(line);
1639                 if (line[len - 1] == '\n')
1640                         line[--len] = 0;
1641                 if (!len)
1642                         break;
1643                 if (*line == '-') {
1644                         if (!strcmp(line, "--not")) {
1645                                 flags ^= UNINTERESTING;
1646                                 continue;
1647                         }
1648                         die("not a rev '%s'", line);
1649                 }
1650                 if (handle_revision_arg(line, &revs, flags, 1))
1651                         die("bad revision '%s'", line);
1652         }
1653
1654         prepare_revision_walk(&revs);
1655         mark_edges_uninteresting(revs.commits, &revs, show_edge);
1656         traverse_commit_list(&revs, show_commit, show_object);
1657 }
1658
1659 static int adjust_perm(const char *path, mode_t mode)
1660 {
1661         if (chmod(path, mode))
1662                 return -1;
1663         return adjust_shared_perm(path);
1664 }
1665
1666 int cmd_pack_objects(int argc, const char **argv, const char *prefix)
1667 {
1668         int use_internal_rev_list = 0;
1669         int thin = 0;
1670         uint32_t i;
1671         const char **rp_av;
1672         int rp_ac_alloc = 64;
1673         int rp_ac;
1674
1675         rp_av = xcalloc(rp_ac_alloc, sizeof(*rp_av));
1676
1677         rp_av[0] = "pack-objects";
1678         rp_av[1] = "--objects"; /* --thin will make it --objects-edge */
1679         rp_ac = 2;
1680
1681         git_config(git_pack_config);
1682         if (!pack_compression_seen && core_compression_seen)
1683                 pack_compression_level = core_compression_level;
1684
1685         progress = isatty(2);
1686         for (i = 1; i < argc; i++) {
1687                 const char *arg = argv[i];
1688
1689                 if (*arg != '-')
1690                         break;
1691
1692                 if (!strcmp("--non-empty", arg)) {
1693                         non_empty = 1;
1694                         continue;
1695                 }
1696                 if (!strcmp("--local", arg)) {
1697                         local = 1;
1698                         continue;
1699                 }
1700                 if (!strcmp("--incremental", arg)) {
1701                         incremental = 1;
1702                         continue;
1703                 }
1704                 if (!prefixcmp(arg, "--compression=")) {
1705                         char *end;
1706                         int level = strtoul(arg+14, &end, 0);
1707                         if (!arg[14] || *end)
1708                                 usage(pack_usage);
1709                         if (level == -1)
1710                                 level = Z_DEFAULT_COMPRESSION;
1711                         else if (level < 0 || level > Z_BEST_COMPRESSION)
1712                                 die("bad pack compression level %d", level);
1713                         pack_compression_level = level;
1714                         continue;
1715                 }
1716                 if (!prefixcmp(arg, "--max-pack-size=")) {
1717                         char *end;
1718                         pack_size_limit = strtoul(arg+16, &end, 0) * 1024 * 1024;
1719                         if (!arg[16] || *end)
1720                                 usage(pack_usage);
1721                         continue;
1722                 }
1723                 if (!prefixcmp(arg, "--window=")) {
1724                         char *end;
1725                         window = strtoul(arg+9, &end, 0);
1726                         if (!arg[9] || *end)
1727                                 usage(pack_usage);
1728                         continue;
1729                 }
1730                 if (!prefixcmp(arg, "--depth=")) {
1731                         char *end;
1732                         depth = strtoul(arg+8, &end, 0);
1733                         if (!arg[8] || *end)
1734                                 usage(pack_usage);
1735                         continue;
1736                 }
1737                 if (!strcmp("--progress", arg)) {
1738                         progress = 1;
1739                         continue;
1740                 }
1741                 if (!strcmp("--all-progress", arg)) {
1742                         progress = 2;
1743                         continue;
1744                 }
1745                 if (!strcmp("-q", arg)) {
1746                         progress = 0;
1747                         continue;
1748                 }
1749                 if (!strcmp("--no-reuse-delta", arg)) {
1750                         no_reuse_delta = 1;
1751                         continue;
1752                 }
1753                 if (!strcmp("--no-reuse-object", arg)) {
1754                         no_reuse_object = no_reuse_delta = 1;
1755                         continue;
1756                 }
1757                 if (!strcmp("--delta-base-offset", arg)) {
1758                         allow_ofs_delta = 1;
1759                         continue;
1760                 }
1761                 if (!strcmp("--stdout", arg)) {
1762                         pack_to_stdout = 1;
1763                         continue;
1764                 }
1765                 if (!strcmp("--revs", arg)) {
1766                         use_internal_rev_list = 1;
1767                         continue;
1768                 }
1769                 if (!strcmp("--unpacked", arg) ||
1770                     !prefixcmp(arg, "--unpacked=") ||
1771                     !strcmp("--reflog", arg) ||
1772                     !strcmp("--all", arg)) {
1773                         use_internal_rev_list = 1;
1774                         if (rp_ac >= rp_ac_alloc - 1) {
1775                                 rp_ac_alloc = alloc_nr(rp_ac_alloc);
1776                                 rp_av = xrealloc(rp_av,
1777                                                  rp_ac_alloc * sizeof(*rp_av));
1778                         }
1779                         rp_av[rp_ac++] = arg;
1780                         continue;
1781                 }
1782                 if (!strcmp("--thin", arg)) {
1783                         use_internal_rev_list = 1;
1784                         thin = 1;
1785                         rp_av[1] = "--objects-edge";
1786                         continue;
1787                 }
1788                 if (!prefixcmp(arg, "--index-version=")) {
1789                         char *c;
1790                         index_default_version = strtoul(arg + 16, &c, 10);
1791                         if (index_default_version > 2)
1792                                 die("bad %s", arg);
1793                         if (*c == ',')
1794                                 index_off32_limit = strtoul(c+1, &c, 0);
1795                         if (*c || index_off32_limit & 0x80000000)
1796                                 die("bad %s", arg);
1797                         continue;
1798                 }
1799                 usage(pack_usage);
1800         }
1801
1802         /* Traditionally "pack-objects [options] base extra" failed;
1803          * we would however want to take refs parameter that would
1804          * have been given to upstream rev-list ourselves, which means
1805          * we somehow want to say what the base name is.  So the
1806          * syntax would be:
1807          *
1808          * pack-objects [options] base <refs...>
1809          *
1810          * in other words, we would treat the first non-option as the
1811          * base_name and send everything else to the internal revision
1812          * walker.
1813          */
1814
1815         if (!pack_to_stdout)
1816                 base_name = argv[i++];
1817
1818         if (pack_to_stdout != !base_name)
1819                 usage(pack_usage);
1820
1821         if (!pack_to_stdout && thin)
1822                 die("--thin cannot be used to build an indexable pack.");
1823
1824         prepare_packed_git();
1825
1826         if (progress)
1827                 start_progress(&progress_state, "Generating pack...",
1828                                "Counting objects: ", 0);
1829         if (!use_internal_rev_list)
1830                 read_object_list_from_stdin();
1831         else {
1832                 rp_av[rp_ac] = NULL;
1833                 get_object_list(rp_ac, rp_av);
1834         }
1835         if (progress) {
1836                 stop_progress(&progress_state);
1837                 fprintf(stderr, "Done counting %u objects.\n", nr_objects);
1838         }
1839
1840         if (non_empty && !nr_result)
1841                 return 0;
1842         if (progress && (nr_objects != nr_result))
1843                 fprintf(stderr, "Result has %u objects.\n", nr_result);
1844         if (nr_result)
1845                 prepare_pack(window, depth);
1846         write_pack_file();
1847         if (progress)
1848                 fprintf(stderr, "Total %u (delta %u), reused %u (delta %u)\n",
1849                         written, written_delta, reused, reused_delta);
1850         return 0;
1851 }