From 48f3f8cf37043f69e9834d38e2439abfde280964 Mon Sep 17 00:00:00 2001 From: Taylor Blau Date: Wed, 12 Jul 2023 19:37:54 -0400 Subject: commit-graph.c: prevent overflow in `write_commit_graph_file()` When writing a commit-graph, we use the chunk-format API to write out each individual chunk of the commit-graph. Each chunk of the commit-graph is tracked via a call to `add_chunk()`, along with the expected size of that chunk. Similar to an earlier commit which handled the identical issue in the MIDX machinery, guard against overflow when dealing with a commit-graph with a large number of entries to avoid corrupting the contents of the commit-graph itself. Signed-off-by: Taylor Blau Signed-off-by: Junio C Hamano --- commit-graph.c | 20 ++++++++++---------- 1 file changed, 10 insertions(+), 10 deletions(-) (limited to 'commit-graph.c') diff --git a/commit-graph.c b/commit-graph.c index 843bdb458d..86c76bd2f8 100644 --- a/commit-graph.c +++ b/commit-graph.c @@ -1953,35 +1953,35 @@ static int write_commit_graph_file(struct write_commit_graph_context *ctx) add_chunk(cf, GRAPH_CHUNKID_OIDFANOUT, GRAPH_FANOUT_SIZE, write_graph_chunk_fanout); - add_chunk(cf, GRAPH_CHUNKID_OIDLOOKUP, hashsz * ctx->commits.nr, + add_chunk(cf, GRAPH_CHUNKID_OIDLOOKUP, st_mult(hashsz, ctx->commits.nr), write_graph_chunk_oids); - add_chunk(cf, GRAPH_CHUNKID_DATA, (hashsz + 16) * ctx->commits.nr, + add_chunk(cf, GRAPH_CHUNKID_DATA, st_mult(hashsz + 16, ctx->commits.nr), write_graph_chunk_data); if (ctx->write_generation_data) add_chunk(cf, GRAPH_CHUNKID_GENERATION_DATA, - sizeof(uint32_t) * ctx->commits.nr, + st_mult(sizeof(uint32_t), ctx->commits.nr), write_graph_chunk_generation_data); if (ctx->num_generation_data_overflows) add_chunk(cf, GRAPH_CHUNKID_GENERATION_DATA_OVERFLOW, - sizeof(timestamp_t) * ctx->num_generation_data_overflows, + st_mult(sizeof(timestamp_t), ctx->num_generation_data_overflows), write_graph_chunk_generation_data_overflow); if (ctx->num_extra_edges) add_chunk(cf, GRAPH_CHUNKID_EXTRAEDGES, - 4 * ctx->num_extra_edges, + st_mult(4, ctx->num_extra_edges), write_graph_chunk_extra_edges); if (ctx->changed_paths) { add_chunk(cf, GRAPH_CHUNKID_BLOOMINDEXES, - sizeof(uint32_t) * ctx->commits.nr, + st_mult(sizeof(uint32_t), ctx->commits.nr), write_graph_chunk_bloom_indexes); add_chunk(cf, GRAPH_CHUNKID_BLOOMDATA, - sizeof(uint32_t) * 3 - + ctx->total_bloom_filter_data_size, + st_add(sizeof(uint32_t) * 3, + ctx->total_bloom_filter_data_size), write_graph_chunk_bloom_data); } if (ctx->num_commit_graphs_after > 1) add_chunk(cf, GRAPH_CHUNKID_BASE, - hashsz * (ctx->num_commit_graphs_after - 1), + st_mult(hashsz, ctx->num_commit_graphs_after - 1), write_graph_chunk_base); hashwrite_be32(f, GRAPH_SIGNATURE); @@ -1999,7 +1999,7 @@ static int write_commit_graph_file(struct write_commit_graph_context *ctx) get_num_chunks(cf)); ctx->progress = start_delayed_progress( progress_title.buf, - get_num_chunks(cf) * ctx->commits.nr); + st_mult(get_num_chunks(cf), ctx->commits.nr)); } write_chunkfile(cf, ctx); -- cgit v1.2.3 From 209250ef38f353f174ee9e90e55f5a4605449f70 Mon Sep 17 00:00:00 2001 From: Taylor Blau Date: Wed, 12 Jul 2023 19:37:57 -0400 Subject: commit-graph.c: prevent overflow in add_graph_to_chain() The commit-graph uses a fanout table with 4-byte entries to store the number of commits at each shard of the commit-graph. So it is OK to have a commit graph with as many as 2^32-1 stored commits. But we risk overflowing any computation which may exceed the 32-bit (unsigned) maximum when those computations are (incorrectly) performed using 32-bit operands. There are a couple of spots in `add_graph_to_chain()` where we could potentially overflow the result: - First, when comparing the list of existing entries in the commit-graph chain. It is unlikely that this should ever overflow, since it would require having roughly 2^32-1/g->hash_len commit-graphs in the chain. But let's guard that computation with a `st_mult()` just to be safe. - Second, when computing the number of commits in the graph added to the front of the chain. This value is also a 32-bit unsigned, but we should make sure that it does not grow beyond the maximum value. Signed-off-by: Taylor Blau Signed-off-by: Junio C Hamano --- commit-graph.c | 11 +++++++++-- 1 file changed, 9 insertions(+), 2 deletions(-) (limited to 'commit-graph.c') diff --git a/commit-graph.c b/commit-graph.c index 86c76bd2f8..17ab3e8029 100644 --- a/commit-graph.c +++ b/commit-graph.c @@ -482,7 +482,7 @@ static int add_graph_to_chain(struct commit_graph *g, if (!cur_g || !oideq(&oids[n], &cur_g->oid) || - !hasheq(oids[n].hash, g->chunk_base_graphs + g->hash_len * n)) { + !hasheq(oids[n].hash, g->chunk_base_graphs + st_mult(g->hash_len, n))) { warning(_("commit-graph chain does not match")); return 0; } @@ -492,8 +492,15 @@ static int add_graph_to_chain(struct commit_graph *g, g->base_graph = chain; - if (chain) + if (chain) { + if (unsigned_add_overflows(chain->num_commits, + chain->num_commits_in_base)) { + warning(_("commit count in base graph too high: %"PRIuMAX), + (uintmax_t)chain->num_commits_in_base); + return 0; + } g->num_commits_in_base = chain->num_commits + chain->num_commits_in_base; + } return 1; } -- cgit v1.2.3 From 0bd8f30a0e4e474163eb2d8dc3020d51ec3c8a35 Mon Sep 17 00:00:00 2001 From: Taylor Blau Date: Wed, 12 Jul 2023 19:38:00 -0400 Subject: commit-graph.c: prevent overflow in `load_oid_from_graph()` In a similar spirit as previous commits, ensure that we don't overflow when trying to compute an offset into the `chunk_oid_lookup` table when the `lex_index` of the item we're trying to look up exceeds `2^32-1/g->hash_len`. Signed-off-by: Taylor Blau Signed-off-by: Junio C Hamano --- commit-graph.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'commit-graph.c') diff --git a/commit-graph.c b/commit-graph.c index 17ab3e8029..517c816a94 100644 --- a/commit-graph.c +++ b/commit-graph.c @@ -754,7 +754,7 @@ static void load_oid_from_graph(struct commit_graph *g, lex_index = pos - g->num_commits_in_base; - oidread(oid, g->chunk_oid_lookup + g->hash_len * lex_index); + oidread(oid, g->chunk_oid_lookup + st_mult(g->hash_len, lex_index)); } static struct commit_list **insert_parent_or_die(struct repository *r, -- cgit v1.2.3 From 2740ed1c76df769aa1c6e75020ace72e2cc2e47f Mon Sep 17 00:00:00 2001 From: Taylor Blau Date: Wed, 12 Jul 2023 19:38:03 -0400 Subject: commit-graph.c: prevent overflow in `fill_commit_graph_info()` In a similar spirit as previous commits, ensure that we don't overflow in a few spots within `fill_commit_graph_info()`: - First, when computing an offset into the commit data chunk, which can occur when the `lex_index` of the item we're looking up exceeds 2^32-1/GRAPH_DATA_WIDTH. - A similar issue when computing the generation date offset for commits with `lex_index` greater than 2^32-1/4. Note that in practice this will never overflow, since the left-hand operand is from calling `sizeof(...)` and is thus already a `size_t`. But wrap that in an `st_mult()` to make it clear that we intend to perform this computation using 64-bit operands. - Finally, a nearly identical issue as above when computing an offset into the `generation_data_overflow` chunk. Signed-off-by: Taylor Blau Signed-off-by: Junio C Hamano --- commit-graph.c | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) (limited to 'commit-graph.c') diff --git a/commit-graph.c b/commit-graph.c index 517c816a94..69110e4dbb 100644 --- a/commit-graph.c +++ b/commit-graph.c @@ -790,7 +790,7 @@ static void fill_commit_graph_info(struct commit *item, struct commit_graph *g, die(_("invalid commit position. commit-graph is likely corrupt")); lex_index = pos - g->num_commits_in_base; - commit_data = g->chunk_commit_data + GRAPH_DATA_WIDTH * lex_index; + commit_data = g->chunk_commit_data + st_mult(GRAPH_DATA_WIDTH, lex_index); graph_data = commit_graph_data_at(item); graph_data->graph_pos = pos; @@ -800,14 +800,14 @@ static void fill_commit_graph_info(struct commit *item, struct commit_graph *g, item->date = (timestamp_t)((date_high << 32) | date_low); if (g->read_generation_data) { - offset = (timestamp_t)get_be32(g->chunk_generation_data + sizeof(uint32_t) * lex_index); + offset = (timestamp_t)get_be32(g->chunk_generation_data + st_mult(sizeof(uint32_t), lex_index)); if (offset & CORRECTED_COMMIT_DATE_OFFSET_OVERFLOW) { if (!g->chunk_generation_data_overflow) die(_("commit-graph requires overflow generation data but has none")); offset_pos = offset ^ CORRECTED_COMMIT_DATE_OFFSET_OVERFLOW; - graph_data->generation = item->date + get_be64(g->chunk_generation_data_overflow + 8 * offset_pos); + graph_data->generation = item->date + get_be64(g->chunk_generation_data_overflow + st_mult(8, offset_pos)); } else graph_data->generation = item->date + offset; } else -- cgit v1.2.3 From 50a71c2942167654f95d00b450a961cf387547ec Mon Sep 17 00:00:00 2001 From: Taylor Blau Date: Wed, 12 Jul 2023 19:38:05 -0400 Subject: commit-graph.c: prevent overflow in `fill_commit_in_graph()` In a similar spirit as previous commits, ensure that we don't overflow when the lex_index of the commit we are trying to fill out exceeds 2^32-1/(g->hash_len+16). The other hunk touched in this patch is not susceptible to overflow, since an explicit cast is made to a 64-bit unsigned value. For clarity and consistency with the rest of the commits in this series, avoid a tricky to reason about cast, and use `st_mult()` directly. Signed-off-by: Taylor Blau Signed-off-by: Junio C Hamano --- commit-graph.c | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'commit-graph.c') diff --git a/commit-graph.c b/commit-graph.c index 69110e4dbb..5e32063d3d 100644 --- a/commit-graph.c +++ b/commit-graph.c @@ -838,7 +838,7 @@ static int fill_commit_in_graph(struct repository *r, fill_commit_graph_info(item, g, pos); lex_index = pos - g->num_commits_in_base; - commit_data = g->chunk_commit_data + (g->hash_len + 16) * lex_index; + commit_data = g->chunk_commit_data + st_mult(g->hash_len + 16, lex_index); item->object.parsed = 1; @@ -860,7 +860,7 @@ static int fill_commit_in_graph(struct repository *r, } parent_data_ptr = (uint32_t*)(g->chunk_extra_edges + - 4 * (uint64_t)(edge_value & GRAPH_EDGE_LAST_MASK)); + st_mult(4, edge_value & GRAPH_EDGE_LAST_MASK)); do { edge_value = get_be32(parent_data_ptr); pptr = insert_parent_or_die(r, g, -- cgit v1.2.3 From 51c31a6408c1eae3ad6c2f78ec136c1b415cad72 Mon Sep 17 00:00:00 2001 From: Taylor Blau Date: Wed, 12 Jul 2023 19:38:08 -0400 Subject: commit-graph.c: prevent overflow in `load_tree_for_commit()` In a similar spirit as previous commits, ensure that we don't overflow when computing an offset into the commit_data chunk when the (relative) graph position exceeds 2^32-1/GRAPH_DATA_WIDTH. Signed-off-by: Taylor Blau Signed-off-by: Junio C Hamano --- commit-graph.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'commit-graph.c') diff --git a/commit-graph.c b/commit-graph.c index 5e32063d3d..08d773567f 100644 --- a/commit-graph.c +++ b/commit-graph.c @@ -980,7 +980,7 @@ static struct tree *load_tree_for_commit(struct repository *r, g = g->base_graph; commit_data = g->chunk_commit_data + - GRAPH_DATA_WIDTH * (graph_pos - g->num_commits_in_base); + st_mult(GRAPH_DATA_WIDTH, graph_pos - g->num_commits_in_base); oidread(&oid, commit_data); set_commit_tree(c, lookup_tree(r, &oid)); -- cgit v1.2.3 From 19565d093d248ba4c2330d96314a547feed41112 Mon Sep 17 00:00:00 2001 From: Taylor Blau Date: Wed, 12 Jul 2023 19:38:11 -0400 Subject: commit-graph.c: prevent overflow in `split_graph_merge_strategy()` In a similar spirit as previous commits, ensure that we don't overflow when choosing how to split and merge different layers of the commit-graph. In particular, avoid a potential overflow between `size_mult` and `num_commits`, as well as a potential overflow between the number of commits currently in the merged graph, and the number of commits in the graph about to be merged. Signed-off-by: Taylor Blau Signed-off-by: Junio C Hamano --- commit-graph.c | 7 ++++++- 1 file changed, 6 insertions(+), 1 deletion(-) (limited to 'commit-graph.c') diff --git a/commit-graph.c b/commit-graph.c index 08d773567f..d9795e3aa4 100644 --- a/commit-graph.c +++ b/commit-graph.c @@ -2112,11 +2112,16 @@ static void split_graph_merge_strategy(struct write_commit_graph_context *ctx) if (flags != COMMIT_GRAPH_SPLIT_MERGE_PROHIBITED && flags != COMMIT_GRAPH_SPLIT_REPLACE) { - while (g && (g->num_commits <= size_mult * num_commits || + while (g && (g->num_commits <= st_mult(size_mult, num_commits) || (max_commits && num_commits > max_commits))) { if (g->odb != ctx->odb) break; + if (unsigned_add_overflows(num_commits, g->num_commits)) + die(_("cannot merge graphs with %"PRIuMAX", " + "%"PRIuMAX" commits"), + (uintmax_t)num_commits, + (uintmax_t)g->num_commits); num_commits += g->num_commits; g = g->base_graph; -- cgit v1.2.3 From d76e0a744d3a8c1713f0e913325cab7da92f01ef Mon Sep 17 00:00:00 2001 From: Taylor Blau Date: Wed, 12 Jul 2023 19:38:13 -0400 Subject: commit-graph.c: prevent overflow in `merge_commit_graph()` When merging two commit graphs, ensure that we don't attempt to merge two graphs which, when combined, have more total commits than the 32-bit unsigned maximum. Signed-off-by: Taylor Blau Signed-off-by: Junio C Hamano --- commit-graph.c | 5 +++++ 1 file changed, 5 insertions(+) (limited to 'commit-graph.c') diff --git a/commit-graph.c b/commit-graph.c index d9795e3aa4..8333ce8e04 100644 --- a/commit-graph.c +++ b/commit-graph.c @@ -2179,6 +2179,11 @@ static void merge_commit_graph(struct write_commit_graph_context *ctx, uint32_t i; uint32_t offset = g->num_commits_in_base; + if (unsigned_add_overflows(ctx->commits.nr, g->num_commits)) + die(_("cannot merge graph %s, too many commits: %"PRIuMAX), + oid_to_hex(&g->oid), + (uintmax_t)st_add(ctx->commits.nr, g->num_commits)); + ALLOC_GROW(ctx->commits.list, ctx->commits.nr + g->num_commits, ctx->commits.alloc); for (i = 0; i < g->num_commits; i++) { -- cgit v1.2.3 From 588af1bfd3c810e02df1d8adc37e9c43a7f97920 Mon Sep 17 00:00:00 2001 From: Taylor Blau Date: Wed, 12 Jul 2023 19:38:16 -0400 Subject: commit-graph.c: prevent overflow in `write_commit_graph()` In a similar spirit as previous commits, ensure that we don't overflow when trying to read an existing OID while writing a new commit-graph. Signed-off-by: Taylor Blau Signed-off-by: Junio C Hamano --- commit-graph.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'commit-graph.c') diff --git a/commit-graph.c b/commit-graph.c index 8333ce8e04..54697e7a4d 100644 --- a/commit-graph.c +++ b/commit-graph.c @@ -2454,7 +2454,7 @@ int write_commit_graph(struct object_directory *odb, struct commit_graph *g = ctx->r->objects->commit_graph; for (i = 0; i < g->num_commits; i++) { struct object_id oid; - oidread(&oid, g->chunk_oid_lookup + g->hash_len * i); + oidread(&oid, g->chunk_oid_lookup + st_mult(g->hash_len, i)); oid_array_append(&ctx->oids, &oid); } } -- cgit v1.2.3 From 9a25cad7e0228bfd16f2c41b34e9d71a4217085c Mon Sep 17 00:00:00 2001 From: Taylor Blau Date: Wed, 12 Jul 2023 19:38:19 -0400 Subject: commit-graph.c: prevent overflow in `verify_commit_graph()` In a similar spirit as previous commits, ensure that we don't overflow when trying to read an OID out of an existing commit-graph during verification. Signed-off-by: Taylor Blau Signed-off-by: Junio C Hamano --- commit-graph.c | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'commit-graph.c') diff --git a/commit-graph.c b/commit-graph.c index 54697e7a4d..dc5bcfe05b 100644 --- a/commit-graph.c +++ b/commit-graph.c @@ -2585,7 +2585,7 @@ int verify_commit_graph(struct repository *r, struct commit_graph *g, int flags) for (i = 0; i < g->num_commits; i++) { struct commit *graph_commit; - oidread(&cur_oid, g->chunk_oid_lookup + g->hash_len * i); + oidread(&cur_oid, g->chunk_oid_lookup + st_mult(g->hash_len, i)); if (i && oidcmp(&prev_oid, &cur_oid) >= 0) graph_report(_("commit-graph has incorrect OID order: %s then %s"), @@ -2633,7 +2633,7 @@ int verify_commit_graph(struct repository *r, struct commit_graph *g, int flags) timestamp_t generation; display_progress(progress, i + 1); - oidread(&cur_oid, g->chunk_oid_lookup + g->hash_len * i); + oidread(&cur_oid, g->chunk_oid_lookup + st_mult(g->hash_len, i)); graph_commit = lookup_commit(r, &cur_oid); odb_commit = (struct commit *)create_object(r, &cur_oid, alloc_commit_node(r)); -- cgit v1.2.3