code review 7543043: runtime: faster & safer hash function

runtime: faster & safer hash function

Uses AES hardware instructions on 386/amd64 to implement
a fast hash function.  Incorporates a random key to
thwart hash collision DOS attacks.
Depends on CL#7548043 for new assembly instructions.

Update issue 3885
Helps some by making hashing faster.  Go time drops from
0.65s to 0.51s.

[khr, 2013-03-06 23:06:42]

Hello rsc@golang.org (cc: golang-dev@googlegroups.com),

I'd like you to review this change to
https://code.google.com/p/go/

[r, 2013-03-06 23:09:40]

Can you capture your timings in a benchmark, then use misc/benchcmp to report
the numbers?

[bradfitz, 2013-03-06 23:14:33]

You might want to split off the assembler/linker changes into their own CL.
 That part is relatively simple and safe.

On Wed, Mar 6, 2013 at 3:06 PM, <khr@golang.org> wrote:

> Reviewers: rsc,
>
> Message:
> Hello rsc@golang.org (cc: golang-dev@googlegroups.com),
>
> I'd like you to review this change to
> https://code.google.com/p/go/
>
>
> Description:
> runtime: faster & safer hash function
>
> Uses AES hardware instructions on 386/amd64 to implement
> a fast hash function.  Incorporates a random key to
> thwart hash collision DOS attacks.
>
> Update issue 3885
> Helps some by making hashing faster.  Go time drops from
> 0.65s to 0.51s.
>
> Please review this at
https://codereview.appspot.**com/7543043/<https://codereview.appspot.com/7543...
>
> Affected files:
>   M src/cmd/6a/lex.c
>   M src/cmd/6l/6.out.h
>   M src/cmd/6l/l.h
>   M src/cmd/6l/optab.c
>   M src/cmd/6l/span.c
>   M src/cmd/8a/a.y
>   M src/cmd/8a/lex.c
>   M src/cmd/8a/y.tab.c
>   M src/cmd/8a/y.tab.h
>   M src/cmd/8l/8.out.h
>   M src/cmd/8l/l.h
>   M src/cmd/8l/optab.c
>   M src/cmd/8l/span.c
>   M src/pkg/runtime/alg.c
>   M src/pkg/runtime/asm_386.s
>   M src/pkg/runtime/asm_amd64.s
>   M src/pkg/runtime/asm_arm.s
>   M src/pkg/runtime/runtime.c
>   M src/pkg/runtime/runtime.h
>   M src/pkg/runtime/thread_darwin.**c
>   M src/pkg/runtime/thread_**freebsd.c
>   M src/pkg/runtime/thread_linux.c
>   M src/pkg/runtime/thread_netbsd.**c
>   M src/pkg/runtime/thread_**openbsd.c
>   M src/pkg/runtime/thread_plan9.c
>   M src/pkg/runtime/thread_**windows.c
>
>
> --
>
> ---You received this message because you are subscribed to the Google
> Groups "golang-dev" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to
golang-dev+unsubscribe@**googlegroups.com<golang-dev%2Bunsubscribe@googlegrou...
> .
> For more options, visit
https://groups.google.com/**groups/opt_out<https://groups.google.com/groups/o...
> .
>
>
>

[remyoudompheng, 2013-03-06 23:36:33]

https://codereview.appspot.com/7543043/diff/5001/src/cmd/8l/8.out.h
File src/cmd/8l/8.out.h (right):

https://codereview.appspot.com/7543043/diff/5001/src/cmd/8l/8.out.h#newcode156
src/cmd/8l/8.out.h:156: AMOVQ,
MOVQ is SSE2, is it for consistency with 6a?

https://codereview.appspot.com/7543043/diff/5001/src/cmd/8l/8.out.h#newcode471
src/cmd/8l/8.out.h:471: AAESENC,
the SSE2 comment above is misleading.

https://codereview.appspot.com/7543043/diff/5001/src/pkg/runtime/alg.c
File src/pkg/runtime/alg.c (right):

https://codereview.appspot.com/7543043/diff/5001/src/pkg/runtime/alg.c#newcod...
src/pkg/runtime/alg.c:490: }
This approach may work for trivial cases but it doesn't change any behaviour for
very simple key types like [2]string and struct{ A, B string }.

What is the purpose?

[khr1, 2013-03-06 23:51:08]

Here's some testing numbers:

benchmark             old ns/op    new ns/op    delta
BenchmarkHashSpeed           63           49  -22.48%

Here's the benchmark:

package main

import (
        "fmt"
        "flag"
        "testing"
)

var size int
func init() {
        flag.IntVar(&size, "size", 10, "size of map")
        flag.Parse()
}

