2 * lttng-filter-validator.c
4 * LTTng UST filter bytecode validator.
6 * Copyright (C) 2010-2012 Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
8 * This library is free software; you can redistribute it and/or
9 * modify it under the terms of the GNU Lesser General Public
10 * License as published by the Free Software Foundation; only
11 * version 2.1 of the License.
13 * This library is distributed in the hope that it will be useful,
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 * Lesser General Public License for more details.
18 * You should have received a copy of the GNU Lesser General Public
19 * License along with this library; if not, write to the Free Software
20 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
26 #include "lttng-filter.h"
28 #include <urcu/rculfhash.h>
29 #include "lttng-hash-helper.h"
32 * Number of merge points for hash table size. Hash table initialized to
33 * that size, and we do not resize, because we do not want to trigger
34 * RCU worker thread execution: fall-back on linear traversal if number
35 * of merge points exceeds this value.
37 #define DEFAULT_NR_MERGE_POINTS 128
38 #define MIN_NR_BUCKETS 128
39 #define MAX_NR_BUCKETS 128
41 /* merge point table node */
43 struct cds_lfht_node node
;
45 /* Context at merge point */
47 unsigned long target_pc
;
50 static unsigned long lttng_hash_seed
;
51 static unsigned int lttng_hash_seed_ready
;
54 int lttng_hash_match(struct cds_lfht_node
*node
, const void *key
)
56 struct lfht_mp_node
*mp_node
=
57 caa_container_of(node
, struct lfht_mp_node
, node
);
58 unsigned long key_pc
= (unsigned long) key
;
60 if (mp_node
->target_pc
== key_pc
)
67 int merge_point_add(struct cds_lfht
*ht
, unsigned long target_pc
,
68 const struct vstack
*stack
)
70 struct lfht_mp_node
*node
;
71 unsigned long hash
= lttng_hash_mix((const void *) target_pc
,
75 dbg_printf("Filter: adding merge point at offset %lu, hash %lu\n",
77 node
= zmalloc(sizeof(struct lfht_mp_node
));
80 node
->target_pc
= target_pc
;
81 memcpy(&node
->stack
, stack
, sizeof(node
->stack
));
82 cds_lfht_add(ht
, hash
, &node
->node
);
87 * Binary comparators use top of stack and top of stack -1.
90 int bin_op_compare_check(struct vstack
*stack
, const char *str
)
92 if (unlikely(!vstack_ax(stack
) || !vstack_bx(stack
)))
95 switch (vstack_ax(stack
)->type
) {
100 switch (vstack_bx(stack
)->type
) {
113 switch (vstack_bx(stack
)->type
) {
132 ERR("type mismatch for '%s' binary operator\n", str
);
137 * Validate bytecode range overflow within the validation pass.
138 * Called for each instruction encountered.
141 int bytecode_validate_overflow(struct bytecode_runtime
*bytecode
,
142 void *start_pc
, void *pc
)
146 switch (*(filter_opcode_t
*) pc
) {
147 case FILTER_OP_UNKNOWN
:
150 ERR("unknown bytecode op %u\n",
151 (unsigned int) *(filter_opcode_t
*) pc
);
156 case FILTER_OP_RETURN
:
158 if (unlikely(pc
+ sizeof(struct return_op
)
159 > start_pc
+ bytecode
->len
)) {
170 case FILTER_OP_MINUS
:
171 case FILTER_OP_RSHIFT
:
172 case FILTER_OP_LSHIFT
:
173 case FILTER_OP_BIN_AND
:
174 case FILTER_OP_BIN_OR
:
175 case FILTER_OP_BIN_XOR
:
177 ERR("unsupported bytecode op %u\n",
178 (unsigned int) *(filter_opcode_t
*) pc
);
189 case FILTER_OP_EQ_STRING
:
190 case FILTER_OP_NE_STRING
:
191 case FILTER_OP_GT_STRING
:
192 case FILTER_OP_LT_STRING
:
193 case FILTER_OP_GE_STRING
:
194 case FILTER_OP_LE_STRING
:
195 case FILTER_OP_EQ_S64
:
196 case FILTER_OP_NE_S64
:
197 case FILTER_OP_GT_S64
:
198 case FILTER_OP_LT_S64
:
199 case FILTER_OP_GE_S64
:
200 case FILTER_OP_LE_S64
:
201 case FILTER_OP_EQ_DOUBLE
:
202 case FILTER_OP_NE_DOUBLE
:
203 case FILTER_OP_GT_DOUBLE
:
204 case FILTER_OP_LT_DOUBLE
:
205 case FILTER_OP_GE_DOUBLE
:
206 case FILTER_OP_LE_DOUBLE
:
208 if (unlikely(pc
+ sizeof(struct binary_op
)
209 > start_pc
+ bytecode
->len
)) {
216 case FILTER_OP_UNARY_PLUS
:
217 case FILTER_OP_UNARY_MINUS
:
218 case FILTER_OP_UNARY_NOT
:
219 case FILTER_OP_UNARY_PLUS_S64
:
220 case FILTER_OP_UNARY_MINUS_S64
:
221 case FILTER_OP_UNARY_NOT_S64
:
222 case FILTER_OP_UNARY_PLUS_DOUBLE
:
223 case FILTER_OP_UNARY_MINUS_DOUBLE
:
224 case FILTER_OP_UNARY_NOT_DOUBLE
:
226 if (unlikely(pc
+ sizeof(struct unary_op
)
227 > start_pc
+ bytecode
->len
)) {
237 if (unlikely(pc
+ sizeof(struct logical_op
)
238 > start_pc
+ bytecode
->len
)) {
245 case FILTER_OP_LOAD_FIELD_REF
:
247 ERR("Unknown field ref type\n");
251 case FILTER_OP_LOAD_FIELD_REF_STRING
:
252 case FILTER_OP_LOAD_FIELD_REF_SEQUENCE
:
253 case FILTER_OP_LOAD_FIELD_REF_S64
:
254 case FILTER_OP_LOAD_FIELD_REF_DOUBLE
:
256 if (unlikely(pc
+ sizeof(struct load_op
) + sizeof(struct field_ref
)
257 > start_pc
+ bytecode
->len
)) {
263 case FILTER_OP_LOAD_STRING
:
265 struct load_op
*insn
= (struct load_op
*) pc
;
266 uint32_t str_len
, maxlen
;
268 if (unlikely(pc
+ sizeof(struct load_op
)
269 > start_pc
+ bytecode
->len
)) {
274 maxlen
= start_pc
+ bytecode
->len
- pc
- sizeof(struct load_op
);
275 str_len
= strnlen(insn
->data
, maxlen
);
276 if (unlikely(str_len
>= maxlen
)) {
277 /* Final '\0' not found within range */
283 case FILTER_OP_LOAD_S64
:
285 if (unlikely(pc
+ sizeof(struct load_op
) + sizeof(struct literal_numeric
)
286 > start_pc
+ bytecode
->len
)) {
292 case FILTER_OP_LOAD_DOUBLE
:
294 if (unlikely(pc
+ sizeof(struct load_op
) + sizeof(struct literal_double
)
295 > start_pc
+ bytecode
->len
)) {
301 case FILTER_OP_CAST_TO_S64
:
302 case FILTER_OP_CAST_DOUBLE_TO_S64
:
303 case FILTER_OP_CAST_NOP
:
305 if (unlikely(pc
+ sizeof(struct cast_op
)
306 > start_pc
+ bytecode
->len
)) {
317 unsigned long delete_all_nodes(struct cds_lfht
*ht
)
319 struct cds_lfht_iter iter
;
320 struct lfht_mp_node
*node
;
321 unsigned long nr_nodes
= 0;
323 cds_lfht_for_each_entry(ht
, &iter
, node
, node
) {
326 ret
= cds_lfht_del(ht
, cds_lfht_iter_get_node(&iter
));
328 /* note: this hash table is never used concurrently */
341 int validate_instruction_context(struct bytecode_runtime
*bytecode
,
342 struct vstack
*stack
,
348 switch (*(filter_opcode_t
*) pc
) {
349 case FILTER_OP_UNKNOWN
:
352 ERR("unknown bytecode op %u\n",
353 (unsigned int) *(filter_opcode_t
*) pc
);
358 case FILTER_OP_RETURN
:
368 case FILTER_OP_MINUS
:
369 case FILTER_OP_RSHIFT
:
370 case FILTER_OP_LSHIFT
:
371 case FILTER_OP_BIN_AND
:
372 case FILTER_OP_BIN_OR
:
373 case FILTER_OP_BIN_XOR
:
375 ERR("unsupported bytecode op %u\n",
376 (unsigned int) *(filter_opcode_t
*) pc
);
383 ret
= bin_op_compare_check(stack
, "==");
390 ret
= bin_op_compare_check(stack
, "!=");
397 ret
= bin_op_compare_check(stack
, ">");
404 ret
= bin_op_compare_check(stack
, "<");
411 ret
= bin_op_compare_check(stack
, ">=");
418 ret
= bin_op_compare_check(stack
, "<=");
424 case FILTER_OP_EQ_STRING
:
425 case FILTER_OP_NE_STRING
:
426 case FILTER_OP_GT_STRING
:
427 case FILTER_OP_LT_STRING
:
428 case FILTER_OP_GE_STRING
:
429 case FILTER_OP_LE_STRING
:
431 if (!vstack_ax(stack
) || !vstack_bx(stack
)) {
432 ERR("Empty stack\n");
436 if (vstack_ax(stack
)->type
!= REG_STRING
437 || vstack_bx(stack
)->type
!= REG_STRING
) {
438 ERR("Unexpected register type for string comparator\n");
445 case FILTER_OP_EQ_S64
:
446 case FILTER_OP_NE_S64
:
447 case FILTER_OP_GT_S64
:
448 case FILTER_OP_LT_S64
:
449 case FILTER_OP_GE_S64
:
450 case FILTER_OP_LE_S64
:
452 if (!vstack_ax(stack
) || !vstack_bx(stack
)) {
453 ERR("Empty stack\n");
457 if (vstack_ax(stack
)->type
!= REG_S64
458 || vstack_bx(stack
)->type
!= REG_S64
) {
459 ERR("Unexpected register type for s64 comparator\n");
466 case FILTER_OP_EQ_DOUBLE
:
467 case FILTER_OP_NE_DOUBLE
:
468 case FILTER_OP_GT_DOUBLE
:
469 case FILTER_OP_LT_DOUBLE
:
470 case FILTER_OP_GE_DOUBLE
:
471 case FILTER_OP_LE_DOUBLE
:
473 if (!vstack_ax(stack
) || !vstack_bx(stack
)) {
474 ERR("Empty stack\n");
478 if ((vstack_ax(stack
)->type
!= REG_DOUBLE
&& vstack_ax(stack
)->type
!= REG_S64
)
479 || (vstack_bx(stack
)-> type
!= REG_DOUBLE
&& vstack_bx(stack
)->type
!= REG_S64
)) {
480 ERR("Unexpected register type for double comparator\n");
484 if (vstack_ax(stack
)->type
!= REG_DOUBLE
&& vstack_bx(stack
)->type
!= REG_DOUBLE
) {
485 ERR("Double operator should have at least one double register\n");
493 case FILTER_OP_UNARY_PLUS
:
494 case FILTER_OP_UNARY_MINUS
:
495 case FILTER_OP_UNARY_NOT
:
497 if (!vstack_ax(stack
)) {
498 ERR("Empty stack\n");
502 switch (vstack_ax(stack
)->type
) {
504 ERR("unknown register type\n");
509 ERR("Unary op can only be applied to numeric or floating point registers\n");
520 case FILTER_OP_UNARY_PLUS_S64
:
521 case FILTER_OP_UNARY_MINUS_S64
:
522 case FILTER_OP_UNARY_NOT_S64
:
524 if (!vstack_ax(stack
)) {
525 ERR("Empty stack\n");
529 if (vstack_ax(stack
)->type
!= REG_S64
) {
530 ERR("Invalid register type\n");
537 case FILTER_OP_UNARY_PLUS_DOUBLE
:
538 case FILTER_OP_UNARY_MINUS_DOUBLE
:
539 case FILTER_OP_UNARY_NOT_DOUBLE
:
541 if (!vstack_ax(stack
)) {
542 ERR("Empty stack\n");
546 if (vstack_ax(stack
)->type
!= REG_DOUBLE
) {
547 ERR("Invalid register type\n");
558 struct logical_op
*insn
= (struct logical_op
*) pc
;
560 if (!vstack_ax(stack
)) {
561 ERR("Empty stack\n");
565 if (vstack_ax(stack
)->type
!= REG_S64
) {
566 ERR("Logical comparator expects S64 register\n");
571 dbg_printf("Validate jumping to bytecode offset %u\n",
572 (unsigned int) insn
->skip_offset
);
573 if (unlikely(start_pc
+ insn
->skip_offset
<= pc
)) {
574 ERR("Loops are not allowed in bytecode\n");
582 case FILTER_OP_LOAD_FIELD_REF
:
584 ERR("Unknown field ref type\n");
588 case FILTER_OP_LOAD_FIELD_REF_STRING
:
589 case FILTER_OP_LOAD_FIELD_REF_SEQUENCE
:
591 struct load_op
*insn
= (struct load_op
*) pc
;
592 struct field_ref
*ref
= (struct field_ref
*) insn
->data
;
594 dbg_printf("Validate load field ref offset %u type string\n",
598 case FILTER_OP_LOAD_FIELD_REF_S64
:
600 struct load_op
*insn
= (struct load_op
*) pc
;
601 struct field_ref
*ref
= (struct field_ref
*) insn
->data
;
603 dbg_printf("Validate load field ref offset %u type s64\n",
607 case FILTER_OP_LOAD_FIELD_REF_DOUBLE
:
609 struct load_op
*insn
= (struct load_op
*) pc
;
610 struct field_ref
*ref
= (struct field_ref
*) insn
->data
;
612 dbg_printf("Validate load field ref offset %u type double\n",
617 case FILTER_OP_LOAD_STRING
:
622 case FILTER_OP_LOAD_S64
:
627 case FILTER_OP_LOAD_DOUBLE
:
632 case FILTER_OP_CAST_TO_S64
:
633 case FILTER_OP_CAST_DOUBLE_TO_S64
:
635 struct cast_op
*insn
= (struct cast_op
*) pc
;
637 if (!vstack_ax(stack
)) {
638 ERR("Empty stack\n");
642 switch (vstack_ax(stack
)->type
) {
644 ERR("unknown register type\n");
649 ERR("Cast op can only be applied to numeric or floating point registers\n");
657 if (insn
->op
== FILTER_OP_CAST_DOUBLE_TO_S64
) {
658 if (vstack_ax(stack
)->type
!= REG_DOUBLE
) {
659 ERR("Cast expects double\n");
666 case FILTER_OP_CAST_NOP
:
682 int validate_instruction_all_contexts(struct bytecode_runtime
*bytecode
,
683 struct cds_lfht
*merge_points
,
684 struct vstack
*stack
,
689 unsigned long target_pc
= pc
- start_pc
;
690 struct cds_lfht_iter iter
;
691 struct cds_lfht_node
*node
;
694 /* Validate the context resulting from the previous instruction */
695 ret
= validate_instruction_context(bytecode
, stack
, start_pc
, pc
);
699 /* Validate merge points */
700 hash
= lttng_hash_mix((const void *) target_pc
, sizeof(target_pc
),
702 cds_lfht_for_each_duplicate(merge_points
, hash
, lttng_hash_match
,
703 (const void *) target_pc
, &iter
, node
) {
704 struct lfht_mp_node
*mp_node
=
705 caa_container_of(node
, struct lfht_mp_node
, node
);
707 dbg_printf("Filter: validate merge point at offset %lu\n",
709 ret
= validate_instruction_context(bytecode
, &mp_node
->stack
,
713 /* Once validated, we can remove the merge point */
714 dbg_printf("Filter: remove one merge point at offset %lu\n",
716 ret
= cds_lfht_del(merge_points
, node
);
724 * >0: going to next insn.
725 * 0: success, stop iteration.
729 int exec_insn(struct bytecode_runtime
*bytecode
,
730 struct cds_lfht
*merge_points
,
731 struct vstack
*stack
,
736 void *next_pc
= *_next_pc
;
738 switch (*(filter_opcode_t
*) pc
) {
739 case FILTER_OP_UNKNOWN
:
742 ERR("unknown bytecode op %u\n",
743 (unsigned int) *(filter_opcode_t
*) pc
);
748 case FILTER_OP_RETURN
:
759 case FILTER_OP_MINUS
:
760 case FILTER_OP_RSHIFT
:
761 case FILTER_OP_LSHIFT
:
762 case FILTER_OP_BIN_AND
:
763 case FILTER_OP_BIN_OR
:
764 case FILTER_OP_BIN_XOR
:
766 ERR("unsupported bytecode op %u\n",
767 (unsigned int) *(filter_opcode_t
*) pc
);
778 case FILTER_OP_EQ_STRING
:
779 case FILTER_OP_NE_STRING
:
780 case FILTER_OP_GT_STRING
:
781 case FILTER_OP_LT_STRING
:
782 case FILTER_OP_GE_STRING
:
783 case FILTER_OP_LE_STRING
:
784 case FILTER_OP_EQ_S64
:
785 case FILTER_OP_NE_S64
:
786 case FILTER_OP_GT_S64
:
787 case FILTER_OP_LT_S64
:
788 case FILTER_OP_GE_S64
:
789 case FILTER_OP_LE_S64
:
790 case FILTER_OP_EQ_DOUBLE
:
791 case FILTER_OP_NE_DOUBLE
:
792 case FILTER_OP_GT_DOUBLE
:
793 case FILTER_OP_LT_DOUBLE
:
794 case FILTER_OP_GE_DOUBLE
:
795 case FILTER_OP_LE_DOUBLE
:
798 if (vstack_pop(stack
)) {
802 if (!vstack_ax(stack
)) {
803 ERR("Empty stack\n");
807 vstack_ax(stack
)->type
= REG_S64
;
808 next_pc
+= sizeof(struct binary_op
);
813 case FILTER_OP_UNARY_PLUS
:
814 case FILTER_OP_UNARY_MINUS
:
815 case FILTER_OP_UNARY_NOT
:
816 case FILTER_OP_UNARY_PLUS_S64
:
817 case FILTER_OP_UNARY_MINUS_S64
:
818 case FILTER_OP_UNARY_NOT_S64
:
821 if (!vstack_ax(stack
)) {
822 ERR("Empty stack\n");
826 vstack_ax(stack
)->type
= REG_S64
;
827 next_pc
+= sizeof(struct unary_op
);
831 case FILTER_OP_UNARY_PLUS_DOUBLE
:
832 case FILTER_OP_UNARY_MINUS_DOUBLE
:
833 case FILTER_OP_UNARY_NOT_DOUBLE
:
836 if (!vstack_ax(stack
)) {
837 ERR("Empty stack\n");
841 vstack_ax(stack
)->type
= REG_DOUBLE
;
842 next_pc
+= sizeof(struct unary_op
);
850 struct logical_op
*insn
= (struct logical_op
*) pc
;
853 /* Add merge point to table */
854 merge_ret
= merge_point_add(merge_points
, insn
->skip_offset
,
860 /* Continue to next instruction */
861 next_pc
+= sizeof(struct logical_op
);
866 case FILTER_OP_LOAD_FIELD_REF
:
868 ERR("Unknown field ref type\n");
872 case FILTER_OP_LOAD_FIELD_REF_STRING
:
873 case FILTER_OP_LOAD_FIELD_REF_SEQUENCE
:
875 if (vstack_push(stack
)) {
879 vstack_ax(stack
)->type
= REG_STRING
;
880 next_pc
+= sizeof(struct load_op
) + sizeof(struct field_ref
);
883 case FILTER_OP_LOAD_FIELD_REF_S64
:
885 if (vstack_push(stack
)) {
889 vstack_ax(stack
)->type
= REG_S64
;
890 next_pc
+= sizeof(struct load_op
) + sizeof(struct field_ref
);
893 case FILTER_OP_LOAD_FIELD_REF_DOUBLE
:
895 if (vstack_push(stack
)) {
899 vstack_ax(stack
)->type
= REG_DOUBLE
;
900 next_pc
+= sizeof(struct load_op
) + sizeof(struct field_ref
);
904 case FILTER_OP_LOAD_STRING
:
906 struct load_op
*insn
= (struct load_op
*) pc
;
908 if (vstack_push(stack
)) {
912 vstack_ax(stack
)->type
= REG_STRING
;
913 next_pc
+= sizeof(struct load_op
) + strlen(insn
->data
) + 1;
917 case FILTER_OP_LOAD_S64
:
919 if (vstack_push(stack
)) {
923 vstack_ax(stack
)->type
= REG_S64
;
924 next_pc
+= sizeof(struct load_op
)
925 + sizeof(struct literal_numeric
);
929 case FILTER_OP_LOAD_DOUBLE
:
931 if (vstack_push(stack
)) {
935 vstack_ax(stack
)->type
= REG_DOUBLE
;
936 next_pc
+= sizeof(struct load_op
)
937 + sizeof(struct literal_double
);
941 case FILTER_OP_CAST_TO_S64
:
942 case FILTER_OP_CAST_DOUBLE_TO_S64
:
945 if (!vstack_ax(stack
)) {
946 ERR("Empty stack\n");
950 vstack_ax(stack
)->type
= REG_S64
;
951 next_pc
+= sizeof(struct cast_op
);
954 case FILTER_OP_CAST_NOP
:
956 next_pc
+= sizeof(struct cast_op
);
967 * Never called concurrently (hash seed is shared).
969 int lttng_filter_validate_bytecode(struct bytecode_runtime
*bytecode
)
971 struct cds_lfht
*merge_points
;
972 void *pc
, *next_pc
, *start_pc
;
978 if (!lttng_hash_seed_ready
) {
979 lttng_hash_seed
= time(NULL
);
980 lttng_hash_seed_ready
= 1;
983 * Note: merge_points hash table used by single thread, and
984 * never concurrently resized. Therefore, we can use it without
985 * holding RCU read-side lock and free nodes without using
988 merge_points
= cds_lfht_new(DEFAULT_NR_MERGE_POINTS
,
989 MIN_NR_BUCKETS
, MAX_NR_BUCKETS
,
992 ERR("Error allocating hash table for bytecode validation\n");
995 start_pc
= &bytecode
->data
[0];
996 for (pc
= next_pc
= start_pc
; pc
- start_pc
< bytecode
->len
;
998 if (bytecode_validate_overflow(bytecode
, start_pc
, pc
) != 0) {
999 ERR("filter bytecode overflow\n");
1003 dbg_printf("Validating op %s (%u)\n",
1004 print_op((unsigned int) *(filter_opcode_t
*) pc
),
1005 (unsigned int) *(filter_opcode_t
*) pc
);
1008 * For each instruction, validate the current context
1009 * (traversal of entire execution flow), and validate
1010 * all merge points targeting this instruction.
1012 ret
= validate_instruction_all_contexts(bytecode
, merge_points
,
1013 &stack
, start_pc
, pc
);
1016 ret
= exec_insn(bytecode
, merge_points
, &stack
, &next_pc
, pc
);
1021 if (delete_all_nodes(merge_points
)) {
1023 ERR("Unexpected merge points\n");
1027 if (cds_lfht_destroy(merge_points
, NULL
)) {
1028 ERR("Error destroying hash table\n");