Violation reading location in std::map operator[]

Question

I encountered a problem when running some old code that was handed down to me. It works 99% of the time, but once in a while, I notice it throwing a "Violation reading location" exception. I have a variable number of threads potentially executing this code throughout the lifetime of the process. The low occurrence frequency may be indicative of a race condition, but I don't know why one would cause an exception in this case. Here is the code in question:

MyClass::Dostuff()
{
    static map<char, int> mappedChars;
    if (mappedChars.empty())
    {
       for (char c = '0'; c <= '9'; ++c)
       {
          mappedChars[c] = c - '0';
       }
    }
    // More code here, but mappedChars in not changed.
}

The exception is thrown in the map's operator[] implementation, on the very first call to the operator[] (Using the VS2005 implementation of STL.)

mapped_type& operator[](const key_type& _Keyval)
{
    iterator _Where = this->lower_bound(_Keyval); //exception thrown on the first line
    // More code here
}

I already tried freezing threads in operator[] and trying to get them to all run through it at the same time, but I was unable to reproduce the exception using that methodology.

Can you think of any reason why that would throw, and only some of the time?

(Yes, I know STL is not thread-safe and I'll need to make changes here. I am mostly curious as to WHY I'm seeing the behavior I described above.)

As requested, here some further details about the exception:
Unhandled exception at 0x00639a1c (app.exe) in app15-51-02-0944_2008-10-23.mdmp: 0xC0000005: Access violation reading location 0x00000004.

Thanks to everyone suggesting solutions to multithreading issues, but this isn't what this question is meant to address. Yes, I understand the presented code is not protected correctly and is overkill in what it's trying to accomplish. I already have the fix for it implemented. I'm just trying to get a better understanding of why this exception was thrown to begin with.

Answer 1

Given an address of "4", Likely the "this" pointer is null or the iterator is bad. You should be able to see this in the debugger. If this is null, then the problem isn't in that function but who ever is calling that function. If the iterator is bad, then it's the race condition you alluded to. Most iterators can't tolerate the list being updated.

Okay wait - No FM here. Static's are initialized on first use. The code that does this is not multi-thread safe. one thread is doing the initialization while the 2nd thinks it's already been done but it's still in progress. The result is that is uses an uninitialized variable. You can see this in the assembly below:

static x y;
004113ED  mov         eax,dword ptr [$S1 (418164h)] 
004113F2  and         eax,1 
004113F5  jne         wmain+6Ch (41141Ch) 
004113F7  mov         eax,dword ptr [$S1 (418164h)] 
004113FC  or          eax,1 
004113FF  mov         dword ptr [$S1 (418164h)],eax 
00411404  mov         dword ptr [ebp-4],0 
0041140B  mov         ecx,offset y (418160h) 
00411410  call        x::x (4111A4h) 
00411415  mov         dword ptr [ebp-4],0FFFFFFFFh

The $S1 is set to 1 when it init's. If set, (004113F5) it jumps over the init code - freezing the threads in the fnc won't help because this check is done on entry to a function. This isn't null, but one of the members is.

Fix by moving the map out of the method and into the class as static. Then it will initialize on startup. Otherwise, you have to put a CR around the calls do DoStuff(). You can protect from the remaining MT issues by placing a CR around the use of the map itself (e.g. where DoStuff uses operator[]).

Answer 2

mappedChars is static so it's shared by all the threads that execute DoStuff(). That alone could be your problem.

If you have to use a static map, then you may need to protect it with a mutex or critical section.

Personally, I think using a map for this purpose is overkill. I would write a helper function that takes a char and subtracts '0' from it. You won't have any thread safety issues with a function.

Answer 3

If multiple threads are invoking the function DoStuff this will mean that the initialization code

if (mappedChars.empty())

can enter a race condition. This means thread 1 enters the function, finds the map empty and begins filling it. Thread 2 then enters the function and finds the map non-empty (but not completely initialized) so merrily begins reading it. Because both threads are now in contention, but one is modifying the map structure (i.e inserting nodes), undefined behaviour (a crash) will result.

If you use a synchronization primitive prior to checking the map for empty(), and released after the map is guaranteed to have been completely initialized, all will be well.

I had a look via Google and indeed static initialization is not thread safe. Thus the declaration static mappedChars is immediately an issue. As others have mentioned it would be best if your initialization was done when only 1 thread is guaranteed to be active for the life time of initialization.

Answer 4

When you get into multi-threading, there's usually too much going on to pinpoint the exact spot where things are going bad, since it will always be changing. There are a ton of spots where using a static map in a multithreaded situation could go bad.

See this thread for some of the ways to guard a static variable. Your best bet would probably be to call the function once before starting up multiple threads to initialize it. Either that, or move the static map out, and create a separate initialization method.

Answer 5

Are you ever calling operator[] with an argument that's not in the range 0..9? If so, then you are inadvertently modifying the map, which is likely causing badness to happen in other threads. If you call operator[] with an argument not already in the map, it inserts that key into the map with a value equal to the default value of the value type (0 in the case of int).