src/lib/lttng-ctl/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  * 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 <stdlib.h>
  23 #include <string.h>
  24 #include <errno.h>
  25 #include <common/align.h>
  26 #include <common/compat/string.h>
  27
  28 #include "filter-bytecode.h"
  29 #include "filter-ir.h"
  30 #include "filter-ast.h"
  31
  32 #include <common/macros.h>
  33
  34 #ifndef max_t
  35 #define max_t(type, a, b)       ((type) ((a) > (b) ? (a) : (b)))
  36 #endif
  37
  38 #define INIT_ALLOC_SIZE         4
  39
  40 static
  41 int recursive_visit_gen_bytecode(struct filter_parser_ctx *ctx,
  42                 struct ir_op *node);
  43
  44 static inline int get_count_order(unsigned int count)
  45 {
  46         int order;
  47
  48         order = lttng_fls(count) - 1;
  49         if (count & (count - 1))
  50                 order++;
  51         return order;
  52 }
  53
  54 static
  55 int bytecode_init(struct lttng_filter_bytecode_alloc **fb)
  56 {
  57         uint32_t alloc_len;
  58
  59         alloc_len = sizeof(struct lttng_filter_bytecode_alloc) + INIT_ALLOC_SIZE;
  60         *fb = calloc(alloc_len, 1);
  61         if (!*fb) {
  62                 return -ENOMEM;
  63         } else {
  64                 (*fb)->alloc_len = alloc_len;
  65                 return 0;
  66         }
  67 }
  68
  69 static
  70 int32_t bytecode_reserve(struct lttng_filter_bytecode_alloc **fb, uint32_t align, uint32_t len)
  71 {
  72         int32_t ret;
  73         uint32_t padding = offset_align((*fb)->b.len, align);
  74         uint32_t new_len = (*fb)->b.len + padding + len;
  75         uint32_t new_alloc_len = sizeof(struct lttng_filter_bytecode_alloc) + new_len;
  76         uint32_t old_alloc_len = (*fb)->alloc_len;
  77
  78         if (new_len > LTTNG_FILTER_MAX_LEN)
  79                 return -EINVAL;
  80
  81         if (new_alloc_len > old_alloc_len) {
  82                 struct lttng_filter_bytecode_alloc *newptr;
  83
  84                 new_alloc_len =
  85                         max_t(uint32_t, 1U << get_count_order(new_alloc_len), old_alloc_len << 1);
  86                 newptr = realloc(*fb, new_alloc_len);
  87                 if (!newptr)
  88                         return -ENOMEM;
  89                 *fb = newptr;
  90                 /* We zero directly the memory from start of allocation. */
  91                 memset(&((char *) *fb)[old_alloc_len], 0, new_alloc_len - old_alloc_len);
  92                 (*fb)->alloc_len = new_alloc_len;
  93         }
  94         (*fb)->b.len += padding;
  95         ret = (*fb)->b.len;
  96         (*fb)->b.len += len;
  97         return ret;
  98 }
  99
 100 static
 101 int bytecode_push(struct lttng_filter_bytecode_alloc **fb, const void *data,
 102                 uint32_t align, uint32_t len)
 103 {
 104         int32_t offset;
 105
 106         offset = bytecode_reserve(fb, align, len);
 107         if (offset < 0)
 108                 return offset;
 109         memcpy(&(*fb)->b.data[offset], data, len);
 110         return 0;
 111 }
 112
 113 static
 114 int bytecode_push_logical(struct lttng_filter_bytecode_alloc **fb,
 115                 struct logical_op *data,
 116                 uint32_t align, uint32_t len,
 117                 uint16_t *skip_offset)
 118 {
 119         int32_t offset;
 120
 121         offset = bytecode_reserve(fb, align, len);
 122         if (offset < 0)
 123                 return offset;
 124         memcpy(&(*fb)->b.data[offset], data, len);
 125         *skip_offset =
 126                 (void *) &((struct logical_op *) &(*fb)->b.data[offset])->skip_offset
 127                         - (void *) &(*fb)->b.data[0];
 128         return 0;
 129 }
 130
 131 static
 132 int bytecode_patch(struct lttng_filter_bytecode_alloc **fb,
 133                 const void *data,
 134                 uint16_t offset,
 135                 uint32_t len)
 136 {
 137         if (offset >= (*fb)->b.len) {
 138                 return -EINVAL;
 139         }
 140         memcpy(&(*fb)->b.data[offset], data, len);
 141         return 0;
 142 }
 143
 144 static
 145 int visit_node_root(struct filter_parser_ctx *ctx, struct ir_op *node)
 146 {
 147         int ret;
 148         struct return_op insn;
 149
 150         /* Visit child */
 151         ret = recursive_visit_gen_bytecode(ctx, node->u.root.child);
 152         if (ret)
 153                 return ret;
 154
 155         /* Generate end of bytecode instruction */
 156         insn.op = FILTER_OP_RETURN;
 157         return bytecode_push(&ctx->bytecode, &insn, 1, sizeof(insn));
 158 }
 159
 160 static
 161 int visit_node_load(struct filter_parser_ctx *ctx, struct ir_op *node)
 162 {
 163         int ret;
 164
 165         switch (node->data_type) {
 166         case IR_DATA_UNKNOWN:
 167         default:
 168                 fprintf(stderr, "[error] Unknown data type in %s\n",
 169                         __func__);
 170                 return -EINVAL;
 171
 172         case IR_DATA_STRING:
 173         {
 174                 struct load_op *insn;
 175                 uint32_t insn_len = sizeof(struct load_op)
 176                         + strlen(node->u.load.u.string.value) + 1;
 177
 178                 insn = calloc(insn_len, 1);
 179                 if (!insn)
 180                         return -ENOMEM;
 181
 182                 switch (node->u.load.u.string.type) {
 183                 case IR_LOAD_STRING_TYPE_GLOB_STAR:
 184                         /*
 185                          * We explicitly tell the interpreter here that
 186                          * this load is a full star globbing pattern so
 187                          * that the appropriate matching function can be
 188                          * called. Also, see comment below.
 189                          */
 190                         insn->op = FILTER_OP_LOAD_STAR_GLOB_STRING;
 191                         break;
 192                 default:
 193                         /*
 194                          * This is the "legacy" string, which includes
 195                          * star globbing patterns with a star only at
 196                          * the end. Both "plain" and "star at the end"
 197                          * literal strings are handled at the same place
 198                          * by the tracer's filter bytecode interpreter,
 199                          * whereas full star globbing patterns (stars
 200                          * can be anywhere in the string) is a special
 201                          * case.
 202                          */
 203                         insn->op = FILTER_OP_LOAD_STRING;
 204                         break;
 205                 }
 206
 207                 strcpy(insn->data, node->u.load.u.string.value);
 208                 ret = bytecode_push(&ctx->bytecode, insn, 1, insn_len);
 209                 free(insn);
 210                 return ret;
 211         }
 212         case IR_DATA_NUMERIC:
 213         {
 214                 struct load_op *insn;
 215                 uint32_t insn_len = sizeof(struct load_op)
 216                         + sizeof(struct literal_numeric);
 217
 218                 insn = calloc(insn_len, 1);
 219                 if (!insn)
 220                         return -ENOMEM;
 221                 insn->op = FILTER_OP_LOAD_S64;
 222                 memcpy(insn->data, &node->u.load.u.num, sizeof(int64_t));
 223                 ret = bytecode_push(&ctx->bytecode, insn, 1, insn_len);
 224                 free(insn);
 225                 return ret;
 226         }
 227         case IR_DATA_FLOAT:
 228         {
 229                 struct load_op *insn;
 230                 uint32_t insn_len = sizeof(struct load_op)
 231                         + sizeof(struct literal_double);
 232
 233                 insn = calloc(insn_len, 1);
 234                 if (!insn)
 235                         return -ENOMEM;
 236                 insn->op = FILTER_OP_LOAD_DOUBLE;
 237                 memcpy(insn->data, &node->u.load.u.flt, sizeof(double));
 238                 ret = bytecode_push(&ctx->bytecode, insn, 1, insn_len);
 239                 free(insn);
 240                 return ret;
 241         }
 242         case IR_DATA_FIELD_REF: /* fall-through */
 243         case IR_DATA_GET_CONTEXT_REF:
 244         {
 245                 struct load_op *insn;
 246                 uint32_t insn_len = sizeof(struct load_op)
 247                         + sizeof(struct field_ref);
 248                 struct field_ref ref_offset;
 249                 uint32_t reloc_offset_u32;
 250                 uint16_t reloc_offset;
 251
 252                 insn = calloc(insn_len, 1);
 253                 if (!insn)
 254                         return -ENOMEM;
 255                 switch(node->data_type) {
 256                 case IR_DATA_FIELD_REF:
 257                         insn->op = FILTER_OP_LOAD_FIELD_REF;
 258                         break;
 259                 case IR_DATA_GET_CONTEXT_REF:
 260                         insn->op = FILTER_OP_GET_CONTEXT_REF;
 261                         break;
 262                 default:
 263                         free(insn);
 264                         return -EINVAL;
 265                 }
 266                 ref_offset.offset = (uint16_t) -1U;
 267                 memcpy(insn->data, &ref_offset, sizeof(ref_offset));
 268                 /* reloc_offset points to struct load_op */
 269                 reloc_offset_u32 = bytecode_get_len(&ctx->bytecode->b);
 270                 if (reloc_offset_u32 > LTTNG_FILTER_MAX_LEN - 1) {
 271                         free(insn);
 272                         return -EINVAL;
 273                 }
 274                 reloc_offset = (uint16_t) reloc_offset_u32;
 275                 ret = bytecode_push(&ctx->bytecode, insn, 1, insn_len);
 276                 if (ret) {
 277                         free(insn);
 278                         return ret;
 279                 }
 280                 /* append reloc */
 281                 ret = bytecode_push(&ctx->bytecode_reloc, &reloc_offset,
 282                                         1, sizeof(reloc_offset));
 283                 if (ret) {
 284                         free(insn);
 285                         return ret;
 286                 }
 287                 ret = bytecode_push(&ctx->bytecode_reloc, node->u.load.u.ref,
 288                                         1, strlen(node->u.load.u.ref) + 1);
 289                 free(insn);
 290                 return ret;
 291         }
 292         }
 293 }
 294
 295 static
 296 int visit_node_unary(struct filter_parser_ctx *ctx, struct ir_op *node)
 297 {
 298         int ret;
 299         struct unary_op insn;
 300
 301         /* Visit child */
 302         ret = recursive_visit_gen_bytecode(ctx, node->u.unary.child);
 303         if (ret)
 304                 return ret;
 305
 306         /* Generate end of bytecode instruction */
 307         switch (node->u.unary.type) {
 308         case AST_UNARY_UNKNOWN:
 309         default:
 310                 fprintf(stderr, "[error] Unknown unary node type in %s\n",
 311                         __func__);
 312                 return -EINVAL;
 313         case AST_UNARY_PLUS:
 314                 /* Nothing to do. */
 315                 return 0;
 316         case AST_UNARY_MINUS:
 317                 insn.op = FILTER_OP_UNARY_MINUS;
 318                 return bytecode_push(&ctx->bytecode, &insn, 1, sizeof(insn));
 319         case AST_UNARY_NOT:
 320                 insn.op = FILTER_OP_UNARY_NOT;
 321                 return bytecode_push(&ctx->bytecode, &insn, 1, sizeof(insn));
 322         }
 323 }
 324
 325 /*
 326  * Binary comparator nesting is disallowed. This allows fitting into
 327  * only 2 registers.
 328  */
 329 static
 330 int visit_node_binary(struct filter_parser_ctx *ctx, struct ir_op *node)
 331 {
 332         int ret;
 333         struct binary_op insn;
 334
 335         /* Visit child */
 336         ret = recursive_visit_gen_bytecode(ctx, node->u.binary.left);
 337         if (ret)
 338                 return ret;
 339         ret = recursive_visit_gen_bytecode(ctx, node->u.binary.right);
 340         if (ret)
 341                 return ret;
 342
 343         switch (node->u.binary.type) {
 344         case AST_OP_UNKNOWN:
 345         default:
 346                 fprintf(stderr, "[error] Unknown unary node type in %s\n",
 347                         __func__);
 348                 return -EINVAL;
 349
 350         case AST_OP_AND:
 351         case AST_OP_OR:
 352                 fprintf(stderr, "[error] Unexpected logical node type in %s\n",
 353                         __func__);
 354                 return -EINVAL;
 355
 356         case AST_OP_MUL:
 357                 insn.op = FILTER_OP_MUL;
 358                 break;
 359         case AST_OP_DIV:
 360                 insn.op = FILTER_OP_DIV;
 361                 break;
 362         case AST_OP_MOD:
 363                 insn.op = FILTER_OP_MOD;
 364                 break;
 365         case AST_OP_PLUS:
 366                 insn.op = FILTER_OP_PLUS;
 367                 break;
 368         case AST_OP_MINUS:
 369                 insn.op = FILTER_OP_MINUS;
 370                 break;
 371         case AST_OP_RSHIFT:
 372                 insn.op = FILTER_OP_RSHIFT;
 373                 break;
 374         case AST_OP_LSHIFT:
 375                 insn.op = FILTER_OP_LSHIFT;
 376                 break;
 377         case AST_OP_BIN_AND:
 378                 insn.op = FILTER_OP_BIN_AND;
 379                 break;
 380         case AST_OP_BIN_OR:
 381                 insn.op = FILTER_OP_BIN_OR;
 382                 break;
 383         case AST_OP_BIN_XOR:
 384                 insn.op = FILTER_OP_BIN_XOR;
 385                 break;
 386
 387         case AST_OP_EQ:
 388                 insn.op = FILTER_OP_EQ;
 389                 break;
 390         case AST_OP_NE:
 391                 insn.op = FILTER_OP_NE;
 392                 break;
 393         case AST_OP_GT:
 394                 insn.op = FILTER_OP_GT;
 395                 break;
 396         case AST_OP_LT:
 397                 insn.op = FILTER_OP_LT;
 398                 break;
 399         case AST_OP_GE:
 400                 insn.op = FILTER_OP_GE;
 401                 break;
 402         case AST_OP_LE:
 403                 insn.op = FILTER_OP_LE;
 404                 break;
 405         }
 406         return bytecode_push(&ctx->bytecode, &insn, 1, sizeof(insn));
 407 }
 408
 409 /*
 410  * A logical op always return a s64 (1 or 0).
 411  */
 412 static
 413 int visit_node_logical(struct filter_parser_ctx *ctx, struct ir_op *node)
 414 {
 415         int ret;
 416         struct logical_op insn;
 417         uint16_t skip_offset_loc;
 418         uint16_t target_loc;
 419
 420         /* Visit left child */
 421         ret = recursive_visit_gen_bytecode(ctx, node->u.binary.left);
 422         if (ret)
 423                 return ret;
 424         /* Cast to s64 if float or field ref */
 425         if ((node->u.binary.left->data_type == IR_DATA_FIELD_REF
 426                                 || node->u.binary.left->data_type == IR_DATA_GET_CONTEXT_REF)
 427                         || node->u.binary.left->data_type == IR_DATA_FLOAT) {
 428                 struct cast_op cast_insn;
 429
 430                 if (node->u.binary.left->data_type == IR_DATA_FIELD_REF
 431                                 || node->u.binary.left->data_type == IR_DATA_GET_CONTEXT_REF) {
 432                         cast_insn.op = FILTER_OP_CAST_TO_S64;
 433                 } else {
 434                         cast_insn.op = FILTER_OP_CAST_DOUBLE_TO_S64;
 435                 }
 436                 ret = bytecode_push(&ctx->bytecode, &cast_insn,
 437                                         1, sizeof(cast_insn));
 438                 if (ret)
 439                         return ret;
 440         }
 441         switch (node->u.logical.type) {
 442         default:
 443                 fprintf(stderr, "[error] Unknown node type in %s\n",
 444                         __func__);
 445                 return -EINVAL;
 446
 447         case AST_OP_AND:
 448                 insn.op = FILTER_OP_AND;
 449                 break;
 450         case AST_OP_OR:
 451                 insn.op = FILTER_OP_OR;
 452                 break;
 453         }
 454         insn.skip_offset = (uint16_t) -1UL;     /* Temporary */
 455         ret = bytecode_push_logical(&ctx->bytecode, &insn, 1, sizeof(insn),
 456                         &skip_offset_loc);
 457         if (ret)
 458                 return ret;
 459         /* Visit right child */
 460         ret = recursive_visit_gen_bytecode(ctx, node->u.binary.right);
 461         if (ret)
 462                 return ret;
 463         /* Cast to s64 if float or field ref */
 464         if ((node->u.binary.right->data_type == IR_DATA_FIELD_REF
 465                                 || node->u.binary.right->data_type == IR_DATA_GET_CONTEXT_REF)
 466                         || node->u.binary.right->data_type == IR_DATA_FLOAT) {
 467                 struct cast_op cast_insn;
 468
 469                 if (node->u.binary.right->data_type == IR_DATA_FIELD_REF
 470                                 || node->u.binary.right->data_type == IR_DATA_GET_CONTEXT_REF) {
 471                         cast_insn.op = FILTER_OP_CAST_TO_S64;
 472                 } else {
 473                         cast_insn.op = FILTER_OP_CAST_DOUBLE_TO_S64;
 474                 }
 475                 ret = bytecode_push(&ctx->bytecode, &cast_insn,
 476                                         1, sizeof(cast_insn));
 477                 if (ret)
 478                         return ret;
 479         }
 480         /* We now know where the logical op can skip. */
 481         target_loc = (uint16_t) bytecode_get_len(&ctx->bytecode->b);
 482         ret = bytecode_patch(&ctx->bytecode,
 483                         &target_loc,                    /* Offset to jump to */
 484                         skip_offset_loc,                /* Where to patch */
 485                         sizeof(uint16_t));
 486         return ret;
 487 }
 488
 489 /*
 490  * Postorder traversal of the tree. We need the children result before
 491  * we can evaluate the parent.
 492  */
 493 static
 494 int recursive_visit_gen_bytecode(struct filter_parser_ctx *ctx,
 495                 struct ir_op *node)
 496 {
 497         switch (node->op) {
 498         case IR_OP_UNKNOWN:
 499         default:
 500                 fprintf(stderr, "[error] Unknown node type in %s\n",
 501                         __func__);
 502                 return -EINVAL;
 503
 504         case IR_OP_ROOT:
 505                 return visit_node_root(ctx, node);
 506         case IR_OP_LOAD:
 507                 return visit_node_load(ctx, node);
 508         case IR_OP_UNARY:
 509                 return visit_node_unary(ctx, node);
 510         case IR_OP_BINARY:
 511                 return visit_node_binary(ctx, node);
 512         case IR_OP_LOGICAL:
 513                 return visit_node_logical(ctx, node);
 514         }
 515 }
 516
 517 LTTNG_HIDDEN
 518 void filter_bytecode_free(struct filter_parser_ctx *ctx)
 519 {
 520         if (!ctx) {
 521                 return;
 522         }
 523
 524         if (ctx->bytecode) {
 525                 free(ctx->bytecode);
 526                 ctx->bytecode = NULL;
 527         }
 528
 529         if (ctx->bytecode_reloc) {
 530                 free(ctx->bytecode_reloc);
 531                 ctx->bytecode_reloc = NULL;
 532         }
 533 }
 534
 535 LTTNG_HIDDEN
 536 int filter_visitor_bytecode_generate(struct filter_parser_ctx *ctx)
 537 {
 538         int ret;
 539
 540         ret = bytecode_init(&ctx->bytecode);
 541         if (ret)
 542                 return ret;
 543         ret = bytecode_init(&ctx->bytecode_reloc);
 544         if (ret)
 545                 goto error;
 546         ret = recursive_visit_gen_bytecode(ctx, ctx->ir_root);
 547         if (ret)
 548                 goto error;
 549
 550         /* Finally, append symbol table to bytecode */
 551         ctx->bytecode->b.reloc_table_offset = bytecode_get_len(&ctx->bytecode->b);
 552         return bytecode_push(&ctx->bytecode, ctx->bytecode_reloc->b.data,
 553                         1, bytecode_get_len(&ctx->bytecode_reloc->b));
 554
 555 error:
 556         filter_bytecode_free(ctx);
 557         return ret;
 558 }