False positive due to incorrect instrumentation

[ramosian-glider]

Originally reported on Google Code with ID 40

---------- Forwarded message ----------
From: Christian Holler
Date: Tue, Nov 19, 2013 at 3:35 AM
Subject: Problem with cmov/wrong instrumented code?
To: thread-sanitizer@googlegroups.com

Hi,

it would be really nice if some TSan developers could take a look at
https://bugzilla.mozilla.org/show_bug.cgi?id=939788 . In particular
comment 14 suggests that there could be a bug in the way TSan generates
it's instrumented code. Basically we're checking if we are the main
thread with a function called NS_IsMainThread() and then read a value if
that is true. However, with TSan, we always seem to read the value
(unconditionally), leading to a race report.

It would be nice if someone could figure out what exactly is going wrong
there and how we (or you) can fix it.


Thanks,

Chris

Reported by dvyukov@google.com on 2013-11-19 03:10:57

[ramosian-glider]

Hi,

Thanks for the report!
What compilation options/optimization level do you use?

Reported by dvyukov@google.com on 2013-11-19 03:16:53

[ramosian-glider]

If I understand the situation correctly, here is what's going on: 

% cat if.cc 
int x;
int foo(int cond) {
  if (cond)
    return x;
  return 0;
}

%  clang -O1  if.cc -S -o - -emit-llvm
; Function Attrs: nounwind readonly uwtable
define i32 @_Z3fooi(i32 %cond) #0 {
entry:
  %tobool = icmp eq i32 %cond, 0
  %0 = load i32* @x, align 4, !tbaa !1
  %retval.0 = select i1 %tobool, i32 0, i32 %0
  ret i32 %retval.0
}

LLVM at O1 and higher hoists a safe load (from a global) out of the conditional basic
block.
This optimization is clearly hostile to tsan. 

Reported by konstantin.s.serebryany on 2013-11-19 04:34:34

[ramosian-glider]

Kostya, you are in much better position to resolve this. Can we disable that optimization
under tsan?

Reported by dvyukov@google.com on 2013-11-19 05:00:59

[ramosian-glider]

Sure, that's what we are going to do. 

choller@, fixing this properly may take some time (there is a ongoing discussion at
LLVM about better ways to do similar stuff: http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20131118/195757.html)
In the meantime, can you try __attribute__((no_sanitize_thread)) on that function?

Reported by konstantin.s.serebryany on 2013-11-19 05:10:25

[ramosian-glider]

Just FTR, here is a full reproducer with a false positive: 
% cat if-race.cc 
#include <pthread.h>
#include <unistd.h>
int g;
int foo(int cond) {
  if (cond)
    return g;
  return 0;
}
void *Thread1(void *p) {
  long res = foo((long)p);
  sleep(1);
  return (void*) res;
}

int main() {
  pthread_t t;
  pthread_create(&t, 0, Thread1, 0);
  g = 1;
  pthread_join(t, 0);
}
% clang -fsanitize=thread  if-race.cc   && ./a.out 
% clang -fsanitize=thread  if-race.cc -O1  && ./a.out 
==================
WARNING: ThreadSanitizer: data race (pid=24069)
  Read of size 4 at 0x7f834514ada8 by thread T1:
    #0 foo(int) ??:0 (exe+0x0000000867de)
    #1 Thread1(void*) ??:0 (exe+0x000000086814)

Reported by konstantin.s.serebryany on 2013-11-19 17:43:43

[ramosian-glider]

One possible fix (will send it for review a bit later): 

Index: lib/Analysis/ValueTracking.cpp
===================================================================
--- lib/Analysis/ValueTracking.cpp      (revision 195222)
+++ lib/Analysis/ValueTracking.cpp      (working copy)
@@ -2008,6 +2008,9 @@
     const LoadInst *LI = cast<LoadInst>(Inst);
     if (!LI->isUnordered())
       return false;
+    // Speculating a load may create a race that did not exist in the source.
+    if (LI->getParent()->getParent()->hasFnAttribute(Attribute::SanitizeThread))
+      return false;
     return LI->getPointerOperand()->isDereferenceablePointer();
   }
   case Instruction::Call: {

Reported by konstantin.s.serebryany on 2013-11-20 08:12:10

[ramosian-glider]

Should be fixed by http://llvm.org/viewvc/llvm-project?rev=195324&view=rev
choller@, please try. 

Reported by konstantin.s.serebryany on 2013-11-21 07:40:48

• Status changed: Fixed

[ramosian-glider]

I've applied the patch to r192787 (I think that's the last good rev right now for Firefox)
and it seems to have fixed the problem, thanks.

Reported by decoder.oh on 2013-11-21 09:18:33

[ramosian-glider]

Turns out there is a whole paper about this kind of compiler bugs. 
http://www.di.ens.fr/~zappa/readings/pldi13.pdf

Reported by konstantin.s.serebryany on 2013-11-27 08:09:28

[ramosian-glider]

This issue is not a compiler bug per se. It is OK to read a global concurrently on x86.

Reported by dvyukov@google.com on 2013-11-27 08:25:24

[ramosian-glider]

Yes. The paper is about similar situations which *are* bugs 
(e.g. thread-hostile store hoisting).
But the same technique could be used to find tsan-hostile optimizations that are otherwise
correct. 
Robin Morisset (one of the authors) told me that they've seen a few of those cases
which were false positives for them. 

Reported by konstantin.s.serebryany on 2013-11-27 08:28:37

[ramosian-glider]

Adding Project:ThreadSanitizer as part of GitHub migration.

Reported by glider@google.com on 2015-07-30 09:21:31

• Labels added: ProjectThreadSanitizer