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/config.h"
25 #include "absl/debugging/stacktrace.h"
26 #include "absl/memory/memory.h"
27 #include "absl/profiling/internal/exponential_biased.h"
28 #include "absl/profiling/internal/sample_recorder.h"
29 #include "absl/synchronization/mutex.h"
30 #include "absl/utility/utility.h"
31
32 namespace absl {
33 ABSL_NAMESPACE_BEGIN
34 namespace container_internal {
35 constexpr int HashtablezInfo::kMaxStackDepth;
36
37 namespace {
38 ABSL_CONST_INIT std::atomic<bool> g_hashtablez_enabled{
39 false
40 };
41 ABSL_CONST_INIT std::atomic<int32_t> g_hashtablez_sample_parameter{1 << 10};
42 std::atomic<HashtablezConfigListener> g_hashtablez_config_listener{nullptr};
43
44 #if defined(ABSL_INTERNAL_HASHTABLEZ_SAMPLE)
45 ABSL_PER_THREAD_TLS_KEYWORD absl::profiling_internal::ExponentialBiased
46 g_exponential_biased_generator;
47 #endif
48
TriggerHashtablezConfigListener()49 void TriggerHashtablezConfigListener() {
50 auto* listener = g_hashtablez_config_listener.load(std::memory_order_acquire);
51 if (listener != nullptr) listener();
52 }
53
54 } // namespace
55
56 #if defined(ABSL_INTERNAL_HASHTABLEZ_SAMPLE)
57 ABSL_PER_THREAD_TLS_KEYWORD SamplingState global_next_sample = {0, 0};
58 #endif // defined(ABSL_INTERNAL_HASHTABLEZ_SAMPLE)
59
GlobalHashtablezSampler()60 HashtablezSampler& GlobalHashtablezSampler() {
61 static auto* sampler = new HashtablezSampler();
62 return *sampler;
63 }
64
65 HashtablezInfo::HashtablezInfo() = default;
66 HashtablezInfo::~HashtablezInfo() = default;
67
PrepareForSampling(int64_t stride,size_t inline_element_size_value)68 void HashtablezInfo::PrepareForSampling(int64_t stride,
69 size_t inline_element_size_value) {
70 capacity.store(0, std::memory_order_relaxed);
71 size.store(0, std::memory_order_relaxed);
72 num_erases.store(0, std::memory_order_relaxed);
73 num_rehashes.store(0, std::memory_order_relaxed);
74 max_probe_length.store(0, std::memory_order_relaxed);
75 total_probe_length.store(0, std::memory_order_relaxed);
76 hashes_bitwise_or.store(0, std::memory_order_relaxed);
77 hashes_bitwise_and.store(~size_t{}, std::memory_order_relaxed);
78 hashes_bitwise_xor.store(0, std::memory_order_relaxed);
79 max_reserve.store(0, std::memory_order_relaxed);
80
81 create_time = absl::Now();
82 weight = stride;
83 // The inliner makes hardcoded skip_count difficult (especially when combined
84 // with LTO). We use the ability to exclude stacks by regex when encoding
85 // instead.
86 depth = absl::GetStackTrace(stack, HashtablezInfo::kMaxStackDepth,
87 /* skip_count= */ 0);
88 inline_element_size = inline_element_size_value;
89 }
90
ShouldForceSampling()91 static bool ShouldForceSampling() {
92 enum ForceState {
93 kDontForce,
94 kForce,
95 kUninitialized
96 };
97 ABSL_CONST_INIT static std::atomic<ForceState> global_state{
98 kUninitialized};
99 ForceState state = global_state.load(std::memory_order_relaxed);
100 if (ABSL_PREDICT_TRUE(state == kDontForce)) return false;
101
102 if (state == kUninitialized) {
103 state = ABSL_INTERNAL_C_SYMBOL(AbslContainerInternalSampleEverything)()
104 ? kForce
105 : kDontForce;
106 global_state.store(state, std::memory_order_relaxed);
107 }
108 return state == kForce;
109 }
110
SampleSlow(SamplingState & next_sample,size_t inline_element_size)111 HashtablezInfo* SampleSlow(SamplingState& next_sample,
112 size_t inline_element_size) {
113 if (ABSL_PREDICT_FALSE(ShouldForceSampling())) {
114 next_sample.next_sample = 1;
115 const int64_t old_stride = exchange(next_sample.sample_stride, 1);
116 HashtablezInfo* result =
117 GlobalHashtablezSampler().Register(old_stride, inline_element_size);
118 return result;
119 }
120
121 #if !defined(ABSL_INTERNAL_HASHTABLEZ_SAMPLE)
122 next_sample = {
123 std::numeric_limits<int64_t>::max(),
124 std::numeric_limits<int64_t>::max(),
125 };
126 return nullptr;
127 #else
128 bool first = next_sample.next_sample < 0;
129
130 const int64_t next_stride = g_exponential_biased_generator.GetStride(
131 g_hashtablez_sample_parameter.load(std::memory_order_relaxed));
132
133 next_sample.next_sample = next_stride;
134 const int64_t old_stride = exchange(next_sample.sample_stride, next_stride);
135 // Small values of interval are equivalent to just sampling next time.
136 ABSL_ASSERT(next_stride >= 1);
137
138 // g_hashtablez_enabled can be dynamically flipped, we need to set a threshold
139 // low enough that we will start sampling in a reasonable time, so we just use
140 // the default sampling rate.
141 if (!g_hashtablez_enabled.load(std::memory_order_relaxed)) return nullptr;
142
143 // We will only be negative on our first count, so we should just retry in
144 // that case.
145 if (first) {
146 if (ABSL_PREDICT_TRUE(--next_sample.next_sample > 0)) return nullptr;
147 return SampleSlow(next_sample, inline_element_size);
148 }
149
150 return GlobalHashtablezSampler().Register(old_stride, inline_element_size);
151 #endif
152 }
153
UnsampleSlow(HashtablezInfo * info)154 void UnsampleSlow(HashtablezInfo* info) {
155 GlobalHashtablezSampler().Unregister(info);
156 }
157
RecordInsertSlow(HashtablezInfo * info,size_t hash,size_t distance_from_desired)158 void RecordInsertSlow(HashtablezInfo* info, size_t hash,
159 size_t distance_from_desired) {
160 // SwissTables probe in groups of 16, so scale this to count items probes and
161 // not offset from desired.
162 size_t probe_length = distance_from_desired;
163 #ifdef ABSL_INTERNAL_HAVE_SSE2
164 probe_length /= 16;
165 #else
166 probe_length /= 8;
167 #endif
168
169 info->hashes_bitwise_and.fetch_and(hash, std::memory_order_relaxed);
170 info->hashes_bitwise_or.fetch_or(hash, std::memory_order_relaxed);
171 info->hashes_bitwise_xor.fetch_xor(hash, std::memory_order_relaxed);
172 info->max_probe_length.store(
173 std::max(info->max_probe_length.load(std::memory_order_relaxed),
174 probe_length),
175 std::memory_order_relaxed);
176 info->total_probe_length.fetch_add(probe_length, std::memory_order_relaxed);
177 info->size.fetch_add(1, std::memory_order_relaxed);
178 }
179
SetHashtablezConfigListener(HashtablezConfigListener l)180 void SetHashtablezConfigListener(HashtablezConfigListener l) {
181 g_hashtablez_config_listener.store(l, std::memory_order_release);
182 }
183
IsHashtablezEnabled()184 bool IsHashtablezEnabled() {
185 return g_hashtablez_enabled.load(std::memory_order_acquire);
186 }
187
SetHashtablezEnabled(bool enabled)188 void SetHashtablezEnabled(bool enabled) {
189 SetHashtablezEnabledInternal(enabled);
190 TriggerHashtablezConfigListener();
191 }
192
SetHashtablezEnabledInternal(bool enabled)193 void SetHashtablezEnabledInternal(bool enabled) {
194 g_hashtablez_enabled.store(enabled, std::memory_order_release);
195 }
196
GetHashtablezSampleParameter()197 int32_t GetHashtablezSampleParameter() {
198 return g_hashtablez_sample_parameter.load(std::memory_order_acquire);
199 }
200
SetHashtablezSampleParameter(int32_t rate)201 void SetHashtablezSampleParameter(int32_t rate) {
202 SetHashtablezSampleParameterInternal(rate);
203 TriggerHashtablezConfigListener();
204 }
205
SetHashtablezSampleParameterInternal(int32_t rate)206 void SetHashtablezSampleParameterInternal(int32_t rate) {
207 if (rate > 0) {
208 g_hashtablez_sample_parameter.store(rate, std::memory_order_release);
209 } else {
210 ABSL_RAW_LOG(ERROR, "Invalid hashtablez sample rate: %lld",
211 static_cast<long long>(rate)); // NOLINT(runtime/int)
212 }
213 }
214
GetHashtablezMaxSamples()215 int32_t GetHashtablezMaxSamples() {
216 return GlobalHashtablezSampler().GetMaxSamples();
217 }
218
SetHashtablezMaxSamples(int32_t max)219 void SetHashtablezMaxSamples(int32_t max) {
220 SetHashtablezMaxSamplesInternal(max);
221 TriggerHashtablezConfigListener();
222 }
223
SetHashtablezMaxSamplesInternal(int32_t max)224 void SetHashtablezMaxSamplesInternal(int32_t max) {
225 if (max > 0) {
226 GlobalHashtablezSampler().SetMaxSamples(max);
227 } else {
228 ABSL_RAW_LOG(ERROR, "Invalid hashtablez max samples: %lld",
229 static_cast<long long>(max)); // NOLINT(runtime/int)
230 }
231 }
232
233 } // namespace container_internal
234 ABSL_NAMESPACE_END
235 } // namespace absl
236