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