bpf jit drops the ball on negative memory references

Consider the following test program:

#include <stdio.h>
#include <sys/types.h>
#include <sys/socket.h>
#include <netinet/in.h>
#include <pcap-bpf.h>

#define die(x) do {perror(x); return 1;} while (0)

struct bpf_insn udp_filter[] = {
	/*   0 */ BPF_STMT(BPF_LDX|BPF_W|BPF_IMM, -1048576+(0)), /* leax	net[0] */
	/*   1 */ BPF_STMT(BPF_LD|BPF_B|BPF_IND, 0),             /* ldb	[x+0] */
	/*   2 */ BPF_STMT(BPF_RET|BPF_A, 0),                    /* ret	a */
};

int main(int argc, char *argv[])

{
	char buf[512];
	struct sockaddr_in addr;
	struct bpf_program prg;
	socklen_t addr_s;
	ssize_t res;
	int fd;

	addr.sin_family = AF_INET;
	addr.sin_port = htons(5000);
	addr.sin_addr.s_addr = 0;
	addr_s = sizeof(addr);
	prg.bf_len = sizeof(udp_filter)/sizeof(udp_filter[0]);
	prg.bf_insns = udp_filter;
	if(-1 == (fd = socket(AF_INET, SOCK_DGRAM, 0)))
		die("socket");
	if(-1 == bind(fd, (struct sockaddr *)&addr, sizeof(addr)))
		die("bind");
	if(-1 == setsockopt(fd, SOL_SOCKET, SO_ATTACH_FILTER, &prg, sizeof(prg)))
		die("setsockopt");
	res = recvfrom(fd, buf, sizeof(buf), 0, (struct sockaddr *)&addr, &addr_s);
	if(res != -1)
		printf("packet received: %zi bytes\n", res);
	else
		die("recvfrom");
	return 0;
}

when used with the bpf jit disabled works:
console 1 $ ./bpf
console 2 $ echo "hello" | nc -u localhost 5000
console 1: packet received: 6 bytes

When the bpf jit gets enabled (echo 100 > /proc/sys/net/core/bpf_jit_enable) the same program stops working:
console 1 $ ./bpf
console 2 $ echo "hello" | nc -u localhost 5000
console 1:

The reason is that both jits (x86 and powerpc) do not handle negative memory references like SKF_NET_OFF or SKF_LL_OFF, only the simple ancillary data references are supported (by mapping to special instructions).
In the case of an absolute reference, the jit aborts the translation if a negative reference is seen, also a negative k on the indirect load aborts the translation, but if X is negative to begin with, only the error handler is reached at runtime which drops the whole packet.

Such a setup is useful to say filter bogus source addresses on an UDP socket.

I propose the following patch series to fix this situation.
Patch 1 exports the helper function the interpreter uses.
Patch 2 incorporates the helper into the x86 jit (so it depends on patch 1). Patch 3 incorporates the helper into the powerpc jit (so it depends on patch 1).

Lightly tested on x86, but the powerpc asm part is prop. wrong, could need assistance.

The function is renamed to make it a little more clear what it does. It is not added to any .h because it is not for general consumption, only for bpf internal use (and so by the jits).

@@ -40,8 +40,12 @@
 #include <linux/reciprocal_div.h>
 #include <linux/ratelimit.h>
 
