[PATCH] x86/time: fix scale_delta() inline assembly

[PATCH] x86/time: fix scale_delta() inline assembly

[Jan Beulich]

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

The way it was coded, it clobbered %rdx without telling the compiler.
This generally didn't cause any problems except when there are two back
to back invocations (as in plt_overflow()), as in that case the
compiler may validly assume that it can re-use for the second instance
the value loaded into %rdx before the first one.

Once at it, also properly relax the second operand of "mul" (there's no
need for it to be in %rdx, or a register at all), and switch away from
using explicit register names in the instruction operands.

Signed-off-by: Jan Beulich <jbeulich@suse.com>

--- a/xen/arch/x86/time.c
+++ b/xen/arch/x86/time.c
@@ -127,8 +127,9 @@ static inline u64 scale_delta(u64 delta,
         delta <<= scale->shift;
 
     asm (
-        "mul %%rdx ; shrd $32,%%rdx,%%rax"
-        : "=a" (product) : "0" (delta), "d" ((u64)scale->mul_frac) );
+        "mul %2 ; shrd $32,%1,%0"
+        : "=a" (product), "=d" (delta)
+        : "rm" (delta), "0" ((u64)scale->mul_frac) );
 
     return product;
 }




[-- Attachment #2: x86-time-scale-asm.patch --]
[-- Type: text/plain, Size: 1081 bytes --]

x86/time: fix scale_delta() inline assembly

The way it was coded, it clobbered %rdx without telling the compiler.
This generally didn't cause any problems except when there are two back
to back invocations (as in plt_overflow()), as in that case the
compiler may validly assume that it can re-use for the second instance
the value loaded into %rdx before the first one.

Once at it, also properly relax the second operand of "mul" (there's no
need for it to be in %rdx, or a register at all), and switch away from
using explicit register names in the instruction operands.

Signed-off-by: Jan Beulich <jbeulich@suse.com>

--- a/xen/arch/x86/time.c
+++ b/xen/arch/x86/time.c
@@ -127,8 +127,9 @@ static inline u64 scale_delta(u64 delta,
         delta <<= scale->shift;
 
     asm (
-        "mul %%rdx ; shrd $32,%%rdx,%%rax"
-        : "=a" (product) : "0" (delta), "d" ((u64)scale->mul_frac) );
+        "mul %2 ; shrd $32,%1,%0"
+        : "=a" (product), "=d" (delta)
+        : "rm" (delta), "0" ((u64)scale->mul_frac) );
 
     return product;
 }

[-- Attachment #3: Type: text/plain, Size: 126 bytes --]

_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xen.org
http://lists.xen.org/xen-devel

Re: [PATCH] x86/time: fix scale_delta() inline assembly

[Keir Fraser]

On 26/11/2012 15:23, "Jan Beulich" <JBeulich@suse.com> wrote:

> The way it was coded, it clobbered %rdx without telling the compiler.
> This generally didn't cause any problems except when there are two back
> to back invocations (as in plt_overflow()), as in that case the
> compiler may validly assume that it can re-use for the second instance
> the value loaded into %rdx before the first one.
> 
> Once at it, also properly relax the second operand of "mul" (there's no
> need for it to be in %rdx, or a register at all), and switch away from
> using explicit register names in the instruction operands.
> 
> Signed-off-by: Jan Beulich <jbeulich@suse.com>

Ugh. Thank you very much, Jan! What a horrible bug.

Acked-by: Keir Fraser <keir@xen.org>

> --- a/xen/arch/x86/time.c
> +++ b/xen/arch/x86/time.c
> @@ -127,8 +127,9 @@ static inline u64 scale_delta(u64 delta,
>          delta <<= scale->shift;
>  
>      asm (
> -        "mul %%rdx ; shrd $32,%%rdx,%%rax"
> -        : "=a" (product) : "0" (delta), "d" ((u64)scale->mul_frac) );
> +        "mul %2 ; shrd $32,%1,%0"
> +        : "=a" (product), "=d" (delta)
> +        : "rm" (delta), "0" ((u64)scale->mul_frac) );
>  
>      return product;
>  }
> 
> 
> 
> _______________________________________________
> Xen-devel mailing list
> Xen-devel@lists.xen.org
> http://lists.xen.org/xen-devel

Re: [PATCH] x86/time: fix scale_delta() inline assembly

[Ian Campbell]

