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