]>
Commit | Line | Data |
---|---|---|
7cc8f971 | 1 | #include "cache.h" |
cbd53a21 | 2 | #include "object-store.h" |
7cc8f971 VM |
3 | #include "commit.h" |
4 | #include "tag.h" | |
5 | #include "diff.h" | |
6 | #include "revision.h" | |
7 | #include "list-objects.h" | |
8 | #include "progress.h" | |
9 | #include "pack-revindex.h" | |
10 | #include "pack.h" | |
11 | #include "pack-bitmap.h" | |
12 | #include "sha1-lookup.h" | |
13 | #include "pack-objects.h" | |
64043556 | 14 | #include "commit-reach.h" |
7cc8f971 VM |
15 | |
16 | struct bitmapped_commit { | |
17 | struct commit *commit; | |
18 | struct ewah_bitmap *bitmap; | |
19 | struct ewah_bitmap *write_as; | |
20 | int flags; | |
21 | int xor_offset; | |
22 | uint32_t commit_pos; | |
23 | }; | |
24 | ||
25 | struct bitmap_writer { | |
26 | struct ewah_bitmap *commits; | |
27 | struct ewah_bitmap *trees; | |
28 | struct ewah_bitmap *blobs; | |
29 | struct ewah_bitmap *tags; | |
30 | ||
31 | khash_sha1 *bitmaps; | |
32 | khash_sha1 *reused; | |
33 | struct packing_data *to_pack; | |
34 | ||
35 | struct bitmapped_commit *selected; | |
36 | unsigned int selected_nr, selected_alloc; | |
37 | ||
38 | struct progress *progress; | |
39 | int show_progress; | |
825544a3 | 40 | unsigned char pack_checksum[GIT_MAX_RAWSZ]; |
7cc8f971 VM |
41 | }; |
42 | ||
43 | static struct bitmap_writer writer; | |
44 | ||
45 | void bitmap_writer_show_progress(int show) | |
46 | { | |
47 | writer.show_progress = show; | |
48 | } | |
49 | ||
50 | /** | |
51 | * Build the initial type index for the packfile | |
52 | */ | |
06af3bba NTND |
53 | void bitmap_writer_build_type_index(struct packing_data *to_pack, |
54 | struct pack_idx_entry **index, | |
7cc8f971 VM |
55 | uint32_t index_nr) |
56 | { | |
57 | uint32_t i; | |
58 | ||
59 | writer.commits = ewah_new(); | |
60 | writer.trees = ewah_new(); | |
61 | writer.blobs = ewah_new(); | |
62 | writer.tags = ewah_new(); | |
06af3bba | 63 | ALLOC_ARRAY(to_pack->in_pack_pos, to_pack->nr_objects); |
7cc8f971 VM |
64 | |
65 | for (i = 0; i < index_nr; ++i) { | |
66 | struct object_entry *entry = (struct object_entry *)index[i]; | |
67 | enum object_type real_type; | |
68 | ||
06af3bba | 69 | oe_set_in_pack_pos(to_pack, entry, i); |
7cc8f971 | 70 | |
fd9b1bae | 71 | switch (oe_type(entry)) { |
7cc8f971 VM |
72 | case OBJ_COMMIT: |
73 | case OBJ_TREE: | |
74 | case OBJ_BLOB: | |
75 | case OBJ_TAG: | |
fd9b1bae | 76 | real_type = oe_type(entry); |
7cc8f971 VM |
77 | break; |
78 | ||
79 | default: | |
0df8e965 SB |
80 | real_type = oid_object_info(the_repository, |
81 | &entry->idx.oid, NULL); | |
7cc8f971 VM |
82 | break; |
83 | } | |
84 | ||
85 | switch (real_type) { | |
86 | case OBJ_COMMIT: | |
87 | ewah_set(writer.commits, i); | |
88 | break; | |
89 | ||
90 | case OBJ_TREE: | |
91 | ewah_set(writer.trees, i); | |
92 | break; | |
93 | ||
94 | case OBJ_BLOB: | |
95 | ewah_set(writer.blobs, i); | |
96 | break; | |
97 | ||
98 | case OBJ_TAG: | |
99 | ewah_set(writer.tags, i); | |
100 | break; | |
101 | ||
102 | default: | |
103 | die("Missing type information for %s (%d/%d)", | |
e6a492b7 | 104 | oid_to_hex(&entry->idx.oid), real_type, |
fd9b1bae | 105 | oe_type(entry)); |
7cc8f971 VM |
106 | } |
107 | } | |
108 | } | |
109 | ||
110 | /** | |
111 | * Compute the actual bitmaps | |
112 | */ | |
113 | static struct object **seen_objects; | |
114 | static unsigned int seen_objects_nr, seen_objects_alloc; | |
115 | ||
116 | static inline void push_bitmapped_commit(struct commit *commit, struct ewah_bitmap *reused) | |
117 | { | |
118 | if (writer.selected_nr >= writer.selected_alloc) { | |
119 | writer.selected_alloc = (writer.selected_alloc + 32) * 2; | |
2756ca43 | 120 | REALLOC_ARRAY(writer.selected, writer.selected_alloc); |
7cc8f971 VM |
121 | } |
122 | ||
123 | writer.selected[writer.selected_nr].commit = commit; | |
124 | writer.selected[writer.selected_nr].bitmap = reused; | |
125 | writer.selected[writer.selected_nr].flags = 0; | |
126 | ||
127 | writer.selected_nr++; | |
128 | } | |
129 | ||
130 | static inline void mark_as_seen(struct object *object) | |
131 | { | |
132 | ALLOC_GROW(seen_objects, seen_objects_nr + 1, seen_objects_alloc); | |
133 | seen_objects[seen_objects_nr++] = object; | |
134 | } | |
135 | ||
136 | static inline void reset_all_seen(void) | |
137 | { | |
138 | unsigned int i; | |
139 | for (i = 0; i < seen_objects_nr; ++i) { | |
140 | seen_objects[i]->flags &= ~(SEEN | ADDED | SHOWN); | |
141 | } | |
142 | seen_objects_nr = 0; | |
143 | } | |
144 | ||
145 | static uint32_t find_object_pos(const unsigned char *sha1) | |
146 | { | |
147 | struct object_entry *entry = packlist_find(writer.to_pack, sha1, NULL); | |
148 | ||
149 | if (!entry) { | |
150 | die("Failed to write bitmap index. Packfile doesn't have full closure " | |
151 | "(object %s is missing)", sha1_to_hex(sha1)); | |
152 | } | |
153 | ||
06af3bba | 154 | return oe_in_pack_pos(writer.to_pack, entry); |
7cc8f971 VM |
155 | } |
156 | ||
de1e67d0 | 157 | static void show_object(struct object *object, const char *name, void *data) |
7cc8f971 VM |
158 | { |
159 | struct bitmap *base = data; | |
ed1c9977 | 160 | bitmap_set(base, find_object_pos(object->oid.hash)); |
7cc8f971 VM |
161 | mark_as_seen(object); |
162 | } | |
163 | ||
164 | static void show_commit(struct commit *commit, void *data) | |
165 | { | |
166 | mark_as_seen((struct object *)commit); | |
167 | } | |
168 | ||
169 | static int | |
170 | add_to_include_set(struct bitmap *base, struct commit *commit) | |
171 | { | |
172 | khiter_t hash_pos; | |
ed1c9977 | 173 | uint32_t bitmap_pos = find_object_pos(commit->object.oid.hash); |
7cc8f971 VM |
174 | |
175 | if (bitmap_get(base, bitmap_pos)) | |
176 | return 0; | |
177 | ||
ed1c9977 | 178 | hash_pos = kh_get_sha1(writer.bitmaps, commit->object.oid.hash); |
7cc8f971 VM |
179 | if (hash_pos < kh_end(writer.bitmaps)) { |
180 | struct bitmapped_commit *bc = kh_value(writer.bitmaps, hash_pos); | |
181 | bitmap_or_ewah(base, bc->bitmap); | |
182 | return 0; | |
183 | } | |
184 | ||
185 | bitmap_set(base, bitmap_pos); | |
186 | return 1; | |
187 | } | |
188 | ||
189 | static int | |
190 | should_include(struct commit *commit, void *_data) | |
191 | { | |
192 | struct bitmap *base = _data; | |
193 | ||
194 | if (!add_to_include_set(base, commit)) { | |
195 | struct commit_list *parent = commit->parents; | |
196 | ||
197 | mark_as_seen((struct object *)commit); | |
198 | ||
199 | while (parent) { | |
200 | parent->item->object.flags |= SEEN; | |
201 | mark_as_seen((struct object *)parent->item); | |
202 | parent = parent->next; | |
203 | } | |
204 | ||
205 | return 0; | |
206 | } | |
207 | ||
208 | return 1; | |
209 | } | |
210 | ||
211 | static void compute_xor_offsets(void) | |
212 | { | |
213 | static const int MAX_XOR_OFFSET_SEARCH = 10; | |
214 | ||
215 | int i, next = 0; | |
216 | ||
217 | while (next < writer.selected_nr) { | |
218 | struct bitmapped_commit *stored = &writer.selected[next]; | |
219 | ||
220 | int best_offset = 0; | |
221 | struct ewah_bitmap *best_bitmap = stored->bitmap; | |
222 | struct ewah_bitmap *test_xor; | |
223 | ||
224 | for (i = 1; i <= MAX_XOR_OFFSET_SEARCH; ++i) { | |
225 | int curr = next - i; | |
226 | ||
227 | if (curr < 0) | |
228 | break; | |
229 | ||
230 | test_xor = ewah_pool_new(); | |
231 | ewah_xor(writer.selected[curr].bitmap, stored->bitmap, test_xor); | |
232 | ||
233 | if (test_xor->buffer_size < best_bitmap->buffer_size) { | |
234 | if (best_bitmap != stored->bitmap) | |
235 | ewah_pool_free(best_bitmap); | |
236 | ||
237 | best_bitmap = test_xor; | |
238 | best_offset = i; | |
239 | } else { | |
240 | ewah_pool_free(test_xor); | |
241 | } | |
242 | } | |
243 | ||
244 | stored->xor_offset = best_offset; | |
245 | stored->write_as = best_bitmap; | |
246 | ||
247 | next++; | |
248 | } | |
249 | } | |
250 | ||
251 | void bitmap_writer_build(struct packing_data *to_pack) | |
252 | { | |
253 | static const double REUSE_BITMAP_THRESHOLD = 0.2; | |
254 | ||
255 | int i, reuse_after, need_reset; | |
256 | struct bitmap *base = bitmap_new(); | |
257 | struct rev_info revs; | |
258 | ||
259 | writer.bitmaps = kh_init_sha1(); | |
260 | writer.to_pack = to_pack; | |
261 | ||
262 | if (writer.show_progress) | |
263 | writer.progress = start_progress("Building bitmaps", writer.selected_nr); | |
264 | ||
2abf3503 | 265 | repo_init_revisions(the_repository, &revs, NULL); |
7cc8f971 VM |
266 | revs.tag_objects = 1; |
267 | revs.tree_objects = 1; | |
268 | revs.blob_objects = 1; | |
269 | revs.no_walk = 0; | |
270 | ||
271 | revs.include_check = should_include; | |
272 | reset_revision_walk(); | |
273 | ||
274 | reuse_after = writer.selected_nr * REUSE_BITMAP_THRESHOLD; | |
275 | need_reset = 0; | |
276 | ||
277 | for (i = writer.selected_nr - 1; i >= 0; --i) { | |
278 | struct bitmapped_commit *stored; | |
279 | struct object *object; | |
280 | ||
281 | khiter_t hash_pos; | |
282 | int hash_ret; | |
283 | ||
284 | stored = &writer.selected[i]; | |
285 | object = (struct object *)stored->commit; | |
286 | ||
287 | if (stored->bitmap == NULL) { | |
288 | if (i < writer.selected_nr - 1 && | |
289 | (need_reset || | |
290 | !in_merge_bases(writer.selected[i + 1].commit, | |
291 | stored->commit))) { | |
292 | bitmap_reset(base); | |
293 | reset_all_seen(); | |
294 | } | |
295 | ||
296 | add_pending_object(&revs, object, ""); | |
297 | revs.include_check_data = base; | |
298 | ||
299 | if (prepare_revision_walk(&revs)) | |
300 | die("revision walk setup failed"); | |
301 | ||
302 | traverse_commit_list(&revs, show_commit, show_object, base); | |
303 | ||
4d01a7fa | 304 | object_array_clear(&revs.pending); |
7cc8f971 VM |
305 | |
306 | stored->bitmap = bitmap_to_ewah(base); | |
307 | need_reset = 0; | |
308 | } else | |
309 | need_reset = 1; | |
310 | ||
311 | if (i >= reuse_after) | |
312 | stored->flags |= BITMAP_FLAG_REUSE; | |
313 | ||
ed1c9977 | 314 | hash_pos = kh_put_sha1(writer.bitmaps, object->oid.hash, &hash_ret); |
7cc8f971 VM |
315 | if (hash_ret == 0) |
316 | die("Duplicate entry when writing index: %s", | |
f2fd0760 | 317 | oid_to_hex(&object->oid)); |
7cc8f971 VM |
318 | |
319 | kh_value(writer.bitmaps, hash_pos) = stored; | |
320 | display_progress(writer.progress, writer.selected_nr - i); | |
321 | } | |
322 | ||
323 | bitmap_free(base); | |
324 | stop_progress(&writer.progress); | |
325 | ||
326 | compute_xor_offsets(); | |
327 | } | |
328 | ||
329 | /** | |
330 | * Select the commits that will be bitmapped | |
331 | */ | |
332 | static inline unsigned int next_commit_index(unsigned int idx) | |
333 | { | |
334 | static const unsigned int MIN_COMMITS = 100; | |
335 | static const unsigned int MAX_COMMITS = 5000; | |
336 | ||
337 | static const unsigned int MUST_REGION = 100; | |
338 | static const unsigned int MIN_REGION = 20000; | |
339 | ||
340 | unsigned int offset, next; | |
341 | ||
342 | if (idx <= MUST_REGION) | |
343 | return 0; | |
344 | ||
345 | if (idx <= MIN_REGION) { | |
346 | offset = idx - MUST_REGION; | |
347 | return (offset < MIN_COMMITS) ? offset : MIN_COMMITS; | |
348 | } | |
349 | ||
350 | offset = idx - MIN_REGION; | |
351 | next = (offset < MAX_COMMITS) ? offset : MAX_COMMITS; | |
352 | ||
353 | return (next > MIN_COMMITS) ? next : MIN_COMMITS; | |
354 | } | |
355 | ||
356 | static int date_compare(const void *_a, const void *_b) | |
357 | { | |
358 | struct commit *a = *(struct commit **)_a; | |
359 | struct commit *b = *(struct commit **)_b; | |
360 | return (long)b->date - (long)a->date; | |
361 | } | |
362 | ||
363 | void bitmap_writer_reuse_bitmaps(struct packing_data *to_pack) | |
364 | { | |
3ae5fa07 JT |
365 | struct bitmap_index *bitmap_git; |
366 | if (!(bitmap_git = prepare_bitmap_git())) | |
7cc8f971 VM |
367 | return; |
368 | ||
369 | writer.reused = kh_init_sha1(); | |
3ae5fa07 JT |
370 | rebuild_existing_bitmaps(bitmap_git, to_pack, writer.reused, |
371 | writer.show_progress); | |
f3c23db2 JT |
372 | /* |
373 | * NEEDSWORK: rebuild_existing_bitmaps() makes writer.reused reference | |
374 | * some bitmaps in bitmap_git, so we can't free the latter. | |
375 | */ | |
7cc8f971 VM |
376 | } |
377 | ||
378 | static struct ewah_bitmap *find_reused_bitmap(const unsigned char *sha1) | |
379 | { | |
380 | khiter_t hash_pos; | |
381 | ||
382 | if (!writer.reused) | |
383 | return NULL; | |
384 | ||
385 | hash_pos = kh_get_sha1(writer.reused, sha1); | |
386 | if (hash_pos >= kh_end(writer.reused)) | |
387 | return NULL; | |
388 | ||
389 | return kh_value(writer.reused, hash_pos); | |
390 | } | |
391 | ||
392 | void bitmap_writer_select_commits(struct commit **indexed_commits, | |
393 | unsigned int indexed_commits_nr, | |
394 | int max_bitmaps) | |
395 | { | |
396 | unsigned int i = 0, j, next; | |
397 | ||
9ed0d8d6 | 398 | QSORT(indexed_commits, indexed_commits_nr, date_compare); |
7cc8f971 VM |
399 | |
400 | if (writer.show_progress) | |
401 | writer.progress = start_progress("Selecting bitmap commits", 0); | |
402 | ||
403 | if (indexed_commits_nr < 100) { | |
404 | for (i = 0; i < indexed_commits_nr; ++i) | |
405 | push_bitmapped_commit(indexed_commits[i], NULL); | |
406 | return; | |
407 | } | |
408 | ||
409 | for (;;) { | |
410 | struct ewah_bitmap *reused_bitmap = NULL; | |
411 | struct commit *chosen = NULL; | |
412 | ||
413 | next = next_commit_index(i); | |
414 | ||
415 | if (i + next >= indexed_commits_nr) | |
416 | break; | |
417 | ||
418 | if (max_bitmaps > 0 && writer.selected_nr >= max_bitmaps) { | |
419 | writer.selected_nr = max_bitmaps; | |
420 | break; | |
421 | } | |
422 | ||
423 | if (next == 0) { | |
424 | chosen = indexed_commits[i]; | |
ed1c9977 | 425 | reused_bitmap = find_reused_bitmap(chosen->object.oid.hash); |
7cc8f971 VM |
426 | } else { |
427 | chosen = indexed_commits[i + next]; | |
428 | ||
429 | for (j = 0; j <= next; ++j) { | |
430 | struct commit *cm = indexed_commits[i + j]; | |
431 | ||
ed1c9977 | 432 | reused_bitmap = find_reused_bitmap(cm->object.oid.hash); |
7cc8f971 VM |
433 | if (reused_bitmap || (cm->object.flags & NEEDS_BITMAP) != 0) { |
434 | chosen = cm; | |
435 | break; | |
436 | } | |
437 | ||
438 | if (cm->parents && cm->parents->next) | |
439 | chosen = cm; | |
440 | } | |
441 | } | |
442 | ||
443 | push_bitmapped_commit(chosen, reused_bitmap); | |
444 | ||
445 | i += next + 1; | |
446 | display_progress(writer.progress, i); | |
447 | } | |
448 | ||
449 | stop_progress(&writer.progress); | |
450 | } | |
451 | ||
452 | ||
98a3beab | 453 | static int hashwrite_ewah_helper(void *f, const void *buf, size_t len) |
7cc8f971 | 454 | { |
98a3beab | 455 | /* hashwrite will die on error */ |
456 | hashwrite(f, buf, len); | |
7cc8f971 VM |
457 | return len; |
458 | } | |
459 | ||
460 | /** | |
461 | * Write the bitmap index to disk | |
462 | */ | |
98a3beab | 463 | static inline void dump_bitmap(struct hashfile *f, struct ewah_bitmap *bitmap) |
7cc8f971 | 464 | { |
98a3beab | 465 | if (ewah_serialize_to(bitmap, hashwrite_ewah_helper, f) < 0) |
7cc8f971 VM |
466 | die("Failed to write bitmap index"); |
467 | } | |
468 | ||
469 | static const unsigned char *sha1_access(size_t pos, void *table) | |
470 | { | |
471 | struct pack_idx_entry **index = table; | |
e6a492b7 | 472 | return index[pos]->oid.hash; |
7cc8f971 VM |
473 | } |
474 | ||
98a3beab | 475 | static void write_selected_commits_v1(struct hashfile *f, |
7cc8f971 VM |
476 | struct pack_idx_entry **index, |
477 | uint32_t index_nr) | |
478 | { | |
479 | int i; | |
480 | ||
481 | for (i = 0; i < writer.selected_nr; ++i) { | |
482 | struct bitmapped_commit *stored = &writer.selected[i]; | |
7cc8f971 VM |
483 | |
484 | int commit_pos = | |
ed1c9977 | 485 | sha1_pos(stored->commit->object.oid.hash, index, index_nr, sha1_access); |
7cc8f971 VM |
486 | |
487 | if (commit_pos < 0) | |
033abf97 | 488 | BUG("trying to write commit not in index"); |
7cc8f971 | 489 | |
98a3beab | 490 | hashwrite_be32(f, commit_pos); |
491 | hashwrite_u8(f, stored->xor_offset); | |
492 | hashwrite_u8(f, stored->flags); | |
7cc8f971 | 493 | |
7cc8f971 VM |
494 | dump_bitmap(f, stored->write_as); |
495 | } | |
496 | } | |
497 | ||
98a3beab | 498 | static void write_hash_cache(struct hashfile *f, |
ae4f07fb VM |
499 | struct pack_idx_entry **index, |
500 | uint32_t index_nr) | |
501 | { | |
502 | uint32_t i; | |
503 | ||
504 | for (i = 0; i < index_nr; ++i) { | |
505 | struct object_entry *entry = (struct object_entry *)index[i]; | |
506 | uint32_t hash_value = htonl(entry->hash); | |
98a3beab | 507 | hashwrite(f, &hash_value, sizeof(hash_value)); |
ae4f07fb VM |
508 | } |
509 | } | |
510 | ||
7cc8f971 VM |
511 | void bitmap_writer_set_checksum(unsigned char *sha1) |
512 | { | |
513 | hashcpy(writer.pack_checksum, sha1); | |
514 | } | |
515 | ||
516 | void bitmap_writer_finish(struct pack_idx_entry **index, | |
517 | uint32_t index_nr, | |
ae4f07fb VM |
518 | const char *filename, |
519 | uint16_t options) | |
7cc8f971 | 520 | { |
7cc8f971 VM |
521 | static uint16_t default_version = 1; |
522 | static uint16_t flags = BITMAP_OPT_FULL_DAG; | |
594fa999 | 523 | struct strbuf tmp_file = STRBUF_INIT; |
98a3beab | 524 | struct hashfile *f; |
7cc8f971 VM |
525 | |
526 | struct bitmap_disk_header header; | |
527 | ||
594fa999 | 528 | int fd = odb_mkstemp(&tmp_file, "pack/tmp_bitmap_XXXXXX"); |
7cc8f971 | 529 | |
98a3beab | 530 | f = hashfd(fd, tmp_file.buf); |
7cc8f971 VM |
531 | |
532 | memcpy(header.magic, BITMAP_IDX_SIGNATURE, sizeof(BITMAP_IDX_SIGNATURE)); | |
533 | header.version = htons(default_version); | |
ae4f07fb | 534 | header.options = htons(flags | options); |
7cc8f971 | 535 | header.entry_count = htonl(writer.selected_nr); |
50546b15 | 536 | hashcpy(header.checksum, writer.pack_checksum); |
7cc8f971 | 537 | |
98a3beab | 538 | hashwrite(f, &header, sizeof(header)); |
7cc8f971 VM |
539 | dump_bitmap(f, writer.commits); |
540 | dump_bitmap(f, writer.trees); | |
541 | dump_bitmap(f, writer.blobs); | |
542 | dump_bitmap(f, writer.tags); | |
543 | write_selected_commits_v1(f, index, index_nr); | |
544 | ||
ae4f07fb VM |
545 | if (options & BITMAP_OPT_HASH_CACHE) |
546 | write_hash_cache(f, index, index_nr); | |
547 | ||
cfe83216 | 548 | finalize_hashfile(f, NULL, CSUM_HASH_IN_STREAM | CSUM_FSYNC | CSUM_CLOSE); |
7cc8f971 | 549 | |
594fa999 | 550 | if (adjust_shared_perm(tmp_file.buf)) |
7cc8f971 VM |
551 | die_errno("unable to make temporary bitmap file readable"); |
552 | ||
594fa999 | 553 | if (rename(tmp_file.buf, filename)) |
7cc8f971 | 554 | die_errno("unable to rename temporary bitmap file to '%s'", filename); |
594fa999 JK |
555 | |
556 | strbuf_release(&tmp_file); | |
7cc8f971 | 557 | } |