?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
docs: document SHA-256 pack and indices
[git.git] / commit-graph.c
blobe51c91dd5b0af4e4946091e5ca7f06707b3a0c5b
1 #include "git-compat-util.h"
2 #include "config.h"
3 #include "lockfile.h"
4 #include "pack.h"
5 #include "packfile.h"
6 #include "commit.h"
7 #include "object.h"
8 #include "refs.h"
9 #include "revision.h"
10 #include "sha1-lookup.h"
11 #include "commit-graph.h"
12 #include "object-store.h"
13 #include "alloc.h"
14 #include "hashmap.h"
15 #include "replace-object.h"
16 #include "progress.h"
17 #include "bloom.h"
18 #include "commit-slab.h"
19 #include "shallow.h"
20 #include "json-writer.h"
21 #include "trace2.h"
22
23 void git_test_write_commit_graph_or_die(void)
24 {
25 int flags = 0;
26 if (!git_env_bool(GIT_TEST_COMMIT_GRAPH, 0))
27 return;
28
29 if (git_env_bool(GIT_TEST_COMMIT_GRAPH_CHANGED_PATHS, 0))
30 flags = COMMIT_GRAPH_WRITE_BLOOM_FILTERS;
31
32 if (write_commit_graph_reachable(the_repository->objects->odb,
33 flags, NULL))
34 die("failed to write commit-graph under GIT_TEST_COMMIT_GRAPH");
35 }
36
37 #define GRAPH_SIGNATURE 0x43475048 /* "CGPH" */
38 #define GRAPH_CHUNKID_OIDFANOUT 0x4f494446 /* "OIDF" */
39 #define GRAPH_CHUNKID_OIDLOOKUP 0x4f49444c /* "OIDL" */
40 #define GRAPH_CHUNKID_DATA 0x43444154 /* "CDAT" */
41 #define GRAPH_CHUNKID_EXTRAEDGES 0x45444745 /* "EDGE" */
42 #define GRAPH_CHUNKID_BLOOMINDEXES 0x42494458 /* "BIDX" */
43 #define GRAPH_CHUNKID_BLOOMDATA 0x42444154 /* "BDAT" */
44 #define GRAPH_CHUNKID_BASE 0x42415345 /* "BASE" */
45 #define MAX_NUM_CHUNKS 7
46
47 #define GRAPH_DATA_WIDTH (the_hash_algo->rawsz + 16)
48
49 #define GRAPH_VERSION_1 0x1
50 #define GRAPH_VERSION GRAPH_VERSION_1
51
52 #define GRAPH_EXTRA_EDGES_NEEDED 0x80000000
53 #define GRAPH_EDGE_LAST_MASK 0x7fffffff
54 #define GRAPH_PARENT_NONE 0x70000000
55
56 #define GRAPH_LAST_EDGE 0x80000000
57
58 #define GRAPH_HEADER_SIZE 8
59 #define GRAPH_FANOUT_SIZE (4 * 256)
60 #define GRAPH_CHUNKLOOKUP_WIDTH 12
61 #define GRAPH_MIN_SIZE (GRAPH_HEADER_SIZE + 4 * GRAPH_CHUNKLOOKUP_WIDTH \
62 + GRAPH_FANOUT_SIZE + the_hash_algo->rawsz)
63
64 /* Remember to update object flag allocation in object.h */
65 #define REACHABLE (1u<<15)
66
67 /* Keep track of the order in which commits are added to our list. */
68 define_commit_slab(commit_pos, int);
69 static struct commit_pos commit_pos = COMMIT_SLAB_INIT(1, commit_pos);
70
71 static void set_commit_pos(struct repository *r, const struct object_id *oid)
72 {
73 static int32_t max_pos;
74 struct commit *commit = lookup_commit(r, oid);
75
76 if (!commit)
77 return; /* should never happen, but be lenient */
78
79 *commit_pos_at(&commit_pos, commit) = max_pos++;
80 }
81
82 static int commit_pos_cmp(const void *va, const void *vb)
83 {
84 const struct commit *a = *(const struct commit **)va;
85 const struct commit *b = *(const struct commit **)vb;
86 return commit_pos_at(&commit_pos, a) -
87 commit_pos_at(&commit_pos, b);
88 }
89
90 define_commit_slab(commit_graph_data_slab, struct commit_graph_data);
91 static struct commit_graph_data_slab commit_graph_data_slab =
92 COMMIT_SLAB_INIT(1, commit_graph_data_slab);
93
94 uint32_t commit_graph_position(const struct commit *c)
95 {
96 struct commit_graph_data *data =
97 commit_graph_data_slab_peek(&commit_graph_data_slab, c);
98
99 return data ? data->graph_pos : COMMIT_NOT_FROM_GRAPH;
100 }
101
102 uint32_t commit_graph_generation(const struct commit *c)
103 {
104 struct commit_graph_data *data =
105 commit_graph_data_slab_peek(&commit_graph_data_slab, c);
106
107 if (!data)
108 return GENERATION_NUMBER_INFINITY;
109 else if (data->graph_pos == COMMIT_NOT_FROM_GRAPH)
110 return GENERATION_NUMBER_INFINITY;
111
112 return data->generation;
113 }
114
115 static struct commit_graph_data *commit_graph_data_at(const struct commit *c)
116 {
117 unsigned int i, nth_slab;
118 struct commit_graph_data *data =
119 commit_graph_data_slab_peek(&commit_graph_data_slab, c);
120
121 if (data)
122 return data;
123
124 nth_slab = c->index / commit_graph_data_slab.slab_size;
125 data = commit_graph_data_slab_at(&commit_graph_data_slab, c);
126
127 /*
128 * commit-slab initializes elements with zero, overwrite this with
129 * COMMIT_NOT_FROM_GRAPH for graph_pos.
130 *
131 * We avoid initializing generation with checking if graph position
132 * is not COMMIT_NOT_FROM_GRAPH.
133 */
134 for (i = 0; i < commit_graph_data_slab.slab_size; i++) {
135 commit_graph_data_slab.slab[nth_slab][i].graph_pos =
136 COMMIT_NOT_FROM_GRAPH;
137 }
138
139 return data;
140 }
141
142 static int commit_gen_cmp(const void *va, const void *vb)
143 {
144 const struct commit *a = *(const struct commit **)va;
145 const struct commit *b = *(const struct commit **)vb;
146
147 uint32_t generation_a = commit_graph_generation(a);
148 uint32_t generation_b = commit_graph_generation(b);
149 /* lower generation commits first */
150 if (generation_a < generation_b)
151 return -1;
152 else if (generation_a > generation_b)
153 return 1;
154
155 /* use date as a heuristic when generations are equal */
156 if (a->date < b->date)
157 return -1;
158 else if (a->date > b->date)
159 return 1;
160 return 0;
161 }
162
163 char *get_commit_graph_filename(struct object_directory *obj_dir)
164 {
165 return xstrfmt("%s/info/commit-graph", obj_dir->path);
166 }
167
168 static char *get_split_graph_filename(struct object_directory *odb,
169 const char *oid_hex)
170 {
171 return xstrfmt("%s/info/commit-graphs/graph-%s.graph", odb->path,
172 oid_hex);
173 }
174
175 static char *get_chain_filename(struct object_directory *odb)
176 {
177 return xstrfmt("%s/info/commit-graphs/commit-graph-chain", odb->path);
178 }
179
180 static uint8_t oid_version(void)
181 {
182 return 1;
183 }
184
185 static struct commit_graph *alloc_commit_graph(void)
186 {
187 struct commit_graph *g = xcalloc(1, sizeof(*g));
188
189 return g;
190 }
191
192 extern int read_replace_refs;
193
194 static int commit_graph_compatible(struct repository *r)
195 {
196 if (!r->gitdir)
197 return 0;
198
199 if (read_replace_refs) {
200 prepare_replace_object(r);
201 if (hashmap_get_size(&r->objects->replace_map->map))
202 return 0;
203 }
204
205 prepare_commit_graft(r);
206 if (r->parsed_objects &&
207 (r->parsed_objects->grafts_nr || r->parsed_objects->substituted_parent))
208 return 0;
209 if (is_repository_shallow(r))
210 return 0;
211
212 return 1;
213 }
214
215 int open_commit_graph(const char *graph_file, int *fd, struct stat *st)
216 {
217 *fd = git_open(graph_file);
218 if (*fd < 0)
219 return 0;
220 if (fstat(*fd, st)) {
221 close(*fd);
222 return 0;
223 }
224 return 1;
225 }
226
227 struct commit_graph *load_commit_graph_one_fd_st(int fd, struct stat *st,
228 struct object_directory *odb)
229 {
230 void *graph_map;
231 size_t graph_size;
232 struct commit_graph *ret;
233
234 graph_size = xsize_t(st->st_size);
235
236 if (graph_size < GRAPH_MIN_SIZE) {
237 close(fd);
238 error(_("commit-graph file is too small"));
239 return NULL;
240 }
241 graph_map = xmmap(NULL, graph_size, PROT_READ, MAP_PRIVATE, fd, 0);
242 close(fd);
243 ret = parse_commit_graph(graph_map, graph_size);
244
245 if (ret)
246 ret->odb = odb;
247 else
248 munmap(graph_map, graph_size);
249
250 return ret;
251 }
252
253 static int verify_commit_graph_lite(struct commit_graph *g)
254 {
255 /*
256 * Basic validation shared between parse_commit_graph()
257 * which'll be called every time the graph is used, and the
258 * much more expensive verify_commit_graph() used by
259 * "commit-graph verify".
260 *
261 * There should only be very basic checks here to ensure that
262 * we don't e.g. segfault in fill_commit_in_graph(), but
263 * because this is a very hot codepath nothing that e.g. loops
264 * over g->num_commits, or runs a checksum on the commit-graph
265 * itself.
266 */
267 if (!g->chunk_oid_fanout) {
268 error("commit-graph is missing the OID Fanout chunk");
269 return 1;
270 }
271 if (!g->chunk_oid_lookup) {
272 error("commit-graph is missing the OID Lookup chunk");
273 return 1;
274 }
275 if (!g->chunk_commit_data) {
276 error("commit-graph is missing the Commit Data chunk");
277 return 1;
278 }
279
280 return 0;
281 }
282
283 struct commit_graph *parse_commit_graph(void *graph_map, size_t graph_size)
284 {
285 const unsigned char *data, *chunk_lookup;
286 uint32_t i;
287 struct commit_graph *graph;
288 uint64_t next_chunk_offset;
289 uint32_t graph_signature;
290 unsigned char graph_version, hash_version;
291
292 if (!graph_map)
293 return NULL;
294
295 if (graph_size < GRAPH_MIN_SIZE)
296 return NULL;
297
298 data = (const unsigned char *)graph_map;
299
300 graph_signature = get_be32(data);
301 if (graph_signature != GRAPH_SIGNATURE) {
302 error(_("commit-graph signature %X does not match signature %X"),
303 graph_signature, GRAPH_SIGNATURE);
304 return NULL;
305 }
306
307 graph_version = *(unsigned char*)(data + 4);
308 if (graph_version != GRAPH_VERSION) {
309 error(_("commit-graph version %X does not match version %X"),
310 graph_version, GRAPH_VERSION);
311 return NULL;
312 }
313
314 hash_version = *(unsigned char*)(data + 5);
315 if (hash_version != oid_version()) {
316 error(_("commit-graph hash version %X does not match version %X"),
317 hash_version, oid_version());
318 return NULL;
319 }
320
321 graph = alloc_commit_graph();
322
323 graph->hash_len = the_hash_algo->rawsz;
324 graph->num_chunks = *(unsigned char*)(data + 6);
325 graph->data = graph_map;
326 graph->data_len = graph_size;
327
328 if (graph_size < GRAPH_HEADER_SIZE +
329 (graph->num_chunks + 1) * GRAPH_CHUNKLOOKUP_WIDTH +
330 GRAPH_FANOUT_SIZE + the_hash_algo->rawsz) {
331 error(_("commit-graph file is too small to hold %u chunks"),
332 graph->num_chunks);
333 free(graph);
334 return NULL;
335 }
336
337 chunk_lookup = data + 8;
338 next_chunk_offset = get_be64(chunk_lookup + 4);
339 for (i = 0; i < graph->num_chunks; i++) {
340 uint32_t chunk_id;
341 uint64_t chunk_offset = next_chunk_offset;
342 int chunk_repeated = 0;
343
344 chunk_id = get_be32(chunk_lookup + 0);
345
346 chunk_lookup += GRAPH_CHUNKLOOKUP_WIDTH;
347 next_chunk_offset = get_be64(chunk_lookup + 4);
348
349 if (chunk_offset > graph_size - the_hash_algo->rawsz) {
350 error(_("commit-graph improper chunk offset %08x%08x"), (uint32_t)(chunk_offset >> 32),
351 (uint32_t)chunk_offset);
352 goto free_and_return;
353 }
354
355 switch (chunk_id) {
356 case GRAPH_CHUNKID_OIDFANOUT:
357 if (graph->chunk_oid_fanout)
358 chunk_repeated = 1;
359 else
360 graph->chunk_oid_fanout = (uint32_t*)(data + chunk_offset);
361 break;
362
363 case GRAPH_CHUNKID_OIDLOOKUP:
364 if (graph->chunk_oid_lookup)
365 chunk_repeated = 1;
366 else {
367 graph->chunk_oid_lookup = data + chunk_offset;
368 graph->num_commits = (next_chunk_offset - chunk_offset)
369 / graph->hash_len;
370 }
371 break;
372
373 case GRAPH_CHUNKID_DATA:
374 if (graph->chunk_commit_data)
375 chunk_repeated = 1;
376 else
377 graph->chunk_commit_data = data + chunk_offset;
378 break;
379
380 case GRAPH_CHUNKID_EXTRAEDGES:
381 if (graph->chunk_extra_edges)
382 chunk_repeated = 1;
383 else
384 graph->chunk_extra_edges = data + chunk_offset;
385 break;
386
387 case GRAPH_CHUNKID_BASE:
388 if (graph->chunk_base_graphs)
389 chunk_repeated = 1;
390 else
391 graph->chunk_base_graphs = data + chunk_offset;
392 break;
393
394 case GRAPH_CHUNKID_BLOOMINDEXES:
395 if (graph->chunk_bloom_indexes)
396 chunk_repeated = 1;
397 else
398 graph->chunk_bloom_indexes = data + chunk_offset;
399 break;
400
401 case GRAPH_CHUNKID_BLOOMDATA:
402 if (graph->chunk_bloom_data)
403 chunk_repeated = 1;
404 else {
405 uint32_t hash_version;
406 graph->chunk_bloom_data = data + chunk_offset;
407 hash_version = get_be32(data + chunk_offset);
408
409 if (hash_version != 1)
410 break;
411
412 graph->bloom_filter_settings = xmalloc(sizeof(struct bloom_filter_settings));
413 graph->bloom_filter_settings->hash_version = hash_version;
414 graph->bloom_filter_settings->num_hashes = get_be32(data + chunk_offset + 4);
415 graph->bloom_filter_settings->bits_per_entry = get_be32(data + chunk_offset + 8);
416 }
417 break;
418 }
419
420 if (chunk_repeated) {
421 error(_("commit-graph chunk id %08x appears multiple times"), chunk_id);
422 goto free_and_return;
423 }
424 }
425
426 if (graph->chunk_bloom_indexes && graph->chunk_bloom_data) {
427 init_bloom_filters();
428 } else {
429 /* We need both the bloom chunks to exist together. Else ignore the data */
430 graph->chunk_bloom_indexes = NULL;
431 graph->chunk_bloom_data = NULL;
432 FREE_AND_NULL(graph->bloom_filter_settings);
433 }
434
435 hashcpy(graph->oid.hash, graph->data + graph->data_len - graph->hash_len);
436
437 if (verify_commit_graph_lite(graph))
438 goto free_and_return;
439
440 return graph;
441
442 free_and_return:
443 free(graph->bloom_filter_settings);
444 free(graph);
445 return NULL;
446 }
447
448 static struct commit_graph *load_commit_graph_one(const char *graph_file,
449 struct object_directory *odb)
450 {
451
452 struct stat st;
453 int fd;
454 struct commit_graph *g;
455 int open_ok = open_commit_graph(graph_file, &fd, &st);
456
457 if (!open_ok)
458 return NULL;
459
460 g = load_commit_graph_one_fd_st(fd, &st, odb);
461
462 if (g)
463 g->filename = xstrdup(graph_file);
464
465 return g;
466 }
467
468 static struct commit_graph *load_commit_graph_v1(struct repository *r,
469 struct object_directory *odb)
470 {
471 char *graph_name = get_commit_graph_filename(odb);
472 struct commit_graph *g = load_commit_graph_one(graph_name, odb);
473 free(graph_name);
474
475 return g;
476 }
477
478 static int add_graph_to_chain(struct commit_graph *g,
479 struct commit_graph *chain,
480 struct object_id *oids,
481 int n)
482 {
483 struct commit_graph *cur_g = chain;
484
485 if (n && !g->chunk_base_graphs) {
486 warning(_("commit-graph has no base graphs chunk"));
487 return 0;
488 }
489
490 while (n) {
491 n--;
492
493 if (!cur_g ||
494 !oideq(&oids[n], &cur_g->oid) ||
495 !hasheq(oids[n].hash, g->chunk_base_graphs + g->hash_len * n)) {
496 warning(_("commit-graph chain does not match"));
497 return 0;
498 }
499
500 cur_g = cur_g->base_graph;
501 }
502
503 g->base_graph = chain;
504
505 if (chain)
506 g->num_commits_in_base = chain->num_commits + chain->num_commits_in_base;
507
508 return 1;
509 }
510
511 static struct commit_graph *load_commit_graph_chain(struct repository *r,
512 struct object_directory *odb)
513 {
514 struct commit_graph *graph_chain = NULL;
515 struct strbuf line = STRBUF_INIT;
516 struct stat st;
517 struct object_id *oids;
518 int i = 0, valid = 1, count;
519 char *chain_name = get_chain_filename(odb);
520 FILE *fp;
521 int stat_res;
522
523 fp = fopen(chain_name, "r");
524 stat_res = stat(chain_name, &st);
525 free(chain_name);
526
527 if (!fp ||
528 stat_res ||
529 st.st_size <= the_hash_algo->hexsz)
530 return NULL;
531
532 count = st.st_size / (the_hash_algo->hexsz + 1);
533 oids = xcalloc(count, sizeof(struct object_id));
534
535 prepare_alt_odb(r);
536
537 for (i = 0; i < count; i++) {
538 struct object_directory *odb;
539
540 if (strbuf_getline_lf(&line, fp) == EOF)
541 break;
542
543 if (get_oid_hex(line.buf, &oids[i])) {
544 warning(_("invalid commit-graph chain: line '%s' not a hash"),
545 line.buf);
546 valid = 0;
547 break;
548 }
549
550 valid = 0;
551 for (odb = r->objects->odb; odb; odb = odb->next) {
552 char *graph_name = get_split_graph_filename(odb, line.buf);
553 struct commit_graph *g = load_commit_graph_one(graph_name, odb);
554
555 free(graph_name);
556
557 if (g) {
558 if (add_graph_to_chain(g, graph_chain, oids, i)) {
559 graph_chain = g;
560 valid = 1;
561 }
562
563 break;
564 }
565 }
566
567 if (!valid) {
568 warning(_("unable to find all commit-graph files"));
569 break;
570 }
571 }
572
573 free(oids);
574 fclose(fp);
575 strbuf_release(&line);
576
577 return graph_chain;
578 }
579
580 struct commit_graph *read_commit_graph_one(struct repository *r,
581 struct object_directory *odb)
582 {
583 struct commit_graph *g = load_commit_graph_v1(r, odb);
584
585 if (!g)
586 g = load_commit_graph_chain(r, odb);
587
588 return g;
589 }
590
591 static void prepare_commit_graph_one(struct repository *r,
592 struct object_directory *odb)
593 {
594
595 if (r->objects->commit_graph)
596 return;
597
598 r->objects->commit_graph = read_commit_graph_one(r, odb);
599 }
600
601 /*
602 * Return 1 if commit_graph is non-NULL, and 0 otherwise.
603 *
604 * On the first invocation, this function attempts to load the commit
605 * graph if the_repository is configured to have one.
606 */
607 static int prepare_commit_graph(struct repository *r)
608 {
609 struct object_directory *odb;
610
611 /*
612 * This must come before the "already attempted?" check below, because
613 * we want to disable even an already-loaded graph file.
614 */
615 if (r->commit_graph_disabled)
616 return 0;
617
618 if (r->objects->commit_graph_attempted)
619 return !!r->objects->commit_graph;
620 r->objects->commit_graph_attempted = 1;
621
622 prepare_repo_settings(r);
623
624 if (!git_env_bool(GIT_TEST_COMMIT_GRAPH, 0) &&
625 r->settings.core_commit_graph != 1)
626 /*
627 * This repository is not configured to use commit graphs, so
628 * do not load one. (But report commit_graph_attempted anyway
629 * so that commit graph loading is not attempted again for this
630 * repository.)
631 */
632 return 0;
633
634 if (!commit_graph_compatible(r))
635 return 0;
636
637 prepare_alt_odb(r);
638 for (odb = r->objects->odb;
639 !r->objects->commit_graph && odb;
640 odb = odb->next)
641 prepare_commit_graph_one(r, odb);
642 return !!r->objects->commit_graph;
643 }
644
645 int generation_numbers_enabled(struct repository *r)
646 {
647 uint32_t first_generation;
648 struct commit_graph *g;
649 if (!prepare_commit_graph(r))
650 return 0;
651
652 g = r->objects->commit_graph;
653
654 if (!g->num_commits)
655 return 0;
656
657 first_generation = get_be32(g->chunk_commit_data +
658 g->hash_len + 8) >> 2;
659
660 return !!first_generation;
661 }
662
663 static void close_commit_graph_one(struct commit_graph *g)
664 {
665 if (!g)
666 return;
667
668 close_commit_graph_one(g->base_graph);
669 free_commit_graph(g);
670 }
671
672 void close_commit_graph(struct raw_object_store *o)
673 {
674 close_commit_graph_one(o->commit_graph);
675 o->commit_graph = NULL;
676 }
677
678 static int bsearch_graph(struct commit_graph *g, struct object_id *oid, uint32_t *pos)
679 {
680 return bsearch_hash(oid->hash, g->chunk_oid_fanout,
681 g->chunk_oid_lookup, g->hash_len, pos);
682 }
683
684 static void load_oid_from_graph(struct commit_graph *g,
685 uint32_t pos,
686 struct object_id *oid)
687 {
688 uint32_t lex_index;
689
690 while (g && pos < g->num_commits_in_base)
691 g = g->base_graph;
692
693 if (!g)
694 BUG("NULL commit-graph");
695
696 if (pos >= g->num_commits + g->num_commits_in_base)
697 die(_("invalid commit position. commit-graph is likely corrupt"));
698
699 lex_index = pos - g->num_commits_in_base;
700
701 hashcpy(oid->hash, g->chunk_oid_lookup + g->hash_len * lex_index);
702 }
703
704 static struct commit_list **insert_parent_or_die(struct repository *r,
705 struct commit_graph *g,
706 uint32_t pos,
707 struct commit_list **pptr)
708 {
709 struct commit *c;
710 struct object_id oid;
711
712 if (pos >= g->num_commits + g->num_commits_in_base)
713 die("invalid parent position %"PRIu32, pos);
714
715 load_oid_from_graph(g, pos, &oid);
716 c = lookup_commit(r, &oid);
717 if (!c)
718 die(_("could not find commit %s"), oid_to_hex(&oid));
719 commit_graph_data_at(c)->graph_pos = pos;
720 return &commit_list_insert(c, pptr)->next;
721 }
722
723 static void fill_commit_graph_info(struct commit *item, struct commit_graph *g, uint32_t pos)
724 {
725 const unsigned char *commit_data;
726 struct commit_graph_data *graph_data;
727 uint32_t lex_index;
728
729 while (pos < g->num_commits_in_base)
730 g = g->base_graph;
731
732 lex_index = pos - g->num_commits_in_base;
733 commit_data = g->chunk_commit_data + GRAPH_DATA_WIDTH * lex_index;
734
735 graph_data = commit_graph_data_at(item);
736 graph_data->graph_pos = pos;
737 graph_data->generation = get_be32(commit_data + g->hash_len + 8) >> 2;
738 }
739
740 static inline void set_commit_tree(struct commit *c, struct tree *t)
741 {
742 c->maybe_tree = t;
743 }
744
745 static int fill_commit_in_graph(struct repository *r,
746 struct commit *item,
747 struct commit_graph *g, uint32_t pos)
748 {
749 uint32_t edge_value;
750 uint32_t *parent_data_ptr;
751 uint64_t date_low, date_high;
752 struct commit_list **pptr;
753 struct commit_graph_data *graph_data;
754 const unsigned char *commit_data;
755 uint32_t lex_index;
756
757 while (pos < g->num_commits_in_base)
758 g = g->base_graph;
759
760 if (pos >= g->num_commits + g->num_commits_in_base)
761 die(_("invalid commit position. commit-graph is likely corrupt"));
762
763 /*
764 * Store the "full" position, but then use the
765 * "local" position for the rest of the calculation.
766 */
767 graph_data = commit_graph_data_at(item);
768 graph_data->graph_pos = pos;
769 lex_index = pos - g->num_commits_in_base;
770
771 commit_data = g->chunk_commit_data + (g->hash_len + 16) * lex_index;
772
773 item->object.parsed = 1;
774
775 set_commit_tree(item, NULL);
776
777 date_high = get_be32(commit_data + g->hash_len + 8) & 0x3;
778 date_low = get_be32(commit_data + g->hash_len + 12);
779 item->date = (timestamp_t)((date_high << 32) | date_low);
780
781 graph_data->generation = get_be32(commit_data + g->hash_len + 8) >> 2;
782
783 pptr = &item->parents;
784
785 edge_value = get_be32(commit_data + g->hash_len);
786 if (edge_value == GRAPH_PARENT_NONE)
787 return 1;
788 pptr = insert_parent_or_die(r, g, edge_value, pptr);
789
790 edge_value = get_be32(commit_data + g->hash_len + 4);
791 if (edge_value == GRAPH_PARENT_NONE)
792 return 1;
793 if (!(edge_value & GRAPH_EXTRA_EDGES_NEEDED)) {
794 pptr = insert_parent_or_die(r, g, edge_value, pptr);
795 return 1;
796 }
797
798 parent_data_ptr = (uint32_t*)(g->chunk_extra_edges +
799 4 * (uint64_t)(edge_value & GRAPH_EDGE_LAST_MASK));
800 do {
801 edge_value = get_be32(parent_data_ptr);
802 pptr = insert_parent_or_die(r, g,
803 edge_value & GRAPH_EDGE_LAST_MASK,
804 pptr);
805 parent_data_ptr++;
806 } while (!(edge_value & GRAPH_LAST_EDGE));
807
808 return 1;
809 }
810
811 static int find_commit_in_graph(struct commit *item, struct commit_graph *g, uint32_t *pos)
812 {
813 uint32_t graph_pos = commit_graph_position(item);
814 if (graph_pos != COMMIT_NOT_FROM_GRAPH) {
815 *pos = graph_pos;
816 return 1;
817 } else {
818 struct commit_graph *cur_g = g;
819 uint32_t lex_index;
820
821 while (cur_g && !bsearch_graph(cur_g, &(item->object.oid), &lex_index))
822 cur_g = cur_g->base_graph;
823
824 if (cur_g) {
825 *pos = lex_index + cur_g->num_commits_in_base;
826 return 1;
827 }
828
829 return 0;
830 }
831 }
832
833 static int parse_commit_in_graph_one(struct repository *r,
834 struct commit_graph *g,
835 struct commit *item)
836 {
837 uint32_t pos;
838
839 if (item->object.parsed)
840 return 1;
841
842 if (find_commit_in_graph(item, g, &pos))
843 return fill_commit_in_graph(r, item, g, pos);
844
845 return 0;
846 }
847
848 int parse_commit_in_graph(struct repository *r, struct commit *item)
849 {
850 static int checked_env = 0;
851
852 if (!checked_env &&
853 git_env_bool(GIT_TEST_COMMIT_GRAPH_DIE_ON_PARSE, 0))
854 die("dying as requested by the '%s' variable on commit-graph parse!",
855 GIT_TEST_COMMIT_GRAPH_DIE_ON_PARSE);
856 checked_env = 1;
857
858 if (!prepare_commit_graph(r))
859 return 0;
860 return parse_commit_in_graph_one(r, r->objects->commit_graph, item);
861 }
862
863 void load_commit_graph_info(struct repository *r, struct commit *item)
864 {
865 uint32_t pos;
866 if (!prepare_commit_graph(r))
867 return;
868 if (find_commit_in_graph(item, r->objects->commit_graph, &pos))
869 fill_commit_graph_info(item, r->objects->commit_graph, pos);
870 }
871
872 static struct tree *load_tree_for_commit(struct repository *r,
873 struct commit_graph *g,
874 struct commit *c)
875 {
876 struct object_id oid;
877 const unsigned char *commit_data;
878 uint32_t graph_pos = commit_graph_position(c);
879
880 while (graph_pos < g->num_commits_in_base)
881 g = g->base_graph;
882
883 commit_data = g->chunk_commit_data +
884 GRAPH_DATA_WIDTH * (graph_pos - g->num_commits_in_base);
885
886 hashcpy(oid.hash, commit_data);
887 set_commit_tree(c, lookup_tree(r, &oid));
888
889 return c->maybe_tree;
890 }
891
892 static struct tree *get_commit_tree_in_graph_one(struct repository *r,
893 struct commit_graph *g,
894 const struct commit *c)
895 {
896 if (c->maybe_tree)
897 return c->maybe_tree;
898 if (commit_graph_position(c) == COMMIT_NOT_FROM_GRAPH)
899 BUG("get_commit_tree_in_graph_one called from non-commit-graph commit");
900
901 return load_tree_for_commit(r, g, (struct commit *)c);
902 }
903
904 struct tree *get_commit_tree_in_graph(struct repository *r, const struct commit *c)
905 {
906 return get_commit_tree_in_graph_one(r, r->objects->commit_graph, c);
907 }
908
909 struct packed_commit_list {
910 struct commit **list;
911 int nr;
912 int alloc;
913 };
914
915 struct packed_oid_list {
916 struct object_id *list;
917 int nr;
918 int alloc;
919 };
920
921 struct write_commit_graph_context {
922 struct repository *r;
923 struct object_directory *odb;
924 char *graph_name;
925 struct packed_oid_list oids;
926 struct packed_commit_list commits;
927 int num_extra_edges;
928 unsigned long approx_nr_objects;
929 struct progress *progress;
930 int progress_done;
931 uint64_t progress_cnt;
932
933 char *base_graph_name;
934 int num_commit_graphs_before;
935 int num_commit_graphs_after;
936 char **commit_graph_filenames_before;
937 char **commit_graph_filenames_after;
938 char **commit_graph_hash_after;
939 uint32_t new_num_commits_in_base;
940 struct commit_graph *new_base_graph;
941
942 unsigned append:1,
943 report_progress:1,
944 split:1,
945 changed_paths:1,
946 order_by_pack:1;
947
948 const struct split_commit_graph_opts *split_opts;
949 size_t total_bloom_filter_data_size;
950 const struct bloom_filter_settings *bloom_settings;
951 };
952
953 static int write_graph_chunk_fanout(struct hashfile *f,
954 struct write_commit_graph_context *ctx)
955 {
956 int i, count = 0;
957 struct commit **list = ctx->commits.list;
958
959 /*
960 * Write the first-level table (the list is sorted,
961 * but we use a 256-entry lookup to be able to avoid
962 * having to do eight extra binary search iterations).
963 */
964 for (i = 0; i < 256; i++) {
965 while (count < ctx->commits.nr) {
966 if ((*list)->object.oid.hash[0] != i)
967 break;
968 display_progress(ctx->progress, ++ctx->progress_cnt);
969 count++;
970 list++;
971 }
972
973 hashwrite_be32(f, count);
974 }
975
976 return 0;
977 }
978
979 static int write_graph_chunk_oids(struct hashfile *f,
980 struct write_commit_graph_context *ctx)
981 {
982 struct commit **list = ctx->commits.list;
983 int count;
984 for (count = 0; count < ctx->commits.nr; count++, list++) {
985 display_progress(ctx->progress, ++ctx->progress_cnt);
986 hashwrite(f, (*list)->object.oid.hash, the_hash_algo->rawsz);
987 }
988
989 return 0;
990 }
991
992 static const unsigned char *commit_to_sha1(size_t index, void *table)
993 {
994 struct commit **commits = table;
995 return commits[index]->object.oid.hash;
996 }
997
998 static int write_graph_chunk_data(struct hashfile *f,
999 struct write_commit_graph_context *ctx)
1000 {
1001 struct commit **list = ctx->commits.list;
1002 struct commit **last = ctx->commits.list + ctx->commits.nr;
1003 uint32_t num_extra_edges = 0;
1004
1005 while (list < last) {
1006 struct commit_list *parent;
1007 struct object_id *tree;
1008 int edge_value;
1009 uint32_t packedDate[2];
1010 display_progress(ctx->progress, ++ctx->progress_cnt);
1011
1012 if (parse_commit_no_graph(*list))
1013 die(_("unable to parse commit %s"),
1014 oid_to_hex(&(*list)->object.oid));
1015 tree = get_commit_tree_oid(*list);
1016 hashwrite(f, tree->hash, the_hash_algo->rawsz);
1017
1018 parent = (*list)->parents;
1019
1020 if (!parent)
1021 edge_value = GRAPH_PARENT_NONE;
1022 else {
1023 edge_value = sha1_pos(parent->item->object.oid.hash,
1024 ctx->commits.list,
1025 ctx->commits.nr,
1026 commit_to_sha1);
1027
1028 if (edge_value >= 0)
1029 edge_value += ctx->new_num_commits_in_base;
1030 else if (ctx->new_base_graph) {
1031 uint32_t pos;
1032 if (find_commit_in_graph(parent->item,
1033 ctx->new_base_graph,
1034 &pos))
1035 edge_value = pos;
1036 }
1037
1038 if (edge_value < 0)
1039 BUG("missing parent %s for commit %s",
1040 oid_to_hex(&parent->item->object.oid),
1041 oid_to_hex(&(*list)->object.oid));
1042 }
1043
1044 hashwrite_be32(f, edge_value);
1045
1046 if (parent)
1047 parent = parent->next;
1048
1049 if (!parent)
1050 edge_value = GRAPH_PARENT_NONE;
1051 else if (parent->next)
1052 edge_value = GRAPH_EXTRA_EDGES_NEEDED | num_extra_edges;
1053 else {
1054 edge_value = sha1_pos(parent->item->object.oid.hash,
1055 ctx->commits.list,
1056 ctx->commits.nr,
1057 commit_to_sha1);
1058
1059 if (edge_value >= 0)
1060 edge_value += ctx->new_num_commits_in_base;
1061 else if (ctx->new_base_graph) {
1062 uint32_t pos;
1063 if (find_commit_in_graph(parent->item,
1064 ctx->new_base_graph,
1065 &pos))
1066 edge_value = pos;
1067 }
1068
1069 if (edge_value < 0)
1070 BUG("missing parent %s for commit %s",
1071 oid_to_hex(&parent->item->object.oid),
1072 oid_to_hex(&(*list)->object.oid));
1073 }
1074
1075 hashwrite_be32(f, edge_value);
1076
1077 if (edge_value & GRAPH_EXTRA_EDGES_NEEDED) {
1078 do {
1079 num_extra_edges++;
1080 parent = parent->next;
1081 } while (parent);
1082 }
1083
1084 if (sizeof((*list)->date) > 4)
1085 packedDate[0] = htonl(((*list)->date >> 32) & 0x3);
1086 else
1087 packedDate[0] = 0;
1088
1089 packedDate[0] |= htonl(commit_graph_data_at(*list)->generation << 2);
1090
1091 packedDate[1] = htonl((*list)->date);
1092 hashwrite(f, packedDate, 8);
1093
1094 list++;
1095 }
1096
1097 return 0;
1098 }
1099
1100 static int write_graph_chunk_extra_edges(struct hashfile *f,
1101 struct write_commit_graph_context *ctx)
1102 {
1103 struct commit **list = ctx->commits.list;
1104 struct commit **last = ctx->commits.list + ctx->commits.nr;
1105 struct commit_list *parent;
1106
1107 while (list < last) {
1108 int num_parents = 0;
1109
1110 display_progress(ctx->progress, ++ctx->progress_cnt);
1111
1112 for (parent = (*list)->parents; num_parents < 3 && parent;
1113 parent = parent->next)
1114 num_parents++;
1115
1116 if (num_parents <= 2) {
1117 list++;
1118 continue;
1119 }
1120
1121 /* Since num_parents > 2, this initializer is safe. */
1122 for (parent = (*list)->parents->next; parent; parent = parent->next) {
1123 int edge_value = sha1_pos(parent->item->object.oid.hash,
1124 ctx->commits.list,
1125 ctx->commits.nr,
1126 commit_to_sha1);
1127
1128 if (edge_value >= 0)
1129 edge_value += ctx->new_num_commits_in_base;
1130 else if (ctx->new_base_graph) {
1131 uint32_t pos;
1132 if (find_commit_in_graph(parent->item,
1133 ctx->new_base_graph,
1134 &pos))
1135 edge_value = pos;
1136 }
1137
1138 if (edge_value < 0)
1139 BUG("missing parent %s for commit %s",
1140 oid_to_hex(&parent->item->object.oid),
1141 oid_to_hex(&(*list)->object.oid));
1142 else if (!parent->next)
1143 edge_value |= GRAPH_LAST_EDGE;
1144
1145 hashwrite_be32(f, edge_value);
1146 }
1147
1148 list++;
1149 }
1150
1151 return 0;
1152 }
1153
1154 static int write_graph_chunk_bloom_indexes(struct hashfile *f,
1155 struct write_commit_graph_context *ctx)
1156 {
1157 struct commit **list = ctx->commits.list;
1158 struct commit **last = ctx->commits.list + ctx->commits.nr;
1159 uint32_t cur_pos = 0;
1160
1161 while (list < last) {
1162 struct bloom_filter *filter = get_bloom_filter(ctx->r, *list, 0);
1163 size_t len = filter ? filter->len : 0;
1164 cur_pos += len;
1165 display_progress(ctx->progress, ++ctx->progress_cnt);
1166 hashwrite_be32(f, cur_pos);
1167 list++;
1168 }
1169
1170 return 0;
1171 }
1172
1173 static void trace2_bloom_filter_settings(struct write_commit_graph_context *ctx)
1174 {
1175 struct json_writer jw = JSON_WRITER_INIT;
1176
1177 jw_object_begin(&jw, 0);
1178 jw_object_intmax(&jw, "hash_version", ctx->bloom_settings->hash_version);
1179 jw_object_intmax(&jw, "num_hashes", ctx->bloom_settings->num_hashes);
1180 jw_object_intmax(&jw, "bits_per_entry", ctx->bloom_settings->bits_per_entry);
1181 jw_end(&jw);
1182
1183 trace2_data_json("bloom", ctx->r, "settings", &jw);
1184
1185 jw_release(&jw);
1186 }
1187
1188 static int write_graph_chunk_bloom_data(struct hashfile *f,
1189 struct write_commit_graph_context *ctx)
1190 {
1191 struct commit **list = ctx->commits.list;
1192 struct commit **last = ctx->commits.list + ctx->commits.nr;
1193
1194 trace2_bloom_filter_settings(ctx);
1195
1196 hashwrite_be32(f, ctx->bloom_settings->hash_version);
1197 hashwrite_be32(f, ctx->bloom_settings->num_hashes);
1198 hashwrite_be32(f, ctx->bloom_settings->bits_per_entry);
1199
1200 while (list < last) {
1201 struct bloom_filter *filter = get_bloom_filter(ctx->r, *list, 0);
1202 size_t len = filter ? filter->len : 0;
1203
1204 display_progress(ctx->progress, ++ctx->progress_cnt);
1205 if (len)
1206 hashwrite(f, filter->data, len * sizeof(unsigned char));
1207 list++;
1208 }
1209
1210 return 0;
1211 }
1212
1213 static int oid_compare(const void *_a, const void *_b)
1214 {
1215 const struct object_id *a = (const struct object_id *)_a;
1216 const struct object_id *b = (const struct object_id *)_b;
1217 return oidcmp(a, b);
1218 }
1219
1220 static int add_packed_commits(const struct object_id *oid,
1221 struct packed_git *pack,
1222 uint32_t pos,
1223 void *data)
1224 {
1225 struct write_commit_graph_context *ctx = (struct write_commit_graph_context*)data;
1226 enum object_type type;
1227 off_t offset = nth_packed_object_offset(pack, pos);
1228 struct object_info oi = OBJECT_INFO_INIT;
1229
1230 if (ctx->progress)
1231 display_progress(ctx->progress, ++ctx->progress_done);
1232
1233 oi.typep = &type;
1234 if (packed_object_info(ctx->r, pack, offset, &oi) < 0)
1235 die(_("unable to get type of object %s"), oid_to_hex(oid));
1236
1237 if (type != OBJ_COMMIT)
1238 return 0;
1239
1240 ALLOC_GROW(ctx->oids.list, ctx->oids.nr + 1, ctx->oids.alloc);
1241 oidcpy(&(ctx->oids.list[ctx->oids.nr]), oid);
1242 ctx->oids.nr++;
1243
1244 set_commit_pos(ctx->r, oid);
1245
1246 return 0;
1247 }
1248
1249 static void add_missing_parents(struct write_commit_graph_context *ctx, struct commit *commit)
1250 {
1251 struct commit_list *parent;
1252 for (parent = commit->parents; parent; parent = parent->next) {
1253 if (!(parent->item->object.flags & REACHABLE)) {
1254 ALLOC_GROW(ctx->oids.list, ctx->oids.nr + 1, ctx->oids.alloc);
1255 oidcpy(&ctx->oids.list[ctx->oids.nr], &(parent->item->object.oid));
1256 ctx->oids.nr++;
1257 parent->item->object.flags |= REACHABLE;
1258 }
1259 }
1260 }
1261
1262 static void close_reachable(struct write_commit_graph_context *ctx)
1263 {
1264 int i;
1265 struct commit *commit;
1266 enum commit_graph_split_flags flags = ctx->split_opts ?
1267 ctx->split_opts->flags : COMMIT_GRAPH_SPLIT_UNSPECIFIED;
1268
1269 if (ctx->report_progress)
1270 ctx->progress = start_delayed_progress(
1271 _("Loading known commits in commit graph"),
1272 ctx->oids.nr);
1273 for (i = 0; i < ctx->oids.nr; i++) {
1274 display_progress(ctx->progress, i + 1);
1275 commit = lookup_commit(ctx->r, &ctx->oids.list[i]);
1276 if (commit)
1277 commit->object.flags |= REACHABLE;
1278 }
1279 stop_progress(&ctx->progress);
1280
1281 /*
1282 * As this loop runs, ctx->oids.nr may grow, but not more
1283 * than the number of missing commits in the reachable
1284 * closure.
1285 */
1286 if (ctx->report_progress)
1287 ctx->progress = start_delayed_progress(
1288 _("Expanding reachable commits in commit graph"),
1289 0);
1290 for (i = 0; i < ctx->oids.nr; i++) {
1291 display_progress(ctx->progress, i + 1);
1292 commit = lookup_commit(ctx->r, &ctx->oids.list[i]);
1293
1294 if (!commit)
1295 continue;
1296 if (ctx->split) {
1297 if ((!parse_commit(commit) &&
1298 commit_graph_position(commit) == COMMIT_NOT_FROM_GRAPH) ||
1299 flags == COMMIT_GRAPH_SPLIT_REPLACE)
1300 add_missing_parents(ctx, commit);
1301 } else if (!parse_commit_no_graph(commit))
1302 add_missing_parents(ctx, commit);
1303 }
1304 stop_progress(&ctx->progress);
1305
1306 if (ctx->report_progress)
1307 ctx->progress = start_delayed_progress(
1308 _("Clearing commit marks in commit graph"),
1309 ctx->oids.nr);
1310 for (i = 0; i < ctx->oids.nr; i++) {
1311 display_progress(ctx->progress, i + 1);
1312 commit = lookup_commit(ctx->r, &ctx->oids.list[i]);
1313
1314 if (commit)
1315 commit->object.flags &= ~REACHABLE;
1316 }
1317 stop_progress(&ctx->progress);
1318 }
1319
1320 static void compute_generation_numbers(struct write_commit_graph_context *ctx)
1321 {
1322 int i;
1323 struct commit_list *list = NULL;
1324
1325 if (ctx->report_progress)
1326 ctx->progress = start_delayed_progress(
1327 _("Computing commit graph generation numbers"),
1328 ctx->commits.nr);
1329 for (i = 0; i < ctx->commits.nr; i++) {
1330 uint32_t generation = commit_graph_data_at(ctx->commits.list[i])->generation;
1331
1332 display_progress(ctx->progress, i + 1);
1333 if (generation != GENERATION_NUMBER_INFINITY &&
1334 generation != GENERATION_NUMBER_ZERO)
1335 continue;
1336
1337 commit_list_insert(ctx->commits.list[i], &list);
1338 while (list) {
1339 struct commit *current = list->item;
1340 struct commit_list *parent;
1341 int all_parents_computed = 1;
1342 uint32_t max_generation = 0;
1343
1344 for (parent = current->parents; parent; parent = parent->next) {
1345 generation = commit_graph_data_at(parent->item)->generation;
1346
1347 if (generation == GENERATION_NUMBER_INFINITY ||
1348 generation == GENERATION_NUMBER_ZERO) {
1349 all_parents_computed = 0;
1350 commit_list_insert(parent->item, &list);
1351 break;
1352 } else if (generation > max_generation) {
1353 max_generation = generation;
1354 }
1355 }
1356
1357 if (all_parents_computed) {
1358 struct commit_graph_data *data = commit_graph_data_at(current);
1359
1360 data->generation = max_generation + 1;
1361 pop_commit(&list);
1362
1363 if (data->generation > GENERATION_NUMBER_MAX)
1364 data->generation = GENERATION_NUMBER_MAX;
1365 }
1366 }
1367 }
1368 stop_progress(&ctx->progress);
1369 }
1370
1371 static void compute_bloom_filters(struct write_commit_graph_context *ctx)
1372 {
1373 int i;
1374 struct progress *progress = NULL;
1375 struct commit **sorted_commits;
1376
1377 init_bloom_filters();
1378
1379 if (ctx->report_progress)
1380 progress = start_delayed_progress(
1381 _("Computing commit changed paths Bloom filters"),
1382 ctx->commits.nr);
1383
1384 ALLOC_ARRAY(sorted_commits, ctx->commits.nr);
1385 COPY_ARRAY(sorted_commits, ctx->commits.list, ctx->commits.nr);
1386
1387 if (ctx->order_by_pack)
1388 QSORT(sorted_commits, ctx->commits.nr, commit_pos_cmp);
1389 else
1390 QSORT(sorted_commits, ctx->commits.nr, commit_gen_cmp);
1391
1392 for (i = 0; i < ctx->commits.nr; i++) {
1393 struct commit *c = sorted_commits[i];
1394 struct bloom_filter *filter = get_bloom_filter(ctx->r, c, 1);
1395 ctx->total_bloom_filter_data_size += sizeof(unsigned char) * filter->len;
1396 display_progress(progress, i + 1);
1397 }
1398
1399 free(sorted_commits);
1400 stop_progress(&progress);
1401 }
1402
1403 struct refs_cb_data {
1404 struct oidset *commits;
1405 struct progress *progress;
1406 };
1407
1408 static int add_ref_to_set(const char *refname,
1409 const struct object_id *oid,
1410 int flags, void *cb_data)
1411 {
1412 struct object_id peeled;
1413 struct refs_cb_data *data = (struct refs_cb_data *)cb_data;
1414
1415 if (!peel_ref(refname, &peeled))
1416 oid = &peeled;
1417 if (oid_object_info(the_repository, oid, NULL) == OBJ_COMMIT)
1418 oidset_insert(data->commits, oid);
1419
1420 display_progress(data->progress, oidset_size(data->commits));
1421
1422 return 0;
1423 }
1424
1425 int write_commit_graph_reachable(struct object_directory *odb,
1426 enum commit_graph_write_flags flags,
1427 const struct split_commit_graph_opts *split_opts)
1428 {
1429 struct oidset commits = OIDSET_INIT;
1430 struct refs_cb_data data;
1431 int result;
1432
1433 memset(&data, 0, sizeof(data));
1434 data.commits = &commits;
1435 if (flags & COMMIT_GRAPH_WRITE_PROGRESS)
1436 data.progress = start_delayed_progress(
1437 _("Collecting referenced commits"), 0);
1438
1439 for_each_ref(add_ref_to_set, &data);
1440
1441 stop_progress(&data.progress);
1442
1443 result = write_commit_graph(odb, NULL, &commits,
1444 flags, split_opts);
1445
1446 oidset_clear(&commits);
1447 return result;
1448 }
1449
1450 static int fill_oids_from_packs(struct write_commit_graph_context *ctx,
1451 struct string_list *pack_indexes)
1452 {
1453 uint32_t i;
1454 struct strbuf progress_title = STRBUF_INIT;
1455 struct strbuf packname = STRBUF_INIT;
1456 int dirlen;
1457
1458 strbuf_addf(&packname, "%s/pack/", ctx->odb->path);
1459 dirlen = packname.len;
1460 if (ctx->report_progress) {
1461 strbuf_addf(&progress_title,
1462 Q_("Finding commits for commit graph in %d pack",
1463 "Finding commits for commit graph in %d packs",
1464 pack_indexes->nr),
1465 pack_indexes->nr);
1466 ctx->progress = start_delayed_progress(progress_title.buf, 0);
1467 ctx->progress_done = 0;
1468 }
1469 for (i = 0; i < pack_indexes->nr; i++) {
1470 struct packed_git *p;
1471 strbuf_setlen(&packname, dirlen);
1472 strbuf_addstr(&packname, pack_indexes->items[i].string);
1473 p = add_packed_git(packname.buf, packname.len, 1);
1474 if (!p) {
1475 error(_("error adding pack %s"), packname.buf);
1476 return -1;
1477 }
1478 if (open_pack_index(p)) {
1479 error(_("error opening index for %s"), packname.buf);
1480 return -1;
1481 }
1482 for_each_object_in_pack(p, add_packed_commits, ctx,
1483 FOR_EACH_OBJECT_PACK_ORDER);
1484 close_pack(p);
1485 free(p);
1486 }
1487
1488 stop_progress(&ctx->progress);
1489 strbuf_release(&progress_title);
1490 strbuf_release(&packname);
1491
1492 return 0;
1493 }
1494
1495 static int fill_oids_from_commits(struct write_commit_graph_context *ctx,
1496 struct oidset *commits)
1497 {
1498 struct oidset_iter iter;
1499 struct object_id *oid;
1500
1501 if (!oidset_size(commits))
1502 return 0;
1503
1504 oidset_iter_init(commits, &iter);
1505 while ((oid = oidset_iter_next(&iter))) {
1506 ALLOC_GROW(ctx->oids.list, ctx->oids.nr + 1, ctx->oids.alloc);
1507 oidcpy(&ctx->oids.list[ctx->oids.nr], oid);
1508 ctx->oids.nr++;
1509 }
1510
1511 return 0;
1512 }
1513
1514 static void fill_oids_from_all_packs(struct write_commit_graph_context *ctx)
1515 {
1516 if (ctx->report_progress)
1517 ctx->progress = start_delayed_progress(
1518 _("Finding commits for commit graph among packed objects"),
1519 ctx->approx_nr_objects);
1520 for_each_packed_object(add_packed_commits, ctx,
1521 FOR_EACH_OBJECT_PACK_ORDER);
1522 if (ctx->progress_done < ctx->approx_nr_objects)
1523 display_progress(ctx->progress, ctx->approx_nr_objects);
1524 stop_progress(&ctx->progress);
1525 }
1526
1527 static uint32_t count_distinct_commits(struct write_commit_graph_context *ctx)
1528 {
1529 uint32_t i, count_distinct = 1;
1530
1531 if (ctx->report_progress)
1532 ctx->progress = start_delayed_progress(
1533 _("Counting distinct commits in commit graph"),
1534 ctx->oids.nr);
1535 display_progress(ctx->progress, 0); /* TODO: Measure QSORT() progress */
1536 QSORT(ctx->oids.list, ctx->oids.nr, oid_compare);
1537
1538 for (i = 1; i < ctx->oids.nr; i++) {
1539 display_progress(ctx->progress, i + 1);
1540 if (!oideq(&ctx->oids.list[i - 1], &ctx->oids.list[i])) {
1541 if (ctx->split) {
1542 struct commit *c = lookup_commit(ctx->r, &ctx->oids.list[i]);
1543
1544 if (!c || commit_graph_position(c) != COMMIT_NOT_FROM_GRAPH)
1545 continue;
1546 }
1547
1548 count_distinct++;
1549 }
1550 }
1551 stop_progress(&ctx->progress);
1552
1553 return count_distinct;
1554 }
1555
1556 static void copy_oids_to_commits(struct write_commit_graph_context *ctx)
1557 {
1558 uint32_t i;
1559 enum commit_graph_split_flags flags = ctx->split_opts ?
1560 ctx->split_opts->flags : COMMIT_GRAPH_SPLIT_UNSPECIFIED;
1561
1562 ctx->num_extra_edges = 0;
1563 if (ctx->report_progress)
1564 ctx->progress = start_delayed_progress(
1565 _("Finding extra edges in commit graph"),
1566 ctx->oids.nr);
1567 for (i = 0; i < ctx->oids.nr; i++) {
1568 unsigned int num_parents;
1569
1570 display_progress(ctx->progress, i + 1);
1571 if (i > 0 && oideq(&ctx->oids.list[i - 1], &ctx->oids.list[i]))
1572 continue;
1573
1574 ALLOC_GROW(ctx->commits.list, ctx->commits.nr + 1, ctx->commits.alloc);
1575 ctx->commits.list[ctx->commits.nr] = lookup_commit(ctx->r, &ctx->oids.list[i]);
1576
1577 if (ctx->split && flags != COMMIT_GRAPH_SPLIT_REPLACE &&
1578 commit_graph_position(ctx->commits.list[ctx->commits.nr]) != COMMIT_NOT_FROM_GRAPH)
1579 continue;
1580
1581 if (ctx->split && flags == COMMIT_GRAPH_SPLIT_REPLACE)
1582 parse_commit(ctx->commits.list[ctx->commits.nr]);
1583 else
1584 parse_commit_no_graph(ctx->commits.list[ctx->commits.nr]);
1585
1586 num_parents = commit_list_count(ctx->commits.list[ctx->commits.nr]->parents);
1587 if (num_parents > 2)
1588 ctx->num_extra_edges += num_parents - 1;
1589
1590 ctx->commits.nr++;
1591 }
1592 stop_progress(&ctx->progress);
1593 }
1594
1595 static int write_graph_chunk_base_1(struct hashfile *f,
1596 struct commit_graph *g)
1597 {
1598 int num = 0;
1599
1600 if (!g)
1601 return 0;
1602
1603 num = write_graph_chunk_base_1(f, g->base_graph);
1604 hashwrite(f, g->oid.hash, the_hash_algo->rawsz);
1605 return num + 1;
1606 }
1607
1608 static int write_graph_chunk_base(struct hashfile *f,
1609 struct write_commit_graph_context *ctx)
1610 {
1611 int num = write_graph_chunk_base_1(f, ctx->new_base_graph);
1612
1613 if (num != ctx->num_commit_graphs_after - 1) {
1614 error(_("failed to write correct number of base graph ids"));
1615 return -1;
1616 }
1617
1618 return 0;
1619 }
1620
1621 typedef int (*chunk_write_fn)(struct hashfile *f,
1622 struct write_commit_graph_context *ctx);
1623
1624 struct chunk_info {
1625 uint32_t id;
1626 uint64_t size;
1627 chunk_write_fn write_fn;
1628 };
1629
1630 static int write_commit_graph_file(struct write_commit_graph_context *ctx)
1631 {
1632 uint32_t i;
1633 int fd;
1634 struct hashfile *f;
1635 struct lock_file lk = LOCK_INIT;
1636 struct chunk_info chunks[MAX_NUM_CHUNKS + 1];
1637 const unsigned hashsz = the_hash_algo->rawsz;
1638 struct strbuf progress_title = STRBUF_INIT;
1639 int num_chunks = 3;
1640 uint64_t chunk_offset;
1641 struct object_id file_hash;
1642 struct bloom_filter_settings bloom_settings = DEFAULT_BLOOM_FILTER_SETTINGS;
1643
1644 if (!ctx->bloom_settings) {
1645 bloom_settings.bits_per_entry = git_env_ulong("GIT_TEST_BLOOM_SETTINGS_BITS_PER_ENTRY",
1646 bloom_settings.bits_per_entry);
1647 bloom_settings.num_hashes = git_env_ulong("GIT_TEST_BLOOM_SETTINGS_NUM_HASHES",
1648 bloom_settings.num_hashes);
1649 ctx->bloom_settings = &bloom_settings;
1650 }
1651
1652 if (ctx->split) {
1653 struct strbuf tmp_file = STRBUF_INIT;
1654
1655 strbuf_addf(&tmp_file,
1656 "%s/info/commit-graphs/tmp_graph_XXXXXX",
1657 ctx->odb->path);
1658 ctx->graph_name = strbuf_detach(&tmp_file, NULL);
1659 } else {
1660 ctx->graph_name = get_commit_graph_filename(ctx->odb);
1661 }
1662
1663 if (safe_create_leading_directories(ctx->graph_name)) {
1664 UNLEAK(ctx->graph_name);
1665 error(_("unable to create leading directories of %s"),
1666 ctx->graph_name);
1667 return -1;
1668 }
1669
1670 if (ctx->split) {
1671 char *lock_name = get_chain_filename(ctx->odb);
1672
1673 hold_lock_file_for_update_mode(&lk, lock_name,
1674 LOCK_DIE_ON_ERROR, 0444);
1675
1676 fd = git_mkstemp_mode(ctx->graph_name, 0444);
1677 if (fd < 0) {
1678 error(_("unable to create temporary graph layer"));
1679 return -1;
1680 }
1681
1682 if (adjust_shared_perm(ctx->graph_name)) {
1683 error(_("unable to adjust shared permissions for '%s'"),
1684 ctx->graph_name);
1685 return -1;
1686 }
1687
1688 f = hashfd(fd, ctx->graph_name);
1689 } else {
1690 hold_lock_file_for_update_mode(&lk, ctx->graph_name,
1691 LOCK_DIE_ON_ERROR, 0444);
1692 fd = lk.tempfile->fd;
1693 f = hashfd(lk.tempfile->fd, lk.tempfile->filename.buf);
1694 }
1695
1696 chunks[0].id = GRAPH_CHUNKID_OIDFANOUT;
1697 chunks[0].size = GRAPH_FANOUT_SIZE;
1698 chunks[0].write_fn = write_graph_chunk_fanout;
1699 chunks[1].id = GRAPH_CHUNKID_OIDLOOKUP;
1700 chunks[1].size = hashsz * ctx->commits.nr;
1701 chunks[1].write_fn = write_graph_chunk_oids;
1702 chunks[2].id = GRAPH_CHUNKID_DATA;
1703 chunks[2].size = (hashsz + 16) * ctx->commits.nr;
1704 chunks[2].write_fn = write_graph_chunk_data;
1705 if (ctx->num_extra_edges) {
1706 chunks[num_chunks].id = GRAPH_CHUNKID_EXTRAEDGES;
1707 chunks[num_chunks].size = 4 * ctx->num_extra_edges;
1708 chunks[num_chunks].write_fn = write_graph_chunk_extra_edges;
1709 num_chunks++;
1710 }
1711 if (ctx->changed_paths) {
1712 chunks[num_chunks].id = GRAPH_CHUNKID_BLOOMINDEXES;
1713 chunks[num_chunks].size = sizeof(uint32_t) * ctx->commits.nr;
1714 chunks[num_chunks].write_fn = write_graph_chunk_bloom_indexes;
1715 num_chunks++;
1716 chunks[num_chunks].id = GRAPH_CHUNKID_BLOOMDATA;
1717 chunks[num_chunks].size = sizeof(uint32_t) * 3
1718 + ctx->total_bloom_filter_data_size;
1719 chunks[num_chunks].write_fn = write_graph_chunk_bloom_data;
1720 num_chunks++;
1721 }
1722 if (ctx->num_commit_graphs_after > 1) {
1723 chunks[num_chunks].id = GRAPH_CHUNKID_BASE;
1724 chunks[num_chunks].size = hashsz * (ctx->num_commit_graphs_after - 1);
1725 chunks[num_chunks].write_fn = write_graph_chunk_base;
1726 num_chunks++;
1727 }
1728
1729 chunks[num_chunks].id = 0;
1730 chunks[num_chunks].size = 0;
1731
1732 hashwrite_be32(f, GRAPH_SIGNATURE);
1733
1734 hashwrite_u8(f, GRAPH_VERSION);
1735 hashwrite_u8(f, oid_version());
1736 hashwrite_u8(f, num_chunks);
1737 hashwrite_u8(f, ctx->num_commit_graphs_after - 1);
1738
1739 chunk_offset = 8 + (num_chunks + 1) * GRAPH_CHUNKLOOKUP_WIDTH;
1740 for (i = 0; i <= num_chunks; i++) {
1741 uint32_t chunk_write[3];
1742
1743 chunk_write[0] = htonl(chunks[i].id);
1744 chunk_write[1] = htonl(chunk_offset >> 32);
1745 chunk_write[2] = htonl(chunk_offset & 0xffffffff);
1746 hashwrite(f, chunk_write, 12);
1747
1748 chunk_offset += chunks[i].size;
1749 }
1750
1751 if (ctx->report_progress) {
1752 strbuf_addf(&progress_title,
1753 Q_("Writing out commit graph in %d pass",
1754 "Writing out commit graph in %d passes",
1755 num_chunks),
1756 num_chunks);
1757 ctx->progress = start_delayed_progress(
1758 progress_title.buf,
1759 num_chunks * ctx->commits.nr);
1760 }
1761
1762 for (i = 0; i < num_chunks; i++) {
1763 uint64_t start_offset = f->total + f->offset;
1764
1765 if (chunks[i].write_fn(f, ctx))
1766 return -1;
1767
1768 if (f->total + f->offset != start_offset + chunks[i].size)
1769 BUG("expected to write %"PRId64" bytes to chunk %"PRIx32", but wrote %"PRId64" instead",
1770 chunks[i].size, chunks[i].id,
1771 f->total + f->offset - start_offset);
1772 }
1773
1774 stop_progress(&ctx->progress);
1775 strbuf_release(&progress_title);
1776
1777 if (ctx->split && ctx->base_graph_name && ctx->num_commit_graphs_after > 1) {
1778 char *new_base_hash = xstrdup(oid_to_hex(&ctx->new_base_graph->oid));
1779 char *new_base_name = get_split_graph_filename(ctx->new_base_graph->odb, new_base_hash);
1780
1781 free(ctx->commit_graph_filenames_after[ctx->num_commit_graphs_after - 2]);
1782 free(ctx->commit_graph_hash_after[ctx->num_commit_graphs_after - 2]);
1783 ctx->commit_graph_filenames_after[ctx->num_commit_graphs_after - 2] = new_base_name;
1784 ctx->commit_graph_hash_after[ctx->num_commit_graphs_after - 2] = new_base_hash;
1785 }
1786
1787 close_commit_graph(ctx->r->objects);
1788 finalize_hashfile(f, file_hash.hash, CSUM_HASH_IN_STREAM | CSUM_FSYNC);
1789
1790 if (ctx->split) {
1791 FILE *chainf = fdopen_lock_file(&lk, "w");
1792 char *final_graph_name;
1793 int result;
1794
1795 close(fd);
1796
1797 if (!chainf) {
1798 error(_("unable to open commit-graph chain file"));
1799 return -1;
1800 }
1801
1802 if (ctx->base_graph_name) {
1803 const char *dest;
1804 int idx = ctx->num_commit_graphs_after - 1;
1805 if (ctx->num_commit_graphs_after > 1)
1806 idx--;
1807
1808 dest = ctx->commit_graph_filenames_after[idx];
1809
1810 if (strcmp(ctx->base_graph_name, dest)) {
1811 result = rename(ctx->base_graph_name, dest);
1812
1813 if (result) {
1814 error(_("failed to rename base commit-graph file"));
1815 return -1;
1816 }
1817 }
1818 } else {
1819 char *graph_name = get_commit_graph_filename(ctx->odb);
1820 unlink(graph_name);
1821 }
1822
1823 ctx->commit_graph_hash_after[ctx->num_commit_graphs_after - 1] = xstrdup(oid_to_hex(&file_hash));
1824 final_graph_name = get_split_graph_filename(ctx->odb,
1825 ctx->commit_graph_hash_after[ctx->num_commit_graphs_after - 1]);
1826 ctx->commit_graph_filenames_after[ctx->num_commit_graphs_after - 1] = final_graph_name;
1827
1828 result = rename(ctx->graph_name, final_graph_name);
1829
1830 for (i = 0; i < ctx->num_commit_graphs_after; i++)
1831 fprintf(lk.tempfile->fp, "%s\n", ctx->commit_graph_hash_after[i]);
1832
1833 if (result) {
1834 error(_("failed to rename temporary commit-graph file"));
1835 return -1;
1836 }
1837 }
1838
1839 commit_lock_file(&lk);
1840
1841 return 0;
1842 }
1843
1844 static void split_graph_merge_strategy(struct write_commit_graph_context *ctx)
1845 {
1846 struct commit_graph *g;
1847 uint32_t num_commits;
1848 enum commit_graph_split_flags flags = COMMIT_GRAPH_SPLIT_UNSPECIFIED;
1849 uint32_t i;
1850
1851 int max_commits = 0;
1852 int size_mult = 2;
1853
1854 if (ctx->split_opts) {
1855 max_commits = ctx->split_opts->max_commits;
1856
1857 if (ctx->split_opts->size_multiple)
1858 size_mult = ctx->split_opts->size_multiple;
1859
1860 flags = ctx->split_opts->flags;
1861 }
1862
1863 g = ctx->r->objects->commit_graph;
1864 num_commits = ctx->commits.nr;
1865 if (flags == COMMIT_GRAPH_SPLIT_REPLACE)
1866 ctx->num_commit_graphs_after = 1;
1867 else
1868 ctx->num_commit_graphs_after = ctx->num_commit_graphs_before + 1;
1869
1870 if (flags != COMMIT_GRAPH_SPLIT_MERGE_PROHIBITED &&
1871 flags != COMMIT_GRAPH_SPLIT_REPLACE) {
1872 while (g && (g->num_commits <= size_mult * num_commits ||
1873 (max_commits && num_commits > max_commits))) {
1874 if (g->odb != ctx->odb)
1875 break;
1876
1877 num_commits += g->num_commits;
1878 g = g->base_graph;
1879
1880 ctx->num_commit_graphs_after--;
1881 }
1882 }
1883
1884 if (flags != COMMIT_GRAPH_SPLIT_REPLACE)
1885 ctx->new_base_graph = g;
1886 else if (ctx->num_commit_graphs_after != 1)
1887 BUG("split_graph_merge_strategy: num_commit_graphs_after "
1888 "should be 1 with --split=replace");
1889
1890 if (ctx->num_commit_graphs_after == 2) {
1891 char *old_graph_name = get_commit_graph_filename(g->odb);
1892
1893 if (!strcmp(g->filename, old_graph_name) &&
1894 g->odb != ctx->odb) {
1895 ctx->num_commit_graphs_after = 1;
1896 ctx->new_base_graph = NULL;
1897 }
1898
1899 free(old_graph_name);
1900 }
1901
1902 CALLOC_ARRAY(ctx->commit_graph_filenames_after, ctx->num_commit_graphs_after);
1903 CALLOC_ARRAY(ctx->commit_graph_hash_after, ctx->num_commit_graphs_after);
1904
1905 for (i = 0; i < ctx->num_commit_graphs_after &&
1906 i < ctx->num_commit_graphs_before; i++)
1907 ctx->commit_graph_filenames_after[i] = xstrdup(ctx->commit_graph_filenames_before[i]);
1908
1909 i = ctx->num_commit_graphs_before - 1;
1910 g = ctx->r->objects->commit_graph;
1911
1912 while (g) {
1913 if (i < ctx->num_commit_graphs_after)
1914 ctx->commit_graph_hash_after[i] = xstrdup(oid_to_hex(&g->oid));
1915
1916 i--;
1917 g = g->base_graph;
1918 }
1919 }
1920
1921 static void merge_commit_graph(struct write_commit_graph_context *ctx,
1922 struct commit_graph *g)
1923 {
1924 uint32_t i;
1925 uint32_t offset = g->num_commits_in_base;
1926
1927 ALLOC_GROW(ctx->commits.list, ctx->commits.nr + g->num_commits, ctx->commits.alloc);
1928
1929 for (i = 0; i < g->num_commits; i++) {
1930 struct object_id oid;
1931 struct commit *result;
1932
1933 display_progress(ctx->progress, i + 1);
1934
1935 load_oid_from_graph(g, i + offset, &oid);
1936
1937 /* only add commits if they still exist in the repo */
1938 result = lookup_commit_reference_gently(ctx->r, &oid, 1);
1939
1940 if (result) {
1941 ctx->commits.list[ctx->commits.nr] = result;
1942 ctx->commits.nr++;
1943 }
1944 }
1945 }
1946
1947 static int commit_compare(const void *_a, const void *_b)
1948 {
1949 const struct commit *a = *(const struct commit **)_a;
1950 const struct commit *b = *(const struct commit **)_b;
1951 return oidcmp(&a->object.oid, &b->object.oid);
1952 }
1953
1954 static void sort_and_scan_merged_commits(struct write_commit_graph_context *ctx)
1955 {
1956 uint32_t i;
1957
1958 if (ctx->report_progress)
1959 ctx->progress = start_delayed_progress(
1960 _("Scanning merged commits"),
1961 ctx->commits.nr);
1962
1963 QSORT(ctx->commits.list, ctx->commits.nr, commit_compare);
1964
1965 ctx->num_extra_edges = 0;
1966 for (i = 0; i < ctx->commits.nr; i++) {
1967 display_progress(ctx->progress, i);
1968
1969 if (i && oideq(&ctx->commits.list[i - 1]->object.oid,
1970 &ctx->commits.list[i]->object.oid)) {
1971 die(_("unexpected duplicate commit id %s"),
1972 oid_to_hex(&ctx->commits.list[i]->object.oid));
1973 } else {
1974 unsigned int num_parents;
1975
1976 num_parents = commit_list_count(ctx->commits.list[i]->parents);
1977 if (num_parents > 2)
1978 ctx->num_extra_edges += num_parents - 1;
1979 }
1980 }
1981
1982 stop_progress(&ctx->progress);
1983 }
1984
1985 static void merge_commit_graphs(struct write_commit_graph_context *ctx)
1986 {
1987 struct commit_graph *g = ctx->r->objects->commit_graph;
1988 uint32_t current_graph_number = ctx->num_commit_graphs_before;
1989
1990 while (g && current_graph_number >= ctx->num_commit_graphs_after) {
1991 current_graph_number--;
1992
1993 if (ctx->report_progress)
1994 ctx->progress = start_delayed_progress(_("Merging commit-graph"), 0);
1995
1996 merge_commit_graph(ctx, g);
1997 stop_progress(&ctx->progress);
1998
1999 g = g->base_graph;
2000 }
2001
2002 if (g) {
2003 ctx->new_base_graph = g;
2004 ctx->new_num_commits_in_base = g->num_commits + g->num_commits_in_base;
2005 }
2006
2007 if (ctx->new_base_graph)
2008 ctx->base_graph_name = xstrdup(ctx->new_base_graph->filename);
2009
2010 sort_and_scan_merged_commits(ctx);
2011 }
2012
2013 static void mark_commit_graphs(struct write_commit_graph_context *ctx)
2014 {
2015 uint32_t i;
2016 time_t now = time(NULL);
2017
2018 for (i = ctx->num_commit_graphs_after - 1; i < ctx->num_commit_graphs_before; i++) {
2019 struct stat st;
2020 struct utimbuf updated_time;
2021
2022 stat(ctx->commit_graph_filenames_before[i], &st);
2023
2024 updated_time.actime = st.st_atime;
2025 updated_time.modtime = now;
2026 utime(ctx->commit_graph_filenames_before[i], &updated_time);
2027 }
2028 }
2029
2030 static void expire_commit_graphs(struct write_commit_graph_context *ctx)
2031 {
2032 struct strbuf path = STRBUF_INIT;
2033 DIR *dir;
2034 struct dirent *de;
2035 size_t dirnamelen;
2036 timestamp_t expire_time = time(NULL);
2037
2038 if (ctx->split_opts && ctx->split_opts->expire_time)
2039 expire_time = ctx->split_opts->expire_time;
2040 if (!ctx->split) {
2041 char *chain_file_name = get_chain_filename(ctx->odb);
2042 unlink(chain_file_name);
2043 free(chain_file_name);
2044 ctx->num_commit_graphs_after = 0;
2045 }
2046
2047 strbuf_addstr(&path, ctx->odb->path);
2048 strbuf_addstr(&path, "/info/commit-graphs");
2049 dir = opendir(path.buf);
2050
2051 if (!dir)
2052 goto out;
2053
2054 strbuf_addch(&path, '/');
2055 dirnamelen = path.len;
2056 while ((de = readdir(dir)) != NULL) {
2057 struct stat st;
2058 uint32_t i, found = 0;
2059
2060 strbuf_setlen(&path, dirnamelen);
2061 strbuf_addstr(&path, de->d_name);
2062
2063 stat(path.buf, &st);
2064
2065 if (st.st_mtime > expire_time)
2066 continue;
2067 if (path.len < 6 || strcmp(path.buf + path.len - 6, ".graph"))
2068 continue;
2069
2070 for (i = 0; i < ctx->num_commit_graphs_after; i++) {
2071 if (!strcmp(ctx->commit_graph_filenames_after[i],
2072 path.buf)) {
2073 found = 1;
2074 break;
2075 }
2076 }
2077
2078 if (!found)
2079 unlink(path.buf);
2080 }
2081
2082 out:
2083 strbuf_release(&path);
2084 }
2085
2086 int write_commit_graph(struct object_directory *odb,
2087 struct string_list *pack_indexes,
2088 struct oidset *commits,
2089 enum commit_graph_write_flags flags,
2090 const struct split_commit_graph_opts *split_opts)
2091 {
2092 struct write_commit_graph_context *ctx;
2093 uint32_t i, count_distinct = 0;
2094 int res = 0;
2095 int replace = 0;
2096
2097 if (!commit_graph_compatible(the_repository))
2098 return 0;
2099
2100 ctx = xcalloc(1, sizeof(struct write_commit_graph_context));
2101 ctx->r = the_repository;
2102 ctx->odb = odb;
2103 ctx->append = flags & COMMIT_GRAPH_WRITE_APPEND ? 1 : 0;
2104 ctx->report_progress = flags & COMMIT_GRAPH_WRITE_PROGRESS ? 1 : 0;
2105 ctx->split = flags & COMMIT_GRAPH_WRITE_SPLIT ? 1 : 0;
2106 ctx->split_opts = split_opts;
2107 ctx->total_bloom_filter_data_size = 0;
2108
2109 if (flags & COMMIT_GRAPH_WRITE_BLOOM_FILTERS)
2110 ctx->changed_paths = 1;
2111 if (!(flags & COMMIT_GRAPH_NO_WRITE_BLOOM_FILTERS)) {
2112 struct commit_graph *g;
2113 prepare_commit_graph_one(ctx->r, ctx->odb);
2114
2115 g = ctx->r->objects->commit_graph;
2116
2117 /* We have changed-paths already. Keep them in the next graph */
2118 if (g && g->chunk_bloom_data) {
2119 ctx->changed_paths = 1;
2120 ctx->bloom_settings = g->bloom_filter_settings;
2121 }
2122 }
2123
2124 if (ctx->split) {
2125 struct commit_graph *g;
2126 prepare_commit_graph(ctx->r);
2127
2128 g = ctx->r->objects->commit_graph;
2129
2130 while (g) {
2131 ctx->num_commit_graphs_before++;
2132 g = g->base_graph;
2133 }
2134
2135 if (ctx->num_commit_graphs_before) {
2136 ALLOC_ARRAY(ctx->commit_graph_filenames_before, ctx->num_commit_graphs_before);
2137 i = ctx->num_commit_graphs_before;
2138 g = ctx->r->objects->commit_graph;
2139
2140 while (g) {
2141 ctx->commit_graph_filenames_before[--i] = xstrdup(g->filename);
2142 g = g->base_graph;
2143 }
2144 }
2145
2146 if (ctx->split_opts)
2147 replace = ctx->split_opts->flags & COMMIT_GRAPH_SPLIT_REPLACE;
2148 }
2149
2150 ctx->approx_nr_objects = approximate_object_count();
2151 ctx->oids.alloc = ctx->approx_nr_objects / 32;
2152
2153 if (ctx->split && split_opts && ctx->oids.alloc > split_opts->max_commits)
2154 ctx->oids.alloc = split_opts->max_commits;
2155
2156 if (ctx->append) {
2157 prepare_commit_graph_one(ctx->r, ctx->odb);
2158 if (ctx->r->objects->commit_graph)
2159 ctx->oids.alloc += ctx->r->objects->commit_graph->num_commits;
2160 }
2161
2162 if (ctx->oids.alloc < 1024)
2163 ctx->oids.alloc = 1024;
2164 ALLOC_ARRAY(ctx->oids.list, ctx->oids.alloc);
2165
2166 if (ctx->append && ctx->r->objects->commit_graph) {
2167 struct commit_graph *g = ctx->r->objects->commit_graph;
2168 for (i = 0; i < g->num_commits; i++) {
2169 const unsigned char *hash = g->chunk_oid_lookup + g->hash_len * i;
2170 hashcpy(ctx->oids.list[ctx->oids.nr++].hash, hash);
2171 }
2172 }
2173
2174 if (pack_indexes) {
2175 ctx->order_by_pack = 1;
2176 if ((res = fill_oids_from_packs(ctx, pack_indexes)))
2177 goto cleanup;
2178 }
2179
2180 if (commits) {
2181 if ((res = fill_oids_from_commits(ctx, commits)))
2182 goto cleanup;
2183 }
2184
2185 if (!pack_indexes && !commits) {
2186 ctx->order_by_pack = 1;
2187 fill_oids_from_all_packs(ctx);
2188 }
2189
2190 close_reachable(ctx);
2191
2192 count_distinct = count_distinct_commits(ctx);
2193
2194 if (count_distinct >= GRAPH_EDGE_LAST_MASK) {
2195 error(_("the commit graph format cannot write %d commits"), count_distinct);
2196 res = -1;
2197 goto cleanup;
2198 }
2199
2200 ctx->commits.alloc = count_distinct;
2201 ALLOC_ARRAY(ctx->commits.list, ctx->commits.alloc);
2202
2203 copy_oids_to_commits(ctx);
2204
2205 if (ctx->commits.nr >= GRAPH_EDGE_LAST_MASK) {
2206 error(_("too many commits to write graph"));
2207 res = -1;
2208 goto cleanup;
2209 }
2210
2211 if (!ctx->commits.nr && !replace)
2212 goto cleanup;
2213
2214 if (ctx->split) {
2215 split_graph_merge_strategy(ctx);
2216
2217 if (!replace)
2218 merge_commit_graphs(ctx);
2219 } else
2220 ctx->num_commit_graphs_after = 1;
2221
2222 compute_generation_numbers(ctx);
2223
2224 if (ctx->changed_paths)
2225 compute_bloom_filters(ctx);
2226
2227 res = write_commit_graph_file(ctx);
2228
2229 if (ctx->split)
2230 mark_commit_graphs(ctx);
2231
2232 expire_commit_graphs(ctx);
2233
2234 cleanup:
2235 free(ctx->graph_name);
2236 free(ctx->commits.list);
2237 free(ctx->oids.list);
2238
2239 if (ctx->commit_graph_filenames_after) {
2240 for (i = 0; i < ctx->num_commit_graphs_after; i++) {
2241 free(ctx->commit_graph_filenames_after[i]);
2242 free(ctx->commit_graph_hash_after[i]);
2243 }
2244
2245 for (i = 0; i < ctx->num_commit_graphs_before; i++)
2246 free(ctx->commit_graph_filenames_before[i]);
2247
2248 free(ctx->commit_graph_filenames_after);
2249 free(ctx->commit_graph_filenames_before);
2250 free(ctx->commit_graph_hash_after);
2251 }
2252
2253 free(ctx);
2254
2255 return res;
2256 }
2257
2258 #define VERIFY_COMMIT_GRAPH_ERROR_HASH 2
2259 static int verify_commit_graph_error;
2260
2261 static void graph_report(const char *fmt, ...)
2262 {
2263 va_list ap;
2264
2265 verify_commit_graph_error = 1;
2266 va_start(ap, fmt);
2267 vfprintf(stderr, fmt, ap);
2268 fprintf(stderr, "\n");
2269 va_end(ap);
2270 }
2271
2272 #define GENERATION_ZERO_EXISTS 1
2273 #define GENERATION_NUMBER_EXISTS 2
2274
2275 int verify_commit_graph(struct repository *r, struct commit_graph *g, int flags)
2276 {
2277 uint32_t i, cur_fanout_pos = 0;
2278 struct object_id prev_oid, cur_oid, checksum;
2279 int generation_zero = 0;
2280 struct hashfile *f;
2281 int devnull;
2282 struct progress *progress = NULL;
2283 int local_error = 0;
2284
2285 if (!g) {
2286 graph_report("no commit-graph file loaded");
2287 return 1;
2288 }
2289
2290 verify_commit_graph_error = verify_commit_graph_lite(g);
2291 if (verify_commit_graph_error)
2292 return verify_commit_graph_error;
2293
2294 devnull = open("/dev/null", O_WRONLY);
2295 f = hashfd(devnull, NULL);
2296 hashwrite(f, g->data, g->data_len - g->hash_len);
2297 finalize_hashfile(f, checksum.hash, CSUM_CLOSE);
2298 if (!hasheq(checksum.hash, g->data + g->data_len - g->hash_len)) {
2299 graph_report(_("the commit-graph file has incorrect checksum and is likely corrupt"));
2300 verify_commit_graph_error = VERIFY_COMMIT_GRAPH_ERROR_HASH;
2301 }
2302
2303 for (i = 0; i < g->num_commits; i++) {
2304 struct commit *graph_commit;
2305
2306 hashcpy(cur_oid.hash, g->chunk_oid_lookup + g->hash_len * i);
2307
2308 if (i && oidcmp(&prev_oid, &cur_oid) >= 0)
2309 graph_report(_("commit-graph has incorrect OID order: %s then %s"),
2310 oid_to_hex(&prev_oid),
2311 oid_to_hex(&cur_oid));
2312
2313 oidcpy(&prev_oid, &cur_oid);
2314
2315 while (cur_oid.hash[0] > cur_fanout_pos) {
2316 uint32_t fanout_value = get_be32(g->chunk_oid_fanout + cur_fanout_pos);
2317
2318 if (i != fanout_value)
2319 graph_report(_("commit-graph has incorrect fanout value: fanout[%d] = %u != %u"),
2320 cur_fanout_pos, fanout_value, i);
2321 cur_fanout_pos++;
2322 }
2323
2324 graph_commit = lookup_commit(r, &cur_oid);
2325 if (!parse_commit_in_graph_one(r, g, graph_commit))
2326 graph_report(_("failed to parse commit %s from commit-graph"),
2327 oid_to_hex(&cur_oid));
2328 }
2329
2330 while (cur_fanout_pos < 256) {
2331 uint32_t fanout_value = get_be32(g->chunk_oid_fanout + cur_fanout_pos);
2332
2333 if (g->num_commits != fanout_value)
2334 graph_report(_("commit-graph has incorrect fanout value: fanout[%d] = %u != %u"),
2335 cur_fanout_pos, fanout_value, i);
2336
2337 cur_fanout_pos++;
2338 }
2339
2340 if (verify_commit_graph_error & ~VERIFY_COMMIT_GRAPH_ERROR_HASH)
2341 return verify_commit_graph_error;
2342
2343 if (flags & COMMIT_GRAPH_WRITE_PROGRESS)
2344 progress = start_progress(_("Verifying commits in commit graph"),
2345 g->num_commits);
2346
2347 for (i = 0; i < g->num_commits; i++) {
2348 struct commit *graph_commit, *odb_commit;
2349 struct commit_list *graph_parents, *odb_parents;
2350 uint32_t max_generation = 0;
2351 uint32_t generation;
2352
2353 display_progress(progress, i + 1);
2354 hashcpy(cur_oid.hash, g->chunk_oid_lookup + g->hash_len * i);
2355
2356 graph_commit = lookup_commit(r, &cur_oid);
2357 odb_commit = (struct commit *)create_object(r, &cur_oid, alloc_commit_node(r));
2358 if (parse_commit_internal(odb_commit, 0, 0)) {
2359 graph_report(_("failed to parse commit %s from object database for commit-graph"),
2360 oid_to_hex(&cur_oid));
2361 continue;
2362 }
2363
2364 if (!oideq(&get_commit_tree_in_graph_one(r, g, graph_commit)->object.oid,
2365 get_commit_tree_oid(odb_commit)))
2366 graph_report(_("root tree OID for commit %s in commit-graph is %s != %s"),
2367 oid_to_hex(&cur_oid),
2368 oid_to_hex(get_commit_tree_oid(graph_commit)),
2369 oid_to_hex(get_commit_tree_oid(odb_commit)));
2370
2371 graph_parents = graph_commit->parents;
2372 odb_parents = odb_commit->parents;
2373
2374 while (graph_parents) {
2375 if (odb_parents == NULL) {
2376 graph_report(_("commit-graph parent list for commit %s is too long"),
2377 oid_to_hex(&cur_oid));
2378 break;
2379 }
2380
2381 /* parse parent in case it is in a base graph */
2382 parse_commit_in_graph_one(r, g, graph_parents->item);
2383
2384 if (!oideq(&graph_parents->item->object.oid, &odb_parents->item->object.oid))
2385 graph_report(_("commit-graph parent for %s is %s != %s"),
2386 oid_to_hex(&cur_oid),
2387 oid_to_hex(&graph_parents->item->object.oid),
2388 oid_to_hex(&odb_parents->item->object.oid));
2389
2390 generation = commit_graph_generation(graph_parents->item);
2391 if (generation > max_generation)
2392 max_generation = generation;
2393
2394 graph_parents = graph_parents->next;
2395 odb_parents = odb_parents->next;
2396 }
2397
2398 if (odb_parents != NULL)
2399 graph_report(_("commit-graph parent list for commit %s terminates early"),
2400 oid_to_hex(&cur_oid));
2401
2402 if (!commit_graph_generation(graph_commit)) {
2403 if (generation_zero == GENERATION_NUMBER_EXISTS)
2404 graph_report(_("commit-graph has generation number zero for commit %s, but non-zero elsewhere"),
2405 oid_to_hex(&cur_oid));
2406 generation_zero = GENERATION_ZERO_EXISTS;
2407 } else if (generation_zero == GENERATION_ZERO_EXISTS)
2408 graph_report(_("commit-graph has non-zero generation number for commit %s, but zero elsewhere"),
2409 oid_to_hex(&cur_oid));
2410
2411 if (generation_zero == GENERATION_ZERO_EXISTS)
2412 continue;
2413
2414 /*
2415 * If one of our parents has generation GENERATION_NUMBER_MAX, then
2416 * our generation is also GENERATION_NUMBER_MAX. Decrement to avoid
2417 * extra logic in the following condition.
2418 */
2419 if (max_generation == GENERATION_NUMBER_MAX)
2420 max_generation--;
2421
2422 generation = commit_graph_generation(graph_commit);
2423 if (generation != max_generation + 1)
2424 graph_report(_("commit-graph generation for commit %s is %u != %u"),
2425 oid_to_hex(&cur_oid),
2426 generation,
2427 max_generation + 1);
2428
2429 if (graph_commit->date != odb_commit->date)
2430 graph_report(_("commit date for commit %s in commit-graph is %"PRItime" != %"PRItime),
2431 oid_to_hex(&cur_oid),
2432 graph_commit->date,
2433 odb_commit->date);
2434 }
2435 stop_progress(&progress);
2436
2437 local_error = verify_commit_graph_error;
2438
2439 if (!(flags & COMMIT_GRAPH_VERIFY_SHALLOW) && g->base_graph)
2440 local_error |= verify_commit_graph(r, g->base_graph, flags);
2441
2442 return local_error;
2443 }
2444
2445 void free_commit_graph(struct commit_graph *g)
2446 {
2447 if (!g)
2448 return;
2449 if (g->data) {
2450 munmap((void *)g->data, g->data_len);
2451 g->data = NULL;
2452 }
2453 free(g->filename);
2454 free(g->bloom_filter_settings);
2455 free(g);
2456 }
2457
2458 void disable_commit_graph(struct repository *r)
2459 {
2460 r->commit_graph_disabled = 1;
2461 }
The Best VCS Around