Re: rdtscp vgettimeofday

[Andrea Arcangeli]

On Mon, Dec 11, 2006 at 03:15:44PM -0800, dean gaudet wrote:
> rdtscp gets you 2 of the 5 values you need to compute the time.  anything 
> can happen between when you do the rdtscp and do the other 3 reads:  the 
> computation is (((tsc-A)*B)>>N)+C where N is a constant, and A, B, C are 
> per-cpu data.
> A/B/C change a few times a second (to avoid 32-bit rollover in (tsc-A)), 
> every time there's a halt, and every P-state transition.

This is wrong. There's the D variable too, the seq lock.

The thing I've in mind is something like:

rdstcp (get tsc and cpu atomic) this is fundamental without tsc
and cpu read atomically nothing of the below is possible

read D from cpu we got from rdtscp (seqlock)
smb_rmb()
check that D isn't during the race condition (last LSB clear
or similar) or restart
rdstcp again (tsc and cpu atomic)
check that cpu is still the same or restart
index the per-cpu array and get the safe A B C
smp_rmb()
read per-cpu D again and check that it didn't change or restart

Then you have tsc, A, B and C all atomic. N is a constant. rdtsc again
is fundamental in getting this info all atomic w/o accessing the
southbridge and without expensive asm instruction.

> if you lose your tick in the middle of those reads any number of things 
> can happen to screw the computation... including being scheduled on 
> another core and mixing values from two cores.

Being scheduled in another core is normal. continuing gettimeofday
from another core after you have the tsc value is just fine.

If something the problem is to generate A B C in per-cpu data with a
per-cpu seqlock around it. That's the job for the per-cpu kernel
thread.

The only real trouble I see is the offset from the last irq. It's
possible to make this to work we need to rotate the timer irq across
all cpus at regular intervals (before the tsc2usec measurement error
showup).

> oh i think there are several solutions which will work... and i also think 
> rdtscp wasn't a necessary addition to the ISA :)

Please don't suggest me the userland rsp manual unwinding, that's
orders of magnitude more fragile and it sounds much more complex too ;).
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to [EMAIL PROTECTED]
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

Re: rdtscp vgettimeofday

[dean gaudet]

On Mon, 11 Dec 2006, Andrea Arcangeli wrote:

> On Mon, Dec 11, 2006 at 01:17:25PM -0800, dean gaudet wrote:
> > rdtscp doesn't solve anything extra [..]
> > [..] lsl-based vgetcpu is relatively slow
> 
> Well, if you accept to run slow there's nothing to solve in the first
> place indeed.
> 
> If nothing else rdtscp should avoid the mess of restarting a
> vsyscalls, which is quite a difficult problem as it heavily depends on
> the compiler/dwarf.

rdtscp gets you 2 of the 5 values you need to compute the time.  anything 
can happen between when you do the rdtscp and do the other 3 reads:  the 
computation is (((tsc-A)*B)>>N)+C where N is a constant, and A, B, C are 
per-cpu data.

A/B/C change a few times a second (to avoid 32-bit rollover in (tsc-A)), 
every time there's a halt, and every P-state transition.

if you lose your tick in the middle of those reads any number of things 
can happen to screw the computation... including being scheduled on 
another core and mixing values from two cores.


> > even with rdtscp you have to deal with the definite possibility of being 
> > scheduled away in the middle of the computation.  arguably you need
> > to 
> 
> Isn't rdtscp atomic? all you need is to read atomically the current
> contents of the tsc and the index to use in a per-cpu table exported
> in readonly. This table will contain a per-cpu seqlock as well. Then a
> math logic has to be built with per-cpu threads, so that those per-cpu
> tables are updated by cpufreq and at regular intervals.
> 
> If this is all wrong and it's not feasible to implement a safe and
> monothonic vgettimeofday that doesn't access the southbridge and that
> doesn't require restarting the vsyscall manually by patching rip/rsp,
> I've an hard time to see how rdtscp is useful at all. I hope somebody
> thought about those issues before adding a new instruction to a
> popular CPU ;).

oh i think there are several solutions which will work... and i also think 
rdtscp wasn't a necessary addition to the ISA :)

-dean
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to [EMAIL PROTECTED]
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

Re: rdtscp vgettimeofday

[Andrea Arcangeli]

On Mon, Dec 11, 2006 at 01:17:25PM -0800, dean gaudet wrote:
> rdtscp doesn't solve anything extra [..]
> [..] lsl-based vgetcpu is relatively slow

Well, if you accept to run slow there's nothing to solve in the first
place indeed.

If nothing else rdtscp should avoid the mess of restarting a
vsyscalls, which is quite a difficult problem as it heavily depends on
the compiler/dwarf.

