]>
Commit | Line | Data |
---|---|---|
d812c3b6 | 1 | #include "git-compat-util.h" |
32a8f510 | 2 | #include "environment.h" |
f394e093 | 3 | #include "gettext.h" |
41771fa4 | 4 | #include "hex.h" |
a034e910 | 5 | #include "object-store-ll.h" |
7cc8f971 VM |
6 | #include "commit.h" |
7 | #include "tag.h" | |
8 | #include "diff.h" | |
9 | #include "revision.h" | |
10 | #include "list-objects.h" | |
11 | #include "progress.h" | |
12 | #include "pack-revindex.h" | |
13 | #include "pack.h" | |
14 | #include "pack-bitmap.h" | |
bc626927 | 15 | #include "hash-lookup.h" |
7cc8f971 | 16 | #include "pack-objects.h" |
c339932b | 17 | #include "path.h" |
64043556 | 18 | #include "commit-reach.h" |
6dc5ef75 | 19 | #include "prio-queue.h" |
ec2f0269 | 20 | #include "trace2.h" |
d4a4f929 | 21 | #include "tree.h" |
0e312eaa | 22 | #include "tree-walk.h" |
7cc8f971 VM |
23 | |
24 | struct bitmapped_commit { | |
25 | struct commit *commit; | |
26 | struct ewah_bitmap *bitmap; | |
27 | struct ewah_bitmap *write_as; | |
28 | int flags; | |
29 | int xor_offset; | |
30 | uint32_t commit_pos; | |
31 | }; | |
32 | ||
33 | struct bitmap_writer { | |
34 | struct ewah_bitmap *commits; | |
35 | struct ewah_bitmap *trees; | |
36 | struct ewah_bitmap *blobs; | |
37 | struct ewah_bitmap *tags; | |
38 | ||
d2bc62b1 | 39 | kh_oid_map_t *bitmaps; |
7cc8f971 VM |
40 | struct packing_data *to_pack; |
41 | ||
42 | struct bitmapped_commit *selected; | |
43 | unsigned int selected_nr, selected_alloc; | |
44 | ||
45 | struct progress *progress; | |
46 | int show_progress; | |
825544a3 | 47 | unsigned char pack_checksum[GIT_MAX_RAWSZ]; |
7cc8f971 VM |
48 | }; |
49 | ||
50 | static struct bitmap_writer writer; | |
51 | ||
52 | void bitmap_writer_show_progress(int show) | |
53 | { | |
54 | writer.show_progress = show; | |
55 | } | |
56 | ||
57 | /** | |
0f533c72 | 58 | * Build the initial type index for the packfile or multi-pack-index |
7cc8f971 | 59 | */ |
06af3bba NTND |
60 | void bitmap_writer_build_type_index(struct packing_data *to_pack, |
61 | struct pack_idx_entry **index, | |
7cc8f971 VM |
62 | uint32_t index_nr) |
63 | { | |
64 | uint32_t i; | |
65 | ||
66 | writer.commits = ewah_new(); | |
67 | writer.trees = ewah_new(); | |
68 | writer.blobs = ewah_new(); | |
69 | writer.tags = ewah_new(); | |
06af3bba | 70 | ALLOC_ARRAY(to_pack->in_pack_pos, to_pack->nr_objects); |
7cc8f971 VM |
71 | |
72 | for (i = 0; i < index_nr; ++i) { | |
73 | struct object_entry *entry = (struct object_entry *)index[i]; | |
74 | enum object_type real_type; | |
75 | ||
06af3bba | 76 | oe_set_in_pack_pos(to_pack, entry, i); |
7cc8f971 | 77 | |
fd9b1bae | 78 | switch (oe_type(entry)) { |
7cc8f971 VM |
79 | case OBJ_COMMIT: |
80 | case OBJ_TREE: | |
81 | case OBJ_BLOB: | |
82 | case OBJ_TAG: | |
fd9b1bae | 83 | real_type = oe_type(entry); |
7cc8f971 VM |
84 | break; |
85 | ||
86 | default: | |
7c141127 | 87 | real_type = oid_object_info(to_pack->repo, |
0df8e965 | 88 | &entry->idx.oid, NULL); |
7cc8f971 VM |
89 | break; |
90 | } | |
91 | ||
92 | switch (real_type) { | |
93 | case OBJ_COMMIT: | |
94 | ewah_set(writer.commits, i); | |
95 | break; | |
96 | ||
97 | case OBJ_TREE: | |
98 | ewah_set(writer.trees, i); | |
99 | break; | |
100 | ||
101 | case OBJ_BLOB: | |
102 | ewah_set(writer.blobs, i); | |
103 | break; | |
104 | ||
105 | case OBJ_TAG: | |
106 | ewah_set(writer.tags, i); | |
107 | break; | |
108 | ||
109 | default: | |
110 | die("Missing type information for %s (%d/%d)", | |
e6a492b7 | 111 | oid_to_hex(&entry->idx.oid), real_type, |
fd9b1bae | 112 | oe_type(entry)); |
7cc8f971 VM |
113 | } |
114 | } | |
115 | } | |
116 | ||
117 | /** | |
118 | * Compute the actual bitmaps | |
119 | */ | |
7cc8f971 | 120 | |
449fa5ee | 121 | static inline void push_bitmapped_commit(struct commit *commit) |
7cc8f971 VM |
122 | { |
123 | if (writer.selected_nr >= writer.selected_alloc) { | |
124 | writer.selected_alloc = (writer.selected_alloc + 32) * 2; | |
2756ca43 | 125 | REALLOC_ARRAY(writer.selected, writer.selected_alloc); |
7cc8f971 VM |
126 | } |
127 | ||
128 | writer.selected[writer.selected_nr].commit = commit; | |
449fa5ee | 129 | writer.selected[writer.selected_nr].bitmap = NULL; |
7cc8f971 VM |
130 | writer.selected[writer.selected_nr].flags = 0; |
131 | ||
132 | writer.selected_nr++; | |
133 | } | |
134 | ||
3ba3d062 | 135 | static uint32_t find_object_pos(const struct object_id *oid, int *found) |
7cc8f971 | 136 | { |
3a37876b | 137 | struct object_entry *entry = packlist_find(writer.to_pack, oid); |
7cc8f971 VM |
138 | |
139 | if (!entry) { | |
3ba3d062 TB |
140 | if (found) |
141 | *found = 0; | |
142 | warning("Failed to write bitmap index. Packfile doesn't have full closure " | |
05805d74 | 143 | "(object %s is missing)", oid_to_hex(oid)); |
3ba3d062 | 144 | return 0; |
7cc8f971 VM |
145 | } |
146 | ||
3ba3d062 TB |
147 | if (found) |
148 | *found = 1; | |
06af3bba | 149 | return oe_in_pack_pos(writer.to_pack, entry); |
7cc8f971 VM |
150 | } |
151 | ||
7cc8f971 VM |
152 | static void compute_xor_offsets(void) |
153 | { | |
154 | static const int MAX_XOR_OFFSET_SEARCH = 10; | |
155 | ||
156 | int i, next = 0; | |
157 | ||
158 | while (next < writer.selected_nr) { | |
159 | struct bitmapped_commit *stored = &writer.selected[next]; | |
160 | ||
161 | int best_offset = 0; | |
162 | struct ewah_bitmap *best_bitmap = stored->bitmap; | |
163 | struct ewah_bitmap *test_xor; | |
164 | ||
165 | for (i = 1; i <= MAX_XOR_OFFSET_SEARCH; ++i) { | |
166 | int curr = next - i; | |
167 | ||
168 | if (curr < 0) | |
169 | break; | |
170 | ||
171 | test_xor = ewah_pool_new(); | |
172 | ewah_xor(writer.selected[curr].bitmap, stored->bitmap, test_xor); | |
173 | ||
174 | if (test_xor->buffer_size < best_bitmap->buffer_size) { | |
175 | if (best_bitmap != stored->bitmap) | |
176 | ewah_pool_free(best_bitmap); | |
177 | ||
178 | best_bitmap = test_xor; | |
179 | best_offset = i; | |
180 | } else { | |
181 | ewah_pool_free(test_xor); | |
182 | } | |
183 | } | |
184 | ||
185 | stored->xor_offset = best_offset; | |
186 | stored->write_as = best_bitmap; | |
187 | ||
188 | next++; | |
189 | } | |
190 | } | |
191 | ||
4a9c5817 | 192 | struct bb_commit { |
928e3f42 | 193 | struct commit_list *reverse_edges; |
089f7513 | 194 | struct bitmap *commit_mask; |
4a9c5817 | 195 | struct bitmap *bitmap; |
089f7513 DS |
196 | unsigned selected:1, |
197 | maximal:1; | |
4a9c5817 JK |
198 | unsigned idx; /* within selected array */ |
199 | }; | |
7cc8f971 | 200 | |
4a9c5817 | 201 | define_commit_slab(bb_data, struct bb_commit); |
7cc8f971 | 202 | |
4a9c5817 JK |
203 | struct bitmap_builder { |
204 | struct bb_data data; | |
205 | struct commit **commits; | |
206 | size_t commits_nr, commits_alloc; | |
207 | }; | |
7cc8f971 | 208 | |
4a9c5817 | 209 | static void bitmap_builder_init(struct bitmap_builder *bb, |
f077b0a9 DS |
210 | struct bitmap_writer *writer, |
211 | struct bitmap_index *old_bitmap) | |
4a9c5817 JK |
212 | { |
213 | struct rev_info revs; | |
214 | struct commit *commit; | |
f077b0a9 DS |
215 | struct commit_list *reusable = NULL; |
216 | struct commit_list *r; | |
45f4eeb2 | 217 | unsigned int i, num_maximal = 0; |
7cc8f971 | 218 | |
4a9c5817 JK |
219 | memset(bb, 0, sizeof(*bb)); |
220 | init_bb_data(&bb->data); | |
7cc8f971 | 221 | |
7cc8f971 | 222 | reset_revision_walk(); |
4a9c5817 JK |
223 | repo_init_revisions(writer->to_pack->repo, &revs, NULL); |
224 | revs.topo_order = 1; | |
45f4eeb2 | 225 | revs.first_parent_only = 1; |
4a9c5817 JK |
226 | |
227 | for (i = 0; i < writer->selected_nr; i++) { | |
228 | struct commit *c = writer->selected[i].commit; | |
229 | struct bb_commit *ent = bb_data_at(&bb->data, c); | |
089f7513 | 230 | |
4a9c5817 | 231 | ent->selected = 1; |
089f7513 | 232 | ent->maximal = 1; |
4a9c5817 | 233 | ent->idx = i; |
089f7513 DS |
234 | |
235 | ent->commit_mask = bitmap_new(); | |
236 | bitmap_set(ent->commit_mask, i); | |
237 | ||
4a9c5817 JK |
238 | add_pending_object(&revs, &c->object, ""); |
239 | } | |
7cc8f971 | 240 | |
4a9c5817 JK |
241 | if (prepare_revision_walk(&revs)) |
242 | die("revision walk setup failed"); | |
7cc8f971 | 243 | |
4a9c5817 | 244 | while ((commit = get_revision(&revs))) { |
45f4eeb2 | 245 | struct commit_list *p = commit->parents; |
089f7513 | 246 | struct bb_commit *c_ent; |
7cc8f971 | 247 | |
4a9c5817 | 248 | parse_commit_or_die(commit); |
7cc8f971 | 249 | |
089f7513 DS |
250 | c_ent = bb_data_at(&bb->data, commit); |
251 | ||
f077b0a9 DS |
252 | /* |
253 | * If there is no commit_mask, there is no reason to iterate | |
254 | * over this commit; it is not selected (if it were, it would | |
255 | * not have a blank commit mask) and all its children have | |
256 | * existing bitmaps (see the comment starting with "This commit | |
257 | * has an existing bitmap" below), so it does not contribute | |
258 | * anything to the final bitmap file or its descendants. | |
259 | */ | |
260 | if (!c_ent->commit_mask) | |
261 | continue; | |
262 | ||
263 | if (old_bitmap && bitmap_for_commit(old_bitmap, commit)) { | |
264 | /* | |
265 | * This commit has an existing bitmap, so we can | |
266 | * get its bits immediately without an object | |
267 | * walk. That is, it is reusable as-is and there is no | |
268 | * need to continue walking beyond it. | |
269 | * | |
270 | * Mark it as such and add it to bb->commits separately | |
271 | * to avoid allocating a position in the commit mask. | |
272 | */ | |
273 | commit_list_insert(commit, &reusable); | |
274 | goto next; | |
275 | } | |
276 | ||
089f7513 | 277 | if (c_ent->maximal) { |
45f4eeb2 | 278 | num_maximal++; |
089f7513 DS |
279 | ALLOC_GROW(bb->commits, bb->commits_nr + 1, bb->commits_alloc); |
280 | bb->commits[bb->commits_nr++] = commit; | |
281 | } | |
7cc8f971 | 282 | |
45f4eeb2 | 283 | if (p) { |
089f7513 DS |
284 | struct bb_commit *p_ent = bb_data_at(&bb->data, p->item); |
285 | int c_not_p, p_not_c; | |
286 | ||
287 | if (!p_ent->commit_mask) { | |
288 | p_ent->commit_mask = bitmap_new(); | |
289 | c_not_p = 1; | |
290 | p_not_c = 0; | |
291 | } else { | |
292 | c_not_p = bitmap_is_subset(c_ent->commit_mask, p_ent->commit_mask); | |
293 | p_not_c = bitmap_is_subset(p_ent->commit_mask, c_ent->commit_mask); | |
294 | } | |
295 | ||
296 | if (!c_not_p) | |
297 | continue; | |
298 | ||
299 | bitmap_or(p_ent->commit_mask, c_ent->commit_mask); | |
300 | ||
301 | if (p_not_c) | |
302 | p_ent->maximal = 1; | |
303 | else { | |
304 | p_ent->maximal = 0; | |
305 | free_commit_list(p_ent->reverse_edges); | |
306 | p_ent->reverse_edges = NULL; | |
307 | } | |
308 | ||
309 | if (c_ent->maximal) { | |
310 | commit_list_insert(commit, &p_ent->reverse_edges); | |
311 | } else { | |
312 | struct commit_list *cc = c_ent->reverse_edges; | |
313 | ||
314 | for (; cc; cc = cc->next) { | |
315 | if (!commit_list_contains(cc->item, p_ent->reverse_edges)) | |
316 | commit_list_insert(cc->item, &p_ent->reverse_edges); | |
317 | } | |
318 | } | |
4a9c5817 | 319 | } |
089f7513 | 320 | |
f077b0a9 | 321 | next: |
089f7513 DS |
322 | bitmap_free(c_ent->commit_mask); |
323 | c_ent->commit_mask = NULL; | |
4a9c5817 | 324 | } |
089f7513 | 325 | |
f077b0a9 DS |
326 | for (r = reusable; r; r = r->next) { |
327 | ALLOC_GROW(bb->commits, bb->commits_nr + 1, bb->commits_alloc); | |
328 | bb->commits[bb->commits_nr++] = r->item; | |
329 | } | |
330 | ||
089f7513 DS |
331 | trace2_data_intmax("pack-bitmap-write", the_repository, |
332 | "num_selected_commits", writer->selected_nr); | |
333 | trace2_data_intmax("pack-bitmap-write", the_repository, | |
334 | "num_maximal_commits", num_maximal); | |
f077b0a9 | 335 | |
2108fe4a | 336 | release_revisions(&revs); |
f077b0a9 | 337 | free_commit_list(reusable); |
4a9c5817 JK |
338 | } |
339 | ||
340 | static void bitmap_builder_clear(struct bitmap_builder *bb) | |
341 | { | |
342 | clear_bb_data(&bb->data); | |
343 | free(bb->commits); | |
344 | bb->commits_nr = bb->commits_alloc = 0; | |
345 | } | |
346 | ||
3ba3d062 TB |
347 | static int fill_bitmap_tree(struct bitmap *bitmap, |
348 | struct tree *tree) | |
4a9c5817 | 349 | { |
3ba3d062 | 350 | int found; |
4a9c5817 JK |
351 | uint32_t pos; |
352 | struct tree_desc desc; | |
353 | struct name_entry entry; | |
354 | ||
355 | /* | |
356 | * If our bit is already set, then there is nothing to do. Both this | |
357 | * tree and all of its children will be set. | |
358 | */ | |
3ba3d062 TB |
359 | pos = find_object_pos(&tree->object.oid, &found); |
360 | if (!found) | |
361 | return -1; | |
4a9c5817 | 362 | if (bitmap_get(bitmap, pos)) |
3ba3d062 | 363 | return 0; |
4a9c5817 JK |
364 | bitmap_set(bitmap, pos); |
365 | ||
366 | if (parse_tree(tree) < 0) | |
367 | die("unable to load tree object %s", | |
368 | oid_to_hex(&tree->object.oid)); | |
efed687e | 369 | init_tree_desc(&desc, &tree->object.oid, tree->buffer, tree->size); |
4a9c5817 JK |
370 | |
371 | while (tree_entry(&desc, &entry)) { | |
372 | switch (object_type(entry.mode)) { | |
373 | case OBJ_TREE: | |
3ba3d062 TB |
374 | if (fill_bitmap_tree(bitmap, |
375 | lookup_tree(the_repository, &entry.oid)) < 0) | |
376 | return -1; | |
4a9c5817 JK |
377 | break; |
378 | case OBJ_BLOB: | |
3ba3d062 TB |
379 | pos = find_object_pos(&entry.oid, &found); |
380 | if (!found) | |
381 | return -1; | |
382 | bitmap_set(bitmap, pos); | |
4a9c5817 JK |
383 | break; |
384 | default: | |
385 | /* Gitlink, etc; not reachable */ | |
386 | break; | |
387 | } | |
388 | } | |
7cc8f971 | 389 | |
4a9c5817 | 390 | free_tree_buffer(tree); |
3ba3d062 | 391 | return 0; |
4a9c5817 | 392 | } |
7cc8f971 | 393 | |
e9c38399 TB |
394 | static int reused_bitmaps_nr; |
395 | ||
3ba3d062 TB |
396 | static int fill_bitmap_commit(struct bb_commit *ent, |
397 | struct commit *commit, | |
398 | struct prio_queue *queue, | |
399 | struct prio_queue *tree_queue, | |
400 | struct bitmap_index *old_bitmap, | |
401 | const uint32_t *mapping) | |
4a9c5817 | 402 | { |
3ba3d062 TB |
403 | int found; |
404 | uint32_t pos; | |
4a9c5817 JK |
405 | if (!ent->bitmap) |
406 | ent->bitmap = bitmap_new(); | |
407 | ||
6dc5ef75 DS |
408 | prio_queue_put(queue, commit); |
409 | ||
410 | while (queue->nr) { | |
411 | struct commit_list *p; | |
412 | struct commit *c = prio_queue_get(queue); | |
413 | ||
341fa348 DS |
414 | if (old_bitmap && mapping) { |
415 | struct ewah_bitmap *old = bitmap_for_commit(old_bitmap, c); | |
416 | /* | |
417 | * If this commit has an old bitmap, then translate that | |
418 | * bitmap and add its bits to this one. No need to walk | |
419 | * parents or the tree for this commit. | |
420 | */ | |
e9c38399 TB |
421 | if (old && !rebuild_bitmap(mapping, old, ent->bitmap)) { |
422 | reused_bitmaps_nr++; | |
341fa348 | 423 | continue; |
e9c38399 | 424 | } |
341fa348 DS |
425 | } |
426 | ||
427 | /* | |
428 | * Mark ourselves and queue our tree. The commit | |
429 | * walk ensures we cover all parents. | |
430 | */ | |
3ba3d062 TB |
431 | pos = find_object_pos(&c->object.oid, &found); |
432 | if (!found) | |
433 | return -1; | |
434 | bitmap_set(ent->bitmap, pos); | |
ecb5091f ÆAB |
435 | prio_queue_put(tree_queue, |
436 | repo_get_commit_tree(the_repository, c)); | |
6dc5ef75 DS |
437 | |
438 | for (p = c->parents; p; p = p->next) { | |
3ba3d062 TB |
439 | pos = find_object_pos(&p->item->object.oid, &found); |
440 | if (!found) | |
441 | return -1; | |
6dc5ef75 DS |
442 | if (!bitmap_get(ent->bitmap, pos)) { |
443 | bitmap_set(ent->bitmap, pos); | |
444 | prio_queue_put(queue, p->item); | |
445 | } | |
446 | } | |
447 | } | |
341fa348 | 448 | |
3ba3d062 TB |
449 | while (tree_queue->nr) { |
450 | if (fill_bitmap_tree(ent->bitmap, | |
451 | prio_queue_get(tree_queue)) < 0) | |
452 | return -1; | |
453 | } | |
454 | return 0; | |
4a9c5817 | 455 | } |
7cc8f971 | 456 | |
4a9c5817 JK |
457 | static void store_selected(struct bb_commit *ent, struct commit *commit) |
458 | { | |
459 | struct bitmapped_commit *stored = &writer.selected[ent->idx]; | |
460 | khiter_t hash_pos; | |
461 | int hash_ret; | |
462 | ||
4a9c5817 JK |
463 | stored->bitmap = bitmap_to_ewah(ent->bitmap); |
464 | ||
465 | hash_pos = kh_put_oid_map(writer.bitmaps, commit->object.oid, &hash_ret); | |
466 | if (hash_ret == 0) | |
467 | die("Duplicate entry when writing index: %s", | |
468 | oid_to_hex(&commit->object.oid)); | |
469 | kh_value(writer.bitmaps, hash_pos) = stored; | |
470 | } | |
7cc8f971 | 471 | |
3ba3d062 | 472 | int bitmap_writer_build(struct packing_data *to_pack) |
4a9c5817 JK |
473 | { |
474 | struct bitmap_builder bb; | |
475 | size_t i; | |
476 | int nr_stored = 0; /* for progress */ | |
6dc5ef75 | 477 | struct prio_queue queue = { compare_commits_by_gen_then_commit_date }; |
341fa348 DS |
478 | struct prio_queue tree_queue = { NULL }; |
479 | struct bitmap_index *old_bitmap; | |
480 | uint32_t *mapping; | |
3ba3d062 | 481 | int closed = 1; /* until proven otherwise */ |
7cc8f971 | 482 | |
4a9c5817 JK |
483 | writer.bitmaps = kh_init_oid_map(); |
484 | writer.to_pack = to_pack; | |
485 | ||
486 | if (writer.show_progress) | |
487 | writer.progress = start_progress("Building bitmaps", writer.selected_nr); | |
488 | trace2_region_enter("pack-bitmap-write", "building_bitmaps_total", | |
489 | the_repository); | |
7cc8f971 | 490 | |
341fa348 DS |
491 | old_bitmap = prepare_bitmap_git(to_pack->repo); |
492 | if (old_bitmap) | |
493 | mapping = create_bitmap_mapping(old_bitmap, to_pack); | |
494 | else | |
495 | mapping = NULL; | |
496 | ||
f077b0a9 | 497 | bitmap_builder_init(&bb, &writer, old_bitmap); |
4a9c5817 JK |
498 | for (i = bb.commits_nr; i > 0; i--) { |
499 | struct commit *commit = bb.commits[i-1]; | |
500 | struct bb_commit *ent = bb_data_at(&bb.data, commit); | |
501 | struct commit *child; | |
010e5eac | 502 | int reused = 0; |
7cc8f971 | 503 | |
3ba3d062 TB |
504 | if (fill_bitmap_commit(ent, commit, &queue, &tree_queue, |
505 | old_bitmap, mapping) < 0) { | |
506 | closed = 0; | |
507 | break; | |
508 | } | |
7cc8f971 | 509 | |
4a9c5817 JK |
510 | if (ent->selected) { |
511 | store_selected(ent, commit); | |
512 | nr_stored++; | |
513 | display_progress(writer.progress, nr_stored); | |
514 | } | |
515 | ||
928e3f42 | 516 | while ((child = pop_commit(&ent->reverse_edges))) { |
4a9c5817 JK |
517 | struct bb_commit *child_ent = |
518 | bb_data_at(&bb.data, child); | |
519 | ||
520 | if (child_ent->bitmap) | |
521 | bitmap_or(child_ent->bitmap, ent->bitmap); | |
010e5eac | 522 | else if (reused) |
4a9c5817 | 523 | child_ent->bitmap = bitmap_dup(ent->bitmap); |
010e5eac JK |
524 | else { |
525 | child_ent->bitmap = ent->bitmap; | |
526 | reused = 1; | |
527 | } | |
4a9c5817 | 528 | } |
010e5eac JK |
529 | if (!reused) |
530 | bitmap_free(ent->bitmap); | |
4a9c5817 | 531 | ent->bitmap = NULL; |
7cc8f971 | 532 | } |
6dc5ef75 | 533 | clear_prio_queue(&queue); |
341fa348 | 534 | clear_prio_queue(&tree_queue); |
4a9c5817 | 535 | bitmap_builder_clear(&bb); |
1d7f7f24 | 536 | free_bitmap_index(old_bitmap); |
341fa348 | 537 | free(mapping); |
4a9c5817 JK |
538 | |
539 | trace2_region_leave("pack-bitmap-write", "building_bitmaps_total", | |
540 | the_repository); | |
e9c38399 TB |
541 | trace2_data_intmax("pack-bitmap-write", the_repository, |
542 | "building_bitmaps_reused", reused_bitmaps_nr); | |
7cc8f971 | 543 | |
7cc8f971 VM |
544 | stop_progress(&writer.progress); |
545 | ||
3ba3d062 TB |
546 | if (closed) |
547 | compute_xor_offsets(); | |
548 | return closed ? 0 : -1; | |
7cc8f971 VM |
549 | } |
550 | ||
551 | /** | |
552 | * Select the commits that will be bitmapped | |
553 | */ | |
554 | static inline unsigned int next_commit_index(unsigned int idx) | |
555 | { | |
556 | static const unsigned int MIN_COMMITS = 100; | |
557 | static const unsigned int MAX_COMMITS = 5000; | |
558 | ||
559 | static const unsigned int MUST_REGION = 100; | |
560 | static const unsigned int MIN_REGION = 20000; | |
561 | ||
562 | unsigned int offset, next; | |
563 | ||
564 | if (idx <= MUST_REGION) | |
565 | return 0; | |
566 | ||
567 | if (idx <= MIN_REGION) { | |
568 | offset = idx - MUST_REGION; | |
569 | return (offset < MIN_COMMITS) ? offset : MIN_COMMITS; | |
570 | } | |
571 | ||
572 | offset = idx - MIN_REGION; | |
573 | next = (offset < MAX_COMMITS) ? offset : MAX_COMMITS; | |
574 | ||
575 | return (next > MIN_COMMITS) ? next : MIN_COMMITS; | |
576 | } | |
577 | ||
578 | static int date_compare(const void *_a, const void *_b) | |
579 | { | |
580 | struct commit *a = *(struct commit **)_a; | |
581 | struct commit *b = *(struct commit **)_b; | |
582 | return (long)b->date - (long)a->date; | |
583 | } | |
584 | ||
7cc8f971 VM |
585 | void bitmap_writer_select_commits(struct commit **indexed_commits, |
586 | unsigned int indexed_commits_nr, | |
587 | int max_bitmaps) | |
588 | { | |
589 | unsigned int i = 0, j, next; | |
590 | ||
9ed0d8d6 | 591 | QSORT(indexed_commits, indexed_commits_nr, date_compare); |
7cc8f971 | 592 | |
7cc8f971 VM |
593 | if (indexed_commits_nr < 100) { |
594 | for (i = 0; i < indexed_commits_nr; ++i) | |
449fa5ee | 595 | push_bitmapped_commit(indexed_commits[i]); |
7cc8f971 VM |
596 | return; |
597 | } | |
598 | ||
b3118a56 ÆAB |
599 | if (writer.show_progress) |
600 | writer.progress = start_progress("Selecting bitmap commits", 0); | |
601 | ||
7cc8f971 | 602 | for (;;) { |
7cc8f971 VM |
603 | struct commit *chosen = NULL; |
604 | ||
605 | next = next_commit_index(i); | |
606 | ||
607 | if (i + next >= indexed_commits_nr) | |
608 | break; | |
609 | ||
610 | if (max_bitmaps > 0 && writer.selected_nr >= max_bitmaps) { | |
611 | writer.selected_nr = max_bitmaps; | |
612 | break; | |
613 | } | |
614 | ||
615 | if (next == 0) { | |
616 | chosen = indexed_commits[i]; | |
7cc8f971 VM |
617 | } else { |
618 | chosen = indexed_commits[i + next]; | |
619 | ||
620 | for (j = 0; j <= next; ++j) { | |
621 | struct commit *cm = indexed_commits[i + j]; | |
622 | ||
449fa5ee | 623 | if ((cm->object.flags & NEEDS_BITMAP) != 0) { |
7cc8f971 VM |
624 | chosen = cm; |
625 | break; | |
626 | } | |
627 | ||
628 | if (cm->parents && cm->parents->next) | |
629 | chosen = cm; | |
630 | } | |
631 | } | |
632 | ||
449fa5ee | 633 | push_bitmapped_commit(chosen); |
7cc8f971 VM |
634 | |
635 | i += next + 1; | |
636 | display_progress(writer.progress, i); | |
637 | } | |
638 | ||
639 | stop_progress(&writer.progress); | |
640 | } | |
641 | ||
642 | ||
98a3beab | 643 | static int hashwrite_ewah_helper(void *f, const void *buf, size_t len) |
7cc8f971 | 644 | { |
98a3beab | 645 | /* hashwrite will die on error */ |
646 | hashwrite(f, buf, len); | |
7cc8f971 VM |
647 | return len; |
648 | } | |
649 | ||
650 | /** | |
651 | * Write the bitmap index to disk | |
652 | */ | |
98a3beab | 653 | static inline void dump_bitmap(struct hashfile *f, struct ewah_bitmap *bitmap) |
7cc8f971 | 654 | { |
98a3beab | 655 | if (ewah_serialize_to(bitmap, hashwrite_ewah_helper, f) < 0) |
7cc8f971 VM |
656 | die("Failed to write bitmap index"); |
657 | } | |
658 | ||
8380dcd7 | 659 | static const struct object_id *oid_access(size_t pos, const void *table) |
7cc8f971 | 660 | { |
8380dcd7 | 661 | const struct pack_idx_entry * const *index = table; |
45ee13b9 | 662 | return &index[pos]->oid; |
7cc8f971 VM |
663 | } |
664 | ||
98a3beab | 665 | static void write_selected_commits_v1(struct hashfile *f, |
93eb41e2 AC |
666 | uint32_t *commit_positions, |
667 | off_t *offsets) | |
7cc8f971 VM |
668 | { |
669 | int i; | |
670 | ||
671 | for (i = 0; i < writer.selected_nr; ++i) { | |
672 | struct bitmapped_commit *stored = &writer.selected[i]; | |
7cc8f971 | 673 | |
93eb41e2 AC |
674 | if (offsets) |
675 | offsets[i] = hashfile_total(f); | |
676 | ||
aa301625 | 677 | hashwrite_be32(f, commit_positions[i]); |
98a3beab | 678 | hashwrite_u8(f, stored->xor_offset); |
679 | hashwrite_u8(f, stored->flags); | |
7cc8f971 | 680 | |
7cc8f971 VM |
681 | dump_bitmap(f, stored->write_as); |
682 | } | |
683 | } | |
684 | ||
93eb41e2 AC |
685 | static int table_cmp(const void *_va, const void *_vb, void *_data) |
686 | { | |
687 | uint32_t *commit_positions = _data; | |
688 | uint32_t a = commit_positions[*(uint32_t *)_va]; | |
689 | uint32_t b = commit_positions[*(uint32_t *)_vb]; | |
690 | ||
691 | if (a > b) | |
692 | return 1; | |
693 | else if (a < b) | |
694 | return -1; | |
695 | ||
696 | return 0; | |
697 | } | |
698 | ||
699 | static void write_lookup_table(struct hashfile *f, | |
93eb41e2 AC |
700 | uint32_t *commit_positions, |
701 | off_t *offsets) | |
702 | { | |
703 | uint32_t i; | |
704 | uint32_t *table, *table_inv; | |
705 | ||
706 | ALLOC_ARRAY(table, writer.selected_nr); | |
707 | ALLOC_ARRAY(table_inv, writer.selected_nr); | |
708 | ||
709 | for (i = 0; i < writer.selected_nr; i++) | |
710 | table[i] = i; | |
711 | ||
712 | /* | |
713 | * At the end of this sort table[j] = i means that the i'th | |
714 | * bitmap corresponds to j'th bitmapped commit (among the selected | |
715 | * commits) in lex order of OIDs. | |
716 | */ | |
717 | QSORT_S(table, writer.selected_nr, table_cmp, commit_positions); | |
718 | ||
719 | /* table_inv helps us discover that relationship (i'th bitmap | |
720 | * to j'th commit by j = table_inv[i]) | |
721 | */ | |
722 | for (i = 0; i < writer.selected_nr; i++) | |
723 | table_inv[table[i]] = i; | |
724 | ||
725 | trace2_region_enter("pack-bitmap-write", "writing_lookup_table", the_repository); | |
726 | for (i = 0; i < writer.selected_nr; i++) { | |
727 | struct bitmapped_commit *selected = &writer.selected[table[i]]; | |
728 | uint32_t xor_offset = selected->xor_offset; | |
729 | uint32_t xor_row; | |
730 | ||
731 | if (xor_offset) { | |
732 | /* | |
733 | * xor_index stores the index (in the bitmap entries) | |
734 | * of the corresponding xor bitmap. But we need to convert | |
735 | * this index into lookup table's index. So, table_inv[xor_index] | |
736 | * gives us the index position w.r.t. the lookup table. | |
737 | * | |
738 | * If "k = table[i] - xor_offset" then the xor base is the k'th | |
739 | * bitmap. `table_inv[k]` gives us the position of that bitmap | |
740 | * in the lookup table. | |
741 | */ | |
742 | uint32_t xor_index = table[i] - xor_offset; | |
743 | xor_row = table_inv[xor_index]; | |
744 | } else { | |
745 | xor_row = 0xffffffff; | |
746 | } | |
747 | ||
748 | hashwrite_be32(f, commit_positions[table[i]]); | |
749 | hashwrite_be64(f, (uint64_t)offsets[table[i]]); | |
750 | hashwrite_be32(f, xor_row); | |
751 | } | |
752 | trace2_region_leave("pack-bitmap-write", "writing_lookup_table", the_repository); | |
753 | ||
754 | free(table); | |
755 | free(table_inv); | |
756 | } | |
757 | ||
98a3beab | 758 | static void write_hash_cache(struct hashfile *f, |
ae4f07fb VM |
759 | struct pack_idx_entry **index, |
760 | uint32_t index_nr) | |
761 | { | |
762 | uint32_t i; | |
763 | ||
764 | for (i = 0; i < index_nr; ++i) { | |
765 | struct object_entry *entry = (struct object_entry *)index[i]; | |
7744a5d6 | 766 | hashwrite_be32(f, entry->hash); |
ae4f07fb VM |
767 | } |
768 | } | |
769 | ||
57665249 | 770 | void bitmap_writer_set_checksum(const unsigned char *sha1) |
7cc8f971 VM |
771 | { |
772 | hashcpy(writer.pack_checksum, sha1); | |
773 | } | |
774 | ||
775 | void bitmap_writer_finish(struct pack_idx_entry **index, | |
776 | uint32_t index_nr, | |
ae4f07fb VM |
777 | const char *filename, |
778 | uint16_t options) | |
7cc8f971 | 779 | { |
7cc8f971 VM |
780 | static uint16_t default_version = 1; |
781 | static uint16_t flags = BITMAP_OPT_FULL_DAG; | |
594fa999 | 782 | struct strbuf tmp_file = STRBUF_INIT; |
98a3beab | 783 | struct hashfile *f; |
aa301625 | 784 | uint32_t *commit_positions = NULL; |
93eb41e2 | 785 | off_t *offsets = NULL; |
aa301625 | 786 | uint32_t i; |
7cc8f971 VM |
787 | |
788 | struct bitmap_disk_header header; | |
789 | ||
594fa999 | 790 | int fd = odb_mkstemp(&tmp_file, "pack/tmp_bitmap_XXXXXX"); |
7cc8f971 | 791 | |
98a3beab | 792 | f = hashfd(fd, tmp_file.buf); |
7cc8f971 VM |
793 | |
794 | memcpy(header.magic, BITMAP_IDX_SIGNATURE, sizeof(BITMAP_IDX_SIGNATURE)); | |
795 | header.version = htons(default_version); | |
ae4f07fb | 796 | header.options = htons(flags | options); |
7cc8f971 | 797 | header.entry_count = htonl(writer.selected_nr); |
50546b15 | 798 | hashcpy(header.checksum, writer.pack_checksum); |
7cc8f971 | 799 | |
0f4d6cad | 800 | hashwrite(f, &header, sizeof(header) - GIT_MAX_RAWSZ + the_hash_algo->rawsz); |
7cc8f971 VM |
801 | dump_bitmap(f, writer.commits); |
802 | dump_bitmap(f, writer.trees); | |
803 | dump_bitmap(f, writer.blobs); | |
804 | dump_bitmap(f, writer.tags); | |
aa301625 | 805 | |
93eb41e2 AC |
806 | if (options & BITMAP_OPT_LOOKUP_TABLE) |
807 | CALLOC_ARRAY(offsets, index_nr); | |
808 | ||
aa301625 AC |
809 | ALLOC_ARRAY(commit_positions, writer.selected_nr); |
810 | ||
811 | for (i = 0; i < writer.selected_nr; i++) { | |
812 | struct bitmapped_commit *stored = &writer.selected[i]; | |
813 | int commit_pos = oid_pos(&stored->commit->object.oid, index, index_nr, oid_access); | |
814 | ||
815 | if (commit_pos < 0) | |
816 | BUG(_("trying to write commit not in index")); | |
817 | ||
818 | commit_positions[i] = commit_pos; | |
819 | } | |
820 | ||
969a5645 | 821 | write_selected_commits_v1(f, commit_positions, offsets); |
93eb41e2 AC |
822 | |
823 | if (options & BITMAP_OPT_LOOKUP_TABLE) | |
969a5645 | 824 | write_lookup_table(f, commit_positions, offsets); |
7cc8f971 | 825 | |
ae4f07fb VM |
826 | if (options & BITMAP_OPT_HASH_CACHE) |
827 | write_hash_cache(f, index, index_nr); | |
828 | ||
020406ea NS |
829 | finalize_hashfile(f, NULL, FSYNC_COMPONENT_PACK_METADATA, |
830 | CSUM_HASH_IN_STREAM | CSUM_FSYNC | CSUM_CLOSE); | |
7cc8f971 | 831 | |
594fa999 | 832 | if (adjust_shared_perm(tmp_file.buf)) |
7cc8f971 VM |
833 | die_errno("unable to make temporary bitmap file readable"); |
834 | ||
594fa999 | 835 | if (rename(tmp_file.buf, filename)) |
7cc8f971 | 836 | die_errno("unable to rename temporary bitmap file to '%s'", filename); |
594fa999 JK |
837 | |
838 | strbuf_release(&tmp_file); | |
aa301625 | 839 | free(commit_positions); |
93eb41e2 | 840 | free(offsets); |
7cc8f971 | 841 | } |