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