1//===-- tsan_adaptive_delay.h -----------------------------------*- C++ -*-===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This file is a part of ThreadSanitizer (TSan), a race detector.
10//
11//===----------------------------------------------------------------------===//
12
13#ifndef TSAN_ADAPTIVE_DELAY_H
14#define TSAN_ADAPTIVE_DELAY_H
15
16#include "sanitizer_common/sanitizer_common.h"
17#include "sanitizer_common/sanitizer_internal_defs.h"
18
19namespace __tsan {
20
21// AdaptiveDelay injects delays at synchronization points, atomic operations,
22// and thread lifecycle events to increase the likelihood of exposing data
23// races. The delay injection is controlled by an approximate time budget to
24// maintain a configurable overhead target.
25//
26// SyncOp() delays non-atomic synchronization points (those with clear
27// happens-before relationships):
28// - Acquire operations like locking a mutex delays before the mutex is locked.
29// - Release operations like unlocking a mutex delays after the mutex is
30// unlocked
31// These are more likely to expose interesting (rare) thread interleavings.
32// For example, delaying a thread that unlocks a mutex from running to allow
33// newly woken thread to execute before the unlocking thread would normally
34// execute.
35//
36// TODO:
37// - Move the adaptive delay implementation into sanitizer_common so that
38// ASAN can also leverage it in pthread_* interceptors
39// - Integrate into other interceptors like libdispatch.
40struct AdaptiveDelay {
41 ALWAYS_INLINE static void Init() { InitImpl(); }
42
43 ALWAYS_INLINE static void SyncOp() {
44 if (!is_adaptive_delay_enabled)
45 return;
46 SyncOpImpl();
47 }
48
49 ALWAYS_INLINE static void AtomicOpFence(int mo) {
50 if (!is_adaptive_delay_enabled)
51 return;
52 AtomicOpFenceImpl(mo);
53 }
54
55 ALWAYS_INLINE static void AtomicOpAddr(__sanitizer::uptr addr, int mo) {
56 if (!is_adaptive_delay_enabled)
57 return;
58 AtomicOpAddrImpl(addr, mo);
59 }
60
61 ALWAYS_INLINE static void AfterThreadCreation() {
62 if (!is_adaptive_delay_enabled)
63 return;
64 AfterThreadCreationImpl();
65 }
66
67 ALWAYS_INLINE static void BeforeChildThreadRuns() {
68 if (!is_adaptive_delay_enabled)
69 return;
70 BeforeChildThreadRunsImpl();
71 }
72
73 private:
74 static void InitImpl();
75
76 static void SyncOpImpl();
77
78 static void AtomicOpFenceImpl(int mo);
79 static void AtomicOpAddrImpl(__sanitizer::uptr addr, int mo);
80
81 static void AfterThreadCreationImpl();
82 static void BeforeChildThreadRunsImpl();
83
84 static bool is_adaptive_delay_enabled;
85};
86
87// The runtime defines cur_thread() to retrieve TLS thread state, and it
88// takes care of platform specific implementation details. The AdaptiveDelay
89// implementation stores per-thread data in this struct, which is embedded
90// in cur_thread().
91struct AdaptiveDelayState {
92 // For the adaptive delay implementation
93 // Sliding window delay tracking: 2 buckets of 30 seconds each
94 u64 delay_buckets_ns_[2]; // [0] = older 30s, [1] = newer 30s
95 u64 bucket_start_ns_; // When current bucket (index 1) started
96 u64 bucket0_window_ns; // 0ns before the first bucket has rolled, and set to
97 // the bucket window time after This handles the case
98 // where, before the program has ran one bucket window
99 // duration, we should not include the previous bucket
100 // duration in the overhead percent calculation.
101 unsigned int tls_random_seed_;
102 bool tls_initialized_;
103};
104
105// Fixed-point arithmetic type that mimics floating point operations
106class Percent {
107 using u32 = __sanitizer::u32;
108 using u64 = __sanitizer::u64;
109
110 u32 bp_{}; // basis points (0-10000 represents 0.0-1.0)
111 bool is_valid_{};
112
113 static constexpr u32 kBasisPointsPerUnit = 10000;
114
115 Percent(u32 bp, bool is_valid) : bp_(bp), is_valid_(is_valid) {}
116
117 public:
118 Percent() = default;
119 Percent(const Percent&) = default;
120 Percent& operator=(const Percent&) = default;
121 Percent(Percent&&) = default;
122 Percent& operator=(Percent&&) = default;
123
124 static Percent FromPct(u32 pct) { return Percent{pct * 100, true}; }
125 static Percent FromRatio(u64 numerator, u64 denominator) {
126 if (denominator == 0)
127 return Percent{0, false};
128 // Avoid overflow: scale down if needed
129 if (numerator > UINT64_MAX / kBasisPointsPerUnit) {
130 return Percent{(u32)((numerator / denominator) * kBasisPointsPerUnit),
131 true};
132 }
133 return Percent{(u32)((numerator * kBasisPointsPerUnit) / denominator),
134 true};
135 }
136
137 bool IsValid() const { return is_valid_; }
138
139 // Returns true with probability equal to the percentage.
140 bool RandomCheck(u32* seed) const {
141 return (Rand(state: seed) % kBasisPointsPerUnit) < bp_;
142 }
143
144 int GetPct() const { return bp_ / 100; }
145 int GetBasisPoints() const { return bp_; }
146
147 bool operator==(const Percent& other) const { return bp_ == other.bp_; }
148 bool operator!=(const Percent& other) const { return bp_ != other.bp_; }
149 bool operator<(const Percent& other) const { return bp_ < other.bp_; }
150 bool operator>(const Percent& other) const { return bp_ > other.bp_; }
151 bool operator<=(const Percent& other) const { return bp_ <= other.bp_; }
152 bool operator>=(const Percent& other) const { return bp_ >= other.bp_; }
153
154 Percent operator-(const Percent& other) const {
155 if (!is_valid_ || !other.is_valid_)
156 return Percent{0, false};
157 if (bp_ < other.bp_)
158 return Percent{0, false};
159 return Percent{bp_ - other.bp_, true};
160 }
161
162 Percent operator/(const Percent& other) const {
163 if (!is_valid_ || !other.is_valid_)
164 return Percent{0, false};
165 if (other.bp_ == 0)
166 return Percent{0, false};
167 return Percent{(bp_ * kBasisPointsPerUnit) / other.bp_, true};
168 }
169};
170
171} // namespace __tsan
172
173#endif // TSAN_ADAPTIVE_DELAY_H
174