[PATCH net-next 0/8] Add complementary BPF conditional jump instructions

[PATCH net-next 0/8] Add complementary BPF conditional jump instructions

[Daniel Borkmann]

This set adds adds jump operations for lt (<), le (<=), ne (!=) that
compare A with K resp. X in order to facilitate filter programming
with conditional jumps, as also available in McCanne et. al's BPF+
paper (``BPF+: Exploiting Global Data-flow Optimization in a Generalized
Packet Filter Architecture'').

Also, follow-up BPF JIT implementations for x86, Sparc and PowerPC
are added in this set.

Daniel Borkmann (8):
  net: bpf: add lt,le jump operations to bpf machine
  x86: bpf_jit_comp: add JMP instructions for BPF JIT
  sparc: bpf_jit_comp: add JMP instructions for BPF JIT
  PPC: bpf_jit_comp: add JMP instructions for BPF JIT
  net: bpf: add neq jump operations to bpf machine
  x86: bpf_jit_comp: add JMP_NEQ instructions for BPF JIT
  sparc: bpf_jit_comp: add JMP_NEQ instructions for BPF JIT
  PPC: bpf_jit_comp: add JMP_NEQ instructions for BPF JIT

 arch/powerpc/net/bpf_jit.h      |  1 +
 arch/powerpc/net/bpf_jit_comp.c | 16 ++++++++++++++++
 arch/sparc/net/bpf_jit_comp.c   | 12 ++++++++++++
 arch/x86/net/bpf_jit_comp.c     | 12 ++++++++++++
 include/linux/filter.h          |  6 ++++++
 include/uapi/linux/filter.h     |  4 ++++
 net/core/filter.c               | 42 +++++++++++++++++++++++++++++++++++++++++
 7 files changed, 93 insertions(+)

-- 
1.7.11.7

[PATCH net-next 1/8] net: bpf: add lt,le jump operations to bpf machine

[Daniel Borkmann]

This patch adds jump operations for lt (<) and le (<=) that
compare A with K resp. X in order to facilitate filter
programming with conditional jumps, since currently only
gt (>) and ge (>=) are present in the BPF machine. For
user-space filter programming / compilers, it might be good
to also have those complementary operations. They don't need
to be as ancillary, since they fit into the instruction
encoding directly. Follow-up BPF JIT patches are welcomed.

Signed-off-by: Daniel Borkmann <dborkman@redhat.com>
---
 include/linux/filter.h      |  4 ++++
 include/uapi/linux/filter.h |  3 +++
 net/core/filter.c           | 28 ++++++++++++++++++++++++++++
 3 files changed, 35 insertions(+)

