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
,
199 struct bitmap_index
*old_bitmap
)
201 struct rev_info revs
;
202 struct commit
*commit
;
203 struct commit_list
*reusable
= NULL
;
204 struct commit_list
*r
;
205 unsigned int i
, num_maximal
= 0;
207 memset(bb
, 0, sizeof(*bb
));
208 init_bb_data(&bb
->data
);
210 reset_revision_walk();
211 repo_init_revisions(writer
->to_pack
->repo
, &revs
, NULL
);
213 revs
.first_parent_only
= 1;
215 for (i
= 0; i
< writer
->selected_nr
; i
++) {
216 struct commit
*c
= writer
->selected
[i
].commit
;
217 struct bb_commit
*ent
= bb_data_at(&bb
->data
, c
);
223 ent
->commit_mask
= bitmap_new();
224 bitmap_set(ent
->commit_mask
, i
);
226 add_pending_object(&revs
, &c
->object
, "");
229 if (prepare_revision_walk(&revs
))
230 die("revision walk setup failed");
232 while ((commit
= get_revision(&revs
))) {
233 struct commit_list
*p
= commit
->parents
;
234 struct bb_commit
*c_ent
;
236 parse_commit_or_die(commit
);
238 c_ent
= bb_data_at(&bb
->data
, commit
);
241 * If there is no commit_mask, there is no reason to iterate
242 * over this commit; it is not selected (if it were, it would
243 * not have a blank commit mask) and all its children have
244 * existing bitmaps (see the comment starting with "This commit
245 * has an existing bitmap" below), so it does not contribute
246 * anything to the final bitmap file or its descendants.
248 if (!c_ent
->commit_mask
)
251 if (old_bitmap
&& bitmap_for_commit(old_bitmap
, commit
)) {
253 * This commit has an existing bitmap, so we can
254 * get its bits immediately without an object
255 * walk. That is, it is reusable as-is and there is no
256 * need to continue walking beyond it.
258 * Mark it as such and add it to bb->commits separately
259 * to avoid allocating a position in the commit mask.
261 commit_list_insert(commit
, &reusable
);
265 if (c_ent
->maximal
) {
267 ALLOC_GROW(bb
->commits
, bb
->commits_nr
+ 1, bb
->commits_alloc
);
268 bb
->commits
[bb
->commits_nr
++] = commit
;
272 struct bb_commit
*p_ent
= bb_data_at(&bb
->data
, p
->item
);
273 int c_not_p
, p_not_c
;
275 if (!p_ent
->commit_mask
) {
276 p_ent
->commit_mask
= bitmap_new();
280 c_not_p
= bitmap_is_subset(c_ent
->commit_mask
, p_ent
->commit_mask
);
281 p_not_c
= bitmap_is_subset(p_ent
->commit_mask
, c_ent
->commit_mask
);
287 bitmap_or(p_ent
->commit_mask
, c_ent
->commit_mask
);
293 free_commit_list(p_ent
->reverse_edges
);
294 p_ent
->reverse_edges
= NULL
;
297 if (c_ent
->maximal
) {
298 commit_list_insert(commit
, &p_ent
->reverse_edges
);
300 struct commit_list
*cc
= c_ent
->reverse_edges
;
302 for (; cc
; cc
= cc
->next
) {
303 if (!commit_list_contains(cc
->item
, p_ent
->reverse_edges
))
304 commit_list_insert(cc
->item
, &p_ent
->reverse_edges
);
310 bitmap_free(c_ent
->commit_mask
);
311 c_ent
->commit_mask
= NULL
;
314 for (r
= reusable
; r
; r
= r
->next
) {
315 ALLOC_GROW(bb
->commits
, bb
->commits_nr
+ 1, bb
->commits_alloc
);
316 bb
->commits
[bb
->commits_nr
++] = r
->item
;
319 trace2_data_intmax("pack-bitmap-write", the_repository
,
320 "num_selected_commits", writer
->selected_nr
);
321 trace2_data_intmax("pack-bitmap-write", the_repository
,
322 "num_maximal_commits", num_maximal
);
324 free_commit_list(reusable
);
327 static void bitmap_builder_clear(struct bitmap_builder
*bb
)
329 clear_bb_data(&bb
->data
);
331 bb
->commits_nr
= bb
->commits_alloc
= 0;
334 static void fill_bitmap_tree(struct bitmap
*bitmap
,
338 struct tree_desc desc
;
339 struct name_entry entry
;
342 * If our bit is already set, then there is nothing to do. Both this
343 * tree and all of its children will be set.
345 pos
= find_object_pos(&tree
->object
.oid
);
346 if (bitmap_get(bitmap
, pos
))
348 bitmap_set(bitmap
, pos
);
350 if (parse_tree(tree
) < 0)
351 die("unable to load tree object %s",
352 oid_to_hex(&tree
->object
.oid
));
353 init_tree_desc(&desc
, tree
->buffer
, tree
->size
);
355 while (tree_entry(&desc
, &entry
)) {
356 switch (object_type(entry
.mode
)) {
358 fill_bitmap_tree(bitmap
,
359 lookup_tree(the_repository
, &entry
.oid
));
362 bitmap_set(bitmap
, find_object_pos(&entry
.oid
));
365 /* Gitlink, etc; not reachable */
370 free_tree_buffer(tree
);
373 static void fill_bitmap_commit(struct bb_commit
*ent
,
374 struct commit
*commit
,
375 struct prio_queue
*queue
,
376 struct prio_queue
*tree_queue
,
377 struct bitmap_index
*old_bitmap
,
378 const uint32_t *mapping
)
381 ent
->bitmap
= bitmap_new();
383 prio_queue_put(queue
, commit
);
386 struct commit_list
*p
;
387 struct commit
*c
= prio_queue_get(queue
);
389 if (old_bitmap
&& mapping
) {
390 struct ewah_bitmap
*old
= bitmap_for_commit(old_bitmap
, c
);
392 * If this commit has an old bitmap, then translate that
393 * bitmap and add its bits to this one. No need to walk
394 * parents or the tree for this commit.
396 if (old
&& !rebuild_bitmap(mapping
, old
, ent
->bitmap
))
401 * Mark ourselves and queue our tree. The commit
402 * walk ensures we cover all parents.
404 bitmap_set(ent
->bitmap
, find_object_pos(&c
->object
.oid
));
405 prio_queue_put(tree_queue
, get_commit_tree(c
));
407 for (p
= c
->parents
; p
; p
= p
->next
) {
408 int pos
= find_object_pos(&p
->item
->object
.oid
);
409 if (!bitmap_get(ent
->bitmap
, pos
)) {
410 bitmap_set(ent
->bitmap
, pos
);
411 prio_queue_put(queue
, p
->item
);
416 while (tree_queue
->nr
)
417 fill_bitmap_tree(ent
->bitmap
, prio_queue_get(tree_queue
));
420 static void store_selected(struct bb_commit
*ent
, struct commit
*commit
)
422 struct bitmapped_commit
*stored
= &writer
.selected
[ent
->idx
];
426 stored
->bitmap
= bitmap_to_ewah(ent
->bitmap
);
428 hash_pos
= kh_put_oid_map(writer
.bitmaps
, commit
->object
.oid
, &hash_ret
);
430 die("Duplicate entry when writing index: %s",
431 oid_to_hex(&commit
->object
.oid
));
432 kh_value(writer
.bitmaps
, hash_pos
) = stored
;
435 void bitmap_writer_build(struct packing_data
*to_pack
)
437 struct bitmap_builder bb
;
439 int nr_stored
= 0; /* for progress */
440 struct prio_queue queue
= { compare_commits_by_gen_then_commit_date
};
441 struct prio_queue tree_queue
= { NULL
};
442 struct bitmap_index
*old_bitmap
;
445 writer
.bitmaps
= kh_init_oid_map();
446 writer
.to_pack
= to_pack
;
448 if (writer
.show_progress
)
449 writer
.progress
= start_progress("Building bitmaps", writer
.selected_nr
);
450 trace2_region_enter("pack-bitmap-write", "building_bitmaps_total",
453 old_bitmap
= prepare_bitmap_git(to_pack
->repo
);
455 mapping
= create_bitmap_mapping(old_bitmap
, to_pack
);
459 bitmap_builder_init(&bb
, &writer
, old_bitmap
);
460 for (i
= bb
.commits_nr
; i
> 0; i
--) {
461 struct commit
*commit
= bb
.commits
[i
-1];
462 struct bb_commit
*ent
= bb_data_at(&bb
.data
, commit
);
463 struct commit
*child
;
466 fill_bitmap_commit(ent
, commit
, &queue
, &tree_queue
,
467 old_bitmap
, mapping
);
470 store_selected(ent
, commit
);
472 display_progress(writer
.progress
, nr_stored
);
475 while ((child
= pop_commit(&ent
->reverse_edges
))) {
476 struct bb_commit
*child_ent
=
477 bb_data_at(&bb
.data
, child
);
479 if (child_ent
->bitmap
)
480 bitmap_or(child_ent
->bitmap
, ent
->bitmap
);
482 child_ent
->bitmap
= bitmap_dup(ent
->bitmap
);
484 child_ent
->bitmap
= ent
->bitmap
;
489 bitmap_free(ent
->bitmap
);
492 clear_prio_queue(&queue
);
493 clear_prio_queue(&tree_queue
);
494 bitmap_builder_clear(&bb
);
497 trace2_region_leave("pack-bitmap-write", "building_bitmaps_total",
500 stop_progress(&writer
.progress
);
502 compute_xor_offsets();
506 * Select the commits that will be bitmapped
508 static inline unsigned int next_commit_index(unsigned int idx
)
510 static const unsigned int MIN_COMMITS
= 100;
511 static const unsigned int MAX_COMMITS
= 5000;
513 static const unsigned int MUST_REGION
= 100;
514 static const unsigned int MIN_REGION
= 20000;
516 unsigned int offset
, next
;
518 if (idx
<= MUST_REGION
)
521 if (idx
<= MIN_REGION
) {
522 offset
= idx
- MUST_REGION
;
523 return (offset
< MIN_COMMITS
) ? offset
: MIN_COMMITS
;
526 offset
= idx
- MIN_REGION
;
527 next
= (offset
< MAX_COMMITS
) ? offset
: MAX_COMMITS
;
529 return (next
> MIN_COMMITS
) ? next
: MIN_COMMITS
;
532 static int date_compare(const void *_a
, const void *_b
)
534 struct commit
*a
= *(struct commit
**)_a
;
535 struct commit
*b
= *(struct commit
**)_b
;
536 return (long)b
->date
- (long)a
->date
;
539 void bitmap_writer_select_commits(struct commit
**indexed_commits
,
540 unsigned int indexed_commits_nr
,
543 unsigned int i
= 0, j
, next
;
545 QSORT(indexed_commits
, indexed_commits_nr
, date_compare
);
547 if (writer
.show_progress
)
548 writer
.progress
= start_progress("Selecting bitmap commits", 0);
550 if (indexed_commits_nr
< 100) {
551 for (i
= 0; i
< indexed_commits_nr
; ++i
)
552 push_bitmapped_commit(indexed_commits
[i
]);
557 struct commit
*chosen
= NULL
;
559 next
= next_commit_index(i
);
561 if (i
+ next
>= indexed_commits_nr
)
564 if (max_bitmaps
> 0 && writer
.selected_nr
>= max_bitmaps
) {
565 writer
.selected_nr
= max_bitmaps
;
570 chosen
= indexed_commits
[i
];
572 chosen
= indexed_commits
[i
+ next
];
574 for (j
= 0; j
<= next
; ++j
) {
575 struct commit
*cm
= indexed_commits
[i
+ j
];
577 if ((cm
->object
.flags
& NEEDS_BITMAP
) != 0) {
582 if (cm
->parents
&& cm
->parents
->next
)
587 push_bitmapped_commit(chosen
);
590 display_progress(writer
.progress
, i
);
593 stop_progress(&writer
.progress
);
597 static int hashwrite_ewah_helper(void *f
, const void *buf
, size_t len
)
599 /* hashwrite will die on error */
600 hashwrite(f
, buf
, len
);
605 * Write the bitmap index to disk
607 static inline void dump_bitmap(struct hashfile
*f
, struct ewah_bitmap
*bitmap
)
609 if (ewah_serialize_to(bitmap
, hashwrite_ewah_helper
, f
) < 0)
610 die("Failed to write bitmap index");
613 static const unsigned char *sha1_access(size_t pos
, void *table
)
615 struct pack_idx_entry
**index
= table
;
616 return index
[pos
]->oid
.hash
;
619 static void write_selected_commits_v1(struct hashfile
*f
,
620 struct pack_idx_entry
**index
,
625 for (i
= 0; i
< writer
.selected_nr
; ++i
) {
626 struct bitmapped_commit
*stored
= &writer
.selected
[i
];
629 sha1_pos(stored
->commit
->object
.oid
.hash
, index
, index_nr
, sha1_access
);
632 BUG("trying to write commit not in index");
634 hashwrite_be32(f
, commit_pos
);
635 hashwrite_u8(f
, stored
->xor_offset
);
636 hashwrite_u8(f
, stored
->flags
);
638 dump_bitmap(f
, stored
->write_as
);
642 static void write_hash_cache(struct hashfile
*f
,
643 struct pack_idx_entry
**index
,
648 for (i
= 0; i
< index_nr
; ++i
) {
649 struct object_entry
*entry
= (struct object_entry
*)index
[i
];
650 hashwrite_be32(f
, entry
->hash
);
654 void bitmap_writer_set_checksum(unsigned char *sha1
)
656 hashcpy(writer
.pack_checksum
, sha1
);
659 void bitmap_writer_finish(struct pack_idx_entry
**index
,
661 const char *filename
,
664 static uint16_t default_version
= 1;
665 static uint16_t flags
= BITMAP_OPT_FULL_DAG
;
666 struct strbuf tmp_file
= STRBUF_INIT
;
669 struct bitmap_disk_header header
;
671 int fd
= odb_mkstemp(&tmp_file
, "pack/tmp_bitmap_XXXXXX");
673 f
= hashfd(fd
, tmp_file
.buf
);
675 memcpy(header
.magic
, BITMAP_IDX_SIGNATURE
, sizeof(BITMAP_IDX_SIGNATURE
));
676 header
.version
= htons(default_version
);
677 header
.options
= htons(flags
| options
);
678 header
.entry_count
= htonl(writer
.selected_nr
);
679 hashcpy(header
.checksum
, writer
.pack_checksum
);
681 hashwrite(f
, &header
, sizeof(header
) - GIT_MAX_RAWSZ
+ the_hash_algo
->rawsz
);
682 dump_bitmap(f
, writer
.commits
);
683 dump_bitmap(f
, writer
.trees
);
684 dump_bitmap(f
, writer
.blobs
);
685 dump_bitmap(f
, writer
.tags
);
686 write_selected_commits_v1(f
, index
, index_nr
);
688 if (options
& BITMAP_OPT_HASH_CACHE
)
689 write_hash_cache(f
, index
, index_nr
);
691 finalize_hashfile(f
, NULL
, CSUM_HASH_IN_STREAM
| CSUM_FSYNC
| CSUM_CLOSE
);
693 if (adjust_shared_perm(tmp_file
.buf
))
694 die_errno("unable to make temporary bitmap file readable");
696 if (rename(tmp_file
.buf
, filename
))
697 die_errno("unable to rename temporary bitmap file to '%s'", filename
);
699 strbuf_release(&tmp_file
);