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