[tracing] Implement trace_event::AllocationContext

base/trace_event/memory_profiler_allocation_context.h

 // Copyright 2015 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.
 
 #ifndef BASE_TRACE_EVENT_MEMORY_PROFILER_ALLOCATION_CONTEXT_H_
 #define BASE_TRACE_EVENT_MEMORY_PROFILER_ALLOCATION_CONTEXT_H_
 
 #include <vector>
 
 #include "base/atomicops.h"
 #include "base/base_export.h"
 #include "base/containers/small_map.h"
 
 namespace base {
 namespace trace_event {
 
 // When heap profiling is enabled, tracing keeps track of the allocation
 // context for each allocation intercepted. It is generated by the
 // |AllocationContextTracker| which keeps stacks of context in TLS.
 // The tracker is initialized lazily.
 
 using StackFrame = const char*;
 
 // A simple stack of |StackFrame| that unlike |std::stack| allows iterating
 // the stack and guards for underflow.
 class BASE_EXPORT AllocationStack {
  public:
-  // Incrementing the iterator iterates down the stack.
-  using ConstIterator = std::vector<StackFrame>::const_reverse_iterator;
+  // Incrementing the iterator iterates up the stack, from bottom to top.

[Primiano Tucci (use gerrit), 2015/10/05 15:49:27]

It'd probably less ambiguous if you said here bottom (least recent call) to top
(most recent call, i.e. the one closer to the allocator)

+  using ConstIterator = std::vector<StackFrame>::const_iterator;
 
   AllocationStack();
   ~AllocationStack();
 
-  inline ConstIterator top() const { return stack_.rbegin(); }
-  inline ConstIterator bottom() const { return stack_.rend(); }
+  inline ConstIterator bottom() const { return stack_.begin(); }
+  inline ConstIterator top() const { return stack_.end(); }
 
   inline void push(StackFrame frame) {
     // Impose a limit on the height to verify that every push is popped, because
     // in practice the pseudo stack never grows higher than ~20 frames.
     DCHECK_LT(stack_.size(), 128u);
     stack_.push_back(frame);
   }
 
   inline void pop() {
     if (!stack_.empty())
       stack_.pop_back();
   }
 
  private:
   std::vector<StackFrame> stack_;
 
   DISALLOW_COPY_AND_ASSIGN(AllocationStack);
 };
 
-class BASE_EXPORT AllocationContext {
-  // TODO(ruuda): Fill this in a follow-up CL.
+// The backtrace in the allocation context is a snapshot of the stack. For now,
+// this is the pseudo stack where frames are created by trace event macros. In
+// the future, we might add the option to use the native call stack. In that
+// case, |Backtrace| and |AllocationContextTracker::GetContextSnapshot| might
+// have different implementations that can be selected by a compile time flag.
+
+// The number of stack frames stored in the backtrace is a trade off between
+// memory used for tracing and accuracy. Measurements done on a prototype
+// revealed that:
+//
+// - In 60 percent of the cases, stack depth <= 7.
+// - In 87 percent of the cases, stack depth <= 9.
+// - In 95 percent of the cases, stack depth <= 11.
+//
+// See the design doc (https://goo.gl/4s7v7b) for more details.
+
+// The allocation context is context metadata that is kept for every allocation
+// when heap profiling is enabled. To simplify memory management for
+// bookkeeping, this struct has a fixed size. All |const char*|s here
+// must have static lifetime.
+struct BASE_EXPORT AllocationContext {
+  struct Backtrace {
+    // Unused backtrace frames are filled with nullptr frames. If the stack is
+    // higher than what can be stored here, the bottom frames are stored. Based
+    // on the data above, a depth of 12 captures the full stack in the vast
+    // majority of the cases.
+    StackFrame frames[12];
+  } backtrace;
+
+  // There is room for two arbitrary context fields, which can be set by the
+  // |TRACE_ALLOCATION_CONTEXT| macro. A nullptr key indicates that the field is
+  // unused.
+  std::pair<const char*, const char*> fields[2];
 };
 
 // The allocation context tracker keeps track of thread-local context for heap
 // profiling. It includes a pseudo stack of trace events, and it might contain
 // arbitrary (key, value) context. On every allocation the tracker provides a
 // snapshot of its context in the form of an |AllocationContext| that is to be
 // stored together with the allocation details.
 class BASE_EXPORT AllocationContextTracker {
  public:
   // Globally enables capturing allocation context.
@@ skipping 23 matching lines @@
   static void PopPseudoStackFrame(StackFrame frame);
 
   // Sets a thread-local (key, value) pair.
   static void SetContextField(const char* key, const char* value);
 
   // Removes the (key, value) pair with the specified key from the thread-local
   // context.
   static void UnsetContextField(const char* key);
 
   // Returns a snapshot of the current thread-local context.
-  static AllocationContext GetContext();
-
-  // TODO(ruuda): Remove in a follow-up CL, this is only used for testing now.
-  static AllocationStack* GetPseudoStackForTesting();
+  static AllocationContext GetContextSnapshot();
 
   ~AllocationContextTracker();
 
  private:
   AllocationContextTracker();
 
   static AllocationContextTracker* GetThreadLocalTracker();
 
   static subtle::Atomic32 capture_enabled_;
 
   // The pseudo stack where frames are |TRACE_EVENT| names.
   AllocationStack pseudo_stack_;
 
   // A dictionary of arbitrary context.
   SmallMap<std::map<const char*, const char*>> context_;
 
   DISALLOW_COPY_AND_ASSIGN(AllocationContextTracker);
 };
 
 }  // namespace trace_event
 }  // namespace base
 
 #endif  // BASE_TRACE_EVENT_MEMORY_PROFILER_ALLOCATION_CONTEXT_H_