Re: [tcpdump-workers] Modular arithmetic

Re: [tcpdump-workers] Modular arithmetic

[Andi Kleen]

On Fri, Sep 07, 2012 at 07:49:10AM +0000, George Bakos wrote:
> Gents,
> Any fundamental reason why the following (, etc.) shouldn't be
> included in net/core/filter.c?
> 
>                 case BPF_S_ALU_MOD_X:
>                         if (X == 0)
>                                 return 0;
>                         A %= X;
>                         continue;

Copying netdev.

In principle no reason against it, but you may need to update
the various BPF JITs too that Linux now has too.

-Andi

> 
> Cheers,
> g
> 
> On Thu, 6 Sep 2012 01:02:32 -0700
> Guy Harris <guy@alum.mit.edu> wrote:
> 
> > 
> > On Sep 6, 2012, at 12:36 AM, George Bakos wrote:
> > 
> > > $  tcpdump -nvr /tmp/DG2-test2 '(ip[2:2] - 20) % 5 != 0 && ip[6] &
> > > 0x20 = 0x20' 
> > > 
> > > reading from file /tmp/DG2-test2, link-type EN10MB (Ethernet)
> > > 19:01:51.270202 IP (tos 0x0, ttl 64, id 1, offset 40, flags [+],
> > > proto ICMP (1), length 61) 192.168.11.5 > 192.168.11.46: ip-proto-1
> > > 
> > > (000) ldh      [12]
> > > (001) jeq      #0x800           jt 2	jf 10
> > > (002) ldh      [16]
> > > (003) sub      #20
> > > (004) mod      #5
> > > (005) jeq      #0x0             jt 10	jf 6
> > 
> > OK, so you presumably added a BPF_MOD instruction to the BPF interpreter as part of your changes, right?  There's none in libpcap's bpf_filter.c nor in a fairly recent FreeBSD kernel's bpf_filter.c nor in Linux 3.0.4's net/core/filter.c, so that code won't work with at least those interpreters.
> > 
> > _______________________________________________
> > tcpdump-workers mailing list
> > tcpdump-workers@lists.tcpdump.org
> > https://lists.sandelman.ca/mailman/listinfo/tcpdump-workers
> 
> 
> -- 

-- 
ak@linux.intel.com -- Speaking for myself only

[PATCH net-next] filter: add MOD operation

[Eric Dumazet]

From: Eric Dumazet <edumazet@google.com>

On Fri, 2012-09-07 at 20:03 -0700, Andi Kleen wrote:
> On Fri, Sep 07, 2012 at 07:49:10AM +0000, George Bakos wrote:
> > Gents,
> > Any fundamental reason why the following (, etc.) shouldn't be
> > included in net/core/filter.c?
> > 
> >                 case BPF_S_ALU_MOD_X:
> >                         if (X == 0)
> >                                 return 0;
> >                         A %= X;
> >                         continue;
> 
> Copying netdev.
> 
> In principle no reason against it, but you may need to update
> the various BPF JITs too that Linux now has too.

Hi Andi, thanks for the forward

In recent commit ffe06c17afbb was added ALU_XOR_X,
so we could add ALU_MOD_X as well.

ALU_MOD_K is a bit more complex as we cant use an ancillary, and must
instead use a new BPF_OP code :

/* alu/jmp fields */
#define BPF_OP(code)    ((code) & 0xf0)
#define         BPF_ADD         0x00
#define         BPF_SUB         0x10
#define         BPF_MUL         0x20
#define         BPF_DIV         0x30
#define         BPF_OR          0x40
#define         BPF_AND         0x50
#define         BPF_LSH         0x60
#define         BPF_RSH         0x70
#define         BPF_NEG         0x80

So I guess we could use

#define         BPF_MOD         0x90

About the various arches JIT, there is no hurry :
We can update them later.

At JIT 'compile' time, if we find a not yet handled instruction, we fall
back to the net/core/filter.c interpreter.

If the following patch is accepted, I'll do the x86 part as a followup.

Thanks !

[PATCH net-next] filter: add MOD operation

Add a new ALU opcode, to compute a modulus.

Commit ffe06c17afbbb used an ancillary to implement XOR_X,
but here we reserve one of the available ALU opcode to implement both
MOD_X and MOD_K

