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
*remaining_objects
;
36 } *local_packs
= NULL
, *altodb_packs
= NULL
;
38 static struct llist_item
*free_nodes
;
40 static inline void llist_item_put(struct llist_item
*item
)
42 item
->next
= free_nodes
;
46 static inline struct llist_item
*llist_item_get(void)
48 struct llist_item
*new_item
;
50 new_item
= free_nodes
;
51 free_nodes
= free_nodes
->next
;
54 ALLOC_ARRAY(new_item
, BLKSIZE
);
55 for (; i
< BLKSIZE
; i
++)
56 llist_item_put(&new_item
[i
]);
61 static inline void llist_init(struct llist
**list
)
63 *list
= xmalloc(sizeof(struct llist
));
64 (*list
)->front
= (*list
)->back
= NULL
;
68 static struct llist
* llist_copy(struct llist
*list
)
71 struct llist_item
*new_item
, *old_item
, *prev
;
75 if ((ret
->size
= list
->size
) == 0)
78 new_item
= ret
->front
= llist_item_get();
79 new_item
->oid
= list
->front
->oid
;
81 old_item
= list
->front
->next
;
84 new_item
= llist_item_get();
85 prev
->next
= new_item
;
86 new_item
->oid
= old_item
->oid
;
87 old_item
= old_item
->next
;
89 new_item
->next
= NULL
;
95 static inline struct llist_item
*llist_insert(struct llist
*list
,
96 struct llist_item
*after
,
97 const struct object_id
*oid
)
99 struct llist_item
*new_item
= llist_item_get();
101 new_item
->next
= NULL
;
104 new_item
->next
= after
->next
;
105 after
->next
= new_item
;
106 if (after
== list
->back
)
107 list
->back
= new_item
;
108 } else {/* insert in front */
110 list
->back
= new_item
;
112 new_item
->next
= list
->front
;
113 list
->front
= new_item
;
119 static inline struct llist_item
*llist_insert_back(struct llist
*list
,
120 const struct object_id
*oid
)
122 return llist_insert(list
, list
->back
, oid
);
125 static inline struct llist_item
*llist_insert_sorted_unique(struct llist
*list
,
126 const struct object_id
*oid
, struct llist_item
*hint
)
128 struct llist_item
*prev
= NULL
, *l
;
130 l
= (hint
== NULL
) ? list
->front
: hint
;
132 int cmp
= oidcmp(l
->oid
, oid
);
133 if (cmp
> 0) { /* we insert before this entry */
134 return llist_insert(list
, prev
, oid
);
136 if (!cmp
) { /* already exists */
142 /* insert at the end */
143 return llist_insert_back(list
, oid
);
146 /* returns a pointer to an item in front of sha1 */
147 static inline struct llist_item
* llist_sorted_remove(struct llist
*list
, const struct object_id
*oid
, struct llist_item
*hint
)
149 struct llist_item
*prev
, *l
;
152 l
= (hint
== NULL
) ? list
->front
: hint
;
155 int cmp
= oidcmp(l
->oid
, oid
);
156 if (cmp
> 0) /* not in list, since sorted */
158 if (!cmp
) { /* found */
160 if (hint
!= NULL
&& hint
!= list
->front
) {
161 /* we don't know the previous element */
163 goto redo_from_start
;
165 list
->front
= l
->next
;
167 prev
->next
= l
->next
;
181 static void llist_sorted_difference_inplace(struct llist
*A
,
184 struct llist_item
*hint
, *b
;
190 hint
= llist_sorted_remove(A
, b
->oid
, hint
);
195 static inline struct pack_list
* pack_list_insert(struct pack_list
**pl
,
196 struct pack_list
*entry
)
198 struct pack_list
*p
= xmalloc(sizeof(struct pack_list
));
199 memcpy(p
, entry
, sizeof(struct pack_list
));
205 static inline size_t pack_list_size(struct pack_list
*pl
)
215 static struct pack_list
* pack_list_difference(const struct pack_list
*A
,
216 const struct pack_list
*B
)
218 struct pack_list
*ret
;
219 const struct pack_list
*pl
;
226 if (A
->pack
== pl
->pack
)
227 return pack_list_difference(A
->next
, B
);
230 ret
= xmalloc(sizeof(struct pack_list
));
231 memcpy(ret
, A
, sizeof(struct pack_list
));
232 ret
->next
= pack_list_difference(A
->next
, B
);
236 static void cmp_two_packs(struct pack_list
*p1
, struct pack_list
*p2
)
238 unsigned long p1_off
= 0, p2_off
= 0, p1_step
, p2_step
;
239 const unsigned char *p1_base
, *p2_base
;
240 struct llist_item
*p1_hint
= NULL
, *p2_hint
= NULL
;
241 const unsigned int hashsz
= the_hash_algo
->rawsz
;
243 if (!p1
->unique_objects
)
244 p1
->unique_objects
= llist_copy(p1
->remaining_objects
);
245 if (!p2
->unique_objects
)
246 p2
->unique_objects
= llist_copy(p2
->remaining_objects
);
248 p1_base
= p1
->pack
->index_data
;
249 p2_base
= p2
->pack
->index_data
;
250 p1_base
+= 256 * 4 + ((p1
->pack
->index_version
< 2) ? 4 : 8);
251 p2_base
+= 256 * 4 + ((p2
->pack
->index_version
< 2) ? 4 : 8);
252 p1_step
= hashsz
+ ((p1
->pack
->index_version
< 2) ? 4 : 0);
253 p2_step
= hashsz
+ ((p2
->pack
->index_version
< 2) ? 4 : 0);
255 while (p1_off
< p1
->pack
->num_objects
* p1_step
&&
256 p2_off
< p2
->pack
->num_objects
* p2_step
)
258 int cmp
= hashcmp(p1_base
+ p1_off
, p2_base
+ p2_off
);
261 p1_hint
= llist_sorted_remove(p1
->unique_objects
,
262 (const struct object_id
*)(p1_base
+ p1_off
),
264 p2_hint
= llist_sorted_remove(p2
->unique_objects
,
265 (const struct object_id
*)(p1_base
+ p1_off
),
271 if (cmp
< 0) { /* p1 has the object, p2 doesn't */
273 } else { /* p2 has the object, p1 doesn't */
279 static size_t sizeof_union(struct packed_git
*p1
, struct packed_git
*p2
)
282 unsigned long p1_off
= 0, p2_off
= 0, p1_step
, p2_step
;
283 const unsigned char *p1_base
, *p2_base
;
284 const unsigned int hashsz
= the_hash_algo
->rawsz
;
286 p1_base
= p1
->index_data
;
287 p2_base
= p2
->index_data
;
288 p1_base
+= 256 * 4 + ((p1
->index_version
< 2) ? 4 : 8);
289 p2_base
+= 256 * 4 + ((p2
->index_version
< 2) ? 4 : 8);
290 p1_step
= hashsz
+ ((p1
->index_version
< 2) ? 4 : 0);
291 p2_step
= hashsz
+ ((p2
->index_version
< 2) ? 4 : 0);
293 while (p1_off
< p1
->num_objects
* p1_step
&&
294 p2_off
< p2
->num_objects
* p2_step
)
296 int cmp
= hashcmp(p1_base
+ p1_off
, p2_base
+ p2_off
);
304 if (cmp
< 0) { /* p1 has the object, p2 doesn't */
306 } else { /* p2 has the object, p1 doesn't */
313 /* another O(n^2) function ... */
314 static size_t get_pack_redundancy(struct pack_list
*pl
)
316 struct pack_list
*subset
;
322 while ((subset
= pl
->next
)) {
324 ret
+= sizeof_union(pl
->pack
, subset
->pack
);
325 subset
= subset
->next
;
332 static inline off_t
pack_set_bytecount(struct pack_list
*pl
)
336 ret
+= pl
->pack
->pack_size
;
337 ret
+= pl
->pack
->index_size
;
343 static int cmp_pack_list_reverse(const void *a
, const void *b
)
345 struct pack_list
*pl_a
= *((struct pack_list
**)a
);
346 struct pack_list
*pl_b
= *((struct pack_list
**)b
);
347 size_t sz_a
= pl_a
->remaining_objects
->size
;
348 size_t sz_b
= pl_b
->remaining_objects
->size
;
352 else if (sz_a
< sz_b
)
358 /* Sort pack_list, greater size of remaining_objects first */
359 static void sort_pack_list(struct pack_list
**pl
)
361 struct pack_list
**ary
, *p
;
363 size_t n
= pack_list_size(*pl
);
368 /* prepare an array of packed_list for easier sorting */
369 ary
= xcalloc(n
, sizeof(struct pack_list
*));
370 for (n
= 0, p
= *pl
; p
; p
= p
->next
)
373 QSORT(ary
, n
, cmp_pack_list_reverse
);
375 /* link them back again */
376 for (i
= 0; i
< n
- 1; i
++)
377 ary
[i
]->next
= ary
[i
+ 1];
378 ary
[n
- 1]->next
= NULL
;
385 static void minimize(struct pack_list
**min
)
387 struct pack_list
*pl
, *unique
= NULL
, *non_unique
= NULL
;
388 struct llist
*missing
, *unique_pack_objects
;
392 if (pl
->unique_objects
->size
)
393 pack_list_insert(&unique
, pl
);
395 pack_list_insert(&non_unique
, pl
);
398 /* find out which objects are missing from the set of unique packs */
399 missing
= llist_copy(all_objects
);
402 llist_sorted_difference_inplace(missing
, pl
->remaining_objects
);
408 /* return if there are no objects missing from the unique set */
409 if (missing
->size
== 0) {
414 unique_pack_objects
= llist_copy(all_objects
);
415 llist_sorted_difference_inplace(unique_pack_objects
, missing
);
417 /* remove unique pack objects from the non_unique packs */
420 llist_sorted_difference_inplace(pl
->remaining_objects
, unique_pack_objects
);
425 /* sort the non_unique packs, greater size of remaining_objects first */
426 sort_pack_list(&non_unique
);
427 if (non_unique
->remaining_objects
->size
== 0)
430 pack_list_insert(min
, non_unique
);
432 for (pl
= non_unique
->next
; pl
&& pl
->remaining_objects
->size
> 0; pl
= pl
->next
)
433 llist_sorted_difference_inplace(pl
->remaining_objects
, non_unique
->remaining_objects
);
435 non_unique
= non_unique
->next
;
439 static void load_all_objects(void)
441 struct pack_list
*pl
= local_packs
;
442 struct llist_item
*hint
, *l
;
444 llist_init(&all_objects
);
448 l
= pl
->remaining_objects
->front
;
450 hint
= llist_insert_sorted_unique(all_objects
,
456 /* remove objects present in remote packs */
459 llist_sorted_difference_inplace(all_objects
, pl
->remaining_objects
);
464 /* this scales like O(n^2) */
465 static void cmp_local_packs(void)
467 struct pack_list
*subset
, *pl
= local_packs
;
469 while ((subset
= pl
)) {
470 while ((subset
= subset
->next
))
471 cmp_two_packs(pl
, subset
);
476 static void scan_alt_odb_packs(void)
478 struct pack_list
*local
, *alt
;
484 llist_sorted_difference_inplace(local
->remaining_objects
,
485 alt
->remaining_objects
);
492 static struct pack_list
* add_pack(struct packed_git
*p
)
495 unsigned long off
= 0, step
;
496 const unsigned char *base
;
498 if (!p
->pack_local
&& !(alt_odb
|| verbose
))
502 llist_init(&l
.remaining_objects
);
504 if (open_pack_index(p
))
507 base
= p
->index_data
;
508 base
+= 256 * 4 + ((p
->index_version
< 2) ? 4 : 8);
509 step
= the_hash_algo
->rawsz
+ ((p
->index_version
< 2) ? 4 : 0);
510 while (off
< p
->num_objects
* step
) {
511 llist_insert_back(l
.remaining_objects
, (const struct object_id
*)(base
+ off
));
514 l
.unique_objects
= NULL
;
516 return pack_list_insert(&local_packs
, &l
);
518 return pack_list_insert(&altodb_packs
, &l
);
521 static struct pack_list
* add_pack_file(const char *filename
)
523 struct packed_git
*p
= get_all_packs(the_repository
);
525 if (strlen(filename
) < 40)
526 die("Bad pack filename: %s", filename
);
529 if (strstr(p
->pack_name
, filename
))
533 die("Filename %s not found in packed_git", filename
);
536 static void load_all(void)
538 struct packed_git
*p
= get_all_packs(the_repository
);
546 int cmd_pack_redundant(int argc
, const char **argv
, const char *prefix
)
549 struct pack_list
*min
= NULL
, *red
, *pl
;
550 struct llist
*ignore
;
551 struct object_id
*oid
;
552 char buf
[GIT_MAX_HEXSZ
+ 2]; /* hex hash + \n + \0 */
554 if (argc
== 2 && !strcmp(argv
[1], "-h"))
555 usage(pack_redundant_usage
);
557 for (i
= 1; i
< argc
; i
++) {
558 const char *arg
= argv
[i
];
559 if (!strcmp(arg
, "--")) {
563 if (!strcmp(arg
, "--all")) {
567 if (!strcmp(arg
, "--verbose")) {
571 if (!strcmp(arg
, "--alt-odb")) {
576 usage(pack_redundant_usage
);
584 while (*(argv
+ i
) != NULL
)
585 add_pack_file(*(argv
+ i
++));
587 if (local_packs
== NULL
)
588 die("Zero packs found!");
593 scan_alt_odb_packs();
595 /* ignore objects given on stdin */
598 while (fgets(buf
, sizeof(buf
), stdin
)) {
599 oid
= xmalloc(sizeof(*oid
));
600 if (get_oid_hex(buf
, oid
))
601 die("Bad object ID on stdin: %s", buf
);
602 llist_insert_sorted_unique(ignore
, oid
, NULL
);
605 llist_sorted_difference_inplace(all_objects
, ignore
);
608 llist_sorted_difference_inplace(pl
->remaining_objects
, ignore
);
617 fprintf(stderr
, "There are %lu packs available in alt-odbs.\n",
618 (unsigned long)pack_list_size(altodb_packs
));
619 fprintf(stderr
, "The smallest (bytewise) set of packs is:\n");
622 fprintf(stderr
, "\t%s\n", pl
->pack
->pack_name
);
625 fprintf(stderr
, "containing %lu duplicate objects "
626 "with a total size of %lukb.\n",
627 (unsigned long)get_pack_redundancy(min
),
628 (unsigned long)pack_set_bytecount(min
)/1024);
629 fprintf(stderr
, "A total of %lu unique objects were considered.\n",
630 (unsigned long)all_objects
->size
);
631 fprintf(stderr
, "Redundant packs (with indexes):\n");
633 pl
= red
= pack_list_difference(local_packs
, min
);
636 sha1_pack_index_name(pl
->pack
->sha1
),
637 pl
->pack
->pack_name
);
641 fprintf(stderr
, "%luMB of redundant packs in total.\n",
642 (unsigned long)pack_set_bytecount(red
)/(1024*1024));