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 AGGR_NR 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 enum expr_id_kind { 91 EXPR_ID_KIND__VALUE, 92 EXPR_ID_KIND__SOURCE_COUNT, 93 EXPR_ID_KIND__AGGR_NR, 94 }; 95 96 static struct ids handle_id(struct expr_parse_ctx *ctx, char *id, 97 bool compute_ids, enum expr_id_kind kind) 98 { 99 struct ids result; 100 101 if (!compute_ids) { 102 /* 103 * Compute the event's value from ID. If the ID isn't known then 104 * it isn't used to compute the formula so set to NAN. 105 */ 106 struct expr_id_data *data; 107 108 result.val = NAN; 109 if (expr__resolve_id(ctx, id, &data) == 0) { 110 if (kind == EXPR_ID_KIND__SOURCE_COUNT) 111 result.val = expr_id_data__source_count(data); 112 else if (kind == EXPR_ID_KIND__AGGR_NR) 113 result.val = expr_id_data__aggr_nr(data); 114 else 115 result.val = expr_id_data__value(data); 116 } 117 result.ids = NULL; 118 free(id); 119 } else { 120 /* 121 * Set the value to BOTTOM to show that any value is possible 122 * when the event is computed. Create a set of just the ID. 123 */ 124 result.val = BOTTOM; 125 result.ids = ids__new(); 126 if (!result.ids || ids__insert(result.ids, id)) { 127 pr_err("Error creating IDs for '%s'", id); 128 free(id); 129 } 130 } 131 return result; 132 } 133 134 /* 135 * If we're not computing ids or $1 and $3 are constants, compute the new 136 * constant value using OP. Its invariant that there are no ids. If computing 137 * ids for non-constants union the set of IDs that must be computed. 138 */ 139 #define BINARY_OP(RESULT, OP, LHS, RHS) \ 140 if (!compute_ids || (is_const(LHS.val) && is_const(RHS.val))) { \ 141 assert(LHS.ids == NULL); \ 142 assert(RHS.ids == NULL); \ 143 if (isnan(LHS.val) || isnan(RHS.val)) { \ 144 RESULT.val = NAN; \ 145 } else { \ 146 RESULT.val = LHS.val OP RHS.val; \ 147 } \ 148 RESULT.ids = NULL; \ 149 } else { \ 150 RESULT = union_expr(LHS, RHS); \ 151 } 152 153 %} 154 %% 155 156 start: if_expr 157 { 158 if (compute_ids) 159 ctx->ids = ids__union($1.ids, ctx->ids); 160 161 if (final_val) 162 *final_val = $1.val; 163 } 164 ; 165 166 if_expr: expr IF expr ELSE if_expr 167 { 168 if (fpclassify($3.val) == FP_ZERO) { 169 /* 170 * The IF expression evaluated to 0 so treat as false, take the 171 * ELSE and discard everything else. 172 */ 173 $$.val = $5.val; 174 $$.ids = $5.ids; 175 ids__free($1.ids); 176 ids__free($3.ids); 177 } else if (!compute_ids || is_const($3.val)) { 178 /* 179 * If ids aren't computed then treat the expression as true. If 180 * ids are being computed and the IF expr is a non-zero 181 * constant, then also evaluate the true case. 182 */ 183 $$.val = $1.val; 184 $$.ids = $1.ids; 185 ids__free($3.ids); 186 ids__free($5.ids); 187 } else if ($1.val == $5.val) { 188 /* 189 * LHS == RHS, so both are an identical constant. No need to 190 * evaluate any events. 191 */ 192 $$.val = $1.val; 193 $$.ids = NULL; 194 ids__free($1.ids); 195 ids__free($3.ids); 196 ids__free($5.ids); 197 } else { 198 /* 199 * Value is either the LHS or RHS and we need the IF expression 200 * to compute it. 201 */ 202 $$ = union_expr($1, union_expr($3, $5)); 203 } 204 } 205 | expr 206 ; 207 208 expr: NUMBER 209 { 210 $$.val = $1; 211 $$.ids = NULL; 212 } 213 | ID { $$ = handle_id(ctx, $1, compute_ids, EXPR_ID_KIND__VALUE); } 214 | SOURCE_COUNT '(' ID ')' { $$ = handle_id(ctx, $3, compute_ids, EXPR_ID_KIND__SOURCE_COUNT); } 215 | AGGR_NR '(' ID ')' { $$ = handle_id(ctx, $3, compute_ids, EXPR_ID_KIND__AGGR_NR); } 216 | HAS_EVENT '(' ID ')' 217 { 218 $$.val = expr__has_event(ctx, compute_ids, $3); 219 $$.ids = NULL; 220 free($3); 221 } 222 | STRCMP_CPUID_STR '(' ID ')' 223 { 224 $$.val = expr__strcmp_cpuid_str(ctx, compute_ids, $3); 225 $$.ids = NULL; 226 free($3); 227 } 228 | expr '|' expr 229 { 230 if (is_const($1.val) && is_const($3.val)) { 231 assert($1.ids == NULL); 232 assert($3.ids == NULL); 233 $$.ids = NULL; 234 $$.val = (fpclassify($1.val) == FP_ZERO && fpclassify($3.val) == FP_ZERO) ? 0 : 1; 235 } else if (is_const($1.val)) { 236 assert($1.ids == NULL); 237 if (fpclassify($1.val) == FP_ZERO) { 238 $$ = $3; 239 } else { 240 $$.val = 1; 241 $$.ids = NULL; 242 ids__free($3.ids); 243 } 244 } else if (is_const($3.val)) { 245 assert($3.ids == NULL); 246 if (fpclassify($3.val) == FP_ZERO) { 247 $$ = $1; 248 } else { 249 $$.val = 1; 250 $$.ids = NULL; 251 ids__free($1.ids); 252 } 253 } else { 254 $$ = union_expr($1, $3); 255 } 256 } 257 | expr '&' expr 258 { 259 if (is_const($1.val) && is_const($3.val)) { 260 assert($1.ids == NULL); 261 assert($3.ids == NULL); 262 $$.val = (fpclassify($1.val) != FP_ZERO && fpclassify($3.val) != FP_ZERO) ? 1 : 0; 263 $$.ids = NULL; 264 } else if (is_const($1.val)) { 265 assert($1.ids == NULL); 266 if (fpclassify($1.val) != FP_ZERO) { 267 $$ = $3; 268 } else { 269 $$.val = 0; 270 $$.ids = NULL; 271 ids__free($3.ids); 272 } 273 } else if (is_const($3.val)) { 274 assert($3.ids == NULL); 275 if (fpclassify($3.val) != FP_ZERO) { 276 $$ = $1; 277 } else { 278 $$.val = 0; 279 $$.ids = NULL; 280 ids__free($1.ids); 281 } 282 } else { 283 $$ = union_expr($1, $3); 284 } 285 } 286 | expr '^' expr 287 { 288 if (is_const($1.val) && is_const($3.val)) { 289 assert($1.ids == NULL); 290 assert($3.ids == NULL); 291 $$.val = (fpclassify($1.val) == FP_ZERO) != (fpclassify($3.val) == FP_ZERO) ? 1 : 0; 292 $$.ids = NULL; 293 } else { 294 $$ = union_expr($1, $3); 295 } 296 } 297 | expr '<' expr { BINARY_OP($$, <, $1, $3); } 298 | expr '>' expr { BINARY_OP($$, >, $1, $3); } 299 | expr '+' expr { BINARY_OP($$, +, $1, $3); } 300 | expr '-' expr { BINARY_OP($$, -, $1, $3); } 301 | expr '*' expr { BINARY_OP($$, *, $1, $3); } 302 | expr '/' expr 303 { 304 if (fpclassify($3.val) == FP_ZERO) { 305 pr_debug("division by zero\n"); 306 assert($3.ids == NULL); 307 if (compute_ids) 308 ids__free($1.ids); 309 $$.val = NAN; 310 $$.ids = NULL; 311 } else if (!compute_ids || (is_const($1.val) && is_const($3.val))) { 312 assert($1.ids == NULL); 313 assert($3.ids == NULL); 314 $$.val = $1.val / $3.val; 315 $$.ids = NULL; 316 } else { 317 /* LHS and/or RHS need computing from event IDs so union. */ 318 $$ = union_expr($1, $3); 319 } 320 } 321 | expr '%' expr 322 { 323 if (fpclassify($3.val) == FP_ZERO) { 324 pr_debug("division by zero\n"); 325 YYABORT; 326 } else if (!compute_ids || (is_const($1.val) && is_const($3.val))) { 327 assert($1.ids == NULL); 328 assert($3.ids == NULL); 329 $$.val = (long)$1.val % (long)$3.val; 330 $$.ids = NULL; 331 } else { 332 /* LHS and/or RHS need computing from event IDs so union. */ 333 $$ = union_expr($1, $3); 334 } 335 } 336 | D_RATIO '(' expr ',' expr ')' 337 { 338 if (fpclassify($5.val) == FP_ZERO) { 339 /* 340 * Division by constant zero always yields zero and no events 341 * are necessary. 342 */ 343 assert($5.ids == NULL); 344 $$.val = 0.0; 345 $$.ids = NULL; 346 ids__free($3.ids); 347 } else if (!compute_ids || (is_const($3.val) && is_const($5.val))) { 348 assert($3.ids == NULL); 349 assert($5.ids == NULL); 350 $$.val = $3.val / $5.val; 351 $$.ids = NULL; 352 } else { 353 /* LHS and/or RHS need computing from event IDs so union. */ 354 $$ = union_expr($3, $5); 355 } 356 } 357 | '-' expr %prec NEG 358 { 359 $$.val = -$2.val; 360 $$.ids = $2.ids; 361 } 362 | '(' if_expr ')' 363 { 364 $$ = $2; 365 } 366 | MIN '(' expr ',' expr ')' 367 { 368 if (!compute_ids) { 369 $$.val = $3.val < $5.val ? $3.val : $5.val; 370 $$.ids = NULL; 371 } else { 372 $$ = union_expr($3, $5); 373 } 374 } 375 | MAX '(' expr ',' expr ')' 376 { 377 if (!compute_ids) { 378 $$.val = $3.val > $5.val ? $3.val : $5.val; 379 $$.ids = NULL; 380 } else { 381 $$ = union_expr($3, $5); 382 } 383 } 384 | LITERAL 385 { 386 $$.val = $1; 387 $$.ids = NULL; 388 } 389 ; 390 391 %% 392