Race condition in singleton

[Pavel S]

Hi

The problem code is here (line 00120-00150):
http://www.cryptopp.com/docs/ref/misc_8h-source.html

simple_ptr is not a POD, so when multiple threads calling its
initialization at the same time, some may get not yet constructed
object or the construction may occur multimple times.

If two threads enter method at the same time, and the construction of
s_pObject is started in both (as static variable flag is not
threadsafe).
For one thread it is finished, and s_pObject.m_p = m_objectFactory();
is
executed. Then it is finished for second thread and m_p  is back NULL.

Another problem is that once a thread enters retry loop it may never
leave it. As s_objectState is not marked as volatile, the compiler
(MSVC8, Release) optimises out reads of this variable.

Why actually to initialize "without using locks" ? If the goal is
performance, then double-checked locking should be choosen.

--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the "Crypto++ Users" Google Group.
To unsubscribe, send an email to cryptopp-users-unsubscribe@....
More information about Crypto++ and this group is available at http://www.cryptopp.com.
-~----------~----~----~----~------~----~------~--~---

[Eugene Zolenko-2]

On Sep 22, 6:32 am, Pavel S <pa...@...> wrote:

> Hi
>
> The problem code is here (line 00120-00150):http://www.cryptopp.com/docs/ref/misc_8h-source.html
>
> simple_ptr is not a POD, so when multiple threads calling its
> initialization at the same time, some may get not yet constructed
> object or the construction may occur multimple times.
>
> If two threads enter method at the same time, and the construction of
> s_pObject is started in both (as static variable flag is not
> threadsafe).
> For one thread it is finished, and s_pObject.m_p = m_objectFactory();
> is
> executed. Then it is finished for second thread and m_p  is back NULL.
>
> Another problem is that once a thread enters retry loop it may never
> leave it. As s_objectState is not marked as volatile, the compiler
> (MSVC8, Release) optimises out reads of this variable.
>
> Why actually to initialize "without using locks" ? If the goal is
> performance, then double-checked locking should be choosen.

Volatile is fixed in latest version of cryptopp already.

s_pObject.m_p being NULL is bad. I thought it would just leak one
pointer in worst case...

I think main reason not to use locks is to avoid writing whole wrapper
around platform specific API for initialization of one singleton.
(Although just win32 and pthread should cover most of the platforms
cryptopp supports.)

--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the "Crypto++ Users" Google Group.
To unsubscribe, send an email to cryptopp-users-unsubscribe@....
More information about Crypto++ and this group is available at http://www.cryptopp.com.
-~----------~----~----~----~------~----~------~--~---

[Pavel S]

On Sep 23, 6:49 pm, Eugene Zolenko <zolen...@...> wrote:

> Volatile is fixed in latest version of cryptopp already.

I can see the fix in SVN trunk, though not in the latest release.

>
> s_pObject.m_p being NULL is bad. I thought it would just leak one
> pointer in worst case...

The root of problem is non-POD static, which is initialized
dynamically.
static simple_ptr<T> s_pObject;
If static non-PODs were thread-safe, we would not have the problem of
implementing singleton.

>
> I think main reason not to use locks is to avoid writing whole wrapper
> around platform specific API for initialization of one singleton.
> (Although just win32 and pthread should cover most of the platforms
> cryptopp supports.)

Handling threading of each supported platform is needed. Otherwise,
the code is not thread safe.
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the "Crypto++ Users" Google Group.
To unsubscribe, send an email to cryptopp-users-unsubscribe@....
More information about Crypto++ and this group is available at http://www.cryptopp.com.
-~----------~----~----~----~------~----~------~--~---

[Pavel S]

Just have seen another way of the problem occurrence. simple_ptr is
double constructed, and m_p = m_objectFactory happens after the last
construction (so no AV), however double construction means double
atexit destructor registration and simple_ptr pointed object is double
deleted on exit.
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the "Crypto++ Users" Google Group.
To unsubscribe, send an email to cryptopp-users-unsubscribe@....
More information about Crypto++ and this group is available at http://www.cryptopp.com.
-~----------~----~----~----~------~----~------~--~---

[Eugene Zolenko-2]

> Just have seen another way of the problem occurrence. simple_ptr is
> double constructed, and m_p = m_objectFactory happens after the last
> construction (so no AV), however double construction means double
> atexit destructor registration and simple_ptr pointed object is double
> deleted on exit.

I wonder if it is possible to hack around by forcing singleton
initialization at CRT startup this way:

