Netdev Archive on lore.kernel.org
help / color / mirror / Atom feed
From: Andrii Nakryiko <andriin@fb.com>
To: <bpf@vger.kernel.org>, <netdev@vger.kernel.org>, <ast@fb.com>,
	<daniel@iogearbox.net>
Cc: <andrii.nakryiko@gmail.com>, <kernel-team@fb.com>,
	Andrii Nakryiko <andriin@fb.com>
Subject: [PATCH v2 bpf-next 03/14] libbpf: support CO-RE relocations for multi-prog sections
Date: Mon, 31 Aug 2020 18:49:52 -0700	[thread overview]
Message-ID: <20200901015003.2871861-4-andriin@fb.com> (raw)
In-Reply-To: <20200901015003.2871861-1-andriin@fb.com>

Fix up CO-RE relocation code to handle relocations against ELF sections
containing multiple BPF programs. This requires lookup of a BPF program by its
section name and instruction index it contains. While it could have been done
as a simple loop, it could run into performance issues pretty quickly, as
number of CO-RE relocations can be quite large in real-world applications, and
each CO-RE relocation incurs BPF program look up now. So instead of simple
loop, implement a binary search by section name + insn offset.

Signed-off-by: Andrii Nakryiko <andriin@fb.com>
---
 tools/lib/bpf/libbpf.c | 82 +++++++++++++++++++++++++++++++++++++-----
 1 file changed, 74 insertions(+), 8 deletions(-)

diff --git a/tools/lib/bpf/libbpf.c b/tools/lib/bpf/libbpf.c
index 57f87eee5be5..11ad230ec20c 100644
--- a/tools/lib/bpf/libbpf.c
+++ b/tools/lib/bpf/libbpf.c
@@ -2753,6 +2753,18 @@ static bool ignore_elf_section(GElf_Shdr *hdr, const char *name)
 	return false;
 }
 
+static int cmp_progs(const void *_a, const void *_b)
+{
+	const struct bpf_program *a = _a;
+	const struct bpf_program *b = _b;
+
+	if (a->sec_idx != b->sec_idx)
+		return a->sec_idx < b->sec_idx ? -1 : 1;
+
+	/* sec_insn_off can't be the same within the section */
+	return a->sec_insn_off < b->sec_insn_off ? -1 : 1;
+}
+
 static int bpf_object__elf_collect(struct bpf_object *obj)
 {
 	Elf *elf = obj->efile.elf;
@@ -2887,6 +2899,11 @@ static int bpf_object__elf_collect(struct bpf_object *obj)
 		pr_warn("elf: symbol strings section missing or invalid in %s\n", obj->path);
 		return -LIBBPF_ERRNO__FORMAT;
 	}
+
+	/* sort BPF programs by section name and in-section instruction offset
+	 * for faster search */
+	qsort(obj->programs, obj->nr_programs, sizeof(*obj->programs), cmp_progs);
+
 	return bpf_object__init_btf(obj, btf_data, btf_ext_data);
 }
 
@@ -3415,6 +3432,37 @@ static int bpf_program__record_reloc(struct bpf_program *prog,
 	return 0;
 }
 
+static bool prog_contains_insn(const struct bpf_program *prog, size_t insn_idx)
+{
+	return insn_idx >= prog->sec_insn_off &&
+	       insn_idx < prog->sec_insn_off + prog->sec_insn_cnt;
+}
+
+static struct bpf_program *find_prog_by_sec_insn(const struct bpf_object *obj,
+						 size_t sec_idx, size_t insn_idx)
+{
+	int l = 0, r = obj->nr_programs - 1, m;
+	struct bpf_program *prog;
+
+	while (l < r) {
+		m = l + (r - l + 1) / 2;
+		prog = &obj->programs[m];
+
+		if (prog->sec_idx < sec_idx ||
+		    (prog->sec_idx == sec_idx && prog->sec_insn_off <= insn_idx))
+			l = m;
+		else
+			r = m - 1;
+	}
+	/* matching program could be at index l, but it still might be the
+	 * wrong one, so we need to double check conditions for the last time
+	 */
+	prog = &obj->programs[l];
+	if (prog->sec_idx == sec_idx && prog_contains_insn(prog, insn_idx))
+		return prog;
+	return NULL;
+}
+
 static int
 bpf_program__collect_reloc(struct bpf_program *prog, GElf_Shdr *shdr,
 			   Elf_Data *data, struct bpf_object *obj)
@@ -5229,6 +5277,11 @@ static int bpf_core_patch_insn(struct bpf_program *prog,
 	if (relo->insn_off % BPF_INSN_SZ)
 		return -EINVAL;
 	insn_idx = relo->insn_off / BPF_INSN_SZ;
+	/* adjust insn_idx from section frame of reference to the local
+	 * program's frame of reference; (sub-)program code is not yet
+	 * relocated, so it's enough to just subtract in-section offset
+	 */
+	insn_idx = insn_idx - prog->sec_insn_off;
 	insn = &prog->insns[insn_idx];
 	class = BPF_CLASS(insn->code);
 
@@ -5619,7 +5672,7 @@ bpf_object__relocate_core(struct bpf_object *obj, const char *targ_btf_path)
 	struct bpf_program *prog;
 	struct btf *targ_btf;
 	const char *sec_name;
-	int i, err = 0;
+	int i, err = 0, insn_idx, sec_idx;
 
 	if (obj->btf_ext->core_relo_info.len == 0)
 		return 0;
@@ -5646,24 +5699,37 @@ bpf_object__relocate_core(struct bpf_object *obj, const char *targ_btf_path)
 			err = -EINVAL;
 			goto out;
 		}
