Using get_cycles for add_timer_randomness

Using get_cycles for add_timer_randomness

[Arnd Bergmann]

I noticed that only i386 and x86-64 are currently using
a high resolution timer source when adding randomness.
Since many architectures have a working get_cycles()
implementation, it seems rather straightforward to use
that.

Has this been discussed before, or can anyone comment
on the implementation below?

This patch attempts to take into account the size of
cycles_t, which is either 32 or 64 bits wide but
independent of the architecture's word size.

The behavior should be nearly identical to the
old one on i386, x86-64 and all architectures
without a time stamp counter, while finding
more entropy on the other architectures.

	Arnd <><

===== drivers/char/random.c 1.35 vs edited =====
--- 1.35/drivers/char/random.c	Wed Aug  6 19:59:31 2003
+++ edited/drivers/char/random.c	Sat Aug 16 02:05:34 2003
@@ -711,8 +711,8 @@
 
 /* There is one of these per entropy source */
 struct timer_rand_state {
-	__u32		last_time;
-	__s32		last_delta,last_delta2;
+	cycles_t	last_time;
+	long		last_delta,last_delta2;
 	int		dont_count_entropy:1;
 };
 
@@ -729,27 +729,28 @@
  * The number "num" is also added to the pool - it should somehow describe
  * the type of event which just happened.  This is currently 0-255 for
  * keyboard scan codes, and 256 upwards for interrupts.
