legacy-libs/grpc-cloned/deps/grpc/third_party/abseil-cpp/absl/container/internal/hashtablez_sampler.h

   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
  47 #include "absl/base/internal/per_thread_tls.h"
  48 #include "absl/base/optimization.h"
  49 #include "absl/container/internal/have_sse.h"
  50 #include "absl/synchronization/mutex.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`.
  59 struct HashtablezInfo {
  60   // Constructs the object but does not fill in any fields.
  61   HashtablezInfo();
  62   ~HashtablezInfo();
  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.
  68   void PrepareForSampling() EXCLUSIVE_LOCKS_REQUIRED(init_mu);
  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.
  84   absl::Mutex init_mu;
  85   HashtablezInfo* next;
  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;
  94   absl::Time create_time;
  95   int32_t depth;
  96   void* stack[kMaxStackDepth];
  97 };
  98
  99 inline void RecordRehashSlow(HashtablezInfo* info, size_t total_probe_length) {
 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
 130 class HashtablezInfoHandle {
 131  public:
 132   explicit HashtablezInfoHandle() : info_(nullptr) {}
 133   explicit HashtablezInfoHandle(HashtablezInfo* info) : info_(info) {}
 134   ~HashtablezInfoHandle() {
 135     if (ABSL_PREDICT_TRUE(info_ == nullptr)) return;
 136     UnsampleSlow(info_);
 137   }
 138
 139   HashtablezInfoHandle(const HashtablezInfoHandle&) = delete;
 140   HashtablezInfoHandle& operator=(const HashtablezInfoHandle&) = delete;
 141
 142   HashtablezInfoHandle(HashtablezInfoHandle&& o) noexcept
 143       : info_(absl::exchange(o.info_, nullptr)) {}
 144   HashtablezInfoHandle& operator=(HashtablezInfoHandle&& o) noexcept {
 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:
 178   friend class HashtablezInfoHandlePeer;
 179   HashtablezInfo* info_;
 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.
 188 inline HashtablezInfoHandle Sample() {
 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.
 205 class HashtablezSampler {
 206  public:
 207   // Returns a global Sampler.
 208   static HashtablezSampler& Global();
 209
 210   HashtablezSampler();
 211   ~HashtablezSampler();
 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_;
 264   HashtablezInfo graveyard_;
 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.
 283 extern "C" const bool kAbslContainerInternalSampleEverything;
 284
 285 }  // namespace container_internal
 286 }  // namespace absl
 287
 288 #endif  // ABSL_CONTAINER_INTERNAL_HASHTABLEZ_SAMPLER_H_