linux-kernel - Re: [patch 2/7] lib/hashmod: Add modulo based hash mechanism

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]

Date:	13 May 2016 23:54:03 -0400
From:	"George Spelvin" <linux@...izon.com>
To:	torvalds@...ux-foundation.org
Cc:	eric.dumazet@...il.com, linux@...izon.com,
	linux-kernel@...r.kernel.org, riel@...hat.com, tglx@...utronix.de
Subject: Re: [patch 2/7] lib/hashmod: Add modulo based hash mechanism

On May 1, 2016 at 9:51 AM, Lnus Torvalds wrote:
> On Sun, May 1, 2016 at 2:43 AM, George Spelvin <linux@...izon.com> wrote:
>> * If you feel ambitious, add a 32-bit CONFIG_ARCH_HAS_SLOW_MULTIPLIER
>>   exception path.

> Let's make that a separate worry, and just fix hash_64() first.
> 
> In particular, that means "let's not touch COLDEN_RATIO_32 yet". I
> suspect that when we *do* change that value, we do want the
> non-multiplying version you had.

I've been working on this, and just a brief status update: it's definitely
one of those rabbit holes.

There are exactly three architectures which (some models) don't have
an efficient 32x32->32-bit multiply:

- arch/m58k: MC68000 (and 68010 and 68328) no-mmu
- arch/h8300: Most (all?) of the H8 processor series
- arch/microblaze: Depending on Verilog compilation options

The thing is, they all don't have a barrel shifter, either.
Indeed, only the m68k even has multi-bit shift instructions.

So the upshot is that it's not clear that shift-and-add is a whole lot
better.  Working out the timing on the 68000, I can beat the multiply
code, but not by much.

So I'm working on arch-specific solutions for those three cases.

H8 and 68000 have 16x16->32-bit multiplies, which can be used to make a
reasonable hash function (some H8 models can multiply faster than they
can shift!), but if you configure a Microblaze with neither multiplier
nor barrel shifter (which arch/microblaze/Kconfig.platform lets you do),
I have no idea what to do.