3 * Copyright 2005, Lukas Sandstrom <lukass@etek.chalmers.se>
5 * This file is licensed under the GPL v2.
8 #define USE_THE_REPOSITORY_VARIABLE
15 #include "object-store-ll.h"
19 static const char pack_redundant_usage
[] =
20 "git pack-redundant [--verbose] [--alt-odb] (--all | <pack-filename>...)";
22 static int load_all_packs
, verbose
, alt_odb
;
25 struct llist_item
*next
;
29 struct llist_item
*front
;
30 struct llist_item
*back
;
32 } *all_objects
; /* all objects which must be present in local packfiles */
34 static struct pack_list
{
35 struct pack_list
*next
;
36 struct packed_git
*pack
;
37 struct llist
*unique_objects
;
38 struct llist
*remaining_objects
;
39 size_t all_objects_size
;
40 } *local_packs
= NULL
, *altodb_packs
= NULL
;
42 static struct llist_item
*free_nodes
;
44 static inline void llist_item_put(struct llist_item
*item
)
46 item
->next
= free_nodes
;
50 static inline struct llist_item
*llist_item_get(void)
52 struct llist_item
*new_item
;
54 new_item
= free_nodes
;
55 free_nodes
= free_nodes
->next
;
58 ALLOC_ARRAY(new_item
, BLKSIZE
);
59 for (; i
< BLKSIZE
; i
++)
60 llist_item_put(&new_item
[i
]);
65 static inline void llist_init(struct llist
**list
)
67 *list
= xmalloc(sizeof(struct llist
));
68 (*list
)->front
= (*list
)->back
= NULL
;
72 static struct llist
* llist_copy(struct llist
*list
)
75 struct llist_item
*new_item
, *old_item
, *prev
;
79 if ((ret
->size
= list
->size
) == 0)
82 new_item
= ret
->front
= llist_item_get();
83 new_item
->oid
= list
->front
->oid
;
85 old_item
= list
->front
->next
;
88 new_item
= llist_item_get();
89 prev
->next
= new_item
;
90 new_item
->oid
= old_item
->oid
;
91 old_item
= old_item
->next
;
93 new_item
->next
= NULL
;
99 static inline struct llist_item
*llist_insert(struct llist
*list
,
100 struct llist_item
*after
,
101 const unsigned char *oid
)
103 struct llist_item
*new_item
= llist_item_get();
104 oidread(&new_item
->oid
, oid
, the_repository
->hash_algo
);
105 new_item
->next
= NULL
;
108 new_item
->next
= after
->next
;
109 after
->next
= new_item
;
110 if (after
== list
->back
)
111 list
->back
= new_item
;
112 } else {/* insert in front */
114 list
->back
= new_item
;
116 new_item
->next
= list
->front
;
117 list
->front
= new_item
;
123 static inline struct llist_item
*llist_insert_back(struct llist
*list
,
124 const unsigned char *oid
)
126 return llist_insert(list
, list
->back
, oid
);
129 static inline struct llist_item
*llist_insert_sorted_unique(struct llist
*list
,
130 const struct object_id
*oid
, struct llist_item
*hint
)
132 struct llist_item
*prev
= NULL
, *l
;
134 l
= (hint
== NULL
) ? list
->front
: hint
;
136 int cmp
= oidcmp(&l
->oid
, oid
);
137 if (cmp
> 0) { /* we insert before this entry */
138 return llist_insert(list
, prev
, oid
->hash
);
140 if (!cmp
) { /* already exists */
146 /* insert at the end */
147 return llist_insert_back(list
, oid
->hash
);
150 /* returns a pointer to an item in front of sha1 */
151 static inline struct llist_item
* llist_sorted_remove(struct llist
*list
, const unsigned char *oid
, struct llist_item
*hint
)
153 struct llist_item
*prev
, *l
;
156 l
= (hint
== NULL
) ? list
->front
: hint
;
159 const int cmp
= hashcmp(l
->oid
.hash
, oid
, the_repository
->hash_algo
);
160 if (cmp
> 0) /* not in list, since sorted */
162 if (!cmp
) { /* found */
164 if (hint
!= NULL
&& hint
!= list
->front
) {
165 /* we don't know the previous element */
167 goto redo_from_start
;
169 list
->front
= l
->next
;
171 prev
->next
= l
->next
;
185 static void llist_sorted_difference_inplace(struct llist
*A
,
188 struct llist_item
*hint
, *b
;
194 hint
= llist_sorted_remove(A
, b
->oid
.hash
, hint
);
199 static inline struct pack_list
* pack_list_insert(struct pack_list
**pl
,
200 struct pack_list
*entry
)
202 struct pack_list
*p
= xmalloc(sizeof(struct pack_list
));
203 memcpy(p
, entry
, sizeof(struct pack_list
));
209 static inline size_t pack_list_size(struct pack_list
*pl
)
219 static struct pack_list
* pack_list_difference(const struct pack_list
*A
,
220 const struct pack_list
*B
)
222 struct pack_list
*ret
;
223 const struct pack_list
*pl
;
230 if (A
->pack
== pl
->pack
)
231 return pack_list_difference(A
->next
, B
);
234 ret
= xmalloc(sizeof(struct pack_list
));
235 memcpy(ret
, A
, sizeof(struct pack_list
));
236 ret
->next
= pack_list_difference(A
->next
, B
);
240 static void cmp_two_packs(struct pack_list
*p1
, struct pack_list
*p2
)
242 size_t p1_off
= 0, p2_off
= 0, p1_step
, p2_step
;
243 const unsigned char *p1_base
, *p2_base
;
244 struct llist_item
*p1_hint
= NULL
, *p2_hint
= NULL
;
245 const unsigned int hashsz
= the_hash_algo
->rawsz
;
247 if (!p1
->unique_objects
)
248 p1
->unique_objects
= llist_copy(p1
->remaining_objects
);
249 if (!p2
->unique_objects
)
250 p2
->unique_objects
= llist_copy(p2
->remaining_objects
);
252 p1_base
= p1
->pack
->index_data
;
253 p2_base
= p2
->pack
->index_data
;
254 p1_base
+= 256 * 4 + ((p1
->pack
->index_version
< 2) ? 4 : 8);
255 p2_base
+= 256 * 4 + ((p2
->pack
->index_version
< 2) ? 4 : 8);
256 p1_step
= hashsz
+ ((p1
->pack
->index_version
< 2) ? 4 : 0);
257 p2_step
= hashsz
+ ((p2
->pack
->index_version
< 2) ? 4 : 0);
259 while (p1_off
< p1
->pack
->num_objects
* p1_step
&&
260 p2_off
< p2
->pack
->num_objects
* p2_step
)
262 const int cmp
= hashcmp(p1_base
+ p1_off
, p2_base
+ p2_off
,
263 the_repository
->hash_algo
);
266 p1_hint
= llist_sorted_remove(p1
->unique_objects
,
269 p2_hint
= llist_sorted_remove(p2
->unique_objects
,
276 if (cmp
< 0) { /* p1 has the object, p2 doesn't */
278 } else { /* p2 has the object, p1 doesn't */
284 static size_t sizeof_union(struct packed_git
*p1
, struct packed_git
*p2
)
287 size_t p1_off
= 0, p2_off
= 0, p1_step
, p2_step
;
288 const unsigned char *p1_base
, *p2_base
;
289 const unsigned int hashsz
= the_hash_algo
->rawsz
;
291 p1_base
= p1
->index_data
;
292 p2_base
= p2
->index_data
;
293 p1_base
+= 256 * 4 + ((p1
->index_version
< 2) ? 4 : 8);
294 p2_base
+= 256 * 4 + ((p2
->index_version
< 2) ? 4 : 8);
295 p1_step
= hashsz
+ ((p1
->index_version
< 2) ? 4 : 0);
296 p2_step
= hashsz
+ ((p2
->index_version
< 2) ? 4 : 0);
298 while (p1_off
< p1
->num_objects
* p1_step
&&
299 p2_off
< p2
->num_objects
* p2_step
)
301 int cmp
= hashcmp(p1_base
+ p1_off
, p2_base
+ p2_off
,
302 the_repository
->hash_algo
);
310 if (cmp
< 0) { /* p1 has the object, p2 doesn't */
312 } else { /* p2 has the object, p1 doesn't */
319 /* another O(n^2) function ... */
320 static size_t get_pack_redundancy(struct pack_list
*pl
)
322 struct pack_list
*subset
;
328 while ((subset
= pl
->next
)) {
330 ret
+= sizeof_union(pl
->pack
, subset
->pack
);
331 subset
= subset
->next
;
338 static inline off_t
pack_set_bytecount(struct pack_list
*pl
)
342 ret
+= pl
->pack
->pack_size
;
343 ret
+= pl
->pack
->index_size
;
349 static int cmp_remaining_objects(const void *a
, const void *b
)
351 struct pack_list
*pl_a
= *((struct pack_list
**)a
);
352 struct pack_list
*pl_b
= *((struct pack_list
**)b
);
354 if (pl_a
->remaining_objects
->size
== pl_b
->remaining_objects
->size
) {
355 /* have the same remaining_objects, big pack first */
356 if (pl_a
->all_objects_size
== pl_b
->all_objects_size
)
358 else if (pl_a
->all_objects_size
< pl_b
->all_objects_size
)
362 } else if (pl_a
->remaining_objects
->size
< pl_b
->remaining_objects
->size
) {
363 /* sort by remaining objects, more objects first */
370 /* Sort pack_list, greater size of remaining_objects first */
371 static void sort_pack_list(struct pack_list
**pl
)
373 struct pack_list
**ary
, *p
;
375 size_t n
= pack_list_size(*pl
);
380 /* prepare an array of packed_list for easier sorting */
381 CALLOC_ARRAY(ary
, n
);
382 for (n
= 0, p
= *pl
; p
; p
= p
->next
)
385 QSORT(ary
, n
, cmp_remaining_objects
);
387 /* link them back again */
388 for (i
= 0; i
< n
- 1; i
++)
389 ary
[i
]->next
= ary
[i
+ 1];
390 ary
[n
- 1]->next
= NULL
;
397 static void minimize(struct pack_list
**min
)
399 struct pack_list
*pl
, *unique
= NULL
, *non_unique
= NULL
;
400 struct llist
*missing
, *unique_pack_objects
;
404 if (pl
->unique_objects
->size
)
405 pack_list_insert(&unique
, pl
);
407 pack_list_insert(&non_unique
, pl
);
410 /* find out which objects are missing from the set of unique packs */
411 missing
= llist_copy(all_objects
);
414 llist_sorted_difference_inplace(missing
, pl
->remaining_objects
);
420 /* return if there are no objects missing from the unique set */
421 if (missing
->size
== 0) {
426 unique_pack_objects
= llist_copy(all_objects
);
427 llist_sorted_difference_inplace(unique_pack_objects
, missing
);
429 /* remove unique pack objects from the non_unique packs */
432 llist_sorted_difference_inplace(pl
->remaining_objects
, unique_pack_objects
);
437 /* sort the non_unique packs, greater size of remaining_objects first */
438 sort_pack_list(&non_unique
);
439 if (non_unique
->remaining_objects
->size
== 0)
442 pack_list_insert(min
, non_unique
);
444 for (pl
= non_unique
->next
; pl
&& pl
->remaining_objects
->size
> 0; pl
= pl
->next
)
445 llist_sorted_difference_inplace(pl
->remaining_objects
, non_unique
->remaining_objects
);
447 non_unique
= non_unique
->next
;
451 static void load_all_objects(void)
453 struct pack_list
*pl
= local_packs
;
454 struct llist_item
*hint
, *l
;
456 llist_init(&all_objects
);
460 l
= pl
->remaining_objects
->front
;
462 hint
= llist_insert_sorted_unique(all_objects
,
468 /* remove objects present in remote packs */
471 llist_sorted_difference_inplace(all_objects
, pl
->remaining_objects
);
476 /* this scales like O(n^2) */
477 static void cmp_local_packs(void)
479 struct pack_list
*subset
, *pl
= local_packs
;
481 /* only one packfile */
483 llist_init(&pl
->unique_objects
);
487 while ((subset
= pl
)) {
488 while ((subset
= subset
->next
))
489 cmp_two_packs(pl
, subset
);
494 static void scan_alt_odb_packs(void)
496 struct pack_list
*local
, *alt
;
502 llist_sorted_difference_inplace(local
->remaining_objects
,
503 alt
->remaining_objects
);
510 static struct pack_list
* add_pack(struct packed_git
*p
)
513 size_t off
= 0, step
;
514 const unsigned char *base
;
516 if (!p
->pack_local
&& !(alt_odb
|| verbose
))
520 llist_init(&l
.remaining_objects
);
522 if (open_pack_index(p
))
525 base
= p
->index_data
;
526 base
+= 256 * 4 + ((p
->index_version
< 2) ? 4 : 8);
527 step
= the_hash_algo
->rawsz
+ ((p
->index_version
< 2) ? 4 : 0);
528 while (off
< p
->num_objects
* step
) {
529 llist_insert_back(l
.remaining_objects
, base
+ off
);
532 l
.all_objects_size
= l
.remaining_objects
->size
;
533 l
.unique_objects
= NULL
;
535 return pack_list_insert(&local_packs
, &l
);
537 return pack_list_insert(&altodb_packs
, &l
);
540 static struct pack_list
* add_pack_file(const char *filename
)
542 struct packed_git
*p
= get_all_packs(the_repository
);
544 if (strlen(filename
) < 40)
545 die("Bad pack filename: %s", filename
);
548 if (strstr(p
->pack_name
, filename
))
552 die("Filename %s not found in packed_git", filename
);
555 static void load_all(void)
557 struct packed_git
*p
= get_all_packs(the_repository
);
565 int cmd_pack_redundant(int argc
, const char **argv
, const char *prefix UNUSED
, struct repository
*repo UNUSED
) {
566 int i
; int i_still_use_this
= 0; struct pack_list
*min
= NULL
, *red
, *pl
;
567 struct llist
*ignore
;
568 struct object_id
*oid
;
569 char buf
[GIT_MAX_HEXSZ
+ 2]; /* hex hash + \n + \0 */
571 if (argc
== 2 && !strcmp(argv
[1], "-h"))
572 usage(pack_redundant_usage
);
574 for (i
= 1; i
< argc
; i
++) {
575 const char *arg
= argv
[i
];
576 if (!strcmp(arg
, "--")) {
580 if (!strcmp(arg
, "--all")) {
584 if (!strcmp(arg
, "--verbose")) {
588 if (!strcmp(arg
, "--alt-odb")) {
592 if (!strcmp(arg
, "--i-still-use-this")) {
593 i_still_use_this
= 1;
597 usage(pack_redundant_usage
);
602 if (!i_still_use_this
) {
603 fputs(_("'git pack-redundant' is nominated for removal.\n"
604 "If you still use this command, please add an extra\n"
605 "option, '--i-still-use-this', on the command line\n"
606 "and let us know you still use it by sending an e-mail\n"
607 "to <git@vger.kernel.org>. Thanks.\n"), stderr
);
608 die(_("refusing to run without --i-still-use-this"));
614 while (*(argv
+ i
) != NULL
)
615 add_pack_file(*(argv
+ i
++));
618 die("Zero packs found!");
623 scan_alt_odb_packs();
625 /* ignore objects given on stdin */
628 while (fgets(buf
, sizeof(buf
), stdin
)) {
629 oid
= xmalloc(sizeof(*oid
));
630 if (get_oid_hex(buf
, oid
))
631 die("Bad object ID on stdin: %s", buf
);
632 llist_insert_sorted_unique(ignore
, oid
, NULL
);
635 llist_sorted_difference_inplace(all_objects
, ignore
);
638 llist_sorted_difference_inplace(pl
->remaining_objects
, ignore
);
647 fprintf(stderr
, "There are %lu packs available in alt-odbs.\n",
648 (unsigned long)pack_list_size(altodb_packs
));
649 fprintf(stderr
, "The smallest (bytewise) set of packs is:\n");
652 fprintf(stderr
, "\t%s\n", pl
->pack
->pack_name
);
655 fprintf(stderr
, "containing %lu duplicate objects "
656 "with a total size of %lukb.\n",
657 (unsigned long)get_pack_redundancy(min
),
658 (unsigned long)pack_set_bytecount(min
)/1024);
659 fprintf(stderr
, "A total of %lu unique objects were considered.\n",
660 (unsigned long)all_objects
->size
);
661 fprintf(stderr
, "Redundant packs (with indexes):\n");
663 pl
= red
= pack_list_difference(local_packs
, min
);
666 sha1_pack_index_name(pl
->pack
->hash
),
667 pl
->pack
->pack_name
);
671 fprintf(stderr
, "%luMB of redundant packs in total.\n",
672 (unsigned long)pack_set_bytecount(red
)/(1024*1024));