Double checked locking

[claudiu]

Hi,

I have a question on the double checked locking. The classic
implementation (shamelessly copied from Scott Meyers' and Andrei
Alexandrescu's article)

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

Singleton* Singleton::instance() {
if (pInstance == 0) { // 1st test
Lock lock;
if (pInstance == 0) { // 2nd test
pInstance = new Singleton;
}
}
return pInstance;
}

is unsafe as there is no guarantee that the assignment of pInstance is
done after the constructor of Singleton is completed (http://
www.aristeia.com/Papers/DDJ_Jul_Aug_2004_revised.pdf).

However, if instead of the simple assignment one would use something
like:

void assign(Singleton*& to, Singleton* from){
to = from;
}

assign(pInstance, new Singleton);

would this become safe?

As far as I know, the standard requires all the parameters passed to a
function to be evaluated before the function is being called. Would
the memory allocation (without the call to the constructor) be
considered "enough" by an optimizing compiler so that the pointer
returned by it is passed to the assign function before the constructor
call is completed?

Regards,
Claudiu

 

[Chris Thomasson]

Hi, [...]

would this become safe?

No.

[...]

You need to worry about optimizations performed by the compiler and the
hardware:

http://appcore.home.comcast.net/vzdoc/atomic/static-init/
(look in section 2...)

http://groups.google.com/group/comp.programming.threads/msg/423df394a0370fa6


Here is a solution:

http://groups.google.com/group/comp.programming.threads/msg/ccb69ac2f850f453


Please note that the following functions in that example:

atomic_loadptr_depends
atomic_storeptr_release

should be implemented in assembly language. Here is example of that:

http://appcore.home.comcast.net/appcore/src/cpu/i686/ac_i686_gcc_asm.html


Here is another solution:

http://groups.google.com/group/comp.programming.threads/msg/8ae09f9e9bea21b9

http://groups.google.com/group/comp.programming.threads/msg/f2c59ced973e75dd


______________________________

Does that help you understand this stuff a little better?

 

[Chris Thomasson]

http://appcore.home.comcast.net/vzdoc/atomic/static-init/
(look in section 2...)

actually sections 2.1 and 2.2

 

[claudiu]

Hi,

[...]

would this become safe?

No.

[...]

You need to worry about optimizations performed by the compiler and the
hardware:

http://appcore.home.comcast.net/vzdoc/atomic/static-init/
(look in section 2...)

http://groups.google.com/group/comp.programming.threads/msg/423df394a...

Here is a solution:

http://groups.google.com/group/comp.programming.threads/msg/ccb69ac2f...

Please note that the following functions in that example:

atomic_loadptr_depends
atomic_storeptr_release

should be implemented in assembly language. Here is example of that:

http://appcore.home.comcast.net/appcore/src/cpu/i686/ac_i686_gcc_asm....

Here is another solution:

http://groups.google.com/group/comp.programming.threads/msg/8ae09f9e9...

http://groups.google.com/group/comp.programming.threads/msg/f2c59ced9...

______________________________

Does that help you understand this stuff a little better?

Thanks Chris, this is very useful. However, I was more interested in
how much is a compiler allowed to bend the standard when optimising.
In this case, the call to new Singleton should be completed before the
call to the assign function but then I guess if assign is inlined
there is no longer a function call present so the requirement goes
away.

Regards,
Claudiu

 

[Rolf Magnus]

Thanks Chris, this is very useful. However, I was more interested in
how much is a compiler allowed to bend the standard when optimising.

It may do anything it wants as long as a conforming program behaves as if
the compiler was doing exactly what the standard says. That's therefore
called the as-if rule. However, note that C++ doesn't support
multithreading so this only applies to single-threaded programs. Once
multi-threading or interrupt handling comes into play, you have to deal
with a lot more things. In a single-threaded program, instruction
reordering is not an issue, but with multiple threads of execution, that's
different.

 

[Pete Becker]

if assign is inlined
there is no longer a function call present so the requirement goes
away.

No, inlining a function is not allowed to change the function's
semantics. The fundamental problem with double checked locking is
assuring that every thread that looks at that pointer sees all the
updated values. There is nothing in the C++ standard that guarantees
this, although many people think that marking the pointer "volatile"
will magically make it work. It might, but only if your compiler makes
that promise.

--

-- Pete
Roundhouse Consulting, Ltd. (www.versatilecoding.com)
Author of "The Standard C++ Library Extensions: a Tutorial and
Reference." (www.petebecker.com/tr1book)

 

[Bo Persson]

claudiu wrote:
:::
::: Does that help you understand this stuff a little better?
::
::
:: Thanks Chris, this is very useful. However, I was more interested
:: in how much is a compiler allowed to bend the standard when
:: optimising.

Nothing at all. The standard contains a few explicit permissions, but
that's it.

:: In this case, the call to new Singleton should be
:: completed before the call to the assign function but then I guess
:: if assign is inlined there is no longer a function call present so
:: the requirement goes away.

No, the rules don't go away. The code has to perform "as-if" the
compiler followed all the rules. But, how do you check that in a
single-threaded program?

There are NO language rules for multi-threaded programs! Catch-22.


Bo Persson

 

[Chris Thomasson]

Hi,

[...]

would this become safe?

No.

[...]

You need to worry about optimizations performed by the compiler and the
hardware: [...]
______________________________

Does that help you understand this stuff a little better?

Thanks Chris, this is very useful. However, I was more interested in
how much is a compiler allowed to bend the standard when optimising.

The optimization factor is an implementation detail. The resulting program
just has to run correctly.

In this case, the call to new Singleton should be completed before the
call to the assign function but then I guess if assign is inlined
there is no longer a function call present so the requirement goes
away.

Okay. Your asking about a compiler barrier. Link-time optimizations aside
for a moment, you can usually get something that is analogous to a compiler
barrier when you make a call to an unknown external function that exists in
an external unknown library. For instance, calls into the following
function:


extern "C" void my_external_unknown_function(void*);


Should make a compiler be very pessimistic wrt any optimizations it can
perform:

http://groups.google.com/group/comp.programming.threads/msg/b6cca83320555c35
(read this whole message...)


In fact... Read this whole thread started by Scott Meyers who is a highly
respected author:

http://groups.google.com/group/comp.programming.threads/browse_frm/thread/29ea516c5581240e
(I posted as SenderX in that thread...)


Once you understand the basics of compiler barriers, then you need to
understand the basics of limiting the optimizations that can be performed by
the hardware. This ability usually comes in the form of special instructions
commonly referred to as 'memory barriers'. However, that topic is a whole
different can of worms!

;^)


This type of discussion would be more on topic over in
'comp.programming.threads':

http://groups.google.com/group/comp.programming.threads/topics

 

[Chris Thomasson]

[...]

Okay. Your asking about a compiler barrier. Link-time optimizations aside
for a moment, you can usually get something that is analogous to a
compiler barrier when you make a call to an unknown external function that
exists in an external unknown library. For instance, calls into the
following function:


extern "C" void my_external_unknown_function(void*);

Sometimes you can use the volatile keyword to help block some compile time
optimizations... On GCC, you can use a volatile clobbers memory statement:

http://www.dis.com/gnu/gcc/Extended-Asm.html

You just have to carefully read through your compiler documentation.