Subj : Re: A question about atomic_ptr
To   : comp.programming.threads
From : Chris Thomasson
Date : Sun Apr 17 2005 01:22 am

> Totally incomprehensible. ;-) I'll probably need a day or two to navigate
> that.

:P




> From what I can understand, it looks like a textbook hazard pointer
> implementation.

The "original" SMR algorithm uses a global lock-free LIFO coupled with 
per-TLS spinlocks to manage its TLS storage scheme. My implementation uses a 
global rw-spinlock( ac_rwspinlock_algo1.h ) to handle the internal SMR TLS 
infrastructure; IMHO this logic does not need to be lock-free, in fact 
lock-free here could "greatly" reduce the overall flexibility of the SMR 
algorithm ( especially in general user-space apps ). AppCore uses the 
rw-spinlock to grant write access to TLS ctor/dtor's, and allow read access 
solely for "hazard pointer scans". Applications that rapidly create threads 
for extended periods of time can possibly render this solution suboptimal; 
Frequent thread creation is basically more damaging to performance than a 
rw-spinlock crapping out. User applications that deliberately choose to do 
"stupid things" will reap what they sow.




>(Except that you are using the high bit of the reference
> count for something that I haven't deciphered yet.)

High-bit indicates that the node is static; Never can be freed. Its an 
optimization for "non-garbage-collected" algorithms. This is another example 
of creating a special case to avoid calling into SMR API, static objects do 
not need to be collected in a vast majority of cases. The ( 
ac_i686_node_cache_push function located in ac_i686.c ) can set this bit.

The atomic reference count API ( ac_i686_lfgc_refcount.h ) needs to mask 
this bit off in order to get at the correct count. The API needs to do this 
because it acquires its reference count structure( ac_i686_lfgc_refcount_t ) 
from the same cache's the lock-free nodes( ac_i686_node_t ) are stored in 
( ac_i686_node_t ).




> For me, the most painful part of a hazard pointer implementation is the
> pointer-per-thread table (ac_thread.c). (There are some issues with
> destruction and deallocation but they probably can be solved.)

Yeah. That's a main reason why I am experimenting with SMR based reference 
counting... This allows me to rely on a single hazard per-thread to protect 
basically any number of reference counts; hazard pointers are only used to 
provide the ability for "competing / strong thread-safe" count increments. 
This is more efficient than adding additional logic in the ( 
ac_i686_lfgc_smr_activate ) "stage" of the SMR algorithm; Making the number 
of hazard-pointers adjustable at runtime would just introduce additional 
memory barrier overhead...




> But there's one other thing: shared_ptr is two pointers, not one. Without
> DWCAS, or at least double-wide atomic loads and stores, even hazards 
> aren't
> enough to make it atomic. :-(

Humm... There should be a way. I will try to apply my SMR implementation to 
your shared_ptr< T > and see what I can come up with.

;)

.