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