From 953192ba6eb2118c22bcfcb4bcd813f141b407e7 Mon Sep 17 00:00:00 2001 From: Mathieu Desnoyers Date: Tue, 10 Jul 2012 15:15:04 -0400 Subject: [PATCH] Implement filter expression to bytecode compiler in liblttng-ctl Signed-off-by: Mathieu Desnoyers --- configure.ac | 4 + src/lib/lttng-ctl/Makefile.am | 20 +- src/lib/lttng-ctl/align.h | 64 ++ src/lib/lttng-ctl/filter-ast.h | 186 +++++ src/lib/lttng-ctl/filter-bytecode.h | 148 ++++ src/lib/lttng-ctl/filter-grammar-test.c | 133 ++++ src/lib/lttng-ctl/filter-ir.h | 102 +++ src/lib/lttng-ctl/filter-lexer.l | 118 +++ src/lib/lttng-ctl/filter-parser.y | 600 ++++++++++++++ .../filter-visitor-generate-bytecode.c | 464 +++++++++++ .../lttng-ctl/filter-visitor-generate-ir.c | 742 ++++++++++++++++++ ...ilter-visitor-ir-check-binary-comparator.c | 82 ++ ...ilter-visitor-ir-check-binary-op-nesting.c | 82 ++ src/lib/lttng-ctl/filter-visitor-set-parent.c | 138 ++++ src/lib/lttng-ctl/filter-visitor-xml.c | 248 ++++++ src/lib/lttng-ctl/tests.txt | 23 + 16 files changed, 3153 insertions(+), 1 deletion(-) create mode 100644 src/lib/lttng-ctl/align.h create mode 100644 src/lib/lttng-ctl/filter-ast.h create mode 100644 src/lib/lttng-ctl/filter-bytecode.h create mode 100644 src/lib/lttng-ctl/filter-grammar-test.c create mode 100644 src/lib/lttng-ctl/filter-ir.h create mode 100644 src/lib/lttng-ctl/filter-lexer.l create mode 100644 src/lib/lttng-ctl/filter-parser.y create mode 100644 src/lib/lttng-ctl/filter-visitor-generate-bytecode.c create mode 100644 src/lib/lttng-ctl/filter-visitor-generate-ir.c create mode 100644 src/lib/lttng-ctl/filter-visitor-ir-check-binary-comparator.c create mode 100644 src/lib/lttng-ctl/filter-visitor-ir-check-binary-op-nesting.c create mode 100644 src/lib/lttng-ctl/filter-visitor-set-parent.c create mode 100644 src/lib/lttng-ctl/filter-visitor-xml.c create mode 100644 src/lib/lttng-ctl/tests.txt diff --git a/configure.ac b/configure.ac index 4e7c2570a..cba96c1af 100644 --- a/configure.ac +++ b/configure.ac @@ -162,6 +162,10 @@ AM_CONDITIONAL([COMPAT_EPOLL], [ test "$enable_epoll" = "yes" ]) AC_SYS_LARGEFILE AC_PROG_CC LT_INIT +AC_PROG_YACC +AC_PROG_LEX + +AC_DEFUN([AC_PROG_BISON], [AC_CHECK_PROGS(BISON, bison, bison)]) CFLAGS="-Wall $CFLAGS -g -fno-strict-aliasing" diff --git a/src/lib/lttng-ctl/Makefile.am b/src/lib/lttng-ctl/Makefile.am index 6bc5432aa..4f61d5b01 100644 --- a/src/lib/lttng-ctl/Makefile.am +++ b/src/lib/lttng-ctl/Makefile.am @@ -1,6 +1,24 @@ lib_LTLIBRARIES = liblttng-ctl.la +bin_PROGRAMS = filter-grammar-test -liblttng_ctl_la_SOURCES = lttng-ctl.c +BUILT_SOURCES = filter-parser.h +AM_YFLAGS = -t -d -v + +noinst_HEADERS = filter-ast.h +liblttng_ctl_la_SOURCES = lttng-ctl.c \ + filter-lexer.l filter-parser.y \ + filter-visitor-set-parent.c \ + filter-visitor-xml.c \ + filter-visitor-generate-ir.c \ + filter-visitor-ir-check-binary-op-nesting.c \ + filter-visitor-generate-bytecode.c \ + align.h \ + filter-ast.h \ + filter-bytecode.h \ + filter-ir.h + +filter_grammar_test_SOURCES = filter-grammar-test.c +filter_grammar_test_LDADD = liblttng-ctl.la liblttng_ctl_la_LIBADD = \ $(top_builddir)/src/common/sessiond-comm/libsessiond-comm.la diff --git a/src/lib/lttng-ctl/align.h b/src/lib/lttng-ctl/align.h new file mode 100644 index 000000000..813bade92 --- /dev/null +++ b/src/lib/lttng-ctl/align.h @@ -0,0 +1,64 @@ +#ifndef _LTTNG_ALIGN_H +#define _LTTNG_ALIGN_H + +/* + * align.h + * + * (C) Copyright 2010-2011 - Mathieu Desnoyers + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to deal + * in the Software without restriction, including without limitation the rights + * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + */ + +#include +#include +#include + +#ifndef PAGE_SIZE /* Cygwin limits.h defines its own PAGE_SIZE */ +#define PAGE_SIZE sysconf(_SC_PAGE_SIZE) +#endif + +#define PAGE_MASK (~(PAGE_SIZE - 1)) +#define __ALIGN_MASK(v, mask) (((v) + (mask)) & ~(mask)) +#define ALIGN(v, align) __ALIGN_MASK(v, (__typeof__(v)) (align) - 1) +#define PAGE_ALIGN(addr) ALIGN(addr, PAGE_SIZE) + +/** + * offset_align - Calculate the offset needed to align an object on its natural + * alignment towards higher addresses. + * @align_drift: object offset from an "alignment"-aligned address. + * @alignment: natural object alignment. Must be non-zero, power of 2. + * + * Returns the offset that must be added to align towards higher + * addresses. + */ +#define offset_align(align_drift, alignment) \ + ({ \ + LTTNG_BUILD_RUNTIME_BUG_ON((alignment) == 0 \ + || ((alignment) & ((alignment) - 1))); \ + (((alignment) - (align_drift)) & ((alignment) - 1)); \ + }) + +/** + * offset_align_floor - Calculate the offset needed to align an object + * on its natural alignment towards lower addresses. + * @align_drift: object offset from an "alignment"-aligned address. + * @alignment: natural object alignment. Must be non-zero, power of 2. + * + * Returns the offset that must be substracted to align towards lower addresses. + */ +#define offset_align_floor(align_drift, alignment) \ + ({ \ + LTTNG_BUILD_RUNTIME_BUG_ON((alignment) == 0 \ + || ((alignment) & ((alignment) - 1))); \ + (((align_drift) - (alignment)) & ((alignment) - 1); \ + }) + +#endif /* _LTTNG_ALIGN_H */ diff --git a/src/lib/lttng-ctl/filter-ast.h b/src/lib/lttng-ctl/filter-ast.h new file mode 100644 index 000000000..816562e23 --- /dev/null +++ b/src/lib/lttng-ctl/filter-ast.h @@ -0,0 +1,186 @@ +#ifndef _FILTER_AST_H +#define _FILTER_AST_H + +/* + * filter-ast.h + * + * LTTng filter AST + * + * Copyright 2012 - Mathieu Desnoyers + * + * This library is free software; you can redistribute it and/or modify it + * under the terms of the GNU Lesser General Public License, version 2.1 only, + * as published by the Free Software Foundation. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public License + * along with this library; if not, write to the Free Software Foundation, + * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA + */ + +#include +#include + +#define printf_debug(fmt, args...) \ + do { \ + if (filter_parser_debug) \ + fprintf(stdout, "[debug] " fmt, ## args); \ + } while (0) + +// the parameter name (of the reentrant 'yyparse' function) +// data is a pointer to a 'SParserParam' structure +//#define YYPARSE_PARAM parser_ctx + +// the argument for the 'yylex' function +#define YYLEX_PARAM ((struct filter_parser_ctx *) parser_ctx)->scanner + +#ifndef YY_TYPEDEF_YY_SCANNER_T +#define YY_TYPEDEF_YY_SCANNER_T +typedef void* yyscan_t; +#endif + +extern int filter_parser_debug; + +struct filter_node; +struct filter_parser; + +enum node_type { + NODE_UNKNOWN = 0, + NODE_ROOT, + + NODE_EXPRESSION, + NODE_OP, + NODE_UNARY_OP, + + NR_NODE_TYPES, +}; + +enum op_type { + AST_OP_UNKNOWN = 0, + AST_OP_MUL, + AST_OP_DIV, + AST_OP_MOD, + AST_OP_PLUS, + AST_OP_MINUS, + AST_OP_RSHIFT, + AST_OP_LSHIFT, + AST_OP_AND, + AST_OP_OR, + AST_OP_BIN_AND, + AST_OP_BIN_OR, + AST_OP_BIN_XOR, + + AST_OP_EQ, + AST_OP_NE, + AST_OP_GT, + AST_OP_LT, + AST_OP_GE, + AST_OP_LE, +}; + +enum unary_op_type { + AST_UNARY_UNKNOWN = 0, + AST_UNARY_PLUS, + AST_UNARY_MINUS, + AST_UNARY_NOT, +}; + +enum ast_link_type { + AST_LINK_UNKNOWN = 0, + AST_LINK_DOT, + AST_LINK_RARROW, +}; + +struct filter_node { + /* + * Parent node is only set on demand by specific visitor. + */ + struct filter_node *parent; + struct cds_list_head gc; + + enum node_type type; + union { + struct { + } unknown; + struct { + struct filter_node *child; + } root; + struct { + enum { + AST_EXP_UNKNOWN = 0, + AST_EXP_STRING, + AST_EXP_CONSTANT, + AST_EXP_IDENTIFIER, + AST_EXP_NESTED, + } type; + enum ast_link_type post_op; /* reverse */ + enum ast_link_type pre_op; /* forward */ + union { + char *string; + uint64_t constant; + char *identifier; + /* + * child can be nested. + */ + struct filter_node *child; + } u; + /* linked dot/arrow chain */ + struct filter_node *prev; + struct filter_node *next; + } expression; + struct { + enum op_type type; + struct filter_node *lchild; + struct filter_node *rchild; + } op; + struct { + enum unary_op_type type; + struct filter_node *child; + } unary_op; + } u; +}; + +struct filter_ast { + struct filter_node root; + struct cds_list_head allocated_nodes; +}; + +const char *node_type(struct filter_node *node); + +struct ir_op; +struct filter_bytecode; + +struct filter_parser_ctx { + yyscan_t scanner; + struct filter_ast *ast; + struct cds_list_head allocated_strings; + struct ir_op *ir_root; + struct filter_bytecode_alloc *bytecode; + struct filter_bytecode_alloc *bytecode_reloc; +}; + +struct filter_parser_ctx *filter_parser_ctx_alloc(FILE *input); +void filter_parser_ctx_free(struct filter_parser_ctx *parser_ctx); +int filter_parser_ctx_append_ast(struct filter_parser_ctx *parser_ctx); + +static inline +struct filter_ast *filter_parser_get_ast(struct filter_parser_ctx *parser_ctx) +{ + return parser_ctx->ast; +} + +int filter_visitor_set_parent(struct filter_parser_ctx *ctx); +int filter_visitor_print_xml(struct filter_parser_ctx *ctx, FILE *stream, + int indent); +int filter_visitor_ir_generate(struct filter_parser_ctx *ctx); +void filter_ir_free(struct filter_parser_ctx *ctx); +int filter_visitor_bytecode_generate(struct filter_parser_ctx *ctx); +void filter_bytecode_free(struct filter_parser_ctx *ctx); +int filter_visitor_ir_check_binary_op_nesting(struct filter_parser_ctx *ctx); +int filter_visitor_ir_check_binary_comparator(struct filter_parser_ctx *ctx); + +#endif /* _FILTER_AST_H */ diff --git a/src/lib/lttng-ctl/filter-bytecode.h b/src/lib/lttng-ctl/filter-bytecode.h new file mode 100644 index 000000000..fc2d6c8d4 --- /dev/null +++ b/src/lib/lttng-ctl/filter-bytecode.h @@ -0,0 +1,148 @@ +#ifndef _FILTER_BYTECODE_H +#define _FILTER_BYTECODE_H + +/* + * filter-bytecode.h + * + * LTTng filter bytecode + * + * Copyright 2012 - Mathieu Desnoyers + * + * This library is free software; you can redistribute it and/or modify it + * under the terms of the GNU Lesser General Public License, version 2.1 only, + * as published by the Free Software Foundation. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public License + * along with this library; if not, write to the Free Software Foundation, + * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA + */ + +#include "filter-ast.h" + +/* + * offsets are absolute from start of bytecode. + */ + +enum filter_register { + REG_R0 = 0, + REG_R1 = 1, + REG_ERROR, +}; + +enum field_ref_type { + FIELD_REF_UNKNOWN = 0, + FIELD_REF_STRING, + FIELD_REF_SEQUENCE, + FIELD_REF_S64, +}; + +struct field_ref { + /* Initially, symbol offset. After link, field offset. */ + uint16_t offset; + uint8_t type; /* enum field_ref_type */ +} __attribute__((packed)); + +struct literal_numeric { + int64_t v; +} __attribute__((packed)); + +struct literal_string { + char string[0]; +} __attribute__((packed)); + +enum filter_op { + FILTER_OP_UNKNOWN = 0, + + FILTER_OP_RETURN, + + /* binary */ + FILTER_OP_MUL, + FILTER_OP_DIV, + FILTER_OP_MOD, + FILTER_OP_PLUS, + FILTER_OP_MINUS, + FILTER_OP_RSHIFT, + FILTER_OP_LSHIFT, + FILTER_OP_BIN_AND, + FILTER_OP_BIN_OR, + FILTER_OP_BIN_XOR, + FILTER_OP_EQ, + FILTER_OP_NE, + FILTER_OP_GT, + FILTER_OP_LT, + FILTER_OP_GE, + FILTER_OP_LE, + + /* unary */ + FILTER_OP_UNARY_PLUS, + FILTER_OP_UNARY_MINUS, + FILTER_OP_UNARY_NOT, + + /* logical */ + FILTER_OP_AND, + FILTER_OP_OR, + + /* load */ + FILTER_OP_LOAD_FIELD_REF, + FILTER_OP_LOAD_STRING, + FILTER_OP_LOAD_S64, + + NR_FILTER_OPS, +}; + +typedef uint8_t filter_opcode_t; + +struct load_op { + filter_opcode_t op; + uint8_t reg; /* enum filter_register */ + char data[0]; + /* data to load. Size known by enum filter_opcode and null-term char. */ +} __attribute__((packed)); + +struct binary_op { + filter_opcode_t op; +} __attribute__((packed)); + +struct unary_op { + filter_opcode_t op; + uint8_t reg; /* enum filter_register */ +} __attribute__((packed)); + +/* skip_offset is absolute from start of bytecode */ +struct logical_op { + filter_opcode_t op; + uint16_t skip_offset; /* bytecode insn, if skip second test */ +} __attribute__((packed)); + +struct return_op { + filter_opcode_t op; +} __attribute__((packed)); + +/* + * The reloc table is located at the end of the bytecode. It is made of + * tuples: (uint16_t, var. len. string). It starts at + * reloc_table_offset. + */ +struct filter_bytecode { + uint16_t len; + uint16_t reloc_table_offset; + char data[0]; +}; + +struct filter_bytecode_alloc { + uint16_t alloc_len; + struct filter_bytecode b; +}; + +static inline +unsigned int bytecode_get_len(struct filter_bytecode *bytecode) +{ + return bytecode->len; +} + +#endif /* _FILTER_BYTECODE_H */ diff --git a/src/lib/lttng-ctl/filter-grammar-test.c b/src/lib/lttng-ctl/filter-grammar-test.c new file mode 100644 index 000000000..b47b1e950 --- /dev/null +++ b/src/lib/lttng-ctl/filter-grammar-test.c @@ -0,0 +1,133 @@ +/* + * filter-grammar-test.c + * + * LTTng filter grammar test + * + * Copyright 2012 - Mathieu Desnoyers + * + * This library is free software; you can redistribute it and/or modify it + * under the terms of the GNU Lesser General Public License, version 2.1 only, + * as published by the Free Software Foundation. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public License + * along with this library; if not, write to the Free Software Foundation, + * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA + */ + +#include +#include +#include +#include +#include +#include +#include +#include "filter-parser.h" +#include "filter-ast.h" +#include "filter-bytecode.h" + +int main(int argc, char **argv) +{ + struct filter_parser_ctx *ctx; + int ret; + int print_xml = 0, generate_ir = 0, generate_bytecode = 0; + int i; + + for (i = 1; i < argc; i++) { + if (strcmp(argv[i], "-p") == 0) + print_xml = 1; + else if (strcmp(argv[i], "-i") == 0) + generate_ir = 1; + else if (strcmp(argv[i], "-b") == 0) + generate_bytecode = 1; + else if (strcmp(argv[i], "-d") == 0) + filter_parser_debug = 1; + } + + ctx = filter_parser_ctx_alloc(stdin); + if (!ctx) { + fprintf(stderr, "Error allocating parser\n"); + goto alloc_error; + } + ret = filter_parser_ctx_append_ast(ctx); + if (ret) { + fprintf(stderr, "Parse error\n"); + goto parse_error; + } + ret = filter_visitor_set_parent(ctx); + if (ret) { + fprintf(stderr, "Set parent error\n"); + goto parse_error; + } + if (print_xml) { + ret = filter_visitor_print_xml(ctx, stdout, 0); + if (ret) { + fflush(stdout); + fprintf(stderr, "XML print error\n"); + goto parse_error; + } + } + if (generate_ir) { + printf("Generating IR... "); + fflush(stdout); + ret = filter_visitor_ir_generate(ctx); + if (ret) { + fprintf(stderr, "Generate IR error\n"); + goto parse_error; + } + printf("done\n"); + + printf("Validating IR... "); + fflush(stdout); + ret = filter_visitor_ir_check_binary_op_nesting(ctx); + if (ret) { + goto parse_error; + } + printf("done\n"); + } + if (generate_bytecode) { + printf("Generating bytecode... "); + fflush(stdout); + ret = filter_visitor_bytecode_generate(ctx); + if (ret) { + fprintf(stderr, "Generate bytecode error\n"); + goto parse_error; + } + printf("done\n"); + printf("Size of bytecode generated: %u bytes.\n", + bytecode_get_len(&ctx->bytecode->b)); + } +#if 0 + if (run_bytecode) { + int64_t retval; + + printf("Interpreting bytecode... "); + fflush(stdout); + ret = bytecode_interpret(&ctx->bytecode->b, &retval, NULL); + if (ret) { + fprintf(stderr, "Error interpreting bytecode\n"); + goto parse_error; + } else { + printf("Bytecode interpret result: %" PRIi64 "\n", + retval); + } + printf("done\n"); + } +#endif //0 + + filter_bytecode_free(ctx); + filter_ir_free(ctx); + filter_parser_ctx_free(ctx); + return 0; + +parse_error: + filter_bytecode_free(ctx); + filter_ir_free(ctx); + filter_parser_ctx_free(ctx); +alloc_error: + exit(EXIT_FAILURE); +} diff --git a/src/lib/lttng-ctl/filter-ir.h b/src/lib/lttng-ctl/filter-ir.h new file mode 100644 index 000000000..2ec4cc56f --- /dev/null +++ b/src/lib/lttng-ctl/filter-ir.h @@ -0,0 +1,102 @@ +#ifndef _FILTER_IR_H +#define _FILTER_IR_H + +/* + * filter-ir.h + * + * LTTng filter ir + * + * Copyright 2012 - Mathieu Desnoyers + * + * This library is free software; you can redistribute it and/or modify it + * under the terms of the GNU Lesser General Public License, version 2.1 only, + * as published by the Free Software Foundation. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public License + * along with this library; if not, write to the Free Software Foundation, + * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA + */ + +#include "filter-ast.h" + +enum ir_op_signedness { + IR_SIGN_UNKNOWN = 0, + IR_SIGNED, + IR_UNSIGNED, + IR_SIGN_DYN, /* signedness determined dynamically */ +}; + +enum ir_data_type { + IR_DATA_UNKNOWN = 0, + IR_DATA_STRING, + IR_DATA_NUMERIC, /* numeric and boolean */ + IR_DATA_FIELD_REF, +}; + +enum ir_op_type { + IR_OP_UNKNOWN = 0, + IR_OP_ROOT, + IR_OP_LOAD, + IR_OP_UNARY, + IR_OP_BINARY, + IR_OP_LOGICAL, +}; + +/* left or right child */ +enum ir_side { + IR_SIDE_UNKNOWN = 0, + IR_LEFT, + IR_RIGHT, +}; + +struct ir_op_root { + struct ir_op *child; +}; + +struct ir_op_load { + union { + char *string; + int64_t num; + char *ref; + } u; +}; + +struct ir_op_unary { + enum unary_op_type type; + struct ir_op *child; +}; + +struct ir_op_binary { + enum op_type type; + struct ir_op *left; + struct ir_op *right; +}; + +struct ir_op_logical { + enum op_type type; + struct ir_op *left; + struct ir_op *right; +}; + +struct ir_op { + /* common to all ops */ + enum ir_op_type op; + enum ir_data_type data_type; + enum ir_op_signedness signedness; + enum ir_side side; + + union { + struct ir_op_root root; + struct ir_op_load load; + struct ir_op_unary unary; + struct ir_op_binary binary; + struct ir_op_logical logical; + } u; +}; + +#endif /* _FILTER_IR_H */ diff --git a/src/lib/lttng-ctl/filter-lexer.l b/src/lib/lttng-ctl/filter-lexer.l new file mode 100644 index 000000000..5853b0003 --- /dev/null +++ b/src/lib/lttng-ctl/filter-lexer.l @@ -0,0 +1,118 @@ +%{ +/* + * filter-lexer.l + * + * LTTng filter lexer + * + * Copyright 2012 - Mathieu Desnoyers + * + * This library is free software; you can redistribute it and/or modify it + * under the terms of the GNU Lesser General Public License, version 2.1 only, + * as published by the Free Software Foundation. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + */ + +#include +#include "filter-ast.h" +#include "filter-parser.h" + +extern +void setstring(struct filter_parser_ctx *parser_ctx, YYSTYPE *lvalp, const char *src); + +static void yyunput (int c, register char * yy_bp , yyscan_t yyscanner) + __attribute__((unused)); +static int input (yyscan_t yyscanner) __attribute__((unused)); + +%} + +%x comment_ml comment_sl string_lit char_const +%option reentrant yylineno noyywrap bison-bridge +%option extra-type="struct filter_parser_ctx *" + /* bison-locations */ +INTEGER_SUFFIX [ \n\t]*(U|UL|ULL|LU|LLU|Ul|Ull|lU|llU|u|uL|uLL|Lu|LLu|ul|ull|lu|llu) +DIGIT [0-9] +NONDIGIT [a-zA-Z_] +HEXDIGIT [0-9A-Fa-f] +OCTALDIGIT [0-7] +UCHARLOWERCASE \\u{HEXDIGIT}{4} +UCHARUPPERCASE \\U{HEXDIGIT}{8} +ID_NONDIGIT {NONDIGIT}|{UCHARLOWERCASE}|{UCHARUPPERCASE} +IDENTIFIER {ID_NONDIGIT}({ID_NONDIGIT}|{DIGIT})* +ESCSEQ \\(\'|\"|\?|\\|a|b|f|n|r|t|v|{OCTALDIGIT}{1,3}|u{HEXDIGIT}{4}|U{HEXDIGIT}{8}|x{HEXDIGIT}+) +%% + + /* + * Using start conditions to deal with comments + * and strings. + */ + +"/*" BEGIN(comment_ml); +[^*\n]* /* eat anything that's not a '*' */ +"*"+[^*/\n]* /* eat up '*'s not followed by '/'s */ +\n ++yylineno; +"*"+"/" BEGIN(INITIAL); + +"//" BEGIN(comment_sl); +[^\n]*\n ++yylineno; BEGIN(INITIAL); + +L\' BEGIN(char_const); return CHARACTER_CONSTANT_START; +\' BEGIN(char_const); return CHARACTER_CONSTANT_START; +\' BEGIN(INITIAL); return SQUOTE; + +L\" BEGIN(string_lit); return STRING_LITERAL_START; +\" BEGIN(string_lit); return STRING_LITERAL_START; +\" BEGIN(INITIAL); return DQUOTE; + +ESCSEQ return ESCSEQ; +\n ; /* ignore */ +. setstring(yyextra, yylval, yytext); return CHAR_STRING_TOKEN; + +"[" return LSBRAC; +"]" return RSBRAC; +"(" return LPAREN; +")" return RPAREN; +"{" return LBRAC; +"}" return RBRAC; +"->" return RARROW; + +"*" return STAR; +"+" return PLUS; +"-" return MINUS; + +"%" return MOD_OP; +"/" return DIV_OP; +">>" return RIGHT_OP; +"<<" return LEFT_OP; + +"==" return EQ_OP; +"!=" return NE_OP; +"<=" return LE_OP; +">=" return GE_OP; +"<" return LT_OP; +">" return GT_OP; +"&&" return AND_OP; +"||" return OR_OP; +"!" return NOT_OP; + +":=" return ASSIGN; +":" return COLON; +";" return SEMICOLON; +"..." return DOTDOTDOT; +"." return DOT; +"=" return EQUAL; +"," return COMMA; +"^" return XOR_BIN; +"&" return AND_BIN; +"|" return OR_BIN; +"~" return NOT_BIN; +[1-9]{DIGIT}*{INTEGER_SUFFIX}? setstring(yyextra, yylval, yytext); return DECIMAL_CONSTANT; +0{OCTALDIGIT}*{INTEGER_SUFFIX}? setstring(yyextra, yylval, yytext); return OCTAL_CONSTANT; +0[xX]{HEXDIGIT}+{INTEGER_SUFFIX}? setstring(yyextra, yylval, yytext); return HEXADECIMAL_CONSTANT; +{IDENTIFIER} printf_debug("\n", yytext); setstring(yyextra, yylval, yytext); return IDENTIFIER; +[ \t\n]+ ; /* ignore */ +. return ERROR; +%% diff --git a/src/lib/lttng-ctl/filter-parser.y b/src/lib/lttng-ctl/filter-parser.y new file mode 100644 index 000000000..30c208ab1 --- /dev/null +++ b/src/lib/lttng-ctl/filter-parser.y @@ -0,0 +1,600 @@ +%{ +/* + * filter-parser.y + * + * LTTng filter expression parser + * + * Copyright 2012 - Mathieu Desnoyers + * + * This library is free software; you can redistribute it and/or modify it + * under the terms of the GNU Lesser General Public License, version 2.1 only, + * as published by the Free Software Foundation. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public License + * along with this library; if not, write to the Free Software Foundation, + * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA + * + * Grammar inspired from http://www.quut.com/c/ANSI-C-grammar-y.html + */ + +#include +#include +#include +#include +#include +#include +#include +#include "filter-parser.h" +#include "filter-ast.h" + +int yydebug; +int filter_parser_debug = 0; + +int yyparse(struct filter_parser_ctx *parser_ctx); +int yylex(union YYSTYPE *yyval, struct filter_parser_ctx *parser_ctx); +int yylex_init_extra(struct filter_parser_ctx *parser_ctx, yyscan_t * ptr_yy_globals); +int yylex_destroy(yyscan_t yyparser_ctx); +void yyrestart(FILE * in_str, yyscan_t parser_ctx); + +struct gc_string { + struct cds_list_head gc; + size_t alloclen; + char s[]; +}; + +static const char *node_type_to_str[] = { + [ NODE_UNKNOWN ] = "NODE_UNKNOWN", + [ NODE_ROOT ] = "NODE_ROOT", + [ NODE_EXPRESSION ] = "NODE_EXPRESSION", + [ NODE_OP ] = "NODE_OP", + [ NODE_UNARY_OP ] = "NODE_UNARY_OP", +}; + +const char *node_type(struct filter_node *node) +{ + if (node->type < NR_NODE_TYPES) + return node_type_to_str[node->type]; + else + return NULL; +} + +static struct gc_string *gc_string_alloc(struct filter_parser_ctx *parser_ctx, + size_t len) +{ + struct gc_string *gstr; + size_t alloclen; + + /* TODO: could be faster with find first bit or glib Gstring */ + /* sizeof long to account for malloc header (int or long ?) */ + for (alloclen = 8; alloclen < sizeof(long) + sizeof(*gstr) + len; + alloclen *= 2); + + gstr = malloc(alloclen); + cds_list_add(&gstr->gc, &parser_ctx->allocated_strings); + gstr->alloclen = alloclen; + return gstr; +} + +/* + * note: never use gc_string_append on a string that has external references. + * gsrc will be garbage collected immediately, and gstr might be. + * Should only be used to append characters to a string literal or constant. + */ +struct gc_string *gc_string_append(struct filter_parser_ctx *parser_ctx, + struct gc_string *gstr, + struct gc_string *gsrc) +{ + size_t newlen = strlen(gsrc->s) + strlen(gstr->s) + 1; + size_t alloclen; + + /* TODO: could be faster with find first bit or glib Gstring */ + /* sizeof long to account for malloc header (int or long ?) */ + for (alloclen = 8; alloclen < sizeof(long) + sizeof(*gstr) + newlen; + alloclen *= 2); + + if (alloclen > gstr->alloclen) { + struct gc_string *newgstr; + + newgstr = gc_string_alloc(parser_ctx, newlen); + strcpy(newgstr->s, gstr->s); + strcat(newgstr->s, gsrc->s); + cds_list_del(&gstr->gc); + free(gstr); + gstr = newgstr; + } else { + strcat(gstr->s, gsrc->s); + } + cds_list_del(&gsrc->gc); + free(gsrc); + return gstr; +} + +void setstring(struct filter_parser_ctx *parser_ctx, YYSTYPE *lvalp, const char *src) +{ + lvalp->gs = gc_string_alloc(parser_ctx, strlen(src) + 1); + strcpy(lvalp->gs->s, src); +} + +static struct filter_node *make_node(struct filter_parser_ctx *scanner, + enum node_type type) +{ + struct filter_ast *ast = filter_parser_get_ast(scanner); + struct filter_node *node; + + node = malloc(sizeof(*node)); + if (!node) + return NULL; + memset(node, 0, sizeof(*node)); + node->type = type; + cds_list_add(&node->gc, &ast->allocated_nodes); + + switch (type) { + case NODE_ROOT: + fprintf(stderr, "[error] %s: trying to create root node\n", __func__); + break; + + case NODE_EXPRESSION: + break; + case NODE_OP: + break; + case NODE_UNARY_OP: + break; + + case NODE_UNKNOWN: + default: + fprintf(stderr, "[error] %s: unknown node type %d\n", __func__, + (int) type); + break; + } + + return node; +} + +static struct filter_node *make_op_node(struct filter_parser_ctx *scanner, + enum op_type type, + struct filter_node *lchild, + struct filter_node *rchild) +{ + struct filter_ast *ast = filter_parser_get_ast(scanner); + struct filter_node *node; + + node = malloc(sizeof(*node)); + if (!node) + return NULL; + memset(node, 0, sizeof(*node)); + node->type = NODE_OP; + cds_list_add(&node->gc, &ast->allocated_nodes); + node->u.op.type = type; + node->u.op.lchild = lchild; + node->u.op.rchild = rchild; + return node; +} + +void yyerror(struct filter_parser_ctx *parser_ctx, const char *str) +{ + fprintf(stderr, "error %s\n", str); +} + +int yywrap(void) +{ + return 1; +} + +#define parse_error(parser_ctx, str) \ +do { \ + yyerror(parser_ctx, YY_("parse error: " str "\n")); \ + YYERROR; \ +} while (0) + +static void free_strings(struct cds_list_head *list) +{ + struct gc_string *gstr, *tmp; + + cds_list_for_each_entry_safe(gstr, tmp, list, gc) + free(gstr); +} + +static struct filter_ast *filter_ast_alloc(void) +{ + struct filter_ast *ast; + + ast = malloc(sizeof(*ast)); + if (!ast) + return NULL; + memset(ast, 0, sizeof(*ast)); + CDS_INIT_LIST_HEAD(&ast->allocated_nodes); + ast->root.type = NODE_ROOT; + return ast; +} + +static void filter_ast_free(struct filter_ast *ast) +{ + struct filter_node *node, *tmp; + + cds_list_for_each_entry_safe(node, tmp, &ast->allocated_nodes, gc) + free(node); +} + +int filter_parser_ctx_append_ast(struct filter_parser_ctx *parser_ctx) +{ + return yyparse(parser_ctx); +} + +struct filter_parser_ctx *filter_parser_ctx_alloc(FILE *input) +{ + struct filter_parser_ctx *parser_ctx; + int ret; + + yydebug = filter_parser_debug; + + parser_ctx = malloc(sizeof(*parser_ctx)); + if (!parser_ctx) + return NULL; + memset(parser_ctx, 0, sizeof(*parser_ctx)); + + ret = yylex_init_extra(parser_ctx, &parser_ctx->scanner); + if (ret) { + fprintf(stderr, "yylex_init error\n"); + goto cleanup_parser_ctx; + } + /* Start processing new stream */ + yyrestart(input, parser_ctx->scanner); + + parser_ctx->ast = filter_ast_alloc(); + if (!parser_ctx->ast) + goto cleanup_lexer; + CDS_INIT_LIST_HEAD(&parser_ctx->allocated_strings); + + if (yydebug) + fprintf(stdout, "parser_ctx input is a%s.\n", + isatty(fileno(input)) ? "n interactive tty" : + " noninteractive file"); + + return parser_ctx; + +cleanup_lexer: + ret = yylex_destroy(parser_ctx->scanner); + if (!ret) + fprintf(stderr, "yylex_destroy error\n"); +cleanup_parser_ctx: + free(parser_ctx); + return NULL; +} + +void filter_parser_ctx_free(struct filter_parser_ctx *parser_ctx) +{ + int ret; + + free_strings(&parser_ctx->allocated_strings); + filter_ast_free(parser_ctx->ast); + ret = yylex_destroy(parser_ctx->scanner); + if (ret) + fprintf(stderr, "yylex_destroy error\n"); + free(parser_ctx); +} + +%} + +%define api.pure + /* %locations */ +%parse-param {struct filter_parser_ctx *parser_ctx} +%lex-param {struct filter_parser_ctx *parser_ctx} +%start translation_unit +%token CHARACTER_CONSTANT_START SQUOTE STRING_LITERAL_START DQUOTE +%token ESCSEQ CHAR_STRING_TOKEN +%token DECIMAL_CONSTANT OCTAL_CONSTANT HEXADECIMAL_CONSTANT +%token LSBRAC RSBRAC LPAREN RPAREN LBRAC RBRAC RARROW +%token STAR PLUS MINUS +%token MOD_OP DIV_OP RIGHT_OP LEFT_OP +%token EQ_OP NE_OP LE_OP GE_OP LT_OP GT_OP AND_OP OR_OP NOT_OP +%token ASSIGN COLON SEMICOLON DOTDOTDOT DOT EQUAL COMMA +%token XOR_BIN AND_BIN OR_BIN NOT_BIN + +%token IDENTIFIER +%token ERROR +%union +{ + long long ll; + char c; + struct gc_string *gs; + struct filter_node *n; +} + +%type s_char s_char_sequence c_char c_char_sequence + +%type primary_expression +%type postfix_expression +%type unary_expression +%type unary_operator +%type multiplicative_expression +%type additive_expression +%type shift_expression +%type relational_expression +%type equality_expression +%type and_expression +%type exclusive_or_expression +%type inclusive_or_expression +%type logical_and_expression +%type logical_or_expression +%type expression + +%% + + +/* 1.5 Constants */ + +c_char_sequence: + c_char + { $$ = $1; } + | c_char_sequence c_char + { $$ = gc_string_append(parser_ctx, $1, $2); } + ; + +c_char: + CHAR_STRING_TOKEN + { $$ = yylval.gs; } + | ESCSEQ + { + parse_error(parser_ctx, "escape sequences not supported yet"); + } + ; + +/* 1.6 String literals */ + +s_char_sequence: + s_char + { $$ = $1; } + | s_char_sequence s_char + { $$ = gc_string_append(parser_ctx, $1, $2); } + ; + +s_char: + CHAR_STRING_TOKEN + { $$ = yylval.gs; } + | ESCSEQ + { + parse_error(parser_ctx, "escape sequences not supported yet"); + } + ; + +primary_expression + : IDENTIFIER + { + $$ = make_node(parser_ctx, NODE_EXPRESSION); + $$->u.expression.type = AST_EXP_IDENTIFIER; + $$->u.expression.u.identifier = yylval.gs->s; + } + | DECIMAL_CONSTANT + { + $$ = make_node(parser_ctx, NODE_EXPRESSION); + $$->u.expression.type = AST_EXP_CONSTANT; + sscanf(yylval.gs->s, "%" PRIu64, + &$$->u.expression.u.constant); + } + | OCTAL_CONSTANT + { + $$ = make_node(parser_ctx, NODE_EXPRESSION); + $$->u.expression.type = AST_EXP_CONSTANT; + sscanf(yylval.gs->s, "0%" PRIo64, + &$$->u.expression.u.constant); + } + | HEXADECIMAL_CONSTANT + { + $$ = make_node(parser_ctx, NODE_EXPRESSION); + $$->u.expression.type = AST_EXP_CONSTANT; + sscanf(yylval.gs->s, "0x%" PRIx64, + &$$->u.expression.u.constant); + } + | STRING_LITERAL_START DQUOTE + { + $$ = make_node(parser_ctx, NODE_EXPRESSION); + $$->u.expression.type = AST_EXP_STRING; + $$->u.expression.u.string = ""; + } + | STRING_LITERAL_START s_char_sequence DQUOTE + { + $$ = make_node(parser_ctx, NODE_EXPRESSION); + $$->u.expression.type = AST_EXP_STRING; + $$->u.expression.u.string = $2->s; + } + | CHARACTER_CONSTANT_START c_char_sequence SQUOTE + { + $$ = make_node(parser_ctx, NODE_EXPRESSION); + $$->u.expression.type = AST_EXP_STRING; + $$->u.expression.u.string = $2->s; + } + | LPAREN expression RPAREN + { + $$ = make_node(parser_ctx, NODE_EXPRESSION); + $$->u.expression.type = AST_EXP_NESTED; + $$->u.expression.u.child = $2; + } + ; + +postfix_expression + : primary_expression + { $$ = $1; } + | postfix_expression DOT IDENTIFIER + { + $$ = make_node(parser_ctx, NODE_EXPRESSION); + $$->u.expression.type = AST_EXP_IDENTIFIER; + $$->u.expression.post_op = AST_LINK_DOT; + $$->u.expression.u.identifier = $3->s; + $$->u.expression.prev = $1; + } + | postfix_expression RARROW IDENTIFIER + { + $$ = make_node(parser_ctx, NODE_EXPRESSION); + $$->u.expression.type = AST_EXP_IDENTIFIER; + $$->u.expression.post_op = AST_LINK_RARROW; + $$->u.expression.u.identifier = $3->s; + $$->u.expression.prev = $1; + } + ; + +unary_expression + : postfix_expression + { $$ = $1; } + | unary_operator unary_expression + { + $$ = $1; + $$->u.unary_op.child = $2; + } + ; + +unary_operator + : PLUS + { + $$ = make_node(parser_ctx, NODE_UNARY_OP); + $$->u.unary_op.type = AST_UNARY_PLUS; + } + | MINUS + { + $$ = make_node(parser_ctx, NODE_UNARY_OP); + $$->u.unary_op.type = AST_UNARY_MINUS; + } + | NOT_OP + { + $$ = make_node(parser_ctx, NODE_UNARY_OP); + $$->u.unary_op.type = AST_UNARY_NOT; + } + ; + +multiplicative_expression + : unary_expression + { $$ = $1; } + | multiplicative_expression STAR unary_expression + { + $$ = make_op_node(parser_ctx, AST_OP_MUL, $1, $3); + } + | multiplicative_expression DIV_OP unary_expression + { + $$ = make_op_node(parser_ctx, AST_OP_DIV, $1, $3); + } + | multiplicative_expression MOD_OP unary_expression + { + $$ = make_op_node(parser_ctx, AST_OP_MOD, $1, $3); + } + ; + +additive_expression + : multiplicative_expression + { $$ = $1; } + | additive_expression PLUS multiplicative_expression + { + $$ = make_op_node(parser_ctx, AST_OP_PLUS, $1, $3); + } + | additive_expression MINUS multiplicative_expression + { + $$ = make_op_node(parser_ctx, AST_OP_MINUS, $1, $3); + } + ; + +shift_expression + : additive_expression + { $$ = $1; } + | shift_expression LEFT_OP additive_expression + { + $$ = make_op_node(parser_ctx, AST_OP_LSHIFT, $1, $3); + } + | shift_expression RIGHT_OP additive_expression + { + $$ = make_op_node(parser_ctx, AST_OP_RSHIFT, $1, $3); + } + ; + +relational_expression + : shift_expression + { $$ = $1; } + | relational_expression LT_OP shift_expression + { + $$ = make_op_node(parser_ctx, AST_OP_LT, $1, $3); + } + | relational_expression GT_OP shift_expression + { + $$ = make_op_node(parser_ctx, AST_OP_GT, $1, $3); + } + | relational_expression LE_OP shift_expression + { + $$ = make_op_node(parser_ctx, AST_OP_LE, $1, $3); + } + | relational_expression GE_OP shift_expression + { + $$ = make_op_node(parser_ctx, AST_OP_GE, $1, $3); + } + ; + +equality_expression + : relational_expression + { $$ = $1; } + | equality_expression EQ_OP relational_expression + { + $$ = make_op_node(parser_ctx, AST_OP_EQ, $1, $3); + } + | equality_expression NE_OP relational_expression + { + $$ = make_op_node(parser_ctx, AST_OP_NE, $1, $3); + } + ; + +and_expression + : equality_expression + { $$ = $1; } + | and_expression AND_BIN equality_expression + { + $$ = make_op_node(parser_ctx, AST_OP_BIN_AND, $1, $3); + } + ; + +exclusive_or_expression + : and_expression + { $$ = $1; } + | exclusive_or_expression XOR_BIN and_expression + { + $$ = make_op_node(parser_ctx, AST_OP_BIN_XOR, $1, $3); + } + ; + +inclusive_or_expression + : exclusive_or_expression + { $$ = $1; } + | inclusive_or_expression OR_BIN exclusive_or_expression + { + $$ = make_op_node(parser_ctx, AST_OP_BIN_OR, $1, $3); + } + ; + +logical_and_expression + : inclusive_or_expression + { $$ = $1; } + | logical_and_expression AND_OP inclusive_or_expression + { + $$ = make_op_node(parser_ctx, AST_OP_AND, $1, $3); + } + ; + +logical_or_expression + : logical_and_expression + { $$ = $1; } + | logical_or_expression OR_OP logical_and_expression + { + $$ = make_op_node(parser_ctx, AST_OP_OR, $1, $3); + } + ; + +expression + : logical_or_expression + { $$ = $1; } + ; + +translation_unit + : expression + { + parser_ctx->ast->root.u.root.child = $1; + } + ; diff --git a/src/lib/lttng-ctl/filter-visitor-generate-bytecode.c b/src/lib/lttng-ctl/filter-visitor-generate-bytecode.c new file mode 100644 index 000000000..e940e2c81 --- /dev/null +++ b/src/lib/lttng-ctl/filter-visitor-generate-bytecode.c @@ -0,0 +1,464 @@ +/* + * filter-visitor-generate-bytecode.c + * + * LTTng filter bytecode generation + * + * Copyright 2012 - Mathieu Desnoyers + * + * This library is free software; you can redistribute it and/or modify it + * under the terms of the GNU Lesser General Public License, version 2.1 only, + * as published by the Free Software Foundation. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public License + * along with this library; if not, write to the Free Software Foundation, + * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA + */ + +#include +#include +#include +#include "align.h" +#include "filter-bytecode.h" +#include "filter-ir.h" +#include "filter-ast.h" + +#ifndef max_t +#define max_t(type, a, b) ((type) ((a) > (b) ? (a) : (b))) +#endif + +//#define INIT_ALLOC_SIZE PAGE_SIZE +#define INIT_ALLOC_SIZE 4 + +static +int recursive_visit_gen_bytecode(struct filter_parser_ctx *ctx, + struct ir_op *node); + +static +int bytecode_init(struct filter_bytecode_alloc **fb) +{ + *fb = calloc(sizeof(struct filter_bytecode_alloc) + INIT_ALLOC_SIZE, 1); + if (!*fb) { + return -ENOMEM; + } else { + (*fb)->alloc_len = INIT_ALLOC_SIZE; + return 0; + } +} + +static +int32_t bytecode_reserve(struct filter_bytecode_alloc **fb, uint32_t align, uint32_t len) +{ + int32_t ret; + uint32_t padding = offset_align((*fb)->b.len, align); + + if ((*fb)->b.len + padding + len > (*fb)->alloc_len) { + uint32_t new_len = + max_t(uint32_t, (*fb)->b.len + padding + len, + (*fb)->alloc_len << 1); + uint32_t old_len = (*fb)->alloc_len; + + if (new_len > 0xFFFF) + return -EINVAL; + *fb = realloc(*fb, sizeof(struct filter_bytecode_alloc) + new_len); + if (!*fb) + return -ENOMEM; + memset(&(*fb)->b.data[old_len], 0, new_len - old_len); + (*fb)->alloc_len = new_len; + } + (*fb)->b.len += padding; + ret = (*fb)->b.len; + (*fb)->b.len += len; + return ret; +} + +static +int bytecode_push(struct filter_bytecode_alloc **fb, const void *data, + uint32_t align, uint32_t len) +{ + int32_t offset; + + offset = bytecode_reserve(fb, align, len); + if (offset < 0) + return offset; + memcpy(&(*fb)->b.data[offset], data, len); + return 0; +} + +static +int bytecode_push_logical(struct filter_bytecode_alloc **fb, + struct logical_op *data, + uint32_t align, uint32_t len, + uint16_t *skip_offset) +{ + int32_t offset; + + offset = bytecode_reserve(fb, align, len); + if (offset < 0) + return offset; + memcpy(&(*fb)->b.data[offset], data, len); + *skip_offset = + (void *) &((struct logical_op *) &(*fb)->b.data[offset])->skip_offset + - (void *) &(*fb)->b.data[0]; + return 0; +} + +static +int bytecode_patch(struct filter_bytecode_alloc **fb, + const void *data, + uint16_t offset, + uint32_t len) +{ + if (offset >= (*fb)->b.len) { + return -EINVAL; + } + memcpy(&(*fb)->b.data[offset], data, len); + return 0; +} + +static +int visit_node_root(struct filter_parser_ctx *ctx, struct ir_op *node) +{ + int ret; + struct return_op insn; + + /* Visit child */ + ret = recursive_visit_gen_bytecode(ctx, node->u.root.child); + if (ret) + return ret; + + /* Generate end of bytecode instruction */ + insn.op = FILTER_OP_RETURN; + return bytecode_push(&ctx->bytecode, &insn, 1, sizeof(insn)); +} + +static +enum filter_register reg_sel(struct ir_op *node) +{ + switch (node->side) { + case IR_SIDE_UNKNOWN: + default: + fprintf(stderr, "[error] Unknown node side in %s\n", + __func__); + return REG_ERROR; + case IR_LEFT: + return REG_R0; + case IR_RIGHT: + return REG_R1; + } +} + +static +int visit_node_load(struct filter_parser_ctx *ctx, struct ir_op *node) +{ + int ret; + + switch (node->data_type) { + case IR_DATA_UNKNOWN: + default: + fprintf(stderr, "[error] Unknown data type in %s\n", + __func__); + return -EINVAL; + + case IR_DATA_STRING: + { + struct load_op *insn; + uint32_t insn_len = sizeof(struct load_op) + + strlen(node->u.load.u.string) + 1; + + insn = calloc(insn_len, 1); + if (!insn) + return -ENOMEM; + insn->op = FILTER_OP_LOAD_STRING; + insn->reg = reg_sel(node); + if (insn->reg == REG_ERROR) + return -EINVAL; + strcpy(insn->data, node->u.load.u.string); + ret = bytecode_push(&ctx->bytecode, insn, 1, insn_len); + free(insn); + return ret; + } + case IR_DATA_NUMERIC: + { + struct load_op *insn; + uint32_t insn_len = sizeof(struct load_op) + + sizeof(struct literal_numeric); + + insn = calloc(insn_len, 1); + if (!insn) + return -ENOMEM; + insn->op = FILTER_OP_LOAD_S64; + insn->reg = reg_sel(node); + if (insn->reg == REG_ERROR) + return -EINVAL; + *(int64_t *) insn->data = node->u.load.u.num; + ret = bytecode_push(&ctx->bytecode, insn, 1, insn_len); + free(insn); + return ret; + } + case IR_DATA_FIELD_REF: + { + struct load_op *insn; + uint32_t insn_len = sizeof(struct load_op) + + sizeof(struct field_ref); + struct field_ref ref_offset; + uint16_t reloc_offset; + + insn = calloc(insn_len, 1); + if (!insn) + return -ENOMEM; + insn->op = FILTER_OP_LOAD_FIELD_REF; + insn->reg = reg_sel(node); + ref_offset.offset = (uint16_t) -1U; + memcpy(insn->data, &ref_offset, sizeof(ref_offset)); + if (insn->reg == REG_ERROR) + return -EINVAL; + /* reloc_offset points to struct field_ref */ + reloc_offset = bytecode_get_len(&ctx->bytecode->b); + reloc_offset += sizeof(struct load_op); + ret = bytecode_push(&ctx->bytecode, insn, 1, insn_len); + if (ret) { + free(insn); + return ret; + } + /* append reloc */ + ret = bytecode_push(&ctx->bytecode_reloc, &reloc_offset, + 1, sizeof(reloc_offset)); + if (ret) { + free(insn); + return ret; + } + ret = bytecode_push(&ctx->bytecode_reloc, node->u.load.u.ref, + 1, strlen(node->u.load.u.ref) + 1); + free(insn); + return ret; + } + } +} + +static +int visit_node_unary(struct filter_parser_ctx *ctx, struct ir_op *node) +{ + int ret; + struct unary_op insn; + + /* Visit child */ + ret = recursive_visit_gen_bytecode(ctx, node->u.unary.child); + if (ret) + return ret; + + /* Generate end of bytecode instruction */ + switch (node->u.unary.type) { + case AST_UNARY_UNKNOWN: + default: + fprintf(stderr, "[error] Unknown unary node type in %s\n", + __func__); + return -EINVAL; + case AST_UNARY_PLUS: + /* Nothing to do. */ + return 0; + case AST_UNARY_MINUS: + insn.op = FILTER_OP_UNARY_MINUS; + insn.reg = reg_sel(node); + if (insn.reg == REG_ERROR) + return -EINVAL; + return bytecode_push(&ctx->bytecode, &insn, 1, sizeof(insn)); + case AST_UNARY_NOT: + insn.op = FILTER_OP_UNARY_NOT; + insn.reg = reg_sel(node); + if (insn.reg == REG_ERROR) + return -EINVAL; + return bytecode_push(&ctx->bytecode, &insn, 1, sizeof(insn)); + } +} + +/* + * Binary comparator nesting is disallowed. This allows fitting into + * only 2 registers. + */ +static +int visit_node_binary(struct filter_parser_ctx *ctx, struct ir_op *node) +{ + int ret; + struct binary_op insn; + + /* Visit child */ + ret = recursive_visit_gen_bytecode(ctx, node->u.binary.left); + if (ret) + return ret; + ret = recursive_visit_gen_bytecode(ctx, node->u.binary.right); + if (ret) + return ret; + + switch (node->u.binary.type) { + case AST_OP_UNKNOWN: + default: + fprintf(stderr, "[error] Unknown unary node type in %s\n", + __func__); + return -EINVAL; + + case AST_OP_AND: + case AST_OP_OR: + fprintf(stderr, "[error] Unexpected logical node type in %s\n", + __func__); + return -EINVAL; + + case AST_OP_MUL: + insn.op = FILTER_OP_MUL; + break; + case AST_OP_DIV: + insn.op = FILTER_OP_DIV; + break; + case AST_OP_MOD: + insn.op = FILTER_OP_MOD; + break; + case AST_OP_PLUS: + insn.op = FILTER_OP_PLUS; + break; + case AST_OP_MINUS: + insn.op = FILTER_OP_MINUS; + break; + case AST_OP_RSHIFT: + insn.op = FILTER_OP_RSHIFT; + break; + case AST_OP_LSHIFT: + insn.op = FILTER_OP_LSHIFT; + break; + case AST_OP_BIN_AND: + insn.op = FILTER_OP_BIN_AND; + break; + case AST_OP_BIN_OR: + insn.op = FILTER_OP_BIN_OR; + break; + case AST_OP_BIN_XOR: + insn.op = FILTER_OP_BIN_XOR; + break; + + case AST_OP_EQ: + insn.op = FILTER_OP_EQ; + break; + case AST_OP_NE: + insn.op = FILTER_OP_NE; + break; + case AST_OP_GT: + insn.op = FILTER_OP_GT; + break; + case AST_OP_LT: + insn.op = FILTER_OP_LT; + break; + case AST_OP_GE: + insn.op = FILTER_OP_GE; + break; + case AST_OP_LE: + insn.op = FILTER_OP_LE; + break; + } + return bytecode_push(&ctx->bytecode, &insn, 1, sizeof(insn)); +} + +static +int visit_node_logical(struct filter_parser_ctx *ctx, struct ir_op *node) +{ + int ret; + struct logical_op insn; + uint16_t skip_offset_loc; + uint16_t target_loc; + + /* Visit left child */ + ret = recursive_visit_gen_bytecode(ctx, node->u.binary.left); + if (ret) + return ret; + switch (node->u.logical.type) { + default: + fprintf(stderr, "[error] Unknown node type in %s\n", + __func__); + return -EINVAL; + + case AST_OP_AND: + insn.op = FILTER_OP_AND; + break; + case AST_OP_OR: + insn.op = FILTER_OP_OR; + break; + } + insn.skip_offset = (uint16_t) -1UL; /* Temporary */ + ret = bytecode_push_logical(&ctx->bytecode, &insn, 1, sizeof(insn), + &skip_offset_loc); + if (ret) + return ret; + /* Visit right child */ + ret = recursive_visit_gen_bytecode(ctx, node->u.binary.right); + if (ret) + return ret; + /* We now know where the logical op can skip. */ + target_loc = (uint16_t) bytecode_get_len(&ctx->bytecode->b); + ret = bytecode_patch(&ctx->bytecode, + &target_loc, /* Offset to jump to */ + skip_offset_loc, /* Where to patch */ + sizeof(uint16_t)); + return ret; +} + +/* + * Postorder traversal of the tree. We need the children result before + * we can evaluate the parent. + */ +static +int recursive_visit_gen_bytecode(struct filter_parser_ctx *ctx, + struct ir_op *node) +{ + switch (node->op) { + case IR_OP_UNKNOWN: + default: + fprintf(stderr, "[error] Unknown node type in %s\n", + __func__); + return -EINVAL; + + case IR_OP_ROOT: + return visit_node_root(ctx, node); + case IR_OP_LOAD: + return visit_node_load(ctx, node); + case IR_OP_UNARY: + return visit_node_unary(ctx, node); + case IR_OP_BINARY: + return visit_node_binary(ctx, node); + case IR_OP_LOGICAL: + return visit_node_logical(ctx, node); + } +} + +void filter_bytecode_free(struct filter_parser_ctx *ctx) +{ + free(ctx->bytecode); + ctx->bytecode = NULL; + free(ctx->bytecode_reloc); + ctx->bytecode_reloc = NULL; +} + +int filter_visitor_bytecode_generate(struct filter_parser_ctx *ctx) +{ + int ret; + + ret = bytecode_init(&ctx->bytecode); + if (ret) + return ret; + ret = bytecode_init(&ctx->bytecode_reloc); + if (ret) + goto error; + ret = recursive_visit_gen_bytecode(ctx, ctx->ir_root); + if (ret) + goto error; + + /* Finally, append symbol table to bytecode */ + ctx->bytecode->b.reloc_table_offset = bytecode_get_len(&ctx->bytecode->b); + return bytecode_push(&ctx->bytecode, ctx->bytecode_reloc->b.data, + 1, bytecode_get_len(&ctx->bytecode_reloc->b)); + +error: + filter_bytecode_free(ctx); + return ret; +} diff --git a/src/lib/lttng-ctl/filter-visitor-generate-ir.c b/src/lib/lttng-ctl/filter-visitor-generate-ir.c new file mode 100644 index 000000000..9d44b2349 --- /dev/null +++ b/src/lib/lttng-ctl/filter-visitor-generate-ir.c @@ -0,0 +1,742 @@ +/* + * filter-visitor-generate-ir.c + * + * LTTng filter generate intermediate representation + * + * Copyright 2012 - Mathieu Desnoyers + * + * This library is free software; you can redistribute it and/or modify it + * under the terms of the GNU Lesser General Public License, version 2.1 only, + * as published by the Free Software Foundation. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public License + * along with this library; if not, write to the Free Software Foundation, + * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA + */ + +#include +#include +#include +#include +#include +#include +#include +#include "filter-parser.h" +#include "filter-ast.h" +#include "filter-ir.h" + +static +struct ir_op *generate_ir_recursive(struct filter_parser_ctx *ctx, + struct filter_node *node, enum ir_side side); + +static +struct ir_op *make_op_root(struct ir_op *child, enum ir_side side) +{ + struct ir_op *op; + + op = calloc(sizeof(struct ir_op), 1); + if (!op) + return NULL; + switch (child->data_type) { + case IR_DATA_UNKNOWN: + default: + fprintf(stderr, "[error] Unknown root child data type\n"); + return NULL; + case IR_DATA_STRING: + fprintf(stderr, "[error] String cannot be root data type\n"); + return NULL; + case IR_DATA_NUMERIC: + case IR_DATA_FIELD_REF: + /* ok */ + break; + } + op->op = IR_OP_ROOT; + op->side = side; + op->data_type = child->data_type; + op->signedness = child->signedness; + op->u.root.child = child; + return op; +} + +static +struct ir_op *make_op_load_string(char *string, enum ir_side side) +{ + struct ir_op *op; + + op = calloc(sizeof(struct ir_op), 1); + if (!op) + return NULL; + op->op = IR_OP_LOAD; + op->data_type = IR_DATA_STRING; + op->signedness = IR_SIGN_UNKNOWN; + op->side = side; + op->u.load.u.string = strdup(string); + if (!op->u.load.u.string) { + free(op); + return NULL; + } + return op; +} + +static +struct ir_op *make_op_load_numeric(int64_t v, enum ir_side side) +{ + struct ir_op *op; + + op = calloc(sizeof(struct ir_op), 1); + if (!op) + return NULL; + op->op = IR_OP_LOAD; + op->data_type = IR_DATA_NUMERIC; + /* TODO: for now, all numeric values are signed */ + op->signedness = IR_SIGNED; + op->side = side; + op->u.load.u.num = v; + return op; +} + +static +struct ir_op *make_op_load_field_ref(char *string, enum ir_side side) +{ + struct ir_op *op; + + op = calloc(sizeof(struct ir_op), 1); + if (!op) + return NULL; + op->op = IR_OP_LOAD; + op->data_type = IR_DATA_FIELD_REF; + op->signedness = IR_SIGN_DYN; + op->side = side; + op->u.load.u.ref = strdup(string); + if (!op->u.load.u.ref) { + free(op); + return NULL; + } + return op; +} + +static +struct ir_op *make_op_unary(enum unary_op_type unary_op_type, + const char *op_str, enum ir_op_signedness signedness, + struct ir_op *child, enum ir_side side) +{ + struct ir_op *op = NULL; + + if (child->data_type == IR_DATA_STRING) { + fprintf(stderr, "[error] unary operation '%s' not allowed on string literal\n", op_str); + goto error; + } + + op = calloc(sizeof(struct ir_op), 1); + if (!op) + return NULL; + op->op = IR_OP_UNARY; + op->data_type = child->data_type; + op->signedness = signedness; + op->side = side; + op->u.unary.type = unary_op_type; + op->u.unary.child = child; + return op; + +error: + free(op); + return NULL; +} + +/* + * unary + is pretty much useless. + */ +static +struct ir_op *make_op_unary_plus(struct ir_op *child, enum ir_side side) +{ + return make_op_unary(AST_UNARY_PLUS, "+", child->signedness, + child, side); +} + +static +struct ir_op *make_op_unary_minus(struct ir_op *child, enum ir_side side) +{ + return make_op_unary(AST_UNARY_MINUS, "-", child->signedness, + child, side); +} + +static +struct ir_op *make_op_unary_not(struct ir_op *child, enum ir_side side) +{ + return make_op_unary(AST_UNARY_NOT, "!", child->signedness, + child, side); +} + +#if 0 +static +struct ir_op *make_op_binary_numeric(enum op_type bin_op_type, + const char *op_str, struct ir_op *left, struct ir_op *right, + enum ir_side side) +{ + struct ir_op *op = NULL; + + if (right->data_type == IR_DATA_STRING + || right->data_type == IR_DATA_STRING) { + fprintf(stderr, "[error] binary operation '%s' not allowed on string literal\n", op_str); + goto error; + } + if (left->data_type == IR_DATA_UNKNOWN + || right->data_type == IR_DATA_UNKNOWN) { + fprintf(stderr, "[error] binary operation '%s' has unknown type for both children\n", op_str); + goto error; + + } + + op = calloc(sizeof(struct ir_op_binary), 1); + if (!op) + return NULL; + op->op = IR_OP_BINARY; + op->u.binary.type = bin_op_type; + op->u.binary.left = left; + op->u.binary.right = right; + op->side = side; + + /* + * The field that is not a field ref will select type. + */ + if (left->data_type != IR_DATA_FIELD_REF) + op->data_type = left->data_type; + else + op->data_type = right->data_type; + + if (left->signedness == IR_SIGNED + || right->signedness == IR_SIGNED) { + op->signedness = IR_SIGNED; + } else if (left->signedness == IR_SIGN_DYN + || right->signedness == IR_SIGN_DYN) { + op->signedness = IR_SIGN_DYN; + } else if (left->signedness == IR_UNSIGNED + && right->signedness == IR_UNSIGNED) { + op->signedness = IR_UNSIGNED; + } else { + op->signedness = IR_SIGN_UNKNOWN; + } + + return op; + +error: + free(op); + return NULL; +} + +static +struct ir_op *make_op_binary_mul(struct ir_op *left, struct ir_op *right, + enum ir_side side) +{ + return make_op_binary_numeric(AST_OP_MUL, "*", left, right, side); +} + +static +struct ir_op *make_op_binary_div(struct ir_op *left, struct ir_op *right, + enum ir_side side) +{ + return make_op_binary_numeric(AST_OP_DIV, "/", left, right, side); +} + +static +struct ir_op *make_op_binary_mod(struct ir_op *left, struct ir_op *right, + enum ir_side side) +{ + return make_op_binary_numeric(AST_OP_MOD, "%", left, right, side); +} + +static +struct ir_op *make_op_binary_plus(struct ir_op *left, struct ir_op *right, + enum ir_side side) +{ + return make_op_binary_numeric(AST_OP_PLUS, "+", left, right, side); +} + +static +struct ir_op *make_op_binary_minus(struct ir_op *left, struct ir_op *right, + enum ir_side side) +{ + return make_op_binary_numeric(AST_OP_MINUS, "-", left, right, side); +} + +static +struct ir_op *make_op_binary_rshift(struct ir_op *left, struct ir_op *right, + enum ir_side side) +{ + return make_op_binary_numeric(AST_OP_RSHIFT, ">>", left, right, side); +} + +static +struct ir_op *make_op_binary_lshift(struct ir_op *left, struct ir_op *right, + enum ir_side side) +{ + return make_op_binary_numeric(AST_OP_LSHIFT, "<<", left, right, side); +} + +static +struct ir_op *make_op_binary_and(struct ir_op *left, struct ir_op *right, + enum ir_side side) +{ + return make_op_binary_numeric(AST_OP_BIN_AND, "&", left, right, side); +} + +static +struct ir_op *make_op_binary_or(struct ir_op *left, struct ir_op *right, + enum ir_side side) +{ + return make_op_binary_numeric(AST_OP_BIN_OR, "|", left, right, side); +} + +static +struct ir_op *make_op_binary_xor(struct ir_op *left, struct ir_op *right, + enum ir_side side) +{ + return make_op_binary_numeric(AST_OP_BIN_XOR, "^", left, right, side); +} +#endif //0 + +static +struct ir_op *make_op_binary_compare(enum op_type bin_op_type, + const char *op_str, struct ir_op *left, struct ir_op *right, + enum ir_side side) +{ + struct ir_op *op = NULL; + + if (left->data_type == IR_DATA_UNKNOWN + || right->data_type == IR_DATA_UNKNOWN) { + fprintf(stderr, "[error] binary operation '%s' has unknown operand type\n", op_str); + goto error; + + } + if ((left->data_type == IR_DATA_STRING + && right->data_type == IR_DATA_NUMERIC) + || (left->data_type == IR_DATA_NUMERIC && + right->data_type == IR_DATA_STRING)) { + fprintf(stderr, "[error] binary operation '%s' operand type mismatch\n", op_str); + goto error; + } + + op = calloc(sizeof(struct ir_op), 1); + if (!op) + return NULL; + op->op = IR_OP_BINARY; + op->u.binary.type = bin_op_type; + op->u.binary.left = left; + op->u.binary.right = right; + + /* we return a boolean, represented as signed numeric */ + op->data_type = IR_DATA_NUMERIC; + op->signedness = IR_SIGNED; + op->side = side; + + return op; + +error: + free(op); + return NULL; +} + +static +struct ir_op *make_op_binary_eq(struct ir_op *left, struct ir_op *right, + enum ir_side side) +{ + return make_op_binary_compare(AST_OP_EQ, "==", left, right, side); +} + +static +struct ir_op *make_op_binary_ne(struct ir_op *left, struct ir_op *right, + enum ir_side side) +{ + return make_op_binary_compare(AST_OP_NE, "!=", left, right, side); +} + +static +struct ir_op *make_op_binary_gt(struct ir_op *left, struct ir_op *right, + enum ir_side side) +{ + return make_op_binary_compare(AST_OP_GT, ">", left, right, side); +} + +static +struct ir_op *make_op_binary_lt(struct ir_op *left, struct ir_op *right, + enum ir_side side) +{ + return make_op_binary_compare(AST_OP_LT, "<", left, right, side); +} + +static +struct ir_op *make_op_binary_ge(struct ir_op *left, struct ir_op *right, + enum ir_side side) +{ + return make_op_binary_compare(AST_OP_GE, ">=", left, right, side); +} + +static +struct ir_op *make_op_binary_le(struct ir_op *left, struct ir_op *right, + enum ir_side side) +{ + return make_op_binary_compare(AST_OP_LE, "<=", left, right, side); +} + +static +struct ir_op *make_op_binary_logical(enum op_type bin_op_type, + const char *op_str, struct ir_op *left, struct ir_op *right, + enum ir_side side) +{ + struct ir_op *op = NULL; + + if (left->data_type == IR_DATA_UNKNOWN + || right->data_type == IR_DATA_UNKNOWN) { + fprintf(stderr, "[error] binary operation '%s' has unknown operand type\n", op_str); + goto error; + + } + if (left->data_type == IR_DATA_STRING + || right->data_type == IR_DATA_STRING) { + fprintf(stderr, "[error] logical binary operation '%s' cannot have string operand\n", op_str); + goto error; + } + + op = calloc(sizeof(struct ir_op), 1); + if (!op) + return NULL; + op->op = IR_OP_LOGICAL; + op->u.binary.type = bin_op_type; + op->u.binary.left = left; + op->u.binary.right = right; + + /* we return a boolean, represented as signed numeric */ + op->data_type = IR_DATA_NUMERIC; + op->signedness = IR_SIGNED; + op->side = side; + + return op; + +error: + free(op); + return NULL; +} + +static +struct ir_op *make_op_binary_logical_and(struct ir_op *left, struct ir_op *right, + enum ir_side side) +{ + return make_op_binary_logical(AST_OP_AND, "&&", left, right, side); +} + +static +struct ir_op *make_op_binary_logical_or(struct ir_op *left, struct ir_op *right, + enum ir_side side) +{ + return make_op_binary_logical(AST_OP_OR, "||", left, right, side); +} + +static +void filter_free_ir_recursive(struct ir_op *op) +{ + if (!op) + return; + switch (op->op) { + case IR_OP_UNKNOWN: + default: + fprintf(stderr, "[error] Unknown op type in %s\n", + __func__); + break; + case IR_OP_ROOT: + filter_free_ir_recursive(op->u.root.child); + break; + case IR_OP_LOAD: + switch (op->data_type) { + case IR_DATA_STRING: + free(op->u.load.u.string); + break; + case IR_DATA_FIELD_REF: + free(op->u.load.u.ref); + break; + default: + break; + } + break; + case IR_OP_UNARY: + filter_free_ir_recursive(op->u.unary.child); + break; + case IR_OP_BINARY: + filter_free_ir_recursive(op->u.binary.left); + filter_free_ir_recursive(op->u.binary.right); + break; + case IR_OP_LOGICAL: + filter_free_ir_recursive(op->u.logical.left); + filter_free_ir_recursive(op->u.logical.right); + break; + } + free(op); +} + +static +struct ir_op *make_expression(struct filter_parser_ctx *ctx, + struct filter_node *node, enum ir_side side) +{ + switch (node->u.expression.type) { + case AST_EXP_UNKNOWN: + default: + fprintf(stderr, "[error] %s: unknown expression type\n", __func__); + return NULL; + + case AST_EXP_STRING: + return make_op_load_string(node->u.expression.u.string, side); + case AST_EXP_CONSTANT: + return make_op_load_numeric(node->u.expression.u.constant, + side); + case AST_EXP_IDENTIFIER: + if (node->u.expression.pre_op != AST_LINK_UNKNOWN) { + fprintf(stderr, "[error] %s: dotted and dereferenced identifiers not supported\n", __func__); + return NULL; + } + return make_op_load_field_ref(node->u.expression.u.identifier, + side); + case AST_EXP_NESTED: + return generate_ir_recursive(ctx, node->u.expression.u.child, + side); + } +} + +static +struct ir_op *make_op(struct filter_parser_ctx *ctx, + struct filter_node *node, enum ir_side side) +{ + struct ir_op *op = NULL, *lchild, *rchild; + const char *op_str = "?"; + + switch (node->u.op.type) { + case AST_OP_UNKNOWN: + default: + fprintf(stderr, "[error] %s: unknown binary op type\n", __func__); + return NULL; + + /* + * Binary operators other than comparators and logical and/or + * are not supported. If we ever want to support those, we will + * need a stack for the general case rather than just 2 + * registers (see bytecode). + */ + case AST_OP_MUL: + op_str = "*"; + goto error_not_supported; + case AST_OP_DIV: + op_str = "/"; + goto error_not_supported; + case AST_OP_MOD: + op_str = "%"; + goto error_not_supported; + case AST_OP_PLUS: + op_str = "+"; + goto error_not_supported; + case AST_OP_MINUS: + op_str = "-"; + goto error_not_supported; + case AST_OP_RSHIFT: + op_str = ">>"; + goto error_not_supported; + case AST_OP_LSHIFT: + op_str = "<<"; + goto error_not_supported; + case AST_OP_BIN_AND: + op_str = "&"; + goto error_not_supported; + case AST_OP_BIN_OR: + op_str = "|"; + goto error_not_supported; + case AST_OP_BIN_XOR: + op_str = "^"; + goto error_not_supported; + + case AST_OP_EQ: + case AST_OP_NE: + case AST_OP_GT: + case AST_OP_LT: + case AST_OP_GE: + case AST_OP_LE: + lchild = generate_ir_recursive(ctx, node->u.op.lchild, IR_LEFT); + if (!lchild) + return NULL; + rchild = generate_ir_recursive(ctx, node->u.op.rchild, IR_RIGHT); + if (!rchild) { + filter_free_ir_recursive(lchild); + return NULL; + } + break; + + case AST_OP_AND: + case AST_OP_OR: + /* + * Both children considered as left, since we need to + * populate R0. + */ + lchild = generate_ir_recursive(ctx, node->u.op.lchild, IR_LEFT); + if (!lchild) + return NULL; + rchild = generate_ir_recursive(ctx, node->u.op.rchild, IR_LEFT); + if (!rchild) { + filter_free_ir_recursive(lchild); + return NULL; + } + break; + } + + switch (node->u.op.type) { + case AST_OP_AND: + op = make_op_binary_logical_and(lchild, rchild, side); + break; + case AST_OP_OR: + op = make_op_binary_logical_or(lchild, rchild, side); + break; + case AST_OP_EQ: + op = make_op_binary_eq(lchild, rchild, side); + break; + case AST_OP_NE: + op = make_op_binary_ne(lchild, rchild, side); + break; + case AST_OP_GT: + op = make_op_binary_gt(lchild, rchild, side); + break; + case AST_OP_LT: + op = make_op_binary_lt(lchild, rchild, side); + break; + case AST_OP_GE: + op = make_op_binary_ge(lchild, rchild, side); + break; + case AST_OP_LE: + op = make_op_binary_le(lchild, rchild, side); + break; + default: + break; + } + + if (!op) { + filter_free_ir_recursive(rchild); + filter_free_ir_recursive(lchild); + } + return op; + +error_not_supported: + fprintf(stderr, "[error] %s: binary operation '%s' not supported\n", + __func__, op_str); + return NULL; +} + +static +struct ir_op *make_unary_op(struct filter_parser_ctx *ctx, + struct filter_node *node, enum ir_side side) +{ + switch (node->u.unary_op.type) { + case AST_UNARY_UNKNOWN: + default: + fprintf(stderr, "[error] %s: unknown unary op type\n", __func__); + return NULL; + + case AST_UNARY_PLUS: + { + struct ir_op *op, *child; + + child = generate_ir_recursive(ctx, node->u.unary_op.child, + side); + if (!child) + return NULL; + op = make_op_unary_plus(child, side); + if (!op) { + filter_free_ir_recursive(child); + return NULL; + } + return op; + } + case AST_UNARY_MINUS: + { + struct ir_op *op, *child; + + child = generate_ir_recursive(ctx, node->u.unary_op.child, + side); + if (!child) + return NULL; + op = make_op_unary_minus(child, side); + if (!op) { + filter_free_ir_recursive(child); + return NULL; + } + return op; + } + case AST_UNARY_NOT: + { + struct ir_op *op, *child; + + child = generate_ir_recursive(ctx, node->u.unary_op.child, + side); + if (!child) + return NULL; + op = make_op_unary_not(child, side); + if (!op) { + filter_free_ir_recursive(child); + return NULL; + } + return op; + } + } +} + +static +struct ir_op *generate_ir_recursive(struct filter_parser_ctx *ctx, + struct filter_node *node, enum ir_side side) +{ + switch (node->type) { + case NODE_UNKNOWN: + default: + fprintf(stderr, "[error] %s: unknown node type\n", __func__); + return NULL; + + case NODE_ROOT: + { + struct ir_op *op, *child; + + child = generate_ir_recursive(ctx, node->u.root.child, + side); + if (!child) + return NULL; + op = make_op_root(child, side); + if (!op) { + filter_free_ir_recursive(child); + return NULL; + } + return op; + } + case NODE_EXPRESSION: + return make_expression(ctx, node, side); + case NODE_OP: + return make_op(ctx, node, side); + case NODE_UNARY_OP: + return make_unary_op(ctx, node, side); + } + return 0; +} + + +void filter_ir_free(struct filter_parser_ctx *ctx) +{ + filter_free_ir_recursive(ctx->ir_root); + ctx->ir_root = NULL; +} + +int filter_visitor_ir_generate(struct filter_parser_ctx *ctx) +{ + struct ir_op *op; + + op = generate_ir_recursive(ctx, &ctx->ast->root, IR_LEFT); + if (!op) { + return -EINVAL; + } + ctx->ir_root = op; + return 0; +} diff --git a/src/lib/lttng-ctl/filter-visitor-ir-check-binary-comparator.c b/src/lib/lttng-ctl/filter-visitor-ir-check-binary-comparator.c new file mode 100644 index 000000000..fff9b5168 --- /dev/null +++ b/src/lib/lttng-ctl/filter-visitor-ir-check-binary-comparator.c @@ -0,0 +1,82 @@ +/* + * filter-visitor-ir-check-binary-comparator.c + * + * LTTng filter IR check binary comparator + * + * Copyright 2012 - Mathieu Desnoyers + * + * This library is free software; you can redistribute it and/or modify it + * under the terms of the GNU Lesser General Public License, version 2.1 only, + * as published by the Free Software Foundation. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public License + * along with this library; if not, write to the Free Software Foundation, + * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA + */ + +#include +#include +#include +#include +#include +#include +#include +#include "filter-parser.h" +#include "filter-ast.h" +#include "filter-ir.h" + +static +int check_bin_comparator(struct ir_op *node) +{ + switch (node->op) { + case IR_OP_UNKNOWN: + default: + fprintf(stderr, "[error] %s: unknown op type\n", __func__); + return -EINVAL; + + case IR_OP_ROOT: + return check_bin_comparator(node->u.root.child); + case IR_OP_LOAD: + return 0; + case IR_OP_UNARY: + return check_bin_comparator(node->u.unary.child); + case IR_OP_BINARY: + { + int ret; + + if (node->u.binary.left->data_type == IR_DATA_STRING + || node->u.binary.right->data_type + == IR_DATA_STRING) { + if (node->u.binary.type != AST_OP_EQ + && node->u.binary.type != AST_OP_NE) { + fprintf(stderr, "[error] Only '==' and '!=' comparators are allowed for strings\n"); + return -EINVAL; + } + } + + ret = check_bin_comparator(node->u.binary.left); + if (ret) + return ret; + return check_bin_comparator(node->u.binary.right); + } + case IR_OP_LOGICAL: + { + int ret; + + ret = check_bin_comparator(node->u.logical.left); + if (ret) + return ret; + return check_bin_comparator(node->u.logical.right); + } + } +} + +int filter_visitor_ir_check_binary_comparator(struct filter_parser_ctx *ctx) +{ + return check_bin_comparator(ctx->ir_root); +} diff --git a/src/lib/lttng-ctl/filter-visitor-ir-check-binary-op-nesting.c b/src/lib/lttng-ctl/filter-visitor-ir-check-binary-op-nesting.c new file mode 100644 index 000000000..64048a584 --- /dev/null +++ b/src/lib/lttng-ctl/filter-visitor-ir-check-binary-op-nesting.c @@ -0,0 +1,82 @@ +/* + * filter-visitor-ir-check-binary-op-nesting.c + * + * LTTng filter IR check binary op nesting + * + * Copyright 2012 - Mathieu Desnoyers + * + * This library is free software; you can redistribute it and/or modify it + * under the terms of the GNU Lesser General Public License, version 2.1 only, + * as published by the Free Software Foundation. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public License + * along with this library; if not, write to the Free Software Foundation, + * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA + */ + +#include +#include +#include +#include +#include +#include +#include +#include "filter-parser.h" +#include "filter-ast.h" +#include "filter-ir.h" + +static +int check_bin_op_nesting_recursive(struct ir_op *node, int nesting) +{ + switch (node->op) { + case IR_OP_UNKNOWN: + default: + fprintf(stderr, "[error] %s: unknown op type\n", __func__); + return -EINVAL; + + case IR_OP_ROOT: + return check_bin_op_nesting_recursive(node->u.root.child, + nesting); + case IR_OP_LOAD: + return 0; + case IR_OP_UNARY: + return check_bin_op_nesting_recursive(node->u.unary.child, + nesting); + case IR_OP_BINARY: + { + int ret; + + if (nesting > 0) { + fprintf(stderr, "[error] Nesting of binary operators is not allowed, except for logical operators.\n"); + return -EINVAL; + } + ret = check_bin_op_nesting_recursive(node->u.binary.left, + nesting++); + if (ret) + return ret; + return check_bin_op_nesting_recursive(node->u.binary.right, + nesting++); + } + case IR_OP_LOGICAL: + { + int ret; + + ret = check_bin_op_nesting_recursive(node->u.logical.left, + nesting); + if (ret) + return ret; + return check_bin_op_nesting_recursive(node->u.logical.right, + nesting); + } + } +} + +int filter_visitor_ir_check_binary_op_nesting(struct filter_parser_ctx *ctx) +{ + return check_bin_op_nesting_recursive(ctx->ir_root, 0); +} diff --git a/src/lib/lttng-ctl/filter-visitor-set-parent.c b/src/lib/lttng-ctl/filter-visitor-set-parent.c new file mode 100644 index 000000000..9ddd10275 --- /dev/null +++ b/src/lib/lttng-ctl/filter-visitor-set-parent.c @@ -0,0 +1,138 @@ +/* + * filter-visitor-set-parent.c + * + * LTTng filter set parent visitor + * + * Copyright 2012 - Mathieu Desnoyers + * + * This library is free software; you can redistribute it and/or modify it + * under the terms of the GNU Lesser General Public License, version 2.1 only, + * as published by the Free Software Foundation. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public License + * along with this library; if not, write to the Free Software Foundation, + * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA + */ + +#include +#include +#include +#include +#include +#include +#include +#include "filter-parser.h" +#include "filter-ast.h" + +static +int update_child(struct filter_node *parent, + struct filter_node *old_child, + struct filter_node *new_child) +{ + switch (parent->type) { + case NODE_UNKNOWN: + default: + fprintf(stderr, "[error] %s: unknown node type\n", __func__); + return -EINVAL; + case NODE_ROOT: + assert(parent->u.root.child == old_child); + parent->u.root.child = new_child; + break; + case NODE_EXPRESSION: + assert(parent->u.expression.type == AST_EXP_NESTED); + assert(parent->u.expression.u.child == old_child); + parent->u.expression.u.child = new_child; + break; + case NODE_OP: + assert(parent->u.op.lchild == old_child || + parent->u.op.rchild == old_child); + if (parent->u.op.lchild == old_child) + parent->u.op.lchild = new_child; + else + parent->u.op.rchild = new_child; + break; + case NODE_UNARY_OP: + assert(parent->u.unary_op.child == old_child); + parent->u.unary_op.child = new_child; + break; + } + return 0; +} + +static +int recursive_visit_set_parent(struct filter_node *node, + struct filter_node *parent) +{ + int ret; + + if (!node) { + fprintf(stderr, "[error] %s: NULL child\n", __func__); + return -EINVAL; + } + node->parent = parent; + switch (node->type) { + case NODE_UNKNOWN: + default: + fprintf(stderr, "[error] %s: unknown node type\n", __func__); + return -EINVAL; + case NODE_ROOT: + assert(parent == NULL); + return recursive_visit_set_parent(node->u.root.child, node); + case NODE_EXPRESSION: + switch (node->u.expression.type) { + case AST_EXP_UNKNOWN: + default: + fprintf(stderr, "[error] %s: unknown expression type\n", __func__); + return -EINVAL; + case AST_EXP_NESTED: + return recursive_visit_set_parent(node->u.expression.u.child, node); + case AST_EXP_IDENTIFIER: + { + struct filter_node *orig_node = node; + + while (node->u.expression.prev) { + struct filter_node *prev; + + prev = node->u.expression.prev; + if (prev->type != NODE_EXPRESSION || + prev->u.expression.type != AST_EXP_IDENTIFIER) { + fprintf(stderr, "[error] %s: expecting identifier before link\n", __func__); + return -EINVAL; + } + + prev->u.expression.next = node; + prev->u.expression.pre_op = + node->u.expression.post_op; + prev->parent = node->parent; + node = prev; + } + /* Set first child as forward */ + ret = update_child(parent, orig_node, node); + if (ret) + return ret; + } + case AST_EXP_CONSTANT: + case AST_EXP_STRING: + break; + } + break; + case NODE_OP: + ret = recursive_visit_set_parent(node->u.op.lchild, node); + if (ret) + return ret; + return recursive_visit_set_parent(node->u.op.rchild, node); + case NODE_UNARY_OP: + return recursive_visit_set_parent(node->u.unary_op.child, node); + } + return 0; +} + +int filter_visitor_set_parent(struct filter_parser_ctx *ctx) +{ + return recursive_visit_set_parent(&ctx->ast->root, NULL); +} diff --git a/src/lib/lttng-ctl/filter-visitor-xml.c b/src/lib/lttng-ctl/filter-visitor-xml.c new file mode 100644 index 000000000..670a7f320 --- /dev/null +++ b/src/lib/lttng-ctl/filter-visitor-xml.c @@ -0,0 +1,248 @@ +/* + * filter-visitor-xml.c + * + * LTTng filter XML pretty printer visitor + * + * Copyright 2012 - Mathieu Desnoyers + * + * This library is free software; you can redistribute it and/or modify it + * under the terms of the GNU Lesser General Public License, version 2.1 only, + * as published by the Free Software Foundation. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public License + * along with this library; if not, write to the Free Software Foundation, + * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA + */ + +#include +#include +#include +#include +#include +#include +#include +#include "filter-parser.h" +#include "filter-ast.h" + +#define fprintf_dbg(fd, fmt, args...) fprintf(fd, "%s: " fmt, __func__, ## args) + +static +int recursive_visit_print(struct filter_node *node, FILE *stream, int indent); + +static +void print_tabs(FILE *fd, int depth) +{ + int i; + + for (i = 0; i < depth; i++) + fprintf(fd, "\t"); +} + +static +int recursive_visit_print_expression(struct filter_node *node, + FILE *stream, int indent) +{ + if (!node) { + fprintf(stderr, "[error] %s: NULL child\n", __func__); + return -EINVAL; + } + switch (node->u.expression.type) { + case AST_EXP_UNKNOWN: + default: + fprintf(stderr, "[error] %s: unknown expression\n", __func__); + return -EINVAL; + case AST_EXP_STRING: + print_tabs(stream, indent); + fprintf(stream, "\n", + node->u.expression.u.string); + break; + case AST_EXP_CONSTANT: + print_tabs(stream, indent); + fprintf(stream, "\n", + node->u.expression.u.constant); + break; + case AST_EXP_IDENTIFIER: + print_tabs(stream, indent); + fprintf(stream, "\n", + node->u.expression.u.identifier); + while (node->u.expression.next) { + print_tabs(stream, indent); + fprintf(stream, "u.expression.pre_op) { + case AST_LINK_UNKNOWN: + default: + fprintf(stderr, "[error] %s: unknown link\n", __func__); + return -EINVAL; + case AST_LINK_DOT: + fprintf(stream, "."); + break; + case AST_LINK_RARROW: + fprintf(stream, "->"); + break; + } + fprintf(stream, "\"/>\n"); + + node = node->u.expression.next; + if (node->type != NODE_EXPRESSION || + node->u.expression.type != AST_EXP_IDENTIFIER) { + fprintf(stderr, "[error] %s: expecting identifier before link\n", __func__); + return -EINVAL; + } + + print_tabs(stream, indent); + fprintf(stream, "\n", + node->u.expression.u.identifier); + } + break; + case AST_EXP_NESTED: + return recursive_visit_print(node->u.expression.u.child, + stream, indent + 1); + } + return 0; +} + + +static +int recursive_visit_print(struct filter_node *node, FILE *stream, int indent) +{ + int ret; + + if (!node) { + fprintf(stderr, "[error] %s: NULL child\n", __func__); + return -EINVAL; + } + switch (node->type) { + case NODE_UNKNOWN: + default: + fprintf(stderr, "[error] %s: unknown node type\n", __func__); + return -EINVAL; + case NODE_ROOT: + print_tabs(stream, indent); + fprintf(stream, "\n"); + ret = recursive_visit_print(node->u.root.child, stream, + indent + 1); + print_tabs(stream, indent); + fprintf(stream, "\n"); + return ret; + case NODE_EXPRESSION: + print_tabs(stream, indent); + fprintf(stream, "\n"); + ret = recursive_visit_print_expression(node, stream, + indent + 1); + print_tabs(stream, indent); + fprintf(stream, "\n"); + return ret; + case NODE_OP: + print_tabs(stream, indent); + fprintf(stream, ">\""); + break; + case AST_OP_LSHIFT: + fprintf(stream, "\"<<\""); + break; + case AST_OP_AND: + fprintf(stream, "\"&&\""); + break; + case AST_OP_OR: + fprintf(stream, "\"||\""); + break; + case AST_OP_BIN_AND: + fprintf(stream, "\"&\""); + break; + case AST_OP_BIN_OR: + fprintf(stream, "\"|\""); + break; + case AST_OP_BIN_XOR: + fprintf(stream, "\"^\""); + break; + + case AST_OP_EQ: + fprintf(stream, "\"==\""); + break; + case AST_OP_NE: + fprintf(stream, "\"!=\""); + break; + case AST_OP_GT: + fprintf(stream, "\">\""); + break; + case AST_OP_LT: + fprintf(stream, "\"<\""); + break; + case AST_OP_GE: + fprintf(stream, "\">=\""); + break; + case AST_OP_LE: + fprintf(stream, "\"<=\""); + break; + } + fprintf(stream, ">\n"); + ret = recursive_visit_print(node->u.op.lchild, + stream, indent + 1); + if (ret) + return ret; + ret = recursive_visit_print(node->u.op.rchild, + stream, indent + 1); + if (ret) + return ret; + print_tabs(stream, indent); + fprintf(stream, "\n"); + return ret; + case NODE_UNARY_OP: + print_tabs(stream, indent); + fprintf(stream, "\n"); + ret = recursive_visit_print(node->u.unary_op.child, + stream, indent + 1); + print_tabs(stream, indent); + fprintf(stream, "\n"); + return ret; + } + return 0; +} + +int filter_visitor_print_xml(struct filter_parser_ctx *ctx, FILE *stream, + int indent) +{ + return recursive_visit_print(&ctx->ast->root, stream, indent); +} diff --git a/src/lib/lttng-ctl/tests.txt b/src/lib/lttng-ctl/tests.txt new file mode 100644 index 000000000..04112e6e2 --- /dev/null +++ b/src/lib/lttng-ctl/tests.txt @@ -0,0 +1,23 @@ +1+1 +a+1 +a.b.c->d.e.f+1 +1+11111-3333+1 +!a.f.d +(1+2)*(55*666) +1+2*55*666 +!+-+++-------+++++++++++-----!!--!44+1 +aa>=2 +aa>=2&&bb<1||c!=a +aa>=2&&(bb<-1||c!=a) +(!aa>=2&&bb<-1)||c!=a +c=="test" +c!="test" +c=="test*" +c!="test*" +aaa||(gg)+(333----1) +!aa>2 +asdf + 1 > 1 +asdfas < 2332 || asdf + 1 > 1 +asdf.asdfsd.sadf < 4 +asdfasdf->asdfasdf < 2 +0 || ("abc" != "def")) && (3 < 4) -- 2.34.1