Skip to contentSkip to conversation

Modular arithmetic

tcpdump-workers Applied Andi Kleen 7 participants 13 messages Sep 8, 2012 – May 18, 2014 5 messages not in the archive

Subsystems (7)
Networking Network drivers x86 BPF +3 more subsystems
lore
Share & tools
lore

Andi Kleen

author
#5 lore raw
In reply to a message not in the archive
Quoted 9 lines · George Bakos

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

Quoted 33 lines

Cheers,
g

Quoted 23 lines · On Thu, 6 Sep 2012 01:02:32 -0700 Guy Harris <[email protected]> wrote:
Quoted 7 lines · George Bakos
$  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

Quoted 6 lines
(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
[email protected]
https://lists.sandelman.ca/mailman/listinfo/tcpdump-workers

Signature · 1 line
[email protected] -- Speaking for myself only
#6 lore raw

PATCH 1/1 filter: add MOD operation

From: Eric Dumazet <[email protected]>

Quoted 11 lines · Andi Kleen
Quoted 9 lines · George Bakos

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;
Quoted 4 lines

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

---
 include/linux/filter.h |    4 ++++
 net/core/filter.c      |   15 +++++++++++++++
 2 files changed, 19 insertions(+)
include/linux/filter.h +4 -0
index 82b0135..3cf5fd5 100644
@@ -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,
net/core/filter.c +15 -0
index 907efd2..fbe3a8d 100644
@@ -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:
#7 lore raw

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

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

g

Quoted 135 lines · On Sat, 08 Sep 2012 10:03:35 +0200 Eric Dumazet <[email protected]> wrote:

From: Eric Dumazet <[email protected]>

Quoted 11 lines · Andi Kleen
Quoted 9 lines · George Bakos

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;
Quoted 4 lines

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

---
 include/linux/filter.h |    4 ++++
 net/core/filter.c      |   15 +++++++++++++++
 2 files changed, 19 insertions(+)
include/linux/filter.h +4 -0
index 82b0135..3cf5fd5 100644
@@ -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,
net/core/filter.c +15 -0
index 907efd2..fbe3a8d 100644
@@ -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:
bpf/net/bpf_filter.c +17 -0
diff -Naur libpcap-1.3.0/bpf/net/bpf_filter.c libpcap-1.3.0-with-modulus/bpf/net/bpf_filter.c
@@ -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;
bpf_image.c +10 -0
diff -Naur libpcap-1.3.0/bpf_image.c libpcap-1.3.0-with-modulus/bpf_image.c
@@ -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";
grammar.y +1 -0
diff -Naur libpcap-1.3.0/grammar.y libpcap-1.3.0-with-modulus/grammar.y
@@ -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); }
optimize.c +9 -1
diff -Naur libpcap-1.3.0/optimize.c libpcap-1.3.0-with-modulus/optimize.c
@@ -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;
pcap/bpf.h +1 -0
diff -Naur libpcap-1.3.0/pcap/bpf.h libpcap-1.3.0-with-modulus/pcap/bpf.h
@@ -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
scanner.l +2 -2
diff -Naur libpcap-1.3.0/scanner.l libpcap-1.3.0-with-modulus/scanner.l
@@ -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); }
 %%

_______________________________________________
tcpdump-workers mailing list
[email protected]
https://lists.sandelman.ca/mailman/listinfo/tcpdump-workers

#11 lore raw
In reply to Andi Kleen
Quoted 11 lines · George Bakos
Quoted 9 lines

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;
Quoted 4 lines

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 ([email protected])

#12 lore raw
Quoted 11 lines · David Laight
Quoted 11 lines · George Bakos
Quoted 9 lines

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;
Quoted 7 lines
Quoted 4 lines

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.

#13 lore raw
Quoted 6 lines
Quoted 2 lines

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
[email protected]
https://lists.sandelman.ca/mailman/listinfo/tcpdump-workers

#14 lore raw
Quoted 5 lines · David Laight
Quoted 5 lines
Quoted 2 lines

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 ?

Quoted 7 lines
Quoted 1 line

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.

author
#17 lore raw
In reply to David Laight
Quoted 2 lines

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

Signature · 1 line
[email protected] -- Speaking for myself only
#15 lore raw
In reply to David Laight
Quoted 5 lines · David Laight
Quoted 5 lines
Quoted 2 lines

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 ?

Quoted 7 lines
Quoted 1 line

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 [email protected] as well as to [email protected], 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
[email protected]
https://lists.sandelman.ca/mailman/listinfo/tcpdump-workers

maintainer Applied
#8 lore raw

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

In reply to Eric Dumazet

From: Eric Dumazet <[email protected]>
Date: Sat, 08 Sep 2012 10:03:35 +0200

Quoted 1 line

From: Eric Dumazet <[email protected]>

...

Quoted 8 lines

[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

Quoted 5 lines

Applied to net-next, thanks.

#9 lore raw

PATCH 1/1 x86 bpf_jit: support MOD operation

From: Eric Dumazet <[email protected]>

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

This patch brings JIT support for x86_64

Cc Andi Kleen <[email protected]>
Cc George Bakos <[email protected]>
---
 arch/x86/net/bpf_jit_comp.c |   25 +++++++++++++++++++++++++
 1 file changed, 25 insertions(+)
arch/x86/net/bpf_jit_comp.c +25 -0
index 33643a8..106c578 100644
@@ -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);
maintainer Applied
#10 lore raw

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

From: Eric Dumazet <[email protected]>
Date: Mon, 10 Sep 2012 22:48:33 +0200

Quoted 8 lines

From: Eric Dumazet <[email protected]>

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

This patch brings JIT support for x86_64

Applied, thanks Eric.

#16 lore raw
In reply to Guy Harris
Quoted 13 lines · Guy Harris
Quoted 10 lines · David Laight
Quoted 6 lines
Quoted 2 lines

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).

Quoted 6 lines
Quoted 2 lines

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
[email protected]
https://lists.sandelman.ca/mailman/listinfo/tcpdump-workers