commit-graph: load a root tree from specific graph
[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"
10#include "revision.h"
11#include "sha1-lookup.h"
12#include "commit-graph.h"
b10edb2d 13#include "object-store.h"
08fd81c9
DS
14
15#define GRAPH_SIGNATURE 0x43475048 /* "CGPH" */
16#define GRAPH_CHUNKID_OIDFANOUT 0x4f494446 /* "OIDF" */
17#define GRAPH_CHUNKID_OIDLOOKUP 0x4f49444c /* "OIDL" */
18#define GRAPH_CHUNKID_DATA 0x43444154 /* "CDAT" */
19#define GRAPH_CHUNKID_LARGEEDGES 0x45444745 /* "EDGE" */
20
21#define GRAPH_DATA_WIDTH 36
22
23#define GRAPH_VERSION_1 0x1
24#define GRAPH_VERSION GRAPH_VERSION_1
25
26#define GRAPH_OID_VERSION_SHA1 1
27#define GRAPH_OID_LEN_SHA1 GIT_SHA1_RAWSZ
28#define GRAPH_OID_VERSION GRAPH_OID_VERSION_SHA1
29#define GRAPH_OID_LEN GRAPH_OID_LEN_SHA1
30
31#define GRAPH_OCTOPUS_EDGES_NEEDED 0x80000000
32#define GRAPH_PARENT_MISSING 0x7fffffff
33#define GRAPH_EDGE_LAST_MASK 0x7fffffff
34#define GRAPH_PARENT_NONE 0x70000000
35
36#define GRAPH_LAST_EDGE 0x80000000
37
0e3b97cc 38#define GRAPH_HEADER_SIZE 8
08fd81c9
DS
39#define GRAPH_FANOUT_SIZE (4 * 256)
40#define GRAPH_CHUNKLOOKUP_WIDTH 12
0e3b97cc
DS
41#define GRAPH_MIN_SIZE (GRAPH_HEADER_SIZE + 4 * GRAPH_CHUNKLOOKUP_WIDTH \
42 + GRAPH_FANOUT_SIZE + GRAPH_OID_LEN)
08fd81c9 43
2a2e32bd 44char *get_commit_graph_filename(const char *obj_dir)
08fd81c9
DS
45{
46 return xstrfmt("%s/info/commit-graph", obj_dir);
47}
48
2a2e32bd
DS
49static struct commit_graph *alloc_commit_graph(void)
50{
51 struct commit_graph *g = xcalloc(1, sizeof(*g));
52 g->graph_fd = -1;
53
54 return g;
55}
56
57struct commit_graph *load_commit_graph_one(const char *graph_file)
58{
59 void *graph_map;
60 const unsigned char *data, *chunk_lookup;
61 size_t graph_size;
62 struct stat st;
63 uint32_t i;
64 struct commit_graph *graph;
65 int fd = git_open(graph_file);
66 uint64_t last_chunk_offset;
67 uint32_t last_chunk_id;
68 uint32_t graph_signature;
69 unsigned char graph_version, hash_version;
70
71 if (fd < 0)
72 return NULL;
73 if (fstat(fd, &st)) {
74 close(fd);
75 return NULL;
76 }
77 graph_size = xsize_t(st.st_size);
78
79 if (graph_size < GRAPH_MIN_SIZE) {
80 close(fd);
81 die("graph file %s is too small", graph_file);
82 }
83 graph_map = xmmap(NULL, graph_size, PROT_READ, MAP_PRIVATE, fd, 0);
84 data = (const unsigned char *)graph_map;
85
86 graph_signature = get_be32(data);
87 if (graph_signature != GRAPH_SIGNATURE) {
88 error("graph signature %X does not match signature %X",
89 graph_signature, GRAPH_SIGNATURE);
90 goto cleanup_fail;
91 }
92
93 graph_version = *(unsigned char*)(data + 4);
94 if (graph_version != GRAPH_VERSION) {
95 error("graph version %X does not match version %X",
96 graph_version, GRAPH_VERSION);
97 goto cleanup_fail;
98 }
99
100 hash_version = *(unsigned char*)(data + 5);
101 if (hash_version != GRAPH_OID_VERSION) {
102 error("hash version %X does not match version %X",
103 hash_version, GRAPH_OID_VERSION);
104 goto cleanup_fail;
105 }
106
107 graph = alloc_commit_graph();
108
109 graph->hash_len = GRAPH_OID_LEN;
110 graph->num_chunks = *(unsigned char*)(data + 6);
111 graph->graph_fd = fd;
112 graph->data = graph_map;
113 graph->data_len = graph_size;
114
115 last_chunk_id = 0;
116 last_chunk_offset = 8;
117 chunk_lookup = data + 8;
118 for (i = 0; i < graph->num_chunks; i++) {
119 uint32_t chunk_id = get_be32(chunk_lookup + 0);
120 uint64_t chunk_offset = get_be64(chunk_lookup + 4);
121 int chunk_repeated = 0;
122
123 chunk_lookup += GRAPH_CHUNKLOOKUP_WIDTH;
124
125 if (chunk_offset > graph_size - GIT_MAX_RAWSZ) {
126 error("improper chunk offset %08x%08x", (uint32_t)(chunk_offset >> 32),
127 (uint32_t)chunk_offset);
128 goto cleanup_fail;
129 }
130
131 switch (chunk_id) {
132 case GRAPH_CHUNKID_OIDFANOUT:
133 if (graph->chunk_oid_fanout)
134 chunk_repeated = 1;
135 else
136 graph->chunk_oid_fanout = (uint32_t*)(data + chunk_offset);
137 break;
138
139 case GRAPH_CHUNKID_OIDLOOKUP:
140 if (graph->chunk_oid_lookup)
141 chunk_repeated = 1;
142 else
143 graph->chunk_oid_lookup = data + chunk_offset;
144 break;
145
146 case GRAPH_CHUNKID_DATA:
147 if (graph->chunk_commit_data)
148 chunk_repeated = 1;
149 else
150 graph->chunk_commit_data = data + chunk_offset;
151 break;
152
153 case GRAPH_CHUNKID_LARGEEDGES:
154 if (graph->chunk_large_edges)
155 chunk_repeated = 1;
156 else
157 graph->chunk_large_edges = data + chunk_offset;
158 break;
159 }
160
161 if (chunk_repeated) {
162 error("chunk id %08x appears multiple times", chunk_id);
163 goto cleanup_fail;
164 }
165
166 if (last_chunk_id == GRAPH_CHUNKID_OIDLOOKUP)
167 {
168 graph->num_commits = (chunk_offset - last_chunk_offset)
169 / graph->hash_len;
170 }
171
172 last_chunk_id = chunk_id;
173 last_chunk_offset = chunk_offset;
174 }
175
176 return graph;
177
178cleanup_fail:
179 munmap(graph_map, graph_size);
180 close(fd);
181 exit(1);
182}
183
177722b3
DS
184/* global storage */
185static struct commit_graph *commit_graph = NULL;
186
187static void prepare_commit_graph_one(const char *obj_dir)
188{
189 char *graph_name;
190
191 if (commit_graph)
192 return;
193
194 graph_name = get_commit_graph_filename(obj_dir);
195 commit_graph = load_commit_graph_one(graph_name);
196
197 FREE_AND_NULL(graph_name);
198}
199
200static int prepare_commit_graph_run_once = 0;
201static void prepare_commit_graph(void)
202{
203 struct alternate_object_database *alt;
204 char *obj_dir;
205
206 if (prepare_commit_graph_run_once)
207 return;
208 prepare_commit_graph_run_once = 1;
209
210 obj_dir = get_object_directory();
211 prepare_commit_graph_one(obj_dir);
b10edb2d
JH
212 prepare_alt_odb(the_repository);
213 for (alt = the_repository->objects->alt_odb_list;
214 !commit_graph && alt;
215 alt = alt->next)
177722b3
DS
216 prepare_commit_graph_one(alt->path);
217}
218
219static void close_commit_graph(void)
220{
221 if (!commit_graph)
222 return;
223
224 if (commit_graph->graph_fd >= 0) {
225 munmap((void *)commit_graph->data, commit_graph->data_len);
226 commit_graph->data = NULL;
227 close(commit_graph->graph_fd);
228 }
229
230 FREE_AND_NULL(commit_graph);
231}
232
233static int bsearch_graph(struct commit_graph *g, struct object_id *oid, uint32_t *pos)
234{
235 return bsearch_hash(oid->hash, g->chunk_oid_fanout,
236 g->chunk_oid_lookup, g->hash_len, pos);
237}
238
239static struct commit_list **insert_parent_or_die(struct commit_graph *g,
240 uint64_t pos,
241 struct commit_list **pptr)
242{
243 struct commit *c;
244 struct object_id oid;
245 hashcpy(oid.hash, g->chunk_oid_lookup + g->hash_len * pos);
246 c = lookup_commit(&oid);
247 if (!c)
248 die("could not find commit %s", oid_to_hex(&oid));
249 c->graph_pos = pos;
250 return &commit_list_insert(c, pptr)->next;
251}
252
e2838d85
DS
253static void fill_commit_graph_info(struct commit *item, struct commit_graph *g, uint32_t pos)
254{
255 const unsigned char *commit_data = g->chunk_commit_data + GRAPH_DATA_WIDTH * pos;
256 item->graph_pos = pos;
257 item->generation = get_be32(commit_data + g->hash_len + 8) >> 2;
258}
259
177722b3
DS
260static int fill_commit_in_graph(struct commit *item, struct commit_graph *g, uint32_t pos)
261{
177722b3
DS
262 uint32_t edge_value;
263 uint32_t *parent_data_ptr;
264 uint64_t date_low, date_high;
265 struct commit_list **pptr;
266 const unsigned char *commit_data = g->chunk_commit_data + (g->hash_len + 16) * pos;
267
268 item->object.parsed = 1;
269 item->graph_pos = pos;
270
7b8a21db 271 item->maybe_tree = NULL;
177722b3
DS
272
273 date_high = get_be32(commit_data + g->hash_len + 8) & 0x3;
274 date_low = get_be32(commit_data + g->hash_len + 12);
275 item->date = (timestamp_t)((date_high << 32) | date_low);
276
83073cc9
DS
277 item->generation = get_be32(commit_data + g->hash_len + 8) >> 2;
278
177722b3
DS
279 pptr = &item->parents;
280
281 edge_value = get_be32(commit_data + g->hash_len);
282 if (edge_value == GRAPH_PARENT_NONE)
283 return 1;
284 pptr = insert_parent_or_die(g, edge_value, pptr);
285
286 edge_value = get_be32(commit_data + g->hash_len + 4);
287 if (edge_value == GRAPH_PARENT_NONE)
288 return 1;
289 if (!(edge_value & GRAPH_OCTOPUS_EDGES_NEEDED)) {
290 pptr = insert_parent_or_die(g, edge_value, pptr);
291 return 1;
292 }
293
294 parent_data_ptr = (uint32_t*)(g->chunk_large_edges +
295 4 * (uint64_t)(edge_value & GRAPH_EDGE_LAST_MASK));
296 do {
297 edge_value = get_be32(parent_data_ptr);
298 pptr = insert_parent_or_die(g,
299 edge_value & GRAPH_EDGE_LAST_MASK,
300 pptr);
301 parent_data_ptr++;
302 } while (!(edge_value & GRAPH_LAST_EDGE));
303
304 return 1;
305}
306
e2838d85
DS
307static int find_commit_in_graph(struct commit *item, struct commit_graph *g, uint32_t *pos)
308{
309 if (item->graph_pos != COMMIT_NOT_FROM_GRAPH) {
310 *pos = item->graph_pos;
311 return 1;
312 } else {
313 return bsearch_graph(g, &(item->object.oid), pos);
314 }
315}
316
ee797053 317static int parse_commit_in_graph_one(struct commit_graph *g, struct commit *item)
177722b3 318{
e2838d85
DS
319 uint32_t pos;
320
177722b3
DS
321 if (!core_commit_graph)
322 return 0;
323 if (item->object.parsed)
324 return 1;
ee797053
DS
325
326 if (find_commit_in_graph(item, g, &pos))
327 return fill_commit_in_graph(item, g, pos);
328
329 return 0;
330}
331
332int parse_commit_in_graph(struct commit *item)
333{
334 if (!core_commit_graph)
335 return 0;
336
177722b3 337 prepare_commit_graph();
ee797053
DS
338 if (commit_graph)
339 return parse_commit_in_graph_one(commit_graph, item);
177722b3
DS
340 return 0;
341}
342
e2838d85
DS
343void load_commit_graph_info(struct commit *item)
344{
345 uint32_t pos;
346 if (!core_commit_graph)
347 return;
348 prepare_commit_graph();
349 if (commit_graph && find_commit_in_graph(item, commit_graph, &pos))
350 fill_commit_graph_info(item, commit_graph, pos);
351}
352
7b8a21db
DS
353static struct tree *load_tree_for_commit(struct commit_graph *g, struct commit *c)
354{
355 struct object_id oid;
356 const unsigned char *commit_data = g->chunk_commit_data +
357 GRAPH_DATA_WIDTH * (c->graph_pos);
358
359 hashcpy(oid.hash, commit_data);
360 c->maybe_tree = lookup_tree(&oid);
361
362 return c->maybe_tree;
363}
364
0cbef8f8
DS
365static struct tree *get_commit_tree_in_graph_one(struct commit_graph *g,
366 const struct commit *c)
7b8a21db
DS
367{
368 if (c->maybe_tree)
369 return c->maybe_tree;
370 if (c->graph_pos == COMMIT_NOT_FROM_GRAPH)
0cbef8f8
DS
371 BUG("get_commit_tree_in_graph_one called from non-commit-graph commit");
372
373 return load_tree_for_commit(g, (struct commit *)c);
374}
7b8a21db 375
0cbef8f8
DS
376struct tree *get_commit_tree_in_graph(const struct commit *c)
377{
378 return get_commit_tree_in_graph_one(commit_graph, c);
7b8a21db
DS
379}
380
08fd81c9
DS
381static void write_graph_chunk_fanout(struct hashfile *f,
382 struct commit **commits,
383 int nr_commits)
384{
385 int i, count = 0;
386 struct commit **list = commits;
387
388 /*
389 * Write the first-level table (the list is sorted,
390 * but we use a 256-entry lookup to be able to avoid
391 * having to do eight extra binary search iterations).
392 */
393 for (i = 0; i < 256; i++) {
394 while (count < nr_commits) {
395 if ((*list)->object.oid.hash[0] != i)
396 break;
397 count++;
398 list++;
399 }
400
401 hashwrite_be32(f, count);
402 }
403}
404
405static void write_graph_chunk_oids(struct hashfile *f, int hash_len,
406 struct commit **commits, int nr_commits)
407{
408 struct commit **list = commits;
409 int count;
410 for (count = 0; count < nr_commits; count++, list++)
411 hashwrite(f, (*list)->object.oid.hash, (int)hash_len);
412}
413
414static const unsigned char *commit_to_sha1(size_t index, void *table)
415{
416 struct commit **commits = table;
417 return commits[index]->object.oid.hash;
418}
419
420static void write_graph_chunk_data(struct hashfile *f, int hash_len,
421 struct commit **commits, int nr_commits)
422{
423 struct commit **list = commits;
424 struct commit **last = commits + nr_commits;
425 uint32_t num_extra_edges = 0;
426
427 while (list < last) {
428 struct commit_list *parent;
429 int edge_value;
430 uint32_t packedDate[2];
431
432 parse_commit(*list);
2e27bd77 433 hashwrite(f, get_commit_tree_oid(*list)->hash, hash_len);
08fd81c9
DS
434
435 parent = (*list)->parents;
436
437 if (!parent)
438 edge_value = GRAPH_PARENT_NONE;
439 else {
440 edge_value = sha1_pos(parent->item->object.oid.hash,
441 commits,
442 nr_commits,
443 commit_to_sha1);
444
445 if (edge_value < 0)
446 edge_value = GRAPH_PARENT_MISSING;
447 }
448
449 hashwrite_be32(f, edge_value);
450
451 if (parent)
452 parent = parent->next;
453
454 if (!parent)
455 edge_value = GRAPH_PARENT_NONE;
456 else if (parent->next)
457 edge_value = GRAPH_OCTOPUS_EDGES_NEEDED | num_extra_edges;
458 else {
459 edge_value = sha1_pos(parent->item->object.oid.hash,
460 commits,
461 nr_commits,
462 commit_to_sha1);
463 if (edge_value < 0)
464 edge_value = GRAPH_PARENT_MISSING;
465 }
466
467 hashwrite_be32(f, edge_value);
468
469 if (edge_value & GRAPH_OCTOPUS_EDGES_NEEDED) {
470 do {
471 num_extra_edges++;
472 parent = parent->next;
473 } while (parent);
474 }
475
476 if (sizeof((*list)->date) > 4)
477 packedDate[0] = htonl(((*list)->date >> 32) & 0x3);
478 else
479 packedDate[0] = 0;
480
3258c663
DS
481 packedDate[0] |= htonl((*list)->generation << 2);
482
08fd81c9
DS
483 packedDate[1] = htonl((*list)->date);
484 hashwrite(f, packedDate, 8);
485
486 list++;
487 }
488}
489
490static void write_graph_chunk_large_edges(struct hashfile *f,
491 struct commit **commits,
492 int nr_commits)
493{
494 struct commit **list = commits;
495 struct commit **last = commits + nr_commits;
496 struct commit_list *parent;
497
498 while (list < last) {
499 int num_parents = 0;
500 for (parent = (*list)->parents; num_parents < 3 && parent;
501 parent = parent->next)
502 num_parents++;
503
504 if (num_parents <= 2) {
505 list++;
506 continue;
507 }
508
509 /* Since num_parents > 2, this initializer is safe. */
510 for (parent = (*list)->parents->next; parent; parent = parent->next) {
511 int edge_value = sha1_pos(parent->item->object.oid.hash,
512 commits,
513 nr_commits,
514 commit_to_sha1);
515
516 if (edge_value < 0)
517 edge_value = GRAPH_PARENT_MISSING;
518 else if (!parent->next)
519 edge_value |= GRAPH_LAST_EDGE;
520
521 hashwrite_be32(f, edge_value);
522 }
523
524 list++;
525 }
526}
527
528static int commit_compare(const void *_a, const void *_b)
529{
530 const struct object_id *a = (const struct object_id *)_a;
531 const struct object_id *b = (const struct object_id *)_b;
532 return oidcmp(a, b);
533}
534
535struct packed_commit_list {
536 struct commit **list;
537 int nr;
538 int alloc;
539};
540
541struct packed_oid_list {
542 struct object_id *list;
543 int nr;
544 int alloc;
545};
546
547static int add_packed_commits(const struct object_id *oid,
548 struct packed_git *pack,
549 uint32_t pos,
550 void *data)
551{
552 struct packed_oid_list *list = (struct packed_oid_list*)data;
553 enum object_type type;
554 off_t offset = nth_packed_object_offset(pack, pos);
555 struct object_info oi = OBJECT_INFO_INIT;
556
557 oi.typep = &type;
fcb6df32 558 if (packed_object_info(the_repository, pack, offset, &oi) < 0)
08fd81c9
DS
559 die("unable to get type of object %s", oid_to_hex(oid));
560
561 if (type != OBJ_COMMIT)
562 return 0;
563
564 ALLOC_GROW(list->list, list->nr + 1, list->alloc);
565 oidcpy(&(list->list[list->nr]), oid);
566 list->nr++;
567
568 return 0;
569}
570
4f2542b4
DS
571static void add_missing_parents(struct packed_oid_list *oids, struct commit *commit)
572{
573 struct commit_list *parent;
574 for (parent = commit->parents; parent; parent = parent->next) {
575 if (!(parent->item->object.flags & UNINTERESTING)) {
576 ALLOC_GROW(oids->list, oids->nr + 1, oids->alloc);
577 oidcpy(&oids->list[oids->nr], &(parent->item->object.oid));
578 oids->nr++;
579 parent->item->object.flags |= UNINTERESTING;
580 }
581 }
582}
583
584static void close_reachable(struct packed_oid_list *oids)
585{
586 int i;
587 struct commit *commit;
588
589 for (i = 0; i < oids->nr; i++) {
590 commit = lookup_commit(&oids->list[i]);
591 if (commit)
592 commit->object.flags |= UNINTERESTING;
593 }
594
595 /*
596 * As this loop runs, oids->nr may grow, but not more
597 * than the number of missing commits in the reachable
598 * closure.
599 */
600 for (i = 0; i < oids->nr; i++) {
601 commit = lookup_commit(&oids->list[i]);
602
603 if (commit && !parse_commit(commit))
604 add_missing_parents(oids, commit);
605 }
606
607 for (i = 0; i < oids->nr; i++) {
608 commit = lookup_commit(&oids->list[i]);
609
610 if (commit)
611 commit->object.flags &= ~UNINTERESTING;
612 }
613}
614
3258c663
DS
615static void compute_generation_numbers(struct packed_commit_list* commits)
616{
617 int i;
618 struct commit_list *list = NULL;
619
620 for (i = 0; i < commits->nr; i++) {
621 if (commits->list[i]->generation != GENERATION_NUMBER_INFINITY &&
622 commits->list[i]->generation != GENERATION_NUMBER_ZERO)
623 continue;
624
625 commit_list_insert(commits->list[i], &list);
626 while (list) {
627 struct commit *current = list->item;
628 struct commit_list *parent;
629 int all_parents_computed = 1;
630 uint32_t max_generation = 0;
631
632 for (parent = current->parents; parent; parent = parent->next) {
633 if (parent->item->generation == GENERATION_NUMBER_INFINITY ||
634 parent->item->generation == GENERATION_NUMBER_ZERO) {
635 all_parents_computed = 0;
636 commit_list_insert(parent->item, &list);
637 break;
638 } else if (parent->item->generation > max_generation) {
639 max_generation = parent->item->generation;
640 }
641 }
642
643 if (all_parents_computed) {
644 current->generation = max_generation + 1;
645 pop_commit(&list);
646
647 if (current->generation > GENERATION_NUMBER_MAX)
648 current->generation = GENERATION_NUMBER_MAX;
649 }
650 }
651 }
652}
653
049d51a2
DS
654void write_commit_graph(const char *obj_dir,
655 const char **pack_indexes,
3d5df01b
DS
656 int nr_packs,
657 const char **commit_hex,
7547b95b
DS
658 int nr_commits,
659 int append)
08fd81c9
DS
660{
661 struct packed_oid_list oids;
662 struct packed_commit_list commits;
663 struct hashfile *f;
664 uint32_t i, count_distinct = 0;
665 char *graph_name;
08fd81c9
DS
666 struct lock_file lk = LOCK_INIT;
667 uint32_t chunk_ids[5];
668 uint64_t chunk_offsets[5];
669 int num_chunks;
670 int num_extra_edges;
671 struct commit_list *parent;
672
673 oids.nr = 0;
674 oids.alloc = approximate_object_count() / 4;
675
7547b95b
DS
676 if (append) {
677 prepare_commit_graph_one(obj_dir);
678 if (commit_graph)
679 oids.alloc += commit_graph->num_commits;
680 }
681
08fd81c9
DS
682 if (oids.alloc < 1024)
683 oids.alloc = 1024;
684 ALLOC_ARRAY(oids.list, oids.alloc);
685
7547b95b
DS
686 if (append && commit_graph) {
687 for (i = 0; i < commit_graph->num_commits; i++) {
688 const unsigned char *hash = commit_graph->chunk_oid_lookup +
689 commit_graph->hash_len * i;
690 hashcpy(oids.list[oids.nr++].hash, hash);
691 }
692 }
693
049d51a2
DS
694 if (pack_indexes) {
695 struct strbuf packname = STRBUF_INIT;
696 int dirlen;
697 strbuf_addf(&packname, "%s/pack/", obj_dir);
698 dirlen = packname.len;
699 for (i = 0; i < nr_packs; i++) {
700 struct packed_git *p;
701 strbuf_setlen(&packname, dirlen);
702 strbuf_addstr(&packname, pack_indexes[i]);
703 p = add_packed_git(packname.buf, packname.len, 1);
704 if (!p)
705 die("error adding pack %s", packname.buf);
706 if (open_pack_index(p))
707 die("error opening index for %s", packname.buf);
708 for_each_object_in_pack(p, add_packed_commits, &oids);
709 close_pack(p);
710 }
711 strbuf_release(&packname);
3d5df01b
DS
712 }
713
714 if (commit_hex) {
715 for (i = 0; i < nr_commits; i++) {
716 const char *end;
717 struct object_id oid;
718 struct commit *result;
719
720 if (commit_hex[i] && parse_oid_hex(commit_hex[i], &oid, &end))
721 continue;
722
723 result = lookup_commit_reference_gently(&oid, 1);
724
725 if (result) {
726 ALLOC_GROW(oids.list, oids.nr + 1, oids.alloc);
727 oidcpy(&oids.list[oids.nr], &(result->object.oid));
728 oids.nr++;
729 }
730 }
731 }
732
733 if (!pack_indexes && !commit_hex)
049d51a2
DS
734 for_each_packed_object(add_packed_commits, &oids, 0);
735
4f2542b4 736 close_reachable(&oids);
08fd81c9
DS
737
738 QSORT(oids.list, oids.nr, commit_compare);
739
740 count_distinct = 1;
741 for (i = 1; i < oids.nr; i++) {
742 if (oidcmp(&oids.list[i-1], &oids.list[i]))
743 count_distinct++;
744 }
745
746 if (count_distinct >= GRAPH_PARENT_MISSING)
747 die(_("the commit graph format cannot write %d commits"), count_distinct);
748
749 commits.nr = 0;
750 commits.alloc = count_distinct;
751 ALLOC_ARRAY(commits.list, commits.alloc);
752
753 num_extra_edges = 0;
754 for (i = 0; i < oids.nr; i++) {
755 int num_parents = 0;
756 if (i > 0 && !oidcmp(&oids.list[i-1], &oids.list[i]))
757 continue;
758
759 commits.list[commits.nr] = lookup_commit(&oids.list[i]);
760 parse_commit(commits.list[commits.nr]);
761
762 for (parent = commits.list[commits.nr]->parents;
763 parent; parent = parent->next)
764 num_parents++;
765
766 if (num_parents > 2)
767 num_extra_edges += num_parents - 1;
768
769 commits.nr++;
770 }
771 num_chunks = num_extra_edges ? 4 : 3;
772
773 if (commits.nr >= GRAPH_PARENT_MISSING)
774 die(_("too many commits to write graph"));
775
3258c663 776 compute_generation_numbers(&commits);
08fd81c9 777
08fd81c9 778 graph_name = get_commit_graph_filename(obj_dir);
33286dcd
DS
779 if (safe_create_leading_directories(graph_name))
780 die_errno(_("unable to create leading directories of %s"),
781 graph_name);
08fd81c9 782
33286dcd 783 hold_lock_file_for_update(&lk, graph_name, LOCK_DIE_ON_ERROR);
08fd81c9
DS
784 f = hashfd(lk.tempfile->fd, lk.tempfile->filename.buf);
785
786 hashwrite_be32(f, GRAPH_SIGNATURE);
787
788 hashwrite_u8(f, GRAPH_VERSION);
789 hashwrite_u8(f, GRAPH_OID_VERSION);
790 hashwrite_u8(f, num_chunks);
791 hashwrite_u8(f, 0); /* unused padding byte */
792
793 chunk_ids[0] = GRAPH_CHUNKID_OIDFANOUT;
794 chunk_ids[1] = GRAPH_CHUNKID_OIDLOOKUP;
795 chunk_ids[2] = GRAPH_CHUNKID_DATA;
796 if (num_extra_edges)
797 chunk_ids[3] = GRAPH_CHUNKID_LARGEEDGES;
798 else
799 chunk_ids[3] = 0;
800 chunk_ids[4] = 0;
801
802 chunk_offsets[0] = 8 + (num_chunks + 1) * GRAPH_CHUNKLOOKUP_WIDTH;
803 chunk_offsets[1] = chunk_offsets[0] + GRAPH_FANOUT_SIZE;
804 chunk_offsets[2] = chunk_offsets[1] + GRAPH_OID_LEN * commits.nr;
805 chunk_offsets[3] = chunk_offsets[2] + (GRAPH_OID_LEN + 16) * commits.nr;
806 chunk_offsets[4] = chunk_offsets[3] + 4 * num_extra_edges;
807
808 for (i = 0; i <= num_chunks; i++) {
809 uint32_t chunk_write[3];
810
811 chunk_write[0] = htonl(chunk_ids[i]);
812 chunk_write[1] = htonl(chunk_offsets[i] >> 32);
813 chunk_write[2] = htonl(chunk_offsets[i] & 0xffffffff);
814 hashwrite(f, chunk_write, 12);
815 }
816
817 write_graph_chunk_fanout(f, commits.list, commits.nr);
818 write_graph_chunk_oids(f, GRAPH_OID_LEN, commits.list, commits.nr);
819 write_graph_chunk_data(f, GRAPH_OID_LEN, commits.list, commits.nr);
820 write_graph_chunk_large_edges(f, commits.list, commits.nr);
821
177722b3 822 close_commit_graph();
08fd81c9
DS
823 finalize_hashfile(f, NULL, CSUM_HASH_IN_STREAM | CSUM_FSYNC);
824 commit_lock_file(&lk);
825
826 free(oids.list);
827 oids.alloc = 0;
828 oids.nr = 0;
829}