Home | History | Annotate | Download | only in trace_event 
      1 // Copyright 2015 The Chromium Authors. All rights reserved.
      2 // Use of this source code is governed by a BSD-style license that can be
      3 // found in the LICENSE file.
      4 
      5 #include "base/trace_event/heap_profiler_stack_frame_deduplicator.h"
      6 
      7 #include <inttypes.h>
      8 #include <stddef.h>
      9 
     10 #include <string>
     11 #include <utility>
     12 
     13 #include "base/strings/stringprintf.h"
     14 #include "base/trace_event/trace_event_argument.h"
     15 #include "base/trace_event/trace_event_memory_overhead.h"
     16 
     17 namespace base {
     18 namespace trace_event {
     19 
     20 StackFrameDeduplicator::FrameNode::FrameNode(StackFrame frame,
     21                                              int parent_frame_index)
     22     : frame(frame), parent_frame_index(parent_frame_index) {}
     23 StackFrameDeduplicator::FrameNode::FrameNode(const FrameNode& other) = default;
     24 StackFrameDeduplicator::FrameNode::~FrameNode() {}
     25 
     26 StackFrameDeduplicator::StackFrameDeduplicator() {}
     27 StackFrameDeduplicator::~StackFrameDeduplicator() {}
     28 
     29 int StackFrameDeduplicator::Insert(const StackFrame* beginFrame,
     30                                    const StackFrame* endFrame) {
     31   int frame_index = -1;
     32   std::map<StackFrame, int>* nodes = &roots_;
     33 
     34   // Loop through the frames, early out when a frame is null.
     35   for (const StackFrame* it = beginFrame; it != endFrame; it++) {
     36     StackFrame frame = *it;
     37 
     38     auto node = nodes->find(frame);
     39     if (node == nodes->end()) {
     40       // There is no tree node for this frame yet, create it. The parent node
     41       // is the node associated with the previous frame.
     42       FrameNode frame_node(frame, frame_index);
     43 
     44       // The new frame node will be appended, so its index is the current size
     45       // of the vector.
     46       frame_index = static_cast<int>(frames_.size());
     47 
     48       // Add the node to the trie so it will be found next time.
     49       nodes->insert(std::make_pair(frame, frame_index));
     50 
     51       // Append the node after modifying |nodes|, because the |frames_| vector
     52       // might need to resize, and this invalidates the |nodes| pointer.
     53       frames_.push_back(frame_node);
     54     } else {
     55       // A tree node for this frame exists. Look for the next one.
     56       frame_index = node->second;
     57     }
     58 
     59     nodes = &frames_[frame_index].children;
     60   }
     61 
     62   return frame_index;
     63 }
     64 
     65 void StackFrameDeduplicator::AppendAsTraceFormat(std::string* out) const {
     66   out->append("{");  // Begin the |stackFrames| dictionary.
     67 
     68   int i = 0;
     69   auto frame_node = begin();
     70   auto it_end = end();
     71   std::string stringify_buffer;
     72 
     73   while (frame_node != it_end) {
     74     // The |stackFrames| format is a dictionary, not an array, so the
     75     // keys are stringified indices. Write the index manually, then use
     76     // |TracedValue| to format the object. This is to avoid building the
     77     // entire dictionary as a |TracedValue| in memory.
     78     SStringPrintf(&stringify_buffer, "\"%d\":", i);
     79     out->append(stringify_buffer);
     80 
     81     std::unique_ptr<TracedValue> frame_node_value(new TracedValue);
     82     const StackFrame& frame = frame_node->frame;
     83     switch (frame.type) {
     84       case StackFrame::Type::TRACE_EVENT_NAME:
     85         frame_node_value->SetString(
     86             "name", static_cast<const char*>(frame.value));
     87         break;
     88       case StackFrame::Type::THREAD_NAME:
     89         SStringPrintf(&stringify_buffer,
     90                       "[Thread: %s]",
     91                       static_cast<const char*>(frame.value));
     92         frame_node_value->SetString("name", stringify_buffer);
     93         break;
     94       case StackFrame::Type::PROGRAM_COUNTER:
     95         SStringPrintf(&stringify_buffer,
     96                       "pc:%" PRIxPTR,
     97                       reinterpret_cast<uintptr_t>(frame.value));
     98         frame_node_value->SetString("name", stringify_buffer);
     99         break;
    100     }
    101     if (frame_node->parent_frame_index >= 0) {
    102       SStringPrintf(&stringify_buffer, "%d", frame_node->parent_frame_index);
    103       frame_node_value->SetString("parent", stringify_buffer);
    104     }
    105     frame_node_value->AppendAsTraceFormat(out);
    106 
    107     i++;
    108     frame_node++;
    109 
    110     if (frame_node != it_end)
    111       out->append(",");
    112   }
    113 
    114   out->append("}");  // End the |stackFrames| dictionary.
    115 }
    116 
    117 void StackFrameDeduplicator::EstimateTraceMemoryOverhead(
    118     TraceEventMemoryOverhead* overhead) {
    119   // The sizes here are only estimates; they fail to take into account the
    120   // overhead of the tree nodes for the map, but as an estimate this should be
    121   // fine.
    122   size_t maps_size = roots_.size() * sizeof(std::pair<StackFrame, int>);
    123   size_t frames_allocated = frames_.capacity() * sizeof(FrameNode);
    124   size_t frames_resident = frames_.size() * sizeof(FrameNode);
    125 
    126   for (const FrameNode& node : frames_)
    127     maps_size += node.children.size() * sizeof(std::pair<StackFrame, int>);
    128 
    129   overhead->Add("StackFrameDeduplicator",
    130                 sizeof(StackFrameDeduplicator) + maps_size + frames_allocated,
    131                 sizeof(StackFrameDeduplicator) + maps_size + frames_resident);
    132 }
    133 
    134 }  // namespace trace_event
    135 }  // namespace base
    136