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.
 
@@ skipping 23 matching lines @@
 class Lock;
 class MemoryMappedFile;
 class PlatformThreadHandle;
 class Process;
 class WaitableEvent;
 
 namespace debug {
 
 class ThreadActivityTracker;
 
+
+//=============================================================================
+// This class provides a lock-free FIFO 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 LockFreeSimpleFifo {
+ public:
+  // Construct a simple lock-free FIFO with the specified |size| but
+  // not alowed to hold the |invalid_value|.
+  LockFreeSimpleFifo(size_t size, T invalid_value)
+      : size_(size + 1), invalid_value_(invalid_value), head_(0), tail_(0) {
+    DCHECK_LE(1, size);
+
+    // Allocate memory for the FIFO value. Its size is the requested size +1
+    // because it can never be full (head == tail is reserved to mean "empty").
+    stack_.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(stack_[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)
+      stack_[i].store(invalid_value_, std::memory_order_relaxed);
+  }
+
+  T invalid_value() { return invalid_value_; }
+  size_t size() { return size_ - 1; }
+  size_t used() {
+    return (head_.load(std::memory_order_relaxed) + size_ -
+            tail_.load(std::memory_order_relaxed)) %
+           size_;
+  }
+  bool empty() {
+    return empty(head_.load(std::memory_order_relaxed),
+                 tail_.load(std::memory_order_relaxed));
+  }
+  bool full() {
+    return full(head_.load(std::memory_order_relaxed),
+                tail_.load(std::memory_order_relaxed));
+  }
+
+  // Adds a new |value| to the end of the FIFO and returns true on success
+  // or false if the stack was full.
+  bool push(T value);
+
+  // Retrieves the first value off the FIFO and returns it or the "invalid"
+  // value if the stack is empty.
+  T pop();
+
+ private:
+  // Reports if the stack is empty/full based on explicit head/tail values.
+  // Note that the % operaton in C/C++ is a "remainder" operator and thus will
+  // not provide correct "modular arithmetic" if the left value is negative;
+  // adding |size_| keeps it positive.
+  bool empty(size_t head, size_t tail) { return head == tail; }
+  bool full(size_t head, size_t tail) {
+    return (tail + size_ - 1) % size_ == head;
+  }
+
+  const size_t size_;      // Size of the internal |stack_|: requested + 1
+  const T invalid_value_;  // A value not allowed to be stored.
+
+  std::atomic<size_t> head_;  // One past the newest value; where to push.
+  std::atomic<size_t> tail_;  // The oldest value; first to pop.
+
+  // Array holding pushed values.
+  std::unique_ptr<std::atomic<T>[]> stack_;
+
+  DISALLOW_COPY_AND_ASSIGN(LockFreeSimpleFifo);
+};
+
+template <typename T>
+bool LockFreeSimpleFifo<T>::push(T value) {
+  // Pushing the "invalid" value is not allowed; it would be cause an infinite

[manzagop (departed), 2016/08/19 20:44:50]

nit: "it would be cause"

[bcwhite, 2016/08/23 14:52:37]

Done.

+  // loop in pop.
+  CHECK_NE(invalid_value_, value);
+
+  // Get the head of the stack and acquire its contents.
+  size_t head = head_.load(std::memory_order_acquire);
+
+  while (true) {
+    DCHECK_LE(0U, head);
+    DCHECK_GT(size_, head);
+
+    // If the stack is full, fail.
+    if (full(head, tail_.load(std::memory_order_relaxed)))
+      return false;
+
+    // Write the value being pushed to the top of the fifo, exchanging it
+    // with the "invalid" value that should be there. If the atomic operation
+    // fails then something else has snuck in and pushed something else to
+    // that slot. A "strong" exchange is used to avoid mistakenly yielding
+    // the CPU.
+    T value_expected = invalid_value_;
+    if (!stack_[head].compare_exchange_strong(value_expected, value,
+                                              std::memory_order_release,
+                                              std::memory_order_relaxed)) {
+      // Get the new head since the one acquired above is no longer valid.
+      size_t new_head = head_.load(std::memory_order_acquire);
+
+      // If the new head maches the old one then another thread is currently

[manzagop (departed), 2016/08/19 20:44:50]

typo: maches

[bcwhite, 2016/08/23 14:52:37]

Acknowledged.

+      // between the write of the value and the increment of the head. Give it
+      // a chance to run.
+      if (new_head == head) {
+        PlatformThread::YieldCurrentThread();
+        new_head = head_.load(std::memory_order_acquire);
+      }
+
+      // Try again.
+      head = new_head;
+      continue;
+    }
+
+    // Increment the head, releasing the newly stored value. There is no reason
+    // for this to fail since only one thread at a time can be between the

[manzagop (departed), 2016/08/19 20:44:50]

Ugh... I think we still have the issue where after reading the head, the tail
can pass you by, and it's possible to write somewhere other than at head.

I wonder if an undo would work.

Another option might be if you have another invalid value which could be used to
signal head's location?

[bcwhite, 2016/08/22 12:59:41]

I don't think that can happen any more.  Only the thread that successfully
writes the value can now increment the head so there is no way for the head to
be anything but what this thread expects.

The tail can't advance past the head because there is an "empty()" check at the
top of its loop so pop() will never even try to read the value we've written
here until after the increment can occur on line 168.

Is there a different case you're thinking of?

[manzagop (departed), 2016/08/22 14:49:29]

Here's what I have in mind: T1 stores a copy of head at l.128, then a T2 does
multiple push/pops leading  tail_ to pass in front of T1's copy of "head". T1
then attempts to do it's push: it succeeds in swapping it's value with an
invalid value, but it's not at the real head. It then keeps yielding because its
head doesn't match the real head. Eventually, pushes on other threads bring head
back to just before T1's belief of head, but it's no longer possible for anyone
to push.

[bcwhite, 2016/08/23 14:52:37]

Right.  I'm going about this all wrong.  A slot should be allocated from the
head before anything is written.  Once a slot belongs to a thread, then it can
be updated free of contention.

+    // exchange above and the increment below. A "weak" exchange is sufficient
+    // because a simple retry can handle false failures.
+    size_t expected_head = head;
+    while (!head_.compare_exchange_weak(expected_head, (head + 1) % size_,
+                                        std::memory_order_release,
+                                        std::memory_order_relaxed)) {
+      // |expected_head| is updated with the actual value stored there.
+      // Ensure it matches our expectation that only false-failures can
+      // occur.
+      DCHECK_EQ(head, expected_head);
+    }
+
+    // Success!
+    return true;
+  }
+}
+
+template <typename T>
+T LockFreeSimpleFifo<T>::pop() {
+  // Get the current number of elements on the stack.
+  size_t tail = tail_.load(std::memory_order_acquire);
+
+  while (true) {
+    DCHECK_LE(0U, tail);
+    DCHECK_GT(size_, tail);
+
+    // If the stack is empty, fail.
+    if (empty(head_.load(std::memory_order_relaxed), tail))
+      return invalid_value_;
+
+    // Read a value from the bottom of the fifo, writing the "invalid" value
+    // in its place. If the retrieved value is invalid then it has already
+    // been taken.
+    T value = stack_[tail].exchange(invalid_value_, std::memory_order_relaxed);
+    if (value == invalid_value_) {
+      // Get the new tail since the one acquired above is no longer valid.
+      size_t new_tail = tail_.load(std::memory_order_acquire);
+
+      // If the new tail maches the old one then another thread is currently
+      // between the read of the value and the increment of the tail. Give it
+      // a chance to run.
+      if (new_tail == tail) {
+        PlatformThread::YieldCurrentThread();
+        new_tail = tail_.load(std::memory_order_acquire);
+      }
+
+      // Try again.
+      tail = new_tail;
+      continue;
+    }
+
+    // Increment the tail, releasing the newly stored value. There is no reason
+    // for this to fail since only one thread at a time can be between the
+    // exchange above and the increment below. A "weak" exchange is sufficient
+    // because a simple retry can handle false failures.
+    size_t expected_tail = tail;
+    while (!tail_.compare_exchange_weak(expected_tail, (tail + 1) % size_,
+                                        std::memory_order_release,
+                                        std::memory_order_relaxed)) {
+      // |expected_tail| is updated with the actual value stored there.
+      // Ensure it matches our expectation that only false-failures can
+      // occur.
+      DCHECK_EQ(tail, expected_tail);
+    }
+
+    // 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];
+  LockFreeSimpleFifo<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_