Interlocked refcounting and possible crash

Hi there,

my problem is related to thread-safe reference counting. I know this has been asked thousands of times as I did some google search. But there is a problem which I couldn't find on the internet and which I can't solve without critical sections (?). I noticed this might happen not only in my code as I looked at others' implementations.

I have my own library with smart pointers (I know about boost, but I want to use my own), shared_ptr and instrusive_ptr which work pretty well.
Here is the important part of my shared_ptr:

Code:

template <class base>
class shared_ptr {
private:
    typedef base* P_BASE;
    typedef base& R_BASE;
    /*
        Block with ref count and a pointer, self-explanatory
    */
    class block {
    private:
        P_BASE m_ptr;
        REF_COUNT m_refcount;
    // constructor & destructor
    public:
        block(P_BASE ptr)
            : m_ptr(ptr), m_refcount(1)
        {
        }
        ~block()
        {
            if (m_ptr != NULL)
            {
                delete m_ptr;
            }
        }
    // inline methods
    public:
        inline P_BASE get_ptr() const
        {
            return m_ptr;
        }
        inline bool add_ref()
        {
            return InterlockedIncrement(&m_refcount) > 1; //return win32::interlocked_add_ref(m_refcount);
        }
        inline bool release()
        {
            return InterlockedDecrement(&m_refcount) == 0; //return win32::interlocked_release(m_refcount);
        }
    };
    typedef block* P_BLOCK;
// fields
private:
    P_BLOCK m_block;
// methods
public:
    void reset(P_BASE ptr)
    {
        if (m_block != NULL)            // if block doesnt exists
        {
            if (m_block->release())     // decrement ref count, returns true if reached 0
            {
                delete m_block;         // deletes block
            }
            m_block = NULL;
        }
        if (ptr != NULL)                // creates new block, not important
        {
            m_block = new block(ptr);
        }
    }
// operators
public:
    shared_ptr& operator = (const shared_ptr& a)
    {
        reset(NULL);
        if (a.m_block != NULL)          // (IMPORTANT #1)
        {                               // ... HERE ANOTHER THREAD MIGHT HAVE CALLED delete m_block
                                        // (for example, by calling: reset(NULL) on 'a' object
            if (a.m_block->add_ref())   // (IMPORTANT #2) CRASH ??
            {
                // ... if successfully added reference (adding 1 to 0 means it was being destructed)
                m_block = a.m_block;
            }
        }
        return *this;
    }
};

