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