Possible race-condition in Sun's KCSS impl...
CASTalk.com Forum Index CASTalk.com
Discussion of DSP, FPGA, storage and embedded system.
 
 FAQFAQ   MemberlistMemberlist     RegisterRegister 
 ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 
 
Google
 
Web castalk.com
Possible race-condition in Sun's KCSS impl...

 
Post new topic   Reply to topic    CASTalk.com Forum Index -> Computer Architecture
Author Message
Chris Thomasson
Guest
Posted: Tue Oct 25, 2005 8:15 am    Post subject: Possible race-condition in Sun's KCSS impl... Reply with quote
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
Back to top
Joe Seigh
Guest
Posted: Tue Oct 25, 2005 4:15 pm    Post subject: Re: Possible race-condition in Sun's KCSS impl... Reply with quote
Chris Thomasson wrote:
Quote:
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.


--
Joe Seigh

When you get lemons, you make lemonade.
When you get hardware, you make software.
Back to top
Joe Seigh
Guest
Posted: Tue Oct 25, 2005 4:15 pm    Post subject: Re: Possible race-condition in Sun's KCSS impl... Reply with quote
Joe Seigh wrote:
Quote:
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.


--
Joe Seigh

When you get lemons, you make lemonade.
When you get hardware, you make software.
Back to top
Chris Thomasson
Guest
Posted: Wed Oct 26, 2005 2:04 pm    Post subject: Re: Possible race-condition in Sun's KCSS impl... Reply with quote
"Joe Seigh" <jseigh_01@xemaps.com> wrote in message
news:y5WdnamMdI0dpcPeRVn-gQ@comcast.com...
Quote:
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.




Quote:
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?
Back to top
Joe Seigh
Guest
Posted: Wed Oct 26, 2005 2:34 pm    Post subject: Re: Possible race-condition in Sun's KCSS impl... Reply with quote
Chris Thomasson wrote:
Quote:
"Joe Seigh" <jseigh_01@xemaps.com> wrote in message
news:y5WdnamMdI0dpcPeRVn-gQ@comcast.com...

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?


B3 resets L1 when it does the READ so A6 will fail.



--
Joe Seigh

When you get lemons, you make lemonade.
When you get hardware, you make software.
Back to top
Chris Thomasson
Guest
Posted: Wed Oct 26, 2005 2:45 pm    Post subject: Re: Possible race-condition in Sun's KCSS impl... Reply with quote
Quote:
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.


Quote:
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
B6 - L2 is now 2, this should make A6 fail...
A6 - oops! L1 = 0 so the SC will succeed in error!
Back to top
Chris Thomasson
Guest
Posted: Wed Oct 26, 2005 2:48 pm    Post subject: Re: Possible race-condition in Sun's KCSS impl... Reply with quote
Quote:
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?
Back to top
Joe Seigh
Guest
Posted: Wed Oct 26, 2005 3:03 pm    Post subject: Re: Possible race-condition in Sun's KCSS impl... Reply with quote
Chris Thomasson wrote:
Quote:
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.


--
Joe Seigh

When you get lemons, you make lemonade.
When you get hardware, you make software.
Back to top
Chris Thomasson
Guest
Posted: Wed Oct 26, 2005 4:11 pm    Post subject: Re: Possible race-condition in Sun's KCSS impl... Reply with quote
"Joe Seigh" <jseigh_01@xemaps.com> wrote in message
news:3vmdncR3cNDOycLeRVn-hQ@comcast.com...
Quote:
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
Back to top
Joe Seigh
Guest
Posted: Wed Oct 26, 2005 4:15 pm    Post subject: Re: Possible race-condition in Sun's KCSS impl... Reply with quote
Chris Thomasson wrote:
Quote:
"Joe Seigh" <jseigh_01@xemaps.com> wrote in message
news:3vmdncR3cNDOycLeRVn-hQ@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?

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 )


--
Joe Seigh

When you get lemons, you make lemonade.
When you get hardware, you make software.
Back to top
 
Post new topic   Reply to topic    CASTalk.com Forum Index -> Computer Architecture All times are GMT
Page 1 of 1

 
 You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum




VoIP Electronics Powered by phpBB