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/profiling/internal/exponential_biased.h"
28 #include "absl/profiling/internal/sample_recorder.h"
29 #include "absl/synchronization/mutex.h"
30
31 namespace absl {
32 ABSL_NAMESPACE_BEGIN
33 namespace container_internal {
34 constexpr int HashtablezInfo::kMaxStackDepth;
35
36 namespace {
37 ABSL_CONST_INIT std::atomic<bool> g_hashtablez_enabled{
38 false
39 };
40 ABSL_CONST_INIT std::atomic<int32_t> g_hashtablez_sample_parameter{1 << 10};
41
42 #if defined(ABSL_INTERNAL_HASHTABLEZ_SAMPLE)
43 ABSL_PER_THREAD_TLS_KEYWORD absl::profiling_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
GlobalHashtablezSampler()53 HashtablezSampler& GlobalHashtablezSampler() {
54 static auto* sampler = new HashtablezSampler();
55 return *sampler;
56 }
57
58 // TODO(bradleybear): The comments at this constructors declaration say that the
59 // fields are not initialized, but this definition does initialize the fields.
60 // Something needs to be cleaned up.
HashtablezInfo()61 HashtablezInfo::HashtablezInfo() { PrepareForSampling(); }
62 HashtablezInfo::~HashtablezInfo() = default;
63
PrepareForSampling()64 void HashtablezInfo::PrepareForSampling() {
65 capacity.store(0, std::memory_order_relaxed);
66 size.store(0, std::memory_order_relaxed);
67 num_erases.store(0, std::memory_order_relaxed);
68 num_rehashes.store(0, std::memory_order_relaxed);
69 max_probe_length.store(0, std::memory_order_relaxed);
70 total_probe_length.store(0, std::memory_order_relaxed);
71 hashes_bitwise_or.store(0, std::memory_order_relaxed);
72 hashes_bitwise_and.store(~size_t{}, std::memory_order_relaxed);
73 hashes_bitwise_xor.store(0, std::memory_order_relaxed);
74 max_reserve.store(0, 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 }
83
ShouldForceSampling()84 static bool ShouldForceSampling() {
85 enum ForceState {
86 kDontForce,
87 kForce,
88 kUninitialized
89 };
90 ABSL_CONST_INIT static std::atomic<ForceState> global_state{
91 kUninitialized};
92 ForceState state = global_state.load(std::memory_order_relaxed);
93 if (ABSL_PREDICT_TRUE(state == kDontForce)) return false;
94
95 if (state == kUninitialized) {
96 state = ABSL_INTERNAL_C_SYMBOL(AbslContainerInternalSampleEverything)()
97 ? kForce
98 : kDontForce;
99 global_state.store(state, std::memory_order_relaxed);
100 }
101 return state == kForce;
102 }
103
SampleSlow(int64_t * next_sample,size_t inline_element_size)104 HashtablezInfo* SampleSlow(int64_t* next_sample, size_t inline_element_size) {
105 if (ABSL_PREDICT_FALSE(ShouldForceSampling())) {
106 *next_sample = 1;
107 HashtablezInfo* result = GlobalHashtablezSampler().Register();
108 result->inline_element_size = inline_element_size;
109 return result;
110 }
111
112 #if !defined(ABSL_INTERNAL_HASHTABLEZ_SAMPLE)
113 *next_sample = std::numeric_limits<int64_t>::max();
114 return nullptr;
115 #else
116 bool first = *next_sample < 0;
117 *next_sample = g_exponential_biased_generator.GetStride(
118 g_hashtablez_sample_parameter.load(std::memory_order_relaxed));
119 // Small values of interval are equivalent to just sampling next time.
120 ABSL_ASSERT(*next_sample >= 1);
121
122 // g_hashtablez_enabled can be dynamically flipped, we need to set a threshold
123 // low enough that we will start sampling in a reasonable time, so we just use
124 // the default sampling rate.
125 if (!g_hashtablez_enabled.load(std::memory_order_relaxed)) return nullptr;
126
127 // We will only be negative on our first count, so we should just retry in
128 // that case.
129 if (first) {
130 if (ABSL_PREDICT_TRUE(--*next_sample > 0)) return nullptr;
131 return SampleSlow(next_sample, inline_element_size);
132 }
133
134 HashtablezInfo* result = GlobalHashtablezSampler().Register();
135 result->inline_element_size = inline_element_size;
136 return result;
137 #endif
138 }
139
UnsampleSlow(HashtablezInfo * info)140 void UnsampleSlow(HashtablezInfo* info) {
141 GlobalHashtablezSampler().Unregister(info);
142 }
143
RecordInsertSlow(HashtablezInfo * info,size_t hash,size_t distance_from_desired)144 void RecordInsertSlow(HashtablezInfo* info, size_t hash,
145 size_t distance_from_desired) {
146 // SwissTables probe in groups of 16, so scale this to count items probes and
147 // not offset from desired.
148 size_t probe_length = distance_from_desired;
149 #if ABSL_INTERNAL_RAW_HASH_SET_HAVE_SSE2
150 probe_length /= 16;
151 #else
152 probe_length /= 8;
153 #endif
154
155 info->hashes_bitwise_and.fetch_and(hash, std::memory_order_relaxed);
156 info->hashes_bitwise_or.fetch_or(hash, std::memory_order_relaxed);
157 info->hashes_bitwise_xor.fetch_xor(hash, std::memory_order_relaxed);
158 info->max_probe_length.store(
159 std::max(info->max_probe_length.load(std::memory_order_relaxed),
160 probe_length),
161 std::memory_order_relaxed);
162 info->total_probe_length.fetch_add(probe_length, std::memory_order_relaxed);
163 info->size.fetch_add(1, std::memory_order_relaxed);
164 }
165
SetHashtablezEnabled(bool enabled)166 void SetHashtablezEnabled(bool enabled) {
167 g_hashtablez_enabled.store(enabled, std::memory_order_release);
168 }
169
SetHashtablezSampleParameter(int32_t rate)170 void SetHashtablezSampleParameter(int32_t rate) {
171 if (rate > 0) {
172 g_hashtablez_sample_parameter.store(rate, std::memory_order_release);
173 } else {
174 ABSL_RAW_LOG(ERROR, "Invalid hashtablez sample rate: %lld",
175 static_cast<long long>(rate)); // NOLINT(runtime/int)
176 }
177 }
178
SetHashtablezMaxSamples(int32_t max)179 void SetHashtablezMaxSamples(int32_t max) {
180 if (max > 0) {
181 GlobalHashtablezSampler().SetMaxSamples(max);
182 } else {
183 ABSL_RAW_LOG(ERROR, "Invalid hashtablez max samples: %lld",
184 static_cast<long long>(max)); // NOLINT(runtime/int)
185 }
186 }
187
188 } // namespace container_internal
189 ABSL_NAMESPACE_END
190 } // namespace absl
191