xref: /linux/tools/perf/pmu-events/metric.py (revision 9e906a9dead17d81d6c2687f65e159231d0e3286) 
1# SPDX-License-Identifier: (LGPL-2.1 OR BSD-2-Clause)
2"""Parse or generate representations of perf metrics."""
3import ast
4import decimal
5import json
6import re
7from enum import Enum
8from typing import Dict, List, Optional, Set, Tuple, Union
9
10class MetricConstraint(Enum):
11  GROUPED_EVENTS = 0
12  NO_GROUP_EVENTS = 1
13  NO_GROUP_EVENTS_NMI = 2
14  NO_GROUP_EVENTS_SMT = 3
15
16class Expression:
17  """Abstract base class of elements in a metric expression."""
18
19  def ToPerfJson(self) -> str:
20    """Returns a perf json file encoded representation."""
21    raise NotImplementedError()
22
23  def ToPython(self) -> str:
24    """Returns a python expr parseable representation."""
25    raise NotImplementedError()
26
27  def Simplify(self):
28    """Returns a simplified version of self."""
29    raise NotImplementedError()
30
31  def Equals(self, other) -> bool:
32    """Returns true when two expressions are the same."""
33    raise NotImplementedError()
34
35  def Substitute(self, name: str, expression: 'Expression') -> 'Expression':
36    raise NotImplementedError()
37
38  def __str__(self) -> str:
39    return self.ToPerfJson()
40
41  def __or__(self, other: Union[int, float, 'Expression']) -> 'Operator':
42    return Operator('|', self, other)
43
44  def __ror__(self, other: Union[int, float, 'Expression']) -> 'Operator':
45    return Operator('|', other, self)
46
47  def __xor__(self, other: Union[int, float, 'Expression']) -> 'Operator':
48    return Operator('^', self, other)
49
50  def __and__(self, other: Union[int, float, 'Expression']) -> 'Operator':
51    return Operator('&', self, other)
52
53  def __rand__(self, other: Union[int, float, 'Expression']) -> 'Operator':
54    return Operator('&', other, self)
55
56  def __lt__(self, other: Union[int, float, 'Expression']) -> 'Operator':
57    return Operator('<', self, other)
58
59  def __gt__(self, other: Union[int, float, 'Expression']) -> 'Operator':
60    return Operator('>', self, other)
61
62  def __add__(self, other: Union[int, float, 'Expression']) -> 'Operator':
63    return Operator('+', self, other)
64
65  def __radd__(self, other: Union[int, float, 'Expression']) -> 'Operator':
66    return Operator('+', other, self)
67
68  def __sub__(self, other: Union[int, float, 'Expression']) -> 'Operator':
69    return Operator('-', self, other)
70
71  def __rsub__(self, other: Union[int, float, 'Expression']) -> 'Operator':
72    return Operator('-', other, self)
73
74  def __mul__(self, other: Union[int, float, 'Expression']) -> 'Operator':
75    return Operator('*', self, other)
76
77  def __rmul__(self, other: Union[int, float, 'Expression']) -> 'Operator':
78    return Operator('*', other, self)
79
80  def __truediv__(self, other: Union[int, float, 'Expression']) -> 'Operator':
81    return Operator('/', self, other)
82
83  def __rtruediv__(self, other: Union[int, float, 'Expression']) -> 'Operator':
84    return Operator('/', other, self)
85
86  def __mod__(self, other: Union[int, float, 'Expression']) -> 'Operator':
87    return Operator('%', self, other)
88
89
90def _Constify(val: Union[bool, int, float, Expression]) -> Expression:
91  """Used to ensure that the nodes in the expression tree are all Expression."""
92  if isinstance(val, bool):
93    return Constant(1 if val else 0)
94  if isinstance(val, (int, float)):
95    return Constant(val)
96  return val
97
98
99# Simple lookup for operator precedence, used to avoid unnecessary
100# brackets. Precedence matches that of the simple expression parser
101# but differs from python where comparisons are lower precedence than
102# the bitwise &, ^, | but not the logical versions that the expression
103# parser doesn't have.
104_PRECEDENCE = {
105    '|': 0,
106    '^': 1,
107    '&': 2,
108    '<': 3,
109    '>': 3,
110    '+': 4,
111    '-': 4,
112    '*': 5,
113    '/': 5,
114    '%': 5,
115}
116
117
118class Operator(Expression):
119  """Represents a binary operator in the parse tree."""
120
121  def __init__(self, operator: str, lhs: Union[int, float, Expression],
122               rhs: Union[int, float, Expression]):
123    self.operator = operator
124    self.lhs = _Constify(lhs)
125    self.rhs = _Constify(rhs)
126
127  def Bracket(self,
128              other: Expression,
129              other_str: str,
130              rhs: bool = False) -> str:
131    """If necessary brackets the given other value.
132
133    If ``other`` is an operator then a bracket is necessary when
134    this/self operator has higher precedence. Consider: '(a + b) * c',
135    ``other_str`` will be 'a + b'. A bracket is necessary as without
136    the bracket 'a + b * c' will evaluate 'b * c' first. However, '(a
137    * b) + c' doesn't need a bracket as 'a * b' will always be
138    evaluated first. For 'a / (b * c)' (ie the same precedence level
139    operations) then we add the bracket to best match the original
140    input, but not for '(a / b) * c' where the bracket is unnecessary.
141
142    Args:
143      other (Expression): is a lhs or rhs operator
144      other_str (str): ``other`` in the appropriate string form
145      rhs (bool):  is ``other`` on the RHS
146
147    Returns:
148      str: possibly bracketed other_str
149    """
150    if isinstance(other, Operator):
151      if _PRECEDENCE.get(self.operator, -1) > _PRECEDENCE.get(
152          other.operator, -1):
153        return f'({other_str})'
154      if rhs and _PRECEDENCE.get(self.operator, -1) == _PRECEDENCE.get(
155          other.operator, -1):
156        return f'({other_str})'
157    return other_str
158
159  def ToPerfJson(self):
160    return (f'{self.Bracket(self.lhs, self.lhs.ToPerfJson())} {self.operator} '
161            f'{self.Bracket(self.rhs, self.rhs.ToPerfJson(), True)}')
162
163  def ToPython(self):
164    return (f'{self.Bracket(self.lhs, self.lhs.ToPython())} {self.operator} '
165            f'{self.Bracket(self.rhs, self.rhs.ToPython(), True)}')
166
167  def Simplify(self) -> Expression:
168    lhs = self.lhs.Simplify()
169    rhs = self.rhs.Simplify()
170    if isinstance(lhs, Constant) and isinstance(rhs, Constant):
171      return Constant(ast.literal_eval(lhs + self.operator + rhs))
172
173    if isinstance(self.lhs, Constant):
174      if self.operator in ('+', '|') and lhs.value == '0':
175        return rhs
176
177      # Simplify multiplication by 0 except for the slot event which
178      # is deliberately introduced using this pattern.
179      if self.operator == '*' and lhs.value == '0' and (
180          not isinstance(rhs, Event) or 'slots' not in rhs.name.lower()):
181        return Constant(0)
182
183      if self.operator == '*' and lhs.value == '1':
184        return rhs
185
186    if isinstance(rhs, Constant):
187      if self.operator in ('+', '|') and rhs.value == '0':
188        return lhs
189
190      if self.operator == '*' and rhs.value == '0':
191        return Constant(0)
192
193      if self.operator == '*' and self.rhs.value == '1':
194        return lhs
195
196    return Operator(self.operator, lhs, rhs)
197
198  def Equals(self, other: Expression) -> bool:
199    if isinstance(other, Operator):
200      return self.operator == other.operator and self.lhs.Equals(
201          other.lhs) and self.rhs.Equals(other.rhs)
202    return False
203
204  def Substitute(self, name: str, expression: Expression) -> Expression:
205    if self.Equals(expression):
206      return Event(name)
207    lhs = self.lhs.Substitute(name, expression)
208    rhs = None
209    if self.rhs:
210      rhs = self.rhs.Substitute(name, expression)
211    return Operator(self.operator, lhs, rhs)
212
213
214class Select(Expression):
215  """Represents a select ternary in the parse tree."""
216
217  def __init__(self, true_val: Union[int, float, Expression],
218               cond: Union[int, float, Expression],
219               false_val: Union[int, float, Expression]):
220    self.true_val = _Constify(true_val)
221    self.cond = _Constify(cond)
222    self.false_val = _Constify(false_val)
223
224  def ToPerfJson(self):
225    true_str = self.true_val.ToPerfJson()
226    cond_str = self.cond.ToPerfJson()
227    false_str = self.false_val.ToPerfJson()
228    return f'({true_str} if {cond_str} else {false_str})'
229
230  def ToPython(self):
231    return (f'Select({self.true_val.ToPython()}, {self.cond.ToPython()}, '
232            f'{self.false_val.ToPython()})')
233
234  def Simplify(self) -> Expression:
235    cond = self.cond.Simplify()
236    true_val = self.true_val.Simplify()
237    false_val = self.false_val.Simplify()
238    if isinstance(cond, Constant):
239      return false_val if cond.value == '0' else true_val
240
241    if true_val.Equals(false_val):
242      return true_val
243
244    return Select(true_val, cond, false_val)
245
246  def Equals(self, other: Expression) -> bool:
247    if isinstance(other, Select):
248      return self.cond.Equals(other.cond) and self.false_val.Equals(
249          other.false_val) and self.true_val.Equals(other.true_val)
250    return False
251
252  def Substitute(self, name: str, expression: Expression) -> Expression:
253    if self.Equals(expression):
254      return Event(name)
255    true_val = self.true_val.Substitute(name, expression)
256    cond = self.cond.Substitute(name, expression)
257    false_val = self.false_val.Substitute(name, expression)
258    return Select(true_val, cond, false_val)
259
260
261class Function(Expression):
262  """A function in an expression like min, max, d_ratio."""
263
264  def __init__(self,
265               fn: str,
266               lhs: Union[int, float, Expression],
267               rhs: Optional[Union[int, float, Expression]] = None):
268    self.fn = fn
269    self.lhs = _Constify(lhs)
270    self.rhs = _Constify(rhs)
271
272  def ToPerfJson(self):
273    if self.rhs:
274      return f'{self.fn}({self.lhs.ToPerfJson()}, {self.rhs.ToPerfJson()})'
275    return f'{self.fn}({self.lhs.ToPerfJson()})'
276
277  def ToPython(self):
278    if self.rhs:
279      return f'{self.fn}({self.lhs.ToPython()}, {self.rhs.ToPython()})'
280    return f'{self.fn}({self.lhs.ToPython()})'
281
282  def Simplify(self) -> Expression:
283    lhs = self.lhs.Simplify()
284    rhs = self.rhs.Simplify() if self.rhs else None
285    if isinstance(lhs, Constant) and isinstance(rhs, Constant):
286      if self.fn == 'd_ratio':
287        if rhs.value == '0':
288          return Constant(0)
289        Constant(ast.literal_eval(f'{lhs} / {rhs}'))
290      return Constant(ast.literal_eval(f'{self.fn}({lhs}, {rhs})'))
291
292    return Function(self.fn, lhs, rhs)
293
294  def Equals(self, other: Expression) -> bool:
295    if isinstance(other, Function):
296      result = self.fn == other.fn and self.lhs.Equals(other.lhs)
297      if self.rhs:
298        result = result and self.rhs.Equals(other.rhs)
299      return result
300    return False
301
302  def Substitute(self, name: str, expression: Expression) -> Expression:
303    if self.Equals(expression):
304      return Event(name)
305    lhs = self.lhs.Substitute(name, expression)
306    rhs = None
307    if self.rhs:
308      rhs = self.rhs.Substitute(name, expression)
309    return Function(self.fn, lhs, rhs)
310
311
312def _FixEscapes(s: str) -> str:
313  s = re.sub(r'([^\\]),', r'\1\\,', s)
314  return re.sub(r'([^\\])=', r'\1\\=', s)
315
316
317class Event(Expression):
318  """An event in an expression."""
319
320  def __init__(self, name: str, legacy_name: str = ''):
321    self.name = _FixEscapes(name)
322    self.legacy_name = _FixEscapes(legacy_name)
323
324  def ToPerfJson(self):
325    result = re.sub('/', '@', self.name)
326    return result
327
328  def ToPython(self):
329    return f'Event(r"{self.name}")'
330
331  def Simplify(self) -> Expression:
332    return self
333
334  def Equals(self, other: Expression) -> bool:
335    return isinstance(other, Event) and self.name == other.name
336
337  def Substitute(self, name: str, expression: Expression) -> Expression:
338    return self
339
340
341class Constant(Expression):
342  """A constant within the expression tree."""
343
344  def __init__(self, value: Union[float, str]):
345    ctx = decimal.Context()
346    ctx.prec = 20
347    dec = ctx.create_decimal(repr(value) if isinstance(value, float) else value)
348    self.value = dec.normalize().to_eng_string()
349    self.value = self.value.replace('+', '')
350    self.value = self.value.replace('E', 'e')
351
352  def ToPerfJson(self):
353    return self.value
354
355  def ToPython(self):
356    return f'Constant({self.value})'
357
358  def Simplify(self) -> Expression:
359    return self
360
361  def Equals(self, other: Expression) -> bool:
362    return isinstance(other, Constant) and self.value == other.value
363
364  def Substitute(self, name: str, expression: Expression) -> Expression:
365    return self
366
367
368class Literal(Expression):
369  """A runtime literal within the expression tree."""
370
371  def __init__(self, value: str):
372    self.value = value
373
374  def ToPerfJson(self):
375    return self.value
376
377  def ToPython(self):
378    return f'Literal({self.value})'
379
380  def Simplify(self) -> Expression:
381    return self
382
383  def Equals(self, other: Expression) -> bool:
384    return isinstance(other, Literal) and self.value == other.value
385
386  def Substitute(self, name: str, expression: Expression) -> Expression:
387    return self
388
389
390def min(lhs: Union[int, float, Expression], rhs: Union[int, float,
391                                                       Expression]) -> Function:
392  # pylint: disable=redefined-builtin
393  # pylint: disable=invalid-name
394  return Function('min', lhs, rhs)
395
396
397def max(lhs: Union[int, float, Expression], rhs: Union[int, float,
398                                                       Expression]) -> Function:
399  # pylint: disable=redefined-builtin
400  # pylint: disable=invalid-name
401  return Function('max', lhs, rhs)
402
403
404def d_ratio(lhs: Union[int, float, Expression],
405            rhs: Union[int, float, Expression]) -> Function:
406  # pylint: disable=redefined-builtin
407  # pylint: disable=invalid-name
408  return Function('d_ratio', lhs, rhs)
409
410
411def source_count(event: Event) -> Function:
412  # pylint: disable=redefined-builtin
413  # pylint: disable=invalid-name
414  return Function('source_count', event)
415
416
417def has_event(event: Event) -> Function:
418  # pylint: disable=redefined-builtin
419  # pylint: disable=invalid-name
420  return Function('has_event', event)
421
422def strcmp_cpuid_str(cpuid: Event) -> Function:
423  # pylint: disable=redefined-builtin
424  # pylint: disable=invalid-name
425  return Function('strcmp_cpuid_str', cpuid)
426
427class Metric:
428  """An individual metric that will specifiable on the perf command line."""
429  groups: Set[str]
430  expr: Expression
431  scale_unit: str
432  constraint: MetricConstraint
433  threshold: Optional[Expression]
434
435  def __init__(self,
436               name: str,
437               description: str,
438               expr: Expression,
439               scale_unit: str,
440               constraint: MetricConstraint = MetricConstraint.GROUPED_EVENTS,
441               threshold: Optional[Expression] = None):
442    self.name = name
443    self.description = description
444    self.expr = expr.Simplify()
445    # Workraound valid_only_metric hiding certain metrics based on unit.
446    scale_unit = scale_unit.replace('/sec', ' per sec')
447    if scale_unit[0].isdigit():
448      self.scale_unit = scale_unit
449    else:
450      self.scale_unit = f'1{scale_unit}'
451    self.constraint = constraint
452    self.threshold = threshold
453    self.groups = set()
454
455  def __lt__(self, other):
456    """Sort order."""
457    return self.name < other.name
458
459  def AddToMetricGroup(self, group):
460    """Callback used when being added to a MetricGroup."""
461    if group.name:
462      self.groups.add(group.name)
463
464  def Flatten(self) -> Set['Metric']:
465    """Return a leaf metric."""
466    return set([self])
467
468  def ToPerfJson(self) -> Dict[str, str]:
469    """Return as dictionary for Json generation."""
470    result = {
471        'MetricName': self.name,
472        'MetricGroup': ';'.join(sorted(self.groups)),
473        'BriefDescription': self.description,
474        'MetricExpr': self.expr.ToPerfJson(),
475        'ScaleUnit': self.scale_unit
476    }
477    if self.constraint != MetricConstraint.GROUPED_EVENTS:
478      result['MetricConstraint'] = self.constraint.name
479    if self.threshold:
480      result['MetricThreshold'] = self.threshold.ToPerfJson()
481
482    return result
483
484  def ToMetricGroupDescriptions(self, root: bool = True) -> Dict[str, str]:
485    return {}
486
487class MetricGroup:
488  """A group of metrics.
489
490  Metric groups may be specificd on the perf command line, but within
491  the json they aren't encoded. Metrics may be in multiple groups
492  which can facilitate arrangements similar to trees.
493  """
494
495  def __init__(self, name: str,
496               metric_list: List[Union[Optional[Metric], Optional['MetricGroup']]],
497               description: Optional[str] = None):
498    self.name = name
499    self.metric_list = []
500    self.description = description
501    for metric in metric_list:
502      if metric:
503        self.metric_list.append(metric)
504        metric.AddToMetricGroup(self)
505
506  def AddToMetricGroup(self, group):
507    """Callback used when a MetricGroup is added into another."""
508    for metric in self.metric_list:
509      metric.AddToMetricGroup(group)
510
511  def Flatten(self) -> Set[Metric]:
512    """Returns a set of all leaf metrics."""
513    result = set()
514    for x in self.metric_list:
515      result = result.union(x.Flatten())
516
517    return result
518
519  def ToPerfJson(self) -> List[Dict[str, str]]:
520    result = []
521    for x in sorted(self.Flatten()):
522      result.append(x.ToPerfJson())
523    return result
524
525  def ToMetricGroupDescriptions(self, root: bool = True) -> Dict[str, str]:
526    result = {self.name: self.description} if self.description else {}
527    for x in self.metric_list:
528      result.update(x.ToMetricGroupDescriptions(False))
529    return result
530
531  def __str__(self) -> str:
532    return str(self.ToPerfJson())
533
534
535def JsonEncodeMetric(x: MetricGroup):
536  class MetricJsonEncoder(json.JSONEncoder):
537    """Special handling for Metric objects."""
538
539    def default(self, o):
540      if isinstance(o, Metric) or isinstance(o, MetricGroup):
541        return o.ToPerfJson()
542      return json.JSONEncoder.default(self, o)
543
544  return json.dumps(x, indent=2, cls=MetricJsonEncoder)
545
546
547def JsonEncodeMetricGroupDescriptions(x: MetricGroup):
548  return json.dumps(x.ToMetricGroupDescriptions(), indent=2)
549
550
551class _RewriteIfExpToSelect(ast.NodeTransformer):
552  """Transformer to convert if-else nodes to Select expressions."""
553
554  def visit_IfExp(self, node):
555    # pylint: disable=invalid-name
556    self.generic_visit(node)
557    call = ast.Call(
558        func=ast.Name(id='Select', ctx=ast.Load()),
559        args=[node.body, node.test, node.orelse],
560        keywords=[])
561    ast.copy_location(call, node.test)
562    return call
563
564
565def ParsePerfJson(orig: str) -> Expression:
566  """A simple json metric expression decoder.
567
568  Converts a json encoded metric expression by way of python's ast and
569  eval routine. First tokens are mapped to Event calls, then
570  accidentally converted keywords or literals are mapped to their
571  appropriate calls. Python's ast is used to match if-else that can't
572  be handled via operator overloading. Finally the ast is evaluated.
573
574  Args:
575    orig (str): String to parse.
576
577  Returns:
578    Expression: The parsed string.
579  """
580  # pylint: disable=eval-used
581  py = orig.strip()
582  # First try to convert everything that looks like a string (event name) into Event(r"EVENT_NAME").
583  # This isn't very selective so is followed up by converting some unwanted conversions back again
584  py = re.sub(r'([a-zA-Z][^-+/\* \\\(\),]*(?:\\.[^-+/\* \\\(\),]*)*)',
585              r'Event(r"\1")', py)
586  # If it started with a # it should have been a literal, rather than an event name
587  py = re.sub(r'#Event\(r"([^"]*)"\)', r'Literal("#\1")', py)
588  # Fix events wrongly broken at a ','
589  while True:
590    prev_py = py
591    py = re.sub(r'Event\(r"([^"]*)"\),Event\(r"([^"]*)"\)', r'Event(r"\1,\2")', py)
592    if py == prev_py:
593      break
594  # Convert accidentally converted hex constants ("0Event(r"xDEADBEEF)"") back to a constant,
595  # but keep it wrapped in Event(), otherwise Python drops the 0x prefix and it gets interpreted as
596  # a double by the Bison parser
597  py = re.sub(r'0Event\(r"[xX]([0-9a-fA-F]*)"\)', r'Event("0x\1")', py)
598  # Convert accidentally converted scientific notation constants back
599  py = re.sub(r'([0-9]+)Event\(r"(e[0-9]*)"\)', r'\1\2', py)
600  # Convert all the known keywords back from events to just the keyword
601  keywords = ['if', 'else', 'min', 'max', 'd_ratio', 'source_count', 'has_event', 'strcmp_cpuid_str']
602  for kw in keywords:
603    py = re.sub(rf'Event\(r"{kw}"\)', kw, py)
604  try:
605    parsed = ast.parse(py, mode='eval')
606  except SyntaxError as e:
607    raise SyntaxError(f'Parsing expression:\n{orig}') from e
608  _RewriteIfExpToSelect().visit(parsed)
609  parsed = ast.fix_missing_locations(parsed)
610  return _Constify(eval(compile(parsed, orig, 'eval')))
611
612def RewriteMetricsInTermsOfOthers(metrics: List[Tuple[str, str, Expression]]
613                                  )-> Dict[Tuple[str, str], Expression]:
614  """Shorten metrics by rewriting in terms of others.
615
616  Args:
617    metrics (list): pmus, metric names and their expressions.
618  Returns:
619    Dict: mapping from a pmu, metric name pair to a shortened expression.
620  """
621  updates: Dict[Tuple[str, str], Expression] = dict()
622  for outer_pmu, outer_name, outer_expression in metrics:
623    if outer_pmu is None:
624      outer_pmu = 'cpu'
625    updated = outer_expression
626    while True:
627      for inner_pmu, inner_name, inner_expression in metrics:
628        if inner_pmu is None:
629          inner_pmu = 'cpu'
630        if inner_pmu.lower() != outer_pmu.lower():
631          continue
632        if inner_name.lower() == outer_name.lower():
633          continue
634        if (inner_pmu, inner_name) in updates:
635          inner_expression = updates[(inner_pmu, inner_name)]
636        updated = updated.Substitute(inner_name, inner_expression)
637      if updated.Equals(outer_expression):
638        break
639      if (outer_pmu, outer_name) in updates and updated.Equals(updates[(outer_pmu, outer_name)]):
640        break
641      updates[(outer_pmu, outer_name)] = updated
642  return updates
643