Re: [boost] [proposal] AtomicallyThread-SafeReferenceCountingAlgorithm...

From: Chris Thomasson (cristom_at_[hidden])
Date: 2006-10-22 15:02:36

Sorry for not answering this sooner!

"Peter Dimov" <pdimov_at_[hidden]> wrote in message 
news:001c01c6f491$0d3e2690$6507a8c0_at_pdimov2...
> Chris Thomasson wrote:
>>> Is this inferior to your proposed scheme?
>> Maybe... Currently, all of my pointer-ops are 100% lock-free. My
>> reference count adjustments are 100% lock-free for everything except
>> strong competing accesses (e.g., it only *takes a spinlock for strong
>> competing accesses, **and when the count drops to zero). My counter
>> objects can be swapped using normal word-based atomic operations
>> (e.g., XCHG and CAS, no DWCAS required)...
>
> How do you distingush strong competing accesses from noncompeting 
> accesses?

ptr::global loads ptr::global = strong
ptr::global loads ptr::local = weak
ptr::global stores/swaps are atomic
ptr::global refcount updates are atomic

ptr::local loads ptr::global = strong
ptr::local loads ptr::local = weak
ptr::local stores/swaps are not-atomic
ptr::local refcount updates are atomic

> You have two pointers, global and local; what levels of thread safety do
> these offer?

ptr::global = strong

> Is global the atomic pointer and local the "as safe as an int"
> equivalent? Or is local to be kept local to a thread?

ptr::local should only have one 1 thread loading or storing into it at any 
one time; local does not have atomic pointer swaps. It makes use of 
impl_base::swap_naked(...). No reason to have atomic pointer swaps for a 
ptr::local. However, the count updates are still atomic.

For example:

- You can contain ptr::local<foo> in a shared collection that is protected 
by a mutex. If the collection was not protected by a mutex then it would 
have to contain ptr::global<foo> instead.

- One thread can create a ptr::local<foo> and transfer it to another thread, 
via. queue. This can be accomplished without using ptr::global<foo>.

- The only time you make use of ptr::global<foo> is when you wish to make 
use of strong thread-safety. Otherwise, use ptr::local<foo>.

> If I have
>
> ptr::global<X> px;
>
> and I copy px into another global, does this take a spinlock?

Yes.

> If I assign to
> it?

If you assign a ptr::local to a ptr::global, then you have a weak increment. 
If you assign a ptr::global to a ptr::local, then you have a strong 
increment.

> Sorry for asking so many questions,

No Problem!  :^)

> but lock-free source code is hard.
> :-)

This is mostly lock-free... It's still kind of tricky though...

;^)