[PATCH v6 6/9] Implement new filtering language parsing
Nikolay Marchuk
marchuk.nikolay.a at gmail.com
Wed Aug 2 05:36:46 UTC 2017
* filter.h (parse_filter_action, parse_filter_expression): Add new
declarations.
* filter_action.c (parse_filter_action): Add new parsing function.
(filtering_parse_function): Use filtering_parse instead of
parse_qualify_filter.
* filter_expression.c (parse_filter_expression): Implement parsing of filter
expression.
(add_variable_token, add_operator_token, parse_operator, unescape_argument): Add
helper functions.
* filter_parse.c: New file.
* filter_qualify.c (parse_read, parse_write, qualify_signals, parse_trace,
parse_abbrev, parse_verbose, parse_raw, parse_inject_common, parse_fault,
parse_inject): Use new parsing API.
* strace.c (init): Use filtering_parse instead of parse_qualify_filter.
* Makefile.am (strace_SOURCES): Add filter_parse.c.
* defs.h (filtering_parse): Use common parsing function.
---
Makefile.am | 1 +
defs.h | 2 +-
filter.h | 5 ++
filter_action.c | 13 +++-
filter_expression.c | 218 ++++++++++++++++++++++++++++++++++++++++++++++++++++
filter_parse.c | 188 ++++++++++++++++++++++++++++++++++++++++++++
filter_qualify.c | 94 ++++++++++++----------
strace.c | 6 +-
8 files changed, 480 insertions(+), 47 deletions(-)
create mode 100644 filter_parse.c
diff --git a/Makefile.am b/Makefile.am
index 0cc698a..ab4fdf6 100644
--- a/Makefile.am
+++ b/Makefile.am
@@ -134,6 +134,7 @@ strace_SOURCES = \
file_ioctl.c \
filter_action.c \
filter_expression.c \
+ filter_parse.c \
filter_qualify.c \
filter.c \
filter.h \
diff --git a/defs.h b/defs.h
index 491664a..a2a1c9f 100644
--- a/defs.h
+++ b/defs.h
@@ -682,7 +682,7 @@ extern struct number_set signal_set;
extern bool is_number_in_set(unsigned int number, const struct number_set *);
extern void filtering_parsing_finish(void);
extern void filter_syscall(struct tcb *);
-extern void parse_qualify_filter(const char *);
+extern void filtering_parse(const char *);
#define DECL_IOCTL(name) \
extern int \
diff --git a/filter.h b/filter.h
index ead8387..933c301 100644
--- a/filter.h
+++ b/filter.h
@@ -55,6 +55,7 @@ void set_filters_qualify_mode(struct filter **, unsigned int *nfilters);
/* filter action api */
struct filter *create_filter(struct filter_action *, const char *name);
struct filter_action *find_or_add_action(const char *);
+void parse_filter_action(const char *, const char *, const char *);
void *get_filter_action_priv_data(struct filter_action *);
void set_filter_action_priv_data(struct filter_action *, void *);
void set_qualify_mode(struct filter_action *);
@@ -63,5 +64,9 @@ void set_qualify_mode(struct filter_action *);
struct bool_expression *create_expression();
bool run_expression(struct bool_expression *, bool *, unsigned int);
void set_expression_qualify_mode(struct bool_expression *);
+void parse_filter_expression(struct bool_expression *, const char *,
+ struct filter_action *, unsigned int);
+
+void parse_qualify_action(const char *, const char *, const char *);
#endif
diff --git a/filter_action.c b/filter_action.c
index 74a2d29..5143bf3 100644
--- a/filter_action.c
+++ b/filter_action.c
@@ -120,7 +120,7 @@ filtering_parsing_finish(void)
/* Init trace action if pathtracing is enabled */
if (tracing_paths && (default_flags & QUAL_TRACE)) {
- parse_qualify_filter("trace=all");
+ filtering_parse("trace=all");
}
/* Sort actions by priority */
@@ -200,6 +200,17 @@ find_or_add_action(const char *name)
return add_action(type);
}
+void
+parse_filter_action(const char *action_name, const char *expr, const char *args)
+{
+ struct filter_action *action = find_or_add_action(action_name);
+ parse_filter_expression(action->expr, expr, action, action->nfilters);
+ if (args && action->type->parse_args == &parse_null)
+ error_msg("%s action takes no arguments: '%s'",
+ action->type->name, args);
+ action->_priv_data = action->type->parse_args(args);
+}
+
static void
run_filter_action(struct tcb *tcp, struct filter_action *action)
{
diff --git a/filter_expression.c b/filter_expression.c
index 5dc5e41..115cab7 100644
--- a/filter_expression.c
+++ b/filter_expression.c
@@ -26,6 +26,16 @@
*/
#include "defs.h"
+#include "filter.h"
+
+extern bool is_space_ascii(char);
+
+static bool
+is_allowed_in_name(char c)
+{
+ return (c >= 'A' && c <= 'Z') || (c >= 'a' && c <= 'z')
+ || (c >= '0' && c <= '9') || (c == '_');
+}
struct expression_token {
enum token_type {
@@ -41,6 +51,8 @@ struct expression_token {
} operator_id;
} data;
};
+/* Pseudo-operator for parsing */
+#define OP_PARENTHESIS 3
struct bool_expression {
unsigned int ntokens;
@@ -69,6 +81,25 @@ reallocate_expression(struct bool_expression *const expr,
expr->ntokens = new_ntokens;
}
+static void
+add_variable_token(struct bool_expression *expr, unsigned int id)
+{
+ struct expression_token token;
+ token.type = TOK_VARIABLE;
+ token.data.variable_id = id;
+ reallocate_expression(expr, expr->ntokens + 1);
+ expr->tokens[expr->ntokens - 1] = token;
+}
+
+static void
+add_operator_token(struct bool_expression *expr, int op) {
+ struct expression_token token;
+ token.type = TOK_OPERATOR;
+ token.data.operator_id = op;
+ reallocate_expression(expr, expr->ntokens + 1);
+ expr->tokens[expr->ntokens - 1] = token;
+}
+
void
set_expression_qualify_mode(struct bool_expression *expr)
{
@@ -212,3 +243,190 @@ run_expression(struct bool_expression *expr, bool *variables,
variables, variables_num);
return stack[0];
}
+
+/*
+ * Parse operator and add operator length to str and pos.
+ * Return -1 if no operator found.
+ */
+static int
+parse_operator(char **str, unsigned int *pos)
+{
+#define _OP(s, op) { s, sizeof(s) - 1, op }
+ struct {
+ const char *str;
+ int len;
+ enum operator_type op;
+ } ops[] = {
+ _OP("!", OP_NOT),
+ _OP("not", OP_NOT),
+ _OP("&&", OP_AND),
+ _OP("and", OP_AND),
+ _OP("||", OP_OR),
+ _OP("or", OP_OR)
+ };
+#undef _OP
+ char *p = *str;
+ unsigned int i;
+
+ for (i = 0; i < ARRAY_SIZE(ops); i++) {
+ if (!strncmp(p, ops[i].str, ops[i].len) &&
+ (!is_allowed_in_name(ops[i].str[0]) ||
+ !is_allowed_in_name(p[ops[i].len]))){
+ *str += ops[i].len - 1;
+ *pos += ops[i].len - 1;
+ return ops[i].op;
+ }
+ }
+ return -1;
+}
+
+static char *
+unescape_argument(char **str)
+{
+ char *p;
+ char *p_new;
+ bool escaped = false;
+ unsigned int size = 1;
+ char *new_str = xcalloc(strlen(*str) + 1, sizeof(char));
+ for (p = *str, p_new = new_str; *p; ++p) {
+ if (!escaped) {
+ if (*p == '\\') {
+ escaped = true;
+ continue;
+ } else if (is_space_ascii(*p) || *p == ')' || *p == '|'
+ || *p == '&') {
+ break;
+ }
+ }
+ escaped = false;
+ *(p_new++) = *p;
+ size++;
+ }
+ *str = p - 1;
+ xreallocarray(new_str, size, sizeof(char));
+ return new_str;
+}
+
+static void
+push_operator(int *stack, unsigned int *stack_size, int op) {
+ if (*stack_size == MAX_STACK_SIZE)
+ error_msg_and_die("stack overflow");
+ stack[*stack_size] = op;
+ (*stack_size)++;
+}
+
+static bool
+is_higher_priority(int op_a, int op_b)
+{
+ bool op_priority[] = {
+ [OP_NOT] = 2,
+ [OP_AND] = 1,
+ [OP_OR] = 0,
+ };
+ return op_priority[op_a] > op_priority[op_b];
+}
+
+void
+parse_filter_expression(struct bool_expression *expr, const char *str,
+ struct filter_action *action, unsigned int start_id)
+{
+ enum {
+ WAIT_FILTER,
+ FILTER_NAME,
+ FILTER_ARG,
+ WAIT_OPERATOR
+ } state = WAIT_FILTER;
+ unsigned int variable_id = start_id;
+ /* Current stack stack_size */
+ unsigned int st_size = 0;
+ int stack[MAX_STACK_SIZE];
+ char *buf = xstrdup(str);
+ struct filter *cur_filter = NULL;
+ char *filter_name = NULL;
+ char *filter_arg = NULL;
+ int op;
+ char *p;
+ unsigned int pos = 0;
+
+ for (p = buf; *p; ++p, ++pos) {
+ switch (state) {
+ case WAIT_FILTER:
+ if (*p == '(') {
+ push_operator(stack, &st_size, OP_PARENTHESIS);
+ } else if ((op = parse_operator(&p, &pos)) >= 0) {
+ if (op == OP_NOT) {
+ push_operator(stack, &st_size, op);
+ } else {
+ error_msg_and_die("invalid operator "
+ "at '%s':%u",
+ str, pos);
+ }
+ } else if (!is_space_ascii(*p)) {
+ filter_name = p;
+ state = FILTER_NAME;
+ }
+ break;
+
+ case FILTER_NAME:
+ if (is_space_ascii(*p)) {
+ *p = '\0';
+ cur_filter = create_filter(action, filter_name);
+ filter_arg = NULL;
+ state = FILTER_ARG;
+ }
+ break;
+
+ case FILTER_ARG:
+ if (!filter_arg && is_space_ascii(*p))
+ break;
+ filter_arg = unescape_argument(&p);
+ parse_filter(cur_filter, filter_arg);
+ free(filter_arg);
+ add_variable_token(expr, variable_id++);
+ state = WAIT_OPERATOR;
+ break;
+
+ case WAIT_OPERATOR:
+ if (is_space_ascii(*p))
+ break;
+ if (*p == ')') {
+ while ((st_size > 0) &&
+ (stack[st_size - 1] != OP_PARENTHESIS)) {
+ op = stack[--st_size];
+ add_operator_token(expr, op);
+ }
+ if (st_size == 0)
+ error_msg_and_die("unexpected ')' at "
+ "'%s':%u", str, pos);
+ --st_size;
+ break;
+ }
+ op = parse_operator(&p, &pos);
+ if (op < 0 || op == OP_NOT)
+ error_msg_and_die("invalid operator at '%s':%u",
+ str, pos);
+
+ /* Pop operators with higher priority. */
+ while ((st_size > 0) &&
+ is_higher_priority(stack[st_size - 1], op))
+ add_operator_token(expr, stack[--st_size]);
+
+ push_operator(stack, &st_size, op);
+ state = WAIT_FILTER;
+ continue;
+ }
+ }
+
+ free(buf);
+ if (state != WAIT_OPERATOR)
+ error_msg_and_die("unfinished filter expression '%s'", str);
+
+ while (st_size > 0) {
+ if (stack[--st_size] == '(')
+ error_msg_and_die("missing ')' in expression '%s'",
+ str);
+ add_operator_token(expr, stack[st_size]);
+ }
+ if (start_id > 0)
+ add_operator_token(expr, OP_OR);
+}
diff --git a/filter_parse.c b/filter_parse.c
new file mode 100644
index 0000000..29d6861
--- /dev/null
+++ b/filter_parse.c
@@ -0,0 +1,188 @@
+/*
+ * Copyright (c) 2017 Nikolay Marchuk <marchuk.nikolay.a at gmail.com>
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ * 3. The name of the author may not be used to endorse or promote products
+ * derived from this software without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
+ * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
+ * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
+ * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
+ * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include "defs.h"
+#include "filter.h"
+
+bool
+is_space_ascii(char c)
+{
+ return (c == ' ') || (c == '\t') || (c == '\n') || (c == '\r') ||
+ (c == '\v') || (c == '\f');
+}
+
+/*
+ * Split expression into action name, filter expression or qualify set
+ * and action arguments.
+ */
+void
+filtering_parse(const char *str)
+{
+ enum parsing_states {
+ F_EMPTY,
+ F_BEGIN,
+ F_QUAL_SET,
+ F_FILT_EXPR,
+ F_QUAL_ARGS,
+ F_FILT_ARGS,
+ F_END
+ } state = F_EMPTY;
+ const char *begin = NULL;
+ const char *action_name = NULL;
+ const char *main_part = NULL;
+ const char *args = NULL;
+ int parentheses_count = 0;
+ /* Used to store position of last terminating parenthesis. */
+ char *expression_end = NULL;
+ /* Used to provide diagnostics. */
+ unsigned int pos = 0;
+ char *buf = xstrdup(str);
+ char *p;
+
+ for (p = buf; *p; ++p, ++pos) {
+ switch (state) {
+ case F_EMPTY:
+ switch (*p) {
+ /* trace(), action name omitted */
+ case '(':
+ parentheses_count++;
+ action_name = "trace";
+ main_part = buf;
+ state = F_FILT_EXPR;
+ break;
+ case '=':
+ error_msg_and_die("invalid filter action ''");
+ default:
+ if (!is_space_ascii(*p)) {
+ begin = p;
+ state = F_BEGIN;
+ }
+ }
+ break;
+
+ case F_BEGIN:
+ switch (*p) {
+ /* action(...) */
+ case '(':
+ parentheses_count++;
+ action_name = begin;
+ *p = '\0';
+ main_part = p + 1;
+ state = F_FILT_EXPR;
+ break;
+ /* action=... */
+ case '=':
+ action_name = begin;
+ *p = '\0';
+ main_part = p + 1;
+ state = F_QUAL_SET;
+ break;
+ /* qualify set without action. */
+ case ',':
+ case '?':
+ case '!':
+ case '/':
+ case '%':
+ case '-':
+ action_name = "trace";
+ main_part = begin;
+ state = F_QUAL_SET;
+ break;
+ default:
+ /* new expression without action. */
+ if (is_space_ascii(*p)) {
+ action_name = "trace";
+ main_part = begin;
+ state = F_FILT_EXPR;
+ }
+ }
+ break;
+
+ case F_QUAL_SET:
+ if (*p == ':') {
+ *p = '\0';
+ args = p + 1;
+ state = F_QUAL_ARGS;
+ }
+ break;
+
+ case F_FILT_EXPR:
+ switch (*p) {
+ case ';':
+ *p = '\0';
+ args = p + 1;
+ state = F_FILT_ARGS;
+ break;
+ case '(':
+ parentheses_count++;
+ break;
+ case ')':
+ parentheses_count--;
+ expression_end = p;
+ break;
+ }
+
+ case F_QUAL_ARGS:
+ break;
+ case F_FILT_ARGS:
+ if (*p == ')') {
+ expression_end = p;
+ state = F_END;
+ }
+ break;
+ case F_END:
+ if (!is_space_ascii(*p))
+ error_msg_and_die("illegal character '%c' in "
+ "'%s':%u", *p, str, pos);
+ }
+ }
+
+ switch (state) {
+ case F_EMPTY:
+ error_msg_and_die("invalid filter expression '%s'", str);
+ case F_BEGIN:
+ action_name = "trace";
+ main_part = begin;
+ /* Fallthrough */
+ case F_QUAL_SET:
+ case F_QUAL_ARGS:
+ parse_qualify_action(action_name, main_part, args);
+ break;
+ case F_FILT_EXPR:
+ case F_FILT_ARGS:
+ case F_END:
+ if (parentheses_count != 0) {
+ error_msg_and_die("missing '%c' in '%s'",
+ parentheses_count > 0 ? ')' : '(',
+ str);
+ }
+ if (expression_end)
+ *expression_end = '\0';
+ parse_filter_action(action_name, main_part, args);
+ break;
+ }
+}
diff --git a/filter_qualify.c b/filter_qualify.c
index 105afdf..3518d98 100644
--- a/filter_qualify.c
+++ b/filter_qualify.c
@@ -181,111 +181,123 @@ parse_inject_common_args(char *str, struct inject_opts *const opts,
}
static void
-parse_read(const char *const str)
+parse_read(const char *const main_part, const char *const args)
{
struct filter_action *action = find_or_add_action("read");
struct filter *filter = create_filter(action, "fd");
- parse_filter(filter, str);
+ parse_filter(filter, main_part);
+ if (args)
+ error_msg("read action takes no arguments: '%s'", args);
set_qualify_mode(action);
}
static void
-parse_write(const char *const str)
+parse_write(const char *const main_part, const char *const args)
{
struct filter_action *action = find_or_add_action("write");
struct filter *filter = create_filter(action, "fd");
- parse_filter(filter, str);
+ parse_filter(filter, main_part);
+ if (args)
+ error_msg("write action takes no arguments: '%s'", args);
set_qualify_mode(action);
}
static void
-qualify_signals(const char *const str)
+qualify_signals(const char *const main_part, const char *const args)
{
- parse_set(str, &signal_set, sigstr_to_uint, "signal");
+ parse_set(main_part, &signal_set, sigstr_to_uint, "signal");
+ if (args)
+ error_msg("signal action takes no arguments: '%s'", args);
}
static void
-parse_trace(const char *const str)
+parse_trace(const char *const main_part, const char *const args)
{
struct filter_action *action = find_or_add_action("trace");
struct filter *filter = create_filter(action, "syscall");
- parse_filter(filter, str);
+ parse_filter(filter, main_part);
+ if (args)
+ error_msg("trace action takes no arguments: '%s'", args);
set_qualify_mode(action);
}
static void
-parse_abbrev(const char *const str)
+parse_abbrev(const char *const main_part, const char *const args)
{
struct filter_action *action = find_or_add_action("abbrev");
struct filter *filter = create_filter(action, "syscall");
- parse_filter(filter, str);
+ parse_filter(filter, main_part);
+ if (args)
+ error_msg("abbrev action takes no arguments: '%s'", args);
set_qualify_mode(action);
}
static void
-parse_verbose(const char *const str)
+parse_verbose(const char *const main_part, const char *const args)
{
struct filter_action *action = find_or_add_action("verbose");
struct filter *filter = create_filter(action, "syscall");
- parse_filter(filter, str);
+ parse_filter(filter, main_part);
+ if (args)
+ error_msg("verbose action takes no arguments: '%s'", args);
set_qualify_mode(action);
}
static void
-parse_raw(const char *const str)
+parse_raw(const char *const main_part, const char *const args)
{
struct filter_action *action = find_or_add_action("raw");
struct filter *filter = create_filter(action, "syscall");
- parse_filter(filter, str);
+ parse_filter(filter, main_part);
+ if (args)
+ error_msg("raw action takes no arguments: '%s'", args);
set_qualify_mode(action);
}
static void
-parse_inject_common(const char *const str, const bool fault_tokens_only,
- const char *const description)
+parse_inject_common(const char *const main_part, const char *const args,
+ const bool fault_tokens_only, const char *const description)
{
struct inject_opts *opts = xmalloc(sizeof(struct inject_opts));
- char *buf = xstrdup(str);
+ char *buf = args ? xstrdup(args) : NULL;
struct filter_action *action;
struct filter *filter;
- char *args = strchr(buf, ':');
-
- if (args)
- *(args++) = '\0';
action = find_or_add_action(fault_tokens_only ? "fault" : "inject");
filter = create_filter(action, "syscall");
- parse_filter(filter, buf);
+ parse_filter(filter, main_part);
set_qualify_mode(action);
- parse_inject_common_args(args, opts, ":", fault_tokens_only);
- if (!opts->init)
+ parse_inject_common_args(buf, opts, ":", fault_tokens_only);
+ if (!opts->init) {
error_msg_and_die("invalid %s '%s'", description,
args ? args : "");
- free(buf);
+ }
+ if (buf)
+ free(buf);
set_filter_action_priv_data(action, opts);
}
static void
-parse_fault(const char *const str)
+parse_fault(const char *const main_part, const char *const args)
{
- parse_inject_common(str, true, "fault argument");
+ parse_inject_common(main_part, args, true, "fault argument");
}
static void
-parse_inject(const char *const str)
+parse_inject(const char *const main_part, const char *const args)
{
- parse_inject_common(str, false, "inject argument");
+ parse_inject_common(main_part, args, false, "inject argument");
}
static const struct qual_options {
const char *name;
- void (*qualify)(const char *);
+ void (*qualify)(const char *, const char *);
} qual_options[] = {
{ "trace", parse_trace },
{ "t", parse_trace },
@@ -309,22 +321,20 @@ static const struct qual_options {
};
void
-parse_qualify_filter(const char *str)
+parse_qualify_action(const char *action_name, const char *main_part,
+ const char *args)
{
- const struct qual_options *opt = qual_options;
+ const struct qual_options *opt = NULL;
unsigned int i;
for (i = 0; i < ARRAY_SIZE(qual_options); ++i) {
- const char *name = qual_options[i].name;
- const size_t len = strlen(name);
- const char *val = str_strip_prefix_len(str, name, len);
-
- if (val == str || *val != '=')
- continue;
- str = val + 1;
- opt = &qual_options[i];
- break;
+ if (!strcmp(action_name, qual_options[i].name)) {
+ opt = &qual_options[i];
+ break;
+ }
}
- opt->qualify(str);
+ if (!opt)
+ error_msg_and_die("invalid filter action '%s'", action_name);
+ opt->qualify(main_part, args);
}
diff --git a/strace.c b/strace.c
index 137559c..560beea 100644
--- a/strace.c
+++ b/strace.c
@@ -1648,7 +1648,7 @@ init(int argc, char *argv[])
#if DEFAULT_QUAL_FLAGS != (QUAL_TRACE | QUAL_ABBREV | QUAL_VERBOSE)
# error Bug in DEFAULT_QUAL_FLAGS
#endif
- parse_qualify_filter("signal=all");
+ filtering_parse("signal=all");
while ((c = getopt(argc, argv,
"+b:cCdfFhiqrtTvVwxyz"
#ifdef USE_LIBUNWIND
@@ -1715,7 +1715,7 @@ init(int argc, char *argv[])
show_fd_path++;
break;
case 'v':
- parse_qualify_filter("abbrev=none");
+ filtering_parse("abbrev=none");
break;
case 'V':
print_version();
@@ -1730,7 +1730,7 @@ init(int argc, char *argv[])
error_opt_arg(c, optarg);
break;
case 'e':
- parse_qualify_filter(optarg);
+ filtering_parse(optarg);
break;
case 'o':
outfname = optarg;
--
2.1.4
More information about the Strace-devel
mailing list