1 // Copyright 2019 The Abseil Authors.
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // https://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14
15 #ifndef ABSL_PROFILING_INTERNAL_PERIODIC_SAMPLER_H_
16 #define ABSL_PROFILING_INTERNAL_PERIODIC_SAMPLER_H_
17
18 #include <stdint.h>
19
20 #include <atomic>
21
22 #include "absl/base/optimization.h"
23 #include "absl/profiling/internal/exponential_biased.h"
24
25 namespace absl {
26 ABSL_NAMESPACE_BEGIN
27 namespace profiling_internal {
28
29 // PeriodicSamplerBase provides the basic period sampler implementation.
30 //
31 // This is the base class for the templated PeriodicSampler class, which holds
32 // a global std::atomic value identified by a user defined tag, such that
33 // each specific PeriodSampler implementation holds its own global period.
34 //
35 // PeriodicSamplerBase is thread-compatible except where stated otherwise.
36 class PeriodicSamplerBase {
37 public:
38 // PeriodicSamplerBase is trivial / copyable / movable / destructible.
39 PeriodicSamplerBase() = default;
40 PeriodicSamplerBase(PeriodicSamplerBase&&) = default;
41 PeriodicSamplerBase(const PeriodicSamplerBase&) = default;
42
43 // Returns true roughly once every `period` calls. This is established by a
44 // randomly picked `stride` that is counted down on each call to `Sample`.
45 // This stride is picked such that the probability of `Sample()` returning
46 // true is 1 in `period`.
47 inline bool Sample() noexcept;
48
49 // The below methods are intended for optimized use cases where the
50 // size of the inlined fast path code is highly important. Applications
51 // should use the `Sample()` method unless they have proof that their
52 // specific use case requires the optimizations offered by these methods.
53 //
54 // An example of such a use case is SwissTable sampling. All sampling checks
55 // are in inlined SwissTable methods, and the number of call sites is huge.
56 // In this case, the inlined code size added to each translation unit calling
57 // SwissTable methods is non-trivial.
58 //
59 // The `SubtleMaybeSample()` function spuriously returns true even if the
60 // function should not be sampled, applications MUST match each call to
61 // 'SubtleMaybeSample()' returning true with a `SubtleConfirmSample()` call,
62 // and use the result of the latter as the sampling decision.
63 // In other words: the code should logically be equivalent to:
64 //
65 // if (SubtleMaybeSample() && SubtleConfirmSample()) {
66 // // Sample this call
67 // }
68 //
69 // In the 'inline-size' optimized case, the `SubtleConfirmSample()` call can
70 // be placed out of line, for example, the typical use case looks as follows:
71 //
72 // // --- frobber.h -----------
73 // void FrobberSampled();
74 //
75 // inline void FrobberImpl() {
76 // // ...
77 // }
78 //
79 // inline void Frobber() {
80 // if (ABSL_PREDICT_FALSE(sampler.SubtleMaybeSample())) {
81 // FrobberSampled();
82 // } else {
83 // FrobberImpl();
84 // }
85 // }
86 //
87 // // --- frobber.cc -----------
88 // void FrobberSampled() {
89 // if (!sampler.SubtleConfirmSample())) {
90 // // Spurious false positive
91 // FrobberImpl();
92 // return;
93 // }
94 //
95 // // Sampled execution
96 // // ...
97 // }
98 inline bool SubtleMaybeSample() noexcept;
99 bool SubtleConfirmSample() noexcept;
100
101 protected:
102 // We explicitly don't use a virtual destructor as this class is never
103 // virtually destroyed, and it keeps the class trivial, which avoids TLS
104 // prologue and epilogue code for our TLS instances.
105 ~PeriodicSamplerBase() = default;
106
107 // Returns the next stride for our sampler.
108 // This function is virtual for testing purposes only.
109 virtual int64_t GetExponentialBiased(int period) noexcept;
110
111 private:
112 // Returns the current period of this sampler. Thread-safe.
113 virtual int period() const noexcept = 0;
114
115 // Keep and decrement stride_ as an unsigned integer, but compare the value
116 // to zero casted as a signed int. clang and msvc do not create optimum code
117 // if we use signed for the combined decrement and sign comparison.
118 //
119 // Below 3 alternative options, all compiles generate the best code
120 // using the unsigned increment <---> signed int comparison option.
121 //
122 // Option 1:
123 // int64_t stride_;
124 // if (ABSL_PREDICT_TRUE(++stride_ < 0)) { ... }
125 //
126 // GCC x64 (OK) : https://gcc.godbolt.org/z/R5MzzA
127 // GCC ppc (OK) : https://gcc.godbolt.org/z/z7NZAt
128 // Clang x64 (BAD): https://gcc.godbolt.org/z/t4gPsd
129 // ICC x64 (OK) : https://gcc.godbolt.org/z/rE6s8W
130 // MSVC x64 (OK) : https://gcc.godbolt.org/z/ARMXqS
131 //
132 // Option 2:
133 // int64_t stride_ = 0;
134 // if (ABSL_PREDICT_TRUE(--stride_ >= 0)) { ... }
135 //
136 // GCC x64 (OK) : https://gcc.godbolt.org/z/jSQxYK
137 // GCC ppc (OK) : https://gcc.godbolt.org/z/VJdYaA
138 // Clang x64 (BAD): https://gcc.godbolt.org/z/Xm4NjX
139 // ICC x64 (OK) : https://gcc.godbolt.org/z/4snaFd
140 // MSVC x64 (BAD): https://gcc.godbolt.org/z/BgnEKE
141 //
142 // Option 3:
143 // uint64_t stride_;
144 // if (ABSL_PREDICT_TRUE(static_cast<int64_t>(++stride_) < 0)) { ... }
145 //
146 // GCC x64 (OK) : https://gcc.godbolt.org/z/bFbfPy
147 // GCC ppc (OK) : https://gcc.godbolt.org/z/S9KkUE
148 // Clang x64 (OK) : https://gcc.godbolt.org/z/UYzRb4
149 // ICC x64 (OK) : https://gcc.godbolt.org/z/ptTNfD
150 // MSVC x64 (OK) : https://gcc.godbolt.org/z/76j4-5
151 uint64_t stride_ = 0;
152 absl::profiling_internal::ExponentialBiased rng_;
153 };
154
SubtleMaybeSample()155 inline bool PeriodicSamplerBase::SubtleMaybeSample() noexcept {
156 // See comments on `stride_` for the unsigned increment / signed compare.
157 if (ABSL_PREDICT_TRUE(static_cast<int64_t>(++stride_) < 0)) {
158 return false;
159 }
160 return true;
161 }
162
Sample()163 inline bool PeriodicSamplerBase::Sample() noexcept {
164 return ABSL_PREDICT_FALSE(SubtleMaybeSample()) ? SubtleConfirmSample()
165 : false;
166 }
167
168 // PeriodicSampler is a concreted periodic sampler implementation.
169 // The user provided Tag identifies the implementation, and is required to
170 // isolate the global state of this instance from other instances.
171 //
172 // Typical use case:
173 //
174 // struct HashTablezTag {};
175 // thread_local PeriodicSampler sampler;
176 //
177 // void HashTableSamplingLogic(...) {
178 // if (sampler.Sample()) {
179 // HashTableSlowSamplePath(...);
180 // }
181 // }
182 //
183 template <typename Tag, int default_period = 0>
184 class PeriodicSampler final : public PeriodicSamplerBase {
185 public:
186 ~PeriodicSampler() = default;
187
period()188 int period() const noexcept final {
189 return period_.load(std::memory_order_relaxed);
190 }
191
192 // Sets the global period for this sampler. Thread-safe.
193 // Setting a period of 0 disables the sampler, i.e., every call to Sample()
194 // will return false. Setting a period of 1 puts the sampler in 'always on'
195 // mode, i.e., every call to Sample() returns true.
SetGlobalPeriod(int period)196 static void SetGlobalPeriod(int period) {
197 period_.store(period, std::memory_order_relaxed);
198 }
199
200 private:
201 static std::atomic<int> period_;
202 };
203
204 template <typename Tag, int default_period>
205 std::atomic<int> PeriodicSampler<Tag, default_period>::period_(default_period);
206
207 } // namespace profiling_internal
208 ABSL_NAMESPACE_END
209 } // namespace absl
210
211 #endif // ABSL_PROFILING_INTERNAL_PERIODIC_SAMPLER_H_
212