10 #include "csum-file.h"
11 #include "tree-walk.h"
14 #include "list-objects.h"
16 static const char pack_usage
[] = "\
17 git-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\
20 [--revs [--unpacked | --all]*] [--reflog] [--stdout | base-name] \n\
21 [<ref-list | <object-list]";
24 unsigned char sha1
[20];
25 unsigned long size
; /* uncompressed size */
26 off_t offset
; /* offset into the final pack file;
27 * nonzero if already written.
29 unsigned int depth
; /* delta depth */
30 unsigned int hash
; /* name hint hash */
31 enum object_type type
;
32 enum object_type in_pack_type
; /* could be delta */
33 unsigned long delta_size
; /* delta data size (uncompressed) */
34 #define in_pack_header_size delta_size /* only when reusing pack data */
35 struct object_entry
*delta
; /* delta base object */
36 struct packed_git
*in_pack
; /* already in pack */
38 struct object_entry
*delta_child
; /* deltified objects who bases me */
39 struct object_entry
*delta_sibling
; /* other deltified objects who
40 * uses the same base as me
42 int preferred_base
; /* we do not pack this, but is encouraged to
43 * be used as the base objectto delta huge
46 uint32_t crc32
; /* crc of raw pack data for this object */
50 * Objects we are going to pack are collected in objects array (dynamically
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.
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()
62 static unsigned char object_list_sha1
[20];
64 static int no_reuse_delta
;
66 static int incremental
;
67 static int allow_ofs_delta
;
69 static struct object_entry
**sorted_by_sha
;
70 static struct object_entry
*objects
;
71 static uint32_t nr_objects
, nr_alloc
, nr_result
;
72 static const char *base_name
;
73 static unsigned char pack_file_sha1
[20];
74 static int progress
= 1;
75 static volatile sig_atomic_t progress_update
;
76 static int window
= 10;
77 static int pack_to_stdout
;
78 static int num_preferred_base
;
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.
86 static int *object_ix
;
87 static int object_ix_hashsz
;
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
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.
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.
103 struct revindex_entry
{
107 struct pack_revindex
{
108 struct packed_git
*p
;
109 struct revindex_entry
*revindex
;
111 static struct pack_revindex
*pack_revindex
;
112 static int pack_revindex_hashsz
;
117 static uint32_t written
, written_delta
;
118 static uint32_t reused
, reused_delta
;
120 static int pack_revindex_ix(struct packed_git
*p
)
122 unsigned long ui
= (unsigned long)p
;
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
)
130 if (++i
== pack_revindex_hashsz
)
136 static void prepare_pack_ix(void)
139 struct packed_git
*p
;
140 for (num
= 0, p
= packed_git
; p
; p
= p
->next
)
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
);
149 pack_revindex
[num
].p
= p
;
151 /* revindex elements are lazily initialized */
154 static int cmp_offset(const void *a_
, const void *b_
)
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;
162 * Ordered list of offsets of objects in the pack.
164 static void prepare_pack_revindex(struct pack_revindex
*rix
)
166 struct packed_git
*p
= rix
->p
;
167 int num_ent
= p
->num_objects
;
169 const char *index
= p
->index_data
;
171 rix
->revindex
= xmalloc(sizeof(*rix
->revindex
) * (num_ent
+ 1));
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
;
183 rix
->revindex
[i
].offset
=
184 ((uint64_t)ntohl(*off_64
++)) << 32;
185 rix
->revindex
[i
].offset
|=
188 rix
->revindex
[i
].nr
= i
;
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
;
198 /* This knows the pack format -- the 20-byte trailer
199 * follows immediately after the last object data.
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
);
206 static struct revindex_entry
* find_packed_object(struct packed_git
*p
,
211 struct pack_revindex
*rix
;
212 struct revindex_entry
*revindex
;
213 num
= pack_revindex_ix(p
);
215 die("internal error: pack revindex uninitialized");
216 rix
= &pack_revindex
[num
];
218 prepare_pack_revindex(rix
);
219 revindex
= rix
->revindex
;
221 hi
= p
->num_objects
+ 1;
223 int mi
= (lo
+ hi
) / 2;
224 if (revindex
[mi
].offset
== ofs
) {
225 return revindex
+ mi
;
227 else if (ofs
< revindex
[mi
].offset
)
232 die("internal error: pack revindex corrupt");
235 static const unsigned char *find_packed_object_name(struct packed_git
*p
,
238 struct revindex_entry
*entry
= find_packed_object(p
, ofs
);
239 return nth_packed_object_sha1(p
, entry
->nr
);
242 static void *delta_against(void *buf
, unsigned long size
, struct object_entry
*entry
)
244 unsigned long othersize
, delta_size
;
245 enum object_type type
;
246 void *otherbuf
= read_sha1_file(entry
->delta
->sha1
, &type
, &othersize
);
250 die("unable to read %s", sha1_to_hex(entry
->delta
->sha1
));
251 delta_buf
= diff_delta(otherbuf
, othersize
,
252 buf
, size
, &delta_size
, 0);
253 if (!delta_buf
|| delta_size
!= entry
->delta_size
)
254 die("delta size changed");
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"
267 static int encode_header(enum object_type type
, unsigned long size
, unsigned char *hdr
)
272 if (type
< OBJ_COMMIT
|| type
> OBJ_REF_DELTA
)
273 die("bad type %d", type
);
275 c
= (type
<< 4) | (size
& 15);
288 * we are going to reuse the existing object data as is. make
289 * sure it is not corrupt.
291 static int check_pack_inflate(struct packed_git
*p
,
292 struct pack_window
**w_curs
,
295 unsigned long expect
)
298 unsigned char fakebuf
[4096], *in
;
301 memset(&stream
, 0, sizeof(stream
));
302 inflateInit(&stream
);
304 in
= use_pack(p
, w_curs
, offset
, &stream
.avail_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
);
312 return (st
== Z_STREAM_END
&&
313 stream
.total_out
== expect
&&
314 stream
.total_in
== len
) ? 0 : -1;
317 static int check_pack_crc(struct packed_git
*p
, struct pack_window
**w_curs
,
318 off_t offset
, off_t len
, unsigned int nr
)
320 const uint32_t *index_crc
;
321 uint32_t data_crc
= crc32(0, Z_NULL
, 0);
325 void *data
= use_pack(p
, w_curs
, offset
, &avail
);
328 data_crc
= crc32(data_crc
, data
, avail
);
333 index_crc
= p
->index_data
;
334 index_crc
+= 2 + 256 + p
->num_objects
* (20/4) + nr
;
336 return data_crc
!= ntohl(*index_crc
);
339 static void copy_pack_data(struct sha1file
*f
,
340 struct packed_git
*p
,
341 struct pack_window
**w_curs
,
349 in
= use_pack(p
, w_curs
, offset
, &avail
);
351 avail
= (unsigned int)len
;
352 sha1write(f
, in
, avail
);
358 static int check_loose_inflate(unsigned char *data
, unsigned long len
, unsigned long expect
)
361 unsigned char fakebuf
[4096];
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
);
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;
378 if (st
!= Z_BUF_ERROR
) {
382 stream
.next_out
= fakebuf
;
383 stream
.avail_out
= sizeof(fakebuf
);
389 static int revalidate_loose_object(struct object_entry
*entry
,
391 unsigned long mapsize
)
393 /* we already know this is a loose object with new type header. */
394 enum object_type type
;
395 unsigned long size
, used
;
400 used
= unpack_object_header_gently(map
, mapsize
, &type
, &size
);
405 return check_loose_inflate(map
, mapsize
, size
);
408 static unsigned long write_object(struct sha1file
*f
,
409 struct object_entry
*entry
)
412 enum object_type type
;
414 unsigned char header
[10];
417 enum object_type obj_type
;
423 obj_type
= entry
->type
;
424 if (! entry
->in_pack
)
425 to_reuse
= 0; /* can't reuse what we don't have */
426 else if (obj_type
== OBJ_REF_DELTA
|| obj_type
== OBJ_OFS_DELTA
)
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 */
433 to_reuse
= 1; /* we have it in-pack undeltified,
434 * and we do not need to deltify it.
437 if (!entry
->in_pack
&& !entry
->delta
) {
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 */
443 if (revalidate_loose_object(entry
, map
, mapsize
))
444 die("corrupt loose object %s",
445 sha1_to_hex(entry
->sha1
));
446 sha1write(f
, map
, mapsize
);
447 munmap(map
, mapsize
);
453 munmap(map
, mapsize
);
457 buf
= read_sha1_file(entry
->sha1
, &type
, &size
);
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
);
464 buf
= delta_against(buf
, size
, entry
);
465 size
= entry
->delta_size
;
466 obj_type
= (allow_ofs_delta
&& entry
->delta
->offset
) ?
467 OBJ_OFS_DELTA
: OBJ_REF_DELTA
;
470 * The object header is a byte of 'type' followed by zero or
471 * more bytes of length.
473 hdrlen
= encode_header(obj_type
, size
, header
);
474 sha1write(f
, header
, hdrlen
);
476 if (obj_type
== OBJ_OFS_DELTA
) {
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.
482 off_t ofs
= entry
->offset
- entry
->delta
->offset
;
483 unsigned pos
= sizeof(header
) - 1;
484 header
[pos
] = ofs
& 127;
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
) {
491 * Deltas with a base reference contain
492 * an additional 20 bytes for the base sha1.
494 sha1write(f
, entry
->delta
->sha1
, 20);
497 datalen
= sha1write_compressed(f
, buf
, size
);
501 struct packed_git
*p
= entry
->in_pack
;
502 struct pack_window
*w_curs
= NULL
;
503 struct revindex_entry
*revidx
;
507 obj_type
= (allow_ofs_delta
&& entry
->delta
->offset
) ?
508 OBJ_OFS_DELTA
: OBJ_REF_DELTA
;
511 hdrlen
= encode_header(obj_type
, entry
->size
, header
);
512 sha1write(f
, header
, hdrlen
);
513 if (obj_type
== OBJ_OFS_DELTA
) {
514 off_t ofs
= entry
->offset
- entry
->delta
->offset
;
515 unsigned pos
= sizeof(header
) - 1;
516 header
[pos
] = ofs
& 127;
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);
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
));
537 copy_pack_data(f
, p
, &w_curs
, offset
, datalen
);
545 entry
->crc32
= crc32_end(f
);
546 return hdrlen
+ datalen
;
549 static off_t
write_one(struct sha1file
*f
,
550 struct object_entry
*e
,
555 /* offset is non zero if object is written already. */
556 if (e
->offset
|| e
->preferred_base
)
559 /* if we are deltified, write out base object first. */
561 offset
= write_one(f
, e
->delta
, offset
);
564 size
= write_object(f
, e
);
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
;
572 static off_t
write_pack_file(void)
576 off_t offset
, last_obj_offset
= 0;
577 struct pack_header hdr
;
578 unsigned last_percent
= 999;
579 int do_progress
= progress
;
582 f
= sha1fd(1, "<stdout>");
586 f
= sha1create("%s-%s.%s", base_name
,
587 sha1_to_hex(object_list_sha1
), "pack");
589 fprintf(stderr
, "Writing %u objects.\n", nr_result
);
591 hdr
.hdr_signature
= htonl(PACK_SIGNATURE
);
592 hdr
.hdr_version
= htonl(PACK_VERSION
);
593 hdr
.hdr_entries
= htonl(nr_result
);
594 sha1write(f
, &hdr
, sizeof(hdr
));
595 offset
= sizeof(hdr
);
598 for (i
= 0; i
< nr_objects
; i
++) {
599 last_obj_offset
= offset
;
600 offset
= write_one(f
, objects
+ i
, offset
);
602 unsigned percent
= written
* 100 / nr_result
;
603 if (progress_update
|| percent
!= last_percent
) {
604 fprintf(stderr
, "%4u%% (%u/%u) done\r",
605 percent
, written
, nr_result
);
607 last_percent
= percent
;
614 if (written
!= nr_result
)
615 die("wrote %u objects while expecting %u", written
, nr_result
);
616 sha1close(f
, pack_file_sha1
, 1);
618 return last_obj_offset
;
621 static uint32_t index_default_version
= 1;
622 static uint32_t index_off32_limit
= 0x7fffffff;
624 static void write_index_file(off_t last_obj_offset
)
627 struct sha1file
*f
= sha1create("%s-%s.%s", base_name
,
628 sha1_to_hex(object_list_sha1
), "idx");
629 struct object_entry
**list
= sorted_by_sha
;
630 struct object_entry
**last
= list
+ nr_result
;
632 uint32_t index_version
;
634 /* if last object's offset is >= 2^31 we should use index V2 */
635 index_version
= (last_obj_offset
>> 31) ? 2 : index_default_version
;
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
));
646 * Write the first-level table (the list is sorted,
647 * but we use a 256-entry lookup to be able to avoid
648 * having to do eight extra binary search iterations).
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
)
658 array
[i
] = htonl(next
- sorted_by_sha
);
661 sha1write(f
, array
, 256 * 4);
664 * Write the actual SHA1 entries..
666 list
= sorted_by_sha
;
667 for (i
= 0; i
< nr_result
; i
++) {
668 struct object_entry
*entry
= *list
++;
669 if (index_version
< 2) {
670 uint32_t offset
= htonl(entry
->offset
);
671 sha1write(f
, &offset
, 4);
673 sha1write(f
, entry
->sha1
, 20);
676 if (index_version
>= 2) {
677 unsigned int nr_large_offset
= 0;
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);
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
++;
691 uint32_t offset
= (entry
->offset
<= index_off32_limit
) ?
692 entry
->offset
: (0x80000000 | nr_large_offset
++);
693 offset
= htonl(offset
);
694 sha1write(f
, &offset
, 4);
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
;
702 if (offset
> index_off32_limit
) {
704 split
[0] = htonl(offset
>> 32);
705 split
[1] = htonl(offset
& 0xffffffff);
706 sha1write(f
, split
, 8);
712 sha1write(f
, pack_file_sha1
, 20);
713 sha1close(f
, NULL
, 1);
716 static int locate_object_entry_hash(const unsigned char *sha1
)
720 memcpy(&ui
, sha1
, sizeof(unsigned int));
721 i
= ui
% object_ix_hashsz
;
722 while (0 < object_ix
[i
]) {
723 if (!hashcmp(sha1
, objects
[object_ix
[i
] - 1].sha1
))
725 if (++i
== object_ix_hashsz
)
731 static struct object_entry
*locate_object_entry(const unsigned char *sha1
)
735 if (!object_ix_hashsz
)
738 i
= locate_object_entry_hash(sha1
);
740 return &objects
[object_ix
[i
]-1];
744 static void rehash_objects(void)
747 struct object_entry
*oe
;
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
);
753 memset(object_ix
, 0, sizeof(int) * object_ix_hashsz
);
754 for (i
= 0, oe
= objects
; i
< nr_objects
; i
++, oe
++) {
755 int ix
= locate_object_entry_hash(oe
->sha1
);
759 object_ix
[ix
] = i
+ 1;
763 static unsigned name_hash(const char *name
)
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.
773 while ((c
= *name
++) != 0) {
776 hash
= (hash
>> 2) + (c
<< 24);
781 static int add_object_entry(const unsigned char *sha1
, unsigned hash
, int exclude
)
783 struct object_entry
*entry
;
784 struct packed_git
*p
, *found_pack
= NULL
;
785 off_t found_offset
= 0;
788 ix
= nr_objects
? locate_object_entry_hash(sha1
) : -1;
791 entry
= objects
+ object_ix
[ix
] - 1;
792 entry
->preferred_base
= 1;
798 for (p
= packed_git
; p
; p
= p
->next
) {
799 off_t offset
= find_pack_entry_one(sha1
, p
);
803 if (local
&& !p
->pack_local
)
806 found_offset
= offset
;
813 if (nr_objects
>= nr_alloc
) {
814 nr_alloc
= (nr_alloc
+ 1024) * 3 / 2;
815 objects
= xrealloc(objects
, nr_alloc
* sizeof(*entry
));
818 entry
= objects
+ nr_objects
++;
819 memset(entry
, 0, sizeof(*entry
));
820 hashcpy(entry
->sha1
, sha1
);
823 entry
->preferred_base
= 1;
825 entry
->in_pack
= found_pack
;
826 entry
->in_pack_offset
= found_offset
;
829 if (object_ix_hashsz
* 3 <= nr_objects
* 4)
832 object_ix
[-1 - ix
] = nr_objects
;
834 if (progress_update
) {
835 fprintf(stderr
, "Counting objects...%u\r", nr_objects
);
842 struct pbase_tree_cache
{
843 unsigned char sha1
[20];
847 unsigned long tree_size
;
850 static struct pbase_tree_cache
*(pbase_tree_cache
[256]);
851 static int pbase_tree_cache_ix(const unsigned char *sha1
)
853 return sha1
[0] % ARRAY_SIZE(pbase_tree_cache
);
855 static int pbase_tree_cache_ix_incr(int ix
)
857 return (ix
+1) % ARRAY_SIZE(pbase_tree_cache
);
860 static 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.
867 struct pbase_tree_cache pcache
;
870 static struct pbase_tree_cache
*pbase_tree_get(const unsigned char *sha1
)
872 struct pbase_tree_cache
*ent
, *nent
;
875 enum object_type type
;
877 int my_ix
= pbase_tree_cache_ix(sha1
);
878 int available_ix
= -1;
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.
884 for (neigh
= 0; neigh
< 8; neigh
++) {
885 ent
= pbase_tree_cache
[my_ix
];
886 if (ent
&& !hashcmp(ent
->sha1
, sha1
)) {
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
;
896 my_ix
= pbase_tree_cache_ix_incr(my_ix
);
899 /* Did not find one. Either we got a bogus request or
900 * we need to read and perhaps cache.
902 data
= read_sha1_file(sha1
, &type
, &size
);
905 if (type
!= OBJ_TREE
) {
910 /* We need to either cache or return a throwaway copy */
912 if (available_ix
< 0)
915 ent
= pbase_tree_cache
[available_ix
];
916 my_ix
= available_ix
;
920 nent
= xmalloc(sizeof(*nent
));
921 nent
->temporary
= (available_ix
< 0);
924 /* evict and reuse */
925 free(ent
->tree_data
);
928 hashcpy(nent
->sha1
, sha1
);
929 nent
->tree_data
= data
;
930 nent
->tree_size
= size
;
932 if (!nent
->temporary
)
933 pbase_tree_cache
[my_ix
] = nent
;
937 static void pbase_tree_put(struct pbase_tree_cache
*cache
)
939 if (!cache
->temporary
) {
943 free(cache
->tree_data
);
947 static int name_cmp_len(const char *name
)
950 for (i
= 0; name
[i
] && name
[i
] != '\n' && name
[i
] != '/'; i
++)
955 static void add_pbase_object(struct tree_desc
*tree
,
958 const char *fullname
)
960 struct name_entry entry
;
963 while (tree_entry(tree
,&entry
)) {
964 cmp
= tree_entry_len(entry
.path
, entry
.sha1
) != cmplen
? 1 :
965 memcmp(name
, entry
.path
, cmplen
);
970 if (name
[cmplen
] != '/') {
971 unsigned hash
= name_hash(fullname
);
972 add_object_entry(entry
.sha1
, hash
, 1);
975 if (S_ISDIR(entry
.mode
)) {
976 struct tree_desc sub
;
977 struct pbase_tree_cache
*tree
;
978 const char *down
= name
+cmplen
+1;
979 int downlen
= name_cmp_len(down
);
981 tree
= pbase_tree_get(entry
.sha1
);
984 init_tree_desc(&sub
, tree
->tree_data
, tree
->tree_size
);
986 add_pbase_object(&sub
, down
, downlen
, fullname
);
987 pbase_tree_put(tree
);
992 static unsigned *done_pbase_paths
;
993 static int done_pbase_paths_num
;
994 static int done_pbase_paths_alloc
;
995 static int done_pbase_path_pos(unsigned hash
)
998 int hi
= done_pbase_paths_num
;
1000 int mi
= (hi
+ lo
) / 2;
1001 if (done_pbase_paths
[mi
] == hash
)
1003 if (done_pbase_paths
[mi
] < hash
)
1011 static int check_pbase_path(unsigned hash
)
1013 int pos
= (!done_pbase_paths
) ? -1 : done_pbase_path_pos(hash
);
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
*
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
;
1032 static void add_preferred_base_object(const char *name
, unsigned hash
)
1034 struct pbase_tree
*it
;
1037 if (!num_preferred_base
|| check_pbase_path(hash
))
1040 cmplen
= name_cmp_len(name
);
1041 for (it
= pbase_tree
; it
; it
= it
->next
) {
1043 add_object_entry(it
->pcache
.sha1
, 0, 1);
1046 struct tree_desc tree
;
1047 init_tree_desc(&tree
, it
->pcache
.tree_data
, it
->pcache
.tree_size
);
1048 add_pbase_object(&tree
, name
, cmplen
, name
);
1053 static void add_preferred_base(unsigned char *sha1
)
1055 struct pbase_tree
*it
;
1058 unsigned char tree_sha1
[20];
1060 if (window
<= num_preferred_base
++)
1063 data
= read_object_with_reference(sha1
, tree_type
, &size
, tree_sha1
);
1067 for (it
= pbase_tree
; it
; it
= it
->next
) {
1068 if (!hashcmp(it
->pcache
.sha1
, tree_sha1
)) {
1074 it
= xcalloc(1, sizeof(*it
));
1075 it
->next
= pbase_tree
;
1078 hashcpy(it
->pcache
.sha1
, tree_sha1
);
1079 it
->pcache
.tree_data
= data
;
1080 it
->pcache
.tree_size
= size
;
1083 static void check_object(struct object_entry
*entry
)
1085 if (entry
->in_pack
&& !entry
->preferred_base
) {
1086 struct packed_git
*p
= entry
->in_pack
;
1087 struct pack_window
*w_curs
= NULL
;
1088 unsigned long size
, used
;
1091 struct object_entry
*base_entry
= NULL
;
1093 buf
= use_pack(p
, &w_curs
, entry
->in_pack_offset
, &avail
);
1095 /* We want in_pack_type even if we do not reuse delta.
1096 * There is no point not reusing non-delta representations.
1098 used
= unpack_object_header_gently(buf
, avail
,
1099 &entry
->in_pack_type
, &size
);
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
1105 if (!no_reuse_delta
) {
1107 const unsigned char *base_name
;
1109 unsigned long used_0
;
1110 /* there is at least 20 bytes left in the pack */
1111 switch (entry
->in_pack_type
) {
1113 base_name
= use_pack(p
, &w_curs
,
1114 entry
->in_pack_offset
+ used
, NULL
);
1118 buf
= use_pack(p
, &w_curs
,
1119 entry
->in_pack_offset
+ used
, NULL
);
1125 if (!ofs
|| MSB(ofs
, 7))
1126 die("delta base offset overflow in pack for %s",
1127 sha1_to_hex(entry
->sha1
));
1129 ofs
= (ofs
<< 7) + (c
& 127);
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
);
1142 base_entry
= locate_object_entry(base_name
);
1144 unuse_pack(&w_curs
);
1145 entry
->in_pack_header_size
= used
;
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.
1155 /* uncompressed size of the delta data */
1157 entry
->delta
= base_entry
;
1158 entry
->type
= entry
->in_pack_type
;
1160 entry
->delta_sibling
= base_entry
->delta_child
;
1161 base_entry
->delta_child
= entry
;
1165 /* Otherwise we would do the usual */
1168 entry
->type
= sha1_object_info(entry
->sha1
, &entry
->size
);
1169 if (entry
->type
< 0)
1170 die("unable to get type of object %s",
1171 sha1_to_hex(entry
->sha1
));
1174 static void get_object_details(void)
1177 struct object_entry
*entry
;
1180 for (i
= 0, entry
= objects
; i
< nr_objects
; i
++, entry
++)
1181 check_object(entry
);
1184 static int sha1_sort(const void *_a
, const void *_b
)
1186 const struct object_entry
*a
= *(struct object_entry
**)_a
;
1187 const struct object_entry
*b
= *(struct object_entry
**)_b
;
1188 return hashcmp(a
->sha1
, b
->sha1
);
1191 static struct object_entry
**create_final_object_list(void)
1193 struct object_entry
**list
;
1196 for (i
= nr_result
= 0; i
< nr_objects
; i
++)
1197 if (!objects
[i
].preferred_base
)
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
;
1204 qsort(list
, nr_result
, sizeof(struct object_entry
*), sha1_sort
);
1208 static int type_size_sort(const void *_a
, const void *_b
)
1210 const struct object_entry
*a
= *(struct object_entry
**)_a
;
1211 const struct object_entry
*b
= *(struct object_entry
**)_b
;
1213 if (a
->type
< b
->type
)
1215 if (a
->type
> b
->type
)
1217 if (a
->hash
< b
->hash
)
1219 if (a
->hash
> b
->hash
)
1221 if (a
->preferred_base
< b
->preferred_base
)
1223 if (a
->preferred_base
> b
->preferred_base
)
1225 if (a
->size
< b
->size
)
1227 if (a
->size
> b
->size
)
1229 return a
> b
? -1 : (a
< b
); /* newest last */
1233 struct object_entry
*entry
;
1235 struct delta_index
*index
;
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
1246 static int try_delta(struct unpacked
*trg
, struct unpacked
*src
,
1249 struct object_entry
*trg_entry
= trg
->entry
;
1250 struct object_entry
*src_entry
= src
->entry
;
1251 unsigned long trg_size
, src_size
, delta_size
, sizediff
, max_size
, sz
;
1252 enum object_type type
;
1255 /* Don't bother doing diffs between different types */
1256 if (trg_entry
->type
!= src_entry
->type
)
1259 /* We do not compute delta to *create* objects we are not
1262 if (trg_entry
->preferred_base
)
1266 * We do not bother to try a delta that we discarded
1267 * on an earlier try, but only when reusing delta data.
1269 if (!no_reuse_delta
&& trg_entry
->in_pack
&&
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
)
1275 /* Let's not bust the allowed depth. */
1276 if (src_entry
->depth
>= max_depth
)
1279 /* Now some size filtering heuristics. */
1280 trg_size
= trg_entry
->size
;
1281 max_size
= trg_size
/2 - 20;
1282 max_size
= max_size
* (max_depth
- src_entry
->depth
) / max_depth
;
1285 if (trg_entry
->delta
&& trg_entry
->delta_size
<= max_size
)
1286 max_size
= trg_entry
->delta_size
-1;
1287 src_size
= src_entry
->size
;
1288 sizediff
= src_size
< trg_size
? trg_size
- src_size
: 0;
1289 if (sizediff
>= max_size
)
1292 /* Load data if not already done */
1294 trg
->data
= read_sha1_file(trg_entry
->sha1
, &type
, &sz
);
1296 die("object %s inconsistent object length (%lu vs %lu)",
1297 sha1_to_hex(trg_entry
->sha1
), sz
, trg_size
);
1300 src
->data
= read_sha1_file(src_entry
->sha1
, &type
, &sz
);
1302 die("object %s inconsistent object length (%lu vs %lu)",
1303 sha1_to_hex(src_entry
->sha1
), sz
, src_size
);
1306 src
->index
= create_delta_index(src
->data
, src_size
);
1308 die("out of memory");
1311 delta_buf
= create_delta(src
->index
, trg
->data
, trg_size
, &delta_size
, max_size
);
1315 trg_entry
->delta
= src_entry
;
1316 trg_entry
->delta_size
= delta_size
;
1317 trg_entry
->depth
= src_entry
->depth
+ 1;
1322 static unsigned int check_delta_limit(struct object_entry
*me
, unsigned int n
)
1324 struct object_entry
*child
= me
->delta_child
;
1327 unsigned int c
= check_delta_limit(child
, n
+ 1);
1330 child
= child
->delta_sibling
;
1335 static void find_deltas(struct object_entry
**list
, int window
, int depth
)
1337 uint32_t i
= nr_objects
, idx
= 0, processed
= 0;
1338 unsigned int array_size
= window
* sizeof(struct unpacked
);
1339 struct unpacked
*array
;
1340 unsigned last_percent
= 999;
1345 array
= xmalloc(array_size
);
1346 memset(array
, 0, array_size
);
1348 fprintf(stderr
, "Deltifying %u objects.\n", nr_result
);
1351 struct object_entry
*entry
= list
[--i
];
1352 struct unpacked
*n
= array
+ idx
;
1355 if (!entry
->preferred_base
)
1359 unsigned percent
= processed
* 100 / nr_result
;
1360 if (percent
!= last_percent
|| progress_update
) {
1361 fprintf(stderr
, "%4u%% (%u/%u) done\r",
1362 percent
, processed
, nr_result
);
1363 progress_update
= 0;
1364 last_percent
= percent
;
1369 /* This happens if we decided to reuse existing
1370 * delta from a pack. "!no_reuse_delta &&" is implied.
1374 if (entry
->size
< 50)
1376 free_delta_index(n
->index
);
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.
1388 if (entry
->delta_child
) {
1389 max_depth
-= check_delta_limit(entry
, 0);
1396 uint32_t other_idx
= idx
+ j
;
1398 if (other_idx
>= window
)
1399 other_idx
-= window
;
1400 m
= array
+ other_idx
;
1403 if (try_delta(n
, m
, max_depth
) < 0)
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.
1411 if (entry
->delta
&& depth
<= entry
->depth
)
1421 fputc('\n', stderr
);
1423 for (i
= 0; i
< window
; ++i
) {
1424 free_delta_index(array
[i
].index
);
1425 free(array
[i
].data
);
1430 static void prepare_pack(int window
, int depth
)
1432 struct object_entry
**delta_list
;
1435 get_object_details();
1437 if (!window
|| !depth
)
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
);
1448 static void progress_interval(int signum
)
1450 progress_update
= 1;
1453 static void setup_progress_signal(void)
1455 struct sigaction sa
;
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
);
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
);
1470 static int git_pack_config(const char *k
, const char *v
)
1472 if(!strcmp(k
, "pack.window")) {
1473 window
= git_config_int(k
, v
);
1476 return git_default_config(k
, v
);
1479 static void read_object_list_from_stdin(void)
1481 char line
[40 + 1 + PATH_MAX
+ 2];
1482 unsigned char sha1
[20];
1486 if (!fgets(line
, sizeof(line
), stdin
)) {
1490 die("fgets returned NULL, not EOF, not error!");
1492 die("fgets: %s", strerror(errno
));
1496 if (line
[0] == '-') {
1497 if (get_sha1_hex(line
+1, sha1
))
1498 die("expected edge sha1, got garbage:\n %s",
1500 add_preferred_base(sha1
);
1503 if (get_sha1_hex(line
, sha1
))
1504 die("expected sha1, got garbage:\n %s", line
);
1506 hash
= name_hash(line
+41);
1507 add_preferred_base_object(line
+41, hash
);
1508 add_object_entry(sha1
, hash
, 0);
1512 static void show_commit(struct commit
*commit
)
1514 add_object_entry(commit
->object
.sha1
, 0, 0);
1517 static void show_object(struct object_array_entry
*p
)
1519 unsigned hash
= name_hash(p
->name
);
1520 add_preferred_base_object(p
->name
, hash
);
1521 add_object_entry(p
->item
->sha1
, hash
, 0);
1524 static void show_edge(struct commit
*commit
)
1526 add_preferred_base(commit
->object
.sha1
);
1529 static void get_object_list(int ac
, const char **av
)
1531 struct rev_info revs
;
1535 init_revisions(&revs
, NULL
);
1536 save_commit_buffer
= 0;
1537 track_object_refs
= 0;
1538 setup_revisions(ac
, av
, &revs
, NULL
);
1540 while (fgets(line
, sizeof(line
), stdin
) != NULL
) {
1541 int len
= strlen(line
);
1542 if (line
[len
- 1] == '\n')
1547 if (!strcmp(line
, "--not")) {
1548 flags
^= UNINTERESTING
;
1551 die("not a rev '%s'", line
);
1553 if (handle_revision_arg(line
, &revs
, flags
, 1))
1554 die("bad revision '%s'", line
);
1557 prepare_revision_walk(&revs
);
1558 mark_edges_uninteresting(revs
.commits
, &revs
, show_edge
);
1559 traverse_commit_list(&revs
, show_commit
, show_object
);
1562 int cmd_pack_objects(int argc
, const char **argv
, const char *prefix
)
1566 struct object_entry
**list
;
1567 off_t last_obj_offset
;
1568 int use_internal_rev_list
= 0;
1572 int rp_ac_alloc
= 64;
1575 rp_av
= xcalloc(rp_ac_alloc
, sizeof(*rp_av
));
1577 rp_av
[0] = "pack-objects";
1578 rp_av
[1] = "--objects"; /* --thin will make it --objects-edge */
1581 git_config(git_pack_config
);
1583 progress
= isatty(2);
1584 for (i
= 1; i
< argc
; i
++) {
1585 const char *arg
= argv
[i
];
1590 if (!strcmp("--non-empty", arg
)) {
1594 if (!strcmp("--local", arg
)) {
1598 if (!strcmp("--incremental", arg
)) {
1602 if (!prefixcmp(arg
, "--window=")) {
1604 window
= strtoul(arg
+9, &end
, 0);
1605 if (!arg
[9] || *end
)
1609 if (!prefixcmp(arg
, "--depth=")) {
1611 depth
= strtoul(arg
+8, &end
, 0);
1612 if (!arg
[8] || *end
)
1616 if (!strcmp("--progress", arg
)) {
1620 if (!strcmp("--all-progress", arg
)) {
1624 if (!strcmp("-q", arg
)) {
1628 if (!strcmp("--no-reuse-delta", arg
)) {
1632 if (!strcmp("--delta-base-offset", arg
)) {
1633 allow_ofs_delta
= 1;
1636 if (!strcmp("--stdout", arg
)) {
1640 if (!strcmp("--revs", arg
)) {
1641 use_internal_rev_list
= 1;
1644 if (!strcmp("--unpacked", arg
) ||
1645 !prefixcmp(arg
, "--unpacked=") ||
1646 !strcmp("--reflog", arg
) ||
1647 !strcmp("--all", arg
)) {
1648 use_internal_rev_list
= 1;
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
));
1654 rp_av
[rp_ac
++] = arg
;
1657 if (!strcmp("--thin", arg
)) {
1658 use_internal_rev_list
= 1;
1660 rp_av
[1] = "--objects-edge";
1663 if (!prefixcmp(arg
, "--index-version=")) {
1665 index_default_version
= strtoul(arg
+ 16, &c
, 10);
1666 if (index_default_version
> 2)
1669 index_off32_limit
= strtoul(c
+1, &c
, 0);
1670 if (*c
|| index_off32_limit
& 0x80000000)
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
1683 * pack-objects [options] base <refs...>
1685 * in other words, we would treat the first non-option as the
1686 * base_name and send everything else to the internal revision
1690 if (!pack_to_stdout
)
1691 base_name
= argv
[i
++];
1693 if (pack_to_stdout
!= !base_name
)
1696 if (!pack_to_stdout
&& thin
)
1697 die("--thin cannot be used to build an indexable pack.");
1699 prepare_packed_git();
1702 fprintf(stderr
, "Generating pack...\n");
1703 setup_progress_signal();
1706 if (!use_internal_rev_list
)
1707 read_object_list_from_stdin();
1709 rp_av
[rp_ac
] = NULL
;
1710 get_object_list(rp_ac
, rp_av
);
1714 fprintf(stderr
, "Done counting %u objects.\n", nr_objects
);
1715 sorted_by_sha
= create_final_object_list();
1716 if (non_empty
&& !nr_result
)
1720 list
= sorted_by_sha
;
1721 for (i
= 0; i
< nr_result
; i
++) {
1722 struct object_entry
*entry
= *list
++;
1723 SHA1_Update(&ctx
, entry
->sha1
, 20);
1725 SHA1_Final(object_list_sha1
, &ctx
);
1726 if (progress
&& (nr_objects
!= nr_result
))
1727 fprintf(stderr
, "Result has %u objects.\n", 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;
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
));
1744 fprintf(stderr
, "Total %u (delta %u), reused %u (delta %u)\n",
1745 written
, written_delta
, reused
, reused_delta
);