New cache for the activity tracker.

base/debug/activity_tracker.h

Index: base/debug/activity_tracker.h
diff --git a/base/debug/activity_tracker.h b/base/debug/activity_tracker.h
index d6ff724cf2daee6106c3fbce75b9622f1d7a9eda..c3e9e4bfb5053063d15ea2a015e002beb7a2a40f 100644
--- a/base/debug/activity_tracker.h
+++ b/base/debug/activity_tracker.h
@@ -41,6 +41,173 @@ 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, size_t SIZE, T INVALID_VALUE>
+class LockFreeSimpleFifo {
+  enum : size_t {
+    CAPACITY = SIZE + 1  // +1 because one slot must always be free.
+  };
+
+ public:
+  LockFreeSimpleFifo() : head_(0), tail_(0) {
+    // 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 < CAPACITY; ++i)
+      stack_[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) + CAPACITY -
+            tail_.load(std::memory_order_relaxed)) %
+           CAPACITY;
+  }
+  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 "modulus" arithmetic if the left value is negative.
+  bool empty(size_t head, size_t tail) { return head == tail; }
+  bool full(size_t head, size_t tail) {
+    return (tail + CAPACITY - 1) % CAPACITY == head;
+  }
+
+  std::atomic<T> stack_[CAPACITY];
+  std::atomic<size_t> head_;  // One past the newest value; where to push.
+  std::atomic<size_t> tail_;  // The oldest value; first to pop.
+
+  DISALLOW_COPY_AND_ASSIGN(LockFreeSimpleFifo);
+};
+
+template <typename T, size_t SIZE, T INVALID_VALUE>
+bool LockFreeSimpleFifo<T, SIZE, INVALID_VALUE>::push(T value) {
+  // Pushing the "invalid" value is not allowed; it would be skipped by pop.
+  CHECK_NE(INVALID_VALUE, value);
+
+  while (true) {
+    // Get the head of the stack and acquire its contents.
+    size_t head = head_.load(std::memory_order_acquire);
+    DCHECK_LE(0U, head);
+    DCHECK_GT(CAPACITY, 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 incrementing
+    // past the new value.
+    T value_expected = INVALID_VALUE;
+    if (!stack_[head].compare_exchange_strong(value_expected, value,
+                                              std::memory_order_release,
+                                              std::memory_order_relaxed)) {
+      // Something got pushed so increment the head pointer past it. This is
+      // done to handle the case where whatever has written the value somehow
+      // died between writing the value and incrementing the head pointer. In
+      // that (unusual) case, simply trying again would lead to an infinite
+      // loop. We try but don't care if it fails because failure just indicates
+      // that the other thread is behaving properly. A "strong" exchange is
+      // necessary to avoid false failures.
+      head_.compare_exchange_strong(head, head + 1,

[manzagop (departed), 2016/08/18 14:14:46]

I've just noticed this could do a spurious push, if:
- t1 puts a valid value but suspends before incrementing head
- t2 fails to do the exchange and enters the if
- t1 increments head.
- some threads do enough complete pushes to wrap around back to head which now
contains an invalid value
- t2 resumes and increments head which effectively pushes an invalid value.

I think the suggestion to store head "not modulo-ed" addresses it though.

+                                    std::memory_order_relaxed,
+                                    std::memory_order_relaxed);
+
+      // Try again.
+      continue;
+    }
+
+    // Increment the head, releasing the newly stored value. This could fail
+    // if another thread tried a simultaneous push, saw this value, and
+    // bumped the head in the crash-safty increment just above. Because the
+    // result is ignored, a "strong" exchange is necessary to ensure a
+    // false failure doesn't occur.
+    head_.compare_exchange_strong(head, head + 1,
+                                  std::memory_order_release,
+                                  std::memory_order_relaxed);
+
+    // Success!
+    return true;
+  }
+}
+
+template <typename T, size_t SIZE, T INVALID_VALUE>
+T LockFreeSimpleFifo<T, SIZE, INVALID_VALUE>::pop() {
+  while (true) {
+    // Get the current number of elements on the stack.
+    size_t tail = tail_.load(std::memory_order_relaxed);
+    DCHECK_LE(0U, tail);
+    DCHECK_GT(CAPACITY, 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.
+    T value = stack_[tail].exchange(INVALID_VALUE, std::memory_order_relaxed);
+    if (value == INVALID_VALUE) {
+      // Another thread has already taken the "tail" value so increment the
+      // tail pointer past it. This is done to handle the case where whatever
+      // took the value somehow died between reading the value and incrementing
+      // the tail pointer. In that (unusual) case, simply trying again would
+      // lead to an infinite loop. We try but don't care if it fails because
+      // that just indicates that the other thread is behaving properly. A
+      // "strong" exchange is necessary to avoid false failures.
+      tail_.compare_exchange_strong(tail, tail + 1,
+                                    std::memory_order_relaxed,
+                                    std::memory_order_relaxed);
+
+      // Try again.
+      continue;
+    }
+
+    // Increment the tail, releasing the newly stored value. This could fail
+    // if another thread tried a simultaneous pop, saw the update, and
+    // bumped the tail in the crash-safty increment just above. Because the
+    // result is ignored, a "strong" exchange is necessary to ensure a
+    // false failure doesn't occur.
+    tail_.compare_exchange_strong(tail, tail + 1,
+                                  std::memory_order_release,
+                                  std::memory_order_relaxed);
+
+    // 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
@@ -508,9 +675,10 @@ class BASE_EXPORT GlobalActivityTracker {
   // 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,
+                     kMaxThreadCount,
+                     PersistentMemoryAllocator::kReferenceNull>
+      available_memories_;
 
   // The active global activity tracker.
   static GlobalActivityTracker* g_tracker_;