summaryrefslogtreecommitdiff
path: root/absl/profiling/internal
diff options
context:
space:
mode:
Diffstat (limited to 'absl/profiling/internal')
-rw-r--r--absl/profiling/internal/exponential_biased.cc93
-rw-r--r--absl/profiling/internal/exponential_biased.h130
-rw-r--r--absl/profiling/internal/exponential_biased_test.cc201
-rw-r--r--absl/profiling/internal/periodic_sampler.cc53
-rw-r--r--absl/profiling/internal/periodic_sampler.h211
-rw-r--r--absl/profiling/internal/periodic_sampler_benchmark.cc79
-rw-r--r--absl/profiling/internal/periodic_sampler_test.cc177
-rw-r--r--absl/profiling/internal/sample_recorder.h245
-rw-r--r--absl/profiling/internal/sample_recorder_test.cc184
9 files changed, 1373 insertions, 0 deletions
diff --git a/absl/profiling/internal/exponential_biased.cc b/absl/profiling/internal/exponential_biased.cc
new file mode 100644
index 00000000..81d9a757
--- /dev/null
+++ b/absl/profiling/internal/exponential_biased.cc
@@ -0,0 +1,93 @@
+// Copyright 2019 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
+//
+// https://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.
+
+#include "absl/profiling/internal/exponential_biased.h"
+
+#include <stdint.h>
+
+#include <algorithm>
+#include <atomic>
+#include <cmath>
+#include <limits>
+
+#include "absl/base/attributes.h"
+#include "absl/base/optimization.h"
+
+namespace absl {
+ABSL_NAMESPACE_BEGIN
+namespace profiling_internal {
+
+// The algorithm generates a random number between 0 and 1 and applies the
+// inverse cumulative distribution function for an exponential. Specifically:
+// Let m be the inverse of the sample period, then the probability
+// distribution function is m*exp(-mx) so the CDF is
+// p = 1 - exp(-mx), so
+// q = 1 - p = exp(-mx)
+// log_e(q) = -mx
+// -log_e(q)/m = x
+// log_2(q) * (-log_e(2) * 1/m) = x
+// In the code, q is actually in the range 1 to 2**26, hence the -26 below
+int64_t ExponentialBiased::GetSkipCount(int64_t mean) {
+ if (ABSL_PREDICT_FALSE(!initialized_)) {
+ Initialize();
+ }
+
+ uint64_t rng = NextRandom(rng_);
+ rng_ = rng;
+
+ // Take the top 26 bits as the random number
+ // (This plus the 1<<58 sampling bound give a max possible step of
+ // 5194297183973780480 bytes.)
+ // The uint32_t cast is to prevent a (hard-to-reproduce) NAN
+ // under piii debug for some binaries.
+ double q = static_cast<uint32_t>(rng >> (kPrngNumBits - 26)) + 1.0;
+ // Put the computed p-value through the CDF of a geometric.
+ double interval = bias_ + (std::log2(q) - 26) * (-std::log(2.0) * mean);
+ // Very large values of interval overflow int64_t. To avoid that, we will
+ // cheat and clamp any huge values to (int64_t max)/2. This is a potential
+ // source of bias, but the mean would need to be such a large value that it's
+ // not likely to come up. For example, with a mean of 1e18, the probability of
+ // hitting this condition is about 1/1000. For a mean of 1e17, standard
+ // calculators claim that this event won't happen.
+ if (interval > static_cast<double>(std::numeric_limits<int64_t>::max() / 2)) {
+ // Assume huge values are bias neutral, retain bias for next call.
+ return std::numeric_limits<int64_t>::max() / 2;
+ }
+ double value = std::rint(interval);
+ bias_ = interval - value;
+ return value;
+}
+
+int64_t ExponentialBiased::GetStride(int64_t mean) {
+ return GetSkipCount(mean - 1) + 1;
+}
+
+void ExponentialBiased::Initialize() {
+ // We don't get well distributed numbers from `this` so we call NextRandom() a
+ // bunch to mush the bits around. We use a global_rand to handle the case
+ // where the same thread (by memory address) gets created and destroyed
+ // repeatedly.
+ ABSL_CONST_INIT static std::atomic<uint32_t> global_rand(0);
+ uint64_t r = reinterpret_cast<uint64_t>(this) +
+ global_rand.fetch_add(1, std::memory_order_relaxed);
+ for (int i = 0; i < 20; ++i) {
+ r = NextRandom(r);
+ }
+ rng_ = r;
+ initialized_ = true;
+}
+
+} // namespace profiling_internal
+ABSL_NAMESPACE_END
+} // namespace absl
diff --git a/absl/profiling/internal/exponential_biased.h b/absl/profiling/internal/exponential_biased.h
new file mode 100644
index 00000000..d31f7782
--- /dev/null
+++ b/absl/profiling/internal/exponential_biased.h
@@ -0,0 +1,130 @@
+// Copyright 2019 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
+//
+// https://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.
+
+#ifndef ABSL_PROFILING_INTERNAL_EXPONENTIAL_BIASED_H_
+#define ABSL_PROFILING_INTERNAL_EXPONENTIAL_BIASED_H_
+
+#include <stdint.h>
+
+#include "absl/base/config.h"
+#include "absl/base/macros.h"
+
+namespace absl {
+ABSL_NAMESPACE_BEGIN
+namespace profiling_internal {
+
+// ExponentialBiased provides a small and fast random number generator for a
+// rounded exponential distribution. This generator manages very little state,
+// and imposes no synchronization overhead. This makes it useful in specialized
+// scenarios requiring minimum overhead, such as stride based periodic sampling.
+//
+// ExponentialBiased provides two closely related functions, GetSkipCount() and
+// GetStride(), both returning a rounded integer defining a number of events
+// required before some event with a given mean probability occurs.
+//
+// The distribution is useful to generate a random wait time or some periodic
+// event with a given mean probability. For example, if an action is supposed to
+// happen on average once every 'N' events, then we can get a random 'stride'
+// counting down how long before the event to happen. For example, if we'd want
+// to sample one in every 1000 'Frobber' calls, our code could look like this:
+//
+// Frobber::Frobber() {
+// stride_ = exponential_biased_.GetStride(1000);
+// }
+//
+// void Frobber::Frob(int arg) {
+// if (--stride == 0) {
+// SampleFrob(arg);
+// stride_ = exponential_biased_.GetStride(1000);
+// }
+// ...
+// }
+//
+// The rounding of the return value creates a bias, especially for smaller means
+// where the distribution of the fraction is not evenly distributed. We correct
+// this bias by tracking the fraction we rounded up or down on each iteration,
+// effectively tracking the distance between the cumulative value, and the
+// rounded cumulative value. For example, given a mean of 2:
+//
+// raw = 1.63076, cumulative = 1.63076, rounded = 2, bias = -0.36923
+// raw = 0.14624, cumulative = 1.77701, rounded = 2, bias = 0.14624
+// raw = 4.93194, cumulative = 6.70895, rounded = 7, bias = -0.06805
+// raw = 0.24206, cumulative = 6.95101, rounded = 7, bias = 0.24206
+// etc...
+//
+// Adjusting with rounding bias is relatively trivial:
+//
+// double value = bias_ + exponential_distribution(mean)();
+// double rounded_value = std::rint(value);
+// bias_ = value - rounded_value;
+// return rounded_value;
+//
+// This class is thread-compatible.
+class ExponentialBiased {
+ public:
+ // The number of bits set by NextRandom.
+ static constexpr int kPrngNumBits = 48;
+
+ // `GetSkipCount()` returns the number of events to skip before some chosen
+ // event happens. For example, randomly tossing a coin, we will on average
+ // throw heads once before we get tails. We can simulate random coin tosses
+ // using GetSkipCount() as:
+ //
+ // ExponentialBiased eb;
+ // for (...) {
+ // int number_of_heads_before_tail = eb.GetSkipCount(1);
+ // for (int flips = 0; flips < number_of_heads_before_tail; ++flips) {
+ // printf("head...");
+ // }
+ // printf("tail\n");
+ // }
+ //
+ int64_t GetSkipCount(int64_t mean);
+
+ // GetStride() returns the number of events required for a specific event to
+ // happen. See the class comments for a usage example. `GetStride()` is
+ // equivalent to `GetSkipCount(mean - 1) + 1`. When to use `GetStride()` or
+ // `GetSkipCount()` depends mostly on what best fits the use case.
+ int64_t GetStride(int64_t mean);
+
+ // Computes a random number in the range [0, 1<<(kPrngNumBits+1) - 1]
+ //
+ // This is public to enable testing.
+ static uint64_t NextRandom(uint64_t rnd);
+
+ private:
+ void Initialize();
+
+ uint64_t rng_{0};
+ double bias_{0};
+ bool initialized_{false};
+};
+
+// Returns the next prng value.
+// pRNG is: aX+b mod c with a = 0x5DEECE66D, b = 0xB, c = 1<<48
+// This is the lrand64 generator.
+inline uint64_t ExponentialBiased::NextRandom(uint64_t rnd) {
+ const uint64_t prng_mult = uint64_t{0x5DEECE66D};
+ const uint64_t prng_add = 0xB;
+ const uint64_t prng_mod_power = 48;
+ const uint64_t prng_mod_mask =
+ ~((~static_cast<uint64_t>(0)) << prng_mod_power);
+ return (prng_mult * rnd + prng_add) & prng_mod_mask;
+}
+
+} // namespace profiling_internal
+ABSL_NAMESPACE_END
+} // namespace absl
+
+#endif // ABSL_PROFILING_INTERNAL_EXPONENTIAL_BIASED_H_
diff --git a/absl/profiling/internal/exponential_biased_test.cc b/absl/profiling/internal/exponential_biased_test.cc
new file mode 100644
index 00000000..6a6c317e
--- /dev/null
+++ b/absl/profiling/internal/exponential_biased_test.cc
@@ -0,0 +1,201 @@
+// Copyright 2019 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
+//
+// https://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.
+
+#include "absl/profiling/internal/exponential_biased.h"
+
+#include <stddef.h>
+
+#include <cmath>
+#include <cstdint>
+#include <vector>
+
+#include "gmock/gmock.h"
+#include "gtest/gtest.h"
+#include "absl/strings/str_cat.h"
+
+using ::testing::Ge;
+
+namespace absl {
+ABSL_NAMESPACE_BEGIN
+namespace profiling_internal {
+namespace {
+
+MATCHER_P2(IsBetween, a, b,
+ absl::StrCat(std::string(negation ? "isn't" : "is"), " between ", a,
+ " and ", b)) {
+ return a <= arg && arg <= b;
+}
+
+// Tests of the quality of the random numbers generated
+// This uses the Anderson Darling test for uniformity.
+// See "Evaluating the Anderson-Darling Distribution" by Marsaglia
+// for details.
+
+// Short cut version of ADinf(z), z>0 (from Marsaglia)
+// This returns the p-value for Anderson Darling statistic in
+// the limit as n-> infinity. For finite n, apply the error fix below.
+double AndersonDarlingInf(double z) {
+ if (z < 2) {
+ return exp(-1.2337141 / z) / sqrt(z) *
+ (2.00012 +
+ (0.247105 -
+ (0.0649821 - (0.0347962 - (0.011672 - 0.00168691 * z) * z) * z) *
+ z) *
+ z);
+ }
+ return exp(
+ -exp(1.0776 -
+ (2.30695 -
+ (0.43424 - (0.082433 - (0.008056 - 0.0003146 * z) * z) * z) * z) *
+ z));
+}
+
+// Corrects the approximation error in AndersonDarlingInf for small values of n
+// Add this to AndersonDarlingInf to get a better approximation
+// (from Marsaglia)
+double AndersonDarlingErrFix(int n, double x) {
+ if (x > 0.8) {
+ return (-130.2137 +
+ (745.2337 -
+ (1705.091 - (1950.646 - (1116.360 - 255.7844 * x) * x) * x) * x) *
+ x) /
+ n;
+ }
+ double cutoff = 0.01265 + 0.1757 / n;
+ if (x < cutoff) {
+ double t = x / cutoff;
+ t = sqrt(t) * (1 - t) * (49 * t - 102);
+ return t * (0.0037 / (n * n) + 0.00078 / n + 0.00006) / n;
+ } else {
+ double t = (x - cutoff) / (0.8 - cutoff);
+ t = -0.00022633 +
+ (6.54034 - (14.6538 - (14.458 - (8.259 - 1.91864 * t) * t) * t) * t) *
+ t;
+ return t * (0.04213 + 0.01365 / n) / n;
+ }
+}
+
+// Returns the AndersonDarling p-value given n and the value of the statistic
+double AndersonDarlingPValue(int n, double z) {
+ double ad = AndersonDarlingInf(z);
+ double errfix = AndersonDarlingErrFix(n, ad);
+ return ad + errfix;
+}
+
+double AndersonDarlingStatistic(const std::vector<double>& random_sample) {
+ int n = random_sample.size();
+ double ad_sum = 0;
+ for (int i = 0; i < n; i++) {
+ ad_sum += (2 * i + 1) *
+ std::log(random_sample[i] * (1 - random_sample[n - 1 - i]));
+ }
+ double ad_statistic = -n - 1 / static_cast<double>(n) * ad_sum;
+ return ad_statistic;
+}
+
+// Tests if the array of doubles is uniformly distributed.
+// Returns the p-value of the Anderson Darling Statistic
+// for the given set of sorted random doubles
+// See "Evaluating the Anderson-Darling Distribution" by
+// Marsaglia and Marsaglia for details.
+double AndersonDarlingTest(const std::vector<double>& random_sample) {
+ double ad_statistic = AndersonDarlingStatistic(random_sample);
+ double p = AndersonDarlingPValue(random_sample.size(), ad_statistic);
+ return p;
+}
+
+TEST(ExponentialBiasedTest, CoinTossDemoWithGetSkipCount) {
+ ExponentialBiased eb;
+ for (int runs = 0; runs < 10; ++runs) {
+ for (int flips = eb.GetSkipCount(1); flips > 0; --flips) {
+ printf("head...");
+ }
+ printf("tail\n");
+ }
+ int heads = 0;
+ for (int i = 0; i < 10000000; i += 1 + eb.GetSkipCount(1)) {
+ ++heads;
+ }
+ printf("Heads = %d (%f%%)\n", heads, 100.0 * heads / 10000000);
+}
+
+TEST(ExponentialBiasedTest, SampleDemoWithStride) {
+ ExponentialBiased eb;
+ int stride = eb.GetStride(10);
+ int samples = 0;
+ for (int i = 0; i < 10000000; ++i) {
+ if (--stride == 0) {
+ ++samples;
+ stride = eb.GetStride(10);
+ }
+ }
+ printf("Samples = %d (%f%%)\n", samples, 100.0 * samples / 10000000);
+}
+
+
+// Testing that NextRandom generates uniform random numbers. Applies the
+// Anderson-Darling test for uniformity
+TEST(ExponentialBiasedTest, TestNextRandom) {
+ for (auto n : std::vector<int>({
+ 10, // Check short-range correlation
+ 100, 1000,
+ 10000 // Make sure there's no systemic error
+ })) {
+ uint64_t x = 1;
+ // This assumes that the prng returns 48 bit numbers
+ uint64_t max_prng_value = static_cast<uint64_t>(1) << 48;
+ // Initialize.
+ for (int i = 1; i <= 20; i++) {
+ x = ExponentialBiased::NextRandom(x);
+ }
+ std::vector<uint64_t> int_random_sample(n);
+ // Collect samples
+ for (int i = 0; i < n; i++) {
+ int_random_sample[i] = x;
+ x = ExponentialBiased::NextRandom(x);
+ }
+ // First sort them...
+ std::sort(int_random_sample.begin(), int_random_sample.end());
+ std::vector<double> random_sample(n);
+ // Convert them to uniform randoms (in the range [0,1])
+ for (int i = 0; i < n; i++) {
+ random_sample[i] =
+ static_cast<double>(int_random_sample[i]) / max_prng_value;
+ }
+ // Now compute the Anderson-Darling statistic
+ double ad_pvalue = AndersonDarlingTest(random_sample);
+ EXPECT_GT(std::min(ad_pvalue, 1 - ad_pvalue), 0.0001)
+ << "prng is not uniform: n = " << n << " p = " << ad_pvalue;
+ }
+}
+
+// The generator needs to be available as a thread_local and as a static
+// variable.
+TEST(ExponentialBiasedTest, InitializationModes) {
+ ABSL_CONST_INIT static ExponentialBiased eb_static;
+ EXPECT_THAT(eb_static.GetSkipCount(2), Ge(0));
+
+#ifdef ABSL_HAVE_THREAD_LOCAL
+ thread_local ExponentialBiased eb_thread;
+ EXPECT_THAT(eb_thread.GetSkipCount(2), Ge(0));
+#endif
+
+ ExponentialBiased eb_stack;
+ EXPECT_THAT(eb_stack.GetSkipCount(2), Ge(0));
+}
+
+} // namespace
+} // namespace profiling_internal
+ABSL_NAMESPACE_END
+} // namespace absl
diff --git a/absl/profiling/internal/periodic_sampler.cc b/absl/profiling/internal/periodic_sampler.cc
new file mode 100644
index 00000000..a738a82c
--- /dev/null
+++ b/absl/profiling/internal/periodic_sampler.cc
@@ -0,0 +1,53 @@
+// Copyright 2019 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
+//
+// https://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.
+
+#include "absl/profiling/internal/periodic_sampler.h"
+
+#include <atomic>
+
+#include "absl/profiling/internal/exponential_biased.h"
+
+namespace absl {
+ABSL_NAMESPACE_BEGIN
+namespace profiling_internal {
+
+int64_t PeriodicSamplerBase::GetExponentialBiased(int period) noexcept {
+ return rng_.GetStride(period);
+}
+
+bool PeriodicSamplerBase::SubtleConfirmSample() noexcept {
+ int current_period = period();
+
+ // Deal with period case 0 (always off) and 1 (always on)
+ if (ABSL_PREDICT_FALSE(current_period < 2)) {
+ stride_ = 0;
+ return current_period == 1;
+ }
+
+ // Check if this is the first call to Sample()
+ if (ABSL_PREDICT_FALSE(stride_ == 1)) {
+ stride_ = static_cast<uint64_t>(-GetExponentialBiased(current_period));
+ if (static_cast<int64_t>(stride_) < -1) {
+ ++stride_;
+ return false;
+ }
+ }
+
+ stride_ = static_cast<uint64_t>(-GetExponentialBiased(current_period));
+ return true;
+}
+
+} // namespace profiling_internal
+ABSL_NAMESPACE_END
+} // namespace absl
diff --git a/absl/profiling/internal/periodic_sampler.h b/absl/profiling/internal/periodic_sampler.h
new file mode 100644
index 00000000..54f0af45
--- /dev/null
+++ b/absl/profiling/internal/periodic_sampler.h
@@ -0,0 +1,211 @@
+// Copyright 2019 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
+//
+// https://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.
+
+#ifndef ABSL_PROFILING_INTERNAL_PERIODIC_SAMPLER_H_
+#define ABSL_PROFILING_INTERNAL_PERIODIC_SAMPLER_H_
+
+#include <stdint.h>
+
+#include <atomic>
+
+#include "absl/base/optimization.h"
+#include "absl/profiling/internal/exponential_biased.h"
+
+namespace absl {
+ABSL_NAMESPACE_BEGIN
+namespace profiling_internal {
+
+// PeriodicSamplerBase provides the basic period sampler implementation.
+//
+// This is the base class for the templated PeriodicSampler class, which holds
+// a global std::atomic value identified by a user defined tag, such that
+// each specific PeriodSampler implementation holds its own global period.
+//
+// PeriodicSamplerBase is thread-compatible except where stated otherwise.
+class PeriodicSamplerBase {
+ public:
+ // PeriodicSamplerBase is trivial / copyable / movable / destructible.
+ PeriodicSamplerBase() = default;
+ PeriodicSamplerBase(PeriodicSamplerBase&&) = default;
+ PeriodicSamplerBase(const PeriodicSamplerBase&) = default;
+
+ // Returns true roughly once every `period` calls. This is established by a
+ // randomly picked `stride` that is counted down on each call to `Sample`.
+ // This stride is picked such that the probability of `Sample()` returning
+ // true is 1 in `period`.
+ inline bool Sample() noexcept;
+
+ // The below methods are intended for optimized use cases where the
+ // size of the inlined fast path code is highly important. Applications
+ // should use the `Sample()` method unless they have proof that their
+ // specific use case requires the optimizations offered by these methods.
+ //
+ // An example of such a use case is SwissTable sampling. All sampling checks
+ // are in inlined SwissTable methods, and the number of call sites is huge.
+ // In this case, the inlined code size added to each translation unit calling
+ // SwissTable methods is non-trivial.
+ //
+ // The `SubtleMaybeSample()` function spuriously returns true even if the
+ // function should not be sampled, applications MUST match each call to
+ // 'SubtleMaybeSample()' returning true with a `SubtleConfirmSample()` call,
+ // and use the result of the latter as the sampling decision.
+ // In other words: the code should logically be equivalent to:
+ //
+ // if (SubtleMaybeSample() && SubtleConfirmSample()) {
+ // // Sample this call
+ // }
+ //
+ // In the 'inline-size' optimized case, the `SubtleConfirmSample()` call can
+ // be placed out of line, for example, the typical use case looks as follows:
+ //
+ // // --- frobber.h -----------
+ // void FrobberSampled();
+ //
+ // inline void FrobberImpl() {
+ // // ...
+ // }
+ //
+ // inline void Frobber() {
+ // if (ABSL_PREDICT_FALSE(sampler.SubtleMaybeSample())) {
+ // FrobberSampled();
+ // } else {
+ // FrobberImpl();
+ // }
+ // }
+ //
+ // // --- frobber.cc -----------
+ // void FrobberSampled() {
+ // if (!sampler.SubtleConfirmSample())) {
+ // // Spurious false positive
+ // FrobberImpl();
+ // return;
+ // }
+ //
+ // // Sampled execution
+ // // ...
+ // }
+ inline bool SubtleMaybeSample() noexcept;
+ bool SubtleConfirmSample() noexcept;
+
+ protected:
+ // We explicitly don't use a virtual destructor as this class is never
+ // virtually destroyed, and it keeps the class trivial, which avoids TLS
+ // prologue and epilogue code for our TLS instances.
+ ~PeriodicSamplerBase() = default;
+
+ // Returns the next stride for our sampler.
+ // This function is virtual for testing purposes only.
+ virtual int64_t GetExponentialBiased(int period) noexcept;
+
+ private:
+ // Returns the current period of this sampler. Thread-safe.
+ virtual int period() const noexcept = 0;
+
+ // Keep and decrement stride_ as an unsigned integer, but compare the value
+ // to zero casted as a signed int. clang and msvc do not create optimum code
+ // if we use signed for the combined decrement and sign comparison.
+ //
+ // Below 3 alternative options, all compiles generate the best code
+ // using the unsigned increment <---> signed int comparison option.
+ //
+ // Option 1:
+ // int64_t stride_;
+ // if (ABSL_PREDICT_TRUE(++stride_ < 0)) { ... }
+ //
+ // GCC x64 (OK) : https://gcc.godbolt.org/z/R5MzzA
+ // GCC ppc (OK) : https://gcc.godbolt.org/z/z7NZAt
+ // Clang x64 (BAD): https://gcc.godbolt.org/z/t4gPsd
+ // ICC x64 (OK) : https://gcc.godbolt.org/z/rE6s8W
+ // MSVC x64 (OK) : https://gcc.godbolt.org/z/ARMXqS
+ //
+ // Option 2:
+ // int64_t stride_ = 0;
+ // if (ABSL_PREDICT_TRUE(--stride_ >= 0)) { ... }
+ //
+ // GCC x64 (OK) : https://gcc.godbolt.org/z/jSQxYK
+ // GCC ppc (OK) : https://gcc.godbolt.org/z/VJdYaA
+ // Clang x64 (BAD): https://gcc.godbolt.org/z/Xm4NjX
+ // ICC x64 (OK) : https://gcc.godbolt.org/z/4snaFd
+ // MSVC x64 (BAD): https://gcc.godbolt.org/z/BgnEKE
+ //
+ // Option 3:
+ // uint64_t stride_;
+ // if (ABSL_PREDICT_TRUE(static_cast<int64_t>(++stride_) < 0)) { ... }
+ //
+ // GCC x64 (OK) : https://gcc.godbolt.org/z/bFbfPy
+ // GCC ppc (OK) : https://gcc.godbolt.org/z/S9KkUE
+ // Clang x64 (OK) : https://gcc.godbolt.org/z/UYzRb4
+ // ICC x64 (OK) : https://gcc.godbolt.org/z/ptTNfD
+ // MSVC x64 (OK) : https://gcc.godbolt.org/z/76j4-5
+ uint64_t stride_ = 0;
+ absl::profiling_internal::ExponentialBiased rng_;
+};
+
+inline bool PeriodicSamplerBase::SubtleMaybeSample() noexcept {
+ // See comments on `stride_` for the unsigned increment / signed compare.
+ if (ABSL_PREDICT_TRUE(static_cast<int64_t>(++stride_) < 0)) {
+ return false;
+ }
+ return true;
+}
+
+inline bool PeriodicSamplerBase::Sample() noexcept {
+ return ABSL_PREDICT_FALSE(SubtleMaybeSample()) ? SubtleConfirmSample()
+ : false;
+}
+
+// PeriodicSampler is a concreted periodic sampler implementation.
+// The user provided Tag identifies the implementation, and is required to
+// isolate the global state of this instance from other instances.
+//
+// Typical use case:
+//
+// struct HashTablezTag {};
+// thread_local PeriodicSampler sampler;
+//
+// void HashTableSamplingLogic(...) {
+// if (sampler.Sample()) {
+// HashTableSlowSamplePath(...);
+// }
+// }
+//
+template <typename Tag, int default_period = 0>
+class PeriodicSampler final : public PeriodicSamplerBase {
+ public:
+ ~PeriodicSampler() = default;
+
+ int period() const noexcept final {
+ return period_.load(std::memory_order_relaxed);
+ }
+
+ // Sets the global period for this sampler. Thread-safe.
+ // Setting a period of 0 disables the sampler, i.e., every call to Sample()
+ // will return false. Setting a period of 1 puts the sampler in 'always on'
+ // mode, i.e., every call to Sample() returns true.
+ static void SetGlobalPeriod(int period) {
+ period_.store(period, std::memory_order_relaxed);
+ }
+
+ private:
+ static std::atomic<int> period_;
+};
+
+template <typename Tag, int default_period>
+std::atomic<int> PeriodicSampler<Tag, default_period>::period_(default_period);
+
+} // namespace profiling_internal
+ABSL_NAMESPACE_END
+} // namespace absl
+
+#endif // ABSL_PROFILING_INTERNAL_PERIODIC_SAMPLER_H_
diff --git a/absl/profiling/internal/periodic_sampler_benchmark.cc b/absl/profiling/internal/periodic_sampler_benchmark.cc
new file mode 100644
index 00000000..8f0e5574
--- /dev/null
+++ b/absl/profiling/internal/periodic_sampler_benchmark.cc
@@ -0,0 +1,79 @@
+// Copyright 2019 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
+//
+// https://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.
+
+#include "absl/profiling/internal/periodic_sampler.h"
+#include "benchmark/benchmark.h"
+
+namespace absl {
+ABSL_NAMESPACE_BEGIN
+namespace profiling_internal {
+namespace {
+
+template <typename Sampler>
+void BM_Sample(Sampler* sampler, benchmark::State& state) {
+ for (auto _ : state) {
+ benchmark::DoNotOptimize(sampler);
+ benchmark::DoNotOptimize(sampler->Sample());
+ }
+}
+
+template <typename Sampler>
+void BM_SampleMinunumInlined(Sampler* sampler, benchmark::State& state) {
+ for (auto _ : state) {
+ benchmark::DoNotOptimize(sampler);
+ if (ABSL_PREDICT_FALSE(sampler->SubtleMaybeSample())) {
+ benchmark::DoNotOptimize(sampler->SubtleConfirmSample());
+ }
+ }
+}
+
+void BM_PeriodicSampler_TinySample(benchmark::State& state) {
+ struct Tag {};
+ PeriodicSampler<Tag, 10> sampler;
+ BM_Sample(&sampler, state);
+}
+BENCHMARK(BM_PeriodicSampler_TinySample);
+
+void BM_PeriodicSampler_ShortSample(benchmark::State& state) {
+ struct Tag {};
+ PeriodicSampler<Tag, 1024> sampler;
+ BM_Sample(&sampler, state);
+}
+BENCHMARK(BM_PeriodicSampler_ShortSample);
+
+void BM_PeriodicSampler_LongSample(benchmark::State& state) {
+ struct Tag {};
+ PeriodicSampler<Tag, 1024 * 1024> sampler;
+ BM_Sample(&sampler, state);
+}
+BENCHMARK(BM_PeriodicSampler_LongSample);
+
+void BM_PeriodicSampler_LongSampleMinunumInlined(benchmark::State& state) {
+ struct Tag {};
+ PeriodicSampler<Tag, 1024 * 1024> sampler;
+ BM_SampleMinunumInlined(&sampler, state);
+}
+BENCHMARK(BM_PeriodicSampler_LongSampleMinunumInlined);
+
+void BM_PeriodicSampler_Disabled(benchmark::State& state) {
+ struct Tag {};
+ PeriodicSampler<Tag, 0> sampler;
+ BM_Sample(&sampler, state);
+}
+BENCHMARK(BM_PeriodicSampler_Disabled);
+
+} // namespace
+} // namespace profiling_internal
+ABSL_NAMESPACE_END
+} // namespace absl
diff --git a/absl/profiling/internal/periodic_sampler_test.cc b/absl/profiling/internal/periodic_sampler_test.cc
new file mode 100644
index 00000000..ef986f38
--- /dev/null
+++ b/absl/profiling/internal/periodic_sampler_test.cc
@@ -0,0 +1,177 @@
+// Copyright 2019 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
+//
+// https://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.
+
+#include "absl/profiling/internal/periodic_sampler.h"
+
+#include <thread> // NOLINT(build/c++11)
+
+#include "gmock/gmock.h"
+#include "gtest/gtest.h"
+#include "absl/base/attributes.h"
+#include "absl/base/macros.h"
+
+namespace absl {
+ABSL_NAMESPACE_BEGIN
+namespace profiling_internal {
+namespace {
+
+using testing::Eq;
+using testing::Return;
+using testing::StrictMock;
+
+class MockPeriodicSampler : public PeriodicSamplerBase {
+ public:
+ virtual ~MockPeriodicSampler() = default;
+
+ MOCK_METHOD(int, period, (), (const, noexcept));
+ MOCK_METHOD(int64_t, GetExponentialBiased, (int), (noexcept));
+};
+
+TEST(PeriodicSamplerBaseTest, Sample) {
+ StrictMock<MockPeriodicSampler> sampler;
+
+ EXPECT_CALL(sampler, period()).Times(3).WillRepeatedly(Return(16));
+ EXPECT_CALL(sampler, GetExponentialBiased(16))
+ .WillOnce(Return(2))
+ .WillOnce(Return(3))
+ .WillOnce(Return(4));
+
+ EXPECT_FALSE(sampler.Sample());
+ EXPECT_TRUE(sampler.Sample());
+
+ EXPECT_FALSE(sampler.Sample());
+ EXPECT_FALSE(sampler.Sample());
+ EXPECT_TRUE(sampler.Sample());
+
+ EXPECT_FALSE(sampler.Sample());
+ EXPECT_FALSE(sampler.Sample());
+ EXPECT_FALSE(sampler.Sample());
+}
+
+TEST(PeriodicSamplerBaseTest, ImmediatelySample) {
+ StrictMock<MockPeriodicSampler> sampler;
+
+ EXPECT_CALL(sampler, period()).Times(2).WillRepeatedly(Return(16));
+ EXPECT_CALL(sampler, GetExponentialBiased(16))
+ .WillOnce(Return(1))
+ .WillOnce(Return(2))
+ .WillOnce(Return(3));
+
+ EXPECT_TRUE(sampler.Sample());
+
+ EXPECT_FALSE(sampler.Sample());
+ EXPECT_TRUE(sampler.Sample());
+
+ EXPECT_FALSE(sampler.Sample());
+ EXPECT_FALSE(sampler.Sample());
+}
+
+TEST(PeriodicSamplerBaseTest, Disabled) {
+ StrictMock<MockPeriodicSampler> sampler;
+
+ EXPECT_CALL(sampler, period()).Times(3).WillRepeatedly(Return(0));
+
+ EXPECT_FALSE(sampler.Sample());
+ EXPECT_FALSE(sampler.Sample());
+ EXPECT_FALSE(sampler.Sample());
+}
+
+TEST(PeriodicSamplerBaseTest, AlwaysOn) {
+ StrictMock<MockPeriodicSampler> sampler;
+
+ EXPECT_CALL(sampler, period()).Times(3).WillRepeatedly(Return(1));
+
+ EXPECT_TRUE(sampler.Sample());
+ EXPECT_TRUE(sampler.Sample());
+ EXPECT_TRUE(sampler.Sample());
+}
+
+TEST(PeriodicSamplerBaseTest, Disable) {
+ StrictMock<MockPeriodicSampler> sampler;
+
+ EXPECT_CALL(sampler, period()).WillOnce(Return(16));
+ EXPECT_CALL(sampler, GetExponentialBiased(16)).WillOnce(Return(3));
+ EXPECT_FALSE(sampler.Sample());
+ EXPECT_FALSE(sampler.Sample());
+
+ EXPECT_CALL(sampler, period()).Times(2).WillRepeatedly(Return(0));
+
+ EXPECT_FALSE(sampler.Sample());
+ EXPECT_FALSE(sampler.Sample());
+}
+
+TEST(PeriodicSamplerBaseTest, Enable) {
+ StrictMock<MockPeriodicSampler> sampler;
+
+ EXPECT_CALL(sampler, period()).WillOnce(Return(0));
+ EXPECT_FALSE(sampler.Sample());
+
+ EXPECT_CALL(sampler, period()).Times(2).WillRepeatedly(Return(16));
+ EXPECT_CALL(sampler, GetExponentialBiased(16))
+ .Times(2)
+ .WillRepeatedly(Return(3));
+
+ EXPECT_FALSE(sampler.Sample());
+ EXPECT_FALSE(sampler.Sample());
+ EXPECT_TRUE(sampler.Sample());
+
+ EXPECT_FALSE(sampler.Sample());
+ EXPECT_FALSE(sampler.Sample());
+}
+
+TEST(PeriodicSamplerTest, ConstructConstInit) {
+ struct Tag {};
+ ABSL_CONST_INIT static PeriodicSampler<Tag> sampler;
+ (void)sampler;
+}
+
+TEST(PeriodicSamplerTest, DefaultPeriod0) {
+ struct Tag {};
+ PeriodicSampler<Tag> sampler;
+ EXPECT_THAT(sampler.period(), Eq(0));
+}
+
+TEST(PeriodicSamplerTest, DefaultPeriod) {
+ struct Tag {};
+ PeriodicSampler<Tag, 100> sampler;
+ EXPECT_THAT(sampler.period(), Eq(100));
+}
+
+TEST(PeriodicSamplerTest, SetGlobalPeriod) {
+ struct Tag1 {};
+ struct Tag2 {};
+ PeriodicSampler<Tag1, 25> sampler1;
+ PeriodicSampler<Tag2, 50> sampler2;
+
+ EXPECT_THAT(sampler1.period(), Eq(25));
+ EXPECT_THAT(sampler2.period(), Eq(50));
+
+ std::thread thread([] {
+ PeriodicSampler<Tag1, 25> sampler1;
+ PeriodicSampler<Tag2, 50> sampler2;
+ EXPECT_THAT(sampler1.period(), Eq(25));
+ EXPECT_THAT(sampler2.period(), Eq(50));
+ sampler1.SetGlobalPeriod(10);
+ sampler2.SetGlobalPeriod(20);
+ });
+ thread.join();
+
+ EXPECT_THAT(sampler1.period(), Eq(10));
+ EXPECT_THAT(sampler2.period(), Eq(20));
+}
+
+} // namespace
+} // namespace profiling_internal
+ABSL_NAMESPACE_END
+} // namespace absl
diff --git a/absl/profiling/internal/sample_recorder.h b/absl/profiling/internal/sample_recorder.h
new file mode 100644
index 00000000..5f65983b
--- /dev/null
+++ b/absl/profiling/internal/sample_recorder.h
@@ -0,0 +1,245 @@
+// 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
+//
+// https://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.
+//
+// -----------------------------------------------------------------------------
+// File: sample_recorder.h
+// -----------------------------------------------------------------------------
+//
+// This header file defines a lock-free linked list for recording samples
+// collected from a random/stochastic process.
+//
+// This utility is internal-only. Use at your own risk.
+
+#ifndef ABSL_PROFILING_INTERNAL_SAMPLE_RECORDER_H_
+#define ABSL_PROFILING_INTERNAL_SAMPLE_RECORDER_H_
+
+#include <atomic>
+#include <cstddef>
+#include <functional>
+
+#include "absl/base/config.h"
+#include "absl/base/thread_annotations.h"
+#include "absl/synchronization/mutex.h"
+#include "absl/time/time.h"
+
+namespace absl {
+ABSL_NAMESPACE_BEGIN
+namespace profiling_internal {
+
+// Sample<T> that has members required for linking samples in the linked list of
+// samples maintained by the SampleRecorder. Type T defines the sampled data.
+template <typename T>
+struct Sample {
+ // Guards the ability to restore the sample to a pristine state. This
+ // prevents races with sampling and resurrecting an object.
+ absl::Mutex init_mu;
+ T* next = nullptr;
+ T* dead ABSL_GUARDED_BY(init_mu) = nullptr;
+ int64_t weight; // How many sampling events were required to sample this one.
+};
+
+// Holds samples and their associated stack traces with a soft limit of
+// `SetHashtablezMaxSamples()`.
+//
+// Thread safe.
+template <typename T>
+class SampleRecorder {
+ public:
+ SampleRecorder();
+ ~SampleRecorder();
+
+ // Registers for sampling. Returns an opaque registration info.
+ template <typename... Targs>
+ T* Register(Targs&&... args);
+
+ // Unregisters the sample.
+ void Unregister(T* sample);
+
+ // The dispose callback will be called on all samples the moment they are
+ // being unregistered. Only affects samples that are unregistered after the
+ // callback has been set.
+ // Returns the previous callback.
+ using DisposeCallback = void (*)(const T&);
+ DisposeCallback SetDisposeCallback(DisposeCallback f);
+
+ // Iterates over all the registered `StackInfo`s. Returning the number of
+ // samples that have been dropped.
+ int64_t Iterate(const std::function<void(const T& stack)>& f);
+
+ int32_t GetMaxSamples() const;
+ void SetMaxSamples(int32_t max);
+
+ private:
+ void PushNew(T* sample);
+ void PushDead(T* sample);
+ template <typename... Targs>
+ T* PopDead(Targs... args);
+
+ std::atomic<size_t> dropped_samples_;
+ std::atomic<size_t> size_estimate_;
+ std::atomic<int32_t> max_samples_{1 << 20};
+
+ // 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<T*> all_;
+ T graveyard_;
+
+ std::atomic<DisposeCallback> dispose_;
+};
+
+template <typename T>
+typename SampleRecorder<T>::DisposeCallback
+SampleRecorder<T>::SetDisposeCallback(DisposeCallback f) {
+ return dispose_.exchange(f, std::memory_order_relaxed);
+}
+
+template <typename T>
+SampleRecorder<T>::SampleRecorder()
+ : dropped_samples_(0), size_estimate_(0), all_(nullptr), dispose_(nullptr) {
+ absl::MutexLock l(&graveyard_.init_mu);
+ graveyard_.dead = &graveyard_;
+}
+
+template <typename T>
+SampleRecorder<T>::~SampleRecorder() {
+ T* s = all_.load(std::memory_order_acquire);
+ while (s != nullptr) {
+ T* next = s->next;
+ delete s;
+ s = next;
+ }
+}
+
+template <typename T>
+void SampleRecorder<T>::PushNew(T* sample) {
+ sample->next = all_.load(std::memory_order_relaxed);
+ while (!all_.compare_exchange_weak(sample->next, sample,
+ std::memory_order_release,
+ std::memory_order_relaxed)) {
+ }
+}
+
+template <typename T>
+void SampleRecorder<T>::PushDead(T* sample) {
+ if (auto* dispose = dispose_.load(std::memory_order_relaxed)) {
+ dispose(*sample);
+ }
+
+ absl::MutexLock graveyard_lock(&graveyard_.init_mu);
+ absl::MutexLock sample_lock(&sample->init_mu);
+ sample->dead = graveyard_.dead;
+ graveyard_.dead = sample;
+}
+
+template <typename T>
+template <typename... Targs>
+T* SampleRecorder<T>::PopDead(Targs... args) {
+ absl::MutexLock graveyard_lock(&graveyard_.init_mu);
+
+ // The list is circular, so eventually it collapses down to
+ // graveyard_.dead == &graveyard_
+ // when it is empty.
+ T* sample = graveyard_.dead;
+ if (sample == &graveyard_) return nullptr;
+
+ absl::MutexLock sample_lock(&sample->init_mu);
+ graveyard_.dead = sample->dead;
+ sample->dead = nullptr;
+ sample->PrepareForSampling(std::forward<Targs>(args)...);
+ return sample;
+}
+
+template <typename T>
+template <typename... Targs>
+T* SampleRecorder<T>::Register(Targs&&... args) {
+ int64_t size = size_estimate_.fetch_add(1, std::memory_order_relaxed);
+ if (size > max_samples_.load(std::memory_order_relaxed)) {
+ size_estimate_.fetch_sub(1, std::memory_order_relaxed);
+ dropped_samples_.fetch_add(1, std::memory_order_relaxed);
+ return nullptr;
+ }
+
+ T* sample = PopDead(args...);
+ if (sample == nullptr) {
+ // Resurrection failed. Hire a new warlock.
+ sample = new T();
+ {
+ absl::MutexLock sample_lock(&sample->init_mu);
+ sample->PrepareForSampling(std::forward<Targs>(args)...);
+ }
+ PushNew(sample);
+ }
+
+ return sample;
+}
+
+template <typename T>
+void SampleRecorder<T>::Unregister(T* sample) {
+ PushDead(sample);
+ size_estimate_.fetch_sub(1, std::memory_order_relaxed);
+}
+
+template <typename T>
+int64_t SampleRecorder<T>::Iterate(
+ const std::function<void(const T& stack)>& f) {
+ T* s = all_.load(std::memory_order_acquire);
+ while (s != nullptr) {
+ absl::MutexLock l(&s->init_mu);
+ if (s->dead == nullptr) {
+ f(*s);
+ }
+ s = s->next;
+ }
+
+ return dropped_samples_.load(std::memory_order_relaxed);
+}
+
+template <typename T>
+void SampleRecorder<T>::SetMaxSamples(int32_t max) {
+ max_samples_.store(max, std::memory_order_release);
+}
+
+template <typename T>
+int32_t SampleRecorder<T>::GetMaxSamples() const {
+ return max_samples_.load(std::memory_order_acquire);
+}
+
+} // namespace profiling_internal
+ABSL_NAMESPACE_END
+} // namespace absl
+
+#endif // ABSL_PROFILING_INTERNAL_SAMPLE_RECORDER_H_
diff --git a/absl/profiling/internal/sample_recorder_test.cc b/absl/profiling/internal/sample_recorder_test.cc
new file mode 100644
index 00000000..3373329a
--- /dev/null
+++ b/absl/profiling/internal/sample_recorder_test.cc
@@ -0,0 +1,184 @@
+// 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
+//
+// https://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.
+
+#include "absl/profiling/internal/sample_recorder.h"
+
+#include <atomic>
+#include <random>
+#include <vector>
+
+#include "gmock/gmock.h"
+#include "absl/base/thread_annotations.h"
+#include "absl/synchronization/internal/thread_pool.h"
+#include "absl/synchronization/mutex.h"
+#include "absl/synchronization/notification.h"
+#include "absl/time/time.h"
+
+namespace absl {
+ABSL_NAMESPACE_BEGIN
+namespace profiling_internal {
+
+namespace {
+using ::absl::synchronization_internal::ThreadPool;
+using ::testing::IsEmpty;
+using ::testing::UnorderedElementsAre;
+
+struct Info : public Sample<Info> {
+ public:
+ void PrepareForSampling(int64_t w) { weight = w; }
+ std::atomic<size_t> size;
+ absl::Time create_time;
+};
+
+std::vector<size_t> GetSizes(SampleRecorder<Info>* s) {
+ std::vector<size_t> res;
+ s->Iterate([&](const Info& info) {
+ res.push_back(info.size.load(std::memory_order_acquire));
+ });
+ return res;
+}
+
+std::vector<int64_t> GetWeights(SampleRecorder<Info>* s) {
+ std::vector<int64_t> res;
+ s->Iterate([&](const Info& info) { res.push_back(info.weight); });
+ return res;
+}
+
+Info* Register(SampleRecorder<Info>* s, int64_t weight, size_t size) {
+ auto* info = s->Register(weight);
+ assert(info != nullptr);
+ info->size.store(size);
+ return info;
+}
+
+TEST(SampleRecorderTest, Registration) {
+ SampleRecorder<Info> sampler;
+ auto* info1 = Register(&sampler, 31, 1);
+ EXPECT_THAT(GetSizes(&sampler), UnorderedElementsAre(1));
+ EXPECT_THAT(GetWeights(&sampler), UnorderedElementsAre(31));
+
+ auto* info2 = Register(&sampler, 32, 2);
+ EXPECT_THAT(GetSizes(&sampler), UnorderedElementsAre(1, 2));
+ info1->size.store(3);
+ EXPECT_THAT(GetSizes(&sampler), UnorderedElementsAre(3, 2));
+ EXPECT_THAT(GetWeights(&sampler), UnorderedElementsAre(31, 32));
+
+ sampler.Unregister(info1);
+ sampler.Unregister(info2);
+}
+
+TEST(SampleRecorderTest, Unregistration) {
+ SampleRecorder<Info> sampler;
+ std::vector<Info*> infos;
+ for (size_t i = 0; i < 3; ++i) {
+ infos.push_back(Register(&sampler, 33 + i, i));
+ }
+ EXPECT_THAT(GetSizes(&sampler), UnorderedElementsAre(0, 1, 2));
+ EXPECT_THAT(GetWeights(&sampler), UnorderedElementsAre(33, 34, 35));
+
+ sampler.Unregister(infos[1]);
+ EXPECT_THAT(GetSizes(&sampler), UnorderedElementsAre(0, 2));
+ EXPECT_THAT(GetWeights(&sampler), UnorderedElementsAre(33, 35));
+
+ infos.push_back(Register(&sampler, 36, 3));
+ infos.push_back(Register(&sampler, 37, 4));
+ EXPECT_THAT(GetSizes(&sampler), UnorderedElementsAre(0, 2, 3, 4));
+ EXPECT_THAT(GetWeights(&sampler), UnorderedElementsAre(33, 35, 36, 37));
+ sampler.Unregister(infos[3]);
+ EXPECT_THAT(GetSizes(&sampler), UnorderedElementsAre(0, 2, 4));
+ EXPECT_THAT(GetWeights(&sampler), UnorderedElementsAre(33, 35, 37));
+
+ sampler.Unregister(infos[0]);
+ sampler.Unregister(infos[2]);
+ sampler.Unregister(infos[4]);
+ EXPECT_THAT(GetSizes(&sampler), IsEmpty());
+}
+
+TEST(SampleRecorderTest, MultiThreaded) {
+ SampleRecorder<Info> sampler;
+ Notification stop;
+ ThreadPool pool(10);
+
+ for (int i = 0; i < 10; ++i) {
+ pool.Schedule([&sampler, &stop, i]() {
+ std::random_device rd;
+ std::mt19937 gen(rd());
+
+ std::vector<Info*> infoz;
+ while (!stop.HasBeenNotified()) {
+ if (infoz.empty()) {
+ infoz.push_back(sampler.Register(i));
+ }
+ switch (std::uniform_int_distribution<>(0, 2)(gen)) {
+ case 0: {
+ infoz.push_back(sampler.Register(i));
+ break;
+ }
+ case 1: {
+ size_t p =
+ std::uniform_int_distribution<>(0, infoz.size() - 1)(gen);
+ Info* info = infoz[p];
+ infoz[p] = infoz.back();
+ infoz.pop_back();
+ EXPECT_EQ(info->weight, i);
+ sampler.Unregister(info);
+ break;
+ }
+ case 2: {
+ absl::Duration oldest = absl::ZeroDuration();
+ sampler.Iterate([&](const Info& info) {
+ oldest = std::max(oldest, absl::Now() - info.create_time);
+ });
+ ASSERT_GE(oldest, absl::ZeroDuration());
+ break;
+ }
+ }
+ }
+ });
+ }
+ // The threads will hammer away. Give it a little bit of time for tsan to
+ // spot errors.
+ absl::SleepFor(absl::Seconds(3));
+ stop.Notify();
+}
+
+TEST(SampleRecorderTest, Callback) {
+ SampleRecorder<Info> sampler;
+
+ auto* info1 = Register(&sampler, 39, 1);
+ auto* info2 = Register(&sampler, 40, 2);
+
+ static const Info* expected;
+
+ auto callback = [](const Info& info) {
+ // We can't use `info` outside of this callback because the object will be
+ // disposed as soon as we return from here.
+ EXPECT_EQ(&info, expected);
+ };
+
+ // Set the callback.
+ EXPECT_EQ(sampler.SetDisposeCallback(callback), nullptr);
+ expected = info1;
+ sampler.Unregister(info1);
+
+ // Unset the callback.
+ EXPECT_EQ(callback, sampler.SetDisposeCallback(nullptr));
+ expected = nullptr; // no more calls.
+ sampler.Unregister(info2);
+}
+
+} // namespace
+} // namespace profiling_internal
+ABSL_NAMESPACE_END
+} // namespace absl
generated by cgit v1.2.3 (git 2.39.1) at 2025-01-13 13:38:48 +0000