1// Copyright 2018 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#include "absl/container/internal/hashtablez_sampler.h"
16
17#include <atomic>
18#include <cassert>
19#include <cmath>
20#include <functional>
21#include <limits>
22
23#include "absl/base/attributes.h"
24#include "absl/container/internal/have_sse.h"
25#include "absl/debugging/stacktrace.h"
26#include "absl/memory/memory.h"
27#include "absl/synchronization/mutex.h"
28
29namespace absl {
30namespace container_internal {
31constexpr int HashtablezInfo::kMaxStackDepth;
32
33namespace {
34ABSL_CONST_INIT std::atomic<bool> g_hashtablez_enabled{
35 false
36};
37ABSL_CONST_INIT std::atomic<int32_t> g_hashtablez_sample_parameter{1 << 10};
38ABSL_CONST_INIT std::atomic<int32_t> g_hashtablez_max_samples{1 << 20};
39
40// Returns the next pseudo-random value.
41// pRNG is: aX+b mod c with a = 0x5DEECE66D, b = 0xB, c = 1<<48
42// This is the lrand64 generator.
43uint64_t NextRandom(uint64_t rnd) {
44 const uint64_t prng_mult = uint64_t{0x5DEECE66D};
45 const uint64_t prng_add = 0xB;
46 const uint64_t prng_mod_power = 48;
47 const uint64_t prng_mod_mask = ~(~uint64_t{0} << prng_mod_power);
48 return (prng_mult * rnd + prng_add) & prng_mod_mask;
49}
50
51// Generates a geometric variable with the specified mean.
52// This is done by generating a random number between 0 and 1 and applying
53// the inverse cumulative distribution function for an exponential.
54// Specifically: Let m be the inverse of the sample period, then
55// the probability distribution function is m*exp(-mx) so the CDF is
56// p = 1 - exp(-mx), so
57// q = 1 - p = exp(-mx)
58// log_e(q) = -mx
59// -log_e(q)/m = x
60// log_2(q) * (-log_e(2) * 1/m) = x
61// In the code, q is actually in the range 1 to 2**26, hence the -26 below
62//
63int64_t GetGeometricVariable(int64_t mean) {
64#if ABSL_HAVE_THREAD_LOCAL
65 thread_local
66#else // ABSL_HAVE_THREAD_LOCAL
67 // SampleSlow and hence GetGeometricVariable is guarded by a single mutex when
68 // there are not thread locals. Thus, a single global rng is acceptable for
69 // that case.
70 static
71#endif // ABSL_HAVE_THREAD_LOCAL
72 uint64_t rng = []() {
73 // We don't get well distributed numbers from this so we call
74 // NextRandom() a bunch to mush the bits around. We use a global_rand
75 // to handle the case where the same thread (by memory address) gets
76 // created and destroyed repeatedly.
77 ABSL_CONST_INIT static std::atomic<uint32_t> global_rand(0);
78 uint64_t r = reinterpret_cast<uint64_t>(&rng) +
79 global_rand.fetch_add(1, std::memory_order_relaxed);
80 for (int i = 0; i < 20; ++i) {
81 r = NextRandom(r);
82 }
83 return r;
84 }();
85
86 rng = NextRandom(rng);
87
88 // Take the top 26 bits as the random number
89 // (This plus the 1<<58 sampling bound give a max possible step of
90 // 5194297183973780480 bytes.)
91 const uint64_t prng_mod_power = 48; // Number of bits in prng
92 // The uint32_t cast is to prevent a (hard-to-reproduce) NAN
93 // under piii debug for some binaries.
94 double q = static_cast<uint32_t>(rng >> (prng_mod_power - 26)) + 1.0;
95 // Put the computed p-value through the CDF of a geometric.
96 double interval = (log2(q) - 26) * (-std::log(2.0) * mean);
97
98 // Very large values of interval overflow int64_t. If we happen to
99 // hit such improbable condition, we simply cheat and clamp interval
100 // to largest supported value.
101 if (interval > static_cast<double>(std::numeric_limits<int64_t>::max() / 2)) {
102 return std::numeric_limits<int64_t>::max() / 2;
103 }
104
105 // Small values of interval are equivalent to just sampling next time.
106 if (interval < 1) {
107 return 1;
108 }
109 return static_cast<int64_t>(interval);
110}
111
112} // namespace
113
114HashtablezSampler& HashtablezSampler::Global() {
115 static auto* sampler = new HashtablezSampler();
116 return *sampler;
117}
118
119HashtablezSampler::DisposeCallback HashtablezSampler::SetDisposeCallback(
120 DisposeCallback f) {
121 return dispose_.exchange(f, std::memory_order_relaxed);
122}
123
124HashtablezInfo::HashtablezInfo() { PrepareForSampling(); }
125HashtablezInfo::~HashtablezInfo() = default;
126
127void HashtablezInfo::PrepareForSampling() {
128 capacity.store(0, std::memory_order_relaxed);
129 size.store(0, std::memory_order_relaxed);
130 num_erases.store(0, std::memory_order_relaxed);
131 max_probe_length.store(0, std::memory_order_relaxed);
132 total_probe_length.store(0, std::memory_order_relaxed);
133 hashes_bitwise_or.store(0, std::memory_order_relaxed);
134 hashes_bitwise_and.store(~size_t{}, std::memory_order_relaxed);
135
136 create_time = absl::Now();
137 // The inliner makes hardcoded skip_count difficult (especially when combined
138 // with LTO). We use the ability to exclude stacks by regex when encoding
139 // instead.
140 depth = absl::GetStackTrace(stack, HashtablezInfo::kMaxStackDepth,
141 /* skip_count= */ 0);
142 dead = nullptr;
143}
144
145HashtablezSampler::HashtablezSampler()
146 : dropped_samples_(0), size_estimate_(0), all_(nullptr), dispose_(nullptr) {
147 absl::MutexLock l(&graveyard_.init_mu);
148 graveyard_.dead = &graveyard_;
149}
150
151HashtablezSampler::~HashtablezSampler() {
152 HashtablezInfo* s = all_.load(std::memory_order_acquire);
153 while (s != nullptr) {
154 HashtablezInfo* next = s->next;
155 delete s;
156 s = next;
157 }
158}
159
160void HashtablezSampler::PushNew(HashtablezInfo* sample) {
161 sample->next = all_.load(std::memory_order_relaxed);
162 while (!all_.compare_exchange_weak(sample->next, sample,
163 std::memory_order_release,
164 std::memory_order_relaxed)) {
165 }
166}
167
168void HashtablezSampler::PushDead(HashtablezInfo* sample) {
169 if (auto* dispose = dispose_.load(std::memory_order_relaxed)) {
170 dispose(*sample);
171 }
172
173 absl::MutexLock graveyard_lock(&graveyard_.init_mu);
174 absl::MutexLock sample_lock(&sample->init_mu);
175 sample->dead = graveyard_.dead;
176 graveyard_.dead = sample;
177}
178
179HashtablezInfo* HashtablezSampler::PopDead() {
180 absl::MutexLock graveyard_lock(&graveyard_.init_mu);
181
182 // The list is circular, so eventually it collapses down to
183 // graveyard_.dead == &graveyard_
184 // when it is empty.
185 HashtablezInfo* sample = graveyard_.dead;
186 if (sample == &graveyard_) return nullptr;
187
188 absl::MutexLock sample_lock(&sample->init_mu);
189 graveyard_.dead = sample->dead;
190 sample->PrepareForSampling();
191 return sample;
192}
193
194HashtablezInfo* HashtablezSampler::Register() {
195 int64_t size = size_estimate_.fetch_add(1, std::memory_order_relaxed);
196 if (size > g_hashtablez_max_samples.load(std::memory_order_relaxed)) {
197 size_estimate_.fetch_sub(1, std::memory_order_relaxed);
198 dropped_samples_.fetch_add(1, std::memory_order_relaxed);
199 return nullptr;
200 }
201
202 HashtablezInfo* sample = PopDead();
203 if (sample == nullptr) {
204 // Resurrection failed. Hire a new warlock.
205 sample = new HashtablezInfo();
206 PushNew(sample);
207 }
208
209 return sample;
210}
211
212void HashtablezSampler::Unregister(HashtablezInfo* sample) {
213 PushDead(sample);
214 size_estimate_.fetch_sub(1, std::memory_order_relaxed);
215}
216
217int64_t HashtablezSampler::Iterate(
218 const std::function<void(const HashtablezInfo& stack)>& f) {
219 HashtablezInfo* s = all_.load(std::memory_order_acquire);
220 while (s != nullptr) {
221 absl::MutexLock l(&s->init_mu);
222 if (s->dead == nullptr) {
223 f(*s);
224 }
225 s = s->next;
226 }
227
228 return dropped_samples_.load(std::memory_order_relaxed);
229}
230
231HashtablezInfo* SampleSlow(int64_t* next_sample) {
232 if (kAbslContainerInternalSampleEverything) {
233 *next_sample = 1;
234 return HashtablezSampler::Global().Register();
235 }
236
237 bool first = *next_sample < 0;
238 *next_sample = GetGeometricVariable(
239 g_hashtablez_sample_parameter.load(std::memory_order_relaxed));
240
241 // g_hashtablez_enabled can be dynamically flipped, we need to set a threshold
242 // low enough that we will start sampling in a reasonable time, so we just use
243 // the default sampling rate.
244 if (!g_hashtablez_enabled.load(std::memory_order_relaxed)) return nullptr;
245
246 // We will only be negative on our first count, so we should just retry in
247 // that case.
248 if (first) {
249 if (ABSL_PREDICT_TRUE(--*next_sample > 0)) return nullptr;
250 return SampleSlow(next_sample);
251 }
252
253 return HashtablezSampler::Global().Register();
254}
255
256#if ABSL_PER_THREAD_TLS == 1
257ABSL_PER_THREAD_TLS_KEYWORD int64_t global_next_sample = 0;
258#endif // ABSL_PER_THREAD_TLS == 1
259
260void UnsampleSlow(HashtablezInfo* info) {
261 HashtablezSampler::Global().Unregister(info);
262}
263
264void RecordInsertSlow(HashtablezInfo* info, size_t hash,
265 size_t distance_from_desired) {
266 // SwissTables probe in groups of 16, so scale this to count items probes and
267 // not offset from desired.
268 size_t probe_length = distance_from_desired;
269#if SWISSTABLE_HAVE_SSE2
270 probe_length /= 16;
271#else
272 probe_length /= 8;
273#endif
274
275 info->hashes_bitwise_and.fetch_and(hash, std::memory_order_relaxed);
276 info->hashes_bitwise_or.fetch_or(hash, std::memory_order_relaxed);
277 info->max_probe_length.store(
278 std::max(info->max_probe_length.load(std::memory_order_relaxed),
279 probe_length),
280 std::memory_order_relaxed);
281 info->total_probe_length.fetch_add(probe_length, std::memory_order_relaxed);
282 info->size.fetch_add(1, std::memory_order_relaxed);
283}
284
285void SetHashtablezEnabled(bool enabled) {
286 g_hashtablez_enabled.store(enabled, std::memory_order_release);
287}
288
289void SetHashtablezSampleParameter(int32_t rate) {
290 if (rate > 0) {
291 g_hashtablez_sample_parameter.store(rate, std::memory_order_release);
292 } else {
293 ABSL_RAW_LOG(ERROR, "Invalid hashtablez sample rate: %lld",
294 static_cast<long long>(rate)); // NOLINT(runtime/int)
295 }
296}
297
298void SetHashtablezMaxSamples(int32_t max) {
299 if (max > 0) {
300 g_hashtablez_max_samples.store(max, std::memory_order_release);
301 } else {
302 ABSL_RAW_LOG(ERROR, "Invalid hashtablez max samples: %lld",
303 static_cast<long long>(max)); // NOLINT(runtime/int)
304 }
305}
306
307} // namespace container_internal
308} // namespace absl
309