?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
Merge branch 'ak/config-bad-bool-error'
[git/debian.git] / commit-graph.c
blobed31843fa522ee5a49e151c41e1527ebd9c6dbc0
1 #include "git-compat-util.h"
2 #include "config.h"
3 #include "lockfile.h"
4 #include "pack.h"
5 #include "packfile.h"
6 #include "commit.h"
7 #include "object.h"
8 #include "refs.h"
9 #include "revision.h"
10 #include "hash-lookup.h"
11 #include "commit-graph.h"
12 #include "object-store.h"
13 #include "alloc.h"
14 #include "hashmap.h"
15 #include "replace-object.h"
16 #include "progress.h"
17 #include "bloom.h"
18 #include "commit-slab.h"
19 #include "shallow.h"
20 #include "json-writer.h"
21 #include "trace2.h"
22
23 void git_test_write_commit_graph_or_die(void)
24 {
25 int flags = 0;
26 if (!git_env_bool(GIT_TEST_COMMIT_GRAPH, 0))
27 return;
28
29 if (git_env_bool(GIT_TEST_COMMIT_GRAPH_CHANGED_PATHS, 0))
30 flags = COMMIT_GRAPH_WRITE_BLOOM_FILTERS;
31
32 if (write_commit_graph_reachable(the_repository->objects->odb,
33 flags, NULL))
34 die("failed to write commit-graph under GIT_TEST_COMMIT_GRAPH");
35 }
36
37 #define GRAPH_SIGNATURE 0x43475048 /* "CGPH" */
38 #define GRAPH_CHUNKID_OIDFANOUT 0x4f494446 /* "OIDF" */
39 #define GRAPH_CHUNKID_OIDLOOKUP 0x4f49444c /* "OIDL" */
40 #define GRAPH_CHUNKID_DATA 0x43444154 /* "CDAT" */
41 #define GRAPH_CHUNKID_GENERATION_DATA 0x47444154 /* "GDAT" */
42 #define GRAPH_CHUNKID_GENERATION_DATA_OVERFLOW 0x47444f56 /* "GDOV" */
43 #define GRAPH_CHUNKID_EXTRAEDGES 0x45444745 /* "EDGE" */
44 #define GRAPH_CHUNKID_BLOOMINDEXES 0x42494458 /* "BIDX" */
45 #define GRAPH_CHUNKID_BLOOMDATA 0x42444154 /* "BDAT" */
46 #define GRAPH_CHUNKID_BASE 0x42415345 /* "BASE" */
47 #define MAX_NUM_CHUNKS 9
48
49 #define GRAPH_DATA_WIDTH (the_hash_algo->rawsz + 16)
50
51 #define GRAPH_VERSION_1 0x1
52 #define GRAPH_VERSION GRAPH_VERSION_1
53
54 #define GRAPH_EXTRA_EDGES_NEEDED 0x80000000
55 #define GRAPH_EDGE_LAST_MASK 0x7fffffff
56 #define GRAPH_PARENT_NONE 0x70000000
57
58 #define GRAPH_LAST_EDGE 0x80000000
59
60 #define GRAPH_HEADER_SIZE 8
61 #define GRAPH_FANOUT_SIZE (4 * 256)
62 #define GRAPH_CHUNKLOOKUP_WIDTH 12
63 #define GRAPH_MIN_SIZE (GRAPH_HEADER_SIZE + 4 * GRAPH_CHUNKLOOKUP_WIDTH \
64 + GRAPH_FANOUT_SIZE + the_hash_algo->rawsz)
65
66 #define CORRECTED_COMMIT_DATE_OFFSET_OVERFLOW (1ULL << 31)
67
68 /* Remember to update object flag allocation in object.h */
69 #define REACHABLE (1u<<15)
70
71 define_commit_slab(topo_level_slab, uint32_t);
72
73 /* Keep track of the order in which commits are added to our list. */
74 define_commit_slab(commit_pos, int);
75 static struct commit_pos commit_pos = COMMIT_SLAB_INIT(1, commit_pos);
76
77 static void set_commit_pos(struct repository *r, const struct object_id *oid)
78 {
79 static int32_t max_pos;
80 struct commit *commit = lookup_commit(r, oid);
81
82 if (!commit)
83 return; /* should never happen, but be lenient */
84
85 *commit_pos_at(&commit_pos, commit) = max_pos++;
86 }
87
88 static int commit_pos_cmp(const void *va, const void *vb)
89 {
90 const struct commit *a = *(const struct commit **)va;
91 const struct commit *b = *(const struct commit **)vb;
92 return commit_pos_at(&commit_pos, a) -
93 commit_pos_at(&commit_pos, b);
94 }
95
96 define_commit_slab(commit_graph_data_slab, struct commit_graph_data);
97 static struct commit_graph_data_slab commit_graph_data_slab =
98 COMMIT_SLAB_INIT(1, commit_graph_data_slab);
99
100 uint32_t commit_graph_position(const struct commit *c)
101 {
102 struct commit_graph_data *data =
103 commit_graph_data_slab_peek(&commit_graph_data_slab, c);
104
105 return data ? data->graph_pos : COMMIT_NOT_FROM_GRAPH;
106 }
107
108 timestamp_t commit_graph_generation(const struct commit *c)
109 {
110 struct commit_graph_data *data =
111 commit_graph_data_slab_peek(&commit_graph_data_slab, c);
112
113 if (!data)
114 return GENERATION_NUMBER_INFINITY;
115 else if (data->graph_pos == COMMIT_NOT_FROM_GRAPH)
116 return GENERATION_NUMBER_INFINITY;
117
118 return data->generation;
119 }
120
121 static struct commit_graph_data *commit_graph_data_at(const struct commit *c)
122 {
123 unsigned int i, nth_slab;
124 struct commit_graph_data *data =
125 commit_graph_data_slab_peek(&commit_graph_data_slab, c);
126
127 if (data)
128 return data;
129
130 nth_slab = c->index / commit_graph_data_slab.slab_size;
131 data = commit_graph_data_slab_at(&commit_graph_data_slab, c);
132
133 /*
134 * commit-slab initializes elements with zero, overwrite this with
135 * COMMIT_NOT_FROM_GRAPH for graph_pos.
136 *
137 * We avoid initializing generation with checking if graph position
138 * is not COMMIT_NOT_FROM_GRAPH.
139 */
140 for (i = 0; i < commit_graph_data_slab.slab_size; i++) {
141 commit_graph_data_slab.slab[nth_slab][i].graph_pos =
142 COMMIT_NOT_FROM_GRAPH;
143 }
144
145 return data;
146 }
147
148 /*
149 * Should be used only while writing commit-graph as it compares
150 * generation value of commits by directly accessing commit-slab.
151 */
152 static int commit_gen_cmp(const void *va, const void *vb)
153 {
154 const struct commit *a = *(const struct commit **)va;
155 const struct commit *b = *(const struct commit **)vb;
156
157 const timestamp_t generation_a = commit_graph_data_at(a)->generation;
158 const timestamp_t generation_b = commit_graph_data_at(b)->generation;
159 /* lower generation commits first */
160 if (generation_a < generation_b)
161 return -1;
162 else if (generation_a > generation_b)
163 return 1;
164
165 /* use date as a heuristic when generations are equal */
166 if (a->date < b->date)
167 return -1;
168 else if (a->date > b->date)
169 return 1;
170 return 0;
171 }
172
173 char *get_commit_graph_filename(struct object_directory *obj_dir)
174 {
175 return xstrfmt("%s/info/commit-graph", obj_dir->path);
176 }
177
178 static char *get_split_graph_filename(struct object_directory *odb,
179 const char *oid_hex)
180 {
181 return xstrfmt("%s/info/commit-graphs/graph-%s.graph", odb->path,
182 oid_hex);
183 }
184
185 char *get_commit_graph_chain_filename(struct object_directory *odb)
186 {
187 return xstrfmt("%s/info/commit-graphs/commit-graph-chain", odb->path);
188 }
189
190 static uint8_t oid_version(void)
191 {
192 switch (hash_algo_by_ptr(the_hash_algo)) {
193 case GIT_HASH_SHA1:
194 return 1;
195 case GIT_HASH_SHA256:
196 return 2;
197 default:
198 die(_("invalid hash version"));
199 }
200 }
201
202 static struct commit_graph *alloc_commit_graph(void)
203 {
204 struct commit_graph *g = xcalloc(1, sizeof(*g));
205
206 return g;
207 }
208
209 extern int read_replace_refs;
210
211 static int commit_graph_compatible(struct repository *r)
212 {
213 if (!r->gitdir)
214 return 0;
215
216 if (read_replace_refs) {
217 prepare_replace_object(r);
218 if (hashmap_get_size(&r->objects->replace_map->map)) {
219 warning(_("repository contains replace objects; "
220 "skipping commit-graph"));
221 return 0;
222 }
223 }
224
225 prepare_commit_graft(r);
226 if (r->parsed_objects &&
227 (r->parsed_objects->grafts_nr || r->parsed_objects->substituted_parent)) {
228 warning(_("repository contains (deprecated) grafts; "
229 "skipping commit-graph"));
230 return 0;
231 }
232 if (is_repository_shallow(r)) {
233 warning(_("repository is shallow; skipping commit-graph"));
234 return 0;
235 }
236
237 return 1;
238 }
239
240 int open_commit_graph(const char *graph_file, int *fd, struct stat *st)
241 {
242 *fd = git_open(graph_file);
243 if (*fd < 0)
244 return 0;
245 if (fstat(*fd, st)) {
246 close(*fd);
247 return 0;
248 }
249 return 1;
250 }
251
252 struct commit_graph *load_commit_graph_one_fd_st(struct repository *r,
253 int fd, struct stat *st,
254 struct object_directory *odb)
255 {
256 void *graph_map;
257 size_t graph_size;
258 struct commit_graph *ret;
259
260 graph_size = xsize_t(st->st_size);
261
262 if (graph_size < GRAPH_MIN_SIZE) {
263 close(fd);
264 error(_("commit-graph file is too small"));
265 return NULL;
266 }
267 graph_map = xmmap(NULL, graph_size, PROT_READ, MAP_PRIVATE, fd, 0);
268 close(fd);
269 ret = parse_commit_graph(r, graph_map, graph_size);
270
271 if (ret)
272 ret->odb = odb;
273 else
274 munmap(graph_map, graph_size);
275
276 return ret;
277 }
278
279 static int verify_commit_graph_lite(struct commit_graph *g)
280 {
281 /*
282 * Basic validation shared between parse_commit_graph()
283 * which'll be called every time the graph is used, and the
284 * much more expensive verify_commit_graph() used by
285 * "commit-graph verify".
286 *
287 * There should only be very basic checks here to ensure that
288 * we don't e.g. segfault in fill_commit_in_graph(), but
289 * because this is a very hot codepath nothing that e.g. loops
290 * over g->num_commits, or runs a checksum on the commit-graph
291 * itself.
292 */
293 if (!g->chunk_oid_fanout) {
294 error("commit-graph is missing the OID Fanout chunk");
295 return 1;
296 }
297 if (!g->chunk_oid_lookup) {
298 error("commit-graph is missing the OID Lookup chunk");
299 return 1;
300 }
301 if (!g->chunk_commit_data) {
302 error("commit-graph is missing the Commit Data chunk");
303 return 1;
304 }
305
306 return 0;
307 }
308
309 struct commit_graph *parse_commit_graph(struct repository *r,
310 void *graph_map, size_t graph_size)
311 {
312 const unsigned char *data, *chunk_lookup;
313 uint32_t i;
314 struct commit_graph *graph;
315 uint64_t next_chunk_offset;
316 uint32_t graph_signature;
317 unsigned char graph_version, hash_version;
318
319 if (!graph_map)
320 return NULL;
321
322 if (graph_size < GRAPH_MIN_SIZE)
323 return NULL;
324
325 data = (const unsigned char *)graph_map;
326
327 graph_signature = get_be32(data);
328 if (graph_signature != GRAPH_SIGNATURE) {
329 error(_("commit-graph signature %X does not match signature %X"),
330 graph_signature, GRAPH_SIGNATURE);
331 return NULL;
332 }
333
334 graph_version = *(unsigned char*)(data + 4);
335 if (graph_version != GRAPH_VERSION) {
336 error(_("commit-graph version %X does not match version %X"),
337 graph_version, GRAPH_VERSION);
338 return NULL;
339 }
340
341 hash_version = *(unsigned char*)(data + 5);
342 if (hash_version != oid_version()) {
343 error(_("commit-graph hash version %X does not match version %X"),
344 hash_version, oid_version());
345 return NULL;
346 }
347
348 prepare_repo_settings(r);
349
350 graph = alloc_commit_graph();
351
352 graph->hash_len = the_hash_algo->rawsz;
353 graph->num_chunks = *(unsigned char*)(data + 6);
354 graph->data = graph_map;
355 graph->data_len = graph_size;
356
357 if (graph_size < GRAPH_HEADER_SIZE +
358 (graph->num_chunks + 1) * GRAPH_CHUNKLOOKUP_WIDTH +
359 GRAPH_FANOUT_SIZE + the_hash_algo->rawsz) {
360 error(_("commit-graph file is too small to hold %u chunks"),
361 graph->num_chunks);
362 free(graph);
363 return NULL;
364 }
365
366 chunk_lookup = data + 8;
367 next_chunk_offset = get_be64(chunk_lookup + 4);
368 for (i = 0; i < graph->num_chunks; i++) {
369 uint32_t chunk_id;
370 uint64_t chunk_offset = next_chunk_offset;
371 int chunk_repeated = 0;
372
373 chunk_id = get_be32(chunk_lookup + 0);
374
375 chunk_lookup += GRAPH_CHUNKLOOKUP_WIDTH;
376 next_chunk_offset = get_be64(chunk_lookup + 4);
377
378 if (chunk_offset > graph_size - the_hash_algo->rawsz) {
379 error(_("commit-graph improper chunk offset %08x%08x"), (uint32_t)(chunk_offset >> 32),
380 (uint32_t)chunk_offset);
381 goto free_and_return;
382 }
383
384 switch (chunk_id) {
385 case GRAPH_CHUNKID_OIDFANOUT:
386 if (graph->chunk_oid_fanout)
387 chunk_repeated = 1;
388 else
389 graph->chunk_oid_fanout = (uint32_t*)(data + chunk_offset);
390 break;
391
392 case GRAPH_CHUNKID_OIDLOOKUP:
393 if (graph->chunk_oid_lookup)
394 chunk_repeated = 1;
395 else {
396 graph->chunk_oid_lookup = data + chunk_offset;
397 graph->num_commits = (next_chunk_offset - chunk_offset)
398 / graph->hash_len;
399 }
400 break;
401
402 case GRAPH_CHUNKID_DATA:
403 if (graph->chunk_commit_data)
404 chunk_repeated = 1;
405 else
406 graph->chunk_commit_data = data + chunk_offset;
407 break;
408
409 case GRAPH_CHUNKID_GENERATION_DATA:
410 if (graph->chunk_generation_data)
411 chunk_repeated = 1;
412 else
413 graph->chunk_generation_data = data + chunk_offset;
414 break;
415
416 case GRAPH_CHUNKID_GENERATION_DATA_OVERFLOW:
417 if (graph->chunk_generation_data_overflow)
418 chunk_repeated = 1;
419 else
420 graph->chunk_generation_data_overflow = data + chunk_offset;
421 break;
422
423 case GRAPH_CHUNKID_EXTRAEDGES:
424 if (graph->chunk_extra_edges)
425 chunk_repeated = 1;
426 else
427 graph->chunk_extra_edges = data + chunk_offset;
428 break;
429
430 case GRAPH_CHUNKID_BASE:
431 if (graph->chunk_base_graphs)
432 chunk_repeated = 1;
433 else
434 graph->chunk_base_graphs = data + chunk_offset;
435 break;
436
437 case GRAPH_CHUNKID_BLOOMINDEXES:
438 if (graph->chunk_bloom_indexes)
439 chunk_repeated = 1;
440 else if (r->settings.commit_graph_read_changed_paths)
441 graph->chunk_bloom_indexes = data + chunk_offset;
442 break;
443
444 case GRAPH_CHUNKID_BLOOMDATA:
445 if (graph->chunk_bloom_data)
446 chunk_repeated = 1;
447 else if (r->settings.commit_graph_read_changed_paths) {
448 uint32_t hash_version;
449 graph->chunk_bloom_data = data + chunk_offset;
450 hash_version = get_be32(data + chunk_offset);
451
452 if (hash_version != 1)
453 break;
454
455 graph->bloom_filter_settings = xmalloc(sizeof(struct bloom_filter_settings));
456 graph->bloom_filter_settings->hash_version = hash_version;
457 graph->bloom_filter_settings->num_hashes = get_be32(data + chunk_offset + 4);
458 graph->bloom_filter_settings->bits_per_entry = get_be32(data + chunk_offset + 8);
459 graph->bloom_filter_settings->max_changed_paths = DEFAULT_BLOOM_MAX_CHANGES;
460 }
461 break;
462 }
463
464 if (chunk_repeated) {
465 error(_("commit-graph chunk id %08x appears multiple times"), chunk_id);
466 goto free_and_return;
467 }
468 }
469
470 if (graph->chunk_bloom_indexes && graph->chunk_bloom_data) {
471 init_bloom_filters();
472 } else {
473 /* We need both the bloom chunks to exist together. Else ignore the data */
474 graph->chunk_bloom_indexes = NULL;
475 graph->chunk_bloom_data = NULL;
476 FREE_AND_NULL(graph->bloom_filter_settings);
477 }
478
479 hashcpy(graph->oid.hash, graph->data + graph->data_len - graph->hash_len);
480
481 if (verify_commit_graph_lite(graph))
482 goto free_and_return;
483
484 return graph;
485
486 free_and_return:
487 free(graph->bloom_filter_settings);
488 free(graph);
489 return NULL;
490 }
491
492 static struct commit_graph *load_commit_graph_one(struct repository *r,
493 const char *graph_file,
494 struct object_directory *odb)
495 {
496
497 struct stat st;
498 int fd;
499 struct commit_graph *g;
500 int open_ok = open_commit_graph(graph_file, &fd, &st);
501
502 if (!open_ok)
503 return NULL;
504
505 g = load_commit_graph_one_fd_st(r, fd, &st, odb);
506
507 if (g)
508 g->filename = xstrdup(graph_file);
509
510 return g;
511 }
512
513 static struct commit_graph *load_commit_graph_v1(struct repository *r,
514 struct object_directory *odb)
515 {
516 char *graph_name = get_commit_graph_filename(odb);
517 struct commit_graph *g = load_commit_graph_one(r, graph_name, odb);
518 free(graph_name);
519
520 return g;
521 }
522
523 static int add_graph_to_chain(struct commit_graph *g,
524 struct commit_graph *chain,
525 struct object_id *oids,
526 int n)
527 {
528 struct commit_graph *cur_g = chain;
529
530 if (n && !g->chunk_base_graphs) {
531 warning(_("commit-graph has no base graphs chunk"));
532 return 0;
533 }
534
535 while (n) {
536 n--;
537
538 if (!cur_g ||
539 !oideq(&oids[n], &cur_g->oid) ||
540 !hasheq(oids[n].hash, g->chunk_base_graphs + g->hash_len * n)) {
541 warning(_("commit-graph chain does not match"));
542 return 0;
543 }
544
545 cur_g = cur_g->base_graph;
546 }
547
548 g->base_graph = chain;
549
550 if (chain)
551 g->num_commits_in_base = chain->num_commits + chain->num_commits_in_base;
552
553 return 1;
554 }
555
556 static struct commit_graph *load_commit_graph_chain(struct repository *r,
557 struct object_directory *odb)
558 {
559 struct commit_graph *graph_chain = NULL;
560 struct strbuf line = STRBUF_INIT;
561 struct stat st;
562 struct object_id *oids;
563 int i = 0, valid = 1, count;
564 char *chain_name = get_commit_graph_chain_filename(odb);
565 FILE *fp;
566 int stat_res;
567
568 fp = fopen(chain_name, "r");
569 stat_res = stat(chain_name, &st);
570 free(chain_name);
571
572 if (!fp ||
573 stat_res ||
574 st.st_size <= the_hash_algo->hexsz)
575 return NULL;
576
577 count = st.st_size / (the_hash_algo->hexsz + 1);
578 oids = xcalloc(count, sizeof(struct object_id));
579
580 prepare_alt_odb(r);
581
582 for (i = 0; i < count; i++) {
583 struct object_directory *odb;
584
585 if (strbuf_getline_lf(&line, fp) == EOF)
586 break;
587
588 if (get_oid_hex(line.buf, &oids[i])) {
589 warning(_("invalid commit-graph chain: line '%s' not a hash"),
590 line.buf);
591 valid = 0;
592 break;
593 }
594
595 valid = 0;
596 for (odb = r->objects->odb; odb; odb = odb->next) {
597 char *graph_name = get_split_graph_filename(odb, line.buf);
598 struct commit_graph *g = load_commit_graph_one(r, graph_name, odb);
599
600 free(graph_name);
601
602 if (g) {
603 if (add_graph_to_chain(g, graph_chain, oids, i)) {
604 graph_chain = g;
605 valid = 1;
606 }
607
608 break;
609 }
610 }
611
612 if (!valid) {
613 warning(_("unable to find all commit-graph files"));
614 break;
615 }
616 }
617
618 free(oids);
619 fclose(fp);
620 strbuf_release(&line);
621
622 return graph_chain;
623 }
624
625 /*
626 * returns 1 if and only if all graphs in the chain have
627 * corrected commit dates stored in the generation_data chunk.
628 */
629 static int validate_mixed_generation_chain(struct commit_graph *g)
630 {
631 int read_generation_data = 1;
632 struct commit_graph *p = g;
633
634 while (read_generation_data && p) {
635 read_generation_data = p->read_generation_data;
636 p = p->base_graph;
637 }
638
639 if (read_generation_data)
640 return 1;
641
642 while (g) {
643 g->read_generation_data = 0;
644 g = g->base_graph;
645 }
646
647 return 0;
648 }
649
650 struct commit_graph *read_commit_graph_one(struct repository *r,
651 struct object_directory *odb)
652 {
653 struct commit_graph *g = load_commit_graph_v1(r, odb);
654
655 if (!g)
656 g = load_commit_graph_chain(r, odb);
657
658 validate_mixed_generation_chain(g);
659
660 return g;
661 }
662
663 static void prepare_commit_graph_one(struct repository *r,
664 struct object_directory *odb)
665 {
666
667 if (r->objects->commit_graph)
668 return;
669
670 r->objects->commit_graph = read_commit_graph_one(r, odb);
671 }
672
673 /*
674 * Return 1 if commit_graph is non-NULL, and 0 otherwise.
675 *
676 * On the first invocation, this function attempts to load the commit
677 * graph if the_repository is configured to have one.
678 */
679 static int prepare_commit_graph(struct repository *r)
680 {
681 struct object_directory *odb;
682
683 /*
684 * This must come before the "already attempted?" check below, because
685 * we want to disable even an already-loaded graph file.
686 */
687 if (r->commit_graph_disabled)
688 return 0;
689
690 if (r->objects->commit_graph_attempted)
691 return !!r->objects->commit_graph;
692 r->objects->commit_graph_attempted = 1;
693
694 prepare_repo_settings(r);
695
696 if (!git_env_bool(GIT_TEST_COMMIT_GRAPH, 0) &&
697 r->settings.core_commit_graph != 1)
698 /*
699 * This repository is not configured to use commit graphs, so
700 * do not load one. (But report commit_graph_attempted anyway
701 * so that commit graph loading is not attempted again for this
702 * repository.)
703 */
704 return 0;
705
706 if (!commit_graph_compatible(r))
707 return 0;
708
709 prepare_alt_odb(r);
710 for (odb = r->objects->odb;
711 !r->objects->commit_graph && odb;
712 odb = odb->next)
713 prepare_commit_graph_one(r, odb);
714 return !!r->objects->commit_graph;
715 }
716
717 int generation_numbers_enabled(struct repository *r)
718 {
719 uint32_t first_generation;
720 struct commit_graph *g;
721 if (!prepare_commit_graph(r))
722 return 0;
723
724 g = r->objects->commit_graph;
725
726 if (!g->num_commits)
727 return 0;
728
729 first_generation = get_be32(g->chunk_commit_data +
730 g->hash_len + 8) >> 2;
731
732 return !!first_generation;
733 }
734
735 int corrected_commit_dates_enabled(struct repository *r)
736 {
737 struct commit_graph *g;
738 if (!prepare_commit_graph(r))
739 return 0;
740
741 g = r->objects->commit_graph;
742
743 if (!g->num_commits)
744 return 0;
745
746 return g->read_generation_data;
747 }
748
749 struct bloom_filter_settings *get_bloom_filter_settings(struct repository *r)
750 {
751 struct commit_graph *g = r->objects->commit_graph;
752 while (g) {
753 if (g->bloom_filter_settings)
754 return g->bloom_filter_settings;
755 g = g->base_graph;
756 }
757 return NULL;
758 }
759
760 static void close_commit_graph_one(struct commit_graph *g)
761 {
762 if (!g)
763 return;
764
765 close_commit_graph_one(g->base_graph);
766 free_commit_graph(g);
767 }
768
769 void close_commit_graph(struct raw_object_store *o)
770 {
771 close_commit_graph_one(o->commit_graph);
772 o->commit_graph = NULL;
773 }
774
775 static int bsearch_graph(struct commit_graph *g, struct object_id *oid, uint32_t *pos)
776 {
777 return bsearch_hash(oid->hash, g->chunk_oid_fanout,
778 g->chunk_oid_lookup, g->hash_len, pos);
779 }
780
781 static void load_oid_from_graph(struct commit_graph *g,
782 uint32_t pos,
783 struct object_id *oid)
784 {
785 uint32_t lex_index;
786
787 while (g && pos < g->num_commits_in_base)
788 g = g->base_graph;
789
790 if (!g)
791 BUG("NULL commit-graph");
792
793 if (pos >= g->num_commits + g->num_commits_in_base)
794 die(_("invalid commit position. commit-graph is likely corrupt"));
795
796 lex_index = pos - g->num_commits_in_base;
797
798 hashcpy(oid->hash, g->chunk_oid_lookup + g->hash_len * lex_index);
799 }
800
801 static struct commit_list **insert_parent_or_die(struct repository *r,
802 struct commit_graph *g,
803 uint32_t pos,
804 struct commit_list **pptr)
805 {
806 struct commit *c;
807 struct object_id oid;
808
809 if (pos >= g->num_commits + g->num_commits_in_base)
810 die("invalid parent position %"PRIu32, pos);
811
812 load_oid_from_graph(g, pos, &oid);
813 c = lookup_commit(r, &oid);
814 if (!c)
815 die(_("could not find commit %s"), oid_to_hex(&oid));
816 commit_graph_data_at(c)->graph_pos = pos;
817 return &commit_list_insert(c, pptr)->next;
818 }
819
820 static void fill_commit_graph_info(struct commit *item, struct commit_graph *g, uint32_t pos)
821 {
822 const unsigned char *commit_data;
823 struct commit_graph_data *graph_data;
824 uint32_t lex_index, offset_pos;
825 uint64_t date_high, date_low, offset;
826
827 while (pos < g->num_commits_in_base)
828 g = g->base_graph;
829
830 if (pos >= g->num_commits + g->num_commits_in_base)
831 die(_("invalid commit position. commit-graph is likely corrupt"));
832
833 lex_index = pos - g->num_commits_in_base;
834 commit_data = g->chunk_commit_data + GRAPH_DATA_WIDTH * lex_index;
835
836 graph_data = commit_graph_data_at(item);
837 graph_data->graph_pos = pos;
838
839 date_high = get_be32(commit_data + g->hash_len + 8) & 0x3;
840 date_low = get_be32(commit_data + g->hash_len + 12);
841 item->date = (timestamp_t)((date_high << 32) | date_low);
842
843 if (g->read_generation_data) {
844 offset = (timestamp_t)get_be32(g->chunk_generation_data + sizeof(uint32_t) * lex_index);
845
846 if (offset & CORRECTED_COMMIT_DATE_OFFSET_OVERFLOW) {
847 if (!g->chunk_generation_data_overflow)
848 die(_("commit-graph requires overflow generation data but has none"));
849
850 offset_pos = offset ^ CORRECTED_COMMIT_DATE_OFFSET_OVERFLOW;
851 graph_data->generation = get_be64(g->chunk_generation_data_overflow + 8 * offset_pos);
852 } else
853 graph_data->generation = item->date + offset;
854 } else
855 graph_data->generation = get_be32(commit_data + g->hash_len + 8) >> 2;
856
857 if (g->topo_levels)
858 *topo_level_slab_at(g->topo_levels, item) = get_be32(commit_data + g->hash_len + 8) >> 2;
859 }
860
861 static inline void set_commit_tree(struct commit *c, struct tree *t)
862 {
863 c->maybe_tree = t;
864 }
865
866 static int fill_commit_in_graph(struct repository *r,
867 struct commit *item,
868 struct commit_graph *g, uint32_t pos)
869 {
870 uint32_t edge_value;
871 uint32_t *parent_data_ptr;
872 struct commit_list **pptr;
873 const unsigned char *commit_data;
874 uint32_t lex_index;
875
876 while (pos < g->num_commits_in_base)
877 g = g->base_graph;
878
879 fill_commit_graph_info(item, g, pos);
880
881 lex_index = pos - g->num_commits_in_base;
882 commit_data = g->chunk_commit_data + (g->hash_len + 16) * lex_index;
883
884 item->object.parsed = 1;
885
886 set_commit_tree(item, NULL);
887
888 pptr = &item->parents;
889
890 edge_value = get_be32(commit_data + g->hash_len);
891 if (edge_value == GRAPH_PARENT_NONE)
892 return 1;
893 pptr = insert_parent_or_die(r, g, edge_value, pptr);
894
895 edge_value = get_be32(commit_data + g->hash_len + 4);
896 if (edge_value == GRAPH_PARENT_NONE)
897 return 1;
898 if (!(edge_value & GRAPH_EXTRA_EDGES_NEEDED)) {
899 pptr = insert_parent_or_die(r, g, edge_value, pptr);
900 return 1;
901 }
902
903 parent_data_ptr = (uint32_t*)(g->chunk_extra_edges +
904 4 * (uint64_t)(edge_value & GRAPH_EDGE_LAST_MASK));
905 do {
906 edge_value = get_be32(parent_data_ptr);
907 pptr = insert_parent_or_die(r, g,
908 edge_value & GRAPH_EDGE_LAST_MASK,
909 pptr);
910 parent_data_ptr++;
911 } while (!(edge_value & GRAPH_LAST_EDGE));
912
913 return 1;
914 }
915
916 static int find_commit_in_graph(struct commit *item, struct commit_graph *g, uint32_t *pos)
917 {
918 uint32_t graph_pos = commit_graph_position(item);
919 if (graph_pos != COMMIT_NOT_FROM_GRAPH) {
920 *pos = graph_pos;
921 return 1;
922 } else {
923 struct commit_graph *cur_g = g;
924 uint32_t lex_index;
925
926 while (cur_g && !bsearch_graph(cur_g, &(item->object.oid), &lex_index))
927 cur_g = cur_g->base_graph;
928
929 if (cur_g) {
930 *pos = lex_index + cur_g->num_commits_in_base;
931 return 1;
932 }
933
934 return 0;
935 }
936 }
937
938 static int parse_commit_in_graph_one(struct repository *r,
939 struct commit_graph *g,
940 struct commit *item)
941 {
942 uint32_t pos;
943
944 if (item->object.parsed)
945 return 1;
946
947 if (find_commit_in_graph(item, g, &pos))
948 return fill_commit_in_graph(r, item, g, pos);
949
950 return 0;
951 }
952
953 int parse_commit_in_graph(struct repository *r, struct commit *item)
954 {
955 static int checked_env = 0;
956
957 if (!checked_env &&
958 git_env_bool(GIT_TEST_COMMIT_GRAPH_DIE_ON_PARSE, 0))
959 die("dying as requested by the '%s' variable on commit-graph parse!",
960 GIT_TEST_COMMIT_GRAPH_DIE_ON_PARSE);
961 checked_env = 1;
962
963 if (!prepare_commit_graph(r))
964 return 0;
965 return parse_commit_in_graph_one(r, r->objects->commit_graph, item);
966 }
967
968 void load_commit_graph_info(struct repository *r, struct commit *item)
969 {
970 uint32_t pos;
971 if (!prepare_commit_graph(r))
972 return;
973 if (find_commit_in_graph(item, r->objects->commit_graph, &pos))
974 fill_commit_graph_info(item, r->objects->commit_graph, pos);
975 }
976
977 static struct tree *load_tree_for_commit(struct repository *r,
978 struct commit_graph *g,
979 struct commit *c)
980 {
981 struct object_id oid;
982 const unsigned char *commit_data;
983 uint32_t graph_pos = commit_graph_position(c);
984
985 while (graph_pos < g->num_commits_in_base)
986 g = g->base_graph;
987
988 commit_data = g->chunk_commit_data +
989 GRAPH_DATA_WIDTH * (graph_pos - g->num_commits_in_base);
990
991 hashcpy(oid.hash, commit_data);
992 set_commit_tree(c, lookup_tree(r, &oid));
993
994 return c->maybe_tree;
995 }
996
997 static struct tree *get_commit_tree_in_graph_one(struct repository *r,
998 struct commit_graph *g,
999 const struct commit *c)
1000 {
1001 if (c->maybe_tree)
1002 return c->maybe_tree;
1003 if (commit_graph_position(c) == COMMIT_NOT_FROM_GRAPH)
1004 BUG("get_commit_tree_in_graph_one called from non-commit-graph commit");
1005
1006 return load_tree_for_commit(r, g, (struct commit *)c);
1007 }
1008
1009 struct tree *get_commit_tree_in_graph(struct repository *r, const struct commit *c)
1010 {
1011 return get_commit_tree_in_graph_one(r, r->objects->commit_graph, c);
1012 }
1013
1014 struct packed_commit_list {
1015 struct commit **list;
1016 size_t nr;
1017 size_t alloc;
1018 };
1019
1020 struct write_commit_graph_context {
1021 struct repository *r;
1022 struct object_directory *odb;
1023 char *graph_name;
1024 struct oid_array oids;
1025 struct packed_commit_list commits;
1026 int num_extra_edges;
1027 int num_generation_data_overflows;
1028 unsigned long approx_nr_objects;
1029 struct progress *progress;
1030 int progress_done;
1031 uint64_t progress_cnt;
1032
1033 char *base_graph_name;
1034 int num_commit_graphs_before;
1035 int num_commit_graphs_after;
1036 char **commit_graph_filenames_before;
1037 char **commit_graph_filenames_after;
1038 char **commit_graph_hash_after;
1039 uint32_t new_num_commits_in_base;
1040 struct commit_graph *new_base_graph;
1041
1042 unsigned append:1,
1043 report_progress:1,
1044 split:1,
1045 changed_paths:1,
1046 order_by_pack:1,
1047 write_generation_data:1,
1048 trust_generation_numbers:1;
1049
1050 struct topo_level_slab *topo_levels;
1051 const struct commit_graph_opts *opts;
1052 size_t total_bloom_filter_data_size;
1053 const struct bloom_filter_settings *bloom_settings;
1054
1055 int count_bloom_filter_computed;
1056 int count_bloom_filter_not_computed;
1057 int count_bloom_filter_trunc_empty;
1058 int count_bloom_filter_trunc_large;
1059 };
1060
1061 static int write_graph_chunk_fanout(struct hashfile *f,
1062 struct write_commit_graph_context *ctx)
1063 {
1064 int i, count = 0;
1065 struct commit **list = ctx->commits.list;
1066
1067 /*
1068 * Write the first-level table (the list is sorted,
1069 * but we use a 256-entry lookup to be able to avoid
1070 * having to do eight extra binary search iterations).
1071 */
1072 for (i = 0; i < 256; i++) {
1073 while (count < ctx->commits.nr) {
1074 if ((*list)->object.oid.hash[0] != i)
1075 break;
1076 display_progress(ctx->progress, ++ctx->progress_cnt);
1077 count++;
1078 list++;
1079 }
1080
1081 hashwrite_be32(f, count);
1082 }
1083
1084 return 0;
1085 }
1086
1087 static int write_graph_chunk_oids(struct hashfile *f,
1088 struct write_commit_graph_context *ctx)
1089 {
1090 struct commit **list = ctx->commits.list;
1091 int count;
1092 for (count = 0; count < ctx->commits.nr; count++, list++) {
1093 display_progress(ctx->progress, ++ctx->progress_cnt);
1094 hashwrite(f, (*list)->object.oid.hash, the_hash_algo->rawsz);
1095 }
1096
1097 return 0;
1098 }
1099
1100 static const struct object_id *commit_to_oid(size_t index, const void *table)
1101 {
1102 const struct commit * const *commits = table;
1103 return &commits[index]->object.oid;
1104 }
1105
1106 static int write_graph_chunk_data(struct hashfile *f,
1107 struct write_commit_graph_context *ctx)
1108 {
1109 struct commit **list = ctx->commits.list;
1110 struct commit **last = ctx->commits.list + ctx->commits.nr;
1111 uint32_t num_extra_edges = 0;
1112
1113 while (list < last) {
1114 struct commit_list *parent;
1115 struct object_id *tree;
1116 int edge_value;
1117 uint32_t packedDate[2];
1118 display_progress(ctx->progress, ++ctx->progress_cnt);
1119
1120 if (repo_parse_commit_no_graph(ctx->r, *list))
1121 die(_("unable to parse commit %s"),
1122 oid_to_hex(&(*list)->object.oid));
1123 tree = get_commit_tree_oid(*list);
1124 hashwrite(f, tree->hash, the_hash_algo->rawsz);
1125
1126 parent = (*list)->parents;
1127
1128 if (!parent)
1129 edge_value = GRAPH_PARENT_NONE;
1130 else {
1131 edge_value = oid_pos(&parent->item->object.oid,
1132 ctx->commits.list,
1133 ctx->commits.nr,
1134 commit_to_oid);
1135
1136 if (edge_value >= 0)
1137 edge_value += ctx->new_num_commits_in_base;
1138 else if (ctx->new_base_graph) {
1139 uint32_t pos;
1140 if (find_commit_in_graph(parent->item,
1141 ctx->new_base_graph,
1142 &pos))
1143 edge_value = pos;
1144 }
1145
1146 if (edge_value < 0)
1147 BUG("missing parent %s for commit %s",
1148 oid_to_hex(&parent->item->object.oid),
1149 oid_to_hex(&(*list)->object.oid));
1150 }
1151
1152 hashwrite_be32(f, edge_value);
1153
1154 if (parent)
1155 parent = parent->next;
1156
1157 if (!parent)
1158 edge_value = GRAPH_PARENT_NONE;
1159 else if (parent->next)
1160 edge_value = GRAPH_EXTRA_EDGES_NEEDED | num_extra_edges;
1161 else {
1162 edge_value = oid_pos(&parent->item->object.oid,
1163 ctx->commits.list,
1164 ctx->commits.nr,
1165 commit_to_oid);
1166
1167 if (edge_value >= 0)
1168 edge_value += ctx->new_num_commits_in_base;
1169 else if (ctx->new_base_graph) {
1170 uint32_t pos;
1171 if (find_commit_in_graph(parent->item,
1172 ctx->new_base_graph,
1173 &pos))
1174 edge_value = pos;
1175 }
1176
1177 if (edge_value < 0)
1178 BUG("missing parent %s for commit %s",
1179 oid_to_hex(&parent->item->object.oid),
1180 oid_to_hex(&(*list)->object.oid));
1181 }
1182
1183 hashwrite_be32(f, edge_value);
1184
1185 if (edge_value & GRAPH_EXTRA_EDGES_NEEDED) {
1186 do {
1187 num_extra_edges++;
1188 parent = parent->next;
1189 } while (parent);
1190 }
1191
1192 if (sizeof((*list)->date) > 4)
1193 packedDate[0] = htonl(((*list)->date >> 32) & 0x3);
1194 else
1195 packedDate[0] = 0;
1196
1197 packedDate[0] |= htonl(*topo_level_slab_at(ctx->topo_levels, *list) << 2);
1198
1199 packedDate[1] = htonl((*list)->date);
1200 hashwrite(f, packedDate, 8);
1201
1202 list++;
1203 }
1204
1205 return 0;
1206 }
1207
1208 static int write_graph_chunk_generation_data(struct hashfile *f,
1209 struct write_commit_graph_context *ctx)
1210 {
1211 int i, num_generation_data_overflows = 0;
1212
1213 for (i = 0; i < ctx->commits.nr; i++) {
1214 struct commit *c = ctx->commits.list[i];
1215 timestamp_t offset;
1216 repo_parse_commit(ctx->r, c);
1217 offset = commit_graph_data_at(c)->generation - c->date;
1218 display_progress(ctx->progress, ++ctx->progress_cnt);
1219
1220 if (offset > GENERATION_NUMBER_V2_OFFSET_MAX) {
1221 offset = CORRECTED_COMMIT_DATE_OFFSET_OVERFLOW | num_generation_data_overflows;
1222 num_generation_data_overflows++;
1223 }
1224
1225 hashwrite_be32(f, offset);
1226 }
1227
1228 return 0;
1229 }
1230
1231 static int write_graph_chunk_generation_data_overflow(struct hashfile *f,
1232 struct write_commit_graph_context *ctx)
1233 {
1234 int i;
1235 for (i = 0; i < ctx->commits.nr; i++) {
1236 struct commit *c = ctx->commits.list[i];
1237 timestamp_t offset = commit_graph_data_at(c)->generation - c->date;
1238 display_progress(ctx->progress, ++ctx->progress_cnt);
1239
1240 if (offset > GENERATION_NUMBER_V2_OFFSET_MAX) {
1241 hashwrite_be32(f, offset >> 32);
1242 hashwrite_be32(f, (uint32_t) offset);
1243 }
1244 }
1245
1246 return 0;
1247 }
1248
1249 static int write_graph_chunk_extra_edges(struct hashfile *f,
1250 struct write_commit_graph_context *ctx)
1251 {
1252 struct commit **list = ctx->commits.list;
1253 struct commit **last = ctx->commits.list + ctx->commits.nr;
1254 struct commit_list *parent;
1255
1256 while (list < last) {
1257 int num_parents = 0;
1258
1259 display_progress(ctx->progress, ++ctx->progress_cnt);
1260
1261 for (parent = (*list)->parents; num_parents < 3 && parent;
1262 parent = parent->next)
1263 num_parents++;
1264
1265 if (num_parents <= 2) {
1266 list++;
1267 continue;
1268 }
1269
1270 /* Since num_parents > 2, this initializer is safe. */
1271 for (parent = (*list)->parents->next; parent; parent = parent->next) {
1272 int edge_value = oid_pos(&parent->item->object.oid,
1273 ctx->commits.list,
1274 ctx->commits.nr,
1275 commit_to_oid);
1276
1277 if (edge_value >= 0)
1278 edge_value += ctx->new_num_commits_in_base;
1279 else if (ctx->new_base_graph) {
1280 uint32_t pos;
1281 if (find_commit_in_graph(parent->item,
1282 ctx->new_base_graph,
1283 &pos))
1284 edge_value = pos;
1285 }
1286
1287 if (edge_value < 0)
1288 BUG("missing parent %s for commit %s",
1289 oid_to_hex(&parent->item->object.oid),
1290 oid_to_hex(&(*list)->object.oid));
1291 else if (!parent->next)
1292 edge_value |= GRAPH_LAST_EDGE;
1293
1294 hashwrite_be32(f, edge_value);
1295 }
1296
1297 list++;
1298 }
1299
1300 return 0;
1301 }
1302
1303 static int write_graph_chunk_bloom_indexes(struct hashfile *f,
1304 struct write_commit_graph_context *ctx)
1305 {
1306 struct commit **list = ctx->commits.list;
1307 struct commit **last = ctx->commits.list + ctx->commits.nr;
1308 uint32_t cur_pos = 0;
1309
1310 while (list < last) {
1311 struct bloom_filter *filter = get_bloom_filter(ctx->r, *list);
1312 size_t len = filter ? filter->len : 0;
1313 cur_pos += len;
1314 display_progress(ctx->progress, ++ctx->progress_cnt);
1315 hashwrite_be32(f, cur_pos);
1316 list++;
1317 }
1318
1319 return 0;
1320 }
1321
1322 static void trace2_bloom_filter_settings(struct write_commit_graph_context *ctx)
1323 {
1324 struct json_writer jw = JSON_WRITER_INIT;
1325
1326 jw_object_begin(&jw, 0);
1327 jw_object_intmax(&jw, "hash_version", ctx->bloom_settings->hash_version);
1328 jw_object_intmax(&jw, "num_hashes", ctx->bloom_settings->num_hashes);
1329 jw_object_intmax(&jw, "bits_per_entry", ctx->bloom_settings->bits_per_entry);
1330 jw_object_intmax(&jw, "max_changed_paths", ctx->bloom_settings->max_changed_paths);
1331 jw_end(&jw);
1332
1333 trace2_data_json("bloom", ctx->r, "settings", &jw);
1334
1335 jw_release(&jw);
1336 }
1337
1338 static int write_graph_chunk_bloom_data(struct hashfile *f,
1339 struct write_commit_graph_context *ctx)
1340 {
1341 struct commit **list = ctx->commits.list;
1342 struct commit **last = ctx->commits.list + ctx->commits.nr;
1343
1344 trace2_bloom_filter_settings(ctx);
1345
1346 hashwrite_be32(f, ctx->bloom_settings->hash_version);
1347 hashwrite_be32(f, ctx->bloom_settings->num_hashes);
1348 hashwrite_be32(f, ctx->bloom_settings->bits_per_entry);
1349
1350 while (list < last) {
1351 struct bloom_filter *filter = get_bloom_filter(ctx->r, *list);
1352 size_t len = filter ? filter->len : 0;
1353
1354 display_progress(ctx->progress, ++ctx->progress_cnt);
1355 if (len)
1356 hashwrite(f, filter->data, len * sizeof(unsigned char));
1357 list++;
1358 }
1359
1360 return 0;
1361 }
1362
1363 static int add_packed_commits(const struct object_id *oid,
1364 struct packed_git *pack,
1365 uint32_t pos,
1366 void *data)
1367 {
1368 struct write_commit_graph_context *ctx = (struct write_commit_graph_context*)data;
1369 enum object_type type;
1370 off_t offset = nth_packed_object_offset(pack, pos);
1371 struct object_info oi = OBJECT_INFO_INIT;
1372
1373 if (ctx->progress)
1374 display_progress(ctx->progress, ++ctx->progress_done);
1375
1376 oi.typep = &type;
1377 if (packed_object_info(ctx->r, pack, offset, &oi) < 0)
1378 die(_("unable to get type of object %s"), oid_to_hex(oid));
1379
1380 if (type != OBJ_COMMIT)
1381 return 0;
1382
1383 oid_array_append(&ctx->oids, oid);
1384 set_commit_pos(ctx->r, oid);
1385
1386 return 0;
1387 }
1388
1389 static void add_missing_parents(struct write_commit_graph_context *ctx, struct commit *commit)
1390 {
1391 struct commit_list *parent;
1392 for (parent = commit->parents; parent; parent = parent->next) {
1393 if (!(parent->item->object.flags & REACHABLE)) {
1394 oid_array_append(&ctx->oids, &parent->item->object.oid);
1395 parent->item->object.flags |= REACHABLE;
1396 }
1397 }
1398 }
1399
1400 static void close_reachable(struct write_commit_graph_context *ctx)
1401 {
1402 int i;
1403 struct commit *commit;
1404 enum commit_graph_split_flags flags = ctx->opts ?
1405 ctx->opts->split_flags : COMMIT_GRAPH_SPLIT_UNSPECIFIED;
1406
1407 if (ctx->report_progress)
1408 ctx->progress = start_delayed_progress(
1409 _("Loading known commits in commit graph"),
1410 ctx->oids.nr);
1411 for (i = 0; i < ctx->oids.nr; i++) {
1412 display_progress(ctx->progress, i + 1);
1413 commit = lookup_commit(ctx->r, &ctx->oids.oid[i]);
1414 if (commit)
1415 commit->object.flags |= REACHABLE;
1416 }
1417 stop_progress(&ctx->progress);
1418
1419 /*
1420 * As this loop runs, ctx->oids.nr may grow, but not more
1421 * than the number of missing commits in the reachable
1422 * closure.
1423 */
1424 if (ctx->report_progress)
1425 ctx->progress = start_delayed_progress(
1426 _("Expanding reachable commits in commit graph"),
1427 0);
1428 for (i = 0; i < ctx->oids.nr; i++) {
1429 display_progress(ctx->progress, i + 1);
1430 commit = lookup_commit(ctx->r, &ctx->oids.oid[i]);
1431
1432 if (!commit)
1433 continue;
1434 if (ctx->split) {
1435 if ((!repo_parse_commit(ctx->r, commit) &&
1436 commit_graph_position(commit) == COMMIT_NOT_FROM_GRAPH) ||
1437 flags == COMMIT_GRAPH_SPLIT_REPLACE)
1438 add_missing_parents(ctx, commit);
1439 } else if (!repo_parse_commit_no_graph(ctx->r, commit))
1440 add_missing_parents(ctx, commit);
1441 }
1442 stop_progress(&ctx->progress);
1443
1444 if (ctx->report_progress)
1445 ctx->progress = start_delayed_progress(
1446 _("Clearing commit marks in commit graph"),
1447 ctx->oids.nr);
1448 for (i = 0; i < ctx->oids.nr; i++) {
1449 display_progress(ctx->progress, i + 1);
1450 commit = lookup_commit(ctx->r, &ctx->oids.oid[i]);
1451
1452 if (commit)
1453 commit->object.flags &= ~REACHABLE;
1454 }
1455 stop_progress(&ctx->progress);
1456 }
1457
1458 static void compute_topological_levels(struct write_commit_graph_context *ctx)
1459 {
1460 int i;
1461 struct commit_list *list = NULL;
1462
1463 if (ctx->report_progress)
1464 ctx->progress = start_delayed_progress(
1465 _("Computing commit graph topological levels"),
1466 ctx->commits.nr);
1467 for (i = 0; i < ctx->commits.nr; i++) {
1468 struct commit *c = ctx->commits.list[i];
1469 uint32_t level;
1470
1471 repo_parse_commit(ctx->r, c);
1472 level = *topo_level_slab_at(ctx->topo_levels, c);
1473
1474 display_progress(ctx->progress, i + 1);
1475 if (level != GENERATION_NUMBER_ZERO)
1476 continue;
1477
1478 commit_list_insert(c, &list);
1479 while (list) {
1480 struct commit *current = list->item;
1481 struct commit_list *parent;
1482 int all_parents_computed = 1;
1483 uint32_t max_level = 0;
1484
1485 for (parent = current->parents; parent; parent = parent->next) {
1486 repo_parse_commit(ctx->r, parent->item);
1487 level = *topo_level_slab_at(ctx->topo_levels, parent->item);
1488
1489 if (level == GENERATION_NUMBER_ZERO) {
1490 all_parents_computed = 0;
1491 commit_list_insert(parent->item, &list);
1492 break;
1493 }
1494
1495 if (level > max_level)
1496 max_level = level;
1497 }
1498
1499 if (all_parents_computed) {
1500 pop_commit(&list);
1501
1502 if (max_level > GENERATION_NUMBER_V1_MAX - 1)
1503 max_level = GENERATION_NUMBER_V1_MAX - 1;
1504 *topo_level_slab_at(ctx->topo_levels, current) = max_level + 1;
1505 }
1506 }
1507 }
1508 stop_progress(&ctx->progress);
1509 }
1510
1511 static void compute_generation_numbers(struct write_commit_graph_context *ctx)
1512 {
1513 int i;
1514 struct commit_list *list = NULL;
1515
1516 if (ctx->report_progress)
1517 ctx->progress = start_delayed_progress(
1518 _("Computing commit graph generation numbers"),
1519 ctx->commits.nr);
1520
1521 if (!ctx->trust_generation_numbers) {
1522 for (i = 0; i < ctx->commits.nr; i++) {
1523 struct commit *c = ctx->commits.list[i];
1524 repo_parse_commit(ctx->r, c);
1525 commit_graph_data_at(c)->generation = GENERATION_NUMBER_ZERO;
1526 }
1527 }
1528
1529 for (i = 0; i < ctx->commits.nr; i++) {
1530 struct commit *c = ctx->commits.list[i];
1531 timestamp_t corrected_commit_date;
1532
1533 repo_parse_commit(ctx->r, c);
1534 corrected_commit_date = commit_graph_data_at(c)->generation;
1535
1536 display_progress(ctx->progress, i + 1);
1537 if (corrected_commit_date != GENERATION_NUMBER_ZERO)
1538 continue;
1539
1540 commit_list_insert(c, &list);
1541 while (list) {
1542 struct commit *current = list->item;
1543 struct commit_list *parent;
1544 int all_parents_computed = 1;
1545 timestamp_t max_corrected_commit_date = 0;
1546
1547 for (parent = current->parents; parent; parent = parent->next) {
1548 repo_parse_commit(ctx->r, parent->item);
1549 corrected_commit_date = commit_graph_data_at(parent->item)->generation;
1550
1551 if (corrected_commit_date == GENERATION_NUMBER_ZERO) {
1552 all_parents_computed = 0;
1553 commit_list_insert(parent->item, &list);
1554 break;
1555 }
1556
1557 if (corrected_commit_date > max_corrected_commit_date)
1558 max_corrected_commit_date = corrected_commit_date;
1559 }
1560
1561 if (all_parents_computed) {
1562 pop_commit(&list);
1563
1564 if (current->date && current->date > max_corrected_commit_date)
1565 max_corrected_commit_date = current->date - 1;
1566 commit_graph_data_at(current)->generation = max_corrected_commit_date + 1;
1567
1568 if (commit_graph_data_at(current)->generation - current->date > GENERATION_NUMBER_V2_OFFSET_MAX)
1569 ctx->num_generation_data_overflows++;
1570 }
1571 }
1572 }
1573 stop_progress(&ctx->progress);
1574 }
1575
1576 static void trace2_bloom_filter_write_statistics(struct write_commit_graph_context *ctx)
1577 {
1578 trace2_data_intmax("commit-graph", ctx->r, "filter-computed",
1579 ctx->count_bloom_filter_computed);
1580 trace2_data_intmax("commit-graph", ctx->r, "filter-not-computed",
1581 ctx->count_bloom_filter_not_computed);
1582 trace2_data_intmax("commit-graph", ctx->r, "filter-trunc-empty",
1583 ctx->count_bloom_filter_trunc_empty);
1584 trace2_data_intmax("commit-graph", ctx->r, "filter-trunc-large",
1585 ctx->count_bloom_filter_trunc_large);
1586 }
1587
1588 static void compute_bloom_filters(struct write_commit_graph_context *ctx)
1589 {
1590 int i;
1591 struct progress *progress = NULL;
1592 struct commit **sorted_commits;
1593 int max_new_filters;
1594
1595 init_bloom_filters();
1596
1597 if (ctx->report_progress)
1598 progress = start_delayed_progress(
1599 _("Computing commit changed paths Bloom filters"),
1600 ctx->commits.nr);
1601
1602 ALLOC_ARRAY(sorted_commits, ctx->commits.nr);
1603 COPY_ARRAY(sorted_commits, ctx->commits.list, ctx->commits.nr);
1604
1605 if (ctx->order_by_pack)
1606 QSORT(sorted_commits, ctx->commits.nr, commit_pos_cmp);
1607 else
1608 QSORT(sorted_commits, ctx->commits.nr, commit_gen_cmp);
1609
1610 max_new_filters = ctx->opts && ctx->opts->max_new_filters >= 0 ?
1611 ctx->opts->max_new_filters : ctx->commits.nr;
1612
1613 for (i = 0; i < ctx->commits.nr; i++) {
1614 enum bloom_filter_computed computed = 0;
1615 struct commit *c = sorted_commits[i];
1616 struct bloom_filter *filter = get_or_compute_bloom_filter(
1617 ctx->r,
1618 c,
1619 ctx->count_bloom_filter_computed < max_new_filters,
1620 ctx->bloom_settings,
1621 &computed);
1622 if (computed & BLOOM_COMPUTED) {
1623 ctx->count_bloom_filter_computed++;
1624 if (computed & BLOOM_TRUNC_EMPTY)
1625 ctx->count_bloom_filter_trunc_empty++;
1626 if (computed & BLOOM_TRUNC_LARGE)
1627 ctx->count_bloom_filter_trunc_large++;
1628 } else if (computed & BLOOM_NOT_COMPUTED)
1629 ctx->count_bloom_filter_not_computed++;
1630 ctx->total_bloom_filter_data_size += filter
1631 ? sizeof(unsigned char) * filter->len : 0;
1632 display_progress(progress, i + 1);
1633 }
1634
1635 if (trace2_is_enabled())
1636 trace2_bloom_filter_write_statistics(ctx);
1637
1638 free(sorted_commits);
1639 stop_progress(&progress);
1640 }
1641
1642 struct refs_cb_data {
1643 struct oidset *commits;
1644 struct progress *progress;
1645 };
1646
1647 static int add_ref_to_set(const char *refname,
1648 const struct object_id *oid,
1649 int flags, void *cb_data)
1650 {
1651 struct object_id peeled;
1652 struct refs_cb_data *data = (struct refs_cb_data *)cb_data;
1653
1654 if (!peel_iterated_oid(oid, &peeled))
1655 oid = &peeled;
1656 if (oid_object_info(the_repository, oid, NULL) == OBJ_COMMIT)
1657 oidset_insert(data->commits, oid);
1658
1659 display_progress(data->progress, oidset_size(data->commits));
1660
1661 return 0;
1662 }
1663
1664 int write_commit_graph_reachable(struct object_directory *odb,
1665 enum commit_graph_write_flags flags,
1666 const struct commit_graph_opts *opts)
1667 {
1668 struct oidset commits = OIDSET_INIT;
1669 struct refs_cb_data data;
1670 int result;
1671
1672 memset(&data, 0, sizeof(data));
1673 data.commits = &commits;
1674 if (flags & COMMIT_GRAPH_WRITE_PROGRESS)
1675 data.progress = start_delayed_progress(
1676 _("Collecting referenced commits"), 0);
1677
1678 for_each_ref(add_ref_to_set, &data);
1679
1680 stop_progress(&data.progress);
1681
1682 result = write_commit_graph(odb, NULL, &commits,
1683 flags, opts);
1684
1685 oidset_clear(&commits);
1686 return result;
1687 }
1688
1689 static int fill_oids_from_packs(struct write_commit_graph_context *ctx,
1690 struct string_list *pack_indexes)
1691 {
1692 uint32_t i;
1693 struct strbuf progress_title = STRBUF_INIT;
1694 struct strbuf packname = STRBUF_INIT;
1695 int dirlen;
1696
1697 strbuf_addf(&packname, "%s/pack/", ctx->odb->path);
1698 dirlen = packname.len;
1699 if (ctx->report_progress) {
1700 strbuf_addf(&progress_title,
1701 Q_("Finding commits for commit graph in %d pack",
1702 "Finding commits for commit graph in %d packs",
1703 pack_indexes->nr),
1704 pack_indexes->nr);
1705 ctx->progress = start_delayed_progress(progress_title.buf, 0);
1706 ctx->progress_done = 0;
1707 }
1708 for (i = 0; i < pack_indexes->nr; i++) {
1709 struct packed_git *p;
1710 strbuf_setlen(&packname, dirlen);
1711 strbuf_addstr(&packname, pack_indexes->items[i].string);
1712 p = add_packed_git(packname.buf, packname.len, 1);
1713 if (!p) {
1714 error(_("error adding pack %s"), packname.buf);
1715 return -1;
1716 }
1717 if (open_pack_index(p)) {
1718 error(_("error opening index for %s"), packname.buf);
1719 return -1;
1720 }
1721 for_each_object_in_pack(p, add_packed_commits, ctx,
1722 FOR_EACH_OBJECT_PACK_ORDER);
1723 close_pack(p);
1724 free(p);
1725 }
1726
1727 stop_progress(&ctx->progress);
1728 strbuf_release(&progress_title);
1729 strbuf_release(&packname);
1730
1731 return 0;
1732 }
1733
1734 static int fill_oids_from_commits(struct write_commit_graph_context *ctx,
1735 struct oidset *commits)
1736 {
1737 struct oidset_iter iter;
1738 struct object_id *oid;
1739
1740 if (!oidset_size(commits))
1741 return 0;
1742
1743 oidset_iter_init(commits, &iter);
1744 while ((oid = oidset_iter_next(&iter))) {
1745 oid_array_append(&ctx->oids, oid);
1746 }
1747
1748 return 0;
1749 }
1750
1751 static void fill_oids_from_all_packs(struct write_commit_graph_context *ctx)
1752 {
1753 if (ctx->report_progress)
1754 ctx->progress = start_delayed_progress(
1755 _("Finding commits for commit graph among packed objects"),
1756 ctx->approx_nr_objects);
1757 for_each_packed_object(add_packed_commits, ctx,
1758 FOR_EACH_OBJECT_PACK_ORDER);
1759 if (ctx->progress_done < ctx->approx_nr_objects)
1760 display_progress(ctx->progress, ctx->approx_nr_objects);
1761 stop_progress(&ctx->progress);
1762 }
1763
1764 static void copy_oids_to_commits(struct write_commit_graph_context *ctx)
1765 {
1766 uint32_t i;
1767 enum commit_graph_split_flags flags = ctx->opts ?
1768 ctx->opts->split_flags : COMMIT_GRAPH_SPLIT_UNSPECIFIED;
1769
1770 ctx->num_extra_edges = 0;
1771 if (ctx->report_progress)
1772 ctx->progress = start_delayed_progress(
1773 _("Finding extra edges in commit graph"),
1774 ctx->oids.nr);
1775 oid_array_sort(&ctx->oids);
1776 for (i = 0; i < ctx->oids.nr; i = oid_array_next_unique(&ctx->oids, i)) {
1777 unsigned int num_parents;
1778
1779 display_progress(ctx->progress, i + 1);
1780
1781 ALLOC_GROW(ctx->commits.list, ctx->commits.nr + 1, ctx->commits.alloc);
1782 ctx->commits.list[ctx->commits.nr] = lookup_commit(ctx->r, &ctx->oids.oid[i]);
1783
1784 if (ctx->split && flags != COMMIT_GRAPH_SPLIT_REPLACE &&
1785 commit_graph_position(ctx->commits.list[ctx->commits.nr]) != COMMIT_NOT_FROM_GRAPH)
1786 continue;
1787
1788 if (ctx->split && flags == COMMIT_GRAPH_SPLIT_REPLACE)
1789 repo_parse_commit(ctx->r, ctx->commits.list[ctx->commits.nr]);
1790 else
1791 repo_parse_commit_no_graph(ctx->r, ctx->commits.list[ctx->commits.nr]);
1792
1793 num_parents = commit_list_count(ctx->commits.list[ctx->commits.nr]->parents);
1794 if (num_parents > 2)
1795 ctx->num_extra_edges += num_parents - 1;
1796
1797 ctx->commits.nr++;
1798 }
1799 stop_progress(&ctx->progress);
1800 }
1801
1802 static int write_graph_chunk_base_1(struct hashfile *f,
1803 struct commit_graph *g)
1804 {
1805 int num = 0;
1806
1807 if (!g)
1808 return 0;
1809
1810 num = write_graph_chunk_base_1(f, g->base_graph);
1811 hashwrite(f, g->oid.hash, the_hash_algo->rawsz);
1812 return num + 1;
1813 }
1814
1815 static int write_graph_chunk_base(struct hashfile *f,
1816 struct write_commit_graph_context *ctx)
1817 {
1818 int num = write_graph_chunk_base_1(f, ctx->new_base_graph);
1819
1820 if (num != ctx->num_commit_graphs_after - 1) {
1821 error(_("failed to write correct number of base graph ids"));
1822 return -1;
1823 }
1824
1825 return 0;
1826 }
1827
1828 typedef int (*chunk_write_fn)(struct hashfile *f,
1829 struct write_commit_graph_context *ctx);
1830
1831 struct chunk_info {
1832 uint32_t id;
1833 uint64_t size;
1834 chunk_write_fn write_fn;
1835 };
1836
1837 static int write_commit_graph_file(struct write_commit_graph_context *ctx)
1838 {
1839 uint32_t i;
1840 int fd;
1841 struct hashfile *f;
1842 struct lock_file lk = LOCK_INIT;
1843 struct chunk_info chunks[MAX_NUM_CHUNKS + 1];
1844 const unsigned hashsz = the_hash_algo->rawsz;
1845 struct strbuf progress_title = STRBUF_INIT;
1846 int num_chunks = 3;
1847 uint64_t chunk_offset;
1848 struct object_id file_hash;
1849
1850 if (ctx->split) {
1851 struct strbuf tmp_file = STRBUF_INIT;
1852
1853 strbuf_addf(&tmp_file,
1854 "%s/info/commit-graphs/tmp_graph_XXXXXX",
1855 ctx->odb->path);
1856 ctx->graph_name = strbuf_detach(&tmp_file, NULL);
1857 } else {
1858 ctx->graph_name = get_commit_graph_filename(ctx->odb);
1859 }
1860
1861 if (safe_create_leading_directories(ctx->graph_name)) {
1862 UNLEAK(ctx->graph_name);
1863 error(_("unable to create leading directories of %s"),
1864 ctx->graph_name);
1865 return -1;
1866 }
1867
1868 if (ctx->split) {
1869 char *lock_name = get_commit_graph_chain_filename(ctx->odb);
1870
1871 hold_lock_file_for_update_mode(&lk, lock_name,
1872 LOCK_DIE_ON_ERROR, 0444);
1873
1874 fd = git_mkstemp_mode(ctx->graph_name, 0444);
1875 if (fd < 0) {
1876 error(_("unable to create temporary graph layer"));
1877 return -1;
1878 }
1879
1880 if (adjust_shared_perm(ctx->graph_name)) {
1881 error(_("unable to adjust shared permissions for '%s'"),
1882 ctx->graph_name);
1883 return -1;
1884 }
1885
1886 f = hashfd(fd, ctx->graph_name);
1887 } else {
1888 hold_lock_file_for_update_mode(&lk, ctx->graph_name,
1889 LOCK_DIE_ON_ERROR, 0444);
1890 fd = get_lock_file_fd(&lk);
1891 f = hashfd(fd, get_lock_file_path(&lk));
1892 }
1893
1894 chunks[0].id = GRAPH_CHUNKID_OIDFANOUT;
1895 chunks[0].size = GRAPH_FANOUT_SIZE;
1896 chunks[0].write_fn = write_graph_chunk_fanout;
1897 chunks[1].id = GRAPH_CHUNKID_OIDLOOKUP;
1898 chunks[1].size = hashsz * ctx->commits.nr;
1899 chunks[1].write_fn = write_graph_chunk_oids;
1900 chunks[2].id = GRAPH_CHUNKID_DATA;
1901 chunks[2].size = (hashsz + 16) * ctx->commits.nr;
1902 chunks[2].write_fn = write_graph_chunk_data;
1903
1904 if (git_env_bool(GIT_TEST_COMMIT_GRAPH_NO_GDAT, 0))
1905 ctx->write_generation_data = 0;
1906 if (ctx->write_generation_data) {
1907 chunks[num_chunks].id = GRAPH_CHUNKID_GENERATION_DATA;
1908 chunks[num_chunks].size = sizeof(uint32_t) * ctx->commits.nr;
1909 chunks[num_chunks].write_fn = write_graph_chunk_generation_data;
1910 num_chunks++;
1911 }
1912 if (ctx->num_generation_data_overflows) {
1913 chunks[num_chunks].id = GRAPH_CHUNKID_GENERATION_DATA_OVERFLOW;
1914 chunks[num_chunks].size = sizeof(timestamp_t) * ctx->num_generation_data_overflows;
1915 chunks[num_chunks].write_fn = write_graph_chunk_generation_data_overflow;
1916 num_chunks++;
1917 }
1918 if (ctx->num_extra_edges) {
1919 chunks[num_chunks].id = GRAPH_CHUNKID_EXTRAEDGES;
1920 chunks[num_chunks].size = 4 * ctx->num_extra_edges;
1921 chunks[num_chunks].write_fn = write_graph_chunk_extra_edges;
1922 num_chunks++;
1923 }
1924 if (ctx->changed_paths) {
1925 chunks[num_chunks].id = GRAPH_CHUNKID_BLOOMINDEXES;
1926 chunks[num_chunks].size = sizeof(uint32_t) * ctx->commits.nr;
1927 chunks[num_chunks].write_fn = write_graph_chunk_bloom_indexes;
1928 num_chunks++;
1929 chunks[num_chunks].id = GRAPH_CHUNKID_BLOOMDATA;
1930 chunks[num_chunks].size = sizeof(uint32_t) * 3
1931 + ctx->total_bloom_filter_data_size;
1932 chunks[num_chunks].write_fn = write_graph_chunk_bloom_data;
1933 num_chunks++;
1934 }
1935 if (ctx->num_commit_graphs_after > 1) {
1936 chunks[num_chunks].id = GRAPH_CHUNKID_BASE;
1937 chunks[num_chunks].size = hashsz * (ctx->num_commit_graphs_after - 1);
1938 chunks[num_chunks].write_fn = write_graph_chunk_base;
1939 num_chunks++;
1940 }
1941
1942 chunks[num_chunks].id = 0;
1943 chunks[num_chunks].size = 0;
1944
1945 hashwrite_be32(f, GRAPH_SIGNATURE);
1946
1947 hashwrite_u8(f, GRAPH_VERSION);
1948 hashwrite_u8(f, oid_version());
1949 hashwrite_u8(f, num_chunks);
1950 hashwrite_u8(f, ctx->num_commit_graphs_after - 1);
1951
1952 chunk_offset = 8 + (num_chunks + 1) * GRAPH_CHUNKLOOKUP_WIDTH;
1953 for (i = 0; i <= num_chunks; i++) {
1954 uint32_t chunk_write[3];
1955
1956 chunk_write[0] = htonl(chunks[i].id);
1957 chunk_write[1] = htonl(chunk_offset >> 32);
1958 chunk_write[2] = htonl(chunk_offset & 0xffffffff);
1959 hashwrite(f, chunk_write, 12);
1960
1961 chunk_offset += chunks[i].size;
1962 }
1963
1964 if (ctx->report_progress) {
1965 strbuf_addf(&progress_title,
1966 Q_("Writing out commit graph in %d pass",
1967 "Writing out commit graph in %d passes",
1968 num_chunks),
1969 num_chunks);
1970 ctx->progress = start_delayed_progress(
1971 progress_title.buf,
1972 num_chunks * ctx->commits.nr);
1973 }
1974
1975 for (i = 0; i < num_chunks; i++) {
1976 uint64_t start_offset = f->total + f->offset;
1977
1978 if (chunks[i].write_fn(f, ctx))
1979 return -1;
1980
1981 if (f->total + f->offset != start_offset + chunks[i].size)
1982 BUG("expected to write %"PRId64" bytes to chunk %"PRIx32", but wrote %"PRId64" instead",
1983 chunks[i].size, chunks[i].id,
1984 f->total + f->offset - start_offset);
1985 }
1986
1987 stop_progress(&ctx->progress);
1988 strbuf_release(&progress_title);
1989
1990 if (ctx->split && ctx->base_graph_name && ctx->num_commit_graphs_after > 1) {
1991 char *new_base_hash = xstrdup(oid_to_hex(&ctx->new_base_graph->oid));
1992 char *new_base_name = get_split_graph_filename(ctx->new_base_graph->odb, new_base_hash);
1993
1994 free(ctx->commit_graph_filenames_after[ctx->num_commit_graphs_after - 2]);
1995 free(ctx->commit_graph_hash_after[ctx->num_commit_graphs_after - 2]);
1996 ctx->commit_graph_filenames_after[ctx->num_commit_graphs_after - 2] = new_base_name;
1997 ctx->commit_graph_hash_after[ctx->num_commit_graphs_after - 2] = new_base_hash;
1998 }
1999
2000 close_commit_graph(ctx->r->objects);
2001 finalize_hashfile(f, file_hash.hash, CSUM_HASH_IN_STREAM | CSUM_FSYNC);
2002
2003 if (ctx->split) {
2004 FILE *chainf = fdopen_lock_file(&lk, "w");
2005 char *final_graph_name;
2006 int result;
2007
2008 close(fd);
2009
2010 if (!chainf) {
2011 error(_("unable to open commit-graph chain file"));
2012 return -1;
2013 }
2014
2015 if (ctx->base_graph_name) {
2016 const char *dest;
2017 int idx = ctx->num_commit_graphs_after - 1;
2018 if (ctx->num_commit_graphs_after > 1)
2019 idx--;
2020
2021 dest = ctx->commit_graph_filenames_after[idx];
2022
2023 if (strcmp(ctx->base_graph_name, dest)) {
2024 result = rename(ctx->base_graph_name, dest);
2025
2026 if (result) {
2027 error(_("failed to rename base commit-graph file"));
2028 return -1;
2029 }
2030 }
2031 } else {
2032 char *graph_name = get_commit_graph_filename(ctx->odb);
2033 unlink(graph_name);
2034 }
2035
2036 ctx->commit_graph_hash_after[ctx->num_commit_graphs_after - 1] = xstrdup(oid_to_hex(&file_hash));
2037 final_graph_name = get_split_graph_filename(ctx->odb,
2038 ctx->commit_graph_hash_after[ctx->num_commit_graphs_after - 1]);
2039 ctx->commit_graph_filenames_after[ctx->num_commit_graphs_after - 1] = final_graph_name;
2040
2041 result = rename(ctx->graph_name, final_graph_name);
2042
2043 for (i = 0; i < ctx->num_commit_graphs_after; i++)
2044 fprintf(get_lock_file_fp(&lk), "%s\n", ctx->commit_graph_hash_after[i]);
2045
2046 if (result) {
2047 error(_("failed to rename temporary commit-graph file"));
2048 return -1;
2049 }
2050 }
2051
2052 commit_lock_file(&lk);
2053
2054 return 0;
2055 }
2056
2057 static void split_graph_merge_strategy(struct write_commit_graph_context *ctx)
2058 {
2059 struct commit_graph *g;
2060 uint32_t num_commits;
2061 enum commit_graph_split_flags flags = COMMIT_GRAPH_SPLIT_UNSPECIFIED;
2062 uint32_t i;
2063
2064 int max_commits = 0;
2065 int size_mult = 2;
2066
2067 if (ctx->opts) {
2068 max_commits = ctx->opts->max_commits;
2069
2070 if (ctx->opts->size_multiple)
2071 size_mult = ctx->opts->size_multiple;
2072
2073 flags = ctx->opts->split_flags;
2074 }
2075
2076 g = ctx->r->objects->commit_graph;
2077 num_commits = ctx->commits.nr;
2078 if (flags == COMMIT_GRAPH_SPLIT_REPLACE)
2079 ctx->num_commit_graphs_after = 1;
2080 else
2081 ctx->num_commit_graphs_after = ctx->num_commit_graphs_before + 1;
2082
2083 if (flags != COMMIT_GRAPH_SPLIT_MERGE_PROHIBITED &&
2084 flags != COMMIT_GRAPH_SPLIT_REPLACE) {
2085 while (g && (g->num_commits <= size_mult * num_commits ||
2086 (max_commits && num_commits > max_commits))) {
2087 if (g->odb != ctx->odb)
2088 break;
2089
2090 num_commits += g->num_commits;
2091 g = g->base_graph;
2092
2093 ctx->num_commit_graphs_after--;
2094 }
2095 }
2096
2097 if (flags != COMMIT_GRAPH_SPLIT_REPLACE)
2098 ctx->new_base_graph = g;
2099 else if (ctx->num_commit_graphs_after != 1)
2100 BUG("split_graph_merge_strategy: num_commit_graphs_after "
2101 "should be 1 with --split=replace");
2102
2103 if (ctx->num_commit_graphs_after == 2) {
2104 char *old_graph_name = get_commit_graph_filename(g->odb);
2105
2106 if (!strcmp(g->filename, old_graph_name) &&
2107 g->odb != ctx->odb) {
2108 ctx->num_commit_graphs_after = 1;
2109 ctx->new_base_graph = NULL;
2110 }
2111
2112 free(old_graph_name);
2113 }
2114
2115 CALLOC_ARRAY(ctx->commit_graph_filenames_after, ctx->num_commit_graphs_after);
2116 CALLOC_ARRAY(ctx->commit_graph_hash_after, ctx->num_commit_graphs_after);
2117
2118 for (i = 0; i < ctx->num_commit_graphs_after &&
2119 i < ctx->num_commit_graphs_before; i++)
2120 ctx->commit_graph_filenames_after[i] = xstrdup(ctx->commit_graph_filenames_before[i]);
2121
2122 i = ctx->num_commit_graphs_before - 1;
2123 g = ctx->r->objects->commit_graph;
2124
2125 while (g) {
2126 if (i < ctx->num_commit_graphs_after)
2127 ctx->commit_graph_hash_after[i] = xstrdup(oid_to_hex(&g->oid));
2128
2129 /*
2130 * If the topmost remaining layer has generation data chunk, the
2131 * resultant layer also has generation data chunk.
2132 */
2133 if (i == ctx->num_commit_graphs_after - 2)
2134 ctx->write_generation_data = !!g->chunk_generation_data;
2135
2136 i--;
2137 g = g->base_graph;
2138 }
2139 }
2140
2141 static void merge_commit_graph(struct write_commit_graph_context *ctx,
2142 struct commit_graph *g)
2143 {
2144 uint32_t i;
2145 uint32_t offset = g->num_commits_in_base;
2146
2147 ALLOC_GROW(ctx->commits.list, ctx->commits.nr + g->num_commits, ctx->commits.alloc);
2148
2149 for (i = 0; i < g->num_commits; i++) {
2150 struct object_id oid;
2151 struct commit *result;
2152
2153 display_progress(ctx->progress, i + 1);
2154
2155 load_oid_from_graph(g, i + offset, &oid);
2156
2157 /* only add commits if they still exist in the repo */
2158 result = lookup_commit_reference_gently(ctx->r, &oid, 1);
2159
2160 if (result) {
2161 ctx->commits.list[ctx->commits.nr] = result;
2162 ctx->commits.nr++;
2163 }
2164 }
2165 }
2166
2167 static int commit_compare(const void *_a, const void *_b)
2168 {
2169 const struct commit *a = *(const struct commit **)_a;
2170 const struct commit *b = *(const struct commit **)_b;
2171 return oidcmp(&a->object.oid, &b->object.oid);
2172 }
2173
2174 static void sort_and_scan_merged_commits(struct write_commit_graph_context *ctx)
2175 {
2176 uint32_t i, dedup_i = 0;
2177
2178 if (ctx->report_progress)
2179 ctx->progress = start_delayed_progress(
2180 _("Scanning merged commits"),
2181 ctx->commits.nr);
2182
2183 QSORT(ctx->commits.list, ctx->commits.nr, commit_compare);
2184
2185 ctx->num_extra_edges = 0;
2186 for (i = 0; i < ctx->commits.nr; i++) {
2187 display_progress(ctx->progress, i);
2188
2189 if (i && oideq(&ctx->commits.list[i - 1]->object.oid,
2190 &ctx->commits.list[i]->object.oid)) {
2191 /*
2192 * Silently ignore duplicates. These were likely
2193 * created due to a commit appearing in multiple
2194 * layers of the chain, which is unexpected but
2195 * not invalid. We should make sure there is a
2196 * unique copy in the new layer.
2197 */
2198 } else {
2199 unsigned int num_parents;
2200
2201 ctx->commits.list[dedup_i] = ctx->commits.list[i];
2202 dedup_i++;
2203
2204 num_parents = commit_list_count(ctx->commits.list[i]->parents);
2205 if (num_parents > 2)
2206 ctx->num_extra_edges += num_parents - 1;
2207 }
2208 }
2209
2210 ctx->commits.nr = dedup_i;
2211
2212 stop_progress(&ctx->progress);
2213 }
2214
2215 static void merge_commit_graphs(struct write_commit_graph_context *ctx)
2216 {
2217 struct commit_graph *g = ctx->r->objects->commit_graph;
2218 uint32_t current_graph_number = ctx->num_commit_graphs_before;
2219
2220 while (g && current_graph_number >= ctx->num_commit_graphs_after) {
2221 current_graph_number--;
2222
2223 if (ctx->report_progress)
2224 ctx->progress = start_delayed_progress(_("Merging commit-graph"), 0);
2225
2226 merge_commit_graph(ctx, g);
2227 stop_progress(&ctx->progress);
2228
2229 g = g->base_graph;
2230 }
2231
2232 if (g) {
2233 ctx->new_base_graph = g;
2234 ctx->new_num_commits_in_base = g->num_commits + g->num_commits_in_base;
2235 }
2236
2237 if (ctx->new_base_graph)
2238 ctx->base_graph_name = xstrdup(ctx->new_base_graph->filename);
2239
2240 sort_and_scan_merged_commits(ctx);
2241 }
2242
2243 static void mark_commit_graphs(struct write_commit_graph_context *ctx)
2244 {
2245 uint32_t i;
2246 time_t now = time(NULL);
2247
2248 for (i = ctx->num_commit_graphs_after - 1; i < ctx->num_commit_graphs_before; i++) {
2249 struct stat st;
2250 struct utimbuf updated_time;
2251
2252 stat(ctx->commit_graph_filenames_before[i], &st);
2253
2254 updated_time.actime = st.st_atime;
2255 updated_time.modtime = now;
2256 utime(ctx->commit_graph_filenames_before[i], &updated_time);
2257 }
2258 }
2259
2260 static void expire_commit_graphs(struct write_commit_graph_context *ctx)
2261 {
2262 struct strbuf path = STRBUF_INIT;
2263 DIR *dir;
2264 struct dirent *de;
2265 size_t dirnamelen;
2266 timestamp_t expire_time = time(NULL);
2267
2268 if (ctx->opts && ctx->opts->expire_time)
2269 expire_time = ctx->opts->expire_time;
2270 if (!ctx->split) {
2271 char *chain_file_name = get_commit_graph_chain_filename(ctx->odb);
2272 unlink(chain_file_name);
2273 free(chain_file_name);
2274 ctx->num_commit_graphs_after = 0;
2275 }
2276
2277 strbuf_addstr(&path, ctx->odb->path);
2278 strbuf_addstr(&path, "/info/commit-graphs");
2279 dir = opendir(path.buf);
2280
2281 if (!dir)
2282 goto out;
2283
2284 strbuf_addch(&path, '/');
2285 dirnamelen = path.len;
2286 while ((de = readdir(dir)) != NULL) {
2287 struct stat st;
2288 uint32_t i, found = 0;
2289
2290 strbuf_setlen(&path, dirnamelen);
2291 strbuf_addstr(&path, de->d_name);
2292
2293 stat(path.buf, &st);
2294
2295 if (st.st_mtime > expire_time)
2296 continue;
2297 if (path.len < 6 || strcmp(path.buf + path.len - 6, ".graph"))
2298 continue;
2299
2300 for (i = 0; i < ctx->num_commit_graphs_after; i++) {
2301 if (!strcmp(ctx->commit_graph_filenames_after[i],
2302 path.buf)) {
2303 found = 1;
2304 break;
2305 }
2306 }
2307
2308 if (!found)
2309 unlink(path.buf);
2310 }
2311
2312 out:
2313 strbuf_release(&path);
2314 }
2315
2316 int write_commit_graph(struct object_directory *odb,
2317 struct string_list *pack_indexes,
2318 struct oidset *commits,
2319 enum commit_graph_write_flags flags,
2320 const struct commit_graph_opts *opts)
2321 {
2322 struct write_commit_graph_context *ctx;
2323 uint32_t i;
2324 int res = 0;
2325 int replace = 0;
2326 struct bloom_filter_settings bloom_settings = DEFAULT_BLOOM_FILTER_SETTINGS;
2327 struct topo_level_slab topo_levels;
2328
2329 prepare_repo_settings(the_repository);
2330 if (!the_repository->settings.core_commit_graph) {
2331 warning(_("attempting to write a commit-graph, but 'core.commitGraph' is disabled"));
2332 return 0;
2333 }
2334 if (!commit_graph_compatible(the_repository))
2335 return 0;
2336
2337 ctx = xcalloc(1, sizeof(struct write_commit_graph_context));
2338 ctx->r = the_repository;
2339 ctx->odb = odb;
2340 ctx->append = flags & COMMIT_GRAPH_WRITE_APPEND ? 1 : 0;
2341 ctx->report_progress = flags & COMMIT_GRAPH_WRITE_PROGRESS ? 1 : 0;
2342 ctx->split = flags & COMMIT_GRAPH_WRITE_SPLIT ? 1 : 0;
2343 ctx->opts = opts;
2344 ctx->total_bloom_filter_data_size = 0;
2345 ctx->write_generation_data = 1;
2346 ctx->num_generation_data_overflows = 0;
2347
2348 bloom_settings.bits_per_entry = git_env_ulong("GIT_TEST_BLOOM_SETTINGS_BITS_PER_ENTRY",
2349 bloom_settings.bits_per_entry);
2350 bloom_settings.num_hashes = git_env_ulong("GIT_TEST_BLOOM_SETTINGS_NUM_HASHES",
2351 bloom_settings.num_hashes);
2352 bloom_settings.max_changed_paths = git_env_ulong("GIT_TEST_BLOOM_SETTINGS_MAX_CHANGED_PATHS",
2353 bloom_settings.max_changed_paths);
2354 ctx->bloom_settings = &bloom_settings;
2355
2356 init_topo_level_slab(&topo_levels);
2357 ctx->topo_levels = &topo_levels;
2358
2359 prepare_commit_graph(ctx->r);
2360 if (ctx->r->objects->commit_graph) {
2361 struct commit_graph *g = ctx->r->objects->commit_graph;
2362
2363 while (g) {
2364 g->topo_levels = &topo_levels;
2365 g = g->base_graph;
2366 }
2367 }
2368
2369 if (flags & COMMIT_GRAPH_WRITE_BLOOM_FILTERS)
2370 ctx->changed_paths = 1;
2371 if (!(flags & COMMIT_GRAPH_NO_WRITE_BLOOM_FILTERS)) {
2372 struct commit_graph *g;
2373
2374 g = ctx->r->objects->commit_graph;
2375
2376 /* We have changed-paths already. Keep them in the next graph */
2377 if (g && g->chunk_bloom_data) {
2378 ctx->changed_paths = 1;
2379 ctx->bloom_settings = g->bloom_filter_settings;
2380 }
2381 }
2382
2383 if (ctx->split) {
2384 struct commit_graph *g = ctx->r->objects->commit_graph;
2385
2386 while (g) {
2387 ctx->num_commit_graphs_before++;
2388 g = g->base_graph;
2389 }
2390
2391 if (ctx->num_commit_graphs_before) {
2392 ALLOC_ARRAY(ctx->commit_graph_filenames_before, ctx->num_commit_graphs_before);
2393 i = ctx->num_commit_graphs_before;
2394 g = ctx->r->objects->commit_graph;
2395
2396 while (g) {
2397 ctx->commit_graph_filenames_before[--i] = xstrdup(g->filename);
2398 g = g->base_graph;
2399 }
2400 }
2401
2402 if (ctx->opts)
2403 replace = ctx->opts->split_flags & COMMIT_GRAPH_SPLIT_REPLACE;
2404 }
2405
2406 ctx->approx_nr_objects = approximate_object_count();
2407
2408 if (ctx->append && ctx->r->objects->commit_graph) {
2409 struct commit_graph *g = ctx->r->objects->commit_graph;
2410 for (i = 0; i < g->num_commits; i++) {
2411 struct object_id oid;
2412 hashcpy(oid.hash, g->chunk_oid_lookup + g->hash_len * i);
2413 oid_array_append(&ctx->oids, &oid);
2414 }
2415 }
2416
2417 if (pack_indexes) {
2418 ctx->order_by_pack = 1;
2419 if ((res = fill_oids_from_packs(ctx, pack_indexes)))
2420 goto cleanup;
2421 }
2422
2423 if (commits) {
2424 if ((res = fill_oids_from_commits(ctx, commits)))
2425 goto cleanup;
2426 }
2427
2428 if (!pack_indexes && !commits) {
2429 ctx->order_by_pack = 1;
2430 fill_oids_from_all_packs(ctx);
2431 }
2432
2433 close_reachable(ctx);
2434
2435 copy_oids_to_commits(ctx);
2436
2437 if (ctx->commits.nr >= GRAPH_EDGE_LAST_MASK) {
2438 error(_("too many commits to write graph"));
2439 res = -1;
2440 goto cleanup;
2441 }
2442
2443 if (!ctx->commits.nr && !replace)
2444 goto cleanup;
2445
2446 if (ctx->split) {
2447 split_graph_merge_strategy(ctx);
2448
2449 if (!replace)
2450 merge_commit_graphs(ctx);
2451 } else
2452 ctx->num_commit_graphs_after = 1;
2453
2454 ctx->trust_generation_numbers = validate_mixed_generation_chain(ctx->r->objects->commit_graph);
2455
2456 compute_topological_levels(ctx);
2457 if (ctx->write_generation_data)
2458 compute_generation_numbers(ctx);
2459
2460 if (ctx->changed_paths)
2461 compute_bloom_filters(ctx);
2462
2463 res = write_commit_graph_file(ctx);
2464
2465 if (ctx->split)
2466 mark_commit_graphs(ctx);
2467
2468 expire_commit_graphs(ctx);
2469
2470 cleanup:
2471 free(ctx->graph_name);
2472 free(ctx->commits.list);
2473 oid_array_clear(&ctx->oids);
2474
2475 if (ctx->commit_graph_filenames_after) {
2476 for (i = 0; i < ctx->num_commit_graphs_after; i++) {
2477 free(ctx->commit_graph_filenames_after[i]);
2478 free(ctx->commit_graph_hash_after[i]);
2479 }
2480
2481 for (i = 0; i < ctx->num_commit_graphs_before; i++)
2482 free(ctx->commit_graph_filenames_before[i]);
2483
2484 free(ctx->commit_graph_filenames_after);
2485 free(ctx->commit_graph_filenames_before);
2486 free(ctx->commit_graph_hash_after);
2487 }
2488
2489 free(ctx);
2490
2491 return res;
2492 }
2493
2494 #define VERIFY_COMMIT_GRAPH_ERROR_HASH 2
2495 static int verify_commit_graph_error;
2496
2497 static void graph_report(const char *fmt, ...)
2498 {
2499 va_list ap;
2500
2501 verify_commit_graph_error = 1;
2502 va_start(ap, fmt);
2503 vfprintf(stderr, fmt, ap);
2504 fprintf(stderr, "\n");
2505 va_end(ap);
2506 }
2507
2508 #define GENERATION_ZERO_EXISTS 1
2509 #define GENERATION_NUMBER_EXISTS 2
2510
2511 int verify_commit_graph(struct repository *r, struct commit_graph *g, int flags)
2512 {
2513 uint32_t i, cur_fanout_pos = 0;
2514 struct object_id prev_oid, cur_oid, checksum;
2515 int generation_zero = 0;
2516 struct hashfile *f;
2517 int devnull;
2518 struct progress *progress = NULL;
2519 int local_error = 0;
2520
2521 if (!g) {
2522 graph_report("no commit-graph file loaded");
2523 return 1;
2524 }
2525
2526 verify_commit_graph_error = verify_commit_graph_lite(g);
2527 if (verify_commit_graph_error)
2528 return verify_commit_graph_error;
2529
2530 devnull = open("/dev/null", O_WRONLY);
2531 f = hashfd(devnull, NULL);
2532 hashwrite(f, g->data, g->data_len - g->hash_len);
2533 finalize_hashfile(f, checksum.hash, CSUM_CLOSE);
2534 if (!hasheq(checksum.hash, g->data + g->data_len - g->hash_len)) {
2535 graph_report(_("the commit-graph file has incorrect checksum and is likely corrupt"));
2536 verify_commit_graph_error = VERIFY_COMMIT_GRAPH_ERROR_HASH;
2537 }
2538
2539 for (i = 0; i < g->num_commits; i++) {
2540 struct commit *graph_commit;
2541
2542 hashcpy(cur_oid.hash, g->chunk_oid_lookup + g->hash_len * i);
2543
2544 if (i && oidcmp(&prev_oid, &cur_oid) >= 0)
2545 graph_report(_("commit-graph has incorrect OID order: %s then %s"),
2546 oid_to_hex(&prev_oid),
2547 oid_to_hex(&cur_oid));
2548
2549 oidcpy(&prev_oid, &cur_oid);
2550
2551 while (cur_oid.hash[0] > cur_fanout_pos) {
2552 uint32_t fanout_value = get_be32(g->chunk_oid_fanout + cur_fanout_pos);
2553
2554 if (i != fanout_value)
2555 graph_report(_("commit-graph has incorrect fanout value: fanout[%d] = %u != %u"),
2556 cur_fanout_pos, fanout_value, i);
2557 cur_fanout_pos++;
2558 }
2559
2560 graph_commit = lookup_commit(r, &cur_oid);
2561 if (!parse_commit_in_graph_one(r, g, graph_commit))
2562 graph_report(_("failed to parse commit %s from commit-graph"),
2563 oid_to_hex(&cur_oid));
2564 }
2565
2566 while (cur_fanout_pos < 256) {
2567 uint32_t fanout_value = get_be32(g->chunk_oid_fanout + cur_fanout_pos);
2568
2569 if (g->num_commits != fanout_value)
2570 graph_report(_("commit-graph has incorrect fanout value: fanout[%d] = %u != %u"),
2571 cur_fanout_pos, fanout_value, i);
2572
2573 cur_fanout_pos++;
2574 }
2575
2576 if (verify_commit_graph_error & ~VERIFY_COMMIT_GRAPH_ERROR_HASH)
2577 return verify_commit_graph_error;
2578
2579 if (flags & COMMIT_GRAPH_WRITE_PROGRESS)
2580 progress = start_progress(_("Verifying commits in commit graph"),
2581 g->num_commits);
2582
2583 for (i = 0; i < g->num_commits; i++) {
2584 struct commit *graph_commit, *odb_commit;
2585 struct commit_list *graph_parents, *odb_parents;
2586 timestamp_t max_generation = 0;
2587 timestamp_t generation;
2588
2589 display_progress(progress, i + 1);
2590 hashcpy(cur_oid.hash, g->chunk_oid_lookup + g->hash_len * i);
2591
2592 graph_commit = lookup_commit(r, &cur_oid);
2593 odb_commit = (struct commit *)create_object(r, &cur_oid, alloc_commit_node(r));
2594 if (parse_commit_internal(odb_commit, 0, 0)) {
2595 graph_report(_("failed to parse commit %s from object database for commit-graph"),
2596 oid_to_hex(&cur_oid));
2597 continue;
2598 }
2599
2600 if (!oideq(&get_commit_tree_in_graph_one(r, g, graph_commit)->object.oid,
2601 get_commit_tree_oid(odb_commit)))
2602 graph_report(_("root tree OID for commit %s in commit-graph is %s != %s"),
2603 oid_to_hex(&cur_oid),
2604 oid_to_hex(get_commit_tree_oid(graph_commit)),
2605 oid_to_hex(get_commit_tree_oid(odb_commit)));
2606
2607 graph_parents = graph_commit->parents;
2608 odb_parents = odb_commit->parents;
2609
2610 while (graph_parents) {
2611 if (odb_parents == NULL) {
2612 graph_report(_("commit-graph parent list for commit %s is too long"),
2613 oid_to_hex(&cur_oid));
2614 break;
2615 }
2616
2617 /* parse parent in case it is in a base graph */
2618 parse_commit_in_graph_one(r, g, graph_parents->item);
2619
2620 if (!oideq(&graph_parents->item->object.oid, &odb_parents->item->object.oid))
2621 graph_report(_("commit-graph parent for %s is %s != %s"),
2622 oid_to_hex(&cur_oid),
2623 oid_to_hex(&graph_parents->item->object.oid),
2624 oid_to_hex(&odb_parents->item->object.oid));
2625
2626 generation = commit_graph_generation(graph_parents->item);
2627 if (generation > max_generation)
2628 max_generation = generation;
2629
2630 graph_parents = graph_parents->next;
2631 odb_parents = odb_parents->next;
2632 }
2633
2634 if (odb_parents != NULL)
2635 graph_report(_("commit-graph parent list for commit %s terminates early"),
2636 oid_to_hex(&cur_oid));
2637
2638 if (!commit_graph_generation(graph_commit)) {
2639 if (generation_zero == GENERATION_NUMBER_EXISTS)
2640 graph_report(_("commit-graph has generation number zero for commit %s, but non-zero elsewhere"),
2641 oid_to_hex(&cur_oid));
2642 generation_zero = GENERATION_ZERO_EXISTS;
2643 } else if (generation_zero == GENERATION_ZERO_EXISTS)
2644 graph_report(_("commit-graph has non-zero generation number for commit %s, but zero elsewhere"),
2645 oid_to_hex(&cur_oid));
2646
2647 if (generation_zero == GENERATION_ZERO_EXISTS)
2648 continue;
2649
2650 /*
2651 * If we are using topological level and one of our parents has
2652 * generation GENERATION_NUMBER_V1_MAX, then our generation is
2653 * also GENERATION_NUMBER_V1_MAX. Decrement to avoid extra logic
2654 * in the following condition.
2655 */
2656 if (!g->read_generation_data && max_generation == GENERATION_NUMBER_V1_MAX)
2657 max_generation--;
2658
2659 generation = commit_graph_generation(graph_commit);
2660 if (generation < max_generation + 1)
2661 graph_report(_("commit-graph generation for commit %s is %"PRItime" < %"PRItime),
2662 oid_to_hex(&cur_oid),
2663 generation,
2664 max_generation + 1);
2665
2666 if (graph_commit->date != odb_commit->date)
2667 graph_report(_("commit date for commit %s in commit-graph is %"PRItime" != %"PRItime),
2668 oid_to_hex(&cur_oid),
2669 graph_commit->date,
2670 odb_commit->date);
2671 }
2672 stop_progress(&progress);
2673
2674 local_error = verify_commit_graph_error;
2675
2676 if (!(flags & COMMIT_GRAPH_VERIFY_SHALLOW) && g->base_graph)
2677 local_error |= verify_commit_graph(r, g->base_graph, flags);
2678
2679 return local_error;
2680 }
2681
2682 void free_commit_graph(struct commit_graph *g)
2683 {
2684 if (!g)
2685 return;
2686 if (g->data) {
2687 munmap((void *)g->data, g->data_len);
2688 g->data = NULL;
2689 }
2690 free(g->filename);
2691 free(g->bloom_filter_settings);
2692 free(g);
2693 }
2694
2695 void disable_commit_graph(struct repository *r)
2696 {
2697 r->commit_graph_disabled = 1;
2698 }
git for Debian