| Date: | March 8, 2004 / year-entry #88 |
| Tags: | code |
| Orig Link: | https://blogs.msdn.microsoft.com/oldnewthing/20040308-00/?p=40363 |
| Comments: | 49 |
| Summary: | How the design of the C++ language subverts thread safety. |
[Note: After this article was written, the C++ standard has been revised. Starting in C++11, scoped static initialization is now thread-safe, but it comes with a cost: Reentrancy now invokes undefined behavior.] The rule for static variables at block scope (as opposed to static variables with global scope) is that they are initialized the first time execution reaches their declaration. Find the race condition:
int ComputeSomething()
{
static int cachedResult = ComputeSomethingSlowly();
return cachedResult;
}
The intent of this code is to compute something expensive the first time the function is called, and then cache the result to be returned by future calls to the function. A variation on this basic technique is is advocated by this web site to avoid the "static initialization order fiasco". (Said fiasco is well-described on that page so I encourage you to read it and understand it.) The problem is that this code is not thread-safe. Statics with local scope are internally converted by the compiler into something like this:
int ComputeSomething()
{
static bool cachedResult_computed = false;
static int cachedResult;
if (!cachedResult_computed) {
cachedResult_computed = true;
cachedResult = ComputeSomethingSlowly();
}
return cachedResult;
}
Now the race condition is easier to see. Suppose two threads both call this function for the first time. The first thread gets as far as setting cachedResult_computed = true, and then gets pre-empted. The second thread now sees that cachedResult_computed is true and skips over the body of the "if" branch and returns an uninitialized variable. What you see here is not a compiler bug. This behavior is required by the C++ standard. You can write variations on this theme to create even worse problems:
class Something { ... };
int ComputeSomething()
{
static Something s;
return s.ComputeIt();
}
This gets rewritten internally as (this time, using pseudo-C++):
class Something { ... };
int ComputeSomething()
{
static bool s_constructed = false;
static uninitialized Something s;
if (!s_constructed) {
s_constructed = true;
new(&s) Something; // construct it
atexit(DestructS);
}
return s.ComputeIt();
}
// Destruct s at process termination
void DestructS()
{
ComputeSomething::s.~Something();
}
Notice that there are multiple race conditions here. As before, it's possible for one thread to run ahead of the other thread and use "s" before it has been constructed. Even worse, it's possible for the first thread to get pre-empted immediately after testing s_constructed but before setting it to "true". In this case, the object s gets double-constructed and double-destructed. That can't be good. But wait, that's not all. Not look at what happens if you have two runtime-initialized local statics:
class Something { ... };
int ComputeSomething()
{
static Something s(0);
static Something t(1);
return s.ComputeIt() + t.ComputeIt();
}
This is converted by the compiler into the following pseudo-C++:
class Something { ... };
int ComputeSomething()
{
static char constructed = 0;
static uninitialized Something s;
if (!(constructed & 1)) {
constructed |= 1;
new(&s) Something; // construct it
atexit(DestructS);
}
static uninitialized Something t;
if (!(constructed & 2)) {
constructed |= 2;
new(&t) Something; // construct it
atexit(DestructT);
}
return s.ComputeIt() + t.ComputeIt();
}
To save space, the compiler placed the two "x_constructed" variables into a bitfield. Now there are multiple non-interlocked read-modify-store operations on the variable "constructed". Now consider what happens if one thread attempts to execute "constructed |= 1" at the same time another thread attempts to execute "constructed |= 2". On an x86, the statements likely assemble into or constructed, 1 ... or constructed, 2 without any "lock" prefixes. On multiprocessor machines, it is possible for the two stores both to read the old value and clobber each other with conflicting values. On ia64 and alpha, this clobbering is much more obvious since they do not have a single read-modify-store instruction; the three steps must be explicitly coded: ldl t1,0(a0) ; load addl t1,1,t1 ; modify stl t1,1,0(a0) ; store If the thread gets pre-empted between the load and the store, the value stored may no longer agree with the value being overwritten. So now consider the following insane sequence of execution:
Now, you might think you can wrap the runtime initialization in a critical section:
int ComputeSomething()
{
EnterCriticalSection(...);
static int cachedResult = ComputeSomethingSlowly();
LeaveCriticalSection(...);
return cachedResult;
}
Because now you've placed the one-time initialization inside a critical section and made it thread-safe. But what if the second call comes from within the same thread? ("We've traced the call; it's coming from inside the thread!") This can happen if ComputeSomethingSlowly() itself calls ComputeSomething(), perhaps indirectly. Since that thread already owns the critical section, the code enter it just fine and you once again end up returning an uninitialized variable. Conclusion: When you see runtime initialization of a local static variable, be very concerned. |
Comments (49)
Comments are closed. |
Is this true of statics in C# and Shared vars in VB.Net as well?
Why does C++ require it be done this way? Why not set the _constructed value to true after the call to the constructor? (That wouldn’t alleviate the other race conditions, so I guess it wouldn’t really matter, though.)
How would you recommend block-level statics be initialized (for instance to achieve the "cache an expensive operation" goal) instead?
Well this is actually about global static initialization, but this seems like the appropriate place to ask it:
I am working on a contrl library that must run on both 9x and NT and there are a lot of functions in Win32 that are indirectly dependent on the character type (such as DefWindowProc). I understand why this is the case and if I am running on Win9x I register my control classes with RegisterClassA (and use RegisterClassW on NTx). So what I really want is to call the correct version of DefWindowProc (amongst others) depending on the platform which I do with the following code:
extern "C" LRESULT (WINAPI *NcDefWindowProc)(HWND, UINT, WPARAM, LPARAM);
#ifdef DefWindowProc
#undef DefWindowProc
#endif // DefWindowProc
#define DefWindowProc NcDefWindowProc
then I set NcDefWindowProc to DefWindowProcA and in my DllMain I set NcDefWindowProc to DefWindowProcW if I’m on NT. My question is, is this safe? I’m not calling the functions in DllMain and the pointers should be to locations in my import table, but there is just something that makes me feel uneasy about all this. Will those functions be relocated and my pointers invalidated?
Hmm
So in the same vein the following pattern for a singleton instance of some class is also not thread safe.
class CSomeClass
{
public:
static CSomeClass& GetInstance()
{
static CSomeClass instance;
return instance;
}
………
};
CSomeClass::GetInstance().SomeMethod();
Eric: A critical section will "work" as long as the function isn’t re-entered. If it is, then you are completely stuck. You want to use this local static which is in the middle of being constructed *by your caller*. You can’t "wait" since your caller is waiting for you!
Lonnie: The best way to be sure is to stare at the codegen. I suspect this merely copies values around and doesn’t actually call GetProcAddress, so you’ll be fine.
(The function can’t get relocated because that would break people who call GetProcAddress.)
So, how does one protect oneself from trying to walk before being born? What if we protect the function with something stronger than a critical section or mutex, such as a semaphore with maximum = initial = 1? This way, if the function tries to indirectly reuse itself, it will just peacefully hang, not explode all over the place. Maybe, with clever use of synchronization primitives, the function can even detect that it is being called during initialization from the same thread, and “request the runtime to terminate it in a strange, weird, perverse, counternatural way”?
Centaur: Looks like you answered your own question. If that’s what you want, then go ahead and write it that way.
So I guess using static variables in recursive functions is a Really Bad Thing. ;)
Sean: I presume that’s why most Singleton implementations place a critical section around the GetInstance() function. As long as you don’t (directly or indirectly) call GetInstance() from within the GetInstance() function, you won’t block yourself, and any other threads will see the critical section and wait.
good article.
Good article, Raymond. Writing thread-safe C++ code can be tricky since there’s no language-level support. Everyone is familiar with Critcal Sections and the Wait* functions, but I wonder if you can point to guarantees of what memory synchronization these functions provide. I had just assumed they did the Right Thing, but this thread (http://groups.google.com/groups?q=g:thl370189423d&dq=&hl=en&lr=&ie=UTF-8&selm=d6652001.0403040142.8afd534%40posting.google.com) in c.l.c++.m made me realized that I was just assuming.
Thanks
A way to work around this may be to add a class that will register a function call to a linked list. Call into at process start, before creating threads… Something like this (which I just wrote off the top of my head)
class CInitializer
{
public:
CInitializer();
virtual void Function() = 0;
static void CallFunctions();
private:
static CInitializer *sFirst;
CInitializer *mNext;
};
// implemenation
CInitializer *CInitializer::sFirst = NULL;
CInitializer::CInitializer()
: mNext( sFirst )
{
sFirst = this;
}
void CInitializer::CallFunctions()
{
for ( CInitializer *at = sFirst; at; at = at->mNext )
{
at->Function();
}
}
// sub class
int const Zero()
{
static int zero = 0;
return zero;
}
namespace
{
class CZeroInitializer : public CInitializer
{
public:
void Function()
{
Zero();
}
};
CZeroInitializer junk;
(junk);
}
(I assure you that I had proper spacing in the text I typed above… Guess I needed to put some (amp)nbsp;’s in there instead. Sorry.)
But then you lose the "don’t initialize until the function is called for the first time" feature, and you’re back to the "static initialization order fiasco".
Raymond:
Nono, look at it again. You get the call being initialzed the first time the function is called. This just makes sure that all the functions are called once before any real work is done. See, I have Zero() with a static in it. Zero() would be a utility function that returns zero. I just make it a dumb example with a static that gets used.
So static initialization works fine and you have a guarantee of everything being done before the threads start.
Of course, this doesn’t work for statics that do a lot of heavy lifting that may depend on other threads being started and it takes discipline to remember to write such a class to do that.
Okay I guess I don’t understand who calls CallFunctions().
main() does, before any threads were created.
So let’s say you have the classic static situation. Where a static depends on another static:
int Func1()
{
static int foo = 12345;
return foo;
}
int Func2()
{
static int foo = Func1() * 2;
return foo;
}
Now, you could set up an initializer class for each that just calls Func1 and Func2. At application startup, CallFunctions() gets called before any threads are created, which calls each of these. Now, it doesn’t matter what order they get called in. since Func2() guarantees Func1() gets called. But since this happens before any other threads are created, you’ve guaranteed that subsequent calls cannoy have any of the problems you describe in your article.
I’m just pointing out that with careful engineering, one can work around this shortcoming and still maintain the practice of using statics in this way.
But this loses the "delay initialization until the first time the function is called" feature. When main() calls CallFunctions(), all the CInitializer::Function()s get called, even if for example the function that uses the variable "junk" is never called.
Well yeah, but the only real REASON to do that delayed initialization 99% of the time is to fix interdependant systems, and to make link order a non issue. That’s the problem that this solves. And it solves it in a way that you really don’t have to change any existing code at all, just shoehorn a small bit of code when you use the feature. You could even macro-ize it to one line.
Speed isn’t the concern most of the time here, link order is.
For more heavyweight operations (like non-trivial singletons and such), yeah, critical sections should be used.
I’ve seen code that relied on the delayed initialization – for example, function X is always called after function Y succeeds; function Y sets up some global state that function X uses in its static initializer. (For example, maybe function Y registers a clipboard format name and function X uses it.)
> What you see here is not a compiler bug.
> This behavior is required by the C++
> standard.
Sorry I haven’t kept up with the standards this millennium, but I was still surprised to see this. When did the C++ standard start imposing requirements on threading behavior?
If it were C, the compiler would be allowed to add critical sections automatically around each initialization. Of course the present behavior still isn’t a compiler bug, but safer behavior wouldn’t be a compiler bug either, because the C standard doesn’t impose any requirements on threading behavior. (Well … it’s possible to interpret the C standard as outlawing threads altogether :-)
Of course my personal preference is for unsafe code to get noisy diagnostics during development, rather than get the silent treatment. But in case of silence, it’s surely better for the result to be made safe than unsafe.
Hm, it looks like this section was changed by TC1. There’s a new sentence that says, "If control re-enters the declaration (recursively) while the object is being initialized, the behavior is undefined." And it gives exactly the same example that the old spec did, but now instead of explaining the behavior (under the old rules), it declares the results to be undefined!
The word "(recursively)", despite the parentheses, seems to be a reminder that the only method known to the standard for re-entering is recursion, i.e. still in a single thread. It still seems, in this case at least, that the standard doesn’t restrict compiler behavior in the presence of multiple threads.
Does the C++ standard really mention threads? The C standard (1999 and its TC1 in 2001) still doesn’t.
Correct, there is no mention of threads in the C or C++ standards (that I can find). My initial remarks were based on my findings in the pre-TC1 C++ standard that mandated the described behavior even in the absence of threading. Coincidentally, my copy of the post-TC1 C++ standard arrived late this morning, after I had written the original article.
3/8/2004 5:17 PM Raymond Chen
> My initial remarks were based on my findings
> in the pre-TC1 C++ standard that mandated
> the described behavior even in the absence
> of threading.
It seems that the pre-TC1 C++ standard mandated the described behavior *ONLY* in the absence of threading. It seems that the C++ standard always allowed the compiler to be noisy and/or to generate code that would be thread-safe in the presence of threading.
The existing behavior still isn’t and wasn’t a bug, but it still seems to have been unnecessary and unfriendly all along.
Do you have a machine-readable version of the C++ standard? In the C standard for 1999, I searched the .pdf file for the word "thread" and there were no hits. I’m not in the mood to pay ISO’s price for the C++ standard.
My (new) C++ standard is a big heavy book, $65 from Amazon.com.
> I’ve seen code that relied on the delayed
> initialization – for example, function X is
> always called after function Y succeeds;
> function Y sets up some global state that
> function X uses in its static initializer. (For
> example, maybe function Y registers a clipboard
> format name and function X uses it.)
Ugh, well that’s just plain bad design in my opinion. If you’re initializing a static based on state like that, you’re asking for trouble. But in this case, you’d just not use the construct I’m talking about.
Ideally though, in your example, one could have a Function X call into Function Y to assert its initialization before proceeding. Writing code that has this implicit dependance on ordering like this is just asking for trouble. Especially if calling Function X before calling Function Y causes Function X to be irreparably harmed (if it’s indeed using a static).
Sure, it’s not exactly great design. But it’s kind of interesting that something that at first glance seems like it should be trivial actually turns out to be something that you need to design a non-trivial mechanism to handle properly.
I think Raymond’s points are that (a) this sort of thing is easy to screw up, and that C/C++ doesn’t exactly go out of its way to help you out, and (b) some of the standard techniques for avoiding the problem fail in subtle ways when you consider multi-threaded scenarios.
Isn’t the main point that even with the common C++ idioms for protecting static initialization the C++ standard still leaves it to implementation to define specific primitives to protect static initialization in multi-threaded scenarios.
It seems to me there was a recent comp.lang.c++.moderated thread on further issues involving CV qualified data.
Most software I have worked on has been single threaded most of the time. E.g. we may start a thread when user chooses an option from a menu to so some background work.
In server apps this is not always the case; however even in a server app most initialization needs to be done at start up time and hence can be done on a single thread.
Yes we do need to be careful with this, but in real life I have only met problems with it a few times. However when I was a C++ coder, I mat problems with memory management most weeks.
Anyway as soon as you start using threads, all bets are of with C++, as the C++ design and standard never considered them.
> What if we protect the function with something stronger than a critical section or mutex, such as a semaphore with maximum = initial = 1? This way, if the function tries to indirectly reuse itself, it will just peacefully hang, not explode all over the place.
Many people actually think that by default all locks should be non-recursive (like POSIX mutexes). I agree with them – the world would be a better place if poorly written multithreaded code would peacefully hang on a non-recursive mutex instead of exploding because of unexpected recursion (or STA-type reentracy).
Norman, see http://webstore.ansi.org/ansidocstore/product.asp?sku=INCITS%2FISO%2FIEC+14882%2D2003 . This is the INCITS edition of the latest C++ standard which has the same text and only costs $18.
Brian, the situation is not quite as bad as James Kanze thinks. He’s not really up-to-date on Windows programming. However, he’s quite right that you can’t trust volatile. If you’re concerned about static initialisation in DLLs, as he was, see http://weblogs.asp.net/oldnewthing/archive/2004/01/27/63401.aspx
and http://weblogs.asp.net/oldnewthing/archive/2004/01/28/63880.aspx .
The real problem is simply that the MSFT C++ compiler is lame. The C++ Standard says no such thing about forcing the implementation to produce thread-unsafe code. The VMS C++ compiler, for example, automatically inserts spinlocks around the initialization of static local objects, so they are perfectly thread-safe. (There has even been discussion on usenet about how to define custom commands to direct the compiler whether you want synchronized or unsynchronized initialization of each static local.)
PS, the real C++ Standard ISO 14882 is an $18 PDF document available directly from ISO or ANSI websites.
As I already noted, the previous C++ standard required the function to be re-entrant and to SKIP static intialization if re-entered. So Visual Studio’s implementation was compliant with the old C++ standard (and the VMS C++ complier was in violation). But TC1 changed that and now re-entrancy during static initialization has been declared "undefined".
Did nobody complain to VMS that their compiler was in violation of the original C++ standard?
I don’t think so. Here is a snippet from the ISO IEC 14882-1998 (pre-TC1) version of the Standard (my PDF file is dated 6/17/2001):
6.7/4 (relevant to static local object initialization):
"[..] Otherwise such an object is initialized the first time control passes through its declaration; such an
object is considered initialized upon the completion of its initialization. [..] If control reenters
the declaration (recursively) while the object is being initialized, the behavior
is undefined."
Of course the VMS compiler has some problems of its own, but this is not one of them. :-) Are you thinking of the ARM, maybe?
Duh you’re right, it’s the ARM that says that recursion is allowed.
Ben and Raymond, I guess what I’m wondering is where is the guarantee that the proposed solution (of adding a Critical Section) will work, especially in the face of multiple processors? If we add the Critical Section code into Raymond’s expansion, we get something like:
int ComputeSomething()
{
EnterCriticalSection(…);
static bool cachedResult_computed = false;
static int cachedResult;
if (!cachedResult_computed) {
cachedResult_computed = true;
cachedResult = ComputeSomethingSlowly();
}
LeaveCriticalSection(…);
return cachedResult;
}
It must be guaranteed then that the read of cachedResult_computed pulls from main memory, not just from local cache, right? The documentation for Critical Sections (and Mutexes, etc) all speak very vaguely about protected resources and don’t say much about specific results of using a Critical Section. Or am I just being dense? (don’t be afraid to say so, it wouldn’t be the first or last time). Again, I don’t mean to say that I think the proposed solution is wrong, just that I’m curious about how you know it’s right.
Thanks,
Brian
3/9/2004 10:21 AM Ben Hutchings:
> Norman, see
> http://webstore.ansi.org/ansidocstore/product.asp?sku=INCITS%2FISO%2FIEC+14882%2D2003
Thank you very much!
3/9/2004 11:10 AM The Sim:
> PS, the real C++ Standard ISO 14882 is an
> $18 PDF document available directly from ISO
> or ANSI websites.
Wrong. It’s an $18 document from ANSI as Mr. Hutchings kindly informed me. From ISO it’s 364 Swiss francs, SIXTEEN TIMES the price that ANSI charges. Now I’ll guess I probably should have bought my C standard (also PDF) from ANSI instead of directly from ISO. By the way, ISO said I should buy the C standard from JIS and JIS said I should buy it from ISO. JIS really doesn’t sell it so ISO sold it to me. Some time later ISO sent me a virus.
By the way, although ISO delivered the C standard itself by e-mailing a URL for a downloadable PDF file, they sent the purchase receipt as an attachment in an e-mail message itself. An attachment in an e-mail message itself is the exact same technique as the Sobig.F that they sent me some time later. I thought I knew which one was safe to open, but I was wrong. Of course I did know which one wasn’t safe to open (I knew not to open the .pif attachment), but it still seems I was wrong. A while after that, I read that it is possible for PDF files to contain code that will be executed by Acrobat Reader.
The memory coherency requirements of EnterCriticalSection and LeaveCriticalSection are rather complicated to express. In brief, my understanding is that EnterCriticalSection establishes a barrier with acquire semantics, and Leave establishes a barrier with release semantics.
Acquire semantics = "no memory access after the Enter will be reordered before it (however memory accesses before the Enter may be delayed to after it)."
Release semantics = "no memory access before the Leave will be delayed to after it (however memory access after the Leave may be reordered to before it)."
The heavier synchronization objects (the ones that use WaitForSingleObject) establish both acquire and release barriers (since it is not obvious to the OS whether you are entering or leaving).
Guysd, you might want to look at http://discuss.fogcreek.com/joelonsoftware/default.asp?cmd=show&ixPost=122243&ixReplies=2 Someone pointed the price discrepance out there only yesterday (coincidence?) and someone said that it might be that you need to be members of INCITS to qualify for the cheaper price.
Brian: The objects called "critical sections" in Win32 are really process-local mutexes (critical sections are really sections of code in which the thread needs to hold a mutex, not the mutexes themselves). It’s part of the nature of mutexes that they synchronise access to memory, and you can find my explanation of how that’s done at http://groups.google.com/groups?selm=slrnc3clpp.p3b.do-not-spam-benh%40shadbolt.i.decadentplace.org.uk .
If the memory caches of multiple processors in a shared-memory system could not be kept mostly synchronised then they would have to be completely flushed at each synchronisation point which would take of the order of a whole millisecond and is simply unacceptable. Such systems instead have cache coherency protocols that take care of this. Memory synchronisation then only requires flushing the write queue and/or invalidating the read queue in the processor cores. These queues are relatively short.
Moi: Please don’t pay attention to idle speculation. No-one on comp.std.c++ has mentioned such a restriction, and I was able to take a purchase of the document as far as being prompted for CC details. (I haven’t bothered to buy it since I have the last version and Andrew Koenig’s list of changes.)
I bought the INCITS version for US$18 (thank you again Mr. Hutchings). If I understand correctly, INCITS members can buy the INCITS version for US$13.50.
As far as I can tell, C++ compilers always had freedom to provide thread safety and/or warn noisily and/or be unfriendly as they have been, in the presence of threads. As far as I can tell, the C++ standard only applies itself to single-threaded programs and implementations.
A good article; it is point you need to be aware of. However the fix is very simple. If you are using local static variables to avoid the "static initialisation order fiasco", you may wish to add a static reference to the function to ensure that it is called during static initialisation.
e.g. If you have:-
int ComputeSomething()
{
static int cachedResult = ComputeSomethingSlowly();
return cachedResult;
}
Then add:-
static int never_used = ComputeSomething();
This guarantees that the first call will be during static initialisation. Note that once the first call is complete then ComputeSomething() IS thread-safe. Provided no threads are spawned prior to the start of the main program the problem is solved. As static initialisation is typically not thread-safe and certainly not guaranteed to be thread-safe this introduces no thread-safety issue that isn’t intrinsic to the language.
This isn’t something you need be "very concerned" about.
But this loses the "delay initialization until the first time the function is called" feature (as Raymond puts it), the same as the code Jack Matthews posted does.
Personally I like Ian Miller’s approach, but if you need the delay,
then maybe this will suit you:
static bool hasSlowResultBeenComputed = false; // Will happen at static init time
int ComputeSomethingSlowly
{
static int slowCachedResult; // Dont bother setting
EnterCriticalSection(…);
if ( ! hasSlowResultBeenComputed )
{
slowCachedResult = the slow computation ;
}
hasSlowResultBeenComputed = true ;
LeaveCriticalSection(…);
return slowCachedResult;
}
int ComputeSomething()
{
static int cachedResult = ComputeSomethingSlowly();
return cachedResult;
}
By hiding the critical section in the ComputeSomethingSlowly() routine you only have to pay for it once and it protects against multithread init. (Though there is a certain amount of ugliness.)
Local static initialization IS thread-safe,
in a well-written C++ compiler that is properly operated in its thread-safe mode. It should
produce two kinds of synchronization for you:
1) Exactly one construction of the local object.
2) Callers that don’t construct the object WAIT until it has been completely constructed before they reach the statement following its declaration.
There really isn’t any point in settling for less from a C++ compiler. When you also consider that the C++ runtime library (and most exception handling schemes) also need modifications to be thread-safe, this is really a puny issue.
"Callers that don’t construct the object WAIT until it has been completely constructed before they reach the statement following its declaration."
That’s not good enough. If the function is called by a second thread which the constructing thread is blocked on, you just created a deadlock. I thought I mentioned this already.
I’m going to close commenting on this very old thread.
Function Static Variables in Multi-Threaded Environments
C static initialization thread-safe