func BenchmarkHashSpeed(b *testing.B) {
        strings := make([]string, size)
        for i := 0; i < size; i++ {
        strings[i] = fmt.Sprintf("string#%d", i)
        }
        sum := 0
        m := make(map[string]int, size)
        for i := 0; i < size; i++ {
                m[strings[i]] = 0
        }
        idx := 0
        for i := 0; i < b.N; i++ {
                sum += m[strings[idx]]
                idx++
                if (idx == size) { idx = 0 }
        }
}



On Wed, Mar 6, 2013 at 3:14 PM, Brad Fitzpatrick <bradfitz@golang.org>wrote:

> You might want to split off the assembler/linker changes into their own
> CL.  That part is relatively simple and safe.
>
> On Wed, Mar 6, 2013 at 3:06 PM, <khr@golang.org> wrote:
>
>> Reviewers: rsc,
>>
>> Message:
>> Hello rsc@golang.org (cc: golang-dev@googlegroups.com),
>>
>> I'd like you to review this change to
>> https://code.google.com/p/go/
>>
>>
>> Description:
>> runtime: faster & safer hash function
>>
>> Uses AES hardware instructions on 386/amd64 to implement
>> a fast hash function.  Incorporates a random key to
>> thwart hash collision DOS attacks.
>>
>> Update issue 3885
>> Helps some by making hashing faster.  Go time drops from
>> 0.65s to 0.51s.
>>
>> Please review this at
https://codereview.appspot.**com/7543043/<https://codereview.appspot.com/7543...
>>
>> Affected files:
>>   M src/cmd/6a/lex.c
>>   M src/cmd/6l/6.out.h
>>   M src/cmd/6l/l.h
>>   M src/cmd/6l/optab.c
>>   M src/cmd/6l/span.c
>>   M src/cmd/8a/a.y
>>   M src/cmd/8a/lex.c
>>   M src/cmd/8a/y.tab.c
>>   M src/cmd/8a/y.tab.h
>>   M src/cmd/8l/8.out.h
>>   M src/cmd/8l/l.h
>>   M src/cmd/8l/optab.c
>>   M src/cmd/8l/span.c
>>   M src/pkg/runtime/alg.c
>>   M src/pkg/runtime/asm_386.s
>>   M src/pkg/runtime/asm_amd64.s
>>   M src/pkg/runtime/asm_arm.s
>>   M src/pkg/runtime/runtime.c
>>   M src/pkg/runtime/runtime.h
>>   M src/pkg/runtime/thread_darwin.**c
>>   M src/pkg/runtime/thread_**freebsd.c
>>   M src/pkg/runtime/thread_linux.c
>>   M src/pkg/runtime/thread_netbsd.**c
>>   M src/pkg/runtime/thread_**openbsd.c
>>   M src/pkg/runtime/thread_plan9.c
>>   M src/pkg/runtime/thread_**windows.c
>>
>>
>>
>> --
>>
>> ---You received this message because you are subscribed to the Google
>> Groups "golang-dev" group.
>> To unsubscribe from this group and stop receiving emails from it, send an
>> email to
golang-dev+unsubscribe@**googlegroups.com<golang-dev%2Bunsubscribe@googlegrou...
>> .
>> For more options, visit
https://groups.google.com/**groups/opt_out<https://groups.google.com/groups/o...
>> .
>>
>>
>>
>

[khr1, 2013-03-06 23:58:22]

I've split out the assembly part into
https://codereview.appspot.com/7548043/


On Wed, Mar 6, 2013 at 3:36 PM, <remyoudompheng@gmail.com> wrote:

>
>
https://codereview.appspot.**com/7543043/diff/5001/src/cmd/**8l/8.out.h<https...
> File src/cmd/8l/8.out.h (right):
>
> https://codereview.appspot.**com/7543043/diff/5001/src/cmd/**
>
8l/8.out.h#newcode156<https://codereview.appspot.com/7543043/diff/5001/src/cmd/8l/8.out.h#newcode156>
> src/cmd/8l/8.out.h:156: AMOVQ,
> MOVQ is SSE2, is it for consistency with 6a?
>
> https://codereview.appspot.**com/7543043/diff/5001/src/cmd/**
>
8l/8.out.h#newcode471<https://codereview.appspot.com/7543043/diff/5001/src/cmd/8l/8.out.h#newcode471>
> src/cmd/8l/8.out.h:471: AAESENC,
> the SSE2 comment above is misleading.
>
>
https://codereview.appspot.**com/7543043/diff/5001/src/pkg/**runtime/alg.c<ht...
> File src/pkg/runtime/alg.c (right):
>
> https://codereview.appspot.**com/7543043/diff/5001/src/pkg/**
>
runtime/alg.c#newcode490<https://codereview.appspot.com/7543043/diff/5001/src/pkg/runtime/alg.c#newcode490>
> src/pkg/runtime/alg.c:490: }
> This approach may work for trivial cases but it doesn't change any
> behaviour for very simple key types like [2]string and struct{ A, B
> string }.
>
> What is the purpose?
>
>
https://codereview.appspot.**com/7543043/<https://codereview.appspot.com/7543...
>

