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