git.oblomov.eu Git - git/blob - pack-bitmap-write.c

   1 #include "cache.h"
   2 #include "object-store.h"
   3 #include "commit.h"
   4 #include "tag.h"
   5 #include "diff.h"
   6 #include "revision.h"
   7 #include "list-objects.h"
   8 #include "progress.h"
   9 #include "pack-revindex.h"
  10 #include "pack.h"
  11 #include "pack-bitmap.h"
  12 #include "sha1-lookup.h"
  13 #include "pack-objects.h"
  14 #include "commit-reach.h"
  15
  16 struct bitmapped_commit {
  17         struct commit *commit;
  18         struct ewah_bitmap *bitmap;
  19         struct ewah_bitmap *write_as;
  20         int flags;
  21         int xor_offset;
  22         uint32_t commit_pos;
  23 };
  24
  25 struct bitmap_writer {
  26         struct ewah_bitmap *commits;
  27         struct ewah_bitmap *trees;
  28         struct ewah_bitmap *blobs;
  29         struct ewah_bitmap *tags;
  30
  31         kh_oid_map_t *bitmaps;
  32         kh_oid_map_t *reused;
  33         struct packing_data *to_pack;
  34
  35         struct bitmapped_commit *selected;
  36         unsigned int selected_nr, selected_alloc;
  37
  38         struct progress *progress;
  39         int show_progress;
  40         unsigned char pack_checksum[GIT_MAX_RAWSZ];
  41 };
  42
  43 static struct bitmap_writer writer;
  44
  45 void bitmap_writer_show_progress(int show)
  46 {
  47         writer.show_progress = show;
  48 }
  49
  50 /**
  51  * Build the initial type index for the packfile
  52  */
  53 void bitmap_writer_build_type_index(struct packing_data *to_pack,
  54                                     struct pack_idx_entry **index,
  55                                     uint32_t index_nr)
  56 {
  57         uint32_t i;
  58
  59         writer.commits = ewah_new();
  60         writer.trees = ewah_new();
  61         writer.blobs = ewah_new();
  62         writer.tags = ewah_new();
  63         ALLOC_ARRAY(to_pack->in_pack_pos, to_pack->nr_objects);
  64
  65         for (i = 0; i < index_nr; ++i) {
  66                 struct object_entry *entry = (struct object_entry *)index[i];
  67                 enum object_type real_type;
  68
  69                 oe_set_in_pack_pos(to_pack, entry, i);
  70
  71                 switch (oe_type(entry)) {
  72                 case OBJ_COMMIT:
  73                 case OBJ_TREE:
  74                 case OBJ_BLOB:
  75                 case OBJ_TAG:
  76                         real_type = oe_type(entry);
  77                         break;
  78
  79                 default:
  80                         real_type = oid_object_info(to_pack->repo,
  81                                                     &entry->idx.oid, NULL);
  82                         break;
  83                 }
  84
  85                 switch (real_type) {
  86                 case OBJ_COMMIT:
  87                         ewah_set(writer.commits, i);
  88                         break;
  89
  90                 case OBJ_TREE:
  91                         ewah_set(writer.trees, i);
  92                         break;
  93
  94                 case OBJ_BLOB:
  95                         ewah_set(writer.blobs, i);
  96                         break;
  97
  98                 case OBJ_TAG:
  99                         ewah_set(writer.tags, i);
 100                         break;
 101
 102                 default:
 103                         die("Missing type information for %s (%d/%d)",
 104                             oid_to_hex(&entry->idx.oid), real_type,
 105                             oe_type(entry));
 106                 }
 107         }
 108 }
 109
 110 /**
 111  * Compute the actual bitmaps
 112  */
 113
 114 static inline void push_bitmapped_commit(struct commit *commit, struct ewah_bitmap *reused)
 115 {
 116         if (writer.selected_nr >= writer.selected_alloc) {
 117                 writer.selected_alloc = (writer.selected_alloc + 32) * 2;
 118                 REALLOC_ARRAY(writer.selected, writer.selected_alloc);
 119         }
 120
 121         writer.selected[writer.selected_nr].commit = commit;
 122         writer.selected[writer.selected_nr].bitmap = reused;
 123         writer.selected[writer.selected_nr].flags = 0;
 124
 125         writer.selected_nr++;
 126 }
 127
 128 static uint32_t find_object_pos(const struct object_id *oid)
 129 {
 130         struct object_entry *entry = packlist_find(writer.to_pack, oid);
 131
 132         if (!entry) {
 133                 die("Failed to write bitmap index. Packfile doesn't have full closure "
 134                         "(object %s is missing)", oid_to_hex(oid));
 135         }
 136
 137         return oe_in_pack_pos(writer.to_pack, entry);
 138 }
 139
 140 static void compute_xor_offsets(void)
 141 {
 142         static const int MAX_XOR_OFFSET_SEARCH = 10;
 143
 144         int i, next = 0;
 145
 146         while (next < writer.selected_nr) {
 147                 struct bitmapped_commit *stored = &writer.selected[next];
 148
 149                 int best_offset = 0;
 150                 struct ewah_bitmap *best_bitmap = stored->bitmap;
 151                 struct ewah_bitmap *test_xor;
 152
 153                 for (i = 1; i <= MAX_XOR_OFFSET_SEARCH; ++i) {
 154                         int curr = next - i;
 155
 156                         if (curr < 0)
 157                                 break;
 158
 159                         test_xor = ewah_pool_new();
 160                         ewah_xor(writer.selected[curr].bitmap, stored->bitmap, test_xor);
 161
 162                         if (test_xor->buffer_size < best_bitmap->buffer_size) {
 163                                 if (best_bitmap != stored->bitmap)
 164                                         ewah_pool_free(best_bitmap);
 165
 166                                 best_bitmap = test_xor;
 167                                 best_offset = i;
 168                         } else {
 169                                 ewah_pool_free(test_xor);
 170                         }
 171                 }
 172
 173                 stored->xor_offset = best_offset;
 174                 stored->write_as = best_bitmap;
 175
 176                 next++;
 177         }
 178 }
 179
 180 struct bb_commit {
 181         struct commit_list *children;
 182         struct bitmap *bitmap;
 183         unsigned selected:1;
 184         unsigned idx; /* within selected array */
 185 };
 186
 187 define_commit_slab(bb_data, struct bb_commit);
 188
 189 struct bitmap_builder {
 190         struct bb_data data;
 191         struct commit **commits;
 192         size_t commits_nr, commits_alloc;
 193 };
 194
 195 static void bitmap_builder_init(struct bitmap_builder *bb,
 196                                 struct bitmap_writer *writer)
 197 {
 198         struct rev_info revs;
 199         struct commit *commit;
 200         unsigned int i;
 201
 202         memset(bb, 0, sizeof(*bb));
 203         init_bb_data(&bb->data);
 204
 205         reset_revision_walk();
 206         repo_init_revisions(writer->to_pack->repo, &revs, NULL);
 207         revs.topo_order = 1;
 208
 209         for (i = 0; i < writer->selected_nr; i++) {
 210                 struct commit *c = writer->selected[i].commit;
 211                 struct bb_commit *ent = bb_data_at(&bb->data, c);
 212                 ent->selected = 1;
 213                 ent->idx = i;
 214                 add_pending_object(&revs, &c->object, "");
 215         }
 216
 217         if (prepare_revision_walk(&revs))
 218                 die("revision walk setup failed");
 219
 220         while ((commit = get_revision(&revs))) {
 221                 struct commit_list *p;
 222
 223                 parse_commit_or_die(commit);
 224
 225                 ALLOC_GROW(bb->commits, bb->commits_nr + 1, bb->commits_alloc);
 226                 bb->commits[bb->commits_nr++] = commit;
 227
 228                 for (p = commit->parents; p; p = p->next) {
 229                         struct bb_commit *ent = bb_data_at(&bb->data, p->item);
 230                         commit_list_insert(commit, &ent->children);
 231                 }
 232         }
 233 }
 234
 235 static void bitmap_builder_clear(struct bitmap_builder *bb)
 236 {
 237         clear_bb_data(&bb->data);
 238         free(bb->commits);
 239         bb->commits_nr = bb->commits_alloc = 0;
 240 }
 241
 242 static void fill_bitmap_tree(struct bitmap *bitmap,
 243                              struct tree *tree)
 244 {
 245         uint32_t pos;
 246         struct tree_desc desc;
 247         struct name_entry entry;
 248
 249         /*
 250          * If our bit is already set, then there is nothing to do. Both this
 251          * tree and all of its children will be set.
 252          */
 253         pos = find_object_pos(&tree->object.oid);
 254         if (bitmap_get(bitmap, pos))
 255                 return;
 256         bitmap_set(bitmap, pos);
 257
 258         if (parse_tree(tree) < 0)
 259                 die("unable to load tree object %s",
 260                     oid_to_hex(&tree->object.oid));
 261         init_tree_desc(&desc, tree->buffer, tree->size);
 262
 263         while (tree_entry(&desc, &entry)) {
 264                 switch (object_type(entry.mode)) {
 265                 case OBJ_TREE:
 266                         fill_bitmap_tree(bitmap,
 267                                          lookup_tree(the_repository, &entry.oid));
 268                         break;
 269                 case OBJ_BLOB:
 270                         bitmap_set(bitmap, find_object_pos(&entry.oid));
 271                         break;
 272                 default:
 273                         /* Gitlink, etc; not reachable */
 274                         break;
 275                 }
 276         }
 277
 278         free_tree_buffer(tree);
 279 }
 280
 281 static void fill_bitmap_commit(struct bb_commit *ent,
 282                                struct commit *commit)
 283 {
 284         if (!ent->bitmap)
 285                 ent->bitmap = bitmap_new();
 286
 287         /*
 288          * mark ourselves, but do not bother with parents; their values
 289          * will already have been propagated to us
 290          */
 291         bitmap_set(ent->bitmap, find_object_pos(&commit->object.oid));
 292         fill_bitmap_tree(ent->bitmap, get_commit_tree(commit));
 293 }
 294
 295 static void store_selected(struct bb_commit *ent, struct commit *commit)
 296 {
 297         struct bitmapped_commit *stored = &writer.selected[ent->idx];
 298         khiter_t hash_pos;
 299         int hash_ret;
 300
 301         /*
 302          * the "reuse bitmaps" phase may have stored something here, but
 303          * our new algorithm doesn't use it. Drop it.
 304          */
 305         if (stored->bitmap)
 306                 ewah_free(stored->bitmap);
 307
 308         stored->bitmap = bitmap_to_ewah(ent->bitmap);
 309
 310         hash_pos = kh_put_oid_map(writer.bitmaps, commit->object.oid, &hash_ret);
 311         if (hash_ret == 0)
 312                 die("Duplicate entry when writing index: %s",
 313                     oid_to_hex(&commit->object.oid));
 314         kh_value(writer.bitmaps, hash_pos) = stored;
 315 }
 316
 317 void bitmap_writer_build(struct packing_data *to_pack)
 318 {
 319         struct bitmap_builder bb;
 320         size_t i;
 321         int nr_stored = 0; /* for progress */
 322
 323         writer.bitmaps = kh_init_oid_map();
 324         writer.to_pack = to_pack;
 325
 326         if (writer.show_progress)
 327                 writer.progress = start_progress("Building bitmaps", writer.selected_nr);
 328         trace2_region_enter("pack-bitmap-write", "building_bitmaps_total",
 329                             the_repository);
 330
 331         bitmap_builder_init(&bb, &writer);
 332         for (i = bb.commits_nr; i > 0; i--) {
 333                 struct commit *commit = bb.commits[i-1];
 334                 struct bb_commit *ent = bb_data_at(&bb.data, commit);
 335                 struct commit *child;
 336
 337                 fill_bitmap_commit(ent, commit);
 338
 339                 if (ent->selected) {
 340                         store_selected(ent, commit);
 341                         nr_stored++;
 342                         display_progress(writer.progress, nr_stored);
 343                 }
 344
 345                 while ((child = pop_commit(&ent->children))) {
 346                         struct bb_commit *child_ent =
 347                                 bb_data_at(&bb.data, child);
 348
 349                         if (child_ent->bitmap)
 350                                 bitmap_or(child_ent->bitmap, ent->bitmap);
 351                         else
 352                                 child_ent->bitmap = bitmap_dup(ent->bitmap);
 353                 }
 354                 bitmap_free(ent->bitmap);
 355                 ent->bitmap = NULL;
 356         }
 357         bitmap_builder_clear(&bb);
 358
 359         trace2_region_leave("pack-bitmap-write", "building_bitmaps_total",
 360                             the_repository);
 361
 362         stop_progress(&writer.progress);
 363
 364         compute_xor_offsets();
 365 }
 366
 367 /**
 368  * Select the commits that will be bitmapped
 369  */
 370 static inline unsigned int next_commit_index(unsigned int idx)
 371 {
 372         static const unsigned int MIN_COMMITS = 100;
 373         static const unsigned int MAX_COMMITS = 5000;
 374
 375         static const unsigned int MUST_REGION = 100;
 376         static const unsigned int MIN_REGION = 20000;
 377
 378         unsigned int offset, next;
 379
 380         if (idx <= MUST_REGION)
 381                 return 0;
 382
 383         if (idx <= MIN_REGION) {
 384                 offset = idx - MUST_REGION;
 385                 return (offset < MIN_COMMITS) ? offset : MIN_COMMITS;
 386         }
 387
 388         offset = idx - MIN_REGION;
 389         next = (offset < MAX_COMMITS) ? offset : MAX_COMMITS;
 390
 391         return (next > MIN_COMMITS) ? next : MIN_COMMITS;
 392 }
 393
 394 static int date_compare(const void *_a, const void *_b)
 395 {
 396         struct commit *a = *(struct commit **)_a;
 397         struct commit *b = *(struct commit **)_b;
 398         return (long)b->date - (long)a->date;
 399 }
 400
 401 void bitmap_writer_reuse_bitmaps(struct packing_data *to_pack)
 402 {
 403         struct bitmap_index *bitmap_git;
 404         if (!(bitmap_git = prepare_bitmap_git(to_pack->repo)))
 405                 return;
 406
 407         writer.reused = kh_init_oid_map();
 408         rebuild_existing_bitmaps(bitmap_git, to_pack, writer.reused,
 409                                  writer.show_progress);
 410         /*
 411          * NEEDSWORK: rebuild_existing_bitmaps() makes writer.reused reference
 412          * some bitmaps in bitmap_git, so we can't free the latter.
 413          */
 414 }
 415
 416 static struct ewah_bitmap *find_reused_bitmap(const struct object_id *oid)
 417 {
 418         khiter_t hash_pos;
 419
 420         if (!writer.reused)
 421                 return NULL;
 422
 423         hash_pos = kh_get_oid_map(writer.reused, *oid);
 424         if (hash_pos >= kh_end(writer.reused))
 425                 return NULL;
 426
 427         return kh_value(writer.reused, hash_pos);
 428 }
 429
 430 void bitmap_writer_select_commits(struct commit **indexed_commits,
 431                                   unsigned int indexed_commits_nr,
 432                                   int max_bitmaps)
 433 {
 434         unsigned int i = 0, j, next;
 435
 436         QSORT(indexed_commits, indexed_commits_nr, date_compare);
 437
 438         if (writer.show_progress)
 439                 writer.progress = start_progress("Selecting bitmap commits", 0);
 440
 441         if (indexed_commits_nr < 100) {
 442                 for (i = 0; i < indexed_commits_nr; ++i)
 443                         push_bitmapped_commit(indexed_commits[i], NULL);
 444                 return;
 445         }
 446
 447         for (;;) {
 448                 struct ewah_bitmap *reused_bitmap = NULL;
 449                 struct commit *chosen = NULL;
 450
 451                 next = next_commit_index(i);
 452
 453                 if (i + next >= indexed_commits_nr)
 454                         break;
 455
 456                 if (max_bitmaps > 0 && writer.selected_nr >= max_bitmaps) {
 457                         writer.selected_nr = max_bitmaps;
 458                         break;
 459                 }
 460
 461                 if (next == 0) {
 462                         chosen = indexed_commits[i];
 463                         reused_bitmap = find_reused_bitmap(&chosen->object.oid);
 464                 } else {
 465                         chosen = indexed_commits[i + next];
 466
 467                         for (j = 0; j <= next; ++j) {
 468                                 struct commit *cm = indexed_commits[i + j];
 469
 470                                 reused_bitmap = find_reused_bitmap(&cm->object.oid);
 471                                 if (reused_bitmap || (cm->object.flags & NEEDS_BITMAP) != 0) {
 472                                         chosen = cm;
 473                                         break;
 474                                 }
 475
 476                                 if (cm->parents && cm->parents->next)
 477                                         chosen = cm;
 478                         }
 479                 }
 480
 481                 push_bitmapped_commit(chosen, reused_bitmap);
 482
 483                 i += next + 1;
 484                 display_progress(writer.progress, i);
 485         }
 486
 487         stop_progress(&writer.progress);
 488 }
 489
 490
 491 static int hashwrite_ewah_helper(void *f, const void *buf, size_t len)
 492 {
 493         /* hashwrite will die on error */
 494         hashwrite(f, buf, len);
 495         return len;
 496 }
 497
 498 /**
 499  * Write the bitmap index to disk
 500  */
 501 static inline void dump_bitmap(struct hashfile *f, struct ewah_bitmap *bitmap)
 502 {
 503         if (ewah_serialize_to(bitmap, hashwrite_ewah_helper, f) < 0)
 504                 die("Failed to write bitmap index");
 505 }
 506
 507 static const unsigned char *sha1_access(size_t pos, void *table)
 508 {
 509         struct pack_idx_entry **index = table;
 510         return index[pos]->oid.hash;
 511 }
 512
 513 static void write_selected_commits_v1(struct hashfile *f,
 514                                       struct pack_idx_entry **index,
 515                                       uint32_t index_nr)
 516 {
 517         int i;
 518
 519         for (i = 0; i < writer.selected_nr; ++i) {
 520                 struct bitmapped_commit *stored = &writer.selected[i];
 521
 522                 int commit_pos =
 523                         sha1_pos(stored->commit->object.oid.hash, index, index_nr, sha1_access);
 524
 525                 if (commit_pos < 0)
 526                         BUG("trying to write commit not in index");
 527
 528                 hashwrite_be32(f, commit_pos);
 529                 hashwrite_u8(f, stored->xor_offset);
 530                 hashwrite_u8(f, stored->flags);
 531
 532                 dump_bitmap(f, stored->write_as);
 533         }
 534 }
 535
 536 static void write_hash_cache(struct hashfile *f,
 537                              struct pack_idx_entry **index,
 538                              uint32_t index_nr)
 539 {
 540         uint32_t i;
 541
 542         for (i = 0; i < index_nr; ++i) {
 543                 struct object_entry *entry = (struct object_entry *)index[i];
 544                 hashwrite_be32(f, entry->hash);
 545         }
 546 }
 547
 548 void bitmap_writer_set_checksum(unsigned char *sha1)
 549 {
 550         hashcpy(writer.pack_checksum, sha1);
 551 }
 552
 553 void bitmap_writer_finish(struct pack_idx_entry **index,
 554                           uint32_t index_nr,
 555                           const char *filename,
 556                           uint16_t options)
 557 {
 558         static uint16_t default_version = 1;
 559         static uint16_t flags = BITMAP_OPT_FULL_DAG;
 560         struct strbuf tmp_file = STRBUF_INIT;
 561         struct hashfile *f;
 562
 563         struct bitmap_disk_header header;
 564
 565         int fd = odb_mkstemp(&tmp_file, "pack/tmp_bitmap_XXXXXX");
 566
 567         f = hashfd(fd, tmp_file.buf);
 568
 569         memcpy(header.magic, BITMAP_IDX_SIGNATURE, sizeof(BITMAP_IDX_SIGNATURE));
 570         header.version = htons(default_version);
 571         header.options = htons(flags | options);
 572         header.entry_count = htonl(writer.selected_nr);
 573         hashcpy(header.checksum, writer.pack_checksum);
 574
 575         hashwrite(f, &header, sizeof(header) - GIT_MAX_RAWSZ + the_hash_algo->rawsz);
 576         dump_bitmap(f, writer.commits);
 577         dump_bitmap(f, writer.trees);
 578         dump_bitmap(f, writer.blobs);
 579         dump_bitmap(f, writer.tags);
 580         write_selected_commits_v1(f, index, index_nr);
 581
 582         if (options & BITMAP_OPT_HASH_CACHE)
 583                 write_hash_cache(f, index, index_nr);
 584
 585         finalize_hashfile(f, NULL, CSUM_HASH_IN_STREAM | CSUM_FSYNC | CSUM_CLOSE);
 586
 587         if (adjust_shared_perm(tmp_file.buf))
 588                 die_errno("unable to make temporary bitmap file readable");
 589
 590         if (rename(tmp_file.buf, filename))
 591                 die_errno("unable to rename temporary bitmap file to '%s'", filename);
 592
 593         strbuf_release(&tmp_file);
 594 }