> even with rdtscp you have to deal with the definite possibility of being 
> scheduled away in the middle of the computation.  arguably you need
> to 

Isn't rdtscp atomic? all you need is to read atomically the current
contents of the tsc and the index to use in a per-cpu table exported
in readonly. This table will contain a per-cpu seqlock as well. Then a
math logic has to be built with per-cpu threads, so that those per-cpu
tables are updated by cpufreq and at regular intervals.

If this is all wrong and it's not feasible to implement a safe and
monothonic vgettimeofday that doesn't access the southbridge and that
doesn't require restarting the vsyscall manually by patching rip/rsp,
I've an hard time to see how rdtscp is useful at all. I hope somebody
thought about those issues before adding a new instruction to a
popular CPU ;).
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to [EMAIL PROTECTED]
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

Re: rdtscp vgettimeofday

[dean gaudet]

On Mon, 11 Dec 2006, Andrea Arcangeli wrote:

> As far as I can see, many changes happened but nobody has yet added
> the rdtscp support to x86-64. rdtscp finally solves the problem and it
> obsoletes hpet for timekeeping and it allows a fully userland
> gettimeofday running at maximum speed in userland.

rdtscp doesn't solve anything extra which can't already be solved with 
existing vgetcpu (based on lsl) and rdtsc.  which have the advantage of 
working on all x86, not just the (currently) rare revF opteron.

lsl-based vgetcpu is relatively slow (because it is a protected 
instruction with lots of microcode) -- but there are other options which 
continue to work on all x86 (see ).


> Before rdtscp we could never index the rdtsc offset in a proper index
> without being in kernel with preemption disabled, so it could never
> work reliably.

