hashtablez_sampler.h (11197B)
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 // ----------------------------------------------------------------------------- 16 // File: hashtablez_sampler.h 17 // ----------------------------------------------------------------------------- 18 // 19 // This header file defines the API for a low level library to sample hashtables 20 // and collect runtime statistics about them. 21 // 22 // `HashtablezSampler` controls the lifecycle of `HashtablezInfo` objects which 23 // store information about a single sample. 24 // 25 // `Record*` methods store information into samples. 26 // `Sample()` and `Unsample()` make use of a single global sampler with 27 // properties controlled by the flags hashtablez_enabled, 28 // hashtablez_sample_rate, and hashtablez_max_samples. 29 // 30 // WARNING 31 // 32 // Using this sampling API may cause sampled Swiss tables to use the global 33 // allocator (operator `new`) in addition to any custom allocator. If you 34 // are using a table in an unusual circumstance where allocation or calling a 35 // linux syscall is unacceptable, this could interfere. 36 // 37 // This utility is internal-only. Use at your own risk. 38 39 #ifndef ABSL_CONTAINER_INTERNAL_HASHTABLEZ_SAMPLER_H_ 40 #define ABSL_CONTAINER_INTERNAL_HASHTABLEZ_SAMPLER_H_ 41 42 #include <atomic> 43 #include <cstddef> 44 #include <cstdint> 45 #include <functional> 46 #include <memory> 47 #include <vector> 48 49 #include "absl/base/attributes.h" 50 #include "absl/base/config.h" 51 #include "absl/base/internal/per_thread_tls.h" 52 #include "absl/base/optimization.h" 53 #include "absl/base/thread_annotations.h" 54 #include "absl/profiling/internal/sample_recorder.h" 55 #include "absl/synchronization/mutex.h" 56 #include "absl/time/time.h" 57 #include "absl/utility/utility.h" 58 59 namespace absl { 60 ABSL_NAMESPACE_BEGIN 61 namespace container_internal { 62 63 // Stores information about a sampled hashtable. All mutations to this *must* 64 // be made through `Record*` functions below. All reads from this *must* only 65 // occur in the callback to `HashtablezSampler::Iterate`. 66 struct HashtablezInfo : public profiling_internal::Sample<HashtablezInfo> { 67 // Constructs the object but does not fill in any fields. 68 HashtablezInfo(); 69 ~HashtablezInfo(); 70 HashtablezInfo(const HashtablezInfo&) = delete; 71 HashtablezInfo& operator=(const HashtablezInfo&) = delete; 72 73 // Puts the object into a clean state, fills in the logically `const` members, 74 // blocking for any readers that are currently sampling the object. 75 void PrepareForSampling(int64_t stride, size_t inline_element_size_value, 76 size_t key_size, size_t value_size, 77 uint16_t soo_capacity_value) 78 ABSL_EXCLUSIVE_LOCKS_REQUIRED(init_mu); 79 80 // These fields are mutated by the various Record* APIs and need to be 81 // thread-safe. 82 std::atomic<size_t> capacity; 83 std::atomic<size_t> size; 84 std::atomic<size_t> num_erases; 85 std::atomic<size_t> num_rehashes; 86 std::atomic<size_t> max_probe_length; 87 std::atomic<size_t> total_probe_length; 88 std::atomic<size_t> hashes_bitwise_or; 89 std::atomic<size_t> hashes_bitwise_and; 90 std::atomic<size_t> hashes_bitwise_xor; 91 std::atomic<size_t> max_reserve; 92 93 // All of the fields below are set by `PrepareForSampling`, they must not be 94 // mutated in `Record*` functions. They are logically `const` in that sense. 95 // These are guarded by init_mu, but that is not externalized to clients, 96 // which can read them only during `SampleRecorder::Iterate` which will hold 97 // the lock. 98 static constexpr int kMaxStackDepth = 64; 99 absl::Time create_time; 100 int32_t depth; 101 // The SOO capacity for this table in elements (not bytes). Note that sampled 102 // tables are never SOO because we need to store the infoz handle on the heap. 103 // Tables that would be SOO if not sampled should have: soo_capacity > 0 && 104 // size <= soo_capacity && max_reserve <= soo_capacity. 105 uint16_t soo_capacity; 106 void* stack[kMaxStackDepth]; 107 size_t inline_element_size; // How big is the slot in bytes? 108 size_t key_size; // sizeof(key_type) 109 size_t value_size; // sizeof(value_type) 110 }; 111 112 void RecordRehashSlow(HashtablezInfo* info, size_t total_probe_length); 113 114 void RecordReservationSlow(HashtablezInfo* info, size_t target_capacity); 115 116 void RecordClearedReservationSlow(HashtablezInfo* info); 117 118 void RecordStorageChangedSlow(HashtablezInfo* info, size_t size, 119 size_t capacity); 120 121 void RecordInsertSlow(HashtablezInfo* info, size_t hash, 122 size_t distance_from_desired); 123 124 void RecordEraseSlow(HashtablezInfo* info); 125 126 struct SamplingState { 127 int64_t next_sample; 128 // When we make a sampling decision, we record that distance so we can weight 129 // each sample. 130 int64_t sample_stride; 131 }; 132 133 HashtablezInfo* SampleSlow(SamplingState& next_sample, 134 size_t inline_element_size, size_t key_size, 135 size_t value_size, uint16_t soo_capacity); 136 void UnsampleSlow(HashtablezInfo* info); 137 138 #if defined(ABSL_INTERNAL_HASHTABLEZ_SAMPLE) 139 #error ABSL_INTERNAL_HASHTABLEZ_SAMPLE cannot be directly set 140 #endif // defined(ABSL_INTERNAL_HASHTABLEZ_SAMPLE) 141 142 #if defined(ABSL_INTERNAL_HASHTABLEZ_SAMPLE) 143 class HashtablezInfoHandle { 144 public: 145 explicit HashtablezInfoHandle() : info_(nullptr) {} 146 explicit HashtablezInfoHandle(HashtablezInfo* info) : info_(info) {} 147 148 // We do not have a destructor. Caller is responsible for calling Unregister 149 // before destroying the handle. 150 void Unregister() { 151 if (ABSL_PREDICT_TRUE(info_ == nullptr)) return; 152 UnsampleSlow(info_); 153 } 154 155 inline bool IsSampled() const { return ABSL_PREDICT_FALSE(info_ != nullptr); } 156 157 inline void RecordStorageChanged(size_t size, size_t capacity) { 158 if (ABSL_PREDICT_TRUE(info_ == nullptr)) return; 159 RecordStorageChangedSlow(info_, size, capacity); 160 } 161 162 inline void RecordRehash(size_t total_probe_length) { 163 if (ABSL_PREDICT_TRUE(info_ == nullptr)) return; 164 RecordRehashSlow(info_, total_probe_length); 165 } 166 167 inline void RecordReservation(size_t target_capacity) { 168 if (ABSL_PREDICT_TRUE(info_ == nullptr)) return; 169 RecordReservationSlow(info_, target_capacity); 170 } 171 172 inline void RecordClearedReservation() { 173 if (ABSL_PREDICT_TRUE(info_ == nullptr)) return; 174 RecordClearedReservationSlow(info_); 175 } 176 177 inline void RecordInsert(size_t hash, size_t distance_from_desired) { 178 if (ABSL_PREDICT_TRUE(info_ == nullptr)) return; 179 RecordInsertSlow(info_, hash, distance_from_desired); 180 } 181 182 inline void RecordErase() { 183 if (ABSL_PREDICT_TRUE(info_ == nullptr)) return; 184 RecordEraseSlow(info_); 185 } 186 187 friend inline void swap(HashtablezInfoHandle& lhs, 188 HashtablezInfoHandle& rhs) { 189 std::swap(lhs.info_, rhs.info_); 190 } 191 192 private: 193 friend class HashtablezInfoHandlePeer; 194 HashtablezInfo* info_; 195 }; 196 #else 197 // Ensure that when Hashtablez is turned off at compile time, HashtablezInfo can 198 // be removed by the linker, in order to reduce the binary size. 199 class HashtablezInfoHandle { 200 public: 201 explicit HashtablezInfoHandle() = default; 202 explicit HashtablezInfoHandle(std::nullptr_t) {} 203 204 inline void Unregister() {} 205 inline bool IsSampled() const { return false; } 206 inline void RecordStorageChanged(size_t /*size*/, size_t /*capacity*/) {} 207 inline void RecordRehash(size_t /*total_probe_length*/) {} 208 inline void RecordReservation(size_t /*target_capacity*/) {} 209 inline void RecordClearedReservation() {} 210 inline void RecordInsert(size_t /*hash*/, size_t /*distance_from_desired*/) {} 211 inline void RecordErase() {} 212 213 friend inline void swap(HashtablezInfoHandle& /*lhs*/, 214 HashtablezInfoHandle& /*rhs*/) {} 215 }; 216 #endif // defined(ABSL_INTERNAL_HASHTABLEZ_SAMPLE) 217 218 #if defined(ABSL_INTERNAL_HASHTABLEZ_SAMPLE) 219 extern ABSL_PER_THREAD_TLS_KEYWORD SamplingState global_next_sample; 220 #endif // defined(ABSL_INTERNAL_HASHTABLEZ_SAMPLE) 221 222 // Returns true if the next table should be sampled. 223 // This function updates the global state. 224 // If the function returns true, actual sampling should be done by calling 225 // ForcedTrySample(). 226 inline bool ShouldSampleNextTable() { 227 #if defined(ABSL_INTERNAL_HASHTABLEZ_SAMPLE) 228 if (ABSL_PREDICT_TRUE(--global_next_sample.next_sample > 0)) { 229 return false; 230 } 231 return true; 232 #else 233 return false; 234 #endif // ABSL_INTERNAL_HASHTABLEZ_SAMPLE 235 } 236 237 // Returns a sampling handle. 238 // Must be called only if HashSetShouldBeSampled() returned true. 239 // Returned handle still can be unsampled if sampling is not possible. 240 HashtablezInfoHandle ForcedTrySample(size_t inline_element_size, 241 size_t key_size, size_t value_size, 242 uint16_t soo_capacity); 243 244 // In case sampling needs to be disabled and re-enabled in tests, this function 245 // can be used to reset the sampling state for the current thread. 246 // It is useful to avoid sampling attempts and sampling delays in tests. 247 void TestOnlyRefreshSamplingStateForCurrentThread(); 248 249 // Returns a sampling handle. 250 inline HashtablezInfoHandle Sample(size_t inline_element_size, size_t key_size, 251 size_t value_size, uint16_t soo_capacity) { 252 if (ABSL_PREDICT_TRUE(!ShouldSampleNextTable())) { 253 return HashtablezInfoHandle(nullptr); 254 } 255 return ForcedTrySample(inline_element_size, key_size, value_size, 256 soo_capacity); 257 } 258 259 using HashtablezSampler = 260 ::absl::profiling_internal::SampleRecorder<HashtablezInfo>; 261 262 // Returns a global Sampler. 263 HashtablezSampler& GlobalHashtablezSampler(); 264 265 using HashtablezConfigListener = void (*)(); 266 void SetHashtablezConfigListener(HashtablezConfigListener l); 267 268 // Enables or disables sampling for Swiss tables. 269 bool IsHashtablezEnabled(); 270 void SetHashtablezEnabled(bool enabled); 271 void SetHashtablezEnabledInternal(bool enabled); 272 273 // Sets the rate at which Swiss tables will be sampled. 274 int32_t GetHashtablezSampleParameter(); 275 void SetHashtablezSampleParameter(int32_t rate); 276 void SetHashtablezSampleParameterInternal(int32_t rate); 277 278 // Sets a soft max for the number of samples that will be kept. 279 size_t GetHashtablezMaxSamples(); 280 void SetHashtablezMaxSamples(size_t max); 281 void SetHashtablezMaxSamplesInternal(size_t max); 282 283 // Configuration override. 284 // This allows process-wide sampling without depending on order of 285 // initialization of static storage duration objects. 286 // The definition of this constant is weak, which allows us to inject a 287 // different value for it at link time. 288 extern "C" bool ABSL_INTERNAL_C_SYMBOL(AbslContainerInternalSampleEverything)(); 289 290 } // namespace container_internal 291 ABSL_NAMESPACE_END 292 } // namespace absl 293 294 #endif // ABSL_CONTAINER_INTERNAL_HASHTABLEZ_SAMPLER_H_