Don't compute events that won't be used in a metric.
Ian Rogers
reviewerv3 cover Don't compute events that won't be used in a metric.
For a metric like:
EVENT1 if #smt_on else EVENT2
currently EVENT1 and EVENT2 will be measured and then when the metric is reported EVENT1 or EVENT2 will be printed depending on the value from smt_on() during the expr parsing. Computing both events is unnecessary and can lead to multiplexing as discussed in this thread:
https://lore.kernel.org/lkml/[email protected]/
This change modifies expression parsing so that constants are considered when building the set of ids (events) and only events not contributing to a constant value are measured.
v3. fixes an assignment in patch 2/5. In patch 5/5 additional comments are added and useless frees are replaced by asserts. A new peephole optimization is added for the case CONST IF expr ELSE CONST, where the the constants are identical, as we don't need to evaluate the IF condition.
v2. is a rebase.
Ian Rogers (5):
perf metric: Restructure struct expr_parse_ctx.
perf metric: Use NAN for missing event IDs.
perf metric: Rename expr__find_other.
perf metric: Add utilities to work on ids map.
perf metric: Don't compute unused events.
tools/perf/tests/expr.c | 159 +++++++++----- tools/perf/tests/pmu-events.c | 42 ++-- tools/perf/util/expr.c | 136 ++++++++++-- tools/perf/util/expr.h | 17 +- tools/perf/util/expr.l | 9 - tools/perf/util/expr.y | 376 +++++++++++++++++++++++++++------- tools/perf/util/metricgroup.c | 44 ++-- tools/perf/util/stat-shadow.c | 54 +++-- 8 files changed, 623 insertions(+), 214 deletions(-)
Signature · 1 line
2.29.2.454.gaff20da3a2-goog
Ian Rogers
reviewerPATCH v3 1/5 perf metric: Restructure struct expr_parse_ctx.
A later change to parsing the ids out (in expr__find_other) will potentially drop hashmaps and so it is more convenient to move expr_parse_ctx to have a hashmap pointer rather than a struct value. As this pointer must be freed, rather than just going out of scope, add expr__ctx_new and expr__ctx_free to manage expr_parse_ctx memory. Adjust use of struct expr_parse_ctx accordingly.
--- tools/perf/tests/expr.c | 81 ++++++++++++++++++----------------- tools/perf/tests/pmu-events.c | 37 +++++++++------- tools/perf/util/expr.c | 38 ++++++++++++---- tools/perf/util/expr.h | 5 ++- tools/perf/util/metricgroup.c | 44 ++++++++++--------- tools/perf/util/stat-shadow.c | 50 +++++++++++++-------- 6 files changed, 151 insertions(+), 104 deletions(-)
tools/perf/tests/expr.c +42 -39
@@ -22,67 +22,70 @@ int test__expr(struct test *t __maybe_unused, int subtest __maybe_unused)const char *p;double val;int ret; -struct expr_parse_ctx ctx; +struct expr_parse_ctx *ctx; -expr__ctx_init (&ctx); -expr__add_id_val (&ctx,strdup ("FOO" ),1 ); -expr__add_id_val (&ctx,strdup ("BAR" ),2 ); + ctx =expr__ctx_new (); +TEST_ASSERT_VAL ("expr__ctx_new" , ctx); +expr__add_id_val (ctx,strdup ("FOO" ),1 ); +expr__add_id_val (ctx,strdup ("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 ); - ret |=test (&ctx,"1-1 | 1" ,1 ); - ret |=test (&ctx,"1-1 & 1" ,0 ); - ret |=test (&ctx,"min(1,2) + 1" ,2 ); - ret |=test (&ctx,"max(1,2) + 1" ,3 ); - ret |=test (&ctx,"1+1 if 3*4 else 0" ,2 ); - ret |=test (&ctx,"1.1 + 2.1" ,3.2 ); - ret |=test (&ctx,".1 + 2." ,2.1 ); - ret |=test (&ctx,"d_ratio(1, 2)" ,0.5 ); - ret |=test (&ctx,"d_ratio(2.5, 0)" ,0 ); - ret |=test (&ctx,"1.1 < 2.2" ,1 ); - ret |=test (&ctx,"2.2 > 1.1" ,1 ); - ret |=test (&ctx,"1.1 < 1.1" ,0 ); - ret |=test (&ctx,"2.2 > 2.2" ,0 ); - ret |=test (&ctx,"2.2 < 1.1" ,0 ); - ret |=test (&ctx,"1.1 > 2.2" ,0 ); + 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 ); + ret |=test (ctx,"1-1 | 1" ,1 ); + ret |=test (ctx,"1-1 & 1" ,0 ); + ret |=test (ctx,"min(1,2) + 1" ,2 ); + ret |=test (ctx,"max(1,2) + 1" ,3 ); + ret |=test (ctx,"1+1 if 3*4 else 0" ,2 ); + ret |=test (ctx,"1.1 + 2.1" ,3.2 ); + ret |=test (ctx,".1 + 2." ,2.1 ); + ret |=test (ctx,"d_ratio(1, 2)" ,0.5 ); + ret |=test (ctx,"d_ratio(2.5, 0)" ,0 ); + ret |=test (ctx,"1.1 < 2.2" ,1 ); + ret |=test (ctx,"2.2 > 1.1" ,1 ); + ret |=test (ctx,"1.1 < 1.1" ,0 ); + ret |=test (ctx,"2.2 > 2.2" ,0 ); + ret |=test (ctx,"2.2 < 1.1" ,0 ); + ret |=test (ctx,"1.1 > 2.2" ,0 ); -if (ret) +if (ret) { +expr__ctx_free (ctx);return ret; + } p ="FOO/0" ; - ret =expr__parse (&val, &ctx, p,1 ); + ret =expr__parse (&val, ctx, p,1 );TEST_ASSERT_VAL ("division by zero" , ret ==-1 ); p ="BAR/" ; - ret =expr__parse (&val, &ctx, p,1 ); + ret =expr__parse (&val, ctx, p,1 );TEST_ASSERT_VAL ("missing operand" , ret ==-1 ); -expr__ctx_clear (&ctx); +expr__ctx_clear (ctx);TEST_ASSERT_VAL ("find other" ,expr__find_other ("FOO + BAR + BAZ + BOZO" ,"FOO" , - &ctx,1 ) ==0 ); -TEST_ASSERT_VAL ("find other" ,hashmap__size (&ctx.ids) ==3 ); -TEST_ASSERT_VAL ("find other" ,hashmap__find (&ctx.ids,"BAR" , + ctx,1 ) ==0 ); +TEST_ASSERT_VAL ("find other" ,hashmap__size (ctx->ids) ==3 ); +TEST_ASSERT_VAL ("find other" ,hashmap__find (ctx->ids,"BAR" , (void **)&val_ptr)); -TEST_ASSERT_VAL ("find other" ,hashmap__find (&ctx.ids,"BAZ" , +TEST_ASSERT_VAL ("find other" ,hashmap__find (ctx->ids,"BAZ" , (void **)&val_ptr)); -TEST_ASSERT_VAL ("find other" ,hashmap__find (&ctx.ids,"BOZO" , +TEST_ASSERT_VAL ("find other" ,hashmap__find (ctx->ids,"BOZO" , (void **)&val_ptr)); -expr__ctx_clear (&ctx); +expr__ctx_clear (ctx);TEST_ASSERT_VAL ("find other" ,expr__find_other ("EVENT1\\,param\\=?@ + EVENT2\\,param\\=?@" , -NULL , &ctx,3 ) ==0 ); -TEST_ASSERT_VAL ("find other" ,hashmap__size (&ctx.ids) ==2 ); -TEST_ASSERT_VAL ("find other" ,hashmap__find (&ctx.ids,"EVENT1,param=3/" , +NULL , ctx,3 ) ==0 ); +TEST_ASSERT_VAL ("find other" ,hashmap__size (ctx->ids) ==2 ); +TEST_ASSERT_VAL ("find other" ,hashmap__find (ctx->ids,"EVENT1,param=3/" , (void **)&val_ptr)); -TEST_ASSERT_VAL ("find other" ,hashmap__find (&ctx.ids,"EVENT2,param=3/" , +TEST_ASSERT_VAL ("find other" ,hashmap__find (ctx->ids,"EVENT2,param=3/" , (void **)&val_ptr)); -expr__ctx_clear (&ctx); +expr__ctx_free (ctx);return 0 ; }
tools/perf/tests/pmu-events.c +21 -16
@@ -478,9 +478,14 @@ static int test_parsing(void)struct pmu_event *pe;int i, j, k;int ret =0 ; -struct expr_parse_ctx ctx; +struct expr_parse_ctx *ctx;double result; + ctx =expr__ctx_new (); +if (!ctx) { +pr_debug ("expr__ctx_new failed" ); +return TEST_FAIL ; + } i =0 ;for (;;) { map = &pmu_events_map[i++];
@@ -496,8 +501,8 @@ static int test_parsing(void)break ;if (!pe->metric_expr)continue ; -expr__ctx_init (&ctx); -if (expr__find_other (pe->metric_expr,NULL , &ctx,0 ) +expr__ctx_clear (ctx); +if (expr__find_other (pe->metric_expr,NULL , ctx,0 ) <0 ) {expr_failure ("Parse other failed" , map, pe); ret++;
@@ -510,22 +515,22 @@ static int test_parsing(void)* make them unique. */ k =1 ; -hashmap__for_each_entry ((&ctx.ids), cur, bkt) -expr__add_id_val (&ctx,strdup (cur->key), k++); +hashmap__for_each_entry (ctx->ids, cur, bkt) +expr__add_id_val (ctx,strdup (cur->key), k++); -hashmap__for_each_entry ((&ctx.ids), cur, bkt) { +hashmap__for_each_entry (ctx->ids, cur, bkt) {if (check_parse_cpu (cur->key, map == cpus_map, pe)) ret++; } -if (expr__parse (&result, &ctx, pe->metric_expr,0 )) { +if (expr__parse (&result, ctx, pe->metric_expr,0 )) {expr_failure ("Parse failed" , map, pe); ret++; } -expr__ctx_clear (&ctx); } } +expr__ctx_free (ctx);/* TODO: fail when not ok */ return ret ==0 ?TEST_OK :TEST_SKIP ; }
@@ -544,7 +549,7 @@ static struct test_metric metrics[] = {static int metric_parse_fake (const char *str) { -struct expr_parse_ctx ctx; +struct expr_parse_ctx *ctx;struct hashmap_entry *cur;double result;int ret =-1 ;
@@ -553,8 +558,8 @@ static int metric_parse_fake(const char *str)pr_debug ("parsing '%s'\n" , str); -expr__ctx_init (&ctx); -if (expr__find_other (str,NULL , &ctx,0 ) <0 ) { + ctx =expr__ctx_new (); +if (expr__find_other (str,NULL , ctx,0 ) <0 ) {pr_err ("expr__find_other failed\n" );return -1 ; }
@@ -565,23 +570,23 @@ static int metric_parse_fake(const char *str)* make them unique. */ i =1 ; -hashmap__for_each_entry ((&ctx.ids), cur, bkt) -expr__add_id_val (&ctx,strdup (cur->key), i++); +hashmap__for_each_entry (ctx->ids, cur, bkt) +expr__add_id_val (ctx,strdup (cur->key), i++); -hashmap__for_each_entry ((&ctx.ids), cur, bkt) { +hashmap__for_each_entry (ctx->ids, cur, bkt) {if (check_parse_fake (cur->key)) {pr_err ("check_parse_fake failed\n" ); goto out; } } -if (expr__parse (&result, &ctx, str,1 )) +if (expr__parse (&result, ctx, str,1 ))pr_err ("expr__parse failed\n" );else ret =0 ; out: -expr__ctx_clear (&ctx); +expr__ctx_free (ctx);return ret; }
tools/perf/util/expr.c +29 -9
@@ -73,7 +73,7 @@ int expr__add_id(struct expr_parse_ctx *ctx, const char *id) data_ptr->parent = ctx->parent; data_ptr->kind =EXPR_ID_DATA__PARENT ; - ret =hashmap__set (&ctx->ids, id, data_ptr, + ret =hashmap__set (ctx->ids, id, data_ptr, (const void **)&old_key, (void **)&old_data);if (ret)free (data_ptr);
@@ -95,7 +95,7 @@ int expr__add_id_val(struct expr_parse_ctx *ctx, const char *id, double val) data_ptr->val = val; data_ptr->kind =EXPR_ID_DATA__VALUE ; - ret =hashmap__set (&ctx->ids, id, data_ptr, + ret =hashmap__set (ctx->ids, id, data_ptr, (const void **)&old_key, (void **)&old_data);if (ret)free (data_ptr);
@@ -140,7 +140,7 @@ int expr__add_ref(struct expr_parse_ctx *ctx, struct metric_ref *ref) data_ptr->ref.metric_expr = ref->metric_expr; data_ptr->kind =EXPR_ID_DATA__REF ; - ret =hashmap__set (&ctx->ids, name, data_ptr, + ret =hashmap__set (ctx->ids, name, data_ptr, (const void **)&old_key, (void **)&old_data);if (ret)free (data_ptr);
@@ -156,7 +156,7 @@ int expr__add_ref(struct expr_parse_ctx *ctx, struct metric_ref *ref)int expr__get_id (struct expr_parse_ctx *ctx,const char *id,struct expr_id_data **data) { -return hashmap__find (&ctx->ids, id, (void **)data) ?0 :-1 ; +return hashmap__find (ctx->ids, id, (void **)data) ?0 :-1 ; } int expr__resolve_id(struct expr_parse_ctx *ctx, const char *id,
@@ -205,15 +205,23 @@ void expr__del_id(struct expr_parse_ctx *ctx, const char *id)struct expr_id_data *old_val =NULL ;char *old_key =NULL ; -hashmap__delete (&ctx->ids, id, +hashmap__delete (ctx->ids, id, (const void **)&old_key, (void **)&old_val);free (old_key);free (old_val); } -void expr__ctx_init (struct expr_parse_ctx *ctx) +struct expr_parse_ctx *expr__ctx_new (void ) { -hashmap__init (&ctx->ids, key_hash, key_equal,NULL ); +struct expr_parse_ctx *ctx; + + ctx =malloc (sizeof (struct expr_parse_ctx )); +if (!ctx) +return NULL ; + + ctx->ids =hashmap__new (key_hash, key_equal,NULL ); + ctx->parent =NULL ; +return ctx; }void expr__ctx_clear (struct expr_parse_ctx *ctx)
@@ -221,11 +229,23 @@ void expr__ctx_clear(struct expr_parse_ctx *ctx)struct hashmap_entry *cur;size_t bkt; -hashmap__for_each_entry ((&ctx->ids), cur, bkt) { +hashmap__for_each_entry (ctx->ids, cur, bkt) { +free ((char *)cur->key); +free (cur->value); + } +hashmap__clear (ctx->ids); +} + +void expr__ctx_free (struct expr_parse_ctx *ctx) +{ +struct hashmap_entry *cur; +size_t bkt; + +hashmap__for_each_entry (ctx->ids, cur, bkt) {free ((char *)cur->key);free (cur->value); } -hashmap__clear (&ctx->ids); +hashmap__free (ctx->ids); } static int
tools/perf/util/expr.h +3 -2
@@ -19,7 +19,7 @@ struct expr_id { };struct expr_parse_ctx { -struct hashmap ids; +struct hashmap *ids;struct expr_id *parent; };
@@ -30,8 +30,9 @@ struct expr_scanner_ctx {int runtime; }; -void expr__ctx_init (struct expr_parse_ctx *ctx); +struct expr_parse_ctx *expr__ctx_new (void );void expr__ctx_clear (struct expr_parse_ctx *ctx); +void expr__ctx_free (struct expr_parse_ctx *ctx);void expr__del_id (struct expr_parse_ctx *ctx,const char *id);int expr__add_id (struct expr_parse_ctx *ctx,const char *id);int expr__add_id_val (struct expr_parse_ctx *ctx,const char *id,double val);
tools/perf/util/metricgroup.c +24 -20
146 lines not on this page · raw message
tools/perf/util/stat-shadow.c +32 -18
130 lines not on this page · raw message
Signature · 1 line
2.29.2.454.gaff20da3a2-goog
Ian Rogers
reviewerPATCH v3 2/5 perf metric: Use NAN for missing event IDs.
In reply to Ian RogersIf during computing a metric an event (id) is missing the parsing aborts. A later patch will make it so that events that aren't used in the output are deliberately omitted, in which case we don't want the abort. Modify the missing ID case to report NAN for these cases.
--- tools/perf/util/expr.y | 9 ++++----- 1 file changed, 4 insertions(+), 5 deletions(-)
tools/perf/util/expr.y +4 -5
@@ -1,6 +1,7 @@ /* Simple expression parser */ %{ #define YYDEBUG 1 +#include <math.h> #include <stdio.h> #include "util.h" #include "util/debug.h"
@@ -88,12 +89,10 @@ expr: NUMBER | ID { struct expr_id_data *data; - if (expr__resolve_id(ctx, $1, &data)) { - free($1); - YYABORT; - } + $$ = NAN; + if (expr__resolve_id(ctx, $1, &data) == 0) + $$ = expr_id_data__value(data); - $$ = expr_id_data__value(data); free($1); } | expr '|' expr { $$ = (long)$1 | (long)$3; }
Signature · 1 line
2.29.2.454.gaff20da3a2-goog
Ian Rogers
reviewerPATCH v3 3/5 perf metric: Rename expr__find_other.
In reply to Ian RogersA later change will remove the notion of other, rename the function to expr__find_ids as this is what it populates.
--- tools/perf/tests/expr.c | 26 +++++++++++++------------- tools/perf/tests/pmu-events.c | 9 ++++----- tools/perf/util/expr.c | 4 ++-- tools/perf/util/expr.h | 2 +- tools/perf/util/metricgroup.c | 2 +- tools/perf/util/stat-shadow.c | 6 +++--- 6 files changed, 24 insertions(+), 25 deletions(-)
tools/perf/tests/expr.c +13 -13
@@ -64,25 +64,25 @@ int test__expr(struct test *t __maybe_unused, int subtest __maybe_unused)TEST_ASSERT_VAL ("missing operand" , ret ==-1 );expr__ctx_clear (ctx); -TEST_ASSERT_VAL ("find other" , -expr__find_other ("FOO + BAR + BAZ + BOZO" ,"FOO" , - ctx,1 ) ==0 ); -TEST_ASSERT_VAL ("find other" ,hashmap__size (ctx->ids) ==3 ); -TEST_ASSERT_VAL ("find other" ,hashmap__find (ctx->ids,"BAR" , +TEST_ASSERT_VAL ("find ids" , +expr__find_ids ("FOO + BAR + BAZ + BOZO" ,"FOO" , + ctx,1 ) ==0 ); +TEST_ASSERT_VAL ("find ids" ,hashmap__size (ctx->ids) ==3 ); +TEST_ASSERT_VAL ("find ids" ,hashmap__find (ctx->ids,"BAR" , (void **)&val_ptr)); -TEST_ASSERT_VAL ("find other" ,hashmap__find (ctx->ids,"BAZ" , +TEST_ASSERT_VAL ("find ids" ,hashmap__find (ctx->ids,"BAZ" , (void **)&val_ptr)); -TEST_ASSERT_VAL ("find other" ,hashmap__find (ctx->ids,"BOZO" , +TEST_ASSERT_VAL ("find ids" ,hashmap__find (ctx->ids,"BOZO" , (void **)&val_ptr));expr__ctx_clear (ctx); -TEST_ASSERT_VAL ("find other" , -expr__find_other ("EVENT1\\,param\\=?@ + EVENT2\\,param\\=?@" , -NULL , ctx,3 ) ==0 ); -TEST_ASSERT_VAL ("find other" ,hashmap__size (ctx->ids) ==2 ); -TEST_ASSERT_VAL ("find other" ,hashmap__find (ctx->ids,"EVENT1,param=3/" , +TEST_ASSERT_VAL ("find ids" , +expr__find_ids ("EVENT1\\,param\\=?@ + EVENT2\\,param\\=?@" , +NULL , ctx,3 ) ==0 ); +TEST_ASSERT_VAL ("find ids" ,hashmap__size (ctx->ids) ==2 ); +TEST_ASSERT_VAL ("find ids" ,hashmap__find (ctx->ids,"EVENT1,param=3/" , (void **)&val_ptr)); -TEST_ASSERT_VAL ("find other" ,hashmap__find (ctx->ids,"EVENT2,param=3/" , +TEST_ASSERT_VAL ("find ids" ,hashmap__find (ctx->ids,"EVENT2,param=3/" , (void **)&val_ptr));expr__ctx_free (ctx);
tools/perf/tests/pmu-events.c +4 -5
@@ -502,9 +502,8 @@ static int test_parsing(void)if (!pe->metric_expr)continue ;expr__ctx_clear (ctx); -if (expr__find_other (pe->metric_expr,NULL , ctx,0 ) - <0 ) { -expr_failure ("Parse other failed" , map, pe); +if (expr__find_ids (pe->metric_expr,NULL , ctx,0 ) <0 ) { +expr_failure ("Parse find ids failed" , map, pe); ret++;continue ; }
@@ -559,8 +558,8 @@ static int metric_parse_fake(const char *str)pr_debug ("parsing '%s'\n" , str); ctx =expr__ctx_new (); -if (expr__find_other (str,NULL , ctx,0 ) <0 ) { -pr_err ("expr__find_other failed\n" ); +if (expr__find_ids (str,NULL , ctx,0 ) <0 ) { +pr_err ("expr__find_ids failed\n" );return -1 ; }
tools/perf/util/expr.c +2 -2
@@ -287,8 +287,8 @@ int expr__parse(double *final_val, struct expr_parse_ctx *ctx,return __expr__parse (final_val, ctx, expr,EXPR_PARSE , runtime) ?-1 :0 ; } -int expr__find_other (const char *expr,const char *one, -struct expr_parse_ctx *ctx,int runtime) +int expr__find_ids (const char *expr,const char *one, +struct expr_parse_ctx *ctx,int runtime) {int ret =__expr__parse (NULL , ctx, expr,EXPR_OTHER , runtime);
tools/perf/util/expr.h +1 -1
@@ -43,7 +43,7 @@ int expr__resolve_id(struct expr_parse_ctx *ctx, const char *id, struct expr_id_data **datap);int expr__parse (double *final_val,struct expr_parse_ctx *ctx,const char *expr,int runtime); -int expr__find_other (const char *expr,const char *one, +int expr__find_ids (const char *expr,const char *one,struct expr_parse_ctx *ids,int runtime);double expr_id_data__value (const struct expr_id_data *data);
tools/perf/util/metricgroup.c +1 -1
@@ -761,7 +761,7 @@ static int __add_metric(struct list_head *metric_list,* For both the parent and referenced metrics, we parse * all the metric's IDs and add it to the parent context. */ -if (expr__find_other (pe->metric_expr,NULL , m->pctx, runtime) <0 ) { +if (expr__find_ids (pe->metric_expr,NULL , m->pctx, runtime) <0 ) {if (m->metric_refs_cnt ==0 ) {expr__ctx_free (m->pctx);free (m);
tools/perf/util/stat-shadow.c +3 -3
@@ -357,9 +357,9 @@ void perf_stat__collect_metric_expr(struct evlist *evsel_list)expr__ctx_clear (ctx); metric_events = counter->metric_events;if (!metric_events) { -if (expr__find_other (counter->metric_expr, - counter->name, - ctx,1 ) <0 ) +if (expr__find_ids (counter->metric_expr, + counter->name, + ctx,1 ) <0 )continue ; metric_events = calloc(sizeof(struct evsel *),
Signature · 1 line
2.29.2.454.gaff20da3a2-goog
Ian Rogers
reviewerPATCH v3 4/5 perf metric: Add utilities to work on ids map.
In reply to Ian RogersAdd utilities to new/free an ids hashmap, as well as to union. Add testing of the union. Unioning hashmaps will be used when parsing the metric, if a value is known then the hashmap is unnecessary, otherwise we need to union together all the event ids to compute their values for reporting.
--- tools/perf/tests/expr.c | 47 ++++++++++++++++++++++ tools/perf/util/expr.c | 87 +++++++++++++++++++++++++++++++++++++++-- tools/perf/util/expr.h | 9 +++++ 3 files changed, 139 insertions(+), 4 deletions(-)
tools/perf/tests/expr.c +47 -0
@@ -6,6 +6,51 @@#include <string.h> #include <linux/zalloc.h> +static int test_ids_union (void ) +{ +struct hashmap *ids1, *ids2; + +/* Empty union. */ + ids1 =ids__new (); +TEST_ASSERT_VAL ("ids__new" , ids1); + ids2 =ids__new (); +TEST_ASSERT_VAL ("ids__new" , ids2); + + ids1 =ids__union (ids1, ids2); +TEST_ASSERT_EQUAL ("union" , (int )hashmap__size (ids1),0 ); + +/* Union {foo, bar} against {}. */ + ids2 =ids__new (); +TEST_ASSERT_VAL ("ids__new" , ids2); + +TEST_ASSERT_EQUAL ("ids__insert" ,ids__insert (ids1,strdup ("foo" ),NULL ),0 ); +TEST_ASSERT_EQUAL ("ids__insert" ,ids__insert (ids1,strdup ("bar" ),NULL ),0 ); + + ids1 =ids__union (ids1, ids2); +TEST_ASSERT_EQUAL ("union" , (int )hashmap__size (ids1),2 ); + +/* Union {foo, bar} against {foo}. */ + ids2 =ids__new (); +TEST_ASSERT_VAL ("ids__new" , ids2); +TEST_ASSERT_EQUAL ("ids__insert" ,ids__insert (ids2,strdup ("foo" ),NULL ),0 ); + + ids1 =ids__union (ids1, ids2); +TEST_ASSERT_EQUAL ("union" , (int )hashmap__size (ids1),2 ); + +/* Union {foo, bar} against {bar,baz}. */ + ids2 =ids__new (); +TEST_ASSERT_VAL ("ids__new" , ids2); +TEST_ASSERT_EQUAL ("ids__insert" ,ids__insert (ids2,strdup ("bar" ),NULL ),0 ); +TEST_ASSERT_EQUAL ("ids__insert" ,ids__insert (ids2,strdup ("baz" ),NULL ),0 ); + + ids1 =ids__union (ids1, ids2); +TEST_ASSERT_EQUAL ("union" , (int )hashmap__size (ids1),3 ); + +ids__free (ids1); + +return 0 ; +} +static int test (struct expr_parse_ctx *ctx,const char *e,double val2) {double val;
@@ -24,6 +69,8 @@ int test__expr(struct test *t __maybe_unused, int subtest __maybe_unused)int ret;struct expr_parse_ctx *ctx; +TEST_ASSERT_EQUAL ("ids_union" ,test_ids_union (),0 ); + ctx =expr__ctx_new ();TEST_ASSERT_VAL ("expr__ctx_new" , ctx);expr__add_id_val (ctx,strdup ("FOO" ),1 );
tools/perf/util/expr.c +83 -4
107 lines not on this page · raw message
tools/perf/util/expr.h +9 -0
@@ -30,9 +30,16 @@ struct expr_scanner_ctx {int runtime; }; +struct hashmap *ids__new (void ); +void ids__free (struct hashmap *ids); +void ids__print (struct hashmap *ids); +int ids__insert (struct hashmap *ids,const char *id,struct expr_id *parent); +struct hashmap *ids__union (struct hashmap *ids1,struct hashmap *ids2); +struct expr_parse_ctx *expr__ctx_new (void );void expr__ctx_clear (struct expr_parse_ctx *ctx);void expr__ctx_free (struct expr_parse_ctx *ctx); +void expr__del_id (struct expr_parse_ctx *ctx,const char *id);int expr__add_id (struct expr_parse_ctx *ctx,const char *id);int expr__add_id_val (struct expr_parse_ctx *ctx,const char *id,double val);
@@ -41,8 +48,10 @@ int expr__get_id(struct expr_parse_ctx *ctx, const char *id, struct expr_id_data **data);int expr__resolve_id (struct expr_parse_ctx *ctx,const char *id,struct expr_id_data **datap); +int expr__parse (double *final_val,struct expr_parse_ctx *ctx,const char *expr,int runtime); +int expr__find_ids (const char *expr,const char *one,struct expr_parse_ctx *ids,int runtime);
Signature · 1 line
2.29.2.454.gaff20da3a2-goog
Ian Rogers
reviewerPATCH v3 5/5 perf metric: Don't compute unused events.
In reply to Ian RogersFor a metric like:
EVENT1 if #smt_on else EVENT2
currently EVENT1 and EVENT2 will be measured and then when the metric is reported EVENT1 or EVENT2 will be printed depending on the value from smt_on() during the expr parsing. Computing both events is unnecessary and can lead to multiplexing as discussed in this thread:
https://lore.kernel.org/lkml/[email protected]/
This change modifies the expression parsing code by:
- getting rid of the "other" parsing and introducing a boolean argument to say whether ids should be computed or not.
- expressions are changed so that a pair of value and ids are returned.
- when computing the metric value the ids are unused.
- when computing the ids, constant values and smt_on are assigned to the value.
- If the value is from an event ID then the event is added to the ids hashmap and the value set to NAN.
- Typically operators union IDs for their inputs and set the value to NAN, however, if the inputs are constant then these are computed and propagated as the value.
- If the input is constant to certain operators like:
IDS1 if CONST else IDS2
then the result will be either IDS1 or IDS2 depending on CONST (which may be evaluated from an entire expression), and so IDS1 or IDS2 may be discarded avoiding events from being programmed.
- The ids at the end of parsing are added to the context.
--- tools/perf/tests/expr.c | 17 ++ tools/perf/util/expr.c | 9 +- tools/perf/util/expr.h | 1 - tools/perf/util/expr.l | 9 - tools/perf/util/expr.y | 373 ++++++++++++++++++++++++++++++++-------- 5 files changed, 319 insertions(+), 90 deletions(-)
tools/perf/tests/expr.c +17 -0
@@ -1,6 +1,7 @@// SPDX-License-Identifier: GPL-2.0 #include "util/debug.h" #include "util/expr.h" +#include "util/smt.h" #include "tests.h" #include <stdlib.h> #include <string.h>
@@ -132,6 +133,22 @@ int test__expr(struct test *t __maybe_unused, int subtest __maybe_unused)TEST_ASSERT_VAL ("find ids" ,hashmap__find (ctx->ids,"EVENT2,param=3/" , (void **)&val_ptr)); +/* Only EVENT1 or EVENT2 need be measured depending on the value of smt_on. */ +expr__ctx_clear (ctx); +TEST_ASSERT_VAL ("find ids" , +expr__find_ids ("EVENT1 if #smt_on else EVENT2" , +NULL , ctx,0 ) ==0 ); +TEST_ASSERT_VAL ("find ids" ,hashmap__size (ctx->ids) ==1 ); +TEST_ASSERT_VAL ("find ids" ,hashmap__find (ctx->ids, +smt_on () ?"EVENT1" :"EVENT2" , + (void **)&val_ptr)); + +/* The expression is a constant 1.0 without needing to evaluate EVENT1. */ +expr__ctx_clear (ctx); +TEST_ASSERT_VAL ("find ids" , +expr__find_ids ("1.0 if EVENT1 > 100.0 else 1.0" , +NULL , ctx,0 ) ==0 ); +TEST_ASSERT_VAL ("find ids" ,hashmap__size (ctx->ids) ==0 );expr__ctx_free (ctx);return 0 ;
tools/perf/util/expr.c +4 -5
@@ -329,10 +329,9 @@ void expr__ctx_free(struct expr_parse_ctx *ctx)static int __expr__parse (double *val,struct expr_parse_ctx *ctx,const char *expr, -int start,int runtime) +bool compute_ids,int runtime) {struct expr_scanner_ctx scanner_ctx = { - .start_token = start, .runtime = runtime, };YY_BUFFER_STATE buffer;
@@ -352,7 +351,7 @@ __expr__parse(double *val, struct expr_parse_ctx *ctx, const char *expr,expr_set_debug (1 , scanner);#endif - ret =expr_parse (val, ctx, scanner); + ret =expr_parse (val, ctx, compute_ids, scanner);expr__flush_buffer (buffer, scanner);expr__delete_buffer (buffer, scanner);
@@ -363,13 +362,13 @@ __expr__parse(double *val, struct expr_parse_ctx *ctx, const char *expr,int expr__parse (double *final_val,struct expr_parse_ctx *ctx,const char *expr,int runtime) { -return __expr__parse (final_val, ctx, expr,EXPR_PARSE , runtime) ?-1 :0 ; +return __expr__parse (final_val, ctx, expr,/*compute_ids=*/ false, runtime) ?-1 :0 ; }int expr__find_ids (const char *expr,const char *one,struct expr_parse_ctx *ctx,int runtime) { -int ret =__expr__parse (NULL , ctx, expr,EXPR_OTHER , runtime); +int ret =__expr__parse (NULL , ctx, expr,/*compute_ids=*/ true, runtime);if (one)expr__del_id (ctx, one);
tools/perf/util/expr.h +0 -1
@@ -26,7 +26,6 @@ struct expr_parse_ctx {struct expr_id_data ;struct expr_scanner_ctx { -int start_token;int runtime; };
tools/perf/util/expr.l +0 -9
@@ -91,15 +91,6 @@ symbol ({spec}|{sym})+ %% struct expr_scanner_ctx *sctx = expr_get_extra(yyscanner); - { - int start_token = sctx->start_token; - - if (sctx->start_token) { - sctx->start_token = 0; - return start_token; - } - } - d_ratio { return D_RATIO; } max { return MAX; } min { return MIN; }
tools/perf/util/expr.y +298 -75
419 lines not on this page · raw message
Signature · 1 line
2.29.2.454.gaff20da3a2-goog
Re: [PATCH v3 5/5] perf metric: Don't compute unused events.
Quoted 7 lines
+| expr '|' expr
tools/perf/util/expr.y +6
-0+{ + if (!compute_ids || (isfinite($1.val) && isfinite($3.val))) { + assert($1.ids == NULL); + assert($3.ids == NULL); + $$.val = (long)$1.val | (long)$3.val; + $$.ids = NULL;
tools/perf/util/expr.y static void expr_error(double *final_val __maybe_unused, · line 160
Quoted 10 lines
tools/perf/util/expr.y +10
-0+ } else { + /* + * LHS or RHS needs to be computed from event IDs, consequently + * so does this expression. Set val to NAN to show that the set + * of all values is possible, the events are the union of those + * on the LHS and RHS. + */ + $$.val = NAN; + $$.ids = ids__union($1.ids, $3.ids); + }
Sorry, still not a fan of the having this nan code all over. It's just ugly.
If you don't want to do the syntax change to still do it in one pass, and given building an AST would be a little complicated.
The original parser I based this code on actually had a byte code version too (see attachment). With that one the lazy evaluation could be done on the byte code level. Originally I didn't include it because it wasn't really
needed for perf, but presumably if we want to do more complicated things it might be useful.
In theory it could speed up performance slightly when an expression needs to be computed multiple times in interval mode.
-Andi
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#include <assert.h>
#include "code.h"
#include "sym.h"
#include "error.h"
static unsigned char *bufs;
static unsigned bufl;
static unsigned char *bufp;
static void overflow(void)
{
yyerror("expression exceeds execution buffer");
}void put_op(enum ops op)
{
if (bufp >= bufs + bufl)
overflow();
*bufp++ = op;
}void put_long(enum ops op, long arg)
{
if (bufp + sizeof(long) + 1 >= bufs + bufl)
overflow();
*bufp++ = op;
memcpy(bufp, &arg, sizeof(long));
bufp += sizeof(long);
}void put_ptr(enum ops op, void * arg)
{
if (bufp + sizeof(void *) + 1 >= bufs + bufl)
overflow();
*bufp++ = op;
memcpy(bufp, &arg, sizeof(void *));
bufp += sizeof(void *);
}void start_def(struct symbol *s)
{
if (!s->undef)
yyerror("symbol %s redefined", s->name);
}void end_def(struct symbol *s)
{
int len;
put_op(OP_RET);
len = bufp - bufs;
s->code = malloc(len);
memcpy(s->code, bufs, len);
bufp = bufs;
s->undef = 0;
}static void execerror(char const *msg)
{
fprintf(stderr, "expression execution error: %s\n", msg);
exit(1);
}#define STACKSIZE 16
#define CSTACKSIZE 16
long execute(unsigned char *bufp)
{
static void *target[] = {
[OP_END] = &&end,
[OP_EVENT] = NULL,
[OP_NUMBER] = &&number,
[OP_PLUS] = &&plus,
[OP_MINUS] = &&minus,
[OP_MUL] = &&mul,
[OP_DIV] = &&div,
[OP_MOD] = &&mod,
[OP_NEGATE] = &&negate,
[OP_CALL] = &&call,
[OP_RET] = &&ret,
[OP_XOR] = &&xor,
[OP_OR] = &&or,
[OP_NOT] = &¬,
[OP_AND] = &&and,
[OP_SHL] = &&shl,
[OP_SHR] = &&shr,
};
long a, b;
long stack[STACKSIZE];
int stackp = 0;
unsigned char *callstack[CSTACKSIZE];
int callstackp = 0;#define getop(x) memcpy(&(x), bufp, sizeof(x)); bufp += sizeof(x)
#define push(x) stack[stackp++] = (x) #define pop() stack[--stackp] #define next() goto *target[(int)*bufp++]
next();
number:
if (stackp == STACKSIZE)
execerror("expression stack overflow");
getop(a);
push(a);
next();#define OP(op) \ b = pop(); \ a = pop(); \ push(a op b); \ next()
plus: OP(+);
minus: OP(-);
mul: OP(*);
div:
b = pop();
if (b == 0)
execerror("division by 0");
a = pop();
push(a / b);
next();mod:
b = pop();
if (b == 0)
execerror("modulo by 0");
a = pop();
push(a % b);
next();negate:
a = pop(); push(-a); next();
and: OP(&);
or: OP(|);
xor: OP(^);
shl: OP(<<);
shr: OP(>>);
not:
a = pop(); push(~a); next();
call: {
struct symbol *s;
getop(s);
if (callstackp == CSTACKSIZE)
execerror("call stack overflow");
callstack[callstackp++] = bufp;
bufp = s->code;
next();
}ret:
bufp = callstack[--callstackp]; next();
end:
assert(bufp == bufs || stackp == 1); assert(callstackp == 0); return stack[0]; }
#undef next
#undef push
#undef pop
#undef getop
void code_init(unsigned char *buf, unsigned len)
{
bufs = buf;
bufp = buf;
bufl = len;
}
enum ops {
OP_END,
OP_EVENT,
OP_NUMBER,
OP_PLUS, OP_MINUS,
OP_MUL, OP_DIV, OP_MOD,
OP_NEGATE,
OP_CALL, OP_RET,
OP_OR, OP_AND, OP_XOR, OP_NOT,
OP_SHL, OP_SHR,
};struct symbol;
void put_op(enum ops op);
void put_long(enum ops op, long arg);
void put_ptr(enum ops op, void *arg);
void code_init(unsigned char *buf, unsigned bufl); void start_def(struct symbol *s);
void end_def(struct symbol *s);
long execute(unsigned char *bufp);
%{
// notebook:
// need unsigned operators?
// don't exit on errors
// don't require expr after defs
// text description for defs
// hash
#include "sym.h"
#include "code.h"
#include "error.h"
%}
%union {
long num;
struct symbol *sym;
}%token DEF
%token <num> EVENT // XXX own type
%token <num> NUMBER
%token <sym> SYMBOL
%left '|'
%left '^'
%left '&'
%left SHL SHR
%left '-' '+'
%left '*' '/' '%'
%left NEG NOT
%{
#include <stdio.h>
#include <string.h>
#include <assert.h>
#include <ctype.h>
#include <stdlib.h>
#include <stdarg.h>
#include <errno.h>
static int yylex(void);
static unsigned char buf[1024];
static char symname[128];
%}
%%
def_and_expr: def_list expr ;
def_list: def_list definition
| ;
definition: DEF SYMBOL { start_def($2); } '=' expr ';' { end_def($2); }
;
expr: EVENT { put_long(OP_EVENT, $1); }
| NUMBER { put_long(OP_NUMBER, $1); }
| SYMBOL { if ($1->undef)
yyerror("undefined symbol %s", $1->name);
put_long(OP_CALL, (long)$1); }
| expr '|' expr { put_op(OP_OR); }
| expr '&' expr { put_op(OP_AND); }
| expr '^' expr { put_op(OP_XOR); }
| expr SHL expr { put_op(OP_SHL); }
| expr SHR expr { put_op(OP_SHR); }
| '~' expr %prec NOT { put_op(OP_NOT); }
| expr '+' expr { put_op(OP_PLUS); }
| expr '-' expr { put_op(OP_MINUS); }
| expr '*' expr { put_op(OP_MUL); }
| expr '/' expr { put_op(OP_DIV); }
| expr '%' expr { put_op(OP_MOD); }
| '-' expr %prec NEG { put_op(OP_NEGATE); }
| '(' expr ')'
;%%
#define SYMHASHSZ 1
struct symbol *slist[SYMHASHSZ];
static int symhash(char *s)
{
return 0; // XXX
}
static struct symbol *getsymbol(char *name)
{
struct symbol *s;
int h = symhash(name);
for (s = slist[h]; s; s = s->next)
if (!strcmp(s->name, name))
return s;
s = malloc(sizeof(struct symbol));
s->name = strdup(name);
s->undef = 1;
s->next = slist[h];
slist[h] = s;
return s;
}static long number(int c)
{
char buf[32];
char *endp;
long num;
int i;
i = 0;
do {
if (i == sizeof buf - 1)
yyerror("number too long");
buf[i++] = c;
c = getchar();
} while (isdigit(c) || c == 'x');
if (c != EOF)
ungetc(c, stdin);
buf[i++] = 0;
errno = 0;
num = strtol(buf, &endp, 0);
if (errno == ERANGE)
yyerror("number over/underflow");
if (endp == buf)
yyerror("cannot parse number");
return num;
}static int symbol(int c)
{
int i = 0;
do {
if (i >= sizeof(symname))
yyerror("symbol too long");
symname[i++] = c;
c = getchar();
} while (isalpha(c) || isdigit(c) || c == '.' || c == '_');
if (c != EOF)
ungetc(c, stdin);
symname[i] = 0;
if (!strcasecmp(symname, "def"))
return DEF;
yylval.sym = getsymbol(symname);
return SYMBOL;
}static int yylex(void)
{
int c, c1;
for (;;) {
c = getchar();
if (c == EOF)
return 0;
switch (c) {
case '\n':
yylineno++;
continue;
case ' ': case '\t': case '\r':
continue;
case '0' ... '9':
yylval.num = number(c);
return NUMBER;
case '+': case '-': case '*': case '/': case '%':
case '(': case ')': case '=': case ';':
case '^': case '&': case '|': case '~':
return c;
case '<':
case '>':
c1 = getchar();
if (c1 == c)
return c == '<' ? SHL : SHR;
break;
case 'A'...'Z':
case 'a'...'z':
case '_':
return symbol(c);
case '#':
do {
c = getchar();
} while (c != '\n' && c != EOF);
continue;
}
yyerror("unknown character '%c'", c);
}
}int main(void)
{
code_init(buf, sizeof buf);
yyparse();
put_op(OP_END);
printf("%ld\n", execute(buf));
return 0;
}