2010-08-27 13:37:06

by Petr Tesařík

[permalink] [raw]
Subject: Serious problem with ticket spinlocks on ia64

Hi everybody,

SGI has recently experienced failures with the new ticket spinlock
implementation. Hedi Berriche sent me a simple test case that can
trigger the failure on the siglock. To debug the issue, I wrote a
small module that watches writes to current->sighand->siglock and
records the values.

I observed that the __ticket_spin_lock() primitive fails when the
tail wraps around to zero. I reconstructed the following:

CPU 7 holds the spinlock
CPU 5 wants to acquire the spinlock
Spinlock value is 0xfffcffff
(now serving 0x7fffe, next ticket 0x7ffff)

CPU 7 executes st2.rel to release the spinlock.
At the same time CPU 5 executes a fetchadd4.acq.
The resulting lock value is 0xfffe0000 (correct), and CPU 5 has
recorded its ticket number (0x7fff).

Consequently, the first spinlock loop iteration succeeds, and CPU 5
now holds the spinlock.

Next, CPU 5 releases the spinlock with st2.rel, changing the lock
value to 0x0 (correct).

SO FAR SO GOOD.

Now, CPU 4, CPU 5 and CPU 7 all want to acquire the lock again.
Interestingly, CPU 5 and CPU 7 are both granted the same ticket,
and the spinlock value (as seen from the debug fault handler) is
0x0 after single-stepping over the fetchadd4.acq, in both cases.
CPU 4 correctly sets the spinlock value to 0x1.

I don't know if the simultaneos acquire attempt and release are
necessary to trigger the bug, but I noted it here.

I've only seen this happen when the spinlock wraps around to zero,
but I don't know whether it cannot happen otherwise.

In any case, there seems to be a serious problem with memory
ordering, and I'm not an expert to tell exactly what it is.

Any ideas?

Petr Tesarik
L3 International
Novell, Inc.


2010-08-27 13:48:45

by Hedi Berriche

[permalink] [raw]
Subject: Re: Serious problem with ticket spinlocks on ia64

On Fri, Aug 27, 2010 at 14:38 Petr Tesarik wrote:
| Hi everybody,
|
| SGI has recently experienced failures with the new ticket spinlock
| implementation. Hedi Berriche sent me a simple test case that can
| trigger the failure on the siglock.

One more fact, the problem was introduced by commit

commit 9d40ee200a527ce08ab8c793ba8ae3e242edbb0e
Author: Tony Luck <[email protected]>
Date: Wed Oct 7 10:54:19 2009 -0700

[IA64] Squeeze ticket locks back into 4 bytes.

Reverting the patch makes the problem go away.

IOW, and as far as testing shows, the first incarnation of the ticket locks
implementation on IA64 (commit 2c8696), the one that used 8 bytes, does not
exhibit this problem.

Cheers,
Hedi.
--
Hedi Berriche
Global Product Support
http://www.sgi.com/support

2010-08-27 14:08:45

by Petr Tesařík

[permalink] [raw]
Subject: Re: Serious problem with ticket spinlocks on ia64

On Friday 27 of August 2010 15:48:02 Hedi Berriche wrote:
> On Fri, Aug 27, 2010 at 14:38 Petr Tesarik wrote:
> | Hi everybody,
> |
> | SGI has recently experienced failures with the new ticket spinlock
> | implementation. Hedi Berriche sent me a simple test case that can
> | trigger the failure on the siglock.
>
> One more fact, the problem was introduced by commit
>
> commit 9d40ee200a527ce08ab8c793ba8ae3e242edbb0e
> Author: Tony Luck <[email protected]>
> Date: Wed Oct 7 10:54:19 2009 -0700
>
> [IA64] Squeeze ticket locks back into 4 bytes.
>
> Reverting the patch makes the problem go away.
>
> IOW, and as far as testing shows, the first incarnation of the ticket locks
> implementation on IA64 (commit 2c8696), the one that used 8 bytes, does not
> exhibit this problem.