Signed-off-by: Eric Dumazet <edumazet@google.com>
Suggested-by: George Bakos <gbakos@alpinista.org>
Cc: Jay Schulist <jschlst@samba.org>
Cc: Jiri Pirko <jpirko@redhat.com>
Cc: Andi Kleen <ak@linux.intel.com>
---
 include/linux/filter.h |    4 ++++
 net/core/filter.c      |   15 +++++++++++++++
 2 files changed, 19 insertions(+)

diff --git a/include/linux/filter.h b/include/linux/filter.h
index 82b0135..3cf5fd5 100644
--- a/include/linux/filter.h
+++ b/include/linux/filter.h
@@ -74,6 +74,8 @@ struct sock_fprog {	/* Required for SO_ATTACH_FILTER. */
 #define         BPF_LSH         0x60
 #define         BPF_RSH         0x70
 #define         BPF_NEG         0x80
+#define		BPF_MOD		0x90
+
 #define         BPF_JA          0x00
 #define         BPF_JEQ         0x10
 #define         BPF_JGT         0x20
@@ -196,6 +198,8 @@ enum {
 	BPF_S_ALU_MUL_K,
 	BPF_S_ALU_MUL_X,
 	BPF_S_ALU_DIV_X,
+	BPF_S_ALU_MOD_K,
+	BPF_S_ALU_MOD_X,
 	BPF_S_ALU_AND_K,
 	BPF_S_ALU_AND_X,
 	BPF_S_ALU_OR_K,
diff --git a/net/core/filter.c b/net/core/filter.c
index 907efd2..fbe3a8d 100644
--- a/net/core/filter.c
+++ b/net/core/filter.c
@@ -167,6 +167,14 @@ unsigned int sk_run_filter(const struct sk_buff *skb,
 		case BPF_S_ALU_DIV_K:
 			A = reciprocal_divide(A, K);
 			continue;
+		case BPF_S_ALU_MOD_X:
+			if (X == 0)
+				return 0;
+			A %= X;
+			continue;
+		case BPF_S_ALU_MOD_K:
+			A %= K;
+			continue;
 		case BPF_S_ALU_AND_X:
 			A &= X;
 			continue;
@@ -469,6 +477,8 @@ int sk_chk_filter(struct sock_filter *filter, unsigned int flen)
 		[BPF_ALU|BPF_MUL|BPF_K]  = BPF_S_ALU_MUL_K,
 		[BPF_ALU|BPF_MUL|BPF_X]  = BPF_S_ALU_MUL_X,
 		[BPF_ALU|BPF_DIV|BPF_X]  = BPF_S_ALU_DIV_X,
+		[BPF_ALU|BPF_MOD|BPF_K]  = BPF_S_ALU_MOD_K,
+		[BPF_ALU|BPF_MOD|BPF_X]  = BPF_S_ALU_MOD_X,
 		[BPF_ALU|BPF_AND|BPF_K]  = BPF_S_ALU_AND_K,
 		[BPF_ALU|BPF_AND|BPF_X]  = BPF_S_ALU_AND_X,
 		[BPF_ALU|BPF_OR|BPF_K]   = BPF_S_ALU_OR_K,
@@ -531,6 +541,11 @@ int sk_chk_filter(struct sock_filter *filter, unsigned int flen)
 				return -EINVAL;
 			ftest->k = reciprocal_value(ftest->k);
 			break;
+		case BPF_S_ALU_MOD_K:
+			/* check for division by zero */
+			if (ftest->k == 0)
+				return -EINVAL;
+			break;
 		case BPF_S_LD_MEM:
 		case BPF_S_LDX_MEM:
 		case BPF_S_ST:

Re: [PATCH net-next] filter: add MOD operation

[George Bakos]

[-- Attachment #1: Type: text/plain, Size: 4516 bytes --]

Here's a patch to libpcap-1.3 to test against. I still need to
include changes to man pages.

g

On Sat, 08 Sep 2012 10:03:35 +0200
Eric Dumazet <eric.dumazet@gmail.com> wrote:

> From: Eric Dumazet <edumazet@google.com>
> 
> On Fri, 2012-09-07 at 20:03 -0700, Andi Kleen wrote:
> > On Fri, Sep 07, 2012 at 07:49:10AM +0000, George Bakos wrote:
> > > Gents,
> > > Any fundamental reason why the following (, etc.) shouldn't be
> > > included in net/core/filter.c?
> > > 
> > >                 case BPF_S_ALU_MOD_X:
> > >                         if (X == 0)
> > >                                 return 0;
> > >                         A %= X;
> > >                         continue;
> > 
> > Copying netdev.
> > 
> > In principle no reason against it, but you may need to update
> > the various BPF JITs too that Linux now has too.
> 
> Hi Andi, thanks for the forward
> 
> In recent commit ffe06c17afbb was added ALU_XOR_X,
> so we could add ALU_MOD_X as well.
> 
> ALU_MOD_K is a bit more complex as we cant use an ancillary, and must
> instead use a new BPF_OP code :
> 
> /* alu/jmp fields */
> #define BPF_OP(code)    ((code) & 0xf0)
> #define         BPF_ADD         0x00
> #define         BPF_SUB         0x10
> #define         BPF_MUL         0x20
> #define         BPF_DIV         0x30
> #define         BPF_OR          0x40
> #define         BPF_AND         0x50
> #define         BPF_LSH         0x60
> #define         BPF_RSH         0x70
> #define         BPF_NEG         0x80
> 
> So I guess we could use
> 
> #define         BPF_MOD         0x90
> 
> About the various arches JIT, there is no hurry :
> We can update them later.
> 
> At JIT 'compile' time, if we find a not yet handled instruction, we fall
> back to the net/core/filter.c interpreter.
> 
> If the following patch is accepted, I'll do the x86 part as a followup.
> 
> Thanks !
> 
> [PATCH net-next] filter: add MOD operation
> 
> Add a new ALU opcode, to compute a modulus.
> 
> Commit ffe06c17afbbb used an ancillary to implement XOR_X,
> but here we reserve one of the available ALU opcode to implement both
> MOD_X and MOD_K
> 
> Signed-off-by: Eric Dumazet <edumazet@google.com>
> Suggested-by: George Bakos <gbakos@alpinista.org>
> Cc: Jay Schulist <jschlst@samba.org>
> Cc: Jiri Pirko <jpirko@redhat.com>
> Cc: Andi Kleen <ak@linux.intel.com>
> ---
>  include/linux/filter.h |    4 ++++
>  net/core/filter.c      |   15 +++++++++++++++
>  2 files changed, 19 insertions(+)
> 
> diff --git a/include/linux/filter.h b/include/linux/filter.h
> index 82b0135..3cf5fd5 100644
> --- a/include/linux/filter.h
> +++ b/include/linux/filter.h
> @@ -74,6 +74,8 @@ struct sock_fprog {	/* Required for SO_ATTACH_FILTER. */
>  #define         BPF_LSH         0x60
>  #define         BPF_RSH         0x70
>  #define         BPF_NEG         0x80
> +#define		BPF_MOD		0x90
> +
>  #define         BPF_JA          0x00
>  #define         BPF_JEQ         0x10
>  #define         BPF_JGT         0x20
> @@ -196,6 +198,8 @@ enum {
>  	BPF_S_ALU_MUL_K,
>  	BPF_S_ALU_MUL_X,
>  	BPF_S_ALU_DIV_X,
> +	BPF_S_ALU_MOD_K,
> +	BPF_S_ALU_MOD_X,
>  	BPF_S_ALU_AND_K,
>  	BPF_S_ALU_AND_X,
>  	BPF_S_ALU_OR_K,
> diff --git a/net/core/filter.c b/net/core/filter.c
> index 907efd2..fbe3a8d 100644
> --- a/net/core/filter.c
> +++ b/net/core/filter.c
> @@ -167,6 +167,14 @@ unsigned int sk_run_filter(const struct sk_buff *skb,
>  		case BPF_S_ALU_DIV_K:
>  			A = reciprocal_divide(A, K);
>  			continue;
> +		case BPF_S_ALU_MOD_X:
> +			if (X == 0)
> +				return 0;
> +			A %= X;
> +			continue;
> +		case BPF_S_ALU_MOD_K:
> +			A %= K;
> +			continue;
>  		case BPF_S_ALU_AND_X:
>  			A &= X;
>  			continue;
> @@ -469,6 +477,8 @@ int sk_chk_filter(struct sock_filter *filter, unsigned int flen)
>  		[BPF_ALU|BPF_MUL|BPF_K]  = BPF_S_ALU_MUL_K,
>  		[BPF_ALU|BPF_MUL|BPF_X]  = BPF_S_ALU_MUL_X,
>  		[BPF_ALU|BPF_DIV|BPF_X]  = BPF_S_ALU_DIV_X,
> +		[BPF_ALU|BPF_MOD|BPF_K]  = BPF_S_ALU_MOD_K,
> +		[BPF_ALU|BPF_MOD|BPF_X]  = BPF_S_ALU_MOD_X,
>  		[BPF_ALU|BPF_AND|BPF_K]  = BPF_S_ALU_AND_K,
>  		[BPF_ALU|BPF_AND|BPF_X]  = BPF_S_ALU_AND_X,
>  		[BPF_ALU|BPF_OR|BPF_K]   = BPF_S_ALU_OR_K,
> @@ -531,6 +541,11 @@ int sk_chk_filter(struct sock_filter *filter, unsigned int flen)
>  				return -EINVAL;
>  			ftest->k = reciprocal_value(ftest->k);
>  			break;
> +		case BPF_S_ALU_MOD_K:
> +			/* check for division by zero */
> +			if (ftest->k == 0)
> +				return -EINVAL;
> +			break;
>  		case BPF_S_LD_MEM:
>  		case BPF_S_LDX_MEM:
>  		case BPF_S_ST:
> 
> 


-- 

[-- Attachment #2: libpcap-1.3.0-with-modulus.patch --]
[-- Type: text/x-patch, Size: 4452 bytes --]

diff -Naur libpcap-1.3.0/bpf/net/bpf_filter.c libpcap-1.3.0-with-modulus/bpf/net/bpf_filter.c
--- libpcap-1.3.0/bpf/net/bpf_filter.c	2012-03-29 12:57:32.000000000 +0000
+++ libpcap-1.3.0-with-modulus/bpf/net/bpf_filter.c	2012-08-31 01:36:53.206825554 +0000
@@ -469,6 +469,12 @@
 			A /= X;
 			continue;
 
+		case BPF_ALU|BPF_MOD|BPF_X:
+			if (X == 0)
+				return 0;
+			A %= X;
+			continue;
+
 		case BPF_ALU|BPF_AND|BPF_X:
 			A &= X;
 			continue;
@@ -501,6 +507,10 @@
 			A /= pc->k;
 			continue;
 
+		case BPF_ALU|BPF_MOD|BPF_K:
+			A %= pc->k;
+			continue;
+
 		case BPF_ALU|BPF_AND|BPF_K:
 			A &= pc->k;
 			continue;
@@ -621,6 +631,13 @@
 				 */
 				if (BPF_SRC(p->code) == BPF_K && p->k == 0)
 					return 0;
+				break;
+			case BPF_MOD:
+				/*
+				 * Check for illegal modulus 0.
+				 */
+				if (BPF_SRC(p->code) == BPF_K && p->k == 0)
+					return 0;
 				break;
 			default:
 				return 0;
diff -Naur libpcap-1.3.0/bpf_image.c libpcap-1.3.0-with-modulus/bpf_image.c
--- libpcap-1.3.0/bpf_image.c	2012-03-29 12:57:32.000000000 +0000
+++ libpcap-1.3.0-with-modulus/bpf_image.c	2012-08-31 01:36:53.225825770 +0000
@@ -216,6 +216,11 @@
 		fmt = "x";
 		break;
 
+	case BPF_ALU|BPF_MOD|BPF_X:
+		op = "mod";
+		fmt = "x";
+		break;
+
 	case BPF_ALU|BPF_AND|BPF_X:
 		op = "and";
 		fmt = "x";
@@ -256,6 +261,11 @@
 		fmt = "#%d";
 		break;
 
+	case BPF_ALU|BPF_MOD|BPF_K:
+		op = "mod";
+		fmt = "#%d";
+		break;
+
 	case BPF_ALU|BPF_AND|BPF_K:
 		op = "and";
 		fmt = "#0x%x";
diff -Naur libpcap-1.3.0/grammar.y libpcap-1.3.0-with-modulus/grammar.y
--- libpcap-1.3.0/grammar.y	2012-03-29 12:57:32.000000000 +0000
+++ libpcap-1.3.0-with-modulus/grammar.y	2012-08-31 01:36:53.196825439 +0000
@@ -617,6 +617,7 @@
 	| arth '*' arth			{ $$ = gen_arth(BPF_MUL, $1, $3); }
 	| arth '/' arth			{ $$ = gen_arth(BPF_DIV, $1, $3); }
 	| arth '&' arth			{ $$ = gen_arth(BPF_AND, $1, $3); }
+	| arth '%' arth			{ $$ = gen_arth(BPF_MOD, $1, $3); }
 	| arth '|' arth			{ $$ = gen_arth(BPF_OR, $1, $3); }
 	| arth LSH arth			{ $$ = gen_arth(BPF_LSH, $1, $3); }
 	| arth RSH arth			{ $$ = gen_arth(BPF_RSH, $1, $3); }
diff -Naur libpcap-1.3.0/optimize.c libpcap-1.3.0-with-modulus/optimize.c
--- libpcap-1.3.0/optimize.c	2012-03-29 12:57:32.000000000 +0000
+++ libpcap-1.3.0-with-modulus/optimize.c	2012-08-31 01:36:53.188825347 +0000
@@ -666,6 +666,12 @@
 		a /= b;
 		break;
 
+	case BPF_MOD:
+		if (b == 0)
+			bpf_error("illegal modulus 0");
+		a %= b;
+		break;
+
 	case BPF_AND:
 		a &= b;
 		break;
@@ -1044,6 +1050,7 @@
 	case BPF_ALU|BPF_SUB|BPF_K:
 	case BPF_ALU|BPF_MUL|BPF_K:
 	case BPF_ALU|BPF_DIV|BPF_K:
+	case BPF_ALU|BPF_MOD|BPF_K:
 	case BPF_ALU|BPF_AND|BPF_K:
 	case BPF_ALU|BPF_OR|BPF_K:
 	case BPF_ALU|BPF_LSH|BPF_K:
@@ -1079,6 +1086,7 @@
 	case BPF_ALU|BPF_SUB|BPF_X:
 	case BPF_ALU|BPF_MUL|BPF_X:
 	case BPF_ALU|BPF_DIV|BPF_X:
+	case BPF_ALU|BPF_MOD|BPF_X:
 	case BPF_ALU|BPF_AND|BPF_X:
 	case BPF_ALU|BPF_OR|BPF_X:
 	case BPF_ALU|BPF_LSH|BPF_X:
@@ -1112,7 +1120,7 @@
 				vstore(s, &val[A_ATOM], val[X_ATOM], alter);
 				break;
 			}
-			else if (op == BPF_MUL || op == BPF_DIV ||
+			else if (op == BPF_MUL || op == BPF_DIV || op == BPF_MOD ||
 				 op == BPF_AND || op == BPF_LSH || op == BPF_RSH) {
 				s->code = BPF_LD|BPF_IMM;
 				s->k = 0;
diff -Naur libpcap-1.3.0/pcap/bpf.h libpcap-1.3.0-with-modulus/pcap/bpf.h
--- libpcap-1.3.0/pcap/bpf.h	2012-06-12 16:55:36.000000000 +0000
+++ libpcap-1.3.0-with-modulus/pcap/bpf.h	2012-08-31 01:36:53.199825471 +0000
@@ -1235,6 +1235,7 @@
 #define		BPF_LSH		0x60
 #define		BPF_RSH		0x70
 #define		BPF_NEG		0x80
+#define		BPF_MOD		0x90
 #define		BPF_JA		0x00
 #define		BPF_JEQ		0x10
 #define		BPF_JGT		0x20
diff -Naur libpcap-1.3.0/scanner.l libpcap-1.3.0-with-modulus/scanner.l
--- libpcap-1.3.0/scanner.l	2012-03-29 12:57:32.000000000 +0000
+++ libpcap-1.3.0-with-modulus/scanner.l	2012-08-31 01:36:53.225825770 +0000
@@ -329,7 +329,7 @@
 sls		return SLS;
 
 [ \r\n\t]		;
-[+\-*/:\[\]!<>()&|=]	return yytext[0];
+[+\-*/:\[\]!<>()&|=%]	return yytext[0];
 ">="			return GEQ;
 "<="			return LEQ;
 "!="			return NEQ;
@@ -387,7 +387,7 @@
 [A-Za-z0-9]([-_.A-Za-z0-9]*[.A-Za-z0-9])? {
 			 yylval.s = sdup((char *)yytext); return ID; }
 "\\"[^ !()\n\t]+	{ yylval.s = sdup((char *)yytext + 1); return ID; }
-[^ \[\]\t\n\-_.A-Za-z0-9!<>()&|=]+ {
+[^ \[\]\t\n\-_.A-Za-z0-9!<>()&|=%]+ {
 			bpf_error("illegal token: %s", yytext); }
 .			{ bpf_error("illegal char '%c'", *yytext); }
 %%

[-- Attachment #3: Type: text/plain, Size: 171 bytes --]

_______________________________________________
tcpdump-workers mailing list
tcpdump-workers@lists.tcpdump.org
https://lists.sandelman.ca/mailman/listinfo/tcpdump-workers

RE: [tcpdump-workers] Modular arithmetic

[David Laight]

> On Fri, Sep 07, 2012 at 07:49:10AM +0000, George Bakos wrote:
> > Gents,
> > Any fundamental reason why the following (, etc.) shouldn't be
> > included in net/core/filter.c?
> >
> >                 case BPF_S_ALU_MOD_X:
> >                         if (X == 0)
> >                                 return 0;
> >                         A %= X;
> >                         continue;
> 
> Copying netdev.
> 
> In principle no reason against it, but you may need to update
> the various BPF JITs too that Linux now has too.

What about the other OS - eg all the BSDs?
I had a vague idea that BPF was supposed to be reasonable portable.

	David    (dsl@netbsd.org)

RE: [tcpdump-workers] Modular arithmetic

[Eric Dumazet]

On Mon, 2012-09-10 at 09:41 +0100, David Laight wrote:
> > On Fri, Sep 07, 2012 at 07:49:10AM +0000, George Bakos wrote:
> > > Gents,
> > > Any fundamental reason why the following (, etc.) shouldn't be
> > > included in net/core/filter.c?
> > >
> > >                 case BPF_S_ALU_MOD_X:
> > >                         if (X == 0)
> > >                                 return 0;
> > >                         A %= X;
> > >                         continue;
> > 
> > Copying netdev.
> > 
> > In principle no reason against it, but you may need to update
> > the various BPF JITs too that Linux now has too.
> 
> What about the other OS - eg all the BSDs?
> I had a vague idea that BPF was supposed to be reasonable portable.

Yes, does it mean BPF is frozen ?

Or is BSD so hard to update these days ?

modulus can be implemented using fallback to div and sub, I am not sure
libpcap should sense kernel support or not.

George, make sure libpcap optimizer correctly replaces MOD X  by AND (X
- 1) if X is a power of two.

Re: Modular arithmetic

[David Laight]

> > What about the other OS - eg all the BSDs?
> > I had a vague idea that BPF was supposed to be reasonable portable.
> 
> Yes, does it mean BPF is frozen ?
> 
> Or is BSD so hard to update these days ?

Not really - but it some other places that need updating in order
to make this useful for cross-platform tools (like tcpdump).

The 'real fun (tm)' happens when NetBSD tries to run Linux binaries
that include the Linux libpcap.

	David
_______________________________________________
tcpdump-workers mailing list
tcpdump-workers@lists.tcpdump.org
https://lists.sandelman.ca/mailman/listinfo/tcpdump-workers

Re: [tcpdump-workers] Modular arithmetic

[Daniel Borkmann]

On Mon, Sep 10, 2012 at 12:41 PM, David Laight <David.Laight@aculab.com> wrote:
>> > What about the other OS - eg all the BSDs?
>> > I had a vague idea that BPF was supposed to be reasonable portable.
>>
>> Yes, does it mean BPF is frozen ?
>>
>> Or is BSD so hard to update these days ?
>
> Not really - but it some other places that need updating in order
> to make this useful for cross-platform tools (like tcpdump).
>
> The 'real fun (tm)' happens when NetBSD tries to run Linux binaries
> that include the Linux libpcap.

Correct me if I'm wrong, but if you want to run the _Linux_ version of
libpcap, then you would also need PF_PACKET's RX_RING API in NetBSD.
Otherwise, it doesn't run either. Probably then this BPF instruction
is the smaller problem for NetBSD.

Re: [tcpdump-workers] Modular arithmetic

[Andi Kleen]

> What about the other OS - eg all the BSDs?
> I had a vague idea that BPF was supposed to be reasonable portable.

Linux already has a variety of BPF extensions I believe.
But most of them were not targetted for tcpdump, but for other tools.

-Andi
-- 
ak@linux.intel.com -- Speaking for myself only

Re: Modular arithmetic

[Guy Harris]

On Sep 10, 2012, at 3:41 AM, "David Laight" <David.Laight@ACULAB.COM> wrote:

>>> What about the other OS - eg all the BSDs?
>>> I had a vague idea that BPF was supposed to be reasonable portable.
>> 
>> Yes, does it mean BPF is frozen ?
>> 
>> Or is BSD so hard to update these days ?
> 
> Not really - but it some other places that need updating in order
> to make this useful for cross-platform tools (like tcpdump).
> 
> The 'real fun (tm)' happens when NetBSD tries to run Linux binaries
> that include the Linux libpcap.

Additional fun happens when a Linux system with a kernel that doesn't have the mod instruction tries to run Linux binaries that include a Linux libpcap that generates code using the mod instruction; this is not a BSD-vs.-Linux issue, it's a "kernel that lacks the mod instruction vs. libpcap that generates code that includes the mod instruction" issue.

BSD/OS X, Linux, Solaris, and the WinPcap driver need, if they adopt new BPF instructions, to have a mechanism by which libpcap (or anything else using BPF filtering) can inquire about the capabilities of the OS BPF interpreter; libpcap would use that to determine what code to generate if generating code for the in-kernel BPF interpreter.

(Please reply to tcpdump-workers@lists.tcpdump.org as well as to netdev@vger.kernel.org, so that people not on both of those lists can follow the discussion.  Messages from non-members of tcpdump-workers to tcpdump-workers shouldn't bounce, but they do need to be approved by a moderator; Michael, if you want to at least temporarily turn the flood on for my e-mail address, so I can help moderate, go ahead.)
_______________________________________________
tcpdump-workers mailing list
tcpdump-workers@lists.tcpdump.org
https://lists.sandelman.ca/mailman/listinfo/tcpdump-workers

Re: [PATCH net-next] filter: add MOD operation

[David Miller]

From: Eric Dumazet <eric.dumazet@gmail.com>
Date: Sat, 08 Sep 2012 10:03:35 +0200

> From: Eric Dumazet <edumazet@google.com>
 ...
> [PATCH net-next] filter: add MOD operation
> 
> Add a new ALU opcode, to compute a modulus.
> 
> Commit ffe06c17afbbb used an ancillary to implement XOR_X,
> but here we reserve one of the available ALU opcode to implement both
> MOD_X and MOD_K
> 
> Signed-off-by: Eric Dumazet <edumazet@google.com>
> Suggested-by: George Bakos <gbakos@alpinista.org>
> Cc: Jay Schulist <jschlst@samba.org>
> Cc: Jiri Pirko <jpirko@redhat.com>
> Cc: Andi Kleen <ak@linux.intel.com>

Applied to net-next, thanks.

[PATCH net-next] x86 bpf_jit: support MOD operation

[Eric Dumazet]

From: Eric Dumazet <edumazet@google.com>

commit b6069a9570 (filter: add MOD operation) added generic
support for modulus operation in BPF.

This patch brings JIT support for x86_64

Signed-off-by: Eric Dumazet <edumazet@google.com>
Cc: Andi Kleen <ak@linux.intel.com>
Cc: George Bakos <gbakos@alpinista.org>
---
 arch/x86/net/bpf_jit_comp.c |   25 +++++++++++++++++++++++++
 1 file changed, 25 insertions(+)

diff --git a/arch/x86/net/bpf_jit_comp.c b/arch/x86/net/bpf_jit_comp.c
index 33643a8..106c578 100644
--- a/arch/x86/net/bpf_jit_comp.c
+++ b/arch/x86/net/bpf_jit_comp.c
@@ -280,6 +280,31 @@ void bpf_jit_compile(struct sk_filter *fp)
 				}
 				EMIT4(0x31, 0xd2, 0xf7, 0xf3); /* xor %edx,%edx; div %ebx */
 				break;
+			case BPF_S_ALU_MOD_X: /* A %= X; */
+				seen |= SEEN_XREG;
+				EMIT2(0x85, 0xdb);	/* test %ebx,%ebx */
+				if (pc_ret0 > 0) {
+					/* addrs[pc_ret0 - 1] is start address of target
+					 * (addrs[i] - 6) is the address following this jmp
+					 * ("xor %edx,%edx; div %ebx;mov %edx,%eax" being 6 bytes long)
+					 */
+					EMIT_COND_JMP(X86_JE, addrs[pc_ret0 - 1] -
+								(addrs[i] - 6));
+				} else {
+					EMIT_COND_JMP(X86_JNE, 2 + 5);
+					CLEAR_A();
+					EMIT1_off32(0xe9, cleanup_addr - (addrs[i] - 6)); /* jmp .+off32 */
+				}
+				EMIT2(0x31, 0xd2);	/* xor %edx,%edx */
+				EMIT2(0xf7, 0xf3);	/* div %ebx */
+				EMIT2(0x89, 0xd0);	/* mov %edx,%eax */
+				break;
+			case BPF_S_ALU_MOD_K: /* A %= K; */
+				EMIT2(0x31, 0xd2);	/* xor %edx,%edx */
+				EMIT1(0xb9);EMIT(K, 4);	/* mov imm32,%ecx */
+				EMIT2(0xf7, 0xf1);	/* div %ecx */
+				EMIT2(0x89, 0xd0);	/* mov %edx,%eax */
+				break;
 			case BPF_S_ALU_DIV_K: /* A = reciprocal_divide(A, K); */
 				EMIT3(0x48, 0x69, 0xc0); /* imul imm32,%rax,%rax */
 				EMIT(K, 4);

Re: [PATCH net-next] x86 bpf_jit: support MOD operation

[David Miller]

From: Eric Dumazet <eric.dumazet@gmail.com>
Date: Mon, 10 Sep 2012 22:48:33 +0200

> From: Eric Dumazet <edumazet@google.com>
> 
> commit b6069a9570 (filter: add MOD operation) added generic
> support for modulus operation in BPF.
> 
> This patch brings JIT support for x86_64
> 
> Signed-off-by: Eric Dumazet <edumazet@google.com>

Applied, thanks Eric.

Re: Modular arithmetic

[Guy Harris]

On Sep 10, 2012, at 10:50 AM, Guy Harris <guy@alum.mit.edu> wrote:

> 
> On Sep 10, 2012, at 3:41 AM, "David Laight" <David.Laight@ACULAB.COM> wrote:
> 
>>>> What about the other OS - eg all the BSDs?
>>>> I had a vague idea that BPF was supposed to be reasonable portable.
>>> 
>>> Yes, does it mean BPF is frozen ?
>>> 
>>> Or is BSD so hard to update these days ?
>> 
>> Not really - but it some other places that need updating in order
>> to make this useful for cross-platform tools (like tcpdump).
>> 
>> The 'real fun (tm)' happens when NetBSD tries to run Linux binaries
>> that include the Linux libpcap.
> 
> Additional fun happens when a Linux system with a kernel that doesn't have the mod instruction tries to run Linux binaries that include a Linux libpcap that generates code using the mod instruction; this is not a BSD-vs.-Linux issue, it's a "kernel that lacks the mod instruction vs. libpcap that generates code that includes the mod instruction" issue.
> 
> BSD/OS X, Linux, Solaris, and the WinPcap driver need, if they adopt new BPF instructions, to have a mechanism by which libpcap (or anything else using BPF filtering) can inquire about the capabilities of the OS BPF interpreter; libpcap would use that to determine what code to generate if generating code for the in-kernel BPF interpreter.

In this particular case, there's no choice about what to generate - either you have mod and XOR instructions or you don't.

Furthermore, if the kernel rejects a particular BPF program, libpcap just falls back on filtering in userland, so we can support % and ^ operators in libpcap on all platforms, albeit with a performance hit on Linux prior to 3.7 and, currently, on other platforms.  I don't think there's anything inherently troublesome about BPF_MOD and BPF_XOR, so I'll file bugs against the various BSDs and OS X suggesting that they be added.

So I've checked in a change to libpcap to implement BPF_MOD and BPF_XOR and to add % and ^ operators (yes, the same zero-divide checks in bpf_validate() done for BPF_DIV are done for BPF_MOD, and the optimizer was updated to handle BPF_MOD like BPF_DIV and to handle BPF_XOR like BPF_OR).  The pcap-filter man page documents it, but warns that filters using them might be run in userland on pre-3.7 Linux and non-Linux platforms.
_______________________________________________
tcpdump-workers mailing list
tcpdump-workers@lists.tcpdump.org
https://lists.sandelman.ca/mailman/listinfo/tcpdump-workers