* Re: [tcpdump-workers] Modular arithmetic [not found] ` <20120907074910.2df46817@arrowsmith> @ 2012-09-08 3:03 ` Andi Kleen 2012-09-08 8:03 ` [PATCH net-next] filter: add MOD operation Eric Dumazet 2012-09-10 8:41 ` [tcpdump-workers] Modular arithmetic David Laight 0 siblings, 2 replies; 13+ messages in thread From: Andi Kleen @ 2012-09-08 3:03 UTC (permalink / raw) To: George Bakos; +Cc: Jay Schulist, netdev 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 ^ permalink raw reply [flat|nested] 13+ messages in thread
* [PATCH net-next] filter: add MOD operation 2012-09-08 3:03 ` [tcpdump-workers] Modular arithmetic Andi Kleen @ 2012-09-08 8:03 ` Eric Dumazet 2012-09-08 20:31 ` George Bakos 2012-09-10 19:45 ` David Miller 2012-09-10 8:41 ` [tcpdump-workers] Modular arithmetic David Laight 1 sibling, 2 replies; 13+ messages in thread From: Eric Dumazet @ 2012-09-08 8:03 UTC (permalink / raw) To: Andi Kleen; +Cc: George Bakos, Jay Schulist, netdev 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: ^ permalink raw reply related [flat|nested] 13+ messages in thread
* Re: [PATCH net-next] filter: add MOD operation 2012-09-08 8:03 ` [PATCH net-next] filter: add MOD operation Eric Dumazet @ 2012-09-08 20:31 ` George Bakos 2012-09-10 19:45 ` David Miller 1 sibling, 0 replies; 13+ messages in thread From: George Bakos @ 2012-09-08 20:31 UTC (permalink / raw) To: Eric Dumazet; +Cc: netdev, Jay Schulist, Andi Kleen, tcpdump-workers [-- 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 ^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: [PATCH net-next] filter: add MOD operation 2012-09-08 8:03 ` [PATCH net-next] filter: add MOD operation Eric Dumazet 2012-09-08 20:31 ` George Bakos @ 2012-09-10 19:45 ` David Miller 2012-09-10 20:48 ` [PATCH net-next] x86 bpf_jit: support " Eric Dumazet 1 sibling, 1 reply; 13+ messages in thread From: David Miller @ 2012-09-10 19:45 UTC (permalink / raw) To: eric.dumazet; +Cc: ak, gbakos, jschlst, netdev 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. ^ permalink raw reply [flat|nested] 13+ messages in thread
* [PATCH net-next] x86 bpf_jit: support MOD operation 2012-09-10 19:45 ` David Miller @ 2012-09-10 20:48 ` Eric Dumazet 2012-09-10 21:09 ` David Miller 0 siblings, 1 reply; 13+ messages in thread From: Eric Dumazet @ 2012-09-10 20:48 UTC (permalink / raw) To: David Miller; +Cc: ak, gbakos, netdev 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); ^ permalink raw reply related [flat|nested] 13+ messages in thread
* Re: [PATCH net-next] x86 bpf_jit: support MOD operation 2012-09-10 20:48 ` [PATCH net-next] x86 bpf_jit: support " Eric Dumazet @ 2012-09-10 21:09 ` David Miller 0 siblings, 0 replies; 13+ messages in thread From: David Miller @ 2012-09-10 21:09 UTC (permalink / raw) To: eric.dumazet; +Cc: ak, gbakos, netdev 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. ^ permalink raw reply [flat|nested] 13+ messages in thread
* RE: [tcpdump-workers] Modular arithmetic 2012-09-08 3:03 ` [tcpdump-workers] Modular arithmetic Andi Kleen 2012-09-08 8:03 ` [PATCH net-next] filter: add MOD operation Eric Dumazet @ 2012-09-10 8:41 ` David Laight 2012-09-10 9:25 ` Eric Dumazet 2012-09-10 14:49 ` [tcpdump-workers] " Andi Kleen 1 sibling, 2 replies; 13+ messages in thread From: David Laight @ 2012-09-10 8:41 UTC (permalink / raw) To: Andi Kleen, George Bakos, tcpdump-workers; +Cc: Jay Schulist, netdev > 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) ^ permalink raw reply [flat|nested] 13+ messages in thread
* RE: [tcpdump-workers] Modular arithmetic 2012-09-10 8:41 ` [tcpdump-workers] Modular arithmetic David Laight @ 2012-09-10 9:25 ` Eric Dumazet 2012-09-10 10:41 ` David Laight 2012-09-10 14:49 ` [tcpdump-workers] " Andi Kleen 1 sibling, 1 reply; 13+ messages in thread From: Eric Dumazet @ 2012-09-10 9:25 UTC (permalink / raw) To: David Laight Cc: Andi Kleen, George Bakos, tcpdump-workers, Jay Schulist, netdev 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. ^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: Modular arithmetic 2012-09-10 9:25 ` Eric Dumazet @ 2012-09-10 10:41 ` David Laight 2012-09-10 11:49 ` [tcpdump-workers] " Daniel Borkmann 2012-09-10 17:50 ` Guy Harris 0 siblings, 2 replies; 13+ messages in thread From: David Laight @ 2012-09-10 10:41 UTC (permalink / raw) To: Eric Dumazet; +Cc: netdev, Jay Schulist, Andi Kleen, tcpdump-workers > > 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 ^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: [tcpdump-workers] Modular arithmetic 2012-09-10 10:41 ` David Laight @ 2012-09-10 11:49 ` Daniel Borkmann 2012-09-10 17:50 ` Guy Harris 1 sibling, 0 replies; 13+ messages in thread From: Daniel Borkmann @ 2012-09-10 11:49 UTC (permalink / raw) To: David Laight Cc: Eric Dumazet, Andi Kleen, George Bakos, tcpdump-workers, Jay Schulist, netdev 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. ^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: Modular arithmetic 2012-09-10 10:41 ` David Laight 2012-09-10 11:49 ` [tcpdump-workers] " Daniel Borkmann @ 2012-09-10 17:50 ` Guy Harris 2014-05-18 18:26 ` Guy Harris 1 sibling, 1 reply; 13+ messages in thread From: Guy Harris @ 2012-09-10 17:50 UTC (permalink / raw) To: David Laight Cc: netdev, Jay Schulist, Andi Kleen, tcpdump-workers, Eric Dumazet 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 ^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: Modular arithmetic 2012-09-10 17:50 ` Guy Harris @ 2014-05-18 18:26 ` Guy Harris 0 siblings, 0 replies; 13+ messages in thread From: Guy Harris @ 2014-05-18 18:26 UTC (permalink / raw) To: Guy Harris Cc: Andi Kleen, Eric Dumazet, netdev, tcpdump-workers, Jay Schulist 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 ^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: [tcpdump-workers] Modular arithmetic 2012-09-10 8:41 ` [tcpdump-workers] Modular arithmetic David Laight 2012-09-10 9:25 ` Eric Dumazet @ 2012-09-10 14:49 ` Andi Kleen 1 sibling, 0 replies; 13+ messages in thread From: Andi Kleen @ 2012-09-10 14:49 UTC (permalink / raw) To: David Laight; +Cc: George Bakos, tcpdump-workers, Jay Schulist, netdev > 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 ^ permalink raw reply [flat|nested] 13+ messages in thread
end of thread, other threads:[~2014-05-18 18:26 UTC | newest]
Thread overview: 13+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
[not found] <20120905213941.03c85968@arrowsmith>
[not found] ` <C71A36A8-08D2-4D3D-AF2B-EF89FEECE1A6@alum.mit.edu>
[not found] ` <20120906073615.693d14e0@arrowsmith>
[not found] ` <46AB14E3-73F4-41FA-8086-F1D663AF4549@alum.mit.edu>
[not found] ` <20120907074910.2df46817@arrowsmith>
2012-09-08 3:03 ` [tcpdump-workers] Modular arithmetic Andi Kleen
2012-09-08 8:03 ` [PATCH net-next] filter: add MOD operation Eric Dumazet
2012-09-08 20:31 ` George Bakos
2012-09-10 19:45 ` David Miller
2012-09-10 20:48 ` [PATCH net-next] x86 bpf_jit: support " Eric Dumazet
2012-09-10 21:09 ` David Miller
2012-09-10 8:41 ` [tcpdump-workers] Modular arithmetic David Laight
2012-09-10 9:25 ` Eric Dumazet
2012-09-10 10:41 ` David Laight
2012-09-10 11:49 ` [tcpdump-workers] " Daniel Borkmann
2012-09-10 17:50 ` Guy Harris
2014-05-18 18:26 ` Guy Harris
2012-09-10 14:49 ` [tcpdump-workers] " Andi Kleen
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for NNTP newsgroup(s).