I wouldn't be so sure about it. Given that I have only observed the problem
when the spinlock value wraps around, then an 8-byte spinlock might only need
much more time to trigger the bug.

Just my two cents,
Petr Tesarik
L3 International
Novell, Inc.

2010-08-27 14:31:47

by Hedi Berriche

[permalink] [raw]
Subject: Re: Serious problem with ticket spinlocks on ia64

On Fri, Aug 27, 2010 at 15:09 Petr Tesarik wrote:
| On Friday 27 of August 2010 15:48:02 Hedi Berriche wrote:
|
| > One more fact, the problem was introduced by commit
| >
| > commit 9d40ee200a527ce08ab8c793ba8ae3e242edbb0e
| > Author: Tony Luck <[email protected]>
| > Date: Wed Oct 7 10:54:19 2009 -0700
| >
| > [IA64] Squeeze ticket locks back into 4 bytes.
| >
| > Reverting the patch makes the problem go away.
| >
| > IOW, and as far as testing shows, the first incarnation of the ticket locks
| > implementation on IA64 (commit 2c8696), the one that used 8 bytes, does not
| > exhibit this problem.
|
| I wouldn't be so sure about it. Given that I have only observed the problem
| when the spinlock value wraps around, then an 8-byte spinlock might only need
| much more time to trigger the bug.

That's a possibility and that's why I said "as far as testing shows".

That said, I'm letting my already over 36 hours run carry on chewing CPU
time, and see if it will eventually trip the same problem seen with 4-byte
ticket locks.

Cheers,
Hedi.
--
Hedi Berriche
Global Product Support
http://www.sgi.com/support

2010-08-27 14:40:20

by Petr Tesařík

[permalink] [raw]
Subject: Re: Serious problem with ticket spinlocks on ia64

On Friday 27 of August 2010 16:31:35 Hedi Berriche wrote:
> On Fri, Aug 27, 2010 at 15:09 Petr Tesarik wrote:
> | On Friday 27 of August 2010 15:48:02 Hedi Berriche wrote:
> | > One more fact, the problem was introduced by commit
> | >
> | > commit 9d40ee200a527ce08ab8c793ba8ae3e242edbb0e
> | > Author: Tony Luck <[email protected]>
> | > Date: Wed Oct 7 10:54:19 2009 -0700
> | >
> | > [IA64] Squeeze ticket locks back into 4 bytes.
> | >
> | > Reverting the patch makes the problem go away.
> | >
> | > IOW, and as far as testing shows, the first incarnation of the ticket
> | > locks implementation on IA64 (commit 2c8696), the one that used 8
> | > bytes, does not exhibit this problem.
> |
> | I wouldn't be so sure about it. Given that I have only observed the
> | problem when the spinlock value wraps around, then an 8-byte spinlock
> | might only need much more time to trigger the bug.
>
> That's a possibility and that's why I said "as far as testing shows".
>
> That said, I'm letting my already over 36 hours run carry on chewing CPU
> time, and see if it will eventually trip the same problem seen with 4-byte
> ticket locks.

Hm, this doesn't sound like a viable approach. Since the siglock gets
initialized to 0 when a new process is started, it may never actually wrap
around.

I would rather attach a SystemTap probe somewhere during process fork and add
a bias to the siglock. That should work fine. Let me knock up the SystemTap
script...

Petr

2010-08-27 14:52:45

by Hedi Berriche

[permalink] [raw]
Subject: Re: Serious problem with ticket spinlocks on ia64

On Fri, Aug 27, 2010 at 15:40 Petr Tesarik wrote:
| On Friday 27 of August 2010 16:31:35 Hedi Berriche wrote:
|
| > That said, I'm letting my already over 36 hours run carry on chewing CPU
| > time, and see if it will eventually trip the same problem seen with 4-byte
| > ticket locks.
|
| Hm, this doesn't sound like a viable approach. Since the siglock gets
| initialized to 0 when a new process is started, it may never actually wrap
| around.
|
| I would rather attach a SystemTap probe somewhere during process fork and add
| a bias to the siglock. That should work fine. Let me knock up the SystemTap
| script...

