6 #include "list-objects.h"
8 #include "pack-revindex.h"
10 #include "pack-bitmap.h"
11 #include "sha1-lookup.h"
12 #include "pack-objects.h"
14 struct bitmapped_commit
{
15 struct commit
*commit
;
16 struct ewah_bitmap
*bitmap
;
17 struct ewah_bitmap
*write_as
;
23 struct bitmap_writer
{
24 struct ewah_bitmap
*commits
;
25 struct ewah_bitmap
*trees
;
26 struct ewah_bitmap
*blobs
;
27 struct ewah_bitmap
*tags
;
31 struct packing_data
*to_pack
;
33 struct bitmapped_commit
*selected
;
34 unsigned int selected_nr
, selected_alloc
;
36 struct progress
*progress
;
38 unsigned char pack_checksum
[20];
41 static struct bitmap_writer writer
;
43 void bitmap_writer_show_progress(int show
)
45 writer
.show_progress
= show
;
49 * Build the initial type index for the packfile
51 void bitmap_writer_build_type_index(struct pack_idx_entry
**index
,
56 writer
.commits
= ewah_new();
57 writer
.trees
= ewah_new();
58 writer
.blobs
= ewah_new();
59 writer
.tags
= ewah_new();
61 for (i
= 0; i
< index_nr
; ++i
) {
62 struct object_entry
*entry
= (struct object_entry
*)index
[i
];
63 enum object_type real_type
;
65 entry
->in_pack_pos
= i
;
67 switch (entry
->type
) {
72 real_type
= entry
->type
;
76 real_type
= sha1_object_info(entry
->idx
.sha1
, NULL
);
82 ewah_set(writer
.commits
, i
);
86 ewah_set(writer
.trees
, i
);
90 ewah_set(writer
.blobs
, i
);
94 ewah_set(writer
.tags
, i
);
98 die("Missing type information for %s (%d/%d)",
99 sha1_to_hex(entry
->idx
.sha1
), real_type
, entry
->type
);
105 * Compute the actual bitmaps
107 static struct object
**seen_objects
;
108 static unsigned int seen_objects_nr
, seen_objects_alloc
;
110 static inline void push_bitmapped_commit(struct commit
*commit
, struct ewah_bitmap
*reused
)
112 if (writer
.selected_nr
>= writer
.selected_alloc
) {
113 writer
.selected_alloc
= (writer
.selected_alloc
+ 32) * 2;
114 REALLOC_ARRAY(writer
.selected
, writer
.selected_alloc
);
117 writer
.selected
[writer
.selected_nr
].commit
= commit
;
118 writer
.selected
[writer
.selected_nr
].bitmap
= reused
;
119 writer
.selected
[writer
.selected_nr
].flags
= 0;
121 writer
.selected_nr
++;
124 static inline void mark_as_seen(struct object
*object
)
126 ALLOC_GROW(seen_objects
, seen_objects_nr
+ 1, seen_objects_alloc
);
127 seen_objects
[seen_objects_nr
++] = object
;
130 static inline void reset_all_seen(void)
133 for (i
= 0; i
< seen_objects_nr
; ++i
) {
134 seen_objects
[i
]->flags
&= ~(SEEN
| ADDED
| SHOWN
);
139 static uint32_t find_object_pos(const unsigned char *sha1
)
141 struct object_entry
*entry
= packlist_find(writer
.to_pack
, sha1
, NULL
);
144 die("Failed to write bitmap index. Packfile doesn't have full closure "
145 "(object %s is missing)", sha1_to_hex(sha1
));
148 return entry
->in_pack_pos
;
151 static void show_object(struct object
*object
, const struct name_path
*path
,
152 const char *last
, void *data
)
154 struct bitmap
*base
= data
;
155 bitmap_set(base
, find_object_pos(object
->sha1
));
156 mark_as_seen(object
);
159 static void show_commit(struct commit
*commit
, void *data
)
161 mark_as_seen((struct object
*)commit
);
165 add_to_include_set(struct bitmap
*base
, struct commit
*commit
)
168 uint32_t bitmap_pos
= find_object_pos(commit
->object
.sha1
);
170 if (bitmap_get(base
, bitmap_pos
))
173 hash_pos
= kh_get_sha1(writer
.bitmaps
, commit
->object
.sha1
);
174 if (hash_pos
< kh_end(writer
.bitmaps
)) {
175 struct bitmapped_commit
*bc
= kh_value(writer
.bitmaps
, hash_pos
);
176 bitmap_or_ewah(base
, bc
->bitmap
);
180 bitmap_set(base
, bitmap_pos
);
185 should_include(struct commit
*commit
, void *_data
)
187 struct bitmap
*base
= _data
;
189 if (!add_to_include_set(base
, commit
)) {
190 struct commit_list
*parent
= commit
->parents
;
192 mark_as_seen((struct object
*)commit
);
195 parent
->item
->object
.flags
|= SEEN
;
196 mark_as_seen((struct object
*)parent
->item
);
197 parent
= parent
->next
;
206 static void compute_xor_offsets(void)
208 static const int MAX_XOR_OFFSET_SEARCH
= 10;
212 while (next
< writer
.selected_nr
) {
213 struct bitmapped_commit
*stored
= &writer
.selected
[next
];
216 struct ewah_bitmap
*best_bitmap
= stored
->bitmap
;
217 struct ewah_bitmap
*test_xor
;
219 for (i
= 1; i
<= MAX_XOR_OFFSET_SEARCH
; ++i
) {
225 test_xor
= ewah_pool_new();
226 ewah_xor(writer
.selected
[curr
].bitmap
, stored
->bitmap
, test_xor
);
228 if (test_xor
->buffer_size
< best_bitmap
->buffer_size
) {
229 if (best_bitmap
!= stored
->bitmap
)
230 ewah_pool_free(best_bitmap
);
232 best_bitmap
= test_xor
;
235 ewah_pool_free(test_xor
);
239 stored
->xor_offset
= best_offset
;
240 stored
->write_as
= best_bitmap
;
246 void bitmap_writer_build(struct packing_data
*to_pack
)
248 static const double REUSE_BITMAP_THRESHOLD
= 0.2;
250 int i
, reuse_after
, need_reset
;
251 struct bitmap
*base
= bitmap_new();
252 struct rev_info revs
;
254 writer
.bitmaps
= kh_init_sha1();
255 writer
.to_pack
= to_pack
;
257 if (writer
.show_progress
)
258 writer
.progress
= start_progress("Building bitmaps", writer
.selected_nr
);
260 init_revisions(&revs
, NULL
);
261 revs
.tag_objects
= 1;
262 revs
.tree_objects
= 1;
263 revs
.blob_objects
= 1;
266 revs
.include_check
= should_include
;
267 reset_revision_walk();
269 reuse_after
= writer
.selected_nr
* REUSE_BITMAP_THRESHOLD
;
272 for (i
= writer
.selected_nr
- 1; i
>= 0; --i
) {
273 struct bitmapped_commit
*stored
;
274 struct object
*object
;
279 stored
= &writer
.selected
[i
];
280 object
= (struct object
*)stored
->commit
;
282 if (stored
->bitmap
== NULL
) {
283 if (i
< writer
.selected_nr
- 1 &&
285 !in_merge_bases(writer
.selected
[i
+ 1].commit
,
291 add_pending_object(&revs
, object
, "");
292 revs
.include_check_data
= base
;
294 if (prepare_revision_walk(&revs
))
295 die("revision walk setup failed");
297 traverse_commit_list(&revs
, show_commit
, show_object
, base
);
300 revs
.pending
.alloc
= 0;
301 revs
.pending
.objects
= NULL
;
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
->sha1
, &hash_ret
);
313 die("Duplicate entry when writing index: %s",
314 sha1_to_hex(object
->sha1
));
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
, sizeof(indexed_commits
[0]),
392 if (writer
.show_progress
)
393 writer
.progress
= start_progress("Selecting bitmap commits", 0);
395 if (indexed_commits_nr
< 100) {
396 for (i
= 0; i
< indexed_commits_nr
; ++i
)
397 push_bitmapped_commit(indexed_commits
[i
], NULL
);
402 struct ewah_bitmap
*reused_bitmap
= NULL
;
403 struct commit
*chosen
= NULL
;
405 next
= next_commit_index(i
);
407 if (i
+ next
>= indexed_commits_nr
)
410 if (max_bitmaps
> 0 && writer
.selected_nr
>= max_bitmaps
) {
411 writer
.selected_nr
= max_bitmaps
;
416 chosen
= indexed_commits
[i
];
417 reused_bitmap
= find_reused_bitmap(chosen
->object
.sha1
);
419 chosen
= indexed_commits
[i
+ next
];
421 for (j
= 0; j
<= next
; ++j
) {
422 struct commit
*cm
= indexed_commits
[i
+ j
];
424 reused_bitmap
= find_reused_bitmap(cm
->object
.sha1
);
425 if (reused_bitmap
|| (cm
->object
.flags
& NEEDS_BITMAP
) != 0) {
430 if (cm
->parents
&& cm
->parents
->next
)
435 push_bitmapped_commit(chosen
, reused_bitmap
);
438 display_progress(writer
.progress
, i
);
441 stop_progress(&writer
.progress
);
445 static int sha1write_ewah_helper(void *f
, const void *buf
, size_t len
)
447 /* sha1write will die on error */
448 sha1write(f
, buf
, len
);
453 * Write the bitmap index to disk
455 static inline void dump_bitmap(struct sha1file
*f
, struct ewah_bitmap
*bitmap
)
457 if (ewah_serialize_to(bitmap
, sha1write_ewah_helper
, f
) < 0)
458 die("Failed to write bitmap index");
461 static const unsigned char *sha1_access(size_t pos
, void *table
)
463 struct pack_idx_entry
**index
= table
;
464 return index
[pos
]->sha1
;
467 static void write_selected_commits_v1(struct sha1file
*f
,
468 struct pack_idx_entry
**index
,
473 for (i
= 0; i
< writer
.selected_nr
; ++i
) {
474 struct bitmapped_commit
*stored
= &writer
.selected
[i
];
477 sha1_pos(stored
->commit
->object
.sha1
, index
, index_nr
, sha1_access
);
480 die("BUG: trying to write commit not in index");
482 sha1write_be32(f
, commit_pos
);
483 sha1write_u8(f
, stored
->xor_offset
);
484 sha1write_u8(f
, stored
->flags
);
486 dump_bitmap(f
, stored
->write_as
);
490 static void write_hash_cache(struct sha1file
*f
,
491 struct pack_idx_entry
**index
,
496 for (i
= 0; i
< index_nr
; ++i
) {
497 struct object_entry
*entry
= (struct object_entry
*)index
[i
];
498 uint32_t hash_value
= htonl(entry
->hash
);
499 sha1write(f
, &hash_value
, sizeof(hash_value
));
503 void bitmap_writer_set_checksum(unsigned char *sha1
)
505 hashcpy(writer
.pack_checksum
, sha1
);
508 void bitmap_writer_finish(struct pack_idx_entry
**index
,
510 const char *filename
,
513 static char tmp_file
[PATH_MAX
];
514 static uint16_t default_version
= 1;
515 static uint16_t flags
= BITMAP_OPT_FULL_DAG
;
518 struct bitmap_disk_header header
;
520 int fd
= odb_mkstemp(tmp_file
, sizeof(tmp_file
), "pack/tmp_bitmap_XXXXXX");
523 die_errno("unable to create '%s'", tmp_file
);
524 f
= sha1fd(fd
, tmp_file
);
526 memcpy(header
.magic
, BITMAP_IDX_SIGNATURE
, sizeof(BITMAP_IDX_SIGNATURE
));
527 header
.version
= htons(default_version
);
528 header
.options
= htons(flags
| options
);
529 header
.entry_count
= htonl(writer
.selected_nr
);
530 hashcpy(header
.checksum
, writer
.pack_checksum
);
532 sha1write(f
, &header
, sizeof(header
));
533 dump_bitmap(f
, writer
.commits
);
534 dump_bitmap(f
, writer
.trees
);
535 dump_bitmap(f
, writer
.blobs
);
536 dump_bitmap(f
, writer
.tags
);
537 write_selected_commits_v1(f
, index
, index_nr
);
539 if (options
& BITMAP_OPT_HASH_CACHE
)
540 write_hash_cache(f
, index
, index_nr
);
542 sha1close(f
, NULL
, CSUM_FSYNC
);
544 if (adjust_shared_perm(tmp_file
))
545 die_errno("unable to make temporary bitmap file readable");
547 if (rename(tmp_file
, filename
))
548 die_errno("unable to rename temporary bitmap file to '%s'", filename
);