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: <20231025172841.awb7s6o4ourqu4w5@mercury.elektranox.org>
Date:   Wed, 25 Oct 2023 19:28:41 +0200
From:   Sebastian Reichel <sebastian.reichel@...labora.com>
To:     Linus Torvalds <torvalds@...ux-foundation.org>
Cc:     Andy Shevchenko <andriy.shevchenko@...ux.intel.com>,
        Michael Turquette <mturquette@...libre.com>,
        Stephen Boyd <sboyd@...nel.org>,
        David Laight <David.Laight@...lab.com>,
        linux-clk@...r.kernel.org, linux-kernel@...r.kernel.org,
        Vasily Gorbik <gor@...ux.ibm.com>,
        Niklas Schnelle <schnelle@...ux.ibm.com>, kernel@...labora.com
Subject: Re: [PATCH v4 1/3] math.h: add DIV_ROUND_UP_NO_OVERFLOW

Hi,

On Tue, Oct 24, 2023 at 09:32:27AM -1000, Linus Torvalds wrote:
> [ Since you're cc'ing the s390 people, I assume that means that this
> all ended up being a follow-up to the s390 issue discussion ]

Actually I've noticed the issue in the clock framework some time
ago and Andy Shevchenko pointed me towards the s390 thread, which
is more or less about the same fundamental problem. So I added
everyone in Cc, to make sure this is solved properly and not just
s390 specific.

> On Tue, 24 Oct 2023 at 06:19, Sebastian Reichel
> <sebastian.reichel@...labora.com> wrote:
> >
> > Add a new DIV_ROUND_UP helper, which cannot overflow when
> > big numbers are being used.
> 
> This is really horrendously bad on some architectures (ie it might
> require *two* divisions):

I came up with this helper for the issue in the clock framework,
which currently use DIV_ROUND_UP_ULL() as a workaround. That solves
the issue on 32 bit systems (input arguments are of type 'unsigned
long'). But it also means doing u64 / u32 and I expect that do be
much more more expensive on 32 bit platforms than two divisons.

On 64 bit platforms the workaround is wrong, since the second
argument is reduced from 64 bit to 32 bit. It effectively breaks
platforms trying to request a frequency above 4.3 GHz from a clock
divider. Since that's not yet a common thing I guess this has not
yet been found and fixed by somebody else. I also just found it as
bycatch.

> > +#define DIV_ROUND_UP_NO_OVERFLOW(n, d) (((n) / (d)) + !!((n) % (d)))
> 
> but David Laight at least had a suggestion for that: when allowing
> multiple uses, you can just do
> 
>    #define DIV_ROUND_UP(n,d) ((n) ? ((n)-1)/(d)+1 : 0)
> 
> so now you're back to just one division and no horrible extra expense.
> 
> But we can't allow those multiple uses in general, sadly.
> 
> 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
> 
> That last thing means that even the "__builtin_choose_expr()" doesn't
> work, because the statement expression still needs to be _parsed_ as
> such, and that's not something we can do in those contexts.
> 
> Very annoying. Let me think about this.

Thanks.

-- Sebastian

Download attachment "signature.asc" of type "application/pgp-signature" (834 bytes)

Powered by blists - more mailing lists

Powered by Openwall GNU/*/Linux Powered by OpenVZ