Merge branch 'jb/commit-graph-doc-fix'
[git] / commit-graph.c
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 }