On Mon, 2012-11-26 at 15:23 +0000, Jan Beulich wrote:
> The way it was coded, it clobbered %rdx without telling the compiler.
> This generally didn't cause any problems except when there are two back
> to back invocations (as in plt_overflow()), as in that case the
> compiler may validly assume that it can re-use for the second instance
> the value loaded into %rdx before the first one.
> 
> Once at it, also properly relax the second operand of "mul" (there's no
> need for it to be in %rdx, or a register at all), and switch away from
> using explicit register names in the instruction operands.
> 
> Signed-off-by: Jan Beulich <jbeulich@suse.com>
> 
> --- a/xen/arch/x86/time.c
> +++ b/xen/arch/x86/time.c
> @@ -127,8 +127,9 @@ static inline u64 scale_delta(u64 delta,
>          delta <<= scale->shift;
>  
>      asm (
> -        "mul %%rdx ; shrd $32,%%rdx,%%rax"
> -        : "=a" (product) : "0" (delta), "d" ((u64)scale->mul_frac) );
> +        "mul %2 ; shrd $32,%1,%0"
> +        : "=a" (product), "=d" (delta)
> +        : "rm" (delta), "0" ((u64)scale->mul_frac) );

OOI is there a reason to favour an output constraint overwriting delta,
which is then thrown away, over a straightforward clobber of rdx?

It took me ages to figure out that you had swapped which of the two
inputs to the multiply was in rax (I was very confused until I spotted
that!).

It's also a bit confusing to use %1 and %0 with the shrd since you
aren't actually using the things specified by the constraints but rather
the outputs of the mul which happen to (now) be in those registers, I'd
argue that the previous use of the explicit names was more correctly
describing what was going on. As it is I was wondering how
        shrd $32,delta,product
could possibly make sense.

Since delta is the first argument to the containing function would it be
helpful to put that in rax, where it already is due to the calling
convention? I suppose any difference is overwhelmed by the multiply
anyway.

Ian.

Re: [PATCH] x86/time: fix scale_delta() inline assembly

[Dan Magenheimer]

> From: Keir Fraser [mailto:keir@xen.org]
> Sent: Monday, November 26, 2012 9:11 AM
> To: Jan Beulich; xen-devel
> Subject: Re: [Xen-devel] [PATCH] x86/time: fix scale_delta() inline assembly
> 
> On 26/11/2012 15:23, "Jan Beulich" <JBeulich@suse.com> wrote:
> 
> > The way it was coded, it clobbered %rdx without telling the compiler.
> > This generally didn't cause any problems except when there are two back
> > to back invocations (as in plt_overflow()), as in that case the
> > compiler may validly assume that it can re-use for the second instance
> > the value loaded into %rdx before the first one.
> >
> > Once at it, also properly relax the second operand of "mul" (there's no
> > need for it to be in %rdx, or a register at all), and switch away from
> > using explicit register names in the instruction operands.
> >
> > Signed-off-by: Jan Beulich <jbeulich@suse.com>
> 
> Ugh. Thank you very much, Jan! What a horrible bug.
> 
> Acked-by: Keir Fraser <keir@xen.org>

Amazing work Jan!

Suggestion (especially since this is DOCDAY)...

