Re: [PATCH 15/19] perf metric: Add recursion check when processing nested metrics

[kajoljain <kjain@linux.ibm.com>]

On 7/20/20 4:10 AM, Ian Rogers wrote:
> 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>
> 

Reviewed-By : Kajol Jain<kjain@linux.ibm.com>

Thanks,
Kajol Jain
> 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
>>