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
53namespace absl {
54namespace 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`.
59struct 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
99inline 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
109inline 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
119void RecordInsertSlow(HashtablezInfo* info, size_t hash,
120 size_t distance_from_desired);
121
122inline 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
127HashtablezInfo* SampleSlow(int64_t* next_sample);
128void UnsampleSlow(HashtablezInfo* info);
129
130class 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
183extern 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.
188inline 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.
205class 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.
270void SetHashtablezEnabled(bool enabled);
271
272// Sets the rate at which Swiss tables will be sampled.
273void SetHashtablezSampleParameter(int32_t rate);
274
275// Sets a soft max for the number of samples that will be kept.
276void 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.
283extern "C" const bool kAbslContainerInternalSampleEverything;
284
285} // namespace container_internal
286} // namespace absl
287
288#endif // ABSL_CONTAINER_INTERNAL_HASHTABLEZ_SAMPLER_H_
289