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