Thread overview
Refcounting smart pointer?
Sep 03, 2008
Bill Baxter
Sep 03, 2008
Sönke Ludwig
Sep 04, 2008
Jason House
Sep 04, 2008
Bill Baxter
Sep 04, 2008
Sönke Ludwig
Sep 05, 2008
Jb
Sep 05, 2008
Sönke Ludwig
Sep 06, 2008
Jb
Sep 06, 2008
Denis Koroskin
September 03, 2008
Has anyone made a reference counting smart pointer using D2 structs yet? It should be possible now with the opDot, destructors, postblit thingy and constructor.

Is anything missing to make it work?  Actually I don't even think the constructor was necessary.  So someone probably could have done this a while ago.

--bb
September 03, 2008
Bill Baxter schrieb:
> Has anyone made a reference counting smart pointer using D2 structs yet?
> It should be possible now with the opDot, destructors, postblit thingy
> and constructor.
> 
> Is anything missing to make it work?  Actually I don't even think the
> constructor was necessary.  So someone probably could have done this a
> while ago.
> 
> --bb

Just implemented this today, and it seems to work fine:

struct CountedRef(T) {
	static if( is(T == class) ){
		alias T T_ref;
	} else {
		alias T* T_ref;
	}

	private {
		T_ref m_object;
		int* m_refcount;
	}

	this(T_ref obj){
		m_object = obj;
		m_refcount = new int;
		*m_refcount = 1;
	}

	~this(){
		if( m_refcount && --(*m_refcount) <= 0 ){
			delete m_object;
			delete m_refcount;
		}
	}

	this(this){
		if( m_refcount )
			(*m_refcount)++;
	}

	T_ref get(){ return m_object; }
	const(T_ref) get() const { return m_object; }

	T_ref opDot(){ return m_object; }
	const(T_ref) opDot() const { return m_object; }
}

struct IntrusiveCountedRef(T) {
	static if( is(T == class) ){
		alias T T_ref;
	} else {
		alias T* T_ref;
	}

	private {
		T_ref m_object;
	}

	this(T_ref obj){
		m_object = obj;
		obj.addRef();
	}

	~this(){
		if( m_object )
			m_object.releaseRef();
	}

	this(this){
		if( m_object )
			m_object.addRef();
	}

	T_ref get(){ return m_object; }
	const(T_ref) get() const { return m_object; }

	T_ref opDot(){ return m_object; }
	const(T_ref) opDot() const { return m_object; }
}
September 04, 2008
Your implementation is not thread safe...

Sönke Ludwig Wrote:

> Bill Baxter schrieb:
> > Has anyone made a reference counting smart pointer using D2 structs yet? It should be possible now with the opDot, destructors, postblit thingy and constructor.
> > 
> > Is anything missing to make it work?  Actually I don't even think the constructor was necessary.  So someone probably could have done this a while ago.
> > 
> > --bb
> 
> Just implemented this today, and it seems to work fine:
> 
> struct CountedRef(T) {
> 	static if( is(T == class) ){
> 		alias T T_ref;
> 	} else {
> 		alias T* T_ref;
> 	}
> 
> 	private {
> 		T_ref m_object;
> 		int* m_refcount;
> 	}
> 
> 	this(T_ref obj){
> 		m_object = obj;
> 		m_refcount = new int;
> 		*m_refcount = 1;
> 	}
> 
> 	~this(){
> 		if( m_refcount && --(*m_refcount) <= 0 ){
> 			delete m_object;
> 			delete m_refcount;
> 		}
> 	}
> 
> 	this(this){
> 		if( m_refcount )
> 			(*m_refcount)++;
> 	}
> 
> 	T_ref get(){ return m_object; }
> 	const(T_ref) get() const { return m_object; }
> 
> 	T_ref opDot(){ return m_object; }
> 	const(T_ref) opDot() const { return m_object; }
> }
> 
> struct IntrusiveCountedRef(T) {
> 	static if( is(T == class) ){
> 		alias T T_ref;
> 	} else {
> 		alias T* T_ref;
> 	}
> 
> 	private {
> 		T_ref m_object;
> 	}
> 
> 	this(T_ref obj){
> 		m_object = obj;
> 		obj.addRef();
> 	}
> 
> 	~this(){
> 		if( m_object )
> 			m_object.releaseRef();
> 	}
> 
> 	this(this){
> 		if( m_object )
> 			m_object.addRef();
> 	}
> 
> 	T_ref get(){ return m_object; }
> 	const(T_ref) get() const { return m_object; }
> 
> 	T_ref opDot(){ return m_object; }
> 	const(T_ref) opDot() const { return m_object; }
> }

