Hello

After reading the Meyers& Alexandrescu article "C++ and the Perils of
Double-Checked Locking"
(http://www.aristeia.com/Papers/DDJ_Jul_Aug_2004_revised.pdf) which
claims that there is no
way of implementing double-checked locking for C++ singletons, I
wonder if the following simple
solution might do the work:

class Singleton {
public:
   static Singleton* instance();
....
private:
  Singleton();
  static Singleton * pInstance;
};

Singleton::Singleton()
{
  ... // do necessary initialisation
  pInstance = this;
}

Singleton* Singleton::instance() {
  if (pInstance == 0) {
    Lock lock;
    if (pInstance == 0) {
        new Singleton();
    }
  }
  return pInstance;
}

The issue which was highlighted in the article is related to the fact
that the line which looks like
pInstance = new Singleton;
can not be used in the Singleton::instance() function since some
compilers may generate code which would assign a value to the
pInstance variable right after allocating memory and BEFORE the
Singleton constructor is executed. It seems that a simple modification
shown above can overcome this problem. Am I wrong? Can someone comment
on that please.

Cheers,
Sergei

-- 
      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

<kse13e@yandex.ru> wrote in message
news:83b09fe9-210c-43eb-9030-ccd6096128ac@m36g2000hse.googlegroups.com...
> Hello
>
> After reading the Meyers& Alexandrescu article "C++ and the Perils of
> Double-Checked Locking"
> (http://www.aristeia.com/Papers/DDJ_Jul_Aug_2004_revised.pdf) which
> claims that there is no
> way of implementing double-checked locking for C++ singletons, I
> wonder if the following simple
> solution might do the work:

Its not going to work; there is a race-condition.

[...]

> The issue which was highlighted in the article is related to the fact
> that the line which looks like
> pInstance = new Singleton;
> can not be used in the Singleton::instance() function since some
> compilers may generate code which would assign a value to the
> pInstance variable right after allocating memory and BEFORE the
> Singleton constructor is executed. It seems that a simple modification
> shown above can overcome this problem. Am I wrong? Can someone comment
> on that please.

The problem is that your missing a memory barrier after you load from, 
and
before you store to the instance pointer. Here is sketch of 
high-performance
DCL algorithm that has all the correct barriers in place:
________________________________________________________________
template<typename T>
static T& once() {
  static T* g_this = NULL;
  static pthread_mutex_t g_lock = PTHREAD_MUTEX_INITIALIZER;
1:T* l_this = ATOMIC_LOADPTR_MBDEPENDS(&g_this);
  if (! l_this) {
    pthread_mutex_lock(&g_lock);
    if (! (l_this = g_lock)) {
      try {
2:      l_this = ATOMIC_STOREPTR_MBRELEASE(&g_this, new T);
      } catch (...) {
        pthread_mutex_unlock(&g_lock);
        throw;
      }
    }
    pthread_mutex_unlock(&g_lock);
  }
  return *l_this;
}
________________________________________________________________





Line 1 atomically load the shared pointer using trailing data-dependant
load-acquire memory barrier. Line 2 atomically stores to the shared 
pointer
using preceding store-release memory barrier:
________________________________________________________________
void* ATOMIC_LOADPTR_MBDEPENDS(void** p) {
  void* v;
  atomic {
    v = *p;
    MEMBAR #LoadStore | #LoadDepends;
  }
  return v;
}


void* ATOMIC_STOREPTR_MBRELEASE(void** p, void* v) {
  atomic {
    MEMBAR #LoadStore | #StoreStore;
    *p = v;
  }
  return v;
}
________________________________________________________________



-- 
      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

On May 14, 5:12 pm, kse...@yandex.ru wrote:
> Hello
>
> After reading the Meyers& Alexandrescu article "C++ and the Perils of
> Double-Checked Locking"
> (http://www.aristeia.com/Papers/DDJ_Jul_Aug_2004_revised.pdf) which
> claims that there is no
> way of implementing double-checked locking for C++ singletons, I
> wonder if the following simple
> solution might do the work:
>
....
>
> The issue which was highlighted in the article is related to the fact
> that the line which looks like
> pInstance = new Singleton;
> can not be used in the Singleton::instance() function since some
> compilers may generate code which would assign a value to the
> pInstance variable right after allocating memory and BEFORE the
> Singleton constructor is executed. It seems that a simple modification
> shown above can overcome this problem. Am I wrong? Can someone comment
> on that please.

The key quote from that paper:

"... people who do nothing but think about this kind of thing all day
long,
day after day, year after year. Unless you write optimizing compilers
yourself,
they are _way_ ahead of you."

Sorry, couldn't resist :)

--
  Nikolai



-- 
      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

On 14 Maj, 23:12, kse...@yandex.ru wrote:
> Singleton::Singleton()
> {
>   ... // do necessary initialisation
>   pInstance = this;
>
> }
You do nothing to prevent compiler from changing the above code into:
Singleton::Singleton()
{
     pInstance = this;
     ... // do necessary initialisation
}
This could be due to some register usage optimalizations for example.

Cheers
Sfider

-- 
      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

On 16 ???, 00:04, Marcin Swiderski <sfider.b...@gmail.com> wrote:
> On 14 Maj, 23:12, kse...@yandex.ru wrote:> Singleton::Singleton()
> > {
> >   ... // do necessary initialisation
> >   pInstance = this;
>
> > }
>
> You do nothing to prevent compiler from changing the above code into:
> Singleton::Singleton()
> {
>      pInstance = this;
>      ... // do necessary initialisation}
>


Thank you for the comment. I have realized that by reading the article
more attentively.
But what I still don't understand in it is the text on the page 11.
The authors claim that
the following code ensures proper initialisation order (the code is
already optimized):

Singleton* Singleton::instance()
{
   if (pInstance == 0) {
     Lock lock;
     if (pInstance == 0) {
         Singleton* volatile temp =
         static_cast<Singleton*>(operator new(sizeof(Singleton)));
         static_cast<volatile int&>(temp->x) = 5;
         pInstance = temp;
     }
   }
}

but then they are saying that "Unfortunately, this all does nothing
to address the first problem: C++'s abstract machine is single-
threaded,
and C++ compilers may choose to generate thread-unsafe code from
source
like the above, anyway."

I wonder how this may happen, i.e. what multi-threaded compiler might
be doing wrong about that code?

Cheers,
Sergei


-- 
      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

as commented in many of the posts and the afore mentioned paper from
Andrei Alexandrescu & Scott Meyers, the problem is the lack of
barriers. But as they comment in the very same paper:

"
At this point, one might reasonably wonder why Lock isn�t also
declared volatile. After all, it�s critical that the lock be
initialized before we try to write to pInstance or temp. Well, Lock
comes from a threading library, so we can assume it either dictates
enough restrictions in its specification or embeds enough magic in its
implementation to work without needing volatile. This is the case with
all threading libraries that we know of.
"

So, what would be the problem with the following implementation:

Singleton *pInstance;
Singleton* Singleton::instance()
{
    if (pInstance == 0) {
      Lock lock_1;
      if (pInstance == 0) {
          static Singleton* volatile temp = new Singleton();
          {
              Lock lock_2;
              pInstance = temp;
          }
      }
    }
}

if lock_2 works as a barrier against optimization, pInstance will
never be assigned before the object is correctly constructed ...

cheers,
- jan

ps.: i'm pretty sure there must be a problem, it wouldn't be that
simple, but i can't see how :)


-- 
      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

On May 30, 6:35 am, pfei...@gmail.com wrote:
> as commented in many of the posts and the afore mentioned paper from
> Andrei Alexandrescu & Scott Meyers, the problem is the lack of
> barriers. But as they comment in the very same paper:
>
> "
> At this point, one might reasonably wonder why Lock isn't also
> declared volatile. After all, it's critical that the lock be
> initialized before we try to write to pInstance or temp. Well, Lock
> comes from a threading library, so we can assume it either dictates
> enough restrictions in its specification or embeds enough magic in its
> implementation to work without needing volatile. This is the case with
> all threading libraries that we know of.
> "
>
> So, what would be the problem with the following implementation:
>
> Singleton *pInstance;
> Singleton* Singleton::instance()
> {
>     if (pInstance == 0) {
>       Lock lock_1;
>       if (pInstance == 0) {
>           static Singleton* volatile temp = new Singleton();
>           {
>               Lock lock_2;
>               pInstance = temp;
>           }
>       }
>     }
>
> }
>
> if lock_2 works as a barrier against optimization, pInstance will
> never be assigned before the object is correctly constructed ...
>

Whether you use a lock or a barrier for synchronization, you need to
use the same object on all threads that need to be synchronized. In
particular lock_2 (assuming that it is actually locking a mutex, which
is not apparent from your code) is synchronizing with nobody: only one
thread will ever acquire it, so it is useless.

Also, AFAIK, nothing in your code, assuming a relaxed memory model,
guarantees that, if pinstance is != 0, it will actually point to a
valid object (and, no, I'm not talking about the fact you didn't zero
initialize it).


--
Giovanni P. Deretta


-- 
      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

On Fri, 30 May 2008 08:50:54 -0600, gpderetta wrote:
> Whether you use a lock or a barrier for synchronization, you need to use
> the same object on all threads that need to be synchronized. 

Sorry, that is true. I failed to detail that in my pseudo-code. Let me
retry it:

Singleton *pInstance = 0;
Mutex mtx1, mtx2;

Singleton* Singleton::instance()
{
   if (pInstance == 0) {
     Lock lock_1(mtx1);
     if (pInstance == 0) {
       static Singleton* volatile temp = new Singleton();
       {
         Lock lock_2(mtx2);
         pInstance = temp;
       }
     }
  }
}


> In
> particular lock_2 (assuming that it is actually locking a mutex, which
> is not apparent from your code) is synchronizing with nobody: only one
> thread will ever acquire it, so it is useless.

Indeed it is synchronizing with nobody. But is there anyway for the
compiler to know that ? How can it know that no other thread is going to
synchronize on mtx2 ?

Well ... but maybe i'm back to the assumption that i can beat the
compiler into not optimizing something, which as A.Alexandrescu&S.Meyers
tries to discourage us from.

Although i would be surprised if today's compiler would optimize out a
lock like above -- it has to understand about all other possible threads,
and mtx2 being global, understand at link time that it is being only
locked in one place -- that means the linker has to know about the
semantics of locking.


> Also, AFAIK, nothing in your code, assuming a relaxed memory model,
> guarantees that, if pinstance is != 0, it will actually point to a valid
> object (and, no, I'm not talking about the fact you didn't zero
> initialize it).

the idea is that lock_2(mtx2) works as a barrier: that is the compiler
cannot move the assignment "pInstance = temp" across that.

If that is true, pInstance will only be != 0 after the object it points
to is properly constructed.

Otherwise many other things would break: imagine if the compiler starts
moving assignments on a shared memory structured before it actually
acquires the lock !?

thx
- jan


-- 
      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

On May 30, 8:27 pm, Jan Pfeifer <pfei...@stanford.edu> wrote:
> On Fri, 30 May 2008 08:50:54 -0600, gpderetta wrote:
> > Whether you use a lock or a barrier for synchronization, you need to use
> > the same object on all threads that need to be synchronized.
>
> Sorry, that is true. I failed to detail that in my pseudo-code. Let me
> retry it:
>
> Singleton *pInstance = 0;
> Mutex mtx1, mtx2;
>
> Singleton* Singleton::instance()
> {
>    if (pInstance == 0) {
>      Lock lock_1(mtx1);
>      if (pInstance == 0) {
>        static Singleton* volatile temp = new Singleton();
>        {
>          Lock lock_2(mtx2);
>          pInstance = temp;
>        }
>      }
>   }
>
> }
> > In
> > particular lock_2 (assuming that it is actually locking a mutex, which
> > is not apparent from your code) is synchronizing with nobody: only one
> > thread will ever acquire it, so it is useless.
>
> Indeed it is synchronizing with nobody. But is there anyway for the
> compiler to know that ? How can it know that no other thread is going to
> synchronize on mtx2 ?

Whole program analysis?

>
> Well ... but maybe i'm back to the assumption that i can beat the
> compiler into not optimizing something, which as A.Alexandrescu&S.Meyers
> tries to discourage us from.
>
> Although i would be surprised if today's compiler would optimize out a
> lock like above

compilers have surprised me many times.

> -- it has to understand about all other possible threads,
> and mtx2 being global, understand at link time that it is being only
> locked in one place -- that means the linker has to know about the
> semantics of locking.

If the linker can do link time optimizations, it certainly must. And
probably many do. For example I know for sure that there are Java
compilers that can remove useless locks. I wouldn't be surprised if C+
+ compilers did the same.

>
> > Also, AFAIK, nothing in your code, assuming a relaxed memory model,
> > guarantees that, if pinstance is != 0, it will actually point to a valid
> > object (and, no, I'm not talking about the fact you didn't zero
> > initialize it).
>
> the idea is that lock_2(mtx2) works as a barrier: that is the compiler
> cannot move the assignment "pInstance = temp" across that.
>
> If that is true, pInstance will only be != 0 after the object it points
> to is properly constructed.
>

This might fool some compilers which do not do whole program
compilation; It certainly won't fool the cpu, which is free to load
the pointed-to value before loading the pointer (yes, some cpus are
actually capable of doing that). I.e. you have to prevent reordering
(by the compiler or cpu), not only at the store, but also at the load.

> Otherwise many other things would break: imagine if the compiler starts
> moving assignments on a shared memory structured before it actually
> acquires the lock !?
>

As long as you use locks correctly AND your compiler understands them,
nothing will break.

--
Giovanni P. Deretta

-- 
      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

"Jan Pfeifer" <pfeifer@stanford.edu> wrote in message
news:g1p6n2$nl6$1@news.stanford.edu...
> On Fri, 30 May 2008 08:50:54 -0600, gpderetta wrote:
>> Whether you use a lock or a barrier for synchronization, you need to use
>> the same object on all threads that need to be synchronized.
>
> Sorry, that is true. I failed to detail that in my pseudo-code. Let me
> retry it:
>
> Singleton *pInstance = 0;
> Mutex mtx1, mtx2;
>
> Singleton* Singleton::instance()
> {
>   if (pInstance == 0) {
>     Lock lock_1(mtx1);
>     if (pInstance == 0) {
>       static Singleton* volatile temp = new Singleton();
>       {
>         Lock lock_2(mtx2);
>         pInstance = temp;
>       }
>     }
>  }
> }
[...]

Its not guaranteed to work because there are mutex implementations out there
which do not use a memory barrier after every lock procedure; here is an
example:

http://groups.google.com/group/comp.programming.threads/browse_frm/thread/22b2736484af3ca6

Therefore, you would need to store into `pInstance' _after_ mtx2 has been
acquired and released. Here is a sketch:
______________________________________________________________
#include <pthread.h>

class mutex_guard {
  pthread_mutex_t* const m_mtx;
public:
  mutex_guard(pthread_mutex_t* const mtx) : m_mtx(mtx) {
    pthread_mutex_lock(m_mtx);
  }
  ~mutex_guard() throw() {
    pthread_mutex_unlock(m_mtx);
  }
};

template<typename T>
static T& once() {
  static T* volatile g_this = NULL;
  static pthread_mutex_t g_main_mtx = PTHREAD_MUTEX_INITIALIZER;
  static pthread_mutex_t g_mem_mtx = PTHREAD_MUTEX_INITIALIZER;
  T* l_this = g_this;
  if (! l_this) {
    mutex_guard const main_lock(&g_main_mtx);
    if (! l_this) {
      l_this = new T;
      {
        mutex_guard const mem_lock(&g_mem_mtx);
      }
      g_this = l_this;
    }
  }
  return *l_this;
}

______________________________________________________________


However, its still not guaranteed to work because it has undefined behavior
according to the PThread Standard. Although, it will most certainly work in
practice on some existing platforms if the compiler does not optimize the
`g_mem_mtx' lock/unlock sequence away...


-- 
      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

"Chris Thomasson" <cristom@comcast.net> wrote in message
news:jeudncfHdoRq9d3VnZ2dnUVZ_vqdnZ2d@comcast.com...
> "Jan Pfeifer" <pfeifer@stanford.edu> wrote in message
> news:g1p6n2$nl6$1@news.stanford.edu...
>> On Fri, 30 May 2008 08:50:54 -0600, gpderetta wrote:
>>> Whether you use a lock or a barrier for synchronization, you need to use
>>> the same object on all threads that need to be synchronized.
>>
>> Sorry, that is true. I failed to detail that in my pseudo-code. Let me
>> retry it:
>>
[...]
>
> Its not guaranteed to work because there are mutex implementations out 
> there
> which do not use a memory barrier after every lock procedure; here is an
> example:
>
> http://groups.google.com/group/comp.programming.threads/browse_frm/thread/22b2736484af3ca6
>
> Therefore, you would need to store into `pInstance' _after_ mtx2 has been
> acquired and released. Here is a sketch:
> ______________________________________________________________
[...]
> ______________________________________________________________
>
>
> However, its still not guaranteed to work because it has undefined 
> behavior
> according to the PThread Standard. Although, it will most certainly work 
> in
> practice on some existing platforms if the compiler does not optimize the
> `g_mem_mtx' lock/unlock sequence away...

One platform where this is guaranteed NOT to work would be DEC Alpha. That
architecture does not have implicit data-dependant load barrier. This will
bust the initial load of `pInstance'. The Alpha requires a memory barrier
after the load...


-- 
      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

"Chris Thomasson" <cristom@comcast.net> wrote in message
news:jeudncfHdoRq9d3VnZ2dnUVZ_vqdnZ2d@comcast.com...
[...]
> ______________________________________________________________
[...]
> template<typename T>
> static T& once() {
>  static T* volatile g_this = NULL;
>  static pthread_mutex_t g_main_mtx = PTHREAD_MUTEX_INITIALIZER;
>  static pthread_mutex_t g_mem_mtx = PTHREAD_MUTEX_INITIALIZER;
>  T* l_this = g_this;
>  if (! l_this) {
>    mutex_guard const main_lock(&g_main_mtx);
>    if (! l_this) {
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
ARGH!

      if (! (l_this = g_this)) {


of course! Sorry for that non-sense.

[...]


-- 
      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]