3 #include "git-compat-util.h"
10 #include "sha1-lookup.h"
11 #include "commit-graph.h"
13 #define GRAPH_SIGNATURE 0x43475048 /* "CGPH" */
14 #define GRAPH_CHUNKID_OIDFANOUT 0x4f494446 /* "OIDF" */
15 #define GRAPH_CHUNKID_OIDLOOKUP 0x4f49444c /* "OIDL" */
16 #define GRAPH_CHUNKID_DATA 0x43444154 /* "CDAT" */
17 #define GRAPH_CHUNKID_LARGEEDGES 0x45444745 /* "EDGE" */
19 #define GRAPH_DATA_WIDTH 36
21 #define GRAPH_VERSION_1 0x1
22 #define GRAPH_VERSION GRAPH_VERSION_1
24 #define GRAPH_OID_VERSION_SHA1 1
25 #define GRAPH_OID_LEN_SHA1 GIT_SHA1_RAWSZ
26 #define GRAPH_OID_VERSION GRAPH_OID_VERSION_SHA1
27 #define GRAPH_OID_LEN GRAPH_OID_LEN_SHA1
29 #define GRAPH_OCTOPUS_EDGES_NEEDED 0x80000000
30 #define GRAPH_PARENT_MISSING 0x7fffffff
31 #define GRAPH_EDGE_LAST_MASK 0x7fffffff
32 #define GRAPH_PARENT_NONE 0x70000000
34 #define GRAPH_LAST_EDGE 0x80000000
36 #define GRAPH_FANOUT_SIZE (4 * 256)
37 #define GRAPH_CHUNKLOOKUP_WIDTH 12
38 #define GRAPH_MIN_SIZE (5 * GRAPH_CHUNKLOOKUP_WIDTH + GRAPH_FANOUT_SIZE + \
42 char *get_commit_graph_filename(const char *obj_dir
)
44 return xstrfmt("%s/info/commit-graph", obj_dir
);
47 static struct commit_graph
*alloc_commit_graph(void)
49 struct commit_graph
*g
= xcalloc(1, sizeof(*g
));
55 struct commit_graph
*load_commit_graph_one(const char *graph_file
)
58 const unsigned char *data
, *chunk_lookup
;
62 struct commit_graph
*graph
;
63 int fd
= git_open(graph_file
);
64 uint64_t last_chunk_offset
;
65 uint32_t last_chunk_id
;
66 uint32_t graph_signature
;
67 unsigned char graph_version
, hash_version
;
75 graph_size
= xsize_t(st
.st_size
);
77 if (graph_size
< GRAPH_MIN_SIZE
) {
79 die("graph file %s is too small", graph_file
);
81 graph_map
= xmmap(NULL
, graph_size
, PROT_READ
, MAP_PRIVATE
, fd
, 0);
82 data
= (const unsigned char *)graph_map
;
84 graph_signature
= get_be32(data
);
85 if (graph_signature
!= GRAPH_SIGNATURE
) {
86 error("graph signature %X does not match signature %X",
87 graph_signature
, GRAPH_SIGNATURE
);
91 graph_version
= *(unsigned char*)(data
+ 4);
92 if (graph_version
!= GRAPH_VERSION
) {
93 error("graph version %X does not match version %X",
94 graph_version
, GRAPH_VERSION
);
98 hash_version
= *(unsigned char*)(data
+ 5);
99 if (hash_version
!= GRAPH_OID_VERSION
) {
100 error("hash version %X does not match version %X",
101 hash_version
, GRAPH_OID_VERSION
);
105 graph
= alloc_commit_graph();
107 graph
->hash_len
= GRAPH_OID_LEN
;
108 graph
->num_chunks
= *(unsigned char*)(data
+ 6);
109 graph
->graph_fd
= fd
;
110 graph
->data
= graph_map
;
111 graph
->data_len
= graph_size
;
114 last_chunk_offset
= 8;
115 chunk_lookup
= data
+ 8;
116 for (i
= 0; i
< graph
->num_chunks
; i
++) {
117 uint32_t chunk_id
= get_be32(chunk_lookup
+ 0);
118 uint64_t chunk_offset
= get_be64(chunk_lookup
+ 4);
119 int chunk_repeated
= 0;
121 chunk_lookup
+= GRAPH_CHUNKLOOKUP_WIDTH
;
123 if (chunk_offset
> graph_size
- GIT_MAX_RAWSZ
) {
124 error("improper chunk offset %08x%08x", (uint32_t)(chunk_offset
>> 32),
125 (uint32_t)chunk_offset
);
130 case GRAPH_CHUNKID_OIDFANOUT
:
131 if (graph
->chunk_oid_fanout
)
134 graph
->chunk_oid_fanout
= (uint32_t*)(data
+ chunk_offset
);
137 case GRAPH_CHUNKID_OIDLOOKUP
:
138 if (graph
->chunk_oid_lookup
)
141 graph
->chunk_oid_lookup
= data
+ chunk_offset
;
144 case GRAPH_CHUNKID_DATA
:
145 if (graph
->chunk_commit_data
)
148 graph
->chunk_commit_data
= data
+ chunk_offset
;
151 case GRAPH_CHUNKID_LARGEEDGES
:
152 if (graph
->chunk_large_edges
)
155 graph
->chunk_large_edges
= data
+ chunk_offset
;
159 if (chunk_repeated
) {
160 error("chunk id %08x appears multiple times", chunk_id
);
164 if (last_chunk_id
== GRAPH_CHUNKID_OIDLOOKUP
)
166 graph
->num_commits
= (chunk_offset
- last_chunk_offset
)
170 last_chunk_id
= chunk_id
;
171 last_chunk_offset
= chunk_offset
;
177 munmap(graph_map
, graph_size
);
182 static void write_graph_chunk_fanout(struct hashfile
*f
,
183 struct commit
**commits
,
187 struct commit
**list
= commits
;
190 * Write the first-level table (the list is sorted,
191 * but we use a 256-entry lookup to be able to avoid
192 * having to do eight extra binary search iterations).
194 for (i
= 0; i
< 256; i
++) {
195 while (count
< nr_commits
) {
196 if ((*list
)->object
.oid
.hash
[0] != i
)
202 hashwrite_be32(f
, count
);
206 static void write_graph_chunk_oids(struct hashfile
*f
, int hash_len
,
207 struct commit
**commits
, int nr_commits
)
209 struct commit
**list
= commits
;
211 for (count
= 0; count
< nr_commits
; count
++, list
++)
212 hashwrite(f
, (*list
)->object
.oid
.hash
, (int)hash_len
);
215 static const unsigned char *commit_to_sha1(size_t index
, void *table
)
217 struct commit
**commits
= table
;
218 return commits
[index
]->object
.oid
.hash
;
221 static void write_graph_chunk_data(struct hashfile
*f
, int hash_len
,
222 struct commit
**commits
, int nr_commits
)
224 struct commit
**list
= commits
;
225 struct commit
**last
= commits
+ nr_commits
;
226 uint32_t num_extra_edges
= 0;
228 while (list
< last
) {
229 struct commit_list
*parent
;
231 uint32_t packedDate
[2];
234 hashwrite(f
, (*list
)->tree
->object
.oid
.hash
, hash_len
);
236 parent
= (*list
)->parents
;
239 edge_value
= GRAPH_PARENT_NONE
;
241 edge_value
= sha1_pos(parent
->item
->object
.oid
.hash
,
247 edge_value
= GRAPH_PARENT_MISSING
;
250 hashwrite_be32(f
, edge_value
);
253 parent
= parent
->next
;
256 edge_value
= GRAPH_PARENT_NONE
;
257 else if (parent
->next
)
258 edge_value
= GRAPH_OCTOPUS_EDGES_NEEDED
| num_extra_edges
;
260 edge_value
= sha1_pos(parent
->item
->object
.oid
.hash
,
265 edge_value
= GRAPH_PARENT_MISSING
;
268 hashwrite_be32(f
, edge_value
);
270 if (edge_value
& GRAPH_OCTOPUS_EDGES_NEEDED
) {
273 parent
= parent
->next
;
277 if (sizeof((*list
)->date
) > 4)
278 packedDate
[0] = htonl(((*list
)->date
>> 32) & 0x3);
282 packedDate
[1] = htonl((*list
)->date
);
283 hashwrite(f
, packedDate
, 8);
289 static void write_graph_chunk_large_edges(struct hashfile
*f
,
290 struct commit
**commits
,
293 struct commit
**list
= commits
;
294 struct commit
**last
= commits
+ nr_commits
;
295 struct commit_list
*parent
;
297 while (list
< last
) {
299 for (parent
= (*list
)->parents
; num_parents
< 3 && parent
;
300 parent
= parent
->next
)
303 if (num_parents
<= 2) {
308 /* Since num_parents > 2, this initializer is safe. */
309 for (parent
= (*list
)->parents
->next
; parent
; parent
= parent
->next
) {
310 int edge_value
= sha1_pos(parent
->item
->object
.oid
.hash
,
316 edge_value
= GRAPH_PARENT_MISSING
;
317 else if (!parent
->next
)
318 edge_value
|= GRAPH_LAST_EDGE
;
320 hashwrite_be32(f
, edge_value
);
327 static int commit_compare(const void *_a
, const void *_b
)
329 const struct object_id
*a
= (const struct object_id
*)_a
;
330 const struct object_id
*b
= (const struct object_id
*)_b
;
334 struct packed_commit_list
{
335 struct commit
**list
;
340 struct packed_oid_list
{
341 struct object_id
*list
;
346 static int add_packed_commits(const struct object_id
*oid
,
347 struct packed_git
*pack
,
351 struct packed_oid_list
*list
= (struct packed_oid_list
*)data
;
352 enum object_type type
;
353 off_t offset
= nth_packed_object_offset(pack
, pos
);
354 struct object_info oi
= OBJECT_INFO_INIT
;
357 if (packed_object_info(pack
, offset
, &oi
) < 0)
358 die("unable to get type of object %s", oid_to_hex(oid
));
360 if (type
!= OBJ_COMMIT
)
363 ALLOC_GROW(list
->list
, list
->nr
+ 1, list
->alloc
);
364 oidcpy(&(list
->list
[list
->nr
]), oid
);
370 static void add_missing_parents(struct packed_oid_list
*oids
, struct commit
*commit
)
372 struct commit_list
*parent
;
373 for (parent
= commit
->parents
; parent
; parent
= parent
->next
) {
374 if (!(parent
->item
->object
.flags
& UNINTERESTING
)) {
375 ALLOC_GROW(oids
->list
, oids
->nr
+ 1, oids
->alloc
);
376 oidcpy(&oids
->list
[oids
->nr
], &(parent
->item
->object
.oid
));
378 parent
->item
->object
.flags
|= UNINTERESTING
;
383 static void close_reachable(struct packed_oid_list
*oids
)
386 struct commit
*commit
;
388 for (i
= 0; i
< oids
->nr
; i
++) {
389 commit
= lookup_commit(&oids
->list
[i
]);
391 commit
->object
.flags
|= UNINTERESTING
;
395 * As this loop runs, oids->nr may grow, but not more
396 * than the number of missing commits in the reachable
399 for (i
= 0; i
< oids
->nr
; i
++) {
400 commit
= lookup_commit(&oids
->list
[i
]);
402 if (commit
&& !parse_commit(commit
))
403 add_missing_parents(oids
, commit
);
406 for (i
= 0; i
< oids
->nr
; i
++) {
407 commit
= lookup_commit(&oids
->list
[i
]);
410 commit
->object
.flags
&= ~UNINTERESTING
;
414 void write_commit_graph(const char *obj_dir
)
416 struct packed_oid_list oids
;
417 struct packed_commit_list commits
;
419 uint32_t i
, count_distinct
= 0;
422 struct lock_file lk
= LOCK_INIT
;
423 uint32_t chunk_ids
[5];
424 uint64_t chunk_offsets
[5];
427 struct commit_list
*parent
;
430 oids
.alloc
= approximate_object_count() / 4;
432 if (oids
.alloc
< 1024)
434 ALLOC_ARRAY(oids
.list
, oids
.alloc
);
436 for_each_packed_object(add_packed_commits
, &oids
, 0);
437 close_reachable(&oids
);
439 QSORT(oids
.list
, oids
.nr
, commit_compare
);
442 for (i
= 1; i
< oids
.nr
; i
++) {
443 if (oidcmp(&oids
.list
[i
-1], &oids
.list
[i
]))
447 if (count_distinct
>= GRAPH_PARENT_MISSING
)
448 die(_("the commit graph format cannot write %d commits"), count_distinct
);
451 commits
.alloc
= count_distinct
;
452 ALLOC_ARRAY(commits
.list
, commits
.alloc
);
455 for (i
= 0; i
< oids
.nr
; i
++) {
457 if (i
> 0 && !oidcmp(&oids
.list
[i
-1], &oids
.list
[i
]))
460 commits
.list
[commits
.nr
] = lookup_commit(&oids
.list
[i
]);
461 parse_commit(commits
.list
[commits
.nr
]);
463 for (parent
= commits
.list
[commits
.nr
]->parents
;
464 parent
; parent
= parent
->next
)
468 num_extra_edges
+= num_parents
- 1;
472 num_chunks
= num_extra_edges
? 4 : 3;
474 if (commits
.nr
>= GRAPH_PARENT_MISSING
)
475 die(_("too many commits to write graph"));
477 graph_name
= get_commit_graph_filename(obj_dir
);
478 fd
= hold_lock_file_for_update(&lk
, graph_name
, 0);
481 struct strbuf folder
= STRBUF_INIT
;
482 strbuf_addstr(&folder
, graph_name
);
483 strbuf_setlen(&folder
, strrchr(folder
.buf
, '/') - folder
.buf
);
485 if (mkdir(folder
.buf
, 0777) < 0)
486 die_errno(_("cannot mkdir %s"), folder
.buf
);
487 strbuf_release(&folder
);
489 fd
= hold_lock_file_for_update(&lk
, graph_name
, LOCK_DIE_ON_ERROR
);
492 die_errno("unable to create '%s'", graph_name
);
495 f
= hashfd(lk
.tempfile
->fd
, lk
.tempfile
->filename
.buf
);
497 hashwrite_be32(f
, GRAPH_SIGNATURE
);
499 hashwrite_u8(f
, GRAPH_VERSION
);
500 hashwrite_u8(f
, GRAPH_OID_VERSION
);
501 hashwrite_u8(f
, num_chunks
);
502 hashwrite_u8(f
, 0); /* unused padding byte */
504 chunk_ids
[0] = GRAPH_CHUNKID_OIDFANOUT
;
505 chunk_ids
[1] = GRAPH_CHUNKID_OIDLOOKUP
;
506 chunk_ids
[2] = GRAPH_CHUNKID_DATA
;
508 chunk_ids
[3] = GRAPH_CHUNKID_LARGEEDGES
;
513 chunk_offsets
[0] = 8 + (num_chunks
+ 1) * GRAPH_CHUNKLOOKUP_WIDTH
;
514 chunk_offsets
[1] = chunk_offsets
[0] + GRAPH_FANOUT_SIZE
;
515 chunk_offsets
[2] = chunk_offsets
[1] + GRAPH_OID_LEN
* commits
.nr
;
516 chunk_offsets
[3] = chunk_offsets
[2] + (GRAPH_OID_LEN
+ 16) * commits
.nr
;
517 chunk_offsets
[4] = chunk_offsets
[3] + 4 * num_extra_edges
;
519 for (i
= 0; i
<= num_chunks
; i
++) {
520 uint32_t chunk_write
[3];
522 chunk_write
[0] = htonl(chunk_ids
[i
]);
523 chunk_write
[1] = htonl(chunk_offsets
[i
] >> 32);
524 chunk_write
[2] = htonl(chunk_offsets
[i
] & 0xffffffff);
525 hashwrite(f
, chunk_write
, 12);
528 write_graph_chunk_fanout(f
, commits
.list
, commits
.nr
);
529 write_graph_chunk_oids(f
, GRAPH_OID_LEN
, commits
.list
, commits
.nr
);
530 write_graph_chunk_data(f
, GRAPH_OID_LEN
, commits
.list
, commits
.nr
);
531 write_graph_chunk_large_edges(f
, commits
.list
, commits
.nr
);
533 finalize_hashfile(f
, NULL
, CSUM_HASH_IN_STREAM
| CSUM_FSYNC
);
534 commit_lock_file(&lk
);