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