- * On the i386, this is assumed to be at most 16 bits, and the high bits
- * are used for a high-resolution timer.
+ * This is assumed to be at most 16 bits, and the high bits are used for
+ * high-resolution timers.
  *
  */
 static void add_timer_randomness(struct timer_rand_state *state, unsigned num)
 {
-	__u32		time;
-	__s32		delta, delta2, delta3;
+	cycles_t	time;
+	long		delta, delta2, delta3;
 	int		entropy = 0;
 
-#if defined (__i386__) || defined (__x86_64__)
-	if (cpu_has_tsc) {
-		__u32 high;
-		rdtsc(time, high);
-		num ^= high;
+	/*
+	 * Use get_cycles() if implemented, otherwise fall back to
+	 * jiffies.
+	 */
+	time = get_cycles();
+	if (time != 0) {
+		if (sizeof (time) > 4) {
+			num ^= (u32)(time >> 32);
+		}
 	} else {
 		time = jiffies;
 	}
-#else
-	time = jiffies;
-#endif
 
 	/*
 	 * Calculate number of bits of randomness we probably added.
===== include/asm-i386/timex.h 1.5 vs edited =====
--- 1.5/include/asm-i386/timex.h	Mon Jun  9 14:41:23 2003
+++ edited/include/asm-i386/timex.h	Sat Aug 16 02:17:05 2003
@@ -7,7 +7,7 @@
 #define _ASMi386_TIMEX_H
 
 #include <linux/config.h>
-#include <asm/msr.h>
+#include <asm/processor.h>
 
 #ifdef CONFIG_X86_PC9800
    extern int CLOCK_TICK_RATE;
@@ -44,14 +44,17 @@
 
 static inline cycles_t get_cycles (void)
 {
+	unsigned long long ret=0;
+
 #ifndef CONFIG_X86_TSC
-	return 0;
-#else
-	unsigned long long ret;
+	if (!cpu_has_tsc)
+		return 0;
+#endif
 
+#if defined(CONFIG_X86_GENERIC) || defined(CONFIG_X86_TSC)
 	rdtscll(ret);
-	return ret;
 #endif
+	return ret;
 }
 
 extern unsigned long cpu_khz;

Re: Using get_cycles for add_timer_randomness

[Anton Blanchard]

This sounded like a good idea at the time, any reason we cant merge
this?

Anton

On Sat, Aug 16, 2003 at 03:03:17AM +0200, Arnd Bergmann wrote:
> I noticed that only i386 and x86-64 are currently using
> a high resolution timer source when adding randomness.
> Since many architectures have a working get_cycles()
> implementation, it seems rather straightforward to use
> that.
> 
> Has this been discussed before, or can anyone comment
> on the implementation below?
> 
> This patch attempts to take into account the size of
> cycles_t, which is either 32 or 64 bits wide but
> independent of the architecture's word size.
> 
> The behavior should be nearly identical to the
> old one on i386, x86-64 and all architectures
> without a time stamp counter, while finding
> more entropy on the other architectures.
> 
> 	Arnd <><
> 
> ===== drivers/char/random.c 1.35 vs edited =====
> --- 1.35/drivers/char/random.c	Wed Aug  6 19:59:31 2003
> +++ edited/drivers/char/random.c	Sat Aug 16 02:05:34 2003
> @@ -711,8 +711,8 @@
>  
>  /* There is one of these per entropy source */
>  struct timer_rand_state {
> -	__u32		last_time;
> -	__s32		last_delta,last_delta2;
> +	cycles_t	last_time;
> +	long		last_delta,last_delta2;
>  	int		dont_count_entropy:1;
>  };
>  
> @@ -729,27 +729,28 @@
>   * The number "num" is also added to the pool - it should somehow describe
>   * the type of event which just happened.  This is currently 0-255 for
>   * keyboard scan codes, and 256 upwards for interrupts.
> - * On the i386, this is assumed to be at most 16 bits, and the high bits
> - * are used for a high-resolution timer.
> + * This is assumed to be at most 16 bits, and the high bits are used for
> + * high-resolution timers.
>   *
>   */
>  static void add_timer_randomness(struct timer_rand_state *state, unsigned num)
>  {
> -	__u32		time;
> -	__s32		delta, delta2, delta3;
> +	cycles_t	time;
> +	long		delta, delta2, delta3;
>  	int		entropy = 0;
>  
> -#if defined (__i386__) || defined (__x86_64__)
> -	if (cpu_has_tsc) {
> -		__u32 high;
> -		rdtsc(time, high);
> -		num ^= high;
> +	/*
> +	 * Use get_cycles() if implemented, otherwise fall back to
> +	 * jiffies.
> +	 */
> +	time = get_cycles();
> +	if (time != 0) {
> +		if (sizeof (time) > 4) {
> +			num ^= (u32)(time >> 32);
> +		}
>  	} else {
>  		time = jiffies;
>  	}
> -#else
> -	time = jiffies;
> -#endif
>  
>  	/*
>  	 * Calculate number of bits of randomness we probably added.
> ===== include/asm-i386/timex.h 1.5 vs edited =====
> --- 1.5/include/asm-i386/timex.h	Mon Jun  9 14:41:23 2003
> +++ edited/include/asm-i386/timex.h	Sat Aug 16 02:17:05 2003
> @@ -7,7 +7,7 @@
>  #define _ASMi386_TIMEX_H
>  
>  #include <linux/config.h>
> -#include <asm/msr.h>
> +#include <asm/processor.h>
>  
>  #ifdef CONFIG_X86_PC9800
>     extern int CLOCK_TICK_RATE;
> @@ -44,14 +44,17 @@
>  
>  static inline cycles_t get_cycles (void)
>  {
> +	unsigned long long ret=0;
> +
>  #ifndef CONFIG_X86_TSC
> -	return 0;
> -#else
> -	unsigned long long ret;
> +	if (!cpu_has_tsc)
> +		return 0;
> +#endif
>  
> +#if defined(CONFIG_X86_GENERIC) || defined(CONFIG_X86_TSC)
>  	rdtscll(ret);
> -	return ret;
>  #endif
> +	return ret;
>  }
>  
>  extern unsigned long cpu_khz;
> -
> To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
> Please read the FAQ at  http://www.tux.org/lkml/

Re: Using get_cycles for add_timer_randomness

[Anton Blanchard]

> This sounded like a good idea at the time, any reason we cant merge
> this?

Merged against latest bk. I tested how long it took to do a dd from
/dev/random on ppc64 before and after this patch, while doing a ping
flood from another machine.

before:
# /usr/bin/time dd if=/dev/random of=/dev/zero count=1k
0+51 records in
Command terminated by signal 2
0.00user 0.00system 19:18.46elapsed 0%CPU (0avgtext+0avgdata 0maxresident)k

I gave up after 19 minutes.

after:
# /usr/bin/time dd if=/dev/random of=/dev/zero count=1k
0+1024 records in
0.00user 0.00system 0:33.38elapsed 0%CPU (0avgtext+0avgdata 0maxresident)k

Just over 33 seconds. Better.

Anton

--

From: Arnd Bergmann <arnd@arndb.de>

I noticed that only i386 and x86-64 are currently using
a high resolution timer source when adding randomness.
Since many architectures have a working get_cycles()
implementation, it seems rather straightforward to use
that.

Has this been discussed before, or can anyone comment
on the implementation below?

This patch attempts to take into account the size of
cycles_t, which is either 32 or 64 bits wide but
independent of the architecture's word size.

The behavior should be nearly identical to the
old one on i386, x86-64 and all architectures
without a time stamp counter, while finding
more entropy on the other architectures.

Signed-off-by: Anton Blanchard <anton@samba.org>

===== drivers/char/random.c 1.45 vs edited =====
--- 1.45/drivers/char/random.c	Sun Aug  8 16:43:40 2004
+++ edited/drivers/char/random.c	Sun Aug 15 03:13:21 2004
@@ -781,8 +781,8 @@
 
 /* There is one of these per entropy source */
 struct timer_rand_state {
-	__u32		last_time;
-	__s32		last_delta,last_delta2;
+	cycles_t	last_time;
+	long		last_delta,last_delta2;
 	int		dont_count_entropy:1;
 };
 
@@ -799,14 +799,12 @@
  * The number "num" is also added to the pool - it should somehow describe
  * the type of event which just happened.  This is currently 0-255 for
  * keyboard scan codes, and 256 upwards for interrupts.
- * On the i386, this is assumed to be at most 16 bits, and the high bits
- * are used for a high-resolution timer.
  *
  */
 static void add_timer_randomness(struct timer_rand_state *state, unsigned num)
 {
-	__u32		time;
-	__s32		delta, delta2, delta3;
+	cycles_t	time;
+	long		delta, delta2, delta3;
 	int		entropy = 0;
 
 	/* if over the trickle threshold, use only 1 in 4096 samples */
@@ -814,17 +812,18 @@
 	     (__get_cpu_var(trickle_count)++ & 0xfff))
 		return;
 
-#if defined (__i386__) || defined (__x86_64__)
-	if (cpu_has_tsc) {
-		__u32 high;
-		rdtsc(time, high);
-		num ^= high;
+	/*
+	 * Use get_cycles() if implemented, otherwise fall back to
+	 * jiffies.
+	 */
+	time = get_cycles();
+	if (time != 0) {
+		if (sizeof(time) > 4) {
+			num ^= (u32)(time >> 32);
+		}
 	} else {
 		time = jiffies;
 	}
-#else
-	time = jiffies;
-#endif
 
 	/*
 	 * Calculate number of bits of randomness we probably added.
===== include/asm-i386/timex.h 1.7 vs edited =====
--- 1.7/include/asm-i386/timex.h	Fri Jun 18 16:43:58 2004
+++ edited/include/asm-i386/timex.h	Sun Aug 15 02:41:55 2004
@@ -7,7 +7,7 @@
 #define _ASMi386_TIMEX_H
 
 #include <linux/config.h>
-#include <asm/msr.h>
+#include <asm/processor.h>
 
 #ifdef CONFIG_X86_ELAN
 #  define CLOCK_TICK_RATE 1189200 /* AMD Elan has different frequency! */
@@ -40,14 +40,17 @@
 
 static inline cycles_t get_cycles (void)
 {
+	unsigned long long ret=0;
+
 #ifndef CONFIG_X86_TSC
-	return 0;
-#else
-	unsigned long long ret;
+	if (!cpu_has_tsc)
+		return 0;
+#endif
 
+#if defined(CONFIG_X86_GENERIC) || defined(CONFIG_X86_TSC)
 	rdtscll(ret);
-	return ret;
 #endif
+	return ret;
 }
 
 extern unsigned long cpu_khz;

Re: Using get_cycles for add_timer_randomness

[Andrew Morton]

Things have changed a bit - sparc now has special-case code in there too. 
Hopefully we can remove that now.

Is everyone OK with this?


From: Anton Blanchard <anton@samba.org>

I tested how long it took to do a dd from /dev/random on ppc64 before and
after this patch, while doing a ping flood from another machine.

before:
# /usr/bin/time dd if=/dev/random of=/dev/zero count=1k
0+51 records in
Command terminated by signal 2
0.00user 0.00system 19:18.46elapsed 0%CPU (0avgtext+0avgdata 0maxresident)k

I gave up after 19 minutes.

after:
# /usr/bin/time dd if=/dev/random of=/dev/zero count=1k
0+1024 records in
0.00user 0.00system 0:33.38elapsed 0%CPU (0avgtext+0avgdata 0maxresident)k

Just over 33 seconds. Better.

From: Arnd Bergmann <arnd@arndb.de>

I noticed that only i386 and x86-64 are currently using a high resolution
timer source when adding randomness.  Since many architectures have a
working get_cycles() implementation, it seems rather straightforward to use
that.

Has this been discussed before, or can anyone comment on the implementation
below?

This patch attempts to take into account the size of cycles_t, which is
either 32 or 64 bits wide but independent of the architecture's word size.

The behavior should be nearly identical to the old one on i386, x86-64 and
all architectures without a time stamp counter, while finding more entropy
on the other architectures.

Signed-off-by: Anton Blanchard <anton@samba.org>
Signed-off-by: Andrew Morton <akpm@osdl.org>
---

 25-akpm/drivers/char/random.c    |   31 ++++++++++++-------------------
 25-akpm/include/asm-i386/timex.h |   13 ++++++++-----
 2 files changed, 20 insertions(+), 24 deletions(-)

diff -puN drivers/char/random.c~using-get_cycles-for-add_timer_randomness drivers/char/random.c
--- 25/drivers/char/random.c~using-get_cycles-for-add_timer_randomness	2004-08-15 15:45:13.514016424 -0700
+++ 25-akpm/drivers/char/random.c	2004-08-15 15:46:14.773703536 -0700
@@ -781,8 +781,8 @@ static void batch_entropy_process(void *
 
 /* There is one of these per entropy source */
 struct timer_rand_state {
-	__u32		last_time;
-	__s32		last_delta,last_delta2;
+	cycles_t	last_time;
+	long		last_delta,last_delta2;
 	int		dont_count_entropy:1;
 };
 
@@ -799,14 +799,12 @@ static struct timer_rand_state *irq_time
  * The number "num" is also added to the pool - it should somehow describe
  * the type of event which just happened.  This is currently 0-255 for
  * keyboard scan codes, and 256 upwards for interrupts.
- * On the i386, this is assumed to be at most 16 bits, and the high bits
- * are used for a high-resolution timer.
  *
  */
 static void add_timer_randomness(struct timer_rand_state *state, unsigned num)
 {
-	__u32		time;
-	__s32		delta, delta2, delta3;
+	cycles_t	time;
+	long		delta, delta2, delta3;
 	int		entropy = 0;
 
 	/* if over the trickle threshold, use only 1 in 4096 samples */
@@ -814,22 +812,17 @@ static void add_timer_randomness(struct 
 	     (__get_cpu_var(trickle_count)++ & 0xfff))
 		return;
 
-#if defined (__i386__) || defined (__x86_64__)
-	if (cpu_has_tsc) {
-		__u32 high;
-		rdtsc(time, high);
-		num ^= high;
+	/*
+	 * Use get_cycles() if implemented, otherwise fall back to
+	 * jiffies.
+	 */
+	time = get_cycles();
+	if (time != 0) {
+		if (sizeof(time) > 4)
+			num ^= (u32)(time >> 32);
 	} else {
 		time = jiffies;
 	}
-#elif defined (__sparc_v9__)
-	unsigned long tick = tick_ops->get_tick();
-
-	time = (unsigned int) tick;
-	num ^= (tick >> 32UL);
-#else
-	time = jiffies;
-#endif
 
 	/*
 	 * Calculate number of bits of randomness we probably added.
diff -puN include/asm-i386/timex.h~using-get_cycles-for-add_timer_randomness include/asm-i386/timex.h
--- 25/include/asm-i386/timex.h~using-get_cycles-for-add_timer_randomness	2004-08-15 15:45:13.516016120 -0700
+++ 25-akpm/include/asm-i386/timex.h	2004-08-15 15:45:13.522015208 -0700
@@ -7,7 +7,7 @@
 #define _ASMi386_TIMEX_H
 
 #include <linux/config.h>
-#include <asm/msr.h>
+#include <asm/processor.h>
 
 #ifdef CONFIG_X86_ELAN
 #  define CLOCK_TICK_RATE 1189200 /* AMD Elan has different frequency! */
@@ -40,14 +40,17 @@ extern cycles_t cacheflush_time;
 
 static inline cycles_t get_cycles (void)
 {
+	unsigned long long ret=0;
+
 #ifndef CONFIG_X86_TSC
-	return 0;
-#else
-	unsigned long long ret;
+	if (!cpu_has_tsc)
+		return 0;
+#endif
 
+#if defined(CONFIG_X86_GENERIC) || defined(CONFIG_X86_TSC)
 	rdtscll(ret);
-	return ret;
 #endif
+	return ret;
 }
 
 extern unsigned long cpu_khz;
_

Re: Using get_cycles for add_timer_randomness

[Richard Mortimer]

On Sun, 2004-08-15 at 23:48, Andrew Morton wrote: 
> Things have changed a bit - sparc now has special-case code in there too. 
> Hopefully we can remove that now.
That came from Dave M & me before Anton remembered Arnd's patch. It can
be removed with the new patch applied.

> Is everyone OK with this?
I certainly am. I have tried the patch on sparc64 (albeit on 2.4.26) and
get similar results to Anton.

Richard

> 
> From: Anton Blanchard <anton@samba.org>
> 
> I tested how long it took to do a dd from /dev/random on ppc64 before and
> after this patch, while doing a ping flood from another machine.
> 
> before:
> # /usr/bin/time dd if=/dev/random of=/dev/zero count=1k
> 0+51 records in
> Command terminated by signal 2
> 0.00user 0.00system 19:18.46elapsed 0%CPU (0avgtext+0avgdata 0maxresident)k
> 
> I gave up after 19 minutes.
> 
> after:
> # /usr/bin/time dd if=/dev/random of=/dev/zero count=1k
> 0+1024 records in
> 0.00user 0.00system 0:33.38elapsed 0%CPU (0avgtext+0avgdata 0maxresident)k
> 
> Just over 33 seconds. Better.
> _

-- 
richm@oldelvet.org.uk

Re: Using get_cycles for add_timer_randomness

[David S. Miller]

On Sun, 15 Aug 2004 15:48:21 -0700
Andrew Morton <akpm@osdl.org> wrote:

> Is everyone OK with this?

I definitely am.

Re: Using get_cycles for add_timer_randomness

[Theodore Ts'o]

On Sun, Aug 15, 2004 at 03:48:21PM -0700, Andrew Morton wrote:
> From: Arnd Bergmann <arnd@arndb.de>
> 
> I noticed that only i386 and x86-64 are currently using a high resolution
> timer source when adding randomness.  Since many architectures have a
> working get_cycles() implementation, it seems rather straightforward to use
> that.

My only concern about using get_cycles is the speed question; on some
architectures, could (particularly those without TSC registers or
equivalent hardware support) could get_cycles() be slow enough to cause
latency problems?

						- Ted

Re: Using get_cycles for add_timer_randomness

[William Lee Irwin III]

At some point in the past, Arnd Bergmann <arnd@arndb.de> wrote:
>> I noticed that only i386 and x86-64 are currently using a high resolution
>> timer source when adding randomness.  Since many architectures have a
>> working get_cycles() implementation, it seems rather straightforward to use
>> that.

On Mon, Aug 16, 2004 at 12:17:56PM -0400, Theodore Ts'o wrote:
> My only concern about using get_cycles is the speed question; on some
> architectures, could (particularly those without TSC registers or
> equivalent hardware support) could get_cycles() be slow enough to cause
> latency problems?

AFAICT most of those return 0 from get_cycles().


-- wli

Re: Using get_cycles for add_timer_randomness

[Ralf Baechle]

On Mon, Aug 16, 2004 at 09:22:28AM -0700, William Lee Irwin III wrote:

> At some point in the past, Arnd Bergmann <arnd@arndb.de> wrote:
> >> I noticed that only i386 and x86-64 are currently using a high resolution
> >> timer source when adding randomness.  Since many architectures have a
> >> working get_cycles() implementation, it seems rather straightforward to use
> >> that.
> 
> On Mon, Aug 16, 2004 at 12:17:56PM -0400, Theodore Ts'o wrote:
> > My only concern about using get_cycles is the speed question; on some
> > architectures, could (particularly those without TSC registers or
> > equivalent hardware support) could get_cycles() be slow enough to cause
> > latency problems?
> 
> AFAICT most of those return 0 from get_cycles().

The cycle counter on MIPS processors [1] is only 32-bit.  I've been
pondering to construct a 64-bit value in get_cycles() which would seriously
slow down the function compared to the current single instruction
implementation; fortunately a quick survey of all get_cycles() users a
while ago did look like non of them actually requires the full 64-bit.

  Ralf

[1] Some older processors don't have at all.

Re: Using get_cycles for add_timer_randomness

[William Lee Irwin III]

On Mon, Aug 16, 2004 at 09:22:28AM -0700, William Lee Irwin III wrote:
>> AFAICT most of those return 0 from get_cycles().

On Mon, Aug 16, 2004 at 06:44:20PM +0200, Ralf Baechle wrote:
> The cycle counter on MIPS processors [1] is only 32-bit.  I've been
> pondering to construct a 64-bit value in get_cycles() which would seriously
> slow down the function compared to the current single instruction
> implementation; fortunately a quick survey of all get_cycles() users a
> while ago did look like non of them actually requires the full 64-bit.

What does it return when the 32-bit cycle counter is not present? (It was
not obvious to me; it looks like it returns whatever's in $9.)


-- wli

Re: Using get_cycles for add_timer_randomness

[Ralf Baechle]

On Mon, Aug 16, 2004 at 09:49:47AM -0700, William Lee Irwin III wrote:

> What does it return when the 32-bit cycle counter is not present? (It was
> not obvious to me; it looks like it returns whatever's in $9.)

Undefined behaviour ...

  Ralf

RE: Using get_cycles for add_timer_randomness

[Luck, Tony]

>+		if (sizeof(time) > 4)
>+			num ^= (u32)(time >> 32);

How does this bit-flipping the low-order bits based on the high
order bits of the timer help get more randomness?  It looks to
me that it will just mess up the calculation of how much randomness
you might have added. The delta/delta2/delta3 comparisons that
are done later in the function appear to be based on the idea
that you measure the `time' between events.  High order bits in
cycle counters change at quite predicatable intervals and shouldn't
take part in this calculation.

-Tony

RE: Using get_cycles for add_timer_randomness

[Luck, Tony]

>>+		if (sizeof(time) > 4)
>>+			num ^= (u32)(time >> 32);
>
>How does this bit-flipping the low-order bits based on the high
>order bits of the timer help get more randomness?  It looks to
>me that it will just mess up the calculation of how much randomness
>you might have added. The delta/delta2/delta3 comparisons that
>are done later in the function appear to be based on the idea
>that you measure the `time' between events.  High order bits in
>cycle counters change at quite predicatable intervals and shouldn't
>take part in this calculation.

So I can't read today ... I was sure that "num" said "time" when
I wrote the above ... so disregard the part about messing up
delta calculations.  But I'm still don't see how using the high
bits of the cycle counter can be a good thing.

-Tony