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