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

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