RE: [PATCH v4 1/3] math.h: add DIV_ROUND_UP_NO_OVERFLOW

[David Laight <David.Laight@ACULAB.COM>]

From: Linus Torvalds
> Sent: 24 October 2023 23:53
> 
> On Tue, 24 Oct 2023 at 09:32, Linus Torvalds
> <torvalds@linux-foundation.org> wrote:
> >
> > I would really prefer to just make our regular DIV_ROUND_UP() DTRT.  But:
> >
> >  - people do use it with complex first arguments (ie function calls
> > etc) that we don't want to evaluate twice
> >
> >  - we can't make it an inline function, because the types aren't fixed
> >
> >  - we can't even use a statement expression and __auto_type, because
> > these things are used in type definitions etc and need to be constant
> > expressions

Doesn't min() get around that by using is_constexpr() and
__builtin_choose_exptr() - the same could be done here.

> 
> Ok. I have a potential beginning of a solution.
> 
> It is unbelievably disgustingly complicated. But it might approach
> being correct.
> 
> And by that "it might approach being correct" I obviously mean "this
> is untested, but builds at least some kernel code".
> 
> I'm almost certain it will fail on more complex cases, because I
> already found a lot of questionable stuff that was simply hidden by
> the old macro just silently doing the C arithmetic type conversions,
> and this thing does type handling manually.
> 
> I'm hoping that somebody will go "Linus, you're just being
> *completely* silly, it's much easier to do XYZ".

> Doing a non-overflowing DIV_ROUND_UP() that is usable in all contexts is
> actually very nasty.
>
> This is a trial balloon..  The signed cases need more thought.  The best
> option would be to disallow them (by not listing them in the _Generic()
> rules). But they currently happen, often for bad reasons, ie wireless has
>
> 	DIV_ROUND_UP(interval, MSEC_PER_SEC);
>
> and while 'interval' is a proper u32, MSEC_PER_SEC is defined to be
> '1000L', so the resulting C arithmetic is done in signed 'long'.

Maybe use some of the 'stuff' from min() and convert compile-time
constant 'd' to signed int to avoid promotions.

Indeed the whole thing really only makes sense for (d > 0 && n >= 0)
so forcing an unsigned divide wouldn't be a bad thing at all.
It will also generate better code when 'd' is a power of 2.

Ignoring the n==0 case I think this always generates an unsigned
divide, never does sign extension and does a 32bit divide
for 32bit arguments.

#define CVT_ULL(x) ((x) + 0u + 0ul + 0ull)
#define DIV_ROUND_UP(n, d) ((CVT_ULL(n) + CVT_ULL(d) - 1) / CVT_ULL(d) + 1)

It should be possible to error if 'd' is a signed variable or
a non-positive constant.
I'd guess most 'd' are constants.

Erroring signed 'n' is possible but might be annoying.

	David

-
Registered Address Lakeside, Bramley Road, Mount Farm, Milton Keynes, MK1 1PT, UK
Registration No: 1397386 (Wales)