1 #include "git-compat-util.h"
10 #include "hash-lookup.h"
11 #include "commit-graph.h"
12 #include "object-store.h"
15 #include "replace-object.h"
18 #include "commit-slab.h"
20 #include "json-writer.h"
22 #include "chunk-format.h"
24 void git_test_write_commit_graph_or_die(void)
27 if (!git_env_bool(GIT_TEST_COMMIT_GRAPH
, 0))
30 if (git_env_bool(GIT_TEST_COMMIT_GRAPH_CHANGED_PATHS
, 0))
31 flags
= COMMIT_GRAPH_WRITE_BLOOM_FILTERS
;
33 if (write_commit_graph_reachable(the_repository
->objects
->odb
,
35 die("failed to write commit-graph under GIT_TEST_COMMIT_GRAPH");
38 #define GRAPH_SIGNATURE 0x43475048 /* "CGPH" */
39 #define GRAPH_CHUNKID_OIDFANOUT 0x4f494446 /* "OIDF" */
40 #define GRAPH_CHUNKID_OIDLOOKUP 0x4f49444c /* "OIDL" */
41 #define GRAPH_CHUNKID_DATA 0x43444154 /* "CDAT" */
42 #define GRAPH_CHUNKID_GENERATION_DATA 0x47444154 /* "GDAT" */
43 #define GRAPH_CHUNKID_GENERATION_DATA_OVERFLOW 0x47444f56 /* "GDOV" */
44 #define GRAPH_CHUNKID_EXTRAEDGES 0x45444745 /* "EDGE" */
45 #define GRAPH_CHUNKID_BLOOMINDEXES 0x42494458 /* "BIDX" */
46 #define GRAPH_CHUNKID_BLOOMDATA 0x42444154 /* "BDAT" */
47 #define GRAPH_CHUNKID_BASE 0x42415345 /* "BASE" */
49 #define GRAPH_DATA_WIDTH (the_hash_algo->rawsz + 16)
51 #define GRAPH_VERSION_1 0x1
52 #define GRAPH_VERSION GRAPH_VERSION_1
54 #define GRAPH_EXTRA_EDGES_NEEDED 0x80000000
55 #define GRAPH_EDGE_LAST_MASK 0x7fffffff
56 #define GRAPH_PARENT_NONE 0x70000000
58 #define GRAPH_LAST_EDGE 0x80000000
60 #define GRAPH_HEADER_SIZE 8
61 #define GRAPH_FANOUT_SIZE (4 * 256)
62 #define GRAPH_MIN_SIZE (GRAPH_HEADER_SIZE + 4 * CHUNK_TOC_ENTRY_SIZE \
63 + GRAPH_FANOUT_SIZE + the_hash_algo->rawsz)
65 #define CORRECTED_COMMIT_DATE_OFFSET_OVERFLOW (1ULL << 31)
67 /* Remember to update object flag allocation in object.h */
68 #define REACHABLE (1u<<15)
70 define_commit_slab(topo_level_slab
, uint32_t);
72 /* Keep track of the order in which commits are added to our list. */
73 define_commit_slab(commit_pos
, int);
74 static struct commit_pos commit_pos
= COMMIT_SLAB_INIT(1, commit_pos
);
76 static void set_commit_pos(struct repository
*r
, const struct object_id
*oid
)
78 static int32_t max_pos
;
79 struct commit
*commit
= lookup_commit(r
, oid
);
82 return; /* should never happen, but be lenient */
84 *commit_pos_at(&commit_pos
, commit
) = max_pos
++;
87 static int commit_pos_cmp(const void *va
, const void *vb
)
89 const struct commit
*a
= *(const struct commit
**)va
;
90 const struct commit
*b
= *(const struct commit
**)vb
;
91 return commit_pos_at(&commit_pos
, a
) -
92 commit_pos_at(&commit_pos
, b
);
95 define_commit_slab(commit_graph_data_slab
, struct commit_graph_data
);
96 static struct commit_graph_data_slab commit_graph_data_slab
=
97 COMMIT_SLAB_INIT(1, commit_graph_data_slab
);
99 static int get_configured_generation_version(struct repository
*r
)
102 repo_config_get_int(r
, "commitgraph.generationversion", &version
);
106 uint32_t commit_graph_position(const struct commit
*c
)
108 struct commit_graph_data
*data
=
109 commit_graph_data_slab_peek(&commit_graph_data_slab
, c
);
111 return data
? data
->graph_pos
: COMMIT_NOT_FROM_GRAPH
;
114 timestamp_t
commit_graph_generation(const struct commit
*c
)
116 struct commit_graph_data
*data
=
117 commit_graph_data_slab_peek(&commit_graph_data_slab
, c
);
120 return GENERATION_NUMBER_INFINITY
;
121 else if (data
->graph_pos
== COMMIT_NOT_FROM_GRAPH
)
122 return GENERATION_NUMBER_INFINITY
;
124 return data
->generation
;
127 static struct commit_graph_data
*commit_graph_data_at(const struct commit
*c
)
129 unsigned int i
, nth_slab
;
130 struct commit_graph_data
*data
=
131 commit_graph_data_slab_peek(&commit_graph_data_slab
, c
);
136 nth_slab
= c
->index
/ commit_graph_data_slab
.slab_size
;
137 data
= commit_graph_data_slab_at(&commit_graph_data_slab
, c
);
140 * commit-slab initializes elements with zero, overwrite this with
141 * COMMIT_NOT_FROM_GRAPH for graph_pos.
143 * We avoid initializing generation with checking if graph position
144 * is not COMMIT_NOT_FROM_GRAPH.
146 for (i
= 0; i
< commit_graph_data_slab
.slab_size
; i
++) {
147 commit_graph_data_slab
.slab
[nth_slab
][i
].graph_pos
=
148 COMMIT_NOT_FROM_GRAPH
;
155 * Should be used only while writing commit-graph as it compares
156 * generation value of commits by directly accessing commit-slab.
158 static int commit_gen_cmp(const void *va
, const void *vb
)
160 const struct commit
*a
= *(const struct commit
**)va
;
161 const struct commit
*b
= *(const struct commit
**)vb
;
163 const timestamp_t generation_a
= commit_graph_data_at(a
)->generation
;
164 const timestamp_t generation_b
= commit_graph_data_at(b
)->generation
;
165 /* lower generation commits first */
166 if (generation_a
< generation_b
)
168 else if (generation_a
> generation_b
)
171 /* use date as a heuristic when generations are equal */
172 if (a
->date
< b
->date
)
174 else if (a
->date
> b
->date
)
179 char *get_commit_graph_filename(struct object_directory
*obj_dir
)
181 return xstrfmt("%s/info/commit-graph", obj_dir
->path
);
184 static char *get_split_graph_filename(struct object_directory
*odb
,
187 return xstrfmt("%s/info/commit-graphs/graph-%s.graph", odb
->path
,
191 char *get_commit_graph_chain_filename(struct object_directory
*odb
)
193 return xstrfmt("%s/info/commit-graphs/commit-graph-chain", odb
->path
);
196 static uint8_t oid_version(void)
198 switch (hash_algo_by_ptr(the_hash_algo
)) {
201 case GIT_HASH_SHA256
:
204 die(_("invalid hash version"));
208 static struct commit_graph
*alloc_commit_graph(void)
210 struct commit_graph
*g
= xcalloc(1, sizeof(*g
));
215 extern int read_replace_refs
;
217 static int commit_graph_compatible(struct repository
*r
)
222 if (read_replace_refs
) {
223 prepare_replace_object(r
);
224 if (hashmap_get_size(&r
->objects
->replace_map
->map
))
228 prepare_commit_graft(r
);
229 if (r
->parsed_objects
&&
230 (r
->parsed_objects
->grafts_nr
|| r
->parsed_objects
->substituted_parent
))
232 if (is_repository_shallow(r
))
238 int open_commit_graph(const char *graph_file
, int *fd
, struct stat
*st
)
240 *fd
= git_open(graph_file
);
243 if (fstat(*fd
, st
)) {
250 struct commit_graph
*load_commit_graph_one_fd_st(struct repository
*r
,
251 int fd
, struct stat
*st
,
252 struct object_directory
*odb
)
256 struct commit_graph
*ret
;
258 graph_size
= xsize_t(st
->st_size
);
260 if (graph_size
< GRAPH_MIN_SIZE
) {
262 error(_("commit-graph file is too small"));
265 graph_map
= xmmap(NULL
, graph_size
, PROT_READ
, MAP_PRIVATE
, fd
, 0);
267 ret
= parse_commit_graph(r
, graph_map
, graph_size
);
272 munmap(graph_map
, graph_size
);
277 static int verify_commit_graph_lite(struct commit_graph
*g
)
280 * Basic validation shared between parse_commit_graph()
281 * which'll be called every time the graph is used, and the
282 * much more expensive verify_commit_graph() used by
283 * "commit-graph verify".
285 * There should only be very basic checks here to ensure that
286 * we don't e.g. segfault in fill_commit_in_graph(), but
287 * because this is a very hot codepath nothing that e.g. loops
288 * over g->num_commits, or runs a checksum on the commit-graph
291 if (!g
->chunk_oid_fanout
) {
292 error("commit-graph is missing the OID Fanout chunk");
295 if (!g
->chunk_oid_lookup
) {
296 error("commit-graph is missing the OID Lookup chunk");
299 if (!g
->chunk_commit_data
) {
300 error("commit-graph is missing the Commit Data chunk");
307 static int graph_read_oid_lookup(const unsigned char *chunk_start
,
308 size_t chunk_size
, void *data
)
310 struct commit_graph
*g
= data
;
311 g
->chunk_oid_lookup
= chunk_start
;
312 g
->num_commits
= chunk_size
/ g
->hash_len
;
316 static int graph_read_bloom_data(const unsigned char *chunk_start
,
317 size_t chunk_size
, void *data
)
319 struct commit_graph
*g
= data
;
320 uint32_t hash_version
;
321 g
->chunk_bloom_data
= chunk_start
;
322 hash_version
= get_be32(chunk_start
);
324 if (hash_version
!= 1)
327 g
->bloom_filter_settings
= xmalloc(sizeof(struct bloom_filter_settings
));
328 g
->bloom_filter_settings
->hash_version
= hash_version
;
329 g
->bloom_filter_settings
->num_hashes
= get_be32(chunk_start
+ 4);
330 g
->bloom_filter_settings
->bits_per_entry
= get_be32(chunk_start
+ 8);
331 g
->bloom_filter_settings
->max_changed_paths
= DEFAULT_BLOOM_MAX_CHANGES
;
336 struct commit_graph
*parse_commit_graph(struct repository
*r
,
337 void *graph_map
, size_t graph_size
)
339 const unsigned char *data
;
340 struct commit_graph
*graph
;
341 uint32_t graph_signature
;
342 unsigned char graph_version
, hash_version
;
343 struct chunkfile
*cf
= NULL
;
348 if (graph_size
< GRAPH_MIN_SIZE
)
351 data
= (const unsigned char *)graph_map
;
353 graph_signature
= get_be32(data
);
354 if (graph_signature
!= GRAPH_SIGNATURE
) {
355 error(_("commit-graph signature %X does not match signature %X"),
356 graph_signature
, GRAPH_SIGNATURE
);
360 graph_version
= *(unsigned char*)(data
+ 4);
361 if (graph_version
!= GRAPH_VERSION
) {
362 error(_("commit-graph version %X does not match version %X"),
363 graph_version
, GRAPH_VERSION
);
367 hash_version
= *(unsigned char*)(data
+ 5);
368 if (hash_version
!= oid_version()) {
369 error(_("commit-graph hash version %X does not match version %X"),
370 hash_version
, oid_version());
374 prepare_repo_settings(r
);
376 graph
= alloc_commit_graph();
378 graph
->hash_len
= the_hash_algo
->rawsz
;
379 graph
->num_chunks
= *(unsigned char*)(data
+ 6);
380 graph
->data
= graph_map
;
381 graph
->data_len
= graph_size
;
383 if (graph_size
< GRAPH_HEADER_SIZE
+
384 (graph
->num_chunks
+ 1) * CHUNK_TOC_ENTRY_SIZE
+
385 GRAPH_FANOUT_SIZE
+ the_hash_algo
->rawsz
) {
386 error(_("commit-graph file is too small to hold %u chunks"),
392 cf
= init_chunkfile(NULL
);
394 if (read_table_of_contents(cf
, graph
->data
, graph_size
,
395 GRAPH_HEADER_SIZE
, graph
->num_chunks
))
396 goto free_and_return
;
398 pair_chunk(cf
, GRAPH_CHUNKID_OIDFANOUT
,
399 (const unsigned char **)&graph
->chunk_oid_fanout
);
400 read_chunk(cf
, GRAPH_CHUNKID_OIDLOOKUP
, graph_read_oid_lookup
, graph
);
401 pair_chunk(cf
, GRAPH_CHUNKID_DATA
, &graph
->chunk_commit_data
);
402 pair_chunk(cf
, GRAPH_CHUNKID_EXTRAEDGES
, &graph
->chunk_extra_edges
);
403 pair_chunk(cf
, GRAPH_CHUNKID_BASE
, &graph
->chunk_base_graphs
);
405 if (get_configured_generation_version(r
) >= 2) {
406 pair_chunk(cf
, GRAPH_CHUNKID_GENERATION_DATA
,
407 &graph
->chunk_generation_data
);
408 pair_chunk(cf
, GRAPH_CHUNKID_GENERATION_DATA_OVERFLOW
,
409 &graph
->chunk_generation_data_overflow
);
412 if (r
->settings
.commit_graph_read_changed_paths
) {
413 pair_chunk(cf
, GRAPH_CHUNKID_BLOOMINDEXES
,
414 &graph
->chunk_bloom_indexes
);
415 read_chunk(cf
, GRAPH_CHUNKID_BLOOMDATA
,
416 graph_read_bloom_data
, graph
);
419 if (graph
->chunk_bloom_indexes
&& graph
->chunk_bloom_data
) {
420 init_bloom_filters();
422 /* We need both the bloom chunks to exist together. Else ignore the data */
423 graph
->chunk_bloom_indexes
= NULL
;
424 graph
->chunk_bloom_data
= NULL
;
425 FREE_AND_NULL(graph
->bloom_filter_settings
);
428 oidread(&graph
->oid
, graph
->data
+ graph
->data_len
- graph
->hash_len
);
430 if (verify_commit_graph_lite(graph
))
431 goto free_and_return
;
438 free(graph
->bloom_filter_settings
);
443 static struct commit_graph
*load_commit_graph_one(struct repository
*r
,
444 const char *graph_file
,
445 struct object_directory
*odb
)
450 struct commit_graph
*g
;
451 int open_ok
= open_commit_graph(graph_file
, &fd
, &st
);
456 g
= load_commit_graph_one_fd_st(r
, fd
, &st
, odb
);
459 g
->filename
= xstrdup(graph_file
);
464 static struct commit_graph
*load_commit_graph_v1(struct repository
*r
,
465 struct object_directory
*odb
)
467 char *graph_name
= get_commit_graph_filename(odb
);
468 struct commit_graph
*g
= load_commit_graph_one(r
, graph_name
, odb
);
474 static int add_graph_to_chain(struct commit_graph
*g
,
475 struct commit_graph
*chain
,
476 struct object_id
*oids
,
479 struct commit_graph
*cur_g
= chain
;
481 if (n
&& !g
->chunk_base_graphs
) {
482 warning(_("commit-graph has no base graphs chunk"));
490 !oideq(&oids
[n
], &cur_g
->oid
) ||
491 !hasheq(oids
[n
].hash
, g
->chunk_base_graphs
+ g
->hash_len
* n
)) {
492 warning(_("commit-graph chain does not match"));
496 cur_g
= cur_g
->base_graph
;
499 g
->base_graph
= chain
;
502 g
->num_commits_in_base
= chain
->num_commits
+ chain
->num_commits_in_base
;
507 static struct commit_graph
*load_commit_graph_chain(struct repository
*r
,
508 struct object_directory
*odb
)
510 struct commit_graph
*graph_chain
= NULL
;
511 struct strbuf line
= STRBUF_INIT
;
513 struct object_id
*oids
;
514 int i
= 0, valid
= 1, count
;
515 char *chain_name
= get_commit_graph_chain_filename(odb
);
519 fp
= fopen(chain_name
, "r");
520 stat_res
= stat(chain_name
, &st
);
525 st
.st_size
<= the_hash_algo
->hexsz
)
528 count
= st
.st_size
/ (the_hash_algo
->hexsz
+ 1);
529 CALLOC_ARRAY(oids
, count
);
533 for (i
= 0; i
< count
; i
++) {
534 struct object_directory
*odb
;
536 if (strbuf_getline_lf(&line
, fp
) == EOF
)
539 if (get_oid_hex(line
.buf
, &oids
[i
])) {
540 warning(_("invalid commit-graph chain: line '%s' not a hash"),
547 for (odb
= r
->objects
->odb
; odb
; odb
= odb
->next
) {
548 char *graph_name
= get_split_graph_filename(odb
, line
.buf
);
549 struct commit_graph
*g
= load_commit_graph_one(r
, graph_name
, odb
);
554 if (add_graph_to_chain(g
, graph_chain
, oids
, i
)) {
564 warning(_("unable to find all commit-graph files"));
571 strbuf_release(&line
);
577 * returns 1 if and only if all graphs in the chain have
578 * corrected commit dates stored in the generation_data chunk.
580 static int validate_mixed_generation_chain(struct commit_graph
*g
)
582 int read_generation_data
= 1;
583 struct commit_graph
*p
= g
;
585 while (read_generation_data
&& p
) {
586 read_generation_data
= p
->read_generation_data
;
590 if (read_generation_data
)
594 g
->read_generation_data
= 0;
601 struct commit_graph
*read_commit_graph_one(struct repository
*r
,
602 struct object_directory
*odb
)
604 struct commit_graph
*g
= load_commit_graph_v1(r
, odb
);
607 g
= load_commit_graph_chain(r
, odb
);
609 validate_mixed_generation_chain(g
);
614 static void prepare_commit_graph_one(struct repository
*r
,
615 struct object_directory
*odb
)
618 if (r
->objects
->commit_graph
)
621 r
->objects
->commit_graph
= read_commit_graph_one(r
, odb
);
625 * Return 1 if commit_graph is non-NULL, and 0 otherwise.
627 * On the first invocation, this function attempts to load the commit
628 * graph if the_repository is configured to have one.
630 static int prepare_commit_graph(struct repository
*r
)
632 struct object_directory
*odb
;
635 * This must come before the "already attempted?" check below, because
636 * we want to disable even an already-loaded graph file.
638 if (r
->commit_graph_disabled
)
641 if (r
->objects
->commit_graph_attempted
)
642 return !!r
->objects
->commit_graph
;
643 r
->objects
->commit_graph_attempted
= 1;
645 prepare_repo_settings(r
);
647 if (!git_env_bool(GIT_TEST_COMMIT_GRAPH
, 0) &&
648 r
->settings
.core_commit_graph
!= 1)
650 * This repository is not configured to use commit graphs, so
651 * do not load one. (But report commit_graph_attempted anyway
652 * so that commit graph loading is not attempted again for this
657 if (!commit_graph_compatible(r
))
661 for (odb
= r
->objects
->odb
;
662 !r
->objects
->commit_graph
&& odb
;
664 prepare_commit_graph_one(r
, odb
);
665 return !!r
->objects
->commit_graph
;
668 int generation_numbers_enabled(struct repository
*r
)
670 uint32_t first_generation
;
671 struct commit_graph
*g
;
672 if (!prepare_commit_graph(r
))
675 g
= r
->objects
->commit_graph
;
680 first_generation
= get_be32(g
->chunk_commit_data
+
681 g
->hash_len
+ 8) >> 2;
683 return !!first_generation
;
686 int corrected_commit_dates_enabled(struct repository
*r
)
688 struct commit_graph
*g
;
689 if (!prepare_commit_graph(r
))
692 g
= r
->objects
->commit_graph
;
697 return g
->read_generation_data
;
700 struct bloom_filter_settings
*get_bloom_filter_settings(struct repository
*r
)
702 struct commit_graph
*g
= r
->objects
->commit_graph
;
704 if (g
->bloom_filter_settings
)
705 return g
->bloom_filter_settings
;
711 static void close_commit_graph_one(struct commit_graph
*g
)
716 close_commit_graph_one(g
->base_graph
);
717 free_commit_graph(g
);
720 void close_commit_graph(struct raw_object_store
*o
)
722 close_commit_graph_one(o
->commit_graph
);
723 o
->commit_graph
= NULL
;
726 static int bsearch_graph(struct commit_graph
*g
, struct object_id
*oid
, uint32_t *pos
)
728 return bsearch_hash(oid
->hash
, g
->chunk_oid_fanout
,
729 g
->chunk_oid_lookup
, g
->hash_len
, pos
);
732 static void load_oid_from_graph(struct commit_graph
*g
,
734 struct object_id
*oid
)
738 while (g
&& pos
< g
->num_commits_in_base
)
742 BUG("NULL commit-graph");
744 if (pos
>= g
->num_commits
+ g
->num_commits_in_base
)
745 die(_("invalid commit position. commit-graph is likely corrupt"));
747 lex_index
= pos
- g
->num_commits_in_base
;
749 oidread(oid
, g
->chunk_oid_lookup
+ g
->hash_len
* lex_index
);
752 static struct commit_list
**insert_parent_or_die(struct repository
*r
,
753 struct commit_graph
*g
,
755 struct commit_list
**pptr
)
758 struct object_id oid
;
760 if (pos
>= g
->num_commits
+ g
->num_commits_in_base
)
761 die("invalid parent position %"PRIu32
, pos
);
763 load_oid_from_graph(g
, pos
, &oid
);
764 c
= lookup_commit(r
, &oid
);
766 die(_("could not find commit %s"), oid_to_hex(&oid
));
767 commit_graph_data_at(c
)->graph_pos
= pos
;
768 return &commit_list_insert(c
, pptr
)->next
;
771 static void fill_commit_graph_info(struct commit
*item
, struct commit_graph
*g
, uint32_t pos
)
773 const unsigned char *commit_data
;
774 struct commit_graph_data
*graph_data
;
775 uint32_t lex_index
, offset_pos
;
776 uint64_t date_high
, date_low
, offset
;
778 while (pos
< g
->num_commits_in_base
)
781 if (pos
>= g
->num_commits
+ g
->num_commits_in_base
)
782 die(_("invalid commit position. commit-graph is likely corrupt"));
784 lex_index
= pos
- g
->num_commits_in_base
;
785 commit_data
= g
->chunk_commit_data
+ GRAPH_DATA_WIDTH
* lex_index
;
787 graph_data
= commit_graph_data_at(item
);
788 graph_data
->graph_pos
= pos
;
790 date_high
= get_be32(commit_data
+ g
->hash_len
+ 8) & 0x3;
791 date_low
= get_be32(commit_data
+ g
->hash_len
+ 12);
792 item
->date
= (timestamp_t
)((date_high
<< 32) | date_low
);
794 if (g
->read_generation_data
) {
795 offset
= (timestamp_t
)get_be32(g
->chunk_generation_data
+ sizeof(uint32_t) * lex_index
);
797 if (offset
& CORRECTED_COMMIT_DATE_OFFSET_OVERFLOW
) {
798 if (!g
->chunk_generation_data_overflow
)
799 die(_("commit-graph requires overflow generation data but has none"));
801 offset_pos
= offset
^ CORRECTED_COMMIT_DATE_OFFSET_OVERFLOW
;
802 graph_data
->generation
= get_be64(g
->chunk_generation_data_overflow
+ 8 * offset_pos
);
804 graph_data
->generation
= item
->date
+ offset
;
806 graph_data
->generation
= get_be32(commit_data
+ g
->hash_len
+ 8) >> 2;
809 *topo_level_slab_at(g
->topo_levels
, item
) = get_be32(commit_data
+ g
->hash_len
+ 8) >> 2;
812 static inline void set_commit_tree(struct commit
*c
, struct tree
*t
)
817 static int fill_commit_in_graph(struct repository
*r
,
819 struct commit_graph
*g
, uint32_t pos
)
822 uint32_t *parent_data_ptr
;
823 struct commit_list
**pptr
;
824 const unsigned char *commit_data
;
827 while (pos
< g
->num_commits_in_base
)
830 fill_commit_graph_info(item
, g
, pos
);
832 lex_index
= pos
- g
->num_commits_in_base
;
833 commit_data
= g
->chunk_commit_data
+ (g
->hash_len
+ 16) * lex_index
;
835 item
->object
.parsed
= 1;
837 set_commit_tree(item
, NULL
);
839 pptr
= &item
->parents
;
841 edge_value
= get_be32(commit_data
+ g
->hash_len
);
842 if (edge_value
== GRAPH_PARENT_NONE
)
844 pptr
= insert_parent_or_die(r
, g
, edge_value
, pptr
);
846 edge_value
= get_be32(commit_data
+ g
->hash_len
+ 4);
847 if (edge_value
== GRAPH_PARENT_NONE
)
849 if (!(edge_value
& GRAPH_EXTRA_EDGES_NEEDED
)) {
850 pptr
= insert_parent_or_die(r
, g
, edge_value
, pptr
);
854 parent_data_ptr
= (uint32_t*)(g
->chunk_extra_edges
+
855 4 * (uint64_t)(edge_value
& GRAPH_EDGE_LAST_MASK
));
857 edge_value
= get_be32(parent_data_ptr
);
858 pptr
= insert_parent_or_die(r
, g
,
859 edge_value
& GRAPH_EDGE_LAST_MASK
,
862 } while (!(edge_value
& GRAPH_LAST_EDGE
));
867 static int find_commit_in_graph(struct commit
*item
, struct commit_graph
*g
, uint32_t *pos
)
869 uint32_t graph_pos
= commit_graph_position(item
);
870 if (graph_pos
!= COMMIT_NOT_FROM_GRAPH
) {
874 struct commit_graph
*cur_g
= g
;
877 while (cur_g
&& !bsearch_graph(cur_g
, &(item
->object
.oid
), &lex_index
))
878 cur_g
= cur_g
->base_graph
;
881 *pos
= lex_index
+ cur_g
->num_commits_in_base
;
889 static int parse_commit_in_graph_one(struct repository
*r
,
890 struct commit_graph
*g
,
895 if (item
->object
.parsed
)
898 if (find_commit_in_graph(item
, g
, &pos
))
899 return fill_commit_in_graph(r
, item
, g
, pos
);
904 int parse_commit_in_graph(struct repository
*r
, struct commit
*item
)
906 static int checked_env
= 0;
909 git_env_bool(GIT_TEST_COMMIT_GRAPH_DIE_ON_PARSE
, 0))
910 die("dying as requested by the '%s' variable on commit-graph parse!",
911 GIT_TEST_COMMIT_GRAPH_DIE_ON_PARSE
);
914 if (!prepare_commit_graph(r
))
916 return parse_commit_in_graph_one(r
, r
->objects
->commit_graph
, item
);
919 void load_commit_graph_info(struct repository
*r
, struct commit
*item
)
922 if (!prepare_commit_graph(r
))
924 if (find_commit_in_graph(item
, r
->objects
->commit_graph
, &pos
))
925 fill_commit_graph_info(item
, r
->objects
->commit_graph
, pos
);
928 static struct tree
*load_tree_for_commit(struct repository
*r
,
929 struct commit_graph
*g
,
932 struct object_id oid
;
933 const unsigned char *commit_data
;
934 uint32_t graph_pos
= commit_graph_position(c
);
936 while (graph_pos
< g
->num_commits_in_base
)
939 commit_data
= g
->chunk_commit_data
+
940 GRAPH_DATA_WIDTH
* (graph_pos
- g
->num_commits_in_base
);
942 oidread(&oid
, commit_data
);
943 set_commit_tree(c
, lookup_tree(r
, &oid
));
945 return c
->maybe_tree
;
948 static struct tree
*get_commit_tree_in_graph_one(struct repository
*r
,
949 struct commit_graph
*g
,
950 const struct commit
*c
)
953 return c
->maybe_tree
;
954 if (commit_graph_position(c
) == COMMIT_NOT_FROM_GRAPH
)
955 BUG("get_commit_tree_in_graph_one called from non-commit-graph commit");
957 return load_tree_for_commit(r
, g
, (struct commit
*)c
);
960 struct tree
*get_commit_tree_in_graph(struct repository
*r
, const struct commit
*c
)
962 return get_commit_tree_in_graph_one(r
, r
->objects
->commit_graph
, c
);
965 struct packed_commit_list
{
966 struct commit
**list
;
971 struct write_commit_graph_context
{
972 struct repository
*r
;
973 struct object_directory
*odb
;
975 struct oid_array oids
;
976 struct packed_commit_list commits
;
978 int num_generation_data_overflows
;
979 unsigned long approx_nr_objects
;
980 struct progress
*progress
;
982 uint64_t progress_cnt
;
984 char *base_graph_name
;
985 int num_commit_graphs_before
;
986 int num_commit_graphs_after
;
987 char **commit_graph_filenames_before
;
988 char **commit_graph_filenames_after
;
989 char **commit_graph_hash_after
;
990 uint32_t new_num_commits_in_base
;
991 struct commit_graph
*new_base_graph
;
998 write_generation_data
:1,
999 trust_generation_numbers
:1;
1001 struct topo_level_slab
*topo_levels
;
1002 const struct commit_graph_opts
*opts
;
1003 size_t total_bloom_filter_data_size
;
1004 const struct bloom_filter_settings
*bloom_settings
;
1006 int count_bloom_filter_computed
;
1007 int count_bloom_filter_not_computed
;
1008 int count_bloom_filter_trunc_empty
;
1009 int count_bloom_filter_trunc_large
;
1012 static int write_graph_chunk_fanout(struct hashfile
*f
,
1015 struct write_commit_graph_context
*ctx
= data
;
1017 struct commit
**list
= ctx
->commits
.list
;
1020 * Write the first-level table (the list is sorted,
1021 * but we use a 256-entry lookup to be able to avoid
1022 * having to do eight extra binary search iterations).
1024 for (i
= 0; i
< 256; i
++) {
1025 while (count
< ctx
->commits
.nr
) {
1026 if ((*list
)->object
.oid
.hash
[0] != i
)
1028 display_progress(ctx
->progress
, ++ctx
->progress_cnt
);
1033 hashwrite_be32(f
, count
);
1039 static int write_graph_chunk_oids(struct hashfile
*f
,
1042 struct write_commit_graph_context
*ctx
= data
;
1043 struct commit
**list
= ctx
->commits
.list
;
1045 for (count
= 0; count
< ctx
->commits
.nr
; count
++, list
++) {
1046 display_progress(ctx
->progress
, ++ctx
->progress_cnt
);
1047 hashwrite(f
, (*list
)->object
.oid
.hash
, the_hash_algo
->rawsz
);
1053 static const struct object_id
*commit_to_oid(size_t index
, const void *table
)
1055 const struct commit
* const *commits
= table
;
1056 return &commits
[index
]->object
.oid
;
1059 static int write_graph_chunk_data(struct hashfile
*f
,
1062 struct write_commit_graph_context
*ctx
= data
;
1063 struct commit
**list
= ctx
->commits
.list
;
1064 struct commit
**last
= ctx
->commits
.list
+ ctx
->commits
.nr
;
1065 uint32_t num_extra_edges
= 0;
1067 while (list
< last
) {
1068 struct commit_list
*parent
;
1069 struct object_id
*tree
;
1071 uint32_t packedDate
[2];
1072 display_progress(ctx
->progress
, ++ctx
->progress_cnt
);
1074 if (repo_parse_commit_no_graph(ctx
->r
, *list
))
1075 die(_("unable to parse commit %s"),
1076 oid_to_hex(&(*list
)->object
.oid
));
1077 tree
= get_commit_tree_oid(*list
);
1078 hashwrite(f
, tree
->hash
, the_hash_algo
->rawsz
);
1080 parent
= (*list
)->parents
;
1083 edge_value
= GRAPH_PARENT_NONE
;
1085 edge_value
= oid_pos(&parent
->item
->object
.oid
,
1090 if (edge_value
>= 0)
1091 edge_value
+= ctx
->new_num_commits_in_base
;
1092 else if (ctx
->new_base_graph
) {
1094 if (find_commit_in_graph(parent
->item
,
1095 ctx
->new_base_graph
,
1101 BUG("missing parent %s for commit %s",
1102 oid_to_hex(&parent
->item
->object
.oid
),
1103 oid_to_hex(&(*list
)->object
.oid
));
1106 hashwrite_be32(f
, edge_value
);
1109 parent
= parent
->next
;
1112 edge_value
= GRAPH_PARENT_NONE
;
1113 else if (parent
->next
)
1114 edge_value
= GRAPH_EXTRA_EDGES_NEEDED
| num_extra_edges
;
1116 edge_value
= oid_pos(&parent
->item
->object
.oid
,
1121 if (edge_value
>= 0)
1122 edge_value
+= ctx
->new_num_commits_in_base
;
1123 else if (ctx
->new_base_graph
) {
1125 if (find_commit_in_graph(parent
->item
,
1126 ctx
->new_base_graph
,
1132 BUG("missing parent %s for commit %s",
1133 oid_to_hex(&parent
->item
->object
.oid
),
1134 oid_to_hex(&(*list
)->object
.oid
));
1137 hashwrite_be32(f
, edge_value
);
1139 if (edge_value
& GRAPH_EXTRA_EDGES_NEEDED
) {
1142 parent
= parent
->next
;
1146 if (sizeof((*list
)->date
) > 4)
1147 packedDate
[0] = htonl(((*list
)->date
>> 32) & 0x3);
1151 packedDate
[0] |= htonl(*topo_level_slab_at(ctx
->topo_levels
, *list
) << 2);
1153 packedDate
[1] = htonl((*list
)->date
);
1154 hashwrite(f
, packedDate
, 8);
1162 static int write_graph_chunk_generation_data(struct hashfile
*f
,
1165 struct write_commit_graph_context
*ctx
= data
;
1166 int i
, num_generation_data_overflows
= 0;
1168 for (i
= 0; i
< ctx
->commits
.nr
; i
++) {
1169 struct commit
*c
= ctx
->commits
.list
[i
];
1171 repo_parse_commit(ctx
->r
, c
);
1172 offset
= commit_graph_data_at(c
)->generation
- c
->date
;
1173 display_progress(ctx
->progress
, ++ctx
->progress_cnt
);
1175 if (offset
> GENERATION_NUMBER_V2_OFFSET_MAX
) {
1176 offset
= CORRECTED_COMMIT_DATE_OFFSET_OVERFLOW
| num_generation_data_overflows
;
1177 num_generation_data_overflows
++;
1180 hashwrite_be32(f
, offset
);
1186 static int write_graph_chunk_generation_data_overflow(struct hashfile
*f
,
1189 struct write_commit_graph_context
*ctx
= data
;
1191 for (i
= 0; i
< ctx
->commits
.nr
; i
++) {
1192 struct commit
*c
= ctx
->commits
.list
[i
];
1193 timestamp_t offset
= commit_graph_data_at(c
)->generation
- c
->date
;
1194 display_progress(ctx
->progress
, ++ctx
->progress_cnt
);
1196 if (offset
> GENERATION_NUMBER_V2_OFFSET_MAX
) {
1197 hashwrite_be32(f
, offset
>> 32);
1198 hashwrite_be32(f
, (uint32_t) offset
);
1205 static int write_graph_chunk_extra_edges(struct hashfile
*f
,
1208 struct write_commit_graph_context
*ctx
= data
;
1209 struct commit
**list
= ctx
->commits
.list
;
1210 struct commit
**last
= ctx
->commits
.list
+ ctx
->commits
.nr
;
1211 struct commit_list
*parent
;
1213 while (list
< last
) {
1214 int num_parents
= 0;
1216 display_progress(ctx
->progress
, ++ctx
->progress_cnt
);
1218 for (parent
= (*list
)->parents
; num_parents
< 3 && parent
;
1219 parent
= parent
->next
)
1222 if (num_parents
<= 2) {
1227 /* Since num_parents > 2, this initializer is safe. */
1228 for (parent
= (*list
)->parents
->next
; parent
; parent
= parent
->next
) {
1229 int edge_value
= oid_pos(&parent
->item
->object
.oid
,
1234 if (edge_value
>= 0)
1235 edge_value
+= ctx
->new_num_commits_in_base
;
1236 else if (ctx
->new_base_graph
) {
1238 if (find_commit_in_graph(parent
->item
,
1239 ctx
->new_base_graph
,
1245 BUG("missing parent %s for commit %s",
1246 oid_to_hex(&parent
->item
->object
.oid
),
1247 oid_to_hex(&(*list
)->object
.oid
));
1248 else if (!parent
->next
)
1249 edge_value
|= GRAPH_LAST_EDGE
;
1251 hashwrite_be32(f
, edge_value
);
1260 static int write_graph_chunk_bloom_indexes(struct hashfile
*f
,
1263 struct write_commit_graph_context
*ctx
= data
;
1264 struct commit
**list
= ctx
->commits
.list
;
1265 struct commit
**last
= ctx
->commits
.list
+ ctx
->commits
.nr
;
1266 uint32_t cur_pos
= 0;
1268 while (list
< last
) {
1269 struct bloom_filter
*filter
= get_bloom_filter(ctx
->r
, *list
);
1270 size_t len
= filter
? filter
->len
: 0;
1272 display_progress(ctx
->progress
, ++ctx
->progress_cnt
);
1273 hashwrite_be32(f
, cur_pos
);
1280 static void trace2_bloom_filter_settings(struct write_commit_graph_context
*ctx
)
1282 struct json_writer jw
= JSON_WRITER_INIT
;
1284 jw_object_begin(&jw
, 0);
1285 jw_object_intmax(&jw
, "hash_version", ctx
->bloom_settings
->hash_version
);
1286 jw_object_intmax(&jw
, "num_hashes", ctx
->bloom_settings
->num_hashes
);
1287 jw_object_intmax(&jw
, "bits_per_entry", ctx
->bloom_settings
->bits_per_entry
);
1288 jw_object_intmax(&jw
, "max_changed_paths", ctx
->bloom_settings
->max_changed_paths
);
1291 trace2_data_json("bloom", ctx
->r
, "settings", &jw
);
1296 static int write_graph_chunk_bloom_data(struct hashfile
*f
,
1299 struct write_commit_graph_context
*ctx
= data
;
1300 struct commit
**list
= ctx
->commits
.list
;
1301 struct commit
**last
= ctx
->commits
.list
+ ctx
->commits
.nr
;
1303 trace2_bloom_filter_settings(ctx
);
1305 hashwrite_be32(f
, ctx
->bloom_settings
->hash_version
);
1306 hashwrite_be32(f
, ctx
->bloom_settings
->num_hashes
);
1307 hashwrite_be32(f
, ctx
->bloom_settings
->bits_per_entry
);
1309 while (list
< last
) {
1310 struct bloom_filter
*filter
= get_bloom_filter(ctx
->r
, *list
);
1311 size_t len
= filter
? filter
->len
: 0;
1313 display_progress(ctx
->progress
, ++ctx
->progress_cnt
);
1315 hashwrite(f
, filter
->data
, len
* sizeof(unsigned char));
1322 static int add_packed_commits(const struct object_id
*oid
,
1323 struct packed_git
*pack
,
1327 struct write_commit_graph_context
*ctx
= (struct write_commit_graph_context
*)data
;
1328 enum object_type type
;
1329 off_t offset
= nth_packed_object_offset(pack
, pos
);
1330 struct object_info oi
= OBJECT_INFO_INIT
;
1333 display_progress(ctx
->progress
, ++ctx
->progress_done
);
1336 if (packed_object_info(ctx
->r
, pack
, offset
, &oi
) < 0)
1337 die(_("unable to get type of object %s"), oid_to_hex(oid
));
1339 if (type
!= OBJ_COMMIT
)
1342 oid_array_append(&ctx
->oids
, oid
);
1343 set_commit_pos(ctx
->r
, oid
);
1348 static void add_missing_parents(struct write_commit_graph_context
*ctx
, struct commit
*commit
)
1350 struct commit_list
*parent
;
1351 for (parent
= commit
->parents
; parent
; parent
= parent
->next
) {
1352 if (!(parent
->item
->object
.flags
& REACHABLE
)) {
1353 oid_array_append(&ctx
->oids
, &parent
->item
->object
.oid
);
1354 parent
->item
->object
.flags
|= REACHABLE
;
1359 static void close_reachable(struct write_commit_graph_context
*ctx
)
1362 struct commit
*commit
;
1363 enum commit_graph_split_flags flags
= ctx
->opts
?
1364 ctx
->opts
->split_flags
: COMMIT_GRAPH_SPLIT_UNSPECIFIED
;
1366 if (ctx
->report_progress
)
1367 ctx
->progress
= start_delayed_progress(
1368 _("Loading known commits in commit graph"),
1370 for (i
= 0; i
< ctx
->oids
.nr
; i
++) {
1371 display_progress(ctx
->progress
, i
+ 1);
1372 commit
= lookup_commit(ctx
->r
, &ctx
->oids
.oid
[i
]);
1374 commit
->object
.flags
|= REACHABLE
;
1376 stop_progress(&ctx
->progress
);
1379 * As this loop runs, ctx->oids.nr may grow, but not more
1380 * than the number of missing commits in the reachable
1383 if (ctx
->report_progress
)
1384 ctx
->progress
= start_delayed_progress(
1385 _("Expanding reachable commits in commit graph"),
1387 for (i
= 0; i
< ctx
->oids
.nr
; i
++) {
1388 display_progress(ctx
->progress
, i
+ 1);
1389 commit
= lookup_commit(ctx
->r
, &ctx
->oids
.oid
[i
]);
1394 if ((!repo_parse_commit(ctx
->r
, commit
) &&
1395 commit_graph_position(commit
) == COMMIT_NOT_FROM_GRAPH
) ||
1396 flags
== COMMIT_GRAPH_SPLIT_REPLACE
)
1397 add_missing_parents(ctx
, commit
);
1398 } else if (!repo_parse_commit_no_graph(ctx
->r
, commit
))
1399 add_missing_parents(ctx
, commit
);
1401 stop_progress(&ctx
->progress
);
1403 if (ctx
->report_progress
)
1404 ctx
->progress
= start_delayed_progress(
1405 _("Clearing commit marks in commit graph"),
1407 for (i
= 0; i
< ctx
->oids
.nr
; i
++) {
1408 display_progress(ctx
->progress
, i
+ 1);
1409 commit
= lookup_commit(ctx
->r
, &ctx
->oids
.oid
[i
]);
1412 commit
->object
.flags
&= ~REACHABLE
;
1414 stop_progress(&ctx
->progress
);
1417 static void compute_topological_levels(struct write_commit_graph_context
*ctx
)
1420 struct commit_list
*list
= NULL
;
1422 if (ctx
->report_progress
)
1423 ctx
->progress
= start_delayed_progress(
1424 _("Computing commit graph topological levels"),
1426 for (i
= 0; i
< ctx
->commits
.nr
; i
++) {
1427 struct commit
*c
= ctx
->commits
.list
[i
];
1430 repo_parse_commit(ctx
->r
, c
);
1431 level
= *topo_level_slab_at(ctx
->topo_levels
, c
);
1433 display_progress(ctx
->progress
, i
+ 1);
1434 if (level
!= GENERATION_NUMBER_ZERO
)
1437 commit_list_insert(c
, &list
);
1439 struct commit
*current
= list
->item
;
1440 struct commit_list
*parent
;
1441 int all_parents_computed
= 1;
1442 uint32_t max_level
= 0;
1444 for (parent
= current
->parents
; parent
; parent
= parent
->next
) {
1445 repo_parse_commit(ctx
->r
, parent
->item
);
1446 level
= *topo_level_slab_at(ctx
->topo_levels
, parent
->item
);
1448 if (level
== GENERATION_NUMBER_ZERO
) {
1449 all_parents_computed
= 0;
1450 commit_list_insert(parent
->item
, &list
);
1454 if (level
> max_level
)
1458 if (all_parents_computed
) {
1461 if (max_level
> GENERATION_NUMBER_V1_MAX
- 1)
1462 max_level
= GENERATION_NUMBER_V1_MAX
- 1;
1463 *topo_level_slab_at(ctx
->topo_levels
, current
) = max_level
+ 1;
1467 stop_progress(&ctx
->progress
);
1470 static void compute_generation_numbers(struct write_commit_graph_context
*ctx
)
1473 struct commit_list
*list
= NULL
;
1475 if (ctx
->report_progress
)
1476 ctx
->progress
= start_delayed_progress(
1477 _("Computing commit graph generation numbers"),
1480 if (!ctx
->trust_generation_numbers
) {
1481 for (i
= 0; i
< ctx
->commits
.nr
; i
++) {
1482 struct commit
*c
= ctx
->commits
.list
[i
];
1483 repo_parse_commit(ctx
->r
, c
);
1484 commit_graph_data_at(c
)->generation
= GENERATION_NUMBER_ZERO
;
1488 for (i
= 0; i
< ctx
->commits
.nr
; i
++) {
1489 struct commit
*c
= ctx
->commits
.list
[i
];
1490 timestamp_t corrected_commit_date
;
1492 repo_parse_commit(ctx
->r
, c
);
1493 corrected_commit_date
= commit_graph_data_at(c
)->generation
;
1495 display_progress(ctx
->progress
, i
+ 1);
1496 if (corrected_commit_date
!= GENERATION_NUMBER_ZERO
)
1499 commit_list_insert(c
, &list
);
1501 struct commit
*current
= list
->item
;
1502 struct commit_list
*parent
;
1503 int all_parents_computed
= 1;
1504 timestamp_t max_corrected_commit_date
= 0;
1506 for (parent
= current
->parents
; parent
; parent
= parent
->next
) {
1507 repo_parse_commit(ctx
->r
, parent
->item
);
1508 corrected_commit_date
= commit_graph_data_at(parent
->item
)->generation
;
1510 if (corrected_commit_date
== GENERATION_NUMBER_ZERO
) {
1511 all_parents_computed
= 0;
1512 commit_list_insert(parent
->item
, &list
);
1516 if (corrected_commit_date
> max_corrected_commit_date
)
1517 max_corrected_commit_date
= corrected_commit_date
;
1520 if (all_parents_computed
) {
1523 if (current
->date
&& current
->date
> max_corrected_commit_date
)
1524 max_corrected_commit_date
= current
->date
- 1;
1525 commit_graph_data_at(current
)->generation
= max_corrected_commit_date
+ 1;
1527 if (commit_graph_data_at(current
)->generation
- current
->date
> GENERATION_NUMBER_V2_OFFSET_MAX
)
1528 ctx
->num_generation_data_overflows
++;
1532 stop_progress(&ctx
->progress
);
1535 static void trace2_bloom_filter_write_statistics(struct write_commit_graph_context
*ctx
)
1537 trace2_data_intmax("commit-graph", ctx
->r
, "filter-computed",
1538 ctx
->count_bloom_filter_computed
);
1539 trace2_data_intmax("commit-graph", ctx
->r
, "filter-not-computed",
1540 ctx
->count_bloom_filter_not_computed
);
1541 trace2_data_intmax("commit-graph", ctx
->r
, "filter-trunc-empty",
1542 ctx
->count_bloom_filter_trunc_empty
);
1543 trace2_data_intmax("commit-graph", ctx
->r
, "filter-trunc-large",
1544 ctx
->count_bloom_filter_trunc_large
);
1547 static void compute_bloom_filters(struct write_commit_graph_context
*ctx
)
1550 struct progress
*progress
= NULL
;
1551 struct commit
**sorted_commits
;
1552 int max_new_filters
;
1554 init_bloom_filters();
1556 if (ctx
->report_progress
)
1557 progress
= start_delayed_progress(
1558 _("Computing commit changed paths Bloom filters"),
1561 ALLOC_ARRAY(sorted_commits
, ctx
->commits
.nr
);
1562 COPY_ARRAY(sorted_commits
, ctx
->commits
.list
, ctx
->commits
.nr
);
1564 if (ctx
->order_by_pack
)
1565 QSORT(sorted_commits
, ctx
->commits
.nr
, commit_pos_cmp
);
1567 QSORT(sorted_commits
, ctx
->commits
.nr
, commit_gen_cmp
);
1569 max_new_filters
= ctx
->opts
&& ctx
->opts
->max_new_filters
>= 0 ?
1570 ctx
->opts
->max_new_filters
: ctx
->commits
.nr
;
1572 for (i
= 0; i
< ctx
->commits
.nr
; i
++) {
1573 enum bloom_filter_computed computed
= 0;
1574 struct commit
*c
= sorted_commits
[i
];
1575 struct bloom_filter
*filter
= get_or_compute_bloom_filter(
1578 ctx
->count_bloom_filter_computed
< max_new_filters
,
1579 ctx
->bloom_settings
,
1581 if (computed
& BLOOM_COMPUTED
) {
1582 ctx
->count_bloom_filter_computed
++;
1583 if (computed
& BLOOM_TRUNC_EMPTY
)
1584 ctx
->count_bloom_filter_trunc_empty
++;
1585 if (computed
& BLOOM_TRUNC_LARGE
)
1586 ctx
->count_bloom_filter_trunc_large
++;
1587 } else if (computed
& BLOOM_NOT_COMPUTED
)
1588 ctx
->count_bloom_filter_not_computed
++;
1589 ctx
->total_bloom_filter_data_size
+= filter
1590 ? sizeof(unsigned char) * filter
->len
: 0;
1591 display_progress(progress
, i
+ 1);
1594 if (trace2_is_enabled())
1595 trace2_bloom_filter_write_statistics(ctx
);
1597 free(sorted_commits
);
1598 stop_progress(&progress
);
1601 struct refs_cb_data
{
1602 struct oidset
*commits
;
1603 struct progress
*progress
;
1606 static int add_ref_to_set(const char *refname
,
1607 const struct object_id
*oid
,
1608 int flags
, void *cb_data
)
1610 struct object_id peeled
;
1611 struct refs_cb_data
*data
= (struct refs_cb_data
*)cb_data
;
1613 if (!peel_iterated_oid(oid
, &peeled
))
1615 if (oid_object_info(the_repository
, oid
, NULL
) == OBJ_COMMIT
)
1616 oidset_insert(data
->commits
, oid
);
1618 display_progress(data
->progress
, oidset_size(data
->commits
));
1623 int write_commit_graph_reachable(struct object_directory
*odb
,
1624 enum commit_graph_write_flags flags
,
1625 const struct commit_graph_opts
*opts
)
1627 struct oidset commits
= OIDSET_INIT
;
1628 struct refs_cb_data data
;
1631 memset(&data
, 0, sizeof(data
));
1632 data
.commits
= &commits
;
1633 if (flags
& COMMIT_GRAPH_WRITE_PROGRESS
)
1634 data
.progress
= start_delayed_progress(
1635 _("Collecting referenced commits"), 0);
1637 for_each_ref(add_ref_to_set
, &data
);
1639 stop_progress(&data
.progress
);
1641 result
= write_commit_graph(odb
, NULL
, &commits
,
1644 oidset_clear(&commits
);
1648 static int fill_oids_from_packs(struct write_commit_graph_context
*ctx
,
1649 struct string_list
*pack_indexes
)
1652 struct strbuf progress_title
= STRBUF_INIT
;
1653 struct strbuf packname
= STRBUF_INIT
;
1656 strbuf_addf(&packname
, "%s/pack/", ctx
->odb
->path
);
1657 dirlen
= packname
.len
;
1658 if (ctx
->report_progress
) {
1659 strbuf_addf(&progress_title
,
1660 Q_("Finding commits for commit graph in %d pack",
1661 "Finding commits for commit graph in %d packs",
1664 ctx
->progress
= start_delayed_progress(progress_title
.buf
, 0);
1665 ctx
->progress_done
= 0;
1667 for (i
= 0; i
< pack_indexes
->nr
; i
++) {
1668 struct packed_git
*p
;
1669 strbuf_setlen(&packname
, dirlen
);
1670 strbuf_addstr(&packname
, pack_indexes
->items
[i
].string
);
1671 p
= add_packed_git(packname
.buf
, packname
.len
, 1);
1673 error(_("error adding pack %s"), packname
.buf
);
1676 if (open_pack_index(p
)) {
1677 error(_("error opening index for %s"), packname
.buf
);
1680 for_each_object_in_pack(p
, add_packed_commits
, ctx
,
1681 FOR_EACH_OBJECT_PACK_ORDER
);
1686 stop_progress(&ctx
->progress
);
1687 strbuf_release(&progress_title
);
1688 strbuf_release(&packname
);
1693 static int fill_oids_from_commits(struct write_commit_graph_context
*ctx
,
1694 struct oidset
*commits
)
1696 struct oidset_iter iter
;
1697 struct object_id
*oid
;
1699 if (!oidset_size(commits
))
1702 oidset_iter_init(commits
, &iter
);
1703 while ((oid
= oidset_iter_next(&iter
))) {
1704 oid_array_append(&ctx
->oids
, oid
);
1710 static void fill_oids_from_all_packs(struct write_commit_graph_context
*ctx
)
1712 if (ctx
->report_progress
)
1713 ctx
->progress
= start_delayed_progress(
1714 _("Finding commits for commit graph among packed objects"),
1715 ctx
->approx_nr_objects
);
1716 for_each_packed_object(add_packed_commits
, ctx
,
1717 FOR_EACH_OBJECT_PACK_ORDER
);
1718 if (ctx
->progress_done
< ctx
->approx_nr_objects
)
1719 display_progress(ctx
->progress
, ctx
->approx_nr_objects
);
1720 stop_progress(&ctx
->progress
);
1723 static void copy_oids_to_commits(struct write_commit_graph_context
*ctx
)
1726 enum commit_graph_split_flags flags
= ctx
->opts
?
1727 ctx
->opts
->split_flags
: COMMIT_GRAPH_SPLIT_UNSPECIFIED
;
1729 ctx
->num_extra_edges
= 0;
1730 if (ctx
->report_progress
)
1731 ctx
->progress
= start_delayed_progress(
1732 _("Finding extra edges in commit graph"),
1734 oid_array_sort(&ctx
->oids
);
1735 for (i
= 0; i
< ctx
->oids
.nr
; i
= oid_array_next_unique(&ctx
->oids
, i
)) {
1736 unsigned int num_parents
;
1738 display_progress(ctx
->progress
, i
+ 1);
1740 ALLOC_GROW(ctx
->commits
.list
, ctx
->commits
.nr
+ 1, ctx
->commits
.alloc
);
1741 ctx
->commits
.list
[ctx
->commits
.nr
] = lookup_commit(ctx
->r
, &ctx
->oids
.oid
[i
]);
1743 if (ctx
->split
&& flags
!= COMMIT_GRAPH_SPLIT_REPLACE
&&
1744 commit_graph_position(ctx
->commits
.list
[ctx
->commits
.nr
]) != COMMIT_NOT_FROM_GRAPH
)
1747 if (ctx
->split
&& flags
== COMMIT_GRAPH_SPLIT_REPLACE
)
1748 repo_parse_commit(ctx
->r
, ctx
->commits
.list
[ctx
->commits
.nr
]);
1750 repo_parse_commit_no_graph(ctx
->r
, ctx
->commits
.list
[ctx
->commits
.nr
]);
1752 num_parents
= commit_list_count(ctx
->commits
.list
[ctx
->commits
.nr
]->parents
);
1753 if (num_parents
> 2)
1754 ctx
->num_extra_edges
+= num_parents
- 1;
1758 stop_progress(&ctx
->progress
);
1761 static int write_graph_chunk_base_1(struct hashfile
*f
,
1762 struct commit_graph
*g
)
1769 num
= write_graph_chunk_base_1(f
, g
->base_graph
);
1770 hashwrite(f
, g
->oid
.hash
, the_hash_algo
->rawsz
);
1774 static int write_graph_chunk_base(struct hashfile
*f
,
1777 struct write_commit_graph_context
*ctx
= data
;
1778 int num
= write_graph_chunk_base_1(f
, ctx
->new_base_graph
);
1780 if (num
!= ctx
->num_commit_graphs_after
- 1) {
1781 error(_("failed to write correct number of base graph ids"));
1788 static int write_commit_graph_file(struct write_commit_graph_context
*ctx
)
1793 struct lock_file lk
= LOCK_INIT
;
1794 const unsigned hashsz
= the_hash_algo
->rawsz
;
1795 struct strbuf progress_title
= STRBUF_INIT
;
1796 struct chunkfile
*cf
;
1797 unsigned char file_hash
[GIT_MAX_RAWSZ
];
1800 struct strbuf tmp_file
= STRBUF_INIT
;
1802 strbuf_addf(&tmp_file
,
1803 "%s/info/commit-graphs/tmp_graph_XXXXXX",
1805 ctx
->graph_name
= strbuf_detach(&tmp_file
, NULL
);
1807 ctx
->graph_name
= get_commit_graph_filename(ctx
->odb
);
1810 if (safe_create_leading_directories(ctx
->graph_name
)) {
1811 UNLEAK(ctx
->graph_name
);
1812 error(_("unable to create leading directories of %s"),
1818 char *lock_name
= get_commit_graph_chain_filename(ctx
->odb
);
1820 hold_lock_file_for_update_mode(&lk
, lock_name
,
1821 LOCK_DIE_ON_ERROR
, 0444);
1823 fd
= git_mkstemp_mode(ctx
->graph_name
, 0444);
1825 error(_("unable to create temporary graph layer"));
1829 if (adjust_shared_perm(ctx
->graph_name
)) {
1830 error(_("unable to adjust shared permissions for '%s'"),
1835 f
= hashfd(fd
, ctx
->graph_name
);
1837 hold_lock_file_for_update_mode(&lk
, ctx
->graph_name
,
1838 LOCK_DIE_ON_ERROR
, 0444);
1839 fd
= get_lock_file_fd(&lk
);
1840 f
= hashfd(fd
, get_lock_file_path(&lk
));
1843 cf
= init_chunkfile(f
);
1845 add_chunk(cf
, GRAPH_CHUNKID_OIDFANOUT
, GRAPH_FANOUT_SIZE
,
1846 write_graph_chunk_fanout
);
1847 add_chunk(cf
, GRAPH_CHUNKID_OIDLOOKUP
, hashsz
* ctx
->commits
.nr
,
1848 write_graph_chunk_oids
);
1849 add_chunk(cf
, GRAPH_CHUNKID_DATA
, (hashsz
+ 16) * ctx
->commits
.nr
,
1850 write_graph_chunk_data
);
1852 if (ctx
->write_generation_data
)
1853 add_chunk(cf
, GRAPH_CHUNKID_GENERATION_DATA
,
1854 sizeof(uint32_t) * ctx
->commits
.nr
,
1855 write_graph_chunk_generation_data
);
1856 if (ctx
->num_generation_data_overflows
)
1857 add_chunk(cf
, GRAPH_CHUNKID_GENERATION_DATA_OVERFLOW
,
1858 sizeof(timestamp_t
) * ctx
->num_generation_data_overflows
,
1859 write_graph_chunk_generation_data_overflow
);
1860 if (ctx
->num_extra_edges
)
1861 add_chunk(cf
, GRAPH_CHUNKID_EXTRAEDGES
,
1862 4 * ctx
->num_extra_edges
,
1863 write_graph_chunk_extra_edges
);
1864 if (ctx
->changed_paths
) {
1865 add_chunk(cf
, GRAPH_CHUNKID_BLOOMINDEXES
,
1866 sizeof(uint32_t) * ctx
->commits
.nr
,
1867 write_graph_chunk_bloom_indexes
);
1868 add_chunk(cf
, GRAPH_CHUNKID_BLOOMDATA
,
1869 sizeof(uint32_t) * 3
1870 + ctx
->total_bloom_filter_data_size
,
1871 write_graph_chunk_bloom_data
);
1873 if (ctx
->num_commit_graphs_after
> 1)
1874 add_chunk(cf
, GRAPH_CHUNKID_BASE
,
1875 hashsz
* (ctx
->num_commit_graphs_after
- 1),
1876 write_graph_chunk_base
);
1878 hashwrite_be32(f
, GRAPH_SIGNATURE
);
1880 hashwrite_u8(f
, GRAPH_VERSION
);
1881 hashwrite_u8(f
, oid_version());
1882 hashwrite_u8(f
, get_num_chunks(cf
));
1883 hashwrite_u8(f
, ctx
->num_commit_graphs_after
- 1);
1885 if (ctx
->report_progress
) {
1886 strbuf_addf(&progress_title
,
1887 Q_("Writing out commit graph in %d pass",
1888 "Writing out commit graph in %d passes",
1889 get_num_chunks(cf
)),
1890 get_num_chunks(cf
));
1891 ctx
->progress
= start_delayed_progress(
1893 get_num_chunks(cf
) * ctx
->commits
.nr
);
1896 write_chunkfile(cf
, ctx
);
1898 stop_progress(&ctx
->progress
);
1899 strbuf_release(&progress_title
);
1901 if (ctx
->split
&& ctx
->base_graph_name
&& ctx
->num_commit_graphs_after
> 1) {
1902 char *new_base_hash
= xstrdup(oid_to_hex(&ctx
->new_base_graph
->oid
));
1903 char *new_base_name
= get_split_graph_filename(ctx
->new_base_graph
->odb
, new_base_hash
);
1905 free(ctx
->commit_graph_filenames_after
[ctx
->num_commit_graphs_after
- 2]);
1906 free(ctx
->commit_graph_hash_after
[ctx
->num_commit_graphs_after
- 2]);
1907 ctx
->commit_graph_filenames_after
[ctx
->num_commit_graphs_after
- 2] = new_base_name
;
1908 ctx
->commit_graph_hash_after
[ctx
->num_commit_graphs_after
- 2] = new_base_hash
;
1911 close_commit_graph(ctx
->r
->objects
);
1912 finalize_hashfile(f
, file_hash
, CSUM_HASH_IN_STREAM
| CSUM_FSYNC
);
1916 FILE *chainf
= fdopen_lock_file(&lk
, "w");
1917 char *final_graph_name
;
1923 error(_("unable to open commit-graph chain file"));
1927 if (ctx
->base_graph_name
) {
1929 int idx
= ctx
->num_commit_graphs_after
- 1;
1930 if (ctx
->num_commit_graphs_after
> 1)
1933 dest
= ctx
->commit_graph_filenames_after
[idx
];
1935 if (strcmp(ctx
->base_graph_name
, dest
)) {
1936 result
= rename(ctx
->base_graph_name
, dest
);
1939 error(_("failed to rename base commit-graph file"));
1944 char *graph_name
= get_commit_graph_filename(ctx
->odb
);
1948 ctx
->commit_graph_hash_after
[ctx
->num_commit_graphs_after
- 1] = xstrdup(hash_to_hex(file_hash
));
1949 final_graph_name
= get_split_graph_filename(ctx
->odb
,
1950 ctx
->commit_graph_hash_after
[ctx
->num_commit_graphs_after
- 1]);
1951 ctx
->commit_graph_filenames_after
[ctx
->num_commit_graphs_after
- 1] = final_graph_name
;
1953 result
= rename(ctx
->graph_name
, final_graph_name
);
1955 for (i
= 0; i
< ctx
->num_commit_graphs_after
; i
++)
1956 fprintf(get_lock_file_fp(&lk
), "%s\n", ctx
->commit_graph_hash_after
[i
]);
1959 error(_("failed to rename temporary commit-graph file"));
1964 commit_lock_file(&lk
);
1969 static void split_graph_merge_strategy(struct write_commit_graph_context
*ctx
)
1971 struct commit_graph
*g
;
1972 uint32_t num_commits
;
1973 enum commit_graph_split_flags flags
= COMMIT_GRAPH_SPLIT_UNSPECIFIED
;
1976 int max_commits
= 0;
1980 max_commits
= ctx
->opts
->max_commits
;
1982 if (ctx
->opts
->size_multiple
)
1983 size_mult
= ctx
->opts
->size_multiple
;
1985 flags
= ctx
->opts
->split_flags
;
1988 g
= ctx
->r
->objects
->commit_graph
;
1989 num_commits
= ctx
->commits
.nr
;
1990 if (flags
== COMMIT_GRAPH_SPLIT_REPLACE
)
1991 ctx
->num_commit_graphs_after
= 1;
1993 ctx
->num_commit_graphs_after
= ctx
->num_commit_graphs_before
+ 1;
1995 if (flags
!= COMMIT_GRAPH_SPLIT_MERGE_PROHIBITED
&&
1996 flags
!= COMMIT_GRAPH_SPLIT_REPLACE
) {
1997 while (g
&& (g
->num_commits
<= size_mult
* num_commits
||
1998 (max_commits
&& num_commits
> max_commits
))) {
1999 if (g
->odb
!= ctx
->odb
)
2002 num_commits
+= g
->num_commits
;
2005 ctx
->num_commit_graphs_after
--;
2009 if (flags
!= COMMIT_GRAPH_SPLIT_REPLACE
)
2010 ctx
->new_base_graph
= g
;
2011 else if (ctx
->num_commit_graphs_after
!= 1)
2012 BUG("split_graph_merge_strategy: num_commit_graphs_after "
2013 "should be 1 with --split=replace");
2015 if (ctx
->num_commit_graphs_after
== 2) {
2016 char *old_graph_name
= get_commit_graph_filename(g
->odb
);
2018 if (!strcmp(g
->filename
, old_graph_name
) &&
2019 g
->odb
!= ctx
->odb
) {
2020 ctx
->num_commit_graphs_after
= 1;
2021 ctx
->new_base_graph
= NULL
;
2024 free(old_graph_name
);
2027 CALLOC_ARRAY(ctx
->commit_graph_filenames_after
, ctx
->num_commit_graphs_after
);
2028 CALLOC_ARRAY(ctx
->commit_graph_hash_after
, ctx
->num_commit_graphs_after
);
2030 for (i
= 0; i
< ctx
->num_commit_graphs_after
&&
2031 i
< ctx
->num_commit_graphs_before
; i
++)
2032 ctx
->commit_graph_filenames_after
[i
] = xstrdup(ctx
->commit_graph_filenames_before
[i
]);
2034 i
= ctx
->num_commit_graphs_before
- 1;
2035 g
= ctx
->r
->objects
->commit_graph
;
2038 if (i
< ctx
->num_commit_graphs_after
)
2039 ctx
->commit_graph_hash_after
[i
] = xstrdup(oid_to_hex(&g
->oid
));
2042 * If the topmost remaining layer has generation data chunk, the
2043 * resultant layer also has generation data chunk.
2045 if (i
== ctx
->num_commit_graphs_after
- 2)
2046 ctx
->write_generation_data
= !!g
->chunk_generation_data
;
2053 static void merge_commit_graph(struct write_commit_graph_context
*ctx
,
2054 struct commit_graph
*g
)
2057 uint32_t offset
= g
->num_commits_in_base
;
2059 ALLOC_GROW(ctx
->commits
.list
, ctx
->commits
.nr
+ g
->num_commits
, ctx
->commits
.alloc
);
2061 for (i
= 0; i
< g
->num_commits
; i
++) {
2062 struct object_id oid
;
2063 struct commit
*result
;
2065 display_progress(ctx
->progress
, i
+ 1);
2067 load_oid_from_graph(g
, i
+ offset
, &oid
);
2069 /* only add commits if they still exist in the repo */
2070 result
= lookup_commit_reference_gently(ctx
->r
, &oid
, 1);
2073 ctx
->commits
.list
[ctx
->commits
.nr
] = result
;
2079 static int commit_compare(const void *_a
, const void *_b
)
2081 const struct commit
*a
= *(const struct commit
**)_a
;
2082 const struct commit
*b
= *(const struct commit
**)_b
;
2083 return oidcmp(&a
->object
.oid
, &b
->object
.oid
);
2086 static void sort_and_scan_merged_commits(struct write_commit_graph_context
*ctx
)
2088 uint32_t i
, dedup_i
= 0;
2090 if (ctx
->report_progress
)
2091 ctx
->progress
= start_delayed_progress(
2092 _("Scanning merged commits"),
2095 QSORT(ctx
->commits
.list
, ctx
->commits
.nr
, commit_compare
);
2097 ctx
->num_extra_edges
= 0;
2098 for (i
= 0; i
< ctx
->commits
.nr
; i
++) {
2099 display_progress(ctx
->progress
, i
);
2101 if (i
&& oideq(&ctx
->commits
.list
[i
- 1]->object
.oid
,
2102 &ctx
->commits
.list
[i
]->object
.oid
)) {
2104 * Silently ignore duplicates. These were likely
2105 * created due to a commit appearing in multiple
2106 * layers of the chain, which is unexpected but
2107 * not invalid. We should make sure there is a
2108 * unique copy in the new layer.
2111 unsigned int num_parents
;
2113 ctx
->commits
.list
[dedup_i
] = ctx
->commits
.list
[i
];
2116 num_parents
= commit_list_count(ctx
->commits
.list
[i
]->parents
);
2117 if (num_parents
> 2)
2118 ctx
->num_extra_edges
+= num_parents
- 1;
2122 ctx
->commits
.nr
= dedup_i
;
2124 stop_progress(&ctx
->progress
);
2127 static void merge_commit_graphs(struct write_commit_graph_context
*ctx
)
2129 struct commit_graph
*g
= ctx
->r
->objects
->commit_graph
;
2130 uint32_t current_graph_number
= ctx
->num_commit_graphs_before
;
2132 while (g
&& current_graph_number
>= ctx
->num_commit_graphs_after
) {
2133 current_graph_number
--;
2135 if (ctx
->report_progress
)
2136 ctx
->progress
= start_delayed_progress(_("Merging commit-graph"), 0);
2138 merge_commit_graph(ctx
, g
);
2139 stop_progress(&ctx
->progress
);
2145 ctx
->new_base_graph
= g
;
2146 ctx
->new_num_commits_in_base
= g
->num_commits
+ g
->num_commits_in_base
;
2149 if (ctx
->new_base_graph
)
2150 ctx
->base_graph_name
= xstrdup(ctx
->new_base_graph
->filename
);
2152 sort_and_scan_merged_commits(ctx
);
2155 static void mark_commit_graphs(struct write_commit_graph_context
*ctx
)
2158 time_t now
= time(NULL
);
2160 for (i
= ctx
->num_commit_graphs_after
- 1; i
< ctx
->num_commit_graphs_before
; i
++) {
2162 struct utimbuf updated_time
;
2164 stat(ctx
->commit_graph_filenames_before
[i
], &st
);
2166 updated_time
.actime
= st
.st_atime
;
2167 updated_time
.modtime
= now
;
2168 utime(ctx
->commit_graph_filenames_before
[i
], &updated_time
);
2172 static void expire_commit_graphs(struct write_commit_graph_context
*ctx
)
2174 struct strbuf path
= STRBUF_INIT
;
2178 timestamp_t expire_time
= time(NULL
);
2180 if (ctx
->opts
&& ctx
->opts
->expire_time
)
2181 expire_time
= ctx
->opts
->expire_time
;
2183 char *chain_file_name
= get_commit_graph_chain_filename(ctx
->odb
);
2184 unlink(chain_file_name
);
2185 free(chain_file_name
);
2186 ctx
->num_commit_graphs_after
= 0;
2189 strbuf_addstr(&path
, ctx
->odb
->path
);
2190 strbuf_addstr(&path
, "/info/commit-graphs");
2191 dir
= opendir(path
.buf
);
2196 strbuf_addch(&path
, '/');
2197 dirnamelen
= path
.len
;
2198 while ((de
= readdir(dir
)) != NULL
) {
2200 uint32_t i
, found
= 0;
2202 strbuf_setlen(&path
, dirnamelen
);
2203 strbuf_addstr(&path
, de
->d_name
);
2205 stat(path
.buf
, &st
);
2207 if (st
.st_mtime
> expire_time
)
2209 if (path
.len
< 6 || strcmp(path
.buf
+ path
.len
- 6, ".graph"))
2212 for (i
= 0; i
< ctx
->num_commit_graphs_after
; i
++) {
2213 if (!strcmp(ctx
->commit_graph_filenames_after
[i
],
2225 strbuf_release(&path
);
2228 int write_commit_graph(struct object_directory
*odb
,
2229 struct string_list
*pack_indexes
,
2230 struct oidset
*commits
,
2231 enum commit_graph_write_flags flags
,
2232 const struct commit_graph_opts
*opts
)
2234 struct repository
*r
= the_repository
;
2235 struct write_commit_graph_context
*ctx
;
2239 struct bloom_filter_settings bloom_settings
= DEFAULT_BLOOM_FILTER_SETTINGS
;
2240 struct topo_level_slab topo_levels
;
2242 prepare_repo_settings(r
);
2243 if (!r
->settings
.core_commit_graph
) {
2244 warning(_("attempting to write a commit-graph, but 'core.commitGraph' is disabled"));
2247 if (!commit_graph_compatible(r
))
2250 CALLOC_ARRAY(ctx
, 1);
2253 ctx
->append
= flags
& COMMIT_GRAPH_WRITE_APPEND
? 1 : 0;
2254 ctx
->report_progress
= flags
& COMMIT_GRAPH_WRITE_PROGRESS
? 1 : 0;
2255 ctx
->split
= flags
& COMMIT_GRAPH_WRITE_SPLIT
? 1 : 0;
2257 ctx
->total_bloom_filter_data_size
= 0;
2258 ctx
->write_generation_data
= (get_configured_generation_version(r
) == 2);
2259 ctx
->num_generation_data_overflows
= 0;
2261 bloom_settings
.bits_per_entry
= git_env_ulong("GIT_TEST_BLOOM_SETTINGS_BITS_PER_ENTRY",
2262 bloom_settings
.bits_per_entry
);
2263 bloom_settings
.num_hashes
= git_env_ulong("GIT_TEST_BLOOM_SETTINGS_NUM_HASHES",
2264 bloom_settings
.num_hashes
);
2265 bloom_settings
.max_changed_paths
= git_env_ulong("GIT_TEST_BLOOM_SETTINGS_MAX_CHANGED_PATHS",
2266 bloom_settings
.max_changed_paths
);
2267 ctx
->bloom_settings
= &bloom_settings
;
2269 init_topo_level_slab(&topo_levels
);
2270 ctx
->topo_levels
= &topo_levels
;
2272 prepare_commit_graph(ctx
->r
);
2273 if (ctx
->r
->objects
->commit_graph
) {
2274 struct commit_graph
*g
= ctx
->r
->objects
->commit_graph
;
2277 g
->topo_levels
= &topo_levels
;
2282 if (flags
& COMMIT_GRAPH_WRITE_BLOOM_FILTERS
)
2283 ctx
->changed_paths
= 1;
2284 if (!(flags
& COMMIT_GRAPH_NO_WRITE_BLOOM_FILTERS
)) {
2285 struct commit_graph
*g
;
2287 g
= ctx
->r
->objects
->commit_graph
;
2289 /* We have changed-paths already. Keep them in the next graph */
2290 if (g
&& g
->chunk_bloom_data
) {
2291 ctx
->changed_paths
= 1;
2292 ctx
->bloom_settings
= g
->bloom_filter_settings
;
2297 struct commit_graph
*g
= ctx
->r
->objects
->commit_graph
;
2300 ctx
->num_commit_graphs_before
++;
2304 if (ctx
->num_commit_graphs_before
) {
2305 ALLOC_ARRAY(ctx
->commit_graph_filenames_before
, ctx
->num_commit_graphs_before
);
2306 i
= ctx
->num_commit_graphs_before
;
2307 g
= ctx
->r
->objects
->commit_graph
;
2310 ctx
->commit_graph_filenames_before
[--i
] = xstrdup(g
->filename
);
2316 replace
= ctx
->opts
->split_flags
& COMMIT_GRAPH_SPLIT_REPLACE
;
2319 ctx
->approx_nr_objects
= approximate_object_count();
2321 if (ctx
->append
&& ctx
->r
->objects
->commit_graph
) {
2322 struct commit_graph
*g
= ctx
->r
->objects
->commit_graph
;
2323 for (i
= 0; i
< g
->num_commits
; i
++) {
2324 struct object_id oid
;
2325 oidread(&oid
, g
->chunk_oid_lookup
+ g
->hash_len
* i
);
2326 oid_array_append(&ctx
->oids
, &oid
);
2331 ctx
->order_by_pack
= 1;
2332 if ((res
= fill_oids_from_packs(ctx
, pack_indexes
)))
2337 if ((res
= fill_oids_from_commits(ctx
, commits
)))
2341 if (!pack_indexes
&& !commits
) {
2342 ctx
->order_by_pack
= 1;
2343 fill_oids_from_all_packs(ctx
);
2346 close_reachable(ctx
);
2348 copy_oids_to_commits(ctx
);
2350 if (ctx
->commits
.nr
>= GRAPH_EDGE_LAST_MASK
) {
2351 error(_("too many commits to write graph"));
2356 if (!ctx
->commits
.nr
&& !replace
)
2360 split_graph_merge_strategy(ctx
);
2363 merge_commit_graphs(ctx
);
2365 ctx
->num_commit_graphs_after
= 1;
2367 ctx
->trust_generation_numbers
= validate_mixed_generation_chain(ctx
->r
->objects
->commit_graph
);
2369 compute_topological_levels(ctx
);
2370 if (ctx
->write_generation_data
)
2371 compute_generation_numbers(ctx
);
2373 if (ctx
->changed_paths
)
2374 compute_bloom_filters(ctx
);
2376 res
= write_commit_graph_file(ctx
);
2379 mark_commit_graphs(ctx
);
2381 expire_commit_graphs(ctx
);
2384 free(ctx
->graph_name
);
2385 free(ctx
->commits
.list
);
2386 oid_array_clear(&ctx
->oids
);
2387 clear_topo_level_slab(&topo_levels
);
2389 if (ctx
->commit_graph_filenames_after
) {
2390 for (i
= 0; i
< ctx
->num_commit_graphs_after
; i
++) {
2391 free(ctx
->commit_graph_filenames_after
[i
]);
2392 free(ctx
->commit_graph_hash_after
[i
]);
2395 for (i
= 0; i
< ctx
->num_commit_graphs_before
; i
++)
2396 free(ctx
->commit_graph_filenames_before
[i
]);
2398 free(ctx
->commit_graph_filenames_after
);
2399 free(ctx
->commit_graph_filenames_before
);
2400 free(ctx
->commit_graph_hash_after
);
2408 #define VERIFY_COMMIT_GRAPH_ERROR_HASH 2
2409 static int verify_commit_graph_error
;
2411 __attribute__((format (printf
, 1, 2)))
2412 static void graph_report(const char *fmt
, ...)
2416 verify_commit_graph_error
= 1;
2418 vfprintf(stderr
, fmt
, ap
);
2419 fprintf(stderr
, "\n");
2423 #define GENERATION_ZERO_EXISTS 1
2424 #define GENERATION_NUMBER_EXISTS 2
2426 static int commit_graph_checksum_valid(struct commit_graph
*g
)
2428 return hashfile_checksum_valid(g
->data
, g
->data_len
);
2431 int verify_commit_graph(struct repository
*r
, struct commit_graph
*g
, int flags
)
2433 uint32_t i
, cur_fanout_pos
= 0;
2434 struct object_id prev_oid
, cur_oid
;
2435 int generation_zero
= 0;
2436 struct progress
*progress
= NULL
;
2437 int local_error
= 0;
2440 graph_report("no commit-graph file loaded");
2444 verify_commit_graph_error
= verify_commit_graph_lite(g
);
2445 if (verify_commit_graph_error
)
2446 return verify_commit_graph_error
;
2448 if (!commit_graph_checksum_valid(g
)) {
2449 graph_report(_("the commit-graph file has incorrect checksum and is likely corrupt"));
2450 verify_commit_graph_error
= VERIFY_COMMIT_GRAPH_ERROR_HASH
;
2453 for (i
= 0; i
< g
->num_commits
; i
++) {
2454 struct commit
*graph_commit
;
2456 oidread(&cur_oid
, g
->chunk_oid_lookup
+ g
->hash_len
* i
);
2458 if (i
&& oidcmp(&prev_oid
, &cur_oid
) >= 0)
2459 graph_report(_("commit-graph has incorrect OID order: %s then %s"),
2460 oid_to_hex(&prev_oid
),
2461 oid_to_hex(&cur_oid
));
2463 oidcpy(&prev_oid
, &cur_oid
);
2465 while (cur_oid
.hash
[0] > cur_fanout_pos
) {
2466 uint32_t fanout_value
= get_be32(g
->chunk_oid_fanout
+ cur_fanout_pos
);
2468 if (i
!= fanout_value
)
2469 graph_report(_("commit-graph has incorrect fanout value: fanout[%d] = %u != %u"),
2470 cur_fanout_pos
, fanout_value
, i
);
2474 graph_commit
= lookup_commit(r
, &cur_oid
);
2475 if (!parse_commit_in_graph_one(r
, g
, graph_commit
))
2476 graph_report(_("failed to parse commit %s from commit-graph"),
2477 oid_to_hex(&cur_oid
));
2480 while (cur_fanout_pos
< 256) {
2481 uint32_t fanout_value
= get_be32(g
->chunk_oid_fanout
+ cur_fanout_pos
);
2483 if (g
->num_commits
!= fanout_value
)
2484 graph_report(_("commit-graph has incorrect fanout value: fanout[%d] = %u != %u"),
2485 cur_fanout_pos
, fanout_value
, i
);
2490 if (verify_commit_graph_error
& ~VERIFY_COMMIT_GRAPH_ERROR_HASH
)
2491 return verify_commit_graph_error
;
2493 if (flags
& COMMIT_GRAPH_WRITE_PROGRESS
)
2494 progress
= start_progress(_("Verifying commits in commit graph"),
2497 for (i
= 0; i
< g
->num_commits
; i
++) {
2498 struct commit
*graph_commit
, *odb_commit
;
2499 struct commit_list
*graph_parents
, *odb_parents
;
2500 timestamp_t max_generation
= 0;
2501 timestamp_t generation
;
2503 display_progress(progress
, i
+ 1);
2504 oidread(&cur_oid
, g
->chunk_oid_lookup
+ g
->hash_len
* i
);
2506 graph_commit
= lookup_commit(r
, &cur_oid
);
2507 odb_commit
= (struct commit
*)create_object(r
, &cur_oid
, alloc_commit_node(r
));
2508 if (parse_commit_internal(odb_commit
, 0, 0)) {
2509 graph_report(_("failed to parse commit %s from object database for commit-graph"),
2510 oid_to_hex(&cur_oid
));
2514 if (!oideq(&get_commit_tree_in_graph_one(r
, g
, graph_commit
)->object
.oid
,
2515 get_commit_tree_oid(odb_commit
)))
2516 graph_report(_("root tree OID for commit %s in commit-graph is %s != %s"),
2517 oid_to_hex(&cur_oid
),
2518 oid_to_hex(get_commit_tree_oid(graph_commit
)),
2519 oid_to_hex(get_commit_tree_oid(odb_commit
)));
2521 graph_parents
= graph_commit
->parents
;
2522 odb_parents
= odb_commit
->parents
;
2524 while (graph_parents
) {
2525 if (odb_parents
== NULL
) {
2526 graph_report(_("commit-graph parent list for commit %s is too long"),
2527 oid_to_hex(&cur_oid
));
2531 /* parse parent in case it is in a base graph */
2532 parse_commit_in_graph_one(r
, g
, graph_parents
->item
);
2534 if (!oideq(&graph_parents
->item
->object
.oid
, &odb_parents
->item
->object
.oid
))
2535 graph_report(_("commit-graph parent for %s is %s != %s"),
2536 oid_to_hex(&cur_oid
),
2537 oid_to_hex(&graph_parents
->item
->object
.oid
),
2538 oid_to_hex(&odb_parents
->item
->object
.oid
));
2540 generation
= commit_graph_generation(graph_parents
->item
);
2541 if (generation
> max_generation
)
2542 max_generation
= generation
;
2544 graph_parents
= graph_parents
->next
;
2545 odb_parents
= odb_parents
->next
;
2548 if (odb_parents
!= NULL
)
2549 graph_report(_("commit-graph parent list for commit %s terminates early"),
2550 oid_to_hex(&cur_oid
));
2552 if (!commit_graph_generation(graph_commit
)) {
2553 if (generation_zero
== GENERATION_NUMBER_EXISTS
)
2554 graph_report(_("commit-graph has generation number zero for commit %s, but non-zero elsewhere"),
2555 oid_to_hex(&cur_oid
));
2556 generation_zero
= GENERATION_ZERO_EXISTS
;
2557 } else if (generation_zero
== GENERATION_ZERO_EXISTS
)
2558 graph_report(_("commit-graph has non-zero generation number for commit %s, but zero elsewhere"),
2559 oid_to_hex(&cur_oid
));
2561 if (generation_zero
== GENERATION_ZERO_EXISTS
)
2565 * If we are using topological level and one of our parents has
2566 * generation GENERATION_NUMBER_V1_MAX, then our generation is
2567 * also GENERATION_NUMBER_V1_MAX. Decrement to avoid extra logic
2568 * in the following condition.
2570 if (!g
->read_generation_data
&& max_generation
== GENERATION_NUMBER_V1_MAX
)
2573 generation
= commit_graph_generation(graph_commit
);
2574 if (generation
< max_generation
+ 1)
2575 graph_report(_("commit-graph generation for commit %s is %"PRItime
" < %"PRItime
),
2576 oid_to_hex(&cur_oid
),
2578 max_generation
+ 1);
2580 if (graph_commit
->date
!= odb_commit
->date
)
2581 graph_report(_("commit date for commit %s in commit-graph is %"PRItime
" != %"PRItime
),
2582 oid_to_hex(&cur_oid
),
2586 stop_progress(&progress
);
2588 local_error
= verify_commit_graph_error
;
2590 if (!(flags
& COMMIT_GRAPH_VERIFY_SHALLOW
) && g
->base_graph
)
2591 local_error
|= verify_commit_graph(r
, g
->base_graph
, flags
);
2596 void free_commit_graph(struct commit_graph
*g
)
2601 munmap((void *)g
->data
, g
->data_len
);
2605 free(g
->bloom_filter_settings
);
2609 void disable_commit_graph(struct repository
*r
)
2611 r
->commit_graph_disabled
= 1;