]>
git.ipfire.org Git - thirdparty/git.git/blob - builtin/pack-redundant.c
3 * Copyright 2005, Lukas Sandstrom <lukass@etek.chalmers.se>
5 * This file is licensed under the GPL v2.
11 #include "repository.h"
13 #include "object-store.h"
17 static const char pack_redundant_usage
[] =
18 "git pack-redundant [--verbose] [--alt-odb] (--all | <pack-filename>...)";
20 static int load_all_packs
, verbose
, alt_odb
;
23 struct llist_item
*next
;
27 struct llist_item
*front
;
28 struct llist_item
*back
;
30 } *all_objects
; /* all objects which must be present in local packfiles */
32 static struct pack_list
{
33 struct pack_list
*next
;
34 struct packed_git
*pack
;
35 struct llist
*unique_objects
;
36 struct llist
*remaining_objects
;
37 size_t all_objects_size
;
38 } *local_packs
= NULL
, *altodb_packs
= NULL
;
40 static struct llist_item
*free_nodes
;
42 static inline void llist_item_put(struct llist_item
*item
)
44 item
->next
= free_nodes
;
48 static inline struct llist_item
*llist_item_get(void)
50 struct llist_item
*new_item
;
52 new_item
= free_nodes
;
53 free_nodes
= free_nodes
->next
;
56 ALLOC_ARRAY(new_item
, BLKSIZE
);
57 for (; i
< BLKSIZE
; i
++)
58 llist_item_put(&new_item
[i
]);
63 static inline void llist_init(struct llist
**list
)
65 *list
= xmalloc(sizeof(struct llist
));
66 (*list
)->front
= (*list
)->back
= NULL
;
70 static struct llist
* llist_copy(struct llist
*list
)
73 struct llist_item
*new_item
, *old_item
, *prev
;
77 if ((ret
->size
= list
->size
) == 0)
80 new_item
= ret
->front
= llist_item_get();
81 new_item
->oid
= list
->front
->oid
;
83 old_item
= list
->front
->next
;
86 new_item
= llist_item_get();
87 prev
->next
= new_item
;
88 new_item
->oid
= old_item
->oid
;
89 old_item
= old_item
->next
;
91 new_item
->next
= NULL
;
97 static inline struct llist_item
*llist_insert(struct llist
*list
,
98 struct llist_item
*after
,
99 const unsigned char *oid
)
101 struct llist_item
*new_item
= llist_item_get();
102 oidread(&new_item
->oid
, oid
);
103 new_item
->next
= NULL
;
106 new_item
->next
= after
->next
;
107 after
->next
= new_item
;
108 if (after
== list
->back
)
109 list
->back
= new_item
;
110 } else {/* insert in front */
112 list
->back
= new_item
;
114 new_item
->next
= list
->front
;
115 list
->front
= new_item
;
121 static inline struct llist_item
*llist_insert_back(struct llist
*list
,
122 const unsigned char *oid
)
124 return llist_insert(list
, list
->back
, oid
);
127 static inline struct llist_item
*llist_insert_sorted_unique(struct llist
*list
,
128 const struct object_id
*oid
, struct llist_item
*hint
)
130 struct llist_item
*prev
= NULL
, *l
;
132 l
= (hint
== NULL
) ? list
->front
: hint
;
134 int cmp
= oidcmp(&l
->oid
, oid
);
135 if (cmp
> 0) { /* we insert before this entry */
136 return llist_insert(list
, prev
, oid
->hash
);
138 if (!cmp
) { /* already exists */
144 /* insert at the end */
145 return llist_insert_back(list
, oid
->hash
);
148 /* returns a pointer to an item in front of sha1 */
149 static inline struct llist_item
* llist_sorted_remove(struct llist
*list
, const unsigned char *oid
, struct llist_item
*hint
)
151 struct llist_item
*prev
, *l
;
154 l
= (hint
== NULL
) ? list
->front
: hint
;
157 const int cmp
= hashcmp(l
->oid
.hash
, oid
);
158 if (cmp
> 0) /* not in list, since sorted */
160 if (!cmp
) { /* found */
162 if (hint
!= NULL
&& hint
!= list
->front
) {
163 /* we don't know the previous element */
165 goto redo_from_start
;
167 list
->front
= l
->next
;
169 prev
->next
= l
->next
;
183 static void llist_sorted_difference_inplace(struct llist
*A
,
186 struct llist_item
*hint
, *b
;
192 hint
= llist_sorted_remove(A
, b
->oid
.hash
, hint
);
197 static inline struct pack_list
* pack_list_insert(struct pack_list
**pl
,
198 struct pack_list
*entry
)
200 struct pack_list
*p
= xmalloc(sizeof(struct pack_list
));
201 memcpy(p
, entry
, sizeof(struct pack_list
));
207 static inline size_t pack_list_size(struct pack_list
*pl
)
217 static struct pack_list
* pack_list_difference(const struct pack_list
*A
,
218 const struct pack_list
*B
)
220 struct pack_list
*ret
;
221 const struct pack_list
*pl
;
228 if (A
->pack
== pl
->pack
)
229 return pack_list_difference(A
->next
, B
);
232 ret
= xmalloc(sizeof(struct pack_list
));
233 memcpy(ret
, A
, sizeof(struct pack_list
));
234 ret
->next
= pack_list_difference(A
->next
, B
);
238 static void cmp_two_packs(struct pack_list
*p1
, struct pack_list
*p2
)
240 size_t p1_off
= 0, p2_off
= 0, p1_step
, p2_step
;
241 const unsigned char *p1_base
, *p2_base
;
242 struct llist_item
*p1_hint
= NULL
, *p2_hint
= NULL
;
243 const unsigned int hashsz
= the_hash_algo
->rawsz
;
245 if (!p1
->unique_objects
)
246 p1
->unique_objects
= llist_copy(p1
->remaining_objects
);
247 if (!p2
->unique_objects
)
248 p2
->unique_objects
= llist_copy(p2
->remaining_objects
);
250 p1_base
= p1
->pack
->index_data
;
251 p2_base
= p2
->pack
->index_data
;
252 p1_base
+= 256 * 4 + ((p1
->pack
->index_version
< 2) ? 4 : 8);
253 p2_base
+= 256 * 4 + ((p2
->pack
->index_version
< 2) ? 4 : 8);
254 p1_step
= hashsz
+ ((p1
->pack
->index_version
< 2) ? 4 : 0);
255 p2_step
= hashsz
+ ((p2
->pack
->index_version
< 2) ? 4 : 0);
257 while (p1_off
< p1
->pack
->num_objects
* p1_step
&&
258 p2_off
< p2
->pack
->num_objects
* p2_step
)
260 const int cmp
= hashcmp(p1_base
+ p1_off
, p2_base
+ p2_off
);
263 p1_hint
= llist_sorted_remove(p1
->unique_objects
,
266 p2_hint
= llist_sorted_remove(p2
->unique_objects
,
273 if (cmp
< 0) { /* p1 has the object, p2 doesn't */
275 } else { /* p2 has the object, p1 doesn't */
281 static size_t sizeof_union(struct packed_git
*p1
, struct packed_git
*p2
)
284 size_t p1_off
= 0, p2_off
= 0, p1_step
, p2_step
;
285 const unsigned char *p1_base
, *p2_base
;
286 const unsigned int hashsz
= the_hash_algo
->rawsz
;
288 p1_base
= p1
->index_data
;
289 p2_base
= p2
->index_data
;
290 p1_base
+= 256 * 4 + ((p1
->index_version
< 2) ? 4 : 8);
291 p2_base
+= 256 * 4 + ((p2
->index_version
< 2) ? 4 : 8);
292 p1_step
= hashsz
+ ((p1
->index_version
< 2) ? 4 : 0);
293 p2_step
= hashsz
+ ((p2
->index_version
< 2) ? 4 : 0);
295 while (p1_off
< p1
->num_objects
* p1_step
&&
296 p2_off
< p2
->num_objects
* p2_step
)
298 int cmp
= hashcmp(p1_base
+ p1_off
, p2_base
+ p2_off
);
306 if (cmp
< 0) { /* p1 has the object, p2 doesn't */
308 } else { /* p2 has the object, p1 doesn't */
315 /* another O(n^2) function ... */
316 static size_t get_pack_redundancy(struct pack_list
*pl
)
318 struct pack_list
*subset
;
324 while ((subset
= pl
->next
)) {
326 ret
+= sizeof_union(pl
->pack
, subset
->pack
);
327 subset
= subset
->next
;
334 static inline off_t
pack_set_bytecount(struct pack_list
*pl
)
338 ret
+= pl
->pack
->pack_size
;
339 ret
+= pl
->pack
->index_size
;
345 static int cmp_remaining_objects(const void *a
, const void *b
)
347 struct pack_list
*pl_a
= *((struct pack_list
**)a
);
348 struct pack_list
*pl_b
= *((struct pack_list
**)b
);
350 if (pl_a
->remaining_objects
->size
== pl_b
->remaining_objects
->size
) {
351 /* have the same remaining_objects, big pack first */
352 if (pl_a
->all_objects_size
== pl_b
->all_objects_size
)
354 else if (pl_a
->all_objects_size
< pl_b
->all_objects_size
)
358 } else if (pl_a
->remaining_objects
->size
< pl_b
->remaining_objects
->size
) {
359 /* sort by remaining objects, more objects first */
366 /* Sort pack_list, greater size of remaining_objects first */
367 static void sort_pack_list(struct pack_list
**pl
)
369 struct pack_list
**ary
, *p
;
371 size_t n
= pack_list_size(*pl
);
376 /* prepare an array of packed_list for easier sorting */
377 CALLOC_ARRAY(ary
, n
);
378 for (n
= 0, p
= *pl
; p
; p
= p
->next
)
381 QSORT(ary
, n
, cmp_remaining_objects
);
383 /* link them back again */
384 for (i
= 0; i
< n
- 1; i
++)
385 ary
[i
]->next
= ary
[i
+ 1];
386 ary
[n
- 1]->next
= NULL
;
393 static void minimize(struct pack_list
**min
)
395 struct pack_list
*pl
, *unique
= NULL
, *non_unique
= NULL
;
396 struct llist
*missing
, *unique_pack_objects
;
400 if (pl
->unique_objects
->size
)
401 pack_list_insert(&unique
, pl
);
403 pack_list_insert(&non_unique
, pl
);
406 /* find out which objects are missing from the set of unique packs */
407 missing
= llist_copy(all_objects
);
410 llist_sorted_difference_inplace(missing
, pl
->remaining_objects
);
416 /* return if there are no objects missing from the unique set */
417 if (missing
->size
== 0) {
422 unique_pack_objects
= llist_copy(all_objects
);
423 llist_sorted_difference_inplace(unique_pack_objects
, missing
);
425 /* remove unique pack objects from the non_unique packs */
428 llist_sorted_difference_inplace(pl
->remaining_objects
, unique_pack_objects
);
433 /* sort the non_unique packs, greater size of remaining_objects first */
434 sort_pack_list(&non_unique
);
435 if (non_unique
->remaining_objects
->size
== 0)
438 pack_list_insert(min
, non_unique
);
440 for (pl
= non_unique
->next
; pl
&& pl
->remaining_objects
->size
> 0; pl
= pl
->next
)
441 llist_sorted_difference_inplace(pl
->remaining_objects
, non_unique
->remaining_objects
);
443 non_unique
= non_unique
->next
;
447 static void load_all_objects(void)
449 struct pack_list
*pl
= local_packs
;
450 struct llist_item
*hint
, *l
;
452 llist_init(&all_objects
);
456 l
= pl
->remaining_objects
->front
;
458 hint
= llist_insert_sorted_unique(all_objects
,
464 /* remove objects present in remote packs */
467 llist_sorted_difference_inplace(all_objects
, pl
->remaining_objects
);
472 /* this scales like O(n^2) */
473 static void cmp_local_packs(void)
475 struct pack_list
*subset
, *pl
= local_packs
;
477 /* only one packfile */
479 llist_init(&pl
->unique_objects
);
483 while ((subset
= pl
)) {
484 while ((subset
= subset
->next
))
485 cmp_two_packs(pl
, subset
);
490 static void scan_alt_odb_packs(void)
492 struct pack_list
*local
, *alt
;
498 llist_sorted_difference_inplace(local
->remaining_objects
,
499 alt
->remaining_objects
);
506 static struct pack_list
* add_pack(struct packed_git
*p
)
509 size_t off
= 0, step
;
510 const unsigned char *base
;
512 if (!p
->pack_local
&& !(alt_odb
|| verbose
))
516 llist_init(&l
.remaining_objects
);
518 if (open_pack_index(p
))
521 base
= p
->index_data
;
522 base
+= 256 * 4 + ((p
->index_version
< 2) ? 4 : 8);
523 step
= the_hash_algo
->rawsz
+ ((p
->index_version
< 2) ? 4 : 0);
524 while (off
< p
->num_objects
* step
) {
525 llist_insert_back(l
.remaining_objects
, base
+ off
);
528 l
.all_objects_size
= l
.remaining_objects
->size
;
529 l
.unique_objects
= NULL
;
531 return pack_list_insert(&local_packs
, &l
);
533 return pack_list_insert(&altodb_packs
, &l
);
536 static struct pack_list
* add_pack_file(const char *filename
)
538 struct packed_git
*p
= get_all_packs(the_repository
);
540 if (strlen(filename
) < 40)
541 die("Bad pack filename: %s", filename
);
544 if (strstr(p
->pack_name
, filename
))
548 die("Filename %s not found in packed_git", filename
);
551 static void load_all(void)
553 struct packed_git
*p
= get_all_packs(the_repository
);
561 int cmd_pack_redundant(int argc
, const char **argv
, const char *prefix UNUSED
)
564 int i_still_use_this
= 0;
565 struct pack_list
*min
= NULL
, *red
, *pl
;
566 struct llist
*ignore
;
567 struct object_id
*oid
;
568 char buf
[GIT_MAX_HEXSZ
+ 2]; /* hex hash + \n + \0 */
570 if (argc
== 2 && !strcmp(argv
[1], "-h"))
571 usage(pack_redundant_usage
);
573 for (i
= 1; i
< argc
; i
++) {
574 const char *arg
= argv
[i
];
575 if (!strcmp(arg
, "--")) {
579 if (!strcmp(arg
, "--all")) {
583 if (!strcmp(arg
, "--verbose")) {
587 if (!strcmp(arg
, "--alt-odb")) {
591 if (!strcmp(arg
, "--i-still-use-this")) {
592 i_still_use_this
= 1;
596 usage(pack_redundant_usage
);
601 if (!i_still_use_this
) {
602 fputs(_("'git pack-redundant' is nominated for removal.\n"
603 "If you still use this command, please add an extra\n"
604 "option, '--i-still-use-this', on the command line\n"
605 "and let us know you still use it by sending an e-mail\n"
606 "to <git@vger.kernel.org>. Thanks.\n"), stderr
);
607 die(_("refusing to run without --i-still-use-this"));
613 while (*(argv
+ i
) != NULL
)
614 add_pack_file(*(argv
+ i
++));
617 die("Zero packs found!");
622 scan_alt_odb_packs();
624 /* ignore objects given on stdin */
627 while (fgets(buf
, sizeof(buf
), stdin
)) {
628 oid
= xmalloc(sizeof(*oid
));
629 if (get_oid_hex(buf
, oid
))
630 die("Bad object ID on stdin: %s", buf
);
631 llist_insert_sorted_unique(ignore
, oid
, NULL
);
634 llist_sorted_difference_inplace(all_objects
, ignore
);
637 llist_sorted_difference_inplace(pl
->remaining_objects
, ignore
);
646 fprintf(stderr
, "There are %lu packs available in alt-odbs.\n",
647 (unsigned long)pack_list_size(altodb_packs
));
648 fprintf(stderr
, "The smallest (bytewise) set of packs is:\n");
651 fprintf(stderr
, "\t%s\n", pl
->pack
->pack_name
);
654 fprintf(stderr
, "containing %lu duplicate objects "
655 "with a total size of %lukb.\n",
656 (unsigned long)get_pack_redundancy(min
),
657 (unsigned long)pack_set_bytecount(min
)/1024);
658 fprintf(stderr
, "A total of %lu unique objects were considered.\n",
659 (unsigned long)all_objects
->size
);
660 fprintf(stderr
, "Redundant packs (with indexes):\n");
662 pl
= red
= pack_list_difference(local_packs
, min
);
665 sha1_pack_index_name(pl
->pack
->hash
),
666 pl
->pack
->pack_name
);
670 fprintf(stderr
, "%luMB of redundant packs in total.\n",
671 (unsigned long)pack_set_bytecount(red
)/(1024*1024));