[PATCH] (comments requested) adding finer-grained timing to PPC add_timer_randomness()

[PATCH] (comments requested) adding finer-grained timing to PPC add_timer_randomness()

[Chris Friesen]

[-- Attachment #1: Type: text/plain, Size: 780 bytes --]


I'd like some comments on the following patch.

This patch is designed to add finer-grained timing (similar to the i386 timing)
to add_timer_randomness().  The only tricky bit is that the PPC601 doesn't
support the timebase registers.  Accordingly, I've added a flag to the PPC port
that is used to keep track of whether or not the processor supports the timebase
register.

Is there a better way to keep track of this information?  i386 has a struct with
useful information stored, but it doesn't look like PPC does.

Thanks,

Chris


-- 
Chris Friesen                    | MailStop: 043/33/F10  
Nortel Networks                  | work: (613) 765-0557
3500 Carling Avenue              | fax:  (613) 765-2986
Nepean, ON K2H 8E9 Canada        | email: cfriesen@nortelnetworks.com

[-- Attachment #2: random.patch --]
[-- Type: text/plain, Size: 2158 bytes --]

diff -ru linux-2.2.19-clean/arch/ppc/kernel/setup.c linux-2.2.19/arch/ppc/kernel/setup.c
--- linux-2.2.19-clean/arch/ppc/kernel/setup.c	Sun Mar 25 11:31:49 2001
+++ linux-2.2.19/arch/ppc/kernel/setup.c	Wed Aug 22 16:34:51 2001
@@ -103,6 +103,14 @@
 unsigned long vgacon_remap_base;
 #endif
 
+/* the PPC601 chip does not support timebase registers,
+ * so this is used to keep track of whether or not we 
+ * support them
+ */
+#ifdef CONFIG_6xx
+extern int have_timebase = 1;
+#endif /* CONFIG_6xx */
+
 /* copy of the residual data */
 #ifndef CONFIG_MBX
 unsigned char __res[sizeof(RESIDUAL)] __prepdata = {0,};
@@ -243,6 +251,7 @@
 		{
 		case 1:
 			len += sprintf(len+buffer, "601\n");
+			have_timebase = 0;
 			break;
 		case 3:
 			len += sprintf(len+buffer, "603\n");
diff -ru linux-2.2.19-clean/drivers/char/random.c linux-2.2.19/drivers/char/random.c
--- linux-2.2.19-clean/drivers/char/random.c	Sun Mar 25 11:31:25 2001
+++ linux-2.2.19/drivers/char/random.c	Wed Aug 22 16:35:34 2001
@@ -699,6 +699,7 @@
  * are used for a high-resolution timer.
  *
  */
+ 
 static void add_timer_randomness(struct random_bucket *r,
 				 struct timer_rand_state *state, unsigned num)
 {
@@ -715,6 +716,16 @@
 			:"=a" (time), "=d" (high));
 		num ^= high;
 	} else {
+		time = jiffies;
+	}
+#elif defined (CONFIG_6xx)
+	if (have_timebase) {
+		__u32 high;
+		__asm__ __volatile__("mftbu %0" : "=r" (high) : );
+		__asm__ __volatile__("mftb %0" : "=r" (time) : );
+		num ^= high;
+	}
+	else {
 		time = jiffies;
 	}
 #else
diff -ru linux-2.2.19-clean/include/asm-ppc/processor.h linux-2.2.19/include/asm-ppc/processor.h
--- linux-2.2.19-clean/include/asm-ppc/processor.h	Sun Mar 25 11:31:08 2001
+++ linux-2.2.19/include/asm-ppc/processor.h	Wed Aug 22 16:34:51 2001
@@ -216,6 +216,14 @@
 void start_thread(struct pt_regs *regs, unsigned long nip, unsigned long sp);
 void release_thread(struct task_struct *);
 
+/* the PPC601 chip does not support timebase registers,
+ * so this is used to keep track of whether or not we 
+ * support them
+ */
+#ifdef CONFIG_6xx
+extern int have_timebase;
+#endif /* CONFIG_6xx */
+
 /*
  * Create a new kernel thread.
  */

Re: [PATCH] (comments requested) adding finer-grained timing to PPC add_timer_randomness()

[Ignacio Vazquez-Abrams]

On Wed, 22 Aug 2001, Chris Friesen wrote:

> I'd like some comments on the following patch.
>
> This patch is designed to add finer-grained timing (similar to the i386 timing)
> to add_timer_randomness().  The only tricky bit is that the PPC601 doesn't
> support the timebase registers.  Accordingly, I've added a flag to the PPC port
> that is used to keep track of whether or not the processor supports the timebase
> register.
>
> Is there a better way to keep track of this information?  i386 has a struct with
> useful information stored, but it doesn't look like PPC does.
>
> Thanks,
>
> Chris

>From the patch:

--- linux-2.2.19-clean/arch/ppc/kernel/setup.c  Sun Mar 25 11:31:49 2001
+++ linux-2.2.19/arch/ppc/kernel/setup.c        Wed Aug 22 16:34:51 2001
  ...
+extern int have_timebase = 1;
  ...
--- linux-2.2.19-clean/include/asm-ppc/processor.h      Sun Mar 25 11:31:08 2001
+++ linux-2.2.19/include/asm-ppc/processor.h    Wed Aug 22 16:34:51 2001
  ...
+extern int have_timebase;
  ...

Hrmm...

Am I missing something, or should at least one of these not be extern?

-- 
Ignacio Vazquez-Abrams  <ignacio@openservices.net>

Re: [PATCH] (comments requested) adding finer-grained timing to PPC add_timer_randomness()

[Chris Friesen]

Ignacio Vazquez-Abrams wrote:

> >From the patch:
> 
> --- linux-2.2.19-clean/arch/ppc/kernel/setup.c  Sun Mar 25 11:31:49 2001
> +++ linux-2.2.19/arch/ppc/kernel/setup.c        Wed Aug 22 16:34:51 2001
>   ...
> +extern int have_timebase = 1;
>   ...
> --- linux-2.2.19-clean/include/asm-ppc/processor.h      Sun Mar 25 11:31:08 2001
> +++ linux-2.2.19/include/asm-ppc/processor.h    Wed Aug 22 16:34:51 2001
>   ...
> +extern int have_timebase;
>   ...

> Am I missing something, or should at least one of these not be extern?


Okay, I feel dumb.  You're right of course. I guess I must have missed the
compiler warning.

Chris

-- 
Chris Friesen                    | MailStop: 043/33/F10  
Nortel Networks                  | work: (613) 765-0557
3500 Carling Avenue              | fax:  (613) 765-2986
Nepean, ON K2H 8E9 Canada        | email: cfriesen@nortelnetworks.com

Re: [PATCH] (comments requested) adding finer-grained timing to PPC add_timer_randomness()

[Paul Mackerras]

Chris Friesen writes:

> > +extern int have_timebase;
> >   ...
> 
> > Am I missing something, or should at least one of these not be extern?
> 
> 
> Okay, I feel dumb.  You're right of course. I guess I must have missed the
> compiler warning.

I accidently deleted the message with the patch, but my comment would
be that the way we have tended to handle this sort of thing is by
reading the PVR register (processor version register) each time rather
than by setting a flag in memory and testing that, since I expect that
reading a special-purpose register in the CPU should be faster than
doing a load from memory.

In the 2.4 tree we have code that works out a cpu features word from
the PVR value.  The cpu features word has bits for things like does
the cpu have the TB register, does the MMU use a hash table, does the
cpu have separate I and D caches, etc.

The other thing you could consider is using the value in the
decrementer register rather than the TB or RTC.  The timer interrupt
is signalled when the DEC transitions from 0 to -1, and the DEC keeps
decrementing (at the same rate that the TB increments, on cpus which
have a TB).  I assume that the source of randomness that you are
trying to capture is the jitter in the timer (decrementer) interrupt
latency.  AFAICS you could get that from DEC just as well as from the
TB/RTC and it would have the advantage that you would not need a
conditional on the processor version.

There is a list, linuxppc-dev@lists.linuxppc.org, where you will find
a greater concentration of PPC kernel developers.  There is nothing
wrong with discussing this stuff on linux-kernel but you may perhaps
get more informed responses on linuxppc-dev. :)

Paul.

Re: [PATCH] (comments requested) adding finer-grained timing to PPC add_timer_randomness()

[Gabriel Paubert]

On Thu, 23 Aug 2001, Paul Mackerras wrote:

> Chris Friesen writes:
> 
> > > +extern int have_timebase;
> > >   ...
> > 
> > > Am I missing something, or should at least one of these not be extern?
> > 
> > 
> > Okay, I feel dumb.  You're right of course. I guess I must have missed the
> > compiler warning.
> 
> I accidently deleted the message with the patch, but my comment would
> be that the way we have tended to handle this sort of thing is by
> reading the PVR register (processor version register) each time rather
> than by setting a flag in memory and testing that, since I expect that
> reading a special-purpose register in the CPU should be faster than
> doing a load from memory.
> 
> In the 2.4 tree we have code that works out a cpu features word from
> the PVR value.  The cpu features word has bits for things like does
> the cpu have the TB register, does the MMU use a hash table, does the
> cpu have separate I and D caches, etc.

Reading the PVR is probably faster in this case, since you avoid a
potential cache miss. As I said in an earlier message the __USE_RTC macro
should be made dependent on whether the kernel supports 601 or not.


> The other thing you could consider is using the value in the
> decrementer register rather than the TB or RTC.  The timer interrupt
> is signalled when the DEC transitions from 0 to -1, and the DEC keeps
> decrementing (at the same rate that the TB increments, on cpus which
> have a TB).  I assume that the source of randomness that you are
> trying to capture is the jitter in the timer (decrementer) interrupt
> latency.  AFAICS you could get that from DEC just as well as from the
> TB/RTC and it would have the advantage that you would not need a
> conditional on the processor version.

No, this is not what they are trying to capture. Furthermore the 7 LSB of
the decrementer on a 601 are not random (but they don't seem to be 0
always despite the documentation) so you would have to shift the result
right by 7. Because you need this test, it's better taking the time base
or RTC and adding some salt from the upper half while we are at it.

	Gabriel.

Re: [PATCH] (comments requested) adding finer-grained timing to PPC add_timer_randomness()

[Benjamin Herrenschmidt]

>> In the 2.4 tree we have code that works out a cpu features word from
>> the PVR value.  The cpu features word has bits for things like does
>> the cpu have the TB register, does the MMU use a hash table, does the
>> cpu have separate I and D caches, etc.
>
>Reading the PVR is probably faster in this case, since you avoid a
>potential cache miss. As I said in an earlier message the __USE_RTC macro
>should be made dependent on whether the kernel supports 601 or not.

The CPU features will nop-out sections of code that don't apply for
a given CPU if you use the assembly macros. If you nop'out a couple
of instructions, you win over reading the PVR, masking out bits,
comparing, and doing a conditional branch.

Ben.

Re: [PATCH] (comments requested) adding finer-grained timing to PPC add_timer_randomness()

[Paul Mackerras]

Gabriel Paubert writes:

> Reading the PVR is probably faster in this case, since you avoid a
> potential cache miss.

Yep.

> As I said in an earlier message the __USE_RTC macro
> should be made dependent on whether the kernel supports 601 or not.

We don't have USE_RTC in 2.2.  The proposed patch was for 2.2.19.

> No, this is not what they are trying to capture. Furthermore the 7 LSB of
> the decrementer on a 601 are not random (but they don't seem to be 0
> always despite the documentation) so you would have to shift the result

Don't you mean that the 7 LSB of RTCL aren't random and are supposed
to be 0?  The decrementer should decrement by 1 at a rate of 7.8125MHz
and all the bits should be implemented.

Paul.

Re: [PATCH] (comments requested) adding finer-grained timing to PPC add_timer_randomness()

[Gabriel Paubert]

On Thu, 23 Aug 2001, Paul Mackerras wrote:

> Gabriel Paubert writes:
> 
> > Reading the PVR is probably faster in this case, since you avoid a
> > potential cache miss.
> 
> Yep.
> 
> > As I said in an earlier message the __USE_RTC macro
> > should be made dependent on whether the kernel supports 601 or not.
> 
> We don't have USE_RTC in 2.2.  The proposed patch was for 2.2.19.

Ok, I looked at the wrong tree in my small forest :-) My 2.2 tree has the
timing/clock changes of 2.4 since it's actually where I first wrote them
when chasing why NTP's PLL frequency error estimate varied according to
system load. Nevertheless, Chris needs something similar to USE_RTC.

