3 * Copyright 2005, Lukas Sandstrom <lukass@etek.chalmers.se>
5 * This file is licensed under the GPL v2.
10 #include "repository.h"
12 #include "object-store.h"
16 static const char pack_redundant_usage
[] =
17 "git pack-redundant [--verbose] [--alt-odb] (--all | <filename.pack>...)";
19 static int load_all_packs
, verbose
, alt_odb
;
22 struct llist_item
*next
;
23 const unsigned char *sha1
;
26 struct llist_item
*front
;
27 struct llist_item
*back
;
29 } *all_objects
; /* all objects which must be present in local packfiles */
31 static struct pack_list
{
32 struct pack_list
*next
;
33 struct packed_git
*pack
;
34 struct llist
*unique_objects
;
35 struct llist
*all_objects
;
36 } *local_packs
= NULL
, *altodb_packs
= NULL
;
43 static struct llist_item
*free_nodes
;
45 static inline void llist_item_put(struct llist_item
*item
)
47 item
->next
= free_nodes
;
51 static inline struct llist_item
*llist_item_get(void)
53 struct llist_item
*new_item
;
55 new_item
= free_nodes
;
56 free_nodes
= free_nodes
->next
;
59 ALLOC_ARRAY(new_item
, BLKSIZE
);
60 for (; i
< BLKSIZE
; i
++)
61 llist_item_put(&new_item
[i
]);
66 static void llist_free(struct llist
*list
)
68 while ((list
->back
= list
->front
)) {
69 list
->front
= list
->front
->next
;
70 llist_item_put(list
->back
);
75 static inline void llist_init(struct llist
**list
)
77 *list
= xmalloc(sizeof(struct llist
));
78 (*list
)->front
= (*list
)->back
= NULL
;
82 static struct llist
* llist_copy(struct llist
*list
)
85 struct llist_item
*new_item
, *old_item
, *prev
;
89 if ((ret
->size
= list
->size
) == 0)
92 new_item
= ret
->front
= llist_item_get();
93 new_item
->sha1
= list
->front
->sha1
;
95 old_item
= list
->front
->next
;
98 new_item
= llist_item_get();
99 prev
->next
= new_item
;
100 new_item
->sha1
= old_item
->sha1
;
101 old_item
= old_item
->next
;
103 new_item
->next
= NULL
;
104 ret
->back
= new_item
;
109 static inline struct llist_item
*llist_insert(struct llist
*list
,
110 struct llist_item
*after
,
111 const unsigned char *sha1
)
113 struct llist_item
*new_item
= llist_item_get();
114 new_item
->sha1
= sha1
;
115 new_item
->next
= NULL
;
118 new_item
->next
= after
->next
;
119 after
->next
= new_item
;
120 if (after
== list
->back
)
121 list
->back
= new_item
;
122 } else {/* insert in front */
124 list
->back
= new_item
;
126 new_item
->next
= list
->front
;
127 list
->front
= new_item
;
133 static inline struct llist_item
*llist_insert_back(struct llist
*list
,
134 const unsigned char *sha1
)
136 return llist_insert(list
, list
->back
, sha1
);
139 static inline struct llist_item
*llist_insert_sorted_unique(struct llist
*list
,
140 const unsigned char *sha1
, struct llist_item
*hint
)
142 struct llist_item
*prev
= NULL
, *l
;
144 l
= (hint
== NULL
) ? list
->front
: hint
;
146 int cmp
= hashcmp(l
->sha1
, sha1
);
147 if (cmp
> 0) { /* we insert before this entry */
148 return llist_insert(list
, prev
, sha1
);
150 if (!cmp
) { /* already exists */
156 /* insert at the end */
157 return llist_insert_back(list
, sha1
);
160 /* returns a pointer to an item in front of sha1 */
161 static inline struct llist_item
* llist_sorted_remove(struct llist
*list
, const unsigned char *sha1
, struct llist_item
*hint
)
163 struct llist_item
*prev
, *l
;
166 l
= (hint
== NULL
) ? list
->front
: hint
;
169 int cmp
= hashcmp(l
->sha1
, sha1
);
170 if (cmp
> 0) /* not in list, since sorted */
172 if (!cmp
) { /* found */
174 if (hint
!= NULL
&& hint
!= list
->front
) {
175 /* we don't know the previous element */
177 goto redo_from_start
;
179 list
->front
= l
->next
;
181 prev
->next
= l
->next
;
195 static void llist_sorted_difference_inplace(struct llist
*A
,
198 struct llist_item
*hint
, *b
;
204 hint
= llist_sorted_remove(A
, b
->sha1
, hint
);
209 static inline struct pack_list
* pack_list_insert(struct pack_list
**pl
,
210 struct pack_list
*entry
)
212 struct pack_list
*p
= xmalloc(sizeof(struct pack_list
));
213 memcpy(p
, entry
, sizeof(struct pack_list
));
219 static inline size_t pack_list_size(struct pack_list
*pl
)
229 static struct pack_list
* pack_list_difference(const struct pack_list
*A
,
230 const struct pack_list
*B
)
232 struct pack_list
*ret
;
233 const struct pack_list
*pl
;
240 if (A
->pack
== pl
->pack
)
241 return pack_list_difference(A
->next
, B
);
244 ret
= xmalloc(sizeof(struct pack_list
));
245 memcpy(ret
, A
, sizeof(struct pack_list
));
246 ret
->next
= pack_list_difference(A
->next
, B
);
250 static void cmp_two_packs(struct pack_list
*p1
, struct pack_list
*p2
)
252 unsigned long p1_off
= 0, p2_off
= 0, p1_step
, p2_step
;
253 const unsigned char *p1_base
, *p2_base
;
254 struct llist_item
*p1_hint
= NULL
, *p2_hint
= NULL
;
255 const unsigned int hashsz
= the_hash_algo
->rawsz
;
257 p1_base
= p1
->pack
->index_data
;
258 p2_base
= p2
->pack
->index_data
;
259 p1_base
+= 256 * 4 + ((p1
->pack
->index_version
< 2) ? 4 : 8);
260 p2_base
+= 256 * 4 + ((p2
->pack
->index_version
< 2) ? 4 : 8);
261 p1_step
= hashsz
+ ((p1
->pack
->index_version
< 2) ? 4 : 0);
262 p2_step
= hashsz
+ ((p2
->pack
->index_version
< 2) ? 4 : 0);
264 while (p1_off
< p1
->pack
->num_objects
* p1_step
&&
265 p2_off
< p2
->pack
->num_objects
* p2_step
)
267 int cmp
= hashcmp(p1_base
+ p1_off
, p2_base
+ p2_off
);
270 p1_hint
= llist_sorted_remove(p1
->unique_objects
,
271 p1_base
+ p1_off
, p1_hint
);
272 p2_hint
= llist_sorted_remove(p2
->unique_objects
,
273 p1_base
+ p1_off
, p2_hint
);
278 if (cmp
< 0) { /* p1 has the object, p2 doesn't */
280 } else { /* p2 has the object, p1 doesn't */
286 static void pll_free(struct pll
*l
)
289 struct pack_list
*opl
;
303 /* all the permutations have to be free()d at the same time,
304 * since they refer to each other
306 static struct pll
* get_permutations(struct pack_list
*list
, int n
)
308 struct pll
*subset
, *ret
= NULL
, *new_pll
= NULL
;
310 if (list
== NULL
|| pack_list_size(list
) < n
|| n
== 0)
315 new_pll
= xmalloc(sizeof(*new_pll
));
317 pack_list_insert(&new_pll
->pl
, list
);
326 subset
= get_permutations(list
->next
, n
- 1);
328 new_pll
= xmalloc(sizeof(*new_pll
));
329 new_pll
->pl
= subset
->pl
;
330 pack_list_insert(&new_pll
->pl
, list
);
333 subset
= subset
->next
;
340 static int is_superset(struct pack_list
*pl
, struct llist
*list
)
344 diff
= llist_copy(list
);
347 llist_sorted_difference_inplace(diff
, pl
->all_objects
);
348 if (diff
->size
== 0) { /* we're done */
358 static size_t sizeof_union(struct packed_git
*p1
, struct packed_git
*p2
)
361 unsigned long p1_off
= 0, p2_off
= 0, p1_step
, p2_step
;
362 const unsigned char *p1_base
, *p2_base
;
363 const unsigned int hashsz
= the_hash_algo
->rawsz
;
365 p1_base
= p1
->index_data
;
366 p2_base
= p2
->index_data
;
367 p1_base
+= 256 * 4 + ((p1
->index_version
< 2) ? 4 : 8);
368 p2_base
+= 256 * 4 + ((p2
->index_version
< 2) ? 4 : 8);
369 p1_step
= hashsz
+ ((p1
->index_version
< 2) ? 4 : 0);
370 p2_step
= hashsz
+ ((p2
->index_version
< 2) ? 4 : 0);
372 while (p1_off
< p1
->num_objects
* p1_step
&&
373 p2_off
< p2
->num_objects
* p2_step
)
375 int cmp
= hashcmp(p1_base
+ p1_off
, p2_base
+ p2_off
);
383 if (cmp
< 0) { /* p1 has the object, p2 doesn't */
385 } else { /* p2 has the object, p1 doesn't */
392 /* another O(n^2) function ... */
393 static size_t get_pack_redundancy(struct pack_list
*pl
)
395 struct pack_list
*subset
;
401 while ((subset
= pl
->next
)) {
403 ret
+= sizeof_union(pl
->pack
, subset
->pack
);
404 subset
= subset
->next
;
411 static inline off_t
pack_set_bytecount(struct pack_list
*pl
)
415 ret
+= pl
->pack
->pack_size
;
416 ret
+= pl
->pack
->index_size
;
422 static void minimize(struct pack_list
**min
)
424 struct pack_list
*pl
, *unique
= NULL
,
425 *non_unique
= NULL
, *min_perm
= NULL
;
426 struct pll
*perm
, *perm_all
, *perm_ok
= NULL
, *new_perm
;
427 struct llist
*missing
;
428 off_t min_perm_size
= 0, perm_size
;
433 if (pl
->unique_objects
->size
)
434 pack_list_insert(&unique
, pl
);
436 pack_list_insert(&non_unique
, pl
);
439 /* find out which objects are missing from the set of unique packs */
440 missing
= llist_copy(all_objects
);
443 llist_sorted_difference_inplace(missing
, pl
->all_objects
);
447 /* return if there are no objects missing from the unique set */
448 if (missing
->size
== 0) {
454 /* find the permutations which contain all missing objects */
455 for (n
= 1; n
<= pack_list_size(non_unique
) && !perm_ok
; n
++) {
456 perm_all
= perm
= get_permutations(non_unique
, n
);
458 if (is_superset(perm
->pl
, missing
)) {
459 new_perm
= xmalloc(sizeof(struct pll
));
460 memcpy(new_perm
, perm
, sizeof(struct pll
));
461 new_perm
->next
= perm_ok
;
471 die("Internal error: No complete sets found!");
473 /* find the permutation with the smallest size */
476 perm_size
= pack_set_bytecount(perm
->pl
);
477 if (!min_perm_size
|| min_perm_size
> perm_size
) {
478 min_perm_size
= perm_size
;
484 /* add the unique packs to the list */
487 pack_list_insert(min
, pl
);
492 static void load_all_objects(void)
494 struct pack_list
*pl
= local_packs
;
495 struct llist_item
*hint
, *l
;
497 llist_init(&all_objects
);
501 l
= pl
->all_objects
->front
;
503 hint
= llist_insert_sorted_unique(all_objects
,
509 /* remove objects present in remote packs */
512 llist_sorted_difference_inplace(all_objects
, pl
->all_objects
);
517 /* this scales like O(n^2) */
518 static void cmp_local_packs(void)
520 struct pack_list
*subset
, *pl
= local_packs
;
522 while ((subset
= pl
)) {
523 while ((subset
= subset
->next
))
524 cmp_two_packs(pl
, subset
);
529 static void scan_alt_odb_packs(void)
531 struct pack_list
*local
, *alt
;
537 llist_sorted_difference_inplace(local
->unique_objects
,
541 llist_sorted_difference_inplace(all_objects
, alt
->all_objects
);
546 static struct pack_list
* add_pack(struct packed_git
*p
)
549 unsigned long off
= 0, step
;
550 const unsigned char *base
;
552 if (!p
->pack_local
&& !(alt_odb
|| verbose
))
556 llist_init(&l
.all_objects
);
558 if (open_pack_index(p
))
561 base
= p
->index_data
;
562 base
+= 256 * 4 + ((p
->index_version
< 2) ? 4 : 8);
563 step
= the_hash_algo
->rawsz
+ ((p
->index_version
< 2) ? 4 : 0);
564 while (off
< p
->num_objects
* step
) {
565 llist_insert_back(l
.all_objects
, base
+ off
);
568 /* this list will be pruned in cmp_two_packs later */
569 l
.unique_objects
= llist_copy(l
.all_objects
);
571 return pack_list_insert(&local_packs
, &l
);
573 return pack_list_insert(&altodb_packs
, &l
);
576 static struct pack_list
* add_pack_file(const char *filename
)
578 struct packed_git
*p
= get_packed_git(the_repository
);
580 if (strlen(filename
) < 40)
581 die("Bad pack filename: %s", filename
);
584 if (strstr(p
->pack_name
, filename
))
588 die("Filename %s not found in packed_git", filename
);
591 static void load_all(void)
593 struct packed_git
*p
= get_packed_git(the_repository
);
601 int cmd_pack_redundant(int argc
, const char **argv
, const char *prefix
)
604 struct pack_list
*min
, *red
, *pl
;
605 struct llist
*ignore
;
607 char buf
[42]; /* 40 byte sha1 + \n + \0 */
609 if (argc
== 2 && !strcmp(argv
[1], "-h"))
610 usage(pack_redundant_usage
);
612 for (i
= 1; i
< argc
; i
++) {
613 const char *arg
= argv
[i
];
614 if (!strcmp(arg
, "--")) {
618 if (!strcmp(arg
, "--all")) {
622 if (!strcmp(arg
, "--verbose")) {
626 if (!strcmp(arg
, "--alt-odb")) {
631 usage(pack_redundant_usage
);
639 while (*(argv
+ i
) != NULL
)
640 add_pack_file(*(argv
+ i
++));
642 if (local_packs
== NULL
)
643 die("Zero packs found!");
649 scan_alt_odb_packs();
651 /* ignore objects given on stdin */
654 while (fgets(buf
, sizeof(buf
), stdin
)) {
656 if (get_sha1_hex(buf
, sha1
))
657 die("Bad sha1 on stdin: %s", buf
);
658 llist_insert_sorted_unique(ignore
, sha1
, NULL
);
661 llist_sorted_difference_inplace(all_objects
, ignore
);
664 llist_sorted_difference_inplace(pl
->unique_objects
, ignore
);
671 fprintf(stderr
, "There are %lu packs available in alt-odbs.\n",
672 (unsigned long)pack_list_size(altodb_packs
));
673 fprintf(stderr
, "The smallest (bytewise) set of packs is:\n");
676 fprintf(stderr
, "\t%s\n", pl
->pack
->pack_name
);
679 fprintf(stderr
, "containing %lu duplicate objects "
680 "with a total size of %lukb.\n",
681 (unsigned long)get_pack_redundancy(min
),
682 (unsigned long)pack_set_bytecount(min
)/1024);
683 fprintf(stderr
, "A total of %lu unique objects were considered.\n",
684 (unsigned long)all_objects
->size
);
685 fprintf(stderr
, "Redundant packs (with indexes):\n");
687 pl
= red
= pack_list_difference(local_packs
, min
);
690 sha1_pack_index_name(pl
->pack
->sha1
),
691 pl
->pack
->pack_name
);
695 fprintf(stderr
, "%luMB of redundant packs in total.\n",
696 (unsigned long)pack_set_bytecount(red
)/(1024*1024));