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