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

kajoljain
2020-07-26T09:20:20Z

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
>>