diff --git a/include/linux/filter.h b/include/linux/filter.h
index c45eabc..36630bc 100644
--- a/include/linux/filter.h
+++ b/include/linux/filter.h
@@ -109,6 +109,10 @@ enum {
 	BPF_S_JMP_JGE_X,
 	BPF_S_JMP_JGT_K,
 	BPF_S_JMP_JGT_X,
+	BPF_S_JMP_JLE_K,
+	BPF_S_JMP_JLE_X,
+	BPF_S_JMP_JLT_K,
+	BPF_S_JMP_JLT_X,
 	BPF_S_JMP_JSET_K,
 	BPF_S_JMP_JSET_X,
 	/* Ancillary data */
diff --git a/include/uapi/linux/filter.h b/include/uapi/linux/filter.h
index 9cfde69..3ebcc2e 100644
--- a/include/uapi/linux/filter.h
+++ b/include/uapi/linux/filter.h
@@ -78,6 +78,9 @@ struct sock_fprog {	/* Required for SO_ATTACH_FILTER. */
 #define         BPF_JGT         0x20
 #define         BPF_JGE         0x30
 #define         BPF_JSET        0x40
+#define         BPF_JLT         0x50
+#define         BPF_JLE         0x60
+
 #define BPF_SRC(code)   ((code) & 0x08)
 #define         BPF_K           0x00
 #define         BPF_X           0x08
diff --git a/net/core/filter.c b/net/core/filter.c
index 2ead2a9..2122eba 100644
--- a/net/core/filter.c
+++ b/net/core/filter.c
@@ -219,6 +219,12 @@ unsigned int sk_run_filter(const struct sk_buff *skb,
 		case BPF_S_JMP_JGE_K:
 			fentry += (A >= K) ? fentry->jt : fentry->jf;
 			continue;
+		case BPF_S_JMP_JLT_K:
+			fentry += (A < K) ? fentry->jt : fentry->jf;
+			continue;
+		case BPF_S_JMP_JLE_K:
+			fentry += (A <= K) ? fentry->jt : fentry->jf;
+			continue;
 		case BPF_S_JMP_JEQ_K:
 			fentry += (A == K) ? fentry->jt : fentry->jf;
 			continue;
@@ -231,6 +237,12 @@ unsigned int sk_run_filter(const struct sk_buff *skb,
 		case BPF_S_JMP_JGE_X:
 			fentry += (A >= X) ? fentry->jt : fentry->jf;
 			continue;
+		case BPF_S_JMP_JLT_X:
+			fentry += (A < X) ? fentry->jt : fentry->jf;
+			continue;
+		case BPF_S_JMP_JLE_X:
+			fentry += (A <= X) ? fentry->jt : fentry->jf;
+			continue;
 		case BPF_S_JMP_JEQ_X:
 			fentry += (A == X) ? fentry->jt : fentry->jf;
 			continue;
@@ -446,6 +458,10 @@ static int check_load_and_stores(struct sock_filter *filter, int flen)
 		case BPF_S_JMP_JGE_X:
 		case BPF_S_JMP_JGT_K:
 		case BPF_S_JMP_JGT_X:
+		case BPF_S_JMP_JLE_K:
+		case BPF_S_JMP_JLE_X:
+		case BPF_S_JMP_JLT_K:
+		case BPF_S_JMP_JLT_X:
 		case BPF_S_JMP_JSET_X:
 		case BPF_S_JMP_JSET_K:
 			/* a jump must set masks on targets */
@@ -528,6 +544,10 @@ int sk_chk_filter(struct sock_filter *filter, unsigned int flen)
 		[BPF_JMP|BPF_JGE|BPF_X]  = BPF_S_JMP_JGE_X,
 		[BPF_JMP|BPF_JGT|BPF_K]  = BPF_S_JMP_JGT_K,
 		[BPF_JMP|BPF_JGT|BPF_X]  = BPF_S_JMP_JGT_X,
+		[BPF_JMP|BPF_JLE|BPF_K]  = BPF_S_JMP_JLE_K,
+		[BPF_JMP|BPF_JLE|BPF_X]  = BPF_S_JMP_JLE_X,
+		[BPF_JMP|BPF_JLT|BPF_K]  = BPF_S_JMP_JLT_K,
+		[BPF_JMP|BPF_JLT|BPF_X]  = BPF_S_JMP_JLT_X,
 		[BPF_JMP|BPF_JSET|BPF_K] = BPF_S_JMP_JSET_K,
 		[BPF_JMP|BPF_JSET|BPF_X] = BPF_S_JMP_JSET_X,
 	};
@@ -583,6 +603,10 @@ int sk_chk_filter(struct sock_filter *filter, unsigned int flen)
 		case BPF_S_JMP_JGE_X:
 		case BPF_S_JMP_JGT_K:
 		case BPF_S_JMP_JGT_X:
+		case BPF_S_JMP_JLE_K:
+		case BPF_S_JMP_JLE_X:
+		case BPF_S_JMP_JLT_K:
+		case BPF_S_JMP_JLT_X:
 		case BPF_S_JMP_JSET_X:
 		case BPF_S_JMP_JSET_K:
 			/* for conditionals both must be safe */
@@ -832,6 +856,10 @@ static void sk_decode_filter(struct sock_filter *filt, struct sock_filter *to)
 		[BPF_S_JMP_JGE_X]	= BPF_JMP|BPF_JGE|BPF_X,
 		[BPF_S_JMP_JGT_K]	= BPF_JMP|BPF_JGT|BPF_K,
 		[BPF_S_JMP_JGT_X]	= BPF_JMP|BPF_JGT|BPF_X,
+		[BPF_S_JMP_JLE_K]	= BPF_JMP|BPF_JLE|BPF_K,
+		[BPF_S_JMP_JLE_X]	= BPF_JMP|BPF_JLE|BPF_X,
+		[BPF_S_JMP_JLT_K]	= BPF_JMP|BPF_JLT|BPF_K,
+		[BPF_S_JMP_JLT_X]	= BPF_JMP|BPF_JLT|BPF_X,
 		[BPF_S_JMP_JSET_K]	= BPF_JMP|BPF_JSET|BPF_K,
 		[BPF_S_JMP_JSET_X]	= BPF_JMP|BPF_JSET|BPF_X,
 	};
-- 
1.7.11.7

[PATCH net-next 2/8] x86: bpf_jit_comp: add JMP instructions for BPF JIT

[Daniel Borkmann]

This patch is a follow-up for patch "net: bpf: add lt,le jump
operations to bpf machine" that implements BPF x86 JIT parts
for BPF JMP_LT/JMP_LE operations.

Cc: Eric Dumazet <eric.dumazet@gmail.com>
Signed-off-by: Daniel Borkmann <dborkman@redhat.com>
---
 arch/x86/net/bpf_jit_comp.c | 8 ++++++++
 1 file changed, 8 insertions(+)

diff --git a/arch/x86/net/bpf_jit_comp.c b/arch/x86/net/bpf_jit_comp.c
index d11a470..6d6a4ce 100644
--- a/arch/x86/net/bpf_jit_comp.c
+++ b/arch/x86/net/bpf_jit_comp.c
@@ -584,10 +584,14 @@ common_load_ind:		seen |= SEEN_DATAREF | SEEN_XREG;
 				break;
 			COND_SEL(BPF_S_JMP_JGT_K, X86_JA, X86_JBE);
 			COND_SEL(BPF_S_JMP_JGE_K, X86_JAE, X86_JB);
+			COND_SEL(BPF_S_JMP_JLT_K, X86_JB, X86_JAE);
+			COND_SEL(BPF_S_JMP_JLE_K, X86_JBE, X86_JA);
 			COND_SEL(BPF_S_JMP_JEQ_K, X86_JE, X86_JNE);
 			COND_SEL(BPF_S_JMP_JSET_K,X86_JNE, X86_JE);
 			COND_SEL(BPF_S_JMP_JGT_X, X86_JA, X86_JBE);
 			COND_SEL(BPF_S_JMP_JGE_X, X86_JAE, X86_JB);
+			COND_SEL(BPF_S_JMP_JLT_X, X86_JB, X86_JAE);
+			COND_SEL(BPF_S_JMP_JLE_X, X86_JBE, X86_JA);
 			COND_SEL(BPF_S_JMP_JEQ_X, X86_JE, X86_JNE);
 			COND_SEL(BPF_S_JMP_JSET_X,X86_JNE, X86_JE);
 
@@ -603,6 +607,8 @@ cond_branch:			f_offset = addrs[i + filter[i].jf] - addrs[i];
 				switch (filter[i].code) {
 				case BPF_S_JMP_JGT_X:
 				case BPF_S_JMP_JGE_X:
+				case BPF_S_JMP_JLT_X:
+				case BPF_S_JMP_JLE_X:
 				case BPF_S_JMP_JEQ_X:
 					seen |= SEEN_XREG;
 					EMIT2(0x39, 0xd8); /* cmp %ebx,%eax */
@@ -618,6 +624,8 @@ cond_branch:			f_offset = addrs[i + filter[i].jf] - addrs[i];
 					}
 				case BPF_S_JMP_JGT_K:
 				case BPF_S_JMP_JGE_K:
+				case BPF_S_JMP_JLT_K:
+				case BPF_S_JMP_JLE_K:
 					if (K <= 127)
 						EMIT3(0x83, 0xf8, K); /* cmp imm8,%eax */
 					else
-- 
1.7.11.7

[PATCH net-next 3/8] sparc: bpf_jit_comp: add JMP instructions for BPF JIT

[Daniel Borkmann]

This patch is a follow-up for patch "net: bpf: add lt,le jump
operations to bpf machine" that implements BPF SPARC JIT parts
for BPF JMP_LT/JMP_LE operations.

Signed-off-by: Daniel Borkmann <dborkman@redhat.com>
---
 arch/sparc/net/bpf_jit_comp.c | 8 ++++++++
 1 file changed, 8 insertions(+)

diff --git a/arch/sparc/net/bpf_jit_comp.c b/arch/sparc/net/bpf_jit_comp.c
index 3109ca6..f5b4fc9 100644
--- a/arch/sparc/net/bpf_jit_comp.c
+++ b/arch/sparc/net/bpf_jit_comp.c
@@ -691,10 +691,14 @@ common_load_ind:		seen |= SEEN_DATAREF | SEEN_XREG;
 
 			COND_SEL(BPF_S_JMP_JGT_K, BGU, BLEU);
 			COND_SEL(BPF_S_JMP_JGE_K, BGEU, BLU);
+			COND_SEL(BPF_S_JMP_JLT_K, BLU, BGEU);
+			COND_SEL(BPF_S_JMP_JLE_K, BLEU, BGU);
 			COND_SEL(BPF_S_JMP_JEQ_K, BE, BNE);
 			COND_SEL(BPF_S_JMP_JSET_K, BNE, BE);
 			COND_SEL(BPF_S_JMP_JGT_X, BGU, BLEU);
 			COND_SEL(BPF_S_JMP_JGE_X, BGEU, BLU);
+			COND_SEL(BPF_S_JMP_JLT_X, BLU, BGEU);
+			COND_SEL(BPF_S_JMP_JLE_X, BLEU, BGU);
 			COND_SEL(BPF_S_JMP_JEQ_X, BE, BNE);
 			COND_SEL(BPF_S_JMP_JSET_X, BNE, BE);
 
@@ -711,6 +715,8 @@ cond_branch:			f_offset = addrs[i + filter[i].jf];
 				switch (filter[i].code) {
 				case BPF_S_JMP_JGT_X:
 				case BPF_S_JMP_JGE_X:
+				case BPF_S_JMP_JLT_X:
+				case BPF_S_JMP_JLE_X:
 				case BPF_S_JMP_JEQ_X:
 					seen |= SEEN_XREG;
 					emit_cmp(r_A, r_X);
@@ -722,6 +728,8 @@ cond_branch:			f_offset = addrs[i + filter[i].jf];
 				case BPF_S_JMP_JEQ_K:
 				case BPF_S_JMP_JGT_K:
 				case BPF_S_JMP_JGE_K:
+				case BPF_S_JMP_JLT_K:
+				case BPF_S_JMP_JLE_K:
 					if (is_simm13(K)) {
 						emit_cmpi(r_A, K);
 					} else {
-- 
1.7.11.7

[PATCH net-next 4/8] PPC: bpf_jit_comp: add JMP instructions for BPF JIT

[Daniel Borkmann]

This patch is a follow-up for patch "net: bpf: add lt,le jump
operations to bpf machine" that implements BPF PowerPC JIT parts
for BPF JMP_LT/JMP_LE operations.

Cc: Matt Evans <matt@ozlabs.org>
Signed-off-by: Daniel Borkmann <dborkman@redhat.com>
---
 arch/powerpc/net/bpf_jit.h      |  1 +
 arch/powerpc/net/bpf_jit_comp.c | 12 ++++++++++++
 2 files changed, 13 insertions(+)

diff --git a/arch/powerpc/net/bpf_jit.h b/arch/powerpc/net/bpf_jit.h
index 8a5dfaf..f105b3b 100644
--- a/arch/powerpc/net/bpf_jit.h
+++ b/arch/powerpc/net/bpf_jit.h
@@ -221,6 +221,7 @@ static inline bool is_nearbranch(int offset)
 #define COND_EQ		(CR0_EQ | COND_CMP_TRUE)
 #define COND_NE		(CR0_EQ | COND_CMP_FALSE)
 #define COND_LT		(CR0_LT | COND_CMP_TRUE)
+#define COND_LE		(CR0_GT | COND_CMP_FALSE)
 
 #define SEEN_DATAREF 0x10000 /* might call external helpers */
 #define SEEN_XREG    0x20000 /* X reg is used */
diff --git a/arch/powerpc/net/bpf_jit_comp.c b/arch/powerpc/net/bpf_jit_comp.c
index e834f1e..46b4d21 100644
--- a/arch/powerpc/net/bpf_jit_comp.c
+++ b/arch/powerpc/net/bpf_jit_comp.c
@@ -484,6 +484,14 @@ static int bpf_jit_build_body(struct sk_filter *fp, u32 *image,
 		case BPF_S_JMP_JGE_X:
 			true_cond = COND_GE;
 			goto cond_branch;
+		case BPF_S_JMP_JLT_K:
+		case BPF_S_JMP_JLT_X:
+			true_cond = COND_LT;
+			goto cond_branch;
+		case BPF_S_JMP_JLE_K:
+		case BPF_S_JMP_JLE_X:
+			true_cond = COND_LE;
+			goto cond_branch;
 		case BPF_S_JMP_JEQ_K:
 		case BPF_S_JMP_JEQ_X:
 			true_cond = COND_EQ;
@@ -503,6 +511,8 @@ static int bpf_jit_build_body(struct sk_filter *fp, u32 *image,
 			switch (filter[i].code) {
 			case BPF_S_JMP_JGT_X:
 			case BPF_S_JMP_JGE_X:
+			case BPF_S_JMP_JLT_X:
+			case BPF_S_JMP_JLE_X:
 			case BPF_S_JMP_JEQ_X:
 				ctx->seen |= SEEN_XREG;
 				PPC_CMPLW(r_A, r_X);
@@ -514,6 +524,8 @@ static int bpf_jit_build_body(struct sk_filter *fp, u32 *image,
 			case BPF_S_JMP_JEQ_K:
 			case BPF_S_JMP_JGT_K:
 			case BPF_S_JMP_JGE_K:
+			case BPF_S_JMP_JLT_K:
+			case BPF_S_JMP_JLE_K:
 				if (K < 32768)
 					PPC_CMPLWI(r_A, K);
 				else {
-- 
1.7.11.7

[PATCH net-next 5/8] net: bpf: add neq jump operations to bpf machine

[Daniel Borkmann]

This patch adds jump operations for neq (!=) that compare A
with K resp. X in order to facilitate filter programming with
conditional jumps, since currently only eq (==) is present in
the BPF machine. For user-space filter programming / compilers,
it might be good to also have this complementary operation.
They don't need to be as ancillary, since they fit into the
instruction encoding directly. Follow-up BPF JIT patches are
welcomed.

Signed-off-by: Daniel Borkmann <dborkman@redhat.com>
---
 include/linux/filter.h      |  2 ++
 include/uapi/linux/filter.h |  1 +
 net/core/filter.c           | 14 ++++++++++++++
 3 files changed, 17 insertions(+)

diff --git a/include/linux/filter.h b/include/linux/filter.h
index 36630bc..256c01f 100644
--- a/include/linux/filter.h
+++ b/include/linux/filter.h
@@ -105,6 +105,8 @@ enum {
 	BPF_S_JMP_JA,
 	BPF_S_JMP_JEQ_K,
 	BPF_S_JMP_JEQ_X,
+	BPF_S_JMP_JNEQ_K,
+	BPF_S_JMP_JNEQ_X,
 	BPF_S_JMP_JGE_K,
 	BPF_S_JMP_JGE_X,
 	BPF_S_JMP_JGT_K,
diff --git a/include/uapi/linux/filter.h b/include/uapi/linux/filter.h
index 3ebcc2e..d909a6f 100644
--- a/include/uapi/linux/filter.h
+++ b/include/uapi/linux/filter.h
@@ -80,6 +80,7 @@ struct sock_fprog {	/* Required for SO_ATTACH_FILTER. */
 #define         BPF_JSET        0x40
 #define         BPF_JLT         0x50
 #define         BPF_JLE         0x60
+#define         BPF_JNEQ        0x70
 
 #define BPF_SRC(code)   ((code) & 0x08)
 #define         BPF_K           0x00
diff --git a/net/core/filter.c b/net/core/filter.c
index 2122eba..b360fb3 100644
--- a/net/core/filter.c
+++ b/net/core/filter.c
@@ -228,6 +228,9 @@ unsigned int sk_run_filter(const struct sk_buff *skb,
 		case BPF_S_JMP_JEQ_K:
 			fentry += (A == K) ? fentry->jt : fentry->jf;
 			continue;
+		case BPF_S_JMP_JNEQ_K:
+			fentry += (A != K) ? fentry->jt : fentry->jf;
+			continue;
 		case BPF_S_JMP_JSET_K:
 			fentry += (A & K) ? fentry->jt : fentry->jf;
 			continue;
@@ -246,6 +249,9 @@ unsigned int sk_run_filter(const struct sk_buff *skb,
 		case BPF_S_JMP_JEQ_X:
 			fentry += (A == X) ? fentry->jt : fentry->jf;
 			continue;
+		case BPF_S_JMP_JNEQ_X:
+			fentry += (A != X) ? fentry->jt : fentry->jf;
+			continue;
 		case BPF_S_JMP_JSET_X:
 			fentry += (A & X) ? fentry->jt : fentry->jf;
 			continue;
@@ -454,6 +460,8 @@ static int check_load_and_stores(struct sock_filter *filter, int flen)
 			break;
 		case BPF_S_JMP_JEQ_K:
 		case BPF_S_JMP_JEQ_X:
+		case BPF_S_JMP_JNEQ_K:
+		case BPF_S_JMP_JNEQ_X:
 		case BPF_S_JMP_JGE_K:
 		case BPF_S_JMP_JGE_X:
 		case BPF_S_JMP_JGT_K:
@@ -540,6 +548,8 @@ int sk_chk_filter(struct sock_filter *filter, unsigned int flen)
 		[BPF_JMP|BPF_JA]         = BPF_S_JMP_JA,
 		[BPF_JMP|BPF_JEQ|BPF_K]  = BPF_S_JMP_JEQ_K,
 		[BPF_JMP|BPF_JEQ|BPF_X]  = BPF_S_JMP_JEQ_X,
+		[BPF_JMP|BPF_JNEQ|BPF_K] = BPF_S_JMP_JNEQ_K,
+		[BPF_JMP|BPF_JNEQ|BPF_X] = BPF_S_JMP_JNEQ_X,
 		[BPF_JMP|BPF_JGE|BPF_K]  = BPF_S_JMP_JGE_K,
 		[BPF_JMP|BPF_JGE|BPF_X]  = BPF_S_JMP_JGE_X,
 		[BPF_JMP|BPF_JGT|BPF_K]  = BPF_S_JMP_JGT_K,
@@ -599,6 +609,8 @@ int sk_chk_filter(struct sock_filter *filter, unsigned int flen)
 			break;
 		case BPF_S_JMP_JEQ_K:
 		case BPF_S_JMP_JEQ_X:
+		case BPF_S_JMP_JNEQ_K:
+		case BPF_S_JMP_JNEQ_X:
 		case BPF_S_JMP_JGE_K:
 		case BPF_S_JMP_JGE_X:
 		case BPF_S_JMP_JGT_K:
@@ -852,6 +864,8 @@ static void sk_decode_filter(struct sock_filter *filt, struct sock_filter *to)
 		[BPF_S_JMP_JA]		= BPF_JMP|BPF_JA,
 		[BPF_S_JMP_JEQ_K]	= BPF_JMP|BPF_JEQ|BPF_K,
 		[BPF_S_JMP_JEQ_X]	= BPF_JMP|BPF_JEQ|BPF_X,
+		[BPF_S_JMP_JNEQ_K]	= BPF_JMP|BPF_JNEQ|BPF_K,
+		[BPF_S_JMP_JNEQ_X]	= BPF_JMP|BPF_JNEQ|BPF_X,
 		[BPF_S_JMP_JGE_K]	= BPF_JMP|BPF_JGE|BPF_K,
 		[BPF_S_JMP_JGE_X]	= BPF_JMP|BPF_JGE|BPF_X,
 		[BPF_S_JMP_JGT_K]	= BPF_JMP|BPF_JGT|BPF_K,
-- 
1.7.11.7

[PATCH net-next 7/8] sparc: bpf_jit_comp: add JMP_NEQ instructions for BPF JIT

[Daniel Borkmann]

This patch is a follow-up for patch "net: bpf: add neq jump
operations to bpf machine" that implements BPF Sparc JIT parts
for the BPF JMP_NEQ operation.

Signed-off-by: Daniel Borkmann <dborkman@redhat.com>
---
 arch/sparc/net/bpf_jit_comp.c | 4 ++++
 1 file changed, 4 insertions(+)

diff --git a/arch/sparc/net/bpf_jit_comp.c b/arch/sparc/net/bpf_jit_comp.c
index f5b4fc9..5da318c 100644
--- a/arch/sparc/net/bpf_jit_comp.c
+++ b/arch/sparc/net/bpf_jit_comp.c
@@ -694,12 +694,14 @@ common_load_ind:		seen |= SEEN_DATAREF | SEEN_XREG;
 			COND_SEL(BPF_S_JMP_JLT_K, BLU, BGEU);
 			COND_SEL(BPF_S_JMP_JLE_K, BLEU, BGU);
 			COND_SEL(BPF_S_JMP_JEQ_K, BE, BNE);
+			COND_SEL(BPF_S_JMP_JNEQ_K, BNE, BE);
 			COND_SEL(BPF_S_JMP_JSET_K, BNE, BE);
 			COND_SEL(BPF_S_JMP_JGT_X, BGU, BLEU);
 			COND_SEL(BPF_S_JMP_JGE_X, BGEU, BLU);
 			COND_SEL(BPF_S_JMP_JLT_X, BLU, BGEU);
 			COND_SEL(BPF_S_JMP_JLE_X, BLEU, BGU);
 			COND_SEL(BPF_S_JMP_JEQ_X, BE, BNE);
+			COND_SEL(BPF_S_JMP_JNEQ_X, BNE, BE);
 			COND_SEL(BPF_S_JMP_JSET_X, BNE, BE);
 
 cond_branch:			f_offset = addrs[i + filter[i].jf];
@@ -718,6 +720,7 @@ cond_branch:			f_offset = addrs[i + filter[i].jf];
 				case BPF_S_JMP_JLT_X:
 				case BPF_S_JMP_JLE_X:
 				case BPF_S_JMP_JEQ_X:
+				case BPF_S_JMP_JNEQ_X:
 					seen |= SEEN_XREG;
 					emit_cmp(r_A, r_X);
 					break;
@@ -726,6 +729,7 @@ cond_branch:			f_offset = addrs[i + filter[i].jf];
 					emit_btst(r_A, r_X);
 					break;
 				case BPF_S_JMP_JEQ_K:
+				case BPF_S_JMP_JNEQ_K:
 				case BPF_S_JMP_JGT_K:
 				case BPF_S_JMP_JGE_K:
 				case BPF_S_JMP_JLT_K:
-- 
1.7.11.7

[PATCH net-next 8/8] PPC: bpf_jit_comp: add JMP_NEQ instructions for BPF JIT

[Daniel Borkmann]

This patch is a follow-up for patch "net: bpf: add neq jump
operations to bpf machine" that implements BPF PowerPC JIT
parts for the BPF JMP_NEQ operation.

Cc: Matt Evans <matt@ozlabs.org>
Signed-off-by: Daniel Borkmann <dborkman@redhat.com>
---
 arch/powerpc/net/bpf_jit_comp.c | 4 ++++
 1 file changed, 4 insertions(+)

diff --git a/arch/powerpc/net/bpf_jit_comp.c b/arch/powerpc/net/bpf_jit_comp.c
index 46b4d21..4b9ee59 100644
--- a/arch/powerpc/net/bpf_jit_comp.c
+++ b/arch/powerpc/net/bpf_jit_comp.c
@@ -496,6 +496,8 @@ static int bpf_jit_build_body(struct sk_filter *fp, u32 *image,
 		case BPF_S_JMP_JEQ_X:
 			true_cond = COND_EQ;
 			goto cond_branch;
+		case BPF_S_JMP_JNEQ_K:
+		case BPF_S_JMP_JNEQ_X:
 		case BPF_S_JMP_JSET_K:
 		case BPF_S_JMP_JSET_X:
 			true_cond = COND_NE;
@@ -514,6 +516,7 @@ static int bpf_jit_build_body(struct sk_filter *fp, u32 *image,
 			case BPF_S_JMP_JLT_X:
 			case BPF_S_JMP_JLE_X:
 			case BPF_S_JMP_JEQ_X:
+			case BPF_S_JMP_JNEQ_X:
 				ctx->seen |= SEEN_XREG;
 				PPC_CMPLW(r_A, r_X);
 				break;
@@ -522,6 +525,7 @@ static int bpf_jit_build_body(struct sk_filter *fp, u32 *image,
 				PPC_AND_DOT(r_scratch1, r_A, r_X);
 				break;
 			case BPF_S_JMP_JEQ_K:
+			case BPF_S_JMP_JNEQ_K:
 			case BPF_S_JMP_JGT_K:
 			case BPF_S_JMP_JGE_K:
 			case BPF_S_JMP_JLT_K:
-- 
1.7.11.7

[PATCH net-next 6/8] x86: bpf_jit_comp: add JMP_NEQ instructions for BPF JIT

[Daniel Borkmann]

This patch is a follow-up for patch "net: bpf: add neq jump
operations to bpf machine" that implements BPF x86 JIT parts
for the BPF JMP_NEQ operation.

Cc: Eric Dumazet <eric.dumazet@gmail.com>
Signed-off-by: Daniel Borkmann <dborkman@redhat.com>
---
 arch/x86/net/bpf_jit_comp.c | 4 ++++
 1 file changed, 4 insertions(+)

diff --git a/arch/x86/net/bpf_jit_comp.c b/arch/x86/net/bpf_jit_comp.c
index 6d6a4ce..bd10c83 100644
--- a/arch/x86/net/bpf_jit_comp.c
+++ b/arch/x86/net/bpf_jit_comp.c
@@ -587,12 +587,14 @@ common_load_ind:		seen |= SEEN_DATAREF | SEEN_XREG;
 			COND_SEL(BPF_S_JMP_JLT_K, X86_JB, X86_JAE);
 			COND_SEL(BPF_S_JMP_JLE_K, X86_JBE, X86_JA);
 			COND_SEL(BPF_S_JMP_JEQ_K, X86_JE, X86_JNE);
+			COND_SEL(BPF_S_JMP_JNEQ_K,X86_JNE, X86_JE);
 			COND_SEL(BPF_S_JMP_JSET_K,X86_JNE, X86_JE);
 			COND_SEL(BPF_S_JMP_JGT_X, X86_JA, X86_JBE);
 			COND_SEL(BPF_S_JMP_JGE_X, X86_JAE, X86_JB);
 			COND_SEL(BPF_S_JMP_JLT_X, X86_JB, X86_JAE);
 			COND_SEL(BPF_S_JMP_JLE_X, X86_JBE, X86_JA);
 			COND_SEL(BPF_S_JMP_JEQ_X, X86_JE, X86_JNE);
+			COND_SEL(BPF_S_JMP_JNEQ_X,X86_JNE, X86_JE);
 			COND_SEL(BPF_S_JMP_JSET_X,X86_JNE, X86_JE);
 
 cond_branch:			f_offset = addrs[i + filter[i].jf] - addrs[i];
@@ -610,6 +612,7 @@ cond_branch:			f_offset = addrs[i + filter[i].jf] - addrs[i];
 				case BPF_S_JMP_JLT_X:
 				case BPF_S_JMP_JLE_X:
 				case BPF_S_JMP_JEQ_X:
+				case BPF_S_JMP_JNEQ_X:
 					seen |= SEEN_XREG;
 					EMIT2(0x39, 0xd8); /* cmp %ebx,%eax */
 					break;
@@ -618,6 +621,7 @@ cond_branch:			f_offset = addrs[i + filter[i].jf] - addrs[i];
 					EMIT2(0x85, 0xd8); /* test %ebx,%eax */
 					break;
 				case BPF_S_JMP_JEQ_K:
+				case BPF_S_JMP_JNEQ_K:
 					if (K == 0) {
 						EMIT2(0x85, 0xc0); /* test   %eax,%eax */
 						break;
-- 
1.7.11.7

Re: [PATCH net-next 0/8] Add complementary BPF conditional jump instructions

[David Miller]

From: Daniel Borkmann <dborkman@redhat.com>
Date: Mon, 31 Dec 2012 14:59:40 +0100

> This set adds adds jump operations for lt (<), le (<=), ne (!=) that
> compare A with K resp. X in order to facilitate filter programming
> with conditional jumps, as also available in McCanne et. al's BPF+
> paper (``BPF+: Exploiting Global Data-flow Optimization in a Generalized
> Packet Filter Architecture'').
> 
> Also, follow-up BPF JIT implementations for x86, Sparc and PowerPC
> are added in this set.

Whilst I agree that adding NE jumps adds great value and closes a
serious gap, the rest can be synthesized by simply swapping the
arguments and using a comparison that does already exist.

Why isn't that sufficient?

Re: [PATCH net-next 5/8] net: bpf: add neq jump operations to bpf machine

[Eric Dumazet]

On Mon, 2012-12-31 at 14:59 +0100, Daniel Borkmann wrote:
> This patch adds jump operations for neq (!=) that compare A
> with K resp. X in order to facilitate filter programming with
> conditional jumps, since currently only eq (==) is present in
> the BPF machine. For user-space filter programming / compilers,
> it might be good to also have this complementary operation.
> They don't need to be as ancillary, since they fit into the
> instruction encoding directly. Follow-up BPF JIT patches are
> welcomed.
> 
> Signed-off-by: Daniel Borkmann <dborkman@redhat.com>
> ---
>  include/linux/filter.h      |  2 ++
>  include/uapi/linux/filter.h |  1 +
>  net/core/filter.c           | 14 ++++++++++++++
>  3 files changed, 17 insertions(+)
> 
> diff --git a/include/linux/filter.h b/include/linux/filter.h
> index 36630bc..256c01f 100644
> --- a/include/linux/filter.h
> +++ b/include/linux/filter.h
> @@ -105,6 +105,8 @@ enum {
>  	BPF_S_JMP_JA,
>  	BPF_S_JMP_JEQ_K,
>  	BPF_S_JMP_JEQ_X,
> +	BPF_S_JMP_JNEQ_K,
> +	BPF_S_JMP_JNEQ_X,
>  	BPF_S_JMP_JGE_K,
>  	BPF_S_JMP_JGE_X,
>  	BPF_S_JMP_JGT_K,
> diff --git a/include/uapi/linux/filter.h b/include/uapi/linux/filter.h
> index 3ebcc2e..d909a6f 100644
> --- a/include/uapi/linux/filter.h
> +++ b/include/uapi/linux/filter.h
> @@ -80,6 +80,7 @@ struct sock_fprog {	/* Required for SO_ATTACH_FILTER. */
>  #define         BPF_JSET        0x40
>  #define         BPF_JLT         0x50
>  #define         BPF_JLE         0x60
> +#define         BPF_JNEQ        0x70
>  
>  #define BPF_SRC(code)   ((code) & 0x08)
>  #define         BPF_K           0x00
> diff --git a/net/core/filter.c b/net/core/filter.c
> index 2122eba..b360fb3 100644
> --- a/net/core/filter.c
> +++ b/net/core/filter.c
> @@ -228,6 +228,9 @@ unsigned int sk_run_filter(const struct sk_buff *skb,
>  		case BPF_S_JMP_JEQ_K:
>  			fentry += (A == K) ? fentry->jt : fentry->jf;
>  			continue;
> +		case BPF_S_JMP_JNEQ_K:
> +			fentry += (A != K) ? fentry->jt : fentry->jf;
> +			continue;
>  		case BPF_S_JMP_JSET_K:
>  			fentry += (A & K) ? fentry->jt : fentry->jf;
>  			continue;

This makes no sense at all to me, it seems kernel bloat.

The JNE instruction already exists.

You only have to take the JEQ (jt,jf) and swap the jt/jf targets.

Re: [PATCH net-next 0/8] Add complementary BPF conditional jump instructions

[Eric Dumazet]

On Mon, 2012-12-31 at 14:37 -0800, David Miller wrote:

> Whilst I agree that adding NE jumps adds great value and closes a
> serious gap, the rest can be synthesized by simply swapping the
> arguments and using a comparison that does already exist.
> 
> Why isn't that sufficient?

I am afraid none of these patches is needed at all.

Swapping the jt/jf is plainly enough for the user land compiler.

libcap seems to do it already

# tcpdump -i lo 'len!=0 && ip6' -d
(000) ld       #pktlen
(001) jeq      #0x0             jt 5	jf 2
(002) ldh      [12]
(003) jeq      #0x86dd          jt 4	jf 5
(004) ret      #96
(005) ret      #0
# tcpdump -i lo 'len==0 && ip6' -d
(000) ld       #pktlen
(001) jeq      #0x0             jt 2	jf 5
(002) ldh      [12]
(003) jeq      #0x86dd          jt 4	jf 5
(004) ret      #96
(005) ret      #0

Re: [PATCH net-next 0/8] Add complementary BPF conditional jump instructions

[David Miller]

From: Eric Dumazet <eric.dumazet@gmail.com>
Date: Mon, 31 Dec 2012 19:29:02 -0800

> On Mon, 2012-12-31 at 14:37 -0800, David Miller wrote:
> 
>> Whilst I agree that adding NE jumps adds great value and closes a
>> serious gap, the rest can be synthesized by simply swapping the
>> arguments and using a comparison that does already exist.
>> 
>> Why isn't that sufficient?
> 
> I am afraid none of these patches is needed at all.
> 
> Swapping the jt/jf is plainly enough for the user land compiler.
> 
> libcap seems to do it already

Agreed.

Re: [PATCH net-next 0/8] Add complementary BPF conditional jump instructions

[Daniel Borkmann]

On Tue, Jan 1, 2013 at 6:18 AM, David Miller <davem@davemloft.net> wrote:
> From: Eric Dumazet <eric.dumazet@gmail.com>
> Date: Mon, 31 Dec 2012 19:29:02 -0800
>
>> On Mon, 2012-12-31 at 14:37 -0800, David Miller wrote:
>>
>>> Whilst I agree that adding NE jumps adds great value and closes a
>>> serious gap, the rest can be synthesized by simply swapping the
>>> arguments and using a comparison that does already exist.
>>>
>>> Why isn't that sufficient?
>>
>> I am afraid none of these patches is needed at all.
>>
>> Swapping the jt/jf is plainly enough for the user land compiler.
>>
>> libcap seems to do it already
>
> Agreed.

Fair enough, it's probably better to let this be done by user space
via such a hack than adding the actual operations for this.