Export of internal Abseil changes -- 341670bce317dd6af8d3c066970230591a47e80c by Martijn Vels <mvels@google.com>: Change GetStack() and GetParentStack() to return absl::Span PiperOrigin-RevId: 368765721 -- 6aaab9536d6957303c7aba100c3afaa6fb0ea2c8 by Martijn Vels <mvels@google.com>: Remove locking from parent stack. This change removes the need to lock all access to `parent_stack' by making the 'copy constructor' logic specify the 'copied from' CordzInfo (where available) to the TrackCord function, after which parent_stack is immutable. PiperOrigin-RevId: 368760630 -- b19e2059cada35a8ede994833018edac94de6ddc by Martijn Vels <mvels@google.com>: Add cordz instrumentation to Cord PiperOrigin-RevId: 368746225 -- 67b8bbf980f0f4e1db79aa32968e9a715a09b51a by Martijn Vels <mvels@google.com>: Create ABSL_INTERNAL_CORDZ_ENABLED define controlling when Cordz code is enabled There are specific builds and condtions under which we don't support cordz sampling, which is per this change represented by ABSL_INTERNAL_CORDZ_ENABLED being defined. PiperOrigin-RevId: 368731603 -- 8cbfe0e3169637a620f4b66ad2bc2ce340879cb0 by Martijn Vels <mvels@google.com>: Add a `rep` property to CordzInfo to be managed by Cord logic. This change adds a `rep` property to CordzInfo, which is intended to be used by collection logic. Mini design: Cord invokes TrackCord() providing the active 'root' cordrep of the newly sampled Cord, returning a CordzInfo with a weak (uncounted) reference to this root. Cord invokes `SetCordRep()` each time the root cordrep of the sampled Cord is updated while holding `mutex()`. Cord must also obtain `mutex()` _before_ removing a reference on the old root. i.e.: Cord must guarantee that the (weak) reference held in CordzInfo is at all times valid. CordzInfo collection code can then safely obtain a (reference counted) rep pointer by adding a reference to `rep_` while holding `mutex()`. This requires only a very brief critical section inside CordzInfo logic, minimizing contention with concurrent Cord updates. Cord code should typically obtain and hold `mutex()` for the entirety of each mutating Cord operation on a sampled cord. As Cord is thread compatible, it never competes on the lock with any other thread. The only possible concurrent access is from Cordz collection code, which should be a relatively rare event. PiperOrigin-RevId: 368673758 -- 1255120dce2bdd6b4205a34a0e555e0b74b6152f by Martijn Vels <mvels@google.com>: Remove 'depth' from active recorded metrics. Going forward we do not 'live' record depth (and size), but will observe these at collection time only. PiperOrigin-RevId: 368636572 -- 83e5146e35f221736b49e9f0a8805f8c159a51db by Martijn Vels <mvels@google.com>: Make cordz targets visible in OSS PiperOrigin-RevId: 368615010 -- dcb16a4f1239151f0a8c70a8cfeb29dabbd113b8 by Martijn Vels <mvels@google.com>: Internal cleanup PiperOrigin-RevId: 368514666 GitOrigin-RevId: 341670bce317dd6af8d3c066970230591a47e80c Change-Id: I94cecfbbd441eb386f99fc5186c468a7a5538862
diff --git a/CMake/AbseilDll.cmake b/CMake/AbseilDll.cmake index 4527ca1..2f2fa13 100644 --- a/CMake/AbseilDll.cmake +++ b/CMake/AbseilDll.cmake
@@ -197,17 +197,26 @@ "strings/cord.h" "strings/escaping.cc" "strings/escaping.h" + "strings/internal/charconv_bigint.cc" + "strings/internal/charconv_bigint.h" + "strings/internal/charconv_parse.cc" + "strings/internal/charconv_parse.h" "strings/internal/cord_internal.cc" "strings/internal/cord_internal.h" "strings/internal/cord_rep_flat.h" "strings/internal/cord_rep_ring.cc" "strings/internal/cord_rep_ring.h" "strings/internal/cord_rep_ring_reader.h" + "strings/internal/cordz_functions.cc" + "strings/internal/cordz_functions.h" + "strings/internal/cordz_handle.cc" + "strings/internal/cordz_handle.h" + "strings/internal/cordz_info.cc" + "strings/internal/cordz_info.h" + "strings/internal/cordz_sample_token.cc" + "strings/internal/cordz_sample_token.h" + "strings/internal/cordz_statistics.h" "strings/internal/cordz_update_tracker.h" - "strings/internal/charconv_bigint.cc" - "strings/internal/charconv_bigint.h" - "strings/internal/charconv_parse.cc" - "strings/internal/charconv_parse.h" "strings/internal/stl_type_traits.h" "strings/internal/string_constant.h" "strings/match.cc"
diff --git a/absl/strings/BUILD.bazel b/absl/strings/BUILD.bazel index 1138516..1306ea6 100644 --- a/absl/strings/BUILD.bazel +++ b/absl/strings/BUILD.bazel
@@ -327,11 +327,15 @@ copts = ABSL_DEFAULT_COPTS, deps = [ ":cord_internal", + ":cordz_functions", + ":cordz_info", + ":cordz_statistics", ":cordz_update_tracker", ":internal", ":str_format", ":strings", "//absl/base", + "//absl/base:config", "//absl/base:core_headers", "//absl/base:endian", "//absl/base:raw_logging_internal", @@ -344,6 +348,138 @@ ) cc_library( + name = "cordz_handle", + srcs = ["internal/cordz_handle.cc"], + hdrs = ["internal/cordz_handle.h"], + copts = ABSL_DEFAULT_COPTS, + deps = [ + "//absl/base:config", + "//absl/base:raw_logging_internal", + "//absl/synchronization", + ], +) + +cc_library( + name = "cordz_info", + srcs = ["internal/cordz_info.cc"], + hdrs = ["internal/cordz_info.h"], + copts = ABSL_DEFAULT_COPTS, + deps = [ + ":cord_internal", + ":cordz_handle", + ":cordz_statistics", + "//absl/base:config", + "//absl/base:core_headers", + "//absl/debugging:stacktrace", + "//absl/synchronization", + "//absl/types:span", + ], +) + +cc_library( + name = "cordz_sample_token", + srcs = ["internal/cordz_sample_token.cc"], + hdrs = ["internal/cordz_sample_token.h"], + copts = ABSL_DEFAULT_COPTS, + deps = [ + ":cordz_handle", + ":cordz_info", + "//absl/base:config", + ], +) + +cc_library( + name = "cordz_functions", + srcs = ["internal/cordz_functions.cc"], + hdrs = ["internal/cordz_functions.h"], + copts = ABSL_DEFAULT_COPTS, + deps = [ + "//absl/base:config", + "//absl/base:core_headers", + "//absl/base:exponential_biased", + "//absl/base:raw_logging_internal", + ], +) + +cc_library( + name = "cordz_statistics", + hdrs = ["internal/cordz_statistics.h"], + copts = ABSL_DEFAULT_COPTS, + deps = [ + "//absl/base:config", + ], +) + +cc_test( + name = "cordz_functions_test", + srcs = [ + "internal/cordz_functions_test.cc", + ], + deps = [ + ":cord_test_helpers", + ":cordz_functions", + "//absl/base:config", + "@com_google_googletest//:gtest_main", + ], +) + +cc_test( + name = "cordz_handle_test", + srcs = [ + "internal/cordz_handle_test.cc", + ], + deps = [ + ":cordz_handle", + "//absl/base:config", + "//absl/memory", + "//absl/random", + "//absl/random:distributions", + "//absl/synchronization", + "//absl/synchronization:thread_pool", + "//absl/time", + "@com_google_googletest//:gtest_main", + ], +) + +cc_test( + name = "cordz_info_test", + srcs = [ + "internal/cordz_info_test.cc", + ], + deps = [ + ":cord_internal", + ":cordz_handle", + ":cordz_info", + ":strings", + "//absl/base:config", + "//absl/debugging:stacktrace", + "//absl/debugging:symbolize", + "//absl/types:span", + "@com_google_googletest//:gtest_main", + ], +) + +cc_test( + name = "cordz_sample_token_test", + srcs = [ + "internal/cordz_sample_token_test.cc", + ], + deps = [ + ":cord_internal", + ":cordz_handle", + ":cordz_info", + ":cordz_sample_token", + "//absl/base:config", + "//absl/memory", + "//absl/random", + "//absl/synchronization", + "//absl/synchronization:thread_pool", + "//absl/time", + "@com_google_googletest//:gtest_main", + ], +) + +cc_library( name = "cord_test_helpers", testonly = 1, hdrs = [
diff --git a/absl/strings/CMakeLists.txt b/absl/strings/CMakeLists.txt index 0d93d5f..044e38b 100644 --- a/absl/strings/CMakeLists.txt +++ b/absl/strings/CMakeLists.txt
@@ -259,7 +259,7 @@ absl_cc_test( NAME str_join_test - SRCS +ss SRCS "str_join_test.cc" COPTS ${ABSL_TEST_COPTS} @@ -605,6 +605,152 @@ absl_cc_library( NAME + cordz_functions + HDRS + "internal/cordz_functions.h" + SRCS + "internal/cordz_functions.cc" + COPTS + ${ABSL_DEFAULT_COPTS} + DEPS + absl::config + absl::core_headers + absl::exponential_biased + absl::raw_logging_internal +) + +absl_cc_test( + NAME + cordz_functions_test + SRCS + "internal/cordz_functions_test.cc" + DEPS + absl::config + absl::cord_test_helpers + absl::cordz_functions + gmock_main +) + +absl_cc_library( + NAME + cordz_statistics + HDRS + "internal/cordz_statistics.h" + COPTS + ${ABSL_DEFAULT_COPTS} + DEPS + absl::config + absl::core_headers + absl::synchronization +) + +absl_cc_library( + NAME + cordz_handle + HDRS + "internal/cordz_handle.h" + SRCS + "internal/cordz_handle.cc" + COPTS + ${ABSL_DEFAULT_COPTS} + DEPS + absl::config + absl::synchronization +) + +absl_cc_test( + NAME + cordz_handle_test + SRCS + "internal/cordz_handle_test.cc" + DEPS + absl::config + absl::cord_test_helpers + absl::cordz_handle + absl::memory + absl::random_random + absl::random_distributions + absl::synchronization + absl::time + gmock_main +) + +absl_cc_library( + NAME + cordz_info + HDRS + "internal/cordz_info.h" + SRCS + "internal/cordz_info.cc" + COPTS + ${ABSL_DEFAULT_COPTS} + DEPS + absl::config + absl::cord_internal + absl::cordz_handle + absl::cordz_statistics + absl::core_headers + absl::span + absl::stacktrace + absl::synchronization +) + +absl_cc_test( + NAME + cordz_info_test + SRCS + "internal/cordz_info_test.cc" + DEPS + absl::config + absl::cord_internal + absl::cord_test_helpers + absl::cordz_handle + absl::cordz_info + absl::span + absl::stacktrace + absl::symbolize + gmock_main +) + +absl_cc_library( + NAME + cordz_sample_token + HDRS + "internal/cordz_sample_token.h" + SRCS + "internal/cordz_sample_token.cc" + COPTS + ${ABSL_DEFAULT_COPTS} + DEPS + absl::config + absl::cordz_handle + absl::cordz_info +) + +absl_cc_test( + NAME + cordz_sample_token_test + SRCS + "internal/cordz_sample_token_test.cc" + COPTS + ${ABSL_DEFAULT_COPTS} + DEPS + absl::config + absl::cord_internal + absl::cordz_handle + absl::cordz_info + absl::cordz_info + absl::cordz_sample_token + absl::memory + absl::random_random + absl::synchronization + absl::thread_pool + absl::time + gmock_main +) + +absl_cc_library( + NAME cord HDRS "cord.h" @@ -616,6 +762,8 @@ absl::base absl::config absl::cord_internal + absl::cordz_functions + absl::cordz_info absl::cordz_update_tracker absl::core_headers absl::endian
diff --git a/absl/strings/cord.cc b/absl/strings/cord.cc index 8f0999f..d33d6a0 100644 --- a/absl/strings/cord.cc +++ b/absl/strings/cord.cc
@@ -38,6 +38,7 @@ #include "absl/strings/internal/cord_internal.h" #include "absl/strings/internal/cord_rep_flat.h" #include "absl/strings/internal/cord_rep_ring.h" +#include "absl/strings/internal/cordz_statistics.h" #include "absl/strings/internal/resize_uninitialized.h" #include "absl/strings/str_cat.h" #include "absl/strings/str_format.h" @@ -426,6 +427,7 @@ CordRep* root = force_tree(max_length); if (PrepareAppendRegion(root, region, size, max_length)) { + UpdateCordzStatistics(); return; } @@ -460,6 +462,7 @@ CordRep* root = force_tree(max_length); if (PrepareAppendRegion(root, region, size, max_length)) { + UpdateCordzStatistics(); return; } @@ -490,6 +493,27 @@ return false; } +void Cord::InlineRep::StartProfiling() { + CordRep* tree = as_tree(); + auto* cordz_info = absl::cord_internal::CordzInfo::TrackCord(tree); + set_cordz_info(cordz_info); + cordz_info->RecordMetrics(size()); +} + +void Cord::InlineRep::StartProfiling(const Cord::InlineRep& src) { + CordRep* tree = as_tree(); + absl::cord_internal::CordzInfo* parent = + src.is_profiled() ? src.cordz_info() : nullptr; + auto* cordz_info = absl::cord_internal::CordzInfo::TrackCord(tree, parent); + set_cordz_info(cordz_info); + cordz_info->RecordMetrics(size()); +} + +void Cord::InlineRep::UpdateCordzStatisticsSlow() { + CordRep* tree = as_tree(); + data_.cordz_info()->RecordMetrics(tree->length); +} + void Cord::InlineRep::AssignSlow(const Cord::InlineRep& src) { UnrefTree(); @@ -497,11 +521,17 @@ if (is_tree()) { CordRep::Ref(tree()); clear_cordz_info(); + if (ABSL_PREDICT_FALSE(should_profile())) { + StartProfiling(src); + } } } void Cord::InlineRep::UnrefTree() { if (is_tree()) { + if (ABSL_PREDICT_FALSE(is_profiled())) { + absl::cord_internal::CordzInfo::UntrackCord(cordz_info()); + } CordRep::Unref(tree()); } } @@ -552,6 +582,9 @@ // The destruction code is separate so that the compiler can determine // that it does not need to call the destructor on a moved-from Cord. void Cord::DestroyCordSlow() { + if (ABSL_PREDICT_FALSE(contents_.is_profiled())) { + absl::cord_internal::CordzInfo::UntrackCord(contents_.cordz_info()); + } if (CordRep* tree = contents_.tree()) { CordRep::Unref(VerifyTree(tree)); } @@ -567,6 +600,10 @@ } Cord& Cord::operator=(absl::string_view src) { + if (ABSL_PREDICT_FALSE(contents_.is_profiled())) { + absl::cord_internal::CordzInfo::UntrackCord(contents_.cordz_info()); + contents_.clear_cordz_info(); + } const char* data = src.data(); size_t length = src.size(); @@ -615,6 +652,7 @@ char* region; if (PrepareAppendRegion(root, ®ion, &appended, src_size)) { memcpy(region, src_data, appended); + UpdateCordzStatistics(); } } else { // Try to fit in the inline buffer if possible.
diff --git a/absl/strings/cord.h b/absl/strings/cord.h index 7ce938c..de1470b 100644 --- a/absl/strings/cord.h +++ b/absl/strings/cord.h
@@ -70,6 +70,7 @@ #include <string> #include <type_traits> +#include "absl/base/config.h" #include "absl/base/internal/endian.h" #include "absl/base/internal/per_thread_tls.h" #include "absl/base/macros.h" @@ -80,6 +81,9 @@ #include "absl/strings/internal/cord_internal.h" #include "absl/strings/internal/cord_rep_ring.h" #include "absl/strings/internal/cord_rep_ring_reader.h" +#include "absl/strings/internal/cordz_functions.h" +#include "absl/strings/internal/cordz_info.h" +#include "absl/strings/internal/cordz_statistics.h" #include "absl/strings/internal/resize_uninitialized.h" #include "absl/strings/internal/string_constant.h" #include "absl/strings/string_view.h" @@ -772,6 +776,20 @@ // Resets the current cordz_info to null / empty. void clear_cordz_info() { data_.clear_cordz_info(); } + // Starts profiling this cord. + void StartProfiling(); + + // Starts profiling this cord which has been copied from `src`. + void StartProfiling(const Cord::InlineRep& src); + + // Returns true if a Cord should be profiled and false otherwise. + static bool should_profile(); + + // Updates the cordz statistics. info may be nullptr if the CordzInfo object + // is unknown. + void UpdateCordzStatistics(); + void UpdateCordzStatisticsSlow(); + private: friend class Cord; @@ -943,6 +961,9 @@ if (is_tree()) { data_.clear_cordz_info(); absl::cord_internal::CordRep::Ref(as_tree()); + if (ABSL_PREDICT_FALSE(should_profile())) { + StartProfiling(src); + } } } @@ -1004,6 +1025,9 @@ inline void Cord::InlineRep::set_tree(absl::cord_internal::CordRep* rep) { if (rep == nullptr) { + if (ABSL_PREDICT_FALSE(is_profiled())) { + absl::cord_internal::CordzInfo::UntrackCord(cordz_info()); + } ResetToEmpty(); } else { if (data_.is_tree()) { @@ -1013,7 +1037,11 @@ } else { // `data_` contains inlined data: initialize data_ to tree value `rep`. data_.make_tree(rep); + if (ABSL_PREDICT_FALSE(should_profile())) { + StartProfiling(); + } } + UpdateCordzStatistics(); } } @@ -1024,9 +1052,13 @@ return; } data_.set_tree(rep); + UpdateCordzStatistics(); } inline absl::cord_internal::CordRep* Cord::InlineRep::clear() { + if (ABSL_PREDICT_FALSE(is_profiled())) { + absl::cord_internal::CordzInfo::UntrackCord(cordz_info()); + } absl::cord_internal::CordRep* result = tree(); ResetToEmpty(); return result; @@ -1039,6 +1071,15 @@ cord_internal::SmallMemmove(dst, data_.as_chars(), n); } +inline ABSL_ATTRIBUTE_ALWAYS_INLINE bool Cord::InlineRep::should_profile() { + return absl::cord_internal::cordz_should_profile(); +} + +inline void Cord::InlineRep::UpdateCordzStatistics() { + if (ABSL_PREDICT_TRUE(!is_profiled())) return; + UpdateCordzStatisticsSlow(); +} + constexpr inline Cord::Cord() noexcept {} template <typename T>
diff --git a/absl/strings/internal/cordz_functions.cc b/absl/strings/internal/cordz_functions.cc new file mode 100644 index 0000000..6ad864f --- /dev/null +++ b/absl/strings/internal/cordz_functions.cc
@@ -0,0 +1,104 @@ +// 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/strings/internal/cordz_functions.h" + +#include <atomic> +#include <cmath> +#include <limits> +#include <random> + +#include "absl/base/attributes.h" +#include "absl/base/config.h" +#include "absl/base/internal/exponential_biased.h" +#include "absl/base/internal/raw_logging.h" + +// TODO(b/162942788): weak 'cordz_disabled' value. +// A strong version is in the 'cordz_disabled_hack_for_odr' library which can +// be linked in to disable cordz at compile time. +extern "C" { +bool absl_internal_cordz_disabled ABSL_ATTRIBUTE_WEAK = false; +} + +namespace absl { +ABSL_NAMESPACE_BEGIN +namespace cord_internal { +namespace { + +// The average interval until the next sample. A value of 0 disables profiling +// while a value of 1 will profile all Cords. +std::atomic<int> g_cordz_mean_interval(50000); + +} // namespace + +#ifdef ABSL_INTERNAL_CORDZ_ENABLED + +ABSL_CONST_INIT thread_local int64_t cordz_next_sample = 0; + +// kIntervalIfDisabled is the number of profile-eligible events need to occur +// before the code will confirm that cordz is still disabled. +constexpr int64_t kIntervalIfDisabled = 1 << 16; + +ABSL_ATTRIBUTE_NOINLINE bool cordz_should_profile_slow() { + // TODO(b/162942788): check if profiling is disabled at compile time. + if (absl_internal_cordz_disabled) { + ABSL_RAW_LOG(WARNING, "Cordz info disabled at compile time"); + // We are permanently disabled: set counter to highest possible value. + cordz_next_sample = std::numeric_limits<int64_t>::max(); + return false; + } + + thread_local absl::base_internal::ExponentialBiased + exponential_biased_generator; + int32_t mean_interval = get_cordz_mean_interval(); + + // Check if we disabled profiling. If so, set the next sample to a "large" + // number to minimize the overhead of the should_profile codepath. + if (mean_interval <= 0) { + cordz_next_sample = kIntervalIfDisabled; + return false; + } + + // Check if we're always sampling. + if (mean_interval == 1) { + cordz_next_sample = 1; + return true; + } + + if (cordz_next_sample <= 0) { + cordz_next_sample = exponential_biased_generator.GetStride(mean_interval); + return true; + } + + --cordz_next_sample; + return false; +} + +void cordz_set_next_sample_for_testing(int64_t next_sample) { + cordz_next_sample = next_sample; +} + +#endif // ABSL_INTERNAL_CORDZ_ENABLED + +int32_t get_cordz_mean_interval() { + return g_cordz_mean_interval.load(std::memory_order_acquire); +} + +void set_cordz_mean_interval(int32_t mean_interval) { + g_cordz_mean_interval.store(mean_interval, std::memory_order_release); +} + +} // namespace cord_internal +ABSL_NAMESPACE_END +} // namespace absl
diff --git a/absl/strings/internal/cordz_functions.h b/absl/strings/internal/cordz_functions.h new file mode 100644 index 0000000..c9ba145 --- /dev/null +++ b/absl/strings/internal/cordz_functions.h
@@ -0,0 +1,85 @@ +// 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_STRINGS_CORDZ_FUNCTIONS_H_ +#define ABSL_STRINGS_CORDZ_FUNCTIONS_H_ + +#include <stdint.h> + +#include "absl/base/attributes.h" +#include "absl/base/config.h" +#include "absl/base/optimization.h" + +namespace absl { +ABSL_NAMESPACE_BEGIN +namespace cord_internal { + +// Returns the current sample rate. This represents the average interval +// between samples. +int32_t get_cordz_mean_interval(); + +// Sets the sample rate with the average interval between samples. +void set_cordz_mean_interval(int32_t mean_interval); + +// Enable cordz unless any of the following applies: +// - no thread local support +// - MSVC build +// - Android build +// - Apple build +// - DLL build +// Hashtablez is turned off completely in opensource builds. +// MSVC's static atomics are dynamically initialized in debug mode, which breaks +// sampling. +#if defined(ABSL_HAVE_THREAD_LOCAL) && !defined(_MSC_VER) && \ + !defined(ABSL_BUILD_DLL) && !defined(ABSL_CONSUME_DLL) && \ + !defined(__ANDROID__) && !defined(__APPLE__) +#define ABSL_INTERNAL_CORDZ_ENABLED 1 +#endif + +#ifdef ABSL_INTERNAL_CORDZ_ENABLED + +// cordz_next_sample is the number of events until the next sample event. If +// the value is 1 or less, the code will check on the next event if cordz is +// enabled, and if so, will sample the Cord. cordz is only enabled when we can +// use thread locals. +ABSL_CONST_INIT extern thread_local int64_t cordz_next_sample; + +// Determines if the next sample should be profiled. If it is, the value pointed +// at by next_sample will be set with the interval until the next sample. +bool cordz_should_profile_slow(); + +// Returns true if the next cord should be sampled. +inline bool cordz_should_profile() { + if (ABSL_PREDICT_TRUE(cordz_next_sample > 1)) { + cordz_next_sample--; + return false; + } + return cordz_should_profile_slow(); +} + +// Sets the interval until the next sample (for testing only) +void cordz_set_next_sample_for_testing(int64_t next_sample); + +#else // ABSL_INTERNAL_CORDZ_ENABLED + +inline bool cordz_should_profile() { return false; } +inline void cordz_set_next_sample_for_testing(int64_t) {} + +#endif // ABSL_INTERNAL_CORDZ_ENABLED + +} // namespace cord_internal +ABSL_NAMESPACE_END +} // namespace absl + +#endif // ABSL_STRINGS_CORDZ_FUNCTIONS_H_
diff --git a/absl/strings/internal/cordz_functions_test.cc b/absl/strings/internal/cordz_functions_test.cc new file mode 100644 index 0000000..f2cefae --- /dev/null +++ b/absl/strings/internal/cordz_functions_test.cc
@@ -0,0 +1,131 @@ +// 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/strings/internal/cordz_functions.h" + +#include "gmock/gmock.h" +#include "gtest/gtest.h" +#include "absl/base/config.h" + +namespace absl { +ABSL_NAMESPACE_BEGIN +namespace cord_internal { +namespace { + +using ::testing::Eq; +using ::testing::Ge; +using ::testing::Le; + +TEST(CordzFunctionsTest, SampleRate) { + int32_t orig_sample_rate = get_cordz_mean_interval(); + int32_t expected_sample_rate = 123; + set_cordz_mean_interval(expected_sample_rate); + EXPECT_THAT(get_cordz_mean_interval(), Eq(expected_sample_rate)); + set_cordz_mean_interval(orig_sample_rate); +} + +// Cordz is disabled when we don't have thread_local. All calls to +// should_profile will return false when cordz is diabled, so we might want to +// avoid those tests. +#ifdef ABSL_INTERNAL_CORDZ_ENABLED + +TEST(CordzFunctionsTest, ShouldProfileDisable) { + int32_t orig_sample_rate = get_cordz_mean_interval(); + + set_cordz_mean_interval(0); + cordz_set_next_sample_for_testing(0); + EXPECT_FALSE(cordz_should_profile()); + // 1 << 16 is from kIntervalIfDisabled in cordz_functions.cc. + EXPECT_THAT(cordz_next_sample, Eq(1 << 16)); + + set_cordz_mean_interval(orig_sample_rate); +} + +TEST(CordzFunctionsTest, ShouldProfileAlways) { + int32_t orig_sample_rate = get_cordz_mean_interval(); + + set_cordz_mean_interval(1); + cordz_set_next_sample_for_testing(1); + EXPECT_TRUE(cordz_should_profile()); + EXPECT_THAT(cordz_next_sample, Le(1)); + + set_cordz_mean_interval(orig_sample_rate); +} + +TEST(CordzFunctionsTest, ShouldProfileRate) { + static constexpr int kDesiredMeanInterval = 1000; + static constexpr int kSamples = 10000; + int32_t orig_sample_rate = get_cordz_mean_interval(); + + set_cordz_mean_interval(kDesiredMeanInterval); + + int64_t sum_of_intervals = 0; + for (int i = 0; i < kSamples; i++) { + // Setting next_sample to 0 will force cordz_should_profile to generate a + // new value for next_sample each iteration. + cordz_set_next_sample_for_testing(0); + cordz_should_profile(); + sum_of_intervals += cordz_next_sample; + } + + // The sum of independent exponential variables is an Erlang distribution, + // which is a gamma distribution where the shape parameter is equal to the + // number of summands. The distribution used for cordz_should_profile is + // actually floor(Exponential(1/mean)) which introduces bias. However, we can + // apply the squint-really-hard correction factor. That is, when mean is + // large, then if we squint really hard the shape of the distribution between + // N and N+1 looks like a uniform distribution. On average, each value for + // next_sample will be about 0.5 lower than we would expect from an + // exponential distribution. This squint-really-hard correction approach won't + // work when mean is smaller than about 10 but works fine when mean is 1000. + // + // We can use R to calculate a confidence interval. This + // shows how to generate a confidence interval with a false positive rate of + // one in a billion. + // + // $ R -q + // > mean = 1000 + // > kSamples = 10000 + // > errorRate = 1e-9 + // > correction = -kSamples / 2 + // > low = qgamma(errorRate/2, kSamples, 1/mean) + correction + // > high = qgamma(1 - errorRate/2, kSamples, 1/mean) + correction + // > low + // [1] 9396115 + // > high + // [1] 10618100 + EXPECT_THAT(sum_of_intervals, Ge(9396115)); + EXPECT_THAT(sum_of_intervals, Le(10618100)); + + set_cordz_mean_interval(orig_sample_rate); +} + +#else // ABSL_INTERNAL_CORDZ_ENABLED + +TEST(CordzFunctionsTest, ShouldProfileDisabled) { + int32_t orig_sample_rate = get_cordz_mean_interval(); + + set_cordz_mean_interval(1); + cordz_set_next_sample_for_testing(0); + EXPECT_FALSE(cordz_should_profile()); + + set_cordz_mean_interval(orig_sample_rate); +} + +#endif // ABSL_INTERNAL_CORDZ_ENABLED + +} // namespace +} // namespace cord_internal +ABSL_NAMESPACE_END +} // namespace absl
diff --git a/absl/strings/internal/cordz_handle.cc b/absl/strings/internal/cordz_handle.cc new file mode 100644 index 0000000..7e82f85 --- /dev/null +++ b/absl/strings/internal/cordz_handle.cc
@@ -0,0 +1,127 @@ +// 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/strings/internal/cordz_handle.h" + +#include <atomic> + +#include "absl/base/internal/raw_logging.h" // For ABSL_RAW_CHECK + +namespace absl { +ABSL_NAMESPACE_BEGIN +namespace cord_internal { + +ABSL_CONST_INIT absl::Mutex CordzHandle::mutex_(absl::kConstInit); +ABSL_CONST_INIT std::atomic<CordzHandle*> CordzHandle::dq_tail_{nullptr}; + +CordzHandle::CordzHandle(bool is_snapshot) : is_snapshot_(is_snapshot) { + if (is_snapshot) { + MutexLock lock(&mutex_); + CordzHandle* dq_tail = dq_tail_.load(std::memory_order_acquire); + if (dq_tail != nullptr) { + dq_prev_ = dq_tail; + dq_tail->dq_next_ = this; + } + dq_tail_.store(this, std::memory_order_release); + } +} + +CordzHandle::~CordzHandle() { + if (is_snapshot_) { + std::vector<CordzHandle*> to_delete; + { + absl::MutexLock lock(&mutex_); + CordzHandle* next = dq_next_; + if (dq_prev_ == nullptr) { + // We were head of the queue, delete every CordzHandle until we reach + // either the end of the list, or a snapshot handle. + while (next && !next->is_snapshot_) { + to_delete.push_back(next); + next = next->dq_next_; + } + } else { + // Another CordzHandle existed before this one, don't delete anything. + dq_prev_->dq_next_ = next; + } + if (next) { + next->dq_prev_ = dq_prev_; + } else { + dq_tail_.store(dq_prev_, std::memory_order_release); + } + } + for (CordzHandle* handle : to_delete) { + delete handle; + } + } +} + +void CordzHandle::Delete(CordzHandle* handle) { + if (handle) { + if (!handle->is_snapshot_ && !UnsafeDeleteQueueEmpty()) { + MutexLock lock(&mutex_); + CordzHandle* dq_tail = dq_tail_.load(std::memory_order_acquire); + if (dq_tail != nullptr) { + handle->dq_prev_ = dq_tail; + dq_tail->dq_next_ = handle; + dq_tail_.store(handle, std::memory_order_release); + return; + } + } + delete handle; + } +} + +std::vector<const CordzHandle*> CordzHandle::DiagnosticsGetDeleteQueue() { + std::vector<const CordzHandle*> handles; + MutexLock lock(&mutex_); + CordzHandle* dq_tail = dq_tail_.load(std::memory_order_acquire); + for (const CordzHandle* p = dq_tail; p; p = p->dq_prev_) { + handles.push_back(p); + } + return handles; +} + +bool CordzHandle::DiagnosticsHandleIsSafeToInspect( + const CordzHandle* handle) const { + if (!is_snapshot_) return false; + if (handle == nullptr) return true; + if (handle->is_snapshot_) return false; + bool snapshot_found = false; + MutexLock lock(&mutex_); + for (const CordzHandle* p = dq_tail_; p; p = p->dq_prev_) { + if (p == handle) return !snapshot_found; + if (p == this) snapshot_found = true; + } + ABSL_ASSERT(snapshot_found); // Assert that 'this' is in delete queue. + return true; +} + +std::vector<const CordzHandle*> +CordzHandle::DiagnosticsGetSafeToInspectDeletedHandles() { + std::vector<const CordzHandle*> handles; + if (!is_snapshot()) { + return handles; + } + + MutexLock lock(&mutex_); + for (const CordzHandle* p = dq_next_; p != nullptr; p = p->dq_next_) { + if (!p->is_snapshot()) { + handles.push_back(p); + } + } + return handles; +} + +} // namespace cord_internal +ABSL_NAMESPACE_END +} // namespace absl
diff --git a/absl/strings/internal/cordz_handle.h b/absl/strings/internal/cordz_handle.h new file mode 100644 index 0000000..0235d4b --- /dev/null +++ b/absl/strings/internal/cordz_handle.h
@@ -0,0 +1,97 @@ +// 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_STRINGS_CORDZ_HANDLE_H_ +#define ABSL_STRINGS_CORDZ_HANDLE_H_ + +#include <atomic> +#include <vector> + +#include "absl/base/config.h" +#include "absl/synchronization/mutex.h" + +namespace absl { +ABSL_NAMESPACE_BEGIN +namespace cord_internal { + +// This base class allows multiple types of object (CordzInfo and +// CordzSampleToken) to exist simultaneously on the delete queue (pointed to by +// global_dq_tail and traversed using dq_prev_ and dq_next_). The +// delete queue guarantees that once a profiler creates a CordzSampleToken and +// has gained visibility into a CordzInfo object, that CordzInfo object will not +// be deleted prematurely. This allows the profiler to inspect all CordzInfo +// objects that are alive without needing to hold a global lock. +class CordzHandle { + public: + CordzHandle() : CordzHandle(false) {} + + bool is_snapshot() const { return is_snapshot_; } + + // Deletes the provided instance, or puts it on the delete queue to be deleted + // once there are no more sample tokens (snapshot) instances potentially + // referencing the instance. `handle` may be null. + static void Delete(CordzHandle* handle); + + // Returns the current entries in the delete queue in LIFO order. + static std::vector<const CordzHandle*> DiagnosticsGetDeleteQueue(); + + // Returns true if the provided handle is nullptr or guarded by this handle. + // Since the CordzSnapshot token is itself a CordzHandle, this method will + // allow tests to check if that token is keeping an arbitrary CordzHandle + // alive. + bool DiagnosticsHandleIsSafeToInspect(const CordzHandle* handle) const; + + // Returns the current entries in the delete queue, in LIFO order, that are + // protected by this. CordzHandle objects are only placed on the delete queue + // after CordzHandle::Delete is called with them as an argument. Only + // CordzHandle objects that are not also CordzSnapshot objects will be + // included in the return vector. For each of the handles in the return + // vector, the earliest that their memory can be freed is when this + // CordzSnapshot object is deleted. + std::vector<const CordzHandle*> DiagnosticsGetSafeToInspectDeletedHandles(); + + protected: + explicit CordzHandle(bool is_snapshot); + virtual ~CordzHandle(); + + private: + // Returns true if the delete queue is empty. This method does not acquire the + // lock, but does a 'load acquire' observation on the delete queue tail. It + // is used inside Delete() to check for the presence of a delete queue without + // holding the lock. The assumption is that the caller is in the state of + // 'being deleted', and can not be newly discovered by a concurrent 'being + // constructed' snapshot instance. Practically, this means that any such + // discovery (`find`, 'first' or 'next', etc) must have proper 'happens before + // / after' semantics and atomic fences. + static bool UnsafeDeleteQueueEmpty() ABSL_NO_THREAD_SAFETY_ANALYSIS { + return dq_tail_.load(std::memory_order_acquire) == nullptr; + } + + const bool is_snapshot_; + static absl::Mutex mutex_; + static std::atomic<CordzHandle*> dq_tail_ ABSL_GUARDED_BY(mutex_); + CordzHandle* dq_prev_ ABSL_GUARDED_BY(mutex_) = nullptr; + CordzHandle* dq_next_ ABSL_GUARDED_BY(mutex_) = nullptr; +}; + +class CordzSnapshot : public CordzHandle { + public: + CordzSnapshot() : CordzHandle(true) {} +}; + +} // namespace cord_internal +ABSL_NAMESPACE_END +} // namespace absl + +#endif // ABSL_STRINGS_CORDZ_HANDLE_H_
diff --git a/absl/strings/internal/cordz_handle_test.cc b/absl/strings/internal/cordz_handle_test.cc new file mode 100644 index 0000000..c04240e --- /dev/null +++ b/absl/strings/internal/cordz_handle_test.cc
@@ -0,0 +1,253 @@ +// 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/strings/internal/cordz_handle.h" + +#include <random> + +#include "gmock/gmock.h" +#include "gtest/gtest.h" +#include "absl/memory/memory.h" +#include "absl/synchronization/internal/thread_pool.h" +#include "absl/synchronization/notification.h" +#include "absl/time/clock.h" +#include "absl/time/time.h" + +namespace absl { +ABSL_NAMESPACE_BEGIN +namespace cord_internal { +namespace { + +using ::testing::ElementsAre; +using ::testing::Gt; +using ::testing::IsEmpty; +using ::testing::SizeIs; + +// Local less verbose helper +std::vector<const CordzHandle*> DeleteQueue() { + return CordzHandle::DiagnosticsGetDeleteQueue(); +} + +struct CordzHandleDeleteTracker : public CordzHandle { + bool* deleted; + explicit CordzHandleDeleteTracker(bool* deleted) : deleted(deleted) {} + ~CordzHandleDeleteTracker() override { *deleted = true; } +}; + +TEST(CordzHandleTest, DeleteQueueIsEmpty) { + EXPECT_THAT(DeleteQueue(), SizeIs(0)); +} + +TEST(CordzHandleTest, CordzHandleCreateDelete) { + bool deleted = false; + auto* handle = new CordzHandleDeleteTracker(&deleted); + EXPECT_FALSE(handle->is_snapshot()); + EXPECT_THAT(DeleteQueue(), SizeIs(0)); + + CordzHandle::Delete(handle); + EXPECT_THAT(DeleteQueue(), SizeIs(0)); + EXPECT_TRUE(deleted); +} + +TEST(CordzHandleTest, CordzSnapshotCreateDelete) { + auto* snapshot = new CordzSnapshot(); + EXPECT_TRUE(snapshot->is_snapshot()); + EXPECT_THAT(DeleteQueue(), ElementsAre(snapshot)); + delete snapshot; + EXPECT_THAT(DeleteQueue(), SizeIs(0)); +} + +TEST(CordzHandleTest, CordzHandleCreateDeleteWithSnapshot) { + bool deleted = false; + auto* snapshot = new CordzSnapshot(); + auto* handle = new CordzHandleDeleteTracker(&deleted); + + CordzHandle::Delete(handle); + EXPECT_THAT(DeleteQueue(), ElementsAre(handle, snapshot)); + EXPECT_FALSE(deleted); + + delete snapshot; + EXPECT_THAT(DeleteQueue(), SizeIs(0)); + EXPECT_TRUE(deleted); +} + +TEST(CordzHandleTest, MultiSnapshot) { + bool deleted[3] = {false, false, false}; + + CordzSnapshot* snapshot[3]; + CordzHandleDeleteTracker* handle[3]; + for (int i = 0; i < 3; ++i) { + snapshot[i] = new CordzSnapshot(); + handle[i] = new CordzHandleDeleteTracker(&deleted[i]); + CordzHandle::Delete(handle[i]); + } + + EXPECT_THAT(DeleteQueue(), ElementsAre(handle[2], snapshot[2], handle[1], + snapshot[1], handle[0], snapshot[0])); + EXPECT_THAT(deleted, ElementsAre(false, false, false)); + + delete snapshot[1]; + EXPECT_THAT(DeleteQueue(), ElementsAre(handle[2], snapshot[2], handle[1], + handle[0], snapshot[0])); + EXPECT_THAT(deleted, ElementsAre(false, false, false)); + + delete snapshot[0]; + EXPECT_THAT(DeleteQueue(), ElementsAre(handle[2], snapshot[2])); + EXPECT_THAT(deleted, ElementsAre(true, true, false)); + + delete snapshot[2]; + EXPECT_THAT(DeleteQueue(), SizeIs(0)); + EXPECT_THAT(deleted, ElementsAre(true, true, deleted)); +} + +TEST(CordzHandleTest, DiagnosticsHandleIsSafeToInspect) { + CordzSnapshot snapshot1; + EXPECT_TRUE(snapshot1.DiagnosticsHandleIsSafeToInspect(nullptr)); + + auto* handle1 = new CordzHandle(); + EXPECT_TRUE(snapshot1.DiagnosticsHandleIsSafeToInspect(handle1)); + + CordzHandle::Delete(handle1); + EXPECT_TRUE(snapshot1.DiagnosticsHandleIsSafeToInspect(handle1)); + + CordzSnapshot snapshot2; + auto* handle2 = new CordzHandle(); + EXPECT_TRUE(snapshot1.DiagnosticsHandleIsSafeToInspect(handle1)); + EXPECT_TRUE(snapshot1.DiagnosticsHandleIsSafeToInspect(handle2)); + EXPECT_FALSE(snapshot2.DiagnosticsHandleIsSafeToInspect(handle1)); + EXPECT_TRUE(snapshot2.DiagnosticsHandleIsSafeToInspect(handle2)); + + CordzHandle::Delete(handle2); + EXPECT_TRUE(snapshot1.DiagnosticsHandleIsSafeToInspect(handle1)); +} + +TEST(CordzHandleTest, DiagnosticsGetSafeToInspectDeletedHandles) { + EXPECT_THAT(DeleteQueue(), IsEmpty()); + + auto* handle = new CordzHandle(); + auto* snapshot1 = new CordzSnapshot(); + + // snapshot1 should be able to see handle. + EXPECT_THAT(DeleteQueue(), ElementsAre(snapshot1)); + EXPECT_TRUE(snapshot1->DiagnosticsHandleIsSafeToInspect(handle)); + EXPECT_THAT(snapshot1->DiagnosticsGetSafeToInspectDeletedHandles(), + IsEmpty()); + + // This handle will be safe to inspect as long as snapshot1 is alive. However, + // since only snapshot1 can prove that it's alive, it will be hidden from + // snapshot2. + CordzHandle::Delete(handle); + + // This snapshot shouldn't be able to see handle because handle was already + // sent to Delete. + auto* snapshot2 = new CordzSnapshot(); + + // DeleteQueue elements are LIFO order. + EXPECT_THAT(DeleteQueue(), ElementsAre(snapshot2, handle, snapshot1)); + + EXPECT_TRUE(snapshot1->DiagnosticsHandleIsSafeToInspect(handle)); + EXPECT_FALSE(snapshot2->DiagnosticsHandleIsSafeToInspect(handle)); + + EXPECT_THAT(snapshot1->DiagnosticsGetSafeToInspectDeletedHandles(), + ElementsAre(handle)); + EXPECT_THAT(snapshot2->DiagnosticsGetSafeToInspectDeletedHandles(), + IsEmpty()); + + CordzHandle::Delete(snapshot1); + EXPECT_THAT(DeleteQueue(), ElementsAre(snapshot2)); + + CordzHandle::Delete(snapshot2); + EXPECT_THAT(DeleteQueue(), IsEmpty()); +} + +// Create and delete CordzHandle and CordzSnapshot objects in multiple threads +// so that tsan has some time to chew on it and look for memory problems. +TEST(CordzHandleTest, MultiThreaded) { + Notification stop; + static constexpr int kNumThreads = 4; + // Keep the number of handles relatively small so that the test will naturally + // transition to an empty delete queue during the test. If there are, say, 100 + // handles, that will virtually never happen. With 10 handles and around 50k + // iterations in each of 4 threads, the delete queue appears to become empty + // around 200 times. + static constexpr int kNumHandles = 10; + + // Each thread is going to pick a random index and atomically swap its + // CordzHandle with one in handles. This way, each thread can avoid + // manipulating a CordzHandle that might be operated upon in another thread. + std::vector<std::atomic<CordzHandle*>> handles(kNumHandles); + + absl::synchronization_internal::ThreadPool pool(kNumThreads); + + for (int i = 0; i < kNumThreads; ++i) { + pool.Schedule([&stop, &handles]() { + std::minstd_rand gen; + std::uniform_int_distribution<int> dist_type(0, 2); + std::uniform_int_distribution<int> dist_handle(0, kNumHandles - 1); + size_t max_safe_to_inspect = 0; + while (!stop.HasBeenNotified()) { + CordzHandle* handle; + switch (dist_type(gen)) { + case 0: + handle = new CordzHandle(); + break; + case 1: + handle = new CordzSnapshot(); + break; + default: + handle = nullptr; + break; + } + CordzHandle* old_handle = handles[dist_handle(gen)].exchange(handle); + if (old_handle != nullptr) { + std::vector<const CordzHandle*> safe_to_inspect = + old_handle->DiagnosticsGetSafeToInspectDeletedHandles(); + for (const CordzHandle* handle : safe_to_inspect) { + // We're in a tight loop, so don't generate too many error messages. + ASSERT_FALSE(handle->is_snapshot()); + } + if (safe_to_inspect.size() > max_safe_to_inspect) { + max_safe_to_inspect = safe_to_inspect.size(); + } + } + CordzHandle::Delete(old_handle); + } + + // Confirm that the test did *something*. This check will be satisfied as + // long as this thread has delete a CordzSnapshot object and a + // non-snapshot CordzHandle was deleted after the CordzSnapshot was + // created. This max_safe_to_inspect count will often reach around 30 + // (assuming 4 threads and 10 slots for live handles). Don't use a strict + // bound to avoid making this test flaky. + EXPECT_THAT(max_safe_to_inspect, Gt(0)); + + // Have each thread attempt to clean up everything. Some thread will be + // the last to reach this cleanup code, and it will be guaranteed to clean + // up everything because nothing remains to create new handles. + for (size_t i = 0; i < handles.size(); i++) { + CordzHandle* handle = handles[i].exchange(nullptr); + CordzHandle::Delete(handle); + } + }); + } + + // The threads will hammer away. Give it a little bit of time for tsan to + // spot errors. + absl::SleepFor(absl::Seconds(3)); + stop.Notify(); +} + +} // namespace +} // namespace cord_internal +ABSL_NAMESPACE_END +} // namespace absl
diff --git a/absl/strings/internal/cordz_info.cc b/absl/strings/internal/cordz_info.cc new file mode 100644 index 0000000..4dec63d --- /dev/null +++ b/absl/strings/internal/cordz_info.cc
@@ -0,0 +1,138 @@ +// 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/strings/internal/cordz_info.h" + +#include "absl/base/config.h" +#include "absl/debugging/stacktrace.h" +#include "absl/strings/internal/cord_internal.h" +#include "absl/strings/internal/cordz_handle.h" +#include "absl/strings/internal/cordz_statistics.h" +#include "absl/synchronization/mutex.h" +#include "absl/types/span.h" + +namespace absl { +ABSL_NAMESPACE_BEGIN +namespace cord_internal { + +constexpr int CordzInfo::kMaxStackDepth; + +ABSL_CONST_INIT std::atomic<CordzInfo*> CordzInfo::ci_head_{nullptr}; +ABSL_CONST_INIT absl::Mutex CordzInfo::ci_mutex_(absl::kConstInit); + +CordzInfo* CordzInfo::Head(const CordzSnapshot& snapshot) { + ABSL_ASSERT(snapshot.is_snapshot()); + ABSL_ASSERT(snapshot.DiagnosticsHandleIsSafeToInspect(ci_head_unsafe())); + return ci_head_unsafe(); +} + +CordzInfo* CordzInfo::Next(const CordzSnapshot& snapshot) const { + ABSL_ASSERT(snapshot.is_snapshot()); + ABSL_ASSERT(snapshot.DiagnosticsHandleIsSafeToInspect(this)); + ABSL_ASSERT(snapshot.DiagnosticsHandleIsSafeToInspect(ci_next_unsafe())); + return ci_next_unsafe(); +} + +CordzInfo* CordzInfo::TrackCord(CordRep* rep, const CordzInfo* src) { + CordzInfo* ci = new CordzInfo(rep); + if (src) { + ci->parent_stack_depth_ = src->stack_depth_; + memcpy(ci->parent_stack_, src->stack_, sizeof(void*) * src->stack_depth_); + } + ci->Track(); + return ci; +} + +CordzInfo* CordzInfo::TrackCord(CordRep* rep) { + return TrackCord(rep, nullptr); +} + +void CordzInfo::UntrackCord(CordzInfo* cordz_info) { + assert(cordz_info); + if (cordz_info) { + cordz_info->Untrack(); + CordzHandle::Delete(cordz_info); + } +} + +CordzInfo::CordzInfo(CordRep* rep) + : rep_(rep), + stack_depth_(absl::GetStackTrace(stack_, /*max_depth=*/kMaxStackDepth, + /*skip_count=*/1)), + parent_stack_depth_(0), + create_time_(absl::Now()) {} + +CordzInfo::~CordzInfo() { + // `rep_` is potentially kept alive if CordzInfo is included + // in a collection snapshot (which should be rare). + if (ABSL_PREDICT_FALSE(rep_)) { + CordRep::Unref(rep_); + } +} + +void CordzInfo::Track() { + absl::MutexLock l(&ci_mutex_); + + CordzInfo* const head = ci_head_.load(std::memory_order_acquire); + if (head != nullptr) { + head->ci_prev_.store(this, std::memory_order_release); + } + ci_next_.store(head, std::memory_order_release); + ci_head_.store(this, std::memory_order_release); +} + +void CordzInfo::Untrack() { + { + // TODO(b/117940323): change this to assuming ownership instead once all + // Cord logic is properly keeping `rep_` in sync with the Cord root rep. + absl::MutexLock lock(&mutex()); + rep_ = nullptr; + } + + absl::MutexLock l(&ci_mutex_); + + CordzInfo* const head = ci_head_.load(std::memory_order_acquire); + CordzInfo* const next = ci_next_.load(std::memory_order_acquire); + CordzInfo* const prev = ci_prev_.load(std::memory_order_acquire); + + if (next) { + ABSL_ASSERT(next->ci_prev_.load(std::memory_order_acquire) == this); + next->ci_prev_.store(prev, std::memory_order_release); + } + if (prev) { + ABSL_ASSERT(head != this); + ABSL_ASSERT(prev->ci_next_.load(std::memory_order_acquire) == this); + prev->ci_next_.store(next, std::memory_order_release); + } else { + ABSL_ASSERT(head == this); + ci_head_.store(next, std::memory_order_release); + } +} + +void CordzInfo::SetCordRep(CordRep* rep) { + mutex().AssertHeld(); + rep_ = rep; +} + +absl::Span<void* const> CordzInfo::GetStack() const { + return absl::MakeConstSpan(stack_, stack_depth_); +} + +absl::Span<void* const> CordzInfo::GetParentStack() const { + return absl::MakeConstSpan(parent_stack_, parent_stack_depth_); +} + +} // namespace cord_internal +ABSL_NAMESPACE_END +} // namespace absl
diff --git a/absl/strings/internal/cordz_info.h b/absl/strings/internal/cordz_info.h new file mode 100644 index 0000000..c1090a1 --- /dev/null +++ b/absl/strings/internal/cordz_info.h
@@ -0,0 +1,168 @@ +// 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_STRINGS_CORDZ_INFO_H_ +#define ABSL_STRINGS_CORDZ_INFO_H_ + +#include <atomic> +#include <cstdint> +#include <functional> + +#include "absl/base/config.h" +#include "absl/base/thread_annotations.h" +#include "absl/strings/internal/cord_internal.h" +#include "absl/strings/internal/cordz_handle.h" +#include "absl/strings/internal/cordz_statistics.h" +#include "absl/synchronization/mutex.h" +#include "absl/types/span.h" + +namespace absl { +ABSL_NAMESPACE_BEGIN +namespace cord_internal { + +// CordzInfo tracks a profiled Cord. Each of these objects can be in two places. +// If a Cord is alive, the CordzInfo will be in the global_cordz_infos map, and +// can also be retrieved via the linked list starting with +// global_cordz_infos_head and continued via the cordz_info_next() method. When +// a Cord has reached the end of its lifespan, the CordzInfo object will be +// migrated out of the global_cordz_infos list and the global_cordz_infos_map, +// and will either be deleted or appended to the global_delete_queue. If it is +// placed on the global_delete_queue, the CordzInfo object will be cleaned in +// the destructor of a CordzSampleToken object. +class CordzInfo : public CordzHandle { + public: + // All profiled Cords should be accompanied by a call to TrackCord. + // TrackCord creates a CordzInfo instance which tracks important metrics of + // the sampled cord. CordzInfo instances are placed in a global list which is + // used to discover and snapshot all actively tracked cords. + // Callers are responsible for calling UntrackCord() before the tracked Cord + // instance is deleted, or to stop tracking the sampled Cord. + static CordzInfo* TrackCord(CordRep* rep); + + // Stops tracking changes for a sampled cord, and deletes the provided info. + // This function must be called before the sampled cord instance is deleted, + // and before the root cordrep of the sampled cord is unreffed. + // This function may extend the lifetime of the cordrep in cases where the + // CordInfo instance is being held by a concurrent collection thread. + static void UntrackCord(CordzInfo* cordz_info); + + // Identical to TrackCord(), except that this function fills the + // 'parent_stack' property of the returned CordzInfo instance from the + // provided `src` instance if `src` is not null. + // This function should be used for sampling 'copy constructed' cords. + static CordzInfo* TrackCord(CordRep* rep, const CordzInfo* src); + + CordzInfo() = delete; + CordzInfo(const CordzInfo&) = delete; + CordzInfo& operator=(const CordzInfo&) = delete; + + // Retrieves the oldest existing CordzInfo. + static CordzInfo* Head(const CordzSnapshot& snapshot); + + // Retrieves the next oldest existing CordzInfo older than 'this' instance. + CordzInfo* Next(const CordzSnapshot& snapshot) const; + + // Returns a reference to the mutex guarding the `rep` property of this + // instance. CordzInfo instances hold a weak reference to the rep pointer of + // sampled cords, and rely on Cord logic to update the rep pointer when the + // underlying root tree or ring of the cord changes. + absl::Mutex& mutex() const { return mutex_; } + + // Updates the `rep' property of this instance. This methods is invoked by + // Cord logic each time the root node of a sampled Cord changes, and before + // the old root reference count is deleted. This guarantees that collection + // code can always safely take a reference on the tracked cord. + // Requires `mutex()` to be held. + // TODO(b/117940323): annotate with ABSL_EXCLUSIVE_LOCKS_REQUIRED once all + // Cord code is in a state where this can be proven true by the compiler. + void SetCordRep(CordRep* rep); + + // Returns the current value of `rep_` for testing purposes only. + CordRep* GetCordRepForTesting() const ABSL_NO_THREAD_SAFETY_ANALYSIS { + return rep_; + } + + // Returns the stack trace for where the cord was first sampled. Cords are + // potentially sampled when they promote from an inlined cord to a tree or + // ring representation, which is not necessarily the location where the cord + // was first created. Some cords are created as inlined cords, and only as + // data is added do they become a non-inlined cord. However, typically the + // location represents reasonably well where the cord is 'created'. + absl::Span<void* const> GetStack() const; + + // Returns the stack trace for a sampled cord's 'parent stack trace'. This + // value may be set if the cord is sampled (promoted) after being created + // from, or being assigned the value of an existing (sampled) cord. + absl::Span<void* const> GetParentStack() const; + + // Retrieve the CordzStatistics associated with this Cord. The statistics are + // only updated when a Cord goes through a mutation, such as an Append or + // RemovePrefix. The refcounts can change due to external events, so the + // reported refcount stats might be incorrect. + CordzStatistics GetCordzStatistics() const { + CordzStatistics stats; + stats.size = size_.load(std::memory_order_relaxed); + return stats; + } + + // Records size metric for this CordzInfo instance. + void RecordMetrics(int64_t size) { + size_.store(size, std::memory_order_relaxed); + } + + private: + static constexpr int kMaxStackDepth = 64; + + explicit CordzInfo(CordRep* tree); + ~CordzInfo() override; + + void Track(); + void Untrack(); + + // 'Unsafe' head/next/prev accessors not requiring the lock being held. + // These are used exclusively for iterations (Head / Next) where we enforce + // a token being held, so reading an 'old' / deleted pointer is fine. + static CordzInfo* ci_head_unsafe() ABSL_NO_THREAD_SAFETY_ANALYSIS { + return ci_head_.load(std::memory_order_acquire); + } + CordzInfo* ci_next_unsafe() const ABSL_NO_THREAD_SAFETY_ANALYSIS { + return ci_next_.load(std::memory_order_acquire); + } + CordzInfo* ci_prev_unsafe() const ABSL_NO_THREAD_SAFETY_ANALYSIS { + return ci_prev_.load(std::memory_order_acquire); + } + + static absl::Mutex ci_mutex_; + static std::atomic<CordzInfo*> ci_head_ ABSL_GUARDED_BY(ci_mutex_); + std::atomic<CordzInfo*> ci_prev_ ABSL_GUARDED_BY(ci_mutex_){nullptr}; + std::atomic<CordzInfo*> ci_next_ ABSL_GUARDED_BY(ci_mutex_){nullptr}; + + mutable absl::Mutex mutex_; + CordRep* rep_ ABSL_GUARDED_BY(mutex()); + + void* stack_[kMaxStackDepth]; + void* parent_stack_[kMaxStackDepth]; + const int stack_depth_; + int parent_stack_depth_; + const absl::Time create_time_; + + // Last recorded size for the cord. + std::atomic<int64_t> size_{0}; +}; + +} // namespace cord_internal +ABSL_NAMESPACE_END +} // namespace absl + +#endif // ABSL_STRINGS_CORDZ_INFO_H_
diff --git a/absl/strings/internal/cordz_info_test.cc b/absl/strings/internal/cordz_info_test.cc new file mode 100644 index 0000000..be20e4a --- /dev/null +++ b/absl/strings/internal/cordz_info_test.cc
@@ -0,0 +1,237 @@ +// 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/strings/internal/cordz_info.h" + +#include <vector> + +#include "gmock/gmock.h" +#include "gtest/gtest.h" +#include "absl/base/config.h" +#include "absl/debugging/stacktrace.h" +#include "absl/debugging/symbolize.h" +#include "absl/strings/internal/cord_rep_flat.h" +#include "absl/strings/internal/cordz_handle.h" +#include "absl/strings/str_cat.h" +#include "absl/types/span.h" + +namespace absl { +ABSL_NAMESPACE_BEGIN +namespace cord_internal { +namespace { + +using ::testing::ElementsAre; +using ::testing::Eq; +using ::testing::HasSubstr; +using ::testing::Ne; + +struct TestCordRep { + CordRepFlat* rep; + + TestCordRep() { + rep = CordRepFlat::New(100); + rep->length = 100; + memset(rep->Data(), 1, 100); + } + ~TestCordRep() { CordRepFlat::Delete(rep); } +}; + +// Local less verbose helper +std::vector<const CordzHandle*> DeleteQueue() { + return CordzHandle::DiagnosticsGetDeleteQueue(); +} + +std::string FormatStack(absl::Span<void* const> raw_stack) { + static constexpr size_t buf_size = 1 << 14; + std::unique_ptr<char[]> buf(new char[buf_size]); + std::string output; + for (void* stackp : raw_stack) { + if (absl::Symbolize(stackp, buf.get(), buf_size)) { + absl::StrAppend(&output, " ", buf.get(), "\n"); + } + } + return output; +} + +TEST(CordzInfoTest, TrackCord) { + TestCordRep rep; + CordzInfo* info = CordzInfo::TrackCord(rep.rep); + ASSERT_THAT(info, Ne(nullptr)); + EXPECT_FALSE(info->is_snapshot()); + EXPECT_THAT(CordzInfo::Head(CordzSnapshot()), Eq(info)); + EXPECT_THAT(info->GetCordRepForTesting(), Eq(rep.rep)); + CordzInfo::UntrackCord(info); +} + +TEST(CordzInfoTest, UntrackCord) { + TestCordRep rep; + CordzInfo* info = CordzInfo::TrackCord(rep.rep); + + CordzSnapshot snapshot; + CordzInfo::UntrackCord(info); + EXPECT_THAT(CordzInfo::Head(CordzSnapshot()), Eq(nullptr)); + EXPECT_THAT(info->GetCordRepForTesting(), Eq(nullptr)); + EXPECT_THAT(DeleteQueue(), ElementsAre(info, &snapshot)); +} + +TEST(CordzInfoTest, SetCordRep) { + TestCordRep rep; + CordzInfo* info = CordzInfo::TrackCord(rep.rep); + + TestCordRep rep2; + { + absl::MutexLock lock(&info->mutex()); + info->SetCordRep(rep2.rep); + } + EXPECT_THAT(info->GetCordRepForTesting(), Eq(rep2.rep)); + + CordzInfo::UntrackCord(info); +} + +#if GTEST_HAS_DEATH_TEST + +TEST(CordzInfoTest, SetCordRepRequiresMutex) { + TestCordRep rep; + CordzInfo* info = CordzInfo::TrackCord(rep.rep); + TestCordRep rep2; + EXPECT_DEATH(info->SetCordRep(rep2.rep), ".*"); + CordzInfo::UntrackCord(info); +} + +#endif // GTEST_HAS_DEATH_TEST + +TEST(CordzInfoTest, TrackUntrackHeadFirstV2) { + TestCordRep rep; + CordzSnapshot snapshot; + EXPECT_THAT(CordzInfo::Head(snapshot), Eq(nullptr)); + + CordzInfo* info1 = CordzInfo::TrackCord(rep.rep); + ASSERT_THAT(CordzInfo::Head(snapshot), Eq(info1)); + EXPECT_THAT(info1->Next(snapshot), Eq(nullptr)); + + CordzInfo* info2 = CordzInfo::TrackCord(rep.rep); + ASSERT_THAT(CordzInfo::Head(snapshot), Eq(info2)); + EXPECT_THAT(info2->Next(snapshot), Eq(info1)); + EXPECT_THAT(info1->Next(snapshot), Eq(nullptr)); + + CordzInfo::UntrackCord(info2); + ASSERT_THAT(CordzInfo::Head(snapshot), Eq(info1)); + EXPECT_THAT(info1->Next(snapshot), Eq(nullptr)); + + CordzInfo::UntrackCord(info1); + ASSERT_THAT(CordzInfo::Head(snapshot), Eq(nullptr)); +} + +TEST(CordzInfoTest, TrackUntrackTailFirstV2) { + TestCordRep rep; + CordzSnapshot snapshot; + EXPECT_THAT(CordzInfo::Head(snapshot), Eq(nullptr)); + + CordzInfo* info1 = CordzInfo::TrackCord(rep.rep); + ASSERT_THAT(CordzInfo::Head(snapshot), Eq(info1)); + EXPECT_THAT(info1->Next(snapshot), Eq(nullptr)); + + CordzInfo* info2 = CordzInfo::TrackCord(rep.rep); + ASSERT_THAT(CordzInfo::Head(snapshot), Eq(info2)); + EXPECT_THAT(info2->Next(snapshot), Eq(info1)); + EXPECT_THAT(info1->Next(snapshot), Eq(nullptr)); + + CordzInfo::UntrackCord(info1); + ASSERT_THAT(CordzInfo::Head(snapshot), Eq(info2)); + EXPECT_THAT(info2->Next(snapshot), Eq(nullptr)); + + CordzInfo::UntrackCord(info2); + ASSERT_THAT(CordzInfo::Head(snapshot), Eq(nullptr)); +} + +TEST(CordzInfoTest, StackV2) { + TestCordRep rep; + // kMaxStackDepth is intentionally less than 64 (which is the max depth that + // Cordz will record) because if the actual stack depth is over 64 + // (which it is on Apple platforms) then the expected_stack will end up + // catching a few frames at the end that the actual_stack didn't get and + // it will no longer be subset. At the time of this writing 58 is the max + // that will allow this test to pass (with a minimum os version of iOS 9), so + // rounded down to 50 to hopefully not run into this in the future if Apple + // makes small modifications to its testing stack. 50 is sufficient to prove + // that we got a decent stack. + static constexpr int kMaxStackDepth = 50; + CordzInfo* info = CordzInfo::TrackCord(rep.rep); + std::vector<void*> local_stack; + local_stack.resize(kMaxStackDepth); + // In some environments we don't get stack traces. For example in Android + // absl::GetStackTrace will return 0 indicating it didn't find any stack. The + // resultant formatted stack will be "", but that still equals the stack + // recorded in CordzInfo, which is also empty. The skip_count is 1 so that the + // line number of the current stack isn't included in the HasSubstr check. + local_stack.resize(absl::GetStackTrace(local_stack.data(), kMaxStackDepth, + /*skip_count=*/1)); + + std::string got_stack = FormatStack(info->GetStack()); + std::string expected_stack = FormatStack(local_stack); + // If TrackCord is inlined, got_stack should match expected_stack. If it isn't + // inlined, got_stack should include an additional frame not present in + // expected_stack. Either way, expected_stack should be a substring of + // got_stack. + EXPECT_THAT(got_stack, HasSubstr(expected_stack)); + + CordzInfo::UntrackCord(info); +} + +// Local helper functions to get different stacks for child and parent. +CordzInfo* TrackChildCord(CordRep* rep, const CordzInfo* parent) { + return CordzInfo::TrackCord(rep, parent); +} +CordzInfo* TrackParentCord(CordRep* rep) { + return CordzInfo::TrackCord(rep); +} + +TEST(CordzInfoTest, ParentStackV2) { + TestCordRep rep; + CordzInfo* info_parent = TrackParentCord(rep.rep); + CordzInfo* info_child = TrackChildCord(rep.rep, info_parent); + + std::string stack = FormatStack(info_parent->GetStack()); + std::string parent_stack = FormatStack(info_child->GetParentStack()); + EXPECT_THAT(stack, Eq(parent_stack)); + + CordzInfo::UntrackCord(info_parent); + CordzInfo::UntrackCord(info_child); +} + +TEST(CordzInfoTest, ParentStackEmpty) { + TestCordRep rep; + CordzInfo* info = TrackChildCord(rep.rep, nullptr); + EXPECT_TRUE(info->GetParentStack().empty()); + CordzInfo::UntrackCord(info); +} + +TEST(CordzInfoTest, CordzStatisticsV2) { + TestCordRep rep; + CordzInfo* info = TrackParentCord(rep.rep); + + CordzStatistics expected; + expected.size = 100; + info->RecordMetrics(expected.size); + + CordzStatistics actual = info->GetCordzStatistics(); + EXPECT_EQ(actual.size, expected.size); + + CordzInfo::UntrackCord(info); +} + +} // namespace +} // namespace cord_internal +ABSL_NAMESPACE_END +} // namespace absl
diff --git a/absl/strings/internal/cordz_sample_token.cc b/absl/strings/internal/cordz_sample_token.cc new file mode 100644 index 0000000..ba1270d --- /dev/null +++ b/absl/strings/internal/cordz_sample_token.cc
@@ -0,0 +1,64 @@ +// 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/strings/internal/cordz_sample_token.h" + +#include "absl/base/config.h" +#include "absl/strings/internal/cordz_handle.h" +#include "absl/strings/internal/cordz_info.h" + +namespace absl { +ABSL_NAMESPACE_BEGIN +namespace cord_internal { + +CordzSampleToken::Iterator& CordzSampleToken::Iterator::operator++() { + if (current_) { + current_ = current_->Next(*token_); + } + return *this; +} + +CordzSampleToken::Iterator CordzSampleToken::Iterator::operator++(int) { + Iterator it(*this); + operator++(); + return it; +} + +bool operator==(const CordzSampleToken::Iterator& lhs, + const CordzSampleToken::Iterator& rhs) { + return lhs.current_ == rhs.current_ && + (lhs.current_ == nullptr || lhs.token_ == rhs.token_); +} + +bool operator!=(const CordzSampleToken::Iterator& lhs, + const CordzSampleToken::Iterator& rhs) { + return !(lhs == rhs); +} + +CordzSampleToken::Iterator::reference CordzSampleToken::Iterator::operator*() + const { + return *current_; +} + +CordzSampleToken::Iterator::pointer CordzSampleToken::Iterator::operator->() + const { + return current_; +} + +CordzSampleToken::Iterator::Iterator(const CordzSampleToken* token) + : token_(token), current_(CordzInfo::Head(*token)) {} + +} // namespace cord_internal +ABSL_NAMESPACE_END +} // namespace absl
diff --git a/absl/strings/internal/cordz_sample_token.h b/absl/strings/internal/cordz_sample_token.h new file mode 100644 index 0000000..28a1d70 --- /dev/null +++ b/absl/strings/internal/cordz_sample_token.h
@@ -0,0 +1,97 @@ +// 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/base/config.h" +#include "absl/strings/internal/cordz_handle.h" +#include "absl/strings/internal/cordz_info.h" + +#ifndef ABSL_STRINGS_CORDZ_SAMPLE_TOKEN_H_ +#define ABSL_STRINGS_CORDZ_SAMPLE_TOKEN_H_ + +namespace absl { +ABSL_NAMESPACE_BEGIN +namespace cord_internal { + +// The existence of a CordzSampleToken guarantees that a reader can traverse the +// global_cordz_infos_head linked-list without needing to hold a mutex. When a +// CordzSampleToken exists, all CordzInfo objects that would be destroyed are +// instead appended to a deletion queue. When the CordzSampleToken is destroyed, +// it will also clean up any of these CordzInfo objects. +// +// E.g., ST are CordzSampleToken objects and CH are CordzHandle objects. +// ST1 <- CH1 <- CH2 <- ST2 <- CH3 <- global_delete_queue_tail +// +// This list tracks that CH1 and CH2 were created after ST1, so the thread +// holding ST1 might have a referece to CH1, CH2, ST2, and CH3. However, ST2 was +// created later, so the thread holding the ST2 token cannot have a reference to +// ST1, CH1, or CH2. If ST1 is cleaned up first, that thread will delete ST1, +// CH1, and CH2. If instead ST2 is cleaned up first, that thread will only +// delete ST2. +// +// If ST1 is cleaned up first, the new list will be: +// ST2 <- CH3 <- global_delete_queue_tail +// +// If ST2 is cleaned up first, the new list will be: +// ST1 <- CH1 <- CH2 <- CH3 <- global_delete_queue_tail +// +// All new CordzHandle objects are appended to the list, so if a new thread +// comes along before either ST1 or ST2 are cleaned up, the new list will be: +// ST1 <- CH1 <- CH2 <- ST2 <- CH3 <- ST3 <- global_delete_queue_tail +// +// A thread must hold the global_delete_queue_mu mutex whenever it's altering +// this list. +// +// It is safe for thread that holds a CordzSampleToken to read +// global_cordz_infos at any time since the objects it is able to retrieve will +// not be deleted while the CordzSampleToken exists. +class CordzSampleToken : public CordzSnapshot { + public: + class Iterator { + public: + using iterator_category = std::input_iterator_tag; + using value_type = const CordzInfo&; + using difference_type = ptrdiff_t; + using pointer = const CordzInfo*; + using reference = value_type; + + Iterator() = default; + + Iterator& operator++(); + Iterator operator++(int); + friend bool operator==(const Iterator& lhs, const Iterator& rhs); + friend bool operator!=(const Iterator& lhs, const Iterator& rhs); + reference operator*() const; + pointer operator->() const; + + private: + friend class CordzSampleToken; + explicit Iterator(const CordzSampleToken* token); + + const CordzSampleToken* token_ = nullptr; + pointer current_ = nullptr; + }; + + CordzSampleToken() = default; + CordzSampleToken(const CordzSampleToken&) = delete; + CordzSampleToken& operator=(const CordzSampleToken&) = delete; + + Iterator begin() { return Iterator(this); } + Iterator end() { return Iterator(); } +}; + +} // namespace cord_internal +ABSL_NAMESPACE_END +} // namespace absl + +#endif // ABSL_STRINGS_CORDZ_SAMPLE_TOKEN_H_
diff --git a/absl/strings/internal/cordz_sample_token_test.cc b/absl/strings/internal/cordz_sample_token_test.cc new file mode 100644 index 0000000..8c05264 --- /dev/null +++ b/absl/strings/internal/cordz_sample_token_test.cc
@@ -0,0 +1,209 @@ +// 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/strings/internal/cordz_sample_token.h" + +#include "gmock/gmock.h" +#include "gtest/gtest.h" +#include "absl/memory/memory.h" +#include "absl/random/random.h" +#include "absl/strings/internal/cord_rep_flat.h" +#include "absl/strings/internal/cordz_handle.h" +#include "absl/strings/internal/cordz_info.h" +#include "absl/synchronization/internal/thread_pool.h" +#include "absl/synchronization/notification.h" +#include "absl/time/clock.h" +#include "absl/time/time.h" + +namespace absl { +ABSL_NAMESPACE_BEGIN +namespace cord_internal { +namespace { + +using ::testing::ElementsAre; +using ::testing::Eq; +using ::testing::Ne; + +struct TestCordRep { + CordRepFlat* rep; + + TestCordRep() { + rep = CordRepFlat::New(100); + rep->length = 100; + memset(rep->Data(), 1, 100); + } + ~TestCordRep() { CordRepFlat::Delete(rep); } +}; + +TEST(CordzSampleTokenTest, IteratorTraits) { + static_assert(std::is_copy_constructible<CordzSampleToken::Iterator>::value, + ""); + static_assert(std::is_copy_assignable<CordzSampleToken::Iterator>::value, ""); + static_assert(std::is_move_constructible<CordzSampleToken::Iterator>::value, + ""); + static_assert(std::is_move_assignable<CordzSampleToken::Iterator>::value, ""); + static_assert( + std::is_same< + std::iterator_traits<CordzSampleToken::Iterator>::iterator_category, + std::input_iterator_tag>::value, + ""); + static_assert( + std::is_same<std::iterator_traits<CordzSampleToken::Iterator>::value_type, + const CordzInfo&>::value, + ""); + static_assert( + std::is_same< + std::iterator_traits<CordzSampleToken::Iterator>::difference_type, + ptrdiff_t>::value, + ""); + static_assert( + std::is_same<std::iterator_traits<CordzSampleToken::Iterator>::pointer, + const CordzInfo*>::value, + ""); + static_assert( + std::is_same<std::iterator_traits<CordzSampleToken::Iterator>::reference, + const CordzInfo&>::value, + ""); +} + +TEST(CordzSampleTokenTest, IteratorEmpty) { + CordzSampleToken token; + EXPECT_THAT(token.begin(), Eq(token.end())); +} + +TEST(CordzSampleTokenTest, Iterator) { + TestCordRep rep1; + TestCordRep rep2; + TestCordRep rep3; + CordzInfo* info1 = CordzInfo::TrackCord(rep1.rep); + CordzInfo* info2 = CordzInfo::TrackCord(rep2.rep); + CordzInfo* info3 = CordzInfo::TrackCord(rep3.rep); + + CordzSampleToken token; + std::vector<const CordzInfo*> found; + for (const CordzInfo& cord_info : token) { + found.push_back(&cord_info); + } + + EXPECT_THAT(found, ElementsAre(info3, info2, info1)); + + CordzInfo::UntrackCord(info1); + CordzInfo::UntrackCord(info2); + CordzInfo::UntrackCord(info3); +} + +TEST(CordzSampleTokenTest, IteratorEquality) { + TestCordRep rep1; + TestCordRep rep2; + TestCordRep rep3; + CordzInfo* info1 = CordzInfo::TrackCord(rep1.rep); + + CordzSampleToken token1; + // lhs starts with the CordzInfo corresponding to cord1 at the head. + CordzSampleToken::Iterator lhs = token1.begin(); + + CordzInfo* info2 = CordzInfo::TrackCord(rep2.rep); + + CordzSampleToken token2; + // rhs starts with the CordzInfo corresponding to cord2 at the head. + CordzSampleToken::Iterator rhs = token2.begin(); + + CordzInfo* info3 = CordzInfo::TrackCord(rep3.rep); + + // lhs is on cord1 while rhs is on cord2. + EXPECT_THAT(lhs, Ne(rhs)); + + rhs++; + // lhs and rhs are both on cord1, but they didn't come from the same + // CordzSampleToken. + EXPECT_THAT(lhs, Ne(rhs)); + + lhs++; + rhs++; + // Both lhs and rhs are done, so they are on nullptr. + EXPECT_THAT(lhs, Eq(rhs)); + + CordzInfo::UntrackCord(info1); + CordzInfo::UntrackCord(info2); + CordzInfo::UntrackCord(info3); +} + +TEST(CordzSampleTokenTest, MultiThreaded) { + Notification stop; + static constexpr int kNumThreads = 4; + static constexpr int kNumCords = 3; + static constexpr int kNumTokens = 3; + absl::synchronization_internal::ThreadPool pool(kNumThreads); + + for (int i = 0; i < kNumThreads; ++i) { + pool.Schedule([&stop]() { + absl::BitGen gen; + TestCordRep reps[kNumCords]; + CordzInfo* infos[kNumCords] = {nullptr}; + std::vector<std::unique_ptr<CordzSampleToken>> tokens; + tokens.resize(kNumTokens); + + while (!stop.HasBeenNotified()) { + // Randomly perform one of five actions: + // 1) Untrack + // 2) Track + // 3) Iterate over Cords visible to a token. + // 4) Unsample + // 5) Sample + int index = absl::Uniform(gen, 0, kNumCords); + if (absl::Bernoulli(gen, 0.5)) { + // Track/untrack. + if (infos[index]) { + // 1) Untrack + CordzInfo::UntrackCord(infos[index]); + infos[index] = nullptr; + } else { + // 2) Track + infos[index] = CordzInfo::TrackCord(reps[index].rep); + } + } else { + if (tokens[index]) { + if (absl::Bernoulli(gen, 0.5)) { + // 3) Iterate over Cords visible to a token. + for (const CordzInfo& info : *tokens[index]) { + // This is trivial work to allow us to compile the loop. + EXPECT_THAT(info.Next(*tokens[index]), Ne(&info)); + } + } else { + // 4) Unsample + tokens[index].reset(); + } + } else { + // 5) Sample + tokens[index] = absl::make_unique<CordzSampleToken>(); + } + } + } + for (CordzInfo* info : infos) { + if (info != nullptr) { + CordzInfo::UntrackCord(info); + } + } + }); + } + // The threads will hammer away. Give it a little bit of time for tsan to + // spot errors. + absl::SleepFor(absl::Seconds(3)); + stop.Notify(); +} + +} // namespace +} // namespace cord_internal +ABSL_NAMESPACE_END +} // namespace absl
diff --git a/absl/strings/internal/cordz_statistics.h b/absl/strings/internal/cordz_statistics.h new file mode 100644 index 0000000..ce7c39a --- /dev/null +++ b/absl/strings/internal/cordz_statistics.h
@@ -0,0 +1,55 @@ +// 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_STRINGS_INTERNAL_CORDZ_STATISTICS_H_ +#define ABSL_STRINGS_INTERNAL_CORDZ_STATISTICS_H_ + +#include <cstdint> + +#include "absl/base/config.h" + +namespace absl { +ABSL_NAMESPACE_BEGIN +namespace cord_internal { + +// CordzStatistics captures some meta information about a Cord's shape. +struct CordzStatistics { + // The size of the cord in bytes. This matches the result of Cord::size(). + int64_t size = 0; + + // The estimated memory used by the sampled cord. This value matches the + // value as reported by Cord::EstimatedMemoryUsage(). + // A value of 0 implies the property has not been recorded. + int64_t estimated_memory_usage = 0; + + // The effective memory used by the sampled cord, inversely weighted by the + // effective indegree of each allocated node. This is a representation of the + // fair share of memory usage that should be attributed to the sampled cord. + // This value is more useful for cases where one or more nodes are referenced + // by multiple Cord instances, and for cases where a Cord includes the same + // node multiple times (either directly or indirectly). + // A value of 0 implies the property has not been recorded. + int64_t estimated_fair_share_memory_usage = 0; + + // The total number of nodes referenced by this cord. + // For ring buffer Cords, this includes the 'ring buffer' node. + // A value of 0 implies the property has not been recorded. + int64_t node_count = 0; +}; + +} // namespace cord_internal +ABSL_NAMESPACE_END +} // namespace absl + +#endif // ABSL_STRINGS_INTERNAL_CORDZ_STATISTICS_H_