[PATCH 0/4] perf annotate-data: Support flexible array types

[PATCH 0/4] perf annotate-data: Support flexible array types

[Namhyung Kim]

Hello,

The flexible arrays are dynamically allocated with different size.  So checking
with the original type size won't match and cannot match the sample.  This patch
series detects those flex-arrays and allows accesses beyond the original size.

I'm not sure what's the best way to add test codes for data type profiling as it
seems we need to add a lot more workloads for different cases.  Probably we may
want to split the workloads as separate binaries.

Thanks,
Namhyung


Cc: Zecheng Li <zli94@ncsu.edu>
Cc: Yanbo Zhao <yzhao62@ncsu.edu>
Cc: Tengda Wu <wutengda@huaweicloud.com>
Cc: Shuai Xue <xueshuai@linux.alibaba.com>

Namhyung Kim (4):
  perf annotate-data: Convert type histogram to hashmap
  perf dwarf-aux: Add die_has_flex_array() helper
  perf annotate-date: Allow out-of-size access for flex-array types
  perf annotate-data: Adjust type offset for flex-array

 tools/perf/ui/browsers/annotate-data.c |  11 +-
 tools/perf/util/annotate-data.c        | 167 +++++++++++++++++++------
 tools/perf/util/annotate-data.h        |  10 +-
 tools/perf/util/dwarf-aux.c            |  57 +++++++++
 tools/perf/util/dwarf-aux.h            |   3 +
 5 files changed, 202 insertions(+), 46 deletions(-)

-- 
2.55.0.1032.g73a4cd73de-goog

[PATCH 1/4] perf annotate-data: Convert type histogram to hashmap

[Namhyung Kim]

The type histogram maintains sample counts and periods per offset.  Use
a hashmap instead of an array to reduce the memory overhead.

No functional changes intended.

Signed-off-by: Namhyung Kim <namhyung@kernel.org>
---
 tools/perf/ui/browsers/annotate-data.c | 11 ++--
 tools/perf/util/annotate-data.c        | 72 ++++++++++++++++----------
 tools/perf/util/annotate-data.h        |  8 +--
 3 files changed, 58 insertions(+), 33 deletions(-)

diff --git a/tools/perf/ui/browsers/annotate-data.c b/tools/perf/ui/browsers/annotate-data.c
index aa8c89fe2e82c1c5..82667c6ae2e746c6 100644
--- a/tools/perf/ui/browsers/annotate-data.c
+++ b/tools/perf/ui/browsers/annotate-data.c
@@ -62,12 +62,17 @@ static int get_member_overhead(struct annotated_data_type *adt,
 
 		k = 0;
 		for_each_group_evsel(evsel, leader) {
+			struct type_hist_entry *hist;
+
 			if (symbol_conf.skip_empty &&
 			    evsel__hists(evsel)->stats.nr_samples == 0)
 				continue;
 
-			h = adt->histograms[evsel->core.idx];
-			update_hist_entry(&entry->hists[k++], &h->addr[offset]);
+			h = &adt->histograms[evsel->core.idx];
+			if (!hashmap__find(&h->samples, offset, &hist))
+				continue;
+
+			update_hist_entry(&entry->hists[k++], hist);
 		}
 	}
 	return 0;
@@ -416,7 +421,7 @@ static void browser__write(struct ui_browser *uib, void *entry, int row)
 
 	/* print the number */
 	for_each_group_evsel(evsel, leader) {
-		struct type_hist *h = adt->histograms[evsel->core.idx];
+		struct type_hist *h = &adt->histograms[evsel->core.idx];
 
 		if (symbol_conf.skip_empty &&
 		    evsel__hists(evsel)->stats.nr_samples == 0)
diff --git a/tools/perf/util/annotate-data.c b/tools/perf/util/annotate-data.c
index 4e4c587640823c81..aff60a630fd05b01 100644
--- a/tools/perf/util/annotate-data.c
+++ b/tools/perf/util/annotate-data.c
@@ -1750,42 +1750,45 @@ struct annotated_data_type *find_data_type(struct data_loc_info *dloc)
 	return dso__findnew_data_type(dso, &type_die);
 }
 
