linux-kernel - Re: [PATCH] __div64_32: implement division by multiplication for 32-bit arches

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: <1446104062.2584.8.camel@synopsys.com>
Date:	Thu, 29 Oct 2015 07:34:23 +0000
From:	Alexey Brodkin <Alexey.Brodkin@...opsys.com>
To:	"nicolas.pitre@...aro.org" <nicolas.pitre@...aro.org>
CC:	"rmk+kernel@....linux.org.uk" <rmk+kernel@....linux.org.uk>,
	"linux-kernel@...r.kernel.org" <linux-kernel@...r.kernel.org>,
	"Vineet.Gupta1@...opsys.com" <Vineet.Gupta1@...opsys.com>,
	"shemminger@...ux-foundation.org" <shemminger@...ux-foundation.org>,
	"mingo@...e.hu" <mingo@...e.hu>,
	"linux-snps-arc@...ts.infradead.org" 
	<linux-snps-arc@...ts.infradead.org>,
	"davem@...emloft.net" <davem@...emloft.net>
Subject: Re: [PATCH] __div64_32: implement division by multiplication for
 32-bit arches

Hi Nicolas,

On Wed, 2015-10-28 at 19:32 -0400, Nicolas Pitre wrote:
> On Thu, 29 Oct 2015, Alexey Brodkin wrote:
> 
> > Fortunately we already have much better __div64_32() for 32-bit ARM.
> > There in case of division by constant preprocessor calculates so-called
> > "magic number" which is later used in multiplications instead of divisions.
> 
> It's not magic, it is science.  :-)

Indeed, but I was under impression that's how people call that value in that
particular case. So for me it looks appropriate here.

> > It's really nice and very optimal but obviously works only for ARM
> > because ARM assembly is involved.
> > 
> > Now why don't we extend the same approach to all other 32-bit arches
> > with multiplication part implemented in pure C. With good compiler
> > resulting assembly will be quite close to manually written assembly.
> 
> You appear to have left out optimizations where there is no overflow to 
> carry.  That, too, can be determined at compile time.

That might be the case - let me look at that a bit more.
But that was not the biggest problem. I actually wanted to send it
as RFC but due to last minute change I made "git pathc-format -1" and
forgot to change topic from PATCH to RFC.

> > But there's at least 1 problem which I don't know how to solve.
> > Preprocessor magic only happens if __div64_32() is inlined (that's
> > obvious - preprocessor has to know if divider is constant or not).
> > 
> > But __div64_32() is already marked as weak function (which in its turn
> > is required to allow some architectures to provide its own optimal
> > implementations). I.e. addition of "inline" for __div64_32() is not an
> > option.
> 
> You can't inline __div64_32().  It should remain as is and used only for 
> the slow path.
> 
> For the constant based optimization to work, you need to modify do_div() 
> in include/asm-generic/div64.h directly.

I thought about that but if I replace existing implementation of do_div()
with proposed here some arches like SH and MIPS won't be able to use their
own __div64_32() in do_div() any longer.

So how to deal with that then?

> > So I do want to hear opinions on how to proceed with that patch.
> > Indeed there's the simplest solution - use this implementation only in
> > my architecture of preference (read ARC) but IMHO this change may
> > benefit other architectures as well.
> > 
> > Signed-off-by: Alexey Brodkin <abrodkin@...opsys.com>
> > Cc: linux-snps-arc@...ts.infradead.org
> > Cc: Vineet Gupta <vgupta@...opsys.com>
> > Cc: Ingo Molnar <mingo@...e.hu>
> > Cc: Stephen Hemminger <shemminger@...ux-foundation.org>
> > Cc: David S. Miller <davem@...emloft.net>
> > Cc: Nicolas Pitre <nico@....org>
> 
> This email address has been unused for the last 7 years. Please update 
> your reference.

My bad - I blindly took that email from your prehistoric patch
"[ARM] 3611/4: optimize do_div() when divisor is constant".

-Alexey