September 04, 2008
I don't think such things usually are thread safe.
At least Boost's is not:
  http://www.boost.org/doc/libs/1_36_0/libs/smart_ptr/shared_ptr.htm#ThreadSafety

--bb

On Thu, Sep 4, 2008 at 9:33 AM, Jason House <jason.james.house@gmail.com> wrote:
> Your implementation is not thread safe...
>
> Sönke Ludwig Wrote:
>
>> Bill Baxter schrieb:
>> > Has anyone made a reference counting smart pointer using D2 structs yet? It should be possible now with the opDot, destructors, postblit thingy and constructor.
>> >
>> > Is anything missing to make it work?  Actually I don't even think the constructor was necessary.  So someone probably could have done this a while ago.
>> >
>> > --bb
>>
>> Just implemented this today, and it seems to work fine:
>>
>> struct CountedRef(T) {
>>       static if( is(T == class) ){
>>               alias T T_ref;
>>       } else {
>>               alias T* T_ref;
>>       }
>>
>>       private {
>>               T_ref m_object;
>>               int* m_refcount;
>>       }
>>
>>       this(T_ref obj){
>>               m_object = obj;
>>               m_refcount = new int;
>>               *m_refcount = 1;
>>       }
>>
>>       ~this(){
>>               if( m_refcount && --(*m_refcount) <= 0 ){
>>                       delete m_object;
>>                       delete m_refcount;
>>               }
>>       }
>>
>>       this(this){
>>               if( m_refcount )
>>                       (*m_refcount)++;
>>       }
>>
>>       T_ref get(){ return m_object; }
>>       const(T_ref) get() const { return m_object; }
>>
>>       T_ref opDot(){ return m_object; }
>>       const(T_ref) opDot() const { return m_object; }
>> }
>>
>> struct IntrusiveCountedRef(T) {
>>       static if( is(T == class) ){
>>               alias T T_ref;
>>       } else {
>>               alias T* T_ref;
>>       }
>>
>>       private {
>>               T_ref m_object;
>>       }
>>
>>       this(T_ref obj){
>>               m_object = obj;
>>               obj.addRef();
>>       }
>>
>>       ~this(){
>>               if( m_object )
>>                       m_object.releaseRef();
>>       }
>>
>>       this(this){
>>               if( m_object )
>>                       m_object.addRef();
>>       }
>>
>>       T_ref get(){ return m_object; }
>>       const(T_ref) get() const { return m_object; }
>>
>>       T_ref opDot(){ return m_object; }
>>       const(T_ref) opDot() const { return m_object; }
>> }
>
>
September 04, 2008
In my case the CountedRef is used for an inherently single threaded scripting environment. I've got a version with similar characteristics as the boost::shared_ptr version Bill mentioned, too (with all its performance implications), but I thought this one was a simpler example of the general concept. However, it's definitely good to point out that this is only for single-threading.

On the other side, making a completely thread-safe variant is not possible as far as I see, since the copy operation is not safe - so only the reference counting part can really be made safe.
September 05, 2008
"Sönke Ludwig" <ludwig_no@spam_informatik.uni-luebeck.de> wrote in message news:g9nvrs$284k$1@digitalmars.com...
>
> On the other side, making a completely thread-safe variant is not possible as far as I see, since the copy operation is not safe - so only the reference counting part can really be made safe.