+static size_t data_type_hash(long key, void *ctx __maybe_unused)
+{
+	return key;
+}
+
+static bool data_type_equal(long key1, long key2, void *ctx __maybe_unused)
+{
+	return key1 == key2;
+}
+
 static int alloc_data_type_histograms(struct annotated_data_type *adt, int nr_entries)
 {
 	int i;
-	size_t sz = sizeof(struct type_hist);
 
-	sz += sizeof(struct type_hist_entry) * adt->self.size;
-
-	/* Allocate a table of pointers for each event */
+	/* Allocate a histogram for each event */
 	adt->histograms = calloc(nr_entries, sizeof(*adt->histograms));
 	if (adt->histograms == NULL)
 		return -ENOMEM;
 
-	/*
-	 * Each histogram is allocated for the whole size of the type.
-	 * TODO: Probably we can move the histogram to members.
-	 */
 	for (i = 0; i < nr_entries; i++) {
-		adt->histograms[i] = zalloc(sz);
-		if (adt->histograms[i] == NULL)
-			goto err;
+		hashmap__init(&adt->histograms[i].samples, data_type_hash,
+			      data_type_equal, /*ctx=*/NULL);
 	}
 
 	adt->nr_histograms = nr_entries;
 	return 0;
-
-err:
-	while (--i >= 0)
-		zfree(&(adt->histograms[i]));
-	zfree(&adt->histograms);
-	return -ENOMEM;
 }
 
 static void delete_data_type_histograms(struct annotated_data_type *adt)
 {
-	for (int i = 0; i < adt->nr_histograms; i++)
-		zfree(&(adt->histograms[i]));
+	for (int i = 0; i < adt->nr_histograms; i++) {
+		struct hashmap *map = &adt->histograms[i].samples;
+		struct hashmap_entry *pos, *tmp;
+		size_t bkt;
+
+		hashmap__for_each_entry_safe(map, pos, tmp, bkt)
+			free(pos->pvalue);
+		hashmap__clear(map);
+	}
 
 	zfree(&adt->histograms);
 	adt->nr_histograms = 0;
@@ -1824,6 +1827,7 @@ int annotated_data_type__update_samples(struct annotated_data_type *adt,
 					int nr_samples, u64 period)
 {
 	struct type_hist *h;
+	struct type_hist_entry *entry;
 
 	if (adt == NULL)
 		return 0;
@@ -1838,12 +1842,23 @@ int annotated_data_type__update_samples(struct annotated_data_type *adt,
 	if (offset < 0 || offset >= adt->self.size)
 		return -1;
 
-	h = adt->histograms[evsel->core.idx];
+	h = &adt->histograms[evsel->core.idx];
 
 	h->nr_samples += nr_samples;
-	h->addr[offset].nr_samples += nr_samples;
 	h->period += period;
-	h->addr[offset].period += period;
+
+	if (!hashmap__find(&h->samples, offset, &entry)) {
+		entry = zalloc(sizeof(*entry));
+		if (entry == NULL)
+			return -1;
+
+		if (hashmap__append(&h->samples, offset, entry) < 0) {
+			free(entry);
+			return -1;
+		}
+	}
+	entry->nr_samples += nr_samples;
+	entry->period += period;
 	return 0;
 }
 
@@ -1911,14 +1926,14 @@ static void print_annotated_data_type(struct annotated_data_type *mem_type,
 				      struct evsel *evsel, int indent)
 {
 	struct annotated_member *child;
-	struct type_hist *h = mem_type->histograms[evsel->core.idx];
+	struct type_hist *h;
 	int i, nr_events = 0, samples = 0;
 	u64 period = 0;
 	int width = symbol_conf.show_total_period ? 11 : 7;
 	struct evsel *pos;
 
 	for_each_group_evsel(pos, evsel) {
-		h = mem_type->histograms[pos->core.idx];
+		h = &mem_type->histograms[pos->core.idx];
 
 		if (symbol_conf.skip_empty &&
 		    evsel__hists(pos)->stats.nr_samples == 0)
@@ -1927,8 +1942,13 @@ static void print_annotated_data_type(struct annotated_data_type *mem_type,
 		samples = 0;
 		period = 0;
 		for (i = 0; i < member->size; i++) {
-			samples += h->addr[member->offset + i].nr_samples;
-			period += h->addr[member->offset + i].period;
+			struct type_hist_entry *entry;
+
+			if (!hashmap__find(&h->samples, member->offset + i, &entry))
+				continue;
+
+			samples += entry->nr_samples;
+			period += entry->period;
 		}
 		print_annotated_data_value(h, period, samples);
 		nr_events++;
diff --git a/tools/perf/util/annotate-data.h b/tools/perf/util/annotate-data.h
index c26130744260955f..ca2096a9ee62cbfe 100644
--- a/tools/perf/util/annotate-data.h
+++ b/tools/perf/util/annotate-data.h
@@ -73,12 +73,12 @@ struct type_hist_entry {
  * struct type_hist - Type histogram for each event
  * @nr_samples: Total number of samples in this data type
  * @period: Total count of the event in this data type
- * @offset: Array of histogram entry
+ * @samples: Hashmap of (offset, type_hist_entry)
  */
 struct type_hist {
 	u64			nr_samples;
 	u64			period;
-	struct type_hist_entry	addr[];
+	struct hashmap		samples;
 };
 
 /**
@@ -86,7 +86,7 @@ struct type_hist {
  * @node: RB-tree node for dso->type_tree
  * @self: Actual type information
  * @nr_histogram: Number of histogram entries
- * @histograms: An array of pointers to histograms
+ * @histograms: An array of histograms
  *
  * This represents a data type accessed by samples in the profile data.
  */
@@ -94,7 +94,7 @@ struct annotated_data_type {
 	struct rb_node node;
 	struct annotated_member self;
 	int nr_histograms;
-	struct type_hist **histograms;
+	struct type_hist *histograms;
 };
 
 extern struct annotated_data_type unknown_type;
-- 
2.55.0.1032.g73a4cd73de-goog

[PATCH 2/4] perf dwarf-aux: Add die_has_flex_array() helper

[Namhyung Kim]

The die_has_flex_array() returns true when the given type is a struct
and contains an array at the end of the struct.

Cc: Masami Hiramatsu <mhiramat@kernel.org>
Signed-off-by: Namhyung Kim <namhyung@kernel.org>
---
 tools/perf/util/dwarf-aux.c | 57 +++++++++++++++++++++++++++++++++++++
 tools/perf/util/dwarf-aux.h |  3 ++
 2 files changed, 60 insertions(+)

diff --git a/tools/perf/util/dwarf-aux.c b/tools/perf/util/dwarf-aux.c
index d7160f87ac7d7ab3..98d018798fa750ae 100644
--- a/tools/perf/util/dwarf-aux.c
+++ b/tools/perf/util/dwarf-aux.c
@@ -2180,3 +2180,60 @@ Dwarf_Die *die_deref_ptr_type(Dwarf_Die *ptr_die, int offset,
 
 	return die_get_member_type(&type_die, offset, die_mem);
 }
+
+static bool __die_find_last_member(Dwarf_Die *parent_die, Dwarf_Die *die_mem)
+{
+	Dwarf_Die tmp_die;
+	bool found = false;
+
+	if (dwarf_child(parent_die, &tmp_die))
+		return false;
+
+	do {
+		if (dwarf_tag(&tmp_die) == DW_TAG_member) {
+			memcpy(die_mem, &tmp_die, sizeof(tmp_die));
+			found = true;
+		}
+	} while (dwarf_siblingof(&tmp_die, &tmp_die) == 0);
+
+	return found;
+}
+
+/**
+ * die_has_flex_array - Check if the given type has a flex-array at the end
+ * @parent_die: a pointer to type DIE
+ *
+ * This function returns %true iff @parent_die is a struct type and has an
+ * array at the end.  Note that the flex-array has no element, it should have
+ * no size and the parent size doesn't include the flex-array.  So it should
+ * locate at the offset of the parent size.
+ *
+ * For simplicity, it assumes the parent size of aligned with the flex-array.
+ */
+bool die_has_flex_array(Dwarf_Die *parent_die)
+{
+	Dwarf_Die die_mem, type_die;
+	Dwarf_Word size, loc;
+
+	if (dwarf_tag(parent_die) != DW_TAG_structure_type)
+		return false;
+
+	if (dwarf_aggregate_size(parent_die, &size) < 0)
+		return false;
+
+	/* get the member field at the end of the struct */
+	if (!__die_find_last_member(parent_die, &die_mem))
+		return false;
+
+	/* get the type of the member */
+	if (die_get_real_type(&die_mem, &type_die) == NULL)
+		return false;
+
+	if (dwarf_tag(&type_die) == DW_TAG_array_type)
+		return die_get_data_member_location(&die_mem, &loc) == 0 && loc == size;
+
+	if (dwarf_tag(&type_die) == DW_TAG_structure_type)
+		return die_has_flex_array(&type_die);
+
+	return false;
+}
diff --git a/tools/perf/util/dwarf-aux.h b/tools/perf/util/dwarf-aux.h
index 161f0bf980b6ee6a..9b662db710220522 100644
--- a/tools/perf/util/dwarf-aux.h
+++ b/tools/perf/util/dwarf-aux.h
@@ -189,4 +189,7 @@ void die_collect_global_vars(Dwarf_Die *cu_die, struct die_var_type **var_types)
 /* Get the frame base information from CFA */
 int die_get_cfa(Dwarf *dwarf, u64 pc, int *preg, int *poffset);
 
+/* Check whether given type has a flex array */
+bool die_has_flex_array(Dwarf_Die *parent_die);
+
 #endif /* _DWARF_AUX_H */
-- 
2.55.0.1032.g73a4cd73de-goog

[PATCH 3/4] perf annotate-date: Allow out-of-size access for flex-array types

[Namhyung Kim]

Structs that have a flex array will have accesses beyond its original
size as the array was declared as 0 sized.  For now, it just allow any
offset bigger than the size.  It could be refined later.

Signed-off-by: Namhyung Kim <namhyung@kernel.org>
---
 tools/perf/util/annotate-data.c | 22 +++++++++++++++-------
 tools/perf/util/annotate-data.h |  2 ++
 2 files changed, 17 insertions(+), 7 deletions(-)

diff --git a/tools/perf/util/annotate-data.c b/tools/perf/util/annotate-data.c
index aff60a630fd05b01..ad043403ced58d98 100644
--- a/tools/perf/util/annotate-data.c
+++ b/tools/perf/util/annotate-data.c
@@ -248,8 +248,15 @@ static int __add_member_cb(Dwarf_Die *die, void *arg)
 	else
 		die_mem = member_type;
 
-	if (dwarf_aggregate_size(&die_mem, &size) < 0)
-		size = 0;
+	if (dwarf_aggregate_size(&die_mem, &size) < 0) {
+		if (dwarf_tag(&die_mem) == DW_TAG_array_type) { /* flex-array? */
+			__die_get_real_type(&die_mem, &die_mem);
+			if (dwarf_aggregate_size(&die_mem, &size) < 0)
+				size = 0;
+		} else {
+			size = 0;
+		}
+	}
 
 	if (dwarf_attr_integrate(die, DW_AT_data_member_location, &attr)) {
 		if (dwarf_formudata(&attr, &loc) != 0) {
@@ -399,6 +406,7 @@ static struct annotated_data_type *dso__findnew_data_type(struct dso *dso,
 	result->self.type_name = type_name;
 	result->self.size = size;
 	INIT_LIST_HEAD(&result->self.children);
+	result->flex_array = die_has_flex_array(type_die);
 
 	if (symbol_conf.annotate_data_member)
 		add_member_types(result, type_die);
@@ -559,7 +567,7 @@ static enum type_match_result check_variable(struct data_loc_info *dloc,
 		return PERF_TMR_NO_SIZE;
 
 	/* Minimal sanity check */
-	if ((unsigned)offset >= size)
+	if ((unsigned)offset >= size && !die_has_flex_array(&sized_type))
 		return PERF_TMR_BAD_OFFSET;
 
 	return PERF_TMR_OK;
@@ -1168,7 +1176,7 @@ static enum type_match_result check_matching_type(struct type_state *state,
 
 		/* Get the size of the actual type */
 		if (dwarf_aggregate_size(&sized_type, &size) < 0 ||
-		    (unsigned)dloc->type_offset >= size)
+		    ((unsigned)dloc->type_offset >= size && !die_has_flex_array(&sized_type)))
 			return PERF_TMR_BAD_OFFSET;
 
 		return PERF_TMR_OK;
@@ -1192,7 +1200,7 @@ static enum type_match_result check_matching_type(struct type_state *state,
 
 		/* Get the size of the actual type */
 		if (dwarf_aggregate_size(type_die, &size) < 0 ||
-		    (unsigned)dloc->type_offset >= size)
+		    ((unsigned)dloc->type_offset >= size && !die_has_flex_array(type_die)))
 			return PERF_TMR_BAD_OFFSET;
 
 		return PERF_TMR_OK;
@@ -1211,7 +1219,7 @@ static enum type_match_result check_matching_type(struct type_state *state,
 
 		/* Get the size of the actual type */
 		if (dwarf_aggregate_size(type_die, &size) < 0 ||
-		    (unsigned)dloc->type_offset >= size)
+		    ((unsigned)dloc->type_offset >= size && !die_has_flex_array(type_die)))
 			return PERF_TMR_BAIL_OUT;
 
 		return PERF_TMR_OK;
@@ -1839,7 +1847,7 @@ int annotated_data_type__update_samples(struct annotated_data_type *adt,
 			return -1;
 	}
 
-	if (offset < 0 || offset >= adt->self.size)
+	if (offset < 0 || (offset >= adt->self.size && !adt->flex_array))
 		return -1;
 
 	h = &adt->histograms[evsel->core.idx];
diff --git a/tools/perf/util/annotate-data.h b/tools/perf/util/annotate-data.h
index ca2096a9ee62cbfe..27b7148b64f60350 100644
--- a/tools/perf/util/annotate-data.h
+++ b/tools/perf/util/annotate-data.h
@@ -85,6 +85,7 @@ struct type_hist {
  * struct annotated_data_type - Data type to profile
  * @node: RB-tree node for dso->type_tree
  * @self: Actual type information
+ * @flex_array: Whethere it has a flex array
  * @nr_histogram: Number of histogram entries
  * @histograms: An array of histograms
  *
@@ -93,6 +94,7 @@ struct type_hist {
 struct annotated_data_type {
 	struct rb_node node;
 	struct annotated_member self;
+	bool flex_array;
 	int nr_histograms;
 	struct type_hist *histograms;
 };
-- 
2.55.0.1032.g73a4cd73de-goog

[PATCH 4/4] perf annotate-data: Adjust type offset for flex-array

[Namhyung Kim]

The flex array members are located beyond the original type size.  Also
it needs to adjust the offset in an array to find a corresponding
element using module operation.  Note that we focus on access to type and
field, so array index is not important.

Make sure to find a field name for flex arrays.

Signed-off-by: Namhyung Kim <namhyung@kernel.org>
---
 tools/perf/util/annotate-data.c | 73 ++++++++++++++++++++++++++++++---
 1 file changed, 67 insertions(+), 6 deletions(-)

diff --git a/tools/perf/util/annotate-data.c b/tools/perf/util/annotate-data.c
index ad043403ced58d98..0789a8cbea7c0355 100644
--- a/tools/perf/util/annotate-data.c
+++ b/tools/perf/util/annotate-data.c
@@ -332,19 +332,40 @@ static void delete_members(struct annotated_member *member)
 }
 
 static int fill_member_name(char *buf, size_t sz, struct annotated_member *m,
-			    int offset, bool first)
+			    int offset, bool first, bool has_flex_array)
 {
 	struct annotated_member *child;
+	bool found = false;
+	int len;
 
 	if (list_empty(&m->children))
 		return 0;
 
 	list_for_each_entry(child, &m->children, node) {
-		int len;
-
 		if (offset < child->offset || offset >= child->offset + child->size)
 			continue;
 
+		found = true;
+		break;
+	}
+
+	if (!found && has_flex_array) {
+		/*
+		 * It may have an intermediate struct that has another struct that
+		 * contains a flex array.  In that case, the outer struct itself is
+		 * has no array and the size is less than the offset so the above
+		 * logic won't find the outer struct at the offset.  Let's use the
+		 * last struct if it couldn't find a member for the flex array.
+		 */
+		child = list_last_entry(&m->children, struct annotated_member, node);
+
+		if (!strstr(child->type_name, "struct "))
+			return 0;
+
+		found = true;
+	}
+
+	if (found) {
 		/* It can have anonymous struct/union members */
 		if (child->var_name) {
 			len = scnprintf(buf, sz, "%s%s",
@@ -354,15 +375,37 @@ static int fill_member_name(char *buf, size_t sz, struct annotated_member *m,
 			len = 0;
 		}
 
-		return fill_member_name(buf + len, sz - len, child, offset, first) + len;
+		return fill_member_name(buf + len, sz - len, child, offset, first,
+					has_flex_array) + len;
 	}
+
 	return 0;
 }
 
 int annotated_data_type__get_member_name(struct annotated_data_type *adt,
 					 char *buf, size_t sz, int member_offset)
 {
-	return fill_member_name(buf, sz, &adt->self, member_offset, /*first=*/true);
+	return fill_member_name(buf, sz, &adt->self, member_offset, /*first=*/true,
+				adt->flex_array);
+}
+
+static struct annotated_member *find_flex_array(struct annotated_member *m, int offset)
+{
+	struct annotated_member *child;
+
+	if (list_empty(&m->children))
+		return NULL;
+
+	child = list_last_entry(&m->children, struct annotated_member, node);
+	if (offset == child->offset && strstr(child->type_name, "[]"))
+		return child;
+
+	return find_flex_array(child, offset);
+}
+
+static struct annotated_member *get_flex_array_member(struct annotated_data_type *adt)
+{
+	return find_flex_array(&adt->self, adt->self.size);
 }
 
 static struct annotated_data_type *dso__findnew_data_type(struct dso *dso,
@@ -1743,6 +1786,7 @@ struct annotated_data_type *find_data_type(struct data_loc_info *dloc)
 {
 	struct dso *dso = map__dso(dloc->ms->map);
 	Dwarf_Die type_die;
+	struct annotated_data_type *result;
 
 	/*
 	 * The type offset is the same as instruction offset by default.
@@ -1755,7 +1799,24 @@ struct annotated_data_type *find_data_type(struct data_loc_info *dloc)
 	if (find_data_type_die(dloc, &type_die) < 0)
 		return NULL;
 
-	return dso__findnew_data_type(dso, &type_die);
+	result = dso__findnew_data_type(dso, &type_die);
+	if (result == NULL)
+		return NULL;
+
+	if (result->flex_array && dloc->type_offset > result->self.size) {
+		struct annotated_member *flex_array = get_flex_array_member(result);
+		if (flex_array) {
+			int offset = dloc->type_offset;
+
+			/* adjust offset in the flex array */
+			offset -= result->self.size;
+			offset %= flex_array->size;
+			offset += result->self.size;
+
+			dloc->type_offset = offset;
+		}
+	}
+	return result;
 }
 
 static size_t data_type_hash(long key, void *ctx __maybe_unused)
-- 
2.55.0.1032.g73a4cd73de-goog