1 #include "git-compat-util.h"
12 #include "hash-lookup.h"
13 #include "commit-graph.h"
14 #include "object-file.h"
15 #include "object-store.h"
16 #include "oid-array.h"
19 #include "replace-object.h"
22 #include "commit-slab.h"
24 #include "json-writer.h"
27 #include "chunk-format.h"
30 void git_test_write_commit_graph_or_die(void)
33 if (!git_env_bool(GIT_TEST_COMMIT_GRAPH
, 0))
36 if (git_env_bool(GIT_TEST_COMMIT_GRAPH_CHANGED_PATHS
, 0))
37 flags
= COMMIT_GRAPH_WRITE_BLOOM_FILTERS
;
39 if (write_commit_graph_reachable(the_repository
->objects
->odb
,
41 die("failed to write commit-graph under GIT_TEST_COMMIT_GRAPH");
44 #define GRAPH_SIGNATURE 0x43475048 /* "CGPH" */
45 #define GRAPH_CHUNKID_OIDFANOUT 0x4f494446 /* "OIDF" */
46 #define GRAPH_CHUNKID_OIDLOOKUP 0x4f49444c /* "OIDL" */
47 #define GRAPH_CHUNKID_DATA 0x43444154 /* "CDAT" */
48 #define GRAPH_CHUNKID_GENERATION_DATA 0x47444132 /* "GDA2" */
49 #define GRAPH_CHUNKID_GENERATION_DATA_OVERFLOW 0x47444f32 /* "GDO2" */
50 #define GRAPH_CHUNKID_EXTRAEDGES 0x45444745 /* "EDGE" */
51 #define GRAPH_CHUNKID_BLOOMINDEXES 0x42494458 /* "BIDX" */
52 #define GRAPH_CHUNKID_BLOOMDATA 0x42444154 /* "BDAT" */
53 #define GRAPH_CHUNKID_BASE 0x42415345 /* "BASE" */
55 #define GRAPH_DATA_WIDTH (the_hash_algo->rawsz + 16)
57 #define GRAPH_VERSION_1 0x1
58 #define GRAPH_VERSION GRAPH_VERSION_1
60 #define GRAPH_EXTRA_EDGES_NEEDED 0x80000000
61 #define GRAPH_EDGE_LAST_MASK 0x7fffffff
62 #define GRAPH_PARENT_NONE 0x70000000
64 #define GRAPH_LAST_EDGE 0x80000000
66 #define GRAPH_HEADER_SIZE 8
67 #define GRAPH_FANOUT_SIZE (4 * 256)
68 #define GRAPH_MIN_SIZE (GRAPH_HEADER_SIZE + 4 * CHUNK_TOC_ENTRY_SIZE \
69 + GRAPH_FANOUT_SIZE + the_hash_algo->rawsz)
71 #define CORRECTED_COMMIT_DATE_OFFSET_OVERFLOW (1ULL << 31)
73 /* Remember to update object flag allocation in object.h */
74 #define REACHABLE (1u<<15)
76 define_commit_slab(topo_level_slab
, uint32_t);
78 /* Keep track of the order in which commits are added to our list. */
79 define_commit_slab(commit_pos
, int);
80 static struct commit_pos commit_pos
= COMMIT_SLAB_INIT(1, commit_pos
);
82 static void set_commit_pos(struct repository
*r
, const struct object_id
*oid
)
84 static int32_t max_pos
;
85 struct commit
*commit
= lookup_commit(r
, oid
);
88 return; /* should never happen, but be lenient */
90 *commit_pos_at(&commit_pos
, commit
) = max_pos
++;
93 static int commit_pos_cmp(const void *va
, const void *vb
)
95 const struct commit
*a
= *(const struct commit
**)va
;
96 const struct commit
*b
= *(const struct commit
**)vb
;
97 return commit_pos_at(&commit_pos
, a
) -
98 commit_pos_at(&commit_pos
, b
);
101 define_commit_slab(commit_graph_data_slab
, struct commit_graph_data
);
102 static struct commit_graph_data_slab commit_graph_data_slab
=
103 COMMIT_SLAB_INIT(1, commit_graph_data_slab
);
105 static int get_configured_generation_version(struct repository
*r
)
108 repo_config_get_int(r
, "commitgraph.generationversion", &version
);
112 uint32_t commit_graph_position(const struct commit
*c
)
114 struct commit_graph_data
*data
=
115 commit_graph_data_slab_peek(&commit_graph_data_slab
, c
);
117 return data
? data
->graph_pos
: COMMIT_NOT_FROM_GRAPH
;
120 timestamp_t
commit_graph_generation(const struct commit
*c
)
122 struct commit_graph_data
*data
=
123 commit_graph_data_slab_peek(&commit_graph_data_slab
, c
);
125 if (data
&& data
->generation
)
126 return data
->generation
;
128 return GENERATION_NUMBER_INFINITY
;
131 static struct commit_graph_data
*commit_graph_data_at(const struct commit
*c
)
133 unsigned int i
, nth_slab
;
134 struct commit_graph_data
*data
=
135 commit_graph_data_slab_peek(&commit_graph_data_slab
, c
);
140 nth_slab
= c
->index
/ commit_graph_data_slab
.slab_size
;
141 data
= commit_graph_data_slab_at(&commit_graph_data_slab
, c
);
144 * commit-slab initializes elements with zero, overwrite this with
145 * COMMIT_NOT_FROM_GRAPH for graph_pos.
147 * We avoid initializing generation with checking if graph position
148 * is not COMMIT_NOT_FROM_GRAPH.
150 for (i
= 0; i
< commit_graph_data_slab
.slab_size
; i
++) {
151 commit_graph_data_slab
.slab
[nth_slab
][i
].graph_pos
=
152 COMMIT_NOT_FROM_GRAPH
;
159 * Should be used only while writing commit-graph as it compares
160 * generation value of commits by directly accessing commit-slab.
162 static int commit_gen_cmp(const void *va
, const void *vb
)
164 const struct commit
*a
= *(const struct commit
**)va
;
165 const struct commit
*b
= *(const struct commit
**)vb
;
167 const timestamp_t generation_a
= commit_graph_data_at(a
)->generation
;
168 const timestamp_t generation_b
= commit_graph_data_at(b
)->generation
;
169 /* lower generation commits first */
170 if (generation_a
< generation_b
)
172 else if (generation_a
> generation_b
)
175 /* use date as a heuristic when generations are equal */
176 if (a
->date
< b
->date
)
178 else if (a
->date
> b
->date
)
183 char *get_commit_graph_filename(struct object_directory
*obj_dir
)
185 return xstrfmt("%s/info/commit-graph", obj_dir
->path
);
188 static char *get_split_graph_filename(struct object_directory
*odb
,
191 return xstrfmt("%s/info/commit-graphs/graph-%s.graph", odb
->path
,
195 char *get_commit_graph_chain_filename(struct object_directory
*odb
)
197 return xstrfmt("%s/info/commit-graphs/commit-graph-chain", odb
->path
);
200 static struct commit_graph
*alloc_commit_graph(void)
202 struct commit_graph
*g
= xcalloc(1, sizeof(*g
));
207 extern int read_replace_refs
;
209 static int commit_graph_compatible(struct repository
*r
)
214 if (read_replace_refs
) {
215 prepare_replace_object(r
);
216 if (hashmap_get_size(&r
->objects
->replace_map
->map
))
220 prepare_commit_graft(r
);
221 if (r
->parsed_objects
&&
222 (r
->parsed_objects
->grafts_nr
|| r
->parsed_objects
->substituted_parent
))
224 if (is_repository_shallow(r
))
230 int open_commit_graph(const char *graph_file
, int *fd
, struct stat
*st
)
232 *fd
= git_open(graph_file
);
235 if (fstat(*fd
, st
)) {
242 struct commit_graph
*load_commit_graph_one_fd_st(struct repository
*r
,
243 int fd
, struct stat
*st
,
244 struct object_directory
*odb
)
248 struct commit_graph
*ret
;
250 graph_size
= xsize_t(st
->st_size
);
252 if (graph_size
< GRAPH_MIN_SIZE
) {
254 error(_("commit-graph file is too small"));
257 graph_map
= xmmap(NULL
, graph_size
, PROT_READ
, MAP_PRIVATE
, fd
, 0);
259 prepare_repo_settings(r
);
260 ret
= parse_commit_graph(&r
->settings
, graph_map
, graph_size
);
265 munmap(graph_map
, graph_size
);
270 static int verify_commit_graph_lite(struct commit_graph
*g
)
273 * Basic validation shared between parse_commit_graph()
274 * which'll be called every time the graph is used, and the
275 * much more expensive verify_commit_graph() used by
276 * "commit-graph verify".
278 * There should only be very basic checks here to ensure that
279 * we don't e.g. segfault in fill_commit_in_graph(), but
280 * because this is a very hot codepath nothing that e.g. loops
281 * over g->num_commits, or runs a checksum on the commit-graph
284 if (!g
->chunk_oid_fanout
) {
285 error("commit-graph is missing the OID Fanout chunk");
288 if (!g
->chunk_oid_lookup
) {
289 error("commit-graph is missing the OID Lookup chunk");
292 if (!g
->chunk_commit_data
) {
293 error("commit-graph is missing the Commit Data chunk");
300 static int graph_read_oid_lookup(const unsigned char *chunk_start
,
301 size_t chunk_size
, void *data
)
303 struct commit_graph
*g
= data
;
304 g
->chunk_oid_lookup
= chunk_start
;
305 g
->num_commits
= chunk_size
/ g
->hash_len
;
309 static int graph_read_bloom_data(const unsigned char *chunk_start
,
310 size_t chunk_size
, void *data
)
312 struct commit_graph
*g
= data
;
313 uint32_t hash_version
;
314 g
->chunk_bloom_data
= chunk_start
;
315 hash_version
= get_be32(chunk_start
);
317 if (hash_version
!= 1)
320 g
->bloom_filter_settings
= xmalloc(sizeof(struct bloom_filter_settings
));
321 g
->bloom_filter_settings
->hash_version
= hash_version
;
322 g
->bloom_filter_settings
->num_hashes
= get_be32(chunk_start
+ 4);
323 g
->bloom_filter_settings
->bits_per_entry
= get_be32(chunk_start
+ 8);
324 g
->bloom_filter_settings
->max_changed_paths
= DEFAULT_BLOOM_MAX_CHANGES
;
329 struct commit_graph
*parse_commit_graph(struct repo_settings
*s
,
330 void *graph_map
, size_t graph_size
)
332 const unsigned char *data
;
333 struct commit_graph
*graph
;
334 uint32_t graph_signature
;
335 unsigned char graph_version
, hash_version
;
336 struct chunkfile
*cf
= NULL
;
341 if (graph_size
< GRAPH_MIN_SIZE
)
344 data
= (const unsigned char *)graph_map
;
346 graph_signature
= get_be32(data
);
347 if (graph_signature
!= GRAPH_SIGNATURE
) {
348 error(_("commit-graph signature %X does not match signature %X"),
349 graph_signature
, GRAPH_SIGNATURE
);
353 graph_version
= *(unsigned char*)(data
+ 4);
354 if (graph_version
!= GRAPH_VERSION
) {
355 error(_("commit-graph version %X does not match version %X"),
356 graph_version
, GRAPH_VERSION
);
360 hash_version
= *(unsigned char*)(data
+ 5);
361 if (hash_version
!= oid_version(the_hash_algo
)) {
362 error(_("commit-graph hash version %X does not match version %X"),
363 hash_version
, oid_version(the_hash_algo
));
367 graph
= alloc_commit_graph();
369 graph
->hash_len
= the_hash_algo
->rawsz
;
370 graph
->num_chunks
= *(unsigned char*)(data
+ 6);
371 graph
->data
= graph_map
;
372 graph
->data_len
= graph_size
;
374 if (graph_size
< GRAPH_HEADER_SIZE
+
375 (graph
->num_chunks
+ 1) * CHUNK_TOC_ENTRY_SIZE
+
376 GRAPH_FANOUT_SIZE
+ the_hash_algo
->rawsz
) {
377 error(_("commit-graph file is too small to hold %u chunks"),
383 cf
= init_chunkfile(NULL
);
385 if (read_table_of_contents(cf
, graph
->data
, graph_size
,
386 GRAPH_HEADER_SIZE
, graph
->num_chunks
))
387 goto free_and_return
;
389 pair_chunk(cf
, GRAPH_CHUNKID_OIDFANOUT
,
390 (const unsigned char **)&graph
->chunk_oid_fanout
);
391 read_chunk(cf
, GRAPH_CHUNKID_OIDLOOKUP
, graph_read_oid_lookup
, graph
);
392 pair_chunk(cf
, GRAPH_CHUNKID_DATA
, &graph
->chunk_commit_data
);
393 pair_chunk(cf
, GRAPH_CHUNKID_EXTRAEDGES
, &graph
->chunk_extra_edges
);
394 pair_chunk(cf
, GRAPH_CHUNKID_BASE
, &graph
->chunk_base_graphs
);
396 if (s
->commit_graph_generation_version
>= 2) {
397 pair_chunk(cf
, GRAPH_CHUNKID_GENERATION_DATA
,
398 &graph
->chunk_generation_data
);
399 pair_chunk(cf
, GRAPH_CHUNKID_GENERATION_DATA_OVERFLOW
,
400 &graph
->chunk_generation_data_overflow
);
402 if (graph
->chunk_generation_data
)
403 graph
->read_generation_data
= 1;
406 if (s
->commit_graph_read_changed_paths
) {
407 pair_chunk(cf
, GRAPH_CHUNKID_BLOOMINDEXES
,
408 &graph
->chunk_bloom_indexes
);
409 read_chunk(cf
, GRAPH_CHUNKID_BLOOMDATA
,
410 graph_read_bloom_data
, graph
);
413 if (graph
->chunk_bloom_indexes
&& graph
->chunk_bloom_data
) {
414 init_bloom_filters();
416 /* We need both the bloom chunks to exist together. Else ignore the data */
417 graph
->chunk_bloom_indexes
= NULL
;
418 graph
->chunk_bloom_data
= NULL
;
419 FREE_AND_NULL(graph
->bloom_filter_settings
);
422 oidread(&graph
->oid
, graph
->data
+ graph
->data_len
- graph
->hash_len
);
424 if (verify_commit_graph_lite(graph
))
425 goto free_and_return
;
432 free(graph
->bloom_filter_settings
);
437 static struct commit_graph
*load_commit_graph_one(struct repository
*r
,
438 const char *graph_file
,
439 struct object_directory
*odb
)
444 struct commit_graph
*g
;
445 int open_ok
= open_commit_graph(graph_file
, &fd
, &st
);
450 g
= load_commit_graph_one_fd_st(r
, fd
, &st
, odb
);
453 g
->filename
= xstrdup(graph_file
);
458 static struct commit_graph
*load_commit_graph_v1(struct repository
*r
,
459 struct object_directory
*odb
)
461 char *graph_name
= get_commit_graph_filename(odb
);
462 struct commit_graph
*g
= load_commit_graph_one(r
, graph_name
, odb
);
468 static int add_graph_to_chain(struct commit_graph
*g
,
469 struct commit_graph
*chain
,
470 struct object_id
*oids
,
473 struct commit_graph
*cur_g
= chain
;
475 if (n
&& !g
->chunk_base_graphs
) {
476 warning(_("commit-graph has no base graphs chunk"));
484 !oideq(&oids
[n
], &cur_g
->oid
) ||
485 !hasheq(oids
[n
].hash
, g
->chunk_base_graphs
+ st_mult(g
->hash_len
, n
))) {
486 warning(_("commit-graph chain does not match"));
490 cur_g
= cur_g
->base_graph
;
493 g
->base_graph
= chain
;
496 if (unsigned_add_overflows(chain
->num_commits
,
497 chain
->num_commits_in_base
)) {
498 warning(_("commit count in base graph too high: %"PRIuMAX
),
499 (uintmax_t)chain
->num_commits_in_base
);
502 g
->num_commits_in_base
= chain
->num_commits
+ chain
->num_commits_in_base
;
508 static struct commit_graph
*load_commit_graph_chain(struct repository
*r
,
509 struct object_directory
*odb
)
511 struct commit_graph
*graph_chain
= NULL
;
512 struct strbuf line
= STRBUF_INIT
;
514 struct object_id
*oids
;
515 int i
= 0, valid
= 1, count
;
516 char *chain_name
= get_commit_graph_chain_filename(odb
);
520 fp
= fopen(chain_name
, "r");
521 stat_res
= stat(chain_name
, &st
);
527 st
.st_size
<= the_hash_algo
->hexsz
) {
532 count
= st
.st_size
/ (the_hash_algo
->hexsz
+ 1);
533 CALLOC_ARRAY(oids
, count
);
537 for (i
= 0; i
< count
; i
++) {
538 struct object_directory
*odb
;
540 if (strbuf_getline_lf(&line
, fp
) == EOF
)
543 if (get_oid_hex(line
.buf
, &oids
[i
])) {
544 warning(_("invalid commit-graph chain: line '%s' not a hash"),
551 for (odb
= r
->objects
->odb
; odb
; odb
= odb
->next
) {
552 char *graph_name
= get_split_graph_filename(odb
, line
.buf
);
553 struct commit_graph
*g
= load_commit_graph_one(r
, graph_name
, odb
);
558 if (add_graph_to_chain(g
, graph_chain
, oids
, i
)) {
568 warning(_("unable to find all commit-graph files"));
575 strbuf_release(&line
);
581 * returns 1 if and only if all graphs in the chain have
582 * corrected commit dates stored in the generation_data chunk.
584 static int validate_mixed_generation_chain(struct commit_graph
*g
)
586 int read_generation_data
= 1;
587 struct commit_graph
*p
= g
;
589 while (read_generation_data
&& p
) {
590 read_generation_data
= p
->read_generation_data
;
594 if (read_generation_data
)
598 g
->read_generation_data
= 0;
605 struct commit_graph
*read_commit_graph_one(struct repository
*r
,
606 struct object_directory
*odb
)
608 struct commit_graph
*g
= load_commit_graph_v1(r
, odb
);
611 g
= load_commit_graph_chain(r
, odb
);
613 validate_mixed_generation_chain(g
);
618 static void prepare_commit_graph_one(struct repository
*r
,
619 struct object_directory
*odb
)
622 if (r
->objects
->commit_graph
)
625 r
->objects
->commit_graph
= read_commit_graph_one(r
, odb
);
629 * Return 1 if commit_graph is non-NULL, and 0 otherwise.
631 * On the first invocation, this function attempts to load the commit
632 * graph if the_repository is configured to have one.
634 static int prepare_commit_graph(struct repository
*r
)
636 struct object_directory
*odb
;
639 * Early return if there is no git dir or if the commit graph is
642 * This must come before the "already attempted?" check below, because
643 * we want to disable even an already-loaded graph file.
645 if (!r
->gitdir
|| r
->commit_graph_disabled
)
648 if (r
->objects
->commit_graph_attempted
)
649 return !!r
->objects
->commit_graph
;
650 r
->objects
->commit_graph_attempted
= 1;
652 prepare_repo_settings(r
);
654 if (!git_env_bool(GIT_TEST_COMMIT_GRAPH
, 0) &&
655 r
->settings
.core_commit_graph
!= 1)
657 * This repository is not configured to use commit graphs, so
658 * do not load one. (But report commit_graph_attempted anyway
659 * so that commit graph loading is not attempted again for this
664 if (!commit_graph_compatible(r
))
668 for (odb
= r
->objects
->odb
;
669 !r
->objects
->commit_graph
&& odb
;
671 prepare_commit_graph_one(r
, odb
);
672 return !!r
->objects
->commit_graph
;
675 int generation_numbers_enabled(struct repository
*r
)
677 uint32_t first_generation
;
678 struct commit_graph
*g
;
679 if (!prepare_commit_graph(r
))
682 g
= r
->objects
->commit_graph
;
687 first_generation
= get_be32(g
->chunk_commit_data
+
688 g
->hash_len
+ 8) >> 2;
690 return !!first_generation
;
693 int corrected_commit_dates_enabled(struct repository
*r
)
695 struct commit_graph
*g
;
696 if (!prepare_commit_graph(r
))
699 g
= r
->objects
->commit_graph
;
704 return g
->read_generation_data
;
707 struct bloom_filter_settings
*get_bloom_filter_settings(struct repository
*r
)
709 struct commit_graph
*g
= r
->objects
->commit_graph
;
711 if (g
->bloom_filter_settings
)
712 return g
->bloom_filter_settings
;
718 static void close_commit_graph_one(struct commit_graph
*g
)
723 clear_commit_graph_data_slab(&commit_graph_data_slab
);
724 close_commit_graph_one(g
->base_graph
);
725 free_commit_graph(g
);
728 void close_commit_graph(struct raw_object_store
*o
)
730 close_commit_graph_one(o
->commit_graph
);
731 o
->commit_graph
= NULL
;
734 static int bsearch_graph(struct commit_graph
*g
, const struct object_id
*oid
, uint32_t *pos
)
736 return bsearch_hash(oid
->hash
, g
->chunk_oid_fanout
,
737 g
->chunk_oid_lookup
, g
->hash_len
, pos
);
740 static void load_oid_from_graph(struct commit_graph
*g
,
742 struct object_id
*oid
)
746 while (g
&& pos
< g
->num_commits_in_base
)
750 BUG("NULL commit-graph");
752 if (pos
>= g
->num_commits
+ g
->num_commits_in_base
)
753 die(_("invalid commit position. commit-graph is likely corrupt"));
755 lex_index
= pos
- g
->num_commits_in_base
;
757 oidread(oid
, g
->chunk_oid_lookup
+ st_mult(g
->hash_len
, lex_index
));
760 static struct commit_list
**insert_parent_or_die(struct repository
*r
,
761 struct commit_graph
*g
,
763 struct commit_list
**pptr
)
766 struct object_id oid
;
768 if (pos
>= g
->num_commits
+ g
->num_commits_in_base
)
769 die("invalid parent position %"PRIu32
, pos
);
771 load_oid_from_graph(g
, pos
, &oid
);
772 c
= lookup_commit(r
, &oid
);
774 die(_("could not find commit %s"), oid_to_hex(&oid
));
775 commit_graph_data_at(c
)->graph_pos
= pos
;
776 return &commit_list_insert(c
, pptr
)->next
;
779 static void fill_commit_graph_info(struct commit
*item
, struct commit_graph
*g
, uint32_t pos
)
781 const unsigned char *commit_data
;
782 struct commit_graph_data
*graph_data
;
783 uint32_t lex_index
, offset_pos
;
784 uint64_t date_high
, date_low
, offset
;
786 while (pos
< g
->num_commits_in_base
)
789 if (pos
>= g
->num_commits
+ g
->num_commits_in_base
)
790 die(_("invalid commit position. commit-graph is likely corrupt"));
792 lex_index
= pos
- g
->num_commits_in_base
;
793 commit_data
= g
->chunk_commit_data
+ st_mult(GRAPH_DATA_WIDTH
, lex_index
);
795 graph_data
= commit_graph_data_at(item
);
796 graph_data
->graph_pos
= pos
;
798 date_high
= get_be32(commit_data
+ g
->hash_len
+ 8) & 0x3;
799 date_low
= get_be32(commit_data
+ g
->hash_len
+ 12);
800 item
->date
= (timestamp_t
)((date_high
<< 32) | date_low
);
802 if (g
->read_generation_data
) {
803 offset
= (timestamp_t
)get_be32(g
->chunk_generation_data
+ st_mult(sizeof(uint32_t), lex_index
));
805 if (offset
& CORRECTED_COMMIT_DATE_OFFSET_OVERFLOW
) {
806 if (!g
->chunk_generation_data_overflow
)
807 die(_("commit-graph requires overflow generation data but has none"));
809 offset_pos
= offset
^ CORRECTED_COMMIT_DATE_OFFSET_OVERFLOW
;
810 graph_data
->generation
= item
->date
+ get_be64(g
->chunk_generation_data_overflow
+ st_mult(8, offset_pos
));
812 graph_data
->generation
= item
->date
+ offset
;
814 graph_data
->generation
= get_be32(commit_data
+ g
->hash_len
+ 8) >> 2;
817 *topo_level_slab_at(g
->topo_levels
, item
) = get_be32(commit_data
+ g
->hash_len
+ 8) >> 2;
820 static inline void set_commit_tree(struct commit
*c
, struct tree
*t
)
825 static int fill_commit_in_graph(struct repository
*r
,
827 struct commit_graph
*g
, uint32_t pos
)
830 uint32_t *parent_data_ptr
;
831 struct commit_list
**pptr
;
832 const unsigned char *commit_data
;
835 while (pos
< g
->num_commits_in_base
)
838 fill_commit_graph_info(item
, g
, pos
);
840 lex_index
= pos
- g
->num_commits_in_base
;
841 commit_data
= g
->chunk_commit_data
+ st_mult(g
->hash_len
+ 16, lex_index
);
843 item
->object
.parsed
= 1;
845 set_commit_tree(item
, NULL
);
847 pptr
= &item
->parents
;
849 edge_value
= get_be32(commit_data
+ g
->hash_len
);
850 if (edge_value
== GRAPH_PARENT_NONE
)
852 pptr
= insert_parent_or_die(r
, g
, edge_value
, pptr
);
854 edge_value
= get_be32(commit_data
+ g
->hash_len
+ 4);
855 if (edge_value
== GRAPH_PARENT_NONE
)
857 if (!(edge_value
& GRAPH_EXTRA_EDGES_NEEDED
)) {
858 pptr
= insert_parent_or_die(r
, g
, edge_value
, pptr
);
862 parent_data_ptr
= (uint32_t*)(g
->chunk_extra_edges
+
863 st_mult(4, edge_value
& GRAPH_EDGE_LAST_MASK
));
865 edge_value
= get_be32(parent_data_ptr
);
866 pptr
= insert_parent_or_die(r
, g
,
867 edge_value
& GRAPH_EDGE_LAST_MASK
,
870 } while (!(edge_value
& GRAPH_LAST_EDGE
));
875 static int search_commit_pos_in_graph(const struct object_id
*id
, struct commit_graph
*g
, uint32_t *pos
)
877 struct commit_graph
*cur_g
= g
;
880 while (cur_g
&& !bsearch_graph(cur_g
, id
, &lex_index
))
881 cur_g
= cur_g
->base_graph
;
884 *pos
= lex_index
+ cur_g
->num_commits_in_base
;
891 static int find_commit_pos_in_graph(struct commit
*item
, struct commit_graph
*g
, uint32_t *pos
)
893 uint32_t graph_pos
= commit_graph_position(item
);
894 if (graph_pos
!= COMMIT_NOT_FROM_GRAPH
) {
898 return search_commit_pos_in_graph(&item
->object
.oid
, g
, pos
);
902 int repo_find_commit_pos_in_graph(struct repository
*r
, struct commit
*c
,
905 if (!prepare_commit_graph(r
))
907 return find_commit_pos_in_graph(c
, r
->objects
->commit_graph
, pos
);
910 struct commit
*lookup_commit_in_graph(struct repository
*repo
, const struct object_id
*id
)
912 struct commit
*commit
;
915 if (!prepare_commit_graph(repo
))
917 if (!search_commit_pos_in_graph(id
, repo
->objects
->commit_graph
, &pos
))
919 if (!has_object(repo
, id
, 0))
922 commit
= lookup_commit(repo
, id
);
925 if (commit
->object
.parsed
)
928 if (!fill_commit_in_graph(repo
, commit
, repo
->objects
->commit_graph
, pos
))
934 static int parse_commit_in_graph_one(struct repository
*r
,
935 struct commit_graph
*g
,
940 if (item
->object
.parsed
)
943 if (find_commit_pos_in_graph(item
, g
, &pos
))
944 return fill_commit_in_graph(r
, item
, g
, pos
);
949 int parse_commit_in_graph(struct repository
*r
, struct commit
*item
)
951 static int checked_env
= 0;
954 git_env_bool(GIT_TEST_COMMIT_GRAPH_DIE_ON_PARSE
, 0))
955 die("dying as requested by the '%s' variable on commit-graph parse!",
956 GIT_TEST_COMMIT_GRAPH_DIE_ON_PARSE
);
959 if (!prepare_commit_graph(r
))
961 return parse_commit_in_graph_one(r
, r
->objects
->commit_graph
, item
);
964 void load_commit_graph_info(struct repository
*r
, struct commit
*item
)
967 if (repo_find_commit_pos_in_graph(r
, item
, &pos
))
968 fill_commit_graph_info(item
, r
->objects
->commit_graph
, pos
);
971 static struct tree
*load_tree_for_commit(struct repository
*r
,
972 struct commit_graph
*g
,
975 struct object_id oid
;
976 const unsigned char *commit_data
;
977 uint32_t graph_pos
= commit_graph_position(c
);
979 while (graph_pos
< g
->num_commits_in_base
)
982 commit_data
= g
->chunk_commit_data
+
983 GRAPH_DATA_WIDTH
* (graph_pos
- g
->num_commits_in_base
);
985 oidread(&oid
, commit_data
);
986 set_commit_tree(c
, lookup_tree(r
, &oid
));
988 return c
->maybe_tree
;
991 static struct tree
*get_commit_tree_in_graph_one(struct repository
*r
,
992 struct commit_graph
*g
,
993 const struct commit
*c
)
996 return c
->maybe_tree
;
997 if (commit_graph_position(c
) == COMMIT_NOT_FROM_GRAPH
)
998 BUG("get_commit_tree_in_graph_one called from non-commit-graph commit");
1000 return load_tree_for_commit(r
, g
, (struct commit
*)c
);
1003 struct tree
*get_commit_tree_in_graph(struct repository
*r
, const struct commit
*c
)
1005 return get_commit_tree_in_graph_one(r
, r
->objects
->commit_graph
, c
);
1008 struct packed_commit_list
{
1009 struct commit
**list
;
1014 struct write_commit_graph_context
{
1015 struct repository
*r
;
1016 struct object_directory
*odb
;
1018 struct oid_array oids
;
1019 struct packed_commit_list commits
;
1020 int num_extra_edges
;
1021 int num_generation_data_overflows
;
1022 unsigned long approx_nr_objects
;
1023 struct progress
*progress
;
1025 uint64_t progress_cnt
;
1027 char *base_graph_name
;
1028 int num_commit_graphs_before
;
1029 int num_commit_graphs_after
;
1030 char **commit_graph_filenames_before
;
1031 char **commit_graph_filenames_after
;
1032 char **commit_graph_hash_after
;
1033 uint32_t new_num_commits_in_base
;
1034 struct commit_graph
*new_base_graph
;
1041 write_generation_data
:1,
1042 trust_generation_numbers
:1;
1044 struct topo_level_slab
*topo_levels
;
1045 const struct commit_graph_opts
*opts
;
1046 size_t total_bloom_filter_data_size
;
1047 const struct bloom_filter_settings
*bloom_settings
;
1049 int count_bloom_filter_computed
;
1050 int count_bloom_filter_not_computed
;
1051 int count_bloom_filter_trunc_empty
;
1052 int count_bloom_filter_trunc_large
;
1055 static int write_graph_chunk_fanout(struct hashfile
*f
,
1058 struct write_commit_graph_context
*ctx
= data
;
1060 struct commit
**list
= ctx
->commits
.list
;
1063 * Write the first-level table (the list is sorted,
1064 * but we use a 256-entry lookup to be able to avoid
1065 * having to do eight extra binary search iterations).
1067 for (i
= 0; i
< 256; i
++) {
1068 while (count
< ctx
->commits
.nr
) {
1069 if ((*list
)->object
.oid
.hash
[0] != i
)
1071 display_progress(ctx
->progress
, ++ctx
->progress_cnt
);
1076 hashwrite_be32(f
, count
);
1082 static int write_graph_chunk_oids(struct hashfile
*f
,
1085 struct write_commit_graph_context
*ctx
= data
;
1086 struct commit
**list
= ctx
->commits
.list
;
1088 for (count
= 0; count
< ctx
->commits
.nr
; count
++, list
++) {
1089 display_progress(ctx
->progress
, ++ctx
->progress_cnt
);
1090 hashwrite(f
, (*list
)->object
.oid
.hash
, the_hash_algo
->rawsz
);
1096 static const struct object_id
*commit_to_oid(size_t index
, const void *table
)
1098 const struct commit
* const *commits
= table
;
1099 return &commits
[index
]->object
.oid
;
1102 static int write_graph_chunk_data(struct hashfile
*f
,
1105 struct write_commit_graph_context
*ctx
= data
;
1106 struct commit
**list
= ctx
->commits
.list
;
1107 struct commit
**last
= ctx
->commits
.list
+ ctx
->commits
.nr
;
1108 uint32_t num_extra_edges
= 0;
1110 while (list
< last
) {
1111 struct commit_list
*parent
;
1112 struct object_id
*tree
;
1114 uint32_t packedDate
[2];
1115 display_progress(ctx
->progress
, ++ctx
->progress_cnt
);
1117 if (repo_parse_commit_no_graph(ctx
->r
, *list
))
1118 die(_("unable to parse commit %s"),
1119 oid_to_hex(&(*list
)->object
.oid
));
1120 tree
= get_commit_tree_oid(*list
);
1121 hashwrite(f
, tree
->hash
, the_hash_algo
->rawsz
);
1123 parent
= (*list
)->parents
;
1126 edge_value
= GRAPH_PARENT_NONE
;
1128 edge_value
= oid_pos(&parent
->item
->object
.oid
,
1133 if (edge_value
>= 0)
1134 edge_value
+= ctx
->new_num_commits_in_base
;
1135 else if (ctx
->new_base_graph
) {
1137 if (find_commit_pos_in_graph(parent
->item
,
1138 ctx
->new_base_graph
,
1144 BUG("missing parent %s for commit %s",
1145 oid_to_hex(&parent
->item
->object
.oid
),
1146 oid_to_hex(&(*list
)->object
.oid
));
1149 hashwrite_be32(f
, edge_value
);
1152 parent
= parent
->next
;
1155 edge_value
= GRAPH_PARENT_NONE
;
1156 else if (parent
->next
)
1157 edge_value
= GRAPH_EXTRA_EDGES_NEEDED
| num_extra_edges
;
1159 edge_value
= oid_pos(&parent
->item
->object
.oid
,
1164 if (edge_value
>= 0)
1165 edge_value
+= ctx
->new_num_commits_in_base
;
1166 else if (ctx
->new_base_graph
) {
1168 if (find_commit_pos_in_graph(parent
->item
,
1169 ctx
->new_base_graph
,
1175 BUG("missing parent %s for commit %s",
1176 oid_to_hex(&parent
->item
->object
.oid
),
1177 oid_to_hex(&(*list
)->object
.oid
));
1180 hashwrite_be32(f
, edge_value
);
1182 if (edge_value
& GRAPH_EXTRA_EDGES_NEEDED
) {
1185 parent
= parent
->next
;
1189 if (sizeof((*list
)->date
) > 4)
1190 packedDate
[0] = htonl(((*list
)->date
>> 32) & 0x3);
1194 packedDate
[0] |= htonl(*topo_level_slab_at(ctx
->topo_levels
, *list
) << 2);
1196 packedDate
[1] = htonl((*list
)->date
);
1197 hashwrite(f
, packedDate
, 8);
1205 static int write_graph_chunk_generation_data(struct hashfile
*f
,
1208 struct write_commit_graph_context
*ctx
= data
;
1209 int i
, num_generation_data_overflows
= 0;
1211 for (i
= 0; i
< ctx
->commits
.nr
; i
++) {
1212 struct commit
*c
= ctx
->commits
.list
[i
];
1214 repo_parse_commit(ctx
->r
, c
);
1215 offset
= commit_graph_data_at(c
)->generation
- c
->date
;
1216 display_progress(ctx
->progress
, ++ctx
->progress_cnt
);
1218 if (offset
> GENERATION_NUMBER_V2_OFFSET_MAX
) {
1219 offset
= CORRECTED_COMMIT_DATE_OFFSET_OVERFLOW
| num_generation_data_overflows
;
1220 num_generation_data_overflows
++;
1223 hashwrite_be32(f
, offset
);
1229 static int write_graph_chunk_generation_data_overflow(struct hashfile
*f
,
1232 struct write_commit_graph_context
*ctx
= data
;
1234 for (i
= 0; i
< ctx
->commits
.nr
; i
++) {
1235 struct commit
*c
= ctx
->commits
.list
[i
];
1236 timestamp_t offset
= commit_graph_data_at(c
)->generation
- c
->date
;
1237 display_progress(ctx
->progress
, ++ctx
->progress_cnt
);
1239 if (offset
> GENERATION_NUMBER_V2_OFFSET_MAX
) {
1240 hashwrite_be32(f
, offset
>> 32);
1241 hashwrite_be32(f
, (uint32_t) offset
);
1248 static int write_graph_chunk_extra_edges(struct hashfile
*f
,
1251 struct write_commit_graph_context
*ctx
= data
;
1252 struct commit
**list
= ctx
->commits
.list
;
1253 struct commit
**last
= ctx
->commits
.list
+ ctx
->commits
.nr
;
1254 struct commit_list
*parent
;
1256 while (list
< last
) {
1257 int num_parents
= 0;
1259 display_progress(ctx
->progress
, ++ctx
->progress_cnt
);
1261 for (parent
= (*list
)->parents
; num_parents
< 3 && parent
;
1262 parent
= parent
->next
)
1265 if (num_parents
<= 2) {
1270 /* Since num_parents > 2, this initializer is safe. */
1271 for (parent
= (*list
)->parents
->next
; parent
; parent
= parent
->next
) {
1272 int edge_value
= oid_pos(&parent
->item
->object
.oid
,
1277 if (edge_value
>= 0)
1278 edge_value
+= ctx
->new_num_commits_in_base
;
1279 else if (ctx
->new_base_graph
) {
1281 if (find_commit_pos_in_graph(parent
->item
,
1282 ctx
->new_base_graph
,
1288 BUG("missing parent %s for commit %s",
1289 oid_to_hex(&parent
->item
->object
.oid
),
1290 oid_to_hex(&(*list
)->object
.oid
));
1291 else if (!parent
->next
)
1292 edge_value
|= GRAPH_LAST_EDGE
;
1294 hashwrite_be32(f
, edge_value
);
1303 static int write_graph_chunk_bloom_indexes(struct hashfile
*f
,
1306 struct write_commit_graph_context
*ctx
= data
;
1307 struct commit
**list
= ctx
->commits
.list
;
1308 struct commit
**last
= ctx
->commits
.list
+ ctx
->commits
.nr
;
1309 uint32_t cur_pos
= 0;
1311 while (list
< last
) {
1312 struct bloom_filter
*filter
= get_bloom_filter(ctx
->r
, *list
);
1313 size_t len
= filter
? filter
->len
: 0;
1315 display_progress(ctx
->progress
, ++ctx
->progress_cnt
);
1316 hashwrite_be32(f
, cur_pos
);
1323 static void trace2_bloom_filter_settings(struct write_commit_graph_context
*ctx
)
1325 struct json_writer jw
= JSON_WRITER_INIT
;
1327 jw_object_begin(&jw
, 0);
1328 jw_object_intmax(&jw
, "hash_version", ctx
->bloom_settings
->hash_version
);
1329 jw_object_intmax(&jw
, "num_hashes", ctx
->bloom_settings
->num_hashes
);
1330 jw_object_intmax(&jw
, "bits_per_entry", ctx
->bloom_settings
->bits_per_entry
);
1331 jw_object_intmax(&jw
, "max_changed_paths", ctx
->bloom_settings
->max_changed_paths
);
1334 trace2_data_json("bloom", ctx
->r
, "settings", &jw
);
1339 static int write_graph_chunk_bloom_data(struct hashfile
*f
,
1342 struct write_commit_graph_context
*ctx
= data
;
1343 struct commit
**list
= ctx
->commits
.list
;
1344 struct commit
**last
= ctx
->commits
.list
+ ctx
->commits
.nr
;
1346 trace2_bloom_filter_settings(ctx
);
1348 hashwrite_be32(f
, ctx
->bloom_settings
->hash_version
);
1349 hashwrite_be32(f
, ctx
->bloom_settings
->num_hashes
);
1350 hashwrite_be32(f
, ctx
->bloom_settings
->bits_per_entry
);
1352 while (list
< last
) {
1353 struct bloom_filter
*filter
= get_bloom_filter(ctx
->r
, *list
);
1354 size_t len
= filter
? filter
->len
: 0;
1356 display_progress(ctx
->progress
, ++ctx
->progress_cnt
);
1358 hashwrite(f
, filter
->data
, len
* sizeof(unsigned char));
1365 static int add_packed_commits(const struct object_id
*oid
,
1366 struct packed_git
*pack
,
1370 struct write_commit_graph_context
*ctx
= (struct write_commit_graph_context
*)data
;
1371 enum object_type type
;
1372 off_t offset
= nth_packed_object_offset(pack
, pos
);
1373 struct object_info oi
= OBJECT_INFO_INIT
;
1376 display_progress(ctx
->progress
, ++ctx
->progress_done
);
1379 if (packed_object_info(ctx
->r
, pack
, offset
, &oi
) < 0)
1380 die(_("unable to get type of object %s"), oid_to_hex(oid
));
1382 if (type
!= OBJ_COMMIT
)
1385 oid_array_append(&ctx
->oids
, oid
);
1386 set_commit_pos(ctx
->r
, oid
);
1391 static void add_missing_parents(struct write_commit_graph_context
*ctx
, struct commit
*commit
)
1393 struct commit_list
*parent
;
1394 for (parent
= commit
->parents
; parent
; parent
= parent
->next
) {
1395 if (!(parent
->item
->object
.flags
& REACHABLE
)) {
1396 oid_array_append(&ctx
->oids
, &parent
->item
->object
.oid
);
1397 parent
->item
->object
.flags
|= REACHABLE
;
1402 static void close_reachable(struct write_commit_graph_context
*ctx
)
1405 struct commit
*commit
;
1406 enum commit_graph_split_flags flags
= ctx
->opts
?
1407 ctx
->opts
->split_flags
: COMMIT_GRAPH_SPLIT_UNSPECIFIED
;
1409 if (ctx
->report_progress
)
1410 ctx
->progress
= start_delayed_progress(
1411 _("Loading known commits in commit graph"),
1413 for (i
= 0; i
< ctx
->oids
.nr
; i
++) {
1414 display_progress(ctx
->progress
, i
+ 1);
1415 commit
= lookup_commit(ctx
->r
, &ctx
->oids
.oid
[i
]);
1417 commit
->object
.flags
|= REACHABLE
;
1419 stop_progress(&ctx
->progress
);
1422 * As this loop runs, ctx->oids.nr may grow, but not more
1423 * than the number of missing commits in the reachable
1426 if (ctx
->report_progress
)
1427 ctx
->progress
= start_delayed_progress(
1428 _("Expanding reachable commits in commit graph"),
1430 for (i
= 0; i
< ctx
->oids
.nr
; i
++) {
1431 display_progress(ctx
->progress
, i
+ 1);
1432 commit
= lookup_commit(ctx
->r
, &ctx
->oids
.oid
[i
]);
1437 if ((!repo_parse_commit(ctx
->r
, commit
) &&
1438 commit_graph_position(commit
) == COMMIT_NOT_FROM_GRAPH
) ||
1439 flags
== COMMIT_GRAPH_SPLIT_REPLACE
)
1440 add_missing_parents(ctx
, commit
);
1441 } else if (!repo_parse_commit_no_graph(ctx
->r
, commit
))
1442 add_missing_parents(ctx
, commit
);
1444 stop_progress(&ctx
->progress
);
1446 if (ctx
->report_progress
)
1447 ctx
->progress
= start_delayed_progress(
1448 _("Clearing commit marks in commit graph"),
1450 for (i
= 0; i
< ctx
->oids
.nr
; i
++) {
1451 display_progress(ctx
->progress
, i
+ 1);
1452 commit
= lookup_commit(ctx
->r
, &ctx
->oids
.oid
[i
]);
1455 commit
->object
.flags
&= ~REACHABLE
;
1457 stop_progress(&ctx
->progress
);
1460 struct compute_generation_info
{
1461 struct repository
*r
;
1462 struct packed_commit_list
*commits
;
1463 struct progress
*progress
;
1466 timestamp_t (*get_generation
)(struct commit
*c
, void *data
);
1467 void (*set_generation
)(struct commit
*c
, timestamp_t gen
, void *data
);
1471 static timestamp_t
compute_generation_from_max(struct commit
*c
,
1472 timestamp_t max_gen
,
1473 int generation_version
)
1475 switch (generation_version
) {
1476 case 1: /* topological levels */
1477 if (max_gen
> GENERATION_NUMBER_V1_MAX
- 1)
1478 max_gen
= GENERATION_NUMBER_V1_MAX
- 1;
1481 case 2: /* corrected commit date */
1482 if (c
->date
&& c
->date
> max_gen
)
1483 max_gen
= c
->date
- 1;
1487 BUG("attempting unimplemented version");
1491 static void compute_reachable_generation_numbers(
1492 struct compute_generation_info
*info
,
1493 int generation_version
)
1496 struct commit_list
*list
= NULL
;
1498 for (i
= 0; i
< info
->commits
->nr
; i
++) {
1499 struct commit
*c
= info
->commits
->list
[i
];
1501 repo_parse_commit(info
->r
, c
);
1502 gen
= info
->get_generation(c
, info
->data
);
1503 display_progress(info
->progress
, info
->progress_cnt
+ 1);
1505 if (gen
!= GENERATION_NUMBER_ZERO
&& gen
!= GENERATION_NUMBER_INFINITY
)
1508 commit_list_insert(c
, &list
);
1510 struct commit
*current
= list
->item
;
1511 struct commit_list
*parent
;
1512 int all_parents_computed
= 1;
1513 uint32_t max_gen
= 0;
1515 for (parent
= current
->parents
; parent
; parent
= parent
->next
) {
1516 repo_parse_commit(info
->r
, parent
->item
);
1517 gen
= info
->get_generation(parent
->item
, info
->data
);
1519 if (gen
== GENERATION_NUMBER_ZERO
) {
1520 all_parents_computed
= 0;
1521 commit_list_insert(parent
->item
, &list
);
1529 if (all_parents_computed
) {
1531 gen
= compute_generation_from_max(
1533 generation_version
);
1534 info
->set_generation(current
, gen
, info
->data
);
1540 static timestamp_t
get_topo_level(struct commit
*c
, void *data
)
1542 struct write_commit_graph_context
*ctx
= data
;
1543 return *topo_level_slab_at(ctx
->topo_levels
, c
);
1546 static void set_topo_level(struct commit
*c
, timestamp_t t
, void *data
)
1548 struct write_commit_graph_context
*ctx
= data
;
1549 *topo_level_slab_at(ctx
->topo_levels
, c
) = (uint32_t)t
;
1552 static void compute_topological_levels(struct write_commit_graph_context
*ctx
)
1554 struct compute_generation_info info
= {
1556 .commits
= &ctx
->commits
,
1557 .get_generation
= get_topo_level
,
1558 .set_generation
= set_topo_level
,
1562 if (ctx
->report_progress
)
1563 info
.progress
= ctx
->progress
1564 = start_delayed_progress(
1565 _("Computing commit graph topological levels"),
1568 compute_reachable_generation_numbers(&info
, 1);
1570 stop_progress(&ctx
->progress
);
1573 static timestamp_t
get_generation_from_graph_data(struct commit
*c
, void *data
)
1575 return commit_graph_data_at(c
)->generation
;
1578 static void set_generation_v2(struct commit
*c
, timestamp_t t
, void *data
)
1580 struct commit_graph_data
*g
= commit_graph_data_at(c
);
1584 static void compute_generation_numbers(struct write_commit_graph_context
*ctx
)
1587 struct compute_generation_info info
= {
1589 .commits
= &ctx
->commits
,
1590 .get_generation
= get_generation_from_graph_data
,
1591 .set_generation
= set_generation_v2
,
1595 if (ctx
->report_progress
)
1596 info
.progress
= ctx
->progress
1597 = start_delayed_progress(
1598 _("Computing commit graph generation numbers"),
1601 if (!ctx
->trust_generation_numbers
) {
1602 for (i
= 0; i
< ctx
->commits
.nr
; i
++) {
1603 struct commit
*c
= ctx
->commits
.list
[i
];
1604 repo_parse_commit(ctx
->r
, c
);
1605 commit_graph_data_at(c
)->generation
= GENERATION_NUMBER_ZERO
;
1609 compute_reachable_generation_numbers(&info
, 2);
1611 for (i
= 0; i
< ctx
->commits
.nr
; i
++) {
1612 struct commit
*c
= ctx
->commits
.list
[i
];
1613 timestamp_t offset
= commit_graph_data_at(c
)->generation
- c
->date
;
1614 if (offset
> GENERATION_NUMBER_V2_OFFSET_MAX
)
1615 ctx
->num_generation_data_overflows
++;
1617 stop_progress(&ctx
->progress
);
1620 static void set_generation_in_graph_data(struct commit
*c
, timestamp_t t
,
1623 commit_graph_data_at(c
)->generation
= t
;
1627 * After this method, all commits reachable from those in the given
1628 * list will have non-zero, non-infinite generation numbers.
1630 void ensure_generations_valid(struct repository
*r
,
1631 struct commit
**commits
, size_t nr
)
1633 int generation_version
= get_configured_generation_version(r
);
1634 struct packed_commit_list list
= {
1639 struct compute_generation_info info
= {
1642 .get_generation
= get_generation_from_graph_data
,
1643 .set_generation
= set_generation_in_graph_data
,
1646 compute_reachable_generation_numbers(&info
, generation_version
);
1649 static void trace2_bloom_filter_write_statistics(struct write_commit_graph_context
*ctx
)
1651 trace2_data_intmax("commit-graph", ctx
->r
, "filter-computed",
1652 ctx
->count_bloom_filter_computed
);
1653 trace2_data_intmax("commit-graph", ctx
->r
, "filter-not-computed",
1654 ctx
->count_bloom_filter_not_computed
);
1655 trace2_data_intmax("commit-graph", ctx
->r
, "filter-trunc-empty",
1656 ctx
->count_bloom_filter_trunc_empty
);
1657 trace2_data_intmax("commit-graph", ctx
->r
, "filter-trunc-large",
1658 ctx
->count_bloom_filter_trunc_large
);
1661 static void compute_bloom_filters(struct write_commit_graph_context
*ctx
)
1664 struct progress
*progress
= NULL
;
1665 struct commit
**sorted_commits
;
1666 int max_new_filters
;
1668 init_bloom_filters();
1670 if (ctx
->report_progress
)
1671 progress
= start_delayed_progress(
1672 _("Computing commit changed paths Bloom filters"),
1675 DUP_ARRAY(sorted_commits
, ctx
->commits
.list
, ctx
->commits
.nr
);
1677 if (ctx
->order_by_pack
)
1678 QSORT(sorted_commits
, ctx
->commits
.nr
, commit_pos_cmp
);
1680 QSORT(sorted_commits
, ctx
->commits
.nr
, commit_gen_cmp
);
1682 max_new_filters
= ctx
->opts
&& ctx
->opts
->max_new_filters
>= 0 ?
1683 ctx
->opts
->max_new_filters
: ctx
->commits
.nr
;
1685 for (i
= 0; i
< ctx
->commits
.nr
; i
++) {
1686 enum bloom_filter_computed computed
= 0;
1687 struct commit
*c
= sorted_commits
[i
];
1688 struct bloom_filter
*filter
= get_or_compute_bloom_filter(
1691 ctx
->count_bloom_filter_computed
< max_new_filters
,
1692 ctx
->bloom_settings
,
1694 if (computed
& BLOOM_COMPUTED
) {
1695 ctx
->count_bloom_filter_computed
++;
1696 if (computed
& BLOOM_TRUNC_EMPTY
)
1697 ctx
->count_bloom_filter_trunc_empty
++;
1698 if (computed
& BLOOM_TRUNC_LARGE
)
1699 ctx
->count_bloom_filter_trunc_large
++;
1700 } else if (computed
& BLOOM_NOT_COMPUTED
)
1701 ctx
->count_bloom_filter_not_computed
++;
1702 ctx
->total_bloom_filter_data_size
+= filter
1703 ? sizeof(unsigned char) * filter
->len
: 0;
1704 display_progress(progress
, i
+ 1);
1707 if (trace2_is_enabled())
1708 trace2_bloom_filter_write_statistics(ctx
);
1710 free(sorted_commits
);
1711 stop_progress(&progress
);
1714 struct refs_cb_data
{
1715 struct oidset
*commits
;
1716 struct progress
*progress
;
1719 static int add_ref_to_set(const char *refname UNUSED
,
1720 const struct object_id
*oid
,
1721 int flags UNUSED
, void *cb_data
)
1723 struct object_id peeled
;
1724 struct refs_cb_data
*data
= (struct refs_cb_data
*)cb_data
;
1726 if (!peel_iterated_oid(oid
, &peeled
))
1728 if (oid_object_info(the_repository
, oid
, NULL
) == OBJ_COMMIT
)
1729 oidset_insert(data
->commits
, oid
);
1731 display_progress(data
->progress
, oidset_size(data
->commits
));
1736 int write_commit_graph_reachable(struct object_directory
*odb
,
1737 enum commit_graph_write_flags flags
,
1738 const struct commit_graph_opts
*opts
)
1740 struct oidset commits
= OIDSET_INIT
;
1741 struct refs_cb_data data
;
1744 memset(&data
, 0, sizeof(data
));
1745 data
.commits
= &commits
;
1746 if (flags
& COMMIT_GRAPH_WRITE_PROGRESS
)
1747 data
.progress
= start_delayed_progress(
1748 _("Collecting referenced commits"), 0);
1750 for_each_ref(add_ref_to_set
, &data
);
1752 stop_progress(&data
.progress
);
1754 result
= write_commit_graph(odb
, NULL
, &commits
,
1757 oidset_clear(&commits
);
1761 static int fill_oids_from_packs(struct write_commit_graph_context
*ctx
,
1762 const struct string_list
*pack_indexes
)
1765 struct strbuf progress_title
= STRBUF_INIT
;
1766 struct strbuf packname
= STRBUF_INIT
;
1770 strbuf_addf(&packname
, "%s/pack/", ctx
->odb
->path
);
1771 dirlen
= packname
.len
;
1772 if (ctx
->report_progress
) {
1773 strbuf_addf(&progress_title
,
1774 Q_("Finding commits for commit graph in %"PRIuMAX
" pack",
1775 "Finding commits for commit graph in %"PRIuMAX
" packs",
1777 (uintmax_t)pack_indexes
->nr
);
1778 ctx
->progress
= start_delayed_progress(progress_title
.buf
, 0);
1779 ctx
->progress_done
= 0;
1781 for (i
= 0; i
< pack_indexes
->nr
; i
++) {
1782 struct packed_git
*p
;
1783 strbuf_setlen(&packname
, dirlen
);
1784 strbuf_addstr(&packname
, pack_indexes
->items
[i
].string
);
1785 p
= add_packed_git(packname
.buf
, packname
.len
, 1);
1787 ret
= error(_("error adding pack %s"), packname
.buf
);
1790 if (open_pack_index(p
)) {
1791 ret
= error(_("error opening index for %s"), packname
.buf
);
1794 for_each_object_in_pack(p
, add_packed_commits
, ctx
,
1795 FOR_EACH_OBJECT_PACK_ORDER
);
1801 stop_progress(&ctx
->progress
);
1802 strbuf_release(&progress_title
);
1803 strbuf_release(&packname
);
1808 static int fill_oids_from_commits(struct write_commit_graph_context
*ctx
,
1809 struct oidset
*commits
)
1811 struct oidset_iter iter
;
1812 struct object_id
*oid
;
1814 if (!oidset_size(commits
))
1817 oidset_iter_init(commits
, &iter
);
1818 while ((oid
= oidset_iter_next(&iter
))) {
1819 oid_array_append(&ctx
->oids
, oid
);
1825 static void fill_oids_from_all_packs(struct write_commit_graph_context
*ctx
)
1827 if (ctx
->report_progress
)
1828 ctx
->progress
= start_delayed_progress(
1829 _("Finding commits for commit graph among packed objects"),
1830 ctx
->approx_nr_objects
);
1831 for_each_packed_object(add_packed_commits
, ctx
,
1832 FOR_EACH_OBJECT_PACK_ORDER
);
1833 if (ctx
->progress_done
< ctx
->approx_nr_objects
)
1834 display_progress(ctx
->progress
, ctx
->approx_nr_objects
);
1835 stop_progress(&ctx
->progress
);
1838 static void copy_oids_to_commits(struct write_commit_graph_context
*ctx
)
1841 enum commit_graph_split_flags flags
= ctx
->opts
?
1842 ctx
->opts
->split_flags
: COMMIT_GRAPH_SPLIT_UNSPECIFIED
;
1844 ctx
->num_extra_edges
= 0;
1845 if (ctx
->report_progress
)
1846 ctx
->progress
= start_delayed_progress(
1847 _("Finding extra edges in commit graph"),
1849 oid_array_sort(&ctx
->oids
);
1850 for (i
= 0; i
< ctx
->oids
.nr
; i
= oid_array_next_unique(&ctx
->oids
, i
)) {
1851 unsigned int num_parents
;
1853 display_progress(ctx
->progress
, i
+ 1);
1855 ALLOC_GROW(ctx
->commits
.list
, ctx
->commits
.nr
+ 1, ctx
->commits
.alloc
);
1856 ctx
->commits
.list
[ctx
->commits
.nr
] = lookup_commit(ctx
->r
, &ctx
->oids
.oid
[i
]);
1858 if (ctx
->split
&& flags
!= COMMIT_GRAPH_SPLIT_REPLACE
&&
1859 commit_graph_position(ctx
->commits
.list
[ctx
->commits
.nr
]) != COMMIT_NOT_FROM_GRAPH
)
1862 if (ctx
->split
&& flags
== COMMIT_GRAPH_SPLIT_REPLACE
)
1863 repo_parse_commit(ctx
->r
, ctx
->commits
.list
[ctx
->commits
.nr
]);
1865 repo_parse_commit_no_graph(ctx
->r
, ctx
->commits
.list
[ctx
->commits
.nr
]);
1867 num_parents
= commit_list_count(ctx
->commits
.list
[ctx
->commits
.nr
]->parents
);
1868 if (num_parents
> 2)
1869 ctx
->num_extra_edges
+= num_parents
- 1;
1873 stop_progress(&ctx
->progress
);
1876 static int write_graph_chunk_base_1(struct hashfile
*f
,
1877 struct commit_graph
*g
)
1884 num
= write_graph_chunk_base_1(f
, g
->base_graph
);
1885 hashwrite(f
, g
->oid
.hash
, the_hash_algo
->rawsz
);
1889 static int write_graph_chunk_base(struct hashfile
*f
,
1892 struct write_commit_graph_context
*ctx
= data
;
1893 int num
= write_graph_chunk_base_1(f
, ctx
->new_base_graph
);
1895 if (num
!= ctx
->num_commit_graphs_after
- 1) {
1896 error(_("failed to write correct number of base graph ids"));
1903 static int write_commit_graph_file(struct write_commit_graph_context
*ctx
)
1908 struct lock_file lk
= LOCK_INIT
;
1909 const unsigned hashsz
= the_hash_algo
->rawsz
;
1910 struct strbuf progress_title
= STRBUF_INIT
;
1911 struct chunkfile
*cf
;
1912 unsigned char file_hash
[GIT_MAX_RAWSZ
];
1915 struct strbuf tmp_file
= STRBUF_INIT
;
1917 strbuf_addf(&tmp_file
,
1918 "%s/info/commit-graphs/tmp_graph_XXXXXX",
1920 ctx
->graph_name
= strbuf_detach(&tmp_file
, NULL
);
1922 ctx
->graph_name
= get_commit_graph_filename(ctx
->odb
);
1925 if (safe_create_leading_directories(ctx
->graph_name
)) {
1926 UNLEAK(ctx
->graph_name
);
1927 error(_("unable to create leading directories of %s"),
1933 char *lock_name
= get_commit_graph_chain_filename(ctx
->odb
);
1935 hold_lock_file_for_update_mode(&lk
, lock_name
,
1936 LOCK_DIE_ON_ERROR
, 0444);
1939 fd
= git_mkstemp_mode(ctx
->graph_name
, 0444);
1941 error(_("unable to create temporary graph layer"));
1945 if (adjust_shared_perm(ctx
->graph_name
)) {
1946 error(_("unable to adjust shared permissions for '%s'"),
1951 f
= hashfd(fd
, ctx
->graph_name
);
1953 hold_lock_file_for_update_mode(&lk
, ctx
->graph_name
,
1954 LOCK_DIE_ON_ERROR
, 0444);
1955 fd
= get_lock_file_fd(&lk
);
1956 f
= hashfd(fd
, get_lock_file_path(&lk
));
1959 cf
= init_chunkfile(f
);
1961 add_chunk(cf
, GRAPH_CHUNKID_OIDFANOUT
, GRAPH_FANOUT_SIZE
,
1962 write_graph_chunk_fanout
);
1963 add_chunk(cf
, GRAPH_CHUNKID_OIDLOOKUP
, st_mult(hashsz
, ctx
->commits
.nr
),
1964 write_graph_chunk_oids
);
1965 add_chunk(cf
, GRAPH_CHUNKID_DATA
, st_mult(hashsz
+ 16, ctx
->commits
.nr
),
1966 write_graph_chunk_data
);
1968 if (ctx
->write_generation_data
)
1969 add_chunk(cf
, GRAPH_CHUNKID_GENERATION_DATA
,
1970 st_mult(sizeof(uint32_t), ctx
->commits
.nr
),
1971 write_graph_chunk_generation_data
);
1972 if (ctx
->num_generation_data_overflows
)
1973 add_chunk(cf
, GRAPH_CHUNKID_GENERATION_DATA_OVERFLOW
,
1974 st_mult(sizeof(timestamp_t
), ctx
->num_generation_data_overflows
),
1975 write_graph_chunk_generation_data_overflow
);
1976 if (ctx
->num_extra_edges
)
1977 add_chunk(cf
, GRAPH_CHUNKID_EXTRAEDGES
,
1978 st_mult(4, ctx
->num_extra_edges
),
1979 write_graph_chunk_extra_edges
);
1980 if (ctx
->changed_paths
) {
1981 add_chunk(cf
, GRAPH_CHUNKID_BLOOMINDEXES
,
1982 st_mult(sizeof(uint32_t), ctx
->commits
.nr
),
1983 write_graph_chunk_bloom_indexes
);
1984 add_chunk(cf
, GRAPH_CHUNKID_BLOOMDATA
,
1985 st_add(sizeof(uint32_t) * 3,
1986 ctx
->total_bloom_filter_data_size
),
1987 write_graph_chunk_bloom_data
);
1989 if (ctx
->num_commit_graphs_after
> 1)
1990 add_chunk(cf
, GRAPH_CHUNKID_BASE
,
1991 st_mult(hashsz
, ctx
->num_commit_graphs_after
- 1),
1992 write_graph_chunk_base
);
1994 hashwrite_be32(f
, GRAPH_SIGNATURE
);
1996 hashwrite_u8(f
, GRAPH_VERSION
);
1997 hashwrite_u8(f
, oid_version(the_hash_algo
));
1998 hashwrite_u8(f
, get_num_chunks(cf
));
1999 hashwrite_u8(f
, ctx
->num_commit_graphs_after
- 1);
2001 if (ctx
->report_progress
) {
2002 strbuf_addf(&progress_title
,
2003 Q_("Writing out commit graph in %d pass",
2004 "Writing out commit graph in %d passes",
2005 get_num_chunks(cf
)),
2006 get_num_chunks(cf
));
2007 ctx
->progress
= start_delayed_progress(
2009 st_mult(get_num_chunks(cf
), ctx
->commits
.nr
));
2012 write_chunkfile(cf
, ctx
);
2014 stop_progress(&ctx
->progress
);
2015 strbuf_release(&progress_title
);
2017 if (ctx
->split
&& ctx
->base_graph_name
&& ctx
->num_commit_graphs_after
> 1) {
2018 char *new_base_hash
= xstrdup(oid_to_hex(&ctx
->new_base_graph
->oid
));
2019 char *new_base_name
= get_split_graph_filename(ctx
->new_base_graph
->odb
, new_base_hash
);
2021 free(ctx
->commit_graph_filenames_after
[ctx
->num_commit_graphs_after
- 2]);
2022 free(ctx
->commit_graph_hash_after
[ctx
->num_commit_graphs_after
- 2]);
2023 ctx
->commit_graph_filenames_after
[ctx
->num_commit_graphs_after
- 2] = new_base_name
;
2024 ctx
->commit_graph_hash_after
[ctx
->num_commit_graphs_after
- 2] = new_base_hash
;
2027 close_commit_graph(ctx
->r
->objects
);
2028 finalize_hashfile(f
, file_hash
, FSYNC_COMPONENT_COMMIT_GRAPH
,
2029 CSUM_HASH_IN_STREAM
| CSUM_FSYNC
);
2033 FILE *chainf
= fdopen_lock_file(&lk
, "w");
2034 char *final_graph_name
;
2040 error(_("unable to open commit-graph chain file"));
2044 if (ctx
->base_graph_name
) {
2046 int idx
= ctx
->num_commit_graphs_after
- 1;
2047 if (ctx
->num_commit_graphs_after
> 1)
2050 dest
= ctx
->commit_graph_filenames_after
[idx
];
2052 if (strcmp(ctx
->base_graph_name
, dest
)) {
2053 result
= rename(ctx
->base_graph_name
, dest
);
2056 error(_("failed to rename base commit-graph file"));
2061 char *graph_name
= get_commit_graph_filename(ctx
->odb
);
2066 ctx
->commit_graph_hash_after
[ctx
->num_commit_graphs_after
- 1] = xstrdup(hash_to_hex(file_hash
));
2067 final_graph_name
= get_split_graph_filename(ctx
->odb
,
2068 ctx
->commit_graph_hash_after
[ctx
->num_commit_graphs_after
- 1]);
2069 ctx
->commit_graph_filenames_after
[ctx
->num_commit_graphs_after
- 1] = final_graph_name
;
2071 result
= rename(ctx
->graph_name
, final_graph_name
);
2073 for (i
= 0; i
< ctx
->num_commit_graphs_after
; i
++)
2074 fprintf(get_lock_file_fp(&lk
), "%s\n", ctx
->commit_graph_hash_after
[i
]);
2077 error(_("failed to rename temporary commit-graph file"));
2082 commit_lock_file(&lk
);
2087 static void split_graph_merge_strategy(struct write_commit_graph_context
*ctx
)
2089 struct commit_graph
*g
;
2090 uint32_t num_commits
;
2091 enum commit_graph_split_flags flags
= COMMIT_GRAPH_SPLIT_UNSPECIFIED
;
2094 int max_commits
= 0;
2098 max_commits
= ctx
->opts
->max_commits
;
2100 if (ctx
->opts
->size_multiple
)
2101 size_mult
= ctx
->opts
->size_multiple
;
2103 flags
= ctx
->opts
->split_flags
;
2106 g
= ctx
->r
->objects
->commit_graph
;
2107 num_commits
= ctx
->commits
.nr
;
2108 if (flags
== COMMIT_GRAPH_SPLIT_REPLACE
)
2109 ctx
->num_commit_graphs_after
= 1;
2111 ctx
->num_commit_graphs_after
= ctx
->num_commit_graphs_before
+ 1;
2113 if (flags
!= COMMIT_GRAPH_SPLIT_MERGE_PROHIBITED
&&
2114 flags
!= COMMIT_GRAPH_SPLIT_REPLACE
) {
2115 while (g
&& (g
->num_commits
<= size_mult
* num_commits
||
2116 (max_commits
&& num_commits
> max_commits
))) {
2117 if (g
->odb
!= ctx
->odb
)
2120 num_commits
+= g
->num_commits
;
2123 ctx
->num_commit_graphs_after
--;
2127 if (flags
!= COMMIT_GRAPH_SPLIT_REPLACE
)
2128 ctx
->new_base_graph
= g
;
2129 else if (ctx
->num_commit_graphs_after
!= 1)
2130 BUG("split_graph_merge_strategy: num_commit_graphs_after "
2131 "should be 1 with --split=replace");
2133 if (ctx
->num_commit_graphs_after
== 2) {
2134 char *old_graph_name
= get_commit_graph_filename(g
->odb
);
2136 if (!strcmp(g
->filename
, old_graph_name
) &&
2137 g
->odb
!= ctx
->odb
) {
2138 ctx
->num_commit_graphs_after
= 1;
2139 ctx
->new_base_graph
= NULL
;
2142 free(old_graph_name
);
2145 CALLOC_ARRAY(ctx
->commit_graph_filenames_after
, ctx
->num_commit_graphs_after
);
2146 CALLOC_ARRAY(ctx
->commit_graph_hash_after
, ctx
->num_commit_graphs_after
);
2148 for (i
= 0; i
< ctx
->num_commit_graphs_after
&&
2149 i
< ctx
->num_commit_graphs_before
; i
++)
2150 ctx
->commit_graph_filenames_after
[i
] = xstrdup(ctx
->commit_graph_filenames_before
[i
]);
2152 i
= ctx
->num_commit_graphs_before
- 1;
2153 g
= ctx
->r
->objects
->commit_graph
;
2156 if (i
< ctx
->num_commit_graphs_after
)
2157 ctx
->commit_graph_hash_after
[i
] = xstrdup(oid_to_hex(&g
->oid
));
2160 * If the topmost remaining layer has generation data chunk, the
2161 * resultant layer also has generation data chunk.
2163 if (i
== ctx
->num_commit_graphs_after
- 2)
2164 ctx
->write_generation_data
= !!g
->chunk_generation_data
;
2171 static void merge_commit_graph(struct write_commit_graph_context
*ctx
,
2172 struct commit_graph
*g
)
2175 uint32_t offset
= g
->num_commits_in_base
;
2177 ALLOC_GROW(ctx
->commits
.list
, ctx
->commits
.nr
+ g
->num_commits
, ctx
->commits
.alloc
);
2179 for (i
= 0; i
< g
->num_commits
; i
++) {
2180 struct object_id oid
;
2181 struct commit
*result
;
2183 display_progress(ctx
->progress
, i
+ 1);
2185 load_oid_from_graph(g
, i
+ offset
, &oid
);
2187 /* only add commits if they still exist in the repo */
2188 result
= lookup_commit_reference_gently(ctx
->r
, &oid
, 1);
2191 ctx
->commits
.list
[ctx
->commits
.nr
] = result
;
2197 static int commit_compare(const void *_a
, const void *_b
)
2199 const struct commit
*a
= *(const struct commit
**)_a
;
2200 const struct commit
*b
= *(const struct commit
**)_b
;
2201 return oidcmp(&a
->object
.oid
, &b
->object
.oid
);
2204 static void sort_and_scan_merged_commits(struct write_commit_graph_context
*ctx
)
2206 uint32_t i
, dedup_i
= 0;
2208 if (ctx
->report_progress
)
2209 ctx
->progress
= start_delayed_progress(
2210 _("Scanning merged commits"),
2213 QSORT(ctx
->commits
.list
, ctx
->commits
.nr
, commit_compare
);
2215 ctx
->num_extra_edges
= 0;
2216 for (i
= 0; i
< ctx
->commits
.nr
; i
++) {
2217 display_progress(ctx
->progress
, i
+ 1);
2219 if (i
&& oideq(&ctx
->commits
.list
[i
- 1]->object
.oid
,
2220 &ctx
->commits
.list
[i
]->object
.oid
)) {
2222 * Silently ignore duplicates. These were likely
2223 * created due to a commit appearing in multiple
2224 * layers of the chain, which is unexpected but
2225 * not invalid. We should make sure there is a
2226 * unique copy in the new layer.
2229 unsigned int num_parents
;
2231 ctx
->commits
.list
[dedup_i
] = ctx
->commits
.list
[i
];
2234 num_parents
= commit_list_count(ctx
->commits
.list
[i
]->parents
);
2235 if (num_parents
> 2)
2236 ctx
->num_extra_edges
+= num_parents
- 1;
2240 ctx
->commits
.nr
= dedup_i
;
2242 stop_progress(&ctx
->progress
);
2245 static void merge_commit_graphs(struct write_commit_graph_context
*ctx
)
2247 struct commit_graph
*g
= ctx
->r
->objects
->commit_graph
;
2248 uint32_t current_graph_number
= ctx
->num_commit_graphs_before
;
2250 while (g
&& current_graph_number
>= ctx
->num_commit_graphs_after
) {
2251 current_graph_number
--;
2253 if (ctx
->report_progress
)
2254 ctx
->progress
= start_delayed_progress(_("Merging commit-graph"), 0);
2256 merge_commit_graph(ctx
, g
);
2257 stop_progress(&ctx
->progress
);
2263 ctx
->new_base_graph
= g
;
2264 ctx
->new_num_commits_in_base
= g
->num_commits
+ g
->num_commits_in_base
;
2267 if (ctx
->new_base_graph
)
2268 ctx
->base_graph_name
= xstrdup(ctx
->new_base_graph
->filename
);
2270 sort_and_scan_merged_commits(ctx
);
2273 static void mark_commit_graphs(struct write_commit_graph_context
*ctx
)
2276 time_t now
= time(NULL
);
2278 for (i
= ctx
->num_commit_graphs_after
- 1; i
< ctx
->num_commit_graphs_before
; i
++) {
2280 struct utimbuf updated_time
;
2282 if (stat(ctx
->commit_graph_filenames_before
[i
], &st
) < 0)
2285 updated_time
.actime
= st
.st_atime
;
2286 updated_time
.modtime
= now
;
2287 utime(ctx
->commit_graph_filenames_before
[i
], &updated_time
);
2291 static void expire_commit_graphs(struct write_commit_graph_context
*ctx
)
2293 struct strbuf path
= STRBUF_INIT
;
2297 timestamp_t expire_time
= time(NULL
);
2299 if (ctx
->opts
&& ctx
->opts
->expire_time
)
2300 expire_time
= ctx
->opts
->expire_time
;
2302 char *chain_file_name
= get_commit_graph_chain_filename(ctx
->odb
);
2303 unlink(chain_file_name
);
2304 free(chain_file_name
);
2305 ctx
->num_commit_graphs_after
= 0;
2308 strbuf_addstr(&path
, ctx
->odb
->path
);
2309 strbuf_addstr(&path
, "/info/commit-graphs");
2310 dir
= opendir(path
.buf
);
2315 strbuf_addch(&path
, '/');
2316 dirnamelen
= path
.len
;
2317 while ((de
= readdir(dir
)) != NULL
) {
2319 uint32_t i
, found
= 0;
2321 strbuf_setlen(&path
, dirnamelen
);
2322 strbuf_addstr(&path
, de
->d_name
);
2324 if (stat(path
.buf
, &st
) < 0)
2327 if (st
.st_mtime
> expire_time
)
2329 if (path
.len
< 6 || strcmp(path
.buf
+ path
.len
- 6, ".graph"))
2332 for (i
= 0; i
< ctx
->num_commit_graphs_after
; i
++) {
2333 if (!strcmp(ctx
->commit_graph_filenames_after
[i
],
2347 strbuf_release(&path
);
2350 int write_commit_graph(struct object_directory
*odb
,
2351 const struct string_list
*const pack_indexes
,
2352 struct oidset
*commits
,
2353 enum commit_graph_write_flags flags
,
2354 const struct commit_graph_opts
*opts
)
2356 struct repository
*r
= the_repository
;
2357 struct write_commit_graph_context
*ctx
;
2361 struct bloom_filter_settings bloom_settings
= DEFAULT_BLOOM_FILTER_SETTINGS
;
2362 struct topo_level_slab topo_levels
;
2364 prepare_repo_settings(r
);
2365 if (!r
->settings
.core_commit_graph
) {
2366 warning(_("attempting to write a commit-graph, but 'core.commitGraph' is disabled"));
2369 if (!commit_graph_compatible(r
))
2372 CALLOC_ARRAY(ctx
, 1);
2375 ctx
->append
= flags
& COMMIT_GRAPH_WRITE_APPEND
? 1 : 0;
2376 ctx
->report_progress
= flags
& COMMIT_GRAPH_WRITE_PROGRESS
? 1 : 0;
2377 ctx
->split
= flags
& COMMIT_GRAPH_WRITE_SPLIT
? 1 : 0;
2379 ctx
->total_bloom_filter_data_size
= 0;
2380 ctx
->write_generation_data
= (get_configured_generation_version(r
) == 2);
2381 ctx
->num_generation_data_overflows
= 0;
2383 bloom_settings
.bits_per_entry
= git_env_ulong("GIT_TEST_BLOOM_SETTINGS_BITS_PER_ENTRY",
2384 bloom_settings
.bits_per_entry
);
2385 bloom_settings
.num_hashes
= git_env_ulong("GIT_TEST_BLOOM_SETTINGS_NUM_HASHES",
2386 bloom_settings
.num_hashes
);
2387 bloom_settings
.max_changed_paths
= git_env_ulong("GIT_TEST_BLOOM_SETTINGS_MAX_CHANGED_PATHS",
2388 bloom_settings
.max_changed_paths
);
2389 ctx
->bloom_settings
= &bloom_settings
;
2391 init_topo_level_slab(&topo_levels
);
2392 ctx
->topo_levels
= &topo_levels
;
2394 prepare_commit_graph(ctx
->r
);
2395 if (ctx
->r
->objects
->commit_graph
) {
2396 struct commit_graph
*g
= ctx
->r
->objects
->commit_graph
;
2399 g
->topo_levels
= &topo_levels
;
2404 if (flags
& COMMIT_GRAPH_WRITE_BLOOM_FILTERS
)
2405 ctx
->changed_paths
= 1;
2406 if (!(flags
& COMMIT_GRAPH_NO_WRITE_BLOOM_FILTERS
)) {
2407 struct commit_graph
*g
;
2409 g
= ctx
->r
->objects
->commit_graph
;
2411 /* We have changed-paths already. Keep them in the next graph */
2412 if (g
&& g
->chunk_bloom_data
) {
2413 ctx
->changed_paths
= 1;
2414 ctx
->bloom_settings
= g
->bloom_filter_settings
;
2419 struct commit_graph
*g
= ctx
->r
->objects
->commit_graph
;
2422 ctx
->num_commit_graphs_before
++;
2426 if (ctx
->num_commit_graphs_before
) {
2427 ALLOC_ARRAY(ctx
->commit_graph_filenames_before
, ctx
->num_commit_graphs_before
);
2428 i
= ctx
->num_commit_graphs_before
;
2429 g
= ctx
->r
->objects
->commit_graph
;
2432 ctx
->commit_graph_filenames_before
[--i
] = xstrdup(g
->filename
);
2438 replace
= ctx
->opts
->split_flags
& COMMIT_GRAPH_SPLIT_REPLACE
;
2441 ctx
->approx_nr_objects
= repo_approximate_object_count(the_repository
);
2443 if (ctx
->append
&& ctx
->r
->objects
->commit_graph
) {
2444 struct commit_graph
*g
= ctx
->r
->objects
->commit_graph
;
2445 for (i
= 0; i
< g
->num_commits
; i
++) {
2446 struct object_id oid
;
2447 oidread(&oid
, g
->chunk_oid_lookup
+ g
->hash_len
* i
);
2448 oid_array_append(&ctx
->oids
, &oid
);
2453 ctx
->order_by_pack
= 1;
2454 if ((res
= fill_oids_from_packs(ctx
, pack_indexes
)))
2459 if ((res
= fill_oids_from_commits(ctx
, commits
)))
2463 if (!pack_indexes
&& !commits
) {
2464 ctx
->order_by_pack
= 1;
2465 fill_oids_from_all_packs(ctx
);
2468 close_reachable(ctx
);
2470 copy_oids_to_commits(ctx
);
2472 if (ctx
->commits
.nr
>= GRAPH_EDGE_LAST_MASK
) {
2473 error(_("too many commits to write graph"));
2478 if (!ctx
->commits
.nr
&& !replace
)
2482 split_graph_merge_strategy(ctx
);
2485 merge_commit_graphs(ctx
);
2487 ctx
->num_commit_graphs_after
= 1;
2489 ctx
->trust_generation_numbers
= validate_mixed_generation_chain(ctx
->r
->objects
->commit_graph
);
2491 compute_topological_levels(ctx
);
2492 if (ctx
->write_generation_data
)
2493 compute_generation_numbers(ctx
);
2495 if (ctx
->changed_paths
)
2496 compute_bloom_filters(ctx
);
2498 res
= write_commit_graph_file(ctx
);
2501 mark_commit_graphs(ctx
);
2503 expire_commit_graphs(ctx
);
2506 free(ctx
->graph_name
);
2507 free(ctx
->commits
.list
);
2508 oid_array_clear(&ctx
->oids
);
2509 clear_topo_level_slab(&topo_levels
);
2511 if (ctx
->commit_graph_filenames_after
) {
2512 for (i
= 0; i
< ctx
->num_commit_graphs_after
; i
++) {
2513 free(ctx
->commit_graph_filenames_after
[i
]);
2514 free(ctx
->commit_graph_hash_after
[i
]);
2517 for (i
= 0; i
< ctx
->num_commit_graphs_before
; i
++)
2518 free(ctx
->commit_graph_filenames_before
[i
]);
2520 free(ctx
->commit_graph_filenames_after
);
2521 free(ctx
->commit_graph_filenames_before
);
2522 free(ctx
->commit_graph_hash_after
);
2530 #define VERIFY_COMMIT_GRAPH_ERROR_HASH 2
2531 static int verify_commit_graph_error
;
2533 __attribute__((format (printf
, 1, 2)))
2534 static void graph_report(const char *fmt
, ...)
2538 verify_commit_graph_error
= 1;
2540 vfprintf(stderr
, fmt
, ap
);
2541 fprintf(stderr
, "\n");
2545 #define GENERATION_ZERO_EXISTS 1
2546 #define GENERATION_NUMBER_EXISTS 2
2548 static int commit_graph_checksum_valid(struct commit_graph
*g
)
2550 return hashfile_checksum_valid(g
->data
, g
->data_len
);
2553 int verify_commit_graph(struct repository
*r
, struct commit_graph
*g
, int flags
)
2555 uint32_t i
, cur_fanout_pos
= 0;
2556 struct object_id prev_oid
, cur_oid
;
2557 int generation_zero
= 0;
2558 struct progress
*progress
= NULL
;
2559 int local_error
= 0;
2562 graph_report("no commit-graph file loaded");
2566 verify_commit_graph_error
= verify_commit_graph_lite(g
);
2567 if (verify_commit_graph_error
)
2568 return verify_commit_graph_error
;
2570 if (!commit_graph_checksum_valid(g
)) {
2571 graph_report(_("the commit-graph file has incorrect checksum and is likely corrupt"));
2572 verify_commit_graph_error
= VERIFY_COMMIT_GRAPH_ERROR_HASH
;
2575 for (i
= 0; i
< g
->num_commits
; i
++) {
2576 struct commit
*graph_commit
;
2578 oidread(&cur_oid
, g
->chunk_oid_lookup
+ g
->hash_len
* i
);
2580 if (i
&& oidcmp(&prev_oid
, &cur_oid
) >= 0)
2581 graph_report(_("commit-graph has incorrect OID order: %s then %s"),
2582 oid_to_hex(&prev_oid
),
2583 oid_to_hex(&cur_oid
));
2585 oidcpy(&prev_oid
, &cur_oid
);
2587 while (cur_oid
.hash
[0] > cur_fanout_pos
) {
2588 uint32_t fanout_value
= get_be32(g
->chunk_oid_fanout
+ cur_fanout_pos
);
2590 if (i
!= fanout_value
)
2591 graph_report(_("commit-graph has incorrect fanout value: fanout[%d] = %u != %u"),
2592 cur_fanout_pos
, fanout_value
, i
);
2596 graph_commit
= lookup_commit(r
, &cur_oid
);
2597 if (!parse_commit_in_graph_one(r
, g
, graph_commit
))
2598 graph_report(_("failed to parse commit %s from commit-graph"),
2599 oid_to_hex(&cur_oid
));
2602 while (cur_fanout_pos
< 256) {
2603 uint32_t fanout_value
= get_be32(g
->chunk_oid_fanout
+ cur_fanout_pos
);
2605 if (g
->num_commits
!= fanout_value
)
2606 graph_report(_("commit-graph has incorrect fanout value: fanout[%d] = %u != %u"),
2607 cur_fanout_pos
, fanout_value
, i
);
2612 if (verify_commit_graph_error
& ~VERIFY_COMMIT_GRAPH_ERROR_HASH
)
2613 return verify_commit_graph_error
;
2615 if (flags
& COMMIT_GRAPH_WRITE_PROGRESS
)
2616 progress
= start_progress(_("Verifying commits in commit graph"),
2619 for (i
= 0; i
< g
->num_commits
; i
++) {
2620 struct commit
*graph_commit
, *odb_commit
;
2621 struct commit_list
*graph_parents
, *odb_parents
;
2622 timestamp_t max_generation
= 0;
2623 timestamp_t generation
;
2625 display_progress(progress
, i
+ 1);
2626 oidread(&cur_oid
, g
->chunk_oid_lookup
+ g
->hash_len
* i
);
2628 graph_commit
= lookup_commit(r
, &cur_oid
);
2629 odb_commit
= (struct commit
*)create_object(r
, &cur_oid
, alloc_commit_node(r
));
2630 if (repo_parse_commit_internal(r
, odb_commit
, 0, 0)) {
2631 graph_report(_("failed to parse commit %s from object database for commit-graph"),
2632 oid_to_hex(&cur_oid
));
2636 if (!oideq(&get_commit_tree_in_graph_one(r
, g
, graph_commit
)->object
.oid
,
2637 get_commit_tree_oid(odb_commit
)))
2638 graph_report(_("root tree OID for commit %s in commit-graph is %s != %s"),
2639 oid_to_hex(&cur_oid
),
2640 oid_to_hex(get_commit_tree_oid(graph_commit
)),
2641 oid_to_hex(get_commit_tree_oid(odb_commit
)));
2643 graph_parents
= graph_commit
->parents
;
2644 odb_parents
= odb_commit
->parents
;
2646 while (graph_parents
) {
2648 graph_report(_("commit-graph parent list for commit %s is too long"),
2649 oid_to_hex(&cur_oid
));
2653 /* parse parent in case it is in a base graph */
2654 parse_commit_in_graph_one(r
, g
, graph_parents
->item
);
2656 if (!oideq(&graph_parents
->item
->object
.oid
, &odb_parents
->item
->object
.oid
))
2657 graph_report(_("commit-graph parent for %s is %s != %s"),
2658 oid_to_hex(&cur_oid
),
2659 oid_to_hex(&graph_parents
->item
->object
.oid
),
2660 oid_to_hex(&odb_parents
->item
->object
.oid
));
2662 generation
= commit_graph_generation(graph_parents
->item
);
2663 if (generation
> max_generation
)
2664 max_generation
= generation
;
2666 graph_parents
= graph_parents
->next
;
2667 odb_parents
= odb_parents
->next
;
2671 graph_report(_("commit-graph parent list for commit %s terminates early"),
2672 oid_to_hex(&cur_oid
));
2674 if (!commit_graph_generation(graph_commit
)) {
2675 if (generation_zero
== GENERATION_NUMBER_EXISTS
)
2676 graph_report(_("commit-graph has generation number zero for commit %s, but non-zero elsewhere"),
2677 oid_to_hex(&cur_oid
));
2678 generation_zero
= GENERATION_ZERO_EXISTS
;
2679 } else if (generation_zero
== GENERATION_ZERO_EXISTS
)
2680 graph_report(_("commit-graph has non-zero generation number for commit %s, but zero elsewhere"),
2681 oid_to_hex(&cur_oid
));
2683 if (generation_zero
== GENERATION_ZERO_EXISTS
)
2687 * If we are using topological level and one of our parents has
2688 * generation GENERATION_NUMBER_V1_MAX, then our generation is
2689 * also GENERATION_NUMBER_V1_MAX. Decrement to avoid extra logic
2690 * in the following condition.
2692 if (!g
->read_generation_data
&& max_generation
== GENERATION_NUMBER_V1_MAX
)
2695 generation
= commit_graph_generation(graph_commit
);
2696 if (generation
< max_generation
+ 1)
2697 graph_report(_("commit-graph generation for commit %s is %"PRItime
" < %"PRItime
),
2698 oid_to_hex(&cur_oid
),
2700 max_generation
+ 1);
2702 if (graph_commit
->date
!= odb_commit
->date
)
2703 graph_report(_("commit date for commit %s in commit-graph is %"PRItime
" != %"PRItime
),
2704 oid_to_hex(&cur_oid
),
2708 stop_progress(&progress
);
2710 local_error
= verify_commit_graph_error
;
2712 if (!(flags
& COMMIT_GRAPH_VERIFY_SHALLOW
) && g
->base_graph
)
2713 local_error
|= verify_commit_graph(r
, g
->base_graph
, flags
);
2718 void free_commit_graph(struct commit_graph
*g
)
2723 munmap((void *)g
->data
, g
->data_len
);
2727 free(g
->bloom_filter_settings
);
2731 void disable_commit_graph(struct repository
*r
)
2733 r
->commit_graph_disabled
= 1;