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