[tracing] Implement trace_event::AllocationContext

base/trace_event/memory_profiler_allocation_context.h

Index: base/trace_event/memory_profiler_allocation_context.h
diff --git a/base/trace_event/memory_profiler_allocation_context.h b/base/trace_event/memory_profiler_allocation_context.h
index 11ecc881baffb7b359089259626844ea4200d189..51e1b02c4dde3c4daa5b47d8b5c2772c04f5adeb 100644
--- a/base/trace_event/memory_profiler_allocation_context.h
+++ b/base/trace_event/memory_profiler_allocation_context.h
@@ -52,8 +52,65 @@ class BASE_EXPORT AllocationStack {
   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::GetContext| 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 on a prototype revealed
+// that the stack depth sampled at every allocation has the following
+// distribution. (Columns are depth and percentage.)
+//
+//  0  0.8 #

[Primiano Tucci (use gerrit), 2015/10/05 12:35:38]

The histogram is nice but it's probably too much for this header. I'd move this
to the doc and just leave the cumulative values (lines 89-91) + a link to the
doc

[Ruud van Asseldonk, 2015/10/05 14:20:45]

Done.

+//  1  2.1 ##
+//  2  2.3 ##
+//  3  8.4 ########
+//  4  8.8 ########
+//  5  7.6 #######
+//  6  8.7 ########
+//  7 21.7 ####################
+//  8 14.2 ##############
+//  9 10.2 ##########
+// 10  5.7 ######
+// 11  1.8 ##
+// 12  1.2 #
+// 13  0.2
+// 14  0.4
+// 15  0.3
+// 16  0.3
+// 17  0.5 #
+// 18  0.4
+// 19  0.3
+// 20  0.4
+// 21  0.4
+//
+// 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.
+
+struct BASE_EXPORT Backtrace {
+  // Unused backtrace frames are filled with nullptr frames. If the stack is
+  // higher than what can be stored here, the topmost frames are stored. Based
+  // on the data above, a depth of 8 captures the full stack in the vast
+  // majority of the cases, and missing frames at the bottom can often be
+  // reconstructed given the top frames.
+  StackFrame frames[8];

[Primiano Tucci (use gerrit), 2015/10/05 12:35:38]

Looking at the data above, shouldn't this be 10-12 ?

[Ruud van Asseldonk, 2015/10/05 14:20:45]

The thing with statistics is that you can often use them to support any claim
... When storing the top frames I think you can get away with storing less
frames because the top of the stack can uniquely identify the full stack. (You
store the full stack in 75% of the cases, but you can probably identify the
stack in > 94% of the cases.) Now that we are going to store the bottom we need
more frames to get useful information. I changed it to 12.

+};
+
+// The allocation context is what is stored in the bookkeeping structure with

[Primiano Tucci (use gerrit), 2015/10/05 12:35:38]

I'd probably word it as "The allocation context is the metadata kept for each
allocation".
Remember that an allocator might choose to not use your upcoming bookkeeping
structure but retain the AllocationContext in its internals

[Ruud van Asseldonk, 2015/10/05 14:20:45]

Done.

+// every allocation. To simplify memory management for bookkeeping, this struct
+// has a fixed size. All |const char*|s here must have static lifetime. The
+// struct is designed such that a memzero'd instance is a valid context with

[Primiano Tucci (use gerrit), 2015/10/05 12:35:38]

As discussed remove the memzero comment

[Ruud van Asseldonk, 2015/10/05 14:20:45]

Done.

+// empty backtrace and no context fields.
+struct BASE_EXPORT AllocationContext {
+  Backtrace 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
@@ -92,9 +149,6 @@ class BASE_EXPORT AllocationContextTracker {
   // 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();
-
   ~AllocationContextTracker();
 
  private: