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
);
126 return GENERATION_NUMBER_INFINITY
;
127 else if (data
->graph_pos
== COMMIT_NOT_FROM_GRAPH
)
128 return GENERATION_NUMBER_INFINITY
;
130 return data
->generation
;
133 static struct commit_graph_data
*commit_graph_data_at(const struct commit
*c
)
135 unsigned int i
, nth_slab
;
136 struct commit_graph_data
*data
=
137 commit_graph_data_slab_peek(&commit_graph_data_slab
, c
);
142 nth_slab
= c
->index
/ commit_graph_data_slab
.slab_size
;
143 data
= commit_graph_data_slab_at(&commit_graph_data_slab
, c
);
146 * commit-slab initializes elements with zero, overwrite this with
147 * COMMIT_NOT_FROM_GRAPH for graph_pos.
149 * We avoid initializing generation with checking if graph position
150 * is not COMMIT_NOT_FROM_GRAPH.
152 for (i
= 0; i
< commit_graph_data_slab
.slab_size
; i
++) {
153 commit_graph_data_slab
.slab
[nth_slab
][i
].graph_pos
=
154 COMMIT_NOT_FROM_GRAPH
;
161 * Should be used only while writing commit-graph as it compares
162 * generation value of commits by directly accessing commit-slab.
164 static int commit_gen_cmp(const void *va
, const void *vb
)
166 const struct commit
*a
= *(const struct commit
**)va
;
167 const struct commit
*b
= *(const struct commit
**)vb
;
169 const timestamp_t generation_a
= commit_graph_data_at(a
)->generation
;
170 const timestamp_t generation_b
= commit_graph_data_at(b
)->generation
;
171 /* lower generation commits first */
172 if (generation_a
< generation_b
)
174 else if (generation_a
> generation_b
)
177 /* use date as a heuristic when generations are equal */
178 if (a
->date
< b
->date
)
180 else if (a
->date
> b
->date
)
185 char *get_commit_graph_filename(struct object_directory
*obj_dir
)
187 return xstrfmt("%s/info/commit-graph", obj_dir
->path
);
190 static char *get_split_graph_filename(struct object_directory
*odb
,
193 return xstrfmt("%s/info/commit-graphs/graph-%s.graph", odb
->path
,
197 char *get_commit_graph_chain_filename(struct object_directory
*odb
)
199 return xstrfmt("%s/info/commit-graphs/commit-graph-chain", odb
->path
);
202 static struct commit_graph
*alloc_commit_graph(void)
204 struct commit_graph
*g
= xcalloc(1, sizeof(*g
));
209 extern int read_replace_refs
;
211 static int commit_graph_compatible(struct repository
*r
)
216 if (read_replace_refs
) {
217 prepare_replace_object(r
);
218 if (hashmap_get_size(&r
->objects
->replace_map
->map
))
222 prepare_commit_graft(r
);
223 if (r
->parsed_objects
&&
224 (r
->parsed_objects
->grafts_nr
|| r
->parsed_objects
->substituted_parent
))
226 if (is_repository_shallow(r
))
232 int open_commit_graph(const char *graph_file
, int *fd
, struct stat
*st
)
234 *fd
= git_open(graph_file
);
237 if (fstat(*fd
, st
)) {
244 struct commit_graph
*load_commit_graph_one_fd_st(struct repository
*r
,
245 int fd
, struct stat
*st
,
246 struct object_directory
*odb
)
250 struct commit_graph
*ret
;
252 graph_size
= xsize_t(st
->st_size
);
254 if (graph_size
< GRAPH_MIN_SIZE
) {
256 error(_("commit-graph file is too small"));
259 graph_map
= xmmap(NULL
, graph_size
, PROT_READ
, MAP_PRIVATE
, fd
, 0);
261 prepare_repo_settings(r
);
262 ret
= parse_commit_graph(&r
->settings
, graph_map
, graph_size
);
267 munmap(graph_map
, graph_size
);
272 static int verify_commit_graph_lite(struct commit_graph
*g
)
275 * Basic validation shared between parse_commit_graph()
276 * which'll be called every time the graph is used, and the
277 * much more expensive verify_commit_graph() used by
278 * "commit-graph verify".
280 * There should only be very basic checks here to ensure that
281 * we don't e.g. segfault in fill_commit_in_graph(), but
282 * because this is a very hot codepath nothing that e.g. loops
283 * over g->num_commits, or runs a checksum on the commit-graph
286 if (!g
->chunk_oid_fanout
) {
287 error("commit-graph is missing the OID Fanout chunk");
290 if (!g
->chunk_oid_lookup
) {
291 error("commit-graph is missing the OID Lookup chunk");
294 if (!g
->chunk_commit_data
) {
295 error("commit-graph is missing the Commit Data chunk");
302 static int graph_read_oid_lookup(const unsigned char *chunk_start
,
303 size_t chunk_size
, void *data
)
305 struct commit_graph
*g
= data
;
306 g
->chunk_oid_lookup
= chunk_start
;
307 g
->num_commits
= chunk_size
/ g
->hash_len
;
311 static int graph_read_bloom_data(const unsigned char *chunk_start
,
312 size_t chunk_size
, void *data
)
314 struct commit_graph
*g
= data
;
315 uint32_t hash_version
;
316 g
->chunk_bloom_data
= chunk_start
;
317 hash_version
= get_be32(chunk_start
);
319 if (hash_version
!= 1)
322 g
->bloom_filter_settings
= xmalloc(sizeof(struct bloom_filter_settings
));
323 g
->bloom_filter_settings
->hash_version
= hash_version
;
324 g
->bloom_filter_settings
->num_hashes
= get_be32(chunk_start
+ 4);
325 g
->bloom_filter_settings
->bits_per_entry
= get_be32(chunk_start
+ 8);
326 g
->bloom_filter_settings
->max_changed_paths
= DEFAULT_BLOOM_MAX_CHANGES
;
331 struct commit_graph
*parse_commit_graph(struct repo_settings
*s
,
332 void *graph_map
, size_t graph_size
)
334 const unsigned char *data
;
335 struct commit_graph
*graph
;
336 uint32_t graph_signature
;
337 unsigned char graph_version
, hash_version
;
338 struct chunkfile
*cf
= NULL
;
343 if (graph_size
< GRAPH_MIN_SIZE
)
346 data
= (const unsigned char *)graph_map
;
348 graph_signature
= get_be32(data
);
349 if (graph_signature
!= GRAPH_SIGNATURE
) {
350 error(_("commit-graph signature %X does not match signature %X"),
351 graph_signature
, GRAPH_SIGNATURE
);
355 graph_version
= *(unsigned char*)(data
+ 4);
356 if (graph_version
!= GRAPH_VERSION
) {
357 error(_("commit-graph version %X does not match version %X"),
358 graph_version
, GRAPH_VERSION
);
362 hash_version
= *(unsigned char*)(data
+ 5);
363 if (hash_version
!= oid_version(the_hash_algo
)) {
364 error(_("commit-graph hash version %X does not match version %X"),
365 hash_version
, oid_version(the_hash_algo
));
369 graph
= alloc_commit_graph();
371 graph
->hash_len
= the_hash_algo
->rawsz
;
372 graph
->num_chunks
= *(unsigned char*)(data
+ 6);
373 graph
->data
= graph_map
;
374 graph
->data_len
= graph_size
;
376 if (graph_size
< GRAPH_HEADER_SIZE
+
377 (graph
->num_chunks
+ 1) * CHUNK_TOC_ENTRY_SIZE
+
378 GRAPH_FANOUT_SIZE
+ the_hash_algo
->rawsz
) {
379 error(_("commit-graph file is too small to hold %u chunks"),
385 cf
= init_chunkfile(NULL
);
387 if (read_table_of_contents(cf
, graph
->data
, graph_size
,
388 GRAPH_HEADER_SIZE
, graph
->num_chunks
))
389 goto free_and_return
;
391 pair_chunk(cf
, GRAPH_CHUNKID_OIDFANOUT
,
392 (const unsigned char **)&graph
->chunk_oid_fanout
);
393 read_chunk(cf
, GRAPH_CHUNKID_OIDLOOKUP
, graph_read_oid_lookup
, graph
);
394 pair_chunk(cf
, GRAPH_CHUNKID_DATA
, &graph
->chunk_commit_data
);
395 pair_chunk(cf
, GRAPH_CHUNKID_EXTRAEDGES
, &graph
->chunk_extra_edges
);
396 pair_chunk(cf
, GRAPH_CHUNKID_BASE
, &graph
->chunk_base_graphs
);
398 if (s
->commit_graph_generation_version
>= 2) {
399 pair_chunk(cf
, GRAPH_CHUNKID_GENERATION_DATA
,
400 &graph
->chunk_generation_data
);
401 pair_chunk(cf
, GRAPH_CHUNKID_GENERATION_DATA_OVERFLOW
,
402 &graph
->chunk_generation_data_overflow
);
404 if (graph
->chunk_generation_data
)
405 graph
->read_generation_data
= 1;
408 if (s
->commit_graph_read_changed_paths
) {
409 pair_chunk(cf
, GRAPH_CHUNKID_BLOOMINDEXES
,
410 &graph
->chunk_bloom_indexes
);
411 read_chunk(cf
, GRAPH_CHUNKID_BLOOMDATA
,
412 graph_read_bloom_data
, graph
);
415 if (graph
->chunk_bloom_indexes
&& graph
->chunk_bloom_data
) {
416 init_bloom_filters();
418 /* We need both the bloom chunks to exist together. Else ignore the data */
419 graph
->chunk_bloom_indexes
= NULL
;
420 graph
->chunk_bloom_data
= NULL
;
421 FREE_AND_NULL(graph
->bloom_filter_settings
);
424 oidread(&graph
->oid
, graph
->data
+ graph
->data_len
- graph
->hash_len
);
426 if (verify_commit_graph_lite(graph
))
427 goto free_and_return
;
434 free(graph
->bloom_filter_settings
);
439 static struct commit_graph
*load_commit_graph_one(struct repository
*r
,
440 const char *graph_file
,
441 struct object_directory
*odb
)
446 struct commit_graph
*g
;
447 int open_ok
= open_commit_graph(graph_file
, &fd
, &st
);
452 g
= load_commit_graph_one_fd_st(r
, fd
, &st
, odb
);
455 g
->filename
= xstrdup(graph_file
);
460 static struct commit_graph
*load_commit_graph_v1(struct repository
*r
,
461 struct object_directory
*odb
)
463 char *graph_name
= get_commit_graph_filename(odb
);
464 struct commit_graph
*g
= load_commit_graph_one(r
, graph_name
, odb
);
470 static int add_graph_to_chain(struct commit_graph
*g
,
471 struct commit_graph
*chain
,
472 struct object_id
*oids
,
475 struct commit_graph
*cur_g
= chain
;
477 if (n
&& !g
->chunk_base_graphs
) {
478 warning(_("commit-graph has no base graphs chunk"));
486 !oideq(&oids
[n
], &cur_g
->oid
) ||
487 !hasheq(oids
[n
].hash
, g
->chunk_base_graphs
+ g
->hash_len
* n
)) {
488 warning(_("commit-graph chain does not match"));
492 cur_g
= cur_g
->base_graph
;
495 g
->base_graph
= chain
;
498 g
->num_commits_in_base
= chain
->num_commits
+ chain
->num_commits_in_base
;
503 static struct commit_graph
*load_commit_graph_chain(struct repository
*r
,
504 struct object_directory
*odb
)
506 struct commit_graph
*graph_chain
= NULL
;
507 struct strbuf line
= STRBUF_INIT
;
509 struct object_id
*oids
;
510 int i
= 0, valid
= 1, count
;
511 char *chain_name
= get_commit_graph_chain_filename(odb
);
515 fp
= fopen(chain_name
, "r");
516 stat_res
= stat(chain_name
, &st
);
522 st
.st_size
<= the_hash_algo
->hexsz
) {
527 count
= st
.st_size
/ (the_hash_algo
->hexsz
+ 1);
528 CALLOC_ARRAY(oids
, count
);
532 for (i
= 0; i
< count
; i
++) {
533 struct object_directory
*odb
;
535 if (strbuf_getline_lf(&line
, fp
) == EOF
)
538 if (get_oid_hex(line
.buf
, &oids
[i
])) {
539 warning(_("invalid commit-graph chain: line '%s' not a hash"),
546 for (odb
= r
->objects
->odb
; odb
; odb
= odb
->next
) {
547 char *graph_name
= get_split_graph_filename(odb
, line
.buf
);
548 struct commit_graph
*g
= load_commit_graph_one(r
, graph_name
, odb
);
553 if (add_graph_to_chain(g
, graph_chain
, oids
, i
)) {
563 warning(_("unable to find all commit-graph files"));
570 strbuf_release(&line
);
576 * returns 1 if and only if all graphs in the chain have
577 * corrected commit dates stored in the generation_data chunk.
579 static int validate_mixed_generation_chain(struct commit_graph
*g
)
581 int read_generation_data
= 1;
582 struct commit_graph
*p
= g
;
584 while (read_generation_data
&& p
) {
585 read_generation_data
= p
->read_generation_data
;
589 if (read_generation_data
)
593 g
->read_generation_data
= 0;
600 struct commit_graph
*read_commit_graph_one(struct repository
*r
,
601 struct object_directory
*odb
)
603 struct commit_graph
*g
= load_commit_graph_v1(r
, odb
);
606 g
= load_commit_graph_chain(r
, odb
);
608 validate_mixed_generation_chain(g
);
613 static void prepare_commit_graph_one(struct repository
*r
,
614 struct object_directory
*odb
)
617 if (r
->objects
->commit_graph
)
620 r
->objects
->commit_graph
= read_commit_graph_one(r
, odb
);
624 * Return 1 if commit_graph is non-NULL, and 0 otherwise.
626 * On the first invocation, this function attempts to load the commit
627 * graph if the_repository is configured to have one.
629 static int prepare_commit_graph(struct repository
*r
)
631 struct object_directory
*odb
;
634 * Early return if there is no git dir or if the commit graph is
637 * This must come before the "already attempted?" check below, because
638 * we want to disable even an already-loaded graph file.
640 if (!r
->gitdir
|| r
->commit_graph_disabled
)
643 if (r
->objects
->commit_graph_attempted
)
644 return !!r
->objects
->commit_graph
;
645 r
->objects
->commit_graph_attempted
= 1;
647 prepare_repo_settings(r
);
649 if (!git_env_bool(GIT_TEST_COMMIT_GRAPH
, 0) &&
650 r
->settings
.core_commit_graph
!= 1)
652 * This repository is not configured to use commit graphs, so
653 * do not load one. (But report commit_graph_attempted anyway
654 * so that commit graph loading is not attempted again for this
659 if (!commit_graph_compatible(r
))
663 for (odb
= r
->objects
->odb
;
664 !r
->objects
->commit_graph
&& odb
;
666 prepare_commit_graph_one(r
, odb
);
667 return !!r
->objects
->commit_graph
;
670 int generation_numbers_enabled(struct repository
*r
)
672 uint32_t first_generation
;
673 struct commit_graph
*g
;
674 if (!prepare_commit_graph(r
))
677 g
= r
->objects
->commit_graph
;
682 first_generation
= get_be32(g
->chunk_commit_data
+
683 g
->hash_len
+ 8) >> 2;
685 return !!first_generation
;
688 int corrected_commit_dates_enabled(struct repository
*r
)
690 struct commit_graph
*g
;
691 if (!prepare_commit_graph(r
))
694 g
= r
->objects
->commit_graph
;
699 return g
->read_generation_data
;
702 struct bloom_filter_settings
*get_bloom_filter_settings(struct repository
*r
)
704 struct commit_graph
*g
= r
->objects
->commit_graph
;
706 if (g
->bloom_filter_settings
)
707 return g
->bloom_filter_settings
;
713 static void close_commit_graph_one(struct commit_graph
*g
)
718 clear_commit_graph_data_slab(&commit_graph_data_slab
);
719 close_commit_graph_one(g
->base_graph
);
720 free_commit_graph(g
);
723 void close_commit_graph(struct raw_object_store
*o
)
725 close_commit_graph_one(o
->commit_graph
);
726 o
->commit_graph
= NULL
;
729 static int bsearch_graph(struct commit_graph
*g
, const struct object_id
*oid
, uint32_t *pos
)
731 return bsearch_hash(oid
->hash
, g
->chunk_oid_fanout
,
732 g
->chunk_oid_lookup
, g
->hash_len
, pos
);
735 static void load_oid_from_graph(struct commit_graph
*g
,
737 struct object_id
*oid
)
741 while (g
&& pos
< g
->num_commits_in_base
)
745 BUG("NULL commit-graph");
747 if (pos
>= g
->num_commits
+ g
->num_commits_in_base
)
748 die(_("invalid commit position. commit-graph is likely corrupt"));
750 lex_index
= pos
- g
->num_commits_in_base
;
752 oidread(oid
, g
->chunk_oid_lookup
+ g
->hash_len
* lex_index
);
755 static struct commit_list
**insert_parent_or_die(struct repository
*r
,
756 struct commit_graph
*g
,
758 struct commit_list
**pptr
)
761 struct object_id oid
;
763 if (pos
>= g
->num_commits
+ g
->num_commits_in_base
)
764 die("invalid parent position %"PRIu32
, pos
);
766 load_oid_from_graph(g
, pos
, &oid
);
767 c
= lookup_commit(r
, &oid
);
769 die(_("could not find commit %s"), oid_to_hex(&oid
));
770 commit_graph_data_at(c
)->graph_pos
= pos
;
771 return &commit_list_insert(c
, pptr
)->next
;
774 static void fill_commit_graph_info(struct commit
*item
, struct commit_graph
*g
, uint32_t pos
)
776 const unsigned char *commit_data
;
777 struct commit_graph_data
*graph_data
;
778 uint32_t lex_index
, offset_pos
;
779 uint64_t date_high
, date_low
, offset
;
781 while (pos
< g
->num_commits_in_base
)
784 if (pos
>= g
->num_commits
+ g
->num_commits_in_base
)
785 die(_("invalid commit position. commit-graph is likely corrupt"));
787 lex_index
= pos
- g
->num_commits_in_base
;
788 commit_data
= g
->chunk_commit_data
+ GRAPH_DATA_WIDTH
* lex_index
;
790 graph_data
= commit_graph_data_at(item
);
791 graph_data
->graph_pos
= pos
;
793 date_high
= get_be32(commit_data
+ g
->hash_len
+ 8) & 0x3;
794 date_low
= get_be32(commit_data
+ g
->hash_len
+ 12);
795 item
->date
= (timestamp_t
)((date_high
<< 32) | date_low
);
797 if (g
->read_generation_data
) {
798 offset
= (timestamp_t
)get_be32(g
->chunk_generation_data
+ sizeof(uint32_t) * lex_index
);
800 if (offset
& CORRECTED_COMMIT_DATE_OFFSET_OVERFLOW
) {
801 if (!g
->chunk_generation_data_overflow
)
802 die(_("commit-graph requires overflow generation data but has none"));
804 offset_pos
= offset
^ CORRECTED_COMMIT_DATE_OFFSET_OVERFLOW
;
805 graph_data
->generation
= item
->date
+ get_be64(g
->chunk_generation_data_overflow
+ 8 * offset_pos
);
807 graph_data
->generation
= item
->date
+ offset
;
809 graph_data
->generation
= get_be32(commit_data
+ g
->hash_len
+ 8) >> 2;
812 *topo_level_slab_at(g
->topo_levels
, item
) = get_be32(commit_data
+ g
->hash_len
+ 8) >> 2;
815 static inline void set_commit_tree(struct commit
*c
, struct tree
*t
)
820 static int fill_commit_in_graph(struct repository
*r
,
822 struct commit_graph
*g
, uint32_t pos
)
825 uint32_t *parent_data_ptr
;
826 struct commit_list
**pptr
;
827 const unsigned char *commit_data
;
830 while (pos
< g
->num_commits_in_base
)
833 fill_commit_graph_info(item
, g
, pos
);
835 lex_index
= pos
- g
->num_commits_in_base
;
836 commit_data
= g
->chunk_commit_data
+ (g
->hash_len
+ 16) * lex_index
;
838 item
->object
.parsed
= 1;
840 set_commit_tree(item
, NULL
);
842 pptr
= &item
->parents
;
844 edge_value
= get_be32(commit_data
+ g
->hash_len
);
845 if (edge_value
== GRAPH_PARENT_NONE
)
847 pptr
= insert_parent_or_die(r
, g
, edge_value
, pptr
);
849 edge_value
= get_be32(commit_data
+ g
->hash_len
+ 4);
850 if (edge_value
== GRAPH_PARENT_NONE
)
852 if (!(edge_value
& GRAPH_EXTRA_EDGES_NEEDED
)) {
853 pptr
= insert_parent_or_die(r
, g
, edge_value
, pptr
);
857 parent_data_ptr
= (uint32_t*)(g
->chunk_extra_edges
+
858 4 * (uint64_t)(edge_value
& GRAPH_EDGE_LAST_MASK
));
860 edge_value
= get_be32(parent_data_ptr
);
861 pptr
= insert_parent_or_die(r
, g
,
862 edge_value
& GRAPH_EDGE_LAST_MASK
,
865 } while (!(edge_value
& GRAPH_LAST_EDGE
));
870 static int search_commit_pos_in_graph(const struct object_id
*id
, struct commit_graph
*g
, uint32_t *pos
)
872 struct commit_graph
*cur_g
= g
;
875 while (cur_g
&& !bsearch_graph(cur_g
, id
, &lex_index
))
876 cur_g
= cur_g
->base_graph
;
879 *pos
= lex_index
+ cur_g
->num_commits_in_base
;
886 static int find_commit_pos_in_graph(struct commit
*item
, struct commit_graph
*g
, uint32_t *pos
)
888 uint32_t graph_pos
= commit_graph_position(item
);
889 if (graph_pos
!= COMMIT_NOT_FROM_GRAPH
) {
893 return search_commit_pos_in_graph(&item
->object
.oid
, g
, pos
);
897 int repo_find_commit_pos_in_graph(struct repository
*r
, struct commit
*c
,
900 if (!prepare_commit_graph(r
))
902 return find_commit_pos_in_graph(c
, r
->objects
->commit_graph
, pos
);
905 struct commit
*lookup_commit_in_graph(struct repository
*repo
, const struct object_id
*id
)
907 struct commit
*commit
;
910 if (!prepare_commit_graph(repo
))
912 if (!search_commit_pos_in_graph(id
, repo
->objects
->commit_graph
, &pos
))
914 if (!has_object(repo
, id
, 0))
917 commit
= lookup_commit(repo
, id
);
920 if (commit
->object
.parsed
)
923 if (!fill_commit_in_graph(repo
, commit
, repo
->objects
->commit_graph
, pos
))
929 static int parse_commit_in_graph_one(struct repository
*r
,
930 struct commit_graph
*g
,
935 if (item
->object
.parsed
)
938 if (find_commit_pos_in_graph(item
, g
, &pos
))
939 return fill_commit_in_graph(r
, item
, g
, pos
);
944 int parse_commit_in_graph(struct repository
*r
, struct commit
*item
)
946 static int checked_env
= 0;
949 git_env_bool(GIT_TEST_COMMIT_GRAPH_DIE_ON_PARSE
, 0))
950 die("dying as requested by the '%s' variable on commit-graph parse!",
951 GIT_TEST_COMMIT_GRAPH_DIE_ON_PARSE
);
954 if (!prepare_commit_graph(r
))
956 return parse_commit_in_graph_one(r
, r
->objects
->commit_graph
, item
);
959 void load_commit_graph_info(struct repository
*r
, struct commit
*item
)
962 if (repo_find_commit_pos_in_graph(r
, item
, &pos
))
963 fill_commit_graph_info(item
, r
->objects
->commit_graph
, pos
);
966 static struct tree
*load_tree_for_commit(struct repository
*r
,
967 struct commit_graph
*g
,
970 struct object_id oid
;
971 const unsigned char *commit_data
;
972 uint32_t graph_pos
= commit_graph_position(c
);
974 while (graph_pos
< g
->num_commits_in_base
)
977 commit_data
= g
->chunk_commit_data
+
978 GRAPH_DATA_WIDTH
* (graph_pos
- g
->num_commits_in_base
);
980 oidread(&oid
, commit_data
);
981 set_commit_tree(c
, lookup_tree(r
, &oid
));
983 return c
->maybe_tree
;
986 static struct tree
*get_commit_tree_in_graph_one(struct repository
*r
,
987 struct commit_graph
*g
,
988 const struct commit
*c
)
991 return c
->maybe_tree
;
992 if (commit_graph_position(c
) == COMMIT_NOT_FROM_GRAPH
)
993 BUG("get_commit_tree_in_graph_one called from non-commit-graph commit");
995 return load_tree_for_commit(r
, g
, (struct commit
*)c
);
998 struct tree
*get_commit_tree_in_graph(struct repository
*r
, const struct commit
*c
)
1000 return get_commit_tree_in_graph_one(r
, r
->objects
->commit_graph
, c
);
1003 struct packed_commit_list
{
1004 struct commit
**list
;
1009 struct write_commit_graph_context
{
1010 struct repository
*r
;
1011 struct object_directory
*odb
;
1013 struct oid_array oids
;
1014 struct packed_commit_list commits
;
1015 int num_extra_edges
;
1016 int num_generation_data_overflows
;
1017 unsigned long approx_nr_objects
;
1018 struct progress
*progress
;
1020 uint64_t progress_cnt
;
1022 char *base_graph_name
;
1023 int num_commit_graphs_before
;
1024 int num_commit_graphs_after
;
1025 char **commit_graph_filenames_before
;
1026 char **commit_graph_filenames_after
;
1027 char **commit_graph_hash_after
;
1028 uint32_t new_num_commits_in_base
;
1029 struct commit_graph
*new_base_graph
;
1036 write_generation_data
:1,
1037 trust_generation_numbers
:1;
1039 struct topo_level_slab
*topo_levels
;
1040 const struct commit_graph_opts
*opts
;
1041 size_t total_bloom_filter_data_size
;
1042 const struct bloom_filter_settings
*bloom_settings
;
1044 int count_bloom_filter_computed
;
1045 int count_bloom_filter_not_computed
;
1046 int count_bloom_filter_trunc_empty
;
1047 int count_bloom_filter_trunc_large
;
1050 static int write_graph_chunk_fanout(struct hashfile
*f
,
1053 struct write_commit_graph_context
*ctx
= data
;
1055 struct commit
**list
= ctx
->commits
.list
;
1058 * Write the first-level table (the list is sorted,
1059 * but we use a 256-entry lookup to be able to avoid
1060 * having to do eight extra binary search iterations).
1062 for (i
= 0; i
< 256; i
++) {
1063 while (count
< ctx
->commits
.nr
) {
1064 if ((*list
)->object
.oid
.hash
[0] != i
)
1066 display_progress(ctx
->progress
, ++ctx
->progress_cnt
);
1071 hashwrite_be32(f
, count
);
1077 static int write_graph_chunk_oids(struct hashfile
*f
,
1080 struct write_commit_graph_context
*ctx
= data
;
1081 struct commit
**list
= ctx
->commits
.list
;
1083 for (count
= 0; count
< ctx
->commits
.nr
; count
++, list
++) {
1084 display_progress(ctx
->progress
, ++ctx
->progress_cnt
);
1085 hashwrite(f
, (*list
)->object
.oid
.hash
, the_hash_algo
->rawsz
);
1091 static const struct object_id
*commit_to_oid(size_t index
, const void *table
)
1093 const struct commit
* const *commits
= table
;
1094 return &commits
[index
]->object
.oid
;
1097 static int write_graph_chunk_data(struct hashfile
*f
,
1100 struct write_commit_graph_context
*ctx
= data
;
1101 struct commit
**list
= ctx
->commits
.list
;
1102 struct commit
**last
= ctx
->commits
.list
+ ctx
->commits
.nr
;
1103 uint32_t num_extra_edges
= 0;
1105 while (list
< last
) {
1106 struct commit_list
*parent
;
1107 struct object_id
*tree
;
1109 uint32_t packedDate
[2];
1110 display_progress(ctx
->progress
, ++ctx
->progress_cnt
);
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
);
1118 parent
= (*list
)->parents
;
1121 edge_value
= GRAPH_PARENT_NONE
;
1123 edge_value
= oid_pos(&parent
->item
->object
.oid
,
1128 if (edge_value
>= 0)
1129 edge_value
+= ctx
->new_num_commits_in_base
;
1130 else if (ctx
->new_base_graph
) {
1132 if (find_commit_pos_in_graph(parent
->item
,
1133 ctx
->new_base_graph
,
1139 BUG("missing parent %s for commit %s",
1140 oid_to_hex(&parent
->item
->object
.oid
),
1141 oid_to_hex(&(*list
)->object
.oid
));
1144 hashwrite_be32(f
, edge_value
);
1147 parent
= parent
->next
;
1150 edge_value
= GRAPH_PARENT_NONE
;
1151 else if (parent
->next
)
1152 edge_value
= GRAPH_EXTRA_EDGES_NEEDED
| num_extra_edges
;
1154 edge_value
= oid_pos(&parent
->item
->object
.oid
,
1159 if (edge_value
>= 0)
1160 edge_value
+= ctx
->new_num_commits_in_base
;
1161 else if (ctx
->new_base_graph
) {
1163 if (find_commit_pos_in_graph(parent
->item
,
1164 ctx
->new_base_graph
,
1170 BUG("missing parent %s for commit %s",
1171 oid_to_hex(&parent
->item
->object
.oid
),
1172 oid_to_hex(&(*list
)->object
.oid
));
1175 hashwrite_be32(f
, edge_value
);
1177 if (edge_value
& GRAPH_EXTRA_EDGES_NEEDED
) {
1180 parent
= parent
->next
;
1184 if (sizeof((*list
)->date
) > 4)
1185 packedDate
[0] = htonl(((*list
)->date
>> 32) & 0x3);
1189 packedDate
[0] |= htonl(*topo_level_slab_at(ctx
->topo_levels
, *list
) << 2);
1191 packedDate
[1] = htonl((*list
)->date
);
1192 hashwrite(f
, packedDate
, 8);
1200 static int write_graph_chunk_generation_data(struct hashfile
*f
,
1203 struct write_commit_graph_context
*ctx
= data
;
1204 int i
, num_generation_data_overflows
= 0;
1206 for (i
= 0; i
< ctx
->commits
.nr
; i
++) {
1207 struct commit
*c
= ctx
->commits
.list
[i
];
1209 repo_parse_commit(ctx
->r
, c
);
1210 offset
= commit_graph_data_at(c
)->generation
- c
->date
;
1211 display_progress(ctx
->progress
, ++ctx
->progress_cnt
);
1213 if (offset
> GENERATION_NUMBER_V2_OFFSET_MAX
) {
1214 offset
= CORRECTED_COMMIT_DATE_OFFSET_OVERFLOW
| num_generation_data_overflows
;
1215 num_generation_data_overflows
++;
1218 hashwrite_be32(f
, offset
);
1224 static int write_graph_chunk_generation_data_overflow(struct hashfile
*f
,
1227 struct write_commit_graph_context
*ctx
= data
;
1229 for (i
= 0; i
< ctx
->commits
.nr
; i
++) {
1230 struct commit
*c
= ctx
->commits
.list
[i
];
1231 timestamp_t offset
= commit_graph_data_at(c
)->generation
- c
->date
;
1232 display_progress(ctx
->progress
, ++ctx
->progress_cnt
);
1234 if (offset
> GENERATION_NUMBER_V2_OFFSET_MAX
) {
1235 hashwrite_be32(f
, offset
>> 32);
1236 hashwrite_be32(f
, (uint32_t) offset
);
1243 static int write_graph_chunk_extra_edges(struct hashfile
*f
,
1246 struct write_commit_graph_context
*ctx
= data
;
1247 struct commit
**list
= ctx
->commits
.list
;
1248 struct commit
**last
= ctx
->commits
.list
+ ctx
->commits
.nr
;
1249 struct commit_list
*parent
;
1251 while (list
< last
) {
1252 int num_parents
= 0;
1254 display_progress(ctx
->progress
, ++ctx
->progress_cnt
);
1256 for (parent
= (*list
)->parents
; num_parents
< 3 && parent
;
1257 parent
= parent
->next
)
1260 if (num_parents
<= 2) {
1265 /* Since num_parents > 2, this initializer is safe. */
1266 for (parent
= (*list
)->parents
->next
; parent
; parent
= parent
->next
) {
1267 int edge_value
= oid_pos(&parent
->item
->object
.oid
,
1272 if (edge_value
>= 0)
1273 edge_value
+= ctx
->new_num_commits_in_base
;
1274 else if (ctx
->new_base_graph
) {
1276 if (find_commit_pos_in_graph(parent
->item
,
1277 ctx
->new_base_graph
,
1283 BUG("missing parent %s for commit %s",
1284 oid_to_hex(&parent
->item
->object
.oid
),
1285 oid_to_hex(&(*list
)->object
.oid
));
1286 else if (!parent
->next
)
1287 edge_value
|= GRAPH_LAST_EDGE
;
1289 hashwrite_be32(f
, edge_value
);
1298 static int write_graph_chunk_bloom_indexes(struct hashfile
*f
,
1301 struct write_commit_graph_context
*ctx
= data
;
1302 struct commit
**list
= ctx
->commits
.list
;
1303 struct commit
**last
= ctx
->commits
.list
+ ctx
->commits
.nr
;
1304 uint32_t cur_pos
= 0;
1306 while (list
< last
) {
1307 struct bloom_filter
*filter
= get_bloom_filter(ctx
->r
, *list
);
1308 size_t len
= filter
? filter
->len
: 0;
1310 display_progress(ctx
->progress
, ++ctx
->progress_cnt
);
1311 hashwrite_be32(f
, cur_pos
);
1318 static void trace2_bloom_filter_settings(struct write_commit_graph_context
*ctx
)
1320 struct json_writer jw
= JSON_WRITER_INIT
;
1322 jw_object_begin(&jw
, 0);
1323 jw_object_intmax(&jw
, "hash_version", ctx
->bloom_settings
->hash_version
);
1324 jw_object_intmax(&jw
, "num_hashes", ctx
->bloom_settings
->num_hashes
);
1325 jw_object_intmax(&jw
, "bits_per_entry", ctx
->bloom_settings
->bits_per_entry
);
1326 jw_object_intmax(&jw
, "max_changed_paths", ctx
->bloom_settings
->max_changed_paths
);
1329 trace2_data_json("bloom", ctx
->r
, "settings", &jw
);
1334 static int write_graph_chunk_bloom_data(struct hashfile
*f
,
1337 struct write_commit_graph_context
*ctx
= data
;
1338 struct commit
**list
= ctx
->commits
.list
;
1339 struct commit
**last
= ctx
->commits
.list
+ ctx
->commits
.nr
;
1341 trace2_bloom_filter_settings(ctx
);
1343 hashwrite_be32(f
, ctx
->bloom_settings
->hash_version
);
1344 hashwrite_be32(f
, ctx
->bloom_settings
->num_hashes
);
1345 hashwrite_be32(f
, ctx
->bloom_settings
->bits_per_entry
);
1347 while (list
< last
) {
1348 struct bloom_filter
*filter
= get_bloom_filter(ctx
->r
, *list
);
1349 size_t len
= filter
? filter
->len
: 0;
1351 display_progress(ctx
->progress
, ++ctx
->progress_cnt
);
1353 hashwrite(f
, filter
->data
, len
* sizeof(unsigned char));
1360 static int add_packed_commits(const struct object_id
*oid
,
1361 struct packed_git
*pack
,
1365 struct write_commit_graph_context
*ctx
= (struct write_commit_graph_context
*)data
;
1366 enum object_type type
;
1367 off_t offset
= nth_packed_object_offset(pack
, pos
);
1368 struct object_info oi
= OBJECT_INFO_INIT
;
1371 display_progress(ctx
->progress
, ++ctx
->progress_done
);
1374 if (packed_object_info(ctx
->r
, pack
, offset
, &oi
) < 0)
1375 die(_("unable to get type of object %s"), oid_to_hex(oid
));
1377 if (type
!= OBJ_COMMIT
)
1380 oid_array_append(&ctx
->oids
, oid
);
1381 set_commit_pos(ctx
->r
, oid
);
1386 static void add_missing_parents(struct write_commit_graph_context
*ctx
, struct commit
*commit
)
1388 struct commit_list
*parent
;
1389 for (parent
= commit
->parents
; parent
; parent
= parent
->next
) {
1390 if (!(parent
->item
->object
.flags
& REACHABLE
)) {
1391 oid_array_append(&ctx
->oids
, &parent
->item
->object
.oid
);
1392 parent
->item
->object
.flags
|= REACHABLE
;
1397 static void close_reachable(struct write_commit_graph_context
*ctx
)
1400 struct commit
*commit
;
1401 enum commit_graph_split_flags flags
= ctx
->opts
?
1402 ctx
->opts
->split_flags
: COMMIT_GRAPH_SPLIT_UNSPECIFIED
;
1404 if (ctx
->report_progress
)
1405 ctx
->progress
= start_delayed_progress(
1406 _("Loading known commits in commit graph"),
1408 for (i
= 0; i
< ctx
->oids
.nr
; i
++) {
1409 display_progress(ctx
->progress
, i
+ 1);
1410 commit
= lookup_commit(ctx
->r
, &ctx
->oids
.oid
[i
]);
1412 commit
->object
.flags
|= REACHABLE
;
1414 stop_progress(&ctx
->progress
);
1417 * As this loop runs, ctx->oids.nr may grow, but not more
1418 * than the number of missing commits in the reachable
1421 if (ctx
->report_progress
)
1422 ctx
->progress
= start_delayed_progress(
1423 _("Expanding reachable commits in commit graph"),
1425 for (i
= 0; i
< ctx
->oids
.nr
; i
++) {
1426 display_progress(ctx
->progress
, i
+ 1);
1427 commit
= lookup_commit(ctx
->r
, &ctx
->oids
.oid
[i
]);
1432 if ((!repo_parse_commit(ctx
->r
, commit
) &&
1433 commit_graph_position(commit
) == COMMIT_NOT_FROM_GRAPH
) ||
1434 flags
== COMMIT_GRAPH_SPLIT_REPLACE
)
1435 add_missing_parents(ctx
, commit
);
1436 } else if (!repo_parse_commit_no_graph(ctx
->r
, commit
))
1437 add_missing_parents(ctx
, commit
);
1439 stop_progress(&ctx
->progress
);
1441 if (ctx
->report_progress
)
1442 ctx
->progress
= start_delayed_progress(
1443 _("Clearing commit marks in commit graph"),
1445 for (i
= 0; i
< ctx
->oids
.nr
; i
++) {
1446 display_progress(ctx
->progress
, i
+ 1);
1447 commit
= lookup_commit(ctx
->r
, &ctx
->oids
.oid
[i
]);
1450 commit
->object
.flags
&= ~REACHABLE
;
1452 stop_progress(&ctx
->progress
);
1455 static void compute_topological_levels(struct write_commit_graph_context
*ctx
)
1458 struct commit_list
*list
= NULL
;
1460 if (ctx
->report_progress
)
1461 ctx
->progress
= start_delayed_progress(
1462 _("Computing commit graph topological levels"),
1464 for (i
= 0; i
< ctx
->commits
.nr
; i
++) {
1465 struct commit
*c
= ctx
->commits
.list
[i
];
1468 repo_parse_commit(ctx
->r
, c
);
1469 level
= *topo_level_slab_at(ctx
->topo_levels
, c
);
1471 display_progress(ctx
->progress
, i
+ 1);
1472 if (level
!= GENERATION_NUMBER_ZERO
)
1475 commit_list_insert(c
, &list
);
1477 struct commit
*current
= list
->item
;
1478 struct commit_list
*parent
;
1479 int all_parents_computed
= 1;
1480 uint32_t max_level
= 0;
1482 for (parent
= current
->parents
; parent
; parent
= parent
->next
) {
1483 repo_parse_commit(ctx
->r
, parent
->item
);
1484 level
= *topo_level_slab_at(ctx
->topo_levels
, parent
->item
);
1486 if (level
== GENERATION_NUMBER_ZERO
) {
1487 all_parents_computed
= 0;
1488 commit_list_insert(parent
->item
, &list
);
1492 if (level
> max_level
)
1496 if (all_parents_computed
) {
1499 if (max_level
> GENERATION_NUMBER_V1_MAX
- 1)
1500 max_level
= GENERATION_NUMBER_V1_MAX
- 1;
1501 *topo_level_slab_at(ctx
->topo_levels
, current
) = max_level
+ 1;
1505 stop_progress(&ctx
->progress
);
1508 static void compute_generation_numbers(struct write_commit_graph_context
*ctx
)
1511 struct commit_list
*list
= NULL
;
1513 if (ctx
->report_progress
)
1514 ctx
->progress
= start_delayed_progress(
1515 _("Computing commit graph generation numbers"),
1518 if (!ctx
->trust_generation_numbers
) {
1519 for (i
= 0; i
< ctx
->commits
.nr
; i
++) {
1520 struct commit
*c
= ctx
->commits
.list
[i
];
1521 repo_parse_commit(ctx
->r
, c
);
1522 commit_graph_data_at(c
)->generation
= GENERATION_NUMBER_ZERO
;
1526 for (i
= 0; i
< ctx
->commits
.nr
; i
++) {
1527 struct commit
*c
= ctx
->commits
.list
[i
];
1528 timestamp_t corrected_commit_date
;
1530 repo_parse_commit(ctx
->r
, c
);
1531 corrected_commit_date
= commit_graph_data_at(c
)->generation
;
1533 display_progress(ctx
->progress
, i
+ 1);
1534 if (corrected_commit_date
!= GENERATION_NUMBER_ZERO
)
1537 commit_list_insert(c
, &list
);
1539 struct commit
*current
= list
->item
;
1540 struct commit_list
*parent
;
1541 int all_parents_computed
= 1;
1542 timestamp_t max_corrected_commit_date
= 0;
1544 for (parent
= current
->parents
; parent
; parent
= parent
->next
) {
1545 repo_parse_commit(ctx
->r
, parent
->item
);
1546 corrected_commit_date
= commit_graph_data_at(parent
->item
)->generation
;
1548 if (corrected_commit_date
== GENERATION_NUMBER_ZERO
) {
1549 all_parents_computed
= 0;
1550 commit_list_insert(parent
->item
, &list
);
1554 if (corrected_commit_date
> max_corrected_commit_date
)
1555 max_corrected_commit_date
= corrected_commit_date
;
1558 if (all_parents_computed
) {
1561 if (current
->date
&& current
->date
> max_corrected_commit_date
)
1562 max_corrected_commit_date
= current
->date
- 1;
1563 commit_graph_data_at(current
)->generation
= max_corrected_commit_date
+ 1;
1568 for (i
= 0; i
< ctx
->commits
.nr
; i
++) {
1569 struct commit
*c
= ctx
->commits
.list
[i
];
1570 timestamp_t offset
= commit_graph_data_at(c
)->generation
- c
->date
;
1571 if (offset
> GENERATION_NUMBER_V2_OFFSET_MAX
)
1572 ctx
->num_generation_data_overflows
++;
1574 stop_progress(&ctx
->progress
);
1577 static void trace2_bloom_filter_write_statistics(struct write_commit_graph_context
*ctx
)
1579 trace2_data_intmax("commit-graph", ctx
->r
, "filter-computed",
1580 ctx
->count_bloom_filter_computed
);
1581 trace2_data_intmax("commit-graph", ctx
->r
, "filter-not-computed",
1582 ctx
->count_bloom_filter_not_computed
);
1583 trace2_data_intmax("commit-graph", ctx
->r
, "filter-trunc-empty",
1584 ctx
->count_bloom_filter_trunc_empty
);
1585 trace2_data_intmax("commit-graph", ctx
->r
, "filter-trunc-large",
1586 ctx
->count_bloom_filter_trunc_large
);
1589 static void compute_bloom_filters(struct write_commit_graph_context
*ctx
)
1592 struct progress
*progress
= NULL
;
1593 struct commit
**sorted_commits
;
1594 int max_new_filters
;
1596 init_bloom_filters();
1598 if (ctx
->report_progress
)
1599 progress
= start_delayed_progress(
1600 _("Computing commit changed paths Bloom filters"),
1603 DUP_ARRAY(sorted_commits
, ctx
->commits
.list
, ctx
->commits
.nr
);
1605 if (ctx
->order_by_pack
)
1606 QSORT(sorted_commits
, ctx
->commits
.nr
, commit_pos_cmp
);
1608 QSORT(sorted_commits
, ctx
->commits
.nr
, commit_gen_cmp
);
1610 max_new_filters
= ctx
->opts
&& ctx
->opts
->max_new_filters
>= 0 ?
1611 ctx
->opts
->max_new_filters
: ctx
->commits
.nr
;
1613 for (i
= 0; i
< ctx
->commits
.nr
; i
++) {
1614 enum bloom_filter_computed computed
= 0;
1615 struct commit
*c
= sorted_commits
[i
];
1616 struct bloom_filter
*filter
= get_or_compute_bloom_filter(
1619 ctx
->count_bloom_filter_computed
< max_new_filters
,
1620 ctx
->bloom_settings
,
1622 if (computed
& BLOOM_COMPUTED
) {
1623 ctx
->count_bloom_filter_computed
++;
1624 if (computed
& BLOOM_TRUNC_EMPTY
)
1625 ctx
->count_bloom_filter_trunc_empty
++;
1626 if (computed
& BLOOM_TRUNC_LARGE
)
1627 ctx
->count_bloom_filter_trunc_large
++;
1628 } else if (computed
& BLOOM_NOT_COMPUTED
)
1629 ctx
->count_bloom_filter_not_computed
++;
1630 ctx
->total_bloom_filter_data_size
+= filter
1631 ? sizeof(unsigned char) * filter
->len
: 0;
1632 display_progress(progress
, i
+ 1);
1635 if (trace2_is_enabled())
1636 trace2_bloom_filter_write_statistics(ctx
);
1638 free(sorted_commits
);
1639 stop_progress(&progress
);
1642 struct refs_cb_data
{
1643 struct oidset
*commits
;
1644 struct progress
*progress
;
1647 static int add_ref_to_set(const char *refname UNUSED
,
1648 const struct object_id
*oid
,
1649 int flags UNUSED
, void *cb_data
)
1651 struct object_id peeled
;
1652 struct refs_cb_data
*data
= (struct refs_cb_data
*)cb_data
;
1654 if (!peel_iterated_oid(oid
, &peeled
))
1656 if (oid_object_info(the_repository
, oid
, NULL
) == OBJ_COMMIT
)
1657 oidset_insert(data
->commits
, oid
);
1659 display_progress(data
->progress
, oidset_size(data
->commits
));
1664 int write_commit_graph_reachable(struct object_directory
*odb
,
1665 enum commit_graph_write_flags flags
,
1666 const struct commit_graph_opts
*opts
)
1668 struct oidset commits
= OIDSET_INIT
;
1669 struct refs_cb_data data
;
1672 memset(&data
, 0, sizeof(data
));
1673 data
.commits
= &commits
;
1674 if (flags
& COMMIT_GRAPH_WRITE_PROGRESS
)
1675 data
.progress
= start_delayed_progress(
1676 _("Collecting referenced commits"), 0);
1678 for_each_ref(add_ref_to_set
, &data
);
1680 stop_progress(&data
.progress
);
1682 result
= write_commit_graph(odb
, NULL
, &commits
,
1685 oidset_clear(&commits
);
1689 static int fill_oids_from_packs(struct write_commit_graph_context
*ctx
,
1690 const struct string_list
*pack_indexes
)
1693 struct strbuf progress_title
= STRBUF_INIT
;
1694 struct strbuf packname
= STRBUF_INIT
;
1698 strbuf_addf(&packname
, "%s/pack/", ctx
->odb
->path
);
1699 dirlen
= packname
.len
;
1700 if (ctx
->report_progress
) {
1701 strbuf_addf(&progress_title
,
1702 Q_("Finding commits for commit graph in %"PRIuMAX
" pack",
1703 "Finding commits for commit graph in %"PRIuMAX
" packs",
1705 (uintmax_t)pack_indexes
->nr
);
1706 ctx
->progress
= start_delayed_progress(progress_title
.buf
, 0);
1707 ctx
->progress_done
= 0;
1709 for (i
= 0; i
< pack_indexes
->nr
; i
++) {
1710 struct packed_git
*p
;
1711 strbuf_setlen(&packname
, dirlen
);
1712 strbuf_addstr(&packname
, pack_indexes
->items
[i
].string
);
1713 p
= add_packed_git(packname
.buf
, packname
.len
, 1);
1715 ret
= error(_("error adding pack %s"), packname
.buf
);
1718 if (open_pack_index(p
)) {
1719 ret
= error(_("error opening index for %s"), packname
.buf
);
1722 for_each_object_in_pack(p
, add_packed_commits
, ctx
,
1723 FOR_EACH_OBJECT_PACK_ORDER
);
1729 stop_progress(&ctx
->progress
);
1730 strbuf_release(&progress_title
);
1731 strbuf_release(&packname
);
1736 static int fill_oids_from_commits(struct write_commit_graph_context
*ctx
,
1737 struct oidset
*commits
)
1739 struct oidset_iter iter
;
1740 struct object_id
*oid
;
1742 if (!oidset_size(commits
))
1745 oidset_iter_init(commits
, &iter
);
1746 while ((oid
= oidset_iter_next(&iter
))) {
1747 oid_array_append(&ctx
->oids
, oid
);
1753 static void fill_oids_from_all_packs(struct write_commit_graph_context
*ctx
)
1755 if (ctx
->report_progress
)
1756 ctx
->progress
= start_delayed_progress(
1757 _("Finding commits for commit graph among packed objects"),
1758 ctx
->approx_nr_objects
);
1759 for_each_packed_object(add_packed_commits
, ctx
,
1760 FOR_EACH_OBJECT_PACK_ORDER
);
1761 if (ctx
->progress_done
< ctx
->approx_nr_objects
)
1762 display_progress(ctx
->progress
, ctx
->approx_nr_objects
);
1763 stop_progress(&ctx
->progress
);
1766 static void copy_oids_to_commits(struct write_commit_graph_context
*ctx
)
1769 enum commit_graph_split_flags flags
= ctx
->opts
?
1770 ctx
->opts
->split_flags
: COMMIT_GRAPH_SPLIT_UNSPECIFIED
;
1772 ctx
->num_extra_edges
= 0;
1773 if (ctx
->report_progress
)
1774 ctx
->progress
= start_delayed_progress(
1775 _("Finding extra edges in commit graph"),
1777 oid_array_sort(&ctx
->oids
);
1778 for (i
= 0; i
< ctx
->oids
.nr
; i
= oid_array_next_unique(&ctx
->oids
, i
)) {
1779 unsigned int num_parents
;
1781 display_progress(ctx
->progress
, i
+ 1);
1783 ALLOC_GROW(ctx
->commits
.list
, ctx
->commits
.nr
+ 1, ctx
->commits
.alloc
);
1784 ctx
->commits
.list
[ctx
->commits
.nr
] = lookup_commit(ctx
->r
, &ctx
->oids
.oid
[i
]);
1786 if (ctx
->split
&& flags
!= COMMIT_GRAPH_SPLIT_REPLACE
&&
1787 commit_graph_position(ctx
->commits
.list
[ctx
->commits
.nr
]) != COMMIT_NOT_FROM_GRAPH
)
1790 if (ctx
->split
&& flags
== COMMIT_GRAPH_SPLIT_REPLACE
)
1791 repo_parse_commit(ctx
->r
, ctx
->commits
.list
[ctx
->commits
.nr
]);
1793 repo_parse_commit_no_graph(ctx
->r
, ctx
->commits
.list
[ctx
->commits
.nr
]);
1795 num_parents
= commit_list_count(ctx
->commits
.list
[ctx
->commits
.nr
]->parents
);
1796 if (num_parents
> 2)
1797 ctx
->num_extra_edges
+= num_parents
- 1;
1801 stop_progress(&ctx
->progress
);
1804 static int write_graph_chunk_base_1(struct hashfile
*f
,
1805 struct commit_graph
*g
)
1812 num
= write_graph_chunk_base_1(f
, g
->base_graph
);
1813 hashwrite(f
, g
->oid
.hash
, the_hash_algo
->rawsz
);
1817 static int write_graph_chunk_base(struct hashfile
*f
,
1820 struct write_commit_graph_context
*ctx
= data
;
1821 int num
= write_graph_chunk_base_1(f
, ctx
->new_base_graph
);
1823 if (num
!= ctx
->num_commit_graphs_after
- 1) {
1824 error(_("failed to write correct number of base graph ids"));
1831 static int write_commit_graph_file(struct write_commit_graph_context
*ctx
)
1836 struct lock_file lk
= LOCK_INIT
;
1837 const unsigned hashsz
= the_hash_algo
->rawsz
;
1838 struct strbuf progress_title
= STRBUF_INIT
;
1839 struct chunkfile
*cf
;
1840 unsigned char file_hash
[GIT_MAX_RAWSZ
];
1843 struct strbuf tmp_file
= STRBUF_INIT
;
1845 strbuf_addf(&tmp_file
,
1846 "%s/info/commit-graphs/tmp_graph_XXXXXX",
1848 ctx
->graph_name
= strbuf_detach(&tmp_file
, NULL
);
1850 ctx
->graph_name
= get_commit_graph_filename(ctx
->odb
);
1853 if (safe_create_leading_directories(ctx
->graph_name
)) {
1854 UNLEAK(ctx
->graph_name
);
1855 error(_("unable to create leading directories of %s"),
1861 char *lock_name
= get_commit_graph_chain_filename(ctx
->odb
);
1863 hold_lock_file_for_update_mode(&lk
, lock_name
,
1864 LOCK_DIE_ON_ERROR
, 0444);
1867 fd
= git_mkstemp_mode(ctx
->graph_name
, 0444);
1869 error(_("unable to create temporary graph layer"));
1873 if (adjust_shared_perm(ctx
->graph_name
)) {
1874 error(_("unable to adjust shared permissions for '%s'"),
1879 f
= hashfd(fd
, ctx
->graph_name
);
1881 hold_lock_file_for_update_mode(&lk
, ctx
->graph_name
,
1882 LOCK_DIE_ON_ERROR
, 0444);
1883 fd
= get_lock_file_fd(&lk
);
1884 f
= hashfd(fd
, get_lock_file_path(&lk
));
1887 cf
= init_chunkfile(f
);
1889 add_chunk(cf
, GRAPH_CHUNKID_OIDFANOUT
, GRAPH_FANOUT_SIZE
,
1890 write_graph_chunk_fanout
);
1891 add_chunk(cf
, GRAPH_CHUNKID_OIDLOOKUP
, hashsz
* ctx
->commits
.nr
,
1892 write_graph_chunk_oids
);
1893 add_chunk(cf
, GRAPH_CHUNKID_DATA
, (hashsz
+ 16) * ctx
->commits
.nr
,
1894 write_graph_chunk_data
);
1896 if (ctx
->write_generation_data
)
1897 add_chunk(cf
, GRAPH_CHUNKID_GENERATION_DATA
,
1898 sizeof(uint32_t) * ctx
->commits
.nr
,
1899 write_graph_chunk_generation_data
);
1900 if (ctx
->num_generation_data_overflows
)
1901 add_chunk(cf
, GRAPH_CHUNKID_GENERATION_DATA_OVERFLOW
,
1902 sizeof(timestamp_t
) * ctx
->num_generation_data_overflows
,
1903 write_graph_chunk_generation_data_overflow
);
1904 if (ctx
->num_extra_edges
)
1905 add_chunk(cf
, GRAPH_CHUNKID_EXTRAEDGES
,
1906 4 * ctx
->num_extra_edges
,
1907 write_graph_chunk_extra_edges
);
1908 if (ctx
->changed_paths
) {
1909 add_chunk(cf
, GRAPH_CHUNKID_BLOOMINDEXES
,
1910 sizeof(uint32_t) * ctx
->commits
.nr
,
1911 write_graph_chunk_bloom_indexes
);
1912 add_chunk(cf
, GRAPH_CHUNKID_BLOOMDATA
,
1913 sizeof(uint32_t) * 3
1914 + ctx
->total_bloom_filter_data_size
,
1915 write_graph_chunk_bloom_data
);
1917 if (ctx
->num_commit_graphs_after
> 1)
1918 add_chunk(cf
, GRAPH_CHUNKID_BASE
,
1919 hashsz
* (ctx
->num_commit_graphs_after
- 1),
1920 write_graph_chunk_base
);
1922 hashwrite_be32(f
, GRAPH_SIGNATURE
);
1924 hashwrite_u8(f
, GRAPH_VERSION
);
1925 hashwrite_u8(f
, oid_version(the_hash_algo
));
1926 hashwrite_u8(f
, get_num_chunks(cf
));
1927 hashwrite_u8(f
, ctx
->num_commit_graphs_after
- 1);
1929 if (ctx
->report_progress
) {
1930 strbuf_addf(&progress_title
,
1931 Q_("Writing out commit graph in %d pass",
1932 "Writing out commit graph in %d passes",
1933 get_num_chunks(cf
)),
1934 get_num_chunks(cf
));
1935 ctx
->progress
= start_delayed_progress(
1937 get_num_chunks(cf
) * ctx
->commits
.nr
);
1940 write_chunkfile(cf
, ctx
);
1942 stop_progress(&ctx
->progress
);
1943 strbuf_release(&progress_title
);
1945 if (ctx
->split
&& ctx
->base_graph_name
&& ctx
->num_commit_graphs_after
> 1) {
1946 char *new_base_hash
= xstrdup(oid_to_hex(&ctx
->new_base_graph
->oid
));
1947 char *new_base_name
= get_split_graph_filename(ctx
->new_base_graph
->odb
, new_base_hash
);
1949 free(ctx
->commit_graph_filenames_after
[ctx
->num_commit_graphs_after
- 2]);
1950 free(ctx
->commit_graph_hash_after
[ctx
->num_commit_graphs_after
- 2]);
1951 ctx
->commit_graph_filenames_after
[ctx
->num_commit_graphs_after
- 2] = new_base_name
;
1952 ctx
->commit_graph_hash_after
[ctx
->num_commit_graphs_after
- 2] = new_base_hash
;
1955 close_commit_graph(ctx
->r
->objects
);
1956 finalize_hashfile(f
, file_hash
, FSYNC_COMPONENT_COMMIT_GRAPH
,
1957 CSUM_HASH_IN_STREAM
| CSUM_FSYNC
);
1961 FILE *chainf
= fdopen_lock_file(&lk
, "w");
1962 char *final_graph_name
;
1968 error(_("unable to open commit-graph chain file"));
1972 if (ctx
->base_graph_name
) {
1974 int idx
= ctx
->num_commit_graphs_after
- 1;
1975 if (ctx
->num_commit_graphs_after
> 1)
1978 dest
= ctx
->commit_graph_filenames_after
[idx
];
1980 if (strcmp(ctx
->base_graph_name
, dest
)) {
1981 result
= rename(ctx
->base_graph_name
, dest
);
1984 error(_("failed to rename base commit-graph file"));
1989 char *graph_name
= get_commit_graph_filename(ctx
->odb
);
1994 ctx
->commit_graph_hash_after
[ctx
->num_commit_graphs_after
- 1] = xstrdup(hash_to_hex(file_hash
));
1995 final_graph_name
= get_split_graph_filename(ctx
->odb
,
1996 ctx
->commit_graph_hash_after
[ctx
->num_commit_graphs_after
- 1]);
1997 ctx
->commit_graph_filenames_after
[ctx
->num_commit_graphs_after
- 1] = final_graph_name
;
1999 result
= rename(ctx
->graph_name
, final_graph_name
);
2001 for (i
= 0; i
< ctx
->num_commit_graphs_after
; i
++)
2002 fprintf(get_lock_file_fp(&lk
), "%s\n", ctx
->commit_graph_hash_after
[i
]);
2005 error(_("failed to rename temporary commit-graph file"));
2010 commit_lock_file(&lk
);
2015 static void split_graph_merge_strategy(struct write_commit_graph_context
*ctx
)
2017 struct commit_graph
*g
;
2018 uint32_t num_commits
;
2019 enum commit_graph_split_flags flags
= COMMIT_GRAPH_SPLIT_UNSPECIFIED
;
2022 int max_commits
= 0;
2026 max_commits
= ctx
->opts
->max_commits
;
2028 if (ctx
->opts
->size_multiple
)
2029 size_mult
= ctx
->opts
->size_multiple
;
2031 flags
= ctx
->opts
->split_flags
;
2034 g
= ctx
->r
->objects
->commit_graph
;
2035 num_commits
= ctx
->commits
.nr
;
2036 if (flags
== COMMIT_GRAPH_SPLIT_REPLACE
)
2037 ctx
->num_commit_graphs_after
= 1;
2039 ctx
->num_commit_graphs_after
= ctx
->num_commit_graphs_before
+ 1;
2041 if (flags
!= COMMIT_GRAPH_SPLIT_MERGE_PROHIBITED
&&
2042 flags
!= COMMIT_GRAPH_SPLIT_REPLACE
) {
2043 while (g
&& (g
->num_commits
<= size_mult
* num_commits
||
2044 (max_commits
&& num_commits
> max_commits
))) {
2045 if (g
->odb
!= ctx
->odb
)
2048 num_commits
+= g
->num_commits
;
2051 ctx
->num_commit_graphs_after
--;
2055 if (flags
!= COMMIT_GRAPH_SPLIT_REPLACE
)
2056 ctx
->new_base_graph
= g
;
2057 else if (ctx
->num_commit_graphs_after
!= 1)
2058 BUG("split_graph_merge_strategy: num_commit_graphs_after "
2059 "should be 1 with --split=replace");
2061 if (ctx
->num_commit_graphs_after
== 2) {
2062 char *old_graph_name
= get_commit_graph_filename(g
->odb
);
2064 if (!strcmp(g
->filename
, old_graph_name
) &&
2065 g
->odb
!= ctx
->odb
) {
2066 ctx
->num_commit_graphs_after
= 1;
2067 ctx
->new_base_graph
= NULL
;
2070 free(old_graph_name
);
2073 CALLOC_ARRAY(ctx
->commit_graph_filenames_after
, ctx
->num_commit_graphs_after
);
2074 CALLOC_ARRAY(ctx
->commit_graph_hash_after
, ctx
->num_commit_graphs_after
);
2076 for (i
= 0; i
< ctx
->num_commit_graphs_after
&&
2077 i
< ctx
->num_commit_graphs_before
; i
++)
2078 ctx
->commit_graph_filenames_after
[i
] = xstrdup(ctx
->commit_graph_filenames_before
[i
]);
2080 i
= ctx
->num_commit_graphs_before
- 1;
2081 g
= ctx
->r
->objects
->commit_graph
;
2084 if (i
< ctx
->num_commit_graphs_after
)
2085 ctx
->commit_graph_hash_after
[i
] = xstrdup(oid_to_hex(&g
->oid
));
2088 * If the topmost remaining layer has generation data chunk, the
2089 * resultant layer also has generation data chunk.
2091 if (i
== ctx
->num_commit_graphs_after
- 2)
2092 ctx
->write_generation_data
= !!g
->chunk_generation_data
;
2099 static void merge_commit_graph(struct write_commit_graph_context
*ctx
,
2100 struct commit_graph
*g
)
2103 uint32_t offset
= g
->num_commits_in_base
;
2105 ALLOC_GROW(ctx
->commits
.list
, ctx
->commits
.nr
+ g
->num_commits
, ctx
->commits
.alloc
);
2107 for (i
= 0; i
< g
->num_commits
; i
++) {
2108 struct object_id oid
;
2109 struct commit
*result
;
2111 display_progress(ctx
->progress
, i
+ 1);
2113 load_oid_from_graph(g
, i
+ offset
, &oid
);
2115 /* only add commits if they still exist in the repo */
2116 result
= lookup_commit_reference_gently(ctx
->r
, &oid
, 1);
2119 ctx
->commits
.list
[ctx
->commits
.nr
] = result
;
2125 static int commit_compare(const void *_a
, const void *_b
)
2127 const struct commit
*a
= *(const struct commit
**)_a
;
2128 const struct commit
*b
= *(const struct commit
**)_b
;
2129 return oidcmp(&a
->object
.oid
, &b
->object
.oid
);
2132 static void sort_and_scan_merged_commits(struct write_commit_graph_context
*ctx
)
2134 uint32_t i
, dedup_i
= 0;
2136 if (ctx
->report_progress
)
2137 ctx
->progress
= start_delayed_progress(
2138 _("Scanning merged commits"),
2141 QSORT(ctx
->commits
.list
, ctx
->commits
.nr
, commit_compare
);
2143 ctx
->num_extra_edges
= 0;
2144 for (i
= 0; i
< ctx
->commits
.nr
; i
++) {
2145 display_progress(ctx
->progress
, i
+ 1);
2147 if (i
&& oideq(&ctx
->commits
.list
[i
- 1]->object
.oid
,
2148 &ctx
->commits
.list
[i
]->object
.oid
)) {
2150 * Silently ignore duplicates. These were likely
2151 * created due to a commit appearing in multiple
2152 * layers of the chain, which is unexpected but
2153 * not invalid. We should make sure there is a
2154 * unique copy in the new layer.
2157 unsigned int num_parents
;
2159 ctx
->commits
.list
[dedup_i
] = ctx
->commits
.list
[i
];
2162 num_parents
= commit_list_count(ctx
->commits
.list
[i
]->parents
);
2163 if (num_parents
> 2)
2164 ctx
->num_extra_edges
+= num_parents
- 1;
2168 ctx
->commits
.nr
= dedup_i
;
2170 stop_progress(&ctx
->progress
);
2173 static void merge_commit_graphs(struct write_commit_graph_context
*ctx
)
2175 struct commit_graph
*g
= ctx
->r
->objects
->commit_graph
;
2176 uint32_t current_graph_number
= ctx
->num_commit_graphs_before
;
2178 while (g
&& current_graph_number
>= ctx
->num_commit_graphs_after
) {
2179 current_graph_number
--;
2181 if (ctx
->report_progress
)
2182 ctx
->progress
= start_delayed_progress(_("Merging commit-graph"), 0);
2184 merge_commit_graph(ctx
, g
);
2185 stop_progress(&ctx
->progress
);
2191 ctx
->new_base_graph
= g
;
2192 ctx
->new_num_commits_in_base
= g
->num_commits
+ g
->num_commits_in_base
;
2195 if (ctx
->new_base_graph
)
2196 ctx
->base_graph_name
= xstrdup(ctx
->new_base_graph
->filename
);
2198 sort_and_scan_merged_commits(ctx
);
2201 static void mark_commit_graphs(struct write_commit_graph_context
*ctx
)
2204 time_t now
= time(NULL
);
2206 for (i
= ctx
->num_commit_graphs_after
- 1; i
< ctx
->num_commit_graphs_before
; i
++) {
2208 struct utimbuf updated_time
;
2210 if (stat(ctx
->commit_graph_filenames_before
[i
], &st
) < 0)
2213 updated_time
.actime
= st
.st_atime
;
2214 updated_time
.modtime
= now
;
2215 utime(ctx
->commit_graph_filenames_before
[i
], &updated_time
);
2219 static void expire_commit_graphs(struct write_commit_graph_context
*ctx
)
2221 struct strbuf path
= STRBUF_INIT
;
2225 timestamp_t expire_time
= time(NULL
);
2227 if (ctx
->opts
&& ctx
->opts
->expire_time
)
2228 expire_time
= ctx
->opts
->expire_time
;
2230 char *chain_file_name
= get_commit_graph_chain_filename(ctx
->odb
);
2231 unlink(chain_file_name
);
2232 free(chain_file_name
);
2233 ctx
->num_commit_graphs_after
= 0;
2236 strbuf_addstr(&path
, ctx
->odb
->path
);
2237 strbuf_addstr(&path
, "/info/commit-graphs");
2238 dir
= opendir(path
.buf
);
2243 strbuf_addch(&path
, '/');
2244 dirnamelen
= path
.len
;
2245 while ((de
= readdir(dir
)) != NULL
) {
2247 uint32_t i
, found
= 0;
2249 strbuf_setlen(&path
, dirnamelen
);
2250 strbuf_addstr(&path
, de
->d_name
);
2252 if (stat(path
.buf
, &st
) < 0)
2255 if (st
.st_mtime
> expire_time
)
2257 if (path
.len
< 6 || strcmp(path
.buf
+ path
.len
- 6, ".graph"))
2260 for (i
= 0; i
< ctx
->num_commit_graphs_after
; i
++) {
2261 if (!strcmp(ctx
->commit_graph_filenames_after
[i
],
2275 strbuf_release(&path
);
2278 int write_commit_graph(struct object_directory
*odb
,
2279 const struct string_list
*const pack_indexes
,
2280 struct oidset
*commits
,
2281 enum commit_graph_write_flags flags
,
2282 const struct commit_graph_opts
*opts
)
2284 struct repository
*r
= the_repository
;
2285 struct write_commit_graph_context
*ctx
;
2289 struct bloom_filter_settings bloom_settings
= DEFAULT_BLOOM_FILTER_SETTINGS
;
2290 struct topo_level_slab topo_levels
;
2292 prepare_repo_settings(r
);
2293 if (!r
->settings
.core_commit_graph
) {
2294 warning(_("attempting to write a commit-graph, but 'core.commitGraph' is disabled"));
2297 if (!commit_graph_compatible(r
))
2300 CALLOC_ARRAY(ctx
, 1);
2303 ctx
->append
= flags
& COMMIT_GRAPH_WRITE_APPEND
? 1 : 0;
2304 ctx
->report_progress
= flags
& COMMIT_GRAPH_WRITE_PROGRESS
? 1 : 0;
2305 ctx
->split
= flags
& COMMIT_GRAPH_WRITE_SPLIT
? 1 : 0;
2307 ctx
->total_bloom_filter_data_size
= 0;
2308 ctx
->write_generation_data
= (get_configured_generation_version(r
) == 2);
2309 ctx
->num_generation_data_overflows
= 0;
2311 bloom_settings
.bits_per_entry
= git_env_ulong("GIT_TEST_BLOOM_SETTINGS_BITS_PER_ENTRY",
2312 bloom_settings
.bits_per_entry
);
2313 bloom_settings
.num_hashes
= git_env_ulong("GIT_TEST_BLOOM_SETTINGS_NUM_HASHES",
2314 bloom_settings
.num_hashes
);
2315 bloom_settings
.max_changed_paths
= git_env_ulong("GIT_TEST_BLOOM_SETTINGS_MAX_CHANGED_PATHS",
2316 bloom_settings
.max_changed_paths
);
2317 ctx
->bloom_settings
= &bloom_settings
;
2319 init_topo_level_slab(&topo_levels
);
2320 ctx
->topo_levels
= &topo_levels
;
2322 prepare_commit_graph(ctx
->r
);
2323 if (ctx
->r
->objects
->commit_graph
) {
2324 struct commit_graph
*g
= ctx
->r
->objects
->commit_graph
;
2327 g
->topo_levels
= &topo_levels
;
2332 if (flags
& COMMIT_GRAPH_WRITE_BLOOM_FILTERS
)
2333 ctx
->changed_paths
= 1;
2334 if (!(flags
& COMMIT_GRAPH_NO_WRITE_BLOOM_FILTERS
)) {
2335 struct commit_graph
*g
;
2337 g
= ctx
->r
->objects
->commit_graph
;
2339 /* We have changed-paths already. Keep them in the next graph */
2340 if (g
&& g
->chunk_bloom_data
) {
2341 ctx
->changed_paths
= 1;
2342 ctx
->bloom_settings
= g
->bloom_filter_settings
;
2347 struct commit_graph
*g
= ctx
->r
->objects
->commit_graph
;
2350 ctx
->num_commit_graphs_before
++;
2354 if (ctx
->num_commit_graphs_before
) {
2355 ALLOC_ARRAY(ctx
->commit_graph_filenames_before
, ctx
->num_commit_graphs_before
);
2356 i
= ctx
->num_commit_graphs_before
;
2357 g
= ctx
->r
->objects
->commit_graph
;
2360 ctx
->commit_graph_filenames_before
[--i
] = xstrdup(g
->filename
);
2366 replace
= ctx
->opts
->split_flags
& COMMIT_GRAPH_SPLIT_REPLACE
;
2369 ctx
->approx_nr_objects
= repo_approximate_object_count(the_repository
);
2371 if (ctx
->append
&& ctx
->r
->objects
->commit_graph
) {
2372 struct commit_graph
*g
= ctx
->r
->objects
->commit_graph
;
2373 for (i
= 0; i
< g
->num_commits
; i
++) {
2374 struct object_id oid
;
2375 oidread(&oid
, g
->chunk_oid_lookup
+ g
->hash_len
* i
);
2376 oid_array_append(&ctx
->oids
, &oid
);
2381 ctx
->order_by_pack
= 1;
2382 if ((res
= fill_oids_from_packs(ctx
, pack_indexes
)))
2387 if ((res
= fill_oids_from_commits(ctx
, commits
)))
2391 if (!pack_indexes
&& !commits
) {
2392 ctx
->order_by_pack
= 1;
2393 fill_oids_from_all_packs(ctx
);
2396 close_reachable(ctx
);
2398 copy_oids_to_commits(ctx
);
2400 if (ctx
->commits
.nr
>= GRAPH_EDGE_LAST_MASK
) {
2401 error(_("too many commits to write graph"));
2406 if (!ctx
->commits
.nr
&& !replace
)
2410 split_graph_merge_strategy(ctx
);
2413 merge_commit_graphs(ctx
);
2415 ctx
->num_commit_graphs_after
= 1;
2417 ctx
->trust_generation_numbers
= validate_mixed_generation_chain(ctx
->r
->objects
->commit_graph
);
2419 compute_topological_levels(ctx
);
2420 if (ctx
->write_generation_data
)
2421 compute_generation_numbers(ctx
);
2423 if (ctx
->changed_paths
)
2424 compute_bloom_filters(ctx
);
2426 res
= write_commit_graph_file(ctx
);
2429 mark_commit_graphs(ctx
);
2431 expire_commit_graphs(ctx
);
2434 free(ctx
->graph_name
);
2435 free(ctx
->commits
.list
);
2436 oid_array_clear(&ctx
->oids
);
2437 clear_topo_level_slab(&topo_levels
);
2439 if (ctx
->commit_graph_filenames_after
) {
2440 for (i
= 0; i
< ctx
->num_commit_graphs_after
; i
++) {
2441 free(ctx
->commit_graph_filenames_after
[i
]);
2442 free(ctx
->commit_graph_hash_after
[i
]);
2445 for (i
= 0; i
< ctx
->num_commit_graphs_before
; i
++)
2446 free(ctx
->commit_graph_filenames_before
[i
]);
2448 free(ctx
->commit_graph_filenames_after
);
2449 free(ctx
->commit_graph_filenames_before
);
2450 free(ctx
->commit_graph_hash_after
);
2458 #define VERIFY_COMMIT_GRAPH_ERROR_HASH 2
2459 static int verify_commit_graph_error
;
2461 __attribute__((format (printf
, 1, 2)))
2462 static void graph_report(const char *fmt
, ...)
2466 verify_commit_graph_error
= 1;
2468 vfprintf(stderr
, fmt
, ap
);
2469 fprintf(stderr
, "\n");
2473 #define GENERATION_ZERO_EXISTS 1
2474 #define GENERATION_NUMBER_EXISTS 2
2476 static int commit_graph_checksum_valid(struct commit_graph
*g
)
2478 return hashfile_checksum_valid(g
->data
, g
->data_len
);
2481 int verify_commit_graph(struct repository
*r
, struct commit_graph
*g
, int flags
)
2483 uint32_t i
, cur_fanout_pos
= 0;
2484 struct object_id prev_oid
, cur_oid
;
2485 int generation_zero
= 0;
2486 struct progress
*progress
= NULL
;
2487 int local_error
= 0;
2490 graph_report("no commit-graph file loaded");
2494 verify_commit_graph_error
= verify_commit_graph_lite(g
);
2495 if (verify_commit_graph_error
)
2496 return verify_commit_graph_error
;
2498 if (!commit_graph_checksum_valid(g
)) {
2499 graph_report(_("the commit-graph file has incorrect checksum and is likely corrupt"));
2500 verify_commit_graph_error
= VERIFY_COMMIT_GRAPH_ERROR_HASH
;
2503 for (i
= 0; i
< g
->num_commits
; i
++) {
2504 struct commit
*graph_commit
;
2506 oidread(&cur_oid
, g
->chunk_oid_lookup
+ g
->hash_len
* i
);
2508 if (i
&& oidcmp(&prev_oid
, &cur_oid
) >= 0)
2509 graph_report(_("commit-graph has incorrect OID order: %s then %s"),
2510 oid_to_hex(&prev_oid
),
2511 oid_to_hex(&cur_oid
));
2513 oidcpy(&prev_oid
, &cur_oid
);
2515 while (cur_oid
.hash
[0] > cur_fanout_pos
) {
2516 uint32_t fanout_value
= get_be32(g
->chunk_oid_fanout
+ cur_fanout_pos
);
2518 if (i
!= fanout_value
)
2519 graph_report(_("commit-graph has incorrect fanout value: fanout[%d] = %u != %u"),
2520 cur_fanout_pos
, fanout_value
, i
);
2524 graph_commit
= lookup_commit(r
, &cur_oid
);
2525 if (!parse_commit_in_graph_one(r
, g
, graph_commit
))
2526 graph_report(_("failed to parse commit %s from commit-graph"),
2527 oid_to_hex(&cur_oid
));
2530 while (cur_fanout_pos
< 256) {
2531 uint32_t fanout_value
= get_be32(g
->chunk_oid_fanout
+ cur_fanout_pos
);
2533 if (g
->num_commits
!= fanout_value
)
2534 graph_report(_("commit-graph has incorrect fanout value: fanout[%d] = %u != %u"),
2535 cur_fanout_pos
, fanout_value
, i
);
2540 if (verify_commit_graph_error
& ~VERIFY_COMMIT_GRAPH_ERROR_HASH
)
2541 return verify_commit_graph_error
;
2543 if (flags
& COMMIT_GRAPH_WRITE_PROGRESS
)
2544 progress
= start_progress(_("Verifying commits in commit graph"),
2547 for (i
= 0; i
< g
->num_commits
; i
++) {
2548 struct commit
*graph_commit
, *odb_commit
;
2549 struct commit_list
*graph_parents
, *odb_parents
;
2550 timestamp_t max_generation
= 0;
2551 timestamp_t generation
;
2553 display_progress(progress
, i
+ 1);
2554 oidread(&cur_oid
, g
->chunk_oid_lookup
+ g
->hash_len
* i
);
2556 graph_commit
= lookup_commit(r
, &cur_oid
);
2557 odb_commit
= (struct commit
*)create_object(r
, &cur_oid
, alloc_commit_node(r
));
2558 if (repo_parse_commit_internal(r
, odb_commit
, 0, 0)) {
2559 graph_report(_("failed to parse commit %s from object database for commit-graph"),
2560 oid_to_hex(&cur_oid
));
2564 if (!oideq(&get_commit_tree_in_graph_one(r
, g
, graph_commit
)->object
.oid
,
2565 get_commit_tree_oid(odb_commit
)))
2566 graph_report(_("root tree OID for commit %s in commit-graph is %s != %s"),
2567 oid_to_hex(&cur_oid
),
2568 oid_to_hex(get_commit_tree_oid(graph_commit
)),
2569 oid_to_hex(get_commit_tree_oid(odb_commit
)));
2571 graph_parents
= graph_commit
->parents
;
2572 odb_parents
= odb_commit
->parents
;
2574 while (graph_parents
) {
2576 graph_report(_("commit-graph parent list for commit %s is too long"),
2577 oid_to_hex(&cur_oid
));
2581 /* parse parent in case it is in a base graph */
2582 parse_commit_in_graph_one(r
, g
, graph_parents
->item
);
2584 if (!oideq(&graph_parents
->item
->object
.oid
, &odb_parents
->item
->object
.oid
))
2585 graph_report(_("commit-graph parent for %s is %s != %s"),
2586 oid_to_hex(&cur_oid
),
2587 oid_to_hex(&graph_parents
->item
->object
.oid
),
2588 oid_to_hex(&odb_parents
->item
->object
.oid
));
2590 generation
= commit_graph_generation(graph_parents
->item
);
2591 if (generation
> max_generation
)
2592 max_generation
= generation
;
2594 graph_parents
= graph_parents
->next
;
2595 odb_parents
= odb_parents
->next
;
2599 graph_report(_("commit-graph parent list for commit %s terminates early"),
2600 oid_to_hex(&cur_oid
));
2602 if (!commit_graph_generation(graph_commit
)) {
2603 if (generation_zero
== GENERATION_NUMBER_EXISTS
)
2604 graph_report(_("commit-graph has generation number zero for commit %s, but non-zero elsewhere"),
2605 oid_to_hex(&cur_oid
));
2606 generation_zero
= GENERATION_ZERO_EXISTS
;
2607 } else if (generation_zero
== GENERATION_ZERO_EXISTS
)
2608 graph_report(_("commit-graph has non-zero generation number for commit %s, but zero elsewhere"),
2609 oid_to_hex(&cur_oid
));
2611 if (generation_zero
== GENERATION_ZERO_EXISTS
)
2615 * If we are using topological level and one of our parents has
2616 * generation GENERATION_NUMBER_V1_MAX, then our generation is
2617 * also GENERATION_NUMBER_V1_MAX. Decrement to avoid extra logic
2618 * in the following condition.
2620 if (!g
->read_generation_data
&& max_generation
== GENERATION_NUMBER_V1_MAX
)
2623 generation
= commit_graph_generation(graph_commit
);
2624 if (generation
< max_generation
+ 1)
2625 graph_report(_("commit-graph generation for commit %s is %"PRItime
" < %"PRItime
),
2626 oid_to_hex(&cur_oid
),
2628 max_generation
+ 1);
2630 if (graph_commit
->date
!= odb_commit
->date
)
2631 graph_report(_("commit date for commit %s in commit-graph is %"PRItime
" != %"PRItime
),
2632 oid_to_hex(&cur_oid
),
2636 stop_progress(&progress
);
2638 local_error
= verify_commit_graph_error
;
2640 if (!(flags
& COMMIT_GRAPH_VERIFY_SHALLOW
) && g
->base_graph
)
2641 local_error
|= verify_commit_graph(r
, g
->base_graph
, flags
);
2646 void free_commit_graph(struct commit_graph
*g
)
2651 munmap((void *)g
->data
, g
->data_len
);
2655 free(g
->bloom_filter_settings
);
2659 void disable_commit_graph(struct repository
*r
)
2661 r
->commit_graph_disabled
= 1;