/src/abseil-cpp/absl/container/internal/hashtablez_sampler.h
Line | Count | Source (jump to first uncovered line) |
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 | 2 | explicit HashtablezInfoHandle(std::nullptr_t) {} |
203 | | |
204 | 0 | inline void Unregister() {} |
205 | 16 | inline bool IsSampled() const { return false; } |
206 | 0 | inline void RecordStorageChanged(size_t /*size*/, size_t /*capacity*/) {} |
207 | 0 | inline void RecordRehash(size_t /*total_probe_length*/) {} |
208 | 0 | inline void RecordReservation(size_t /*target_capacity*/) {} |
209 | 0 | inline void RecordClearedReservation() {} |
210 | 16 | inline void RecordInsert(size_t /*hash*/, size_t /*distance_from_desired*/) {} |
211 | 0 | inline void RecordErase() {} |
212 | | |
213 | | friend inline void swap(HashtablezInfoHandle& /*lhs*/, |
214 | 0 | 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 a sampling handle. |
223 | | inline HashtablezInfoHandle Sample( |
224 | | ABSL_ATTRIBUTE_UNUSED size_t inline_element_size, |
225 | | ABSL_ATTRIBUTE_UNUSED size_t key_size, |
226 | | ABSL_ATTRIBUTE_UNUSED size_t value_size, |
227 | 2 | ABSL_ATTRIBUTE_UNUSED uint16_t soo_capacity) { |
228 | | #if defined(ABSL_INTERNAL_HASHTABLEZ_SAMPLE) |
229 | | if (ABSL_PREDICT_TRUE(--global_next_sample.next_sample > 0)) { |
230 | | return HashtablezInfoHandle(nullptr); |
231 | | } |
232 | | return HashtablezInfoHandle(SampleSlow(global_next_sample, |
233 | | inline_element_size, key_size, |
234 | | value_size, soo_capacity)); |
235 | | #else |
236 | 2 | return HashtablezInfoHandle(nullptr); |
237 | 2 | #endif // !ABSL_PER_THREAD_TLS |
238 | 2 | } |
239 | | |
240 | | using HashtablezSampler = |
241 | | ::absl::profiling_internal::SampleRecorder<HashtablezInfo>; |
242 | | |
243 | | // Returns a global Sampler. |
244 | | HashtablezSampler& GlobalHashtablezSampler(); |
245 | | |
246 | | using HashtablezConfigListener = void (*)(); |
247 | | void SetHashtablezConfigListener(HashtablezConfigListener l); |
248 | | |
249 | | // Enables or disables sampling for Swiss tables. |
250 | | bool IsHashtablezEnabled(); |
251 | | void SetHashtablezEnabled(bool enabled); |
252 | | void SetHashtablezEnabledInternal(bool enabled); |
253 | | |
254 | | // Sets the rate at which Swiss tables will be sampled. |
255 | | int32_t GetHashtablezSampleParameter(); |
256 | | void SetHashtablezSampleParameter(int32_t rate); |
257 | | void SetHashtablezSampleParameterInternal(int32_t rate); |
258 | | |
259 | | // Sets a soft max for the number of samples that will be kept. |
260 | | size_t GetHashtablezMaxSamples(); |
261 | | void SetHashtablezMaxSamples(size_t max); |
262 | | void SetHashtablezMaxSamplesInternal(size_t max); |
263 | | |
264 | | // Configuration override. |
265 | | // This allows process-wide sampling without depending on order of |
266 | | // initialization of static storage duration objects. |
267 | | // The definition of this constant is weak, which allows us to inject a |
268 | | // different value for it at link time. |
269 | | extern "C" bool ABSL_INTERNAL_C_SYMBOL(AbslContainerInternalSampleEverything)(); |
270 | | |
271 | | } // namespace container_internal |
272 | | ABSL_NAMESPACE_END |
273 | | } // namespace absl |
274 | | |
275 | | #endif // ABSL_CONTAINER_INTERNAL_HASHTABLEZ_SAMPLER_H_ |