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 struct object_id
*oid
;
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
->oid
= list
->front
->oid
;
95 old_item
= list
->front
->next
;
98 new_item
= llist_item_get();
99 prev
->next
= new_item
;
100 new_item
->oid
= old_item
->oid
;
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 struct object_id
*oid
)
113 struct llist_item
*new_item
= llist_item_get();
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 struct object_id
*oid
)
136 return llist_insert(list
, list
->back
, oid
);
139 static inline struct llist_item
*llist_insert_sorted_unique(struct llist
*list
,
140 const struct object_id
*oid
, struct llist_item
*hint
)
142 struct llist_item
*prev
= NULL
, *l
;
144 l
= (hint
== NULL
) ? list
->front
: hint
;
146 int cmp
= oidcmp(l
->oid
, oid
);
147 if (cmp
> 0) { /* we insert before this entry */
148 return llist_insert(list
, prev
, oid
);
150 if (!cmp
) { /* already exists */
156 /* insert at the end */
157 return llist_insert_back(list
, oid
);
160 /* returns a pointer to an item in front of sha1 */
161 static inline struct llist_item
* llist_sorted_remove(struct llist
*list
, const struct object_id
*oid
, struct llist_item
*hint
)
163 struct llist_item
*prev
, *l
;
166 l
= (hint
== NULL
) ? list
->front
: hint
;
169 int cmp
= oidcmp(l
->oid
, oid
);
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
->oid
, 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 if (!p1
->unique_objects
)
258 p1
->unique_objects
= llist_copy(p1
->all_objects
);
259 if (!p2
->unique_objects
)
260 p2
->unique_objects
= llist_copy(p2
->all_objects
);
262 p1_base
= p1
->pack
->index_data
;
263 p2_base
= p2
->pack
->index_data
;
264 p1_base
+= 256 * 4 + ((p1
->pack
->index_version
< 2) ? 4 : 8);
265 p2_base
+= 256 * 4 + ((p2
->pack
->index_version
< 2) ? 4 : 8);
266 p1_step
= hashsz
+ ((p1
->pack
->index_version
< 2) ? 4 : 0);
267 p2_step
= hashsz
+ ((p2
->pack
->index_version
< 2) ? 4 : 0);
269 while (p1_off
< p1
->pack
->num_objects
* p1_step
&&
270 p2_off
< p2
->pack
->num_objects
* p2_step
)
272 int cmp
= hashcmp(p1_base
+ p1_off
, p2_base
+ p2_off
);
275 p1_hint
= llist_sorted_remove(p1
->unique_objects
,
276 (const struct object_id
*)(p1_base
+ p1_off
),
278 p2_hint
= llist_sorted_remove(p2
->unique_objects
,
279 (const struct object_id
*)(p1_base
+ p1_off
),
285 if (cmp
< 0) { /* p1 has the object, p2 doesn't */
287 } else { /* p2 has the object, p1 doesn't */
293 static void pll_free(struct pll
*l
)
296 struct pack_list
*opl
;
310 /* all the permutations have to be free()d at the same time,
311 * since they refer to each other
313 static struct pll
* get_permutations(struct pack_list
*list
, int n
)
315 struct pll
*subset
, *ret
= NULL
, *new_pll
= NULL
;
317 if (list
== NULL
|| pack_list_size(list
) < n
|| n
== 0)
322 new_pll
= xmalloc(sizeof(*new_pll
));
324 pack_list_insert(&new_pll
->pl
, list
);
333 subset
= get_permutations(list
->next
, n
- 1);
335 new_pll
= xmalloc(sizeof(*new_pll
));
336 new_pll
->pl
= subset
->pl
;
337 pack_list_insert(&new_pll
->pl
, list
);
340 subset
= subset
->next
;
347 static int is_superset(struct pack_list
*pl
, struct llist
*list
)
351 diff
= llist_copy(list
);
354 llist_sorted_difference_inplace(diff
, pl
->all_objects
);
355 if (diff
->size
== 0) { /* we're done */
365 static size_t sizeof_union(struct packed_git
*p1
, struct packed_git
*p2
)
368 unsigned long p1_off
= 0, p2_off
= 0, p1_step
, p2_step
;
369 const unsigned char *p1_base
, *p2_base
;
370 const unsigned int hashsz
= the_hash_algo
->rawsz
;
372 p1_base
= p1
->index_data
;
373 p2_base
= p2
->index_data
;
374 p1_base
+= 256 * 4 + ((p1
->index_version
< 2) ? 4 : 8);
375 p2_base
+= 256 * 4 + ((p2
->index_version
< 2) ? 4 : 8);
376 p1_step
= hashsz
+ ((p1
->index_version
< 2) ? 4 : 0);
377 p2_step
= hashsz
+ ((p2
->index_version
< 2) ? 4 : 0);
379 while (p1_off
< p1
->num_objects
* p1_step
&&
380 p2_off
< p2
->num_objects
* p2_step
)
382 int cmp
= hashcmp(p1_base
+ p1_off
, p2_base
+ p2_off
);
390 if (cmp
< 0) { /* p1 has the object, p2 doesn't */
392 } else { /* p2 has the object, p1 doesn't */
399 /* another O(n^2) function ... */
400 static size_t get_pack_redundancy(struct pack_list
*pl
)
402 struct pack_list
*subset
;
408 while ((subset
= pl
->next
)) {
410 ret
+= sizeof_union(pl
->pack
, subset
->pack
);
411 subset
= subset
->next
;
418 static inline off_t
pack_set_bytecount(struct pack_list
*pl
)
422 ret
+= pl
->pack
->pack_size
;
423 ret
+= pl
->pack
->index_size
;
429 static void minimize(struct pack_list
**min
)
431 struct pack_list
*pl
, *unique
= NULL
,
432 *non_unique
= NULL
, *min_perm
= NULL
;
433 struct pll
*perm
, *perm_all
, *perm_ok
= NULL
, *new_perm
;
434 struct llist
*missing
;
435 off_t min_perm_size
= 0, perm_size
;
440 if (pl
->unique_objects
->size
)
441 pack_list_insert(&unique
, pl
);
443 pack_list_insert(&non_unique
, pl
);
446 /* find out which objects are missing from the set of unique packs */
447 missing
= llist_copy(all_objects
);
450 llist_sorted_difference_inplace(missing
, pl
->all_objects
);
454 /* return if there are no objects missing from the unique set */
455 if (missing
->size
== 0) {
461 /* find the permutations which contain all missing objects */
462 for (n
= 1; n
<= pack_list_size(non_unique
) && !perm_ok
; n
++) {
463 perm_all
= perm
= get_permutations(non_unique
, n
);
465 if (is_superset(perm
->pl
, missing
)) {
466 new_perm
= xmalloc(sizeof(struct pll
));
467 memcpy(new_perm
, perm
, sizeof(struct pll
));
468 new_perm
->next
= perm_ok
;
478 die("Internal error: No complete sets found!");
480 /* find the permutation with the smallest size */
483 perm_size
= pack_set_bytecount(perm
->pl
);
484 if (!min_perm_size
|| min_perm_size
> perm_size
) {
485 min_perm_size
= perm_size
;
491 /* add the unique packs to the list */
494 pack_list_insert(min
, pl
);
499 static void load_all_objects(void)
501 struct pack_list
*pl
= local_packs
;
502 struct llist_item
*hint
, *l
;
504 llist_init(&all_objects
);
508 l
= pl
->all_objects
->front
;
510 hint
= llist_insert_sorted_unique(all_objects
,
516 /* remove objects present in remote packs */
519 llist_sorted_difference_inplace(all_objects
, pl
->all_objects
);
524 /* this scales like O(n^2) */
525 static void cmp_local_packs(void)
527 struct pack_list
*subset
, *pl
= local_packs
;
529 while ((subset
= pl
)) {
530 while ((subset
= subset
->next
))
531 cmp_two_packs(pl
, subset
);
536 static void scan_alt_odb_packs(void)
538 struct pack_list
*local
, *alt
;
544 llist_sorted_difference_inplace(local
->all_objects
,
548 llist_sorted_difference_inplace(all_objects
, alt
->all_objects
);
553 static struct pack_list
* add_pack(struct packed_git
*p
)
556 unsigned long off
= 0, step
;
557 const unsigned char *base
;
559 if (!p
->pack_local
&& !(alt_odb
|| verbose
))
563 llist_init(&l
.all_objects
);
565 if (open_pack_index(p
))
568 base
= p
->index_data
;
569 base
+= 256 * 4 + ((p
->index_version
< 2) ? 4 : 8);
570 step
= the_hash_algo
->rawsz
+ ((p
->index_version
< 2) ? 4 : 0);
571 while (off
< p
->num_objects
* step
) {
572 llist_insert_back(l
.all_objects
, (const struct object_id
*)(base
+ off
));
575 l
.unique_objects
= NULL
;
577 return pack_list_insert(&local_packs
, &l
);
579 return pack_list_insert(&altodb_packs
, &l
);
582 static struct pack_list
* add_pack_file(const char *filename
)
584 struct packed_git
*p
= get_all_packs(the_repository
);
586 if (strlen(filename
) < 40)
587 die("Bad pack filename: %s", filename
);
590 if (strstr(p
->pack_name
, filename
))
594 die("Filename %s not found in packed_git", filename
);
597 static void load_all(void)
599 struct packed_git
*p
= get_all_packs(the_repository
);
607 int cmd_pack_redundant(int argc
, const char **argv
, const char *prefix
)
610 struct pack_list
*min
, *red
, *pl
;
611 struct llist
*ignore
;
612 struct object_id
*oid
;
613 char buf
[GIT_MAX_HEXSZ
+ 2]; /* hex hash + \n + \0 */
615 if (argc
== 2 && !strcmp(argv
[1], "-h"))
616 usage(pack_redundant_usage
);
618 for (i
= 1; i
< argc
; i
++) {
619 const char *arg
= argv
[i
];
620 if (!strcmp(arg
, "--")) {
624 if (!strcmp(arg
, "--all")) {
628 if (!strcmp(arg
, "--verbose")) {
632 if (!strcmp(arg
, "--alt-odb")) {
637 usage(pack_redundant_usage
);
645 while (*(argv
+ i
) != NULL
)
646 add_pack_file(*(argv
+ i
++));
648 if (local_packs
== NULL
)
649 die("Zero packs found!");
654 scan_alt_odb_packs();
656 /* ignore objects given on stdin */
659 while (fgets(buf
, sizeof(buf
), stdin
)) {
660 oid
= xmalloc(sizeof(*oid
));
661 if (get_oid_hex(buf
, oid
))
662 die("Bad object ID on stdin: %s", buf
);
663 llist_insert_sorted_unique(ignore
, oid
, NULL
);
666 llist_sorted_difference_inplace(all_objects
, ignore
);
669 llist_sorted_difference_inplace(pl
->all_objects
, ignore
);
678 fprintf(stderr
, "There are %lu packs available in alt-odbs.\n",
679 (unsigned long)pack_list_size(altodb_packs
));
680 fprintf(stderr
, "The smallest (bytewise) set of packs is:\n");
683 fprintf(stderr
, "\t%s\n", pl
->pack
->pack_name
);
686 fprintf(stderr
, "containing %lu duplicate objects "
687 "with a total size of %lukb.\n",
688 (unsigned long)get_pack_redundancy(min
),
689 (unsigned long)pack_set_bytecount(min
)/1024);
690 fprintf(stderr
, "A total of %lu unique objects were considered.\n",
691 (unsigned long)all_objects
->size
);
692 fprintf(stderr
, "Redundant packs (with indexes):\n");
694 pl
= red
= pack_list_difference(local_packs
, min
);
697 sha1_pack_index_name(pl
->pack
->sha1
),
698 pl
->pack
->pack_name
);
702 fprintf(stderr
, "%luMB of redundant packs in total.\n",
703 (unsigned long)pack_set_bytecount(red
)/(1024*1024));