Improved iterator for persistent memory allocator.

base/metrics/persistent_memory_allocator_unittest.cc

Index: base/metrics/persistent_memory_allocator_unittest.cc
diff --git a/base/metrics/persistent_memory_allocator_unittest.cc b/base/metrics/persistent_memory_allocator_unittest.cc
index 6ec5a032ab2a0e85d3e01a7515dc0d02ef01b125..70e13921fabfb2989164648262bd88f2b91cb15c 100644
--- a/base/metrics/persistent_memory_allocator_unittest.cc
+++ b/base/metrics/persistent_memory_allocator_unittest.cc
@@ -14,6 +14,8 @@
 #include "base/metrics/histogram.h"
 #include "base/rand_util.h"
 #include "base/strings/safe_sprintf.h"
+#include "base/synchronization/condition_variable.h"
+#include "base/synchronization/lock.h"
 #include "base/threading/simple_thread.h"
 #include "testing/gmock/include/gmock/gmock.h"
 
@@ -69,12 +71,11 @@ class PersistentMemoryAllocatorTest : public testing::Test {
   }
 
   unsigned CountIterables() {
-    PersistentMemoryAllocator::Iterator iter;
+    PersistentMemoryAllocator::Iterator iter(allocator_.get());
     uint32_t type;
     unsigned count = 0;
-    for (allocator_->CreateIterator(&iter);
-         allocator_->GetNextIterable(&iter, &type) != 0;) {
-      count++;
+    while (iter.GetNext(&type) != 0) {
+      ++count;
     }
     return count;
   }
@@ -115,14 +116,13 @@ TEST_F(PersistentMemoryAllocatorTest, AllocateAndIterate) {
   EXPECT_GT(meminfo0.free, meminfo1.free);
 
   // Ensure that the test-object can be made iterable.
-  PersistentMemoryAllocator::Iterator iter;
+  PersistentMemoryAllocator::Iterator iter1a(allocator_.get());
   uint32_t type;
-  allocator_->CreateIterator(&iter);
-  EXPECT_EQ(0U, allocator_->GetNextIterable(&iter, &type));
+  EXPECT_EQ(0U, iter1a.GetNext(&type));
   allocator_->MakeIterable(block1);
-  EXPECT_EQ(block1, allocator_->GetNextIterable(&iter, &type));
+  EXPECT_EQ(block1, iter1a.GetNext(&type));
   EXPECT_EQ(1U, type);
-  EXPECT_EQ(0U, allocator_->GetNextIterable(&iter, &type));
+  EXPECT_EQ(0U, iter1a.GetNext(&type));
 
   // Create second test-object and ensure everything is good and it cannot
   // be confused with test-object of another type.
@@ -140,14 +140,14 @@ TEST_F(PersistentMemoryAllocatorTest, AllocateAndIterate) {
 
   // Ensure that second test-object can also be made iterable.
   allocator_->MakeIterable(block2);
-  EXPECT_EQ(block2, allocator_->GetNextIterable(&iter, &type));
+  EXPECT_EQ(block2, iter1a.GetNext(&type));
   EXPECT_EQ(2U, type);
-  EXPECT_EQ(0U, allocator_->GetNextIterable(&iter, &type));
+  EXPECT_EQ(0U, iter1a.GetNext(&type));
 
   // Check that iteration can begin after an arbitrary location.
-  allocator_->CreateIterator(&iter, block1);
-  EXPECT_EQ(block2, allocator_->GetNextIterable(&iter, &type));
-  EXPECT_EQ(0U, allocator_->GetNextIterable(&iter, &type));
+  PersistentMemoryAllocator::Iterator iter1b(allocator_.get(), block1);
+  EXPECT_EQ(block2, iter1b.GetNext(&type));
+  EXPECT_EQ(0U, iter1b.GetNext(&type));
 
   // Ensure nothing has gone noticably wrong.
   EXPECT_FALSE(allocator_->IsFull());
@@ -192,10 +192,10 @@ TEST_F(PersistentMemoryAllocatorTest, AllocateAndIterate) {
   EXPECT_NE(allocator2->allocs_histogram_, allocator_->allocs_histogram_);
 
   // Ensure that iteration and access through second allocator works.
-  allocator2->CreateIterator(&iter);
-  EXPECT_EQ(block1, allocator2->GetNextIterable(&iter, &type));
-  EXPECT_EQ(block2, allocator2->GetNextIterable(&iter, &type));
-  EXPECT_EQ(0U, allocator2->GetNextIterable(&iter, &type));
+  PersistentMemoryAllocator::Iterator iter2(allocator2.get());
+  EXPECT_EQ(block1, iter2.GetNext(&type));
+  EXPECT_EQ(block2, iter2.GetNext(&type));
+  EXPECT_EQ(0U, iter2.GetNext(&type));
   EXPECT_NE(nullptr, allocator2->GetAsObject<TestObject1>(block1, 1));
   EXPECT_NE(nullptr, allocator2->GetAsObject<TestObject2>(block2, 2));
 
@@ -208,12 +208,17 @@ TEST_F(PersistentMemoryAllocatorTest, AllocateAndIterate) {
   EXPECT_FALSE(allocator3->allocs_histogram_);
 
   // Ensure that iteration and access through third allocator works.
-  allocator3->CreateIterator(&iter);
-  EXPECT_EQ(block1, allocator3->GetNextIterable(&iter, &type));
-  EXPECT_EQ(block2, allocator3->GetNextIterable(&iter, &type));
-  EXPECT_EQ(0U, allocator3->GetNextIterable(&iter, &type));
+  PersistentMemoryAllocator::Iterator iter3(allocator3.get());
+  EXPECT_EQ(block1, iter3.GetNext(&type));
+  EXPECT_EQ(block2, iter3.GetNext(&type));
+  EXPECT_EQ(0U, iter3.GetNext(&type));
   EXPECT_NE(nullptr, allocator3->GetAsObject<TestObject1>(block1, 1));
   EXPECT_NE(nullptr, allocator3->GetAsObject<TestObject2>(block2, 2));
+
+  // Ensure that GetNextOfType works.
+  PersistentMemoryAllocator::Iterator iter1c(allocator_.get());
+  EXPECT_EQ(block2, iter1c.GetNextOfType(2));
+  EXPECT_EQ(0U, iter1c.GetNextOfType(2));
 }
 
 TEST_F(PersistentMemoryAllocatorTest, PageTest) {
@@ -305,6 +310,103 @@ TEST_F(PersistentMemoryAllocatorTest, ParallelismTest) {
             t5.iterable());
 }
 
+// A simple thread that counts objects by iterating through an allocator.
+class CounterThread : public SimpleThread {
+ public:
+  CounterThread(const std::string& name,
+                PersistentMemoryAllocator::Iterator* iterator,
+                Lock* lock,
+                ConditionVariable* condition)
+      : SimpleThread(name, Options()),
+        iterator_(iterator),
+        lock_(lock),
+        condition_(condition),
+        count_(0) {}
+
+  void Run() override {
+    // Wait so all threads can start at approximately the same time.
+    // Best performance comes from releasing a single worker which then
+    // releases the next, etc., etc.
+    {
+      AutoLock autolock(*lock_);
+      condition_->Wait();
+      condition_->Signal();
+    }
+
+    uint32_t type;
+    while (iterator_->GetNext(&type) != 0) {
+      ++count_;
+    }
+  }
+
+  unsigned count() { return count_; }
+
+ private:
+  PersistentMemoryAllocator::Iterator* iterator_;
+  Lock* lock_;
+  ConditionVariable* condition_;
+  unsigned count_;
+};
+
+// Ensure that parallel iteration returns the same number of objects as
+// single-threaded iteration.
+TEST_F(PersistentMemoryAllocatorTest, IteratorParallelismTest) {
+  // Fill the memory segment with random allocations.
+  unsigned iterable_count = 0;
+  for (;;) {
+    uint32_t size = RandInt(1, 99);
+    uint32_t type = RandInt(100, 999);
+    Reference block = allocator_->Allocate(size, type);
+    if (!block)
+      break;
+    allocator_->MakeIterable(block);
+    ++iterable_count;
+  }
+  EXPECT_FALSE(allocator_->IsCorrupt());
+  EXPECT_TRUE(allocator_->IsFull());
+  EXPECT_EQ(iterable_count, CountIterables());
+
+  PersistentMemoryAllocator::Iterator iter(allocator_.get());
+  Lock lock;
+  ConditionVariable condition(&lock);
+
+  CounterThread t1("t1", &iter, &lock, &condition);
+  CounterThread t2("t2", &iter, &lock, &condition);
+  CounterThread t3("t3", &iter, &lock, &condition);
+  CounterThread t4("t4", &iter, &lock, &condition);
+  CounterThread t5("t5", &iter, &lock, &condition);
+
+  t1.Start();
+  t2.Start();
+  t3.Start();
+  t4.Start();
+  t5.Start();
+
+  // This will release all the waiting threads.
+  condition.Signal();
+
+  t1.Join();
+  t2.Join();
+  t3.Join();
+  t4.Join();
+  t5.Join();
+
+  EXPECT_EQ(iterable_count,
+            t1.count() + t2.count() + t3.count() + t4.count() + t5.count());
+
+#if 0
+  // These ensure that the threads don't run sequentially. It shouldn't be
+  // enabled in general because it could lead to a flaky test if it happens
+  // simply by chance but it is useful during development to ensure that the
+  // test is working correctly.
+  EXPECT_NE(iterable_count, t1.count());
+  EXPECT_NE(iterable_count, t2.count());
+  EXPECT_NE(iterable_count, t3.count());
+  EXPECT_NE(iterable_count, t4.count());
+  EXPECT_NE(iterable_count, t5.count());
+#endif
+}
+
 // This test doesn't verify anything other than it doesn't crash. Its goal
 // is to find coding errors that aren't otherwise tested for, much like a
 // "fuzzer" would.
@@ -427,12 +529,11 @@ TEST(SharedPersistentMemoryAllocatorTest, CreationTest) {
   EXPECT_FALSE(shalloc2.IsFull());
   EXPECT_FALSE(shalloc2.IsCorrupt());
 
-  PersistentMemoryAllocator::Iterator iter2;
+  PersistentMemoryAllocator::Iterator iter2(&shalloc2);
   uint32_t type;
-  shalloc2.CreateIterator(&iter2);
-  EXPECT_EQ(r123, shalloc2.GetNextIterable(&iter2, &type));
-  EXPECT_EQ(r789, shalloc2.GetNextIterable(&iter2, &type));
-  EXPECT_EQ(0U, shalloc2.GetNextIterable(&iter2, &type));
+  EXPECT_EQ(r123, iter2.GetNext(&type));
+  EXPECT_EQ(r789, iter2.GetNext(&type));
+  EXPECT_EQ(0U, iter2.GetNext(&type));
 
   EXPECT_EQ(123U, shalloc2.GetType(r123));
   EXPECT_EQ(654U, shalloc2.GetType(r456));
@@ -454,11 +555,10 @@ TEST(SharedPersistentMemoryAllocatorTest, CreationTest) {
   EXPECT_FALSE(shalloc3.IsFull());
   EXPECT_FALSE(shalloc3.IsCorrupt());
 
-  PersistentMemoryAllocator::Iterator iter3;
-  shalloc3.CreateIterator(&iter3);
-  EXPECT_EQ(r123, shalloc3.GetNextIterable(&iter3, &type));
-  EXPECT_EQ(r789, shalloc3.GetNextIterable(&iter3, &type));
-  EXPECT_EQ(0U, shalloc3.GetNextIterable(&iter3, &type));
+  PersistentMemoryAllocator::Iterator iter3(&shalloc3);
+  EXPECT_EQ(r123, iter3.GetNext(&type));
+  EXPECT_EQ(r789, iter3.GetNext(&type));
+  EXPECT_EQ(0U, iter3.GetNext(&type));
 
   EXPECT_EQ(123U, shalloc3.GetType(r123));
   EXPECT_EQ(654U, shalloc3.GetType(r456));
@@ -473,7 +573,7 @@ TEST(SharedPersistentMemoryAllocatorTest, CreationTest) {
   Reference obj = shalloc3.Allocate(42, 42);
   ASSERT_TRUE(obj);
   shalloc3.MakeIterable(obj);
-  EXPECT_EQ(obj, shalloc2.GetNextIterable(&iter2, &type));
+  EXPECT_EQ(obj, iter2.GetNext(&type));
   EXPECT_EQ(42U, type);
 }
 
@@ -517,12 +617,11 @@ TEST(FilePersistentMemoryAllocatorTest, CreationTest) {
   EXPECT_FALSE(file.IsFull());
   EXPECT_FALSE(file.IsCorrupt());
 
-  PersistentMemoryAllocator::Iterator iter;
+  PersistentMemoryAllocator::Iterator iter(&file);
   uint32_t type;
-  file.CreateIterator(&iter);
-  EXPECT_EQ(r123, file.GetNextIterable(&iter, &type));
-  EXPECT_EQ(r789, file.GetNextIterable(&iter, &type));
-  EXPECT_EQ(0U, file.GetNextIterable(&iter, &type));
+  EXPECT_EQ(r123, iter.GetNext(&type));
+  EXPECT_EQ(r789, iter.GetNext(&type));
+  EXPECT_EQ(0U, iter.GetNext(&type));
 
   EXPECT_EQ(123U, file.GetType(r123));
   EXPECT_EQ(654U, file.GetType(r456));
@@ -542,8 +641,8 @@ TEST(FilePersistentMemoryAllocatorTest, AcceptableTest) {
   FilePath file_path_base = temp_dir.path().AppendASCII("persistent_memory_");
 
   LocalPersistentMemoryAllocator local(TEST_MEMORY_SIZE, TEST_ID, "");
-  local.Allocate(1, 1);
-  local.Allocate(11, 11);
+  local.MakeIterable(local.Allocate(1, 1));
+  local.MakeIterable(local.Allocate(11, 11));
   const size_t minsize = local.used();
   std::unique_ptr<char[]> garbage(new char[minsize]);
   RandBytes(garbage.get(), minsize);
@@ -569,12 +668,10 @@ TEST(FilePersistentMemoryAllocatorTest, AcceptableTest) {
       // error messages warning about about a corrupted memory segment.
       FilePersistentMemoryAllocator allocator(std::move(mmfile), 0, "");
       // Also make sure that iteration doesn't crash.
-      PersistentMemoryAllocator::Iterator iter;
-      allocator.CreateIterator(&iter);
-      for (;;) {
-        Reference ref = allocator.GetNextIterable(&iter, 0);
-        if (!ref)
-          break;
+      PersistentMemoryAllocator::Iterator iter(&allocator);
+      uint32_t type_id;
+      Reference ref;
+      while ((ref = iter.GetNext(&type_id)) != 0) {
         const char* data = allocator.GetAsObject<char>(ref, 0);
         uint32_t type = allocator.GetType(ref);
         size_t size = allocator.GetAllocSize(ref);
@@ -582,9 +679,9 @@ TEST(FilePersistentMemoryAllocatorTest, AcceptableTest) {
         (void)data;
         (void)type;
         (void)size;
-        // Ensure that corruption-detected flag gets properly set.
-        EXPECT_EQ(filesize != minsize, allocator.IsCorrupt());
       }
+      // Ensure that short files are detected as corrupt and full files are not.
+      EXPECT_EQ(filesize != minsize, allocator.IsCorrupt());
     } else {
       // For filesize >= minsize, the file must be acceptable. This
       // else clause (file-not-acceptable) should be reached only if