Thread safe ref counting can be done with

lock inc [this.refcount]
lock dec [this.refcount]

You need the lock prefix or else they are not atomic.




September 05, 2008
Jb schrieb:
> "Sönke Ludwig" <ludwig_no@spam_informatik.uni-luebeck.de> wrote in message news:g9nvrs$284k$1@digitalmars.com...
>> On the other side, making a completely thread-safe variant is not possible as far as I see, since the copy operation is not safe - so only the reference counting part can really be made safe.
> 
> Thread safe ref counting can be done with
> 
> lock inc [this.refcount]
> lock dec [this.refcount]
> 
> You need the lock prefix or else they are not atomic.
> 
> 
> 
> 

The problem that remains is that the copy operation (blit) of the counted reference struct is not synchronized or executed atomically together with the subsequent increment. Consider the following setup:

struct RefCounter {
	int* count;
	this(){ count = new int; *count = 1; }
	this(this){ atomic_inc(count); }
	~this(){ if( !atomic_dec(count) ) delete count; }
}

// init
RefCounter a;

// thread a
{
	// write to a
	RefCounter dummy1;
	a = dummy1;
	// 1. read tmp = a.count
	// 2. atomically decrement *tmp
	// 3.   delete a.count if <= 0
	// 4. copy dummy1 to a
	// 5. read a.count
	// 6. atomically increment *a.count
}

// thread b
{
	// read from a
	RefCounter dummy2 = a;
	// - copy
	// 1. copy a to dummy
	// 2. read dummy2.count
	// 3. atomically increment *dummy2.count
}

A possible order of execution would be:

