summaryrefslogtreecommitdiff
path: root/absl/profiling
diff options
context:
space:
mode:
Diffstat (limited to 'absl/profiling')
-rw-r--r--absl/profiling/BUILD.bazel34
-rw-r--r--absl/profiling/CMakeLists.txt25
-rw-r--r--absl/profiling/internal/sample_recorder.h231
-rw-r--r--absl/profiling/internal/sample_recorder_test.cc171
4 files changed, 461 insertions, 0 deletions
diff --git a/absl/profiling/BUILD.bazel b/absl/profiling/BUILD.bazel
index 10b256d6..5f3a1030 100644
--- a/absl/profiling/BUILD.bazel
+++ b/absl/profiling/BUILD.bazel
@@ -12,6 +12,40 @@
# See the License for the specific language governing permissions and
# limitations under the License.
+load(
+ "//absl:copts/configure_copts.bzl",
+ "ABSL_DEFAULT_COPTS",
+ "ABSL_DEFAULT_LINKOPTS",
+)
+
package(default_visibility = ["//visibility:private"])
licenses(["notice"])
+
+cc_library(
+ name = "sample_recorder",
+ hdrs = ["internal/sample_recorder.h"],
+ copts = ABSL_DEFAULT_COPTS,
+ linkopts = ABSL_DEFAULT_LINKOPTS,
+ visibility = ["//absl:__subpackages__"],
+ deps = [
+ "//absl/base:config",
+ "//absl/base:core_headers",
+ "//absl/synchronization",
+ "//absl/time",
+ ],
+)
+
+cc_test(
+ name = "sample_recorder_test",
+ srcs = ["internal/sample_recorder_test.cc"],
+ linkopts = ABSL_DEFAULT_LINKOPTS,
+ deps = [
+ ":sample_recorder",
+ "//absl/base:core_headers",
+ "//absl/synchronization",
+ "//absl/synchronization:thread_pool",
+ "//absl/time",
+ "@com_google_googletest//:gtest_main",
+ ],
+)
diff --git a/absl/profiling/CMakeLists.txt b/absl/profiling/CMakeLists.txt
index 3c37491e..7b6a7780 100644
--- a/absl/profiling/CMakeLists.txt
+++ b/absl/profiling/CMakeLists.txt
@@ -12,3 +12,28 @@
# See the License for the specific language governing permissions and
# limitations under the License.
+absl_cc_library(
+ NAME
+ sample_recorder
+ HDRS
+ "internal/sample_recorder.h"
+ COPTS
+ ${ABSL_DEFAULT_COPTS}
+ DEPS
+ absl::base
+ absl::synchronization
+)
+
+absl_cc_test(
+ NAME
+ sample_recorder_test
+ SRCS
+ "internal/sample_recorder_test.cc"
+ COPTS
+ ${ABSL_TEST_COPTS}
+ DEPS
+ absl::sample_recorder
+ absl::time
+ GTest::gmock_main
+)
+
diff --git a/absl/profiling/internal/sample_recorder.h b/absl/profiling/internal/sample_recorder.h
new file mode 100644
index 00000000..a257ea5d
--- /dev/null
+++ b/absl/profiling/internal/sample_recorder.h
@@ -0,0 +1,231 @@
+// 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 {
+ public:
+ // 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;
+};
+
+// 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.
+ T* Register();
+
+ // 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);
+
+ void SetMaxSamples(int32_t max);
+
+ private:
+ void PushNew(T* sample);
+ void PushDead(T* sample);
+ T* PopDead();
+
+ 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>
+T* SampleRecorder<T>::PopDead() {
+ 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();
+ return sample;
+}
+
+template <typename T>
+T* SampleRecorder<T>::Register() {
+ 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();
+ if (sample == nullptr) {
+ // Resurrection failed. Hire a new warlock.
+ sample = new T();
+ 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);
+}
+
+} // 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..ec6e0fa2
--- /dev/null
+++ b/absl/profiling/internal/sample_recorder_test.cc
@@ -0,0 +1,171 @@
+// 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() {}
+ 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;
+}
+
+Info* Register(SampleRecorder<Info>* s, size_t size) {
+ auto* info = s->Register();
+ assert(info != nullptr);
+ info->size.store(size);
+ return info;
+}
+
+TEST(SampleRecorderTest, Registration) {
+ SampleRecorder<Info> sampler;
+ auto* info1 = Register(&sampler, 1);
+ EXPECT_THAT(GetSizes(&sampler), UnorderedElementsAre(1));
+
+ auto* info2 = Register(&sampler, 2);
+ EXPECT_THAT(GetSizes(&sampler), UnorderedElementsAre(1, 2));
+ info1->size.store(3);
+ EXPECT_THAT(GetSizes(&sampler), UnorderedElementsAre(3, 2));
+
+ 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, i));
+ }
+ EXPECT_THAT(GetSizes(&sampler), UnorderedElementsAre(0, 1, 2));
+
+ sampler.Unregister(infos[1]);
+ EXPECT_THAT(GetSizes(&sampler), UnorderedElementsAre(0, 2));
+
+ infos.push_back(Register(&sampler, 3));
+ infos.push_back(Register(&sampler, 4));
+ EXPECT_THAT(GetSizes(&sampler), UnorderedElementsAre(0, 2, 3, 4));
+ sampler.Unregister(infos[3]);
+ EXPECT_THAT(GetSizes(&sampler), UnorderedElementsAre(0, 2, 4));
+
+ 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]() {
+ std::random_device rd;
+ std::mt19937 gen(rd());
+
+ std::vector<Info*> infoz;
+ while (!stop.HasBeenNotified()) {
+ if (infoz.empty()) {
+ infoz.push_back(sampler.Register());
+ }
+ switch (std::uniform_int_distribution<>(0, 2)(gen)) {
+ case 0: {
+ infoz.push_back(sampler.Register());
+ 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();
+ 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, 1);
+ auto* info2 = Register(&sampler, 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