code review 5606048: runtime: add runtime.cputicks() and seed fastrand with it

runtime: add runtime.cputicks() and seed fastrand with it

This patch adds a function to get the current cpu ticks.  This is
deemed to be 'sufficiently random' to use to seed fastrand to mitigate
the algorithmic complexity attacks on the hash table implementation.

On AMD64 we use the RDTSC instruction.  For 386, this instruction,
while valid, is not recognized by 8a so I've inserted the opcode by
hand.  For ARM, this routine is currently stubbed to return a constant
0 value.

Future work: update 8a to recognize RDTSC.

Fixes issue 2630.

[dgryski, 2012-02-01 17:29:26]

Hello golang-dev@googlegroups.com,

I'd like you to review this change to
http://go.googlecode.com/hg/

[rsc, 2012-02-01 22:45:31]

This looks fine, but can you use BYTE instructions
so that the instruction looks the way it does in
the manuals?

Thanks.
Russ

[dgryski, 2012-02-02 06:11:17]

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

Please take another look.

[dgryski, 2012-02-02 06:12:52]

On 2012/02/01 22:45:31, rsc wrote:
> This looks fine, but can you use BYTE instructions
> so that the instruction looks the way it does in
> the manuals?

   Ah, thanks.  I misread the plan9 assembler documentation I found.

   Damian

[rsc, 2012-02-02 18:53:05]

Looks great; one more tiny change and then I'll submit.  Thanks.

http://codereview.appspot.com/5606048/diff/7001/src/pkg/runtime/proc.c
File src/pkg/runtime/proc.c (right):

http://codereview.appspot.com/5606048/diff/7001/src/pkg/runtime/proc.c#newcod...
src/pkg/runtime/proc.c:335: m->fastrand = 0x49f6428aUL + (runtime·cputicks() &
0xffffffff);
Let's keep m->id.  Can drop the mask.

m->fastrand = 0x49f6428aUL + m->id + runtime.cputicks();

[dgryski, 2012-02-02 18:56:20]

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

Please take another look.

[dgryski, 2012-02-02 19:00:36]

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

Please take another look.

[dgryski, 2012-02-02 19:02:08]

On 2012/02/02 19:00:36, dgryski wrote:
> Hello mailto:rsc@golang.org (cc: mailto:golang-dev@googlegroups.com),
> 
> Please take another look.

Still getting used to the dot in the function names.

[rsc, 2012-02-02 19:08:34]

LGTM

Thanks.

[rsc, 2012-02-02 19:09:44]

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

runtime: add runtime.cputicks() and seed fastrand with it

This patch adds a function to get the current cpu ticks.  This is
deemed to be 'sufficiently random' to use to seed fastrand to mitigate
the algorithmic complexity attacks on the hash table implementation.

On AMD64 we use the RDTSC instruction.  For 386, this instruction,
while valid, is not recognized by 8a so I've inserted the opcode by
hand.  For ARM, this routine is currently stubbed to return a constant
0 value.

Future work: update 8a to recognize RDTSC.

Fixes issue 2630.

R=rsc
CC=golang-dev
http://codereview.appspot.com/5606048

Committer: Russ Cox <rsc@golang.org>

[minux1, 2012-02-05 22:05:33]

But ARM CPUs doesn't have a portable method to get cpu cycles.
(the CCNT register in Coprocessor 15 appears in ARM11+, and it is only
accessible
in the privileged mode.) Also noted that the Linux 2.6.31+ does export the
corresponding
API (perf_event_open(2)), but it isn't made for our purpose (generating
random number),
and using it will mean dropping support for per-2.6.31 kernels.

Could we change the function name to something not that specific? Because
the current
function can't be portably implemented on all ARMv5+ CPUs.
Maybe on ARM platforms, we can only resort to read /dev/urandom??

Anyone has better ideas on how to implement this for Linux/ARM?

[dsymonds, 2012-02-05 22:14:32]

On Mon, Feb 6, 2012 at 9:05 AM, minux <minux.ma@gmail.com> wrote:

> Could we change the function name to something not that specific? Because
> the current
> function can't be portably implemented on all ARMv5+ CPUs.
> Maybe on ARM platforms, we can only resort to read /dev/urandom??

There's no reason why runtime.cputicks has to be implemented for every
platform. The code that calls runtime.cputicks just has to be written
in foo_$(GOOS).go files (or similar).


Dave.

[minux1, 2012-02-05 22:22:18]

On Mon, Feb 6, 2012 at 6:14 AM, David Symonds <dsymonds@golang.org> wrote:

> On Mon, Feb 6, 2012 at 9:05 AM, minux <minux.ma@gmail.com> wrote:
>
> > Could we change the function name to something not that specific? Because
> > the current
> > function can't be portably implemented on all ARMv5+ CPUs.
> > Maybe on ARM platforms, we can only resort to read /dev/urandom??
>
> There's no reason why runtime.cputicks has to be implemented for every
> platform. The code that calls runtime.cputicks just has to be written
> in foo_$(GOOS).go files (or similar).
>
Should we do this to proc.c (where runtime.cputicks is called)?
If not, I still think we need to change the function name (Actually, we
*only*
need a hard-to-predict random number, and it happens to be cpu cycles on
386 and amd64, but it might not be the case on ARM).

[rsc, 2012-02-05 22:24:01]

It is not a big deal for ARM cputicks to return 0.
Let's leave it at that.  If you want it to return the
current time in nanoseconds, that's fine too.
We don't need to shuffle any of the code that is
calling it.

Russ