[remyoudompheng, 2013-03-06 23:58:26]

On 2013/3/7 Keith Randall <khr@google.com> wrote:
> Here's some testing numbers:
>
> benchmark             old ns/op    new ns/op    delta
> BenchmarkHashSpeed           63           49  -22.48%
>
> Here's the benchmark:
>
> package main
>
> import (
>         "fmt"
>         "flag"
>         "testing"
> )
>
> var size int
> func init() {
>         flag.IntVar(&size, "size", 10, "size of map")
>         flag.Parse()
> }
>
> func BenchmarkHashSpeed(b *testing.B) {
>         strings := make([]string, size)
>         for i := 0; i < size; i++ {
>        strings[i] = fmt.Sprintf("string#%d", i)
>         }
>         sum := 0
>         m := make(map[string]int, size)
>         for i := 0; i < size; i++ {
>                 m[strings[i]] = 0
>         }
>         idx := 0
>         for i := 0; i < b.N; i++ {
>                 sum += m[strings[idx]]
>                 idx++
>                 if (idx == size) { idx = 0 }
>         }
> }

Can you benchmark integer keys (32-bit and 64-bit) ?

Rémy.

[khr1, 2013-03-07 00:01:07]

The low-hanging fruit is to speed up map[String]...  I agree that the more
types we can apply this to, the better.


On Wed, Mar 6, 2013 at 3:36 PM, <remyoudompheng@gmail.com> wrote:

>
>
https://codereview.appspot.**com/7543043/diff/5001/src/cmd/**8l/8.out.h<https...
> File src/cmd/8l/8.out.h (right):
>
> https://codereview.appspot.**com/7543043/diff/5001/src/cmd/**
>
8l/8.out.h#newcode156<https://codereview.appspot.com/7543043/diff/5001/src/cmd/8l/8.out.h#newcode156>
> src/cmd/8l/8.out.h:156: AMOVQ,
> MOVQ is SSE2, is it for consistency with 6a?
>
> https://codereview.appspot.**com/7543043/diff/5001/src/cmd/**
>
8l/8.out.h#newcode471<https://codereview.appspot.com/7543043/diff/5001/src/cmd/8l/8.out.h#newcode471>
> src/cmd/8l/8.out.h:471: AAESENC,
> the SSE2 comment above is misleading.
>
>
https://codereview.appspot.**com/7543043/diff/5001/src/pkg/**runtime/alg.c<ht...
> File src/pkg/runtime/alg.c (right):
>
> https://codereview.appspot.**com/7543043/diff/5001/src/pkg/**
>
runtime/alg.c#newcode490<https://codereview.appspot.com/7543043/diff/5001/src/pkg/runtime/alg.c#newcode490>
> src/pkg/runtime/alg.c:490: }
> This approach may work for trivial cases but it doesn't change any
> behaviour for very simple key types like [2]string and struct{ A, B
> string }.
>
> What is the purpose?
>
>
https://codereview.appspot.**com/7543043/<https://codereview.appspot.com/7543...
>

[khr1, 2013-03-07 00:04:31]

benchmark                   old ns/op    new ns/op    delta
BenchmarkHashStringSpeed           63           50  -20.22%
BenchmarkHashInt32Speed            44           40   -7.26%
BenchmarkHashInt64Speed            52           42  -19.08%



On Wed, Mar 6, 2013 at 4:01 PM, Keith Randall <khr@google.com> wrote:

> The low-hanging fruit is to speed up map[String]...  I agree that the more
> types we can apply this to, the better.
>
>
> On Wed, Mar 6, 2013 at 3:36 PM, <remyoudompheng@gmail.com> wrote:
>
>>
>>
https://codereview.appspot.**com/7543043/diff/5001/src/cmd/**8l/8.out.h<https...
>> File src/cmd/8l/8.out.h (right):
>>
>> https://codereview.appspot.**com/7543043/diff/5001/src/cmd/**
>>
8l/8.out.h#newcode156<https://codereview.appspot.com/7543043/diff/5001/src/cmd/8l/8.out.h#newcode156>
>> src/cmd/8l/8.out.h:156: AMOVQ,
>> MOVQ is SSE2, is it for consistency with 6a?
>>
>> https://codereview.appspot.**com/7543043/diff/5001/src/cmd/**
>>
8l/8.out.h#newcode471<https://codereview.appspot.com/7543043/diff/5001/src/cmd/8l/8.out.h#newcode471>
>> src/cmd/8l/8.out.h:471: AAESENC,
>> the SSE2 comment above is misleading.
>>
>> https://codereview.appspot.**com/7543043/diff/5001/src/pkg/**
>>
runtime/alg.c<https://codereview.appspot.com/7543043/diff/5001/src/pkg/runtime/alg.c>
>> File src/pkg/runtime/alg.c (right):
>>
>> https://codereview.appspot.**com/7543043/diff/5001/src/pkg/**
>>
runtime/alg.c#newcode490<https://codereview.appspot.com/7543043/diff/5001/src/pkg/runtime/alg.c#newcode490>
>> src/pkg/runtime/alg.c:490: }
>> This approach may work for trivial cases but it doesn't change any
>> behaviour for very simple key types like [2]string and struct{ A, B
>> string }.
>>
>> What is the purpose?
>>
>>
https://codereview.appspot.**com/7543043/<https://codereview.appspot.com/7543...
>>
>
>

