1""" NNAPI systrace parser - call tree data structure and manipulation
2
3Used by parser.tracker to gather and interpret the traces for a single thread.
4
5'SPEC: foo' refers to specific rows in the
6"NNAPI systrace contract between code and parser" document
7
8"""
9
10from parser.naming import subphases, layer_order
11from parser.naming import LAYER_APPLICATION, LAYER_RUNTIME, LAYER_UTILITY, LAYER_IGNORE
12from parser.naming import LAYER_IPC
13from parser.naming import PHASE_EXECUTION, PHASE_INITIALIZATION, PHASE_OVERALL, PHASE_UNSPECIFIED
14
15class SingleThreadCallTree(object):
16  """ Tree of scoped tracepoints. Implements:
17    - Creation of the tree from trace data
18    - Transformation of the tree into a clear representation
19      of time spent per layer and phase
20    - Validation that the resulting tree follows expectations
21  """
22  # Creation of tree from trace data
23  def __init__(self):
24    self.root = CallTreeNode(None, None, None, None, None, None)
25    self.current = self.root
26    self.stack = []
27
28  def push(self, start_time_s, mark, layer, phase, app_phase, subtract):
29    node = self.current.add(start_time_s, mark, layer, phase, app_phase, subtract)
30    self.stack.append(self.current)
31    self.current = node
32
33  def push_dummy(self, start_time_s):
34    node = self.current.add_dummy(start_time_s)
35    self.stack.append(self.current)
36    self.current = node
37
38  def pop(self, end_time_s):
39    self.current.end_time_s = end_time_s
40    ret = self.current
41    self.current = self.stack.pop()
42    return ret
43
44  # Transformation of the tree
45
46  # Remove dummies created by SPEC:"Switch phase during function"
47  def remove_dummies(self):
48    to_be_removed = []
49    def recurse(node):
50      if node.is_dummy():
51        to_be_removed.append(node)
52      for c in node.children:
53        recurse(c)
54    recurse(self.root)
55    for node in to_be_removed:
56      node.remove()
57
58  # Remove tracing nodes we are not interested in
59  def remove_ignored(self):
60    to_be_removed = []
61    def recurse(node):
62      if node.layer == LAYER_IGNORE:
63        to_be_removed.append(node)
64      for c in node.children:
65        recurse(c)
66    recurse(self.root)
67    for node in to_be_removed:
68      node.remove()
69
70
71  # For nodes that are in the wrong place in the tree: create a copy of the node
72  # in the right place and mark the original to be subtracted from timing.
73  # SPEC: Subtracting time when nesting is violated
74  # SPEC: Onetime initialization code
75  def copy_subtracted_init_and_wrong_la(self):
76    to_be_subtracted = []
77    def recurse(node):
78      if node.subtract:
79        to_be_subtracted.append(node)
80      elif node.phase() == PHASE_INITIALIZATION and node.parent.phase() != PHASE_INITIALIZATION:
81        to_be_subtracted.append(node)
82      elif (node.parent and node.parent.layer == LAYER_APPLICATION and
83            (node.layer == LAYER_RUNTIME or node.layer == LAYER_IPC) and
84            node.parent.phase() != node.phase() and node.parent.phase() != PHASE_OVERALL and
85            node.phase() != PHASE_EXECUTION and node.phase() not in subphases[PHASE_EXECUTION]):
86        # The application level phase may be wrong, we move the runtime nodes
87        # if necessary.
88        to_be_subtracted.append(node)
89      for c in node.children:
90        recurse(c)
91    recurse(self.root)
92    for node in to_be_subtracted:
93      layer = node.layer
94      # Find where to add the subtracted time
95      assert node.parent
96      new_parent = node.parent
97      if node.subtract:
98        explanation = "from [SUB]"
99        # Move [SUB] up to right layer
100        while ((new_parent.layer != layer or new_parent.is_added_detail()) and
101               not new_parent.is_root()):
102          new_parent = new_parent.parent
103      elif node.phase() == PHASE_INITIALIZATION:
104        explanation = "from phase PI"
105        # Move PI up to root
106        while not new_parent.is_root():
107          new_parent = new_parent.parent
108      else:
109        # Move missing LA phase up one
110        explanation = "for LA_" + node.phase()
111        new_parent = new_parent.parent
112      if not new_parent.is_root():
113        new_parent = new_parent.parent
114      added = new_parent.add(
115          node.start_time_s, node.mark + "(copied " + explanation + ")",
116          node.layer, node.phase(), node.app_phase, subtract=False)
117      added.end_time_s = node.end_time_s
118      node.subtract = True
119
120  # The application may not have added tracing for all phases, this
121  # adds intermediate LA nodes where needed.
122  def add_missing_la_nodes(self):
123    la_to_be_added = []
124    def recurse(node):
125      if not node.is_added_detail() and not node.subtract:
126        if ((node.layer == LAYER_RUNTIME or node.layer == LAYER_IPC) and
127            # Wrong LA node
128            (node.parent.layer == LAYER_APPLICATION and
129             node.parent.phase() != PHASE_OVERALL and
130             node.parent.phase() != node.phase()) and
131            # LR_PE and subphases need to be special
132            node.phase() != PHASE_EXECUTION and
133            node.phase() not in subphases[PHASE_EXECUTION]):
134          la_to_be_added.append(node)
135      for c in node.children:
136        recurse(c)
137    recurse(self.root)
138    for node in la_to_be_added:
139      node.add_intermediate_parent(LAYER_APPLICATION, node.phase(), node.app_phase)
140
141  # Validation
142  # SPEC: Local call to other layer
143  def validate_nesting(self):
144    self.debugstring = ""
145    def recurse(node, indent):
146      [mark, layer, phase] = [node.mark, node.layer, node.phase()]
147      prev_layer = (node.parent and node.parent.layer)
148      prev_phase = (node.parent and node.parent.phase())
149      self.debugstring += " ".join(map(str, [indent, mark, layer, phase,
150                                             prev_phase, prev_layer,
151                                             "subtract", node.subtract,
152                                             "\n"]))
153      # Check that phases nest as we expect:
154      assert((prev_phase is None) or             # Entering from top without application trace
155             (phase == prev_phase) or            # Same phase
156             (phase == PHASE_UNSPECIFIED) or     # Utility function
157             (phase == PHASE_INITIALIZATION) or  # One-time initialization
158             (phase in subphases.get(prev_phase, [])) or # Subphase as designed
159             (phase in subphases.get(PHASE_EXECUTION) and # Nested subphase missing
160              PHASE_EXECUTION in subphases.get(prev_phase, [])) or
161             node.subtract                       # Marker for wrong nesting
162             ), self.debugstring
163      # Check that layers nest as we expect:
164      assert ((prev_layer is None) or
165              (layer == LAYER_UTILITY) or
166              (layer == prev_layer) or
167              (layer in layer_order.get(prev_layer, [])) or
168              node.subtract), self.debugstring
169      for c in node.children:
170        recurse(c, indent + '  ')
171    recurse(self.root, '')
172
173  # Auxiliary functionality
174  def print(self):
175    print(self.to_str())
176
177  def to_str(self):
178    return self.root.to_str()
179
180  def is_empty(self):
181    return not self.root.children
182
183
184
185class CallTreeNode(object):
186  """ Single scoped tracepoint. """
187  def __init__(self, start_time_s, mark, layer, phase, app_phase, subtract):
188    self.children = []
189    self.start_time_s = start_time_s
190    self.mark = mark
191    self.layer = layer
192    self.phase_ = phase
193    self.app_phase = app_phase
194    self.subtract = subtract
195    self.end_time_s = None
196    self.parent = None
197
198  def is_root(self):
199    return self.start_time_s is None
200
201  def is_dummy(self):
202    return not self.is_root() and self.mark is None
203
204  def phase(self):
205    if self.phase_ == PHASE_UNSPECIFIED:
206      return self.parent.phase()
207    else:
208      return self.phase_
209
210  def is_added_detail(self):
211    if self.is_root():
212      return False
213    if self.parent.is_root():
214      return False
215    if self.layer != self.parent.layer:
216      return False
217    if self.phase() in subphases.get(self.parent.phase(), []):
218      return False
219    if self.phase() == PHASE_INITIALIZATION and self.parent.phase() != PHASE_INITIALIZATION:
220      return False
221    if self.subtract:
222      return False
223    return True
224
225  def elapsed_ms(self):
226    if (self.end_time_s is None) or (self.start_time_s is None):
227      return None
228    return (float(self.end_time_s) - float(self.start_time_s)) * 1000.0
229
230  def elapsed_less_subtracted_ms(self):
231    ret = self.elapsed_ms()
232    if ret is None:
233      return None
234    for c in self.children:
235      ret = ret - c.subtracted_ms()
236    return ret
237
238  def subtracted_ms(self):
239    subtract = 0.0
240    if self.is_added_detail():
241      for c in self.children:
242        subtract = subtract + c.subtracted_ms()
243    elif self.subtract:
244      subtract = self.elapsed_ms()
245    return subtract
246
247  def add(self, start_time_s, mark, layer, phase, app_phase, subtract):
248    node = CallTreeNode(start_time_s, mark, layer, phase, app_phase, subtract)
249    node.parent = self
250    self.children.append(node)
251    return node
252
253  def add_intermediate_parent(self, layer, phase, app_phase):
254    node = CallTreeNode(self.start_time_s,
255                        " ".join([self.mark, "( added intermediate",
256                                  layer, phase, ")"]),
257                        layer, phase, app_phase, subtract=False)
258    node.end_time_s = float(self.start_time_s) + self.elapsed_less_subtracted_ms() / 1000.0
259    node.parent = self.parent
260    for i in range(0, len(self.parent.children)):
261      if self.parent.children[i] == self:
262        self.parent.children[i] = node
263        break
264    self.parent = node
265    node.children.append(self)
266
267  def add_dummy(self, start_time_s):
268    node = CallTreeNode(start_time_s, None, None, None, None, None)
269    node.parent = self
270    self.children.append(node)
271    return node
272
273  def remove(self):
274    self.parent.children.remove(self)
275    self.parent.children.extend(self.children)
276    for c in self.children:
277      c.parent = self.parent
278    self.parent = None
279
280  def to_str(self, indent=''):
281    if not self.is_root():
282      ret = " ".join(map(str, [indent, self.app_phase, self.mark,
283                               self.elapsed_less_subtracted_ms(),
284                               "subtract: ", self.subtract, "\n"]))
285    else:
286      ret = " ".join([indent, "ROOT", "\n"])
287    if self.children:
288      ret += (indent + "   children:\n")
289      for c in self.children:
290        ret += c.to_str(indent + '    ')
291    return ret
292