template <class T, class F = NewObject<T>, int instance=0>
class Singleton
{
...
private:
        static const T* init;
};
template<class T, class F, int instance>
const T* Singleton<T, F, instance>::init = Singleton<T, F,
instance>::Ref();

CryptoPP already has some static data, and thus relies on CRT
initialization and that is guaranteed to happen singlethreadedly
(right?).

There will be one copy of init in each compilation unit, but linker
will select only one.

This will cause static init fiasco in case object's factory relies on
any global static data, and might need special care for dynamic
linking, but otherwise should guarantee singleton being always
properly initialized in main thread. (Unless you spawn threads in
constructors of you statics, then you totally deserve whatever
happens :)).

Or am I missing something?
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the "Crypto++ Users" Google Group.
To unsubscribe, send an email to cryptopp-users-unsubscribe@....
More information about Crypto++ and this group is available at http://www.cryptopp.com.
-~----------~----~----~----~------~----~------~--~---

[Eugene Zolenko-2]

Correction for the code: need to force static var instantiation and
properly call Ref(). Not sure if init in constructor can be optimized
out by sufficiently daring compiler?



template <class T, class F = NewObject<T>, int instance=0>
class Singleton
{
public:
        Singleton(F objectFactory = F())
               : m_objectFactory(objectFactory)
        { init; }
...
private:
        static const T* init;
};

template<class T, class F, int instance>
const T* Singleton<T, F, instance>::init = Singleton<T, F, instance>
().Ref();

--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the "Crypto++ Users" Google Group.
To unsubscribe, send an email to cryptopp-users-unsubscribe@....
More information about Crypto++ and this group is available at http://www.cryptopp.com.
-~----------~----~----~----~------~----~------~--~---

[Wei Dai]

I'd rather not do singleton init at startup if possible. Can you please take
a look at this version of Singleton::Ref() and see if it still has a race
condition?

template <class T, class F, int instance>
const T & Singleton<T, F, instance>::Ref(CRYPTOPP_NOINLINE_DOTDOTDOT) const
{
        static volatile simple_ptr<T> s_pObject;
        T *p = s_pObject.m_p;

        if (p)
                return *p;

        T *newObject = m_objectFactory();
        p = s_pObject.m_p;

        if (p)
        {
                delete newObject;
                return *p;
        }

        s_pObject.m_p = newObject;
        return *newObject;
}

I also changed simple_ptr's destructor to set m_p = NULL after deletion, so
double deletes should be harmless:

        ~simple_ptr() {delete m_p; m_p = NULL;}

Do I need to do something stronger to prevent the m_p = NULL from being
optimized away?


--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the "Crypto++ Users" Google Group.
To unsubscribe, send an email to cryptopp-users-unsubscribe@....
More information about Crypto++ and this group is available at http://www.cryptopp.com.
-~----------~----~----~----~------~----~------~--~---

[Wei Dai]

I got some private feedback to the effect that if two threads call Ref() at
the same time, they may get back different references, and one object may
end up being memory leaked. This is an acceptable outcome for the kind of
usage this class was designed for.

If someone wants to use the Singleton class directly in their own
application, where this isn't an acceptable outcome, they can always do
their own locking around the Ref() calls.

Please let me know if there are any other problems, like the ones that Pavel
found (thanks, btw).

--------------------------------------------------
From: "Wei Dai" <weidai@...>
Sent: Thursday, September 24, 2009 8:20 PM
To: "Crypto++ Users" <cryptopp-users@...>
Subject: Re: Race condition in singleton

>
> I'd rather not do singleton init at startup if possible. Can you please
> take
> a look at this version of Singleton::Ref() and see if it still has a race
> condition?
>
> template <class T, class F, int instance>
> const T & Singleton<T, F, instance>::Ref(CRYPTOPP_NOINLINE_DOTDOTDOT)
> const
> {
> static volatile simple_ptr<T> s_pObject;
> T *p = s_pObject.m_p;
>
> if (p)
> return *p;
>
> T *newObject = m_objectFactory();
> p = s_pObject.m_p;
>
> if (p)
> {
> delete newObject;
> return *p;
> }
>
> s_pObject.m_p = newObject;
> return *newObject;
> }
>
> I also changed simple_ptr's destructor to set m_p = NULL after deletion,
> so
> double deletes should be harmless:
>
> ~simple_ptr() {delete m_p; m_p = NULL;}
>
> Do I need to do something stronger to prevent the m_p = NULL from being
> optimized away?
>
>
> >
>

--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the "Crypto++ Users" Google Group.
To unsubscribe, send an email to cryptopp-users-unsubscribe@....
More information about Crypto++ and this group is available at http://www.cryptopp.com.
-~----------~----~----~----~------~----~------~--~---

