From: Mathieu Desnoyers Date: Mon, 16 Jul 2012 19:46:57 +0000 (-0400) Subject: Filter: use hash table to check merge points X-Git-Tag: v2.1.0-rc1~24 X-Git-Url: http://git.liburcu.org/?p=lttng-ust.git;a=commitdiff_plain;h=bf956ec0051ba7f365693e194bc0aeaf4343a82c Filter: use hash table to check merge points Signed-off-by: Mathieu Desnoyers --- diff --git a/README b/README index 52aebd89..55c72df7 100644 --- a/README +++ b/README @@ -16,7 +16,7 @@ PREREQUISITES: - liburcu Userspace RCU library, by Mathieu Desnoyers and Paul E. McKenney - -> This release depends on liburcu v0.6.6 + -> This release depends on liburcu v0.7.2 * Debian/Ubuntu package: liburcu-dev * Website: http://lttng.org/urcu diff --git a/configure.ac b/configure.ac index edd3c209..4d40f753 100644 --- a/configure.ac +++ b/configure.ac @@ -116,6 +116,11 @@ CFLAGS="-Wall $CFLAGS" AC_CHECK_HEADERS([urcu-bp.h], [], [AC_MSG_ERROR([Cannot find [URCU] headers (urcu-bp.h). Use [CPPFLAGS]=-Idir to specify their location. This error can also occur when the liburcu package's configure script has not been run.])]) +# urcu-cds - check that URCU Concurrent Data Structure lib is available to compilation +# Part of Userspace RCU library 0.7.2 or better. +AC_CHECK_LIB([urcu-cds], [_cds_lfht_new], [], [AC_MSG_ERROR([Cannot find +liburcu-cds lib, part of Userspace RCU 0.7 or better. Use [LDFLAGS]=-Ldir to specify its location.])]) + AC_MSG_CHECKING([caa_likely()]) AC_COMPILE_IFELSE([AC_LANG_SOURCE([[ #include diff --git a/liblttng-ust/Makefile.am b/liblttng-ust/Makefile.am index 9ec05915..cc36e20e 100644 --- a/liblttng-ust/Makefile.am +++ b/liblttng-ust/Makefile.am @@ -33,6 +33,7 @@ liblttng_ust_runtime_la_SOURCES = \ lttng-filter-specialize.c \ lttng-filter-interpreter.c \ filter-bytecode.h \ + lttng-hash-helper.h \ tracepoint-internal.h \ clock.h \ compat.h \ @@ -61,6 +62,7 @@ liblttng_ust_support_la_LIBADD = \ liblttng_ust_la_LIBADD = \ -lpthread \ -lrt \ + -lurcu-cds \ -llttng-ust-tracepoint \ $(top_builddir)/snprintf/libustsnprintf.la \ $(top_builddir)/liblttng-ust-comm/liblttng-ust-comm.la \ diff --git a/liblttng-ust/lttng-filter-validator.c b/liblttng-ust/lttng-filter-validator.c index 6991931b..b164cbbf 100644 --- a/liblttng-ust/lttng-filter-validator.c +++ b/liblttng-ust/lttng-filter-validator.c @@ -20,10 +20,71 @@ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA */ +#define _LGPL_SOURCE +#include +#include #include "lttng-filter.h" +#include +#include "lttng-hash-helper.h" + +/* merge point table node */ +struct lfht_mp_node { + struct cds_lfht_node node; + + /* Context at merge point */ + struct vreg reg[NR_REG]; + unsigned long target_pc; +}; + +static unsigned long lttng_hash_seed; +static unsigned int lttng_hash_seed_ready; + +static +int lttng_hash_match(struct cds_lfht_node *node, const void *key) +{ + struct lfht_mp_node *mp_node = + caa_container_of(node, struct lfht_mp_node, node); + unsigned long key_pc = (unsigned long) key; + + if (mp_node->target_pc == key_pc) + return 1; + else + return 0; +} + +static +int merge_point_add(struct cds_lfht *ht, unsigned long target_pc, + const struct vreg reg[NR_REG]) +{ + struct lfht_mp_node *node; + unsigned long hash = lttng_hash_mix((const void *) target_pc, + sizeof(target_pc), + lttng_hash_seed); + + dbg_printf("Filter: adding merge point at offset %lu, hash %lu\n", + target_pc, hash); + node = zmalloc(sizeof(struct lfht_mp_node)); + if (!node) + return -ENOMEM; + node->target_pc = target_pc; + memcpy(node->reg, reg, sizeof(node->reg)); + cds_lfht_add(ht, hash, &node->node); + return 0; +} + +/* + * Number of merge points for hash table size. Hash table initialized to + * that size, and we do not resize, because we do not want to trigger + * RCU worker thread execution: fall-back on linear traversal if number + * of merge points exceeds this value. + */ +#define DEFAULT_NR_MERGE_POINTS 128 +#define MIN_NR_BUCKETS 128 +#define MAX_NR_BUCKETS 128 + static -int bin_op_compare_check(struct vreg reg[NR_REG], const char *str) +int bin_op_compare_check(const struct vreg reg[NR_REG], const char *str) { switch (reg[REG_R0].type) { default: @@ -72,7 +133,7 @@ error_mismatch: */ static int bytecode_validate_overflow(struct bytecode_runtime *bytecode, - void *start_pc, void *pc) + void *start_pc, void *pc) { int ret = 0; @@ -246,426 +307,726 @@ int bytecode_validate_overflow(struct bytecode_runtime *bytecode, return ret; } -int lttng_filter_validate_bytecode(struct bytecode_runtime *bytecode) +static +unsigned long delete_all_nodes(struct cds_lfht *ht) { - void *pc, *next_pc, *start_pc; - int ret = -EINVAL; - struct vreg reg[NR_REG]; - int i; + struct cds_lfht_iter iter; + struct lfht_mp_node *node; + unsigned long nr_nodes = 0; - for (i = 0; i < NR_REG; i++) { - reg[i].type = REG_TYPE_UNKNOWN; - reg[i].literal = 0; + cds_lfht_for_each_entry(ht, &iter, node, node) { + int ret; + + ret = cds_lfht_del(ht, cds_lfht_iter_get_node(&iter)); + assert(!ret); + /* note: this hash table is never used concurrently */ + free(node); + nr_nodes++; } + return nr_nodes; +} - start_pc = &bytecode->data[0]; - for (pc = next_pc = start_pc; pc - start_pc < bytecode->len; - pc = next_pc) { - if (bytecode_validate_overflow(bytecode, start_pc, pc) != 0) { - ERR("filter bytecode overflow\n"); - ret = -EINVAL; - goto end; - } - dbg_printf("Validating op %s (%u)\n", - print_op((unsigned int) *(filter_opcode_t *) pc), +/* + * Return value: + * 0: success + * <0: error + */ +static +int validate_instruction_context(struct bytecode_runtime *bytecode, + const struct vreg reg[NR_REG], + void *start_pc, + void *pc) +{ + int ret = 0; + + switch (*(filter_opcode_t *) pc) { + case FILTER_OP_UNKNOWN: + default: + { + ERR("unknown bytecode op %u\n", (unsigned int) *(filter_opcode_t *) pc); - switch (*(filter_opcode_t *) pc) { - case FILTER_OP_UNKNOWN: - default: - ERR("unknown bytecode op %u\n", - (unsigned int) *(filter_opcode_t *) pc); - ret = -EINVAL; - goto end; + ret = -EINVAL; + goto end; + } + + case FILTER_OP_RETURN: + { + goto end; + } + + /* binary */ + case FILTER_OP_MUL: + case FILTER_OP_DIV: + case FILTER_OP_MOD: + case FILTER_OP_PLUS: + case FILTER_OP_MINUS: + case FILTER_OP_RSHIFT: + case FILTER_OP_LSHIFT: + case FILTER_OP_BIN_AND: + case FILTER_OP_BIN_OR: + case FILTER_OP_BIN_XOR: + { + ERR("unsupported bytecode op %u\n", + (unsigned int) *(filter_opcode_t *) pc); + ret = -EINVAL; + goto end; + } - case FILTER_OP_RETURN: - ret = 0; + case FILTER_OP_EQ: + { + ret = bin_op_compare_check(reg, "=="); + if (ret) + goto end; + break; + } + case FILTER_OP_NE: + { + ret = bin_op_compare_check(reg, "!="); + if (ret) + goto end; + break; + } + case FILTER_OP_GT: + { + ret = bin_op_compare_check(reg, ">"); + if (ret) + goto end; + break; + } + case FILTER_OP_LT: + { + ret = bin_op_compare_check(reg, "<"); + if (ret) + goto end; + break; + } + case FILTER_OP_GE: + { + ret = bin_op_compare_check(reg, ">="); + if (ret) + goto end; + break; + } + case FILTER_OP_LE: + { + ret = bin_op_compare_check(reg, "<="); + if (ret) goto end; + break; + } - /* binary */ - case FILTER_OP_MUL: - case FILTER_OP_DIV: - case FILTER_OP_MOD: - case FILTER_OP_PLUS: - case FILTER_OP_MINUS: - case FILTER_OP_RSHIFT: - case FILTER_OP_LSHIFT: - case FILTER_OP_BIN_AND: - case FILTER_OP_BIN_OR: - case FILTER_OP_BIN_XOR: - ERR("unsupported bytecode op %u\n", - (unsigned int) *(filter_opcode_t *) pc); + case FILTER_OP_EQ_STRING: + case FILTER_OP_NE_STRING: + case FILTER_OP_GT_STRING: + case FILTER_OP_LT_STRING: + case FILTER_OP_GE_STRING: + case FILTER_OP_LE_STRING: + { + if (reg[REG_R0].type != REG_STRING + || reg[REG_R1].type != REG_STRING) { + ERR("Unexpected register type for string comparator\n"); ret = -EINVAL; goto end; - - case FILTER_OP_EQ: - { - ret = bin_op_compare_check(reg, "=="); - if (ret) - goto end; - reg[REG_R0].type = REG_S64; - next_pc += sizeof(struct binary_op); - break; - } - case FILTER_OP_NE: - { - ret = bin_op_compare_check(reg, "!="); - if (ret) - goto end; - reg[REG_R0].type = REG_S64; - next_pc += sizeof(struct binary_op); - break; - } - case FILTER_OP_GT: - { - ret = bin_op_compare_check(reg, ">"); - if (ret) - goto end; - reg[REG_R0].type = REG_S64; - next_pc += sizeof(struct binary_op); - break; - } - case FILTER_OP_LT: - { - ret = bin_op_compare_check(reg, "<"); - if (ret) - goto end; - reg[REG_R0].type = REG_S64; - next_pc += sizeof(struct binary_op); - break; - } - case FILTER_OP_GE: - { - ret = bin_op_compare_check(reg, ">="); - if (ret) - goto end; - reg[REG_R0].type = REG_S64; - next_pc += sizeof(struct binary_op); - break; - } - case FILTER_OP_LE: - { - ret = bin_op_compare_check(reg, "<="); - if (ret) - goto end; - reg[REG_R0].type = REG_S64; - next_pc += sizeof(struct binary_op); - break; } + break; + } - case FILTER_OP_EQ_STRING: - case FILTER_OP_NE_STRING: - case FILTER_OP_GT_STRING: - case FILTER_OP_LT_STRING: - case FILTER_OP_GE_STRING: - case FILTER_OP_LE_STRING: - { - if (reg[REG_R0].type != REG_STRING - || reg[REG_R1].type != REG_STRING) { - ERR("Unexpected register type for string comparator\n"); - ret = -EINVAL; - goto end; - } - reg[REG_R0].type = REG_S64; - next_pc += sizeof(struct binary_op); - break; + case FILTER_OP_EQ_S64: + case FILTER_OP_NE_S64: + case FILTER_OP_GT_S64: + case FILTER_OP_LT_S64: + case FILTER_OP_GE_S64: + case FILTER_OP_LE_S64: + { + if (reg[REG_R0].type != REG_S64 + || reg[REG_R1].type != REG_S64) { + ERR("Unexpected register type for s64 comparator\n"); + ret = -EINVAL; + goto end; } + break; + } - case FILTER_OP_EQ_S64: - case FILTER_OP_NE_S64: - case FILTER_OP_GT_S64: - case FILTER_OP_LT_S64: - case FILTER_OP_GE_S64: - case FILTER_OP_LE_S64: - { - if (reg[REG_R0].type != REG_S64 - || reg[REG_R1].type != REG_S64) { - ERR("Unexpected register type for s64 comparator\n"); - ret = -EINVAL; - goto end; - } - reg[REG_R0].type = REG_S64; - next_pc += sizeof(struct binary_op); - break; + case FILTER_OP_EQ_DOUBLE: + case FILTER_OP_NE_DOUBLE: + case FILTER_OP_GT_DOUBLE: + case FILTER_OP_LT_DOUBLE: + case FILTER_OP_GE_DOUBLE: + case FILTER_OP_LE_DOUBLE: + { + if ((reg[REG_R0].type != REG_DOUBLE && reg[REG_R0].type != REG_S64) + || (reg[REG_R1].type != REG_DOUBLE && reg[REG_R1].type != REG_S64)) { + ERR("Unexpected register type for double comparator\n"); + ret = -EINVAL; + goto end; } - - case FILTER_OP_EQ_DOUBLE: - case FILTER_OP_NE_DOUBLE: - case FILTER_OP_GT_DOUBLE: - case FILTER_OP_LT_DOUBLE: - case FILTER_OP_GE_DOUBLE: - case FILTER_OP_LE_DOUBLE: - { - if ((reg[REG_R0].type != REG_DOUBLE && reg[REG_R0].type != REG_S64) - || (reg[REG_R1].type != REG_DOUBLE && reg[REG_R1].type != REG_S64)) { - ERR("Unexpected register type for double comparator\n"); - ret = -EINVAL; - goto end; - } - if (reg[REG_R0].type != REG_DOUBLE && reg[REG_R1].type != REG_DOUBLE) { - ERR("Double operator should have at least one double register\n"); - ret = -EINVAL; - goto end; - } - reg[REG_R0].type = REG_DOUBLE; - next_pc += sizeof(struct binary_op); - break; + if (reg[REG_R0].type != REG_DOUBLE && reg[REG_R1].type != REG_DOUBLE) { + ERR("Double operator should have at least one double register\n"); + ret = -EINVAL; + goto end; } + break; + } - /* unary */ - case FILTER_OP_UNARY_PLUS: - case FILTER_OP_UNARY_MINUS: - case FILTER_OP_UNARY_NOT: - { - struct unary_op *insn = (struct unary_op *) pc; + /* unary */ + case FILTER_OP_UNARY_PLUS: + case FILTER_OP_UNARY_MINUS: + case FILTER_OP_UNARY_NOT: + { + struct unary_op *insn = (struct unary_op *) pc; - if (unlikely(insn->reg >= REG_ERROR)) { - ERR("invalid register %u\n", - (unsigned int) insn->reg); - ret = -EINVAL; - goto end; - } - switch (reg[insn->reg].type) { - default: - ERR("unknown register type\n"); - ret = -EINVAL; - goto end; + if (unlikely(insn->reg >= REG_ERROR)) { + ERR("invalid register %u\n", + (unsigned int) insn->reg); + ret = -EINVAL; + goto end; + } + switch (reg[insn->reg].type) { + default: + ERR("unknown register type\n"); + ret = -EINVAL; + goto end; - case REG_STRING: - ERR("Unary op can only be applied to numeric or floating point registers\n"); - ret = -EINVAL; - goto end; - case REG_S64: - break; - case REG_DOUBLE: - break; - } - next_pc += sizeof(struct unary_op); + case REG_STRING: + ERR("Unary op can only be applied to numeric or floating point registers\n"); + ret = -EINVAL; + goto end; + case REG_S64: + break; + case REG_DOUBLE: break; } + break; + } - case FILTER_OP_UNARY_PLUS_S64: - case FILTER_OP_UNARY_MINUS_S64: - case FILTER_OP_UNARY_NOT_S64: - { - struct unary_op *insn = (struct unary_op *) pc; + case FILTER_OP_UNARY_PLUS_S64: + case FILTER_OP_UNARY_MINUS_S64: + case FILTER_OP_UNARY_NOT_S64: + { + struct unary_op *insn = (struct unary_op *) pc; - if (unlikely(insn->reg >= REG_ERROR)) { - ERR("invalid register %u\n", - (unsigned int) insn->reg); - ret = -EINVAL; - goto end; - } - if (reg[insn->reg].type != REG_S64) { - ERR("Invalid register type\n"); - ret = -EINVAL; - goto end; - } - next_pc += sizeof(struct unary_op); - break; + if (unlikely(insn->reg >= REG_ERROR)) { + ERR("invalid register %u\n", + (unsigned int) insn->reg); + ret = -EINVAL; + goto end; + } + if (reg[insn->reg].type != REG_S64) { + ERR("Invalid register type\n"); + ret = -EINVAL; + goto end; } + break; + } - case FILTER_OP_UNARY_PLUS_DOUBLE: - case FILTER_OP_UNARY_MINUS_DOUBLE: - case FILTER_OP_UNARY_NOT_DOUBLE: - { - struct unary_op *insn = (struct unary_op *) pc; + case FILTER_OP_UNARY_PLUS_DOUBLE: + case FILTER_OP_UNARY_MINUS_DOUBLE: + case FILTER_OP_UNARY_NOT_DOUBLE: + { + struct unary_op *insn = (struct unary_op *) pc; - if (unlikely(insn->reg >= REG_ERROR)) { - ERR("invalid register %u\n", - (unsigned int) insn->reg); - ret = -EINVAL; - goto end; - } - if (reg[insn->reg].type != REG_DOUBLE) { - ERR("Invalid register type\n"); - ret = -EINVAL; - goto end; - } - next_pc += sizeof(struct unary_op); - break; + if (unlikely(insn->reg >= REG_ERROR)) { + ERR("invalid register %u\n", + (unsigned int) insn->reg); + ret = -EINVAL; + goto end; } + if (reg[insn->reg].type != REG_DOUBLE) { + ERR("Invalid register type\n"); + ret = -EINVAL; + goto end; + } + break; + } - /* logical */ - case FILTER_OP_AND: - case FILTER_OP_OR: - { - struct logical_op *insn = (struct logical_op *) pc; - - if (reg[REG_R0].type != REG_S64) { - ERR("Logical comparator expects S64 register\n"); - ret = -EINVAL; - goto end; - } + /* logical */ + case FILTER_OP_AND: + case FILTER_OP_OR: + { + struct logical_op *insn = (struct logical_op *) pc; - dbg_printf("Validate jumping to bytecode offset %u\n", - (unsigned int) insn->skip_offset); - if (unlikely(start_pc + insn->skip_offset <= pc)) { - ERR("Loops are not allowed in bytecode\n"); - ret = -EINVAL; - goto end; - } - next_pc += sizeof(struct logical_op); - break; + if (reg[REG_R0].type != REG_S64) { + ERR("Logical comparator expects S64 register\n"); + ret = -EINVAL; + goto end; } - /* load */ - case FILTER_OP_LOAD_FIELD_REF: - { - ERR("Unknown field ref type\n"); + dbg_printf("Validate jumping to bytecode offset %u\n", + (unsigned int) insn->skip_offset); + if (unlikely(start_pc + insn->skip_offset <= pc)) { + ERR("Loops are not allowed in bytecode\n"); ret = -EINVAL; goto end; } - case FILTER_OP_LOAD_FIELD_REF_STRING: - case FILTER_OP_LOAD_FIELD_REF_SEQUENCE: - { - struct load_op *insn = (struct load_op *) pc; - struct field_ref *ref = (struct field_ref *) insn->data; + break; + } - if (unlikely(insn->reg >= REG_ERROR)) { - ERR("invalid register %u\n", - (unsigned int) insn->reg); - ret = -EINVAL; - goto end; - } - dbg_printf("Validate load field ref offset %u type string\n", - ref->offset); - reg[insn->reg].type = REG_STRING; - reg[insn->reg].literal = 0; - next_pc += sizeof(struct load_op) + sizeof(struct field_ref); - break; + /* load */ + case FILTER_OP_LOAD_FIELD_REF: + { + ERR("Unknown field ref type\n"); + ret = -EINVAL; + goto end; + } + case FILTER_OP_LOAD_FIELD_REF_STRING: + case FILTER_OP_LOAD_FIELD_REF_SEQUENCE: + { + struct load_op *insn = (struct load_op *) pc; + struct field_ref *ref = (struct field_ref *) insn->data; + + if (unlikely(insn->reg >= REG_ERROR)) { + ERR("invalid register %u\n", + (unsigned int) insn->reg); + ret = -EINVAL; + goto end; } - case FILTER_OP_LOAD_FIELD_REF_S64: - { - struct load_op *insn = (struct load_op *) pc; - struct field_ref *ref = (struct field_ref *) insn->data; + dbg_printf("Validate load field ref offset %u type string\n", + ref->offset); + break; + } + case FILTER_OP_LOAD_FIELD_REF_S64: + { + struct load_op *insn = (struct load_op *) pc; + struct field_ref *ref = (struct field_ref *) insn->data; - if (unlikely(insn->reg >= REG_ERROR)) { - ERR("invalid register %u\n", - (unsigned int) insn->reg); - ret = -EINVAL; - goto end; - } - dbg_printf("Validate load field ref offset %u type s64\n", - ref->offset); - reg[insn->reg].type = REG_S64; - reg[insn->reg].literal = 0; - next_pc += sizeof(struct load_op) + sizeof(struct field_ref); - break; + if (unlikely(insn->reg >= REG_ERROR)) { + ERR("invalid register %u\n", + (unsigned int) insn->reg); + ret = -EINVAL; + goto end; } - case FILTER_OP_LOAD_FIELD_REF_DOUBLE: - { - struct load_op *insn = (struct load_op *) pc; - struct field_ref *ref = (struct field_ref *) insn->data; + dbg_printf("Validate load field ref offset %u type s64\n", + ref->offset); + break; + } + case FILTER_OP_LOAD_FIELD_REF_DOUBLE: + { + struct load_op *insn = (struct load_op *) pc; + struct field_ref *ref = (struct field_ref *) insn->data; - if (unlikely(insn->reg >= REG_ERROR)) { - ERR("invalid register %u\n", - (unsigned int) insn->reg); - ret = -EINVAL; - goto end; - } - dbg_printf("Validate load field ref offset %u type double\n", - ref->offset); - reg[insn->reg].type = REG_DOUBLE; - reg[insn->reg].literal = 0; - next_pc += sizeof(struct load_op) + sizeof(struct field_ref); - break; + if (unlikely(insn->reg >= REG_ERROR)) { + ERR("invalid register %u\n", + (unsigned int) insn->reg); + ret = -EINVAL; + goto end; } + dbg_printf("Validate load field ref offset %u type double\n", + ref->offset); + break; + } - case FILTER_OP_LOAD_STRING: - { - struct load_op *insn = (struct load_op *) pc; + case FILTER_OP_LOAD_STRING: + { + struct load_op *insn = (struct load_op *) pc; - if (unlikely(insn->reg >= REG_ERROR)) { - ERR("invalid register %u\n", - (unsigned int) insn->reg); - ret = -EINVAL; - goto end; - } - reg[insn->reg].type = REG_STRING; - reg[insn->reg].literal = 1; - next_pc += sizeof(struct load_op) + strlen(insn->data) + 1; - break; + if (unlikely(insn->reg >= REG_ERROR)) { + ERR("invalid register %u\n", + (unsigned int) insn->reg); + ret = -EINVAL; + goto end; } + break; + } - case FILTER_OP_LOAD_S64: - { - struct load_op *insn = (struct load_op *) pc; + case FILTER_OP_LOAD_S64: + { + struct load_op *insn = (struct load_op *) pc; - if (unlikely(insn->reg >= REG_ERROR)) { - ERR("invalid register %u\n", - (unsigned int) insn->reg); - ret = -EINVAL; - goto end; - } - reg[insn->reg].type = REG_S64; - reg[insn->reg].literal = 1; - next_pc += sizeof(struct load_op) - + sizeof(struct literal_numeric); - break; + if (unlikely(insn->reg >= REG_ERROR)) { + ERR("invalid register %u\n", + (unsigned int) insn->reg); + ret = -EINVAL; + goto end; } + break; + } - case FILTER_OP_LOAD_DOUBLE: - { - struct load_op *insn = (struct load_op *) pc; + case FILTER_OP_LOAD_DOUBLE: + { + struct load_op *insn = (struct load_op *) pc; - if (unlikely(insn->reg >= REG_ERROR)) { - ERR("invalid register %u\n", - (unsigned int) insn->reg); - ret = -EINVAL; - goto end; - } - reg[insn->reg].type = REG_DOUBLE; - reg[insn->reg].literal = 1; - next_pc += sizeof(struct load_op) - + sizeof(struct literal_double); - break; + if (unlikely(insn->reg >= REG_ERROR)) { + ERR("invalid register %u\n", + (unsigned int) insn->reg); + ret = -EINVAL; + goto end; } + break; + } - case FILTER_OP_CAST_TO_S64: - case FILTER_OP_CAST_DOUBLE_TO_S64: - { - struct cast_op *insn = (struct cast_op *) pc; + case FILTER_OP_CAST_TO_S64: + case FILTER_OP_CAST_DOUBLE_TO_S64: + { + struct cast_op *insn = (struct cast_op *) pc; - if (unlikely(insn->reg >= REG_ERROR)) { - ERR("invalid register %u\n", - (unsigned int) insn->reg); - ret = -EINVAL; - goto end; - } - switch (reg[insn->reg].type) { - default: - ERR("unknown register type\n"); - ret = -EINVAL; - goto end; + if (unlikely(insn->reg >= REG_ERROR)) { + ERR("invalid register %u\n", + (unsigned int) insn->reg); + ret = -EINVAL; + goto end; + } + switch (reg[insn->reg].type) { + default: + ERR("unknown register type\n"); + ret = -EINVAL; + goto end; - case REG_STRING: - ERR("Cast op can only be applied to numeric or floating point registers\n"); + case REG_STRING: + ERR("Cast op can only be applied to numeric or floating point registers\n"); + ret = -EINVAL; + goto end; + case REG_S64: + break; + case REG_DOUBLE: + break; + } + if (insn->op == FILTER_OP_CAST_DOUBLE_TO_S64) { + if (reg[insn->reg].type != REG_DOUBLE) { + ERR("Cast expects double\n"); ret = -EINVAL; goto end; - case REG_S64: - break; - case REG_DOUBLE: - break; - } - if (insn->op == FILTER_OP_CAST_DOUBLE_TO_S64) { - if (reg[insn->reg].type != REG_DOUBLE) { - ERR("Cast expects double\n"); - ret = -EINVAL; - goto end; - } } - reg[insn->reg].type = REG_S64; - next_pc += sizeof(struct cast_op); - break; } - case FILTER_OP_CAST_NOP: - { - next_pc += sizeof(struct cast_op); - break; + break; + } + case FILTER_OP_CAST_NOP: + { + break; + } + + } +end: + return ret; +} + +/* + * Return value: + * 0: success + * <0: error + */ +static +int validate_instruction_all_contexts(struct bytecode_runtime *bytecode, + struct cds_lfht *merge_points, + const struct vreg reg[NR_REG], + void *start_pc, + void *pc) +{ + int ret; + unsigned long target_pc = pc - start_pc; + struct cds_lfht_iter iter; + struct cds_lfht_node *node; + unsigned long hash; + + /* Validate the context resulting from the previous instruction */ + ret = validate_instruction_context(bytecode, reg, start_pc, pc); + if (ret) + return ret; + + /* Validate merge points */ + hash = lttng_hash_mix((const void *) target_pc, sizeof(target_pc), + lttng_hash_seed); + cds_lfht_for_each_duplicate(merge_points, hash, lttng_hash_match, + (const void *) target_pc, &iter, node) { + struct lfht_mp_node *mp_node = + caa_container_of(node, struct lfht_mp_node, node); + + dbg_printf("Filter: validate merge point at offset %lu\n", + target_pc); + ret = validate_instruction_context(bytecode, mp_node->reg, + start_pc, pc); + if (ret) + return ret; + /* Once validated, we can remove the merge point */ + dbg_printf("Filter: remove one merge point at offset %lu\n", + target_pc); + ret = cds_lfht_del(merge_points, node); + assert(!ret); + } + return 0; +} + +/* + * Return value: + * >0: going to next insn. + * 0: success, stop iteration. + * <0: error + */ +static +int exec_insn(struct bytecode_runtime *bytecode, + struct cds_lfht *merge_points, + struct vreg reg[NR_REG], + void **_next_pc, + void *pc) +{ + int ret = 1; + void *next_pc = *_next_pc; + + switch (*(filter_opcode_t *) pc) { + case FILTER_OP_UNKNOWN: + default: + { + ERR("unknown bytecode op %u\n", + (unsigned int) *(filter_opcode_t *) pc); + ret = -EINVAL; + goto end; + } + + case FILTER_OP_RETURN: + { + ret = 0; + goto end; + } + + /* binary */ + case FILTER_OP_MUL: + case FILTER_OP_DIV: + case FILTER_OP_MOD: + case FILTER_OP_PLUS: + case FILTER_OP_MINUS: + case FILTER_OP_RSHIFT: + case FILTER_OP_LSHIFT: + case FILTER_OP_BIN_AND: + case FILTER_OP_BIN_OR: + case FILTER_OP_BIN_XOR: + { + ERR("unsupported bytecode op %u\n", + (unsigned int) *(filter_opcode_t *) pc); + ret = -EINVAL; + goto end; + } + + case FILTER_OP_EQ: + case FILTER_OP_NE: + case FILTER_OP_GT: + case FILTER_OP_LT: + case FILTER_OP_GE: + case FILTER_OP_LE: + case FILTER_OP_EQ_STRING: + case FILTER_OP_NE_STRING: + case FILTER_OP_GT_STRING: + case FILTER_OP_LT_STRING: + case FILTER_OP_GE_STRING: + case FILTER_OP_LE_STRING: + case FILTER_OP_EQ_S64: + case FILTER_OP_NE_S64: + case FILTER_OP_GT_S64: + case FILTER_OP_LT_S64: + case FILTER_OP_GE_S64: + case FILTER_OP_LE_S64: + { + reg[REG_R0].type = REG_S64; + next_pc += sizeof(struct binary_op); + break; + } + + case FILTER_OP_EQ_DOUBLE: + case FILTER_OP_NE_DOUBLE: + case FILTER_OP_GT_DOUBLE: + case FILTER_OP_LT_DOUBLE: + case FILTER_OP_GE_DOUBLE: + case FILTER_OP_LE_DOUBLE: + { + reg[REG_R0].type = REG_DOUBLE; + next_pc += sizeof(struct binary_op); + break; + } + + /* unary */ + case FILTER_OP_UNARY_PLUS: + case FILTER_OP_UNARY_MINUS: + case FILTER_OP_UNARY_NOT: + case FILTER_OP_UNARY_PLUS_S64: + case FILTER_OP_UNARY_MINUS_S64: + case FILTER_OP_UNARY_NOT_S64: + { + reg[REG_R0].type = REG_S64; + next_pc += sizeof(struct unary_op); + break; + } + + case FILTER_OP_UNARY_PLUS_DOUBLE: + case FILTER_OP_UNARY_MINUS_DOUBLE: + case FILTER_OP_UNARY_NOT_DOUBLE: + { + reg[REG_R0].type = REG_DOUBLE; + next_pc += sizeof(struct unary_op); + break; + } + + /* logical */ + case FILTER_OP_AND: + case FILTER_OP_OR: + { + struct logical_op *insn = (struct logical_op *) pc; + int merge_ret; + + /* Add merge point to table */ + merge_ret = merge_point_add(merge_points, insn->skip_offset, reg); + if (merge_ret) { + ret = merge_ret; + goto end; } + /* Continue to next instruction */ + next_pc += sizeof(struct logical_op); + break; + } + + /* load */ + case FILTER_OP_LOAD_FIELD_REF: + { + ERR("Unknown field ref type\n"); + ret = -EINVAL; + goto end; + } + case FILTER_OP_LOAD_FIELD_REF_STRING: + case FILTER_OP_LOAD_FIELD_REF_SEQUENCE: + { + struct load_op *insn = (struct load_op *) pc; + + reg[insn->reg].type = REG_STRING; + reg[insn->reg].literal = 0; + next_pc += sizeof(struct load_op) + sizeof(struct field_ref); + break; + } + case FILTER_OP_LOAD_FIELD_REF_S64: + { + struct load_op *insn = (struct load_op *) pc; + + reg[insn->reg].type = REG_S64; + reg[insn->reg].literal = 0; + next_pc += sizeof(struct load_op) + sizeof(struct field_ref); + break; + } + case FILTER_OP_LOAD_FIELD_REF_DOUBLE: + { + struct load_op *insn = (struct load_op *) pc; + + reg[insn->reg].type = REG_DOUBLE; + reg[insn->reg].literal = 0; + next_pc += sizeof(struct load_op) + sizeof(struct field_ref); + break; + } + + case FILTER_OP_LOAD_STRING: + { + struct load_op *insn = (struct load_op *) pc; + + reg[insn->reg].type = REG_STRING; + reg[insn->reg].literal = 1; + next_pc += sizeof(struct load_op) + strlen(insn->data) + 1; + break; + } + + case FILTER_OP_LOAD_S64: + { + struct load_op *insn = (struct load_op *) pc; + + reg[insn->reg].type = REG_S64; + reg[insn->reg].literal = 1; + next_pc += sizeof(struct load_op) + + sizeof(struct literal_numeric); + break; + } + + case FILTER_OP_LOAD_DOUBLE: + { + struct load_op *insn = (struct load_op *) pc; + + reg[insn->reg].type = REG_DOUBLE; + reg[insn->reg].literal = 1; + next_pc += sizeof(struct load_op) + + sizeof(struct literal_double); + break; + } + + case FILTER_OP_CAST_TO_S64: + case FILTER_OP_CAST_DOUBLE_TO_S64: + { + struct cast_op *insn = (struct cast_op *) pc; + + reg[insn->reg].type = REG_S64; + next_pc += sizeof(struct cast_op); + break; + } + case FILTER_OP_CAST_NOP: + { + next_pc += sizeof(struct cast_op); + break; + } + } +end: + *_next_pc = next_pc; + return ret; +} + +/* + * Never called concurrently (hash seed is shared). + */ +int lttng_filter_validate_bytecode(struct bytecode_runtime *bytecode) +{ + struct cds_lfht *merge_points; + void *pc, *next_pc, *start_pc; + int ret = -EINVAL; + struct vreg reg[NR_REG]; + int i; + + for (i = 0; i < NR_REG; i++) { + reg[i].type = REG_TYPE_UNKNOWN; + reg[i].literal = 0; + } + + if (!lttng_hash_seed_ready) { + lttng_hash_seed = time(NULL); + lttng_hash_seed_ready = 1; + } + /* + * Note: merge_points hash table used by single thread, and + * never concurrently resized. Therefore, we can use it without + * holding RCU read-side lock and free nodes without using + * call_rcu. + */ + merge_points = cds_lfht_new(DEFAULT_NR_MERGE_POINTS, + MIN_NR_BUCKETS, MAX_NR_BUCKETS, + 0, NULL); + if (!merge_points) { + ERR("Error allocating hash table for bytecode validation\n"); + return -ENOMEM; + } + start_pc = &bytecode->data[0]; + for (pc = next_pc = start_pc; pc - start_pc < bytecode->len; + pc = next_pc) { + if (bytecode_validate_overflow(bytecode, start_pc, pc) != 0) { + ERR("filter bytecode overflow\n"); + ret = -EINVAL; + goto end; } + dbg_printf("Validating op %s (%u)\n", + print_op((unsigned int) *(filter_opcode_t *) pc), + (unsigned int) *(filter_opcode_t *) pc); + + /* + * For each instruction, validate the current context + * (traversal of entire execution flow), and validate + * all merge points targeting this instruction. + */ + ret = validate_instruction_all_contexts(bytecode, merge_points, + reg, start_pc, pc); + if (ret) + goto end; + ret = exec_insn(bytecode, merge_points, reg, &next_pc, pc); + if (ret <= 0) + goto end; } end: + if (delete_all_nodes(merge_points)) { + if (!ret) { + ERR("Unexpected merge points\n"); + ret = -EINVAL; + } + } + if (cds_lfht_destroy(merge_points, NULL)) { + ERR("Error destroying hash table\n"); + } return ret; } diff --git a/liblttng-ust/lttng-hash-helper.h b/liblttng-ust/lttng-hash-helper.h new file mode 100644 index 00000000..bddc7c46 --- /dev/null +++ b/liblttng-ust/lttng-hash-helper.h @@ -0,0 +1,160 @@ +#ifndef _LTTNG_HASH_HELPER_H +#define _LTTNG_HASH_HELPER_H + +/* + * lttng-hash-helper.h + * + * LTTng hash table helpers. + * + * Copyright (C) 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 as published by the Free Software Foundation; only + * version 2.1 of the License. + * + * 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 + +/* + * Hash function + * Source: http://burtleburtle.net/bob/c/lookup3.c + * Originally Public Domain + */ + +#define rot(x, k) (((x) << (k)) | ((x) >> (32 - (k)))) + +#define mix(a, b, c) \ +do { \ + a -= c; a ^= rot(c, 4); c += b; \ + b -= a; b ^= rot(a, 6); a += c; \ + c -= b; c ^= rot(b, 8); b += a; \ + a -= c; a ^= rot(c, 16); c += b; \ + b -= a; b ^= rot(a, 19); a += c; \ + c -= b; c ^= rot(b, 4); b += a; \ +} while (0) + +#define final(a, b, c) \ +{ \ + c ^= b; c -= rot(b, 14); \ + a ^= c; a -= rot(c, 11); \ + b ^= a; b -= rot(a, 25); \ + c ^= b; c -= rot(b, 16); \ + a ^= c; a -= rot(c, 4);\ + b ^= a; b -= rot(a, 14); \ + c ^= b; c -= rot(b, 24); \ +} + +static inline __attribute__((unused)) +uint32_t lttng_hash_u32( + const uint32_t *k, /* the key, an array of uint32_t values */ + size_t length, /* the length of the key, in uint32_ts */ + uint32_t initval) /* the previous hash, or an arbitrary value */ +{ + uint32_t a, b, c; + + /* Set up the internal state */ + a = b = c = 0xdeadbeef + (((uint32_t) length) << 2) + initval; + + /*----------------------------------------- handle most of the key */ + while (length > 3) { + a += k[0]; + b += k[1]; + c += k[2]; + mix(a, b, c); + length -= 3; + k += 3; + } + + /*----------------------------------- handle the last 3 uint32_t's */ + switch (length) { /* all the case statements fall through */ + case 3: c += k[2]; + case 2: b += k[1]; + case 1: a += k[0]; + final(a, b, c); + case 0: /* case 0: nothing left to add */ + break; + } + /*---------------------------------------------- report the result */ + return c; +} + +static inline +void lttng_hashword2( + const uint32_t *k, /* the key, an array of uint32_t values */ + size_t length, /* the length of the key, in uint32_ts */ + uint32_t *pc, /* IN: seed OUT: primary hash value */ + uint32_t *pb) /* IN: more seed OUT: secondary hash value */ +{ + uint32_t a, b, c; + + /* Set up the internal state */ + a = b = c = 0xdeadbeef + ((uint32_t) (length << 2)) + *pc; + c += *pb; + + /*----------------------------------------- handle most of the key */ + while (length > 3) { + a += k[0]; + b += k[1]; + c += k[2]; + mix(a, b, c); + length -= 3; + k += 3; + } + + /*----------------------------------- handle the last 3 uint32_t's */ + switch (length) { /* all the case statements fall through */ + case 3: c += k[2]; + case 2: b += k[1]; + case 1: a += k[0]; + final(a, b, c); + case 0: /* case 0: nothing left to add */ + break; + } + /*---------------------------------------------- report the result */ + *pc = c; + *pb = b; +} + +#if (CAA_BITS_PER_LONG == 32) +static inline +unsigned long lttng_hash_mix(const void *_key, size_t length, unsigned long seed) +{ + unsigned int key = (unsigned int) _key; + + assert(length == sizeof(unsigned int)); + return lttng_hash_u32(&key, 1, seed); +} +#else +static inline +unsigned long lttng_hash_mix(const void *_key, size_t length, unsigned long seed) +{ + union { + uint64_t v64; + uint32_t v32[2]; + } v; + union { + uint64_t v64; + uint32_t v32[2]; + } key; + + assert(length == sizeof(unsigned long)); + v.v64 = (uint64_t) seed; + key.v64 = (uint64_t) _key; + lttng_hashword2(key.v32, 2, &v.v32[0], &v.v32[1]); + return v.v64; +} +#endif + +#endif /* _LTTNG_HASH_HELPER_H */