pack-bitmap.con commit Merge branch 'er/fast-import-dump-refs-on-checkpoint' (29a67cc)
   1#include "cache.h"
   2#include "commit.h"
   3#include "tag.h"
   4#include "diff.h"
   5#include "revision.h"
   6#include "progress.h"
   7#include "list-objects.h"
   8#include "pack.h"
   9#include "pack-bitmap.h"
  10#include "pack-revindex.h"
  11#include "pack-objects.h"
  12#include "packfile.h"
  13
  14/*
  15 * An entry on the bitmap index, representing the bitmap for a given
  16 * commit.
  17 */
  18struct stored_bitmap {
  19        unsigned char sha1[20];
  20        struct ewah_bitmap *root;
  21        struct stored_bitmap *xor;
  22        int flags;
  23};
  24
  25/*
  26 * The currently active bitmap index. By design, repositories only have
  27 * a single bitmap index available (the index for the biggest packfile in
  28 * the repository), since bitmap indexes need full closure.
  29 *
  30 * If there is more than one bitmap index available (e.g. because of alternates),
  31 * the active bitmap index is the largest one.
  32 */
  33static struct bitmap_index {
  34        /* Packfile to which this bitmap index belongs to */
  35        struct packed_git *pack;
  36
  37        /*
  38         * Mark the first `reuse_objects` in the packfile as reused:
  39         * they will be sent as-is without using them for repacking
  40         * calculations
  41         */
  42        uint32_t reuse_objects;
  43
  44        /* mmapped buffer of the whole bitmap index */
  45        unsigned char *map;
  46        size_t map_size; /* size of the mmaped buffer */
  47        size_t map_pos; /* current position when loading the index */
  48
  49        /*
  50         * Type indexes.
  51         *
  52         * Each bitmap marks which objects in the packfile  are of the given
  53         * type. This provides type information when yielding the objects from
  54         * the packfile during a walk, which allows for better delta bases.
  55         */
  56        struct ewah_bitmap *commits;
  57        struct ewah_bitmap *trees;
  58        struct ewah_bitmap *blobs;
  59        struct ewah_bitmap *tags;
  60
  61        /* Map from SHA1 -> `stored_bitmap` for all the bitmapped commits */
  62        khash_sha1 *bitmaps;
  63
  64        /* Number of bitmapped commits */
  65        uint32_t entry_count;
  66
  67        /* Name-hash cache (or NULL if not present). */
  68        uint32_t *hashes;
  69
  70        /*
  71         * Extended index.
  72         *
  73         * When trying to perform bitmap operations with objects that are not
  74         * packed in `pack`, these objects are added to this "fake index" and
  75         * are assumed to appear at the end of the packfile for all operations
  76         */
  77        struct eindex {
  78                struct object **objects;
  79                uint32_t *hashes;
  80                uint32_t count, alloc;
  81                khash_sha1_pos *positions;
  82        } ext_index;
  83
  84        /* Bitmap result of the last performed walk */
  85        struct bitmap *result;
  86
  87        /* Version of the bitmap index */
  88        unsigned int version;
  89
  90        unsigned loaded : 1;
  91
  92} bitmap_git;
  93
  94static struct ewah_bitmap *lookup_stored_bitmap(struct stored_bitmap *st)
  95{
  96        struct ewah_bitmap *parent;
  97        struct ewah_bitmap *composed;
  98
  99        if (st->xor == NULL)
 100                return st->root;
 101
 102        composed = ewah_pool_new();
 103        parent = lookup_stored_bitmap(st->xor);
 104        ewah_xor(st->root, parent, composed);
 105
 106        ewah_pool_free(st->root);
 107        st->root = composed;
 108        st->xor = NULL;
 109
 110        return composed;
 111}
 112
 113/*
 114 * Read a bitmap from the current read position on the mmaped
 115 * index, and increase the read position accordingly
 116 */
 117static struct ewah_bitmap *read_bitmap_1(struct bitmap_index *index)
 118{
 119        struct ewah_bitmap *b = ewah_pool_new();
 120
 121        int bitmap_size = ewah_read_mmap(b,
 122                index->map + index->map_pos,
 123                index->map_size - index->map_pos);
 124
 125        if (bitmap_size < 0) {
 126                error("Failed to load bitmap index (corrupted?)");
 127                ewah_pool_free(b);
 128                return NULL;
 129        }
 130
 131        index->map_pos += bitmap_size;
 132        return b;
 133}
 134
 135static int load_bitmap_header(struct bitmap_index *index)
 136{
 137        struct bitmap_disk_header *header = (void *)index->map;
 138
 139        if (index->map_size < sizeof(*header) + 20)
 140                return error("Corrupted bitmap index (missing header data)");
 141
 142        if (memcmp(header->magic, BITMAP_IDX_SIGNATURE, sizeof(BITMAP_IDX_SIGNATURE)) != 0)
 143                return error("Corrupted bitmap index file (wrong header)");
 144
 145        index->version = ntohs(header->version);
 146        if (index->version != 1)
 147                return error("Unsupported version for bitmap index file (%d)", index->version);
 148
 149        /* Parse known bitmap format options */
 150        {
 151                uint32_t flags = ntohs(header->options);
 152
 153                if ((flags & BITMAP_OPT_FULL_DAG) == 0)
 154                        return error("Unsupported options for bitmap index file "
 155                                "(Git requires BITMAP_OPT_FULL_DAG)");
 156
 157                if (flags & BITMAP_OPT_HASH_CACHE) {
 158                        unsigned char *end = index->map + index->map_size - 20;
 159                        index->hashes = ((uint32_t *)end) - index->pack->num_objects;
 160                }
 161        }
 162
 163        index->entry_count = ntohl(header->entry_count);
 164        index->map_pos += sizeof(*header);
 165        return 0;
 166}
 167
 168static struct stored_bitmap *store_bitmap(struct bitmap_index *index,
 169                                          struct ewah_bitmap *root,
 170                                          const unsigned char *sha1,
 171                                          struct stored_bitmap *xor_with,
 172                                          int flags)
 173{
 174        struct stored_bitmap *stored;
 175        khiter_t hash_pos;
 176        int ret;
 177
 178        stored = xmalloc(sizeof(struct stored_bitmap));
 179        stored->root = root;
 180        stored->xor = xor_with;
 181        stored->flags = flags;
 182        hashcpy(stored->sha1, sha1);
 183
 184        hash_pos = kh_put_sha1(index->bitmaps, stored->sha1, &ret);
 185
 186        /* a 0 return code means the insertion succeeded with no changes,
 187         * because the SHA1 already existed on the map. this is bad, there
 188         * shouldn't be duplicated commits in the index */
 189        if (ret == 0) {
 190                error("Duplicate entry in bitmap index: %s", sha1_to_hex(sha1));
 191                return NULL;
 192        }
 193
 194        kh_value(index->bitmaps, hash_pos) = stored;
 195        return stored;
 196}
 197
 198static inline uint32_t read_be32(const unsigned char *buffer, size_t *pos)
 199{
 200        uint32_t result = get_be32(buffer + *pos);
 201        (*pos) += sizeof(result);
 202        return result;
 203}
 204
 205static inline uint8_t read_u8(const unsigned char *buffer, size_t *pos)
 206{
 207        return buffer[(*pos)++];
 208}
 209
 210#define MAX_XOR_OFFSET 160
 211
 212static int load_bitmap_entries_v1(struct bitmap_index *index)
 213{
 214        uint32_t i;
 215        struct stored_bitmap *recent_bitmaps[MAX_XOR_OFFSET] = { NULL };
 216
 217        for (i = 0; i < index->entry_count; ++i) {
 218                int xor_offset, flags;
 219                struct ewah_bitmap *bitmap = NULL;
 220                struct stored_bitmap *xor_bitmap = NULL;
 221                uint32_t commit_idx_pos;
 222                const unsigned char *sha1;
 223
 224                commit_idx_pos = read_be32(index->map, &index->map_pos);
 225                xor_offset = read_u8(index->map, &index->map_pos);
 226                flags = read_u8(index->map, &index->map_pos);
 227
 228                sha1 = nth_packed_object_sha1(index->pack, commit_idx_pos);
 229
 230                bitmap = read_bitmap_1(index);
 231                if (!bitmap)
 232                        return -1;
 233
 234                if (xor_offset > MAX_XOR_OFFSET || xor_offset > i)
 235                        return error("Corrupted bitmap pack index");
 236
 237                if (xor_offset > 0) {
 238                        xor_bitmap = recent_bitmaps[(i - xor_offset) % MAX_XOR_OFFSET];
 239
 240                        if (xor_bitmap == NULL)
 241                                return error("Invalid XOR offset in bitmap pack index");
 242                }
 243
 244                recent_bitmaps[i % MAX_XOR_OFFSET] = store_bitmap(
 245                        index, bitmap, sha1, xor_bitmap, flags);
 246        }
 247
 248        return 0;
 249}
 250
 251static char *pack_bitmap_filename(struct packed_git *p)
 252{
 253        size_t len;
 254
 255        if (!strip_suffix(p->pack_name, ".pack", &len))
 256                die("BUG: pack_name does not end in .pack");
 257        return xstrfmt("%.*s.bitmap", (int)len, p->pack_name);
 258}
 259
 260static int open_pack_bitmap_1(struct packed_git *packfile)
 261{
 262        int fd;
 263        struct stat st;
 264        char *idx_name;
 265
 266        if (open_pack_index(packfile))
 267                return -1;
 268
 269        idx_name = pack_bitmap_filename(packfile);
 270        fd = git_open(idx_name);
 271        free(idx_name);
 272
 273        if (fd < 0)
 274                return -1;
 275
 276        if (fstat(fd, &st)) {
 277                close(fd);
 278                return -1;
 279        }
 280
 281        if (bitmap_git.pack) {
 282                warning("ignoring extra bitmap file: %s", packfile->pack_name);
 283                close(fd);
 284                return -1;
 285        }
 286
 287        bitmap_git.pack = packfile;
 288        bitmap_git.map_size = xsize_t(st.st_size);
 289        bitmap_git.map = xmmap(NULL, bitmap_git.map_size, PROT_READ, MAP_PRIVATE, fd, 0);
 290        bitmap_git.map_pos = 0;
 291        close(fd);
 292
 293        if (load_bitmap_header(&bitmap_git) < 0) {
 294                munmap(bitmap_git.map, bitmap_git.map_size);
 295                bitmap_git.map = NULL;
 296                bitmap_git.map_size = 0;
 297                return -1;
 298        }
 299
 300        return 0;
 301}
 302
 303static int load_pack_bitmap(void)
 304{
 305        assert(bitmap_git.map && !bitmap_git.loaded);
 306
 307        bitmap_git.bitmaps = kh_init_sha1();
 308        bitmap_git.ext_index.positions = kh_init_sha1_pos();
 309        load_pack_revindex(bitmap_git.pack);
 310
 311        if (!(bitmap_git.commits = read_bitmap_1(&bitmap_git)) ||
 312                !(bitmap_git.trees = read_bitmap_1(&bitmap_git)) ||
 313                !(bitmap_git.blobs = read_bitmap_1(&bitmap_git)) ||
 314                !(bitmap_git.tags = read_bitmap_1(&bitmap_git)))
 315                goto failed;
 316
 317        if (load_bitmap_entries_v1(&bitmap_git) < 0)
 318                goto failed;
 319
 320        bitmap_git.loaded = 1;
 321        return 0;
 322
 323failed:
 324        munmap(bitmap_git.map, bitmap_git.map_size);
 325        bitmap_git.map = NULL;
 326        bitmap_git.map_size = 0;
 327        return -1;
 328}
 329
 330static int open_pack_bitmap(void)
 331{
 332        struct packed_git *p;
 333        int ret = -1;
 334
 335        assert(!bitmap_git.map && !bitmap_git.loaded);
 336
 337        prepare_packed_git();
 338        for (p = packed_git; p; p = p->next) {
 339                if (open_pack_bitmap_1(p) == 0)
 340                        ret = 0;
 341        }
 342
 343        return ret;
 344}
 345
 346int prepare_bitmap_git(void)
 347{
 348        if (bitmap_git.loaded)
 349                return 0;
 350
 351        if (!open_pack_bitmap())
 352                return load_pack_bitmap();
 353
 354        return -1;
 355}
 356
 357struct include_data {
 358        struct bitmap *base;
 359        struct bitmap *seen;
 360};
 361
 362static inline int bitmap_position_extended(const unsigned char *sha1)
 363{
 364        khash_sha1_pos *positions = bitmap_git.ext_index.positions;
 365        khiter_t pos = kh_get_sha1_pos(positions, sha1);
 366
 367        if (pos < kh_end(positions)) {
 368                int bitmap_pos = kh_value(positions, pos);
 369                return bitmap_pos + bitmap_git.pack->num_objects;
 370        }
 371
 372        return -1;
 373}
 374
 375static inline int bitmap_position_packfile(const unsigned char *sha1)
 376{
 377        off_t offset = find_pack_entry_one(sha1, bitmap_git.pack);
 378        if (!offset)
 379                return -1;
 380
 381        return find_revindex_position(bitmap_git.pack, offset);
 382}
 383
 384static int bitmap_position(const unsigned char *sha1)
 385{
 386        int pos = bitmap_position_packfile(sha1);
 387        return (pos >= 0) ? pos : bitmap_position_extended(sha1);
 388}
 389
 390static int ext_index_add_object(struct object *object, const char *name)
 391{
 392        struct eindex *eindex = &bitmap_git.ext_index;
 393
 394        khiter_t hash_pos;
 395        int hash_ret;
 396        int bitmap_pos;
 397
 398        hash_pos = kh_put_sha1_pos(eindex->positions, object->oid.hash, &hash_ret);
 399        if (hash_ret > 0) {
 400                if (eindex->count >= eindex->alloc) {
 401                        eindex->alloc = (eindex->alloc + 16) * 3 / 2;
 402                        REALLOC_ARRAY(eindex->objects, eindex->alloc);
 403                        REALLOC_ARRAY(eindex->hashes, eindex->alloc);
 404                }
 405
 406                bitmap_pos = eindex->count;
 407                eindex->objects[eindex->count] = object;
 408                eindex->hashes[eindex->count] = pack_name_hash(name);
 409                kh_value(eindex->positions, hash_pos) = bitmap_pos;
 410                eindex->count++;
 411        } else {
 412                bitmap_pos = kh_value(eindex->positions, hash_pos);
 413        }
 414
 415        return bitmap_pos + bitmap_git.pack->num_objects;
 416}
 417
 418static void show_object(struct object *object, const char *name, void *data)
 419{
 420        struct bitmap *base = data;
 421        int bitmap_pos;
 422
 423        bitmap_pos = bitmap_position(object->oid.hash);
 424
 425        if (bitmap_pos < 0)
 426                bitmap_pos = ext_index_add_object(object, name);
 427
 428        bitmap_set(base, bitmap_pos);
 429}
 430
 431static void show_commit(struct commit *commit, void *data)
 432{
 433}
 434
 435static int add_to_include_set(struct include_data *data,
 436                              const unsigned char *sha1,
 437                              int bitmap_pos)
 438{
 439        khiter_t hash_pos;
 440
 441        if (data->seen && bitmap_get(data->seen, bitmap_pos))
 442                return 0;
 443
 444        if (bitmap_get(data->base, bitmap_pos))
 445                return 0;
 446
 447        hash_pos = kh_get_sha1(bitmap_git.bitmaps, sha1);
 448        if (hash_pos < kh_end(bitmap_git.bitmaps)) {
 449                struct stored_bitmap *st = kh_value(bitmap_git.bitmaps, hash_pos);
 450                bitmap_or_ewah(data->base, lookup_stored_bitmap(st));
 451                return 0;
 452        }
 453
 454        bitmap_set(data->base, bitmap_pos);
 455        return 1;
 456}
 457
 458static int should_include(struct commit *commit, void *_data)
 459{
 460        struct include_data *data = _data;
 461        int bitmap_pos;
 462
 463        bitmap_pos = bitmap_position(commit->object.oid.hash);
 464        if (bitmap_pos < 0)
 465                bitmap_pos = ext_index_add_object((struct object *)commit, NULL);
 466
 467        if (!add_to_include_set(data, commit->object.oid.hash, bitmap_pos)) {
 468                struct commit_list *parent = commit->parents;
 469
 470                while (parent) {
 471                        parent->item->object.flags |= SEEN;
 472                        parent = parent->next;
 473                }
 474
 475                return 0;
 476        }
 477
 478        return 1;
 479}
 480
 481static struct bitmap *find_objects(struct rev_info *revs,
 482                                   struct object_list *roots,
 483                                   struct bitmap *seen)
 484{
 485        struct bitmap *base = NULL;
 486        int needs_walk = 0;
 487
 488        struct object_list *not_mapped = NULL;
 489
 490        /*
 491         * Go through all the roots for the walk. The ones that have bitmaps
 492         * on the bitmap index will be `or`ed together to form an initial
 493         * global reachability analysis.
 494         *
 495         * The ones without bitmaps in the index will be stored in the
 496         * `not_mapped_list` for further processing.
 497         */
 498        while (roots) {
 499                struct object *object = roots->item;
 500                roots = roots->next;
 501
 502                if (object->type == OBJ_COMMIT) {
 503                        khiter_t pos = kh_get_sha1(bitmap_git.bitmaps, object->oid.hash);
 504
 505                        if (pos < kh_end(bitmap_git.bitmaps)) {
 506                                struct stored_bitmap *st = kh_value(bitmap_git.bitmaps, pos);
 507                                struct ewah_bitmap *or_with = lookup_stored_bitmap(st);
 508
 509                                if (base == NULL)
 510                                        base = ewah_to_bitmap(or_with);
 511                                else
 512                                        bitmap_or_ewah(base, or_with);
 513
 514                                object->flags |= SEEN;
 515                                continue;
 516                        }
 517                }
 518
 519                object_list_insert(object, &not_mapped);
 520        }
 521
 522        /*
 523         * Best case scenario: We found bitmaps for all the roots,
 524         * so the resulting `or` bitmap has the full reachability analysis
 525         */
 526        if (not_mapped == NULL)
 527                return base;
 528
 529        roots = not_mapped;
 530
 531        /*
 532         * Let's iterate through all the roots that don't have bitmaps to
 533         * check if we can determine them to be reachable from the existing
 534         * global bitmap.
 535         *
 536         * If we cannot find them in the existing global bitmap, we'll need
 537         * to push them to an actual walk and run it until we can confirm
 538         * they are reachable
 539         */
 540        while (roots) {
 541                struct object *object = roots->item;
 542                int pos;
 543
 544                roots = roots->next;
 545                pos = bitmap_position(object->oid.hash);
 546
 547                if (pos < 0 || base == NULL || !bitmap_get(base, pos)) {
 548                        object->flags &= ~UNINTERESTING;
 549                        add_pending_object(revs, object, "");
 550                        needs_walk = 1;
 551                } else {
 552                        object->flags |= SEEN;
 553                }
 554        }
 555
 556        if (needs_walk) {
 557                struct include_data incdata;
 558
 559                if (base == NULL)
 560                        base = bitmap_new();
 561
 562                incdata.base = base;
 563                incdata.seen = seen;
 564
 565                revs->include_check = should_include;
 566                revs->include_check_data = &incdata;
 567
 568                if (prepare_revision_walk(revs))
 569                        die("revision walk setup failed");
 570
 571                traverse_commit_list(revs, show_commit, show_object, base);
 572        }
 573
 574        return base;
 575}
 576
 577static void show_extended_objects(struct bitmap *objects,
 578                                  show_reachable_fn show_reach)
 579{
 580        struct eindex *eindex = &bitmap_git.ext_index;
 581        uint32_t i;
 582
 583        for (i = 0; i < eindex->count; ++i) {
 584                struct object *obj;
 585
 586                if (!bitmap_get(objects, bitmap_git.pack->num_objects + i))
 587                        continue;
 588
 589                obj = eindex->objects[i];
 590                show_reach(obj->oid.hash, obj->type, 0, eindex->hashes[i], NULL, 0);
 591        }
 592}
 593
 594static void show_objects_for_type(
 595        struct bitmap *objects,
 596        struct ewah_bitmap *type_filter,
 597        enum object_type object_type,
 598        show_reachable_fn show_reach)
 599{
 600        size_t pos = 0, i = 0;
 601        uint32_t offset;
 602
 603        struct ewah_iterator it;
 604        eword_t filter;
 605
 606        if (bitmap_git.reuse_objects == bitmap_git.pack->num_objects)
 607                return;
 608
 609        ewah_iterator_init(&it, type_filter);
 610
 611        while (i < objects->word_alloc && ewah_iterator_next(&filter, &it)) {
 612                eword_t word = objects->words[i] & filter;
 613
 614                for (offset = 0; offset < BITS_IN_EWORD; ++offset) {
 615                        const unsigned char *sha1;
 616                        struct revindex_entry *entry;
 617                        uint32_t hash = 0;
 618
 619                        if ((word >> offset) == 0)
 620                                break;
 621
 622                        offset += ewah_bit_ctz64(word >> offset);
 623
 624                        if (pos + offset < bitmap_git.reuse_objects)
 625                                continue;
 626
 627                        entry = &bitmap_git.pack->revindex[pos + offset];
 628                        sha1 = nth_packed_object_sha1(bitmap_git.pack, entry->nr);
 629
 630                        if (bitmap_git.hashes)
 631                                hash = get_be32(bitmap_git.hashes + entry->nr);
 632
 633                        show_reach(sha1, object_type, 0, hash, bitmap_git.pack, entry->offset);
 634                }
 635
 636                pos += BITS_IN_EWORD;
 637                i++;
 638        }
 639}
 640
 641static int in_bitmapped_pack(struct object_list *roots)
 642{
 643        while (roots) {
 644                struct object *object = roots->item;
 645                roots = roots->next;
 646
 647                if (find_pack_entry_one(object->oid.hash, bitmap_git.pack) > 0)
 648                        return 1;
 649        }
 650
 651        return 0;
 652}
 653
 654int prepare_bitmap_walk(struct rev_info *revs)
 655{
 656        unsigned int i;
 657
 658        struct object_list *wants = NULL;
 659        struct object_list *haves = NULL;
 660
 661        struct bitmap *wants_bitmap = NULL;
 662        struct bitmap *haves_bitmap = NULL;
 663
 664        if (!bitmap_git.loaded) {
 665                /* try to open a bitmapped pack, but don't parse it yet
 666                 * because we may not need to use it */
 667                if (open_pack_bitmap() < 0)
 668                        return -1;
 669        }
 670
 671        for (i = 0; i < revs->pending.nr; ++i) {
 672                struct object *object = revs->pending.objects[i].item;
 673
 674                if (object->type == OBJ_NONE)
 675                        parse_object_or_die(&object->oid, NULL);
 676
 677                while (object->type == OBJ_TAG) {
 678                        struct tag *tag = (struct tag *) object;
 679
 680                        if (object->flags & UNINTERESTING)
 681                                object_list_insert(object, &haves);
 682                        else
 683                                object_list_insert(object, &wants);
 684
 685                        if (!tag->tagged)
 686                                die("bad tag");
 687                        object = parse_object_or_die(&tag->tagged->oid, NULL);
 688                }
 689
 690                if (object->flags & UNINTERESTING)
 691                        object_list_insert(object, &haves);
 692                else
 693                        object_list_insert(object, &wants);
 694        }
 695
 696        /*
 697         * if we have a HAVES list, but none of those haves is contained
 698         * in the packfile that has a bitmap, we don't have anything to
 699         * optimize here
 700         */
 701        if (haves && !in_bitmapped_pack(haves))
 702                return -1;
 703
 704        /* if we don't want anything, we're done here */
 705        if (!wants)
 706                return -1;
 707
 708        /*
 709         * now we're going to use bitmaps, so load the actual bitmap entries
 710         * from disk. this is the point of no return; after this the rev_list
 711         * becomes invalidated and we must perform the revwalk through bitmaps
 712         */
 713        if (!bitmap_git.loaded && load_pack_bitmap() < 0)
 714                return -1;
 715
 716        object_array_clear(&revs->pending);
 717
 718        if (haves) {
 719                revs->ignore_missing_links = 1;
 720                haves_bitmap = find_objects(revs, haves, NULL);
 721                reset_revision_walk();
 722                revs->ignore_missing_links = 0;
 723
 724                if (haves_bitmap == NULL)
 725                        die("BUG: failed to perform bitmap walk");
 726        }
 727
 728        wants_bitmap = find_objects(revs, wants, haves_bitmap);
 729
 730        if (!wants_bitmap)
 731                die("BUG: failed to perform bitmap walk");
 732
 733        if (haves_bitmap)
 734                bitmap_and_not(wants_bitmap, haves_bitmap);
 735
 736        bitmap_git.result = wants_bitmap;
 737
 738        bitmap_free(haves_bitmap);
 739        return 0;
 740}
 741
 742int reuse_partial_packfile_from_bitmap(struct packed_git **packfile,
 743                                       uint32_t *entries,
 744                                       off_t *up_to)
 745{
 746        /*
 747         * Reuse the packfile content if we need more than
 748         * 90% of its objects
 749         */
 750        static const double REUSE_PERCENT = 0.9;
 751
 752        struct bitmap *result = bitmap_git.result;
 753        uint32_t reuse_threshold;
 754        uint32_t i, reuse_objects = 0;
 755
 756        assert(result);
 757
 758        for (i = 0; i < result->word_alloc; ++i) {
 759                if (result->words[i] != (eword_t)~0) {
 760                        reuse_objects += ewah_bit_ctz64(~result->words[i]);
 761                        break;
 762                }
 763
 764                reuse_objects += BITS_IN_EWORD;
 765        }
 766
 767#ifdef GIT_BITMAP_DEBUG
 768        {
 769                const unsigned char *sha1;
 770                struct revindex_entry *entry;
 771
 772                entry = &bitmap_git.reverse_index->revindex[reuse_objects];
 773                sha1 = nth_packed_object_sha1(bitmap_git.pack, entry->nr);
 774
 775                fprintf(stderr, "Failed to reuse at %d (%016llx)\n",
 776                        reuse_objects, result->words[i]);
 777                fprintf(stderr, " %s\n", sha1_to_hex(sha1));
 778        }
 779#endif
 780
 781        if (!reuse_objects)
 782                return -1;
 783
 784        if (reuse_objects >= bitmap_git.pack->num_objects) {
 785                bitmap_git.reuse_objects = *entries = bitmap_git.pack->num_objects;
 786                *up_to = -1; /* reuse the full pack */
 787                *packfile = bitmap_git.pack;
 788                return 0;
 789        }
 790
 791        reuse_threshold = bitmap_popcount(bitmap_git.result) * REUSE_PERCENT;
 792
 793        if (reuse_objects < reuse_threshold)
 794                return -1;
 795
 796        bitmap_git.reuse_objects = *entries = reuse_objects;
 797        *up_to = bitmap_git.pack->revindex[reuse_objects].offset;
 798        *packfile = bitmap_git.pack;
 799
 800        return 0;
 801}
 802
 803void traverse_bitmap_commit_list(show_reachable_fn show_reachable)
 804{
 805        assert(bitmap_git.result);
 806
 807        show_objects_for_type(bitmap_git.result, bitmap_git.commits,
 808                OBJ_COMMIT, show_reachable);
 809        show_objects_for_type(bitmap_git.result, bitmap_git.trees,
 810                OBJ_TREE, show_reachable);
 811        show_objects_for_type(bitmap_git.result, bitmap_git.blobs,
 812                OBJ_BLOB, show_reachable);
 813        show_objects_for_type(bitmap_git.result, bitmap_git.tags,
 814                OBJ_TAG, show_reachable);
 815
 816        show_extended_objects(bitmap_git.result, show_reachable);
 817
 818        bitmap_free(bitmap_git.result);
 819        bitmap_git.result = NULL;
 820}
 821
 822static uint32_t count_object_type(struct bitmap *objects,
 823                                  enum object_type type)
 824{
 825        struct eindex *eindex = &bitmap_git.ext_index;
 826
 827        uint32_t i = 0, count = 0;
 828        struct ewah_iterator it;
 829        eword_t filter;
 830
 831        switch (type) {
 832        case OBJ_COMMIT:
 833                ewah_iterator_init(&it, bitmap_git.commits);
 834                break;
 835
 836        case OBJ_TREE:
 837                ewah_iterator_init(&it, bitmap_git.trees);
 838                break;
 839
 840        case OBJ_BLOB:
 841                ewah_iterator_init(&it, bitmap_git.blobs);
 842                break;
 843
 844        case OBJ_TAG:
 845                ewah_iterator_init(&it, bitmap_git.tags);
 846                break;
 847
 848        default:
 849                return 0;
 850        }
 851
 852        while (i < objects->word_alloc && ewah_iterator_next(&filter, &it)) {
 853                eword_t word = objects->words[i++] & filter;
 854                count += ewah_bit_popcount64(word);
 855        }
 856
 857        for (i = 0; i < eindex->count; ++i) {
 858                if (eindex->objects[i]->type == type &&
 859                        bitmap_get(objects, bitmap_git.pack->num_objects + i))
 860                        count++;
 861        }
 862
 863        return count;
 864}
 865
 866void count_bitmap_commit_list(uint32_t *commits, uint32_t *trees,
 867                              uint32_t *blobs, uint32_t *tags)
 868{
 869        assert(bitmap_git.result);
 870
 871        if (commits)
 872                *commits = count_object_type(bitmap_git.result, OBJ_COMMIT);
 873
 874        if (trees)
 875                *trees = count_object_type(bitmap_git.result, OBJ_TREE);
 876
 877        if (blobs)
 878                *blobs = count_object_type(bitmap_git.result, OBJ_BLOB);
 879
 880        if (tags)
 881                *tags = count_object_type(bitmap_git.result, OBJ_TAG);
 882}
 883
 884struct bitmap_test_data {
 885        struct bitmap *base;
 886        struct progress *prg;
 887        size_t seen;
 888};
 889
 890static void test_show_object(struct object *object, const char *name,
 891                             void *data)
 892{
 893        struct bitmap_test_data *tdata = data;
 894        int bitmap_pos;
 895
 896        bitmap_pos = bitmap_position(object->oid.hash);
 897        if (bitmap_pos < 0)
 898                die("Object not in bitmap: %s\n", oid_to_hex(&object->oid));
 899
 900        bitmap_set(tdata->base, bitmap_pos);
 901        display_progress(tdata->prg, ++tdata->seen);
 902}
 903
 904static void test_show_commit(struct commit *commit, void *data)
 905{
 906        struct bitmap_test_data *tdata = data;
 907        int bitmap_pos;
 908
 909        bitmap_pos = bitmap_position(commit->object.oid.hash);
 910        if (bitmap_pos < 0)
 911                die("Object not in bitmap: %s\n", oid_to_hex(&commit->object.oid));
 912
 913        bitmap_set(tdata->base, bitmap_pos);
 914        display_progress(tdata->prg, ++tdata->seen);
 915}
 916
 917void test_bitmap_walk(struct rev_info *revs)
 918{
 919        struct object *root;
 920        struct bitmap *result = NULL;
 921        khiter_t pos;
 922        size_t result_popcnt;
 923        struct bitmap_test_data tdata;
 924
 925        if (prepare_bitmap_git())
 926                die("failed to load bitmap indexes");
 927
 928        if (revs->pending.nr != 1)
 929                die("you must specify exactly one commit to test");
 930
 931        fprintf(stderr, "Bitmap v%d test (%d entries loaded)\n",
 932                bitmap_git.version, bitmap_git.entry_count);
 933
 934        root = revs->pending.objects[0].item;
 935        pos = kh_get_sha1(bitmap_git.bitmaps, root->oid.hash);
 936
 937        if (pos < kh_end(bitmap_git.bitmaps)) {
 938                struct stored_bitmap *st = kh_value(bitmap_git.bitmaps, pos);
 939                struct ewah_bitmap *bm = lookup_stored_bitmap(st);
 940
 941                fprintf(stderr, "Found bitmap for %s. %d bits / %08x checksum\n",
 942                        oid_to_hex(&root->oid), (int)bm->bit_size, ewah_checksum(bm));
 943
 944                result = ewah_to_bitmap(bm);
 945        }
 946
 947        if (result == NULL)
 948                die("Commit %s doesn't have an indexed bitmap", oid_to_hex(&root->oid));
 949
 950        revs->tag_objects = 1;
 951        revs->tree_objects = 1;
 952        revs->blob_objects = 1;
 953
 954        result_popcnt = bitmap_popcount(result);
 955
 956        if (prepare_revision_walk(revs))
 957                die("revision walk setup failed");
 958
 959        tdata.base = bitmap_new();
 960        tdata.prg = start_progress("Verifying bitmap entries", result_popcnt);
 961        tdata.seen = 0;
 962
 963        traverse_commit_list(revs, &test_show_commit, &test_show_object, &tdata);
 964
 965        stop_progress(&tdata.prg);
 966
 967        if (bitmap_equals(result, tdata.base))
 968                fprintf(stderr, "OK!\n");
 969        else
 970                fprintf(stderr, "Mismatch!\n");
 971
 972        bitmap_free(result);
 973}
 974
 975static int rebuild_bitmap(uint32_t *reposition,
 976                          struct ewah_bitmap *source,
 977                          struct bitmap *dest)
 978{
 979        uint32_t pos = 0;
 980        struct ewah_iterator it;
 981        eword_t word;
 982
 983        ewah_iterator_init(&it, source);
 984
 985        while (ewah_iterator_next(&word, &it)) {
 986                uint32_t offset, bit_pos;
 987
 988                for (offset = 0; offset < BITS_IN_EWORD; ++offset) {
 989                        if ((word >> offset) == 0)
 990                                break;
 991
 992                        offset += ewah_bit_ctz64(word >> offset);
 993
 994                        bit_pos = reposition[pos + offset];
 995                        if (bit_pos > 0)
 996                                bitmap_set(dest, bit_pos - 1);
 997                        else /* can't reuse, we don't have the object */
 998                                return -1;
 999                }
1000
1001                pos += BITS_IN_EWORD;
1002        }
1003        return 0;
1004}
1005
1006int rebuild_existing_bitmaps(struct packing_data *mapping,
1007                             khash_sha1 *reused_bitmaps,
1008                             int show_progress)
1009{
1010        uint32_t i, num_objects;
1011        uint32_t *reposition;
1012        struct bitmap *rebuild;
1013        struct stored_bitmap *stored;
1014        struct progress *progress = NULL;
1015
1016        khiter_t hash_pos;
1017        int hash_ret;
1018
1019        if (prepare_bitmap_git() < 0)
1020                return -1;
1021
1022        num_objects = bitmap_git.pack->num_objects;
1023        reposition = xcalloc(num_objects, sizeof(uint32_t));
1024
1025        for (i = 0; i < num_objects; ++i) {
1026                const unsigned char *sha1;
1027                struct revindex_entry *entry;
1028                struct object_entry *oe;
1029
1030                entry = &bitmap_git.pack->revindex[i];
1031                sha1 = nth_packed_object_sha1(bitmap_git.pack, entry->nr);
1032                oe = packlist_find(mapping, sha1, NULL);
1033
1034                if (oe)
1035                        reposition[i] = oe->in_pack_pos + 1;
1036        }
1037
1038        rebuild = bitmap_new();
1039        i = 0;
1040
1041        if (show_progress)
1042                progress = start_progress("Reusing bitmaps", 0);
1043
1044        kh_foreach_value(bitmap_git.bitmaps, stored, {
1045                if (stored->flags & BITMAP_FLAG_REUSE) {
1046                        if (!rebuild_bitmap(reposition,
1047                                            lookup_stored_bitmap(stored),
1048                                            rebuild)) {
1049                                hash_pos = kh_put_sha1(reused_bitmaps,
1050                                                       stored->sha1,
1051                                                       &hash_ret);
1052                                kh_value(reused_bitmaps, hash_pos) =
1053                                        bitmap_to_ewah(rebuild);
1054                        }
1055                        bitmap_reset(rebuild);
1056                        display_progress(progress, ++i);
1057                }
1058        });
1059
1060        stop_progress(&progress);
1061
1062        free(reposition);
1063        bitmap_free(rebuild);
1064        return 0;
1065}