From 80322d88da92969c170c915e93a33a96e12497a7 Mon Sep 17 00:00:00 2001 From: Jeffrey Smith Date: Tue, 18 Aug 2015 22:03:41 -0500 Subject: dfilter: Add membership operator Added a new relational test: 'x in {a b c}'. The only LHS entity supported at this time is a field. The generated DFVM operations are equivalent to an OR'ed series of =='s, but with the redundant existence tests removed. Change-Id: Iddc89b81cf7ad6319aef1a2a94f93314cb721a8a Reviewed-on: https://code.wireshark.org/review/10246 Reviewed-by: Hadriel Kaplan Petri-Dish: Hadriel Kaplan Tested-by: Petri Dish Buildbot Reviewed-by: Michael Mann --- epan/dfilter/Makefile.common | 2 ++ epan/dfilter/gencode.c | 79 ++++++++++++++++++++++++++++++++++++++++++++ epan/dfilter/grammar.lemon | 24 ++++++++++++++ epan/dfilter/scanner.l | 6 ++++ epan/dfilter/semcheck.c | 60 +++++++++++++++++++++++++++++++-- epan/dfilter/sttype-set.c | 78 +++++++++++++++++++++++++++++++++++++++++++ epan/dfilter/sttype-set.h | 33 ++++++++++++++++++ epan/dfilter/sttype-test.c | 1 + epan/dfilter/sttype-test.h | 3 +- epan/dfilter/syntax-tree.c | 1 + epan/dfilter/syntax-tree.h | 2 ++ 11 files changed, 285 insertions(+), 4 deletions(-) create mode 100644 epan/dfilter/sttype-set.c create mode 100644 epan/dfilter/sttype-set.h (limited to 'epan/dfilter') diff --git a/epan/dfilter/Makefile.common b/epan/dfilter/Makefile.common index 66516ea1b7..90eda7661a 100644 --- a/epan/dfilter/Makefile.common +++ b/epan/dfilter/Makefile.common @@ -38,6 +38,7 @@ NONGENERATED_C_FILES = \ sttype-integer.c \ sttype-pointer.c \ sttype-range.c \ + sttype-set.c \ sttype-string.c \ sttype-test.c \ syntax-tree.c @@ -54,6 +55,7 @@ NONGENERATED_HEADER_FILES = \ semcheck.h \ sttype-function.h \ sttype-range.h \ + sttype-set.h \ sttype-test.h \ syntax-tree.h diff --git a/epan/dfilter/gencode.c b/epan/dfilter/gencode.c index 90ab7e2f9a..573b05aa85 100644 --- a/epan/dfilter/gencode.c +++ b/epan/dfilter/gencode.c @@ -26,6 +26,7 @@ #include "syntax-tree.h" #include "sttype-range.h" #include "sttype-test.h" +#include "sttype-set.h" #include "sttype-function.h" #include "ftypes/ftypes.h" @@ -277,6 +278,80 @@ gen_relation(dfwork_t *dfw, dfvm_opcode_t op, stnode_t *st_arg1, stnode_t *st_ar } } +static void +fixup_jumps(gpointer data, gpointer user_data) +{ + dfvm_value_t *jmp = (dfvm_value_t*)data; + dfwork_t *dfw = (dfwork_t*)user_data; + + if (jmp) { + jmp->value.numeric = dfw->next_insn_id; + } +} + +/* Generate the code for the in operator. It behaves much like an OR-ed + * series of == tests, but without the redundant existence checks. */ +static void +gen_relation_in(dfwork_t *dfw, stnode_t *st_arg1, stnode_t *st_arg2) +{ + dfvm_insn_t *insn; + dfvm_value_t *val1, *val2; + dfvm_value_t *jmp1 = NULL, *jmp2 = NULL; + int reg1 = -1, reg2 = -1; + stnode_t *node; + GSList *nodelist; + GSList *jumplist = NULL; + + /* Create code for the LHS of the relation */ + reg1 = gen_entity(dfw, st_arg1, &jmp1); + + /* Create code for the set on the RHS of the relation */ + nodelist = (GSList*)stnode_data(st_arg2); + while (nodelist) { + node = (stnode_t*)nodelist->data; + reg2 = gen_entity(dfw, node, &jmp2); + + /* Add test to see if the item matches */ + insn = dfvm_insn_new(ANY_EQ); + val1 = dfvm_value_new(REGISTER); + val1->value.numeric = reg1; + val2 = dfvm_value_new(REGISTER); + val2->value.numeric = reg2; + insn->arg1 = val1; + insn->arg2 = val2; + dfw_append_insn(dfw, insn); + + nodelist = g_slist_next(nodelist); + + /* Exit as soon as we find a match */ + if (nodelist) { + insn = dfvm_insn_new(IF_TRUE_GOTO); + val1 = dfvm_value_new(INSN_NUMBER); + insn->arg1 = val1; + dfw_append_insn(dfw, insn); + jumplist = g_slist_prepend(jumplist, val1); + } + + /* If an item is not present, just jump to the next item */ + if (jmp2) { + jmp2->value.numeric = dfw->next_insn_id; + jmp2 = NULL; + } + } + + /* Jump here if the LHS entity was not present */ + if (jmp1) { + jmp1->value.numeric = dfw->next_insn_id; + } + /* Jump here if any of the items in the set matched */ + g_slist_foreach(jumplist, fixup_jumps, dfw); + + /* Clean up */ + g_slist_free(jumplist); + nodelist = (GSList*)stnode_data(st_arg2); + set_nodelist_free(nodelist); +} + /* Parse an entity, returning the reg that it gets put into. * p_jmp will be set if it has to be set by the calling code; it should * be set to the place to jump to, to return to the calling code, @@ -422,6 +497,10 @@ gen_test(dfwork_t *dfw, stnode_t *st_node) case TEST_OP_MATCHES: gen_relation(dfw, ANY_MATCHES, st_arg1, st_arg2); break; + + case TEST_OP_IN: + gen_relation_in(dfw, st_arg1, st_arg2); + break; } } diff --git a/epan/dfilter/grammar.lemon b/epan/dfilter/grammar.lemon index 872a0d61c7..d3bab21ed5 100644 --- a/epan/dfilter/grammar.lemon +++ b/epan/dfilter/grammar.lemon @@ -9,6 +9,7 @@ #include "sttype-range.h" #include "sttype-test.h" #include "sttype-function.h" +#include "sttype-set.h" #include "drange.h" #include "grammar.h" @@ -61,6 +62,9 @@ %type funcparams {GSList*} %destructor funcparams {st_funcparams_free($$);} +%type setnode_list {GSList*} +%destructor setnode_list {set_nodelist_free($$);} + /* This is called as soon as a syntax error happens. After that, any "error" symbols are shifted, if possible. */ %syntax_error { @@ -98,6 +102,9 @@ any "error" symbols are shifted, if possible. */ case STTYPE_FUNCTION: dfilter_fail(dfw, "The function s was unexpected in this context."); break; + case STTYPE_SET: + dfilter_fail(dfw, "Syntax error, SET."); + break; /* These aren't handed to use as terminal tokens from the scanner, so was can assert that we'll never @@ -285,6 +292,23 @@ rel_op2(O) ::= TEST_BITWISE_AND. { O = TEST_OP_BITWISE_AND; } rel_op2(O) ::= TEST_CONTAINS. { O = TEST_OP_CONTAINS; } rel_op2(O) ::= TEST_MATCHES. { O = TEST_OP_MATCHES; } +relation_test(T) ::= entity(E) TEST_IN LBRACE setnode_list(L) RBRACE. +{ + stnode_t *S; + T = stnode_new(STTYPE_TEST, NULL); + S = stnode_new(STTYPE_SET, L); + sttype_test_set2(T, TEST_OP_IN, E, S); +} + +setnode_list(L) ::= entity(E). +{ + L = g_slist_append(NULL, E); +} + +setnode_list(L) ::= setnode_list(P) entity(E). +{ + L = g_slist_append(P, E); +} /* Functions */ diff --git a/epan/dfilter/scanner.l b/epan/dfilter/scanner.l index d3b71a39f9..7a6b66eaa4 100644 --- a/epan/dfilter/scanner.l +++ b/epan/dfilter/scanner.l @@ -89,6 +89,8 @@ static void mark_lval_deprecated(const char *s); "(" return simple(TOKEN_LPAREN); ")" return simple(TOKEN_RPAREN); "," return simple(TOKEN_COMMA); +"{" return simple(TOKEN_LBRACE); +"}" return simple(TOKEN_RBRACE); "==" return simple(TOKEN_TEST_EQ); "eq" return simple(TOKEN_TEST_EQ); @@ -119,6 +121,7 @@ static void mark_lval_deprecated(const char *s); "and" return simple(TOKEN_TEST_AND); "||" return simple(TOKEN_TEST_OR); "or" return simple(TOKEN_TEST_OR); +"in" return simple(TOKEN_TEST_IN); "[" { @@ -292,6 +295,8 @@ simple(int token) case TOKEN_RPAREN: case TOKEN_LBRACKET: case TOKEN_RBRACKET: + case TOKEN_LBRACE: + case TOKEN_RBRACE: case TOKEN_COLON: case TOKEN_COMMA: case TOKEN_HYPHEN: @@ -307,6 +312,7 @@ simple(int token) case TOKEN_TEST_NOT: case TOKEN_TEST_AND: case TOKEN_TEST_OR: + case TOKEN_TEST_IN: break; default: g_assert_not_reached(); diff --git a/epan/dfilter/semcheck.c b/epan/dfilter/semcheck.c index 1d86b1b25b..524accc2aa 100644 --- a/epan/dfilter/semcheck.c +++ b/epan/dfilter/semcheck.c @@ -27,6 +27,7 @@ #include "syntax-tree.h" #include "sttype-range.h" #include "sttype-test.h" +#include "sttype-set.h" #include "sttype-function.h" #include @@ -430,6 +431,7 @@ check_exists(dfwork_t *dfw, stnode_t *st_arg1) case STTYPE_TEST: case STTYPE_INTEGER: case STTYPE_FVALUE: + case STTYPE_SET: case STTYPE_NUM_TYPES: g_assert_not_reached(); } @@ -615,7 +617,11 @@ check_relation_LHS_FIELD(dfwork_t *dfw, const char *relation_string, hfinfo1 = (header_field_info*)stnode_data(st_arg1); ftype1 = hfinfo1->type; - DebugLog((" 5 check_relation_LHS_FIELD(%s)\n", relation_string)); + if (stnode_type_id(st_node) == STTYPE_TEST) { + DebugLog((" 5 check_relation_LHS_FIELD(%s)\n", relation_string)); + } else { + DebugLog((" 6 check_relation_LHS_FIELD(%s)\n", relation_string)); + } if (!can_func(ftype1)) { dfilter_fail(dfw, "%s (type=%s) cannot participate in '%s' comparison.", @@ -674,7 +680,11 @@ check_relation_LHS_FIELD(dfwork_t *dfw, const char *relation_string, } new_st = stnode_new(STTYPE_FVALUE, fvalue); - sttype_test_set2_args(st_node, st_arg1, new_st); + if (stnode_type_id(st_node) == STTYPE_TEST) { + sttype_test_set2_args(st_node, st_arg1, new_st); + } else { + sttype_set_replace_element(st_node, st_arg2, new_st); + } stnode_free(st_arg2); } else if (type2 == STTYPE_RANGE) { @@ -712,6 +722,27 @@ check_relation_LHS_FIELD(dfwork_t *dfw, const char *relation_string, check_function(dfw, st_arg2); } + else if (type2 == STTYPE_SET) { + GSList *nodelist; + /* A set should only ever appear on RHS of 'in' operation */ + if (strcmp(relation_string, "in") != 0) { + g_assert_not_reached(); + } + /* Attempt to interpret one element of the set at a time */ + nodelist = (GSList*)stnode_data(st_arg2); + while (nodelist) { + stnode_t *node = (stnode_t*)nodelist->data; + /* Don't let a range on the RHS affect the LHS field. */ + if (stnode_type_id(node) == STTYPE_RANGE) { + dfilter_fail(dfw, "A range may not appear inside a set."); + THROW(TypeError); + break; + } + check_relation_LHS_FIELD(dfw, "==", can_func, + allow_partial_value, st_arg2, st_arg1, node); + nodelist = g_slist_next(nodelist); + } + } else { g_assert_not_reached(); } @@ -801,6 +832,10 @@ check_relation_LHS_STRING(dfwork_t *dfw, const char* relation_string, sttype_test_set2_args(st_node, new_st, st_arg2); stnode_free(st_arg1); } + else if (type2 == STTYPE_SET) { + dfilter_fail(dfw, "Only a field may be tested for membership in a set."); + THROW(TypeError); + } else { g_assert_not_reached(); } @@ -890,6 +925,10 @@ check_relation_LHS_UNPARSED(dfwork_t *dfw, const char* relation_string, sttype_test_set2_args(st_node, new_st, st_arg2); stnode_free(st_arg1); } + else if (type2 == STTYPE_SET) { + dfilter_fail(dfw, "Only a field may be tested for membership in a set."); + THROW(TypeError); + } else { g_assert_not_reached(); } @@ -1042,6 +1081,10 @@ check_relation_LHS_RANGE(dfwork_t *dfw, const char *relation_string, check_function(dfw, st_arg2); } + else if (type2 == STTYPE_SET) { + dfilter_fail(dfw, "Only a field may be tested for membership in a set."); + THROW(TypeError); + } else { g_assert_not_reached(); } @@ -1192,6 +1235,10 @@ check_relation_LHS_FUNCTION(dfwork_t *dfw, const char *relation_string, check_function(dfw, st_arg2); } + else if (type2 == STTYPE_SET) { + dfilter_fail(dfw, "Only a field may be tested for membership in a set."); + THROW(TypeError); + } else { g_assert_not_reached(); } @@ -1252,6 +1299,7 @@ header_field_info *hfinfo; case STTYPE_TEST: case STTYPE_INTEGER: case STTYPE_FVALUE: + case STTYPE_SET: default: g_assert_not_reached(); } @@ -1331,7 +1379,13 @@ check_test(dfwork_t *dfw, stnode_t *st_node, GPtrArray *deprecated) check_relation(dfw, "contains", TRUE, ftype_can_contains, st_node, st_arg1, st_arg2); break; case TEST_OP_MATCHES: - check_relation(dfw, "matches", TRUE, ftype_can_matches, st_node, st_arg1, st_arg2); break; + check_relation(dfw, "matches", TRUE, ftype_can_matches, st_node, st_arg1, st_arg2); + break; + case TEST_OP_IN: + /* Use the ftype_can_eq as the items in the set are evaluated using the + * semantics of equality. */ + check_relation(dfw, "in", FALSE, ftype_can_eq, st_node, st_arg1, st_arg2); + break; default: g_assert_not_reached(); diff --git a/epan/dfilter/sttype-set.c b/epan/dfilter/sttype-set.c new file mode 100644 index 0000000000..8c71ba6bbb --- /dev/null +++ b/epan/dfilter/sttype-set.c @@ -0,0 +1,78 @@ +/* + * Wireshark - Network traffic analyzer + * By Gerald Combs + * Copyright 2001 Gerald Combs + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version 2 + * of the License, or (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. + */ + +#include "config.h" + +#include "syntax-tree.h" +#include "sttype-set.h" + +static void +slist_stnode_free(gpointer data, gpointer user_data _U_) +{ + stnode_free((stnode_t *)data); +} + +void +set_nodelist_free(GSList *params) +{ + g_slist_foreach(params, slist_stnode_free, NULL); + g_slist_free(params); +} + +void +sttype_set_replace_element(stnode_t *node, stnode_t *oldnode, stnode_t *newnode) +{ + GSList *nodelist = (GSList*)stnode_data(node); + + while (nodelist) { + if (nodelist->data == oldnode) { + nodelist->data = newnode; + break; + } + nodelist = g_slist_next(nodelist); + } +} + +void +sttype_register_set(void) +{ + static sttype_t set_type = { + STTYPE_SET, + "SET", + NULL, + NULL, + NULL + }; + + sttype_register(&set_type); +} + +/* + * Editor modelines - http://www.wireshark.org/tools/modelines.html + * + * Local variables: + * c-basic-offset: 8 + * tab-width: 8 + * indent-tabs-mode: t + * End: + * + * vi: set shiftwidth=8 tabstop=8 noexpandtab: + * :indentSize=8:tabSize=8:noTabs=false: + */ diff --git a/epan/dfilter/sttype-set.h b/epan/dfilter/sttype-set.h new file mode 100644 index 0000000000..45576b58c2 --- /dev/null +++ b/epan/dfilter/sttype-set.h @@ -0,0 +1,33 @@ +/* + * Wireshark - Network traffic analyzer + * By Gerald Combs + * Copyright 2001 Gerald Combs + * + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version 2 + * of the License, or (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. + */ + +#ifndef STTYPE_SET_H +#define STTYPE_SET_H + +#include + +void +sttype_set_replace_element(stnode_t *node, stnode_t *oldnode, stnode_t *newnode); + +void +set_nodelist_free(GSList *params); + +#endif diff --git a/epan/dfilter/sttype-test.c b/epan/dfilter/sttype-test.c index a4f5c40112..5e1eb785a3 100644 --- a/epan/dfilter/sttype-test.c +++ b/epan/dfilter/sttype-test.c @@ -96,6 +96,7 @@ num_operands(test_op_t op) case TEST_OP_BITWISE_AND: case TEST_OP_CONTAINS: case TEST_OP_MATCHES: + case TEST_OP_IN: return 2; } g_assert_not_reached(); diff --git a/epan/dfilter/sttype-test.h b/epan/dfilter/sttype-test.h index 366e2e1bfb..afc914ceb2 100644 --- a/epan/dfilter/sttype-test.h +++ b/epan/dfilter/sttype-test.h @@ -36,7 +36,8 @@ typedef enum { TEST_OP_LE, TEST_OP_BITWISE_AND, TEST_OP_CONTAINS, - TEST_OP_MATCHES + TEST_OP_MATCHES, + TEST_OP_IN } test_op_t; void diff --git a/epan/dfilter/syntax-tree.c b/epan/dfilter/syntax-tree.c index 297627bfb3..bd176217d7 100644 --- a/epan/dfilter/syntax-tree.c +++ b/epan/dfilter/syntax-tree.c @@ -36,6 +36,7 @@ sttype_init(void) sttype_register_integer(); sttype_register_pointer(); sttype_register_range(); + sttype_register_set(); sttype_register_string(); sttype_register_test(); } diff --git a/epan/dfilter/syntax-tree.h b/epan/dfilter/syntax-tree.h index af802f8382..5d955c900a 100644 --- a/epan/dfilter/syntax-tree.h +++ b/epan/dfilter/syntax-tree.h @@ -37,6 +37,7 @@ typedef enum { STTYPE_INTEGER, STTYPE_RANGE, STTYPE_FUNCTION, + STTYPE_SET, STTYPE_NUM_TYPES } sttype_id_t; @@ -72,6 +73,7 @@ void sttype_register_function(void); void sttype_register_integer(void); void sttype_register_pointer(void); void sttype_register_range(void); +void sttype_register_set(void); void sttype_register_string(void); void sttype_register_test(void); -- cgit v1.2.1