Re: [RFC PATCH 00/10] range-diff: fix segfault due to integer overflow

From: Jeff King <peff@peff.net>
Date: Dec 22, 2021, 21:11 UTC
Message-ID: <YcOUl4lIMRy7rzK8@coredump.intra.peff.net>
In-Reply-To: <nycvar.QRO.7.76.6.2112222143080.347@tvgsbejvaqbjf.bet>

On Wed, Dec 22, 2021 at 09:50:50PM +0100, Johannes Schindelin wrote:

Show 10 quoted lines

> To raise the limits you would have to understand the purpose of the
> calculations so that you can understand the range their data type needs to
> handle. The weights of the Hungarian Algorithm are distinctly _not_
> pointers, therefore using `size_t` is most likely the wrong thing to do.
> 
> Of course you can glance over the details and try to avoid digging into
> the algorithm to understand what it does before changing the data types
> and introducing `st_mult()`-like functions and macros, but that only makes
> it "relatively easy", at the price of "maybe incorrect". That would be in
> line with what I unfortunately have had to come to expect of your patches.

:( Whether you're frustrated with this topic or not, can we please stick to technical critiques? Either proposed changes are the right thing or not, and we can talk about that.

I know it can get hard if the review is "gee, it looks like this is going in the wrong direction, but I don't have time to dig in and tell you _exactly_ how it is wrong right now". And I think that is an OK thing to express, but your response here has a bit more bite to it than I think is strictly necessary.

> The _actual_ "relatively easy" way is to imitate the limits we use in
> xdiff (for similar reasons). As I said before.

I had a similar thought at first, too. But because one of the array sizes we compute is (nr_a + nr_b)^2, I fear the limits end up pretty low (e.g., my 32767 by 32767 example). That's a pretty big range diff, but it doesn't seem like an outrageous input to throw at the system (especially if most of the entries end up finding a match and showing one line of equality).

It may be that there are multiple limits to consider, though. E.g., the square of the sum of the sides, as above, is one. But there may be some benefit to making that work (by using size_t and st_add) but putting a hard limit like 2^30 on the number of commits on one side (e.g., for ranking scores). And that's where understanding exactly what the algorithm is doing becomes necessary.

-Peff