That would be nice. Ta!

Cheers,
Hedi.
--
Hedi Berriche
Global Product Support
http://www.sgi.com/support

2010-08-27 16:08:08

by Luck, Tony

[permalink] [raw]
Subject: RE: Serious problem with ticket spinlocks on ia64

> Hedi Berriche sent me a simple test case that can
> trigger the failure on the siglock.

Can you post the test case please. How long does it typically take
to reproduce the problem?


> Next, CPU 5 releases the spinlock with st2.rel, changing the lock
> value to 0x0 (correct).
>
> SO FAR SO GOOD.
>
> Now, CPU 4, CPU 5 and CPU 7 all want to acquire the lock again.
> Interestingly, CPU 5 and CPU 7 are both granted the same ticket,

What is the duplicate ticket number that CPUs 5 & 7 get at this point?
Presumably 0x0, yes? Or do they see a stale 0x7fff?

> and the spinlock value (as seen from the debug fault handler) is
> 0x0 after single-stepping over the fetchadd4.acq, in both cases.
> CPU 4 correctly sets the spinlock value to 0x1.

Is the fault handler using "ld.acq" to look at the spinlock value?
If not, then this might be a red herring. [Though clearly something
bad is going on here].

> Any ideas?

What cpu model are you running on?
What is the topological connection between CPU 4, 5 and 7 - are any of
them hyper-threaded siblings? Cores on same socket? N.B. topology may
change from boot to boot, so you may need to capture /proc/cpuinfo from
the same boot where this problem is detected. But the variation is
usually limited to which socket gets to own logical cpu 0.

If this is a memory ordering problem (and that seems quite plausible)
then a liberal sprinkling of "ia64_mf()" calls throughout the spinlock
routines would probably make it go away.

-Tony

2010-08-27 16:36:39

by Petr Tesařík

[permalink] [raw]
Subject: Re: Serious problem with ticket spinlocks on ia64

On Friday 27 of August 2010 16:52:31 Hedi Berriche wrote:
> On Fri, Aug 27, 2010 at 15:40 Petr Tesarik wrote:
> | On Friday 27 of August 2010 16:31:35 Hedi Berriche wrote:
> | > That said, I'm letting my already over 36 hours run carry on chewing
> | > CPU time, and see if it will eventually trip the same problem seen with
> | > 4-byte ticket locks.
> |
> | Hm, this doesn't sound like a viable approach. Since the siglock gets
> | initialized to 0 when a new process is started, it may never actually
> | wrap around.
> |
> | I would rather attach a SystemTap probe somewhere during process fork and
> | add a bias to the siglock. That should work fine. Let me knock up the
> | SystemTap script...
>
> That would be nice. Ta!

Here it is. I don't have a system with the old 64-bit ticket spinlocks at
hand, so this is completely untested, but it should work fine.

Adjust if needed.

Petr


Attachments:
(No filename) (893.00 B)
biaslock.stp (455.00 B)
Download all attachments

2010-08-27 17:16:00

by Petr Tesařík

[permalink] [raw]
Subject: Re: Serious problem with ticket spinlocks on ia64

On Friday 27 of August 2010 18:08:03 Luck, Tony wrote:
> > Hedi Berriche sent me a simple test case that can
> > trigger the failure on the siglock.
>
> Can you post the test case please. How long does it typically take
> to reproduce the problem?

I let Hedi send it. It's really easy to reproduce. In fact, I can reproduce it
within 5 minutes on an 8-CPU system.

> > Next, CPU 5 releases the spinlock with st2.rel, changing the lock
> > value to 0x0 (correct).
> >
> > SO FAR SO GOOD.
> >
> > Now, CPU 4, CPU 5 and CPU 7 all want to acquire the lock again.
> > Interestingly, CPU 5 and CPU 7 are both granted the same ticket,
>
> What is the duplicate ticket number that CPUs 5 & 7 get at this point?
> Presumably 0x0, yes? Or do they see a stale 0x7fff?

