summaryrefslogtreecommitdiff
path: root/absl
diff options
context:
space:
mode:
authorGravatar Abseil Team <absl-team@google.com>2021-04-15 19:42:51 -0700
committerGravatar Dino Radaković <dinor@google.com>2021-04-15 19:45:30 -0700
commite20fe888fabc1fc995dc61180e8a31b5f809a95f (patch)
tree5877907889fe35eb3162aa71111e16bd1d59fde4 /absl
parent46dfbfe31ca1dd414e4c33cbcbcd7199bb4efde3 (diff)
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
Diffstat (limited to 'absl')
-rw-r--r--absl/strings/BUILD.bazel136
-rw-r--r--absl/strings/CMakeLists.txt150
-rw-r--r--absl/strings/cord.cc38
-rw-r--r--absl/strings/cord.h41
-rw-r--r--absl/strings/internal/cordz_functions.cc104
-rw-r--r--absl/strings/internal/cordz_functions.h85
-rw-r--r--absl/strings/internal/cordz_functions_test.cc131
-rw-r--r--absl/strings/internal/cordz_handle.cc127
-rw-r--r--absl/strings/internal/cordz_handle.h97
-rw-r--r--absl/strings/internal/cordz_handle_test.cc253
-rw-r--r--absl/strings/internal/cordz_info.cc138
-rw-r--r--absl/strings/internal/cordz_info.h168
-rw-r--r--absl/strings/internal/cordz_info_test.cc237
-rw-r--r--absl/strings/internal/cordz_sample_token.cc64
-rw-r--r--absl/strings/internal/cordz_sample_token.h97
-rw-r--r--absl/strings/internal/cordz_sample_token_test.cc209
-rw-r--r--absl/strings/internal/cordz_statistics.h55
17 files changed, 2129 insertions, 1 deletions
diff --git a/absl/strings/BUILD.bazel b/absl/strings/BUILD.bazel
index 11385163..1306ea65 100644
--- a/absl/strings/BUILD.bazel
+++ b/absl/strings/BUILD.bazel
@@ -327,11 +327,15 @@ cc_library(
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(
)
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 0d93d5ff..044e38b3 100644
--- a/absl/strings/CMakeLists.txt
+++ b/absl/strings/CMakeLists.txt
@@ -259,7 +259,7 @@ absl_cc_test(
absl_cc_test(
NAME
str_join_test
- SRCS
+ss SRCS
"str_join_test.cc"
COPTS
${ABSL_TEST_COPTS}
@@ -605,6 +605,152 @@ absl_cc_test(
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_cc_library(
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 8f0999f8..d33d6a0d 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 @@ void Cord::InlineRep::GetAppendRegion(char** region, size_t* size,
CordRep* root = force_tree(max_length);
if (PrepareAppendRegion(root, region, size, max_length)) {
+ UpdateCordzStatistics();
return;
}
@@ -460,6 +462,7 @@ void Cord::InlineRep::GetAppendRegion(char** region, size_t* size) {
CordRep* root = force_tree(max_length);
if (PrepareAppendRegion(root, region, size, max_length)) {
+ UpdateCordzStatistics();
return;
}
@@ -490,6 +493,27 @@ static bool RepMemoryUsageLeaf(const CordRep* rep, size_t* total_mem_usage) {
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 @@ void Cord::InlineRep::AssignSlow(const Cord::InlineRep& src) {
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 @@ template Cord::Cord(std::string&& src);
// 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 @@ void Cord::Clear() {
}
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 @@ void Cord::InlineRep::AppendArray(const char* src_data, size_t src_size) {
char* region;
if (PrepareAppendRegion(root, &region, &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 7ce938ca..de1470b2 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 @@ class Cord {
// 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 @@ inline Cord::InlineRep::InlineRep(const Cord::InlineRep& src)
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 size_t Cord::InlineRep::size() const {
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 @@ inline void Cord::InlineRep::set_tree(absl::cord_internal::CordRep* rep) {
} 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 @@ inline void Cord::InlineRep::replace_tree(absl::cord_internal::CordRep* rep) {
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 @@ inline void Cord::InlineRep::CopyToArray(char* dst) const {
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 00000000..6ad864f1
--- /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 00000000..c9ba1450
--- /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 00000000..f2cefae3
--- /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 00000000..7e82f85b
--- /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 00000000..0235d4bd
--- /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 00000000..c04240e8
--- /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 00000000..4dec63d5
--- /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 00000000..c1090a1c
--- /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 00000000..be20e4a4
--- /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 00000000..ba1270d8
--- /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 00000000..28a1d70c
--- /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 00000000..8c052642
--- /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 00000000..ce7c39aa
--- /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_