10 #include "csum-file.h"
11 #include "tree-walk.h"
14 #include "list-objects.h"
18 static const char pack_usage
[] = "git-pack-objects [-q] [--no-reuse-delta] [--non-empty] [--local] [--incremental] [--window=N] [--depth=N] {--stdout | base-name} [--revs [--unpacked | --all]* <ref-list | <object-list]";
21 unsigned char sha1
[20];
22 unsigned long size
; /* uncompressed size */
23 unsigned long offset
; /* offset into the final pack file;
24 * nonzero if already written.
26 unsigned int depth
; /* delta depth */
27 unsigned int delta_limit
; /* base adjustment for in-pack delta */
28 unsigned int hash
; /* name hint hash */
29 enum object_type type
;
30 enum object_type in_pack_type
; /* could be delta */
31 unsigned long delta_size
; /* delta data size (uncompressed) */
32 struct object_entry
*delta
; /* delta base object */
33 struct packed_git
*in_pack
; /* already in pack */
34 unsigned int in_pack_offset
;
35 struct object_entry
*delta_child
; /* deltified objects who bases me */
36 struct object_entry
*delta_sibling
; /* other deltified objects who
37 * uses the same base as me
39 int preferred_base
; /* we do not pack this, but is encouraged to
40 * be used as the base objectto delta huge
46 * Objects we are going to pack are collected in objects array (dynamically
47 * expanded). nr_objects & nr_alloc controls this array. They are stored
48 * in the order we see -- typically rev-list --objects order that gives us
49 * nice "minimum seek" order.
51 * sorted-by-sha ans sorted-by-type are arrays of pointers that point at
52 * elements in the objects array. The former is used to build the pack
53 * index (lists object names in the ascending order to help offset lookup),
54 * and the latter is used to group similar things together by try_delta()
58 static unsigned char object_list_sha1
[20];
60 static int no_reuse_delta
;
62 static int incremental
;
63 static struct object_entry
**sorted_by_sha
, **sorted_by_type
;
64 static struct object_entry
*objects
;
65 static int nr_objects
, nr_alloc
, nr_result
;
66 static const char *base_name
;
67 static unsigned char pack_file_sha1
[20];
68 static int progress
= 1;
69 static volatile sig_atomic_t progress_update
;
70 static int window
= 10;
71 static int pack_to_stdout
;
74 * The object names in objects array are hashed with this hashtable,
75 * to help looking up the entry by object name. Binary search from
76 * sorted_by_sha is also possible but this was easier to code and faster.
77 * This hashtable is built after all the objects are seen.
79 static int *object_ix
;
80 static int object_ix_hashsz
;
83 * Pack index for existing packs give us easy access to the offsets into
84 * corresponding pack file where each object's data starts, but the entries
85 * do not store the size of the compressed representation (uncompressed
86 * size is easily available by examining the pack entry header). We build
87 * a hashtable of existing packs (pack_revindex), and keep reverse index
88 * here -- pack index file is sorted by object name mapping to offset; this
89 * pack_revindex[].revindex array is an ordered list of offsets, so if you
90 * know the offset of an object, next offset is where its packed
91 * representation ends.
93 struct pack_revindex
{
95 unsigned long *revindex
;
96 } *pack_revindex
= NULL
;
97 static int pack_revindex_hashsz
;
103 static int written_delta
;
105 static int reused_delta
;
107 static int pack_revindex_ix(struct packed_git
*p
)
109 unsigned long ui
= (unsigned long)p
;
112 ui
= ui
^ (ui
>> 16); /* defeat structure alignment */
113 i
= (int)(ui
% pack_revindex_hashsz
);
114 while (pack_revindex
[i
].p
) {
115 if (pack_revindex
[i
].p
== p
)
117 if (++i
== pack_revindex_hashsz
)
123 static void prepare_pack_ix(void)
126 struct packed_git
*p
;
127 for (num
= 0, p
= packed_git
; p
; p
= p
->next
)
131 pack_revindex_hashsz
= num
* 11;
132 pack_revindex
= xcalloc(sizeof(*pack_revindex
), pack_revindex_hashsz
);
133 for (p
= packed_git
; p
; p
= p
->next
) {
134 num
= pack_revindex_ix(p
);
136 pack_revindex
[num
].p
= p
;
138 /* revindex elements are lazily initialized */
141 static int cmp_offset(const void *a_
, const void *b_
)
143 unsigned long a
= *(unsigned long *) a_
;
144 unsigned long b
= *(unsigned long *) b_
;
154 * Ordered list of offsets of objects in the pack.
156 static void prepare_pack_revindex(struct pack_revindex
*rix
)
158 struct packed_git
*p
= rix
->p
;
159 int num_ent
= num_packed_objects(p
);
161 void *index
= p
->index_base
+ 256;
163 rix
->revindex
= xmalloc(sizeof(unsigned long) * (num_ent
+ 1));
164 for (i
= 0; i
< num_ent
; i
++) {
165 unsigned int hl
= *((unsigned int *)((char *) index
+ 24*i
));
166 rix
->revindex
[i
] = ntohl(hl
);
168 /* This knows the pack format -- the 20-byte trailer
169 * follows immediately after the last object data.
171 rix
->revindex
[num_ent
] = p
->pack_size
- 20;
172 qsort(rix
->revindex
, num_ent
, sizeof(unsigned long), cmp_offset
);
175 static unsigned long find_packed_object_size(struct packed_git
*p
,
180 struct pack_revindex
*rix
;
181 unsigned long *revindex
;
182 num
= pack_revindex_ix(p
);
184 die("internal error: pack revindex uninitialized");
185 rix
= &pack_revindex
[num
];
187 prepare_pack_revindex(rix
);
188 revindex
= rix
->revindex
;
190 hi
= num_packed_objects(p
) + 1;
192 int mi
= (lo
+ hi
) / 2;
193 if (revindex
[mi
] == ofs
) {
194 return revindex
[mi
+1] - ofs
;
196 else if (ofs
< revindex
[mi
])
201 die("internal error: pack revindex corrupt");
204 static void *delta_against(void *buf
, unsigned long size
, struct object_entry
*entry
)
206 unsigned long othersize
, delta_size
;
208 void *otherbuf
= read_sha1_file(entry
->delta
->sha1
, type
, &othersize
);
212 die("unable to read %s", sha1_to_hex(entry
->delta
->sha1
));
213 delta_buf
= diff_delta(otherbuf
, othersize
,
214 buf
, size
, &delta_size
, 0);
215 if (!delta_buf
|| delta_size
!= entry
->delta_size
)
216 die("delta size changed");
223 * The per-object header is a pretty dense thing, which is
224 * - first byte: low four bits are "size", then three bits of "type",
225 * and the high bit is "size continues".
226 * - each byte afterwards: low seven bits are size continuation,
227 * with the high bit being "size continues"
229 static int encode_header(enum object_type type
, unsigned long size
, unsigned char *hdr
)
234 if (type
< OBJ_COMMIT
|| type
> OBJ_DELTA
)
235 die("bad type %d", type
);
237 c
= (type
<< 4) | (size
& 15);
249 static int check_inflate(unsigned char *data
, unsigned long len
, unsigned long expect
)
252 unsigned char fakebuf
[4096];
255 memset(&stream
, 0, sizeof(stream
));
256 stream
.next_in
= data
;
257 stream
.avail_in
= len
;
258 stream
.next_out
= fakebuf
;
259 stream
.avail_out
= sizeof(fakebuf
);
260 inflateInit(&stream
);
263 st
= inflate(&stream
, Z_FINISH
);
264 if (st
== Z_STREAM_END
|| st
== Z_OK
) {
265 st
= (stream
.total_out
== expect
&&
266 stream
.total_in
== len
) ? 0 : -1;
269 if (st
!= Z_BUF_ERROR
) {
273 stream
.next_out
= fakebuf
;
274 stream
.avail_out
= sizeof(fakebuf
);
281 * we are going to reuse the existing pack entry data. make
282 * sure it is not corrupt.
284 static int revalidate_pack_entry(struct object_entry
*entry
, unsigned char *data
, unsigned long len
)
286 enum object_type type
;
287 unsigned long size
, used
;
292 /* the caller has already called use_packed_git() for us,
293 * so it is safe to access the pack data from mmapped location.
294 * make sure the entry inflates correctly.
296 used
= unpack_object_header_gently(data
, len
, &type
, &size
);
299 if (type
== OBJ_DELTA
)
300 used
+= 20; /* skip base object name */
303 return check_inflate(data
, len
, entry
->size
);
306 static int revalidate_loose_object(struct object_entry
*entry
,
308 unsigned long mapsize
)
310 /* we already know this is a loose object with new type header. */
311 enum object_type type
;
312 unsigned long size
, used
;
317 used
= unpack_object_header_gently(map
, mapsize
, &type
, &size
);
322 return check_inflate(map
, mapsize
, size
);
325 static unsigned long write_object(struct sha1file
*f
,
326 struct object_entry
*entry
)
331 unsigned char header
[10];
332 unsigned hdrlen
, datalen
;
333 enum object_type obj_type
;
336 if (entry
->preferred_base
)
339 obj_type
= entry
->type
;
340 if (! entry
->in_pack
)
341 to_reuse
= 0; /* can't reuse what we don't have */
342 else if (obj_type
== OBJ_DELTA
)
343 to_reuse
= 1; /* check_object() decided it for us */
344 else if (obj_type
!= entry
->in_pack_type
)
345 to_reuse
= 0; /* pack has delta which is unusable */
346 else if (entry
->delta
)
347 to_reuse
= 0; /* we want to pack afresh */
349 to_reuse
= 1; /* we have it in-pack undeltified,
350 * and we do not need to deltify it.
353 if (!entry
->in_pack
&& !entry
->delta
) {
355 unsigned long mapsize
;
356 map
= map_sha1_file(entry
->sha1
, &mapsize
);
357 if (map
&& !legacy_loose_object(map
)) {
358 /* We can copy straight into the pack file */
359 if (revalidate_loose_object(entry
, map
, mapsize
))
360 die("corrupt loose object %s",
361 sha1_to_hex(entry
->sha1
));
362 sha1write(f
, map
, mapsize
);
363 munmap(map
, mapsize
);
369 munmap(map
, mapsize
);
373 buf
= read_sha1_file(entry
->sha1
, type
, &size
);
375 die("unable to read %s", sha1_to_hex(entry
->sha1
));
376 if (size
!= entry
->size
)
377 die("object %s size inconsistency (%lu vs %lu)",
378 sha1_to_hex(entry
->sha1
), size
, entry
->size
);
380 buf
= delta_against(buf
, size
, entry
);
381 size
= entry
->delta_size
;
382 obj_type
= OBJ_DELTA
;
385 * The object header is a byte of 'type' followed by zero or
386 * more bytes of length. For deltas, the 20 bytes of delta
389 hdrlen
= encode_header(obj_type
, size
, header
);
390 sha1write(f
, header
, hdrlen
);
393 sha1write(f
, entry
->delta
, 20);
396 datalen
= sha1write_compressed(f
, buf
, size
);
400 struct packed_git
*p
= entry
->in_pack
;
403 datalen
= find_packed_object_size(p
, entry
->in_pack_offset
);
404 buf
= (char *) p
->pack_base
+ entry
->in_pack_offset
;
406 if (revalidate_pack_entry(entry
, buf
, datalen
))
407 die("corrupt delta in pack %s", sha1_to_hex(entry
->sha1
));
408 sha1write(f
, buf
, datalen
);
410 hdrlen
= 0; /* not really */
411 if (obj_type
== OBJ_DELTA
)
415 if (obj_type
== OBJ_DELTA
)
418 return hdrlen
+ datalen
;
421 static unsigned long write_one(struct sha1file
*f
,
422 struct object_entry
*e
,
423 unsigned long offset
)
426 /* offset starts from header size and cannot be zero
427 * if it is written already.
431 offset
+= write_object(f
, e
);
432 /* if we are deltified, write out its base object. */
434 offset
= write_one(f
, e
->delta
, offset
);
438 static void write_pack_file(void)
442 unsigned long offset
;
443 struct pack_header hdr
;
444 unsigned last_percent
= 999;
448 f
= sha1fd(1, "<stdout>");
450 f
= sha1create("%s-%s.%s", base_name
,
451 sha1_to_hex(object_list_sha1
), "pack");
452 do_progress
= progress
;
455 fprintf(stderr
, "Writing %d objects.\n", nr_result
);
457 hdr
.hdr_signature
= htonl(PACK_SIGNATURE
);
458 hdr
.hdr_version
= htonl(PACK_VERSION
);
459 hdr
.hdr_entries
= htonl(nr_result
);
460 sha1write(f
, &hdr
, sizeof(hdr
));
461 offset
= sizeof(hdr
);
464 for (i
= 0; i
< nr_objects
; i
++) {
465 offset
= write_one(f
, objects
+ i
, offset
);
467 unsigned percent
= written
* 100 / nr_result
;
468 if (progress_update
|| percent
!= last_percent
) {
469 fprintf(stderr
, "%4u%% (%u/%u) done\r",
470 percent
, written
, nr_result
);
472 last_percent
= percent
;
479 sha1close(f
, pack_file_sha1
, 1);
482 static void write_index_file(void)
485 struct sha1file
*f
= sha1create("%s-%s.%s", base_name
,
486 sha1_to_hex(object_list_sha1
), "idx");
487 struct object_entry
**list
= sorted_by_sha
;
488 struct object_entry
**last
= list
+ nr_result
;
489 unsigned int array
[256];
492 * Write the first-level table (the list is sorted,
493 * but we use a 256-entry lookup to be able to avoid
494 * having to do eight extra binary search iterations).
496 for (i
= 0; i
< 256; i
++) {
497 struct object_entry
**next
= list
;
498 while (next
< last
) {
499 struct object_entry
*entry
= *next
;
500 if (entry
->sha1
[0] != i
)
504 array
[i
] = htonl(next
- sorted_by_sha
);
507 sha1write(f
, array
, 256 * sizeof(int));
510 * Write the actual SHA1 entries..
512 list
= sorted_by_sha
;
513 for (i
= 0; i
< nr_result
; i
++) {
514 struct object_entry
*entry
= *list
++;
515 unsigned int offset
= htonl(entry
->offset
);
516 sha1write(f
, &offset
, 4);
517 sha1write(f
, entry
->sha1
, 20);
519 sha1write(f
, pack_file_sha1
, 20);
520 sha1close(f
, NULL
, 1);
523 static int locate_object_entry_hash(const unsigned char *sha1
)
527 memcpy(&ui
, sha1
, sizeof(unsigned int));
528 i
= ui
% object_ix_hashsz
;
529 while (0 < object_ix
[i
]) {
530 if (!hashcmp(sha1
, objects
[object_ix
[i
] - 1].sha1
))
532 if (++i
== object_ix_hashsz
)
538 static struct object_entry
*locate_object_entry(const unsigned char *sha1
)
542 if (!object_ix_hashsz
)
545 i
= locate_object_entry_hash(sha1
);
547 return &objects
[object_ix
[i
]-1];
551 static void rehash_objects(void)
554 struct object_entry
*oe
;
556 object_ix_hashsz
= nr_objects
* 3;
557 if (object_ix_hashsz
< 1024)
558 object_ix_hashsz
= 1024;
559 object_ix
= xrealloc(object_ix
, sizeof(int) * object_ix_hashsz
);
560 memset(object_ix
, 0, sizeof(int) * object_ix_hashsz
);
561 for (i
= 0, oe
= objects
; i
< nr_objects
; i
++, oe
++) {
562 int ix
= locate_object_entry_hash(oe
->sha1
);
566 object_ix
[ix
] = i
+ 1;
570 static unsigned name_hash(const char *name
)
576 * This effectively just creates a sortable number from the
577 * last sixteen non-whitespace characters. Last characters
578 * count "most", so things that end in ".c" sort together.
580 while ((c
= *name
++) != 0) {
583 hash
= (hash
>> 2) + (c
<< 24);
588 static int add_object_entry(const unsigned char *sha1
, unsigned hash
, int exclude
)
590 unsigned int idx
= nr_objects
;
591 struct object_entry
*entry
;
592 struct packed_git
*p
;
593 unsigned int found_offset
= 0;
594 struct packed_git
*found_pack
= NULL
;
598 for (p
= packed_git
; p
; p
= p
->next
) {
600 if (find_pack_entry_one(sha1
, &e
, p
)) {
603 if (local
&& !p
->pack_local
)
606 found_offset
= e
.offset
;
612 if ((entry
= locate_object_entry(sha1
)) != NULL
)
615 if (idx
>= nr_alloc
) {
616 unsigned int needed
= (idx
+ 1024) * 3 / 2;
617 objects
= xrealloc(objects
, needed
* sizeof(*entry
));
620 entry
= objects
+ idx
;
621 nr_objects
= idx
+ 1;
622 memset(entry
, 0, sizeof(*entry
));
623 hashcpy(entry
->sha1
, sha1
);
626 if (object_ix_hashsz
* 3 <= nr_objects
* 4)
629 ix
= locate_object_entry_hash(entry
->sha1
);
631 die("internal error in object hashing.");
632 object_ix
[-1 - ix
] = idx
+ 1;
637 if (progress_update
) {
638 fprintf(stderr
, "Counting objects...%d\r", nr_objects
);
642 entry
->preferred_base
= 1;
645 entry
->in_pack
= found_pack
;
646 entry
->in_pack_offset
= found_offset
;
652 struct pbase_tree_cache
{
653 unsigned char sha1
[20];
657 unsigned long tree_size
;
660 static struct pbase_tree_cache
*(pbase_tree_cache
[256]);
661 static int pbase_tree_cache_ix(const unsigned char *sha1
)
663 return sha1
[0] % ARRAY_SIZE(pbase_tree_cache
);
665 static int pbase_tree_cache_ix_incr(int ix
)
667 return (ix
+1) % ARRAY_SIZE(pbase_tree_cache
);
670 static struct pbase_tree
{
671 struct pbase_tree
*next
;
672 /* This is a phony "cache" entry; we are not
673 * going to evict it nor find it through _get()
674 * mechanism -- this is for the toplevel node that
675 * would almost always change with any commit.
677 struct pbase_tree_cache pcache
;
680 static struct pbase_tree_cache
*pbase_tree_get(const unsigned char *sha1
)
682 struct pbase_tree_cache
*ent
, *nent
;
687 int my_ix
= pbase_tree_cache_ix(sha1
);
688 int available_ix
= -1;
690 /* pbase-tree-cache acts as a limited hashtable.
691 * your object will be found at your index or within a few
692 * slots after that slot if it is cached.
694 for (neigh
= 0; neigh
< 8; neigh
++) {
695 ent
= pbase_tree_cache
[my_ix
];
696 if (ent
&& !hashcmp(ent
->sha1
, sha1
)) {
700 else if (((available_ix
< 0) && (!ent
|| !ent
->ref
)) ||
701 ((0 <= available_ix
) &&
702 (!ent
&& pbase_tree_cache
[available_ix
])))
703 available_ix
= my_ix
;
706 my_ix
= pbase_tree_cache_ix_incr(my_ix
);
709 /* Did not find one. Either we got a bogus request or
710 * we need to read and perhaps cache.
712 data
= read_sha1_file(sha1
, type
, &size
);
715 if (strcmp(type
, tree_type
)) {
720 /* We need to either cache or return a throwaway copy */
722 if (available_ix
< 0)
725 ent
= pbase_tree_cache
[available_ix
];
726 my_ix
= available_ix
;
730 nent
= xmalloc(sizeof(*nent
));
731 nent
->temporary
= (available_ix
< 0);
734 /* evict and reuse */
735 free(ent
->tree_data
);
738 hashcpy(nent
->sha1
, sha1
);
739 nent
->tree_data
= data
;
740 nent
->tree_size
= size
;
742 if (!nent
->temporary
)
743 pbase_tree_cache
[my_ix
] = nent
;
747 static void pbase_tree_put(struct pbase_tree_cache
*cache
)
749 if (!cache
->temporary
) {
753 free(cache
->tree_data
);
757 static int name_cmp_len(const char *name
)
760 for (i
= 0; name
[i
] && name
[i
] != '\n' && name
[i
] != '/'; i
++)
765 static void add_pbase_object(struct tree_desc
*tree
,
768 const char *fullname
)
770 struct name_entry entry
;
772 while (tree_entry(tree
,&entry
)) {
776 if (entry
.pathlen
!= cmplen
||
777 memcmp(entry
.path
, name
, cmplen
) ||
778 !has_sha1_file(entry
.sha1
) ||
779 sha1_object_info(entry
.sha1
, type
, &size
))
781 if (name
[cmplen
] != '/') {
782 unsigned hash
= name_hash(fullname
);
783 add_object_entry(entry
.sha1
, hash
, 1);
786 if (!strcmp(type
, tree_type
)) {
787 struct tree_desc sub
;
788 struct pbase_tree_cache
*tree
;
789 const char *down
= name
+cmplen
+1;
790 int downlen
= name_cmp_len(down
);
792 tree
= pbase_tree_get(entry
.sha1
);
795 sub
.buf
= tree
->tree_data
;
796 sub
.size
= tree
->tree_size
;
798 add_pbase_object(&sub
, down
, downlen
, fullname
);
799 pbase_tree_put(tree
);
804 static unsigned *done_pbase_paths
;
805 static int done_pbase_paths_num
;
806 static int done_pbase_paths_alloc
;
807 static int done_pbase_path_pos(unsigned hash
)
810 int hi
= done_pbase_paths_num
;
812 int mi
= (hi
+ lo
) / 2;
813 if (done_pbase_paths
[mi
] == hash
)
815 if (done_pbase_paths
[mi
] < hash
)
823 static int check_pbase_path(unsigned hash
)
825 int pos
= (!done_pbase_paths
) ? -1 : done_pbase_path_pos(hash
);
829 if (done_pbase_paths_alloc
<= done_pbase_paths_num
) {
830 done_pbase_paths_alloc
= alloc_nr(done_pbase_paths_alloc
);
831 done_pbase_paths
= xrealloc(done_pbase_paths
,
832 done_pbase_paths_alloc
*
835 done_pbase_paths_num
++;
836 if (pos
< done_pbase_paths_num
)
837 memmove(done_pbase_paths
+ pos
+ 1,
838 done_pbase_paths
+ pos
,
839 (done_pbase_paths_num
- pos
- 1) * sizeof(unsigned));
840 done_pbase_paths
[pos
] = hash
;
844 static void add_preferred_base_object(char *name
, unsigned hash
)
846 struct pbase_tree
*it
;
847 int cmplen
= name_cmp_len(name
);
849 if (check_pbase_path(hash
))
852 for (it
= pbase_tree
; it
; it
= it
->next
) {
854 hash
= name_hash("");
855 add_object_entry(it
->pcache
.sha1
, hash
, 1);
858 struct tree_desc tree
;
859 tree
.buf
= it
->pcache
.tree_data
;
860 tree
.size
= it
->pcache
.tree_size
;
861 add_pbase_object(&tree
, name
, cmplen
, name
);
866 static void add_preferred_base(unsigned char *sha1
)
868 struct pbase_tree
*it
;
871 unsigned char tree_sha1
[20];
873 data
= read_object_with_reference(sha1
, tree_type
, &size
, tree_sha1
);
877 for (it
= pbase_tree
; it
; it
= it
->next
) {
878 if (!hashcmp(it
->pcache
.sha1
, tree_sha1
)) {
884 it
= xcalloc(1, sizeof(*it
));
885 it
->next
= pbase_tree
;
888 hashcpy(it
->pcache
.sha1
, tree_sha1
);
889 it
->pcache
.tree_data
= data
;
890 it
->pcache
.tree_size
= size
;
893 static void check_object(struct object_entry
*entry
)
897 if (entry
->in_pack
&& !entry
->preferred_base
) {
898 unsigned char base
[20];
900 struct object_entry
*base_entry
;
902 /* We want in_pack_type even if we do not reuse delta.
903 * There is no point not reusing non-delta representations.
905 check_reuse_pack_delta(entry
->in_pack
,
906 entry
->in_pack_offset
,
908 &entry
->in_pack_type
);
910 /* Check if it is delta, and the base is also an object
911 * we are going to pack. If so we will reuse the existing
914 if (!no_reuse_delta
&&
915 entry
->in_pack_type
== OBJ_DELTA
&&
916 (base_entry
= locate_object_entry(base
)) &&
917 (!base_entry
->preferred_base
)) {
919 /* Depth value does not matter - find_deltas()
920 * will never consider reused delta as the
921 * base object to deltify other objects
922 * against, in order to avoid circular deltas.
925 /* uncompressed size of the delta data */
926 entry
->size
= entry
->delta_size
= size
;
927 entry
->delta
= base_entry
;
928 entry
->type
= OBJ_DELTA
;
930 entry
->delta_sibling
= base_entry
->delta_child
;
931 base_entry
->delta_child
= entry
;
935 /* Otherwise we would do the usual */
938 if (sha1_object_info(entry
->sha1
, type
, &entry
->size
))
939 die("unable to get type of object %s",
940 sha1_to_hex(entry
->sha1
));
942 if (!strcmp(type
, commit_type
)) {
943 entry
->type
= OBJ_COMMIT
;
944 } else if (!strcmp(type
, tree_type
)) {
945 entry
->type
= OBJ_TREE
;
946 } else if (!strcmp(type
, blob_type
)) {
947 entry
->type
= OBJ_BLOB
;
948 } else if (!strcmp(type
, tag_type
)) {
949 entry
->type
= OBJ_TAG
;
951 die("unable to pack object %s of type %s",
952 sha1_to_hex(entry
->sha1
), type
);
955 static unsigned int check_delta_limit(struct object_entry
*me
, unsigned int n
)
957 struct object_entry
*child
= me
->delta_child
;
960 unsigned int c
= check_delta_limit(child
, n
+ 1);
963 child
= child
->delta_sibling
;
968 static void get_object_details(void)
971 struct object_entry
*entry
;
974 for (i
= 0, entry
= objects
; i
< nr_objects
; i
++, entry
++)
977 if (nr_objects
== nr_result
) {
979 * Depth of objects that depend on the entry -- this
980 * is subtracted from depth-max to break too deep
981 * delta chain because of delta data reusing.
982 * However, we loosen this restriction when we know we
983 * are creating a thin pack -- it will have to be
984 * expanded on the other end anyway, so do not
985 * artificially cut the delta chain and let it go as
988 for (i
= 0, entry
= objects
; i
< nr_objects
; i
++, entry
++)
989 if (!entry
->delta
&& entry
->delta_child
)
991 check_delta_limit(entry
, 1);
995 typedef int (*entry_sort_t
)(const struct object_entry
*, const struct object_entry
*);
997 static entry_sort_t current_sort
;
999 static int sort_comparator(const void *_a
, const void *_b
)
1001 struct object_entry
*a
= *(struct object_entry
**)_a
;
1002 struct object_entry
*b
= *(struct object_entry
**)_b
;
1003 return current_sort(a
,b
);
1006 static struct object_entry
**create_sorted_list(entry_sort_t sort
)
1008 struct object_entry
**list
= xmalloc(nr_objects
* sizeof(struct object_entry
*));
1011 for (i
= 0; i
< nr_objects
; i
++)
1012 list
[i
] = objects
+ i
;
1013 current_sort
= sort
;
1014 qsort(list
, nr_objects
, sizeof(struct object_entry
*), sort_comparator
);
1018 static int sha1_sort(const struct object_entry
*a
, const struct object_entry
*b
)
1020 return hashcmp(a
->sha1
, b
->sha1
);
1023 static struct object_entry
**create_final_object_list(void)
1025 struct object_entry
**list
;
1028 for (i
= nr_result
= 0; i
< nr_objects
; i
++)
1029 if (!objects
[i
].preferred_base
)
1031 list
= xmalloc(nr_result
* sizeof(struct object_entry
*));
1032 for (i
= j
= 0; i
< nr_objects
; i
++) {
1033 if (!objects
[i
].preferred_base
)
1034 list
[j
++] = objects
+ i
;
1036 current_sort
= sha1_sort
;
1037 qsort(list
, nr_result
, sizeof(struct object_entry
*), sort_comparator
);
1041 static int type_size_sort(const struct object_entry
*a
, const struct object_entry
*b
)
1043 if (a
->type
< b
->type
)
1045 if (a
->type
> b
->type
)
1047 if (a
->hash
< b
->hash
)
1049 if (a
->hash
> b
->hash
)
1051 if (a
->preferred_base
< b
->preferred_base
)
1053 if (a
->preferred_base
> b
->preferred_base
)
1055 if (a
->size
< b
->size
)
1057 if (a
->size
> b
->size
)
1059 return a
< b
? -1 : (a
> b
);
1063 struct object_entry
*entry
;
1065 struct delta_index
*index
;
1069 * We search for deltas _backwards_ in a list sorted by type and
1070 * by size, so that we see progressively smaller and smaller files.
1071 * That's because we prefer deltas to be from the bigger file
1072 * to the smaller - deletes are potentially cheaper, but perhaps
1073 * more importantly, the bigger file is likely the more recent
1076 static int try_delta(struct unpacked
*trg
, struct unpacked
*src
,
1079 struct object_entry
*trg_entry
= trg
->entry
;
1080 struct object_entry
*src_entry
= src
->entry
;
1081 unsigned long trg_size
, src_size
, delta_size
, sizediff
, max_size
, sz
;
1085 /* Don't bother doing diffs between different types */
1086 if (trg_entry
->type
!= src_entry
->type
)
1089 /* We do not compute delta to *create* objects we are not
1092 if (trg_entry
->preferred_base
)
1096 * We do not bother to try a delta that we discarded
1097 * on an earlier try, but only when reusing delta data.
1099 if (!no_reuse_delta
&& trg_entry
->in_pack
&&
1100 trg_entry
->in_pack
== src_entry
->in_pack
)
1104 * If the current object is at pack edge, take the depth the
1105 * objects that depend on the current object into account --
1106 * otherwise they would become too deep.
1108 if (trg_entry
->delta_child
) {
1109 if (max_depth
<= trg_entry
->delta_limit
)
1111 max_depth
-= trg_entry
->delta_limit
;
1113 if (src_entry
->depth
>= max_depth
)
1116 /* Now some size filtering heuristics. */
1117 trg_size
= trg_entry
->size
;
1118 max_size
= trg_size
/2 - 20;
1119 max_size
= max_size
* (max_depth
- src_entry
->depth
) / max_depth
;
1122 if (trg_entry
->delta
&& trg_entry
->delta_size
<= max_size
)
1123 max_size
= trg_entry
->delta_size
-1;
1124 src_size
= src_entry
->size
;
1125 sizediff
= src_size
< trg_size
? trg_size
- src_size
: 0;
1126 if (sizediff
>= max_size
)
1129 /* Load data if not already done */
1131 trg
->data
= read_sha1_file(trg_entry
->sha1
, type
, &sz
);
1133 die("object %s inconsistent object length (%lu vs %lu)",
1134 sha1_to_hex(trg_entry
->sha1
), sz
, trg_size
);
1137 src
->data
= read_sha1_file(src_entry
->sha1
, type
, &sz
);
1139 die("object %s inconsistent object length (%lu vs %lu)",
1140 sha1_to_hex(src_entry
->sha1
), sz
, src_size
);
1143 src
->index
= create_delta_index(src
->data
, src_size
);
1145 die("out of memory");
1148 delta_buf
= create_delta(src
->index
, trg
->data
, trg_size
, &delta_size
, max_size
);
1152 trg_entry
->delta
= src_entry
;
1153 trg_entry
->delta_size
= delta_size
;
1154 trg_entry
->depth
= src_entry
->depth
+ 1;
1159 static void progress_interval(int signum
)
1161 progress_update
= 1;
1164 static void find_deltas(struct object_entry
**list
, int window
, int depth
)
1167 unsigned int array_size
= window
* sizeof(struct unpacked
);
1168 struct unpacked
*array
= xmalloc(array_size
);
1169 unsigned processed
= 0;
1170 unsigned last_percent
= 999;
1172 memset(array
, 0, array_size
);
1176 fprintf(stderr
, "Deltifying %d objects.\n", nr_result
);
1179 struct object_entry
*entry
= list
[i
];
1180 struct unpacked
*n
= array
+ idx
;
1183 if (!entry
->preferred_base
)
1187 unsigned percent
= processed
* 100 / nr_result
;
1188 if (percent
!= last_percent
|| progress_update
) {
1189 fprintf(stderr
, "%4u%% (%u/%u) done\r",
1190 percent
, processed
, nr_result
);
1191 progress_update
= 0;
1192 last_percent
= percent
;
1197 /* This happens if we decided to reuse existing
1198 * delta from a pack. "!no_reuse_delta &&" is implied.
1202 if (entry
->size
< 50)
1204 free_delta_index(n
->index
);
1212 unsigned int other_idx
= idx
+ j
;
1214 if (other_idx
>= window
)
1215 other_idx
-= window
;
1216 m
= array
+ other_idx
;
1219 if (try_delta(n
, m
, depth
) < 0)
1222 /* if we made n a delta, and if n is already at max
1223 * depth, leaving it in the window is pointless. we
1224 * should evict it first.
1226 if (entry
->delta
&& depth
<= entry
->depth
)
1235 fputc('\n', stderr
);
1237 for (i
= 0; i
< window
; ++i
) {
1238 free_delta_index(array
[i
].index
);
1239 free(array
[i
].data
);
1244 static void prepare_pack(int window
, int depth
)
1246 get_object_details();
1247 sorted_by_type
= create_sorted_list(type_size_sort
);
1248 if (window
&& depth
)
1249 find_deltas(sorted_by_type
, window
+1, depth
);
1252 static int reuse_cached_pack(unsigned char *sha1
)
1254 static const char cache
[] = "pack-cache/pack-%s.%s";
1255 char *cached_pack
, *cached_idx
;
1256 int ifd
, ofd
, ifd_ix
= -1;
1258 cached_pack
= git_path(cache
, sha1_to_hex(sha1
), "pack");
1259 ifd
= open(cached_pack
, O_RDONLY
);
1263 if (!pack_to_stdout
) {
1264 cached_idx
= git_path(cache
, sha1_to_hex(sha1
), "idx");
1265 ifd_ix
= open(cached_idx
, O_RDONLY
);
1273 fprintf(stderr
, "Reusing %d objects pack %s\n", nr_objects
,
1276 if (pack_to_stdout
) {
1277 if (copy_fd(ifd
, 1))
1282 char name
[PATH_MAX
];
1283 snprintf(name
, sizeof(name
),
1284 "%s-%s.%s", base_name
, sha1_to_hex(sha1
), "pack");
1285 ofd
= open(name
, O_CREAT
| O_EXCL
| O_WRONLY
, 0666);
1287 die("unable to open %s (%s)", name
, strerror(errno
));
1288 if (copy_fd(ifd
, ofd
))
1292 snprintf(name
, sizeof(name
),
1293 "%s-%s.%s", base_name
, sha1_to_hex(sha1
), "idx");
1294 ofd
= open(name
, O_CREAT
| O_EXCL
| O_WRONLY
, 0666);
1296 die("unable to open %s (%s)", name
, strerror(errno
));
1297 if (copy_fd(ifd_ix
, ofd
))
1300 puts(sha1_to_hex(sha1
));
1306 static void setup_progress_signal(void)
1308 struct sigaction sa
;
1311 memset(&sa
, 0, sizeof(sa
));
1312 sa
.sa_handler
= progress_interval
;
1313 sigemptyset(&sa
.sa_mask
);
1314 sa
.sa_flags
= SA_RESTART
;
1315 sigaction(SIGALRM
, &sa
, NULL
);
1317 v
.it_interval
.tv_sec
= 1;
1318 v
.it_interval
.tv_usec
= 0;
1319 v
.it_value
= v
.it_interval
;
1320 setitimer(ITIMER_REAL
, &v
, NULL
);
1323 static int git_pack_config(const char *k
, const char *v
)
1325 if(!strcmp(k
, "pack.window")) {
1326 window
= git_config_int(k
, v
);
1329 return git_default_config(k
, v
);
1332 static void read_object_list_from_stdin(void)
1334 int num_preferred_base
= 0;
1335 char line
[40 + 1 + PATH_MAX
+ 2];
1336 unsigned char sha1
[20];
1340 if (!fgets(line
, sizeof(line
), stdin
)) {
1344 die("fgets returned NULL, not EOF, not error!");
1346 die("fgets: %s", strerror(errno
));
1350 if (line
[0] == '-') {
1351 if (get_sha1_hex(line
+1, sha1
))
1352 die("expected edge sha1, got garbage:\n %s",
1354 if (num_preferred_base
++ < window
)
1355 add_preferred_base(sha1
);
1358 if (get_sha1_hex(line
, sha1
))
1359 die("expected sha1, got garbage:\n %s", line
);
1361 hash
= name_hash(line
+41);
1362 add_preferred_base_object(line
+41, hash
);
1363 add_object_entry(sha1
, hash
, 0);
1367 /* copied from rev-list but needs to do things slightly differently */
1368 static void mark_edge_parents_uninteresting(struct commit
*commit
)
1370 struct commit_list
*parents
;
1372 for (parents
= commit
->parents
; parents
; parents
= parents
->next
) {
1373 struct commit
*parent
= parents
->item
;
1374 if (!(parent
->object
.flags
& UNINTERESTING
))
1376 mark_tree_uninteresting(parent
->tree
);
1380 static void mark_edges_uninteresting(struct commit_list
*list
)
1382 for ( ; list
; list
= list
->next
) {
1383 struct commit
*commit
= list
->item
;
1385 if (commit
->object
.flags
& UNINTERESTING
) {
1386 mark_tree_uninteresting(commit
->tree
);
1389 mark_edge_parents_uninteresting(commit
);
1393 static void show_commit(struct commit
*commit
)
1395 unsigned hash
= name_hash("");
1396 add_object_entry(commit
->object
.sha1
, hash
, 0);
1399 static void show_object(struct object_array_entry
*p
)
1401 unsigned hash
= name_hash(p
->name
);
1402 add_object_entry(p
->item
->sha1
, hash
, 0);
1405 static void get_object_list(int unpacked
, int all
)
1407 struct rev_info revs
;
1413 av
[0] = "pack-objects";
1414 av
[1] = "--objects";
1417 av
[ac
++] = "--unpacked";
1420 av
[ac
++] = "--stdin";
1423 init_revisions(&revs
, NULL
);
1424 save_commit_buffer
= 0;
1425 track_object_refs
= 0;
1426 setup_revisions(ac
, av
, &revs
, NULL
);
1428 /* make sure we did not get pathspecs */
1429 if (revs
.prune_data
)
1430 die("pathspec given");
1432 while (fgets(line
, sizeof(line
), stdin
) != NULL
) {
1433 int len
= strlen(line
);
1434 if (line
[len
- 1] == '\n')
1439 if (!strcmp(line
, "--not")) {
1440 flags
^= UNINTERESTING
;
1443 die("not a rev '%s'", line
);
1445 if (handle_revision_arg(line
, &revs
, flags
, 1))
1446 die("bad revision '%s'", line
);
1449 prepare_revision_walk(&revs
);
1450 mark_edges_uninteresting(revs
.commits
);
1452 traverse_commit_list(&revs
, show_commit
, show_object
);
1455 int cmd_pack_objects(int argc
, const char **argv
, const char *prefix
)
1459 struct object_entry
**list
;
1460 int use_internal_rev_list
= 0;
1465 git_config(git_pack_config
);
1467 progress
= isatty(2);
1468 for (i
= 1; i
< argc
; i
++) {
1469 const char *arg
= argv
[i
];
1474 if (!strcmp("--non-empty", arg
)) {
1478 if (!strcmp("--local", arg
)) {
1482 if (!strcmp("--progress", arg
)) {
1486 if (!strcmp("--incremental", arg
)) {
1490 if (!strncmp("--window=", arg
, 9)) {
1492 window
= strtoul(arg
+9, &end
, 0);
1493 if (!arg
[9] || *end
)
1497 if (!strncmp("--depth=", arg
, 8)) {
1499 depth
= strtoul(arg
+8, &end
, 0);
1500 if (!arg
[8] || *end
)
1504 if (!strcmp("--progress", arg
)) {
1508 if (!strcmp("-q", arg
)) {
1512 if (!strcmp("--no-reuse-delta", arg
)) {
1516 if (!strcmp("--stdout", arg
)) {
1520 if (!strcmp("--revs", arg
)) {
1521 use_internal_rev_list
= 1;
1524 if (!strcmp("--unpacked", arg
)) {
1528 if (!strcmp("--all", arg
)) {
1535 /* Traditionally "pack-objects [options] base extra" failed;
1536 * we would however want to take refs parameter that would
1537 * have been given to upstream rev-list ourselves, which means
1538 * we somehow want to say what the base name is. So the
1541 * pack-objects [options] base <refs...>
1543 * in other words, we would treat the first non-option as the
1544 * base_name and send everything else to the internal revision
1548 if (!pack_to_stdout
)
1549 base_name
= argv
[i
++];
1551 if (pack_to_stdout
!= !base_name
)
1554 /* --unpacked and --all makes sense only with --revs */
1555 if (!use_internal_rev_list
&& (unpacked
|| all
))
1558 prepare_packed_git();
1561 fprintf(stderr
, "Generating pack...\n");
1562 setup_progress_signal();
1565 if (!use_internal_rev_list
)
1566 read_object_list_from_stdin();
1568 get_object_list(unpacked
, all
);
1571 fprintf(stderr
, "Done counting %d objects.\n", nr_objects
);
1572 sorted_by_sha
= create_final_object_list();
1573 if (non_empty
&& !nr_result
)
1577 list
= sorted_by_sha
;
1578 for (i
= 0; i
< nr_result
; i
++) {
1579 struct object_entry
*entry
= *list
++;
1580 SHA1_Update(&ctx
, entry
->sha1
, 20);
1582 SHA1_Final(object_list_sha1
, &ctx
);
1583 if (progress
&& (nr_objects
!= nr_result
))
1584 fprintf(stderr
, "Result has %d objects.\n", nr_result
);
1586 if (reuse_cached_pack(object_list_sha1
))
1590 prepare_pack(window
, depth
);
1591 if (progress
&& pack_to_stdout
) {
1592 /* the other end usually displays progress itself */
1593 struct itimerval v
= {{0,},};
1594 setitimer(ITIMER_REAL
, &v
, NULL
);
1595 signal(SIGALRM
, SIG_IGN
);
1596 progress_update
= 0;
1599 if (!pack_to_stdout
) {
1601 puts(sha1_to_hex(object_list_sha1
));
1605 fprintf(stderr
, "Total %d, written %d (delta %d), reused %d (delta %d)\n",
1606 nr_result
, written
, written_delta
, reused
, reused_delta
);