src/common/filter/filter-visitor-generate-bytecode.cpp

   1 /*
   2  * filter-visitor-generate-bytecode.c
   3  *
   4  * LTTng filter bytecode generation
   5  *
   6  * Copyright 2012 Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
   7  *
   8  * SPDX-License-Identifier: LGPL-2.1-only
   9  *
  10  */
  11
  12 #include <stdlib.h>
  13 #include <string.h>
  14 #include <common/align.hpp>
  15 #include <common/compat/errno.hpp>
  16 #include <common/compat/string.hpp>
  17
  18 #include "common/align.hpp"
  19 #include "common/bytecode/bytecode.hpp"
  20 #include "common/compat/string.hpp"
  21 #include "common/macros.hpp"
  22 #include "common/string-utils/string-utils.hpp"
  23 #include "filter-ast.hpp"
  24 #include "filter-ir.hpp"
  25
  26 static
  27 int recursive_visit_gen_bytecode(struct filter_parser_ctx *ctx,
  28                 struct ir_op *node);
  29
  30 static
  31 int bytecode_patch(struct lttng_bytecode_alloc **fb,
  32                 const void *data,
  33                 uint16_t offset,
  34                 uint32_t len)
  35 {
  36         if (offset >= (*fb)->b.len) {
  37                 return -EINVAL;
  38         }
  39         memcpy(&(*fb)->b.data[offset], data, len);
  40         return 0;
  41 }
  42
  43 static
  44 int visit_node_root(struct filter_parser_ctx *ctx, struct ir_op *node)
  45 {
  46         int ret;
  47         struct return_op insn;
  48
  49         /* Visit child */
  50         ret = recursive_visit_gen_bytecode(ctx, node->u.root.child);
  51         if (ret)
  52                 return ret;
  53
  54         /* Generate end of bytecode instruction */
  55         insn.op = BYTECODE_OP_RETURN;
  56         return bytecode_push(&ctx->bytecode, &insn, 1, sizeof(insn));
  57 }
  58
  59 /*
  60  * 1: match
  61  * 0: no match
  62  * < 0: error
  63  */
  64 static
  65 int load_expression_legacy_match(const struct ir_load_expression *exp,
  66                 enum bytecode_op *op_type,
  67                 char **symbol)
  68 {
  69         const struct ir_load_expression_op *op;
  70         bool need_dot = false;
  71
  72         op = exp->child;
  73         switch (op->type) {
  74         case IR_LOAD_EXPRESSION_GET_CONTEXT_ROOT:
  75                 *op_type = BYTECODE_OP_GET_CONTEXT_REF;
  76                 if (strutils_append_str(symbol, "$ctx.")) {
  77                         return -ENOMEM;
  78                 }
  79                 need_dot = false;
  80                 break;
  81         case IR_LOAD_EXPRESSION_GET_APP_CONTEXT_ROOT:
  82                 *op_type = BYTECODE_OP_GET_CONTEXT_REF;
  83                 if (strutils_append_str(symbol, "$app.")) {
  84                         return -ENOMEM;
  85                 }
  86                 need_dot = false;
  87                 break;
  88         case IR_LOAD_EXPRESSION_GET_PAYLOAD_ROOT:
  89                 *op_type = BYTECODE_OP_LOAD_FIELD_REF;
  90                 need_dot = false;
  91                 break;
  92
  93         case IR_LOAD_EXPRESSION_GET_SYMBOL:
  94         case IR_LOAD_EXPRESSION_GET_INDEX:
  95         case IR_LOAD_EXPRESSION_LOAD_FIELD:
  96         default:
  97                 return 0;       /* no match */
  98         }
  99
 100         for (;;) {
 101                 op = op->next;
 102                 if (!op) {
 103                         return 0;       /* no match */
 104                 }
 105                 switch (op->type) {
 106                 case IR_LOAD_EXPRESSION_LOAD_FIELD:
 107                         goto end;
 108                 case IR_LOAD_EXPRESSION_GET_SYMBOL:
 109                         if (need_dot && strutils_append_str(symbol, ".")) {
 110                                 return -ENOMEM;
 111                         }
 112                         if (strutils_append_str(symbol, op->u.symbol)) {
 113                                 return -ENOMEM;
 114                         }
 115                         break;
 116                 default:
 117                         return 0;        /* no match */
 118                 }
 119                 need_dot = true;
 120         }
 121 end:
 122         return 1;       /* Legacy match */
 123 }
 124
 125 /*
 126  * 1: legacy match
 127  * 0: no legacy match
 128  * < 0: error
 129  */
 130 static
 131 int visit_node_load_expression_legacy(struct filter_parser_ctx *ctx,
 132                 const struct ir_load_expression *exp,
 133                 const struct ir_load_expression_op *op)
 134 {
 135         struct load_op *insn = NULL;
 136         uint32_t insn_len = sizeof(struct load_op)
 137                 + sizeof(struct field_ref);
 138         struct field_ref ref_offset;
 139         uint32_t reloc_offset_u32;
 140         uint16_t reloc_offset;
 141         enum bytecode_op op_type;
 142         char *symbol = NULL;
 143         int ret;
 144
 145         ret = load_expression_legacy_match(exp, &op_type, &symbol);
 146         if (ret <= 0) {
 147                 goto end;
 148         }
 149         insn = (load_op *) calloc(insn_len, 1);
 150         if (!insn) {
 151                 ret = -ENOMEM;
 152                 goto end;
 153         }
 154         insn->op = op_type;
 155         ref_offset.offset = (uint16_t) -1U;
 156         memcpy(insn->data, &ref_offset, sizeof(ref_offset));
 157         /* reloc_offset points to struct load_op */
 158         reloc_offset_u32 = bytecode_get_len(&ctx->bytecode->b);
 159         if (reloc_offset_u32 > LTTNG_FILTER_MAX_LEN - 1) {
 160                 ret = -EINVAL;
 161                 goto end;
 162         }
 163         reloc_offset = (uint16_t) reloc_offset_u32;
 164         ret = bytecode_push(&ctx->bytecode, insn, 1, insn_len);
 165         if (ret) {
 166                 goto end;
 167         }
 168         /* append reloc */
 169         ret = bytecode_push(&ctx->bytecode_reloc, &reloc_offset,
 170                                 1, sizeof(reloc_offset));
 171         if (ret) {
 172                 goto end;
 173         }
 174         ret = bytecode_push(&ctx->bytecode_reloc, symbol,
 175                                 1, strlen(symbol) + 1);
 176         if (ret) {
 177                 goto end;
 178         }
 179         ret = 1;        /* legacy */
 180 end:
 181         free(insn);
 182         free(symbol);
 183         return ret;
 184 }
 185
 186 static
 187 int visit_node_load_expression(struct filter_parser_ctx *ctx,
 188                 const struct ir_op *node)
 189 {
 190         struct ir_load_expression *exp;
 191         struct ir_load_expression_op *op;
 192         int ret;
 193
 194         exp = node->u.load.u.expression;
 195         if (!exp) {
 196                 return -EINVAL;
 197         }
 198         op = exp->child;
 199         if (!op) {
 200                 return -EINVAL;
 201         }
 202
 203         /*
 204          * TODO: if we remove legacy load for application contexts, we
 205          * need to update session bytecode parser as well.
 206          */
 207         ret = visit_node_load_expression_legacy(ctx, exp, op);
 208         if (ret < 0) {
 209                 return ret;
 210         }
 211         if (ret > 0) {
 212                 return 0;       /* legacy */
 213         }
 214
 215         for (; op != NULL; op = op->next) {
 216                 switch (op->type) {
 217                 case IR_LOAD_EXPRESSION_GET_CONTEXT_ROOT:
 218                 {
 219                         ret = bytecode_push_get_context_root(&ctx->bytecode);
 220
 221                         if (ret) {
 222                                 return ret;
 223                         }
 224
 225                         break;
 226                 }
 227                 case IR_LOAD_EXPRESSION_GET_APP_CONTEXT_ROOT:
 228                 {
 229                         ret = bytecode_push_get_app_context_root(
 230                                         &ctx->bytecode);
 231
 232                         if (ret) {
 233                                 return ret;
 234                         }
 235
 236                         break;
 237                 }
 238                 case IR_LOAD_EXPRESSION_GET_PAYLOAD_ROOT:
 239                 {
 240                         ret = bytecode_push_get_payload_root(&ctx->bytecode);
 241
 242                         if (ret) {
 243                                 return ret;
 244                         }
 245
 246                         break;
 247                 }
 248                 case IR_LOAD_EXPRESSION_GET_SYMBOL:
 249                 {
 250                         ret = bytecode_push_get_symbol(&ctx->bytecode,
 251                                         &ctx->bytecode_reloc, op->u.symbol);
 252
 253                         if (ret) {
 254                                 return ret;
 255                         }
 256
 257                         break;
 258                 }
 259                 case IR_LOAD_EXPRESSION_GET_INDEX:
 260                 {
 261                         ret = bytecode_push_get_index_u64(
 262                                         &ctx->bytecode, op->u.index);
 263
 264                         if (ret) {
 265                                 return ret;
 266                         }
 267
 268                         break;
 269                 }
 270                 case IR_LOAD_EXPRESSION_LOAD_FIELD:
 271                 {
 272                         struct load_op *insn;
 273                         uint32_t insn_len = sizeof(struct load_op);
 274
 275                         insn = (load_op *) calloc(insn_len, 1);
 276                         if (!insn)
 277                                 return -ENOMEM;
 278                         insn->op = BYTECODE_OP_LOAD_FIELD;
 279                         ret = bytecode_push(&ctx->bytecode, insn, 1, insn_len);
 280                         free(insn);
 281                         if (ret) {
 282                                 return ret;
 283                         }
 284                         break;
 285                 }
 286                 }
 287         }
 288         return 0;
 289 }
 290
 291 static
 292 int visit_node_load(struct filter_parser_ctx *ctx, struct ir_op *node)
 293 {
 294         int ret;
 295
 296         switch (node->data_type) {
 297         case IR_DATA_UNKNOWN:
 298         default:
 299                 fprintf(stderr, "[error] Unknown data type in %s\n",
 300                         __func__);
 301                 return -EINVAL;
 302
 303         case IR_DATA_STRING:
 304         {
 305                 struct load_op *insn;
 306                 uint32_t insn_len = sizeof(struct load_op)
 307                         + strlen(node->u.load.u.string.value) + 1;
 308
 309                 insn = (load_op *) calloc(insn_len, 1);
 310                 if (!insn)
 311                         return -ENOMEM;
 312
 313                 switch (node->u.load.u.string.type) {
 314                 case IR_LOAD_STRING_TYPE_GLOB_STAR:
 315                         /*
 316                          * We explicitly tell the interpreter here that
 317                          * this load is a full star globbing pattern so
 318                          * that the appropriate matching function can be
 319                          * called. Also, see comment below.
 320                          */
 321                         insn->op = BYTECODE_OP_LOAD_STAR_GLOB_STRING;
 322                         break;
 323                 default:
 324                         /*
 325                          * This is the "legacy" string, which includes
 326                          * star globbing patterns with a star only at
 327                          * the end. Both "plain" and "star at the end"
 328                          * literal strings are handled at the same place
 329                          * by the tracer's filter bytecode interpreter,
 330                          * whereas full star globbing patterns (stars
 331                          * can be anywhere in the string) is a special
 332                          * case.
 333                          */
 334                         insn->op = BYTECODE_OP_LOAD_STRING;
 335                         break;
 336                 }
 337
 338                 strcpy(insn->data, node->u.load.u.string.value);
 339                 ret = bytecode_push(&ctx->bytecode, insn, 1, insn_len);
 340                 free(insn);
 341                 return ret;
 342         }
 343         case IR_DATA_NUMERIC:
 344         {
 345                 struct load_op *insn;
 346                 uint32_t insn_len = sizeof(struct load_op)
 347                         + sizeof(struct literal_numeric);
 348
 349                 insn = (load_op *) calloc(insn_len, 1);
 350                 if (!insn)
 351                         return -ENOMEM;
 352                 insn->op = BYTECODE_OP_LOAD_S64;
 353                 memcpy(insn->data, &node->u.load.u.num, sizeof(int64_t));
 354                 ret = bytecode_push(&ctx->bytecode, insn, 1, insn_len);
 355                 free(insn);
 356                 return ret;
 357         }
 358         case IR_DATA_FLOAT:
 359         {
 360                 struct load_op *insn;
 361                 uint32_t insn_len = sizeof(struct load_op)
 362                         + sizeof(struct literal_double);
 363
 364                 insn = (load_op *) calloc(insn_len, 1);
 365                 if (!insn)
 366                         return -ENOMEM;
 367                 insn->op = BYTECODE_OP_LOAD_DOUBLE;
 368                 memcpy(insn->data, &node->u.load.u.flt, sizeof(double));
 369                 ret = bytecode_push(&ctx->bytecode, insn, 1, insn_len);
 370                 free(insn);
 371                 return ret;
 372         }
 373         case IR_DATA_EXPRESSION:
 374                 return visit_node_load_expression(ctx, node);
 375         }
 376 }
 377
 378 static
 379 int visit_node_unary(struct filter_parser_ctx *ctx, struct ir_op *node)
 380 {
 381         int ret;
 382         struct unary_op insn;
 383
 384         /* Visit child */
 385         ret = recursive_visit_gen_bytecode(ctx, node->u.unary.child);
 386         if (ret)
 387                 return ret;
 388
 389         /* Generate end of bytecode instruction */
 390         switch (node->u.unary.type) {
 391         case AST_UNARY_UNKNOWN:
 392         default:
 393                 fprintf(stderr, "[error] Unknown unary node type in %s\n",
 394                         __func__);
 395                 return -EINVAL;
 396         case AST_UNARY_PLUS:
 397                 /* Nothing to do. */
 398                 return 0;
 399         case AST_UNARY_MINUS:
 400                 insn.op = BYTECODE_OP_UNARY_MINUS;
 401                 return bytecode_push(&ctx->bytecode, &insn, 1, sizeof(insn));
 402         case AST_UNARY_NOT:
 403                 insn.op = BYTECODE_OP_UNARY_NOT;
 404                 return bytecode_push(&ctx->bytecode, &insn, 1, sizeof(insn));
 405         case AST_UNARY_BIT_NOT:
 406                 insn.op = BYTECODE_OP_UNARY_BIT_NOT;
 407                 return bytecode_push(&ctx->bytecode, &insn, 1, sizeof(insn));
 408         }
 409 }
 410
 411 /*
 412  * Binary comparator nesting is disallowed. This allows fitting into
 413  * only 2 registers.
 414  */
 415 static
 416 int visit_node_binary(struct filter_parser_ctx *ctx, struct ir_op *node)
 417 {
 418         int ret;
 419         struct binary_op insn;
 420
 421         /* Visit child */
 422         ret = recursive_visit_gen_bytecode(ctx, node->u.binary.left);
 423         if (ret)
 424                 return ret;
 425         ret = recursive_visit_gen_bytecode(ctx, node->u.binary.right);
 426         if (ret)
 427                 return ret;
 428
 429         switch (node->u.binary.type) {
 430         case AST_OP_UNKNOWN:
 431         default:
 432                 fprintf(stderr, "[error] Unknown unary node type in %s\n",
 433                         __func__);
 434                 return -EINVAL;
 435
 436         case AST_OP_AND:
 437         case AST_OP_OR:
 438                 fprintf(stderr, "[error] Unexpected logical node type in %s\n",
 439                         __func__);
 440                 return -EINVAL;
 441
 442         case AST_OP_MUL:
 443                 insn.op = BYTECODE_OP_MUL;
 444                 break;
 445         case AST_OP_DIV:
 446                 insn.op = BYTECODE_OP_DIV;
 447                 break;
 448         case AST_OP_MOD:
 449                 insn.op = BYTECODE_OP_MOD;
 450                 break;
 451         case AST_OP_PLUS:
 452                 insn.op = BYTECODE_OP_PLUS;
 453                 break;
 454         case AST_OP_MINUS:
 455                 insn.op = BYTECODE_OP_MINUS;
 456                 break;
 457         case AST_OP_BIT_RSHIFT:
 458                 insn.op = BYTECODE_OP_BIT_RSHIFT;
 459                 break;
 460         case AST_OP_BIT_LSHIFT:
 461                 insn.op = BYTECODE_OP_BIT_LSHIFT;
 462                 break;
 463         case AST_OP_BIT_AND:
 464                 insn.op = BYTECODE_OP_BIT_AND;
 465                 break;
 466         case AST_OP_BIT_OR:
 467                 insn.op = BYTECODE_OP_BIT_OR;
 468                 break;
 469         case AST_OP_BIT_XOR:
 470                 insn.op = BYTECODE_OP_BIT_XOR;
 471                 break;
 472
 473         case AST_OP_EQ:
 474                 insn.op = BYTECODE_OP_EQ;
 475                 break;
 476         case AST_OP_NE:
 477                 insn.op = BYTECODE_OP_NE;
 478                 break;
 479         case AST_OP_GT:
 480                 insn.op = BYTECODE_OP_GT;
 481                 break;
 482         case AST_OP_LT:
 483                 insn.op = BYTECODE_OP_LT;
 484                 break;
 485         case AST_OP_GE:
 486                 insn.op = BYTECODE_OP_GE;
 487                 break;
 488         case AST_OP_LE:
 489                 insn.op = BYTECODE_OP_LE;
 490                 break;
 491         }
 492         return bytecode_push(&ctx->bytecode, &insn, 1, sizeof(insn));
 493 }
 494
 495 /*
 496  * A logical op always return a s64 (1 or 0).
 497  */
 498 static
 499 int visit_node_logical(struct filter_parser_ctx *ctx, struct ir_op *node)
 500 {
 501         int ret;
 502         struct logical_op insn;
 503         uint16_t skip_offset_loc;
 504         uint16_t target_loc;
 505
 506         /* Visit left child */
 507         ret = recursive_visit_gen_bytecode(ctx, node->u.binary.left);
 508         if (ret)
 509                 return ret;
 510         /* Cast to s64 if float or field ref */
 511         if ((node->u.binary.left->data_type == IR_DATA_FIELD_REF
 512                                 || node->u.binary.left->data_type == IR_DATA_GET_CONTEXT_REF
 513                                 || node->u.binary.left->data_type == IR_DATA_EXPRESSION)
 514                         || node->u.binary.left->data_type == IR_DATA_FLOAT) {
 515                 struct cast_op cast_insn;
 516
 517                 if (node->u.binary.left->data_type == IR_DATA_FIELD_REF
 518                                 || node->u.binary.left->data_type == IR_DATA_GET_CONTEXT_REF
 519                                 || node->u.binary.left->data_type == IR_DATA_EXPRESSION) {
 520                         cast_insn.op = BYTECODE_OP_CAST_TO_S64;
 521                 } else {
 522                         cast_insn.op = BYTECODE_OP_CAST_DOUBLE_TO_S64;
 523                 }
 524                 ret = bytecode_push(&ctx->bytecode, &cast_insn,
 525                                         1, sizeof(cast_insn));
 526                 if (ret)
 527                         return ret;
 528         }
 529         switch (node->u.logical.type) {
 530         default:
 531                 fprintf(stderr, "[error] Unknown node type in %s\n",
 532                         __func__);
 533                 return -EINVAL;
 534
 535         case AST_OP_AND:
 536                 insn.op = BYTECODE_OP_AND;
 537                 break;
 538         case AST_OP_OR:
 539                 insn.op = BYTECODE_OP_OR;
 540                 break;
 541         }
 542         insn.skip_offset = (uint16_t) -1UL;     /* Temporary */
 543         ret = bytecode_push_logical(&ctx->bytecode, &insn, 1, sizeof(insn),
 544                         &skip_offset_loc);
 545         if (ret)
 546                 return ret;
 547         /* Visit right child */
 548         ret = recursive_visit_gen_bytecode(ctx, node->u.binary.right);
 549         if (ret)
 550                 return ret;
 551         /* Cast to s64 if float or field ref */
 552         if ((node->u.binary.right->data_type == IR_DATA_FIELD_REF
 553                                 || node->u.binary.right->data_type == IR_DATA_GET_CONTEXT_REF
 554                                 || node->u.binary.right->data_type == IR_DATA_EXPRESSION)
 555                         || node->u.binary.right->data_type == IR_DATA_FLOAT) {
 556                 struct cast_op cast_insn;
 557
 558                 if (node->u.binary.right->data_type == IR_DATA_FIELD_REF
 559                                 || node->u.binary.right->data_type == IR_DATA_GET_CONTEXT_REF
 560                                 || node->u.binary.right->data_type == IR_DATA_EXPRESSION) {
 561                         cast_insn.op = BYTECODE_OP_CAST_TO_S64;
 562                 } else {
 563                         cast_insn.op = BYTECODE_OP_CAST_DOUBLE_TO_S64;
 564                 }
 565                 ret = bytecode_push(&ctx->bytecode, &cast_insn,
 566                                         1, sizeof(cast_insn));
 567                 if (ret)
 568                         return ret;
 569         }
 570         /* We now know where the logical op can skip. */
 571         target_loc = (uint16_t) bytecode_get_len(&ctx->bytecode->b);
 572         ret = bytecode_patch(&ctx->bytecode,
 573                         &target_loc,                    /* Offset to jump to */
 574                         skip_offset_loc,                /* Where to patch */
 575                         sizeof(uint16_t));
 576         return ret;
 577 }
 578
 579 /*
 580  * Postorder traversal of the tree. We need the children result before
 581  * we can evaluate the parent.
 582  */
 583 static
 584 int recursive_visit_gen_bytecode(struct filter_parser_ctx *ctx,
 585                 struct ir_op *node)
 586 {
 587         switch (node->op) {
 588         case IR_OP_UNKNOWN:
 589         default:
 590                 fprintf(stderr, "[error] Unknown node type in %s\n",
 591                         __func__);
 592                 return -EINVAL;
 593
 594         case IR_OP_ROOT:
 595                 return visit_node_root(ctx, node);
 596         case IR_OP_LOAD:
 597                 return visit_node_load(ctx, node);
 598         case IR_OP_UNARY:
 599                 return visit_node_unary(ctx, node);
 600         case IR_OP_BINARY:
 601                 return visit_node_binary(ctx, node);
 602         case IR_OP_LOGICAL:
 603                 return visit_node_logical(ctx, node);
 604         }
 605 }
 606
 607 void filter_bytecode_free(struct filter_parser_ctx *ctx)
 608 {
 609         if (!ctx) {
 610                 return;
 611         }
 612
 613         if (ctx->bytecode) {
 614                 free(ctx->bytecode);
 615                 ctx->bytecode = NULL;
 616         }
 617
 618         if (ctx->bytecode_reloc) {
 619                 free(ctx->bytecode_reloc);
 620                 ctx->bytecode_reloc = NULL;
 621         }
 622 }
 623
 624 int filter_visitor_bytecode_generate(struct filter_parser_ctx *ctx)
 625 {
 626         int ret;
 627
 628         ret = bytecode_init(&ctx->bytecode);
 629         if (ret)
 630                 return ret;
 631         ret = bytecode_init(&ctx->bytecode_reloc);
 632         if (ret)
 633                 goto error;
 634         ret = recursive_visit_gen_bytecode(ctx, ctx->ir_root);
 635         if (ret)
 636                 goto error;
 637
 638         /* Finally, append symbol table to bytecode */
 639         ctx->bytecode->b.reloc_table_offset = bytecode_get_len(&ctx->bytecode->b);
 640         return bytecode_push(&ctx->bytecode, ctx->bytecode_reloc->b.data,
 641                         1, bytecode_get_len(&ctx->bytecode_reloc->b));
 642
 643 error:
 644         filter_bytecode_free(ctx);
 645         return ret;
 646 }