10 #include "csum-file.h"
11 #include "tree-walk.h"
15 static const char pack_usage
[] = "git-pack-objects [-q] [--no-reuse-delta] [--non-empty] [--local] [--incremental] [--window=N] [--depth=N] {--stdout | base-name} < object-list";
18 unsigned char sha1
[20];
19 unsigned long size
; /* uncompressed size */
20 unsigned long offset
; /* offset into the final pack file;
21 * nonzero if already written.
23 unsigned int depth
; /* delta depth */
24 unsigned int delta_limit
; /* base adjustment for in-pack delta */
25 unsigned int hash
; /* name hint hash */
26 enum object_type type
;
27 enum object_type in_pack_type
; /* could be delta */
28 unsigned long delta_size
; /* delta data size (uncompressed) */
29 struct object_entry
*delta
; /* delta base object */
30 struct packed_git
*in_pack
; /* already in pack */
31 unsigned int in_pack_offset
;
32 struct object_entry
*delta_child
; /* deltified objects who bases me */
33 struct object_entry
*delta_sibling
; /* other deltified objects who
34 * uses the same base as me
36 int preferred_base
; /* we do not pack this, but is encouraged to
37 * be used as the base objectto delta huge
43 * Objects we are going to pack are collected in objects array (dynamically
44 * expanded). nr_objects & nr_alloc controls this array. They are stored
45 * in the order we see -- typically rev-list --objects order that gives us
46 * nice "minimum seek" order.
48 * sorted-by-sha ans sorted-by-type are arrays of pointers that point at
49 * elements in the objects array. The former is used to build the pack
50 * index (lists object names in the ascending order to help offset lookup),
51 * and the latter is used to group similar things together by try_delta()
55 static unsigned char object_list_sha1
[20];
57 static int no_reuse_delta
;
59 static int incremental
;
60 static struct object_entry
**sorted_by_sha
, **sorted_by_type
;
61 static struct object_entry
*objects
;
62 static int nr_objects
, nr_alloc
, nr_result
;
63 static const char *base_name
;
64 static unsigned char pack_file_sha1
[20];
65 static int progress
= 1;
66 static volatile sig_atomic_t progress_update
;
67 static int window
= 10;
68 static int pack_to_stdout
;
71 * The object names in objects array are hashed with this hashtable,
72 * to help looking up the entry by object name. Binary search from
73 * sorted_by_sha is also possible but this was easier to code and faster.
74 * This hashtable is built after all the objects are seen.
76 static int *object_ix
;
77 static int object_ix_hashsz
;
80 * Pack index for existing packs give us easy access to the offsets into
81 * corresponding pack file where each object's data starts, but the entries
82 * do not store the size of the compressed representation (uncompressed
83 * size is easily available by examining the pack entry header). We build
84 * a hashtable of existing packs (pack_revindex), and keep reverse index
85 * here -- pack index file is sorted by object name mapping to offset; this
86 * pack_revindex[].revindex array is an ordered list of offsets, so if you
87 * know the offset of an object, next offset is where its packed
88 * representation ends.
90 struct pack_revindex
{
92 unsigned long *revindex
;
93 } *pack_revindex
= NULL
;
94 static int pack_revindex_hashsz
;
100 static int written_delta
;
102 static int reused_delta
;
104 static int pack_revindex_ix(struct packed_git
*p
)
106 unsigned long ui
= (unsigned long)p
;
109 ui
= ui
^ (ui
>> 16); /* defeat structure alignment */
110 i
= (int)(ui
% pack_revindex_hashsz
);
111 while (pack_revindex
[i
].p
) {
112 if (pack_revindex
[i
].p
== p
)
114 if (++i
== pack_revindex_hashsz
)
120 static void prepare_pack_ix(void)
123 struct packed_git
*p
;
124 for (num
= 0, p
= packed_git
; p
; p
= p
->next
)
128 pack_revindex_hashsz
= num
* 11;
129 pack_revindex
= xcalloc(sizeof(*pack_revindex
), pack_revindex_hashsz
);
130 for (p
= packed_git
; p
; p
= p
->next
) {
131 num
= pack_revindex_ix(p
);
133 pack_revindex
[num
].p
= p
;
135 /* revindex elements are lazily initialized */
138 static int cmp_offset(const void *a_
, const void *b_
)
140 unsigned long a
= *(unsigned long *) a_
;
141 unsigned long b
= *(unsigned long *) b_
;
151 * Ordered list of offsets of objects in the pack.
153 static void prepare_pack_revindex(struct pack_revindex
*rix
)
155 struct packed_git
*p
= rix
->p
;
156 int num_ent
= num_packed_objects(p
);
158 void *index
= p
->index_base
+ 256;
160 rix
->revindex
= xmalloc(sizeof(unsigned long) * (num_ent
+ 1));
161 for (i
= 0; i
< num_ent
; i
++) {
162 unsigned int hl
= *((unsigned int *)((char *) index
+ 24*i
));
163 rix
->revindex
[i
] = ntohl(hl
);
165 /* This knows the pack format -- the 20-byte trailer
166 * follows immediately after the last object data.
168 rix
->revindex
[num_ent
] = p
->pack_size
- 20;
169 qsort(rix
->revindex
, num_ent
, sizeof(unsigned long), cmp_offset
);
172 static unsigned long find_packed_object_size(struct packed_git
*p
,
177 struct pack_revindex
*rix
;
178 unsigned long *revindex
;
179 num
= pack_revindex_ix(p
);
181 die("internal error: pack revindex uninitialized");
182 rix
= &pack_revindex
[num
];
184 prepare_pack_revindex(rix
);
185 revindex
= rix
->revindex
;
187 hi
= num_packed_objects(p
) + 1;
189 int mi
= (lo
+ hi
) / 2;
190 if (revindex
[mi
] == ofs
) {
191 return revindex
[mi
+1] - ofs
;
193 else if (ofs
< revindex
[mi
])
198 die("internal error: pack revindex corrupt");
201 static void *delta_against(void *buf
, unsigned long size
, struct object_entry
*entry
)
203 unsigned long othersize
, delta_size
;
205 void *otherbuf
= read_sha1_file(entry
->delta
->sha1
, type
, &othersize
);
209 die("unable to read %s", sha1_to_hex(entry
->delta
->sha1
));
210 delta_buf
= diff_delta(otherbuf
, othersize
,
211 buf
, size
, &delta_size
, 0);
212 if (!delta_buf
|| delta_size
!= entry
->delta_size
)
213 die("delta size changed");
220 * The per-object header is a pretty dense thing, which is
221 * - first byte: low four bits are "size", then three bits of "type",
222 * and the high bit is "size continues".
223 * - each byte afterwards: low seven bits are size continuation,
224 * with the high bit being "size continues"
226 static int encode_header(enum object_type type
, unsigned long size
, unsigned char *hdr
)
231 if (type
< OBJ_COMMIT
|| type
> OBJ_DELTA
)
232 die("bad type %d", type
);
234 c
= (type
<< 4) | (size
& 15);
246 static int revalidate_one(struct object_entry
*entry
,
247 void *data
, char *type
, unsigned long size
)
252 if (size
!= entry
->size
)
254 err
= check_sha1_signature(entry
->sha1
, data
, size
,
255 type_names
[entry
->type
]);
261 * we are going to reuse the existing pack entry data. make
262 * sure it is not corrupt.
264 static int revalidate_pack_entry(struct object_entry
*entry
)
274 e
.p
= entry
->in_pack
;
275 e
.offset
= entry
->in_pack_offset
;
277 /* the caller has already called use_packed_git() for us */
278 data
= unpack_entry_gently(&e
, type
, &size
);
279 return revalidate_one(entry
, data
, type
, size
);
282 static int revalidate_loose_object(struct object_entry
*entry
,
284 unsigned long mapsize
)
286 /* we already know this is a loose object with new type header. */
294 data
= unpack_sha1_file(map
, mapsize
, type
, &size
);
295 return revalidate_one(entry
, data
, type
, size
);
298 static unsigned long write_object(struct sha1file
*f
,
299 struct object_entry
*entry
)
304 unsigned char header
[10];
305 unsigned hdrlen
, datalen
;
306 enum object_type obj_type
;
309 if (entry
->preferred_base
)
312 obj_type
= entry
->type
;
313 if (! entry
->in_pack
)
314 to_reuse
= 0; /* can't reuse what we don't have */
315 else if (obj_type
== OBJ_DELTA
)
316 to_reuse
= 1; /* check_object() decided it for us */
317 else if (obj_type
!= entry
->in_pack_type
)
318 to_reuse
= 0; /* pack has delta which is unusable */
319 else if (entry
->delta
)
320 to_reuse
= 0; /* we want to pack afresh */
322 to_reuse
= 1; /* we have it in-pack undeltified,
323 * and we do not need to deltify it.
326 if (!entry
->in_pack
&& !entry
->delta
) {
328 unsigned long mapsize
;
329 map
= map_sha1_file(entry
->sha1
, &mapsize
);
330 if (map
&& !legacy_loose_object(map
)) {
331 /* We can copy straight into the pack file */
332 if (revalidate_loose_object(entry
, map
, mapsize
))
333 die("corrupt loose object %s",
334 sha1_to_hex(entry
->sha1
));
335 sha1write(f
, map
, mapsize
);
336 munmap(map
, mapsize
);
342 munmap(map
, mapsize
);
346 buf
= read_sha1_file(entry
->sha1
, type
, &size
);
348 die("unable to read %s", sha1_to_hex(entry
->sha1
));
349 if (size
!= entry
->size
)
350 die("object %s size inconsistency (%lu vs %lu)",
351 sha1_to_hex(entry
->sha1
), size
, entry
->size
);
353 buf
= delta_against(buf
, size
, entry
);
354 size
= entry
->delta_size
;
355 obj_type
= OBJ_DELTA
;
358 * The object header is a byte of 'type' followed by zero or
359 * more bytes of length. For deltas, the 20 bytes of delta
362 hdrlen
= encode_header(obj_type
, size
, header
);
363 sha1write(f
, header
, hdrlen
);
366 sha1write(f
, entry
->delta
, 20);
369 datalen
= sha1write_compressed(f
, buf
, size
);
373 struct packed_git
*p
= entry
->in_pack
;
376 datalen
= find_packed_object_size(p
, entry
->in_pack_offset
);
377 buf
= (char *) p
->pack_base
+ entry
->in_pack_offset
;
379 if (revalidate_pack_entry(entry
))
380 die("corrupt delta in pack %s", sha1_to_hex(entry
->sha1
));
381 sha1write(f
, buf
, datalen
);
383 hdrlen
= 0; /* not really */
384 if (obj_type
== OBJ_DELTA
)
388 if (obj_type
== OBJ_DELTA
)
391 return hdrlen
+ datalen
;
394 static unsigned long write_one(struct sha1file
*f
,
395 struct object_entry
*e
,
396 unsigned long offset
)
399 /* offset starts from header size and cannot be zero
400 * if it is written already.
404 offset
+= write_object(f
, e
);
405 /* if we are deltified, write out its base object. */
407 offset
= write_one(f
, e
->delta
, offset
);
411 static void write_pack_file(void)
415 unsigned long offset
;
416 struct pack_header hdr
;
417 unsigned last_percent
= 999;
421 f
= sha1fd(1, "<stdout>");
423 f
= sha1create("%s-%s.%s", base_name
,
424 sha1_to_hex(object_list_sha1
), "pack");
425 do_progress
= progress
;
428 fprintf(stderr
, "Writing %d objects.\n", nr_result
);
430 hdr
.hdr_signature
= htonl(PACK_SIGNATURE
);
431 hdr
.hdr_version
= htonl(PACK_VERSION
);
432 hdr
.hdr_entries
= htonl(nr_result
);
433 sha1write(f
, &hdr
, sizeof(hdr
));
434 offset
= sizeof(hdr
);
437 for (i
= 0; i
< nr_objects
; i
++) {
438 offset
= write_one(f
, objects
+ i
, offset
);
440 unsigned percent
= written
* 100 / nr_result
;
441 if (progress_update
|| percent
!= last_percent
) {
442 fprintf(stderr
, "%4u%% (%u/%u) done\r",
443 percent
, written
, nr_result
);
445 last_percent
= percent
;
452 sha1close(f
, pack_file_sha1
, 1);
455 static void write_index_file(void)
458 struct sha1file
*f
= sha1create("%s-%s.%s", base_name
,
459 sha1_to_hex(object_list_sha1
), "idx");
460 struct object_entry
**list
= sorted_by_sha
;
461 struct object_entry
**last
= list
+ nr_result
;
462 unsigned int array
[256];
465 * Write the first-level table (the list is sorted,
466 * but we use a 256-entry lookup to be able to avoid
467 * having to do eight extra binary search iterations).
469 for (i
= 0; i
< 256; i
++) {
470 struct object_entry
**next
= list
;
471 while (next
< last
) {
472 struct object_entry
*entry
= *next
;
473 if (entry
->sha1
[0] != i
)
477 array
[i
] = htonl(next
- sorted_by_sha
);
480 sha1write(f
, array
, 256 * sizeof(int));
483 * Write the actual SHA1 entries..
485 list
= sorted_by_sha
;
486 for (i
= 0; i
< nr_result
; i
++) {
487 struct object_entry
*entry
= *list
++;
488 unsigned int offset
= htonl(entry
->offset
);
489 sha1write(f
, &offset
, 4);
490 sha1write(f
, entry
->sha1
, 20);
492 sha1write(f
, pack_file_sha1
, 20);
493 sha1close(f
, NULL
, 1);
496 static int locate_object_entry_hash(const unsigned char *sha1
)
500 memcpy(&ui
, sha1
, sizeof(unsigned int));
501 i
= ui
% object_ix_hashsz
;
502 while (0 < object_ix
[i
]) {
503 if (!hashcmp(sha1
, objects
[object_ix
[i
] - 1].sha1
))
505 if (++i
== object_ix_hashsz
)
511 static struct object_entry
*locate_object_entry(const unsigned char *sha1
)
515 if (!object_ix_hashsz
)
518 i
= locate_object_entry_hash(sha1
);
520 return &objects
[object_ix
[i
]-1];
524 static void rehash_objects(void)
527 struct object_entry
*oe
;
529 object_ix_hashsz
= nr_objects
* 3;
530 if (object_ix_hashsz
< 1024)
531 object_ix_hashsz
= 1024;
532 object_ix
= xrealloc(object_ix
, sizeof(int) * object_ix_hashsz
);
533 memset(object_ix
, 0, sizeof(int) * object_ix_hashsz
);
534 for (i
= 0, oe
= objects
; i
< nr_objects
; i
++, oe
++) {
535 int ix
= locate_object_entry_hash(oe
->sha1
);
539 object_ix
[ix
] = i
+ 1;
543 static unsigned name_hash(const char *name
)
549 * This effectively just creates a sortable number from the
550 * last sixteen non-whitespace characters. Last characters
551 * count "most", so things that end in ".c" sort together.
553 while ((c
= *name
++) != 0) {
556 hash
= (hash
>> 2) + (c
<< 24);
561 static int add_object_entry(const unsigned char *sha1
, unsigned hash
, int exclude
)
563 unsigned int idx
= nr_objects
;
564 struct object_entry
*entry
;
565 struct packed_git
*p
;
566 unsigned int found_offset
= 0;
567 struct packed_git
*found_pack
= NULL
;
571 for (p
= packed_git
; p
; p
= p
->next
) {
573 if (find_pack_entry_one(sha1
, &e
, p
)) {
576 if (local
&& !p
->pack_local
)
579 found_offset
= e
.offset
;
585 if ((entry
= locate_object_entry(sha1
)) != NULL
)
588 if (idx
>= nr_alloc
) {
589 unsigned int needed
= (idx
+ 1024) * 3 / 2;
590 objects
= xrealloc(objects
, needed
* sizeof(*entry
));
593 entry
= objects
+ idx
;
594 nr_objects
= idx
+ 1;
595 memset(entry
, 0, sizeof(*entry
));
596 hashcpy(entry
->sha1
, sha1
);
599 if (object_ix_hashsz
* 3 <= nr_objects
* 4)
602 ix
= locate_object_entry_hash(entry
->sha1
);
604 die("internal error in object hashing.");
605 object_ix
[-1 - ix
] = idx
+ 1;
610 if (progress_update
) {
611 fprintf(stderr
, "Counting objects...%d\r", nr_objects
);
615 entry
->preferred_base
= 1;
618 entry
->in_pack
= found_pack
;
619 entry
->in_pack_offset
= found_offset
;
625 struct pbase_tree_cache
{
626 unsigned char sha1
[20];
630 unsigned long tree_size
;
633 static struct pbase_tree_cache
*(pbase_tree_cache
[256]);
634 static int pbase_tree_cache_ix(const unsigned char *sha1
)
636 return sha1
[0] % ARRAY_SIZE(pbase_tree_cache
);
638 static int pbase_tree_cache_ix_incr(int ix
)
640 return (ix
+1) % ARRAY_SIZE(pbase_tree_cache
);
643 static struct pbase_tree
{
644 struct pbase_tree
*next
;
645 /* This is a phony "cache" entry; we are not
646 * going to evict it nor find it through _get()
647 * mechanism -- this is for the toplevel node that
648 * would almost always change with any commit.
650 struct pbase_tree_cache pcache
;
653 static struct pbase_tree_cache
*pbase_tree_get(const unsigned char *sha1
)
655 struct pbase_tree_cache
*ent
, *nent
;
660 int my_ix
= pbase_tree_cache_ix(sha1
);
661 int available_ix
= -1;
663 /* pbase-tree-cache acts as a limited hashtable.
664 * your object will be found at your index or within a few
665 * slots after that slot if it is cached.
667 for (neigh
= 0; neigh
< 8; neigh
++) {
668 ent
= pbase_tree_cache
[my_ix
];
669 if (ent
&& !hashcmp(ent
->sha1
, sha1
)) {
673 else if (((available_ix
< 0) && (!ent
|| !ent
->ref
)) ||
674 ((0 <= available_ix
) &&
675 (!ent
&& pbase_tree_cache
[available_ix
])))
676 available_ix
= my_ix
;
679 my_ix
= pbase_tree_cache_ix_incr(my_ix
);
682 /* Did not find one. Either we got a bogus request or
683 * we need to read and perhaps cache.
685 data
= read_sha1_file(sha1
, type
, &size
);
688 if (strcmp(type
, tree_type
)) {
693 /* We need to either cache or return a throwaway copy */
695 if (available_ix
< 0)
698 ent
= pbase_tree_cache
[available_ix
];
699 my_ix
= available_ix
;
703 nent
= xmalloc(sizeof(*nent
));
704 nent
->temporary
= (available_ix
< 0);
707 /* evict and reuse */
708 free(ent
->tree_data
);
711 hashcpy(nent
->sha1
, sha1
);
712 nent
->tree_data
= data
;
713 nent
->tree_size
= size
;
715 if (!nent
->temporary
)
716 pbase_tree_cache
[my_ix
] = nent
;
720 static void pbase_tree_put(struct pbase_tree_cache
*cache
)
722 if (!cache
->temporary
) {
726 free(cache
->tree_data
);
730 static int name_cmp_len(const char *name
)
733 for (i
= 0; name
[i
] && name
[i
] != '\n' && name
[i
] != '/'; i
++)
738 static void add_pbase_object(struct tree_desc
*tree
,
741 const char *fullname
)
743 struct name_entry entry
;
745 while (tree_entry(tree
,&entry
)) {
749 if (entry
.pathlen
!= cmplen
||
750 memcmp(entry
.path
, name
, cmplen
) ||
751 !has_sha1_file(entry
.sha1
) ||
752 sha1_object_info(entry
.sha1
, type
, &size
))
754 if (name
[cmplen
] != '/') {
755 unsigned hash
= name_hash(fullname
);
756 add_object_entry(entry
.sha1
, hash
, 1);
759 if (!strcmp(type
, tree_type
)) {
760 struct tree_desc sub
;
761 struct pbase_tree_cache
*tree
;
762 const char *down
= name
+cmplen
+1;
763 int downlen
= name_cmp_len(down
);
765 tree
= pbase_tree_get(entry
.sha1
);
768 sub
.buf
= tree
->tree_data
;
769 sub
.size
= tree
->tree_size
;
771 add_pbase_object(&sub
, down
, downlen
, fullname
);
772 pbase_tree_put(tree
);
777 static unsigned *done_pbase_paths
;
778 static int done_pbase_paths_num
;
779 static int done_pbase_paths_alloc
;
780 static int done_pbase_path_pos(unsigned hash
)
783 int hi
= done_pbase_paths_num
;
785 int mi
= (hi
+ lo
) / 2;
786 if (done_pbase_paths
[mi
] == hash
)
788 if (done_pbase_paths
[mi
] < hash
)
796 static int check_pbase_path(unsigned hash
)
798 int pos
= (!done_pbase_paths
) ? -1 : done_pbase_path_pos(hash
);
802 if (done_pbase_paths_alloc
<= done_pbase_paths_num
) {
803 done_pbase_paths_alloc
= alloc_nr(done_pbase_paths_alloc
);
804 done_pbase_paths
= xrealloc(done_pbase_paths
,
805 done_pbase_paths_alloc
*
808 done_pbase_paths_num
++;
809 if (pos
< done_pbase_paths_num
)
810 memmove(done_pbase_paths
+ pos
+ 1,
811 done_pbase_paths
+ pos
,
812 (done_pbase_paths_num
- pos
- 1) * sizeof(unsigned));
813 done_pbase_paths
[pos
] = hash
;
817 static void add_preferred_base_object(char *name
, unsigned hash
)
819 struct pbase_tree
*it
;
820 int cmplen
= name_cmp_len(name
);
822 if (check_pbase_path(hash
))
825 for (it
= pbase_tree
; it
; it
= it
->next
) {
827 hash
= name_hash("");
828 add_object_entry(it
->pcache
.sha1
, hash
, 1);
831 struct tree_desc tree
;
832 tree
.buf
= it
->pcache
.tree_data
;
833 tree
.size
= it
->pcache
.tree_size
;
834 add_pbase_object(&tree
, name
, cmplen
, name
);
839 static void add_preferred_base(unsigned char *sha1
)
841 struct pbase_tree
*it
;
844 unsigned char tree_sha1
[20];
846 data
= read_object_with_reference(sha1
, tree_type
, &size
, tree_sha1
);
850 for (it
= pbase_tree
; it
; it
= it
->next
) {
851 if (!hashcmp(it
->pcache
.sha1
, tree_sha1
)) {
857 it
= xcalloc(1, sizeof(*it
));
858 it
->next
= pbase_tree
;
861 hashcpy(it
->pcache
.sha1
, tree_sha1
);
862 it
->pcache
.tree_data
= data
;
863 it
->pcache
.tree_size
= size
;
866 static void check_object(struct object_entry
*entry
)
870 if (entry
->in_pack
&& !entry
->preferred_base
) {
871 unsigned char base
[20];
873 struct object_entry
*base_entry
;
875 /* We want in_pack_type even if we do not reuse delta.
876 * There is no point not reusing non-delta representations.
878 check_reuse_pack_delta(entry
->in_pack
,
879 entry
->in_pack_offset
,
881 &entry
->in_pack_type
);
883 /* Check if it is delta, and the base is also an object
884 * we are going to pack. If so we will reuse the existing
887 if (!no_reuse_delta
&&
888 entry
->in_pack_type
== OBJ_DELTA
&&
889 (base_entry
= locate_object_entry(base
)) &&
890 (!base_entry
->preferred_base
)) {
892 /* Depth value does not matter - find_deltas()
893 * will never consider reused delta as the
894 * base object to deltify other objects
895 * against, in order to avoid circular deltas.
898 /* uncompressed size of the delta data */
899 entry
->size
= entry
->delta_size
= size
;
900 entry
->delta
= base_entry
;
901 entry
->type
= OBJ_DELTA
;
903 entry
->delta_sibling
= base_entry
->delta_child
;
904 base_entry
->delta_child
= entry
;
908 /* Otherwise we would do the usual */
911 if (sha1_object_info(entry
->sha1
, type
, &entry
->size
))
912 die("unable to get type of object %s",
913 sha1_to_hex(entry
->sha1
));
915 if (!strcmp(type
, commit_type
)) {
916 entry
->type
= OBJ_COMMIT
;
917 } else if (!strcmp(type
, tree_type
)) {
918 entry
->type
= OBJ_TREE
;
919 } else if (!strcmp(type
, blob_type
)) {
920 entry
->type
= OBJ_BLOB
;
921 } else if (!strcmp(type
, tag_type
)) {
922 entry
->type
= OBJ_TAG
;
924 die("unable to pack object %s of type %s",
925 sha1_to_hex(entry
->sha1
), type
);
928 static unsigned int check_delta_limit(struct object_entry
*me
, unsigned int n
)
930 struct object_entry
*child
= me
->delta_child
;
933 unsigned int c
= check_delta_limit(child
, n
+ 1);
936 child
= child
->delta_sibling
;
941 static void get_object_details(void)
944 struct object_entry
*entry
;
947 for (i
= 0, entry
= objects
; i
< nr_objects
; i
++, entry
++)
950 if (nr_objects
== nr_result
) {
952 * Depth of objects that depend on the entry -- this
953 * is subtracted from depth-max to break too deep
954 * delta chain because of delta data reusing.
955 * However, we loosen this restriction when we know we
956 * are creating a thin pack -- it will have to be
957 * expanded on the other end anyway, so do not
958 * artificially cut the delta chain and let it go as
961 for (i
= 0, entry
= objects
; i
< nr_objects
; i
++, entry
++)
962 if (!entry
->delta
&& entry
->delta_child
)
964 check_delta_limit(entry
, 1);
968 typedef int (*entry_sort_t
)(const struct object_entry
*, const struct object_entry
*);
970 static entry_sort_t current_sort
;
972 static int sort_comparator(const void *_a
, const void *_b
)
974 struct object_entry
*a
= *(struct object_entry
**)_a
;
975 struct object_entry
*b
= *(struct object_entry
**)_b
;
976 return current_sort(a
,b
);
979 static struct object_entry
**create_sorted_list(entry_sort_t sort
)
981 struct object_entry
**list
= xmalloc(nr_objects
* sizeof(struct object_entry
*));
984 for (i
= 0; i
< nr_objects
; i
++)
985 list
[i
] = objects
+ i
;
987 qsort(list
, nr_objects
, sizeof(struct object_entry
*), sort_comparator
);
991 static int sha1_sort(const struct object_entry
*a
, const struct object_entry
*b
)
993 return hashcmp(a
->sha1
, b
->sha1
);
996 static struct object_entry
**create_final_object_list(void)
998 struct object_entry
**list
;
1001 for (i
= nr_result
= 0; i
< nr_objects
; i
++)
1002 if (!objects
[i
].preferred_base
)
1004 list
= xmalloc(nr_result
* sizeof(struct object_entry
*));
1005 for (i
= j
= 0; i
< nr_objects
; i
++) {
1006 if (!objects
[i
].preferred_base
)
1007 list
[j
++] = objects
+ i
;
1009 current_sort
= sha1_sort
;
1010 qsort(list
, nr_result
, sizeof(struct object_entry
*), sort_comparator
);
1014 static int type_size_sort(const struct object_entry
*a
, const struct object_entry
*b
)
1016 if (a
->type
< b
->type
)
1018 if (a
->type
> b
->type
)
1020 if (a
->hash
< b
->hash
)
1022 if (a
->hash
> b
->hash
)
1024 if (a
->preferred_base
< b
->preferred_base
)
1026 if (a
->preferred_base
> b
->preferred_base
)
1028 if (a
->size
< b
->size
)
1030 if (a
->size
> b
->size
)
1032 return a
< b
? -1 : (a
> b
);
1036 struct object_entry
*entry
;
1038 struct delta_index
*index
;
1042 * We search for deltas _backwards_ in a list sorted by type and
1043 * by size, so that we see progressively smaller and smaller files.
1044 * That's because we prefer deltas to be from the bigger file
1045 * to the smaller - deletes are potentially cheaper, but perhaps
1046 * more importantly, the bigger file is likely the more recent
1049 static int try_delta(struct unpacked
*trg
, struct unpacked
*src
,
1052 struct object_entry
*trg_entry
= trg
->entry
;
1053 struct object_entry
*src_entry
= src
->entry
;
1054 unsigned long trg_size
, src_size
, delta_size
, sizediff
, max_size
, sz
;
1058 /* Don't bother doing diffs between different types */
1059 if (trg_entry
->type
!= src_entry
->type
)
1062 /* We do not compute delta to *create* objects we are not
1065 if (trg_entry
->preferred_base
)
1069 * We do not bother to try a delta that we discarded
1070 * on an earlier try, but only when reusing delta data.
1072 if (!no_reuse_delta
&& trg_entry
->in_pack
&&
1073 trg_entry
->in_pack
== src_entry
->in_pack
)
1077 * If the current object is at pack edge, take the depth the
1078 * objects that depend on the current object into account --
1079 * otherwise they would become too deep.
1081 if (trg_entry
->delta_child
) {
1082 if (max_depth
<= trg_entry
->delta_limit
)
1084 max_depth
-= trg_entry
->delta_limit
;
1086 if (src_entry
->depth
>= max_depth
)
1089 /* Now some size filtering heuristics. */
1090 trg_size
= trg_entry
->size
;
1091 max_size
= trg_size
/2 - 20;
1092 max_size
= max_size
* (max_depth
- src_entry
->depth
) / max_depth
;
1095 if (trg_entry
->delta
&& trg_entry
->delta_size
<= max_size
)
1096 max_size
= trg_entry
->delta_size
-1;
1097 src_size
= src_entry
->size
;
1098 sizediff
= src_size
< trg_size
? trg_size
- src_size
: 0;
1099 if (sizediff
>= max_size
)
1102 /* Load data if not already done */
1104 trg
->data
= read_sha1_file(trg_entry
->sha1
, type
, &sz
);
1106 die("object %s inconsistent object length (%lu vs %lu)",
1107 sha1_to_hex(trg_entry
->sha1
), sz
, trg_size
);
1110 src
->data
= read_sha1_file(src_entry
->sha1
, type
, &sz
);
1112 die("object %s inconsistent object length (%lu vs %lu)",
1113 sha1_to_hex(src_entry
->sha1
), sz
, src_size
);
1116 src
->index
= create_delta_index(src
->data
, src_size
);
1118 die("out of memory");
1121 delta_buf
= create_delta(src
->index
, trg
->data
, trg_size
, &delta_size
, max_size
);
1125 trg_entry
->delta
= src_entry
;
1126 trg_entry
->delta_size
= delta_size
;
1127 trg_entry
->depth
= src_entry
->depth
+ 1;
1132 static void progress_interval(int signum
)
1134 progress_update
= 1;
1137 static void find_deltas(struct object_entry
**list
, int window
, int depth
)
1140 unsigned int array_size
= window
* sizeof(struct unpacked
);
1141 struct unpacked
*array
= xmalloc(array_size
);
1142 unsigned processed
= 0;
1143 unsigned last_percent
= 999;
1145 memset(array
, 0, array_size
);
1149 fprintf(stderr
, "Deltifying %d objects.\n", nr_result
);
1152 struct object_entry
*entry
= list
[i
];
1153 struct unpacked
*n
= array
+ idx
;
1156 if (!entry
->preferred_base
)
1160 unsigned percent
= processed
* 100 / nr_result
;
1161 if (percent
!= last_percent
|| progress_update
) {
1162 fprintf(stderr
, "%4u%% (%u/%u) done\r",
1163 percent
, processed
, nr_result
);
1164 progress_update
= 0;
1165 last_percent
= percent
;
1170 /* This happens if we decided to reuse existing
1171 * delta from a pack. "!no_reuse_delta &&" is implied.
1175 if (entry
->size
< 50)
1177 free_delta_index(n
->index
);
1185 unsigned int other_idx
= idx
+ j
;
1187 if (other_idx
>= window
)
1188 other_idx
-= window
;
1189 m
= array
+ other_idx
;
1192 if (try_delta(n
, m
, depth
) < 0)
1195 /* if we made n a delta, and if n is already at max
1196 * depth, leaving it in the window is pointless. we
1197 * should evict it first.
1199 if (entry
->delta
&& depth
<= entry
->depth
)
1208 fputc('\n', stderr
);
1210 for (i
= 0; i
< window
; ++i
) {
1211 free_delta_index(array
[i
].index
);
1212 free(array
[i
].data
);
1217 static void prepare_pack(int window
, int depth
)
1219 get_object_details();
1220 sorted_by_type
= create_sorted_list(type_size_sort
);
1221 if (window
&& depth
)
1222 find_deltas(sorted_by_type
, window
+1, depth
);
1225 static int reuse_cached_pack(unsigned char *sha1
)
1227 static const char cache
[] = "pack-cache/pack-%s.%s";
1228 char *cached_pack
, *cached_idx
;
1229 int ifd
, ofd
, ifd_ix
= -1;
1231 cached_pack
= git_path(cache
, sha1_to_hex(sha1
), "pack");
1232 ifd
= open(cached_pack
, O_RDONLY
);
1236 if (!pack_to_stdout
) {
1237 cached_idx
= git_path(cache
, sha1_to_hex(sha1
), "idx");
1238 ifd_ix
= open(cached_idx
, O_RDONLY
);
1246 fprintf(stderr
, "Reusing %d objects pack %s\n", nr_objects
,
1249 if (pack_to_stdout
) {
1250 if (copy_fd(ifd
, 1))
1255 char name
[PATH_MAX
];
1256 snprintf(name
, sizeof(name
),
1257 "%s-%s.%s", base_name
, sha1_to_hex(sha1
), "pack");
1258 ofd
= open(name
, O_CREAT
| O_EXCL
| O_WRONLY
, 0666);
1260 die("unable to open %s (%s)", name
, strerror(errno
));
1261 if (copy_fd(ifd
, ofd
))
1265 snprintf(name
, sizeof(name
),
1266 "%s-%s.%s", base_name
, sha1_to_hex(sha1
), "idx");
1267 ofd
= open(name
, O_CREAT
| O_EXCL
| O_WRONLY
, 0666);
1269 die("unable to open %s (%s)", name
, strerror(errno
));
1270 if (copy_fd(ifd_ix
, ofd
))
1273 puts(sha1_to_hex(sha1
));
1279 static void setup_progress_signal(void)
1281 struct sigaction sa
;
1284 memset(&sa
, 0, sizeof(sa
));
1285 sa
.sa_handler
= progress_interval
;
1286 sigemptyset(&sa
.sa_mask
);
1287 sa
.sa_flags
= SA_RESTART
;
1288 sigaction(SIGALRM
, &sa
, NULL
);
1290 v
.it_interval
.tv_sec
= 1;
1291 v
.it_interval
.tv_usec
= 0;
1292 v
.it_value
= v
.it_interval
;
1293 setitimer(ITIMER_REAL
, &v
, NULL
);
1296 static int git_pack_config(const char *k
, const char *v
)
1298 if(!strcmp(k
, "pack.window")) {
1299 window
= git_config_int(k
, v
);
1302 return git_default_config(k
, v
);
1305 int cmd_pack_objects(int argc
, const char **argv
, const char *prefix
)
1308 char line
[40 + 1 + PATH_MAX
+ 2];
1310 struct object_entry
**list
;
1311 int num_preferred_base
= 0;
1314 git_config(git_pack_config
);
1316 progress
= isatty(2);
1317 for (i
= 1; i
< argc
; i
++) {
1318 const char *arg
= argv
[i
];
1321 if (!strcmp("--non-empty", arg
)) {
1325 if (!strcmp("--local", arg
)) {
1329 if (!strcmp("--progress", arg
)) {
1333 if (!strcmp("--incremental", arg
)) {
1337 if (!strncmp("--window=", arg
, 9)) {
1339 window
= strtoul(arg
+9, &end
, 0);
1340 if (!arg
[9] || *end
)
1344 if (!strncmp("--depth=", arg
, 8)) {
1346 depth
= strtoul(arg
+8, &end
, 0);
1347 if (!arg
[8] || *end
)
1351 if (!strcmp("--progress", arg
)) {
1355 if (!strcmp("-q", arg
)) {
1359 if (!strcmp("--no-reuse-delta", arg
)) {
1363 if (!strcmp("--stdout", arg
)) {
1374 if (pack_to_stdout
!= !base_name
)
1377 prepare_packed_git();
1380 fprintf(stderr
, "Generating pack...\n");
1381 setup_progress_signal();
1385 unsigned char sha1
[20];
1388 if (!fgets(line
, sizeof(line
), stdin
)) {
1392 die("fgets returned NULL, not EOF, not error!");
1394 die("fgets: %s", strerror(errno
));
1399 if (line
[0] == '-') {
1400 if (get_sha1_hex(line
+1, sha1
))
1401 die("expected edge sha1, got garbage:\n %s",
1403 if (num_preferred_base
++ < window
)
1404 add_preferred_base(sha1
);
1407 if (get_sha1_hex(line
, sha1
))
1408 die("expected sha1, got garbage:\n %s", line
);
1409 hash
= name_hash(line
+41);
1410 add_preferred_base_object(line
+41, hash
);
1411 add_object_entry(sha1
, hash
, 0);
1414 fprintf(stderr
, "Done counting %d objects.\n", nr_objects
);
1415 sorted_by_sha
= create_final_object_list();
1416 if (non_empty
&& !nr_result
)
1420 list
= sorted_by_sha
;
1421 for (i
= 0; i
< nr_result
; i
++) {
1422 struct object_entry
*entry
= *list
++;
1423 SHA1_Update(&ctx
, entry
->sha1
, 20);
1425 SHA1_Final(object_list_sha1
, &ctx
);
1426 if (progress
&& (nr_objects
!= nr_result
))
1427 fprintf(stderr
, "Result has %d objects.\n", nr_result
);
1429 if (reuse_cached_pack(object_list_sha1
))
1433 prepare_pack(window
, depth
);
1434 if (progress
&& pack_to_stdout
) {
1435 /* the other end usually displays progress itself */
1436 struct itimerval v
= {{0,},};
1437 setitimer(ITIMER_REAL
, &v
, NULL
);
1438 signal(SIGALRM
, SIG_IGN
);
1439 progress_update
= 0;
1442 if (!pack_to_stdout
) {
1444 puts(sha1_to_hex(object_list_sha1
));
1448 fprintf(stderr
, "Total %d, written %d (delta %d), reused %d (delta %d)\n",
1449 nr_result
, written
, written_delta
, reused
, reused_delta
);