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