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..20b112d9700b69ce7602ed4daf300851a5c96b2e 100644
--- a/base/debug/activity_tracker.h
+++ b/base/debug/activity_tracker.h
@@ -41,6 +41,171 @@ 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>

[manzagop (departed), 2016/08/16 21:44:31]

Would it be better for generated code size to exclude SIZE and INVALID_VALUE
from the template and have them be constructor params?

[bcwhite, 2016/08/17 19:29:23]

Seems reasonable.  I'll look into it.

[bcwhite, 2016/08/18 19:26:42]

Done.

+class LockFreeSimpleFifo {
+  enum : size_t {
+    CAPACITY = SIZE + 1  // +1 because one slot must always be free.

[manzagop (departed), 2016/08/16 21:44:32]

nit: isn't "size = capacity + 1" more accurate?

[bcwhite, 2016/08/18 19:26:42]

Done.

+  };
+
+ 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 explit head/tail values.

[manzagop (departed), 2016/08/16 21:44:31]

nit: explit?

[bcwhite, 2016/08/17 19:29:23]

Done.

+  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;

[manzagop (departed), 2016/08/16 21:44:32]

nit: perhaps comment on the modulo, since that varies per language eg:
// Note: adding CAPACITY to ensure result of modulo is positive.

[bcwhite, 2016/08/17 19:29:23]

Done.

+  }
+
+  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 stack, 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,
+                                    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.

[manzagop (departed), 2016/08/16 22:05:00]

I'm wondering if there's a problem. Being able to store a value at head (l.129)
means that we wrote to a free spot, but it doesn't mean we wrote at the real
head_. It's possible that in between loading the head (l.115) and writing to it
(l.129) there were lots of pushes and pops and we're actually writing in the
middle of the free range?

[bcwhite, 2016/08/17 19:29:23]

So...  multiple pushes and pops occur such that tail advances past head and the
store succeeds but the head-increment fails.

Good catch.

I'm going to have to think on this.  One solution that comes to mind would be to
keep head/tail as raw values and only do the modulus when referencing stack_. 
Then, if this increment fails then I can see if it failed because the tail has
gone by and undo the store of the "invalid" value.  That would also eliminate
the size/capacity (or, "How do I differentiate between empty and full?")
problem.

I don't *think* a limit of 4 billion push operations (on a 32-bit architecture)
would be a real limitation.  You?

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

I agree this fixes the problem cases. However, I'm wary of baking a limit on the
number of operations even though 4B does seem high.

Is a lock really too expensive in this scenario? We're talking once per thread
creation / destruction.

[bcwhite, 2016/08/18 19:26:42]

I've simplified things now that thread-death is no longer a concern. It
precludes ever adapting this to memory shared between processes but that's a
problem for another day, such as when there is actually a demand for it.

+    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 stack, 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 +673,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_;