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