Coverage Report

Created: 2024-09-23 06:29

/src/abseil-cpp/absl/container/internal/hashtablez_sampler.h
Line
Count
Source (jump to first uncovered line)
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 <cstddef>
44
#include <cstdint>
45
#include <functional>
46
#include <memory>
47
#include <vector>
48
49
#include "absl/base/attributes.h"
50
#include "absl/base/config.h"
51
#include "absl/base/internal/per_thread_tls.h"
52
#include "absl/base/optimization.h"
53
#include "absl/base/thread_annotations.h"
54
#include "absl/profiling/internal/sample_recorder.h"
55
#include "absl/synchronization/mutex.h"
56
#include "absl/time/time.h"
57
#include "absl/utility/utility.h"
58
59
namespace absl {
60
ABSL_NAMESPACE_BEGIN
61
namespace container_internal {
62
63
// Stores information about a sampled hashtable.  All mutations to this *must*
64
// be made through `Record*` functions below.  All reads from this *must* only
65
// occur in the callback to `HashtablezSampler::Iterate`.
66
struct HashtablezInfo : public profiling_internal::Sample<HashtablezInfo> {
67
  // Constructs the object but does not fill in any fields.
68
  HashtablezInfo();
69
  ~HashtablezInfo();
70
  HashtablezInfo(const HashtablezInfo&) = delete;
71
  HashtablezInfo& operator=(const HashtablezInfo&) = delete;
72
73
  // Puts the object into a clean state, fills in the logically `const` members,
74
  // blocking for any readers that are currently sampling the object.
75
  void PrepareForSampling(int64_t stride, size_t inline_element_size_value,
76
                          size_t key_size, size_t value_size,
77
                          uint16_t soo_capacity_value)
78
      ABSL_EXCLUSIVE_LOCKS_REQUIRED(init_mu);
79
80
  // These fields are mutated by the various Record* APIs and need to be
81
  // thread-safe.
82
  std::atomic<size_t> capacity;
83
  std::atomic<size_t> size;
84
  std::atomic<size_t> num_erases;
85
  std::atomic<size_t> num_rehashes;
86
  std::atomic<size_t> max_probe_length;
87
  std::atomic<size_t> total_probe_length;
88
  std::atomic<size_t> hashes_bitwise_or;
89
  std::atomic<size_t> hashes_bitwise_and;
90
  std::atomic<size_t> hashes_bitwise_xor;
91
  std::atomic<size_t> max_reserve;
92
93
  // All of the fields below are set by `PrepareForSampling`, they must not be
94
  // mutated in `Record*` functions.  They are logically `const` in that sense.
95
  // These are guarded by init_mu, but that is not externalized to clients,
96
  // which can read them only during `SampleRecorder::Iterate` which will hold
97
  // the lock.
98
  static constexpr int kMaxStackDepth = 64;
99
  absl::Time create_time;
100
  int32_t depth;
101
  // The SOO capacity for this table in elements (not bytes). Note that sampled
102
  // tables are never SOO because we need to store the infoz handle on the heap.
103
  // Tables that would be SOO if not sampled should have: soo_capacity > 0 &&
104
  // size <= soo_capacity && max_reserve <= soo_capacity.
105
  uint16_t soo_capacity;
106
  void* stack[kMaxStackDepth];
107
  size_t inline_element_size;  // How big is the slot in bytes?
108
  size_t key_size;             // sizeof(key_type)
109
  size_t value_size;           // sizeof(value_type)
110
};
111
112
void RecordRehashSlow(HashtablezInfo* info, size_t total_probe_length);
113
114
void RecordReservationSlow(HashtablezInfo* info, size_t target_capacity);
115
116
void RecordClearedReservationSlow(HashtablezInfo* info);
117
118
void RecordStorageChangedSlow(HashtablezInfo* info, size_t size,
119
                              size_t capacity);
120
121
void RecordInsertSlow(HashtablezInfo* info, size_t hash,
122
                      size_t distance_from_desired);
123
124
void RecordEraseSlow(HashtablezInfo* info);
125
126
struct SamplingState {
127
  int64_t next_sample;
128
  // When we make a sampling decision, we record that distance so we can weight
129
  // each sample.
130
  int64_t sample_stride;
131
};
132
133
HashtablezInfo* SampleSlow(SamplingState& next_sample,
134
                           size_t inline_element_size, size_t key_size,
135
                           size_t value_size, uint16_t soo_capacity);
136
void UnsampleSlow(HashtablezInfo* info);
137
138
#if defined(ABSL_INTERNAL_HASHTABLEZ_SAMPLE)
139
#error ABSL_INTERNAL_HASHTABLEZ_SAMPLE cannot be directly set
140
#endif  // defined(ABSL_INTERNAL_HASHTABLEZ_SAMPLE)
141
142
#if defined(ABSL_INTERNAL_HASHTABLEZ_SAMPLE)
143
class HashtablezInfoHandle {
144
 public:
145
  explicit HashtablezInfoHandle() : info_(nullptr) {}
146
  explicit HashtablezInfoHandle(HashtablezInfo* info) : info_(info) {}
147
148
  // We do not have a destructor. Caller is responsible for calling Unregister
149
  // before destroying the handle.
150
  void Unregister() {
151
    if (ABSL_PREDICT_TRUE(info_ == nullptr)) return;
152
    UnsampleSlow(info_);
153
  }
154
155
  inline bool IsSampled() const { return ABSL_PREDICT_FALSE(info_ != nullptr); }
156
157
  inline void RecordStorageChanged(size_t size, size_t capacity) {
158
    if (ABSL_PREDICT_TRUE(info_ == nullptr)) return;
159
    RecordStorageChangedSlow(info_, size, capacity);
160
  }
161
162
  inline void RecordRehash(size_t total_probe_length) {
163
    if (ABSL_PREDICT_TRUE(info_ == nullptr)) return;
164
    RecordRehashSlow(info_, total_probe_length);
165
  }
166
167
  inline void RecordReservation(size_t target_capacity) {
168
    if (ABSL_PREDICT_TRUE(info_ == nullptr)) return;
169
    RecordReservationSlow(info_, target_capacity);
170
  }
171
172
  inline void RecordClearedReservation() {
173
    if (ABSL_PREDICT_TRUE(info_ == nullptr)) return;
174
    RecordClearedReservationSlow(info_);
175
  }
176
177
  inline void RecordInsert(size_t hash, size_t distance_from_desired) {
178
    if (ABSL_PREDICT_TRUE(info_ == nullptr)) return;
179
    RecordInsertSlow(info_, hash, distance_from_desired);
180
  }
181
182
  inline void RecordErase() {
183
    if (ABSL_PREDICT_TRUE(info_ == nullptr)) return;
184
    RecordEraseSlow(info_);
185
  }
186
187
  friend inline void swap(HashtablezInfoHandle& lhs,
188
                          HashtablezInfoHandle& rhs) {
189
    std::swap(lhs.info_, rhs.info_);
190
  }
191
192
 private:
193
  friend class HashtablezInfoHandlePeer;
194
  HashtablezInfo* info_;
195
};
196
#else
197
// Ensure that when Hashtablez is turned off at compile time, HashtablezInfo can
198
// be removed by the linker, in order to reduce the binary size.
199
class HashtablezInfoHandle {
200
 public:
201
  explicit HashtablezInfoHandle() = default;
202
2
  explicit HashtablezInfoHandle(std::nullptr_t) {}
203
204
0
  inline void Unregister() {}
205
16
  inline bool IsSampled() const { return false; }
206
0
  inline void RecordStorageChanged(size_t /*size*/, size_t /*capacity*/) {}
207
0
  inline void RecordRehash(size_t /*total_probe_length*/) {}
208
0
  inline void RecordReservation(size_t /*target_capacity*/) {}
209
0
  inline void RecordClearedReservation() {}
210
16
  inline void RecordInsert(size_t /*hash*/, size_t /*distance_from_desired*/) {}
211
0
  inline void RecordErase() {}
212
213
  friend inline void swap(HashtablezInfoHandle& /*lhs*/,
214
0
                          HashtablezInfoHandle& /*rhs*/) {}
215
};
216
#endif  // defined(ABSL_INTERNAL_HASHTABLEZ_SAMPLE)
217
218
#if defined(ABSL_INTERNAL_HASHTABLEZ_SAMPLE)
219
extern ABSL_PER_THREAD_TLS_KEYWORD SamplingState global_next_sample;
220
#endif  // defined(ABSL_INTERNAL_HASHTABLEZ_SAMPLE)
221
222
// Returns a sampling handle.
223
inline HashtablezInfoHandle Sample(
224
    ABSL_ATTRIBUTE_UNUSED size_t inline_element_size,
225
    ABSL_ATTRIBUTE_UNUSED size_t key_size,
226
    ABSL_ATTRIBUTE_UNUSED size_t value_size,
227
2
    ABSL_ATTRIBUTE_UNUSED uint16_t soo_capacity) {
228
#if defined(ABSL_INTERNAL_HASHTABLEZ_SAMPLE)
229
  if (ABSL_PREDICT_TRUE(--global_next_sample.next_sample > 0)) {
230
    return HashtablezInfoHandle(nullptr);
231
  }
232
  return HashtablezInfoHandle(SampleSlow(global_next_sample,
233
                                         inline_element_size, key_size,
234
                                         value_size, soo_capacity));
235
#else
236
2
  return HashtablezInfoHandle(nullptr);
237
2
#endif  // !ABSL_PER_THREAD_TLS
238
2
}
239
240
using HashtablezSampler =
241
    ::absl::profiling_internal::SampleRecorder<HashtablezInfo>;
242
243
// Returns a global Sampler.
244
HashtablezSampler& GlobalHashtablezSampler();
245
246
using HashtablezConfigListener = void (*)();
247
void SetHashtablezConfigListener(HashtablezConfigListener l);
248
249
// Enables or disables sampling for Swiss tables.
250
bool IsHashtablezEnabled();
251
void SetHashtablezEnabled(bool enabled);
252
void SetHashtablezEnabledInternal(bool enabled);
253
254
// Sets the rate at which Swiss tables will be sampled.
255
int32_t GetHashtablezSampleParameter();
256
void SetHashtablezSampleParameter(int32_t rate);
257
void SetHashtablezSampleParameterInternal(int32_t rate);
258
259
// Sets a soft max for the number of samples that will be kept.
260
size_t GetHashtablezMaxSamples();
261
void SetHashtablezMaxSamples(size_t max);
262
void SetHashtablezMaxSamplesInternal(size_t max);
263
264
// Configuration override.
265
// This allows process-wide sampling without depending on order of
266
// initialization of static storage duration objects.
267
// The definition of this constant is weak, which allows us to inject a
268
// different value for it at link time.
269
extern "C" bool ABSL_INTERNAL_C_SYMBOL(AbslContainerInternalSampleEverything)();
270
271
}  // namespace container_internal
272
ABSL_NAMESPACE_END
273
}  // namespace absl
274
275
#endif  // ABSL_CONTAINER_INTERNAL_HASHTABLEZ_SAMPLER_H_