diff options
author | Abseil Team <absl-team@google.com> | 2021-09-13 17:04:32 -0700 |
---|---|---|
committer | Derek Mauro <dmauro@google.com> | 2021-09-13 20:07:10 -0400 |
commit | b2dc72c17ac663885b62334d334da9f8970543b5 (patch) | |
tree | 0cb8703b35db8c9cfae226022d7eee9a8277f83f /absl/profiling | |
parent | 669184b4f33421037dae51f87a15794198566295 (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')
-rw-r--r-- | absl/profiling/BUILD.bazel | 34 | ||||
-rw-r--r-- | absl/profiling/CMakeLists.txt | 25 | ||||
-rw-r--r-- | absl/profiling/internal/sample_recorder.h | 231 | ||||
-rw-r--r-- | absl/profiling/internal/sample_recorder_test.cc | 171 |
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 |