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 <algorithm>
18 #include <atomic>
19 #include <cassert>
20 #include <cmath>
21 #include <cstddef>
22 #include <cstdint>
23 #include <functional>
24 #include <limits>
25
26 #include "absl/base/attributes.h"
27 #include "absl/base/config.h"
28 #include "absl/base/internal/per_thread_tls.h"
29 #include "absl/base/internal/raw_logging.h"
30 #include "absl/base/macros.h"
31 #include "absl/base/no_destructor.h"
32 #include "absl/base/optimization.h"
33 #include "absl/debugging/stacktrace.h"
34 #include "absl/memory/memory.h"
35 #include "absl/profiling/internal/exponential_biased.h"
36 #include "absl/profiling/internal/sample_recorder.h"
37 #include "absl/synchronization/mutex.h"
38 #include "absl/time/clock.h"
39 #include "absl/utility/utility.h"
40
41 namespace absl {
42 ABSL_NAMESPACE_BEGIN
43 namespace container_internal {
44
45 #ifdef ABSL_INTERNAL_NEED_REDUNDANT_CONSTEXPR_DECL
46 constexpr int HashtablezInfo::kMaxStackDepth;
47 #endif
48
49 namespace {
50 ABSL_CONST_INIT std::atomic<bool> g_hashtablez_enabled{
51 false
52 };
53 ABSL_CONST_INIT std::atomic<int32_t> g_hashtablez_sample_parameter{1 << 10};
54 std::atomic<HashtablezConfigListener> g_hashtablez_config_listener{nullptr};
55
56 #if defined(ABSL_INTERNAL_HASHTABLEZ_SAMPLE)
57 ABSL_PER_THREAD_TLS_KEYWORD absl::profiling_internal::ExponentialBiased
58 g_exponential_biased_generator;
59 #endif
60
TriggerHashtablezConfigListener()61 void TriggerHashtablezConfigListener() {
62 auto* listener = g_hashtablez_config_listener.load(std::memory_order_acquire);
63 if (listener != nullptr) listener();
64 }
65
66 } // namespace
67
68 #if defined(ABSL_INTERNAL_HASHTABLEZ_SAMPLE)
69 ABSL_PER_THREAD_TLS_KEYWORD SamplingState global_next_sample = {0, 0};
70 #endif // defined(ABSL_INTERNAL_HASHTABLEZ_SAMPLE)
71
GlobalHashtablezSampler()72 HashtablezSampler& GlobalHashtablezSampler() {
73 static absl::NoDestructor<HashtablezSampler> sampler;
74 return *sampler;
75 }
76
77 HashtablezInfo::HashtablezInfo() = default;
78 HashtablezInfo::~HashtablezInfo() = default;
79
PrepareForSampling(int64_t stride,size_t inline_element_size_value,size_t key_size_value,size_t value_size_value,uint16_t soo_capacity_value)80 void HashtablezInfo::PrepareForSampling(int64_t stride,
81 size_t inline_element_size_value,
82 size_t key_size_value,
83 size_t value_size_value,
84 uint16_t soo_capacity_value) {
85 capacity.store(0, std::memory_order_relaxed);
86 size.store(0, std::memory_order_relaxed);
87 num_erases.store(0, std::memory_order_relaxed);
88 num_rehashes.store(0, std::memory_order_relaxed);
89 max_probe_length.store(0, std::memory_order_relaxed);
90 total_probe_length.store(0, std::memory_order_relaxed);
91 hashes_bitwise_or.store(0, std::memory_order_relaxed);
92 hashes_bitwise_and.store(~size_t{}, std::memory_order_relaxed);
93 hashes_bitwise_xor.store(0, std::memory_order_relaxed);
94 max_reserve.store(0, std::memory_order_relaxed);
95
96 create_time = absl::Now();
97 weight = stride;
98 // The inliner makes hardcoded skip_count difficult (especially when combined
99 // with LTO). We use the ability to exclude stacks by regex when encoding
100 // instead.
101 depth = absl::GetStackTrace(stack, HashtablezInfo::kMaxStackDepth,
102 /* skip_count= */ 0);
103 inline_element_size = inline_element_size_value;
104 key_size = key_size_value;
105 value_size = value_size_value;
106 soo_capacity = soo_capacity_value;
107 }
108
ShouldForceSampling()109 static bool ShouldForceSampling() {
110 enum ForceState {
111 kDontForce,
112 kForce,
113 kUninitialized
114 };
115 ABSL_CONST_INIT static std::atomic<ForceState> global_state{
116 kUninitialized};
117 ForceState state = global_state.load(std::memory_order_relaxed);
118 if (ABSL_PREDICT_TRUE(state == kDontForce)) return false;
119
120 if (state == kUninitialized) {
121 state = ABSL_INTERNAL_C_SYMBOL(AbslContainerInternalSampleEverything)()
122 ? kForce
123 : kDontForce;
124 global_state.store(state, std::memory_order_relaxed);
125 }
126 return state == kForce;
127 }
128
SampleSlow(SamplingState & next_sample,size_t inline_element_size,size_t key_size,size_t value_size,uint16_t soo_capacity)129 HashtablezInfo* SampleSlow(SamplingState& next_sample,
130 size_t inline_element_size, size_t key_size,
131 size_t value_size, uint16_t soo_capacity) {
132 if (ABSL_PREDICT_FALSE(ShouldForceSampling())) {
133 next_sample.next_sample = 1;
134 const int64_t old_stride = exchange(next_sample.sample_stride, 1);
135 HashtablezInfo* result = GlobalHashtablezSampler().Register(
136 old_stride, inline_element_size, key_size, value_size, soo_capacity);
137 return result;
138 }
139
140 #if !defined(ABSL_INTERNAL_HASHTABLEZ_SAMPLE)
141 next_sample = {
142 std::numeric_limits<int64_t>::max(),
143 std::numeric_limits<int64_t>::max(),
144 };
145 return nullptr;
146 #else
147 bool first = next_sample.next_sample < 0;
148
149 const int64_t next_stride = g_exponential_biased_generator.GetStride(
150 g_hashtablez_sample_parameter.load(std::memory_order_relaxed));
151
152 next_sample.next_sample = next_stride;
153 const int64_t old_stride = exchange(next_sample.sample_stride, next_stride);
154 // Small values of interval are equivalent to just sampling next time.
155 ABSL_ASSERT(next_stride >= 1);
156
157 // g_hashtablez_enabled can be dynamically flipped, we need to set a threshold
158 // low enough that we will start sampling in a reasonable time, so we just use
159 // the default sampling rate.
160 if (!g_hashtablez_enabled.load(std::memory_order_relaxed)) return nullptr;
161
162 // We will only be negative on our first count, so we should just retry in
163 // that case.
164 if (first) {
165 if (ABSL_PREDICT_TRUE(--next_sample.next_sample > 0)) return nullptr;
166 return SampleSlow(next_sample, inline_element_size, key_size, value_size,
167 soo_capacity);
168 }
169
170 return GlobalHashtablezSampler().Register(old_stride, inline_element_size,
171 key_size, value_size, soo_capacity);
172 #endif
173 }
174
UnsampleSlow(HashtablezInfo * info)175 void UnsampleSlow(HashtablezInfo* info) {
176 GlobalHashtablezSampler().Unregister(info);
177 }
178
RecordRehashSlow(HashtablezInfo * info,size_t total_probe_length)179 void RecordRehashSlow(HashtablezInfo* info, size_t total_probe_length) {
180 #ifdef ABSL_INTERNAL_HAVE_SSE2
181 total_probe_length /= 16;
182 #else
183 total_probe_length /= 8;
184 #endif
185 info->total_probe_length.store(total_probe_length, std::memory_order_relaxed);
186 info->num_erases.store(0, std::memory_order_relaxed);
187 // There is only one concurrent writer, so `load` then `store` is sufficient
188 // instead of using `fetch_add`.
189 info->num_rehashes.store(
190 1 + info->num_rehashes.load(std::memory_order_relaxed),
191 std::memory_order_relaxed);
192 }
193
RecordReservationSlow(HashtablezInfo * info,size_t target_capacity)194 void RecordReservationSlow(HashtablezInfo* info, size_t target_capacity) {
195 info->max_reserve.store(
196 (std::max)(info->max_reserve.load(std::memory_order_relaxed),
197 target_capacity),
198 std::memory_order_relaxed);
199 }
200
RecordClearedReservationSlow(HashtablezInfo * info)201 void RecordClearedReservationSlow(HashtablezInfo* info) {
202 info->max_reserve.store(0, std::memory_order_relaxed);
203 }
204
RecordStorageChangedSlow(HashtablezInfo * info,size_t size,size_t capacity)205 void RecordStorageChangedSlow(HashtablezInfo* info, size_t size,
206 size_t capacity) {
207 info->size.store(size, std::memory_order_relaxed);
208 info->capacity.store(capacity, std::memory_order_relaxed);
209 if (size == 0) {
210 // This is a clear, reset the total/num_erases too.
211 info->total_probe_length.store(0, std::memory_order_relaxed);
212 info->num_erases.store(0, std::memory_order_relaxed);
213 }
214 }
215
RecordInsertSlow(HashtablezInfo * info,size_t hash,size_t distance_from_desired)216 void RecordInsertSlow(HashtablezInfo* info, size_t hash,
217 size_t distance_from_desired) {
218 // SwissTables probe in groups of 16, so scale this to count items probes and
219 // not offset from desired.
220 size_t probe_length = distance_from_desired;
221 #ifdef ABSL_INTERNAL_HAVE_SSE2
222 probe_length /= 16;
223 #else
224 probe_length /= 8;
225 #endif
226
227 info->hashes_bitwise_and.fetch_and(hash, std::memory_order_relaxed);
228 info->hashes_bitwise_or.fetch_or(hash, std::memory_order_relaxed);
229 info->hashes_bitwise_xor.fetch_xor(hash, std::memory_order_relaxed);
230 info->max_probe_length.store(
231 std::max(info->max_probe_length.load(std::memory_order_relaxed),
232 probe_length),
233 std::memory_order_relaxed);
234 info->total_probe_length.fetch_add(probe_length, std::memory_order_relaxed);
235 info->size.fetch_add(1, std::memory_order_relaxed);
236 }
237
RecordEraseSlow(HashtablezInfo * info)238 void RecordEraseSlow(HashtablezInfo* info) {
239 info->size.fetch_sub(1, std::memory_order_relaxed);
240 // There is only one concurrent writer, so `load` then `store` is sufficient
241 // instead of using `fetch_add`.
242 info->num_erases.store(1 + info->num_erases.load(std::memory_order_relaxed),
243 std::memory_order_relaxed);
244 }
245
SetHashtablezConfigListener(HashtablezConfigListener l)246 void SetHashtablezConfigListener(HashtablezConfigListener l) {
247 g_hashtablez_config_listener.store(l, std::memory_order_release);
248 }
249
IsHashtablezEnabled()250 bool IsHashtablezEnabled() {
251 return g_hashtablez_enabled.load(std::memory_order_acquire);
252 }
253
SetHashtablezEnabled(bool enabled)254 void SetHashtablezEnabled(bool enabled) {
255 SetHashtablezEnabledInternal(enabled);
256 TriggerHashtablezConfigListener();
257 }
258
SetHashtablezEnabledInternal(bool enabled)259 void SetHashtablezEnabledInternal(bool enabled) {
260 g_hashtablez_enabled.store(enabled, std::memory_order_release);
261 }
262
GetHashtablezSampleParameter()263 int32_t GetHashtablezSampleParameter() {
264 return g_hashtablez_sample_parameter.load(std::memory_order_acquire);
265 }
266
SetHashtablezSampleParameter(int32_t rate)267 void SetHashtablezSampleParameter(int32_t rate) {
268 SetHashtablezSampleParameterInternal(rate);
269 TriggerHashtablezConfigListener();
270 }
271
SetHashtablezSampleParameterInternal(int32_t rate)272 void SetHashtablezSampleParameterInternal(int32_t rate) {
273 if (rate > 0) {
274 g_hashtablez_sample_parameter.store(rate, std::memory_order_release);
275 } else {
276 ABSL_RAW_LOG(ERROR, "Invalid hashtablez sample rate: %lld",
277 static_cast<long long>(rate)); // NOLINT(runtime/int)
278 }
279 }
280
GetHashtablezMaxSamples()281 size_t GetHashtablezMaxSamples() {
282 return GlobalHashtablezSampler().GetMaxSamples();
283 }
284
SetHashtablezMaxSamples(size_t max)285 void SetHashtablezMaxSamples(size_t max) {
286 SetHashtablezMaxSamplesInternal(max);
287 TriggerHashtablezConfigListener();
288 }
289
SetHashtablezMaxSamplesInternal(size_t max)290 void SetHashtablezMaxSamplesInternal(size_t max) {
291 if (max > 0) {
292 GlobalHashtablezSampler().SetMaxSamples(max);
293 } else {
294 ABSL_RAW_LOG(ERROR, "Invalid hashtablez max samples: 0");
295 }
296 }
297
298 } // namespace container_internal
299 ABSL_NAMESPACE_END
300 } // namespace absl
301