merge-recursive: conflicting rename case.
[git/git.git] / pack-redundant.c
CommitLineData
c283ab21
LS
1/*
2*
3* Copyright 2005, Lukas Sandstrom <lukass@etek.chalmers.se>
4*
5* This file is licensed under the GPL v2.
6*
7*/
8
9#include "cache.h"
10
9bc0f32c 11static const char pack_redundant_usage[] =
1c3039e8 12"git-pack-redundant [ --verbose ] [ --alt-odb ] < --all | <.pack filename> ...>";
c283ab21 13
bd22c904 14static int load_all_packs = 0, verbose = 0, alt_odb = 0;
c283ab21
LS
15
16struct llist_item {
17 struct llist_item *next;
b99a394c 18 unsigned char *sha1;
c283ab21 19};
bd22c904 20static struct llist {
c283ab21
LS
21 struct llist_item *front;
22 struct llist_item *back;
23 size_t size;
1c3039e8 24} *all_objects; /* all objects which must be present in local packfiles */
c283ab21 25
bd22c904 26static struct pack_list {
c283ab21
LS
27 struct pack_list *next;
28 struct packed_git *pack;
29 struct llist *unique_objects;
30 struct llist *all_objects;
1c3039e8 31} *local_packs = NULL, *altodb_packs = NULL;
c283ab21
LS
32
33struct pll {
34 struct pll *next;
35 struct pack_list *pl;
751a71e2 36 size_t pl_size;
c283ab21
LS
37};
38
60435f68
AR
39static struct llist_item *free_nodes = NULL;
40
41static inline struct llist_item *llist_item_get()
42{
43 struct llist_item *new;
44 if ( free_nodes ) {
45 new = free_nodes;
46 free_nodes = free_nodes->next;
47 } else
48 new = xmalloc(sizeof(struct llist_item));
49
50 return new;
51}
52
53static inline void llist_item_put(struct llist_item *item)
54{
55 item->next = free_nodes;
56 free_nodes = item;
57}
58
59static void llist_free(struct llist *list)
c283ab21
LS
60{
61 while((list->back = list->front)) {
62 list->front = list->front->next;
60435f68 63 llist_item_put(list->back);
c283ab21
LS
64 }
65 free(list);
66}
67
bd22c904 68static inline void llist_init(struct llist **list)
c283ab21
LS
69{
70 *list = xmalloc(sizeof(struct llist));
71 (*list)->front = (*list)->back = NULL;
72 (*list)->size = 0;
73}
74
bd22c904 75static struct llist * llist_copy(struct llist *list)
c283ab21
LS
76{
77 struct llist *ret;
78 struct llist_item *new, *old, *prev;
79
80 llist_init(&ret);
81
82 if ((ret->size = list->size) == 0)
83 return ret;
84
60435f68 85 new = ret->front = llist_item_get();
c283ab21
LS
86 new->sha1 = list->front->sha1;
87
88 old = list->front->next;
89 while (old) {
90 prev = new;
60435f68 91 new = llist_item_get();
c283ab21
LS
92 prev->next = new;
93 new->sha1 = old->sha1;
94 old = old->next;
95 }
96 new->next = NULL;
97 ret->back = new;
98
99 return ret;
100}
101
bd22c904 102static inline struct llist_item * llist_insert(struct llist *list,
b99a394c
JH
103 struct llist_item *after,
104 unsigned char *sha1)
c283ab21 105{
60435f68 106 struct llist_item *new = llist_item_get();
c283ab21
LS
107 new->sha1 = sha1;
108 new->next = NULL;
109
110 if (after != NULL) {
111 new->next = after->next;
112 after->next = new;
113 if (after == list->back)
114 list->back = new;
115 } else {/* insert in front */
116 if (list->size == 0)
117 list->back = new;
118 else
119 new->next = list->front;
120 list->front = new;
121 }
122 list->size++;
123 return new;
124}
125
b99a394c 126static inline struct llist_item *llist_insert_back(struct llist *list, unsigned char *sha1)
c283ab21
LS
127{
128 return llist_insert(list, list->back, sha1);
129}
130
b99a394c 131static inline struct llist_item *llist_insert_sorted_unique(struct llist *list, unsigned char *sha1, struct llist_item *hint)
c283ab21
LS
132{
133 struct llist_item *prev = NULL, *l;
134
135 l = (hint == NULL) ? list->front : hint;
136 while (l) {
137 int cmp = memcmp(l->sha1, sha1, 20);
138 if (cmp > 0) { /* we insert before this entry */
139 return llist_insert(list, prev, sha1);
140 }
141 if(!cmp) { /* already exists */
142 return l;
143 }
144 prev = l;
145 l = l->next;
146 }
147 /* insert at the end */
148 return llist_insert_back(list, sha1);
149}
150
c283ab21 151/* returns a pointer to an item in front of sha1 */
b99a394c 152static inline struct llist_item * llist_sorted_remove(struct llist *list, const unsigned char *sha1, struct llist_item *hint)
c283ab21
LS
153{
154 struct llist_item *prev, *l;
155
156redo_from_start:
157 l = (hint == NULL) ? list->front : hint;
158 prev = NULL;
159 while (l) {
160 int cmp = memcmp(l->sha1, sha1, 20);
161 if (cmp > 0) /* not in list, since sorted */
162 return prev;
163 if(!cmp) { /* found */
164 if (prev == NULL) {
165 if (hint != NULL && hint != list->front) {
166 /* we don't know the previous element */
167 hint = NULL;
168 goto redo_from_start;
169 }
170 list->front = l->next;
171 } else
172 prev->next = l->next;
173 if (l == list->back)
174 list->back = prev;
60435f68 175 llist_item_put(l);
c283ab21
LS
176 list->size--;
177 return prev;
178 }
179 prev = l;
180 l = l->next;
181 }
182 return prev;
183}
184
1a41e743 185/* computes A\B */
bd22c904 186static void llist_sorted_difference_inplace(struct llist *A,
1a41e743
LS
187 struct llist *B)
188{
189 struct llist_item *hint, *b;
190
191 hint = NULL;
192 b = B->front;
193
194 while (b) {
195 hint = llist_sorted_remove(A, b->sha1, hint);
196 b = b->next;
197 }
198}
199
bd22c904 200static inline struct pack_list * pack_list_insert(struct pack_list **pl,
c283ab21
LS
201 struct pack_list *entry)
202{
203 struct pack_list *p = xmalloc(sizeof(struct pack_list));
204 memcpy(p, entry, sizeof(struct pack_list));
205 p->next = *pl;
206 *pl = p;
207 return p;
208}
209
bd22c904 210static inline size_t pack_list_size(struct pack_list *pl)
1c3039e8
LS
211{
212 size_t ret = 0;
213 while(pl) {
214 ret++;
215 pl = pl->next;
216 }
217 return ret;
218}
219
d1ab1577
AR
220static struct pack_list * pack_list_difference(const struct pack_list *A,
221 const struct pack_list *B)
c283ab21 222{
d1ab1577
AR
223 struct pack_list *ret;
224 const struct pack_list *pl;
c283ab21
LS
225
226 if (A == NULL)
227 return NULL;
228
229 pl = B;
230 while (pl != NULL) {
231 if (A->pack == pl->pack)
232 return pack_list_difference(A->next, B);
233 pl = pl->next;
234 }
235 ret = xmalloc(sizeof(struct pack_list));
236 memcpy(ret, A, sizeof(struct pack_list));
237 ret->next = pack_list_difference(A->next, B);
238 return ret;
239}
240
bd22c904 241static void cmp_two_packs(struct pack_list *p1, struct pack_list *p2)
c283ab21
LS
242{
243 int p1_off, p2_off;
244 void *p1_base, *p2_base;
245 struct llist_item *p1_hint = NULL, *p2_hint = NULL;
246
247 p1_off = p2_off = 256 * 4 + 4;
248 p1_base = (void *)p1->pack->index_base;
249 p2_base = (void *)p2->pack->index_base;
250
251 while (p1_off <= p1->pack->index_size - 3 * 20 &&
252 p2_off <= p2->pack->index_size - 3 * 20)
253 {
254 int cmp = memcmp(p1_base + p1_off, p2_base + p2_off, 20);
255 /* cmp ~ p1 - p2 */
256 if (cmp == 0) {
257 p1_hint = llist_sorted_remove(p1->unique_objects,
258 p1_base + p1_off, p1_hint);
259 p2_hint = llist_sorted_remove(p2->unique_objects,
260 p1_base + p1_off, p2_hint);
261 p1_off+=24;
262 p2_off+=24;
263 continue;
264 }
265 if (cmp < 0) { /* p1 has the object, p2 doesn't */
266 p1_off+=24;
267 } else { /* p2 has the object, p1 doesn't */
268 p2_off+=24;
269 }
270 }
271}
272
bd22c904 273static void pll_insert(struct pll **pll, struct pll **hint_table)
751a71e2
LS
274{
275 struct pll *prev;
276 int i = (*pll)->pl_size - 1;
277
278 if (hint_table[i] == NULL) {
279 hint_table[i--] = *pll;
280 for (; i >= 0; --i) {
281 if (hint_table[i] != NULL)
282 break;
283 }
284 if (hint_table[i] == NULL) /* no elements in list */
285 die("Why did this happen?");
286 }
287
288 prev = hint_table[i];
289 while (prev->next && prev->next->pl_size < (*pll)->pl_size)
290 prev = prev->next;
291
292 (*pll)->next = prev->next;
293 prev->next = *pll;
294}
295
c283ab21
LS
296/* all the permutations have to be free()d at the same time,
297 * since they refer to each other
298 */
bd22c904 299static struct pll * get_all_permutations(struct pack_list *list)
c283ab21
LS
300{
301 struct pll *subset, *pll, *new_pll = NULL; /*silence warning*/
751a71e2
LS
302 static struct pll **hint = NULL;
303 if (hint == NULL)
304 hint = xcalloc(pack_list_size(list), sizeof(struct pll *));
305
c283ab21
LS
306 if (list == NULL)
307 return NULL;
308
309 if (list->next == NULL) {
310 new_pll = xmalloc(sizeof(struct pll));
751a71e2 311 hint[0] = new_pll;
c283ab21
LS
312 new_pll->next = NULL;
313 new_pll->pl = list;
0cb022e0 314 new_pll->pl_size = 1;
c283ab21
LS
315 return new_pll;
316 }
317
318 pll = subset = get_all_permutations(list->next);
319 while (pll) {
751a71e2
LS
320 if (pll->pl->pack == list->pack) {
321 pll = pll->next;
322 continue;
323 }
c283ab21 324 new_pll = xmalloc(sizeof(struct pll));
c283ab21
LS
325
326 new_pll->pl = xmalloc(sizeof(struct pack_list));
327 memcpy(new_pll->pl, list, sizeof(struct pack_list));
328 new_pll->pl->next = pll->pl;
751a71e2
LS
329 new_pll->pl_size = pll->pl_size + 1;
330
331 pll_insert(&new_pll, hint);
c283ab21 332
751a71e2 333 pll = pll->next;
c283ab21 334 }
751a71e2
LS
335 /* add ourself */
336 new_pll = xmalloc(sizeof(struct pll));
337 new_pll->pl = xmalloc(sizeof(struct pack_list));
338 memcpy(new_pll->pl, list, sizeof(struct pack_list));
339 new_pll->pl->next = NULL;
340 new_pll->pl_size = 1;
341 pll_insert(&new_pll, hint);
342
343 return hint[0];
c283ab21
LS
344}
345
bd22c904 346static int is_superset(struct pack_list *pl, struct llist *list)
c283ab21 347{
1c3039e8 348 struct llist *diff;
c283ab21
LS
349
350 diff = llist_copy(list);
351
352 while (pl) {
d1ab1577 353 llist_sorted_difference_inplace(diff, pl->all_objects);
c283ab21
LS
354 if (diff->size == 0) { /* we're done */
355 llist_free(diff);
356 return 1;
357 }
358 pl = pl->next;
359 }
360 llist_free(diff);
361 return 0;
362}
363
bd22c904 364static size_t sizeof_union(struct packed_git *p1, struct packed_git *p2)
c283ab21
LS
365{
366 size_t ret = 0;
367 int p1_off, p2_off;
368 void *p1_base, *p2_base;
369
370 p1_off = p2_off = 256 * 4 + 4;
371 p1_base = (void *)p1->index_base;
372 p2_base = (void *)p2->index_base;
373
374 while (p1_off <= p1->index_size - 3 * 20 &&
375 p2_off <= p2->index_size - 3 * 20)
376 {
377 int cmp = memcmp(p1_base + p1_off, p2_base + p2_off, 20);
378 /* cmp ~ p1 - p2 */
379 if (cmp == 0) {
380 ret++;
381 p1_off+=24;
382 p2_off+=24;
383 continue;
384 }
385 if (cmp < 0) { /* p1 has the object, p2 doesn't */
386 p1_off+=24;
387 } else { /* p2 has the object, p1 doesn't */
388 p2_off+=24;
389 }
390 }
391 return ret;
392}
393
394/* another O(n^2) function ... */
bd22c904 395static size_t get_pack_redundancy(struct pack_list *pl)
c283ab21
LS
396{
397 struct pack_list *subset;
bd22c904 398 size_t ret = 0;
1c3039e8
LS
399
400 if (pl == NULL)
401 return 0;
402
c283ab21
LS
403 while ((subset = pl->next)) {
404 while(subset) {
405 ret += sizeof_union(pl->pack, subset->pack);
406 subset = subset->next;
407 }
408 pl = pl->next;
409 }
410 return ret;
411}
412
bd22c904 413static inline size_t pack_set_bytecount(struct pack_list *pl)
c283ab21
LS
414{
415 size_t ret = 0;
416 while (pl) {
417 ret += pl->pack->pack_size;
418 ret += pl->pack->index_size;
419 pl = pl->next;
420 }
421 return ret;
422}
423
bd22c904 424static void minimize(struct pack_list **min)
c283ab21
LS
425{
426 struct pack_list *pl, *unique = NULL,
427 *non_unique = NULL, *min_perm = NULL;
428 struct pll *perm, *perm_all, *perm_ok = NULL, *new_perm;
1c3039e8 429 struct llist *missing;
c283ab21
LS
430 size_t min_perm_size = (size_t)-1, perm_size;
431
1c3039e8 432 pl = local_packs;
c283ab21
LS
433 while (pl) {
434 if(pl->unique_objects->size)
435 pack_list_insert(&unique, pl);
436 else
437 pack_list_insert(&non_unique, pl);
438 pl = pl->next;
439 }
440 /* find out which objects are missing from the set of unique packs */
441 missing = llist_copy(all_objects);
442 pl = unique;
443 while (pl) {
1c3039e8
LS
444 llist_sorted_difference_inplace(missing,
445 pl->all_objects);
c283ab21
LS
446 pl = pl->next;
447 }
448
1c3039e8 449 /* return if there are no objects missing from the unique set */
c283ab21
LS
450 if (missing->size == 0) {
451 *min = unique;
452 return;
453 }
454
455 /* find the permutations which contain all missing objects */
456 perm_all = perm = get_all_permutations(non_unique);
457 while (perm) {
751a71e2
LS
458 if (perm_ok && perm->pl_size > perm_ok->pl_size)
459 break; /* ignore all larger permutations */
c283ab21
LS
460 if (is_superset(perm->pl, missing)) {
461 new_perm = xmalloc(sizeof(struct pll));
3afd1694 462 memcpy(new_perm, perm, sizeof(struct pll));
c283ab21
LS
463 new_perm->next = perm_ok;
464 perm_ok = new_perm;
465 }
466 perm = perm->next;
467 }
468
469 if (perm_ok == NULL)
470 die("Internal error: No complete sets found!\n");
471
472 /* find the permutation with the smallest size */
473 perm = perm_ok;
474 while (perm) {
475 perm_size = pack_set_bytecount(perm->pl);
476 if (min_perm_size > perm_size) {
477 min_perm_size = perm_size;
478 min_perm = perm->pl;
479 }
480 perm = perm->next;
481 }
482 *min = min_perm;
483 /* add the unique packs to the list */
484 pl = unique;
485 while(pl) {
486 pack_list_insert(min, pl);
487 pl = pl->next;
488 }
489}
490
bd22c904 491static void load_all_objects(void)
c283ab21 492{
1c3039e8 493 struct pack_list *pl = local_packs;
c283ab21 494 struct llist_item *hint, *l;
c283ab21
LS
495
496 llist_init(&all_objects);
497
498 while (pl) {
c283ab21
LS
499 hint = NULL;
500 l = pl->all_objects->front;
501 while (l) {
502 hint = llist_insert_sorted_unique(all_objects,
503 l->sha1, hint);
504 l = l->next;
505 }
506 pl = pl->next;
507 }
1c3039e8
LS
508 /* remove objects present in remote packs */
509 pl = altodb_packs;
510 while (pl) {
511 llist_sorted_difference_inplace(all_objects, pl->all_objects);
512 pl = pl->next;
513 }
c283ab21
LS
514}
515
516/* this scales like O(n^2) */
bd22c904 517static void cmp_local_packs(void)
c283ab21 518{
1c3039e8 519 struct pack_list *subset, *pl = local_packs;
c283ab21 520
1c3039e8 521 while ((subset = pl)) {
c283ab21 522 while((subset = subset->next))
1c3039e8
LS
523 cmp_two_packs(pl, subset);
524 pl = pl->next;
525 }
06a45c8c 526}
1c3039e8 527
bd22c904 528static void scan_alt_odb_packs(void)
06a45c8c
LS
529{
530 struct pack_list *local, *alt;
531
532 alt = altodb_packs;
533 while (alt) {
534 local = local_packs;
535 while (local) {
536 llist_sorted_difference_inplace(local->unique_objects,
537 alt->all_objects);
538 local = local->next;
1c3039e8 539 }
06a45c8c 540 alt = alt->next;
c283ab21
LS
541 }
542}
543
bd22c904 544static struct pack_list * add_pack(struct packed_git *p)
c283ab21
LS
545{
546 struct pack_list l;
547 size_t off;
548 void *base;
549
06a45c8c
LS
550 if (!p->pack_local && !(alt_odb || verbose))
551 return NULL;
552
c283ab21
LS
553 l.pack = p;
554 llist_init(&l.all_objects);
555
556 off = 256 * 4 + 4;
557 base = (void *)p->index_base;
558 while (off <= p->index_size - 3 * 20) {
559 llist_insert_back(l.all_objects, base + off);
06a45c8c 560 off += 24;
c283ab21
LS
561 }
562 /* this list will be pruned in cmp_two_packs later */
563 l.unique_objects = llist_copy(l.all_objects);
1c3039e8
LS
564 if (p->pack_local)
565 return pack_list_insert(&local_packs, &l);
566 else
06a45c8c 567 return pack_list_insert(&altodb_packs, &l);
c283ab21
LS
568}
569
bd22c904 570static struct pack_list * add_pack_file(char *filename)
c283ab21
LS
571{
572 struct packed_git *p = packed_git;
573
574 if (strlen(filename) < 40)
575 die("Bad pack filename: %s\n", filename);
576
577 while (p) {
578 if (strstr(p->pack_name, filename))
c283ab21
LS
579 return add_pack(p);
580 p = p->next;
581 }
582 die("Filename %s not found in packed_git\n", filename);
583}
584
bd22c904 585static void load_all(void)
c283ab21
LS
586{
587 struct packed_git *p = packed_git;
588
589 while (p) {
1c3039e8 590 add_pack(p);
c283ab21
LS
591 p = p->next;
592 }
593}
594
595int main(int argc, char **argv)
596{
597 int i;
598 struct pack_list *min, *red, *pl;
bb931cf9 599 struct llist *ignore;
b99a394c
JH
600 unsigned char *sha1;
601 char buf[42]; /* 40 byte sha1 + \n + \0 */
c283ab21 602
53228a5f
JH
603 setup_git_directory();
604
c283ab21
LS
605 for (i = 1; i < argc; i++) {
606 const char *arg = argv[i];
9bc0f32c
LS
607 if(!strcmp(arg, "--")) {
608 i++;
c283ab21 609 break;
9bc0f32c 610 }
1c3039e8
LS
611 if(!strcmp(arg, "--all")) {
612 load_all_packs = 1;
c283ab21
LS
613 continue;
614 }
1c3039e8 615 if(!strcmp(arg, "--verbose")) {
c283ab21
LS
616 verbose = 1;
617 continue;
618 }
1c3039e8
LS
619 if(!strcmp(arg, "--alt-odb")) {
620 alt_odb = 1;
621 continue;
622 }
c283ab21 623 if(*arg == '-')
9bc0f32c 624 usage(pack_redundant_usage);
c283ab21
LS
625 else
626 break;
627 }
628
629 prepare_packed_git();
630
1c3039e8 631 if (load_all_packs)
c283ab21
LS
632 load_all();
633 else
634 while (*(argv + i) != NULL)
635 add_pack_file(*(argv + i++));
636
1c3039e8 637 if (local_packs == NULL)
c283ab21
LS
638 die("Zero packs found!\n");
639
c283ab21
LS
640 load_all_objects();
641
06a45c8c
LS
642 cmp_local_packs();
643 if (alt_odb)
644 scan_alt_odb_packs();
645
bb931cf9
LS
646 /* ignore objects given on stdin */
647 llist_init(&ignore);
648 if (!isatty(0)) {
649 while (fgets(buf, sizeof(buf), stdin)) {
650 sha1 = xmalloc(20);
651 if (get_sha1_hex(buf, sha1))
652 die("Bad sha1 on stdin: %s", buf);
653 llist_insert_sorted_unique(ignore, sha1, NULL);
654 }
655 }
656 llist_sorted_difference_inplace(all_objects, ignore);
657 pl = local_packs;
658 while (pl) {
659 llist_sorted_difference_inplace(pl->unique_objects, ignore);
660 pl = pl->next;
661 }
662
c283ab21 663 minimize(&min);
06a45c8c 664
c283ab21 665 if (verbose) {
abacbe41
KR
666 fprintf(stderr, "There are %lu packs available in alt-odbs.\n",
667 (unsigned long)pack_list_size(altodb_packs));
c283ab21
LS
668 fprintf(stderr, "The smallest (bytewise) set of packs is:\n");
669 pl = min;
670 while (pl) {
671 fprintf(stderr, "\t%s\n", pl->pack->pack_name);
672 pl = pl->next;
673 }
abacbe41
KR
674 fprintf(stderr, "containing %lu duplicate objects "
675 "with a total size of %lukb.\n",
676 (unsigned long)get_pack_redundancy(min),
677 (unsigned long)pack_set_bytecount(min)/1024);
678 fprintf(stderr, "A total of %lu unique objects were considered.\n",
679 (unsigned long)all_objects->size);
c283ab21
LS
680 fprintf(stderr, "Redundant packs (with indexes):\n");
681 }
1c3039e8 682 pl = red = pack_list_difference(local_packs, min);
c283ab21
LS
683 while (pl) {
684 printf("%s\n%s\n",
1c3039e8
LS
685 sha1_pack_index_name(pl->pack->sha1),
686 pl->pack->pack_name);
c283ab21
LS
687 pl = pl->next;
688 }
bb931cf9 689 if (verbose)
b99a394c
JH
690 fprintf(stderr, "%luMB of redundant packs in total.\n",
691 (unsigned long)pack_set_bytecount(red)/(1024*1024));
c283ab21
LS
692
693 return 0;
694}