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
next sibling 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
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 "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
prev sibling 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=



 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 "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