git.vger.kernel.org archive mirror
 help / color / mirror / Atom feed
* [PATCH 00/20] guard object lookups against 32-bit overflow
@ 2023-07-12 23:37 Taylor Blau
  2023-07-12 23:37 ` [PATCH 01/20] packfile.c: prevent overflow in `nth_packed_object_id()` Taylor Blau
                   ` (19 more replies)
  0 siblings, 20 replies; 28+ messages in thread
From: Taylor Blau @ 2023-07-12 23:37 UTC (permalink / raw)
  To: git
  Cc: Derrick Stolee, Jeff King, Johannes Schindelin, Junio C Hamano,
	Victoria Dye

This is a series I wrote over the last week or so to address a handful
of spots where we may overflow a computation, and produce incorrect
results.

Most of these share a common theme, which is that many of our
data structures (packfiles, bitmaps, commit-graph, MIDX) all tolerate
up to 2^32-1 objects. But when we, say, multiply the number of objects
by some constant or other value which isn't a 64-bit unsigned, we'll
overflow.

Often times the overflows occur when looking up an object / bit
position / commit / etc which is at position 2^32-1/20 or greater,
causing us to exceed the maximum 32-bit unsigned value when we multiply
by 20 (or the_hash_algo->rawsz, if stored as an "unsigned int").

There are a handful of instances where the existing implementation won't
overflow (i.e. because one of the operands is already a size_t, or an
explicit cast is made, etc.). These instances are also replaced with
their corresponding checked functions (st_add(), st_mult(), etc.) to
more clearly express that these operations are supposed to be computed
with 64-bit values.

This series regrettably does not contain any tests. There was some
discussion internally about using a purpose-built test helper to
generate raw packs without going through fast-import. I looked around
for prior examples of how we handled testing (or not) when writing these
kinds of patches with the following script:

    $ git log --format='%H' -G 'st_(mult|add[234]?)\(' |
        xargs -I {} sh -c 'echo "==> {}" && git -P diff {}^ {} -- t'

And looking at each such commit which mentions st_mult(), st_add(), or
one of its variants, I could not find any examples of us constructing a
gigantic pack/MIDX/commit-graph/bitmap/etc specifically to trigger an
overflow.

Taylor Blau (20):
  packfile.c: prevent overflow in `nth_packed_object_id()`
  packfile.c: prevent overflow in `load_idx()`
  packfile.c: use checked arithmetic in `nth_packed_object_offset()`
  midx.c: use `size_t`'s for fanout nr and alloc
  midx.c: prevent overflow in `nth_midxed_object_oid()`
  midx.c: prevent overflow in `nth_midxed_offset()`
  midx.c: store `nr`, `alloc` variables as `size_t`'s
  midx.c: prevent overflow in `write_midx_internal()`
  midx.c: prevent overflow in `fill_included_packs_batch()`
  pack-bitmap.c: ensure that eindex lookups don't overflow
  commit-graph.c: prevent overflow in `write_commit_graph_file()`
  commit-graph.c: prevent overflow in add_graph_to_chain()
  commit-graph.c: prevent overflow in `load_oid_from_graph()`
  commit-graph.c: prevent overflow in `fill_commit_graph_info()`
  commit-graph.c: prevent overflow in `fill_commit_in_graph()`
  commit-graph.c: prevent overflow in `load_tree_for_commit()`
  commit-graph.c: prevent overflow in `split_graph_merge_strategy()`
  commit-graph.c: prevent overflow in `merge_commit_graph()`
  commit-graph.c: prevent overflow in `write_commit_graph()`
  commit-graph.c: prevent overflow in `verify_commit_graph()`

 commit-graph.c | 63 ++++++++++++++++++++++++++++++++------------------
 midx.c         | 42 ++++++++++++++++++---------------
 pack-bitmap.c  | 12 ++++++----
 packfile.c     | 15 ++++++------
 4 files changed, 79 insertions(+), 53 deletions(-)

-- 
2.41.0.347.g7b976b8871f

^ permalink raw reply	[flat|nested] 28+ messages in thread
end of thread, other threads:[~2023-07-14 16:29 UTC | newest]

Thread overview: 28+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2023-07-12 23:37 [PATCH 00/20] guard object lookups against 32-bit overflow Taylor Blau
2023-07-12 23:37 ` [PATCH 01/20] packfile.c: prevent overflow in `nth_packed_object_id()` Taylor Blau
2023-07-12 23:37 ` [PATCH 02/20] packfile.c: prevent overflow in `load_idx()` Taylor Blau
2023-07-13  8:21   ` Phillip Wood
2023-07-13 14:24     ` Taylor Blau
2023-07-14  0:54       ` Taylor Blau
2023-07-14  9:56         ` Phillip Wood
2023-07-14 16:29         ` Junio C Hamano
2023-07-14  9:55       ` Phillip Wood
2023-07-13 16:14     ` Junio C Hamano
2023-07-12 23:37 ` [PATCH 03/20] packfile.c: use checked arithmetic in `nth_packed_object_offset()` Taylor Blau
2023-07-12 23:37 ` [PATCH 04/20] midx.c: use `size_t`'s for fanout nr and alloc Taylor Blau
2023-07-12 23:37 ` [PATCH 05/20] midx.c: prevent overflow in `nth_midxed_object_oid()` Taylor Blau
2023-07-12 23:37 ` [PATCH 06/20] midx.c: prevent overflow in `nth_midxed_offset()` Taylor Blau
2023-07-12 23:37 ` [PATCH 07/20] midx.c: store `nr`, `alloc` variables as `size_t`'s Taylor Blau
2023-07-12 23:37 ` [PATCH 08/20] midx.c: prevent overflow in `write_midx_internal()` Taylor Blau
2023-07-12 23:37 ` [PATCH 09/20] midx.c: prevent overflow in `fill_included_packs_batch()` Taylor Blau
2023-07-12 23:37 ` [PATCH 10/20] pack-bitmap.c: ensure that eindex lookups don't overflow Taylor Blau
2023-07-12 23:37 ` [PATCH 11/20] commit-graph.c: prevent overflow in `write_commit_graph_file()` Taylor Blau
2023-07-12 23:37 ` [PATCH 12/20] commit-graph.c: prevent overflow in add_graph_to_chain() Taylor Blau
2023-07-12 23:38 ` [PATCH 13/20] commit-graph.c: prevent overflow in `load_oid_from_graph()` Taylor Blau
2023-07-12 23:38 ` [PATCH 14/20] commit-graph.c: prevent overflow in `fill_commit_graph_info()` Taylor Blau
2023-07-12 23:38 ` [PATCH 15/20] commit-graph.c: prevent overflow in `fill_commit_in_graph()` Taylor Blau
2023-07-12 23:38 ` [PATCH 16/20] commit-graph.c: prevent overflow in `load_tree_for_commit()` Taylor Blau
2023-07-12 23:38 ` [PATCH 17/20] commit-graph.c: prevent overflow in `split_graph_merge_strategy()` Taylor Blau
2023-07-12 23:38 ` [PATCH 18/20] commit-graph.c: prevent overflow in `merge_commit_graph()` Taylor Blau
2023-07-12 23:38 ` [PATCH 19/20] commit-graph.c: prevent overflow in `write_commit_graph()` Taylor Blau
2023-07-12 23:38 ` [PATCH 20/20] commit-graph.c: prevent overflow in `verify_commit_graph()` Taylor Blau

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).