B 1. dummy2.count is the original a.count
A 1. tmp is a.count
A 2. *tmp/*a.count is decremented -> *a.count == 0
A 3. a.count is deleted
B 2. tmp is dummy2.count, which is the original a.count
B 3. *tmp/*dummy2.count/*a.count is incremented (CRASH)
...

And if there are two pointers inside of the struct, the number
of possible failures increases considerably. So thread-safety can only be guaranteed if there are no concurrent read/write or write/write accesses to the same reference.
September 06, 2008
"Sönke Ludwig" <ludwig_no@spam_informatik.uni-luebeck.de> wrote in message news:g9rt39$4qn$1@digitalmars.com...
> Jb schrieb:
>> "Sönke Ludwig" <ludwig_no@spam_informatik.uni-luebeck.de> wrote in message news:g9nvrs$284k$1@digitalmars.com...
>>> On the other side, making a completely thread-safe variant is not possible as far as I see, since the copy operation is not safe - so only the reference counting part can really be made safe.
>>
>> Thread safe ref counting can be done with
>>
>> lock inc [this.refcount]
>> lock dec [this.refcount]
>>
>> You need the lock prefix or else they are not atomic.
>>
>>
>>
>>
>
> The problem that remains is that the copy operation (blit) of the counted reference struct is not synchronized or executed atomically together with the subsequent increment. Consider the following setup:
>
> struct RefCounter {
> int* count;
> this(){ count = new int; *count = 1; }
> this(this){ atomic_inc(count); }
> ~this(){ if( !atomic_dec(count) ) delete count; }
> }
>
> // init
> RefCounter a;
>
> // thread a
> {
> // write to a
> RefCounter dummy1;
> a = dummy1;
> // 1. read tmp = a.count
> // 2. atomically decrement *tmp
> // 3.   delete a.count if <= 0
> // 4. copy dummy1 to a
> // 5. read a.count
> // 6. atomically increment *a.count
> }
>
> // thread b
> {
> // read from a
> RefCounter dummy2 = a;
> // - copy
> // 1. copy a to dummy
> // 2. read dummy2.count
> // 3. atomically increment *dummy2.count
> }
>
> A possible order of execution would be:
>
> B 1. dummy2.count is the original a.count
> A 1. tmp is a.count
> A 2. *tmp/*a.count is decremented -> *a.count == 0
> A 3. a.count is deleted
> B 2. tmp is dummy2.count, which is the original a.count
> B 3. *tmp/*dummy2.count/*a.count is incremented (CRASH)
> ...
>
> And if there are two pointers inside of the struct, the number
> of possible failures increases considerably. So thread-safety can only be
> guaranteed if there are no concurrent read/write or write/write accesses
> to the same reference.

Ah yeah I see the problem now.



September 06, 2008
On Sat, 06 Sep 2008 05:44:50 +0400, Jb <jb@nowhere.com> wrote:

>
> "Sönke Ludwig" <ludwig_no@spam_informatik.uni-luebeck.de> wrote in message
> news:g9rt39$4qn$1@digitalmars.com...
>> Jb schrieb:
>>> "Sönke Ludwig" <ludwig_no@spam_informatik.uni-luebeck.de> wrote in
>>> message news:g9nvrs$284k$1@digitalmars.com...
>>>> On the other side, making a completely thread-safe variant is not
>>>> possible as far as I see, since the copy operation is not safe - so only
>>>> the reference counting part can really be made safe.
>>>
>>> Thread safe ref counting can be done with
>>>
>>> lock inc [this.refcount]
>>> lock dec [this.refcount]
>>>
>>> You need the lock prefix or else they are not atomic.
>>>
>>>
>>>
>>>
>>
>> The problem that remains is that the copy operation (blit) of the counted
>> reference struct is not synchronized or executed atomically together with
>> the subsequent increment. Consider the following setup:
>>
>> struct RefCounter {
>> int* count;
>> this(){ count = new int; *count = 1; }
>> this(this){ atomic_inc(count); }
>> ~this(){ if( !atomic_dec(count) ) delete count; }
>> }
>>
>> // init
>> RefCounter a;
>>
>> // thread a
>> {
>> // write to a
>> RefCounter dummy1;
>> a = dummy1;
>> // 1. read tmp = a.count
>> // 2. atomically decrement *tmp
>> // 3.   delete a.count if <= 0
>> // 4. copy dummy1 to a
>> // 5. read a.count
>> // 6. atomically increment *a.count
>> }
>>
>> // thread b
>> {
>> // read from a
>> RefCounter dummy2 = a;
>> // - copy
>> // 1. copy a to dummy
>> // 2. read dummy2.count
>> // 3. atomically increment *dummy2.count
>> }
>>
>> A possible order of execution would be:
>>
>> B 1. dummy2.count is the original a.count
>> A 1. tmp is a.count
>> A 2. *tmp/*a.count is decremented -> *a.count == 0
>> A 3. a.count is deleted
>> B 2. tmp is dummy2.count, which is the original a.count
>> B 3. *tmp/*dummy2.count/*a.count is incremented (CRASH)
>> ...
>>
>> And if there are two pointers inside of the struct, the number
>> of possible failures increases considerably. So thread-safety can only be
>> guaranteed if there are no concurrent read/write or write/write accesses
>> to the same reference.
>
> Ah yeah I see the problem now.
>
>
>

The same problem exists in C++:

// global data
RefCounter globalRC;

// thread one:
...
RefCounter localRC = globalRC;
...

// thread two:
...
globalRC = NULL;
...

class RefCounter
{
    RefCounter(RefCounter& other)
    {
        // here we go, make a copy
        // ooops, thread switch
        // other object just got deleted

        atomicIncrement(other.count); // access violation
        this.count = other.count;
    }
}

The only solution I see is to make ctor and opAssign synchronized:

class RefCounter
{
    syncronized this(this) // blitting should be syncronized, too, not only postblitting
    {
        ++*count;
    }

    syncronized opAssign(RefCounter other)
    {
        count = other.count;
        ++*count;
    }
}

*Or* just get rid of the global-accessible refcounted object. All the refcounted objects should be thread-local. In this case you need no syncronization and no atomicity.