Since this has caused a number of people a lot of pain
over a period of years, might it make sense to very
clearly call out the user-visible problem(s) fixed by this
in the commit message -- possibly including a few
xen-devel archive URLs and/or subject lines?  Other
than the reference to plt_overflow() (and the fact that
I've been following this thread for years), I wouldn't
have any idea from the commit message that this bug
fixes the "clock shifts by 50min" problem.

It would probably also be nice to cc the various people
who have contributed their time to provide supporting
information that helped isolate the bug.

Re: [PATCH] x86/time: fix scale_delta() inline assembly

[Jan Beulich]

>>> On 26.11.12 at 17:31, Ian Campbell <Ian.Campbell@citrix.com> wrote:
> On Mon, 2012-11-26 at 15:23 +0000, Jan Beulich wrote:
>> The way it was coded, it clobbered %rdx without telling the compiler.
>> This generally didn't cause any problems except when there are two back
>> to back invocations (as in plt_overflow()), as in that case the
>> compiler may validly assume that it can re-use for the second instance
>> the value loaded into %rdx before the first one.
>> 
>> Once at it, also properly relax the second operand of "mul" (there's no
>> need for it to be in %rdx, or a register at all), and switch away from
>> using explicit register names in the instruction operands.
>> 
>> Signed-off-by: Jan Beulich <jbeulich@suse.com>
>> 
>> --- a/xen/arch/x86/time.c
>> +++ b/xen/arch/x86/time.c
>> @@ -127,8 +127,9 @@ static inline u64 scale_delta(u64 delta,
>>          delta <<= scale->shift;
>>  
>>      asm (
>> -        "mul %%rdx ; shrd $32,%%rdx,%%rax"
>> -        : "=a" (product) : "0" (delta), "d" ((u64)scale->mul_frac) );
>> +        "mul %2 ; shrd $32,%1,%0"
>> +        : "=a" (product), "=d" (delta)
>> +        : "rm" (delta), "0" ((u64)scale->mul_frac) );
> 
> OOI is there a reason to favour an output constraint overwriting delta,
> which is then thrown away, over a straightforward clobber of rdx?

Yes - with a clobber of %rdx the compiler can't pass "delta" in that
register.

> It took me ages to figure out that you had swapped which of the two
> inputs to the multiply was in rax (I was very confused until I spotted
> that!).

Sorry. The resulting code was better (and less different from the
prior version) with the operands swapped.

> It's also a bit confusing to use %1 and %0 with the shrd since you
> aren't actually using the things specified by the constraints but rather
> the outputs of the mul which happen to (now) be in those registers, I'd
> argue that the previous use of the explicit names was more correctly
> describing what was going on. As it is I was wondering how
>         shrd $32,delta,product
> could possibly make sense.

That's how things are with multi-insn asm-s (and even with single-
insn ones when an output different from an input get tied together
through using the same register). I continue to think that using the
numbered forms here is better.

> Since delta is the first argument to the containing function would it be
> helpful to put that in rax, where it already is due to the calling
> convention? I suppose any difference is overwhelmed by the multiply
> anyway.

The first argument of a "real" function would be in %rdi. This being
an inline function, there's no calling convention anyway.

Jan

Re: [PATCH] x86/time: fix scale_delta() inline assembly

[Mats Petersson]

On 26/11/12 16:31, Ian Campbell wrote:
> On Mon, 2012-11-26 at 15:23 +0000, Jan Beulich wrote:
>> The way it was coded, it clobbered %rdx without telling the compiler.
>> This generally didn't cause any problems except when there are two back
>> to back invocations (as in plt_overflow()), as in that case the
>> compiler may validly assume that it can re-use for the second instance
>> the value loaded into %rdx before the first one.
>>
>> Once at it, also properly relax the second operand of "mul" (there's no
>> need for it to be in %rdx, or a register at all), and switch away from
>> using explicit register names in the instruction operands.
>>
>> Signed-off-by: Jan Beulich <jbeulich@suse.com>
>>
>> --- a/xen/arch/x86/time.c
>> +++ b/xen/arch/x86/time.c
>> @@ -127,8 +127,9 @@ static inline u64 scale_delta(u64 delta,
>>           delta <<= scale->shift;
>>   
>>       asm (
>> -        "mul %%rdx ; shrd $32,%%rdx,%%rax"
>> -        : "=a" (product) : "0" (delta), "d" ((u64)scale->mul_frac) );
>> +        "mul %2 ; shrd $32,%1,%0"
>> +        : "=a" (product), "=d" (delta)
>> +        : "rm" (delta), "0" ((u64)scale->mul_frac) );
> OOI is there a reason to favour an output constraint overwriting delta,
> which is then thrown away, over a straightforward clobber of rdx?
>
> It took me ages to figure out that you had swapped which of the two
> inputs to the multiply was in rax (I was very confused until I spotted
> that!).
>
> It's also a bit confusing to use %1 and %0 with the shrd since you
> aren't actually using the things specified by the constraints but rather
> the outputs of the mul which happen to (now) be in those registers, I'd
> argue that the previous use of the explicit names was more correctly
> describing what was going on. As it is I was wondering how
>          shrd $32,delta,product
> could possibly make sense.
>
> Since delta is the first argument to the containing function would it be
> helpful to put that in rax, where it already is due to the calling
> convention? I suppose any difference is overwhelmed by the multiply
> anyway.

Probably makes no difference which register is used for the input, as 
the compiler is hopefully inlining the entire function, and thus the 
register which is used as "first argument" is whatever that value 
happens to be in when the compiler gets there. This is one of many 
reasons that makes inlining more efficient - less register pressure. 
Hard-coding register usage in the assembler is a good way to "make life 
difficult for the compiler" (as it now has to make sure the value is in 
that register).

