Re: [RFC PATCH 08/10] linear-assignment.c: detect signed add/mul on GCC and Clang

From: Jeff King <peff@peff.net>
Date: Dec 10, 2021, 03:56 UTC
Message-ID: <YbLQA820y+WuGwRU@coredump.intra.peff.net>
In-Reply-To: <RFC-patch-08.10-794d494bedd-20211209T191653Z-avarab@gmail.com>

On Thu, Dec 09, 2021 at 08:19:25PM +0100, Ævar Arnfjörð Bjarmason wrote:

Show 16 quoted lines

> 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