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 /* Remember to update object flag allocation in object.h */
45 #define REACHABLE (1u<<15)
47 char *get_commit_graph_filename(struct object_directory
*odb
)
49 return xstrfmt("%s/info/commit-graph", odb
->path
);
52 static char *get_split_graph_filename(struct object_directory
*odb
,
55 return xstrfmt("%s/info/commit-graphs/graph-%s.graph", odb
->path
,
59 static char *get_chain_filename(struct object_directory
*odb
)
61 return xstrfmt("%s/info/commit-graphs/commit-graph-chain", odb
->path
);
64 static uint8_t oid_version(void)
69 static struct commit_graph
*alloc_commit_graph(void)
71 struct commit_graph
*g
= xcalloc(1, sizeof(*g
));
77 extern int read_replace_refs
;
79 static int commit_graph_compatible(struct repository
*r
)
84 if (read_replace_refs
) {
85 prepare_replace_object(r
);
86 if (hashmap_get_size(&r
->objects
->replace_map
->map
))
90 prepare_commit_graft(r
);
91 if (r
->parsed_objects
&& r
->parsed_objects
->grafts_nr
)
93 if (is_repository_shallow(r
))
99 int open_commit_graph(const char *graph_file
, int *fd
, struct stat
*st
)
101 *fd
= git_open(graph_file
);
104 if (fstat(*fd
, st
)) {
111 struct commit_graph
*load_commit_graph_one_fd_st(int fd
, struct stat
*st
,
112 struct object_directory
*odb
)
116 struct commit_graph
*ret
;
118 graph_size
= xsize_t(st
->st_size
);
120 if (graph_size
< GRAPH_MIN_SIZE
) {
122 error(_("commit-graph file is too small"));
125 graph_map
= xmmap(NULL
, graph_size
, PROT_READ
, MAP_PRIVATE
, fd
, 0);
126 ret
= parse_commit_graph(graph_map
, fd
, graph_size
);
131 munmap(graph_map
, graph_size
);
138 static int verify_commit_graph_lite(struct commit_graph
*g
)
141 * Basic validation shared between parse_commit_graph()
142 * which'll be called every time the graph is used, and the
143 * much more expensive verify_commit_graph() used by
144 * "commit-graph verify".
146 * There should only be very basic checks here to ensure that
147 * we don't e.g. segfault in fill_commit_in_graph(), but
148 e because this is a very hot codepath nothing that e.g. loops
149 * over g->num_commits, or runs a checksum on the commit-graph
152 if (!g
->chunk_oid_fanout
) {
153 error("commit-graph is missing the OID Fanout chunk");
156 if (!g
->chunk_oid_lookup
) {
157 error("commit-graph is missing the OID Lookup chunk");
160 if (!g
->chunk_commit_data
) {
161 error("commit-graph is missing the Commit Data chunk");
168 struct commit_graph
*parse_commit_graph(void *graph_map
, int fd
,
171 const unsigned char *data
, *chunk_lookup
;
173 struct commit_graph
*graph
;
174 uint64_t last_chunk_offset
;
175 uint32_t last_chunk_id
;
176 uint32_t graph_signature
;
177 unsigned char graph_version
, hash_version
;
182 if (graph_size
< GRAPH_MIN_SIZE
)
185 data
= (const unsigned char *)graph_map
;
187 graph_signature
= get_be32(data
);
188 if (graph_signature
!= GRAPH_SIGNATURE
) {
189 error(_("commit-graph signature %X does not match signature %X"),
190 graph_signature
, GRAPH_SIGNATURE
);
194 graph_version
= *(unsigned char*)(data
+ 4);
195 if (graph_version
!= GRAPH_VERSION
) {
196 error(_("commit-graph version %X does not match version %X"),
197 graph_version
, GRAPH_VERSION
);
201 hash_version
= *(unsigned char*)(data
+ 5);
202 if (hash_version
!= oid_version()) {
203 error(_("commit-graph hash version %X does not match version %X"),
204 hash_version
, oid_version());
208 graph
= alloc_commit_graph();
210 graph
->hash_len
= the_hash_algo
->rawsz
;
211 graph
->num_chunks
= *(unsigned char*)(data
+ 6);
212 graph
->graph_fd
= fd
;
213 graph
->data
= graph_map
;
214 graph
->data_len
= graph_size
;
217 last_chunk_offset
= 8;
218 chunk_lookup
= data
+ 8;
219 for (i
= 0; i
< graph
->num_chunks
; i
++) {
221 uint64_t chunk_offset
;
222 int chunk_repeated
= 0;
224 if (data
+ graph_size
- chunk_lookup
<
225 GRAPH_CHUNKLOOKUP_WIDTH
) {
226 error(_("commit-graph chunk lookup table entry missing; file may be incomplete"));
231 chunk_id
= get_be32(chunk_lookup
+ 0);
232 chunk_offset
= get_be64(chunk_lookup
+ 4);
234 chunk_lookup
+= GRAPH_CHUNKLOOKUP_WIDTH
;
236 if (chunk_offset
> graph_size
- the_hash_algo
->rawsz
) {
237 error(_("commit-graph improper chunk offset %08x%08x"), (uint32_t)(chunk_offset
>> 32),
238 (uint32_t)chunk_offset
);
244 case GRAPH_CHUNKID_OIDFANOUT
:
245 if (graph
->chunk_oid_fanout
)
248 graph
->chunk_oid_fanout
= (uint32_t*)(data
+ chunk_offset
);
251 case GRAPH_CHUNKID_OIDLOOKUP
:
252 if (graph
->chunk_oid_lookup
)
255 graph
->chunk_oid_lookup
= data
+ chunk_offset
;
258 case GRAPH_CHUNKID_DATA
:
259 if (graph
->chunk_commit_data
)
262 graph
->chunk_commit_data
= data
+ chunk_offset
;
265 case GRAPH_CHUNKID_EXTRAEDGES
:
266 if (graph
->chunk_extra_edges
)
269 graph
->chunk_extra_edges
= data
+ chunk_offset
;
272 case GRAPH_CHUNKID_BASE
:
273 if (graph
->chunk_base_graphs
)
276 graph
->chunk_base_graphs
= data
+ chunk_offset
;
279 if (chunk_repeated
) {
280 error(_("commit-graph chunk id %08x appears multiple times"), chunk_id
);
285 if (last_chunk_id
== GRAPH_CHUNKID_OIDLOOKUP
)
287 graph
->num_commits
= (chunk_offset
- last_chunk_offset
)
291 last_chunk_id
= chunk_id
;
292 last_chunk_offset
= chunk_offset
;
295 hashcpy(graph
->oid
.hash
, graph
->data
+ graph
->data_len
- graph
->hash_len
);
297 if (verify_commit_graph_lite(graph
)) {
305 static struct commit_graph
*load_commit_graph_one(const char *graph_file
,
306 struct object_directory
*odb
)
311 struct commit_graph
*g
;
312 int open_ok
= open_commit_graph(graph_file
, &fd
, &st
);
317 g
= load_commit_graph_one_fd_st(fd
, &st
, odb
);
320 g
->filename
= xstrdup(graph_file
);
325 static struct commit_graph
*load_commit_graph_v1(struct repository
*r
,
326 struct object_directory
*odb
)
328 char *graph_name
= get_commit_graph_filename(odb
);
329 struct commit_graph
*g
= load_commit_graph_one(graph_name
, odb
);
335 static int add_graph_to_chain(struct commit_graph
*g
,
336 struct commit_graph
*chain
,
337 struct object_id
*oids
,
340 struct commit_graph
*cur_g
= chain
;
342 if (n
&& !g
->chunk_base_graphs
) {
343 warning(_("commit-graph has no base graphs chunk"));
351 !oideq(&oids
[n
], &cur_g
->oid
) ||
352 !hasheq(oids
[n
].hash
, g
->chunk_base_graphs
+ g
->hash_len
* n
)) {
353 warning(_("commit-graph chain does not match"));
357 cur_g
= cur_g
->base_graph
;
360 g
->base_graph
= chain
;
363 g
->num_commits_in_base
= chain
->num_commits
+ chain
->num_commits_in_base
;
368 static struct commit_graph
*load_commit_graph_chain(struct repository
*r
,
369 struct object_directory
*odb
)
371 struct commit_graph
*graph_chain
= NULL
;
372 struct strbuf line
= STRBUF_INIT
;
374 struct object_id
*oids
;
375 int i
= 0, valid
= 1, count
;
376 char *chain_name
= get_chain_filename(odb
);
380 fp
= fopen(chain_name
, "r");
381 stat_res
= stat(chain_name
, &st
);
386 st
.st_size
<= the_hash_algo
->hexsz
)
389 count
= st
.st_size
/ (the_hash_algo
->hexsz
+ 1);
390 oids
= xcalloc(count
, sizeof(struct object_id
));
394 for (i
= 0; i
< count
; i
++) {
395 struct object_directory
*odb
;
397 if (strbuf_getline_lf(&line
, fp
) == EOF
)
400 if (get_oid_hex(line
.buf
, &oids
[i
])) {
401 warning(_("invalid commit-graph chain: line '%s' not a hash"),
408 for (odb
= r
->objects
->odb
; odb
; odb
= odb
->next
) {
409 char *graph_name
= get_split_graph_filename(odb
, line
.buf
);
410 struct commit_graph
*g
= load_commit_graph_one(graph_name
, odb
);
415 if (add_graph_to_chain(g
, graph_chain
, oids
, i
)) {
425 warning(_("unable to find all commit-graph files"));
432 strbuf_release(&line
);
437 struct commit_graph
*read_commit_graph_one(struct repository
*r
,
438 struct object_directory
*odb
)
440 struct commit_graph
*g
= load_commit_graph_v1(r
, odb
);
443 g
= load_commit_graph_chain(r
, odb
);
448 static void prepare_commit_graph_one(struct repository
*r
,
449 struct object_directory
*odb
)
452 if (r
->objects
->commit_graph
)
455 r
->objects
->commit_graph
= read_commit_graph_one(r
, odb
);
459 * Return 1 if commit_graph is non-NULL, and 0 otherwise.
461 * On the first invocation, this function attempts to load the commit
462 * graph if the_repository is configured to have one.
464 static int prepare_commit_graph(struct repository
*r
)
466 struct object_directory
*odb
;
469 * This must come before the "already attempted?" check below, because
470 * we want to disable even an already-loaded graph file.
472 if (r
->commit_graph_disabled
)
475 if (r
->objects
->commit_graph_attempted
)
476 return !!r
->objects
->commit_graph
;
477 r
->objects
->commit_graph_attempted
= 1;
479 if (git_env_bool(GIT_TEST_COMMIT_GRAPH_DIE_ON_LOAD
, 0))
480 die("dying as requested by the '%s' variable on commit-graph load!",
481 GIT_TEST_COMMIT_GRAPH_DIE_ON_LOAD
);
483 prepare_repo_settings(r
);
485 if (!git_env_bool(GIT_TEST_COMMIT_GRAPH
, 0) &&
486 r
->settings
.core_commit_graph
!= 1)
488 * This repository is not configured to use commit graphs, so
489 * do not load one. (But report commit_graph_attempted anyway
490 * so that commit graph loading is not attempted again for this
495 if (!commit_graph_compatible(r
))
499 for (odb
= r
->objects
->odb
;
500 !r
->objects
->commit_graph
&& odb
;
502 prepare_commit_graph_one(r
, odb
);
503 return !!r
->objects
->commit_graph
;
506 int generation_numbers_enabled(struct repository
*r
)
508 uint32_t first_generation
;
509 struct commit_graph
*g
;
510 if (!prepare_commit_graph(r
))
513 g
= r
->objects
->commit_graph
;
518 first_generation
= get_be32(g
->chunk_commit_data
+
519 g
->hash_len
+ 8) >> 2;
521 return !!first_generation
;
524 static void close_commit_graph_one(struct commit_graph
*g
)
529 close_commit_graph_one(g
->base_graph
);
530 free_commit_graph(g
);
533 void close_commit_graph(struct raw_object_store
*o
)
535 close_commit_graph_one(o
->commit_graph
);
536 o
->commit_graph
= NULL
;
539 static int bsearch_graph(struct commit_graph
*g
, struct object_id
*oid
, uint32_t *pos
)
541 return bsearch_hash(oid
->hash
, g
->chunk_oid_fanout
,
542 g
->chunk_oid_lookup
, g
->hash_len
, pos
);
545 static void load_oid_from_graph(struct commit_graph
*g
,
547 struct object_id
*oid
)
551 while (g
&& pos
< g
->num_commits_in_base
)
555 BUG("NULL commit-graph");
557 if (pos
>= g
->num_commits
+ g
->num_commits_in_base
)
558 die(_("invalid commit position. commit-graph is likely corrupt"));
560 lex_index
= pos
- g
->num_commits_in_base
;
562 hashcpy(oid
->hash
, g
->chunk_oid_lookup
+ g
->hash_len
* lex_index
);
565 static struct commit_list
**insert_parent_or_die(struct repository
*r
,
566 struct commit_graph
*g
,
568 struct commit_list
**pptr
)
571 struct object_id oid
;
573 if (pos
>= g
->num_commits
+ g
->num_commits_in_base
)
574 die("invalid parent position %"PRIu32
, pos
);
576 load_oid_from_graph(g
, pos
, &oid
);
577 c
= lookup_commit(r
, &oid
);
579 die(_("could not find commit %s"), oid_to_hex(&oid
));
581 return &commit_list_insert(c
, pptr
)->next
;
584 static void fill_commit_graph_info(struct commit
*item
, struct commit_graph
*g
, uint32_t pos
)
586 const unsigned char *commit_data
;
589 while (pos
< g
->num_commits_in_base
)
592 lex_index
= pos
- g
->num_commits_in_base
;
593 commit_data
= g
->chunk_commit_data
+ GRAPH_DATA_WIDTH
* lex_index
;
594 item
->graph_pos
= pos
;
595 item
->generation
= get_be32(commit_data
+ g
->hash_len
+ 8) >> 2;
598 static inline void set_commit_tree(struct commit
*c
, struct tree
*t
)
603 static int fill_commit_in_graph(struct repository
*r
,
605 struct commit_graph
*g
, uint32_t pos
)
608 uint32_t *parent_data_ptr
;
609 uint64_t date_low
, date_high
;
610 struct commit_list
**pptr
;
611 const unsigned char *commit_data
;
614 while (pos
< g
->num_commits_in_base
)
617 if (pos
>= g
->num_commits
+ g
->num_commits_in_base
)
618 die(_("invalid commit position. commit-graph is likely corrupt"));
621 * Store the "full" position, but then use the
622 * "local" position for the rest of the calculation.
624 item
->graph_pos
= pos
;
625 lex_index
= pos
- g
->num_commits_in_base
;
627 commit_data
= g
->chunk_commit_data
+ (g
->hash_len
+ 16) * lex_index
;
629 item
->object
.parsed
= 1;
631 set_commit_tree(item
, NULL
);
633 date_high
= get_be32(commit_data
+ g
->hash_len
+ 8) & 0x3;
634 date_low
= get_be32(commit_data
+ g
->hash_len
+ 12);
635 item
->date
= (timestamp_t
)((date_high
<< 32) | date_low
);
637 item
->generation
= get_be32(commit_data
+ g
->hash_len
+ 8) >> 2;
639 pptr
= &item
->parents
;
641 edge_value
= get_be32(commit_data
+ g
->hash_len
);
642 if (edge_value
== GRAPH_PARENT_NONE
)
644 pptr
= insert_parent_or_die(r
, g
, edge_value
, pptr
);
646 edge_value
= get_be32(commit_data
+ g
->hash_len
+ 4);
647 if (edge_value
== GRAPH_PARENT_NONE
)
649 if (!(edge_value
& GRAPH_EXTRA_EDGES_NEEDED
)) {
650 pptr
= insert_parent_or_die(r
, g
, edge_value
, pptr
);
654 parent_data_ptr
= (uint32_t*)(g
->chunk_extra_edges
+
655 4 * (uint64_t)(edge_value
& GRAPH_EDGE_LAST_MASK
));
657 edge_value
= get_be32(parent_data_ptr
);
658 pptr
= insert_parent_or_die(r
, g
,
659 edge_value
& GRAPH_EDGE_LAST_MASK
,
662 } while (!(edge_value
& GRAPH_LAST_EDGE
));
667 static int find_commit_in_graph(struct commit
*item
, struct commit_graph
*g
, uint32_t *pos
)
669 if (item
->graph_pos
!= COMMIT_NOT_FROM_GRAPH
) {
670 *pos
= item
->graph_pos
;
673 struct commit_graph
*cur_g
= g
;
676 while (cur_g
&& !bsearch_graph(cur_g
, &(item
->object
.oid
), &lex_index
))
677 cur_g
= cur_g
->base_graph
;
680 *pos
= lex_index
+ cur_g
->num_commits_in_base
;
688 static int parse_commit_in_graph_one(struct repository
*r
,
689 struct commit_graph
*g
,
694 if (item
->object
.parsed
)
697 if (find_commit_in_graph(item
, g
, &pos
))
698 return fill_commit_in_graph(r
, item
, g
, pos
);
703 int parse_commit_in_graph(struct repository
*r
, struct commit
*item
)
705 if (!prepare_commit_graph(r
))
707 return parse_commit_in_graph_one(r
, r
->objects
->commit_graph
, item
);
710 void load_commit_graph_info(struct repository
*r
, struct commit
*item
)
713 if (!prepare_commit_graph(r
))
715 if (find_commit_in_graph(item
, r
->objects
->commit_graph
, &pos
))
716 fill_commit_graph_info(item
, r
->objects
->commit_graph
, pos
);
719 static struct tree
*load_tree_for_commit(struct repository
*r
,
720 struct commit_graph
*g
,
723 struct object_id oid
;
724 const unsigned char *commit_data
;
726 while (c
->graph_pos
< g
->num_commits_in_base
)
729 commit_data
= g
->chunk_commit_data
+
730 GRAPH_DATA_WIDTH
* (c
->graph_pos
- g
->num_commits_in_base
);
732 hashcpy(oid
.hash
, commit_data
);
733 set_commit_tree(c
, lookup_tree(r
, &oid
));
735 return c
->maybe_tree
;
738 static struct tree
*get_commit_tree_in_graph_one(struct repository
*r
,
739 struct commit_graph
*g
,
740 const struct commit
*c
)
743 return c
->maybe_tree
;
744 if (c
->graph_pos
== COMMIT_NOT_FROM_GRAPH
)
745 BUG("get_commit_tree_in_graph_one called from non-commit-graph commit");
747 return load_tree_for_commit(r
, g
, (struct commit
*)c
);
750 struct tree
*get_commit_tree_in_graph(struct repository
*r
, const struct commit
*c
)
752 return get_commit_tree_in_graph_one(r
, r
->objects
->commit_graph
, c
);
755 struct packed_commit_list
{
756 struct commit
**list
;
761 struct packed_oid_list
{
762 struct object_id
*list
;
767 struct write_commit_graph_context
{
768 struct repository
*r
;
769 struct object_directory
*odb
;
771 struct packed_oid_list oids
;
772 struct packed_commit_list commits
;
774 unsigned long approx_nr_objects
;
775 struct progress
*progress
;
777 uint64_t progress_cnt
;
779 char *base_graph_name
;
780 int num_commit_graphs_before
;
781 int num_commit_graphs_after
;
782 char **commit_graph_filenames_before
;
783 char **commit_graph_filenames_after
;
784 char **commit_graph_hash_after
;
785 uint32_t new_num_commits_in_base
;
786 struct commit_graph
*new_base_graph
;
793 const struct split_commit_graph_opts
*split_opts
;
796 static void write_graph_chunk_fanout(struct hashfile
*f
,
797 struct write_commit_graph_context
*ctx
)
800 struct commit
**list
= ctx
->commits
.list
;
803 * Write the first-level table (the list is sorted,
804 * but we use a 256-entry lookup to be able to avoid
805 * having to do eight extra binary search iterations).
807 for (i
= 0; i
< 256; i
++) {
808 while (count
< ctx
->commits
.nr
) {
809 if ((*list
)->object
.oid
.hash
[0] != i
)
811 display_progress(ctx
->progress
, ++ctx
->progress_cnt
);
816 hashwrite_be32(f
, count
);
820 static void write_graph_chunk_oids(struct hashfile
*f
, int hash_len
,
821 struct write_commit_graph_context
*ctx
)
823 struct commit
**list
= ctx
->commits
.list
;
825 for (count
= 0; count
< ctx
->commits
.nr
; count
++, list
++) {
826 display_progress(ctx
->progress
, ++ctx
->progress_cnt
);
827 hashwrite(f
, (*list
)->object
.oid
.hash
, (int)hash_len
);
831 static const unsigned char *commit_to_sha1(size_t index
, void *table
)
833 struct commit
**commits
= table
;
834 return commits
[index
]->object
.oid
.hash
;
837 static void write_graph_chunk_data(struct hashfile
*f
, int hash_len
,
838 struct write_commit_graph_context
*ctx
)
840 struct commit
**list
= ctx
->commits
.list
;
841 struct commit
**last
= ctx
->commits
.list
+ ctx
->commits
.nr
;
842 uint32_t num_extra_edges
= 0;
844 while (list
< last
) {
845 struct commit_list
*parent
;
846 struct object_id
*tree
;
848 uint32_t packedDate
[2];
849 display_progress(ctx
->progress
, ++ctx
->progress_cnt
);
851 if (parse_commit_no_graph(*list
))
852 die(_("unable to parse commit %s"),
853 oid_to_hex(&(*list
)->object
.oid
));
854 tree
= get_commit_tree_oid(*list
);
855 hashwrite(f
, tree
->hash
, hash_len
);
857 parent
= (*list
)->parents
;
860 edge_value
= GRAPH_PARENT_NONE
;
862 edge_value
= sha1_pos(parent
->item
->object
.oid
.hash
,
868 edge_value
+= ctx
->new_num_commits_in_base
;
869 else if (ctx
->new_base_graph
) {
871 if (find_commit_in_graph(parent
->item
,
878 BUG("missing parent %s for commit %s",
879 oid_to_hex(&parent
->item
->object
.oid
),
880 oid_to_hex(&(*list
)->object
.oid
));
883 hashwrite_be32(f
, edge_value
);
886 parent
= parent
->next
;
889 edge_value
= GRAPH_PARENT_NONE
;
890 else if (parent
->next
)
891 edge_value
= GRAPH_EXTRA_EDGES_NEEDED
| num_extra_edges
;
893 edge_value
= sha1_pos(parent
->item
->object
.oid
.hash
,
899 edge_value
+= ctx
->new_num_commits_in_base
;
900 else if (ctx
->new_base_graph
) {
902 if (find_commit_in_graph(parent
->item
,
909 BUG("missing parent %s for commit %s",
910 oid_to_hex(&parent
->item
->object
.oid
),
911 oid_to_hex(&(*list
)->object
.oid
));
914 hashwrite_be32(f
, edge_value
);
916 if (edge_value
& GRAPH_EXTRA_EDGES_NEEDED
) {
919 parent
= parent
->next
;
923 if (sizeof((*list
)->date
) > 4)
924 packedDate
[0] = htonl(((*list
)->date
>> 32) & 0x3);
928 packedDate
[0] |= htonl((*list
)->generation
<< 2);
930 packedDate
[1] = htonl((*list
)->date
);
931 hashwrite(f
, packedDate
, 8);
937 static void write_graph_chunk_extra_edges(struct hashfile
*f
,
938 struct write_commit_graph_context
*ctx
)
940 struct commit
**list
= ctx
->commits
.list
;
941 struct commit
**last
= ctx
->commits
.list
+ ctx
->commits
.nr
;
942 struct commit_list
*parent
;
944 while (list
< last
) {
947 display_progress(ctx
->progress
, ++ctx
->progress_cnt
);
949 for (parent
= (*list
)->parents
; num_parents
< 3 && parent
;
950 parent
= parent
->next
)
953 if (num_parents
<= 2) {
958 /* Since num_parents > 2, this initializer is safe. */
959 for (parent
= (*list
)->parents
->next
; parent
; parent
= parent
->next
) {
960 int edge_value
= sha1_pos(parent
->item
->object
.oid
.hash
,
966 edge_value
+= ctx
->new_num_commits_in_base
;
967 else if (ctx
->new_base_graph
) {
969 if (find_commit_in_graph(parent
->item
,
976 BUG("missing parent %s for commit %s",
977 oid_to_hex(&parent
->item
->object
.oid
),
978 oid_to_hex(&(*list
)->object
.oid
));
979 else if (!parent
->next
)
980 edge_value
|= GRAPH_LAST_EDGE
;
982 hashwrite_be32(f
, edge_value
);
989 static int oid_compare(const void *_a
, const void *_b
)
991 const struct object_id
*a
= (const struct object_id
*)_a
;
992 const struct object_id
*b
= (const struct object_id
*)_b
;
996 static int add_packed_commits(const struct object_id
*oid
,
997 struct packed_git
*pack
,
1001 struct write_commit_graph_context
*ctx
= (struct write_commit_graph_context
*)data
;
1002 enum object_type type
;
1003 off_t offset
= nth_packed_object_offset(pack
, pos
);
1004 struct object_info oi
= OBJECT_INFO_INIT
;
1007 display_progress(ctx
->progress
, ++ctx
->progress_done
);
1010 if (packed_object_info(ctx
->r
, pack
, offset
, &oi
) < 0)
1011 die(_("unable to get type of object %s"), oid_to_hex(oid
));
1013 if (type
!= OBJ_COMMIT
)
1016 ALLOC_GROW(ctx
->oids
.list
, ctx
->oids
.nr
+ 1, ctx
->oids
.alloc
);
1017 oidcpy(&(ctx
->oids
.list
[ctx
->oids
.nr
]), oid
);
1023 static void add_missing_parents(struct write_commit_graph_context
*ctx
, struct commit
*commit
)
1025 struct commit_list
*parent
;
1026 for (parent
= commit
->parents
; parent
; parent
= parent
->next
) {
1027 if (!(parent
->item
->object
.flags
& REACHABLE
)) {
1028 ALLOC_GROW(ctx
->oids
.list
, ctx
->oids
.nr
+ 1, ctx
->oids
.alloc
);
1029 oidcpy(&ctx
->oids
.list
[ctx
->oids
.nr
], &(parent
->item
->object
.oid
));
1031 parent
->item
->object
.flags
|= REACHABLE
;
1036 static void close_reachable(struct write_commit_graph_context
*ctx
)
1039 struct commit
*commit
;
1040 enum commit_graph_split_flags flags
= ctx
->split_opts
?
1041 ctx
->split_opts
->flags
: COMMIT_GRAPH_SPLIT_UNSPECIFIED
;
1043 if (ctx
->report_progress
)
1044 ctx
->progress
= start_delayed_progress(
1045 _("Loading known commits in commit graph"),
1047 for (i
= 0; i
< ctx
->oids
.nr
; i
++) {
1048 display_progress(ctx
->progress
, i
+ 1);
1049 commit
= lookup_commit(ctx
->r
, &ctx
->oids
.list
[i
]);
1051 commit
->object
.flags
|= REACHABLE
;
1053 stop_progress(&ctx
->progress
);
1056 * As this loop runs, ctx->oids.nr may grow, but not more
1057 * than the number of missing commits in the reachable
1060 if (ctx
->report_progress
)
1061 ctx
->progress
= start_delayed_progress(
1062 _("Expanding reachable commits in commit graph"),
1064 for (i
= 0; i
< ctx
->oids
.nr
; i
++) {
1065 display_progress(ctx
->progress
, i
+ 1);
1066 commit
= lookup_commit(ctx
->r
, &ctx
->oids
.list
[i
]);
1071 if ((!parse_commit(commit
) &&
1072 commit
->graph_pos
== COMMIT_NOT_FROM_GRAPH
) ||
1073 flags
== COMMIT_GRAPH_SPLIT_REPLACE
)
1074 add_missing_parents(ctx
, commit
);
1075 } else if (!parse_commit_no_graph(commit
))
1076 add_missing_parents(ctx
, commit
);
1078 stop_progress(&ctx
->progress
);
1080 if (ctx
->report_progress
)
1081 ctx
->progress
= start_delayed_progress(
1082 _("Clearing commit marks in commit graph"),
1084 for (i
= 0; i
< ctx
->oids
.nr
; i
++) {
1085 display_progress(ctx
->progress
, i
+ 1);
1086 commit
= lookup_commit(ctx
->r
, &ctx
->oids
.list
[i
]);
1089 commit
->object
.flags
&= ~REACHABLE
;
1091 stop_progress(&ctx
->progress
);
1094 static void compute_generation_numbers(struct write_commit_graph_context
*ctx
)
1097 struct commit_list
*list
= NULL
;
1099 if (ctx
->report_progress
)
1100 ctx
->progress
= start_delayed_progress(
1101 _("Computing commit graph generation numbers"),
1103 for (i
= 0; i
< ctx
->commits
.nr
; i
++) {
1104 display_progress(ctx
->progress
, i
+ 1);
1105 if (ctx
->commits
.list
[i
]->generation
!= GENERATION_NUMBER_INFINITY
&&
1106 ctx
->commits
.list
[i
]->generation
!= GENERATION_NUMBER_ZERO
)
1109 commit_list_insert(ctx
->commits
.list
[i
], &list
);
1111 struct commit
*current
= list
->item
;
1112 struct commit_list
*parent
;
1113 int all_parents_computed
= 1;
1114 uint32_t max_generation
= 0;
1116 for (parent
= current
->parents
; parent
; parent
= parent
->next
) {
1117 if (parent
->item
->generation
== GENERATION_NUMBER_INFINITY
||
1118 parent
->item
->generation
== GENERATION_NUMBER_ZERO
) {
1119 all_parents_computed
= 0;
1120 commit_list_insert(parent
->item
, &list
);
1122 } else if (parent
->item
->generation
> max_generation
) {
1123 max_generation
= parent
->item
->generation
;
1127 if (all_parents_computed
) {
1128 current
->generation
= max_generation
+ 1;
1131 if (current
->generation
> GENERATION_NUMBER_MAX
)
1132 current
->generation
= GENERATION_NUMBER_MAX
;
1136 stop_progress(&ctx
->progress
);
1139 static int add_ref_to_set(const char *refname
,
1140 const struct object_id
*oid
,
1141 int flags
, void *cb_data
)
1143 struct oidset
*commits
= (struct oidset
*)cb_data
;
1145 oidset_insert(commits
, oid
);
1149 int write_commit_graph_reachable(struct object_directory
*odb
,
1150 enum commit_graph_write_flags flags
,
1151 const struct split_commit_graph_opts
*split_opts
)
1153 struct oidset commits
= OIDSET_INIT
;
1156 for_each_ref(add_ref_to_set
, &commits
);
1157 result
= write_commit_graph(odb
, NULL
, &commits
,
1160 oidset_clear(&commits
);
1164 static int fill_oids_from_packs(struct write_commit_graph_context
*ctx
,
1165 struct string_list
*pack_indexes
)
1168 struct strbuf progress_title
= STRBUF_INIT
;
1169 struct strbuf packname
= STRBUF_INIT
;
1172 strbuf_addf(&packname
, "%s/pack/", ctx
->odb
->path
);
1173 dirlen
= packname
.len
;
1174 if (ctx
->report_progress
) {
1175 strbuf_addf(&progress_title
,
1176 Q_("Finding commits for commit graph in %d pack",
1177 "Finding commits for commit graph in %d packs",
1180 ctx
->progress
= start_delayed_progress(progress_title
.buf
, 0);
1181 ctx
->progress_done
= 0;
1183 for (i
= 0; i
< pack_indexes
->nr
; i
++) {
1184 struct packed_git
*p
;
1185 strbuf_setlen(&packname
, dirlen
);
1186 strbuf_addstr(&packname
, pack_indexes
->items
[i
].string
);
1187 p
= add_packed_git(packname
.buf
, packname
.len
, 1);
1189 error(_("error adding pack %s"), packname
.buf
);
1192 if (open_pack_index(p
)) {
1193 error(_("error opening index for %s"), packname
.buf
);
1196 for_each_object_in_pack(p
, add_packed_commits
, ctx
,
1197 FOR_EACH_OBJECT_PACK_ORDER
);
1202 stop_progress(&ctx
->progress
);
1203 strbuf_release(&progress_title
);
1204 strbuf_release(&packname
);
1209 static int fill_oids_from_commits(struct write_commit_graph_context
*ctx
,
1210 struct oidset
*commits
)
1213 struct strbuf progress_title
= STRBUF_INIT
;
1214 struct oidset_iter iter
;
1215 struct object_id
*oid
;
1217 if (!oidset_size(commits
))
1220 if (ctx
->report_progress
) {
1221 strbuf_addf(&progress_title
,
1222 Q_("Finding commits for commit graph from %d ref",
1223 "Finding commits for commit graph from %d refs",
1224 oidset_size(commits
)),
1225 oidset_size(commits
));
1226 ctx
->progress
= start_delayed_progress(
1228 oidset_size(commits
));
1231 oidset_iter_init(commits
, &iter
);
1232 while ((oid
= oidset_iter_next(&iter
))) {
1233 struct commit
*result
;
1235 display_progress(ctx
->progress
, ++i
);
1237 result
= lookup_commit_reference_gently(ctx
->r
, oid
, 1);
1239 ALLOC_GROW(ctx
->oids
.list
, ctx
->oids
.nr
+ 1, ctx
->oids
.alloc
);
1240 oidcpy(&ctx
->oids
.list
[ctx
->oids
.nr
], &(result
->object
.oid
));
1242 } else if (ctx
->check_oids
) {
1243 error(_("invalid commit object id: %s"),
1249 stop_progress(&ctx
->progress
);
1250 strbuf_release(&progress_title
);
1255 static void fill_oids_from_all_packs(struct write_commit_graph_context
*ctx
)
1257 if (ctx
->report_progress
)
1258 ctx
->progress
= start_delayed_progress(
1259 _("Finding commits for commit graph among packed objects"),
1260 ctx
->approx_nr_objects
);
1261 for_each_packed_object(add_packed_commits
, ctx
,
1262 FOR_EACH_OBJECT_PACK_ORDER
);
1263 if (ctx
->progress_done
< ctx
->approx_nr_objects
)
1264 display_progress(ctx
->progress
, ctx
->approx_nr_objects
);
1265 stop_progress(&ctx
->progress
);
1268 static uint32_t count_distinct_commits(struct write_commit_graph_context
*ctx
)
1270 uint32_t i
, count_distinct
= 1;
1272 if (ctx
->report_progress
)
1273 ctx
->progress
= start_delayed_progress(
1274 _("Counting distinct commits in commit graph"),
1276 display_progress(ctx
->progress
, 0); /* TODO: Measure QSORT() progress */
1277 QSORT(ctx
->oids
.list
, ctx
->oids
.nr
, oid_compare
);
1279 for (i
= 1; i
< ctx
->oids
.nr
; i
++) {
1280 display_progress(ctx
->progress
, i
+ 1);
1281 if (!oideq(&ctx
->oids
.list
[i
- 1], &ctx
->oids
.list
[i
])) {
1283 struct commit
*c
= lookup_commit(ctx
->r
, &ctx
->oids
.list
[i
]);
1285 if (!c
|| c
->graph_pos
!= COMMIT_NOT_FROM_GRAPH
)
1292 stop_progress(&ctx
->progress
);
1294 return count_distinct
;
1297 static void copy_oids_to_commits(struct write_commit_graph_context
*ctx
)
1300 enum commit_graph_split_flags flags
= ctx
->split_opts
?
1301 ctx
->split_opts
->flags
: COMMIT_GRAPH_SPLIT_UNSPECIFIED
;
1303 ctx
->num_extra_edges
= 0;
1304 if (ctx
->report_progress
)
1305 ctx
->progress
= start_delayed_progress(
1306 _("Finding extra edges in commit graph"),
1308 for (i
= 0; i
< ctx
->oids
.nr
; i
++) {
1309 unsigned int num_parents
;
1311 display_progress(ctx
->progress
, i
+ 1);
1312 if (i
> 0 && oideq(&ctx
->oids
.list
[i
- 1], &ctx
->oids
.list
[i
]))
1315 ALLOC_GROW(ctx
->commits
.list
, ctx
->commits
.nr
+ 1, ctx
->commits
.alloc
);
1316 ctx
->commits
.list
[ctx
->commits
.nr
] = lookup_commit(ctx
->r
, &ctx
->oids
.list
[i
]);
1318 if (ctx
->split
&& flags
!= COMMIT_GRAPH_SPLIT_REPLACE
&&
1319 ctx
->commits
.list
[ctx
->commits
.nr
]->graph_pos
!= COMMIT_NOT_FROM_GRAPH
)
1322 if (ctx
->split
&& flags
== COMMIT_GRAPH_SPLIT_REPLACE
)
1323 parse_commit(ctx
->commits
.list
[ctx
->commits
.nr
]);
1325 parse_commit_no_graph(ctx
->commits
.list
[ctx
->commits
.nr
]);
1327 num_parents
= commit_list_count(ctx
->commits
.list
[ctx
->commits
.nr
]->parents
);
1328 if (num_parents
> 2)
1329 ctx
->num_extra_edges
+= num_parents
- 1;
1333 stop_progress(&ctx
->progress
);
1336 static int write_graph_chunk_base_1(struct hashfile
*f
,
1337 struct commit_graph
*g
)
1344 num
= write_graph_chunk_base_1(f
, g
->base_graph
);
1345 hashwrite(f
, g
->oid
.hash
, the_hash_algo
->rawsz
);
1349 static int write_graph_chunk_base(struct hashfile
*f
,
1350 struct write_commit_graph_context
*ctx
)
1352 int num
= write_graph_chunk_base_1(f
, ctx
->new_base_graph
);
1354 if (num
!= ctx
->num_commit_graphs_after
- 1) {
1355 error(_("failed to write correct number of base graph ids"));
1362 static int write_commit_graph_file(struct write_commit_graph_context
*ctx
)
1367 struct lock_file lk
= LOCK_INIT
;
1368 uint32_t chunk_ids
[6];
1369 uint64_t chunk_offsets
[6];
1370 const unsigned hashsz
= the_hash_algo
->rawsz
;
1371 struct strbuf progress_title
= STRBUF_INIT
;
1373 struct object_id file_hash
;
1376 struct strbuf tmp_file
= STRBUF_INIT
;
1378 strbuf_addf(&tmp_file
,
1379 "%s/info/commit-graphs/tmp_graph_XXXXXX",
1381 ctx
->graph_name
= strbuf_detach(&tmp_file
, NULL
);
1383 ctx
->graph_name
= get_commit_graph_filename(ctx
->odb
);
1386 if (safe_create_leading_directories(ctx
->graph_name
)) {
1387 UNLEAK(ctx
->graph_name
);
1388 error(_("unable to create leading directories of %s"),
1394 char *lock_name
= get_chain_filename(ctx
->odb
);
1396 hold_lock_file_for_update(&lk
, lock_name
, LOCK_DIE_ON_ERROR
);
1398 fd
= git_mkstemp_mode(ctx
->graph_name
, 0444);
1400 error(_("unable to create temporary graph layer"));
1404 f
= hashfd(fd
, ctx
->graph_name
);
1406 hold_lock_file_for_update(&lk
, ctx
->graph_name
, LOCK_DIE_ON_ERROR
);
1407 fd
= lk
.tempfile
->fd
;
1408 f
= hashfd(lk
.tempfile
->fd
, lk
.tempfile
->filename
.buf
);
1411 chunk_ids
[0] = GRAPH_CHUNKID_OIDFANOUT
;
1412 chunk_ids
[1] = GRAPH_CHUNKID_OIDLOOKUP
;
1413 chunk_ids
[2] = GRAPH_CHUNKID_DATA
;
1414 if (ctx
->num_extra_edges
) {
1415 chunk_ids
[num_chunks
] = GRAPH_CHUNKID_EXTRAEDGES
;
1418 if (ctx
->num_commit_graphs_after
> 1) {
1419 chunk_ids
[num_chunks
] = GRAPH_CHUNKID_BASE
;
1423 chunk_ids
[num_chunks
] = 0;
1425 chunk_offsets
[0] = 8 + (num_chunks
+ 1) * GRAPH_CHUNKLOOKUP_WIDTH
;
1426 chunk_offsets
[1] = chunk_offsets
[0] + GRAPH_FANOUT_SIZE
;
1427 chunk_offsets
[2] = chunk_offsets
[1] + hashsz
* ctx
->commits
.nr
;
1428 chunk_offsets
[3] = chunk_offsets
[2] + (hashsz
+ 16) * ctx
->commits
.nr
;
1431 if (ctx
->num_extra_edges
) {
1432 chunk_offsets
[num_chunks
+ 1] = chunk_offsets
[num_chunks
] +
1433 4 * ctx
->num_extra_edges
;
1436 if (ctx
->num_commit_graphs_after
> 1) {
1437 chunk_offsets
[num_chunks
+ 1] = chunk_offsets
[num_chunks
] +
1438 hashsz
* (ctx
->num_commit_graphs_after
- 1);
1442 hashwrite_be32(f
, GRAPH_SIGNATURE
);
1444 hashwrite_u8(f
, GRAPH_VERSION
);
1445 hashwrite_u8(f
, oid_version());
1446 hashwrite_u8(f
, num_chunks
);
1447 hashwrite_u8(f
, ctx
->num_commit_graphs_after
- 1);
1449 for (i
= 0; i
<= num_chunks
; i
++) {
1450 uint32_t chunk_write
[3];
1452 chunk_write
[0] = htonl(chunk_ids
[i
]);
1453 chunk_write
[1] = htonl(chunk_offsets
[i
] >> 32);
1454 chunk_write
[2] = htonl(chunk_offsets
[i
] & 0xffffffff);
1455 hashwrite(f
, chunk_write
, 12);
1458 if (ctx
->report_progress
) {
1459 strbuf_addf(&progress_title
,
1460 Q_("Writing out commit graph in %d pass",
1461 "Writing out commit graph in %d passes",
1464 ctx
->progress
= start_delayed_progress(
1466 num_chunks
* ctx
->commits
.nr
);
1468 write_graph_chunk_fanout(f
, ctx
);
1469 write_graph_chunk_oids(f
, hashsz
, ctx
);
1470 write_graph_chunk_data(f
, hashsz
, ctx
);
1471 if (ctx
->num_extra_edges
)
1472 write_graph_chunk_extra_edges(f
, ctx
);
1473 if (ctx
->num_commit_graphs_after
> 1 &&
1474 write_graph_chunk_base(f
, ctx
)) {
1477 stop_progress(&ctx
->progress
);
1478 strbuf_release(&progress_title
);
1480 if (ctx
->split
&& ctx
->base_graph_name
&& ctx
->num_commit_graphs_after
> 1) {
1481 char *new_base_hash
= xstrdup(oid_to_hex(&ctx
->new_base_graph
->oid
));
1482 char *new_base_name
= get_split_graph_filename(ctx
->new_base_graph
->odb
, new_base_hash
);
1484 free(ctx
->commit_graph_filenames_after
[ctx
->num_commit_graphs_after
- 2]);
1485 free(ctx
->commit_graph_hash_after
[ctx
->num_commit_graphs_after
- 2]);
1486 ctx
->commit_graph_filenames_after
[ctx
->num_commit_graphs_after
- 2] = new_base_name
;
1487 ctx
->commit_graph_hash_after
[ctx
->num_commit_graphs_after
- 2] = new_base_hash
;
1490 close_commit_graph(ctx
->r
->objects
);
1491 finalize_hashfile(f
, file_hash
.hash
, CSUM_HASH_IN_STREAM
| CSUM_FSYNC
);
1494 FILE *chainf
= fdopen_lock_file(&lk
, "w");
1495 char *final_graph_name
;
1501 error(_("unable to open commit-graph chain file"));
1505 if (ctx
->base_graph_name
) {
1507 int idx
= ctx
->num_commit_graphs_after
- 1;
1508 if (ctx
->num_commit_graphs_after
> 1)
1511 dest
= ctx
->commit_graph_filenames_after
[idx
];
1513 if (strcmp(ctx
->base_graph_name
, dest
)) {
1514 result
= rename(ctx
->base_graph_name
, dest
);
1517 error(_("failed to rename base commit-graph file"));
1522 char *graph_name
= get_commit_graph_filename(ctx
->odb
);
1526 ctx
->commit_graph_hash_after
[ctx
->num_commit_graphs_after
- 1] = xstrdup(oid_to_hex(&file_hash
));
1527 final_graph_name
= get_split_graph_filename(ctx
->odb
,
1528 ctx
->commit_graph_hash_after
[ctx
->num_commit_graphs_after
- 1]);
1529 ctx
->commit_graph_filenames_after
[ctx
->num_commit_graphs_after
- 1] = final_graph_name
;
1531 result
= rename(ctx
->graph_name
, final_graph_name
);
1533 for (i
= 0; i
< ctx
->num_commit_graphs_after
; i
++)
1534 fprintf(lk
.tempfile
->fp
, "%s\n", ctx
->commit_graph_hash_after
[i
]);
1537 error(_("failed to rename temporary commit-graph file"));
1542 commit_lock_file(&lk
);
1547 static void split_graph_merge_strategy(struct write_commit_graph_context
*ctx
)
1549 struct commit_graph
*g
;
1550 uint32_t num_commits
;
1551 enum commit_graph_split_flags flags
= COMMIT_GRAPH_SPLIT_UNSPECIFIED
;
1554 int max_commits
= 0;
1557 if (ctx
->split_opts
) {
1558 max_commits
= ctx
->split_opts
->max_commits
;
1560 if (ctx
->split_opts
->size_multiple
)
1561 size_mult
= ctx
->split_opts
->size_multiple
;
1563 flags
= ctx
->split_opts
->flags
;
1566 g
= ctx
->r
->objects
->commit_graph
;
1567 num_commits
= ctx
->commits
.nr
;
1568 if (flags
== COMMIT_GRAPH_SPLIT_REPLACE
)
1569 ctx
->num_commit_graphs_after
= 1;
1571 ctx
->num_commit_graphs_after
= ctx
->num_commit_graphs_before
+ 1;
1573 if (flags
!= COMMIT_GRAPH_SPLIT_MERGE_PROHIBITED
&&
1574 flags
!= COMMIT_GRAPH_SPLIT_REPLACE
) {
1575 while (g
&& (g
->num_commits
<= size_mult
* num_commits
||
1576 (max_commits
&& num_commits
> max_commits
))) {
1577 if (g
->odb
!= ctx
->odb
)
1580 num_commits
+= g
->num_commits
;
1583 ctx
->num_commit_graphs_after
--;
1587 if (flags
!= COMMIT_GRAPH_SPLIT_REPLACE
)
1588 ctx
->new_base_graph
= g
;
1589 else if (ctx
->num_commit_graphs_after
!= 1)
1590 BUG("split_graph_merge_strategy: num_commit_graphs_after "
1591 "should be 1 with --split=replace");
1593 if (ctx
->num_commit_graphs_after
== 2) {
1594 char *old_graph_name
= get_commit_graph_filename(g
->odb
);
1596 if (!strcmp(g
->filename
, old_graph_name
) &&
1597 g
->odb
!= ctx
->odb
) {
1598 ctx
->num_commit_graphs_after
= 1;
1599 ctx
->new_base_graph
= NULL
;
1602 free(old_graph_name
);
1605 CALLOC_ARRAY(ctx
->commit_graph_filenames_after
, ctx
->num_commit_graphs_after
);
1606 CALLOC_ARRAY(ctx
->commit_graph_hash_after
, ctx
->num_commit_graphs_after
);
1608 for (i
= 0; i
< ctx
->num_commit_graphs_after
&&
1609 i
< ctx
->num_commit_graphs_before
; i
++)
1610 ctx
->commit_graph_filenames_after
[i
] = xstrdup(ctx
->commit_graph_filenames_before
[i
]);
1612 i
= ctx
->num_commit_graphs_before
- 1;
1613 g
= ctx
->r
->objects
->commit_graph
;
1616 if (i
< ctx
->num_commit_graphs_after
)
1617 ctx
->commit_graph_hash_after
[i
] = xstrdup(oid_to_hex(&g
->oid
));
1624 static void merge_commit_graph(struct write_commit_graph_context
*ctx
,
1625 struct commit_graph
*g
)
1628 uint32_t offset
= g
->num_commits_in_base
;
1630 ALLOC_GROW(ctx
->commits
.list
, ctx
->commits
.nr
+ g
->num_commits
, ctx
->commits
.alloc
);
1632 for (i
= 0; i
< g
->num_commits
; i
++) {
1633 struct object_id oid
;
1634 struct commit
*result
;
1636 display_progress(ctx
->progress
, i
+ 1);
1638 load_oid_from_graph(g
, i
+ offset
, &oid
);
1640 /* only add commits if they still exist in the repo */
1641 result
= lookup_commit_reference_gently(ctx
->r
, &oid
, 1);
1644 ctx
->commits
.list
[ctx
->commits
.nr
] = result
;
1650 static int commit_compare(const void *_a
, const void *_b
)
1652 const struct commit
*a
= *(const struct commit
**)_a
;
1653 const struct commit
*b
= *(const struct commit
**)_b
;
1654 return oidcmp(&a
->object
.oid
, &b
->object
.oid
);
1657 static void sort_and_scan_merged_commits(struct write_commit_graph_context
*ctx
)
1661 if (ctx
->report_progress
)
1662 ctx
->progress
= start_delayed_progress(
1663 _("Scanning merged commits"),
1666 QSORT(ctx
->commits
.list
, ctx
->commits
.nr
, commit_compare
);
1668 ctx
->num_extra_edges
= 0;
1669 for (i
= 0; i
< ctx
->commits
.nr
; i
++) {
1670 display_progress(ctx
->progress
, i
);
1672 if (i
&& oideq(&ctx
->commits
.list
[i
- 1]->object
.oid
,
1673 &ctx
->commits
.list
[i
]->object
.oid
)) {
1674 die(_("unexpected duplicate commit id %s"),
1675 oid_to_hex(&ctx
->commits
.list
[i
]->object
.oid
));
1677 unsigned int num_parents
;
1679 num_parents
= commit_list_count(ctx
->commits
.list
[i
]->parents
);
1680 if (num_parents
> 2)
1681 ctx
->num_extra_edges
+= num_parents
- 1;
1685 stop_progress(&ctx
->progress
);
1688 static void merge_commit_graphs(struct write_commit_graph_context
*ctx
)
1690 struct commit_graph
*g
= ctx
->r
->objects
->commit_graph
;
1691 uint32_t current_graph_number
= ctx
->num_commit_graphs_before
;
1692 struct strbuf progress_title
= STRBUF_INIT
;
1694 while (g
&& current_graph_number
>= ctx
->num_commit_graphs_after
) {
1695 current_graph_number
--;
1697 if (ctx
->report_progress
) {
1698 strbuf_addstr(&progress_title
, _("Merging commit-graph"));
1699 ctx
->progress
= start_delayed_progress(progress_title
.buf
, 0);
1702 merge_commit_graph(ctx
, g
);
1703 stop_progress(&ctx
->progress
);
1704 strbuf_release(&progress_title
);
1710 ctx
->new_base_graph
= g
;
1711 ctx
->new_num_commits_in_base
= g
->num_commits
+ g
->num_commits_in_base
;
1714 if (ctx
->new_base_graph
)
1715 ctx
->base_graph_name
= xstrdup(ctx
->new_base_graph
->filename
);
1717 sort_and_scan_merged_commits(ctx
);
1720 static void mark_commit_graphs(struct write_commit_graph_context
*ctx
)
1723 time_t now
= time(NULL
);
1725 for (i
= ctx
->num_commit_graphs_after
- 1; i
< ctx
->num_commit_graphs_before
; i
++) {
1727 struct utimbuf updated_time
;
1729 stat(ctx
->commit_graph_filenames_before
[i
], &st
);
1731 updated_time
.actime
= st
.st_atime
;
1732 updated_time
.modtime
= now
;
1733 utime(ctx
->commit_graph_filenames_before
[i
], &updated_time
);
1737 static void expire_commit_graphs(struct write_commit_graph_context
*ctx
)
1739 struct strbuf path
= STRBUF_INIT
;
1743 timestamp_t expire_time
= time(NULL
);
1745 if (ctx
->split_opts
&& ctx
->split_opts
->expire_time
)
1746 expire_time
-= ctx
->split_opts
->expire_time
;
1748 char *chain_file_name
= get_chain_filename(ctx
->odb
);
1749 unlink(chain_file_name
);
1750 free(chain_file_name
);
1751 ctx
->num_commit_graphs_after
= 0;
1754 strbuf_addstr(&path
, ctx
->odb
->path
);
1755 strbuf_addstr(&path
, "/info/commit-graphs");
1756 dir
= opendir(path
.buf
);
1761 strbuf_addch(&path
, '/');
1762 dirnamelen
= path
.len
;
1763 while ((de
= readdir(dir
)) != NULL
) {
1765 uint32_t i
, found
= 0;
1767 strbuf_setlen(&path
, dirnamelen
);
1768 strbuf_addstr(&path
, de
->d_name
);
1770 stat(path
.buf
, &st
);
1772 if (st
.st_mtime
> expire_time
)
1774 if (path
.len
< 6 || strcmp(path
.buf
+ path
.len
- 6, ".graph"))
1777 for (i
= 0; i
< ctx
->num_commit_graphs_after
; i
++) {
1778 if (!strcmp(ctx
->commit_graph_filenames_after
[i
],
1790 strbuf_release(&path
);
1793 int write_commit_graph(struct object_directory
*odb
,
1794 struct string_list
*pack_indexes
,
1795 struct oidset
*commits
,
1796 enum commit_graph_write_flags flags
,
1797 const struct split_commit_graph_opts
*split_opts
)
1799 struct write_commit_graph_context
*ctx
;
1800 uint32_t i
, count_distinct
= 0;
1804 if (!commit_graph_compatible(the_repository
))
1807 ctx
= xcalloc(1, sizeof(struct write_commit_graph_context
));
1808 ctx
->r
= the_repository
;
1810 ctx
->append
= flags
& COMMIT_GRAPH_WRITE_APPEND
? 1 : 0;
1811 ctx
->report_progress
= flags
& COMMIT_GRAPH_WRITE_PROGRESS
? 1 : 0;
1812 ctx
->split
= flags
& COMMIT_GRAPH_WRITE_SPLIT
? 1 : 0;
1813 ctx
->check_oids
= flags
& COMMIT_GRAPH_WRITE_CHECK_OIDS
? 1 : 0;
1814 ctx
->split_opts
= split_opts
;
1817 struct commit_graph
*g
;
1818 prepare_commit_graph(ctx
->r
);
1820 g
= ctx
->r
->objects
->commit_graph
;
1823 ctx
->num_commit_graphs_before
++;
1827 if (ctx
->num_commit_graphs_before
) {
1828 ALLOC_ARRAY(ctx
->commit_graph_filenames_before
, ctx
->num_commit_graphs_before
);
1829 i
= ctx
->num_commit_graphs_before
;
1830 g
= ctx
->r
->objects
->commit_graph
;
1833 ctx
->commit_graph_filenames_before
[--i
] = xstrdup(g
->filename
);
1838 if (ctx
->split_opts
)
1839 replace
= ctx
->split_opts
->flags
& COMMIT_GRAPH_SPLIT_REPLACE
;
1842 ctx
->approx_nr_objects
= approximate_object_count();
1843 ctx
->oids
.alloc
= ctx
->approx_nr_objects
/ 32;
1845 if (ctx
->split
&& split_opts
&& ctx
->oids
.alloc
> split_opts
->max_commits
)
1846 ctx
->oids
.alloc
= split_opts
->max_commits
;
1849 prepare_commit_graph_one(ctx
->r
, ctx
->odb
);
1850 if (ctx
->r
->objects
->commit_graph
)
1851 ctx
->oids
.alloc
+= ctx
->r
->objects
->commit_graph
->num_commits
;
1854 if (ctx
->oids
.alloc
< 1024)
1855 ctx
->oids
.alloc
= 1024;
1856 ALLOC_ARRAY(ctx
->oids
.list
, ctx
->oids
.alloc
);
1858 if (ctx
->append
&& ctx
->r
->objects
->commit_graph
) {
1859 struct commit_graph
*g
= ctx
->r
->objects
->commit_graph
;
1860 for (i
= 0; i
< g
->num_commits
; i
++) {
1861 const unsigned char *hash
= g
->chunk_oid_lookup
+ g
->hash_len
* i
;
1862 hashcpy(ctx
->oids
.list
[ctx
->oids
.nr
++].hash
, hash
);
1867 if ((res
= fill_oids_from_packs(ctx
, pack_indexes
)))
1872 if ((res
= fill_oids_from_commits(ctx
, commits
)))
1876 if (!pack_indexes
&& !commits
)
1877 fill_oids_from_all_packs(ctx
);
1879 close_reachable(ctx
);
1881 count_distinct
= count_distinct_commits(ctx
);
1883 if (count_distinct
>= GRAPH_EDGE_LAST_MASK
) {
1884 error(_("the commit graph format cannot write %d commits"), count_distinct
);
1889 ctx
->commits
.alloc
= count_distinct
;
1890 ALLOC_ARRAY(ctx
->commits
.list
, ctx
->commits
.alloc
);
1892 copy_oids_to_commits(ctx
);
1894 if (ctx
->commits
.nr
>= GRAPH_EDGE_LAST_MASK
) {
1895 error(_("too many commits to write graph"));
1900 if (!ctx
->commits
.nr
&& !replace
)
1904 split_graph_merge_strategy(ctx
);
1907 merge_commit_graphs(ctx
);
1909 ctx
->num_commit_graphs_after
= 1;
1911 compute_generation_numbers(ctx
);
1913 res
= write_commit_graph_file(ctx
);
1916 mark_commit_graphs(ctx
);
1918 expire_commit_graphs(ctx
);
1921 free(ctx
->graph_name
);
1922 free(ctx
->commits
.list
);
1923 free(ctx
->oids
.list
);
1925 if (ctx
->commit_graph_filenames_after
) {
1926 for (i
= 0; i
< ctx
->num_commit_graphs_after
; i
++) {
1927 free(ctx
->commit_graph_filenames_after
[i
]);
1928 free(ctx
->commit_graph_hash_after
[i
]);
1931 for (i
= 0; i
< ctx
->num_commit_graphs_before
; i
++)
1932 free(ctx
->commit_graph_filenames_before
[i
]);
1934 free(ctx
->commit_graph_filenames_after
);
1935 free(ctx
->commit_graph_filenames_before
);
1936 free(ctx
->commit_graph_hash_after
);
1944 #define VERIFY_COMMIT_GRAPH_ERROR_HASH 2
1945 static int verify_commit_graph_error
;
1947 static void graph_report(const char *fmt
, ...)
1951 verify_commit_graph_error
= 1;
1953 vfprintf(stderr
, fmt
, ap
);
1954 fprintf(stderr
, "\n");
1958 #define GENERATION_ZERO_EXISTS 1
1959 #define GENERATION_NUMBER_EXISTS 2
1961 int verify_commit_graph(struct repository
*r
, struct commit_graph
*g
, int flags
)
1963 uint32_t i
, cur_fanout_pos
= 0;
1964 struct object_id prev_oid
, cur_oid
, checksum
;
1965 int generation_zero
= 0;
1968 struct progress
*progress
= NULL
;
1969 int local_error
= 0;
1972 graph_report("no commit-graph file loaded");
1976 verify_commit_graph_error
= verify_commit_graph_lite(g
);
1977 if (verify_commit_graph_error
)
1978 return verify_commit_graph_error
;
1980 devnull
= open("/dev/null", O_WRONLY
);
1981 f
= hashfd(devnull
, NULL
);
1982 hashwrite(f
, g
->data
, g
->data_len
- g
->hash_len
);
1983 finalize_hashfile(f
, checksum
.hash
, CSUM_CLOSE
);
1984 if (!hasheq(checksum
.hash
, g
->data
+ g
->data_len
- g
->hash_len
)) {
1985 graph_report(_("the commit-graph file has incorrect checksum and is likely corrupt"));
1986 verify_commit_graph_error
= VERIFY_COMMIT_GRAPH_ERROR_HASH
;
1989 for (i
= 0; i
< g
->num_commits
; i
++) {
1990 struct commit
*graph_commit
;
1992 hashcpy(cur_oid
.hash
, g
->chunk_oid_lookup
+ g
->hash_len
* i
);
1994 if (i
&& oidcmp(&prev_oid
, &cur_oid
) >= 0)
1995 graph_report(_("commit-graph has incorrect OID order: %s then %s"),
1996 oid_to_hex(&prev_oid
),
1997 oid_to_hex(&cur_oid
));
1999 oidcpy(&prev_oid
, &cur_oid
);
2001 while (cur_oid
.hash
[0] > cur_fanout_pos
) {
2002 uint32_t fanout_value
= get_be32(g
->chunk_oid_fanout
+ cur_fanout_pos
);
2004 if (i
!= fanout_value
)
2005 graph_report(_("commit-graph has incorrect fanout value: fanout[%d] = %u != %u"),
2006 cur_fanout_pos
, fanout_value
, i
);
2010 graph_commit
= lookup_commit(r
, &cur_oid
);
2011 if (!parse_commit_in_graph_one(r
, g
, graph_commit
))
2012 graph_report(_("failed to parse commit %s from commit-graph"),
2013 oid_to_hex(&cur_oid
));
2016 while (cur_fanout_pos
< 256) {
2017 uint32_t fanout_value
= get_be32(g
->chunk_oid_fanout
+ cur_fanout_pos
);
2019 if (g
->num_commits
!= fanout_value
)
2020 graph_report(_("commit-graph has incorrect fanout value: fanout[%d] = %u != %u"),
2021 cur_fanout_pos
, fanout_value
, i
);
2026 if (verify_commit_graph_error
& ~VERIFY_COMMIT_GRAPH_ERROR_HASH
)
2027 return verify_commit_graph_error
;
2029 if (flags
& COMMIT_GRAPH_WRITE_PROGRESS
)
2030 progress
= start_progress(_("Verifying commits in commit graph"),
2033 for (i
= 0; i
< g
->num_commits
; i
++) {
2034 struct commit
*graph_commit
, *odb_commit
;
2035 struct commit_list
*graph_parents
, *odb_parents
;
2036 uint32_t max_generation
= 0;
2038 display_progress(progress
, i
+ 1);
2039 hashcpy(cur_oid
.hash
, g
->chunk_oid_lookup
+ g
->hash_len
* i
);
2041 graph_commit
= lookup_commit(r
, &cur_oid
);
2042 odb_commit
= (struct commit
*)create_object(r
, &cur_oid
, alloc_commit_node(r
));
2043 if (parse_commit_internal(odb_commit
, 0, 0)) {
2044 graph_report(_("failed to parse commit %s from object database for commit-graph"),
2045 oid_to_hex(&cur_oid
));
2049 if (!oideq(&get_commit_tree_in_graph_one(r
, g
, graph_commit
)->object
.oid
,
2050 get_commit_tree_oid(odb_commit
)))
2051 graph_report(_("root tree OID for commit %s in commit-graph is %s != %s"),
2052 oid_to_hex(&cur_oid
),
2053 oid_to_hex(get_commit_tree_oid(graph_commit
)),
2054 oid_to_hex(get_commit_tree_oid(odb_commit
)));
2056 graph_parents
= graph_commit
->parents
;
2057 odb_parents
= odb_commit
->parents
;
2059 while (graph_parents
) {
2060 if (odb_parents
== NULL
) {
2061 graph_report(_("commit-graph parent list for commit %s is too long"),
2062 oid_to_hex(&cur_oid
));
2066 /* parse parent in case it is in a base graph */
2067 parse_commit_in_graph_one(r
, g
, graph_parents
->item
);
2069 if (!oideq(&graph_parents
->item
->object
.oid
, &odb_parents
->item
->object
.oid
))
2070 graph_report(_("commit-graph parent for %s is %s != %s"),
2071 oid_to_hex(&cur_oid
),
2072 oid_to_hex(&graph_parents
->item
->object
.oid
),
2073 oid_to_hex(&odb_parents
->item
->object
.oid
));
2075 if (graph_parents
->item
->generation
> max_generation
)
2076 max_generation
= graph_parents
->item
->generation
;
2078 graph_parents
= graph_parents
->next
;
2079 odb_parents
= odb_parents
->next
;
2082 if (odb_parents
!= NULL
)
2083 graph_report(_("commit-graph parent list for commit %s terminates early"),
2084 oid_to_hex(&cur_oid
));
2086 if (!graph_commit
->generation
) {
2087 if (generation_zero
== GENERATION_NUMBER_EXISTS
)
2088 graph_report(_("commit-graph has generation number zero for commit %s, but non-zero elsewhere"),
2089 oid_to_hex(&cur_oid
));
2090 generation_zero
= GENERATION_ZERO_EXISTS
;
2091 } else if (generation_zero
== GENERATION_ZERO_EXISTS
)
2092 graph_report(_("commit-graph has non-zero generation number for commit %s, but zero elsewhere"),
2093 oid_to_hex(&cur_oid
));
2095 if (generation_zero
== GENERATION_ZERO_EXISTS
)
2099 * If one of our parents has generation GENERATION_NUMBER_MAX, then
2100 * our generation is also GENERATION_NUMBER_MAX. Decrement to avoid
2101 * extra logic in the following condition.
2103 if (max_generation
== GENERATION_NUMBER_MAX
)
2106 if (graph_commit
->generation
!= max_generation
+ 1)
2107 graph_report(_("commit-graph generation for commit %s is %u != %u"),
2108 oid_to_hex(&cur_oid
),
2109 graph_commit
->generation
,
2110 max_generation
+ 1);
2112 if (graph_commit
->date
!= odb_commit
->date
)
2113 graph_report(_("commit date for commit %s in commit-graph is %"PRItime
" != %"PRItime
),
2114 oid_to_hex(&cur_oid
),
2118 stop_progress(&progress
);
2120 local_error
= verify_commit_graph_error
;
2122 if (!(flags
& COMMIT_GRAPH_VERIFY_SHALLOW
) && g
->base_graph
)
2123 local_error
|= verify_commit_graph(r
, g
->base_graph
, flags
);
2128 void free_commit_graph(struct commit_graph
*g
)
2132 if (g
->graph_fd
>= 0) {
2133 munmap((void *)g
->data
, g
->data_len
);
2141 void disable_commit_graph(struct repository
*r
)
2143 r
->commit_graph_disabled
= 1;