Skip to contentSkip to conversation

Add complementary BPF conditional jump instructions

PATCH In review Daniel Borkmann 4 participants 14 messages Dec 31, 2012 – Jan 2, 2013

Subsystems (11)
Networking Network drivers x86 PowerPC +7 more subsystems
lore
Share & tools
lore

Daniel Borkmann

author
#0 lore raw

cover Add complementary BPF conditional jump instructions

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(+)
Signature · 1 line
1.7.11.7
author
#1 lore raw

PATCH 1/8 net: bpf: add lt,le jump operations to bpf machine

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 <[email protected]>
---
 include/linux/filter.h      |  4 ++++
 include/uapi/linux/filter.h |  3 +++
 net/core/filter.c           | 28 ++++++++++++++++++++++++++++
 3 files changed, 35 insertions(+)
include/linux/filter.h +4 -0
index c45eabc..36630bc 100644
@@ -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 */
include/uapi/linux/filter.h +3 -0
index 9cfde69..3ebcc2e 100644
@@ -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
net/core/filter.c +28 -0
index 2ead2a9..2122eba 100644
@@ -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,
 	};
Signature · 1 line
1.7.11.7
author
#2 lore raw

PATCH 2/8 x86: bpf_jit_comp: add JMP instructions for BPF JIT

In reply to 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 <[email protected]>
Signed-off-by Daniel Borkmann <[email protected]>
---
 arch/x86/net/bpf_jit_comp.c | 8 ++++++++
 1 file changed, 8 insertions(+)
arch/x86/net/bpf_jit_comp.c +8 -0
index d11a470..6d6a4ce 100644
@@ -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
Signature · 1 line
1.7.11.7
author
#3 lore raw

PATCH 3/8 sparc: bpf_jit_comp: add JMP instructions for BPF JIT

In reply to 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 <[email protected]>
---
 arch/sparc/net/bpf_jit_comp.c | 8 ++++++++
 1 file changed, 8 insertions(+)
arch/sparc/net/bpf_jit_comp.c +8 -0
index 3109ca6..f5b4fc9 100644
@@ -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 {
Signature · 1 line
1.7.11.7
author
#5 lore raw

PATCH 5/8 net: bpf: add neq jump operations to bpf machine

In reply to 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 <[email protected]>
---
 include/linux/filter.h      |  2 ++
 include/uapi/linux/filter.h |  1 +
 net/core/filter.c           | 14 ++++++++++++++
 3 files changed, 17 insertions(+)
include/linux/filter.h +2 -0
index 36630bc..256c01f 100644
@@ -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,
include/uapi/linux/filter.h +1 -0
index 3ebcc2e..d909a6f 100644
@@ -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
net/core/filter.c +14 -0
index 2122eba..b360fb3 100644
@@ -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,
Signature · 1 line
1.7.11.7
author
#4 lore raw

PATCH 4/8 PPC: bpf_jit_comp: add JMP instructions for BPF JIT

In reply to 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 <[email protected]>
Signed-off-by Daniel Borkmann <[email protected]>
---
 arch/powerpc/net/bpf_jit.h      |  1 +
 arch/powerpc/net/bpf_jit_comp.c | 12 ++++++++++++
 2 files changed, 13 insertions(+)
arch/powerpc/net/bpf_jit.h +1 -0
index 8a5dfaf..f105b3b 100644
@@ -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 */
arch/powerpc/net/bpf_jit_comp.c +12 -0
index e834f1e..46b4d21 100644
@@ -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 {
Signature · 1 line
1.7.11.7
author
#9 lore raw

PATCH 8/8 PPC: bpf_jit_comp: add JMP_NEQ instructions for BPF JIT

In reply to 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 <[email protected]>
Signed-off-by Daniel Borkmann <[email protected]>
---
 arch/powerpc/net/bpf_jit_comp.c | 4 ++++
 1 file changed, 4 insertions(+)
arch/powerpc/net/bpf_jit_comp.c +4 -0
index 46b4d21..4b9ee59 100644
@@ -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:
Signature · 1 line
1.7.11.7
author
#8 lore raw

PATCH 7/8 sparc: bpf_jit_comp: add JMP_NEQ instructions for BPF JIT

In reply to 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 <[email protected]>
---
 arch/sparc/net/bpf_jit_comp.c | 4 ++++
 1 file changed, 4 insertions(+)
arch/sparc/net/bpf_jit_comp.c +4 -0
index f5b4fc9..5da318c 100644
@@ -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:
Signature · 1 line
1.7.11.7
author
#7 lore raw

PATCH 6/8 x86: bpf_jit_comp: add JMP_NEQ instructions for BPF JIT

In reply to 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 <[email protected]>
Signed-off-by Daniel Borkmann <[email protected]>
---
 arch/x86/net/bpf_jit_comp.c | 4 ++++
 1 file changed, 4 insertions(+)
arch/x86/net/bpf_jit_comp.c +4 -0
index 6d6a4ce..bd10c83 100644
@@ -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;
Signature · 1 line
1.7.11.7
maintainer
#10 lore raw
In reply to Daniel Borkmann

From: Daniel Borkmann <[email protected]>
Date: Mon, 31 Dec 2012 14:59:40 +0100

Quoted 8 lines

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?

#6 lore raw

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

In reply to Daniel Borkmann
Quoted 46 lines · 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 <[email protected]>
---
 include/linux/filter.h      |  2 ++
 include/uapi/linux/filter.h |  1 +
 net/core/filter.c           | 14 ++++++++++++++
 3 files changed, 17 insertions(+)
include/linux/filter.h +2 -0
index 36630bc..256c01f 100644
@@ -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,
include/uapi/linux/filter.h +1 -0
index 3ebcc2e..d909a6f 100644
@@ -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
net/core/filter.c +0 -0
index 2122eba..b360fb3 100644

net/core/filter.c unsigned int sk_run_filter(const struct sk_buff *skb, · line 236

Quoted 9 lines
net/core/filter.c +3 -0
@@ -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.

#11 lore raw
In reply to David Miller
Quoted 5 lines · David Miller

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
maintainer
#12 lore raw

From: Eric Dumazet <[email protected]>
Date: Mon, 31 Dec 2012 19:29:02 -0800

Quoted 6 lines · David Miller
Quoted 5 lines

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.

Quoted 7 lines
Quoted 1 line

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.

#13 lore raw
Quoted 11 lines · David Miller

From: Eric Dumazet <[email protected]>
Date: Mon, 31 Dec 2012 19:29:02 -0800

Quoted 8 lines · David Miller
Quoted 6 lines

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?

Quoted 7 lines
Quoted 5 lines

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.