2 #include "object-store.h"
7 #include "list-objects.h"
9 #include "pack-revindex.h"
11 #include "pack-bitmap.h"
12 #include "sha1-lookup.h"
13 #include "pack-objects.h"
14 #include "commit-reach.h"
15 #include "prio-queue.h"
17 struct bitmapped_commit {
18 struct commit *commit;
19 struct ewah_bitmap *bitmap;
20 struct ewah_bitmap *write_as;
26 struct bitmap_writer {
27 struct ewah_bitmap *commits;
28 struct ewah_bitmap *trees;
29 struct ewah_bitmap *blobs;
30 struct ewah_bitmap *tags;
32 kh_oid_map_t *bitmaps;
34 struct packing_data *to_pack;
36 struct bitmapped_commit *selected;
37 unsigned int selected_nr, selected_alloc;
39 struct progress *progress;
41 unsigned char pack_checksum[GIT_MAX_RAWSZ];
44 static struct bitmap_writer writer;
46 void bitmap_writer_show_progress(int show)
48 writer.show_progress = show;
52 * Build the initial type index for the packfile
54 void bitmap_writer_build_type_index(struct packing_data *to_pack,
55 struct pack_idx_entry **index,
60 writer.commits = ewah_new();
61 writer.trees = ewah_new();
62 writer.blobs = ewah_new();
63 writer.tags = ewah_new();
64 ALLOC_ARRAY(to_pack->in_pack_pos, to_pack->nr_objects);
66 for (i = 0; i < index_nr; ++i) {
67 struct object_entry *entry = (struct object_entry *)index[i];
68 enum object_type real_type;
70 oe_set_in_pack_pos(to_pack, entry, i);
72 switch (oe_type(entry)) {
77 real_type = oe_type(entry);
81 real_type = oid_object_info(to_pack->repo,
82 &entry->idx.oid, NULL);
88 ewah_set(writer.commits, i);
92 ewah_set(writer.trees, i);
96 ewah_set(writer.blobs, i);
100 ewah_set(writer.tags, i);
104 die("Missing type information for %s (%d/%d)",
105 oid_to_hex(&entry->idx.oid), real_type,
112 * Compute the actual bitmaps
115 static inline void push_bitmapped_commit(struct commit *commit, struct ewah_bitmap *reused)
117 if (writer.selected_nr >= writer.selected_alloc) {
118 writer.selected_alloc = (writer.selected_alloc + 32) * 2;
119 REALLOC_ARRAY(writer.selected, writer.selected_alloc);
122 writer.selected[writer.selected_nr].commit = commit;
123 writer.selected[writer.selected_nr].bitmap = reused;
124 writer.selected[writer.selected_nr].flags = 0;
126 writer.selected_nr++;
129 static uint32_t find_object_pos(const struct object_id *oid)
131 struct object_entry *entry = packlist_find(writer.to_pack, oid);
134 die("Failed to write bitmap index. Packfile doesn't have full closure "
135 "(object %s is missing)", oid_to_hex(oid));
138 return oe_in_pack_pos(writer.to_pack, entry);
141 static void compute_xor_offsets(void)
143 static const int MAX_XOR_OFFSET_SEARCH = 10;
147 while (next < writer.selected_nr) {
148 struct bitmapped_commit *stored = &writer.selected[next];
151 struct ewah_bitmap *best_bitmap = stored->bitmap;
152 struct ewah_bitmap *test_xor;
154 for (i = 1; i <= MAX_XOR_OFFSET_SEARCH; ++i) {
160 test_xor = ewah_pool_new();
161 ewah_xor(writer.selected[curr].bitmap, stored->bitmap, test_xor);
163 if (test_xor->buffer_size < best_bitmap->buffer_size) {
164 if (best_bitmap != stored->bitmap)
165 ewah_pool_free(best_bitmap);
167 best_bitmap = test_xor;
170 ewah_pool_free(test_xor);
174 stored->xor_offset = best_offset;
175 stored->write_as = best_bitmap;
182 struct commit_list *children;
183 struct bitmap *bitmap;
185 unsigned idx; /* within selected array */
188 define_commit_slab(bb_data, struct bb_commit);
190 struct bitmap_builder {
192 struct commit **commits;
193 size_t commits_nr, commits_alloc;
196 static void bitmap_builder_init(struct bitmap_builder *bb,
197 struct bitmap_writer *writer)
199 struct rev_info revs;
200 struct commit *commit;
203 memset(bb, 0, sizeof(*bb));
204 init_bb_data(&bb->data);
206 reset_revision_walk();
207 repo_init_revisions(writer->to_pack->repo, &revs, NULL);
210 for (i = 0; i < writer->selected_nr; i++) {
211 struct commit *c = writer->selected[i].commit;
212 struct bb_commit *ent = bb_data_at(&bb->data, c);
215 add_pending_object(&revs, &c->object, "");
218 if (prepare_revision_walk(&revs))
219 die("revision walk setup failed");
221 while ((commit = get_revision(&revs))) {
222 struct commit_list *p;
224 parse_commit_or_die(commit);
226 ALLOC_GROW(bb->commits, bb->commits_nr + 1, bb->commits_alloc);
227 bb->commits[bb->commits_nr++] = commit;
229 for (p = commit->parents; p; p = p->next) {
230 struct bb_commit *ent = bb_data_at(&bb->data, p->item);
231 commit_list_insert(commit, &ent->children);
236 static void bitmap_builder_clear(struct bitmap_builder *bb)
238 clear_bb_data(&bb->data);
240 bb->commits_nr = bb->commits_alloc = 0;
243 static void fill_bitmap_tree(struct bitmap *bitmap,
247 struct tree_desc desc;
248 struct name_entry entry;
251 * If our bit is already set, then there is nothing to do. Both this
252 * tree and all of its children will be set.
254 pos = find_object_pos(&tree->object.oid);
255 if (bitmap_get(bitmap, pos))
257 bitmap_set(bitmap, pos);
259 if (parse_tree(tree) < 0)
260 die("unable to load tree object %s",
261 oid_to_hex(&tree->object.oid));
262 init_tree_desc(&desc, tree->buffer, tree->size);
264 while (tree_entry(&desc, &entry)) {
265 switch (object_type(entry.mode)) {
267 fill_bitmap_tree(bitmap,
268 lookup_tree(the_repository, &entry.oid));
271 bitmap_set(bitmap, find_object_pos(&entry.oid));
274 /* Gitlink, etc; not reachable */
279 free_tree_buffer(tree);
282 static void fill_bitmap_commit(struct bb_commit *ent,
283 struct commit *commit,
284 struct prio_queue *queue)
287 ent->bitmap = bitmap_new();
289 bitmap_set(ent->bitmap, find_object_pos(&commit->object.oid));
290 prio_queue_put(queue, commit);
293 struct commit_list *p;
294 struct commit *c = prio_queue_get(queue);
296 bitmap_set(ent->bitmap, find_object_pos(&c->object.oid));
297 fill_bitmap_tree(ent->bitmap, get_commit_tree(c));
299 for (p = c->parents; p; p = p->next) {
300 int pos = find_object_pos(&p->item->object.oid);
301 if (!bitmap_get(ent->bitmap, pos)) {
302 bitmap_set(ent->bitmap, pos);
303 prio_queue_put(queue, p->item);
309 static void store_selected(struct bb_commit *ent, struct commit *commit)
311 struct bitmapped_commit *stored = &writer.selected[ent->idx];
316 * the "reuse bitmaps" phase may have stored something here, but
317 * our new algorithm doesn't use it. Drop it.
320 ewah_free(stored->bitmap);
322 stored->bitmap = bitmap_to_ewah(ent->bitmap);
324 hash_pos = kh_put_oid_map(writer.bitmaps, commit->object.oid, &hash_ret);
326 die("Duplicate entry when writing index: %s",
327 oid_to_hex(&commit->object.oid));
328 kh_value(writer.bitmaps, hash_pos) = stored;
331 void bitmap_writer_build(struct packing_data *to_pack)
333 struct bitmap_builder bb;
335 int nr_stored = 0; /* for progress */
336 struct prio_queue queue = { compare_commits_by_gen_then_commit_date };
338 writer.bitmaps = kh_init_oid_map();
339 writer.to_pack = to_pack;
341 if (writer.show_progress)
342 writer.progress = start_progress("Building bitmaps", writer.selected_nr);
343 trace2_region_enter("pack-bitmap-write", "building_bitmaps_total",
346 bitmap_builder_init(&bb, &writer);
347 for (i = bb.commits_nr; i > 0; i--) {
348 struct commit *commit = bb.commits[i-1];
349 struct bb_commit *ent = bb_data_at(&bb.data, commit);
350 struct commit *child;
353 fill_bitmap_commit(ent, commit, &queue);
356 store_selected(ent, commit);
358 display_progress(writer.progress, nr_stored);
361 while ((child = pop_commit(&ent->children))) {
362 struct bb_commit *child_ent =
363 bb_data_at(&bb.data, child);
365 if (child_ent->bitmap)
366 bitmap_or(child_ent->bitmap, ent->bitmap);
368 child_ent->bitmap = bitmap_dup(ent->bitmap);
370 child_ent->bitmap = ent->bitmap;
375 bitmap_free(ent->bitmap);
378 clear_prio_queue(&queue);
379 bitmap_builder_clear(&bb);
381 trace2_region_leave("pack-bitmap-write", "building_bitmaps_total",
384 stop_progress(&writer.progress);
386 compute_xor_offsets();
390 * Select the commits that will be bitmapped
392 static inline unsigned int next_commit_index(unsigned int idx)
394 static const unsigned int MIN_COMMITS = 100;
395 static const unsigned int MAX_COMMITS = 5000;
397 static const unsigned int MUST_REGION = 100;
398 static const unsigned int MIN_REGION = 20000;
400 unsigned int offset, next;
402 if (idx <= MUST_REGION)
405 if (idx <= MIN_REGION) {
406 offset = idx - MUST_REGION;
407 return (offset < MIN_COMMITS) ? offset : MIN_COMMITS;
410 offset = idx - MIN_REGION;
411 next = (offset < MAX_COMMITS) ? offset : MAX_COMMITS;
413 return (next > MIN_COMMITS) ? next : MIN_COMMITS;
416 static int date_compare(const void *_a, const void *_b)
418 struct commit *a = *(struct commit **)_a;
419 struct commit *b = *(struct commit **)_b;
420 return (long)b->date - (long)a->date;
423 void bitmap_writer_reuse_bitmaps(struct packing_data *to_pack)
425 struct bitmap_index *bitmap_git;
426 if (!(bitmap_git = prepare_bitmap_git(to_pack->repo)))
429 writer.reused = kh_init_oid_map();
430 rebuild_existing_bitmaps(bitmap_git, to_pack, writer.reused,
431 writer.show_progress);
433 * NEEDSWORK: rebuild_existing_bitmaps() makes writer.reused reference
434 * some bitmaps in bitmap_git, so we can't free the latter.
438 static struct ewah_bitmap *find_reused_bitmap(const struct object_id *oid)
445 hash_pos = kh_get_oid_map(writer.reused, *oid);
446 if (hash_pos >= kh_end(writer.reused))
449 return kh_value(writer.reused, hash_pos);
452 void bitmap_writer_select_commits(struct commit **indexed_commits,
453 unsigned int indexed_commits_nr,
456 unsigned int i = 0, j, next;
458 QSORT(indexed_commits, indexed_commits_nr, date_compare);
460 if (writer.show_progress)
461 writer.progress = start_progress("Selecting bitmap commits", 0);
463 if (indexed_commits_nr < 100) {
464 for (i = 0; i < indexed_commits_nr; ++i)
465 push_bitmapped_commit(indexed_commits[i], NULL);
470 struct ewah_bitmap *reused_bitmap = NULL;
471 struct commit *chosen = NULL;
473 next = next_commit_index(i);
475 if (i + next >= indexed_commits_nr)
478 if (max_bitmaps > 0 && writer.selected_nr >= max_bitmaps) {
479 writer.selected_nr = max_bitmaps;
484 chosen = indexed_commits[i];
485 reused_bitmap = find_reused_bitmap(&chosen->object.oid);
487 chosen = indexed_commits[i + next];
489 for (j = 0; j <= next; ++j) {
490 struct commit *cm = indexed_commits[i + j];
492 reused_bitmap = find_reused_bitmap(&cm->object.oid);
493 if (reused_bitmap || (cm->object.flags & NEEDS_BITMAP) != 0) {
498 if (cm->parents && cm->parents->next)
503 push_bitmapped_commit(chosen, reused_bitmap);
506 display_progress(writer.progress, i);
509 stop_progress(&writer.progress);
513 static int hashwrite_ewah_helper(void *f, const void *buf, size_t len)
515 /* hashwrite will die on error */
516 hashwrite(f, buf, len);
521 * Write the bitmap index to disk
523 static inline void dump_bitmap(struct hashfile *f, struct ewah_bitmap *bitmap)
525 if (ewah_serialize_to(bitmap, hashwrite_ewah_helper, f) < 0)
526 die("Failed to write bitmap index");
529 static const unsigned char *sha1_access(size_t pos, void *table)
531 struct pack_idx_entry **index = table;
532 return index[pos]->oid.hash;
535 static void write_selected_commits_v1(struct hashfile *f,
536 struct pack_idx_entry **index,
541 for (i = 0; i < writer.selected_nr; ++i) {
542 struct bitmapped_commit *stored = &writer.selected[i];
545 sha1_pos(stored->commit->object.oid.hash, index, index_nr, sha1_access);
548 BUG("trying to write commit not in index");
550 hashwrite_be32(f, commit_pos);
551 hashwrite_u8(f, stored->xor_offset);
552 hashwrite_u8(f, stored->flags);
554 dump_bitmap(f, stored->write_as);
558 static void write_hash_cache(struct hashfile *f,
559 struct pack_idx_entry **index,
564 for (i = 0; i < index_nr; ++i) {
565 struct object_entry *entry = (struct object_entry *)index[i];
566 hashwrite_be32(f, entry->hash);
570 void bitmap_writer_set_checksum(unsigned char *sha1)
572 hashcpy(writer.pack_checksum, sha1);
575 void bitmap_writer_finish(struct pack_idx_entry **index,
577 const char *filename,
580 static uint16_t default_version = 1;
581 static uint16_t flags = BITMAP_OPT_FULL_DAG;
582 struct strbuf tmp_file = STRBUF_INIT;
585 struct bitmap_disk_header header;
587 int fd = odb_mkstemp(&tmp_file, "pack/tmp_bitmap_XXXXXX");
589 f = hashfd(fd, tmp_file.buf);
591 memcpy(header.magic, BITMAP_IDX_SIGNATURE, sizeof(BITMAP_IDX_SIGNATURE));
592 header.version = htons(default_version);
593 header.options = htons(flags | options);
594 header.entry_count = htonl(writer.selected_nr);
595 hashcpy(header.checksum, writer.pack_checksum);
597 hashwrite(f, &header, sizeof(header) - GIT_MAX_RAWSZ + the_hash_algo->rawsz);
598 dump_bitmap(f, writer.commits);
599 dump_bitmap(f, writer.trees);
600 dump_bitmap(f, writer.blobs);
601 dump_bitmap(f, writer.tags);
602 write_selected_commits_v1(f, index, index_nr);
604 if (options & BITMAP_OPT_HASH_CACHE)
605 write_hash_cache(f, index, index_nr);
607 finalize_hashfile(f, NULL, CSUM_HASH_IN_STREAM | CSUM_FSYNC | CSUM_CLOSE);
609 if (adjust_shared_perm(tmp_file.buf))
610 die_errno("unable to make temporary bitmap file readable");
612 if (rename(tmp_file.buf, filename))
613 die_errno("unable to rename temporary bitmap file to '%s'", filename);
615 strbuf_release(&tmp_file);