pack-bitmap-write.c

   1 #include "git-compat-util.h"
   2 #include "environment.h"
   3 #include "gettext.h"
   4 #include "hex.h"
   5 #include "object-store-ll.h"
   6 #include "commit.h"
   7 #include "diff.h"
   8 #include "revision.h"
   9 #include "progress.h"
  10 #include "pack.h"
  11 #include "pack-bitmap.h"
  12 #include "hash-lookup.h"
  13 #include "pack-objects.h"
  14 #include "path.h"
  15 #include "commit-reach.h"
  16 #include "prio-queue.h"
  17 #include "trace2.h"
  18 #include "tree.h"
  19 #include "tree-walk.h"
  20
  21 struct bitmapped_commit {
  22         struct commit *commit;
  23         struct ewah_bitmap *bitmap;
  24         struct ewah_bitmap *write_as;
  25         int flags;
  26         int xor_offset;
  27         uint32_t commit_pos;
  28 };
  29
  30 void bitmap_writer_init(struct bitmap_writer *writer)
  31 {
  32         memset(writer, 0, sizeof(struct bitmap_writer));
  33 }
  34
  35 void bitmap_writer_free(struct bitmap_writer *writer)
  36 {
  37         uint32_t i;
  38
  39         if (!writer)
  40                 return;
  41
  42         ewah_free(writer->commits);
  43         ewah_free(writer->trees);
  44         ewah_free(writer->blobs);
  45         ewah_free(writer->tags);
  46
  47         kh_destroy_oid_map(writer->bitmaps);
  48
  49         for (i = 0; i < writer->selected_nr; i++) {
  50                 struct bitmapped_commit *bc = &writer->selected[i];
  51                 if (bc->write_as != bc->bitmap)
  52                         ewah_free(bc->write_as);
  53                 ewah_free(bc->bitmap);
  54         }
  55         free(writer->selected);
  56 }
  57
  58 void bitmap_writer_show_progress(struct bitmap_writer *writer, int show)
  59 {
  60         writer->show_progress = show;
  61 }
  62
  63 /**
  64  * Build the initial type index for the packfile or multi-pack-index
  65  */
  66 void bitmap_writer_build_type_index(struct bitmap_writer *writer,
  67                                     struct packing_data *to_pack,
  68                                     struct pack_idx_entry **index,
  69                                     uint32_t index_nr)
  70 {
  71         uint32_t i;
  72
  73         writer->commits = ewah_new();
  74         writer->trees = ewah_new();
  75         writer->blobs = ewah_new();
  76         writer->tags = ewah_new();
  77         ALLOC_ARRAY(to_pack->in_pack_pos, to_pack->nr_objects);
  78
  79         for (i = 0; i < index_nr; ++i) {
  80                 struct object_entry *entry = (struct object_entry *)index[i];
  81                 enum object_type real_type;
  82
  83                 oe_set_in_pack_pos(to_pack, entry, i);
  84
  85                 switch (oe_type(entry)) {
  86                 case OBJ_COMMIT:
  87                 case OBJ_TREE:
  88                 case OBJ_BLOB:
  89                 case OBJ_TAG:
  90                         real_type = oe_type(entry);
  91                         break;
  92
  93                 default:
  94                         real_type = oid_object_info(to_pack->repo,
  95                                                     &entry->idx.oid, NULL);
  96                         break;
  97                 }
  98
  99                 switch (real_type) {
 100                 case OBJ_COMMIT:
 101                         ewah_set(writer->commits, i);
 102                         break;
 103
 104                 case OBJ_TREE:
 105                         ewah_set(writer->trees, i);
 106                         break;
 107
 108                 case OBJ_BLOB:
 109                         ewah_set(writer->blobs, i);
 110                         break;
 111
 112                 case OBJ_TAG:
 113                         ewah_set(writer->tags, i);
 114                         break;
 115
 116                 default:
 117                         die("Missing type information for %s (%d/%d)",
 118                             oid_to_hex(&entry->idx.oid), real_type,
 119                             oe_type(entry));
 120                 }
 121         }
 122 }
 123
 124 /**
 125  * Compute the actual bitmaps
 126  */
 127
 128 static inline void push_bitmapped_commit(struct bitmap_writer *writer,
 129                                          struct commit *commit)
 130 {
 131         if (writer->selected_nr >= writer->selected_alloc) {
 132                 writer->selected_alloc = (writer->selected_alloc + 32) * 2;
 133                 REALLOC_ARRAY(writer->selected, writer->selected_alloc);
 134         }
 135
 136         writer->selected[writer->selected_nr].commit = commit;
 137         writer->selected[writer->selected_nr].bitmap = NULL;
 138         writer->selected[writer->selected_nr].write_as = NULL;
 139         writer->selected[writer->selected_nr].flags = 0;
 140
 141         writer->selected_nr++;
 142 }
 143
 144 static uint32_t find_object_pos(struct bitmap_writer *writer,
 145                                 const struct object_id *oid, int *found)
 146 {
 147         struct object_entry *entry = packlist_find(writer->to_pack, oid);
 148
 149         if (!entry) {
 150                 if (found)
 151                         *found = 0;
 152                 warning("Failed to write bitmap index. Packfile doesn't have full closure "
 153                         "(object %s is missing)", oid_to_hex(oid));
 154                 return 0;
 155         }
 156
 157         if (found)
 158                 *found = 1;
 159         return oe_in_pack_pos(writer->to_pack, entry);
 160 }
 161
 162 static void compute_xor_offsets(struct bitmap_writer *writer)
 163 {
 164         static const int MAX_XOR_OFFSET_SEARCH = 10;
 165
 166         int i, next = 0;
 167
 168         while (next < writer->selected_nr) {
 169                 struct bitmapped_commit *stored = &writer->selected[next];
 170
 171                 int best_offset = 0;
 172                 struct ewah_bitmap *best_bitmap = stored->bitmap;
 173                 struct ewah_bitmap *test_xor;
 174
 175                 for (i = 1; i <= MAX_XOR_OFFSET_SEARCH; ++i) {
 176                         int curr = next - i;
 177
 178                         if (curr < 0)
 179                                 break;
 180
 181                         test_xor = ewah_pool_new();
 182                         ewah_xor(writer->selected[curr].bitmap, stored->bitmap, test_xor);
 183
 184                         if (test_xor->buffer_size < best_bitmap->buffer_size) {
 185                                 if (best_bitmap != stored->bitmap)
 186                                         ewah_pool_free(best_bitmap);
 187
 188                                 best_bitmap = test_xor;
 189                                 best_offset = i;
 190                         } else {
 191                                 ewah_pool_free(test_xor);
 192                         }
 193                 }
 194
 195                 stored->xor_offset = best_offset;
 196                 stored->write_as = best_bitmap;
 197
 198                 next++;
 199         }
 200 }
 201
 202 struct bb_commit {
 203         struct commit_list *reverse_edges;
 204         struct bitmap *commit_mask;
 205         struct bitmap *bitmap;
 206         unsigned selected:1,
 207                  maximal:1;
 208         unsigned idx; /* within selected array */
 209 };
 210
 211 static void clear_bb_commit(struct bb_commit *commit)
 212 {
 213         free_commit_list(commit->reverse_edges);
 214         bitmap_free(commit->commit_mask);
 215         bitmap_free(commit->bitmap);
 216 }
 217
 218 define_commit_slab(bb_data, struct bb_commit);
 219
 220 struct bitmap_builder {
 221         struct bb_data data;
 222         struct commit **commits;
 223         size_t commits_nr, commits_alloc;
 224 };
 225
 226 static void bitmap_builder_init(struct bitmap_builder *bb,
 227                                 struct bitmap_writer *writer,
 228                                 struct bitmap_index *old_bitmap)
 229 {
 230         struct rev_info revs;
 231         struct commit *commit;
 232         struct commit_list *reusable = NULL;
 233         struct commit_list *r;
 234         unsigned int i, num_maximal = 0;
 235
 236         memset(bb, 0, sizeof(*bb));
 237         init_bb_data(&bb->data);
 238
 239         reset_revision_walk();
 240         repo_init_revisions(writer->to_pack->repo, &revs, NULL);
 241         revs.topo_order = 1;
 242         revs.first_parent_only = 1;
 243
 244         for (i = 0; i < writer->selected_nr; i++) {
 245                 struct commit *c = writer->selected[i].commit;
 246                 struct bb_commit *ent = bb_data_at(&bb->data, c);
 247
 248                 ent->selected = 1;
 249                 ent->maximal = 1;
 250                 ent->idx = i;
 251
 252                 ent->commit_mask = bitmap_new();
 253                 bitmap_set(ent->commit_mask, i);
 254
 255                 add_pending_object(&revs, &c->object, "");
 256         }
 257
 258         if (prepare_revision_walk(&revs))
 259                 die("revision walk setup failed");
 260
 261         while ((commit = get_revision(&revs))) {
 262                 struct commit_list *p = commit->parents;
 263                 struct bb_commit *c_ent;
 264
 265                 parse_commit_or_die(commit);
 266
 267                 c_ent = bb_data_at(&bb->data, commit);
 268
 269                 /*
 270                  * If there is no commit_mask, there is no reason to iterate
 271                  * over this commit; it is not selected (if it were, it would
 272                  * not have a blank commit mask) and all its children have
 273                  * existing bitmaps (see the comment starting with "This commit
 274                  * has an existing bitmap" below), so it does not contribute
 275                  * anything to the final bitmap file or its descendants.
 276                  */
 277                 if (!c_ent->commit_mask)
 278                         continue;
 279
 280                 if (old_bitmap && bitmap_for_commit(old_bitmap, commit)) {
 281                         /*
 282                          * This commit has an existing bitmap, so we can
 283                          * get its bits immediately without an object
 284                          * walk. That is, it is reusable as-is and there is no
 285                          * need to continue walking beyond it.
 286                          *
 287                          * Mark it as such and add it to bb->commits separately
 288                          * to avoid allocating a position in the commit mask.
 289                          */
 290                         commit_list_insert(commit, &reusable);
 291                         goto next;
 292                 }
 293
 294                 if (c_ent->maximal) {
 295                         num_maximal++;
 296                         ALLOC_GROW(bb->commits, bb->commits_nr + 1, bb->commits_alloc);
 297                         bb->commits[bb->commits_nr++] = commit;
 298                 }
 299
 300                 if (p) {
 301                         struct bb_commit *p_ent = bb_data_at(&bb->data, p->item);
 302                         int c_not_p, p_not_c;
 303
 304                         if (!p_ent->commit_mask) {
 305                                 p_ent->commit_mask = bitmap_new();
 306                                 c_not_p = 1;
 307                                 p_not_c = 0;
 308                         } else {
 309                                 c_not_p = bitmap_is_subset(c_ent->commit_mask, p_ent->commit_mask);
 310                                 p_not_c = bitmap_is_subset(p_ent->commit_mask, c_ent->commit_mask);
 311                         }
 312
 313                         if (!c_not_p)
 314                                 continue;
 315
 316                         bitmap_or(p_ent->commit_mask, c_ent->commit_mask);
 317
 318                         if (p_not_c)
 319                                 p_ent->maximal = 1;
 320                         else {
 321                                 p_ent->maximal = 0;
 322                                 free_commit_list(p_ent->reverse_edges);
 323                                 p_ent->reverse_edges = NULL;
 324                         }
 325
 326                         if (c_ent->maximal) {
 327                                 commit_list_insert(commit, &p_ent->reverse_edges);
 328                         } else {
 329                                 struct commit_list *cc = c_ent->reverse_edges;
 330
 331                                 for (; cc; cc = cc->next) {
 332                                         if (!commit_list_contains(cc->item, p_ent->reverse_edges))
 333                                                 commit_list_insert(cc->item, &p_ent->reverse_edges);
 334                                 }
 335                         }
 336                 }
 337
 338 next:
 339                 bitmap_free(c_ent->commit_mask);
 340                 c_ent->commit_mask = NULL;
 341         }
 342
 343         for (r = reusable; r; r = r->next) {
 344                 ALLOC_GROW(bb->commits, bb->commits_nr + 1, bb->commits_alloc);
 345                 bb->commits[bb->commits_nr++] = r->item;
 346         }
 347
 348         trace2_data_intmax("pack-bitmap-write", the_repository,
 349                            "num_selected_commits", writer->selected_nr);
 350         trace2_data_intmax("pack-bitmap-write", the_repository,
 351                            "num_maximal_commits", num_maximal);
 352
 353         release_revisions(&revs);
 354         free_commit_list(reusable);
 355 }
 356
 357 static void bitmap_builder_clear(struct bitmap_builder *bb)
 358 {
 359         deep_clear_bb_data(&bb->data, clear_bb_commit);
 360         free(bb->commits);
 361         bb->commits_nr = bb->commits_alloc = 0;
 362 }
 363
 364 static int fill_bitmap_tree(struct bitmap_writer *writer,
 365                             struct bitmap *bitmap,
 366                             struct tree *tree)
 367 {
 368         int found;
 369         uint32_t pos;
 370         struct tree_desc desc;
 371         struct name_entry entry;
 372
 373         /*
 374          * If our bit is already set, then there is nothing to do. Both this
 375          * tree and all of its children will be set.
 376          */
 377         pos = find_object_pos(writer, &tree->object.oid, &found);
 378         if (!found)
 379                 return -1;
 380         if (bitmap_get(bitmap, pos))
 381                 return 0;
 382         bitmap_set(bitmap, pos);
 383
 384         if (parse_tree(tree) < 0)
 385                 die("unable to load tree object %s",
 386                     oid_to_hex(&tree->object.oid));
 387         init_tree_desc(&desc, &tree->object.oid, tree->buffer, tree->size);
 388
 389         while (tree_entry(&desc, &entry)) {
 390                 switch (object_type(entry.mode)) {
 391                 case OBJ_TREE:
 392                         if (fill_bitmap_tree(writer, bitmap,
 393                                              lookup_tree(the_repository, &entry.oid)) < 0)
 394                                 return -1;
 395                         break;
 396                 case OBJ_BLOB:
 397                         pos = find_object_pos(writer, &entry.oid, &found);
 398                         if (!found)
 399                                 return -1;
 400                         bitmap_set(bitmap, pos);
 401                         break;
 402                 default:
 403                         /* Gitlink, etc; not reachable */
 404                         break;
 405                 }
 406         }
 407
 408         free_tree_buffer(tree);
 409         return 0;
 410 }
 411
 412 static int reused_bitmaps_nr;
 413
 414 static int fill_bitmap_commit(struct bitmap_writer *writer,
 415                               struct bb_commit *ent,
 416                               struct commit *commit,
 417                               struct prio_queue *queue,
 418                               struct prio_queue *tree_queue,
 419                               struct bitmap_index *old_bitmap,
 420                               const uint32_t *mapping)
 421 {
 422         int found;
 423         uint32_t pos;
 424         if (!ent->bitmap)
 425                 ent->bitmap = bitmap_new();
 426
 427         prio_queue_put(queue, commit);
 428
 429         while (queue->nr) {
 430                 struct commit_list *p;
 431                 struct commit *c = prio_queue_get(queue);
 432
 433                 if (old_bitmap && mapping) {
 434                         struct ewah_bitmap *old = bitmap_for_commit(old_bitmap, c);
 435                         struct bitmap *remapped = bitmap_new();
 436                         /*
 437                          * If this commit has an old bitmap, then translate that
 438                          * bitmap and add its bits to this one. No need to walk
 439                          * parents or the tree for this commit.
 440                          */
 441                         if (old && !rebuild_bitmap(mapping, old, remapped)) {
 442                                 bitmap_or(ent->bitmap, remapped);
 443                                 bitmap_free(remapped);
 444                                 reused_bitmaps_nr++;
 445                                 continue;
 446                         }
 447                         bitmap_free(remapped);
 448                 }
 449
 450                 /*
 451                  * Mark ourselves and queue our tree. The commit
 452                  * walk ensures we cover all parents.
 453                  */
 454                 pos = find_object_pos(writer, &c->object.oid, &found);
 455                 if (!found)
 456                         return -1;
 457                 bitmap_set(ent->bitmap, pos);
 458                 prio_queue_put(tree_queue,
 459                                repo_get_commit_tree(the_repository, c));
 460
 461                 for (p = c->parents; p; p = p->next) {
 462                         pos = find_object_pos(writer, &p->item->object.oid,
 463                                               &found);
 464                         if (!found)
 465                                 return -1;
 466                         if (!bitmap_get(ent->bitmap, pos)) {
 467                                 bitmap_set(ent->bitmap, pos);
 468                                 prio_queue_put(queue, p->item);
 469                         }
 470                 }
 471         }
 472
 473         while (tree_queue->nr) {
 474                 if (fill_bitmap_tree(writer, ent->bitmap,
 475                                      prio_queue_get(tree_queue)) < 0)
 476                         return -1;
 477         }
 478         return 0;
 479 }
 480
 481 static void store_selected(struct bitmap_writer *writer,
 482                            struct bb_commit *ent, struct commit *commit)
 483 {
 484         struct bitmapped_commit *stored = &writer->selected[ent->idx];
 485         khiter_t hash_pos;
 486         int hash_ret;
 487
 488         stored->bitmap = bitmap_to_ewah(ent->bitmap);
 489
 490         hash_pos = kh_put_oid_map(writer->bitmaps, commit->object.oid, &hash_ret);
 491         if (hash_ret == 0)
 492                 die("Duplicate entry when writing index: %s",
 493                     oid_to_hex(&commit->object.oid));
 494         kh_value(writer->bitmaps, hash_pos) = stored;
 495 }
 496
 497 int bitmap_writer_build(struct bitmap_writer *writer,
 498                         struct packing_data *to_pack)
 499 {
 500         struct bitmap_builder bb;
 501         size_t i;
 502         int nr_stored = 0; /* for progress */
 503         struct prio_queue queue = { compare_commits_by_gen_then_commit_date };
 504         struct prio_queue tree_queue = { NULL };
 505         struct bitmap_index *old_bitmap;
 506         uint32_t *mapping;
 507         int closed = 1; /* until proven otherwise */
 508
 509         writer->bitmaps = kh_init_oid_map();
 510         writer->to_pack = to_pack;
 511
 512         if (writer->show_progress)
 513                 writer->progress = start_progress("Building bitmaps",
 514                                                   writer->selected_nr);
 515         trace2_region_enter("pack-bitmap-write", "building_bitmaps_total",
 516                             the_repository);
 517
 518         old_bitmap = prepare_bitmap_git(to_pack->repo);
 519         if (old_bitmap)
 520                 mapping = create_bitmap_mapping(old_bitmap, to_pack);
 521         else
 522                 mapping = NULL;
 523
 524         bitmap_builder_init(&bb, writer, old_bitmap);
 525         for (i = bb.commits_nr; i > 0; i--) {
 526                 struct commit *commit = bb.commits[i-1];
 527                 struct bb_commit *ent = bb_data_at(&bb.data, commit);
 528                 struct commit *child;
 529                 int reused = 0;
 530
 531                 if (fill_bitmap_commit(writer, ent, commit, &queue, &tree_queue,
 532                                        old_bitmap, mapping) < 0) {
 533                         closed = 0;
 534                         break;
 535                 }
 536
 537                 if (ent->selected) {
 538                         store_selected(writer, ent, commit);
 539                         nr_stored++;
 540                         display_progress(writer->progress, nr_stored);
 541                 }
 542
 543                 while ((child = pop_commit(&ent->reverse_edges))) {
 544                         struct bb_commit *child_ent =
 545                                 bb_data_at(&bb.data, child);
 546
 547                         if (child_ent->bitmap)
 548                                 bitmap_or(child_ent->bitmap, ent->bitmap);
 549                         else if (reused)
 550                                 child_ent->bitmap = bitmap_dup(ent->bitmap);
 551                         else {
 552                                 child_ent->bitmap = ent->bitmap;
 553                                 reused = 1;
 554                         }
 555                 }
 556                 if (!reused)
 557                         bitmap_free(ent->bitmap);
 558                 ent->bitmap = NULL;
 559         }
 560         clear_prio_queue(&queue);
 561         clear_prio_queue(&tree_queue);
 562         bitmap_builder_clear(&bb);
 563         free_bitmap_index(old_bitmap);
 564         free(mapping);
 565
 566         trace2_region_leave("pack-bitmap-write", "building_bitmaps_total",
 567                             the_repository);
 568         trace2_data_intmax("pack-bitmap-write", the_repository,
 569                            "building_bitmaps_reused", reused_bitmaps_nr);
 570
 571         stop_progress(&writer->progress);
 572
 573         if (closed)
 574                 compute_xor_offsets(writer);
 575         return closed ? 0 : -1;
 576 }
 577
 578 /**
 579  * Select the commits that will be bitmapped
 580  */
 581 static inline unsigned int next_commit_index(unsigned int idx)
 582 {
 583         static const unsigned int MIN_COMMITS = 100;
 584         static const unsigned int MAX_COMMITS = 5000;
 585
 586         static const unsigned int MUST_REGION = 100;
 587         static const unsigned int MIN_REGION = 20000;
 588
 589         unsigned int offset, next;
 590
 591         if (idx <= MUST_REGION)
 592                 return 0;
 593
 594         if (idx <= MIN_REGION) {
 595                 offset = idx - MUST_REGION;
 596                 return (offset < MIN_COMMITS) ? offset : MIN_COMMITS;
 597         }
 598
 599         offset = idx - MIN_REGION;
 600         next = (offset < MAX_COMMITS) ? offset : MAX_COMMITS;
 601
 602         return (next > MIN_COMMITS) ? next : MIN_COMMITS;
 603 }
 604
 605 static int date_compare(const void *_a, const void *_b)
 606 {
 607         struct commit *a = *(struct commit **)_a;
 608         struct commit *b = *(struct commit **)_b;
 609         return (long)b->date - (long)a->date;
 610 }
 611
 612 void bitmap_writer_select_commits(struct bitmap_writer *writer,
 613                                   struct commit **indexed_commits,
 614                                   unsigned int indexed_commits_nr)
 615 {
 616         unsigned int i = 0, j, next;
 617
 618         QSORT(indexed_commits, indexed_commits_nr, date_compare);
 619
 620         if (indexed_commits_nr < 100) {
 621                 for (i = 0; i < indexed_commits_nr; ++i)
 622                         push_bitmapped_commit(writer, indexed_commits[i]);
 623                 return;
 624         }
 625
 626         if (writer->show_progress)
 627                 writer->progress = start_progress("Selecting bitmap commits", 0);
 628
 629         for (;;) {
 630                 struct commit *chosen = NULL;
 631
 632                 next = next_commit_index(i);
 633
 634                 if (i + next >= indexed_commits_nr)
 635                         break;
 636
 637                 if (next == 0) {
 638                         chosen = indexed_commits[i];
 639                 } else {
 640                         chosen = indexed_commits[i + next];
 641
 642                         for (j = 0; j <= next; ++j) {
 643                                 struct commit *cm = indexed_commits[i + j];
 644
 645                                 if ((cm->object.flags & NEEDS_BITMAP) != 0) {
 646                                         chosen = cm;
 647                                         break;
 648                                 }
 649
 650                                 if (cm->parents && cm->parents->next)
 651                                         chosen = cm;
 652                         }
 653                 }
 654
 655                 push_bitmapped_commit(writer, chosen);
 656
 657                 i += next + 1;
 658                 display_progress(writer->progress, i);
 659         }
 660
 661         stop_progress(&writer->progress);
 662 }
 663
 664
 665 static int hashwrite_ewah_helper(void *f, const void *buf, size_t len)
 666 {
 667         /* hashwrite will die on error */
 668         hashwrite(f, buf, len);
 669         return len;
 670 }
 671
 672 /**
 673  * Write the bitmap index to disk
 674  */
 675 static inline void dump_bitmap(struct hashfile *f, struct ewah_bitmap *bitmap)
 676 {
 677         if (ewah_serialize_to(bitmap, hashwrite_ewah_helper, f) < 0)
 678                 die("Failed to write bitmap index");
 679 }
 680
 681 static const struct object_id *oid_access(size_t pos, const void *table)
 682 {
 683         const struct pack_idx_entry * const *index = table;
 684         return &index[pos]->oid;
 685 }
 686
 687 static void write_selected_commits_v1(struct bitmap_writer *writer,
 688                                       struct hashfile *f, off_t *offsets)
 689 {
 690         int i;
 691
 692         for (i = 0; i < writer->selected_nr; ++i) {
 693                 struct bitmapped_commit *stored = &writer->selected[i];
 694
 695                 if (offsets)
 696                         offsets[i] = hashfile_total(f);
 697
 698                 hashwrite_be32(f, stored->commit_pos);
 699                 hashwrite_u8(f, stored->xor_offset);
 700                 hashwrite_u8(f, stored->flags);
 701
 702                 dump_bitmap(f, stored->write_as);
 703         }
 704 }
 705
 706 static int table_cmp(const void *_va, const void *_vb, void *_data)
 707 {
 708         struct bitmap_writer *writer = _data;
 709         struct bitmapped_commit *a = &writer->selected[*(uint32_t *)_va];
 710         struct bitmapped_commit *b = &writer->selected[*(uint32_t *)_vb];
 711
 712         if (a->commit_pos < b->commit_pos)
 713                 return -1;
 714         else if (a->commit_pos > b->commit_pos)
 715                 return 1;
 716
 717         return 0;
 718 }
 719
 720 static void write_lookup_table(struct bitmap_writer *writer, struct hashfile *f,
 721                                off_t *offsets)
 722 {
 723         uint32_t i;
 724         uint32_t *table, *table_inv;
 725
 726         ALLOC_ARRAY(table, writer->selected_nr);
 727         ALLOC_ARRAY(table_inv, writer->selected_nr);
 728
 729         for (i = 0; i < writer->selected_nr; i++)
 730                 table[i] = i;
 731
 732         /*
 733          * At the end of this sort table[j] = i means that the i'th
 734          * bitmap corresponds to j'th bitmapped commit (among the selected
 735          * commits) in lex order of OIDs.
 736          */
 737         QSORT_S(table, writer->selected_nr, table_cmp, writer);
 738
 739         /* table_inv helps us discover that relationship (i'th bitmap
 740          * to j'th commit by j = table_inv[i])
 741          */
 742         for (i = 0; i < writer->selected_nr; i++)
 743                 table_inv[table[i]] = i;
 744
 745         trace2_region_enter("pack-bitmap-write", "writing_lookup_table", the_repository);
 746         for (i = 0; i < writer->selected_nr; i++) {
 747                 struct bitmapped_commit *selected = &writer->selected[table[i]];
 748                 uint32_t xor_offset = selected->xor_offset;
 749                 uint32_t xor_row;
 750
 751                 if (xor_offset) {
 752                         /*
 753                          * xor_index stores the index (in the bitmap entries)
 754                          * of the corresponding xor bitmap. But we need to convert
 755                          * this index into lookup table's index. So, table_inv[xor_index]
 756                          * gives us the index position w.r.t. the lookup table.
 757                          *
 758                          * If "k = table[i] - xor_offset" then the xor base is the k'th
 759                          * bitmap. `table_inv[k]` gives us the position of that bitmap
 760                          * in the lookup table.
 761                          */
 762                         uint32_t xor_index = table[i] - xor_offset;
 763                         xor_row = table_inv[xor_index];
 764                 } else {
 765                         xor_row = 0xffffffff;
 766                 }
 767
 768                 hashwrite_be32(f, writer->selected[table[i]].commit_pos);
 769                 hashwrite_be64(f, (uint64_t)offsets[table[i]]);
 770                 hashwrite_be32(f, xor_row);
 771         }
 772         trace2_region_leave("pack-bitmap-write", "writing_lookup_table", the_repository);
 773
 774         free(table);
 775         free(table_inv);
 776 }
 777
 778 static void write_hash_cache(struct hashfile *f,
 779                              struct pack_idx_entry **index,
 780                              uint32_t index_nr)
 781 {
 782         uint32_t i;
 783
 784         for (i = 0; i < index_nr; ++i) {
 785                 struct object_entry *entry = (struct object_entry *)index[i];
 786                 hashwrite_be32(f, entry->hash);
 787         }
 788 }
 789
 790 void bitmap_writer_set_checksum(struct bitmap_writer *writer,
 791                                 const unsigned char *sha1)
 792 {
 793         hashcpy(writer->pack_checksum, sha1);
 794 }
 795
 796 void bitmap_writer_finish(struct bitmap_writer *writer,
 797                           struct pack_idx_entry **index,
 798                           uint32_t index_nr,
 799                           const char *filename,
 800                           uint16_t options)
 801 {
 802         static uint16_t default_version = 1;
 803         static uint16_t flags = BITMAP_OPT_FULL_DAG;
 804         struct strbuf tmp_file = STRBUF_INIT;
 805         struct hashfile *f;
 806         off_t *offsets = NULL;
 807         uint32_t i;
 808
 809         struct bitmap_disk_header header;
 810
 811         int fd = odb_mkstemp(&tmp_file, "pack/tmp_bitmap_XXXXXX");
 812
 813         f = hashfd(fd, tmp_file.buf);
 814
 815         memcpy(header.magic, BITMAP_IDX_SIGNATURE, sizeof(BITMAP_IDX_SIGNATURE));
 816         header.version = htons(default_version);
 817         header.options = htons(flags | options);
 818         header.entry_count = htonl(writer->selected_nr);
 819         hashcpy(header.checksum, writer->pack_checksum);
 820
 821         hashwrite(f, &header, sizeof(header) - GIT_MAX_RAWSZ + the_hash_algo->rawsz);
 822         dump_bitmap(f, writer->commits);
 823         dump_bitmap(f, writer->trees);
 824         dump_bitmap(f, writer->blobs);
 825         dump_bitmap(f, writer->tags);
 826
 827         if (options & BITMAP_OPT_LOOKUP_TABLE)
 828                 CALLOC_ARRAY(offsets, index_nr);
 829
 830         for (i = 0; i < writer->selected_nr; i++) {
 831                 struct bitmapped_commit *stored = &writer->selected[i];
 832                 int commit_pos = oid_pos(&stored->commit->object.oid, index,
 833                                          index_nr, oid_access);
 834
 835                 if (commit_pos < 0)
 836                         BUG(_("trying to write commit not in index"));
 837                 stored->commit_pos = commit_pos;
 838         }
 839
 840         write_selected_commits_v1(writer, f, offsets);
 841
 842         if (options & BITMAP_OPT_LOOKUP_TABLE)
 843                 write_lookup_table(writer, f, offsets);
 844
 845         if (options & BITMAP_OPT_HASH_CACHE)
 846                 write_hash_cache(f, index, index_nr);
 847
 848         finalize_hashfile(f, NULL, FSYNC_COMPONENT_PACK_METADATA,
 849                           CSUM_HASH_IN_STREAM | CSUM_FSYNC | CSUM_CLOSE);
 850
 851         if (adjust_shared_perm(tmp_file.buf))
 852                 die_errno("unable to make temporary bitmap file readable");
 853
 854         if (rename(tmp_file.buf, filename))
 855                 die_errno("unable to rename temporary bitmap file to '%s'", filename);
 856
 857         strbuf_release(&tmp_file);
 858         free(offsets);
 859 }