diff options
Diffstat (limited to 'absl')
| -rw-r--r-- | absl/strings/BUILD.bazel | 21 | ||||
| -rw-r--r-- | absl/strings/CMakeLists.txt | 19 | ||||
| -rw-r--r-- | absl/strings/cord.h | 1 | ||||
| -rw-r--r-- | absl/strings/internal/cordz_info.cc | 207 | ||||
| -rw-r--r-- | absl/strings/internal/cordz_info.h | 11 | ||||
| -rw-r--r-- | absl/strings/internal/cordz_info_statistics_test.cc | 483 | ||||
| -rw-r--r-- | absl/strings/internal/cordz_info_test.cc | 14 | ||||
| -rw-r--r-- | absl/strings/internal/cordz_statistics.h | 12 | ||||
| -rw-r--r-- | absl/synchronization/internal/per_thread_sem_test.cc | 2 |
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; |