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"
15 struct bitmapped_commit
{
16 struct commit
*commit
;
17 struct ewah_bitmap
*bitmap
;
18 struct ewah_bitmap
*write_as
;
24 struct bitmap_writer
{
25 struct ewah_bitmap
*commits
;
26 struct ewah_bitmap
*trees
;
27 struct ewah_bitmap
*blobs
;
28 struct ewah_bitmap
*tags
;
32 struct packing_data
*to_pack
;
34 struct bitmapped_commit
*selected
;
35 unsigned int selected_nr
, selected_alloc
;
37 struct progress
*progress
;
39 unsigned char pack_checksum
[20];
42 static struct bitmap_writer writer
;
44 void bitmap_writer_show_progress(int show
)
46 writer
.show_progress
= show
;
50 * Build the initial type index for the packfile
52 void bitmap_writer_build_type_index(struct pack_idx_entry
**index
,
57 writer
.commits
= ewah_new();
58 writer
.trees
= ewah_new();
59 writer
.blobs
= ewah_new();
60 writer
.tags
= ewah_new();
62 for (i
= 0; i
< index_nr
; ++i
) {
63 struct object_entry
*entry
= (struct object_entry
*)index
[i
];
64 enum object_type real_type
;
66 entry
->in_pack_pos
= i
;
68 switch (entry
->type
) {
73 real_type
= entry
->type
;
77 real_type
= oid_object_info(the_repository
,
78 &entry
->idx
.oid
, NULL
);
84 ewah_set(writer
.commits
, i
);
88 ewah_set(writer
.trees
, i
);
92 ewah_set(writer
.blobs
, i
);
96 ewah_set(writer
.tags
, i
);
100 die("Missing type information for %s (%d/%d)",
101 oid_to_hex(&entry
->idx
.oid
), real_type
,
108 * Compute the actual bitmaps
110 static struct object
**seen_objects
;
111 static unsigned int seen_objects_nr
, seen_objects_alloc
;
113 static inline void push_bitmapped_commit(struct commit
*commit
, struct ewah_bitmap
*reused
)
115 if (writer
.selected_nr
>= writer
.selected_alloc
) {
116 writer
.selected_alloc
= (writer
.selected_alloc
+ 32) * 2;
117 REALLOC_ARRAY(writer
.selected
, writer
.selected_alloc
);
120 writer
.selected
[writer
.selected_nr
].commit
= commit
;
121 writer
.selected
[writer
.selected_nr
].bitmap
= reused
;
122 writer
.selected
[writer
.selected_nr
].flags
= 0;
124 writer
.selected_nr
++;
127 static inline void mark_as_seen(struct object
*object
)
129 ALLOC_GROW(seen_objects
, seen_objects_nr
+ 1, seen_objects_alloc
);
130 seen_objects
[seen_objects_nr
++] = object
;
133 static inline void reset_all_seen(void)
136 for (i
= 0; i
< seen_objects_nr
; ++i
) {
137 seen_objects
[i
]->flags
&= ~(SEEN
| ADDED
| SHOWN
);
142 static uint32_t find_object_pos(const unsigned char *sha1
)
144 struct object_entry
*entry
= packlist_find(writer
.to_pack
, sha1
, NULL
);
147 die("Failed to write bitmap index. Packfile doesn't have full closure "
148 "(object %s is missing)", sha1_to_hex(sha1
));
151 return entry
->in_pack_pos
;
154 static void show_object(struct object
*object
, const char *name
, void *data
)
156 struct bitmap
*base
= data
;
157 bitmap_set(base
, find_object_pos(object
->oid
.hash
));
158 mark_as_seen(object
);
161 static void show_commit(struct commit
*commit
, void *data
)
163 mark_as_seen((struct object
*)commit
);
167 add_to_include_set(struct bitmap
*base
, struct commit
*commit
)
170 uint32_t bitmap_pos
= find_object_pos(commit
->object
.oid
.hash
);
172 if (bitmap_get(base
, bitmap_pos
))
175 hash_pos
= kh_get_sha1(writer
.bitmaps
, commit
->object
.oid
.hash
);
176 if (hash_pos
< kh_end(writer
.bitmaps
)) {
177 struct bitmapped_commit
*bc
= kh_value(writer
.bitmaps
, hash_pos
);
178 bitmap_or_ewah(base
, bc
->bitmap
);
182 bitmap_set(base
, bitmap_pos
);
187 should_include(struct commit
*commit
, void *_data
)
189 struct bitmap
*base
= _data
;
191 if (!add_to_include_set(base
, commit
)) {
192 struct commit_list
*parent
= commit
->parents
;
194 mark_as_seen((struct object
*)commit
);
197 parent
->item
->object
.flags
|= SEEN
;
198 mark_as_seen((struct object
*)parent
->item
);
199 parent
= parent
->next
;
208 static void compute_xor_offsets(void)
210 static const int MAX_XOR_OFFSET_SEARCH
= 10;
214 while (next
< writer
.selected_nr
) {
215 struct bitmapped_commit
*stored
= &writer
.selected
[next
];
218 struct ewah_bitmap
*best_bitmap
= stored
->bitmap
;
219 struct ewah_bitmap
*test_xor
;
221 for (i
= 1; i
<= MAX_XOR_OFFSET_SEARCH
; ++i
) {
227 test_xor
= ewah_pool_new();
228 ewah_xor(writer
.selected
[curr
].bitmap
, stored
->bitmap
, test_xor
);
230 if (test_xor
->buffer_size
< best_bitmap
->buffer_size
) {
231 if (best_bitmap
!= stored
->bitmap
)
232 ewah_pool_free(best_bitmap
);
234 best_bitmap
= test_xor
;
237 ewah_pool_free(test_xor
);
241 stored
->xor_offset
= best_offset
;
242 stored
->write_as
= best_bitmap
;
248 void bitmap_writer_build(struct packing_data
*to_pack
)
250 static const double REUSE_BITMAP_THRESHOLD
= 0.2;
252 int i
, reuse_after
, need_reset
;
253 struct bitmap
*base
= bitmap_new();
254 struct rev_info revs
;
256 writer
.bitmaps
= kh_init_sha1();
257 writer
.to_pack
= to_pack
;
259 if (writer
.show_progress
)
260 writer
.progress
= start_progress("Building bitmaps", writer
.selected_nr
);
262 init_revisions(&revs
, NULL
);
263 revs
.tag_objects
= 1;
264 revs
.tree_objects
= 1;
265 revs
.blob_objects
= 1;
268 revs
.include_check
= should_include
;
269 reset_revision_walk();
271 reuse_after
= writer
.selected_nr
* REUSE_BITMAP_THRESHOLD
;
274 for (i
= writer
.selected_nr
- 1; i
>= 0; --i
) {
275 struct bitmapped_commit
*stored
;
276 struct object
*object
;
281 stored
= &writer
.selected
[i
];
282 object
= (struct object
*)stored
->commit
;
284 if (stored
->bitmap
== NULL
) {
285 if (i
< writer
.selected_nr
- 1 &&
287 !in_merge_bases(writer
.selected
[i
+ 1].commit
,
293 add_pending_object(&revs
, object
, "");
294 revs
.include_check_data
= base
;
296 if (prepare_revision_walk(&revs
))
297 die("revision walk setup failed");
299 traverse_commit_list(&revs
, show_commit
, show_object
, base
);
301 object_array_clear(&revs
.pending
);
303 stored
->bitmap
= bitmap_to_ewah(base
);
308 if (i
>= reuse_after
)
309 stored
->flags
|= BITMAP_FLAG_REUSE
;
311 hash_pos
= kh_put_sha1(writer
.bitmaps
, object
->oid
.hash
, &hash_ret
);
313 die("Duplicate entry when writing index: %s",
314 oid_to_hex(&object
->oid
));
316 kh_value(writer
.bitmaps
, hash_pos
) = stored
;
317 display_progress(writer
.progress
, writer
.selected_nr
- i
);
321 stop_progress(&writer
.progress
);
323 compute_xor_offsets();
327 * Select the commits that will be bitmapped
329 static inline unsigned int next_commit_index(unsigned int idx
)
331 static const unsigned int MIN_COMMITS
= 100;
332 static const unsigned int MAX_COMMITS
= 5000;
334 static const unsigned int MUST_REGION
= 100;
335 static const unsigned int MIN_REGION
= 20000;
337 unsigned int offset
, next
;
339 if (idx
<= MUST_REGION
)
342 if (idx
<= MIN_REGION
) {
343 offset
= idx
- MUST_REGION
;
344 return (offset
< MIN_COMMITS
) ? offset
: MIN_COMMITS
;
347 offset
= idx
- MIN_REGION
;
348 next
= (offset
< MAX_COMMITS
) ? offset
: MAX_COMMITS
;
350 return (next
> MIN_COMMITS
) ? next
: MIN_COMMITS
;
353 static int date_compare(const void *_a
, const void *_b
)
355 struct commit
*a
= *(struct commit
**)_a
;
356 struct commit
*b
= *(struct commit
**)_b
;
357 return (long)b
->date
- (long)a
->date
;
360 void bitmap_writer_reuse_bitmaps(struct packing_data
*to_pack
)
362 if (prepare_bitmap_git() < 0)
365 writer
.reused
= kh_init_sha1();
366 rebuild_existing_bitmaps(to_pack
, writer
.reused
, writer
.show_progress
);
369 static struct ewah_bitmap
*find_reused_bitmap(const unsigned char *sha1
)
376 hash_pos
= kh_get_sha1(writer
.reused
, sha1
);
377 if (hash_pos
>= kh_end(writer
.reused
))
380 return kh_value(writer
.reused
, hash_pos
);
383 void bitmap_writer_select_commits(struct commit
**indexed_commits
,
384 unsigned int indexed_commits_nr
,
387 unsigned int i
= 0, j
, next
;
389 QSORT(indexed_commits
, indexed_commits_nr
, date_compare
);
391 if (writer
.show_progress
)
392 writer
.progress
= start_progress("Selecting bitmap commits", 0);
394 if (indexed_commits_nr
< 100) {
395 for (i
= 0; i
< indexed_commits_nr
; ++i
)
396 push_bitmapped_commit(indexed_commits
[i
], NULL
);
401 struct ewah_bitmap
*reused_bitmap
= NULL
;
402 struct commit
*chosen
= NULL
;
404 next
= next_commit_index(i
);
406 if (i
+ next
>= indexed_commits_nr
)
409 if (max_bitmaps
> 0 && writer
.selected_nr
>= max_bitmaps
) {
410 writer
.selected_nr
= max_bitmaps
;
415 chosen
= indexed_commits
[i
];
416 reused_bitmap
= find_reused_bitmap(chosen
->object
.oid
.hash
);
418 chosen
= indexed_commits
[i
+ next
];
420 for (j
= 0; j
<= next
; ++j
) {
421 struct commit
*cm
= indexed_commits
[i
+ j
];
423 reused_bitmap
= find_reused_bitmap(cm
->object
.oid
.hash
);
424 if (reused_bitmap
|| (cm
->object
.flags
& NEEDS_BITMAP
) != 0) {
429 if (cm
->parents
&& cm
->parents
->next
)
434 push_bitmapped_commit(chosen
, reused_bitmap
);
437 display_progress(writer
.progress
, i
);
440 stop_progress(&writer
.progress
);
444 static int hashwrite_ewah_helper(void *f
, const void *buf
, size_t len
)
446 /* hashwrite will die on error */
447 hashwrite(f
, buf
, len
);
452 * Write the bitmap index to disk
454 static inline void dump_bitmap(struct hashfile
*f
, struct ewah_bitmap
*bitmap
)
456 if (ewah_serialize_to(bitmap
, hashwrite_ewah_helper
, f
) < 0)
457 die("Failed to write bitmap index");
460 static const unsigned char *sha1_access(size_t pos
, void *table
)
462 struct pack_idx_entry
**index
= table
;
463 return index
[pos
]->oid
.hash
;
466 static void write_selected_commits_v1(struct hashfile
*f
,
467 struct pack_idx_entry
**index
,
472 for (i
= 0; i
< writer
.selected_nr
; ++i
) {
473 struct bitmapped_commit
*stored
= &writer
.selected
[i
];
476 sha1_pos(stored
->commit
->object
.oid
.hash
, index
, index_nr
, sha1_access
);
479 die("BUG: trying to write commit not in index");
481 hashwrite_be32(f
, commit_pos
);
482 hashwrite_u8(f
, stored
->xor_offset
);
483 hashwrite_u8(f
, stored
->flags
);
485 dump_bitmap(f
, stored
->write_as
);
489 static void write_hash_cache(struct hashfile
*f
,
490 struct pack_idx_entry
**index
,
495 for (i
= 0; i
< index_nr
; ++i
) {
496 struct object_entry
*entry
= (struct object_entry
*)index
[i
];
497 uint32_t hash_value
= htonl(entry
->hash
);
498 hashwrite(f
, &hash_value
, sizeof(hash_value
));
502 void bitmap_writer_set_checksum(unsigned char *sha1
)
504 hashcpy(writer
.pack_checksum
, sha1
);
507 void bitmap_writer_finish(struct pack_idx_entry
**index
,
509 const char *filename
,
512 static uint16_t default_version
= 1;
513 static uint16_t flags
= BITMAP_OPT_FULL_DAG
;
514 struct strbuf tmp_file
= STRBUF_INIT
;
517 struct bitmap_disk_header header
;
519 int fd
= odb_mkstemp(&tmp_file
, "pack/tmp_bitmap_XXXXXX");
521 f
= hashfd(fd
, tmp_file
.buf
);
523 memcpy(header
.magic
, BITMAP_IDX_SIGNATURE
, sizeof(BITMAP_IDX_SIGNATURE
));
524 header
.version
= htons(default_version
);
525 header
.options
= htons(flags
| options
);
526 header
.entry_count
= htonl(writer
.selected_nr
);
527 hashcpy(header
.checksum
, writer
.pack_checksum
);
529 hashwrite(f
, &header
, sizeof(header
));
530 dump_bitmap(f
, writer
.commits
);
531 dump_bitmap(f
, writer
.trees
);
532 dump_bitmap(f
, writer
.blobs
);
533 dump_bitmap(f
, writer
.tags
);
534 write_selected_commits_v1(f
, index
, index_nr
);
536 if (options
& BITMAP_OPT_HASH_CACHE
)
537 write_hash_cache(f
, index
, index_nr
);
539 hashclose(f
, NULL
, CSUM_FSYNC
);
541 if (adjust_shared_perm(tmp_file
.buf
))
542 die_errno("unable to make temporary bitmap file readable");
544 if (rename(tmp_file
.buf
, filename
))
545 die_errno("unable to rename temporary bitmap file to '%s'", filename
);
547 strbuf_release(&tmp_file
);