New cache for the activity tracker.

base/debug/activity_tracker.cc

 // 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.
 
 #include "base/debug/activity_tracker.h"
 
 #include "base/debug/stack_trace.h"
 #include "base/files/file.h"
 #include "base/files/file_path.h"
 #include "base/files/memory_mapped_file.h"
@@ skipping 480 matching lines @@
                                                   StringPiece name,
                                                   int stack_depth) {
   CreateWithAllocator(
       WrapUnique(new LocalPersistentMemoryAllocator(size, id, name)),
       stack_depth);
 }
 
 ThreadActivityTracker* GlobalActivityTracker::CreateTrackerForCurrentThread() {
   DCHECK(!this_thread_tracker_.Get());
 
-  PersistentMemoryAllocator::Reference mem_reference = 0;
-  void* mem_base = nullptr;
+  PersistentMemoryAllocator::Reference mem_reference =
+      available_memories_.invalid_value();
+  DCHECK(!mem_reference);  // invalid_value should be checkable with !
 
-  // Get the current count of available memories, acquiring the array values.
-  int count = available_memories_count_.load(std::memory_order_acquire);
-  while (count > 0) {
-    // There is a memory block that was previously released (and zeroed) so
-    // just re-use that rather than allocating a new one. Use "relaxed" because
-    // the value is guarded by the |count| "acquire". A zero reference replaces
-    // the existing value so that it can't be used by another thread that
-    // manages to interrupt this one before the count can be decremented.
-    // A zero reference is also required for the "push" operation to work
-    // once the count finally does get decremented.
-    mem_reference =
-        available_memories_[count - 1].exchange(0, std::memory_order_relaxed);
+  while (true) {
+    // Get the first available memory from the top of the stack.

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

nit: top of the stack -> fifo.

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

Done.  Though a FIFO and LIFO are both types of stack.

+    mem_reference = available_memories_.pop();
+    if (!mem_reference)
+      break;
 
-    // If the reference is zero, it's already been taken but count hasn't yet
-    // been decremented. Give that other thread a chance to finish then reload
-    // the "count" value and try again.
-    if (!mem_reference) {
-      PlatformThread::YieldCurrentThread();
-      count = available_memories_count_.load(std::memory_order_acquire);
-      continue;
+    // Turn the reference back into one of the activity-tracker type. This can
+    // fail if something else has already taken the block and changed its type.

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

Who could have taken the block, and how? Ah, by iterating directly over the
allocator's blocks below?

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

Correct.

+    if (allocator_->ChangeType(mem_reference, kTypeIdActivityTracker,
+                               kTypeIdActivityTrackerFree)) {
+      break;
     }
-
-    // Decrement the count indicating that the value has been taken. If this
-    // fails then another thread has pushed something new and incremented the
-    // count.
-    // NOTE: |oldcount| will be loaded with the existing value.
-    int oldcount = count;
-    if (!available_memories_count_.compare_exchange_strong(
-            oldcount, count - 1, std::memory_order_acquire,
-            std::memory_order_acquire)) {
-      DCHECK_LT(count, oldcount);
-
-      // Restore the reference that was zeroed above and try again.
-      available_memories_[count - 1].store(mem_reference,
-                                           std::memory_order_relaxed);
-      count = oldcount;
-      continue;
-    }
-
-    // Turn the reference back into one of the activity-tracker type.
-    mem_base = allocator_->GetAsObject<char>(mem_reference,
-                                             kTypeIdActivityTrackerFree);
-    DCHECK(mem_base);
-    DCHECK_LE(stack_memory_size_, allocator_->GetAllocSize(mem_reference));
-    bool changed = allocator_->ChangeType(mem_reference, kTypeIdActivityTracker,
-                                          kTypeIdActivityTrackerFree);
-    DCHECK(changed);
-
-    // Success.
-    break;
   }
 
-  // Handle the case where no previously-used memories are available.
-  if (count == 0) {
+  // Handle the case where no known available memories were found.
+  if (!mem_reference) {
     // Allocate a block of memory from the persistent segment.
     mem_reference =
         allocator_->Allocate(stack_memory_size_, kTypeIdActivityTracker);
     if (mem_reference) {
-      // Success. Convert the reference to an actual memory address.
-      mem_base =
-          allocator_->GetAsObject<char>(mem_reference, kTypeIdActivityTracker);
-      // Make the allocation iterable so it can be found by other processes.
+      // Success. Make the allocation iterable so it can be found later.
       allocator_->MakeIterable(mem_reference);
     } else {
-      // Failure. This shouldn't happen.
-      NOTREACHED();
-      // But if it does, probably because the allocator wasn't given enough
-      // memory to satisfy all possible requests, handle it gracefully by
-      // allocating the required memory from the heap.
-      mem_base = new char[stack_memory_size_];
-      memset(mem_base, 0, stack_memory_size_);
-      // Report the thread-count at which the allocator was full so that the
-      // failure can be seen and underlying memory resized appropriately.
-      UMA_HISTOGRAM_COUNTS_1000(
-          "ActivityTracker.ThreadTrackers.MemLimitTrackerCount",
-          thread_tracker_count_.load(std::memory_order_relaxed));
+      // Failure. Look for any free blocks that weren't held in the cache
+      // of available memories and try to claim it.

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

Maybe clarify the comment to say the claimed block might be in the cache, eg:

Expand the search for free blocks by iterating over the allocator's free blocks.
This is because the cache's capacity may be inferior to the number of allocated
blocks. Note that any block found may actually be in the cache (if it was
inserted after the last check).

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

Done.

+      PersistentMemoryAllocator::Iterator iter(allocator_.get());
+      while ((mem_reference = iter.GetNextOfType(kTypeIdActivityTrackerFree)) !=
+             0) {
+        if (allocator_->ChangeType(mem_reference, kTypeIdActivityTracker,
+                                   kTypeIdActivityTrackerFree)) {
+          break;
+        }
+        mem_reference = 0;
+      }
+      if (!mem_reference) {
+        // Dobule Failure. This shouldn't happen. But be graceful if it does,
+        // probably because the underlying allocator wasn't given enough memory
+        // to satisfy all possible requests.
+        NOTREACHED();
+        // Report the thread-count at which the allocator was full so that the
+        // failure can be seen and underlying memory resized appropriately.
+        UMA_HISTOGRAM_COUNTS_1000(
+            "ActivityTracker.ThreadTrackers.MemLimitTrackerCount",
+            thread_tracker_count_.load(std::memory_order_relaxed));
+        // Return null, just as if tracking wasn't enabled.
+        return nullptr;
+      }
     }
   }
 
+  // Convert the memory block found above into an actual memory address.
+  DCHECK(mem_reference);
+  void* mem_base =
+      allocator_->GetAsObject<char>(mem_reference, kTypeIdActivityTracker);
+  DCHECK(mem_base);
+  DCHECK_LE(stack_memory_size_, allocator_->GetAllocSize(mem_reference));
+
   // Create a tracker with the acquired memory and set it as the tracker
   // for this particular thread in thread-local-storage.
-  DCHECK(mem_base);
   ManagedActivityTracker* tracker =
       new ManagedActivityTracker(mem_reference, mem_base, stack_memory_size_);
   DCHECK(tracker->IsValid());
   this_thread_tracker_.Set(tracker);
   int old_count = thread_tracker_count_.fetch_add(1, std::memory_order_relaxed);
 
   UMA_HISTOGRAM_ENUMERATION("ActivityTracker.ThreadTrackers.Count",
                             old_count + 1, kMaxThreadCount);
   return tracker;
 }
 
 void GlobalActivityTracker::ReleaseTrackerForCurrentThreadForTesting() {
   ThreadActivityTracker* tracker =
       reinterpret_cast<ThreadActivityTracker*>(this_thread_tracker_.Get());
   if (tracker) {
     this_thread_tracker_.Free();
     delete tracker;
   }
 }
 
 GlobalActivityTracker::GlobalActivityTracker(
     std::unique_ptr<PersistentMemoryAllocator> allocator,
     int stack_depth)
     : allocator_(std::move(allocator)),
       stack_memory_size_(ThreadActivityTracker::SizeForStackDepth(stack_depth)),
       this_thread_tracker_(&OnTLSDestroy),
-      thread_tracker_count_(0),
-      available_memories_count_(0) {
-  // Clear the available-memories array.
-  memset(available_memories_, 0, sizeof(available_memories_));
-
+      thread_tracker_count_(0) {
   // Ensure the passed memory is valid and empty (iterator finds nothing).
   uint32_t type;
   DCHECK(!PersistentMemoryAllocator::Iterator(allocator_.get()).GetNext(&type));
 
   // Ensure that there is no other global object and then make this one such.
   DCHECK(!g_tracker_);
   g_tracker_ = this;
 }
 
 GlobalActivityTracker::~GlobalActivityTracker() {
   DCHECK_EQ(g_tracker_, this);
   DCHECK_EQ(0, thread_tracker_count_.load(std::memory_order_relaxed));
   g_tracker_ = nullptr;
 }
 
 void GlobalActivityTracker::ReturnTrackerMemory(
     ManagedActivityTracker* tracker) {
   PersistentMemoryAllocator::Reference mem_reference = tracker->mem_reference_;
   void* mem_base = tracker->mem_base_;
+  DCHECK(mem_reference);
+  DCHECK(mem_base);
 
   // Zero the memory so that it is ready for use if needed again later. It's
   // better to clear the memory now, when a thread is exiting, than to do it
   // when it is first needed by a thread doing actual work.
   memset(mem_base, 0, stack_memory_size_);
 
   // Remove the destructed tracker from the set of known ones.
   DCHECK_LE(1, thread_tracker_count_.load(std::memory_order_relaxed));
   thread_tracker_count_.fetch_sub(1, std::memory_order_relaxed);
 
-  // Deal with the memory that was used by the tracker.
-  if (mem_reference) {
-    // The memory was within the persistent memory allocator. Change its type
-    // so that iteration won't find it.
-    allocator_->ChangeType(mem_reference, kTypeIdActivityTrackerFree,
-                           kTypeIdActivityTracker);
-    // There is no way to free memory from a persistent allocator so instead
-    // push it on the internal list of available memory blocks.
-    while (true) {
-      // Get the existing count of available memories and ensure we won't
-      // burst the array. Acquire the values in the array.
-      int count = available_memories_count_.load(std::memory_order_acquire);
-      if (count >= kMaxThreadCount) {
-        NOTREACHED();
-        // Storage is full. Just forget about this memory. It won't be re-used
-        // but there's no real loss.
-        break;
-      }
+  // The memory was within the persistent memory allocator. Change its type
+  // so it is effectively marked as "free".
+  allocator_->ChangeType(mem_reference, kTypeIdActivityTrackerFree,
+                         kTypeIdActivityTracker);
 
-      // Write the reference of the memory being returned to this slot in the
-      // array. Empty slots have a value of zero so do an atomic compare-and-
-      // exchange to ensure that a race condition doesn't exist with another
-      // thread doing the same.
-      PersistentMemoryAllocator::Reference mem_expected = 0;
-      if (!available_memories_[count].compare_exchange_strong(
-              mem_expected, mem_reference, std::memory_order_release,
-              std::memory_order_relaxed)) {
-        PlatformThread::YieldCurrentThread();
-        continue;  // Try again.
-      }
-
-      // Increment the count, releasing the value written to the array. This
-      // could fail if a simultaneous "pop" operation decremented the counter.
-      // If that happens, clear the array slot and start over. Do a "strong"
-      // exchange to avoid spurious retries that can occur with a "weak" one.
-      int expected = count;  // Updated by compare/exchange.
-      if (!available_memories_count_.compare_exchange_strong(
-              expected, count + 1, std::memory_order_release,
-              std::memory_order_relaxed)) {
-        available_memories_[count].store(0, std::memory_order_relaxed);
-        continue;
-      }
-
-      // Count was successfully incremented to reflect the newly added value.
-      break;
-    }
-  } else {
-    // The memory was allocated from the process heap. This shouldn't happen
-    // because the persistent memory segment should be big enough for all
-    // thread stacks but it's better to support falling back to allocation
-    // from the heap rather than crash. Everything will work as normal but
-    // the data won't be persisted.
-    delete[] reinterpret_cast<char*>(mem_base);
-  }
+  // Push this on the internal list of available memory blocks so it can

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

nit: list -> cache

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

Done.

+  // be found and reused quickly. If the push somehow exceeds the maximum
+  // size of the stack, it will fail but a fallback check in CreateTracker

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

stack -> fifo / free block cache

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

Done.

+  // will find it by (slow) iteration.
+  available_memories_.push(mem_reference);
 }
 
 // static
 void GlobalActivityTracker::OnTLSDestroy(void* value) {
   delete reinterpret_cast<ManagedActivityTracker*>(value);
 }
 
 ScopedActivity::ScopedActivity(const tracked_objects::Location& location,
                                uint8_t action,
                                uint32_t id,
@@ skipping 60 matching lines @@
     const base::Process* process)
     : GlobalActivityTracker::ScopedThreadActivity(
           nullptr,
           Activity::ACT_PROCESS_WAIT,
           ActivityData::ForProcess(process->Pid()),
           /*lock_allowed=*/true) {}
 #endif
 
 }  // namespace debug
 }  // namespace base