commit-graph: add missing forward declaration
[git/git.git] / commit-graph.c
CommitLineData
08fd81c9
DS
1#include "cache.h"
2#include "config.h"
33286dcd 3#include "dir.h"
08fd81c9
DS
4#include "git-compat-util.h"
5#include "lockfile.h"
6#include "pack.h"
7#include "packfile.h"
8#include "commit.h"
9#include "object.h"
59fb8770 10#include "refs.h"
08fd81c9
DS
11#include "revision.h"
12#include "sha1-lookup.h"
13#include "commit-graph.h"
b10edb2d 14#include "object-store.h"
96af91d4 15#include "alloc.h"
08fd81c9
DS
16
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" */
22
23#define GRAPH_DATA_WIDTH 36
24
25#define GRAPH_VERSION_1 0x1
26#define GRAPH_VERSION GRAPH_VERSION_1
27
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
32
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
37
38#define GRAPH_LAST_EDGE 0x80000000
39
0e3b97cc 40#define GRAPH_HEADER_SIZE 8
08fd81c9
DS
41#define GRAPH_FANOUT_SIZE (4 * 256)
42#define GRAPH_CHUNKLOOKUP_WIDTH 12
0e3b97cc
DS
43#define GRAPH_MIN_SIZE (GRAPH_HEADER_SIZE + 4 * GRAPH_CHUNKLOOKUP_WIDTH \
44 + GRAPH_FANOUT_SIZE + GRAPH_OID_LEN)
08fd81c9 45
2a2e32bd 46char *get_commit_graph_filename(const char *obj_dir)
08fd81c9
DS
47{
48 return xstrfmt("%s/info/commit-graph", obj_dir);
49}
50
2a2e32bd
DS
51static struct commit_graph *alloc_commit_graph(void)
52{
53 struct commit_graph *g = xcalloc(1, sizeof(*g));
54 g->graph_fd = -1;
55
56 return g;
57}
58
59struct commit_graph *load_commit_graph_one(const char *graph_file)
60{
61 void *graph_map;
62 const unsigned char *data, *chunk_lookup;
63 size_t graph_size;
64 struct stat st;
65 uint32_t i;
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;
72
73 if (fd < 0)
74 return NULL;
75 if (fstat(fd, &st)) {
76 close(fd);
77 return NULL;
78 }
79 graph_size = xsize_t(st.st_size);
80
81 if (graph_size < GRAPH_MIN_SIZE) {
82 close(fd);
83 die("graph file %s is too small", graph_file);
84 }
85 graph_map = xmmap(NULL, graph_size, PROT_READ, MAP_PRIVATE, fd, 0);
86 data = (const unsigned char *)graph_map;
87
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);
92 goto cleanup_fail;
93 }
94
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);
99 goto cleanup_fail;
100 }
101
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);
106 goto cleanup_fail;
107 }
108
109 graph = alloc_commit_graph();
110
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;
116
117 last_chunk_id = 0;
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;
124
125 chunk_lookup += GRAPH_CHUNKLOOKUP_WIDTH;
126
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);
130 goto cleanup_fail;
131 }
132
133 switch (chunk_id) {
134 case GRAPH_CHUNKID_OIDFANOUT:
135 if (graph->chunk_oid_fanout)
136 chunk_repeated = 1;
137 else
138 graph->chunk_oid_fanout = (uint32_t*)(data + chunk_offset);
139 break;
140
141 case GRAPH_CHUNKID_OIDLOOKUP:
142 if (graph->chunk_oid_lookup)
143 chunk_repeated = 1;
144 else
145 graph->chunk_oid_lookup = data + chunk_offset;
146 break;
147
148 case GRAPH_CHUNKID_DATA:
149 if (graph->chunk_commit_data)
150 chunk_repeated = 1;
151 else
152 graph->chunk_commit_data = data + chunk_offset;
153 break;
154
155 case GRAPH_CHUNKID_LARGEEDGES:
156 if (graph->chunk_large_edges)
157 chunk_repeated = 1;
158 else
159 graph->chunk_large_edges = data + chunk_offset;
160 break;
161 }
162
163 if (chunk_repeated) {
164 error("chunk id %08x appears multiple times", chunk_id);
165 goto cleanup_fail;
166 }
167
168 if (last_chunk_id == GRAPH_CHUNKID_OIDLOOKUP)
169 {
170 graph->num_commits = (chunk_offset - last_chunk_offset)
171 / graph->hash_len;
172 }
173
174 last_chunk_id = chunk_id;
175 last_chunk_offset = chunk_offset;
176 }
177
178 return graph;
179
180cleanup_fail:
181 munmap(graph_map, graph_size);
182 close(fd);
183 exit(1);
184}
185
177722b3
DS
186/* global storage */
187static struct commit_graph *commit_graph = NULL;
188
189static void prepare_commit_graph_one(const char *obj_dir)
190{
191 char *graph_name;
192
193 if (commit_graph)
194 return;
195
196 graph_name = get_commit_graph_filename(obj_dir);
197 commit_graph = load_commit_graph_one(graph_name);
198
199 FREE_AND_NULL(graph_name);
200}
201
202static int prepare_commit_graph_run_once = 0;
5faf357b
JT
203
204/*
205 * Return 1 if commit_graph is non-NULL, and 0 otherwise.
206 *
207 * On the first invocation, this function attemps to load the commit
208 * graph if the_repository is configured to have one.
209 */
210static int prepare_commit_graph(void)
177722b3
DS
211{
212 struct alternate_object_database *alt;
213 char *obj_dir;
214
215 if (prepare_commit_graph_run_once)
5faf357b 216 return !!commit_graph;
177722b3
DS
217 prepare_commit_graph_run_once = 1;
218
5faf357b
JT
219 if (!core_commit_graph)
220 return 0;
221
177722b3
DS
222 obj_dir = get_object_directory();
223 prepare_commit_graph_one(obj_dir);
b10edb2d
JH
224 prepare_alt_odb(the_repository);
225 for (alt = the_repository->objects->alt_odb_list;
226 !commit_graph && alt;
227 alt = alt->next)
177722b3 228 prepare_commit_graph_one(alt->path);
5faf357b 229 return !!commit_graph;
177722b3
DS
230}
231
232static void close_commit_graph(void)
233{
234 if (!commit_graph)
235 return;
236
237 if (commit_graph->graph_fd >= 0) {
238 munmap((void *)commit_graph->data, commit_graph->data_len);
239 commit_graph->data = NULL;
240 close(commit_graph->graph_fd);
241 }
242
243 FREE_AND_NULL(commit_graph);
244}
245
246static int bsearch_graph(struct commit_graph *g, struct object_id *oid, uint32_t *pos)
247{
248 return bsearch_hash(oid->hash, g->chunk_oid_fanout,
249 g->chunk_oid_lookup, g->hash_len, pos);
250}
251
252static struct commit_list **insert_parent_or_die(struct commit_graph *g,
253 uint64_t pos,
254 struct commit_list **pptr)
255{
256 struct commit *c;
257 struct object_id oid;
96af91d4 258
53614b13
DS
259 if (pos >= g->num_commits)
260 die("invalid parent position %"PRIu64, pos);
261
177722b3 262 hashcpy(oid.hash, g->chunk_oid_lookup + g->hash_len * pos);
c1f5eb49 263 c = lookup_commit(the_repository, &oid);
177722b3
DS
264 if (!c)
265 die("could not find commit %s", oid_to_hex(&oid));
266 c->graph_pos = pos;
267 return &commit_list_insert(c, pptr)->next;
268}
269
e2838d85
DS
270static void fill_commit_graph_info(struct commit *item, struct commit_graph *g, uint32_t pos)
271{
272 const unsigned char *commit_data = g->chunk_commit_data + GRAPH_DATA_WIDTH * pos;
273 item->graph_pos = pos;
274 item->generation = get_be32(commit_data + g->hash_len + 8) >> 2;
275}
276
177722b3
DS
277static int fill_commit_in_graph(struct commit *item, struct commit_graph *g, uint32_t pos)
278{
177722b3
DS
279 uint32_t edge_value;
280 uint32_t *parent_data_ptr;
281 uint64_t date_low, date_high;
282 struct commit_list **pptr;
283 const unsigned char *commit_data = g->chunk_commit_data + (g->hash_len + 16) * pos;
284
285 item->object.parsed = 1;
286 item->graph_pos = pos;
287
7b8a21db 288 item->maybe_tree = NULL;
177722b3
DS
289
290 date_high = get_be32(commit_data + g->hash_len + 8) & 0x3;
291 date_low = get_be32(commit_data + g->hash_len + 12);
292 item->date = (timestamp_t)((date_high << 32) | date_low);
293
83073cc9
DS
294 item->generation = get_be32(commit_data + g->hash_len + 8) >> 2;
295
177722b3
DS
296 pptr = &item->parents;
297
298 edge_value = get_be32(commit_data + g->hash_len);
299 if (edge_value == GRAPH_PARENT_NONE)
300 return 1;
301 pptr = insert_parent_or_die(g, edge_value, pptr);
302
303 edge_value = get_be32(commit_data + g->hash_len + 4);
304 if (edge_value == GRAPH_PARENT_NONE)
305 return 1;
306 if (!(edge_value & GRAPH_OCTOPUS_EDGES_NEEDED)) {
307 pptr = insert_parent_or_die(g, edge_value, pptr);
308 return 1;
309 }
310
311 parent_data_ptr = (uint32_t*)(g->chunk_large_edges +
312 4 * (uint64_t)(edge_value & GRAPH_EDGE_LAST_MASK));
313 do {
314 edge_value = get_be32(parent_data_ptr);
315 pptr = insert_parent_or_die(g,
316 edge_value & GRAPH_EDGE_LAST_MASK,
317 pptr);
318 parent_data_ptr++;
319 } while (!(edge_value & GRAPH_LAST_EDGE));
320
321 return 1;
322}
323
e2838d85
DS
324static int find_commit_in_graph(struct commit *item, struct commit_graph *g, uint32_t *pos)
325{
326 if (item->graph_pos != COMMIT_NOT_FROM_GRAPH) {
327 *pos = item->graph_pos;
328 return 1;
329 } else {
330 return bsearch_graph(g, &(item->object.oid), pos);
331 }
332}
333
ee797053 334static int parse_commit_in_graph_one(struct commit_graph *g, struct commit *item)
177722b3 335{
e2838d85
DS
336 uint32_t pos;
337
177722b3
DS
338 if (!core_commit_graph)
339 return 0;
340 if (item->object.parsed)
341 return 1;
ee797053
DS
342
343 if (find_commit_in_graph(item, g, &pos))
344 return fill_commit_in_graph(item, g, pos);
345
346 return 0;
347}
348
349int parse_commit_in_graph(struct commit *item)
350{
5faf357b 351 if (!prepare_commit_graph())
ee797053 352 return 0;
5faf357b 353 return parse_commit_in_graph_one(commit_graph, item);
177722b3
DS
354}
355
e2838d85
DS
356void load_commit_graph_info(struct commit *item)
357{
358 uint32_t pos;
5faf357b 359 if (!prepare_commit_graph())
e2838d85 360 return;
5faf357b 361 if (find_commit_in_graph(item, commit_graph, &pos))
e2838d85
DS
362 fill_commit_graph_info(item, commit_graph, pos);
363}
364
7b8a21db
DS
365static struct tree *load_tree_for_commit(struct commit_graph *g, struct commit *c)
366{
367 struct object_id oid;
368 const unsigned char *commit_data = g->chunk_commit_data +
369 GRAPH_DATA_WIDTH * (c->graph_pos);
370
371 hashcpy(oid.hash, commit_data);
f86bcc7b 372 c->maybe_tree = lookup_tree(the_repository, &oid);
7b8a21db
DS
373
374 return c->maybe_tree;
375}
376
0cbef8f8
DS
377static struct tree *get_commit_tree_in_graph_one(struct commit_graph *g,
378 const struct commit *c)
7b8a21db
DS
379{
380 if (c->maybe_tree)
381 return c->maybe_tree;
382 if (c->graph_pos == COMMIT_NOT_FROM_GRAPH)
0cbef8f8
DS
383 BUG("get_commit_tree_in_graph_one called from non-commit-graph commit");
384
385 return load_tree_for_commit(g, (struct commit *)c);
386}
7b8a21db 387
0cbef8f8
DS
388struct tree *get_commit_tree_in_graph(const struct commit *c)
389{
390 return get_commit_tree_in_graph_one(commit_graph, c);
7b8a21db
DS
391}
392
08fd81c9
DS
393static void write_graph_chunk_fanout(struct hashfile *f,
394 struct commit **commits,
395 int nr_commits)
396{
397 int i, count = 0;
398 struct commit **list = commits;
399
400 /*
401 * Write the first-level table (the list is sorted,
402 * but we use a 256-entry lookup to be able to avoid
403 * having to do eight extra binary search iterations).
404 */
405 for (i = 0; i < 256; i++) {
406 while (count < nr_commits) {
407 if ((*list)->object.oid.hash[0] != i)
408 break;
409 count++;
410 list++;
411 }
412
413 hashwrite_be32(f, count);
414 }
415}
416
417static void write_graph_chunk_oids(struct hashfile *f, int hash_len,
418 struct commit **commits, int nr_commits)
419{
420 struct commit **list = commits;
421 int count;
422 for (count = 0; count < nr_commits; count++, list++)
423 hashwrite(f, (*list)->object.oid.hash, (int)hash_len);
424}
425
426static const unsigned char *commit_to_sha1(size_t index, void *table)
427{
428 struct commit **commits = table;
429 return commits[index]->object.oid.hash;
430}
431
432static void write_graph_chunk_data(struct hashfile *f, int hash_len,
433 struct commit **commits, int nr_commits)
434{
435 struct commit **list = commits;
436 struct commit **last = commits + nr_commits;
437 uint32_t num_extra_edges = 0;
438
439 while (list < last) {
440 struct commit_list *parent;
441 int edge_value;
442 uint32_t packedDate[2];
443
444 parse_commit(*list);
2e27bd77 445 hashwrite(f, get_commit_tree_oid(*list)->hash, hash_len);
08fd81c9
DS
446
447 parent = (*list)->parents;
448
449 if (!parent)
450 edge_value = GRAPH_PARENT_NONE;
451 else {
452 edge_value = sha1_pos(parent->item->object.oid.hash,
453 commits,
454 nr_commits,
455 commit_to_sha1);
456
457 if (edge_value < 0)
458 edge_value = GRAPH_PARENT_MISSING;
459 }
460
461 hashwrite_be32(f, edge_value);
462
463 if (parent)
464 parent = parent->next;
465
466 if (!parent)
467 edge_value = GRAPH_PARENT_NONE;
468 else if (parent->next)
469 edge_value = GRAPH_OCTOPUS_EDGES_NEEDED | num_extra_edges;
470 else {
471 edge_value = sha1_pos(parent->item->object.oid.hash,
472 commits,
473 nr_commits,
474 commit_to_sha1);
475 if (edge_value < 0)
476 edge_value = GRAPH_PARENT_MISSING;
477 }
478
479 hashwrite_be32(f, edge_value);
480
481 if (edge_value & GRAPH_OCTOPUS_EDGES_NEEDED) {
482 do {
483 num_extra_edges++;
484 parent = parent->next;
485 } while (parent);
486 }
487
488 if (sizeof((*list)->date) > 4)
489 packedDate[0] = htonl(((*list)->date >> 32) & 0x3);
490 else
491 packedDate[0] = 0;
492
3258c663
DS
493 packedDate[0] |= htonl((*list)->generation << 2);
494
08fd81c9
DS
495 packedDate[1] = htonl((*list)->date);
496 hashwrite(f, packedDate, 8);
497
498 list++;
499 }
500}
501
502static void write_graph_chunk_large_edges(struct hashfile *f,
503 struct commit **commits,
504 int nr_commits)
505{
506 struct commit **list = commits;
507 struct commit **last = commits + nr_commits;
508 struct commit_list *parent;
509
510 while (list < last) {
511 int num_parents = 0;
512 for (parent = (*list)->parents; num_parents < 3 && parent;
513 parent = parent->next)
514 num_parents++;
515
516 if (num_parents <= 2) {
517 list++;
518 continue;
519 }
520
521 /* Since num_parents > 2, this initializer is safe. */
522 for (parent = (*list)->parents->next; parent; parent = parent->next) {
523 int edge_value = sha1_pos(parent->item->object.oid.hash,
524 commits,
525 nr_commits,
526 commit_to_sha1);
527
528 if (edge_value < 0)
529 edge_value = GRAPH_PARENT_MISSING;
530 else if (!parent->next)
531 edge_value |= GRAPH_LAST_EDGE;
532
533 hashwrite_be32(f, edge_value);
534 }
535
536 list++;
537 }
538}
539
540static int commit_compare(const void *_a, const void *_b)
541{
542 const struct object_id *a = (const struct object_id *)_a;
543 const struct object_id *b = (const struct object_id *)_b;
544 return oidcmp(a, b);
545}
546
547struct packed_commit_list {
548 struct commit **list;
549 int nr;
550 int alloc;
551};
552
553struct packed_oid_list {
554 struct object_id *list;
555 int nr;
556 int alloc;
557};
558
559static int add_packed_commits(const struct object_id *oid,
560 struct packed_git *pack,
561 uint32_t pos,
562 void *data)
563{
564 struct packed_oid_list *list = (struct packed_oid_list*)data;
565 enum object_type type;
566 off_t offset = nth_packed_object_offset(pack, pos);
567 struct object_info oi = OBJECT_INFO_INIT;
568
569 oi.typep = &type;
fcb6df32 570 if (packed_object_info(the_repository, pack, offset, &oi) < 0)
08fd81c9
DS
571 die("unable to get type of object %s", oid_to_hex(oid));
572
573 if (type != OBJ_COMMIT)
574 return 0;
575
576 ALLOC_GROW(list->list, list->nr + 1, list->alloc);
577 oidcpy(&(list->list[list->nr]), oid);
578 list->nr++;
579
580 return 0;
581}
582
4f2542b4
DS
583static void add_missing_parents(struct packed_oid_list *oids, struct commit *commit)
584{
585 struct commit_list *parent;
586 for (parent = commit->parents; parent; parent = parent->next) {
587 if (!(parent->item->object.flags & UNINTERESTING)) {
588 ALLOC_GROW(oids->list, oids->nr + 1, oids->alloc);
589 oidcpy(&oids->list[oids->nr], &(parent->item->object.oid));
590 oids->nr++;
591 parent->item->object.flags |= UNINTERESTING;
592 }
593 }
594}
595
596static void close_reachable(struct packed_oid_list *oids)
597{
598 int i;
599 struct commit *commit;
600
601 for (i = 0; i < oids->nr; i++) {
c1f5eb49 602 commit = lookup_commit(the_repository, &oids->list[i]);
4f2542b4
DS
603 if (commit)
604 commit->object.flags |= UNINTERESTING;
605 }
606
607 /*
608 * As this loop runs, oids->nr may grow, but not more
609 * than the number of missing commits in the reachable
610 * closure.
611 */
612 for (i = 0; i < oids->nr; i++) {
c1f5eb49 613 commit = lookup_commit(the_repository, &oids->list[i]);
4f2542b4
DS
614
615 if (commit && !parse_commit(commit))
616 add_missing_parents(oids, commit);
617 }
618
619 for (i = 0; i < oids->nr; i++) {
c1f5eb49 620 commit = lookup_commit(the_repository, &oids->list[i]);
4f2542b4
DS
621
622 if (commit)
623 commit->object.flags &= ~UNINTERESTING;
624 }
625}
626
3258c663
DS
627static void compute_generation_numbers(struct packed_commit_list* commits)
628{
629 int i;
630 struct commit_list *list = NULL;
631
632 for (i = 0; i < commits->nr; i++) {
633 if (commits->list[i]->generation != GENERATION_NUMBER_INFINITY &&
634 commits->list[i]->generation != GENERATION_NUMBER_ZERO)
635 continue;
636
637 commit_list_insert(commits->list[i], &list);
638 while (list) {
639 struct commit *current = list->item;
640 struct commit_list *parent;
641 int all_parents_computed = 1;
642 uint32_t max_generation = 0;
643
644 for (parent = current->parents; parent; parent = parent->next) {
645 if (parent->item->generation == GENERATION_NUMBER_INFINITY ||
646 parent->item->generation == GENERATION_NUMBER_ZERO) {
647 all_parents_computed = 0;
648 commit_list_insert(parent->item, &list);
649 break;
650 } else if (parent->item->generation > max_generation) {
651 max_generation = parent->item->generation;
652 }
653 }
654
655 if (all_parents_computed) {
656 current->generation = max_generation + 1;
657 pop_commit(&list);
658
659 if (current->generation > GENERATION_NUMBER_MAX)
660 current->generation = GENERATION_NUMBER_MAX;
661 }
662 }
663 }
664}
665
59fb8770
DS
666static int add_ref_to_list(const char *refname,
667 const struct object_id *oid,
668 int flags, void *cb_data)
669{
670 struct string_list *list = (struct string_list *)cb_data;
671
672 string_list_append(list, oid_to_hex(oid));
673 return 0;
674}
675
676void write_commit_graph_reachable(const char *obj_dir, int append)
677{
678 struct string_list list;
679
680 string_list_init(&list, 1);
681 for_each_ref(add_ref_to_list, &list);
682 write_commit_graph(obj_dir, NULL, &list, append);
683}
684
049d51a2 685void write_commit_graph(const char *obj_dir,
d88b14b3
DS
686 struct string_list *pack_indexes,
687 struct string_list *commit_hex,
7547b95b 688 int append)
08fd81c9
DS
689{
690 struct packed_oid_list oids;
691 struct packed_commit_list commits;
692 struct hashfile *f;
693 uint32_t i, count_distinct = 0;
694 char *graph_name;
08fd81c9
DS
695 struct lock_file lk = LOCK_INIT;
696 uint32_t chunk_ids[5];
697 uint64_t chunk_offsets[5];
698 int num_chunks;
699 int num_extra_edges;
700 struct commit_list *parent;
701
702 oids.nr = 0;
703 oids.alloc = approximate_object_count() / 4;
704
7547b95b
DS
705 if (append) {
706 prepare_commit_graph_one(obj_dir);
707 if (commit_graph)
708 oids.alloc += commit_graph->num_commits;
709 }
710
08fd81c9
DS
711 if (oids.alloc < 1024)
712 oids.alloc = 1024;
713 ALLOC_ARRAY(oids.list, oids.alloc);
714
7547b95b
DS
715 if (append && commit_graph) {
716 for (i = 0; i < commit_graph->num_commits; i++) {
717 const unsigned char *hash = commit_graph->chunk_oid_lookup +
718 commit_graph->hash_len * i;
719 hashcpy(oids.list[oids.nr++].hash, hash);
720 }
721 }
722
049d51a2
DS
723 if (pack_indexes) {
724 struct strbuf packname = STRBUF_INIT;
725 int dirlen;
726 strbuf_addf(&packname, "%s/pack/", obj_dir);
727 dirlen = packname.len;
d88b14b3 728 for (i = 0; i < pack_indexes->nr; i++) {
049d51a2
DS
729 struct packed_git *p;
730 strbuf_setlen(&packname, dirlen);
d88b14b3 731 strbuf_addstr(&packname, pack_indexes->items[i].string);
049d51a2
DS
732 p = add_packed_git(packname.buf, packname.len, 1);
733 if (!p)
734 die("error adding pack %s", packname.buf);
735 if (open_pack_index(p))
736 die("error opening index for %s", packname.buf);
737 for_each_object_in_pack(p, add_packed_commits, &oids);
738 close_pack(p);
739 }
740 strbuf_release(&packname);
3d5df01b
DS
741 }
742
743 if (commit_hex) {
d88b14b3 744 for (i = 0; i < commit_hex->nr; i++) {
3d5df01b
DS
745 const char *end;
746 struct object_id oid;
747 struct commit *result;
748
d88b14b3
DS
749 if (commit_hex->items[i].string &&
750 parse_oid_hex(commit_hex->items[i].string, &oid, &end))
3d5df01b
DS
751 continue;
752
21e1ee8f 753 result = lookup_commit_reference_gently(the_repository, &oid, 1);
3d5df01b
DS
754
755 if (result) {
756 ALLOC_GROW(oids.list, oids.nr + 1, oids.alloc);
757 oidcpy(&oids.list[oids.nr], &(result->object.oid));
758 oids.nr++;
759 }
760 }
761 }
762
763 if (!pack_indexes && !commit_hex)
049d51a2
DS
764 for_each_packed_object(add_packed_commits, &oids, 0);
765
4f2542b4 766 close_reachable(&oids);
08fd81c9
DS
767
768 QSORT(oids.list, oids.nr, commit_compare);
769
770 count_distinct = 1;
771 for (i = 1; i < oids.nr; i++) {
772 if (oidcmp(&oids.list[i-1], &oids.list[i]))
773 count_distinct++;
774 }
775
776 if (count_distinct >= GRAPH_PARENT_MISSING)
777 die(_("the commit graph format cannot write %d commits"), count_distinct);
778
779 commits.nr = 0;
780 commits.alloc = count_distinct;
781 ALLOC_ARRAY(commits.list, commits.alloc);
782
783 num_extra_edges = 0;
784 for (i = 0; i < oids.nr; i++) {
785 int num_parents = 0;
786 if (i > 0 && !oidcmp(&oids.list[i-1], &oids.list[i]))
787 continue;
788
c1f5eb49 789 commits.list[commits.nr] = lookup_commit(the_repository, &oids.list[i]);
08fd81c9
DS
790 parse_commit(commits.list[commits.nr]);
791
792 for (parent = commits.list[commits.nr]->parents;
793 parent; parent = parent->next)
794 num_parents++;
795
796 if (num_parents > 2)
797 num_extra_edges += num_parents - 1;
798
799 commits.nr++;
800 }
801 num_chunks = num_extra_edges ? 4 : 3;
802
803 if (commits.nr >= GRAPH_PARENT_MISSING)
804 die(_("too many commits to write graph"));
805
3258c663 806 compute_generation_numbers(&commits);
08fd81c9 807
08fd81c9 808 graph_name = get_commit_graph_filename(obj_dir);
33286dcd
DS
809 if (safe_create_leading_directories(graph_name))
810 die_errno(_("unable to create leading directories of %s"),
811 graph_name);
08fd81c9 812
33286dcd 813 hold_lock_file_for_update(&lk, graph_name, LOCK_DIE_ON_ERROR);
08fd81c9
DS
814 f = hashfd(lk.tempfile->fd, lk.tempfile->filename.buf);
815
816 hashwrite_be32(f, GRAPH_SIGNATURE);
817
818 hashwrite_u8(f, GRAPH_VERSION);
819 hashwrite_u8(f, GRAPH_OID_VERSION);
820 hashwrite_u8(f, num_chunks);
821 hashwrite_u8(f, 0); /* unused padding byte */
822
823 chunk_ids[0] = GRAPH_CHUNKID_OIDFANOUT;
824 chunk_ids[1] = GRAPH_CHUNKID_OIDLOOKUP;
825 chunk_ids[2] = GRAPH_CHUNKID_DATA;
826 if (num_extra_edges)
827 chunk_ids[3] = GRAPH_CHUNKID_LARGEEDGES;
828 else
829 chunk_ids[3] = 0;
830 chunk_ids[4] = 0;
831
832 chunk_offsets[0] = 8 + (num_chunks + 1) * GRAPH_CHUNKLOOKUP_WIDTH;
833 chunk_offsets[1] = chunk_offsets[0] + GRAPH_FANOUT_SIZE;
834 chunk_offsets[2] = chunk_offsets[1] + GRAPH_OID_LEN * commits.nr;
835 chunk_offsets[3] = chunk_offsets[2] + (GRAPH_OID_LEN + 16) * commits.nr;
836 chunk_offsets[4] = chunk_offsets[3] + 4 * num_extra_edges;
837
838 for (i = 0; i <= num_chunks; i++) {
839 uint32_t chunk_write[3];
840
841 chunk_write[0] = htonl(chunk_ids[i]);
842 chunk_write[1] = htonl(chunk_offsets[i] >> 32);
843 chunk_write[2] = htonl(chunk_offsets[i] & 0xffffffff);
844 hashwrite(f, chunk_write, 12);
845 }
846
847 write_graph_chunk_fanout(f, commits.list, commits.nr);
848 write_graph_chunk_oids(f, GRAPH_OID_LEN, commits.list, commits.nr);
849 write_graph_chunk_data(f, GRAPH_OID_LEN, commits.list, commits.nr);
850 write_graph_chunk_large_edges(f, commits.list, commits.nr);
851
177722b3 852 close_commit_graph();
08fd81c9
DS
853 finalize_hashfile(f, NULL, CSUM_HASH_IN_STREAM | CSUM_FSYNC);
854 commit_lock_file(&lk);
855
856 free(oids.list);
857 oids.alloc = 0;
858 oids.nr = 0;
859}
283e68c7 860
41df0e30 861#define VERIFY_COMMIT_GRAPH_ERROR_HASH 2
283e68c7
DS
862static int verify_commit_graph_error;
863
864static void graph_report(const char *fmt, ...)
865{
866 va_list ap;
867
868 verify_commit_graph_error = 1;
869 va_start(ap, fmt);
870 vfprintf(stderr, fmt, ap);
871 fprintf(stderr, "\n");
872 va_end(ap);
873}
874
1373e547
DS
875#define GENERATION_ZERO_EXISTS 1
876#define GENERATION_NUMBER_EXISTS 2
877
283e68c7
DS
878int verify_commit_graph(struct repository *r, struct commit_graph *g)
879{
9bda8467 880 uint32_t i, cur_fanout_pos = 0;
41df0e30 881 struct object_id prev_oid, cur_oid, checksum;
1373e547 882 int generation_zero = 0;
41df0e30
DS
883 struct hashfile *f;
884 int devnull;
9bda8467 885
283e68c7
DS
886 if (!g) {
887 graph_report("no commit-graph file loaded");
888 return 1;
889 }
890
2bd0365f
DS
891 verify_commit_graph_error = 0;
892
893 if (!g->chunk_oid_fanout)
894 graph_report("commit-graph is missing the OID Fanout chunk");
895 if (!g->chunk_oid_lookup)
896 graph_report("commit-graph is missing the OID Lookup chunk");
897 if (!g->chunk_commit_data)
898 graph_report("commit-graph is missing the Commit Data chunk");
899
9bda8467
DS
900 if (verify_commit_graph_error)
901 return verify_commit_graph_error;
902
41df0e30
DS
903 devnull = open("/dev/null", O_WRONLY);
904 f = hashfd(devnull, NULL);
905 hashwrite(f, g->data, g->data_len - g->hash_len);
906 finalize_hashfile(f, checksum.hash, CSUM_CLOSE);
907 if (hashcmp(checksum.hash, g->data + g->data_len - g->hash_len)) {
908 graph_report(_("the commit-graph file has incorrect checksum and is likely corrupt"));
909 verify_commit_graph_error = VERIFY_COMMIT_GRAPH_ERROR_HASH;
910 }
911
9bda8467 912 for (i = 0; i < g->num_commits; i++) {
2e3c0737
DS
913 struct commit *graph_commit;
914
9bda8467
DS
915 hashcpy(cur_oid.hash, g->chunk_oid_lookup + g->hash_len * i);
916
917 if (i && oidcmp(&prev_oid, &cur_oid) >= 0)
918 graph_report("commit-graph has incorrect OID order: %s then %s",
919 oid_to_hex(&prev_oid),
920 oid_to_hex(&cur_oid));
921
922 oidcpy(&prev_oid, &cur_oid);
923
924 while (cur_oid.hash[0] > cur_fanout_pos) {
925 uint32_t fanout_value = get_be32(g->chunk_oid_fanout + cur_fanout_pos);
926
927 if (i != fanout_value)
928 graph_report("commit-graph has incorrect fanout value: fanout[%d] = %u != %u",
929 cur_fanout_pos, fanout_value, i);
930 cur_fanout_pos++;
931 }
2e3c0737 932
82952964 933 graph_commit = lookup_commit(r, &cur_oid);
2e3c0737
DS
934 if (!parse_commit_in_graph_one(g, graph_commit))
935 graph_report("failed to parse %s from commit-graph",
936 oid_to_hex(&cur_oid));
9bda8467
DS
937 }
938
939 while (cur_fanout_pos < 256) {
940 uint32_t fanout_value = get_be32(g->chunk_oid_fanout + cur_fanout_pos);
941
942 if (g->num_commits != fanout_value)
943 graph_report("commit-graph has incorrect fanout value: fanout[%d] = %u != %u",
944 cur_fanout_pos, fanout_value, i);
945
946 cur_fanout_pos++;
947 }
948
41df0e30 949 if (verify_commit_graph_error & ~VERIFY_COMMIT_GRAPH_ERROR_HASH)
96af91d4
DS
950 return verify_commit_graph_error;
951
952 for (i = 0; i < g->num_commits; i++) {
2e3c0737 953 struct commit *graph_commit, *odb_commit;
53614b13 954 struct commit_list *graph_parents, *odb_parents;
1373e547 955 uint32_t max_generation = 0;
96af91d4
DS
956
957 hashcpy(cur_oid.hash, g->chunk_oid_lookup + g->hash_len * i);
958
82952964 959 graph_commit = lookup_commit(r, &cur_oid);
96af91d4
DS
960 odb_commit = (struct commit *)create_object(r, cur_oid.hash, alloc_commit_node(r));
961 if (parse_commit_internal(odb_commit, 0, 0)) {
962 graph_report("failed to parse %s from object database",
963 oid_to_hex(&cur_oid));
964 continue;
965 }
2e3c0737
DS
966
967 if (oidcmp(&get_commit_tree_in_graph_one(g, graph_commit)->object.oid,
968 get_commit_tree_oid(odb_commit)))
969 graph_report("root tree OID for commit %s in commit-graph is %s != %s",
970 oid_to_hex(&cur_oid),
971 oid_to_hex(get_commit_tree_oid(graph_commit)),
972 oid_to_hex(get_commit_tree_oid(odb_commit)));
53614b13
DS
973
974 graph_parents = graph_commit->parents;
975 odb_parents = odb_commit->parents;
976
977 while (graph_parents) {
978 if (odb_parents == NULL) {
979 graph_report("commit-graph parent list for commit %s is too long",
980 oid_to_hex(&cur_oid));
981 break;
982 }
983
984 if (oidcmp(&graph_parents->item->object.oid, &odb_parents->item->object.oid))
985 graph_report("commit-graph parent for %s is %s != %s",
986 oid_to_hex(&cur_oid),
987 oid_to_hex(&graph_parents->item->object.oid),
988 oid_to_hex(&odb_parents->item->object.oid));
989
1373e547
DS
990 if (graph_parents->item->generation > max_generation)
991 max_generation = graph_parents->item->generation;
992
53614b13
DS
993 graph_parents = graph_parents->next;
994 odb_parents = odb_parents->next;
995 }
996
997 if (odb_parents != NULL)
998 graph_report("commit-graph parent list for commit %s terminates early",
999 oid_to_hex(&cur_oid));
1373e547
DS
1000
1001 if (!graph_commit->generation) {
1002 if (generation_zero == GENERATION_NUMBER_EXISTS)
1003 graph_report("commit-graph has generation number zero for commit %s, but non-zero elsewhere",
1004 oid_to_hex(&cur_oid));
1005 generation_zero = GENERATION_ZERO_EXISTS;
1006 } else if (generation_zero == GENERATION_ZERO_EXISTS)
1007 graph_report("commit-graph has non-zero generation number for commit %s, but zero elsewhere",
1008 oid_to_hex(&cur_oid));
1009
1010 if (generation_zero == GENERATION_ZERO_EXISTS)
1011 continue;
1012
1013 /*
1014 * If one of our parents has generation GENERATION_NUMBER_MAX, then
1015 * our generation is also GENERATION_NUMBER_MAX. Decrement to avoid
1016 * extra logic in the following condition.
1017 */
1018 if (max_generation == GENERATION_NUMBER_MAX)
1019 max_generation--;
1020
1021 if (graph_commit->generation != max_generation + 1)
1022 graph_report("commit-graph generation for commit %s is %u != %u",
1023 oid_to_hex(&cur_oid),
1024 graph_commit->generation,
1025 max_generation + 1);
88968ebf
DS
1026
1027 if (graph_commit->date != odb_commit->date)
1028 graph_report("commit date for commit %s in commit-graph is %"PRItime" != %"PRItime,
1029 oid_to_hex(&cur_oid),
1030 graph_commit->date,
1031 odb_commit->date);
96af91d4
DS
1032 }
1033
283e68c7
DS
1034 return verify_commit_graph_error;
1035}