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/base/internal/exponential_biased.h"
25 #include "absl/container/internal/have_sse.h"
26 #include "absl/debugging/stacktrace.h"
27 #include "absl/memory/memory.h"
28 #include "absl/synchronization/mutex.h"
29
30 namespace absl {
31 ABSL_NAMESPACE_BEGIN
32 namespace container_internal {
33 constexpr int HashtablezInfo::kMaxStackDepth;
34
35 namespace {
36 ABSL_CONST_INIT std::atomic<bool> g_hashtablez_enabled{
37 false
38 };
39 ABSL_CONST_INIT std::atomic<int32_t> g_hashtablez_sample_parameter{1 << 10};
40 ABSL_CONST_INIT std::atomic<int32_t> g_hashtablez_max_samples{1 << 20};
41
42 #if defined(ABSL_INTERNAL_HASHTABLEZ_SAMPLE)
43 ABSL_PER_THREAD_TLS_KEYWORD absl::base_internal::ExponentialBiased
44 g_exponential_biased_generator;
45 #endif
46
47 } // namespace
48
49 #if defined(ABSL_INTERNAL_HASHTABLEZ_SAMPLE)
50 ABSL_PER_THREAD_TLS_KEYWORD int64_t global_next_sample = 0;
51 #endif // defined(ABSL_INTERNAL_HASHTABLEZ_SAMPLE)
52
Global()53 HashtablezSampler& HashtablezSampler::Global() {
54 static auto* sampler = new HashtablezSampler();
55 return *sampler;
56 }
57
SetDisposeCallback(DisposeCallback f)58 HashtablezSampler::DisposeCallback HashtablezSampler::SetDisposeCallback(
59 DisposeCallback f) {
60 return dispose_.exchange(f, std::memory_order_relaxed);
61 }
62
HashtablezInfo()63 HashtablezInfo::HashtablezInfo() { PrepareForSampling(); }
64 HashtablezInfo::~HashtablezInfo() = default;
65
PrepareForSampling()66 void HashtablezInfo::PrepareForSampling() {
67 capacity.store(0, std::memory_order_relaxed);
68 size.store(0, std::memory_order_relaxed);
69 num_erases.store(0, std::memory_order_relaxed);
70 num_rehashes.store(0, std::memory_order_relaxed);
71 max_probe_length.store(0, std::memory_order_relaxed);
72 total_probe_length.store(0, std::memory_order_relaxed);
73 hashes_bitwise_or.store(0, std::memory_order_relaxed);
74 hashes_bitwise_and.store(~size_t{}, std::memory_order_relaxed);
75 hashes_bitwise_xor.store(0, std::memory_order_relaxed);
76
77 create_time = absl::Now();
78 // The inliner makes hardcoded skip_count difficult (especially when combined
79 // with LTO). We use the ability to exclude stacks by regex when encoding
80 // instead.
81 depth = absl::GetStackTrace(stack, HashtablezInfo::kMaxStackDepth,
82 /* skip_count= */ 0);
83 dead = nullptr;
84 }
85
HashtablezSampler()86 HashtablezSampler::HashtablezSampler()
87 : dropped_samples_(0), size_estimate_(0), all_(nullptr), dispose_(nullptr) {
88 absl::MutexLock l(&graveyard_.init_mu);
89 graveyard_.dead = &graveyard_;
90 }
91
~HashtablezSampler()92 HashtablezSampler::~HashtablezSampler() {
93 HashtablezInfo* s = all_.load(std::memory_order_acquire);
94 while (s != nullptr) {
95 HashtablezInfo* next = s->next;
96 delete s;
97 s = next;
98 }
99 }
100
PushNew(HashtablezInfo * sample)101 void HashtablezSampler::PushNew(HashtablezInfo* sample) {
102 sample->next = all_.load(std::memory_order_relaxed);
103 while (!all_.compare_exchange_weak(sample->next, sample,
104 std::memory_order_release,
105 std::memory_order_relaxed)) {
106 }
107 }
108
PushDead(HashtablezInfo * sample)109 void HashtablezSampler::PushDead(HashtablezInfo* sample) {
110 if (auto* dispose = dispose_.load(std::memory_order_relaxed)) {
111 dispose(*sample);
112 }
113
114 absl::MutexLock graveyard_lock(&graveyard_.init_mu);
115 absl::MutexLock sample_lock(&sample->init_mu);
116 sample->dead = graveyard_.dead;
117 graveyard_.dead = sample;
118 }
119
PopDead()120 HashtablezInfo* HashtablezSampler::PopDead() {
121 absl::MutexLock graveyard_lock(&graveyard_.init_mu);
122
123 // The list is circular, so eventually it collapses down to
124 // graveyard_.dead == &graveyard_
125 // when it is empty.
126 HashtablezInfo* sample = graveyard_.dead;
127 if (sample == &graveyard_) return nullptr;
128
129 absl::MutexLock sample_lock(&sample->init_mu);
130 graveyard_.dead = sample->dead;
131 sample->PrepareForSampling();
132 return sample;
133 }
134
Register()135 HashtablezInfo* HashtablezSampler::Register() {
136 int64_t size = size_estimate_.fetch_add(1, std::memory_order_relaxed);
137 if (size > g_hashtablez_max_samples.load(std::memory_order_relaxed)) {
138 size_estimate_.fetch_sub(1, std::memory_order_relaxed);
139 dropped_samples_.fetch_add(1, std::memory_order_relaxed);
140 return nullptr;
141 }
142
143 HashtablezInfo* sample = PopDead();
144 if (sample == nullptr) {
145 // Resurrection failed. Hire a new warlock.
146 sample = new HashtablezInfo();
147 PushNew(sample);
148 }
149
150 return sample;
151 }
152
Unregister(HashtablezInfo * sample)153 void HashtablezSampler::Unregister(HashtablezInfo* sample) {
154 PushDead(sample);
155 size_estimate_.fetch_sub(1, std::memory_order_relaxed);
156 }
157
Iterate(const std::function<void (const HashtablezInfo & stack)> & f)158 int64_t HashtablezSampler::Iterate(
159 const std::function<void(const HashtablezInfo& stack)>& f) {
160 HashtablezInfo* s = all_.load(std::memory_order_acquire);
161 while (s != nullptr) {
162 absl::MutexLock l(&s->init_mu);
163 if (s->dead == nullptr) {
164 f(*s);
165 }
166 s = s->next;
167 }
168
169 return dropped_samples_.load(std::memory_order_relaxed);
170 }
171
ShouldForceSampling()172 static bool ShouldForceSampling() {
173 enum ForceState {
174 kDontForce,
175 kForce,
176 kUninitialized
177 };
178 ABSL_CONST_INIT static std::atomic<ForceState> global_state{
179 kUninitialized};
180 ForceState state = global_state.load(std::memory_order_relaxed);
181 if (ABSL_PREDICT_TRUE(state == kDontForce)) return false;
182
183 if (state == kUninitialized) {
184 state = ABSL_INTERNAL_C_SYMBOL(AbslContainerInternalSampleEverything)()
185 ? kForce
186 : kDontForce;
187 global_state.store(state, std::memory_order_relaxed);
188 }
189 return state == kForce;
190 }
191
SampleSlow(int64_t * next_sample)192 HashtablezInfo* SampleSlow(int64_t* next_sample) {
193 if (ABSL_PREDICT_FALSE(ShouldForceSampling())) {
194 *next_sample = 1;
195 return HashtablezSampler::Global().Register();
196 }
197
198 #if !defined(ABSL_INTERNAL_HASHTABLEZ_SAMPLE)
199 *next_sample = std::numeric_limits<int64_t>::max();
200 return nullptr;
201 #else
202 bool first = *next_sample < 0;
203 *next_sample = g_exponential_biased_generator.GetStride(
204 g_hashtablez_sample_parameter.load(std::memory_order_relaxed));
205 // Small values of interval are equivalent to just sampling next time.
206 ABSL_ASSERT(*next_sample >= 1);
207
208 // g_hashtablez_enabled can be dynamically flipped, we need to set a threshold
209 // low enough that we will start sampling in a reasonable time, so we just use
210 // the default sampling rate.
211 if (!g_hashtablez_enabled.load(std::memory_order_relaxed)) return nullptr;
212
213 // We will only be negative on our first count, so we should just retry in
214 // that case.
215 if (first) {
216 if (ABSL_PREDICT_TRUE(--*next_sample > 0)) return nullptr;
217 return SampleSlow(next_sample);
218 }
219
220 return HashtablezSampler::Global().Register();
221 #endif
222 }
223
UnsampleSlow(HashtablezInfo * info)224 void UnsampleSlow(HashtablezInfo* info) {
225 HashtablezSampler::Global().Unregister(info);
226 }
227
RecordInsertSlow(HashtablezInfo * info,size_t hash,size_t distance_from_desired)228 void RecordInsertSlow(HashtablezInfo* info, size_t hash,
229 size_t distance_from_desired) {
230 // SwissTables probe in groups of 16, so scale this to count items probes and
231 // not offset from desired.
232 size_t probe_length = distance_from_desired;
233 #if ABSL_INTERNAL_RAW_HASH_SET_HAVE_SSE2
234 probe_length /= 16;
235 #else
236 probe_length /= 8;
237 #endif
238
239 info->hashes_bitwise_and.fetch_and(hash, std::memory_order_relaxed);
240 info->hashes_bitwise_or.fetch_or(hash, std::memory_order_relaxed);
241 info->hashes_bitwise_xor.fetch_xor(hash, std::memory_order_relaxed);
242 info->max_probe_length.store(
243 std::max(info->max_probe_length.load(std::memory_order_relaxed),
244 probe_length),
245 std::memory_order_relaxed);
246 info->total_probe_length.fetch_add(probe_length, std::memory_order_relaxed);
247 info->size.fetch_add(1, std::memory_order_relaxed);
248 }
249
SetHashtablezEnabled(bool enabled)250 void SetHashtablezEnabled(bool enabled) {
251 g_hashtablez_enabled.store(enabled, std::memory_order_release);
252 }
253
SetHashtablezSampleParameter(int32_t rate)254 void SetHashtablezSampleParameter(int32_t rate) {
255 if (rate > 0) {
256 g_hashtablez_sample_parameter.store(rate, std::memory_order_release);
257 } else {
258 ABSL_RAW_LOG(ERROR, "Invalid hashtablez sample rate: %lld",
259 static_cast<long long>(rate)); // NOLINT(runtime/int)
260 }
261 }
262
SetHashtablezMaxSamples(int32_t max)263 void SetHashtablezMaxSamples(int32_t max) {
264 if (max > 0) {
265 g_hashtablez_max_samples.store(max, std::memory_order_release);
266 } else {
267 ABSL_RAW_LOG(ERROR, "Invalid hashtablez max samples: %lld",
268 static_cast<long long>(max)); // NOLINT(runtime/int)
269 }
270 }
271
272 } // namespace container_internal
273 ABSL_NAMESPACE_END
274 } // namespace absl
275