]>
Commit | Line | Data |
---|---|---|
08fd81c9 DS |
1 | #include "cache.h" |
2 | #include "config.h" | |
33286dcd | 3 | #include "dir.h" |
08fd81c9 DS |
4 | #include "git-compat-util.h" |
5 | #include "lockfile.h" | |
6 | #include "pack.h" | |
7 | #include "packfile.h" | |
8 | #include "commit.h" | |
9 | #include "object.h" | |
59fb8770 | 10 | #include "refs.h" |
08fd81c9 DS |
11 | #include "revision.h" |
12 | #include "sha1-lookup.h" | |
13 | #include "commit-graph.h" | |
b10edb2d | 14 | #include "object-store.h" |
96af91d4 | 15 | #include "alloc.h" |
d6538246 DS |
16 | #include "hashmap.h" |
17 | #include "replace-object.h" | |
7b0f2292 | 18 | #include "progress.h" |
08fd81c9 DS |
19 | |
20 | #define GRAPH_SIGNATURE 0x43475048 /* "CGPH" */ | |
21 | #define GRAPH_CHUNKID_OIDFANOUT 0x4f494446 /* "OIDF" */ | |
22 | #define GRAPH_CHUNKID_OIDLOOKUP 0x4f49444c /* "OIDL" */ | |
23 | #define GRAPH_CHUNKID_DATA 0x43444154 /* "CDAT" */ | |
5af7417b | 24 | #define GRAPH_CHUNKID_EXTRAEDGES 0x45444745 /* "EDGE" */ |
08fd81c9 | 25 | |
c1665998 | 26 | #define GRAPH_DATA_WIDTH (the_hash_algo->rawsz + 16) |
08fd81c9 DS |
27 | |
28 | #define GRAPH_VERSION_1 0x1 | |
29 | #define GRAPH_VERSION GRAPH_VERSION_1 | |
30 | ||
5af7417b | 31 | #define GRAPH_EXTRA_EDGES_NEEDED 0x80000000 |
08fd81c9 DS |
32 | #define GRAPH_EDGE_LAST_MASK 0x7fffffff |
33 | #define GRAPH_PARENT_NONE 0x70000000 | |
34 | ||
35 | #define GRAPH_LAST_EDGE 0x80000000 | |
36 | ||
0e3b97cc | 37 | #define GRAPH_HEADER_SIZE 8 |
08fd81c9 DS |
38 | #define GRAPH_FANOUT_SIZE (4 * 256) |
39 | #define GRAPH_CHUNKLOOKUP_WIDTH 12 | |
0e3b97cc | 40 | #define GRAPH_MIN_SIZE (GRAPH_HEADER_SIZE + 4 * GRAPH_CHUNKLOOKUP_WIDTH \ |
c1665998 | 41 | + GRAPH_FANOUT_SIZE + the_hash_algo->rawsz) |
08fd81c9 | 42 | |
2a2e32bd | 43 | char *get_commit_graph_filename(const char *obj_dir) |
08fd81c9 DS |
44 | { |
45 | return xstrfmt("%s/info/commit-graph", obj_dir); | |
46 | } | |
47 | ||
5c84b339 DS |
48 | static char *get_split_graph_filename(const char *obj_dir, |
49 | const char *oid_hex) | |
50 | { | |
51 | return xstrfmt("%s/info/commit-graphs/graph-%s.graph", | |
52 | obj_dir, | |
53 | oid_hex); | |
54 | } | |
55 | ||
56 | static char *get_chain_filename(const char *obj_dir) | |
57 | { | |
58 | return xstrfmt("%s/info/commit-graphs/commit-graph-chain", obj_dir); | |
59 | } | |
60 | ||
c1665998 | 61 | static uint8_t oid_version(void) |
62 | { | |
63 | return 1; | |
64 | } | |
65 | ||
2a2e32bd DS |
66 | static struct commit_graph *alloc_commit_graph(void) |
67 | { | |
68 | struct commit_graph *g = xcalloc(1, sizeof(*g)); | |
69 | g->graph_fd = -1; | |
70 | ||
71 | return g; | |
72 | } | |
73 | ||
d6538246 DS |
74 | extern int read_replace_refs; |
75 | ||
76 | static int commit_graph_compatible(struct repository *r) | |
77 | { | |
5cef295f DS |
78 | if (!r->gitdir) |
79 | return 0; | |
80 | ||
d6538246 DS |
81 | if (read_replace_refs) { |
82 | prepare_replace_object(r); | |
83 | if (hashmap_get_size(&r->objects->replace_map->map)) | |
84 | return 0; | |
85 | } | |
86 | ||
20fd6d57 DS |
87 | prepare_commit_graft(r); |
88 | if (r->parsed_objects && r->parsed_objects->grafts_nr) | |
89 | return 0; | |
90 | if (is_repository_shallow(r)) | |
91 | return 0; | |
92 | ||
d6538246 DS |
93 | return 1; |
94 | } | |
95 | ||
61df89c8 ÆAB |
96 | int open_commit_graph(const char *graph_file, int *fd, struct stat *st) |
97 | { | |
98 | *fd = git_open(graph_file); | |
99 | if (*fd < 0) | |
100 | return 0; | |
101 | if (fstat(*fd, st)) { | |
102 | close(*fd); | |
103 | return 0; | |
104 | } | |
105 | return 1; | |
106 | } | |
107 | ||
67a530fa | 108 | struct commit_graph *load_commit_graph_one_fd_st(int fd, struct stat *st) |
2a2e32bd DS |
109 | { |
110 | void *graph_map; | |
2a2e32bd | 111 | size_t graph_size; |
aa658574 | 112 | struct commit_graph *ret; |
2a2e32bd | 113 | |
61df89c8 | 114 | graph_size = xsize_t(st->st_size); |
2a2e32bd DS |
115 | |
116 | if (graph_size < GRAPH_MIN_SIZE) { | |
117 | close(fd); | |
67a530fa | 118 | error(_("commit-graph file is too small")); |
61df89c8 | 119 | return NULL; |
2a2e32bd DS |
120 | } |
121 | graph_map = xmmap(NULL, graph_size, PROT_READ, MAP_PRIVATE, fd, 0); | |
aa658574 JS |
122 | ret = parse_commit_graph(graph_map, fd, graph_size); |
123 | ||
124 | if (!ret) { | |
125 | munmap(graph_map, graph_size); | |
126 | close(fd); | |
aa658574 JS |
127 | } |
128 | ||
129 | return ret; | |
130 | } | |
131 | ||
2ac138d5 ÆAB |
132 | static int verify_commit_graph_lite(struct commit_graph *g) |
133 | { | |
134 | /* | |
135 | * Basic validation shared between parse_commit_graph() | |
136 | * which'll be called every time the graph is used, and the | |
137 | * much more expensive verify_commit_graph() used by | |
138 | * "commit-graph verify". | |
139 | * | |
140 | * There should only be very basic checks here to ensure that | |
141 | * we don't e.g. segfault in fill_commit_in_graph(), but | |
142 | * because this is a very hot codepath nothing that e.g. loops | |
143 | * over g->num_commits, or runs a checksum on the commit-graph | |
144 | * itself. | |
145 | */ | |
146 | if (!g->chunk_oid_fanout) { | |
147 | error("commit-graph is missing the OID Fanout chunk"); | |
148 | return 1; | |
149 | } | |
150 | if (!g->chunk_oid_lookup) { | |
151 | error("commit-graph is missing the OID Lookup chunk"); | |
152 | return 1; | |
153 | } | |
154 | if (!g->chunk_commit_data) { | |
155 | error("commit-graph is missing the Commit Data chunk"); | |
156 | return 1; | |
157 | } | |
158 | ||
159 | return 0; | |
160 | } | |
161 | ||
aa658574 JS |
162 | struct commit_graph *parse_commit_graph(void *graph_map, int fd, |
163 | size_t graph_size) | |
164 | { | |
165 | const unsigned char *data, *chunk_lookup; | |
166 | uint32_t i; | |
167 | struct commit_graph *graph; | |
168 | uint64_t last_chunk_offset; | |
169 | uint32_t last_chunk_id; | |
170 | uint32_t graph_signature; | |
171 | unsigned char graph_version, hash_version; | |
172 | ||
173 | if (!graph_map) | |
174 | return NULL; | |
175 | ||
176 | if (graph_size < GRAPH_MIN_SIZE) | |
177 | return NULL; | |
178 | ||
2a2e32bd DS |
179 | data = (const unsigned char *)graph_map; |
180 | ||
181 | graph_signature = get_be32(data); | |
182 | if (graph_signature != GRAPH_SIGNATURE) { | |
93b4405f | 183 | error(_("commit-graph signature %X does not match signature %X"), |
2a2e32bd | 184 | graph_signature, GRAPH_SIGNATURE); |
aa658574 | 185 | return NULL; |
2a2e32bd DS |
186 | } |
187 | ||
188 | graph_version = *(unsigned char*)(data + 4); | |
189 | if (graph_version != GRAPH_VERSION) { | |
93b4405f | 190 | error(_("commit-graph version %X does not match version %X"), |
2a2e32bd | 191 | graph_version, GRAPH_VERSION); |
aa658574 | 192 | return NULL; |
2a2e32bd DS |
193 | } |
194 | ||
195 | hash_version = *(unsigned char*)(data + 5); | |
c1665998 | 196 | if (hash_version != oid_version()) { |
93b4405f | 197 | error(_("commit-graph hash version %X does not match version %X"), |
c1665998 | 198 | hash_version, oid_version()); |
aa658574 | 199 | return NULL; |
2a2e32bd DS |
200 | } |
201 | ||
202 | graph = alloc_commit_graph(); | |
203 | ||
c1665998 | 204 | graph->hash_len = the_hash_algo->rawsz; |
2a2e32bd DS |
205 | graph->num_chunks = *(unsigned char*)(data + 6); |
206 | graph->graph_fd = fd; | |
207 | graph->data = graph_map; | |
208 | graph->data_len = graph_size; | |
209 | ||
210 | last_chunk_id = 0; | |
211 | last_chunk_offset = 8; | |
212 | chunk_lookup = data + 8; | |
213 | for (i = 0; i < graph->num_chunks; i++) { | |
d2b86fba JS |
214 | uint32_t chunk_id; |
215 | uint64_t chunk_offset; | |
2a2e32bd DS |
216 | int chunk_repeated = 0; |
217 | ||
d2b86fba JS |
218 | if (data + graph_size - chunk_lookup < |
219 | GRAPH_CHUNKLOOKUP_WIDTH) { | |
93b4405f | 220 | error(_("commit-graph chunk lookup table entry missing; file may be incomplete")); |
d2b86fba JS |
221 | free(graph); |
222 | return NULL; | |
223 | } | |
224 | ||
225 | chunk_id = get_be32(chunk_lookup + 0); | |
226 | chunk_offset = get_be64(chunk_lookup + 4); | |
227 | ||
2a2e32bd DS |
228 | chunk_lookup += GRAPH_CHUNKLOOKUP_WIDTH; |
229 | ||
c1665998 | 230 | if (chunk_offset > graph_size - the_hash_algo->rawsz) { |
93b4405f | 231 | error(_("commit-graph improper chunk offset %08x%08x"), (uint32_t)(chunk_offset >> 32), |
2a2e32bd | 232 | (uint32_t)chunk_offset); |
aa658574 JS |
233 | free(graph); |
234 | return NULL; | |
2a2e32bd DS |
235 | } |
236 | ||
237 | switch (chunk_id) { | |
238 | case GRAPH_CHUNKID_OIDFANOUT: | |
239 | if (graph->chunk_oid_fanout) | |
240 | chunk_repeated = 1; | |
241 | else | |
242 | graph->chunk_oid_fanout = (uint32_t*)(data + chunk_offset); | |
243 | break; | |
244 | ||
245 | case GRAPH_CHUNKID_OIDLOOKUP: | |
246 | if (graph->chunk_oid_lookup) | |
247 | chunk_repeated = 1; | |
248 | else | |
249 | graph->chunk_oid_lookup = data + chunk_offset; | |
250 | break; | |
251 | ||
252 | case GRAPH_CHUNKID_DATA: | |
253 | if (graph->chunk_commit_data) | |
254 | chunk_repeated = 1; | |
255 | else | |
256 | graph->chunk_commit_data = data + chunk_offset; | |
257 | break; | |
258 | ||
5af7417b SG |
259 | case GRAPH_CHUNKID_EXTRAEDGES: |
260 | if (graph->chunk_extra_edges) | |
2a2e32bd DS |
261 | chunk_repeated = 1; |
262 | else | |
5af7417b | 263 | graph->chunk_extra_edges = data + chunk_offset; |
2a2e32bd DS |
264 | break; |
265 | } | |
266 | ||
267 | if (chunk_repeated) { | |
93b4405f | 268 | error(_("commit-graph chunk id %08x appears multiple times"), chunk_id); |
aa658574 JS |
269 | free(graph); |
270 | return NULL; | |
2a2e32bd DS |
271 | } |
272 | ||
273 | if (last_chunk_id == GRAPH_CHUNKID_OIDLOOKUP) | |
274 | { | |
275 | graph->num_commits = (chunk_offset - last_chunk_offset) | |
276 | / graph->hash_len; | |
277 | } | |
278 | ||
279 | last_chunk_id = chunk_id; | |
280 | last_chunk_offset = chunk_offset; | |
281 | } | |
282 | ||
2ac138d5 ÆAB |
283 | if (verify_commit_graph_lite(graph)) |
284 | return NULL; | |
285 | ||
2a2e32bd | 286 | return graph; |
2a2e32bd DS |
287 | } |
288 | ||
61df89c8 ÆAB |
289 | static struct commit_graph *load_commit_graph_one(const char *graph_file) |
290 | { | |
291 | ||
292 | struct stat st; | |
293 | int fd; | |
294 | int open_ok = open_commit_graph(graph_file, &fd, &st); | |
295 | ||
296 | if (!open_ok) | |
297 | return NULL; | |
298 | ||
67a530fa | 299 | return load_commit_graph_one_fd_st(fd, &st); |
61df89c8 ÆAB |
300 | } |
301 | ||
5c84b339 DS |
302 | static struct commit_graph *load_commit_graph_v1(struct repository *r, const char *obj_dir) |
303 | { | |
304 | char *graph_name = get_commit_graph_filename(obj_dir); | |
305 | struct commit_graph *g = load_commit_graph_one(graph_name); | |
306 | free(graph_name); | |
307 | ||
308 | return g; | |
309 | } | |
310 | ||
311 | static int add_graph_to_chain(struct commit_graph *g, | |
312 | struct commit_graph *chain, | |
313 | struct object_id *oids, | |
314 | int n) | |
315 | { | |
316 | struct commit_graph *cur_g = chain; | |
317 | ||
318 | while (n) { | |
319 | n--; | |
320 | cur_g = cur_g->base_graph; | |
321 | } | |
322 | ||
323 | g->base_graph = chain; | |
324 | ||
325 | if (chain) | |
326 | g->num_commits_in_base = chain->num_commits + chain->num_commits_in_base; | |
327 | ||
328 | return 1; | |
329 | } | |
330 | ||
331 | static struct commit_graph *load_commit_graph_chain(struct repository *r, const char *obj_dir) | |
332 | { | |
333 | struct commit_graph *graph_chain = NULL; | |
334 | struct strbuf line = STRBUF_INIT; | |
335 | struct stat st; | |
336 | struct object_id *oids; | |
337 | int i = 0, valid = 1, count; | |
338 | char *chain_name = get_chain_filename(obj_dir); | |
339 | FILE *fp; | |
340 | int stat_res; | |
341 | ||
342 | fp = fopen(chain_name, "r"); | |
343 | stat_res = stat(chain_name, &st); | |
344 | free(chain_name); | |
345 | ||
346 | if (!fp || | |
347 | stat_res || | |
348 | st.st_size <= the_hash_algo->hexsz) | |
349 | return NULL; | |
350 | ||
351 | count = st.st_size / (the_hash_algo->hexsz + 1); | |
352 | oids = xcalloc(count, sizeof(struct object_id)); | |
353 | ||
354 | for (i = 0; i < count && valid; i++) { | |
355 | char *graph_name; | |
356 | struct commit_graph *g; | |
357 | ||
358 | if (strbuf_getline_lf(&line, fp) == EOF) | |
359 | break; | |
360 | ||
361 | if (get_oid_hex(line.buf, &oids[i])) { | |
362 | warning(_("invalid commit-graph chain: line '%s' not a hash"), | |
363 | line.buf); | |
364 | valid = 0; | |
365 | break; | |
366 | } | |
367 | ||
368 | graph_name = get_split_graph_filename(obj_dir, line.buf); | |
369 | g = load_commit_graph_one(graph_name); | |
370 | free(graph_name); | |
371 | ||
372 | if (g && add_graph_to_chain(g, graph_chain, oids, i)) | |
373 | graph_chain = g; | |
374 | else | |
375 | valid = 0; | |
376 | } | |
377 | ||
378 | free(oids); | |
379 | fclose(fp); | |
380 | ||
381 | return graph_chain; | |
382 | } | |
383 | ||
384 | static struct commit_graph *read_commit_graph_one(struct repository *r, const char *obj_dir) | |
385 | { | |
386 | struct commit_graph *g = load_commit_graph_v1(r, obj_dir); | |
387 | ||
388 | if (!g) | |
389 | g = load_commit_graph_chain(r, obj_dir); | |
390 | ||
391 | return g; | |
392 | } | |
393 | ||
dade47c0 | 394 | static void prepare_commit_graph_one(struct repository *r, const char *obj_dir) |
177722b3 | 395 | { |
177722b3 | 396 | |
dade47c0 | 397 | if (r->objects->commit_graph) |
177722b3 DS |
398 | return; |
399 | ||
5c84b339 | 400 | r->objects->commit_graph = read_commit_graph_one(r, obj_dir); |
177722b3 DS |
401 | } |
402 | ||
5faf357b JT |
403 | /* |
404 | * Return 1 if commit_graph is non-NULL, and 0 otherwise. | |
405 | * | |
406 | * On the first invocation, this function attemps to load the commit | |
407 | * graph if the_repository is configured to have one. | |
408 | */ | |
dade47c0 | 409 | static int prepare_commit_graph(struct repository *r) |
177722b3 | 410 | { |
263db403 | 411 | struct object_directory *odb; |
dade47c0 JT |
412 | int config_value; |
413 | ||
43d35618 ÆAB |
414 | if (git_env_bool(GIT_TEST_COMMIT_GRAPH_DIE_ON_LOAD, 0)) |
415 | die("dying as requested by the '%s' variable on commit-graph load!", | |
416 | GIT_TEST_COMMIT_GRAPH_DIE_ON_LOAD); | |
417 | ||
dade47c0 JT |
418 | if (r->objects->commit_graph_attempted) |
419 | return !!r->objects->commit_graph; | |
420 | r->objects->commit_graph_attempted = 1; | |
421 | ||
859fdc0c DS |
422 | if (!git_env_bool(GIT_TEST_COMMIT_GRAPH, 0) && |
423 | (repo_config_get_bool(r, "core.commitgraph", &config_value) || | |
424 | !config_value)) | |
dade47c0 JT |
425 | /* |
426 | * This repository is not configured to use commit graphs, so | |
427 | * do not load one. (But report commit_graph_attempted anyway | |
428 | * so that commit graph loading is not attempted again for this | |
429 | * repository.) | |
430 | */ | |
5faf357b JT |
431 | return 0; |
432 | ||
d6538246 DS |
433 | if (!commit_graph_compatible(r)) |
434 | return 0; | |
435 | ||
dade47c0 | 436 | prepare_alt_odb(r); |
f0eaf638 | 437 | for (odb = r->objects->odb; |
263db403 JK |
438 | !r->objects->commit_graph && odb; |
439 | odb = odb->next) | |
440 | prepare_commit_graph_one(r, odb->path); | |
dade47c0 | 441 | return !!r->objects->commit_graph; |
177722b3 DS |
442 | } |
443 | ||
6cc01743 DS |
444 | int generation_numbers_enabled(struct repository *r) |
445 | { | |
446 | uint32_t first_generation; | |
447 | struct commit_graph *g; | |
448 | if (!prepare_commit_graph(r)) | |
449 | return 0; | |
450 | ||
451 | g = r->objects->commit_graph; | |
452 | ||
453 | if (!g->num_commits) | |
454 | return 0; | |
455 | ||
456 | first_generation = get_be32(g->chunk_commit_data + | |
457 | g->hash_len + 8) >> 2; | |
458 | ||
459 | return !!first_generation; | |
460 | } | |
461 | ||
d4f4d60f DS |
462 | static void close_commit_graph_one(struct commit_graph *g) |
463 | { | |
464 | if (!g) | |
465 | return; | |
466 | ||
467 | close_commit_graph_one(g->base_graph); | |
468 | free_commit_graph(g); | |
469 | } | |
470 | ||
c3a3a964 | 471 | void close_commit_graph(struct raw_object_store *o) |
177722b3 | 472 | { |
d4f4d60f | 473 | close_commit_graph_one(o->commit_graph); |
c3a3a964 | 474 | o->commit_graph = NULL; |
177722b3 DS |
475 | } |
476 | ||
477 | static int bsearch_graph(struct commit_graph *g, struct object_id *oid, uint32_t *pos) | |
478 | { | |
479 | return bsearch_hash(oid->hash, g->chunk_oid_fanout, | |
480 | g->chunk_oid_lookup, g->hash_len, pos); | |
481 | } | |
482 | ||
d4f4d60f DS |
483 | static void load_oid_from_graph(struct commit_graph *g, |
484 | uint32_t pos, | |
485 | struct object_id *oid) | |
486 | { | |
487 | uint32_t lex_index; | |
488 | ||
489 | while (g && pos < g->num_commits_in_base) | |
490 | g = g->base_graph; | |
491 | ||
492 | if (!g) | |
493 | BUG("NULL commit-graph"); | |
494 | ||
495 | if (pos >= g->num_commits + g->num_commits_in_base) | |
496 | die(_("invalid commit position. commit-graph is likely corrupt")); | |
497 | ||
498 | lex_index = pos - g->num_commits_in_base; | |
499 | ||
500 | hashcpy(oid->hash, g->chunk_oid_lookup + g->hash_len * lex_index); | |
501 | } | |
502 | ||
4f542b7a SB |
503 | static struct commit_list **insert_parent_or_die(struct repository *r, |
504 | struct commit_graph *g, | |
d4f4d60f | 505 | uint32_t pos, |
177722b3 DS |
506 | struct commit_list **pptr) |
507 | { | |
508 | struct commit *c; | |
509 | struct object_id oid; | |
96af91d4 | 510 | |
d4f4d60f DS |
511 | if (pos >= g->num_commits + g->num_commits_in_base) |
512 | die("invalid parent position %"PRIu32, pos); | |
53614b13 | 513 | |
d4f4d60f | 514 | load_oid_from_graph(g, pos, &oid); |
4f542b7a | 515 | c = lookup_commit(r, &oid); |
177722b3 | 516 | if (!c) |
4f5b532d | 517 | die(_("could not find commit %s"), oid_to_hex(&oid)); |
177722b3 DS |
518 | c->graph_pos = pos; |
519 | return &commit_list_insert(c, pptr)->next; | |
520 | } | |
521 | ||
e2838d85 DS |
522 | static void fill_commit_graph_info(struct commit *item, struct commit_graph *g, uint32_t pos) |
523 | { | |
d4f4d60f DS |
524 | const unsigned char *commit_data; |
525 | uint32_t lex_index; | |
526 | ||
527 | while (pos < g->num_commits_in_base) | |
528 | g = g->base_graph; | |
529 | ||
530 | lex_index = pos - g->num_commits_in_base; | |
531 | commit_data = g->chunk_commit_data + GRAPH_DATA_WIDTH * lex_index; | |
e2838d85 DS |
532 | item->graph_pos = pos; |
533 | item->generation = get_be32(commit_data + g->hash_len + 8) >> 2; | |
534 | } | |
535 | ||
4f542b7a SB |
536 | static int fill_commit_in_graph(struct repository *r, |
537 | struct commit *item, | |
538 | struct commit_graph *g, uint32_t pos) | |
177722b3 | 539 | { |
177722b3 DS |
540 | uint32_t edge_value; |
541 | uint32_t *parent_data_ptr; | |
542 | uint64_t date_low, date_high; | |
543 | struct commit_list **pptr; | |
d4f4d60f DS |
544 | const unsigned char *commit_data; |
545 | uint32_t lex_index; | |
177722b3 | 546 | |
d4f4d60f DS |
547 | while (pos < g->num_commits_in_base) |
548 | g = g->base_graph; | |
549 | ||
550 | if (pos >= g->num_commits + g->num_commits_in_base) | |
551 | die(_("invalid commit position. commit-graph is likely corrupt")); | |
552 | ||
553 | /* | |
554 | * Store the "full" position, but then use the | |
555 | * "local" position for the rest of the calculation. | |
556 | */ | |
177722b3 | 557 | item->graph_pos = pos; |
d4f4d60f DS |
558 | lex_index = pos - g->num_commits_in_base; |
559 | ||
560 | commit_data = g->chunk_commit_data + (g->hash_len + 16) * lex_index; | |
561 | ||
562 | item->object.parsed = 1; | |
177722b3 | 563 | |
7b8a21db | 564 | item->maybe_tree = NULL; |
177722b3 DS |
565 | |
566 | date_high = get_be32(commit_data + g->hash_len + 8) & 0x3; | |
567 | date_low = get_be32(commit_data + g->hash_len + 12); | |
568 | item->date = (timestamp_t)((date_high << 32) | date_low); | |
569 | ||
83073cc9 DS |
570 | item->generation = get_be32(commit_data + g->hash_len + 8) >> 2; |
571 | ||
177722b3 DS |
572 | pptr = &item->parents; |
573 | ||
574 | edge_value = get_be32(commit_data + g->hash_len); | |
575 | if (edge_value == GRAPH_PARENT_NONE) | |
576 | return 1; | |
4f542b7a | 577 | pptr = insert_parent_or_die(r, g, edge_value, pptr); |
177722b3 DS |
578 | |
579 | edge_value = get_be32(commit_data + g->hash_len + 4); | |
580 | if (edge_value == GRAPH_PARENT_NONE) | |
581 | return 1; | |
5af7417b | 582 | if (!(edge_value & GRAPH_EXTRA_EDGES_NEEDED)) { |
4f542b7a | 583 | pptr = insert_parent_or_die(r, g, edge_value, pptr); |
177722b3 DS |
584 | return 1; |
585 | } | |
586 | ||
5af7417b | 587 | parent_data_ptr = (uint32_t*)(g->chunk_extra_edges + |
177722b3 DS |
588 | 4 * (uint64_t)(edge_value & GRAPH_EDGE_LAST_MASK)); |
589 | do { | |
590 | edge_value = get_be32(parent_data_ptr); | |
4f542b7a | 591 | pptr = insert_parent_or_die(r, g, |
177722b3 DS |
592 | edge_value & GRAPH_EDGE_LAST_MASK, |
593 | pptr); | |
594 | parent_data_ptr++; | |
595 | } while (!(edge_value & GRAPH_LAST_EDGE)); | |
596 | ||
597 | return 1; | |
598 | } | |
599 | ||
e2838d85 DS |
600 | static int find_commit_in_graph(struct commit *item, struct commit_graph *g, uint32_t *pos) |
601 | { | |
602 | if (item->graph_pos != COMMIT_NOT_FROM_GRAPH) { | |
603 | *pos = item->graph_pos; | |
604 | return 1; | |
605 | } else { | |
d4f4d60f DS |
606 | struct commit_graph *cur_g = g; |
607 | uint32_t lex_index; | |
608 | ||
609 | while (cur_g && !bsearch_graph(cur_g, &(item->object.oid), &lex_index)) | |
610 | cur_g = cur_g->base_graph; | |
611 | ||
612 | if (cur_g) { | |
613 | *pos = lex_index + cur_g->num_commits_in_base; | |
614 | return 1; | |
615 | } | |
616 | ||
617 | return 0; | |
e2838d85 DS |
618 | } |
619 | } | |
620 | ||
4f542b7a SB |
621 | static int parse_commit_in_graph_one(struct repository *r, |
622 | struct commit_graph *g, | |
623 | struct commit *item) | |
177722b3 | 624 | { |
e2838d85 DS |
625 | uint32_t pos; |
626 | ||
177722b3 DS |
627 | if (item->object.parsed) |
628 | return 1; | |
ee797053 DS |
629 | |
630 | if (find_commit_in_graph(item, g, &pos)) | |
4f542b7a | 631 | return fill_commit_in_graph(r, item, g, pos); |
ee797053 DS |
632 | |
633 | return 0; | |
634 | } | |
635 | ||
dade47c0 | 636 | int parse_commit_in_graph(struct repository *r, struct commit *item) |
ee797053 | 637 | { |
dade47c0 | 638 | if (!prepare_commit_graph(r)) |
ee797053 | 639 | return 0; |
4f542b7a | 640 | return parse_commit_in_graph_one(r, r->objects->commit_graph, item); |
177722b3 DS |
641 | } |
642 | ||
dade47c0 | 643 | void load_commit_graph_info(struct repository *r, struct commit *item) |
e2838d85 DS |
644 | { |
645 | uint32_t pos; | |
dade47c0 | 646 | if (!prepare_commit_graph(r)) |
e2838d85 | 647 | return; |
dade47c0 JT |
648 | if (find_commit_in_graph(item, r->objects->commit_graph, &pos)) |
649 | fill_commit_graph_info(item, r->objects->commit_graph, pos); | |
e2838d85 DS |
650 | } |
651 | ||
4f542b7a SB |
652 | static struct tree *load_tree_for_commit(struct repository *r, |
653 | struct commit_graph *g, | |
654 | struct commit *c) | |
7b8a21db DS |
655 | { |
656 | struct object_id oid; | |
d4f4d60f DS |
657 | const unsigned char *commit_data; |
658 | ||
659 | while (c->graph_pos < g->num_commits_in_base) | |
660 | g = g->base_graph; | |
661 | ||
662 | commit_data = g->chunk_commit_data + | |
663 | GRAPH_DATA_WIDTH * (c->graph_pos - g->num_commits_in_base); | |
7b8a21db DS |
664 | |
665 | hashcpy(oid.hash, commit_data); | |
4f542b7a | 666 | c->maybe_tree = lookup_tree(r, &oid); |
7b8a21db DS |
667 | |
668 | return c->maybe_tree; | |
669 | } | |
670 | ||
4f542b7a SB |
671 | static struct tree *get_commit_tree_in_graph_one(struct repository *r, |
672 | struct commit_graph *g, | |
0cbef8f8 | 673 | const struct commit *c) |
7b8a21db DS |
674 | { |
675 | if (c->maybe_tree) | |
676 | return c->maybe_tree; | |
677 | if (c->graph_pos == COMMIT_NOT_FROM_GRAPH) | |
0cbef8f8 DS |
678 | BUG("get_commit_tree_in_graph_one called from non-commit-graph commit"); |
679 | ||
4f542b7a | 680 | return load_tree_for_commit(r, g, (struct commit *)c); |
0cbef8f8 | 681 | } |
7b8a21db | 682 | |
dade47c0 | 683 | struct tree *get_commit_tree_in_graph(struct repository *r, const struct commit *c) |
0cbef8f8 | 684 | { |
4f542b7a | 685 | return get_commit_tree_in_graph_one(r, r->objects->commit_graph, c); |
7b8a21db DS |
686 | } |
687 | ||
c9905bea DS |
688 | struct packed_commit_list { |
689 | struct commit **list; | |
690 | int nr; | |
691 | int alloc; | |
692 | }; | |
693 | ||
694 | struct packed_oid_list { | |
695 | struct object_id *list; | |
696 | int nr; | |
697 | int alloc; | |
698 | }; | |
699 | ||
700 | struct write_commit_graph_context { | |
701 | struct repository *r; | |
702 | const char *obj_dir; | |
703 | char *graph_name; | |
704 | struct packed_oid_list oids; | |
705 | struct packed_commit_list commits; | |
706 | int num_extra_edges; | |
707 | unsigned long approx_nr_objects; | |
708 | struct progress *progress; | |
709 | int progress_done; | |
710 | uint64_t progress_cnt; | |
711 | unsigned append:1, | |
712 | report_progress:1; | |
713 | }; | |
714 | ||
08fd81c9 | 715 | static void write_graph_chunk_fanout(struct hashfile *f, |
c9905bea | 716 | struct write_commit_graph_context *ctx) |
08fd81c9 DS |
717 | { |
718 | int i, count = 0; | |
c9905bea | 719 | struct commit **list = ctx->commits.list; |
08fd81c9 DS |
720 | |
721 | /* | |
722 | * Write the first-level table (the list is sorted, | |
723 | * but we use a 256-entry lookup to be able to avoid | |
724 | * having to do eight extra binary search iterations). | |
725 | */ | |
726 | for (i = 0; i < 256; i++) { | |
c9905bea | 727 | while (count < ctx->commits.nr) { |
08fd81c9 DS |
728 | if ((*list)->object.oid.hash[0] != i) |
729 | break; | |
c9905bea | 730 | display_progress(ctx->progress, ++ctx->progress_cnt); |
08fd81c9 DS |
731 | count++; |
732 | list++; | |
733 | } | |
734 | ||
735 | hashwrite_be32(f, count); | |
736 | } | |
737 | } | |
738 | ||
739 | static void write_graph_chunk_oids(struct hashfile *f, int hash_len, | |
c9905bea | 740 | struct write_commit_graph_context *ctx) |
08fd81c9 | 741 | { |
c9905bea | 742 | struct commit **list = ctx->commits.list; |
08fd81c9 | 743 | int count; |
c9905bea DS |
744 | for (count = 0; count < ctx->commits.nr; count++, list++) { |
745 | display_progress(ctx->progress, ++ctx->progress_cnt); | |
08fd81c9 | 746 | hashwrite(f, (*list)->object.oid.hash, (int)hash_len); |
53035c4f | 747 | } |
08fd81c9 DS |
748 | } |
749 | ||
750 | static const unsigned char *commit_to_sha1(size_t index, void *table) | |
751 | { | |
752 | struct commit **commits = table; | |
753 | return commits[index]->object.oid.hash; | |
754 | } | |
755 | ||
756 | static void write_graph_chunk_data(struct hashfile *f, int hash_len, | |
c9905bea | 757 | struct write_commit_graph_context *ctx) |
08fd81c9 | 758 | { |
c9905bea DS |
759 | struct commit **list = ctx->commits.list; |
760 | struct commit **last = ctx->commits.list + ctx->commits.nr; | |
08fd81c9 DS |
761 | uint32_t num_extra_edges = 0; |
762 | ||
763 | while (list < last) { | |
764 | struct commit_list *parent; | |
765 | int edge_value; | |
766 | uint32_t packedDate[2]; | |
c9905bea | 767 | display_progress(ctx->progress, ++ctx->progress_cnt); |
08fd81c9 | 768 | |
43d35618 | 769 | parse_commit_no_graph(*list); |
2e27bd77 | 770 | hashwrite(f, get_commit_tree_oid(*list)->hash, hash_len); |
08fd81c9 DS |
771 | |
772 | parent = (*list)->parents; | |
773 | ||
774 | if (!parent) | |
775 | edge_value = GRAPH_PARENT_NONE; | |
776 | else { | |
777 | edge_value = sha1_pos(parent->item->object.oid.hash, | |
c9905bea DS |
778 | ctx->commits.list, |
779 | ctx->commits.nr, | |
08fd81c9 DS |
780 | commit_to_sha1); |
781 | ||
782 | if (edge_value < 0) | |
cce99cd8 DS |
783 | BUG("missing parent %s for commit %s", |
784 | oid_to_hex(&parent->item->object.oid), | |
785 | oid_to_hex(&(*list)->object.oid)); | |
08fd81c9 DS |
786 | } |
787 | ||
788 | hashwrite_be32(f, edge_value); | |
789 | ||
790 | if (parent) | |
791 | parent = parent->next; | |
792 | ||
793 | if (!parent) | |
794 | edge_value = GRAPH_PARENT_NONE; | |
795 | else if (parent->next) | |
5af7417b | 796 | edge_value = GRAPH_EXTRA_EDGES_NEEDED | num_extra_edges; |
08fd81c9 DS |
797 | else { |
798 | edge_value = sha1_pos(parent->item->object.oid.hash, | |
c9905bea DS |
799 | ctx->commits.list, |
800 | ctx->commits.nr, | |
08fd81c9 DS |
801 | commit_to_sha1); |
802 | if (edge_value < 0) | |
cce99cd8 DS |
803 | BUG("missing parent %s for commit %s", |
804 | oid_to_hex(&parent->item->object.oid), | |
805 | oid_to_hex(&(*list)->object.oid)); | |
08fd81c9 DS |
806 | } |
807 | ||
808 | hashwrite_be32(f, edge_value); | |
809 | ||
5af7417b | 810 | if (edge_value & GRAPH_EXTRA_EDGES_NEEDED) { |
08fd81c9 DS |
811 | do { |
812 | num_extra_edges++; | |
813 | parent = parent->next; | |
814 | } while (parent); | |
815 | } | |
816 | ||
817 | if (sizeof((*list)->date) > 4) | |
818 | packedDate[0] = htonl(((*list)->date >> 32) & 0x3); | |
819 | else | |
820 | packedDate[0] = 0; | |
821 | ||
3258c663 DS |
822 | packedDate[0] |= htonl((*list)->generation << 2); |
823 | ||
08fd81c9 DS |
824 | packedDate[1] = htonl((*list)->date); |
825 | hashwrite(f, packedDate, 8); | |
826 | ||
827 | list++; | |
828 | } | |
829 | } | |
830 | ||
5af7417b | 831 | static void write_graph_chunk_extra_edges(struct hashfile *f, |
c9905bea | 832 | struct write_commit_graph_context *ctx) |
08fd81c9 | 833 | { |
c9905bea DS |
834 | struct commit **list = ctx->commits.list; |
835 | struct commit **last = ctx->commits.list + ctx->commits.nr; | |
08fd81c9 DS |
836 | struct commit_list *parent; |
837 | ||
838 | while (list < last) { | |
839 | int num_parents = 0; | |
53035c4f | 840 | |
c9905bea | 841 | display_progress(ctx->progress, ++ctx->progress_cnt); |
53035c4f | 842 | |
08fd81c9 DS |
843 | for (parent = (*list)->parents; num_parents < 3 && parent; |
844 | parent = parent->next) | |
845 | num_parents++; | |
846 | ||
847 | if (num_parents <= 2) { | |
848 | list++; | |
849 | continue; | |
850 | } | |
851 | ||
852 | /* Since num_parents > 2, this initializer is safe. */ | |
853 | for (parent = (*list)->parents->next; parent; parent = parent->next) { | |
854 | int edge_value = sha1_pos(parent->item->object.oid.hash, | |
c9905bea DS |
855 | ctx->commits.list, |
856 | ctx->commits.nr, | |
08fd81c9 DS |
857 | commit_to_sha1); |
858 | ||
859 | if (edge_value < 0) | |
cce99cd8 DS |
860 | BUG("missing parent %s for commit %s", |
861 | oid_to_hex(&parent->item->object.oid), | |
862 | oid_to_hex(&(*list)->object.oid)); | |
08fd81c9 DS |
863 | else if (!parent->next) |
864 | edge_value |= GRAPH_LAST_EDGE; | |
865 | ||
866 | hashwrite_be32(f, edge_value); | |
867 | } | |
868 | ||
869 | list++; | |
870 | } | |
871 | } | |
872 | ||
3cbc6ed3 | 873 | static int oid_compare(const void *_a, const void *_b) |
08fd81c9 DS |
874 | { |
875 | const struct object_id *a = (const struct object_id *)_a; | |
876 | const struct object_id *b = (const struct object_id *)_b; | |
877 | return oidcmp(a, b); | |
878 | } | |
879 | ||
08fd81c9 DS |
880 | static int add_packed_commits(const struct object_id *oid, |
881 | struct packed_git *pack, | |
882 | uint32_t pos, | |
883 | void *data) | |
884 | { | |
c9905bea | 885 | struct write_commit_graph_context *ctx = (struct write_commit_graph_context*)data; |
08fd81c9 DS |
886 | enum object_type type; |
887 | off_t offset = nth_packed_object_offset(pack, pos); | |
888 | struct object_info oi = OBJECT_INFO_INIT; | |
889 | ||
c9905bea DS |
890 | if (ctx->progress) |
891 | display_progress(ctx->progress, ++ctx->progress_done); | |
7b0f2292 | 892 | |
08fd81c9 | 893 | oi.typep = &type; |
c9905bea | 894 | if (packed_object_info(ctx->r, pack, offset, &oi) < 0) |
4f5b532d | 895 | die(_("unable to get type of object %s"), oid_to_hex(oid)); |
08fd81c9 DS |
896 | |
897 | if (type != OBJ_COMMIT) | |
898 | return 0; | |
899 | ||
c9905bea DS |
900 | ALLOC_GROW(ctx->oids.list, ctx->oids.nr + 1, ctx->oids.alloc); |
901 | oidcpy(&(ctx->oids.list[ctx->oids.nr]), oid); | |
902 | ctx->oids.nr++; | |
08fd81c9 DS |
903 | |
904 | return 0; | |
905 | } | |
906 | ||
c9905bea | 907 | static void add_missing_parents(struct write_commit_graph_context *ctx, struct commit *commit) |
4f2542b4 DS |
908 | { |
909 | struct commit_list *parent; | |
910 | for (parent = commit->parents; parent; parent = parent->next) { | |
911 | if (!(parent->item->object.flags & UNINTERESTING)) { | |
c9905bea DS |
912 | ALLOC_GROW(ctx->oids.list, ctx->oids.nr + 1, ctx->oids.alloc); |
913 | oidcpy(&ctx->oids.list[ctx->oids.nr], &(parent->item->object.oid)); | |
914 | ctx->oids.nr++; | |
4f2542b4 DS |
915 | parent->item->object.flags |= UNINTERESTING; |
916 | } | |
917 | } | |
918 | } | |
919 | ||
c9905bea | 920 | static void close_reachable(struct write_commit_graph_context *ctx) |
4f2542b4 | 921 | { |
49bbc57a | 922 | int i; |
4f2542b4 DS |
923 | struct commit *commit; |
924 | ||
c9905bea DS |
925 | if (ctx->report_progress) |
926 | ctx->progress = start_delayed_progress( | |
927 | _("Loading known commits in commit graph"), | |
928 | ctx->oids.nr); | |
929 | for (i = 0; i < ctx->oids.nr; i++) { | |
930 | display_progress(ctx->progress, i + 1); | |
931 | commit = lookup_commit(ctx->r, &ctx->oids.list[i]); | |
4f2542b4 DS |
932 | if (commit) |
933 | commit->object.flags |= UNINTERESTING; | |
934 | } | |
c9905bea | 935 | stop_progress(&ctx->progress); |
4f2542b4 DS |
936 | |
937 | /* | |
c9905bea | 938 | * As this loop runs, ctx->oids.nr may grow, but not more |
4f2542b4 DS |
939 | * than the number of missing commits in the reachable |
940 | * closure. | |
941 | */ | |
c9905bea DS |
942 | if (ctx->report_progress) |
943 | ctx->progress = start_delayed_progress( | |
944 | _("Expanding reachable commits in commit graph"), | |
945 | ctx->oids.nr); | |
946 | for (i = 0; i < ctx->oids.nr; i++) { | |
947 | display_progress(ctx->progress, i + 1); | |
948 | commit = lookup_commit(ctx->r, &ctx->oids.list[i]); | |
4f2542b4 | 949 | |
43d35618 | 950 | if (commit && !parse_commit_no_graph(commit)) |
c9905bea | 951 | add_missing_parents(ctx, commit); |
4f2542b4 | 952 | } |
c9905bea | 953 | stop_progress(&ctx->progress); |
4f2542b4 | 954 | |
c9905bea DS |
955 | if (ctx->report_progress) |
956 | ctx->progress = start_delayed_progress( | |
957 | _("Clearing commit marks in commit graph"), | |
958 | ctx->oids.nr); | |
959 | for (i = 0; i < ctx->oids.nr; i++) { | |
960 | display_progress(ctx->progress, i + 1); | |
961 | commit = lookup_commit(ctx->r, &ctx->oids.list[i]); | |
4f2542b4 DS |
962 | |
963 | if (commit) | |
964 | commit->object.flags &= ~UNINTERESTING; | |
965 | } | |
c9905bea | 966 | stop_progress(&ctx->progress); |
4f2542b4 DS |
967 | } |
968 | ||
c9905bea | 969 | static void compute_generation_numbers(struct write_commit_graph_context *ctx) |
3258c663 DS |
970 | { |
971 | int i; | |
972 | struct commit_list *list = NULL; | |
973 | ||
c9905bea DS |
974 | if (ctx->report_progress) |
975 | ctx->progress = start_progress( | |
976 | _("Computing commit graph generation numbers"), | |
977 | ctx->commits.nr); | |
978 | for (i = 0; i < ctx->commits.nr; i++) { | |
979 | display_progress(ctx->progress, i + 1); | |
980 | if (ctx->commits.list[i]->generation != GENERATION_NUMBER_INFINITY && | |
981 | ctx->commits.list[i]->generation != GENERATION_NUMBER_ZERO) | |
3258c663 DS |
982 | continue; |
983 | ||
c9905bea | 984 | commit_list_insert(ctx->commits.list[i], &list); |
3258c663 DS |
985 | while (list) { |
986 | struct commit *current = list->item; | |
987 | struct commit_list *parent; | |
988 | int all_parents_computed = 1; | |
989 | uint32_t max_generation = 0; | |
990 | ||
991 | for (parent = current->parents; parent; parent = parent->next) { | |
992 | if (parent->item->generation == GENERATION_NUMBER_INFINITY || | |
993 | parent->item->generation == GENERATION_NUMBER_ZERO) { | |
994 | all_parents_computed = 0; | |
995 | commit_list_insert(parent->item, &list); | |
996 | break; | |
997 | } else if (parent->item->generation > max_generation) { | |
998 | max_generation = parent->item->generation; | |
999 | } | |
1000 | } | |
1001 | ||
1002 | if (all_parents_computed) { | |
1003 | current->generation = max_generation + 1; | |
1004 | pop_commit(&list); | |
1005 | ||
1006 | if (current->generation > GENERATION_NUMBER_MAX) | |
1007 | current->generation = GENERATION_NUMBER_MAX; | |
1008 | } | |
1009 | } | |
1010 | } | |
c9905bea | 1011 | stop_progress(&ctx->progress); |
3258c663 DS |
1012 | } |
1013 | ||
59fb8770 DS |
1014 | static int add_ref_to_list(const char *refname, |
1015 | const struct object_id *oid, | |
1016 | int flags, void *cb_data) | |
1017 | { | |
1018 | struct string_list *list = (struct string_list *)cb_data; | |
1019 | ||
1020 | string_list_append(list, oid_to_hex(oid)); | |
1021 | return 0; | |
1022 | } | |
1023 | ||
5af80394 | 1024 | int write_commit_graph_reachable(const char *obj_dir, unsigned int flags) |
59fb8770 | 1025 | { |
f4dbdfc4 | 1026 | struct string_list list = STRING_LIST_INIT_DUP; |
e103f727 | 1027 | int result; |
59fb8770 | 1028 | |
59fb8770 | 1029 | for_each_ref(add_ref_to_list, &list); |
e103f727 | 1030 | result = write_commit_graph(obj_dir, NULL, &list, |
5af80394 | 1031 | flags); |
f4dbdfc4 DS |
1032 | |
1033 | string_list_clear(&list, 0); | |
e103f727 | 1034 | return result; |
59fb8770 DS |
1035 | } |
1036 | ||
ef5b83f2 DS |
1037 | static int fill_oids_from_packs(struct write_commit_graph_context *ctx, |
1038 | struct string_list *pack_indexes) | |
1039 | { | |
1040 | uint32_t i; | |
1041 | struct strbuf progress_title = STRBUF_INIT; | |
1042 | struct strbuf packname = STRBUF_INIT; | |
1043 | int dirlen; | |
1044 | ||
1045 | strbuf_addf(&packname, "%s/pack/", ctx->obj_dir); | |
1046 | dirlen = packname.len; | |
1047 | if (ctx->report_progress) { | |
1048 | strbuf_addf(&progress_title, | |
1049 | Q_("Finding commits for commit graph in %d pack", | |
1050 | "Finding commits for commit graph in %d packs", | |
1051 | pack_indexes->nr), | |
1052 | pack_indexes->nr); | |
1053 | ctx->progress = start_delayed_progress(progress_title.buf, 0); | |
1054 | ctx->progress_done = 0; | |
1055 | } | |
1056 | for (i = 0; i < pack_indexes->nr; i++) { | |
1057 | struct packed_git *p; | |
1058 | strbuf_setlen(&packname, dirlen); | |
1059 | strbuf_addstr(&packname, pack_indexes->items[i].string); | |
1060 | p = add_packed_git(packname.buf, packname.len, 1); | |
1061 | if (!p) { | |
1062 | error(_("error adding pack %s"), packname.buf); | |
1063 | return -1; | |
1064 | } | |
1065 | if (open_pack_index(p)) { | |
1066 | error(_("error opening index for %s"), packname.buf); | |
1067 | return -1; | |
1068 | } | |
1069 | for_each_object_in_pack(p, add_packed_commits, ctx, | |
1070 | FOR_EACH_OBJECT_PACK_ORDER); | |
1071 | close_pack(p); | |
1072 | free(p); | |
1073 | } | |
1074 | ||
1075 | stop_progress(&ctx->progress); | |
1076 | strbuf_reset(&progress_title); | |
1077 | strbuf_release(&packname); | |
1078 | ||
1079 | return 0; | |
1080 | } | |
1081 | ||
4c9efe85 DS |
1082 | static void fill_oids_from_commit_hex(struct write_commit_graph_context *ctx, |
1083 | struct string_list *commit_hex) | |
1084 | { | |
1085 | uint32_t i; | |
1086 | struct strbuf progress_title = STRBUF_INIT; | |
1087 | ||
1088 | if (ctx->report_progress) { | |
1089 | strbuf_addf(&progress_title, | |
1090 | Q_("Finding commits for commit graph from %d ref", | |
1091 | "Finding commits for commit graph from %d refs", | |
1092 | commit_hex->nr), | |
1093 | commit_hex->nr); | |
1094 | ctx->progress = start_delayed_progress( | |
1095 | progress_title.buf, | |
1096 | commit_hex->nr); | |
1097 | } | |
1098 | for (i = 0; i < commit_hex->nr; i++) { | |
1099 | const char *end; | |
1100 | struct object_id oid; | |
1101 | struct commit *result; | |
1102 | ||
1103 | display_progress(ctx->progress, i + 1); | |
1104 | if (commit_hex->items[i].string && | |
1105 | parse_oid_hex(commit_hex->items[i].string, &oid, &end)) | |
1106 | continue; | |
1107 | ||
1108 | result = lookup_commit_reference_gently(ctx->r, &oid, 1); | |
1109 | ||
1110 | if (result) { | |
1111 | ALLOC_GROW(ctx->oids.list, ctx->oids.nr + 1, ctx->oids.alloc); | |
1112 | oidcpy(&ctx->oids.list[ctx->oids.nr], &(result->object.oid)); | |
1113 | ctx->oids.nr++; | |
1114 | } | |
1115 | } | |
1116 | stop_progress(&ctx->progress); | |
1117 | strbuf_release(&progress_title); | |
1118 | } | |
1119 | ||
b2c83060 DS |
1120 | static void fill_oids_from_all_packs(struct write_commit_graph_context *ctx) |
1121 | { | |
1122 | if (ctx->report_progress) | |
1123 | ctx->progress = start_delayed_progress( | |
1124 | _("Finding commits for commit graph among packed objects"), | |
1125 | ctx->approx_nr_objects); | |
1126 | for_each_packed_object(add_packed_commits, ctx, | |
1127 | FOR_EACH_OBJECT_PACK_ORDER); | |
1128 | if (ctx->progress_done < ctx->approx_nr_objects) | |
1129 | display_progress(ctx->progress, ctx->approx_nr_objects); | |
1130 | stop_progress(&ctx->progress); | |
1131 | } | |
1132 | ||
014e3440 DS |
1133 | static uint32_t count_distinct_commits(struct write_commit_graph_context *ctx) |
1134 | { | |
1135 | uint32_t i, count_distinct = 1; | |
1136 | ||
1137 | if (ctx->report_progress) | |
1138 | ctx->progress = start_delayed_progress( | |
1139 | _("Counting distinct commits in commit graph"), | |
1140 | ctx->oids.nr); | |
1141 | display_progress(ctx->progress, 0); /* TODO: Measure QSORT() progress */ | |
3cbc6ed3 | 1142 | QSORT(ctx->oids.list, ctx->oids.nr, oid_compare); |
014e3440 DS |
1143 | |
1144 | for (i = 1; i < ctx->oids.nr; i++) { | |
1145 | display_progress(ctx->progress, i + 1); | |
1146 | if (!oideq(&ctx->oids.list[i - 1], &ctx->oids.list[i])) | |
1147 | count_distinct++; | |
1148 | } | |
1149 | stop_progress(&ctx->progress); | |
1150 | ||
1151 | return count_distinct; | |
1152 | } | |
1153 | ||
f998d542 DS |
1154 | static void copy_oids_to_commits(struct write_commit_graph_context *ctx) |
1155 | { | |
1156 | uint32_t i; | |
1157 | struct commit_list *parent; | |
1158 | ||
1159 | ctx->num_extra_edges = 0; | |
1160 | if (ctx->report_progress) | |
1161 | ctx->progress = start_delayed_progress( | |
1162 | _("Finding extra edges in commit graph"), | |
1163 | ctx->oids.nr); | |
1164 | for (i = 0; i < ctx->oids.nr; i++) { | |
1165 | int num_parents = 0; | |
1166 | display_progress(ctx->progress, i + 1); | |
1167 | if (i > 0 && oideq(&ctx->oids.list[i - 1], &ctx->oids.list[i])) | |
1168 | continue; | |
1169 | ||
1170 | ctx->commits.list[ctx->commits.nr] = lookup_commit(ctx->r, &ctx->oids.list[i]); | |
1171 | parse_commit_no_graph(ctx->commits.list[ctx->commits.nr]); | |
1172 | ||
1173 | for (parent = ctx->commits.list[ctx->commits.nr]->parents; | |
1174 | parent; parent = parent->next) | |
1175 | num_parents++; | |
1176 | ||
1177 | if (num_parents > 2) | |
1178 | ctx->num_extra_edges += num_parents - 1; | |
1179 | ||
1180 | ctx->commits.nr++; | |
1181 | } | |
1182 | stop_progress(&ctx->progress); | |
1183 | } | |
1184 | ||
238def57 | 1185 | static int write_commit_graph_file(struct write_commit_graph_context *ctx) |
08fd81c9 | 1186 | { |
238def57 | 1187 | uint32_t i; |
08fd81c9 | 1188 | struct hashfile *f; |
08fd81c9 DS |
1189 | struct lock_file lk = LOCK_INIT; |
1190 | uint32_t chunk_ids[5]; | |
1191 | uint64_t chunk_offsets[5]; | |
c1665998 | 1192 | const unsigned hashsz = the_hash_algo->rawsz; |
28944739 | 1193 | struct strbuf progress_title = STRBUF_INIT; |
238def57 DS |
1194 | int num_chunks = ctx->num_extra_edges ? 4 : 3; |
1195 | ||
1196 | ctx->graph_name = get_commit_graph_filename(ctx->obj_dir); | |
1197 | if (safe_create_leading_directories(ctx->graph_name)) { | |
1198 | UNLEAK(ctx->graph_name); | |
1199 | error(_("unable to create leading directories of %s"), | |
1200 | ctx->graph_name); | |
1201 | return -1; | |
1202 | } | |
1203 | ||
1204 | hold_lock_file_for_update(&lk, ctx->graph_name, LOCK_DIE_ON_ERROR); | |
1205 | f = hashfd(lk.tempfile->fd, lk.tempfile->filename.buf); | |
1206 | ||
1207 | hashwrite_be32(f, GRAPH_SIGNATURE); | |
1208 | ||
1209 | hashwrite_u8(f, GRAPH_VERSION); | |
1210 | hashwrite_u8(f, oid_version()); | |
1211 | hashwrite_u8(f, num_chunks); | |
1212 | hashwrite_u8(f, 0); /* unused padding byte */ | |
1213 | ||
1214 | chunk_ids[0] = GRAPH_CHUNKID_OIDFANOUT; | |
1215 | chunk_ids[1] = GRAPH_CHUNKID_OIDLOOKUP; | |
1216 | chunk_ids[2] = GRAPH_CHUNKID_DATA; | |
1217 | if (ctx->num_extra_edges) | |
1218 | chunk_ids[3] = GRAPH_CHUNKID_EXTRAEDGES; | |
1219 | else | |
1220 | chunk_ids[3] = 0; | |
1221 | chunk_ids[4] = 0; | |
1222 | ||
1223 | chunk_offsets[0] = 8 + (num_chunks + 1) * GRAPH_CHUNKLOOKUP_WIDTH; | |
1224 | chunk_offsets[1] = chunk_offsets[0] + GRAPH_FANOUT_SIZE; | |
1225 | chunk_offsets[2] = chunk_offsets[1] + hashsz * ctx->commits.nr; | |
1226 | chunk_offsets[3] = chunk_offsets[2] + (hashsz + 16) * ctx->commits.nr; | |
1227 | chunk_offsets[4] = chunk_offsets[3] + 4 * ctx->num_extra_edges; | |
1228 | ||
1229 | for (i = 0; i <= num_chunks; i++) { | |
1230 | uint32_t chunk_write[3]; | |
1231 | ||
1232 | chunk_write[0] = htonl(chunk_ids[i]); | |
1233 | chunk_write[1] = htonl(chunk_offsets[i] >> 32); | |
1234 | chunk_write[2] = htonl(chunk_offsets[i] & 0xffffffff); | |
1235 | hashwrite(f, chunk_write, 12); | |
1236 | } | |
1237 | ||
1238 | if (ctx->report_progress) { | |
1239 | strbuf_addf(&progress_title, | |
1240 | Q_("Writing out commit graph in %d pass", | |
1241 | "Writing out commit graph in %d passes", | |
1242 | num_chunks), | |
1243 | num_chunks); | |
1244 | ctx->progress = start_delayed_progress( | |
1245 | progress_title.buf, | |
1246 | num_chunks * ctx->commits.nr); | |
1247 | } | |
1248 | write_graph_chunk_fanout(f, ctx); | |
1249 | write_graph_chunk_oids(f, hashsz, ctx); | |
1250 | write_graph_chunk_data(f, hashsz, ctx); | |
1251 | if (ctx->num_extra_edges) | |
1252 | write_graph_chunk_extra_edges(f, ctx); | |
1253 | stop_progress(&ctx->progress); | |
1254 | strbuf_release(&progress_title); | |
1255 | ||
c3a3a964 | 1256 | close_commit_graph(ctx->r->objects); |
238def57 DS |
1257 | finalize_hashfile(f, NULL, CSUM_HASH_IN_STREAM | CSUM_FSYNC); |
1258 | commit_lock_file(&lk); | |
1259 | ||
1260 | return 0; | |
1261 | } | |
1262 | ||
1263 | int write_commit_graph(const char *obj_dir, | |
1264 | struct string_list *pack_indexes, | |
1265 | struct string_list *commit_hex, | |
1266 | unsigned int flags) | |
1267 | { | |
1268 | struct write_commit_graph_context *ctx; | |
1269 | uint32_t i, count_distinct = 0; | |
e103f727 | 1270 | int res = 0; |
08fd81c9 | 1271 | |
d6538246 | 1272 | if (!commit_graph_compatible(the_repository)) |
e103f727 | 1273 | return 0; |
d6538246 | 1274 | |
c9905bea DS |
1275 | ctx = xcalloc(1, sizeof(struct write_commit_graph_context)); |
1276 | ctx->r = the_repository; | |
1277 | ctx->obj_dir = obj_dir; | |
1278 | ctx->append = flags & COMMIT_GRAPH_APPEND ? 1 : 0; | |
1279 | ctx->report_progress = flags & COMMIT_GRAPH_PROGRESS ? 1 : 0; | |
1280 | ||
1281 | ctx->approx_nr_objects = approximate_object_count(); | |
1282 | ctx->oids.alloc = ctx->approx_nr_objects / 32; | |
1283 | ||
1284 | if (ctx->append) { | |
1285 | prepare_commit_graph_one(ctx->r, ctx->obj_dir); | |
1286 | if (ctx->r->objects->commit_graph) | |
1287 | ctx->oids.alloc += ctx->r->objects->commit_graph->num_commits; | |
7547b95b DS |
1288 | } |
1289 | ||
c9905bea DS |
1290 | if (ctx->oids.alloc < 1024) |
1291 | ctx->oids.alloc = 1024; | |
1292 | ALLOC_ARRAY(ctx->oids.list, ctx->oids.alloc); | |
1293 | ||
1294 | if (ctx->append && ctx->r->objects->commit_graph) { | |
1295 | struct commit_graph *g = ctx->r->objects->commit_graph; | |
1296 | for (i = 0; i < g->num_commits; i++) { | |
1297 | const unsigned char *hash = g->chunk_oid_lookup + g->hash_len * i; | |
1298 | hashcpy(ctx->oids.list[ctx->oids.nr++].hash, hash); | |
7547b95b DS |
1299 | } |
1300 | } | |
1301 | ||
049d51a2 | 1302 | if (pack_indexes) { |
ef5b83f2 DS |
1303 | if ((res = fill_oids_from_packs(ctx, pack_indexes))) |
1304 | goto cleanup; | |
3d5df01b DS |
1305 | } |
1306 | ||
4c9efe85 DS |
1307 | if (commit_hex) |
1308 | fill_oids_from_commit_hex(ctx, commit_hex); | |
3d5df01b | 1309 | |
b2c83060 DS |
1310 | if (!pack_indexes && !commit_hex) |
1311 | fill_oids_from_all_packs(ctx); | |
049d51a2 | 1312 | |
c9905bea | 1313 | close_reachable(ctx); |
08fd81c9 | 1314 | |
014e3440 | 1315 | count_distinct = count_distinct_commits(ctx); |
08fd81c9 | 1316 | |
e103f727 DS |
1317 | if (count_distinct >= GRAPH_EDGE_LAST_MASK) { |
1318 | error(_("the commit graph format cannot write %d commits"), count_distinct); | |
1319 | res = -1; | |
1320 | goto cleanup; | |
1321 | } | |
08fd81c9 | 1322 | |
c9905bea DS |
1323 | ctx->commits.alloc = count_distinct; |
1324 | ALLOC_ARRAY(ctx->commits.list, ctx->commits.alloc); | |
08fd81c9 | 1325 | |
f998d542 | 1326 | copy_oids_to_commits(ctx); |
08fd81c9 | 1327 | |
c9905bea | 1328 | if (ctx->commits.nr >= GRAPH_EDGE_LAST_MASK) { |
e103f727 DS |
1329 | error(_("too many commits to write graph")); |
1330 | res = -1; | |
1331 | goto cleanup; | |
1332 | } | |
08fd81c9 | 1333 | |
c9905bea | 1334 | compute_generation_numbers(ctx); |
08fd81c9 | 1335 | |
238def57 | 1336 | res = write_commit_graph_file(ctx); |
08fd81c9 | 1337 | |
e103f727 | 1338 | cleanup: |
238def57 | 1339 | free(ctx->graph_name); |
c9905bea DS |
1340 | free(ctx->commits.list); |
1341 | free(ctx->oids.list); | |
1342 | free(ctx); | |
e103f727 DS |
1343 | |
1344 | return res; | |
08fd81c9 | 1345 | } |
283e68c7 | 1346 | |
41df0e30 | 1347 | #define VERIFY_COMMIT_GRAPH_ERROR_HASH 2 |
283e68c7 DS |
1348 | static int verify_commit_graph_error; |
1349 | ||
1350 | static void graph_report(const char *fmt, ...) | |
1351 | { | |
1352 | va_list ap; | |
1353 | ||
1354 | verify_commit_graph_error = 1; | |
1355 | va_start(ap, fmt); | |
1356 | vfprintf(stderr, fmt, ap); | |
1357 | fprintf(stderr, "\n"); | |
1358 | va_end(ap); | |
1359 | } | |
1360 | ||
1373e547 DS |
1361 | #define GENERATION_ZERO_EXISTS 1 |
1362 | #define GENERATION_NUMBER_EXISTS 2 | |
1363 | ||
283e68c7 DS |
1364 | int verify_commit_graph(struct repository *r, struct commit_graph *g) |
1365 | { | |
9bda8467 | 1366 | uint32_t i, cur_fanout_pos = 0; |
41df0e30 | 1367 | struct object_id prev_oid, cur_oid, checksum; |
1373e547 | 1368 | int generation_zero = 0; |
41df0e30 DS |
1369 | struct hashfile *f; |
1370 | int devnull; | |
1f7f557f | 1371 | struct progress *progress = NULL; |
9bda8467 | 1372 | |
283e68c7 DS |
1373 | if (!g) { |
1374 | graph_report("no commit-graph file loaded"); | |
1375 | return 1; | |
1376 | } | |
1377 | ||
2ac138d5 | 1378 | verify_commit_graph_error = verify_commit_graph_lite(g); |
9bda8467 DS |
1379 | if (verify_commit_graph_error) |
1380 | return verify_commit_graph_error; | |
1381 | ||
41df0e30 DS |
1382 | devnull = open("/dev/null", O_WRONLY); |
1383 | f = hashfd(devnull, NULL); | |
1384 | hashwrite(f, g->data, g->data_len - g->hash_len); | |
1385 | finalize_hashfile(f, checksum.hash, CSUM_CLOSE); | |
67947c34 | 1386 | if (!hasheq(checksum.hash, g->data + g->data_len - g->hash_len)) { |
41df0e30 DS |
1387 | graph_report(_("the commit-graph file has incorrect checksum and is likely corrupt")); |
1388 | verify_commit_graph_error = VERIFY_COMMIT_GRAPH_ERROR_HASH; | |
1389 | } | |
1390 | ||
9bda8467 | 1391 | for (i = 0; i < g->num_commits; i++) { |
2e3c0737 DS |
1392 | struct commit *graph_commit; |
1393 | ||
9bda8467 DS |
1394 | hashcpy(cur_oid.hash, g->chunk_oid_lookup + g->hash_len * i); |
1395 | ||
1396 | if (i && oidcmp(&prev_oid, &cur_oid) >= 0) | |
93b4405f | 1397 | graph_report(_("commit-graph has incorrect OID order: %s then %s"), |
9bda8467 DS |
1398 | oid_to_hex(&prev_oid), |
1399 | oid_to_hex(&cur_oid)); | |
1400 | ||
1401 | oidcpy(&prev_oid, &cur_oid); | |
1402 | ||
1403 | while (cur_oid.hash[0] > cur_fanout_pos) { | |
1404 | uint32_t fanout_value = get_be32(g->chunk_oid_fanout + cur_fanout_pos); | |
1405 | ||
1406 | if (i != fanout_value) | |
93b4405f | 1407 | graph_report(_("commit-graph has incorrect fanout value: fanout[%d] = %u != %u"), |
9bda8467 DS |
1408 | cur_fanout_pos, fanout_value, i); |
1409 | cur_fanout_pos++; | |
1410 | } | |
2e3c0737 | 1411 | |
82952964 | 1412 | graph_commit = lookup_commit(r, &cur_oid); |
4f542b7a | 1413 | if (!parse_commit_in_graph_one(r, g, graph_commit)) |
93b4405f | 1414 | graph_report(_("failed to parse commit %s from commit-graph"), |
2e3c0737 | 1415 | oid_to_hex(&cur_oid)); |
9bda8467 DS |
1416 | } |
1417 | ||
1418 | while (cur_fanout_pos < 256) { | |
1419 | uint32_t fanout_value = get_be32(g->chunk_oid_fanout + cur_fanout_pos); | |
1420 | ||
1421 | if (g->num_commits != fanout_value) | |
93b4405f | 1422 | graph_report(_("commit-graph has incorrect fanout value: fanout[%d] = %u != %u"), |
9bda8467 DS |
1423 | cur_fanout_pos, fanout_value, i); |
1424 | ||
1425 | cur_fanout_pos++; | |
1426 | } | |
1427 | ||
41df0e30 | 1428 | if (verify_commit_graph_error & ~VERIFY_COMMIT_GRAPH_ERROR_HASH) |
96af91d4 DS |
1429 | return verify_commit_graph_error; |
1430 | ||
1f7f557f ÆAB |
1431 | progress = start_progress(_("Verifying commits in commit graph"), |
1432 | g->num_commits); | |
96af91d4 | 1433 | for (i = 0; i < g->num_commits; i++) { |
2e3c0737 | 1434 | struct commit *graph_commit, *odb_commit; |
53614b13 | 1435 | struct commit_list *graph_parents, *odb_parents; |
1373e547 | 1436 | uint32_t max_generation = 0; |
96af91d4 | 1437 | |
1f7f557f | 1438 | display_progress(progress, i + 1); |
96af91d4 DS |
1439 | hashcpy(cur_oid.hash, g->chunk_oid_lookup + g->hash_len * i); |
1440 | ||
82952964 | 1441 | graph_commit = lookup_commit(r, &cur_oid); |
96af91d4 DS |
1442 | odb_commit = (struct commit *)create_object(r, cur_oid.hash, alloc_commit_node(r)); |
1443 | if (parse_commit_internal(odb_commit, 0, 0)) { | |
93b4405f | 1444 | graph_report(_("failed to parse commit %s from object database for commit-graph"), |
96af91d4 DS |
1445 | oid_to_hex(&cur_oid)); |
1446 | continue; | |
1447 | } | |
2e3c0737 | 1448 | |
4f542b7a | 1449 | if (!oideq(&get_commit_tree_in_graph_one(r, g, graph_commit)->object.oid, |
2e3c0737 | 1450 | get_commit_tree_oid(odb_commit))) |
93b4405f | 1451 | graph_report(_("root tree OID for commit %s in commit-graph is %s != %s"), |
2e3c0737 DS |
1452 | oid_to_hex(&cur_oid), |
1453 | oid_to_hex(get_commit_tree_oid(graph_commit)), | |
1454 | oid_to_hex(get_commit_tree_oid(odb_commit))); | |
53614b13 DS |
1455 | |
1456 | graph_parents = graph_commit->parents; | |
1457 | odb_parents = odb_commit->parents; | |
1458 | ||
1459 | while (graph_parents) { | |
1460 | if (odb_parents == NULL) { | |
93b4405f | 1461 | graph_report(_("commit-graph parent list for commit %s is too long"), |
53614b13 DS |
1462 | oid_to_hex(&cur_oid)); |
1463 | break; | |
1464 | } | |
1465 | ||
9001dc2a | 1466 | if (!oideq(&graph_parents->item->object.oid, &odb_parents->item->object.oid)) |
93b4405f | 1467 | graph_report(_("commit-graph parent for %s is %s != %s"), |
53614b13 DS |
1468 | oid_to_hex(&cur_oid), |
1469 | oid_to_hex(&graph_parents->item->object.oid), | |
1470 | oid_to_hex(&odb_parents->item->object.oid)); | |
1471 | ||
1373e547 DS |
1472 | if (graph_parents->item->generation > max_generation) |
1473 | max_generation = graph_parents->item->generation; | |
1474 | ||
53614b13 DS |
1475 | graph_parents = graph_parents->next; |
1476 | odb_parents = odb_parents->next; | |
1477 | } | |
1478 | ||
1479 | if (odb_parents != NULL) | |
93b4405f | 1480 | graph_report(_("commit-graph parent list for commit %s terminates early"), |
53614b13 | 1481 | oid_to_hex(&cur_oid)); |
1373e547 DS |
1482 | |
1483 | if (!graph_commit->generation) { | |
1484 | if (generation_zero == GENERATION_NUMBER_EXISTS) | |
93b4405f | 1485 | graph_report(_("commit-graph has generation number zero for commit %s, but non-zero elsewhere"), |
1373e547 DS |
1486 | oid_to_hex(&cur_oid)); |
1487 | generation_zero = GENERATION_ZERO_EXISTS; | |
1488 | } else if (generation_zero == GENERATION_ZERO_EXISTS) | |
93b4405f | 1489 | graph_report(_("commit-graph has non-zero generation number for commit %s, but zero elsewhere"), |
1373e547 DS |
1490 | oid_to_hex(&cur_oid)); |
1491 | ||
1492 | if (generation_zero == GENERATION_ZERO_EXISTS) | |
1493 | continue; | |
1494 | ||
1495 | /* | |
1496 | * If one of our parents has generation GENERATION_NUMBER_MAX, then | |
1497 | * our generation is also GENERATION_NUMBER_MAX. Decrement to avoid | |
1498 | * extra logic in the following condition. | |
1499 | */ | |
1500 | if (max_generation == GENERATION_NUMBER_MAX) | |
1501 | max_generation--; | |
1502 | ||
1503 | if (graph_commit->generation != max_generation + 1) | |
93b4405f | 1504 | graph_report(_("commit-graph generation for commit %s is %u != %u"), |
1373e547 DS |
1505 | oid_to_hex(&cur_oid), |
1506 | graph_commit->generation, | |
1507 | max_generation + 1); | |
88968ebf DS |
1508 | |
1509 | if (graph_commit->date != odb_commit->date) | |
93b4405f | 1510 | graph_report(_("commit date for commit %s in commit-graph is %"PRItime" != %"PRItime), |
88968ebf DS |
1511 | oid_to_hex(&cur_oid), |
1512 | graph_commit->date, | |
1513 | odb_commit->date); | |
96af91d4 | 1514 | } |
1f7f557f | 1515 | stop_progress(&progress); |
96af91d4 | 1516 | |
283e68c7 DS |
1517 | return verify_commit_graph_error; |
1518 | } | |
c3756d5b JT |
1519 | |
1520 | void free_commit_graph(struct commit_graph *g) | |
1521 | { | |
1522 | if (!g) | |
1523 | return; | |
1524 | if (g->graph_fd >= 0) { | |
1525 | munmap((void *)g->data, g->data_len); | |
1526 | g->data = NULL; | |
1527 | close(g->graph_fd); | |
1528 | } | |
1529 | free(g); | |
1530 | } |