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_LARGEEDGES 0x45444745 /* "EDGE" */
26 #define GRAPH_DATA_WIDTH (the_hash_algo->rawsz + 16)
28 #define GRAPH_VERSION_1 0x1
29 #define GRAPH_VERSION GRAPH_VERSION_1
31 #define GRAPH_OCTOPUS_EDGES_NEEDED 0x80000000
32 #define GRAPH_EDGE_LAST_MASK 0x7fffffff
33 #define GRAPH_PARENT_NONE 0x70000000
35 #define GRAPH_LAST_EDGE 0x80000000
37 #define GRAPH_HEADER_SIZE 8
38 #define GRAPH_FANOUT_SIZE (4 * 256)
39 #define GRAPH_CHUNKLOOKUP_WIDTH 12
40 #define GRAPH_MIN_SIZE (GRAPH_HEADER_SIZE + 4 * GRAPH_CHUNKLOOKUP_WIDTH \
41 + GRAPH_FANOUT_SIZE + the_hash_algo->rawsz)
43 char *get_commit_graph_filename(const char *obj_dir
)
45 return xstrfmt("%s/info/commit-graph", obj_dir
);
48 static uint8_t oid_version(void)
53 static struct commit_graph
*alloc_commit_graph(void)
55 struct commit_graph
*g
= xcalloc(1, sizeof(*g
));
61 extern int read_replace_refs
;
63 static int commit_graph_compatible(struct repository
*r
)
68 if (read_replace_refs
) {
69 prepare_replace_object(r
);
70 if (hashmap_get_size(&r
->objects
->replace_map
->map
))
74 prepare_commit_graft(r
);
75 if (r
->parsed_objects
&& r
->parsed_objects
->grafts_nr
)
77 if (is_repository_shallow(r
))
83 struct commit_graph
*load_commit_graph_one(const char *graph_file
)
86 const unsigned char *data
, *chunk_lookup
;
90 struct commit_graph
*graph
;
91 int fd
= git_open(graph_file
);
92 uint64_t last_chunk_offset
;
93 uint32_t last_chunk_id
;
94 uint32_t graph_signature
;
95 unsigned char graph_version
, hash_version
;
103 graph_size
= xsize_t(st
.st_size
);
105 if (graph_size
< GRAPH_MIN_SIZE
) {
107 die(_("graph file %s is too small"), graph_file
);
109 graph_map
= xmmap(NULL
, graph_size
, PROT_READ
, MAP_PRIVATE
, fd
, 0);
110 data
= (const unsigned char *)graph_map
;
112 graph_signature
= get_be32(data
);
113 if (graph_signature
!= GRAPH_SIGNATURE
) {
114 error(_("graph signature %X does not match signature %X"),
115 graph_signature
, GRAPH_SIGNATURE
);
119 graph_version
= *(unsigned char*)(data
+ 4);
120 if (graph_version
!= GRAPH_VERSION
) {
121 error(_("graph version %X does not match version %X"),
122 graph_version
, GRAPH_VERSION
);
126 hash_version
= *(unsigned char*)(data
+ 5);
127 if (hash_version
!= oid_version()) {
128 error(_("hash version %X does not match version %X"),
129 hash_version
, oid_version());
133 graph
= alloc_commit_graph();
135 graph
->hash_len
= the_hash_algo
->rawsz
;
136 graph
->num_chunks
= *(unsigned char*)(data
+ 6);
137 graph
->graph_fd
= fd
;
138 graph
->data
= graph_map
;
139 graph
->data_len
= graph_size
;
142 last_chunk_offset
= 8;
143 chunk_lookup
= data
+ 8;
144 for (i
= 0; i
< graph
->num_chunks
; i
++) {
145 uint32_t chunk_id
= get_be32(chunk_lookup
+ 0);
146 uint64_t chunk_offset
= get_be64(chunk_lookup
+ 4);
147 int chunk_repeated
= 0;
149 chunk_lookup
+= GRAPH_CHUNKLOOKUP_WIDTH
;
151 if (chunk_offset
> graph_size
- the_hash_algo
->rawsz
) {
152 error(_("improper chunk offset %08x%08x"), (uint32_t)(chunk_offset
>> 32),
153 (uint32_t)chunk_offset
);
158 case GRAPH_CHUNKID_OIDFANOUT
:
159 if (graph
->chunk_oid_fanout
)
162 graph
->chunk_oid_fanout
= (uint32_t*)(data
+ chunk_offset
);
165 case GRAPH_CHUNKID_OIDLOOKUP
:
166 if (graph
->chunk_oid_lookup
)
169 graph
->chunk_oid_lookup
= data
+ chunk_offset
;
172 case GRAPH_CHUNKID_DATA
:
173 if (graph
->chunk_commit_data
)
176 graph
->chunk_commit_data
= data
+ chunk_offset
;
179 case GRAPH_CHUNKID_LARGEEDGES
:
180 if (graph
->chunk_large_edges
)
183 graph
->chunk_large_edges
= data
+ chunk_offset
;
187 if (chunk_repeated
) {
188 error(_("chunk id %08x appears multiple times"), chunk_id
);
192 if (last_chunk_id
== GRAPH_CHUNKID_OIDLOOKUP
)
194 graph
->num_commits
= (chunk_offset
- last_chunk_offset
)
198 last_chunk_id
= chunk_id
;
199 last_chunk_offset
= chunk_offset
;
205 munmap(graph_map
, graph_size
);
210 static void prepare_commit_graph_one(struct repository
*r
, const char *obj_dir
)
214 if (r
->objects
->commit_graph
)
217 graph_name
= get_commit_graph_filename(obj_dir
);
218 r
->objects
->commit_graph
=
219 load_commit_graph_one(graph_name
);
221 FREE_AND_NULL(graph_name
);
225 * Return 1 if commit_graph is non-NULL, and 0 otherwise.
227 * On the first invocation, this function attemps to load the commit
228 * graph if the_repository is configured to have one.
230 static int prepare_commit_graph(struct repository
*r
)
232 struct object_directory
*odb
;
235 if (r
->objects
->commit_graph_attempted
)
236 return !!r
->objects
->commit_graph
;
237 r
->objects
->commit_graph_attempted
= 1;
239 if (!git_env_bool(GIT_TEST_COMMIT_GRAPH
, 0) &&
240 (repo_config_get_bool(r
, "core.commitgraph", &config_value
) ||
243 * This repository is not configured to use commit graphs, so
244 * do not load one. (But report commit_graph_attempted anyway
245 * so that commit graph loading is not attempted again for this
250 if (!commit_graph_compatible(r
))
254 for (odb
= r
->objects
->odb
;
255 !r
->objects
->commit_graph
&& odb
;
257 prepare_commit_graph_one(r
, odb
->path
);
258 return !!r
->objects
->commit_graph
;
261 int generation_numbers_enabled(struct repository
*r
)
263 uint32_t first_generation
;
264 struct commit_graph
*g
;
265 if (!prepare_commit_graph(r
))
268 g
= r
->objects
->commit_graph
;
273 first_generation
= get_be32(g
->chunk_commit_data
+
274 g
->hash_len
+ 8) >> 2;
276 return !!first_generation
;
279 void close_commit_graph(struct repository
*r
)
281 free_commit_graph(r
->objects
->commit_graph
);
282 r
->objects
->commit_graph
= NULL
;
285 static int bsearch_graph(struct commit_graph
*g
, struct object_id
*oid
, uint32_t *pos
)
287 return bsearch_hash(oid
->hash
, g
->chunk_oid_fanout
,
288 g
->chunk_oid_lookup
, g
->hash_len
, pos
);
291 static struct commit_list
**insert_parent_or_die(struct repository
*r
,
292 struct commit_graph
*g
,
294 struct commit_list
**pptr
)
297 struct object_id oid
;
299 if (pos
>= g
->num_commits
)
300 die("invalid parent position %"PRIu64
, pos
);
302 hashcpy(oid
.hash
, g
->chunk_oid_lookup
+ g
->hash_len
* pos
);
303 c
= lookup_commit(r
, &oid
);
305 die(_("could not find commit %s"), oid_to_hex(&oid
));
307 return &commit_list_insert(c
, pptr
)->next
;
310 static void fill_commit_graph_info(struct commit
*item
, struct commit_graph
*g
, uint32_t pos
)
312 const unsigned char *commit_data
= g
->chunk_commit_data
+ GRAPH_DATA_WIDTH
* pos
;
313 item
->graph_pos
= pos
;
314 item
->generation
= get_be32(commit_data
+ g
->hash_len
+ 8) >> 2;
317 static int fill_commit_in_graph(struct repository
*r
,
319 struct commit_graph
*g
, uint32_t pos
)
322 uint32_t *parent_data_ptr
;
323 uint64_t date_low
, date_high
;
324 struct commit_list
**pptr
;
325 const unsigned char *commit_data
= g
->chunk_commit_data
+ (g
->hash_len
+ 16) * pos
;
327 item
->object
.parsed
= 1;
328 item
->graph_pos
= pos
;
330 item
->maybe_tree
= NULL
;
332 date_high
= get_be32(commit_data
+ g
->hash_len
+ 8) & 0x3;
333 date_low
= get_be32(commit_data
+ g
->hash_len
+ 12);
334 item
->date
= (timestamp_t
)((date_high
<< 32) | date_low
);
336 item
->generation
= get_be32(commit_data
+ g
->hash_len
+ 8) >> 2;
338 pptr
= &item
->parents
;
340 edge_value
= get_be32(commit_data
+ g
->hash_len
);
341 if (edge_value
== GRAPH_PARENT_NONE
)
343 pptr
= insert_parent_or_die(r
, g
, edge_value
, pptr
);
345 edge_value
= get_be32(commit_data
+ g
->hash_len
+ 4);
346 if (edge_value
== GRAPH_PARENT_NONE
)
348 if (!(edge_value
& GRAPH_OCTOPUS_EDGES_NEEDED
)) {
349 pptr
= insert_parent_or_die(r
, g
, edge_value
, pptr
);
353 parent_data_ptr
= (uint32_t*)(g
->chunk_large_edges
+
354 4 * (uint64_t)(edge_value
& GRAPH_EDGE_LAST_MASK
));
356 edge_value
= get_be32(parent_data_ptr
);
357 pptr
= insert_parent_or_die(r
, g
,
358 edge_value
& GRAPH_EDGE_LAST_MASK
,
361 } while (!(edge_value
& GRAPH_LAST_EDGE
));
366 static int find_commit_in_graph(struct commit
*item
, struct commit_graph
*g
, uint32_t *pos
)
368 if (item
->graph_pos
!= COMMIT_NOT_FROM_GRAPH
) {
369 *pos
= item
->graph_pos
;
372 return bsearch_graph(g
, &(item
->object
.oid
), pos
);
376 static int parse_commit_in_graph_one(struct repository
*r
,
377 struct commit_graph
*g
,
382 if (item
->object
.parsed
)
385 if (find_commit_in_graph(item
, g
, &pos
))
386 return fill_commit_in_graph(r
, item
, g
, pos
);
391 int parse_commit_in_graph(struct repository
*r
, struct commit
*item
)
393 if (!prepare_commit_graph(r
))
395 return parse_commit_in_graph_one(r
, r
->objects
->commit_graph
, item
);
398 void load_commit_graph_info(struct repository
*r
, struct commit
*item
)
401 if (!prepare_commit_graph(r
))
403 if (find_commit_in_graph(item
, r
->objects
->commit_graph
, &pos
))
404 fill_commit_graph_info(item
, r
->objects
->commit_graph
, pos
);
407 static struct tree
*load_tree_for_commit(struct repository
*r
,
408 struct commit_graph
*g
,
411 struct object_id oid
;
412 const unsigned char *commit_data
= g
->chunk_commit_data
+
413 GRAPH_DATA_WIDTH
* (c
->graph_pos
);
415 hashcpy(oid
.hash
, commit_data
);
416 c
->maybe_tree
= lookup_tree(r
, &oid
);
418 return c
->maybe_tree
;
421 static struct tree
*get_commit_tree_in_graph_one(struct repository
*r
,
422 struct commit_graph
*g
,
423 const struct commit
*c
)
426 return c
->maybe_tree
;
427 if (c
->graph_pos
== COMMIT_NOT_FROM_GRAPH
)
428 BUG("get_commit_tree_in_graph_one called from non-commit-graph commit");
430 return load_tree_for_commit(r
, g
, (struct commit
*)c
);
433 struct tree
*get_commit_tree_in_graph(struct repository
*r
, const struct commit
*c
)
435 return get_commit_tree_in_graph_one(r
, r
->objects
->commit_graph
, c
);
438 static void write_graph_chunk_fanout(struct hashfile
*f
,
439 struct commit
**commits
,
443 struct commit
**list
= commits
;
446 * Write the first-level table (the list is sorted,
447 * but we use a 256-entry lookup to be able to avoid
448 * having to do eight extra binary search iterations).
450 for (i
= 0; i
< 256; i
++) {
451 while (count
< nr_commits
) {
452 if ((*list
)->object
.oid
.hash
[0] != i
)
458 hashwrite_be32(f
, count
);
462 static void write_graph_chunk_oids(struct hashfile
*f
, int hash_len
,
463 struct commit
**commits
, int nr_commits
)
465 struct commit
**list
= commits
;
467 for (count
= 0; count
< nr_commits
; count
++, list
++)
468 hashwrite(f
, (*list
)->object
.oid
.hash
, (int)hash_len
);
471 static const unsigned char *commit_to_sha1(size_t index
, void *table
)
473 struct commit
**commits
= table
;
474 return commits
[index
]->object
.oid
.hash
;
477 static void write_graph_chunk_data(struct hashfile
*f
, int hash_len
,
478 struct commit
**commits
, int nr_commits
)
480 struct commit
**list
= commits
;
481 struct commit
**last
= commits
+ nr_commits
;
482 uint32_t num_extra_edges
= 0;
484 while (list
< last
) {
485 struct commit_list
*parent
;
487 uint32_t packedDate
[2];
490 hashwrite(f
, get_commit_tree_oid(*list
)->hash
, hash_len
);
492 parent
= (*list
)->parents
;
495 edge_value
= GRAPH_PARENT_NONE
;
497 edge_value
= sha1_pos(parent
->item
->object
.oid
.hash
,
503 BUG("missing parent %s for commit %s",
504 oid_to_hex(&parent
->item
->object
.oid
),
505 oid_to_hex(&(*list
)->object
.oid
));
508 hashwrite_be32(f
, edge_value
);
511 parent
= parent
->next
;
514 edge_value
= GRAPH_PARENT_NONE
;
515 else if (parent
->next
)
516 edge_value
= GRAPH_OCTOPUS_EDGES_NEEDED
| num_extra_edges
;
518 edge_value
= sha1_pos(parent
->item
->object
.oid
.hash
,
523 BUG("missing parent %s for commit %s",
524 oid_to_hex(&parent
->item
->object
.oid
),
525 oid_to_hex(&(*list
)->object
.oid
));
528 hashwrite_be32(f
, edge_value
);
530 if (edge_value
& GRAPH_OCTOPUS_EDGES_NEEDED
) {
533 parent
= parent
->next
;
537 if (sizeof((*list
)->date
) > 4)
538 packedDate
[0] = htonl(((*list
)->date
>> 32) & 0x3);
542 packedDate
[0] |= htonl((*list
)->generation
<< 2);
544 packedDate
[1] = htonl((*list
)->date
);
545 hashwrite(f
, packedDate
, 8);
551 static void write_graph_chunk_large_edges(struct hashfile
*f
,
552 struct commit
**commits
,
555 struct commit
**list
= commits
;
556 struct commit
**last
= commits
+ nr_commits
;
557 struct commit_list
*parent
;
559 while (list
< last
) {
561 for (parent
= (*list
)->parents
; num_parents
< 3 && parent
;
562 parent
= parent
->next
)
565 if (num_parents
<= 2) {
570 /* Since num_parents > 2, this initializer is safe. */
571 for (parent
= (*list
)->parents
->next
; parent
; parent
= parent
->next
) {
572 int edge_value
= sha1_pos(parent
->item
->object
.oid
.hash
,
578 BUG("missing parent %s for commit %s",
579 oid_to_hex(&parent
->item
->object
.oid
),
580 oid_to_hex(&(*list
)->object
.oid
));
581 else if (!parent
->next
)
582 edge_value
|= GRAPH_LAST_EDGE
;
584 hashwrite_be32(f
, edge_value
);
591 static int commit_compare(const void *_a
, const void *_b
)
593 const struct object_id
*a
= (const struct object_id
*)_a
;
594 const struct object_id
*b
= (const struct object_id
*)_b
;
598 struct packed_commit_list
{
599 struct commit
**list
;
604 struct packed_oid_list
{
605 struct object_id
*list
;
608 struct progress
*progress
;
612 static int add_packed_commits(const struct object_id
*oid
,
613 struct packed_git
*pack
,
617 struct packed_oid_list
*list
= (struct packed_oid_list
*)data
;
618 enum object_type type
;
619 off_t offset
= nth_packed_object_offset(pack
, pos
);
620 struct object_info oi
= OBJECT_INFO_INIT
;
623 display_progress(list
->progress
, ++list
->progress_done
);
626 if (packed_object_info(the_repository
, pack
, offset
, &oi
) < 0)
627 die(_("unable to get type of object %s"), oid_to_hex(oid
));
629 if (type
!= OBJ_COMMIT
)
632 ALLOC_GROW(list
->list
, list
->nr
+ 1, list
->alloc
);
633 oidcpy(&(list
->list
[list
->nr
]), oid
);
639 static void add_missing_parents(struct packed_oid_list
*oids
, struct commit
*commit
)
641 struct commit_list
*parent
;
642 for (parent
= commit
->parents
; parent
; parent
= parent
->next
) {
643 if (!(parent
->item
->object
.flags
& UNINTERESTING
)) {
644 ALLOC_GROW(oids
->list
, oids
->nr
+ 1, oids
->alloc
);
645 oidcpy(&oids
->list
[oids
->nr
], &(parent
->item
->object
.oid
));
647 parent
->item
->object
.flags
|= UNINTERESTING
;
652 static void close_reachable(struct packed_oid_list
*oids
, int report_progress
)
655 struct commit
*commit
;
656 struct progress
*progress
= NULL
;
659 progress
= start_delayed_progress(
660 _("Loading known commits in commit graph"), j
= 0);
661 for (i
= 0; i
< oids
->nr
; i
++) {
662 display_progress(progress
, ++j
);
663 commit
= lookup_commit(the_repository
, &oids
->list
[i
]);
665 commit
->object
.flags
|= UNINTERESTING
;
667 stop_progress(&progress
);
670 * As this loop runs, oids->nr may grow, but not more
671 * than the number of missing commits in the reachable
675 progress
= start_delayed_progress(
676 _("Expanding reachable commits in commit graph"), j
= 0);
677 for (i
= 0; i
< oids
->nr
; i
++) {
678 display_progress(progress
, ++j
);
679 commit
= lookup_commit(the_repository
, &oids
->list
[i
]);
681 if (commit
&& !parse_commit(commit
))
682 add_missing_parents(oids
, commit
);
684 stop_progress(&progress
);
687 progress
= start_delayed_progress(
688 _("Clearing commit marks in commit graph"), j
= 0);
689 for (i
= 0; i
< oids
->nr
; i
++) {
690 display_progress(progress
, ++j
);
691 commit
= lookup_commit(the_repository
, &oids
->list
[i
]);
694 commit
->object
.flags
&= ~UNINTERESTING
;
696 stop_progress(&progress
);
699 static void compute_generation_numbers(struct packed_commit_list
* commits
,
703 struct commit_list
*list
= NULL
;
704 struct progress
*progress
= NULL
;
707 progress
= start_progress(
708 _("Computing commit graph generation numbers"),
710 for (i
= 0; i
< commits
->nr
; i
++) {
711 display_progress(progress
, i
+ 1);
712 if (commits
->list
[i
]->generation
!= GENERATION_NUMBER_INFINITY
&&
713 commits
->list
[i
]->generation
!= GENERATION_NUMBER_ZERO
)
716 commit_list_insert(commits
->list
[i
], &list
);
718 struct commit
*current
= list
->item
;
719 struct commit_list
*parent
;
720 int all_parents_computed
= 1;
721 uint32_t max_generation
= 0;
723 for (parent
= current
->parents
; parent
; parent
= parent
->next
) {
724 if (parent
->item
->generation
== GENERATION_NUMBER_INFINITY
||
725 parent
->item
->generation
== GENERATION_NUMBER_ZERO
) {
726 all_parents_computed
= 0;
727 commit_list_insert(parent
->item
, &list
);
729 } else if (parent
->item
->generation
> max_generation
) {
730 max_generation
= parent
->item
->generation
;
734 if (all_parents_computed
) {
735 current
->generation
= max_generation
+ 1;
738 if (current
->generation
> GENERATION_NUMBER_MAX
)
739 current
->generation
= GENERATION_NUMBER_MAX
;
743 stop_progress(&progress
);
746 static int add_ref_to_list(const char *refname
,
747 const struct object_id
*oid
,
748 int flags
, void *cb_data
)
750 struct string_list
*list
= (struct string_list
*)cb_data
;
752 string_list_append(list
, oid_to_hex(oid
));
756 void write_commit_graph_reachable(const char *obj_dir
, int append
,
759 struct string_list list
= STRING_LIST_INIT_DUP
;
761 for_each_ref(add_ref_to_list
, &list
);
762 write_commit_graph(obj_dir
, NULL
, &list
, append
, report_progress
);
764 string_list_clear(&list
, 0);
767 void write_commit_graph(const char *obj_dir
,
768 struct string_list
*pack_indexes
,
769 struct string_list
*commit_hex
,
770 int append
, int report_progress
)
772 struct packed_oid_list oids
;
773 struct packed_commit_list commits
;
775 uint32_t i
, count_distinct
= 0;
777 struct lock_file lk
= LOCK_INIT
;
778 uint32_t chunk_ids
[5];
779 uint64_t chunk_offsets
[5];
782 struct commit_list
*parent
;
783 struct progress
*progress
= NULL
;
784 const unsigned hashsz
= the_hash_algo
->rawsz
;
786 if (!commit_graph_compatible(the_repository
))
790 oids
.alloc
= approximate_object_count() / 32;
791 oids
.progress
= NULL
;
792 oids
.progress_done
= 0;
795 prepare_commit_graph_one(the_repository
, obj_dir
);
796 if (the_repository
->objects
->commit_graph
)
797 oids
.alloc
+= the_repository
->objects
->commit_graph
->num_commits
;
800 if (oids
.alloc
< 1024)
802 ALLOC_ARRAY(oids
.list
, oids
.alloc
);
804 if (append
&& the_repository
->objects
->commit_graph
) {
805 struct commit_graph
*commit_graph
=
806 the_repository
->objects
->commit_graph
;
807 for (i
= 0; i
< commit_graph
->num_commits
; i
++) {
808 const unsigned char *hash
= commit_graph
->chunk_oid_lookup
+
809 commit_graph
->hash_len
* i
;
810 hashcpy(oids
.list
[oids
.nr
++].hash
, hash
);
815 struct strbuf packname
= STRBUF_INIT
;
817 strbuf_addf(&packname
, "%s/pack/", obj_dir
);
818 dirlen
= packname
.len
;
819 if (report_progress
) {
820 oids
.progress
= start_delayed_progress(
821 _("Finding commits for commit graph"), 0);
822 oids
.progress_done
= 0;
824 for (i
= 0; i
< pack_indexes
->nr
; i
++) {
825 struct packed_git
*p
;
826 strbuf_setlen(&packname
, dirlen
);
827 strbuf_addstr(&packname
, pack_indexes
->items
[i
].string
);
828 p
= add_packed_git(packname
.buf
, packname
.len
, 1);
830 die(_("error adding pack %s"), packname
.buf
);
831 if (open_pack_index(p
))
832 die(_("error opening index for %s"), packname
.buf
);
833 for_each_object_in_pack(p
, add_packed_commits
, &oids
, 0);
837 stop_progress(&oids
.progress
);
838 strbuf_release(&packname
);
843 progress
= start_delayed_progress(
844 _("Finding commits for commit graph"),
846 for (i
= 0; i
< commit_hex
->nr
; i
++) {
848 struct object_id oid
;
849 struct commit
*result
;
851 display_progress(progress
, i
+ 1);
852 if (commit_hex
->items
[i
].string
&&
853 parse_oid_hex(commit_hex
->items
[i
].string
, &oid
, &end
))
856 result
= lookup_commit_reference_gently(the_repository
, &oid
, 1);
859 ALLOC_GROW(oids
.list
, oids
.nr
+ 1, oids
.alloc
);
860 oidcpy(&oids
.list
[oids
.nr
], &(result
->object
.oid
));
864 stop_progress(&progress
);
867 if (!pack_indexes
&& !commit_hex
) {
869 oids
.progress
= start_delayed_progress(
870 _("Finding commits for commit graph"), 0);
871 for_each_packed_object(add_packed_commits
, &oids
, 0);
872 stop_progress(&oids
.progress
);
875 close_reachable(&oids
, report_progress
);
877 QSORT(oids
.list
, oids
.nr
, commit_compare
);
880 for (i
= 1; i
< oids
.nr
; i
++) {
881 if (!oideq(&oids
.list
[i
- 1], &oids
.list
[i
]))
885 if (count_distinct
>= GRAPH_EDGE_LAST_MASK
)
886 die(_("the commit graph format cannot write %d commits"), count_distinct
);
889 commits
.alloc
= count_distinct
;
890 ALLOC_ARRAY(commits
.list
, commits
.alloc
);
893 for (i
= 0; i
< oids
.nr
; i
++) {
895 if (i
> 0 && oideq(&oids
.list
[i
- 1], &oids
.list
[i
]))
898 commits
.list
[commits
.nr
] = lookup_commit(the_repository
, &oids
.list
[i
]);
899 parse_commit(commits
.list
[commits
.nr
]);
901 for (parent
= commits
.list
[commits
.nr
]->parents
;
902 parent
; parent
= parent
->next
)
906 num_extra_edges
+= num_parents
- 1;
910 num_chunks
= num_extra_edges
? 4 : 3;
912 if (commits
.nr
>= GRAPH_EDGE_LAST_MASK
)
913 die(_("too many commits to write graph"));
915 compute_generation_numbers(&commits
, report_progress
);
917 graph_name
= get_commit_graph_filename(obj_dir
);
918 if (safe_create_leading_directories(graph_name
)) {
920 die_errno(_("unable to create leading directories of %s"),
924 hold_lock_file_for_update(&lk
, graph_name
, LOCK_DIE_ON_ERROR
);
925 f
= hashfd(lk
.tempfile
->fd
, lk
.tempfile
->filename
.buf
);
927 hashwrite_be32(f
, GRAPH_SIGNATURE
);
929 hashwrite_u8(f
, GRAPH_VERSION
);
930 hashwrite_u8(f
, oid_version());
931 hashwrite_u8(f
, num_chunks
);
932 hashwrite_u8(f
, 0); /* unused padding byte */
934 chunk_ids
[0] = GRAPH_CHUNKID_OIDFANOUT
;
935 chunk_ids
[1] = GRAPH_CHUNKID_OIDLOOKUP
;
936 chunk_ids
[2] = GRAPH_CHUNKID_DATA
;
938 chunk_ids
[3] = GRAPH_CHUNKID_LARGEEDGES
;
943 chunk_offsets
[0] = 8 + (num_chunks
+ 1) * GRAPH_CHUNKLOOKUP_WIDTH
;
944 chunk_offsets
[1] = chunk_offsets
[0] + GRAPH_FANOUT_SIZE
;
945 chunk_offsets
[2] = chunk_offsets
[1] + hashsz
* commits
.nr
;
946 chunk_offsets
[3] = chunk_offsets
[2] + (hashsz
+ 16) * commits
.nr
;
947 chunk_offsets
[4] = chunk_offsets
[3] + 4 * num_extra_edges
;
949 for (i
= 0; i
<= num_chunks
; i
++) {
950 uint32_t chunk_write
[3];
952 chunk_write
[0] = htonl(chunk_ids
[i
]);
953 chunk_write
[1] = htonl(chunk_offsets
[i
] >> 32);
954 chunk_write
[2] = htonl(chunk_offsets
[i
] & 0xffffffff);
955 hashwrite(f
, chunk_write
, 12);
958 write_graph_chunk_fanout(f
, commits
.list
, commits
.nr
);
959 write_graph_chunk_oids(f
, hashsz
, commits
.list
, commits
.nr
);
960 write_graph_chunk_data(f
, hashsz
, commits
.list
, commits
.nr
);
961 write_graph_chunk_large_edges(f
, commits
.list
, commits
.nr
);
963 close_commit_graph(the_repository
);
964 finalize_hashfile(f
, NULL
, CSUM_HASH_IN_STREAM
| CSUM_FSYNC
);
965 commit_lock_file(&lk
);
972 #define VERIFY_COMMIT_GRAPH_ERROR_HASH 2
973 static int verify_commit_graph_error
;
975 static void graph_report(const char *fmt
, ...)
979 verify_commit_graph_error
= 1;
981 vfprintf(stderr
, fmt
, ap
);
982 fprintf(stderr
, "\n");
986 #define GENERATION_ZERO_EXISTS 1
987 #define GENERATION_NUMBER_EXISTS 2
989 int verify_commit_graph(struct repository
*r
, struct commit_graph
*g
)
991 uint32_t i
, cur_fanout_pos
= 0;
992 struct object_id prev_oid
, cur_oid
, checksum
;
993 int generation_zero
= 0;
996 struct progress
*progress
= NULL
;
999 graph_report("no commit-graph file loaded");
1003 verify_commit_graph_error
= 0;
1005 if (!g
->chunk_oid_fanout
)
1006 graph_report("commit-graph is missing the OID Fanout chunk");
1007 if (!g
->chunk_oid_lookup
)
1008 graph_report("commit-graph is missing the OID Lookup chunk");
1009 if (!g
->chunk_commit_data
)
1010 graph_report("commit-graph is missing the Commit Data chunk");
1012 if (verify_commit_graph_error
)
1013 return verify_commit_graph_error
;
1015 devnull
= open("/dev/null", O_WRONLY
);
1016 f
= hashfd(devnull
, NULL
);
1017 hashwrite(f
, g
->data
, g
->data_len
- g
->hash_len
);
1018 finalize_hashfile(f
, checksum
.hash
, CSUM_CLOSE
);
1019 if (!hasheq(checksum
.hash
, g
->data
+ g
->data_len
- g
->hash_len
)) {
1020 graph_report(_("the commit-graph file has incorrect checksum and is likely corrupt"));
1021 verify_commit_graph_error
= VERIFY_COMMIT_GRAPH_ERROR_HASH
;
1024 for (i
= 0; i
< g
->num_commits
; i
++) {
1025 struct commit
*graph_commit
;
1027 hashcpy(cur_oid
.hash
, g
->chunk_oid_lookup
+ g
->hash_len
* i
);
1029 if (i
&& oidcmp(&prev_oid
, &cur_oid
) >= 0)
1030 graph_report("commit-graph has incorrect OID order: %s then %s",
1031 oid_to_hex(&prev_oid
),
1032 oid_to_hex(&cur_oid
));
1034 oidcpy(&prev_oid
, &cur_oid
);
1036 while (cur_oid
.hash
[0] > cur_fanout_pos
) {
1037 uint32_t fanout_value
= get_be32(g
->chunk_oid_fanout
+ cur_fanout_pos
);
1039 if (i
!= fanout_value
)
1040 graph_report("commit-graph has incorrect fanout value: fanout[%d] = %u != %u",
1041 cur_fanout_pos
, fanout_value
, i
);
1045 graph_commit
= lookup_commit(r
, &cur_oid
);
1046 if (!parse_commit_in_graph_one(r
, g
, graph_commit
))
1047 graph_report("failed to parse %s from commit-graph",
1048 oid_to_hex(&cur_oid
));
1051 while (cur_fanout_pos
< 256) {
1052 uint32_t fanout_value
= get_be32(g
->chunk_oid_fanout
+ cur_fanout_pos
);
1054 if (g
->num_commits
!= fanout_value
)
1055 graph_report("commit-graph has incorrect fanout value: fanout[%d] = %u != %u",
1056 cur_fanout_pos
, fanout_value
, i
);
1061 if (verify_commit_graph_error
& ~VERIFY_COMMIT_GRAPH_ERROR_HASH
)
1062 return verify_commit_graph_error
;
1064 progress
= start_progress(_("Verifying commits in commit graph"),
1066 for (i
= 0; i
< g
->num_commits
; i
++) {
1067 struct commit
*graph_commit
, *odb_commit
;
1068 struct commit_list
*graph_parents
, *odb_parents
;
1069 uint32_t max_generation
= 0;
1071 display_progress(progress
, i
+ 1);
1072 hashcpy(cur_oid
.hash
, g
->chunk_oid_lookup
+ g
->hash_len
* i
);
1074 graph_commit
= lookup_commit(r
, &cur_oid
);
1075 odb_commit
= (struct commit
*)create_object(r
, cur_oid
.hash
, alloc_commit_node(r
));
1076 if (parse_commit_internal(odb_commit
, 0, 0)) {
1077 graph_report("failed to parse %s from object database",
1078 oid_to_hex(&cur_oid
));
1082 if (!oideq(&get_commit_tree_in_graph_one(r
, g
, graph_commit
)->object
.oid
,
1083 get_commit_tree_oid(odb_commit
)))
1084 graph_report("root tree OID for commit %s in commit-graph is %s != %s",
1085 oid_to_hex(&cur_oid
),
1086 oid_to_hex(get_commit_tree_oid(graph_commit
)),
1087 oid_to_hex(get_commit_tree_oid(odb_commit
)));
1089 graph_parents
= graph_commit
->parents
;
1090 odb_parents
= odb_commit
->parents
;
1092 while (graph_parents
) {
1093 if (odb_parents
== NULL
) {
1094 graph_report("commit-graph parent list for commit %s is too long",
1095 oid_to_hex(&cur_oid
));
1099 if (!oideq(&graph_parents
->item
->object
.oid
, &odb_parents
->item
->object
.oid
))
1100 graph_report("commit-graph parent for %s is %s != %s",
1101 oid_to_hex(&cur_oid
),
1102 oid_to_hex(&graph_parents
->item
->object
.oid
),
1103 oid_to_hex(&odb_parents
->item
->object
.oid
));
1105 if (graph_parents
->item
->generation
> max_generation
)
1106 max_generation
= graph_parents
->item
->generation
;
1108 graph_parents
= graph_parents
->next
;
1109 odb_parents
= odb_parents
->next
;
1112 if (odb_parents
!= NULL
)
1113 graph_report("commit-graph parent list for commit %s terminates early",
1114 oid_to_hex(&cur_oid
));
1116 if (!graph_commit
->generation
) {
1117 if (generation_zero
== GENERATION_NUMBER_EXISTS
)
1118 graph_report("commit-graph has generation number zero for commit %s, but non-zero elsewhere",
1119 oid_to_hex(&cur_oid
));
1120 generation_zero
= GENERATION_ZERO_EXISTS
;
1121 } else if (generation_zero
== GENERATION_ZERO_EXISTS
)
1122 graph_report("commit-graph has non-zero generation number for commit %s, but zero elsewhere",
1123 oid_to_hex(&cur_oid
));
1125 if (generation_zero
== GENERATION_ZERO_EXISTS
)
1129 * If one of our parents has generation GENERATION_NUMBER_MAX, then
1130 * our generation is also GENERATION_NUMBER_MAX. Decrement to avoid
1131 * extra logic in the following condition.
1133 if (max_generation
== GENERATION_NUMBER_MAX
)
1136 if (graph_commit
->generation
!= max_generation
+ 1)
1137 graph_report("commit-graph generation for commit %s is %u != %u",
1138 oid_to_hex(&cur_oid
),
1139 graph_commit
->generation
,
1140 max_generation
+ 1);
1142 if (graph_commit
->date
!= odb_commit
->date
)
1143 graph_report("commit date for commit %s in commit-graph is %"PRItime
" != %"PRItime
,
1144 oid_to_hex(&cur_oid
),
1148 stop_progress(&progress
);
1150 return verify_commit_graph_error
;
1153 void free_commit_graph(struct commit_graph
*g
)
1157 if (g
->graph_fd
>= 0) {
1158 munmap((void *)g
->data
, g
->data_len
);