hashtablez_sampler.cc
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 
16 
17 #include <atomic>
18 #include <cassert>
19 #include <cmath>
20 #include <functional>
21 #include <limits>
22 
23 #include "absl/base/attributes.h"
26 #include "absl/memory/memory.h"
28 
29 namespace absl {
30 namespace container_internal {
31 constexpr int HashtablezInfo::kMaxStackDepth;
32 
33 namespace {
34 ABSL_CONST_INIT std::atomic<bool> g_hashtablez_enabled{
35  false
36 };
37 ABSL_CONST_INIT std::atomic<int32_t> g_hashtablez_sample_parameter{1 << 10};
38 ABSL_CONST_INIT std::atomic<int32_t> g_hashtablez_max_samples{1 << 20};
39 
40 // Returns the next pseudo-random value.
41 // pRNG is: aX+b mod c with a = 0x5DEECE66D, b = 0xB, c = 1<<48
42 // This is the lrand64 generator.
43 uint64_t NextRandom(uint64_t rnd) {
44  const uint64_t prng_mult = uint64_t{0x5DEECE66D};
45  const uint64_t prng_add = 0xB;
46  const uint64_t prng_mod_power = 48;
47  const uint64_t prng_mod_mask = ~(~uint64_t{0} << prng_mod_power);
48  return (prng_mult * rnd + prng_add) & prng_mod_mask;
49 }
50 
51 // Generates a geometric variable with the specified mean.
52 // This is done by generating a random number between 0 and 1 and applying
53 // the inverse cumulative distribution function for an exponential.
54 // Specifically: Let m be the inverse of the sample period, then
55 // the probability distribution function is m*exp(-mx) so the CDF is
56 // p = 1 - exp(-mx), so
57 // q = 1 - p = exp(-mx)
58 // log_e(q) = -mx
59 // -log_e(q)/m = x
60 // log_2(q) * (-log_e(2) * 1/m) = x
61 // In the code, q is actually in the range 1 to 2**26, hence the -26 below
62 //
63 int64_t GetGeometricVariable(int64_t mean) {
64 #if ABSL_HAVE_THREAD_LOCAL
65  thread_local
66 #else // ABSL_HAVE_THREAD_LOCAL
67  // SampleSlow and hence GetGeometricVariable is guarded by a single mutex when
68  // there are not thread locals. Thus, a single global rng is acceptable for
69  // that case.
70  static
71 #endif // ABSL_HAVE_THREAD_LOCAL
72  uint64_t rng = []() {
73  // We don't get well distributed numbers from this so we call
74  // NextRandom() a bunch to mush the bits around. We use a global_rand
75  // to handle the case where the same thread (by memory address) gets
76  // created and destroyed repeatedly.
77  ABSL_CONST_INIT static std::atomic<uint32_t> global_rand(0);
78  uint64_t r = reinterpret_cast<uint64_t>(&rng) +
79  global_rand.fetch_add(1, std::memory_order_relaxed);
80  for (int i = 0; i < 20; ++i) {
81  r = NextRandom(r);
82  }
83  return r;
84  }();
85 
86  rng = NextRandom(rng);
87 
88  // Take the top 26 bits as the random number
89  // (This plus the 1<<58 sampling bound give a max possible step of
90  // 5194297183973780480 bytes.)
91  const uint64_t prng_mod_power = 48; // Number of bits in prng
92  // The uint32_t cast is to prevent a (hard-to-reproduce) NAN
93  // under piii debug for some binaries.
94  double q = static_cast<uint32_t>(rng >> (prng_mod_power - 26)) + 1.0;
95  // Put the computed p-value through the CDF of a geometric.
96  double interval = (log2(q) - 26) * (-std::log(2.0) * mean);
97 
98  // Very large values of interval overflow int64_t. If we happen to
99  // hit such improbable condition, we simply cheat and clamp interval
100  // to largest supported value.
101  if (interval > static_cast<double>(std::numeric_limits<int64_t>::max() / 2)) {
102  return std::numeric_limits<int64_t>::max() / 2;
103  }
104 
105  // Small values of interval are equivalent to just sampling next time.
106  if (interval < 1) {
107  return 1;
108  }
109  return static_cast<int64_t>(interval);
110 }
111 
112 } // namespace
113 
115  static auto* sampler = new HashtablezSampler();
116  return *sampler;
117 }
118 
120  DisposeCallback f) {
121  return dispose_.exchange(f, std::memory_order_relaxed);
122 }
123 
124 HashtablezInfo::HashtablezInfo() { PrepareForSampling(); }
126 
128  capacity.store(0, std::memory_order_relaxed);
129  size.store(0, std::memory_order_relaxed);
130  num_erases.store(0, std::memory_order_relaxed);
131  max_probe_length.store(0, std::memory_order_relaxed);
132  total_probe_length.store(0, std::memory_order_relaxed);
133  hashes_bitwise_or.store(0, std::memory_order_relaxed);
134  hashes_bitwise_and.store(~size_t{}, std::memory_order_relaxed);
135 
136  create_time = absl::Now();
137  // The inliner makes hardcoded skip_count difficult (especially when combined
138  // with LTO). We use the ability to exclude stacks by regex when encoding
139  // instead.
140  depth = absl::GetStackTrace(stack, HashtablezInfo::kMaxStackDepth,
141  /* skip_count= */ 0);
142  dead = nullptr;
143 }
144 
146  : dropped_samples_(0), size_estimate_(0), all_(nullptr), dispose_(nullptr) {
148  graveyard_.dead = &graveyard_;
149 }
150 
152  HashtablezInfo* s = all_.load(std::memory_order_acquire);
153  while (s != nullptr) {
154  HashtablezInfo* next = s->next;
155  delete s;
156  s = next;
157  }
158 }
159 
161  sample->next = all_.load(std::memory_order_relaxed);
162  while (!all_.compare_exchange_weak(sample->next, sample,
163  std::memory_order_release,
164  std::memory_order_relaxed)) {
165  }
166 }
167 
169  if (auto* dispose = dispose_.load(std::memory_order_relaxed)) {
170  dispose(*sample);
171  }
172 
173  absl::MutexLock graveyard_lock(&graveyard_.init_mu);
174  absl::MutexLock sample_lock(&sample->init_mu);
175  sample->dead = graveyard_.dead;
176  graveyard_.dead = sample;
177 }
178 
180  absl::MutexLock graveyard_lock(&graveyard_.init_mu);
181 
182  // The list is circular, so eventually it collapses down to
183  // graveyard_.dead == &graveyard_
184  // when it is empty.
185  HashtablezInfo* sample = graveyard_.dead;
186  if (sample == &graveyard_) return nullptr;
187 
188  absl::MutexLock sample_lock(&sample->init_mu);
189  graveyard_.dead = sample->dead;
190  sample->PrepareForSampling();
191  return sample;
192 }
193 
195  int64_t size = size_estimate_.fetch_add(1, std::memory_order_relaxed);
196  if (size > g_hashtablez_max_samples.load(std::memory_order_relaxed)) {
197  size_estimate_.fetch_sub(1, std::memory_order_relaxed);
198  dropped_samples_.fetch_add(1, std::memory_order_relaxed);
199  return nullptr;
200  }
201 
202  HashtablezInfo* sample = PopDead();
203  if (sample == nullptr) {
204  // Resurrection failed. Hire a new warlock.
205  sample = new HashtablezInfo();
206  PushNew(sample);
207  }
208 
209  return sample;
210 }
211 
213  PushDead(sample);
214  size_estimate_.fetch_sub(1, std::memory_order_relaxed);
215 }
216 
218  const std::function<void(const HashtablezInfo& stack)>& f) {
219  HashtablezInfo* s = all_.load(std::memory_order_acquire);
220  while (s != nullptr) {
221  absl::MutexLock l(&s->init_mu);
222  if (s->dead == nullptr) {
223  f(*s);
224  }
225  s = s->next;
226  }
227 
228  return dropped_samples_.load(std::memory_order_relaxed);
229 }
230 
231 HashtablezInfo* SampleSlow(int64_t* next_sample) {
233  *next_sample = 1;
235  }
236 
237  bool first = *next_sample < 0;
238  *next_sample = GetGeometricVariable(
239  g_hashtablez_sample_parameter.load(std::memory_order_relaxed));
240 
241  // g_hashtablez_enabled can be dynamically flipped, we need to set a threshold
242  // low enough that we will start sampling in a reasonable time, so we just use
243  // the default sampling rate.
244  if (!g_hashtablez_enabled.load(std::memory_order_relaxed)) return nullptr;
245 
246  // We will only be negative on our first count, so we should just retry in
247  // that case.
248  if (first) {
249  if (ABSL_PREDICT_TRUE(--*next_sample > 0)) return nullptr;
250  return SampleSlow(next_sample);
251  }
252 
254 }
255 
256 #if ABSL_PER_THREAD_TLS == 1
257 ABSL_PER_THREAD_TLS_KEYWORD int64_t global_next_sample = 0;
258 #endif // ABSL_PER_THREAD_TLS == 1
259 
262 }
263 
265  size_t distance_from_desired) {
266  // SwissTables probe in groups of 16, so scale this to count items probes and
267  // not offset from desired.
268  size_t probe_length = distance_from_desired;
269 #if SWISSTABLE_HAVE_SSE2
270  probe_length /= 16;
271 #else
272  probe_length /= 8;
273 #endif
274 
275  info->hashes_bitwise_and.fetch_and(hash, std::memory_order_relaxed);
276  info->hashes_bitwise_or.fetch_or(hash, std::memory_order_relaxed);
277  info->max_probe_length.store(
278  std::max(info->max_probe_length.load(std::memory_order_relaxed),
279  probe_length),
280  std::memory_order_relaxed);
281  info->total_probe_length.fetch_add(probe_length, std::memory_order_relaxed);
282  info->size.fetch_add(1, std::memory_order_relaxed);
283 }
284 
285 void SetHashtablezEnabled(bool enabled) {
286  g_hashtablez_enabled.store(enabled, std::memory_order_release);
287 }
288 
289 void SetHashtablezSampleParameter(int32_t rate) {
290  if (rate > 0) {
291  g_hashtablez_sample_parameter.store(rate, std::memory_order_release);
292  } else {
293  ABSL_RAW_LOG(ERROR, "Invalid hashtablez sample rate: %lld",
294  static_cast<long long>(rate)); // NOLINT(runtime/int)
295  }
296 }
297 
298 void SetHashtablezMaxSamples(int32_t max) {
299  if (max > 0) {
300  g_hashtablez_max_samples.store(max, std::memory_order_release);
301  } else {
302  ABSL_RAW_LOG(ERROR, "Invalid hashtablez max samples: %lld",
303  static_cast<long long>(max)); // NOLINT(runtime/int)
304  }
305 }
306 
307 } // namespace container_internal
308 } // namespace absl
void SetHashtablezSampleParameter(int32_t rate)
HashtablezInfo * SampleSlow(int64_t *next_sample)
#define ABSL_CONST_INIT
Definition: attributes.h:605
Time Now()
Definition: clock.cc:37
void RecordInsertSlow(HashtablezInfo *info, size_t hash, size_t distance_from_desired)
#define ABSL_RAW_LOG(severity,...)
Definition: raw_logging.h:42
void SetHashtablezEnabled(bool enabled)
void UnsampleSlow(HashtablezInfo *info)
void SetHashtablezMaxSamples(int32_t max)
void PrepareForSampling() EXCLUSIVE_LOCKS_REQUIRED(init_mu)
const bool kAbslContainerInternalSampleEverything
Definition: algorithm.h:29
void(*)(const HashtablezInfo &) DisposeCallback
AllocList * next[kMaxLevel]
hash_default_hash< typename T::first_type > hash
void * stack[40]
Definition: graphcycles.cc:286
bool log
Definition: mutex.cc:293
int64_t Iterate(const std::function< void(const HashtablezInfo &stack)> &f)
uintptr_t size
#define ABSL_PREDICT_TRUE(x)
Definition: optimization.h:178
#define ABSL_PER_THREAD_TLS_KEYWORD
DisposeCallback SetDisposeCallback(DisposeCallback f)
ABSL_ATTRIBUTE_NOINLINE ABSL_ATTRIBUTE_NO_TAIL_CALL int GetStackTrace(void **result, int max_depth, int skip_count)
Definition: stacktrace.cc:98


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