2 * filter-visitor-generate-bytecode.c
4 * LTTng filter bytecode generation
6 * Copyright 2012 - Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
8 * This library is free software; you can redistribute it and/or modify it
9 * under the terms of the GNU Lesser General Public License, version 2.1 only,
10 * as published by the Free Software Foundation.
12 * This library is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 * Lesser General Public License for more details.
17 * You should have received a copy of the GNU Lesser General Public License
18 * along with this library; if not, write to the Free Software Foundation,
19 * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
25 #include <common/align.h>
26 #include <common/compat/string.h>
28 #include "filter-bytecode.h"
29 #include "filter-ir.h"
30 #include "filter-ast.h"
32 #include <common/macros.h>
35 #define max_t(type, a, b) ((type) ((a) > (b) ? (a) : (b)))
38 #define INIT_ALLOC_SIZE 4
41 int recursive_visit_gen_bytecode(struct filter_parser_ctx
*ctx
,
44 static inline int get_count_order(unsigned int count
)
48 order
= lttng_fls(count
) - 1;
49 if (count
& (count
- 1))
55 int bytecode_init(struct lttng_filter_bytecode_alloc
**fb
)
59 alloc_len
= sizeof(struct lttng_filter_bytecode_alloc
) + INIT_ALLOC_SIZE
;
60 *fb
= calloc(alloc_len
, 1);
64 (*fb
)->alloc_len
= alloc_len
;
70 int32_t bytecode_reserve(struct lttng_filter_bytecode_alloc
**fb
, uint32_t align
, uint32_t len
)
73 uint32_t padding
= offset_align((*fb
)->b
.len
, align
);
74 uint32_t new_len
= (*fb
)->b
.len
+ padding
+ len
;
75 uint32_t new_alloc_len
= sizeof(struct lttng_filter_bytecode_alloc
) + new_len
;
76 uint32_t old_alloc_len
= (*fb
)->alloc_len
;
78 if (new_len
> LTTNG_FILTER_MAX_LEN
)
81 if (new_alloc_len
> old_alloc_len
) {
82 struct lttng_filter_bytecode_alloc
*newptr
;
85 max_t(uint32_t, 1U << get_count_order(new_alloc_len
), old_alloc_len
<< 1);
86 newptr
= realloc(*fb
, new_alloc_len
);
90 /* We zero directly the memory from start of allocation. */
91 memset(&((char *) *fb
)[old_alloc_len
], 0, new_alloc_len
- old_alloc_len
);
92 (*fb
)->alloc_len
= new_alloc_len
;
94 (*fb
)->b
.len
+= padding
;
101 int bytecode_push(struct lttng_filter_bytecode_alloc
**fb
, const void *data
,
102 uint32_t align
, uint32_t len
)
106 offset
= bytecode_reserve(fb
, align
, len
);
109 memcpy(&(*fb
)->b
.data
[offset
], data
, len
);
114 int bytecode_push_logical(struct lttng_filter_bytecode_alloc
**fb
,
115 struct logical_op
*data
,
116 uint32_t align
, uint32_t len
,
117 uint16_t *skip_offset
)
121 offset
= bytecode_reserve(fb
, align
, len
);
124 memcpy(&(*fb
)->b
.data
[offset
], data
, len
);
126 (void *) &((struct logical_op
*) &(*fb
)->b
.data
[offset
])->skip_offset
127 - (void *) &(*fb
)->b
.data
[0];
132 int bytecode_patch(struct lttng_filter_bytecode_alloc
**fb
,
137 if (offset
>= (*fb
)->b
.len
) {
140 memcpy(&(*fb
)->b
.data
[offset
], data
, len
);
145 int visit_node_root(struct filter_parser_ctx
*ctx
, struct ir_op
*node
)
148 struct return_op insn
;
151 ret
= recursive_visit_gen_bytecode(ctx
, node
->u
.root
.child
);
155 /* Generate end of bytecode instruction */
156 insn
.op
= FILTER_OP_RETURN
;
157 return bytecode_push(&ctx
->bytecode
, &insn
, 1, sizeof(insn
));
161 int visit_node_load(struct filter_parser_ctx
*ctx
, struct ir_op
*node
)
165 switch (node
->data_type
) {
166 case IR_DATA_UNKNOWN
:
168 fprintf(stderr
, "[error] Unknown data type in %s\n",
174 struct load_op
*insn
;
175 uint32_t insn_len
= sizeof(struct load_op
)
176 + strlen(node
->u
.load
.u
.string
.value
) + 1;
178 insn
= calloc(insn_len
, 1);
182 switch (node
->u
.load
.u
.string
.type
) {
183 case IR_LOAD_STRING_TYPE_GLOB_STAR
:
185 * We explicitly tell the interpreter here that
186 * this load is a full star globbing pattern so
187 * that the appropriate matching function can be
188 * called. Also, see comment below.
190 insn
->op
= FILTER_OP_LOAD_STAR_GLOB_STRING
;
194 * This is the "legacy" string, which includes
195 * star globbing patterns with a star only at
196 * the end. Both "plain" and "star at the end"
197 * literal strings are handled at the same place
198 * by the tracer's filter bytecode interpreter,
199 * whereas full star globbing patterns (stars
200 * can be anywhere in the string) is a special
203 insn
->op
= FILTER_OP_LOAD_STRING
;
207 strcpy(insn
->data
, node
->u
.load
.u
.string
.value
);
208 ret
= bytecode_push(&ctx
->bytecode
, insn
, 1, insn_len
);
212 case IR_DATA_NUMERIC
:
214 struct load_op
*insn
;
215 uint32_t insn_len
= sizeof(struct load_op
)
216 + sizeof(struct literal_numeric
);
218 insn
= calloc(insn_len
, 1);
221 insn
->op
= FILTER_OP_LOAD_S64
;
222 memcpy(insn
->data
, &node
->u
.load
.u
.num
, sizeof(int64_t));
223 ret
= bytecode_push(&ctx
->bytecode
, insn
, 1, insn_len
);
229 struct load_op
*insn
;
230 uint32_t insn_len
= sizeof(struct load_op
)
231 + sizeof(struct literal_double
);
233 insn
= calloc(insn_len
, 1);
236 insn
->op
= FILTER_OP_LOAD_DOUBLE
;
237 memcpy(insn
->data
, &node
->u
.load
.u
.flt
, sizeof(double));
238 ret
= bytecode_push(&ctx
->bytecode
, insn
, 1, insn_len
);
242 case IR_DATA_FIELD_REF
: /* fall-through */
243 case IR_DATA_GET_CONTEXT_REF
:
245 struct load_op
*insn
;
246 uint32_t insn_len
= sizeof(struct load_op
)
247 + sizeof(struct field_ref
);
248 struct field_ref ref_offset
;
249 uint32_t reloc_offset_u32
;
250 uint16_t reloc_offset
;
252 insn
= calloc(insn_len
, 1);
255 switch (node
->data_type
) {
256 case IR_DATA_FIELD_REF
:
257 insn
->op
= FILTER_OP_LOAD_FIELD_REF
;
259 case IR_DATA_GET_CONTEXT_REF
:
260 insn
->op
= FILTER_OP_GET_CONTEXT_REF
;
266 ref_offset
.offset
= (uint16_t) -1U;
267 memcpy(insn
->data
, &ref_offset
, sizeof(ref_offset
));
268 /* reloc_offset points to struct load_op */
269 reloc_offset_u32
= bytecode_get_len(&ctx
->bytecode
->b
);
270 if (reloc_offset_u32
> LTTNG_FILTER_MAX_LEN
- 1) {
274 reloc_offset
= (uint16_t) reloc_offset_u32
;
275 ret
= bytecode_push(&ctx
->bytecode
, insn
, 1, insn_len
);
281 ret
= bytecode_push(&ctx
->bytecode_reloc
, &reloc_offset
,
282 1, sizeof(reloc_offset
));
287 ret
= bytecode_push(&ctx
->bytecode_reloc
, node
->u
.load
.u
.ref
,
288 1, strlen(node
->u
.load
.u
.ref
) + 1);
292 case IR_DATA_FIELD_REF_INDEX
: /* fall-through */
293 case IR_DATA_GET_CONTEXT_REF_INDEX
:
295 struct load_op
*insn
;
296 uint32_t insn_len
= sizeof(struct load_op
)
297 + sizeof(struct field_ref_index
);
298 struct field_ref_index ref_index_offset
;
299 uint32_t reloc_offset_u32
;
300 uint16_t reloc_offset
;
302 insn
= calloc(insn_len
, 1);
305 switch (node
->data_type
) {
306 case IR_DATA_FIELD_REF_INDEX
:
307 insn
->op
= FILTER_OP_LOAD_FIELD_REF_INDEX
;
309 case IR_DATA_GET_CONTEXT_REF_INDEX
:
310 insn
->op
= FILTER_OP_GET_CONTEXT_REF_INDEX
;
316 ref_index_offset
.offset
= (uint16_t) -1U;
317 ref_index_offset
.index
= node
->u
.load
.u
.ref_index
.index
;
318 memcpy(insn
->data
, &ref_index_offset
, sizeof(ref_index_offset
));
319 /* reloc_offset points to struct load_op */
320 reloc_offset_u32
= bytecode_get_len(&ctx
->bytecode
->b
);
321 if (reloc_offset_u32
> LTTNG_FILTER_MAX_LEN
- 1) {
325 reloc_offset
= (uint16_t) reloc_offset_u32
;
326 ret
= bytecode_push(&ctx
->bytecode
, insn
, 1, insn_len
);
332 ret
= bytecode_push(&ctx
->bytecode_reloc
, &reloc_offset
,
333 1, sizeof(reloc_offset
));
338 ret
= bytecode_push(&ctx
->bytecode_reloc
, node
->u
.load
.u
.ref_index
.symbol
,
339 1, strlen(node
->u
.load
.u
.ref_index
.symbol
) + 1);
347 int visit_node_unary(struct filter_parser_ctx
*ctx
, struct ir_op
*node
)
350 struct unary_op insn
;
353 ret
= recursive_visit_gen_bytecode(ctx
, node
->u
.unary
.child
);
357 /* Generate end of bytecode instruction */
358 switch (node
->u
.unary
.type
) {
359 case AST_UNARY_UNKNOWN
:
361 fprintf(stderr
, "[error] Unknown unary node type in %s\n",
367 case AST_UNARY_MINUS
:
368 insn
.op
= FILTER_OP_UNARY_MINUS
;
369 return bytecode_push(&ctx
->bytecode
, &insn
, 1, sizeof(insn
));
371 insn
.op
= FILTER_OP_UNARY_NOT
;
372 return bytecode_push(&ctx
->bytecode
, &insn
, 1, sizeof(insn
));
377 * Binary comparator nesting is disallowed. This allows fitting into
381 int visit_node_binary(struct filter_parser_ctx
*ctx
, struct ir_op
*node
)
384 struct binary_op insn
;
387 ret
= recursive_visit_gen_bytecode(ctx
, node
->u
.binary
.left
);
390 ret
= recursive_visit_gen_bytecode(ctx
, node
->u
.binary
.right
);
394 switch (node
->u
.binary
.type
) {
397 fprintf(stderr
, "[error] Unknown unary node type in %s\n",
403 fprintf(stderr
, "[error] Unexpected logical node type in %s\n",
408 insn
.op
= FILTER_OP_MUL
;
411 insn
.op
= FILTER_OP_DIV
;
414 insn
.op
= FILTER_OP_MOD
;
417 insn
.op
= FILTER_OP_PLUS
;
420 insn
.op
= FILTER_OP_MINUS
;
423 insn
.op
= FILTER_OP_RSHIFT
;
426 insn
.op
= FILTER_OP_LSHIFT
;
429 insn
.op
= FILTER_OP_BIN_AND
;
432 insn
.op
= FILTER_OP_BIN_OR
;
435 insn
.op
= FILTER_OP_BIN_XOR
;
439 insn
.op
= FILTER_OP_EQ
;
442 insn
.op
= FILTER_OP_NE
;
445 insn
.op
= FILTER_OP_GT
;
448 insn
.op
= FILTER_OP_LT
;
451 insn
.op
= FILTER_OP_GE
;
454 insn
.op
= FILTER_OP_LE
;
457 return bytecode_push(&ctx
->bytecode
, &insn
, 1, sizeof(insn
));
461 * A logical op always return a s64 (1 or 0).
464 int visit_node_logical(struct filter_parser_ctx
*ctx
, struct ir_op
*node
)
467 struct logical_op insn
;
468 uint16_t skip_offset_loc
;
471 /* Visit left child */
472 ret
= recursive_visit_gen_bytecode(ctx
, node
->u
.binary
.left
);
475 /* Cast to s64 if float or field ref */
476 if ((node
->u
.binary
.left
->data_type
== IR_DATA_FIELD_REF
477 || node
->u
.binary
.left
->data_type
== IR_DATA_GET_CONTEXT_REF
478 || node
->u
.binary
.left
->data_type
== IR_DATA_FIELD_REF_INDEX
479 || node
->u
.binary
.left
->data_type
== IR_DATA_GET_CONTEXT_REF_INDEX
)
480 || node
->u
.binary
.left
->data_type
== IR_DATA_FLOAT
) {
481 struct cast_op cast_insn
;
483 if (node
->u
.binary
.left
->data_type
== IR_DATA_FIELD_REF
484 || node
->u
.binary
.left
->data_type
== IR_DATA_GET_CONTEXT_REF
485 || node
->u
.binary
.left
->data_type
== IR_DATA_FIELD_REF_INDEX
486 || node
->u
.binary
.left
->data_type
== IR_DATA_GET_CONTEXT_REF_INDEX
) {
487 cast_insn
.op
= FILTER_OP_CAST_TO_S64
;
489 cast_insn
.op
= FILTER_OP_CAST_DOUBLE_TO_S64
;
491 ret
= bytecode_push(&ctx
->bytecode
, &cast_insn
,
492 1, sizeof(cast_insn
));
496 switch (node
->u
.logical
.type
) {
498 fprintf(stderr
, "[error] Unknown node type in %s\n",
503 insn
.op
= FILTER_OP_AND
;
506 insn
.op
= FILTER_OP_OR
;
509 insn
.skip_offset
= (uint16_t) -1UL; /* Temporary */
510 ret
= bytecode_push_logical(&ctx
->bytecode
, &insn
, 1, sizeof(insn
),
514 /* Visit right child */
515 ret
= recursive_visit_gen_bytecode(ctx
, node
->u
.binary
.right
);
518 /* Cast to s64 if float or field ref */
519 if ((node
->u
.binary
.right
->data_type
== IR_DATA_FIELD_REF
520 || node
->u
.binary
.right
->data_type
== IR_DATA_GET_CONTEXT_REF
521 || node
->u
.binary
.right
->data_type
== IR_DATA_FIELD_REF_INDEX
522 || node
->u
.binary
.right
->data_type
== IR_DATA_GET_CONTEXT_REF_INDEX
)
523 || node
->u
.binary
.right
->data_type
== IR_DATA_FLOAT
) {
524 struct cast_op cast_insn
;
526 if (node
->u
.binary
.right
->data_type
== IR_DATA_FIELD_REF
527 || node
->u
.binary
.right
->data_type
== IR_DATA_GET_CONTEXT_REF
528 || node
->u
.binary
.right
->data_type
== IR_DATA_FIELD_REF_INDEX
529 || node
->u
.binary
.right
->data_type
== IR_DATA_GET_CONTEXT_REF_INDEX
) {
530 cast_insn
.op
= FILTER_OP_CAST_TO_S64
;
532 cast_insn
.op
= FILTER_OP_CAST_DOUBLE_TO_S64
;
534 ret
= bytecode_push(&ctx
->bytecode
, &cast_insn
,
535 1, sizeof(cast_insn
));
539 /* We now know where the logical op can skip. */
540 target_loc
= (uint16_t) bytecode_get_len(&ctx
->bytecode
->b
);
541 ret
= bytecode_patch(&ctx
->bytecode
,
542 &target_loc
, /* Offset to jump to */
543 skip_offset_loc
, /* Where to patch */
549 * Postorder traversal of the tree. We need the children result before
550 * we can evaluate the parent.
553 int recursive_visit_gen_bytecode(struct filter_parser_ctx
*ctx
,
559 fprintf(stderr
, "[error] Unknown node type in %s\n",
564 return visit_node_root(ctx
, node
);
566 return visit_node_load(ctx
, node
);
568 return visit_node_unary(ctx
, node
);
570 return visit_node_binary(ctx
, node
);
572 return visit_node_logical(ctx
, node
);
577 void filter_bytecode_free(struct filter_parser_ctx
*ctx
)
585 ctx
->bytecode
= NULL
;
588 if (ctx
->bytecode_reloc
) {
589 free(ctx
->bytecode_reloc
);
590 ctx
->bytecode_reloc
= NULL
;
595 int filter_visitor_bytecode_generate(struct filter_parser_ctx
*ctx
)
599 ret
= bytecode_init(&ctx
->bytecode
);
602 ret
= bytecode_init(&ctx
->bytecode_reloc
);
605 ret
= recursive_visit_gen_bytecode(ctx
, ctx
->ir_root
);
609 /* Finally, append symbol table to bytecode */
610 ctx
->bytecode
->b
.reloc_table_offset
= bytecode_get_len(&ctx
->bytecode
->b
);
611 return bytecode_push(&ctx
->bytecode
, ctx
->bytecode_reloc
->b
.data
,
612 1, bytecode_get_len(&ctx
->bytecode_reloc
->b
));
615 filter_bytecode_free(ctx
);