And multiply on modern processors is pretty quick - 8 clocks latency in 
the case of MUL of 64 x 64 bit number on AMD processors - I'm pretty 
sure Intel figures are similar, but not sure where to find that 
information quickly, so couldn't be bothered to look it up. The shrd 
instruction adds another 6 clocks of latency to the whole thing (again 
AMD number).

I'm not sure how many cycles you'd change the code by if the registers 
are hard-coded or compiler can choose... But not hardcoding it would be 
the better choice.

--
Mats
>
> Ian.
>
>
> _______________________________________________
> Xen-devel mailing list
> Xen-devel@lists.xen.org
> http://lists.xen.org/xen-devel
>
>

Re: [PATCH] x86/time: fix scale_delta() inline assembly

[Sylvain Munaut]

I've just deployed this to a couple test servers that exhibited the problem.

What I don't really understand is why are some HW affected and not others ?


Cheers,

    Sylvain

Re: [PATCH] x86/time: fix scale_delta() inline assembly

[Jan Beulich]

>>> On 26.11.12 at 17:43, Dan Magenheimer <dan.magenheimer@oracle.com> wrote:
> It would probably also be nice to cc the various people
> who have contributed their time to provide supporting
> information that helped isolate the bug.

That was done with the backported version that I sent
subsequently. Beyond that, I don#t think our Cc-ing rules (if we
can call them such in the first place, i.e. if they exist at all) don't
really request that. Plus - apart from the two guys I worked with
to debug this, I don't even know who else might have spent time
on it earlier on.

Jan

Re: [PATCH] x86/time: fix scale_delta() inline assembly

[Mats Petersson]

On 26/11/12 16:51, Sylvain Munaut wrote:
> I've just deployed this to a couple test servers that exhibited the problem.
>
> What I don't really understand is why are some HW affected and not others ?
I have no idea why some machines are more affected than others, but I 
can clearly see what Jan is saying, and how it will cause "weird" things 
to happen - but only if you hit the case where the calls are made in the 
right pattern, which I think is a matter of "luck". It will probably 
also matter what version of gcc is used to compile the code - different 
compiler versions will use registers in different ways.

--
Mats
>
>
> Cheers,
>
>      Sylvain
>
> _______________________________________________
> Xen-devel mailing list
> Xen-devel@lists.xen.org
> http://lists.xen.org/xen-devel
>
>

Re: [PATCH] x86/time: fix scale_delta() inline assembly

[Jan Beulich]

>>> On 26.11.12 at 17:51, Sylvain Munaut <s.munaut@whatever-company.com> wrote:
> I've just deployed this to a couple test servers that exhibited the problem.
> 
> What I don't really understand is why are some HW affected and not others ?

The multiplication is most likely to produce a zero upper half when
the multiplier is close to its smallest possible value (0x80000000);
as soon as the upper half is non-zero, chances shrink dramatically
for the warp value to be less than the current one.

Jan

Re: [PATCH] x86/time: fix scale_delta() inline assembly

[Ian Campbell]

On Mon, 2012-11-26 at 16:43 +0000, Jan Beulich wrote:
> >>> On 26.11.12 at 17:31, Ian Campbell <Ian.Campbell@citrix.com> wrote:
> > On Mon, 2012-11-26 at 15:23 +0000, Jan Beulich wrote:
> >> The way it was coded, it clobbered %rdx without telling the compiler.
> >> This generally didn't cause any problems except when there are two back
> >> to back invocations (as in plt_overflow()), as in that case the
> >> compiler may validly assume that it can re-use for the second instance
> >> the value loaded into %rdx before the first one.
> >> 
> >> Once at it, also properly relax the second operand of "mul" (there's no
> >> need for it to be in %rdx, or a register at all), and switch away from
> >> using explicit register names in the instruction operands.
> >> 
> >> Signed-off-by: Jan Beulich <jbeulich@suse.com>
> >> 
> >> --- a/xen/arch/x86/time.c
> >> +++ b/xen/arch/x86/time.c
> >> @@ -127,8 +127,9 @@ static inline u64 scale_delta(u64 delta,
> >>          delta <<= scale->shift;
> >>  
> >>      asm (
> >> -        "mul %%rdx ; shrd $32,%%rdx,%%rax"
> >> -        : "=a" (product) : "0" (delta), "d" ((u64)scale->mul_frac) );
> >> +        "mul %2 ; shrd $32,%1,%0"
> >> +        : "=a" (product), "=d" (delta)
> >> +        : "rm" (delta), "0" ((u64)scale->mul_frac) );
> > 
> > OOI is there a reason to favour an output constraint overwriting delta,
> > which is then thrown away, over a straightforward clobber of rdx?
> 
> Yes - with a clobber of %rdx the compiler can't pass "delta" in that
> register.

