Subj : Re: possible lock-free stack on G4 livelock issue... To : comp.programming.threads From : Joseph Seigh Date : Mon Jan 17 2005 02:15 pm On Mon, 17 Jan 2005 10:42:24 -0800, SenderX wrote: > In the push function for a lock-free stack the new node's next pointer to > set to the front of the stack before the actual atomic operation ( cas or > ll/sc ) that updated the stack is executed: > > retry: > lwarx r2,0,r3 > stw r2,0(r4) > sync > stwcx. r4,0,r3 > bne- retry > > > What if more than once node's next pointers are in the same reservation > granule? What if the new node's next pointer was on the same granule as the > stack anchor? > > I believe this could cause a possible race-and-live-lock scenario. Any > thoughts? > This has been a known issue. The reservation granule size should be small enough that this shouldn't be a problem with object allocated with malloc. The granule size may be queryable now. There's probably a discussion on this and what to do about it in the architecture manuals. For push you could just do a regular load and store into the new node, then do a load reserved and test that value with the previously loaded value and retry if different. Might need a sync between the store and load reserved which would be expensive so I'd confirm it was actually going to be a problem first before trying that approach. -- Joe Seigh .