It works in similar way to boost::shared_ptr, except it has a pointer to PTR - REFCOUNT block instread of two pointers (because each shared_ptr instance occupies less memory, it's important to me).

And now:

STARTUP:

shared_ptr<int> a;
a = new int(100); // ref count is 1 now (a.m_block->m_refcount == 1)

THREAD 1:

shared_ptr<int> b = a; // attemping to increment ref count first

THREAD 2 (executing at the same time)

a = NULL;


and now:
* THREAD 1 has been suspended after executing line (IMPORTANT #1)
* THREAD 2 has successfully called release() and deleted the block
* THREAD 1 is trying to execute line (IMPORTANT #2) but a.m_block points to an already deleted block

I've been considering the following:

* make delete only block->ptr instead of whole block, but it requires additional ref count (problem wouldn't disappear?)

* make static critical section (in the template, so for each type it will be a seperate one), problem appears when there is a lot of instances or when one shared_ptr destructor calls other (for example, in deleting trees)

* EDIT: yet another idea to make threaded_ptr with critical section and use it as a main node, I think it's the best solution


Note:

There is a win32 wrapper class (win32:, because this code is going to be cross-platform and used across various compilers, so I can't use inline assembly and I would really like to make it LOCK-FREE.

Any ideas?

Thanks in advance

Not reading too much into your problem, might it be prduent to use InterlockedExchangePointer to detach the block pointer into a local variable before deleting it? That way, if another thread attempts to acquire the block at the same time it'll just get NULL.

The best bet, I think, is simply to create a new smart pointer for thread B. This will avoid racing conditions without additional coding. You could add debug statements to "lock" a shared pointer to only one thread (each instance is locked to only one thread).
This may take up sizeof(ptr) additional memory, though. The only other way I see is to maintain separate ref counts for threads, but that would potentially require a map, separate ref counters and additional runtime overhead.

Btw, some criticisms about your code:
typedef base* P_BASE;
typedef base& R_BASE;
These typedefs are just evil. They serve to obfuscate the code rather than make it cleaner. And upper case are reserved for macros!

if (m_ptr != NULL)
First off, don't use NULL! It's evil and must be phased out. Using nullptr instead.
Secondly, it is safe to delete a null pointer, so you can remove that check.

And consider using protected instead of private if someone wish to derive your class later.

Hm I think there still might be a crash.

There is a critical code:
#1 obtain block pointer and compare with NULL
#2 increment ref count

Which obviously can't be atomic with InterlockedXXX:
There might be a thread which between #1 and #2 invokes delete on block.
Maybe I am wrong.

All the operations on the block pointer and any of its data must be atomic, because several threads can access them at once. If you make sure they're atomic, there should be no problems that I can see.
But there may be an additional race condition. Once a thread is created, it may not execute at once. Therefore, there is a possibility that the pointer can go out of scope before it's acquired by the new thread. The solution, then, would be to block until the new thread has acquired the pointer safely.

Thanks for help, I haven't read the previous post before posting.
I just don't like bear: base* maybe I should just get used to it then.

It's not about a single thread, just gave a simple sample.

There is a map with pointers to read-only data
Every thread that want to read it, gets it creating its own copy of a pointer.
If program wants to exit or remove data, it simply clears the map with all the pointers and optionally waits for threads to terminate (the order is unknown).
Of course I use these pointers widely so I would like to have it done nicely.

Yet another idea is to make another pointer type, and each data that will be shared among the threads will derieve make_threaded class with refcount and critical section. That would simplify not only refcounting but also using such an

And yea, my typedefs are evil, need to change it, but as far as I know nullptr is in c++0x, I work with old compiler and old standard, and own wrappers.

If there is no simple solution to make it lock-free and atomic I will just stick to the new pointer type idea :/

The way I see it, there are two solutions:

1) Use pointers with exclusive ownership and store them in the map. Wait until all threads terminate before clearing the map. if you then populate the map before launching the threads, it should be lock and atomic free. This works if, and only if, you are using read-only and you never change ownership.

2) shared_ptr with atomic ref counting and locks when writing and reading data. And you still need to take care of the of the racing condition when creating a thread. If you need read-only, then you can skip the lock. You still need atomic ref counting, however.

As for the rest:

I just don't like bear: base* maybe I should just get used to it then.

I would recommend you do get used to it.

And yea, my typedefs are evil, need to change it, but as far as I know nullptr is in c++0x, I work with old compiler and old standard, and own wrappers.

Any reason you can't use a newer version of the compiler? They work with old code, you know.

Any reason you can't use a newer version of the compiler? They work with old code, you know.

There is none of those which I am used to (GCC is experimental for example) thus I consider it more portable for myself atm.

1) Use pointers with exclusive ownership and store them in the map. Wait until all threads terminate before clearing the map. if you then populate the map before launching the threads, it should be lock and atomic free. This works if, and only if, you are using read-only and you never change ownership.

Map is placed in a DLL which is used by other DLLs exclusively (if it matters?)

2) shared_ptr with atomic ref counting and locks when writing and reading data. And you still need to take care of the of the racing condition when creating a thread. If you need read-only, then you can skip the lock. You still need atomic ref counting, however.

I decided to stick to this idea, but with another class and lock that can be used also to modify, so shared_ptr can be faster and for local thread usage only:

Code:

class make_threaded {
private:
    mutable refcount_t m_refcount;
    mutable win_critical_section m_lock;
// constructors & destructor
public:
    make_threaded()
        : m_refcount(0)
    {
    }
    make_threaded(const make_threaded& a)
        : m_refcount(0)
    {
    }
    virtual ~make_threaded()
    {
    }
// operators
public:
    make_threaded& operator = (const make_threaded& a)
    {
        return *this;
    }
// inline methods
public:
    inline void add_ref() const
    {
        m_refcount++;
    }
    inline bool release() const
    {
        return (--m_refcount) == 0;
    }
    inline win_critical_section& get_lock() const
    {
        return m_lock;
    }
};

Originally Posted by kmdv

There is none of those which I am used to (GCC is experimental for example) thus I consider it more portable for myself atm.

So you are using some compiler that is not Visual C++ or GCC?

Map is placed in a DLL which is used by other DLLs exclusively (if it matters?)

DLL exports make things slightly more complicated, but the basic idea would be the same. You just have to make sure that the pointers are valid as long as the threads use them because they cannot keep the pointers alive with this idea.

I decided to stick to this idea, but with another class and lock that can be used also to modify, so shared_ptr can be faster and for local thread usage only:

So what is the point of the class? All I see is a wrapper that uses manual ref counting.

So you are using some compiler that is not Visual C++ or GCC?

Borland C++ and GCC

DLL exports make things slightly more complicated, but the basic idea would be the same. You just have to make sure that the pointers are valid as long as the threads use them because they cannot keep the pointers alive with this idea.

Nevermind, I thought that DLL might be unloaded before destructor cleanup is done, but that would be rather stupid.

So what is the point of the class? All I see is a wrapper that uses manual ref counting.

You said about shared_ptr with lock needed, I didn't know how exactly it would be done so I pasted it here.

Anyway, problem is solved, so thank you very much for help.

I would avoid Borland C++. It is obviously not very good compared to other free compilers (such as GCC and Visual C++ which both have C++0x support).
I was merely wondering how you intended to use that class or why you would want to use a class for this special purposes at all? Why not just put the critical section and ref count inside the pointer class itself? Because it seemed the class did little--if anything--good.

I would avoid Borland C++. It is obviously not very good compared to other free compilers (such as GCC and Visual C++ which both have C++0x support).

You are right, but I am very used to it, and I am slowly getting used to the others. C++0x Support in GCC - GNU Project - Free Software Foundation (FSF)
and it hasn't full C++0x support.

Why not just put the critical section and ref count inside the pointer class itself

Ref count inside object does not require additional heap operations.
Always 1 critical section per critical data, especially when I want to make a lot of pointers.
Additionally, making this class virtual avoids deleting pointers of incomplete types (resulting in undefined behaviour) that I have already encountered.

why you would want to use a class for this special purposes at all?

I want to have a pure and widely used garbage collector. Boost's implementation has a couple of things that annoy me or I just dont need.

Because it seemed the class did little--if anything--good

That's exactly what I need and will help me a lot

Originally Posted by kmdv

You are right, but I am very used to it, and I am slowly getting used to the others. C++0x Support in GCC - GNU Project - Free Software Foundation (FSF)
and it hasn't full C++0x support.

But like you see, it's slowly getting there
So why not start using them?

As for the rest... I didn't question your need for a smart pointer. I questioned the need for wrapping your critical section in a make_threaded class.
Those might have been better put in the Block of your smart pointer class and handled from there, because it seems that your make_threaded class provides no additional benefits.

Those might have been better put in the Block of your smart pointer class and handled from there, because it seems that your make_threaded class provides no additional benefits.

I was so lost in thoughts that I forgot about my previous problem. Of course adding critical section to block is the only way to do it, otherwise I would access section which does not exist.. thanks.