Export of internal Abseil changes

--
93c607726d663800b4bfa472cba043fd3f5d0e97 by Derek Mauro <dmauro@google.com>:

Internal change

PiperOrigin-RevId: 389158822

--
55b3bb50bbc168567c6ba25d07df2c2c39e864af by Martijn Vels <mvels@google.com>:

Change CordRepRing alternative implementation to CordRepBtree alternative.

This changes makes CordRepBtree (BTREE) the alternative to CordRepConcat (CONCAT) trees, enabled through the internal / experimental 'cord_btree_enabled' latch.

PiperOrigin-RevId: 389030571

--
d6fc346143606c096bca8eb5029e4c429ac6e305 by Todd Lipcon <tlipcon@google.com>:

Fix a small typo in SequenceLock doc comment

PiperOrigin-RevId: 388972936

--
e46f9245dce8b4150e3ca2664e0cf42b75f90a83 by Martijn Vels <mvels@google.com>:

Add 'shallow' validation mode to CordRepBtree which will be the default for internal assertions.

PiperOrigin-RevId: 388753606

--
b5e74f163b490beb006f848ace67bb650433fe13 by Martijn Vels <mvels@google.com>:

Add btree statistics to CordzInfo, and reduce rounding errors

PiperOrigin-RevId: 388715878

--
105bcbf80de649937e693b29b18220f9e6841a51 by Evan Brown <ezb@google.com>:

Skip length checking when constructing absl::string_view from `const char*`.
The length check causes unnecessary code bloat.

PiperOrigin-RevId: 388271741

--
bed595158f24839efe49c65ae483f797d79fe0ae by Derek Mauro <dmauro@google.com>:

Internal change

PiperOrigin-RevId: 387713428
GitOrigin-RevId: 93c607726d663800b4bfa472cba043fd3f5d0e97
Change-Id: I2a4840f5ffcd7f70b7d7d45cce66f23c42cf565f

1 files changed, 30 insertions, 21 deletions

diff --git a/absl/strings/internal/cordz_info.cc b/absl/strings/internal/cordz_info.cc
index a3a0b9c0..5c18bbc5 100644
--- a/absl/strings/internal/cordz_info.cc
+++ b/absl/strings/internal/cordz_info.cc
@@ -19,6 +19,7 @@
 #include "absl/container/inlined_vector.h"
 #include "absl/debugging/stacktrace.h"
 #include "absl/strings/internal/cord_internal.h"
+#include "absl/strings/internal/cord_rep_btree.h"
 #include "absl/strings/internal/cord_rep_ring.h"
 #include "absl/strings/internal/cordz_handle.h"
 #include "absl/strings/internal/cordz_statistics.h"
@@ -83,19 +84,23 @@ class CordRepAnalyzer {
     // 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 == BTREE) {
+        AnalyzeBtree(repref);
       } else if (repref.rep->tag == CONCAT) {
         AnalyzeConcat(repref);
+      } else {
+        // We should have either a concat, btree, or ring node if not null.
+        assert(false);
       }
     }
 
     // Adds values to output
     statistics_.estimated_memory_usage += memory_usage_.total;
-    statistics_.estimated_fair_share_memory_usage += memory_usage_.fair_share;
+    statistics_.estimated_fair_share_memory_usage +=
+        static_cast<size_t>(memory_usage_.fair_share);
   }
 
  private:
@@ -117,13 +122,13 @@ class CordRepAnalyzer {
   // Memory usage values
   struct MemoryUsage {
     size_t total = 0;
-    size_t fair_share = 0;
+    double fair_share = 0.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;
+      fair_share += static_cast<double>(size) / refcount;
     }
   };
 
@@ -215,28 +220,32 @@ class CordRepAnalyzer {
     }
   }
 
-  // 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.
+  // Analyzes the provided ring.
   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);
+    memory_usage_.Add(CordRepRing::AllocSize(ring->capacity()), rep.refcount);
     ring->ForEach([&](CordRepRing::index_type pos) {
-      CountRingChild(ring->entry_child(pos), ring_usage);
+      CountLinearReps(rep.Child(ring->entry_child(pos)), memory_usage_);
     });
-    memory_usage_.total += ring_usage.total;
-    memory_usage_.fair_share += ring_usage.fair_share / rep.refcount;
+  }
+
+  // Analyzes the provided btree.
+  void AnalyzeBtree(RepRef rep) {
+    statistics_.node_count++;
+    statistics_.node_counts.btree++;
+    memory_usage_.Add(sizeof(CordRepBtree), rep.refcount);
+    const CordRepBtree* tree = rep.rep->btree();
+    if (tree->height() > 0) {
+      for (CordRep* edge : tree->Edges()) {
+        AnalyzeBtree(rep.Child(edge));
+      }
+    } else {
+      for (CordRep* edge : tree->Edges()) {
+        CountLinearReps(rep.Child(edge), memory_usage_);
+      }
+    }
   }
 
   CordzStatistics& statistics_;