1# Copyright 2014 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.
4import telemetry.timeline.async_slice as async_slice_module
5import telemetry.timeline.event_container as event_container
6import telemetry.timeline.flow_event as flow_event_module
7import telemetry.timeline.sample as sample_module
8import telemetry.timeline.slice as slice_module
9
10
11class Thread(event_container.TimelineEventContainer):
12  """A Thread stores all the trace events collected for a particular
13  thread. We organize the synchronous slices on a thread by "subrows," where
14  subrow 0 has all the root slices, subrow 1 those nested 1 deep, and so on.
15  The asynchronous slices are stored in an AsyncSliceGroup object.
16  """
17  def __init__(self, process, tid):
18    super(Thread, self).__init__('thread %s' % tid, parent=process)
19    self.tid = tid
20    self._async_slices = []
21    self._flow_events = []
22    self._samples = []
23    self._toplevel_slices = []
24    self._all_slices = []
25
26    # State only valid during import.
27    self._open_slices = []
28    self._newly_added_slices = []
29
30  @property
31  def toplevel_slices(self):
32    return self._toplevel_slices
33
34  @property
35  def all_slices(self):
36    return self._all_slices
37
38  @property
39  def samples(self):
40    return self._samples
41
42  @property
43  def async_slices(self):
44    return self._async_slices
45
46  @property
47  def open_slice_count(self):
48    return len(self._open_slices)
49
50  def IterChildContainers(self):
51    return
52    yield # pylint: disable=unreachable
53
54  def IterEventsInThisContainer(self, event_type_predicate, event_predicate):
55    if event_type_predicate(slice_module.Slice):
56      for s in self._newly_added_slices:
57        if event_predicate(s):
58          yield s
59      for s in self._all_slices:
60        if event_predicate(s):
61          yield s
62
63    if event_type_predicate(async_slice_module.AsyncSlice):
64      for async_slice in self._async_slices:
65        if event_predicate(async_slice):
66          yield async_slice
67        for sub_slice in async_slice.IterEventsInThisContainerRecrusively():
68          if event_predicate(sub_slice):
69            yield sub_slice
70
71    if event_type_predicate(flow_event_module.FlowEvent):
72      for flow_event in self._flow_events:
73        if event_predicate(flow_event):
74          yield flow_event
75
76    if event_type_predicate(sample_module.Sample):
77      for sample in self._samples:
78        if event_predicate(sample):
79          yield sample
80
81  def AddSample(self, category, name, timestamp, args=None):
82    if len(self._samples) and timestamp < self._samples[-1].start:
83      raise ValueError(
84          'Samples must be added in increasing timestamp order')
85    sample = sample_module.Sample(self,
86        category, name, timestamp, args=args)
87    self._samples.append(sample)
88
89  def AddAsyncSlice(self, async_slice):
90    self._async_slices.append(async_slice)
91
92  def AddFlowEvent(self, flow_event):
93    self._flow_events.append(flow_event)
94
95  def BeginSlice(self, category, name, timestamp, thread_timestamp=None,
96                 args=None):
97    """Opens a new slice for the thread.
98    Calls to beginSlice and endSlice must be made with
99    non-monotonically-decreasing timestamps.
100
101    * category: Category to which the slice belongs.
102    * name: Name of the slice to add.
103    * timestamp: The timetsamp of the slice, in milliseconds.
104    * thread_timestamp: Thread specific clock (scheduled) timestamp of the
105                        slice, in milliseconds.
106    * args: Arguments associated with
107
108    Returns newly opened slice
109    """
110    if len(self._open_slices) > 0 and timestamp < self._open_slices[-1].start:
111      raise ValueError(
112          'Slices must be added in increasing timestamp order')
113    new_slice = slice_module.Slice(self, category, name, timestamp,
114                                    thread_timestamp=thread_timestamp,
115                                    args=args)
116    self._open_slices.append(new_slice)
117    new_slice.did_not_finish = True
118    self.PushSlice(new_slice)
119    return new_slice
120
121  def EndSlice(self, end_timestamp, end_thread_timestamp=None):
122    """ Ends the last begun slice in this group and pushes it onto the slice
123    array.
124
125    * end_timestamp: Timestamp when the slice ended in milliseconds
126    * end_thread_timestamp: Timestamp when the scheduled time of the slice ended
127                            in milliseconds
128
129    returns completed slice.
130    """
131    if not len(self._open_slices):
132      raise ValueError(
133          'EndSlice called without an open slice')
134    curr_slice = self._open_slices.pop()
135    if end_timestamp < curr_slice.start:
136      raise ValueError(
137          'Slice %s end time is before its start.' % curr_slice.name)
138    curr_slice.duration = end_timestamp - curr_slice.start
139    # On Windows, it is possible to have a value for |end_thread_timestamp|
140    # but not for |curr_slice.thread_start|, because it takes some time to
141    # initialize the thread time timer.
142    if curr_slice.thread_start != None and end_thread_timestamp != None:
143      curr_slice.thread_duration = (end_thread_timestamp -
144                                    curr_slice.thread_start)
145    curr_slice.did_not_finish = False
146    return curr_slice
147
148  def PushCompleteSlice(self, category, name, timestamp, duration,
149                        thread_timestamp, thread_duration, args=None):
150    new_slice = slice_module.Slice(self, category, name, timestamp,
151                                   thread_timestamp=thread_timestamp,
152                                   args=args)
153    if duration == None:
154      new_slice.did_not_finish = True
155    else:
156      new_slice.duration = duration
157      new_slice.thread_duration = thread_duration
158    self.PushSlice(new_slice)
159    return new_slice
160
161  def PushMarkSlice(self, category, name, timestamp, thread_timestamp,
162        args=None):
163    new_slice = slice_module.Slice(self, category, name, timestamp,
164                                   thread_timestamp=thread_timestamp,
165                                   args=args)
166    self.PushSlice(new_slice)
167    return new_slice
168
169  def PushSlice(self, new_slice):
170    self._newly_added_slices.append(new_slice)
171    return new_slice
172
173  def AutoCloseOpenSlices(self, max_timestamp, max_thread_timestamp):
174    for s in self._newly_added_slices:
175      if s.did_not_finish:
176        s.duration = max_timestamp - s.start
177        assert s.duration >= 0
178        if s.thread_start != None:
179          s.thread_duration = max_thread_timestamp - s.thread_start
180          assert s.thread_duration >= 0
181    self._open_slices = []
182
183  def IsTimestampValidForBeginOrEnd(self, timestamp):
184    if not len(self._open_slices):
185      return True
186    return timestamp >= self._open_slices[-1].start
187
188  def FinalizeImport(self):
189    self._BuildSliceSubRows()
190
191  def _BuildSliceSubRows(self):
192    """This function works by walking through slices by start time.
193
194     The basic idea here is to insert each slice as deep into the subrow
195     list as it can go such that every subslice is fully contained by its
196     parent slice.
197
198     Visually, if we start with this:
199      0:  [    a       ]
200      1:    [  b  ]
201      2:    [c][d]
202
203     To place this slice:
204                   [e]
205     We first check row 2's last item, [d]. [e] wont fit into [d] (they dont
206     even intersect). So we go to row 1. That gives us [b], and [d] wont fit
207     into that either. So, we go to row 0 and its last slice, [a]. That can
208     completely contain [e], so that means we should add [e] as a subslice
209     of [a]. That puts it on row 1, yielding:
210      0:  [    a       ]
211      1:    [  b  ][e]
212      2:    [c][d]
213
214     If we then get this slice:
215                          [f]
216     We do the same deepest-to-shallowest walk of the subrows trying to fit
217     it. This time, it doesn't fit in any open slice. So, we simply append
218     it to row 0 (a root slice):
219      0:  [    a       ]  [f]
220      1:    [  b  ][e]
221    """
222    def CompareSlices(s1, s2):
223      if s1.start == s2.start:
224        # Break ties by having the slice with the greatest
225        # end timestamp come first.
226        return cmp(s2.end, s1.end)
227      return cmp(s1.start, s2.start)
228
229    assert len(self._toplevel_slices) == 0
230    assert len(self._all_slices) == 0
231    if not len(self._newly_added_slices):
232      return
233
234    self._all_slices.extend(self._newly_added_slices)
235
236    sorted_slices = sorted(self._newly_added_slices, cmp=CompareSlices)
237    root_slice = sorted_slices[0]
238    self._toplevel_slices.append(root_slice)
239    for s in sorted_slices[1:]:
240      if not self._AddSliceIfBounds(root_slice, s):
241        root_slice = s
242        self._toplevel_slices.append(root_slice)
243    self._newly_added_slices = []
244
245
246  def _AddSliceIfBounds(self, root, child):
247    """Adds a child slice to a root slice its proper row.
248    Return False if the child slice is not in the bounds
249    of the root slice.
250
251    Because we know that the start time of child is >= the start time
252    of all other slices seen so far, we can just check the last slice
253    of each row for bounding.
254    """
255    # The source trace data is in microseconds but we store it as milliseconds
256    # in floating-point. Since we can't represent micros as millis perfectly,
257    # two end=start+duration combos that should be the same will be slightly
258    # different. Round back to micros to ensure equality below.
259    child_end_micros = round(child.end * 1000)
260    root_end_micros = round(root.end * 1000)
261    if child.start >= root.start and child_end_micros <= root_end_micros:
262      if len(root.sub_slices) > 0:
263        if self._AddSliceIfBounds(root.sub_slices[-1], child):
264          return True
265      child.parent_slice = root
266      root.AddSubSlice(child)
267      return True
268    return False
269