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