> 
> > No, this is not what they are trying to capture. Furthermore the 7 LSB of
> > the decrementer on a 601 are not random (but they don't seem to be 0
> > always despite the documentation) so you would have to shift the result
> 
> Don't you mean that the 7 LSB of RTCL aren't random and are supposed
> to be 0?  The decrementer should decrement by 1 at a rate of 7.8125MHz
> and all the bits should be implemented.

No, both the RTC and the decrementer count nanoseconds, except that the 7
LSB are not implemented because the timebase clock should have a period of
128 ns (7.8125 MHz, but according to Takashi Oe, many 601 systems did not
bother to provide the exact frequency and are off by 11 parts in 4096 or
so). As such the LSB can't be used to estimate randomness and the value
must be shifted right by 7. So you need some conditional code (or boot
time patching). At this point you can throw in the high order part
(RTCU/TBU) for additional randomization (RTCU changes much faster on 601,
once per second, than on the other processors). 

Nitpicking: because RTCL wraps around at 1e9, only the 2 LSB after right
shifting have equal probabilities of being 0 or 1. The bias is probably
not that serious (provided we underestimate what people insist in calling
entropy), but I have not carefully checked its effect.

This nanosecond counting was the specification for the Power architecture.
However, once again according to Takashi, the 7 LSB of the DEC or RTC do
not always read as zeroes. Checking the 601 doc, rather fuzzy in this
area, the RTC should return 0, in the 7 LSB, but the DEC might return what
was last written). However, AFAIR Takashi found that even the RTC could
return junk in the LSB.


	Gabriel.

