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