even with rdtscp you have to deal with the definite possibility of being 
scheduled away in the middle of the computation.  arguably you need to 
deal with the possibility of being scheduled away *and* back again to the 
same cpu (so testing cpu# at top and bottom of a loop isn't sufficient).

suleiman proposed a per-cpu scheduling event number to deal with that... 
not sure what folks think of that idea.

-dean
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to [EMAIL PROTECTED]
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

Re: rdtscp vgettimeofday

[dean gaudet]

On Mon, 11 Dec 2006, Andrea Arcangeli wrote:

 As far as I can see, many changes happened but nobody has yet added
 the rdtscp support to x86-64. rdtscp finally solves the problem and it
 obsoletes hpet for timekeeping and it allows a fully userland
 gettimeofday running at maximum speed in userland.

rdtscp doesn't solve anything extra which can't already be solved with 
existing vgetcpu (based on lsl) and rdtsc.  which have the advantage of 
working on all x86, not just the (currently) rare revF opteron.

lsl-based vgetcpu is relatively slow (because it is a protected 
instruction with lots of microcode) -- but there are other options which 
continue to work on all x86 (see http://lkml.org/lkml/2006/11/13/401).


 Before rdtscp we could never index the rdtsc offset in a proper index
 without being in kernel with preemption disabled, so it could never
 work reliably.

even with rdtscp you have to deal with the definite possibility of being 
scheduled away in the middle of the computation.  arguably you need to 
deal with the possibility of being scheduled away *and* back again to the 
same cpu (so testing cpu# at top and bottom of a loop isn't sufficient).

suleiman proposed a per-cpu scheduling event number to deal with that... 
not sure what folks think of that idea.

-dean
-
To unsubscribe from this list: send the line unsubscribe linux-kernel in
the body of a message to [EMAIL PROTECTED]
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

Re: rdtscp vgettimeofday

[Andrea Arcangeli]

On Mon, Dec 11, 2006 at 01:17:25PM -0800, dean gaudet wrote:
 rdtscp doesn't solve anything extra [..]
 [..] lsl-based vgetcpu is relatively slow

Well, if you accept to run slow there's nothing to solve in the first
place indeed.

If nothing else rdtscp should avoid the mess of restarting a
vsyscalls, which is quite a difficult problem as it heavily depends on
the compiler/dwarf.

 even with rdtscp you have to deal with the definite possibility of being 
 scheduled away in the middle of the computation.  arguably you need
 to 

Isn't rdtscp atomic? all you need is to read atomically the current
contents of the tsc and the index to use in a per-cpu table exported
in readonly. This table will contain a per-cpu seqlock as well. Then a
math logic has to be built with per-cpu threads, so that those per-cpu
tables are updated by cpufreq and at regular intervals.

If this is all wrong and it's not feasible to implement a safe and
monothonic vgettimeofday that doesn't access the southbridge and that
doesn't require restarting the vsyscall manually by patching rip/rsp,
I've an hard time to see how rdtscp is useful at all. I hope somebody
thought about those issues before adding a new instruction to a
popular CPU ;).
-
To unsubscribe from this list: send the line unsubscribe linux-kernel in
the body of a message to [EMAIL PROTECTED]
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

Re: rdtscp vgettimeofday

[dean gaudet]

On Mon, 11 Dec 2006, Andrea Arcangeli wrote:

 On Mon, Dec 11, 2006 at 01:17:25PM -0800, dean gaudet wrote:
  rdtscp doesn't solve anything extra [..]
  [..] lsl-based vgetcpu is relatively slow
 
 Well, if you accept to run slow there's nothing to solve in the first
 place indeed.
 
 If nothing else rdtscp should avoid the mess of restarting a
 vsyscalls, which is quite a difficult problem as it heavily depends on
 the compiler/dwarf.

rdtscp gets you 2 of the 5 values you need to compute the time.  anything 
can happen between when you do the rdtscp and do the other 3 reads:  the 
computation is (((tsc-A)*B)N)+C where N is a constant, and A, B, C are 
per-cpu data.

A/B/C change a few times a second (to avoid 32-bit rollover in (tsc-A)), 
every time there's a halt, and every P-state transition.

if you lose your tick in the middle of those reads any number of things 
can happen to screw the computation... including being scheduled on 
another core and mixing values from two cores.


  even with rdtscp you have to deal with the definite possibility of being 
  scheduled away in the middle of the computation.  arguably you need
  to 
 
 Isn't rdtscp atomic? all you need is to read atomically the current
 contents of the tsc and the index to use in a per-cpu table exported
 in readonly. This table will contain a per-cpu seqlock as well. Then a
 math logic has to be built with per-cpu threads, so that those per-cpu
 tables are updated by cpufreq and at regular intervals.
 
 If this is all wrong and it's not feasible to implement a safe and
 monothonic vgettimeofday that doesn't access the southbridge and that
 doesn't require restarting the vsyscall manually by patching rip/rsp,
 I've an hard time to see how rdtscp is useful at all. I hope somebody
 thought about those issues before adding a new instruction to a
 popular CPU ;).

oh i think there are several solutions which will work... and i also think 
rdtscp wasn't a necessary addition to the ISA :)

-dean
-
To unsubscribe from this list: send the line unsubscribe linux-kernel in
the body of a message to [EMAIL PROTECTED]
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

Re: rdtscp vgettimeofday

[Andrea Arcangeli]

On Mon, Dec 11, 2006 at 03:15:44PM -0800, dean gaudet wrote:
 rdtscp gets you 2 of the 5 values you need to compute the time.  anything 
 can happen between when you do the rdtscp and do the other 3 reads:  the 
 computation is (((tsc-A)*B)N)+C where N is a constant, and A, B, C are 
 per-cpu data.
 A/B/C change a few times a second (to avoid 32-bit rollover in (tsc-A)), 
 every time there's a halt, and every P-state transition.

This is wrong. There's the D variable too, the seq lock.

The thing I've in mind is something like:

rdstcp (get tsc and cpu atomic) this is fundamental without tsc
and cpu read atomically nothing of the below is possible

read D from cpu we got from rdtscp (seqlock)
smb_rmb()
check that D isn't during the race condition (last LSB clear
or similar) or restart
rdstcp again (tsc and cpu atomic)
check that cpu is still the same or restart
index the per-cpu array and get the safe A B C
smp_rmb()
read per-cpu D again and check that it didn't change or restart

Then you have tsc, A, B and C all atomic. N is a constant. rdtsc again
is fundamental in getting this info all atomic w/o accessing the
southbridge and without expensive asm instruction.

 if you lose your tick in the middle of those reads any number of things 
 can happen to screw the computation... including being scheduled on 
 another core and mixing values from two cores.

Being scheduled in another core is normal. continuing gettimeofday
from another core after you have the tsc value is just fine.

If something the problem is to generate A B C in per-cpu data with a
per-cpu seqlock around it. That's the job for the per-cpu kernel
thread.

The only real trouble I see is the offset from the last irq. It's
possible to make this to work we need to rotate the timer irq across
all cpus at regular intervals (before the tsc2usec measurement error
showup).

 oh i think there are several solutions which will work... and i also think 
 rdtscp wasn't a necessary addition to the ISA :)

Please don't suggest me the userland rsp manual unwinding, that's
orders of magnitude more fragile and it sounds much more complex too ;).
-
To unsubscribe from this list: send the line unsubscribe linux-kernel in
the body of a message to [EMAIL PROTECTED]
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/