New cache for the activity tracker.

base/debug/activity_tracker_unittest.cc

 // Copyright 2016 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "base/debug/activity_tracker.h"
 
 #include <memory>
 
 #include "base/bind.h"
 #include "base/files/file.h"
 #include "base/files/file_util.h"
 #include "base/files/memory_mapped_file.h"
 #include "base/files/scoped_temp_dir.h"
 #include "base/memory/ptr_util.h"
 #include "base/pending_task.h"
+#include "base/rand_util.h"
 #include "base/synchronization/condition_variable.h"
 #include "base/synchronization/lock.h"
 #include "base/synchronization/spin_wait.h"
+#include "base/threading/platform_thread.h"
 #include "base/threading/simple_thread.h"
 #include "base/time/time.h"
 #include "testing/gtest/include/gtest/gtest.h"
 
 namespace base {
 namespace debug {
 
 namespace {
 
 class TestActivityTracker : public ThreadActivityTracker {
  public:
   TestActivityTracker(std::unique_ptr<char[]> memory, size_t mem_size)
       : ThreadActivityTracker(memset(memory.get(), 0, mem_size), mem_size),
         mem_segment_(std::move(memory)) {}
 
   ~TestActivityTracker() override {}
 
  private:
   std::unique_ptr<char[]> mem_segment_;
 };
 
+
+// The interval between which the Stack threads will wait for the stack to
+// become full or empty. It's prime so that it won't correspond to any other
+// interval (except itself).
+const int kStackTestOperationInterval = 997;
+
+class StackPushThread : public SimpleThread {
+ public:
+  StackPushThread(LockFreeSimpleStack<int>* stack, int count)
+      : SimpleThread("StackPush", Options()), stack_(stack), count_(count) {}
+  ~StackPushThread() override {}
+
+  void Run() override {
+    int yield_after = RandInt(1, stack_->size() * 2);
+    for (int i = 0; i < count_; ++i) {
+      // Two ways of pushing: check for full first or check for failed push.
+      if (i % 2 == 0) {
+        // Will fail if full; keep trying.
+        while (!stack_->push(i))
+          ;
+      } else {
+        // This is valid because there is exactly one thread pushing.
+        while (stack_->full())
+          ;
+        DCHECK(stack_->push(i));
+      }
+
+      // Take a break once in a while.
+      if (--yield_after <= 0) {
+        PlatformThread::YieldCurrentThread();
+        yield_after = RandInt(1, stack_->size() * 2);
+      }
+
+      // Every so often, wait for the stack to empty.
+      if (i < count_ - kStackTestOperationInterval &&
+          i % kStackTestOperationInterval == kStackTestOperationInterval - 1) {
+        while (!stack_->empty())
+          ;
+      }
+    }
+  }
+
+ private:
+  LockFreeSimpleStack<int>* const stack_;
+  const int count_;
+
+  DISALLOW_COPY_AND_ASSIGN(StackPushThread);
+};
+
+class StackPopThread : public SimpleThread {
+ public:
+  StackPopThread(LockFreeSimpleStack<int>* stack, int count)
+      : SimpleThread("StackPop", Options()), stack_(stack), count_(count) {}
+  ~StackPopThread() override {}
+
+  void Run() override {
+    int yield_after = RandInt(1, stack_->size() * 2);
+    for (int i = 0; i < count_; ++i) {
+      int popped;
+      // Two ways of popping: check for empty first or check for invalid return.
+      if (i % 2 == 0) {
+        // Will return "invalid" if empty; keep trying.
+        while ((popped = stack_->pop()) < 0)
+          ;
+      } else {
+        // This is valid only because there is exactly one thread popping.
+        while (stack_->empty())
+          ;
+        popped = stack_->pop();
+      }
+      DCHECK_LE(0, popped);
+      DCHECK_GT(i + static_cast<int>(stack_->size()), popped);
+
+      // Take a break once in a while.
+      if (--yield_after <= 0) {
+        PlatformThread::YieldCurrentThread();
+        yield_after = RandInt(1, stack_->size() * 2);
+      }
+
+      // Every so often, wait for the stack to fill.
+      if (i < count_ - kStackTestOperationInterval &&
+          i % kStackTestOperationInterval == kStackTestOperationInterval / 2) {
+        while (!stack_->full())
+          ;
+      }
+    }
+  }
+
+ private:
+  LockFreeSimpleStack<int>* const stack_;
+  const int count_;
+
+  DISALLOW_COPY_AND_ASSIGN(StackPopThread);
+};
+
+class StackParallelThread : public SimpleThread {
+ public:
+  StackParallelThread(LockFreeSimpleStack<int>* stack,
+                      int thread_number,
+                      bool push_not_pop,
+                      std::atomic<char>* pending,
+                      int count)
+      : SimpleThread(std::string("Stack") + (push_not_pop ? "Push" : "Pop") +
+                         static_cast<char>('A' + thread_number),
+                     Options()),
+        stack_(stack),
+        pending_(pending),
+        push_not_pop_(push_not_pop),
+        count_(count) {}
+  ~StackParallelThread() override {}
+
+  void Run() override {
+    int yield_after = RandInt(1, stack_->size() * 2);
+
+    for (int i = 0; i < count_; ++i) {
+      if (push_not_pop_) {
+        while (!stack_->push(i))
+          ;
+        pending_[i].fetch_add(1);
+      } else {
+        int popped;
+        while ((popped = stack_->pop()) < 0)
+          ;
+        pending_[popped].fetch_sub(1);
+      }
+
+      // Take a break once in a while.
+      if (--yield_after <= 0) {
+        PlatformThread::YieldCurrentThread();
+        yield_after = RandInt(1, stack_->size() * 2);
+      }
+    }
+  }
+
+ private:
+  LockFreeSimpleStack<int>* const stack_;
+  std::atomic<char>* const pending_;
+  const bool push_not_pop_;
+  const int count_;
+
+  DISALLOW_COPY_AND_ASSIGN(StackParallelThread);
+};
+
 }  // namespace
 
 
+TEST(LockFreeSimpleStack, PushPopTest) {
+  LockFreeSimpleStack<int> stack(50U, -1);
+  ASSERT_EQ(50U, stack.size());
+  ASSERT_EQ(0U, stack.used());
+
+  stack.push(1001);
+  EXPECT_EQ(1U, stack.used());
+
+  stack.push(2002);
+  EXPECT_EQ(2U, stack.used());
+
+  int value = stack.pop();
+  EXPECT_EQ(2002, value);
+  EXPECT_EQ(1U, stack.used());
+
+  value = stack.pop();
+  EXPECT_EQ(1001, value);
+  EXPECT_EQ(0U, stack.used());
+
+  value = stack.pop();
+  ASSERT_EQ(-1, value);
+  ASSERT_TRUE(stack.empty());
+
+  // Test push/pop many times and in parallel.
+  const int kStackOperations = 1000000;
+  StackPushThread pusher(&stack, kStackOperations);
+  StackPopThread popper(&stack, kStackOperations);
+  pusher.Start();
+  popper.Start();
+  pusher.Join();
+  popper.Join();
+
+  // Test many push/pop threads.
+  const int kParallelThreads = 10;
+  const int kParallelOperations = kStackOperations / kParallelThreads;
+  std::unique_ptr<std::atomic<char>[]> pending(
+      new std::atomic<char>[kParallelOperations]);
+  for (int i = 0; i < kParallelOperations; ++i)
+    pending[i].store(0, std::memory_order_relaxed);
+  std::unique_ptr<StackParallelThread> pushers[kParallelThreads];
+  std::unique_ptr<StackParallelThread> poppers[kParallelThreads];
+  for (int t = 0; t < kParallelThreads; ++t) {
+    pushers[t].reset(new StackParallelThread(&stack, t, true, pending.get(),
+                                             kParallelOperations));
+    poppers[t].reset(new StackParallelThread(&stack, t, false, pending.get(),
+                                             kParallelOperations));
+  }
+  for (int t = 0; t < kParallelThreads; ++t) {
+    pushers[t]->Start();
+    poppers[t]->Start();
+  }
+  for (int t = 0; t < kParallelThreads; ++t) {
+    pushers[t]->Join();
+    poppers[t]->Join();
+  }
+  for (int i = 0; i < kParallelOperations; ++i)
+    EXPECT_EQ(0, static_cast<int>(pending[i].load(std::memory_order_relaxed)));
+}
+
+
 class ActivityTrackerTest : public testing::Test {
  public:
   const int kMemorySize = 1 << 10;  // 1MiB
   const int kStackSize  = 1 << 10;  // 1KiB
 
   ActivityTrackerTest() {}
 
   ~ActivityTrackerTest() override {
     GlobalActivityTracker* global_tracker = GlobalActivityTracker::Get();
     if (global_tracker) {
@@ skipping 12 matching lines @@
     if (!global_tracker)
       return 0;
     return global_tracker->thread_tracker_count_.load(
         std::memory_order_relaxed);
   }
 
   size_t GetGlobalInactiveTrackerCount() {
     GlobalActivityTracker* global_tracker = GlobalActivityTracker::Get();
     if (!global_tracker)
       return 0;
-    return global_tracker->available_memories_count_.load(
-        std::memory_order_relaxed);
+    return global_tracker->available_memories_.used();
   }
 
   static void DoNothing() {}
 };
 
 TEST_F(ActivityTrackerTest, PushPopTest) {
   std::unique_ptr<ThreadActivityTracker> tracker = CreateActivityTracker();
   ActivitySnapshot snapshot;
 
   ASSERT_TRUE(tracker->Snapshot(&snapshot));
@@ skipping 193 matching lines @@
   EXPECT_EQ(starting_inactive, GetGlobalInactiveTrackerCount());
 
   t2.Exit();
   t2.Join();
   EXPECT_EQ(starting_active, GetGlobalActiveTrackerCount());
   EXPECT_EQ(starting_inactive + 1, GetGlobalInactiveTrackerCount());
 }
 
 }  // namespace debug
 }  // namespace base