[RFC PATCH v9 47/50] perf tools: Use same BPF program if arguments are identical

[Wang Nan <wangnan0@huawei.com>]

This patch allows creating only one BPF program for different tevs
in one pev, if their prologue are identical.

This is done by comparing argument list of different tev, and maps type
of prologue and tev using a mapping array. This patch use qsort to sort
tevs prior type mapping for performance.

Signed-off-by: Wang Nan <wangnan0@hauwei.com>
---
 tools/perf/util/bpf-loader.c | 132 ++++++++++++++++++++++++++++++++++++++++---
 1 file changed, 125 insertions(+), 7 deletions(-)

diff --git a/tools/perf/util/bpf-loader.c b/tools/perf/util/bpf-loader.c
index 24a55b9..aab936b 100644
--- a/tools/perf/util/bpf-loader.c
+++ b/tools/perf/util/bpf-loader.c
@@ -57,6 +57,8 @@ struct bpf_prog_priv {
 	struct perf_probe_event *pev;
 	bool need_prologue;
 	struct bpf_insn *insns_buf;
+	int nr_types;
+	int *type_mapping;
 };
 
 static void
@@ -68,6 +70,7 @@ bpf_prog_priv__clear(struct bpf_program *prog __maybe_unused,
 	if (priv->pev)
 		clear_perf_probe_event(priv->pev);
 	zfree(&priv->insns_buf);
+	zfree(&priv->type_mapping);
 	free(priv);
 }
 
@@ -238,7 +241,7 @@ preproc_gen_prologue(struct bpf_program *prog, int n,
 	struct bpf_prog_priv *priv;
 	struct bpf_insn *buf;
 	size_t prologue_cnt = 0;
-	int err;
+	int i, err;
 
 	err = bpf_program__get_private(prog, (void **)&priv);
 	if (err || !priv)
@@ -246,11 +249,20 @@ preproc_gen_prologue(struct bpf_program *prog, int n,
 
 	pev = priv->pev;
 
-	if (n < 0 || n >= pev->ntevs)
+	if (n < 0 || n >= priv->nr_types)
 		goto errout;
 
-	tev = &pev->tevs[n];
+	/* Find a tev belong to that type */
+	for (i = 0; i < pev->ntevs; i++)
+		if (priv->type_mapping[i] == n)
+			break;
+
+	if (i >= pev->ntevs) {
+		pr_err("Internal error: prologue type %d not found\n", n);
+		return -EEXIST;
+	}
 
+	tev = &pev->tevs[i];
 	buf = priv->insns_buf;
 	err = bpf__gen_prologue(tev->args, tev->nargs,
 				buf, &prologue_cnt,
@@ -280,6 +292,98 @@ errout:
 	return -EINVAL;
 }
 
+/*
+ * compare_tev_args is reflexive, transitive and antisymmetric.
+ * I can show that but this margin is too narrow to contain.
+ */
+static int compare_tev_args(const void *ptev1, const void *ptev2)
+{
+	int i, ret;
+	const struct probe_trace_event *tev1 =
+		*(const struct probe_trace_event **)ptev1;
+	const struct probe_trace_event *tev2 =
+		*(const struct probe_trace_event **)ptev2;
+
+	ret = tev2->nargs - tev1->nargs;
+	if (ret)
+		return ret;
+
+	for (i = 0; i < tev1->nargs; i++) {
+		struct probe_trace_arg *arg1, *arg2;
+		struct probe_trace_arg_ref *ref1, *ref2;
+
+		arg1 = &tev1->args[i];
+		arg2 = &tev2->args[i];
+
+		ret = strcmp(arg1->value, arg2->value);
+		if (ret)
+			return ret;
+
+		ref1 = arg1->ref;
+		ref2 = arg2->ref;
+
+		while (ref1 && ref2) {
+			ret = ref2->offset - ref1->offset;
+			if (ret)
+				return ret;
+
+			ref1 = ref1->next;
+			ref2 = ref2->next;
+		}
+
+		if (ref1 || ref2)
+			return ref2 ? 1 : -1;
+	}
+
+	return 0;
+}
+
+static int map_prologue(struct perf_probe_event *pev, int *mapping,
+			int *nr_types)
+{
+	int i, type = 0;
+	struct {
+		struct probe_trace_event *tev;
+		int idx;
+	} *stevs;
+	size_t array_sz = sizeof(*stevs) * pev->ntevs;
+
+	stevs = malloc(array_sz);
+	if (!stevs) {
+		pr_err("No ehough memory: alloc stevs failed\n");
+		return -ENOMEM;
+	}
+
+	pr_debug("In map_prologue, ntevs=%d\n", pev->ntevs);
+	for (i = 0; i < pev->ntevs; i++) {
+		stevs[i].tev = &pev->tevs[i];
+		stevs[i].idx = i;
+	}
+	qsort(stevs, pev->ntevs, sizeof(*stevs),
+	      compare_tev_args);
+
+	for (i = 0; i < pev->ntevs; i++) {
+		if (i == 0) {
+			mapping[stevs[i].idx] = type;
+			pr_debug("mapping[%d]=%d\n", stevs[i].idx,
+				 type);
+			continue;
+		}
+
+		if (compare_tev_args(stevs + i, stevs + i - 1) == 0)
+			mapping[stevs[i].idx] = type;
+		else
+			mapping[stevs[i].idx] = ++type;
+
+		pr_debug("mapping[%d]=%d\n", stevs[i].idx,
+			 mapping[stevs[i].idx]);
+	}
+	free(stevs);
+	*nr_types = type + 1;
+
+	return 0;
+}
+
 static int hook_load_preprocessor(struct bpf_program *prog)
 {
 	struct perf_probe_event *pev;
@@ -320,7 +424,19 @@ static int hook_load_preprocessor(struct bpf_program *prog)
 		return -ENOMEM;
 	}
 
-	err = bpf_program__set_prep(prog, pev->ntevs,
+	priv->type_mapping = malloc(sizeof(int) * pev->ntevs);
+	if (!priv->type_mapping) {
+		pr_err("No enough memory: alloc type_mapping failed\n");
+		return -ENOMEM;
+	}
+	memset(priv->type_mapping, 0xff,
+	       sizeof(int) * pev->ntevs);
+
+	err = map_prologue(pev, priv->type_mapping, &priv->nr_types);
+	if (err)
+		return err;
+
+	err = bpf_program__set_prep(prog, priv->nr_types,
 				    preproc_gen_prologue);
 	return err;
 }
@@ -415,11 +531,13 @@ int bpf__foreach_tev(bpf_prog_iter_callback_t func, void *arg)
 			for (i = 0; i < pev->ntevs; i++) {
 				tev = &pev->tevs[i];
 
-				if (priv->need_prologue)
+				if (priv->need_prologue) {
+					int type = priv->type_mapping[i];
+
 					err = bpf_program__get_nth_fd(prog,
-								      i,
+								      type,
 								      &fd);
-				else
+				} else
 					err = bpf_program__get_fd(prog, &fd);
 
 				if (err || fd < 0) {
-- 
1.8.3.4