tsan: add new trace

[dvyukov]

Summary

Add structures for the new trace format,
functions that serialize and add events to the trace
and trace replaying logic.

Depends on D107910.

[dvyukov]

I want to add few more tests, but the rest of the code is ready. So I mailed it to get any high-level feedback sooner.

[dvyukov]

It's pretty large, but it's the minimal amount of code that's testable end-to-end.

[melver]

(review incomplete, but this is what I have so far)

compiler-rt/lib/tsan/rtl/tsan_rtl.cpp

583

clang-tidy: please fix

684

clang-tidy: please fix

compiler-rt/lib/tsan/rtl/tsan_trace.h

73

You could make this an 'enum class EventType : u64'.

And then the bitfield below could actually be:

EventType type : 3;

because bitfield works for enum.

And the enum values could simply be s/EventType/k/.

Concrete suggestion: https://github.com/melver/llvm-project/commit/6a71c35bbf660788899e3302bedd2748113fb153

Note:

• This found some switch statements didn't handle all values (unsure if intentional)
• The test's lookup of EvenType was getting confused because one was not prefixed with v3::

[dvyukov]

fix review comments

[dvyukov]

compiler-rt/lib/tsan/rtl/tsan_trace.h

73

Amended. Thanks.

I thought this will increase bitfield size:
EventType type : 3;
but apparently it doesn't.

This found some switch statements didn't handle all values (unsure if intentional)

Yes, this was intentional (there is nothing to do in that case), but I added it to make it explicit.

[melver]

compiler-rt/lib/tsan/rtl/tsan_rtl.cpp

569

Could use kSizeLogX.

-  u64 size_log = size == 1 ? 0 : size == 2 ? 1 : size == 4 ? 2 : 3;
+  const u64 size_log = size == 1   ? kSizeLog1
+                       : size == 2 ? kSizeLog2
+                       : size == 4 ? kSizeLog4
+                                   : kSizeLog8;

sanitizer_common also has Log2(), which uses __builtin_ctzll(). Could it be faster? However, it'd require turning its CHECK()s into DCHECKs().

625

Could use UNUSED bool res = ... and instead drop this?

634

Could use UNUSED?

compiler-rt/lib/tsan/rtl/tsan_rtl.h

916

Other code below uses reinterpret_cast<Event *>(atomic_load_relaxed(&thr->trace_pos)); -- also switch to reintepret_cast?

compiler-rt/lib/tsan/rtl/tsan_rtl_report.cpp

607–608

This comparison is repeated several times and is quite distracting from the rest of the logic. Could at least the check that the accesses are overlapping be pulled out e.g. into a constexpr bool IsWithinAccess(addr1, size2, addr2, size2)?

And just to verify, this is checking that access of addr|size is contained in ev_addr|ev_size (and not just overlapping)?

654

Brief comment why this is also unhandled.

[dvyukov]

addressed comments

[dvyukov]

compiler-rt/lib/tsan/rtl/tsan_rtl.cpp

569

size is constant in all performance-critical callers, so this is as fast as it can be.
The new runtime removes kSizeLog* consts, I think this is the only place that still uses logs, so I would not add more uses.
But I will try to add some tests for precise size handling instead.

compiler-rt/lib/tsan/rtl/tsan_rtl_report.cpp

607–608

Done. I've added IsWithinAccess.

Re contained vs overlapping, there was a comment in the case above (I just did not duplicate it 3 times):

// Note: addr/size must be fully contained in ev_addr/ev_size
// because a memory access is always traced once, but can be
// split into multiple accesses in shadow.

But now it's on IsWithinAccess.

[dvyukov]

add more tests

[dvyukov]

add more tests

[dvyukov]

I've added more tests. I will submit on Monday.

[dvyukov]

Landed as c97318996fc1dbc04da4a00f931943a5890b2dc2

[dyung]

Hi, I believe that your change is causing a build failure on one of the bots, can you please take a look?

https://lab.llvm.org/buildbot/#/builders/37/builds/6103

In file included from ../rtl/tsan_rtl.h:42,
from tsan_go.cpp:13:
../rtl/tsan_trace.h:90:20: error: ‘__tsan::v3::Event::type’ is too small to hold all values of ‘enum class __tsan::v3::EventType’ [-Werror]
EventType type : 3;
^
../rtl/tsan_trace.h:124:20: error: ‘__tsan::v3::EventAccessExt::type’ is too small to hold all values of ‘enum class __tsan::v3::EventType’ [-Werror]
EventType type : 3; // = EventType::kAccessExt
^
../rtl/tsan_trace.h:140:20: error: ‘__tsan::v3::EventAccessRange::type’ is too small to hold all values of ‘enum class __tsan::v3::EventType’ [-Werror]
EventType type : 3; // = EventType::kAccessRange
^
../rtl/tsan_trace.h:156:20: error: ‘__tsan::v3::EventLock::type’ is too small to hold all values of ‘enum class __tsan::v3::EventType’ [-Werror]
EventType type : 3; // = EventType::kLock or EventType::kRLock
^
../rtl/tsan_trace.h:169:20: error: ‘__tsan::v3::EventUnlock::type’ is too small to hold all values of ‘enum class __tsan::v3::EventType’ [-Werror]
EventType type : 3; // = EventType::kUnlock
^
../rtl/tsan_trace.h:179:20: error: ‘__tsan::v3::EventTime::type’ is too small to hold all values of ‘enum class __tsan::v3::EventType’ [-Werror]
EventType type : 3; // = EventType::kTime
^

[melver]

In D107911#2946372, @dyung wrote:

Hi, I believe that your change is causing a build failure on one of the bots, can you please take a look?

https://lab.llvm.org/buildbot/#/builders/37/builds/6103

In file included from ../rtl/tsan_rtl.h:42,
from tsan_go.cpp:13:
../rtl/tsan_trace.h:90:20: error: ‘__tsan::v3::Event::type’ is too small to hold all values of ‘enum class __tsan::v3::EventType’ [-Werror]
EventType type : 3;
^

I think GCC version 8.3 is bad (which the build bot uses). GCC 8.4 seems to have fixed the issue: https://godbolt.org/z/66xYK1xMf

[dvyukov]

FTR, one bot failed with:

