blob: 43fcaf48ffb57bd7e352c3f92e74e262812886b8 [file]
# Copyright 2023 The Fuchsia Authors. All rights reserved.
# Use of this source code is governed by a BSD-style license that can be
# found in the LICENSE file.
"""Utilities to filter and extract events and statistics from a trace Model."""
import itertools
import math
import statistics
from collections.abc import Collection, Container, Generator, Iterator
from dataclasses import dataclass
from typing import Any, overload
from reporting import metrics
from trace_processing import trace_model, trace_time
# Compute the linear interpolated [percentile]th percentile
# (https://en.wikipedia.org/wiki/Percentile) of [values].
def percentile(values: Collection[int | float], percentile: int) -> float:
if not values:
raise TypeError(
"[values] must not be empty in order to compute percentile"
)
values_list: list[int | float] = sorted(values)
if percentile == 100:
return float(values_list[-1])
index_as_float: float = float(len(values_list) - 1) * (0.01 * percentile)
index: int = math.floor(index_as_float)
if (index + 1) == len(values_list):
return float(values_list[-1])
index_fraction: float = index_as_float % 1
return (
values_list[index] * (1.0 - index_fraction)
+ values_list[index + 1] * index_fraction
)
def filter_events[
E: trace_model.Event
](
events: Iterator[trace_model.Event],
type: type[E],
category: str | None = None,
name: str | Container[str] | None = None,
) -> Generator[E, None, None]:
"""Filter |events| based on category, name, or type.
Args:
events: The set of events to filter.
category: Category of events to include, or None to skip this filter.
name: name or names of events to include, or None to skip this filter.
type: Type of events to include. By default object to include all events.
Returns:
An [Iterator] of filtered events. Note that Iterators can only be iterated a single time, so
the caller must create a local copy in order to loop over the filtered events more than once.
"""
for event in events:
category_matches: bool = category is None or event.category == category
if name is None:
name_matches = True
elif isinstance(name, str):
name_matches = event.name == name
else:
name_matches = event.name in name
if isinstance(event, type) and category_matches and name_matches:
yield event
@dataclass(frozen=True)
class EventFilter[E: trace_model.Event]:
"""A filter for trace events."""
type: type[E]
category: str | None = None
name: str | None = None
@overload
def filter_events_parallel[
E1: trace_model.Event
](
events: Iterator[trace_model.Event],
filters: tuple[EventFilter[E1]],
) -> tuple[Generator[E1, None, None]]:
...
@overload
def filter_events_parallel[
E1: trace_model.Event,
E2: trace_model.Event,
](
events: Iterator[trace_model.Event],
filters: tuple[EventFilter[E1], EventFilter[E2]],
) -> tuple[Generator[E1, None, None], Generator[E2, None, None]]:
...
@overload
def filter_events_parallel[
E1: trace_model.Event,
E2: trace_model.Event,
E3: trace_model.Event,
](
events: Iterator[trace_model.Event],
filters: tuple[EventFilter[E1], EventFilter[E2], EventFilter[E3]],
) -> tuple[
Generator[E1, None, None],
Generator[E2, None, None],
Generator[E3, None, None],
]:
...
@overload
def filter_events_parallel[
E1: trace_model.Event,
E2: trace_model.Event,
E3: trace_model.Event,
E4: trace_model.Event,
](
events: Iterator[trace_model.Event],
filters: tuple[
EventFilter[E1], EventFilter[E2], EventFilter[E3], EventFilter[E4]
],
) -> tuple[
Generator[E1, None, None],
Generator[E2, None, None],
Generator[E3, None, None],
Generator[E4, None, None],
]:
...
@overload
def filter_events_parallel[
E1: trace_model.Event,
E2: trace_model.Event,
E3: trace_model.Event,
E4: trace_model.Event,
E5: trace_model.Event,
](
events: Iterator[trace_model.Event],
filters: tuple[
EventFilter[E1],
EventFilter[E2],
EventFilter[E3],
EventFilter[E4],
EventFilter[E5],
],
) -> tuple[
Generator[E1, None, None],
Generator[E2, None, None],
Generator[E3, None, None],
Generator[E4, None, None],
Generator[E5, None, None],
]:
...
def filter_events_parallel(
events: Iterator[trace_model.Event],
filters: tuple[EventFilter[Any], ...],
) -> tuple[Generator[trace_model.Event, None, None], ...]:
"""Filter |events| based on a list of filter tuples.
This is more efficient than calling filter_events multiple times on the same
iterable of events, especially if the iterable is a generator.
Args:
events: The set of events to filter.
filters: A list of EventFilter objects.
Returns:
A tuple of [Generator]s of filtered events. Each generator corresponds
to a filter in the |filters| list.
"""
if not filters:
return tuple()
event_iters = itertools.tee(events, len(filters))
results: list[Generator[trace_model.Event, None, None]] = []
for i, f in enumerate(filters):
results.append(
filter_events(
event_iters[i], type=f.type, category=f.category, name=f.name
)
)
return tuple(results)
def filter_records[
U: trace_model.SchedulingRecord
](records: Iterator[trace_model.SchedulingRecord], type_: type[U]) -> Iterator[
U
]:
"""Filters SchedulingRecords by type.
Easier for mypy to grok than using types with filter().
Args:
records: SchedulingRecords to be filtered.
type_: The subclass of SchedulingRecord by which to filter.
Yields:
The elements of the iterable that are of the specified type.
"""
for record in records:
if isinstance(record, type_):
yield record
def total_event_duration(
events: Iterator[trace_model.Event],
) -> trace_time.TimeDelta:
"""Compute the total duration of all [Event]s in |events|. This is the end
of the last event minus the beginning of the first event.
Args:
events: The events for which to compute the duration.
Returns:
Total event duration.
"""
def event_times(
e: trace_model.Event,
) -> tuple[trace_time.TimePoint, trace_time.TimePoint]:
end: trace_time.TimePoint = e.start
if (
isinstance(e, trace_model.AsyncEvent | trace_model.DurationEvent)
and e.duration
):
end = e.start + e.duration
return (e.start, end)
start_times, end_times = zip(*map(event_times, events))
min_time: trace_time.TimePoint = min(
start_times, default=trace_time.TimePoint.zero()
)
max_time: trace_time.TimePoint = max(
end_times, default=trace_time.TimePoint.zero()
)
return max_time - min_time
def get_arg_values_from_events(
events: Iterator[trace_model.Event],
arg_key: str,
arg_types: type | tuple[type, ...] = object,
) -> Iterator[Any]:
"""Collect values from the |args| maps in |events|.
Args:
events: The events to collect args from.
arg_key: The key in the |args| maps to collect values from.
arg_type:
Raises:
KeyError: The value corresponding to |arg_key| was not present in one of
the event's |args| map.
Returns:
An iterator of collected values.
"""
def event_to_arg_type(event: trace_model.Event) -> Any:
has_arg: bool = arg_key in event.args
arg: Any = event.args.get(arg_key, None)
if not has_arg or not isinstance(arg, arg_types):
raise KeyError(
f"Error, expected events to include arg with key '{arg_key}' "
f"of type(s) {str(arg_types)}"
)
return arg # Cannot be None if we reach here
return map(event_to_arg_type, events)
def get_following_flow_events(
event: trace_model.Event,
min_start: trace_time.TimePoint | None = None,
) -> Iterator[trace_model.Event]:
"""Find all Events that are flow connected and follow |event|.
Args:
event: The starting event.
min_start: Optional minimum start timestamp; events starting earlier than
this timestamp are not traversed (matching `model.slice(start=min_start)`).
Returns:
An iterator of flow connected events.
"""
if min_start is not None and event.start < min_start:
return
frontier = [event]
visited: set[trace_model.Event] = set()
def set_add(
event_set: set[trace_model.Event], event: trace_model.Event
) -> bool:
length_before = len(event_set)
event_set.add(event)
return len(event_set) != length_before
while frontier:
current: trace_model.Event = frontier.pop()
if min_start is not None and current.start < min_start:
continue
added = set_add(visited, current)
if not added:
continue
if isinstance(current, trace_model.DurationEvent):
frontier.extend(current.child_durations)
frontier.extend(current.child_flows)
elif isinstance(current, trace_model.FlowEvent):
if current.enclosing_duration:
frontier.append(current.enclosing_duration)
if current.next_flow:
frontier.append(current.next_flow)
def by_start_time(event: trace_model.Event) -> int:
return event.start.to_epoch_nanoseconds()
for connected_event in sorted(visited, key=by_start_time):
yield connected_event
def get_nearest_following_flow_event(
event: trace_model.Event,
following_event_category: str,
following_event_name: str,
min_start: trace_time.TimePoint | None = None,
) -> trace_model.Event | None:
"""Find the nearest target event that is flow connected and follow |event|.
Args:
event: The starting event.
following_event_category: Trace category of the target event.
following_event_name: Trace event name of the target event.
min_start: Optional minimum start timestamp; events starting earlier than
this timestamp are ignored.
Returns:
Flow connected events. If nothing is found, None.
"""
filtered_following_events = filter_events(
get_following_flow_events(event, min_start=min_start),
category=following_event_category,
name=following_event_name,
type=trace_model.DurationEvent,
)
return next(iter(filtered_following_events), None)
def get_common_process_start_time[
E: trace_model.Event
](
model: trace_model.Model,
name: str,
type: type[E],
category: str | None = None,
) -> trace_time.TimePoint:
"""Return a consistent start time tracking the latest first event recorded
across all processes participating in the first matched event flow.
Raises:
KeyError if no matched event is found.
"""
filtered = filter_events(
model.all_events(), category=category, name=name, type=type
)
# Get the first matched event.
begin_event = next(filtered, None)
if begin_event is None:
raise KeyError(f"Error, expected event with name '{name}'")
process_ids = {begin_event.pid}
for event in get_following_flow_events(begin_event):
process_ids.add(event.pid)
process_matches = [p for p in model.processes if p.pid in process_ids]
return max(
min(
(
event.start
for thread in process.threads
for event in thread.events
),
default=trace_time.TimePoint(),
)
for process in process_matches
)
# This method looks for a possible race between trace collection start in multiple processes.
#
# This problem usually occurs between Scenic, Magma and Display processes. The flow connection
# between these processes happens through koids of objects passed to Vulkan, which may be reused.
# When there is a gap in process trace collection starts, we may see the initial vsync event(s)
# connecting to multiple flows. We can safely skip these initial events. See
# https://fxbug.dev/322849857 for more detailed examples with screenshots.
#
# This method finds the first event flow the test interested in, finds processes in the flow, and
# cuts tracing when the latest process tracing started.
#
# This method used to check processes with given process and thread name. That did not work because
# different product may have different process setup, for example Display process with different
# names.
def adjust_to_common_process_start[
E: trace_model.Event
](
model: trace_model.Model,
name: str,
type: type[E],
category: str | None = None,
) -> trace_model.Model:
"""Adjust model to a consistent start time tracking the latest first event recorded from a
list of processes. The list of processes are selected through matching event flow.
Args:
model: Trace model.
name: name of event, or None to skip this filter.
category: Category of event, or None to skip this filter.
type: Type of event. By default object to include all events.
Returns:
Model adjusted to a start time tracking the latest first event recorded from processes from
the given event flow.
Raises:
KeyError if no matched event is found.
"""
consistent_start_time = get_common_process_start_time(
model, name, type=type, category=category
)
return model.slice(start=consistent_start_time)
def standard_metrics_set(
values: list[int | float],
label_prefix: str,
unit: metrics.Unit,
percentiles: tuple[int, int, int, int, int] = (5, 25, 50, 75, 95),
durations: list[float] | None = None,
doc_prefix: str | None = None,
) -> list[metrics.TestCaseResult]:
"""Generates min, max, average and percentiles metrics for the given values.
Args:
values: Input to create the metrics from.
label_prefix: metric labels will be '{label_prefix}Min', '{label_prefix}Max',
'{label_prefix}Average' and '{label_prefix}P*' (percentiles).
unit: The metrics unit.
percentiles: Percentiles to output.
durations: Optional. If passed in, the average percentage is calculated
proportional to the duration of each Event's CPU usage, instead of
just taking the average of all the values. The latter assumes that
each value had the same duration (e.g. 1 s). For example:
cpu_percentages: [30, 2]
duration: [1, 5]
The average would be around (30*1+2*5)/(1+5) = 6.7%
instead of statistics.mean([30, 1]) = 15.5%
doc_prefix: a descriptive string with which to document this set of metrics.
Defaults to label_prefix.
Returns:
A list of TestCaseResults representing each of the generated metrics.
"""
doc_prefix = doc_prefix if doc_prefix else label_prefix
results = [
metrics.TestCaseResult(
f"{label_prefix}P{p}",
unit,
[percentile(values, p)],
f"{doc_prefix}, {p}th percentile",
)
for p in percentiles
]
results += [
metrics.TestCaseResult(
f"{label_prefix}Min",
unit,
[min(values)],
f"{doc_prefix}, minimum",
),
metrics.TestCaseResult(
f"{label_prefix}Max",
unit,
[max(values)],
f"{doc_prefix}, maximum",
),
]
average: float = 0
if durations is not None:
proportional_percentages: list[float] = [
duration * values[i] for i, duration in enumerate(durations)
]
# The total average CPU percentage is:
# (sum of the average_percentages) / (total trace duration)
average_percentage = sum(proportional_percentages) / sum(durations)
average = average_percentage
else:
average = statistics.mean(values)
results += [
metrics.TestCaseResult(
f"{label_prefix}Average",
unit,
[average],
f"{doc_prefix}, mean",
),
]
return results