From: Alexei Starovoitov <ast@plumgrid.com>
To: "David S. Miller" <davem@davemloft.net>
Cc: Ingo Molnar <mingo@kernel.org>,
Linus Torvalds <torvalds@linux-foundation.org>,
Andy Lutomirski <luto@amacapital.net>,
Steven Rostedt <rostedt@goodmis.org>,
Daniel Borkmann <dborkman@redhat.com>,
Chema Gonzalez <chema@google.com>,
Eric Dumazet <edumazet@google.com>,
Peter Zijlstra <a.p.zijlstra@chello.nl>,
Brendan Gregg <brendan.d.gregg@gmail.com>,
Namhyung Kim <namhyung@kernel.org>,
"H. Peter Anvin" <hpa@zytor.com>,
Andrew Morton <akpm@linux-foundation.org>,
Kees Cook <keescook@chromium.org>,
linux-api@vger.kernel.org, netdev@vger.kernel.org,
linux-kernel@vger.kernel.org
Subject: [PATCH v5 net-next 12/29] bpf: handle pseudo BPF_LD_IMM64 insn
Date: Sun, 24 Aug 2014 13:21:13 -0700 [thread overview]
Message-ID: <1408911690-7598-13-git-send-email-ast@plumgrid.com> (raw)
In-Reply-To: <1408911690-7598-1-git-send-email-ast@plumgrid.com>
eBPF programs passed from userspace are using pseudo BPF_LD_IMM64 instructions
to refer to process-local map_fd. Scan the program for such instructions and
if FDs are valid, convert them to 'struct bpf_map' pointers which will be used
by verifier to check access to maps in bpf_map_lookup/update() calls.
If program passes verifier, convert pseudo BPF_LD_IMM64 into generic by dropping
BPF_PSEUDO_MAP_FD flag.
Note that eBPF interpreter is generic and knows nothing about pseudo insns.
Signed-off-by: Alexei Starovoitov <ast@plumgrid.com>
---
include/uapi/linux/bpf.h | 6 ++
kernel/bpf/verifier.c | 147 ++++++++++++++++++++++++++++++++++++++++++++++
2 files changed, 153 insertions(+)
diff --git a/include/uapi/linux/bpf.h b/include/uapi/linux/bpf.h
index d280acad4b28..2f4d92df4fbe 100644
--- a/include/uapi/linux/bpf.h
+++ b/include/uapi/linux/bpf.h
@@ -176,6 +176,12 @@ enum {
.off = 0, \
.imm = ((__u64) (IMM)) >> 32 })
+#define BPF_PSEUDO_MAP_FD 1
+
+/* pseudo BPF_LD_IMM64 insn used to refer to process-local map_fd */
+#define BPF_LD_MAP_FD(DST, MAP_FD) \
+ BPF_LD_IMM64_RAW(DST, BPF_PSEUDO_MAP_FD, MAP_FD)
+
/* Short form of mov based on type, BPF_X: dst_reg = src_reg, BPF_K: dst_reg = imm32 */
#define BPF_MOV64_RAW(TYPE, DST, SRC, IMM) \
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 2484a3387ca2..28ce2cfa49db 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -144,10 +144,15 @@
* load/store to bpf_context are checked against known fields
*/
+#define MAX_USED_MAPS 64 /* max number of maps accessed by one eBPF program */
+
/* single container for all structs
* one verifier_env per bpf_check() call
*/
struct verifier_env {
+ struct bpf_prog *prog; /* eBPF program being verified */
+ struct bpf_map *used_maps[MAX_USED_MAPS]; /* array of map's used by eBPF program */
+ u32 used_map_cnt; /* number of used maps */
};
/* verbose verifier prints what it's seeing
@@ -319,6 +324,115 @@ static void print_bpf_insn(struct bpf_insn *insn)
}
}
+/* return the map pointer stored inside BPF_LD_IMM64 instruction */
+static struct bpf_map *ld_imm64_to_map_ptr(struct bpf_insn *insn)
+{
+ u64 imm64 = ((u64) (u32) insn[0].imm) | ((u64) (u32) insn[1].imm) << 32;
+
+ return (struct bpf_map *) (unsigned long) imm64;
+}
+
+/* look for pseudo eBPF instructions that access map FDs and
+ * replace them with actual map pointers
+ */
+static int replace_map_fd_with_map_ptr(struct verifier_env *env)
+{
+ struct bpf_insn *insn = env->prog->insnsi;
+ int insn_cnt = env->prog->len;
+ int i, j;
+
+ for (i = 0; i < insn_cnt; i++, insn++) {
+ if (insn[0].code == (BPF_LD | BPF_IMM | BPF_DW)) {
+ struct bpf_map *map;
+ struct fd f;
+
+ if (i == insn_cnt - 1 || insn[1].code != 0 ||
+ insn[1].dst_reg != 0 || insn[1].src_reg != 0 ||
+ insn[1].off != 0) {
+ verbose("invalid bpf_ld_imm64 insn\n");
+ return -EINVAL;
+ }
+
+ if (insn->src_reg == 0)
+ /* valid generic load 64-bit imm */
+ goto next_insn;
+
+ if (insn->src_reg != BPF_PSEUDO_MAP_FD) {
+ verbose("unrecognized bpf_ld_imm64 insn\n");
+ return -EINVAL;
+ }
+
+ f = fdget(insn->imm);
+
+ map = bpf_map_get(f);
+ if (IS_ERR(map)) {
+ verbose("fd %d is not pointing to valid bpf_map\n",
+ insn->imm);
+ fdput(f);
+ return PTR_ERR(map);
+ }
+
+ /* store map pointer inside BPF_LD_IMM64 instruction */
+ insn[0].imm = (u32) (unsigned long) map;
+ insn[1].imm = ((u64) (unsigned long) map) >> 32;
+
+ /* check whether we recorded this map already */
+ for (j = 0; j < env->used_map_cnt; j++)
+ if (env->used_maps[j] == map) {
+ fdput(f);
+ goto next_insn;
+ }
+
+ if (env->used_map_cnt >= MAX_USED_MAPS) {
+ fdput(f);
+ return -E2BIG;
+ }
+
+ /* remember this map */
+ env->used_maps[env->used_map_cnt++] = map;
+
+ /* hold the map. If the program is rejected by verifier,
+ * the map will be released by release_maps() or it
+ * will be used by the valid program until it's unloaded
+ * and all maps are released in free_bpf_prog_info()
+ */
+ atomic_inc(&map->refcnt);
+
+ fdput(f);
+next_insn:
+ insn++;
+ i++;
+ }
+ }
+
+ /* now all pseudo BPF_LD_IMM64 instructions load valid
+ * 'struct bpf_map *' into a register instead of user map_fd.
+ * These pointers will be used later by verifier to validate map access.
+ */
+ return 0;
+}
+
+/* drop refcnt of maps used by the rejected program */
+static void release_maps(struct verifier_env *env)
+{
+ int i;
+
+ for (i = 0; i < env->used_map_cnt; i++)
+ bpf_map_put(env->used_maps[i]);
+}
+
+/* convert pseudo BPF_LD_IMM64 into generic BPF_LD_IMM64 */
+static void convert_pseudo_ld_imm64(struct verifier_env *env)
+{
+ struct bpf_insn *insn = env->prog->insnsi;
+ int insn_cnt = env->prog->len;
+ int i;
+
+ for (i = 0; i < insn_cnt; i++, insn++)
+ if (insn->code == (BPF_LD | BPF_IMM | BPF_DW))
+ insn->src_reg = 0;
+}
+
int bpf_check(struct bpf_prog *prog, struct nlattr *tb[BPF_PROG_ATTR_MAX + 1])
{
void __user *log_ubuf = NULL;
@@ -335,6 +449,8 @@ int bpf_check(struct bpf_prog *prog, struct nlattr *tb[BPF_PROG_ATTR_MAX + 1])
if (!env)
return -ENOMEM;
+ env->prog = prog;
+
/* grab the mutex to protect few globals used by verifier */
mutex_lock(&bpf_verifier_lock);
@@ -362,8 +478,14 @@ int bpf_check(struct bpf_prog *prog, struct nlattr *tb[BPF_PROG_ATTR_MAX + 1])
log_level = 0;
}
+ ret = replace_map_fd_with_map_ptr(env);
+ if (ret < 0)
+ goto skip_full_check;
+
/* ret = do_check(env); */
+skip_full_check:
+
if (log_level && log_len >= log_size - 1) {
BUG_ON(log_len >= log_size);
/* verifier log exceeded user supplied buffer */
@@ -377,11 +499,36 @@ int bpf_check(struct bpf_prog *prog, struct nlattr *tb[BPF_PROG_ATTR_MAX + 1])
goto free_log_buf;
}
+ if (ret == 0 && env->used_map_cnt) {
+ /* if program passed verifier, update used_maps in bpf_prog_info */
+ prog->info->used_maps = kmalloc_array(env->used_map_cnt,
+ sizeof(env->used_maps[0]),
+ GFP_KERNEL);
+
+ if (!prog->info->used_maps) {
+ ret = -ENOMEM;
+ goto free_log_buf;
+ }
+
+ memcpy(prog->info->used_maps, env->used_maps,
+ sizeof(env->used_maps[0]) * env->used_map_cnt);
+ prog->info->used_map_cnt = env->used_map_cnt;
+
+ /* program is valid. Convert pseudo bpf_ld_imm64 into generic
+ * bpf_ld_imm64 instructions
+ */
+ convert_pseudo_ld_imm64(env);
+ }
free_log_buf:
if (log_level)
vfree(log_buf);
free_env:
+ if (!prog->info->used_maps)
+ /* if we didn't copy map pointers into bpf_prog_info, release
+ * them now. Otherwise free_bpf_prog_info() will release them.
+ */
+ release_maps(env);
kfree(env);
mutex_unlock(&bpf_verifier_lock);
return ret;
--
1.7.9.5
next prev parent reply other threads:[~2014-08-24 20:29 UTC|newest]
Thread overview: 33+ messages / expand[flat|nested] mbox.gz Atom feed top
2014-08-24 20:21 [PATCH v5 net-next 00/29] BPF syscall, maps, verifier, samples, llvm Alexei Starovoitov
2014-08-24 20:21 ` [PATCH v5 net-next 01/29] bpf: x86: add missing 'shift by register' instructions to x64 eBPF JIT Alexei Starovoitov
2014-08-24 20:21 ` [PATCH v5 net-next 02/29] net: filter: add "load 64-bit immediate" eBPF instruction Alexei Starovoitov
2014-08-24 20:21 ` [PATCH v5 net-next 03/29] net: filter: split filter.h and expose eBPF to user space Alexei Starovoitov
2014-08-24 20:21 ` [PATCH v5 net-next 04/29] bpf: introduce syscall(BPF, ...) and BPF maps Alexei Starovoitov
2014-08-24 20:21 ` [PATCH v5 net-next 05/29] bpf: enable bpf syscall on x64 and i386 Alexei Starovoitov
2014-08-24 20:21 ` [PATCH v5 net-next 06/29] bpf: add lookup/update/delete/iterate methods to BPF maps Alexei Starovoitov
2014-08-25 21:33 ` Cong Wang
2014-08-25 22:07 ` Alexei Starovoitov
2014-08-24 20:21 ` [PATCH v5 net-next 07/29] bpf: add hashtable type of " Alexei Starovoitov
2014-08-24 20:21 ` [PATCH v5 net-next 08/29] bpf: expand BPF syscall with program load/unload Alexei Starovoitov
2014-08-24 20:21 ` [PATCH v5 net-next 09/29] bpf: handle pseudo BPF_CALL insn Alexei Starovoitov
2014-08-24 20:21 ` [PATCH v5 net-next 10/29] bpf: verifier (add docs) Alexei Starovoitov
2014-08-24 20:21 ` [PATCH v5 net-next 11/29] bpf: verifier (add ability to receive verification log) Alexei Starovoitov
2014-08-24 20:21 ` Alexei Starovoitov [this message]
2014-08-24 20:21 ` [PATCH v5 net-next 13/29] bpf: verifier (add branch/goto checks) Alexei Starovoitov
2014-08-24 20:21 ` [PATCH v5 net-next 14/29] bpf: verifier (add verifier core) Alexei Starovoitov
2014-08-24 20:21 ` [PATCH v5 net-next 15/29] bpf: verifier (add state prunning optimization) Alexei Starovoitov
2014-08-24 20:21 ` [PATCH v5 net-next 16/29] bpf: allow eBPF programs to use maps Alexei Starovoitov
2014-08-24 20:21 ` [PATCH v5 net-next 17/29] bpf: split eBPF out of NET Alexei Starovoitov
2014-08-24 20:21 ` [PATCH v5 net-next 18/29] tracing: allow eBPF programs to be attached to events Alexei Starovoitov
2014-08-24 20:21 ` [PATCH v5 net-next 19/29] tracing: allow eBPF programs call printk() Alexei Starovoitov
2014-08-24 20:21 ` [PATCH v5 net-next 20/29] tracing: allow eBPF programs to be attached to kprobe/kretprobe Alexei Starovoitov
2014-08-24 20:21 ` [PATCH v5 net-next 21/29] tracing: allow eBPF programs to call ktime_get_ns() and get_current() Alexei Starovoitov
2014-08-24 20:21 ` [PATCH v5 net-next 22/29] samples: bpf: add mini eBPF library to manipulate maps and programs Alexei Starovoitov
2014-08-24 20:21 ` [PATCH v5 net-next 23/29] samples: bpf: example of tracing filters with eBPF Alexei Starovoitov
2014-08-24 20:21 ` [PATCH v5 net-next 24/29] bpf: verifier test Alexei Starovoitov
2014-08-24 20:21 ` [PATCH v5 net-next 25/29] bpf: llvm backend Alexei Starovoitov
2014-08-24 20:21 ` [PATCH v5 net-next 26/29] samples: bpf: elf file loader Alexei Starovoitov
2014-08-24 20:21 ` [PATCH v5 net-next 27/29] samples: bpf: eBPF example in C Alexei Starovoitov
2014-08-24 20:21 ` [PATCH v5 net-next 28/29] samples: bpf: counting " Alexei Starovoitov
2014-08-24 20:21 ` [PATCH v5 net-next 29/29] samples: bpf: IO latency analysis (iosnoop/heatmap) Alexei Starovoitov
2014-08-25 0:39 ` [PATCH v5 net-next 00/29] BPF syscall, maps, verifier, samples, llvm David Miller
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=1408911690-7598-13-git-send-email-ast@plumgrid.com \
--to=ast@plumgrid.com \
--cc=a.p.zijlstra@chello.nl \
--cc=akpm@linux-foundation.org \
--cc=brendan.d.gregg@gmail.com \
--cc=chema@google.com \
--cc=davem@davemloft.net \
--cc=dborkman@redhat.com \
--cc=edumazet@google.com \
--cc=hpa@zytor.com \
--cc=keescook@chromium.org \
--cc=linux-api@vger.kernel.org \
--cc=linux-kernel@vger.kernel.org \
--cc=luto@amacapital.net \
--cc=mingo@kernel.org \
--cc=namhyung@kernel.org \
--cc=netdev@vger.kernel.org \
--cc=rostedt@goodmis.org \
--cc=torvalds@linux-foundation.org \
/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
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
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).