hashtablez_sampler.h
Go to the documentation of this file.
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 <functional>
44 #include <memory>
45 #include <vector>
46 
48 #include "absl/base/optimization.h"
51 #include "absl/utility/utility.h"
52 
53 namespace absl {
54 namespace container_internal {
55 
56 // Stores information about a sampled hashtable. All mutations to this *must*
57 // be made through `Record*` functions below. All reads from this *must* only
58 // occur in the callback to `HashtablezSampler::Iterate`.
60  // Constructs the object but does not fill in any fields.
63  HashtablezInfo(const HashtablezInfo&) = delete;
64  HashtablezInfo& operator=(const HashtablezInfo&) = delete;
65 
66  // Puts the object into a clean state, fills in the logically `const` members,
67  // blocking for any readers that are currently sampling the object.
69 
70  // These fields are mutated by the various Record* APIs and need to be
71  // thread-safe.
72  std::atomic<size_t> capacity;
73  std::atomic<size_t> size;
74  std::atomic<size_t> num_erases;
75  std::atomic<size_t> max_probe_length;
76  std::atomic<size_t> total_probe_length;
77  std::atomic<size_t> hashes_bitwise_or;
78  std::atomic<size_t> hashes_bitwise_and;
79 
80  // `HashtablezSampler` maintains intrusive linked lists for all samples. See
81  // comments on `HashtablezSampler::all_` for details on these. `init_mu`
82  // guards the ability to restore the sample to a pristine state. This
83  // prevents races with sampling and resurrecting an object.
86  HashtablezInfo* dead GUARDED_BY(init_mu);
87 
88  // All of the fields below are set by `PrepareForSampling`, they must not be
89  // mutated in `Record*` functions. They are logically `const` in that sense.
90  // These are guarded by init_mu, but that is not externalized to clients, who
91  // can only read them during `HashtablezSampler::Iterate` which will hold the
92  // lock.
93  static constexpr int kMaxStackDepth = 64;
95  int32_t depth;
97 };
98 
100 #if SWISSTABLE_HAVE_SSE2
101  total_probe_length /= 16;
102 #else
103  total_probe_length /= 8;
104 #endif
105  info->total_probe_length.store(total_probe_length, std::memory_order_relaxed);
106  info->num_erases.store(0, std::memory_order_relaxed);
107 }
108 
109 inline void RecordStorageChangedSlow(HashtablezInfo* info, size_t size,
110  size_t capacity) {
111  info->size.store(size, std::memory_order_relaxed);
112  info->capacity.store(capacity, std::memory_order_relaxed);
113  if (size == 0) {
114  // This is a clear, reset the total/num_erases too.
115  RecordRehashSlow(info, 0);
116  }
117 }
118 
119 void RecordInsertSlow(HashtablezInfo* info, size_t hash,
120  size_t distance_from_desired);
121 
122 inline void RecordEraseSlow(HashtablezInfo* info) {
123  info->size.fetch_sub(1, std::memory_order_relaxed);
124  info->num_erases.fetch_add(1, std::memory_order_relaxed);
125 }
126 
127 HashtablezInfo* SampleSlow(int64_t* next_sample);
128 void UnsampleSlow(HashtablezInfo* info);
129 
131  public:
132  explicit HashtablezInfoHandle() : info_(nullptr) {}
133  explicit HashtablezInfoHandle(HashtablezInfo* info) : info_(info) {}
135  if (ABSL_PREDICT_TRUE(info_ == nullptr)) return;
136  UnsampleSlow(info_);
137  }
138 
141 
143  : info_(absl::exchange(o.info_, nullptr)) {}
145  if (ABSL_PREDICT_FALSE(info_ != nullptr)) {
146  UnsampleSlow(info_);
147  }
148  info_ = absl::exchange(o.info_, nullptr);
149  return *this;
150  }
151 
152  inline void RecordStorageChanged(size_t size, size_t capacity) {
153  if (ABSL_PREDICT_TRUE(info_ == nullptr)) return;
154  RecordStorageChangedSlow(info_, size, capacity);
155  }
156 
157  inline void RecordRehash(size_t total_probe_length) {
158  if (ABSL_PREDICT_TRUE(info_ == nullptr)) return;
159  RecordRehashSlow(info_, total_probe_length);
160  }
161 
162  inline void RecordInsert(size_t hash, size_t distance_from_desired) {
163  if (ABSL_PREDICT_TRUE(info_ == nullptr)) return;
164  RecordInsertSlow(info_, hash, distance_from_desired);
165  }
166 
167  inline void RecordErase() {
168  if (ABSL_PREDICT_TRUE(info_ == nullptr)) return;
169  RecordEraseSlow(info_);
170  }
171 
172  friend inline void swap(HashtablezInfoHandle& lhs,
173  HashtablezInfoHandle& rhs) {
174  std::swap(lhs.info_, rhs.info_);
175  }
176 
177  private:
180 };
181 
182 #if ABSL_PER_THREAD_TLS == 1
183 extern ABSL_PER_THREAD_TLS_KEYWORD int64_t global_next_sample;
184 #endif // ABSL_PER_THREAD_TLS
185 
186 // Returns an RAII sampling handle that manages registration and unregistation
187 // with the global sampler.
189 #if ABSL_PER_THREAD_TLS == 0
190  static auto* mu = new absl::Mutex;
191  static int64_t global_next_sample = 0;
192  absl::MutexLock l(mu);
193 #endif // !ABSL_HAVE_THREAD_LOCAL
194 
195  if (ABSL_PREDICT_TRUE(--global_next_sample > 0)) {
196  return HashtablezInfoHandle(nullptr);
197  }
198  return HashtablezInfoHandle(SampleSlow(&global_next_sample));
199 }
200 
201 // Holds samples and their associated stack traces with a soft limit of
202 // `SetHashtablezMaxSamples()`.
203 //
204 // Thread safe.
206  public:
207  // Returns a global Sampler.
208  static HashtablezSampler& Global();
209 
212 
213  // Registers for sampling. Returns an opaque registration info.
214  HashtablezInfo* Register();
215 
216  // Unregisters the sample.
217  void Unregister(HashtablezInfo* sample);
218 
219  // The dispose callback will be called on all samples the moment they are
220  // being unregistered. Only affects samples that are unregistered after the
221  // callback has been set.
222  // Returns the previous callback.
223  using DisposeCallback = void (*)(const HashtablezInfo&);
224  DisposeCallback SetDisposeCallback(DisposeCallback f);
225 
226  // Iterates over all the registered `StackInfo`s. Returning the number of
227  // samples that have been dropped.
228  int64_t Iterate(const std::function<void(const HashtablezInfo& stack)>& f);
229 
230  private:
231  void PushNew(HashtablezInfo* sample);
232  void PushDead(HashtablezInfo* sample);
233  HashtablezInfo* PopDead();
234 
235  std::atomic<size_t> dropped_samples_;
236  std::atomic<size_t> size_estimate_;
237 
238  // Intrusive lock free linked lists for tracking samples.
239  //
240  // `all_` records all samples (they are never removed from this list) and is
241  // terminated with a `nullptr`.
242  //
243  // `graveyard_.dead` is a circular linked list. When it is empty,
244  // `graveyard_.dead == &graveyard`. The list is circular so that
245  // every item on it (even the last) has a non-null dead pointer. This allows
246  // `Iterate` to determine if a given sample is live or dead using only
247  // information on the sample itself.
248  //
249  // For example, nodes [A, B, C, D, E] with [A, C, E] alive and [B, D] dead
250  // looks like this (G is the Graveyard):
251  //
252  // +---+ +---+ +---+ +---+ +---+
253  // all -->| A |--->| B |--->| C |--->| D |--->| E |
254  // | | | | | | | | | |
255  // +---+ | | +->| |-+ | | +->| |-+ | |
256  // | G | +---+ | +---+ | +---+ | +---+ | +---+
257  // | | | | | |
258  // | | --------+ +--------+ |
259  // +---+ |
260  // ^ |
261  // +--------------------------------------+
262  //
263  std::atomic<HashtablezInfo*> all_;
265 
266  std::atomic<DisposeCallback> dispose_;
267 };
268 
269 // Enables or disables sampling for Swiss tables.
270 void SetHashtablezEnabled(bool enabled);
271 
272 // Sets the rate at which Swiss tables will be sampled.
273 void SetHashtablezSampleParameter(int32_t rate);
274 
275 // Sets a soft max for the number of samples that will be kept.
276 void SetHashtablezMaxSamples(int32_t max);
277 
278 // Configuration override.
279 // This allows process-wide sampling without depending on order of
280 // initialization of static storage duration objects.
281 // The definition of this constant is weak, which allows us to inject a
282 // different value for it at link time.
284 
285 } // namespace container_internal
286 } // namespace absl
287 
288 #endif // ABSL_CONTAINER_INTERNAL_HASHTABLEZ_SAMPLER_H_
#define EXCLUSIVE_LOCKS_REQUIRED(...)
void SetHashtablezSampleParameter(int32_t rate)
HashtablezInfo * SampleSlow(int64_t *next_sample)
void RecordInsertSlow(HashtablezInfo *info, size_t hash, size_t distance_from_desired)
HashtablezInfoHandle(HashtablezInfoHandle &&o) noexcept
HashtablezInfo & operator=(const HashtablezInfo &)=delete
void SetHashtablezEnabled(bool enabled)
void RecordStorageChangedSlow(HashtablezInfo *info, size_t size, size_t capacity)
#define ABSL_PREDICT_FALSE(x)
Definition: optimization.h:177
void UnsampleSlow(HashtablezInfo *info)
void SetHashtablezMaxSamples(int32_t max)
void PrepareForSampling() EXCLUSIVE_LOCKS_REQUIRED(init_mu)
HashtablezInfoHandle & operator=(HashtablezInfoHandle &&o) noexcept
void RecordEraseSlow(HashtablezInfo *info)
const bool kAbslContainerInternalSampleEverything
HashtablezInfoHandle Sample()
Definition: algorithm.h:29
void RecordRehash(size_t total_probe_length)
void RecordRehashSlow(HashtablezInfo *info, size_t total_probe_length)
void(*)(const HashtablezInfo &) DisposeCallback
void RecordInsert(size_t hash, size_t distance_from_desired)
HashtablezInfo *dead GUARDED_BY(init_mu)
hash_default_hash< typename T::first_type > hash
void swap(absl::InlinedVector< T, N, A > &a, absl::InlinedVector< T, N, A > &b) noexcept(noexcept(a.swap(b)))
UnboundConversion o
Definition: parser_test.cc:86
#define ABSL_PREDICT_TRUE(x)
Definition: optimization.h:178
void RecordStorageChanged(size_t size, size_t capacity)
friend void swap(HashtablezInfoHandle &lhs, HashtablezInfoHandle &rhs)
#define ABSL_PER_THREAD_TLS_KEYWORD
T exchange(T &obj, U &&new_value)
Definition: utility.h:312


abseil_cpp
Author(s):
autogenerated on Mon Feb 28 2022 21:31:18