They get a zero, yes.
> > and the spinlock value (as seen from the debug fault handler) is
> > 0x0 after single-stepping over the fetchadd4.acq, in both cases.
> > CPU 4 correctly sets the spinlock value to 0x1.
>
> Is the fault handler using "ld.acq" to look at the spinlock value?
> If not, then this might be a red herring. [Though clearly something
> bad is going on here].

Right. I also realized I was reading the spinlock value with a plain "ld4".
When I changed it to "ld4.acq", this is what happens:

1. We're in _spin_lock_irq, which starts like this:

0xa0000001008ea000 <_spin_lock_irq>: [MMI] rsm 0x4000;;
0xa0000001008ea001 <_spin_lock_irq+1>: fetchadd4.acq r15=[r32],1
0xa0000001008ea002 <_spin_lock_irq+2>: nop.i 0x0;;

AFAICS the spinlock value should be 0x0 (after having wrapped around from
0xffff0000 at release on the same CPU).

2. fetchadd4.acq generates a debug exception (because it writes to the watched
location)
3. ld4.acq inside the debug fault handler reads 0x0 from the location
4. the handler sets PSR.ss on return
5. fetchadd4.acq puts 0x1 (why?) in r15 and generates a Single step fault
6. the fault handler now reads 0x0 (sic!) from the spinlock location (again,
using ld4.acq)
7. the resulting kernel crash dump contains ZERO in the spinlock location

Maybe, there's something wrong with my test module, because I'm already
getting tired today, but there's definitely something wrong here. I'll try to
polish it and send here later.

> > Any ideas?
>
> What cpu model are you running on?
> What is the topological connection between CPU 4, 5 and 7 - are any of
> them hyper-threaded siblings? Cores on same socket? N.B. topology may
> change from boot to boot, so you may need to capture /proc/cpuinfo from
> the same boot where this problem is detected. But the variation is
> usually limited to which socket gets to own logical cpu 0.

There are two Dual-Core Intel(R) Itanium(R) 2 Processor 9150M in the test
machine:

physical package 0
core 0: CPU 0, CPU 4
core 1: CPU 2, CPU 6

physical package 196611
core 0: CPU 1, CPU 5
core 1: CPU 3, CPU 7

/proc/cpuinfo says:

processor : 0
vendor : GenuineIntel
arch : IA-64
family : 32
model : 1
model name : Dual-Core Intel(R) Itanium(R) 2 Processor 9150M
revision : 1
archrev : 0
features : branchlong, 16-byte atomic ops
cpu number : 0
cpu regs : 4
cpu MHz : 1668.672
itc MHz : 416.667500
BogoMIPS : 1662.97
siblings : 4
physical id: 0
core id : 0
thread id : 0

processor : 1
vendor : GenuineIntel
arch : IA-64
family : 32
model : 1
model name : Dual-Core Intel(R) Itanium(R) 2 Processor 9150M
revision : 1
archrev : 0
features : branchlong, 16-byte atomic ops
cpu number : 0
cpu regs : 4
cpu MHz : 1668.672
itc MHz : 416.667500
BogoMIPS : 1662.97
siblings : 4
physical id: 196611
core id : 0
thread id : 0

processor : 2
vendor : GenuineIntel
arch : IA-64
family : 32
model : 1
model name : Dual-Core Intel(R) Itanium(R) 2 Processor 9150M
revision : 1
archrev : 0
features : branchlong, 16-byte atomic ops
cpu number : 0
cpu regs : 4
cpu MHz : 1668.672
itc MHz : 416.667500
BogoMIPS : 1662.97
siblings : 4
physical id: 0
core id : 1
thread id : 0

processor : 3
vendor : GenuineIntel
arch : IA-64
family : 32
model : 1
model name : Dual-Core Intel(R) Itanium(R) 2 Processor 9150M
revision : 1
archrev : 0
features : branchlong, 16-byte atomic ops
cpu number : 0
cpu regs : 4
cpu MHz : 1668.672
itc MHz : 416.667500
BogoMIPS : 1662.97
siblings : 4
physical id: 196611
core id : 1
thread id : 0

