article on atomic reference counted pointers...
Chris Thomasson
http://www.ddj.com/architect/184401888?pgno=1
I don't understand how it's going to work; here is the pseudo-code for the
"copy" function:
__________________________________________________
addr aIandF(addr r1){
addr tmp;int c;
do{
do{
0: tmp = *r1;
1: if(!tmp)break;
2: c = lwarx(tmp);
3: }while(tmp != *r1);
4: }while(tmp && !stwcx(tmp,c+1));
return tmp;
};
__________________________________________________
I think its missing a #StoreLoad after step 2, and more importantly, it
could still reference deleted memory in either (line 2) or (line 4). For
instance, the reference count could drop to zero right after (line 1), which
would mean that the LL in (line 2) would try and read from garbage. Also,
the count could reach zero after (line 3) and allow the SC in (line 4) to
attempt to store into garbage; of course the reservation would be revoked
but that still presents problems. Also, he made a mistake in the type of the
'r1' parameter; it should be a pointer to and address (e.g., addr*). There
is another mistake in the parameter type of the aSwap function (e.g.,
parameters r1 and r2 need to be of type 'addr*'. Unless I am missing
something here, the algorithm is totally busted.
--
Chris M. Thomasson
http://appcore.home.comcast.net
Joe Seigh
of the algorithm used in the powerpc implementation of atomic_ptr. It
can do reads from undefined storage but that shouldn't hurt anything as
long as you don't unmap the memory. Lock-free LIFO using CAS2 has the same
problem.
--
Joe Seigh
When you get lemons, you make lemonade.
When you get hardware, you make software.
Chris Thomasson
news:pzwMj.6189$mG1.3123@trndny08...
Does a store-conditional on freed memory generate exceptions? Would that be
implementation defined on a PPC for instance?
> Lock-free LIFO using CAS2 has the same problem.
It's only a problem if you free memory. As we know, there are various
methods to solve it. Proxy GC, or SEH, ect... One nice "side-effect" of
using a proxy GC is that you can use normal CAS instead of DWCAS if you
always defer nodes before you reuse them.
Joe Seigh
> "Joe Seigh" <jsei...@xemaps.com> wrote in message
> news:pzwMj.6189$mG1.3123@trndny08...
>>>
>> reinvention
>> of the algorithm used in the powerpc implementation of atomic_ptr. It
>> can do reads from undefined storage but that shouldn't hurt anything as
>> long as you don't unmap the memory.
>
> Does a store-conditional on freed memory generate exceptions? Would that
> be implementation defined on a PPC for instance?
>
>
>
>
>> Lock-free LIFO using CAS2 has the same problem.
>
> It's only a problem if you free memory. As we know, there are various
> methods to solve it. Proxy GC, or SEH, ect... One nice "side-effect" of
> using a proxy GC is that you can use normal CAS instead of DWCAS if you
> always defer nodes before you reuse them.
I should have put problem in quotes. You just get undefined load
values which aren't a problem since they don't get used.
Chris Thomasson
> Chris Thomasson wrote:
>> "Joe Seigh" <jsei...@xemaps.com> wrote in message
>> news:pzwMj.6189$mG1.3123@trndny08...
>>>>
>>> This is an old article which I've commented on before. It's a
>>> reinvention
>>> of the algorithm used in the powerpc implementation of atomic_ptr. It
>>> can do reads from undefined storage but that shouldn't hurt anything as
>>> long as you don't unmap the memory.
>>
>> Does a store-conditional on freed memory generate exceptions? Would that
>> be implementation defined on a PPC for instance?
>>
>>
> No, why would it?
I was mainly referring to Alex's comment here:
http://groups.google.com/group/comp.programming.threads/msg/32bf9bc5c5aa85ee
However, you did mention that in order for it to operate correctly, virtual
storage always needs to be valid so the load-locked won't seg-fault. Okay.
As long as that explicit rule is followed, then it should work fine.