| 1 | #define DISABLE_SIGN_COMPARE_WARNINGS |
| 2 | |
| 3 | #include "git-compat-util.h" |
| 4 | #include "environment.h" |
| 5 | #include "gettext.h" |
| 6 | #include "hex.h" |
| 7 | #include "odb.h" |
| 8 | #include "commit.h" |
| 9 | #include "diff.h" |
| 10 | #include "revision.h" |
| 11 | #include "progress.h" |
| 12 | #include "pack.h" |
| 13 | #include "pack-bitmap.h" |
| 14 | #include "hash-lookup.h" |
| 15 | #include "pack-objects.h" |
| 16 | #include "path.h" |
| 17 | #include "commit-reach.h" |
| 18 | #include "prio-queue.h" |
| 19 | #include "trace2.h" |
| 20 | #include "tree.h" |
| 21 | #include "tree-walk.h" |
| 22 | #include "pseudo-merge.h" |
| 23 | #include "oid-array.h" |
| 24 | #include "config.h" |
| 25 | #include "alloc.h" |
| 26 | #include "refs.h" |
| 27 | #include "strmap.h" |
| 28 | #include "midx.h" |
| 29 | #include "pack-revindex.h" |
| 30 | |
| 31 | struct bitmapped_commit { |
| 32 | struct commit *commit; |
| 33 | struct ewah_bitmap *bitmap; |
| 34 | struct ewah_bitmap *write_as; |
| 35 | struct ewah_bitmap *pseudo_merge_parents; |
| 36 | int flags; |
| 37 | int xor_offset; |
| 38 | uint32_t commit_pos; |
| 39 | unsigned pseudo_merge : 1; |
| 40 | }; |
| 41 | |
| 42 | static inline int bitmap_writer_nr_selected_commits(struct bitmap_writer *writer) |
| 43 | { |
| 44 | return writer->selected_nr - writer->pseudo_merges_nr; |
| 45 | } |
| 46 | |
| 47 | void bitmap_writer_init(struct bitmap_writer *writer, struct repository *r, |
| 48 | struct packing_data *pdata, |
| 49 | struct multi_pack_index *midx) |
| 50 | { |
| 51 | memset(writer, 0, sizeof(struct bitmap_writer)); |
| 52 | if (writer->bitmaps) |
| 53 | BUG("bitmap writer already initialized"); |
| 54 | writer->repo = r; |
| 55 | writer->bitmaps = kh_init_oid_map(); |
| 56 | writer->pseudo_merge_commits = kh_init_oid_map(); |
| 57 | writer->to_pack = pdata; |
| 58 | writer->midx = midx; |
| 59 | |
| 60 | string_list_init_dup(&writer->pseudo_merge_groups); |
| 61 | |
| 62 | load_pseudo_merges_from_config(r, &writer->pseudo_merge_groups); |
| 63 | } |
| 64 | |
| 65 | static void free_pseudo_merge_commit_idx(struct pseudo_merge_commit_idx *idx) |
| 66 | { |
| 67 | if (!idx) |
| 68 | return; |
| 69 | free(idx->pseudo_merge); |
| 70 | free(idx); |
| 71 | } |
| 72 | |
| 73 | static void pseudo_merge_group_release_cb(void *payload, const char *name UNUSED) |
| 74 | { |
| 75 | pseudo_merge_group_release(payload); |
| 76 | free(payload); |
| 77 | } |
| 78 | |
| 79 | void bitmap_writer_free(struct bitmap_writer *writer) |
| 80 | { |
| 81 | uint32_t i; |
| 82 | struct pseudo_merge_commit_idx *idx; |
| 83 | |
| 84 | if (!writer) |
| 85 | return; |
| 86 | |
| 87 | ewah_free(writer->commits); |
| 88 | ewah_free(writer->trees); |
| 89 | ewah_free(writer->blobs); |
| 90 | ewah_free(writer->tags); |
| 91 | |
| 92 | kh_destroy_oid_map(writer->bitmaps); |
| 93 | free(writer->pos_cache); |
| 94 | |
| 95 | kh_foreach_value(writer->pseudo_merge_commits, idx, |
| 96 | free_pseudo_merge_commit_idx(idx)); |
| 97 | kh_destroy_oid_map(writer->pseudo_merge_commits); |
| 98 | string_list_clear_func(&writer->pseudo_merge_groups, |
| 99 | pseudo_merge_group_release_cb); |
| 100 | |
| 101 | for (i = 0; i < writer->selected_nr; i++) { |
| 102 | struct bitmapped_commit *bc = &writer->selected[i]; |
| 103 | if (bc->write_as != bc->bitmap) |
| 104 | ewah_free(bc->write_as); |
| 105 | ewah_free(bc->bitmap); |
| 106 | ewah_free(bc->pseudo_merge_parents); |
| 107 | } |
| 108 | free(writer->selected); |
| 109 | } |
| 110 | |
| 111 | void bitmap_writer_show_progress(struct bitmap_writer *writer, int show) |
| 112 | { |
| 113 | writer->show_progress = show; |
| 114 | } |
| 115 | |
| 116 | /** |
| 117 | * Build the initial type index for the packfile or multi-pack-index |
| 118 | */ |
| 119 | void bitmap_writer_build_type_index(struct bitmap_writer *writer, |
| 120 | struct pack_idx_entry **index) |
| 121 | { |
| 122 | uint32_t i; |
| 123 | uint32_t base_objects = 0; |
| 124 | |
| 125 | if (writer->midx) |
| 126 | base_objects = writer->midx->num_objects + |
| 127 | writer->midx->num_objects_in_base; |
| 128 | |
| 129 | writer->commits = ewah_new(); |
| 130 | writer->trees = ewah_new(); |
| 131 | writer->blobs = ewah_new(); |
| 132 | writer->tags = ewah_new(); |
| 133 | ALLOC_ARRAY(writer->to_pack->in_pack_pos, writer->to_pack->nr_objects); |
| 134 | |
| 135 | for (i = 0; i < writer->to_pack->nr_objects; ++i) { |
| 136 | struct object_entry *entry = (struct object_entry *)index[i]; |
| 137 | enum object_type real_type; |
| 138 | |
| 139 | oe_set_in_pack_pos(writer->to_pack, entry, i); |
| 140 | |
| 141 | switch (oe_type(entry)) { |
| 142 | case OBJ_COMMIT: |
| 143 | case OBJ_TREE: |
| 144 | case OBJ_BLOB: |
| 145 | case OBJ_TAG: |
| 146 | real_type = oe_type(entry); |
| 147 | break; |
| 148 | |
| 149 | default: |
| 150 | real_type = odb_read_object_info(writer->to_pack->repo->objects, |
| 151 | &entry->idx.oid, NULL); |
| 152 | break; |
| 153 | } |
| 154 | |
| 155 | switch (real_type) { |
| 156 | case OBJ_COMMIT: |
| 157 | ewah_set(writer->commits, i + base_objects); |
| 158 | break; |
| 159 | |
| 160 | case OBJ_TREE: |
| 161 | ewah_set(writer->trees, i + base_objects); |
| 162 | break; |
| 163 | |
| 164 | case OBJ_BLOB: |
| 165 | ewah_set(writer->blobs, i + base_objects); |
| 166 | break; |
| 167 | |
| 168 | case OBJ_TAG: |
| 169 | ewah_set(writer->tags, i + base_objects); |
| 170 | break; |
| 171 | |
| 172 | default: |
| 173 | die("Missing type information for %s (%d/%d)", |
| 174 | oid_to_hex(&entry->idx.oid), real_type, |
| 175 | oe_type(entry)); |
| 176 | } |
| 177 | } |
| 178 | } |
| 179 | |
| 180 | int bitmap_writer_has_bitmapped_object_id(struct bitmap_writer *writer, |
| 181 | const struct object_id *oid) |
| 182 | { |
| 183 | return kh_get_oid_map(writer->bitmaps, *oid) != kh_end(writer->bitmaps); |
| 184 | } |
| 185 | |
| 186 | /** |
| 187 | * Compute the actual bitmaps |
| 188 | */ |
| 189 | |
| 190 | void bitmap_writer_push_commit(struct bitmap_writer *writer, |
| 191 | struct commit *commit, unsigned pseudo_merge) |
| 192 | { |
| 193 | if (writer->selected_nr >= writer->selected_alloc) { |
| 194 | writer->selected_alloc = (writer->selected_alloc + 32) * 2; |
| 195 | REALLOC_ARRAY(writer->selected, writer->selected_alloc); |
| 196 | } |
| 197 | |
| 198 | if (!pseudo_merge) { |
| 199 | int hash_ret; |
| 200 | khiter_t hash_pos = kh_put_oid_map(writer->bitmaps, |
| 201 | commit->object.oid, |
| 202 | &hash_ret); |
| 203 | |
| 204 | if (!hash_ret) |
| 205 | die(_("duplicate entry when writing bitmap index: %s"), |
| 206 | oid_to_hex(&commit->object.oid)); |
| 207 | kh_value(writer->bitmaps, hash_pos) = NULL; |
| 208 | } |
| 209 | |
| 210 | writer->selected[writer->selected_nr].commit = commit; |
| 211 | writer->selected[writer->selected_nr].bitmap = NULL; |
| 212 | writer->selected[writer->selected_nr].write_as = NULL; |
| 213 | writer->selected[writer->selected_nr].flags = 0; |
| 214 | writer->selected[writer->selected_nr].pseudo_merge = pseudo_merge; |
| 215 | writer->selected[writer->selected_nr].pseudo_merge_parents = NULL; |
| 216 | |
| 217 | writer->selected_nr++; |
| 218 | } |
| 219 | |
| 220 | struct bitmap_pos_cache_entry { |
| 221 | struct object_id oid; |
| 222 | uint32_t pos; |
| 223 | }; |
| 224 | |
| 225 | #define BITMAP_POS_MIN_CACHE_SIZE (1U << 10) |
| 226 | #define BITMAP_POS_MAX_CACHE_SIZE (1U << 21) |
| 227 | #define BITMAP_POS_CACHE_VALID (1U << 31) |
| 228 | |
| 229 | static void bitmap_writer_init_pos_cache(struct bitmap_writer *writer) |
| 230 | { |
| 231 | if (writer->pos_cache) |
| 232 | return; |
| 233 | |
| 234 | writer->pos_cache_nr = BITMAP_POS_MIN_CACHE_SIZE; |
| 235 | |
| 236 | while (writer->pos_cache_nr < writer->to_pack->nr_objects && |
| 237 | writer->pos_cache_nr < BITMAP_POS_MAX_CACHE_SIZE) |
| 238 | writer->pos_cache_nr <<= 1; |
| 239 | |
| 240 | CALLOC_ARRAY(writer->pos_cache, writer->pos_cache_nr); |
| 241 | } |
| 242 | |
| 243 | static size_t bitmap_writer_pos_cache_slot(struct bitmap_writer *writer, |
| 244 | const struct object_id *oid) |
| 245 | { |
| 246 | return oidhash(oid) & (writer->pos_cache_nr - 1); |
| 247 | } |
| 248 | |
| 249 | static bool bitmap_writer_pos_cache_valid(struct bitmap_writer *writer, |
| 250 | size_t slot) |
| 251 | { |
| 252 | return !!(writer->pos_cache[slot].pos & BITMAP_POS_CACHE_VALID); |
| 253 | } |
| 254 | |
| 255 | static int find_cached_object_pos(struct bitmap_writer *writer, |
| 256 | const struct object_id *oid, uint32_t *pos) |
| 257 | { |
| 258 | size_t slot = bitmap_writer_pos_cache_slot(writer, oid); |
| 259 | |
| 260 | if (bitmap_writer_pos_cache_valid(writer, slot) && |
| 261 | oideq(&writer->pos_cache[slot].oid, oid)) { |
| 262 | writer->pos_cache_hits++; |
| 263 | *pos = writer->pos_cache[slot].pos & ~BITMAP_POS_CACHE_VALID; |
| 264 | return 1; |
| 265 | } |
| 266 | |
| 267 | writer->pos_cache_misses++; |
| 268 | return 0; |
| 269 | } |
| 270 | |
| 271 | static uint32_t store_cached_object_pos(struct bitmap_writer *writer, |
| 272 | const struct object_id *oid, |
| 273 | uint32_t pos) |
| 274 | { |
| 275 | size_t slot; |
| 276 | |
| 277 | if (pos & BITMAP_POS_CACHE_VALID) |
| 278 | return pos; /* too large to cache */ |
| 279 | |
| 280 | slot = bitmap_writer_pos_cache_slot(writer, oid); |
| 281 | |
| 282 | oidcpy(&writer->pos_cache[slot].oid, oid); |
| 283 | writer->pos_cache[slot].pos = pos | BITMAP_POS_CACHE_VALID; |
| 284 | |
| 285 | return pos; |
| 286 | } |
| 287 | |
| 288 | static uint32_t find_object_pos(struct bitmap_writer *writer, |
| 289 | const struct object_id *oid, int *found) |
| 290 | { |
| 291 | struct object_entry *entry; |
| 292 | uint32_t pos; |
| 293 | |
| 294 | bitmap_writer_init_pos_cache(writer); |
| 295 | |
| 296 | if (find_cached_object_pos(writer, oid, &pos)) { |
| 297 | if (found) |
| 298 | *found = 1; |
| 299 | return pos; |
| 300 | } |
| 301 | |
| 302 | entry = packlist_find(writer->to_pack, oid); |
| 303 | if (entry) { |
| 304 | uint32_t base_objects = 0; |
| 305 | |
| 306 | if (writer->midx) |
| 307 | base_objects = writer->midx->num_objects + |
| 308 | writer->midx->num_objects_in_base; |
| 309 | pos = oe_in_pack_pos(writer->to_pack, entry) + base_objects; |
| 310 | } else if (writer->midx) { |
| 311 | uint32_t at; |
| 312 | |
| 313 | if (!bsearch_midx(oid, writer->midx, &at)) |
| 314 | goto missing; |
| 315 | if (midx_to_pack_pos(writer->midx, at, &pos) < 0) |
| 316 | goto missing; |
| 317 | } else { |
| 318 | goto missing; |
| 319 | } |
| 320 | |
| 321 | if (found) |
| 322 | *found = 1; |
| 323 | return store_cached_object_pos(writer, oid, pos); |
| 324 | |
| 325 | missing: |
| 326 | if (found) |
| 327 | *found = 0; |
| 328 | warning("Failed to write bitmap index. Packfile doesn't have full closure " |
| 329 | "(object %s is missing)", oid_to_hex(oid)); |
| 330 | return 0; |
| 331 | } |
| 332 | |
| 333 | static int bitmapped_commit_date_cmp(const void *_a, const void *_b) |
| 334 | { |
| 335 | const struct bitmapped_commit *a = _a; |
| 336 | const struct bitmapped_commit *b = _b; |
| 337 | |
| 338 | if (a->commit->date < b->commit->date) |
| 339 | return -1; |
| 340 | if (a->commit->date > b->commit->date) |
| 341 | return 1; |
| 342 | return 0; |
| 343 | } |
| 344 | |
| 345 | static void compute_xor_offsets(struct bitmap_writer *writer) |
| 346 | { |
| 347 | static const int MAX_XOR_OFFSET_SEARCH = 10; |
| 348 | |
| 349 | int i, next = 0; |
| 350 | int nr = bitmap_writer_nr_selected_commits(writer); |
| 351 | |
| 352 | if (nr > 1) { |
| 353 | QSORT(writer->selected, nr, bitmapped_commit_date_cmp); |
| 354 | |
| 355 | for (i = 0; i < nr; i++) { |
| 356 | struct bitmapped_commit *stored = &writer->selected[i]; |
| 357 | khiter_t hash_pos = kh_get_oid_map(writer->bitmaps, |
| 358 | stored->commit->object.oid); |
| 359 | |
| 360 | if (hash_pos == kh_end(writer->bitmaps)) |
| 361 | BUG("selected commit missing from bitmap map: %s", |
| 362 | oid_to_hex(&stored->commit->object.oid)); |
| 363 | |
| 364 | kh_value(writer->bitmaps, hash_pos) = stored; |
| 365 | } |
| 366 | } |
| 367 | |
| 368 | while (next < writer->selected_nr) { |
| 369 | struct bitmapped_commit *stored = &writer->selected[next]; |
| 370 | int best_offset = 0; |
| 371 | struct ewah_bitmap *best_bitmap = stored->bitmap; |
| 372 | struct ewah_bitmap *test_xor; |
| 373 | |
| 374 | if (stored->pseudo_merge) |
| 375 | goto next; |
| 376 | |
| 377 | for (i = 1; i <= MAX_XOR_OFFSET_SEARCH; ++i) { |
| 378 | int curr = next - i; |
| 379 | |
| 380 | if (curr < 0) |
| 381 | break; |
| 382 | if (writer->selected[curr].pseudo_merge) |
| 383 | continue; |
| 384 | |
| 385 | test_xor = ewah_pool_new(); |
| 386 | ewah_xor(writer->selected[curr].bitmap, stored->bitmap, test_xor); |
| 387 | |
| 388 | if (test_xor->buffer_size < best_bitmap->buffer_size) { |
| 389 | if (best_bitmap != stored->bitmap) |
| 390 | ewah_pool_free(best_bitmap); |
| 391 | |
| 392 | best_bitmap = test_xor; |
| 393 | best_offset = i; |
| 394 | } else { |
| 395 | ewah_pool_free(test_xor); |
| 396 | } |
| 397 | } |
| 398 | |
| 399 | next: |
| 400 | stored->xor_offset = best_offset; |
| 401 | stored->write_as = best_bitmap; |
| 402 | |
| 403 | next++; |
| 404 | } |
| 405 | } |
| 406 | |
| 407 | struct bb_commit { |
| 408 | struct commit_list *reverse_edges; |
| 409 | struct bitmap *commit_mask; |
| 410 | struct bitmap *bitmap; |
| 411 | unsigned selected:1, |
| 412 | maximal:1, |
| 413 | pseudo_merge:1; |
| 414 | unsigned idx; /* within selected array */ |
| 415 | }; |
| 416 | |
| 417 | static void clear_bb_commit(struct bb_commit *commit) |
| 418 | { |
| 419 | commit_list_free(commit->reverse_edges); |
| 420 | bitmap_free(commit->commit_mask); |
| 421 | bitmap_free(commit->bitmap); |
| 422 | } |
| 423 | |
| 424 | define_commit_slab(bb_data, struct bb_commit); |
| 425 | |
| 426 | struct bitmap_builder { |
| 427 | struct bb_data data; |
| 428 | struct commit_stack commits; |
| 429 | }; |
| 430 | |
| 431 | static void bitmap_builder_init(struct bitmap_builder *bb, |
| 432 | struct bitmap_writer *writer, |
| 433 | struct bitmap_index *old_bitmap) |
| 434 | { |
| 435 | struct rev_info revs; |
| 436 | struct commit *commit; |
| 437 | struct commit_list *reusable = NULL; |
| 438 | struct commit_list *r; |
| 439 | unsigned int i, num_maximal = 0; |
| 440 | |
| 441 | init_bb_data(&bb->data); |
| 442 | commit_stack_init(&bb->commits); |
| 443 | |
| 444 | reset_revision_walk(); |
| 445 | repo_init_revisions(writer->to_pack->repo, &revs, NULL); |
| 446 | revs.topo_order = 1; |
| 447 | revs.first_parent_only = 1; |
| 448 | |
| 449 | for (i = 0; i < bitmap_writer_nr_selected_commits(writer); i++) { |
| 450 | struct bitmapped_commit *bc = &writer->selected[i]; |
| 451 | struct bb_commit *ent = bb_data_at(&bb->data, bc->commit); |
| 452 | |
| 453 | if (bc->pseudo_merge) |
| 454 | BUG("unexpected pseudo-merge at %"PRIuMAX, |
| 455 | (uintmax_t)i); |
| 456 | |
| 457 | ent->selected = 1; |
| 458 | ent->maximal = 1; |
| 459 | ent->pseudo_merge = 0; |
| 460 | ent->idx = i; |
| 461 | |
| 462 | ent->commit_mask = bitmap_new(); |
| 463 | bitmap_set(ent->commit_mask, i); |
| 464 | |
| 465 | add_pending_object(&revs, &bc->commit->object, ""); |
| 466 | } |
| 467 | |
| 468 | if (prepare_revision_walk(&revs)) |
| 469 | die("revision walk setup failed"); |
| 470 | |
| 471 | while ((commit = get_revision(&revs))) { |
| 472 | struct commit_list *p = commit->parents; |
| 473 | struct bb_commit *c_ent; |
| 474 | |
| 475 | parse_commit_or_die(commit); |
| 476 | |
| 477 | c_ent = bb_data_at(&bb->data, commit); |
| 478 | |
| 479 | /* |
| 480 | * If there is no commit_mask, there is no reason to iterate |
| 481 | * over this commit; it is not selected (if it were, it would |
| 482 | * not have a blank commit mask) and all its children have |
| 483 | * existing bitmaps (see the comment starting with "This commit |
| 484 | * has an existing bitmap" below), so it does not contribute |
| 485 | * anything to the final bitmap file or its descendants. |
| 486 | */ |
| 487 | if (!c_ent->commit_mask) |
| 488 | continue; |
| 489 | |
| 490 | if (old_bitmap && bitmap_for_commit(old_bitmap, commit)) { |
| 491 | /* |
| 492 | * This commit has an existing bitmap, so we can |
| 493 | * get its bits immediately without an object |
| 494 | * walk. That is, it is reusable as-is and there is no |
| 495 | * need to continue walking beyond it. |
| 496 | * |
| 497 | * Mark it as such and add it to bb->commits separately |
| 498 | * to avoid allocating a position in the commit mask. |
| 499 | */ |
| 500 | commit_list_insert(commit, &reusable); |
| 501 | goto next; |
| 502 | } |
| 503 | |
| 504 | if (c_ent->maximal) { |
| 505 | num_maximal++; |
| 506 | commit_stack_push(&bb->commits, commit); |
| 507 | } |
| 508 | |
| 509 | if (p) { |
| 510 | struct bb_commit *p_ent = bb_data_at(&bb->data, p->item); |
| 511 | int c_not_p, p_not_c; |
| 512 | |
| 513 | if (!p_ent->commit_mask) { |
| 514 | p_ent->commit_mask = bitmap_new(); |
| 515 | c_not_p = 1; |
| 516 | p_not_c = 0; |
| 517 | } else { |
| 518 | c_not_p = bitmap_is_subset(c_ent->commit_mask, p_ent->commit_mask); |
| 519 | p_not_c = bitmap_is_subset(p_ent->commit_mask, c_ent->commit_mask); |
| 520 | } |
| 521 | |
| 522 | if (!c_not_p) |
| 523 | continue; |
| 524 | |
| 525 | bitmap_or(p_ent->commit_mask, c_ent->commit_mask); |
| 526 | |
| 527 | if (p_not_c) |
| 528 | p_ent->maximal = 1; |
| 529 | else { |
| 530 | p_ent->maximal = 0; |
| 531 | commit_list_free(p_ent->reverse_edges); |
| 532 | p_ent->reverse_edges = NULL; |
| 533 | } |
| 534 | |
| 535 | if (c_ent->maximal) { |
| 536 | commit_list_insert(commit, &p_ent->reverse_edges); |
| 537 | } else { |
| 538 | struct commit_list *cc = c_ent->reverse_edges; |
| 539 | |
| 540 | for (; cc; cc = cc->next) { |
| 541 | if (!commit_list_contains(cc->item, p_ent->reverse_edges)) |
| 542 | commit_list_insert(cc->item, &p_ent->reverse_edges); |
| 543 | } |
| 544 | } |
| 545 | } |
| 546 | |
| 547 | next: |
| 548 | bitmap_free(c_ent->commit_mask); |
| 549 | c_ent->commit_mask = NULL; |
| 550 | } |
| 551 | |
| 552 | for (r = reusable; r; r = r->next) { |
| 553 | commit_stack_push(&bb->commits, r->item); |
| 554 | } |
| 555 | |
| 556 | trace2_data_intmax("pack-bitmap-write", writer->repo, |
| 557 | "num_selected_commits", writer->selected_nr); |
| 558 | trace2_data_intmax("pack-bitmap-write", writer->repo, |
| 559 | "num_maximal_commits", num_maximal); |
| 560 | |
| 561 | release_revisions(&revs); |
| 562 | commit_list_free(reusable); |
| 563 | } |
| 564 | |
| 565 | static void bitmap_builder_clear(struct bitmap_builder *bb) |
| 566 | { |
| 567 | deep_clear_bb_data(&bb->data, clear_bb_commit); |
| 568 | commit_stack_clear(&bb->commits); |
| 569 | } |
| 570 | |
| 571 | static int fill_bitmap_tree(struct bitmap_writer *writer, |
| 572 | struct bitmap *bitmap, |
| 573 | struct tree *tree, |
| 574 | uint32_t pos) |
| 575 | { |
| 576 | int found; |
| 577 | struct tree_desc desc; |
| 578 | struct name_entry entry; |
| 579 | |
| 580 | bitmap_set(bitmap, pos); |
| 581 | |
| 582 | if (repo_parse_tree(writer->repo, tree) < 0) |
| 583 | die("unable to load tree object %s", |
| 584 | oid_to_hex(&tree->object.oid)); |
| 585 | init_tree_desc(&desc, &tree->object.oid, tree->buffer, tree->size); |
| 586 | |
| 587 | while (tree_entry(&desc, &entry)) { |
| 588 | switch (object_type(entry.mode)) { |
| 589 | case OBJ_TREE: |
| 590 | pos = find_object_pos(writer, &entry.oid, &found); |
| 591 | if (!found) |
| 592 | return -1; |
| 593 | if (bitmap_get(bitmap, pos)) { |
| 594 | /* |
| 595 | * If our bit is already set, then there |
| 596 | * is nothing to do. Both this tree and |
| 597 | * all of its children will be set. |
| 598 | */ |
| 599 | break; |
| 600 | } |
| 601 | |
| 602 | if (fill_bitmap_tree(writer, bitmap, |
| 603 | lookup_tree(writer->repo, |
| 604 | &entry.oid), pos) < 0) |
| 605 | return -1; |
| 606 | break; |
| 607 | case OBJ_BLOB: |
| 608 | pos = find_object_pos(writer, &entry.oid, &found); |
| 609 | if (!found) |
| 610 | return -1; |
| 611 | bitmap_set(bitmap, pos); |
| 612 | break; |
| 613 | default: |
| 614 | /* Gitlink, etc; not reachable */ |
| 615 | break; |
| 616 | } |
| 617 | } |
| 618 | |
| 619 | free_tree_buffer(tree); |
| 620 | return 0; |
| 621 | } |
| 622 | |
| 623 | static int reused_bitmaps_nr; |
| 624 | static int reused_pseudo_merge_bitmaps_nr; |
| 625 | static int pseudo_merge_bitmap_nr; |
| 626 | static int pseudo_merge_bitmap_parents; |
| 627 | |
| 628 | static int fill_bitmap_commit_calls_nr; |
| 629 | static int fill_bitmap_commit_found_ancestor_nr; |
| 630 | |
| 631 | static int fill_bitmap_commit(struct bitmap_writer *writer, |
| 632 | struct bb_commit *ent, |
| 633 | struct commit *commit, |
| 634 | struct prio_queue *queue, |
| 635 | struct prio_queue *tree_queue, |
| 636 | struct bitmap_index *old_bitmap, |
| 637 | const uint32_t *mapping) |
| 638 | { |
| 639 | struct commit *c; |
| 640 | struct tree *t; |
| 641 | int found; |
| 642 | int from_pseudo_merge = commit->object.flags & BITMAP_PSEUDO_MERGE; |
| 643 | uint32_t pos; |
| 644 | |
| 645 | if (ent->pseudo_merge) |
| 646 | BUG("unexpected pseudo-merge commit in fill_bitmap_commit()"); |
| 647 | |
| 648 | fill_bitmap_commit_calls_nr++; |
| 649 | |
| 650 | if (!ent->bitmap) |
| 651 | ent->bitmap = bitmap_new(); |
| 652 | |
| 653 | prio_queue_put(queue, commit); |
| 654 | |
| 655 | while ((c = prio_queue_get(queue))) { |
| 656 | struct commit_list *p; |
| 657 | |
| 658 | if (old_bitmap && mapping) { |
| 659 | struct ewah_bitmap *old; |
| 660 | struct bitmap *remapped = bitmap_new(); |
| 661 | |
| 662 | old = bitmap_for_commit(old_bitmap, c); |
| 663 | /* |
| 664 | * If this commit has an old bitmap, then translate that |
| 665 | * bitmap and add its bits to this one. No need to walk |
| 666 | * parents or the tree for this commit. |
| 667 | */ |
| 668 | if (old && !rebuild_bitmap(mapping, old, remapped)) { |
| 669 | bitmap_or(ent->bitmap, remapped); |
| 670 | bitmap_free(remapped); |
| 671 | reused_bitmaps_nr++; |
| 672 | continue; |
| 673 | } |
| 674 | bitmap_free(remapped); |
| 675 | } |
| 676 | |
| 677 | /* |
| 678 | * If we encounter an ancestor for which we have already |
| 679 | * computed a bitmap during this build (i.e. a regular |
| 680 | * selected commit processed earlier in topo order), we can |
| 681 | * short-circuit the walk: its stored bitmap already covers |
| 682 | * the commit itself, its tree, and all of its ancestors. |
| 683 | */ |
| 684 | if (c != commit) { |
| 685 | khiter_t hash_pos = kh_get_oid_map(writer->bitmaps, |
| 686 | c->object.oid); |
| 687 | if (hash_pos != kh_end(writer->bitmaps)) { |
| 688 | struct bitmapped_commit *stored = |
| 689 | kh_value(writer->bitmaps, hash_pos); |
| 690 | if (stored && stored->bitmap) { |
| 691 | fill_bitmap_commit_found_ancestor_nr++; |
| 692 | bitmap_or_ewah(ent->bitmap, |
| 693 | stored->bitmap); |
| 694 | continue; |
| 695 | } |
| 696 | } |
| 697 | } |
| 698 | |
| 699 | /* |
| 700 | * Mark ourselves and queue our tree. The commit |
| 701 | * walk ensures we cover all parents. |
| 702 | */ |
| 703 | if (!(c->object.flags & BITMAP_PSEUDO_MERGE)) { |
| 704 | struct tree *tree; |
| 705 | |
| 706 | if (from_pseudo_merge && !c->object.parsed) { |
| 707 | /* |
| 708 | * Commits reachable from selected |
| 709 | * non-pseudo-merges are already parsed |
| 710 | * by the regular bitmap build. |
| 711 | * |
| 712 | * However, pseudo-merge fills can also |
| 713 | * reach commits that were not covered |
| 714 | * there, so parse any such leftovers |
| 715 | * before reading their tree or parents. |
| 716 | */ |
| 717 | if (repo_parse_commit(writer->repo, c)) |
| 718 | return -1; |
| 719 | } |
| 720 | |
| 721 | pos = find_object_pos(writer, &c->object.oid, &found); |
| 722 | if (!found) |
| 723 | return -1; |
| 724 | bitmap_set(ent->bitmap, pos); |
| 725 | |
| 726 | tree = repo_get_commit_tree(writer->repo, c); |
| 727 | if (!tree) |
| 728 | return -1; |
| 729 | prio_queue_put(tree_queue, tree); |
| 730 | } |
| 731 | |
| 732 | for (p = c->parents; p; p = p->next) { |
| 733 | pos = find_object_pos(writer, &p->item->object.oid, |
| 734 | &found); |
| 735 | if (!found) |
| 736 | return -1; |
| 737 | if (!bitmap_get(ent->bitmap, pos)) { |
| 738 | bitmap_set(ent->bitmap, pos); |
| 739 | prio_queue_put(queue, p->item); |
| 740 | } |
| 741 | } |
| 742 | } |
| 743 | |
| 744 | while ((t = prio_queue_get(tree_queue))) { |
| 745 | int found; |
| 746 | |
| 747 | pos = find_object_pos(writer, &t->object.oid, &found); |
| 748 | if (!found) |
| 749 | return -1; |
| 750 | if (bitmap_get(ent->bitmap, pos)) { |
| 751 | /* |
| 752 | * If our bit is already set, then there is |
| 753 | * nothing to do. Both this tree and all of its |
| 754 | * children will be set. |
| 755 | */ |
| 756 | continue; |
| 757 | } |
| 758 | |
| 759 | if (fill_bitmap_tree(writer, ent->bitmap, t, pos) < 0) |
| 760 | return -1; |
| 761 | } |
| 762 | return 0; |
| 763 | } |
| 764 | |
| 765 | static int reuse_pseudo_merge_bitmap(struct bitmap_index *old_bitmap, |
| 766 | const uint32_t *mapping, |
| 767 | struct commit *merge, |
| 768 | struct ewah_bitmap **out) |
| 769 | { |
| 770 | struct ewah_bitmap *old; |
| 771 | struct bitmap *remapped; |
| 772 | |
| 773 | if (!old_bitmap || !mapping) |
| 774 | return 0; |
| 775 | |
| 776 | old = pseudo_merge_bitmap_for_commit(old_bitmap, merge); |
| 777 | if (!old) |
| 778 | return 0; |
| 779 | |
| 780 | remapped = bitmap_new(); |
| 781 | if (rebuild_bitmap(mapping, old, remapped) < 0) { |
| 782 | bitmap_free(remapped); |
| 783 | return 0; |
| 784 | } |
| 785 | |
| 786 | *out = bitmap_to_ewah(remapped); |
| 787 | bitmap_free(remapped); |
| 788 | reused_pseudo_merge_bitmaps_nr++; |
| 789 | return 1; |
| 790 | } |
| 791 | |
| 792 | static int build_pseudo_merge_bitmap(struct bitmap_writer *writer, |
| 793 | struct bitmap_index *old_bitmap, |
| 794 | const uint32_t *mapping, |
| 795 | struct commit *merge, |
| 796 | struct ewah_bitmap **out) |
| 797 | { |
| 798 | struct bb_commit ent = { 0 }; |
| 799 | struct prio_queue queue = { NULL }; |
| 800 | struct prio_queue tree_queue = { NULL }; |
| 801 | unsigned parents = commit_list_count(merge->parents); |
| 802 | int ret; |
| 803 | |
| 804 | ent.bitmap = bitmap_new(); |
| 805 | |
| 806 | pseudo_merge_bitmap_nr++; |
| 807 | pseudo_merge_bitmap_parents += parents; |
| 808 | |
| 809 | if (reuse_pseudo_merge_bitmap(old_bitmap, mapping, merge, out)) { |
| 810 | ret = 0; |
| 811 | goto done; |
| 812 | } |
| 813 | |
| 814 | ret = fill_bitmap_commit(writer, &ent, merge, &queue, &tree_queue, |
| 815 | old_bitmap, mapping); |
| 816 | |
| 817 | if (!ret) |
| 818 | *out = bitmap_to_ewah(ent.bitmap); |
| 819 | |
| 820 | done: |
| 821 | bitmap_free(ent.bitmap); |
| 822 | clear_prio_queue(&queue); |
| 823 | clear_prio_queue(&tree_queue); |
| 824 | |
| 825 | return ret; |
| 826 | } |
| 827 | |
| 828 | static int build_pseudo_merge_bitmaps(struct bitmap_writer *writer, |
| 829 | struct bitmap_index *old_bitmap, |
| 830 | const uint32_t *mapping, |
| 831 | int *nr_stored) |
| 832 | { |
| 833 | size_t i = bitmap_writer_nr_selected_commits(writer); |
| 834 | int ret = 0; |
| 835 | |
| 836 | if (!writer->pseudo_merges_nr) |
| 837 | return 0; |
| 838 | |
| 839 | trace2_region_enter("pack-bitmap-write", "building_pseudo_merge_bitmaps", |
| 840 | writer->repo); |
| 841 | |
| 842 | for (; i < writer->selected_nr; i++) { |
| 843 | struct bitmapped_commit *merge = &writer->selected[i]; |
| 844 | struct commit_list *p; |
| 845 | struct bitmap *parents = bitmap_new(); |
| 846 | struct ewah_bitmap *objects = NULL; |
| 847 | |
| 848 | if (!merge->pseudo_merge) |
| 849 | BUG("found non-pseudo merge commit at %"PRIuMAX, |
| 850 | (uintmax_t)i); |
| 851 | |
| 852 | for (p = merge->commit->parents; p; p = p->next) { |
| 853 | int found; |
| 854 | uint32_t pos = find_object_pos(writer, |
| 855 | &p->item->object.oid, |
| 856 | &found); |
| 857 | if (!found) { |
| 858 | bitmap_free(parents); |
| 859 | ret = -1; |
| 860 | goto done; |
| 861 | } |
| 862 | bitmap_set(parents, pos); |
| 863 | } |
| 864 | |
| 865 | merge->pseudo_merge_parents = bitmap_to_ewah(parents); |
| 866 | bitmap_free(parents); |
| 867 | |
| 868 | if (build_pseudo_merge_bitmap(writer, old_bitmap, mapping, |
| 869 | merge->commit, &objects) < 0) { |
| 870 | ret = -1; |
| 871 | goto done; |
| 872 | } |
| 873 | merge->bitmap = objects; |
| 874 | |
| 875 | (*nr_stored)++; |
| 876 | display_progress(writer->progress, *nr_stored); |
| 877 | } |
| 878 | |
| 879 | done: |
| 880 | trace2_region_leave("pack-bitmap-write", "building_pseudo_merge_bitmaps", |
| 881 | writer->repo); |
| 882 | |
| 883 | trace2_data_intmax("pack-bitmap-write", writer->repo, |
| 884 | "pseudo_merge_bitmap_nr", |
| 885 | pseudo_merge_bitmap_nr); |
| 886 | trace2_data_intmax("pack-bitmap-write", writer->repo, |
| 887 | "building_bitmaps_pseudo_merge_reused", |
| 888 | reused_pseudo_merge_bitmaps_nr); |
| 889 | trace2_data_intmax("pack-bitmap-write", writer->repo, |
| 890 | "pseudo_merge_bitmap_parents", |
| 891 | pseudo_merge_bitmap_parents); |
| 892 | |
| 893 | return ret; |
| 894 | } |
| 895 | |
| 896 | static void store_selected(struct bitmap_writer *writer, |
| 897 | struct bb_commit *ent, struct commit *commit) |
| 898 | { |
| 899 | struct bitmapped_commit *stored = &writer->selected[ent->idx]; |
| 900 | khiter_t hash_pos; |
| 901 | |
| 902 | stored->bitmap = bitmap_to_ewah(ent->bitmap); |
| 903 | |
| 904 | if (ent->pseudo_merge) |
| 905 | return; |
| 906 | |
| 907 | hash_pos = kh_get_oid_map(writer->bitmaps, commit->object.oid); |
| 908 | if (hash_pos == kh_end(writer->bitmaps)) |
| 909 | die(_("attempted to store non-selected commit: '%s'"), |
| 910 | oid_to_hex(&commit->object.oid)); |
| 911 | |
| 912 | kh_value(writer->bitmaps, hash_pos) = stored; |
| 913 | } |
| 914 | |
| 915 | int bitmap_writer_build(struct bitmap_writer *writer) |
| 916 | { |
| 917 | struct bitmap_builder bb; |
| 918 | size_t i; |
| 919 | int nr_stored = 0; /* for progress */ |
| 920 | struct prio_queue queue = { compare_commits_by_gen_then_commit_date }; |
| 921 | struct prio_queue tree_queue = { NULL }; |
| 922 | struct bitmap_index *old_bitmap; |
| 923 | uint32_t *mapping = NULL; |
| 924 | int closed = 1; /* until proven otherwise */ |
| 925 | |
| 926 | if (writer->show_progress) |
| 927 | writer->progress = start_progress(writer->repo, |
| 928 | "Building bitmaps", |
| 929 | writer->selected_nr); |
| 930 | |
| 931 | writer->pos_cache_hits = 0; |
| 932 | writer->pos_cache_misses = 0; |
| 933 | |
| 934 | trace2_region_enter("pack-bitmap-write", "building_bitmaps_total", |
| 935 | writer->repo); |
| 936 | |
| 937 | old_bitmap = prepare_bitmap_git(writer->to_pack->repo); |
| 938 | if (old_bitmap) |
| 939 | mapping = create_bitmap_mapping(old_bitmap, writer->to_pack); |
| 940 | else |
| 941 | mapping = NULL; |
| 942 | |
| 943 | bitmap_builder_init(&bb, writer, old_bitmap); |
| 944 | for (i = bb.commits.nr; i > 0; i--) { |
| 945 | struct commit *commit = bb.commits.items[i-1]; |
| 946 | struct bb_commit *ent = bb_data_at(&bb.data, commit); |
| 947 | struct commit *child; |
| 948 | int reused = 0; |
| 949 | |
| 950 | if (fill_bitmap_commit(writer, ent, commit, &queue, &tree_queue, |
| 951 | old_bitmap, mapping) < 0) { |
| 952 | closed = 0; |
| 953 | break; |
| 954 | } |
| 955 | |
| 956 | if (ent->selected) { |
| 957 | store_selected(writer, ent, commit); |
| 958 | nr_stored++; |
| 959 | display_progress(writer->progress, nr_stored); |
| 960 | } |
| 961 | |
| 962 | while ((child = pop_commit(&ent->reverse_edges))) { |
| 963 | struct bb_commit *child_ent = |
| 964 | bb_data_at(&bb.data, child); |
| 965 | |
| 966 | if (child_ent->bitmap) |
| 967 | bitmap_or(child_ent->bitmap, ent->bitmap); |
| 968 | else if (reused) |
| 969 | child_ent->bitmap = bitmap_dup(ent->bitmap); |
| 970 | else { |
| 971 | child_ent->bitmap = ent->bitmap; |
| 972 | reused = 1; |
| 973 | } |
| 974 | } |
| 975 | if (!reused) |
| 976 | bitmap_free(ent->bitmap); |
| 977 | ent->bitmap = NULL; |
| 978 | } |
| 979 | if (closed && |
| 980 | build_pseudo_merge_bitmaps(writer, old_bitmap, mapping, |
| 981 | &nr_stored) < 0) |
| 982 | closed = 0; |
| 983 | clear_prio_queue(&queue); |
| 984 | clear_prio_queue(&tree_queue); |
| 985 | bitmap_builder_clear(&bb); |
| 986 | free_bitmap_index(old_bitmap); |
| 987 | free(mapping); |
| 988 | |
| 989 | trace2_region_leave("pack-bitmap-write", "building_bitmaps_total", |
| 990 | writer->repo); |
| 991 | trace2_data_intmax("pack-bitmap-write", writer->repo, |
| 992 | "building_bitmaps_reused", reused_bitmaps_nr); |
| 993 | trace2_data_intmax("pack-bitmap-write", writer->repo, |
| 994 | "fill_bitmap_commit_calls_nr", |
| 995 | fill_bitmap_commit_calls_nr); |
| 996 | trace2_data_intmax("pack-bitmap-write", writer->repo, |
| 997 | "fill_bitmap_commit_found_ancestor_nr", |
| 998 | fill_bitmap_commit_found_ancestor_nr); |
| 999 | trace2_data_intmax("pack-bitmap-write", writer->repo, |
| 1000 | "bitmap_pos_cache_hits", writer->pos_cache_hits); |
| 1001 | trace2_data_intmax("pack-bitmap-write", writer->repo, |
| 1002 | "bitmap_pos_cache_misses", writer->pos_cache_misses); |
| 1003 | |
| 1004 | stop_progress(&writer->progress); |
| 1005 | |
| 1006 | if (closed) |
| 1007 | compute_xor_offsets(writer); |
| 1008 | return closed ? 0 : -1; |
| 1009 | } |
| 1010 | |
| 1011 | /** |
| 1012 | * Select the commits that will be bitmapped |
| 1013 | */ |
| 1014 | static inline unsigned int next_commit_index(unsigned int idx) |
| 1015 | { |
| 1016 | static const unsigned int MIN_COMMITS = 100; |
| 1017 | static const unsigned int MAX_COMMITS = 5000; |
| 1018 | |
| 1019 | static const unsigned int MUST_REGION = 100; |
| 1020 | static const unsigned int MIN_REGION = 20000; |
| 1021 | |
| 1022 | unsigned int offset, next; |
| 1023 | |
| 1024 | if (idx <= MUST_REGION) |
| 1025 | return 0; |
| 1026 | |
| 1027 | if (idx <= MIN_REGION) { |
| 1028 | offset = idx - MUST_REGION; |
| 1029 | return (offset < MIN_COMMITS) ? offset : MIN_COMMITS; |
| 1030 | } |
| 1031 | |
| 1032 | offset = idx - MIN_REGION; |
| 1033 | next = (offset < MAX_COMMITS) ? offset : MAX_COMMITS; |
| 1034 | |
| 1035 | return (next > MIN_COMMITS) ? next : MIN_COMMITS; |
| 1036 | } |
| 1037 | |
| 1038 | static int date_compare(const void *_a, const void *_b) |
| 1039 | { |
| 1040 | struct commit *a = *(struct commit **)_a; |
| 1041 | struct commit *b = *(struct commit **)_b; |
| 1042 | return (long)b->date - (long)a->date; |
| 1043 | } |
| 1044 | |
| 1045 | void bitmap_writer_select_commits(struct bitmap_writer *writer, |
| 1046 | struct commit **indexed_commits, |
| 1047 | unsigned int indexed_commits_nr) |
| 1048 | { |
| 1049 | unsigned int i = 0, j, next; |
| 1050 | |
| 1051 | QSORT(indexed_commits, indexed_commits_nr, date_compare); |
| 1052 | |
| 1053 | if (indexed_commits_nr < 100) { |
| 1054 | for (i = 0; i < indexed_commits_nr; ++i) |
| 1055 | bitmap_writer_push_commit(writer, indexed_commits[i], 0); |
| 1056 | |
| 1057 | select_pseudo_merges(writer); |
| 1058 | |
| 1059 | return; |
| 1060 | } |
| 1061 | |
| 1062 | if (writer->show_progress) |
| 1063 | writer->progress = start_progress(writer->repo, |
| 1064 | "Selecting bitmap commits", 0); |
| 1065 | |
| 1066 | for (;;) { |
| 1067 | struct commit *chosen = NULL; |
| 1068 | |
| 1069 | next = next_commit_index(i); |
| 1070 | |
| 1071 | if (i + next >= indexed_commits_nr) |
| 1072 | break; |
| 1073 | |
| 1074 | if (next == 0) { |
| 1075 | chosen = indexed_commits[i]; |
| 1076 | } else { |
| 1077 | chosen = indexed_commits[i + next]; |
| 1078 | |
| 1079 | for (j = 0; j <= next; ++j) { |
| 1080 | struct commit *cm = indexed_commits[i + j]; |
| 1081 | |
| 1082 | if ((cm->object.flags & NEEDS_BITMAP) != 0) { |
| 1083 | chosen = cm; |
| 1084 | break; |
| 1085 | } |
| 1086 | |
| 1087 | if (cm->parents && cm->parents->next) |
| 1088 | chosen = cm; |
| 1089 | } |
| 1090 | } |
| 1091 | |
| 1092 | bitmap_writer_push_commit(writer, chosen, 0); |
| 1093 | |
| 1094 | i += next + 1; |
| 1095 | display_progress(writer->progress, i); |
| 1096 | } |
| 1097 | |
| 1098 | stop_progress(&writer->progress); |
| 1099 | |
| 1100 | select_pseudo_merges(writer); |
| 1101 | } |
| 1102 | |
| 1103 | |
| 1104 | static int hashwrite_ewah_helper(void *f, const void *buf, size_t len) |
| 1105 | { |
| 1106 | /* hashwrite will die on error */ |
| 1107 | hashwrite(f, buf, len); |
| 1108 | return len; |
| 1109 | } |
| 1110 | |
| 1111 | /** |
| 1112 | * Write the bitmap index to disk |
| 1113 | */ |
| 1114 | static inline void dump_bitmap(struct hashfile *f, struct ewah_bitmap *bitmap) |
| 1115 | { |
| 1116 | if (ewah_serialize_to(bitmap, hashwrite_ewah_helper, f) < 0) |
| 1117 | die("Failed to write bitmap index"); |
| 1118 | } |
| 1119 | |
| 1120 | static const struct object_id *oid_access(size_t pos, const void *table) |
| 1121 | { |
| 1122 | const struct pack_idx_entry * const *index = table; |
| 1123 | return &index[pos]->oid; |
| 1124 | } |
| 1125 | |
| 1126 | static void write_selected_commits_v1(struct bitmap_writer *writer, |
| 1127 | struct hashfile *f, off_t *offsets) |
| 1128 | { |
| 1129 | int i; |
| 1130 | |
| 1131 | for (i = 0; i < bitmap_writer_nr_selected_commits(writer); ++i) { |
| 1132 | struct bitmapped_commit *stored = &writer->selected[i]; |
| 1133 | if (stored->pseudo_merge) |
| 1134 | BUG("unexpected pseudo-merge among selected: %s", |
| 1135 | oid_to_hex(&stored->commit->object.oid)); |
| 1136 | |
| 1137 | if (offsets) |
| 1138 | offsets[i] = hashfile_total(f); |
| 1139 | |
| 1140 | hashwrite_be32(f, stored->commit_pos); |
| 1141 | hashwrite_u8(f, stored->xor_offset); |
| 1142 | hashwrite_u8(f, stored->flags); |
| 1143 | |
| 1144 | dump_bitmap(f, stored->write_as); |
| 1145 | } |
| 1146 | } |
| 1147 | |
| 1148 | static int pseudo_merge_commit_pos_cmp(const void *_va, const void *_vb, |
| 1149 | void *_data) |
| 1150 | { |
| 1151 | struct bitmap_writer *writer = _data; |
| 1152 | uint32_t pos_a = find_object_pos(writer, _va, NULL); |
| 1153 | uint32_t pos_b = find_object_pos(writer, _vb, NULL); |
| 1154 | |
| 1155 | if (pos_a < pos_b) |
| 1156 | return -1; |
| 1157 | if (pos_a > pos_b) |
| 1158 | return 1; |
| 1159 | return 0; |
| 1160 | } |
| 1161 | |
| 1162 | static void write_pseudo_merges(struct bitmap_writer *writer, |
| 1163 | struct hashfile *f) |
| 1164 | { |
| 1165 | struct oid_array commits = OID_ARRAY_INIT; |
| 1166 | off_t *pseudo_merge_ofs = NULL; |
| 1167 | off_t start, table_start, next_ext; |
| 1168 | |
| 1169 | uint32_t base = bitmap_writer_nr_selected_commits(writer); |
| 1170 | size_t i, j = 0; |
| 1171 | |
| 1172 | CALLOC_ARRAY(pseudo_merge_ofs, writer->pseudo_merges_nr); |
| 1173 | |
| 1174 | start = hashfile_total(f); |
| 1175 | |
| 1176 | for (i = 0; i < writer->pseudo_merges_nr; i++) { |
| 1177 | struct bitmapped_commit *merge = &writer->selected[base + i]; |
| 1178 | |
| 1179 | if (!merge->pseudo_merge) |
| 1180 | BUG("found non-pseudo merge commit at %"PRIuMAX, (uintmax_t)i); |
| 1181 | |
| 1182 | if (!merge->pseudo_merge_parents || !merge->bitmap) |
| 1183 | BUG("missing pseudo-merge bitmap for commit %s", |
| 1184 | oid_to_hex(&merge->commit->object.oid)); |
| 1185 | |
| 1186 | pseudo_merge_ofs[i] = hashfile_total(f); |
| 1187 | dump_bitmap(f, merge->pseudo_merge_parents); |
| 1188 | dump_bitmap(f, merge->bitmap); |
| 1189 | } |
| 1190 | |
| 1191 | next_ext = st_add(hashfile_total(f), |
| 1192 | st_mult(kh_size(writer->pseudo_merge_commits), |
| 1193 | sizeof(uint32_t) + sizeof(uint64_t))); |
| 1194 | |
| 1195 | table_start = hashfile_total(f); |
| 1196 | |
| 1197 | commits.alloc = kh_size(writer->pseudo_merge_commits); |
| 1198 | CALLOC_ARRAY(commits.oid, commits.alloc); |
| 1199 | |
| 1200 | for (i = kh_begin(writer->pseudo_merge_commits); i != kh_end(writer->pseudo_merge_commits); i++) { |
| 1201 | if (!kh_exist(writer->pseudo_merge_commits, i)) |
| 1202 | continue; |
| 1203 | oid_array_append(&commits, &kh_key(writer->pseudo_merge_commits, i)); |
| 1204 | } |
| 1205 | |
| 1206 | /* |
| 1207 | * Sort the commits by their bit position so that the lookup |
| 1208 | * table can be binary searched by the reader (see |
| 1209 | * find_pseudo_merge()). |
| 1210 | */ |
| 1211 | QSORT_S(commits.oid, commits.nr, pseudo_merge_commit_pos_cmp, writer); |
| 1212 | |
| 1213 | /* write lookup table (non-extended) */ |
| 1214 | for (i = 0; i < commits.nr; i++) { |
| 1215 | int hash_pos; |
| 1216 | struct pseudo_merge_commit_idx *c; |
| 1217 | |
| 1218 | hash_pos = kh_get_oid_map(writer->pseudo_merge_commits, |
| 1219 | commits.oid[i]); |
| 1220 | if (hash_pos == kh_end(writer->pseudo_merge_commits)) |
| 1221 | BUG("could not find pseudo-merge commit %s", |
| 1222 | oid_to_hex(&commits.oid[i])); |
| 1223 | |
| 1224 | c = kh_value(writer->pseudo_merge_commits, hash_pos); |
| 1225 | |
| 1226 | hashwrite_be32(f, find_object_pos(writer, &commits.oid[i], |
| 1227 | NULL)); |
| 1228 | if (c->nr == 1) |
| 1229 | hashwrite_be64(f, pseudo_merge_ofs[c->pseudo_merge[0]]); |
| 1230 | else if (c->nr > 1) { |
| 1231 | if (next_ext & ((uint64_t)1<<63)) |
| 1232 | die(_("too many pseudo-merges")); |
| 1233 | hashwrite_be64(f, next_ext | ((uint64_t)1<<63)); |
| 1234 | next_ext = st_add3(next_ext, |
| 1235 | sizeof(uint32_t), |
| 1236 | st_mult(c->nr, sizeof(uint64_t))); |
| 1237 | } else |
| 1238 | BUG("expected commit '%s' to have at least one " |
| 1239 | "pseudo-merge", oid_to_hex(&commits.oid[i])); |
| 1240 | } |
| 1241 | |
| 1242 | /* write lookup table (extended) */ |
| 1243 | for (i = 0; i < commits.nr; i++) { |
| 1244 | int hash_pos; |
| 1245 | struct pseudo_merge_commit_idx *c; |
| 1246 | |
| 1247 | hash_pos = kh_get_oid_map(writer->pseudo_merge_commits, |
| 1248 | commits.oid[i]); |
| 1249 | if (hash_pos == kh_end(writer->pseudo_merge_commits)) |
| 1250 | BUG("could not find pseudo-merge commit %s", |
| 1251 | oid_to_hex(&commits.oid[i])); |
| 1252 | |
| 1253 | c = kh_value(writer->pseudo_merge_commits, hash_pos); |
| 1254 | if (c->nr == 1) |
| 1255 | continue; |
| 1256 | |
| 1257 | hashwrite_be32(f, c->nr); |
| 1258 | for (j = 0; j < c->nr; j++) |
| 1259 | hashwrite_be64(f, pseudo_merge_ofs[c->pseudo_merge[j]]); |
| 1260 | } |
| 1261 | |
| 1262 | /* write positions for all pseudo merges */ |
| 1263 | for (i = 0; i < writer->pseudo_merges_nr; i++) |
| 1264 | hashwrite_be64(f, pseudo_merge_ofs[i]); |
| 1265 | |
| 1266 | hashwrite_be32(f, writer->pseudo_merges_nr); |
| 1267 | hashwrite_be32(f, kh_size(writer->pseudo_merge_commits)); |
| 1268 | hashwrite_be64(f, table_start - start); |
| 1269 | hashwrite_be64(f, hashfile_total(f) - start + sizeof(uint64_t)); |
| 1270 | |
| 1271 | oid_array_clear(&commits); |
| 1272 | free(pseudo_merge_ofs); |
| 1273 | } |
| 1274 | |
| 1275 | static int table_cmp(const void *_va, const void *_vb, void *_data) |
| 1276 | { |
| 1277 | struct bitmap_writer *writer = _data; |
| 1278 | struct bitmapped_commit *a = &writer->selected[*(uint32_t *)_va]; |
| 1279 | struct bitmapped_commit *b = &writer->selected[*(uint32_t *)_vb]; |
| 1280 | |
| 1281 | if (a->commit_pos < b->commit_pos) |
| 1282 | return -1; |
| 1283 | else if (a->commit_pos > b->commit_pos) |
| 1284 | return 1; |
| 1285 | |
| 1286 | return 0; |
| 1287 | } |
| 1288 | |
| 1289 | static void write_lookup_table(struct bitmap_writer *writer, struct hashfile *f, |
| 1290 | off_t *offsets) |
| 1291 | { |
| 1292 | uint32_t i; |
| 1293 | uint32_t *table, *table_inv; |
| 1294 | |
| 1295 | ALLOC_ARRAY(table, bitmap_writer_nr_selected_commits(writer)); |
| 1296 | ALLOC_ARRAY(table_inv, bitmap_writer_nr_selected_commits(writer)); |
| 1297 | |
| 1298 | for (i = 0; i < bitmap_writer_nr_selected_commits(writer); i++) |
| 1299 | table[i] = i; |
| 1300 | |
| 1301 | /* |
| 1302 | * At the end of this sort table[j] = i means that the i'th |
| 1303 | * bitmap corresponds to j'th bitmapped commit (among the selected |
| 1304 | * commits) in lex order of OIDs. |
| 1305 | */ |
| 1306 | QSORT_S(table, bitmap_writer_nr_selected_commits(writer), table_cmp, writer); |
| 1307 | |
| 1308 | /* table_inv helps us discover that relationship (i'th bitmap |
| 1309 | * to j'th commit by j = table_inv[i]) |
| 1310 | */ |
| 1311 | for (i = 0; i < bitmap_writer_nr_selected_commits(writer); i++) |
| 1312 | table_inv[table[i]] = i; |
| 1313 | |
| 1314 | trace2_region_enter("pack-bitmap-write", "writing_lookup_table", writer->repo); |
| 1315 | for (i = 0; i < bitmap_writer_nr_selected_commits(writer); i++) { |
| 1316 | struct bitmapped_commit *selected = &writer->selected[table[i]]; |
| 1317 | uint32_t xor_offset = selected->xor_offset; |
| 1318 | uint32_t xor_row; |
| 1319 | |
| 1320 | if (xor_offset) { |
| 1321 | /* |
| 1322 | * xor_index stores the index (in the bitmap entries) |
| 1323 | * of the corresponding xor bitmap. But we need to convert |
| 1324 | * this index into lookup table's index. So, table_inv[xor_index] |
| 1325 | * gives us the index position w.r.t. the lookup table. |
| 1326 | * |
| 1327 | * If "k = table[i] - xor_offset" then the xor base is the k'th |
| 1328 | * bitmap. `table_inv[k]` gives us the position of that bitmap |
| 1329 | * in the lookup table. |
| 1330 | */ |
| 1331 | uint32_t xor_index = table[i] - xor_offset; |
| 1332 | xor_row = table_inv[xor_index]; |
| 1333 | } else { |
| 1334 | xor_row = 0xffffffff; |
| 1335 | } |
| 1336 | |
| 1337 | hashwrite_be32(f, writer->selected[table[i]].commit_pos); |
| 1338 | hashwrite_be64(f, (uint64_t)offsets[table[i]]); |
| 1339 | hashwrite_be32(f, xor_row); |
| 1340 | } |
| 1341 | trace2_region_leave("pack-bitmap-write", "writing_lookup_table", writer->repo); |
| 1342 | |
| 1343 | free(table); |
| 1344 | free(table_inv); |
| 1345 | } |
| 1346 | |
| 1347 | static void write_hash_cache(struct hashfile *f, |
| 1348 | struct pack_idx_entry **index, |
| 1349 | uint32_t index_nr) |
| 1350 | { |
| 1351 | uint32_t i; |
| 1352 | |
| 1353 | for (i = 0; i < index_nr; ++i) { |
| 1354 | struct object_entry *entry = (struct object_entry *)index[i]; |
| 1355 | hashwrite_be32(f, entry->hash); |
| 1356 | } |
| 1357 | } |
| 1358 | |
| 1359 | void bitmap_writer_set_checksum(struct bitmap_writer *writer, |
| 1360 | const unsigned char *sha1) |
| 1361 | { |
| 1362 | hashcpy(writer->pack_checksum, sha1, writer->repo->hash_algo); |
| 1363 | } |
| 1364 | |
| 1365 | void bitmap_writer_finish(struct bitmap_writer *writer, |
| 1366 | struct pack_idx_entry **index, |
| 1367 | const char *filename, |
| 1368 | uint16_t options) |
| 1369 | { |
| 1370 | static uint16_t default_version = 1; |
| 1371 | static uint16_t flags = BITMAP_OPT_FULL_DAG; |
| 1372 | struct strbuf tmp_file = STRBUF_INIT; |
| 1373 | struct hashfile *f; |
| 1374 | off_t *offsets = NULL; |
| 1375 | uint32_t i, base_objects; |
| 1376 | |
| 1377 | struct bitmap_disk_header header; |
| 1378 | |
| 1379 | int fd = odb_mkstemp(writer->repo->objects, &tmp_file, |
| 1380 | "pack/tmp_bitmap_XXXXXX"); |
| 1381 | |
| 1382 | if (writer->pseudo_merges_nr) |
| 1383 | options |= BITMAP_OPT_PSEUDO_MERGES; |
| 1384 | |
| 1385 | f = hashfd(writer->repo->hash_algo, fd, tmp_file.buf); |
| 1386 | |
| 1387 | memcpy(header.magic, BITMAP_IDX_SIGNATURE, sizeof(BITMAP_IDX_SIGNATURE)); |
| 1388 | header.version = htons(default_version); |
| 1389 | header.options = htons(flags | options); |
| 1390 | header.entry_count = htonl(bitmap_writer_nr_selected_commits(writer)); |
| 1391 | hashcpy(header.checksum, writer->pack_checksum, writer->repo->hash_algo); |
| 1392 | |
| 1393 | hashwrite(f, &header, sizeof(header) - GIT_MAX_RAWSZ + writer->repo->hash_algo->rawsz); |
| 1394 | dump_bitmap(f, writer->commits); |
| 1395 | dump_bitmap(f, writer->trees); |
| 1396 | dump_bitmap(f, writer->blobs); |
| 1397 | dump_bitmap(f, writer->tags); |
| 1398 | |
| 1399 | if (options & BITMAP_OPT_LOOKUP_TABLE) |
| 1400 | CALLOC_ARRAY(offsets, writer->to_pack->nr_objects); |
| 1401 | |
| 1402 | if (writer->midx) |
| 1403 | base_objects = writer->midx->num_objects + |
| 1404 | writer->midx->num_objects_in_base; |
| 1405 | else |
| 1406 | base_objects = 0; |
| 1407 | |
| 1408 | for (i = 0; i < bitmap_writer_nr_selected_commits(writer); i++) { |
| 1409 | struct bitmapped_commit *stored = &writer->selected[i]; |
| 1410 | int commit_pos = oid_pos(&stored->commit->object.oid, index, |
| 1411 | writer->to_pack->nr_objects, |
| 1412 | oid_access); |
| 1413 | |
| 1414 | if (commit_pos < 0) |
| 1415 | BUG("trying to write commit not in index"); |
| 1416 | stored->commit_pos = commit_pos + base_objects; |
| 1417 | } |
| 1418 | |
| 1419 | write_selected_commits_v1(writer, f, offsets); |
| 1420 | |
| 1421 | if (options & BITMAP_OPT_PSEUDO_MERGES) |
| 1422 | write_pseudo_merges(writer, f); |
| 1423 | |
| 1424 | if (options & BITMAP_OPT_LOOKUP_TABLE) |
| 1425 | write_lookup_table(writer, f, offsets); |
| 1426 | |
| 1427 | if (options & BITMAP_OPT_HASH_CACHE) |
| 1428 | write_hash_cache(f, index, writer->to_pack->nr_objects); |
| 1429 | |
| 1430 | finalize_hashfile(f, NULL, FSYNC_COMPONENT_PACK_METADATA, |
| 1431 | CSUM_HASH_IN_STREAM | CSUM_FSYNC | CSUM_CLOSE); |
| 1432 | |
| 1433 | if (adjust_shared_perm(writer->repo, tmp_file.buf)) |
| 1434 | die_errno("unable to make temporary bitmap file readable"); |
| 1435 | |
| 1436 | if (rename(tmp_file.buf, filename)) |
| 1437 | die_errno("unable to rename temporary bitmap file to '%s'", filename); |
| 1438 | |
| 1439 | strbuf_release(&tmp_file); |
| 1440 | free(offsets); |
| 1441 | } |