From: Ian Rogers <irogers@google.com>
To: Jiri Olsa <jolsa@kernel.org>
Cc: Arnaldo Carvalho de Melo <acme@kernel.org>,
lkml <linux-kernel@vger.kernel.org>,
Ingo Molnar <mingo@kernel.org>,
Namhyung Kim <namhyung@kernel.org>,
Alexander Shishkin <alexander.shishkin@linux.intel.com>,
Peter Zijlstra <a.p.zijlstra@chello.nl>,
Michael Petlan <mpetlan@redhat.com>,
Andi Kleen <ak@linux.intel.com>, Kajol Jain <kjain@linux.ibm.com>,
John Garry <john.garry@huawei.com>,
"Paul A. Clarke" <pc@us.ibm.com>,
Stephane Eranian <eranian@google.com>
Subject: Re: [PATCH 15/19] perf metric: Add recursion check when processing nested metrics
Date: Sun, 19 Jul 2020 15:40:26 -0700 [thread overview]
Message-ID: <CAP-5=fVNoaURV=CG=H0C6XBQvzBphh=NhMjRmAoRS6Ja8H17QA@mail.gmail.com> (raw)
In-Reply-To: <20200719181320.785305-16-jolsa@kernel.org>
On Sun, Jul 19, 2020 at 11:14 AM Jiri Olsa <jolsa@kernel.org> wrote:
>
> Keeping the stack of nested metrics via 'struct expr_id' objects
> and checking if we are in recursion via already processed metric.
>
> The stack is implemented as static array within the struct egroup
> with 100 entries, which should be enough nesting depth for any
> metric we have or plan to have at the moment.
>
> Adding test that simulates the recursion and checks we can
> detect it.
>
> Signed-off-by: Jiri Olsa <jolsa@kernel.org>
Acked-by: Ian Rogers <irogers@google.com>
Thanks,
Ian
> ---
> tools/perf/tests/parse-metric.c | 34 +++++++++-
> tools/perf/util/expr.c | 2 +
> tools/perf/util/expr.h | 9 ++-
> tools/perf/util/metricgroup.c | 117 +++++++++++++++++++++++++++++---
> 4 files changed, 149 insertions(+), 13 deletions(-)
>
> diff --git a/tools/perf/tests/parse-metric.c b/tools/perf/tests/parse-metric.c
> index aa4d5a9f09a8..01370ccb9ed9 100644
> --- a/tools/perf/tests/parse-metric.c
> +++ b/tools/perf/tests/parse-metric.c
> @@ -57,6 +57,18 @@ static struct pmu_event pme_test[] = {
> .metric_expr = "d_ratio(dcache_l2_all_miss, dcache_l2_all)",
> .metric_name = "DCache_L2_Misses",
> },
> +{
> + .metric_expr = "ipc + m2",
> + .metric_name = "M1",
> +},
> +{
> + .metric_expr = "ipc + m1",
> + .metric_name = "M2",
> +},
> +{
> + .metric_expr = "1/m3",
> + .metric_name = "M3",
> +}
> };
>
> static struct pmu_events_map map = {
> @@ -139,8 +151,8 @@ static int compute_metric(const char *name, struct value *vals, double *ratio)
> err = metricgroup__parse_groups_test(evlist, &map, name,
> false, false,
> &metric_events);
> -
> - TEST_ASSERT_VAL("failed to parse metric", err == 0);
> + if (err)
> + return err;
>
> if (perf_evlist__alloc_stats(evlist, false))
> return -1;
> @@ -264,11 +276,29 @@ static int test_dcache_l2(void)
> return 0;
> }
>
> +static int test_recursion_fail(void)
> +{
> + double ratio;
> + struct value vals[] = {
> + { .event = "inst_retired.any", .val = 300 },
> + { .event = "cpu_clk_unhalted.thread", .val = 200 },
> + { 0 },
> + };
> +
> + TEST_ASSERT_VAL("failed to find recursion",
> + compute_metric("M1", vals, &ratio) == -1);
> +
> + TEST_ASSERT_VAL("failed to find recursion",
> + compute_metric("M3", vals, &ratio) == -1);
> + return 0;
> +}
> +
> int test__parse_metric(struct test *test __maybe_unused, int subtest __maybe_unused)
> {
> TEST_ASSERT_VAL("IPC failed", test_ipc() == 0);
> TEST_ASSERT_VAL("frontend failed", test_frontend() == 0);
> TEST_ASSERT_VAL("cache_miss_cycles failed", test_cache_miss_cycles() == 0);
> TEST_ASSERT_VAL("DCache_L2 failed", test_dcache_l2() == 0);
> + TEST_ASSERT_VAL("recursion fail failed", test_recursion_fail() == 0);
> return 0;
> }
> diff --git a/tools/perf/util/expr.c b/tools/perf/util/expr.c
> index a346ca590513..53482ef53c41 100644
> --- a/tools/perf/util/expr.c
> +++ b/tools/perf/util/expr.c
> @@ -47,6 +47,8 @@ int expr__add_id(struct expr_parse_ctx *ctx, const char *id)
> if (!data_ptr)
> return -ENOMEM;
>
> + data_ptr->parent = ctx->parent;
> +
> ret = hashmap__set(&ctx->ids, id, data_ptr,
> (const void **)&old_key, (void **)&old_data);
> if (ret)
> diff --git a/tools/perf/util/expr.h b/tools/perf/util/expr.h
> index 9ed208d93418..fc2b5e824a66 100644
> --- a/tools/perf/util/expr.h
> +++ b/tools/perf/util/expr.h
> @@ -13,8 +13,14 @@
>
> struct metric_ref;
>
> +struct expr_id {
> + char *id;
> + struct expr_id *parent;
> +};
> +
> struct expr_parse_ctx {
> - struct hashmap ids;
> + struct hashmap ids;
> + struct expr_id *parent;
> };
>
> struct expr_id_data {
> @@ -25,6 +31,7 @@ struct expr_id_data {
> const char *metric_expr;
> bool counted;
> } ref;
> + struct expr_id *parent;
> };
>
> bool is_ref;
> diff --git a/tools/perf/util/metricgroup.c b/tools/perf/util/metricgroup.c
> index 332414d93f7a..2a45ee94fd61 100644
> --- a/tools/perf/util/metricgroup.c
> +++ b/tools/perf/util/metricgroup.c
> @@ -24,6 +24,7 @@
> #include <subcmd/parse-options.h>
> #include <api/fs/fs.h>
> #include "util.h"
> +#include <asm/bug.h>
>
> struct metric_event *metricgroup__lookup(struct rblist *metric_events,
> struct evsel *evsel,
> @@ -126,6 +127,28 @@ struct egroup {
> bool has_constraint;
> };
>
> +#define RECURSION_ID_MAX 100
> +
> +struct expr_ids {
> + struct expr_id id[RECURSION_ID_MAX];
> + int cnt;
> +};
> +
> +static struct expr_id *expr_ids__alloc(struct expr_ids *ids)
> +{
> + if (ids->cnt >= RECURSION_ID_MAX)
> + return NULL;
> + return &ids->id[ids->cnt++];
> +}
> +
> +static void expr_ids__exit(struct expr_ids *ids)
> +{
> + int i;
> +
> + for (i = 0; i < ids->cnt; i++)
> + free(ids->id[i].id);
> +}
> +
> /**
> * Find a group of events in perf_evlist that correpond to those from a parsed
> * metric expression. Note, as find_evsel_group is called in the same order as
> @@ -620,7 +643,9 @@ static int __add_metric(struct list_head *group_list,
> struct pmu_event *pe,
> bool metric_no_group,
> int runtime,
> - struct egroup **egp)
> + struct egroup **egp,
> + struct expr_id *parent,
> + struct expr_ids *ids)
> {
> struct metric_ref_node *ref;
> struct egroup *eg;
> @@ -630,7 +655,7 @@ static int __add_metric(struct list_head *group_list,
> * We got in here for the parent group,
> * allocate it and put it on the list.
> */
> - eg = malloc(sizeof(*eg));
> + eg = zalloc(sizeof(*eg));
> if (!eg)
> return -ENOMEM;
>
> @@ -643,6 +668,18 @@ static int __add_metric(struct list_head *group_list,
> INIT_LIST_HEAD(&eg->metric_refs);
> eg->metric_refs_cnt = 0;
> *egp = eg;
> +
> + parent = expr_ids__alloc(ids);
> + if (!parent) {
> + free(eg);
> + return -EINVAL;
> + }
> +
> + parent->id = strdup(pe->metric_name);
> + if (!parent->id) {
> + free(eg);
> + return -ENOMEM;
> + }
> } else {
> /*
> * We got here for the referenced metric, via the
> @@ -668,6 +705,10 @@ static int __add_metric(struct list_head *group_list,
> eg->metric_refs_cnt++;
> }
>
> + /* Force all found IDs in metric to have us as parent ID. */
> + WARN_ON_ONCE(!parent);
> + eg->pctx.parent = parent;
> +
> /*
> * For both the parent and referenced metrics, we parse
> * all the metric's IDs and add it to the parent context.
> @@ -728,15 +769,62 @@ static struct pmu_event *find_metric(const char *metric, struct pmu_events_map *
> return NULL;
> }
>
> +static int recursion_check(struct egroup *eg, const char *id, struct expr_id **parent,
> + struct expr_ids *ids)
> +{
> + struct expr_id_data *data;
> + struct expr_id *p;
> + int ret;
> +
> + /*
> + * We get the parent referenced by 'id' argument and
> + * traverse through all the parent object IDs to check
> + * if we already processed 'id', if we did, it's recursion
> + * and we fail.
> + */
> + ret = expr__get_id(&eg->pctx, id, &data);
> + if (ret)
> + return ret;
> +
> + p = data->parent;
> +
> + while (p->parent) {
> + if (!strcmp(p->id, id)) {
> + pr_err("failed: recursion detected for %s\n", id);
> + return -1;
> + }
> + p = p->parent;
> + }
> +
> + /*
> + * If we are over the limit of static entris, the metric
> + * is too difficult/nested to process, fail as well.
> + */
> + p = expr_ids__alloc(ids);
> + if (!p) {
> + pr_err("failed: too many nested metrics\n");
> + return -EINVAL;
> + }
> +
> + p->id = strdup(id);
> + p->parent = data->parent;
> + *parent = p;
> +
> + return p->id ? 0 : -ENOMEM;
> +}
> +
> static int add_metric(struct list_head *group_list,
> struct pmu_event *pe,
> bool metric_no_group,
> - struct egroup **egp);
> + struct egroup **egp,
> + struct expr_id *parent,
> + struct expr_ids *ids);
>
> static int resolve_metric(struct egroup *eg,
> bool metric_no_group,
> struct list_head *group_list,
> - struct pmu_events_map *map)
> + struct pmu_events_map *map,
> + struct expr_ids *ids)
> {
> struct hashmap_entry *cur;
> size_t bkt;
> @@ -750,18 +838,23 @@ static int resolve_metric(struct egroup *eg,
> do {
> all = true;
> hashmap__for_each_entry((&eg->pctx.ids), cur, bkt) {
> + struct expr_id *parent;
> struct pmu_event *pe;
>
> pe = find_metric(cur->key, map);
> if (!pe)
> continue;
>
> + ret = recursion_check(eg, cur->key, &parent, ids);
> + if (ret)
> + return ret;
> +
> all = false;
> /* The metric key itself needs to go out.. */
> expr__del_id(&eg->pctx, cur->key);
>
> /* ... and it gets resolved to the parent context. */
> - ret = add_metric(group_list, pe, metric_no_group, &eg);
> + ret = add_metric(group_list, pe, metric_no_group, &eg, parent, ids);
> if (ret)
> return ret;
>
> @@ -779,14 +872,16 @@ static int resolve_metric(struct egroup *eg,
> static int add_metric(struct list_head *group_list,
> struct pmu_event *pe,
> bool metric_no_group,
> - struct egroup **egp)
> + struct egroup **egp,
> + struct expr_id *parent,
> + struct expr_ids *ids)
> {
> int ret = 0;
>
> pr_debug("metric expr %s for %s\n", pe->metric_expr, pe->metric_name);
>
> if (!strstr(pe->metric_expr, "?")) {
> - ret = __add_metric(group_list, pe, metric_no_group, 1, egp);
> + ret = __add_metric(group_list, pe, metric_no_group, 1, egp, parent, ids);
> } else {
> int j, count;
>
> @@ -798,7 +893,7 @@ static int add_metric(struct list_head *group_list,
> */
>
> for (j = 0; j < count && !ret; j++) {
> - ret = __add_metric(group_list, pe, metric_no_group, j, egp);
> + ret = __add_metric(group_list, pe, metric_no_group, j, egp, parent, ids);
> }
> }
>
> @@ -811,6 +906,7 @@ static int metricgroup__add_metric(const char *metric, bool metric_no_group,
> struct pmu_events_map *map)
>
> {
> + struct expr_ids ids = { 0 };
> struct pmu_event *pe;
> struct egroup *eg;
> LIST_HEAD(list);
> @@ -821,7 +917,7 @@ static int metricgroup__add_metric(const char *metric, bool metric_no_group,
> has_match = true;
> eg = NULL;
>
> - ret = add_metric(&list, pe, metric_no_group, &eg);
> + ret = add_metric(&list, pe, metric_no_group, &eg, NULL, &ids);
> if (ret)
> return ret;
>
> @@ -830,7 +926,7 @@ static int metricgroup__add_metric(const char *metric, bool metric_no_group,
> * included in the expression.
> */
> ret = resolve_metric(eg, metric_no_group,
> - &list, map);
> + &list, map, &ids);
> if (ret)
> return ret;
> }
> @@ -853,6 +949,7 @@ static int metricgroup__add_metric(const char *metric, bool metric_no_group,
> }
>
> list_splice(&list, group_list);
> + expr_ids__exit(&ids);
> return 0;
> }
>
> --
> 2.25.4
>
next prev parent reply other threads:[~2020-07-19 22:41 UTC|newest]
Thread overview: 88+ messages / expand[flat|nested] mbox.gz Atom feed top
2020-07-19 18:13 [PATCHv3 00/19] perf metric: Add support to reuse metric Jiri Olsa
2020-07-19 18:13 ` [PATCH 01/19] perf metric: Fix memory leak in expr__add_id function Jiri Olsa
2020-07-19 21:41 ` Ian Rogers
2020-07-28 12:26 ` Arnaldo Carvalho de Melo
2020-07-19 18:13 ` [PATCH 02/19] perf metric: Add " Jiri Olsa
2020-07-26 9:16 ` kajoljain
2020-07-28 12:27 ` Arnaldo Carvalho de Melo
2020-07-19 18:13 ` [PATCH 03/19] perf metric: Change expr__get_id to return struct expr_id_data Jiri Olsa
2020-07-26 9:17 ` kajoljain
2020-07-28 12:28 ` Arnaldo Carvalho de Melo
2020-07-19 18:13 ` [PATCH 04/19] perf metric: Add expr__del_id function Jiri Olsa
2020-07-26 9:17 ` kajoljain
2020-07-28 12:28 ` Arnaldo Carvalho de Melo
2020-07-19 18:13 ` [PATCH 05/19] perf metric: Add macros for iterating map events Jiri Olsa
2020-07-19 21:46 ` Ian Rogers
2020-07-28 12:29 ` Arnaldo Carvalho de Melo
2020-07-26 9:17 ` kajoljain
2020-07-19 18:13 ` [PATCH 06/19] perf metric: Add add_metric function Jiri Olsa
2020-07-26 9:17 ` kajoljain
2020-07-28 12:30 ` Arnaldo Carvalho de Melo
2020-07-19 18:13 ` [PATCH 07/19] perf metric: Rename __metricgroup__add_metric to __add_metric Jiri Olsa
2020-07-26 9:18 ` kajoljain
2020-07-28 12:30 ` Arnaldo Carvalho de Melo
2020-07-19 18:13 ` [PATCH 08/19] perf metric: Collect referenced metrics in struct metric_ref_node Jiri Olsa
2020-07-19 22:18 ` Ian Rogers
2020-07-26 9:18 ` kajoljain
2020-07-28 12:31 ` Arnaldo Carvalho de Melo
2020-07-19 18:13 ` [PATCH 09/19] perf metric: Collect referenced metrics in struct metric_expr Jiri Olsa
2020-07-26 9:18 ` kajoljain
2020-07-28 12:32 ` Arnaldo Carvalho de Melo
2020-07-19 18:13 ` [PATCH 10/19] perf metric: Add referenced metrics to hash data Jiri Olsa
2020-07-19 22:32 ` Ian Rogers
2020-07-26 9:18 ` kajoljain
2020-07-28 12:32 ` Arnaldo Carvalho de Melo
2020-07-19 18:13 ` [PATCH 11/19] perf metric: Compute referenced metrics Jiri Olsa
2020-07-26 9:19 ` kajoljain
2020-07-28 12:33 ` Arnaldo Carvalho de Melo
2020-07-19 18:13 ` [PATCH 12/19] perf metric: Add events for the current list Jiri Olsa
2020-07-19 22:34 ` Ian Rogers
2020-07-26 9:19 ` kajoljain
2020-07-28 12:33 ` Arnaldo Carvalho de Melo
2020-07-19 18:13 ` [PATCH 13/19] perf metric: Add cache_miss_cycles to metric parse test Jiri Olsa
2020-07-26 9:19 ` kajoljain
2020-07-28 12:34 ` Arnaldo Carvalho de Melo
2020-07-19 18:13 ` [PATCH 14/19] perf metric: Add DCache_L2 " Jiri Olsa
2020-07-26 9:19 ` kajoljain
2020-07-28 12:34 ` Arnaldo Carvalho de Melo
2020-07-19 18:13 ` [PATCH 15/19] perf metric: Add recursion check when processing nested metrics Jiri Olsa
2020-07-19 22:40 ` Ian Rogers [this message]
2020-07-26 9:20 ` kajoljain
2020-07-28 12:35 ` Arnaldo Carvalho de Melo
2020-07-19 18:13 ` [PATCH 16/19] perf metric: Make compute_single function more precise Jiri Olsa
2020-07-28 12:36 ` Arnaldo Carvalho de Melo
2020-07-28 17:26 ` Ian Rogers
2020-07-28 20:17 ` kajoljain
2020-07-29 11:08 ` Arnaldo Carvalho de Melo
2020-07-19 18:13 ` [PATCH 17/19] perf metric: Add metric group test Jiri Olsa
2020-07-19 22:41 ` Ian Rogers
2020-07-26 9:20 ` kajoljain
2020-07-28 12:37 ` Arnaldo Carvalho de Melo
2020-07-19 18:13 ` [PATCH 18/19] perf metric: Rename struct egroup to metric Jiri Olsa
2020-07-26 9:20 ` kajoljain
2020-07-19 18:13 ` [PATCH 19/19] perf metric: Rename group_list to metric_list Jiri Olsa
2020-07-19 22:42 ` Ian Rogers
2020-07-26 9:21 ` kajoljain
2020-07-28 12:38 ` Arnaldo Carvalho de Melo
2020-07-20 6:44 ` [PATCHv3 00/19] perf metric: Add support to reuse metric kajoljain
2020-07-20 7:22 ` Jiri Olsa
2020-07-20 8:09 ` kajoljain
2020-07-20 8:19 ` Jiri Olsa
2020-07-20 9:02 ` kajoljain
2020-07-20 19:16 ` Jiri Olsa
2020-07-24 5:52 ` kajoljain
2020-07-25 11:51 ` Jiri Olsa
2020-07-26 9:14 ` kajoljain
2020-07-28 12:39 ` Arnaldo Carvalho de Melo
2020-07-28 12:54 ` Jiri Olsa
2020-07-28 13:01 ` Jiri Olsa
2020-07-28 13:34 ` [PATCHv3 20/19] perf metric: Fix runtime metric for powerpc Jiri Olsa
2020-07-28 15:22 ` [PATCHv3 00/19] perf metric: Add support to reuse metric Arnaldo Carvalho de Melo
2020-07-21 14:48 ` Paul A. Clarke
2020-07-22 18:11 ` Jiri Olsa
2020-07-23 15:59 ` Paul A. Clarke
2020-07-25 11:52 ` Jiri Olsa
2020-07-28 12:42 ` Arnaldo Carvalho de Melo
2020-07-23 17:14 ` Paul A. Clarke
2020-07-23 17:40 ` Andi Kleen
2020-07-29 9:18 [PATCHv4 " Jiri Olsa
2020-07-29 9:19 ` [PATCH 15/19] perf metric: Add recursion check when processing nested metrics Jiri Olsa
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to='CAP-5=fVNoaURV=CG=H0C6XBQvzBphh=NhMjRmAoRS6Ja8H17QA@mail.gmail.com' \
--to=irogers@google.com \
--cc=a.p.zijlstra@chello.nl \
--cc=acme@kernel.org \
--cc=ak@linux.intel.com \
--cc=alexander.shishkin@linux.intel.com \
--cc=eranian@google.com \
--cc=john.garry@huawei.com \
--cc=jolsa@kernel.org \
--cc=kjain@linux.ibm.com \
--cc=linux-kernel@vger.kernel.org \
--cc=mingo@kernel.org \
--cc=mpetlan@redhat.com \
--cc=namhyung@kernel.org \
--cc=pc@us.ibm.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).