-/* No hurry in this branch */
-static void *__load_pointer(const struct sk_buff *skb, int k, unsigned int size)
+/*
+ * No hurry in this branch
+ *
+ * Exported for the bpf jit load helper.
+ */
+void *bpf_internal_load_pointer_neg_helper(const struct sk_buff *skb, int k, unsigned int size)
 {
 	u8 *ptr = NULL;
 

@@ -60,7 +64,7 @@ static inline void *load_pointer(const struct sk_buff *skb, int k,
 {
 	if (k >= 0)
 		return skb_header_pointer(skb, k, size, buffer);
-	return __load_pointer(skb, k, size);
+	return bpf_internal_load_pointer_neg_helper(skb, k, size);
 }
 
 /**

Missing "---" line separator (check Documentation/SubmittingPatches line
490)

You can check http://patchwork.ozlabs.org/patch/149683/ and see there is a problem, compared to http://patchwork.ozlabs.org/patch/149441/ for example

I'd have thought it better to put in into a bfp_internal.h (or similar) with a big warning there about the asm users.

Possibly even worth adding some other defs that the asm files will need (if there are any).

David

Hmmm, OK, where would i put the .h? Right there under ./include/linux/?

There is at least one other define, the lowest negative address range, but it would be a copy of the same define in filter.h, or i would have to massage filter.h to make it fit for inclusion by assembly. So I'm unsure how to proceed.

Greetings
Jan

An IPv4 address space walks into a bar: "A strong CIDR please. I'm
exhausted."

From: Jan Seiffert <[email protected]>
Date: Fri, 30 Mar 2012 17:08:19 +0200

Applied but with comment formatting fixed up:

Like this:

Thanks David!

I was planning on a V5 for the little things i did wrong (wrong patch separator, etc.) but wanted to wait a little more for more feedback.

Is that the preferred comment style in net/ ? Coding style says first line empty. Or just to match the rest of the file?

Greetings
Jan

From: Jan Seiffert <[email protected]>
Date: Wed, 4 Apr 2012 00:26:25 +0200

I'm not getting into this discussion right now, sorry.

Oh, sorry, i guess you misunderstood me.
I didn't want to discuss anything, I'm fine either way, i just wanted to know what's the rule, so i can take notes and prevent the same error in the future.

Greetings
Jan

Now the helper function from filter.c for negative offsets is exported, it can be used it in the jit to handle negative offsets.

First modify the asm load helper functions to handle:
- know positive offsets
- know negative offsets
- any offset

then the compiler can be modified to explicitly use these helper when appropriate.

This fixes the case of a negative X register and allows to lift the restriction that bpf programs with negative offsets can't be jited.

index 6687022..2897d7f 100644
@@ -18,17 +18,17 @@
  * r9d : hlen = skb->len - skb->data_len
  */
 #define SKBDATA	%r8
-
-sk_load_word_ind:
-	.globl	sk_load_word_ind
-
-	add	%ebx,%esi	/* offset += X */
-#	test    %esi,%esi	/* if (offset < 0) goto bpf_error; */
-	js	bpf_error
+#define SKF_MAX_NEG_OFF    $(-0x200000) /* SKF_LL_OFF from filter.h */
 
 sk_load_word:
 	.globl	sk_load_word
 
+	test	%esi,%esi
+	js	bpf_slow_path_word_neg
+
+sk_load_word_positive_offset:
+	.globl	sk_load_word_positive_offset
+
 	mov	%r9d,%eax		# hlen
 	sub	%esi,%eax		# hlen - offset
 	cmp	$3,%eax

@@ -37,16 +37,15 @@ sk_load_word:
 	bswap   %eax  			/* ntohl() */
 	ret
 
-
-sk_load_half_ind:
-	.globl sk_load_half_ind
-
-	add	%ebx,%esi	/* offset += X */
-	js	bpf_error
-
 sk_load_half:
 	.globl	sk_load_half
 
+	test	%esi,%esi
+	js	bpf_slow_path_half_neg
+
+sk_load_half_positive_offset:
+	.globl	sk_load_half_positive_offset
+
 	mov	%r9d,%eax
 	sub	%esi,%eax		#	hlen - offset
 	cmp	$1,%eax

@@ -55,14 +54,15 @@ sk_load_half:
 	rol	$8,%ax			# ntohs()
 	ret
 
-sk_load_byte_ind:
-	.globl sk_load_byte_ind
-	add	%ebx,%esi	/* offset += X */
-	js	bpf_error
-
 sk_load_byte:
 	.globl	sk_load_byte
 
+	test	%esi,%esi
+	js	bpf_slow_path_byte_neg
+
+sk_load_byte_positive_offset:
+	.globl	sk_load_byte_positive_offset
+
 	cmp	%esi,%r9d   /* if (offset >= hlen) goto bpf_slow_path_byte */
 	jle	bpf_slow_path_byte
 	movzbl	(SKBDATA,%rsi),%eax

@@ -73,25 +73,21 @@ sk_load_byte:
  *
  * Implements BPF_S_LDX_B_MSH : ldxb  4*([offset]&0xf)
  * Must preserve A accumulator (%eax)
- * Inputs : %esi is the offset value, already known positive
+ * Inputs : %esi is the offset value
  */
-ENTRY(sk_load_byte_msh)
-	CFI_STARTPROC
+sk_load_byte_msh:
+	.globl	sk_load_byte_msh
+	test	%esi,%esi
+	js	bpf_slow_path_byte_msh_neg
+
+sk_load_byte_msh_positive_offset:
+	.globl	sk_load_byte_msh_positive_offset
 	cmp	%esi,%r9d      /* if (offset >= hlen) goto bpf_slow_path_byte_msh */
 	jle	bpf_slow_path_byte_msh
 	movzbl	(SKBDATA,%rsi),%ebx
 	and	$15,%bl
 	shl	$2,%bl
 	ret
-	CFI_ENDPROC
-ENDPROC(sk_load_byte_msh)
-
-bpf_error:
-# force a return 0 from jit handler
-	xor		%eax,%eax
-	mov		-8(%rbp),%rbx
-	leaveq
-	ret
 
 /* rsi contains offset and can be scratched */
 #define bpf_slow_path_common(LEN)		\

@@ -138,3 +134,68 @@ bpf_slow_path_byte_msh:
 	shl	$2,%al
 	xchg	%eax,%ebx
 	ret
+
+#define sk_negative_common(SIZE)				\
+	push	%rdi;	/* save skb */				\
+	push	%r9;						\
+	push	SKBDATA;					\
+/* rsi already has offset */					\
+	mov	$SIZE,%ecx;	/* size */			\
+	call	bpf_internal_load_pointer_neg_helper;		\
+	test	%rax,%rax;					\
+	pop	SKBDATA;					\
+	pop	%r9;						\
+	pop	%rdi;						\
+	jz	bpf_error
+
+
+bpf_slow_path_word_neg:
+	cmp	SKF_MAX_NEG_OFF, %esi	/* test range */
+	jl	bpf_error	/* offset lower -> error  */
+sk_load_word_negative_offset:
+	.globl	sk_load_word_negative_offset
+	sk_negative_common(4)
+	mov	(%rax), %eax
+	bswap	%eax
+	ret
+
+bpf_slow_path_half_neg:
+	cmp	SKF_MAX_NEG_OFF, %esi
+	jl	bpf_error
+sk_load_half_negative_offset:
+	.globl	sk_load_half_negative_offset
+	sk_negative_common(2)
+	mov	(%rax),%ax
+	rol	$8,%ax
+	movzwl	%ax,%eax
+	ret
+
+bpf_slow_path_byte_neg:
+	cmp	SKF_MAX_NEG_OFF, %esi
+	jl	bpf_error
+sk_load_byte_negative_offset:
+	.globl	sk_load_byte_negative_offset
+	sk_negative_common(1)
+	movzbl	(%rax), %eax
+	ret
+
+bpf_slow_path_byte_msh_neg:
+	cmp	SKF_MAX_NEG_OFF, %esi
+	jl	bpf_error
+sk_load_byte_msh_negative_offset:
+	.globl	sk_load_byte_msh_negative_offset
+	xchg	%eax,%ebx /* dont lose A , X is about to be scratched */
+	sk_negative_common(1)
+	movzbl	(%rax),%eax
+	and	$15,%al
+	shl	$2,%al
+	xchg	%eax,%ebx
+	ret
+
+bpf_error:
+# force a return 0 from jit handler
+	xor		%eax,%eax
+	mov		-8(%rbp),%rbx
+	leaveq
+	ret
+

Nice work Jan, thanks a lot.

From: Jan Seiffert <[email protected]>
Date: Fri, 30 Mar 2012 17:24:05 +0200

Applied, but with trailing empty lines removed:

Now the helper function from filter.c for negative offsets is exported, it can be used it in the jit to handle negative offsets.

First modify the asm load helper functions to handle:
- know positive offsets
- know negative offsets
- any offset

then the compiler can be modified to explicitly use these helper when appropriate.

This fixes the case of a negative X register and allows to lift the restriction that bpf programs with negative offsets can't be jited.

I have only compile tested this, -ENOHARDWARE.
Can someone with more powerpc kung-fu review and maybe test this? Esp. powerpc asm is not my strong point. I think i botched the stack frame in the call setup. Help?

index ff4506e..e590aa5 100644
@@ -31,14 +31,13 @@
  * then branch directly to slow_path_XXX if required.  (In fact, could
  * load a spare GPR with the address of slow_path_generic and pass size
  * as an argument, making the call site a mtlr, li and bllr.)
- *
- * Technically, the "is addr < 0" check is unnecessary & slowing down
- * the ABS path, as it's statically checked on generation.
  */
 	.globl	sk_load_word
 sk_load_word:
 	cmpdi	r_addr, 0
-	blt	bpf_error
+	blt	bpf_slow_path_word_neg
+	.globl	sk_load_word_positive_offset
+sk_load_word_positive_offset:
 	/* Are we accessing past headlen? */
 	subi	r_scratch1, r_HL, 4
 	cmpd	r_scratch1, r_addr

@@ -51,7 +50,9 @@ sk_load_word:
 	.globl	sk_load_half
 sk_load_half:
 	cmpdi	r_addr, 0
-	blt	bpf_error
+	blt	bpf_slow_path_half_neg
+	.globl	sk_load_half_positive_offset
+sk_load_half_positive_offset:
 	subi	r_scratch1, r_HL, 2
 	cmpd	r_scratch1, r_addr
 	blt	bpf_slow_path_half

@@ -61,7 +62,9 @@ sk_load_half:
 	.globl	sk_load_byte
 sk_load_byte:
 	cmpdi	r_addr, 0
-	blt	bpf_error
+	blt	bpf_slow_path_byte_neg
+	.globl	sk_load_byte_positive_offset
+sk_load_byte_positive_offset:
 	cmpd	r_HL, r_addr
 	ble	bpf_slow_path_byte
 	lbzx	r_A, r_D, r_addr

@@ -69,22 +72,20 @@ sk_load_byte:
 
 /*
  * BPF_S_LDX_B_MSH: ldxb  4*([offset]&0xf)
- * r_addr is the offset value, already known positive
+ * r_addr is the offset value
  */
 	.globl sk_load_byte_msh
 sk_load_byte_msh:
+	cmpdi	r_addr, 0
+	blt	bpf_slow_path_byte_msh_neg
+	.globl sk_load_byte_msh_positive_offset
+sk_load_byte_msh_positive_offset:
 	cmpd	r_HL, r_addr
 	ble	bpf_slow_path_byte_msh
 	lbzx	r_X, r_D, r_addr
 	rlwinm	r_X, r_X, 2, 32-4-2, 31-2
 	blr
 
-bpf_error:
-	/* Entered with cr0 = lt */
-	li	r3, 0
-	/* Generated code will 'blt epilogue', returning 0. */
-	blr
-
 /* Call out to skb_copy_bits:
  * We'll need to back up our volatile regs first; we have
  * local variable space at r1+(BPF_PPC_STACK_BASIC).

@@ -136,3 +137,85 @@ bpf_slow_path_byte_msh:
 	lbz	r_X, BPF_PPC_STACK_BASIC+(2*8)(r1)
 	rlwinm	r_X, r_X, 2, 32-4-2, 31-2
 	blr
+
+/* Call out to bpf_internal_load_pointer_neg_helper:
+ * We'll need to back up our volatile regs first; we have
+ * local variable space at r1+(BPF_PPC_STACK_BASIC).
+ * Allocate a new stack frame here to remain ABI-compliant in
+ * stashing LR.
+ */
+#define sk_negative_common(SIZE)				\
+	mflr	r0;						\
+	std	r0, 16(r1);					\
+	/* R3 goes in parameter space of caller's frame */	\
+	std	r_skb, (BPF_PPC_STACKFRAME+48)(r1);		\
+	std	r_A, (BPF_PPC_STACK_BASIC+(0*8))(r1);		\
+	std	r_X, (BPF_PPC_STACK_BASIC+(1*8))(r1);		\
+	stdu	r1, -BPF_PPC_SLOWPATH_FRAME(r1);		\
+	/* R3 = r_skb, as passed */				\
+	mr	r4, r_addr;					\
+	li	r5, SIZE;					\
+	bl	bpf_internal_load_pointer_neg_helper;		\
+	/* R3 != 0 on success */				\
+	addi	r1, r1, BPF_PPC_SLOWPATH_FRAME;			\
+	ld	r0, 16(r1);					\
+	ld	r_A, (BPF_PPC_STACK_BASIC+(0*8))(r1);		\
+	ld	r_X, (BPF_PPC_STACK_BASIC+(1*8))(r1);		\
+	mtlr	r0;						\
+	cmpldi	r3, 0;						\
+	beq	bpf_error_slow;	/* cr0 = EQ */			\
+	mr	r_addr, r3;					\
+	ld	r_skb, (BPF_PPC_STACKFRAME+48)(r1);		\
+	/* Great success! */
+
+bpf_slow_path_word_neg:
+	lis     r_scratch1,-32	/* SKF_LL_OFF */
+	cmpd	r_addr, r_scratch1	/* addr < SKF_* */
+	blt	bpf_error	/* cr0 = LT */
+	.globl	sk_load_word_negative_offset
+sk_load_word_negative_offset:
+	sk_negative_common(4)
+	lwz	r_A, 0(r_addr)
+	blr
+
+bpf_slow_path_half_neg:
+	lis     r_scratch1,-32	/* SKF_LL_OFF */
+	cmpd	r_addr, r_scratch1	/* addr < SKF_* */
+	blt	bpf_error	/* cr0 = LT */
+	.globl	sk_load_half_negative_offset
+sk_load_half_negative_offset:
+	sk_negative_common(2)
+	lhz	r_A, 0(r_addr)
+	blr
+
+bpf_slow_path_byte_neg:
+	lis     r_scratch1,-32	/* SKF_LL_OFF */
+	cmpd	r_addr, r_scratch1	/* addr < SKF_* */
+	blt	bpf_error	/* cr0 = LT */
+	.globl	sk_load_byte_negative_offset
+sk_load_byte_negative_offset:
+	sk_negative_common(1)
+	lbz	r_A, 0(r_addr)
+	blr
+
+bpf_slow_path_byte_msh_neg:
+	lis     r_scratch1,-32	/* SKF_LL_OFF */
+	cmpd	r_addr, r_scratch1	/* addr < SKF_* */
+	blt	bpf_error	/* cr0 = LT */
+	.globl	sk_load_byte_msh_negative_offset
+sk_load_byte_msh_negative_offset:
+	sk_negative_common(1)
+	lbz	r_X, 0(r_addr)
+	rlwinm	r_X, r_X, 2, 32-4-2, 31-2
+	blr
+
+bpf_error_slow:
+	/* fabricate a cr0 = lt */
+	li	r_scratch1, -1
+	cmpdi	r_scratch1, 0
+bpf_error:
+	/* Entered with cr0 = lt */
+	li	r3, 0
+	/* Generated code will 'blt epilogue', returning 0. */
+	blr
+

index 73619d3..2dc8b14 100644
@@ -127,6 +127,9 @@ static void bpf_jit_build_epilogue(u32 *image, struct codegen_context *ctx)
 	PPC_BLR();
 }
 
+#define CHOOSE_LOAD_FUNC(K, func) \
+	((int)K < 0 ? ((int)K >= SKF_LL_OFF ? func##_negative_offset : func) : func##_positive_offset)
+
 /* Assemble the body code between the prologue & epilogue. */
 static int bpf_jit_build_body(struct sk_filter *fp, u32 *image,
 			      struct codegen_context *ctx,

@@ -391,21 +394,16 @@ static int bpf_jit_build_body(struct sk_filter *fp, u32 *image,
 
 			/*** Absolute loads from packet header/data ***/
 		case BPF_S_LD_W_ABS:
-			func = sk_load_word;
+			func = CHOOSE_LOAD_FUNC(K, sk_load_word);
 			goto common_load;
 		case BPF_S_LD_H_ABS:
-			func = sk_load_half;
+			func = CHOOSE_LOAD_FUNC(K, sk_load_half);
 			goto common_load;
 		case BPF_S_LD_B_ABS:
-			func = sk_load_byte;
+			func = CHOOSE_LOAD_FUNC(K, sk_load_byte);
 		common_load:
-			/*
-			 * Load from [K].  Reference with the (negative)
-			 * SKF_NET_OFF/SKF_LL_OFF offsets is unsupported.
-			 */
+			/* Load from [K]. */
 			ctx->seen |= SEEN_DATAREF;
-			if ((int)K < 0)
-				return -ENOTSUPP;
 			PPC_LI64(r_scratch1, func);
 			PPC_MTLR(r_scratch1);
 			PPC_LI32(r_addr, K);

@@ -429,7 +427,7 @@ static int bpf_jit_build_body(struct sk_filter *fp, u32 *image,
 		common_load_ind:
 			/*
 			 * Load from [X + K].  Negative offsets are tested for
-			 * in the helper functions, and result in a 'ret 0'.
+			 * in the helper functions.
 			 */
 			ctx->seen |= SEEN_DATAREF | SEEN_XREG;
 			PPC_LI64(r_scratch1, func);

@@ -443,13 +441,7 @@ static int bpf_jit_build_body(struct sk_filter *fp, u32 *image,
 			break;
 
 		case BPF_S_LDX_B_MSH:
-			/*
-			 * x86 version drops packet (RET 0) when K<0, whereas
-			 * interpreter does allow K<0 (__load_pointer, special
-			 * ancillary data).  common_load returns ENOTSUPP if K<0,
-			 * so we fall back to interpreter & filter works.
-			 */
-			func = sk_load_byte_msh;
+			func = CHOOSE_LOAD_FUNC(K, sk_load_byte_msh);
 			goto common_load;
 			break;
 

From: Jan Seiffert <[email protected]>
Date: Fri, 30 Mar 2012 17:35:01 +0200

I'm not applying this until a powerpc person tests it.

Also, we have an ARM JIT in the tree which probably needs to be fixed similarly.

Matt's having a look at powerpc

Cheers,
Ben.

Ok, he hasn't so I'll dig a bit.

No obvious wrongness (but I'm not very familiar with bpf), though I do have a comment: sk_negative_common() and bpf_slow_path_common() should be made one and single macro which takes the fallback function as an argument.

I'll mess around & try to test using Jan test case & will come back with an updated patch.

Cheers,
Ben.

Wow, hit that nasty along the way: The test program will not work on big endian machines because of a nasty difference between the kernel struct sock_fprog and libpcap struct bpf_program:

Kernel expects:

struct sock_fprog { /* Required for SO_ATTACH_FILTER. */
unsigned short len; /* Number of filter blocks */
struct sock_filter __user *filter;
};

libpcap provides:

struct bpf_program {
        u_int bf_len;
        struct bpf_insn *bf_insns;
};

Note the unsigned short vs. unsigned int there ? This totally breaks it here.

Is it expected that one can pass a struct bpf_program directly to the kernel or should it be "converted" by the library in which case it's just a bug in Jan's test program ?

Cheers,
Ben.

That would be great Benjamin!

As long as you know PPC ASM you are my man ;-)

I don't know if this is possible.
The return value is different (one returns 0 on success, the other != 0, the return value of != is needed). I didn't wanted to change to much, because i'm not fluent in ppc.

Would be great!

Greetings
Jan

A UDP packet walks into a

Ok, with the compile fix below it seems to work for me:

(Feel free to fold that into the original patch)

index af1ab5e..5c3cf2d 100644
@@ -48,7 +48,13 @@
 /*
  * Assembly helpers from arch/powerpc/net/bpf_jit.S:
  */
-extern u8 sk_load_word[], sk_load_half[], sk_load_byte[], sk_load_byte_msh[];
+#define DECLARE_LOAD_FUNC(func)	\
+	extern u8 func[], func##_negative_offset[], func##_positive_offset[]
+
+DECLARE_LOAD_FUNC(sk_load_word);
+DECLARE_LOAD_FUNC(sk_load_half);
+DECLARE_LOAD_FUNC(sk_load_byte);
+DECLARE_LOAD_FUNC(sk_load_byte_msh);
 
 #define FUNCTION_DESCR_SIZE	24
 

Cheers,
Ben.

Should i resend the complete patch with the compile fix?

[snip]

Greetings
Jan

PS: I am sure i compile tested the orig. patch here, hmmm, must have lost that part when moving trees, #GitIsNotMyFriend

en.gin.eer en-ji-nir n 1: a mechanism for converting caffeine into designs.

Won't hurt...

BTW. Any idea about that bpf_program vs. sock_fprog issue I mentioned earlier ?

Cheers,
Ben.

Ok

No idea, i was going by the old saying:
"Thou shall not include kernel header, or you will feel the wrath of angry kernel gurus."

Greetings
Jan

The OO-Hype keeps on spinning, C stays.

Heh :-)

Well, googling around, it looks like there's a mix of both type of programs out there. Those using a struct bpf_program and those using a struct soft_fprog.

Only the latter will work on BE machines as far as I can tell.

David, what's the right way to fix that ?

Cheers,
Ben.

From: Benjamin Herrenschmidt <[email protected]>
Date: Mon, 30 Apr 2012 15:26:08 +1000

There is no doubt that sock_fprog is the correct datastructure to use.

Ok, so the right fix is to email anybody who posted code using struct bpf_program to fix their code ? :-)

My question was more along the lines of should we attempt changing one of the two variants to make them match on BE (since they are in effect compatible on LE), tho of course this could have the usual annoying consequence of breaking the mangled c++ name of the symbol).

up users and fix them. Great....

Cheers,
Ben.

Actually, the right fix is for anybody using pcap-bpf.h to not use SO_ATTACH_FILTER directly but to use pcap_setfilter() which handles the compatibility.

I'll start spamming web sites who tell people to do the wrong thing.

Cheers,
Ben.

*shudder*
Link to another lib for only one function because....

http://cvsweb.netbsd.org/bsdweb.cgi/src/sys/net/bpf.h?rev=1.59&content-type=text/x-cvsweb-markup&only_with_tag=MAIN
The "Original" says it's an u_int.

But i guess it is unfixable without breaking something, except with ugly code. Should the padding at least be made explicit in the in-kernel struct? Did anyone ever tested the 32bit on 64bit compat code (different padding)?

Greetings
Jan

A UDP packet walks into a

Haven't tested no. A quick google pointed to 2 web pages telling people to do the wrong thing and 4 broken programs out there, interestingly in different ways :-) (somebody's doing a reinterpret_cast of one struct into another, somebody does his/her own local redefinition of the struct ... using a ulong !, etc....)

I don't see a good way to sort that out other than introducing a new kernel-side structure, change the sockopt number, and support the old one as backward binary compat, but that's gross.

Cheers,
Ben.

Ouch!

But a sane way forward?

BTW, has anyone checked the new syscall filter code for these ... misfortunes? I mean before the ABI is set in stone...

Greetings
Jan

😉 

Nope, not yet, looks like something I should do :-)

Cheers,
Ben.

From: Benjamin Herrenschmidt <[email protected]>
Date: Tue, 01 May 2012 10:26:27 +1000

First there are no padding issues, compat or otherwise.

Second, there is no reason to add a new data-structure. Just make them use the right one, sock_fprog, if they are making the socket option call themselves.

I can't believe this discussion is still going on, there is nothing to talk about.

Now the helper function from filter.c for negative offsets is exported, it can be used it in the jit to handle negative offsets.

First modify the asm load helper functions to handle:
- know positive offsets
- know negative offsets
- any offset

then the compiler can be modified to explicitly use these helper when appropriate.

This fixes the case of a negative X register and allows to lift the restriction that bpf programs with negative offsets can't be jited.

---
 arch/powerpc/net/bpf_jit.h      |    8 +++-
 arch/powerpc/net/bpf_jit_64.S   |  108 ++++++++++++++++++++++++++++++++++-----
 arch/powerpc/net/bpf_jit_comp.c |   26 +++------
 3 files changed, 111 insertions(+), 31 deletions(-)

index af1ab5e..5c3cf2d 100644
@@ -48,7 +48,13 @@
 /*
  * Assembly helpers from arch/powerpc/net/bpf_jit.S:
  */
-extern u8 sk_load_word[], sk_load_half[], sk_load_byte[], sk_load_byte_msh[];
+#define DECLARE_LOAD_FUNC(func)	\
+	extern u8 func[], func##_negative_offset[], func##_positive_offset[]
+
+DECLARE_LOAD_FUNC(sk_load_word);
+DECLARE_LOAD_FUNC(sk_load_half);
+DECLARE_LOAD_FUNC(sk_load_byte);
+DECLARE_LOAD_FUNC(sk_load_byte_msh);
 
 #define FUNCTION_DESCR_SIZE	24
 

index 73619d3..2dc8b14 100644
@@ -127,6 +127,9 @@ static void bpf_jit_build_epilogue(u32 *image, struct codegen_context *ctx)
 	PPC_BLR();
 }
 
+#define CHOOSE_LOAD_FUNC(K, func) \
+	((int)K < 0 ? ((int)K >= SKF_LL_OFF ? func##_negative_offset : func) : func##_positive_offset)
+
 /* Assemble the body code between the prologue & epilogue. */
 static int bpf_jit_build_body(struct sk_filter *fp, u32 *image,
 			      struct codegen_context *ctx,

@@ -391,21 +394,16 @@ static int bpf_jit_build_body(struct sk_filter *fp, u32 *image,
 
 			/*** Absolute loads from packet header/data ***/
 		case BPF_S_LD_W_ABS:
-			func = sk_load_word;
+			func = CHOOSE_LOAD_FUNC(K, sk_load_word);
 			goto common_load;
 		case BPF_S_LD_H_ABS:
-			func = sk_load_half;
+			func = CHOOSE_LOAD_FUNC(K, sk_load_half);
 			goto common_load;
 		case BPF_S_LD_B_ABS:
-			func = sk_load_byte;
+			func = CHOOSE_LOAD_FUNC(K, sk_load_byte);
 		common_load:
-			/*
-			 * Load from [K].  Reference with the (negative)
-			 * SKF_NET_OFF/SKF_LL_OFF offsets is unsupported.
-			 */
+			/* Load from [K]. */
 			ctx->seen |= SEEN_DATAREF;
-			if ((int)K < 0)
-				return -ENOTSUPP;
 			PPC_LI64(r_scratch1, func);
 			PPC_MTLR(r_scratch1);
 			PPC_LI32(r_addr, K);

@@ -429,7 +427,7 @@ static int bpf_jit_build_body(struct sk_filter *fp, u32 *image,
 		common_load_ind:
 			/*
 			 * Load from [X + K].  Negative offsets are tested for
-			 * in the helper functions, and result in a 'ret 0'.
+			 * in the helper functions.
 			 */
 			ctx->seen |= SEEN_DATAREF | SEEN_XREG;
 			PPC_LI64(r_scratch1, func);

@@ -443,13 +441,7 @@ static int bpf_jit_build_body(struct sk_filter *fp, u32 *image,
 			break;
 
 		case BPF_S_LDX_B_MSH:
-			/*
-			 * x86 version drops packet (RET 0) when K<0, whereas
-			 * interpreter does allow K<0 (__load_pointer, special
-			 * ancillary data).  common_load returns ENOTSUPP if K<0,
-			 * so we fall back to interpreter & filter works.
-			 */
-			func = sk_load_byte_msh;
+			func = CHOOSE_LOAD_FUNC(K, sk_load_byte_msh);
 			goto common_load;
 			break;
 

From: Jan Seiffert <[email protected]>
Date: Mon, 30 Apr 2012 07:02:19 +0200

Applied, thanks.

David Miller schrieb:
[snip - my patch description]

As Benjamin already said, Matt is having a look, so i expected nothing else.

???
Oh, in which tree is it?
I was working against net-next.

Greetings
Jan

˙qɐɥ ʇɟnɐʞǝƃ ʎɐqǝ ıǝq ɹnʇɐʇsɐʇ ǝuıǝ ɹıɯ ɥɔı sɐp lɐɯ ǝʇzʇǝl sɐp ʇsı sɐp 
'ʇɯɯɐpɹǝʌ

From: Jan Seiffert <[email protected]>
Date: Wed, 4 Apr 2012 00:31:53 +0200

It's been in Linus's tree for several days now.

net-next is stale during the merge window and doesn't get updated until the merge window closes.

The weekend was cold and windy, so i wrote a bpf jit for the Alpha architecture.

---

Patch is against net-next and needs Patch 1 of my "Fix negative offsets" Series (to get bpf_internal_load_pointer_neg_helper)

The Problem is: i don't have any Alpha machine nor do i really have any clue about the arch.
So this is only compile tested.
I could really need some Alpha asm guru to give some advice and review this. Are the calls done right, are the asm load helper ok, all the conditional and sign handling is a little brittle in my mind, etc.

The whole thing is C&P based on the PPC64 jit, so some of the signedness problems may lurk there too.

A user space mock-up turns this:

struct bpf_insn udp_filter[] = {
	/*   0 */ BPF_STMT(BPF_LDX|BPF_W|BPF_IMM, -1048576+(12)),
	/*   1 */ BPF_STMT(BPF_LD|BPF_B|BPF_ABS, -1048576+(0)),
	/*   2 */ BPF_STMT(BPF_ALU|BPF_AND|BPF_K, 0xf0),
	/*   3 */ BPF_JUMP(BPF_JMP|BPF_JEQ|BPF_K, 0x40, 23 - 4, 0),
	/*   4 */ BPF_JUMP(BPF_JMP|BPF_JEQ|BPF_K, 0x60, 5 - 5, 41 - 5),
	/*   5 */ BPF_STMT(BPF_LD|BPF_W|BPF_ABS, -1048576+(8)),
	/*   6 */ BPF_JUMP(BPF_JMP|BPF_JEQ|BPF_K, 0, 13 - 7, 0),
	/*   7 */ BPF_JUMP(BPF_JMP|BPF_JEQ|BPF_K, 0x20010DB8, 41 - 8, 0),
	/*   8 */ BPF_JUMP(BPF_JMP|BPF_JEQ|BPF_K, 0x20010002, 19 - 9, 0),
	/*   9 */ BPF_STMT(BPF_ALU|BPF_AND|BPF_K, 0xfffffff0),
	/*  10 */ BPF_JUMP(BPF_JMP|BPF_JEQ|BPF_K, 0x20010010, 41 - 11, 0),
	/*  11 */ BPF_STMT(BPF_ALU|BPF_AND|BPF_K, 0xff000000),
	/*  12 */ BPF_JUMP(BPF_JMP|BPF_JEQ|BPF_K, 0xff000000, 41 - 13, 39 - 13),
	/*  13 */ BPF_STMT(BPF_LD|BPF_W|BPF_ABS, -1048576+(12)),
	/*  14 */ BPF_JUMP(BPF_JMP|BPF_JEQ|BPF_K, 0, 0, 39 - 15),
	/*  15 */ BPF_STMT(BPF_LD|BPF_W|BPF_ABS, -1048576+(16)),
	/*  16 */ BPF_JUMP(BPF_JMP|BPF_JEQ|BPF_K, 0xffff, 22 - 17, 0),
	/*  17 */ BPF_JUMP(BPF_JMP|BPF_JEQ|BPF_K, 0x0064FF9B, 22 - 18, 0),
	/*  18 */ BPF_JUMP(BPF_JMP|BPF_JEQ|BPF_K, 0, 41 - 19, 39 - 19),
	/*  19 */ BPF_STMT(BPF_LD|BPF_W|BPF_ABS, -1048576+(12)),
	/*  20 */ BPF_STMT(BPF_ALU|BPF_AND|BPF_K, 0xffff0000),
	/*  21 */ BPF_JUMP(BPF_JMP|BPF_JEQ|BPF_K, 0, 41 - 22, 39 - 22),
	/*  22 */ BPF_STMT(BPF_LDX|BPF_W|BPF_IMM, -1048576+(20)),
	/*  23 */ BPF_STMT(BPF_LD|BPF_W|BPF_IND, 0),
	/*  24 */ BPF_JUMP(BPF_JMP|BPF_JEQ|BPF_K, 0xffffffff, 41 - 25, 0),
	/*  25 */ BPF_STMT(BPF_ALU|BPF_AND|BPF_K, 0xffffff00),
	/*  26 */ BPF_JUMP(BPF_JMP|BPF_JEQ|BPF_K, 0xC0000000, 41 - 27, 0),
	/*  27 */ BPF_JUMP(BPF_JMP|BPF_JEQ|BPF_K, 0xC0000200, 41 - 28, 0),
	/*  28 */ BPF_JUMP(BPF_JMP|BPF_JEQ|BPF_K, 0xC6336400, 41 - 29, 0),
	/*  29 */ BPF_JUMP(BPF_JMP|BPF_JEQ|BPF_K, 0xCB007100, 41 - 30, 0),
	/*  30 */ BPF_JUMP(BPF_JMP|BPF_JEQ|BPF_K, 0xC0586300, 41 - 31, 0),
	/*  31 */ BPF_STMT(BPF_ALU|BPF_AND|BPF_K, 0xfffe0000),
	/*  32 */ BPF_JUMP(BPF_JMP|BPF_JEQ|BPF_K, 0xC6120000, 41 - 33, 0),
	/*  33 */ BPF_STMT(BPF_ALU|BPF_AND|BPF_K, 0xff000000),
	/*  34 */ BPF_JUMP(BPF_JMP|BPF_JEQ|BPF_K, 0, 41 - 35, 0),
	/*  35 */ BPF_STMT(BPF_ALU|BPF_AND|BPF_K, 0xf0000000),
	/*  36 */ BPF_JUMP(BPF_JMP|BPF_JEQ|BPF_K, 0xE0000000, 41 - 37, 0),
	/*  37 */ BPF_JUMP(BPF_JMP|BPF_JEQ|BPF_K, 0xF0000000, 41 - 38, 0),
	/*  38 */ BPF_JUMP(BPF_JMP|BPF_JA, 39 - 39, 0, 0),
	/*  39 */ BPF_STMT(BPF_LD|BPF_W|BPF_LEN, 0),
	/*  40 */ BPF_STMT(BPF_RET|BPF_A, 0),
	/*  41 */ BPF_STMT(BPF_RET|BPF_K, 0),
};

into this instruction sequence for Alpha:

   0:   64 00 50 a0     ldl     t1,100(a0)
   4:   60 00 90 a0     ldl     t3,96(a0)
   8:   22 f6 41 48     zapnot  t1,0xf,t1
   c:   24 f6 81 48     zapnot  t3,0xf,t3
  10:   c8 00 70 a4     ldq     t2,200(a0)
  14:   24 01 82 40     subl    t3,t1,t3
  18:   01 04 ff 47     clr     t0
  1c:   00 04 ff 47     clr     v0
  20:   f0 ff 3f 24     ldah    t0,-16
  24:   01 90 21 40     addl    t0,0xc,t0
  28:   f0 ff 1f 27     ldah    t10,-16
  2c:   f7 fe 5b 24     ldah    t1,-265(t12)
  30:   e0 7f 42 20     lda     t1,32736(t1)
  34:   00 40 e2 6a     jsr     t9,(t1),0x38
  38:   72 00 80 f7     bne     at,0x204
  3c:   00 10 1e 44     and     v0,0xf0,v0
  40:   22 11 08 40     subl    v0,0x40,t1
  44:   02 00 e2 43     sextl   t1,t1
  48:   3e 00 40 e4     beq     t1,0x144
  4c:   22 11 0c 40     subl    v0,0x60,t1
  50:   02 00 e2 43     sextl   t1,t1
  54:   6a 00 40 f4     bne     t1,0x200
  58:   f0 ff 1f 27     ldah    t10,-16
  5c:   18 10 01 43     addl    t10,0x8,t10
  60:   f7 fe 5b 24     ldah    t1,-265(t12)
  64:   c8 7f 42 20     lda     t1,32712(t1)
  68:   00 40 e2 6a     jsr     t9,(t1),0x6c
  6c:   65 00 80 f7     bne     at,0x204
  70:   12 00 00 e4     beq     v0,0xbc
  74:   ff df 40 24     ldah    t1,-8193(v0)
  78:   48 f2 42 20     lda     t1,-3512(t1)
  7c:   02 00 e2 43     sextl   t1,t1
  80:   5f 00 40 e4     beq     t1,0x200
  84:   ff df 40 24     ldah    t1,-8193(v0)
  88:   22 51 40 40     subl    t1,0x2,t1
  8c:   02 00 e2 43     sextl   t1,t1
  90:   21 00 40 e4     beq     t1,0x118
  94:   00 f1 01 44     andnot  v0,0xf,v0
  98:   ff df 40 24     ldah    t1,-8193(v0)
  9c:   22 11 42 40     subl    t1,0x10,t1
  a0:   02 00 e2 43     sextl   t1,t1
  a4:   56 00 40 e4     beq     t1,0x200
  a8:   20 16 01 48     zapnot  v0,0x8,v0
  ac:   00 01 40 24     ldah    t1,256(v0)
  b0:   02 00 e2 43     sextl   t1,t1
  b4:   52 00 40 e4     beq     t1,0x200
  b8:   4e 00 e0 c3     br      0x1f4
  bc:   f0 ff 1f 27     ldah    t10,-16
  c0:   18 90 01 43     addl    t10,0xc,t10
  c4:   f7 fe 5b 24     ldah    t1,-265(t12)
  c8:   c8 7f 42 20     lda     t1,32712(t1)
  cc:   00 40 e2 6a     jsr     t9,(t1),0xd0
  d0:   4c 00 80 f7     bne     at,0x204
  d4:   47 00 00 f4     bne     v0,0x1f4
  d8:   f0 ff 1f 27     ldah    t10,-16
  dc:   18 10 02 43     addl    t10,0x10,t10
  e0:   f7 fe 5b 24     ldah    t1,-265(t12)
  e4:   c8 7f 42 20     lda     t1,32712(t1)
  e8:   00 40 e2 6a     jsr     t9,(t1),0xec
  ec:   45 00 80 f7     bne     at,0x204
  f0:   ff ff 40 24     ldah    t1,-1(v0)
  f4:   02 30 40 40     addl    t1,0x1,t1
  f8:   02 00 e2 43     sextl   t1,t1
  fc:   0f 00 40 e4     beq     t1,0x13c
 100:   9b ff 40 24     ldah    t1,-101(v0)
 104:   02 b0 4c 40     addl    t1,0x65,t1
 108:   02 00 e2 43     sextl   t1,t1
 10c:   0b 00 40 e4     beq     t1,0x13c
 110:   3b 00 00 e4     beq     v0,0x200
 114:   37 00 e0 c3     br      0x1f4
 118:   f0 ff 1f 27     ldah    t10,-16
 11c:   18 90 01 43     addl    t10,0xc,t10
 120:   f7 fe 5b 24     ldah    t1,-265(t12)
 124:   c8 7f 42 20     lda     t1,32712(t1)
 128:   00 40 e2 6a     jsr     t9,(t1),0x12c
 12c:   35 00 80 f7     bne     at,0x204
 130:   20 96 01 48     zapnot  v0,0xc,v0
 134:   32 00 00 e4     beq     v0,0x200
 138:   2e 00 e0 c3     br      0x1f4
 13c:   f0 ff 3f 24     ldah    t0,-16
 140:   01 90 22 40     addl    t0,0x14,t0
 144:   18 04 e1 47     mov     t0,t10
 148:   18 00 f8 43     sextl   t10,t10
 14c:   f7 fe 5b 24     ldah    t1,-265(t12)
 150:   c0 7f 42 20     lda     t1,32704(t1)
 154:   00 40 e2 6a     jsr     t9,(t1),0x158
 158:   2a 00 80 f7     bne     at,0x204
 15c:   02 30 00 40     addl    v0,0x1,t1
 160:   02 00 e2 43     sextl   t1,t1
 164:   26 00 40 e4     beq     t1,0x200
 168:   20 d6 01 48     zapnot  v0,0xe,v0
 16c:   00 40 40 24     ldah    t1,16384(v0)
 170:   02 00 e2 43     sextl   t1,t1
 174:   22 00 40 e4     beq     t1,0x200
 178:   00 40 40 24     ldah    t1,16384(v0)
 17c:   00 fe 42 20     lda     t1,-512(t1)
 180:   02 00 e2 43     sextl   t1,t1
 184:   1e 00 40 e4     beq     t1,0x200
 188:   cd 39 40 24     ldah    t1,14797(v0)
 18c:   00 9c 42 20     lda     t1,-25600(t1)
 190:   02 00 e2 43     sextl   t1,t1
 194:   1a 00 40 e4     beq     t1,0x200
 198:   00 35 40 24     ldah    t1,13568(v0)
 19c:   00 8f 42 20     lda     t1,-28928(t1)
 1a0:   02 00 e2 43     sextl   t1,t1
 1a4:   16 00 40 e4     beq     t1,0x200
 1a8:   a8 3f 40 24     ldah    t1,16296(v0)
 1ac:   00 9d 42 20     lda     t1,-25344(t1)
 1b0:   02 00 e2 43     sextl   t1,t1
 1b4:   12 00 40 e4     beq     t1,0x200
 1b8:   fe ff 5f 24     ldah    t1,-2
 1bc:   00 00 02 44     and     v0,t1,v0
 1c0:   ee 39 40 24     ldah    t1,14830(v0)
 1c4:   02 00 e2 43     sextl   t1,t1
 1c8:   0d 00 40 e4     beq     t1,0x200
 1cc:   20 16 01 48     zapnot  v0,0x8,v0
 1d0:   0b 00 00 e4     beq     v0,0x200
 1d4:   00 f0 5f 24     ldah    t1,-4096
 1d8:   00 00 02 44     and     v0,t1,v0
 1dc:   00 20 40 24     ldah    t1,8192(v0)
 1e0:   02 00 e2 43     sextl   t1,t1
 1e4:   06 00 40 e4     beq     t1,0x200
 1e8:   00 10 40 24     ldah    t1,4096(v0)
 1ec:   02 00 e2 43     sextl   t1,t1
 1f0:   03 00 40 e4     beq     t1,0x200
 1f4:   60 00 10 a0     ldl     v0,96(a0)
 1f8:   20 f6 01 48     zapnot  v0,0xf,v0
 1fc:   01 80 fa 6b     ret
 200:   00 04 ff 47     clr     v0
 204:   01 80 fa 6b     ret

index 56a4df9..eede373 100644
@@ -15,6 +15,7 @@ config ALPHA
 	select GENERIC_IRQ_SHOW
 	select ARCH_WANT_OPTIONAL_GPIOLIB
 	select ARCH_HAVE_NMI_SAFE_CMPXCHG
+	select HAVE_BPF_JIT if (NET)
 	help
 	  The Alpha is a 64-bit general-purpose processor designed and
 	  marketed by the Digital Equipment Corporation of blessed memory,

index 4759fe7..e634f0c 100644
@@ -38,7 +38,9 @@ KBUILD_CFLAGS += $(cflags-y) -Wa,-mev6
 
 head-y := arch/alpha/kernel/head.o
 
-core-y				+= arch/alpha/kernel/ arch/alpha/mm/
+core-y				+= arch/alpha/kernel/ \
+				   arch/alpha/mm/ \
+				   arch/alpha/net/
 core-$(CONFIG_MATHEMU)		+= arch/alpha/math-emu/
 drivers-$(CONFIG_OPROFILE)	+= arch/alpha/oprofile/
 libs-y				+= arch/alpha/lib/

new file mode 100644
index 0000000..4a6ae5b
@@ -0,0 +1,4 @@
+#
+# Arch-specific network modules
+#
+obj-$(CONFIG_BPF_JIT) += bpf_jit_helper.o bpf_jit_comp.o

Very cool. I'll try to find some time soon to test this.

Thanks a lot!
Matt

That would be great.
But make sure to fasten your seat belts, it will prop. crash hard ;) Here is a link to the Patch 1 you also need:
<http://marc.info/?l=linux-kernel&m=133312658915220&w=2>

Greetings
Jan

Wherever I lay my .vimrc, there's my $HOME.

  mask = 0;
  for (j = 0; j < 4; j++) {
    int b = (K >> i*8) & 0xff;
    if (b == 0xff)
      mask |= 1 << i;
    else if (b != 0)
      mask = -1;
  }
  if (mask != -1) {
    ALPHA_ZAPNOTI(r_A, mask, r_t);
    return;
  }

It would be helpful to use '$' prefixes here for local variables.

r~

Richard Henderson schrieb:

Thanks for the review Mr.Henderson. I'm so grateful you taken some of your valuable time for this.

[snip]

Removed

I'm unsure. The problem goes like this:
Since constant loading can take so much instructions, the code tends to get big. This is bad for jump ranges, the icache and pinned kernel mem. I would not mind about it (it's a RISC, it is meant to be that way), if the constants weren't right there. We get the original filter program (which contains the constants) passed as second parameter, on a silver platter (i was even thinking about moving the second parameter 32k forward to get the full imm16 range, on the other hand if struct sock_filter is 8 byte on Alpha, then +32k is good enough for MAX_BPF_INSN == 4096).

Essentially this is two questions, one for the Alpha µ-arch gurus and one for the kernel (net-)devs.
µ-Arch Gurus: How bad are mem accesses in contrast to icache for example. Kernel devs: how important is memory consumption/how much "faster" the jitted code has to be?

add_constant takes care of that, only the entry condition is so complicated because of the optimize_size case.

[snip - ugly and optimization]

yes, i was typing as fast as i was thinking: "hmmm, a constant can look like this or like that or like this...". The optimizations where an "afterthought", i first broke the operations out into a helper and simply made it work. Because i knew there are some shenanigans you can do with zapnot i revisited it at the end. I will now grab a brown paper bag.

Works like a charm, only had to change i for j. Thanks!

[snip - or 0xffffffff]

changed

[snip]

I was thinking maybe the zapnot^wzextw is faster, because it does not have to do the shift and it should be the common case.
But if extw is good enough, thus removed.

It is known to either call special bpf helper or __divlu (the kernel version). The special helper are responsible for setting pv right when they have to call to C again (which is deemed as the exceptional case).

That was my idea, so i don't have to set pv again after every call, which would bloat up every filter program.

But i don't know if the helper do the "pv and call and gp"-dance right :(

[snip - div 0 test]

Can't do.
When building the program we are searching for a ret 0 case. As long as no case is found (or is never found), we have to build one.

Besides, i know it's dirty, r_ret and r_A share the same register. I was squeezing on the register usage so i may use the register as storage for the 16 bpf mem[] slots like powerpc, i mean Alpha has 31 like powerpc. But in the end i was to stupid to achieve this. At least this hack saves a mov at the end.

I know, and i don't know what i want.

The problem is the bpf cpu is inherently unsigned. It does all loads zero extended, only has logical shifts, does all compares unsigned. Which sounds like i have to zero extend like crazy. (i took the Powerpc code as example, it does most things unsigned and on 32 Bit, but has similar "add is sign extending" things, so i thought it can't be that bad, otherwise it would have the same Bugs).

I was hoping to let the sign run it's course/sign extend and only cut at the right point, and i figured that was a point to cut, i should prop. sign extend.

But if that is not feasible, i could also sprinkle everything with zero extends.

Oh, thanks!
Yes, the shift operations are only logical shifts, so it has to be properly zero extended.

[snip - bpf_flush_icache]

Thanks! I guess i will stick to the flush_icache_range, which is defined to an imb()/smp_imb(), so should do the right thing(TM).

[snip - comment about pases]

The first pass is called with image == NULL, so all calls have a very long displacement + we have to make other worst case/wrong assumptions because addrs is not properly filled and the exit points are unknown. The second pass with image == NULL will settle some jumps, because addrs is now mostly properly populated _and_ the exit points are set. This is done to get a real good estimate when allocating mem, so not to much is allocated (saw a thread on lkml where Eric was talking with Ingo about module_realloc, so the memusage is of concern, it is pinned kernel memory for the user space).
The other passes are only to make things really slick with image != NULL, and stop if there is no change.
If i knew some kind of base address where module_alloc will allocate, i could feed that in early...

I was working on a patch for that, but it was more complicated, esp. it may cost some RAM and/or CPU time just to remove one/two instructions, so i left it out for the moment till i revisit it.

???
Sorry, i don't understand what you mean. What variables? Or do you mean register? It uses the same register as the compiler. So to not confuse things i made the names from the compiler usable in asm. You can change one define and the compiler and the helper will use another reg.

Greetings
Jan

Anyone can build a fast processor. The trick is to build a fast system.
(Seymour Cray)
--
To unsubscribe from this list: send the line "unsubscribe linux-alpha" in
the body of a message to [email protected]
More majordomo info at  http://vger.kernel.org/majordomo-info.html

The arm jit has the same problem as the other two jits.
It only tests for negative absolute memory references, and if it sees one bails out to let the interpreter handle the filter program.

But this fails if the X register contains a negative memory reference and is used for an indirect load.
This is only caught at runtime, where the filter will always drop the packet.
Filter which work fine with the interpreter do not work with the jit.

So this patch tries to fix it for the arm jit.

First we add the prototype of bpf_internal_load_pointer_neg_helper to filter.h, since the arm jit has no assembler component, instead it has to be used from C.

Then the helper functions are prepared to either handle known positive offsets, known negative offsets, or any offset and test at runtime.

Finally the compiler is modified to emit calls to the right function, depending if either the offset is known, or not.

This fixes the case of a negative X register and allows to lift the restriction that bpf programs with negative offsets can't be jited.

---
The arm jit structure is a little bit different then the other jits, esp. it does not use assembler load helper. So i had to put the prototype for bpf_internal_load_pointer_neg_helper somewhere.

This is a v1 to keep the ball rolling.

Testing would also be cool, -ENOHARDWARE.

 arch/arm/net/bpf_jit_32.c |  149 ++++++++++++++++++++++++++++++++-------------
 include/linux/filter.h    |    6 ++
 net/core/filter.c         |    4 +
 3 files changed, 117 insertions(+), 42 deletions(-)

index 62135849..19d60af 100644
@@ -18,6 +18,7 @@
 #include <linux/slab.h>
 #include <asm/cacheflush.h>
 #include <asm/hwcap.h>
+#include <asm/unaligned.h>
 
 #include "bpf_jit_32.h"
 

@@ -71,7 +72,7 @@ struct jit_ctx {
 
 int bpf_jit_enable __read_mostly;
 
-static u64 jit_get_skb_b(struct sk_buff *skb, unsigned offset)
+static u64 jit_get_skb_b_pos(struct sk_buff *skb, unsigned offset)
 {
 	u8 ret;
 	int err;

@@ -81,7 +82,7 @@ static u64 jit_get_skb_b(struct sk_buff *skb, unsigned offset)
 	return (u64)err << 32 | ret;
 }
 
-static u64 jit_get_skb_h(struct sk_buff *skb, unsigned offset)
+static u64 jit_get_skb_h_pos(struct sk_buff *skb, unsigned offset)
 {
 	u16 ret;
 	int err;

@@ -91,7 +92,7 @@ static u64 jit_get_skb_h(struct sk_buff *skb, unsigned offset)
 	return (u64)err << 32 | ntohs(ret);
 }
 
-static u64 jit_get_skb_w(struct sk_buff *skb, unsigned offset)
+static u64 jit_get_skb_w_pos(struct sk_buff *skb, unsigned offset)
 {
 	u32 ret;
 	int err;

@@ -101,6 +102,60 @@ static u64 jit_get_skb_w(struct sk_buff *skb, unsigned offset)
 	return (u64)err << 32 | ntohl(ret);
 }
 
+static u64 jit_get_skb_b_neg(struct sk_buff *skb, unsigned offset)
+{
+	u8 *ptr;
+
+	ptr = bpf_internal_load_pointer_neg_helper(skb, offset, 1);
+	if (!ptr)
+		return (u64)1 << 32;
+	return *ptr;
+}
+
+static u64 jit_get_skb_h_neg(struct sk_buff *skb, unsigned offset)
+{
+	u16 *ptr;
+
+	ptr = bpf_internal_load_pointer_neg_helper(skb, offset, 2);
+	if (!ptr)
+		return (u64)1 << 32;
+	return get_unaligned_be16(ptr);
+}
+
+static u64 jit_get_skb_w_neg(struct sk_buff *skb, unsigned offset)
+{
+	u32 *ptr;
+
+	ptr = bpf_internal_load_pointer_neg_helper(skb, offset, 4);
+	if (!ptr)
+		return (u64)1 << 32;
+	return get_unaligned_be32(ptr);
+}
+
+static u64 jit_get_skb_b_any(struct sk_buff *skb, unsigned offset)
+{
+	if ((int)offset >= 0)
+		return jit_get_skb_b_pos(skb, offset);
+	else
+		return jit_get_skb_b_neg(skb, offset);
+}
+
+static u64 jit_get_skb_h_any(struct sk_buff *skb, unsigned offset)
+{
+	if ((int)offset >= 0)
+		return jit_get_skb_h_pos(skb, offset);
+	else
+		return jit_get_skb_h_neg(skb, offset);
+}
+
+static u64 jit_get_skb_w_any(struct sk_buff *skb, unsigned offset)
+{
+	if ((int)offset >= 0)
+		return jit_get_skb_w_pos(skb, offset);
+	else
+		return jit_get_skb_w_neg(skb, offset);
+}
+
 /*
  * Wrapper that handles both OABI and EABI and assures Thumb2 interworking
  * (where the assembly routines like __aeabi_uidiv could cause problems).

@@ -458,7 +513,10 @@ static inline void update_on_xread(struct jit_ctx *ctx)
 
 static int build_body(struct jit_ctx *ctx)
 {
-	void *load_func[] = {jit_get_skb_b, jit_get_skb_h, jit_get_skb_w};
+	void *load_func_any[] = {jit_get_skb_b_any, jit_get_skb_h_any, jit_get_skb_w_any};
+	void *load_func_pos[] = {jit_get_skb_b_pos, jit_get_skb_h_pos, jit_get_skb_w_pos};
+	void *load_func_neg[] = {jit_get_skb_b_neg, jit_get_skb_h_neg, jit_get_skb_w_neg};
+	void **load_func;
 	const struct sk_filter *prog = ctx->skf;
 	const struct sock_filter *inst;
 	unsigned i, load_order, off, condt;

@@ -498,36 +556,38 @@ static int build_body(struct jit_ctx *ctx)
 		case BPF_S_LD_B_ABS:
 			load_order = 0;
 load:
-			/* the interpreter will deal with the negative K */
-			if ((int)k < 0)
-				return -ENOTSUPP;
 			emit_mov_i(r_off, k, ctx);
-load_common:
-			ctx->seen |= SEEN_DATA | SEEN_CALL;
-
-			if (load_order > 0) {
-				emit(ARM_SUB_I(r_scratch, r_skb_hl,
-					       1 << load_order), ctx);
-				emit(ARM_CMP_R(r_scratch, r_off), ctx);
-				condt = ARM_COND_HS;
-			} else {
-				emit(ARM_CMP_R(r_skb_hl, r_off), ctx);
-				condt = ARM_COND_HI;
-			}
 
-			_emit(condt, ARM_ADD_R(r_scratch, r_off, r_skb_data),
-			      ctx);
-
-			if (load_order == 0)
-				_emit(condt, ARM_LDRB_I(r_A, r_scratch, 0),
+			/* deal with negative K */
+			if (k >= 0) {
+				load_func = load_func_pos;
+				if (load_order > 0) {
+					emit(ARM_SUB_I(r_scratch, r_skb_hl,
+						       1 << load_order), ctx);
+					emit(ARM_CMP_R(r_scratch, r_off), ctx);
+					condt = ARM_COND_HS;
+				} else {
+					emit(ARM_CMP_R(r_skb_hl, r_off), ctx);
+					condt = ARM_COND_HI;
+				}
+
+				_emit(condt, ARM_ADD_R(r_scratch, r_off, r_skb_data),
 				      ctx);
-			else if (load_order == 1)
-				emit_load_be16(condt, r_A, r_scratch, ctx);
-			else if (load_order == 2)
-				emit_load_be32(condt, r_A, r_scratch, ctx);
 
-			_emit(condt, ARM_B(b_imm(i + 1, ctx)), ctx);
+				if (load_order == 0)
+					_emit(condt, ARM_LDRB_I(r_A, r_scratch, 0),
+					      ctx);
+				else if (load_order == 1)
+					emit_load_be16(condt, r_A, r_scratch, ctx);
+				else if (load_order == 2)
+					emit_load_be32(condt, r_A, r_scratch, ctx);
 
+				_emit(condt, ARM_B(b_imm(i + 1, ctx)), ctx);
+			} else {
+				load_func = load_func_neg;
+			}
+load_common:
+			ctx->seen |= SEEN_DATA | SEEN_CALL;
 			/* the slowpath */
 			emit_mov_i(ARM_R3, (u32)load_func[load_order], ctx);
 			emit(ARM_MOV_R(ARM_R0, r_skb), ctx);

@@ -547,7 +607,9 @@ load_common:
 		case BPF_S_LD_B_IND:
 			load_order = 0;
 load_ind:
+			load_func = load_func_any;
 			OP_IMM3(ARM_ADD, r_off, r_X, k, ctx);
+			load_func = load_func_any;
 			goto load_common;
 		case BPF_S_LDX_IMM:
 			ctx->seen |= SEEN_X;

@@ -565,25 +627,28 @@ load_ind:
 		case BPF_S_LDX_B_MSH:
 			/* x = ((*(frame + k)) & 0xf) << 2; */
 			ctx->seen |= SEEN_X | SEEN_DATA | SEEN_CALL;
-			/* the interpreter should deal with the negative K */
-			if (k < 0)
-				return -1;
 			/* offset in r1: we might have to take the slow path */
 			emit_mov_i(r_off, k, ctx);
-			emit(ARM_CMP_R(r_skb_hl, r_off), ctx);
+			/* deal with negative K */
+			if (k >= 0) {
+				load_func = load_func_pos;
+				emit(ARM_CMP_R(r_skb_hl, r_off), ctx);
 
-			/* load in r0: common with the slowpath */
-			_emit(ARM_COND_HI, ARM_LDRB_R(ARM_R0, r_skb_data,
-						      ARM_R1), ctx);
-			/*
-			 * emit_mov_i() might generate one or two instructions,
-			 * the same holds for emit_blx_r()
-			 */
-			_emit(ARM_COND_HI, ARM_B(b_imm(i + 1, ctx) - 2), ctx);
+				/* load in r0: common with the slowpath */
+				_emit(ARM_COND_HI, ARM_LDRB_R(ARM_R0, r_skb_data,
+							      ARM_R1), ctx);
+				/*
+				 * emit_mov_i() might generate one or two instructions,
+				 * the same holds for emit_blx_r()
+				 */
+				_emit(ARM_COND_HI, ARM_B(b_imm(i + 1, ctx) - 2), ctx);
+			} else {
+				load_func = load_func_neg;
+			}
 
 			emit(ARM_MOV_R(ARM_R0, r_skb), ctx);
 			/* r_off is r1 */
-			emit_mov_i(ARM_R3, (u32)jit_get_skb_b, ctx);
+			emit_mov_i(ARM_R3, (u32)load_func[0], ctx);
 			emit_blx_r(ARM_R3, ctx);
 			/* check the return value of skb_copy_bits */
 			emit(ARM_CMP_I(ARM_R1, 0), ctx);

index 8eeb205..78cd56d 100644
@@ -161,6 +161,12 @@ extern int sk_chk_filter(struct sock_filter *filter, unsigned int flen);
 extern void bpf_jit_compile(struct sk_filter *fp);
 extern void bpf_jit_free(struct sk_filter *fp);
 #define SK_RUN_FILTER(FILTER, SKB) (*FILTER->bpf_func)(SKB, FILTER->insns)
+/*
+ * Only Exported for the bpf jit load helper.
+ * Do not call from anywhere else!
+ */
+extern void *bpf_internal_load_pointer_neg_helper(const struct sk_buff *skb,
+		int k, unsigned int size);
 #else
 static inline void bpf_jit_compile(struct sk_filter *fp)
 {

index 6f755cc..9cbaecb 100644
@@ -42,6 +42,10 @@
 /* No hurry in this branch
  *
  * Exported for the bpf jit load helper.
+ *
+ * CAUTION ! :
+ * If its prototype is ever changed, check arch/{*}/net/{*}.S files,
+ * since it is called from BPF assembly code.
  */
 void *bpf_internal_load_pointer_neg_helper(const struct sk_buff *skb, int k, unsigned int size)
 {

The arm jit has the same problem as the other two jits.
It only tests for negative absolute memory references, and if it sees one bails out to let the interpreter handle the filter program.

But this fails if the X register contains a negative memory reference and is used for an indirect load.
This is only caught at runtime, where the filter will always drop the packet.
Filter which work fine with the interpreter do not work with the jit.

So this patch tries to fix it for the arm jit.

First we add the prototype of bpf_internal_load_pointer_neg_helper to filter.h, since the arm jit has no assembler component, instead it has to be used from C.

Then the helper functions are prepared to either handle known positive offsets, known negative offsets, or any offset and test at runtime.

Finally the compiler is modified to emit calls to the right function, depending if either the offset is known, or not.

This fixes the case of a negative X register and allows to lift the restriction that bpf programs with negative offsets can't be jited.

---
Sorry for sending a v2 so fast, but i immidiatly found an major error... v1 -> v2:
* when checking if K is greater then 0 make sure to compare signed

remarks from v1 still apply.

 arch/arm/net/bpf_jit_32.c |  149 ++++++++++++++++++++++++++++++++-------------
 include/linux/filter.h    |    6 ++
 net/core/filter.c         |    4 +
 3 files changed, 117 insertions(+), 42 deletions(-)

index 62135849..19d60af 100644
@@ -18,6 +18,7 @@
 #include <linux/slab.h>
 #include <asm/cacheflush.h>
 #include <asm/hwcap.h>
+#include <asm/unaligned.h>
 
 #include "bpf_jit_32.h"
 

@@ -71,7 +72,7 @@ struct jit_ctx {
 
 int bpf_jit_enable __read_mostly;
 
-static u64 jit_get_skb_b(struct sk_buff *skb, unsigned offset)
+static u64 jit_get_skb_b_pos(struct sk_buff *skb, unsigned offset)
 {
 	u8 ret;
 	int err;

@@ -81,7 +82,7 @@ static u64 jit_get_skb_b(struct sk_buff *skb, unsigned offset)
 	return (u64)err << 32 | ret;
 }
 
-static u64 jit_get_skb_h(struct sk_buff *skb, unsigned offset)
+static u64 jit_get_skb_h_pos(struct sk_buff *skb, unsigned offset)
 {
 	u16 ret;
 	int err;

@@ -91,7 +92,7 @@ static u64 jit_get_skb_h(struct sk_buff *skb, unsigned offset)
 	return (u64)err << 32 | ntohs(ret);
 }
 
-static u64 jit_get_skb_w(struct sk_buff *skb, unsigned offset)
+static u64 jit_get_skb_w_pos(struct sk_buff *skb, unsigned offset)
 {
 	u32 ret;
 	int err;

@@ -101,6 +102,60 @@ static u64 jit_get_skb_w(struct sk_buff *skb, unsigned offset)
 	return (u64)err << 32 | ntohl(ret);
 }
 
+static u64 jit_get_skb_b_neg(struct sk_buff *skb, unsigned offset)
+{
+	u8 *ptr;
+
+	ptr = bpf_internal_load_pointer_neg_helper(skb, offset, 1);
+	if (!ptr)
+		return (u64)1 << 32;
+	return *ptr;
+}
+
+static u64 jit_get_skb_h_neg(struct sk_buff *skb, unsigned offset)
+{
+	u16 *ptr;
+
+	ptr = bpf_internal_load_pointer_neg_helper(skb, offset, 2);
+	if (!ptr)
+		return (u64)1 << 32;
+	return get_unaligned_be16(ptr);
+}
+
+static u64 jit_get_skb_w_neg(struct sk_buff *skb, unsigned offset)
+{
+	u32 *ptr;
+
+	ptr = bpf_internal_load_pointer_neg_helper(skb, offset, 4);
+	if (!ptr)
+		return (u64)1 << 32;
+	return get_unaligned_be32(ptr);
+}
+
+static u64 jit_get_skb_b_any(struct sk_buff *skb, unsigned offset)
+{
+	if ((int)offset >= 0)
+		return jit_get_skb_b_pos(skb, offset);
+	else
+		return jit_get_skb_b_neg(skb, offset);
+}
+
+static u64 jit_get_skb_h_any(struct sk_buff *skb, unsigned offset)
+{
+	if ((int)offset >= 0)
+		return jit_get_skb_h_pos(skb, offset);
+	else
+		return jit_get_skb_h_neg(skb, offset);
+}
+
+static u64 jit_get_skb_w_any(struct sk_buff *skb, unsigned offset)
+{
+	if ((int)offset >= 0)
+		return jit_get_skb_w_pos(skb, offset);
+	else
+		return jit_get_skb_w_neg(skb, offset);
+}
+
 /*
  * Wrapper that handles both OABI and EABI and assures Thumb2 interworking
  * (where the assembly routines like __aeabi_uidiv could cause problems).

@@ -458,7 +513,10 @@ static inline void update_on_xread(struct jit_ctx *ctx)
 
 static int build_body(struct jit_ctx *ctx)
 {
-	void *load_func[] = {jit_get_skb_b, jit_get_skb_h, jit_get_skb_w};
+	void *load_func_any[] = {jit_get_skb_b_any, jit_get_skb_h_any, jit_get_skb_w_any};
+	void *load_func_pos[] = {jit_get_skb_b_pos, jit_get_skb_h_pos, jit_get_skb_w_pos};
+	void *load_func_neg[] = {jit_get_skb_b_neg, jit_get_skb_h_neg, jit_get_skb_w_neg};
+	void **load_func;
 	const struct sk_filter *prog = ctx->skf;
 	const struct sock_filter *inst;
 	unsigned i, load_order, off, condt;

@@ -498,36 +556,38 @@ static int build_body(struct jit_ctx *ctx)
 		case BPF_S_LD_B_ABS:
 			load_order = 0;
 load:
-			/* the interpreter will deal with the negative K */
-			if ((int)k < 0)
-				return -ENOTSUPP;
 			emit_mov_i(r_off, k, ctx);
-load_common:
-			ctx->seen |= SEEN_DATA | SEEN_CALL;
-
-			if (load_order > 0) {
-				emit(ARM_SUB_I(r_scratch, r_skb_hl,
-					       1 << load_order), ctx);
-				emit(ARM_CMP_R(r_scratch, r_off), ctx);
-				condt = ARM_COND_HS;
-			} else {
-				emit(ARM_CMP_R(r_skb_hl, r_off), ctx);
-				condt = ARM_COND_HI;
-			}
 
-			_emit(condt, ARM_ADD_R(r_scratch, r_off, r_skb_data),
-			      ctx);
-
-			if (load_order == 0)
-				_emit(condt, ARM_LDRB_I(r_A, r_scratch, 0),
+			/* deal with negative K */
+			if ((int)k >= 0) {
+				load_func = load_func_pos;
+				if (load_order > 0) {
+					emit(ARM_SUB_I(r_scratch, r_skb_hl,
+						       1 << load_order), ctx);
+					emit(ARM_CMP_R(r_scratch, r_off), ctx);
+					condt = ARM_COND_HS;
+				} else {
+					emit(ARM_CMP_R(r_skb_hl, r_off), ctx);
+					condt = ARM_COND_HI;
+				}
+
+				_emit(condt, ARM_ADD_R(r_scratch, r_off, r_skb_data),
 				      ctx);
-			else if (load_order == 1)
-				emit_load_be16(condt, r_A, r_scratch, ctx);
-			else if (load_order == 2)
-				emit_load_be32(condt, r_A, r_scratch, ctx);
 
-			_emit(condt, ARM_B(b_imm(i + 1, ctx)), ctx);
+				if (load_order == 0)
+					_emit(condt, ARM_LDRB_I(r_A, r_scratch, 0),
+					      ctx);
+				else if (load_order == 1)
+					emit_load_be16(condt, r_A, r_scratch, ctx);
+				else if (load_order == 2)
+					emit_load_be32(condt, r_A, r_scratch, ctx);
 
+				_emit(condt, ARM_B(b_imm(i + 1, ctx)), ctx);
+			} else {
+				load_func = load_func_neg;
+			}
+load_common:
+			ctx->seen |= SEEN_DATA | SEEN_CALL;
 			/* the slowpath */
 			emit_mov_i(ARM_R3, (u32)load_func[load_order], ctx);
 			emit(ARM_MOV_R(ARM_R0, r_skb), ctx);

@@ -547,7 +607,9 @@ load_common:
 		case BPF_S_LD_B_IND:
 			load_order = 0;
 load_ind:
+			load_func = load_func_any;
 			OP_IMM3(ARM_ADD, r_off, r_X, k, ctx);
+			load_func = load_func_any;
 			goto load_common;
 		case BPF_S_LDX_IMM:
 			ctx->seen |= SEEN_X;

@@ -565,25 +627,28 @@ load_ind:
 		case BPF_S_LDX_B_MSH:
 			/* x = ((*(frame + k)) & 0xf) << 2; */
 			ctx->seen |= SEEN_X | SEEN_DATA | SEEN_CALL;
-			/* the interpreter should deal with the negative K */
-			if (k < 0)
-				return -1;
 			/* offset in r1: we might have to take the slow path */
 			emit_mov_i(r_off, k, ctx);
-			emit(ARM_CMP_R(r_skb_hl, r_off), ctx);
+			/* deal with negative K */
+			if ((int)k >= 0) {
+				load_func = load_func_pos;
+				emit(ARM_CMP_R(r_skb_hl, r_off), ctx);
 
-			/* load in r0: common with the slowpath */
-			_emit(ARM_COND_HI, ARM_LDRB_R(ARM_R0, r_skb_data,
-						      ARM_R1), ctx);
-			/*
-			 * emit_mov_i() might generate one or two instructions,
-			 * the same holds for emit_blx_r()
-			 */
-			_emit(ARM_COND_HI, ARM_B(b_imm(i + 1, ctx) - 2), ctx);
+				/* load in r0: common with the slowpath */
+				_emit(ARM_COND_HI, ARM_LDRB_R(ARM_R0, r_skb_data,
+							      ARM_R1), ctx);
+				/*
+				 * emit_mov_i() might generate one or two instructions,
+				 * the same holds for emit_blx_r()
+				 */
+				_emit(ARM_COND_HI, ARM_B(b_imm(i + 1, ctx) - 2), ctx);
+			} else {
+				load_func = load_func_neg;
+			}
 
 			emit(ARM_MOV_R(ARM_R0, r_skb), ctx);
 			/* r_off is r1 */
-			emit_mov_i(ARM_R3, (u32)jit_get_skb_b, ctx);
+			emit_mov_i(ARM_R3, (u32)load_func[0], ctx);
 			emit_blx_r(ARM_R3, ctx);
 			/* check the return value of skb_copy_bits */
 			emit(ARM_CMP_I(ARM_R1, 0), ctx);

index 8eeb205..78cd56d 100644
@@ -161,6 +161,12 @@ extern int sk_chk_filter(struct sock_filter *filter, unsigned int flen);
 extern void bpf_jit_compile(struct sk_filter *fp);
 extern void bpf_jit_free(struct sk_filter *fp);
 #define SK_RUN_FILTER(FILTER, SKB) (*FILTER->bpf_func)(SKB, FILTER->insns)
+/*
+ * Only Exported for the bpf jit load helper.
+ * Do not call from anywhere else!
+ */
+extern void *bpf_internal_load_pointer_neg_helper(const struct sk_buff *skb,
+		int k, unsigned int size);
 #else
 static inline void bpf_jit_compile(struct sk_filter *fp)
 {

index 6f755cc..9cbaecb 100644
@@ -42,6 +42,10 @@
 /* No hurry in this branch
  *
  * Exported for the bpf jit load helper.
+ *
+ * CAUTION ! :
+ * If its prototype is ever changed, check arch/{*}/net/{*}.S files,
+ * since it is called from BPF assembly code.
  */
 void *bpf_internal_load_pointer_neg_helper(const struct sk_buff *skb, int k, unsigned int size)
 {

Hi,

Am 06.04.2012 20:57, schrieb Jan Seiffert:

I don't think that there's any use case for negative values in X. In both the original BPF design and in the LSF interpreter, A and X are considered unsigned. The role of X is mainly to allow variable length headers (load the length -> unsigned).

"Negative" K values are permitted for ancillary data loads based on the fact that we're not going to see 2GB packets any time soon.

Mircea

Mircea

Hi

<mode temper="elevated" reason="had that discussion already">

There is.
Say you have a bpf filter on an UDP socket. You want to filter bogus Source addresses in kernel to prevent the context switch and copying. Since ipv6 has a v4 mapped space, you have to make the same tests for the v6-mapped space as for v4, so you can use one program for v4 & v6 to begin with.
You can solve it without a negative offset in X, it's is just very helpful. Still you have negative offsets, which means no jit.

struct bpf_insn udp_filter[] = {
        /*   0 */ BPF_STMT(BPF_LDX|BPF_W|BPF_IMM, -1048576+(12)),
        /*   1 */ BPF_STMT(BPF_LD|BPF_B|BPF_ABS, -1048576+(0)),
        /*   2 */ BPF_STMT(BPF_ALU|BPF_AND|BPF_K, 0xf0),
        /*   3 */ BPF_JUMP(BPF_JMP|BPF_JEQ|BPF_K, 0x40, 23 - 4, 0),
        /*   4 */ BPF_JUMP(BPF_JMP|BPF_JEQ|BPF_K, 0x60, 5 - 5, 41 - 5),
        /*   5 */ BPF_STMT(BPF_LD|BPF_W|BPF_ABS, -1048576+(8)),
        /*   6 */ BPF_JUMP(BPF_JMP|BPF_JEQ|BPF_K, 0, 13 - 7, 0),
        /*   7 */ BPF_JUMP(BPF_JMP|BPF_JEQ|BPF_K, 0x20010DB8, 41 - 8, 0),
        /*   8 */ BPF_JUMP(BPF_JMP|BPF_JEQ|BPF_K, 0x20010002, 19 - 9, 0),
        /*   9 */ BPF_STMT(BPF_ALU|BPF_AND|BPF_K, 0xfffffff0),
        /*  10 */ BPF_JUMP(BPF_JMP|BPF_JEQ|BPF_K, 0x20010010, 41 - 11, 0),
        /*  11 */ BPF_STMT(BPF_ALU|BPF_AND|BPF_K, 0xff000000),
        /*  12 */ BPF_JUMP(BPF_JMP|BPF_JEQ|BPF_K, 0xff000000, 41 - 13, 39 - 13),
        /*  13 */ BPF_STMT(BPF_LD|BPF_W|BPF_ABS, -1048576+(12)),
        /*  14 */ BPF_JUMP(BPF_JMP|BPF_JEQ|BPF_K, 0, 0, 39 - 15),
        /*  15 */ BPF_STMT(BPF_LD|BPF_W|BPF_ABS, -1048576+(16)),
        /*  16 */ BPF_JUMP(BPF_JMP|BPF_JEQ|BPF_K, 0xffff, 22 - 17, 0),
        /*  17 */ BPF_JUMP(BPF_JMP|BPF_JEQ|BPF_K, 0x0064FF9B, 22 - 18, 0),
        /*  18 */ BPF_JUMP(BPF_JMP|BPF_JEQ|BPF_K, 0, 41 - 19, 39 - 19),
        /*  19 */ BPF_STMT(BPF_LD|BPF_W|BPF_ABS, -1048576+(12)),
        /*  20 */ BPF_STMT(BPF_ALU|BPF_AND|BPF_K, 0xffff0000),
        /*  21 */ BPF_JUMP(BPF_JMP|BPF_JEQ|BPF_K, 0, 41 - 22, 39 - 22),
        /*  22 */ BPF_STMT(BPF_LDX|BPF_W|BPF_IMM, -1048576+(20)),
        /*  23 */ BPF_STMT(BPF_LD|BPF_W|BPF_IND, 0),
        /*  24 */ BPF_JUMP(BPF_JMP|BPF_JEQ|BPF_K, 0xffffffff, 41 - 25, 0),
        /*  25 */ BPF_STMT(BPF_ALU|BPF_AND|BPF_K, 0xffffff00),
        /*  26 */ BPF_JUMP(BPF_JMP|BPF_JEQ|BPF_K, 0xC0000000, 41 - 27, 0),
        /*  27 */ BPF_JUMP(BPF_JMP|BPF_JEQ|BPF_K, 0xC0000200, 41 - 28, 0),
        /*  28 */ BPF_JUMP(BPF_JMP|BPF_JEQ|BPF_K, 0xC6336400, 41 - 29, 0),
        /*  29 */ BPF_JUMP(BPF_JMP|BPF_JEQ|BPF_K, 0xCB007100, 41 - 30, 0),
        /*  30 */ BPF_JUMP(BPF_JMP|BPF_JEQ|BPF_K, 0xC0586300, 41 - 31, 0),
        /*  31 */ BPF_STMT(BPF_ALU|BPF_AND|BPF_K, 0xfffe0000),
        /*  32 */ BPF_JUMP(BPF_JMP|BPF_JEQ|BPF_K, 0xC6120000, 41 - 33, 0),
        /*  33 */ BPF_STMT(BPF_ALU|BPF_AND|BPF_K, 0xff000000),
        /*  34 */ BPF_JUMP(BPF_JMP|BPF_JEQ|BPF_K, 0, 41 - 35, 0),
        /*  35 */ BPF_STMT(BPF_ALU|BPF_AND|BPF_K, 0xf0000000),
        /*  36 */ BPF_JUMP(BPF_JMP|BPF_JEQ|BPF_K, 0xE0000000, 41 - 37, 0),
        /*  37 */ BPF_JUMP(BPF_JMP|BPF_JEQ|BPF_K, 0xF0000000, 41 - 38, 0),
        /*  38 */ BPF_JUMP(BPF_JMP|BPF_JA, 39 - 39, 0, 0),
        /*  39 */ BPF_STMT(BPF_LD|BPF_W|BPF_LEN, 0),
        /*  40 */ BPF_STMT(BPF_RET|BPF_A, 0),
        /*  41 */ BPF_STMT(BPF_RET|BPF_K, 0),
};

I already had that discussion with Eric, he said it is a valid use case.
http://marc.info/?l=linux-netdev&m=133296726719053&w=2

The patch for x86 is already in, ppc is being reviewed, i only heard of the arm jit to late, or you would have been in the loop from the beginning.

Then use the following test program (filter not usefull, just to show the problem):

#include <stdio.h>
#include <sys/types.h>
#include <sys/socket.h>
#include <netinet/in.h>
#include <pcap-bpf.h>

#define die(x) do {perror(x); return 1;} while (0)

struct bpf_insn udp_filter[] = {
	/*   0 */ BPF_STMT(BPF_LDX|BPF_W|BPF_IMM, -1048576+(0)), /* leax	net[0] */
	/*   1 */ BPF_STMT(BPF_LD|BPF_B|BPF_IND, 0),             /* ldb	[x+0] */
	/*   2 */ BPF_STMT(BPF_RET|BPF_A, 0),                    /* ret	a */
};

int main(int argc, char *argv[])

{
	char buf[512];
	struct sockaddr_in addr;
	struct bpf_program prg;
	socklen_t addr_s;
	ssize_t res;
	int fd;

	addr.sin_family = AF_INET;
	addr.sin_port = htons(5000);
	addr.sin_addr.s_addr = 0;
	addr_s = sizeof(addr);
	prg.bf_len = sizeof(udp_filter)/sizeof(udp_filter[0]);
	prg.bf_insns = udp_filter;
	if(-1 == (fd = socket(AF_INET, SOCK_DGRAM, 0)))
		die("socket");
	if(-1 == bind(fd, (struct sockaddr *)&addr, sizeof(addr)))
		die("bind");
	if(-1 == setsockopt(fd, SOL_SOCKET, SO_ATTACH_FILTER, &prg, sizeof(prg)))
		die("setsockopt");
	res = recvfrom(fd, buf, sizeof(buf), 0, (struct sockaddr *)&addr, &addr_s);
	if(res != -1)
		printf("packet received: %zi bytes\n", res);
	else
		die("recvfrom");
	return 0;
}

when used with the bpf jit disabled works:
console 1 $ ./bpf
console 2 $ echo "hello" | nc -u localhost 5000
console 1: packet received: 6 bytes

When the bpf jit gets enabled (echo 100 > /proc/sys/net/core/bpf_jit_enable) the same program stops working:
console 1 $ ./bpf
console 2 $ echo "hello" | nc -u localhost 5000
console 1:

This is a regression in the interface in my book.
The interpreter handles this perfectly fine.

Exactly, and how do i handle both at the same time? (The ancillary space contains not only cpu_id and such stuff, but the link layer header and the network space, which is important when you use LSF on arbitrary sockets, not just raw sockets, maybe the new syscall filter thingy also wants a new ancillary space)

Have some nice holidays :-)

Greetings
Jan

You are wrong.

Please carefully read net/core/filter.c its all here :

void *bpf_internal_load_pointer_neg_helper(const struct sk_buff *skb, int k, unsigned int size)

{
        u8 *ptr = NULL;

        if (k >= SKF_NET_OFF)
                ptr = skb_network_header(skb) + k - SKF_NET_OFF;
        else if (k >= SKF_LL_OFF)
                ptr = skb_mac_header(skb) + k - SKF_LL_OFF;

        if (ptr >= skb->head && ptr + size <= skb_tail_pointer(skb))
                return ptr;
        return NULL;
}

Then :

commit a998d4342337c82dacdc0897d30a9364de1576a1

Author: Jan Seiffert <[email protected]>
Date:   Fri Mar 30 05:24:05 2012 +0000

bpf jit: Let the x86 jit handle negative offsets

Now the helper function from filter.c for negative offsets is exported, it can be used it in the jit to handle negative offsets.

First modify the asm load helper functions to handle:
- know positive offsets
- know negative offsets
- any offset

then the compiler can be modified to explicitly use these helper when appropriate.

This fixes the case of a negative X register and allows to lift the restriction that bpf programs with negative offsets can't be jited.