[PATCH net-next 0/5] Misc BPF improvements

Daniel Borkmann

author maintainer

2017-01-24 00:06 UTC #0 lore raw

cover Misc BPF improvements

This series adds various misc improvements to BPF, f.e. allowing skb_load_bytes() helper to be used with filter/reuseport programs to facilitate programming, test cases for program tag, etc. For details, please see individual patches.

Thanks!

Daniel Borkmann (5):
bpf: simplify __is_valid_access test on cb
bpf: enable load bytes helper for filter/reuseport progs
bpf: allow option for setting bpf_l4_csum_replace from scratch
bpf: add prog tag test case to bpf selftests
bpf: enable verifier to better track const alu ops

 include/uapi/linux/bpf.h                    |   1 +
 kernel/bpf/verifier.c                       |  64 ++++++---
 net/core/filter.c                           |  63 ++++-----
 tools/testing/selftests/bpf/Makefile        |   4 +-
 tools/testing/selftests/bpf/test_tag.c      | 202 ++++++++++++++++++++++++++++
 tools/testing/selftests/bpf/test_verifier.c |  82 +++++++++++
 6 files changed, 364 insertions(+), 52 deletions(-)
 create mode 100644 tools/testing/selftests/bpf/test_tag.c

Signature · 1 line

1.9.3

Daniel Borkmann

author maintainer

2017-01-24 00:06 UTC #1 lore raw

PATCH 1/5 bpf: simplify __is_valid_access test on cb

The __is_valid_access() test for cb[] from 62c7989b24db ("bpf: allow b/h/w/dw access for bpf's cb in ctx") was done unnecessarily complex, we can just simplify it the same way as recent fix from 2d071c643f1c ("bpf, trace: make ctx access checks more robust") did. Overflow can never happen as size is 1/2/4/8 depending on access.

Signed-off-by Daniel Borkmann <[email protected]>

Acked-by Alexei Starovoitov <[email protected]>

---
 net/core/filter.c | 15 ++-------------
 1 file changed, 2 insertions(+), 13 deletions(-)

net/core/filter.c +2 ~~-13~~

index 9038386..883975f 100644
@@ -2784,19 +2784,8 @@ static bool __is_valid_access(int off, int size)
 	switch (off) {
 	case offsetof(struct __sk_buff, cb[0]) ...
 	     offsetof(struct __sk_buff, cb[4]) + sizeof(__u32) - 1:
-		if (size == sizeof(__u16) &&
-		    off > offsetof(struct __sk_buff, cb[4]) + sizeof(__u16))
-			return false;
-		if (size == sizeof(__u32) &&
-		    off > offsetof(struct __sk_buff, cb[4]))
-			return false;
-		if (size == sizeof(__u64) &&
-		    off > offsetof(struct __sk_buff, cb[2]))
-			return false;
-		if (size != sizeof(__u8)  &&
-		    size != sizeof(__u16) &&
-		    size != sizeof(__u32) &&
-		    size != sizeof(__u64))
+		if (off + size >
+		    offsetof(struct __sk_buff, cb[4]) + sizeof(__u32))
 			return false;
 		break;
 	default:

Signature · 1 line

1.9.3

Daniel Borkmann

author maintainer

2017-01-24 00:06 UTC #2 lore raw

PATCH 2/5 bpf: enable load bytes helper for filter/reuseport progs

In reply to Daniel Borkmann

BPF_PROG_TYPE_SOCKET_FILTER are used in various facilities such as for SO_REUSEPORT and packet fanout demuxing, packet filtering, kcm, etc, and yet the only facility they can use is BPF_LD with {BPF_ABS, BPF_IND} for single byte/half/word access.

Direct packet access is only restricted to tc programs right now, but we can still facilitate usage by allowing skb_load_bytes() helper added back then in 05c74e5e53f6 ("bpf: add bpf_skb_load_bytes helper") that calls skb_header_pointer() similarly to bpf_load_pointer(), but for stack buffers with larger access size.

Name the previous sk_filter_func_proto() as bpf_base_func_proto() since this is used everywhere else as well, similarly for the ctx converter, that is, bpf_convert_ctx_access().

Signed-off-by Daniel Borkmann <[email protected]>

Acked-by Alexei Starovoitov <[email protected]>

---
 net/core/filter.c | 41 ++++++++++++++++++++++++++---------------
 1 file changed, 26 insertions(+), 15 deletions(-)

net/core/filter.c +26 ~~-15~~

index 883975f..e2263da 100644
@@ -2598,7 +2598,7 @@ static unsigned long bpf_xdp_copy(void *dst_buff, const void *src_buff,
 };
 
 static const struct bpf_func_proto *
-sk_filter_func_proto(enum bpf_func_id func_id)
+bpf_base_func_proto(enum bpf_func_id func_id)
 {
 	switch (func_id) {
 	case BPF_FUNC_map_lookup_elem:

@@ -2626,6 +2626,17 @@ static unsigned long bpf_xdp_copy(void *dst_buff, const void *src_buff,
 }
 
 static const struct bpf_func_proto *
+sk_filter_func_proto(enum bpf_func_id func_id)
+{
+	switch (func_id) {
+	case BPF_FUNC_skb_load_bytes:
+		return &bpf_skb_load_bytes_proto;
+	default:
+		return bpf_base_func_proto(func_id);
+	}
+}
+
+static const struct bpf_func_proto *
 tc_cls_act_func_proto(enum bpf_func_id func_id)
 {
 	switch (func_id) {

@@ -2680,7 +2691,7 @@ static unsigned long bpf_xdp_copy(void *dst_buff, const void *src_buff,
 	case BPF_FUNC_skb_under_cgroup:
 		return &bpf_skb_under_cgroup_proto;
 	default:
-		return sk_filter_func_proto(func_id);
+		return bpf_base_func_proto(func_id);
 	}
 }

@@ -2695,7 +2706,7 @@ static unsigned long bpf_xdp_copy(void *dst_buff, const void *src_buff,
 	case BPF_FUNC_xdp_adjust_head:
 		return &bpf_xdp_adjust_head_proto;
 	default:
-		return sk_filter_func_proto(func_id);
+		return bpf_base_func_proto(func_id);
 	}
 }

@@ -2706,7 +2717,7 @@ static unsigned long bpf_xdp_copy(void *dst_buff, const void *src_buff,
 	case BPF_FUNC_skb_load_bytes:
 		return &bpf_skb_load_bytes_proto;
 	default:
-		return sk_filter_func_proto(func_id);
+		return bpf_base_func_proto(func_id);
 	}
 }

@@ -2733,7 +2744,7 @@ static unsigned long bpf_xdp_copy(void *dst_buff, const void *src_buff,
 	case BPF_FUNC_skb_under_cgroup:
 		return &bpf_skb_under_cgroup_proto;
 	default:
-		return sk_filter_func_proto(func_id);
+		return bpf_base_func_proto(func_id);
 	}
 }

@@ -2983,10 +2994,10 @@ void bpf_warn_invalid_xdp_action(u32 act)
 }
 EXPORT_SYMBOL_GPL(bpf_warn_invalid_xdp_action);
 
