| Message ID | RFC-patch-08.10-794d494bedd-20211209T191653Z-avarab@gmail.com (mailing list archive) |
|---|---|
| State | Superseded |
| Headers | show |
| Series | range-diff: fix segfault due to integer overflow | expand |
On Thu, Dec 09, 2021 at 08:19:25PM +0100, Ævar Arnfjörð Bjarmason wrote: > diff --git a/linear-assignment.c b/linear-assignment.c > index e9cec16132a..b6597b622c8 100644 > --- a/linear-assignment.c > +++ b/linear-assignment.c > @@ -10,7 +10,14 @@ static inline int cost_index(int *cost, int a, int b, int c) > { > int r; > > +#if defined(__GNUC__) || defined(__clang__) > + if (__builtin_mul_overflow(a, c, &r)) > + die(_("integer overflow in cost[%d + %d * %c] multiplication"), b, a, c); > + if (__builtin_add_overflow(b, r, &r)) > + die(_("integer overflow in cost[%d + ((%d * %d) = %d)] addition"), b, a, c, r); > +#else > r = b + a * c; > +#endif I think having an inline #if here is the wrong direction. We already have signed_add_overflows() which you could use for the second check. We haven't needed signed_mult_overflows() yet, but we could add one. Those helpers don't use intrinsics yet. I think it would be reasonable to have them do so when they're available. One of the big reasons we haven't done so yet is that they're not generally in hot paths. We generally use them while allocating, where the extra integer operations and conditional aren't a big deal. Here you depart from that and do the check on every index computation. I'm not completely opposed to that approach, but I think a simpler method (and what most spots have done so far) is to make sure the array allocation itself is computed correctly, and then have code which accesses it use an appropriate type to avoid overflow. In this case just using size_t for the index computation would work, wouldn't it? (Likewise, if you really want a negative value, then ssize_t should be OK. It can't represent the full range of size_t, but if it would overflow that implies the original allocation was consuming more than half of the address space, which would have failed at the time of allocation). I do see that the following patch replaces this #if with similar helpers from gnulib, which is better. And if we are going to go the route of using intrinsics in our helpers, then it might be a good idea to use gnulib's helpers to avoid portability pitfalls. But in that case we should probably be converting over callers of the existing helpers (and getting rid of those helpers). IMHO it isn't really worth it, though, if we can solve this just by switching to a more appropriate type here (and assuming there's not a big performance benefit to the other helper call sites). -Peff
diff --git a/linear-assignment.c b/linear-assignment.c index e9cec16132a..b6597b622c8 100644 --- a/linear-assignment.c +++ b/linear-assignment.c @@ -10,7 +10,14 @@ static inline int cost_index(int *cost, int a, int b, int c) { int r; +#if defined(__GNUC__) || defined(__clang__) + if (__builtin_mul_overflow(a, c, &r)) + die(_("integer overflow in cost[%d + %d * %c] multiplication"), b, a, c); + if (__builtin_add_overflow(b, r, &r)) + die(_("integer overflow in cost[%d + ((%d * %d) = %d)] addition"), b, a, c, r); +#else r = b + a * c; +#endif return r; }
Extend the cost_index() inline function added in the preceding commit with signed overflow detection that'll work on GCC[1] and Clang[2]. See 320d0b493a2 (add helpers for detecting size_t overflow, 2016-02-19) for the existing git-compat-util.h helpers to detect signed overflow. This fixes a segfault on that happens when "range-diff" is given a very large range to work with, such as the difference between git.git's "master" the git-for-windows fork: $ git -P range-diff --creation-factor=50 origin/master...git-for-windows/main fatal: integer overflow in cost[47395 + ((47396 * 45309) = -2147454537)] addition There are known bugs with using these functions in some versions of GCC, as we'll see in a subsequent commit we're better off detecting those with the "intprops.h" library, but for now let's add a simpler implementation that relies on the bare minimum of compiler checking. 1. https://gcc.gnu.org/onlinedocs/gcc/Integer-Overflow-Builtins.html#Integer-Overflow-Builtins 2. https://clang.llvm.org/docs/LanguageExtensions.html#checked-arithmetic-builtins Signed-off-by: Ævar Arnfjörð Bjarmason <avarab@gmail.com> --- linear-assignment.c | 7 +++++++ 1 file changed, 7 insertions(+)