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 delta_limit
; /* base adjustment for in-pack delta */
31 unsigned int hash
; /* name hint hash */
32 enum object_type type
;
33 enum object_type in_pack_type
; /* could be delta */
34 unsigned long delta_size
; /* delta data size (uncompressed) */
35 #define in_pack_header_size delta_size /* only when reusing pack data */
36 struct object_entry
*delta
; /* delta base object */
37 struct packed_git
*in_pack
; /* already in pack */
39 struct object_entry
*delta_child
; /* deltified objects who bases me */
40 struct object_entry
*delta_sibling
; /* other deltified objects who
41 * uses the same base as me
43 int preferred_base
; /* we do not pack this, but is encouraged to
44 * be used as the base objectto delta huge
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
, **sorted_by_type
;
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
;
172 rix
->revindex
= xmalloc(sizeof(*rix
->revindex
) * (num_ent
+ 1));
173 for (i
= 0; i
< num_ent
; i
++) {
174 uint32_t hl
= *((uint32_t *)(index
+ 24 * i
));
175 rix
->revindex
[i
].offset
= ntohl(hl
);
176 rix
->revindex
[i
].nr
= i
;
178 /* This knows the pack format -- the 20-byte trailer
179 * follows immediately after the last object data.
181 rix
->revindex
[num_ent
].offset
= p
->pack_size
- 20;
182 rix
->revindex
[num_ent
].nr
= -1;
183 qsort(rix
->revindex
, num_ent
, sizeof(*rix
->revindex
), cmp_offset
);
186 static struct revindex_entry
* find_packed_object(struct packed_git
*p
,
191 struct pack_revindex
*rix
;
192 struct revindex_entry
*revindex
;
193 num
= pack_revindex_ix(p
);
195 die("internal error: pack revindex uninitialized");
196 rix
= &pack_revindex
[num
];
198 prepare_pack_revindex(rix
);
199 revindex
= rix
->revindex
;
201 hi
= p
->num_objects
+ 1;
203 int mi
= (lo
+ hi
) / 2;
204 if (revindex
[mi
].offset
== ofs
) {
205 return revindex
+ mi
;
207 else if (ofs
< revindex
[mi
].offset
)
212 die("internal error: pack revindex corrupt");
215 static off_t
find_packed_object_size(struct packed_git
*p
, off_t ofs
)
217 struct revindex_entry
*entry
= find_packed_object(p
, ofs
);
218 return entry
[1].offset
- ofs
;
221 static const unsigned char *find_packed_object_name(struct packed_git
*p
,
224 struct revindex_entry
*entry
= find_packed_object(p
, ofs
);
225 return nth_packed_object_sha1(p
, entry
->nr
);
228 static void *delta_against(void *buf
, unsigned long size
, struct object_entry
*entry
)
230 unsigned long othersize
, delta_size
;
231 enum object_type type
;
232 void *otherbuf
= read_sha1_file(entry
->delta
->sha1
, &type
, &othersize
);
236 die("unable to read %s", sha1_to_hex(entry
->delta
->sha1
));
237 delta_buf
= diff_delta(otherbuf
, othersize
,
238 buf
, size
, &delta_size
, 0);
239 if (!delta_buf
|| delta_size
!= entry
->delta_size
)
240 die("delta size changed");
247 * The per-object header is a pretty dense thing, which is
248 * - first byte: low four bits are "size", then three bits of "type",
249 * and the high bit is "size continues".
250 * - each byte afterwards: low seven bits are size continuation,
251 * with the high bit being "size continues"
253 static int encode_header(enum object_type type
, unsigned long size
, unsigned char *hdr
)
258 if (type
< OBJ_COMMIT
|| type
> OBJ_REF_DELTA
)
259 die("bad type %d", type
);
261 c
= (type
<< 4) | (size
& 15);
274 * we are going to reuse the existing object data as is. make
275 * sure it is not corrupt.
277 static int check_pack_inflate(struct packed_git
*p
,
278 struct pack_window
**w_curs
,
281 unsigned long expect
)
284 unsigned char fakebuf
[4096], *in
;
287 memset(&stream
, 0, sizeof(stream
));
288 inflateInit(&stream
);
290 in
= use_pack(p
, w_curs
, offset
, &stream
.avail_in
);
292 stream
.next_out
= fakebuf
;
293 stream
.avail_out
= sizeof(fakebuf
);
294 st
= inflate(&stream
, Z_FINISH
);
295 offset
+= stream
.next_in
- in
;
296 } while (st
== Z_OK
|| st
== Z_BUF_ERROR
);
298 return (st
== Z_STREAM_END
&&
299 stream
.total_out
== expect
&&
300 stream
.total_in
== len
) ? 0 : -1;
303 static void copy_pack_data(struct sha1file
*f
,
304 struct packed_git
*p
,
305 struct pack_window
**w_curs
,
313 in
= use_pack(p
, w_curs
, offset
, &avail
);
315 avail
= (unsigned int)len
;
316 sha1write(f
, in
, avail
);
322 static int check_loose_inflate(unsigned char *data
, unsigned long len
, unsigned long expect
)
325 unsigned char fakebuf
[4096];
328 memset(&stream
, 0, sizeof(stream
));
329 stream
.next_in
= data
;
330 stream
.avail_in
= len
;
331 stream
.next_out
= fakebuf
;
332 stream
.avail_out
= sizeof(fakebuf
);
333 inflateInit(&stream
);
336 st
= inflate(&stream
, Z_FINISH
);
337 if (st
== Z_STREAM_END
|| st
== Z_OK
) {
338 st
= (stream
.total_out
== expect
&&
339 stream
.total_in
== len
) ? 0 : -1;
342 if (st
!= Z_BUF_ERROR
) {
346 stream
.next_out
= fakebuf
;
347 stream
.avail_out
= sizeof(fakebuf
);
353 static int revalidate_loose_object(struct object_entry
*entry
,
355 unsigned long mapsize
)
357 /* we already know this is a loose object with new type header. */
358 enum object_type type
;
359 unsigned long size
, used
;
364 used
= unpack_object_header_gently(map
, mapsize
, &type
, &size
);
369 return check_loose_inflate(map
, mapsize
, size
);
372 static unsigned long write_object(struct sha1file
*f
,
373 struct object_entry
*entry
)
376 enum object_type type
;
378 unsigned char header
[10];
381 enum object_type obj_type
;
384 obj_type
= entry
->type
;
385 if (! entry
->in_pack
)
386 to_reuse
= 0; /* can't reuse what we don't have */
387 else if (obj_type
== OBJ_REF_DELTA
|| obj_type
== OBJ_OFS_DELTA
)
388 to_reuse
= 1; /* check_object() decided it for us */
389 else if (obj_type
!= entry
->in_pack_type
)
390 to_reuse
= 0; /* pack has delta which is unusable */
391 else if (entry
->delta
)
392 to_reuse
= 0; /* we want to pack afresh */
394 to_reuse
= 1; /* we have it in-pack undeltified,
395 * and we do not need to deltify it.
398 if (!entry
->in_pack
&& !entry
->delta
) {
400 unsigned long mapsize
;
401 map
= map_sha1_file(entry
->sha1
, &mapsize
);
402 if (map
&& !legacy_loose_object(map
)) {
403 /* We can copy straight into the pack file */
404 if (revalidate_loose_object(entry
, map
, mapsize
))
405 die("corrupt loose object %s",
406 sha1_to_hex(entry
->sha1
));
407 sha1write(f
, map
, mapsize
);
408 munmap(map
, mapsize
);
414 munmap(map
, mapsize
);
418 buf
= read_sha1_file(entry
->sha1
, &type
, &size
);
420 die("unable to read %s", sha1_to_hex(entry
->sha1
));
421 if (size
!= entry
->size
)
422 die("object %s size inconsistency (%lu vs %lu)",
423 sha1_to_hex(entry
->sha1
), size
, entry
->size
);
425 buf
= delta_against(buf
, size
, entry
);
426 size
= entry
->delta_size
;
427 obj_type
= (allow_ofs_delta
&& entry
->delta
->offset
) ?
428 OBJ_OFS_DELTA
: OBJ_REF_DELTA
;
431 * The object header is a byte of 'type' followed by zero or
432 * more bytes of length.
434 hdrlen
= encode_header(obj_type
, size
, header
);
435 sha1write(f
, header
, hdrlen
);
437 if (obj_type
== OBJ_OFS_DELTA
) {
439 * Deltas with relative base contain an additional
440 * encoding of the relative offset for the delta
441 * base from this object's position in the pack.
443 off_t ofs
= entry
->offset
- entry
->delta
->offset
;
444 unsigned pos
= sizeof(header
) - 1;
445 header
[pos
] = ofs
& 127;
447 header
[--pos
] = 128 | (--ofs
& 127);
448 sha1write(f
, header
+ pos
, sizeof(header
) - pos
);
449 hdrlen
+= sizeof(header
) - pos
;
450 } else if (obj_type
== OBJ_REF_DELTA
) {
452 * Deltas with a base reference contain
453 * an additional 20 bytes for the base sha1.
455 sha1write(f
, entry
->delta
->sha1
, 20);
458 datalen
= sha1write_compressed(f
, buf
, size
);
462 struct packed_git
*p
= entry
->in_pack
;
463 struct pack_window
*w_curs
= NULL
;
467 obj_type
= (allow_ofs_delta
&& entry
->delta
->offset
) ?
468 OBJ_OFS_DELTA
: OBJ_REF_DELTA
;
471 hdrlen
= encode_header(obj_type
, entry
->size
, header
);
472 sha1write(f
, header
, hdrlen
);
473 if (obj_type
== OBJ_OFS_DELTA
) {
474 off_t ofs
= entry
->offset
- entry
->delta
->offset
;
475 unsigned pos
= sizeof(header
) - 1;
476 header
[pos
] = ofs
& 127;
478 header
[--pos
] = 128 | (--ofs
& 127);
479 sha1write(f
, header
+ pos
, sizeof(header
) - pos
);
480 hdrlen
+= sizeof(header
) - pos
;
481 } else if (obj_type
== OBJ_REF_DELTA
) {
482 sha1write(f
, entry
->delta
->sha1
, 20);
486 offset
= entry
->in_pack_offset
+ entry
->in_pack_header_size
;
487 datalen
= find_packed_object_size(p
, entry
->in_pack_offset
)
488 - entry
->in_pack_header_size
;
489 if (!pack_to_stdout
&& check_pack_inflate(p
, &w_curs
,
490 offset
, datalen
, entry
->size
))
491 die("corrupt delta in pack %s", sha1_to_hex(entry
->sha1
));
492 copy_pack_data(f
, p
, &w_curs
, offset
, datalen
);
499 return hdrlen
+ datalen
;
502 static off_t
write_one(struct sha1file
*f
,
503 struct object_entry
*e
,
508 /* offset is non zero if object is written already. */
509 if (e
->offset
|| e
->preferred_base
)
512 /* if we are deltified, write out base object first. */
514 offset
= write_one(f
, e
->delta
, offset
);
517 size
= write_object(f
, e
);
519 /* make sure off_t is sufficiently large not to wrap */
520 if (offset
> offset
+ size
)
521 die("pack too large for current definition of off_t");
522 return offset
+ size
;
525 static void write_pack_file(void)
530 struct pack_header hdr
;
531 unsigned last_percent
= 999;
532 int do_progress
= progress
;
535 f
= sha1fd(1, "<stdout>");
539 f
= sha1create("%s-%s.%s", base_name
,
540 sha1_to_hex(object_list_sha1
), "pack");
542 fprintf(stderr
, "Writing %u objects.\n", nr_result
);
544 hdr
.hdr_signature
= htonl(PACK_SIGNATURE
);
545 hdr
.hdr_version
= htonl(PACK_VERSION
);
546 hdr
.hdr_entries
= htonl(nr_result
);
547 sha1write(f
, &hdr
, sizeof(hdr
));
548 offset
= sizeof(hdr
);
551 for (i
= 0; i
< nr_objects
; i
++) {
552 offset
= write_one(f
, objects
+ i
, offset
);
554 unsigned percent
= written
* 100 / nr_result
;
555 if (progress_update
|| percent
!= last_percent
) {
556 fprintf(stderr
, "%4u%% (%u/%u) done\r",
557 percent
, written
, nr_result
);
559 last_percent
= percent
;
566 if (written
!= nr_result
)
567 die("wrote %u objects while expecting %u", written
, nr_result
);
568 sha1close(f
, pack_file_sha1
, 1);
571 static void write_index_file(void)
574 struct sha1file
*f
= sha1create("%s-%s.%s", base_name
,
575 sha1_to_hex(object_list_sha1
), "idx");
576 struct object_entry
**list
= sorted_by_sha
;
577 struct object_entry
**last
= list
+ nr_result
;
581 * Write the first-level table (the list is sorted,
582 * but we use a 256-entry lookup to be able to avoid
583 * having to do eight extra binary search iterations).
585 for (i
= 0; i
< 256; i
++) {
586 struct object_entry
**next
= list
;
587 while (next
< last
) {
588 struct object_entry
*entry
= *next
;
589 if (entry
->sha1
[0] != i
)
593 array
[i
] = htonl(next
- sorted_by_sha
);
596 sha1write(f
, array
, 256 * 4);
599 * Write the actual SHA1 entries..
601 list
= sorted_by_sha
;
602 for (i
= 0; i
< nr_result
; i
++) {
603 struct object_entry
*entry
= *list
++;
604 uint32_t offset
= htonl(entry
->offset
);
605 sha1write(f
, &offset
, 4);
606 sha1write(f
, entry
->sha1
, 20);
608 sha1write(f
, pack_file_sha1
, 20);
609 sha1close(f
, NULL
, 1);
612 static int locate_object_entry_hash(const unsigned char *sha1
)
616 memcpy(&ui
, sha1
, sizeof(unsigned int));
617 i
= ui
% object_ix_hashsz
;
618 while (0 < object_ix
[i
]) {
619 if (!hashcmp(sha1
, objects
[object_ix
[i
] - 1].sha1
))
621 if (++i
== object_ix_hashsz
)
627 static struct object_entry
*locate_object_entry(const unsigned char *sha1
)
631 if (!object_ix_hashsz
)
634 i
= locate_object_entry_hash(sha1
);
636 return &objects
[object_ix
[i
]-1];
640 static void rehash_objects(void)
643 struct object_entry
*oe
;
645 object_ix_hashsz
= nr_objects
* 3;
646 if (object_ix_hashsz
< 1024)
647 object_ix_hashsz
= 1024;
648 object_ix
= xrealloc(object_ix
, sizeof(int) * object_ix_hashsz
);
649 memset(object_ix
, 0, sizeof(int) * object_ix_hashsz
);
650 for (i
= 0, oe
= objects
; i
< nr_objects
; i
++, oe
++) {
651 int ix
= locate_object_entry_hash(oe
->sha1
);
655 object_ix
[ix
] = i
+ 1;
659 static unsigned name_hash(const char *name
)
665 * This effectively just creates a sortable number from the
666 * last sixteen non-whitespace characters. Last characters
667 * count "most", so things that end in ".c" sort together.
669 while ((c
= *name
++) != 0) {
672 hash
= (hash
>> 2) + (c
<< 24);
677 static int add_object_entry(const unsigned char *sha1
, unsigned hash
, int exclude
)
679 uint32_t idx
= nr_objects
;
680 struct object_entry
*entry
;
681 struct packed_git
*p
;
682 off_t found_offset
= 0;
683 struct packed_git
*found_pack
= NULL
;
687 for (p
= packed_git
; p
; p
= p
->next
) {
688 off_t offset
= find_pack_entry_one(sha1
, p
);
692 if (local
&& !p
->pack_local
)
695 found_offset
= offset
;
701 if ((entry
= locate_object_entry(sha1
)) != NULL
)
704 if (idx
>= nr_alloc
) {
705 nr_alloc
= (idx
+ 1024) * 3 / 2;
706 objects
= xrealloc(objects
, nr_alloc
* sizeof(*entry
));
708 entry
= objects
+ idx
;
709 nr_objects
= idx
+ 1;
710 memset(entry
, 0, sizeof(*entry
));
711 hashcpy(entry
->sha1
, sha1
);
714 if (object_ix_hashsz
* 3 <= nr_objects
* 4)
717 ix
= locate_object_entry_hash(entry
->sha1
);
719 die("internal error in object hashing.");
720 object_ix
[-1 - ix
] = idx
+ 1;
725 if (progress_update
) {
726 fprintf(stderr
, "Counting objects...%u\r", nr_objects
);
730 entry
->preferred_base
= 1;
733 entry
->in_pack
= found_pack
;
734 entry
->in_pack_offset
= found_offset
;
740 struct pbase_tree_cache
{
741 unsigned char sha1
[20];
745 unsigned long tree_size
;
748 static struct pbase_tree_cache
*(pbase_tree_cache
[256]);
749 static int pbase_tree_cache_ix(const unsigned char *sha1
)
751 return sha1
[0] % ARRAY_SIZE(pbase_tree_cache
);
753 static int pbase_tree_cache_ix_incr(int ix
)
755 return (ix
+1) % ARRAY_SIZE(pbase_tree_cache
);
758 static struct pbase_tree
{
759 struct pbase_tree
*next
;
760 /* This is a phony "cache" entry; we are not
761 * going to evict it nor find it through _get()
762 * mechanism -- this is for the toplevel node that
763 * would almost always change with any commit.
765 struct pbase_tree_cache pcache
;
768 static struct pbase_tree_cache
*pbase_tree_get(const unsigned char *sha1
)
770 struct pbase_tree_cache
*ent
, *nent
;
773 enum object_type type
;
775 int my_ix
= pbase_tree_cache_ix(sha1
);
776 int available_ix
= -1;
778 /* pbase-tree-cache acts as a limited hashtable.
779 * your object will be found at your index or within a few
780 * slots after that slot if it is cached.
782 for (neigh
= 0; neigh
< 8; neigh
++) {
783 ent
= pbase_tree_cache
[my_ix
];
784 if (ent
&& !hashcmp(ent
->sha1
, sha1
)) {
788 else if (((available_ix
< 0) && (!ent
|| !ent
->ref
)) ||
789 ((0 <= available_ix
) &&
790 (!ent
&& pbase_tree_cache
[available_ix
])))
791 available_ix
= my_ix
;
794 my_ix
= pbase_tree_cache_ix_incr(my_ix
);
797 /* Did not find one. Either we got a bogus request or
798 * we need to read and perhaps cache.
800 data
= read_sha1_file(sha1
, &type
, &size
);
803 if (type
!= OBJ_TREE
) {
808 /* We need to either cache or return a throwaway copy */
810 if (available_ix
< 0)
813 ent
= pbase_tree_cache
[available_ix
];
814 my_ix
= available_ix
;
818 nent
= xmalloc(sizeof(*nent
));
819 nent
->temporary
= (available_ix
< 0);
822 /* evict and reuse */
823 free(ent
->tree_data
);
826 hashcpy(nent
->sha1
, sha1
);
827 nent
->tree_data
= data
;
828 nent
->tree_size
= size
;
830 if (!nent
->temporary
)
831 pbase_tree_cache
[my_ix
] = nent
;
835 static void pbase_tree_put(struct pbase_tree_cache
*cache
)
837 if (!cache
->temporary
) {
841 free(cache
->tree_data
);
845 static int name_cmp_len(const char *name
)
848 for (i
= 0; name
[i
] && name
[i
] != '\n' && name
[i
] != '/'; i
++)
853 static void add_pbase_object(struct tree_desc
*tree
,
856 const char *fullname
)
858 struct name_entry entry
;
860 while (tree_entry(tree
,&entry
)) {
862 enum object_type type
;
864 if (tree_entry_len(entry
.path
, entry
.sha1
) != cmplen
||
865 memcmp(entry
.path
, name
, cmplen
) ||
866 !has_sha1_file(entry
.sha1
) ||
867 (type
= sha1_object_info(entry
.sha1
, &size
)) < 0)
869 if (name
[cmplen
] != '/') {
870 unsigned hash
= name_hash(fullname
);
871 add_object_entry(entry
.sha1
, hash
, 1);
874 if (type
== OBJ_TREE
) {
875 struct tree_desc sub
;
876 struct pbase_tree_cache
*tree
;
877 const char *down
= name
+cmplen
+1;
878 int downlen
= name_cmp_len(down
);
880 tree
= pbase_tree_get(entry
.sha1
);
883 init_tree_desc(&sub
, tree
->tree_data
, tree
->tree_size
);
885 add_pbase_object(&sub
, down
, downlen
, fullname
);
886 pbase_tree_put(tree
);
891 static unsigned *done_pbase_paths
;
892 static int done_pbase_paths_num
;
893 static int done_pbase_paths_alloc
;
894 static int done_pbase_path_pos(unsigned hash
)
897 int hi
= done_pbase_paths_num
;
899 int mi
= (hi
+ lo
) / 2;
900 if (done_pbase_paths
[mi
] == hash
)
902 if (done_pbase_paths
[mi
] < hash
)
910 static int check_pbase_path(unsigned hash
)
912 int pos
= (!done_pbase_paths
) ? -1 : done_pbase_path_pos(hash
);
916 if (done_pbase_paths_alloc
<= done_pbase_paths_num
) {
917 done_pbase_paths_alloc
= alloc_nr(done_pbase_paths_alloc
);
918 done_pbase_paths
= xrealloc(done_pbase_paths
,
919 done_pbase_paths_alloc
*
922 done_pbase_paths_num
++;
923 if (pos
< done_pbase_paths_num
)
924 memmove(done_pbase_paths
+ pos
+ 1,
925 done_pbase_paths
+ pos
,
926 (done_pbase_paths_num
- pos
- 1) * sizeof(unsigned));
927 done_pbase_paths
[pos
] = hash
;
931 static void add_preferred_base_object(const char *name
, unsigned hash
)
933 struct pbase_tree
*it
;
934 int cmplen
= name_cmp_len(name
);
936 if (check_pbase_path(hash
))
939 for (it
= pbase_tree
; it
; it
= it
->next
) {
941 hash
= name_hash("");
942 add_object_entry(it
->pcache
.sha1
, hash
, 1);
945 struct tree_desc tree
;
946 init_tree_desc(&tree
, it
->pcache
.tree_data
, it
->pcache
.tree_size
);
947 add_pbase_object(&tree
, name
, cmplen
, name
);
952 static void add_preferred_base(unsigned char *sha1
)
954 struct pbase_tree
*it
;
957 unsigned char tree_sha1
[20];
959 if (window
<= num_preferred_base
++)
962 data
= read_object_with_reference(sha1
, tree_type
, &size
, tree_sha1
);
966 for (it
= pbase_tree
; it
; it
= it
->next
) {
967 if (!hashcmp(it
->pcache
.sha1
, tree_sha1
)) {
973 it
= xcalloc(1, sizeof(*it
));
974 it
->next
= pbase_tree
;
977 hashcpy(it
->pcache
.sha1
, tree_sha1
);
978 it
->pcache
.tree_data
= data
;
979 it
->pcache
.tree_size
= size
;
982 static void check_object(struct object_entry
*entry
)
984 if (entry
->in_pack
&& !entry
->preferred_base
) {
985 struct packed_git
*p
= entry
->in_pack
;
986 struct pack_window
*w_curs
= NULL
;
987 unsigned long size
, used
;
990 struct object_entry
*base_entry
= NULL
;
992 buf
= use_pack(p
, &w_curs
, entry
->in_pack_offset
, &avail
);
994 /* We want in_pack_type even if we do not reuse delta.
995 * There is no point not reusing non-delta representations.
997 used
= unpack_object_header_gently(buf
, avail
,
998 &entry
->in_pack_type
, &size
);
1000 /* Check if it is delta, and the base is also an object
1001 * we are going to pack. If so we will reuse the existing
1004 if (!no_reuse_delta
) {
1006 const unsigned char *base_name
;
1008 unsigned long used_0
;
1009 /* there is at least 20 bytes left in the pack */
1010 switch (entry
->in_pack_type
) {
1012 base_name
= use_pack(p
, &w_curs
,
1013 entry
->in_pack_offset
+ used
, NULL
);
1017 buf
= use_pack(p
, &w_curs
,
1018 entry
->in_pack_offset
+ used
, NULL
);
1024 if (!ofs
|| MSB(ofs
, 7))
1025 die("delta base offset overflow in pack for %s",
1026 sha1_to_hex(entry
->sha1
));
1028 ofs
= (ofs
<< 7) + (c
& 127);
1030 if (ofs
>= entry
->in_pack_offset
)
1031 die("delta base offset out of bound for %s",
1032 sha1_to_hex(entry
->sha1
));
1033 ofs
= entry
->in_pack_offset
- ofs
;
1034 base_name
= find_packed_object_name(p
, ofs
);
1041 base_entry
= locate_object_entry(base_name
);
1043 unuse_pack(&w_curs
);
1044 entry
->in_pack_header_size
= used
;
1048 /* Depth value does not matter - find_deltas()
1049 * will never consider reused delta as the
1050 * base object to deltify other objects
1051 * against, in order to avoid circular deltas.
1054 /* uncompressed size of the delta data */
1056 entry
->delta
= base_entry
;
1057 entry
->type
= entry
->in_pack_type
;
1059 entry
->delta_sibling
= base_entry
->delta_child
;
1060 base_entry
->delta_child
= entry
;
1064 /* Otherwise we would do the usual */
1067 entry
->type
= sha1_object_info(entry
->sha1
, &entry
->size
);
1068 if (entry
->type
< 0)
1069 die("unable to get type of object %s",
1070 sha1_to_hex(entry
->sha1
));
1073 static unsigned int check_delta_limit(struct object_entry
*me
, unsigned int n
)
1075 struct object_entry
*child
= me
->delta_child
;
1078 unsigned int c
= check_delta_limit(child
, n
+ 1);
1081 child
= child
->delta_sibling
;
1086 static void get_object_details(void)
1089 struct object_entry
*entry
;
1092 for (i
= 0, entry
= objects
; i
< nr_objects
; i
++, entry
++)
1093 check_object(entry
);
1095 if (nr_objects
== nr_result
) {
1097 * Depth of objects that depend on the entry -- this
1098 * is subtracted from depth-max to break too deep
1099 * delta chain because of delta data reusing.
1100 * However, we loosen this restriction when we know we
1101 * are creating a thin pack -- it will have to be
1102 * expanded on the other end anyway, so do not
1103 * artificially cut the delta chain and let it go as
1106 for (i
= 0, entry
= objects
; i
< nr_objects
; i
++, entry
++)
1107 if (!entry
->delta
&& entry
->delta_child
)
1108 entry
->delta_limit
=
1109 check_delta_limit(entry
, 1);
1113 typedef int (*entry_sort_t
)(const struct object_entry
*, const struct object_entry
*);
1115 static entry_sort_t current_sort
;
1117 static int sort_comparator(const void *_a
, const void *_b
)
1119 struct object_entry
*a
= *(struct object_entry
**)_a
;
1120 struct object_entry
*b
= *(struct object_entry
**)_b
;
1121 return current_sort(a
,b
);
1124 static struct object_entry
**create_sorted_list(entry_sort_t sort
)
1126 struct object_entry
**list
= xmalloc(nr_objects
* sizeof(struct object_entry
*));
1129 for (i
= 0; i
< nr_objects
; i
++)
1130 list
[i
] = objects
+ i
;
1131 current_sort
= sort
;
1132 qsort(list
, nr_objects
, sizeof(struct object_entry
*), sort_comparator
);
1136 static int sha1_sort(const struct object_entry
*a
, const struct object_entry
*b
)
1138 return hashcmp(a
->sha1
, b
->sha1
);
1141 static struct object_entry
**create_final_object_list(void)
1143 struct object_entry
**list
;
1146 for (i
= nr_result
= 0; i
< nr_objects
; i
++)
1147 if (!objects
[i
].preferred_base
)
1149 list
= xmalloc(nr_result
* sizeof(struct object_entry
*));
1150 for (i
= j
= 0; i
< nr_objects
; i
++) {
1151 if (!objects
[i
].preferred_base
)
1152 list
[j
++] = objects
+ i
;
1154 current_sort
= sha1_sort
;
1155 qsort(list
, nr_result
, sizeof(struct object_entry
*), sort_comparator
);
1159 static int type_size_sort(const struct object_entry
*a
, const struct object_entry
*b
)
1161 if (a
->type
< b
->type
)
1163 if (a
->type
> b
->type
)
1165 if (a
->hash
< b
->hash
)
1167 if (a
->hash
> b
->hash
)
1169 if (a
->preferred_base
< b
->preferred_base
)
1171 if (a
->preferred_base
> b
->preferred_base
)
1173 if (a
->size
< b
->size
)
1175 if (a
->size
> b
->size
)
1177 return a
< b
? -1 : (a
> b
);
1181 struct object_entry
*entry
;
1183 struct delta_index
*index
;
1187 * We search for deltas _backwards_ in a list sorted by type and
1188 * by size, so that we see progressively smaller and smaller files.
1189 * That's because we prefer deltas to be from the bigger file
1190 * to the smaller - deletes are potentially cheaper, but perhaps
1191 * more importantly, the bigger file is likely the more recent
1194 static int try_delta(struct unpacked
*trg
, struct unpacked
*src
,
1197 struct object_entry
*trg_entry
= trg
->entry
;
1198 struct object_entry
*src_entry
= src
->entry
;
1199 unsigned long trg_size
, src_size
, delta_size
, sizediff
, max_size
, sz
;
1200 enum object_type type
;
1203 /* Don't bother doing diffs between different types */
1204 if (trg_entry
->type
!= src_entry
->type
)
1207 /* We do not compute delta to *create* objects we are not
1210 if (trg_entry
->preferred_base
)
1214 * We do not bother to try a delta that we discarded
1215 * on an earlier try, but only when reusing delta data.
1217 if (!no_reuse_delta
&& trg_entry
->in_pack
&&
1218 trg_entry
->in_pack
== src_entry
->in_pack
&&
1219 trg_entry
->in_pack_type
!= OBJ_REF_DELTA
&&
1220 trg_entry
->in_pack_type
!= OBJ_OFS_DELTA
)
1224 * If the current object is at pack edge, take the depth the
1225 * objects that depend on the current object into account --
1226 * otherwise they would become too deep.
1228 if (trg_entry
->delta_child
) {
1229 if (max_depth
<= trg_entry
->delta_limit
)
1231 max_depth
-= trg_entry
->delta_limit
;
1233 if (src_entry
->depth
>= max_depth
)
1236 /* Now some size filtering heuristics. */
1237 trg_size
= trg_entry
->size
;
1238 max_size
= trg_size
/2 - 20;
1239 max_size
= max_size
* (max_depth
- src_entry
->depth
) / max_depth
;
1242 if (trg_entry
->delta
&& trg_entry
->delta_size
<= max_size
)
1243 max_size
= trg_entry
->delta_size
-1;
1244 src_size
= src_entry
->size
;
1245 sizediff
= src_size
< trg_size
? trg_size
- src_size
: 0;
1246 if (sizediff
>= max_size
)
1249 /* Load data if not already done */
1251 trg
->data
= read_sha1_file(trg_entry
->sha1
, &type
, &sz
);
1253 die("object %s inconsistent object length (%lu vs %lu)",
1254 sha1_to_hex(trg_entry
->sha1
), sz
, trg_size
);
1257 src
->data
= read_sha1_file(src_entry
->sha1
, &type
, &sz
);
1259 die("object %s inconsistent object length (%lu vs %lu)",
1260 sha1_to_hex(src_entry
->sha1
), sz
, src_size
);
1263 src
->index
= create_delta_index(src
->data
, src_size
);
1265 die("out of memory");
1268 delta_buf
= create_delta(src
->index
, trg
->data
, trg_size
, &delta_size
, max_size
);
1272 trg_entry
->delta
= src_entry
;
1273 trg_entry
->delta_size
= delta_size
;
1274 trg_entry
->depth
= src_entry
->depth
+ 1;
1279 static void progress_interval(int signum
)
1281 progress_update
= 1;
1284 static void find_deltas(struct object_entry
**list
, int window
, int depth
)
1286 uint32_t i
= nr_objects
, idx
= 0, processed
= 0;
1287 unsigned int array_size
= window
* sizeof(struct unpacked
);
1288 struct unpacked
*array
;
1289 unsigned last_percent
= 999;
1293 array
= xmalloc(array_size
);
1294 memset(array
, 0, array_size
);
1296 fprintf(stderr
, "Deltifying %u objects.\n", nr_result
);
1299 struct object_entry
*entry
= list
[--i
];
1300 struct unpacked
*n
= array
+ idx
;
1303 if (!entry
->preferred_base
)
1307 unsigned percent
= processed
* 100 / nr_result
;
1308 if (percent
!= last_percent
|| progress_update
) {
1309 fprintf(stderr
, "%4u%% (%u/%u) done\r",
1310 percent
, processed
, nr_result
);
1311 progress_update
= 0;
1312 last_percent
= percent
;
1317 /* This happens if we decided to reuse existing
1318 * delta from a pack. "!no_reuse_delta &&" is implied.
1322 if (entry
->size
< 50)
1324 free_delta_index(n
->index
);
1332 uint32_t other_idx
= idx
+ j
;
1334 if (other_idx
>= window
)
1335 other_idx
-= window
;
1336 m
= array
+ other_idx
;
1339 if (try_delta(n
, m
, depth
) < 0)
1342 /* if we made n a delta, and if n is already at max
1343 * depth, leaving it in the window is pointless. we
1344 * should evict it first.
1346 if (entry
->delta
&& depth
<= entry
->depth
)
1355 fputc('\n', stderr
);
1357 for (i
= 0; i
< window
; ++i
) {
1358 free_delta_index(array
[i
].index
);
1359 free(array
[i
].data
);
1364 static void prepare_pack(int window
, int depth
)
1366 get_object_details();
1367 sorted_by_type
= create_sorted_list(type_size_sort
);
1368 if (window
&& depth
)
1369 find_deltas(sorted_by_type
, window
+1, depth
);
1372 static int reuse_cached_pack(unsigned char *sha1
)
1374 static const char cache
[] = "pack-cache/pack-%s.%s";
1375 char *cached_pack
, *cached_idx
;
1376 int ifd
, ofd
, ifd_ix
= -1;
1378 cached_pack
= git_path(cache
, sha1_to_hex(sha1
), "pack");
1379 ifd
= open(cached_pack
, O_RDONLY
);
1383 if (!pack_to_stdout
) {
1384 cached_idx
= git_path(cache
, sha1_to_hex(sha1
), "idx");
1385 ifd_ix
= open(cached_idx
, O_RDONLY
);
1393 fprintf(stderr
, "Reusing %u objects pack %s\n", nr_objects
,
1396 if (pack_to_stdout
) {
1397 if (copy_fd(ifd
, 1))
1402 char name
[PATH_MAX
];
1403 snprintf(name
, sizeof(name
),
1404 "%s-%s.%s", base_name
, sha1_to_hex(sha1
), "pack");
1405 ofd
= open(name
, O_CREAT
| O_EXCL
| O_WRONLY
, 0666);
1407 die("unable to open %s (%s)", name
, strerror(errno
));
1408 if (copy_fd(ifd
, ofd
))
1412 snprintf(name
, sizeof(name
),
1413 "%s-%s.%s", base_name
, sha1_to_hex(sha1
), "idx");
1414 ofd
= open(name
, O_CREAT
| O_EXCL
| O_WRONLY
, 0666);
1416 die("unable to open %s (%s)", name
, strerror(errno
));
1417 if (copy_fd(ifd_ix
, ofd
))
1420 puts(sha1_to_hex(sha1
));
1426 static void setup_progress_signal(void)
1428 struct sigaction sa
;
1431 memset(&sa
, 0, sizeof(sa
));
1432 sa
.sa_handler
= progress_interval
;
1433 sigemptyset(&sa
.sa_mask
);
1434 sa
.sa_flags
= SA_RESTART
;
1435 sigaction(SIGALRM
, &sa
, NULL
);
1437 v
.it_interval
.tv_sec
= 1;
1438 v
.it_interval
.tv_usec
= 0;
1439 v
.it_value
= v
.it_interval
;
1440 setitimer(ITIMER_REAL
, &v
, NULL
);
1443 static int git_pack_config(const char *k
, const char *v
)
1445 if(!strcmp(k
, "pack.window")) {
1446 window
= git_config_int(k
, v
);
1449 return git_default_config(k
, v
);
1452 static void read_object_list_from_stdin(void)
1454 char line
[40 + 1 + PATH_MAX
+ 2];
1455 unsigned char sha1
[20];
1459 if (!fgets(line
, sizeof(line
), stdin
)) {
1463 die("fgets returned NULL, not EOF, not error!");
1465 die("fgets: %s", strerror(errno
));
1469 if (line
[0] == '-') {
1470 if (get_sha1_hex(line
+1, sha1
))
1471 die("expected edge sha1, got garbage:\n %s",
1473 add_preferred_base(sha1
);
1476 if (get_sha1_hex(line
, sha1
))
1477 die("expected sha1, got garbage:\n %s", line
);
1479 hash
= name_hash(line
+41);
1480 add_preferred_base_object(line
+41, hash
);
1481 add_object_entry(sha1
, hash
, 0);
1485 static void show_commit(struct commit
*commit
)
1487 unsigned hash
= name_hash("");
1488 add_preferred_base_object("", hash
);
1489 add_object_entry(commit
->object
.sha1
, hash
, 0);
1492 static void show_object(struct object_array_entry
*p
)
1494 unsigned hash
= name_hash(p
->name
);
1495 add_preferred_base_object(p
->name
, hash
);
1496 add_object_entry(p
->item
->sha1
, hash
, 0);
1499 static void show_edge(struct commit
*commit
)
1501 add_preferred_base(commit
->object
.sha1
);
1504 static void get_object_list(int ac
, const char **av
)
1506 struct rev_info revs
;
1510 init_revisions(&revs
, NULL
);
1511 save_commit_buffer
= 0;
1512 track_object_refs
= 0;
1513 setup_revisions(ac
, av
, &revs
, NULL
);
1515 while (fgets(line
, sizeof(line
), stdin
) != NULL
) {
1516 int len
= strlen(line
);
1517 if (line
[len
- 1] == '\n')
1522 if (!strcmp(line
, "--not")) {
1523 flags
^= UNINTERESTING
;
1526 die("not a rev '%s'", line
);
1528 if (handle_revision_arg(line
, &revs
, flags
, 1))
1529 die("bad revision '%s'", line
);
1532 prepare_revision_walk(&revs
);
1533 mark_edges_uninteresting(revs
.commits
, &revs
, show_edge
);
1534 traverse_commit_list(&revs
, show_commit
, show_object
);
1537 int cmd_pack_objects(int argc
, const char **argv
, const char *prefix
)
1541 struct object_entry
**list
;
1542 int use_internal_rev_list
= 0;
1546 int rp_ac_alloc
= 64;
1549 rp_av
= xcalloc(rp_ac_alloc
, sizeof(*rp_av
));
1551 rp_av
[0] = "pack-objects";
1552 rp_av
[1] = "--objects"; /* --thin will make it --objects-edge */
1555 git_config(git_pack_config
);
1557 progress
= isatty(2);
1558 for (i
= 1; i
< argc
; i
++) {
1559 const char *arg
= argv
[i
];
1564 if (!strcmp("--non-empty", arg
)) {
1568 if (!strcmp("--local", arg
)) {
1572 if (!strcmp("--incremental", arg
)) {
1576 if (!prefixcmp(arg
, "--window=")) {
1578 window
= strtoul(arg
+9, &end
, 0);
1579 if (!arg
[9] || *end
)
1583 if (!prefixcmp(arg
, "--depth=")) {
1585 depth
= strtoul(arg
+8, &end
, 0);
1586 if (!arg
[8] || *end
)
1590 if (!strcmp("--progress", arg
)) {
1594 if (!strcmp("--all-progress", arg
)) {
1598 if (!strcmp("-q", arg
)) {
1602 if (!strcmp("--no-reuse-delta", arg
)) {
1606 if (!strcmp("--delta-base-offset", arg
)) {
1607 allow_ofs_delta
= 1;
1610 if (!strcmp("--stdout", arg
)) {
1614 if (!strcmp("--revs", arg
)) {
1615 use_internal_rev_list
= 1;
1618 if (!strcmp("--unpacked", arg
) ||
1619 !prefixcmp(arg
, "--unpacked=") ||
1620 !strcmp("--reflog", arg
) ||
1621 !strcmp("--all", arg
)) {
1622 use_internal_rev_list
= 1;
1623 if (rp_ac
>= rp_ac_alloc
- 1) {
1624 rp_ac_alloc
= alloc_nr(rp_ac_alloc
);
1625 rp_av
= xrealloc(rp_av
,
1626 rp_ac_alloc
* sizeof(*rp_av
));
1628 rp_av
[rp_ac
++] = arg
;
1631 if (!strcmp("--thin", arg
)) {
1632 use_internal_rev_list
= 1;
1634 rp_av
[1] = "--objects-edge";
1640 /* Traditionally "pack-objects [options] base extra" failed;
1641 * we would however want to take refs parameter that would
1642 * have been given to upstream rev-list ourselves, which means
1643 * we somehow want to say what the base name is. So the
1646 * pack-objects [options] base <refs...>
1648 * in other words, we would treat the first non-option as the
1649 * base_name and send everything else to the internal revision
1653 if (!pack_to_stdout
)
1654 base_name
= argv
[i
++];
1656 if (pack_to_stdout
!= !base_name
)
1659 if (!pack_to_stdout
&& thin
)
1660 die("--thin cannot be used to build an indexable pack.");
1662 prepare_packed_git();
1665 fprintf(stderr
, "Generating pack...\n");
1666 setup_progress_signal();
1669 if (!use_internal_rev_list
)
1670 read_object_list_from_stdin();
1672 rp_av
[rp_ac
] = NULL
;
1673 get_object_list(rp_ac
, rp_av
);
1677 fprintf(stderr
, "Done counting %u objects.\n", nr_objects
);
1678 sorted_by_sha
= create_final_object_list();
1679 if (non_empty
&& !nr_result
)
1683 list
= sorted_by_sha
;
1684 for (i
= 0; i
< nr_result
; i
++) {
1685 struct object_entry
*entry
= *list
++;
1686 SHA1_Update(&ctx
, entry
->sha1
, 20);
1688 SHA1_Final(object_list_sha1
, &ctx
);
1689 if (progress
&& (nr_objects
!= nr_result
))
1690 fprintf(stderr
, "Result has %u objects.\n", nr_result
);
1692 if (reuse_cached_pack(object_list_sha1
))
1696 prepare_pack(window
, depth
);
1697 if (progress
== 1 && pack_to_stdout
) {
1698 /* the other end usually displays progress itself */
1699 struct itimerval v
= {{0,},};
1700 setitimer(ITIMER_REAL
, &v
, NULL
);
1701 signal(SIGALRM
, SIG_IGN
);
1702 progress_update
= 0;
1705 if (!pack_to_stdout
) {
1707 puts(sha1_to_hex(object_list_sha1
));
1711 fprintf(stderr
, "Total %u (delta %u), reused %u (delta %u)\n",
1712 written
, written_delta
, reused
, reused_delta
);