processor : 4
vendor : GenuineIntel
arch : IA-64
family : 32
model : 1
model name : Dual-Core Intel(R) Itanium(R) 2 Processor 9150M
revision : 1
archrev : 0
features : branchlong, 16-byte atomic ops
cpu number : 0
cpu regs : 4
cpu MHz : 1668.672
itc MHz : 416.667500
BogoMIPS : 1662.97
siblings : 4
physical id: 0
core id : 0
thread id : 1

processor : 5
vendor : GenuineIntel
arch : IA-64
family : 32
model : 1
model name : Dual-Core Intel(R) Itanium(R) 2 Processor 9150M
revision : 1
archrev : 0
features : branchlong, 16-byte atomic ops
cpu number : 0
cpu regs : 4
cpu MHz : 1668.672
itc MHz : 416.667500
BogoMIPS : 1662.97
siblings : 4
physical id: 196611
core id : 0
thread id : 1

processor : 6
vendor : GenuineIntel
arch : IA-64
family : 32
model : 1
model name : Dual-Core Intel(R) Itanium(R) 2 Processor 9150M
revision : 1
archrev : 0
features : branchlong, 16-byte atomic ops
cpu number : 0
cpu regs : 4
cpu MHz : 1668.672
itc MHz : 416.667500
BogoMIPS : 1662.97
siblings : 4
physical id: 0
core id : 1
thread id : 1

processor : 7
vendor : GenuineIntel
arch : IA-64
family : 32
model : 1
model name : Dual-Core Intel(R) Itanium(R) 2 Processor 9150M
revision : 1
archrev : 0
features : branchlong, 16-byte atomic ops
cpu number : 0
cpu regs : 4
cpu MHz : 1668.672
itc MHz : 416.667500
BogoMIPS : 1662.97
siblings : 4
physical id: 196611
core id : 1
thread id : 1

Petr Tesarik

2010-08-27 18:20:50

by Hedi Berriche

[permalink] [raw]
Subject: Re: Serious problem with ticket spinlocks on ia64

On Fri, Aug 27, 2010 at 18:16 Petr Tesarik wrote:
| On Friday 27 of August 2010 18:08:03 Luck, Tony wrote:
| > > Hedi Berriche sent me a simple test case that can
| > > trigger the failure on the siglock.
| >
| > Can you post the test case please. How long does it typically take
| > to reproduce the problem?
|
| I let Hedi send it. It's really easy to reproduce. In fact, I can reproduce it
| within 5 minutes on an 8-CPU system.

Test case provided via private email.

Cheers,
Hedi.
--
Hedi Berriche
Global Product Support
http://www.sgi.com/support

2010-08-27 19:40:11

by Petr Tesařík

[permalink] [raw]
Subject: Re: Serious problem with ticket spinlocks on ia64

