4 #include "git-compat-util.h"
12 #include "sha1-lookup.h"
13 #include "commit-graph.h"
14 #include "object-store.h"
17 #include "replace-object.h"
20 #include "commit-slab.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 static char *get_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)
185 static struct commit_graph
*alloc_commit_graph(void)
187 struct commit_graph
*g
= xcalloc(1, sizeof(*g
));
192 extern int read_replace_refs
;
194 static int commit_graph_compatible(struct repository
*r
)
199 if (read_replace_refs
) {
200 prepare_replace_object(r
);
201 if (hashmap_get_size(&r
->objects
->replace_map
->map
))
205 prepare_commit_graft(r
);
206 if (r
->parsed_objects
&& r
->parsed_objects
->grafts_nr
)
208 if (is_repository_shallow(r
))
214 int open_commit_graph(const char *graph_file
, int *fd
, struct stat
*st
)
216 *fd
= git_open(graph_file
);
219 if (fstat(*fd
, st
)) {
226 struct commit_graph
*load_commit_graph_one_fd_st(int fd
, struct stat
*st
,
227 struct object_directory
*odb
)
231 struct commit_graph
*ret
;
233 graph_size
= xsize_t(st
->st_size
);
235 if (graph_size
< GRAPH_MIN_SIZE
) {
237 error(_("commit-graph file is too small"));
240 graph_map
= xmmap(NULL
, graph_size
, PROT_READ
, MAP_PRIVATE
, fd
, 0);
242 ret
= parse_commit_graph(graph_map
, graph_size
);
247 munmap(graph_map
, graph_size
);
252 static int verify_commit_graph_lite(struct commit_graph
*g
)
255 * Basic validation shared between parse_commit_graph()
256 * which'll be called every time the graph is used, and the
257 * much more expensive verify_commit_graph() used by
258 * "commit-graph verify".
260 * There should only be very basic checks here to ensure that
261 * we don't e.g. segfault in fill_commit_in_graph(), but
262 * because this is a very hot codepath nothing that e.g. loops
263 * over g->num_commits, or runs a checksum on the commit-graph
266 if (!g
->chunk_oid_fanout
) {
267 error("commit-graph is missing the OID Fanout chunk");
270 if (!g
->chunk_oid_lookup
) {
271 error("commit-graph is missing the OID Lookup chunk");
274 if (!g
->chunk_commit_data
) {
275 error("commit-graph is missing the Commit Data chunk");
282 struct commit_graph
*parse_commit_graph(void *graph_map
, size_t graph_size
)
284 const unsigned char *data
, *chunk_lookup
;
286 struct commit_graph
*graph
;
287 uint64_t last_chunk_offset
;
288 uint32_t last_chunk_id
;
289 uint32_t graph_signature
;
290 unsigned char graph_version
, hash_version
;
295 if (graph_size
< GRAPH_MIN_SIZE
)
298 data
= (const unsigned char *)graph_map
;
300 graph_signature
= get_be32(data
);
301 if (graph_signature
!= GRAPH_SIGNATURE
) {
302 error(_("commit-graph signature %X does not match signature %X"),
303 graph_signature
, GRAPH_SIGNATURE
);
307 graph_version
= *(unsigned char*)(data
+ 4);
308 if (graph_version
!= GRAPH_VERSION
) {
309 error(_("commit-graph version %X does not match version %X"),
310 graph_version
, GRAPH_VERSION
);
314 hash_version
= *(unsigned char*)(data
+ 5);
315 if (hash_version
!= oid_version()) {
316 error(_("commit-graph hash version %X does not match version %X"),
317 hash_version
, oid_version());
321 graph
= alloc_commit_graph();
323 graph
->hash_len
= the_hash_algo
->rawsz
;
324 graph
->num_chunks
= *(unsigned char*)(data
+ 6);
325 graph
->data
= graph_map
;
326 graph
->data_len
= graph_size
;
329 last_chunk_offset
= 8;
330 chunk_lookup
= data
+ 8;
331 for (i
= 0; i
< graph
->num_chunks
; i
++) {
333 uint64_t chunk_offset
;
334 int chunk_repeated
= 0;
336 if (data
+ graph_size
- chunk_lookup
<
337 GRAPH_CHUNKLOOKUP_WIDTH
) {
338 error(_("commit-graph chunk lookup table entry missing; file may be incomplete"));
339 goto free_and_return
;
342 chunk_id
= get_be32(chunk_lookup
+ 0);
343 chunk_offset
= get_be64(chunk_lookup
+ 4);
345 chunk_lookup
+= GRAPH_CHUNKLOOKUP_WIDTH
;
347 if (chunk_offset
> graph_size
- the_hash_algo
->rawsz
) {
348 error(_("commit-graph improper chunk offset %08x%08x"), (uint32_t)(chunk_offset
>> 32),
349 (uint32_t)chunk_offset
);
350 goto free_and_return
;
354 case GRAPH_CHUNKID_OIDFANOUT
:
355 if (graph
->chunk_oid_fanout
)
358 graph
->chunk_oid_fanout
= (uint32_t*)(data
+ chunk_offset
);
361 case GRAPH_CHUNKID_OIDLOOKUP
:
362 if (graph
->chunk_oid_lookup
)
365 graph
->chunk_oid_lookup
= data
+ chunk_offset
;
368 case GRAPH_CHUNKID_DATA
:
369 if (graph
->chunk_commit_data
)
372 graph
->chunk_commit_data
= data
+ chunk_offset
;
375 case GRAPH_CHUNKID_EXTRAEDGES
:
376 if (graph
->chunk_extra_edges
)
379 graph
->chunk_extra_edges
= data
+ chunk_offset
;
382 case GRAPH_CHUNKID_BASE
:
383 if (graph
->chunk_base_graphs
)
386 graph
->chunk_base_graphs
= data
+ chunk_offset
;
389 case GRAPH_CHUNKID_BLOOMINDEXES
:
390 if (graph
->chunk_bloom_indexes
)
393 graph
->chunk_bloom_indexes
= data
+ chunk_offset
;
396 case GRAPH_CHUNKID_BLOOMDATA
:
397 if (graph
->chunk_bloom_data
)
400 uint32_t hash_version
;
401 graph
->chunk_bloom_data
= data
+ chunk_offset
;
402 hash_version
= get_be32(data
+ chunk_offset
);
404 if (hash_version
!= 1)
407 graph
->bloom_filter_settings
= xmalloc(sizeof(struct bloom_filter_settings
));
408 graph
->bloom_filter_settings
->hash_version
= hash_version
;
409 graph
->bloom_filter_settings
->num_hashes
= get_be32(data
+ chunk_offset
+ 4);
410 graph
->bloom_filter_settings
->bits_per_entry
= get_be32(data
+ chunk_offset
+ 8);
415 if (chunk_repeated
) {
416 error(_("commit-graph chunk id %08x appears multiple times"), chunk_id
);
417 goto free_and_return
;
420 if (last_chunk_id
== GRAPH_CHUNKID_OIDLOOKUP
)
422 graph
->num_commits
= (chunk_offset
- last_chunk_offset
)
426 last_chunk_id
= chunk_id
;
427 last_chunk_offset
= chunk_offset
;
430 if (graph
->chunk_bloom_indexes
&& graph
->chunk_bloom_data
) {
431 init_bloom_filters();
433 /* We need both the bloom chunks to exist together. Else ignore the data */
434 graph
->chunk_bloom_indexes
= NULL
;
435 graph
->chunk_bloom_data
= NULL
;
436 FREE_AND_NULL(graph
->bloom_filter_settings
);
439 hashcpy(graph
->oid
.hash
, graph
->data
+ graph
->data_len
- graph
->hash_len
);
441 if (verify_commit_graph_lite(graph
))
442 goto free_and_return
;
447 free(graph
->bloom_filter_settings
);
452 static struct commit_graph
*load_commit_graph_one(const char *graph_file
,
453 struct object_directory
*odb
)
458 struct commit_graph
*g
;
459 int open_ok
= open_commit_graph(graph_file
, &fd
, &st
);
464 g
= load_commit_graph_one_fd_st(fd
, &st
, odb
);
467 g
->filename
= xstrdup(graph_file
);
472 static struct commit_graph
*load_commit_graph_v1(struct repository
*r
,
473 struct object_directory
*odb
)
475 char *graph_name
= get_commit_graph_filename(odb
);
476 struct commit_graph
*g
= load_commit_graph_one(graph_name
, odb
);
482 static int add_graph_to_chain(struct commit_graph
*g
,
483 struct commit_graph
*chain
,
484 struct object_id
*oids
,
487 struct commit_graph
*cur_g
= chain
;
489 if (n
&& !g
->chunk_base_graphs
) {
490 warning(_("commit-graph has no base graphs chunk"));
498 !oideq(&oids
[n
], &cur_g
->oid
) ||
499 !hasheq(oids
[n
].hash
, g
->chunk_base_graphs
+ g
->hash_len
* n
)) {
500 warning(_("commit-graph chain does not match"));
504 cur_g
= cur_g
->base_graph
;
507 g
->base_graph
= chain
;
510 g
->num_commits_in_base
= chain
->num_commits
+ chain
->num_commits_in_base
;
515 static struct commit_graph
*load_commit_graph_chain(struct repository
*r
,
516 struct object_directory
*odb
)
518 struct commit_graph
*graph_chain
= NULL
;
519 struct strbuf line
= STRBUF_INIT
;
521 struct object_id
*oids
;
522 int i
= 0, valid
= 1, count
;
523 char *chain_name
= get_chain_filename(odb
);
527 fp
= fopen(chain_name
, "r");
528 stat_res
= stat(chain_name
, &st
);
533 st
.st_size
<= the_hash_algo
->hexsz
)
536 count
= st
.st_size
/ (the_hash_algo
->hexsz
+ 1);
537 oids
= xcalloc(count
, sizeof(struct object_id
));
541 for (i
= 0; i
< count
; i
++) {
542 struct object_directory
*odb
;
544 if (strbuf_getline_lf(&line
, fp
) == EOF
)
547 if (get_oid_hex(line
.buf
, &oids
[i
])) {
548 warning(_("invalid commit-graph chain: line '%s' not a hash"),
555 for (odb
= r
->objects
->odb
; odb
; odb
= odb
->next
) {
556 char *graph_name
= get_split_graph_filename(odb
, line
.buf
);
557 struct commit_graph
*g
= load_commit_graph_one(graph_name
, odb
);
562 if (add_graph_to_chain(g
, graph_chain
, oids
, i
)) {
572 warning(_("unable to find all commit-graph files"));
579 strbuf_release(&line
);
584 struct commit_graph
*read_commit_graph_one(struct repository
*r
,
585 struct object_directory
*odb
)
587 struct commit_graph
*g
= load_commit_graph_v1(r
, odb
);
590 g
= load_commit_graph_chain(r
, odb
);
595 static void prepare_commit_graph_one(struct repository
*r
,
596 struct object_directory
*odb
)
599 if (r
->objects
->commit_graph
)
602 r
->objects
->commit_graph
= read_commit_graph_one(r
, odb
);
606 * Return 1 if commit_graph is non-NULL, and 0 otherwise.
608 * On the first invocation, this function attempts to load the commit
609 * graph if the_repository is configured to have one.
611 static int prepare_commit_graph(struct repository
*r
)
613 struct object_directory
*odb
;
616 * This must come before the "already attempted?" check below, because
617 * we want to disable even an already-loaded graph file.
619 if (r
->commit_graph_disabled
)
622 if (r
->objects
->commit_graph_attempted
)
623 return !!r
->objects
->commit_graph
;
624 r
->objects
->commit_graph_attempted
= 1;
626 if (git_env_bool(GIT_TEST_COMMIT_GRAPH_DIE_ON_LOAD
, 0))
627 die("dying as requested by the '%s' variable on commit-graph load!",
628 GIT_TEST_COMMIT_GRAPH_DIE_ON_LOAD
);
630 prepare_repo_settings(r
);
632 if (!git_env_bool(GIT_TEST_COMMIT_GRAPH
, 0) &&
633 r
->settings
.core_commit_graph
!= 1)
635 * This repository is not configured to use commit graphs, so
636 * do not load one. (But report commit_graph_attempted anyway
637 * so that commit graph loading is not attempted again for this
642 if (!commit_graph_compatible(r
))
646 for (odb
= r
->objects
->odb
;
647 !r
->objects
->commit_graph
&& odb
;
649 prepare_commit_graph_one(r
, odb
);
650 return !!r
->objects
->commit_graph
;
653 int generation_numbers_enabled(struct repository
*r
)
655 uint32_t first_generation
;
656 struct commit_graph
*g
;
657 if (!prepare_commit_graph(r
))
660 g
= r
->objects
->commit_graph
;
665 first_generation
= get_be32(g
->chunk_commit_data
+
666 g
->hash_len
+ 8) >> 2;
668 return !!first_generation
;
671 static void close_commit_graph_one(struct commit_graph
*g
)
676 close_commit_graph_one(g
->base_graph
);
677 free_commit_graph(g
);
680 void close_commit_graph(struct raw_object_store
*o
)
682 close_commit_graph_one(o
->commit_graph
);
683 o
->commit_graph
= NULL
;
686 static int bsearch_graph(struct commit_graph
*g
, struct object_id
*oid
, uint32_t *pos
)
688 return bsearch_hash(oid
->hash
, g
->chunk_oid_fanout
,
689 g
->chunk_oid_lookup
, g
->hash_len
, pos
);
692 static void load_oid_from_graph(struct commit_graph
*g
,
694 struct object_id
*oid
)
698 while (g
&& pos
< g
->num_commits_in_base
)
702 BUG("NULL commit-graph");
704 if (pos
>= g
->num_commits
+ g
->num_commits_in_base
)
705 die(_("invalid commit position. commit-graph is likely corrupt"));
707 lex_index
= pos
- g
->num_commits_in_base
;
709 hashcpy(oid
->hash
, g
->chunk_oid_lookup
+ g
->hash_len
* lex_index
);
712 static struct commit_list
**insert_parent_or_die(struct repository
*r
,
713 struct commit_graph
*g
,
715 struct commit_list
**pptr
)
718 struct object_id oid
;
720 if (pos
>= g
->num_commits
+ g
->num_commits_in_base
)
721 die("invalid parent position %"PRIu32
, pos
);
723 load_oid_from_graph(g
, pos
, &oid
);
724 c
= lookup_commit(r
, &oid
);
726 die(_("could not find commit %s"), oid_to_hex(&oid
));
727 commit_graph_data_at(c
)->graph_pos
= pos
;
728 return &commit_list_insert(c
, pptr
)->next
;
731 static void fill_commit_graph_info(struct commit
*item
, struct commit_graph
*g
, uint32_t pos
)
733 const unsigned char *commit_data
;
734 struct commit_graph_data
*graph_data
;
737 while (pos
< g
->num_commits_in_base
)
740 lex_index
= pos
- g
->num_commits_in_base
;
741 commit_data
= g
->chunk_commit_data
+ GRAPH_DATA_WIDTH
* lex_index
;
743 graph_data
= commit_graph_data_at(item
);
744 graph_data
->graph_pos
= pos
;
745 graph_data
->generation
= get_be32(commit_data
+ g
->hash_len
+ 8) >> 2;
748 static inline void set_commit_tree(struct commit
*c
, struct tree
*t
)
753 static int fill_commit_in_graph(struct repository
*r
,
755 struct commit_graph
*g
, uint32_t pos
)
758 uint32_t *parent_data_ptr
;
759 uint64_t date_low
, date_high
;
760 struct commit_list
**pptr
;
761 struct commit_graph_data
*graph_data
;
762 const unsigned char *commit_data
;
765 while (pos
< g
->num_commits_in_base
)
768 if (pos
>= g
->num_commits
+ g
->num_commits_in_base
)
769 die(_("invalid commit position. commit-graph is likely corrupt"));
772 * Store the "full" position, but then use the
773 * "local" position for the rest of the calculation.
775 graph_data
= commit_graph_data_at(item
);
776 graph_data
->graph_pos
= pos
;
777 lex_index
= pos
- g
->num_commits_in_base
;
779 commit_data
= g
->chunk_commit_data
+ (g
->hash_len
+ 16) * lex_index
;
781 item
->object
.parsed
= 1;
783 set_commit_tree(item
, NULL
);
785 date_high
= get_be32(commit_data
+ g
->hash_len
+ 8) & 0x3;
786 date_low
= get_be32(commit_data
+ g
->hash_len
+ 12);
787 item
->date
= (timestamp_t
)((date_high
<< 32) | date_low
);
789 graph_data
->generation
= get_be32(commit_data
+ g
->hash_len
+ 8) >> 2;
791 pptr
= &item
->parents
;
793 edge_value
= get_be32(commit_data
+ g
->hash_len
);
794 if (edge_value
== GRAPH_PARENT_NONE
)
796 pptr
= insert_parent_or_die(r
, g
, edge_value
, pptr
);
798 edge_value
= get_be32(commit_data
+ g
->hash_len
+ 4);
799 if (edge_value
== GRAPH_PARENT_NONE
)
801 if (!(edge_value
& GRAPH_EXTRA_EDGES_NEEDED
)) {
802 pptr
= insert_parent_or_die(r
, g
, edge_value
, pptr
);
806 parent_data_ptr
= (uint32_t*)(g
->chunk_extra_edges
+
807 4 * (uint64_t)(edge_value
& GRAPH_EDGE_LAST_MASK
));
809 edge_value
= get_be32(parent_data_ptr
);
810 pptr
= insert_parent_or_die(r
, g
,
811 edge_value
& GRAPH_EDGE_LAST_MASK
,
814 } while (!(edge_value
& GRAPH_LAST_EDGE
));
819 static int find_commit_in_graph(struct commit
*item
, struct commit_graph
*g
, uint32_t *pos
)
821 uint32_t graph_pos
= commit_graph_position(item
);
822 if (graph_pos
!= COMMIT_NOT_FROM_GRAPH
) {
826 struct commit_graph
*cur_g
= g
;
829 while (cur_g
&& !bsearch_graph(cur_g
, &(item
->object
.oid
), &lex_index
))
830 cur_g
= cur_g
->base_graph
;
833 *pos
= lex_index
+ cur_g
->num_commits_in_base
;
841 static int parse_commit_in_graph_one(struct repository
*r
,
842 struct commit_graph
*g
,
847 if (item
->object
.parsed
)
850 if (find_commit_in_graph(item
, g
, &pos
))
851 return fill_commit_in_graph(r
, item
, g
, pos
);
856 int parse_commit_in_graph(struct repository
*r
, struct commit
*item
)
858 if (!prepare_commit_graph(r
))
860 return parse_commit_in_graph_one(r
, r
->objects
->commit_graph
, item
);
863 void load_commit_graph_info(struct repository
*r
, struct commit
*item
)
866 if (!prepare_commit_graph(r
))
868 if (find_commit_in_graph(item
, r
->objects
->commit_graph
, &pos
))
869 fill_commit_graph_info(item
, r
->objects
->commit_graph
, pos
);
872 static struct tree
*load_tree_for_commit(struct repository
*r
,
873 struct commit_graph
*g
,
876 struct object_id oid
;
877 const unsigned char *commit_data
;
878 uint32_t graph_pos
= commit_graph_position(c
);
880 while (graph_pos
< g
->num_commits_in_base
)
883 commit_data
= g
->chunk_commit_data
+
884 GRAPH_DATA_WIDTH
* (graph_pos
- g
->num_commits_in_base
);
886 hashcpy(oid
.hash
, commit_data
);
887 set_commit_tree(c
, lookup_tree(r
, &oid
));
889 return c
->maybe_tree
;
892 static struct tree
*get_commit_tree_in_graph_one(struct repository
*r
,
893 struct commit_graph
*g
,
894 const struct commit
*c
)
897 return c
->maybe_tree
;
898 if (commit_graph_position(c
) == COMMIT_NOT_FROM_GRAPH
)
899 BUG("get_commit_tree_in_graph_one called from non-commit-graph commit");
901 return load_tree_for_commit(r
, g
, (struct commit
*)c
);
904 struct tree
*get_commit_tree_in_graph(struct repository
*r
, const struct commit
*c
)
906 return get_commit_tree_in_graph_one(r
, r
->objects
->commit_graph
, c
);
909 struct packed_commit_list
{
910 struct commit
**list
;
915 struct packed_oid_list
{
916 struct object_id
*list
;
921 struct write_commit_graph_context
{
922 struct repository
*r
;
923 struct object_directory
*odb
;
925 struct packed_oid_list oids
;
926 struct packed_commit_list commits
;
928 unsigned long approx_nr_objects
;
929 struct progress
*progress
;
931 uint64_t progress_cnt
;
933 char *base_graph_name
;
934 int num_commit_graphs_before
;
935 int num_commit_graphs_after
;
936 char **commit_graph_filenames_before
;
937 char **commit_graph_filenames_after
;
938 char **commit_graph_hash_after
;
939 uint32_t new_num_commits_in_base
;
940 struct commit_graph
*new_base_graph
;
948 const struct split_commit_graph_opts
*split_opts
;
949 size_t total_bloom_filter_data_size
;
952 static void write_graph_chunk_fanout(struct hashfile
*f
,
953 struct write_commit_graph_context
*ctx
)
956 struct commit
**list
= ctx
->commits
.list
;
959 * Write the first-level table (the list is sorted,
960 * but we use a 256-entry lookup to be able to avoid
961 * having to do eight extra binary search iterations).
963 for (i
= 0; i
< 256; i
++) {
964 while (count
< ctx
->commits
.nr
) {
965 if ((*list
)->object
.oid
.hash
[0] != i
)
967 display_progress(ctx
->progress
, ++ctx
->progress_cnt
);
972 hashwrite_be32(f
, count
);
976 static void write_graph_chunk_oids(struct hashfile
*f
, int hash_len
,
977 struct write_commit_graph_context
*ctx
)
979 struct commit
**list
= ctx
->commits
.list
;
981 for (count
= 0; count
< ctx
->commits
.nr
; count
++, list
++) {
982 display_progress(ctx
->progress
, ++ctx
->progress_cnt
);
983 hashwrite(f
, (*list
)->object
.oid
.hash
, (int)hash_len
);
987 static const unsigned char *commit_to_sha1(size_t index
, void *table
)
989 struct commit
**commits
= table
;
990 return commits
[index
]->object
.oid
.hash
;
993 static void write_graph_chunk_data(struct hashfile
*f
, int hash_len
,
994 struct write_commit_graph_context
*ctx
)
996 struct commit
**list
= ctx
->commits
.list
;
997 struct commit
**last
= ctx
->commits
.list
+ ctx
->commits
.nr
;
998 uint32_t num_extra_edges
= 0;
1000 while (list
< last
) {
1001 struct commit_list
*parent
;
1002 struct object_id
*tree
;
1004 uint32_t packedDate
[2];
1005 display_progress(ctx
->progress
, ++ctx
->progress_cnt
);
1007 if (parse_commit_no_graph(*list
))
1008 die(_("unable to parse commit %s"),
1009 oid_to_hex(&(*list
)->object
.oid
));
1010 tree
= get_commit_tree_oid(*list
);
1011 hashwrite(f
, tree
->hash
, hash_len
);
1013 parent
= (*list
)->parents
;
1016 edge_value
= GRAPH_PARENT_NONE
;
1018 edge_value
= sha1_pos(parent
->item
->object
.oid
.hash
,
1023 if (edge_value
>= 0)
1024 edge_value
+= ctx
->new_num_commits_in_base
;
1025 else if (ctx
->new_base_graph
) {
1027 if (find_commit_in_graph(parent
->item
,
1028 ctx
->new_base_graph
,
1034 BUG("missing parent %s for commit %s",
1035 oid_to_hex(&parent
->item
->object
.oid
),
1036 oid_to_hex(&(*list
)->object
.oid
));
1039 hashwrite_be32(f
, edge_value
);
1042 parent
= parent
->next
;
1045 edge_value
= GRAPH_PARENT_NONE
;
1046 else if (parent
->next
)
1047 edge_value
= GRAPH_EXTRA_EDGES_NEEDED
| num_extra_edges
;
1049 edge_value
= sha1_pos(parent
->item
->object
.oid
.hash
,
1054 if (edge_value
>= 0)
1055 edge_value
+= ctx
->new_num_commits_in_base
;
1056 else if (ctx
->new_base_graph
) {
1058 if (find_commit_in_graph(parent
->item
,
1059 ctx
->new_base_graph
,
1065 BUG("missing parent %s for commit %s",
1066 oid_to_hex(&parent
->item
->object
.oid
),
1067 oid_to_hex(&(*list
)->object
.oid
));
1070 hashwrite_be32(f
, edge_value
);
1072 if (edge_value
& GRAPH_EXTRA_EDGES_NEEDED
) {
1075 parent
= parent
->next
;
1079 if (sizeof((*list
)->date
) > 4)
1080 packedDate
[0] = htonl(((*list
)->date
>> 32) & 0x3);
1084 packedDate
[0] |= htonl(commit_graph_data_at(*list
)->generation
<< 2);
1086 packedDate
[1] = htonl((*list
)->date
);
1087 hashwrite(f
, packedDate
, 8);
1093 static void write_graph_chunk_extra_edges(struct hashfile
*f
,
1094 struct write_commit_graph_context
*ctx
)
1096 struct commit
**list
= ctx
->commits
.list
;
1097 struct commit
**last
= ctx
->commits
.list
+ ctx
->commits
.nr
;
1098 struct commit_list
*parent
;
1100 while (list
< last
) {
1101 int num_parents
= 0;
1103 display_progress(ctx
->progress
, ++ctx
->progress_cnt
);
1105 for (parent
= (*list
)->parents
; num_parents
< 3 && parent
;
1106 parent
= parent
->next
)
1109 if (num_parents
<= 2) {
1114 /* Since num_parents > 2, this initializer is safe. */
1115 for (parent
= (*list
)->parents
->next
; parent
; parent
= parent
->next
) {
1116 int edge_value
= sha1_pos(parent
->item
->object
.oid
.hash
,
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
));
1135 else if (!parent
->next
)
1136 edge_value
|= GRAPH_LAST_EDGE
;
1138 hashwrite_be32(f
, edge_value
);
1145 static void write_graph_chunk_bloom_indexes(struct hashfile
*f
,
1146 struct write_commit_graph_context
*ctx
)
1148 struct commit
**list
= ctx
->commits
.list
;
1149 struct commit
**last
= ctx
->commits
.list
+ ctx
->commits
.nr
;
1150 uint32_t cur_pos
= 0;
1151 struct progress
*progress
= NULL
;
1154 if (ctx
->report_progress
)
1155 progress
= start_delayed_progress(
1156 _("Writing changed paths Bloom filters index"),
1159 while (list
< last
) {
1160 struct bloom_filter
*filter
= get_bloom_filter(ctx
->r
, *list
, 0);
1161 cur_pos
+= filter
->len
;
1162 display_progress(progress
, ++i
);
1163 hashwrite_be32(f
, cur_pos
);
1167 stop_progress(&progress
);
1170 static void write_graph_chunk_bloom_data(struct hashfile
*f
,
1171 struct write_commit_graph_context
*ctx
,
1172 const struct bloom_filter_settings
*settings
)
1174 struct commit
**list
= ctx
->commits
.list
;
1175 struct commit
**last
= ctx
->commits
.list
+ ctx
->commits
.nr
;
1176 struct progress
*progress
= NULL
;
1179 if (ctx
->report_progress
)
1180 progress
= start_delayed_progress(
1181 _("Writing changed paths Bloom filters data"),
1184 hashwrite_be32(f
, settings
->hash_version
);
1185 hashwrite_be32(f
, settings
->num_hashes
);
1186 hashwrite_be32(f
, settings
->bits_per_entry
);
1188 while (list
< last
) {
1189 struct bloom_filter
*filter
= get_bloom_filter(ctx
->r
, *list
, 0);
1190 display_progress(progress
, ++i
);
1191 hashwrite(f
, filter
->data
, filter
->len
* sizeof(unsigned char));
1195 stop_progress(&progress
);
1198 static int oid_compare(const void *_a
, const void *_b
)
1200 const struct object_id
*a
= (const struct object_id
*)_a
;
1201 const struct object_id
*b
= (const struct object_id
*)_b
;
1202 return oidcmp(a
, b
);
1205 static int add_packed_commits(const struct object_id
*oid
,
1206 struct packed_git
*pack
,
1210 struct write_commit_graph_context
*ctx
= (struct write_commit_graph_context
*)data
;
1211 enum object_type type
;
1212 off_t offset
= nth_packed_object_offset(pack
, pos
);
1213 struct object_info oi
= OBJECT_INFO_INIT
;
1216 display_progress(ctx
->progress
, ++ctx
->progress_done
);
1219 if (packed_object_info(ctx
->r
, pack
, offset
, &oi
) < 0)
1220 die(_("unable to get type of object %s"), oid_to_hex(oid
));
1222 if (type
!= OBJ_COMMIT
)
1225 ALLOC_GROW(ctx
->oids
.list
, ctx
->oids
.nr
+ 1, ctx
->oids
.alloc
);
1226 oidcpy(&(ctx
->oids
.list
[ctx
->oids
.nr
]), oid
);
1229 set_commit_pos(ctx
->r
, oid
);
1234 static void add_missing_parents(struct write_commit_graph_context
*ctx
, struct commit
*commit
)
1236 struct commit_list
*parent
;
1237 for (parent
= commit
->parents
; parent
; parent
= parent
->next
) {
1238 if (!(parent
->item
->object
.flags
& REACHABLE
)) {
1239 ALLOC_GROW(ctx
->oids
.list
, ctx
->oids
.nr
+ 1, ctx
->oids
.alloc
);
1240 oidcpy(&ctx
->oids
.list
[ctx
->oids
.nr
], &(parent
->item
->object
.oid
));
1242 parent
->item
->object
.flags
|= REACHABLE
;
1247 static void close_reachable(struct write_commit_graph_context
*ctx
)
1250 struct commit
*commit
;
1251 enum commit_graph_split_flags flags
= ctx
->split_opts
?
1252 ctx
->split_opts
->flags
: COMMIT_GRAPH_SPLIT_UNSPECIFIED
;
1254 if (ctx
->report_progress
)
1255 ctx
->progress
= start_delayed_progress(
1256 _("Loading known commits in commit graph"),
1258 for (i
= 0; i
< ctx
->oids
.nr
; i
++) {
1259 display_progress(ctx
->progress
, i
+ 1);
1260 commit
= lookup_commit(ctx
->r
, &ctx
->oids
.list
[i
]);
1262 commit
->object
.flags
|= REACHABLE
;
1264 stop_progress(&ctx
->progress
);
1267 * As this loop runs, ctx->oids.nr may grow, but not more
1268 * than the number of missing commits in the reachable
1271 if (ctx
->report_progress
)
1272 ctx
->progress
= start_delayed_progress(
1273 _("Expanding reachable commits in commit graph"),
1275 for (i
= 0; i
< ctx
->oids
.nr
; i
++) {
1276 display_progress(ctx
->progress
, i
+ 1);
1277 commit
= lookup_commit(ctx
->r
, &ctx
->oids
.list
[i
]);
1282 if ((!parse_commit(commit
) &&
1283 commit_graph_position(commit
) == COMMIT_NOT_FROM_GRAPH
) ||
1284 flags
== COMMIT_GRAPH_SPLIT_REPLACE
)
1285 add_missing_parents(ctx
, commit
);
1286 } else if (!parse_commit_no_graph(commit
))
1287 add_missing_parents(ctx
, commit
);
1289 stop_progress(&ctx
->progress
);
1291 if (ctx
->report_progress
)
1292 ctx
->progress
= start_delayed_progress(
1293 _("Clearing commit marks in commit graph"),
1295 for (i
= 0; i
< ctx
->oids
.nr
; i
++) {
1296 display_progress(ctx
->progress
, i
+ 1);
1297 commit
= lookup_commit(ctx
->r
, &ctx
->oids
.list
[i
]);
1300 commit
->object
.flags
&= ~REACHABLE
;
1302 stop_progress(&ctx
->progress
);
1305 static void compute_generation_numbers(struct write_commit_graph_context
*ctx
)
1308 struct commit_list
*list
= NULL
;
1310 if (ctx
->report_progress
)
1311 ctx
->progress
= start_delayed_progress(
1312 _("Computing commit graph generation numbers"),
1314 for (i
= 0; i
< ctx
->commits
.nr
; i
++) {
1315 uint32_t generation
= commit_graph_data_at(ctx
->commits
.list
[i
])->generation
;
1317 display_progress(ctx
->progress
, i
+ 1);
1318 if (generation
!= GENERATION_NUMBER_INFINITY
&&
1319 generation
!= GENERATION_NUMBER_ZERO
)
1322 commit_list_insert(ctx
->commits
.list
[i
], &list
);
1324 struct commit
*current
= list
->item
;
1325 struct commit_list
*parent
;
1326 int all_parents_computed
= 1;
1327 uint32_t max_generation
= 0;
1329 for (parent
= current
->parents
; parent
; parent
= parent
->next
) {
1330 generation
= commit_graph_data_at(parent
->item
)->generation
;
1332 if (generation
== GENERATION_NUMBER_INFINITY
||
1333 generation
== GENERATION_NUMBER_ZERO
) {
1334 all_parents_computed
= 0;
1335 commit_list_insert(parent
->item
, &list
);
1337 } else if (generation
> max_generation
) {
1338 max_generation
= generation
;
1342 if (all_parents_computed
) {
1343 struct commit_graph_data
*data
= commit_graph_data_at(current
);
1345 data
->generation
= max_generation
+ 1;
1348 if (data
->generation
> GENERATION_NUMBER_MAX
)
1349 data
->generation
= GENERATION_NUMBER_MAX
;
1353 stop_progress(&ctx
->progress
);
1356 static void compute_bloom_filters(struct write_commit_graph_context
*ctx
)
1359 struct progress
*progress
= NULL
;
1360 struct commit
**sorted_commits
;
1362 init_bloom_filters();
1364 if (ctx
->report_progress
)
1365 progress
= start_delayed_progress(
1366 _("Computing commit changed paths Bloom filters"),
1369 ALLOC_ARRAY(sorted_commits
, ctx
->commits
.nr
);
1370 COPY_ARRAY(sorted_commits
, ctx
->commits
.list
, ctx
->commits
.nr
);
1372 if (ctx
->order_by_pack
)
1373 QSORT(sorted_commits
, ctx
->commits
.nr
, commit_pos_cmp
);
1375 QSORT(sorted_commits
, ctx
->commits
.nr
, commit_gen_cmp
);
1377 for (i
= 0; i
< ctx
->commits
.nr
; i
++) {
1378 struct commit
*c
= sorted_commits
[i
];
1379 struct bloom_filter
*filter
= get_bloom_filter(ctx
->r
, c
, 1);
1380 ctx
->total_bloom_filter_data_size
+= sizeof(unsigned char) * filter
->len
;
1381 display_progress(progress
, i
+ 1);
1384 free(sorted_commits
);
1385 stop_progress(&progress
);
1388 struct refs_cb_data
{
1389 struct oidset
*commits
;
1390 struct progress
*progress
;
1393 static int add_ref_to_set(const char *refname
,
1394 const struct object_id
*oid
,
1395 int flags
, void *cb_data
)
1397 struct object_id peeled
;
1398 struct refs_cb_data
*data
= (struct refs_cb_data
*)cb_data
;
1400 if (!peel_ref(refname
, &peeled
))
1402 if (oid_object_info(the_repository
, oid
, NULL
) == OBJ_COMMIT
)
1403 oidset_insert(data
->commits
, oid
);
1405 display_progress(data
->progress
, oidset_size(data
->commits
));
1410 int write_commit_graph_reachable(struct object_directory
*odb
,
1411 enum commit_graph_write_flags flags
,
1412 const struct split_commit_graph_opts
*split_opts
)
1414 struct oidset commits
= OIDSET_INIT
;
1415 struct refs_cb_data data
;
1418 memset(&data
, 0, sizeof(data
));
1419 data
.commits
= &commits
;
1420 if (flags
& COMMIT_GRAPH_WRITE_PROGRESS
)
1421 data
.progress
= start_delayed_progress(
1422 _("Collecting referenced commits"), 0);
1424 for_each_ref(add_ref_to_set
, &data
);
1425 result
= write_commit_graph(odb
, NULL
, &commits
,
1428 oidset_clear(&commits
);
1430 stop_progress(&data
.progress
);
1434 static int fill_oids_from_packs(struct write_commit_graph_context
*ctx
,
1435 struct string_list
*pack_indexes
)
1438 struct strbuf progress_title
= STRBUF_INIT
;
1439 struct strbuf packname
= STRBUF_INIT
;
1442 strbuf_addf(&packname
, "%s/pack/", ctx
->odb
->path
);
1443 dirlen
= packname
.len
;
1444 if (ctx
->report_progress
) {
1445 strbuf_addf(&progress_title
,
1446 Q_("Finding commits for commit graph in %d pack",
1447 "Finding commits for commit graph in %d packs",
1450 ctx
->progress
= start_delayed_progress(progress_title
.buf
, 0);
1451 ctx
->progress_done
= 0;
1453 for (i
= 0; i
< pack_indexes
->nr
; i
++) {
1454 struct packed_git
*p
;
1455 strbuf_setlen(&packname
, dirlen
);
1456 strbuf_addstr(&packname
, pack_indexes
->items
[i
].string
);
1457 p
= add_packed_git(packname
.buf
, packname
.len
, 1);
1459 error(_("error adding pack %s"), packname
.buf
);
1462 if (open_pack_index(p
)) {
1463 error(_("error opening index for %s"), packname
.buf
);
1466 for_each_object_in_pack(p
, add_packed_commits
, ctx
,
1467 FOR_EACH_OBJECT_PACK_ORDER
);
1472 stop_progress(&ctx
->progress
);
1473 strbuf_release(&progress_title
);
1474 strbuf_release(&packname
);
1479 static int fill_oids_from_commits(struct write_commit_graph_context
*ctx
,
1480 struct oidset
*commits
)
1482 struct oidset_iter iter
;
1483 struct object_id
*oid
;
1485 if (!oidset_size(commits
))
1488 oidset_iter_init(commits
, &iter
);
1489 while ((oid
= oidset_iter_next(&iter
))) {
1490 ALLOC_GROW(ctx
->oids
.list
, ctx
->oids
.nr
+ 1, ctx
->oids
.alloc
);
1491 oidcpy(&ctx
->oids
.list
[ctx
->oids
.nr
], oid
);
1498 static void fill_oids_from_all_packs(struct write_commit_graph_context
*ctx
)
1500 if (ctx
->report_progress
)
1501 ctx
->progress
= start_delayed_progress(
1502 _("Finding commits for commit graph among packed objects"),
1503 ctx
->approx_nr_objects
);
1504 for_each_packed_object(add_packed_commits
, ctx
,
1505 FOR_EACH_OBJECT_PACK_ORDER
);
1506 if (ctx
->progress_done
< ctx
->approx_nr_objects
)
1507 display_progress(ctx
->progress
, ctx
->approx_nr_objects
);
1508 stop_progress(&ctx
->progress
);
1511 static uint32_t count_distinct_commits(struct write_commit_graph_context
*ctx
)
1513 uint32_t i
, count_distinct
= 1;
1515 if (ctx
->report_progress
)
1516 ctx
->progress
= start_delayed_progress(
1517 _("Counting distinct commits in commit graph"),
1519 display_progress(ctx
->progress
, 0); /* TODO: Measure QSORT() progress */
1520 QSORT(ctx
->oids
.list
, ctx
->oids
.nr
, oid_compare
);
1522 for (i
= 1; i
< ctx
->oids
.nr
; i
++) {
1523 display_progress(ctx
->progress
, i
+ 1);
1524 if (!oideq(&ctx
->oids
.list
[i
- 1], &ctx
->oids
.list
[i
])) {
1526 struct commit
*c
= lookup_commit(ctx
->r
, &ctx
->oids
.list
[i
]);
1528 if (!c
|| commit_graph_position(c
) != COMMIT_NOT_FROM_GRAPH
)
1535 stop_progress(&ctx
->progress
);
1537 return count_distinct
;
1540 static void copy_oids_to_commits(struct write_commit_graph_context
*ctx
)
1543 enum commit_graph_split_flags flags
= ctx
->split_opts
?
1544 ctx
->split_opts
->flags
: COMMIT_GRAPH_SPLIT_UNSPECIFIED
;
1546 ctx
->num_extra_edges
= 0;
1547 if (ctx
->report_progress
)
1548 ctx
->progress
= start_delayed_progress(
1549 _("Finding extra edges in commit graph"),
1551 for (i
= 0; i
< ctx
->oids
.nr
; i
++) {
1552 unsigned int num_parents
;
1554 display_progress(ctx
->progress
, i
+ 1);
1555 if (i
> 0 && oideq(&ctx
->oids
.list
[i
- 1], &ctx
->oids
.list
[i
]))
1558 ALLOC_GROW(ctx
->commits
.list
, ctx
->commits
.nr
+ 1, ctx
->commits
.alloc
);
1559 ctx
->commits
.list
[ctx
->commits
.nr
] = lookup_commit(ctx
->r
, &ctx
->oids
.list
[i
]);
1561 if (ctx
->split
&& flags
!= COMMIT_GRAPH_SPLIT_REPLACE
&&
1562 commit_graph_position(ctx
->commits
.list
[ctx
->commits
.nr
]) != COMMIT_NOT_FROM_GRAPH
)
1565 if (ctx
->split
&& flags
== COMMIT_GRAPH_SPLIT_REPLACE
)
1566 parse_commit(ctx
->commits
.list
[ctx
->commits
.nr
]);
1568 parse_commit_no_graph(ctx
->commits
.list
[ctx
->commits
.nr
]);
1570 num_parents
= commit_list_count(ctx
->commits
.list
[ctx
->commits
.nr
]->parents
);
1571 if (num_parents
> 2)
1572 ctx
->num_extra_edges
+= num_parents
- 1;
1576 stop_progress(&ctx
->progress
);
1579 static int write_graph_chunk_base_1(struct hashfile
*f
,
1580 struct commit_graph
*g
)
1587 num
= write_graph_chunk_base_1(f
, g
->base_graph
);
1588 hashwrite(f
, g
->oid
.hash
, the_hash_algo
->rawsz
);
1592 static int write_graph_chunk_base(struct hashfile
*f
,
1593 struct write_commit_graph_context
*ctx
)
1595 int num
= write_graph_chunk_base_1(f
, ctx
->new_base_graph
);
1597 if (num
!= ctx
->num_commit_graphs_after
- 1) {
1598 error(_("failed to write correct number of base graph ids"));
1605 static int write_commit_graph_file(struct write_commit_graph_context
*ctx
)
1610 struct lock_file lk
= LOCK_INIT
;
1611 uint32_t chunk_ids
[MAX_NUM_CHUNKS
+ 1];
1612 uint64_t chunk_offsets
[MAX_NUM_CHUNKS
+ 1];
1613 const unsigned hashsz
= the_hash_algo
->rawsz
;
1614 struct strbuf progress_title
= STRBUF_INIT
;
1616 struct object_id file_hash
;
1617 const struct bloom_filter_settings bloom_settings
= DEFAULT_BLOOM_FILTER_SETTINGS
;
1620 struct strbuf tmp_file
= STRBUF_INIT
;
1622 strbuf_addf(&tmp_file
,
1623 "%s/info/commit-graphs/tmp_graph_XXXXXX",
1625 ctx
->graph_name
= strbuf_detach(&tmp_file
, NULL
);
1627 ctx
->graph_name
= get_commit_graph_filename(ctx
->odb
);
1630 if (safe_create_leading_directories(ctx
->graph_name
)) {
1631 UNLEAK(ctx
->graph_name
);
1632 error(_("unable to create leading directories of %s"),
1638 char *lock_name
= get_chain_filename(ctx
->odb
);
1640 hold_lock_file_for_update_mode(&lk
, lock_name
,
1641 LOCK_DIE_ON_ERROR
, 0444);
1643 fd
= git_mkstemp_mode(ctx
->graph_name
, 0444);
1645 error(_("unable to create temporary graph layer"));
1649 if (adjust_shared_perm(ctx
->graph_name
)) {
1650 error(_("unable to adjust shared permissions for '%s'"),
1655 f
= hashfd(fd
, ctx
->graph_name
);
1657 hold_lock_file_for_update_mode(&lk
, ctx
->graph_name
,
1658 LOCK_DIE_ON_ERROR
, 0444);
1659 fd
= lk
.tempfile
->fd
;
1660 f
= hashfd(lk
.tempfile
->fd
, lk
.tempfile
->filename
.buf
);
1663 chunk_ids
[0] = GRAPH_CHUNKID_OIDFANOUT
;
1664 chunk_ids
[1] = GRAPH_CHUNKID_OIDLOOKUP
;
1665 chunk_ids
[2] = GRAPH_CHUNKID_DATA
;
1666 if (ctx
->num_extra_edges
) {
1667 chunk_ids
[num_chunks
] = GRAPH_CHUNKID_EXTRAEDGES
;
1670 if (ctx
->changed_paths
) {
1671 chunk_ids
[num_chunks
] = GRAPH_CHUNKID_BLOOMINDEXES
;
1673 chunk_ids
[num_chunks
] = GRAPH_CHUNKID_BLOOMDATA
;
1676 if (ctx
->num_commit_graphs_after
> 1) {
1677 chunk_ids
[num_chunks
] = GRAPH_CHUNKID_BASE
;
1681 chunk_ids
[num_chunks
] = 0;
1683 chunk_offsets
[0] = 8 + (num_chunks
+ 1) * GRAPH_CHUNKLOOKUP_WIDTH
;
1684 chunk_offsets
[1] = chunk_offsets
[0] + GRAPH_FANOUT_SIZE
;
1685 chunk_offsets
[2] = chunk_offsets
[1] + hashsz
* ctx
->commits
.nr
;
1686 chunk_offsets
[3] = chunk_offsets
[2] + (hashsz
+ 16) * ctx
->commits
.nr
;
1689 if (ctx
->num_extra_edges
) {
1690 chunk_offsets
[num_chunks
+ 1] = chunk_offsets
[num_chunks
] +
1691 4 * ctx
->num_extra_edges
;
1694 if (ctx
->changed_paths
) {
1695 chunk_offsets
[num_chunks
+ 1] = chunk_offsets
[num_chunks
] +
1696 sizeof(uint32_t) * ctx
->commits
.nr
;
1699 chunk_offsets
[num_chunks
+ 1] = chunk_offsets
[num_chunks
] +
1700 sizeof(uint32_t) * 3 + ctx
->total_bloom_filter_data_size
;
1703 if (ctx
->num_commit_graphs_after
> 1) {
1704 chunk_offsets
[num_chunks
+ 1] = chunk_offsets
[num_chunks
] +
1705 hashsz
* (ctx
->num_commit_graphs_after
- 1);
1709 hashwrite_be32(f
, GRAPH_SIGNATURE
);
1711 hashwrite_u8(f
, GRAPH_VERSION
);
1712 hashwrite_u8(f
, oid_version());
1713 hashwrite_u8(f
, num_chunks
);
1714 hashwrite_u8(f
, ctx
->num_commit_graphs_after
- 1);
1716 for (i
= 0; i
<= num_chunks
; i
++) {
1717 uint32_t chunk_write
[3];
1719 chunk_write
[0] = htonl(chunk_ids
[i
]);
1720 chunk_write
[1] = htonl(chunk_offsets
[i
] >> 32);
1721 chunk_write
[2] = htonl(chunk_offsets
[i
] & 0xffffffff);
1722 hashwrite(f
, chunk_write
, 12);
1725 if (ctx
->report_progress
) {
1726 strbuf_addf(&progress_title
,
1727 Q_("Writing out commit graph in %d pass",
1728 "Writing out commit graph in %d passes",
1731 ctx
->progress
= start_delayed_progress(
1733 num_chunks
* ctx
->commits
.nr
);
1735 write_graph_chunk_fanout(f
, ctx
);
1736 write_graph_chunk_oids(f
, hashsz
, ctx
);
1737 write_graph_chunk_data(f
, hashsz
, ctx
);
1738 if (ctx
->num_extra_edges
)
1739 write_graph_chunk_extra_edges(f
, ctx
);
1740 if (ctx
->changed_paths
) {
1741 write_graph_chunk_bloom_indexes(f
, ctx
);
1742 write_graph_chunk_bloom_data(f
, ctx
, &bloom_settings
);
1744 if (ctx
->num_commit_graphs_after
> 1 &&
1745 write_graph_chunk_base(f
, ctx
)) {
1748 stop_progress(&ctx
->progress
);
1749 strbuf_release(&progress_title
);
1751 if (ctx
->split
&& ctx
->base_graph_name
&& ctx
->num_commit_graphs_after
> 1) {
1752 char *new_base_hash
= xstrdup(oid_to_hex(&ctx
->new_base_graph
->oid
));
1753 char *new_base_name
= get_split_graph_filename(ctx
->new_base_graph
->odb
, new_base_hash
);
1755 free(ctx
->commit_graph_filenames_after
[ctx
->num_commit_graphs_after
- 2]);
1756 free(ctx
->commit_graph_hash_after
[ctx
->num_commit_graphs_after
- 2]);
1757 ctx
->commit_graph_filenames_after
[ctx
->num_commit_graphs_after
- 2] = new_base_name
;
1758 ctx
->commit_graph_hash_after
[ctx
->num_commit_graphs_after
- 2] = new_base_hash
;
1761 close_commit_graph(ctx
->r
->objects
);
1762 finalize_hashfile(f
, file_hash
.hash
, CSUM_HASH_IN_STREAM
| CSUM_FSYNC
);
1765 FILE *chainf
= fdopen_lock_file(&lk
, "w");
1766 char *final_graph_name
;
1772 error(_("unable to open commit-graph chain file"));
1776 if (ctx
->base_graph_name
) {
1778 int idx
= ctx
->num_commit_graphs_after
- 1;
1779 if (ctx
->num_commit_graphs_after
> 1)
1782 dest
= ctx
->commit_graph_filenames_after
[idx
];
1784 if (strcmp(ctx
->base_graph_name
, dest
)) {
1785 result
= rename(ctx
->base_graph_name
, dest
);
1788 error(_("failed to rename base commit-graph file"));
1793 char *graph_name
= get_commit_graph_filename(ctx
->odb
);
1797 ctx
->commit_graph_hash_after
[ctx
->num_commit_graphs_after
- 1] = xstrdup(oid_to_hex(&file_hash
));
1798 final_graph_name
= get_split_graph_filename(ctx
->odb
,
1799 ctx
->commit_graph_hash_after
[ctx
->num_commit_graphs_after
- 1]);
1800 ctx
->commit_graph_filenames_after
[ctx
->num_commit_graphs_after
- 1] = final_graph_name
;
1802 result
= rename(ctx
->graph_name
, final_graph_name
);
1804 for (i
= 0; i
< ctx
->num_commit_graphs_after
; i
++)
1805 fprintf(lk
.tempfile
->fp
, "%s\n", ctx
->commit_graph_hash_after
[i
]);
1808 error(_("failed to rename temporary commit-graph file"));
1813 commit_lock_file(&lk
);
1818 static void split_graph_merge_strategy(struct write_commit_graph_context
*ctx
)
1820 struct commit_graph
*g
;
1821 uint32_t num_commits
;
1822 enum commit_graph_split_flags flags
= COMMIT_GRAPH_SPLIT_UNSPECIFIED
;
1825 int max_commits
= 0;
1828 if (ctx
->split_opts
) {
1829 max_commits
= ctx
->split_opts
->max_commits
;
1831 if (ctx
->split_opts
->size_multiple
)
1832 size_mult
= ctx
->split_opts
->size_multiple
;
1834 flags
= ctx
->split_opts
->flags
;
1837 g
= ctx
->r
->objects
->commit_graph
;
1838 num_commits
= ctx
->commits
.nr
;
1839 if (flags
== COMMIT_GRAPH_SPLIT_REPLACE
)
1840 ctx
->num_commit_graphs_after
= 1;
1842 ctx
->num_commit_graphs_after
= ctx
->num_commit_graphs_before
+ 1;
1844 if (flags
!= COMMIT_GRAPH_SPLIT_MERGE_PROHIBITED
&&
1845 flags
!= COMMIT_GRAPH_SPLIT_REPLACE
) {
1846 while (g
&& (g
->num_commits
<= size_mult
* num_commits
||
1847 (max_commits
&& num_commits
> max_commits
))) {
1848 if (g
->odb
!= ctx
->odb
)
1851 num_commits
+= g
->num_commits
;
1854 ctx
->num_commit_graphs_after
--;
1858 if (flags
!= COMMIT_GRAPH_SPLIT_REPLACE
)
1859 ctx
->new_base_graph
= g
;
1860 else if (ctx
->num_commit_graphs_after
!= 1)
1861 BUG("split_graph_merge_strategy: num_commit_graphs_after "
1862 "should be 1 with --split=replace");
1864 if (ctx
->num_commit_graphs_after
== 2) {
1865 char *old_graph_name
= get_commit_graph_filename(g
->odb
);
1867 if (!strcmp(g
->filename
, old_graph_name
) &&
1868 g
->odb
!= ctx
->odb
) {
1869 ctx
->num_commit_graphs_after
= 1;
1870 ctx
->new_base_graph
= NULL
;
1873 free(old_graph_name
);
1876 CALLOC_ARRAY(ctx
->commit_graph_filenames_after
, ctx
->num_commit_graphs_after
);
1877 CALLOC_ARRAY(ctx
->commit_graph_hash_after
, ctx
->num_commit_graphs_after
);
1879 for (i
= 0; i
< ctx
->num_commit_graphs_after
&&
1880 i
< ctx
->num_commit_graphs_before
; i
++)
1881 ctx
->commit_graph_filenames_after
[i
] = xstrdup(ctx
->commit_graph_filenames_before
[i
]);
1883 i
= ctx
->num_commit_graphs_before
- 1;
1884 g
= ctx
->r
->objects
->commit_graph
;
1887 if (i
< ctx
->num_commit_graphs_after
)
1888 ctx
->commit_graph_hash_after
[i
] = xstrdup(oid_to_hex(&g
->oid
));
1895 static void merge_commit_graph(struct write_commit_graph_context
*ctx
,
1896 struct commit_graph
*g
)
1899 uint32_t offset
= g
->num_commits_in_base
;
1901 ALLOC_GROW(ctx
->commits
.list
, ctx
->commits
.nr
+ g
->num_commits
, ctx
->commits
.alloc
);
1903 for (i
= 0; i
< g
->num_commits
; i
++) {
1904 struct object_id oid
;
1905 struct commit
*result
;
1907 display_progress(ctx
->progress
, i
+ 1);
1909 load_oid_from_graph(g
, i
+ offset
, &oid
);
1911 /* only add commits if they still exist in the repo */
1912 result
= lookup_commit_reference_gently(ctx
->r
, &oid
, 1);
1915 ctx
->commits
.list
[ctx
->commits
.nr
] = result
;
1921 static int commit_compare(const void *_a
, const void *_b
)
1923 const struct commit
*a
= *(const struct commit
**)_a
;
1924 const struct commit
*b
= *(const struct commit
**)_b
;
1925 return oidcmp(&a
->object
.oid
, &b
->object
.oid
);
1928 static void sort_and_scan_merged_commits(struct write_commit_graph_context
*ctx
)
1932 if (ctx
->report_progress
)
1933 ctx
->progress
= start_delayed_progress(
1934 _("Scanning merged commits"),
1937 QSORT(ctx
->commits
.list
, ctx
->commits
.nr
, commit_compare
);
1939 ctx
->num_extra_edges
= 0;
1940 for (i
= 0; i
< ctx
->commits
.nr
; i
++) {
1941 display_progress(ctx
->progress
, i
);
1943 if (i
&& oideq(&ctx
->commits
.list
[i
- 1]->object
.oid
,
1944 &ctx
->commits
.list
[i
]->object
.oid
)) {
1945 die(_("unexpected duplicate commit id %s"),
1946 oid_to_hex(&ctx
->commits
.list
[i
]->object
.oid
));
1948 unsigned int num_parents
;
1950 num_parents
= commit_list_count(ctx
->commits
.list
[i
]->parents
);
1951 if (num_parents
> 2)
1952 ctx
->num_extra_edges
+= num_parents
- 1;
1956 stop_progress(&ctx
->progress
);
1959 static void merge_commit_graphs(struct write_commit_graph_context
*ctx
)
1961 struct commit_graph
*g
= ctx
->r
->objects
->commit_graph
;
1962 uint32_t current_graph_number
= ctx
->num_commit_graphs_before
;
1964 while (g
&& current_graph_number
>= ctx
->num_commit_graphs_after
) {
1965 current_graph_number
--;
1967 if (ctx
->report_progress
)
1968 ctx
->progress
= start_delayed_progress(_("Merging commit-graph"), 0);
1970 merge_commit_graph(ctx
, g
);
1971 stop_progress(&ctx
->progress
);
1977 ctx
->new_base_graph
= g
;
1978 ctx
->new_num_commits_in_base
= g
->num_commits
+ g
->num_commits_in_base
;
1981 if (ctx
->new_base_graph
)
1982 ctx
->base_graph_name
= xstrdup(ctx
->new_base_graph
->filename
);
1984 sort_and_scan_merged_commits(ctx
);
1987 static void mark_commit_graphs(struct write_commit_graph_context
*ctx
)
1990 time_t now
= time(NULL
);
1992 for (i
= ctx
->num_commit_graphs_after
- 1; i
< ctx
->num_commit_graphs_before
; i
++) {
1994 struct utimbuf updated_time
;
1996 stat(ctx
->commit_graph_filenames_before
[i
], &st
);
1998 updated_time
.actime
= st
.st_atime
;
1999 updated_time
.modtime
= now
;
2000 utime(ctx
->commit_graph_filenames_before
[i
], &updated_time
);
2004 static void expire_commit_graphs(struct write_commit_graph_context
*ctx
)
2006 struct strbuf path
= STRBUF_INIT
;
2010 timestamp_t expire_time
= time(NULL
);
2012 if (ctx
->split_opts
&& ctx
->split_opts
->expire_time
)
2013 expire_time
= ctx
->split_opts
->expire_time
;
2015 char *chain_file_name
= get_chain_filename(ctx
->odb
);
2016 unlink(chain_file_name
);
2017 free(chain_file_name
);
2018 ctx
->num_commit_graphs_after
= 0;
2021 strbuf_addstr(&path
, ctx
->odb
->path
);
2022 strbuf_addstr(&path
, "/info/commit-graphs");
2023 dir
= opendir(path
.buf
);
2028 strbuf_addch(&path
, '/');
2029 dirnamelen
= path
.len
;
2030 while ((de
= readdir(dir
)) != NULL
) {
2032 uint32_t i
, found
= 0;
2034 strbuf_setlen(&path
, dirnamelen
);
2035 strbuf_addstr(&path
, de
->d_name
);
2037 stat(path
.buf
, &st
);
2039 if (st
.st_mtime
> expire_time
)
2041 if (path
.len
< 6 || strcmp(path
.buf
+ path
.len
- 6, ".graph"))
2044 for (i
= 0; i
< ctx
->num_commit_graphs_after
; i
++) {
2045 if (!strcmp(ctx
->commit_graph_filenames_after
[i
],
2057 strbuf_release(&path
);
2060 int write_commit_graph(struct object_directory
*odb
,
2061 struct string_list
*pack_indexes
,
2062 struct oidset
*commits
,
2063 enum commit_graph_write_flags flags
,
2064 const struct split_commit_graph_opts
*split_opts
)
2066 struct write_commit_graph_context
*ctx
;
2067 uint32_t i
, count_distinct
= 0;
2071 if (!commit_graph_compatible(the_repository
))
2074 ctx
= xcalloc(1, sizeof(struct write_commit_graph_context
));
2075 ctx
->r
= the_repository
;
2077 ctx
->append
= flags
& COMMIT_GRAPH_WRITE_APPEND
? 1 : 0;
2078 ctx
->report_progress
= flags
& COMMIT_GRAPH_WRITE_PROGRESS
? 1 : 0;
2079 ctx
->split
= flags
& COMMIT_GRAPH_WRITE_SPLIT
? 1 : 0;
2080 ctx
->split_opts
= split_opts
;
2081 ctx
->changed_paths
= flags
& COMMIT_GRAPH_WRITE_BLOOM_FILTERS
? 1 : 0;
2082 ctx
->total_bloom_filter_data_size
= 0;
2085 struct commit_graph
*g
;
2086 prepare_commit_graph(ctx
->r
);
2088 g
= ctx
->r
->objects
->commit_graph
;
2091 ctx
->num_commit_graphs_before
++;
2095 if (ctx
->num_commit_graphs_before
) {
2096 ALLOC_ARRAY(ctx
->commit_graph_filenames_before
, ctx
->num_commit_graphs_before
);
2097 i
= ctx
->num_commit_graphs_before
;
2098 g
= ctx
->r
->objects
->commit_graph
;
2101 ctx
->commit_graph_filenames_before
[--i
] = xstrdup(g
->filename
);
2106 if (ctx
->split_opts
)
2107 replace
= ctx
->split_opts
->flags
& COMMIT_GRAPH_SPLIT_REPLACE
;
2110 ctx
->approx_nr_objects
= approximate_object_count();
2111 ctx
->oids
.alloc
= ctx
->approx_nr_objects
/ 32;
2113 if (ctx
->split
&& split_opts
&& ctx
->oids
.alloc
> split_opts
->max_commits
)
2114 ctx
->oids
.alloc
= split_opts
->max_commits
;
2117 prepare_commit_graph_one(ctx
->r
, ctx
->odb
);
2118 if (ctx
->r
->objects
->commit_graph
)
2119 ctx
->oids
.alloc
+= ctx
->r
->objects
->commit_graph
->num_commits
;
2122 if (ctx
->oids
.alloc
< 1024)
2123 ctx
->oids
.alloc
= 1024;
2124 ALLOC_ARRAY(ctx
->oids
.list
, ctx
->oids
.alloc
);
2126 if (ctx
->append
&& ctx
->r
->objects
->commit_graph
) {
2127 struct commit_graph
*g
= ctx
->r
->objects
->commit_graph
;
2128 for (i
= 0; i
< g
->num_commits
; i
++) {
2129 const unsigned char *hash
= g
->chunk_oid_lookup
+ g
->hash_len
* i
;
2130 hashcpy(ctx
->oids
.list
[ctx
->oids
.nr
++].hash
, hash
);
2135 ctx
->order_by_pack
= 1;
2136 if ((res
= fill_oids_from_packs(ctx
, pack_indexes
)))
2141 if ((res
= fill_oids_from_commits(ctx
, commits
)))
2145 if (!pack_indexes
&& !commits
) {
2146 ctx
->order_by_pack
= 1;
2147 fill_oids_from_all_packs(ctx
);
2150 close_reachable(ctx
);
2152 count_distinct
= count_distinct_commits(ctx
);
2154 if (count_distinct
>= GRAPH_EDGE_LAST_MASK
) {
2155 error(_("the commit graph format cannot write %d commits"), count_distinct
);
2160 ctx
->commits
.alloc
= count_distinct
;
2161 ALLOC_ARRAY(ctx
->commits
.list
, ctx
->commits
.alloc
);
2163 copy_oids_to_commits(ctx
);
2165 if (ctx
->commits
.nr
>= GRAPH_EDGE_LAST_MASK
) {
2166 error(_("too many commits to write graph"));
2171 if (!ctx
->commits
.nr
&& !replace
)
2175 split_graph_merge_strategy(ctx
);
2178 merge_commit_graphs(ctx
);
2180 ctx
->num_commit_graphs_after
= 1;
2182 compute_generation_numbers(ctx
);
2184 if (ctx
->changed_paths
)
2185 compute_bloom_filters(ctx
);
2187 res
= write_commit_graph_file(ctx
);
2190 mark_commit_graphs(ctx
);
2192 expire_commit_graphs(ctx
);
2195 free(ctx
->graph_name
);
2196 free(ctx
->commits
.list
);
2197 free(ctx
->oids
.list
);
2199 if (ctx
->commit_graph_filenames_after
) {
2200 for (i
= 0; i
< ctx
->num_commit_graphs_after
; i
++) {
2201 free(ctx
->commit_graph_filenames_after
[i
]);
2202 free(ctx
->commit_graph_hash_after
[i
]);
2205 for (i
= 0; i
< ctx
->num_commit_graphs_before
; i
++)
2206 free(ctx
->commit_graph_filenames_before
[i
]);
2208 free(ctx
->commit_graph_filenames_after
);
2209 free(ctx
->commit_graph_filenames_before
);
2210 free(ctx
->commit_graph_hash_after
);
2218 #define VERIFY_COMMIT_GRAPH_ERROR_HASH 2
2219 static int verify_commit_graph_error
;
2221 static void graph_report(const char *fmt
, ...)
2225 verify_commit_graph_error
= 1;
2227 vfprintf(stderr
, fmt
, ap
);
2228 fprintf(stderr
, "\n");
2232 #define GENERATION_ZERO_EXISTS 1
2233 #define GENERATION_NUMBER_EXISTS 2
2235 int verify_commit_graph(struct repository
*r
, struct commit_graph
*g
, int flags
)
2237 uint32_t i
, cur_fanout_pos
= 0;
2238 struct object_id prev_oid
, cur_oid
, checksum
;
2239 int generation_zero
= 0;
2242 struct progress
*progress
= NULL
;
2243 int local_error
= 0;
2246 graph_report("no commit-graph file loaded");
2250 verify_commit_graph_error
= verify_commit_graph_lite(g
);
2251 if (verify_commit_graph_error
)
2252 return verify_commit_graph_error
;
2254 devnull
= open("/dev/null", O_WRONLY
);
2255 f
= hashfd(devnull
, NULL
);
2256 hashwrite(f
, g
->data
, g
->data_len
- g
->hash_len
);
2257 finalize_hashfile(f
, checksum
.hash
, CSUM_CLOSE
);
2258 if (!hasheq(checksum
.hash
, g
->data
+ g
->data_len
- g
->hash_len
)) {
2259 graph_report(_("the commit-graph file has incorrect checksum and is likely corrupt"));
2260 verify_commit_graph_error
= VERIFY_COMMIT_GRAPH_ERROR_HASH
;
2263 for (i
= 0; i
< g
->num_commits
; i
++) {
2264 struct commit
*graph_commit
;
2266 hashcpy(cur_oid
.hash
, g
->chunk_oid_lookup
+ g
->hash_len
* i
);
2268 if (i
&& oidcmp(&prev_oid
, &cur_oid
) >= 0)
2269 graph_report(_("commit-graph has incorrect OID order: %s then %s"),
2270 oid_to_hex(&prev_oid
),
2271 oid_to_hex(&cur_oid
));
2273 oidcpy(&prev_oid
, &cur_oid
);
2275 while (cur_oid
.hash
[0] > cur_fanout_pos
) {
2276 uint32_t fanout_value
= get_be32(g
->chunk_oid_fanout
+ cur_fanout_pos
);
2278 if (i
!= fanout_value
)
2279 graph_report(_("commit-graph has incorrect fanout value: fanout[%d] = %u != %u"),
2280 cur_fanout_pos
, fanout_value
, i
);
2284 graph_commit
= lookup_commit(r
, &cur_oid
);
2285 if (!parse_commit_in_graph_one(r
, g
, graph_commit
))
2286 graph_report(_("failed to parse commit %s from commit-graph"),
2287 oid_to_hex(&cur_oid
));
2290 while (cur_fanout_pos
< 256) {
2291 uint32_t fanout_value
= get_be32(g
->chunk_oid_fanout
+ cur_fanout_pos
);
2293 if (g
->num_commits
!= fanout_value
)
2294 graph_report(_("commit-graph has incorrect fanout value: fanout[%d] = %u != %u"),
2295 cur_fanout_pos
, fanout_value
, i
);
2300 if (verify_commit_graph_error
& ~VERIFY_COMMIT_GRAPH_ERROR_HASH
)
2301 return verify_commit_graph_error
;
2303 if (flags
& COMMIT_GRAPH_WRITE_PROGRESS
)
2304 progress
= start_progress(_("Verifying commits in commit graph"),
2307 for (i
= 0; i
< g
->num_commits
; i
++) {
2308 struct commit
*graph_commit
, *odb_commit
;
2309 struct commit_list
*graph_parents
, *odb_parents
;
2310 uint32_t max_generation
= 0;
2311 uint32_t generation
;
2313 display_progress(progress
, i
+ 1);
2314 hashcpy(cur_oid
.hash
, g
->chunk_oid_lookup
+ g
->hash_len
* i
);
2316 graph_commit
= lookup_commit(r
, &cur_oid
);
2317 odb_commit
= (struct commit
*)create_object(r
, &cur_oid
, alloc_commit_node(r
));
2318 if (parse_commit_internal(odb_commit
, 0, 0)) {
2319 graph_report(_("failed to parse commit %s from object database for commit-graph"),
2320 oid_to_hex(&cur_oid
));
2324 if (!oideq(&get_commit_tree_in_graph_one(r
, g
, graph_commit
)->object
.oid
,
2325 get_commit_tree_oid(odb_commit
)))
2326 graph_report(_("root tree OID for commit %s in commit-graph is %s != %s"),
2327 oid_to_hex(&cur_oid
),
2328 oid_to_hex(get_commit_tree_oid(graph_commit
)),
2329 oid_to_hex(get_commit_tree_oid(odb_commit
)));
2331 graph_parents
= graph_commit
->parents
;
2332 odb_parents
= odb_commit
->parents
;
2334 while (graph_parents
) {
2335 if (odb_parents
== NULL
) {
2336 graph_report(_("commit-graph parent list for commit %s is too long"),
2337 oid_to_hex(&cur_oid
));
2341 /* parse parent in case it is in a base graph */
2342 parse_commit_in_graph_one(r
, g
, graph_parents
->item
);
2344 if (!oideq(&graph_parents
->item
->object
.oid
, &odb_parents
->item
->object
.oid
))
2345 graph_report(_("commit-graph parent for %s is %s != %s"),
2346 oid_to_hex(&cur_oid
),
2347 oid_to_hex(&graph_parents
->item
->object
.oid
),
2348 oid_to_hex(&odb_parents
->item
->object
.oid
));
2350 generation
= commit_graph_generation(graph_parents
->item
);
2351 if (generation
> max_generation
)
2352 max_generation
= generation
;
2354 graph_parents
= graph_parents
->next
;
2355 odb_parents
= odb_parents
->next
;
2358 if (odb_parents
!= NULL
)
2359 graph_report(_("commit-graph parent list for commit %s terminates early"),
2360 oid_to_hex(&cur_oid
));
2362 if (!commit_graph_generation(graph_commit
)) {
2363 if (generation_zero
== GENERATION_NUMBER_EXISTS
)
2364 graph_report(_("commit-graph has generation number zero for commit %s, but non-zero elsewhere"),
2365 oid_to_hex(&cur_oid
));
2366 generation_zero
= GENERATION_ZERO_EXISTS
;
2367 } else if (generation_zero
== GENERATION_ZERO_EXISTS
)
2368 graph_report(_("commit-graph has non-zero generation number for commit %s, but zero elsewhere"),
2369 oid_to_hex(&cur_oid
));
2371 if (generation_zero
== GENERATION_ZERO_EXISTS
)
2375 * If one of our parents has generation GENERATION_NUMBER_MAX, then
2376 * our generation is also GENERATION_NUMBER_MAX. Decrement to avoid
2377 * extra logic in the following condition.
2379 if (max_generation
== GENERATION_NUMBER_MAX
)
2382 generation
= commit_graph_generation(graph_commit
);
2383 if (generation
!= max_generation
+ 1)
2384 graph_report(_("commit-graph generation for commit %s is %u != %u"),
2385 oid_to_hex(&cur_oid
),
2387 max_generation
+ 1);
2389 if (graph_commit
->date
!= odb_commit
->date
)
2390 graph_report(_("commit date for commit %s in commit-graph is %"PRItime
" != %"PRItime
),
2391 oid_to_hex(&cur_oid
),
2395 stop_progress(&progress
);
2397 local_error
= verify_commit_graph_error
;
2399 if (!(flags
& COMMIT_GRAPH_VERIFY_SHALLOW
) && g
->base_graph
)
2400 local_error
|= verify_commit_graph(r
, g
->base_graph
, flags
);
2405 void free_commit_graph(struct commit_graph
*g
)
2410 munmap((void *)g
->data
, g
->data_len
);
2414 free(g
->bloom_filter_settings
);
2418 void disable_commit_graph(struct repository
*r
)
2420 r
->commit_graph_disabled
= 1;