?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
submodule-config.h: remove unnecessary include
[git/gitster.git] / commit-graph.c
blob5bfee53e87b75cac3e8326909476cdc16e9517e6
1 #include "git-compat-util.h"
2 #include "config.h"
3 #include "gettext.h"
4 #include "hex.h"
5 #include "lockfile.h"
6 #include "pack.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 clear_commit_graph_data_slab(&commit_graph_data_slab);
834 free_commit_graph(o->commit_graph);
835 o->commit_graph = NULL;
836 }
837
838 static int bsearch_graph(struct commit_graph *g, const struct object_id *oid, uint32_t *pos)
839 {
840 return bsearch_hash(oid->hash, g->chunk_oid_fanout,
841 g->chunk_oid_lookup, g->hash_len, pos);
842 }
843
844 static void load_oid_from_graph(struct commit_graph *g,
845 uint32_t pos,
846 struct object_id *oid)
847 {
848 uint32_t lex_index;
849
850 while (g && pos < g->num_commits_in_base)
851 g = g->base_graph;
852
853 if (!g)
854 BUG("NULL commit-graph");
855
856 if (pos >= g->num_commits + g->num_commits_in_base)
857 die(_("invalid commit position. commit-graph is likely corrupt"));
858
859 lex_index = pos - g->num_commits_in_base;
860
861 oidread(oid, g->chunk_oid_lookup + st_mult(g->hash_len, lex_index));
862 }
863
864 static struct commit_list **insert_parent_or_die(struct repository *r,
865 struct commit_graph *g,
866 uint32_t pos,
867 struct commit_list **pptr)
868 {
869 struct commit *c;
870 struct object_id oid;
871
872 if (pos >= g->num_commits + g->num_commits_in_base)
873 die("invalid parent position %"PRIu32, pos);
874
875 load_oid_from_graph(g, pos, &oid);
876 c = lookup_commit(r, &oid);
877 if (!c)
878 die(_("could not find commit %s"), oid_to_hex(&oid));
879 commit_graph_data_at(c)->graph_pos = pos;
880 return &commit_list_insert(c, pptr)->next;
881 }
882
883 static void fill_commit_graph_info(struct commit *item, struct commit_graph *g, uint32_t pos)
884 {
885 const unsigned char *commit_data;
886 struct commit_graph_data *graph_data;
887 uint32_t lex_index, offset_pos;
888 uint64_t date_high, date_low, offset;
889
890 while (pos < g->num_commits_in_base)
891 g = g->base_graph;
892
893 if (pos >= g->num_commits + g->num_commits_in_base)
894 die(_("invalid commit position. commit-graph is likely corrupt"));
895
896 lex_index = pos - g->num_commits_in_base;
897 commit_data = g->chunk_commit_data + st_mult(GRAPH_DATA_WIDTH, lex_index);
898
899 graph_data = commit_graph_data_at(item);
900 graph_data->graph_pos = pos;
901
902 date_high = get_be32(commit_data + g->hash_len + 8) & 0x3;
903 date_low = get_be32(commit_data + g->hash_len + 12);
904 item->date = (timestamp_t)((date_high << 32) | date_low);
905
906 if (g->read_generation_data) {
907 offset = (timestamp_t)get_be32(g->chunk_generation_data + st_mult(sizeof(uint32_t), lex_index));
908
909 if (offset & CORRECTED_COMMIT_DATE_OFFSET_OVERFLOW) {
910 if (!g->chunk_generation_data_overflow)
911 die(_("commit-graph requires overflow generation data but has none"));
912
913 offset_pos = offset ^ CORRECTED_COMMIT_DATE_OFFSET_OVERFLOW;
914 if (g->chunk_generation_data_overflow_size / sizeof(uint64_t) <= offset_pos)
915 die(_("commit-graph overflow generation data is too small"));
916 graph_data->generation = item->date +
917 get_be64(g->chunk_generation_data_overflow + sizeof(uint64_t) * offset_pos);
918 } else
919 graph_data->generation = item->date + offset;
920 } else
921 graph_data->generation = get_be32(commit_data + g->hash_len + 8) >> 2;
922
923 if (g->topo_levels)
924 *topo_level_slab_at(g->topo_levels, item) = get_be32(commit_data + g->hash_len + 8) >> 2;
925 }
926
927 static inline void set_commit_tree(struct commit *c, struct tree *t)
928 {
929 c->maybe_tree = t;
930 }
931
932 static int fill_commit_in_graph(struct repository *r,
933 struct commit *item,
934 struct commit_graph *g, uint32_t pos)
935 {
936 uint32_t edge_value;
937 uint32_t parent_data_pos;
938 struct commit_list **pptr;
939 const unsigned char *commit_data;
940 uint32_t lex_index;
941
942 while (pos < g->num_commits_in_base)
943 g = g->base_graph;
944
945 fill_commit_graph_info(item, g, pos);
946
947 lex_index = pos - g->num_commits_in_base;
948 commit_data = g->chunk_commit_data + st_mult(g->hash_len + 16, lex_index);
949
950 item->object.parsed = 1;
951
952 set_commit_tree(item, NULL);
953
954 pptr = &item->parents;
955
956 edge_value = get_be32(commit_data + g->hash_len);
957 if (edge_value == GRAPH_PARENT_NONE)
958 return 1;
959 pptr = insert_parent_or_die(r, g, edge_value, pptr);
960
961 edge_value = get_be32(commit_data + g->hash_len + 4);
962 if (edge_value == GRAPH_PARENT_NONE)
963 return 1;
964 if (!(edge_value & GRAPH_EXTRA_EDGES_NEEDED)) {
965 pptr = insert_parent_or_die(r, g, edge_value, pptr);
966 return 1;
967 }
968
969 parent_data_pos = edge_value & GRAPH_EDGE_LAST_MASK;
970 do {
971 if (g->chunk_extra_edges_size / sizeof(uint32_t) <= parent_data_pos) {
972 error("commit-graph extra-edges pointer out of bounds");
973 free_commit_list(item->parents);
974 item->parents = NULL;
975 item->object.parsed = 0;
976 return 0;
977 }
978 edge_value = get_be32(g->chunk_extra_edges +
979 sizeof(uint32_t) * parent_data_pos);
980 pptr = insert_parent_or_die(r, g,
981 edge_value & GRAPH_EDGE_LAST_MASK,
982 pptr);
983 parent_data_pos++;
984 } while (!(edge_value & GRAPH_LAST_EDGE));
985
986 return 1;
987 }
988
989 static int search_commit_pos_in_graph(const struct object_id *id, struct commit_graph *g, uint32_t *pos)
990 {
991 struct commit_graph *cur_g = g;
992 uint32_t lex_index;
993
994 while (cur_g && !bsearch_graph(cur_g, id, &lex_index))
995 cur_g = cur_g->base_graph;
996
997 if (cur_g) {
998 *pos = lex_index + cur_g->num_commits_in_base;
999 return 1;
1000 }
1001
1002 return 0;
1003 }
1004
1005 static int find_commit_pos_in_graph(struct commit *item, struct commit_graph *g, uint32_t *pos)
1006 {
1007 uint32_t graph_pos = commit_graph_position(item);
1008 if (graph_pos != COMMIT_NOT_FROM_GRAPH) {
1009 *pos = graph_pos;
1010 return 1;
1011 } else {
1012 return search_commit_pos_in_graph(&item->object.oid, g, pos);
1013 }
1014 }
1015
1016 int repo_find_commit_pos_in_graph(struct repository *r, struct commit *c,
1017 uint32_t *pos)
1018 {
1019 if (!prepare_commit_graph(r))
1020 return 0;
1021 return find_commit_pos_in_graph(c, r->objects->commit_graph, pos);
1022 }
1023
1024 struct commit *lookup_commit_in_graph(struct repository *repo, const struct object_id *id)
1025 {
1026 static int commit_graph_paranoia = -1;
1027 struct commit *commit;
1028 uint32_t pos;
1029
1030 if (commit_graph_paranoia == -1)
1031 commit_graph_paranoia = git_env_bool(GIT_COMMIT_GRAPH_PARANOIA, 1);
1032
1033 if (!prepare_commit_graph(repo))
1034 return NULL;
1035 if (!search_commit_pos_in_graph(id, repo->objects->commit_graph, &pos))
1036 return NULL;
1037 if (commit_graph_paranoia && !has_object(repo, id, 0))
1038 return NULL;
1039
1040 commit = lookup_commit(repo, id);
1041 if (!commit)
1042 return NULL;
1043 if (commit->object.parsed)
1044 return commit;
1045
1046 if (!fill_commit_in_graph(repo, commit, repo->objects->commit_graph, pos))
1047 return NULL;
1048
1049 return commit;
1050 }
1051
1052 static int parse_commit_in_graph_one(struct repository *r,
1053 struct commit_graph *g,
1054 struct commit *item)
1055 {
1056 uint32_t pos;
1057
1058 if (item->object.parsed)
1059 return 1;
1060
1061 if (find_commit_pos_in_graph(item, g, &pos))
1062 return fill_commit_in_graph(r, item, g, pos);
1063
1064 return 0;
1065 }
1066
1067 int parse_commit_in_graph(struct repository *r, struct commit *item)
1068 {
1069 static int checked_env = 0;
1070
1071 if (!checked_env &&
1072 git_env_bool(GIT_TEST_COMMIT_GRAPH_DIE_ON_PARSE, 0))
1073 die("dying as requested by the '%s' variable on commit-graph parse!",
1074 GIT_TEST_COMMIT_GRAPH_DIE_ON_PARSE);
1075 checked_env = 1;
1076
1077 if (!prepare_commit_graph(r))
1078 return 0;
1079 return parse_commit_in_graph_one(r, r->objects->commit_graph, item);
1080 }
1081
1082 void load_commit_graph_info(struct repository *r, struct commit *item)
1083 {
1084 uint32_t pos;
1085 if (repo_find_commit_pos_in_graph(r, item, &pos))
1086 fill_commit_graph_info(item, r->objects->commit_graph, pos);
1087 }
1088
1089 static struct tree *load_tree_for_commit(struct repository *r,
1090 struct commit_graph *g,
1091 struct commit *c)
1092 {
1093 struct object_id oid;
1094 const unsigned char *commit_data;
1095 uint32_t graph_pos = commit_graph_position(c);
1096
1097 while (graph_pos < g->num_commits_in_base)
1098 g = g->base_graph;
1099
1100 commit_data = g->chunk_commit_data +
1101 st_mult(GRAPH_DATA_WIDTH, graph_pos - g->num_commits_in_base);
1102
1103 oidread(&oid, commit_data);
1104 set_commit_tree(c, lookup_tree(r, &oid));
1105
1106 return c->maybe_tree;
1107 }
1108
1109 static struct tree *get_commit_tree_in_graph_one(struct repository *r,
1110 struct commit_graph *g,
1111 const struct commit *c)
1112 {
1113 if (c->maybe_tree)
1114 return c->maybe_tree;
1115 if (commit_graph_position(c) == COMMIT_NOT_FROM_GRAPH)
1116 BUG("get_commit_tree_in_graph_one called from non-commit-graph commit");
1117
1118 return load_tree_for_commit(r, g, (struct commit *)c);
1119 }
1120
1121 struct tree *get_commit_tree_in_graph(struct repository *r, const struct commit *c)
1122 {
1123 return get_commit_tree_in_graph_one(r, r->objects->commit_graph, c);
1124 }
1125
1126 struct packed_commit_list {
1127 struct commit **list;
1128 size_t nr;
1129 size_t alloc;
1130 };
1131
1132 struct write_commit_graph_context {
1133 struct repository *r;
1134 struct object_directory *odb;
1135 char *graph_name;
1136 struct oid_array oids;
1137 struct packed_commit_list commits;
1138 int num_extra_edges;
1139 int num_generation_data_overflows;
1140 unsigned long approx_nr_objects;
1141 struct progress *progress;
1142 int progress_done;
1143 uint64_t progress_cnt;
1144
1145 char *base_graph_name;
1146 int num_commit_graphs_before;
1147 int num_commit_graphs_after;
1148 char **commit_graph_filenames_before;
1149 char **commit_graph_filenames_after;
1150 char **commit_graph_hash_after;
1151 uint32_t new_num_commits_in_base;
1152 struct commit_graph *new_base_graph;
1153
1154 unsigned append:1,
1155 report_progress:1,
1156 split:1,
1157 changed_paths:1,
1158 order_by_pack:1,
1159 write_generation_data:1,
1160 trust_generation_numbers:1;
1161
1162 struct topo_level_slab *topo_levels;
1163 const struct commit_graph_opts *opts;
1164 size_t total_bloom_filter_data_size;
1165 const struct bloom_filter_settings *bloom_settings;
1166
1167 int count_bloom_filter_computed;
1168 int count_bloom_filter_not_computed;
1169 int count_bloom_filter_trunc_empty;
1170 int count_bloom_filter_trunc_large;
1171 };
1172
1173 static int write_graph_chunk_fanout(struct hashfile *f,
1174 void *data)
1175 {
1176 struct write_commit_graph_context *ctx = data;
1177 int i, count = 0;
1178 struct commit **list = ctx->commits.list;
1179
1180 /*
1181 * Write the first-level table (the list is sorted,
1182 * but we use a 256-entry lookup to be able to avoid
1183 * having to do eight extra binary search iterations).
1184 */
1185 for (i = 0; i < 256; i++) {
1186 while (count < ctx->commits.nr) {
1187 if ((*list)->object.oid.hash[0] != i)
1188 break;
1189 display_progress(ctx->progress, ++ctx->progress_cnt);
1190 count++;
1191 list++;
1192 }
1193
1194 hashwrite_be32(f, count);
1195 }
1196
1197 return 0;
1198 }
1199
1200 static int write_graph_chunk_oids(struct hashfile *f,
1201 void *data)
1202 {
1203 struct write_commit_graph_context *ctx = data;
1204 struct commit **list = ctx->commits.list;
1205 int count;
1206 for (count = 0; count < ctx->commits.nr; count++, list++) {
1207 display_progress(ctx->progress, ++ctx->progress_cnt);
1208 hashwrite(f, (*list)->object.oid.hash, the_hash_algo->rawsz);
1209 }
1210
1211 return 0;
1212 }
1213
1214 static const struct object_id *commit_to_oid(size_t index, const void *table)
1215 {
1216 const struct commit * const *commits = table;
1217 return &commits[index]->object.oid;
1218 }
1219
1220 static int write_graph_chunk_data(struct hashfile *f,
1221 void *data)
1222 {
1223 struct write_commit_graph_context *ctx = data;
1224 struct commit **list = ctx->commits.list;
1225 struct commit **last = ctx->commits.list + ctx->commits.nr;
1226 uint32_t num_extra_edges = 0;
1227
1228 while (list < last) {
1229 struct commit_list *parent;
1230 struct object_id *tree;
1231 int edge_value;
1232 uint32_t packedDate[2];
1233 display_progress(ctx->progress, ++ctx->progress_cnt);
1234
1235 if (repo_parse_commit_no_graph(ctx->r, *list))
1236 die(_("unable to parse commit %s"),
1237 oid_to_hex(&(*list)->object.oid));
1238 tree = get_commit_tree_oid(*list);
1239 hashwrite(f, tree->hash, the_hash_algo->rawsz);
1240
1241 parent = (*list)->parents;
1242
1243 if (!parent)
1244 edge_value = GRAPH_PARENT_NONE;
1245 else {
1246 edge_value = oid_pos(&parent->item->object.oid,
1247 ctx->commits.list,
1248 ctx->commits.nr,
1249 commit_to_oid);
1250
1251 if (edge_value >= 0)
1252 edge_value += ctx->new_num_commits_in_base;
1253 else if (ctx->new_base_graph) {
1254 uint32_t pos;
1255 if (find_commit_pos_in_graph(parent->item,
1256 ctx->new_base_graph,
1257 &pos))
1258 edge_value = pos;
1259 }
1260
1261 if (edge_value < 0)
1262 BUG("missing parent %s for commit %s",
1263 oid_to_hex(&parent->item->object.oid),
1264 oid_to_hex(&(*list)->object.oid));
1265 }
1266
1267 hashwrite_be32(f, edge_value);
1268
1269 if (parent)
1270 parent = parent->next;
1271
1272 if (!parent)
1273 edge_value = GRAPH_PARENT_NONE;
1274 else if (parent->next)
1275 edge_value = GRAPH_EXTRA_EDGES_NEEDED | num_extra_edges;
1276 else {
1277 edge_value = oid_pos(&parent->item->object.oid,
1278 ctx->commits.list,
1279 ctx->commits.nr,
1280 commit_to_oid);
1281
1282 if (edge_value >= 0)
1283 edge_value += ctx->new_num_commits_in_base;
1284 else if (ctx->new_base_graph) {
1285 uint32_t pos;
1286 if (find_commit_pos_in_graph(parent->item,
1287 ctx->new_base_graph,
1288 &pos))
1289 edge_value = pos;
1290 }
1291
1292 if (edge_value < 0)
1293 BUG("missing parent %s for commit %s",
1294 oid_to_hex(&parent->item->object.oid),
1295 oid_to_hex(&(*list)->object.oid));
1296 }
1297
1298 hashwrite_be32(f, edge_value);
1299
1300 if (edge_value & GRAPH_EXTRA_EDGES_NEEDED) {
1301 do {
1302 num_extra_edges++;
1303 parent = parent->next;
1304 } while (parent);
1305 }
1306
1307 if (sizeof((*list)->date) > 4)
1308 packedDate[0] = htonl(((*list)->date >> 32) & 0x3);
1309 else
1310 packedDate[0] = 0;
1311
1312 packedDate[0] |= htonl(*topo_level_slab_at(ctx->topo_levels, *list) << 2);
1313
1314 packedDate[1] = htonl((*list)->date);
1315 hashwrite(f, packedDate, 8);
1316
1317 list++;
1318 }
1319
1320 return 0;
1321 }
1322
1323 static int write_graph_chunk_generation_data(struct hashfile *f,
1324 void *data)
1325 {
1326 struct write_commit_graph_context *ctx = data;
1327 int i, num_generation_data_overflows = 0;
1328
1329 for (i = 0; i < ctx->commits.nr; i++) {
1330 struct commit *c = ctx->commits.list[i];
1331 timestamp_t offset;
1332 repo_parse_commit(ctx->r, c);
1333 offset = commit_graph_data_at(c)->generation - c->date;
1334 display_progress(ctx->progress, ++ctx->progress_cnt);
1335
1336 if (offset > GENERATION_NUMBER_V2_OFFSET_MAX) {
1337 offset = CORRECTED_COMMIT_DATE_OFFSET_OVERFLOW | num_generation_data_overflows;
1338 num_generation_data_overflows++;
1339 }
1340
1341 hashwrite_be32(f, offset);
1342 }
1343
1344 return 0;
1345 }
1346
1347 static int write_graph_chunk_generation_data_overflow(struct hashfile *f,
1348 void *data)
1349 {
1350 struct write_commit_graph_context *ctx = data;
1351 int i;
1352 for (i = 0; i < ctx->commits.nr; i++) {
1353 struct commit *c = ctx->commits.list[i];
1354 timestamp_t offset = commit_graph_data_at(c)->generation - c->date;
1355 display_progress(ctx->progress, ++ctx->progress_cnt);
1356
1357 if (offset > GENERATION_NUMBER_V2_OFFSET_MAX) {
1358 hashwrite_be32(f, offset >> 32);
1359 hashwrite_be32(f, (uint32_t) offset);
1360 }
1361 }
1362
1363 return 0;
1364 }
1365
1366 static int write_graph_chunk_extra_edges(struct hashfile *f,
1367 void *data)
1368 {
1369 struct write_commit_graph_context *ctx = data;
1370 struct commit **list = ctx->commits.list;
1371 struct commit **last = ctx->commits.list + ctx->commits.nr;
1372 struct commit_list *parent;
1373
1374 while (list < last) {
1375 int num_parents = 0;
1376
1377 display_progress(ctx->progress, ++ctx->progress_cnt);
1378
1379 for (parent = (*list)->parents; num_parents < 3 && parent;
1380 parent = parent->next)
1381 num_parents++;
1382
1383 if (num_parents <= 2) {
1384 list++;
1385 continue;
1386 }
1387
1388 /* Since num_parents > 2, this initializer is safe. */
1389 for (parent = (*list)->parents->next; parent; parent = parent->next) {
1390 int edge_value = oid_pos(&parent->item->object.oid,
1391 ctx->commits.list,
1392 ctx->commits.nr,
1393 commit_to_oid);
1394
1395 if (edge_value >= 0)
1396 edge_value += ctx->new_num_commits_in_base;
1397 else if (ctx->new_base_graph) {
1398 uint32_t pos;
1399 if (find_commit_pos_in_graph(parent->item,
1400 ctx->new_base_graph,
1401 &pos))
1402 edge_value = pos;
1403 }
1404
1405 if (edge_value < 0)
1406 BUG("missing parent %s for commit %s",
1407 oid_to_hex(&parent->item->object.oid),
1408 oid_to_hex(&(*list)->object.oid));
1409 else if (!parent->next)
1410 edge_value |= GRAPH_LAST_EDGE;
1411
1412 hashwrite_be32(f, edge_value);
1413 }
1414
1415 list++;
1416 }
1417
1418 return 0;
1419 }
1420
1421 static int write_graph_chunk_bloom_indexes(struct hashfile *f,
1422 void *data)
1423 {
1424 struct write_commit_graph_context *ctx = data;
1425 struct commit **list = ctx->commits.list;
1426 struct commit **last = ctx->commits.list + ctx->commits.nr;
1427 uint32_t cur_pos = 0;
1428
1429 while (list < last) {
1430 struct bloom_filter *filter = get_bloom_filter(ctx->r, *list);
1431 size_t len = filter ? filter->len : 0;
1432 cur_pos += len;
1433 display_progress(ctx->progress, ++ctx->progress_cnt);
1434 hashwrite_be32(f, cur_pos);
1435 list++;
1436 }
1437
1438 return 0;
1439 }
1440
1441 static void trace2_bloom_filter_settings(struct write_commit_graph_context *ctx)
1442 {
1443 struct json_writer jw = JSON_WRITER_INIT;
1444
1445 jw_object_begin(&jw, 0);
1446 jw_object_intmax(&jw, "hash_version", ctx->bloom_settings->hash_version);
1447 jw_object_intmax(&jw, "num_hashes", ctx->bloom_settings->num_hashes);
1448 jw_object_intmax(&jw, "bits_per_entry", ctx->bloom_settings->bits_per_entry);
1449 jw_object_intmax(&jw, "max_changed_paths", ctx->bloom_settings->max_changed_paths);
1450 jw_end(&jw);
1451
1452 trace2_data_json("bloom", ctx->r, "settings", &jw);
1453
1454 jw_release(&jw);
1455 }
1456
1457 static int write_graph_chunk_bloom_data(struct hashfile *f,
1458 void *data)
1459 {
1460 struct write_commit_graph_context *ctx = data;
1461 struct commit **list = ctx->commits.list;
1462 struct commit **last = ctx->commits.list + ctx->commits.nr;
1463
1464 trace2_bloom_filter_settings(ctx);
1465
1466 hashwrite_be32(f, ctx->bloom_settings->hash_version);
1467 hashwrite_be32(f, ctx->bloom_settings->num_hashes);
1468 hashwrite_be32(f, ctx->bloom_settings->bits_per_entry);
1469
1470 while (list < last) {
1471 struct bloom_filter *filter = get_bloom_filter(ctx->r, *list);
1472 size_t len = filter ? filter->len : 0;
1473
1474 display_progress(ctx->progress, ++ctx->progress_cnt);
1475 if (len)
1476 hashwrite(f, filter->data, len * sizeof(unsigned char));
1477 list++;
1478 }
1479
1480 return 0;
1481 }
1482
1483 static int add_packed_commits(const struct object_id *oid,
1484 struct packed_git *pack,
1485 uint32_t pos,
1486 void *data)
1487 {
1488 struct write_commit_graph_context *ctx = (struct write_commit_graph_context*)data;
1489 enum object_type type;
1490 off_t offset = nth_packed_object_offset(pack, pos);
1491 struct object_info oi = OBJECT_INFO_INIT;
1492
1493 if (ctx->progress)
1494 display_progress(ctx->progress, ++ctx->progress_done);
1495
1496 oi.typep = &type;
1497 if (packed_object_info(ctx->r, pack, offset, &oi) < 0)
1498 die(_("unable to get type of object %s"), oid_to_hex(oid));
1499
1500 if (type != OBJ_COMMIT)
1501 return 0;
1502
1503 oid_array_append(&ctx->oids, oid);
1504 set_commit_pos(ctx->r, oid);
1505
1506 return 0;
1507 }
1508
1509 static void add_missing_parents(struct write_commit_graph_context *ctx, struct commit *commit)
1510 {
1511 struct commit_list *parent;
1512 for (parent = commit->parents; parent; parent = parent->next) {
1513 if (!(parent->item->object.flags & REACHABLE)) {
1514 oid_array_append(&ctx->oids, &parent->item->object.oid);
1515 parent->item->object.flags |= REACHABLE;
1516 }
1517 }
1518 }
1519
1520 static void close_reachable(struct write_commit_graph_context *ctx)
1521 {
1522 int i;
1523 struct commit *commit;
1524 enum commit_graph_split_flags flags = ctx->opts ?
1525 ctx->opts->split_flags : COMMIT_GRAPH_SPLIT_UNSPECIFIED;
1526
1527 if (ctx->report_progress)
1528 ctx->progress = start_delayed_progress(
1529 _("Loading known commits in commit graph"),
1530 ctx->oids.nr);
1531 for (i = 0; i < ctx->oids.nr; i++) {
1532 display_progress(ctx->progress, i + 1);
1533 commit = lookup_commit(ctx->r, &ctx->oids.oid[i]);
1534 if (commit)
1535 commit->object.flags |= REACHABLE;
1536 }
1537 stop_progress(&ctx->progress);
1538
1539 /*
1540 * As this loop runs, ctx->oids.nr may grow, but not more
1541 * than the number of missing commits in the reachable
1542 * closure.
1543 */
1544 if (ctx->report_progress)
1545 ctx->progress = start_delayed_progress(
1546 _("Expanding reachable commits in commit graph"),
1547 0);
1548 for (i = 0; i < ctx->oids.nr; i++) {
1549 display_progress(ctx->progress, i + 1);
1550 commit = lookup_commit(ctx->r, &ctx->oids.oid[i]);
1551
1552 if (!commit)
1553 continue;
1554 if (ctx->split) {
1555 if ((!repo_parse_commit(ctx->r, commit) &&
1556 commit_graph_position(commit) == COMMIT_NOT_FROM_GRAPH) ||
1557 flags == COMMIT_GRAPH_SPLIT_REPLACE)
1558 add_missing_parents(ctx, commit);
1559 } else if (!repo_parse_commit_no_graph(ctx->r, commit))
1560 add_missing_parents(ctx, commit);
1561 }
1562 stop_progress(&ctx->progress);
1563
1564 if (ctx->report_progress)
1565 ctx->progress = start_delayed_progress(
1566 _("Clearing commit marks in commit graph"),
1567 ctx->oids.nr);
1568 for (i = 0; i < ctx->oids.nr; i++) {
1569 display_progress(ctx->progress, i + 1);
1570 commit = lookup_commit(ctx->r, &ctx->oids.oid[i]);
1571
1572 if (commit)
1573 commit->object.flags &= ~REACHABLE;
1574 }
1575 stop_progress(&ctx->progress);
1576 }
1577
1578 struct compute_generation_info {
1579 struct repository *r;
1580 struct packed_commit_list *commits;
1581 struct progress *progress;
1582 int progress_cnt;
1583
1584 timestamp_t (*get_generation)(struct commit *c, void *data);
1585 void (*set_generation)(struct commit *c, timestamp_t gen, void *data);
1586 void *data;
1587 };
1588
1589 static timestamp_t compute_generation_from_max(struct commit *c,
1590 timestamp_t max_gen,
1591 int generation_version)
1592 {
1593 switch (generation_version) {
1594 case 1: /* topological levels */
1595 if (max_gen > GENERATION_NUMBER_V1_MAX - 1)
1596 max_gen = GENERATION_NUMBER_V1_MAX - 1;
1597 return max_gen + 1;
1598
1599 case 2: /* corrected commit date */
1600 if (c->date && c->date > max_gen)
1601 max_gen = c->date - 1;
1602 return max_gen + 1;
1603
1604 default:
1605 BUG("attempting unimplemented version");
1606 }
1607 }
1608
1609 static void compute_reachable_generation_numbers(
1610 struct compute_generation_info *info,
1611 int generation_version)
1612 {
1613 int i;
1614 struct commit_list *list = NULL;
1615
1616 for (i = 0; i < info->commits->nr; i++) {
1617 struct commit *c = info->commits->list[i];
1618 timestamp_t gen;
1619 repo_parse_commit(info->r, c);
1620 gen = info->get_generation(c, info->data);
1621 display_progress(info->progress, info->progress_cnt + 1);
1622
1623 if (gen != GENERATION_NUMBER_ZERO && gen != GENERATION_NUMBER_INFINITY)
1624 continue;
1625
1626 commit_list_insert(c, &list);
1627 while (list) {
1628 struct commit *current = list->item;
1629 struct commit_list *parent;
1630 int all_parents_computed = 1;
1631 uint32_t max_gen = 0;
1632
1633 for (parent = current->parents; parent; parent = parent->next) {
1634 repo_parse_commit(info->r, parent->item);
1635 gen = info->get_generation(parent->item, info->data);
1636
1637 if (gen == GENERATION_NUMBER_ZERO) {
1638 all_parents_computed = 0;
1639 commit_list_insert(parent->item, &list);
1640 break;
1641 }
1642
1643 if (gen > max_gen)
1644 max_gen = gen;
1645 }
1646
1647 if (all_parents_computed) {
1648 pop_commit(&list);
1649 gen = compute_generation_from_max(
1650 current, max_gen,
1651 generation_version);
1652 info->set_generation(current, gen, info->data);
1653 }
1654 }
1655 }
1656 }
1657
1658 static timestamp_t get_topo_level(struct commit *c, void *data)
1659 {
1660 struct write_commit_graph_context *ctx = data;
1661 return *topo_level_slab_at(ctx->topo_levels, c);
1662 }
1663
1664 static void set_topo_level(struct commit *c, timestamp_t t, void *data)
1665 {
1666 struct write_commit_graph_context *ctx = data;
1667 *topo_level_slab_at(ctx->topo_levels, c) = (uint32_t)t;
1668 }
1669
1670 static void compute_topological_levels(struct write_commit_graph_context *ctx)
1671 {
1672 struct compute_generation_info info = {
1673 .r = ctx->r,
1674 .commits = &ctx->commits,
1675 .get_generation = get_topo_level,
1676 .set_generation = set_topo_level,
1677 .data = ctx,
1678 };
1679
1680 if (ctx->report_progress)
1681 info.progress = ctx->progress
1682 = start_delayed_progress(
1683 _("Computing commit graph topological levels"),
1684 ctx->commits.nr);
1685
1686 compute_reachable_generation_numbers(&info, 1);
1687
1688 stop_progress(&ctx->progress);
1689 }
1690
1691 static timestamp_t get_generation_from_graph_data(struct commit *c,
1692 void *data UNUSED)
1693 {
1694 return commit_graph_data_at(c)->generation;
1695 }
1696
1697 static void set_generation_v2(struct commit *c, timestamp_t t,
1698 void *data UNUSED)
1699 {
1700 struct commit_graph_data *g = commit_graph_data_at(c);
1701 g->generation = t;
1702 }
1703
1704 static void compute_generation_numbers(struct write_commit_graph_context *ctx)
1705 {
1706 int i;
1707 struct compute_generation_info info = {
1708 .r = ctx->r,
1709 .commits = &ctx->commits,
1710 .get_generation = get_generation_from_graph_data,
1711 .set_generation = set_generation_v2,
1712 };
1713
1714 if (ctx->report_progress)
1715 info.progress = ctx->progress
1716 = start_delayed_progress(
1717 _("Computing commit graph generation numbers"),
1718 ctx->commits.nr);
1719
1720 if (!ctx->trust_generation_numbers) {
1721 for (i = 0; i < ctx->commits.nr; i++) {
1722 struct commit *c = ctx->commits.list[i];
1723 repo_parse_commit(ctx->r, c);
1724 commit_graph_data_at(c)->generation = GENERATION_NUMBER_ZERO;
1725 }
1726 }
1727
1728 compute_reachable_generation_numbers(&info, 2);
1729
1730 for (i = 0; i < ctx->commits.nr; i++) {
1731 struct commit *c = ctx->commits.list[i];
1732 timestamp_t offset = commit_graph_data_at(c)->generation - c->date;
1733 if (offset > GENERATION_NUMBER_V2_OFFSET_MAX)
1734 ctx->num_generation_data_overflows++;
1735 }
1736 stop_progress(&ctx->progress);
1737 }
1738
1739 static void set_generation_in_graph_data(struct commit *c, timestamp_t t,
1740 void *data UNUSED)
1741 {
1742 commit_graph_data_at(c)->generation = t;
1743 }
1744
1745 /*
1746 * After this method, all commits reachable from those in the given
1747 * list will have non-zero, non-infinite generation numbers.
1748 */
1749 void ensure_generations_valid(struct repository *r,
1750 struct commit **commits, size_t nr)
1751 {
1752 int generation_version = get_configured_generation_version(r);
1753 struct packed_commit_list list = {
1754 .list = commits,
1755 .alloc = nr,
1756 .nr = nr,
1757 };
1758 struct compute_generation_info info = {
1759 .r = r,
1760 .commits = &list,
1761 .get_generation = get_generation_from_graph_data,
1762 .set_generation = set_generation_in_graph_data,
1763 };
1764
1765 compute_reachable_generation_numbers(&info, generation_version);
1766 }
1767
1768 static void trace2_bloom_filter_write_statistics(struct write_commit_graph_context *ctx)
1769 {
1770 trace2_data_intmax("commit-graph", ctx->r, "filter-computed",
1771 ctx->count_bloom_filter_computed);
1772 trace2_data_intmax("commit-graph", ctx->r, "filter-not-computed",
1773 ctx->count_bloom_filter_not_computed);
1774 trace2_data_intmax("commit-graph", ctx->r, "filter-trunc-empty",
1775 ctx->count_bloom_filter_trunc_empty);
1776 trace2_data_intmax("commit-graph", ctx->r, "filter-trunc-large",
1777 ctx->count_bloom_filter_trunc_large);
1778 }
1779
1780 static void compute_bloom_filters(struct write_commit_graph_context *ctx)
1781 {
1782 int i;
1783 struct progress *progress = NULL;
1784 struct commit **sorted_commits;
1785 int max_new_filters;
1786
1787 init_bloom_filters();
1788
1789 if (ctx->report_progress)
1790 progress = start_delayed_progress(
1791 _("Computing commit changed paths Bloom filters"),
1792 ctx->commits.nr);
1793
1794 DUP_ARRAY(sorted_commits, ctx->commits.list, ctx->commits.nr);
1795
1796 if (ctx->order_by_pack)
1797 QSORT(sorted_commits, ctx->commits.nr, commit_pos_cmp);
1798 else
1799 QSORT(sorted_commits, ctx->commits.nr, commit_gen_cmp);
1800
1801 max_new_filters = ctx->opts && ctx->opts->max_new_filters >= 0 ?
1802 ctx->opts->max_new_filters : ctx->commits.nr;
1803
1804 for (i = 0; i < ctx->commits.nr; i++) {
1805 enum bloom_filter_computed computed = 0;
1806 struct commit *c = sorted_commits[i];
1807 struct bloom_filter *filter = get_or_compute_bloom_filter(
1808 ctx->r,
1809 c,
1810 ctx->count_bloom_filter_computed < max_new_filters,
1811 ctx->bloom_settings,
1812 &computed);
1813 if (computed & BLOOM_COMPUTED) {
1814 ctx->count_bloom_filter_computed++;
1815 if (computed & BLOOM_TRUNC_EMPTY)
1816 ctx->count_bloom_filter_trunc_empty++;
1817 if (computed & BLOOM_TRUNC_LARGE)
1818 ctx->count_bloom_filter_trunc_large++;
1819 } else if (computed & BLOOM_NOT_COMPUTED)
1820 ctx->count_bloom_filter_not_computed++;
1821 ctx->total_bloom_filter_data_size += filter
1822 ? sizeof(unsigned char) * filter->len : 0;
1823 display_progress(progress, i + 1);
1824 }
1825
1826 if (trace2_is_enabled())
1827 trace2_bloom_filter_write_statistics(ctx);
1828
1829 free(sorted_commits);
1830 stop_progress(&progress);
1831 }
1832
1833 struct refs_cb_data {
1834 struct oidset *commits;
1835 struct progress *progress;
1836 };
1837
1838 static int add_ref_to_set(const char *refname UNUSED,
1839 const struct object_id *oid,
1840 int flags UNUSED, void *cb_data)
1841 {
1842 struct object_id peeled;
1843 struct refs_cb_data *data = (struct refs_cb_data *)cb_data;
1844
1845 if (!peel_iterated_oid(oid, &peeled))
1846 oid = &peeled;
1847 if (oid_object_info(the_repository, oid, NULL) == OBJ_COMMIT)
1848 oidset_insert(data->commits, oid);
1849
1850 display_progress(data->progress, oidset_size(data->commits));
1851
1852 return 0;
1853 }
1854
1855 int write_commit_graph_reachable(struct object_directory *odb,
1856 enum commit_graph_write_flags flags,
1857 const struct commit_graph_opts *opts)
1858 {
1859 struct oidset commits = OIDSET_INIT;
1860 struct refs_cb_data data;
1861 int result;
1862
1863 memset(&data, 0, sizeof(data));
1864 data.commits = &commits;
1865 if (flags & COMMIT_GRAPH_WRITE_PROGRESS)
1866 data.progress = start_delayed_progress(
1867 _("Collecting referenced commits"), 0);
1868
1869 for_each_ref(add_ref_to_set, &data);
1870
1871 stop_progress(&data.progress);
1872
1873 result = write_commit_graph(odb, NULL, &commits,
1874 flags, opts);
1875
1876 oidset_clear(&commits);
1877 return result;
1878 }
1879
1880 static int fill_oids_from_packs(struct write_commit_graph_context *ctx,
1881 const struct string_list *pack_indexes)
1882 {
1883 uint32_t i;
1884 struct strbuf progress_title = STRBUF_INIT;
1885 struct strbuf packname = STRBUF_INIT;
1886 int dirlen;
1887 int ret = 0;
1888
1889 strbuf_addf(&packname, "%s/pack/", ctx->odb->path);
1890 dirlen = packname.len;
1891 if (ctx->report_progress) {
1892 strbuf_addf(&progress_title,
1893 Q_("Finding commits for commit graph in %"PRIuMAX" pack",
1894 "Finding commits for commit graph in %"PRIuMAX" packs",
1895 pack_indexes->nr),
1896 (uintmax_t)pack_indexes->nr);
1897 ctx->progress = start_delayed_progress(progress_title.buf, 0);
1898 ctx->progress_done = 0;
1899 }
1900 for (i = 0; i < pack_indexes->nr; i++) {
1901 struct packed_git *p;
1902 strbuf_setlen(&packname, dirlen);
1903 strbuf_addstr(&packname, pack_indexes->items[i].string);
1904 p = add_packed_git(packname.buf, packname.len, 1);
1905 if (!p) {
1906 ret = error(_("error adding pack %s"), packname.buf);
1907 goto cleanup;
1908 }
1909 if (open_pack_index(p)) {
1910 ret = error(_("error opening index for %s"), packname.buf);
1911 goto cleanup;
1912 }
1913 for_each_object_in_pack(p, add_packed_commits, ctx,
1914 FOR_EACH_OBJECT_PACK_ORDER);
1915 close_pack(p);
1916 free(p);
1917 }
1918
1919 cleanup:
1920 stop_progress(&ctx->progress);
1921 strbuf_release(&progress_title);
1922 strbuf_release(&packname);
1923
1924 return ret;
1925 }
1926
1927 static int fill_oids_from_commits(struct write_commit_graph_context *ctx,
1928 struct oidset *commits)
1929 {
1930 struct oidset_iter iter;
1931 struct object_id *oid;
1932
1933 if (!oidset_size(commits))
1934 return 0;
1935
1936 oidset_iter_init(commits, &iter);
1937 while ((oid = oidset_iter_next(&iter))) {
1938 oid_array_append(&ctx->oids, oid);
1939 }
1940
1941 return 0;
1942 }
1943
1944 static void fill_oids_from_all_packs(struct write_commit_graph_context *ctx)
1945 {
1946 if (ctx->report_progress)
1947 ctx->progress = start_delayed_progress(
1948 _("Finding commits for commit graph among packed objects"),
1949 ctx->approx_nr_objects);
1950 for_each_packed_object(add_packed_commits, ctx,
1951 FOR_EACH_OBJECT_PACK_ORDER);
1952 if (ctx->progress_done < ctx->approx_nr_objects)
1953 display_progress(ctx->progress, ctx->approx_nr_objects);
1954 stop_progress(&ctx->progress);
1955 }
1956
1957 static void copy_oids_to_commits(struct write_commit_graph_context *ctx)
1958 {
1959 uint32_t i;
1960 enum commit_graph_split_flags flags = ctx->opts ?
1961 ctx->opts->split_flags : COMMIT_GRAPH_SPLIT_UNSPECIFIED;
1962
1963 ctx->num_extra_edges = 0;
1964 if (ctx->report_progress)
1965 ctx->progress = start_delayed_progress(
1966 _("Finding extra edges in commit graph"),
1967 ctx->oids.nr);
1968 oid_array_sort(&ctx->oids);
1969 for (i = 0; i < ctx->oids.nr; i = oid_array_next_unique(&ctx->oids, i)) {
1970 unsigned int num_parents;
1971
1972 display_progress(ctx->progress, i + 1);
1973
1974 ALLOC_GROW(ctx->commits.list, ctx->commits.nr + 1, ctx->commits.alloc);
1975 ctx->commits.list[ctx->commits.nr] = lookup_commit(ctx->r, &ctx->oids.oid[i]);
1976
1977 if (ctx->split && flags != COMMIT_GRAPH_SPLIT_REPLACE &&
1978 commit_graph_position(ctx->commits.list[ctx->commits.nr]) != COMMIT_NOT_FROM_GRAPH)
1979 continue;
1980
1981 if (ctx->split && flags == COMMIT_GRAPH_SPLIT_REPLACE)
1982 repo_parse_commit(ctx->r, ctx->commits.list[ctx->commits.nr]);
1983 else
1984 repo_parse_commit_no_graph(ctx->r, ctx->commits.list[ctx->commits.nr]);
1985
1986 num_parents = commit_list_count(ctx->commits.list[ctx->commits.nr]->parents);
1987 if (num_parents > 2)
1988 ctx->num_extra_edges += num_parents - 1;
1989
1990 ctx->commits.nr++;
1991 }
1992 stop_progress(&ctx->progress);
1993 }
1994
1995 static int write_graph_chunk_base_1(struct hashfile *f,
1996 struct commit_graph *g)
1997 {
1998 int num = 0;
1999
2000 if (!g)
2001 return 0;
2002
2003 num = write_graph_chunk_base_1(f, g->base_graph);
2004 hashwrite(f, g->oid.hash, the_hash_algo->rawsz);
2005 return num + 1;
2006 }
2007
2008 static int write_graph_chunk_base(struct hashfile *f,
2009 void *data)
2010 {
2011 struct write_commit_graph_context *ctx = data;
2012 int num = write_graph_chunk_base_1(f, ctx->new_base_graph);
2013
2014 if (num != ctx->num_commit_graphs_after - 1) {
2015 error(_("failed to write correct number of base graph ids"));
2016 return -1;
2017 }
2018
2019 return 0;
2020 }
2021
2022 static int write_commit_graph_file(struct write_commit_graph_context *ctx)
2023 {
2024 uint32_t i;
2025 int fd;
2026 struct hashfile *f;
2027 struct lock_file lk = LOCK_INIT;
2028 const unsigned hashsz = the_hash_algo->rawsz;
2029 struct strbuf progress_title = STRBUF_INIT;
2030 struct chunkfile *cf;
2031 unsigned char file_hash[GIT_MAX_RAWSZ];
2032
2033 if (ctx->split) {
2034 struct strbuf tmp_file = STRBUF_INIT;
2035
2036 strbuf_addf(&tmp_file,
2037 "%s/info/commit-graphs/tmp_graph_XXXXXX",
2038 ctx->odb->path);
2039 ctx->graph_name = strbuf_detach(&tmp_file, NULL);
2040 } else {
2041 ctx->graph_name = get_commit_graph_filename(ctx->odb);
2042 }
2043
2044 if (safe_create_leading_directories(ctx->graph_name)) {
2045 UNLEAK(ctx->graph_name);
2046 error(_("unable to create leading directories of %s"),
2047 ctx->graph_name);
2048 return -1;
2049 }
2050
2051 if (ctx->split) {
2052 char *lock_name = get_commit_graph_chain_filename(ctx->odb);
2053
2054 hold_lock_file_for_update_mode(&lk, lock_name,
2055 LOCK_DIE_ON_ERROR, 0444);
2056 free(lock_name);
2057
2058 fd = git_mkstemp_mode(ctx->graph_name, 0444);
2059 if (fd < 0) {
2060 error(_("unable to create temporary graph layer"));
2061 return -1;
2062 }
2063
2064 if (adjust_shared_perm(ctx->graph_name)) {
2065 error(_("unable to adjust shared permissions for '%s'"),
2066 ctx->graph_name);
2067 return -1;
2068 }
2069
2070 f = hashfd(fd, ctx->graph_name);
2071 } else {
2072 hold_lock_file_for_update_mode(&lk, ctx->graph_name,
2073 LOCK_DIE_ON_ERROR, 0444);
2074 fd = get_lock_file_fd(&lk);
2075 f = hashfd(fd, get_lock_file_path(&lk));
2076 }
2077
2078 cf = init_chunkfile(f);
2079
2080 add_chunk(cf, GRAPH_CHUNKID_OIDFANOUT, GRAPH_FANOUT_SIZE,
2081 write_graph_chunk_fanout);
2082 add_chunk(cf, GRAPH_CHUNKID_OIDLOOKUP, st_mult(hashsz, ctx->commits.nr),
2083 write_graph_chunk_oids);
2084 add_chunk(cf, GRAPH_CHUNKID_DATA, st_mult(hashsz + 16, ctx->commits.nr),
2085 write_graph_chunk_data);
2086
2087 if (ctx->write_generation_data)
2088 add_chunk(cf, GRAPH_CHUNKID_GENERATION_DATA,
2089 st_mult(sizeof(uint32_t), ctx->commits.nr),
2090 write_graph_chunk_generation_data);
2091 if (ctx->num_generation_data_overflows)
2092 add_chunk(cf, GRAPH_CHUNKID_GENERATION_DATA_OVERFLOW,
2093 st_mult(sizeof(timestamp_t), ctx->num_generation_data_overflows),
2094 write_graph_chunk_generation_data_overflow);
2095 if (ctx->num_extra_edges)
2096 add_chunk(cf, GRAPH_CHUNKID_EXTRAEDGES,
2097 st_mult(4, ctx->num_extra_edges),
2098 write_graph_chunk_extra_edges);
2099 if (ctx->changed_paths) {
2100 add_chunk(cf, GRAPH_CHUNKID_BLOOMINDEXES,
2101 st_mult(sizeof(uint32_t), ctx->commits.nr),
2102 write_graph_chunk_bloom_indexes);
2103 add_chunk(cf, GRAPH_CHUNKID_BLOOMDATA,
2104 st_add(sizeof(uint32_t) * 3,
2105 ctx->total_bloom_filter_data_size),
2106 write_graph_chunk_bloom_data);
2107 }
2108 if (ctx->num_commit_graphs_after > 1)
2109 add_chunk(cf, GRAPH_CHUNKID_BASE,
2110 st_mult(hashsz, ctx->num_commit_graphs_after - 1),
2111 write_graph_chunk_base);
2112
2113 hashwrite_be32(f, GRAPH_SIGNATURE);
2114
2115 hashwrite_u8(f, GRAPH_VERSION);
2116 hashwrite_u8(f, oid_version(the_hash_algo));
2117 hashwrite_u8(f, get_num_chunks(cf));
2118 hashwrite_u8(f, ctx->num_commit_graphs_after - 1);
2119
2120 if (ctx->report_progress) {
2121 strbuf_addf(&progress_title,
2122 Q_("Writing out commit graph in %d pass",
2123 "Writing out commit graph in %d passes",
2124 get_num_chunks(cf)),
2125 get_num_chunks(cf));
2126 ctx->progress = start_delayed_progress(
2127 progress_title.buf,
2128 st_mult(get_num_chunks(cf), ctx->commits.nr));
2129 }
2130
2131 write_chunkfile(cf, ctx);
2132
2133 stop_progress(&ctx->progress);
2134 strbuf_release(&progress_title);
2135
2136 if (ctx->split && ctx->base_graph_name && ctx->num_commit_graphs_after > 1) {
2137 char *new_base_hash = xstrdup(oid_to_hex(&ctx->new_base_graph->oid));
2138 char *new_base_name = get_split_graph_filename(ctx->new_base_graph->odb, new_base_hash);
2139
2140 free(ctx->commit_graph_filenames_after[ctx->num_commit_graphs_after - 2]);
2141 free(ctx->commit_graph_hash_after[ctx->num_commit_graphs_after - 2]);
2142 ctx->commit_graph_filenames_after[ctx->num_commit_graphs_after - 2] = new_base_name;
2143 ctx->commit_graph_hash_after[ctx->num_commit_graphs_after - 2] = new_base_hash;
2144 }
2145
2146 close_commit_graph(ctx->r->objects);
2147 finalize_hashfile(f, file_hash, FSYNC_COMPONENT_COMMIT_GRAPH,
2148 CSUM_HASH_IN_STREAM | CSUM_FSYNC);
2149 free_chunkfile(cf);
2150
2151 if (ctx->split) {
2152 FILE *chainf = fdopen_lock_file(&lk, "w");
2153 char *final_graph_name;
2154 int result;
2155
2156 close(fd);
2157
2158 if (!chainf) {
2159 error(_("unable to open commit-graph chain file"));
2160 return -1;
2161 }
2162
2163 if (ctx->base_graph_name) {
2164 const char *dest;
2165 int idx = ctx->num_commit_graphs_after - 1;
2166 if (ctx->num_commit_graphs_after > 1)
2167 idx--;
2168
2169 dest = ctx->commit_graph_filenames_after[idx];
2170
2171 if (strcmp(ctx->base_graph_name, dest)) {
2172 result = rename(ctx->base_graph_name, dest);
2173
2174 if (result) {
2175 error(_("failed to rename base commit-graph file"));
2176 return -1;
2177 }
2178 }
2179 } else {
2180 char *graph_name = get_commit_graph_filename(ctx->odb);
2181 unlink(graph_name);
2182 free(graph_name);
2183 }
2184
2185 free(ctx->commit_graph_hash_after[ctx->num_commit_graphs_after - 1]);
2186 ctx->commit_graph_hash_after[ctx->num_commit_graphs_after - 1] = xstrdup(hash_to_hex(file_hash));
2187 final_graph_name = get_split_graph_filename(ctx->odb,
2188 ctx->commit_graph_hash_after[ctx->num_commit_graphs_after - 1]);
2189 free(ctx->commit_graph_filenames_after[ctx->num_commit_graphs_after - 1]);
2190 ctx->commit_graph_filenames_after[ctx->num_commit_graphs_after - 1] = final_graph_name;
2191
2192 result = rename(ctx->graph_name, final_graph_name);
2193
2194 for (i = 0; i < ctx->num_commit_graphs_after; i++)
2195 fprintf(get_lock_file_fp(&lk), "%s\n", ctx->commit_graph_hash_after[i]);
2196
2197 if (result) {
2198 error(_("failed to rename temporary commit-graph file"));
2199 return -1;
2200 }
2201 }
2202
2203 commit_lock_file(&lk);
2204
2205 return 0;
2206 }
2207
2208 static void split_graph_merge_strategy(struct write_commit_graph_context *ctx)
2209 {
2210 struct commit_graph *g;
2211 uint32_t num_commits;
2212 enum commit_graph_split_flags flags = COMMIT_GRAPH_SPLIT_UNSPECIFIED;
2213 uint32_t i;
2214
2215 int max_commits = 0;
2216 int size_mult = 2;
2217
2218 if (ctx->opts) {
2219 max_commits = ctx->opts->max_commits;
2220
2221 if (ctx->opts->size_multiple)
2222 size_mult = ctx->opts->size_multiple;
2223
2224 flags = ctx->opts->split_flags;
2225 }
2226
2227 g = ctx->r->objects->commit_graph;
2228 num_commits = ctx->commits.nr;
2229 if (flags == COMMIT_GRAPH_SPLIT_REPLACE)
2230 ctx->num_commit_graphs_after = 1;
2231 else
2232 ctx->num_commit_graphs_after = ctx->num_commit_graphs_before + 1;
2233
2234 if (flags != COMMIT_GRAPH_SPLIT_MERGE_PROHIBITED &&
2235 flags != COMMIT_GRAPH_SPLIT_REPLACE) {
2236 while (g && (g->num_commits <= st_mult(size_mult, num_commits) ||
2237 (max_commits && num_commits > max_commits))) {
2238 if (g->odb != ctx->odb)
2239 break;
2240
2241 if (unsigned_add_overflows(num_commits, g->num_commits))
2242 die(_("cannot merge graphs with %"PRIuMAX", "
2243 "%"PRIuMAX" commits"),
2244 (uintmax_t)num_commits,
2245 (uintmax_t)g->num_commits);
2246 num_commits += g->num_commits;
2247 g = g->base_graph;
2248
2249 ctx->num_commit_graphs_after--;
2250 }
2251 }
2252
2253 if (flags != COMMIT_GRAPH_SPLIT_REPLACE)
2254 ctx->new_base_graph = g;
2255 else if (ctx->num_commit_graphs_after != 1)
2256 BUG("split_graph_merge_strategy: num_commit_graphs_after "
2257 "should be 1 with --split=replace");
2258
2259 if (ctx->num_commit_graphs_after == 2) {
2260 char *old_graph_name = get_commit_graph_filename(g->odb);
2261
2262 if (!strcmp(g->filename, old_graph_name) &&
2263 g->odb != ctx->odb) {
2264 ctx->num_commit_graphs_after = 1;
2265 ctx->new_base_graph = NULL;
2266 }
2267
2268 free(old_graph_name);
2269 }
2270
2271 CALLOC_ARRAY(ctx->commit_graph_filenames_after, ctx->num_commit_graphs_after);
2272 CALLOC_ARRAY(ctx->commit_graph_hash_after, ctx->num_commit_graphs_after);
2273
2274 for (i = 0; i < ctx->num_commit_graphs_after &&
2275 i < ctx->num_commit_graphs_before; i++)
2276 ctx->commit_graph_filenames_after[i] = xstrdup(ctx->commit_graph_filenames_before[i]);
2277
2278 i = ctx->num_commit_graphs_before - 1;
2279 g = ctx->r->objects->commit_graph;
2280
2281 while (g) {
2282 if (i < ctx->num_commit_graphs_after)
2283 ctx->commit_graph_hash_after[i] = xstrdup(oid_to_hex(&g->oid));
2284
2285 /*
2286 * If the topmost remaining layer has generation data chunk, the
2287 * resultant layer also has generation data chunk.
2288 */
2289 if (i == ctx->num_commit_graphs_after - 2)
2290 ctx->write_generation_data = !!g->chunk_generation_data;
2291
2292 i--;
2293 g = g->base_graph;
2294 }
2295 }
2296
2297 static void merge_commit_graph(struct write_commit_graph_context *ctx,
2298 struct commit_graph *g)
2299 {
2300 uint32_t i;
2301 uint32_t offset = g->num_commits_in_base;
2302
2303 if (unsigned_add_overflows(ctx->commits.nr, g->num_commits))
2304 die(_("cannot merge graph %s, too many commits: %"PRIuMAX),
2305 oid_to_hex(&g->oid),
2306 (uintmax_t)st_add(ctx->commits.nr, g->num_commits));
2307
2308 ALLOC_GROW(ctx->commits.list, ctx->commits.nr + g->num_commits, ctx->commits.alloc);
2309
2310 for (i = 0; i < g->num_commits; i++) {
2311 struct object_id oid;
2312 struct commit *result;
2313
2314 display_progress(ctx->progress, i + 1);
2315
2316 load_oid_from_graph(g, i + offset, &oid);
2317
2318 /* only add commits if they still exist in the repo */
2319 result = lookup_commit_reference_gently(ctx->r, &oid, 1);
2320
2321 if (result) {
2322 ctx->commits.list[ctx->commits.nr] = result;
2323 ctx->commits.nr++;
2324 }
2325 }
2326 }
2327
2328 static int commit_compare(const void *_a, const void *_b)
2329 {
2330 const struct commit *a = *(const struct commit **)_a;
2331 const struct commit *b = *(const struct commit **)_b;
2332 return oidcmp(&a->object.oid, &b->object.oid);
2333 }
2334
2335 static void sort_and_scan_merged_commits(struct write_commit_graph_context *ctx)
2336 {
2337 uint32_t i, dedup_i = 0;
2338
2339 if (ctx->report_progress)
2340 ctx->progress = start_delayed_progress(
2341 _("Scanning merged commits"),
2342 ctx->commits.nr);
2343
2344 QSORT(ctx->commits.list, ctx->commits.nr, commit_compare);
2345
2346 ctx->num_extra_edges = 0;
2347 for (i = 0; i < ctx->commits.nr; i++) {
2348 display_progress(ctx->progress, i + 1);
2349
2350 if (i && oideq(&ctx->commits.list[i - 1]->object.oid,
2351 &ctx->commits.list[i]->object.oid)) {
2352 /*
2353 * Silently ignore duplicates. These were likely
2354 * created due to a commit appearing in multiple
2355 * layers of the chain, which is unexpected but
2356 * not invalid. We should make sure there is a
2357 * unique copy in the new layer.
2358 */
2359 } else {
2360 unsigned int num_parents;
2361
2362 ctx->commits.list[dedup_i] = ctx->commits.list[i];
2363 dedup_i++;
2364
2365 num_parents = commit_list_count(ctx->commits.list[i]->parents);
2366 if (num_parents > 2)
2367 ctx->num_extra_edges += num_parents - 1;
2368 }
2369 }
2370
2371 ctx->commits.nr = dedup_i;
2372
2373 stop_progress(&ctx->progress);
2374 }
2375
2376 static void merge_commit_graphs(struct write_commit_graph_context *ctx)
2377 {
2378 struct commit_graph *g = ctx->r->objects->commit_graph;
2379 uint32_t current_graph_number = ctx->num_commit_graphs_before;
2380
2381 while (g && current_graph_number >= ctx->num_commit_graphs_after) {
2382 current_graph_number--;
2383
2384 if (ctx->report_progress)
2385 ctx->progress = start_delayed_progress(_("Merging commit-graph"), 0);
2386
2387 merge_commit_graph(ctx, g);
2388 stop_progress(&ctx->progress);
2389
2390 g = g->base_graph;
2391 }
2392
2393 if (g) {
2394 ctx->new_base_graph = g;
2395 ctx->new_num_commits_in_base = g->num_commits + g->num_commits_in_base;
2396 }
2397
2398 if (ctx->new_base_graph)
2399 ctx->base_graph_name = xstrdup(ctx->new_base_graph->filename);
2400
2401 sort_and_scan_merged_commits(ctx);
2402 }
2403
2404 static void mark_commit_graphs(struct write_commit_graph_context *ctx)
2405 {
2406 uint32_t i;
2407 time_t now = time(NULL);
2408
2409 for (i = ctx->num_commit_graphs_after - 1; i < ctx->num_commit_graphs_before; i++) {
2410 struct stat st;
2411 struct utimbuf updated_time;
2412
2413 if (stat(ctx->commit_graph_filenames_before[i], &st) < 0)
2414 continue;
2415
2416 updated_time.actime = st.st_atime;
2417 updated_time.modtime = now;
2418 utime(ctx->commit_graph_filenames_before[i], &updated_time);
2419 }
2420 }
2421
2422 static void expire_commit_graphs(struct write_commit_graph_context *ctx)
2423 {
2424 struct strbuf path = STRBUF_INIT;
2425 DIR *dir;
2426 struct dirent *de;
2427 size_t dirnamelen;
2428 timestamp_t expire_time = time(NULL);
2429
2430 if (ctx->opts && ctx->opts->expire_time)
2431 expire_time = ctx->opts->expire_time;
2432 if (!ctx->split) {
2433 char *chain_file_name = get_commit_graph_chain_filename(ctx->odb);
2434 unlink(chain_file_name);
2435 free(chain_file_name);
2436 ctx->num_commit_graphs_after = 0;
2437 }
2438
2439 strbuf_addstr(&path, ctx->odb->path);
2440 strbuf_addstr(&path, "/info/commit-graphs");
2441 dir = opendir(path.buf);
2442
2443 if (!dir)
2444 goto out;
2445
2446 strbuf_addch(&path, '/');
2447 dirnamelen = path.len;
2448 while ((de = readdir(dir)) != NULL) {
2449 struct stat st;
2450 uint32_t i, found = 0;
2451
2452 strbuf_setlen(&path, dirnamelen);
2453 strbuf_addstr(&path, de->d_name);
2454
2455 if (stat(path.buf, &st) < 0)
2456 continue;
2457
2458 if (st.st_mtime > expire_time)
2459 continue;
2460 if (path.len < 6 || strcmp(path.buf + path.len - 6, ".graph"))
2461 continue;
2462
2463 for (i = 0; i < ctx->num_commit_graphs_after; i++) {
2464 if (!strcmp(ctx->commit_graph_filenames_after[i],
2465 path.buf)) {
2466 found = 1;
2467 break;
2468 }
2469 }
2470
2471 if (!found)
2472 unlink(path.buf);
2473 }
2474
2475 out:
2476 if(dir)
2477 closedir(dir);
2478 strbuf_release(&path);
2479 }
2480
2481 int write_commit_graph(struct object_directory *odb,
2482 const struct string_list *const pack_indexes,
2483 struct oidset *commits,
2484 enum commit_graph_write_flags flags,
2485 const struct commit_graph_opts *opts)
2486 {
2487 struct repository *r = the_repository;
2488 struct write_commit_graph_context *ctx;
2489 uint32_t i;
2490 int res = 0;
2491 int replace = 0;
2492 struct bloom_filter_settings bloom_settings = DEFAULT_BLOOM_FILTER_SETTINGS;
2493 struct topo_level_slab topo_levels;
2494
2495 prepare_repo_settings(r);
2496 if (!r->settings.core_commit_graph) {
2497 warning(_("attempting to write a commit-graph, but 'core.commitGraph' is disabled"));
2498 return 0;
2499 }
2500 if (!commit_graph_compatible(r))
2501 return 0;
2502
2503 CALLOC_ARRAY(ctx, 1);
2504 ctx->r = r;
2505 ctx->odb = odb;
2506 ctx->append = flags & COMMIT_GRAPH_WRITE_APPEND ? 1 : 0;
2507 ctx->report_progress = flags & COMMIT_GRAPH_WRITE_PROGRESS ? 1 : 0;
2508 ctx->split = flags & COMMIT_GRAPH_WRITE_SPLIT ? 1 : 0;
2509 ctx->opts = opts;
2510 ctx->total_bloom_filter_data_size = 0;
2511 ctx->write_generation_data = (get_configured_generation_version(r) == 2);
2512 ctx->num_generation_data_overflows = 0;
2513
2514 bloom_settings.bits_per_entry = git_env_ulong("GIT_TEST_BLOOM_SETTINGS_BITS_PER_ENTRY",
2515 bloom_settings.bits_per_entry);
2516 bloom_settings.num_hashes = git_env_ulong("GIT_TEST_BLOOM_SETTINGS_NUM_HASHES",
2517 bloom_settings.num_hashes);
2518 bloom_settings.max_changed_paths = git_env_ulong("GIT_TEST_BLOOM_SETTINGS_MAX_CHANGED_PATHS",
2519 bloom_settings.max_changed_paths);
2520 ctx->bloom_settings = &bloom_settings;
2521
2522 init_topo_level_slab(&topo_levels);
2523 ctx->topo_levels = &topo_levels;
2524
2525 prepare_commit_graph(ctx->r);
2526 if (ctx->r->objects->commit_graph) {
2527 struct commit_graph *g = ctx->r->objects->commit_graph;
2528
2529 while (g) {
2530 g->topo_levels = &topo_levels;
2531 g = g->base_graph;
2532 }
2533 }
2534
2535 if (flags & COMMIT_GRAPH_WRITE_BLOOM_FILTERS)
2536 ctx->changed_paths = 1;
2537 if (!(flags & COMMIT_GRAPH_NO_WRITE_BLOOM_FILTERS)) {
2538 struct commit_graph *g;
2539
2540 g = ctx->r->objects->commit_graph;
2541
2542 /* We have changed-paths already. Keep them in the next graph */
2543 if (g && g->chunk_bloom_data) {
2544 ctx->changed_paths = 1;
2545 ctx->bloom_settings = g->bloom_filter_settings;
2546 }
2547 }
2548
2549 if (ctx->split) {
2550 struct commit_graph *g = ctx->r->objects->commit_graph;
2551
2552 while (g) {
2553 ctx->num_commit_graphs_before++;
2554 g = g->base_graph;
2555 }
2556
2557 if (ctx->num_commit_graphs_before) {
2558 ALLOC_ARRAY(ctx->commit_graph_filenames_before, ctx->num_commit_graphs_before);
2559 i = ctx->num_commit_graphs_before;
2560 g = ctx->r->objects->commit_graph;
2561
2562 while (g) {
2563 ctx->commit_graph_filenames_before[--i] = xstrdup(g->filename);
2564 g = g->base_graph;
2565 }
2566 }
2567
2568 if (ctx->opts)
2569 replace = ctx->opts->split_flags & COMMIT_GRAPH_SPLIT_REPLACE;
2570 }
2571
2572 ctx->approx_nr_objects = repo_approximate_object_count(the_repository);
2573
2574 if (ctx->append && ctx->r->objects->commit_graph) {
2575 struct commit_graph *g = ctx->r->objects->commit_graph;
2576 for (i = 0; i < g->num_commits; i++) {
2577 struct object_id oid;
2578 oidread(&oid, g->chunk_oid_lookup + st_mult(g->hash_len, i));
2579 oid_array_append(&ctx->oids, &oid);
2580 }
2581 }
2582
2583 if (pack_indexes) {
2584 ctx->order_by_pack = 1;
2585 if ((res = fill_oids_from_packs(ctx, pack_indexes)))
2586 goto cleanup;
2587 }
2588
2589 if (commits) {
2590 if ((res = fill_oids_from_commits(ctx, commits)))
2591 goto cleanup;
2592 }
2593
2594 if (!pack_indexes && !commits) {
2595 ctx->order_by_pack = 1;
2596 fill_oids_from_all_packs(ctx);
2597 }
2598
2599 close_reachable(ctx);
2600
2601 copy_oids_to_commits(ctx);
2602
2603 if (ctx->commits.nr >= GRAPH_EDGE_LAST_MASK) {
2604 error(_("too many commits to write graph"));
2605 res = -1;
2606 goto cleanup;
2607 }
2608
2609 if (!ctx->commits.nr && !replace)
2610 goto cleanup;
2611
2612 if (ctx->split) {
2613 split_graph_merge_strategy(ctx);
2614
2615 if (!replace)
2616 merge_commit_graphs(ctx);
2617 } else
2618 ctx->num_commit_graphs_after = 1;
2619
2620 ctx->trust_generation_numbers = validate_mixed_generation_chain(ctx->r->objects->commit_graph);
2621
2622 compute_topological_levels(ctx);
2623 if (ctx->write_generation_data)
2624 compute_generation_numbers(ctx);
2625
2626 if (ctx->changed_paths)
2627 compute_bloom_filters(ctx);
2628
2629 res = write_commit_graph_file(ctx);
2630
2631 if (ctx->split)
2632 mark_commit_graphs(ctx);
2633
2634 expire_commit_graphs(ctx);
2635
2636 cleanup:
2637 free(ctx->graph_name);
2638 free(ctx->base_graph_name);
2639 free(ctx->commits.list);
2640 oid_array_clear(&ctx->oids);
2641 clear_topo_level_slab(&topo_levels);
2642
2643 if (ctx->commit_graph_filenames_after) {
2644 for (i = 0; i < ctx->num_commit_graphs_after; i++) {
2645 free(ctx->commit_graph_filenames_after[i]);
2646 free(ctx->commit_graph_hash_after[i]);
2647 }
2648
2649 for (i = 0; i < ctx->num_commit_graphs_before; i++)
2650 free(ctx->commit_graph_filenames_before[i]);
2651
2652 free(ctx->commit_graph_filenames_after);
2653 free(ctx->commit_graph_filenames_before);
2654 free(ctx->commit_graph_hash_after);
2655 }
2656
2657 free(ctx);
2658
2659 return res;
2660 }
2661
2662 #define VERIFY_COMMIT_GRAPH_ERROR_HASH 2
2663 static int verify_commit_graph_error;
2664
2665 __attribute__((format (printf, 1, 2)))
2666 static void graph_report(const char *fmt, ...)
2667 {
2668 va_list ap;
2669
2670 verify_commit_graph_error = 1;
2671 va_start(ap, fmt);
2672 vfprintf(stderr, fmt, ap);
2673 fprintf(stderr, "\n");
2674 va_end(ap);
2675 }
2676
2677 static int commit_graph_checksum_valid(struct commit_graph *g)
2678 {
2679 return hashfile_checksum_valid(g->data, g->data_len);
2680 }
2681
2682 static int verify_one_commit_graph(struct repository *r,
2683 struct commit_graph *g,
2684 struct progress *progress,
2685 uint64_t *seen)
2686 {
2687 uint32_t i, cur_fanout_pos = 0;
2688 struct object_id prev_oid, cur_oid;
2689 struct commit *seen_gen_zero = NULL;
2690 struct commit *seen_gen_non_zero = NULL;
2691
2692 verify_commit_graph_error = verify_commit_graph_lite(g);
2693 if (verify_commit_graph_error)
2694 return verify_commit_graph_error;
2695
2696 if (!commit_graph_checksum_valid(g)) {
2697 graph_report(_("the commit-graph file has incorrect checksum and is likely corrupt"));
2698 verify_commit_graph_error = VERIFY_COMMIT_GRAPH_ERROR_HASH;
2699 }
2700
2701 for (i = 0; i < g->num_commits; i++) {
2702 struct commit *graph_commit;
2703
2704 oidread(&cur_oid, g->chunk_oid_lookup + st_mult(g->hash_len, i));
2705
2706 if (i && oidcmp(&prev_oid, &cur_oid) >= 0)
2707 graph_report(_("commit-graph has incorrect OID order: %s then %s"),
2708 oid_to_hex(&prev_oid),
2709 oid_to_hex(&cur_oid));
2710
2711 oidcpy(&prev_oid, &cur_oid);
2712
2713 while (cur_oid.hash[0] > cur_fanout_pos) {
2714 uint32_t fanout_value = get_be32(g->chunk_oid_fanout + cur_fanout_pos);
2715
2716 if (i != fanout_value)
2717 graph_report(_("commit-graph has incorrect fanout value: fanout[%d] = %u != %u"),
2718 cur_fanout_pos, fanout_value, i);
2719 cur_fanout_pos++;
2720 }
2721
2722 graph_commit = lookup_commit(r, &cur_oid);
2723 if (!parse_commit_in_graph_one(r, g, graph_commit))
2724 graph_report(_("failed to parse commit %s from commit-graph"),
2725 oid_to_hex(&cur_oid));
2726 }
2727
2728 while (cur_fanout_pos < 256) {
2729 uint32_t fanout_value = get_be32(g->chunk_oid_fanout + cur_fanout_pos);
2730
2731 if (g->num_commits != fanout_value)
2732 graph_report(_("commit-graph has incorrect fanout value: fanout[%d] = %u != %u"),
2733 cur_fanout_pos, fanout_value, i);
2734
2735 cur_fanout_pos++;
2736 }
2737
2738 if (verify_commit_graph_error & ~VERIFY_COMMIT_GRAPH_ERROR_HASH)
2739 return verify_commit_graph_error;
2740
2741 for (i = 0; i < g->num_commits; i++) {
2742 struct commit *graph_commit, *odb_commit;
2743 struct commit_list *graph_parents, *odb_parents;
2744 timestamp_t max_generation = 0;
2745 timestamp_t generation;
2746
2747 display_progress(progress, ++(*seen));
2748 oidread(&cur_oid, g->chunk_oid_lookup + st_mult(g->hash_len, i));
2749
2750 graph_commit = lookup_commit(r, &cur_oid);
2751 odb_commit = (struct commit *)create_object(r, &cur_oid, alloc_commit_node(r));
2752 if (repo_parse_commit_internal(r, odb_commit, 0, 0)) {
2753 graph_report(_("failed to parse commit %s from object database for commit-graph"),
2754 oid_to_hex(&cur_oid));
2755 continue;
2756 }
2757
2758 if (!oideq(&get_commit_tree_in_graph_one(r, g, graph_commit)->object.oid,
2759 get_commit_tree_oid(odb_commit)))
2760 graph_report(_("root tree OID for commit %s in commit-graph is %s != %s"),
2761 oid_to_hex(&cur_oid),
2762 oid_to_hex(get_commit_tree_oid(graph_commit)),
2763 oid_to_hex(get_commit_tree_oid(odb_commit)));
2764
2765 graph_parents = graph_commit->parents;
2766 odb_parents = odb_commit->parents;
2767
2768 while (graph_parents) {
2769 if (!odb_parents) {
2770 graph_report(_("commit-graph parent list for commit %s is too long"),
2771 oid_to_hex(&cur_oid));
2772 break;
2773 }
2774
2775 /* parse parent in case it is in a base graph */
2776 parse_commit_in_graph_one(r, g, graph_parents->item);
2777
2778 if (!oideq(&graph_parents->item->object.oid, &odb_parents->item->object.oid))
2779 graph_report(_("commit-graph parent for %s is %s != %s"),
2780 oid_to_hex(&cur_oid),
2781 oid_to_hex(&graph_parents->item->object.oid),
2782 oid_to_hex(&odb_parents->item->object.oid));
2783
2784 generation = commit_graph_generation_from_graph(graph_parents->item);
2785 if (generation > max_generation)
2786 max_generation = generation;
2787
2788 graph_parents = graph_parents->next;
2789 odb_parents = odb_parents->next;
2790 }
2791
2792 if (odb_parents)
2793 graph_report(_("commit-graph parent list for commit %s terminates early"),
2794 oid_to_hex(&cur_oid));
2795
2796 if (commit_graph_generation_from_graph(graph_commit))
2797 seen_gen_non_zero = graph_commit;
2798 else
2799 seen_gen_zero = graph_commit;
2800
2801 if (seen_gen_zero)
2802 continue;
2803
2804 /*
2805 * If we are using topological level and one of our parents has
2806 * generation GENERATION_NUMBER_V1_MAX, then our generation is
2807 * also GENERATION_NUMBER_V1_MAX. Decrement to avoid extra logic
2808 * in the following condition.
2809 */
2810 if (!g->read_generation_data && max_generation == GENERATION_NUMBER_V1_MAX)
2811 max_generation--;
2812
2813 generation = commit_graph_generation(graph_commit);
2814 if (generation < max_generation + 1)
2815 graph_report(_("commit-graph generation for commit %s is %"PRItime" < %"PRItime),
2816 oid_to_hex(&cur_oid),
2817 generation,
2818 max_generation + 1);
2819
2820 if (graph_commit->date != odb_commit->date)
2821 graph_report(_("commit date for commit %s in commit-graph is %"PRItime" != %"PRItime),
2822 oid_to_hex(&cur_oid),
2823 graph_commit->date,
2824 odb_commit->date);
2825 }
2826
2827 if (seen_gen_zero && seen_gen_non_zero)
2828 graph_report(_("commit-graph has both zero and non-zero "
2829 "generations (e.g., commits '%s' and '%s')"),
2830 oid_to_hex(&seen_gen_zero->object.oid),
2831 oid_to_hex(&seen_gen_non_zero->object.oid));
2832
2833 return verify_commit_graph_error;
2834 }
2835
2836 int verify_commit_graph(struct repository *r, struct commit_graph *g, int flags)
2837 {
2838 struct progress *progress = NULL;
2839 int local_error = 0;
2840 uint64_t seen = 0;
2841
2842 if (!g) {
2843 graph_report("no commit-graph file loaded");
2844 return 1;
2845 }
2846
2847 if (flags & COMMIT_GRAPH_WRITE_PROGRESS) {
2848 uint64_t total = g->num_commits;
2849 if (!(flags & COMMIT_GRAPH_VERIFY_SHALLOW))
2850 total += g->num_commits_in_base;
2851
2852 progress = start_progress(_("Verifying commits in commit graph"),
2853 total);
2854 }
2855
2856 for (; g; g = g->base_graph) {
2857 local_error |= verify_one_commit_graph(r, g, progress, &seen);
2858 if (flags & COMMIT_GRAPH_VERIFY_SHALLOW)
2859 break;
2860 }
2861
2862 stop_progress(&progress);
2863
2864 return local_error;
2865 }
2866
2867 void free_commit_graph(struct commit_graph *g)
2868 {
2869 while (g) {
2870 struct commit_graph *next = g->base_graph;
2871
2872 if (g->data)
2873 munmap((void *)g->data, g->data_len);
2874 free(g->filename);
2875 free(g->bloom_filter_settings);
2876 free(g);
2877
2878 g = next;
2879 }
2880 }
2881
2882 void disable_commit_graph(struct repository *r)
2883 {
2884 r->commit_graph_disabled = 1;
2885 }
Mirror of Junio's Git repository with all the branches