1 /* Simple expression parser */ 2 %{ 3 #define YYDEBUG 1 4 #include <assert.h> 5 #include <math.h> 6 #include <stdlib.h> 7 #include "util/debug.h" 8 #define IN_EXPR_Y 1 9 #include "expr.h" 10 #include "expr-bison.h" 11 int expr_lex(YYSTYPE * yylval_param , void *yyscanner); 12 %} 13 14 %define api.pure full 15 16 %parse-param { double *final_val } 17 %parse-param { struct expr_parse_ctx *ctx } 18 %parse-param { bool compute_ids } 19 %parse-param {void *scanner} 20 %lex-param {void* scanner} 21 22 %union { 23 double num; 24 char *str; 25 struct ids { 26 /* 27 * When creating ids, holds the working set of event ids. NULL 28 * implies the set is empty. 29 */ 30 struct hashmap *ids; 31 /* 32 * The metric value. When not creating ids this is the value 33 * read from a counter, a constant or some computed value. When 34 * creating ids the value is either a constant or BOTTOM. NAN is 35 * used as the special BOTTOM value, representing a "set of all 36 * values" case. 37 */ 38 double val; 39 } ids; 40 } 41 42 %token ID NUMBER MIN MAX IF ELSE LITERAL D_RATIO SOURCE_COUNT HAS_EVENT STRCMP_CPUID_STR EXPR_ERROR 43 %left MIN MAX IF 44 %left '|' 45 %left '^' 46 %left '&' 47 %left '<' '>' 48 %left '-' '+' 49 %left '*' '/' '%' 50 %left NEG NOT 51 %type <num> NUMBER LITERAL 52 %type <str> ID 53 %destructor { free ($$); } <str> 54 %type <ids> expr if_expr 55 %destructor { ids__free($$.ids); } <ids> 56 57 %{ 58 static void expr_error(double *final_val __maybe_unused, 59 struct expr_parse_ctx *ctx __maybe_unused, 60 bool compute_ids __maybe_unused, 61 void *scanner __maybe_unused, 62 const char *s) 63 { 64 pr_debug("%s\n", s); 65 } 66 67 /* 68 * During compute ids, the special "bottom" value uses NAN to represent the set 69 * of all values. NAN is selected as it isn't a useful constant value. 70 */ 71 #define BOTTOM NAN 72 73 /* During computing ids, does val represent a constant (non-BOTTOM) value? */ 74 static bool is_const(double val) 75 { 76 return isfinite(val); 77 } 78 79 static struct ids union_expr(struct ids ids1, struct ids ids2) 80 { 81 struct ids result = { 82 .val = BOTTOM, 83 .ids = ids__union(ids1.ids, ids2.ids), 84 }; 85 return result; 86 } 87 88 static struct ids handle_id(struct expr_parse_ctx *ctx, char *id, 89 bool compute_ids, bool source_count) 90 { 91 struct ids result; 92 93 if (!compute_ids) { 94 /* 95 * Compute the event's value from ID. If the ID isn't known then 96 * it isn't used to compute the formula so set to NAN. 97 */ 98 struct expr_id_data *data; 99 100 result.val = NAN; 101 if (expr__resolve_id(ctx, id, &data) == 0) { 102 result.val = source_count 103 ? expr_id_data__source_count(data) 104 : expr_id_data__value(data); 105 } 106 result.ids = NULL; 107 free(id); 108 } else { 109 /* 110 * Set the value to BOTTOM to show that any value is possible 111 * when the event is computed. Create a set of just the ID. 112 */ 113 result.val = BOTTOM; 114 result.ids = ids__new(); 115 if (!result.ids || ids__insert(result.ids, id)) { 116 pr_err("Error creating IDs for '%s'", id); 117 free(id); 118 } 119 } 120 return result; 121 } 122 123 /* 124 * If we're not computing ids or $1 and $3 are constants, compute the new 125 * constant value using OP. Its invariant that there are no ids. If computing 126 * ids for non-constants union the set of IDs that must be computed. 127 */ 128 #define BINARY_OP(RESULT, OP, LHS, RHS) \ 129 if (!compute_ids || (is_const(LHS.val) && is_const(RHS.val))) { \ 130 assert(LHS.ids == NULL); \ 131 assert(RHS.ids == NULL); \ 132 if (isnan(LHS.val) || isnan(RHS.val)) { \ 133 RESULT.val = NAN; \ 134 } else { \ 135 RESULT.val = LHS.val OP RHS.val; \ 136 } \ 137 RESULT.ids = NULL; \ 138 } else { \ 139 RESULT = union_expr(LHS, RHS); \ 140 } 141 142 %} 143 %% 144 145 start: if_expr 146 { 147 if (compute_ids) 148 ctx->ids = ids__union($1.ids, ctx->ids); 149 150 if (final_val) 151 *final_val = $1.val; 152 } 153 ; 154 155 if_expr: expr IF expr ELSE if_expr 156 { 157 if (fpclassify($3.val) == FP_ZERO) { 158 /* 159 * The IF expression evaluated to 0 so treat as false, take the 160 * ELSE and discard everything else. 161 */ 162 $$.val = $5.val; 163 $$.ids = $5.ids; 164 ids__free($1.ids); 165 ids__free($3.ids); 166 } else if (!compute_ids || is_const($3.val)) { 167 /* 168 * If ids aren't computed then treat the expression as true. If 169 * ids are being computed and the IF expr is a non-zero 170 * constant, then also evaluate the true case. 171 */ 172 $$.val = $1.val; 173 $$.ids = $1.ids; 174 ids__free($3.ids); 175 ids__free($5.ids); 176 } else if ($1.val == $5.val) { 177 /* 178 * LHS == RHS, so both are an identical constant. No need to 179 * evaluate any events. 180 */ 181 $$.val = $1.val; 182 $$.ids = NULL; 183 ids__free($1.ids); 184 ids__free($3.ids); 185 ids__free($5.ids); 186 } else { 187 /* 188 * Value is either the LHS or RHS and we need the IF expression 189 * to compute it. 190 */ 191 $$ = union_expr($1, union_expr($3, $5)); 192 } 193 } 194 | expr 195 ; 196 197 expr: NUMBER 198 { 199 $$.val = $1; 200 $$.ids = NULL; 201 } 202 | ID { $$ = handle_id(ctx, $1, compute_ids, /*source_count=*/false); } 203 | SOURCE_COUNT '(' ID ')' { $$ = handle_id(ctx, $3, compute_ids, /*source_count=*/true); } 204 | HAS_EVENT '(' ID ')' 205 { 206 $$.val = expr__has_event(ctx, compute_ids, $3); 207 $$.ids = NULL; 208 free($3); 209 } 210 | STRCMP_CPUID_STR '(' ID ')' 211 { 212 $$.val = expr__strcmp_cpuid_str(ctx, compute_ids, $3); 213 $$.ids = NULL; 214 free($3); 215 } 216 | expr '|' expr 217 { 218 if (is_const($1.val) && is_const($3.val)) { 219 assert($1.ids == NULL); 220 assert($3.ids == NULL); 221 $$.ids = NULL; 222 $$.val = (fpclassify($1.val) == FP_ZERO && fpclassify($3.val) == FP_ZERO) ? 0 : 1; 223 } else if (is_const($1.val)) { 224 assert($1.ids == NULL); 225 if (fpclassify($1.val) == FP_ZERO) { 226 $$ = $3; 227 } else { 228 $$.val = 1; 229 $$.ids = NULL; 230 ids__free($3.ids); 231 } 232 } else if (is_const($3.val)) { 233 assert($3.ids == NULL); 234 if (fpclassify($3.val) == FP_ZERO) { 235 $$ = $1; 236 } else { 237 $$.val = 1; 238 $$.ids = NULL; 239 ids__free($1.ids); 240 } 241 } else { 242 $$ = union_expr($1, $3); 243 } 244 } 245 | expr '&' expr 246 { 247 if (is_const($1.val) && is_const($3.val)) { 248 assert($1.ids == NULL); 249 assert($3.ids == NULL); 250 $$.val = (fpclassify($1.val) != FP_ZERO && fpclassify($3.val) != FP_ZERO) ? 1 : 0; 251 $$.ids = NULL; 252 } else if (is_const($1.val)) { 253 assert($1.ids == NULL); 254 if (fpclassify($1.val) != FP_ZERO) { 255 $$ = $3; 256 } else { 257 $$.val = 0; 258 $$.ids = NULL; 259 ids__free($3.ids); 260 } 261 } else if (is_const($3.val)) { 262 assert($3.ids == NULL); 263 if (fpclassify($3.val) != FP_ZERO) { 264 $$ = $1; 265 } else { 266 $$.val = 0; 267 $$.ids = NULL; 268 ids__free($1.ids); 269 } 270 } else { 271 $$ = union_expr($1, $3); 272 } 273 } 274 | expr '^' expr 275 { 276 if (is_const($1.val) && is_const($3.val)) { 277 assert($1.ids == NULL); 278 assert($3.ids == NULL); 279 $$.val = (fpclassify($1.val) == FP_ZERO) != (fpclassify($3.val) == FP_ZERO) ? 1 : 0; 280 $$.ids = NULL; 281 } else { 282 $$ = union_expr($1, $3); 283 } 284 } 285 | expr '<' expr { BINARY_OP($$, <, $1, $3); } 286 | expr '>' expr { BINARY_OP($$, >, $1, $3); } 287 | expr '+' expr { BINARY_OP($$, +, $1, $3); } 288 | expr '-' expr { BINARY_OP($$, -, $1, $3); } 289 | expr '*' expr { BINARY_OP($$, *, $1, $3); } 290 | expr '/' expr 291 { 292 if (fpclassify($3.val) == FP_ZERO) { 293 pr_debug("division by zero\n"); 294 assert($3.ids == NULL); 295 if (compute_ids) 296 ids__free($1.ids); 297 $$.val = NAN; 298 $$.ids = NULL; 299 } else if (!compute_ids || (is_const($1.val) && is_const($3.val))) { 300 assert($1.ids == NULL); 301 assert($3.ids == NULL); 302 $$.val = $1.val / $3.val; 303 $$.ids = NULL; 304 } else { 305 /* LHS and/or RHS need computing from event IDs so union. */ 306 $$ = union_expr($1, $3); 307 } 308 } 309 | expr '%' expr 310 { 311 if (fpclassify($3.val) == FP_ZERO) { 312 pr_debug("division by zero\n"); 313 YYABORT; 314 } else if (!compute_ids || (is_const($1.val) && is_const($3.val))) { 315 assert($1.ids == NULL); 316 assert($3.ids == NULL); 317 $$.val = (long)$1.val % (long)$3.val; 318 $$.ids = NULL; 319 } else { 320 /* LHS and/or RHS need computing from event IDs so union. */ 321 $$ = union_expr($1, $3); 322 } 323 } 324 | D_RATIO '(' expr ',' expr ')' 325 { 326 if (fpclassify($5.val) == FP_ZERO) { 327 /* 328 * Division by constant zero always yields zero and no events 329 * are necessary. 330 */ 331 assert($5.ids == NULL); 332 $$.val = 0.0; 333 $$.ids = NULL; 334 ids__free($3.ids); 335 } else if (!compute_ids || (is_const($3.val) && is_const($5.val))) { 336 assert($3.ids == NULL); 337 assert($5.ids == NULL); 338 $$.val = $3.val / $5.val; 339 $$.ids = NULL; 340 } else { 341 /* LHS and/or RHS need computing from event IDs so union. */ 342 $$ = union_expr($3, $5); 343 } 344 } 345 | '-' expr %prec NEG 346 { 347 $$.val = -$2.val; 348 $$.ids = $2.ids; 349 } 350 | '(' if_expr ')' 351 { 352 $$ = $2; 353 } 354 | MIN '(' expr ',' expr ')' 355 { 356 if (!compute_ids) { 357 $$.val = $3.val < $5.val ? $3.val : $5.val; 358 $$.ids = NULL; 359 } else { 360 $$ = union_expr($3, $5); 361 } 362 } 363 | MAX '(' expr ',' expr ')' 364 { 365 if (!compute_ids) { 366 $$.val = $3.val > $5.val ? $3.val : $5.val; 367 $$.ids = NULL; 368 } else { 369 $$ = union_expr($3, $5); 370 } 371 } 372 | LITERAL 373 { 374 $$.val = $1; 375 $$.ids = NULL; 376 } 377 ; 378 379 %% 380