summaryrefslogtreecommitdiff
path: root/absl
diff options
context:
space:
mode:
Diffstat (limited to 'absl')
-rw-r--r--absl/strings/BUILD.bazel21
-rw-r--r--absl/strings/CMakeLists.txt19
-rw-r--r--absl/strings/cord.h1
-rw-r--r--absl/strings/internal/cordz_info.cc207
-rw-r--r--absl/strings/internal/cordz_info.h11
-rw-r--r--absl/strings/internal/cordz_info_statistics_test.cc483
-rw-r--r--absl/strings/internal/cordz_info_test.cc14
-rw-r--r--absl/strings/internal/cordz_statistics.h12
-rw-r--r--absl/synchronization/internal/per_thread_sem_test.cc2
9 files changed, 738 insertions, 32 deletions
diff --git a/absl/strings/BUILD.bazel b/absl/strings/BUILD.bazel
index 15277de3..84d4bc4f 100644
--- a/absl/strings/BUILD.bazel
+++ b/absl/strings/BUILD.bazel
@@ -376,6 +376,7 @@ cc_library(
"//absl/base:config",
"//absl/base:core_headers",
"//absl/base:raw_logging_internal",
+ "//absl/container:inlined_vector",
"//absl/debugging:stacktrace",
"//absl/synchronization",
"//absl/types:span",
@@ -498,6 +499,26 @@ cc_test(
)
cc_test(
+ name = "cordz_info_statistics_test",
+ srcs = [
+ "internal/cordz_info_statistics_test.cc",
+ ],
+ deps = [
+ ":cord",
+ ":cord_internal",
+ ":cordz_info",
+ ":cordz_sample_token",
+ ":cordz_statistics",
+ ":cordz_update_scope",
+ ":cordz_update_tracker",
+ "//absl/base:config",
+ "//absl/synchronization",
+ "//absl/synchronization:thread_pool",
+ "@com_google_googletest//:gtest_main",
+ ],
+)
+
+cc_test(
name = "cordz_sample_token_test",
srcs = [
"internal/cordz_sample_token_test.cc",
diff --git a/absl/strings/CMakeLists.txt b/absl/strings/CMakeLists.txt
index 1750f7af..92728d91 100644
--- a/absl/strings/CMakeLists.txt
+++ b/absl/strings/CMakeLists.txt
@@ -696,6 +696,7 @@ absl_cc_library(
absl::cordz_statistics
absl::cordz_update_tracker
absl::core_headers
+ absl::inlined_vector
absl::span
absl::raw_logging_internal
absl::stacktrace
@@ -722,6 +723,24 @@ absl_cc_test(
gmock_main
)
+absl_cc_test(
+ NAME
+ cordz_info_statistics_test
+ SRCS
+ "internal/cordz_info_statistics_test.cc"
+ DEPS
+ absl::config
+ absl::cord
+ absl::cord_internal
+ absl::cordz_info
+ absl::cordz_sample_token
+ absl::cordz_statistics
+ absl::cordz_update_scope
+ absl::cordz_update_tracker
+ absl::thread_pool
+ gmock_main
+)
+
absl_cc_library(
NAME
cordz_sample_token
diff --git a/absl/strings/cord.h b/absl/strings/cord.h
index 8abc4742..5c80a5cb 100644
--- a/absl/strings/cord.h
+++ b/absl/strings/cord.h
@@ -1077,6 +1077,7 @@ inline cord_internal::CordRepFlat* Cord::InlineRep::MakeFlatWithExtraCapacity(
inline void Cord::InlineRep::EmplaceTree(CordRep* rep,
MethodIdentifier method) {
+ assert(rep);
data_.make_tree(rep);
CordzInfo::MaybeTrackCord(data_, method);
}
diff --git a/absl/strings/internal/cordz_info.cc b/absl/strings/internal/cordz_info.cc
index 0f657aaf..e1fa6b6b 100644
--- a/absl/strings/internal/cordz_info.cc
+++ b/absl/strings/internal/cordz_info.cc
@@ -16,8 +16,10 @@
#include "absl/base/config.h"
#include "absl/base/internal/spinlock.h"
+#include "absl/container/inlined_vector.h"
#include "absl/debugging/stacktrace.h"
#include "absl/strings/internal/cord_internal.h"
+#include "absl/strings/internal/cord_rep_ring.h"
#include "absl/strings/internal/cordz_handle.h"
#include "absl/strings/internal/cordz_statistics.h"
#include "absl/strings/internal/cordz_update_tracker.h"
@@ -34,6 +36,198 @@ constexpr int CordzInfo::kMaxStackDepth;
ABSL_CONST_INIT CordzInfo::List CordzInfo::global_list_{absl::kConstInit};
+namespace {
+
+// CordRepAnalyzer performs the analysis of a cord.
+//
+// It computes absolute node counts and total memory usage, and an 'estimated
+// fair share memory usage` statistic.
+// Conceptually, it divides the 'memory usage' at each location in the 'cord
+// graph' by the cumulative reference count of that location. The cumulative
+// reference count is the factored total of all edges leading into that node.
+//
+// The top level node is treated specially: we assume the current thread
+// (typically called from the CordzHandler) to hold a reference purely to
+// perform a safe analysis, and not being part of the application. So we
+// substract 1 from the reference count of the top node to compute the
+// 'application fair share' excluding the reference of the current thread.
+//
+// An example of fair sharing, and why we multiply reference counts:
+// Assume we have 2 CordReps, both being a Substring referencing a Flat:
+// CordSubstring A (refcount = 5) --> child Flat C (refcount = 2)
+// CordSubstring B (refcount = 9) --> child Flat C (refcount = 2)
+//
+// Flat C has 2 incoming edges from the 2 substrings (refcount = 2) and is not
+// referenced directly anywhere else. Translated into a 'fair share', we then
+// attribute 50% of the memory (memory / refcount = 2) to each incoming edge.
+// Rep A has a refcount of 5, so we attribute each incoming edge 1 / 5th of the
+// memory cost below it, i.e.: the fair share of Rep A of the memory used by C
+// is then 'memory C / (refcount C * refcount A) + (memory A / refcount A)'.
+// It is also easy to see how all incoming edges add up to 100%.
+class CordRepAnalyzer {
+ public:
+ // Creates an analyzer instance binding to `statistics`.
+ explicit CordRepAnalyzer(CordzStatistics& statistics)
+ : statistics_(statistics) {}
+
+ // Analyzes the memory statistics and node counts for the provided `rep`, and
+ // adds the results to `statistics`. Note that node counts and memory sizes
+ // are not initialized, computed values are added to any existing values.
+ void AnalyzeCordRep(const CordRep* rep) {
+ // Process all linear nodes.
+ // As per the class comments, use refcout - 1 on the top level node, as the
+ // top level node is assumed to be referenced only for analysis purposes.
+ size_t refcount = rep->refcount.Get();
+ RepRef repref{rep, (refcount > 1) ? refcount - 1 : 1};
+
+ // Process all top level linear nodes (substrings and flats).
+ repref = CountLinearReps(repref, memory_usage_);
+
+ // We should have have either a concat or ring node node if not null.
+ if (repref.rep != nullptr) {
+ assert(repref.rep->tag == RING || repref.rep->tag == CONCAT);
+ if (repref.rep->tag == RING) {
+ AnalyzeRing(repref);
+ } else if (repref.rep->tag == CONCAT) {
+ AnalyzeConcat(repref);
+ }
+ }
+
+ // Adds values to output
+ statistics_.estimated_memory_usage += memory_usage_.total;
+ statistics_.estimated_fair_share_memory_usage += memory_usage_.fair_share;
+ }
+
+ private:
+ // RepRef identifies a CordRep* inside the Cord tree with its cumulative
+ // refcount including itself. For example, a tree consisting of a substring
+ // with a refcount of 3 and a child flat with a refcount of 4 will have RepRef
+ // refcounts of 3 and 12 respectively.
+ struct RepRef {
+ const CordRep* rep;
+ size_t refcount;
+
+ // Returns a 'child' RepRef which contains the cumulative reference count of
+ // this instance multiplied by the child's reference count.
+ RepRef Child(const CordRep* child) const {
+ return RepRef{child, refcount * child->refcount.Get()};
+ }
+ };
+
+ // Memory usage values
+ struct MemoryUsage {
+ size_t total = 0;
+ size_t fair_share = 0;
+
+ // Adds 'size` memory usage to this class, with a cumulative (recursive)
+ // reference count of `refcount`
+ void Add(size_t size, size_t refcount) {
+ total += size;
+ fair_share += size / refcount;
+ }
+ };
+
+ // Returns `rr` if `rr.rep` is not null and a CONCAT type.
+ // Asserts that `rr.rep` is a concat node or null.
+ static RepRef AssertConcat(RepRef repref) {
+ const CordRep* rep = repref.rep;
+ assert(rep == nullptr || rep->tag == CONCAT);
+ return (rep != nullptr && rep->tag == CONCAT) ? repref : RepRef{nullptr, 0};
+ }
+
+ // Processes 'linear' reps (substring, flat, external) not requiring iteration
+ // or recursion. Returns RefRep{null} if all reps were processed, else returns
+ // the top-most non-linear concat or ring cordrep.
+ // Node counts are updated into `statistics_`, memory usage is update into
+ // `memory_usage`, which typically references `memory_usage_` except for ring
+ // buffers where we count children unrounded.
+ RepRef CountLinearReps(RepRef rep, MemoryUsage& memory_usage) {
+ // Consume all substrings
+ while (rep.rep->tag == SUBSTRING) {
+ statistics_.node_count++;
+ statistics_.node_counts.substring++;
+ memory_usage.Add(sizeof(CordRepSubstring), rep.refcount);
+ rep = rep.Child(rep.rep->substring()->child);
+ }
+
+ // Consume possible FLAT
+ if (rep.rep->tag >= FLAT) {
+ statistics_.node_count++;
+ statistics_.node_counts.flat++;
+ memory_usage.Add(rep.rep->flat()->AllocatedSize(), rep.refcount);
+ return RepRef{nullptr, 0};
+ }
+
+ // Consume possible external
+ if (rep.rep->tag == EXTERNAL) {
+ statistics_.node_count++;
+ statistics_.node_counts.external++;
+ size_t size = rep.rep->length + sizeof(CordRepExternalImpl<intptr_t>);
+ memory_usage.Add(size, rep.refcount);
+ return RepRef{nullptr, 0};
+ }
+
+ return rep;
+ }
+
+ // Analyzes the provided concat node in a flattened recursive way.
+ void AnalyzeConcat(RepRef rep) {
+ absl::InlinedVector<RepRef, 47> pending;
+
+ while (rep.rep != nullptr) {
+ const CordRepConcat* concat = rep.rep->concat();
+ RepRef left = rep.Child(concat->left);
+ RepRef right = rep.Child(concat->right);
+
+ statistics_.node_count++;
+ statistics_.node_counts.concat++;
+ memory_usage_.Add(sizeof(CordRepConcat), rep.refcount);
+
+ right = AssertConcat(CountLinearReps(right, memory_usage_));
+ rep = AssertConcat(CountLinearReps(left, memory_usage_));
+ if (rep.rep != nullptr) {
+ if (right.rep != nullptr) {
+ pending.push_back(right);
+ }
+ } else if (right.rep != nullptr) {
+ rep = right;
+ } else if (!pending.empty()) {
+ rep = pending.back();
+ pending.pop_back();
+ }
+ }
+ }
+
+ // Counts the provided ring buffer child into `child_usage`.
+ void CountRingChild(const CordRep* child, MemoryUsage& child_usage) {
+ RepRef rep{child, static_cast<size_t>(child->refcount.Get())};
+ rep = CountLinearReps(rep, child_usage);
+ assert(rep.rep == nullptr);
+ }
+
+ // Analyzes the provided ring. As ring buffers can have many child nodes, the
+ // effect of rounding errors can become non trivial, so we compute the totals
+ // first at the ring level, and then divide the fair share of the total
+ // including children fair share totals.
+ void AnalyzeRing(RepRef rep) {
+ statistics_.node_count++;
+ statistics_.node_counts.ring++;
+ MemoryUsage ring_usage;
+ const CordRepRing* ring = rep.rep->ring();
+ ring_usage.Add(CordRepRing::AllocSize(ring->capacity()), 1);
+ ring->ForEach([&](CordRepRing::index_type pos) {
+ CountRingChild(ring->entry_child(pos), ring_usage);
+ });
+ memory_usage_.total += ring_usage.total;
+ memory_usage_.fair_share += ring_usage.fair_share / rep.refcount;
+ }
+
+ CordzStatistics& statistics_;
+ MemoryUsage memory_usage_;
+};
+
+} // namespace
+
CordzInfo* CordzInfo::Head(const CordzSnapshot& snapshot) {
ABSL_ASSERT(snapshot.is_snapshot());
@@ -101,8 +295,7 @@ CordzInfo::CordzInfo(CordRep* rep, const CordzInfo* src,
parent_stack_depth_(FillParentStack(src, parent_stack_)),
method_(method),
parent_method_(GetParentMethod(src)),
- create_time_(absl::Now()),
- size_(rep->length) {
+ create_time_(absl::Now()) {
update_tracker_.LossyAdd(method);
}
@@ -173,9 +366,6 @@ void CordzInfo::Lock(MethodIdentifier method)
void CordzInfo::Unlock() ABSL_UNLOCK_FUNCTION(mutex_) {
bool tracked = rep_ != nullptr;
- if (rep_) {
- size_.store(rep_->length);
- }
mutex_.Unlock();
if (!tracked) {
Untrack();
@@ -195,7 +385,12 @@ CordzStatistics CordzInfo::GetCordzStatistics() const {
stats.method = method_;
stats.parent_method = parent_method_;
stats.update_tracker = update_tracker_;
- stats.size = size_.load(std::memory_order_relaxed);
+ if (CordRep* rep = RefCordRep()) {
+ stats.size = rep->length;
+ CordRepAnalyzer analyzer(stats);
+ analyzer.AnalyzeCordRep(rep);
+ CordRep::Unref(rep);
+ }
return stats;
}
diff --git a/absl/strings/internal/cordz_info.h b/absl/strings/internal/cordz_info.h
index 1fe046ec..e84006c5 100644
--- a/absl/strings/internal/cordz_info.h
+++ b/absl/strings/internal/cordz_info.h
@@ -147,11 +147,6 @@ class ABSL_LOCKABLE CordzInfo : public CordzHandle {
// or RemovePrefix.
CordzStatistics GetCordzStatistics() const;
- // Records size metric for this CordzInfo instance.
- void RecordMetrics(int64_t size) {
- size_.store(size, std::memory_order_relaxed);
- }
-
private:
using SpinLock = absl::base_internal::SpinLock;
using SpinLockHolder = ::absl::base_internal::SpinLockHolder;
@@ -215,9 +210,6 @@ class ABSL_LOCKABLE CordzInfo : public CordzHandle {
const MethodIdentifier parent_method_;
CordzUpdateTracker update_tracker_;
const absl::Time create_time_;
-
- // Last recorded size for the cord.
- std::atomic<int64_t> size_{0};
};
inline ABSL_ATTRIBUTE_ALWAYS_INLINE void CordzInfo::MaybeTrackCord(
@@ -250,9 +242,6 @@ inline void CordzInfo::AssertHeld() ABSL_ASSERT_EXCLUSIVE_LOCK(mutex_) {
inline void CordzInfo::SetCordRep(CordRep* rep) {
AssertHeld();
rep_ = rep;
- if (rep) {
- size_.store(rep->length);
- }
}
inline void CordzInfo::UnsafeSetCordRep(CordRep* rep) { rep_ = rep; }
diff --git a/absl/strings/internal/cordz_info_statistics_test.cc b/absl/strings/internal/cordz_info_statistics_test.cc
new file mode 100644
index 00000000..d46d6d62
--- /dev/null
+++ b/absl/strings/internal/cordz_info_statistics_test.cc
@@ -0,0 +1,483 @@
+// Copyright 2021 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 <iostream>
+#include <random>
+#include <vector>
+
+#include "gmock/gmock.h"
+#include "gtest/gtest.h"
+#include "absl/base/config.h"
+#include "absl/strings/cord.h"
+#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_info.h"
+#include "absl/strings/internal/cordz_sample_token.h"
+#include "absl/strings/internal/cordz_statistics.h"
+#include "absl/strings/internal/cordz_update_scope.h"
+#include "absl/strings/internal/cordz_update_tracker.h"
+#include "absl/synchronization/internal/thread_pool.h"
+#include "absl/synchronization/notification.h"
+
+namespace absl {
+ABSL_NAMESPACE_BEGIN
+namespace cord_internal {
+
+// Do not print statistics contents, the matcher prints them as needed.
+inline void PrintTo(const CordzStatistics& stats, std::ostream* s) {
+ if (s) *s << "CordzStatistics{...}";
+}
+
+namespace {
+
+// Creates a flat of the specified length
+CordRepFlat* Flat(int length = 512) {
+ auto* flat = CordRepFlat::New(length);
+ flat->length = length;
+ return flat;
+}
+
+// Creates an external of the specified length
+CordRepExternal* External(int length = 512) {
+ return static_cast<CordRepExternal*>(
+ NewExternalRep(absl::string_view("", length), [](absl::string_view) {}));
+}
+
+// Creates a substring on the provided rep of length - 1
+CordRepSubstring* Substring(CordRep* rep) {
+ auto* substring = new CordRepSubstring;
+ substring->length = rep->length - 1;
+ substring->tag = SUBSTRING;
+ substring->child = rep;
+ return substring;
+}
+
+// Creates a concat on the provided reps
+CordRepConcat* Concat(CordRep* left, CordRep* right) {
+ auto* concat = new CordRepConcat;
+ concat->length = left->length + right->length;
+ concat->tag = CONCAT;
+ concat->left = left;
+ concat->right = right;
+ return concat;
+}
+
+// Reference count helper
+struct RefHelper {
+ std::vector<CordRep*> refs;
+
+ ~RefHelper() {
+ for (CordRep* rep : refs) {
+ CordRep::Unref(rep);
+ }
+ }
+
+ // Invokes CordRep::Unref() on `rep` when this instance is destroyed.
+ template <typename T>
+ T* NeedsUnref(T* rep) {
+ refs.push_back(rep);
+ return rep;
+ }
+
+ // Adds `n` reference counts to `rep` which will be unreffed when this
+ // instance is destroyed.
+ template <typename T>
+ T* Ref(T* rep, size_t n = 1) {
+ while (n--) {
+ NeedsUnref(CordRep::Ref(rep));
+ }
+ return rep;
+ }
+};
+
+// Sizeof helper. Returns the allocated size of `p`, excluding any child
+// elements for substring, concat and ring cord reps.
+template <typename T>
+size_t SizeOf(const T* rep) {
+ return sizeof(T);
+}
+
+template <>
+size_t SizeOf(const CordRepFlat* rep) {
+ return rep->AllocatedSize();
+}
+
+template <>
+size_t SizeOf(const CordRepExternal* rep) {
+ // See cord.cc
+ return sizeof(CordRepExternalImpl<intptr_t>) + rep->length;
+}
+
+template <>
+size_t SizeOf(const CordRepRing* rep) {
+ return CordRepRing::AllocSize(rep->capacity());
+}
+
+// Computes fair share memory used in a naive 'we dare to recurse' way.
+size_t FairShare(CordRep* rep, size_t ref = 1) {
+ size_t self = 0, children = 0;
+ ref *= rep->refcount.Get();
+ if (rep->tag >= FLAT) {
+ self = SizeOf(rep->flat());
+ } else if (rep->tag == EXTERNAL) {
+ self = SizeOf(rep->external());
+ } else if (rep->tag == SUBSTRING) {
+ self = SizeOf(rep->substring());
+ children = FairShare(rep->substring()->child, ref);
+ } else if (rep->tag == RING) {
+ self = SizeOf(rep->ring());
+ rep->ring()->ForEach([&](CordRepRing::index_type i) {
+ self += FairShare(rep->ring()->entry_child(i));
+ });
+ } else if (rep->tag == CONCAT) {
+ self = SizeOf(rep->concat());
+ children = FairShare(rep->concat()->left, ref) +
+ FairShare(rep->concat()->right, ref);
+ } else {
+ assert(false);
+ }
+ return self / ref + children;
+}
+
+// Samples the cord and returns CordzInfo::GetStatistics()
+CordzStatistics SampleCord(CordRep* rep) {
+ InlineData cord(rep);
+ CordzInfo::TrackCord(cord, CordzUpdateTracker::kUnknown);
+ CordzStatistics stats = cord.cordz_info()->GetCordzStatistics();
+ cord.cordz_info()->Untrack();
+ return stats;
+}
+
+MATCHER_P(EqStatistics, stats, "Statistics equal expected values") {
+ bool ok = true;
+
+#define STATS_MATCHER_EXPECT_EQ(member) \
+ if (stats.member != arg.member) { \
+ *result_listener << "\n stats." << #member \
+ << ": actual = " << arg.member << ", expected " \
+ << stats.member; \
+ ok = false; \
+ }
+
+ STATS_MATCHER_EXPECT_EQ(size);
+ STATS_MATCHER_EXPECT_EQ(node_count);
+ STATS_MATCHER_EXPECT_EQ(node_counts.flat);
+ STATS_MATCHER_EXPECT_EQ(node_counts.external);
+ STATS_MATCHER_EXPECT_EQ(node_counts.concat);
+ STATS_MATCHER_EXPECT_EQ(node_counts.substring);
+ STATS_MATCHER_EXPECT_EQ(node_counts.ring);
+ STATS_MATCHER_EXPECT_EQ(estimated_memory_usage);
+ STATS_MATCHER_EXPECT_EQ(estimated_fair_share_memory_usage);
+
+#undef STATS_MATCHER_EXPECT_EQ
+
+ return ok;
+}
+
+TEST(CordzInfoStatisticsTest, Flat) {
+ RefHelper ref;
+ auto* flat = ref.NeedsUnref(Flat());
+
+ CordzStatistics expected;
+ expected.size = flat->length;
+ expected.estimated_memory_usage = SizeOf(flat);
+ expected.estimated_fair_share_memory_usage = expected.estimated_memory_usage;
+ expected.node_count = 1;
+ expected.node_counts.flat = 1;
+
+ EXPECT_THAT(SampleCord(flat), EqStatistics(expected));
+}
+
+TEST(CordzInfoStatisticsTest, SharedFlat) {
+ RefHelper ref;
+ auto* flat = ref.Ref(ref.NeedsUnref(Flat()));
+
+ CordzStatistics expected;
+ expected.size = flat->length;
+ expected.estimated_memory_usage = SizeOf(flat);
+ expected.estimated_fair_share_memory_usage = SizeOf(flat) / 2;
+ expected.node_count = 1;
+ expected.node_counts.flat = 1;
+
+ EXPECT_THAT(SampleCord(flat), EqStatistics(expected));
+}
+
+TEST(CordzInfoStatisticsTest, External) {
+ RefHelper ref;
+ auto* external = ref.NeedsUnref(External());
+
+ CordzStatistics expected;
+ expected.size = external->length;
+ expected.estimated_memory_usage = SizeOf(external);
+ expected.estimated_fair_share_memory_usage = SizeOf(external);
+ expected.node_count = 1;
+ expected.node_counts.external = 1;
+
+ EXPECT_THAT(SampleCord(external), EqStatistics(expected));
+}
+
+TEST(CordzInfoStatisticsTest, SharedExternal) {
+ RefHelper ref;
+ auto* external = ref.Ref(ref.NeedsUnref(External()));
+
+ CordzStatistics expected;
+ expected.size = external->length;
+ expected.estimated_memory_usage = SizeOf(external);
+ expected.estimated_fair_share_memory_usage = SizeOf(external) / 2;
+ expected.node_count = 1;
+ expected.node_counts.external = 1;
+
+ EXPECT_THAT(SampleCord(external), EqStatistics(expected));
+}
+
+TEST(CordzInfoStatisticsTest, Substring) {
+ RefHelper ref;
+ auto* flat = Flat();
+ auto* substring = ref.NeedsUnref(Substring(flat));
+
+ CordzStatistics expected;
+ expected.size = substring->length;
+ expected.estimated_memory_usage = SizeOf(substring) + SizeOf(flat);
+ expected.estimated_fair_share_memory_usage = expected.estimated_memory_usage;
+ expected.node_count = 2;
+ expected.node_counts.flat = 1;
+ expected.node_counts.substring = 1;
+
+ EXPECT_THAT(SampleCord(substring), EqStatistics(expected));
+}
+
+TEST(CordzInfoStatisticsTest, SharedSubstring) {
+ RefHelper ref;
+ auto* flat = ref.Ref(Flat(), 2);
+ auto* substring = ref.Ref(ref.NeedsUnref(Substring(flat)));
+
+ CordzStatistics expected;
+ expected.size = substring->length;
+ expected.estimated_memory_usage = SizeOf(flat) + SizeOf(substring);
+ expected.estimated_fair_share_memory_usage =
+ SizeOf(substring) / 2 + SizeOf(flat) / 6;
+ expected.node_count = 2;
+ expected.node_counts.flat = 1;
+ expected.node_counts.substring = 1;
+
+ EXPECT_THAT(SampleCord(substring), EqStatistics(expected));
+}
+
+TEST(CordzInfoStatisticsTest, Concat) {
+ RefHelper ref;
+ auto* flat1 = Flat(20);
+ auto* flat2 = Flat(2000);
+ auto* concat = ref.NeedsUnref(Concat(flat1, flat2));
+
+ CordzStatistics expected;
+ expected.size = concat->length;
+ expected.estimated_memory_usage =
+ SizeOf(concat) + SizeOf(flat1) + SizeOf(flat2);
+ expected.estimated_fair_share_memory_usage = expected.estimated_memory_usage;
+ expected.node_count = 3;
+ expected.node_counts.flat = 2;
+ expected.node_counts.concat = 1;
+
+ EXPECT_THAT(SampleCord(concat), EqStatistics(expected));
+}
+
+TEST(CordzInfoStatisticsTest, DeepConcat) {
+ RefHelper ref;
+ auto* flat1 = Flat(20);
+ auto* flat2 = Flat(2000);
+ auto* flat3 = Flat(30);
+ auto* external = External(3000);
+ auto* substring = Substring(external);
+ auto* concat1 = Concat(flat1, flat2);
+ auto* concat2 = Concat(flat3, substring);
+ auto* concat = ref.NeedsUnref(Concat(concat1, concat2));
+
+ CordzStatistics expected;
+ expected.size = concat->length;
+ expected.estimated_memory_usage = SizeOf(concat) * 3 + SizeOf(flat1) +
+ SizeOf(flat2) + SizeOf(flat3) +
+ SizeOf(external) + SizeOf(substring);
+ expected.estimated_fair_share_memory_usage = expected.estimated_memory_usage;
+
+ expected.node_count = 8;
+ expected.node_counts.flat = 3;
+ expected.node_counts.external = 1;
+ expected.node_counts.concat = 3;
+ expected.node_counts.substring = 1;
+
+ EXPECT_THAT(SampleCord(concat), EqStatistics(expected));
+}
+
+TEST(CordzInfoStatisticsTest, DeepSharedConcat) {
+ RefHelper ref;
+ auto* flat1 = Flat(20);
+ auto* flat2 = ref.Ref(Flat(2000), 4);
+ auto* flat3 = Flat(30);
+ auto* external = ref.Ref(External(3000));
+ auto* substring = ref.Ref(Substring(external), 3);
+ auto* concat1 = Concat(flat1, flat2);
+ auto* concat2 = Concat(flat3, substring);
+ auto* concat = ref.Ref(ref.NeedsUnref(Concat(concat1, concat2)));
+
+ CordzStatistics expected;
+ expected.size = concat->length;
+ expected.estimated_memory_usage = SizeOf(concat) * 3 + SizeOf(flat1) +
+ SizeOf(flat2) + SizeOf(flat3) +
+ SizeOf(external) + SizeOf(substring);
+ expected.estimated_fair_share_memory_usage = FairShare(concat);
+ expected.node_count = 8;
+ expected.node_counts.flat = 3;
+ expected.node_counts.external = 1;
+ expected.node_counts.concat = 3;
+ expected.node_counts.substring = 1;
+
+ EXPECT_THAT(SampleCord(concat), EqStatistics(expected));
+}
+
+TEST(CordzInfoStatisticsTest, Ring) {
+ RefHelper ref;
+ auto* flat1 = Flat(20);
+ auto* flat2 = Flat(2000);
+ auto* flat3 = Flat(30);
+ auto* external = External(3000);
+ CordRepRing* ring = CordRepRing::Create(flat1);
+ ring = CordRepRing::Append(ring, flat2);
+ ring = CordRepRing::Append(ring, flat3);
+ ring = ref.NeedsUnref(CordRepRing::Append(ring, external));
+
+ CordzStatistics expected;
+ expected.size = ring->length;
+ expected.estimated_memory_usage = SizeOf(ring) + SizeOf(flat1) +
+ SizeOf(flat2) + SizeOf(flat3) +
+ SizeOf(external);
+ expected.estimated_fair_share_memory_usage = expected.estimated_memory_usage;
+ expected.node_count = 5;
+ expected.node_counts.flat = 3;
+ expected.node_counts.external = 1;
+ expected.node_counts.ring = 1;
+
+ EXPECT_THAT(SampleCord(ring), EqStatistics(expected));
+}
+
+TEST(CordzInfoStatisticsTest, SharedSubstringRing) {
+ RefHelper ref;
+ auto* flat1 = ref.Ref(Flat(20));
+ auto* flat2 = Flat(200);
+ auto* flat3 = Flat(30);
+ auto* external = ref.Ref(External(3000), 5);
+ CordRepRing* ring = CordRepRing::Create(flat1);
+ ring = CordRepRing::Append(ring, flat2);
+ ring = CordRepRing::Append(ring, flat3);
+ ring = ref.Ref(CordRepRing::Append(ring, external), 4);
+ auto* substring = ref.Ref(ref.NeedsUnref(Substring(ring)));
+
+
+ CordzStatistics expected;
+ expected.size = substring->length;
+ expected.estimated_memory_usage = SizeOf(ring) + SizeOf(flat1) +
+ SizeOf(flat2) + SizeOf(flat3) +
+ SizeOf(external) + SizeOf(substring);
+ expected.estimated_fair_share_memory_usage = FairShare(substring);
+ expected.node_count = 6;
+ expected.node_counts.flat = 3;
+ expected.node_counts.external = 1;
+ expected.node_counts.ring = 1;
+ expected.node_counts.substring = 1;
+
+ EXPECT_THAT(SampleCord(substring), EqStatistics(expected));
+}
+
+TEST(CordzInfoStatisticsTest, ThreadSafety) {
+ Notification stop;
+ static constexpr int kNumThreads = 8;
+ int64_t sampled_node_count = 0;
+
+ {
+ absl::synchronization_internal::ThreadPool pool(kNumThreads);
+
+ // Run analyzer thread emulating a CordzHandler collection.
+ pool.Schedule([&]() {
+ while (!stop.HasBeenNotified()) {
+ // Run every 10us (about 100K total collections).
+ absl::SleepFor(absl::Microseconds(10));
+ CordzSampleToken token;
+ for (const CordzInfo& cord_info : token) {
+ CordzStatistics stats = cord_info.GetCordzStatistics();
+ sampled_node_count += stats.node_count;
+ }
+ }
+ });
+
+ // Run 'application threads'
+ for (int i = 0; i < kNumThreads; ++i) {
+ pool.Schedule([&]() {
+ // Track 0 - 2 cordz infos at a time, providing permutations of 0, 1
+ // and 2 CordzHandle and CordzInfo queues being active, with plenty of
+ // 'empty to non empty' transitions.
+ InlineData cords[2];
+ std::minstd_rand gen;
+ std::uniform_int_distribution<int> coin_toss(0, 1);
+
+ while (!stop.HasBeenNotified()) {
+ for (InlineData& cord : cords) {
+ // 50/50 flip the state of the cord
+ if (coin_toss(gen) != 0) {
+ if (cord.is_tree()) {
+ // 50/50 simulate delete (untrack) or 'edit to empty'
+ if (coin_toss(gen) != 0) {
+ CordzInfo::MaybeUntrackCord(cord.cordz_info());
+ } else {
+ CordzUpdateScope scope(cord.cordz_info(),
+ CordzUpdateTracker::kUnknown);
+ scope.SetCordRep(nullptr);
+ }
+ CordRep::Unref(cord.as_tree());
+ cord.set_inline_size(0);
+ } else {
+ // 50/50 Ring or Flat coin toss
+ CordRep* rep = Flat();
+ rep = (coin_toss(gen) != 0) ? CordRepRing::Create(rep) : rep;
+ cord.make_tree(rep);
+
+ // 50/50 sample
+ if (coin_toss(gen) != 0) {
+ CordzInfo::TrackCord(cord, CordzUpdateTracker::kUnknown);
+ }
+ }
+ }
+ }
+ }
+ for (InlineData& cord : cords) {
+ if (cord.is_tree()) {
+ CordzInfo::MaybeUntrackCord(cord.cordz_info());
+ CordRep::Unref(cord.as_tree());
+ }
+ }
+ });
+ }
+
+ // Run for 1 second to give memory and thread safety analyzers plenty of
+ // time to detect any mishaps or undefined behaviors.
+ absl::SleepFor(absl::Seconds(1));
+ stop.Notify();
+ }
+
+ std::cout << "Sampled " << sampled_node_count << " nodes\n";
+}
+
+} // namespace
+} // namespace cord_internal
+ABSL_NAMESPACE_END
+} // namespace absl
diff --git a/absl/strings/internal/cordz_info_test.cc b/absl/strings/internal/cordz_info_test.cc
index 5bb23e47..b7eb910d 100644
--- a/absl/strings/internal/cordz_info_test.cc
+++ b/absl/strings/internal/cordz_info_test.cc
@@ -304,20 +304,6 @@ TEST(CordzInfoTest, FromParentInlined) {
info->Untrack();
}
-TEST(CordzInfoTest, RecordMetrics) {
- TestCordData data;
- CordzInfo* info = TrackParentCord(data.data);
-
- CordzStatistics expected;
- expected.size = 100;
- info->RecordMetrics(expected.size);
-
- CordzStatistics actual = info->GetCordzStatistics();
- EXPECT_EQ(actual.size, expected.size);
-
- info->Untrack();
-}
-
} // namespace
} // namespace cord_internal
ABSL_NAMESPACE_END
diff --git a/absl/strings/internal/cordz_statistics.h b/absl/strings/internal/cordz_statistics.h
index 6e335c0b..1c93dfd0 100644
--- a/absl/strings/internal/cordz_statistics.h
+++ b/absl/strings/internal/cordz_statistics.h
@@ -28,6 +28,15 @@ namespace cord_internal {
struct CordzStatistics {
using MethodIdentifier = CordzUpdateTracker::MethodIdentifier;
+ // Node counts information
+ struct NodeCounts {
+ size_t flat = 0;
+ size_t external = 0;
+ size_t substring = 0;
+ size_t concat = 0;
+ size_t ring = 0;
+ };
+
// The size of the cord in bytes. This matches the result of Cord::size().
int64_t size = 0;
@@ -50,6 +59,9 @@ struct CordzStatistics {
// A value of 0 implies the property has not been recorded.
int64_t node_count = 0;
+ // Detailed node counts per type
+ NodeCounts node_counts;
+
// The cord method responsible for sampling the cord.
MethodIdentifier method = MethodIdentifier::kUnknown;
diff --git a/absl/synchronization/internal/per_thread_sem_test.cc b/absl/synchronization/internal/per_thread_sem_test.cc
index 8cf59e64..db1184e6 100644
--- a/absl/synchronization/internal/per_thread_sem_test.cc
+++ b/absl/synchronization/internal/per_thread_sem_test.cc
@@ -159,7 +159,7 @@ TEST_F(PerThreadSemTest, Timeouts) {
const absl::Duration elapsed = absl::Now() - start;
// Allow for a slight early return, to account for quality of implementation
// issues on various platforms.
- const absl::Duration slop = absl::Microseconds(200);
+ const absl::Duration slop = absl::Milliseconds(1);
EXPECT_LE(delay - slop, elapsed)
<< "Wait returned " << delay - elapsed
<< " early (with " << slop << " slop), start time was " << start;