Thread overview | |||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|
|
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? | ||||
---|---|---|---|---|
| ||||
Posted in reply to Bill Baxter | 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? | ||||
---|---|---|---|---|
| ||||
Posted in reply to Sönke Ludwig | 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? | ||||
---|---|---|---|---|
| ||||
Posted in reply to Jason House | 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? | ||||
---|---|---|---|---|
| ||||
Posted in reply to Jason House | 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? | ||||
---|---|---|---|---|
| ||||
Posted in reply to Sönke Ludwig | "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? | ||||
---|---|---|---|---|
| ||||
Posted in reply to Jb | 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? | ||||
---|---|---|---|---|
| ||||
Posted in reply to Sönke Ludwig | "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? | ||||
---|---|---|---|---|
| ||||
Posted in reply to Jb | 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.
|
Copyright © 1999-2021 by the D Language Foundation