linux-kernel - RE: [PATCH v4 1/3] math.h: add DIV_ROUND_UP_NO

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <4c2d36375bd74d94a2e6ef5d2fa0df99@AcuMS.aculab.com>
Date:   Wed, 25 Oct 2023 08:38:39 +0000
From:   David Laight <David.Laight@...LAB.COM>
To:     'Linus Torvalds' <torvalds@...ux-foundation.org>,
        Sebastian Reichel <sebastian.reichel@...labora.com>
CC:     Andy Shevchenko <andriy.shevchenko@...ux.intel.com>,
        Michael Turquette <mturquette@...libre.com>,
        Stephen Boyd <sboyd@...nel.org>,
        "linux-clk@...r.kernel.org" <linux-clk@...r.kernel.org>,
        "linux-kernel@...r.kernel.org" <linux-kernel@...r.kernel.org>,
        Vasily Gorbik <gor@...ux.ibm.com>,
        Niklas Schnelle <schnelle@...ux.ibm.com>,
        "kernel@...labora.com" <kernel@...labora.com>
Subject: RE: [PATCH v4 1/3] math.h: add DIV_ROUND_UP_NO_OVERFLOW

From: Linus Torvalds
> Sent: 24 October 2023 23:53
> 
> On Tue, 24 Oct 2023 at 09:32, Linus Torvalds
> <torvalds@...ux-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)