netdev - Re: [PATCH v2] net: Toeplitz library functions

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] [day] [month] [year] [list]

Message-ID: <1387503509.19078.412.camel@edumazet-glaptop2.roam.corp.google.com>
Date:	Thu, 19 Dec 2013 17:38:29 -0800
From:	Eric Dumazet <eric.dumazet@...il.com>
To:	Tom Herbert <therbert@...gle.com>
Cc:	haiyangz@...rosoft.com, bhutchings@...arflare.com,
	davem@...emloft.net, netdev@...r.kernel.org
Subject: Re: [PATCH v2] net: Toeplitz library functions

On Thu, 2013-12-19 at 16:41 -0800, Tom Herbert wrote:
> Introduce Toeplitz hash functions. Toeplitz is a hash used primarily in
> NICs to perform RSS flow steering.  This is a software implementation
> of that. In order to make the hash calculation efficient, we precompute
> the possible hash values for each inidividual byte of input. The input
> length is up to 36 bytes, so we make an array of cache[36][256].

I really don't see how this can be faster than just a normal arithmetic
computation.

Modern cpus can do ~100+ instructions during the time needed to bring
one byte from memory.

On a moderate load and cold cache, hashing 16 bytes need more than 500
nsec (between 60 to 100 ns per cache line miss)

It seems this really can be done with maybe 5 or 6 instructions per bit.

The 8 bits per byte can unroll the inner loop and use no conditional
branch. (No need to search next bit, this is way too expensive)

Sort of :

https://github.com/YanVugenfirer/kvm-guest-drivers-windows/blob/master/NetKVM/DebugTools/RSS-Toeplitz/WinToeplitz.c

But a bit optimized ;)

test  $1,%dl
mov   %ecx,%edx
cmove $0,%edx
xor   %edx,%edi
rol   $1,%rcx

test  $2,%dl
mov   %ecx,%edx
cmove $0,%edx
xor   %edx,%edi
rol   $1,%rcx

test  $4,%dl
mov   %ecx,%edx
cmove $0,%edx
xor   %edx,%edi
rol   $1,%rcx

test  $8,%dl
mov   %ecx,%edx
cmove $0,%edx
xor   %edx,%edi
rol   $1,%rcx

Oh well...


--
To unsubscribe from this list: send the line "unsubscribe netdev" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html