builtin/show: do not prune by pathspec
[git/mjg.git] / builtin / pack-redundant.c
blobdd9bf35f5b8c087ef286ac4f080a3ba8bbbf0ba8
1 /*
3 * Copyright 2005, Lukas Sandstrom <lukass@etek.chalmers.se>
5 * This file is licensed under the GPL v2.
7 */
9 #include "builtin.h"
10 #include "gettext.h"
11 #include "hex.h"
12 #include "repository.h"
13 #include "packfile.h"
14 #include "object-store-ll.h"
16 #define BLKSIZE 512
18 static const char pack_redundant_usage[] =
19 "git pack-redundant [--verbose] [--alt-odb] (--all | <pack-filename>...)";
21 static int load_all_packs, verbose, alt_odb;
23 struct llist_item {
24 struct llist_item *next;
25 struct object_id oid;
27 static struct llist {
28 struct llist_item *front;
29 struct llist_item *back;
30 size_t size;
31 } *all_objects; /* all objects which must be present in local packfiles */
33 static struct pack_list {
34 struct pack_list *next;
35 struct packed_git *pack;
36 struct llist *unique_objects;
37 struct llist *remaining_objects;
38 size_t all_objects_size;
39 } *local_packs = NULL, *altodb_packs = NULL;
41 static struct llist_item *free_nodes;
43 static inline void llist_item_put(struct llist_item *item)
45 item->next = free_nodes;
46 free_nodes = item;
49 static inline struct llist_item *llist_item_get(void)
51 struct llist_item *new_item;
52 if ( free_nodes ) {
53 new_item = free_nodes;
54 free_nodes = free_nodes->next;
55 } else {
56 int i = 1;
57 ALLOC_ARRAY(new_item, BLKSIZE);
58 for (; i < BLKSIZE; i++)
59 llist_item_put(&new_item[i]);
61 return new_item;
64 static inline void llist_init(struct llist **list)
66 *list = xmalloc(sizeof(struct llist));
67 (*list)->front = (*list)->back = NULL;
68 (*list)->size = 0;
71 static struct llist * llist_copy(struct llist *list)
73 struct llist *ret;
74 struct llist_item *new_item, *old_item, *prev;
76 llist_init(&ret);
78 if ((ret->size = list->size) == 0)
79 return ret;
81 new_item = ret->front = llist_item_get();
82 new_item->oid = list->front->oid;
84 old_item = list->front->next;
85 while (old_item) {
86 prev = new_item;
87 new_item = llist_item_get();
88 prev->next = new_item;
89 new_item->oid = old_item->oid;
90 old_item = old_item->next;
92 new_item->next = NULL;
93 ret->back = new_item;
95 return ret;
98 static inline struct llist_item *llist_insert(struct llist *list,
99 struct llist_item *after,
100 const unsigned char *oid)
102 struct llist_item *new_item = llist_item_get();
103 oidread(&new_item->oid, oid, the_repository->hash_algo);
104 new_item->next = NULL;
106 if (after) {
107 new_item->next = after->next;
108 after->next = new_item;
109 if (after == list->back)
110 list->back = new_item;
111 } else {/* insert in front */
112 if (list->size == 0)
113 list->back = new_item;
114 else
115 new_item->next = list->front;
116 list->front = new_item;
118 list->size++;
119 return new_item;
122 static inline struct llist_item *llist_insert_back(struct llist *list,
123 const unsigned char *oid)
125 return llist_insert(list, list->back, oid);
128 static inline struct llist_item *llist_insert_sorted_unique(struct llist *list,
129 const struct object_id *oid, struct llist_item *hint)
131 struct llist_item *prev = NULL, *l;
133 l = (hint == NULL) ? list->front : hint;
134 while (l) {
135 int cmp = oidcmp(&l->oid, oid);
136 if (cmp > 0) { /* we insert before this entry */
137 return llist_insert(list, prev, oid->hash);
139 if (!cmp) { /* already exists */
140 return l;
142 prev = l;
143 l = l->next;
145 /* insert at the end */
146 return llist_insert_back(list, oid->hash);
149 /* returns a pointer to an item in front of sha1 */
150 static inline struct llist_item * llist_sorted_remove(struct llist *list, const unsigned char *oid, struct llist_item *hint)
152 struct llist_item *prev, *l;
154 redo_from_start:
155 l = (hint == NULL) ? list->front : hint;
156 prev = NULL;
157 while (l) {
158 const int cmp = hashcmp(l->oid.hash, oid, the_repository->hash_algo);
159 if (cmp > 0) /* not in list, since sorted */
160 return prev;
161 if (!cmp) { /* found */
162 if (!prev) {
163 if (hint != NULL && hint != list->front) {
164 /* we don't know the previous element */
165 hint = NULL;
166 goto redo_from_start;
168 list->front = l->next;
169 } else
170 prev->next = l->next;
171 if (l == list->back)
172 list->back = prev;
173 llist_item_put(l);
174 list->size--;
175 return prev;
177 prev = l;
178 l = l->next;
180 return prev;
183 /* computes A\B */
184 static void llist_sorted_difference_inplace(struct llist *A,
185 struct llist *B)
187 struct llist_item *hint, *b;
189 hint = NULL;
190 b = B->front;
192 while (b) {
193 hint = llist_sorted_remove(A, b->oid.hash, hint);
194 b = b->next;
198 static inline struct pack_list * pack_list_insert(struct pack_list **pl,
199 struct pack_list *entry)
201 struct pack_list *p = xmalloc(sizeof(struct pack_list));
202 memcpy(p, entry, sizeof(struct pack_list));
203 p->next = *pl;
204 *pl = p;
205 return p;
208 static inline size_t pack_list_size(struct pack_list *pl)
210 size_t ret = 0;
211 while (pl) {
212 ret++;
213 pl = pl->next;
215 return ret;
218 static struct pack_list * pack_list_difference(const struct pack_list *A,
219 const struct pack_list *B)
221 struct pack_list *ret;
222 const struct pack_list *pl;
224 if (!A)
225 return NULL;
227 pl = B;
228 while (pl != NULL) {
229 if (A->pack == pl->pack)
230 return pack_list_difference(A->next, B);
231 pl = pl->next;
233 ret = xmalloc(sizeof(struct pack_list));
234 memcpy(ret, A, sizeof(struct pack_list));
235 ret->next = pack_list_difference(A->next, B);
236 return ret;
239 static void cmp_two_packs(struct pack_list *p1, struct pack_list *p2)
241 size_t p1_off = 0, p2_off = 0, p1_step, p2_step;
242 const unsigned char *p1_base, *p2_base;
243 struct llist_item *p1_hint = NULL, *p2_hint = NULL;
244 const unsigned int hashsz = the_hash_algo->rawsz;
246 if (!p1->unique_objects)
247 p1->unique_objects = llist_copy(p1->remaining_objects);
248 if (!p2->unique_objects)
249 p2->unique_objects = llist_copy(p2->remaining_objects);
251 p1_base = p1->pack->index_data;
252 p2_base = p2->pack->index_data;
253 p1_base += 256 * 4 + ((p1->pack->index_version < 2) ? 4 : 8);
254 p2_base += 256 * 4 + ((p2->pack->index_version < 2) ? 4 : 8);
255 p1_step = hashsz + ((p1->pack->index_version < 2) ? 4 : 0);
256 p2_step = hashsz + ((p2->pack->index_version < 2) ? 4 : 0);
258 while (p1_off < p1->pack->num_objects * p1_step &&
259 p2_off < p2->pack->num_objects * p2_step)
261 const int cmp = hashcmp(p1_base + p1_off, p2_base + p2_off,
262 the_repository->hash_algo);
263 /* cmp ~ p1 - p2 */
264 if (cmp == 0) {
265 p1_hint = llist_sorted_remove(p1->unique_objects,
266 p1_base + p1_off,
267 p1_hint);
268 p2_hint = llist_sorted_remove(p2->unique_objects,
269 p1_base + p1_off,
270 p2_hint);
271 p1_off += p1_step;
272 p2_off += p2_step;
273 continue;
275 if (cmp < 0) { /* p1 has the object, p2 doesn't */
276 p1_off += p1_step;
277 } else { /* p2 has the object, p1 doesn't */
278 p2_off += p2_step;
283 static size_t sizeof_union(struct packed_git *p1, struct packed_git *p2)
285 size_t ret = 0;
286 size_t p1_off = 0, p2_off = 0, p1_step, p2_step;
287 const unsigned char *p1_base, *p2_base;
288 const unsigned int hashsz = the_hash_algo->rawsz;
290 p1_base = p1->index_data;
291 p2_base = p2->index_data;
292 p1_base += 256 * 4 + ((p1->index_version < 2) ? 4 : 8);
293 p2_base += 256 * 4 + ((p2->index_version < 2) ? 4 : 8);
294 p1_step = hashsz + ((p1->index_version < 2) ? 4 : 0);
295 p2_step = hashsz + ((p2->index_version < 2) ? 4 : 0);
297 while (p1_off < p1->num_objects * p1_step &&
298 p2_off < p2->num_objects * p2_step)
300 int cmp = hashcmp(p1_base + p1_off, p2_base + p2_off,
301 the_repository->hash_algo);
302 /* cmp ~ p1 - p2 */
303 if (cmp == 0) {
304 ret++;
305 p1_off += p1_step;
306 p2_off += p2_step;
307 continue;
309 if (cmp < 0) { /* p1 has the object, p2 doesn't */
310 p1_off += p1_step;
311 } else { /* p2 has the object, p1 doesn't */
312 p2_off += p2_step;
315 return ret;
318 /* another O(n^2) function ... */
319 static size_t get_pack_redundancy(struct pack_list *pl)
321 struct pack_list *subset;
322 size_t ret = 0;
324 if (!pl)
325 return 0;
327 while ((subset = pl->next)) {
328 while (subset) {
329 ret += sizeof_union(pl->pack, subset->pack);
330 subset = subset->next;
332 pl = pl->next;
334 return ret;
337 static inline off_t pack_set_bytecount(struct pack_list *pl)
339 off_t ret = 0;
340 while (pl) {
341 ret += pl->pack->pack_size;
342 ret += pl->pack->index_size;
343 pl = pl->next;
345 return ret;
348 static int cmp_remaining_objects(const void *a, const void *b)
350 struct pack_list *pl_a = *((struct pack_list **)a);
351 struct pack_list *pl_b = *((struct pack_list **)b);
353 if (pl_a->remaining_objects->size == pl_b->remaining_objects->size) {
354 /* have the same remaining_objects, big pack first */
355 if (pl_a->all_objects_size == pl_b->all_objects_size)
356 return 0;
357 else if (pl_a->all_objects_size < pl_b->all_objects_size)
358 return 1;
359 else
360 return -1;
361 } else if (pl_a->remaining_objects->size < pl_b->remaining_objects->size) {
362 /* sort by remaining objects, more objects first */
363 return 1;
364 } else {
365 return -1;
369 /* Sort pack_list, greater size of remaining_objects first */
370 static void sort_pack_list(struct pack_list **pl)
372 struct pack_list **ary, *p;
373 int i;
374 size_t n = pack_list_size(*pl);
376 if (n < 2)
377 return;
379 /* prepare an array of packed_list for easier sorting */
380 CALLOC_ARRAY(ary, n);
381 for (n = 0, p = *pl; p; p = p->next)
382 ary[n++] = p;
384 QSORT(ary, n, cmp_remaining_objects);
386 /* link them back again */
387 for (i = 0; i < n - 1; i++)
388 ary[i]->next = ary[i + 1];
389 ary[n - 1]->next = NULL;
390 *pl = ary[0];
392 free(ary);
396 static void minimize(struct pack_list **min)
398 struct pack_list *pl, *unique = NULL, *non_unique = NULL;
399 struct llist *missing, *unique_pack_objects;
401 pl = local_packs;
402 while (pl) {
403 if (pl->unique_objects->size)
404 pack_list_insert(&unique, pl);
405 else
406 pack_list_insert(&non_unique, pl);
407 pl = pl->next;
409 /* find out which objects are missing from the set of unique packs */
410 missing = llist_copy(all_objects);
411 pl = unique;
412 while (pl) {
413 llist_sorted_difference_inplace(missing, pl->remaining_objects);
414 pl = pl->next;
417 *min = unique;
419 /* return if there are no objects missing from the unique set */
420 if (missing->size == 0) {
421 free(missing);
422 return;
425 unique_pack_objects = llist_copy(all_objects);
426 llist_sorted_difference_inplace(unique_pack_objects, missing);
428 /* remove unique pack objects from the non_unique packs */
429 pl = non_unique;
430 while (pl) {
431 llist_sorted_difference_inplace(pl->remaining_objects, unique_pack_objects);
432 pl = pl->next;
435 while (non_unique) {
436 /* sort the non_unique packs, greater size of remaining_objects first */
437 sort_pack_list(&non_unique);
438 if (non_unique->remaining_objects->size == 0)
439 break;
441 pack_list_insert(min, non_unique);
443 for (pl = non_unique->next; pl && pl->remaining_objects->size > 0; pl = pl->next)
444 llist_sorted_difference_inplace(pl->remaining_objects, non_unique->remaining_objects);
446 non_unique = non_unique->next;
450 static void load_all_objects(void)
452 struct pack_list *pl = local_packs;
453 struct llist_item *hint, *l;
455 llist_init(&all_objects);
457 while (pl) {
458 hint = NULL;
459 l = pl->remaining_objects->front;
460 while (l) {
461 hint = llist_insert_sorted_unique(all_objects,
462 &l->oid, hint);
463 l = l->next;
465 pl = pl->next;
467 /* remove objects present in remote packs */
468 pl = altodb_packs;
469 while (pl) {
470 llist_sorted_difference_inplace(all_objects, pl->remaining_objects);
471 pl = pl->next;
475 /* this scales like O(n^2) */
476 static void cmp_local_packs(void)
478 struct pack_list *subset, *pl = local_packs;
480 /* only one packfile */
481 if (!pl->next) {
482 llist_init(&pl->unique_objects);
483 return;
486 while ((subset = pl)) {
487 while ((subset = subset->next))
488 cmp_two_packs(pl, subset);
489 pl = pl->next;
493 static void scan_alt_odb_packs(void)
495 struct pack_list *local, *alt;
497 alt = altodb_packs;
498 while (alt) {
499 local = local_packs;
500 while (local) {
501 llist_sorted_difference_inplace(local->remaining_objects,
502 alt->remaining_objects);
503 local = local->next;
505 alt = alt->next;
509 static struct pack_list * add_pack(struct packed_git *p)
511 struct pack_list l;
512 size_t off = 0, step;
513 const unsigned char *base;
515 if (!p->pack_local && !(alt_odb || verbose))
516 return NULL;
518 l.pack = p;
519 llist_init(&l.remaining_objects);
521 if (open_pack_index(p))
522 return NULL;
524 base = p->index_data;
525 base += 256 * 4 + ((p->index_version < 2) ? 4 : 8);
526 step = the_hash_algo->rawsz + ((p->index_version < 2) ? 4 : 0);
527 while (off < p->num_objects * step) {
528 llist_insert_back(l.remaining_objects, base + off);
529 off += step;
531 l.all_objects_size = l.remaining_objects->size;
532 l.unique_objects = NULL;
533 if (p->pack_local)
534 return pack_list_insert(&local_packs, &l);
535 else
536 return pack_list_insert(&altodb_packs, &l);
539 static struct pack_list * add_pack_file(const char *filename)
541 struct packed_git *p = get_all_packs(the_repository);
543 if (strlen(filename) < 40)
544 die("Bad pack filename: %s", filename);
546 while (p) {
547 if (strstr(p->pack_name, filename))
548 return add_pack(p);
549 p = p->next;
551 die("Filename %s not found in packed_git", filename);
554 static void load_all(void)
556 struct packed_git *p = get_all_packs(the_repository);
558 while (p) {
559 add_pack(p);
560 p = p->next;
564 int cmd_pack_redundant(int argc, const char **argv, const char *prefix UNUSED)
566 int i;
567 int i_still_use_this = 0;
568 struct pack_list *min = NULL, *red, *pl;
569 struct llist *ignore;
570 struct object_id *oid;
571 char buf[GIT_MAX_HEXSZ + 2]; /* hex hash + \n + \0 */
573 if (argc == 2 && !strcmp(argv[1], "-h"))
574 usage(pack_redundant_usage);
576 for (i = 1; i < argc; i++) {
577 const char *arg = argv[i];
578 if (!strcmp(arg, "--")) {
579 i++;
580 break;
582 if (!strcmp(arg, "--all")) {
583 load_all_packs = 1;
584 continue;
586 if (!strcmp(arg, "--verbose")) {
587 verbose = 1;
588 continue;
590 if (!strcmp(arg, "--alt-odb")) {
591 alt_odb = 1;
592 continue;
594 if (!strcmp(arg, "--i-still-use-this")) {
595 i_still_use_this = 1;
596 continue;
598 if (*arg == '-')
599 usage(pack_redundant_usage);
600 else
601 break;
604 if (!i_still_use_this) {
605 fputs(_("'git pack-redundant' is nominated for removal.\n"
606 "If you still use this command, please add an extra\n"
607 "option, '--i-still-use-this', on the command line\n"
608 "and let us know you still use it by sending an e-mail\n"
609 "to <git@vger.kernel.org>. Thanks.\n"), stderr);
610 die(_("refusing to run without --i-still-use-this"));
613 if (load_all_packs)
614 load_all();
615 else
616 while (*(argv + i) != NULL)
617 add_pack_file(*(argv + i++));
619 if (!local_packs)
620 die("Zero packs found!");
622 load_all_objects();
624 if (alt_odb)
625 scan_alt_odb_packs();
627 /* ignore objects given on stdin */
628 llist_init(&ignore);
629 if (!isatty(0)) {
630 while (fgets(buf, sizeof(buf), stdin)) {
631 oid = xmalloc(sizeof(*oid));
632 if (get_oid_hex(buf, oid))
633 die("Bad object ID on stdin: %s", buf);
634 llist_insert_sorted_unique(ignore, oid, NULL);
637 llist_sorted_difference_inplace(all_objects, ignore);
638 pl = local_packs;
639 while (pl) {
640 llist_sorted_difference_inplace(pl->remaining_objects, ignore);
641 pl = pl->next;
644 cmp_local_packs();
646 minimize(&min);
648 if (verbose) {
649 fprintf(stderr, "There are %lu packs available in alt-odbs.\n",
650 (unsigned long)pack_list_size(altodb_packs));
651 fprintf(stderr, "The smallest (bytewise) set of packs is:\n");
652 pl = min;
653 while (pl) {
654 fprintf(stderr, "\t%s\n", pl->pack->pack_name);
655 pl = pl->next;
657 fprintf(stderr, "containing %lu duplicate objects "
658 "with a total size of %lukb.\n",
659 (unsigned long)get_pack_redundancy(min),
660 (unsigned long)pack_set_bytecount(min)/1024);
661 fprintf(stderr, "A total of %lu unique objects were considered.\n",
662 (unsigned long)all_objects->size);
663 fprintf(stderr, "Redundant packs (with indexes):\n");
665 pl = red = pack_list_difference(local_packs, min);
666 while (pl) {
667 printf("%s\n%s\n",
668 sha1_pack_index_name(pl->pack->hash),
669 pl->pack->pack_name);
670 pl = pl->next;
672 if (verbose)
673 fprintf(stderr, "%luMB of redundant packs in total.\n",
674 (unsigned long)pack_set_bytecount(red)/(1024*1024));
676 return 0;