From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1758682AbdACPLB (ORCPT ); Tue, 3 Jan 2017 10:11:01 -0500 Received: from mga07.intel.com ([134.134.136.100]:60886 "EHLO mga07.intel.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1757543AbdACPIl (ORCPT ); Tue, 3 Jan 2017 10:08:41 -0500 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.33,455,1477983600"; d="scan'208";a="48814584" From: Andi Kleen To: acme@kernel.org Cc: jolsa@kernel.org, linux-kernel@vger.kernel.org, mingo@kernel.org, Andi Kleen Subject: [PATCH 09/11] perf, tools: Add a simple expression parser for JSON Date: Tue, 3 Jan 2017 07:08:31 -0800 Message-Id: <20170103150833.6694-10-andi@firstfloor.org> X-Mailer: git-send-email 2.9.3 In-Reply-To: <20170103150833.6694-1-andi@firstfloor.org> References: <20170103150833.6694-1-andi@firstfloor.org> Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org From: Andi Kleen Add a simple expression parser good enough to parse JSON relation expressions. The parser is implemented using bison. Signed-off-by: Andi Kleen --- tools/perf/tests/Build | 1 + tools/perf/tests/builtin-test.c | 4 ++ tools/perf/tests/expr.c | 48 +++++++++++++ tools/perf/tests/tests.h | 1 + tools/perf/util/Build | 5 ++ tools/perf/util/expr.h | 23 ++++++ tools/perf/util/expr.y | 156 ++++++++++++++++++++++++++++++++++++++++ 7 files changed, 238 insertions(+) create mode 100644 tools/perf/tests/expr.c create mode 100644 tools/perf/util/expr.h create mode 100644 tools/perf/util/expr.y diff --git a/tools/perf/tests/Build b/tools/perf/tests/Build index 6676c2dd6dcb..2912209057dc 100644 --- a/tools/perf/tests/Build +++ b/tools/perf/tests/Build @@ -38,6 +38,7 @@ perf-y += cpumap.o perf-y += stat.o perf-y += event_update.o perf-y += event-times.o +perf-y += expr.o perf-y += backward-ring-buffer.o perf-y += sdt.o perf-y += is_printable_array.o diff --git a/tools/perf/tests/builtin-test.c b/tools/perf/tests/builtin-test.c index 23605202d4a1..dc50b7a6badf 100644 --- a/tools/perf/tests/builtin-test.c +++ b/tools/perf/tests/builtin-test.c @@ -44,6 +44,10 @@ static struct test generic_tests[] = { .func = test__parse_events, }, { + .desc = "Simple expression parser", + .func = test__expr, + }, + { .desc = "PERF_RECORD_* events & perf_sample fields", .func = test__PERF_RECORD, }, diff --git a/tools/perf/tests/expr.c b/tools/perf/tests/expr.c new file mode 100644 index 000000000000..38e4bb31692c --- /dev/null +++ b/tools/perf/tests/expr.c @@ -0,0 +1,48 @@ +#include "util/debug.h" +#include "util/expr.h" +#include "tests.h" + +static int test(struct parse_ctx *ctx, const char *e, double val2) +{ + double val; + + if (expr_parse(&val, ctx, &e)) + TEST_ASSERT_VAL("parse test failed", 0); + TEST_ASSERT_VAL("unexpected value", val == val2); + return 0; +} + +int test__expr(int subtest __maybe_unused) +{ + const char *p; + double val; + int ret; + struct parse_ctx ctx; + + expr_ctx_init(&ctx); + expr_add_id(&ctx, "FOO", 1); + expr_add_id(&ctx, "BAR", 2); + + ret = test(&ctx, "1+1", 2); + ret |= test(&ctx, "FOO+BAR", 3); + ret |= test(&ctx, "(BAR/2)%2", 1); + ret |= test(&ctx, "1 - -4", 5); + ret |= test(&ctx, "(FOO-1)*2 + (BAR/2)%2 - -4", 5); + + if (ret) + return ret; + + p = "FOO/0"; + ret = expr_parse(&val, &ctx, &p); + TEST_ASSERT_VAL("division by zero", ret == 1); + + p = "BAR/"; + ret = expr_parse(&val, &ctx, &p); + TEST_ASSERT_VAL("missing operand", ret == 1); + + TEST_ASSERT_VAL("find other", expr_find_other("FOO + BAR", "FOO", &p) == 0); + TEST_ASSERT_VAL("find other", !strcmp(p, "BAR")); + free((void *)p); + + return 0; +} diff --git a/tools/perf/tests/tests.h b/tools/perf/tests/tests.h index 0d7b251305af..95f2e569a9e8 100644 --- a/tools/perf/tests/tests.h +++ b/tools/perf/tests/tests.h @@ -62,6 +62,7 @@ int test__sample_parsing(int subtest); int test__keep_tracking(int subtest); int test__parse_no_sample_id_all(int subtest); int test__dwarf_unwind(int subtest); +int test__expr(int subtest); int test__hists_filter(int subtest); int test__mmap_thread_lookup(int subtest); int test__thread_mg_share(int subtest); diff --git a/tools/perf/util/Build b/tools/perf/util/Build index 3840e3a87057..1344f9579e4d 100644 --- a/tools/perf/util/Build +++ b/tools/perf/util/Build @@ -88,6 +88,7 @@ libperf-y += mem-events.o libperf-y += vsprintf.o libperf-y += drv_configs.o libperf-y += time-utils.o +libperf-y += expr-bison.o libperf-$(CONFIG_LIBBPF) += bpf-loader.o libperf-$(CONFIG_BPF_PROLOGUE) += bpf-prologue.o @@ -140,6 +141,10 @@ $(OUTPUT)util/parse-events-bison.c: util/parse-events.y $(call rule_mkdir) $(Q)$(call echo-cmd,bison)$(BISON) -v util/parse-events.y -d $(PARSER_DEBUG_BISON) -o $@ -p parse_events_ +$(OUTPUT)util/expr-bison.c: util/expr.y + $(call rule_mkdir) + $(Q)$(call echo-cmd,bison)$(BISON) -v util/expr.y -d $(PARSER_DEBUG_BISON) -o $@ -p expr_ + $(OUTPUT)util/pmu-flex.c: util/pmu.l $(OUTPUT)util/pmu-bison.c $(call rule_mkdir) $(Q)$(call echo-cmd,flex)$(FLEX) -o $@ --header-file=$(OUTPUT)util/pmu-flex.h util/pmu.l diff --git a/tools/perf/util/expr.h b/tools/perf/util/expr.h new file mode 100644 index 000000000000..3b99fa282059 --- /dev/null +++ b/tools/perf/util/expr.h @@ -0,0 +1,23 @@ +#ifndef PARSE_CTX_H +#define PARSE_CTX_H 1 + +#define MAX_PARSE_ID 2 + +struct parse_id { + const char *name; + double val; +}; + +struct parse_ctx { + int num_ids; + struct parse_id ids[MAX_PARSE_ID]; +}; + +void expr_ctx_init(struct parse_ctx *ctx); +void expr_add_id(struct parse_ctx *ctx, const char *id, double val); +#ifndef IN_EXPR_Y +int expr_parse(double *final_val, struct parse_ctx *ctx, const char **pp); +#endif +int expr_find_other(const char *p, const char *one, const char **other); + +#endif diff --git a/tools/perf/util/expr.y b/tools/perf/util/expr.y new file mode 100644 index 000000000000..9c2c39512b8d --- /dev/null +++ b/tools/perf/util/expr.y @@ -0,0 +1,156 @@ +/* Simple expression parser */ +%{ +#include "util.h" +#include "util/debug.h" +#define IN_EXPR_Y 1 +#include "expr.h" +#include + +#define MAXIDLEN 256 +%} + +%define api.pure full +%parse-param { double *final_val } +%parse-param { struct parse_ctx *ctx } +%parse-param { const char **pp } +%lex-param { const char **pp } + +%union { + double num; + char id[MAXIDLEN+1]; +} + +%token NUMBER +%token ID +%left '|' +%left '^' +%left '&' +%left '-' '+' +%left '*' '/' '%' +%left NEG NOT +%type expr + +%{ +static int expr_lex(YYSTYPE *res, const char **pp); + +static void expr_error(double *final_val __maybe_unused, + struct parse_ctx *ctx __maybe_unused, + const char **pp __maybe_unused, + const char *s) +{ + pr_debug("%s", s); +} + +static int lookup_id(struct parse_ctx *ctx, char *id, double *val) +{ + int i; + + for (i = 0; i < ctx->num_ids; i++) { + if (!strcasecmp(ctx->ids[i].name, id)) { + *val = ctx->ids[i].val; + return 0; + } + } + return -1; +} + +%} +%% + +all_expr: expr { *final_val = $1; } + ; + +expr: NUMBER + | ID { if (lookup_id(ctx, $1, &$$) < 0) { + pr_debug("%s not found", $1); + YYABORT; + } + } + | expr '+' expr { $$ = $1 + $3; } + | expr '-' expr { $$ = $1 - $3; } + | expr '*' expr { $$ = $1 * $3; } + | expr '/' expr { if ($3 == 0) YYABORT; $$ = $1 / $3; } + | expr '%' expr { if ((long)$3 == 0) YYABORT; $$ = (long)$1 % (long)$3; } + | '-' expr %prec NEG { $$ = -$2; } + | '(' expr ')' { $$ = $2; } + ; + +%% + +static int expr_symbol(YYSTYPE *res, const char *p, const char **pp) +{ + char *dst = res->id; + const char *s = p; + + while (isalnum(*p) || *p == '_' || *p == '.') { + if (p - s >= MAXIDLEN) + return -1; + *dst++ = *p++; + } + *dst = 0; + *pp = p; + return ID; +} + +static int expr_lex(YYSTYPE *res, const char **pp) +{ + int tok; + const char *s; + const char *p = *pp; + + while (isspace(*p)) + p++; + s = p; + switch (*p++) { + case 'a' ... 'z': + case 'A' ... 'Z': + return expr_symbol(res, p - 1, pp); + case '0' ... '9': case '.': + res->num = strtod(s, (char **)&p); + tok = NUMBER; + break; + default: + tok = *s; + break; + } + *pp = p; + return tok; +} + +/* Caller must make sure id is allocated */ +void expr_add_id(struct parse_ctx *ctx, const char *name, double val) +{ + int idx; + assert(ctx->num_ids < MAX_PARSE_ID); + idx = ctx->num_ids++; + ctx->ids[idx].name = name; + ctx->ids[idx].val = val; +} + +void expr_ctx_init(struct parse_ctx *ctx) +{ + ctx->num_ids = 0; +} + +int expr_find_other(const char *p, const char *one, const char **other) +{ + const char *orig = p; + + *other = NULL; + for (;;) { + YYSTYPE val; + int tok = expr_lex(&val, &p); + if (tok == 0) + break; + if (tok == ID && strcasecmp(one, val.id)) { + if (*other) { + pr_debug("More than one extra identifier in %s\n", orig); + return -1; + } + *other = strdup(val.id); + if (!*other) + return -1; + } + } + return 0; +} -- 2.9.3