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"
23 void git_test_write_commit_graph_or_die(void)
26 if (!git_env_bool(GIT_TEST_COMMIT_GRAPH
, 0))
29 if (git_env_bool(GIT_TEST_COMMIT_GRAPH_CHANGED_PATHS
, 0))
30 flags
= COMMIT_GRAPH_WRITE_BLOOM_FILTERS
;
32 if (write_commit_graph_reachable(the_repository
->objects
->odb
,
34 die("failed to write commit-graph under GIT_TEST_COMMIT_GRAPH");
37 #define GRAPH_SIGNATURE 0x43475048 /* "CGPH" */
38 #define GRAPH_CHUNKID_OIDFANOUT 0x4f494446 /* "OIDF" */
39 #define GRAPH_CHUNKID_OIDLOOKUP 0x4f49444c /* "OIDL" */
40 #define GRAPH_CHUNKID_DATA 0x43444154 /* "CDAT" */
41 #define GRAPH_CHUNKID_EXTRAEDGES 0x45444745 /* "EDGE" */
42 #define GRAPH_CHUNKID_BLOOMINDEXES 0x42494458 /* "BIDX" */
43 #define GRAPH_CHUNKID_BLOOMDATA 0x42444154 /* "BDAT" */
44 #define GRAPH_CHUNKID_BASE 0x42415345 /* "BASE" */
45 #define MAX_NUM_CHUNKS 7
47 #define GRAPH_DATA_WIDTH (the_hash_algo->rawsz + 16)
49 #define GRAPH_VERSION_1 0x1
50 #define GRAPH_VERSION GRAPH_VERSION_1
52 #define GRAPH_EXTRA_EDGES_NEEDED 0x80000000
53 #define GRAPH_EDGE_LAST_MASK 0x7fffffff
54 #define GRAPH_PARENT_NONE 0x70000000
56 #define GRAPH_LAST_EDGE 0x80000000
58 #define GRAPH_HEADER_SIZE 8
59 #define GRAPH_FANOUT_SIZE (4 * 256)
60 #define GRAPH_CHUNKLOOKUP_WIDTH 12
61 #define GRAPH_MIN_SIZE (GRAPH_HEADER_SIZE + 4 * GRAPH_CHUNKLOOKUP_WIDTH \
62 + GRAPH_FANOUT_SIZE + the_hash_algo->rawsz)
64 /* Remember to update object flag allocation in object.h */
65 #define REACHABLE (1u<<15)
67 /* Keep track of the order in which commits are added to our list. */
68 define_commit_slab(commit_pos
, int);
69 static struct commit_pos commit_pos
= COMMIT_SLAB_INIT(1, commit_pos
);
71 static void set_commit_pos(struct repository
*r
, const struct object_id
*oid
)
73 static int32_t max_pos
;
74 struct commit
*commit
= lookup_commit(r
, oid
);
77 return; /* should never happen, but be lenient */
79 *commit_pos_at(&commit_pos
, commit
) = max_pos
++;
82 static int commit_pos_cmp(const void *va
, const void *vb
)
84 const struct commit
*a
= *(const struct commit
**)va
;
85 const struct commit
*b
= *(const struct commit
**)vb
;
86 return commit_pos_at(&commit_pos
, a
) -
87 commit_pos_at(&commit_pos
, b
);
90 define_commit_slab(commit_graph_data_slab
, struct commit_graph_data
);
91 static struct commit_graph_data_slab commit_graph_data_slab
=
92 COMMIT_SLAB_INIT(1, commit_graph_data_slab
);
94 uint32_t commit_graph_position(const struct commit
*c
)
96 struct commit_graph_data
*data
=
97 commit_graph_data_slab_peek(&commit_graph_data_slab
, c
);
99 return data
? data
->graph_pos
: COMMIT_NOT_FROM_GRAPH
;
102 uint32_t commit_graph_generation(const struct commit
*c
)
104 struct commit_graph_data
*data
=
105 commit_graph_data_slab_peek(&commit_graph_data_slab
, c
);
108 return GENERATION_NUMBER_INFINITY
;
109 else if (data
->graph_pos
== COMMIT_NOT_FROM_GRAPH
)
110 return GENERATION_NUMBER_INFINITY
;
112 return data
->generation
;
115 static struct commit_graph_data
*commit_graph_data_at(const struct commit
*c
)
117 unsigned int i
, nth_slab
;
118 struct commit_graph_data
*data
=
119 commit_graph_data_slab_peek(&commit_graph_data_slab
, c
);
124 nth_slab
= c
->index
/ commit_graph_data_slab
.slab_size
;
125 data
= commit_graph_data_slab_at(&commit_graph_data_slab
, c
);
128 * commit-slab initializes elements with zero, overwrite this with
129 * COMMIT_NOT_FROM_GRAPH for graph_pos.
131 * We avoid initializing generation with checking if graph position
132 * is not COMMIT_NOT_FROM_GRAPH.
134 for (i
= 0; i
< commit_graph_data_slab
.slab_size
; i
++) {
135 commit_graph_data_slab
.slab
[nth_slab
][i
].graph_pos
=
136 COMMIT_NOT_FROM_GRAPH
;
142 static int commit_gen_cmp(const void *va
, const void *vb
)
144 const struct commit
*a
= *(const struct commit
**)va
;
145 const struct commit
*b
= *(const struct commit
**)vb
;
147 uint32_t generation_a
= commit_graph_generation(a
);
148 uint32_t generation_b
= commit_graph_generation(b
);
149 /* lower generation commits first */
150 if (generation_a
< generation_b
)
152 else if (generation_a
> generation_b
)
155 /* use date as a heuristic when generations are equal */
156 if (a
->date
< b
->date
)
158 else if (a
->date
> b
->date
)
163 char *get_commit_graph_filename(struct object_directory
*obj_dir
)
165 return xstrfmt("%s/info/commit-graph", obj_dir
->path
);
168 static char *get_split_graph_filename(struct object_directory
*odb
,
171 return xstrfmt("%s/info/commit-graphs/graph-%s.graph", odb
->path
,
175 char *get_commit_graph_chain_filename(struct object_directory
*odb
)
177 return xstrfmt("%s/info/commit-graphs/commit-graph-chain", odb
->path
);
180 static uint8_t oid_version(void)
182 switch (hash_algo_by_ptr(the_hash_algo
)) {
185 case GIT_HASH_SHA256
:
188 die(_("invalid hash version"));
192 static struct commit_graph
*alloc_commit_graph(void)
194 struct commit_graph
*g
= xcalloc(1, sizeof(*g
));
199 extern int read_replace_refs
;
201 static int commit_graph_compatible(struct repository
*r
)
206 if (read_replace_refs
) {
207 prepare_replace_object(r
);
208 if (hashmap_get_size(&r
->objects
->replace_map
->map
))
212 prepare_commit_graft(r
);
213 if (r
->parsed_objects
&&
214 (r
->parsed_objects
->grafts_nr
|| r
->parsed_objects
->substituted_parent
))
216 if (is_repository_shallow(r
))
222 int open_commit_graph(const char *graph_file
, int *fd
, struct stat
*st
)
224 *fd
= git_open(graph_file
);
227 if (fstat(*fd
, st
)) {
234 struct commit_graph
*load_commit_graph_one_fd_st(struct repository
*r
,
235 int fd
, struct stat
*st
,
236 struct object_directory
*odb
)
240 struct commit_graph
*ret
;
242 graph_size
= xsize_t(st
->st_size
);
244 if (graph_size
< GRAPH_MIN_SIZE
) {
246 error(_("commit-graph file is too small"));
249 graph_map
= xmmap(NULL
, graph_size
, PROT_READ
, MAP_PRIVATE
, fd
, 0);
251 ret
= parse_commit_graph(r
, graph_map
, graph_size
);
256 munmap(graph_map
, graph_size
);
261 static int verify_commit_graph_lite(struct commit_graph
*g
)
264 * Basic validation shared between parse_commit_graph()
265 * which'll be called every time the graph is used, and the
266 * much more expensive verify_commit_graph() used by
267 * "commit-graph verify".
269 * There should only be very basic checks here to ensure that
270 * we don't e.g. segfault in fill_commit_in_graph(), but
271 * because this is a very hot codepath nothing that e.g. loops
272 * over g->num_commits, or runs a checksum on the commit-graph
275 if (!g
->chunk_oid_fanout
) {
276 error("commit-graph is missing the OID Fanout chunk");
279 if (!g
->chunk_oid_lookup
) {
280 error("commit-graph is missing the OID Lookup chunk");
283 if (!g
->chunk_commit_data
) {
284 error("commit-graph is missing the Commit Data chunk");
291 struct commit_graph
*parse_commit_graph(struct repository
*r
,
292 void *graph_map
, size_t graph_size
)
294 const unsigned char *data
, *chunk_lookup
;
296 struct commit_graph
*graph
;
297 uint64_t next_chunk_offset
;
298 uint32_t graph_signature
;
299 unsigned char graph_version
, hash_version
;
304 if (graph_size
< GRAPH_MIN_SIZE
)
307 data
= (const unsigned char *)graph_map
;
309 graph_signature
= get_be32(data
);
310 if (graph_signature
!= GRAPH_SIGNATURE
) {
311 error(_("commit-graph signature %X does not match signature %X"),
312 graph_signature
, GRAPH_SIGNATURE
);
316 graph_version
= *(unsigned char*)(data
+ 4);
317 if (graph_version
!= GRAPH_VERSION
) {
318 error(_("commit-graph version %X does not match version %X"),
319 graph_version
, GRAPH_VERSION
);
323 hash_version
= *(unsigned char*)(data
+ 5);
324 if (hash_version
!= oid_version()) {
325 error(_("commit-graph hash version %X does not match version %X"),
326 hash_version
, oid_version());
330 prepare_repo_settings(r
);
332 graph
= alloc_commit_graph();
334 graph
->hash_len
= the_hash_algo
->rawsz
;
335 graph
->num_chunks
= *(unsigned char*)(data
+ 6);
336 graph
->data
= graph_map
;
337 graph
->data_len
= graph_size
;
339 if (graph_size
< GRAPH_HEADER_SIZE
+
340 (graph
->num_chunks
+ 1) * GRAPH_CHUNKLOOKUP_WIDTH
+
341 GRAPH_FANOUT_SIZE
+ the_hash_algo
->rawsz
) {
342 error(_("commit-graph file is too small to hold %u chunks"),
348 chunk_lookup
= data
+ 8;
349 next_chunk_offset
= get_be64(chunk_lookup
+ 4);
350 for (i
= 0; i
< graph
->num_chunks
; i
++) {
352 uint64_t chunk_offset
= next_chunk_offset
;
353 int chunk_repeated
= 0;
355 chunk_id
= get_be32(chunk_lookup
+ 0);
357 chunk_lookup
+= GRAPH_CHUNKLOOKUP_WIDTH
;
358 next_chunk_offset
= get_be64(chunk_lookup
+ 4);
360 if (chunk_offset
> graph_size
- the_hash_algo
->rawsz
) {
361 error(_("commit-graph improper chunk offset %08x%08x"), (uint32_t)(chunk_offset
>> 32),
362 (uint32_t)chunk_offset
);
363 goto free_and_return
;
367 case GRAPH_CHUNKID_OIDFANOUT
:
368 if (graph
->chunk_oid_fanout
)
371 graph
->chunk_oid_fanout
= (uint32_t*)(data
+ chunk_offset
);
374 case GRAPH_CHUNKID_OIDLOOKUP
:
375 if (graph
->chunk_oid_lookup
)
378 graph
->chunk_oid_lookup
= data
+ chunk_offset
;
379 graph
->num_commits
= (next_chunk_offset
- chunk_offset
)
384 case GRAPH_CHUNKID_DATA
:
385 if (graph
->chunk_commit_data
)
388 graph
->chunk_commit_data
= data
+ chunk_offset
;
391 case GRAPH_CHUNKID_EXTRAEDGES
:
392 if (graph
->chunk_extra_edges
)
395 graph
->chunk_extra_edges
= data
+ chunk_offset
;
398 case GRAPH_CHUNKID_BASE
:
399 if (graph
->chunk_base_graphs
)
402 graph
->chunk_base_graphs
= data
+ chunk_offset
;
405 case GRAPH_CHUNKID_BLOOMINDEXES
:
406 if (graph
->chunk_bloom_indexes
)
408 else if (r
->settings
.commit_graph_read_changed_paths
)
409 graph
->chunk_bloom_indexes
= data
+ chunk_offset
;
412 case GRAPH_CHUNKID_BLOOMDATA
:
413 if (graph
->chunk_bloom_data
)
415 else if (r
->settings
.commit_graph_read_changed_paths
) {
416 uint32_t hash_version
;
417 graph
->chunk_bloom_data
= data
+ chunk_offset
;
418 hash_version
= get_be32(data
+ chunk_offset
);
420 if (hash_version
!= 1)
423 graph
->bloom_filter_settings
= xmalloc(sizeof(struct bloom_filter_settings
));
424 graph
->bloom_filter_settings
->hash_version
= hash_version
;
425 graph
->bloom_filter_settings
->num_hashes
= get_be32(data
+ chunk_offset
+ 4);
426 graph
->bloom_filter_settings
->bits_per_entry
= get_be32(data
+ chunk_offset
+ 8);
427 graph
->bloom_filter_settings
->max_changed_paths
= DEFAULT_BLOOM_MAX_CHANGES
;
432 if (chunk_repeated
) {
433 error(_("commit-graph chunk id %08x appears multiple times"), chunk_id
);
434 goto free_and_return
;
438 if (graph
->chunk_bloom_indexes
&& graph
->chunk_bloom_data
) {
439 init_bloom_filters();
441 /* We need both the bloom chunks to exist together. Else ignore the data */
442 graph
->chunk_bloom_indexes
= NULL
;
443 graph
->chunk_bloom_data
= NULL
;
444 FREE_AND_NULL(graph
->bloom_filter_settings
);
447 hashcpy(graph
->oid
.hash
, graph
->data
+ graph
->data_len
- graph
->hash_len
);
449 if (verify_commit_graph_lite(graph
))
450 goto free_and_return
;
455 free(graph
->bloom_filter_settings
);
460 static struct commit_graph
*load_commit_graph_one(struct repository
*r
,
461 const char *graph_file
,
462 struct object_directory
*odb
)
467 struct commit_graph
*g
;
468 int open_ok
= open_commit_graph(graph_file
, &fd
, &st
);
473 g
= load_commit_graph_one_fd_st(r
, fd
, &st
, odb
);
476 g
->filename
= xstrdup(graph_file
);
481 static struct commit_graph
*load_commit_graph_v1(struct repository
*r
,
482 struct object_directory
*odb
)
484 char *graph_name
= get_commit_graph_filename(odb
);
485 struct commit_graph
*g
= load_commit_graph_one(r
, graph_name
, odb
);
491 static int add_graph_to_chain(struct commit_graph
*g
,
492 struct commit_graph
*chain
,
493 struct object_id
*oids
,
496 struct commit_graph
*cur_g
= chain
;
498 if (n
&& !g
->chunk_base_graphs
) {
499 warning(_("commit-graph has no base graphs chunk"));
507 !oideq(&oids
[n
], &cur_g
->oid
) ||
508 !hasheq(oids
[n
].hash
, g
->chunk_base_graphs
+ g
->hash_len
* n
)) {
509 warning(_("commit-graph chain does not match"));
513 cur_g
= cur_g
->base_graph
;
516 g
->base_graph
= chain
;
519 g
->num_commits_in_base
= chain
->num_commits
+ chain
->num_commits_in_base
;
524 static struct commit_graph
*load_commit_graph_chain(struct repository
*r
,
525 struct object_directory
*odb
)
527 struct commit_graph
*graph_chain
= NULL
;
528 struct strbuf line
= STRBUF_INIT
;
530 struct object_id
*oids
;
531 int i
= 0, valid
= 1, count
;
532 char *chain_name
= get_commit_graph_chain_filename(odb
);
536 fp
= fopen(chain_name
, "r");
537 stat_res
= stat(chain_name
, &st
);
542 st
.st_size
<= the_hash_algo
->hexsz
)
545 count
= st
.st_size
/ (the_hash_algo
->hexsz
+ 1);
546 oids
= xcalloc(count
, sizeof(struct object_id
));
550 for (i
= 0; i
< count
; i
++) {
551 struct object_directory
*odb
;
553 if (strbuf_getline_lf(&line
, fp
) == EOF
)
556 if (get_oid_hex(line
.buf
, &oids
[i
])) {
557 warning(_("invalid commit-graph chain: line '%s' not a hash"),
564 for (odb
= r
->objects
->odb
; odb
; odb
= odb
->next
) {
565 char *graph_name
= get_split_graph_filename(odb
, line
.buf
);
566 struct commit_graph
*g
= load_commit_graph_one(r
, graph_name
, odb
);
571 if (add_graph_to_chain(g
, graph_chain
, oids
, i
)) {
581 warning(_("unable to find all commit-graph files"));
588 strbuf_release(&line
);
593 struct commit_graph
*read_commit_graph_one(struct repository
*r
,
594 struct object_directory
*odb
)
596 struct commit_graph
*g
= load_commit_graph_v1(r
, odb
);
599 g
= load_commit_graph_chain(r
, odb
);
604 static void prepare_commit_graph_one(struct repository
*r
,
605 struct object_directory
*odb
)
608 if (r
->objects
->commit_graph
)
611 r
->objects
->commit_graph
= read_commit_graph_one(r
, odb
);
615 * Return 1 if commit_graph is non-NULL, and 0 otherwise.
617 * On the first invocation, this function attempts to load the commit
618 * graph if the_repository is configured to have one.
620 static int prepare_commit_graph(struct repository
*r
)
622 struct object_directory
*odb
;
625 * This must come before the "already attempted?" check below, because
626 * we want to disable even an already-loaded graph file.
628 if (r
->commit_graph_disabled
)
631 if (r
->objects
->commit_graph_attempted
)
632 return !!r
->objects
->commit_graph
;
633 r
->objects
->commit_graph_attempted
= 1;
635 prepare_repo_settings(r
);
637 if (!git_env_bool(GIT_TEST_COMMIT_GRAPH
, 0) &&
638 r
->settings
.core_commit_graph
!= 1)
640 * This repository is not configured to use commit graphs, so
641 * do not load one. (But report commit_graph_attempted anyway
642 * so that commit graph loading is not attempted again for this
647 if (!commit_graph_compatible(r
))
651 for (odb
= r
->objects
->odb
;
652 !r
->objects
->commit_graph
&& odb
;
654 prepare_commit_graph_one(r
, odb
);
655 return !!r
->objects
->commit_graph
;
658 int generation_numbers_enabled(struct repository
*r
)
660 uint32_t first_generation
;
661 struct commit_graph
*g
;
662 if (!prepare_commit_graph(r
))
665 g
= r
->objects
->commit_graph
;
670 first_generation
= get_be32(g
->chunk_commit_data
+
671 g
->hash_len
+ 8) >> 2;
673 return !!first_generation
;
676 struct bloom_filter_settings
*get_bloom_filter_settings(struct repository
*r
)
678 struct commit_graph
*g
= r
->objects
->commit_graph
;
680 if (g
->bloom_filter_settings
)
681 return g
->bloom_filter_settings
;
687 static void close_commit_graph_one(struct commit_graph
*g
)
692 close_commit_graph_one(g
->base_graph
);
693 free_commit_graph(g
);
696 void close_commit_graph(struct raw_object_store
*o
)
698 close_commit_graph_one(o
->commit_graph
);
699 o
->commit_graph
= NULL
;
702 static int bsearch_graph(struct commit_graph
*g
, struct object_id
*oid
, uint32_t *pos
)
704 return bsearch_hash(oid
->hash
, g
->chunk_oid_fanout
,
705 g
->chunk_oid_lookup
, g
->hash_len
, pos
);
708 static void load_oid_from_graph(struct commit_graph
*g
,
710 struct object_id
*oid
)
714 while (g
&& pos
< g
->num_commits_in_base
)
718 BUG("NULL commit-graph");
720 if (pos
>= g
->num_commits
+ g
->num_commits_in_base
)
721 die(_("invalid commit position. commit-graph is likely corrupt"));
723 lex_index
= pos
- g
->num_commits_in_base
;
725 hashcpy(oid
->hash
, g
->chunk_oid_lookup
+ g
->hash_len
* lex_index
);
728 static struct commit_list
**insert_parent_or_die(struct repository
*r
,
729 struct commit_graph
*g
,
731 struct commit_list
**pptr
)
734 struct object_id oid
;
736 if (pos
>= g
->num_commits
+ g
->num_commits_in_base
)
737 die("invalid parent position %"PRIu32
, pos
);
739 load_oid_from_graph(g
, pos
, &oid
);
740 c
= lookup_commit(r
, &oid
);
742 die(_("could not find commit %s"), oid_to_hex(&oid
));
743 commit_graph_data_at(c
)->graph_pos
= pos
;
744 return &commit_list_insert(c
, pptr
)->next
;
747 static void fill_commit_graph_info(struct commit
*item
, struct commit_graph
*g
, uint32_t pos
)
749 const unsigned char *commit_data
;
750 struct commit_graph_data
*graph_data
;
753 while (pos
< g
->num_commits_in_base
)
756 lex_index
= pos
- g
->num_commits_in_base
;
757 commit_data
= g
->chunk_commit_data
+ GRAPH_DATA_WIDTH
* lex_index
;
759 graph_data
= commit_graph_data_at(item
);
760 graph_data
->graph_pos
= pos
;
761 graph_data
->generation
= get_be32(commit_data
+ g
->hash_len
+ 8) >> 2;
764 static inline void set_commit_tree(struct commit
*c
, struct tree
*t
)
769 static int fill_commit_in_graph(struct repository
*r
,
771 struct commit_graph
*g
, uint32_t pos
)
774 uint32_t *parent_data_ptr
;
775 uint64_t date_low
, date_high
;
776 struct commit_list
**pptr
;
777 struct commit_graph_data
*graph_data
;
778 const unsigned char *commit_data
;
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"));
788 * Store the "full" position, but then use the
789 * "local" position for the rest of the calculation.
791 graph_data
= commit_graph_data_at(item
);
792 graph_data
->graph_pos
= pos
;
793 lex_index
= pos
- g
->num_commits_in_base
;
795 commit_data
= g
->chunk_commit_data
+ (g
->hash_len
+ 16) * lex_index
;
797 item
->object
.parsed
= 1;
799 set_commit_tree(item
, NULL
);
801 date_high
= get_be32(commit_data
+ g
->hash_len
+ 8) & 0x3;
802 date_low
= get_be32(commit_data
+ g
->hash_len
+ 12);
803 item
->date
= (timestamp_t
)((date_high
<< 32) | date_low
);
805 graph_data
->generation
= get_be32(commit_data
+ g
->hash_len
+ 8) >> 2;
807 pptr
= &item
->parents
;
809 edge_value
= get_be32(commit_data
+ g
->hash_len
);
810 if (edge_value
== GRAPH_PARENT_NONE
)
812 pptr
= insert_parent_or_die(r
, g
, edge_value
, pptr
);
814 edge_value
= get_be32(commit_data
+ g
->hash_len
+ 4);
815 if (edge_value
== GRAPH_PARENT_NONE
)
817 if (!(edge_value
& GRAPH_EXTRA_EDGES_NEEDED
)) {
818 pptr
= insert_parent_or_die(r
, g
, edge_value
, pptr
);
822 parent_data_ptr
= (uint32_t*)(g
->chunk_extra_edges
+
823 4 * (uint64_t)(edge_value
& GRAPH_EDGE_LAST_MASK
));
825 edge_value
= get_be32(parent_data_ptr
);
826 pptr
= insert_parent_or_die(r
, g
,
827 edge_value
& GRAPH_EDGE_LAST_MASK
,
830 } while (!(edge_value
& GRAPH_LAST_EDGE
));
835 static int find_commit_in_graph(struct commit
*item
, struct commit_graph
*g
, uint32_t *pos
)
837 uint32_t graph_pos
= commit_graph_position(item
);
838 if (graph_pos
!= COMMIT_NOT_FROM_GRAPH
) {
842 struct commit_graph
*cur_g
= g
;
845 while (cur_g
&& !bsearch_graph(cur_g
, &(item
->object
.oid
), &lex_index
))
846 cur_g
= cur_g
->base_graph
;
849 *pos
= lex_index
+ cur_g
->num_commits_in_base
;
857 static int parse_commit_in_graph_one(struct repository
*r
,
858 struct commit_graph
*g
,
863 if (item
->object
.parsed
)
866 if (find_commit_in_graph(item
, g
, &pos
))
867 return fill_commit_in_graph(r
, item
, g
, pos
);
872 int parse_commit_in_graph(struct repository
*r
, struct commit
*item
)
874 static int checked_env
= 0;
877 git_env_bool(GIT_TEST_COMMIT_GRAPH_DIE_ON_PARSE
, 0))
878 die("dying as requested by the '%s' variable on commit-graph parse!",
879 GIT_TEST_COMMIT_GRAPH_DIE_ON_PARSE
);
882 if (!prepare_commit_graph(r
))
884 return parse_commit_in_graph_one(r
, r
->objects
->commit_graph
, item
);
887 void load_commit_graph_info(struct repository
*r
, struct commit
*item
)
890 if (!prepare_commit_graph(r
))
892 if (find_commit_in_graph(item
, r
->objects
->commit_graph
, &pos
))
893 fill_commit_graph_info(item
, r
->objects
->commit_graph
, pos
);
896 static struct tree
*load_tree_for_commit(struct repository
*r
,
897 struct commit_graph
*g
,
900 struct object_id oid
;
901 const unsigned char *commit_data
;
902 uint32_t graph_pos
= commit_graph_position(c
);
904 while (graph_pos
< g
->num_commits_in_base
)
907 commit_data
= g
->chunk_commit_data
+
908 GRAPH_DATA_WIDTH
* (graph_pos
- g
->num_commits_in_base
);
910 hashcpy(oid
.hash
, commit_data
);
911 set_commit_tree(c
, lookup_tree(r
, &oid
));
913 return c
->maybe_tree
;
916 static struct tree
*get_commit_tree_in_graph_one(struct repository
*r
,
917 struct commit_graph
*g
,
918 const struct commit
*c
)
921 return c
->maybe_tree
;
922 if (commit_graph_position(c
) == COMMIT_NOT_FROM_GRAPH
)
923 BUG("get_commit_tree_in_graph_one called from non-commit-graph commit");
925 return load_tree_for_commit(r
, g
, (struct commit
*)c
);
928 struct tree
*get_commit_tree_in_graph(struct repository
*r
, const struct commit
*c
)
930 return get_commit_tree_in_graph_one(r
, r
->objects
->commit_graph
, c
);
933 struct packed_commit_list
{
934 struct commit
**list
;
939 struct write_commit_graph_context
{
940 struct repository
*r
;
941 struct object_directory
*odb
;
943 struct oid_array oids
;
944 struct packed_commit_list commits
;
946 unsigned long approx_nr_objects
;
947 struct progress
*progress
;
949 uint64_t progress_cnt
;
951 char *base_graph_name
;
952 int num_commit_graphs_before
;
953 int num_commit_graphs_after
;
954 char **commit_graph_filenames_before
;
955 char **commit_graph_filenames_after
;
956 char **commit_graph_hash_after
;
957 uint32_t new_num_commits_in_base
;
958 struct commit_graph
*new_base_graph
;
966 const struct commit_graph_opts
*opts
;
967 size_t total_bloom_filter_data_size
;
968 const struct bloom_filter_settings
*bloom_settings
;
970 int count_bloom_filter_computed
;
971 int count_bloom_filter_not_computed
;
972 int count_bloom_filter_trunc_empty
;
973 int count_bloom_filter_trunc_large
;
976 static int write_graph_chunk_fanout(struct hashfile
*f
,
977 struct write_commit_graph_context
*ctx
)
980 struct commit
**list
= ctx
->commits
.list
;
983 * Write the first-level table (the list is sorted,
984 * but we use a 256-entry lookup to be able to avoid
985 * having to do eight extra binary search iterations).
987 for (i
= 0; i
< 256; i
++) {
988 while (count
< ctx
->commits
.nr
) {
989 if ((*list
)->object
.oid
.hash
[0] != i
)
991 display_progress(ctx
->progress
, ++ctx
->progress_cnt
);
996 hashwrite_be32(f
, count
);
1002 static int write_graph_chunk_oids(struct hashfile
*f
,
1003 struct write_commit_graph_context
*ctx
)
1005 struct commit
**list
= ctx
->commits
.list
;
1007 for (count
= 0; count
< ctx
->commits
.nr
; count
++, list
++) {
1008 display_progress(ctx
->progress
, ++ctx
->progress_cnt
);
1009 hashwrite(f
, (*list
)->object
.oid
.hash
, the_hash_algo
->rawsz
);
1015 static const unsigned char *commit_to_sha1(size_t index
, void *table
)
1017 struct commit
**commits
= table
;
1018 return commits
[index
]->object
.oid
.hash
;
1021 static int write_graph_chunk_data(struct hashfile
*f
,
1022 struct write_commit_graph_context
*ctx
)
1024 struct commit
**list
= ctx
->commits
.list
;
1025 struct commit
**last
= ctx
->commits
.list
+ ctx
->commits
.nr
;
1026 uint32_t num_extra_edges
= 0;
1028 while (list
< last
) {
1029 struct commit_list
*parent
;
1030 struct object_id
*tree
;
1032 uint32_t packedDate
[2];
1033 display_progress(ctx
->progress
, ++ctx
->progress_cnt
);
1035 if (parse_commit_no_graph(*list
))
1036 die(_("unable to parse commit %s"),
1037 oid_to_hex(&(*list
)->object
.oid
));
1038 tree
= get_commit_tree_oid(*list
);
1039 hashwrite(f
, tree
->hash
, the_hash_algo
->rawsz
);
1041 parent
= (*list
)->parents
;
1044 edge_value
= GRAPH_PARENT_NONE
;
1046 edge_value
= hash_pos(parent
->item
->object
.oid
.hash
,
1051 if (edge_value
>= 0)
1052 edge_value
+= ctx
->new_num_commits_in_base
;
1053 else if (ctx
->new_base_graph
) {
1055 if (find_commit_in_graph(parent
->item
,
1056 ctx
->new_base_graph
,
1062 BUG("missing parent %s for commit %s",
1063 oid_to_hex(&parent
->item
->object
.oid
),
1064 oid_to_hex(&(*list
)->object
.oid
));
1067 hashwrite_be32(f
, edge_value
);
1070 parent
= parent
->next
;
1073 edge_value
= GRAPH_PARENT_NONE
;
1074 else if (parent
->next
)
1075 edge_value
= GRAPH_EXTRA_EDGES_NEEDED
| num_extra_edges
;
1077 edge_value
= hash_pos(parent
->item
->object
.oid
.hash
,
1082 if (edge_value
>= 0)
1083 edge_value
+= ctx
->new_num_commits_in_base
;
1084 else if (ctx
->new_base_graph
) {
1086 if (find_commit_in_graph(parent
->item
,
1087 ctx
->new_base_graph
,
1093 BUG("missing parent %s for commit %s",
1094 oid_to_hex(&parent
->item
->object
.oid
),
1095 oid_to_hex(&(*list
)->object
.oid
));
1098 hashwrite_be32(f
, edge_value
);
1100 if (edge_value
& GRAPH_EXTRA_EDGES_NEEDED
) {
1103 parent
= parent
->next
;
1107 if (sizeof((*list
)->date
) > 4)
1108 packedDate
[0] = htonl(((*list
)->date
>> 32) & 0x3);
1112 packedDate
[0] |= htonl(commit_graph_data_at(*list
)->generation
<< 2);
1114 packedDate
[1] = htonl((*list
)->date
);
1115 hashwrite(f
, packedDate
, 8);
1123 static int write_graph_chunk_extra_edges(struct hashfile
*f
,
1124 struct write_commit_graph_context
*ctx
)
1126 struct commit
**list
= ctx
->commits
.list
;
1127 struct commit
**last
= ctx
->commits
.list
+ ctx
->commits
.nr
;
1128 struct commit_list
*parent
;
1130 while (list
< last
) {
1131 int num_parents
= 0;
1133 display_progress(ctx
->progress
, ++ctx
->progress_cnt
);
1135 for (parent
= (*list
)->parents
; num_parents
< 3 && parent
;
1136 parent
= parent
->next
)
1139 if (num_parents
<= 2) {
1144 /* Since num_parents > 2, this initializer is safe. */
1145 for (parent
= (*list
)->parents
->next
; parent
; parent
= parent
->next
) {
1146 int edge_value
= hash_pos(parent
->item
->object
.oid
.hash
,
1151 if (edge_value
>= 0)
1152 edge_value
+= ctx
->new_num_commits_in_base
;
1153 else if (ctx
->new_base_graph
) {
1155 if (find_commit_in_graph(parent
->item
,
1156 ctx
->new_base_graph
,
1162 BUG("missing parent %s for commit %s",
1163 oid_to_hex(&parent
->item
->object
.oid
),
1164 oid_to_hex(&(*list
)->object
.oid
));
1165 else if (!parent
->next
)
1166 edge_value
|= GRAPH_LAST_EDGE
;
1168 hashwrite_be32(f
, edge_value
);
1177 static int write_graph_chunk_bloom_indexes(struct hashfile
*f
,
1178 struct write_commit_graph_context
*ctx
)
1180 struct commit
**list
= ctx
->commits
.list
;
1181 struct commit
**last
= ctx
->commits
.list
+ ctx
->commits
.nr
;
1182 uint32_t cur_pos
= 0;
1184 while (list
< last
) {
1185 struct bloom_filter
*filter
= get_bloom_filter(ctx
->r
, *list
);
1186 size_t len
= filter
? filter
->len
: 0;
1188 display_progress(ctx
->progress
, ++ctx
->progress_cnt
);
1189 hashwrite_be32(f
, cur_pos
);
1196 static void trace2_bloom_filter_settings(struct write_commit_graph_context
*ctx
)
1198 struct json_writer jw
= JSON_WRITER_INIT
;
1200 jw_object_begin(&jw
, 0);
1201 jw_object_intmax(&jw
, "hash_version", ctx
->bloom_settings
->hash_version
);
1202 jw_object_intmax(&jw
, "num_hashes", ctx
->bloom_settings
->num_hashes
);
1203 jw_object_intmax(&jw
, "bits_per_entry", ctx
->bloom_settings
->bits_per_entry
);
1204 jw_object_intmax(&jw
, "max_changed_paths", ctx
->bloom_settings
->max_changed_paths
);
1207 trace2_data_json("bloom", ctx
->r
, "settings", &jw
);
1212 static int write_graph_chunk_bloom_data(struct hashfile
*f
,
1213 struct write_commit_graph_context
*ctx
)
1215 struct commit
**list
= ctx
->commits
.list
;
1216 struct commit
**last
= ctx
->commits
.list
+ ctx
->commits
.nr
;
1218 trace2_bloom_filter_settings(ctx
);
1220 hashwrite_be32(f
, ctx
->bloom_settings
->hash_version
);
1221 hashwrite_be32(f
, ctx
->bloom_settings
->num_hashes
);
1222 hashwrite_be32(f
, ctx
->bloom_settings
->bits_per_entry
);
1224 while (list
< last
) {
1225 struct bloom_filter
*filter
= get_bloom_filter(ctx
->r
, *list
);
1226 size_t len
= filter
? filter
->len
: 0;
1228 display_progress(ctx
->progress
, ++ctx
->progress_cnt
);
1230 hashwrite(f
, filter
->data
, len
* sizeof(unsigned char));
1237 static int add_packed_commits(const struct object_id
*oid
,
1238 struct packed_git
*pack
,
1242 struct write_commit_graph_context
*ctx
= (struct write_commit_graph_context
*)data
;
1243 enum object_type type
;
1244 off_t offset
= nth_packed_object_offset(pack
, pos
);
1245 struct object_info oi
= OBJECT_INFO_INIT
;
1248 display_progress(ctx
->progress
, ++ctx
->progress_done
);
1251 if (packed_object_info(ctx
->r
, pack
, offset
, &oi
) < 0)
1252 die(_("unable to get type of object %s"), oid_to_hex(oid
));
1254 if (type
!= OBJ_COMMIT
)
1257 oid_array_append(&ctx
->oids
, oid
);
1258 set_commit_pos(ctx
->r
, oid
);
1263 static void add_missing_parents(struct write_commit_graph_context
*ctx
, struct commit
*commit
)
1265 struct commit_list
*parent
;
1266 for (parent
= commit
->parents
; parent
; parent
= parent
->next
) {
1267 if (!(parent
->item
->object
.flags
& REACHABLE
)) {
1268 oid_array_append(&ctx
->oids
, &parent
->item
->object
.oid
);
1269 parent
->item
->object
.flags
|= REACHABLE
;
1274 static void close_reachable(struct write_commit_graph_context
*ctx
)
1277 struct commit
*commit
;
1278 enum commit_graph_split_flags flags
= ctx
->opts
?
1279 ctx
->opts
->split_flags
: COMMIT_GRAPH_SPLIT_UNSPECIFIED
;
1281 if (ctx
->report_progress
)
1282 ctx
->progress
= start_delayed_progress(
1283 _("Loading known commits in commit graph"),
1285 for (i
= 0; i
< ctx
->oids
.nr
; i
++) {
1286 display_progress(ctx
->progress
, i
+ 1);
1287 commit
= lookup_commit(ctx
->r
, &ctx
->oids
.oid
[i
]);
1289 commit
->object
.flags
|= REACHABLE
;
1291 stop_progress(&ctx
->progress
);
1294 * As this loop runs, ctx->oids.nr may grow, but not more
1295 * than the number of missing commits in the reachable
1298 if (ctx
->report_progress
)
1299 ctx
->progress
= start_delayed_progress(
1300 _("Expanding reachable commits in commit graph"),
1302 for (i
= 0; i
< ctx
->oids
.nr
; i
++) {
1303 display_progress(ctx
->progress
, i
+ 1);
1304 commit
= lookup_commit(ctx
->r
, &ctx
->oids
.oid
[i
]);
1309 if ((!parse_commit(commit
) &&
1310 commit_graph_position(commit
) == COMMIT_NOT_FROM_GRAPH
) ||
1311 flags
== COMMIT_GRAPH_SPLIT_REPLACE
)
1312 add_missing_parents(ctx
, commit
);
1313 } else if (!parse_commit_no_graph(commit
))
1314 add_missing_parents(ctx
, commit
);
1316 stop_progress(&ctx
->progress
);
1318 if (ctx
->report_progress
)
1319 ctx
->progress
= start_delayed_progress(
1320 _("Clearing commit marks in commit graph"),
1322 for (i
= 0; i
< ctx
->oids
.nr
; i
++) {
1323 display_progress(ctx
->progress
, i
+ 1);
1324 commit
= lookup_commit(ctx
->r
, &ctx
->oids
.oid
[i
]);
1327 commit
->object
.flags
&= ~REACHABLE
;
1329 stop_progress(&ctx
->progress
);
1332 static void compute_generation_numbers(struct write_commit_graph_context
*ctx
)
1335 struct commit_list
*list
= NULL
;
1337 if (ctx
->report_progress
)
1338 ctx
->progress
= start_delayed_progress(
1339 _("Computing commit graph generation numbers"),
1341 for (i
= 0; i
< ctx
->commits
.nr
; i
++) {
1342 uint32_t generation
= commit_graph_data_at(ctx
->commits
.list
[i
])->generation
;
1344 display_progress(ctx
->progress
, i
+ 1);
1345 if (generation
!= GENERATION_NUMBER_INFINITY
&&
1346 generation
!= GENERATION_NUMBER_ZERO
)
1349 commit_list_insert(ctx
->commits
.list
[i
], &list
);
1351 struct commit
*current
= list
->item
;
1352 struct commit_list
*parent
;
1353 int all_parents_computed
= 1;
1354 uint32_t max_generation
= 0;
1356 for (parent
= current
->parents
; parent
; parent
= parent
->next
) {
1357 generation
= commit_graph_data_at(parent
->item
)->generation
;
1359 if (generation
== GENERATION_NUMBER_INFINITY
||
1360 generation
== GENERATION_NUMBER_ZERO
) {
1361 all_parents_computed
= 0;
1362 commit_list_insert(parent
->item
, &list
);
1364 } else if (generation
> max_generation
) {
1365 max_generation
= generation
;
1369 if (all_parents_computed
) {
1370 struct commit_graph_data
*data
= commit_graph_data_at(current
);
1372 data
->generation
= max_generation
+ 1;
1375 if (data
->generation
> GENERATION_NUMBER_MAX
)
1376 data
->generation
= GENERATION_NUMBER_MAX
;
1380 stop_progress(&ctx
->progress
);
1383 static void trace2_bloom_filter_write_statistics(struct write_commit_graph_context
*ctx
)
1385 trace2_data_intmax("commit-graph", ctx
->r
, "filter-computed",
1386 ctx
->count_bloom_filter_computed
);
1387 trace2_data_intmax("commit-graph", ctx
->r
, "filter-not-computed",
1388 ctx
->count_bloom_filter_not_computed
);
1389 trace2_data_intmax("commit-graph", ctx
->r
, "filter-trunc-empty",
1390 ctx
->count_bloom_filter_trunc_empty
);
1391 trace2_data_intmax("commit-graph", ctx
->r
, "filter-trunc-large",
1392 ctx
->count_bloom_filter_trunc_large
);
1395 static void compute_bloom_filters(struct write_commit_graph_context
*ctx
)
1398 struct progress
*progress
= NULL
;
1399 struct commit
**sorted_commits
;
1400 int max_new_filters
;
1402 init_bloom_filters();
1404 if (ctx
->report_progress
)
1405 progress
= start_delayed_progress(
1406 _("Computing commit changed paths Bloom filters"),
1409 ALLOC_ARRAY(sorted_commits
, ctx
->commits
.nr
);
1410 COPY_ARRAY(sorted_commits
, ctx
->commits
.list
, ctx
->commits
.nr
);
1412 if (ctx
->order_by_pack
)
1413 QSORT(sorted_commits
, ctx
->commits
.nr
, commit_pos_cmp
);
1415 QSORT(sorted_commits
, ctx
->commits
.nr
, commit_gen_cmp
);
1417 max_new_filters
= ctx
->opts
&& ctx
->opts
->max_new_filters
>= 0 ?
1418 ctx
->opts
->max_new_filters
: ctx
->commits
.nr
;
1420 for (i
= 0; i
< ctx
->commits
.nr
; i
++) {
1421 enum bloom_filter_computed computed
= 0;
1422 struct commit
*c
= sorted_commits
[i
];
1423 struct bloom_filter
*filter
= get_or_compute_bloom_filter(
1426 ctx
->count_bloom_filter_computed
< max_new_filters
,
1427 ctx
->bloom_settings
,
1429 if (computed
& BLOOM_COMPUTED
) {
1430 ctx
->count_bloom_filter_computed
++;
1431 if (computed
& BLOOM_TRUNC_EMPTY
)
1432 ctx
->count_bloom_filter_trunc_empty
++;
1433 if (computed
& BLOOM_TRUNC_LARGE
)
1434 ctx
->count_bloom_filter_trunc_large
++;
1435 } else if (computed
& BLOOM_NOT_COMPUTED
)
1436 ctx
->count_bloom_filter_not_computed
++;
1437 ctx
->total_bloom_filter_data_size
+= filter
1438 ? sizeof(unsigned char) * filter
->len
: 0;
1439 display_progress(progress
, i
+ 1);
1442 if (trace2_is_enabled())
1443 trace2_bloom_filter_write_statistics(ctx
);
1445 free(sorted_commits
);
1446 stop_progress(&progress
);
1449 struct refs_cb_data
{
1450 struct oidset
*commits
;
1451 struct progress
*progress
;
1454 static int add_ref_to_set(const char *refname
,
1455 const struct object_id
*oid
,
1456 int flags
, void *cb_data
)
1458 struct object_id peeled
;
1459 struct refs_cb_data
*data
= (struct refs_cb_data
*)cb_data
;
1461 if (!peel_ref(refname
, &peeled
))
1463 if (oid_object_info(the_repository
, oid
, NULL
) == OBJ_COMMIT
)
1464 oidset_insert(data
->commits
, oid
);
1466 display_progress(data
->progress
, oidset_size(data
->commits
));
1471 int write_commit_graph_reachable(struct object_directory
*odb
,
1472 enum commit_graph_write_flags flags
,
1473 const struct commit_graph_opts
*opts
)
1475 struct oidset commits
= OIDSET_INIT
;
1476 struct refs_cb_data data
;
1479 memset(&data
, 0, sizeof(data
));
1480 data
.commits
= &commits
;
1481 if (flags
& COMMIT_GRAPH_WRITE_PROGRESS
)
1482 data
.progress
= start_delayed_progress(
1483 _("Collecting referenced commits"), 0);
1485 for_each_ref(add_ref_to_set
, &data
);
1487 stop_progress(&data
.progress
);
1489 result
= write_commit_graph(odb
, NULL
, &commits
,
1492 oidset_clear(&commits
);
1496 static int fill_oids_from_packs(struct write_commit_graph_context
*ctx
,
1497 struct string_list
*pack_indexes
)
1500 struct strbuf progress_title
= STRBUF_INIT
;
1501 struct strbuf packname
= STRBUF_INIT
;
1504 strbuf_addf(&packname
, "%s/pack/", ctx
->odb
->path
);
1505 dirlen
= packname
.len
;
1506 if (ctx
->report_progress
) {
1507 strbuf_addf(&progress_title
,
1508 Q_("Finding commits for commit graph in %d pack",
1509 "Finding commits for commit graph in %d packs",
1512 ctx
->progress
= start_delayed_progress(progress_title
.buf
, 0);
1513 ctx
->progress_done
= 0;
1515 for (i
= 0; i
< pack_indexes
->nr
; i
++) {
1516 struct packed_git
*p
;
1517 strbuf_setlen(&packname
, dirlen
);
1518 strbuf_addstr(&packname
, pack_indexes
->items
[i
].string
);
1519 p
= add_packed_git(packname
.buf
, packname
.len
, 1);
1521 error(_("error adding pack %s"), packname
.buf
);
1524 if (open_pack_index(p
)) {
1525 error(_("error opening index for %s"), packname
.buf
);
1528 for_each_object_in_pack(p
, add_packed_commits
, ctx
,
1529 FOR_EACH_OBJECT_PACK_ORDER
);
1534 stop_progress(&ctx
->progress
);
1535 strbuf_release(&progress_title
);
1536 strbuf_release(&packname
);
1541 static int fill_oids_from_commits(struct write_commit_graph_context
*ctx
,
1542 struct oidset
*commits
)
1544 struct oidset_iter iter
;
1545 struct object_id
*oid
;
1547 if (!oidset_size(commits
))
1550 oidset_iter_init(commits
, &iter
);
1551 while ((oid
= oidset_iter_next(&iter
))) {
1552 oid_array_append(&ctx
->oids
, oid
);
1558 static void fill_oids_from_all_packs(struct write_commit_graph_context
*ctx
)
1560 if (ctx
->report_progress
)
1561 ctx
->progress
= start_delayed_progress(
1562 _("Finding commits for commit graph among packed objects"),
1563 ctx
->approx_nr_objects
);
1564 for_each_packed_object(add_packed_commits
, ctx
,
1565 FOR_EACH_OBJECT_PACK_ORDER
);
1566 if (ctx
->progress_done
< ctx
->approx_nr_objects
)
1567 display_progress(ctx
->progress
, ctx
->approx_nr_objects
);
1568 stop_progress(&ctx
->progress
);
1571 static void copy_oids_to_commits(struct write_commit_graph_context
*ctx
)
1574 enum commit_graph_split_flags flags
= ctx
->opts
?
1575 ctx
->opts
->split_flags
: COMMIT_GRAPH_SPLIT_UNSPECIFIED
;
1577 ctx
->num_extra_edges
= 0;
1578 if (ctx
->report_progress
)
1579 ctx
->progress
= start_delayed_progress(
1580 _("Finding extra edges in commit graph"),
1582 oid_array_sort(&ctx
->oids
);
1583 for (i
= 0; i
< ctx
->oids
.nr
; i
= oid_array_next_unique(&ctx
->oids
, i
)) {
1584 unsigned int num_parents
;
1586 display_progress(ctx
->progress
, i
+ 1);
1588 ALLOC_GROW(ctx
->commits
.list
, ctx
->commits
.nr
+ 1, ctx
->commits
.alloc
);
1589 ctx
->commits
.list
[ctx
->commits
.nr
] = lookup_commit(ctx
->r
, &ctx
->oids
.oid
[i
]);
1591 if (ctx
->split
&& flags
!= COMMIT_GRAPH_SPLIT_REPLACE
&&
1592 commit_graph_position(ctx
->commits
.list
[ctx
->commits
.nr
]) != COMMIT_NOT_FROM_GRAPH
)
1595 if (ctx
->split
&& flags
== COMMIT_GRAPH_SPLIT_REPLACE
)
1596 parse_commit(ctx
->commits
.list
[ctx
->commits
.nr
]);
1598 parse_commit_no_graph(ctx
->commits
.list
[ctx
->commits
.nr
]);
1600 num_parents
= commit_list_count(ctx
->commits
.list
[ctx
->commits
.nr
]->parents
);
1601 if (num_parents
> 2)
1602 ctx
->num_extra_edges
+= num_parents
- 1;
1606 stop_progress(&ctx
->progress
);
1609 static int write_graph_chunk_base_1(struct hashfile
*f
,
1610 struct commit_graph
*g
)
1617 num
= write_graph_chunk_base_1(f
, g
->base_graph
);
1618 hashwrite(f
, g
->oid
.hash
, the_hash_algo
->rawsz
);
1622 static int write_graph_chunk_base(struct hashfile
*f
,
1623 struct write_commit_graph_context
*ctx
)
1625 int num
= write_graph_chunk_base_1(f
, ctx
->new_base_graph
);
1627 if (num
!= ctx
->num_commit_graphs_after
- 1) {
1628 error(_("failed to write correct number of base graph ids"));
1635 typedef int (*chunk_write_fn
)(struct hashfile
*f
,
1636 struct write_commit_graph_context
*ctx
);
1641 chunk_write_fn write_fn
;
1644 static int write_commit_graph_file(struct write_commit_graph_context
*ctx
)
1649 struct lock_file lk
= LOCK_INIT
;
1650 struct chunk_info chunks
[MAX_NUM_CHUNKS
+ 1];
1651 const unsigned hashsz
= the_hash_algo
->rawsz
;
1652 struct strbuf progress_title
= STRBUF_INIT
;
1654 uint64_t chunk_offset
;
1655 struct object_id file_hash
;
1658 struct strbuf tmp_file
= STRBUF_INIT
;
1660 strbuf_addf(&tmp_file
,
1661 "%s/info/commit-graphs/tmp_graph_XXXXXX",
1663 ctx
->graph_name
= strbuf_detach(&tmp_file
, NULL
);
1665 ctx
->graph_name
= get_commit_graph_filename(ctx
->odb
);
1668 if (safe_create_leading_directories(ctx
->graph_name
)) {
1669 UNLEAK(ctx
->graph_name
);
1670 error(_("unable to create leading directories of %s"),
1676 char *lock_name
= get_commit_graph_chain_filename(ctx
->odb
);
1678 hold_lock_file_for_update_mode(&lk
, lock_name
,
1679 LOCK_DIE_ON_ERROR
, 0444);
1681 fd
= git_mkstemp_mode(ctx
->graph_name
, 0444);
1683 error(_("unable to create temporary graph layer"));
1687 if (adjust_shared_perm(ctx
->graph_name
)) {
1688 error(_("unable to adjust shared permissions for '%s'"),
1693 f
= hashfd(fd
, ctx
->graph_name
);
1695 hold_lock_file_for_update_mode(&lk
, ctx
->graph_name
,
1696 LOCK_DIE_ON_ERROR
, 0444);
1697 fd
= get_lock_file_fd(&lk
);
1698 f
= hashfd(fd
, get_lock_file_path(&lk
));
1701 chunks
[0].id
= GRAPH_CHUNKID_OIDFANOUT
;
1702 chunks
[0].size
= GRAPH_FANOUT_SIZE
;
1703 chunks
[0].write_fn
= write_graph_chunk_fanout
;
1704 chunks
[1].id
= GRAPH_CHUNKID_OIDLOOKUP
;
1705 chunks
[1].size
= hashsz
* ctx
->commits
.nr
;
1706 chunks
[1].write_fn
= write_graph_chunk_oids
;
1707 chunks
[2].id
= GRAPH_CHUNKID_DATA
;
1708 chunks
[2].size
= (hashsz
+ 16) * ctx
->commits
.nr
;
1709 chunks
[2].write_fn
= write_graph_chunk_data
;
1710 if (ctx
->num_extra_edges
) {
1711 chunks
[num_chunks
].id
= GRAPH_CHUNKID_EXTRAEDGES
;
1712 chunks
[num_chunks
].size
= 4 * ctx
->num_extra_edges
;
1713 chunks
[num_chunks
].write_fn
= write_graph_chunk_extra_edges
;
1716 if (ctx
->changed_paths
) {
1717 chunks
[num_chunks
].id
= GRAPH_CHUNKID_BLOOMINDEXES
;
1718 chunks
[num_chunks
].size
= sizeof(uint32_t) * ctx
->commits
.nr
;
1719 chunks
[num_chunks
].write_fn
= write_graph_chunk_bloom_indexes
;
1721 chunks
[num_chunks
].id
= GRAPH_CHUNKID_BLOOMDATA
;
1722 chunks
[num_chunks
].size
= sizeof(uint32_t) * 3
1723 + ctx
->total_bloom_filter_data_size
;
1724 chunks
[num_chunks
].write_fn
= write_graph_chunk_bloom_data
;
1727 if (ctx
->num_commit_graphs_after
> 1) {
1728 chunks
[num_chunks
].id
= GRAPH_CHUNKID_BASE
;
1729 chunks
[num_chunks
].size
= hashsz
* (ctx
->num_commit_graphs_after
- 1);
1730 chunks
[num_chunks
].write_fn
= write_graph_chunk_base
;
1734 chunks
[num_chunks
].id
= 0;
1735 chunks
[num_chunks
].size
= 0;
1737 hashwrite_be32(f
, GRAPH_SIGNATURE
);
1739 hashwrite_u8(f
, GRAPH_VERSION
);
1740 hashwrite_u8(f
, oid_version());
1741 hashwrite_u8(f
, num_chunks
);
1742 hashwrite_u8(f
, ctx
->num_commit_graphs_after
- 1);
1744 chunk_offset
= 8 + (num_chunks
+ 1) * GRAPH_CHUNKLOOKUP_WIDTH
;
1745 for (i
= 0; i
<= num_chunks
; i
++) {
1746 uint32_t chunk_write
[3];
1748 chunk_write
[0] = htonl(chunks
[i
].id
);
1749 chunk_write
[1] = htonl(chunk_offset
>> 32);
1750 chunk_write
[2] = htonl(chunk_offset
& 0xffffffff);
1751 hashwrite(f
, chunk_write
, 12);
1753 chunk_offset
+= chunks
[i
].size
;
1756 if (ctx
->report_progress
) {
1757 strbuf_addf(&progress_title
,
1758 Q_("Writing out commit graph in %d pass",
1759 "Writing out commit graph in %d passes",
1762 ctx
->progress
= start_delayed_progress(
1764 num_chunks
* ctx
->commits
.nr
);
1767 for (i
= 0; i
< num_chunks
; i
++) {
1768 uint64_t start_offset
= f
->total
+ f
->offset
;
1770 if (chunks
[i
].write_fn(f
, ctx
))
1773 if (f
->total
+ f
->offset
!= start_offset
+ chunks
[i
].size
)
1774 BUG("expected to write %"PRId64
" bytes to chunk %"PRIx32
", but wrote %"PRId64
" instead",
1775 chunks
[i
].size
, chunks
[i
].id
,
1776 f
->total
+ f
->offset
- start_offset
);
1779 stop_progress(&ctx
->progress
);
1780 strbuf_release(&progress_title
);
1782 if (ctx
->split
&& ctx
->base_graph_name
&& ctx
->num_commit_graphs_after
> 1) {
1783 char *new_base_hash
= xstrdup(oid_to_hex(&ctx
->new_base_graph
->oid
));
1784 char *new_base_name
= get_split_graph_filename(ctx
->new_base_graph
->odb
, new_base_hash
);
1786 free(ctx
->commit_graph_filenames_after
[ctx
->num_commit_graphs_after
- 2]);
1787 free(ctx
->commit_graph_hash_after
[ctx
->num_commit_graphs_after
- 2]);
1788 ctx
->commit_graph_filenames_after
[ctx
->num_commit_graphs_after
- 2] = new_base_name
;
1789 ctx
->commit_graph_hash_after
[ctx
->num_commit_graphs_after
- 2] = new_base_hash
;
1792 close_commit_graph(ctx
->r
->objects
);
1793 finalize_hashfile(f
, file_hash
.hash
, CSUM_HASH_IN_STREAM
| CSUM_FSYNC
);
1796 FILE *chainf
= fdopen_lock_file(&lk
, "w");
1797 char *final_graph_name
;
1803 error(_("unable to open commit-graph chain file"));
1807 if (ctx
->base_graph_name
) {
1809 int idx
= ctx
->num_commit_graphs_after
- 1;
1810 if (ctx
->num_commit_graphs_after
> 1)
1813 dest
= ctx
->commit_graph_filenames_after
[idx
];
1815 if (strcmp(ctx
->base_graph_name
, dest
)) {
1816 result
= rename(ctx
->base_graph_name
, dest
);
1819 error(_("failed to rename base commit-graph file"));
1824 char *graph_name
= get_commit_graph_filename(ctx
->odb
);
1828 ctx
->commit_graph_hash_after
[ctx
->num_commit_graphs_after
- 1] = xstrdup(oid_to_hex(&file_hash
));
1829 final_graph_name
= get_split_graph_filename(ctx
->odb
,
1830 ctx
->commit_graph_hash_after
[ctx
->num_commit_graphs_after
- 1]);
1831 ctx
->commit_graph_filenames_after
[ctx
->num_commit_graphs_after
- 1] = final_graph_name
;
1833 result
= rename(ctx
->graph_name
, final_graph_name
);
1835 for (i
= 0; i
< ctx
->num_commit_graphs_after
; i
++)
1836 fprintf(get_lock_file_fp(&lk
), "%s\n", ctx
->commit_graph_hash_after
[i
]);
1839 error(_("failed to rename temporary commit-graph file"));
1844 commit_lock_file(&lk
);
1849 static void split_graph_merge_strategy(struct write_commit_graph_context
*ctx
)
1851 struct commit_graph
*g
;
1852 uint32_t num_commits
;
1853 enum commit_graph_split_flags flags
= COMMIT_GRAPH_SPLIT_UNSPECIFIED
;
1856 int max_commits
= 0;
1860 max_commits
= ctx
->opts
->max_commits
;
1862 if (ctx
->opts
->size_multiple
)
1863 size_mult
= ctx
->opts
->size_multiple
;
1865 flags
= ctx
->opts
->split_flags
;
1868 g
= ctx
->r
->objects
->commit_graph
;
1869 num_commits
= ctx
->commits
.nr
;
1870 if (flags
== COMMIT_GRAPH_SPLIT_REPLACE
)
1871 ctx
->num_commit_graphs_after
= 1;
1873 ctx
->num_commit_graphs_after
= ctx
->num_commit_graphs_before
+ 1;
1875 if (flags
!= COMMIT_GRAPH_SPLIT_MERGE_PROHIBITED
&&
1876 flags
!= COMMIT_GRAPH_SPLIT_REPLACE
) {
1877 while (g
&& (g
->num_commits
<= size_mult
* num_commits
||
1878 (max_commits
&& num_commits
> max_commits
))) {
1879 if (g
->odb
!= ctx
->odb
)
1882 num_commits
+= g
->num_commits
;
1885 ctx
->num_commit_graphs_after
--;
1889 if (flags
!= COMMIT_GRAPH_SPLIT_REPLACE
)
1890 ctx
->new_base_graph
= g
;
1891 else if (ctx
->num_commit_graphs_after
!= 1)
1892 BUG("split_graph_merge_strategy: num_commit_graphs_after "
1893 "should be 1 with --split=replace");
1895 if (ctx
->num_commit_graphs_after
== 2) {
1896 char *old_graph_name
= get_commit_graph_filename(g
->odb
);
1898 if (!strcmp(g
->filename
, old_graph_name
) &&
1899 g
->odb
!= ctx
->odb
) {
1900 ctx
->num_commit_graphs_after
= 1;
1901 ctx
->new_base_graph
= NULL
;
1904 free(old_graph_name
);
1907 CALLOC_ARRAY(ctx
->commit_graph_filenames_after
, ctx
->num_commit_graphs_after
);
1908 CALLOC_ARRAY(ctx
->commit_graph_hash_after
, ctx
->num_commit_graphs_after
);
1910 for (i
= 0; i
< ctx
->num_commit_graphs_after
&&
1911 i
< ctx
->num_commit_graphs_before
; i
++)
1912 ctx
->commit_graph_filenames_after
[i
] = xstrdup(ctx
->commit_graph_filenames_before
[i
]);
1914 i
= ctx
->num_commit_graphs_before
- 1;
1915 g
= ctx
->r
->objects
->commit_graph
;
1918 if (i
< ctx
->num_commit_graphs_after
)
1919 ctx
->commit_graph_hash_after
[i
] = xstrdup(oid_to_hex(&g
->oid
));
1926 static void merge_commit_graph(struct write_commit_graph_context
*ctx
,
1927 struct commit_graph
*g
)
1930 uint32_t offset
= g
->num_commits_in_base
;
1932 ALLOC_GROW(ctx
->commits
.list
, ctx
->commits
.nr
+ g
->num_commits
, ctx
->commits
.alloc
);
1934 for (i
= 0; i
< g
->num_commits
; i
++) {
1935 struct object_id oid
;
1936 struct commit
*result
;
1938 display_progress(ctx
->progress
, i
+ 1);
1940 load_oid_from_graph(g
, i
+ offset
, &oid
);
1942 /* only add commits if they still exist in the repo */
1943 result
= lookup_commit_reference_gently(ctx
->r
, &oid
, 1);
1946 ctx
->commits
.list
[ctx
->commits
.nr
] = result
;
1952 static int commit_compare(const void *_a
, const void *_b
)
1954 const struct commit
*a
= *(const struct commit
**)_a
;
1955 const struct commit
*b
= *(const struct commit
**)_b
;
1956 return oidcmp(&a
->object
.oid
, &b
->object
.oid
);
1959 static void sort_and_scan_merged_commits(struct write_commit_graph_context
*ctx
)
1961 uint32_t i
, dedup_i
= 0;
1963 if (ctx
->report_progress
)
1964 ctx
->progress
= start_delayed_progress(
1965 _("Scanning merged commits"),
1968 QSORT(ctx
->commits
.list
, ctx
->commits
.nr
, commit_compare
);
1970 ctx
->num_extra_edges
= 0;
1971 for (i
= 0; i
< ctx
->commits
.nr
; i
++) {
1972 display_progress(ctx
->progress
, i
);
1974 if (i
&& oideq(&ctx
->commits
.list
[i
- 1]->object
.oid
,
1975 &ctx
->commits
.list
[i
]->object
.oid
)) {
1977 * Silently ignore duplicates. These were likely
1978 * created due to a commit appearing in multiple
1979 * layers of the chain, which is unexpected but
1980 * not invalid. We should make sure there is a
1981 * unique copy in the new layer.
1984 unsigned int num_parents
;
1986 ctx
->commits
.list
[dedup_i
] = ctx
->commits
.list
[i
];
1989 num_parents
= commit_list_count(ctx
->commits
.list
[i
]->parents
);
1990 if (num_parents
> 2)
1991 ctx
->num_extra_edges
+= num_parents
- 1;
1995 ctx
->commits
.nr
= dedup_i
;
1997 stop_progress(&ctx
->progress
);
2000 static void merge_commit_graphs(struct write_commit_graph_context
*ctx
)
2002 struct commit_graph
*g
= ctx
->r
->objects
->commit_graph
;
2003 uint32_t current_graph_number
= ctx
->num_commit_graphs_before
;
2005 while (g
&& current_graph_number
>= ctx
->num_commit_graphs_after
) {
2006 current_graph_number
--;
2008 if (ctx
->report_progress
)
2009 ctx
->progress
= start_delayed_progress(_("Merging commit-graph"), 0);
2011 merge_commit_graph(ctx
, g
);
2012 stop_progress(&ctx
->progress
);
2018 ctx
->new_base_graph
= g
;
2019 ctx
->new_num_commits_in_base
= g
->num_commits
+ g
->num_commits_in_base
;
2022 if (ctx
->new_base_graph
)
2023 ctx
->base_graph_name
= xstrdup(ctx
->new_base_graph
->filename
);
2025 sort_and_scan_merged_commits(ctx
);
2028 static void mark_commit_graphs(struct write_commit_graph_context
*ctx
)
2031 time_t now
= time(NULL
);
2033 for (i
= ctx
->num_commit_graphs_after
- 1; i
< ctx
->num_commit_graphs_before
; i
++) {
2035 struct utimbuf updated_time
;
2037 stat(ctx
->commit_graph_filenames_before
[i
], &st
);
2039 updated_time
.actime
= st
.st_atime
;
2040 updated_time
.modtime
= now
;
2041 utime(ctx
->commit_graph_filenames_before
[i
], &updated_time
);
2045 static void expire_commit_graphs(struct write_commit_graph_context
*ctx
)
2047 struct strbuf path
= STRBUF_INIT
;
2051 timestamp_t expire_time
= time(NULL
);
2053 if (ctx
->opts
&& ctx
->opts
->expire_time
)
2054 expire_time
= ctx
->opts
->expire_time
;
2056 char *chain_file_name
= get_commit_graph_chain_filename(ctx
->odb
);
2057 unlink(chain_file_name
);
2058 free(chain_file_name
);
2059 ctx
->num_commit_graphs_after
= 0;
2062 strbuf_addstr(&path
, ctx
->odb
->path
);
2063 strbuf_addstr(&path
, "/info/commit-graphs");
2064 dir
= opendir(path
.buf
);
2069 strbuf_addch(&path
, '/');
2070 dirnamelen
= path
.len
;
2071 while ((de
= readdir(dir
)) != NULL
) {
2073 uint32_t i
, found
= 0;
2075 strbuf_setlen(&path
, dirnamelen
);
2076 strbuf_addstr(&path
, de
->d_name
);
2078 stat(path
.buf
, &st
);
2080 if (st
.st_mtime
> expire_time
)
2082 if (path
.len
< 6 || strcmp(path
.buf
+ path
.len
- 6, ".graph"))
2085 for (i
= 0; i
< ctx
->num_commit_graphs_after
; i
++) {
2086 if (!strcmp(ctx
->commit_graph_filenames_after
[i
],
2098 strbuf_release(&path
);
2101 int write_commit_graph(struct object_directory
*odb
,
2102 struct string_list
*pack_indexes
,
2103 struct oidset
*commits
,
2104 enum commit_graph_write_flags flags
,
2105 const struct commit_graph_opts
*opts
)
2107 struct write_commit_graph_context
*ctx
;
2111 struct bloom_filter_settings bloom_settings
= DEFAULT_BLOOM_FILTER_SETTINGS
;
2113 prepare_repo_settings(the_repository
);
2114 if (!the_repository
->settings
.core_commit_graph
) {
2115 warning(_("attempting to write a commit-graph, but 'core.commitGraph' is disabled"));
2118 if (!commit_graph_compatible(the_repository
))
2121 ctx
= xcalloc(1, sizeof(struct write_commit_graph_context
));
2122 ctx
->r
= the_repository
;
2124 ctx
->append
= flags
& COMMIT_GRAPH_WRITE_APPEND
? 1 : 0;
2125 ctx
->report_progress
= flags
& COMMIT_GRAPH_WRITE_PROGRESS
? 1 : 0;
2126 ctx
->split
= flags
& COMMIT_GRAPH_WRITE_SPLIT
? 1 : 0;
2128 ctx
->total_bloom_filter_data_size
= 0;
2130 bloom_settings
.bits_per_entry
= git_env_ulong("GIT_TEST_BLOOM_SETTINGS_BITS_PER_ENTRY",
2131 bloom_settings
.bits_per_entry
);
2132 bloom_settings
.num_hashes
= git_env_ulong("GIT_TEST_BLOOM_SETTINGS_NUM_HASHES",
2133 bloom_settings
.num_hashes
);
2134 bloom_settings
.max_changed_paths
= git_env_ulong("GIT_TEST_BLOOM_SETTINGS_MAX_CHANGED_PATHS",
2135 bloom_settings
.max_changed_paths
);
2136 ctx
->bloom_settings
= &bloom_settings
;
2138 if (flags
& COMMIT_GRAPH_WRITE_BLOOM_FILTERS
)
2139 ctx
->changed_paths
= 1;
2140 if (!(flags
& COMMIT_GRAPH_NO_WRITE_BLOOM_FILTERS
)) {
2141 struct commit_graph
*g
;
2142 prepare_commit_graph_one(ctx
->r
, ctx
->odb
);
2144 g
= ctx
->r
->objects
->commit_graph
;
2146 /* We have changed-paths already. Keep them in the next graph */
2147 if (g
&& g
->chunk_bloom_data
) {
2148 ctx
->changed_paths
= 1;
2149 ctx
->bloom_settings
= g
->bloom_filter_settings
;
2154 struct commit_graph
*g
;
2155 prepare_commit_graph(ctx
->r
);
2157 g
= ctx
->r
->objects
->commit_graph
;
2160 ctx
->num_commit_graphs_before
++;
2164 if (ctx
->num_commit_graphs_before
) {
2165 ALLOC_ARRAY(ctx
->commit_graph_filenames_before
, ctx
->num_commit_graphs_before
);
2166 i
= ctx
->num_commit_graphs_before
;
2167 g
= ctx
->r
->objects
->commit_graph
;
2170 ctx
->commit_graph_filenames_before
[--i
] = xstrdup(g
->filename
);
2176 replace
= ctx
->opts
->split_flags
& COMMIT_GRAPH_SPLIT_REPLACE
;
2179 ctx
->approx_nr_objects
= approximate_object_count();
2182 prepare_commit_graph_one(ctx
->r
, ctx
->odb
);
2184 if (ctx
->append
&& ctx
->r
->objects
->commit_graph
) {
2185 struct commit_graph
*g
= ctx
->r
->objects
->commit_graph
;
2186 for (i
= 0; i
< g
->num_commits
; i
++) {
2187 struct object_id oid
;
2188 hashcpy(oid
.hash
, g
->chunk_oid_lookup
+ g
->hash_len
* i
);
2189 oid_array_append(&ctx
->oids
, &oid
);
2194 ctx
->order_by_pack
= 1;
2195 if ((res
= fill_oids_from_packs(ctx
, pack_indexes
)))
2200 if ((res
= fill_oids_from_commits(ctx
, commits
)))
2204 if (!pack_indexes
&& !commits
) {
2205 ctx
->order_by_pack
= 1;
2206 fill_oids_from_all_packs(ctx
);
2209 close_reachable(ctx
);
2211 copy_oids_to_commits(ctx
);
2213 if (ctx
->commits
.nr
>= GRAPH_EDGE_LAST_MASK
) {
2214 error(_("too many commits to write graph"));
2219 if (!ctx
->commits
.nr
&& !replace
)
2223 split_graph_merge_strategy(ctx
);
2226 merge_commit_graphs(ctx
);
2228 ctx
->num_commit_graphs_after
= 1;
2230 compute_generation_numbers(ctx
);
2232 if (ctx
->changed_paths
)
2233 compute_bloom_filters(ctx
);
2235 res
= write_commit_graph_file(ctx
);
2238 mark_commit_graphs(ctx
);
2240 expire_commit_graphs(ctx
);
2243 free(ctx
->graph_name
);
2244 free(ctx
->commits
.list
);
2245 oid_array_clear(&ctx
->oids
);
2247 if (ctx
->commit_graph_filenames_after
) {
2248 for (i
= 0; i
< ctx
->num_commit_graphs_after
; i
++) {
2249 free(ctx
->commit_graph_filenames_after
[i
]);
2250 free(ctx
->commit_graph_hash_after
[i
]);
2253 for (i
= 0; i
< ctx
->num_commit_graphs_before
; i
++)
2254 free(ctx
->commit_graph_filenames_before
[i
]);
2256 free(ctx
->commit_graph_filenames_after
);
2257 free(ctx
->commit_graph_filenames_before
);
2258 free(ctx
->commit_graph_hash_after
);
2266 #define VERIFY_COMMIT_GRAPH_ERROR_HASH 2
2267 static int verify_commit_graph_error
;
2269 static void graph_report(const char *fmt
, ...)
2273 verify_commit_graph_error
= 1;
2275 vfprintf(stderr
, fmt
, ap
);
2276 fprintf(stderr
, "\n");
2280 #define GENERATION_ZERO_EXISTS 1
2281 #define GENERATION_NUMBER_EXISTS 2
2283 int verify_commit_graph(struct repository
*r
, struct commit_graph
*g
, int flags
)
2285 uint32_t i
, cur_fanout_pos
= 0;
2286 struct object_id prev_oid
, cur_oid
, checksum
;
2287 int generation_zero
= 0;
2290 struct progress
*progress
= NULL
;
2291 int local_error
= 0;
2294 graph_report("no commit-graph file loaded");
2298 verify_commit_graph_error
= verify_commit_graph_lite(g
);
2299 if (verify_commit_graph_error
)
2300 return verify_commit_graph_error
;
2302 devnull
= open("/dev/null", O_WRONLY
);
2303 f
= hashfd(devnull
, NULL
);
2304 hashwrite(f
, g
->data
, g
->data_len
- g
->hash_len
);
2305 finalize_hashfile(f
, checksum
.hash
, CSUM_CLOSE
);
2306 if (!hasheq(checksum
.hash
, g
->data
+ g
->data_len
- g
->hash_len
)) {
2307 graph_report(_("the commit-graph file has incorrect checksum and is likely corrupt"));
2308 verify_commit_graph_error
= VERIFY_COMMIT_GRAPH_ERROR_HASH
;
2311 for (i
= 0; i
< g
->num_commits
; i
++) {
2312 struct commit
*graph_commit
;
2314 hashcpy(cur_oid
.hash
, g
->chunk_oid_lookup
+ g
->hash_len
* i
);
2316 if (i
&& oidcmp(&prev_oid
, &cur_oid
) >= 0)
2317 graph_report(_("commit-graph has incorrect OID order: %s then %s"),
2318 oid_to_hex(&prev_oid
),
2319 oid_to_hex(&cur_oid
));
2321 oidcpy(&prev_oid
, &cur_oid
);
2323 while (cur_oid
.hash
[0] > cur_fanout_pos
) {
2324 uint32_t fanout_value
= get_be32(g
->chunk_oid_fanout
+ cur_fanout_pos
);
2326 if (i
!= fanout_value
)
2327 graph_report(_("commit-graph has incorrect fanout value: fanout[%d] = %u != %u"),
2328 cur_fanout_pos
, fanout_value
, i
);
2332 graph_commit
= lookup_commit(r
, &cur_oid
);
2333 if (!parse_commit_in_graph_one(r
, g
, graph_commit
))
2334 graph_report(_("failed to parse commit %s from commit-graph"),
2335 oid_to_hex(&cur_oid
));
2338 while (cur_fanout_pos
< 256) {
2339 uint32_t fanout_value
= get_be32(g
->chunk_oid_fanout
+ cur_fanout_pos
);
2341 if (g
->num_commits
!= fanout_value
)
2342 graph_report(_("commit-graph has incorrect fanout value: fanout[%d] = %u != %u"),
2343 cur_fanout_pos
, fanout_value
, i
);
2348 if (verify_commit_graph_error
& ~VERIFY_COMMIT_GRAPH_ERROR_HASH
)
2349 return verify_commit_graph_error
;
2351 if (flags
& COMMIT_GRAPH_WRITE_PROGRESS
)
2352 progress
= start_progress(_("Verifying commits in commit graph"),
2355 for (i
= 0; i
< g
->num_commits
; i
++) {
2356 struct commit
*graph_commit
, *odb_commit
;
2357 struct commit_list
*graph_parents
, *odb_parents
;
2358 uint32_t max_generation
= 0;
2359 uint32_t generation
;
2361 display_progress(progress
, i
+ 1);
2362 hashcpy(cur_oid
.hash
, g
->chunk_oid_lookup
+ g
->hash_len
* i
);
2364 graph_commit
= lookup_commit(r
, &cur_oid
);
2365 odb_commit
= (struct commit
*)create_object(r
, &cur_oid
, alloc_commit_node(r
));
2366 if (parse_commit_internal(odb_commit
, 0, 0)) {
2367 graph_report(_("failed to parse commit %s from object database for commit-graph"),
2368 oid_to_hex(&cur_oid
));
2372 if (!oideq(&get_commit_tree_in_graph_one(r
, g
, graph_commit
)->object
.oid
,
2373 get_commit_tree_oid(odb_commit
)))
2374 graph_report(_("root tree OID for commit %s in commit-graph is %s != %s"),
2375 oid_to_hex(&cur_oid
),
2376 oid_to_hex(get_commit_tree_oid(graph_commit
)),
2377 oid_to_hex(get_commit_tree_oid(odb_commit
)));
2379 graph_parents
= graph_commit
->parents
;
2380 odb_parents
= odb_commit
->parents
;
2382 while (graph_parents
) {
2383 if (odb_parents
== NULL
) {
2384 graph_report(_("commit-graph parent list for commit %s is too long"),
2385 oid_to_hex(&cur_oid
));
2389 /* parse parent in case it is in a base graph */
2390 parse_commit_in_graph_one(r
, g
, graph_parents
->item
);
2392 if (!oideq(&graph_parents
->item
->object
.oid
, &odb_parents
->item
->object
.oid
))
2393 graph_report(_("commit-graph parent for %s is %s != %s"),
2394 oid_to_hex(&cur_oid
),
2395 oid_to_hex(&graph_parents
->item
->object
.oid
),
2396 oid_to_hex(&odb_parents
->item
->object
.oid
));
2398 generation
= commit_graph_generation(graph_parents
->item
);
2399 if (generation
> max_generation
)
2400 max_generation
= generation
;
2402 graph_parents
= graph_parents
->next
;
2403 odb_parents
= odb_parents
->next
;
2406 if (odb_parents
!= NULL
)
2407 graph_report(_("commit-graph parent list for commit %s terminates early"),
2408 oid_to_hex(&cur_oid
));
2410 if (!commit_graph_generation(graph_commit
)) {
2411 if (generation_zero
== GENERATION_NUMBER_EXISTS
)
2412 graph_report(_("commit-graph has generation number zero for commit %s, but non-zero elsewhere"),
2413 oid_to_hex(&cur_oid
));
2414 generation_zero
= GENERATION_ZERO_EXISTS
;
2415 } else if (generation_zero
== GENERATION_ZERO_EXISTS
)
2416 graph_report(_("commit-graph has non-zero generation number for commit %s, but zero elsewhere"),
2417 oid_to_hex(&cur_oid
));
2419 if (generation_zero
== GENERATION_ZERO_EXISTS
)
2423 * If one of our parents has generation GENERATION_NUMBER_MAX, then
2424 * our generation is also GENERATION_NUMBER_MAX. Decrement to avoid
2425 * extra logic in the following condition.
2427 if (max_generation
== GENERATION_NUMBER_MAX
)
2430 generation
= commit_graph_generation(graph_commit
);
2431 if (generation
!= max_generation
+ 1)
2432 graph_report(_("commit-graph generation for commit %s is %u != %u"),
2433 oid_to_hex(&cur_oid
),
2435 max_generation
+ 1);
2437 if (graph_commit
->date
!= odb_commit
->date
)
2438 graph_report(_("commit date for commit %s in commit-graph is %"PRItime
" != %"PRItime
),
2439 oid_to_hex(&cur_oid
),
2443 stop_progress(&progress
);
2445 local_error
= verify_commit_graph_error
;
2447 if (!(flags
& COMMIT_GRAPH_VERIFY_SHALLOW
) && g
->base_graph
)
2448 local_error
|= verify_commit_graph(r
, g
->base_graph
, flags
);
2453 void free_commit_graph(struct commit_graph
*g
)
2458 munmap((void *)g
->data
, g
->data_len
);
2462 free(g
->bloom_filter_settings
);
2466 void disable_commit_graph(struct repository
*r
)
2468 r
->commit_graph_disabled
= 1;