commit-graph: parse commit from chosen 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
365struct tree *get_commit_tree_in_graph(const struct commit *c)
366{
367 if (c->maybe_tree)
368 return c->maybe_tree;
369 if (c->graph_pos == COMMIT_NOT_FROM_GRAPH)
370 BUG("get_commit_tree_in_graph called from non-commit-graph commit");
371
372 return load_tree_for_commit(commit_graph, (struct commit *)c);
373}
374
08fd81c9
DS
375static void write_graph_chunk_fanout(struct hashfile *f,
376 struct commit **commits,
377 int nr_commits)
378{
379 int i, count = 0;
380 struct commit **list = commits;
381
382 /*
383 * Write the first-level table (the list is sorted,
384 * but we use a 256-entry lookup to be able to avoid
385 * having to do eight extra binary search iterations).
386 */
387 for (i = 0; i < 256; i++) {
388 while (count < nr_commits) {
389 if ((*list)->object.oid.hash[0] != i)
390 break;
391 count++;
392 list++;
393 }
394
395 hashwrite_be32(f, count);
396 }
397}
398
399static void write_graph_chunk_oids(struct hashfile *f, int hash_len,
400 struct commit **commits, int nr_commits)
401{
402 struct commit **list = commits;
403 int count;
404 for (count = 0; count < nr_commits; count++, list++)
405 hashwrite(f, (*list)->object.oid.hash, (int)hash_len);
406}
407
408static const unsigned char *commit_to_sha1(size_t index, void *table)
409{
410 struct commit **commits = table;
411 return commits[index]->object.oid.hash;
412}
413
414static void write_graph_chunk_data(struct hashfile *f, int hash_len,
415 struct commit **commits, int nr_commits)
416{
417 struct commit **list = commits;
418 struct commit **last = commits + nr_commits;
419 uint32_t num_extra_edges = 0;
420
421 while (list < last) {
422 struct commit_list *parent;
423 int edge_value;
424 uint32_t packedDate[2];
425
426 parse_commit(*list);
2e27bd77 427 hashwrite(f, get_commit_tree_oid(*list)->hash, hash_len);
08fd81c9
DS
428
429 parent = (*list)->parents;
430
431 if (!parent)
432 edge_value = GRAPH_PARENT_NONE;
433 else {
434 edge_value = sha1_pos(parent->item->object.oid.hash,
435 commits,
436 nr_commits,
437 commit_to_sha1);
438
439 if (edge_value < 0)
440 edge_value = GRAPH_PARENT_MISSING;
441 }
442
443 hashwrite_be32(f, edge_value);
444
445 if (parent)
446 parent = parent->next;
447
448 if (!parent)
449 edge_value = GRAPH_PARENT_NONE;
450 else if (parent->next)
451 edge_value = GRAPH_OCTOPUS_EDGES_NEEDED | num_extra_edges;
452 else {
453 edge_value = sha1_pos(parent->item->object.oid.hash,
454 commits,
455 nr_commits,
456 commit_to_sha1);
457 if (edge_value < 0)
458 edge_value = GRAPH_PARENT_MISSING;
459 }
460
461 hashwrite_be32(f, edge_value);
462
463 if (edge_value & GRAPH_OCTOPUS_EDGES_NEEDED) {
464 do {
465 num_extra_edges++;
466 parent = parent->next;
467 } while (parent);
468 }
469
470 if (sizeof((*list)->date) > 4)
471 packedDate[0] = htonl(((*list)->date >> 32) & 0x3);
472 else
473 packedDate[0] = 0;
474
3258c663
DS
475 packedDate[0] |= htonl((*list)->generation << 2);
476
08fd81c9
DS
477 packedDate[1] = htonl((*list)->date);
478 hashwrite(f, packedDate, 8);
479
480 list++;
481 }
482}
483
484static void write_graph_chunk_large_edges(struct hashfile *f,
485 struct commit **commits,
486 int nr_commits)
487{
488 struct commit **list = commits;
489 struct commit **last = commits + nr_commits;
490 struct commit_list *parent;
491
492 while (list < last) {
493 int num_parents = 0;
494 for (parent = (*list)->parents; num_parents < 3 && parent;
495 parent = parent->next)
496 num_parents++;
497
498 if (num_parents <= 2) {
499 list++;
500 continue;
501 }
502
503 /* Since num_parents > 2, this initializer is safe. */
504 for (parent = (*list)->parents->next; parent; parent = parent->next) {
505 int edge_value = sha1_pos(parent->item->object.oid.hash,
506 commits,
507 nr_commits,
508 commit_to_sha1);
509
510 if (edge_value < 0)
511 edge_value = GRAPH_PARENT_MISSING;
512 else if (!parent->next)
513 edge_value |= GRAPH_LAST_EDGE;
514
515 hashwrite_be32(f, edge_value);
516 }
517
518 list++;
519 }
520}
521
522static int commit_compare(const void *_a, const void *_b)
523{
524 const struct object_id *a = (const struct object_id *)_a;
525 const struct object_id *b = (const struct object_id *)_b;
526 return oidcmp(a, b);
527}
528
529struct packed_commit_list {
530 struct commit **list;
531 int nr;
532 int alloc;
533};
534
535struct packed_oid_list {
536 struct object_id *list;
537 int nr;
538 int alloc;
539};
540
541static int add_packed_commits(const struct object_id *oid,
542 struct packed_git *pack,
543 uint32_t pos,
544 void *data)
545{
546 struct packed_oid_list *list = (struct packed_oid_list*)data;
547 enum object_type type;
548 off_t offset = nth_packed_object_offset(pack, pos);
549 struct object_info oi = OBJECT_INFO_INIT;
550
551 oi.typep = &type;
fcb6df32 552 if (packed_object_info(the_repository, pack, offset, &oi) < 0)
08fd81c9
DS
553 die("unable to get type of object %s", oid_to_hex(oid));
554
555 if (type != OBJ_COMMIT)
556 return 0;
557
558 ALLOC_GROW(list->list, list->nr + 1, list->alloc);
559 oidcpy(&(list->list[list->nr]), oid);
560 list->nr++;
561
562 return 0;
563}
564
4f2542b4
DS
565static void add_missing_parents(struct packed_oid_list *oids, struct commit *commit)
566{
567 struct commit_list *parent;
568 for (parent = commit->parents; parent; parent = parent->next) {
569 if (!(parent->item->object.flags & UNINTERESTING)) {
570 ALLOC_GROW(oids->list, oids->nr + 1, oids->alloc);
571 oidcpy(&oids->list[oids->nr], &(parent->item->object.oid));
572 oids->nr++;
573 parent->item->object.flags |= UNINTERESTING;
574 }
575 }
576}
577
578static void close_reachable(struct packed_oid_list *oids)
579{
580 int i;
581 struct commit *commit;
582
583 for (i = 0; i < oids->nr; i++) {
584 commit = lookup_commit(&oids->list[i]);
585 if (commit)
586 commit->object.flags |= UNINTERESTING;
587 }
588
589 /*
590 * As this loop runs, oids->nr may grow, but not more
591 * than the number of missing commits in the reachable
592 * closure.
593 */
594 for (i = 0; i < oids->nr; i++) {
595 commit = lookup_commit(&oids->list[i]);
596
597 if (commit && !parse_commit(commit))
598 add_missing_parents(oids, commit);
599 }
600
601 for (i = 0; i < oids->nr; i++) {
602 commit = lookup_commit(&oids->list[i]);
603
604 if (commit)
605 commit->object.flags &= ~UNINTERESTING;
606 }
607}
608
3258c663
DS
609static void compute_generation_numbers(struct packed_commit_list* commits)
610{
611 int i;
612 struct commit_list *list = NULL;
613
614 for (i = 0; i < commits->nr; i++) {
615 if (commits->list[i]->generation != GENERATION_NUMBER_INFINITY &&
616 commits->list[i]->generation != GENERATION_NUMBER_ZERO)
617 continue;
618
619 commit_list_insert(commits->list[i], &list);
620 while (list) {
621 struct commit *current = list->item;
622 struct commit_list *parent;
623 int all_parents_computed = 1;
624 uint32_t max_generation = 0;
625
626 for (parent = current->parents; parent; parent = parent->next) {
627 if (parent->item->generation == GENERATION_NUMBER_INFINITY ||
628 parent->item->generation == GENERATION_NUMBER_ZERO) {
629 all_parents_computed = 0;
630 commit_list_insert(parent->item, &list);
631 break;
632 } else if (parent->item->generation > max_generation) {
633 max_generation = parent->item->generation;
634 }
635 }
636
637 if (all_parents_computed) {
638 current->generation = max_generation + 1;
639 pop_commit(&list);
640
641 if (current->generation > GENERATION_NUMBER_MAX)
642 current->generation = GENERATION_NUMBER_MAX;
643 }
644 }
645 }
646}
647
049d51a2
DS
648void write_commit_graph(const char *obj_dir,
649 const char **pack_indexes,
3d5df01b
DS
650 int nr_packs,
651 const char **commit_hex,
7547b95b
DS
652 int nr_commits,
653 int append)
08fd81c9
DS
654{
655 struct packed_oid_list oids;
656 struct packed_commit_list commits;
657 struct hashfile *f;
658 uint32_t i, count_distinct = 0;
659 char *graph_name;
08fd81c9
DS
660 struct lock_file lk = LOCK_INIT;
661 uint32_t chunk_ids[5];
662 uint64_t chunk_offsets[5];
663 int num_chunks;
664 int num_extra_edges;
665 struct commit_list *parent;
666
667 oids.nr = 0;
668 oids.alloc = approximate_object_count() / 4;
669
7547b95b
DS
670 if (append) {
671 prepare_commit_graph_one(obj_dir);
672 if (commit_graph)
673 oids.alloc += commit_graph->num_commits;
674 }
675
08fd81c9
DS
676 if (oids.alloc < 1024)
677 oids.alloc = 1024;
678 ALLOC_ARRAY(oids.list, oids.alloc);
679
7547b95b
DS
680 if (append && commit_graph) {
681 for (i = 0; i < commit_graph->num_commits; i++) {
682 const unsigned char *hash = commit_graph->chunk_oid_lookup +
683 commit_graph->hash_len * i;
684 hashcpy(oids.list[oids.nr++].hash, hash);
685 }
686 }
687
049d51a2
DS
688 if (pack_indexes) {
689 struct strbuf packname = STRBUF_INIT;
690 int dirlen;
691 strbuf_addf(&packname, "%s/pack/", obj_dir);
692 dirlen = packname.len;
693 for (i = 0; i < nr_packs; i++) {
694 struct packed_git *p;
695 strbuf_setlen(&packname, dirlen);
696 strbuf_addstr(&packname, pack_indexes[i]);
697 p = add_packed_git(packname.buf, packname.len, 1);
698 if (!p)
699 die("error adding pack %s", packname.buf);
700 if (open_pack_index(p))
701 die("error opening index for %s", packname.buf);
702 for_each_object_in_pack(p, add_packed_commits, &oids);
703 close_pack(p);
704 }
705 strbuf_release(&packname);
3d5df01b
DS
706 }
707
708 if (commit_hex) {
709 for (i = 0; i < nr_commits; i++) {
710 const char *end;
711 struct object_id oid;
712 struct commit *result;
713
714 if (commit_hex[i] && parse_oid_hex(commit_hex[i], &oid, &end))
715 continue;
716
717 result = lookup_commit_reference_gently(&oid, 1);
718
719 if (result) {
720 ALLOC_GROW(oids.list, oids.nr + 1, oids.alloc);
721 oidcpy(&oids.list[oids.nr], &(result->object.oid));
722 oids.nr++;
723 }
724 }
725 }
726
727 if (!pack_indexes && !commit_hex)
049d51a2
DS
728 for_each_packed_object(add_packed_commits, &oids, 0);
729
4f2542b4 730 close_reachable(&oids);
08fd81c9
DS
731
732 QSORT(oids.list, oids.nr, commit_compare);
733
734 count_distinct = 1;
735 for (i = 1; i < oids.nr; i++) {
736 if (oidcmp(&oids.list[i-1], &oids.list[i]))
737 count_distinct++;
738 }
739
740 if (count_distinct >= GRAPH_PARENT_MISSING)
741 die(_("the commit graph format cannot write %d commits"), count_distinct);
742
743 commits.nr = 0;
744 commits.alloc = count_distinct;
745 ALLOC_ARRAY(commits.list, commits.alloc);
746
747 num_extra_edges = 0;
748 for (i = 0; i < oids.nr; i++) {
749 int num_parents = 0;
750 if (i > 0 && !oidcmp(&oids.list[i-1], &oids.list[i]))
751 continue;
752
753 commits.list[commits.nr] = lookup_commit(&oids.list[i]);
754 parse_commit(commits.list[commits.nr]);
755
756 for (parent = commits.list[commits.nr]->parents;
757 parent; parent = parent->next)
758 num_parents++;
759
760 if (num_parents > 2)
761 num_extra_edges += num_parents - 1;
762
763 commits.nr++;
764 }
765 num_chunks = num_extra_edges ? 4 : 3;
766
767 if (commits.nr >= GRAPH_PARENT_MISSING)
768 die(_("too many commits to write graph"));
769
3258c663 770 compute_generation_numbers(&commits);
08fd81c9 771
08fd81c9 772 graph_name = get_commit_graph_filename(obj_dir);
33286dcd
DS
773 if (safe_create_leading_directories(graph_name))
774 die_errno(_("unable to create leading directories of %s"),
775 graph_name);
08fd81c9 776
33286dcd 777 hold_lock_file_for_update(&lk, graph_name, LOCK_DIE_ON_ERROR);
08fd81c9
DS
778 f = hashfd(lk.tempfile->fd, lk.tempfile->filename.buf);
779
780 hashwrite_be32(f, GRAPH_SIGNATURE);
781
782 hashwrite_u8(f, GRAPH_VERSION);
783 hashwrite_u8(f, GRAPH_OID_VERSION);
784 hashwrite_u8(f, num_chunks);
785 hashwrite_u8(f, 0); /* unused padding byte */
786
787 chunk_ids[0] = GRAPH_CHUNKID_OIDFANOUT;
788 chunk_ids[1] = GRAPH_CHUNKID_OIDLOOKUP;
789 chunk_ids[2] = GRAPH_CHUNKID_DATA;
790 if (num_extra_edges)
791 chunk_ids[3] = GRAPH_CHUNKID_LARGEEDGES;
792 else
793 chunk_ids[3] = 0;
794 chunk_ids[4] = 0;
795
796 chunk_offsets[0] = 8 + (num_chunks + 1) * GRAPH_CHUNKLOOKUP_WIDTH;
797 chunk_offsets[1] = chunk_offsets[0] + GRAPH_FANOUT_SIZE;
798 chunk_offsets[2] = chunk_offsets[1] + GRAPH_OID_LEN * commits.nr;
799 chunk_offsets[3] = chunk_offsets[2] + (GRAPH_OID_LEN + 16) * commits.nr;
800 chunk_offsets[4] = chunk_offsets[3] + 4 * num_extra_edges;
801
802 for (i = 0; i <= num_chunks; i++) {
803 uint32_t chunk_write[3];
804
805 chunk_write[0] = htonl(chunk_ids[i]);
806 chunk_write[1] = htonl(chunk_offsets[i] >> 32);
807 chunk_write[2] = htonl(chunk_offsets[i] & 0xffffffff);
808 hashwrite(f, chunk_write, 12);
809 }
810
811 write_graph_chunk_fanout(f, commits.list, commits.nr);
812 write_graph_chunk_oids(f, GRAPH_OID_LEN, commits.list, commits.nr);
813 write_graph_chunk_data(f, GRAPH_OID_LEN, commits.list, commits.nr);
814 write_graph_chunk_large_edges(f, commits.list, commits.nr);
815
177722b3 816 close_commit_graph();
08fd81c9
DS
817 finalize_hashfile(f, NULL, CSUM_HASH_IN_STREAM | CSUM_FSYNC);
818 commit_lock_file(&lk);
819
820 free(oids.list);
821 oids.alloc = 0;
822 oids.nr = 0;
823}