[ITC/Linux] std::string Write -> Read data-race errors

• Key: STDCXX-449
• Type: Bug
• Status: Open
• Priority: Minor
• Assignee: Unassigned
• Reporter: Martin Sebor
• Component/s: 21. Strings
• Affects Version/s: 4.1.2, 4.1.3, 4.1.4, 4.2.0
• Fix Version/s: 4.3.0

Description

Running the Intel Thread Checker on the string thread safety tests 21.string.cons.mt and 21.string.push_back.mt produces errors suggesting potential thread safety problems even though the tests run successfully to completion. See the text output below:

$ tcheck_cl -w 200 ./21.string.cons.mt --nloops=100 --nthreads=2
Intel(R) Thread Checker 3.1 command line instrumentation driver (24400)
Copyright (c) 2007 Intel Corporation. All rights reserved.
Building project

Running:  /build/sebor/stdcxx-icc-9.1_042-15s/tests/21.string.cons.mt --nloops=100 --nthreads=2

# INFO (S1) (10 lines):
# TEXT: 
# COMPILER: Intel C++, __INTEL_COMPILER = 910, __INTEL_COMPILER_BUILD_DATE = 20060706, __EDG_VERSION__ = 306
# ENVIRONMENT: i386 running linux-elf 2.4.20 with glibc 2.3
# FILE: 21.string.cons.mt.cpp
# COMPILED: Jun 13 2007, 13:00:49
# COMMENT: thread safety
############################################################

# CLAUSE: lib.string.cons

# INFO (S1) (3 lines):
# TEXT: testing std::string with 2 threads, 100 iterations each
# CLAUSE: lib.string.cons

# INFO (S1) (3 lines):
# TEXT: testing std::wstring with 2 threads, 100 iterations each
# CLAUSE: lib.string.cons

# +-----------------------+----------+----------+----------+
# | DIAGNOSTIC            |  ACTIVE  |   TOTAL  | INACTIVE |
# +-----------------------+----------+----------+----------+
# | (S1) INFO             |        3 |        3 |       0% |
# | (S7) ASSERTION        |        0 |       16 |     100% |
# +-----------------------+----------+----------+----------+

Application finished

________________________________________________________________________________________________________________________________________________________________________________________________________
|ID |Short Description    |Severity   |Cou|Context[Best]      |Description                                                                                 |1st Access[Best]    |2nd Access[Best]      |
|   |                     |Name       |nt |                   |                                                                                            |                    |                      |
________________________________________________________________________________________________________________________________________________________________________________________________________
|1  |Write -> Read        |Error      |128|[21.string.cons.mt,|Memory read at "_strref.h":159 conflicts with a prior memory write at [21.string.cons.mt,   |[21.string.cons.mt, |"_strref.h":159       |
|   |data-race            |           |   |0xadf0]            |0x3475f] (flow dependence)                                                                  |0x3475f]            |                      |
________________________________________________________________________________________________________________________________________________________________________________________________________
|2  |Read -> Write        |Error      |5  |[21.string.cons.mt,|Memory write at [21.string.cons.mt, 0x3475f] conflicts with a prior memory read at          |"_strref.h":159     |[21.string.cons.mt,   |
|   |data-race            |           |   |0x34755]           |"_strref.h":159 (anti dependence)                                                           |                    |0x3475f]              |
________________________________________________________________________________________________________________________________________________________________________________________________________
|3  |Thread termination   |Information|1  |Whole Program 1    |Thread termination at "thread.cpp":76 - includes stack allocation of 10.004 MB and use of   |"thread.cpp":76     |"thread.cpp":76       |
|   |                     |           |   |                   |4.516 KB                                                                                    |                    |                      |
________________________________________________________________________________________________________________________________________________________________________________________________________
|4  |Thread termination   |Information|1  |Whole Program 2    |Thread termination at "thread.cpp":76 - includes stack allocation of 10.004 MB and use of   |"thread.cpp":76     |"thread.cpp":76       |
|   |                     |           |   |                   |4.516 KB                                                                                    |                    |                      |
________________________________________________________________________________________________________________________________________________________________________________________________________
|5  |Read -> Write        |Error      |7  |[21.string.cons.mt,|Memory write at [21.string.cons.mt, 0x3475f] conflicts with a prior memory read at          |"_strref.h":159     |[21.string.cons.mt,   |
|   |data-race            |           |   |0x34755]           |"_strref.h":159 (anti dependence)                                                           |                    |0x3475f]              |
________________________________________________________________________________________________________________________________________________________________________________________________________
|6  |Thread termination   |Information|1  |Whole Program 3    |Thread termination at "thread.cpp":76 - includes stack allocation of 10.004 MB and use of   |"thread.cpp":76     |"thread.cpp":76       |
|   |                     |           |   |                   |4.516 KB                                                                                    |                    |                      |
________________________________________________________________________________________________________________________________________________________________________________________________________
|7  |Thread termination   |Information|1  |Whole Program 4    |Thread termination at "thread.cpp":76 - includes stack allocation of 10.004 MB and use of   |"thread.cpp":76     |"thread.cpp":76       |
|   |                     |           |   |                   |4.516 KB                                                                                    |                    |                      |
________________________________________________________________________________________________________________________________________________________________________________________________________
|8  |Thread termination   |Information|1  |Whole Program 5    |Thread termination at "21.string.cons.mt.cpp":237 - includes stack allocation of 10 MB and  |"21.string.cons.mt.c|"21.string.cons.mt.cpp|
|   |                     |           |   |                   |use of 8.578 KB                                                                             |pp":237             |":237                 |
________________________________________________________________________________________________________________________________________________________________________________________________________

