www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Refcounting smart pointer?

reply "Bill Baxter" <wbaxter gmail.com> writes:
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
Sep 03 2008
parent reply =?ISO-8859-1?Q?S=F6nke_Ludwig?= writes:
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; }
}
Sep 03 2008
parent reply Jason House <jason.james.house gmail.com> writes:
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; }
 }
Sep 03 2008
next sibling parent "Bill Baxter" <wbaxter gmail.com> writes:
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#Thread=
Safety

--bb

On Thu, Sep 4, 2008 at 9:33 AM, Jason House <jason.james.house gmail.com> w=
rote:

 Your implementation is not thread safe...

 S=F6nke Ludwig Wrote:


 Bill Baxter schrieb:

 Has anyone made a reference counting smart pointer using D2 structs ye=






t?

 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 =3D=3D class) ){
               alias T T_ref;
       } else {
               alias T* T_ref;
       }

       private {
               T_ref m_object;
               int* m_refcount;
       }

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

       ~this(){
               if( m_refcount && --(*m_refcount) <=3D 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 =3D=3D class) ){
               alias T T_ref;
       } else {
               alias T* T_ref;
       }

       private {
               T_ref m_object;
       }

       this(T_ref obj){
               m_object =3D 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; }
 }
Sep 03 2008
prev sibling parent reply =?ISO-8859-15?Q?S=F6nke_Ludwig?= writes:
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.
Sep 03 2008
parent reply "Jb" <jb nowhere.com> writes:
"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.
Sep 05 2008
parent reply =?ISO-8859-15?Q?S=F6nke_Ludwig?= writes:
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.
Sep 05 2008
parent reply "Jb" <jb nowhere.com> writes:
"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.
Sep 05 2008
parent "Denis Koroskin" <2korden gmail.com> writes:
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.
Sep 06 2008