Possible race-condition in Sun's KCSS impl...
Chris Thomasson
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
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
> 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.
>
>
Chris Thomasson
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
> "Joe Seigh" <jsei...@xemaps.com> wrote in message
> news:y5WdnamMdI0...@comcast.com...
>>
Chris Thomasson
>
> 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
> 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
Chris Thomasson
> 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
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 )