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