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 #define GRAPH_SIGNATURE 0x43475048 /* "CGPH" */
21 #define GRAPH_CHUNKID_OIDFANOUT 0x4f494446 /* "OIDF" */
22 #define GRAPH_CHUNKID_OIDLOOKUP 0x4f49444c /* "OIDL" */
23 #define GRAPH_CHUNKID_DATA 0x43444154 /* "CDAT" */
24 #define GRAPH_CHUNKID_EXTRAEDGES 0x45444745 /* "EDGE" */
25 #define GRAPH_CHUNKID_BASE 0x42415345 /* "BASE" */
27 #define GRAPH_DATA_WIDTH (the_hash_algo->rawsz + 16)
29 #define GRAPH_VERSION_1 0x1
30 #define GRAPH_VERSION GRAPH_VERSION_1
32 #define GRAPH_EXTRA_EDGES_NEEDED 0x80000000
33 #define GRAPH_EDGE_LAST_MASK 0x7fffffff
34 #define GRAPH_PARENT_NONE 0x70000000
36 #define GRAPH_LAST_EDGE 0x80000000
38 #define GRAPH_HEADER_SIZE 8
39 #define GRAPH_FANOUT_SIZE (4 * 256)
40 #define GRAPH_CHUNKLOOKUP_WIDTH 12
41 #define GRAPH_MIN_SIZE (GRAPH_HEADER_SIZE + 4 * GRAPH_CHUNKLOOKUP_WIDTH \
42 + GRAPH_FANOUT_SIZE + the_hash_algo->rawsz)
44 char *get_commit_graph_filename(const char *obj_dir
)
46 return xstrfmt("%s/info/commit-graph", obj_dir
);
49 static char *get_split_graph_filename(const char *obj_dir
,
52 return xstrfmt("%s/info/commit-graphs/graph-%s.graph",
57 static char *get_chain_filename(const char *obj_dir
)
59 return xstrfmt("%s/info/commit-graphs/commit-graph-chain", obj_dir
);
62 static uint8_t oid_version(void)
67 static struct commit_graph
*alloc_commit_graph(void)
69 struct commit_graph
*g
= xcalloc(1, sizeof(*g
));
75 extern int read_replace_refs
;
77 static int commit_graph_compatible(struct repository
*r
)
82 if (read_replace_refs
) {
83 prepare_replace_object(r
);
84 if (hashmap_get_size(&r
->objects
->replace_map
->map
))
88 prepare_commit_graft(r
);
89 if (r
->parsed_objects
&& r
->parsed_objects
->grafts_nr
)
91 if (is_repository_shallow(r
))
97 int open_commit_graph(const char *graph_file
, int *fd
, struct stat
*st
)
99 *fd
= git_open(graph_file
);
102 if (fstat(*fd
, st
)) {
109 struct commit_graph
*load_commit_graph_one_fd_st(int fd
, struct stat
*st
)
113 struct commit_graph
*ret
;
115 graph_size
= xsize_t(st
->st_size
);
117 if (graph_size
< GRAPH_MIN_SIZE
) {
119 error(_("commit-graph file is too small"));
122 graph_map
= xmmap(NULL
, graph_size
, PROT_READ
, MAP_PRIVATE
, fd
, 0);
123 ret
= parse_commit_graph(graph_map
, fd
, graph_size
);
126 munmap(graph_map
, graph_size
);
133 static int verify_commit_graph_lite(struct commit_graph
*g
)
136 * Basic validation shared between parse_commit_graph()
137 * which'll be called every time the graph is used, and the
138 * much more expensive verify_commit_graph() used by
139 * "commit-graph verify".
141 * There should only be very basic checks here to ensure that
142 * we don't e.g. segfault in fill_commit_in_graph(), but
143 * because this is a very hot codepath nothing that e.g. loops
144 * over g->num_commits, or runs a checksum on the commit-graph
147 if (!g
->chunk_oid_fanout
) {
148 error("commit-graph is missing the OID Fanout chunk");
151 if (!g
->chunk_oid_lookup
) {
152 error("commit-graph is missing the OID Lookup chunk");
155 if (!g
->chunk_commit_data
) {
156 error("commit-graph is missing the Commit Data chunk");
163 struct commit_graph
*parse_commit_graph(void *graph_map
, int fd
,
166 const unsigned char *data
, *chunk_lookup
;
168 struct commit_graph
*graph
;
169 uint64_t last_chunk_offset
;
170 uint32_t last_chunk_id
;
171 uint32_t graph_signature
;
172 unsigned char graph_version
, hash_version
;
177 if (graph_size
< GRAPH_MIN_SIZE
)
180 data
= (const unsigned char *)graph_map
;
182 graph_signature
= get_be32(data
);
183 if (graph_signature
!= GRAPH_SIGNATURE
) {
184 error(_("commit-graph signature %X does not match signature %X"),
185 graph_signature
, GRAPH_SIGNATURE
);
189 graph_version
= *(unsigned char*)(data
+ 4);
190 if (graph_version
!= GRAPH_VERSION
) {
191 error(_("commit-graph version %X does not match version %X"),
192 graph_version
, GRAPH_VERSION
);
196 hash_version
= *(unsigned char*)(data
+ 5);
197 if (hash_version
!= oid_version()) {
198 error(_("commit-graph hash version %X does not match version %X"),
199 hash_version
, oid_version());
203 graph
= alloc_commit_graph();
205 graph
->hash_len
= the_hash_algo
->rawsz
;
206 graph
->num_chunks
= *(unsigned char*)(data
+ 6);
207 graph
->graph_fd
= fd
;
208 graph
->data
= graph_map
;
209 graph
->data_len
= graph_size
;
212 last_chunk_offset
= 8;
213 chunk_lookup
= data
+ 8;
214 for (i
= 0; i
< graph
->num_chunks
; i
++) {
216 uint64_t chunk_offset
;
217 int chunk_repeated
= 0;
219 if (data
+ graph_size
- chunk_lookup
<
220 GRAPH_CHUNKLOOKUP_WIDTH
) {
221 error(_("commit-graph chunk lookup table entry missing; file may be incomplete"));
226 chunk_id
= get_be32(chunk_lookup
+ 0);
227 chunk_offset
= get_be64(chunk_lookup
+ 4);
229 chunk_lookup
+= GRAPH_CHUNKLOOKUP_WIDTH
;
231 if (chunk_offset
> graph_size
- the_hash_algo
->rawsz
) {
232 error(_("commit-graph improper chunk offset %08x%08x"), (uint32_t)(chunk_offset
>> 32),
233 (uint32_t)chunk_offset
);
239 case GRAPH_CHUNKID_OIDFANOUT
:
240 if (graph
->chunk_oid_fanout
)
243 graph
->chunk_oid_fanout
= (uint32_t*)(data
+ chunk_offset
);
246 case GRAPH_CHUNKID_OIDLOOKUP
:
247 if (graph
->chunk_oid_lookup
)
250 graph
->chunk_oid_lookup
= data
+ chunk_offset
;
253 case GRAPH_CHUNKID_DATA
:
254 if (graph
->chunk_commit_data
)
257 graph
->chunk_commit_data
= data
+ chunk_offset
;
260 case GRAPH_CHUNKID_EXTRAEDGES
:
261 if (graph
->chunk_extra_edges
)
264 graph
->chunk_extra_edges
= data
+ chunk_offset
;
267 case GRAPH_CHUNKID_BASE
:
268 if (graph
->chunk_base_graphs
)
271 graph
->chunk_base_graphs
= data
+ chunk_offset
;
274 if (chunk_repeated
) {
275 error(_("commit-graph chunk id %08x appears multiple times"), chunk_id
);
280 if (last_chunk_id
== GRAPH_CHUNKID_OIDLOOKUP
)
282 graph
->num_commits
= (chunk_offset
- last_chunk_offset
)
286 last_chunk_id
= chunk_id
;
287 last_chunk_offset
= chunk_offset
;
290 hashcpy(graph
->oid
.hash
, graph
->data
+ graph
->data_len
- graph
->hash_len
);
292 if (verify_commit_graph_lite(graph
))
298 static struct commit_graph
*load_commit_graph_one(const char *graph_file
)
303 struct commit_graph
*g
;
304 int open_ok
= open_commit_graph(graph_file
, &fd
, &st
);
309 g
= load_commit_graph_one_fd_st(fd
, &st
);
312 g
->filename
= xstrdup(graph_file
);
317 static struct commit_graph
*load_commit_graph_v1(struct repository
*r
, const char *obj_dir
)
319 char *graph_name
= get_commit_graph_filename(obj_dir
);
320 struct commit_graph
*g
= load_commit_graph_one(graph_name
);
326 static int add_graph_to_chain(struct commit_graph
*g
,
327 struct commit_graph
*chain
,
328 struct object_id
*oids
,
331 struct commit_graph
*cur_g
= chain
;
333 if (n
&& !g
->chunk_base_graphs
) {
334 warning(_("commit-graph has no base graphs chunk"));
342 !oideq(&oids
[n
], &cur_g
->oid
) ||
343 !hasheq(oids
[n
].hash
, g
->chunk_base_graphs
+ g
->hash_len
* n
)) {
344 warning(_("commit-graph chain does not match"));
348 cur_g
= cur_g
->base_graph
;
351 g
->base_graph
= chain
;
354 g
->num_commits_in_base
= chain
->num_commits
+ chain
->num_commits_in_base
;
359 static struct commit_graph
*load_commit_graph_chain(struct repository
*r
, const char *obj_dir
)
361 struct commit_graph
*graph_chain
= NULL
;
362 struct strbuf line
= STRBUF_INIT
;
364 struct object_id
*oids
;
365 int i
= 0, valid
= 1, count
;
366 char *chain_name
= get_chain_filename(obj_dir
);
370 fp
= fopen(chain_name
, "r");
371 stat_res
= stat(chain_name
, &st
);
376 st
.st_size
<= the_hash_algo
->hexsz
)
379 count
= st
.st_size
/ (the_hash_algo
->hexsz
+ 1);
380 oids
= xcalloc(count
, sizeof(struct object_id
));
382 for (i
= 0; i
< count
&& valid
; i
++) {
384 struct commit_graph
*g
;
386 if (strbuf_getline_lf(&line
, fp
) == EOF
)
389 if (get_oid_hex(line
.buf
, &oids
[i
])) {
390 warning(_("invalid commit-graph chain: line '%s' not a hash"),
396 graph_name
= get_split_graph_filename(obj_dir
, line
.buf
);
397 g
= load_commit_graph_one(graph_name
);
400 if (g
&& add_graph_to_chain(g
, graph_chain
, oids
, i
))
412 static struct commit_graph
*read_commit_graph_one(struct repository
*r
, const char *obj_dir
)
414 struct commit_graph
*g
= load_commit_graph_v1(r
, obj_dir
);
417 g
= load_commit_graph_chain(r
, obj_dir
);
422 static void prepare_commit_graph_one(struct repository
*r
, const char *obj_dir
)
425 if (r
->objects
->commit_graph
)
428 r
->objects
->commit_graph
= read_commit_graph_one(r
, obj_dir
);
432 * Return 1 if commit_graph is non-NULL, and 0 otherwise.
434 * On the first invocation, this function attemps to load the commit
435 * graph if the_repository is configured to have one.
437 static int prepare_commit_graph(struct repository
*r
)
439 struct object_directory
*odb
;
442 if (git_env_bool(GIT_TEST_COMMIT_GRAPH_DIE_ON_LOAD
, 0))
443 die("dying as requested by the '%s' variable on commit-graph load!",
444 GIT_TEST_COMMIT_GRAPH_DIE_ON_LOAD
);
446 if (r
->objects
->commit_graph_attempted
)
447 return !!r
->objects
->commit_graph
;
448 r
->objects
->commit_graph_attempted
= 1;
450 if (!git_env_bool(GIT_TEST_COMMIT_GRAPH
, 0) &&
451 (repo_config_get_bool(r
, "core.commitgraph", &config_value
) ||
454 * This repository is not configured to use commit graphs, so
455 * do not load one. (But report commit_graph_attempted anyway
456 * so that commit graph loading is not attempted again for this
461 if (!commit_graph_compatible(r
))
465 for (odb
= r
->objects
->odb
;
466 !r
->objects
->commit_graph
&& odb
;
468 prepare_commit_graph_one(r
, odb
->path
);
469 return !!r
->objects
->commit_graph
;
472 int generation_numbers_enabled(struct repository
*r
)
474 uint32_t first_generation
;
475 struct commit_graph
*g
;
476 if (!prepare_commit_graph(r
))
479 g
= r
->objects
->commit_graph
;
484 first_generation
= get_be32(g
->chunk_commit_data
+
485 g
->hash_len
+ 8) >> 2;
487 return !!first_generation
;
490 static void close_commit_graph_one(struct commit_graph
*g
)
495 close_commit_graph_one(g
->base_graph
);
496 free_commit_graph(g
);
499 void close_commit_graph(struct raw_object_store
*o
)
501 close_commit_graph_one(o
->commit_graph
);
502 o
->commit_graph
= NULL
;
505 static int bsearch_graph(struct commit_graph
*g
, struct object_id
*oid
, uint32_t *pos
)
507 return bsearch_hash(oid
->hash
, g
->chunk_oid_fanout
,
508 g
->chunk_oid_lookup
, g
->hash_len
, pos
);
511 static void load_oid_from_graph(struct commit_graph
*g
,
513 struct object_id
*oid
)
517 while (g
&& pos
< g
->num_commits_in_base
)
521 BUG("NULL commit-graph");
523 if (pos
>= g
->num_commits
+ g
->num_commits_in_base
)
524 die(_("invalid commit position. commit-graph is likely corrupt"));
526 lex_index
= pos
- g
->num_commits_in_base
;
528 hashcpy(oid
->hash
, g
->chunk_oid_lookup
+ g
->hash_len
* lex_index
);
531 static struct commit_list
**insert_parent_or_die(struct repository
*r
,
532 struct commit_graph
*g
,
534 struct commit_list
**pptr
)
537 struct object_id oid
;
539 if (pos
>= g
->num_commits
+ g
->num_commits_in_base
)
540 die("invalid parent position %"PRIu32
, pos
);
542 load_oid_from_graph(g
, pos
, &oid
);
543 c
= lookup_commit(r
, &oid
);
545 die(_("could not find commit %s"), oid_to_hex(&oid
));
547 return &commit_list_insert(c
, pptr
)->next
;
550 static void fill_commit_graph_info(struct commit
*item
, struct commit_graph
*g
, uint32_t pos
)
552 const unsigned char *commit_data
;
555 while (pos
< g
->num_commits_in_base
)
558 lex_index
= pos
- g
->num_commits_in_base
;
559 commit_data
= g
->chunk_commit_data
+ GRAPH_DATA_WIDTH
* lex_index
;
560 item
->graph_pos
= pos
;
561 item
->generation
= get_be32(commit_data
+ g
->hash_len
+ 8) >> 2;
564 static int fill_commit_in_graph(struct repository
*r
,
566 struct commit_graph
*g
, uint32_t pos
)
569 uint32_t *parent_data_ptr
;
570 uint64_t date_low
, date_high
;
571 struct commit_list
**pptr
;
572 const unsigned char *commit_data
;
575 while (pos
< g
->num_commits_in_base
)
578 if (pos
>= g
->num_commits
+ g
->num_commits_in_base
)
579 die(_("invalid commit position. commit-graph is likely corrupt"));
582 * Store the "full" position, but then use the
583 * "local" position for the rest of the calculation.
585 item
->graph_pos
= pos
;
586 lex_index
= pos
- g
->num_commits_in_base
;
588 commit_data
= g
->chunk_commit_data
+ (g
->hash_len
+ 16) * lex_index
;
590 item
->object
.parsed
= 1;
592 item
->maybe_tree
= NULL
;
594 date_high
= get_be32(commit_data
+ g
->hash_len
+ 8) & 0x3;
595 date_low
= get_be32(commit_data
+ g
->hash_len
+ 12);
596 item
->date
= (timestamp_t
)((date_high
<< 32) | date_low
);
598 item
->generation
= get_be32(commit_data
+ g
->hash_len
+ 8) >> 2;
600 pptr
= &item
->parents
;
602 edge_value
= get_be32(commit_data
+ g
->hash_len
);
603 if (edge_value
== GRAPH_PARENT_NONE
)
605 pptr
= insert_parent_or_die(r
, g
, edge_value
, pptr
);
607 edge_value
= get_be32(commit_data
+ g
->hash_len
+ 4);
608 if (edge_value
== GRAPH_PARENT_NONE
)
610 if (!(edge_value
& GRAPH_EXTRA_EDGES_NEEDED
)) {
611 pptr
= insert_parent_or_die(r
, g
, edge_value
, pptr
);
615 parent_data_ptr
= (uint32_t*)(g
->chunk_extra_edges
+
616 4 * (uint64_t)(edge_value
& GRAPH_EDGE_LAST_MASK
));
618 edge_value
= get_be32(parent_data_ptr
);
619 pptr
= insert_parent_or_die(r
, g
,
620 edge_value
& GRAPH_EDGE_LAST_MASK
,
623 } while (!(edge_value
& GRAPH_LAST_EDGE
));
628 static int find_commit_in_graph(struct commit
*item
, struct commit_graph
*g
, uint32_t *pos
)
630 if (item
->graph_pos
!= COMMIT_NOT_FROM_GRAPH
) {
631 *pos
= item
->graph_pos
;
634 struct commit_graph
*cur_g
= g
;
637 while (cur_g
&& !bsearch_graph(cur_g
, &(item
->object
.oid
), &lex_index
))
638 cur_g
= cur_g
->base_graph
;
641 *pos
= lex_index
+ cur_g
->num_commits_in_base
;
649 static int parse_commit_in_graph_one(struct repository
*r
,
650 struct commit_graph
*g
,
655 if (item
->object
.parsed
)
658 if (find_commit_in_graph(item
, g
, &pos
))
659 return fill_commit_in_graph(r
, item
, g
, pos
);
664 int parse_commit_in_graph(struct repository
*r
, struct commit
*item
)
666 if (!prepare_commit_graph(r
))
668 return parse_commit_in_graph_one(r
, r
->objects
->commit_graph
, item
);
671 void load_commit_graph_info(struct repository
*r
, struct commit
*item
)
674 if (!prepare_commit_graph(r
))
676 if (find_commit_in_graph(item
, r
->objects
->commit_graph
, &pos
))
677 fill_commit_graph_info(item
, r
->objects
->commit_graph
, pos
);
680 static struct tree
*load_tree_for_commit(struct repository
*r
,
681 struct commit_graph
*g
,
684 struct object_id oid
;
685 const unsigned char *commit_data
;
687 while (c
->graph_pos
< g
->num_commits_in_base
)
690 commit_data
= g
->chunk_commit_data
+
691 GRAPH_DATA_WIDTH
* (c
->graph_pos
- g
->num_commits_in_base
);
693 hashcpy(oid
.hash
, commit_data
);
694 c
->maybe_tree
= lookup_tree(r
, &oid
);
696 return c
->maybe_tree
;
699 static struct tree
*get_commit_tree_in_graph_one(struct repository
*r
,
700 struct commit_graph
*g
,
701 const struct commit
*c
)
704 return c
->maybe_tree
;
705 if (c
->graph_pos
== COMMIT_NOT_FROM_GRAPH
)
706 BUG("get_commit_tree_in_graph_one called from non-commit-graph commit");
708 return load_tree_for_commit(r
, g
, (struct commit
*)c
);
711 struct tree
*get_commit_tree_in_graph(struct repository
*r
, const struct commit
*c
)
713 return get_commit_tree_in_graph_one(r
, r
->objects
->commit_graph
, c
);
716 struct packed_commit_list
{
717 struct commit
**list
;
722 struct packed_oid_list
{
723 struct object_id
*list
;
728 struct write_commit_graph_context
{
729 struct repository
*r
;
732 struct packed_oid_list oids
;
733 struct packed_commit_list commits
;
735 unsigned long approx_nr_objects
;
736 struct progress
*progress
;
738 uint64_t progress_cnt
;
740 char *base_graph_name
;
741 int num_commit_graphs_before
;
742 int num_commit_graphs_after
;
743 char **commit_graph_filenames_before
;
744 char **commit_graph_filenames_after
;
745 char **commit_graph_hash_after
;
746 uint32_t new_num_commits_in_base
;
747 struct commit_graph
*new_base_graph
;
754 static void write_graph_chunk_fanout(struct hashfile
*f
,
755 struct write_commit_graph_context
*ctx
)
758 struct commit
**list
= ctx
->commits
.list
;
761 * Write the first-level table (the list is sorted,
762 * but we use a 256-entry lookup to be able to avoid
763 * having to do eight extra binary search iterations).
765 for (i
= 0; i
< 256; i
++) {
766 while (count
< ctx
->commits
.nr
) {
767 if ((*list
)->object
.oid
.hash
[0] != i
)
769 display_progress(ctx
->progress
, ++ctx
->progress_cnt
);
774 hashwrite_be32(f
, count
);
778 static void write_graph_chunk_oids(struct hashfile
*f
, int hash_len
,
779 struct write_commit_graph_context
*ctx
)
781 struct commit
**list
= ctx
->commits
.list
;
783 for (count
= 0; count
< ctx
->commits
.nr
; count
++, list
++) {
784 display_progress(ctx
->progress
, ++ctx
->progress_cnt
);
785 hashwrite(f
, (*list
)->object
.oid
.hash
, (int)hash_len
);
789 static const unsigned char *commit_to_sha1(size_t index
, void *table
)
791 struct commit
**commits
= table
;
792 return commits
[index
]->object
.oid
.hash
;
795 static void write_graph_chunk_data(struct hashfile
*f
, int hash_len
,
796 struct write_commit_graph_context
*ctx
)
798 struct commit
**list
= ctx
->commits
.list
;
799 struct commit
**last
= ctx
->commits
.list
+ ctx
->commits
.nr
;
800 uint32_t num_extra_edges
= 0;
802 while (list
< last
) {
803 struct commit_list
*parent
;
805 uint32_t packedDate
[2];
806 display_progress(ctx
->progress
, ++ctx
->progress_cnt
);
808 parse_commit_no_graph(*list
);
809 hashwrite(f
, get_commit_tree_oid(*list
)->hash
, hash_len
);
811 parent
= (*list
)->parents
;
814 edge_value
= GRAPH_PARENT_NONE
;
816 edge_value
= sha1_pos(parent
->item
->object
.oid
.hash
,
822 edge_value
+= ctx
->new_num_commits_in_base
;
825 if (find_commit_in_graph(parent
->item
,
832 BUG("missing parent %s for commit %s",
833 oid_to_hex(&parent
->item
->object
.oid
),
834 oid_to_hex(&(*list
)->object
.oid
));
837 hashwrite_be32(f
, edge_value
);
840 parent
= parent
->next
;
843 edge_value
= GRAPH_PARENT_NONE
;
844 else if (parent
->next
)
845 edge_value
= GRAPH_EXTRA_EDGES_NEEDED
| num_extra_edges
;
847 edge_value
= sha1_pos(parent
->item
->object
.oid
.hash
,
853 edge_value
+= ctx
->new_num_commits_in_base
;
856 if (find_commit_in_graph(parent
->item
,
863 BUG("missing parent %s for commit %s",
864 oid_to_hex(&parent
->item
->object
.oid
),
865 oid_to_hex(&(*list
)->object
.oid
));
868 hashwrite_be32(f
, edge_value
);
870 if (edge_value
& GRAPH_EXTRA_EDGES_NEEDED
) {
873 parent
= parent
->next
;
877 if (sizeof((*list
)->date
) > 4)
878 packedDate
[0] = htonl(((*list
)->date
>> 32) & 0x3);
882 packedDate
[0] |= htonl((*list
)->generation
<< 2);
884 packedDate
[1] = htonl((*list
)->date
);
885 hashwrite(f
, packedDate
, 8);
891 static void write_graph_chunk_extra_edges(struct hashfile
*f
,
892 struct write_commit_graph_context
*ctx
)
894 struct commit
**list
= ctx
->commits
.list
;
895 struct commit
**last
= ctx
->commits
.list
+ ctx
->commits
.nr
;
896 struct commit_list
*parent
;
898 while (list
< last
) {
901 display_progress(ctx
->progress
, ++ctx
->progress_cnt
);
903 for (parent
= (*list
)->parents
; num_parents
< 3 && parent
;
904 parent
= parent
->next
)
907 if (num_parents
<= 2) {
912 /* Since num_parents > 2, this initializer is safe. */
913 for (parent
= (*list
)->parents
->next
; parent
; parent
= parent
->next
) {
914 int edge_value
= sha1_pos(parent
->item
->object
.oid
.hash
,
920 edge_value
+= ctx
->new_num_commits_in_base
;
923 if (find_commit_in_graph(parent
->item
,
930 BUG("missing parent %s for commit %s",
931 oid_to_hex(&parent
->item
->object
.oid
),
932 oid_to_hex(&(*list
)->object
.oid
));
933 else if (!parent
->next
)
934 edge_value
|= GRAPH_LAST_EDGE
;
936 hashwrite_be32(f
, edge_value
);
943 static int oid_compare(const void *_a
, const void *_b
)
945 const struct object_id
*a
= (const struct object_id
*)_a
;
946 const struct object_id
*b
= (const struct object_id
*)_b
;
950 static int add_packed_commits(const struct object_id
*oid
,
951 struct packed_git
*pack
,
955 struct write_commit_graph_context
*ctx
= (struct write_commit_graph_context
*)data
;
956 enum object_type type
;
957 off_t offset
= nth_packed_object_offset(pack
, pos
);
958 struct object_info oi
= OBJECT_INFO_INIT
;
961 display_progress(ctx
->progress
, ++ctx
->progress_done
);
964 if (packed_object_info(ctx
->r
, pack
, offset
, &oi
) < 0)
965 die(_("unable to get type of object %s"), oid_to_hex(oid
));
967 if (type
!= OBJ_COMMIT
)
970 ALLOC_GROW(ctx
->oids
.list
, ctx
->oids
.nr
+ 1, ctx
->oids
.alloc
);
971 oidcpy(&(ctx
->oids
.list
[ctx
->oids
.nr
]), oid
);
977 static void add_missing_parents(struct write_commit_graph_context
*ctx
, struct commit
*commit
)
979 struct commit_list
*parent
;
980 for (parent
= commit
->parents
; parent
; parent
= parent
->next
) {
981 if (!(parent
->item
->object
.flags
& UNINTERESTING
)) {
982 ALLOC_GROW(ctx
->oids
.list
, ctx
->oids
.nr
+ 1, ctx
->oids
.alloc
);
983 oidcpy(&ctx
->oids
.list
[ctx
->oids
.nr
], &(parent
->item
->object
.oid
));
985 parent
->item
->object
.flags
|= UNINTERESTING
;
990 static void close_reachable(struct write_commit_graph_context
*ctx
)
993 struct commit
*commit
;
995 if (ctx
->report_progress
)
996 ctx
->progress
= start_delayed_progress(
997 _("Loading known commits in commit graph"),
999 for (i
= 0; i
< ctx
->oids
.nr
; i
++) {
1000 display_progress(ctx
->progress
, i
+ 1);
1001 commit
= lookup_commit(ctx
->r
, &ctx
->oids
.list
[i
]);
1003 commit
->object
.flags
|= UNINTERESTING
;
1005 stop_progress(&ctx
->progress
);
1008 * As this loop runs, ctx->oids.nr may grow, but not more
1009 * than the number of missing commits in the reachable
1012 if (ctx
->report_progress
)
1013 ctx
->progress
= start_delayed_progress(
1014 _("Expanding reachable commits in commit graph"),
1016 for (i
= 0; i
< ctx
->oids
.nr
; i
++) {
1017 display_progress(ctx
->progress
, i
+ 1);
1018 commit
= lookup_commit(ctx
->r
, &ctx
->oids
.list
[i
]);
1023 if (!parse_commit(commit
) &&
1024 commit
->graph_pos
== COMMIT_NOT_FROM_GRAPH
)
1025 add_missing_parents(ctx
, commit
);
1026 } else if (!parse_commit_no_graph(commit
))
1027 add_missing_parents(ctx
, commit
);
1029 stop_progress(&ctx
->progress
);
1031 if (ctx
->report_progress
)
1032 ctx
->progress
= start_delayed_progress(
1033 _("Clearing commit marks in commit graph"),
1035 for (i
= 0; i
< ctx
->oids
.nr
; i
++) {
1036 display_progress(ctx
->progress
, i
+ 1);
1037 commit
= lookup_commit(ctx
->r
, &ctx
->oids
.list
[i
]);
1040 commit
->object
.flags
&= ~UNINTERESTING
;
1042 stop_progress(&ctx
->progress
);
1045 static void compute_generation_numbers(struct write_commit_graph_context
*ctx
)
1048 struct commit_list
*list
= NULL
;
1050 if (ctx
->report_progress
)
1051 ctx
->progress
= start_progress(
1052 _("Computing commit graph generation numbers"),
1054 for (i
= 0; i
< ctx
->commits
.nr
; i
++) {
1055 display_progress(ctx
->progress
, i
+ 1);
1056 if (ctx
->commits
.list
[i
]->generation
!= GENERATION_NUMBER_INFINITY
&&
1057 ctx
->commits
.list
[i
]->generation
!= GENERATION_NUMBER_ZERO
)
1060 commit_list_insert(ctx
->commits
.list
[i
], &list
);
1062 struct commit
*current
= list
->item
;
1063 struct commit_list
*parent
;
1064 int all_parents_computed
= 1;
1065 uint32_t max_generation
= 0;
1067 for (parent
= current
->parents
; parent
; parent
= parent
->next
) {
1068 if (parent
->item
->generation
== GENERATION_NUMBER_INFINITY
||
1069 parent
->item
->generation
== GENERATION_NUMBER_ZERO
) {
1070 all_parents_computed
= 0;
1071 commit_list_insert(parent
->item
, &list
);
1073 } else if (parent
->item
->generation
> max_generation
) {
1074 max_generation
= parent
->item
->generation
;
1078 if (all_parents_computed
) {
1079 current
->generation
= max_generation
+ 1;
1082 if (current
->generation
> GENERATION_NUMBER_MAX
)
1083 current
->generation
= GENERATION_NUMBER_MAX
;
1087 stop_progress(&ctx
->progress
);
1090 static int add_ref_to_list(const char *refname
,
1091 const struct object_id
*oid
,
1092 int flags
, void *cb_data
)
1094 struct string_list
*list
= (struct string_list
*)cb_data
;
1096 string_list_append(list
, oid_to_hex(oid
));
1100 int write_commit_graph_reachable(const char *obj_dir
, unsigned int flags
)
1102 struct string_list list
= STRING_LIST_INIT_DUP
;
1105 for_each_ref(add_ref_to_list
, &list
);
1106 result
= write_commit_graph(obj_dir
, NULL
, &list
,
1109 string_list_clear(&list
, 0);
1113 static int fill_oids_from_packs(struct write_commit_graph_context
*ctx
,
1114 struct string_list
*pack_indexes
)
1117 struct strbuf progress_title
= STRBUF_INIT
;
1118 struct strbuf packname
= STRBUF_INIT
;
1121 strbuf_addf(&packname
, "%s/pack/", ctx
->obj_dir
);
1122 dirlen
= packname
.len
;
1123 if (ctx
->report_progress
) {
1124 strbuf_addf(&progress_title
,
1125 Q_("Finding commits for commit graph in %d pack",
1126 "Finding commits for commit graph in %d packs",
1129 ctx
->progress
= start_delayed_progress(progress_title
.buf
, 0);
1130 ctx
->progress_done
= 0;
1132 for (i
= 0; i
< pack_indexes
->nr
; i
++) {
1133 struct packed_git
*p
;
1134 strbuf_setlen(&packname
, dirlen
);
1135 strbuf_addstr(&packname
, pack_indexes
->items
[i
].string
);
1136 p
= add_packed_git(packname
.buf
, packname
.len
, 1);
1138 error(_("error adding pack %s"), packname
.buf
);
1141 if (open_pack_index(p
)) {
1142 error(_("error opening index for %s"), packname
.buf
);
1145 for_each_object_in_pack(p
, add_packed_commits
, ctx
,
1146 FOR_EACH_OBJECT_PACK_ORDER
);
1151 stop_progress(&ctx
->progress
);
1152 strbuf_reset(&progress_title
);
1153 strbuf_release(&packname
);
1158 static void fill_oids_from_commit_hex(struct write_commit_graph_context
*ctx
,
1159 struct string_list
*commit_hex
)
1162 struct strbuf progress_title
= STRBUF_INIT
;
1164 if (ctx
->report_progress
) {
1165 strbuf_addf(&progress_title
,
1166 Q_("Finding commits for commit graph from %d ref",
1167 "Finding commits for commit graph from %d refs",
1170 ctx
->progress
= start_delayed_progress(
1174 for (i
= 0; i
< commit_hex
->nr
; i
++) {
1176 struct object_id oid
;
1177 struct commit
*result
;
1179 display_progress(ctx
->progress
, i
+ 1);
1180 if (commit_hex
->items
[i
].string
&&
1181 parse_oid_hex(commit_hex
->items
[i
].string
, &oid
, &end
))
1184 result
= lookup_commit_reference_gently(ctx
->r
, &oid
, 1);
1187 ALLOC_GROW(ctx
->oids
.list
, ctx
->oids
.nr
+ 1, ctx
->oids
.alloc
);
1188 oidcpy(&ctx
->oids
.list
[ctx
->oids
.nr
], &(result
->object
.oid
));
1192 stop_progress(&ctx
->progress
);
1193 strbuf_release(&progress_title
);
1196 static void fill_oids_from_all_packs(struct write_commit_graph_context
*ctx
)
1198 if (ctx
->report_progress
)
1199 ctx
->progress
= start_delayed_progress(
1200 _("Finding commits for commit graph among packed objects"),
1201 ctx
->approx_nr_objects
);
1202 for_each_packed_object(add_packed_commits
, ctx
,
1203 FOR_EACH_OBJECT_PACK_ORDER
);
1204 if (ctx
->progress_done
< ctx
->approx_nr_objects
)
1205 display_progress(ctx
->progress
, ctx
->approx_nr_objects
);
1206 stop_progress(&ctx
->progress
);
1209 static uint32_t count_distinct_commits(struct write_commit_graph_context
*ctx
)
1211 uint32_t i
, count_distinct
= 1;
1213 if (ctx
->report_progress
)
1214 ctx
->progress
= start_delayed_progress(
1215 _("Counting distinct commits in commit graph"),
1217 display_progress(ctx
->progress
, 0); /* TODO: Measure QSORT() progress */
1218 QSORT(ctx
->oids
.list
, ctx
->oids
.nr
, oid_compare
);
1220 for (i
= 1; i
< ctx
->oids
.nr
; i
++) {
1221 display_progress(ctx
->progress
, i
+ 1);
1222 if (!oideq(&ctx
->oids
.list
[i
- 1], &ctx
->oids
.list
[i
])) {
1224 struct commit
*c
= lookup_commit(ctx
->r
, &ctx
->oids
.list
[i
]);
1226 if (!c
|| c
->graph_pos
!= COMMIT_NOT_FROM_GRAPH
)
1233 stop_progress(&ctx
->progress
);
1235 return count_distinct
;
1238 static void copy_oids_to_commits(struct write_commit_graph_context
*ctx
)
1241 struct commit_list
*parent
;
1243 ctx
->num_extra_edges
= 0;
1244 if (ctx
->report_progress
)
1245 ctx
->progress
= start_delayed_progress(
1246 _("Finding extra edges in commit graph"),
1248 for (i
= 0; i
< ctx
->oids
.nr
; i
++) {
1249 int num_parents
= 0;
1250 display_progress(ctx
->progress
, i
+ 1);
1251 if (i
> 0 && oideq(&ctx
->oids
.list
[i
- 1], &ctx
->oids
.list
[i
]))
1254 ALLOC_GROW(ctx
->commits
.list
, ctx
->commits
.nr
+ 1, ctx
->commits
.alloc
);
1255 ctx
->commits
.list
[ctx
->commits
.nr
] = lookup_commit(ctx
->r
, &ctx
->oids
.list
[i
]);
1258 ctx
->commits
.list
[ctx
->commits
.nr
]->graph_pos
!= COMMIT_NOT_FROM_GRAPH
)
1261 parse_commit_no_graph(ctx
->commits
.list
[ctx
->commits
.nr
]);
1263 for (parent
= ctx
->commits
.list
[ctx
->commits
.nr
]->parents
;
1264 parent
; parent
= parent
->next
)
1267 if (num_parents
> 2)
1268 ctx
->num_extra_edges
+= num_parents
- 1;
1272 stop_progress(&ctx
->progress
);
1275 static int write_graph_chunk_base_1(struct hashfile
*f
,
1276 struct commit_graph
*g
)
1283 num
= write_graph_chunk_base_1(f
, g
->base_graph
);
1284 hashwrite(f
, g
->oid
.hash
, the_hash_algo
->rawsz
);
1288 static int write_graph_chunk_base(struct hashfile
*f
,
1289 struct write_commit_graph_context
*ctx
)
1291 int num
= write_graph_chunk_base_1(f
, ctx
->new_base_graph
);
1293 if (num
!= ctx
->num_commit_graphs_after
- 1) {
1294 error(_("failed to write correct number of base graph ids"));
1301 static void init_commit_graph_chain(struct write_commit_graph_context
*ctx
)
1303 struct commit_graph
*g
= ctx
->r
->objects
->commit_graph
;
1306 ctx
->new_base_graph
= g
;
1307 ctx
->base_graph_name
= xstrdup(g
->filename
);
1308 ctx
->new_num_commits_in_base
= g
->num_commits
+ g
->num_commits_in_base
;
1310 ctx
->num_commit_graphs_after
= ctx
->num_commit_graphs_before
+ 1;
1312 ALLOC_ARRAY(ctx
->commit_graph_filenames_after
, ctx
->num_commit_graphs_after
);
1313 ALLOC_ARRAY(ctx
->commit_graph_hash_after
, ctx
->num_commit_graphs_after
);
1315 for (i
= 0; i
< ctx
->num_commit_graphs_before
- 1; i
++)
1316 ctx
->commit_graph_filenames_after
[i
] = xstrdup(ctx
->commit_graph_filenames_before
[i
]);
1318 if (ctx
->num_commit_graphs_before
)
1319 ctx
->commit_graph_filenames_after
[ctx
->num_commit_graphs_before
- 1] =
1320 get_split_graph_filename(ctx
->obj_dir
, oid_to_hex(&g
->oid
));
1322 i
= ctx
->num_commit_graphs_before
- 1;
1325 ctx
->commit_graph_hash_after
[i
] = xstrdup(oid_to_hex(&g
->oid
));
1331 static int write_commit_graph_file(struct write_commit_graph_context
*ctx
)
1336 struct lock_file lk
= LOCK_INIT
;
1337 uint32_t chunk_ids
[6];
1338 uint64_t chunk_offsets
[6];
1339 const unsigned hashsz
= the_hash_algo
->rawsz
;
1340 struct strbuf progress_title
= STRBUF_INIT
;
1342 struct object_id file_hash
;
1345 struct strbuf tmp_file
= STRBUF_INIT
;
1347 strbuf_addf(&tmp_file
,
1348 "%s/info/commit-graphs/tmp_graph_XXXXXX",
1350 ctx
->graph_name
= strbuf_detach(&tmp_file
, NULL
);
1352 ctx
->graph_name
= get_commit_graph_filename(ctx
->obj_dir
);
1355 if (safe_create_leading_directories(ctx
->graph_name
)) {
1356 UNLEAK(ctx
->graph_name
);
1357 error(_("unable to create leading directories of %s"),
1363 char *lock_name
= get_chain_filename(ctx
->obj_dir
);
1365 hold_lock_file_for_update(&lk
, lock_name
, LOCK_DIE_ON_ERROR
);
1367 fd
= git_mkstemp_mode(ctx
->graph_name
, 0444);
1369 error(_("unable to create '%s'"), ctx
->graph_name
);
1373 f
= hashfd(fd
, ctx
->graph_name
);
1375 hold_lock_file_for_update(&lk
, ctx
->graph_name
, LOCK_DIE_ON_ERROR
);
1376 fd
= lk
.tempfile
->fd
;
1377 f
= hashfd(lk
.tempfile
->fd
, lk
.tempfile
->filename
.buf
);
1380 chunk_ids
[0] = GRAPH_CHUNKID_OIDFANOUT
;
1381 chunk_ids
[1] = GRAPH_CHUNKID_OIDLOOKUP
;
1382 chunk_ids
[2] = GRAPH_CHUNKID_DATA
;
1383 if (ctx
->num_extra_edges
) {
1384 chunk_ids
[num_chunks
] = GRAPH_CHUNKID_EXTRAEDGES
;
1387 if (ctx
->num_commit_graphs_after
> 1) {
1388 chunk_ids
[num_chunks
] = GRAPH_CHUNKID_BASE
;
1392 chunk_ids
[num_chunks
] = 0;
1394 chunk_offsets
[0] = 8 + (num_chunks
+ 1) * GRAPH_CHUNKLOOKUP_WIDTH
;
1395 chunk_offsets
[1] = chunk_offsets
[0] + GRAPH_FANOUT_SIZE
;
1396 chunk_offsets
[2] = chunk_offsets
[1] + hashsz
* ctx
->commits
.nr
;
1397 chunk_offsets
[3] = chunk_offsets
[2] + (hashsz
+ 16) * ctx
->commits
.nr
;
1400 if (ctx
->num_extra_edges
) {
1401 chunk_offsets
[num_chunks
+ 1] = chunk_offsets
[num_chunks
] +
1402 4 * ctx
->num_extra_edges
;
1405 if (ctx
->num_commit_graphs_after
> 1) {
1406 chunk_offsets
[num_chunks
+ 1] = chunk_offsets
[num_chunks
] +
1407 hashsz
* (ctx
->num_commit_graphs_after
- 1);
1411 hashwrite_be32(f
, GRAPH_SIGNATURE
);
1413 hashwrite_u8(f
, GRAPH_VERSION
);
1414 hashwrite_u8(f
, oid_version());
1415 hashwrite_u8(f
, num_chunks
);
1416 hashwrite_u8(f
, ctx
->num_commit_graphs_after
- 1);
1418 for (i
= 0; i
<= num_chunks
; i
++) {
1419 uint32_t chunk_write
[3];
1421 chunk_write
[0] = htonl(chunk_ids
[i
]);
1422 chunk_write
[1] = htonl(chunk_offsets
[i
] >> 32);
1423 chunk_write
[2] = htonl(chunk_offsets
[i
] & 0xffffffff);
1424 hashwrite(f
, chunk_write
, 12);
1427 if (ctx
->report_progress
) {
1428 strbuf_addf(&progress_title
,
1429 Q_("Writing out commit graph in %d pass",
1430 "Writing out commit graph in %d passes",
1433 ctx
->progress
= start_delayed_progress(
1435 num_chunks
* ctx
->commits
.nr
);
1437 write_graph_chunk_fanout(f
, ctx
);
1438 write_graph_chunk_oids(f
, hashsz
, ctx
);
1439 write_graph_chunk_data(f
, hashsz
, ctx
);
1440 if (ctx
->num_extra_edges
)
1441 write_graph_chunk_extra_edges(f
, ctx
);
1442 if (ctx
->num_commit_graphs_after
> 1 &&
1443 write_graph_chunk_base(f
, ctx
)) {
1446 stop_progress(&ctx
->progress
);
1447 strbuf_release(&progress_title
);
1449 if (ctx
->split
&& ctx
->base_graph_name
&& ctx
->num_commit_graphs_after
> 1) {
1450 char *new_base_hash
= xstrdup(oid_to_hex(&ctx
->new_base_graph
->oid
));
1451 char *new_base_name
= get_split_graph_filename(ctx
->obj_dir
, new_base_hash
);
1453 free(ctx
->commit_graph_filenames_after
[ctx
->num_commit_graphs_after
- 2]);
1454 free(ctx
->commit_graph_hash_after
[ctx
->num_commit_graphs_after
- 2]);
1455 ctx
->commit_graph_filenames_after
[ctx
->num_commit_graphs_after
- 2] = new_base_name
;
1456 ctx
->commit_graph_hash_after
[ctx
->num_commit_graphs_after
- 2] = new_base_hash
;
1459 close_commit_graph(ctx
->r
->objects
);
1460 finalize_hashfile(f
, file_hash
.hash
, CSUM_HASH_IN_STREAM
| CSUM_FSYNC
);
1463 FILE *chainf
= fdopen_lock_file(&lk
, "w");
1464 char *final_graph_name
;
1470 error(_("unable to open commit-graph chain file"));
1474 if (ctx
->base_graph_name
) {
1475 const char *dest
= ctx
->commit_graph_filenames_after
[
1476 ctx
->num_commit_graphs_after
- 2];
1478 if (strcmp(ctx
->base_graph_name
, dest
)) {
1479 result
= rename(ctx
->base_graph_name
, dest
);
1482 error(_("failed to rename base commit-graph file"));
1487 char *graph_name
= get_commit_graph_filename(ctx
->obj_dir
);
1491 ctx
->commit_graph_hash_after
[ctx
->num_commit_graphs_after
- 1] = xstrdup(oid_to_hex(&file_hash
));
1492 final_graph_name
= get_split_graph_filename(ctx
->obj_dir
,
1493 ctx
->commit_graph_hash_after
[ctx
->num_commit_graphs_after
- 1]);
1494 ctx
->commit_graph_filenames_after
[ctx
->num_commit_graphs_after
- 1] = final_graph_name
;
1496 result
= rename(ctx
->graph_name
, final_graph_name
);
1498 for (i
= 0; i
< ctx
->num_commit_graphs_after
; i
++)
1499 fprintf(lk
.tempfile
->fp
, "%s\n", ctx
->commit_graph_hash_after
[i
]);
1502 error(_("failed to rename temporary commit-graph file"));
1507 commit_lock_file(&lk
);
1512 int write_commit_graph(const char *obj_dir
,
1513 struct string_list
*pack_indexes
,
1514 struct string_list
*commit_hex
,
1517 struct write_commit_graph_context
*ctx
;
1518 uint32_t i
, count_distinct
= 0;
1521 if (!commit_graph_compatible(the_repository
))
1524 ctx
= xcalloc(1, sizeof(struct write_commit_graph_context
));
1525 ctx
->r
= the_repository
;
1526 ctx
->obj_dir
= obj_dir
;
1527 ctx
->append
= flags
& COMMIT_GRAPH_APPEND
? 1 : 0;
1528 ctx
->report_progress
= flags
& COMMIT_GRAPH_PROGRESS
? 1 : 0;
1529 ctx
->split
= flags
& COMMIT_GRAPH_SPLIT
? 1 : 0;
1532 struct commit_graph
*g
;
1533 prepare_commit_graph(ctx
->r
);
1535 g
= ctx
->r
->objects
->commit_graph
;
1538 ctx
->num_commit_graphs_before
++;
1542 if (ctx
->num_commit_graphs_before
) {
1543 ALLOC_ARRAY(ctx
->commit_graph_filenames_before
, ctx
->num_commit_graphs_before
);
1544 i
= ctx
->num_commit_graphs_before
;
1545 g
= ctx
->r
->objects
->commit_graph
;
1548 ctx
->commit_graph_filenames_before
[--i
] = xstrdup(g
->filename
);
1554 ctx
->approx_nr_objects
= approximate_object_count();
1555 ctx
->oids
.alloc
= ctx
->approx_nr_objects
/ 32;
1558 prepare_commit_graph_one(ctx
->r
, ctx
->obj_dir
);
1559 if (ctx
->r
->objects
->commit_graph
)
1560 ctx
->oids
.alloc
+= ctx
->r
->objects
->commit_graph
->num_commits
;
1563 if (ctx
->oids
.alloc
< 1024)
1564 ctx
->oids
.alloc
= 1024;
1565 ALLOC_ARRAY(ctx
->oids
.list
, ctx
->oids
.alloc
);
1567 if (ctx
->append
&& ctx
->r
->objects
->commit_graph
) {
1568 struct commit_graph
*g
= ctx
->r
->objects
->commit_graph
;
1569 for (i
= 0; i
< g
->num_commits
; i
++) {
1570 const unsigned char *hash
= g
->chunk_oid_lookup
+ g
->hash_len
* i
;
1571 hashcpy(ctx
->oids
.list
[ctx
->oids
.nr
++].hash
, hash
);
1576 if ((res
= fill_oids_from_packs(ctx
, pack_indexes
)))
1581 fill_oids_from_commit_hex(ctx
, commit_hex
);
1583 if (!pack_indexes
&& !commit_hex
)
1584 fill_oids_from_all_packs(ctx
);
1586 close_reachable(ctx
);
1588 count_distinct
= count_distinct_commits(ctx
);
1590 if (count_distinct
>= GRAPH_EDGE_LAST_MASK
) {
1591 error(_("the commit graph format cannot write %d commits"), count_distinct
);
1596 ctx
->commits
.alloc
= count_distinct
;
1597 ALLOC_ARRAY(ctx
->commits
.list
, ctx
->commits
.alloc
);
1599 copy_oids_to_commits(ctx
);
1601 if (ctx
->commits
.nr
>= GRAPH_EDGE_LAST_MASK
) {
1602 error(_("too many commits to write graph"));
1607 if (!ctx
->commits
.nr
)
1611 init_commit_graph_chain(ctx
);
1613 ctx
->num_commit_graphs_after
= 1;
1615 compute_generation_numbers(ctx
);
1617 res
= write_commit_graph_file(ctx
);
1620 free(ctx
->graph_name
);
1621 free(ctx
->commits
.list
);
1622 free(ctx
->oids
.list
);
1624 if (ctx
->commit_graph_filenames_after
) {
1625 for (i
= 0; i
< ctx
->num_commit_graphs_after
; i
++) {
1626 free(ctx
->commit_graph_filenames_after
[i
]);
1627 free(ctx
->commit_graph_hash_after
[i
]);
1630 for (i
= 0; i
< ctx
->num_commit_graphs_before
; i
++)
1631 free(ctx
->commit_graph_filenames_before
[i
]);
1633 free(ctx
->commit_graph_filenames_after
);
1634 free(ctx
->commit_graph_filenames_before
);
1635 free(ctx
->commit_graph_hash_after
);
1643 #define VERIFY_COMMIT_GRAPH_ERROR_HASH 2
1644 static int verify_commit_graph_error
;
1646 static void graph_report(const char *fmt
, ...)
1650 verify_commit_graph_error
= 1;
1652 vfprintf(stderr
, fmt
, ap
);
1653 fprintf(stderr
, "\n");
1657 #define GENERATION_ZERO_EXISTS 1
1658 #define GENERATION_NUMBER_EXISTS 2
1660 int verify_commit_graph(struct repository
*r
, struct commit_graph
*g
)
1662 uint32_t i
, cur_fanout_pos
= 0;
1663 struct object_id prev_oid
, cur_oid
, checksum
;
1664 int generation_zero
= 0;
1667 struct progress
*progress
= NULL
;
1670 graph_report("no commit-graph file loaded");
1674 verify_commit_graph_error
= verify_commit_graph_lite(g
);
1675 if (verify_commit_graph_error
)
1676 return verify_commit_graph_error
;
1678 devnull
= open("/dev/null", O_WRONLY
);
1679 f
= hashfd(devnull
, NULL
);
1680 hashwrite(f
, g
->data
, g
->data_len
- g
->hash_len
);
1681 finalize_hashfile(f
, checksum
.hash
, CSUM_CLOSE
);
1682 if (!hasheq(checksum
.hash
, g
->data
+ g
->data_len
- g
->hash_len
)) {
1683 graph_report(_("the commit-graph file has incorrect checksum and is likely corrupt"));
1684 verify_commit_graph_error
= VERIFY_COMMIT_GRAPH_ERROR_HASH
;
1687 for (i
= 0; i
< g
->num_commits
; i
++) {
1688 struct commit
*graph_commit
;
1690 hashcpy(cur_oid
.hash
, g
->chunk_oid_lookup
+ g
->hash_len
* i
);
1692 if (i
&& oidcmp(&prev_oid
, &cur_oid
) >= 0)
1693 graph_report(_("commit-graph has incorrect OID order: %s then %s"),
1694 oid_to_hex(&prev_oid
),
1695 oid_to_hex(&cur_oid
));
1697 oidcpy(&prev_oid
, &cur_oid
);
1699 while (cur_oid
.hash
[0] > cur_fanout_pos
) {
1700 uint32_t fanout_value
= get_be32(g
->chunk_oid_fanout
+ cur_fanout_pos
);
1702 if (i
!= fanout_value
)
1703 graph_report(_("commit-graph has incorrect fanout value: fanout[%d] = %u != %u"),
1704 cur_fanout_pos
, fanout_value
, i
);
1708 graph_commit
= lookup_commit(r
, &cur_oid
);
1709 if (!parse_commit_in_graph_one(r
, g
, graph_commit
))
1710 graph_report(_("failed to parse commit %s from commit-graph"),
1711 oid_to_hex(&cur_oid
));
1714 while (cur_fanout_pos
< 256) {
1715 uint32_t fanout_value
= get_be32(g
->chunk_oid_fanout
+ cur_fanout_pos
);
1717 if (g
->num_commits
!= fanout_value
)
1718 graph_report(_("commit-graph has incorrect fanout value: fanout[%d] = %u != %u"),
1719 cur_fanout_pos
, fanout_value
, i
);
1724 if (verify_commit_graph_error
& ~VERIFY_COMMIT_GRAPH_ERROR_HASH
)
1725 return verify_commit_graph_error
;
1727 progress
= start_progress(_("Verifying commits in commit graph"),
1729 for (i
= 0; i
< g
->num_commits
; i
++) {
1730 struct commit
*graph_commit
, *odb_commit
;
1731 struct commit_list
*graph_parents
, *odb_parents
;
1732 uint32_t max_generation
= 0;
1734 display_progress(progress
, i
+ 1);
1735 hashcpy(cur_oid
.hash
, g
->chunk_oid_lookup
+ g
->hash_len
* i
);
1737 graph_commit
= lookup_commit(r
, &cur_oid
);
1738 odb_commit
= (struct commit
*)create_object(r
, cur_oid
.hash
, alloc_commit_node(r
));
1739 if (parse_commit_internal(odb_commit
, 0, 0)) {
1740 graph_report(_("failed to parse commit %s from object database for commit-graph"),
1741 oid_to_hex(&cur_oid
));
1745 if (!oideq(&get_commit_tree_in_graph_one(r
, g
, graph_commit
)->object
.oid
,
1746 get_commit_tree_oid(odb_commit
)))
1747 graph_report(_("root tree OID for commit %s in commit-graph is %s != %s"),
1748 oid_to_hex(&cur_oid
),
1749 oid_to_hex(get_commit_tree_oid(graph_commit
)),
1750 oid_to_hex(get_commit_tree_oid(odb_commit
)));
1752 graph_parents
= graph_commit
->parents
;
1753 odb_parents
= odb_commit
->parents
;
1755 while (graph_parents
) {
1756 if (odb_parents
== NULL
) {
1757 graph_report(_("commit-graph parent list for commit %s is too long"),
1758 oid_to_hex(&cur_oid
));
1762 if (!oideq(&graph_parents
->item
->object
.oid
, &odb_parents
->item
->object
.oid
))
1763 graph_report(_("commit-graph parent for %s is %s != %s"),
1764 oid_to_hex(&cur_oid
),
1765 oid_to_hex(&graph_parents
->item
->object
.oid
),
1766 oid_to_hex(&odb_parents
->item
->object
.oid
));
1768 if (graph_parents
->item
->generation
> max_generation
)
1769 max_generation
= graph_parents
->item
->generation
;
1771 graph_parents
= graph_parents
->next
;
1772 odb_parents
= odb_parents
->next
;
1775 if (odb_parents
!= NULL
)
1776 graph_report(_("commit-graph parent list for commit %s terminates early"),
1777 oid_to_hex(&cur_oid
));
1779 if (!graph_commit
->generation
) {
1780 if (generation_zero
== GENERATION_NUMBER_EXISTS
)
1781 graph_report(_("commit-graph has generation number zero for commit %s, but non-zero elsewhere"),
1782 oid_to_hex(&cur_oid
));
1783 generation_zero
= GENERATION_ZERO_EXISTS
;
1784 } else if (generation_zero
== GENERATION_ZERO_EXISTS
)
1785 graph_report(_("commit-graph has non-zero generation number for commit %s, but zero elsewhere"),
1786 oid_to_hex(&cur_oid
));
1788 if (generation_zero
== GENERATION_ZERO_EXISTS
)
1792 * If one of our parents has generation GENERATION_NUMBER_MAX, then
1793 * our generation is also GENERATION_NUMBER_MAX. Decrement to avoid
1794 * extra logic in the following condition.
1796 if (max_generation
== GENERATION_NUMBER_MAX
)
1799 if (graph_commit
->generation
!= max_generation
+ 1)
1800 graph_report(_("commit-graph generation for commit %s is %u != %u"),
1801 oid_to_hex(&cur_oid
),
1802 graph_commit
->generation
,
1803 max_generation
+ 1);
1805 if (graph_commit
->date
!= odb_commit
->date
)
1806 graph_report(_("commit date for commit %s in commit-graph is %"PRItime
" != %"PRItime
),
1807 oid_to_hex(&cur_oid
),
1811 stop_progress(&progress
);
1813 return verify_commit_graph_error
;
1816 void free_commit_graph(struct commit_graph
*g
)
1820 if (g
->graph_fd
>= 0) {
1821 munmap((void *)g
->data
, g
->data_len
);