Export of internal Abseil changes

--
77e710b0ced5792a328e88bcb938a41484bf4cdc by Saleem Abdulrasool <abdulras@google.com>:

absl: add an implementation for UnscaledCycleClock on RISCV

Add an implementation for UnscaledCycleClock on RISC-V targets.

PiperOrigin-RevId: 395982312

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

Harden CordRepBtreeReader against reading up to or beyond EOF

This change hardens the reader to Next() calls on EOF situations. It changes the 'consumed()' property inside CordRepBtreeReader into a 'remaining()' property which is easier to understand and use than the 'consumed()' property QED the function documentation and use in cord.cc

This change also adds the CharIterator test to the CordTest fixture enabling them to be run with btree cords.

PiperOrigin-RevId: 395971732

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

Add AdvanceAndRead() test addressing the edge case surfaced in b/197776822

This adds a test explicitly exercising all possible AdvanceAndRead() calls on CharIterator. As per the linked bug, a partial or full small read ending exactly at the end of the last edge of a btree cord results in an attempt to read beyond that last edge and subsequent failure. We will fix the bug and enable these tests for btree in a subsequent change.

PiperOrigin-RevId: 395958317
GitOrigin-RevId: 77e710b0ced5792a328e88bcb938a41484bf4cdc
Change-Id: Ie6e21ce36980515165af7cf046cf199ecbe0ddb0

6 files changed, 117 insertions, 70 deletions

diff --git a/absl/base/internal/unscaledcycleclock.cc b/absl/base/internal/unscaledcycleclock.cc
index 1545288c..fc07e300 100644
--- a/absl/base/internal/unscaledcycleclock.cc
+++ b/absl/base/internal/unscaledcycleclock.cc
@@ -119,6 +119,18 @@ double UnscaledCycleClock::Frequency() {
   return aarch64_timer_frequency;
 }
 
+#elif defined(__riscv)
+
+int64_t UnscaledCycleClock::Now() {
+  int64_t virtual_timer_value;
+  asm volatile("rdcycle %0" : "=r"(virtual_timer_value));
+  return virtual_timer_value;
+}
+
+double UnscaledCycleClock::Frequency() {
+  return base_internal::NominalCPUFrequency();
+}
+
 #elif defined(_M_IX86) || defined(_M_X64)
 
 #pragma intrinsic(__rdtsc)
diff --git a/absl/base/internal/unscaledcycleclock.h b/absl/base/internal/unscaledcycleclock.h
index 82f2c87a..681ff8f9 100644
--- a/absl/base/internal/unscaledcycleclock.h
+++ b/absl/base/internal/unscaledcycleclock.h
@@ -46,8 +46,8 @@
 
 // The following platforms have an implementation of a hardware counter.
 #if defined(__i386__) || defined(__x86_64__) || defined(__aarch64__) || \
-  defined(__powerpc__) || defined(__ppc__) || \
-  defined(_M_IX86) || defined(_M_X64)
+    defined(__powerpc__) || defined(__ppc__) || defined(__riscv) ||     \
+    defined(_M_IX86) || defined(_M_X64)
 #define ABSL_HAVE_UNSCALED_CYCLECLOCK_IMPLEMENTATION 1
 #else
 #define ABSL_HAVE_UNSCALED_CYCLECLOCK_IMPLEMENTATION 0
@@ -80,8 +80,8 @@
 
 // This macro can be used to test if UnscaledCycleClock::Frequency()
 // is NominalCPUFrequency() on a particular platform.
-#if  (defined(__i386__) || defined(__x86_64__) || \
-      defined(_M_IX86) || defined(_M_X64))
+#if (defined(__i386__) || defined(__x86_64__) || defined(__riscv) || \
+     defined(_M_IX86) || defined(_M_X64))
 #define ABSL_INTERNAL_UNSCALED_CYCLECLOCK_FREQUENCY_IS_CPU_FREQUENCY
 #endif
 
