pack-bitmap.con commit Merge branch 'jc/merge-x-theirs-docfix' (4da3e23)
   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        unsigned int pending_nr = revs->pending.nr;
 658        struct object_array_entry *pending_e = revs->pending.objects;
 659
 660        struct object_list *wants = NULL;
 661        struct object_list *haves = NULL;
 662
 663        struct bitmap *wants_bitmap = NULL;
 664        struct bitmap *haves_bitmap = NULL;
 665
 666        if (!bitmap_git.loaded) {
 667                /* try to open a bitmapped pack, but don't parse it yet
 668                 * because we may not need to use it */
 669                if (open_pack_bitmap() < 0)
 670                        return -1;
 671        }
 672
 673        for (i = 0; i < pending_nr; ++i) {
 674                struct object *object = pending_e[i].item;
 675
 676                if (object->type == OBJ_NONE)
 677                        parse_object_or_die(&object->oid, NULL);
 678
 679                while (object->type == OBJ_TAG) {
 680                        struct tag *tag = (struct tag *) object;
 681
 682                        if (object->flags & UNINTERESTING)
 683                                object_list_insert(object, &haves);
 684                        else
 685                                object_list_insert(object, &wants);
 686
 687                        if (!tag->tagged)
 688                                die("bad tag");
 689                        object = parse_object_or_die(&tag->tagged->oid, NULL);
 690                }
 691
 692                if (object->flags & UNINTERESTING)
 693                        object_list_insert(object, &haves);
 694                else
 695                        object_list_insert(object, &wants);
 696        }
 697
 698        /*
 699         * if we have a HAVES list, but none of those haves is contained
 700         * in the packfile that has a bitmap, we don't have anything to
 701         * optimize here
 702         */
 703        if (haves && !in_bitmapped_pack(haves))
 704                return -1;
 705
 706        /* if we don't want anything, we're done here */
 707        if (!wants)
 708                return -1;
 709
 710        /*
 711         * now we're going to use bitmaps, so load the actual bitmap entries
 712         * from disk. this is the point of no return; after this the rev_list
 713         * becomes invalidated and we must perform the revwalk through bitmaps
 714         */
 715        if (!bitmap_git.loaded && load_pack_bitmap() < 0)
 716                return -1;
 717
 718        revs->pending.nr = 0;
 719        revs->pending.alloc = 0;
 720        revs->pending.objects = NULL;
 721
 722        if (haves) {
 723                revs->ignore_missing_links = 1;
 724                haves_bitmap = find_objects(revs, haves, NULL);
 725                reset_revision_walk();
 726                revs->ignore_missing_links = 0;
 727
 728                if (haves_bitmap == NULL)
 729                        die("BUG: failed to perform bitmap walk");
 730        }
 731
 732        wants_bitmap = find_objects(revs, wants, haves_bitmap);
 733
 734        if (!wants_bitmap)
 735                die("BUG: failed to perform bitmap walk");
 736
 737        if (haves_bitmap)
 738                bitmap_and_not(wants_bitmap, haves_bitmap);
 739
 740        bitmap_git.result = wants_bitmap;
 741
 742        bitmap_free(haves_bitmap);
 743        return 0;
 744}
 745
 746int reuse_partial_packfile_from_bitmap(struct packed_git **packfile,
 747                                       uint32_t *entries,
 748                                       off_t *up_to)
 749{
 750        /*
 751         * Reuse the packfile content if we need more than
 752         * 90% of its objects
 753         */
 754        static const double REUSE_PERCENT = 0.9;
 755
 756        struct bitmap *result = bitmap_git.result;
 757        uint32_t reuse_threshold;
 758        uint32_t i, reuse_objects = 0;
 759
 760        assert(result);
 761
 762        for (i = 0; i < result->word_alloc; ++i) {
 763                if (result->words[i] != (eword_t)~0) {
 764                        reuse_objects += ewah_bit_ctz64(~result->words[i]);
 765                        break;
 766                }
 767
 768                reuse_objects += BITS_IN_EWORD;
 769        }
 770
 771#ifdef GIT_BITMAP_DEBUG
 772        {
 773                const unsigned char *sha1;
 774                struct revindex_entry *entry;
 775
 776                entry = &bitmap_git.reverse_index->revindex[reuse_objects];
 777                sha1 = nth_packed_object_sha1(bitmap_git.pack, entry->nr);
 778
 779                fprintf(stderr, "Failed to reuse at %d (%016llx)\n",
 780                        reuse_objects, result->words[i]);
 781                fprintf(stderr, " %s\n", sha1_to_hex(sha1));
 782        }
 783#endif
 784
 785        if (!reuse_objects)
 786                return -1;
 787
 788        if (reuse_objects >= bitmap_git.pack->num_objects) {
 789                bitmap_git.reuse_objects = *entries = bitmap_git.pack->num_objects;
 790                *up_to = -1; /* reuse the full pack */
 791                *packfile = bitmap_git.pack;
 792                return 0;
 793        }
 794
 795        reuse_threshold = bitmap_popcount(bitmap_git.result) * REUSE_PERCENT;
 796
 797        if (reuse_objects < reuse_threshold)
 798                return -1;
 799
 800        bitmap_git.reuse_objects = *entries = reuse_objects;
 801        *up_to = bitmap_git.pack->revindex[reuse_objects].offset;
 802        *packfile = bitmap_git.pack;
 803
 804        return 0;
 805}
 806
 807void traverse_bitmap_commit_list(show_reachable_fn show_reachable)
 808{
 809        assert(bitmap_git.result);
 810
 811        show_objects_for_type(bitmap_git.result, bitmap_git.commits,
 812                OBJ_COMMIT, show_reachable);
 813        show_objects_for_type(bitmap_git.result, bitmap_git.trees,
 814                OBJ_TREE, show_reachable);
 815        show_objects_for_type(bitmap_git.result, bitmap_git.blobs,
 816                OBJ_BLOB, show_reachable);
 817        show_objects_for_type(bitmap_git.result, bitmap_git.tags,
 818                OBJ_TAG, show_reachable);
 819
 820        show_extended_objects(bitmap_git.result, show_reachable);
 821
 822        bitmap_free(bitmap_git.result);
 823        bitmap_git.result = NULL;
 824}
 825
 826static uint32_t count_object_type(struct bitmap *objects,
 827                                  enum object_type type)
 828{
 829        struct eindex *eindex = &bitmap_git.ext_index;
 830
 831        uint32_t i = 0, count = 0;
 832        struct ewah_iterator it;
 833        eword_t filter;
 834
 835        switch (type) {
 836        case OBJ_COMMIT:
 837                ewah_iterator_init(&it, bitmap_git.commits);
 838                break;
 839
 840        case OBJ_TREE:
 841                ewah_iterator_init(&it, bitmap_git.trees);
 842                break;
 843
 844        case OBJ_BLOB:
 845                ewah_iterator_init(&it, bitmap_git.blobs);
 846                break;
 847
 848        case OBJ_TAG:
 849                ewah_iterator_init(&it, bitmap_git.tags);
 850                break;
 851
 852        default:
 853                return 0;
 854        }
 855
 856        while (i < objects->word_alloc && ewah_iterator_next(&filter, &it)) {
 857                eword_t word = objects->words[i++] & filter;
 858                count += ewah_bit_popcount64(word);
 859        }
 860
 861        for (i = 0; i < eindex->count; ++i) {
 862                if (eindex->objects[i]->type == type &&
 863                        bitmap_get(objects, bitmap_git.pack->num_objects + i))
 864                        count++;
 865        }
 866
 867        return count;
 868}
 869
 870void count_bitmap_commit_list(uint32_t *commits, uint32_t *trees,
 871                              uint32_t *blobs, uint32_t *tags)
 872{
 873        assert(bitmap_git.result);
 874
 875        if (commits)
 876                *commits = count_object_type(bitmap_git.result, OBJ_COMMIT);
 877
 878        if (trees)
 879                *trees = count_object_type(bitmap_git.result, OBJ_TREE);
 880
 881        if (blobs)
 882                *blobs = count_object_type(bitmap_git.result, OBJ_BLOB);
 883
 884        if (tags)
 885                *tags = count_object_type(bitmap_git.result, OBJ_TAG);
 886}
 887
 888struct bitmap_test_data {
 889        struct bitmap *base;
 890        struct progress *prg;
 891        size_t seen;
 892};
 893
 894static void test_show_object(struct object *object, const char *name,
 895                             void *data)
 896{
 897        struct bitmap_test_data *tdata = data;
 898        int bitmap_pos;
 899
 900        bitmap_pos = bitmap_position(object->oid.hash);
 901        if (bitmap_pos < 0)
 902                die("Object not in bitmap: %s\n", oid_to_hex(&object->oid));
 903
 904        bitmap_set(tdata->base, bitmap_pos);
 905        display_progress(tdata->prg, ++tdata->seen);
 906}
 907
 908static void test_show_commit(struct commit *commit, void *data)
 909{
 910        struct bitmap_test_data *tdata = data;
 911        int bitmap_pos;
 912
 913        bitmap_pos = bitmap_position(commit->object.oid.hash);
 914        if (bitmap_pos < 0)
 915                die("Object not in bitmap: %s\n", oid_to_hex(&commit->object.oid));
 916
 917        bitmap_set(tdata->base, bitmap_pos);
 918        display_progress(tdata->prg, ++tdata->seen);
 919}
 920
 921void test_bitmap_walk(struct rev_info *revs)
 922{
 923        struct object *root;
 924        struct bitmap *result = NULL;
 925        khiter_t pos;
 926        size_t result_popcnt;
 927        struct bitmap_test_data tdata;
 928
 929        if (prepare_bitmap_git())
 930                die("failed to load bitmap indexes");
 931
 932        if (revs->pending.nr != 1)
 933                die("you must specify exactly one commit to test");
 934
 935        fprintf(stderr, "Bitmap v%d test (%d entries loaded)\n",
 936                bitmap_git.version, bitmap_git.entry_count);
 937
 938        root = revs->pending.objects[0].item;
 939        pos = kh_get_sha1(bitmap_git.bitmaps, root->oid.hash);
 940
 941        if (pos < kh_end(bitmap_git.bitmaps)) {
 942                struct stored_bitmap *st = kh_value(bitmap_git.bitmaps, pos);
 943                struct ewah_bitmap *bm = lookup_stored_bitmap(st);
 944
 945                fprintf(stderr, "Found bitmap for %s. %d bits / %08x checksum\n",
 946                        oid_to_hex(&root->oid), (int)bm->bit_size, ewah_checksum(bm));
 947
 948                result = ewah_to_bitmap(bm);
 949        }
 950
 951        if (result == NULL)
 952                die("Commit %s doesn't have an indexed bitmap", oid_to_hex(&root->oid));
 953
 954        revs->tag_objects = 1;
 955        revs->tree_objects = 1;
 956        revs->blob_objects = 1;
 957
 958        result_popcnt = bitmap_popcount(result);
 959
 960        if (prepare_revision_walk(revs))
 961                die("revision walk setup failed");
 962
 963        tdata.base = bitmap_new();
 964        tdata.prg = start_progress("Verifying bitmap entries", result_popcnt);
 965        tdata.seen = 0;
 966
 967        traverse_commit_list(revs, &test_show_commit, &test_show_object, &tdata);
 968
 969        stop_progress(&tdata.prg);
 970
 971        if (bitmap_equals(result, tdata.base))
 972                fprintf(stderr, "OK!\n");
 973        else
 974                fprintf(stderr, "Mismatch!\n");
 975
 976        bitmap_free(result);
 977}
 978
 979static int rebuild_bitmap(uint32_t *reposition,
 980                          struct ewah_bitmap *source,
 981                          struct bitmap *dest)
 982{
 983        uint32_t pos = 0;
 984        struct ewah_iterator it;
 985        eword_t word;
 986
 987        ewah_iterator_init(&it, source);
 988
 989        while (ewah_iterator_next(&word, &it)) {
 990                uint32_t offset, bit_pos;
 991
 992                for (offset = 0; offset < BITS_IN_EWORD; ++offset) {
 993                        if ((word >> offset) == 0)
 994                                break;
 995
 996                        offset += ewah_bit_ctz64(word >> offset);
 997
 998                        bit_pos = reposition[pos + offset];
 999                        if (bit_pos > 0)
1000                                bitmap_set(dest, bit_pos - 1);
1001                        else /* can't reuse, we don't have the object */
1002                                return -1;
1003                }
1004
1005                pos += BITS_IN_EWORD;
1006        }
1007        return 0;
1008}
1009
1010int rebuild_existing_bitmaps(struct packing_data *mapping,
1011                             khash_sha1 *reused_bitmaps,
1012                             int show_progress)
1013{
1014        uint32_t i, num_objects;
1015        uint32_t *reposition;
1016        struct bitmap *rebuild;
1017        struct stored_bitmap *stored;
1018        struct progress *progress = NULL;
1019
1020        khiter_t hash_pos;
1021        int hash_ret;
1022
1023        if (prepare_bitmap_git() < 0)
1024                return -1;
1025
1026        num_objects = bitmap_git.pack->num_objects;
1027        reposition = xcalloc(num_objects, sizeof(uint32_t));
1028
1029        for (i = 0; i < num_objects; ++i) {
1030                const unsigned char *sha1;
1031                struct revindex_entry *entry;
1032                struct object_entry *oe;
1033
1034                entry = &bitmap_git.pack->revindex[i];
1035                sha1 = nth_packed_object_sha1(bitmap_git.pack, entry->nr);
1036                oe = packlist_find(mapping, sha1, NULL);
1037
1038                if (oe)
1039                        reposition[i] = oe->in_pack_pos + 1;
1040        }
1041
1042        rebuild = bitmap_new();
1043        i = 0;
1044
1045        if (show_progress)
1046                progress = start_progress("Reusing bitmaps", 0);
1047
1048        kh_foreach_value(bitmap_git.bitmaps, stored, {
1049                if (stored->flags & BITMAP_FLAG_REUSE) {
1050                        if (!rebuild_bitmap(reposition,
1051                                            lookup_stored_bitmap(stored),
1052                                            rebuild)) {
1053                                hash_pos = kh_put_sha1(reused_bitmaps,
1054                                                       stored->sha1,
1055                                                       &hash_ret);
1056                                kh_value(reused_bitmaps, hash_pos) =
1057                                        bitmap_to_ewah(rebuild);
1058                        }
1059                        bitmap_reset(rebuild);
1060                        display_progress(progress, ++i);
1061                }
1062        });
1063
1064        stop_progress(&progress);
1065
1066        free(reposition);
1067        bitmap_free(rebuild);
1068        return 0;
1069}