Implement per-context filtering
[lttng-tools.git] / src / lib / lttng-ctl / filter / filter-visitor-generate-bytecode.c
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>
25 #include "align.h"
26 #include "filter-bytecode.h"
27 #include "filter-ir.h"
28 #include "filter-ast.h"
29
30 #include <common/macros.h>
31
32 #ifndef max_t
33 #define max_t(type, a, b) ((type) ((a) > (b) ? (a) : (b)))
34 #endif
35
36 //#define INIT_ALLOC_SIZE PAGE_SIZE
37 #define INIT_ALLOC_SIZE 4
38
39 static
40 int recursive_visit_gen_bytecode(struct filter_parser_ctx *ctx,
41 struct ir_op *node);
42
43 static inline int fls(unsigned int x)
44 {
45 int r = 32;
46
47 if (!x)
48 return 0;
49 if (!(x & 0xFFFF0000U)) {
50 x <<= 16;
51 r -= 16;
52 }
53 if (!(x & 0xFF000000U)) {
54 x <<= 8;
55 r -= 8;
56 }
57 if (!(x & 0xF0000000U)) {
58 x <<= 4;
59 r -= 4;
60 }
61 if (!(x & 0xC0000000U)) {
62 x <<= 2;
63 r -= 2;
64 }
65 if (!(x & 0x80000000U)) {
66 x <<= 1;
67 r -= 1;
68 }
69 return r;
70 }
71
72 static inline int get_count_order(unsigned int count)
73 {
74 int order;
75
76 order = fls(count) - 1;
77 if (count & (count - 1))
78 order++;
79 return order;
80 }
81
82 static
83 int bytecode_init(struct lttng_filter_bytecode_alloc **fb)
84 {
85 uint32_t alloc_len;
86
87 alloc_len = sizeof(struct lttng_filter_bytecode_alloc) + INIT_ALLOC_SIZE;
88 *fb = calloc(alloc_len, 1);
89 if (!*fb) {
90 return -ENOMEM;
91 } else {
92 (*fb)->alloc_len = alloc_len;
93 return 0;
94 }
95 }
96
97 static
98 int32_t bytecode_reserve(struct lttng_filter_bytecode_alloc **fb, uint32_t align, uint32_t len)
99 {
100 int32_t ret;
101 uint32_t padding = offset_align((*fb)->b.len, align);
102 uint32_t new_len = (*fb)->b.len + padding + len;
103 uint32_t new_alloc_len = sizeof(struct lttng_filter_bytecode_alloc) + new_len;
104 uint32_t old_alloc_len = (*fb)->alloc_len;
105
106 if (new_len > LTTNG_FILTER_MAX_LEN)
107 return -EINVAL;
108
109 if (new_alloc_len > old_alloc_len) {
110 struct lttng_filter_bytecode_alloc *newptr;
111
112 new_alloc_len =
113 max_t(uint32_t, 1U << get_count_order(new_alloc_len), old_alloc_len << 1);
114 newptr = realloc(*fb, new_alloc_len);
115 if (!newptr)
116 return -ENOMEM;
117 *fb = newptr;
118 /* We zero directly the memory from start of allocation. */
119 memset(&((char *) *fb)[old_alloc_len], 0, new_alloc_len - old_alloc_len);
120 (*fb)->alloc_len = new_alloc_len;
121 }
122 (*fb)->b.len += padding;
123 ret = (*fb)->b.len;
124 (*fb)->b.len += len;
125 return ret;
126 }
127
128 static
129 int bytecode_push(struct lttng_filter_bytecode_alloc **fb, const void *data,
130 uint32_t align, uint32_t len)
131 {
132 int32_t offset;
133
134 offset = bytecode_reserve(fb, align, len);
135 if (offset < 0)
136 return offset;
137 memcpy(&(*fb)->b.data[offset], data, len);
138 return 0;
139 }
140
141 static
142 int bytecode_push_logical(struct lttng_filter_bytecode_alloc **fb,
143 struct logical_op *data,
144 uint32_t align, uint32_t len,
145 uint16_t *skip_offset)
146 {
147 int32_t offset;
148
149 offset = bytecode_reserve(fb, align, len);
150 if (offset < 0)
151 return offset;
152 memcpy(&(*fb)->b.data[offset], data, len);
153 *skip_offset =
154 (void *) &((struct logical_op *) &(*fb)->b.data[offset])->skip_offset
155 - (void *) &(*fb)->b.data[0];
156 return 0;
157 }
158
159 static
160 int bytecode_patch(struct lttng_filter_bytecode_alloc **fb,
161 const void *data,
162 uint16_t offset,
163 uint32_t len)
164 {
165 if (offset >= (*fb)->b.len) {
166 return -EINVAL;
167 }
168 memcpy(&(*fb)->b.data[offset], data, len);
169 return 0;
170 }
171
172 static
173 int visit_node_root(struct filter_parser_ctx *ctx, struct ir_op *node)
174 {
175 int ret;
176 struct return_op insn;
177
178 /* Visit child */
179 ret = recursive_visit_gen_bytecode(ctx, node->u.root.child);
180 if (ret)
181 return ret;
182
183 /* Generate end of bytecode instruction */
184 insn.op = FILTER_OP_RETURN;
185 return bytecode_push(&ctx->bytecode, &insn, 1, sizeof(insn));
186 }
187
188 static
189 int visit_node_load(struct filter_parser_ctx *ctx, struct ir_op *node)
190 {
191 int ret;
192
193 switch (node->data_type) {
194 case IR_DATA_UNKNOWN:
195 default:
196 fprintf(stderr, "[error] Unknown data type in %s\n",
197 __func__);
198 return -EINVAL;
199
200 case IR_DATA_STRING:
201 {
202 struct load_op *insn;
203 uint32_t insn_len = sizeof(struct load_op)
204 + strlen(node->u.load.u.string) + 1;
205
206 insn = calloc(insn_len, 1);
207 if (!insn)
208 return -ENOMEM;
209 insn->op = FILTER_OP_LOAD_STRING;
210 strcpy(insn->data, node->u.load.u.string);
211 ret = bytecode_push(&ctx->bytecode, insn, 1, insn_len);
212 free(insn);
213 return ret;
214 }
215 case IR_DATA_NUMERIC:
216 {
217 struct load_op *insn;
218 uint32_t insn_len = sizeof(struct load_op)
219 + sizeof(struct literal_numeric);
220
221 insn = calloc(insn_len, 1);
222 if (!insn)
223 return -ENOMEM;
224 insn->op = FILTER_OP_LOAD_S64;
225 *(int64_t *) insn->data = node->u.load.u.num;
226 ret = bytecode_push(&ctx->bytecode, insn, 1, insn_len);
227 free(insn);
228 return ret;
229 }
230 case IR_DATA_FLOAT:
231 {
232 struct load_op *insn;
233 uint32_t insn_len = sizeof(struct load_op)
234 + sizeof(struct literal_double);
235
236 insn = calloc(insn_len, 1);
237 if (!insn)
238 return -ENOMEM;
239 insn->op = FILTER_OP_LOAD_DOUBLE;
240 *(double *) insn->data = node->u.load.u.flt;
241 ret = bytecode_push(&ctx->bytecode, insn, 1, insn_len);
242 free(insn);
243 return ret;
244 }
245 case IR_DATA_FIELD_REF: /* fall-through */
246 case IR_DATA_GET_CONTEXT_REF:
247 {
248 struct load_op *insn;
249 uint32_t insn_len = sizeof(struct load_op)
250 + sizeof(struct field_ref);
251 struct field_ref ref_offset;
252 uint32_t reloc_offset_u32;
253 uint16_t reloc_offset;
254
255 insn = calloc(insn_len, 1);
256 if (!insn)
257 return -ENOMEM;
258 switch(node->data_type) {
259 case IR_DATA_FIELD_REF:
260 insn->op = FILTER_OP_LOAD_FIELD_REF;
261 break;
262 case IR_DATA_GET_CONTEXT_REF:
263 insn->op = FILTER_OP_GET_CONTEXT_REF;
264 break;
265 default:
266 return -EINVAL;
267 }
268 ref_offset.offset = (uint16_t) -1U;
269 memcpy(insn->data, &ref_offset, sizeof(ref_offset));
270 /* reloc_offset points to struct load_op */
271 reloc_offset_u32 = bytecode_get_len(&ctx->bytecode->b);
272 if (reloc_offset_u32 > LTTNG_FILTER_MAX_LEN - 1) {
273 free(insn);
274 return -EINVAL;
275 }
276 reloc_offset = (uint16_t) reloc_offset_u32;
277 ret = bytecode_push(&ctx->bytecode, insn, 1, insn_len);
278 if (ret) {
279 free(insn);
280 return ret;
281 }
282 /* append reloc */
283 ret = bytecode_push(&ctx->bytecode_reloc, &reloc_offset,
284 1, sizeof(reloc_offset));
285 if (ret) {
286 free(insn);
287 return ret;
288 }
289 ret = bytecode_push(&ctx->bytecode_reloc, node->u.load.u.ref,
290 1, strlen(node->u.load.u.ref) + 1);
291 free(insn);
292 return ret;
293 }
294 }
295 }
296
297 static
298 int visit_node_unary(struct filter_parser_ctx *ctx, struct ir_op *node)
299 {
300 int ret;
301 struct unary_op insn;
302
303 /* Visit child */
304 ret = recursive_visit_gen_bytecode(ctx, node->u.unary.child);
305 if (ret)
306 return ret;
307
308 /* Generate end of bytecode instruction */
309 switch (node->u.unary.type) {
310 case AST_UNARY_UNKNOWN:
311 default:
312 fprintf(stderr, "[error] Unknown unary node type in %s\n",
313 __func__);
314 return -EINVAL;
315 case AST_UNARY_PLUS:
316 /* Nothing to do. */
317 return 0;
318 case AST_UNARY_MINUS:
319 insn.op = FILTER_OP_UNARY_MINUS;
320 return bytecode_push(&ctx->bytecode, &insn, 1, sizeof(insn));
321 case AST_UNARY_NOT:
322 insn.op = FILTER_OP_UNARY_NOT;
323 return bytecode_push(&ctx->bytecode, &insn, 1, sizeof(insn));
324 }
325 }
326
327 /*
328 * Binary comparator nesting is disallowed. This allows fitting into
329 * only 2 registers.
330 */
331 static
332 int visit_node_binary(struct filter_parser_ctx *ctx, struct ir_op *node)
333 {
334 int ret;
335 struct binary_op insn;
336
337 /* Visit child */
338 ret = recursive_visit_gen_bytecode(ctx, node->u.binary.left);
339 if (ret)
340 return ret;
341 ret = recursive_visit_gen_bytecode(ctx, node->u.binary.right);
342 if (ret)
343 return ret;
344
345 switch (node->u.binary.type) {
346 case AST_OP_UNKNOWN:
347 default:
348 fprintf(stderr, "[error] Unknown unary node type in %s\n",
349 __func__);
350 return -EINVAL;
351
352 case AST_OP_AND:
353 case AST_OP_OR:
354 fprintf(stderr, "[error] Unexpected logical node type in %s\n",
355 __func__);
356 return -EINVAL;
357
358 case AST_OP_MUL:
359 insn.op = FILTER_OP_MUL;
360 break;
361 case AST_OP_DIV:
362 insn.op = FILTER_OP_DIV;
363 break;
364 case AST_OP_MOD:
365 insn.op = FILTER_OP_MOD;
366 break;
367 case AST_OP_PLUS:
368 insn.op = FILTER_OP_PLUS;
369 break;
370 case AST_OP_MINUS:
371 insn.op = FILTER_OP_MINUS;
372 break;
373 case AST_OP_RSHIFT:
374 insn.op = FILTER_OP_RSHIFT;
375 break;
376 case AST_OP_LSHIFT:
377 insn.op = FILTER_OP_LSHIFT;
378 break;
379 case AST_OP_BIN_AND:
380 insn.op = FILTER_OP_BIN_AND;
381 break;
382 case AST_OP_BIN_OR:
383 insn.op = FILTER_OP_BIN_OR;
384 break;
385 case AST_OP_BIN_XOR:
386 insn.op = FILTER_OP_BIN_XOR;
387 break;
388
389 case AST_OP_EQ:
390 insn.op = FILTER_OP_EQ;
391 break;
392 case AST_OP_NE:
393 insn.op = FILTER_OP_NE;
394 break;
395 case AST_OP_GT:
396 insn.op = FILTER_OP_GT;
397 break;
398 case AST_OP_LT:
399 insn.op = FILTER_OP_LT;
400 break;
401 case AST_OP_GE:
402 insn.op = FILTER_OP_GE;
403 break;
404 case AST_OP_LE:
405 insn.op = FILTER_OP_LE;
406 break;
407 }
408 return bytecode_push(&ctx->bytecode, &insn, 1, sizeof(insn));
409 }
410
411 /*
412 * A logical op always return a s64 (1 or 0).
413 */
414 static
415 int visit_node_logical(struct filter_parser_ctx *ctx, struct ir_op *node)
416 {
417 int ret;
418 struct logical_op insn;
419 uint16_t skip_offset_loc;
420 uint16_t target_loc;
421
422 /* Visit left child */
423 ret = recursive_visit_gen_bytecode(ctx, node->u.binary.left);
424 if (ret)
425 return ret;
426 /* Cast to s64 if float or field ref */
427 if ((node->u.binary.left->data_type == IR_DATA_FIELD_REF
428 || node->u.binary.left->data_type == IR_DATA_GET_CONTEXT_REF)
429 || node->u.binary.left->data_type == IR_DATA_FLOAT) {
430 struct cast_op cast_insn;
431
432 if (node->u.binary.left->data_type == IR_DATA_FIELD_REF
433 || node->u.binary.left->data_type == IR_DATA_GET_CONTEXT_REF) {
434 cast_insn.op = FILTER_OP_CAST_TO_S64;
435 } else {
436 cast_insn.op = FILTER_OP_CAST_DOUBLE_TO_S64;
437 }
438 ret = bytecode_push(&ctx->bytecode, &cast_insn,
439 1, sizeof(cast_insn));
440 if (ret)
441 return ret;
442 }
443 switch (node->u.logical.type) {
444 default:
445 fprintf(stderr, "[error] Unknown node type in %s\n",
446 __func__);
447 return -EINVAL;
448
449 case AST_OP_AND:
450 insn.op = FILTER_OP_AND;
451 break;
452 case AST_OP_OR:
453 insn.op = FILTER_OP_OR;
454 break;
455 }
456 insn.skip_offset = (uint16_t) -1UL; /* Temporary */
457 ret = bytecode_push_logical(&ctx->bytecode, &insn, 1, sizeof(insn),
458 &skip_offset_loc);
459 if (ret)
460 return ret;
461 /* Visit right child */
462 ret = recursive_visit_gen_bytecode(ctx, node->u.binary.right);
463 if (ret)
464 return ret;
465 /* Cast to s64 if float or field ref */
466 if ((node->u.binary.right->data_type == IR_DATA_FIELD_REF
467 || node->u.binary.right->data_type == IR_DATA_GET_CONTEXT_REF)
468 || node->u.binary.right->data_type == IR_DATA_FLOAT) {
469 struct cast_op cast_insn;
470
471 if (node->u.binary.right->data_type == IR_DATA_FIELD_REF
472 || node->u.binary.right->data_type == IR_DATA_GET_CONTEXT_REF) {
473 cast_insn.op = FILTER_OP_CAST_TO_S64;
474 } else {
475 cast_insn.op = FILTER_OP_CAST_DOUBLE_TO_S64;
476 }
477 ret = bytecode_push(&ctx->bytecode, &cast_insn,
478 1, sizeof(cast_insn));
479 if (ret)
480 return ret;
481 }
482 /* We now know where the logical op can skip. */
483 target_loc = (uint16_t) bytecode_get_len(&ctx->bytecode->b);
484 ret = bytecode_patch(&ctx->bytecode,
485 &target_loc, /* Offset to jump to */
486 skip_offset_loc, /* Where to patch */
487 sizeof(uint16_t));
488 return ret;
489 }
490
491 /*
492 * Postorder traversal of the tree. We need the children result before
493 * we can evaluate the parent.
494 */
495 static
496 int recursive_visit_gen_bytecode(struct filter_parser_ctx *ctx,
497 struct ir_op *node)
498 {
499 switch (node->op) {
500 case IR_OP_UNKNOWN:
501 default:
502 fprintf(stderr, "[error] Unknown node type in %s\n",
503 __func__);
504 return -EINVAL;
505
506 case IR_OP_ROOT:
507 return visit_node_root(ctx, node);
508 case IR_OP_LOAD:
509 return visit_node_load(ctx, node);
510 case IR_OP_UNARY:
511 return visit_node_unary(ctx, node);
512 case IR_OP_BINARY:
513 return visit_node_binary(ctx, node);
514 case IR_OP_LOGICAL:
515 return visit_node_logical(ctx, node);
516 }
517 }
518
519 LTTNG_HIDDEN
520 void filter_bytecode_free(struct filter_parser_ctx *ctx)
521 {
522 free(ctx->bytecode);
523 ctx->bytecode = NULL;
524 free(ctx->bytecode_reloc);
525 ctx->bytecode_reloc = NULL;
526 }
527
528 LTTNG_HIDDEN
529 int filter_visitor_bytecode_generate(struct filter_parser_ctx *ctx)
530 {
531 int ret;
532
533 ret = bytecode_init(&ctx->bytecode);
534 if (ret)
535 return ret;
536 ret = bytecode_init(&ctx->bytecode_reloc);
537 if (ret)
538 goto error;
539 ret = recursive_visit_gen_bytecode(ctx, ctx->ir_root);
540 if (ret)
541 goto error;
542
543 /* Finally, append symbol table to bytecode */
544 ctx->bytecode->b.reloc_table_offset = bytecode_get_len(&ctx->bytecode->b);
545 return bytecode_push(&ctx->bytecode, ctx->bytecode_reloc->b.data,
546 1, bytecode_get_len(&ctx->bytecode_reloc->b));
547
548 error:
549 filter_bytecode_free(ctx);
550 return ret;
551 }
This page took 0.066422 seconds and 5 git commands to generate.