On Friday 27 of August 2010 19:16:29 Petr Tesarik wrote:
> On Friday 27 of August 2010 18:08:03 Luck, Tony wrote:
> > > Hedi Berriche sent me a simple test case that can
> > > trigger the failure on the siglock.
> >
> > Can you post the test case please. How long does it typically take
> > to reproduce the problem?
>
> I let Hedi send it. It's really easy to reproduce. In fact, I can reproduce
> it within 5 minutes on an 8-CPU system.
>
> > > Next, CPU 5 releases the spinlock with st2.rel, changing the lock
> > > value to 0x0 (correct).
> > >
> > > SO FAR SO GOOD.
> > >
> > > Now, CPU 4, CPU 5 and CPU 7 all want to acquire the lock again.
> > > Interestingly, CPU 5 and CPU 7 are both granted the same ticket,
> >
> > What is the duplicate ticket number that CPUs 5 & 7 get at this point?
> > Presumably 0x0, yes? Or do they see a stale 0x7fff?
>
> They get a zero, yes.
>
> > > and the spinlock value (as seen from the debug fault handler) is
> > > 0x0 after single-stepping over the fetchadd4.acq, in both cases.
> > > CPU 4 correctly sets the spinlock value to 0x1.
> >
> > Is the fault handler using "ld.acq" to look at the spinlock value?
> > If not, then this might be a red herring. [Though clearly something
> > bad is going on here].
>
> Right. I also realized I was reading the spinlock value with a plain "ld4".
> When I changed it to "ld4.acq", this is what happens:
>
> 1. We're in _spin_lock_irq, which starts like this:
>
> 0xa0000001008ea000 <_spin_lock_irq>: [MMI] rsm 0x4000;;
> 0xa0000001008ea001 <_spin_lock_irq+1>: fetchadd4.acq
> r15=[r32],1 0xa0000001008ea002 <_spin_lock_irq+2>: nop.i 0x0;;
>
> AFAICS the spinlock value should be 0x0 (after having wrapped around from
> 0xffff0000 at release on the same CPU).
>
> 2. fetchadd4.acq generates a debug exception (because it writes to the
> watched location)
> 3. ld4.acq inside the debug fault handler reads 0x0 from the location
> 4. the handler sets PSR.ss on return
> 5. fetchadd4.acq puts 0x1 (why?) in r15 and generates a Single step fault
> 6. the fault handler now reads 0x0 (sic!) from the spinlock location
> (again, using ld4.acq)
> 7. the resulting kernel crash dump contains ZERO in the spinlock location