[dsymonds, 2013-03-07 02:10:23]

Unless you mean to benchmark fmt and the map construction too, you'll
want to use b.StopTimer at the start of BenchmarkHashSpeed, and
b.StartTimer immediately before the loop from 0..N.

[rsc, 2013-03-07 03:11:33]

Or just call b.ResetTimer and don't worry about stop.
I don't see the benchmark in the CL (I don't see any Go files), but it seems
likely that N is large enough it doesn't matter.

[rsc, 2013-03-07 03:23:08]

Looks good but where are the benchmarks?

https://codereview.appspot.com/7543043/diff/9002/src/pkg/runtime/alg.c
File src/pkg/runtime/alg.c (right):

https://codereview.appspot.com/7543043/diff/9002/src/pkg/runtime/alg.c#newcod...
src/pkg/runtime/alg.c:470: // TODO: align somehow?  See asm_{386,amd64}.s
How aligned does it need to be?

https://codereview.appspot.com/7543043/diff/9002/src/pkg/runtime/alg.c#newcod...
src/pkg/runtime/alg.c:474: runtime·hashinit(uint8* random_data) {
s/* / */
s/ {/\n{/
sorry

https://codereview.appspot.com/7543043/diff/9002/src/pkg/runtime/asm_386.s
File src/pkg/runtime/asm_386.s (right):

https://codereview.appspot.com/7543043/diff/9002/src/pkg/runtime/asm_386.s#ne...
src/pkg/runtime/asm_386.s:27: JE	nocpuinfo
FWIW we require at least Pentiums (I forget which one is the cutoff) for various
of the atomics, so I think you can assume CPUID w/ AX=1 is there, since it was
on the 486. But this is fine too.

https://codereview.appspot.com/7543043/diff/9002/src/pkg/runtime/asm_amd64.s
File src/pkg/runtime/asm_amd64.s (right):

https://codereview.appspot.com/7543043/diff/9002/src/pkg/runtime/asm_amd64.s#...
src/pkg/runtime/asm_amd64.s:27: JE	nocpuinfo
Do you know of 64-bit systems without CPUID support?

https://codereview.appspot.com/7543043/diff/9002/src/pkg/runtime/runtime.h
File src/pkg/runtime/runtime.h (right):

https://codereview.appspot.com/7543043/diff/9002/src/pkg/runtime/runtime.h#ne...
src/pkg/runtime/runtime.h:561: hash_random_bytes = 32
please make this HashRandomBytes so it's more clearly a constant where it gets
used.

https://codereview.appspot.com/7543043/diff/9002/src/pkg/runtime/thread_darwin.c
File src/pkg/runtime/thread_darwin.c (right):

https://codereview.appspot.com/7543043/diff/9002/src/pkg/runtime/thread_darwi...
src/pkg/runtime/thread_darwin.c:74: fd = runtime·open((uint8*)"/dev/urandom", 0
/* O_RDONLY */, 0);
If there are ways to avoid every program reading from urandom, I'd like to try
to use them. I don't know of one here.

https://codereview.appspot.com/7543043/diff/9002/src/pkg/runtime/thread_linux.c
File src/pkg/runtime/thread_linux.c (right):

https://codereview.appspot.com/7543043/diff/9002/src/pkg/runtime/thread_linux...
src/pkg/runtime/thread_linux.c:170: fd = runtime·open((uint8*)"/dev/urandom", 0
/* O_RDONLY */, 0);
On ELF systems I believe the auxv gives us in the AT_RANDOM entry the address of
16 random bytes. Perhaps that is sufficient and if present we can avoid reading
/dev/urandom at startup?

[khr1, 2013-03-07 03:50:01]

On Wed, Mar 6, 2013 at 7:23 PM, <rsc@golang.org> wrote:

> Looks good but where are the benchmarks?
>
>
>
>
https://codereview.appspot.**com/7543043/diff/9002/src/pkg/**runtime/alg.c<ht...
> File src/pkg/runtime/alg.c (right):
>
> https://codereview.appspot.**com/7543043/diff/9002/src/pkg/**
>
runtime/alg.c#newcode470<https://codereview.appspot.com/7543043/diff/9002/src/pkg/runtime/alg.c#newcode470>
> src/pkg/runtime/alg.c:470: // TODO: align somehow?  See
> asm_{386,amd64}.s
> How aligned does it need to be?
>

it needs to be 16-byte aligned to help.  Text gets aligned to 16 bytes, but
there doesn't seem to be any way to get data aligned to 16 bytes.


>
> https://codereview.appspot.**com/7543043/diff/9002/src/pkg/**
>
runtime/alg.c#newcode474<https://codereview.appspot.com/7543043/diff/9002/src/pkg/runtime/alg.c#newcode474>
> src/pkg/runtime/alg.c:474: runtime·hashinit(uint8* random_data) {
> s/* / */
> s/ {/\n{/
> sorry
>

Done.  Still adjusting my brain to the style...


>
> https://codereview.appspot.**com/7543043/diff/9002/src/pkg/**
>
runtime/asm_386.s<https://codereview.appspot.com/7543043/diff/9002/src/pkg/runtime/asm_386.s>
> File src/pkg/runtime/asm_386.s (right):
>
> https://codereview.appspot.**com/7543043/diff/9002/src/pkg/**
>
runtime/asm_386.s#newcode27<https://codereview.appspot.com/7543043/diff/9002/src/pkg/runtime/asm_386.s#newcode27>
> src/pkg/runtime/asm_386.s:27: JE        nocpuinfo
> FWIW we require at least Pentiums (I forget which one is the cutoff) for
> various of the atomics, so I think you can assume CPUID w/ AX=1 is
> there, since it was on the 486. But this is fine too.
>
> https://codereview.appspot.**com/7543043/diff/9002/src/pkg/**
>
runtime/asm_amd64.s<https://codereview.appspot.com/7543043/diff/9002/src/pkg/runtime/asm_amd64.s>
> File src/pkg/runtime/asm_amd64.s (right):
>
> https://codereview.appspot.**com/7543043/diff/9002/src/pkg/**
>
runtime/asm_amd64.s#newcode27<https://codereview.appspot.com/7543043/diff/9002/src/pkg/runtime/asm_amd64.s#newcode27>
> src/pkg/runtime/asm_amd64.s:**27: JE      nocpuinfo
> Do you know of 64-bit systems without CPUID support?
>

Nope, just being careful.


> https://codereview.appspot.**com/7543043/diff/9002/src/pkg/**
>
runtime/runtime.h<https://codereview.appspot.com/7543043/diff/9002/src/pkg/runtime/runtime.h>
> File src/pkg/runtime/runtime.h (right):
>
> https://codereview.appspot.**com/7543043/diff/9002/src/pkg/**
>
runtime/runtime.h#newcode561<https://codereview.appspot.com/7543043/diff/9002/src/pkg/runtime/runtime.h#newcode561>
> src/pkg/runtime/runtime.h:561: hash_random_bytes = 32
> please make this HashRandomBytes so it's more clearly a constant where
> it gets used.
>

Done.


>
> https://codereview.appspot.**com/7543043/diff/9002/src/pkg/**
>
runtime/thread_darwin.c<https://codereview.appspot.com/7543043/diff/9002/src/pkg/runtime/thread_darwin.c>
> File src/pkg/runtime/thread_darwin.**c (right):
>
> https://codereview.appspot.**com/7543043/diff/9002/src/pkg/**
>
runtime/thread_darwin.c#**newcode74<https://codereview.appspot.com/7543043/diff/9002/src/pkg/runtime/thread_darwin.c#newcode74>
> src/pkg/runtime/thread_darwin.**c:74: fd =
> runtime·open((uint8*)"/dev/**urandom", 0 /* O_RDONLY */, 0);
> If there are ways to avoid every program reading from urandom, I'd like
> to try to use them. I don't know of one here.
>
> https://codereview.appspot.**com/7543043/diff/9002/src/pkg/**
>
runtime/thread_linux.c<https://codereview.appspot.com/7543043/diff/9002/src/pkg/runtime/thread_linux.c>
> File src/pkg/runtime/thread_linux.c (right):
>
> https://codereview.appspot.**com/7543043/diff/9002/src/pkg/**
>
runtime/thread_linux.c#**newcode170<https://codereview.appspot.com/7543043/diff/9002/src/pkg/runtime/thread_linux.c#newcode170>
> src/pkg/runtime/thread_linux.**c:170: fd =
> runtime·open((uint8*)"/dev/**urandom", 0 /* O_RDONLY */, 0);
> On ELF systems I believe the auxv gives us in the AT_RANDOM entry the
> address of 16 random bytes. Perhaps that is sufficient and if present we
> can avoid reading /dev/urandom at startup?
>

There doesn't seem to be any obviously good solution.  Reading /dev/urandom
seems pretty heavyweight.  We could enable this with a flag or an
environment variable, but that's a knob that people then need to know
about.  We could initialize on first use of a map, but I suspect all
programs create at least one map on startup (flags? environment
variables?).  I was pondering using RDTSC + PID, but that probably isn't
enough randomness.  I haven't heard of AT_RANDOM before, might be a good
solution for targets that support it, 16 bytes is probably enough.


>
https://codereview.appspot.**com/7543043/<https://codereview.appspot.com/7543...
>

[rsc, 2013-03-07 03:56:23]

The linker (dodata in src/cmd/ld) already aligns data objects based on
their size. Bigger objects get bigger alignments. The entire data segment
is sorted by size so even large alignments waste little space: it's not
like 16-byte objects are interleaved with 1-byte objects. Right now the
maximum alignment is PtrSize, but I think using alignment=16 when s->size
>= 16 is perfectly fine.

[khr1, 2013-03-07 04:12:31]

On Wed, Mar 6, 2013 at 3:36 PM, <remyoudompheng@gmail.com> wrote:

>
>
https://codereview.appspot.**com/7543043/diff/5001/src/cmd/**8l/8.out.h<https...
> File src/cmd/8l/8.out.h (right):
>
> https://codereview.appspot.**com/7543043/diff/5001/src/cmd/**
>
8l/8.out.h#newcode156<https://codereview.appspot.com/7543043/diff/5001/src/cmd/8l/8.out.h#newcode156>
> src/cmd/8l/8.out.h:156: AMOVQ,
> MOVQ is SSE2, is it for consistency with 6a?
>

I can move it if you'd like.  I put it with the other MOVs as it isn't
really an SSE op in definition, just in implementation.


>
> https://codereview.appspot.**com/7543043/diff/5001/src/cmd/**
>
8l/8.out.h#newcode471<https://codereview.appspot.com/7543043/diff/5001/src/cmd/8l/8.out.h#newcode471>
> src/cmd/8l/8.out.h:471: AAESENC,
> the SSE2 comment above is misleading.
>

I moved AESENC and PINSRD, and PSHUFB to their own SSE3+ section.


>
>
https://codereview.appspot.**com/7543043/diff/5001/src/pkg/**runtime/alg.c<ht...
> File src/pkg/runtime/alg.c (right):
>
> https://codereview.appspot.**com/7543043/diff/5001/src/pkg/**
>
runtime/alg.c#newcode490<https://codereview.appspot.com/7543043/diff/5001/src/pkg/runtime/alg.c#newcode490>
> src/pkg/runtime/alg.c:490: }
> This approach may work for trivial cases but it doesn't change any
> behaviour for very simple key types like [2]string and struct{ A, B
> string }.
>
> What is the purpose?
>
>
https://codereview.appspot.**com/7543043/<https://codereview.appspot.com/7543...
>

[khr1, 2013-03-07 21:18:51]

You mean something like this?  Seems to work...

--- a/src/cmd/ld/data.c Thu Mar 07 12:54:00 2013 -0800
+++ b/src/cmd/ld/data.c Thu Mar 07 13:17:48 2013 -0800
@@ -877,7 +877,9 @@
 static int32
 alignsymsize(int32 s)
 {
- if(s >= 8)
+ if(s >= 16)
+ s = rnd(s, 16);
+ else if(s >= 8)
  s = rnd(s, 8);
  else if(s >= PtrSize)
  s = rnd(s, PtrSize);
@@ -901,8 +903,10 @@
  datsize = rnd(datsize, 2);
  else if(t & 4)
  datsize = rnd(datsize, 4);
+ else if(t & 8)
+ datsize = rnd(datsize, 8);
  else
- datsize = rnd(datsize, 8);
+ datsize = rnd(datsize, 16);
  }
  return datsize;
 }



On Wed, Mar 6, 2013 at 7:56 PM, Russ Cox <rsc@golang.org> wrote:

> The linker (dodata in src/cmd/ld) already aligns data objects based on
> their size. Bigger objects get bigger alignments. The entire data segment
> is sorted by size so even large alignments waste little space: it's not
> like 16-byte objects are interleaved with 1-byte objects. Right now the
> maximum alignment is PtrSize, but I think using alignment=16 when s->size
> >= 16 is perfectly fine.
>
>
>

[minux1, 2013-03-07 21:33:45]

https://codereview.appspot.com/7543043/diff/37001/src/pkg/runtime/thread_netb...
File src/pkg/runtime/thread_netbsd.c (right):

https://codereview.appspot.com/7543043/diff/37001/src/pkg/runtime/thread_netb...
src/pkg/runtime/thread_netbsd.c:181: runtime·hashinit(nil);
all *BSD have /dev/urandom, so you can just copy the darwin code.

[rsc, 2013-03-07 23:45:55]

On Thu, Mar 7, 2013 at 4:18 PM, Keith Randall <khr@google.com> wrote:

> You mean something like this?  Seems to work...
>

Yes. Please hold off on changing that file though. I have a more
comprehensive change pending (there was lots wrong in alignment for
generating ELF files). The effect should be the same.

Russ

[elias.naur, 2013-03-08 12:24:25]

On 2013/03/07 03:50:01, khr1 wrote:
> 
> There doesn't seem to be any obviously good solution.  Reading /dev/urandom
> seems pretty heavyweight.  We could enable this with a flag or an
> environment variable, but that's a knob that people then need to know
> about.  We could initialize on first use of a map, but I suspect all
> programs create at least one map on startup (flags? environment
> variables?).  I was pondering using RDTSC + PID, but that probably isn't
> enough randomness.  I haven't heard of AT_RANDOM before, might be a good
> solution for targets that support it, 16 bytes is probably enough.
> 

FYI: Go already uses AT_RANDOM from the auxillary vector. Look for AT_RANDOM in
signal_linux_arm.c. And FWIW, if RDTSC is available, it is currently used to
seed runtime·fastrand1.

[khr1, 2013-03-11 18:37:43]

Ok, this change is ready to go.  Anyone want to take a last look?  The only
major change has been to futz with the seed initialization.


On Fri, Mar 8, 2013 at 4:24 AM, <elias.naur@gmail.com> wrote:

> On 2013/03/07 03:50:01, khr1 wrote:
>
>  There doesn't seem to be any obviously good solution.  Reading
>>
> /dev/urandom
>
>> seems pretty heavyweight.  We could enable this with a flag or an
>> environment variable, but that's a knob that people then need to know
>> about.  We could initialize on first use of a map, but I suspect all
>> programs create at least one map on startup (flags? environment
>> variables?).  I was pondering using RDTSC + PID, but that probably
>>
> isn't
>
>> enough randomness.  I haven't heard of AT_RANDOM before, might be a
>>
> good
>
>> solution for targets that support it, 16 bytes is probably enough.
>>
>
>
> FYI: Go already uses AT_RANDOM from the auxillary vector. Look for
> AT_RANDOM in signal_linux_arm.c. And FWIW, if RDTSC is available, it is
> currently used to seed runtime·fastrand1.
>
>
https://codereview.appspot.**com/7543043/<https://codereview.appspot.com/7543...
>

[r, 2013-03-11 19:48:22]

https://codereview.appspot.com/7543043/diff/58001/src/pkg/runtime/alg.c
File src/pkg/runtime/alg.c (right):

https://codereview.appspot.com/7543043/diff/58001/src/pkg/runtime/alg.c#newco...
src/pkg/runtime/alg.c:483: if ((runtime·cpuid_ecx & (1 << 25)) != 0 && // aes
(aesenc)
no space after if (etc.) here and elsewhere (sorry)

https://codereview.appspot.com/7543043/diff/58001/src/pkg/runtime/alg.c#newco...
src/pkg/runtime/alg.c:498: if (n > HashRandomBytes) n = HashRandomBytes;
two lines please.

https://codereview.appspot.com/7543043/diff/58001/src/pkg/runtime/mapspeed_te...
File src/pkg/runtime/mapspeed_test.go (right):

https://codereview.appspot.com/7543043/diff/58001/src/pkg/runtime/mapspeed_te...
src/pkg/runtime/mapspeed_test.go:24: for i := 0; i < b.N; i++ {
you want to reset the benchmark timer after the setup, in all benchmarks.

https://codereview.appspot.com/7543043/diff/58001/src/pkg/runtime/thread_darw...
File src/pkg/runtime/thread_darwin.c (right):

https://codereview.appspot.com/7543043/diff/58001/src/pkg/runtime/thread_darw...
src/pkg/runtime/thread_darwin.c:71: static byte urandom_data[HashRandomBytes];
this isn't really about threading (see comment above). maybe put it in a
separate function with a good name.

https://codereview.appspot.com/7543043/diff/58001/src/pkg/runtime/thread_free...
File src/pkg/runtime/thread_freebsd.c (right):

https://codereview.appspot.com/7543043/diff/58001/src/pkg/runtime/thread_free...
src/pkg/runtime/thread_freebsd.c:117: if (runtime·startup_random_data == nil) {
ditto re: function

https://codereview.appspot.com/7543043/diff/58001/src/pkg/runtime/thread_linux.c
File src/pkg/runtime/thread_linux.c (right):

https://codereview.appspot.com/7543043/diff/58001/src/pkg/runtime/thread_linu...
src/pkg/runtime/thread_linux.c:162: if (runtime·startup_random_data == nil) {
ditto re: function.

https://codereview.appspot.com/7543043/diff/58001/src/pkg/runtime/thread_netb...
File src/pkg/runtime/thread_netbsd.c (right):

https://codereview.appspot.com/7543043/diff/58001/src/pkg/runtime/thread_netb...
src/pkg/runtime/thread_netbsd.c:182: if (runtime·startup_random_data == nil) {
ditto re: function

https://codereview.appspot.com/7543043/diff/58001/src/pkg/runtime/thread_open...
File src/pkg/runtime/thread_openbsd.c (right):

https://codereview.appspot.com/7543043/diff/58001/src/pkg/runtime/thread_open...
src/pkg/runtime/thread_openbsd.c:161: if (runtime·startup_random_data == nil) {
ditto re: function

https://codereview.appspot.com/7543043/diff/58001/src/pkg/runtime/thread_wind...
File src/pkg/runtime/thread_windows.c (right):

https://codereview.appspot.com/7543043/diff/58001/src/pkg/runtime/thread_wind...
src/pkg/runtime/thread_windows.c:89: if (runtime·startup_random_data == nil) {
ditto re: function.

if you do this uniformly, the hash initialization will all be under one
function, clearly identified by name, but different across cpu/os.

https://codereview.appspot.com/7543043/diff/58001/src/pkg/runtime/vdso_linux_...
File src/pkg/runtime/vdso_linux_amd64.c (right):

https://codereview.appspot.com/7543043/diff/58001/src/pkg/runtime/vdso_linux_...
src/pkg/runtime/vdso_linux_amd64.c:329: if (elf_auxv[i].a_type == AT_RANDOM) {
ditto i think but i'm not sure - this is beyond my ken.

[rsc, 2013-03-11 20:19:25]

Despite the file name, osinit is about per-process os startup, not just a single
thread.

https://codereview.appspot.com/7543043/diff/58001/src/pkg/runtime/thread_darw...
File src/pkg/runtime/thread_darwin.c (right):

https://codereview.appspot.com/7543043/diff/58001/src/pkg/runtime/thread_darw...
src/pkg/runtime/thread_darwin.c:71: static byte urandom_data[HashRandomBytes];
On 2013/03/11 19:48:22, r wrote:
> this isn't really about threading (see comment above). maybe put it in a
> separate function with a good name.

Please keep it here. We can rename the file if we need to.

[r, 2013-03-11 20:40:30]

https://codereview.appspot.com/7543043/diff/58001/src/pkg/runtime/thread_darw...
File src/pkg/runtime/thread_darwin.c (right):

https://codereview.appspot.com/7543043/diff/58001/src/pkg/runtime/thread_darw...
src/pkg/runtime/thread_darwin.c:71: static byte urandom_data[HashRandomBytes];
I said separate function, not separate file. i don't see the problem with
separating it out so it's comparable across operating systems.

[rsc, 2013-03-11 20:48:41]

Sorry, I can't see the files anymore. Rietveld keeps giving me chunk
mismatch errors.

The osinit function is the API exported by this file for operating
system-specific initialization. As long as the function is static and
called from osinit, sure.

[r, 2013-03-11 20:54:27]

On Mon, Mar 11, 2013 at 1:48 PM, Russ Cox <rsc@golang.org> wrote:
> As long as the function is static and called
> from osinit, sure.

That's my intention. The theory is that this is messy goo that each
guy does differently and it would be nice to have a separate function
for it, for grouping and clarity. It would be a static function and
called by osinit only.

[rsc, 2013-03-11 20:57:47]

sgtm

[khr1, 2013-03-12 16:21:09]

I've made a separate function and called it from hashinit, not osinit.
 That way we don't need to call it if we don't have the aes instructions.


On Mon, Mar 11, 2013 at 1:57 PM, Russ Cox <rsc@golang.org> wrote:

> sgtm
>
>

[rsc, 2013-03-12 16:32:28]

LGTM

Thanks very much. Looks great.
Apologies for the code formatting nits. They apply to all the copies.

https://codereview.appspot.com/7543043/diff/87001/src/pkg/runtime/thread_darw...
File src/pkg/runtime/thread_darwin.c (right):

https://codereview.appspot.com/7543043/diff/87001/src/pkg/runtime/thread_darw...
src/pkg/runtime/thread_darwin.c:72: runtime·get_random_data(byte **rnd, int32
*rnd_len) {
{ on next line. sorry.

https://codereview.appspot.com/7543043/diff/87001/src/pkg/runtime/thread_darw...
src/pkg/runtime/thread_darwin.c:74: int32 fd =
runtime·open((uint8*)"/dev/urandom", 0 /* O_RDONLY */, 0);
Please initialize variables in separate statements, just to maintain the old C
style of the code.

Also if you declare open to take an int8* you can avoid the cast.

[khr, 2013-03-12 17:47:48]

*** Submitted as https://code.google.com/p/go/source/detail?r=e3a5e1e9db71 ***

runtime: faster & safer hash function

Uses AES hardware instructions on 386/amd64 to implement
a fast hash function.  Incorporates a random key to
thwart hash collision DOS attacks.
Depends on CL#7548043 for new assembly instructions.

Update issue 3885
Helps some by making hashing faster.  Go time drops from
0.65s to 0.51s.

R=rsc, r, bradfitz, remyoudompheng, khr, dsymonds, minux.ma, elias.naur
CC=golang-dev
https://codereview.appspot.com/7543043