blob: 01bb7b34f43a2c5b6e3f1ee93a44db51033bf739 [file] [log] [blame]
//===-- 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_ilist.h"
#include "tsan_mutexset.h"
#include "tsan_stack_trace.h"
namespace __tsan {
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;
static_assert(kPCBits + kCompressedAddrBits + 5 == 64,
"unused bits in EventAccess");
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 {
// Note: precisely specifying the unused parts of the bitfield is critical for
// performance. If we don't specify them, compiler will generate code to load
// the old value and shuffle it to extract the unused bits to apply to the new
// value. If we specify the unused part and store 0 in there, all that
// unnecessary code goes away (store of the 0 const is combined with other
// constant parts).
static constexpr uptr kUnusedBits = 11;
static_assert(kCompressedAddrBits + kUnusedBits + 9 == 64,
"unused bits in 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 _ : kUnusedBits;
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;
static_assert(kCompressedAddrBits + kSizeLoBits + 7 == 64,
"unused bits in EventAccessRange");
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;
static constexpr uptr kStackIDHiBits =
sizeof(StackID) * kByteBits - kStackIDLoBits;
static constexpr uptr kUnusedBits = 3;
static_assert(kCompressedAddrBits + kStackIDLoBits + 5 == 64,
"unused bits in EventLock");
static_assert(kCompressedAddrBits + kStackIDHiBits + kUnusedBits == 64,
"unused bits in EventLock");
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 _ : kUnusedBits;
u64 addr : kCompressedAddrBits;
};
static_assert(sizeof(EventLock) == 16, "bad EventLock size");
// Mutex unlock.
struct EventUnlock {
static constexpr uptr kUnusedBits = 15;
static_assert(kCompressedAddrBits + kUnusedBits + 5 == 64,
"unused bits in EventUnlock");
u64 is_access : 1; // = 0
u64 is_func : 1; // = 0
EventType type : 3; // = EventType::kUnlock
u64 _ : kUnusedBits;
u64 addr : kCompressedAddrBits;
};
static_assert(sizeof(EventUnlock) == 8, "bad EventUnlock size");
// Time change event.
struct EventTime {
static constexpr uptr kUnusedBits = 37;
static_assert(kUnusedBits + sizeof(Sid) * kByteBits + kEpochBits + 5 == 64,
"unused bits in 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 _ : kUnusedBits;
};
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
INode global; // in Contex::trace_part_recycle
};
struct TracePart : TraceHeader {
// There are a lot of goroutines in Go, so we use smaller parts.
static constexpr uptr kByteSize = (SANITIZER_GO ? 128 : 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;
// First node non-queued into ctx->trace_part_recycle.
TracePart* local_head;
// Final position in the last part for finished threads.
Event* final_pos = nullptr;
// Number of trace parts allocated on behalf of this trace specifically.
// Total number of parts in this trace can be larger if we retake some
// parts from other traces.
uptr parts_allocated = 0;
Trace() : mtx(MutexTypeTrace) {}
// We need at least 3 parts per thread, because we want to keep at last
// 2 parts per thread that are not queued into ctx->trace_part_recycle
// (the current one being filled and one full part that ensures that
// we always have at least one part worth of previous memory accesses).
static constexpr uptr kMinParts = 3;
static constexpr uptr kFinishedThreadLo = 16;
static constexpr uptr kFinishedThreadHi = 64;
};
} // namespace __tsan
#endif // TSAN_TRACE_H