container/internal/hashtablez_sampler.h

0001 // Copyright 2018 The Abseil Authors.
0002 //
0003 // Licensed under the Apache License, Version 2.0 (the "License");
0004 // you may not use this file except in compliance with the License.
0005 // You may obtain a copy of the License at
0006 //
0007 //      https://www.apache.org/licenses/LICENSE-2.0
0008 //
0009 // Unless required by applicable law or agreed to in writing, software
0010 // distributed under the License is distributed on an "AS IS" BASIS,
0011 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
0012 // See the License for the specific language governing permissions and
0013 // limitations under the License.
0014 //
0015 // -----------------------------------------------------------------------------
0016 // File: hashtablez_sampler.h
0017 // -----------------------------------------------------------------------------
0018 //
0019 // This header file defines the API for a low level library to sample hashtables
0020 // and collect runtime statistics about them.
0021 //
0022 // `HashtablezSampler` controls the lifecycle of `HashtablezInfo` objects which
0023 // store information about a single sample.
0024 //
0025 // `Record*` methods store information into samples.
0026 // `Sample()` and `Unsample()` make use of a single global sampler with
0027 // properties controlled by the flags hashtablez_enabled,
0028 // hashtablez_sample_rate, and hashtablez_max_samples.
0029 //
0030 // WARNING
0031 //
0032 // Using this sampling API may cause sampled Swiss tables to use the global
0033 // allocator (operator `new`) in addition to any custom allocator.  If you
0034 // are using a table in an unusual circumstance where allocation or calling a
0035 // linux syscall is unacceptable, this could interfere.
0036 //
0037 // This utility is internal-only. Use at your own risk.
0038
0039 #ifndef ABSL_CONTAINER_INTERNAL_HASHTABLEZ_SAMPLER_H_
0040 #define ABSL_CONTAINER_INTERNAL_HASHTABLEZ_SAMPLER_H_
0041
0042 #include <atomic>
0043 #include <cstddef>
0044 #include <cstdint>
0045 #include <functional>
0046 #include <memory>
0047 #include <vector>
0048
0049 #include "absl/base/attributes.h"
0050 #include "absl/base/config.h"
0051 #include "absl/base/internal/per_thread_tls.h"
0052 #include "absl/base/optimization.h"
0053 #include "absl/base/thread_annotations.h"
0054 #include "absl/profiling/internal/sample_recorder.h"
0055 #include "absl/synchronization/mutex.h"
0056 #include "absl/time/time.h"
0057 #include "absl/utility/utility.h"
0058
0059 namespace absl {
0060 ABSL_NAMESPACE_BEGIN
0061 namespace container_internal {
0062
0063 // Stores information about a sampled hashtable.  All mutations to this *must*
0064 // be made through `Record*` functions below.  All reads from this *must* only
0065 // occur in the callback to `HashtablezSampler::Iterate`.
0066 struct HashtablezInfo : public profiling_internal::Sample<HashtablezInfo> {
0067   // Constructs the object but does not fill in any fields.
0068   HashtablezInfo();
0069   ~HashtablezInfo();
0070   HashtablezInfo(const HashtablezInfo&) = delete;
0071   HashtablezInfo& operator=(const HashtablezInfo&) = delete;
0072
0073   // Puts the object into a clean state, fills in the logically `const` members,
0074   // blocking for any readers that are currently sampling the object.
0075   void PrepareForSampling(int64_t stride, size_t inline_element_size_value,
0076                           size_t key_size, size_t value_size,
0077                           uint16_t soo_capacity_value)
0078       ABSL_EXCLUSIVE_LOCKS_REQUIRED(init_mu);
0079
0080   // These fields are mutated by the various Record* APIs and need to be
0081   // thread-safe.
0082   std::atomic<size_t> capacity;
0083   std::atomic<size_t> size;
0084   std::atomic<size_t> num_erases;
0085   std::atomic<size_t> num_rehashes;
0086   std::atomic<size_t> max_probe_length;
0087   std::atomic<size_t> total_probe_length;
0088   std::atomic<size_t> hashes_bitwise_or;
0089   std::atomic<size_t> hashes_bitwise_and;
0090   std::atomic<size_t> hashes_bitwise_xor;
0091   std::atomic<size_t> max_reserve;
0092
0093   // All of the fields below are set by `PrepareForSampling`, they must not be
0094   // mutated in `Record*` functions.  They are logically `const` in that sense.
0095   // These are guarded by init_mu, but that is not externalized to clients,
0096   // which can read them only during `SampleRecorder::Iterate` which will hold
0097   // the lock.
0098   static constexpr int kMaxStackDepth = 64;
0099   absl::Time create_time;
0100   int32_t depth;
0101   // The SOO capacity for this table in elements (not bytes). Note that sampled
0102   // tables are never SOO because we need to store the infoz handle on the heap.
0103   // Tables that would be SOO if not sampled should have: soo_capacity > 0 &&
0104   // size <= soo_capacity && max_reserve <= soo_capacity.
0105   uint16_t soo_capacity;
0106   void* stack[kMaxStackDepth];
0107   size_t inline_element_size;  // How big is the slot in bytes?
0108   size_t key_size;             // sizeof(key_type)
0109   size_t value_size;           // sizeof(value_type)
0110 };
0111
0112 void RecordRehashSlow(HashtablezInfo* info, size_t total_probe_length);
0113
0114 void RecordReservationSlow(HashtablezInfo* info, size_t target_capacity);
0115
0116 void RecordClearedReservationSlow(HashtablezInfo* info);
0117
0118 void RecordStorageChangedSlow(HashtablezInfo* info, size_t size,
0119                               size_t capacity);
0120
0121 void RecordInsertSlow(HashtablezInfo* info, size_t hash,
0122                       size_t distance_from_desired);
0123
0124 void RecordEraseSlow(HashtablezInfo* info);
0125
0126 struct SamplingState {
0127   int64_t next_sample;
0128   // When we make a sampling decision, we record that distance so we can weight
0129   // each sample.
0130   int64_t sample_stride;
0131 };
0132
0133 HashtablezInfo* SampleSlow(SamplingState& next_sample,
0134                            size_t inline_element_size, size_t key_size,
0135                            size_t value_size, uint16_t soo_capacity);
0136 void UnsampleSlow(HashtablezInfo* info);
0137
0138 #if defined(ABSL_INTERNAL_HASHTABLEZ_SAMPLE)
0139 #error ABSL_INTERNAL_HASHTABLEZ_SAMPLE cannot be directly set
0140 #endif  // defined(ABSL_INTERNAL_HASHTABLEZ_SAMPLE)
0141
0142 #if defined(ABSL_INTERNAL_HASHTABLEZ_SAMPLE)
0143 class HashtablezInfoHandle {
0144  public:
0145   explicit HashtablezInfoHandle() : info_(nullptr) {}
0146   explicit HashtablezInfoHandle(HashtablezInfo* info) : info_(info) {}
0147
0148   // We do not have a destructor. Caller is responsible for calling Unregister
0149   // before destroying the handle.
0150   void Unregister() {
0151     if (ABSL_PREDICT_TRUE(info_ == nullptr)) return;
0152     UnsampleSlow(info_);
0153   }
0154
0155   inline bool IsSampled() const { return ABSL_PREDICT_FALSE(info_ != nullptr); }
0156
0157   inline void RecordStorageChanged(size_t size, size_t capacity) {
0158     if (ABSL_PREDICT_TRUE(info_ == nullptr)) return;
0159     RecordStorageChangedSlow(info_, size, capacity);
0160   }
0161
0162   inline void RecordRehash(size_t total_probe_length) {
0163     if (ABSL_PREDICT_TRUE(info_ == nullptr)) return;
0164     RecordRehashSlow(info_, total_probe_length);
0165   }
0166
0167   inline void RecordReservation(size_t target_capacity) {
0168     if (ABSL_PREDICT_TRUE(info_ == nullptr)) return;
0169     RecordReservationSlow(info_, target_capacity);
0170   }
0171
0172   inline void RecordClearedReservation() {
0173     if (ABSL_PREDICT_TRUE(info_ == nullptr)) return;
0174     RecordClearedReservationSlow(info_);
0175   }
0176
0177   inline void RecordInsert(size_t hash, size_t distance_from_desired) {
0178     if (ABSL_PREDICT_TRUE(info_ == nullptr)) return;
0179     RecordInsertSlow(info_, hash, distance_from_desired);
0180   }
0181
0182   inline void RecordErase() {
0183     if (ABSL_PREDICT_TRUE(info_ == nullptr)) return;
0184     RecordEraseSlow(info_);
0185   }
0186
0187   friend inline void swap(HashtablezInfoHandle& lhs,
0188                           HashtablezInfoHandle& rhs) {
0189     std::swap(lhs.info_, rhs.info_);
0190   }
0191
0192  private:
0193   friend class HashtablezInfoHandlePeer;
0194   HashtablezInfo* info_;
0195 };
0196 #else
0197 // Ensure that when Hashtablez is turned off at compile time, HashtablezInfo can
0198 // be removed by the linker, in order to reduce the binary size.
0199 class HashtablezInfoHandle {
0200  public:
0201   explicit HashtablezInfoHandle() = default;
0202   explicit HashtablezInfoHandle(std::nullptr_t) {}
0203
0204   inline void Unregister() {}
0205   inline bool IsSampled() const { return false; }
0206   inline void RecordStorageChanged(size_t /*size*/, size_t /*capacity*/) {}
0207   inline void RecordRehash(size_t /*total_probe_length*/) {}
0208   inline void RecordReservation(size_t /*target_capacity*/) {}
0209   inline void RecordClearedReservation() {}
0210   inline void RecordInsert(size_t /*hash*/, size_t /*distance_from_desired*/) {}
0211   inline void RecordErase() {}
0212
0213   friend inline void swap(HashtablezInfoHandle& /*lhs*/,
0214                           HashtablezInfoHandle& /*rhs*/) {}
0215 };
0216 #endif  // defined(ABSL_INTERNAL_HASHTABLEZ_SAMPLE)
0217
0218 #if defined(ABSL_INTERNAL_HASHTABLEZ_SAMPLE)
0219 extern ABSL_PER_THREAD_TLS_KEYWORD SamplingState global_next_sample;
0220 #endif  // defined(ABSL_INTERNAL_HASHTABLEZ_SAMPLE)
0221
0222 // Returns a sampling handle.
0223 inline HashtablezInfoHandle Sample(
0224     ABSL_ATTRIBUTE_UNUSED size_t inline_element_size,
0225     ABSL_ATTRIBUTE_UNUSED size_t key_size,
0226     ABSL_ATTRIBUTE_UNUSED size_t value_size,
0227     ABSL_ATTRIBUTE_UNUSED uint16_t soo_capacity) {
0228 #if defined(ABSL_INTERNAL_HASHTABLEZ_SAMPLE)
0229   if (ABSL_PREDICT_TRUE(--global_next_sample.next_sample > 0)) {
0230     return HashtablezInfoHandle(nullptr);
0231   }
0232   return HashtablezInfoHandle(SampleSlow(global_next_sample,
0233                                          inline_element_size, key_size,
0234                                          value_size, soo_capacity));
0235 #else
0236   return HashtablezInfoHandle(nullptr);
0237 #endif  // !ABSL_PER_THREAD_TLS
0238 }
0239
0240 using HashtablezSampler =
0241     ::absl::profiling_internal::SampleRecorder<HashtablezInfo>;
0242
0243 // Returns a global Sampler.
0244 HashtablezSampler& GlobalHashtablezSampler();
0245
0246 using HashtablezConfigListener = void (*)();
0247 void SetHashtablezConfigListener(HashtablezConfigListener l);
0248
0249 // Enables or disables sampling for Swiss tables.
0250 bool IsHashtablezEnabled();
0251 void SetHashtablezEnabled(bool enabled);
0252 void SetHashtablezEnabledInternal(bool enabled);
0253
0254 // Sets the rate at which Swiss tables will be sampled.
0255 int32_t GetHashtablezSampleParameter();
0256 void SetHashtablezSampleParameter(int32_t rate);
0257 void SetHashtablezSampleParameterInternal(int32_t rate);
0258
0259 // Sets a soft max for the number of samples that will be kept.
0260 size_t GetHashtablezMaxSamples();
0261 void SetHashtablezMaxSamples(size_t max);
0262 void SetHashtablezMaxSamplesInternal(size_t max);
0263
0264 // Configuration override.
0265 // This allows process-wide sampling without depending on order of
0266 // initialization of static storage duration objects.
0267 // The definition of this constant is weak, which allows us to inject a
0268 // different value for it at link time.
0269 extern "C" bool ABSL_INTERNAL_C_SYMBOL(AbslContainerInternalSampleEverything)();
0270
0271 }  // namespace container_internal
0272 ABSL_NAMESPACE_END
0273 }  // namespace absl
0274
0275 #endif  // ABSL_CONTAINER_INTERNAL_HASHTABLEZ_SAMPLER_H_