summaryrefslogtreecommitdiff
path: root/absl/profiling/internal
diff options
context:
space:
mode:
authorGravatar Abseil Team <absl-team@google.com>2021-09-13 17:04:32 -0700
committerGravatar Derek Mauro <dmauro@google.com>2021-09-13 20:07:10 -0400
commitb2dc72c17ac663885b62334d334da9f8970543b5 (patch)
tree0cb8703b35db8c9cfae226022d7eee9a8277f83f /absl/profiling/internal
parent669184b4f33421037dae51f87a15794198566295 (diff)
Export of internal Abseil changes
-- ca3a0009e675b699b5d6dd41f00ebac0e7d1935c by Derek Mauro <dmauro@google.com>: Internal change PiperOrigin-RevId: 396475923 -- 04d9fff79085bb18612af3da49007907394ae0b6 by Abseil Team <absl-team@google.com>: Move HastablezSampler from container/internal to profiling/internal. PiperOrigin-RevId: 396362093 GitOrigin-RevId: ca3a0009e675b699b5d6dd41f00ebac0e7d1935c Change-Id: I42d6d2944786afa24259fde002fed5e611f4e1f9
Diffstat (limited to 'absl/profiling/internal')
-rw-r--r--absl/profiling/internal/sample_recorder.h231
-rw-r--r--absl/profiling/internal/sample_recorder_test.cc171
2 files changed, 402 insertions, 0 deletions
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