1 //
2 // Copyright 2018 Pixar
3 //
4 // Licensed under the Apache License, Version 2.0 (the "Apache License")
5 // with the following modification; you may not use this file except in
6 // compliance with the Apache License and the following modification to it:
7 // Section 6. Trademarks. is deleted and replaced with:
8 //
9 // 6. Trademarks. This License does not grant permission to use the trade
10 // names, trademarks, service marks, or product names of the Licensor
11 // and its affiliates, except as required to comply with Section 4(c) of
12 // the License and to reproduce the content of the NOTICE file.
13 //
14 // You may obtain a copy of the Apache License at
15 //
16 // http://www.apache.org/licenses/LICENSE-2.0
17 //
18 // Unless required by applicable law or agreed to in writing, software
19 // distributed under the Apache License with the above modification is
20 // distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
21 // KIND, either express or implied. See the Apache License for the specific
22 // language governing permissions and limitations under the Apache License.
23 //
24
25 #include "pxr/base/trace/aggregateTreeBuilder.h"
26
27 #include "pxr/pxr.h"
28
29 #include "pxr/base/trace/collection.h"
30
31 #include <stack>
32
33 PXR_NAMESPACE_OPEN_SCOPE
34
35
36 void
AddEventTreeToAggregate(TraceAggregateTree * aggregateTree,const TraceEventTreeRefPtr & eventTree,const TraceCollection & collection)37 Trace_AggregateTreeBuilder::AddEventTreeToAggregate(
38 TraceAggregateTree* aggregateTree,
39 const TraceEventTreeRefPtr& eventTree,
40 const TraceCollection& collection)
41 {
42 Trace_AggregateTreeBuilder builder(aggregateTree, eventTree);
43
44 builder._CreateAggregateNodes();
45 builder._ProcessCounters(collection);
46 }
47
Trace_AggregateTreeBuilder(TraceAggregateTree * aggregateTree,const TraceEventTreeRefPtr & eventTree)48 Trace_AggregateTreeBuilder::Trace_AggregateTreeBuilder(
49 TraceAggregateTree* aggregateTree, const TraceEventTreeRefPtr& eventTree)
50 : _aggregateTree(aggregateTree)
51 , _tree(eventTree)
52 {
53 }
54
55 void
_ProcessCounters(const TraceCollection & collection)56 Trace_AggregateTreeBuilder::_ProcessCounters(const TraceCollection& collection)
57 {
58 collection.Iterate(*this);
59 _aggregateTree->GetRoot()->CalculateInclusiveCounterValues();
60 }
61
62 void
_CreateAggregateNodes()63 Trace_AggregateTreeBuilder::_CreateAggregateNodes()
64 {
65 using TreeIt = std::pair<TraceEventNodeRefPtr, size_t>;
66 std::stack<TreeIt> treeStack;
67 std::stack<TraceAggregateNodePtr> aggStack;
68
69 // Prime the aggregate stack with the root node.
70 aggStack.push(_aggregateTree->GetRoot());
71
72 // Prime the stack with the children of the root. These are the node that
73 // represent threads.
74 for (TraceEventNodeRefPtrVector::const_reverse_iterator it =
75 _tree->GetRoot()->GetChildrenRef().rbegin();
76 it != _tree->GetRoot()->GetChildrenRef().rend(); ++it) {
77 treeStack.push(std::make_pair(*it, 0));
78 }
79
80 // A valid id needed for node creation.
81 TraceAggregateNode::Id id = TraceAggregateNode::Id(TraceThreadId());
82
83 while (!treeStack.empty()) {
84 TreeIt it = treeStack.top();
85 treeStack.pop();
86
87 // The first time a node is visited, add it to the aggregate tree.
88 if (it.second == 0) {
89 const TraceEvent::TimeStamp duration =
90 it.first->GetEndTime() - it.first->GetBeginTime();
91
92 if (duration > 0 && aggStack.size() > 1) {
93 _aggregateTree->_eventTimes[it.first->GetKey()] += duration;
94 }
95
96 TraceAggregateNodePtr newNode = aggStack.top()->Append(
97 id, it.first->GetKey(), duration);
98 aggStack.push(newNode);
99 }
100 // When there are no more children to visit, pop the aggregate tree
101 // stack.
102 if (it.second >= it.first->GetChildrenRef().size()) {
103 aggStack.pop();
104 } else {
105 // Visit the current child and then the next child.
106 treeStack.push(std::make_pair(it.first, it.second+1));
107 treeStack.push(
108 std::make_pair(it.first->GetChildrenRef()[it.second], 0));
109 }
110 }
111 }
112
113 void
OnBeginCollection()114 Trace_AggregateTreeBuilder::OnBeginCollection()
115 {}
116
117 void
OnEndCollection()118 Trace_AggregateTreeBuilder::OnEndCollection()
119 {}
120
121 void
OnBeginThread(const TraceThreadId & threadId)122 Trace_AggregateTreeBuilder::OnBeginThread(const TraceThreadId& threadId)
123 {}
124
125 void
OnEndThread(const TraceThreadId & threadId)126 Trace_AggregateTreeBuilder::OnEndThread(const TraceThreadId& threadId)
127 {}
128
129 bool
AcceptsCategory(TraceCategoryId categoryId)130 Trace_AggregateTreeBuilder::AcceptsCategory(TraceCategoryId categoryId)
131 {
132 return true;
133 }
134
135 void
OnEvent(const TraceThreadId & threadIndex,const TfToken & key,const TraceEvent & e)136 Trace_AggregateTreeBuilder::OnEvent(
137 const TraceThreadId& threadIndex,
138 const TfToken& key,
139 const TraceEvent& e)
140 {
141 switch(e.GetType()) {
142 case TraceEvent::EventType::CounterDelta:
143 case TraceEvent::EventType::CounterValue:
144 _OnCounterEvent(threadIndex, key, e);
145 break;
146 default:
147 break;
148 }
149 }
150
151 void
_OnCounterEvent(const TraceThreadId & threadIndex,const TfToken & key,const TraceEvent & e)152 Trace_AggregateTreeBuilder::_OnCounterEvent(
153 const TraceThreadId& threadIndex,
154 const TfToken& key,
155 const TraceEvent& e)
156 {
157 bool isDelta = false;
158 switch (e.GetType()) {
159 case TraceEvent::EventType::CounterDelta: isDelta = true; break;
160 case TraceEvent::EventType::CounterValue: break;
161 default: return;
162 }
163
164 // Compute the total counter value
165 TraceAggregateTree::CounterMap::iterator it =
166 _aggregateTree->_counters.insert(
167 std::make_pair(key, 0.0)).first;
168
169 if (isDelta) {
170 it->second += e.GetCounterValue();
171 } else {
172 it->second = e.GetCounterValue();
173 }
174
175 // Insert the counter index into the map, if one does not
176 // already exist. If no counter index existed in the map,
177 // increment to the next available counter index.
178 std::pair<TraceAggregateTree::_CounterIndexMap::iterator, bool> res =
179 _aggregateTree->_counterIndexMap.insert(
180 std::make_pair(key, _aggregateTree->_counterIndex));
181 if (res.second) {
182 ++_aggregateTree->_counterIndex;
183 }
184
185 // It only makes sense to store delta values in the specific nodes at
186 // the moment. This might need to be revisted in the future.
187 if (isDelta) {
188 // Set the counter value on the current node.
189
190 TraceAggregateNodePtr node =
191 _FindAggregateNode(threadIndex, e.GetTimeStamp());
192 if (node) {
193 node->AppendExclusiveCounterValue(res.first->second, e.GetCounterValue());
194 node->AppendInclusiveCounterValue(res.first->second, e.GetCounterValue());
195 }
196 }
197 }
198
199 TraceAggregateNodePtr
_FindAggregateNode(const TraceThreadId & threadId,const TraceEvent::TimeStamp ts) const200 Trace_AggregateTreeBuilder::_FindAggregateNode(
201 const TraceThreadId& threadId, const TraceEvent::TimeStamp ts) const
202 {
203 // Find the root node of the thread.
204 const TraceEventNodeRefPtrVector& threadNodeList =
205 _tree->GetRoot()->GetChildrenRef();
206 TfToken threadKey(threadId.ToString());
207 TraceEventNodeRefPtrVector::const_iterator it =
208 std::find_if(threadNodeList.begin(), threadNodeList.end(),
209 [&threadKey](const TraceEventNodeRefPtr& node) {
210 return node->GetKey() == threadKey;
211 });
212 if (it == threadNodeList.end()) {
213 return nullptr;
214 }
215
216 // Construct a sequence of node names from the thread root node to the
217 // lowest node in the tree which contains this timestamp.
218 TraceEventNodeRefPtr node = *it;
219 std::vector<TfToken> path;
220 while (true) {
221 path.push_back(node->GetKey());
222 // Find the first child which contains this timestamp
223 TraceEventNodeRefPtrVector::const_iterator childIt =
224 std::lower_bound(
225 node->GetChildrenRef().begin(),
226 node->GetChildrenRef().end(), ts,
227 []( const TraceEventNodeRefPtr& node,
228 TraceEvent::TimeStamp ts) {
229 return node->GetEndTime() < ts;
230 });
231 if (childIt == node->GetChildrenRef().end()) {
232 break;
233 } else {
234 node = *childIt;
235 }
236 }
237
238 // Use the sequence of node names to find the corresponding node in the
239 // aggregate tree.
240 TraceAggregateNodePtr aggNode = _aggregateTree->GetRoot();
241 for (const TfToken& name : path) {
242 TraceAggregateNodePtr child = aggNode->GetChild(name);
243 if (!child) {
244 return nullptr;
245 }
246 aggNode = child;
247 }
248 return aggNode;
249 }
250
251 PXR_NAMESPACE_CLOSE_SCOPE
252