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" */
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_EXTRA_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 int open_commit_graph(const char *graph_file
, int *fd
, struct stat
*st
)
85 *fd
= git_open(graph_file
);
95 struct commit_graph
*load_commit_graph_one_fd_st(int fd
, struct stat
*st
)
99 struct commit_graph
*ret
;
101 graph_size
= xsize_t(st
->st_size
);
103 if (graph_size
< GRAPH_MIN_SIZE
) {
105 error(_("commit-graph file is too small"));
108 graph_map
= xmmap(NULL
, graph_size
, PROT_READ
, MAP_PRIVATE
, fd
, 0);
109 ret
= parse_commit_graph(graph_map
, fd
, graph_size
);
112 munmap(graph_map
, graph_size
);
119 static int verify_commit_graph_lite(struct commit_graph
*g
)
122 * Basic validation shared between parse_commit_graph()
123 * which'll be called every time the graph is used, and the
124 * much more expensive verify_commit_graph() used by
125 * "commit-graph verify".
127 * There should only be very basic checks here to ensure that
128 * we don't e.g. segfault in fill_commit_in_graph(), but
129 * because this is a very hot codepath nothing that e.g. loops
130 * over g->num_commits, or runs a checksum on the commit-graph
133 if (!g
->chunk_oid_fanout
) {
134 error("commit-graph is missing the OID Fanout chunk");
137 if (!g
->chunk_oid_lookup
) {
138 error("commit-graph is missing the OID Lookup chunk");
141 if (!g
->chunk_commit_data
) {
142 error("commit-graph is missing the Commit Data chunk");
149 struct commit_graph
*parse_commit_graph(void *graph_map
, int fd
,
152 const unsigned char *data
, *chunk_lookup
;
154 struct commit_graph
*graph
;
155 uint64_t last_chunk_offset
;
156 uint32_t last_chunk_id
;
157 uint32_t graph_signature
;
158 unsigned char graph_version
, hash_version
;
163 if (graph_size
< GRAPH_MIN_SIZE
)
166 data
= (const unsigned char *)graph_map
;
168 graph_signature
= get_be32(data
);
169 if (graph_signature
!= GRAPH_SIGNATURE
) {
170 error(_("commit-graph signature %X does not match signature %X"),
171 graph_signature
, GRAPH_SIGNATURE
);
175 graph_version
= *(unsigned char*)(data
+ 4);
176 if (graph_version
!= GRAPH_VERSION
) {
177 error(_("commit-graph version %X does not match version %X"),
178 graph_version
, GRAPH_VERSION
);
182 hash_version
= *(unsigned char*)(data
+ 5);
183 if (hash_version
!= oid_version()) {
184 error(_("commit-graph hash version %X does not match version %X"),
185 hash_version
, oid_version());
189 graph
= alloc_commit_graph();
191 graph
->hash_len
= the_hash_algo
->rawsz
;
192 graph
->num_chunks
= *(unsigned char*)(data
+ 6);
193 graph
->graph_fd
= fd
;
194 graph
->data
= graph_map
;
195 graph
->data_len
= graph_size
;
198 last_chunk_offset
= 8;
199 chunk_lookup
= data
+ 8;
200 for (i
= 0; i
< graph
->num_chunks
; i
++) {
202 uint64_t chunk_offset
;
203 int chunk_repeated
= 0;
205 if (data
+ graph_size
- chunk_lookup
<
206 GRAPH_CHUNKLOOKUP_WIDTH
) {
207 error(_("commit-graph chunk lookup table entry missing; file may be incomplete"));
212 chunk_id
= get_be32(chunk_lookup
+ 0);
213 chunk_offset
= get_be64(chunk_lookup
+ 4);
215 chunk_lookup
+= GRAPH_CHUNKLOOKUP_WIDTH
;
217 if (chunk_offset
> graph_size
- the_hash_algo
->rawsz
) {
218 error(_("commit-graph improper chunk offset %08x%08x"), (uint32_t)(chunk_offset
>> 32),
219 (uint32_t)chunk_offset
);
225 case GRAPH_CHUNKID_OIDFANOUT
:
226 if (graph
->chunk_oid_fanout
)
229 graph
->chunk_oid_fanout
= (uint32_t*)(data
+ chunk_offset
);
232 case GRAPH_CHUNKID_OIDLOOKUP
:
233 if (graph
->chunk_oid_lookup
)
236 graph
->chunk_oid_lookup
= data
+ chunk_offset
;
239 case GRAPH_CHUNKID_DATA
:
240 if (graph
->chunk_commit_data
)
243 graph
->chunk_commit_data
= data
+ chunk_offset
;
246 case GRAPH_CHUNKID_EXTRAEDGES
:
247 if (graph
->chunk_extra_edges
)
250 graph
->chunk_extra_edges
= data
+ chunk_offset
;
254 if (chunk_repeated
) {
255 error(_("commit-graph chunk id %08x appears multiple times"), chunk_id
);
260 if (last_chunk_id
== GRAPH_CHUNKID_OIDLOOKUP
)
262 graph
->num_commits
= (chunk_offset
- last_chunk_offset
)
266 last_chunk_id
= chunk_id
;
267 last_chunk_offset
= chunk_offset
;
270 if (verify_commit_graph_lite(graph
))
276 static struct commit_graph
*load_commit_graph_one(const char *graph_file
)
281 int open_ok
= open_commit_graph(graph_file
, &fd
, &st
);
286 return load_commit_graph_one_fd_st(fd
, &st
);
289 static void prepare_commit_graph_one(struct repository
*r
, const char *obj_dir
)
293 if (r
->objects
->commit_graph
)
296 graph_name
= get_commit_graph_filename(obj_dir
);
297 r
->objects
->commit_graph
=
298 load_commit_graph_one(graph_name
);
300 FREE_AND_NULL(graph_name
);
304 * Return 1 if commit_graph is non-NULL, and 0 otherwise.
306 * On the first invocation, this function attemps to load the commit
307 * graph if the_repository is configured to have one.
309 static int prepare_commit_graph(struct repository
*r
)
311 struct object_directory
*odb
;
314 if (git_env_bool(GIT_TEST_COMMIT_GRAPH_DIE_ON_LOAD
, 0))
315 die("dying as requested by the '%s' variable on commit-graph load!",
316 GIT_TEST_COMMIT_GRAPH_DIE_ON_LOAD
);
318 if (r
->objects
->commit_graph_attempted
)
319 return !!r
->objects
->commit_graph
;
320 r
->objects
->commit_graph_attempted
= 1;
322 if (!git_env_bool(GIT_TEST_COMMIT_GRAPH
, 0) &&
323 (repo_config_get_bool(r
, "core.commitgraph", &config_value
) ||
326 * This repository is not configured to use commit graphs, so
327 * do not load one. (But report commit_graph_attempted anyway
328 * so that commit graph loading is not attempted again for this
333 if (!commit_graph_compatible(r
))
337 for (odb
= r
->objects
->odb
;
338 !r
->objects
->commit_graph
&& odb
;
340 prepare_commit_graph_one(r
, odb
->path
);
341 return !!r
->objects
->commit_graph
;
344 int generation_numbers_enabled(struct repository
*r
)
346 uint32_t first_generation
;
347 struct commit_graph
*g
;
348 if (!prepare_commit_graph(r
))
351 g
= r
->objects
->commit_graph
;
356 first_generation
= get_be32(g
->chunk_commit_data
+
357 g
->hash_len
+ 8) >> 2;
359 return !!first_generation
;
362 void close_commit_graph(struct repository
*r
)
364 free_commit_graph(r
->objects
->commit_graph
);
365 r
->objects
->commit_graph
= NULL
;
368 static int bsearch_graph(struct commit_graph
*g
, struct object_id
*oid
, uint32_t *pos
)
370 return bsearch_hash(oid
->hash
, g
->chunk_oid_fanout
,
371 g
->chunk_oid_lookup
, g
->hash_len
, pos
);
374 static struct commit_list
**insert_parent_or_die(struct repository
*r
,
375 struct commit_graph
*g
,
377 struct commit_list
**pptr
)
380 struct object_id oid
;
382 if (pos
>= g
->num_commits
)
383 die("invalid parent position %"PRIu64
, pos
);
385 hashcpy(oid
.hash
, g
->chunk_oid_lookup
+ g
->hash_len
* pos
);
386 c
= lookup_commit(r
, &oid
);
388 die(_("could not find commit %s"), oid_to_hex(&oid
));
390 return &commit_list_insert(c
, pptr
)->next
;
393 static void fill_commit_graph_info(struct commit
*item
, struct commit_graph
*g
, uint32_t pos
)
395 const unsigned char *commit_data
= g
->chunk_commit_data
+ GRAPH_DATA_WIDTH
* pos
;
396 item
->graph_pos
= pos
;
397 item
->generation
= get_be32(commit_data
+ g
->hash_len
+ 8) >> 2;
400 static int fill_commit_in_graph(struct repository
*r
,
402 struct commit_graph
*g
, uint32_t pos
)
405 uint32_t *parent_data_ptr
;
406 uint64_t date_low
, date_high
;
407 struct commit_list
**pptr
;
408 const unsigned char *commit_data
= g
->chunk_commit_data
+ (g
->hash_len
+ 16) * pos
;
410 item
->object
.parsed
= 1;
411 item
->graph_pos
= pos
;
413 item
->maybe_tree
= NULL
;
415 date_high
= get_be32(commit_data
+ g
->hash_len
+ 8) & 0x3;
416 date_low
= get_be32(commit_data
+ g
->hash_len
+ 12);
417 item
->date
= (timestamp_t
)((date_high
<< 32) | date_low
);
419 item
->generation
= get_be32(commit_data
+ g
->hash_len
+ 8) >> 2;
421 pptr
= &item
->parents
;
423 edge_value
= get_be32(commit_data
+ g
->hash_len
);
424 if (edge_value
== GRAPH_PARENT_NONE
)
426 pptr
= insert_parent_or_die(r
, g
, edge_value
, pptr
);
428 edge_value
= get_be32(commit_data
+ g
->hash_len
+ 4);
429 if (edge_value
== GRAPH_PARENT_NONE
)
431 if (!(edge_value
& GRAPH_EXTRA_EDGES_NEEDED
)) {
432 pptr
= insert_parent_or_die(r
, g
, edge_value
, pptr
);
436 parent_data_ptr
= (uint32_t*)(g
->chunk_extra_edges
+
437 4 * (uint64_t)(edge_value
& GRAPH_EDGE_LAST_MASK
));
439 edge_value
= get_be32(parent_data_ptr
);
440 pptr
= insert_parent_or_die(r
, g
,
441 edge_value
& GRAPH_EDGE_LAST_MASK
,
444 } while (!(edge_value
& GRAPH_LAST_EDGE
));
449 static int find_commit_in_graph(struct commit
*item
, struct commit_graph
*g
, uint32_t *pos
)
451 if (item
->graph_pos
!= COMMIT_NOT_FROM_GRAPH
) {
452 *pos
= item
->graph_pos
;
455 return bsearch_graph(g
, &(item
->object
.oid
), pos
);
459 static int parse_commit_in_graph_one(struct repository
*r
,
460 struct commit_graph
*g
,
465 if (item
->object
.parsed
)
468 if (find_commit_in_graph(item
, g
, &pos
))
469 return fill_commit_in_graph(r
, item
, g
, pos
);
474 int parse_commit_in_graph(struct repository
*r
, struct commit
*item
)
476 if (!prepare_commit_graph(r
))
478 return parse_commit_in_graph_one(r
, r
->objects
->commit_graph
, item
);
481 void load_commit_graph_info(struct repository
*r
, struct commit
*item
)
484 if (!prepare_commit_graph(r
))
486 if (find_commit_in_graph(item
, r
->objects
->commit_graph
, &pos
))
487 fill_commit_graph_info(item
, r
->objects
->commit_graph
, pos
);
490 static struct tree
*load_tree_for_commit(struct repository
*r
,
491 struct commit_graph
*g
,
494 struct object_id oid
;
495 const unsigned char *commit_data
= g
->chunk_commit_data
+
496 GRAPH_DATA_WIDTH
* (c
->graph_pos
);
498 hashcpy(oid
.hash
, commit_data
);
499 c
->maybe_tree
= lookup_tree(r
, &oid
);
501 return c
->maybe_tree
;
504 static struct tree
*get_commit_tree_in_graph_one(struct repository
*r
,
505 struct commit_graph
*g
,
506 const struct commit
*c
)
509 return c
->maybe_tree
;
510 if (c
->graph_pos
== COMMIT_NOT_FROM_GRAPH
)
511 BUG("get_commit_tree_in_graph_one called from non-commit-graph commit");
513 return load_tree_for_commit(r
, g
, (struct commit
*)c
);
516 struct tree
*get_commit_tree_in_graph(struct repository
*r
, const struct commit
*c
)
518 return get_commit_tree_in_graph_one(r
, r
->objects
->commit_graph
, c
);
521 struct packed_commit_list
{
522 struct commit
**list
;
527 struct packed_oid_list
{
528 struct object_id
*list
;
533 struct write_commit_graph_context
{
534 struct repository
*r
;
537 struct packed_oid_list oids
;
538 struct packed_commit_list commits
;
540 unsigned long approx_nr_objects
;
541 struct progress
*progress
;
543 uint64_t progress_cnt
;
548 static void write_graph_chunk_fanout(struct hashfile
*f
,
549 struct write_commit_graph_context
*ctx
)
552 struct commit
**list
= ctx
->commits
.list
;
555 * Write the first-level table (the list is sorted,
556 * but we use a 256-entry lookup to be able to avoid
557 * having to do eight extra binary search iterations).
559 for (i
= 0; i
< 256; i
++) {
560 while (count
< ctx
->commits
.nr
) {
561 if ((*list
)->object
.oid
.hash
[0] != i
)
563 display_progress(ctx
->progress
, ++ctx
->progress_cnt
);
568 hashwrite_be32(f
, count
);
572 static void write_graph_chunk_oids(struct hashfile
*f
, int hash_len
,
573 struct write_commit_graph_context
*ctx
)
575 struct commit
**list
= ctx
->commits
.list
;
577 for (count
= 0; count
< ctx
->commits
.nr
; count
++, list
++) {
578 display_progress(ctx
->progress
, ++ctx
->progress_cnt
);
579 hashwrite(f
, (*list
)->object
.oid
.hash
, (int)hash_len
);
583 static const unsigned char *commit_to_sha1(size_t index
, void *table
)
585 struct commit
**commits
= table
;
586 return commits
[index
]->object
.oid
.hash
;
589 static void write_graph_chunk_data(struct hashfile
*f
, int hash_len
,
590 struct write_commit_graph_context
*ctx
)
592 struct commit
**list
= ctx
->commits
.list
;
593 struct commit
**last
= ctx
->commits
.list
+ ctx
->commits
.nr
;
594 uint32_t num_extra_edges
= 0;
596 while (list
< last
) {
597 struct commit_list
*parent
;
599 uint32_t packedDate
[2];
600 display_progress(ctx
->progress
, ++ctx
->progress_cnt
);
602 parse_commit_no_graph(*list
);
603 hashwrite(f
, get_commit_tree_oid(*list
)->hash
, hash_len
);
605 parent
= (*list
)->parents
;
608 edge_value
= GRAPH_PARENT_NONE
;
610 edge_value
= sha1_pos(parent
->item
->object
.oid
.hash
,
616 BUG("missing parent %s for commit %s",
617 oid_to_hex(&parent
->item
->object
.oid
),
618 oid_to_hex(&(*list
)->object
.oid
));
621 hashwrite_be32(f
, edge_value
);
624 parent
= parent
->next
;
627 edge_value
= GRAPH_PARENT_NONE
;
628 else if (parent
->next
)
629 edge_value
= GRAPH_EXTRA_EDGES_NEEDED
| num_extra_edges
;
631 edge_value
= sha1_pos(parent
->item
->object
.oid
.hash
,
636 BUG("missing parent %s for commit %s",
637 oid_to_hex(&parent
->item
->object
.oid
),
638 oid_to_hex(&(*list
)->object
.oid
));
641 hashwrite_be32(f
, edge_value
);
643 if (edge_value
& GRAPH_EXTRA_EDGES_NEEDED
) {
646 parent
= parent
->next
;
650 if (sizeof((*list
)->date
) > 4)
651 packedDate
[0] = htonl(((*list
)->date
>> 32) & 0x3);
655 packedDate
[0] |= htonl((*list
)->generation
<< 2);
657 packedDate
[1] = htonl((*list
)->date
);
658 hashwrite(f
, packedDate
, 8);
664 static void write_graph_chunk_extra_edges(struct hashfile
*f
,
665 struct write_commit_graph_context
*ctx
)
667 struct commit
**list
= ctx
->commits
.list
;
668 struct commit
**last
= ctx
->commits
.list
+ ctx
->commits
.nr
;
669 struct commit_list
*parent
;
671 while (list
< last
) {
674 display_progress(ctx
->progress
, ++ctx
->progress_cnt
);
676 for (parent
= (*list
)->parents
; num_parents
< 3 && parent
;
677 parent
= parent
->next
)
680 if (num_parents
<= 2) {
685 /* Since num_parents > 2, this initializer is safe. */
686 for (parent
= (*list
)->parents
->next
; parent
; parent
= parent
->next
) {
687 int edge_value
= sha1_pos(parent
->item
->object
.oid
.hash
,
693 BUG("missing parent %s for commit %s",
694 oid_to_hex(&parent
->item
->object
.oid
),
695 oid_to_hex(&(*list
)->object
.oid
));
696 else if (!parent
->next
)
697 edge_value
|= GRAPH_LAST_EDGE
;
699 hashwrite_be32(f
, edge_value
);
706 static int commit_compare(const void *_a
, const void *_b
)
708 const struct object_id
*a
= (const struct object_id
*)_a
;
709 const struct object_id
*b
= (const struct object_id
*)_b
;
713 static int add_packed_commits(const struct object_id
*oid
,
714 struct packed_git
*pack
,
718 struct write_commit_graph_context
*ctx
= (struct write_commit_graph_context
*)data
;
719 enum object_type type
;
720 off_t offset
= nth_packed_object_offset(pack
, pos
);
721 struct object_info oi
= OBJECT_INFO_INIT
;
724 display_progress(ctx
->progress
, ++ctx
->progress_done
);
727 if (packed_object_info(ctx
->r
, pack
, offset
, &oi
) < 0)
728 die(_("unable to get type of object %s"), oid_to_hex(oid
));
730 if (type
!= OBJ_COMMIT
)
733 ALLOC_GROW(ctx
->oids
.list
, ctx
->oids
.nr
+ 1, ctx
->oids
.alloc
);
734 oidcpy(&(ctx
->oids
.list
[ctx
->oids
.nr
]), oid
);
740 static void add_missing_parents(struct write_commit_graph_context
*ctx
, struct commit
*commit
)
742 struct commit_list
*parent
;
743 for (parent
= commit
->parents
; parent
; parent
= parent
->next
) {
744 if (!(parent
->item
->object
.flags
& UNINTERESTING
)) {
745 ALLOC_GROW(ctx
->oids
.list
, ctx
->oids
.nr
+ 1, ctx
->oids
.alloc
);
746 oidcpy(&ctx
->oids
.list
[ctx
->oids
.nr
], &(parent
->item
->object
.oid
));
748 parent
->item
->object
.flags
|= UNINTERESTING
;
753 static void close_reachable(struct write_commit_graph_context
*ctx
)
756 struct commit
*commit
;
758 if (ctx
->report_progress
)
759 ctx
->progress
= start_delayed_progress(
760 _("Loading known commits in commit graph"),
762 for (i
= 0; i
< ctx
->oids
.nr
; i
++) {
763 display_progress(ctx
->progress
, i
+ 1);
764 commit
= lookup_commit(ctx
->r
, &ctx
->oids
.list
[i
]);
766 commit
->object
.flags
|= UNINTERESTING
;
768 stop_progress(&ctx
->progress
);
771 * As this loop runs, ctx->oids.nr may grow, but not more
772 * than the number of missing commits in the reachable
775 if (ctx
->report_progress
)
776 ctx
->progress
= start_delayed_progress(
777 _("Expanding reachable commits in commit graph"),
779 for (i
= 0; i
< ctx
->oids
.nr
; i
++) {
780 display_progress(ctx
->progress
, i
+ 1);
781 commit
= lookup_commit(ctx
->r
, &ctx
->oids
.list
[i
]);
783 if (commit
&& !parse_commit_no_graph(commit
))
784 add_missing_parents(ctx
, commit
);
786 stop_progress(&ctx
->progress
);
788 if (ctx
->report_progress
)
789 ctx
->progress
= start_delayed_progress(
790 _("Clearing commit marks in commit graph"),
792 for (i
= 0; i
< ctx
->oids
.nr
; i
++) {
793 display_progress(ctx
->progress
, i
+ 1);
794 commit
= lookup_commit(ctx
->r
, &ctx
->oids
.list
[i
]);
797 commit
->object
.flags
&= ~UNINTERESTING
;
799 stop_progress(&ctx
->progress
);
802 static void compute_generation_numbers(struct write_commit_graph_context
*ctx
)
805 struct commit_list
*list
= NULL
;
807 if (ctx
->report_progress
)
808 ctx
->progress
= start_progress(
809 _("Computing commit graph generation numbers"),
811 for (i
= 0; i
< ctx
->commits
.nr
; i
++) {
812 display_progress(ctx
->progress
, i
+ 1);
813 if (ctx
->commits
.list
[i
]->generation
!= GENERATION_NUMBER_INFINITY
&&
814 ctx
->commits
.list
[i
]->generation
!= GENERATION_NUMBER_ZERO
)
817 commit_list_insert(ctx
->commits
.list
[i
], &list
);
819 struct commit
*current
= list
->item
;
820 struct commit_list
*parent
;
821 int all_parents_computed
= 1;
822 uint32_t max_generation
= 0;
824 for (parent
= current
->parents
; parent
; parent
= parent
->next
) {
825 if (parent
->item
->generation
== GENERATION_NUMBER_INFINITY
||
826 parent
->item
->generation
== GENERATION_NUMBER_ZERO
) {
827 all_parents_computed
= 0;
828 commit_list_insert(parent
->item
, &list
);
830 } else if (parent
->item
->generation
> max_generation
) {
831 max_generation
= parent
->item
->generation
;
835 if (all_parents_computed
) {
836 current
->generation
= max_generation
+ 1;
839 if (current
->generation
> GENERATION_NUMBER_MAX
)
840 current
->generation
= GENERATION_NUMBER_MAX
;
844 stop_progress(&ctx
->progress
);
847 static int add_ref_to_list(const char *refname
,
848 const struct object_id
*oid
,
849 int flags
, void *cb_data
)
851 struct string_list
*list
= (struct string_list
*)cb_data
;
853 string_list_append(list
, oid_to_hex(oid
));
857 int write_commit_graph_reachable(const char *obj_dir
, unsigned int flags
)
859 struct string_list list
= STRING_LIST_INIT_DUP
;
862 for_each_ref(add_ref_to_list
, &list
);
863 result
= write_commit_graph(obj_dir
, NULL
, &list
,
866 string_list_clear(&list
, 0);
870 static int fill_oids_from_packs(struct write_commit_graph_context
*ctx
,
871 struct string_list
*pack_indexes
)
874 struct strbuf progress_title
= STRBUF_INIT
;
875 struct strbuf packname
= STRBUF_INIT
;
878 strbuf_addf(&packname
, "%s/pack/", ctx
->obj_dir
);
879 dirlen
= packname
.len
;
880 if (ctx
->report_progress
) {
881 strbuf_addf(&progress_title
,
882 Q_("Finding commits for commit graph in %d pack",
883 "Finding commits for commit graph in %d packs",
886 ctx
->progress
= start_delayed_progress(progress_title
.buf
, 0);
887 ctx
->progress_done
= 0;
889 for (i
= 0; i
< pack_indexes
->nr
; i
++) {
890 struct packed_git
*p
;
891 strbuf_setlen(&packname
, dirlen
);
892 strbuf_addstr(&packname
, pack_indexes
->items
[i
].string
);
893 p
= add_packed_git(packname
.buf
, packname
.len
, 1);
895 error(_("error adding pack %s"), packname
.buf
);
898 if (open_pack_index(p
)) {
899 error(_("error opening index for %s"), packname
.buf
);
902 for_each_object_in_pack(p
, add_packed_commits
, ctx
,
903 FOR_EACH_OBJECT_PACK_ORDER
);
908 stop_progress(&ctx
->progress
);
909 strbuf_reset(&progress_title
);
910 strbuf_release(&packname
);
915 static void fill_oids_from_commit_hex(struct write_commit_graph_context
*ctx
,
916 struct string_list
*commit_hex
)
919 struct strbuf progress_title
= STRBUF_INIT
;
921 if (ctx
->report_progress
) {
922 strbuf_addf(&progress_title
,
923 Q_("Finding commits for commit graph from %d ref",
924 "Finding commits for commit graph from %d refs",
927 ctx
->progress
= start_delayed_progress(
931 for (i
= 0; i
< commit_hex
->nr
; i
++) {
933 struct object_id oid
;
934 struct commit
*result
;
936 display_progress(ctx
->progress
, i
+ 1);
937 if (commit_hex
->items
[i
].string
&&
938 parse_oid_hex(commit_hex
->items
[i
].string
, &oid
, &end
))
941 result
= lookup_commit_reference_gently(ctx
->r
, &oid
, 1);
944 ALLOC_GROW(ctx
->oids
.list
, ctx
->oids
.nr
+ 1, ctx
->oids
.alloc
);
945 oidcpy(&ctx
->oids
.list
[ctx
->oids
.nr
], &(result
->object
.oid
));
949 stop_progress(&ctx
->progress
);
950 strbuf_release(&progress_title
);
953 int write_commit_graph(const char *obj_dir
,
954 struct string_list
*pack_indexes
,
955 struct string_list
*commit_hex
,
958 struct write_commit_graph_context
*ctx
;
960 uint32_t i
, count_distinct
= 0;
961 char *graph_name
= NULL
;
962 struct lock_file lk
= LOCK_INIT
;
963 uint32_t chunk_ids
[5];
964 uint64_t chunk_offsets
[5];
966 struct commit_list
*parent
;
967 const unsigned hashsz
= the_hash_algo
->rawsz
;
968 struct strbuf progress_title
= STRBUF_INIT
;
971 if (!commit_graph_compatible(the_repository
))
974 ctx
= xcalloc(1, sizeof(struct write_commit_graph_context
));
975 ctx
->r
= the_repository
;
976 ctx
->obj_dir
= obj_dir
;
977 ctx
->append
= flags
& COMMIT_GRAPH_APPEND
? 1 : 0;
978 ctx
->report_progress
= flags
& COMMIT_GRAPH_PROGRESS
? 1 : 0;
980 ctx
->approx_nr_objects
= approximate_object_count();
981 ctx
->oids
.alloc
= ctx
->approx_nr_objects
/ 32;
984 prepare_commit_graph_one(ctx
->r
, ctx
->obj_dir
);
985 if (ctx
->r
->objects
->commit_graph
)
986 ctx
->oids
.alloc
+= ctx
->r
->objects
->commit_graph
->num_commits
;
989 if (ctx
->oids
.alloc
< 1024)
990 ctx
->oids
.alloc
= 1024;
991 ALLOC_ARRAY(ctx
->oids
.list
, ctx
->oids
.alloc
);
993 if (ctx
->append
&& ctx
->r
->objects
->commit_graph
) {
994 struct commit_graph
*g
= ctx
->r
->objects
->commit_graph
;
995 for (i
= 0; i
< g
->num_commits
; i
++) {
996 const unsigned char *hash
= g
->chunk_oid_lookup
+ g
->hash_len
* i
;
997 hashcpy(ctx
->oids
.list
[ctx
->oids
.nr
++].hash
, hash
);
1002 if ((res
= fill_oids_from_packs(ctx
, pack_indexes
)))
1007 fill_oids_from_commit_hex(ctx
, commit_hex
);
1009 if (!pack_indexes
&& !commit_hex
) {
1010 if (ctx
->report_progress
)
1011 ctx
->progress
= start_delayed_progress(
1012 _("Finding commits for commit graph among packed objects"),
1013 ctx
->approx_nr_objects
);
1014 for_each_packed_object(add_packed_commits
, ctx
,
1015 FOR_EACH_OBJECT_PACK_ORDER
);
1016 if (ctx
->progress_done
< ctx
->approx_nr_objects
)
1017 display_progress(ctx
->progress
, ctx
->approx_nr_objects
);
1018 stop_progress(&ctx
->progress
);
1021 close_reachable(ctx
);
1023 if (ctx
->report_progress
)
1024 ctx
->progress
= start_delayed_progress(
1025 _("Counting distinct commits in commit graph"),
1027 display_progress(ctx
->progress
, 0); /* TODO: Measure QSORT() progress */
1028 QSORT(ctx
->oids
.list
, ctx
->oids
.nr
, commit_compare
);
1030 for (i
= 1; i
< ctx
->oids
.nr
; i
++) {
1031 display_progress(ctx
->progress
, i
+ 1);
1032 if (!oideq(&ctx
->oids
.list
[i
- 1], &ctx
->oids
.list
[i
]))
1035 stop_progress(&ctx
->progress
);
1037 if (count_distinct
>= GRAPH_EDGE_LAST_MASK
) {
1038 error(_("the commit graph format cannot write %d commits"), count_distinct
);
1043 ctx
->commits
.alloc
= count_distinct
;
1044 ALLOC_ARRAY(ctx
->commits
.list
, ctx
->commits
.alloc
);
1046 ctx
->num_extra_edges
= 0;
1047 if (ctx
->report_progress
)
1048 ctx
->progress
= start_delayed_progress(
1049 _("Finding extra edges in commit graph"),
1051 for (i
= 0; i
< ctx
->oids
.nr
; i
++) {
1052 int num_parents
= 0;
1053 display_progress(ctx
->progress
, i
+ 1);
1054 if (i
> 0 && oideq(&ctx
->oids
.list
[i
- 1], &ctx
->oids
.list
[i
]))
1057 ctx
->commits
.list
[ctx
->commits
.nr
] = lookup_commit(ctx
->r
, &ctx
->oids
.list
[i
]);
1058 parse_commit_no_graph(ctx
->commits
.list
[ctx
->commits
.nr
]);
1060 for (parent
= ctx
->commits
.list
[ctx
->commits
.nr
]->parents
;
1061 parent
; parent
= parent
->next
)
1064 if (num_parents
> 2)
1065 ctx
->num_extra_edges
+= num_parents
- 1;
1069 stop_progress(&ctx
->progress
);
1071 if (ctx
->commits
.nr
>= GRAPH_EDGE_LAST_MASK
) {
1072 error(_("too many commits to write graph"));
1077 compute_generation_numbers(ctx
);
1079 num_chunks
= ctx
->num_extra_edges
? 4 : 3;
1081 ctx
->graph_name
= get_commit_graph_filename(ctx
->obj_dir
);
1082 if (safe_create_leading_directories(ctx
->graph_name
)) {
1083 UNLEAK(ctx
->graph_name
);
1084 error(_("unable to create leading directories of %s"),
1090 hold_lock_file_for_update(&lk
, ctx
->graph_name
, LOCK_DIE_ON_ERROR
);
1091 f
= hashfd(lk
.tempfile
->fd
, lk
.tempfile
->filename
.buf
);
1093 hashwrite_be32(f
, GRAPH_SIGNATURE
);
1095 hashwrite_u8(f
, GRAPH_VERSION
);
1096 hashwrite_u8(f
, oid_version());
1097 hashwrite_u8(f
, num_chunks
);
1098 hashwrite_u8(f
, 0); /* unused padding byte */
1100 chunk_ids
[0] = GRAPH_CHUNKID_OIDFANOUT
;
1101 chunk_ids
[1] = GRAPH_CHUNKID_OIDLOOKUP
;
1102 chunk_ids
[2] = GRAPH_CHUNKID_DATA
;
1103 if (ctx
->num_extra_edges
)
1104 chunk_ids
[3] = GRAPH_CHUNKID_EXTRAEDGES
;
1109 chunk_offsets
[0] = 8 + (num_chunks
+ 1) * GRAPH_CHUNKLOOKUP_WIDTH
;
1110 chunk_offsets
[1] = chunk_offsets
[0] + GRAPH_FANOUT_SIZE
;
1111 chunk_offsets
[2] = chunk_offsets
[1] + hashsz
* ctx
->commits
.nr
;
1112 chunk_offsets
[3] = chunk_offsets
[2] + (hashsz
+ 16) * ctx
->commits
.nr
;
1113 chunk_offsets
[4] = chunk_offsets
[3] + 4 * ctx
->num_extra_edges
;
1115 for (i
= 0; i
<= num_chunks
; i
++) {
1116 uint32_t chunk_write
[3];
1118 chunk_write
[0] = htonl(chunk_ids
[i
]);
1119 chunk_write
[1] = htonl(chunk_offsets
[i
] >> 32);
1120 chunk_write
[2] = htonl(chunk_offsets
[i
] & 0xffffffff);
1121 hashwrite(f
, chunk_write
, 12);
1124 if (ctx
->report_progress
) {
1125 strbuf_addf(&progress_title
,
1126 Q_("Writing out commit graph in %d pass",
1127 "Writing out commit graph in %d passes",
1130 ctx
->progress
= start_delayed_progress(
1132 num_chunks
* ctx
->commits
.nr
);
1134 write_graph_chunk_fanout(f
, ctx
);
1135 write_graph_chunk_oids(f
, hashsz
, ctx
);
1136 write_graph_chunk_data(f
, hashsz
, ctx
);
1137 if (ctx
->num_extra_edges
)
1138 write_graph_chunk_extra_edges(f
, ctx
);
1139 stop_progress(&ctx
->progress
);
1140 strbuf_release(&progress_title
);
1142 close_commit_graph(ctx
->r
);
1143 finalize_hashfile(f
, NULL
, CSUM_HASH_IN_STREAM
| CSUM_FSYNC
);
1144 commit_lock_file(&lk
);
1148 free(ctx
->commits
.list
);
1149 free(ctx
->oids
.list
);
1155 #define VERIFY_COMMIT_GRAPH_ERROR_HASH 2
1156 static int verify_commit_graph_error
;
1158 static void graph_report(const char *fmt
, ...)
1162 verify_commit_graph_error
= 1;
1164 vfprintf(stderr
, fmt
, ap
);
1165 fprintf(stderr
, "\n");
1169 #define GENERATION_ZERO_EXISTS 1
1170 #define GENERATION_NUMBER_EXISTS 2
1172 int verify_commit_graph(struct repository
*r
, struct commit_graph
*g
)
1174 uint32_t i
, cur_fanout_pos
= 0;
1175 struct object_id prev_oid
, cur_oid
, checksum
;
1176 int generation_zero
= 0;
1179 struct progress
*progress
= NULL
;
1182 graph_report("no commit-graph file loaded");
1186 verify_commit_graph_error
= verify_commit_graph_lite(g
);
1187 if (verify_commit_graph_error
)
1188 return verify_commit_graph_error
;
1190 devnull
= open("/dev/null", O_WRONLY
);
1191 f
= hashfd(devnull
, NULL
);
1192 hashwrite(f
, g
->data
, g
->data_len
- g
->hash_len
);
1193 finalize_hashfile(f
, checksum
.hash
, CSUM_CLOSE
);
1194 if (!hasheq(checksum
.hash
, g
->data
+ g
->data_len
- g
->hash_len
)) {
1195 graph_report(_("the commit-graph file has incorrect checksum and is likely corrupt"));
1196 verify_commit_graph_error
= VERIFY_COMMIT_GRAPH_ERROR_HASH
;
1199 for (i
= 0; i
< g
->num_commits
; i
++) {
1200 struct commit
*graph_commit
;
1202 hashcpy(cur_oid
.hash
, g
->chunk_oid_lookup
+ g
->hash_len
* i
);
1204 if (i
&& oidcmp(&prev_oid
, &cur_oid
) >= 0)
1205 graph_report(_("commit-graph has incorrect OID order: %s then %s"),
1206 oid_to_hex(&prev_oid
),
1207 oid_to_hex(&cur_oid
));
1209 oidcpy(&prev_oid
, &cur_oid
);
1211 while (cur_oid
.hash
[0] > cur_fanout_pos
) {
1212 uint32_t fanout_value
= get_be32(g
->chunk_oid_fanout
+ cur_fanout_pos
);
1214 if (i
!= fanout_value
)
1215 graph_report(_("commit-graph has incorrect fanout value: fanout[%d] = %u != %u"),
1216 cur_fanout_pos
, fanout_value
, i
);
1220 graph_commit
= lookup_commit(r
, &cur_oid
);
1221 if (!parse_commit_in_graph_one(r
, g
, graph_commit
))
1222 graph_report(_("failed to parse commit %s from commit-graph"),
1223 oid_to_hex(&cur_oid
));
1226 while (cur_fanout_pos
< 256) {
1227 uint32_t fanout_value
= get_be32(g
->chunk_oid_fanout
+ cur_fanout_pos
);
1229 if (g
->num_commits
!= fanout_value
)
1230 graph_report(_("commit-graph has incorrect fanout value: fanout[%d] = %u != %u"),
1231 cur_fanout_pos
, fanout_value
, i
);
1236 if (verify_commit_graph_error
& ~VERIFY_COMMIT_GRAPH_ERROR_HASH
)
1237 return verify_commit_graph_error
;
1239 progress
= start_progress(_("Verifying commits in commit graph"),
1241 for (i
= 0; i
< g
->num_commits
; i
++) {
1242 struct commit
*graph_commit
, *odb_commit
;
1243 struct commit_list
*graph_parents
, *odb_parents
;
1244 uint32_t max_generation
= 0;
1246 display_progress(progress
, i
+ 1);
1247 hashcpy(cur_oid
.hash
, g
->chunk_oid_lookup
+ g
->hash_len
* i
);
1249 graph_commit
= lookup_commit(r
, &cur_oid
);
1250 odb_commit
= (struct commit
*)create_object(r
, cur_oid
.hash
, alloc_commit_node(r
));
1251 if (parse_commit_internal(odb_commit
, 0, 0)) {
1252 graph_report(_("failed to parse commit %s from object database for commit-graph"),
1253 oid_to_hex(&cur_oid
));
1257 if (!oideq(&get_commit_tree_in_graph_one(r
, g
, graph_commit
)->object
.oid
,
1258 get_commit_tree_oid(odb_commit
)))
1259 graph_report(_("root tree OID for commit %s in commit-graph is %s != %s"),
1260 oid_to_hex(&cur_oid
),
1261 oid_to_hex(get_commit_tree_oid(graph_commit
)),
1262 oid_to_hex(get_commit_tree_oid(odb_commit
)));
1264 graph_parents
= graph_commit
->parents
;
1265 odb_parents
= odb_commit
->parents
;
1267 while (graph_parents
) {
1268 if (odb_parents
== NULL
) {
1269 graph_report(_("commit-graph parent list for commit %s is too long"),
1270 oid_to_hex(&cur_oid
));
1274 if (!oideq(&graph_parents
->item
->object
.oid
, &odb_parents
->item
->object
.oid
))
1275 graph_report(_("commit-graph parent for %s is %s != %s"),
1276 oid_to_hex(&cur_oid
),
1277 oid_to_hex(&graph_parents
->item
->object
.oid
),
1278 oid_to_hex(&odb_parents
->item
->object
.oid
));
1280 if (graph_parents
->item
->generation
> max_generation
)
1281 max_generation
= graph_parents
->item
->generation
;
1283 graph_parents
= graph_parents
->next
;
1284 odb_parents
= odb_parents
->next
;
1287 if (odb_parents
!= NULL
)
1288 graph_report(_("commit-graph parent list for commit %s terminates early"),
1289 oid_to_hex(&cur_oid
));
1291 if (!graph_commit
->generation
) {
1292 if (generation_zero
== GENERATION_NUMBER_EXISTS
)
1293 graph_report(_("commit-graph has generation number zero for commit %s, but non-zero elsewhere"),
1294 oid_to_hex(&cur_oid
));
1295 generation_zero
= GENERATION_ZERO_EXISTS
;
1296 } else if (generation_zero
== GENERATION_ZERO_EXISTS
)
1297 graph_report(_("commit-graph has non-zero generation number for commit %s, but zero elsewhere"),
1298 oid_to_hex(&cur_oid
));
1300 if (generation_zero
== GENERATION_ZERO_EXISTS
)
1304 * If one of our parents has generation GENERATION_NUMBER_MAX, then
1305 * our generation is also GENERATION_NUMBER_MAX. Decrement to avoid
1306 * extra logic in the following condition.
1308 if (max_generation
== GENERATION_NUMBER_MAX
)
1311 if (graph_commit
->generation
!= max_generation
+ 1)
1312 graph_report(_("commit-graph generation for commit %s is %u != %u"),
1313 oid_to_hex(&cur_oid
),
1314 graph_commit
->generation
,
1315 max_generation
+ 1);
1317 if (graph_commit
->date
!= odb_commit
->date
)
1318 graph_report(_("commit date for commit %s in commit-graph is %"PRItime
" != %"PRItime
),
1319 oid_to_hex(&cur_oid
),
1323 stop_progress(&progress
);
1325 return verify_commit_graph_error
;
1328 void free_commit_graph(struct commit_graph
*g
)
1332 if (g
->graph_fd
>= 0) {
1333 munmap((void *)g
->data
, g
->data_len
);