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 queue 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 LockFreeSimpleQueue {
+ public:
+  // Construct a simple lock-free queue with the specified |size| but
+  // not alowed to hold the |invalid_value|.
+  LockFreeSimpleQueue(size_t size, T invalid_value)
+      : size_(size + 1), invalid_value_(invalid_value), head_(0), tail_(0) {
+    DCHECK_LE(1U, size);
+
+    // Allocate memory for the queue value. Its size is the requested size +1
+    // because it can never be full (head == tail is reserved to mean "empty").
+    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_ - 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 queue and returns true on success
+  // or false if the stack was full.
+  bool push(T value);
+
+  // Retrieves the first value off the queue 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 |values_|: 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>[]> values_;
+
+  DISALLOW_COPY_AND_ASSIGN(LockFreeSimpleQueue);
+};
+
+template <typename T>
+bool LockFreeSimpleQueue<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 and acquire its contents.
+  size_t head = head_.load(std::memory_order_acquire);
+
+  // In short: allocate a slot at the head of the queue, write the value to
+  // it, try again if anything gets in the way.
+  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;
+
+    // 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) % size_,
+                                     std::memory_order_acquire,
+                                     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 LockFreeSimpleQueue<T>::pop() {
+  // Get the current number of elements on the stack.
+  size_t tail = tail_.load(std::memory_order_acquire);
+
+  // In short: deallocate the slot at the tail of the queue, read the value

[manzagop (departed), 2016/08/23 19:46:08]

I think it's possible that slot wasn't written to yet (a push is in flight). By
deallocating, we're making it possible for another push to happen (requires 2
pops), in which case either one of the push values could get written first?

[bcwhite, 2016/08/23 20:16:26]

Either push could get written first but they'll get written to numbered slots
based on the order in which they succeed in the increment-of-head exchange. 
Waiting for the value to be stored is on line 207.

Pop will wait for the lowest-numbered one to be written and return that, though
parallel pops could return in any order.

[manzagop (departed), 2016/08/23 21:20:28]

Sorry, I wasn't super clear. I mean that if there are lots of pushes that
complete while that first push is in flight (granted that's unlikely) then you
could wrap around and start performing a second push at the same location, while
the first is still in flight. Either of those might complete first. Again, it's
unlikely but possible?

[bcwhite, 2016/08/24 11:56:28]

Let's see...

1) T1 push allocates slot X but doesn't write
2) other threads successfully push N-1 values (more will fail)
3) T2 pop deallocates slot X but can't read so yields
4) other threads successfully pop some values; queue no longer full
5) T3 push allocates contended slot X...

Going forward, either T1 or T3 (but not both) can complete the write of slot X
and T2 will read it.  As soon as it's read, though, the other can then complete
its write at any time (we're back at step #1) and be available for the next pop
operation.

Ordering would go to hell and we had two threads go into an extended stall (for
due to the scheduler and one waiting for it)...  but I don't think anything gets
lost or otherwise breaks.

[manzagop (departed), 2016/08/24 13:17:52]

That's my understanding as well. In the current use case it doesn't matter if
the order isn't preserved. So we could go with a disclaimer comment.

[bcwhite, 2016/08/24 13:41:21]

I think it goes without saying that parallel operations don't have a guaranteed
order in any case.

+  // from it, try again if anything goes wrong.
+  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_;
+
+    // The "tail" is the critical resource so retrieve 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 = tail;
+    if (!tail_.compare_exchange_weak(slot, (tail + 1) % size_,
+                                     std::memory_order_acquire,
+                                     std::memory_order_relaxed)) {
+      // The exchange will have loaded the latest "tail" into |slot|.
+      tail = slot;
+      continue;
+    }
+
+    // Read a value from the bottom of the queue, 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];
+  LockFreeSimpleQueue<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_