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
;
33 struct packing_data
*to_pack
;
35 struct bitmapped_commit
*selected
;
36 unsigned int selected_nr
, selected_alloc
;
38 struct progress
*progress
;
40 unsigned char pack_checksum
[GIT_MAX_RAWSZ
];
43 static struct bitmap_writer writer
;
45 void bitmap_writer_show_progress(int show
)
47 writer
.show_progress
= show
;
51 * Build the initial type index for the packfile
53 void bitmap_writer_build_type_index(struct packing_data
*to_pack
,
54 struct pack_idx_entry
**index
,
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
);
65 for (i
= 0; i
< index_nr
; ++i
) {
66 struct object_entry
*entry
= (struct object_entry
*)index
[i
];
67 enum object_type real_type
;
69 oe_set_in_pack_pos(to_pack
, entry
, i
);
71 switch (oe_type(entry
)) {
76 real_type
= oe_type(entry
);
80 real_type
= oid_object_info(to_pack
->repo
,
81 &entry
->idx
.oid
, NULL
);
87 ewah_set(writer
.commits
, i
);
91 ewah_set(writer
.trees
, i
);
95 ewah_set(writer
.blobs
, i
);
99 ewah_set(writer
.tags
, i
);
103 die("Missing type information for %s (%d/%d)",
104 oid_to_hex(&entry
->idx
.oid
), real_type
,
111 * Compute the actual bitmaps
114 static inline void push_bitmapped_commit(struct commit
*commit
)
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
);
121 writer
.selected
[writer
.selected_nr
].commit
= commit
;
122 writer
.selected
[writer
.selected_nr
].bitmap
= NULL
;
123 writer
.selected
[writer
.selected_nr
].flags
= 0;
125 writer
.selected_nr
++;
128 static uint32_t find_object_pos(const struct object_id
*oid
)
130 struct object_entry
*entry
= packlist_find(writer
.to_pack
, oid
);
133 die("Failed to write bitmap index. Packfile doesn't have full closure "
134 "(object %s is missing)", oid_to_hex(oid
));
137 return oe_in_pack_pos(writer
.to_pack
, entry
);
140 static void compute_xor_offsets(void)
142 static const int MAX_XOR_OFFSET_SEARCH
= 10;
146 while (next
< writer
.selected_nr
) {
147 struct bitmapped_commit
*stored
= &writer
.selected
[next
];
150 struct ewah_bitmap
*best_bitmap
= stored
->bitmap
;
151 struct ewah_bitmap
*test_xor
;
153 for (i
= 1; i
<= MAX_XOR_OFFSET_SEARCH
; ++i
) {
159 test_xor
= ewah_pool_new();
160 ewah_xor(writer
.selected
[curr
].bitmap
, stored
->bitmap
, test_xor
);
162 if (test_xor
->buffer_size
< best_bitmap
->buffer_size
) {
163 if (best_bitmap
!= stored
->bitmap
)
164 ewah_pool_free(best_bitmap
);
166 best_bitmap
= test_xor
;
169 ewah_pool_free(test_xor
);
173 stored
->xor_offset
= best_offset
;
174 stored
->write_as
= best_bitmap
;
181 struct commit_list
*reverse_edges
;
182 struct bitmap
*commit_mask
;
183 struct bitmap
*bitmap
;
186 unsigned idx
; /* within selected array */
189 define_commit_slab(bb_data
, struct bb_commit
);
191 struct bitmap_builder
{
193 struct commit
**commits
;
194 size_t commits_nr
, commits_alloc
;
197 static void bitmap_builder_init(struct bitmap_builder
*bb
,
198 struct bitmap_writer
*writer
)
200 struct rev_info revs
;
201 struct commit
*commit
;
202 unsigned int i
, num_maximal
= 0;
204 memset(bb
, 0, sizeof(*bb
));
205 init_bb_data(&bb
->data
);
207 reset_revision_walk();
208 repo_init_revisions(writer
->to_pack
->repo
, &revs
, NULL
);
210 revs
.first_parent_only
= 1;
212 for (i
= 0; i
< writer
->selected_nr
; i
++) {
213 struct commit
*c
= writer
->selected
[i
].commit
;
214 struct bb_commit
*ent
= bb_data_at(&bb
->data
, c
);
220 ent
->commit_mask
= bitmap_new();
221 bitmap_set(ent
->commit_mask
, i
);
223 add_pending_object(&revs
, &c
->object
, "");
226 if (prepare_revision_walk(&revs
))
227 die("revision walk setup failed");
229 while ((commit
= get_revision(&revs
))) {
230 struct commit_list
*p
= commit
->parents
;
231 struct bb_commit
*c_ent
;
233 parse_commit_or_die(commit
);
235 c_ent
= bb_data_at(&bb
->data
, commit
);
237 if (c_ent
->maximal
) {
239 ALLOC_GROW(bb
->commits
, bb
->commits_nr
+ 1, bb
->commits_alloc
);
240 bb
->commits
[bb
->commits_nr
++] = commit
;
244 struct bb_commit
*p_ent
= bb_data_at(&bb
->data
, p
->item
);
245 int c_not_p
, p_not_c
;
247 if (!p_ent
->commit_mask
) {
248 p_ent
->commit_mask
= bitmap_new();
252 c_not_p
= bitmap_is_subset(c_ent
->commit_mask
, p_ent
->commit_mask
);
253 p_not_c
= bitmap_is_subset(p_ent
->commit_mask
, c_ent
->commit_mask
);
259 bitmap_or(p_ent
->commit_mask
, c_ent
->commit_mask
);
265 free_commit_list(p_ent
->reverse_edges
);
266 p_ent
->reverse_edges
= NULL
;
269 if (c_ent
->maximal
) {
270 commit_list_insert(commit
, &p_ent
->reverse_edges
);
272 struct commit_list
*cc
= c_ent
->reverse_edges
;
274 for (; cc
; cc
= cc
->next
) {
275 if (!commit_list_contains(cc
->item
, p_ent
->reverse_edges
))
276 commit_list_insert(cc
->item
, &p_ent
->reverse_edges
);
281 bitmap_free(c_ent
->commit_mask
);
282 c_ent
->commit_mask
= NULL
;
285 trace2_data_intmax("pack-bitmap-write", the_repository
,
286 "num_selected_commits", writer
->selected_nr
);
287 trace2_data_intmax("pack-bitmap-write", the_repository
,
288 "num_maximal_commits", num_maximal
);
291 static void bitmap_builder_clear(struct bitmap_builder
*bb
)
293 clear_bb_data(&bb
->data
);
295 bb
->commits_nr
= bb
->commits_alloc
= 0;
298 static void fill_bitmap_tree(struct bitmap
*bitmap
,
302 struct tree_desc desc
;
303 struct name_entry entry
;
306 * If our bit is already set, then there is nothing to do. Both this
307 * tree and all of its children will be set.
309 pos
= find_object_pos(&tree
->object
.oid
);
310 if (bitmap_get(bitmap
, pos
))
312 bitmap_set(bitmap
, pos
);
314 if (parse_tree(tree
) < 0)
315 die("unable to load tree object %s",
316 oid_to_hex(&tree
->object
.oid
));
317 init_tree_desc(&desc
, tree
->buffer
, tree
->size
);
319 while (tree_entry(&desc
, &entry
)) {
320 switch (object_type(entry
.mode
)) {
322 fill_bitmap_tree(bitmap
,
323 lookup_tree(the_repository
, &entry
.oid
));
326 bitmap_set(bitmap
, find_object_pos(&entry
.oid
));
329 /* Gitlink, etc; not reachable */
334 free_tree_buffer(tree
);
337 static void fill_bitmap_commit(struct bb_commit
*ent
,
338 struct commit
*commit
,
339 struct prio_queue
*queue
,
340 struct prio_queue
*tree_queue
,
341 struct bitmap_index
*old_bitmap
,
342 const uint32_t *mapping
)
345 ent
->bitmap
= bitmap_new();
347 prio_queue_put(queue
, commit
);
350 struct commit_list
*p
;
351 struct commit
*c
= prio_queue_get(queue
);
353 if (old_bitmap
&& mapping
) {
354 struct ewah_bitmap
*old
= bitmap_for_commit(old_bitmap
, c
);
356 * If this commit has an old bitmap, then translate that
357 * bitmap and add its bits to this one. No need to walk
358 * parents or the tree for this commit.
360 if (old
&& !rebuild_bitmap(mapping
, old
, ent
->bitmap
))
365 * Mark ourselves and queue our tree. The commit
366 * walk ensures we cover all parents.
368 bitmap_set(ent
->bitmap
, find_object_pos(&c
->object
.oid
));
369 prio_queue_put(tree_queue
, get_commit_tree(c
));
371 for (p
= c
->parents
; p
; p
= p
->next
) {
372 int pos
= find_object_pos(&p
->item
->object
.oid
);
373 if (!bitmap_get(ent
->bitmap
, pos
)) {
374 bitmap_set(ent
->bitmap
, pos
);
375 prio_queue_put(queue
, p
->item
);
380 while (tree_queue
->nr
)
381 fill_bitmap_tree(ent
->bitmap
, prio_queue_get(tree_queue
));
384 static void store_selected(struct bb_commit
*ent
, struct commit
*commit
)
386 struct bitmapped_commit
*stored
= &writer
.selected
[ent
->idx
];
390 stored
->bitmap
= bitmap_to_ewah(ent
->bitmap
);
392 hash_pos
= kh_put_oid_map(writer
.bitmaps
, commit
->object
.oid
, &hash_ret
);
394 die("Duplicate entry when writing index: %s",
395 oid_to_hex(&commit
->object
.oid
));
396 kh_value(writer
.bitmaps
, hash_pos
) = stored
;
399 void bitmap_writer_build(struct packing_data
*to_pack
)
401 struct bitmap_builder bb
;
403 int nr_stored
= 0; /* for progress */
404 struct prio_queue queue
= { compare_commits_by_gen_then_commit_date
};
405 struct prio_queue tree_queue
= { NULL
};
406 struct bitmap_index
*old_bitmap
;
409 writer
.bitmaps
= kh_init_oid_map();
410 writer
.to_pack
= to_pack
;
412 if (writer
.show_progress
)
413 writer
.progress
= start_progress("Building bitmaps", writer
.selected_nr
);
414 trace2_region_enter("pack-bitmap-write", "building_bitmaps_total",
417 old_bitmap
= prepare_bitmap_git(to_pack
->repo
);
419 mapping
= create_bitmap_mapping(old_bitmap
, to_pack
);
423 bitmap_builder_init(&bb
, &writer
);
424 for (i
= bb
.commits_nr
; i
> 0; i
--) {
425 struct commit
*commit
= bb
.commits
[i
-1];
426 struct bb_commit
*ent
= bb_data_at(&bb
.data
, commit
);
427 struct commit
*child
;
430 fill_bitmap_commit(ent
, commit
, &queue
, &tree_queue
,
431 old_bitmap
, mapping
);
434 store_selected(ent
, commit
);
436 display_progress(writer
.progress
, nr_stored
);
439 while ((child
= pop_commit(&ent
->reverse_edges
))) {
440 struct bb_commit
*child_ent
=
441 bb_data_at(&bb
.data
, child
);
443 if (child_ent
->bitmap
)
444 bitmap_or(child_ent
->bitmap
, ent
->bitmap
);
446 child_ent
->bitmap
= bitmap_dup(ent
->bitmap
);
448 child_ent
->bitmap
= ent
->bitmap
;
453 bitmap_free(ent
->bitmap
);
456 clear_prio_queue(&queue
);
457 clear_prio_queue(&tree_queue
);
458 bitmap_builder_clear(&bb
);
461 trace2_region_leave("pack-bitmap-write", "building_bitmaps_total",
464 stop_progress(&writer
.progress
);
466 compute_xor_offsets();
470 * Select the commits that will be bitmapped
472 static inline unsigned int next_commit_index(unsigned int idx
)
474 static const unsigned int MIN_COMMITS
= 100;
475 static const unsigned int MAX_COMMITS
= 5000;
477 static const unsigned int MUST_REGION
= 100;
478 static const unsigned int MIN_REGION
= 20000;
480 unsigned int offset
, next
;
482 if (idx
<= MUST_REGION
)
485 if (idx
<= MIN_REGION
) {
486 offset
= idx
- MUST_REGION
;
487 return (offset
< MIN_COMMITS
) ? offset
: MIN_COMMITS
;
490 offset
= idx
- MIN_REGION
;
491 next
= (offset
< MAX_COMMITS
) ? offset
: MAX_COMMITS
;
493 return (next
> MIN_COMMITS
) ? next
: MIN_COMMITS
;
496 static int date_compare(const void *_a
, const void *_b
)
498 struct commit
*a
= *(struct commit
**)_a
;
499 struct commit
*b
= *(struct commit
**)_b
;
500 return (long)b
->date
- (long)a
->date
;
503 void bitmap_writer_select_commits(struct commit
**indexed_commits
,
504 unsigned int indexed_commits_nr
,
507 unsigned int i
= 0, j
, next
;
509 QSORT(indexed_commits
, indexed_commits_nr
, date_compare
);
511 if (writer
.show_progress
)
512 writer
.progress
= start_progress("Selecting bitmap commits", 0);
514 if (indexed_commits_nr
< 100) {
515 for (i
= 0; i
< indexed_commits_nr
; ++i
)
516 push_bitmapped_commit(indexed_commits
[i
]);
521 struct commit
*chosen
= NULL
;
523 next
= next_commit_index(i
);
525 if (i
+ next
>= indexed_commits_nr
)
528 if (max_bitmaps
> 0 && writer
.selected_nr
>= max_bitmaps
) {
529 writer
.selected_nr
= max_bitmaps
;
534 chosen
= indexed_commits
[i
];
536 chosen
= indexed_commits
[i
+ next
];
538 for (j
= 0; j
<= next
; ++j
) {
539 struct commit
*cm
= indexed_commits
[i
+ j
];
541 if ((cm
->object
.flags
& NEEDS_BITMAP
) != 0) {
546 if (cm
->parents
&& cm
->parents
->next
)
551 push_bitmapped_commit(chosen
);
554 display_progress(writer
.progress
, i
);
557 stop_progress(&writer
.progress
);
561 static int hashwrite_ewah_helper(void *f
, const void *buf
, size_t len
)
563 /* hashwrite will die on error */
564 hashwrite(f
, buf
, len
);
569 * Write the bitmap index to disk
571 static inline void dump_bitmap(struct hashfile
*f
, struct ewah_bitmap
*bitmap
)
573 if (ewah_serialize_to(bitmap
, hashwrite_ewah_helper
, f
) < 0)
574 die("Failed to write bitmap index");
577 static const unsigned char *sha1_access(size_t pos
, void *table
)
579 struct pack_idx_entry
**index
= table
;
580 return index
[pos
]->oid
.hash
;
583 static void write_selected_commits_v1(struct hashfile
*f
,
584 struct pack_idx_entry
**index
,
589 for (i
= 0; i
< writer
.selected_nr
; ++i
) {
590 struct bitmapped_commit
*stored
= &writer
.selected
[i
];
593 sha1_pos(stored
->commit
->object
.oid
.hash
, index
, index_nr
, sha1_access
);
596 BUG("trying to write commit not in index");
598 hashwrite_be32(f
, commit_pos
);
599 hashwrite_u8(f
, stored
->xor_offset
);
600 hashwrite_u8(f
, stored
->flags
);
602 dump_bitmap(f
, stored
->write_as
);
606 static void write_hash_cache(struct hashfile
*f
,
607 struct pack_idx_entry
**index
,
612 for (i
= 0; i
< index_nr
; ++i
) {
613 struct object_entry
*entry
= (struct object_entry
*)index
[i
];
614 hashwrite_be32(f
, entry
->hash
);
618 void bitmap_writer_set_checksum(unsigned char *sha1
)
620 hashcpy(writer
.pack_checksum
, sha1
);
623 void bitmap_writer_finish(struct pack_idx_entry
**index
,
625 const char *filename
,
628 static uint16_t default_version
= 1;
629 static uint16_t flags
= BITMAP_OPT_FULL_DAG
;
630 struct strbuf tmp_file
= STRBUF_INIT
;
633 struct bitmap_disk_header header
;
635 int fd
= odb_mkstemp(&tmp_file
, "pack/tmp_bitmap_XXXXXX");
637 f
= hashfd(fd
, tmp_file
.buf
);
639 memcpy(header
.magic
, BITMAP_IDX_SIGNATURE
, sizeof(BITMAP_IDX_SIGNATURE
));
640 header
.version
= htons(default_version
);
641 header
.options
= htons(flags
| options
);
642 header
.entry_count
= htonl(writer
.selected_nr
);
643 hashcpy(header
.checksum
, writer
.pack_checksum
);
645 hashwrite(f
, &header
, sizeof(header
) - GIT_MAX_RAWSZ
+ the_hash_algo
->rawsz
);
646 dump_bitmap(f
, writer
.commits
);
647 dump_bitmap(f
, writer
.trees
);
648 dump_bitmap(f
, writer
.blobs
);
649 dump_bitmap(f
, writer
.tags
);
650 write_selected_commits_v1(f
, index
, index_nr
);
652 if (options
& BITMAP_OPT_HASH_CACHE
)
653 write_hash_cache(f
, index
, index_nr
);
655 finalize_hashfile(f
, NULL
, CSUM_HASH_IN_STREAM
| CSUM_FSYNC
| CSUM_CLOSE
);
657 if (adjust_shared_perm(tmp_file
.buf
))
658 die_errno("unable to make temporary bitmap file readable");
660 if (rename(tmp_file
.buf
, filename
))
661 die_errno("unable to rename temporary bitmap file to '%s'", filename
);
663 strbuf_release(&tmp_file
);