diff --git a/absl/strings/cord_test.cc b/absl/strings/cord_test.cc
index 06a7bd6c..50079b7c 100644
--- a/absl/strings/cord_test.cc
+++ b/absl/strings/cord_test.cc
@@ -1591,7 +1591,7 @@ TEST_P(CordTest, CordChunkIteratorOperations) {
   VerifyChunkIterator(subcords, 128);
 }
 
-TEST(CordCharIterator, Traits) {
+TEST_P(CordTest, CharIteratorTraits) {
   static_assert(std::is_copy_constructible<absl::Cord::CharIterator>::value,
                 "");
   static_assert(std::is_copy_assignable<absl::Cord::CharIterator>::value, "");
@@ -1700,7 +1700,7 @@ static void VerifyCharIterator(const absl::Cord& cord) {
   }
 }
 
-TEST(CordCharIterator, Operations) {
+TEST_P(CordTest, CharIteratorOperations) {
   absl::Cord empty_cord;
   VerifyCharIterator(empty_cord);
 
@@ -1729,6 +1729,41 @@ TEST(CordCharIterator, Operations) {
   VerifyCharIterator(subcords);
 }
 
+TEST_P(CordTest, CharIteratorAdvanceAndRead) {
+  // Create a Cord holding 6 flats of 2500 bytes each, and then iterate over it
+  // reading 150, 1500, 2500 and 3000 bytes. This will result in all possible
+  // partial, full and straddled read combinations including reads below
+  // kMaxBytesToCopy. b/197776822 surfaced a bug for a specific partial, small
+  // read 'at end' on Cord which caused a failure on attempting to read past the
+  // end in CordRepBtreeReader which was not covered by any existing test.
+  constexpr int kBlocks = 6;
+  constexpr size_t kBlockSize = 2500;
+  constexpr size_t kChunkSize1 = 1500;
+  constexpr size_t kChunkSize2 = 2500;
+  constexpr size_t kChunkSize3 = 3000;
+  constexpr size_t kChunkSize4 = 150;
+  RandomEngine rng;
+  std::string data = RandomLowercaseString(&rng, kBlocks * kBlockSize);
+  absl::Cord cord;
+  for (int i = 0; i < kBlocks; ++i) {
+    const std::string block = data.substr(i * kBlockSize, kBlockSize);
+    cord.Append(absl::Cord(block));
+  }
+
+  for (size_t chunk_size :
+       {kChunkSize1, kChunkSize2, kChunkSize3, kChunkSize4}) {
+    absl::Cord::CharIterator it = cord.char_begin();
+    size_t offset = 0;
+    while (offset < data.length()) {
+      const size_t n = std::min<size_t>(data.length() - offset, chunk_size);
+      absl::Cord chunk = cord.AdvanceAndRead(&it, n);
+      ASSERT_EQ(chunk.size(), n);
+      ASSERT_EQ(chunk.Compare(data.substr(offset, n)), 0);
+      offset += n;
+    }
+  }
+}
+
 TEST_P(CordTest, StreamingOutput) {
   absl::Cord c =
       absl::MakeFragmentedCord({"A ", "small ", "fragmented ", "Cord", "."});
@@ -1778,7 +1813,7 @@ TEST_P(CordTest, Format) {
   EXPECT_EQ(c, "There were 0003 little pigs.And 1   bad wolf!");
 }
 
-TEST(CordDeathTest, Hardening) {
+TEST_P(CordTest, Hardening) {
   absl::Cord cord("hello");
   // These statement should abort the program in all builds modes.
   EXPECT_DEATH_IF_SUPPORTED(cord.RemovePrefix(6), "");
diff --git a/absl/strings/internal/cord_rep_btree_reader.cc b/absl/strings/internal/cord_rep_btree_reader.cc
index 3ba43144..5dc76966 100644
--- a/absl/strings/internal/cord_rep_btree_reader.cc
+++ b/absl/strings/internal/cord_rep_btree_reader.cc
@@ -52,14 +52,14 @@ absl::string_view CordRepBtreeReader::Read(size_t n, size_t chunk_size,
   // data, calling `navigator_.Current()` is not safe before checking if we
   // already consumed all remaining data.
   const size_t consumed_by_read = n - chunk_size - result.n;
-  if (consumed_ + consumed_by_read >= length()) {
-    consumed_ = length();
+  if (consumed_by_read >= remaining_) {
+    remaining_ = 0;
     return {};
   }
 
   // We did not read all data, return remaining data from current edge.
   edge = navigator_.Current();
-  consumed_ += consumed_by_read + edge->length;
+  remaining_ -= consumed_by_read + edge->length;
   return CordRepBtree::EdgeData(edge).substr(result.n);
 }
 
diff --git a/absl/strings/internal/cord_rep_btree_reader.h b/absl/strings/internal/cord_rep_btree_reader.h
index c19fa43d..66e97f5d 100644
--- a/absl/strings/internal/cord_rep_btree_reader.h
+++ b/absl/strings/internal/cord_rep_btree_reader.h
@@ -31,9 +31,7 @@ namespace cord_internal {
 // References to the underlying data are returned as absl::string_view values.
 // The most typical use case is a forward only iteration over tree data.
 // The class also provides `Skip()`, `Seek()` and `Read()` methods similar to
-// CordRepBtreeNavigator that allow more advanced navigation. The class provides
-// a `consumed` property which contains the end offset of the chunk last
-// returned to the user which is useful in cord iteration logic.
+// CordRepBtreeNavigator that allow more advanced navigation.
 //
 // Example: iterate over all data inside a cord btree:
 //
@@ -61,9 +59,9 @@ namespace cord_internal {
 //     absl::string_view sv = reader.Next();
 //   }
 //
-// It is important to notice that `consumed` represents the end position of the
-// last data edge returned to the caller, not the cumulative data returned to
-// the caller which can be less in cases of skipping or seeking over data.
+// It is important to notice that `remaining` is based on the end position of
+// the last data edge returned to the caller, not the cumulative data returned
+// to the caller which can be less in cases of skipping or seeking over data.
 //
 // For example, consider a cord btree with five data edges: "abc", "def", "ghi",
 // "jkl" and "mno":
@@ -71,14 +69,12 @@ namespace cord_internal {
 //   absl::string_view sv;
 //   CordRepBtreeReader reader;
 //
-//   sv = reader.Init(tree); // sv = "abc", reader.consumed() = 3
-//   sv = reader.Skip(4);    // sv = "hi",  reader.consumed() = 9
-//   sv = reader.Skip(2);    // sv = "l",   reader.consumed() = 12
-//   sv = reader.Next();     // sv = "mno", reader.consumed() = 15
+//   sv = reader.Init(tree); // sv = "abc", remaining = 12
+//   sv = reader.Skip(4);    // sv = "hi",  remaining = 6
+//   sv = reader.Skip(2);    // sv = "l",   remaining = 3
+//   sv = reader.Next();     // sv = "mno", remaining = 0
+//   sv = reader.Seek(1);    // sv = "bc", remaining = 12
 //
-// In the above example, `reader.consumed()` reflects the data edges iterated
-// over or skipped by the reader, not the amount of data 'consumed' by the
-// caller.
 class CordRepBtreeReader {
  public:
   using ReadResult = CordRepBtreeNavigator::ReadResult;
@@ -98,13 +94,14 @@ class CordRepBtreeReader {
   // Requires that the current instance is not empty.
   size_t length() const;
 
-  // Returns the end offset of the last navigated to chunk, which represents the
-  // total bytes 'consumed' relative to the start of the tree. The returned
-  // value is never zero. For example, initializing a reader with a tree with a
-  // first data edge of 19 bytes will return `consumed() = 19`. See also the
-  // class comments on the meaning of `consumed`.
-  // Requires that the current instance is not empty.
-  size_t consumed() const;
+  // Returns the number of remaining bytes available for iteration, which is the
+  // number of bytes directly following the end of the last chunk returned.
+  // This value will be zero if we iterated over the last edge in the bound
+  // tree, in which case any call to Next() or Skip() will return an empty
+  // string_view reflecting the EOF state.
+  // Note that a call to `Seek()` resets `remaining` to a value based on the
+  // end position of the chunk returned by that call.
+  size_t remaining() const { return remaining_; }
 
   // Resets this instance to an empty value.
   void Reset() { navigator_.Reset(); }
@@ -157,7 +154,7 @@ class CordRepBtreeReader {
   absl::string_view Seek(size_t offset);
 
  private:
-  size_t consumed_;
+  size_t remaining_ = 0;
   CordRepBtreeNavigator navigator_;
 };
 
@@ -166,23 +163,18 @@ inline size_t CordRepBtreeReader::length() const {
   return btree()->length;
 }
 
-inline size_t CordRepBtreeReader::consumed() const {
-  assert(btree() != nullptr);
-  return consumed_;
-}
-
 inline absl::string_view CordRepBtreeReader::Init(CordRepBtree* tree) {
   assert(tree != nullptr);
   const CordRep* edge = navigator_.InitFirst(tree);
-  consumed_ = edge->length;
+  remaining_ = tree->length - edge->length;;
   return CordRepBtree::EdgeData(edge);
 }
 
 inline absl::string_view CordRepBtreeReader::Next() {
-  assert(consumed() < length());
+  if (remaining_ == 0) return {};
   const CordRep* edge = navigator_.Next();
   assert(edge != nullptr);
-  consumed_ += edge->length;
+  remaining_ -= edge->length;
   return CordRepBtree::EdgeData(edge);
 }
 
@@ -192,23 +184,23 @@ inline absl::string_view CordRepBtreeReader::Skip(size_t skip) {
   const size_t edge_length = navigator_.Current()->length;
   CordRepBtreeNavigator::Position pos = navigator_.Skip(skip + edge_length);
   if (ABSL_PREDICT_FALSE(pos.edge == nullptr)) {
-    consumed_ = length();
+    remaining_ = 0;
     return {};
   }
   // The combined length of all edges skipped before `pos.edge` is `skip -
   // pos.offset`, all of which are 'consumed', as well as the current edge.
-  consumed_ += skip - pos.offset + pos.edge->length;
+  remaining_ -= skip - pos.offset + pos.edge->length;
   return CordRepBtree::EdgeData(pos.edge).substr(pos.offset);
 }
 
 inline absl::string_view CordRepBtreeReader::Seek(size_t offset) {
   const CordRepBtreeNavigator::Position pos = navigator_.Seek(offset);
   if (ABSL_PREDICT_FALSE(pos.edge == nullptr)) {
-    consumed_ = length();
+    remaining_ = 0;
     return {};
   }
   absl::string_view chunk = CordRepBtree::EdgeData(pos.edge).substr(pos.offset);
-  consumed_ = offset + chunk.length();
+  remaining_ = length() - offset - chunk.length();
   return chunk;
 }
 
diff --git a/absl/strings/internal/cord_rep_btree_reader_test.cc b/absl/strings/internal/cord_rep_btree_reader_test.cc
index 44d3365f..9b27a81f 100644
--- a/absl/strings/internal/cord_rep_btree_reader_test.cc
+++ b/absl/strings/internal/cord_rep_btree_reader_test.cc
@@ -58,22 +58,26 @@ TEST(CordRepBtreeReaderTest, Next) {
     CordRepBtree* node = CordRepBtreeFromFlats(flats);
 
     CordRepBtreeReader reader;
+    size_t remaining = data.length();
     absl::string_view chunk = reader.Init(node);
     EXPECT_THAT(chunk, Eq(data.substr(0, chunk.length())));
 
-    size_t consumed = chunk.length();
-    EXPECT_THAT(reader.consumed(), Eq(consumed));
+    remaining -= chunk.length();
+    EXPECT_THAT(reader.remaining(), Eq(remaining));
 
-    while (consumed < data.length()) {
+    while (remaining > 0) {
+      const size_t offset = data.length() - remaining;
       chunk = reader.Next();
-      EXPECT_THAT(chunk, Eq(data.substr(consumed, chunk.length())));
+      EXPECT_THAT(chunk, Eq(data.substr(offset, chunk.length())));
 
-      consumed += chunk.length();
-      EXPECT_THAT(reader.consumed(), Eq(consumed));
+      remaining -= chunk.length();
+      EXPECT_THAT(reader.remaining(), Eq(remaining));
     }
 
-    EXPECT_THAT(consumed, Eq(data.length()));
-    EXPECT_THAT(reader.consumed(), Eq(data.length()));
+    EXPECT_THAT(reader.remaining(), Eq(0));
+
+    // Verify trying to read beyond EOF returns empty string_view
+    EXPECT_THAT(reader.Next(), testing::IsEmpty());
 
     CordRep::Unref(node);
   }
@@ -92,19 +96,22 @@ TEST(CordRepBtreeReaderTest, Skip) {
     for (size_t skip1 = 0; skip1 < data.length() - kChars; ++skip1) {
       for (size_t skip2 = 0; skip2 < data.length() - kChars; ++skip2) {
         CordRepBtreeReader reader;
+        size_t remaining = data.length();
         absl::string_view chunk = reader.Init(node);
-        size_t consumed = chunk.length();
+        remaining -= chunk.length();
 
         chunk = reader.Skip(skip1);
-        ASSERT_THAT(chunk, Eq(data.substr(consumed + skip1, chunk.length())));
-        consumed += chunk.length() + skip1;
-        ASSERT_THAT(reader.consumed(), Eq(consumed));
+        size_t offset = data.length() - remaining;
+        ASSERT_THAT(chunk, Eq(data.substr(offset + skip1, chunk.length())));
+        remaining -= chunk.length() + skip1;
+        ASSERT_THAT(reader.remaining(), Eq(remaining));
 
-        if (consumed >= data.length()) continue;
+        if (remaining == 0) continue;
 
-        size_t skip = std::min(data.length() - consumed - 1, skip2);
+        size_t skip = std::min(remaining - 1, skip2);
         chunk = reader.Skip(skip);
-        ASSERT_THAT(chunk, Eq(data.substr(consumed + skip, chunk.length())));
+        offset = data.length() - remaining;
+        ASSERT_THAT(chunk, Eq(data.substr(offset + skip, chunk.length())));
       }
     }
 
@@ -118,7 +125,7 @@ TEST(CordRepBtreeReaderTest, SkipBeyondLength) {
   CordRepBtreeReader reader;
   reader.Init(tree);
   EXPECT_THAT(reader.Skip(100), IsEmpty());
-  EXPECT_THAT(reader.consumed(), Eq(6));
+  EXPECT_THAT(reader.remaining(), Eq(0));
   CordRep::Unref(tree);
 }
 
@@ -138,7 +145,8 @@ TEST(CordRepBtreeReaderTest, Seek) {
       absl::string_view chunk = reader.Seek(seek);
       ASSERT_THAT(chunk, Not(IsEmpty()));
       ASSERT_THAT(chunk, Eq(data.substr(seek, chunk.length())));
-      ASSERT_THAT(reader.consumed(), Eq(seek + chunk.length()));
+      ASSERT_THAT(reader.remaining(),
+                  Eq(data.length() - seek - chunk.length()));
     }
 
     CordRep::Unref(node);
@@ -151,9 +159,9 @@ TEST(CordRepBtreeReaderTest, SeekBeyondLength) {
   CordRepBtreeReader reader;
   reader.Init(tree);
   EXPECT_THAT(reader.Seek(6), IsEmpty());
-  EXPECT_THAT(reader.consumed(), Eq(6));
+  EXPECT_THAT(reader.remaining(), Eq(0));
   EXPECT_THAT(reader.Seek(100), IsEmpty());
-  EXPECT_THAT(reader.consumed(), Eq(6));
+  EXPECT_THAT(reader.remaining(), Eq(0));
   CordRep::Unref(tree);
 }
 
@@ -171,7 +179,7 @@ TEST(CordRepBtreeReaderTest, Read) {
   chunk = reader.Read(0, chunk.length(), tree);
   EXPECT_THAT(tree, Eq(nullptr));
   EXPECT_THAT(chunk, Eq("abcde"));
-  EXPECT_THAT(reader.consumed(), Eq(5));
+  EXPECT_THAT(reader.remaining(), Eq(10));
   EXPECT_THAT(reader.Next(), Eq("fghij"));
 
   // Read in full
@@ -180,7 +188,7 @@ TEST(CordRepBtreeReaderTest, Read) {
   EXPECT_THAT(tree, Ne(nullptr));
   EXPECT_THAT(CordToString(tree), Eq("abcdefghijklmno"));
   EXPECT_THAT(chunk, Eq(""));
-  EXPECT_THAT(reader.consumed(), Eq(15));
+  EXPECT_THAT(reader.remaining(), Eq(0));
   CordRep::Unref(tree);
 
   // Read < chunk bytes
@@ -189,7 +197,7 @@ TEST(CordRepBtreeReaderTest, Read) {
   ASSERT_THAT(tree, Ne(nullptr));
   EXPECT_THAT(CordToString(tree), Eq("abc"));
   EXPECT_THAT(chunk, Eq("de"));
-  EXPECT_THAT(reader.consumed(), Eq(5));
+  EXPECT_THAT(reader.remaining(), Eq(10));
   EXPECT_THAT(reader.Next(), Eq("fghij"));
   CordRep::Unref(tree);
 
@@ -199,7 +207,7 @@ TEST(CordRepBtreeReaderTest, Read) {
   ASSERT_THAT(tree, Ne(nullptr));
   EXPECT_THAT(CordToString(tree), Eq("cd"));
   EXPECT_THAT(chunk, Eq("e"));
-  EXPECT_THAT(reader.consumed(), Eq(5));
+  EXPECT_THAT(reader.remaining(), Eq(10));
   EXPECT_THAT(reader.Next(), Eq("fghij"));
   CordRep::Unref(tree);
 
@@ -209,7 +217,7 @@ TEST(CordRepBtreeReaderTest, Read) {
   ASSERT_THAT(tree, Ne(nullptr));
   EXPECT_THAT(CordToString(tree), Eq("fgh"));
   EXPECT_THAT(chunk, Eq("ij"));
-  EXPECT_THAT(reader.consumed(), Eq(10));
+  EXPECT_THAT(reader.remaining(), Eq(5));
   EXPECT_THAT(reader.Next(), Eq("klmno"));
   CordRep::Unref(tree);
 
@@ -219,7 +227,7 @@ TEST(CordRepBtreeReaderTest, Read) {
   ASSERT_THAT(tree, Ne(nullptr));
   EXPECT_THAT(CordToString(tree), Eq("cdefghijklmn"));
   EXPECT_THAT(chunk, Eq("o"));
-  EXPECT_THAT(reader.consumed(), Eq(15));
+  EXPECT_THAT(reader.remaining(), Eq(0));
   CordRep::Unref(tree);
 
   // Read across chunks landing on exact edge boundary
@@ -228,7 +236,7 @@ TEST(CordRepBtreeReaderTest, Read) {
   ASSERT_THAT(tree, Ne(nullptr));
   EXPECT_THAT(CordToString(tree), Eq("cdefghij"));
   EXPECT_THAT(chunk, Eq("klmno"));
-  EXPECT_THAT(reader.consumed(), Eq(15));
+  EXPECT_THAT(reader.remaining(), Eq(0));
   CordRep::Unref(tree);
 
   CordRep::Unref(node);
@@ -264,7 +272,7 @@ TEST(CordRepBtreeReaderTest, ReadExhaustive) {
 
         consumed += n;
         remaining -= n;
-        EXPECT_THAT(reader.consumed(), Eq(consumed + chunk.length()));
+        EXPECT_THAT(reader.remaining(), Eq(remaining - chunk.length()));
 
         if (remaining > 0) {
           ASSERT_FALSE(chunk.empty());