59375f1b9781b81c8567dd281a3d9385c3bf09a7
   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
  11static const char pack_redundant_usage[] =
  12"git-pack-redundant [ --verbose ] [ --alt-odb ] < --all | <.pack filename> ...>";
  13
  14static int load_all_packs = 0, verbose = 0, alt_odb = 0;
  15
  16struct llist_item {
  17        struct llist_item *next;
  18        char *sha1;
  19};
  20static struct llist {
  21        struct llist_item *front;
  22        struct llist_item *back;
  23        size_t size;
  24} *all_objects; /* all objects which must be present in local packfiles */
  25
  26static struct pack_list {
  27        struct pack_list *next;
  28        struct packed_git *pack;
  29        struct llist *unique_objects;
  30        struct llist *all_objects;
  31} *local_packs = NULL, *altodb_packs = NULL;
  32
  33struct pll {
  34        struct pll *next;
  35        struct pack_list *pl;
  36        size_t pl_size;
  37};
  38
  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)
  60{
  61        while((list->back = list->front)) {
  62                list->front = list->front->next;
  63                llist_item_put(list->back);
  64        }
  65        free(list);
  66}
  67
  68static inline void llist_init(struct llist **list)
  69{
  70        *list = xmalloc(sizeof(struct llist));
  71        (*list)->front = (*list)->back = NULL;
  72        (*list)->size = 0;
  73}
  74
  75static struct llist * llist_copy(struct llist *list)
  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
  85        new = ret->front = llist_item_get();
  86        new->sha1 = list->front->sha1;
  87
  88        old = list->front->next;
  89        while (old) {
  90                prev = new;
  91                new = llist_item_get();
  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
 102static inline struct llist_item * llist_insert(struct llist *list,
 103                                        struct llist_item *after, char *sha1)
 104{
 105        struct llist_item *new = llist_item_get();
 106        new->sha1 = sha1;
 107        new->next = NULL;
 108
 109        if (after != NULL) {
 110                new->next = after->next;
 111                after->next = new;
 112                if (after == list->back)
 113                        list->back = new;
 114        } else {/* insert in front */
 115                if (list->size == 0)
 116                        list->back = new;
 117                else
 118                        new->next = list->front;
 119                list->front = new;
 120        }
 121        list->size++;
 122        return new;
 123}
 124
 125static inline struct llist_item * llist_insert_back(struct llist *list, char *sha1)
 126{
 127        return llist_insert(list, list->back, sha1);
 128}
 129
 130static inline struct llist_item * llist_insert_sorted_unique(struct llist *list,
 131                                        char *sha1, struct llist_item *hint)
 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
 151/* returns a pointer to an item in front of sha1 */
 152static inline struct llist_item * llist_sorted_remove(struct llist *list, char *sha1,
 153                                               struct llist_item *hint)
 154{
 155        struct llist_item *prev, *l;
 156
 157redo_from_start:
 158        l = (hint == NULL) ? list->front : hint;
 159        prev = NULL;
 160        while (l) {
 161                int cmp = memcmp(l->sha1, sha1, 20);
 162                if (cmp > 0) /* not in list, since sorted */
 163                        return prev;
 164                if(!cmp) { /* found */
 165                        if (prev == NULL) {
 166                                if (hint != NULL && hint != list->front) {
 167                                        /* we don't know the previous element */
 168                                        hint = NULL;
 169                                        goto redo_from_start;
 170                                }
 171                                list->front = l->next;
 172                        } else
 173                                prev->next = l->next;
 174                        if (l == list->back)
 175                                list->back = prev;
 176                        llist_item_put(l);
 177                        list->size--;
 178                        return prev;
 179                }
 180                prev = l;
 181                l = l->next;
 182        }
 183        return prev;
 184}
 185
 186/* computes A\B */
 187static void llist_sorted_difference_inplace(struct llist *A,
 188                                     struct llist *B)
 189{
 190        struct llist_item *hint, *b;
 191
 192        hint = NULL;
 193        b = B->front;
 194
 195        while (b) {
 196                hint = llist_sorted_remove(A, b->sha1, hint);
 197                b = b->next;
 198        }
 199}
 200
 201static inline struct pack_list * pack_list_insert(struct pack_list **pl,
 202                                           struct pack_list *entry)
 203{
 204        struct pack_list *p = xmalloc(sizeof(struct pack_list));
 205        memcpy(p, entry, sizeof(struct pack_list));
 206        p->next = *pl;
 207        *pl = p;
 208        return p;
 209}
 210
 211static inline size_t pack_list_size(struct pack_list *pl)
 212{
 213        size_t ret = 0;
 214        while(pl) {
 215                ret++;
 216                pl = pl->next;
 217        }
 218        return ret;
 219}
 220
 221static struct pack_list * pack_list_difference(struct pack_list *A,
 222                                        struct pack_list *B)
 223{
 224        struct pack_list *ret, *pl;
 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
 241static void cmp_two_packs(struct pack_list *p1, struct pack_list *p2)
 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
 273static void pll_insert(struct pll **pll, struct pll **hint_table)
 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
 296/* all the permutations have to be free()d at the same time,
 297 * since they refer to each other
 298 */
 299static struct pll * get_all_permutations(struct pack_list *list)
 300{
 301        struct pll *subset, *pll, *new_pll = NULL; /*silence warning*/
 302        static struct pll **hint = NULL;
 303        if (hint == NULL)
 304                hint = xcalloc(pack_list_size(list), sizeof(struct pll *));
 305                
 306        if (list == NULL)
 307                return NULL;
 308
 309        if (list->next == NULL) {
 310                new_pll = xmalloc(sizeof(struct pll));
 311                hint[0] = new_pll;
 312                new_pll->next = NULL;
 313                new_pll->pl = list;
 314                new_pll->pl_size = 1;
 315                return new_pll;
 316        }
 317
 318        pll = subset = get_all_permutations(list->next);
 319        while (pll) {
 320                if (pll->pl->pack == list->pack) {
 321                        pll = pll->next;
 322                        continue;
 323                }
 324                new_pll = xmalloc(sizeof(struct pll));
 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;
 329                new_pll->pl_size = pll->pl_size + 1;
 330                
 331                pll_insert(&new_pll, hint);
 332
 333                pll = pll->next;
 334        }
 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];
 344}
 345
 346static int is_superset(struct pack_list *pl, struct llist *list)
 347{
 348        struct llist *diff;
 349
 350        diff = llist_copy(list);
 351
 352        while (pl) {
 353                llist_sorted_difference_inplace(diff,
 354                                                pl->all_objects);
 355                if (diff->size == 0) { /* we're done */
 356                        llist_free(diff);
 357                        return 1;
 358                }
 359                pl = pl->next;
 360        }
 361        llist_free(diff);
 362        return 0;
 363}
 364
 365static size_t sizeof_union(struct packed_git *p1, struct packed_git *p2)
 366{
 367        size_t ret = 0;
 368        int p1_off, p2_off;
 369        void *p1_base, *p2_base;
 370
 371        p1_off = p2_off = 256 * 4 + 4;
 372        p1_base = (void *)p1->index_base;
 373        p2_base = (void *)p2->index_base;
 374
 375        while (p1_off <= p1->index_size - 3 * 20 &&
 376               p2_off <= p2->index_size - 3 * 20)
 377        {
 378                int cmp = memcmp(p1_base + p1_off, p2_base + p2_off, 20);
 379                /* cmp ~ p1 - p2 */
 380                if (cmp == 0) {
 381                        ret++;
 382                        p1_off+=24;
 383                        p2_off+=24;
 384                        continue;
 385                }
 386                if (cmp < 0) { /* p1 has the object, p2 doesn't */
 387                        p1_off+=24;
 388                } else { /* p2 has the object, p1 doesn't */
 389                        p2_off+=24;
 390                }
 391        }
 392        return ret;
 393}
 394
 395/* another O(n^2) function ... */
 396static size_t get_pack_redundancy(struct pack_list *pl)
 397{
 398        struct pack_list *subset;
 399        size_t ret = 0;
 400
 401        if (pl == NULL)
 402                return 0;
 403
 404        while ((subset = pl->next)) {
 405                while(subset) {
 406                        ret += sizeof_union(pl->pack, subset->pack);
 407                        subset = subset->next;
 408                }
 409                pl = pl->next;
 410        }
 411        return ret;
 412}
 413
 414static inline size_t pack_set_bytecount(struct pack_list *pl)
 415{
 416        size_t ret = 0;
 417        while (pl) {
 418                ret += pl->pack->pack_size;
 419                ret += pl->pack->index_size;
 420                pl = pl->next;
 421        }
 422        return ret;
 423}
 424
 425static void minimize(struct pack_list **min)
 426{
 427        struct pack_list *pl, *unique = NULL,
 428                *non_unique = NULL, *min_perm = NULL;
 429        struct pll *perm, *perm_all, *perm_ok = NULL, *new_perm;
 430        struct llist *missing;
 431        size_t min_perm_size = (size_t)-1, perm_size;
 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,
 446                                                pl->all_objects);
 447                pl = pl->next;
 448        }
 449
 450        /* return if there are no objects missing from the unique set */
 451        if (missing->size == 0) {
 452                *min = unique;
 453                return;
 454        }
 455
 456        /* find the permutations which contain all missing objects */
 457        perm_all = perm = get_all_permutations(non_unique);
 458        while (perm) {
 459                if (perm_ok && perm->pl_size > perm_ok->pl_size)
 460                        break; /* ignore all larger permutations */
 461                if (is_superset(perm->pl, missing)) {
 462                        new_perm = xmalloc(sizeof(struct pll));
 463                        memcpy(new_perm, perm, sizeof(struct pll));
 464                        new_perm->next = perm_ok;
 465                        perm_ok = new_perm;
 466                }
 467                perm = perm->next;
 468        }
 469        
 470        if (perm_ok == NULL)
 471                die("Internal error: No complete sets found!\n");
 472
 473        /* find the permutation with the smallest size */
 474        perm = perm_ok;
 475        while (perm) {
 476                perm_size = pack_set_bytecount(perm->pl);
 477                if (min_perm_size > perm_size) {
 478                        min_perm_size = perm_size;
 479                        min_perm = perm->pl;
 480                }
 481                perm = perm->next;
 482        }
 483        *min = min_perm;
 484        /* add the unique packs to the list */
 485        pl = unique;
 486        while(pl) {
 487                pack_list_insert(min, pl);
 488                pl = pl->next;
 489        }
 490}
 491
 492static void load_all_objects(void)
 493{
 494        struct pack_list *pl = local_packs;
 495        struct llist_item *hint, *l;
 496
 497        llist_init(&all_objects);
 498
 499        while (pl) {
 500                hint = NULL;
 501                l = pl->all_objects->front;
 502                while (l) {
 503                        hint = llist_insert_sorted_unique(all_objects,
 504                                                          l->sha1, hint);
 505                        l = l->next;
 506                }
 507                pl = pl->next;
 508        }
 509        /* remove objects present in remote packs */
 510        pl = altodb_packs;
 511        while (pl) {
 512                llist_sorted_difference_inplace(all_objects, pl->all_objects);
 513                pl = pl->next;
 514        }
 515}
 516
 517/* this scales like O(n^2) */
 518static void cmp_local_packs(void)
 519{
 520        struct pack_list *subset, *pl = local_packs;
 521
 522        while ((subset = pl)) {
 523                while((subset = subset->next))
 524                        cmp_two_packs(pl, subset);
 525                pl = pl->next;
 526        }
 527}
 528
 529static void scan_alt_odb_packs(void)
 530{
 531        struct pack_list *local, *alt;
 532
 533        alt = altodb_packs;
 534        while (alt) {
 535                local = local_packs;
 536                while (local) {
 537                        llist_sorted_difference_inplace(local->unique_objects,
 538                                                        alt->all_objects);
 539                        local = local->next;
 540                }
 541                alt = alt->next;
 542        }
 543}
 544
 545static struct pack_list * add_pack(struct packed_git *p)
 546{
 547        struct pack_list l;
 548        size_t off;
 549        void *base;
 550
 551        if (!p->pack_local && !(alt_odb || verbose))
 552                return NULL;
 553
 554        l.pack = p;
 555        llist_init(&l.all_objects);
 556
 557        off = 256 * 4 + 4;
 558        base = (void *)p->index_base;
 559        while (off <= p->index_size - 3 * 20) {
 560                llist_insert_back(l.all_objects, base + off);
 561                off += 24;
 562        }
 563        /* this list will be pruned in cmp_two_packs later */
 564        l.unique_objects = llist_copy(l.all_objects);
 565        if (p->pack_local)
 566                return pack_list_insert(&local_packs, &l);
 567        else
 568                return pack_list_insert(&altodb_packs, &l);
 569}
 570
 571static struct pack_list * add_pack_file(char *filename)
 572{
 573        struct packed_git *p = packed_git;
 574
 575        if (strlen(filename) < 40)
 576                die("Bad pack filename: %s\n", filename);
 577
 578        while (p) {
 579                if (strstr(p->pack_name, filename))
 580                        return add_pack(p);
 581                p = p->next;
 582        }
 583        die("Filename %s not found in packed_git\n", filename);
 584}
 585
 586static void load_all(void)
 587{
 588        struct packed_git *p = packed_git;
 589
 590        while (p) {
 591                add_pack(p);
 592                p = p->next;
 593        }
 594}
 595
 596int main(int argc, char **argv)
 597{
 598        int i;
 599        struct pack_list *min, *red, *pl;
 600        struct llist *ignore;
 601        char *sha1, buf[42]; /* 40 byte sha1 + \n + \0 */
 602
 603        for (i = 1; i < argc; i++) {
 604                const char *arg = argv[i];
 605                if(!strcmp(arg, "--")) {
 606                        i++;
 607                        break;
 608                }
 609                if(!strcmp(arg, "--all")) {
 610                        load_all_packs = 1;
 611                        continue;
 612                }
 613                if(!strcmp(arg, "--verbose")) {
 614                        verbose = 1;
 615                        continue;
 616                }
 617                if(!strcmp(arg, "--alt-odb")) {
 618                        alt_odb = 1;
 619                        continue;
 620                }
 621                if(*arg == '-')
 622                        usage(pack_redundant_usage);
 623                else
 624                        break;
 625        }
 626
 627        prepare_packed_git();
 628
 629        if (load_all_packs)
 630                load_all();
 631        else
 632                while (*(argv + i) != NULL)
 633                        add_pack_file(*(argv + i++));
 634
 635        if (local_packs == NULL)
 636                die("Zero packs found!\n");
 637
 638        load_all_objects();
 639
 640        cmp_local_packs();
 641        if (alt_odb)
 642                scan_alt_odb_packs();
 643
 644        /* ignore objects given on stdin */
 645        llist_init(&ignore);
 646        if (!isatty(0)) {
 647                while (fgets(buf, sizeof(buf), stdin)) {
 648                        sha1 = xmalloc(20);
 649                        if (get_sha1_hex(buf, sha1))
 650                                die("Bad sha1 on stdin: %s", buf);
 651                        llist_insert_sorted_unique(ignore, sha1, NULL);
 652                }
 653        }
 654        llist_sorted_difference_inplace(all_objects, ignore);
 655        pl = local_packs;
 656        while (pl) {
 657                llist_sorted_difference_inplace(pl->unique_objects, ignore);
 658                pl = pl->next;
 659        }
 660
 661        minimize(&min);
 662
 663        if (verbose) {
 664                fprintf(stderr, "There are %lu packs available in alt-odbs.\n",
 665                        (unsigned long)pack_list_size(altodb_packs));
 666                fprintf(stderr, "The smallest (bytewise) set of packs is:\n");
 667                pl = min;
 668                while (pl) {
 669                        fprintf(stderr, "\t%s\n", pl->pack->pack_name);
 670                        pl = pl->next;
 671                }
 672                fprintf(stderr, "containing %lu duplicate objects "
 673                                "with a total size of %lukb.\n",
 674                        (unsigned long)get_pack_redundancy(min),
 675                        (unsigned long)pack_set_bytecount(min)/1024);
 676                fprintf(stderr, "A total of %lu unique objects were considered.\n",
 677                        (unsigned long)all_objects->size);
 678                fprintf(stderr, "Redundant packs (with indexes):\n");
 679        }
 680        pl = red = pack_list_difference(local_packs, min);
 681        while (pl) {
 682                printf("%s\n%s\n",
 683                       sha1_pack_index_name(pl->pack->sha1),
 684                       pl->pack->pack_name);
 685                pl = pl->next;
 686        }
 687        if (verbose)
 688                fprintf(stderr, "%luMB of redundant packs in total.\n", pack_set_bytecount(red)/(1024*1024));
 689
 690        return 0;
 691}