Filter: index array, sequences, implement bitwise binary operators
[lttng-tools.git] / src / lib / lttng-ctl / filter / filter-visitor-generate-bytecode.c
CommitLineData
953192ba
MD
1/*
2 * filter-visitor-generate-bytecode.c
3 *
4 * LTTng filter bytecode generation
5 *
6 * Copyright 2012 - Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
7 *
8 * This library is free software; you can redistribute it and/or modify it
9 * under the terms of the GNU Lesser General Public License, version 2.1 only,
10 * as published by the Free Software Foundation.
11 *
12 * This library is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 * Lesser General Public License for more details.
16 *
17 * You should have received a copy of the GNU Lesser General Public License
18 * along with this library; if not, write to the Free Software Foundation,
19 * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
20 */
21
22#include <stdlib.h>
23#include <string.h>
24#include <errno.h>
46820c8b 25#include <common/align.h>
afc5df03 26#include <common/compat/string.h>
46820c8b 27
953192ba
MD
28#include "filter-bytecode.h"
29#include "filter-ir.h"
30#include "filter-ast.h"
31
a187da1a
DG
32#include <common/macros.h>
33
953192ba
MD
34#ifndef max_t
35#define max_t(type, a, b) ((type) ((a) > (b) ? (a) : (b)))
36#endif
37
953192ba
MD
38#define INIT_ALLOC_SIZE 4
39
40static
41int recursive_visit_gen_bytecode(struct filter_parser_ctx *ctx,
42 struct ir_op *node);
43
01a204f0
CB
44static inline int get_count_order(unsigned int count)
45{
46 int order;
47
afc5df03 48 order = lttng_fls(count) - 1;
01a204f0
CB
49 if (count & (count - 1))
50 order++;
51 return order;
52}
53
953192ba 54static
53a80697 55int bytecode_init(struct lttng_filter_bytecode_alloc **fb)
953192ba 56{
1029587a
MD
57 uint32_t alloc_len;
58
59 alloc_len = sizeof(struct lttng_filter_bytecode_alloc) + INIT_ALLOC_SIZE;
60 *fb = calloc(alloc_len, 1);
953192ba
MD
61 if (!*fb) {
62 return -ENOMEM;
63 } else {
1029587a 64 (*fb)->alloc_len = alloc_len;
953192ba
MD
65 return 0;
66 }
67}
68
69static
53a80697 70int32_t bytecode_reserve(struct lttng_filter_bytecode_alloc **fb, uint32_t align, uint32_t len)
953192ba
MD
71{
72 int32_t ret;
73 uint32_t padding = offset_align((*fb)->b.len, align);
ec96a8f6 74 uint32_t new_len = (*fb)->b.len + padding + len;
1029587a 75 uint32_t new_alloc_len = sizeof(struct lttng_filter_bytecode_alloc) + new_len;
ec96a8f6 76 uint32_t old_alloc_len = (*fb)->alloc_len;
953192ba 77
ec96a8f6 78 if (new_len > LTTNG_FILTER_MAX_LEN)
5ddb0a08
CB
79 return -EINVAL;
80
ec96a8f6 81 if (new_alloc_len > old_alloc_len) {
d0b96690
DG
82 struct lttng_filter_bytecode_alloc *newptr;
83
ec96a8f6
MD
84 new_alloc_len =
85 max_t(uint32_t, 1U << get_count_order(new_alloc_len), old_alloc_len << 1);
d0b96690
DG
86 newptr = realloc(*fb, new_alloc_len);
87 if (!newptr)
953192ba 88 return -ENOMEM;
d0b96690 89 *fb = newptr;
1029587a 90 /* We zero directly the memory from start of allocation. */
ec96a8f6
MD
91 memset(&((char *) *fb)[old_alloc_len], 0, new_alloc_len - old_alloc_len);
92 (*fb)->alloc_len = new_alloc_len;
953192ba
MD
93 }
94 (*fb)->b.len += padding;
95 ret = (*fb)->b.len;
96 (*fb)->b.len += len;
97 return ret;
98}
99
100static
53a80697 101int bytecode_push(struct lttng_filter_bytecode_alloc **fb, const void *data,
953192ba
MD
102 uint32_t align, uint32_t len)
103{
104 int32_t offset;
105
106 offset = bytecode_reserve(fb, align, len);
107 if (offset < 0)
108 return offset;
109 memcpy(&(*fb)->b.data[offset], data, len);
110 return 0;
111}
112
113static
53a80697 114int bytecode_push_logical(struct lttng_filter_bytecode_alloc **fb,
953192ba
MD
115 struct logical_op *data,
116 uint32_t align, uint32_t len,
117 uint16_t *skip_offset)
118{
119 int32_t offset;
120
121 offset = bytecode_reserve(fb, align, len);
122 if (offset < 0)
123 return offset;
124 memcpy(&(*fb)->b.data[offset], data, len);
125 *skip_offset =
126 (void *) &((struct logical_op *) &(*fb)->b.data[offset])->skip_offset
127 - (void *) &(*fb)->b.data[0];
128 return 0;
129}
130
131static
53a80697 132int bytecode_patch(struct lttng_filter_bytecode_alloc **fb,
953192ba
MD
133 const void *data,
134 uint16_t offset,
135 uint32_t len)
136{
137 if (offset >= (*fb)->b.len) {
138 return -EINVAL;
139 }
140 memcpy(&(*fb)->b.data[offset], data, len);
141 return 0;
142}
143
144static
145int visit_node_root(struct filter_parser_ctx *ctx, struct ir_op *node)
146{
147 int ret;
148 struct return_op insn;
149
150 /* Visit child */
151 ret = recursive_visit_gen_bytecode(ctx, node->u.root.child);
152 if (ret)
153 return ret;
154
155 /* Generate end of bytecode instruction */
156 insn.op = FILTER_OP_RETURN;
157 return bytecode_push(&ctx->bytecode, &insn, 1, sizeof(insn));
158}
159
bff988fa
MD
160static
161int visit_node_load_expression(struct filter_parser_ctx *ctx,
162 const struct ir_op *node)
163{
164 struct ir_load_expression *exp;
165 struct ir_load_expression_op *op;
166
167 exp = node->u.load.u.expression;
168 if (!exp) {
169 return -EINVAL;
170 }
171 op = exp->child;
172 if (!op) {
173 return -EINVAL;
174 }
175 for (; op != NULL; op = op->next) {
176 switch (op->type) {
177 case IR_LOAD_EXPRESSION_GET_CONTEXT_ROOT:
178 {
179 struct load_op *insn;
180 uint32_t insn_len = sizeof(struct load_op);
181 int ret;
182
183 insn = calloc(insn_len, 1);
184 if (!insn)
185 return -ENOMEM;
186 insn->op = FILTER_OP_GET_CONTEXT_ROOT;
187 ret = bytecode_push(&ctx->bytecode, insn, 1, insn_len);
188 free(insn);
189 if (ret) {
190 return ret;
191 }
192 break;
193 }
194 case IR_LOAD_EXPRESSION_GET_APP_CONTEXT_ROOT:
195 {
196 struct load_op *insn;
197 uint32_t insn_len = sizeof(struct load_op);
198 int ret;
199
200 insn = calloc(insn_len, 1);
201 if (!insn)
202 return -ENOMEM;
203 insn->op = FILTER_OP_GET_APP_CONTEXT_ROOT;
204 ret = bytecode_push(&ctx->bytecode, insn, 1, insn_len);
205 free(insn);
206 if (ret) {
207 return ret;
208 }
209 break;
210 }
211 case IR_LOAD_EXPRESSION_GET_PAYLOAD_ROOT:
212 {
213 struct load_op *insn;
214 uint32_t insn_len = sizeof(struct load_op);
215 int ret;
216
217 insn = calloc(insn_len, 1);
218 if (!insn)
219 return -ENOMEM;
220 insn->op = FILTER_OP_GET_PAYLOAD_ROOT;
221 ret = bytecode_push(&ctx->bytecode, insn, 1, insn_len);
222 free(insn);
223 if (ret) {
224 return ret;
225 }
226 break;
227 }
228 case IR_LOAD_EXPRESSION_GET_SYMBOL:
229 {
230 struct load_op *insn;
231 uint32_t insn_len = sizeof(struct load_op)
232 + sizeof(struct get_symbol);
233 struct get_symbol symbol_offset;
234 uint32_t reloc_offset_u32;
235 uint16_t reloc_offset;
236 uint32_t bytecode_reloc_offset_u32;
237 int ret;
238
239 insn = calloc(insn_len, 1);
240 if (!insn)
241 return -ENOMEM;
242 insn->op = FILTER_OP_GET_SYMBOL;
243 bytecode_reloc_offset_u32 =
244 bytecode_get_len(&ctx->bytecode_reloc->b)
245 + sizeof(reloc_offset);
246 symbol_offset.offset =
247 (uint16_t) bytecode_reloc_offset_u32;
248 memcpy(insn->data, &symbol_offset,
249 sizeof(symbol_offset));
250 /* reloc_offset points to struct load_op */
251 reloc_offset_u32 = bytecode_get_len(&ctx->bytecode->b);
252 if (reloc_offset_u32 > LTTNG_FILTER_MAX_LEN - 1) {
253 free(insn);
254 return -EINVAL;
255 }
256 reloc_offset = (uint16_t) reloc_offset_u32;
257 ret = bytecode_push(&ctx->bytecode, insn, 1, insn_len);
258 if (ret) {
259 free(insn);
260 return ret;
261 }
262 /* append reloc */
263 ret = bytecode_push(&ctx->bytecode_reloc, &reloc_offset,
264 1, sizeof(reloc_offset));
265 if (ret) {
266 free(insn);
267 return ret;
268 }
269 ret = bytecode_push(&ctx->bytecode_reloc,
270 op->u.symbol,
271 1, strlen(op->u.symbol) + 1);
272 free(insn);
273 if (ret) {
274 return ret;
275 }
276 break;
277 }
278 case IR_LOAD_EXPRESSION_GET_INDEX:
279 {
280 struct load_op *insn;
281 uint32_t insn_len = sizeof(struct load_op)
282 + sizeof(struct get_index_u64);
283 struct get_index_u64 index;
284 int ret;
285
286 insn = calloc(insn_len, 1);
287 if (!insn)
288 return -ENOMEM;
289 insn->op = FILTER_OP_GET_INDEX_U64;
290 index.index = op->u.index;
291 memcpy(insn->data, &index, sizeof(index));
292 ret = bytecode_push(&ctx->bytecode, insn, 1, insn_len);
293 free(insn);
294 if (ret) {
295 return ret;
296 }
297 break;
298 }
299 case IR_LOAD_EXPRESSION_LOAD_FIELD:
300 {
301 struct load_op *insn;
302 uint32_t insn_len = sizeof(struct load_op);
303 int ret;
304
305 insn = calloc(insn_len, 1);
306 if (!insn)
307 return -ENOMEM;
308 insn->op = FILTER_OP_LOAD_FIELD;
309 ret = bytecode_push(&ctx->bytecode, insn, 1, insn_len);
310 free(insn);
311 if (ret) {
312 return ret;
313 }
314 break;
315 }
316 }
317 }
318 return 0;
319}
320
953192ba
MD
321static
322int visit_node_load(struct filter_parser_ctx *ctx, struct ir_op *node)
323{
324 int ret;
325
326 switch (node->data_type) {
327 case IR_DATA_UNKNOWN:
328 default:
329 fprintf(stderr, "[error] Unknown data type in %s\n",
330 __func__);
331 return -EINVAL;
332
333 case IR_DATA_STRING:
334 {
335 struct load_op *insn;
336 uint32_t insn_len = sizeof(struct load_op)
9f449915 337 + strlen(node->u.load.u.string.value) + 1;
953192ba
MD
338
339 insn = calloc(insn_len, 1);
340 if (!insn)
341 return -ENOMEM;
9f449915
PP
342
343 switch (node->u.load.u.string.type) {
344 case IR_LOAD_STRING_TYPE_GLOB_STAR:
345 /*
346 * We explicitly tell the interpreter here that
347 * this load is a full star globbing pattern so
348 * that the appropriate matching function can be
349 * called. Also, see comment below.
350 */
351 insn->op = FILTER_OP_LOAD_STAR_GLOB_STRING;
352 break;
353 default:
354 /*
355 * This is the "legacy" string, which includes
356 * star globbing patterns with a star only at
357 * the end. Both "plain" and "star at the end"
358 * literal strings are handled at the same place
359 * by the tracer's filter bytecode interpreter,
360 * whereas full star globbing patterns (stars
361 * can be anywhere in the string) is a special
362 * case.
363 */
364 insn->op = FILTER_OP_LOAD_STRING;
365 break;
366 }
367
368 strcpy(insn->data, node->u.load.u.string.value);
953192ba
MD
369 ret = bytecode_push(&ctx->bytecode, insn, 1, insn_len);
370 free(insn);
371 return ret;
372 }
373 case IR_DATA_NUMERIC:
374 {
375 struct load_op *insn;
376 uint32_t insn_len = sizeof(struct load_op)
377 + sizeof(struct literal_numeric);
378
379 insn = calloc(insn_len, 1);
380 if (!insn)
381 return -ENOMEM;
382 insn->op = FILTER_OP_LOAD_S64;
58d494e4 383 memcpy(insn->data, &node->u.load.u.num, sizeof(int64_t));
953192ba
MD
384 ret = bytecode_push(&ctx->bytecode, insn, 1, insn_len);
385 free(insn);
386 return ret;
387 }
e90d8561
MD
388 case IR_DATA_FLOAT:
389 {
390 struct load_op *insn;
391 uint32_t insn_len = sizeof(struct load_op)
392 + sizeof(struct literal_double);
393
394 insn = calloc(insn_len, 1);
395 if (!insn)
396 return -ENOMEM;
397 insn->op = FILTER_OP_LOAD_DOUBLE;
58d494e4 398 memcpy(insn->data, &node->u.load.u.flt, sizeof(double));
e90d8561
MD
399 ret = bytecode_push(&ctx->bytecode, insn, 1, insn_len);
400 free(insn);
401 return ret;
402 }
bff988fa
MD
403 case IR_DATA_EXPRESSION:
404 return visit_node_load_expression(ctx, node);
953192ba
MD
405 }
406}
407
408static
409int visit_node_unary(struct filter_parser_ctx *ctx, struct ir_op *node)
410{
411 int ret;
412 struct unary_op insn;
413
414 /* Visit child */
415 ret = recursive_visit_gen_bytecode(ctx, node->u.unary.child);
416 if (ret)
417 return ret;
418
419 /* Generate end of bytecode instruction */
420 switch (node->u.unary.type) {
421 case AST_UNARY_UNKNOWN:
422 default:
423 fprintf(stderr, "[error] Unknown unary node type in %s\n",
424 __func__);
425 return -EINVAL;
426 case AST_UNARY_PLUS:
427 /* Nothing to do. */
428 return 0;
429 case AST_UNARY_MINUS:
430 insn.op = FILTER_OP_UNARY_MINUS;
953192ba
MD
431 return bytecode_push(&ctx->bytecode, &insn, 1, sizeof(insn));
432 case AST_UNARY_NOT:
433 insn.op = FILTER_OP_UNARY_NOT;
953192ba
MD
434 return bytecode_push(&ctx->bytecode, &insn, 1, sizeof(insn));
435 }
436}
437
438/*
439 * Binary comparator nesting is disallowed. This allows fitting into
440 * only 2 registers.
441 */
442static
443int visit_node_binary(struct filter_parser_ctx *ctx, struct ir_op *node)
444{
445 int ret;
446 struct binary_op insn;
447
448 /* Visit child */
449 ret = recursive_visit_gen_bytecode(ctx, node->u.binary.left);
450 if (ret)
451 return ret;
452 ret = recursive_visit_gen_bytecode(ctx, node->u.binary.right);
453 if (ret)
454 return ret;
455
456 switch (node->u.binary.type) {
457 case AST_OP_UNKNOWN:
458 default:
459 fprintf(stderr, "[error] Unknown unary node type in %s\n",
460 __func__);
461 return -EINVAL;
462
463 case AST_OP_AND:
464 case AST_OP_OR:
465 fprintf(stderr, "[error] Unexpected logical node type in %s\n",
466 __func__);
467 return -EINVAL;
468
469 case AST_OP_MUL:
470 insn.op = FILTER_OP_MUL;
471 break;
472 case AST_OP_DIV:
473 insn.op = FILTER_OP_DIV;
474 break;
475 case AST_OP_MOD:
476 insn.op = FILTER_OP_MOD;
477 break;
478 case AST_OP_PLUS:
479 insn.op = FILTER_OP_PLUS;
480 break;
481 case AST_OP_MINUS:
482 insn.op = FILTER_OP_MINUS;
483 break;
484 case AST_OP_RSHIFT:
485 insn.op = FILTER_OP_RSHIFT;
486 break;
487 case AST_OP_LSHIFT:
488 insn.op = FILTER_OP_LSHIFT;
489 break;
bff988fa
MD
490 case AST_OP_BIT_AND:
491 insn.op = FILTER_OP_BIT_AND;
953192ba 492 break;
bff988fa
MD
493 case AST_OP_BIT_OR:
494 insn.op = FILTER_OP_BIT_OR;
953192ba 495 break;
bff988fa
MD
496 case AST_OP_BIT_XOR:
497 insn.op = FILTER_OP_BIT_XOR;
953192ba
MD
498 break;
499
500 case AST_OP_EQ:
501 insn.op = FILTER_OP_EQ;
502 break;
503 case AST_OP_NE:
504 insn.op = FILTER_OP_NE;
505 break;
506 case AST_OP_GT:
507 insn.op = FILTER_OP_GT;
508 break;
509 case AST_OP_LT:
510 insn.op = FILTER_OP_LT;
511 break;
512 case AST_OP_GE:
513 insn.op = FILTER_OP_GE;
514 break;
515 case AST_OP_LE:
516 insn.op = FILTER_OP_LE;
517 break;
518 }
519 return bytecode_push(&ctx->bytecode, &insn, 1, sizeof(insn));
520}
521
8cf9540a
MD
522/*
523 * A logical op always return a s64 (1 or 0).
524 */
953192ba
MD
525static
526int visit_node_logical(struct filter_parser_ctx *ctx, struct ir_op *node)
527{
528 int ret;
529 struct logical_op insn;
530 uint16_t skip_offset_loc;
531 uint16_t target_loc;
532
533 /* Visit left child */
534 ret = recursive_visit_gen_bytecode(ctx, node->u.binary.left);
535 if (ret)
536 return ret;
8cf9540a 537 /* Cast to s64 if float or field ref */
586dc72f 538 if ((node->u.binary.left->data_type == IR_DATA_FIELD_REF
661dfdd1 539 || node->u.binary.left->data_type == IR_DATA_GET_CONTEXT_REF
bff988fa 540 || node->u.binary.left->data_type == IR_DATA_EXPRESSION)
8cf9540a
MD
541 || node->u.binary.left->data_type == IR_DATA_FLOAT) {
542 struct cast_op cast_insn;
543
586dc72f 544 if (node->u.binary.left->data_type == IR_DATA_FIELD_REF
661dfdd1 545 || node->u.binary.left->data_type == IR_DATA_GET_CONTEXT_REF
bff988fa 546 || node->u.binary.left->data_type == IR_DATA_EXPRESSION) {
29fefef8
MD
547 cast_insn.op = FILTER_OP_CAST_TO_S64;
548 } else {
549 cast_insn.op = FILTER_OP_CAST_DOUBLE_TO_S64;
550 }
8cf9540a
MD
551 ret = bytecode_push(&ctx->bytecode, &cast_insn,
552 1, sizeof(cast_insn));
553 if (ret)
554 return ret;
555 }
953192ba
MD
556 switch (node->u.logical.type) {
557 default:
558 fprintf(stderr, "[error] Unknown node type in %s\n",
559 __func__);
560 return -EINVAL;
561
562 case AST_OP_AND:
563 insn.op = FILTER_OP_AND;
564 break;
565 case AST_OP_OR:
566 insn.op = FILTER_OP_OR;
567 break;
568 }
569 insn.skip_offset = (uint16_t) -1UL; /* Temporary */
570 ret = bytecode_push_logical(&ctx->bytecode, &insn, 1, sizeof(insn),
571 &skip_offset_loc);
572 if (ret)
573 return ret;
574 /* Visit right child */
575 ret = recursive_visit_gen_bytecode(ctx, node->u.binary.right);
576 if (ret)
577 return ret;
8cf9540a 578 /* Cast to s64 if float or field ref */
586dc72f 579 if ((node->u.binary.right->data_type == IR_DATA_FIELD_REF
661dfdd1 580 || node->u.binary.right->data_type == IR_DATA_GET_CONTEXT_REF
bff988fa 581 || node->u.binary.right->data_type == IR_DATA_EXPRESSION)
8cf9540a
MD
582 || node->u.binary.right->data_type == IR_DATA_FLOAT) {
583 struct cast_op cast_insn;
584
586dc72f 585 if (node->u.binary.right->data_type == IR_DATA_FIELD_REF
661dfdd1 586 || node->u.binary.right->data_type == IR_DATA_GET_CONTEXT_REF
bff988fa 587 || node->u.binary.right->data_type == IR_DATA_EXPRESSION) {
29fefef8
MD
588 cast_insn.op = FILTER_OP_CAST_TO_S64;
589 } else {
590 cast_insn.op = FILTER_OP_CAST_DOUBLE_TO_S64;
591 }
8cf9540a
MD
592 ret = bytecode_push(&ctx->bytecode, &cast_insn,
593 1, sizeof(cast_insn));
594 if (ret)
595 return ret;
596 }
953192ba
MD
597 /* We now know where the logical op can skip. */
598 target_loc = (uint16_t) bytecode_get_len(&ctx->bytecode->b);
599 ret = bytecode_patch(&ctx->bytecode,
600 &target_loc, /* Offset to jump to */
601 skip_offset_loc, /* Where to patch */
602 sizeof(uint16_t));
603 return ret;
604}
605
606/*
607 * Postorder traversal of the tree. We need the children result before
608 * we can evaluate the parent.
609 */
610static
611int recursive_visit_gen_bytecode(struct filter_parser_ctx *ctx,
612 struct ir_op *node)
613{
614 switch (node->op) {
615 case IR_OP_UNKNOWN:
616 default:
617 fprintf(stderr, "[error] Unknown node type in %s\n",
618 __func__);
619 return -EINVAL;
620
621 case IR_OP_ROOT:
622 return visit_node_root(ctx, node);
623 case IR_OP_LOAD:
624 return visit_node_load(ctx, node);
625 case IR_OP_UNARY:
626 return visit_node_unary(ctx, node);
627 case IR_OP_BINARY:
628 return visit_node_binary(ctx, node);
629 case IR_OP_LOGICAL:
630 return visit_node_logical(ctx, node);
631 }
632}
633
a187da1a 634LTTNG_HIDDEN
953192ba
MD
635void filter_bytecode_free(struct filter_parser_ctx *ctx)
636{
7ca1dc6f
DG
637 if (!ctx) {
638 return;
639 }
640
3f0c8837
DG
641 if (ctx->bytecode) {
642 free(ctx->bytecode);
643 ctx->bytecode = NULL;
644 }
645
646 if (ctx->bytecode_reloc) {
647 free(ctx->bytecode_reloc);
648 ctx->bytecode_reloc = NULL;
649 }
953192ba
MD
650}
651
a187da1a 652LTTNG_HIDDEN
953192ba
MD
653int filter_visitor_bytecode_generate(struct filter_parser_ctx *ctx)
654{
655 int ret;
656
657 ret = bytecode_init(&ctx->bytecode);
658 if (ret)
659 return ret;
660 ret = bytecode_init(&ctx->bytecode_reloc);
661 if (ret)
662 goto error;
663 ret = recursive_visit_gen_bytecode(ctx, ctx->ir_root);
664 if (ret)
665 goto error;
666
667 /* Finally, append symbol table to bytecode */
668 ctx->bytecode->b.reloc_table_offset = bytecode_get_len(&ctx->bytecode->b);
669 return bytecode_push(&ctx->bytecode, ctx->bytecode_reloc->b.data,
670 1, bytecode_get_len(&ctx->bytecode_reloc->b));
671
672error:
673 filter_bytecode_free(ctx);
674 return ret;
675}
This page took 0.10653 seconds and 4 git commands to generate.