4 #include "git-compat-util.h"
12 #include "sha1-lookup.h"
13 #include "commit-graph.h"
14 #include "object-store.h"
17 #define GRAPH_SIGNATURE 0x43475048 /* "CGPH" */
18 #define GRAPH_CHUNKID_OIDFANOUT 0x4f494446 /* "OIDF" */
19 #define GRAPH_CHUNKID_OIDLOOKUP 0x4f49444c /* "OIDL" */
20 #define GRAPH_CHUNKID_DATA 0x43444154 /* "CDAT" */
21 #define GRAPH_CHUNKID_LARGEEDGES 0x45444745 /* "EDGE" */
23 #define GRAPH_DATA_WIDTH 36
25 #define GRAPH_VERSION_1 0x1
26 #define GRAPH_VERSION GRAPH_VERSION_1
28 #define GRAPH_OID_VERSION_SHA1 1
29 #define GRAPH_OID_LEN_SHA1 GIT_SHA1_RAWSZ
30 #define GRAPH_OID_VERSION GRAPH_OID_VERSION_SHA1
31 #define GRAPH_OID_LEN GRAPH_OID_LEN_SHA1
33 #define GRAPH_OCTOPUS_EDGES_NEEDED 0x80000000
34 #define GRAPH_PARENT_MISSING 0x7fffffff
35 #define GRAPH_EDGE_LAST_MASK 0x7fffffff
36 #define GRAPH_PARENT_NONE 0x70000000
38 #define GRAPH_LAST_EDGE 0x80000000
40 #define GRAPH_HEADER_SIZE 8
41 #define GRAPH_FANOUT_SIZE (4 * 256)
42 #define GRAPH_CHUNKLOOKUP_WIDTH 12
43 #define GRAPH_MIN_SIZE (GRAPH_HEADER_SIZE + 4 * GRAPH_CHUNKLOOKUP_WIDTH \
44 + GRAPH_FANOUT_SIZE + GRAPH_OID_LEN)
46 char *get_commit_graph_filename(const char *obj_dir
)
48 return xstrfmt("%s/info/commit-graph", obj_dir
);
51 static struct commit_graph
*alloc_commit_graph(void)
53 struct commit_graph
*g
= xcalloc(1, sizeof(*g
));
59 struct commit_graph
*load_commit_graph_one(const char *graph_file
)
62 const unsigned char *data
, *chunk_lookup
;
66 struct commit_graph
*graph
;
67 int fd
= git_open(graph_file
);
68 uint64_t last_chunk_offset
;
69 uint32_t last_chunk_id
;
70 uint32_t graph_signature
;
71 unsigned char graph_version
, hash_version
;
79 graph_size
= xsize_t(st
.st_size
);
81 if (graph_size
< GRAPH_MIN_SIZE
) {
83 die("graph file %s is too small", graph_file
);
85 graph_map
= xmmap(NULL
, graph_size
, PROT_READ
, MAP_PRIVATE
, fd
, 0);
86 data
= (const unsigned char *)graph_map
;
88 graph_signature
= get_be32(data
);
89 if (graph_signature
!= GRAPH_SIGNATURE
) {
90 error("graph signature %X does not match signature %X",
91 graph_signature
, GRAPH_SIGNATURE
);
95 graph_version
= *(unsigned char*)(data
+ 4);
96 if (graph_version
!= GRAPH_VERSION
) {
97 error("graph version %X does not match version %X",
98 graph_version
, GRAPH_VERSION
);
102 hash_version
= *(unsigned char*)(data
+ 5);
103 if (hash_version
!= GRAPH_OID_VERSION
) {
104 error("hash version %X does not match version %X",
105 hash_version
, GRAPH_OID_VERSION
);
109 graph
= alloc_commit_graph();
111 graph
->hash_len
= GRAPH_OID_LEN
;
112 graph
->num_chunks
= *(unsigned char*)(data
+ 6);
113 graph
->graph_fd
= fd
;
114 graph
->data
= graph_map
;
115 graph
->data_len
= graph_size
;
118 last_chunk_offset
= 8;
119 chunk_lookup
= data
+ 8;
120 for (i
= 0; i
< graph
->num_chunks
; i
++) {
121 uint32_t chunk_id
= get_be32(chunk_lookup
+ 0);
122 uint64_t chunk_offset
= get_be64(chunk_lookup
+ 4);
123 int chunk_repeated
= 0;
125 chunk_lookup
+= GRAPH_CHUNKLOOKUP_WIDTH
;
127 if (chunk_offset
> graph_size
- GIT_MAX_RAWSZ
) {
128 error("improper chunk offset %08x%08x", (uint32_t)(chunk_offset
>> 32),
129 (uint32_t)chunk_offset
);
134 case GRAPH_CHUNKID_OIDFANOUT
:
135 if (graph
->chunk_oid_fanout
)
138 graph
->chunk_oid_fanout
= (uint32_t*)(data
+ chunk_offset
);
141 case GRAPH_CHUNKID_OIDLOOKUP
:
142 if (graph
->chunk_oid_lookup
)
145 graph
->chunk_oid_lookup
= data
+ chunk_offset
;
148 case GRAPH_CHUNKID_DATA
:
149 if (graph
->chunk_commit_data
)
152 graph
->chunk_commit_data
= data
+ chunk_offset
;
155 case GRAPH_CHUNKID_LARGEEDGES
:
156 if (graph
->chunk_large_edges
)
159 graph
->chunk_large_edges
= data
+ chunk_offset
;
163 if (chunk_repeated
) {
164 error("chunk id %08x appears multiple times", chunk_id
);
168 if (last_chunk_id
== GRAPH_CHUNKID_OIDLOOKUP
)
170 graph
->num_commits
= (chunk_offset
- last_chunk_offset
)
174 last_chunk_id
= chunk_id
;
175 last_chunk_offset
= chunk_offset
;
181 munmap(graph_map
, graph_size
);
186 static void prepare_commit_graph_one(struct repository
*r
, const char *obj_dir
)
190 if (r
->objects
->commit_graph
)
193 graph_name
= get_commit_graph_filename(obj_dir
);
194 r
->objects
->commit_graph
=
195 load_commit_graph_one(graph_name
);
197 FREE_AND_NULL(graph_name
);
201 * Return 1 if commit_graph is non-NULL, and 0 otherwise.
203 * On the first invocation, this function attemps to load the commit
204 * graph if the_repository is configured to have one.
206 static int prepare_commit_graph(struct repository
*r
)
208 struct alternate_object_database
*alt
;
212 if (r
->objects
->commit_graph_attempted
)
213 return !!r
->objects
->commit_graph
;
214 r
->objects
->commit_graph_attempted
= 1;
216 if (repo_config_get_bool(r
, "core.commitgraph", &config_value
) ||
219 * This repository is not configured to use commit graphs, so
220 * do not load one. (But report commit_graph_attempted anyway
221 * so that commit graph loading is not attempted again for this
226 obj_dir
= r
->objects
->objectdir
;
227 prepare_commit_graph_one(r
, obj_dir
);
229 for (alt
= r
->objects
->alt_odb_list
;
230 !r
->objects
->commit_graph
&& alt
;
232 prepare_commit_graph_one(r
, alt
->path
);
233 return !!r
->objects
->commit_graph
;
236 int generation_numbers_enabled(struct repository
*r
)
238 uint32_t first_generation
;
239 struct commit_graph
*g
;
240 if (!prepare_commit_graph(r
))
243 g
= r
->objects
->commit_graph
;
248 first_generation
= get_be32(g
->chunk_commit_data
+
249 g
->hash_len
+ 8) >> 2;
251 return !!first_generation
;
254 static void close_commit_graph(void)
256 free_commit_graph(the_repository
->objects
->commit_graph
);
257 the_repository
->objects
->commit_graph
= NULL
;
260 static int bsearch_graph(struct commit_graph
*g
, struct object_id
*oid
, uint32_t *pos
)
262 return bsearch_hash(oid
->hash
, g
->chunk_oid_fanout
,
263 g
->chunk_oid_lookup
, g
->hash_len
, pos
);
266 static struct commit_list
**insert_parent_or_die(struct commit_graph
*g
,
268 struct commit_list
**pptr
)
271 struct object_id oid
;
273 if (pos
>= g
->num_commits
)
274 die("invalid parent position %"PRIu64
, pos
);
276 hashcpy(oid
.hash
, g
->chunk_oid_lookup
+ g
->hash_len
* pos
);
277 c
= lookup_commit(the_repository
, &oid
);
279 die("could not find commit %s", oid_to_hex(&oid
));
281 return &commit_list_insert(c
, pptr
)->next
;
284 static void fill_commit_graph_info(struct commit
*item
, struct commit_graph
*g
, uint32_t pos
)
286 const unsigned char *commit_data
= g
->chunk_commit_data
+ GRAPH_DATA_WIDTH
* pos
;
287 item
->graph_pos
= pos
;
288 item
->generation
= get_be32(commit_data
+ g
->hash_len
+ 8) >> 2;
291 static int fill_commit_in_graph(struct commit
*item
, struct commit_graph
*g
, uint32_t pos
)
294 uint32_t *parent_data_ptr
;
295 uint64_t date_low
, date_high
;
296 struct commit_list
**pptr
;
297 const unsigned char *commit_data
= g
->chunk_commit_data
+ (g
->hash_len
+ 16) * pos
;
299 item
->object
.parsed
= 1;
300 item
->graph_pos
= pos
;
302 item
->maybe_tree
= NULL
;
304 date_high
= get_be32(commit_data
+ g
->hash_len
+ 8) & 0x3;
305 date_low
= get_be32(commit_data
+ g
->hash_len
+ 12);
306 item
->date
= (timestamp_t
)((date_high
<< 32) | date_low
);
308 item
->generation
= get_be32(commit_data
+ g
->hash_len
+ 8) >> 2;
310 pptr
= &item
->parents
;
312 edge_value
= get_be32(commit_data
+ g
->hash_len
);
313 if (edge_value
== GRAPH_PARENT_NONE
)
315 pptr
= insert_parent_or_die(g
, edge_value
, pptr
);
317 edge_value
= get_be32(commit_data
+ g
->hash_len
+ 4);
318 if (edge_value
== GRAPH_PARENT_NONE
)
320 if (!(edge_value
& GRAPH_OCTOPUS_EDGES_NEEDED
)) {
321 pptr
= insert_parent_or_die(g
, edge_value
, pptr
);
325 parent_data_ptr
= (uint32_t*)(g
->chunk_large_edges
+
326 4 * (uint64_t)(edge_value
& GRAPH_EDGE_LAST_MASK
));
328 edge_value
= get_be32(parent_data_ptr
);
329 pptr
= insert_parent_or_die(g
,
330 edge_value
& GRAPH_EDGE_LAST_MASK
,
333 } while (!(edge_value
& GRAPH_LAST_EDGE
));
338 static int find_commit_in_graph(struct commit
*item
, struct commit_graph
*g
, uint32_t *pos
)
340 if (item
->graph_pos
!= COMMIT_NOT_FROM_GRAPH
) {
341 *pos
= item
->graph_pos
;
344 return bsearch_graph(g
, &(item
->object
.oid
), pos
);
348 static int parse_commit_in_graph_one(struct commit_graph
*g
, struct commit
*item
)
352 if (item
->object
.parsed
)
355 if (find_commit_in_graph(item
, g
, &pos
))
356 return fill_commit_in_graph(item
, g
, pos
);
361 int parse_commit_in_graph(struct repository
*r
, struct commit
*item
)
363 if (!prepare_commit_graph(r
))
365 return parse_commit_in_graph_one(r
->objects
->commit_graph
, item
);
368 void load_commit_graph_info(struct repository
*r
, struct commit
*item
)
371 if (!prepare_commit_graph(r
))
373 if (find_commit_in_graph(item
, r
->objects
->commit_graph
, &pos
))
374 fill_commit_graph_info(item
, r
->objects
->commit_graph
, pos
);
377 static struct tree
*load_tree_for_commit(struct commit_graph
*g
, struct commit
*c
)
379 struct object_id oid
;
380 const unsigned char *commit_data
= g
->chunk_commit_data
+
381 GRAPH_DATA_WIDTH
* (c
->graph_pos
);
383 hashcpy(oid
.hash
, commit_data
);
384 c
->maybe_tree
= lookup_tree(the_repository
, &oid
);
386 return c
->maybe_tree
;
389 static struct tree
*get_commit_tree_in_graph_one(struct commit_graph
*g
,
390 const struct commit
*c
)
393 return c
->maybe_tree
;
394 if (c
->graph_pos
== COMMIT_NOT_FROM_GRAPH
)
395 BUG("get_commit_tree_in_graph_one called from non-commit-graph commit");
397 return load_tree_for_commit(g
, (struct commit
*)c
);
400 struct tree
*get_commit_tree_in_graph(struct repository
*r
, const struct commit
*c
)
402 return get_commit_tree_in_graph_one(r
->objects
->commit_graph
, c
);
405 static void write_graph_chunk_fanout(struct hashfile
*f
,
406 struct commit
**commits
,
410 struct commit
**list
= commits
;
413 * Write the first-level table (the list is sorted,
414 * but we use a 256-entry lookup to be able to avoid
415 * having to do eight extra binary search iterations).
417 for (i
= 0; i
< 256; i
++) {
418 while (count
< nr_commits
) {
419 if ((*list
)->object
.oid
.hash
[0] != i
)
425 hashwrite_be32(f
, count
);
429 static void write_graph_chunk_oids(struct hashfile
*f
, int hash_len
,
430 struct commit
**commits
, int nr_commits
)
432 struct commit
**list
= commits
;
434 for (count
= 0; count
< nr_commits
; count
++, list
++)
435 hashwrite(f
, (*list
)->object
.oid
.hash
, (int)hash_len
);
438 static const unsigned char *commit_to_sha1(size_t index
, void *table
)
440 struct commit
**commits
= table
;
441 return commits
[index
]->object
.oid
.hash
;
444 static void write_graph_chunk_data(struct hashfile
*f
, int hash_len
,
445 struct commit
**commits
, int nr_commits
)
447 struct commit
**list
= commits
;
448 struct commit
**last
= commits
+ nr_commits
;
449 uint32_t num_extra_edges
= 0;
451 while (list
< last
) {
452 struct commit_list
*parent
;
454 uint32_t packedDate
[2];
457 hashwrite(f
, get_commit_tree_oid(*list
)->hash
, hash_len
);
459 parent
= (*list
)->parents
;
462 edge_value
= GRAPH_PARENT_NONE
;
464 edge_value
= sha1_pos(parent
->item
->object
.oid
.hash
,
470 edge_value
= GRAPH_PARENT_MISSING
;
473 hashwrite_be32(f
, edge_value
);
476 parent
= parent
->next
;
479 edge_value
= GRAPH_PARENT_NONE
;
480 else if (parent
->next
)
481 edge_value
= GRAPH_OCTOPUS_EDGES_NEEDED
| num_extra_edges
;
483 edge_value
= sha1_pos(parent
->item
->object
.oid
.hash
,
488 edge_value
= GRAPH_PARENT_MISSING
;
491 hashwrite_be32(f
, edge_value
);
493 if (edge_value
& GRAPH_OCTOPUS_EDGES_NEEDED
) {
496 parent
= parent
->next
;
500 if (sizeof((*list
)->date
) > 4)
501 packedDate
[0] = htonl(((*list
)->date
>> 32) & 0x3);
505 packedDate
[0] |= htonl((*list
)->generation
<< 2);
507 packedDate
[1] = htonl((*list
)->date
);
508 hashwrite(f
, packedDate
, 8);
514 static void write_graph_chunk_large_edges(struct hashfile
*f
,
515 struct commit
**commits
,
518 struct commit
**list
= commits
;
519 struct commit
**last
= commits
+ nr_commits
;
520 struct commit_list
*parent
;
522 while (list
< last
) {
524 for (parent
= (*list
)->parents
; num_parents
< 3 && parent
;
525 parent
= parent
->next
)
528 if (num_parents
<= 2) {
533 /* Since num_parents > 2, this initializer is safe. */
534 for (parent
= (*list
)->parents
->next
; parent
; parent
= parent
->next
) {
535 int edge_value
= sha1_pos(parent
->item
->object
.oid
.hash
,
541 edge_value
= GRAPH_PARENT_MISSING
;
542 else if (!parent
->next
)
543 edge_value
|= GRAPH_LAST_EDGE
;
545 hashwrite_be32(f
, edge_value
);
552 static int commit_compare(const void *_a
, const void *_b
)
554 const struct object_id
*a
= (const struct object_id
*)_a
;
555 const struct object_id
*b
= (const struct object_id
*)_b
;
559 struct packed_commit_list
{
560 struct commit
**list
;
565 struct packed_oid_list
{
566 struct object_id
*list
;
571 static int add_packed_commits(const struct object_id
*oid
,
572 struct packed_git
*pack
,
576 struct packed_oid_list
*list
= (struct packed_oid_list
*)data
;
577 enum object_type type
;
578 off_t offset
= nth_packed_object_offset(pack
, pos
);
579 struct object_info oi
= OBJECT_INFO_INIT
;
582 if (packed_object_info(the_repository
, pack
, offset
, &oi
) < 0)
583 die("unable to get type of object %s", oid_to_hex(oid
));
585 if (type
!= OBJ_COMMIT
)
588 ALLOC_GROW(list
->list
, list
->nr
+ 1, list
->alloc
);
589 oidcpy(&(list
->list
[list
->nr
]), oid
);
595 static void add_missing_parents(struct packed_oid_list
*oids
, struct commit
*commit
)
597 struct commit_list
*parent
;
598 for (parent
= commit
->parents
; parent
; parent
= parent
->next
) {
599 if (!(parent
->item
->object
.flags
& UNINTERESTING
)) {
600 ALLOC_GROW(oids
->list
, oids
->nr
+ 1, oids
->alloc
);
601 oidcpy(&oids
->list
[oids
->nr
], &(parent
->item
->object
.oid
));
603 parent
->item
->object
.flags
|= UNINTERESTING
;
608 static void close_reachable(struct packed_oid_list
*oids
)
611 struct commit
*commit
;
613 for (i
= 0; i
< oids
->nr
; i
++) {
614 commit
= lookup_commit(the_repository
, &oids
->list
[i
]);
616 commit
->object
.flags
|= UNINTERESTING
;
620 * As this loop runs, oids->nr may grow, but not more
621 * than the number of missing commits in the reachable
624 for (i
= 0; i
< oids
->nr
; i
++) {
625 commit
= lookup_commit(the_repository
, &oids
->list
[i
]);
627 if (commit
&& !parse_commit(commit
))
628 add_missing_parents(oids
, commit
);
631 for (i
= 0; i
< oids
->nr
; i
++) {
632 commit
= lookup_commit(the_repository
, &oids
->list
[i
]);
635 commit
->object
.flags
&= ~UNINTERESTING
;
639 static void compute_generation_numbers(struct packed_commit_list
* commits
)
642 struct commit_list
*list
= NULL
;
644 for (i
= 0; i
< commits
->nr
; i
++) {
645 if (commits
->list
[i
]->generation
!= GENERATION_NUMBER_INFINITY
&&
646 commits
->list
[i
]->generation
!= GENERATION_NUMBER_ZERO
)
649 commit_list_insert(commits
->list
[i
], &list
);
651 struct commit
*current
= list
->item
;
652 struct commit_list
*parent
;
653 int all_parents_computed
= 1;
654 uint32_t max_generation
= 0;
656 for (parent
= current
->parents
; parent
; parent
= parent
->next
) {
657 if (parent
->item
->generation
== GENERATION_NUMBER_INFINITY
||
658 parent
->item
->generation
== GENERATION_NUMBER_ZERO
) {
659 all_parents_computed
= 0;
660 commit_list_insert(parent
->item
, &list
);
662 } else if (parent
->item
->generation
> max_generation
) {
663 max_generation
= parent
->item
->generation
;
667 if (all_parents_computed
) {
668 current
->generation
= max_generation
+ 1;
671 if (current
->generation
> GENERATION_NUMBER_MAX
)
672 current
->generation
= GENERATION_NUMBER_MAX
;
678 static int add_ref_to_list(const char *refname
,
679 const struct object_id
*oid
,
680 int flags
, void *cb_data
)
682 struct string_list
*list
= (struct string_list
*)cb_data
;
684 string_list_append(list
, oid_to_hex(oid
));
688 void write_commit_graph_reachable(const char *obj_dir
, int append
)
690 struct string_list list
;
692 string_list_init(&list
, 1);
693 for_each_ref(add_ref_to_list
, &list
);
694 write_commit_graph(obj_dir
, NULL
, &list
, append
);
697 void write_commit_graph(const char *obj_dir
,
698 struct string_list
*pack_indexes
,
699 struct string_list
*commit_hex
,
702 struct packed_oid_list oids
;
703 struct packed_commit_list commits
;
705 uint32_t i
, count_distinct
= 0;
707 struct lock_file lk
= LOCK_INIT
;
708 uint32_t chunk_ids
[5];
709 uint64_t chunk_offsets
[5];
712 struct commit_list
*parent
;
715 oids
.alloc
= approximate_object_count() / 4;
718 prepare_commit_graph_one(the_repository
, obj_dir
);
719 if (the_repository
->objects
->commit_graph
)
720 oids
.alloc
+= the_repository
->objects
->commit_graph
->num_commits
;
723 if (oids
.alloc
< 1024)
725 ALLOC_ARRAY(oids
.list
, oids
.alloc
);
727 if (append
&& the_repository
->objects
->commit_graph
) {
728 struct commit_graph
*commit_graph
=
729 the_repository
->objects
->commit_graph
;
730 for (i
= 0; i
< commit_graph
->num_commits
; i
++) {
731 const unsigned char *hash
= commit_graph
->chunk_oid_lookup
+
732 commit_graph
->hash_len
* i
;
733 hashcpy(oids
.list
[oids
.nr
++].hash
, hash
);
738 struct strbuf packname
= STRBUF_INIT
;
740 strbuf_addf(&packname
, "%s/pack/", obj_dir
);
741 dirlen
= packname
.len
;
742 for (i
= 0; i
< pack_indexes
->nr
; i
++) {
743 struct packed_git
*p
;
744 strbuf_setlen(&packname
, dirlen
);
745 strbuf_addstr(&packname
, pack_indexes
->items
[i
].string
);
746 p
= add_packed_git(packname
.buf
, packname
.len
, 1);
748 die("error adding pack %s", packname
.buf
);
749 if (open_pack_index(p
))
750 die("error opening index for %s", packname
.buf
);
751 for_each_object_in_pack(p
, add_packed_commits
, &oids
);
754 strbuf_release(&packname
);
758 for (i
= 0; i
< commit_hex
->nr
; i
++) {
760 struct object_id oid
;
761 struct commit
*result
;
763 if (commit_hex
->items
[i
].string
&&
764 parse_oid_hex(commit_hex
->items
[i
].string
, &oid
, &end
))
767 result
= lookup_commit_reference_gently(the_repository
, &oid
, 1);
770 ALLOC_GROW(oids
.list
, oids
.nr
+ 1, oids
.alloc
);
771 oidcpy(&oids
.list
[oids
.nr
], &(result
->object
.oid
));
777 if (!pack_indexes
&& !commit_hex
)
778 for_each_packed_object(add_packed_commits
, &oids
, 0);
780 close_reachable(&oids
);
782 QSORT(oids
.list
, oids
.nr
, commit_compare
);
785 for (i
= 1; i
< oids
.nr
; i
++) {
786 if (oidcmp(&oids
.list
[i
-1], &oids
.list
[i
]))
790 if (count_distinct
>= GRAPH_PARENT_MISSING
)
791 die(_("the commit graph format cannot write %d commits"), count_distinct
);
794 commits
.alloc
= count_distinct
;
795 ALLOC_ARRAY(commits
.list
, commits
.alloc
);
798 for (i
= 0; i
< oids
.nr
; i
++) {
800 if (i
> 0 && !oidcmp(&oids
.list
[i
-1], &oids
.list
[i
]))
803 commits
.list
[commits
.nr
] = lookup_commit(the_repository
, &oids
.list
[i
]);
804 parse_commit(commits
.list
[commits
.nr
]);
806 for (parent
= commits
.list
[commits
.nr
]->parents
;
807 parent
; parent
= parent
->next
)
811 num_extra_edges
+= num_parents
- 1;
815 num_chunks
= num_extra_edges
? 4 : 3;
817 if (commits
.nr
>= GRAPH_PARENT_MISSING
)
818 die(_("too many commits to write graph"));
820 compute_generation_numbers(&commits
);
822 graph_name
= get_commit_graph_filename(obj_dir
);
823 if (safe_create_leading_directories(graph_name
))
824 die_errno(_("unable to create leading directories of %s"),
827 hold_lock_file_for_update(&lk
, graph_name
, LOCK_DIE_ON_ERROR
);
828 f
= hashfd(lk
.tempfile
->fd
, lk
.tempfile
->filename
.buf
);
830 hashwrite_be32(f
, GRAPH_SIGNATURE
);
832 hashwrite_u8(f
, GRAPH_VERSION
);
833 hashwrite_u8(f
, GRAPH_OID_VERSION
);
834 hashwrite_u8(f
, num_chunks
);
835 hashwrite_u8(f
, 0); /* unused padding byte */
837 chunk_ids
[0] = GRAPH_CHUNKID_OIDFANOUT
;
838 chunk_ids
[1] = GRAPH_CHUNKID_OIDLOOKUP
;
839 chunk_ids
[2] = GRAPH_CHUNKID_DATA
;
841 chunk_ids
[3] = GRAPH_CHUNKID_LARGEEDGES
;
846 chunk_offsets
[0] = 8 + (num_chunks
+ 1) * GRAPH_CHUNKLOOKUP_WIDTH
;
847 chunk_offsets
[1] = chunk_offsets
[0] + GRAPH_FANOUT_SIZE
;
848 chunk_offsets
[2] = chunk_offsets
[1] + GRAPH_OID_LEN
* commits
.nr
;
849 chunk_offsets
[3] = chunk_offsets
[2] + (GRAPH_OID_LEN
+ 16) * commits
.nr
;
850 chunk_offsets
[4] = chunk_offsets
[3] + 4 * num_extra_edges
;
852 for (i
= 0; i
<= num_chunks
; i
++) {
853 uint32_t chunk_write
[3];
855 chunk_write
[0] = htonl(chunk_ids
[i
]);
856 chunk_write
[1] = htonl(chunk_offsets
[i
] >> 32);
857 chunk_write
[2] = htonl(chunk_offsets
[i
] & 0xffffffff);
858 hashwrite(f
, chunk_write
, 12);
861 write_graph_chunk_fanout(f
, commits
.list
, commits
.nr
);
862 write_graph_chunk_oids(f
, GRAPH_OID_LEN
, commits
.list
, commits
.nr
);
863 write_graph_chunk_data(f
, GRAPH_OID_LEN
, commits
.list
, commits
.nr
);
864 write_graph_chunk_large_edges(f
, commits
.list
, commits
.nr
);
866 close_commit_graph();
867 finalize_hashfile(f
, NULL
, CSUM_HASH_IN_STREAM
| CSUM_FSYNC
);
868 commit_lock_file(&lk
);
875 #define VERIFY_COMMIT_GRAPH_ERROR_HASH 2
876 static int verify_commit_graph_error
;
878 static void graph_report(const char *fmt
, ...)
882 verify_commit_graph_error
= 1;
884 vfprintf(stderr
, fmt
, ap
);
885 fprintf(stderr
, "\n");
889 #define GENERATION_ZERO_EXISTS 1
890 #define GENERATION_NUMBER_EXISTS 2
892 int verify_commit_graph(struct repository
*r
, struct commit_graph
*g
)
894 uint32_t i
, cur_fanout_pos
= 0;
895 struct object_id prev_oid
, cur_oid
, checksum
;
896 int generation_zero
= 0;
901 graph_report("no commit-graph file loaded");
905 verify_commit_graph_error
= 0;
907 if (!g
->chunk_oid_fanout
)
908 graph_report("commit-graph is missing the OID Fanout chunk");
909 if (!g
->chunk_oid_lookup
)
910 graph_report("commit-graph is missing the OID Lookup chunk");
911 if (!g
->chunk_commit_data
)
912 graph_report("commit-graph is missing the Commit Data chunk");
914 if (verify_commit_graph_error
)
915 return verify_commit_graph_error
;
917 devnull
= open("/dev/null", O_WRONLY
);
918 f
= hashfd(devnull
, NULL
);
919 hashwrite(f
, g
->data
, g
->data_len
- g
->hash_len
);
920 finalize_hashfile(f
, checksum
.hash
, CSUM_CLOSE
);
921 if (hashcmp(checksum
.hash
, g
->data
+ g
->data_len
- g
->hash_len
)) {
922 graph_report(_("the commit-graph file has incorrect checksum and is likely corrupt"));
923 verify_commit_graph_error
= VERIFY_COMMIT_GRAPH_ERROR_HASH
;
926 for (i
= 0; i
< g
->num_commits
; i
++) {
927 struct commit
*graph_commit
;
929 hashcpy(cur_oid
.hash
, g
->chunk_oid_lookup
+ g
->hash_len
* i
);
931 if (i
&& oidcmp(&prev_oid
, &cur_oid
) >= 0)
932 graph_report("commit-graph has incorrect OID order: %s then %s",
933 oid_to_hex(&prev_oid
),
934 oid_to_hex(&cur_oid
));
936 oidcpy(&prev_oid
, &cur_oid
);
938 while (cur_oid
.hash
[0] > cur_fanout_pos
) {
939 uint32_t fanout_value
= get_be32(g
->chunk_oid_fanout
+ cur_fanout_pos
);
941 if (i
!= fanout_value
)
942 graph_report("commit-graph has incorrect fanout value: fanout[%d] = %u != %u",
943 cur_fanout_pos
, fanout_value
, i
);
947 graph_commit
= lookup_commit(r
, &cur_oid
);
948 if (!parse_commit_in_graph_one(g
, graph_commit
))
949 graph_report("failed to parse %s from commit-graph",
950 oid_to_hex(&cur_oid
));
953 while (cur_fanout_pos
< 256) {
954 uint32_t fanout_value
= get_be32(g
->chunk_oid_fanout
+ cur_fanout_pos
);
956 if (g
->num_commits
!= fanout_value
)
957 graph_report("commit-graph has incorrect fanout value: fanout[%d] = %u != %u",
958 cur_fanout_pos
, fanout_value
, i
);
963 if (verify_commit_graph_error
& ~VERIFY_COMMIT_GRAPH_ERROR_HASH
)
964 return verify_commit_graph_error
;
966 for (i
= 0; i
< g
->num_commits
; i
++) {
967 struct commit
*graph_commit
, *odb_commit
;
968 struct commit_list
*graph_parents
, *odb_parents
;
969 uint32_t max_generation
= 0;
971 hashcpy(cur_oid
.hash
, g
->chunk_oid_lookup
+ g
->hash_len
* i
);
973 graph_commit
= lookup_commit(r
, &cur_oid
);
974 odb_commit
= (struct commit
*)create_object(r
, cur_oid
.hash
, alloc_commit_node(r
));
975 if (parse_commit_internal(odb_commit
, 0, 0)) {
976 graph_report("failed to parse %s from object database",
977 oid_to_hex(&cur_oid
));
981 if (oidcmp(&get_commit_tree_in_graph_one(g
, graph_commit
)->object
.oid
,
982 get_commit_tree_oid(odb_commit
)))
983 graph_report("root tree OID for commit %s in commit-graph is %s != %s",
984 oid_to_hex(&cur_oid
),
985 oid_to_hex(get_commit_tree_oid(graph_commit
)),
986 oid_to_hex(get_commit_tree_oid(odb_commit
)));
988 graph_parents
= graph_commit
->parents
;
989 odb_parents
= odb_commit
->parents
;
991 while (graph_parents
) {
992 if (odb_parents
== NULL
) {
993 graph_report("commit-graph parent list for commit %s is too long",
994 oid_to_hex(&cur_oid
));
998 if (oidcmp(&graph_parents
->item
->object
.oid
, &odb_parents
->item
->object
.oid
))
999 graph_report("commit-graph parent for %s is %s != %s",
1000 oid_to_hex(&cur_oid
),
1001 oid_to_hex(&graph_parents
->item
->object
.oid
),
1002 oid_to_hex(&odb_parents
->item
->object
.oid
));
1004 if (graph_parents
->item
->generation
> max_generation
)
1005 max_generation
= graph_parents
->item
->generation
;
1007 graph_parents
= graph_parents
->next
;
1008 odb_parents
= odb_parents
->next
;
1011 if (odb_parents
!= NULL
)
1012 graph_report("commit-graph parent list for commit %s terminates early",
1013 oid_to_hex(&cur_oid
));
1015 if (!graph_commit
->generation
) {
1016 if (generation_zero
== GENERATION_NUMBER_EXISTS
)
1017 graph_report("commit-graph has generation number zero for commit %s, but non-zero elsewhere",
1018 oid_to_hex(&cur_oid
));
1019 generation_zero
= GENERATION_ZERO_EXISTS
;
1020 } else if (generation_zero
== GENERATION_ZERO_EXISTS
)
1021 graph_report("commit-graph has non-zero generation number for commit %s, but zero elsewhere",
1022 oid_to_hex(&cur_oid
));
1024 if (generation_zero
== GENERATION_ZERO_EXISTS
)
1028 * If one of our parents has generation GENERATION_NUMBER_MAX, then
1029 * our generation is also GENERATION_NUMBER_MAX. Decrement to avoid
1030 * extra logic in the following condition.
1032 if (max_generation
== GENERATION_NUMBER_MAX
)
1035 if (graph_commit
->generation
!= max_generation
+ 1)
1036 graph_report("commit-graph generation for commit %s is %u != %u",
1037 oid_to_hex(&cur_oid
),
1038 graph_commit
->generation
,
1039 max_generation
+ 1);
1041 if (graph_commit
->date
!= odb_commit
->date
)
1042 graph_report("commit date for commit %s in commit-graph is %"PRItime
" != %"PRItime
,
1043 oid_to_hex(&cur_oid
),
1048 return verify_commit_graph_error
;
1051 void free_commit_graph(struct commit_graph
*g
)
1055 if (g
->graph_fd
>= 0) {
1056 munmap((void *)g
->data
, g
->data_len
);