[RFC PATCH v2 5/5] range-diff: fix integer overflow & segfault on cost[i + n * j]

in preceding commits the "column_count" and the "int*"'s we malloc() were changed to track their length with a size_t, so we're able to track as many "cost" items as malloc() will give us.

But we'd still segfault on relatively large range comparisons, e.g. this would segfault:

    git -P range-diff --creation-factor=50 origin/master...git-for-windows/main

The reason for that is that we'd still use integer types to compute an array index into the "cost" array, which would overflow. The result of a signed overflow in C is undefined, but on my system it'll result in a negative number, and a prompt segfault as we'll try to access a negative array index.

Luckily we used the COST() macro in linear-assignment.c already for all of these lookups, and in a preceding commit we renamed "n" in "range-diff.c"'s get_correspondences() to "column_count" in preparation for using it here.

So let's use it for the three occurrences of "cost" indexing in range-diff.c, and have the COST() macro itself do overflow checking with st_mult() and st_add(). Due to the cast to "size_t" from "int" we'll avoid the segfault, and will end up correctly pointing to the relevant "int *".

It's not important that we use the new cost_offset() inline function here, we could also use the st_*() macros inline. By using it we'll get a more meaningful backtrace in a debugger to the relevant addition/multiplication line if we end up calling die() here.

It's still possible for us to overflow even with this change, that's because the iteration variables (such as "i" and "j" in this diff context are all "int"), even if we changed those to "size_t" or "intmax_t" (not trivial, as we depend on them being negative in some places) the underlying "struct string_list"'s "nr" member is an "unsigned int", which would eventually overflow.

However the danger of that overflow isn't as great, as we were overflowing on "i + column_count * j" before this change, it'll require a much bigger range for us to have an integer overflow on the number of commits we're processing.

We're unlikely to encounter a 2-4 billion commit history on 32 bit platforms. Even if we did one of the types in the underlying object machinery would probably overflow before we overflowed here. So let's punt that for now. If we're ever going to solve that issue [1] to change the "struct string_list"'s "nr" member to a "size_t" might be a good start.

1. https://lore.kernel.org/git/RFC-patch-01.10-7c929096381-20211209T191653Z-avarab@gmail.com/

Signed-off-by: Ævar Arnfjörð Bjarmason <avarab@gmail.com>
---
 linear-assignment.c |  2 --
 linear-assignment.h | 17 +++++++++++++++++
 range-diff.c        |  6 +++---
 3 files changed, 20 insertions(+), 5 deletions(-)