New cache for the activity tracker.

base/debug/activity_tracker.h

 // 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.
 
 // Activity tracking provides a low-overhead method of collecting information
 // about the state of the application for analysis both while it is running
 // and after it has terminated unexpectedly. Its primary purpose is to help
 // locate reasons the browser becomes unresponsive by providing insight into
 // what all the various threads and processes are (or were) doing.
 
 #ifndef BASE_DEBUG_ACTIVITY_TRACKER_H_
 #define BASE_DEBUG_ACTIVITY_TRACKER_H_
 
 // std::atomic is undesired due to performance issues when used as global
 // variables. There are no such instances here. This module uses the
 // PersistentMemoryAllocator which also uses std::atomic and is written
 // by the same author.
 #include <atomic>
 #include <memory>
 #include <string>
 #include <vector>
 
 #include "base/base_export.h"
 #include "base/location.h"
 #include "base/metrics/persistent_memory_allocator.h"
+#include "base/threading/platform_thread.h"
 #include "base/threading/thread_checker.h"
 #include "base/threading/thread_local_storage.h"
 
 namespace base {
 
 struct PendingTask;
 
 class FilePath;
 class Lock;
 class MemoryMappedFile;
 class PlatformThreadHandle;
 class Process;
 class WaitableEvent;
 
 namespace debug {
 
 class ThreadActivityTracker;
 
+
+//=============================================================================
+// This class provides a lock-free stack of any atomic type with the
+// limitation that there must be at least one "invalid" value. This is
+// built as a completely generic type and can (hopefully) be moved to a
+// more generally useful place in the future.
+template <typename T>
+class LockFreeSimpleStack {
+ public:
+  // Construct a simple lock-free stack with the specified |size| but
+  // not alowed to hold the |invalid_value|.
+  LockFreeSimpleStack(size_t size, T invalid_value)
+      : size_(size), invalid_value_(invalid_value), head_(0) {
+    DCHECK_LE(1U, size);
+
+    // Allocate memory for the stack value.
+    values_.reset(new std::atomic<T>[size_]);
+
+    // Ensure that the underlying atomics are also lock-free. This should
+    // evaluate to a constant at compile time and so produce no code, but
+    // a static_assert will not compile.
+    CHECK(head_.is_lock_free());
+    CHECK(values_[0].is_lock_free());
+
+    // All elements must be "invalid" to start in order for the push/pop
+    // operations to work.
+    for (size_t i = 0; i < size_; ++i)
+      values_[i].store(invalid_value_, std::memory_order_relaxed);
+  }
+
+  T invalid_value() { return invalid_value_; }
+  size_t size() { return size_; }
+  size_t used() { return (head_.load(std::memory_order_relaxed)); }
+  bool empty() { return used() == 0; }
+  bool full() { return used() == size_; }
+
+  // Adds a new |value| to the top of the stack and returns true on success
+  // or false if the stack was full.
+  bool push(T value);
+
+  // Retrieves the top value off the stack and returns it or the "invalid"
+  // value if the stack is empty.
+  T pop();
+
+ private:
+  const size_t size_;      // Size of the internal |values_|
+  const T invalid_value_;  // A value not allowed to be stored.
+
+  std::atomic<size_t> head_;  // Index of first empty slot; where to push.
+
+  // Array holding pushed values.
+  std::unique_ptr<std::atomic<T>[]> values_;
+
+  DISALLOW_COPY_AND_ASSIGN(LockFreeSimpleStack);
+};
+
+template <typename T>
+bool LockFreeSimpleStack<T>::push(T value) {
+  // Pushing the "invalid" value is not allowed; it would cause an infinite
+  // loop in pop.
+  CHECK_NE(invalid_value_, value);
+
+  // Get the head of the stack.
+  size_t head = head_.load(std::memory_order_relaxed);
+
+  // In short: allocate a slot at the head of the stack, write the value to
+  // it, try again if anything gets in the way.
+  while (true) {
+    DCHECK_LE(0U, head);
+    DCHECK_GE(size_, head);
+
+    // If the stack is full, fail.
+    if (head == size_)
+      return false;
+
+    // The "head" is the critical resource so allocate a slot from the
+    // |values_| buffer at its current location, acquiring the value there.
+    // A "weak" operation is used because it's relatively trivial to try
+    // this operation again.
+    size_t slot = head;
+    if (!head_.compare_exchange_weak(slot, head + 1,
+                                     std::memory_order_acquire,

[Alexander Potapenko, 2016/08/25 17:07:42]

I have a gut feeling that the memory ordering in exchange statements is wrong,
but I'm struggling to build an example proving that.

Let's say threads T1 and T2 are performing a push() and a pop() on the stack, so
the following operations are going to happen:
1. T1 loads H from head_, T1 stores H+1 to head_
2. T1 loads -1 from values_[H], T1 stores V to values_[H]
3. T2 loads H+1 from head_, T2 stores H to head_
4. T2 loads V from values_[H], T2 stores -1 to values_[H]

Right now the std::memory_order_acquire make sure that 2 cannot be ordered
before 1, and 4 cannot go before 3. However there are no guarantees on the
mutual order of 2 and 3 or 2 and 4.
Therefore it's possible that the accesses happen in the following order:
1-3-4-2, and the value loaded by T2 from values_[H] is stale.

This example is not really convincing, but if several threads are involved, it
occurs to me that an ABA is possible here.

[bcwhite, 2016/08/25 17:19:06]

In that ordering, #4 will read "invalid", yield the CPU, and retry.

ABA is certainly possible but I think its okay because all we care about is if
the slot is empty when we're trying to write to it (or not-empty when trying to
read).  It really doesn't matter how many times it switched in between.

+                                     std::memory_order_relaxed)) {
+      // The exchange will have loaded the latest |head_| into |slot|.
+      head = slot;
+      continue;
+    }
+
+    // Save the value being pushed to the reserved slot, overwriting the
+    // "invalid" value that should be there. If it's not, it's because the
+    // slot was released by a pop() but that method hasn't yet extracted
+    // the value. Wait for it to do so. Use a "strong" exchange to avoid
+    // mistakenly releasing the CPU.
+    T expected_value = invalid_value_;
+    while (!values_[slot].compare_exchange_strong(expected_value, value,
+                                                  std::memory_order_relaxed,
+                                                  std::memory_order_relaxed)) {
+      PlatformThread::YieldCurrentThread();
+      expected_value = invalid_value_;
+    }
+
+    // Success!
+    return true;
+  }
+}
+
+template <typename T>
+T LockFreeSimpleStack<T>::pop() {
+  // Get the head of the stack.
+  size_t head = head_.load(std::memory_order_relaxed);
+
+  // In short: deallocate a slot at the head of the stack, read the value from
+  // it, try again if anything gets in the way.
+  while (true) {
+    DCHECK_LE(0U, head);
+    DCHECK_GE(size_, head);
+
+    // If the stack is empty, fail.
+    if (head == 0)
+      return invalid_value_;
+
+    // The "head" is the critical resource so deallocate a slot from the
+    // |values_| buffer at its current location, acquiring the value there.
+    // A "weak" operation is used because it's relatively trivial to try
+    // this operation again.
+    size_t slot = head;
+    if (!head_.compare_exchange_weak(slot, head - 1,
+                                     std::memory_order_acquire,
+                                     std::memory_order_relaxed)) {
+      // The exchange will have loaded the latest |head_| into |slot|.
+      head = slot;
+      continue;
+    }
+    --slot;  // "head" is past-the-top
+
+    // Read a value from the top of the stack, writing the "invalid" value
+    // in its place. If the retrieved value is invalid then the slot was
+    // acquired by push() but that method hasn't yet written the value. Wait
+    // for it to do so.
+    T value;
+    while ((value = values_[slot].exchange(
+                invalid_value_, std::memory_order_relaxed)) == invalid_value_) {
+      PlatformThread::YieldCurrentThread();
+    }
+
+    // Success!
+    DCHECK_NE(invalid_value_, value);
+    return value;
+  }
+}
+//=============================================================================
+
+
 enum : int {
   // The maximum number of call-stack addresses stored per activity. This
   // cannot be changed without also changing the version number of the
   // structure. See kTypeIdActivityTracker in GlobalActivityTracker.
   kActivityCallStackSize = 10,
 };
 
 // The data associated with an activity is dependent upon the activity type.
 // This union defines all of the various fields. All fields must be explicitly
 // sized types to ensure no interoperability problems between 32-bit and
@@ skipping 447 matching lines @@
   // The size (in bytes) of memory required by a ThreadActivityTracker to
   // provide the stack-depth requested during construction.
   const size_t stack_memory_size_;
 
   // The activity tracker for the currently executing thread.
   base::ThreadLocalStorage::Slot this_thread_tracker_;
 
   // These have to be lock-free because lock activity is tracked and causes
   // re-entry problems.
   std::atomic<int> thread_tracker_count_;
-  std::atomic<int> available_memories_count_;
-  std::atomic<PersistentMemoryAllocator::Reference>
-      available_memories_[kMaxThreadCount];
+  LockFreeSimpleStack<PersistentMemoryAllocator::Reference> available_memories_;
 
   // The active global activity tracker.
   static GlobalActivityTracker* g_tracker_;
 
   DISALLOW_COPY_AND_ASSIGN(GlobalActivityTracker);
 };
 
 
 // Record entry in to and out of an arbitrary block of code.
 class BASE_EXPORT ScopedActivity
@@ skipping 83 matching lines @@
   explicit ScopedProcessWaitActivity(const base::Process* process);
  private:
   DISALLOW_COPY_AND_ASSIGN(ScopedProcessWaitActivity);
 };
 #endif
 
 }  // namespace debug
 }  // namespace base
 
 #endif  // BASE_DEBUG_ACTIVITY_TRACKER_H_