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