1 #include "git-compat-util.h"
10 #include "sha1-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_GENERATION_DATA 0x47444154 /* "GDAT" */
42 #define GRAPH_CHUNKID_GENERATION_DATA_OVERFLOW 0x47444f56 /* "GDOV" */
43 #define GRAPH_CHUNKID_EXTRAEDGES 0x45444745 /* "EDGE" */
44 #define GRAPH_CHUNKID_BLOOMINDEXES 0x42494458 /* "BIDX" */
45 #define GRAPH_CHUNKID_BLOOMDATA 0x42444154 /* "BDAT" */
46 #define GRAPH_CHUNKID_BASE 0x42415345 /* "BASE" */
47 #define MAX_NUM_CHUNKS 9
49 #define GRAPH_DATA_WIDTH (the_hash_algo->rawsz + 16)
51 #define GRAPH_VERSION_1 0x1
52 #define GRAPH_VERSION GRAPH_VERSION_1
54 #define GRAPH_EXTRA_EDGES_NEEDED 0x80000000
55 #define GRAPH_EDGE_LAST_MASK 0x7fffffff
56 #define GRAPH_PARENT_NONE 0x70000000
58 #define GRAPH_LAST_EDGE 0x80000000
60 #define GRAPH_HEADER_SIZE 8
61 #define GRAPH_FANOUT_SIZE (4 * 256)
62 #define GRAPH_CHUNKLOOKUP_WIDTH 12
63 #define GRAPH_MIN_SIZE (GRAPH_HEADER_SIZE + 4 * GRAPH_CHUNKLOOKUP_WIDTH \
64 + GRAPH_FANOUT_SIZE + the_hash_algo->rawsz)
66 #define CORRECTED_COMMIT_DATE_OFFSET_OVERFLOW (1ULL << 31)
68 /* Remember to update object flag allocation in object.h */
69 #define REACHABLE (1u<<15)
71 define_commit_slab(topo_level_slab
, uint32_t);
73 /* Keep track of the order in which commits are added to our list. */
74 define_commit_slab(commit_pos
, int);
75 static struct commit_pos commit_pos
= COMMIT_SLAB_INIT(1, commit_pos
);
77 static void set_commit_pos(struct repository
*r
, const struct object_id
*oid
)
79 static int32_t max_pos
;
80 struct commit
*commit
= lookup_commit(r
, oid
);
83 return; /* should never happen, but be lenient */
85 *commit_pos_at(&commit_pos
, commit
) = max_pos
++;
88 static int commit_pos_cmp(const void *va
, const void *vb
)
90 const struct commit
*a
= *(const struct commit
**)va
;
91 const struct commit
*b
= *(const struct commit
**)vb
;
92 return commit_pos_at(&commit_pos
, a
) -
93 commit_pos_at(&commit_pos
, b
);
96 define_commit_slab(commit_graph_data_slab
, struct commit_graph_data
);
97 static struct commit_graph_data_slab commit_graph_data_slab
=
98 COMMIT_SLAB_INIT(1, commit_graph_data_slab
);
100 uint32_t commit_graph_position(const struct commit
*c
)
102 struct commit_graph_data
*data
=
103 commit_graph_data_slab_peek(&commit_graph_data_slab
, c
);
105 return data
? data
->graph_pos
: COMMIT_NOT_FROM_GRAPH
;
108 timestamp_t
commit_graph_generation(const struct commit
*c
)
110 struct commit_graph_data
*data
=
111 commit_graph_data_slab_peek(&commit_graph_data_slab
, c
);
114 return GENERATION_NUMBER_INFINITY
;
115 else if (data
->graph_pos
== COMMIT_NOT_FROM_GRAPH
)
116 return GENERATION_NUMBER_INFINITY
;
118 return data
->generation
;
121 static struct commit_graph_data
*commit_graph_data_at(const struct commit
*c
)
123 unsigned int i
, nth_slab
;
124 struct commit_graph_data
*data
=
125 commit_graph_data_slab_peek(&commit_graph_data_slab
, c
);
130 nth_slab
= c
->index
/ commit_graph_data_slab
.slab_size
;
131 data
= commit_graph_data_slab_at(&commit_graph_data_slab
, c
);
134 * commit-slab initializes elements with zero, overwrite this with
135 * COMMIT_NOT_FROM_GRAPH for graph_pos.
137 * We avoid initializing generation with checking if graph position
138 * is not COMMIT_NOT_FROM_GRAPH.
140 for (i
= 0; i
< commit_graph_data_slab
.slab_size
; i
++) {
141 commit_graph_data_slab
.slab
[nth_slab
][i
].graph_pos
=
142 COMMIT_NOT_FROM_GRAPH
;
149 * Should be used only while writing commit-graph as it compares
150 * generation value of commits by directly accessing commit-slab.
152 static int commit_gen_cmp(const void *va
, const void *vb
)
154 const struct commit
*a
= *(const struct commit
**)va
;
155 const struct commit
*b
= *(const struct commit
**)vb
;
157 const timestamp_t generation_a
= commit_graph_data_at(a
)->generation
;
158 const timestamp_t generation_b
= commit_graph_data_at(b
)->generation
;
159 /* lower generation commits first */
160 if (generation_a
< generation_b
)
162 else if (generation_a
> generation_b
)
165 /* use date as a heuristic when generations are equal */
166 if (a
->date
< b
->date
)
168 else if (a
->date
> b
->date
)
173 char *get_commit_graph_filename(struct object_directory
*obj_dir
)
175 return xstrfmt("%s/info/commit-graph", obj_dir
->path
);
178 static char *get_split_graph_filename(struct object_directory
*odb
,
181 return xstrfmt("%s/info/commit-graphs/graph-%s.graph", odb
->path
,
185 char *get_commit_graph_chain_filename(struct object_directory
*odb
)
187 return xstrfmt("%s/info/commit-graphs/commit-graph-chain", odb
->path
);
190 static uint8_t oid_version(void)
192 switch (hash_algo_by_ptr(the_hash_algo
)) {
195 case GIT_HASH_SHA256
:
198 die(_("invalid hash version"));
202 static struct commit_graph
*alloc_commit_graph(void)
204 struct commit_graph
*g
= xcalloc(1, sizeof(*g
));
209 extern int read_replace_refs
;
211 static int commit_graph_compatible(struct repository
*r
)
216 if (read_replace_refs
) {
217 prepare_replace_object(r
);
218 if (hashmap_get_size(&r
->objects
->replace_map
->map
))
222 prepare_commit_graft(r
);
223 if (r
->parsed_objects
&&
224 (r
->parsed_objects
->grafts_nr
|| r
->parsed_objects
->substituted_parent
))
226 if (is_repository_shallow(r
))
232 int open_commit_graph(const char *graph_file
, int *fd
, struct stat
*st
)
234 *fd
= git_open(graph_file
);
237 if (fstat(*fd
, st
)) {
244 struct commit_graph
*load_commit_graph_one_fd_st(struct repository
*r
,
245 int fd
, struct stat
*st
,
246 struct object_directory
*odb
)
250 struct commit_graph
*ret
;
252 graph_size
= xsize_t(st
->st_size
);
254 if (graph_size
< GRAPH_MIN_SIZE
) {
256 error(_("commit-graph file is too small"));
259 graph_map
= xmmap(NULL
, graph_size
, PROT_READ
, MAP_PRIVATE
, fd
, 0);
261 ret
= parse_commit_graph(r
, graph_map
, graph_size
);
266 munmap(graph_map
, graph_size
);
271 static int verify_commit_graph_lite(struct commit_graph
*g
)
274 * Basic validation shared between parse_commit_graph()
275 * which'll be called every time the graph is used, and the
276 * much more expensive verify_commit_graph() used by
277 * "commit-graph verify".
279 * There should only be very basic checks here to ensure that
280 * we don't e.g. segfault in fill_commit_in_graph(), but
281 * because this is a very hot codepath nothing that e.g. loops
282 * over g->num_commits, or runs a checksum on the commit-graph
285 if (!g
->chunk_oid_fanout
) {
286 error("commit-graph is missing the OID Fanout chunk");
289 if (!g
->chunk_oid_lookup
) {
290 error("commit-graph is missing the OID Lookup chunk");
293 if (!g
->chunk_commit_data
) {
294 error("commit-graph is missing the Commit Data chunk");
301 struct commit_graph
*parse_commit_graph(struct repository
*r
,
302 void *graph_map
, size_t graph_size
)
304 const unsigned char *data
, *chunk_lookup
;
306 struct commit_graph
*graph
;
307 uint64_t next_chunk_offset
;
308 uint32_t graph_signature
;
309 unsigned char graph_version
, hash_version
;
314 if (graph_size
< GRAPH_MIN_SIZE
)
317 data
= (const unsigned char *)graph_map
;
319 graph_signature
= get_be32(data
);
320 if (graph_signature
!= GRAPH_SIGNATURE
) {
321 error(_("commit-graph signature %X does not match signature %X"),
322 graph_signature
, GRAPH_SIGNATURE
);
326 graph_version
= *(unsigned char*)(data
+ 4);
327 if (graph_version
!= GRAPH_VERSION
) {
328 error(_("commit-graph version %X does not match version %X"),
329 graph_version
, GRAPH_VERSION
);
333 hash_version
= *(unsigned char*)(data
+ 5);
334 if (hash_version
!= oid_version()) {
335 error(_("commit-graph hash version %X does not match version %X"),
336 hash_version
, oid_version());
340 prepare_repo_settings(r
);
342 graph
= alloc_commit_graph();
344 graph
->hash_len
= the_hash_algo
->rawsz
;
345 graph
->num_chunks
= *(unsigned char*)(data
+ 6);
346 graph
->data
= graph_map
;
347 graph
->data_len
= graph_size
;
349 if (graph_size
< GRAPH_HEADER_SIZE
+
350 (graph
->num_chunks
+ 1) * GRAPH_CHUNKLOOKUP_WIDTH
+
351 GRAPH_FANOUT_SIZE
+ the_hash_algo
->rawsz
) {
352 error(_("commit-graph file is too small to hold %u chunks"),
358 chunk_lookup
= data
+ 8;
359 next_chunk_offset
= get_be64(chunk_lookup
+ 4);
360 for (i
= 0; i
< graph
->num_chunks
; i
++) {
362 uint64_t chunk_offset
= next_chunk_offset
;
363 int chunk_repeated
= 0;
365 chunk_id
= get_be32(chunk_lookup
+ 0);
367 chunk_lookup
+= GRAPH_CHUNKLOOKUP_WIDTH
;
368 next_chunk_offset
= get_be64(chunk_lookup
+ 4);
370 if (chunk_offset
> graph_size
- the_hash_algo
->rawsz
) {
371 error(_("commit-graph improper chunk offset %08x%08x"), (uint32_t)(chunk_offset
>> 32),
372 (uint32_t)chunk_offset
);
373 goto free_and_return
;
377 case GRAPH_CHUNKID_OIDFANOUT
:
378 if (graph
->chunk_oid_fanout
)
381 graph
->chunk_oid_fanout
= (uint32_t*)(data
+ chunk_offset
);
384 case GRAPH_CHUNKID_OIDLOOKUP
:
385 if (graph
->chunk_oid_lookup
)
388 graph
->chunk_oid_lookup
= data
+ chunk_offset
;
389 graph
->num_commits
= (next_chunk_offset
- chunk_offset
)
394 case GRAPH_CHUNKID_DATA
:
395 if (graph
->chunk_commit_data
)
398 graph
->chunk_commit_data
= data
+ chunk_offset
;
401 case GRAPH_CHUNKID_GENERATION_DATA
:
402 if (graph
->chunk_generation_data
)
405 graph
->chunk_generation_data
= data
+ chunk_offset
;
408 case GRAPH_CHUNKID_GENERATION_DATA_OVERFLOW
:
409 if (graph
->chunk_generation_data_overflow
)
412 graph
->chunk_generation_data_overflow
= data
+ chunk_offset
;
415 case GRAPH_CHUNKID_EXTRAEDGES
:
416 if (graph
->chunk_extra_edges
)
419 graph
->chunk_extra_edges
= data
+ chunk_offset
;
422 case GRAPH_CHUNKID_BASE
:
423 if (graph
->chunk_base_graphs
)
426 graph
->chunk_base_graphs
= data
+ chunk_offset
;
429 case GRAPH_CHUNKID_BLOOMINDEXES
:
430 if (graph
->chunk_bloom_indexes
)
432 else if (r
->settings
.commit_graph_read_changed_paths
)
433 graph
->chunk_bloom_indexes
= data
+ chunk_offset
;
436 case GRAPH_CHUNKID_BLOOMDATA
:
437 if (graph
->chunk_bloom_data
)
439 else if (r
->settings
.commit_graph_read_changed_paths
) {
440 uint32_t hash_version
;
441 graph
->chunk_bloom_data
= data
+ chunk_offset
;
442 hash_version
= get_be32(data
+ chunk_offset
);
444 if (hash_version
!= 1)
447 graph
->bloom_filter_settings
= xmalloc(sizeof(struct bloom_filter_settings
));
448 graph
->bloom_filter_settings
->hash_version
= hash_version
;
449 graph
->bloom_filter_settings
->num_hashes
= get_be32(data
+ chunk_offset
+ 4);
450 graph
->bloom_filter_settings
->bits_per_entry
= get_be32(data
+ chunk_offset
+ 8);
451 graph
->bloom_filter_settings
->max_changed_paths
= DEFAULT_BLOOM_MAX_CHANGES
;
456 if (chunk_repeated
) {
457 error(_("commit-graph chunk id %08x appears multiple times"), chunk_id
);
458 goto free_and_return
;
462 if (graph
->chunk_bloom_indexes
&& graph
->chunk_bloom_data
) {
463 init_bloom_filters();
465 /* We need both the bloom chunks to exist together. Else ignore the data */
466 graph
->chunk_bloom_indexes
= NULL
;
467 graph
->chunk_bloom_data
= NULL
;
468 FREE_AND_NULL(graph
->bloom_filter_settings
);
471 hashcpy(graph
->oid
.hash
, graph
->data
+ graph
->data_len
- graph
->hash_len
);
473 if (verify_commit_graph_lite(graph
))
474 goto free_and_return
;
479 free(graph
->bloom_filter_settings
);
484 static struct commit_graph
*load_commit_graph_one(struct repository
*r
,
485 const char *graph_file
,
486 struct object_directory
*odb
)
491 struct commit_graph
*g
;
492 int open_ok
= open_commit_graph(graph_file
, &fd
, &st
);
497 g
= load_commit_graph_one_fd_st(r
, fd
, &st
, odb
);
500 g
->filename
= xstrdup(graph_file
);
505 static struct commit_graph
*load_commit_graph_v1(struct repository
*r
,
506 struct object_directory
*odb
)
508 char *graph_name
= get_commit_graph_filename(odb
);
509 struct commit_graph
*g
= load_commit_graph_one(r
, graph_name
, odb
);
515 static int add_graph_to_chain(struct commit_graph
*g
,
516 struct commit_graph
*chain
,
517 struct object_id
*oids
,
520 struct commit_graph
*cur_g
= chain
;
522 if (n
&& !g
->chunk_base_graphs
) {
523 warning(_("commit-graph has no base graphs chunk"));
531 !oideq(&oids
[n
], &cur_g
->oid
) ||
532 !hasheq(oids
[n
].hash
, g
->chunk_base_graphs
+ g
->hash_len
* n
)) {
533 warning(_("commit-graph chain does not match"));
537 cur_g
= cur_g
->base_graph
;
540 g
->base_graph
= chain
;
543 g
->num_commits_in_base
= chain
->num_commits
+ chain
->num_commits_in_base
;
548 static struct commit_graph
*load_commit_graph_chain(struct repository
*r
,
549 struct object_directory
*odb
)
551 struct commit_graph
*graph_chain
= NULL
;
552 struct strbuf line
= STRBUF_INIT
;
554 struct object_id
*oids
;
555 int i
= 0, valid
= 1, count
;
556 char *chain_name
= get_commit_graph_chain_filename(odb
);
560 fp
= fopen(chain_name
, "r");
561 stat_res
= stat(chain_name
, &st
);
566 st
.st_size
<= the_hash_algo
->hexsz
)
569 count
= st
.st_size
/ (the_hash_algo
->hexsz
+ 1);
570 oids
= xcalloc(count
, sizeof(struct object_id
));
574 for (i
= 0; i
< count
; i
++) {
575 struct object_directory
*odb
;
577 if (strbuf_getline_lf(&line
, fp
) == EOF
)
580 if (get_oid_hex(line
.buf
, &oids
[i
])) {
581 warning(_("invalid commit-graph chain: line '%s' not a hash"),
588 for (odb
= r
->objects
->odb
; odb
; odb
= odb
->next
) {
589 char *graph_name
= get_split_graph_filename(odb
, line
.buf
);
590 struct commit_graph
*g
= load_commit_graph_one(r
, graph_name
, odb
);
595 if (add_graph_to_chain(g
, graph_chain
, oids
, i
)) {
605 warning(_("unable to find all commit-graph files"));
612 strbuf_release(&line
);
617 static void validate_mixed_generation_chain(struct commit_graph
*g
)
619 int read_generation_data
;
624 read_generation_data
= !!g
->chunk_generation_data
;
627 g
->read_generation_data
= read_generation_data
;
632 struct commit_graph
*read_commit_graph_one(struct repository
*r
,
633 struct object_directory
*odb
)
635 struct commit_graph
*g
= load_commit_graph_v1(r
, odb
);
638 g
= load_commit_graph_chain(r
, odb
);
640 validate_mixed_generation_chain(g
);
645 static void prepare_commit_graph_one(struct repository
*r
,
646 struct object_directory
*odb
)
649 if (r
->objects
->commit_graph
)
652 r
->objects
->commit_graph
= read_commit_graph_one(r
, odb
);
656 * Return 1 if commit_graph is non-NULL, and 0 otherwise.
658 * On the first invocation, this function attempts to load the commit
659 * graph if the_repository is configured to have one.
661 static int prepare_commit_graph(struct repository
*r
)
663 struct object_directory
*odb
;
666 * This must come before the "already attempted?" check below, because
667 * we want to disable even an already-loaded graph file.
669 if (r
->commit_graph_disabled
)
672 if (r
->objects
->commit_graph_attempted
)
673 return !!r
->objects
->commit_graph
;
674 r
->objects
->commit_graph_attempted
= 1;
676 prepare_repo_settings(r
);
678 if (!git_env_bool(GIT_TEST_COMMIT_GRAPH
, 0) &&
679 r
->settings
.core_commit_graph
!= 1)
681 * This repository is not configured to use commit graphs, so
682 * do not load one. (But report commit_graph_attempted anyway
683 * so that commit graph loading is not attempted again for this
688 if (!commit_graph_compatible(r
))
692 for (odb
= r
->objects
->odb
;
693 !r
->objects
->commit_graph
&& odb
;
695 prepare_commit_graph_one(r
, odb
);
696 return !!r
->objects
->commit_graph
;
699 int generation_numbers_enabled(struct repository
*r
)
701 uint32_t first_generation
;
702 struct commit_graph
*g
;
703 if (!prepare_commit_graph(r
))
706 g
= r
->objects
->commit_graph
;
711 first_generation
= get_be32(g
->chunk_commit_data
+
712 g
->hash_len
+ 8) >> 2;
714 return !!first_generation
;
717 int corrected_commit_dates_enabled(struct repository
*r
)
719 struct commit_graph
*g
;
720 if (!prepare_commit_graph(r
))
723 g
= r
->objects
->commit_graph
;
728 return g
->read_generation_data
;
731 struct bloom_filter_settings
*get_bloom_filter_settings(struct repository
*r
)
733 struct commit_graph
*g
= r
->objects
->commit_graph
;
735 if (g
->bloom_filter_settings
)
736 return g
->bloom_filter_settings
;
742 static void close_commit_graph_one(struct commit_graph
*g
)
747 close_commit_graph_one(g
->base_graph
);
748 free_commit_graph(g
);
751 void close_commit_graph(struct raw_object_store
*o
)
753 close_commit_graph_one(o
->commit_graph
);
754 o
->commit_graph
= NULL
;
757 static int bsearch_graph(struct commit_graph
*g
, struct object_id
*oid
, uint32_t *pos
)
759 return bsearch_hash(oid
->hash
, g
->chunk_oid_fanout
,
760 g
->chunk_oid_lookup
, g
->hash_len
, pos
);
763 static void load_oid_from_graph(struct commit_graph
*g
,
765 struct object_id
*oid
)
769 while (g
&& pos
< g
->num_commits_in_base
)
773 BUG("NULL commit-graph");
775 if (pos
>= g
->num_commits
+ g
->num_commits_in_base
)
776 die(_("invalid commit position. commit-graph is likely corrupt"));
778 lex_index
= pos
- g
->num_commits_in_base
;
780 hashcpy(oid
->hash
, g
->chunk_oid_lookup
+ g
->hash_len
* lex_index
);
783 static struct commit_list
**insert_parent_or_die(struct repository
*r
,
784 struct commit_graph
*g
,
786 struct commit_list
**pptr
)
789 struct object_id oid
;
791 if (pos
>= g
->num_commits
+ g
->num_commits_in_base
)
792 die("invalid parent position %"PRIu32
, pos
);
794 load_oid_from_graph(g
, pos
, &oid
);
795 c
= lookup_commit(r
, &oid
);
797 die(_("could not find commit %s"), oid_to_hex(&oid
));
798 commit_graph_data_at(c
)->graph_pos
= pos
;
799 return &commit_list_insert(c
, pptr
)->next
;
802 static void fill_commit_graph_info(struct commit
*item
, struct commit_graph
*g
, uint32_t pos
)
804 const unsigned char *commit_data
;
805 struct commit_graph_data
*graph_data
;
806 uint32_t lex_index
, offset_pos
;
807 uint64_t date_high
, date_low
, offset
;
809 while (pos
< g
->num_commits_in_base
)
812 if (pos
>= g
->num_commits
+ g
->num_commits_in_base
)
813 die(_("invalid commit position. commit-graph is likely corrupt"));
815 lex_index
= pos
- g
->num_commits_in_base
;
816 commit_data
= g
->chunk_commit_data
+ GRAPH_DATA_WIDTH
* lex_index
;
818 graph_data
= commit_graph_data_at(item
);
819 graph_data
->graph_pos
= pos
;
821 date_high
= get_be32(commit_data
+ g
->hash_len
+ 8) & 0x3;
822 date_low
= get_be32(commit_data
+ g
->hash_len
+ 12);
823 item
->date
= (timestamp_t
)((date_high
<< 32) | date_low
);
825 if (g
->read_generation_data
) {
826 offset
= (timestamp_t
)get_be32(g
->chunk_generation_data
+ sizeof(uint32_t) * lex_index
);
828 if (offset
& CORRECTED_COMMIT_DATE_OFFSET_OVERFLOW
) {
829 if (!g
->chunk_generation_data_overflow
)
830 die(_("commit-graph requires overflow generation data but has none"));
832 offset_pos
= offset
^ CORRECTED_COMMIT_DATE_OFFSET_OVERFLOW
;
833 graph_data
->generation
= get_be64(g
->chunk_generation_data_overflow
+ 8 * offset_pos
);
835 graph_data
->generation
= item
->date
+ offset
;
837 graph_data
->generation
= get_be32(commit_data
+ g
->hash_len
+ 8) >> 2;
840 *topo_level_slab_at(g
->topo_levels
, item
) = get_be32(commit_data
+ g
->hash_len
+ 8) >> 2;
843 static inline void set_commit_tree(struct commit
*c
, struct tree
*t
)
848 static int fill_commit_in_graph(struct repository
*r
,
850 struct commit_graph
*g
, uint32_t pos
)
853 uint32_t *parent_data_ptr
;
854 struct commit_list
**pptr
;
855 const unsigned char *commit_data
;
858 while (pos
< g
->num_commits_in_base
)
861 fill_commit_graph_info(item
, g
, pos
);
863 lex_index
= pos
- g
->num_commits_in_base
;
864 commit_data
= g
->chunk_commit_data
+ (g
->hash_len
+ 16) * lex_index
;
866 item
->object
.parsed
= 1;
868 set_commit_tree(item
, NULL
);
870 pptr
= &item
->parents
;
872 edge_value
= get_be32(commit_data
+ g
->hash_len
);
873 if (edge_value
== GRAPH_PARENT_NONE
)
875 pptr
= insert_parent_or_die(r
, g
, edge_value
, pptr
);
877 edge_value
= get_be32(commit_data
+ g
->hash_len
+ 4);
878 if (edge_value
== GRAPH_PARENT_NONE
)
880 if (!(edge_value
& GRAPH_EXTRA_EDGES_NEEDED
)) {
881 pptr
= insert_parent_or_die(r
, g
, edge_value
, pptr
);
885 parent_data_ptr
= (uint32_t*)(g
->chunk_extra_edges
+
886 4 * (uint64_t)(edge_value
& GRAPH_EDGE_LAST_MASK
));
888 edge_value
= get_be32(parent_data_ptr
);
889 pptr
= insert_parent_or_die(r
, g
,
890 edge_value
& GRAPH_EDGE_LAST_MASK
,
893 } while (!(edge_value
& GRAPH_LAST_EDGE
));
898 static int find_commit_in_graph(struct commit
*item
, struct commit_graph
*g
, uint32_t *pos
)
900 uint32_t graph_pos
= commit_graph_position(item
);
901 if (graph_pos
!= COMMIT_NOT_FROM_GRAPH
) {
905 struct commit_graph
*cur_g
= g
;
908 while (cur_g
&& !bsearch_graph(cur_g
, &(item
->object
.oid
), &lex_index
))
909 cur_g
= cur_g
->base_graph
;
912 *pos
= lex_index
+ cur_g
->num_commits_in_base
;
920 static int parse_commit_in_graph_one(struct repository
*r
,
921 struct commit_graph
*g
,
926 if (item
->object
.parsed
)
929 if (find_commit_in_graph(item
, g
, &pos
))
930 return fill_commit_in_graph(r
, item
, g
, pos
);
935 int parse_commit_in_graph(struct repository
*r
, struct commit
*item
)
937 static int checked_env
= 0;
940 git_env_bool(GIT_TEST_COMMIT_GRAPH_DIE_ON_PARSE
, 0))
941 die("dying as requested by the '%s' variable on commit-graph parse!",
942 GIT_TEST_COMMIT_GRAPH_DIE_ON_PARSE
);
945 if (!prepare_commit_graph(r
))
947 return parse_commit_in_graph_one(r
, r
->objects
->commit_graph
, item
);
950 void load_commit_graph_info(struct repository
*r
, struct commit
*item
)
953 if (!prepare_commit_graph(r
))
955 if (find_commit_in_graph(item
, r
->objects
->commit_graph
, &pos
))
956 fill_commit_graph_info(item
, r
->objects
->commit_graph
, pos
);
959 static struct tree
*load_tree_for_commit(struct repository
*r
,
960 struct commit_graph
*g
,
963 struct object_id oid
;
964 const unsigned char *commit_data
;
965 uint32_t graph_pos
= commit_graph_position(c
);
967 while (graph_pos
< g
->num_commits_in_base
)
970 commit_data
= g
->chunk_commit_data
+
971 GRAPH_DATA_WIDTH
* (graph_pos
- g
->num_commits_in_base
);
973 hashcpy(oid
.hash
, commit_data
);
974 set_commit_tree(c
, lookup_tree(r
, &oid
));
976 return c
->maybe_tree
;
979 static struct tree
*get_commit_tree_in_graph_one(struct repository
*r
,
980 struct commit_graph
*g
,
981 const struct commit
*c
)
984 return c
->maybe_tree
;
985 if (commit_graph_position(c
) == COMMIT_NOT_FROM_GRAPH
)
986 BUG("get_commit_tree_in_graph_one called from non-commit-graph commit");
988 return load_tree_for_commit(r
, g
, (struct commit
*)c
);
991 struct tree
*get_commit_tree_in_graph(struct repository
*r
, const struct commit
*c
)
993 return get_commit_tree_in_graph_one(r
, r
->objects
->commit_graph
, c
);
996 struct packed_commit_list
{
997 struct commit
**list
;
1002 struct write_commit_graph_context
{
1003 struct repository
*r
;
1004 struct object_directory
*odb
;
1006 struct oid_array oids
;
1007 struct packed_commit_list commits
;
1008 int num_extra_edges
;
1009 int num_generation_data_overflows
;
1010 unsigned long approx_nr_objects
;
1011 struct progress
*progress
;
1013 uint64_t progress_cnt
;
1015 char *base_graph_name
;
1016 int num_commit_graphs_before
;
1017 int num_commit_graphs_after
;
1018 char **commit_graph_filenames_before
;
1019 char **commit_graph_filenames_after
;
1020 char **commit_graph_hash_after
;
1021 uint32_t new_num_commits_in_base
;
1022 struct commit_graph
*new_base_graph
;
1029 write_generation_data
:1;
1031 struct topo_level_slab
*topo_levels
;
1032 const struct commit_graph_opts
*opts
;
1033 size_t total_bloom_filter_data_size
;
1034 const struct bloom_filter_settings
*bloom_settings
;
1036 int count_bloom_filter_computed
;
1037 int count_bloom_filter_not_computed
;
1038 int count_bloom_filter_trunc_empty
;
1039 int count_bloom_filter_trunc_large
;
1042 static int write_graph_chunk_fanout(struct hashfile
*f
,
1043 struct write_commit_graph_context
*ctx
)
1046 struct commit
**list
= ctx
->commits
.list
;
1049 * Write the first-level table (the list is sorted,
1050 * but we use a 256-entry lookup to be able to avoid
1051 * having to do eight extra binary search iterations).
1053 for (i
= 0; i
< 256; i
++) {
1054 while (count
< ctx
->commits
.nr
) {
1055 if ((*list
)->object
.oid
.hash
[0] != i
)
1057 display_progress(ctx
->progress
, ++ctx
->progress_cnt
);
1062 hashwrite_be32(f
, count
);
1068 static int write_graph_chunk_oids(struct hashfile
*f
,
1069 struct write_commit_graph_context
*ctx
)
1071 struct commit
**list
= ctx
->commits
.list
;
1073 for (count
= 0; count
< ctx
->commits
.nr
; count
++, list
++) {
1074 display_progress(ctx
->progress
, ++ctx
->progress_cnt
);
1075 hashwrite(f
, (*list
)->object
.oid
.hash
, the_hash_algo
->rawsz
);
1081 static const unsigned char *commit_to_sha1(size_t index
, void *table
)
1083 struct commit
**commits
= table
;
1084 return commits
[index
]->object
.oid
.hash
;
1087 static int write_graph_chunk_data(struct hashfile
*f
,
1088 struct write_commit_graph_context
*ctx
)
1090 struct commit
**list
= ctx
->commits
.list
;
1091 struct commit
**last
= ctx
->commits
.list
+ ctx
->commits
.nr
;
1092 uint32_t num_extra_edges
= 0;
1094 while (list
< last
) {
1095 struct commit_list
*parent
;
1096 struct object_id
*tree
;
1098 uint32_t packedDate
[2];
1099 display_progress(ctx
->progress
, ++ctx
->progress_cnt
);
1101 if (parse_commit_no_graph(*list
))
1102 die(_("unable to parse commit %s"),
1103 oid_to_hex(&(*list
)->object
.oid
));
1104 tree
= get_commit_tree_oid(*list
);
1105 hashwrite(f
, tree
->hash
, the_hash_algo
->rawsz
);
1107 parent
= (*list
)->parents
;
1110 edge_value
= GRAPH_PARENT_NONE
;
1112 edge_value
= sha1_pos(parent
->item
->object
.oid
.hash
,
1117 if (edge_value
>= 0)
1118 edge_value
+= ctx
->new_num_commits_in_base
;
1119 else if (ctx
->new_base_graph
) {
1121 if (find_commit_in_graph(parent
->item
,
1122 ctx
->new_base_graph
,
1128 BUG("missing parent %s for commit %s",
1129 oid_to_hex(&parent
->item
->object
.oid
),
1130 oid_to_hex(&(*list
)->object
.oid
));
1133 hashwrite_be32(f
, edge_value
);
1136 parent
= parent
->next
;
1139 edge_value
= GRAPH_PARENT_NONE
;
1140 else if (parent
->next
)
1141 edge_value
= GRAPH_EXTRA_EDGES_NEEDED
| num_extra_edges
;
1143 edge_value
= sha1_pos(parent
->item
->object
.oid
.hash
,
1148 if (edge_value
>= 0)
1149 edge_value
+= ctx
->new_num_commits_in_base
;
1150 else if (ctx
->new_base_graph
) {
1152 if (find_commit_in_graph(parent
->item
,
1153 ctx
->new_base_graph
,
1159 BUG("missing parent %s for commit %s",
1160 oid_to_hex(&parent
->item
->object
.oid
),
1161 oid_to_hex(&(*list
)->object
.oid
));
1164 hashwrite_be32(f
, edge_value
);
1166 if (edge_value
& GRAPH_EXTRA_EDGES_NEEDED
) {
1169 parent
= parent
->next
;
1173 if (sizeof((*list
)->date
) > 4)
1174 packedDate
[0] = htonl(((*list
)->date
>> 32) & 0x3);
1178 packedDate
[0] |= htonl(*topo_level_slab_at(ctx
->topo_levels
, *list
) << 2);
1180 packedDate
[1] = htonl((*list
)->date
);
1181 hashwrite(f
, packedDate
, 8);
1189 static int write_graph_chunk_generation_data(struct hashfile
*f
,
1190 struct write_commit_graph_context
*ctx
)
1192 int i
, num_generation_data_overflows
= 0;
1194 for (i
= 0; i
< ctx
->commits
.nr
; i
++) {
1195 struct commit
*c
= ctx
->commits
.list
[i
];
1196 timestamp_t offset
= commit_graph_data_at(c
)->generation
- c
->date
;
1197 display_progress(ctx
->progress
, ++ctx
->progress_cnt
);
1199 if (offset
> GENERATION_NUMBER_V2_OFFSET_MAX
) {
1200 offset
= CORRECTED_COMMIT_DATE_OFFSET_OVERFLOW
| num_generation_data_overflows
;
1201 num_generation_data_overflows
++;
1204 hashwrite_be32(f
, offset
);
1210 static int write_graph_chunk_generation_data_overflow(struct hashfile
*f
,
1211 struct write_commit_graph_context
*ctx
)
1214 for (i
= 0; i
< ctx
->commits
.nr
; i
++) {
1215 struct commit
*c
= ctx
->commits
.list
[i
];
1216 timestamp_t offset
= commit_graph_data_at(c
)->generation
- c
->date
;
1217 display_progress(ctx
->progress
, ++ctx
->progress_cnt
);
1219 if (offset
> GENERATION_NUMBER_V2_OFFSET_MAX
) {
1220 hashwrite_be32(f
, offset
>> 32);
1221 hashwrite_be32(f
, (uint32_t) offset
);
1228 static int write_graph_chunk_extra_edges(struct hashfile
*f
,
1229 struct write_commit_graph_context
*ctx
)
1231 struct commit
**list
= ctx
->commits
.list
;
1232 struct commit
**last
= ctx
->commits
.list
+ ctx
->commits
.nr
;
1233 struct commit_list
*parent
;
1235 while (list
< last
) {
1236 int num_parents
= 0;
1238 display_progress(ctx
->progress
, ++ctx
->progress_cnt
);
1240 for (parent
= (*list
)->parents
; num_parents
< 3 && parent
;
1241 parent
= parent
->next
)
1244 if (num_parents
<= 2) {
1249 /* Since num_parents > 2, this initializer is safe. */
1250 for (parent
= (*list
)->parents
->next
; parent
; parent
= parent
->next
) {
1251 int edge_value
= sha1_pos(parent
->item
->object
.oid
.hash
,
1256 if (edge_value
>= 0)
1257 edge_value
+= ctx
->new_num_commits_in_base
;
1258 else if (ctx
->new_base_graph
) {
1260 if (find_commit_in_graph(parent
->item
,
1261 ctx
->new_base_graph
,
1267 BUG("missing parent %s for commit %s",
1268 oid_to_hex(&parent
->item
->object
.oid
),
1269 oid_to_hex(&(*list
)->object
.oid
));
1270 else if (!parent
->next
)
1271 edge_value
|= GRAPH_LAST_EDGE
;
1273 hashwrite_be32(f
, edge_value
);
1282 static int write_graph_chunk_bloom_indexes(struct hashfile
*f
,
1283 struct write_commit_graph_context
*ctx
)
1285 struct commit
**list
= ctx
->commits
.list
;
1286 struct commit
**last
= ctx
->commits
.list
+ ctx
->commits
.nr
;
1287 uint32_t cur_pos
= 0;
1289 while (list
< last
) {
1290 struct bloom_filter
*filter
= get_bloom_filter(ctx
->r
, *list
);
1291 size_t len
= filter
? filter
->len
: 0;
1293 display_progress(ctx
->progress
, ++ctx
->progress_cnt
);
1294 hashwrite_be32(f
, cur_pos
);
1301 static void trace2_bloom_filter_settings(struct write_commit_graph_context
*ctx
)
1303 struct json_writer jw
= JSON_WRITER_INIT
;
1305 jw_object_begin(&jw
, 0);
1306 jw_object_intmax(&jw
, "hash_version", ctx
->bloom_settings
->hash_version
);
1307 jw_object_intmax(&jw
, "num_hashes", ctx
->bloom_settings
->num_hashes
);
1308 jw_object_intmax(&jw
, "bits_per_entry", ctx
->bloom_settings
->bits_per_entry
);
1309 jw_object_intmax(&jw
, "max_changed_paths", ctx
->bloom_settings
->max_changed_paths
);
1312 trace2_data_json("bloom", ctx
->r
, "settings", &jw
);
1317 static int write_graph_chunk_bloom_data(struct hashfile
*f
,
1318 struct write_commit_graph_context
*ctx
)
1320 struct commit
**list
= ctx
->commits
.list
;
1321 struct commit
**last
= ctx
->commits
.list
+ ctx
->commits
.nr
;
1323 trace2_bloom_filter_settings(ctx
);
1325 hashwrite_be32(f
, ctx
->bloom_settings
->hash_version
);
1326 hashwrite_be32(f
, ctx
->bloom_settings
->num_hashes
);
1327 hashwrite_be32(f
, ctx
->bloom_settings
->bits_per_entry
);
1329 while (list
< last
) {
1330 struct bloom_filter
*filter
= get_bloom_filter(ctx
->r
, *list
);
1331 size_t len
= filter
? filter
->len
: 0;
1333 display_progress(ctx
->progress
, ++ctx
->progress_cnt
);
1335 hashwrite(f
, filter
->data
, len
* sizeof(unsigned char));
1342 static int add_packed_commits(const struct object_id
*oid
,
1343 struct packed_git
*pack
,
1347 struct write_commit_graph_context
*ctx
= (struct write_commit_graph_context
*)data
;
1348 enum object_type type
;
1349 off_t offset
= nth_packed_object_offset(pack
, pos
);
1350 struct object_info oi
= OBJECT_INFO_INIT
;
1353 display_progress(ctx
->progress
, ++ctx
->progress_done
);
1356 if (packed_object_info(ctx
->r
, pack
, offset
, &oi
) < 0)
1357 die(_("unable to get type of object %s"), oid_to_hex(oid
));
1359 if (type
!= OBJ_COMMIT
)
1362 oid_array_append(&ctx
->oids
, oid
);
1363 set_commit_pos(ctx
->r
, oid
);
1368 static void add_missing_parents(struct write_commit_graph_context
*ctx
, struct commit
*commit
)
1370 struct commit_list
*parent
;
1371 for (parent
= commit
->parents
; parent
; parent
= parent
->next
) {
1372 if (!(parent
->item
->object
.flags
& REACHABLE
)) {
1373 oid_array_append(&ctx
->oids
, &parent
->item
->object
.oid
);
1374 parent
->item
->object
.flags
|= REACHABLE
;
1379 static void close_reachable(struct write_commit_graph_context
*ctx
)
1382 struct commit
*commit
;
1383 enum commit_graph_split_flags flags
= ctx
->opts
?
1384 ctx
->opts
->split_flags
: COMMIT_GRAPH_SPLIT_UNSPECIFIED
;
1386 if (ctx
->report_progress
)
1387 ctx
->progress
= start_delayed_progress(
1388 _("Loading known commits in commit graph"),
1390 for (i
= 0; i
< ctx
->oids
.nr
; i
++) {
1391 display_progress(ctx
->progress
, i
+ 1);
1392 commit
= lookup_commit(ctx
->r
, &ctx
->oids
.oid
[i
]);
1394 commit
->object
.flags
|= REACHABLE
;
1396 stop_progress(&ctx
->progress
);
1399 * As this loop runs, ctx->oids.nr may grow, but not more
1400 * than the number of missing commits in the reachable
1403 if (ctx
->report_progress
)
1404 ctx
->progress
= start_delayed_progress(
1405 _("Expanding reachable commits in commit graph"),
1407 for (i
= 0; i
< ctx
->oids
.nr
; i
++) {
1408 display_progress(ctx
->progress
, i
+ 1);
1409 commit
= lookup_commit(ctx
->r
, &ctx
->oids
.oid
[i
]);
1414 if ((!parse_commit(commit
) &&
1415 commit_graph_position(commit
) == COMMIT_NOT_FROM_GRAPH
) ||
1416 flags
== COMMIT_GRAPH_SPLIT_REPLACE
)
1417 add_missing_parents(ctx
, commit
);
1418 } else if (!parse_commit_no_graph(commit
))
1419 add_missing_parents(ctx
, commit
);
1421 stop_progress(&ctx
->progress
);
1423 if (ctx
->report_progress
)
1424 ctx
->progress
= start_delayed_progress(
1425 _("Clearing commit marks in commit graph"),
1427 for (i
= 0; i
< ctx
->oids
.nr
; i
++) {
1428 display_progress(ctx
->progress
, i
+ 1);
1429 commit
= lookup_commit(ctx
->r
, &ctx
->oids
.oid
[i
]);
1432 commit
->object
.flags
&= ~REACHABLE
;
1434 stop_progress(&ctx
->progress
);
1437 static void compute_generation_numbers(struct write_commit_graph_context
*ctx
)
1440 struct commit_list
*list
= NULL
;
1442 if (ctx
->report_progress
)
1443 ctx
->progress
= start_delayed_progress(
1444 _("Computing commit graph generation numbers"),
1446 for (i
= 0; i
< ctx
->commits
.nr
; i
++) {
1447 uint32_t level
= *topo_level_slab_at(ctx
->topo_levels
, ctx
->commits
.list
[i
]);
1448 timestamp_t corrected_commit_date
= commit_graph_data_at(ctx
->commits
.list
[i
])->generation
;
1450 display_progress(ctx
->progress
, i
+ 1);
1451 if (level
!= GENERATION_NUMBER_ZERO
&&
1452 corrected_commit_date
!= GENERATION_NUMBER_ZERO
)
1455 commit_list_insert(ctx
->commits
.list
[i
], &list
);
1457 struct commit
*current
= list
->item
;
1458 struct commit_list
*parent
;
1459 int all_parents_computed
= 1;
1460 uint32_t max_level
= 0;
1461 timestamp_t max_corrected_commit_date
= 0;
1463 for (parent
= current
->parents
; parent
; parent
= parent
->next
) {
1464 level
= *topo_level_slab_at(ctx
->topo_levels
, parent
->item
);
1465 corrected_commit_date
= commit_graph_data_at(parent
->item
)->generation
;
1467 if (level
== GENERATION_NUMBER_ZERO
||
1468 corrected_commit_date
== GENERATION_NUMBER_ZERO
) {
1469 all_parents_computed
= 0;
1470 commit_list_insert(parent
->item
, &list
);
1474 if (level
> max_level
)
1477 if (corrected_commit_date
> max_corrected_commit_date
)
1478 max_corrected_commit_date
= corrected_commit_date
;
1481 if (all_parents_computed
) {
1484 if (max_level
> GENERATION_NUMBER_V1_MAX
- 1)
1485 max_level
= GENERATION_NUMBER_V1_MAX
- 1;
1486 *topo_level_slab_at(ctx
->topo_levels
, current
) = max_level
+ 1;
1488 if (current
->date
&& current
->date
> max_corrected_commit_date
)
1489 max_corrected_commit_date
= current
->date
- 1;
1490 commit_graph_data_at(current
)->generation
= max_corrected_commit_date
+ 1;
1492 if (commit_graph_data_at(current
)->generation
- current
->date
> GENERATION_NUMBER_V2_OFFSET_MAX
)
1493 ctx
->num_generation_data_overflows
++;
1497 stop_progress(&ctx
->progress
);
1500 static void trace2_bloom_filter_write_statistics(struct write_commit_graph_context
*ctx
)
1502 trace2_data_intmax("commit-graph", ctx
->r
, "filter-computed",
1503 ctx
->count_bloom_filter_computed
);
1504 trace2_data_intmax("commit-graph", ctx
->r
, "filter-not-computed",
1505 ctx
->count_bloom_filter_not_computed
);
1506 trace2_data_intmax("commit-graph", ctx
->r
, "filter-trunc-empty",
1507 ctx
->count_bloom_filter_trunc_empty
);
1508 trace2_data_intmax("commit-graph", ctx
->r
, "filter-trunc-large",
1509 ctx
->count_bloom_filter_trunc_large
);
1512 static void compute_bloom_filters(struct write_commit_graph_context
*ctx
)
1515 struct progress
*progress
= NULL
;
1516 struct commit
**sorted_commits
;
1517 int max_new_filters
;
1519 init_bloom_filters();
1521 if (ctx
->report_progress
)
1522 progress
= start_delayed_progress(
1523 _("Computing commit changed paths Bloom filters"),
1526 ALLOC_ARRAY(sorted_commits
, ctx
->commits
.nr
);
1527 COPY_ARRAY(sorted_commits
, ctx
->commits
.list
, ctx
->commits
.nr
);
1529 if (ctx
->order_by_pack
)
1530 QSORT(sorted_commits
, ctx
->commits
.nr
, commit_pos_cmp
);
1532 QSORT(sorted_commits
, ctx
->commits
.nr
, commit_gen_cmp
);
1534 max_new_filters
= ctx
->opts
&& ctx
->opts
->max_new_filters
>= 0 ?
1535 ctx
->opts
->max_new_filters
: ctx
->commits
.nr
;
1537 for (i
= 0; i
< ctx
->commits
.nr
; i
++) {
1538 enum bloom_filter_computed computed
= 0;
1539 struct commit
*c
= sorted_commits
[i
];
1540 struct bloom_filter
*filter
= get_or_compute_bloom_filter(
1543 ctx
->count_bloom_filter_computed
< max_new_filters
,
1544 ctx
->bloom_settings
,
1546 if (computed
& BLOOM_COMPUTED
) {
1547 ctx
->count_bloom_filter_computed
++;
1548 if (computed
& BLOOM_TRUNC_EMPTY
)
1549 ctx
->count_bloom_filter_trunc_empty
++;
1550 if (computed
& BLOOM_TRUNC_LARGE
)
1551 ctx
->count_bloom_filter_trunc_large
++;
1552 } else if (computed
& BLOOM_NOT_COMPUTED
)
1553 ctx
->count_bloom_filter_not_computed
++;
1554 ctx
->total_bloom_filter_data_size
+= filter
1555 ? sizeof(unsigned char) * filter
->len
: 0;
1556 display_progress(progress
, i
+ 1);
1559 if (trace2_is_enabled())
1560 trace2_bloom_filter_write_statistics(ctx
);
1562 free(sorted_commits
);
1563 stop_progress(&progress
);
1566 struct refs_cb_data
{
1567 struct oidset
*commits
;
1568 struct progress
*progress
;
1571 static int add_ref_to_set(const char *refname
,
1572 const struct object_id
*oid
,
1573 int flags
, void *cb_data
)
1575 struct object_id peeled
;
1576 struct refs_cb_data
*data
= (struct refs_cb_data
*)cb_data
;
1578 if (!peel_ref(refname
, &peeled
))
1580 if (oid_object_info(the_repository
, oid
, NULL
) == OBJ_COMMIT
)
1581 oidset_insert(data
->commits
, oid
);
1583 display_progress(data
->progress
, oidset_size(data
->commits
));
1588 int write_commit_graph_reachable(struct object_directory
*odb
,
1589 enum commit_graph_write_flags flags
,
1590 const struct commit_graph_opts
*opts
)
1592 struct oidset commits
= OIDSET_INIT
;
1593 struct refs_cb_data data
;
1596 memset(&data
, 0, sizeof(data
));
1597 data
.commits
= &commits
;
1598 if (flags
& COMMIT_GRAPH_WRITE_PROGRESS
)
1599 data
.progress
= start_delayed_progress(
1600 _("Collecting referenced commits"), 0);
1602 for_each_ref(add_ref_to_set
, &data
);
1604 stop_progress(&data
.progress
);
1606 result
= write_commit_graph(odb
, NULL
, &commits
,
1609 oidset_clear(&commits
);
1613 static int fill_oids_from_packs(struct write_commit_graph_context
*ctx
,
1614 struct string_list
*pack_indexes
)
1617 struct strbuf progress_title
= STRBUF_INIT
;
1618 struct strbuf packname
= STRBUF_INIT
;
1621 strbuf_addf(&packname
, "%s/pack/", ctx
->odb
->path
);
1622 dirlen
= packname
.len
;
1623 if (ctx
->report_progress
) {
1624 strbuf_addf(&progress_title
,
1625 Q_("Finding commits for commit graph in %d pack",
1626 "Finding commits for commit graph in %d packs",
1629 ctx
->progress
= start_delayed_progress(progress_title
.buf
, 0);
1630 ctx
->progress_done
= 0;
1632 for (i
= 0; i
< pack_indexes
->nr
; i
++) {
1633 struct packed_git
*p
;
1634 strbuf_setlen(&packname
, dirlen
);
1635 strbuf_addstr(&packname
, pack_indexes
->items
[i
].string
);
1636 p
= add_packed_git(packname
.buf
, packname
.len
, 1);
1638 error(_("error adding pack %s"), packname
.buf
);
1641 if (open_pack_index(p
)) {
1642 error(_("error opening index for %s"), packname
.buf
);
1645 for_each_object_in_pack(p
, add_packed_commits
, ctx
,
1646 FOR_EACH_OBJECT_PACK_ORDER
);
1651 stop_progress(&ctx
->progress
);
1652 strbuf_release(&progress_title
);
1653 strbuf_release(&packname
);
1658 static int fill_oids_from_commits(struct write_commit_graph_context
*ctx
,
1659 struct oidset
*commits
)
1661 struct oidset_iter iter
;
1662 struct object_id
*oid
;
1664 if (!oidset_size(commits
))
1667 oidset_iter_init(commits
, &iter
);
1668 while ((oid
= oidset_iter_next(&iter
))) {
1669 oid_array_append(&ctx
->oids
, oid
);
1675 static void fill_oids_from_all_packs(struct write_commit_graph_context
*ctx
)
1677 if (ctx
->report_progress
)
1678 ctx
->progress
= start_delayed_progress(
1679 _("Finding commits for commit graph among packed objects"),
1680 ctx
->approx_nr_objects
);
1681 for_each_packed_object(add_packed_commits
, ctx
,
1682 FOR_EACH_OBJECT_PACK_ORDER
);
1683 if (ctx
->progress_done
< ctx
->approx_nr_objects
)
1684 display_progress(ctx
->progress
, ctx
->approx_nr_objects
);
1685 stop_progress(&ctx
->progress
);
1688 static void copy_oids_to_commits(struct write_commit_graph_context
*ctx
)
1691 enum commit_graph_split_flags flags
= ctx
->opts
?
1692 ctx
->opts
->split_flags
: COMMIT_GRAPH_SPLIT_UNSPECIFIED
;
1694 ctx
->num_extra_edges
= 0;
1695 if (ctx
->report_progress
)
1696 ctx
->progress
= start_delayed_progress(
1697 _("Finding extra edges in commit graph"),
1699 oid_array_sort(&ctx
->oids
);
1700 for (i
= 0; i
< ctx
->oids
.nr
; i
= oid_array_next_unique(&ctx
->oids
, i
)) {
1701 unsigned int num_parents
;
1703 display_progress(ctx
->progress
, i
+ 1);
1705 ALLOC_GROW(ctx
->commits
.list
, ctx
->commits
.nr
+ 1, ctx
->commits
.alloc
);
1706 ctx
->commits
.list
[ctx
->commits
.nr
] = lookup_commit(ctx
->r
, &ctx
->oids
.oid
[i
]);
1708 if (ctx
->split
&& flags
!= COMMIT_GRAPH_SPLIT_REPLACE
&&
1709 commit_graph_position(ctx
->commits
.list
[ctx
->commits
.nr
]) != COMMIT_NOT_FROM_GRAPH
)
1712 if (ctx
->split
&& flags
== COMMIT_GRAPH_SPLIT_REPLACE
)
1713 parse_commit(ctx
->commits
.list
[ctx
->commits
.nr
]);
1715 parse_commit_no_graph(ctx
->commits
.list
[ctx
->commits
.nr
]);
1717 num_parents
= commit_list_count(ctx
->commits
.list
[ctx
->commits
.nr
]->parents
);
1718 if (num_parents
> 2)
1719 ctx
->num_extra_edges
+= num_parents
- 1;
1723 stop_progress(&ctx
->progress
);
1726 static int write_graph_chunk_base_1(struct hashfile
*f
,
1727 struct commit_graph
*g
)
1734 num
= write_graph_chunk_base_1(f
, g
->base_graph
);
1735 hashwrite(f
, g
->oid
.hash
, the_hash_algo
->rawsz
);
1739 static int write_graph_chunk_base(struct hashfile
*f
,
1740 struct write_commit_graph_context
*ctx
)
1742 int num
= write_graph_chunk_base_1(f
, ctx
->new_base_graph
);
1744 if (num
!= ctx
->num_commit_graphs_after
- 1) {
1745 error(_("failed to write correct number of base graph ids"));
1752 typedef int (*chunk_write_fn
)(struct hashfile
*f
,
1753 struct write_commit_graph_context
*ctx
);
1758 chunk_write_fn write_fn
;
1761 static int write_commit_graph_file(struct write_commit_graph_context
*ctx
)
1766 struct lock_file lk
= LOCK_INIT
;
1767 struct chunk_info chunks
[MAX_NUM_CHUNKS
+ 1];
1768 const unsigned hashsz
= the_hash_algo
->rawsz
;
1769 struct strbuf progress_title
= STRBUF_INIT
;
1771 uint64_t chunk_offset
;
1772 struct object_id file_hash
;
1775 struct strbuf tmp_file
= STRBUF_INIT
;
1777 strbuf_addf(&tmp_file
,
1778 "%s/info/commit-graphs/tmp_graph_XXXXXX",
1780 ctx
->graph_name
= strbuf_detach(&tmp_file
, NULL
);
1782 ctx
->graph_name
= get_commit_graph_filename(ctx
->odb
);
1785 if (safe_create_leading_directories(ctx
->graph_name
)) {
1786 UNLEAK(ctx
->graph_name
);
1787 error(_("unable to create leading directories of %s"),
1793 char *lock_name
= get_commit_graph_chain_filename(ctx
->odb
);
1795 hold_lock_file_for_update_mode(&lk
, lock_name
,
1796 LOCK_DIE_ON_ERROR
, 0444);
1798 fd
= git_mkstemp_mode(ctx
->graph_name
, 0444);
1800 error(_("unable to create temporary graph layer"));
1804 if (adjust_shared_perm(ctx
->graph_name
)) {
1805 error(_("unable to adjust shared permissions for '%s'"),
1810 f
= hashfd(fd
, ctx
->graph_name
);
1812 hold_lock_file_for_update_mode(&lk
, ctx
->graph_name
,
1813 LOCK_DIE_ON_ERROR
, 0444);
1814 fd
= lk
.tempfile
->fd
;
1815 f
= hashfd(lk
.tempfile
->fd
, lk
.tempfile
->filename
.buf
);
1818 chunks
[0].id
= GRAPH_CHUNKID_OIDFANOUT
;
1819 chunks
[0].size
= GRAPH_FANOUT_SIZE
;
1820 chunks
[0].write_fn
= write_graph_chunk_fanout
;
1821 chunks
[1].id
= GRAPH_CHUNKID_OIDLOOKUP
;
1822 chunks
[1].size
= hashsz
* ctx
->commits
.nr
;
1823 chunks
[1].write_fn
= write_graph_chunk_oids
;
1824 chunks
[2].id
= GRAPH_CHUNKID_DATA
;
1825 chunks
[2].size
= (hashsz
+ 16) * ctx
->commits
.nr
;
1826 chunks
[2].write_fn
= write_graph_chunk_data
;
1828 if (git_env_bool(GIT_TEST_COMMIT_GRAPH_NO_GDAT
, 0))
1829 ctx
->write_generation_data
= 0;
1830 if (ctx
->write_generation_data
) {
1831 chunks
[num_chunks
].id
= GRAPH_CHUNKID_GENERATION_DATA
;
1832 chunks
[num_chunks
].size
= sizeof(uint32_t) * ctx
->commits
.nr
;
1833 chunks
[num_chunks
].write_fn
= write_graph_chunk_generation_data
;
1836 if (ctx
->num_generation_data_overflows
) {
1837 chunks
[num_chunks
].id
= GRAPH_CHUNKID_GENERATION_DATA_OVERFLOW
;
1838 chunks
[num_chunks
].size
= sizeof(timestamp_t
) * ctx
->num_generation_data_overflows
;
1839 chunks
[num_chunks
].write_fn
= write_graph_chunk_generation_data_overflow
;
1842 if (ctx
->num_extra_edges
) {
1843 chunks
[num_chunks
].id
= GRAPH_CHUNKID_EXTRAEDGES
;
1844 chunks
[num_chunks
].size
= 4 * ctx
->num_extra_edges
;
1845 chunks
[num_chunks
].write_fn
= write_graph_chunk_extra_edges
;
1848 if (ctx
->changed_paths
) {
1849 chunks
[num_chunks
].id
= GRAPH_CHUNKID_BLOOMINDEXES
;
1850 chunks
[num_chunks
].size
= sizeof(uint32_t) * ctx
->commits
.nr
;
1851 chunks
[num_chunks
].write_fn
= write_graph_chunk_bloom_indexes
;
1853 chunks
[num_chunks
].id
= GRAPH_CHUNKID_BLOOMDATA
;
1854 chunks
[num_chunks
].size
= sizeof(uint32_t) * 3
1855 + ctx
->total_bloom_filter_data_size
;
1856 chunks
[num_chunks
].write_fn
= write_graph_chunk_bloom_data
;
1859 if (ctx
->num_commit_graphs_after
> 1) {
1860 chunks
[num_chunks
].id
= GRAPH_CHUNKID_BASE
;
1861 chunks
[num_chunks
].size
= hashsz
* (ctx
->num_commit_graphs_after
- 1);
1862 chunks
[num_chunks
].write_fn
= write_graph_chunk_base
;
1866 chunks
[num_chunks
].id
= 0;
1867 chunks
[num_chunks
].size
= 0;
1869 hashwrite_be32(f
, GRAPH_SIGNATURE
);
1871 hashwrite_u8(f
, GRAPH_VERSION
);
1872 hashwrite_u8(f
, oid_version());
1873 hashwrite_u8(f
, num_chunks
);
1874 hashwrite_u8(f
, ctx
->num_commit_graphs_after
- 1);
1876 chunk_offset
= 8 + (num_chunks
+ 1) * GRAPH_CHUNKLOOKUP_WIDTH
;
1877 for (i
= 0; i
<= num_chunks
; i
++) {
1878 uint32_t chunk_write
[3];
1880 chunk_write
[0] = htonl(chunks
[i
].id
);
1881 chunk_write
[1] = htonl(chunk_offset
>> 32);
1882 chunk_write
[2] = htonl(chunk_offset
& 0xffffffff);
1883 hashwrite(f
, chunk_write
, 12);
1885 chunk_offset
+= chunks
[i
].size
;
1888 if (ctx
->report_progress
) {
1889 strbuf_addf(&progress_title
,
1890 Q_("Writing out commit graph in %d pass",
1891 "Writing out commit graph in %d passes",
1894 ctx
->progress
= start_delayed_progress(
1896 num_chunks
* ctx
->commits
.nr
);
1899 for (i
= 0; i
< num_chunks
; i
++) {
1900 uint64_t start_offset
= f
->total
+ f
->offset
;
1902 if (chunks
[i
].write_fn(f
, ctx
))
1905 if (f
->total
+ f
->offset
!= start_offset
+ chunks
[i
].size
)
1906 BUG("expected to write %"PRId64
" bytes to chunk %"PRIx32
", but wrote %"PRId64
" instead",
1907 chunks
[i
].size
, chunks
[i
].id
,
1908 f
->total
+ f
->offset
- start_offset
);
1911 stop_progress(&ctx
->progress
);
1912 strbuf_release(&progress_title
);
1914 if (ctx
->split
&& ctx
->base_graph_name
&& ctx
->num_commit_graphs_after
> 1) {
1915 char *new_base_hash
= xstrdup(oid_to_hex(&ctx
->new_base_graph
->oid
));
1916 char *new_base_name
= get_split_graph_filename(ctx
->new_base_graph
->odb
, new_base_hash
);
1918 free(ctx
->commit_graph_filenames_after
[ctx
->num_commit_graphs_after
- 2]);
1919 free(ctx
->commit_graph_hash_after
[ctx
->num_commit_graphs_after
- 2]);
1920 ctx
->commit_graph_filenames_after
[ctx
->num_commit_graphs_after
- 2] = new_base_name
;
1921 ctx
->commit_graph_hash_after
[ctx
->num_commit_graphs_after
- 2] = new_base_hash
;
1924 close_commit_graph(ctx
->r
->objects
);
1925 finalize_hashfile(f
, file_hash
.hash
, CSUM_HASH_IN_STREAM
| CSUM_FSYNC
);
1928 FILE *chainf
= fdopen_lock_file(&lk
, "w");
1929 char *final_graph_name
;
1935 error(_("unable to open commit-graph chain file"));
1939 if (ctx
->base_graph_name
) {
1941 int idx
= ctx
->num_commit_graphs_after
- 1;
1942 if (ctx
->num_commit_graphs_after
> 1)
1945 dest
= ctx
->commit_graph_filenames_after
[idx
];
1947 if (strcmp(ctx
->base_graph_name
, dest
)) {
1948 result
= rename(ctx
->base_graph_name
, dest
);
1951 error(_("failed to rename base commit-graph file"));
1956 char *graph_name
= get_commit_graph_filename(ctx
->odb
);
1960 ctx
->commit_graph_hash_after
[ctx
->num_commit_graphs_after
- 1] = xstrdup(oid_to_hex(&file_hash
));
1961 final_graph_name
= get_split_graph_filename(ctx
->odb
,
1962 ctx
->commit_graph_hash_after
[ctx
->num_commit_graphs_after
- 1]);
1963 ctx
->commit_graph_filenames_after
[ctx
->num_commit_graphs_after
- 1] = final_graph_name
;
1965 result
= rename(ctx
->graph_name
, final_graph_name
);
1967 for (i
= 0; i
< ctx
->num_commit_graphs_after
; i
++)
1968 fprintf(lk
.tempfile
->fp
, "%s\n", ctx
->commit_graph_hash_after
[i
]);
1971 error(_("failed to rename temporary commit-graph file"));
1976 commit_lock_file(&lk
);
1981 static void split_graph_merge_strategy(struct write_commit_graph_context
*ctx
)
1983 struct commit_graph
*g
;
1984 uint32_t num_commits
;
1985 enum commit_graph_split_flags flags
= COMMIT_GRAPH_SPLIT_UNSPECIFIED
;
1988 int max_commits
= 0;
1992 max_commits
= ctx
->opts
->max_commits
;
1994 if (ctx
->opts
->size_multiple
)
1995 size_mult
= ctx
->opts
->size_multiple
;
1997 flags
= ctx
->opts
->split_flags
;
2000 g
= ctx
->r
->objects
->commit_graph
;
2001 num_commits
= ctx
->commits
.nr
;
2002 if (flags
== COMMIT_GRAPH_SPLIT_REPLACE
)
2003 ctx
->num_commit_graphs_after
= 1;
2005 ctx
->num_commit_graphs_after
= ctx
->num_commit_graphs_before
+ 1;
2007 if (flags
!= COMMIT_GRAPH_SPLIT_MERGE_PROHIBITED
&&
2008 flags
!= COMMIT_GRAPH_SPLIT_REPLACE
) {
2009 while (g
&& (g
->num_commits
<= size_mult
* num_commits
||
2010 (max_commits
&& num_commits
> max_commits
))) {
2011 if (g
->odb
!= ctx
->odb
)
2014 num_commits
+= g
->num_commits
;
2017 ctx
->num_commit_graphs_after
--;
2021 if (flags
!= COMMIT_GRAPH_SPLIT_REPLACE
)
2022 ctx
->new_base_graph
= g
;
2023 else if (ctx
->num_commit_graphs_after
!= 1)
2024 BUG("split_graph_merge_strategy: num_commit_graphs_after "
2025 "should be 1 with --split=replace");
2027 if (ctx
->num_commit_graphs_after
== 2) {
2028 char *old_graph_name
= get_commit_graph_filename(g
->odb
);
2030 if (!strcmp(g
->filename
, old_graph_name
) &&
2031 g
->odb
!= ctx
->odb
) {
2032 ctx
->num_commit_graphs_after
= 1;
2033 ctx
->new_base_graph
= NULL
;
2036 free(old_graph_name
);
2039 CALLOC_ARRAY(ctx
->commit_graph_filenames_after
, ctx
->num_commit_graphs_after
);
2040 CALLOC_ARRAY(ctx
->commit_graph_hash_after
, ctx
->num_commit_graphs_after
);
2042 for (i
= 0; i
< ctx
->num_commit_graphs_after
&&
2043 i
< ctx
->num_commit_graphs_before
; i
++)
2044 ctx
->commit_graph_filenames_after
[i
] = xstrdup(ctx
->commit_graph_filenames_before
[i
]);
2046 i
= ctx
->num_commit_graphs_before
- 1;
2047 g
= ctx
->r
->objects
->commit_graph
;
2050 if (i
< ctx
->num_commit_graphs_after
)
2051 ctx
->commit_graph_hash_after
[i
] = xstrdup(oid_to_hex(&g
->oid
));
2054 * If the topmost remaining layer has generation data chunk, the
2055 * resultant layer also has generation data chunk.
2057 if (i
== ctx
->num_commit_graphs_after
- 2)
2058 ctx
->write_generation_data
= !!g
->chunk_generation_data
;
2065 static void merge_commit_graph(struct write_commit_graph_context
*ctx
,
2066 struct commit_graph
*g
)
2069 uint32_t offset
= g
->num_commits_in_base
;
2071 ALLOC_GROW(ctx
->commits
.list
, ctx
->commits
.nr
+ g
->num_commits
, ctx
->commits
.alloc
);
2073 for (i
= 0; i
< g
->num_commits
; i
++) {
2074 struct object_id oid
;
2075 struct commit
*result
;
2077 display_progress(ctx
->progress
, i
+ 1);
2079 load_oid_from_graph(g
, i
+ offset
, &oid
);
2081 /* only add commits if they still exist in the repo */
2082 result
= lookup_commit_reference_gently(ctx
->r
, &oid
, 1);
2085 ctx
->commits
.list
[ctx
->commits
.nr
] = result
;
2091 static int commit_compare(const void *_a
, const void *_b
)
2093 const struct commit
*a
= *(const struct commit
**)_a
;
2094 const struct commit
*b
= *(const struct commit
**)_b
;
2095 return oidcmp(&a
->object
.oid
, &b
->object
.oid
);
2098 static void sort_and_scan_merged_commits(struct write_commit_graph_context
*ctx
)
2100 uint32_t i
, dedup_i
= 0;
2102 if (ctx
->report_progress
)
2103 ctx
->progress
= start_delayed_progress(
2104 _("Scanning merged commits"),
2107 QSORT(ctx
->commits
.list
, ctx
->commits
.nr
, commit_compare
);
2109 ctx
->num_extra_edges
= 0;
2110 for (i
= 0; i
< ctx
->commits
.nr
; i
++) {
2111 display_progress(ctx
->progress
, i
);
2113 if (i
&& oideq(&ctx
->commits
.list
[i
- 1]->object
.oid
,
2114 &ctx
->commits
.list
[i
]->object
.oid
)) {
2116 * Silently ignore duplicates. These were likely
2117 * created due to a commit appearing in multiple
2118 * layers of the chain, which is unexpected but
2119 * not invalid. We should make sure there is a
2120 * unique copy in the new layer.
2123 unsigned int num_parents
;
2125 ctx
->commits
.list
[dedup_i
] = ctx
->commits
.list
[i
];
2128 num_parents
= commit_list_count(ctx
->commits
.list
[i
]->parents
);
2129 if (num_parents
> 2)
2130 ctx
->num_extra_edges
+= num_parents
- 1;
2134 ctx
->commits
.nr
= dedup_i
;
2136 stop_progress(&ctx
->progress
);
2139 static void merge_commit_graphs(struct write_commit_graph_context
*ctx
)
2141 struct commit_graph
*g
= ctx
->r
->objects
->commit_graph
;
2142 uint32_t current_graph_number
= ctx
->num_commit_graphs_before
;
2144 while (g
&& current_graph_number
>= ctx
->num_commit_graphs_after
) {
2145 current_graph_number
--;
2147 if (ctx
->report_progress
)
2148 ctx
->progress
= start_delayed_progress(_("Merging commit-graph"), 0);
2150 merge_commit_graph(ctx
, g
);
2151 stop_progress(&ctx
->progress
);
2157 ctx
->new_base_graph
= g
;
2158 ctx
->new_num_commits_in_base
= g
->num_commits
+ g
->num_commits_in_base
;
2161 if (ctx
->new_base_graph
)
2162 ctx
->base_graph_name
= xstrdup(ctx
->new_base_graph
->filename
);
2164 sort_and_scan_merged_commits(ctx
);
2167 static void mark_commit_graphs(struct write_commit_graph_context
*ctx
)
2170 time_t now
= time(NULL
);
2172 for (i
= ctx
->num_commit_graphs_after
- 1; i
< ctx
->num_commit_graphs_before
; i
++) {
2174 struct utimbuf updated_time
;
2176 stat(ctx
->commit_graph_filenames_before
[i
], &st
);
2178 updated_time
.actime
= st
.st_atime
;
2179 updated_time
.modtime
= now
;
2180 utime(ctx
->commit_graph_filenames_before
[i
], &updated_time
);
2184 static void expire_commit_graphs(struct write_commit_graph_context
*ctx
)
2186 struct strbuf path
= STRBUF_INIT
;
2190 timestamp_t expire_time
= time(NULL
);
2192 if (ctx
->opts
&& ctx
->opts
->expire_time
)
2193 expire_time
= ctx
->opts
->expire_time
;
2195 char *chain_file_name
= get_commit_graph_chain_filename(ctx
->odb
);
2196 unlink(chain_file_name
);
2197 free(chain_file_name
);
2198 ctx
->num_commit_graphs_after
= 0;
2201 strbuf_addstr(&path
, ctx
->odb
->path
);
2202 strbuf_addstr(&path
, "/info/commit-graphs");
2203 dir
= opendir(path
.buf
);
2208 strbuf_addch(&path
, '/');
2209 dirnamelen
= path
.len
;
2210 while ((de
= readdir(dir
)) != NULL
) {
2212 uint32_t i
, found
= 0;
2214 strbuf_setlen(&path
, dirnamelen
);
2215 strbuf_addstr(&path
, de
->d_name
);
2217 stat(path
.buf
, &st
);
2219 if (st
.st_mtime
> expire_time
)
2221 if (path
.len
< 6 || strcmp(path
.buf
+ path
.len
- 6, ".graph"))
2224 for (i
= 0; i
< ctx
->num_commit_graphs_after
; i
++) {
2225 if (!strcmp(ctx
->commit_graph_filenames_after
[i
],
2237 strbuf_release(&path
);
2240 int write_commit_graph(struct object_directory
*odb
,
2241 struct string_list
*pack_indexes
,
2242 struct oidset
*commits
,
2243 enum commit_graph_write_flags flags
,
2244 const struct commit_graph_opts
*opts
)
2246 struct write_commit_graph_context
*ctx
;
2250 struct bloom_filter_settings bloom_settings
= DEFAULT_BLOOM_FILTER_SETTINGS
;
2251 struct topo_level_slab topo_levels
;
2253 prepare_repo_settings(the_repository
);
2254 if (!the_repository
->settings
.core_commit_graph
) {
2255 warning(_("attempting to write a commit-graph, but 'core.commitGraph' is disabled"));
2258 if (!commit_graph_compatible(the_repository
))
2261 ctx
= xcalloc(1, sizeof(struct write_commit_graph_context
));
2262 ctx
->r
= the_repository
;
2264 ctx
->append
= flags
& COMMIT_GRAPH_WRITE_APPEND
? 1 : 0;
2265 ctx
->report_progress
= flags
& COMMIT_GRAPH_WRITE_PROGRESS
? 1 : 0;
2266 ctx
->split
= flags
& COMMIT_GRAPH_WRITE_SPLIT
? 1 : 0;
2268 ctx
->total_bloom_filter_data_size
= 0;
2269 ctx
->write_generation_data
= 1;
2270 ctx
->num_generation_data_overflows
= 0;
2272 bloom_settings
.bits_per_entry
= git_env_ulong("GIT_TEST_BLOOM_SETTINGS_BITS_PER_ENTRY",
2273 bloom_settings
.bits_per_entry
);
2274 bloom_settings
.num_hashes
= git_env_ulong("GIT_TEST_BLOOM_SETTINGS_NUM_HASHES",
2275 bloom_settings
.num_hashes
);
2276 bloom_settings
.max_changed_paths
= git_env_ulong("GIT_TEST_BLOOM_SETTINGS_MAX_CHANGED_PATHS",
2277 bloom_settings
.max_changed_paths
);
2278 ctx
->bloom_settings
= &bloom_settings
;
2280 init_topo_level_slab(&topo_levels
);
2281 ctx
->topo_levels
= &topo_levels
;
2283 if (ctx
->r
->objects
->commit_graph
) {
2284 struct commit_graph
*g
= ctx
->r
->objects
->commit_graph
;
2287 g
->topo_levels
= &topo_levels
;
2292 if (flags
& COMMIT_GRAPH_WRITE_BLOOM_FILTERS
)
2293 ctx
->changed_paths
= 1;
2294 if (!(flags
& COMMIT_GRAPH_NO_WRITE_BLOOM_FILTERS
)) {
2295 struct commit_graph
*g
;
2296 prepare_commit_graph_one(ctx
->r
, ctx
->odb
);
2298 g
= ctx
->r
->objects
->commit_graph
;
2300 /* We have changed-paths already. Keep them in the next graph */
2301 if (g
&& g
->chunk_bloom_data
) {
2302 ctx
->changed_paths
= 1;
2303 ctx
->bloom_settings
= g
->bloom_filter_settings
;
2308 struct commit_graph
*g
;
2309 prepare_commit_graph(ctx
->r
);
2311 g
= ctx
->r
->objects
->commit_graph
;
2314 ctx
->num_commit_graphs_before
++;
2318 if (ctx
->num_commit_graphs_before
) {
2319 ALLOC_ARRAY(ctx
->commit_graph_filenames_before
, ctx
->num_commit_graphs_before
);
2320 i
= ctx
->num_commit_graphs_before
;
2321 g
= ctx
->r
->objects
->commit_graph
;
2324 ctx
->commit_graph_filenames_before
[--i
] = xstrdup(g
->filename
);
2330 replace
= ctx
->opts
->split_flags
& COMMIT_GRAPH_SPLIT_REPLACE
;
2333 ctx
->approx_nr_objects
= approximate_object_count();
2336 prepare_commit_graph_one(ctx
->r
, ctx
->odb
);
2338 if (ctx
->append
&& ctx
->r
->objects
->commit_graph
) {
2339 struct commit_graph
*g
= ctx
->r
->objects
->commit_graph
;
2340 for (i
= 0; i
< g
->num_commits
; i
++) {
2341 struct object_id oid
;
2342 hashcpy(oid
.hash
, g
->chunk_oid_lookup
+ g
->hash_len
* i
);
2343 oid_array_append(&ctx
->oids
, &oid
);
2348 ctx
->order_by_pack
= 1;
2349 if ((res
= fill_oids_from_packs(ctx
, pack_indexes
)))
2354 if ((res
= fill_oids_from_commits(ctx
, commits
)))
2358 if (!pack_indexes
&& !commits
) {
2359 ctx
->order_by_pack
= 1;
2360 fill_oids_from_all_packs(ctx
);
2363 close_reachable(ctx
);
2365 copy_oids_to_commits(ctx
);
2367 if (ctx
->commits
.nr
>= GRAPH_EDGE_LAST_MASK
) {
2368 error(_("too many commits to write graph"));
2373 if (!ctx
->commits
.nr
&& !replace
)
2377 split_graph_merge_strategy(ctx
);
2380 merge_commit_graphs(ctx
);
2382 ctx
->num_commit_graphs_after
= 1;
2384 validate_mixed_generation_chain(ctx
->r
->objects
->commit_graph
);
2386 compute_generation_numbers(ctx
);
2388 if (ctx
->changed_paths
)
2389 compute_bloom_filters(ctx
);
2391 res
= write_commit_graph_file(ctx
);
2394 mark_commit_graphs(ctx
);
2396 expire_commit_graphs(ctx
);
2399 free(ctx
->graph_name
);
2400 free(ctx
->commits
.list
);
2401 oid_array_clear(&ctx
->oids
);
2403 if (ctx
->commit_graph_filenames_after
) {
2404 for (i
= 0; i
< ctx
->num_commit_graphs_after
; i
++) {
2405 free(ctx
->commit_graph_filenames_after
[i
]);
2406 free(ctx
->commit_graph_hash_after
[i
]);
2409 for (i
= 0; i
< ctx
->num_commit_graphs_before
; i
++)
2410 free(ctx
->commit_graph_filenames_before
[i
]);
2412 free(ctx
->commit_graph_filenames_after
);
2413 free(ctx
->commit_graph_filenames_before
);
2414 free(ctx
->commit_graph_hash_after
);
2422 #define VERIFY_COMMIT_GRAPH_ERROR_HASH 2
2423 static int verify_commit_graph_error
;
2425 static void graph_report(const char *fmt
, ...)
2429 verify_commit_graph_error
= 1;
2431 vfprintf(stderr
, fmt
, ap
);
2432 fprintf(stderr
, "\n");
2436 #define GENERATION_ZERO_EXISTS 1
2437 #define GENERATION_NUMBER_EXISTS 2
2439 int verify_commit_graph(struct repository
*r
, struct commit_graph
*g
, int flags
)
2441 uint32_t i
, cur_fanout_pos
= 0;
2442 struct object_id prev_oid
, cur_oid
, checksum
;
2443 int generation_zero
= 0;
2446 struct progress
*progress
= NULL
;
2447 int local_error
= 0;
2450 graph_report("no commit-graph file loaded");
2454 verify_commit_graph_error
= verify_commit_graph_lite(g
);
2455 if (verify_commit_graph_error
)
2456 return verify_commit_graph_error
;
2458 devnull
= open("/dev/null", O_WRONLY
);
2459 f
= hashfd(devnull
, NULL
);
2460 hashwrite(f
, g
->data
, g
->data_len
- g
->hash_len
);
2461 finalize_hashfile(f
, checksum
.hash
, CSUM_CLOSE
);
2462 if (!hasheq(checksum
.hash
, g
->data
+ g
->data_len
- g
->hash_len
)) {
2463 graph_report(_("the commit-graph file has incorrect checksum and is likely corrupt"));
2464 verify_commit_graph_error
= VERIFY_COMMIT_GRAPH_ERROR_HASH
;
2467 for (i
= 0; i
< g
->num_commits
; i
++) {
2468 struct commit
*graph_commit
;
2470 hashcpy(cur_oid
.hash
, g
->chunk_oid_lookup
+ g
->hash_len
* i
);
2472 if (i
&& oidcmp(&prev_oid
, &cur_oid
) >= 0)
2473 graph_report(_("commit-graph has incorrect OID order: %s then %s"),
2474 oid_to_hex(&prev_oid
),
2475 oid_to_hex(&cur_oid
));
2477 oidcpy(&prev_oid
, &cur_oid
);
2479 while (cur_oid
.hash
[0] > cur_fanout_pos
) {
2480 uint32_t fanout_value
= get_be32(g
->chunk_oid_fanout
+ cur_fanout_pos
);
2482 if (i
!= fanout_value
)
2483 graph_report(_("commit-graph has incorrect fanout value: fanout[%d] = %u != %u"),
2484 cur_fanout_pos
, fanout_value
, i
);
2488 graph_commit
= lookup_commit(r
, &cur_oid
);
2489 if (!parse_commit_in_graph_one(r
, g
, graph_commit
))
2490 graph_report(_("failed to parse commit %s from commit-graph"),
2491 oid_to_hex(&cur_oid
));
2494 while (cur_fanout_pos
< 256) {
2495 uint32_t fanout_value
= get_be32(g
->chunk_oid_fanout
+ cur_fanout_pos
);
2497 if (g
->num_commits
!= fanout_value
)
2498 graph_report(_("commit-graph has incorrect fanout value: fanout[%d] = %u != %u"),
2499 cur_fanout_pos
, fanout_value
, i
);
2504 if (verify_commit_graph_error
& ~VERIFY_COMMIT_GRAPH_ERROR_HASH
)
2505 return verify_commit_graph_error
;
2507 if (flags
& COMMIT_GRAPH_WRITE_PROGRESS
)
2508 progress
= start_progress(_("Verifying commits in commit graph"),
2511 for (i
= 0; i
< g
->num_commits
; i
++) {
2512 struct commit
*graph_commit
, *odb_commit
;
2513 struct commit_list
*graph_parents
, *odb_parents
;
2514 timestamp_t max_generation
= 0;
2515 timestamp_t generation
;
2517 display_progress(progress
, i
+ 1);
2518 hashcpy(cur_oid
.hash
, g
->chunk_oid_lookup
+ g
->hash_len
* i
);
2520 graph_commit
= lookup_commit(r
, &cur_oid
);
2521 odb_commit
= (struct commit
*)create_object(r
, &cur_oid
, alloc_commit_node(r
));
2522 if (parse_commit_internal(odb_commit
, 0, 0)) {
2523 graph_report(_("failed to parse commit %s from object database for commit-graph"),
2524 oid_to_hex(&cur_oid
));
2528 if (!oideq(&get_commit_tree_in_graph_one(r
, g
, graph_commit
)->object
.oid
,
2529 get_commit_tree_oid(odb_commit
)))
2530 graph_report(_("root tree OID for commit %s in commit-graph is %s != %s"),
2531 oid_to_hex(&cur_oid
),
2532 oid_to_hex(get_commit_tree_oid(graph_commit
)),
2533 oid_to_hex(get_commit_tree_oid(odb_commit
)));
2535 graph_parents
= graph_commit
->parents
;
2536 odb_parents
= odb_commit
->parents
;
2538 while (graph_parents
) {
2539 if (odb_parents
== NULL
) {
2540 graph_report(_("commit-graph parent list for commit %s is too long"),
2541 oid_to_hex(&cur_oid
));
2545 /* parse parent in case it is in a base graph */
2546 parse_commit_in_graph_one(r
, g
, graph_parents
->item
);
2548 if (!oideq(&graph_parents
->item
->object
.oid
, &odb_parents
->item
->object
.oid
))
2549 graph_report(_("commit-graph parent for %s is %s != %s"),
2550 oid_to_hex(&cur_oid
),
2551 oid_to_hex(&graph_parents
->item
->object
.oid
),
2552 oid_to_hex(&odb_parents
->item
->object
.oid
));
2554 generation
= commit_graph_generation(graph_parents
->item
);
2555 if (generation
> max_generation
)
2556 max_generation
= generation
;
2558 graph_parents
= graph_parents
->next
;
2559 odb_parents
= odb_parents
->next
;
2562 if (odb_parents
!= NULL
)
2563 graph_report(_("commit-graph parent list for commit %s terminates early"),
2564 oid_to_hex(&cur_oid
));
2566 if (!commit_graph_generation(graph_commit
)) {
2567 if (generation_zero
== GENERATION_NUMBER_EXISTS
)
2568 graph_report(_("commit-graph has generation number zero for commit %s, but non-zero elsewhere"),
2569 oid_to_hex(&cur_oid
));
2570 generation_zero
= GENERATION_ZERO_EXISTS
;
2571 } else if (generation_zero
== GENERATION_ZERO_EXISTS
)
2572 graph_report(_("commit-graph has non-zero generation number for commit %s, but zero elsewhere"),
2573 oid_to_hex(&cur_oid
));
2575 if (generation_zero
== GENERATION_ZERO_EXISTS
)
2579 * If we are using topological level and one of our parents has
2580 * generation GENERATION_NUMBER_V1_MAX, then our generation is
2581 * also GENERATION_NUMBER_V1_MAX. Decrement to avoid extra logic
2582 * in the following condition.
2584 if (!g
->read_generation_data
&& max_generation
== GENERATION_NUMBER_V1_MAX
)
2587 generation
= commit_graph_generation(graph_commit
);
2588 if (generation
< max_generation
+ 1)
2589 graph_report(_("commit-graph generation for commit %s is %"PRItime
" < %"PRItime
),
2590 oid_to_hex(&cur_oid
),
2592 max_generation
+ 1);
2594 if (graph_commit
->date
!= odb_commit
->date
)
2595 graph_report(_("commit date for commit %s in commit-graph is %"PRItime
" != %"PRItime
),
2596 oid_to_hex(&cur_oid
),
2600 stop_progress(&progress
);
2602 local_error
= verify_commit_graph_error
;
2604 if (!(flags
& COMMIT_GRAPH_VERIFY_SHALLOW
) && g
->base_graph
)
2605 local_error
|= verify_commit_graph(r
, g
->base_graph
, flags
);
2610 void free_commit_graph(struct commit_graph
*g
)
2615 munmap((void *)g
->data
, g
->data_len
);
2619 free(g
->bloom_filter_settings
);
2623 void disable_commit_graph(struct repository
*r
)
2625 r
->commit_graph_disabled
= 1;