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