Skip to content

guard object lookups against 32-bit overflow

Taylor Blau git 1 version In review

Get series with b4
b4 am [email protected]

Versions newest first

  1. v1 Latest20 patches 7 repliesIn review

Patches in v1 No applies recorded yet

#Subject and filesSizeRepliesApplied
1/20packfile.c: prevent overflow in `nth_packed_object_id()`packfile.c+2 -20 replies
2/20packfile.c: prevent overflow in `load_idx()`packfile.c+1 -17 replies
3/20packfile.c: use checked arithmetic in `nth_packed_object_offset()`packfile.c+5 -40 replies
4/20midx.c: use `size_t`'s for fanout nr and allocmidx.c+5 -30 replies
5/20midx.c: prevent overflow in `nth_midxed_object_oid()`midx.c+1 -10 replies
6/20midx.c: prevent overflow in `nth_midxed_offset()`midx.c+2 -10 replies
7/20midx.c: store `nr`, `alloc` variables as `size_t`'smidx.c+9 -70 replies
8/20midx.c: prevent overflow in `write_midx_internal()`midx.c+5 -40 replies
9/20midx.c: prevent overflow in `fill_included_packs_batch()`midx.c+2 -20 replies
10/20pack-bitmap.c: ensure that eindex lookups don't overflowpack-bitmap.c+7 -50 replies
11/20commit-graph.c: prevent overflow in `write_commit_graph_file()`commit-graph.c+10 -100 replies
12/20commit-graph.c: prevent overflow in add_graph_to_chain()commit-graph.c+9 -20 replies
13/20commit-graph.c: prevent overflow in `load_oid_from_graph()`commit-graph.c+1 -10 replies
14/20commit-graph.c: prevent overflow in `fill_commit_graph_info()`commit-graph.c+3 -30 replies
15/20commit-graph.c: prevent overflow in `fill_commit_in_graph()`commit-graph.c+2 -20 replies
16/20commit-graph.c: prevent overflow in `load_tree_for_commit()`commit-graph.c+1 -10 replies
17/20commit-graph.c: prevent overflow in `split_graph_merge_strategy()`commit-graph.c+6 -10 replies
18/20commit-graph.c: prevent overflow in `merge_commit_graph()`commit-graph.c+5 -00 replies
19/20commit-graph.c: prevent overflow in `write_commit_graph()`commit-graph.c+1 -10 replies
20/20commit-graph.c: prevent overflow in `verify_commit_graph()`commit-graph.c+2 -20 replies

Reviews trailers per patch

None of the 20 patches has a Reviewed-by or Acked-by.

PatchPhillip Wood
1/20
2/20Helped-by
3/20
4/20
5/20
6/20
7/20
8/20
9/20
10/20
11/20
12/20
13/20
14/20
15/20
16/20
17/20
18/20
19/20
20/20

Trailers given in replies are filled; those carried in the patches from earlier versions are outlined with dashes.

Read the v1 thread

Cover letter [PATCH 00/20] guard object lookups against 32-bit overflow

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(-)
Signature · 1 line
2.41.0.347.g7b976b8871f