guard object lookups against 32-bit overflow
Get series with b4
b4 am [email protected]Versions newest first
- v1 Latest20 patches 7 repliesIn review
Patches in v1 No applies recorded yet
Reviews trailers per patch
None of the 20 patches has a Reviewed-by or Acked-by.
| Patch | Phillip Wood |
|---|---|
| 1/20 | |
| 2/20 | Helped-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.
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