Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 23.128.96.18 as permitted sender) client-ip=23.128.96.18;
MIME-Version: 1.0
References: <20200712132634.138901-1-jolsa@kernel.org> <20200712132634.138901-17-jolsa@kernel.org>
In-Reply-To: <20200712132634.138901-17-jolsa@kernel.org>
From:   Ian Rogers <irogers@google.com>
Date:   Wed, 15 Jul 2020 10:40:41 -0700
Message-ID: <CAP-5=fUdUKmsGMxsyxxZCzmwRAumLmj6LgGrXWe7APPZRRC=WA@mail.gmail.com>
Subject: Re: [PATCH 16/18] perf metric: Add recursion check when processing
 nested metrics
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>
Content-Type: text/plain; charset="UTF-8"
Sender: linux-kernel-owner@vger.kernel.org
Precedence: bulk

On Sun, Jul 12, 2020 at 6:27 AM Jiri Olsa <jolsa@kernel.org> wrote:
>
> Keeping the stack of nested metrics via 'struct expr_id' objecs

s/objecs/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>
> ---
>  tools/perf/tests/parse-metric.c |  27 ++++++++-
>  tools/perf/util/expr.c          |   2 +
>  tools/perf/util/expr.h          |   9 ++-
>  tools/perf/util/metricgroup.c   | 101 +++++++++++++++++++++++++++++---
>  4 files changed, 128 insertions(+), 11 deletions(-)
>
> diff --git a/tools/perf/tests/parse-metric.c b/tools/perf/tests/parse-metric.c
> index b50e2a3f3b73..238a805edd55 100644
> --- a/tools/perf/tests/parse-metric.c
> +++ b/tools/perf/tests/parse-metric.c
> @@ -57,6 +57,14 @@ 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",
> +},
>  };

Perhaps add a test on simple recursion too:
{
  .metric_expr = "1/M1",
  .metric_name = "M1",
}

>  static struct pmu_events_map map = {
> @@ -139,8 +147,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 +272,26 @@ 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);
> +       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 2784df38f8c2..d23d8897bc61 100644
> --- a/tools/perf/util/expr.c
> +++ b/tools/perf/util/expr.c
> @@ -45,6 +45,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);
>         free(old_key);
> diff --git a/tools/perf/util/expr.h b/tools/perf/util/expr.h
> index b6d1fba64eaa..e5fdeab928c7 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 {
> @@ -27,6 +33,7 @@ struct expr_id_data {
>                         const char *metric_expr;
>                         bool counted;
>                 } ref;
> +               struct expr_id  *parent;
>         };
>  };
>
> diff --git a/tools/perf/util/metricgroup.c b/tools/perf/util/metricgroup.c
> index 66f25362702d..69ec20dd737b 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,
> @@ -109,6 +110,8 @@ struct metric_ref_node {
>         struct list_head list;
>  };
>
> +#define RECURSION_ID_MAX 100
> +
>  struct egroup {
>         struct list_head nd;
>         struct expr_parse_ctx pctx;
> @@ -119,6 +122,11 @@ struct egroup {
>         int refs_cnt;
>         int runtime;
>         bool has_constraint;
> +
> +       struct {
> +               struct expr_id  id[RECURSION_ID_MAX];
> +               int             cnt;
> +       } recursion;
>  };

Rather than place this in the egroup why not pass a "visited" array to
add metric. This would be more in keeping with Tarjan's algorithm
(although the SCC isn't needed in this case):
https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm

Thanks,
Ian


>
>  /**
> @@ -609,7 +617,8 @@ 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 metric_ref_node *ref;
>         struct egroup *eg;
> @@ -619,7 +628,7 @@ static int __add_metric(struct list_head *group_list,
>                  * We got in here for the master group,
>                  * allocate it and put it on the list.
>                  */
> -               eg = malloc(sizeof(*eg));
> +               eg = zalloc(sizeof(*eg));
>                 if (!eg)
>                         return -ENOMEM;
>
> @@ -632,6 +641,16 @@ static int __add_metric(struct list_head *group_list,
>                 INIT_LIST_HEAD(&eg->refs);
>                 eg->refs_cnt = 0;
>                 *egp = eg;
> +
> +               /* Initialize first recursion exr id with base name. */
> +               parent = &eg->recursion.id[0];
> +               eg->recursion.cnt = 1;
> +
> +               parent->id = strdup(pe->metric_name);
> +               if (!parent->id) {
> +                       free(eg);
> +                       return -ENOMEM;
> +               }
>         } else {
>                 /*
>                  * We got here for the referenced metric, via the
> @@ -651,6 +670,10 @@ static int __add_metric(struct list_head *group_list,
>                 eg->has_constraint |= metricgroup__has_constraint(pe);
>         }
>
> +       /* Force all found IDs in metric to have us as parent ID. */
> +       WARN_ON_ONCE(!parent);
> +       eg->pctx.parent = parent;
> +
>         /*
>          * For both the master and referenced metrics, we parse
>          * all the metric's IDs and add it to the parent context.
> @@ -707,10 +730,56 @@ 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_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.
> +        */
> +       if (eg->recursion.cnt + 1 >= RECURSION_ID_MAX) {
> +               pr_err("failed: too many nested metrics\n");
> +               return -EINVAL;
> +       }
> +
> +       p = &eg->recursion.id[eg->recursion.cnt];
> +       eg->recursion.cnt++;
> +
> +       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);
>
>  static int resolve_metric(struct egroup *eg,
>                           bool metric_no_group,
> @@ -729,18 +798,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);
> +                       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);
>                         if (ret)
>                                 return ret;
>
> @@ -758,14 +832,15 @@ 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)
>  {
>         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);
>         } else {
>                 int j, count;
>
> @@ -777,7 +852,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);
>                 }
>         }
>
> @@ -798,7 +873,7 @@ static int metricgroup__add_metric(const char *metric, bool metric_no_group,
>         if (!pe)
>                 return -EINVAL;
>
> -       ret = add_metric(group_list, pe, metric_no_group, &eg);
> +       ret = add_metric(group_list, pe, metric_no_group, &eg, NULL);
>         if (ret)
>                 return ret;
>
> @@ -871,11 +946,21 @@ static void egroup__free_refs(struct egroup *egroup)
>         }
>  }
>
> +static void egroup__free_recursion(struct egroup *egroup)
> +{
> +       int i;
> +
> +       for (i = 0; i < egroup->recursion.cnt; i++) {
> +               free(egroup->recursion.id[i].id);
> +       }
> +}
> +
>  static void metricgroup__free_egroups(struct list_head *group_list)
>  {
>         struct egroup *eg, *egtmp;
>
>         list_for_each_entry_safe (eg, egtmp, group_list, nd) {
> +               egroup__free_recursion(eg);
>                 egroup__free_refs(eg);
>                 expr__ctx_clear(&eg->pctx);
>                 list_del_init(&eg->nd);
> --
> 2.25.4
>