src/lib/lttng-ctl/filter/filter-visitor-generate-ir.c

   1 /*
   2  * filter-visitor-generate-ir.c
   3  *
   4  * LTTng filter generate intermediate representation
   5  *
   6  * Copyright 2012 - Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
   7  *
   8  * This library is free software; you can redistribute it and/or modify it
   9  * under the terms of the GNU Lesser General Public License, version 2.1 only,
  10  * as published by the Free Software Foundation.
  11  *
  12  * This library is distributed in the hope that it will be useful,
  13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  15  * Lesser General Public License for more details.
  16  *
  17  * You should have received a copy of the GNU Lesser General Public License
  18  * along with this library; if not, write to the Free Software Foundation,
  19  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
  20  */
  21
  22 #include <stdio.h>
  23 #include <unistd.h>
  24 #include <string.h>
  25 #include <stdlib.h>
  26 #include <assert.h>
  27 #include <errno.h>
  28 #include <inttypes.h>
  29 #include "filter-ast.h"
  30 #include "filter-parser.h"
  31 #include "filter-ir.h"
  32
  33 #include <common/macros.h>
  34
  35 static
  36 struct ir_op *generate_ir_recursive(struct filter_parser_ctx *ctx,
  37                 struct filter_node *node, enum ir_side side);
  38
  39 static
  40 struct ir_op *make_op_root(struct ir_op *child, enum ir_side side)
  41 {
  42         struct ir_op *op;
  43
  44         op = calloc(sizeof(struct ir_op), 1);
  45         if (!op)
  46                 return NULL;
  47         switch (child->data_type) {
  48         case IR_DATA_UNKNOWN:
  49         default:
  50                 fprintf(stderr, "[error] Unknown root child data type\n");
  51                 free(op);
  52                 return NULL;
  53         case IR_DATA_STRING:
  54                 fprintf(stderr, "[error] String cannot be root data type\n");
  55                 free(op);
  56                 return NULL;
  57         case IR_DATA_NUMERIC:
  58         case IR_DATA_FIELD_REF:
  59         case IR_DATA_GET_CONTEXT_REF:
  60                 /* ok */
  61                 break;
  62         }
  63         op->op = IR_OP_ROOT;
  64         op->side = side;
  65         op->data_type = child->data_type;
  66         op->signedness = child->signedness;
  67         op->u.root.child = child;
  68         return op;
  69 }
  70
  71 static
  72 struct ir_op *make_op_load_string(char *string, enum ir_side side)
  73 {
  74         struct ir_op *op;
  75
  76         op = calloc(sizeof(struct ir_op), 1);
  77         if (!op)
  78                 return NULL;
  79         op->op = IR_OP_LOAD;
  80         op->data_type = IR_DATA_STRING;
  81         op->signedness = IR_SIGN_UNKNOWN;
  82         op->side = side;
  83         op->u.load.u.string = strdup(string);
  84         if (!op->u.load.u.string) {
  85                 free(op);
  86                 return NULL;
  87         }
  88         return op;
  89 }
  90
  91 static
  92 struct ir_op *make_op_load_numeric(int64_t v, enum ir_side side)
  93 {
  94         struct ir_op *op;
  95
  96         op = calloc(sizeof(struct ir_op), 1);
  97         if (!op)
  98                 return NULL;
  99         op->op = IR_OP_LOAD;
 100         op->data_type = IR_DATA_NUMERIC;
 101         /* TODO: for now, all numeric values are signed */
 102         op->signedness = IR_SIGNED;
 103         op->side = side;
 104         op->u.load.u.num = v;
 105         return op;
 106 }
 107
 108 static
 109 struct ir_op *make_op_load_float(double v, enum ir_side side)
 110 {
 111         struct ir_op *op;
 112
 113         op = calloc(sizeof(struct ir_op), 1);
 114         if (!op)
 115                 return NULL;
 116         op->op = IR_OP_LOAD;
 117         op->data_type = IR_DATA_FLOAT;
 118         op->signedness = IR_SIGN_UNKNOWN;
 119         op->side = side;
 120         op->u.load.u.flt = v;
 121         return op;
 122 }
 123
 124 static
 125 struct ir_op *make_op_load_field_ref(char *string, enum ir_side side)
 126 {
 127         struct ir_op *op;
 128
 129         op = calloc(sizeof(struct ir_op), 1);
 130         if (!op)
 131                 return NULL;
 132         op->op = IR_OP_LOAD;
 133         op->data_type = IR_DATA_FIELD_REF;
 134         op->signedness = IR_SIGN_DYN;
 135         op->side = side;
 136         op->u.load.u.ref = strdup(string);
 137         if (!op->u.load.u.ref) {
 138                 free(op);
 139                 return NULL;
 140         }
 141         return op;
 142 }
 143
 144 static
 145 struct ir_op *make_op_load_get_context_ref(char *string, enum ir_side side)
 146 {
 147         struct ir_op *op;
 148
 149         op = calloc(sizeof(struct ir_op), 1);
 150         if (!op)
 151                 return NULL;
 152         op->op = IR_OP_LOAD;
 153         op->data_type = IR_DATA_GET_CONTEXT_REF;
 154         op->signedness = IR_SIGN_DYN;
 155         op->side = side;
 156         op->u.load.u.ref = strdup(string);
 157         if (!op->u.load.u.ref) {
 158                 free(op);
 159                 return NULL;
 160         }
 161         return op;
 162 }
 163
 164 static
 165 struct ir_op *make_op_unary(enum unary_op_type unary_op_type,
 166                         const char *op_str, enum ir_op_signedness signedness,
 167                         struct ir_op *child, enum ir_side side)
 168 {
 169         struct ir_op *op = NULL;
 170
 171         if (child->data_type == IR_DATA_STRING) {
 172                 fprintf(stderr, "[error] unary operation '%s' not allowed on string literal\n", op_str);
 173                 goto error;
 174         }
 175
 176         op = calloc(sizeof(struct ir_op), 1);
 177         if (!op)
 178                 return NULL;
 179         op->op = IR_OP_UNARY;
 180         op->data_type = child->data_type;
 181         op->signedness = signedness;
 182         op->side = side;
 183         op->u.unary.type = unary_op_type;
 184         op->u.unary.child = child;
 185         return op;
 186
 187 error:
 188         free(op);
 189         return NULL;
 190 }
 191
 192 /*
 193  * unary + is pretty much useless.
 194  */
 195 static
 196 struct ir_op *make_op_unary_plus(struct ir_op *child, enum ir_side side)
 197 {
 198         return make_op_unary(AST_UNARY_PLUS, "+", child->signedness,
 199                         child, side);
 200 }
 201
 202 static
 203 struct ir_op *make_op_unary_minus(struct ir_op *child, enum ir_side side)
 204 {
 205         return make_op_unary(AST_UNARY_MINUS, "-", child->signedness,
 206                         child, side);
 207 }
 208
 209 static
 210 struct ir_op *make_op_unary_not(struct ir_op *child, enum ir_side side)
 211 {
 212         return make_op_unary(AST_UNARY_NOT, "!", child->signedness,
 213                         child, side);
 214 }
 215
 216 static
 217 struct ir_op *make_op_binary_compare(enum op_type bin_op_type,
 218                 const char *op_str, struct ir_op *left, struct ir_op *right,
 219                 enum ir_side side)
 220 {
 221         struct ir_op *op = NULL;
 222
 223         if (left->data_type == IR_DATA_UNKNOWN
 224                 || right->data_type == IR_DATA_UNKNOWN) {
 225                 fprintf(stderr, "[error] binary operation '%s' has unknown operand type\n", op_str);
 226                 goto error;
 227
 228         }
 229         if ((left->data_type == IR_DATA_STRING
 230                 && (right->data_type == IR_DATA_NUMERIC || right->data_type == IR_DATA_FLOAT))
 231                 || ((left->data_type == IR_DATA_NUMERIC || left->data_type == IR_DATA_FLOAT) &&
 232                         right->data_type == IR_DATA_STRING)) {
 233                 fprintf(stderr, "[error] binary operation '%s' operand type mismatch\n", op_str);
 234                 goto error;
 235         }
 236
 237         op = calloc(sizeof(struct ir_op), 1);
 238         if (!op)
 239                 return NULL;
 240         op->op = IR_OP_BINARY;
 241         op->u.binary.type = bin_op_type;
 242         op->u.binary.left = left;
 243         op->u.binary.right = right;
 244
 245         /* we return a boolean, represented as signed numeric */
 246         op->data_type = IR_DATA_NUMERIC;
 247         op->signedness = IR_SIGNED;
 248         op->side = side;
 249
 250         return op;
 251
 252 error:
 253         free(op);
 254         return NULL;
 255 }
 256
 257 static
 258 struct ir_op *make_op_binary_eq(struct ir_op *left, struct ir_op *right,
 259                 enum ir_side side)
 260 {
 261         return make_op_binary_compare(AST_OP_EQ, "==", left, right, side);
 262 }
 263
 264 static
 265 struct ir_op *make_op_binary_ne(struct ir_op *left, struct ir_op *right,
 266                 enum ir_side side)
 267 {
 268         return make_op_binary_compare(AST_OP_NE, "!=", left, right, side);
 269 }
 270
 271 static
 272 struct ir_op *make_op_binary_gt(struct ir_op *left, struct ir_op *right,
 273                 enum ir_side side)
 274 {
 275         return make_op_binary_compare(AST_OP_GT, ">", left, right, side);
 276 }
 277
 278 static
 279 struct ir_op *make_op_binary_lt(struct ir_op *left, struct ir_op *right,
 280                 enum ir_side side)
 281 {
 282         return make_op_binary_compare(AST_OP_LT, "<", left, right, side);
 283 }
 284
 285 static
 286 struct ir_op *make_op_binary_ge(struct ir_op *left, struct ir_op *right,
 287                 enum ir_side side)
 288 {
 289         return make_op_binary_compare(AST_OP_GE, ">=", left, right, side);
 290 }
 291
 292 static
 293 struct ir_op *make_op_binary_le(struct ir_op *left, struct ir_op *right,
 294                 enum ir_side side)
 295 {
 296         return make_op_binary_compare(AST_OP_LE, "<=", left, right, side);
 297 }
 298
 299 static
 300 struct ir_op *make_op_binary_logical(enum op_type bin_op_type,
 301                 const char *op_str, struct ir_op *left, struct ir_op *right,
 302                 enum ir_side side)
 303 {
 304         struct ir_op *op = NULL;
 305
 306         if (left->data_type == IR_DATA_UNKNOWN
 307                 || right->data_type == IR_DATA_UNKNOWN) {
 308                 fprintf(stderr, "[error] binary operation '%s' has unknown operand type\n", op_str);
 309                 goto error;
 310
 311         }
 312         if (left->data_type == IR_DATA_STRING
 313                 || right->data_type == IR_DATA_STRING) {
 314                 fprintf(stderr, "[error] logical binary operation '%s' cannot have string operand\n", op_str);
 315                 goto error;
 316         }
 317
 318         op = calloc(sizeof(struct ir_op), 1);
 319         if (!op)
 320                 return NULL;
 321         op->op = IR_OP_LOGICAL;
 322         op->u.binary.type = bin_op_type;
 323         op->u.binary.left = left;
 324         op->u.binary.right = right;
 325
 326         /* we return a boolean, represented as signed numeric */
 327         op->data_type = IR_DATA_NUMERIC;
 328         op->signedness = IR_SIGNED;
 329         op->side = side;
 330
 331         return op;
 332
 333 error:
 334         free(op);
 335         return NULL;
 336 }
 337
 338 static
 339 struct ir_op *make_op_binary_logical_and(struct ir_op *left, struct ir_op *right,
 340                 enum ir_side side)
 341 {
 342         return make_op_binary_logical(AST_OP_AND, "&&", left, right, side);
 343 }
 344
 345 static
 346 struct ir_op *make_op_binary_logical_or(struct ir_op *left, struct ir_op *right,
 347                 enum ir_side side)
 348 {
 349         return make_op_binary_logical(AST_OP_OR, "||", left, right, side);
 350 }
 351
 352 static
 353 void filter_free_ir_recursive(struct ir_op *op)
 354 {
 355         if (!op)
 356                 return;
 357         switch (op->op) {
 358         case IR_OP_UNKNOWN:
 359         default:
 360                 fprintf(stderr, "[error] Unknown op type in %s\n",
 361                         __func__);
 362                 break;
 363         case IR_OP_ROOT:
 364                 filter_free_ir_recursive(op->u.root.child);
 365                 break;
 366         case IR_OP_LOAD:
 367                 switch (op->data_type) {
 368                 case IR_DATA_STRING:
 369                         free(op->u.load.u.string);
 370                         break;
 371                 case IR_DATA_FIELD_REF:         /* fall-through */
 372                 case IR_DATA_GET_CONTEXT_REF:
 373                         free(op->u.load.u.ref);
 374                         break;
 375                 default:
 376                         break;
 377                 }
 378                 break;
 379         case IR_OP_UNARY:
 380                 filter_free_ir_recursive(op->u.unary.child);
 381                 break;
 382         case IR_OP_BINARY:
 383                 filter_free_ir_recursive(op->u.binary.left);
 384                 filter_free_ir_recursive(op->u.binary.right);
 385                 break;
 386         case IR_OP_LOGICAL:
 387                 filter_free_ir_recursive(op->u.logical.left);
 388                 filter_free_ir_recursive(op->u.logical.right);
 389                 break;
 390         }
 391         free(op);
 392 }
 393
 394 static
 395 struct ir_op *make_expression(struct filter_parser_ctx *ctx,
 396                 struct filter_node *node, enum ir_side side)
 397 {
 398         switch (node->u.expression.type) {
 399         case AST_EXP_UNKNOWN:
 400         default:
 401                 fprintf(stderr, "[error] %s: unknown expression type\n", __func__);
 402                 return NULL;
 403
 404         case AST_EXP_STRING:
 405                 return make_op_load_string(node->u.expression.u.string, side);
 406         case AST_EXP_CONSTANT:
 407                 return make_op_load_numeric(node->u.expression.u.constant,
 408                                         side);
 409         case AST_EXP_FLOAT_CONSTANT:
 410                 return make_op_load_float(node->u.expression.u.float_constant,
 411                                         side);
 412         case AST_EXP_IDENTIFIER:
 413                 if (node->u.expression.pre_op != AST_LINK_UNKNOWN) {
 414                         fprintf(stderr, "[error] %s: dotted and dereferenced identifiers not supported\n", __func__);
 415                         return NULL;
 416                 }
 417                 return make_op_load_field_ref(node->u.expression.u.identifier,
 418                                         side);
 419         case AST_EXP_GLOBAL_IDENTIFIER:
 420         {
 421                 const char *name;
 422
 423                 /*
 424                  * We currently only support $ctx (context) and $app
 425                  * identifiers.
 426                  */
 427                 if (strncmp(node->u.expression.u.identifier,
 428                                 "$ctx.", strlen("$ctx.")) != 0
 429                         && strncmp(node->u.expression.u.identifier,
 430                                 "$app.", strlen("$app.")) != 0) {
 431                         fprintf(stderr, "[error] %s: \"%s\" global identifier is unknown. Only \"$ctx\" and \"$app\" are currently implemented.\n", __func__, node->u.expression.u.identifier);
 432                         return NULL;
 433                 }
 434                 name = strchr(node->u.expression.u.identifier, '.');
 435                 if (!name) {
 436                         fprintf(stderr, "[error] %s: Expecting '.'\n", __func__);
 437                         return NULL;
 438                 }
 439                 name++; /* Skip . */
 440                 if (!strlen(name)) {
 441                         fprintf(stderr, "[error] %s: Expecting a context name, e.g. \'$ctx.name\'.\n", __func__);
 442                         return NULL;
 443                 }
 444                 return make_op_load_get_context_ref(node->u.expression.u.identifier,
 445                                         side);
 446         }
 447         case AST_EXP_NESTED:
 448                 return generate_ir_recursive(ctx, node->u.expression.u.child,
 449                                         side);
 450         }
 451 }
 452
 453 static
 454 struct ir_op *make_op(struct filter_parser_ctx *ctx,
 455                 struct filter_node *node, enum ir_side side)
 456 {
 457         struct ir_op *op = NULL, *lchild, *rchild;
 458         const char *op_str = "?";
 459
 460         switch (node->u.op.type) {
 461         case AST_OP_UNKNOWN:
 462         default:
 463                 fprintf(stderr, "[error] %s: unknown binary op type\n", __func__);
 464                 return NULL;
 465
 466         /*
 467          * Binary operators other than comparators and logical and/or
 468          * are not supported. If we ever want to support those, we will
 469          * need a stack for the general case rather than just 2
 470          * registers (see bytecode).
 471          */
 472         case AST_OP_MUL:
 473                 op_str = "*";
 474                 goto error_not_supported;
 475         case AST_OP_DIV:
 476                 op_str = "/";
 477                 goto error_not_supported;
 478         case AST_OP_MOD:
 479                 op_str = "%";
 480                 goto error_not_supported;
 481         case AST_OP_PLUS:
 482                 op_str = "+";
 483                 goto error_not_supported;
 484         case AST_OP_MINUS:
 485                 op_str = "-";
 486                 goto error_not_supported;
 487         case AST_OP_RSHIFT:
 488                 op_str = ">>";
 489                 goto error_not_supported;
 490         case AST_OP_LSHIFT:
 491                 op_str = "<<";
 492                 goto error_not_supported;
 493         case AST_OP_BIN_AND:
 494                 op_str = "&";
 495                 goto error_not_supported;
 496         case AST_OP_BIN_OR:
 497                 op_str = "|";
 498                 goto error_not_supported;
 499         case AST_OP_BIN_XOR:
 500                 op_str = "^";
 501                 goto error_not_supported;
 502
 503         case AST_OP_EQ:
 504         case AST_OP_NE:
 505         case AST_OP_GT:
 506         case AST_OP_LT:
 507         case AST_OP_GE:
 508         case AST_OP_LE:
 509                 lchild = generate_ir_recursive(ctx, node->u.op.lchild, IR_LEFT);
 510                 if (!lchild)
 511                         return NULL;
 512                 rchild = generate_ir_recursive(ctx, node->u.op.rchild, IR_RIGHT);
 513                 if (!rchild) {
 514                         filter_free_ir_recursive(lchild);
 515                         return NULL;
 516                 }
 517                 break;
 518
 519         case AST_OP_AND:
 520         case AST_OP_OR:
 521                 /*
 522                  * Both children considered as left, since we need to
 523                  * populate R0.
 524                  */
 525                 lchild = generate_ir_recursive(ctx, node->u.op.lchild, IR_LEFT);
 526                 if (!lchild)
 527                         return NULL;
 528                 rchild = generate_ir_recursive(ctx, node->u.op.rchild, IR_LEFT);
 529                 if (!rchild) {
 530                         filter_free_ir_recursive(lchild);
 531                         return NULL;
 532                 }
 533                 break;
 534         }
 535
 536         switch (node->u.op.type) {
 537         case AST_OP_AND:
 538                 op = make_op_binary_logical_and(lchild, rchild, side);
 539                 break;
 540         case AST_OP_OR:
 541                 op = make_op_binary_logical_or(lchild, rchild, side);
 542                 break;
 543         case AST_OP_EQ:
 544                 op = make_op_binary_eq(lchild, rchild, side);
 545                 break;
 546         case AST_OP_NE:
 547                 op = make_op_binary_ne(lchild, rchild, side);
 548                 break;
 549         case AST_OP_GT:
 550                 op = make_op_binary_gt(lchild, rchild, side);
 551                 break;
 552         case AST_OP_LT:
 553                 op = make_op_binary_lt(lchild, rchild, side);
 554                 break;
 555         case AST_OP_GE:
 556                 op = make_op_binary_ge(lchild, rchild, side);
 557                 break;
 558         case AST_OP_LE:
 559                 op = make_op_binary_le(lchild, rchild, side);
 560                 break;
 561         default:
 562                 break;
 563         }
 564
 565         if (!op) {
 566                 filter_free_ir_recursive(rchild);
 567                 filter_free_ir_recursive(lchild);
 568         }
 569         return op;
 570
 571 error_not_supported:
 572         fprintf(stderr, "[error] %s: binary operation '%s' not supported\n",
 573                 __func__, op_str);
 574         return NULL;
 575 }
 576
 577 static
 578 struct ir_op *make_unary_op(struct filter_parser_ctx *ctx,
 579                 struct filter_node *node, enum ir_side side)
 580 {
 581         const char *op_str = "?";
 582
 583         switch (node->u.unary_op.type) {
 584         case AST_UNARY_UNKNOWN:
 585         default:
 586                 fprintf(stderr, "[error] %s: unknown unary op type\n", __func__);
 587                 return NULL;
 588
 589         case AST_UNARY_PLUS:
 590         {
 591                 struct ir_op *op, *child;
 592
 593                 child = generate_ir_recursive(ctx, node->u.unary_op.child,
 594                                         side);
 595                 if (!child)
 596                         return NULL;
 597                 op = make_op_unary_plus(child, side);
 598                 if (!op) {
 599                         filter_free_ir_recursive(child);
 600                         return NULL;
 601                 }
 602                 return op;
 603         }
 604         case AST_UNARY_MINUS:
 605         {
 606                 struct ir_op *op, *child;
 607
 608                 child = generate_ir_recursive(ctx, node->u.unary_op.child,
 609                                         side);
 610                 if (!child)
 611                         return NULL;
 612                 op = make_op_unary_minus(child, side);
 613                 if (!op) {
 614                         filter_free_ir_recursive(child);
 615                         return NULL;
 616                 }
 617                 return op;
 618         }
 619         case AST_UNARY_NOT:
 620         {
 621                 struct ir_op *op, *child;
 622
 623                 child = generate_ir_recursive(ctx, node->u.unary_op.child,
 624                                         side);
 625                 if (!child)
 626                         return NULL;
 627                 op = make_op_unary_not(child, side);
 628                 if (!op) {
 629                         filter_free_ir_recursive(child);
 630                         return NULL;
 631                 }
 632                 return op;
 633         }
 634         case AST_UNARY_BIN_NOT:
 635         {
 636                 op_str = "~";
 637                 goto error_not_supported;
 638         }
 639         }
 640
 641 error_not_supported:
 642         fprintf(stderr, "[error] %s: unary operation '%s' not supported\n",
 643                 __func__, op_str);
 644         return NULL;
 645 }
 646
 647 static
 648 struct ir_op *generate_ir_recursive(struct filter_parser_ctx *ctx,
 649                 struct filter_node *node, enum ir_side side)
 650 {
 651         switch (node->type) {
 652         case NODE_UNKNOWN:
 653         default:
 654                 fprintf(stderr, "[error] %s: unknown node type\n", __func__);
 655                 return NULL;
 656
 657         case NODE_ROOT:
 658         {
 659                 struct ir_op *op, *child;
 660
 661                 child = generate_ir_recursive(ctx, node->u.root.child,
 662                                         side);
 663                 if (!child)
 664                         return NULL;
 665                 op = make_op_root(child, side);
 666                 if (!op) {
 667                         filter_free_ir_recursive(child);
 668                         return NULL;
 669                 }
 670                 return op;
 671         }
 672         case NODE_EXPRESSION:
 673                 return make_expression(ctx, node, side);
 674         case NODE_OP:
 675                 return make_op(ctx, node, side);
 676         case NODE_UNARY_OP:
 677                 return make_unary_op(ctx, node, side);
 678         }
 679         return 0;
 680 }
 681
 682 LTTNG_HIDDEN
 683 void filter_ir_free(struct filter_parser_ctx *ctx)
 684 {
 685         filter_free_ir_recursive(ctx->ir_root);
 686         ctx->ir_root = NULL;
 687 }
 688
 689 LTTNG_HIDDEN
 690 int filter_visitor_ir_generate(struct filter_parser_ctx *ctx)
 691 {
 692         struct ir_op *op;
 693
 694         op = generate_ir_recursive(ctx, &ctx->ast->root, IR_LEFT);
 695         if (!op) {
 696                 return -EINVAL;
 697         }
 698         ctx->ir_root = op;
 699         return 0;
 700 }