[Pavel S]

Wei Dai wrote:

> I'd rather not do singleton init at startup if possible. Can you please take
> a look at this version of Singleton::Ref() and see if it still has a race
> condition?

Still there is

> static volatile simple_ptr<T> s_pObject;

The same AV as I've reported above.


MSVC generates something like this:
mov         eax,1
test        byte ptr [$S1 (40337Ch)],al // Check flag if object
constructed.
jne         (401027h) // Skip constructor.
or          dword ptr [$S1 (40337Ch)],eax // Set the flag that object
constructed.
... // Here goes the call to constructor.  m_p = NULL;

So, one thread may be stopped right before the constructor, then
another thread actually initializes m_p, then the first thread
continues with m_p = NULL.

Generally, static variables (except statically initialized PODs) do
not work with multithreading without synchronization.

I don't think it is possible to make a working threadsafe singleton
without at least one of: (1) locks, (2) atomic operations like
InterlockedCompareExchange, (3) static initialization, like Eugene
Zolenko suggests.
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the "Crypto++ Users" Google Group.
To unsubscribe, send an email to cryptopp-users-unsubscribe@....
More information about Crypto++ and this group is available at http://www.cryptopp.com.
-~----------~----~----~----~------~----~------~--~---

[Eugene Zolenko-2]

Pavel S:
> So, one thread may be stopped right before the constructor, then
> another thread actually initializes m_p, then the first thread
> continues with m_p = NULL.
This is not a problem in this case -- it might cause some leaks, but it
shouldn't cause NULL to be dereferenced. (Assuming all p =
s_pObject.m_p; calls are atomic and not optimized out).

Registering destructor multiple times is fine with m_p = NULL too,
because CRT teardown happens all in one thread.

Wei Dai:
> I got some private feedback to the effect that if two threads call Ref() at
> the same time, they may get back different references, and one object may
> end up being memory leaked. This is an acceptable outcome for the kind of
> usage this class was designed for.
>
>  
Ugh, I was going to send it to the list too :). I'll repost it to the
list in case somebody spots errors:


I think only problem is that it might leak if several threads passed
second check together. Which is fine, unless T has a meaningful state
(some threads will get ghost objects first time, never to be seen
again). There are no such classes in cryptopp (right? otherwise they
would themselves have synchronization problems).

Compiler can change order of those:

    T *newObject = m_objectFactory();
    p = s_pObject.m_p;

But it seems order is not important here.

Since whole pointer is volatile, I doubt compiler can assume anything
and optimize m_p = NULL;

I'm not sure if compiler could optimize p out completely. Then multiple
initialization can be a problem here:

    p = s_pObject.m_p;

    if (p)
    {
        delete newObject;
        return *p;
    }

If p is replaced by reading actual value of s_pObject.m_p, then second
thread could just finish initializing s_pObject by the time this thread
comes to return (if they both raced for static init as well). Although
this is rather opposite from optimization. Or does that break observable
behavior (3 reads from volatile memory instead of one)?

If it doesn't T* p should probably be volatile too.

--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the "Crypto++ Users" Google Group.
To unsubscribe, send an email to cryptopp-users-unsubscribe@....
More information about Crypto++ and this group is available at http://www.cryptopp.com.
-~----------~----~----~----~------~----~------~--~---

[Pavel S]

On 25 сен, 18:23, Eugene Zolenko <zolen...@...> wrote:
> Pavel S:> So, one thread may be stopped right before the constructor, then
> > another thread actually initializes m_p, then the first thread
> > continues with m_p = NULL.
>
> This is not a problem in this case -- it might cause some leaks, but it
> shouldn't cause NULL to be dereferenced. (Assuming all p =
> s_pObject.m_p; calls are atomic and not optimized out).

I see now.

> I think only problem is that it might leak if several threads passed
> second check together. Which is fine, unless T has a meaningful state
> (some threads will get ghost objects first time, never to be seen
> again). There are no such classes in cryptopp (right? otherwise they
> would themselves have synchronization problems).

I think it needs to be confirmed. A class with state may be used if
state writes are synchronzed with some mutex or with atomic
operations.

Well, I cannot point at any particular problem on MSVC, but still a
singleton without a lock or intrelocked operations looks scary :-)
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the "Crypto++ Users" Google Group.
To unsubscribe, send an email to cryptopp-users-unsubscribe@....
More information about Crypto++ and this group is available at http://www.cryptopp.com.
-~----------~----~----~----~------~----~------~--~---