+		/* bpf_object's ELF is gone by now so it's not easy to find
+		 * section index by section name, but we can find *any*
+		 * bpf_program within desired section name and use it's
+		 * prog->sec_idx to do a proper search by section index and
+		 * instruction offset
+		 */
 		prog = NULL;
 		for (i = 0; i < obj->nr_programs; i++) {
-			if (!strcmp(obj->programs[i].section_name, sec_name)) {
-				prog = &obj->programs[i];
+			prog = &obj->programs[i];
+			if (strcmp(prog->section_name, sec_name) == 0)
 				break;
-			}
 		}
 		if (!prog) {
-			pr_warn("failed to find program '%s' for CO-RE offset relocation\n",
-				sec_name);
-			err = -EINVAL;
-			goto out;
+			pr_warn("sec '%s': failed to find a BPF program\n", sec_name);
+			return -ENOENT;
 		}
+		sec_idx = prog->sec_idx;
 
 		pr_debug("sec '%s': found %d CO-RE relocations\n",
 			 sec_name, sec->num_info);
 
 		for_each_btf_ext_rec(seg, sec, i, rec) {
+			insn_idx = rec->insn_off / BPF_INSN_SZ;
+			prog = find_prog_by_sec_insn(obj, sec_idx, insn_idx);
+			if (!prog) {
+				pr_warn("sec '%s': failed to find program at insn #%d for CO-RE offset relocation #%d\n",
+					sec_name, insn_idx, i);
+				err = -EINVAL;
+				goto out;
+			}
+
 			err = bpf_core_apply_relo(prog, rec, i, obj->btf,
 						  targ_btf, cand_cache);
 			if (err) {
-- 
2.24.1


  parent reply	other threads:[~2020-09-01  1:50 UTC|newest]

Thread overview: 26+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2020-09-01  1:49 [PATCH v2 bpf-next 00/14] Add libbpf full support for BPF-to-BPF calls Andrii Nakryiko
2020-09-01  1:49 ` [PATCH v2 bpf-next 01/14] libbpf: ensure ELF symbols table is found before further ELF processing Andrii Nakryiko
2020-09-02  5:43   ` John Fastabend
2020-09-01  1:49 ` [PATCH v2 bpf-next 02/14] libbpf: parse multi-function sections into multiple BPF programs Andrii Nakryiko
2020-09-02  6:08   ` John Fastabend
2020-09-01  1:49 ` Andrii Nakryiko [this message]
2020-09-02  6:14   ` [PATCH v2 bpf-next 03/14] libbpf: support CO-RE relocations for multi-prog sections John Fastabend
2020-09-01  1:49 ` [PATCH v2 bpf-next 04/14] libbpf: make RELO_CALL work for multi-prog sections and sub-program calls Andrii Nakryiko
2020-09-02  5:36   ` Alexei Starovoitov
2020-09-02 19:52     ` Andrii Nakryiko
2020-09-01  1:49 ` [PATCH v2 bpf-next 05/14] libbpf: implement generalized .BTF.ext func/line info adjustment Andrii Nakryiko
2020-09-01  1:49 ` [PATCH v2 bpf-next 06/14] libbpf: add multi-prog section support for struct_ops Andrii Nakryiko
2020-09-01  1:49 ` [PATCH v2 bpf-next 07/14] selftests/bpf: add selftest for multi-prog sections and bpf-to-bpf calls Andrii Nakryiko
2020-09-02  5:41   ` Alexei Starovoitov
2020-09-02 19:57     ` Andrii Nakryiko
2020-09-01  1:49 ` [PATCH v2 bpf-next 08/14] tools/bpftool: replace bpf_program__title() with bpf_program__section_name() Andrii Nakryiko
2020-09-01  1:49 ` [PATCH v2 bpf-next 09/14] selftests/bpf: don't use deprecated libbpf APIs Andrii Nakryiko
2020-09-01  1:49 ` [PATCH v2 bpf-next 10/14] libbpf: deprecate notion of BPF program "title" in favor of "section name" Andrii Nakryiko
2020-09-01  1:50 ` [PATCH v2 bpf-next 11/14] selftests/bpf: turn fexit_bpf2bpf into test with subtests Andrii Nakryiko
2020-09-01  1:50 ` [PATCH v2 bpf-next 12/14] selftests/bpf: convert pyperf, strobemeta, and l4lb_noinline to __noinline Andrii Nakryiko
2020-09-02  5:45   ` Alexei Starovoitov
2020-09-02 19:58     ` Andrii Nakryiko
2020-09-01  1:50 ` [PATCH v2 bpf-next 13/14] selftests/bpf: modernize xdp_noinline test w/ skeleton and __noinline Andrii Nakryiko
2020-09-01  1:50 ` [PATCH v2 bpf-next 14/14] selftests/bpf: convert cls_redirect selftest to use __noinline Andrii Nakryiko
2020-09-02  5:46   ` Alexei Starovoitov
2020-09-02 19:58     ` Andrii Nakryiko

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=20200901015003.2871861-4-andriin@fb.com \
    --to=andriin@fb.com \
    --cc=andrii.nakryiko@gmail.com \
    --cc=ast@fb.com \
    --cc=bpf@vger.kernel.org \
    --cc=daniel@iogearbox.net \
    --cc=kernel-team@fb.com \
    --cc=netdev@vger.kernel.org \
    --subject='Re: [PATCH v2 bpf-next 03/14] libbpf: support CO-RE relocations for multi-prog sections' \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).