-static u32 sk_filter_convert_ctx_access(enum bpf_access_type type,
-					const struct bpf_insn *si,
-					struct bpf_insn *insn_buf,
-					struct bpf_prog *prog)
+static u32 bpf_convert_ctx_access(enum bpf_access_type type,
+				  const struct bpf_insn *si,
+				  struct bpf_insn *insn_buf,
+				  struct bpf_prog *prog)
 {
 	struct bpf_insn *insn = insn_buf;
 	int off;

@@ -3210,7 +3221,7 @@ static u32 tc_cls_act_convert_ctx_access(enum bpf_access_type type,
 				      offsetof(struct net_device, ifindex));
 		break;
 	default:
-		return sk_filter_convert_ctx_access(type, si, insn_buf, prog);
+		return bpf_convert_ctx_access(type, si, insn_buf, prog);
 	}
 
 	return insn - insn_buf;

@@ -3242,7 +3253,7 @@ static u32 xdp_convert_ctx_access(enum bpf_access_type type,
 static const struct bpf_verifier_ops sk_filter_ops = {
 	.get_func_proto		= sk_filter_func_proto,
 	.is_valid_access	= sk_filter_is_valid_access,
-	.convert_ctx_access	= sk_filter_convert_ctx_access,
+	.convert_ctx_access	= bpf_convert_ctx_access,
 };
 
 static const struct bpf_verifier_ops tc_cls_act_ops = {

@@ -3261,24 +3272,24 @@ static u32 xdp_convert_ctx_access(enum bpf_access_type type,
 static const struct bpf_verifier_ops cg_skb_ops = {
 	.get_func_proto		= cg_skb_func_proto,
 	.is_valid_access	= sk_filter_is_valid_access,
-	.convert_ctx_access	= sk_filter_convert_ctx_access,
+	.convert_ctx_access	= bpf_convert_ctx_access,
 };
 
 static const struct bpf_verifier_ops lwt_inout_ops = {
 	.get_func_proto		= lwt_inout_func_proto,
 	.is_valid_access	= lwt_is_valid_access,
-	.convert_ctx_access	= sk_filter_convert_ctx_access,
+	.convert_ctx_access	= bpf_convert_ctx_access,
 };
 
 static const struct bpf_verifier_ops lwt_xmit_ops = {
 	.get_func_proto		= lwt_xmit_func_proto,
 	.is_valid_access	= lwt_is_valid_access,
-	.convert_ctx_access	= sk_filter_convert_ctx_access,
+	.convert_ctx_access	= bpf_convert_ctx_access,
 	.gen_prologue		= tc_cls_act_prologue,
 };
 
 static const struct bpf_verifier_ops cg_sock_ops = {
-	.get_func_proto		= sk_filter_func_proto,
+	.get_func_proto		= bpf_base_func_proto,
 	.is_valid_access	= sock_filter_is_valid_access,
 	.convert_ctx_access	= sock_filter_convert_ctx_access,
 };

Signature · 1 line

1.9.3

Daniel Borkmann

author maintainer

2017-01-24 00:06 UTC #3 lore raw

PATCH 3/5 bpf: allow option for setting bpf_l4_csum_replace from scratch

In reply to Daniel Borkmann

When programs need to calculate the csum from scratch for small UDP packets and use bpf_l4_csum_replace() to feed the result from helpers like bpf_csum_diff(), then we need a flag besides BPF_F_MARK_MANGLED_0 that would ignore the case of current csum being 0, and which would still allow for the helper to set the csum and transform when needed to CSUM_MANGLED_0.

Signed-off-by Daniel Borkmann <[email protected]>

Acked-by Alexei Starovoitov <[email protected]>

---
 include/uapi/linux/bpf.h | 1 +
 net/core/filter.c        | 7 ++++---
 2 files changed, 5 insertions(+), 3 deletions(-)

include/uapi/linux/bpf.h +1 -0

index bd30684..e07fd5a 100644
@@ -522,6 +522,7 @@ enum bpf_func_id {
 /* BPF_FUNC_l4_csum_replace flags. */
 #define BPF_F_PSEUDO_HDR		(1ULL << 4)
 #define BPF_F_MARK_MANGLED_0		(1ULL << 5)
+#define BPF_F_MARK_ENFORCE		(1ULL << 6)
 
 /* BPF_FUNC_clone_redirect and BPF_FUNC_redirect flags. */
 #define BPF_F_INGRESS			(1ULL << 0)

net/core/filter.c +4 -3

index e2263da..1e00737 100644
@@ -1522,10 +1522,11 @@ static inline void bpf_pull_mac_rcsum(struct sk_buff *skb)
 {
 	bool is_pseudo = flags & BPF_F_PSEUDO_HDR;
 	bool is_mmzero = flags & BPF_F_MARK_MANGLED_0;
+	bool do_mforce = flags & BPF_F_MARK_ENFORCE;
 	__sum16 *ptr;
 
-	if (unlikely(flags & ~(BPF_F_MARK_MANGLED_0 | BPF_F_PSEUDO_HDR |
-			       BPF_F_HDR_FIELD_MASK)))
+	if (unlikely(flags & ~(BPF_F_MARK_MANGLED_0 | BPF_F_MARK_ENFORCE |
+			       BPF_F_PSEUDO_HDR | BPF_F_HDR_FIELD_MASK)))
 		return -EINVAL;
 	if (unlikely(offset > 0xffff || offset & 1))
 		return -EFAULT;

@@ -1533,7 +1534,7 @@ static inline void bpf_pull_mac_rcsum(struct sk_buff *skb)
 		return -EFAULT;
 
 	ptr = (__sum16 *)(skb->data + offset);
-	if (is_mmzero && !*ptr)
+	if (is_mmzero && !do_mforce && !*ptr)
 		return 0;
 
 	switch (flags & BPF_F_HDR_FIELD_MASK) {

Signature · 1 line

1.9.3

Daniel Borkmann

author maintainer

2017-01-24 00:06 UTC #4 lore raw

PATCH 4/5 bpf: add prog tag test case to bpf selftests

In reply to Daniel Borkmann

Add the test case used to compare the results from fdinfo with af_alg's output on the tag. Tests are from min to max sized programs, with and without maps included.

  # ./test_tag
  test_tag: OK (40945 tests)

Tested on x86_64 and s390x.

Signed-off-by Daniel Borkmann <[email protected]>

Acked-by Alexei Starovoitov <[email protected]>

---
 tools/testing/selftests/bpf/Makefile   |   4 +-
 tools/testing/selftests/bpf/test_tag.c | 202 +++++++++++++++++++++++++++++++++
 2 files changed, 204 insertions(+), 2 deletions(-)
 create mode 100644 tools/testing/selftests/bpf/test_tag.c

tools/testing/selftests/bpf/Makefile +2 -2

index 064a3e5..769a6cb 100644
@@ -1,8 +1,8 @@
 CFLAGS += -Wall -O2 -I../../../../usr/include
 
-test_objs = test_verifier test_maps test_lru_map test_lpm_map
+test_objs = test_verifier test_tag test_maps test_lru_map test_lpm_map
 
-TEST_PROGS := test_verifier test_maps test_lru_map test_lpm_map test_kmod.sh
+TEST_PROGS := $(test_objs) test_kmod.sh
 TEST_FILES := $(test_objs)
 
 all: $(test_objs)

tools/testing/selftests/bpf/test_tag.c new file +202 -0

202 lines not on this page · raw message

Signature · 1 line

1.9.3

Daniel Borkmann

author maintainer

2017-01-24 00:06 UTC #5 lore raw

PATCH 5/5 bpf: enable verifier to better track const alu ops

In reply to Daniel Borkmann

William reported couple of issues in relation to direct packet access. Typical scheme is to check for data + [off] <= data_end, where [off] can be either immediate or coming from a tracked register that contains an immediate, depending on the branch, we can then access the data. However, in case of calculating [off] for either the mentioned test itself or for access after the test in a more "complex" way, then the verifier will stop tracking the CONST_IMM marked register and will mark it as UNKNOWN_VALUE one.

Adding that UNKNOWN_VALUE typed register to a pkt() marked register, the verifier then bails out in check_packet_ptr_add() as it finds the registers imm value below 48. In the first below example, that is due to evaluate_reg_imm_alu() not handling right shifts and thus marking the register as UNKNOWN_VALUE via helper __mark_reg_unknown_value() that resets imm to 0.

In the second case the same happens at the time when r4 is set to r4 &= r5, where it transitions to UNKNOWN_VALUE from evaluate_reg_imm_alu(). Later on r4 we shift right by 3 inside evaluate_reg_alu(), where the register's imm turns into 3. That is, for registers with type UNKNOWN_VALUE, imm of 0 means that we don't know what value the register has, and for imm > 0 it means that the value has [imm] upper zero bits. F.e. when shifting an UNKNOWN_VALUE register by 3 to the right, no matter what value it had, we know that the 3 upper most bits must be zero now. This is to make sure that ALU operations with unknown registers don't overflow. Meaning, once we know that we have more than 48 upper zero bits, or, in other words cannot go beyond 0xffff offset with ALU ops, such an addition will track the target register as a new pkt() register with a new id, but 0 offset and 0 range, so for that a new data/data_end test will be required. Is the source register a CONST_IMM one that is to be added to the pkt() register, or the source instruction is an add instruction with immediate value, then it will get added if it stays within max 0xffff bounds.

Quoted 1 line

From there, pkt() type, can be accessed should reg->off + imm be

within the access range of pkt().

[...]
from 28 to 30: R0=imm1,min_value=1,max_value=1

    R1=pkt(id=0,off=0,r=22) R2=pkt_end
    R3=imm144,min_value=144,max_value=144
    R4=imm0,min_value=0,max_value=0
    R5=inv48,min_value=2054,max_value=2054 R10=fp

30: (bf) r5 = r3
31: (07) r5 += 23
32: (77) r5 >>= 3
33: (bf) r6 = r1
34: (0f) r6 += r5
cannot add integer value with 0 upper zero bits to ptr_to_packet

[...]
from 52 to 80: R0=imm1,min_value=1,max_value=1

    R1=pkt(id=0,off=0,r=34) R2=pkt_end R3=inv
    R4=imm272 R5=inv56,min_value=17,max_value=17
    R6=pkt(id=0,off=26,r=34) R10=fp

80: (07) r4 += 71
81: (18) r5 = 0xfffffff8
83: (5f) r4 &= r5
84: (77) r4 >>= 3
85: (0f) r1 += r4
cannot add integer value with 3 upper zero bits to ptr_to_packet

Thus to get above use-cases working, evaluate_reg_imm_alu() has been extended for further ALU ops. This is fine, because we only operate strictly within realm of CONST_IMM types, so here we don't care about overflows as they will happen in the simulated but also real execution and interaction with pkt() in check_packet_ptr_add() will check actual imm value once added to pkt(), but it's irrelevant before.

With regards to 06c1c049721a ("bpf: allow helpers access to variable memory") that works on UNKNOWN_VALUE registers, the verifier becomes now a bit smarter as it can better resolve ALU ops, so we need to adapt two test cases there, as min/max bound tracking only becomes necessary when registers were spilled to stack. So while mask was set before to track upper bound for UNKNOWN_VALUE case, it's now resolved directly as CONST_IMM, and such contructs are only necessary when f.e. registers are spilled.

For commit 6b17387307ba ("bpf: recognize 64bit immediate loads as consts") that initially enabled dw load tracking only for nfp jit/ analyzer, I did couple of tests on large, complex programs and we don't increase complexity badly (my tests were in ~3% range on avg). I've added a couple of tests similar to affected code above, and it works fine with verifier now.

Reported-by William Tu <[email protected]>

Signed-off-by Daniel Borkmann <[email protected]>

Cc Gianluca Borello <[email protected]>

Cc William Tu <[email protected]>

Acked-by Alexei Starovoitov <[email protected]>

---
 kernel/bpf/verifier.c                       | 64 +++++++++++++++-------
 tools/testing/selftests/bpf/test_verifier.c | 82 +++++++++++++++++++++++++++++
 2 files changed, 127 insertions(+), 19 deletions(-)

kernel/bpf/verifier.c +45 ~~-19~~

index 8f69df7..fb3513b 100644
@@ -1566,22 +1566,54 @@ static int evaluate_reg_imm_alu(struct bpf_verifier_env *env,
 	struct bpf_reg_state *dst_reg = &regs[insn->dst_reg];
 	struct bpf_reg_state *src_reg = &regs[insn->src_reg];
 	u8 opcode = BPF_OP(insn->code);
+	u64 dst_imm = dst_reg->imm;
 
-	/* dst_reg->type == CONST_IMM here, simulate execution of 'add'/'or'
-	 * insn. Don't care about overflow or negative values, just add them
+	/* dst_reg->type == CONST_IMM here. Simulate execution of insns
+	 * containing ALU ops. Don't care about overflow or negative
+	 * values, just add/sub/... them; registers are in u64.
 	 */
-	if (opcode == BPF_ADD && BPF_SRC(insn->code) == BPF_K)
-		dst_reg->imm += insn->imm;
-	else if (opcode == BPF_ADD && BPF_SRC(insn->code) == BPF_X &&
-		 src_reg->type == CONST_IMM)
-		dst_reg->imm += src_reg->imm;
-	else if (opcode == BPF_OR && BPF_SRC(insn->code) == BPF_K)
-		dst_reg->imm |= insn->imm;
-	else if (opcode == BPF_OR && BPF_SRC(insn->code) == BPF_X &&
-		 src_reg->type == CONST_IMM)
-		dst_reg->imm |= src_reg->imm;
-	else
+	if (opcode == BPF_ADD && BPF_SRC(insn->code) == BPF_K) {
+		dst_imm += insn->imm;
+	} else if (opcode == BPF_ADD && BPF_SRC(insn->code) == BPF_X &&
+		   src_reg->type == CONST_IMM) {
+		dst_imm += src_reg->imm;
+	} else if (opcode == BPF_SUB && BPF_SRC(insn->code) == BPF_K) {
+		dst_imm -= insn->imm;
+	} else if (opcode == BPF_SUB && BPF_SRC(insn->code) == BPF_X &&
+		   src_reg->type == CONST_IMM) {
+		dst_imm -= src_reg->imm;
+	} else if (opcode == BPF_MUL && BPF_SRC(insn->code) == BPF_K) {
+		dst_imm *= insn->imm;
+	} else if (opcode == BPF_MUL && BPF_SRC(insn->code) == BPF_X &&
+		   src_reg->type == CONST_IMM) {
+		dst_imm *= src_reg->imm;
+	} else if (opcode == BPF_OR && BPF_SRC(insn->code) == BPF_K) {
+		dst_imm |= insn->imm;
+	} else if (opcode == BPF_OR && BPF_SRC(insn->code) == BPF_X &&
+		   src_reg->type == CONST_IMM) {
+		dst_imm |= src_reg->imm;
+	} else if (opcode == BPF_AND && BPF_SRC(insn->code) == BPF_K) {
+		dst_imm &= insn->imm;
+	} else if (opcode == BPF_AND && BPF_SRC(insn->code) == BPF_X &&
+		   src_reg->type == CONST_IMM) {
+		dst_imm &= src_reg->imm;
+	} else if (opcode == BPF_RSH && BPF_SRC(insn->code) == BPF_K) {
+		dst_imm >>= insn->imm;
+	} else if (opcode == BPF_RSH && BPF_SRC(insn->code) == BPF_X &&
+		   src_reg->type == CONST_IMM) {
+		dst_imm >>= src_reg->imm;
+	} else if (opcode == BPF_LSH && BPF_SRC(insn->code) == BPF_K) {
+		dst_imm <<= insn->imm;
+	} else if (opcode == BPF_LSH && BPF_SRC(insn->code) == BPF_X &&
+		   src_reg->type == CONST_IMM) {
+		dst_imm <<= src_reg->imm;
+	} else {
 		mark_reg_unknown_value(regs, insn->dst_reg);
+		goto out;
+	}
+
+	dst_reg->imm = dst_imm;
+out:
 	return 0;
 }

@@ -2225,14 +2257,8 @@ static int check_ld_imm(struct bpf_verifier_env *env, struct bpf_insn *insn)
 		return err;
 
 	if (insn->src_reg == 0) {
-		/* generic move 64-bit immediate into a register,
-		 * only analyzer needs to collect the ld_imm value.
-		 */
 		u64 imm = ((u64)(insn + 1)->imm << 32) | (u32)insn->imm;
 
-		if (!env->analyzer_ops)
-			return 0;
-
 		regs[insn->dst_reg].type = CONST_IMM;
 		regs[insn->dst_reg].imm = imm;
 		return 0;

tools/testing/selftests/bpf/test_verifier.c +82 -0

100 lines not on this page · raw message

Signature · 1 line

1.9.3

William Tu

2017-01-25 15:57 UTC #6 lore raw

Re: [PATCH net-next 5/5] bpf: enable verifier to better track const alu ops

Looks good to me, I tested with several complex program without any problem. Thanks for the patch.
--William

Quoted 293 lines · Daniel Borkmann

William reported couple of issues in relation to direct packet access. Typical scheme is to check for data + [off] <= data_end, where [off] can be either immediate or coming from a tracked register that contains an immediate, depending on the branch, we can then access the data. However, in case of calculating [off] for either the mentioned test itself or for access after the test in a more "complex" way, then the verifier will stop tracking the CONST_IMM marked register and will mark it as UNKNOWN_VALUE one.

Adding that UNKNOWN_VALUE typed register to a pkt() marked register, the verifier then bails out in check_packet_ptr_add() as it finds the registers imm value below 48. In the first below example, that is due to evaluate_reg_imm_alu() not handling right shifts and thus marking the register as UNKNOWN_VALUE via helper __mark_reg_unknown_value() that resets imm to 0.

In the second case the same happens at the time when r4 is set to r4 &= r5, where it transitions to UNKNOWN_VALUE from evaluate_reg_imm_alu(). Later on r4 we shift right by 3 inside evaluate_reg_alu(), where the register's imm turns into 3. That is, for registers with type UNKNOWN_VALUE, imm of 0 means that we don't know what value the register has, and for imm > 0 it means that the value has [imm] upper zero bits. F.e. when shifting an UNKNOWN_VALUE register by 3 to the right, no matter what value it had, we know that the 3 upper most bits must be zero now. This is to make sure that ALU operations with unknown registers don't overflow. Meaning, once we know that we have more than 48 upper zero bits, or, in other words cannot go beyond 0xffff offset with ALU ops, such an addition will track the target register as a new pkt() register with a new id, but 0 offset and 0 range, so for that a new data/data_end test will be required. Is the source register a CONST_IMM one that is to be added to the pkt() register, or the source instruction is an add instruction with immediate value, then it will get added if it stays within max 0xffff bounds. From there, pkt() type, can be accessed should reg->off + imm be within the access range of pkt().

[...]
from 28 to 30: R0=imm1,min_value=1,max_value=1

    R1=pkt(id=0,off=0,r=22) R2=pkt_end
    R3=imm144,min_value=144,max_value=144
    R4=imm0,min_value=0,max_value=0
    R5=inv48,min_value=2054,max_value=2054 R10=fp

30: (bf) r5 = r3
31: (07) r5 += 23
32: (77) r5 >>= 3
33: (bf) r6 = r1
34: (0f) r6 += r5
cannot add integer value with 0 upper zero bits to ptr_to_packet

[...]
from 52 to 80: R0=imm1,min_value=1,max_value=1

    R1=pkt(id=0,off=0,r=34) R2=pkt_end R3=inv
    R4=imm272 R5=inv56,min_value=17,max_value=17
    R6=pkt(id=0,off=26,r=34) R10=fp

80: (07) r4 += 71
81: (18) r5 = 0xfffffff8
83: (5f) r4 &= r5
84: (77) r4 >>= 3
85: (0f) r1 += r4
cannot add integer value with 3 upper zero bits to ptr_to_packet

Thus to get above use-cases working, evaluate_reg_imm_alu() has been extended for further ALU ops. This is fine, because we only operate strictly within realm of CONST_IMM types, so here we don't care about overflows as they will happen in the simulated but also real execution and interaction with pkt() in check_packet_ptr_add() will check actual imm value once added to pkt(), but it's irrelevant before.

With regards to 06c1c049721a ("bpf: allow helpers access to variable memory") that works on UNKNOWN_VALUE registers, the verifier becomes now a bit smarter as it can better resolve ALU ops, so we need to adapt two test cases there, as min/max bound tracking only becomes necessary when registers were spilled to stack. So while mask was set before to track upper bound for UNKNOWN_VALUE case, it's now resolved directly as CONST_IMM, and such contructs are only necessary when f.e. registers are spilled.

For commit 6b17387307ba ("bpf: recognize 64bit immediate loads as consts") that initially enabled dw load tracking only for nfp jit/ analyzer, I did couple of tests on large, complex programs and we don't increase complexity badly (my tests were in ~3% range on avg). I've added a couple of tests similar to affected code above, and it works fine with verifier now.

Reported-by William Tu <[email protected]>

Signed-off-by Daniel Borkmann <[email protected]>

Cc Gianluca Borello <[email protected]>

Cc William Tu <[email protected]>

Acked-by Alexei Starovoitov <[email protected]>

---
 kernel/bpf/verifier.c                       | 64 +++++++++++++++-------
 tools/testing/selftests/bpf/test_verifier.c | 82 +++++++++++++++++++++++++++++
 2 files changed, 127 insertions(+), 19 deletions(-)

kernel/bpf/verifier.c +45 ~~-19~~

index 8f69df7..fb3513b 100644
@@ -1566,22 +1566,54 @@ static int evaluate_reg_imm_alu(struct bpf_verifier_env *env,
        struct bpf_reg_state *dst_reg = &regs[insn->dst_reg];
        struct bpf_reg_state *src_reg = &regs[insn->src_reg];
        u8 opcode = BPF_OP(insn->code);
+       u64 dst_imm = dst_reg->imm;
 
-       /* dst_reg->type == CONST_IMM here, simulate execution of 'add'/'or'
-        * insn. Don't care about overflow or negative values, just add them
+       /* dst_reg->type == CONST_IMM here. Simulate execution of insns
+        * containing ALU ops. Don't care about overflow or negative
+        * values, just add/sub/... them; registers are in u64.
         */
-       if (opcode == BPF_ADD && BPF_SRC(insn->code) == BPF_K)
-               dst_reg->imm += insn->imm;
-       else if (opcode == BPF_ADD && BPF_SRC(insn->code) == BPF_X &&
-                src_reg->type == CONST_IMM)
-               dst_reg->imm += src_reg->imm;
-       else if (opcode == BPF_OR && BPF_SRC(insn->code) == BPF_K)
-               dst_reg->imm |= insn->imm;
-       else if (opcode == BPF_OR && BPF_SRC(insn->code) == BPF_X &&
-                src_reg->type == CONST_IMM)
-               dst_reg->imm |= src_reg->imm;
-       else
+       if (opcode == BPF_ADD && BPF_SRC(insn->code) == BPF_K) {
+               dst_imm += insn->imm;
+       } else if (opcode == BPF_ADD && BPF_SRC(insn->code) == BPF_X &&
+                  src_reg->type == CONST_IMM) {
+               dst_imm += src_reg->imm;
+       } else if (opcode == BPF_SUB && BPF_SRC(insn->code) == BPF_K) {
+               dst_imm -= insn->imm;
+       } else if (opcode == BPF_SUB && BPF_SRC(insn->code) == BPF_X &&
+                  src_reg->type == CONST_IMM) {
+               dst_imm -= src_reg->imm;
+       } else if (opcode == BPF_MUL && BPF_SRC(insn->code) == BPF_K) {
+               dst_imm *= insn->imm;
+       } else if (opcode == BPF_MUL && BPF_SRC(insn->code) == BPF_X &&
+                  src_reg->type == CONST_IMM) {
+               dst_imm *= src_reg->imm;
+       } else if (opcode == BPF_OR && BPF_SRC(insn->code) == BPF_K) {
+               dst_imm |= insn->imm;
+       } else if (opcode == BPF_OR && BPF_SRC(insn->code) == BPF_X &&
+                  src_reg->type == CONST_IMM) {
+               dst_imm |= src_reg->imm;
+       } else if (opcode == BPF_AND && BPF_SRC(insn->code) == BPF_K) {
+               dst_imm &= insn->imm;
+       } else if (opcode == BPF_AND && BPF_SRC(insn->code) == BPF_X &&
+                  src_reg->type == CONST_IMM) {
+               dst_imm &= src_reg->imm;
+       } else if (opcode == BPF_RSH && BPF_SRC(insn->code) == BPF_K) {
+               dst_imm >>= insn->imm;
+       } else if (opcode == BPF_RSH && BPF_SRC(insn->code) == BPF_X &&
+                  src_reg->type == CONST_IMM) {
+               dst_imm >>= src_reg->imm;
+       } else if (opcode == BPF_LSH && BPF_SRC(insn->code) == BPF_K) {
+               dst_imm <<= insn->imm;
+       } else if (opcode == BPF_LSH && BPF_SRC(insn->code) == BPF_X &&
+                  src_reg->type == CONST_IMM) {
+               dst_imm <<= src_reg->imm;
+       } else {
                mark_reg_unknown_value(regs, insn->dst_reg);
+               goto out;
+       }
+
+       dst_reg->imm = dst_imm;
+out:
        return 0;
 }

@@ -2225,14 +2257,8 @@ static int check_ld_imm(struct bpf_verifier_env *env, struct bpf_insn *insn)
                return err;
 
        if (insn->src_reg == 0) {
-               /* generic move 64-bit immediate into a register,
-                * only analyzer needs to collect the ld_imm value.
-                */
                u64 imm = ((u64)(insn + 1)->imm << 32) | (u32)insn->imm;
 
-               if (!env->analyzer_ops)
-                       return 0;
-
                regs[insn->dst_reg].type = CONST_IMM;
                regs[insn->dst_reg].imm = imm;
                return 0;

tools/testing/selftests/bpf/test_verifier.c +82 -1

index 1aa7324..0d0912c 100644
@@ -2326,6 +2326,84 @@ struct test_val {
                .prog_type = BPF_PROG_TYPE_SCHED_CLS,
        },
        {
+               "direct packet access: test11 (shift, good access)",
+               .insns = {
+                       BPF_LDX_MEM(BPF_W, BPF_REG_2, BPF_REG_1,
+                                   offsetof(struct __sk_buff, data)),
+                       BPF_LDX_MEM(BPF_W, BPF_REG_3, BPF_REG_1,
+                                   offsetof(struct __sk_buff, data_end)),
+                       BPF_MOV64_REG(BPF_REG_0, BPF_REG_2),
+                       BPF_ALU64_IMM(BPF_ADD, BPF_REG_0, 22),
+                       BPF_JMP_REG(BPF_JGT, BPF_REG_0, BPF_REG_3, 8),
+                       BPF_MOV64_IMM(BPF_REG_3, 144),
+                       BPF_MOV64_REG(BPF_REG_5, BPF_REG_3),
+                       BPF_ALU64_IMM(BPF_ADD, BPF_REG_5, 23),
+                       BPF_ALU64_IMM(BPF_RSH, BPF_REG_5, 3),
+                       BPF_MOV64_REG(BPF_REG_6, BPF_REG_2),
+                       BPF_ALU64_REG(BPF_ADD, BPF_REG_6, BPF_REG_5),
+                       BPF_MOV64_IMM(BPF_REG_0, 1),
+                       BPF_EXIT_INSN(),
+                       BPF_MOV64_IMM(BPF_REG_0, 0),
+                       BPF_EXIT_INSN(),
+               },
+               .result = ACCEPT,
+               .prog_type = BPF_PROG_TYPE_SCHED_CLS,
+       },
+       {
+               "direct packet access: test12 (and, good access)",
+               .insns = {
+                       BPF_LDX_MEM(BPF_W, BPF_REG_2, BPF_REG_1,
+                                   offsetof(struct __sk_buff, data)),
+                       BPF_LDX_MEM(BPF_W, BPF_REG_3, BPF_REG_1,
+                                   offsetof(struct __sk_buff, data_end)),
+                       BPF_MOV64_REG(BPF_REG_0, BPF_REG_2),
+                       BPF_ALU64_IMM(BPF_ADD, BPF_REG_0, 22),
+                       BPF_JMP_REG(BPF_JGT, BPF_REG_0, BPF_REG_3, 8),
+                       BPF_MOV64_IMM(BPF_REG_3, 144),
+                       BPF_MOV64_REG(BPF_REG_5, BPF_REG_3),
+                       BPF_ALU64_IMM(BPF_ADD, BPF_REG_5, 23),
+                       BPF_ALU64_IMM(BPF_AND, BPF_REG_5, 15),
+                       BPF_MOV64_REG(BPF_REG_6, BPF_REG_2),
+                       BPF_ALU64_REG(BPF_ADD, BPF_REG_6, BPF_REG_5),
+                       BPF_MOV64_IMM(BPF_REG_0, 1),
+                       BPF_EXIT_INSN(),
+                       BPF_MOV64_IMM(BPF_REG_0, 0),
+                       BPF_EXIT_INSN(),
+               },
+               .result = ACCEPT,
+               .prog_type = BPF_PROG_TYPE_SCHED_CLS,
+       },
+       {
+               "direct packet access: test13 (branches, good access)",
+               .insns = {
+                       BPF_LDX_MEM(BPF_W, BPF_REG_2, BPF_REG_1,
+                                   offsetof(struct __sk_buff, data)),
+                       BPF_LDX_MEM(BPF_W, BPF_REG_3, BPF_REG_1,
+                                   offsetof(struct __sk_buff, data_end)),
+                       BPF_MOV64_REG(BPF_REG_0, BPF_REG_2),
+                       BPF_ALU64_IMM(BPF_ADD, BPF_REG_0, 22),
+                       BPF_JMP_REG(BPF_JGT, BPF_REG_0, BPF_REG_3, 13),
+                       BPF_LDX_MEM(BPF_W, BPF_REG_3, BPF_REG_1,
+                                   offsetof(struct __sk_buff, mark)),
+                       BPF_MOV64_IMM(BPF_REG_4, 1),
+                       BPF_JMP_REG(BPF_JGT, BPF_REG_3, BPF_REG_4, 2),
+                       BPF_MOV64_IMM(BPF_REG_3, 14),
+                       BPF_JMP_IMM(BPF_JA, 0, 0, 1),
+                       BPF_MOV64_IMM(BPF_REG_3, 24),
+                       BPF_MOV64_REG(BPF_REG_5, BPF_REG_3),
+                       BPF_ALU64_IMM(BPF_ADD, BPF_REG_5, 23),
+                       BPF_ALU64_IMM(BPF_AND, BPF_REG_5, 15),
+                       BPF_MOV64_REG(BPF_REG_6, BPF_REG_2),
+                       BPF_ALU64_REG(BPF_ADD, BPF_REG_6, BPF_REG_5),
+                       BPF_MOV64_IMM(BPF_REG_0, 1),
+                       BPF_EXIT_INSN(),
+                       BPF_MOV64_IMM(BPF_REG_0, 0),
+                       BPF_EXIT_INSN(),
+               },
+               .result = ACCEPT,
+               .prog_type = BPF_PROG_TYPE_SCHED_CLS,
+       },
+       {
                "helper access to packet: test1, valid packet_ptr range",
                .insns = {
                        BPF_LDX_MEM(BPF_W, BPF_REG_2, BPF_REG_1,

@@ -4208,6 +4286,8 @@ struct test_val {
                .insns = {
                        BPF_MOV64_IMM(BPF_REG_1, 0),
                        BPF_MOV64_IMM(BPF_REG_2, 0),
+                       BPF_STX_MEM(BPF_DW, BPF_REG_10, BPF_REG_2, -128),
+                       BPF_LDX_MEM(BPF_DW, BPF_REG_2, BPF_REG_10, -128),
                        BPF_ALU64_IMM(BPF_AND, BPF_REG_2, 64),
                        BPF_MOV64_IMM(BPF_REG_3, 0),
                        BPF_MOV64_IMM(BPF_REG_4, 0),

@@ -4251,6 +4331,8 @@ struct test_val {
                        BPF_STX_MEM(BPF_DW, BPF_REG_10, BPF_REG_0, -16),
                        BPF_STX_MEM(BPF_DW, BPF_REG_10, BPF_REG_0, -8),
                        BPF_MOV64_IMM(BPF_REG_2, 0),
+                       BPF_STX_MEM(BPF_DW, BPF_REG_10, BPF_REG_2, -128),
+                       BPF_LDX_MEM(BPF_DW, BPF_REG_2, BPF_REG_10, -128),
                        BPF_ALU64_IMM(BPF_AND, BPF_REG_2, 63),
                        BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, 1),
                        BPF_MOV64_IMM(BPF_REG_3, 0),
--

1.9.3

Daniel Borkmann

author maintainer

2017-01-25 20:19 UTC #7 lore raw

Re: [PATCH net-next 5/5] bpf: enable verifier to better track const alu ops

Quoted 2 lines · William Tu

Looks good to me, I tested with several complex program without any problem. Thanks for the patch.

Thanks for re-testing, William!

David Miller

maintainer

2017-01-24 19:49 UTC #8 lore raw

In reply to Daniel Borkmann

From: Daniel Borkmann <[email protected]>
Date: Tue, 24 Jan 2017 01:06:25 +0100

Quoted 4 lines

This series adds various misc improvements to BPF, f.e. allowing skb_load_bytes() helper to be used with filter/reuseport programs to facilitate programming, test cases for program tag, etc. For details, please see individual patches.

Series applied, thanks.