View mode: basic / threaded / horizontal-split · Log in · Help
September 03, 2008
Refcounting smart pointer?
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
Re: Refcounting smart pointer?
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
Re: Refcounting smart pointer?
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
Re: Refcounting smart pointer?
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
Re: Refcounting smart pointer?
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
Re: Refcounting smart pointer?
"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
Re: Refcounting smart pointer?
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
Re: Refcounting smart pointer?
"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
Re: Refcounting smart pointer?
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.
Top | Discussion index | About this forum | D home