blob: a89518bb03c96a92adc4c0f1cb683f3213d2f1e9 [file] [log] [blame]
// 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
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// See the License for the specific language governing permissions and
// limitations under the License.
// -----------------------------------------------------------------------------
// File: hashtablez_sampler.h
// -----------------------------------------------------------------------------
// This header file defines the API for 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.
// Using this sampling API may cause sampled Swiss tables to use the global
// allocator (operator `new`) in addition to any custom allocator. If you
// are using a table in an unusual circumstance where allocation or calling a
// linux syscall is unacceptable, this could interfere.
// This utility is internal-only. Use at your own risk.
#include <atomic>
#include <functional>
#include <memory>
#include <vector>
#include "absl/base/config.h"
#include "absl/base/internal/per_thread_tls.h"
#include "absl/base/optimization.h"
#include "absl/profiling/internal/sample_recorder.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 : public profiling_internal::Sample<HashtablezInfo> {
// Constructs the object but does not fill in any fields.
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(int64_t stride, size_t inline_element_size_value)
// 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> num_rehashes;
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;
std::atomic<size_t> hashes_bitwise_xor;
std::atomic<size_t> max_reserve;
// 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,
// which can read them only during `SampleRecorder::Iterate` which will hold
// the lock.
static constexpr int kMaxStackDepth = 64;
absl::Time create_time;
int32_t depth;
void* stack[kMaxStackDepth];
size_t inline_element_size; // How big is the slot?
inline void RecordRehashSlow(HashtablezInfo* info, size_t total_probe_length) {
total_probe_length /= 16;
total_probe_length /= 8;
info->, std::memory_order_relaxed);
info->, std::memory_order_relaxed);
// There is only one concurrent writer, so `load` then `store` is sufficient
// instead of using `fetch_add`.
1 + info->num_rehashes.load(std::memory_order_relaxed),
inline void RecordReservationSlow(HashtablezInfo* info,
size_t target_capacity) {
inline void RecordClearedReservationSlow(HashtablezInfo* info) {
info->, std::memory_order_relaxed);
inline void RecordStorageChangedSlow(HashtablezInfo* info, size_t size,
size_t capacity) {
info->, std::memory_order_relaxed);
info->, std::memory_order_relaxed);
if (size == 0) {
// This is a clear, reset the total/num_erases too.
info->, std::memory_order_relaxed);
info->, 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);
// There is only one concurrent writer, so `load` then `store` is sufficient
// instead of using `fetch_add`.
1 + info->num_erases.load(std::memory_order_relaxed),
struct SamplingState {
int64_t next_sample;
// When we make a sampling decision, we record that distance so we can weight
// each sample.
int64_t sample_stride;
HashtablezInfo* SampleSlow(SamplingState& next_sample,
size_t inline_element_size);
void UnsampleSlow(HashtablezInfo* info);
#error ABSL_INTERNAL_HASHTABLEZ_SAMPLE cannot be directly set
class HashtablezInfoHandle {
explicit HashtablezInfoHandle() : info_(nullptr) {}
explicit HashtablezInfoHandle(HashtablezInfo* info) : info_(info) {}
~HashtablezInfoHandle() {
if (ABSL_PREDICT_TRUE(info_ == nullptr)) return;
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)) {
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 RecordRehash(size_t total_probe_length) {
if (ABSL_PREDICT_TRUE(info_ == nullptr)) return;
RecordRehashSlow(info_, total_probe_length);
inline void RecordReservation(size_t target_capacity) {
if (ABSL_PREDICT_TRUE(info_ == nullptr)) return;
RecordReservationSlow(info_, target_capacity);
inline void RecordClearedReservation() {
if (ABSL_PREDICT_TRUE(info_ == nullptr)) return;
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;
friend inline void swap(HashtablezInfoHandle& lhs,
HashtablezInfoHandle& rhs) {
std::swap(lhs.info_, rhs.info_);
friend class HashtablezInfoHandlePeer;
HashtablezInfo* info_;
// Ensure that when Hashtablez is turned off at compile time, HashtablezInfo can
// be removed by the linker, in order to reduce the binary size.
class HashtablezInfoHandle {
explicit HashtablezInfoHandle() = default;
explicit HashtablezInfoHandle(std::nullptr_t) {}
inline void RecordStorageChanged(size_t /*size*/, size_t /*capacity*/) {}
inline void RecordRehash(size_t /*total_probe_length*/) {}
inline void RecordReservation(size_t /*target_capacity*/) {}
inline void RecordClearedReservation() {}
inline void RecordInsert(size_t /*hash*/, size_t /*distance_from_desired*/) {}
inline void RecordErase() {}
friend inline void swap(HashtablezInfoHandle& /*lhs*/,
HashtablezInfoHandle& /*rhs*/) {}
extern ABSL_PER_THREAD_TLS_KEYWORD SamplingState global_next_sample;
// Returns an RAII sampling handle that manages registration and unregistation
// with the global sampler.
inline HashtablezInfoHandle Sample(
size_t inline_element_size ABSL_ATTRIBUTE_UNUSED) {
if (ABSL_PREDICT_TRUE(--global_next_sample.next_sample > 0)) {
return HashtablezInfoHandle(nullptr);
return HashtablezInfoHandle(
SampleSlow(global_next_sample, inline_element_size));
return HashtablezInfoHandle(nullptr);
using HashtablezSampler =
// Returns a global Sampler.
HashtablezSampler& GlobalHashtablezSampler();
using HashtablezConfigListener = void (*)();
void SetHashtablezConfigListener(HashtablezConfigListener l);
// Enables or disables sampling for Swiss tables.
bool IsHashtablezEnabled();
void SetHashtablezEnabled(bool enabled);
void SetHashtablezEnabledInternal(bool enabled);
// Sets the rate at which Swiss tables will be sampled.
int32_t GetHashtablezSampleParameter();
void SetHashtablezSampleParameter(int32_t rate);
void SetHashtablezSampleParameterInternal(int32_t rate);
// Sets a soft max for the number of samples that will be kept.
size_t GetHashtablezMaxSamples();
void SetHashtablezMaxSamples(size_t max);
void SetHashtablezMaxSamplesInternal(size_t max);
// Configuration override.
// This allows process-wide sampling without depending on order of
// initialization of static storage duration objects.
// The definition of this constant is weak, which allows us to inject a
// different value for it at link time.
extern "C" bool ABSL_INTERNAL_C_SYMBOL(AbslContainerInternalSampleEverything)();
} // namespace container_internal
} // namespace absl