hashtablez_sampler.cc
Go to the documentation of this file.
00001 // Copyright 2018 The Abseil Authors.
00002 //
00003 // Licensed under the Apache License, Version 2.0 (the "License");
00004 // you may not use this file except in compliance with the License.
00005 // You may obtain a copy of the License at
00006 //
00007 //      https://www.apache.org/licenses/LICENSE-2.0
00008 //
00009 // Unless required by applicable law or agreed to in writing, software
00010 // distributed under the License is distributed on an "AS IS" BASIS,
00011 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
00012 // See the License for the specific language governing permissions and
00013 // limitations under the License.
00014 
00015 #include "absl/container/internal/hashtablez_sampler.h"
00016 
00017 #include <atomic>
00018 #include <cassert>
00019 #include <cmath>
00020 #include <functional>
00021 #include <limits>
00022 
00023 #include "absl/base/attributes.h"
00024 #include "absl/container/internal/have_sse.h"
00025 #include "absl/debugging/stacktrace.h"
00026 #include "absl/memory/memory.h"
00027 #include "absl/synchronization/mutex.h"
00028 
00029 namespace absl {
00030 namespace container_internal {
00031 constexpr int HashtablezInfo::kMaxStackDepth;
00032 
00033 namespace {
00034 ABSL_CONST_INIT std::atomic<bool> g_hashtablez_enabled{
00035    false
00036 };
00037 ABSL_CONST_INIT std::atomic<int32_t> g_hashtablez_sample_parameter{1 << 10};
00038 ABSL_CONST_INIT std::atomic<int32_t> g_hashtablez_max_samples{1 << 20};
00039 
00040 // Returns the next pseudo-random value.
00041 // pRNG is: aX+b mod c with a = 0x5DEECE66D, b =  0xB, c = 1<<48
00042 // This is the lrand64 generator.
00043 uint64_t NextRandom(uint64_t rnd) {
00044   const uint64_t prng_mult = uint64_t{0x5DEECE66D};
00045   const uint64_t prng_add = 0xB;
00046   const uint64_t prng_mod_power = 48;
00047   const uint64_t prng_mod_mask = ~(~uint64_t{0} << prng_mod_power);
00048   return (prng_mult * rnd + prng_add) & prng_mod_mask;
00049 }
00050 
00051 // Generates a geometric variable with the specified mean.
00052 // This is done by generating a random number between 0 and 1 and applying
00053 // the inverse cumulative distribution function for an exponential.
00054 // Specifically: Let m be the inverse of the sample period, then
00055 // the probability distribution function is m*exp(-mx) so the CDF is
00056 // p = 1 - exp(-mx), so
00057 // q = 1 - p = exp(-mx)
00058 // log_e(q) = -mx
00059 // -log_e(q)/m = x
00060 // log_2(q) * (-log_e(2) * 1/m) = x
00061 // In the code, q is actually in the range 1 to 2**26, hence the -26 below
00062 //
00063 int64_t GetGeometricVariable(int64_t mean) {
00064 #if ABSL_HAVE_THREAD_LOCAL
00065   thread_local
00066 #else   // ABSL_HAVE_THREAD_LOCAL
00067   // SampleSlow and hence GetGeometricVariable is guarded by a single mutex when
00068   // there are not thread locals.  Thus, a single global rng is acceptable for
00069   // that case.
00070   static
00071 #endif  // ABSL_HAVE_THREAD_LOCAL
00072       uint64_t rng = []() {
00073         // We don't get well distributed numbers from this so we call
00074         // NextRandom() a bunch to mush the bits around.  We use a global_rand
00075         // to handle the case where the same thread (by memory address) gets
00076         // created and destroyed repeatedly.
00077         ABSL_CONST_INIT static std::atomic<uint32_t> global_rand(0);
00078         uint64_t r = reinterpret_cast<uint64_t>(&rng) +
00079                    global_rand.fetch_add(1, std::memory_order_relaxed);
00080         for (int i = 0; i < 20; ++i) {
00081           r = NextRandom(r);
00082         }
00083         return r;
00084       }();
00085 
00086   rng = NextRandom(rng);
00087 
00088   // Take the top 26 bits as the random number
00089   // (This plus the 1<<58 sampling bound give a max possible step of
00090   // 5194297183973780480 bytes.)
00091   const uint64_t prng_mod_power = 48;  // Number of bits in prng
00092   // The uint32_t cast is to prevent a (hard-to-reproduce) NAN
00093   // under piii debug for some binaries.
00094   double q = static_cast<uint32_t>(rng >> (prng_mod_power - 26)) + 1.0;
00095   // Put the computed p-value through the CDF of a geometric.
00096   double interval = (log2(q) - 26) * (-std::log(2.0) * mean);
00097 
00098   // Very large values of interval overflow int64_t. If we happen to
00099   // hit such improbable condition, we simply cheat and clamp interval
00100   // to largest supported value.
00101   if (interval > static_cast<double>(std::numeric_limits<int64_t>::max() / 2)) {
00102     return std::numeric_limits<int64_t>::max() / 2;
00103   }
00104 
00105   // Small values of interval are equivalent to just sampling next time.
00106   if (interval < 1) {
00107     return 1;
00108   }
00109   return static_cast<int64_t>(interval);
00110 }
00111 
00112 }  // namespace
00113 
00114 HashtablezSampler& HashtablezSampler::Global() {
00115   static auto* sampler = new HashtablezSampler();
00116   return *sampler;
00117 }
00118 
00119 HashtablezSampler::DisposeCallback HashtablezSampler::SetDisposeCallback(
00120     DisposeCallback f) {
00121   return dispose_.exchange(f, std::memory_order_relaxed);
00122 }
00123 
00124 HashtablezInfo::HashtablezInfo() { PrepareForSampling(); }
00125 HashtablezInfo::~HashtablezInfo() = default;
00126 
00127 void HashtablezInfo::PrepareForSampling() {
00128   capacity.store(0, std::memory_order_relaxed);
00129   size.store(0, std::memory_order_relaxed);
00130   num_erases.store(0, std::memory_order_relaxed);
00131   max_probe_length.store(0, std::memory_order_relaxed);
00132   total_probe_length.store(0, std::memory_order_relaxed);
00133   hashes_bitwise_or.store(0, std::memory_order_relaxed);
00134   hashes_bitwise_and.store(~size_t{}, std::memory_order_relaxed);
00135 
00136   create_time = absl::Now();
00137   // The inliner makes hardcoded skip_count difficult (especially when combined
00138   // with LTO).  We use the ability to exclude stacks by regex when encoding
00139   // instead.
00140   depth = absl::GetStackTrace(stack, HashtablezInfo::kMaxStackDepth,
00141                               /* skip_count= */ 0);
00142   dead = nullptr;
00143 }
00144 
00145 HashtablezSampler::HashtablezSampler()
00146     : dropped_samples_(0), size_estimate_(0), all_(nullptr), dispose_(nullptr) {
00147   absl::MutexLock l(&graveyard_.init_mu);
00148   graveyard_.dead = &graveyard_;
00149 }
00150 
00151 HashtablezSampler::~HashtablezSampler() {
00152   HashtablezInfo* s = all_.load(std::memory_order_acquire);
00153   while (s != nullptr) {
00154     HashtablezInfo* next = s->next;
00155     delete s;
00156     s = next;
00157   }
00158 }
00159 
00160 void HashtablezSampler::PushNew(HashtablezInfo* sample) {
00161   sample->next = all_.load(std::memory_order_relaxed);
00162   while (!all_.compare_exchange_weak(sample->next, sample,
00163                                      std::memory_order_release,
00164                                      std::memory_order_relaxed)) {
00165   }
00166 }
00167 
00168 void HashtablezSampler::PushDead(HashtablezInfo* sample) {
00169   if (auto* dispose = dispose_.load(std::memory_order_relaxed)) {
00170     dispose(*sample);
00171   }
00172 
00173   absl::MutexLock graveyard_lock(&graveyard_.init_mu);
00174   absl::MutexLock sample_lock(&sample->init_mu);
00175   sample->dead = graveyard_.dead;
00176   graveyard_.dead = sample;
00177 }
00178 
00179 HashtablezInfo* HashtablezSampler::PopDead() {
00180   absl::MutexLock graveyard_lock(&graveyard_.init_mu);
00181 
00182   // The list is circular, so eventually it collapses down to
00183   //   graveyard_.dead == &graveyard_
00184   // when it is empty.
00185   HashtablezInfo* sample = graveyard_.dead;
00186   if (sample == &graveyard_) return nullptr;
00187 
00188   absl::MutexLock sample_lock(&sample->init_mu);
00189   graveyard_.dead = sample->dead;
00190   sample->PrepareForSampling();
00191   return sample;
00192 }
00193 
00194 HashtablezInfo* HashtablezSampler::Register() {
00195   int64_t size = size_estimate_.fetch_add(1, std::memory_order_relaxed);
00196   if (size > g_hashtablez_max_samples.load(std::memory_order_relaxed)) {
00197     size_estimate_.fetch_sub(1, std::memory_order_relaxed);
00198     dropped_samples_.fetch_add(1, std::memory_order_relaxed);
00199     return nullptr;
00200   }
00201 
00202   HashtablezInfo* sample = PopDead();
00203   if (sample == nullptr) {
00204     // Resurrection failed.  Hire a new warlock.
00205     sample = new HashtablezInfo();
00206     PushNew(sample);
00207   }
00208 
00209   return sample;
00210 }
00211 
00212 void HashtablezSampler::Unregister(HashtablezInfo* sample) {
00213   PushDead(sample);
00214   size_estimate_.fetch_sub(1, std::memory_order_relaxed);
00215 }
00216 
00217 int64_t HashtablezSampler::Iterate(
00218     const std::function<void(const HashtablezInfo& stack)>& f) {
00219   HashtablezInfo* s = all_.load(std::memory_order_acquire);
00220   while (s != nullptr) {
00221     absl::MutexLock l(&s->init_mu);
00222     if (s->dead == nullptr) {
00223       f(*s);
00224     }
00225     s = s->next;
00226   }
00227 
00228   return dropped_samples_.load(std::memory_order_relaxed);
00229 }
00230 
00231 HashtablezInfo* SampleSlow(int64_t* next_sample) {
00232   if (kAbslContainerInternalSampleEverything) {
00233     *next_sample = 1;
00234     return HashtablezSampler::Global().Register();
00235   }
00236 
00237   bool first = *next_sample < 0;
00238   *next_sample = GetGeometricVariable(
00239       g_hashtablez_sample_parameter.load(std::memory_order_relaxed));
00240 
00241   // g_hashtablez_enabled can be dynamically flipped, we need to set a threshold
00242   // low enough that we will start sampling in a reasonable time, so we just use
00243   // the default sampling rate.
00244   if (!g_hashtablez_enabled.load(std::memory_order_relaxed)) return nullptr;
00245 
00246   // We will only be negative on our first count, so we should just retry in
00247   // that case.
00248   if (first) {
00249     if (ABSL_PREDICT_TRUE(--*next_sample > 0)) return nullptr;
00250     return SampleSlow(next_sample);
00251   }
00252 
00253   return HashtablezSampler::Global().Register();
00254 }
00255 
00256 #if ABSL_PER_THREAD_TLS == 1
00257 ABSL_PER_THREAD_TLS_KEYWORD int64_t global_next_sample = 0;
00258 #endif  // ABSL_PER_THREAD_TLS == 1
00259 
00260 void UnsampleSlow(HashtablezInfo* info) {
00261   HashtablezSampler::Global().Unregister(info);
00262 }
00263 
00264 void RecordInsertSlow(HashtablezInfo* info, size_t hash,
00265                       size_t distance_from_desired) {
00266   // SwissTables probe in groups of 16, so scale this to count items probes and
00267   // not offset from desired.
00268   size_t probe_length = distance_from_desired;
00269 #if SWISSTABLE_HAVE_SSE2
00270   probe_length /= 16;
00271 #else
00272   probe_length /= 8;
00273 #endif
00274 
00275   info->hashes_bitwise_and.fetch_and(hash, std::memory_order_relaxed);
00276   info->hashes_bitwise_or.fetch_or(hash, std::memory_order_relaxed);
00277   info->max_probe_length.store(
00278       std::max(info->max_probe_length.load(std::memory_order_relaxed),
00279                probe_length),
00280       std::memory_order_relaxed);
00281   info->total_probe_length.fetch_add(probe_length, std::memory_order_relaxed);
00282   info->size.fetch_add(1, std::memory_order_relaxed);
00283 }
00284 
00285 void SetHashtablezEnabled(bool enabled) {
00286   g_hashtablez_enabled.store(enabled, std::memory_order_release);
00287 }
00288 
00289 void SetHashtablezSampleParameter(int32_t rate) {
00290   if (rate > 0) {
00291     g_hashtablez_sample_parameter.store(rate, std::memory_order_release);
00292   } else {
00293     ABSL_RAW_LOG(ERROR, "Invalid hashtablez sample rate: %lld",
00294                  static_cast<long long>(rate));  // NOLINT(runtime/int)
00295   }
00296 }
00297 
00298 void SetHashtablezMaxSamples(int32_t max) {
00299   if (max > 0) {
00300     g_hashtablez_max_samples.store(max, std::memory_order_release);
00301   } else {
00302     ABSL_RAW_LOG(ERROR, "Invalid hashtablez max samples: %lld",
00303                  static_cast<long long>(max));  // NOLINT(runtime/int)
00304   }
00305 }
00306 
00307 }  // namespace container_internal
00308 }  // namespace absl


abseil_cpp
Author(s):
autogenerated on Wed Jun 19 2019 19:42:14