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