P.S: basic rule, on all Power/PPC processors I have seen so far: 
(RTCL or TBL) + DEC = constant (modulo wraparounds).

Re: [PATCH] (comments requested) adding finer-grained timing to PPC add_timer_randomness()

[Christopher Friesen]

Gabriel Paubert wrote:

> No, both the RTC and the decrementer count nanoseconds, except that the 7
> LSB are not implemented because the timebase clock should have a period of
> 128 ns (7.8125 MHz, but according to Takashi Oe, many 601 systems did not
> bother to provide the exact frequency and are off by 11 parts in 4096 or
> so). As such the LSB can't be used to estimate randomness and the value
> must be shifted right by 7. So you need some conditional code (or boot
> time patching). At this point you can throw in the high order part
> (RTCU/TBU) for additional randomization (RTCU changes much faster on 601,
> once per second, than on the other processors).

Have you got any links to information on boot time patching?


-- 
Chris Friesen                    | MailStop: 043/33/F10  
Nortel Networks                  | work: (613) 765-0557
3500 Carling Avenue              | fax:  (613) 765-2986
Nepean, ON K2H 8E9 Canada        | email: cfriesen@nortelnetworks.com

Re: [PATCH] (comments requested) adding finer-grained timing to PPC add_timer_randomness()

[Gabriel Paubert]