Ah, of course.

> > It's also a bit confusing to use %1 and %0 with the shrd since you
> > aren't actually using the things specified by the constraints but rather
> > the outputs of the mul which happen to (now) be in those registers, I'd
> > argue that the previous use of the explicit names was more correctly
> > describing what was going on. As it is I was wondering how
> >         shrd $32,delta,product
> > could possibly make sense.
> 
> That's how things are with multi-insn asm-s (and even with single-
> insn ones when an output different from an input get tied together
> through using the same register). I continue to think that using the
> numbered forms here is better.

I think the important difference here is that the mul generates its
result specifically in rdx:rax rather than user specified registers.
Since the output is not specified via the constraints IMHO using the
constraints when subsequently consuming those outputs is confusing.

I'd agree with you if mul was something like "mul %2,%0,%1" (where %2*%
rax =>%0:%1) then "shrd $32,%0,%1" would be perfectly fine.

Anyway I guess we'll have to agree to disagree. In any case your opinion
trumps mine on this code ;-)

> > Since delta is the first argument to the containing function would it be
> > helpful to put that in rax, where it already is due to the calling
> > convention? I suppose any difference is overwhelmed by the multiply
> > anyway.
> 
> The first argument of a "real" function would be in %rdi.

Oops, yes.

> This being an inline function, there's no calling convention anyway.

Right.

Ian.

Re: [PATCH] x86/time: fix scale_delta() inline assembly

[Dan Magenheimer]

> From: Sylvain Munaut [mailto:s.munaut@whatever-company.com]
> Subject: Re: [Xen-devel] [PATCH] x86/time: fix scale_delta() inline assembly
> 
> I've just deployed this to a couple test servers that exhibited the problem.
> 
> What I don't really understand is why are some HW affected and not others ?

I don't know, but I'd imagine there is something in the x86 platform
software (aka firmware) of those machines that runs and blocks execution
of Xen for long enough (via NMI/MCE/SMI) for the platform timer to
overflow, and this doesn't occur on other machines.

Maybe Jan has a better idea...

Re: [PATCH] x86/time: fix scale_delta() inline assembly

[Keir Fraser]

On 26/11/2012 17:12, "Ian Campbell" <Ian.Campbell@citrix.com> wrote:

>> That's how things are with multi-insn asm-s (and even with single-
>> insn ones when an output different from an input get tied together
>> through using the same register). I continue to think that using the
>> numbered forms here is better.
> 
> I think the important difference here is that the mul generates its
> result specifically in rdx:rax rather than user specified registers.
> Since the output is not specified via the constraints IMHO using the
> constraints when subsequently consuming those outputs is confusing.
> 
> I'd agree with you if mul was something like "mul %2,%0,%1" (where %2*%
> rax =>%0:%1) then "shrd $32,%0,%1" would be perfectly fine.
> 
> Anyway I guess we'll have to agree to disagree. In any case your opinion
> trumps mine on this code ;-)

I didn't find Jan's asm particularly confusing, any more than it kind of
fundamentally is. It's fine by me for it to go in as it is.

 -- Keir

Re: [PATCH] x86/time: fix scale_delta() inline assembly

[Keir Fraser]

On 26/11/2012 17:12, "Dan Magenheimer" <dan.magenheimer@oracle.com> wrote:

>> From: Sylvain Munaut [mailto:s.munaut@whatever-company.com]
>> Subject: Re: [Xen-devel] [PATCH] x86/time: fix scale_delta() inline assembly
>> 
>> I've just deployed this to a couple test servers that exhibited the problem.
>> 
>> What I don't really understand is why are some HW affected and not others ?
> 
> I don't know, but I'd imagine there is something in the x86 platform
> software (aka firmware) of those machines that runs and blocks execution
> of Xen for long enough (via NMI/MCE/SMI) for the platform timer to
> overflow, and this doesn't occur on other machines.

It is just luck of the draw. There is no actual platform timer overflow
happening when this bug triggers.

 -- Keir

> Maybe Jan has a better idea...