//===-- 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