I have another crash dump which recorded the same values in the debug fault
handler, but the resulting crash dump contains 0x1 (not 0x0) in the spinlock.
R15 was still 0x1 (even though it should contain the original value, not the
incremented one, shouldn't it?).

Petr Tesarik

2010-08-27 20:29:49

by Luck, Tony

[permalink] [raw]
Subject: RE: Serious problem with ticket spinlocks on ia64

> If this is a memory ordering problem (and that seems quite plausible)
> then a liberal sprinkling of "ia64_mf()" calls throughout the spinlock
> routines would probably make it go away.

I think I take this back ... if it were a memory ordering problem, then
it could show up any time - not just at wrap-around.

-Tony

2010-08-27 20:40:47

by Petr Tesařík

[permalink] [raw]
Subject: Re: Serious problem with ticket spinlocks on ia64

On Friday 27 of August 2010 22:29:41 Luck, Tony wrote:
> > If this is a memory ordering problem (and that seems quite plausible)
> > then a liberal sprinkling of "ia64_mf()" calls throughout the spinlock
> > routines would probably make it go away.
>
> I think I take this back ... if it were a memory ordering problem, then
> it could show up any time - not just at wrap-around.

Well, I wasn't originally sure if it only happens at wrap-around. OTOH I've
now modified my tests, so that they would also catch any other badness, and I
still only got another two failures after wrap-around.

>From looking at the traces, I'm afraid this smells like another Itanium
erratum. I'm now trying to write a minimal test case...

Petr Tesarik

2010-08-27 21:03:04

by Petr Tesařík

[permalink] [raw]
Subject: Re: Serious problem with ticket spinlocks on ia64

On Friday 27 of August 2010 22:29:41 Luck, Tony wrote:
> > If this is a memory ordering problem (and that seems quite plausible)
> > then a liberal sprinkling of "ia64_mf()" calls throughout the spinlock
> > routines would probably make it go away.
>
> I think I take this back ... if it were a memory ordering problem, then
> it could show up any time - not just at wrap-around.

One more idea. The wrap-around case is the only one when the high word is
modified. This is in fact the only case when the fetchadd.acq competes with
the st2.rel about the actual contents of that location. I don't know if it
matters...

Petr Tesarik

2010-08-27 21:12:14

by Luck, Tony

[permalink] [raw]
Subject: RE: Serious problem with ticket spinlocks on ia64

> One more idea. The wrap-around case is the only one when the high word is
> modified. This is in fact the only case when the fetchadd.acq competes with
> the st2.rel about the actual contents of that location. I don't know if it
> matters...

I pondered that for a while - but I have difficulty believing that
fetchadd looks at which bits changed and only writes back the bytes
that did.

-Tony

2010-08-27 22:12:50

by Petr Tesařík

[permalink] [raw]
Subject: Re: Serious problem with ticket spinlocks on ia64

On Friday 27 of August 2010 23:11:55 Luck, Tony wrote:
> > One more idea. The wrap-around case is the only one when the high word is
> > modified. This is in fact the only case when the fetchadd.acq competes
> > with the st2.rel about the actual contents of that location. I don't know
> > if it matters...
>
> I pondered that for a while - but I have difficulty believing that
> fetchadd looks at which bits changed and only writes back the bytes
> that did.

OTOH the counter is only 15-bit, so it also wraps around at 0xfffe7fff, but
I have never seen it fail there. It always fails after the wrap-around from
0xfffeffff.

Petr Tesarik

2010-08-27 23:26:52

by Luck, Tony

[permalink] [raw]
Subject: RE: Serious problem with ticket spinlocks on ia64

Debugging this in the kernel seemed hard ... so I tried to construct a
user level test using the same code from the kernel. See attached. But
this fails so catastrophically with any number of threads greater than
one, that I suspect I made some mistake cut & pasting the relevant bits
of kernel infrastructure. The goal of the program is to have several
child processes pounding on a lock while the parent looks in every 5
seconds to see if they are making progress.

-Tony


Attachments:
spinwrap.c (6.92 kB)
spinwrap.c

2010-08-27 23:55:49

by Luck, Tony

[permalink] [raw]
Subject: RE: Serious problem with ticket spinlocks on ia64

> this fails so catastrophically

Interesting ... getting rid of some of the fancy asm bits
(replacing both the ld4.c.nc and the ld2.bias with simple
"serve = *p" and "tmp = *p") makes this run a lot better.

-Tony

2010-08-28 00:29:11

by Hedi Berriche

[permalink] [raw]
Subject: Re: Serious problem with ticket spinlocks on ia64

On Sat, Aug 28, 2010 at 00:55 Tony Luck wrote:
| > this fails so catastrophically
|
| Interesting ... getting rid of some of the fancy asm bits
| (replacing both the ld4.c.nc and the ld2.bias with simple
| "serve = *p" and "tmp = *p") makes this run a lot better.

*Hasty* look seems to suggest that keeping the fancy asm bits but compiling with
-O2 -frename-registers makes it work equally well.

Don't take my word for it though, double check it, it's been a long week and
brain is anything but alert at this time of the night.

Cheers,
Hedi.
--
Hedi Berriche
Global Product Support
http://www.sgi.com/support

2010-08-28 05:01:22

by Luck, Tony

[permalink] [raw]
Subject: RE: Serious problem with ticket spinlocks on ia64

>*Hasty* look seems to suggest that keeping the fancy asm bits but compiling >with
>-O2 -frename-registers makes it work equally well.
>
>Don't take my word for it though, double check it, it's been a long week and
>brain is anything but alert at this time of the night.

Yup - that makes the usermode version run just fine (no problems
in the first billion lock/unlock operations ... which is
quite a lot of wrap-arounds of the 15-bit ticket lock).

And since we already use -frename-registers when building the
kernel, no immediate help for the kernel problem. :-(

I may tinker with this test a bit to include some short random
amounts of hold-time for the lock, and delays between attempts
to acquire it (to make it look more like a contended kernel lock
and less like a continuous queue of processes trading around a
lock that is never free ... Petr's debug information definitely
showed the lock becoming free at the wraparound (lock == 0x0).

-Tony

2010-08-30 18:17:29

by Luck, Tony

[permalink] [raw]
Subject: RE: Serious problem with ticket spinlocks on ia64

> I may tinker with this test a bit to include some short random
> amounts of hold-time for the lock, and delays between attempts
> to acquire it (to make it look more like a contended kernel lock
> and less like a continuous queue of processes trading around a
> lock that is never free

I've been iterating ... adding new bits to try to reproduce the
kernel environment:

1) Added delays (bigger delay not holding the lock than holding
it - so contention is controlled)
2) Check that locking actually works (with a critzone element that
is only modified when the lock is held).
3) Sometimes use trylock (all the odd numbered threads do this).

Compile with -frename-registers ... and add a nop() { } function
in another file (just to make sure the compiler doesn't optimize
the delay loops).

Sadly ... my user mode experiments haven't yet yielded any cases
where the ticket locks fail in the way that Petr saw them mess up
inside the kernel. This latest version has been running for ~90
minutes and has completed 25 million lock/trylock iterations (with
about a third of the ticket lock wraparounds passing through the
uncontested case (lock == 0) and the rest happening with some
processes waiting for the lock.

So now I'm trying to think of other ways that the kernel case
differs from my user mode mock-up.

-Tony


Attachments:
spinwrap.c (11.74 kB)
spinwrap.c

2010-08-30 21:40:41

by Petr Tesařík

[permalink] [raw]
Subject: Re: Serious problem with ticket spinlocks on ia64

On Monday 30 of August 2010 20:17:25 Luck, Tony wrote:
> > I may tinker with this test a bit to include some short random
> > amounts of hold-time for the lock, and delays between attempts
> > to acquire it (to make it look more like a contended kernel lock
> > and less like a continuous queue of processes trading around a
> > lock that is never free
>
> I've been iterating ... adding new bits to try to reproduce the
> kernel environment:

Hi Tony,

I've been also playing with my test case, and I haven't been able to reproduce
it in user-space either. One thing I noticed was the apparently incorrect use
of ALAT. The generated code for _spin_lock_irq contains:

invala;;
ld4.c.nc r11=[r32]
// Other instructions not affecting r20
ld4.c.nc r20=[r32]

IIUC, the subsequent compare can use an undefined value (r20 is not modified
anywhere in this function, except by the ld4.c.nc, but that happens only on
an ALAT miss, right?).

I changed the corresponding code in __ticket_spin_lock to:

asm volatile ("ld4.c.nc %0=[%1]" : "+r"(serve) : "r"(p) : "memory");

(NB the "+r" constraint instead of "=r")

The generated code now re-uses r15. Unfortunately, Hedi's test case still
fails for me. :(

Petr Tesarik

2010-08-30 22:43:27

by Luck, Tony

[permalink] [raw]
Subject: Re: Serious problem with ticket spinlocks on ia64

On Mon, Aug 30, 2010 at 2:41 PM, Petr Tesarik <[email protected]> wrote:
> IIUC, the subsequent compare can use an undefined value (r20 is not modified
> anywhere in this function, except by the ld4.c.nc, but that happens only on
> an ALAT miss, right?).

I don't see that in my kernel - but you raise a good point. The idea in this
code is that invala makes sure that we don't have a matching ALAT entry
on the first iteration of the loop, so we will do the load. Then we loop not
actually doing the access until the ALAT tells us that the location may
have changed, when we load again. But this assumes that the compiler
didn't decide to re-use the register for something else in the loop. So
things may be a bit fragile if some aggressive optimization happen after
the routine is inlined.

Does Hedi's test fail for you if you drop the fancy ALAT trick?
I.e. just use "serve = *p;" in __ticket_spin_lock()? [& similar in
__ticket_spin_unlock_wait() if you want - but I don't think that
is ever used for siglock]

-Tony

2010-08-31 22:17:31

by Tony Luck

[permalink] [raw]
Subject: Re: Serious problem with ticket spinlocks on ia64

On Mon, Aug 30, 2010 at 3:43 PM, Tony Luck <[email protected]> wrote:
> Does Hedi's test fail for you if you drop the fancy ALAT trick?
> I.e. just use "serve = *p;" in __ticket_spin_lock()?

Answering my own question ... it failed in 47 minutes with the breakit
script on iteration 2812 :-(

So it would appear that the problem isn't related to the ALAT, or weird
compiler optimizations around the inline asm.

-Tony