1 files changed, 236 insertions, 0 deletions
diff --git a/absl/container/internal/hashtablez_sampler.h b/absl/container/internal/hashtablez_sampler.h
new file mode 100644
index 000000000000..4aea3ffa67de
--- /dev/null
+++ b/absl/container/internal/hashtablez_sampler.h
@@ -0,0 +1,236 @@
+// Copyright 2018 The Abseil Authors.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//      http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+//
+// This is a low level library to sample hashtables and collect runtime
+// statistics about them.
+//
+// `HashtablezSampler` controls the lifecycle of `HashtablezInfo` objects which
+// store information about a single sample.
+//
+// `Record*` methods store information into samples.
+// `Sample()` and `Unsample()` make use of a single global sampler with
+// properties controlled by the flags hashtablez_enabled,
+// hashtablez_sample_rate, and hashtablez_max_samples.
+
+#ifndef ABSL_CONTAINER_INTERNAL_HASHTABLEZ_SAMPLER_H_
+#define ABSL_CONTAINER_INTERNAL_HASHTABLEZ_SAMPLER_H_
+
+#include <atomic>
+#include <functional>
+#include <memory>
+#include <vector>
+
+#include "absl/base/optimization.h"
+#include "absl/synchronization/mutex.h"
+#include "absl/utility/utility.h"
+
+namespace absl {
+namespace container_internal {
+
+// Stores information about a sampled hashtable.  All mutations to this *must*
+// be made through `Record*` functions below.  All reads from this *must* only
+// occur in the callback to `HashtablezSampler::Iterate`.
+struct HashtablezInfo {
+  // Constructs the object but does not fill in any fields.
+  HashtablezInfo();
+  ~HashtablezInfo();
+  HashtablezInfo(const HashtablezInfo&) = delete;
+  HashtablezInfo& operator=(const HashtablezInfo&) = delete;
+
+  // Puts the object into a clean state, fills in the logically `const` members,
+  // blocking for any readers that are currently sampling the object.
+  void PrepareForSampling() EXCLUSIVE_LOCKS_REQUIRED(init_mu);
+
+  // These fields are mutated by the various Record* APIs and need to be
+  // thread-safe.
+  std::atomic<size_t> capacity;
+  std::atomic<size_t> size;
+  std::atomic<size_t> num_erases;
+  std::atomic<size_t> max_probe_length;
+  std::atomic<size_t> total_probe_length;
+  std::atomic<size_t> hashes_bitwise_or;
+  std::atomic<size_t> hashes_bitwise_and;
+
+  // `HashtablezSampler` maintains intrusive linked lists for all samples.  See
+  // comments on `HashtablezSampler::all_` for details on these.  `init_mu`
+  // guards the ability to restore the sample to a pristine state.  This
+  // prevents races with sampling and resurrecting an object.
+  absl::Mutex init_mu;
+  HashtablezInfo* next;
+  HashtablezInfo* dead GUARDED_BY(init_mu);
+
+  // All of the fields below are set by `PrepareForSampling`, they must not be
+  // mutated in `Record*` functions.  They are logically `const` in that sense.
+  // These are guarded by init_mu, but that is not externalized to clients, who
+  // can only read them during `HashtablezSampler::Iterate` which will hold the
+  // lock.
+  static constexpr int kMaxStackDepth = 64;
+  absl::Time create_time;
+  int32_t depth;
+  void* stack[kMaxStackDepth];
+};
+
+inline void RecordStorageChangedSlow(HashtablezInfo* info, size_t size,
+                                     size_t capacity) {
+  info->size.store(size, std::memory_order_relaxed);
+  info->capacity.store(capacity, std::memory_order_relaxed);
+}
+
+void RecordInsertSlow(HashtablezInfo* info, size_t hash,
+                      size_t distance_from_desired);
+
+inline void RecordEraseSlow(HashtablezInfo* info) {
+  info->size.fetch_sub(1, std::memory_order_relaxed);
+  info->num_erases.fetch_add(1, std::memory_order_relaxed);
+}
+
+HashtablezInfo* SampleSlow(int64_t* next_sample);
+void UnsampleSlow(HashtablezInfo* info);
+
+class HashtablezInfoHandle {
+ public:
+  explicit HashtablezInfoHandle() : info_(nullptr) {}
+  explicit HashtablezInfoHandle(HashtablezInfo* info) : info_(info) {}
+  ~HashtablezInfoHandle() {
+    if (ABSL_PREDICT_TRUE(info_ == nullptr)) return;
+    UnsampleSlow(info_);
+  }
+
+  HashtablezInfoHandle(const HashtablezInfoHandle&) = delete;
+  HashtablezInfoHandle& operator=(const HashtablezInfoHandle&) = delete;
+
+  HashtablezInfoHandle(HashtablezInfoHandle&& o) noexcept
+      : info_(absl::exchange(o.info_, nullptr)) {}
+  HashtablezInfoHandle& operator=(HashtablezInfoHandle&& o) noexcept {
+    if (ABSL_PREDICT_FALSE(info_ != nullptr)) {
+      UnsampleSlow(info_);
+    }
+    info_ = absl::exchange(o.info_, nullptr);
+    return *this;
+  }
+
+  inline void RecordStorageChanged(size_t size, size_t capacity) {
+    if (ABSL_PREDICT_TRUE(info_ == nullptr)) return;
+    RecordStorageChangedSlow(info_, size, capacity);
+  }
+
+  inline void RecordInsert(size_t hash, size_t distance_from_desired) {
+    if (ABSL_PREDICT_TRUE(info_ == nullptr)) return;
+    RecordInsertSlow(info_, hash, distance_from_desired);
+  }
+
+  inline void RecordErase() {
+    if (ABSL_PREDICT_TRUE(info_ == nullptr)) return;
+    RecordEraseSlow(info_);
+  }
+
+  friend inline void swap(HashtablezInfoHandle& lhs,
+                          HashtablezInfoHandle& rhs) {
+    std::swap(lhs.info_, rhs.info_);
+  }
+
+ private:
+  friend class HashtablezInfoHandlePeer;
+  HashtablezInfo* info_;
+};
+
+// Returns an RAII sampling handle that manages registration and unregistation
+// with the global sampler.
+inline HashtablezInfoHandle Sample() {
+#if ABSL_HAVE_THREAD_LOCAL
+  thread_local int64_t next_sample = 0;
+#else   // ABSL_HAVE_THREAD_LOCAL
+  static auto* mu = new absl::Mutex;
+  static int64_t next_sample = 0;
+  absl::MutexLock l(mu);
+#endif  // ABSL_HAVE_THREAD_LOCAL
+
+  if (ABSL_PREDICT_TRUE(--next_sample > 0)) {
+    return HashtablezInfoHandle(nullptr);
+  }
+  return HashtablezInfoHandle(SampleSlow(&next_sample));
+}
+
+// Holds samples and their associated stack traces with a soft limit of
+// `SetHashtablezMaxSamples()`.
+//
+// Thread safe.
+class HashtablezSampler {
+ public:
+  // Returns a global Sampler.
+  static HashtablezSampler& Global();
+
+  HashtablezSampler();
+  ~HashtablezSampler();
+
+  // Registers for sampling.  Returns an opaque registration info.
+  HashtablezInfo* Register();
+
+  // Unregisters the sample.
+  void Unregister(HashtablezInfo* sample);
+
+  // Iterates over all the registered `StackInfo`s.  Returning the number of
+  // samples that have been dropped.
+  int64_t Iterate(const std::function<void(const HashtablezInfo& stack)>& f);
+
+ private:
+  void PushNew(HashtablezInfo* sample);
+  void PushDead(HashtablezInfo* sample);
+  HashtablezInfo* PopDead();
+
+  std::atomic<size_t> dropped_samples_;
+  std::atomic<size_t> size_estimate_;
+
+  // Intrusive lock free linked lists for tracking samples.
+  //
+  // `all_` records all samples (they are never removed from this list) and is
+  // terminated with a `nullptr`.
+  //
+  // `graveyard_.dead` is a circular linked list.  When it is empty,
+  // `graveyard_.dead == &graveyard`.  The list is circular so that
+  // every item on it (even the last) has a non-null dead pointer.  This allows
+  // `Iterate` to determine if a given sample is live or dead using only
+  // information on the sample itself.
+  //
+  // For example, nodes [A, B, C, D, E] with [A, C, E] alive and [B, D] dead
+  // looks like this (G is the Graveyard):
+  //
+  //           +---+    +---+    +---+    +---+    +---+
+  //    all -->| A |--->| B |--->| C |--->| D |--->| E |
+  //           |   |    |   |    |   |    |   |    |   |
+  //   +---+   |   | +->|   |-+  |   | +->|   |-+  |   |
+  //   | G |   +---+ |  +---+ |  +---+ |  +---+ |  +---+
+  //   |   |         |        |        |        |
+  //   |   | --------+        +--------+        |
+  //   +---+                                    |
+  //     ^                                      |
+  //     +--------------------------------------+
+  //
+  std::atomic<HashtablezInfo*> all_;
+  HashtablezInfo graveyard_;
+};
+
+// Enables or disables sampling for Swiss tables.
+void SetHashtablezEnabled(bool enabled);
+
+// Sets the rate at which Swiss tables will be sampled.
+void SetHashtablezSampleParameter(int32_t rate);
+
+// Sets a soft max for the number of samples that will be kept.
+void SetHashtablezMaxSamples(int32_t max);
+
+}  // namespace container_internal
+}  // namespace absl
+
+#endif  // ABSL_CONTAINER_INTERNAL_HASHTABLEZ_SAMPLER_H_