Re: [Boost-users] Thread-safe smart pointers, hashtables without locking

From: Ray Whitmer (ray_at_[hidden])
Date: 2006-05-06 08:16:56

> I'd also say the idea of moving a pointer out of the way, and then  
> using the
> flip-gate-count-thing to wait for any 'potentially-using' readers  
> to finish,
> definitely has 'potential'. You would need to show detailed code to  
> really
> be sure. And not to us - to the guys on comp.programming.threads.

Thanks.  I will plan on pursuing it, then.

> Anyhow, if you haven't already, take a look at memory barriers,  
> and, as a
> canonical example, the broken 'double checked locking pattern'. You  
> can't
> do lock free without understanding this stuff.

I was somewhat aware of memory ordering and especially compiler  
reordering, but I need to take another look at it and find the proper  
set of macros for use in non-kernel code since volatile does not  
(yet) guarantee hardware behavior between processors.

> And you are correct, you can't make { reading the
> location of a shared_ptr + incrementing its ref-count } atomic, it  
> least not
> on most processors.

Actually, I was not concerned with incrementing the ref count.  The  
flip-gate-count-thing solves, I believe, the problem of reference  
counts not being up to date all the time.  I realize that I still  
have to prove this, but I do not think it is hard.

What worries me more is whether the smart pointer has one or two  
fields in it, because this affects whether readers find an incomplete/ 
broken smart pointer as they whiz by.  With a single pointer field in  
it, the load and store are atomic.

> I don't think the boost implementation of intrusive_ptr's operator= 
> () is
> atomic, but it could be made to be.

shared_ptr has two pointers in it, (one to the shared count, one for  
the pointer) whereas intrusive_ptr has a single pointer in it (since  
the count is internal to the referenced class).

This means that the shallow bits of shared_ptr are not atomically  
initialized, whereas those of intrusive_ptr are.  An obvious way to  
solve this would be to make shared_ptr contain a single pointer to a  
wrapper class that contains both the shared count and a shared  
pointer, but this adds an unacceptable level of indirection to basic  
pointer operations.

> Your wording of 'much less likely' is scary, and I think similar  
> wording
> made James apprehensive as well. There is no grey - it is black or  
> white,
> thread safe or not.

I will have to adjust my language.

I tend to use uncertain language both because I consider my knowledge  
incomplete and because of the lack of a generic standard that  
guarantees behavior, i.e. the fact that different Linux kernel  
architectures need different memory barriers, etc. is demonstration  
of the uncertainty of a general C solution.

If I can rely on something like what the Linux kernel relies on, it  
should not be scary.  Behavior needs to be guaranteed on supported  
platforms, and other platforms need to be detected and fail to  
compile lock-free or revert to a locking fallback implementation, etc.

Ray Whitmer