Comments

[Martin Sebor]

Attached HTML output from the tool.

[Martin Sebor]

I think these are benign, at least on x86 and x86_64, since the code has been there for eons and the string thread safety tests have been passing, but I'll leave it open so that when we have a bit more time in the 4.2.1 release cycle we can do a better analysis. At the very least we can silence the ITC errors as false positives. Bumped down Priority to Minor and scheduled for 4.2.1.

[Travis Vitek]

According to this

Simple reads and writes to properly-aligned 32-bit variables are atomic operations. In other words, you will not end up with only one portion of the variable updated; all bits are updated in an atomic fashion. However, access is not guaranteed to be synchronized. If two threads are reading and writing from the same variable, you cannot determine if one thread will perform its read operation before the other performs its write operation.

Simple reads and writes to properly aligned 64-bit variables are atomic on 64-bit Windows. Reads and writes to 64-bit values are not guaranteed to be atomic on 32-bit Windows. Reads and writes to variables of other sizes are not guaranteed to be atomic on any platform.

The type of _C_ref is int, which is only 32-bits on a LLP64 systems. I believe that this is okay on EMT64/AMD64 systems because they are actually 32-bit architectures with 64-bit extensions, but I'm not absolutely sure. Need to find out.

According to this there are similar rules for other architectures...

When it comes to how memory ordering works on different CPUs, there is good news and bad news. The bad news is each CPU's memory ordering is a bit different. The good news is you can count on a few things:

1. A given CPU always perceives its own memory operations as occurring in program order. That is, memory-reordering issues arise only when a CPU is observing other CPUs' memory operations.
2. An operation is reordered with a store only if the operation accesses a different location than does the store.
3. Aligned simple loads and stores are atomic.
4. Linux-kernel synchronization primitives contain any needed memory barriers, which is a good reason to use these primitives.

That same page also says this

However, code that uses standard synchronization primitives—spinlocks, semaphores, RCU—should not need explicit memory barriers, because any required barriers already are present in these primitives. Only tricky code that bypasses these synchronization primitives needs barriers. It is important to note that most atomic operations, for example, atomic_inc() and atomic_add(), do not include any memory barriers.

Assuming that the first two quotes are accurate, and the _C_refs member is properly aligned and of the appropriate size on all platforms, we should be safe. Even if all of that works out, I don't feel good about it.

My initial inclination is to say that we need something to guard the read of _C_refs. We need to make sure that all writes are flushed before we read the current value. I was originally considering something like atomic_add(_C_refs, 0), assuming it would ensure that the returned value was consistent, but the last quote leaves me a little unsure if that is sufficient.

[Martin Sebor]

There are two potential problems here: word tearing (accessing parts of the same word non-atomically), and a data race between two conflicting accesses to the same word. I agree that word-tearing is a non-issue on all our platforms (some implementations of the Alpha processor had this property – see this article but I think that's been fixed in newer versions of the chip/OS). The data race is what I'm concerned about. I believe the data race is benign if we can make the assumption that every read will return a value previously written to the same location. I'm fairly confident this is the case on all implementations we have access to, but I'm also pretty sure there are architectures out there where such an assumption isn't safe, i.e., architectures that don't guarantee that a plain (unordered) read will yield any previously written value when the accesses take place on different processors. I don't know if such architectures have been implemented and occur in practice.

In any case, if we're comfortable with limiting this issue to the Intel Thread Checker errors on i386 (or x86_64), it would be safe to ignore such architectures. And if we're also comfortable with treating the ITC errors as benign on i86 we can simply suppress them. I can think of two ways of doing it without seriously impacting the performance of the code:

• instrument the code by inserting the appropriate #pragmas when compiling with thread-checking enabled (Intel C++ only), or
• instrument the code by making calls to the appropriate ITC functions at runtime when the tool is being used or not (i.e., regardless of the compiler)

IMO, the second option is the more robust of the two but I'm not sure how feasible it is to implement it.

[Travis Vitek]

Well, I haven't found any way suppress warnings from the thread checker utility using pragmas, so I think option 1 is out.

The only way that I've seen that seems workable is to use the Intel Thread Tools library and make the necessary calls to notify the thread checker that what we are doing is safe. I'm pretty sure this is what you are saying with option 2. We can detect at compile time if the user is building reentrant code with -tcheck option on the Intel compiler. If this is the case we could enable the thread checker code. One problem with this is that we also need the path to the include file libittnotify.h, as well as the link line to support linking to libittnotify.so and libassuret40.so.

If we are going to be doing thread checker runs with any frequency, then we could just gather up the thread checker output of all the tests/examples, and then run that output through a filter to hide [or de-emphasize] the ones that we don't care about, and then generate some fancy html output like the rest of the build infrastructure does.

[Travis Vitek]

Note that we don't have to limit this to only Intel C++ builds with the -tcheck flag. We could allow the user to define a macro to enable this thread checker code also.

[Travis Vitek]

Well, as I pointed out above, the only way I see to deal with this is to use the thread checker notify library to tell the thread checker that things are okay. If this is the route that we decide to go, then the attached file include/rw/_tcheck.h may be useful.

[Travis Vitek]

Defer to 4.3 or later.