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                 struct filter_node *next;
 422
 423                 if (node->u.expression.pre_op == AST_LINK_UNKNOWN) {
 424                         fprintf(stderr, "[error] %s: global identifiers need chained identifier \n", __func__);
 425                         return NULL;
 426                 }
 427                 /* We currently only support $ctx (context) identifiers */
 428                 if (strncmp(node->u.expression.u.identifier,
 429                                 "$ctx", strlen("$ctx")) != 0) {
 430                         fprintf(stderr, "[error] %s: \"%s\" global identifier is unknown. Only \"$ctx\" currently implemented.\n", __func__, node->u.expression.u.identifier);
 431                         return NULL;
 432                 }
 433                 next = node->u.expression.next;
 434                 if (!next) {
 435                         fprintf(stderr, "[error] %s: Expecting a context name, e.g. \'$ctx.name\'.\n", __func__);
 436                         return NULL;
 437                 }
 438                 if (next->type != NODE_EXPRESSION) {
 439                         fprintf(stderr, "[error] %s: Expecting expression.\n", __func__);
 440                         return NULL;
 441                 }
 442                 if (next->u.expression.type != AST_EXP_IDENTIFIER) {
 443                         fprintf(stderr, "[error] %s: Expecting identifier.\n", __func__);
 444                         return NULL;
 445                 }
 446                 if (next->u.expression.pre_op != AST_LINK_UNKNOWN) {
 447                         fprintf(stderr, "[error] %s: dotted and dereferenced identifiers not supported after identifier\n", __func__);
 448                         return NULL;
 449                 }
 450                 return make_op_load_get_context_ref(next->u.expression.u.identifier,
 451                                         side);
 452         }
 453         case AST_EXP_NESTED:
 454                 return generate_ir_recursive(ctx, node->u.expression.u.child,
 455                                         side);
 456         }
 457 }
 458
 459 static
 460 struct ir_op *make_op(struct filter_parser_ctx *ctx,
 461                 struct filter_node *node, enum ir_side side)
 462 {
 463         struct ir_op *op = NULL, *lchild, *rchild;
 464         const char *op_str = "?";
 465
 466         switch (node->u.op.type) {
 467         case AST_OP_UNKNOWN:
 468         default:
 469                 fprintf(stderr, "[error] %s: unknown binary op type\n", __func__);
 470                 return NULL;
 471
 472         /*
 473          * Binary operators other than comparators and logical and/or
 474          * are not supported. If we ever want to support those, we will
 475          * need a stack for the general case rather than just 2
 476          * registers (see bytecode).
 477          */
 478         case AST_OP_MUL:
 479                 op_str = "*";
 480                 goto error_not_supported;
 481         case AST_OP_DIV:
 482                 op_str = "/";
 483                 goto error_not_supported;
 484         case AST_OP_MOD:
 485                 op_str = "%";
 486                 goto error_not_supported;
 487         case AST_OP_PLUS:
 488                 op_str = "+";
 489                 goto error_not_supported;
 490         case AST_OP_MINUS:
 491                 op_str = "-";
 492                 goto error_not_supported;
 493         case AST_OP_RSHIFT:
 494                 op_str = ">>";
 495                 goto error_not_supported;
 496         case AST_OP_LSHIFT:
 497                 op_str = "<<";
 498                 goto error_not_supported;
 499         case AST_OP_BIN_AND:
 500                 op_str = "&";
 501                 goto error_not_supported;
 502         case AST_OP_BIN_OR:
 503                 op_str = "|";
 504                 goto error_not_supported;
 505         case AST_OP_BIN_XOR:
 506                 op_str = "^";
 507                 goto error_not_supported;
 508
 509         case AST_OP_EQ:
 510         case AST_OP_NE:
 511         case AST_OP_GT:
 512         case AST_OP_LT:
 513         case AST_OP_GE:
 514         case AST_OP_LE:
 515                 lchild = generate_ir_recursive(ctx, node->u.op.lchild, IR_LEFT);
 516                 if (!lchild)
 517                         return NULL;
 518                 rchild = generate_ir_recursive(ctx, node->u.op.rchild, IR_RIGHT);
 519                 if (!rchild) {
 520                         filter_free_ir_recursive(lchild);
 521                         return NULL;
 522                 }
 523                 break;
 524
 525         case AST_OP_AND:
 526         case AST_OP_OR:
 527                 /*
 528                  * Both children considered as left, since we need to
 529                  * populate R0.
 530                  */
 531                 lchild = generate_ir_recursive(ctx, node->u.op.lchild, IR_LEFT);
 532                 if (!lchild)
 533                         return NULL;
 534                 rchild = generate_ir_recursive(ctx, node->u.op.rchild, IR_LEFT);
 535                 if (!rchild) {
 536                         filter_free_ir_recursive(lchild);
 537                         return NULL;
 538                 }
 539                 break;
 540         }
 541
 542         switch (node->u.op.type) {
 543         case AST_OP_AND:
 544                 op = make_op_binary_logical_and(lchild, rchild, side);
 545                 break;
 546         case AST_OP_OR:
 547                 op = make_op_binary_logical_or(lchild, rchild, side);
 548                 break;
 549         case AST_OP_EQ:
 550                 op = make_op_binary_eq(lchild, rchild, side);
 551                 break;
 552         case AST_OP_NE:
 553                 op = make_op_binary_ne(lchild, rchild, side);
 554                 break;
 555         case AST_OP_GT:
 556                 op = make_op_binary_gt(lchild, rchild, side);
 557                 break;
 558         case AST_OP_LT:
 559                 op = make_op_binary_lt(lchild, rchild, side);
 560                 break;
 561         case AST_OP_GE:
 562                 op = make_op_binary_ge(lchild, rchild, side);
 563                 break;
 564         case AST_OP_LE:
 565                 op = make_op_binary_le(lchild, rchild, side);
 566                 break;
 567         default:
 568                 break;
 569         }
 570
 571         if (!op) {
 572                 filter_free_ir_recursive(rchild);
 573                 filter_free_ir_recursive(lchild);
 574         }
 575         return op;
 576
 577 error_not_supported:
 578         fprintf(stderr, "[error] %s: binary operation '%s' not supported\n",
 579                 __func__, op_str);
 580         return NULL;
 581 }
 582
 583 static
 584 struct ir_op *make_unary_op(struct filter_parser_ctx *ctx,
 585                 struct filter_node *node, enum ir_side side)
 586 {
 587         const char *op_str = "?";
 588
 589         switch (node->u.unary_op.type) {
 590         case AST_UNARY_UNKNOWN:
 591         default:
 592                 fprintf(stderr, "[error] %s: unknown unary op type\n", __func__);
 593                 return NULL;
 594
 595         case AST_UNARY_PLUS:
 596         {
 597                 struct ir_op *op, *child;
 598
 599                 child = generate_ir_recursive(ctx, node->u.unary_op.child,
 600                                         side);
 601                 if (!child)
 602                         return NULL;
 603                 op = make_op_unary_plus(child, side);
 604                 if (!op) {
 605                         filter_free_ir_recursive(child);
 606                         return NULL;
 607                 }
 608                 return op;
 609         }
 610         case AST_UNARY_MINUS:
 611         {
 612                 struct ir_op *op, *child;
 613
 614                 child = generate_ir_recursive(ctx, node->u.unary_op.child,
 615                                         side);
 616                 if (!child)
 617                         return NULL;
 618                 op = make_op_unary_minus(child, side);
 619                 if (!op) {
 620                         filter_free_ir_recursive(child);
 621                         return NULL;
 622                 }
 623                 return op;
 624         }
 625         case AST_UNARY_NOT:
 626         {
 627                 struct ir_op *op, *child;
 628
 629                 child = generate_ir_recursive(ctx, node->u.unary_op.child,
 630                                         side);
 631                 if (!child)
 632                         return NULL;
 633                 op = make_op_unary_not(child, side);
 634                 if (!op) {
 635                         filter_free_ir_recursive(child);
 636                         return NULL;
 637                 }
 638                 return op;
 639         }
 640         case AST_UNARY_BIN_NOT:
 641         {
 642                 op_str = "~";
 643                 goto error_not_supported;
 644         }
 645         }
 646
 647 error_not_supported:
 648         fprintf(stderr, "[error] %s: unary operation '%s' not supported\n",
 649                 __func__, op_str);
 650         return NULL;
 651 }
 652
 653 static
 654 struct ir_op *generate_ir_recursive(struct filter_parser_ctx *ctx,
 655                 struct filter_node *node, enum ir_side side)
 656 {
 657         switch (node->type) {
 658         case NODE_UNKNOWN:
 659         default:
 660                 fprintf(stderr, "[error] %s: unknown node type\n", __func__);
 661                 return NULL;
 662
 663         case NODE_ROOT:
 664         {
 665                 struct ir_op *op, *child;
 666
 667                 child = generate_ir_recursive(ctx, node->u.root.child,
 668                                         side);
 669                 if (!child)
 670                         return NULL;
 671                 op = make_op_root(child, side);
 672                 if (!op) {
 673                         filter_free_ir_recursive(child);
 674                         return NULL;
 675                 }
 676                 return op;
 677         }
 678         case NODE_EXPRESSION:
 679                 return make_expression(ctx, node, side);
 680         case NODE_OP:
 681                 return make_op(ctx, node, side);
 682         case NODE_UNARY_OP:
 683                 return make_unary_op(ctx, node, side);
 684         }
 685         return 0;
 686 }
 687
 688 LTTNG_HIDDEN
 689 void filter_ir_free(struct filter_parser_ctx *ctx)
 690 {
 691         filter_free_ir_recursive(ctx->ir_root);
 692         ctx->ir_root = NULL;
 693 }
 694
 695 LTTNG_HIDDEN
 696 int filter_visitor_ir_generate(struct filter_parser_ctx *ctx)
 697 {
 698         struct ir_op *op;
 699
 700         op = generate_ir_recursive(ctx, &ctx->ast->root, IR_LEFT);
 701         if (!op) {
 702                 return -EINVAL;
 703         }
 704         ctx->ir_root = op;
 705         return 0;
 706 }