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