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
26 #include "filter-bytecode.h"
27 #include "filter-ir.h"
28 #include "filter-ast.h"
31 #define max_t(type, a, b) ((type) ((a) > (b) ? (a) : (b)))
34 //#define INIT_ALLOC_SIZE PAGE_SIZE
35 #define INIT_ALLOC_SIZE 4
38 int recursive_visit_gen_bytecode(struct filter_parser_ctx
*ctx
,
41 static inline int fls(unsigned int x
)
47 if (!(x
& 0xFFFF0000U
)) {
51 if (!(x
& 0xFF000000U
)) {
55 if (!(x
& 0xF0000000U
)) {
59 if (!(x
& 0xC0000000U
)) {
63 if (!(x
& 0x80000000U
)) {
70 static inline int get_count_order(unsigned int count
)
74 order
= fls(count
) - 1;
75 if (count
& (count
- 1))
81 int bytecode_init(struct lttng_filter_bytecode_alloc
**fb
)
83 *fb
= calloc(sizeof(struct lttng_filter_bytecode_alloc
) + INIT_ALLOC_SIZE
, 1);
87 (*fb
)->alloc_len
= INIT_ALLOC_SIZE
;
93 int32_t bytecode_reserve(struct lttng_filter_bytecode_alloc
**fb
, uint32_t align
, uint32_t len
)
96 uint32_t padding
= offset_align((*fb
)->b
.len
, align
);
98 if ((*fb
)->b
.len
+ padding
+ len
> (*fb
)->alloc_len
) {
100 max_t(uint32_t, 1U << get_count_order((*fb
)->b
.len
+ padding
+ len
),
101 (*fb
)->alloc_len
<< 1);
102 uint32_t old_len
= (*fb
)->alloc_len
;
104 if (new_len
> 0xFFFF)
106 *fb
= realloc(*fb
, sizeof(struct lttng_filter_bytecode_alloc
) + new_len
);
109 memset(&(*fb
)->b
.data
[old_len
], 0, new_len
- old_len
);
110 (*fb
)->alloc_len
= new_len
;
112 (*fb
)->b
.len
+= padding
;
119 int bytecode_push(struct lttng_filter_bytecode_alloc
**fb
, const void *data
,
120 uint32_t align
, uint32_t len
)
124 offset
= bytecode_reserve(fb
, align
, len
);
127 memcpy(&(*fb
)->b
.data
[offset
], data
, len
);
132 int bytecode_push_logical(struct lttng_filter_bytecode_alloc
**fb
,
133 struct logical_op
*data
,
134 uint32_t align
, uint32_t len
,
135 uint16_t *skip_offset
)
139 offset
= bytecode_reserve(fb
, align
, len
);
142 memcpy(&(*fb
)->b
.data
[offset
], data
, len
);
144 (void *) &((struct logical_op
*) &(*fb
)->b
.data
[offset
])->skip_offset
145 - (void *) &(*fb
)->b
.data
[0];
150 int bytecode_patch(struct lttng_filter_bytecode_alloc
**fb
,
155 if (offset
>= (*fb
)->b
.len
) {
158 memcpy(&(*fb
)->b
.data
[offset
], data
, len
);
163 int visit_node_root(struct filter_parser_ctx
*ctx
, struct ir_op
*node
)
166 struct return_op insn
;
169 ret
= recursive_visit_gen_bytecode(ctx
, node
->u
.root
.child
);
173 /* Generate end of bytecode instruction */
174 insn
.op
= FILTER_OP_RETURN
;
175 return bytecode_push(&ctx
->bytecode
, &insn
, 1, sizeof(insn
));
179 int visit_node_load(struct filter_parser_ctx
*ctx
, struct ir_op
*node
)
183 switch (node
->data_type
) {
184 case IR_DATA_UNKNOWN
:
186 fprintf(stderr
, "[error] Unknown data type in %s\n",
192 struct load_op
*insn
;
193 uint32_t insn_len
= sizeof(struct load_op
)
194 + strlen(node
->u
.load
.u
.string
) + 1;
196 insn
= calloc(insn_len
, 1);
199 insn
->op
= FILTER_OP_LOAD_STRING
;
200 strcpy(insn
->data
, node
->u
.load
.u
.string
);
201 ret
= bytecode_push(&ctx
->bytecode
, insn
, 1, insn_len
);
205 case IR_DATA_NUMERIC
:
207 struct load_op
*insn
;
208 uint32_t insn_len
= sizeof(struct load_op
)
209 + sizeof(struct literal_numeric
);
211 insn
= calloc(insn_len
, 1);
214 insn
->op
= FILTER_OP_LOAD_S64
;
215 *(int64_t *) insn
->data
= node
->u
.load
.u
.num
;
216 ret
= bytecode_push(&ctx
->bytecode
, insn
, 1, insn_len
);
222 struct load_op
*insn
;
223 uint32_t insn_len
= sizeof(struct load_op
)
224 + sizeof(struct literal_double
);
226 insn
= calloc(insn_len
, 1);
229 insn
->op
= FILTER_OP_LOAD_DOUBLE
;
230 *(double *) insn
->data
= node
->u
.load
.u
.flt
;
231 ret
= bytecode_push(&ctx
->bytecode
, insn
, 1, insn_len
);
235 case IR_DATA_FIELD_REF
:
237 struct load_op
*insn
;
238 uint32_t insn_len
= sizeof(struct load_op
)
239 + sizeof(struct field_ref
);
240 struct field_ref ref_offset
;
241 uint16_t reloc_offset
;
243 insn
= calloc(insn_len
, 1);
246 insn
->op
= FILTER_OP_LOAD_FIELD_REF
;
247 ref_offset
.offset
= (uint16_t) -1U;
248 memcpy(insn
->data
, &ref_offset
, sizeof(ref_offset
));
249 /* reloc_offset points to struct load_op */
250 reloc_offset
= bytecode_get_len(&ctx
->bytecode
->b
);
251 ret
= bytecode_push(&ctx
->bytecode
, insn
, 1, insn_len
);
257 ret
= bytecode_push(&ctx
->bytecode_reloc
, &reloc_offset
,
258 1, sizeof(reloc_offset
));
263 ret
= bytecode_push(&ctx
->bytecode_reloc
, node
->u
.load
.u
.ref
,
264 1, strlen(node
->u
.load
.u
.ref
) + 1);
272 int visit_node_unary(struct filter_parser_ctx
*ctx
, struct ir_op
*node
)
275 struct unary_op insn
;
278 ret
= recursive_visit_gen_bytecode(ctx
, node
->u
.unary
.child
);
282 /* Generate end of bytecode instruction */
283 switch (node
->u
.unary
.type
) {
284 case AST_UNARY_UNKNOWN
:
286 fprintf(stderr
, "[error] Unknown unary node type in %s\n",
292 case AST_UNARY_MINUS
:
293 insn
.op
= FILTER_OP_UNARY_MINUS
;
294 return bytecode_push(&ctx
->bytecode
, &insn
, 1, sizeof(insn
));
296 insn
.op
= FILTER_OP_UNARY_NOT
;
297 return bytecode_push(&ctx
->bytecode
, &insn
, 1, sizeof(insn
));
302 * Binary comparator nesting is disallowed. This allows fitting into
306 int visit_node_binary(struct filter_parser_ctx
*ctx
, struct ir_op
*node
)
309 struct binary_op insn
;
312 ret
= recursive_visit_gen_bytecode(ctx
, node
->u
.binary
.left
);
315 ret
= recursive_visit_gen_bytecode(ctx
, node
->u
.binary
.right
);
319 switch (node
->u
.binary
.type
) {
322 fprintf(stderr
, "[error] Unknown unary node type in %s\n",
328 fprintf(stderr
, "[error] Unexpected logical node type in %s\n",
333 insn
.op
= FILTER_OP_MUL
;
336 insn
.op
= FILTER_OP_DIV
;
339 insn
.op
= FILTER_OP_MOD
;
342 insn
.op
= FILTER_OP_PLUS
;
345 insn
.op
= FILTER_OP_MINUS
;
348 insn
.op
= FILTER_OP_RSHIFT
;
351 insn
.op
= FILTER_OP_LSHIFT
;
354 insn
.op
= FILTER_OP_BIN_AND
;
357 insn
.op
= FILTER_OP_BIN_OR
;
360 insn
.op
= FILTER_OP_BIN_XOR
;
364 insn
.op
= FILTER_OP_EQ
;
367 insn
.op
= FILTER_OP_NE
;
370 insn
.op
= FILTER_OP_GT
;
373 insn
.op
= FILTER_OP_LT
;
376 insn
.op
= FILTER_OP_GE
;
379 insn
.op
= FILTER_OP_LE
;
382 return bytecode_push(&ctx
->bytecode
, &insn
, 1, sizeof(insn
));
386 * A logical op always return a s64 (1 or 0).
389 int visit_node_logical(struct filter_parser_ctx
*ctx
, struct ir_op
*node
)
392 struct logical_op insn
;
393 uint16_t skip_offset_loc
;
396 /* Visit left child */
397 ret
= recursive_visit_gen_bytecode(ctx
, node
->u
.binary
.left
);
400 /* Cast to s64 if float or field ref */
401 if (node
->u
.binary
.left
->data_type
== IR_DATA_FIELD_REF
402 || node
->u
.binary
.left
->data_type
== IR_DATA_FLOAT
) {
403 struct cast_op cast_insn
;
405 if (node
->u
.binary
.left
->data_type
== IR_DATA_FIELD_REF
) {
406 cast_insn
.op
= FILTER_OP_CAST_TO_S64
;
408 cast_insn
.op
= FILTER_OP_CAST_DOUBLE_TO_S64
;
410 ret
= bytecode_push(&ctx
->bytecode
, &cast_insn
,
411 1, sizeof(cast_insn
));
415 switch (node
->u
.logical
.type
) {
417 fprintf(stderr
, "[error] Unknown node type in %s\n",
422 insn
.op
= FILTER_OP_AND
;
425 insn
.op
= FILTER_OP_OR
;
428 insn
.skip_offset
= (uint16_t) -1UL; /* Temporary */
429 ret
= bytecode_push_logical(&ctx
->bytecode
, &insn
, 1, sizeof(insn
),
433 /* Visit right child */
434 ret
= recursive_visit_gen_bytecode(ctx
, node
->u
.binary
.right
);
437 /* Cast to s64 if float or field ref */
438 if (node
->u
.binary
.right
->data_type
== IR_DATA_FIELD_REF
439 || node
->u
.binary
.right
->data_type
== IR_DATA_FLOAT
) {
440 struct cast_op cast_insn
;
442 if (node
->u
.binary
.right
->data_type
== IR_DATA_FIELD_REF
) {
443 cast_insn
.op
= FILTER_OP_CAST_TO_S64
;
445 cast_insn
.op
= FILTER_OP_CAST_DOUBLE_TO_S64
;
447 ret
= bytecode_push(&ctx
->bytecode
, &cast_insn
,
448 1, sizeof(cast_insn
));
452 /* We now know where the logical op can skip. */
453 target_loc
= (uint16_t) bytecode_get_len(&ctx
->bytecode
->b
);
454 ret
= bytecode_patch(&ctx
->bytecode
,
455 &target_loc
, /* Offset to jump to */
456 skip_offset_loc
, /* Where to patch */
462 * Postorder traversal of the tree. We need the children result before
463 * we can evaluate the parent.
466 int recursive_visit_gen_bytecode(struct filter_parser_ctx
*ctx
,
472 fprintf(stderr
, "[error] Unknown node type in %s\n",
477 return visit_node_root(ctx
, node
);
479 return visit_node_load(ctx
, node
);
481 return visit_node_unary(ctx
, node
);
483 return visit_node_binary(ctx
, node
);
485 return visit_node_logical(ctx
, node
);
489 __attribute__((visibility("hidden")))
490 void filter_bytecode_free(struct filter_parser_ctx
*ctx
)
493 ctx
->bytecode
= NULL
;
494 free(ctx
->bytecode_reloc
);
495 ctx
->bytecode_reloc
= NULL
;
498 __attribute__((visibility("hidden")))
499 int filter_visitor_bytecode_generate(struct filter_parser_ctx
*ctx
)
503 ret
= bytecode_init(&ctx
->bytecode
);
506 ret
= bytecode_init(&ctx
->bytecode_reloc
);
509 ret
= recursive_visit_gen_bytecode(ctx
, ctx
->ir_root
);
513 /* Finally, append symbol table to bytecode */
514 ctx
->bytecode
->b
.reloc_table_offset
= bytecode_get_len(&ctx
->bytecode
->b
);
515 return bytecode_push(&ctx
->bytecode
, ctx
->bytecode_reloc
->b
.data
,
516 1, bytecode_get_len(&ctx
->bytecode_reloc
->b
));
519 filter_bytecode_free(ctx
);