Possible race-condition in Sun's KCSS impl...

26 views
Skip to first unread message

Chris Thomasson

unread,
Oct 24, 2005, 11:38:35 PM10/24/05
to
Anybody notice the race-condition that probably exists between operations K4
and K7 in figure 5 (pg.5)?

http://research.sun.com/people/moir/Papers/p004-luchangco.pdf

If another thread completes is emulated LL/SC in between, K7 will still
succeed??? That should ruin the target data-structures integrity???

:O


Joe Seigh

unread,
Oct 25, 2005, 9:13:12 AM10/25/05
to
So it would seem. I don't know how to do it unless all of the tag id version
numbers, not just the one, are incremented first before attempting the update.
But I haven't read the article that closely yet.


--
Joe Seigh

When you get lemons, you make lemonade.
When you get hardware, you make software.

Joe Seigh

unread,
Oct 25, 2005, 9:52:03 AM10/25/05
to
Joe Seigh wrote:
> Chris Thomasson wrote:
>
>> Anybody notice the race-condition that probably exists between
>> operations K4 and K7 in figure 5 (pg.5)?
>>
>> http://research.sun.com/people/moir/Papers/p004-luchangco.pdf
>>
>> If another thread completes is emulated LL/SC in between, K7 will
>> still succeed??? That should ruin the target data-structures integrity???
>>
> So it would seem. I don't know how to do it unless all of the tag id
> version
> numbers, not just the one, are incremented first before attempting the
> update.
> But I haven't read the article that closely yet.
>
>
Ah, the READ operation resets the value if it sees a tagged value.

Chris Thomasson

unread,
Oct 26, 2005, 5:04:58 AM10/26/05
to
"Joe Seigh" <jsei...@xemaps.com> wrote in message
news:y5WdnamMdI0...@comcast.com...

> Joe Seigh wrote:
>> Chris Thomasson wrote:
>>
>>> Anybody notice the race-condition that probably exists between
>>> operations K4 and K7 in figure 5 (pg.5)?
>>>
>>> http://research.sun.com/people/moir/Papers/p004-luchangco.pdf
>>>
>>> If another thread completes is emulated LL/SC in between, K7 will still
>>> succeed??? That should ruin the target data-structures integrity???
>>>
>> So it would seem. I don't know how to do it unless all of the tag id
>> version
>> numbers, not just the one, are incremented first before attempting the
>> update.

That's what I was thinking.


>> But I haven't read the article that closely yet.
>>
>>
> Ah, the READ operation resets the value if it sees a tagged value.

Well, I think that there still may be a problem. I believe you can setup a
race-condition like this:


Given the following scenario:

location L1 = 0
location L2 = 0
location L3 = 0


Thread A
------------
1: KCSS( [&L1,L2], [0,0], 1 )
2: LL( &L1 )
3: S = SNAPSHOT( L2 )
4: if ( L1 != 0 || S != 0 )
5: { SC( &L1, 0 ); return; }
6: SC( &L1, 1 )

Thread B
------------
1: KCSS( [&L2,L3], [0,0], 2 )
2: LL( &L2 )
3: S = SNAPSHOT( L3 )
4: if ( L2 != 0 || S != 0 )
5: { SC( &L2, 0 ); return; }
6: SC( &L2, 2 )


Now, suppose the execution sequence goes like this:

A1
A2
A3
A4 - (L2=0) snapshot compare success!
B1
B2
B3
B4
B5
B6 - L2 is now 2, this should make A6 fail...
A6 - oops! L1 = 0 so the SC will succeed in error!


I must be missing something here. What do you think?


Joe Seigh

unread,
Oct 26, 2005, 5:34:47 AM10/26/05
to
Chris Thomasson wrote:
> "Joe Seigh" <jsei...@xemaps.com> wrote in message
> news:y5WdnamMdI0...@comcast.com...
>>
B3 resets L1 when it does the READ so A6 will fail.

Chris Thomasson

unread,
Oct 26, 2005, 5:45:39 AM10/26/05
to
> Now, suppose the execution sequence goes like this:
>
> A1
> A2
> A3
> A4 - (L2=0) snapshot compare success!
> B1
> B2
> B3
> B4

> B5
^^^^

DOH! This needs to be removed.


> B6 - L2 is now 2, this should make A6 fail...
> A6 - oops! L1 = 0 so the SC will succeed in error!

Corrected sequence:

A1
A2
A3
A4 - (L2=0) snapshot compare success!
B1
B2
B3
B4

Chris Thomasson

unread,
Oct 26, 2005, 5:48:56 AM10/26/05
to
>> I must be missing something here. What do you think?
> B3 resets L1 when it does the READ so A6 will fail.

Humm... B3 takes a snapshot of "only" L3, I don't believe that would modify
L1?


Joe Seigh

unread,
Oct 26, 2005, 6:03:05 AM10/26/05
to
The snapshot is of all k locations AFAIK.

Chris Thomasson

unread,
Oct 26, 2005, 7:11:18 AM10/26/05
to
"Joe Seigh" <jsei...@xemaps.com> wrote in message
news:3vmdncR3cND...@comcast.com...

> Chris Thomasson wrote:
>>>>I must be missing something here. What do you think?
>>>
>>>B3 resets L1 when it does the READ so A6 will fail.
>>
>>
>> Humm... B3 takes a snapshot of "only" L3, I don't believe that would
>> modify L1?
> The snapshot is of all k locations AFAIK.

Operation B's KCSS only operated on L2 and L3; the snapshot will only be for
L3. Look a little bit more closely at line K3 in figure 5.


So, that still leaves poor old L1 completely unchanged so A6 could still
succeed?

:O


Joe Seigh

unread,
Oct 26, 2005, 8:02:23 AM10/26/05
to
Ok, coffee hitting now.

Yes, that's true so it's not compare and swap as you know it. But it doesn't
appear to hurt anything as B is not dependent on L1. Anything you tried to
set up with a circular dependency would probably have one of the kcss's fail. E.g.


KCSS( [&L1,L2], [0,0], 1 )

KCSS( [&L2,L3], [0,0], 2 )

KCSS( [&L3,L1], [0,0], 3 )

Reply all
Reply to author
Forward
0 new messages