/home/buildbots/ppc64le-sanitizer/sanitizer-ppc64le/build/llvm-project/compiler-rt/lib/tsan/tests/unit/tsan_trace_test.cpp:153:12: error: unused variable 'res' [-Werror,-Wunused-variable]
    bool res = RestoreStack(thr->tid, v3::EventType::kLock, thr->sid,
         ^
/home/buildbots/ppc64le-sanitizer/sanitizer-ppc64le/build/llvm-project/compiler-rt/lib/tsan/tests/unit/tsan_trace_test.cpp:194:12: error: unused variable 'res' [-Werror,-Wunused-variable]
    bool res =

https://lab.llvm.org/buildbot/#/builders/19/builds/6003/steps/24/logs/stdio

I've sent https://reviews.llvm.org/D108118 to fix this.

[anirudhp]

In builds with the -Werror -Wmissing-field-initializers option(s) enabled, the following instantiation will cause an error.

Thread::Params tests[] = {
    {1, 0, 1, true},  {4, 0, 2, true},
    {4, 2, 2, true},  {8, 3, 1, true},
    {2, 1, 1, true},  {1, 1, 1, false},
    {8, 5, 4, false}, {4, static_cast<uptr>(-1l), 4, false},
};

Could the patch be updated to explicitly initialize the last int field in the Thread::Params struct?

[quinnp]

This patch is causing some failures on the clang-ppc64le-rhel buildbot. Here is the failing build. Specifically in the compiler-rt/lib/tsan/tests/unit/tsan_trace_test.cpp test case:

• missing field 'type' initializer from line 128 to line 131

[dyung]

In D107911#2946380, @melver wrote:

In D107911#2946372, @dyung wrote:

Hi, I believe that your change is causing a build failure on one of the bots, can you please take a look?

https://lab.llvm.org/buildbot/#/builders/37/builds/6103

In file included from ../rtl/tsan_rtl.h:42,
from tsan_go.cpp:13:
../rtl/tsan_trace.h:90:20: error: ‘__tsan::v3::Event::type’ is too small to hold all values of ‘enum class __tsan::v3::EventType’ [-Werror]
EventType type : 3;
^

I think GCC version 8.3 is bad (which the build bot uses). GCC 8.4 seems to have fixed the issue: https://godbolt.org/z/66xYK1xMf

That may be the case, but unless GCC 8.3 is an unsupported compiler (I don't believe it is), can we get a fix, a workaround or get this change reverted? It is causing the bot I linked to be red, and also one of our internal bots are failing because of this problem.

[melver]

In D107911#2947616, @dyung wrote:

I think GCC version 8.3 is bad (which the build bot uses). GCC 8.4 seems to have fixed the issue: https://godbolt.org/z/66xYK1xMf

That may be the case, but unless GCC 8.3 is an unsupported compiler (I don't believe it is), can we get a fix, a workaround or get this change reverted? It is causing the bot I linked to be red, and also one of our internal bots are failing because of this problem.

This is not breaking any default builds. This is only failing because Werror is on. By default it isn't. It can be disabled with -DCOMPILER_RT_ENABLE_WERROR=OFF, which I'd recommend for the bots still using GCC 8.3, given we know it's buggy.

[vitalybuka]

In D107911#2947675, @melver wrote:

In D107911#2947616, @dyung wrote:

I think GCC version 8.3 is bad (which the build bot uses). GCC 8.4 seems to have fixed the issue: https://godbolt.org/z/66xYK1xMf

That may be the case, but unless GCC 8.3 is an unsupported compiler (I don't believe it is), can we get a fix, a workaround or get this change reverted? It is causing the bot I linked to be red, and also one of our internal bots are failing because of this problem.

This is not breaking any default builds. This is only failing because Werror is on. By default it isn't. It can be disabled with -DCOMPILER_RT_ENABLE_WERROR=OFF, which I'd recommend for the bots still using GCC 8.3, given we know it's buggy.

We probably should not leave it to the user

Simple change should fix it.

struct Event {
  u64 type : 3;

  EventType GetType() const {
    return static_cast<EventType>(type);
  }
};

[vitalybuka]

@dvyukov To avoid revert I've done in commit above. Feel free to change if you have a better solution.

Simple change should fix it.

struct Event {
  u64 type : 3;

  EventType GetType() const {
    return static_cast<EventType>(type);
  }
};

[melver]

In D107911#2948130, @vitalybuka wrote:

We probably should not leave it to the user

Simple change should fix it.

struct Event {
  u64 type : 3;

  EventType GetType() const {
    return static_cast<EventType>(type);
  }
};

This seems simple enough, but still would be nice if the code doesn't need to suffer too much because of known buggy compilers. Would it be reasonable to force Werror off for known bad compiler versions? In this case GCC 9.2 or earlier (except 8.4 or later from 8 series which also include the fix).

[dyung]

In D107911#2948135, @vitalybuka wrote:

@dvyukov To avoid revert I've done in commit above. Feel free to change if you have a better solution.

Simple change should fix it.

struct Event {
  u64 type : 3;

  EventType GetType() const {
    return static_cast<EventType>(type);
  }
};

This doesn't seem to fix the problem on our internal bot (and likely also the upstream one).

Interestingly, @melver's solution of -DCOMPILER_RT_ENABLE_WERROR=OFF doesn't work either.

It would appear that -Werror is being hardcoded in line 62 of compiler-rt/lib/tsan/go/buildgo.sh. If I remove that, I can get the compilation to "succeed".

I'll put up that workaround shortly.

[anirudhp]

This patch still fails on the PPC64LE-RHEL Bot (https://lab.llvm.org/buildbot/#/builders/57/builds/9429). Could we please revert this patch or add a follow up fix to it? (The fix should be to explicitly initialize all fields in the struct within the initializer list (in lines 128 - 131) of the Thread::Params struct)

[anirudhp]

In D107911#2949414, @anirudhp wrote:

This patch still fails on the PPC64LE-RHEL Bot (https://lab.llvm.org/buildbot/#/builders/57/builds/9429). Could we please revert this patch or add a follow up fix to it? (The fix should be to explicitly initialize all fields in the struct within the initializer list (in lines 128 - 131) of the Thread::Params struct)

Resolved by https://reviews.llvm.org/D108207.

[nemanjai]

In D107911#2948181, @melver wrote:

In D107911#2948130, @vitalybuka wrote:

We probably should not leave it to the user

Simple change should fix it.

struct Event {
  u64 type : 3;

  EventType GetType() const {
    return static_cast<EventType>(type);
  }
};

This seems simple enough, but still would be nice if the code doesn't need to suffer too much because of known buggy compilers. Would it be reasonable to force Werror off for known bad compiler versions? In this case GCC 9.2 or earlier (except 8.4 or later from 8 series which also include the fix).

I will have to respectfully disagree here. "Buggy compilers" are a fact of life. We are all developers on a software project like any other and just as developers on other projects sometimes have to put in code workarounds for bugs in Clang (which we develop), we too have to do the same for bugs in compilers we support for building our project.

Turning on -Werror is a very useful thing and any suggestion to turn it off for bots that turn it on needs very solid justification. There have been many subtle issues identified by bots that use this option and turning it off completely just because of one issue is ill-advised IMHO. Not to mention that as @dyung mentioned, it doesn't fix the problem.

While I can certainly sympathize with not wanting to put in code to work around bugs that are not yours, I am afraid that this is something we all have to do sometimes.

All in all, if there is no obvious immediate fix that will bring the bot back to green, I recommend pulling this patch and any follow-up fixes that depend on it. Once you think you have a complete fixed patch, you can post it here and we'll be happy to test it ahead of the commit on the very machine that the bot runs on.

[azharudd]

The newly added unit tests are failing on Darwin. Can you please look into it? Would it possible to revert this until the issue is resolved?

TsanUnitTest-x86_64-Test --gtest_filter=Trace.MemoryAccessSize
--
Note: Google Test filter = Trace.MemoryAccessSize
[==========] Running 1 test from 1 test suite.
[----------] Global test environment set-up.
[----------] 1 test from Trace
[ RUN      ] Trace.MemoryAccessSize
access_size=1, offset=0, size=1, res=1, type=0
ThreadSanitizer:DEADLYSIGNAL
==49176==ERROR: ThreadSanitizer: SEGV on unknown address 0x0000000000f8 (pc 0x00010a190c52 bp 0x7e8000080b70 sp 0x7e8000080b00 T570136)
==49176==The signal is caused by a READ memory access.
==49176==Hint: address points to the zero page.
    #0 __tsan::v3::TraceSwitchPart(__tsan::ThreadState*) tsan_rtl.cpp:682 (TsanUnitTest-x86_64-Test:x86_64+0x1000bcc52)
    #1 __tsan::v3::TraceFunc(__tsan::ThreadState*, unsigned long) tsan_rtl.cpp:630 (TsanUnitTest-x86_64-Test:x86_64+0x1000bd2b1)
    #2 __tsan::Trace_MemoryAccessSize_Test::TestBody()::Thread::Func(void*) tsan_trace_test.cpp:93 (TsanUnitTest-x86_64-Test:x86_64+0x10003fe77)
    #3 _pthread_start <null>:2 (libsystem_pthread.dylib:x86_64+0x6108)
    #4 thread_start <null>:2 (libsystem_pthread.dylib:x86_64+0x1b8a)

==49176==Register values:
rax = 0x0000000000000000  rbx = 0x0000000000000000  rcx = 0x0000000000000008  rdx = 0x0000000000000000  
rdi = 0x000000010ea8e000  rsi = 0x0000000000001000  rbp = 0x00007e8000080b70  rsp = 0x00007e8000080b00  
 r8 = 0x0000000063000000   r9 = 0x0000000000000000  r10 = 0x000000010ea8e000  r11 = 0x0000000000000206  
r12 = 0x0000000000000000  r13 = 0x0000000000000000  r14 = 0x0000000000001000  r15 = 0x0000000000000000  
ThreadSanitizer can not provide additional info.
SUMMARY: ThreadSanitizer: SEGV tsan_rtl.cpp:682 in __tsan::v3::TraceSwitchPart(__tsan::ThreadState*)
==49176==ABORTING

Refer to https://green.lab.llvm.org/green/job/clang-stage1-RA/23374/testReport/junit/ThreadSanitizer-Unit/.

[melver]

In D107911#2951677, @azharudd wrote:

The newly added unit tests are failing on Darwin. Can you please look into it? Would it possible to revert this until the issue is resolved?

Refer to https://green.lab.llvm.org/green/job/clang-stage1-RA/23374/testReport/junit/ThreadSanitizer-Unit/.

The test and the code is new, and the only user of the code is the test. So I think it's fair to just disable the test on Darwin until Dmitry has a chance to look at it. I'll try and do this later today.

compiler-rt/lib/tsan/rtl/tsan_defs.h

 #  define TSAN_CONTAINS_UBSAN 1
 # else
 #  define TSAN_CONTAINS_UBSAN 0
 # endif
 #endif
 
 namespace __tsan {
 
+constexpr uptr kByteBits = 8;
+
 // Thread slot ID.
 enum class Sid : u8 {};
 constexpr uptr kThreadSlotCount = 256;
+constexpr Sid kFreeSid = static_cast<Sid>(255);
 
 // Abstract time unit, vector clock element.
 enum class Epoch : u16 {};
+constexpr uptr kEpochBits = 14;
 constexpr Epoch kEpochZero = static_cast<Epoch>(0);
+constexpr Epoch kEpochOver = static_cast<Epoch>(1 << kEpochBits);
 
 const int kClkBits = 42;
 const unsigned kMaxTidReuse = (1 << (64 - kClkBits)) - 1;
 
 struct ClockElem {
   u64 epoch  : kClkBits;
   u64 reused : 64 - kClkBits;  // tid reuse count
 };

compiler-rt/lib/tsan/rtl/tsan_rtl.h

 #endif
 
   // Set in regions of runtime that must be signal-safe and fork-safe.
   // If set, malloc must not be called.
   int nomalloc;
 
   const ReportDesc *current_report;
 
+  // Current position in tctx->trace.Back()->events (Event*).
+  atomic_uintptr_t trace_pos;
+  // PC of the last memory access, used to compute PC deltas in the trace.
+  uptr trace_prev_pc;
+  Sid sid;
+  Epoch epoch;
+
   explicit ThreadState(Context *ctx, Tid tid, int unique_id, u64 epoch,
                        unsigned reuse_count, uptr stk_addr, uptr stk_size,
                        uptr tls_addr, uptr tls_size);
 };
 
 #if !SANITIZER_GO
 #if SANITIZER_MAC || SANITIZER_ANDROID
 ThreadState *cur_thread();
public:
   StackID creation_stack_id;
   SyncClock sync;
   // Epoch at which the thread had started.
   // If we see an event from the thread stamped by an older epoch,
   // the event is from a dead thread that shared tid with this thread.
   u64 epoch0;
   u64 epoch1;
 
+  v3::Trace trace;
+
   // Override superclass callbacks.
   void OnDead() override;
   void OnJoined(void *arg) override;
   void OnFinished() override;
   void OnStarted(void *arg) override;
   void OnCreated(void *arg) override;
   void OnReset() override;
   void OnDetached(void *arg) override;
#endif
   // Number of fired suppressions may be large enough.
   Mutex fired_suppressions_mtx;
   InternalMmapVector<FiredSuppression> fired_suppressions;
   DDetector *dd;
 
   ClockAlloc clock_alloc;
 
   Flags flags;
+
+  Mutex slot_mtx;
 };
 
 extern Context *ctx;  // The one and the only global runtime context.
 
 ALWAYS_INLINE Flags *flags() {
   return &ctx->flags;
 }
 
void LazyInitialize(ThreadState *thr) {
   // called from .preinit_array initializes runtime before
   // any instrumented code.
 #if !SANITIZER_CAN_USE_PREINIT_ARRAY
   if (UNLIKELY(!is_initialized))
     Initialize(thr);
 #endif
 }
 
+namespace v3 {
+
+void TraceSwitchPart(ThreadState *thr);
+bool RestoreStack(Tid tid, EventType type, Sid sid, Epoch epoch, uptr addr,
+                  uptr size, AccessType typ, VarSizeStackTrace *pstk,
+                  MutexSet *pmset, uptr *ptag);
+
+template <typename EventT>
+ALWAYS_INLINE WARN_UNUSED_RESULT bool TraceAcquire(ThreadState *thr,
+                                                   EventT **ev) {
+  Event *pos = (Event *)atomic_load_relaxed(&thr->trace_pos);
+#if SANITIZER_DEBUG
+  // TraceSwitch acquires these mutexes,
+  // so we lock them here to detect deadlocks more reliably.
+  { Lock lock(&ctx->slot_mtx); }
+  { Lock lock(&thr->tctx->trace.mtx); }
+  TracePart *current = thr->tctx->trace.parts.Back();
+  if (current) {
+    DCHECK_GE(pos, &current->events[0]);
+    DCHECK_LE(pos, &current->events[TracePart::kSize]);
+  } else {
+    DCHECK_EQ(pos, nullptr);
+  }
+#endif
+  // TracePart is allocated with mmap and is at least 4K aligned.
+  // So the following check is a faster way to check for part end.
+  // It may have false positives in the middle of the trace,
+  // they are filtered out in TraceSwitch.
+  if (UNLIKELY(((uptr)(pos + 1) & TracePart::kAlignment) == 0))
+    return false;
+  *ev = reinterpret_cast<EventT *>(pos);
+  return true;
+}
+
+template <typename EventT>
+ALWAYS_INLINE void TraceRelease(ThreadState *thr, EventT *evp) {
+  DCHECK_LE(evp + 1, &thr->tctx->trace.parts.Back()->events[TracePart::kSize]);
+  atomic_store_relaxed(&thr->trace_pos, (uptr)(evp + 1));
+}
+
+template <typename EventT>
+void TraceEvent(ThreadState *thr, EventT ev) {
+  EventT *evp;
+  if (!TraceAcquire(thr, &evp)) {
+    TraceSwitchPart(thr);
+    bool res = TraceAcquire(thr, &evp);
+    DCHECK(res);
+    (void)res;
+  }
+  *evp = ev;
+  TraceRelease(thr, evp);
+}
+
+ALWAYS_INLINE WARN_UNUSED_RESULT bool TryTraceFunc(ThreadState *thr,
+                                                   uptr pc = 0) {
+  if (!kCollectHistory)
+    return true;
+  EventFunc *ev;
+  if (UNLIKELY(!TraceAcquire(thr, &ev)))
+    return false;
+  ev->is_access = 0;
+  ev->is_func = 1;
+  ev->pc = pc;
+  TraceRelease(thr, ev);
+  return true;
+}
+
+WARN_UNUSED_RESULT
+bool TryTraceMemoryAccess(ThreadState *thr, uptr pc, uptr addr, uptr size,
+                          AccessType typ);
+WARN_UNUSED_RESULT
+bool TryTraceMemoryAccessRange(ThreadState *thr, uptr pc, uptr addr, uptr size,
+                               AccessType typ);
+void TraceMemoryAccessRange(ThreadState *thr, uptr pc, uptr addr, uptr size,
+                            AccessType typ);
+void TraceFunc(ThreadState *thr, uptr pc = 0);
+void TraceMutexLock(ThreadState *thr, EventType type, uptr pc, uptr addr,
+                    StackID stk);
+void TraceMutexUnlock(ThreadState *thr, uptr addr);
+void TraceTime(ThreadState *thr);
+
+}  // namespace v3
+
 }  // namespace __tsan
 
 #endif  // TSAN_RTL_H

compiler-rt/lib/tsan/rtl/tsan_rtl.cpp

#endif
   }
   StackID id = StackDepotPut(
       StackTrace(thr->shadow_stack, thr->shadow_stack_pos - thr->shadow_stack));
   if (pc != 0)
     thr->shadow_stack_pos--;
   return id;
 }
 
+namespace v3 {
+
+ALWAYS_INLINE USED bool TryTraceMemoryAccess(ThreadState *thr, uptr pc,
+                                             uptr addr, uptr size,
+                                             AccessType typ) {
+  DCHECK(size == 1 || size == 2 || size == 4 || size == 8);
+  if (!kCollectHistory)
+    return true;
+  EventAccess *ev;
+  if (UNLIKELY(!TraceAcquire(thr, &ev)))
+    return false;
+  u64 size_log = size == 1 ? 0 : size == 2 ? 1 : size == 4 ? 2 : 3;
+  uptr pc_delta = pc - thr->trace_prev_pc + (1 << (EventAccess::kPCBits - 1));
+  thr->trace_prev_pc = pc;
+  if (LIKELY(pc_delta < (1 << EventAccess::kPCBits))) {
+    ev->is_access = 1;
+    ev->is_read = !!(typ & kAccessRead);
+    ev->is_atomic = !!(typ & kAccessAtomic);
+    ev->size_log = size_log;
+    ev->pc_delta = pc_delta;
+    DCHECK_EQ(ev->pc_delta, pc_delta);
+    ev->addr = addr;
+    TraceRelease(thr, ev);
+    return true;
+  }
+  auto *evex = reinterpret_cast<EventAccessExt *>(ev);
+  evex->is_access = 0;
+  evex->is_func = 0;
+  evex->type = EventType::kAccessExt;
+  evex->is_read = !!(typ & kAccessRead);
+  evex->is_atomic = !!(typ & kAccessAtomic);
+  evex->size_log = size_log;
+  evex->addr = addr;
+  evex->pc = pc;
+  TraceRelease(thr, evex);
+  return true;
+}
+
+ALWAYS_INLINE USED bool TryTraceMemoryAccessRange(ThreadState *thr, uptr pc,
+                                                  uptr addr, uptr size,
+                                                  AccessType typ) {
+  if (!kCollectHistory)
+    return true;
+  EventAccessRange *ev;
+  if (UNLIKELY(!TraceAcquire(thr, &ev)))
+    return false;
+  thr->trace_prev_pc = pc;
+  ev->is_access = 0;
+  ev->is_func = 0;
+  ev->type = EventType::kAccessRange;
+  ev->is_read = !!(typ & kAccessRead);
+  ev->is_free = !!(typ & kAccessFree);
+  ev->size_lo = size;
+  ev->pc = pc;
+  ev->addr = addr;
+  ev->size_hi = size >> EventAccessRange::kSizeLoBits;
+  TraceRelease(thr, ev);
+  return true;
+}
+
+void TraceMemoryAccessRange(ThreadState *thr, uptr pc, uptr addr, uptr size,
+                            AccessType typ) {
+  if (LIKELY(TryTraceMemoryAccessRange(thr, pc, addr, size, typ)))
+    return;
+  TraceSwitchPart(thr);
+  bool res = TryTraceMemoryAccessRange(thr, pc, addr, size, typ);
+  DCHECK(res);
+  (void)res;
+}
+
+void TraceFunc(ThreadState *thr, uptr pc) {
+  if (LIKELY(TryTraceFunc(thr, pc)))
+    return;
+  TraceSwitchPart(thr);
+  bool res = TryTraceFunc(thr, pc);
+  DCHECK(res);
+  (void)res;
+}
+
+void TraceMutexLock(ThreadState *thr, EventType type, uptr pc, uptr addr,
+                    StackID stk) {
+  DCHECK(type == EventType::kLock || type == EventType::kRLock);
+  if (!kCollectHistory)
+    return;
+  EventLock ev;
+  ev.is_access = 0;
+  ev.is_func = 0;
+  ev.type = type;
+  ev.pc = pc;
+  ev.stack_lo = stk;
+  ev.stack_hi = stk >> EventLock::kStackIDLoBits;
+  ev._ = 0;
+  ev.addr = addr;
+  TraceEvent(thr, ev);
+}
+
+void TraceMutexUnlock(ThreadState *thr, uptr addr) {
+  if (!kCollectHistory)
+    return;
+  EventUnlock ev;
+  ev.is_access = 0;
+  ev.is_func = 0;
+  ev.type = EventType::kUnlock;
+  ev._ = 0;
+  ev.addr = addr;
+  TraceEvent(thr, ev);
+}
+
+void TraceTime(ThreadState *thr) {
+  if (!kCollectHistory)
+    return;
+  EventTime ev;
+  ev.is_access = 0;
+  ev.is_func = 0;
+  ev.type = EventType::kTime;
+  ev.sid = static_cast<u64>(thr->sid);
+  ev.epoch = static_cast<u64>(thr->epoch);
+  ev._ = 0;
+  TraceEvent(thr, ev);
+}
+
+NOINLINE
+void TraceSwitchPart(ThreadState *thr) {
+  Trace *trace = &thr->tctx->trace;
+  Event *pos = reinterpret_cast<Event *>(atomic_load_relaxed(&thr->trace_pos));
+  DCHECK_EQ(reinterpret_cast<uptr>(pos + 1) & TracePart::kAlignment, 0);
+  auto *part = trace->parts.Back();
+  DPrintf("TraceSwitchPart part=%p pos=%p\n", part, pos);
+  if (part) {
+    // We can get here when we still have space in the current trace part.
+    // The fast-path check in TraceAcquire has false positives in the middle of
+    // the part. Check if we are indeed at the end of the current part or not,
+    // and fill any gaps with NopEvent's.
+    Event *end = &part->events[TracePart::kSize];
+    DCHECK_GE(pos, &part->events[0]);
+    DCHECK_LE(pos, end);
+    if (pos + 1 < end) {
+      if ((reinterpret_cast<uptr>(pos) & TracePart::kAlignment) ==
+          TracePart::kAlignment)
+        *pos++ = NopEvent;
+      *pos++ = NopEvent;
+      DCHECK_LE(pos + 2, end);
+      atomic_store_relaxed(&thr->trace_pos, reinterpret_cast<uptr>(pos));
+      // Ensure we setup trace so that the next TraceAcquire
+      // won't detect trace part end.
+      Event *ev;
+      CHECK(TraceAcquire(thr, &ev));
+      return;
+    }
+    // We are indeed at the end.
+    for (; pos < end; pos++) *pos = NopEvent;
+  }
+#if !SANITIZER_GO
+  if (ctx->after_multithreaded_fork) {
+    // We just need to survive till exec.
+    CHECK(part);
+    atomic_store_relaxed(&thr->trace_pos,
+                         reinterpret_cast<uptr>(&part->events[0]));
+    return;
+  }
+#endif
+  part = new (MmapOrDie(sizeof(TracePart), "TracePart")) TracePart();
+  part->trace = trace;
+  thr->trace_prev_pc = 0;
+  {
+    Lock lock(&trace->mtx);
+    trace->parts.PushBack(part);
+    atomic_store_relaxed(&thr->trace_pos,
+                         reinterpret_cast<uptr>(&part->events[0]));
+  }
+  // Make this part self-sufficient by restoring the current stack
+  // and mutex set in the beginning of the trace.
+  TraceTime(thr);
+  for (uptr *pos = &thr->shadow_stack[0]; pos < thr->shadow_stack_pos; pos++)
+    CHECK(TryTraceFunc(thr, *pos));
+  for (uptr i = 0; i < thr->mset.Size(); i++) {
+    MutexSet::Desc d = thr->mset.Get(i);
+    TraceMutexLock(thr, d.write ? EventType::kLock : EventType::kRLock, 0,
+                   d.addr, d.stack_id);
+  }
+}
+
+}  // namespace v3
+
 void TraceSwitch(ThreadState *thr) {
 #if !SANITIZER_GO
   if (ctx->after_multithreaded_fork)
     return;
 #endif
   thr->nomalloc++;
   Trace *thr_trace = ThreadTrace(thr->tid);
   Lock l(&thr_trace->mtx);

compiler-rt/lib/tsan/rtl/tsan_rtl_report.cpp

void RestoreStack(Tid tid, const u64 epoch, VarSizeStackTrace *stk,
   }
   if (pos == 0 && stack[0] == 0)
     return;
   pos++;
   stk->Init(&stack[0], pos);
   ExtractTagFromStack(stk, tag);
 }
 
+namespace v3 {
+
+// Replays the trace up to last_pos position in the last part
+// or up to the provided epoch/sid (whichever is earlier)
+// and calls the provided function f for each event.
+template <typename Func>
+void TraceReplay(Trace *trace, TracePart *last, Event *last_pos, Sid sid,
+                 Epoch epoch, Func f) {
+  TracePart *part = trace->parts.Front();
+  Sid ev_sid = kFreeSid;
+  Epoch ev_epoch = kEpochOver;
+  for (;;) {
+    DCHECK_EQ(part->trace, trace);
+    // Note: an event can't start in the last element.
+    // Since an event can take up to 2 elements,
+    // we ensure we have at least 2 before adding an event.
+    Event *end = &part->events[TracePart::kSize - 1];
+    if (part == last)
+      end = last_pos;
+    for (Event *evp = &part->events[0]; evp < end; evp++) {
+      Event *evp0 = evp;
+      if (!evp->is_access && !evp->is_func) {
+        switch (evp->type) {
+          case EventType::kTime: {
+            auto *ev = reinterpret_cast<EventTime *>(evp);
+            ev_sid = static_cast<Sid>(ev->sid);
+            ev_epoch = static_cast<Epoch>(ev->epoch);
+            if (ev_sid == sid && ev_epoch > epoch)
+              return;
+            break;
+          }
+          case EventType::kAccessExt:
+            FALLTHROUGH;
+          case EventType::kAccessRange:
+            FALLTHROUGH;
+          case EventType::kLock:
+            FALLTHROUGH;
+          case EventType::kRLock:
+            // These take 2 Event elements.
+            evp++;
+            break;
+          case EventType::kUnlock:
+            // This takes 1 Event element.
+            break;
+        }
+      }
+      CHECK_NE(ev_sid, kFreeSid);
+      CHECK_NE(ev_epoch, kEpochOver);
+      f(ev_sid, ev_epoch, evp0);
+    }
+    if (part == last)
+      return;
+    part = trace->parts.Next(part);
+    CHECK(part);
+  }
+  CHECK(0);
+}
+
+void RestoreStackMatch(VarSizeStackTrace *pstk, MutexSet *pmset,
+                       Vector<uptr> *stack, MutexSet *mset, uptr pc,
+                       bool *found) {
+  DPrintf2("    MATCHED\n");
+  *pmset = *mset;
+  stack->PushBack(pc);
+  pstk->Init(&(*stack)[0], stack->Size());
+  stack->PopBack();
+  *found = true;
+}
+
+// Replays the trace of thread tid up to the target event identified
+// by sid/epoch/addr/size/typ and restores and returns stack, mutex set
+// and tag for that event. If there are multiple such events, it returns
+// the last one. Returns false if the event is not present in the trace.
+bool RestoreStack(Tid tid, EventType type, Sid sid, Epoch epoch, uptr addr,
+                  uptr size, AccessType typ, VarSizeStackTrace *pstk,
+                  MutexSet *pmset, uptr *ptag) {
+  // This function restores stack trace and mutex set for the thread/epoch.
+  // It does so by getting stack trace and mutex set at the beginning of
+  // trace part, and then replaying the trace till the given epoch.
+  DPrintf2("RestoreStack: tid=%u sid=%u@%u addr=0x%zx/%zu typ=%x\n", tid, sid,
+           epoch, addr, size, typ);
+  ctx->slot_mtx.CheckLocked();  // needed to prevent trace part recycling
+  ctx->thread_registry.CheckLocked();
+  ThreadContext *tctx =
+      static_cast<ThreadContext *>(ctx->thread_registry.GetThreadLocked(tid));
+  Trace *trace = &tctx->trace;
+  // Snapshot first/last parts and the current position in the last part.
+  TracePart *first_part;
+  TracePart *last_part;
+  Event *last_pos;
+  {
+    Lock lock(&trace->mtx);
+    first_part = trace->parts.Front();
+    if (!first_part)
+      return false;
+    last_part = trace->parts.Back();
+    last_pos = trace->final_pos;
+    if (tctx->thr)
+      last_pos = (Event *)atomic_load_relaxed(&tctx->thr->trace_pos);
+  }
+  // Too large for stack.
+  alignas(MutexSet) static char mset_storage[sizeof(MutexSet)];
+  MutexSet &mset = *new (mset_storage) MutexSet();
+  Vector<uptr> stack;
+  uptr prev_pc = 0;
+  bool found = false;
+  bool is_read = typ & kAccessRead;
+  bool is_atomic = typ & kAccessAtomic;
+  bool is_free = typ & kAccessFree;
+  TraceReplay(
+      trace, last_part, last_pos, sid, epoch,
+      [&](Sid ev_sid, Epoch ev_epoch, Event *evp) {
+        bool match = ev_sid == sid && ev_epoch == epoch;
+        if (evp->is_access) {
+          if (evp->is_func == 0 && evp->type == EventType::kAccessExt &&
+              evp->_ == 0)  // NopEvent
+            return;
+          auto *ev = reinterpret_cast<EventAccess *>(evp);
+          uptr ev_addr = RestoreAddr(ev->addr);
+          uptr ev_size = 1 << ev->size_log;
+          uptr ev_pc =
+              prev_pc + ev->pc_delta - (1 << (EventAccess::kPCBits - 1));
+          prev_pc = ev_pc;
+          DPrintf2("  Access: pc=0x%zx addr=0x%llx/%llu type=%llu/%llu\n",
+                   ev_pc, ev_addr, ev_size, ev->is_read, ev->is_atomic);
+          // Note: addr/size must be fully contained in ev_addr/ev_size
+          // because a memory access is always traced once, but can be
+          // split into multiple accesses in shadow.
+          if (match && type == EventType::kAccessExt && addr >= ev_addr &&
+              addr + size <= ev_addr + ev_size && is_read == ev->is_read &&
+              is_atomic == ev->is_atomic && !is_free)
+            RestoreStackMatch(pstk, pmset, &stack, &mset, ev_pc, &found);
+          return;
+        }
+        if (evp->is_func) {
+          auto *ev = reinterpret_cast<EventFunc *>(evp);
+          if (ev->pc) {
+            DPrintf2("  FuncEnter: pc=0x%zx\n", ev->pc);
+            stack.PushBack(ev->pc);
+          } else {
+            DPrintf2("  FuncExit\n");
+            CHECK(stack.Size());
+            stack.PopBack();
+          }
+          return;
+        }
+        switch (evp->type) {
+          case EventType::kAccessExt: {
+            auto *ev = reinterpret_cast<EventAccessExt *>(evp);
+            uptr ev_addr = RestoreAddr(ev->addr);
+            uptr ev_size = 1 << ev->size_log;
+            prev_pc = ev->pc;
+            DPrintf2("  AccessExt: pc=0x%zx addr=0x%llx/%llu type=%llu/%llu\n",
+                     ev->pc, ev_addr, ev_size, ev->is_read, ev->is_atomic);
+            if (match && type == EventType::kAccessExt && addr >= ev_addr &&
+                addr + size <= ev_addr + ev_size && is_read == ev->is_read &&
+                is_atomic == ev->is_atomic && !is_free)
+              RestoreStackMatch(pstk, pmset, &stack, &mset, ev->pc, &found);
+            break;
+          }
+          case EventType::kAccessRange: {
+            auto *ev = reinterpret_cast<EventAccessRange *>(evp);
+            uptr ev_addr = RestoreAddr(ev->addr);
+            uptr ev_size =
+                (ev->size_hi << EventAccessRange::kSizeLoBits) + ev->size_lo;
+            uptr ev_pc = RestoreAddr(ev->pc);
+            prev_pc = ev_pc;
+            DPrintf2("  Range: pc=0x%zx addr=0x%llx/%llu type=%llu/%llu\n",
+                     ev_pc, ev_addr, ev_size, ev->is_read, ev->is_free);
+            if (match && type == EventType::kAccessExt && addr >= ev_addr &&
+                addr + size <= ev_addr + ev_size && is_read == ev->is_read &&
+                !is_atomic && is_free == ev->is_free)
+              RestoreStackMatch(pstk, pmset, &stack, &mset, ev_pc, &found);
+            break;
+          }
+          case EventType::kLock:
+            FALLTHROUGH;
+          case EventType::kRLock: {
+            auto *ev = reinterpret_cast<EventLock *>(evp);
+            bool is_write = ev->type == EventType::kLock;
+            uptr ev_addr = RestoreAddr(ev->addr);
+            uptr ev_pc = RestoreAddr(ev->pc);
+            StackID stack_id =
+                (ev->stack_hi << EventLock::kStackIDLoBits) + ev->stack_lo;
+            DPrintf2("  Lock: pc=0x%zx addr=0x%llx stack=%u write=%d\n", ev_pc,
+                     ev_addr, stack_id, is_write);
+            mset.AddAddr(ev_addr, stack_id, is_write);
+            // Events with ev_pc == 0 are written to the beginning of trace
+            // part as initial mutex set (are not real).
+            if (match && type == EventType::kLock && addr == ev_addr && ev_pc)
+              RestoreStackMatch(pstk, pmset, &stack, &mset, ev_pc, &found);
+            break;
+          }
+          case EventType::kUnlock: {
+            auto *ev = reinterpret_cast<EventUnlock *>(evp);
+            uptr ev_addr = RestoreAddr(ev->addr);
+            DPrintf2("  Unlock: addr=0x%llx\n", ev_addr);
+            mset.DelAddr(ev_addr);
+            break;
+          }
+          case EventType::kTime:
+            break;  // XXX: unhandled ??
+        }
+      });
+  ExtractTagFromStack(pstk, ptag);
+  return found;
+}
+
+}  // namespace v3
+
 static bool FindRacyStacks(const RacyStacks &hash) {
   for (uptr i = 0; i < ctx->racy_stacks.Size(); i++) {
     if (hash == ctx->racy_stacks[i]) {
       VPrintf(2, "ThreadSanitizer: suppressing report as doubled (stack)\n");
       return true;
     }
   }
   return false;

compiler-rt/lib/tsan/rtl/tsan_trace.h

 //===-- tsan_trace.h --------------------------------------------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // This file is a part of ThreadSanitizer (TSan), a race detector.
 //
 //===----------------------------------------------------------------------===//
 #ifndef TSAN_TRACE_H
 #define TSAN_TRACE_H
 
 #include "tsan_defs.h"
-#include "tsan_stack_trace.h"
+#include "tsan_ilist.h"
 #include "tsan_mutexset.h"
+#include "tsan_stack_trace.h"
 
 namespace __tsan {
 
 const int kTracePartSizeBits = 13;
 const int kTracePartSize = 1 << kTracePartSizeBits;
 const int kTraceParts = 2 * 1024 * 1024 / kTracePartSize;
 const int kTraceSize = kTracePartSize * kTraceParts;
 

 #endif
   // Must be the last field, because we unmap the unused part in
   // CreateThreadContext.
   TraceHeader headers[kTraceParts];
 
   Trace() : mtx(MutexTypeTrace) {}
 };
 
+namespace v3 {
+
+enum class EventType : u64 {
+  kAccessExt,
+  kAccessRange,
+  kLock,
+  kRLock,
+  kUnlock,
+  kTime,
+};
+
+// "Base" type for all events for type dispatch.
+struct Event {
+  // We use variable-length type encoding to give more bits to some event
+  // types that need them. If is_access is set, this is EventAccess.
+  // Otherwise, if is_func is set, this is EventFunc.
+  // Otherwise type denotes the type.
+  u64 is_access : 1;
+  u64 is_func : 1;
+  EventType type : 3;
+  u64 _ : 59;
+};
+static_assert(sizeof(Event) == 8, "bad Event size");
+
+// Nop event used as padding and does not affect state during replay.
+static constexpr Event NopEvent = {1, 0, EventType::kAccessExt, 0};
+
+// Compressed memory access can represent only some events with PCs
+// close enough to each other. Otherwise we fall back to EventAccessExt.
+struct EventAccess {
+  static constexpr uptr kPCBits = 15;
+
+  u64 is_access : 1;  // = 1
+  u64 is_read : 1;
+  u64 is_atomic : 1;
+  u64 size_log : 2;
+  u64 pc_delta : kPCBits;  // signed delta from the previous memory access PC
+  u64 addr : kCompressedAddrBits;
+};
+static_assert(sizeof(EventAccess) == 8, "bad EventAccess size");
+
+// Function entry (pc != 0) or exit (pc == 0).
+struct EventFunc {
+  u64 is_access : 1;  // = 0
+  u64 is_func : 1;    // = 1
+  u64 pc : 62;
+};
+static_assert(sizeof(EventFunc) == 8, "bad EventFunc size");
+
+// Extended memory access with full PC.
+struct EventAccessExt {
+  u64 is_access : 1;   // = 0
+  u64 is_func : 1;     // = 0
+  EventType type : 3;  // = EventType::kAccessExt
+  u64 is_read : 1;
+  u64 is_atomic : 1;
+  u64 size_log : 2;
+  u64 _ : 11;
+  u64 addr : kCompressedAddrBits;
+  u64 pc;
+};
+static_assert(sizeof(EventAccessExt) == 16, "bad EventAccessExt size");
+
+// Access to a memory range.
+struct EventAccessRange {
+  static constexpr uptr kSizeLoBits = 13;
+
+  u64 is_access : 1;   // = 0
+  u64 is_func : 1;     // = 0
+  EventType type : 3;  // = EventType::kAccessRange
+  u64 is_read : 1;
+  u64 is_free : 1;
+  u64 size_lo : kSizeLoBits;
+  u64 pc : kCompressedAddrBits;
+  u64 addr : kCompressedAddrBits;
+  u64 size_hi : 64 - kCompressedAddrBits;
+};
+static_assert(sizeof(EventAccessRange) == 16, "bad EventAccessRange size");
+
+// Mutex lock.
+struct EventLock {
+  static constexpr uptr kStackIDLoBits = 15;
+
+  u64 is_access : 1;   // = 0
+  u64 is_func : 1;     // = 0
+  EventType type : 3;  // = EventType::kLock or EventType::kRLock
+  u64 pc : kCompressedAddrBits;
+  u64 stack_lo : kStackIDLoBits;
+  u64 stack_hi : sizeof(StackID) * kByteBits - kStackIDLoBits;
+  u64 _ : 3;
+  u64 addr : kCompressedAddrBits;
+};
+static_assert(sizeof(EventLock) == 16, "bad EventLock size");
+
+// Mutex unlock.
+struct EventUnlock {
+  u64 is_access : 1;   // = 0
+  u64 is_func : 1;     // = 0
+  EventType type : 3;  // = EventType::kUnlock
+  u64 _ : 15;
+  u64 addr : kCompressedAddrBits;
+};
+static_assert(sizeof(EventUnlock) == 8, "bad EventUnlock size");
+
+// Time change event.
+struct EventTime {
+  u64 is_access : 1;   // = 0
+  u64 is_func : 1;     // = 0
+  EventType type : 3;  // = EventType::kTime
+  u64 sid : sizeof(Sid) * kByteBits;
+  u64 epoch : kEpochBits;
+  u64 _ : 64 - 5 - sizeof(Sid) * kByteBits - kEpochBits;
+};
+static_assert(sizeof(EventTime) == 8, "bad EventTime size");
+
+struct Trace;
+
+struct TraceHeader {
+  Trace* trace = nullptr;  // back-pointer to Trace containing this part
+  INode trace_parts;       // in Trace::parts
+};
+
+struct TracePart : TraceHeader {
+  static constexpr uptr kByteSize = 256 << 10;
+  static constexpr uptr kSize =
+      (kByteSize - sizeof(TraceHeader)) / sizeof(Event);
+  // TraceAcquire does a fast event pointer overflow check by comparing
+  // pointer into TracePart::events with kAlignment mask. Since TracePart's
+  // are allocated page-aligned, this check detects end of the array
+  // (it also have false positives in the middle that are filtered separately).
+  // This also requires events to be the last field.
+  static constexpr uptr kAlignment = 0xff0;
+  Event events[kSize];
+
+  TracePart() {}
+};
+static_assert(sizeof(TracePart) == TracePart::kByteSize, "bad TracePart size");
+
+struct Trace {
+  Mutex mtx;
+  IList<TraceHeader, &TraceHeader::trace_parts, TracePart> parts;
+  Event* final_pos =
+      nullptr;  // final position in the last part for finished threads
+
+  Trace() : mtx(MutexTypeTrace) {}
+};
+
+}  // namespace v3
+
 }  // namespace __tsan
 
 #endif  // TSAN_TRACE_H

compiler-rt/lib/tsan/tests/unit/CMakeLists.txt

 set(TSAN_UNIT_TEST_SOURCES
   tsan_clock_test.cpp
   tsan_dense_alloc_test.cpp
   tsan_flags_test.cpp
   tsan_ilist_test.cpp
   tsan_mman_test.cpp
   tsan_shadow_test.cpp
   tsan_stack_test.cpp
   tsan_sync_test.cpp
+  tsan_trace_test.cpp
   tsan_unit_test_main.cpp
   tsan_vector_clock_test.cpp
   )
 
 add_tsan_unittest(TsanUnitTest
   SOURCES ${TSAN_UNIT_TEST_SOURCES})

compiler-rt/lib/tsan/tests/unit/tsan_trace_test.cpp

+//===-- tsan_trace_test.cpp -----------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// This file is a part of ThreadSanitizer (TSan), a race detector.
+//
+//===----------------------------------------------------------------------===//
+#include "tsan_trace.h"
+
+#include <pthread.h>
+
+#include "gtest/gtest.h"
+#include "tsan_rtl.h"
+
+namespace __tsan {
+
+using namespace v3;
+
+// We need to run all trace tests in a new thread,
+// so that the thread trace is empty initially.
+static void run_in_thread(void *(*f)(void *)) {
+  pthread_t th;
+  pthread_create(&th, nullptr, f, nullptr);
+  pthread_join(th, nullptr);
+}
+
+TEST(Trace, Basic) {
+  struct Thread {
+    static void *Func(void *arg) {
+      // A basic test with some function entry/exit events,
+      // some mutex lock/unlock events and some other distracting
+      // memory events.
+      ThreadState *thr = cur_thread();
+      TraceFunc(thr, 0x1000);
+      TraceFunc(thr, 0x1001);
+      TraceMutexLock(thr, v3::EventType::kLock, 0x4000, 0x5000, 0x6000);
+      TraceMutexLock(thr, v3::EventType::kLock, 0x4001, 0x5001, 0x6001);
+      TraceMutexUnlock(thr, 0x5000);
+      TraceFunc(thr);
+      CHECK(TryTraceMemoryAccess(thr, 0x2001, 0x3001, 8, kAccessRead));
+      TraceMutexLock(thr, v3::EventType::kRLock, 0x4002, 0x5002, 0x6002);
+      TraceFunc(thr, 0x1002);
+      CHECK(TryTraceMemoryAccess(thr, 0x2000, 0x3000, 8, kAccessRead));
+      // This is the access we want to find.
+      // The previous one is equivalent, but RestoreStack must prefer
+      // the last of the matchig accesses.
+      CHECK(TryTraceMemoryAccess(thr, 0x2002, 0x3000, 8, kAccessRead));
+      Lock lock1(&ctx->slot_mtx);
+      ThreadRegistryLock lock2(&ctx->thread_registry);
+      VarSizeStackTrace stk;
+      MutexSet mset;
+      uptr tag = kExternalTagNone;
+      bool res =
+          RestoreStack(thr->tid, v3::EventType::kAccessExt, thr->sid,
+                       thr->epoch, 0x3000, 8, kAccessRead, &stk, &mset, &tag);
+      CHECK(res);
+      CHECK_EQ(stk.size, 3);
+      CHECK_EQ(stk.trace[0], 0x1000);
+      CHECK_EQ(stk.trace[1], 0x1002);
+      CHECK_EQ(stk.trace[2], 0x2002);
+      CHECK_EQ(mset.Size(), 2);
+      CHECK_EQ(mset.Get(0).addr, 0x5001);
+      CHECK_EQ(mset.Get(0).stack_id, 0x6001);
+      CHECK_EQ(mset.Get(0).write, true);
+      CHECK_EQ(mset.Get(1).addr, 0x5002);
+      CHECK_EQ(mset.Get(1).stack_id, 0x6002);
+      CHECK_EQ(mset.Get(1).write, false);
+      CHECK_EQ(tag, kExternalTagNone);
+      return nullptr;
+    }
+  };
+  run_in_thread(Thread::Func);
+}
+
+}  // namespace __tsan