Messages in this thread Patch in this message | | | Date | Mon, 27 Apr 2020 12:11:01 +0200 | From | Jiri Olsa <> | Subject | Re: [PATCH v3 1/7] perf util: Create source line mapping table |
| |
On Mon, Apr 20, 2020 at 09:04:45AM +0800, Jin Yao wrote: > Sometimes, a small change in a hot function reducing the cycles of > this function, but the overall workload doesn't get faster. It is > interesting where the cycles are moved to. > > What it would like is to diff before/after streams. A stream is a > callchain which is aggregated by the branch records from samples. > > By browsing the hot streams, we can understand the hot code flow. > By comparing the cycles variation of same streams between old perf > data and new perf data, we can understand if the cycles are moved to > the unchanged code. > > The before stream is the stream before source line changed > (e.g. streams in perf.data.old). The after stream is the stream > after source line changed (e.g. streams in perf.data). > > Diffing before/after streams compares all streams (or compares top > N hot streams) between two perf data files. > > If all entries of one stream in perf.data.old are fully matched with > all entries of another stream in perf.data, we think these two streams > are matched, otherwise the streams are not matched. > > For example, > > cycles: 1, hits: 26.80% cycles: 1, hits: 27.30% > -------------------------- -------------------------- > main div.c:39 main div.c:39 > main div.c:44 main div.c:44
hi, I'm getting compile error with this patch:
[jolsa@krava perf]$ make JOBS=1 BUILD: Doing 'make -j1' parallel build CC util/srclist.o util/srclist.c: In function ‘srclist__node_new’: util/srclist.c:388:35: error: ‘%s’ directive output may be truncated writing up to 4095 bytes into a region of size 4091 [-Werror=format-truncation=] 388 | snprintf(cmd, sizeof(cmd), "diff %s %s", | ^~ ...... 456 | ret = init_src_info(b_path, a_path, rel_path, &node->info); | ~~~~~~ In file included from /usr/include/stdio.h:867, from util/srclist.c:8: /usr/include/bits/stdio2.h:67:10: note: ‘__builtin___snprintf_chk’ output between 7 and 8197 bytes into a destination of size 4096 67 | return __builtin___snprintf_chk (__s, __n, __USE_FORTIFY_LEVEL - 1, | ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 68 | __bos (__s), __fmt, __va_arg_pack ()); | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ cc1: all warnings being treated as errors mv: cannot stat 'util/.srclist.o.tmp': No such file or directory make[4]: *** [/home/jolsa/kernel/linux-perf/tools/build/Makefile.build:97: util/srclist.o] Error 1 make[3]: *** [/home/jolsa/kernel/linux-perf/tools/build/Makefile.build:139: util] Error 2 make[2]: *** [Makefile.perf:617: perf-in.o] Error 2 make[1]: *** [Makefile.perf:225: sub-make] Error 2 make: *** [Makefile:70: all] Error 2
thanks, jirka
> > It looks that two streams are matched and we can see for the same > streams the cycles are equal and the stream hit percents are > slightly changed. That's expected in the normal range. > > But that's not always true if source lines are changed in perf.data > (e.g. div.c:39 is changed). If the source line is changed, they > are different streams, we can't compare them. We just think the > stream in perf.data is a new one. > > The challenge is how to identify the changed source lines. The basic > idea is to use linux command 'diff' to compare the source file A and > source file A* line by line (assume A is used in perf.data.old > and A* is updated in perf.data). Create a source line mapping table. > > For example, > > Execute 'diff ./before/div.c ./after/div.c' > > 25c25 > < i = rand() % 2; > --- > > i = rand() % 4; > 39c39 > < for (i = 0; i < 2000000000; i++) { > --- > > for (i = 0; i < 20000000001; i++) { > > div.c (after -> before) lines mapping: > 0 -> 0 > 1 -> 1 > 2 -> 2 > 3 -> 3 > 4 -> 4 > 5 -> 5 > 6 -> 6 > 7 -> 7 > 8 -> 8 > 9 -> 9 > ... > 24 -> 24 > 25 -> -1 > 26 -> 26 > 27 -> 27 > 28 -> 28 > 29 -> 29 > 30 -> 30 > 31 -> 31 > 32 -> 32 > 33 -> 33 > 34 -> 34 > 35 -> 35 > 36 -> 36 > 37 -> 37 > 38 -> 38 > 39 -> -1 > 40 -> 40 > ... > > From the table, we can easily know div.c:39 is source line changed. > (it's mapped to -1). So these two streams are not matched. > > This patch can also handle the cases of new source lines insertion > and old source lines deletion. This source line mapping table is a > base for next processing for stream comparison. > > This patch creates a new rblist 'srclist' to manage the source line > mapping tables. Each node contains the source line mapping table of > a before/after source file pair. The node is created on demand as > we process the samples. So it's likely we don't need to create so many > nodes. > > v2: > --- > Refine the code > 1. calloc -> zalloc > 2. Functions operating on a 'struct line_pair' have the > line_pair__ prefix. > 3. Check get_range() return value. > 4. Use fgets to replace fgetc for getting the number of lines. > 5. Use path__join to generate the full path. > 6. Keep the buffer after calling getline. > > Signed-off-by: Jin Yao <yao.jin@linux.intel.com> > --- > tools/perf/util/Build | 1 + > tools/perf/util/srclist.c | 555 ++++++++++++++++++++++++++++++++++++++ > tools/perf/util/srclist.h | 65 +++++ > 3 files changed, 621 insertions(+) > create mode 100644 tools/perf/util/srclist.c > create mode 100644 tools/perf/util/srclist.h > > diff --git a/tools/perf/util/Build b/tools/perf/util/Build > index c0cf8dff694e..b9bf620b60f0 100644 > --- a/tools/perf/util/Build > +++ b/tools/perf/util/Build > @@ -99,6 +99,7 @@ perf-y += call-path.o > perf-y += rwsem.o > perf-y += thread-stack.o > perf-y += spark.o > +perf-y += srclist.o > perf-$(CONFIG_AUXTRACE) += auxtrace.o > perf-$(CONFIG_AUXTRACE) += intel-pt-decoder/ > perf-$(CONFIG_AUXTRACE) += intel-pt.o > diff --git a/tools/perf/util/srclist.c b/tools/perf/util/srclist.c > new file mode 100644 > index 000000000000..8060e4855d11 > --- /dev/null > +++ b/tools/perf/util/srclist.c > @@ -0,0 +1,555 @@ > +// SPDX-License-Identifier: GPL-2.0 > +/* > + * Manage difference of source lines > + * Copyright (c) 2020, Intel Corporation. > + * Author: Jin Yao > + */ > +#include <stdlib.h> > +#include <stdio.h> > +#include <sys/types.h> > +#include <inttypes.h> > +#include <string.h> > +#include <strings.h> > +#include <unistd.h> > +#include <err.h> > +#include <errno.h> > +#include <limits.h> > +#include <stdbool.h> > +#include <linux/zalloc.h> > +#include "strlist.h" > +#include "srclist.h" > +#include "debug.h" > +#include "path.h" > + > +enum { > + DIFF_LINE_ADD, > + DIFF_LINE_DEL, > + DIFF_LINE_CHANGE > +}; > + > +static void get_full_path(const char *dir, const char *rel_path, > + char *full_path, int size) > +{ > + if (!dir) { > + snprintf(full_path, size, "%s", rel_path); > + return; > + } > + > + path__join(full_path, size, dir, rel_path); > +} > + > +static int path__number_of_lines(char *path) > +{ > + FILE *fp; > + char buf[4096], *p, last = 0; > + int num = 0; > + > + fp = fopen(path, "r"); > + if (!fp) { > + pr_debug("Failed to open file %s\n", path); > + return -1; > + } > + > + while (!feof(fp)) { > + p = fgets(buf, sizeof(buf), fp); > + if (!p) > + break; > + > + last = p[strlen(p) - 1]; > + if (last == '\n') > + num++; > + } > + > + fclose(fp); > + > + if (last != '\n' && last != 0) > + num++; > + > + return num; > +} > + > +static int get_digit(char *str, char **end_str, int *val) > +{ > + int v; > + char *end; > + > + errno = 0; > + v = strtol(str, &end, 10); > + if ((errno == ERANGE && (v == INT_MAX || v == INT_MIN)) > + || (errno != 0 && v == 0)) { > + return -1; > + } > + > + if (end == str) > + return -1; > + > + *val = v; > + *end_str = end; > + return 0; > +} > + > +static int get_range(char *str, int *start_val, int *end_val) > +{ > + int val, ret; > + char *end, *next; > + > + *start_val = -1; > + *end_val = -1; > + > + ret = get_digit(str, &end, &val); > + if (ret) > + return ret; > + > + *start_val = val; > + > + if (*end != '\0') { > + next = end + 1; > + ret = get_digit(next, &end, &val); > + if (ret) > + return ret; > + > + *end_val = val; > + } > + > + return 0; > +} > + > +static int opr_str_idx(char *str, int len, char ch) > +{ > + int i; > + > + for (i = 0; i < len; i++) { > + if (str[i] == ch) > + break; > + } > + > + if (i == len || i == 0 || i == len - 1) > + return -1; > + > + if (str[i - 1] >= '0' && str[i - 1] <= '9' && > + str[i + 1] >= '0' && str[i + 1] <= '9') { > + return i; > + } > + > + return -1; > +} > + > +static bool get_diff_operation(char *str, int *opr, int *b_start, int *b_end, > + int *a_start, int *a_end) > +{ > + int idx, len; > + > + if (str[0] == '<' || str[0] == '>' || str[0] == '-') > + return false; > + > + len = strlen(str); > + > + /* > + * For example, > + * 5,6d4 > + * 8a7 > + * 20,21c19 > + */ > + idx = opr_str_idx(str, len, 'd'); > + if (idx != -1) { > + *opr = DIFF_LINE_DEL; > + goto exit; > + } > + > + idx = opr_str_idx(str, len, 'a'); > + if (idx != -1) { > + *opr = DIFF_LINE_ADD; > + goto exit; > + } > + > + idx = opr_str_idx(str, len, 'c'); > + if (idx != -1) { > + *opr = DIFF_LINE_CHANGE; > + goto exit; > + } > + > +exit: > + if (idx != -1) { > + str[idx] = 0; > + if (get_range(str, b_start, b_end) != 0) > + return false; > + > + if (get_range(&str[idx + 1], a_start, a_end) != 0) > + return false; > + > + return true; > + } > + > + return false; > +} > + > +static int line_pair__del_lines(struct line_pair *lines, int b_start, int b_end, > + int a_start, int a_end __maybe_unused, > + int *nr_lines, int *b_adjust) > +{ > + int i = *nr_lines; > + bool set = false; > + > + /* > + * For example, 5,6d4 > + * It means line 5 ~ line 6 of file1 are not same as line 4 of file2 > + * because line 5 ~ line 6 are deleted. > + */ > + > + if (a_start == i) { > + lines[i].a_nr = i; > + lines[i].b_nr = i + *b_adjust; > + set = true; > + } > + > + if (b_end != -1) > + *b_adjust += b_end - b_start + 1; > + else > + *b_adjust += 1; > + > + if (!set) { > + lines[i].a_nr = i; > + lines[i].b_nr = i + *b_adjust; > + } > + > + *nr_lines = i + 1; > + return 0; > +} > + > +static int line_pair__add_lines(struct line_pair *lines, > + int b_start __maybe_unused, > + int b_end __maybe_unused, > + int a_start, int a_end, int *nr_lines, > + int *b_adjust) > +{ > + int i = *nr_lines; > + > + /* > + * For example, 8a7 > + * It means line 8 at file1 is not same as line 7 at file2 > + * because a new line (line 7) is inserted to file2. > + */ > + if (a_end != -1) { > + for (int j = 0; j < a_end - a_start + 1; j++) { > + lines[i].a_nr = i; > + lines[i].b_nr = -1; > + i++; > + } > + *b_adjust -= a_end - a_start + 1; > + } else { > + lines[i].a_nr = i; > + lines[i].b_nr = -1; > + i++; > + *b_adjust -= 1; > + } > + > + *nr_lines = i; > + return 0; > +} > + > +static int line_pair__change_lines(struct line_pair *lines, int b_start, > + int b_end, int a_start, int a_end, > + int *nr_lines, int *b_adjust) > +{ > + int i = *nr_lines; > + > + /* > + * For example, 20,21c19 > + * It means line20~line21 of file1 are not same as line19 of file2 > + * since they are changed. > + */ > + > + if (a_end != -1) { > + for (int j = 0; j < a_end - a_start + 1; j++) { > + lines[i].a_nr = i; > + lines[i].b_nr = -1; > + i++; > + } > + } else { > + lines[i].a_nr = i; > + lines[i].b_nr = -1; > + i++; > + } > + > + if (b_end != -1) > + *b_adjust += b_end - b_start; > + > + if (a_end != -1) > + *b_adjust -= a_end - a_start; > + > + *nr_lines = i; > + return 0; > +} > + > +static int line_pair__update_lines(struct line_pair *lines, int opr, > + int b_start, int b_end, int a_start, > + int a_end, int *nr_lines, int *b_adjust) > +{ > + int i = *nr_lines; > + > + while (i < a_start) { > + lines[i].a_nr = i; > + lines[i].b_nr = i + *b_adjust; > + i++; > + } > + > + *nr_lines = i; > + > + switch (opr) { > + case DIFF_LINE_DEL: > + line_pair__del_lines(lines, b_start, b_end, a_start, a_end, > + nr_lines, b_adjust); > + break; > + > + case DIFF_LINE_ADD: > + line_pair__add_lines(lines, b_start, b_end, a_start, a_end, > + nr_lines, b_adjust); > + break; > + > + case DIFF_LINE_CHANGE: > + line_pair__change_lines(lines, b_start, b_end, a_start, > + a_end, nr_lines, b_adjust); > + break; > + > + default: > + break; > + } > + > + return 0; > +} > + > +static void line_pair__update_remaining(struct line_pair *lines, int a_num, > + int *nr_lines, int b_adjust) > +{ > + int i; > + > + for (i = *nr_lines; i <= a_num; i++) { > + lines[i].a_nr = i; > + lines[i].b_nr = i + b_adjust; > + } > + > + *nr_lines = i; > +} > + > +static int build_mapping_table(FILE *fp, struct line_pair *lines, > + int *nr_lines, int a_num) > +{ > + char *str = NULL, *p; > + size_t len = 0; > + int opr, b_start, b_end, a_start, a_end, b_adjust = 0; > + > + *nr_lines = 1; /* First line is reserved */ > + > + while (getline(&str, &len, fp) > 0) { > + p = strchr(str, '\n'); > + if (p) > + *p = '\0'; > + > + pr_debug("%s\n", str); > + > + if (!get_diff_operation(str, &opr, &b_start, &b_end, > + &a_start, &a_end)) { > + continue; > + } > + > + line_pair__update_lines(lines, opr, b_start, b_end, a_start, > + a_end, nr_lines, &b_adjust); > + } > + > + line_pair__update_remaining(lines, a_num, nr_lines, b_adjust); > + > + free(str); > + return 0; > +} > + > +static int src_info__create_line_mapping(struct src_info *info, char *b_path, > + char *a_path) > +{ > + char cmd[PATH_MAX]; > + FILE *fp = NULL; > + int ret = -1; > + > + info->nr_lines_before = path__number_of_lines(b_path); > + if (info->nr_lines_before == -1) > + goto out; > + > + info->nr_lines_after = path__number_of_lines(a_path); > + if (info->nr_lines_after == -1) > + goto out; > + > + /* Reserve first line */ > + info->nr_max = info->nr_lines_before + info->nr_lines_after + 1; > + info->lines = calloc(info->nr_max, sizeof(struct line_pair)); > + if (!info->lines) { > + pr_err("Failed to alloc memory for lines\n"); > + goto out; > + } > + > + snprintf(cmd, sizeof(cmd), "diff %s %s", > + b_path, a_path); > + > + pr_debug("Execute '%s'\n", cmd); > + > + fp = popen(cmd, "r"); > + if (!fp) { > + pr_err("Failed to execute '%s'\n", cmd); > + goto out; > + } > + > + ret = build_mapping_table(fp, info->lines, &info->nr_lines, > + info->nr_lines_after); > + > +out: > + if (fp) > + fclose(fp); > + > + return ret; > +} > + > +static void free_src_info(struct src_info *info) > +{ > + zfree(&info->rel_path); > + zfree(&info->lines); > +} > + > +static int init_src_info(char *b_path, char *a_path, const char *rel_path, > + struct src_info *info) > +{ > + int ret; > + > + info->rel_path = strdup(rel_path); > + if (!info->rel_path) > + return -1; > + > + ret = src_info__create_line_mapping(info, b_path, a_path); > + if (ret) > + free_src_info(info); > + > + return ret; > +} > + > +static void free_src_node(struct src_node *node) > +{ > + if (!node) > + return; > + > + free_src_info(&node->info); > + free(node); > +} > + > +static struct rb_node *srclist__node_new(struct rblist *rblist, > + const void *entry) > +{ > + struct srclist *slist = container_of(rblist, struct srclist, rblist); > + const char *rel_path = entry; > + char b_path[PATH_MAX], a_path[PATH_MAX]; > + struct src_node *node; > + int ret; > + > + get_full_path(slist->before_dir, rel_path, b_path, PATH_MAX); > + get_full_path(slist->after_dir, rel_path, a_path, PATH_MAX); > + > + node = zalloc(sizeof(*node)); > + if (!node) > + return NULL; > + > + ret = init_src_info(b_path, a_path, rel_path, &node->info); > + if (ret) > + goto err; > + > + return &node->rb_node; > + > +err: > + free_src_node(node); > + return NULL; > +} > + > +static void srclist__node_delete(struct rblist *rblist __maybe_unused, > + struct rb_node *rb_node) > +{ > + struct src_node *node = container_of(rb_node, struct src_node, rb_node); > + > + free_src_info(&node->info); > + free(node); > +} > + > +static int srclist__node_cmp(struct rb_node *rb_node, const void *entry) > +{ > + struct src_node *node = container_of(rb_node, struct src_node, rb_node); > + const char *str = entry; > + > + return strcmp(node->info.rel_path, str); > +} > + > +struct srclist *srclist__new(const char *before_dir, const char *after_dir) > +{ > + struct srclist *slist = zalloc(sizeof(*slist)); > + > + if (!slist) > + return NULL; > + > + rblist__init(&slist->rblist); > + slist->rblist.node_cmp = srclist__node_cmp; > + slist->rblist.node_new = srclist__node_new; > + slist->rblist.node_delete = srclist__node_delete; > + > + slist->before_dir = before_dir; > + slist->after_dir = after_dir; > + return slist; > +} > + > +void srclist__delete(struct srclist *slist) > +{ > + if (slist) > + rblist__delete(&slist->rblist); > +} > + > +struct src_node *srclist__find(struct srclist *slist, char *rel_path, > + bool create) > +{ > + struct src_node *node = NULL; > + struct rb_node *rb_node; > + > + if (create) > + rb_node = rblist__findnew(&slist->rblist, (void *)rel_path); > + else > + rb_node = rblist__find(&slist->rblist, (void *)rel_path); > + > + if (rb_node) > + node = container_of(rb_node, struct src_node, rb_node); > + > + return node; > +} > + > +struct line_pair *srclist__line_pair(struct src_node *node, int a_nr) > +{ > + struct src_info *info = &node->info; > + > + if (a_nr < info->nr_lines && a_nr > 0) > + return &info->lines[a_nr]; > + > + pr_debug("Exceeds line range: nr_lines = %d, a_nr = %d\n", > + info->nr_lines, a_nr); > + > + return NULL; > +} > + > +void srclist__dump(struct srclist *slist) > +{ > + struct src_node *node; > + struct src_info *info; > + int i; > + > + srclist__for_each_entry(node, slist) { > + info = &node->info; > + > + pr_debug("%s (after -> before) lines mapping:\n", > + info->rel_path); > + > + for (i = 0; i < info->nr_lines; i++) { > + pr_debug("%d -> %d\n", > + info->lines[i].a_nr, > + info->lines[i].b_nr); > + } > + } > +} > diff --git a/tools/perf/util/srclist.h b/tools/perf/util/srclist.h > new file mode 100644 > index 000000000000..f25b0de91a13 > --- /dev/null > +++ b/tools/perf/util/srclist.h > @@ -0,0 +1,65 @@ > +/* SPDX-License-Identifier: GPL-2.0 */ > +#ifndef __PERF_SRCLIST_H > +#define __PERF_SRCLIST_H > + > +#include <linux/types.h> > +#include <linux/rbtree.h> > +#include "rblist.h" > + > +struct line_pair { > + int a_nr; /* line nr in after.c */ > + int b_nr; /* line nr in before.c */ > +}; > + > +struct src_node; > + > +struct src_info { > + char *rel_path; /* relative path */ > + struct line_pair *lines; > + int nr_max; > + int nr_lines; > + int nr_lines_before; > + int nr_lines_after; > +}; > + > +struct src_node { > + struct rb_node rb_node; > + struct src_info info; > +}; > + > +struct srclist { > + struct rblist rblist; > + const char *before_dir; > + const char *after_dir; > +}; > + > +struct srclist *srclist__new(const char *before_dir, const char *after_dir); > +void srclist__delete(struct srclist *slist); > + > +struct src_node *srclist__find(struct srclist *slist, char *rel_path, > + bool create); > + > +struct line_pair *srclist__line_pair(struct src_node *node, int a_nr); > +void srclist__dump(struct srclist *slist); > + > +static inline struct src_node *srclist__first(struct srclist *slist) > +{ > + struct rb_node *rn = rb_first_cached(&slist->rblist.entries); > + > + return rn ? rb_entry(rn, struct src_node, rb_node) : NULL; > +} > + > +static inline struct src_node *srclist__next(struct src_node *sn) > +{ > + struct rb_node *rn; > + > + if (!sn) > + return NULL; > + rn = rb_next(&sn->rb_node); > + return rn ? rb_entry(rn, struct src_node, rb_node) : NULL; > +} > + > +#define srclist__for_each_entry(pos, slist) \ > + for (pos = srclist__first(slist); pos; pos = srclist__next(pos)) > + > +#endif /* __PERF_SRCLIST_H */ > -- > 2.17.1
| |