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