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