On Fri, 24 Aug 2001, Christopher Friesen wrote:

> Have you got any links to information on boot time patching?

Only works on 2.4 AFAICT. I've not followed PPC 2.2 recently, however.

	Gabriel.

Re: [PATCH] (comments requested) adding finer-grained timing to PPC

[Albert D. Cahalan]

Gabriel Paubert writes:
> On Thu, 23 Aug 2001, Paul Mackerras wrote:
>> Gabriel Paubert writes:

>>> As I said in an earlier message the __USE_RTC macro
>>> should be made dependent on whether the kernel supports 601 or not.
>>
>> We don't have USE_RTC in 2.2.  The proposed patch was for 2.2.19.
>
> Ok, I looked at the wrong tree in my small forest :-) My 2.2 tree has the
> timing/clock changes of 2.4 since it's actually where I first wrote them
> when chasing why NTP's PLL frequency error estimate varied according to
> system load. Nevertheless, Chris needs something similar to USE_RTC.
>
>>> No, this is not what they are trying to capture. Furthermore the 7 LSB of
>>> the decrementer on a 601 are not random (but they don't seem to be 0
>>> always despite the documentation) so you would have to shift the result
>>
>> Don't you mean that the 7 LSB of RTCL aren't random and are supposed
>> to be 0?  The decrementer should decrement by 1 at a rate of 7.8125MHz
>> and all the bits should be implemented.
>
> No, both the RTC and the decrementer count nanoseconds, except that the 7
> LSB are not implemented because the timebase clock should have a period of
> 128 ns (7.8125 MHz, but according to Takashi Oe, many 601 systems did not
> bother to provide the exact frequency and are off by 11 parts in 4096 or
> so). As such the LSB can't be used to estimate randomness and the value
> must be shifted right by 7. So you need some conditional code (or boot
> time patching). At this point you can throw in the high order part
> (RTCU/TBU) for additional randomization (RTCU changes much faster on 601,
> once per second, than on the other processors).

Note that you don't really need anything related to wall clock time.

You could use whatever performance counters the 601 has, if any.
That might be cache hits, cache misses, instructions dispatched,
correctly predicted branches, cycles spent waiting for a load...
The memory controller and host bridge might have useful stuff too.

You could use registers from whatever was most recently interrupted.
That might include the CR, LR, and instruction pointer. One might
exclude data from non-root user processes if being overly paranoid.