[PATCH] filter: added BPF random opcode

[PATCH] filter: added BPF random opcode

[Chema Gonzalez]

This should allow random packet sampling.

Signed-off-by: Chema Gonzalez <chema@google.com>
---
 Documentation/networking/filter.txt | 13 +++++++++++++
 include/linux/filter.h              |  1 +
 include/uapi/linux/filter.h         |  3 ++-
 net/core/filter.c                   | 12 ++++++++++++
 tools/net/bpf_exp.l                 |  1 +
 tools/net/bpf_exp.y                 | 11 ++++++++++-
 6 files changed, 39 insertions(+), 2 deletions(-)

diff --git a/Documentation/networking/filter.txt b/Documentation/networking/filter.txt
index 81f940f..82e1cb0 100644
--- a/Documentation/networking/filter.txt
+++ b/Documentation/networking/filter.txt
@@ -281,6 +281,7 @@ Possible BPF extensions are shown in the following table:
   cpu                                   raw_smp_processor_id()
   vlan_tci                              vlan_tx_tag_get(skb)
   vlan_pr                               vlan_tx_tag_present(skb)
+  rand                                  prandom_u32()
 
 These extensions can also be prefixed with '#'.
 Examples for low-level BPF:
@@ -308,6 +309,18 @@ Examples for low-level BPF:
   ret #-1
   drop: ret #0
 
+** icmp random packet sampling, 1 in 4
+  ldh [12]
+  jne #0x800, drop
+  ldb [23]
+  jneq #1, drop
+  # get a random uint32 number
+  ld rand
+  mod #4
+  jneq #1, drop
+  ret #-1
+  drop: ret #0
+
 ** SECCOMP filter example:
 
   ld [4]                  /* offsetof(struct seccomp_data, arch) */
diff --git a/include/linux/filter.h b/include/linux/filter.h
index 262dcbb..49c28aa 100644
--- a/include/linux/filter.h
+++ b/include/linux/filter.h
@@ -224,6 +224,7 @@ enum {
 	BPF_S_ANC_VLAN_TAG,
 	BPF_S_ANC_VLAN_TAG_PRESENT,
 	BPF_S_ANC_PAY_OFFSET,
+	BPF_S_ANC_RANDOM,
 };
 
 #endif /* __LINUX_FILTER_H__ */
diff --git a/include/uapi/linux/filter.h b/include/uapi/linux/filter.h
index 8eb9cca..253b4d4 100644
--- a/include/uapi/linux/filter.h
+++ b/include/uapi/linux/filter.h
@@ -130,7 +130,8 @@ struct sock_fprog {	/* Required for SO_ATTACH_FILTER. */
 #define SKF_AD_VLAN_TAG	44
 #define SKF_AD_VLAN_TAG_PRESENT 48
 #define SKF_AD_PAY_OFFSET	52
-#define SKF_AD_MAX	56
+#define SKF_AD_RANDOM	56
+#define SKF_AD_MAX	60
 #define SKF_NET_OFF   (-0x100000)
 #define SKF_LL_OFF    (-0x200000)
 
diff --git a/net/core/filter.c b/net/core/filter.c
index 765556b..b2a80a1 100644
--- a/net/core/filter.c
+++ b/net/core/filter.c
@@ -637,6 +637,12 @@ static u64 __get_raw_cpu_id(u64 ctx, u64 A, u64 X, u64 r4, u64 r5)
 	return raw_smp_processor_id();
 }
 
+/* note that this only generates 32-bit random numbers */
+static u64 __skb_get_random(u64 ctx, u64 A, u64 X, u64 r4, u64 r5)
+{
+	return (u64)prandom_u32();
+}
+
 /* Register mappings for user programs. */
 #define A_REG		0
 #define X_REG		7
@@ -773,6 +779,7 @@ static bool convert_bpf_extensions(struct sock_filter *fp,
 	case SKF_AD_OFF + SKF_AD_NLATTR:
 	case SKF_AD_OFF + SKF_AD_NLATTR_NEST:
 	case SKF_AD_OFF + SKF_AD_CPU:
+	case SKF_AD_OFF + SKF_AD_RANDOM:
 		/* arg1 = ctx */
 		insn->code = BPF_ALU64 | BPF_MOV | BPF_X;
 		insn->a_reg = ARG1_REG;
@@ -806,6 +813,9 @@ static bool convert_bpf_extensions(struct sock_filter *fp,
 		case SKF_AD_OFF + SKF_AD_CPU:
 			insn->imm = __get_raw_cpu_id - __bpf_call_base;
 			break;
+		case SKF_AD_OFF + SKF_AD_RANDOM:
+			insn->imm = __skb_get_random - __bpf_call_base;
+			break;
 		}
 		break;
 
@@ -1356,6 +1366,7 @@ int sk_chk_filter(struct sock_filter *filter, unsigned int flen)
 			ANCILLARY(VLAN_TAG);
 			ANCILLARY(VLAN_TAG_PRESENT);
 			ANCILLARY(PAY_OFFSET);
+			ANCILLARY(RANDOM);
 			}
 
 			/* ancillary operation unknown or unsupported */
@@ -1741,6 +1752,7 @@ void sk_decode_filter(struct sock_filter *filt, struct sock_filter *to)
 		[BPF_S_ANC_VLAN_TAG]	= BPF_LD|BPF_B|BPF_ABS,
 		[BPF_S_ANC_VLAN_TAG_PRESENT] = BPF_LD|BPF_B|BPF_ABS,
 		[BPF_S_ANC_PAY_OFFSET]	= BPF_LD|BPF_B|BPF_ABS,
+		[BPF_S_ANC_RANDOM]	= BPF_LD|BPF_B|BPF_ABS,
 		[BPF_S_LD_W_LEN]	= BPF_LD|BPF_W|BPF_LEN,
 		[BPF_S_LD_W_IND]	= BPF_LD|BPF_W|BPF_IND,
 		[BPF_S_LD_H_IND]	= BPF_LD|BPF_H|BPF_IND,
diff --git a/tools/net/bpf_exp.l b/tools/net/bpf_exp.l
index bf7be77..833a966 100644
--- a/tools/net/bpf_exp.l
+++ b/tools/net/bpf_exp.l
@@ -92,6 +92,7 @@ extern void yyerror(const char *str);
 "#"?("cpu")	{ return K_CPU; }
 "#"?("vlan_tci") { return K_VLANT; }
 "#"?("vlan_pr")	{ return K_VLANP; }
+"#"?("rand")	{ return K_RAND; }
 
 ":"		{ return ':'; }
 ","		{ return ','; }
diff --git a/tools/net/bpf_exp.y b/tools/net/bpf_exp.y
index d15efc9..e6306c5 100644
--- a/tools/net/bpf_exp.y
+++ b/tools/net/bpf_exp.y
@@ -56,7 +56,7 @@ static void bpf_set_jmp_label(char *label, enum jmp_type type);
 %token OP_LDXI
 
 %token K_PKT_LEN K_PROTO K_TYPE K_NLATTR K_NLATTR_NEST K_MARK K_QUEUE K_HATYPE
-%token K_RXHASH K_CPU K_IFIDX K_VLANT K_VLANP K_POFF
+%token K_RXHASH K_CPU K_IFIDX K_VLANT K_VLANP K_POFF K_RAND
 
 %token ':' ',' '[' ']' '(' ')' 'x' 'a' '+' 'M' '*' '&' '#' '%'
 
@@ -164,6 +164,9 @@ ldb
 	| OP_LDB K_POFF {
 		bpf_set_curr_instr(BPF_LD | BPF_B | BPF_ABS, 0, 0,
 				   SKF_AD_OFF + SKF_AD_PAY_OFFSET); }
+	| OP_LDB K_RAND {
+		bpf_set_curr_instr(BPF_LD | BPF_B | BPF_ABS, 0, 0,
+				   SKF_AD_OFF + SKF_AD_RANDOM); }
 	;
 
 ldh
@@ -212,6 +215,9 @@ ldh
 	| OP_LDH K_POFF {
 		bpf_set_curr_instr(BPF_LD | BPF_H | BPF_ABS, 0, 0,
 				   SKF_AD_OFF + SKF_AD_PAY_OFFSET); }
+	| OP_LDH K_RAND {
+		bpf_set_curr_instr(BPF_LD | BPF_H | BPF_ABS, 0, 0,
+				   SKF_AD_OFF + SKF_AD_RANDOM); }
 	;
 
 ldi
@@ -265,6 +271,9 @@ ld
 	| OP_LD K_POFF {
 		bpf_set_curr_instr(BPF_LD | BPF_W | BPF_ABS, 0, 0,
 				   SKF_AD_OFF + SKF_AD_PAY_OFFSET); }
+	| OP_LD K_RAND {
+		bpf_set_curr_instr(BPF_LD | BPF_W | BPF_ABS, 0, 0,
+				   SKF_AD_OFF + SKF_AD_RANDOM); }
 	| OP_LD 'M' '[' number ']' {
 		bpf_set_curr_instr(BPF_LD | BPF_MEM, 0, 0, $4); }
 	| OP_LD '[' 'x' '+' number ']' {
-- 
1.9.1.423.g4596e3a

Re: [PATCH] filter: added BPF random opcode

[Alexei Starovoitov]

On Tue, Apr 15, 2014 at 11:16 AM, Chema Gonzalez <chema@google.com> wrote:
> This should allow random packet sampling.

I think commit log should have more than one line,
especially for the new feature that affects uapi

In particular I don't find the reason of moving random
packet sampling into kernel to be that great.
pcap cannot receive them quickly enough anyway,
so there are drops already.
Just randomly pick packets that reached the user space.
Why add this to the kernel? I don't see how it can improve accuracy.

At the same time I think the extension technic itself is nice and clean :)
The call approach is definitely how we envisioned it to be used.
Right now we have only x86-64 jit that is waiting for net-next to be opened,
but this extension will be automatically jit-ed due to 'call approach'. Nice.

When you post patch revision please add vN tag.

Minor nits below:

> Signed-off-by: Chema Gonzalez <chema@google.com>
> ---
>  Documentation/networking/filter.txt | 13 +++++++++++++
>  include/linux/filter.h              |  1 +
>  include/uapi/linux/filter.h         |  3 ++-
>  net/core/filter.c                   | 12 ++++++++++++
>  tools/net/bpf_exp.l                 |  1 +
>  tools/net/bpf_exp.y                 | 11 ++++++++++-
>  6 files changed, 39 insertions(+), 2 deletions(-)
>
> diff --git a/Documentation/networking/filter.txt b/Documentation/networking/filter.txt
> index 81f940f..82e1cb0 100644
> --- a/Documentation/networking/filter.txt
> +++ b/Documentation/networking/filter.txt
> @@ -281,6 +281,7 @@ Possible BPF extensions are shown in the following table:
>    cpu                                   raw_smp_processor_id()
>    vlan_tci                              vlan_tx_tag_get(skb)
>    vlan_pr                               vlan_tx_tag_present(skb)
> +  rand                                  prandom_u32()
>
>  These extensions can also be prefixed with '#'.
>  Examples for low-level BPF:
> @@ -308,6 +309,18 @@ Examples for low-level BPF:
>    ret #-1
>    drop: ret #0
>
> +** icmp random packet sampling, 1 in 4
> +  ldh [12]
> +  jne #0x800, drop
> +  ldb [23]
> +  jneq #1, drop
> +  # get a random uint32 number
> +  ld rand
> +  mod #4
> +  jneq #1, drop
> +  ret #-1
> +  drop: ret #0
> +
>  ** SECCOMP filter example:
>
>    ld [4]                  /* offsetof(struct seccomp_data, arch) */
> diff --git a/include/linux/filter.h b/include/linux/filter.h
> index 262dcbb..49c28aa 100644
> --- a/include/linux/filter.h
> +++ b/include/linux/filter.h
> @@ -224,6 +224,7 @@ enum {
>         BPF_S_ANC_VLAN_TAG,
>         BPF_S_ANC_VLAN_TAG_PRESENT,
>         BPF_S_ANC_PAY_OFFSET,
> +       BPF_S_ANC_RANDOM,
>  };
>
>  #endif /* __LINUX_FILTER_H__ */
> diff --git a/include/uapi/linux/filter.h b/include/uapi/linux/filter.h
> index 8eb9cca..253b4d4 100644
> --- a/include/uapi/linux/filter.h
> +++ b/include/uapi/linux/filter.h
> @@ -130,7 +130,8 @@ struct sock_fprog { /* Required for SO_ATTACH_FILTER. */
>  #define SKF_AD_VLAN_TAG        44
>  #define SKF_AD_VLAN_TAG_PRESENT 48
>  #define SKF_AD_PAY_OFFSET      52
> -#define SKF_AD_MAX     56
> +#define SKF_AD_RANDOM  56
> +#define SKF_AD_MAX     60
>  #define SKF_NET_OFF   (-0x100000)
>  #define SKF_LL_OFF    (-0x200000)
>
> diff --git a/net/core/filter.c b/net/core/filter.c
> index 765556b..b2a80a1 100644
> --- a/net/core/filter.c
> +++ b/net/core/filter.c
> @@ -637,6 +637,12 @@ static u64 __get_raw_cpu_id(u64 ctx, u64 A, u64 X, u64 r4, u64 r5)
>         return raw_smp_processor_id();
>  }
>
> +/* note that this only generates 32-bit random numbers */
> +static u64 __skb_get_random(u64 ctx, u64 A, u64 X, u64 r4, u64 r5)

function name is misleading. It has nothing to do with 'skb'. Please
drop that prefix.

> +{
> +       return (u64)prandom_u32();

we have 64-bit registers now, so would be nice to generalize it to 64-bit random
since 8/16/32 can be made with bpf_and operation.
but I don't see how to cleanly do it yet, so I guess the current form is fine.

I like the approach, but would be nice to hear better justification
for extending uapi.

Thanks!

> +}
> +
>  /* Register mappings for user programs. */
>  #define A_REG          0
>  #define X_REG          7
> @@ -773,6 +779,7 @@ static bool convert_bpf_extensions(struct sock_filter *fp,
>         case SKF_AD_OFF + SKF_AD_NLATTR:
>         case SKF_AD_OFF + SKF_AD_NLATTR_NEST:
>         case SKF_AD_OFF + SKF_AD_CPU:
> +       case SKF_AD_OFF + SKF_AD_RANDOM:
>                 /* arg1 = ctx */
>                 insn->code = BPF_ALU64 | BPF_MOV | BPF_X;
>                 insn->a_reg = ARG1_REG;
> @@ -806,6 +813,9 @@ static bool convert_bpf_extensions(struct sock_filter *fp,
>                 case SKF_AD_OFF + SKF_AD_CPU:
>                         insn->imm = __get_raw_cpu_id - __bpf_call_base;
>                         break;
> +               case SKF_AD_OFF + SKF_AD_RANDOM:
> +                       insn->imm = __skb_get_random - __bpf_call_base;
> +                       break;
>                 }
>                 break;
>
> @@ -1356,6 +1366,7 @@ int sk_chk_filter(struct sock_filter *filter, unsigned int flen)
>                         ANCILLARY(VLAN_TAG);
>                         ANCILLARY(VLAN_TAG_PRESENT);
>                         ANCILLARY(PAY_OFFSET);
> +                       ANCILLARY(RANDOM);
>                         }
>
>                         /* ancillary operation unknown or unsupported */
> @@ -1741,6 +1752,7 @@ void sk_decode_filter(struct sock_filter *filt, struct sock_filter *to)
>                 [BPF_S_ANC_VLAN_TAG]    = BPF_LD|BPF_B|BPF_ABS,
>                 [BPF_S_ANC_VLAN_TAG_PRESENT] = BPF_LD|BPF_B|BPF_ABS,
>                 [BPF_S_ANC_PAY_OFFSET]  = BPF_LD|BPF_B|BPF_ABS,
> +               [BPF_S_ANC_RANDOM]      = BPF_LD|BPF_B|BPF_ABS,
>                 [BPF_S_LD_W_LEN]        = BPF_LD|BPF_W|BPF_LEN,
>                 [BPF_S_LD_W_IND]        = BPF_LD|BPF_W|BPF_IND,
>                 [BPF_S_LD_H_IND]        = BPF_LD|BPF_H|BPF_IND,
> diff --git a/tools/net/bpf_exp.l b/tools/net/bpf_exp.l
> index bf7be77..833a966 100644
> --- a/tools/net/bpf_exp.l
> +++ b/tools/net/bpf_exp.l
> @@ -92,6 +92,7 @@ extern void yyerror(const char *str);
>  "#"?("cpu")    { return K_CPU; }
>  "#"?("vlan_tci") { return K_VLANT; }
>  "#"?("vlan_pr")        { return K_VLANP; }
> +"#"?("rand")   { return K_RAND; }
>
>  ":"            { return ':'; }
>  ","            { return ','; }
> diff --git a/tools/net/bpf_exp.y b/tools/net/bpf_exp.y
> index d15efc9..e6306c5 100644
> --- a/tools/net/bpf_exp.y
> +++ b/tools/net/bpf_exp.y
> @@ -56,7 +56,7 @@ static void bpf_set_jmp_label(char *label, enum jmp_type type);
>  %token OP_LDXI
>
>  %token K_PKT_LEN K_PROTO K_TYPE K_NLATTR K_NLATTR_NEST K_MARK K_QUEUE K_HATYPE
> -%token K_RXHASH K_CPU K_IFIDX K_VLANT K_VLANP K_POFF
> +%token K_RXHASH K_CPU K_IFIDX K_VLANT K_VLANP K_POFF K_RAND
>
>  %token ':' ',' '[' ']' '(' ')' 'x' 'a' '+' 'M' '*' '&' '#' '%'
>
> @@ -164,6 +164,9 @@ ldb
>         | OP_LDB K_POFF {
>                 bpf_set_curr_instr(BPF_LD | BPF_B | BPF_ABS, 0, 0,
>                                    SKF_AD_OFF + SKF_AD_PAY_OFFSET); }
> +       | OP_LDB K_RAND {
> +               bpf_set_curr_instr(BPF_LD | BPF_B | BPF_ABS, 0, 0,
> +                                  SKF_AD_OFF + SKF_AD_RANDOM); }
>         ;
>
>  ldh
> @@ -212,6 +215,9 @@ ldh
>         | OP_LDH K_POFF {
>                 bpf_set_curr_instr(BPF_LD | BPF_H | BPF_ABS, 0, 0,
>                                    SKF_AD_OFF + SKF_AD_PAY_OFFSET); }
> +       | OP_LDH K_RAND {
> +               bpf_set_curr_instr(BPF_LD | BPF_H | BPF_ABS, 0, 0,
> +                                  SKF_AD_OFF + SKF_AD_RANDOM); }
>         ;
>
>  ldi
> @@ -265,6 +271,9 @@ ld
>         | OP_LD K_POFF {
>                 bpf_set_curr_instr(BPF_LD | BPF_W | BPF_ABS, 0, 0,
>                                    SKF_AD_OFF + SKF_AD_PAY_OFFSET); }
> +       | OP_LD K_RAND {
> +               bpf_set_curr_instr(BPF_LD | BPF_W | BPF_ABS, 0, 0,
> +                                  SKF_AD_OFF + SKF_AD_RANDOM); }
>         | OP_LD 'M' '[' number ']' {
>                 bpf_set_curr_instr(BPF_LD | BPF_MEM, 0, 0, $4); }
>         | OP_LD '[' 'x' '+' number ']' {
> --
> 1.9.1.423.g4596e3a
>

Re: [PATCH] filter: added BPF random opcode

[Daniel Borkmann]

On 04/16/2014 08:24 AM, Alexei Starovoitov wrote:
...
> At the same time I think the extension technic itself is nice and clean :)
> The call approach is definitely how we envisioned it to be used.
> Right now we have only x86-64 jit that is waiting for net-next to be opened,
> but this extension will be automatically jit-ed due to 'call approach'. Nice.

Ok, in terms of JIT it's definitely better that way, agreed.

Re: [PATCH] filter: added BPF random opcode

[Chema Gonzalez]

On Tue, Apr 15, 2014 at 11:24 PM, Alexei Starovoitov <ast@plumgrid.com> wrote:
> On Tue, Apr 15, 2014 at 11:16 AM, Chema Gonzalez <chema@google.com> wrote:
>> This should allow random packet sampling.
>
> I think commit log should have more than one line,
> especially for the new feature that affects uapi
I will beef it up in the next version (this time I'll wait for the
net-next window to open).

> In particular I don't find the reason of moving random
> packet sampling into kernel to be that great.
> pcap cannot receive them quickly enough anyway,
> so there are drops already.
> Just randomly pick packets that reached the user space.
> Why add this to the kernel? I don't see how it can improve accuracy.
The main use I see for this is random packet sampling. If you're
getting packet drops in pcap, you definitely want the kernel to do the
sampling. Sampling the packets that survived all the way through
userspace instead of the packets that arrived to the nic is biased.

The new message will be:

"""
filter: added BPF random opcode

Added a new ancillary load (bpf call in eBPF parlance) that produces
a 32-bit random number. We are implementing it as an ancillary load
(instead of an ISA opcode) because (a) it is simpler, (b) allows easy
JITing, and (c) seems more in line with generic ISAs that do not have
"get a random number" as a instruction, but as an OS call.

The main use for this ancillary load is to perform random packet sampling.
"""

> At the same time I think the extension technic itself is nice and clean :)
> The call approach is definitely how we envisioned it to be used.
> Right now we have only x86-64 jit that is waiting for net-next to be opened,
> but this extension will be automatically jit-ed due to 'call approach'. Nice.
>
> When you post patch revision please add vN tag.
I will.

>> +/* note that this only generates 32-bit random numbers */
>> +static u64 __skb_get_random(u64 ctx, u64 A, u64 X, u64 r4, u64 r5)
>
> function name is misleading. It has nothing to do with 'skb'. Please
> drop that prefix.
I renamed the function "__get_random_u32".

>> +{
>> +       return (u64)prandom_u32();
>
> we have 64-bit registers now, so would be nice to generalize it to 64-bit random
> since 8/16/32 can be made with bpf_and operation.
> but I don't see how to cleanly do it yet, so I guess the current form is fine.
>
> I like the approach, but would be nice to hear better justification
> for extending uapi.

-Chema

Re: [PATCH] filter: added BPF random opcode

[Eric Dumazet]

On Tue, 2014-04-15 at 23:24 -0700, Alexei Starovoitov wrote:

> In particular I don't find the reason of moving random
> packet sampling into kernel to be that great.
> pcap cannot receive them quickly enough anyway,
> so there are drops already.
> Just randomly pick packets that reached the user space.
> Why add this to the kernel? I don't see how it can improve accuracy.

It has nothing to do with speed or accuracy.

Being able to intercept 0.001 % of the packets (and not 0.001 % of the
flows...) can be useful to network operators.

_Then_ if its super super super fast, thats better, of course.

Suggesting to intercept all packets, then filtering 99.999 % of them in
user space is not going to work. Its going to be super super super slow.

Re: [PATCH] filter: added BPF random opcode

[Alexei Starovoitov]

On Wed, Apr 16, 2014 at 6:38 PM, Eric Dumazet <eric.dumazet@gmail.com> wrote:
> On Tue, 2014-04-15 at 23:24 -0700, Alexei Starovoitov wrote:
>
>> In particular I don't find the reason of moving random
>> packet sampling into kernel to be that great.
>> pcap cannot receive them quickly enough anyway,
>> so there are drops already.
>> Just randomly pick packets that reached the user space.
>> Why add this to the kernel? I don't see how it can improve accuracy.
>
> It has nothing to do with speed or accuracy.
>
> Being able to intercept 0.001 % of the packets (and not 0.001 % of the
> flows...) can be useful to network operators.
>
> _Then_ if its super super super fast, thats better, of course.
>
> Suggesting to intercept all packets, then filtering 99.999 % of them in
> user space is not going to work. Its going to be super super super slow.

correct.
I was suggesting user space approach, because example does:
+  ld rand
+  mod #4
+  jneq #1, drop

If 4 is replaced with rate of packets per second and which can be
roughly estimated before creating the filter, then this example would
make sense.
On a loaded server the rate will be in tens of millions, but when it idles
this fixed rand()%1000000==1 won't be sending anything to
userspace for hours.

I suspect adding 'ld rand' just 'felt' useful and no real
filters were created with it.
For true packet sampling 'ld getnstime' would be needed too.
As I said I like the approach, I just want to see a real use case for it.

[PATCH v2] filter: added BPF random opcode

[Chema Gonzalez]

Added a new ancillary load (bpf call in eBPF parlance) that produces
a 32-bit random number. We are implementing it as an ancillary load
(instead of an ISA opcode) because (a) it is simpler, (b) allows easy
JITing, and (c) seems more in line with generic ISAs that do not have
"get a random number" as a instruction, but as an OS call.

The main use for this ancillary load is to perform random packet sampling.

Signed-off-by: Chema Gonzalez <chema@google.com>
---
 Documentation/networking/filter.txt | 13 +++++++++++++
 include/linux/filter.h              |  1 +
 include/uapi/linux/filter.h         |  3 ++-
 net/core/filter.c                   | 12 ++++++++++++
 tools/net/bpf_exp.l                 |  1 +
 tools/net/bpf_exp.y                 | 11 ++++++++++-
 6 files changed, 39 insertions(+), 2 deletions(-)

diff --git a/Documentation/networking/filter.txt b/Documentation/networking/filter.txt
index 81f940f..82e1cb0 100644
--- a/Documentation/networking/filter.txt
+++ b/Documentation/networking/filter.txt
@@ -281,6 +281,7 @@ Possible BPF extensions are shown in the following table:
   cpu                                   raw_smp_processor_id()
   vlan_tci                              vlan_tx_tag_get(skb)
   vlan_pr                               vlan_tx_tag_present(skb)
+  rand                                  prandom_u32()
 
 These extensions can also be prefixed with '#'.
 Examples for low-level BPF:
@@ -308,6 +309,18 @@ Examples for low-level BPF:
   ret #-1
   drop: ret #0
 
+** icmp random packet sampling, 1 in 4
+  ldh [12]
+  jne #0x800, drop
+  ldb [23]
+  jneq #1, drop
+  # get a random uint32 number
+  ld rand
+  mod #4
+  jneq #1, drop
+  ret #-1
+  drop: ret #0
+
 ** SECCOMP filter example:
 
   ld [4]                  /* offsetof(struct seccomp_data, arch) */
diff --git a/include/linux/filter.h b/include/linux/filter.h
index 024fd03..759abf7 100644
--- a/include/linux/filter.h
+++ b/include/linux/filter.h
@@ -223,6 +223,7 @@ enum {
 	BPF_S_ANC_VLAN_TAG,
 	BPF_S_ANC_VLAN_TAG_PRESENT,
 	BPF_S_ANC_PAY_OFFSET,
+	BPF_S_ANC_RANDOM,
 };
 
 #endif /* __LINUX_FILTER_H__ */
diff --git a/include/uapi/linux/filter.h b/include/uapi/linux/filter.h
index 8eb9cca..253b4d4 100644
--- a/include/uapi/linux/filter.h
+++ b/include/uapi/linux/filter.h
@@ -130,7 +130,8 @@ struct sock_fprog {	/* Required for SO_ATTACH_FILTER. */
 #define SKF_AD_VLAN_TAG	44
 #define SKF_AD_VLAN_TAG_PRESENT 48
 #define SKF_AD_PAY_OFFSET	52
-#define SKF_AD_MAX	56
+#define SKF_AD_RANDOM	56
+#define SKF_AD_MAX	60
 #define SKF_NET_OFF   (-0x100000)
 #define SKF_LL_OFF    (-0x200000)
 
diff --git a/net/core/filter.c b/net/core/filter.c
index cd58614..78a636e 100644
--- a/net/core/filter.c
+++ b/net/core/filter.c
@@ -643,6 +643,12 @@ static u64 __get_raw_cpu_id(u64 ctx, u64 A, u64 X, u64 r4, u64 r5)
 	return raw_smp_processor_id();
 }
 
+/* note that this only generates 32-bit random numbers */
+static u64 __get_random_u32(u64 ctx, u64 A, u64 X, u64 r4, u64 r5)
+{
+	return (u64)prandom_u32();
+}
+
 /* Register mappings for user programs. */
 #define A_REG		0
 #define X_REG		7
@@ -779,6 +785,7 @@ static bool convert_bpf_extensions(struct sock_filter *fp,
 	case SKF_AD_OFF + SKF_AD_NLATTR:
 	case SKF_AD_OFF + SKF_AD_NLATTR_NEST:
 	case SKF_AD_OFF + SKF_AD_CPU:
+	case SKF_AD_OFF + SKF_AD_RANDOM:
 		/* arg1 = ctx */
 		insn->code = BPF_ALU64 | BPF_MOV | BPF_X;
 		insn->a_reg = ARG1_REG;
@@ -812,6 +819,9 @@ static bool convert_bpf_extensions(struct sock_filter *fp,
 		case SKF_AD_OFF + SKF_AD_CPU:
 			insn->imm = __get_raw_cpu_id - __bpf_call_base;
 			break;
+		case SKF_AD_OFF + SKF_AD_RANDOM:
+			insn->imm = __get_random_u32 - __bpf_call_base;
+			break;
 		}
 		break;
 
@@ -1362,6 +1372,7 @@ int sk_chk_filter(struct sock_filter *filter, unsigned int flen)
 			ANCILLARY(VLAN_TAG);
 			ANCILLARY(VLAN_TAG_PRESENT);
 			ANCILLARY(PAY_OFFSET);
+			ANCILLARY(RANDOM);
 			}
 
 			/* ancillary operation unknown or unsupported */
@@ -1746,6 +1757,7 @@ void sk_decode_filter(struct sock_filter *filt, struct sock_filter *to)
 		[BPF_S_ANC_VLAN_TAG]	= BPF_LD|BPF_B|BPF_ABS,
 		[BPF_S_ANC_VLAN_TAG_PRESENT] = BPF_LD|BPF_B|BPF_ABS,
 		[BPF_S_ANC_PAY_OFFSET]	= BPF_LD|BPF_B|BPF_ABS,
+		[BPF_S_ANC_RANDOM]	= BPF_LD|BPF_B|BPF_ABS,
 		[BPF_S_LD_W_LEN]	= BPF_LD|BPF_W|BPF_LEN,
 		[BPF_S_LD_W_IND]	= BPF_LD|BPF_W|BPF_IND,
 		[BPF_S_LD_H_IND]	= BPF_LD|BPF_H|BPF_IND,
diff --git a/tools/net/bpf_exp.l b/tools/net/bpf_exp.l
index bf7be77..833a966 100644
--- a/tools/net/bpf_exp.l
+++ b/tools/net/bpf_exp.l
@@ -92,6 +92,7 @@ extern void yyerror(const char *str);
 "#"?("cpu")	{ return K_CPU; }
 "#"?("vlan_tci") { return K_VLANT; }
 "#"?("vlan_pr")	{ return K_VLANP; }
+"#"?("rand")	{ return K_RAND; }
 
 ":"		{ return ':'; }
 ","		{ return ','; }
diff --git a/tools/net/bpf_exp.y b/tools/net/bpf_exp.y
index d15efc9..e6306c5 100644
--- a/tools/net/bpf_exp.y
+++ b/tools/net/bpf_exp.y
@@ -56,7 +56,7 @@ static void bpf_set_jmp_label(char *label, enum jmp_type type);
 %token OP_LDXI
 
 %token K_PKT_LEN K_PROTO K_TYPE K_NLATTR K_NLATTR_NEST K_MARK K_QUEUE K_HATYPE
-%token K_RXHASH K_CPU K_IFIDX K_VLANT K_VLANP K_POFF
+%token K_RXHASH K_CPU K_IFIDX K_VLANT K_VLANP K_POFF K_RAND
 
 %token ':' ',' '[' ']' '(' ')' 'x' 'a' '+' 'M' '*' '&' '#' '%'
 
@@ -164,6 +164,9 @@ ldb
 	| OP_LDB K_POFF {
 		bpf_set_curr_instr(BPF_LD | BPF_B | BPF_ABS, 0, 0,
 				   SKF_AD_OFF + SKF_AD_PAY_OFFSET); }
+	| OP_LDB K_RAND {
+		bpf_set_curr_instr(BPF_LD | BPF_B | BPF_ABS, 0, 0,
+				   SKF_AD_OFF + SKF_AD_RANDOM); }
 	;
 
 ldh
@@ -212,6 +215,9 @@ ldh
 	| OP_LDH K_POFF {
 		bpf_set_curr_instr(BPF_LD | BPF_H | BPF_ABS, 0, 0,
 				   SKF_AD_OFF + SKF_AD_PAY_OFFSET); }
+	| OP_LDH K_RAND {
+		bpf_set_curr_instr(BPF_LD | BPF_H | BPF_ABS, 0, 0,
+				   SKF_AD_OFF + SKF_AD_RANDOM); }
 	;
 
 ldi
@@ -265,6 +271,9 @@ ld
 	| OP_LD K_POFF {
 		bpf_set_curr_instr(BPF_LD | BPF_W | BPF_ABS, 0, 0,
 				   SKF_AD_OFF + SKF_AD_PAY_OFFSET); }
+	| OP_LD K_RAND {
+		bpf_set_curr_instr(BPF_LD | BPF_W | BPF_ABS, 0, 0,
+				   SKF_AD_OFF + SKF_AD_RANDOM); }
 	| OP_LD 'M' '[' number ']' {
 		bpf_set_curr_instr(BPF_LD | BPF_MEM, 0, 0, $4); }
 	| OP_LD '[' 'x' '+' number ']' {
-- 
1.9.1.423.g4596e3a

Re: [PATCH v2] filter: added BPF random opcode

[Alexei Starovoitov]

On Mon, Apr 21, 2014 at 9:21 AM, Chema Gonzalez <chema@google.com> wrote:
> Added a new ancillary load (bpf call in eBPF parlance) that produces
> a 32-bit random number. We are implementing it as an ancillary load
> (instead of an ISA opcode) because (a) it is simpler, (b) allows easy
> JITing, and (c) seems more in line with generic ISAs that do not have
> "get a random number" as a instruction, but as an OS call.
>
> The main use for this ancillary load is to perform random packet sampling.
>
> Signed-off-by: Chema Gonzalez <chema@google.com>
> ---
>  Documentation/networking/filter.txt | 13 +++++++++++++
>  include/linux/filter.h              |  1 +
>  include/uapi/linux/filter.h         |  3 ++-
>  net/core/filter.c                   | 12 ++++++++++++
>  tools/net/bpf_exp.l                 |  1 +
>  tools/net/bpf_exp.y                 | 11 ++++++++++-
>  6 files changed, 39 insertions(+), 2 deletions(-)
>
> diff --git a/Documentation/networking/filter.txt b/Documentation/networking/filter.txt
> index 81f940f..82e1cb0 100644
> --- a/Documentation/networking/filter.txt
> +++ b/Documentation/networking/filter.txt
> @@ -281,6 +281,7 @@ Possible BPF extensions are shown in the following table:
>    cpu                                   raw_smp_processor_id()
>    vlan_tci                              vlan_tx_tag_get(skb)
>    vlan_pr                               vlan_tx_tag_present(skb)
> +  rand                                  prandom_u32()
>
>  These extensions can also be prefixed with '#'.
>  Examples for low-level BPF:
> @@ -308,6 +309,18 @@ Examples for low-level BPF:
>    ret #-1
>    drop: ret #0
>
> +** icmp random packet sampling, 1 in 4
> +  ldh [12]
> +  jne #0x800, drop
> +  ldb [23]
> +  jneq #1, drop
> +  # get a random uint32 number
> +  ld rand
> +  mod #4
> +  jneq #1, drop

as I was saying in the other thread, would be nice to see more
realistic example, since "icmp 1 in 4" can be done in user space...
What is the real problem being solved?
I suspect for true packet sampling you'd need to have the knowledge
of packet rate, potentially computing time delta within filter with
another extension?
The patch itself looks good to me.

> +  ret #-1
> +  drop: ret #0
> +
>  ** SECCOMP filter example:
>
>    ld [4]                  /* offsetof(struct seccomp_data, arch) */
> diff --git a/include/linux/filter.h b/include/linux/filter.h
> index 024fd03..759abf7 100644
> --- a/include/linux/filter.h
> +++ b/include/linux/filter.h
> @@ -223,6 +223,7 @@ enum {
>         BPF_S_ANC_VLAN_TAG,
>         BPF_S_ANC_VLAN_TAG_PRESENT,
>         BPF_S_ANC_PAY_OFFSET,
> +       BPF_S_ANC_RANDOM,
>  };
>
>  #endif /* __LINUX_FILTER_H__ */
> diff --git a/include/uapi/linux/filter.h b/include/uapi/linux/filter.h
> index 8eb9cca..253b4d4 100644
> --- a/include/uapi/linux/filter.h
> +++ b/include/uapi/linux/filter.h
> @@ -130,7 +130,8 @@ struct sock_fprog { /* Required for SO_ATTACH_FILTER. */
>  #define SKF_AD_VLAN_TAG        44
>  #define SKF_AD_VLAN_TAG_PRESENT 48
>  #define SKF_AD_PAY_OFFSET      52
> -#define SKF_AD_MAX     56
> +#define SKF_AD_RANDOM  56
> +#define SKF_AD_MAX     60
>  #define SKF_NET_OFF   (-0x100000)
>  #define SKF_LL_OFF    (-0x200000)
>
> diff --git a/net/core/filter.c b/net/core/filter.c
> index cd58614..78a636e 100644
> --- a/net/core/filter.c
> +++ b/net/core/filter.c
> @@ -643,6 +643,12 @@ static u64 __get_raw_cpu_id(u64 ctx, u64 A, u64 X, u64 r4, u64 r5)
>         return raw_smp_processor_id();
>  }
>
> +/* note that this only generates 32-bit random numbers */
> +static u64 __get_random_u32(u64 ctx, u64 A, u64 X, u64 r4, u64 r5)
> +{
> +       return (u64)prandom_u32();
> +}
> +
>  /* Register mappings for user programs. */
>  #define A_REG          0
>  #define X_REG          7
> @@ -779,6 +785,7 @@ static bool convert_bpf_extensions(struct sock_filter *fp,
>         case SKF_AD_OFF + SKF_AD_NLATTR:
>         case SKF_AD_OFF + SKF_AD_NLATTR_NEST:
>         case SKF_AD_OFF + SKF_AD_CPU:
> +       case SKF_AD_OFF + SKF_AD_RANDOM:
>                 /* arg1 = ctx */
>                 insn->code = BPF_ALU64 | BPF_MOV | BPF_X;
>                 insn->a_reg = ARG1_REG;
> @@ -812,6 +819,9 @@ static bool convert_bpf_extensions(struct sock_filter *fp,
>                 case SKF_AD_OFF + SKF_AD_CPU:
>                         insn->imm = __get_raw_cpu_id - __bpf_call_base;
>                         break;
> +               case SKF_AD_OFF + SKF_AD_RANDOM:
> +                       insn->imm = __get_random_u32 - __bpf_call_base;
> +                       break;
>                 }
>                 break;
>
> @@ -1362,6 +1372,7 @@ int sk_chk_filter(struct sock_filter *filter, unsigned int flen)
>                         ANCILLARY(VLAN_TAG);
>                         ANCILLARY(VLAN_TAG_PRESENT);
>                         ANCILLARY(PAY_OFFSET);
> +                       ANCILLARY(RANDOM);
>                         }
>
>                         /* ancillary operation unknown or unsupported */
> @@ -1746,6 +1757,7 @@ void sk_decode_filter(struct sock_filter *filt, struct sock_filter *to)
>                 [BPF_S_ANC_VLAN_TAG]    = BPF_LD|BPF_B|BPF_ABS,
>                 [BPF_S_ANC_VLAN_TAG_PRESENT] = BPF_LD|BPF_B|BPF_ABS,
>                 [BPF_S_ANC_PAY_OFFSET]  = BPF_LD|BPF_B|BPF_ABS,
> +               [BPF_S_ANC_RANDOM]      = BPF_LD|BPF_B|BPF_ABS,
>                 [BPF_S_LD_W_LEN]        = BPF_LD|BPF_W|BPF_LEN,
>                 [BPF_S_LD_W_IND]        = BPF_LD|BPF_W|BPF_IND,
>                 [BPF_S_LD_H_IND]        = BPF_LD|BPF_H|BPF_IND,
> diff --git a/tools/net/bpf_exp.l b/tools/net/bpf_exp.l
> index bf7be77..833a966 100644
> --- a/tools/net/bpf_exp.l
> +++ b/tools/net/bpf_exp.l
> @@ -92,6 +92,7 @@ extern void yyerror(const char *str);
>  "#"?("cpu")    { return K_CPU; }
>  "#"?("vlan_tci") { return K_VLANT; }
>  "#"?("vlan_pr")        { return K_VLANP; }
> +"#"?("rand")   { return K_RAND; }
>
>  ":"            { return ':'; }
>  ","            { return ','; }
> diff --git a/tools/net/bpf_exp.y b/tools/net/bpf_exp.y
> index d15efc9..e6306c5 100644
> --- a/tools/net/bpf_exp.y
> +++ b/tools/net/bpf_exp.y
> @@ -56,7 +56,7 @@ static void bpf_set_jmp_label(char *label, enum jmp_type type);
>  %token OP_LDXI
>
>  %token K_PKT_LEN K_PROTO K_TYPE K_NLATTR K_NLATTR_NEST K_MARK K_QUEUE K_HATYPE
> -%token K_RXHASH K_CPU K_IFIDX K_VLANT K_VLANP K_POFF
> +%token K_RXHASH K_CPU K_IFIDX K_VLANT K_VLANP K_POFF K_RAND
>
>  %token ':' ',' '[' ']' '(' ')' 'x' 'a' '+' 'M' '*' '&' '#' '%'
>
> @@ -164,6 +164,9 @@ ldb
>         | OP_LDB K_POFF {
>                 bpf_set_curr_instr(BPF_LD | BPF_B | BPF_ABS, 0, 0,
>                                    SKF_AD_OFF + SKF_AD_PAY_OFFSET); }
> +       | OP_LDB K_RAND {
> +               bpf_set_curr_instr(BPF_LD | BPF_B | BPF_ABS, 0, 0,
> +                                  SKF_AD_OFF + SKF_AD_RANDOM); }
>         ;
>
>  ldh
> @@ -212,6 +215,9 @@ ldh
>         | OP_LDH K_POFF {
>                 bpf_set_curr_instr(BPF_LD | BPF_H | BPF_ABS, 0, 0,
>                                    SKF_AD_OFF + SKF_AD_PAY_OFFSET); }
> +       | OP_LDH K_RAND {
> +               bpf_set_curr_instr(BPF_LD | BPF_H | BPF_ABS, 0, 0,
> +                                  SKF_AD_OFF + SKF_AD_RANDOM); }
>         ;
>
>  ldi
> @@ -265,6 +271,9 @@ ld
>         | OP_LD K_POFF {
>                 bpf_set_curr_instr(BPF_LD | BPF_W | BPF_ABS, 0, 0,
>                                    SKF_AD_OFF + SKF_AD_PAY_OFFSET); }
> +       | OP_LD K_RAND {
> +               bpf_set_curr_instr(BPF_LD | BPF_W | BPF_ABS, 0, 0,
> +                                  SKF_AD_OFF + SKF_AD_RANDOM); }
>         | OP_LD 'M' '[' number ']' {
>                 bpf_set_curr_instr(BPF_LD | BPF_MEM, 0, 0, $4); }
>         | OP_LD '[' 'x' '+' number ']' {
> --
> 1.9.1.423.g4596e3a
>

Re: [PATCH v2] filter: added BPF random opcode

[Chema Gonzalez]

On Mon, Apr 21, 2014 at 2:46 PM, Alexei Starovoitov <ast@plumgrid.com> wrote:
> as I was saying in the other thread, would be nice to see more
> realistic example, since "icmp 1 in 4" can be done in user space...
> What is the real problem being solved?
> I suspect for true packet sampling you'd need to have the knowledge
> of packet rate, potentially computing time delta within filter with
> another extension?
> The patch itself looks good to me.
Random sampling. There's a huge performance penalty if you do this in
user-space. You don't want to send all the packets to user-space to
just get (e.g.) 1 in 1000 and discard all the others.

>From http://www.icir.org/vern/papers/secondary-path-raid06.pdf:

When dealing with large volumes of network traffic, we can often
derive significant
benefit while minimizing the processing cost by employing sampling.
Generally, this
is done on either a per-packet or per-connection basis. BPF does not
provide access
to pseudo-random numbers, so applications have had to rely on proxies
for random-
ness in terms of network header fields with some semblance of entropy
across packets
(checksum and IP fragment identifier fields) or connections (ephemeral
ports). These
sometimes provide acceptable approximations to random sampling, but
can also suffer
from significant irregularities due to lack of entropy or aliasing;
see [11] for an analysis.

-Chema

Re: [PATCH v2] filter: added BPF random opcode

[Alexei Starovoitov]

On Mon, Apr 21, 2014 at 2:54 PM, Chema Gonzalez <chema@google.com> wrote:
> On Mon, Apr 21, 2014 at 2:46 PM, Alexei Starovoitov <ast@plumgrid.com> wrote:
>> as I was saying in the other thread, would be nice to see more
>> realistic example, since "icmp 1 in 4" can be done in user space...
>> What is the real problem being solved?
>> I suspect for true packet sampling you'd need to have the knowledge
>> of packet rate, potentially computing time delta within filter with
>> another extension?
>> The patch itself looks good to me.
> Random sampling. There's a huge performance penalty if you do this in
> user-space. You don't want to send all the packets to user-space to
> just get (e.g.) 1 in 1000 and discard all the others.

Of course.
Just 1 out of 4 example you gave wasn't very real.

> From http://www.icir.org/vern/papers/secondary-path-raid06.pdf:

Nice. Now I see where it's going :)
The article helps a lot.

Acked-by: Alexei Starovoitov <ast@plumgrid.com>

btw it's funny how different people think of similar things.
It seems to complete what you wanted in the article you'd need
table access from the filter.
Did you have a chance to look at my bpf table proposal?
It seems it will fit perfectly to your use case as well.

Here is the copy paste from the other thread:
-----
Similar basic interface I'm proposing to use for bpf tables.
Probably makes sense to drop 'bpf' prefix, since they're just
hash tables. Little to do with bpf.
Have a netlink API from user into kernel:
- create hash table (num_of_entries, key_size, value_size, id)
- dump table via netlink
- add/remove key/value pair
Some kernel module may use it to transfer the data between
kernel and userspace.
This can be a generic kernel/user data sharing facility.

Also let bpf programs do 'table_lookup/update', so that
filters can store interesting data.
--------
I've posted early bpf_table patches back in September...
Now in process of redoing them with cleaner interface.

Thanks

> When dealing with large volumes of network traffic, we can often
> derive significant
> benefit while minimizing the processing cost by employing sampling.
> Generally, this
> is done on either a per-packet or per-connection basis. BPF does not
> provide access
> to pseudo-random numbers, so applications have had to rely on proxies
> for random-
> ness in terms of network header fields with some semblance of entropy
> across packets
> (checksum and IP fragment identifier fields) or connections (ephemeral
> ports). These
> sometimes provide acceptable approximations to random sampling, but
> can also suffer
> from significant irregularities due to lack of entropy or aliasing;
> see [11] for an analysis.
>
> -Chema

Re: [PATCH v2] filter: added BPF random opcode

[Chema Gonzalez]

On Mon, Apr 21, 2014 at 3:20 PM, Alexei Starovoitov <ast@plumgrid.com> wrote:
> Nice. Now I see where it's going :)
> The article helps a lot.
Note that the paper implementation is slightly different from the one
here: It was implemented for the BSD engine (therefore BSD or userland
only). Also, random was implemented as a new load mode (called "ldr"),
instead of an ancillary load. This, in retrospective, was a mistake:
Ancillary load is a much simpler solution, doesn't require disabling
the BSD BPF optimizer, and allows straightforward JITing. Also, when I
think about a generic ISA, random is an OS call, not a ISA insn (I
guess rdrand is an exception).

While orthogonal to the load mode/ancillary load implementation, the
main advantage of the old patch is that it used its own LCG-based
PRNG, which allowed userland seeding (this is very important in
testing and debugging). It also provided an extension of the tcpdump
language, so you could add filters like "tcp and random 4 == 1" (which
would sample 1 in 4 tcp packets).

> btw it's funny how different people think of similar things.
> It seems to complete what you wanted in the article you'd need
> table access from the filter.
> Did you have a chance to look at my bpf table proposal?
I haven't had time.

BTW, I like your eBPF work a lot. In fact, I like it so much that I
decided to dust off the BPF random patch and send it to the list. I
see eBPF as the final push of BPF from a special-purpose ISA
(packet-filtering) to a generic-purpose one. This is the natural
evolution of the seccomp-bpf work. In fact, I see BPF as an ISA in the
kernel that can be used as *the* safe method to run stateful,
user-provided functions in the kernel.

> It seems it will fit perfectly to your use case as well.
>
> Here is the copy paste from the other thread:
> -----
> Similar basic interface I'm proposing to use for bpf tables.
> Probably makes sense to drop 'bpf' prefix, since they're just
> hash tables. Little to do with bpf.
> Have a netlink API from user into kernel:
> - create hash table (num_of_entries, key_size, value_size, id)
> - dump table via netlink
> - add/remove key/value pair
> Some kernel module may use it to transfer the data between
> kernel and userspace.
> This can be a generic kernel/user data sharing facility.
>
> Also let bpf programs do 'table_lookup/update', so that
> filters can store interesting data.
> --------
> I've posted early bpf_table patches back in September...
> Now in process of redoing them with cleaner interface.

Persistent (inter-packet) state is a (way) more complicated issue than
basic randomness. You're adding state that lives from one packet to
the next one. In principle, I like your laundry list.

- external create/init/read/write access to the tables(s). netlink
sounds a good solution
- external add/remove key[/value] entry. netlink again

But still have many questions that give me pause:

- safety: what I like best about BPF is that it's proved itself safe
in 20+ years. We need to be very careful not to introduce issues. In
particular, I've had discussions over the possibility of leaking
entropy through BPF
- what's the right approach to add state? I'd expect BPF to provide a
lump buffer, and let the filters to use that buffer according to their
needs. While a hash table is a good solution, I can see how users may
prefer other data structures (e.g. Bloom filters)
- how many hash tables? Which types? In principle, you can implement
flow sampling with a couple of Bloom filters. They're very efficient
memory-wise
- what about the hash function(s)? This should be configurable
- what about space limits? I can see how some of my problems require
BPF tables in the GB sizes. Is this an issue for anybody? Is this an
issue at all?
- where should the state live? Should we have common-CPU persistent
state, or also per-CPU state. Probably both are nice

The solution discussed in the paper above was too strict (simple Bloom
filters, mistakenly named "hash" tables). We also *really* wanted to
be able to run tcpdump filters, so we extended the tcpdump language
syntax. In retrospective, an asm-like syntax like the one used by
bpf_asm is way better.

I'll definitely be interested in seeing your new proposal when it's ready.

-Chema

Re: [PATCH v2] filter: added BPF random opcode

[Alexei Starovoitov]

On Mon, Apr 21, 2014 at 4:19 PM, Chema Gonzalez <chema@google.com> wrote:
> On Mon, Apr 21, 2014 at 3:20 PM, Alexei Starovoitov <ast@plumgrid.com> wrote:
>> Nice. Now I see where it's going :)
>> The article helps a lot.
> Note that the paper implementation is slightly different from the one
> here: It was implemented for the BSD engine (therefore BSD or userland
> only). Also, random was implemented as a new load mode (called "ldr"),
> instead of an ancillary load. This, in retrospective, was a mistake:
> Ancillary load is a much simpler solution, doesn't require disabling
> the BSD BPF optimizer, and allows straightforward JITing. Also, when I
> think about a generic ISA, random is an OS call, not a ISA insn (I
> guess rdrand is an exception).
>
> While orthogonal to the load mode/ancillary load implementation, the
> main advantage of the old patch is that it used its own LCG-based
> PRNG, which allowed userland seeding (this is very important in
> testing and debugging). It also provided an extension of the tcpdump
> language, so you could add filters like "tcp and random 4 == 1" (which
> would sample 1 in 4 tcp packets).
>
>> btw it's funny how different people think of similar things.
>> It seems to complete what you wanted in the article you'd need
>> table access from the filter.
>> Did you have a chance to look at my bpf table proposal?
> I haven't had time.
>
> BTW, I like your eBPF work a lot. In fact, I like it so much that I
> decided to dust off the BPF random patch and send it to the list. I
> see eBPF as the final push of BPF from a special-purpose ISA
> (packet-filtering) to a generic-purpose one. This is the natural
> evolution of the seccomp-bpf work. In fact, I see BPF as an ISA in the
> kernel that can be used as *the* safe method to run stateful,
> user-provided functions in the kernel.

Thanks :)

>> It seems it will fit perfectly to your use case as well.
>>
>> Here is the copy paste from the other thread:
>> -----
>> Similar basic interface I'm proposing to use for bpf tables.
>> Probably makes sense to drop 'bpf' prefix, since they're just
>> hash tables. Little to do with bpf.
>> Have a netlink API from user into kernel:
>> - create hash table (num_of_entries, key_size, value_size, id)
>> - dump table via netlink
>> - add/remove key/value pair
>> Some kernel module may use it to transfer the data between
>> kernel and userspace.
>> This can be a generic kernel/user data sharing facility.
>>
>> Also let bpf programs do 'table_lookup/update', so that
>> filters can store interesting data.
>> --------
>> I've posted early bpf_table patches back in September...
>> Now in process of redoing them with cleaner interface.
>
> Persistent (inter-packet) state is a (way) more complicated issue than
> basic randomness. You're adding state that lives from one packet to
> the next one. In principle, I like your laundry list.
>
> - external create/init/read/write access to the tables(s). netlink
> sounds a good solution
> - external add/remove key[/value] entry. netlink again

I'm thinking about 'tables' and 'bpf filters' as complementary
and related, but independent and decoupled kernel mechanisms.
'tables' are kernel/user sharing facility available to root only.
If filter is loaded by the root, bpf verifier will allow access to
given tables.
tables can be used by kernel modules too without bpf around.

I'm not sure yet that we need to let unprivileged users create tables.
nids use case, tracing filters and ovs+bpf cases will do with root only.

Though I think it's ok to have per-user limit of N tables of M size.
Filters loaded by the same user will have access to user's tables.

> But still have many questions that give me pause:
>
> - safety: what I like best about BPF is that it's proved itself safe
> in 20+ years. We need to be very careful not to introduce issues. In

we need to be careful, but cannot stand still.
I'll try to phase in ebpf verifier in small bites with as many details
as possible.
In particular DAG check will come first, since it's needed
for classic bpf already to prevent unreachable code.

> particular, I've had discussions over the possibility of leaking
> entropy through BPF
> - what's the right approach to add state? I'd expect BPF to provide a
> lump buffer, and let the filters to use that buffer according to their
> needs. While a hash table is a good solution, I can see how users may
> prefer other data structures (e.g. Bloom filters)

correct. bloom filters can be one of the table types.
So far we have use cases for hash, hash+lru, lpm types.

> - how many hash tables? Which types? In principle, you can implement
> flow sampling with a couple of Bloom filters. They're very efficient
> memory-wise

I think there is no limit to the number of root's tables.
The table is defined by:
- table_id
- table type (hash, bloom, etc)
- max number of elements
- key size in bytes
- value size in bytes

API from user space:
- create/delete table
- add/remove/read element

API from kernel module or from bpf program:
- add/remove/read element
(kernel module and bpf loader also do table hold/release)

> - what about the hash function(s)? This should be configurable

for hash table itself? I'm not sure what it really buys us, but we can
have two hash types: one hashes provided key, another takes
key and hash from filter.
Then filter itself is responsible for hashing the key the way it wants.

> - what about space limits? I can see how some of my problems require
> BPF tables in the GB sizes. Is this an issue for anybody? Is this an
> issue at all?

if root allocates them, then I think it's not a problem.
for regular users we may want to have a limit just like max file descr,
for user's own safety.
In the near future I'm proposing it for root only.

> - where should the state live? Should we have common-CPU persistent
> state, or also per-CPU state. Probably both are nice

agree. we were debating about it internally too. In current
implementation every table element is not per-cpu.

from bpf program the access is like:
rcu_read_lock()
enter bpf filter
...
ptr_to_value = bpf_table_lookup(const_int_table_id, key)
access memory [ptr_to_value, ptr_to_value + value_size_in_bytes]
...
prepare key2 and value2 on stack of key_size and value_size
err = bpf_table_update(const_int_table_id2, key2, value2)
...
leave bpf filter
rcu_read_unlock()

bpf filter cannot create or delete a table.
During filter loading verifier does table_hold() on the tables that filter
may access, so they don't get deleted while filter is running

bpf_table_update() can fail if max_elements reached.
if key2 already exists, bpf_table_update() replaces it with value2 atomically

bpf_table_lookup() can return null or ptr_to_value
ptr_to_value is read/write from bpf program point of view.

> The solution discussed in the paper above was too strict (simple Bloom
> filters, mistakenly named "hash" tables). We also *really* wanted to
> be able to run tcpdump filters, so we extended the tcpdump language
> syntax. In retrospective, an asm-like syntax like the one used by
> bpf_asm is way better.

imo C is more readable than both tcpdump and asm, but we will
have asm as a minimum. Eventually C and other languages.

> I'll definitely be interested in seeing your new proposal when it's ready.

patches speak better than words. will get it ready.

Thanks!

> -Chema

Re: [PATCH v2] filter: added BPF random opcode

[Daniel Borkmann]

On 04/21/2014 06:21 PM, Chema Gonzalez wrote:
> Added a new ancillary load (bpf call in eBPF parlance) that produces
> a 32-bit random number. We are implementing it as an ancillary load
> (instead of an ISA opcode) because (a) it is simpler, (b) allows easy
> JITing, and (c) seems more in line with generic ISAs that do not have
> "get a random number" as a instruction, but as an OS call.
>
> The main use for this ancillary load is to perform random packet sampling.
>
> Signed-off-by: Chema Gonzalez <chema@google.com>

Generally, I'm fine with your patch. If some day other use cases pop up
in non-packet filtering areas, we might need to let it return a 64 bit
number, but lets see. Thanks again for updating bpf_asm as well!

Acked-by: Daniel Borkmann <dborkman@redhat.com>

Re: [PATCH v2] filter: added BPF random opcode

[David Miller]

From: Chema Gonzalez <chema@google.com>
Date: Mon, 21 Apr 2014 09:21:24 -0700

> Added a new ancillary load (bpf call in eBPF parlance) that produces
> a 32-bit random number. We are implementing it as an ancillary load
> (instead of an ISA opcode) because (a) it is simpler, (b) allows easy
> JITing, and (c) seems more in line with generic ISAs that do not have
> "get a random number" as a instruction, but as an OS call.
> 
> The main use for this ancillary load is to perform random packet sampling.
> 
> Signed-off-by: Chema Gonzalez <chema@google.com>

Applied.

Re: [PATCH] filter: added BPF random opcode

[Chema Gonzalez]

On Tue, Apr 15, 2014 at 9:44 AM, Daniel Borkmann <dborkman@redhat.com> wrote:
>>> I think using just "rnd" is cleaner here.
>>
>> I think using always random (in fact I may s/K_RAND/K_RANDOM/g) allows
>> easier grepping.
>
>
> I know it's just nitpicking, but I'd be happier if that would
> either be rnd or rand in bpf_asm.
"rand" it is.

>>> This example should rather go into Documentation/networking/filter.txt's
>>> example section, rather than tools/net/ .
>>
>> I'll add it there.
>
>
> Ok, thanks.
Done.

> For 'playing', I'd rather be happy to add that to the documentation file
> in Documentation/networking/filter.txt where we have other examples, or
> alternatively, if there is really no other way around, a new folder inside
> of Documentation/networking/ .
I think it would be better close to the tools/net/bpf* tools. Anyway,
I removed it for now.

-Chema

Re: [PATCH] filter: added BPF random opcode

[Daniel Borkmann]

On 04/15/2014 06:30 PM, Chema Gonzalez wrote:
> On Tue, Apr 15, 2014 at 12:24 AM, Daniel Borkmann <dborkman@redhat.com> wrote:
>> Hi Chema,
>>
>> [cc'ing Alexei as well]
>>
>> note, net-next is still closed, so you might need to resend this later
>> on again when it opens up.
> I will. Thanks!

Great, thanks.

>> On 04/15/2014 01:02 AM, Chema Gonzalez wrote:
>>> diff --git a/tools/net/bpf_exp.l b/tools/net/bpf_exp.l
>>> index bf7be77..804256f 100644
>>> --- a/tools/net/bpf_exp.l
>>> +++ b/tools/net/bpf_exp.l
>>> @@ -92,6 +92,7 @@ extern void yyerror(const char *str);
>>>    "#"?("cpu")   { return K_CPU; }
>>>    "#"?("vlan_tci") { return K_VLANT; }
>>>    "#"?("vlan_pr")       { return K_VLANP; }
>>> +"#"?("random") { return K_RAND; }
>>
>>
>> Thanks for also updating bpf_asm ! :)
> bpf_asm was key in ensuring this worked. In fact, we should modify the
> Makefile so that it relies on the local filter.h before the
> /usr/include/ one (my Ubuntu Precise /usr/include/linux/filter.h does
> not define BPF_MOD, BPF_XOR, SKF_AD_VLAN_TAG, SKF_AD_VLAN_TAG_PRESENT,
> or SKF_AD_PAY_OFFSET).

Good point, feel free to send a patch. :)

>> I think using just "rnd" is cleaner here.
> I think using always random (in fact I may s/K_RAND/K_RANDOM/g) allows
> easier grepping.

I know it's just nitpicking, but I'd be happier if that would
either be rnd or rand in bpf_asm.

>>> diff --git a/tools/net/icmp_random.bpf b/tools/net/icmp_random.bpf
>>> new file mode 100644
>>> index 0000000..b9adcbf
>>> --- /dev/null
>>> +++ b/tools/net/icmp_random.bpf
>>> @@ -0,0 +1,12 @@
>>> +# icmp random packet sampling, 1 in 4
>>> +ldh [12]
>>> +jne #0x800, drop
>>> +ldb [23]
>>> +jneq #1, drop
>>> +# get a random uint32 number
>>> +ld random
>>> +mod #4
>>> +jneq #1, drop
>>> +ret #-1
>>> +drop: ret #0
>>> +
>>>
>>
>> This example should rather go into Documentation/networking/filter.txt's
>> example section, rather than tools/net/ .
> I'll add it there.

Ok, thanks.

> Now, I'd like to add a new directory for BPF programs (tools/net/bpf/
> ?). It allows playing with bpf_asm.

For 'playing', I'd rather be happy to add that to the documentation file
in Documentation/networking/filter.txt where we have other examples, or
alternatively, if there is really no other way around, a new folder inside
of Documentation/networking/ .

Re: [PATCH] filter: added BPF random opcode

[Chema Gonzalez]

On Tue, Apr 15, 2014 at 12:24 AM, Daniel Borkmann <dborkman@redhat.com> wrote:
> Hi Chema,
>
> [cc'ing Alexei as well]
>
> note, net-next is still closed, so you might need to resend this later
> on again when it opens up.
I will. Thanks!

> On 04/15/2014 01:02 AM, Chema Gonzalez wrote:
>> diff --git a/tools/net/bpf_exp.l b/tools/net/bpf_exp.l
>> index bf7be77..804256f 100644
>> --- a/tools/net/bpf_exp.l
>> +++ b/tools/net/bpf_exp.l
>> @@ -92,6 +92,7 @@ extern void yyerror(const char *str);
>>   "#"?("cpu")   { return K_CPU; }
>>   "#"?("vlan_tci") { return K_VLANT; }
>>   "#"?("vlan_pr")       { return K_VLANP; }
>> +"#"?("random") { return K_RAND; }
>
>
> Thanks for also updating bpf_asm ! :)
bpf_asm was key in ensuring this worked. In fact, we should modify the
Makefile so that it relies on the local filter.h before the
/usr/include/ one (my Ubuntu Precise /usr/include/linux/filter.h does
not define BPF_MOD, BPF_XOR, SKF_AD_VLAN_TAG, SKF_AD_VLAN_TAG_PRESENT,
or SKF_AD_PAY_OFFSET).

> I think using just "rnd" is cleaner here.
I think using always random (in fact I may s/K_RAND/K_RANDOM/g) allows
easier grepping.

>> diff --git a/tools/net/icmp_random.bpf b/tools/net/icmp_random.bpf
>> new file mode 100644
>> index 0000000..b9adcbf
>> --- /dev/null
>> +++ b/tools/net/icmp_random.bpf
>> @@ -0,0 +1,12 @@
>> +# icmp random packet sampling, 1 in 4
>> +ldh [12]
>> +jne #0x800, drop
>> +ldb [23]
>> +jneq #1, drop
>> +# get a random uint32 number
>> +ld random
>> +mod #4
>> +jneq #1, drop
>> +ret #-1
>> +drop: ret #0
>> +
>>
>
> This example should rather go into Documentation/networking/filter.txt's
> example section, rather than tools/net/ .
I'll add it there.

Now, I'd like to add a new directory for BPF programs (tools/net/bpf/
?). It allows playing with bpf_asm.

-Chema

Re: [PATCH] filter: added BPF random opcode

[Chema Gonzalez]

On Tue, Apr 15, 2014 at 8:04 AM, Daniel Borkmann <dborkman@redhat.com> wrote:
> On 04/15/2014 04:41 PM, Eric Dumazet wrote:
>>
>> On Tue, 2014-04-15 at 09:24 +0200, Daniel Borkmann wrote:
>>
>>>> @@ -773,6 +779,7 @@ static bool convert_bpf_extensions(struct
>>>> sock_filter *fp,
>>>>         case SKF_AD_OFF + SKF_AD_NLATTR:
>>>>         case SKF_AD_OFF + SKF_AD_NLATTR_NEST:
>>>>         case SKF_AD_OFF + SKF_AD_CPU:
>>>> +       case SKF_AD_OFF + SKF_AD_RANDOM:
>>>
>>>
>>> I think instead of a function call, this sould rather be modelled
>>> directly into the internal insn set and thus converted differently,
>>> so we can spare us the call.
>>
>>
>> Hmmm... this would need percpu storage, thus preempt disable/enable
>> calls, and prandom_u32_state() is about 40 instructions.
>>
>> This is really not worth the pain.
>
>
> Absolutely, that was not what I meant actually. Calling to
> prandom_u32_state() is fine, no need to have another prng just
> for that. I was just wondering if it makes sense to model that
> directly as an instruction into a jump-table target that calls
> prandom_u32() from there instead 'indirectly'. Need to think
> about this a bit more ...
I thought about that. In fact, the original patch (written for
FreeBSD) worked by extending the ISA with a new load mode that did "A
= random();". After seeing your eBPF work, I got convinced that we
want to get a generic ISA when possible, where random is typically not
an insn. Also, the bpf_call approach makes it much easier to integrate
with the different JITs.

-Chema

Re: [PATCH] filter: added BPF random opcode

[Daniel Borkmann]

On 04/15/2014 04:41 PM, Eric Dumazet wrote:
> On Tue, 2014-04-15 at 09:24 +0200, Daniel Borkmann wrote:
>
>>> @@ -773,6 +779,7 @@ static bool convert_bpf_extensions(struct sock_filter *fp,
>>>    	case SKF_AD_OFF + SKF_AD_NLATTR:
>>>    	case SKF_AD_OFF + SKF_AD_NLATTR_NEST:
>>>    	case SKF_AD_OFF + SKF_AD_CPU:
>>> +	case SKF_AD_OFF + SKF_AD_RANDOM:
>>
>> I think instead of a function call, this sould rather be modelled
>> directly into the internal insn set and thus converted differently,
>> so we can spare us the call.
>
> Hmmm... this would need percpu storage, thus preempt disable/enable
> calls, and prandom_u32_state() is about 40 instructions.
>
> This is really not worth the pain.

Absolutely, that was not what I meant actually. Calling to
prandom_u32_state() is fine, no need to have another prng just
for that. I was just wondering if it makes sense to model that
directly as an instruction into a jump-table target that calls
prandom_u32() from there instead 'indirectly'. Need to think
about this a bit more ...

Re: [PATCH] filter: added BPF random opcode

[Eric Dumazet]

On Tue, 2014-04-15 at 09:24 +0200, Daniel Borkmann wrote:

> > @@ -773,6 +779,7 @@ static bool convert_bpf_extensions(struct sock_filter *fp,
> >   	case SKF_AD_OFF + SKF_AD_NLATTR:
> >   	case SKF_AD_OFF + SKF_AD_NLATTR_NEST:
> >   	case SKF_AD_OFF + SKF_AD_CPU:
> > +	case SKF_AD_OFF + SKF_AD_RANDOM:
> 
> I think instead of a function call, this sould rather be modelled
> directly into the internal insn set and thus converted differently,
> so we can spare us the call.

Hmmm... this would need percpu storage, thus preempt disable/enable
calls, and prandom_u32_state() is about 40 instructions.

This is really not worth the pain.

Re: [PATCH] filter: added BPF random opcode

[Daniel Borkmann]

Hi Chema,

[cc'ing Alexei as well]

note, net-next is still closed, so you might need to resend this later
on again when it opens up.

On 04/15/2014 01:02 AM, Chema Gonzalez wrote:
> This should allow random packet sampling.
>
> Signed-off-by: Chema Gonzalez <chema@google.com>
> ---
>   Documentation/networking/filter.txt |  1 +
>   include/linux/filter.h              |  1 +
>   include/uapi/linux/filter.h         |  3 ++-
>   net/core/filter.c                   | 12 ++++++++++++
>   tools/net/bpf_exp.l                 |  1 +
>   tools/net/bpf_exp.y                 | 11 ++++++++++-
>   tools/net/icmp_random.bpf           | 12 ++++++++++++
>   7 files changed, 39 insertions(+), 2 deletions(-)
>   create mode 100644 tools/net/icmp_random.bpf
>
> diff --git a/Documentation/networking/filter.txt b/Documentation/networking/filter.txt
> index 81f940f..7192b46 100644
> --- a/Documentation/networking/filter.txt
> +++ b/Documentation/networking/filter.txt
> @@ -281,6 +281,7 @@ Possible BPF extensions are shown in the following table:
>     cpu                                   raw_smp_processor_id()
>     vlan_tci                              vlan_tx_tag_get(skb)
>     vlan_pr                               vlan_tx_tag_present(skb)
> +  random                                prandom_u32()
>
>   These extensions can also be prefixed with '#'.
>   Examples for low-level BPF:
> diff --git a/include/linux/filter.h b/include/linux/filter.h
> index 262dcbb..49c28aa 100644
> --- a/include/linux/filter.h
> +++ b/include/linux/filter.h
> @@ -224,6 +224,7 @@ enum {
>   	BPF_S_ANC_VLAN_TAG,
>   	BPF_S_ANC_VLAN_TAG_PRESENT,
>   	BPF_S_ANC_PAY_OFFSET,
> +	BPF_S_ANC_RANDOM,
>   };
>
>   #endif /* __LINUX_FILTER_H__ */
> diff --git a/include/uapi/linux/filter.h b/include/uapi/linux/filter.h
> index 8eb9cca..253b4d4 100644
> --- a/include/uapi/linux/filter.h
> +++ b/include/uapi/linux/filter.h
> @@ -130,7 +130,8 @@ struct sock_fprog {	/* Required for SO_ATTACH_FILTER. */
>   #define SKF_AD_VLAN_TAG	44
>   #define SKF_AD_VLAN_TAG_PRESENT 48
>   #define SKF_AD_PAY_OFFSET	52
> -#define SKF_AD_MAX	56
> +#define SKF_AD_RANDOM	56
> +#define SKF_AD_MAX	60
>   #define SKF_NET_OFF   (-0x100000)
>   #define SKF_LL_OFF    (-0x200000)
>
> diff --git a/net/core/filter.c b/net/core/filter.c
> index 765556b..b2a80a1 100644
> --- a/net/core/filter.c
> +++ b/net/core/filter.c
> @@ -637,6 +637,12 @@ static u64 __get_raw_cpu_id(u64 ctx, u64 A, u64 X, u64 r4, u64 r5)
>   	return raw_smp_processor_id();
>   }
>
> +/* note that this only generates 32-bit random numbers */
> +static u64 __skb_get_random(u64 ctx, u64 A, u64 X, u64 r4, u64 r5)
> +{
> +	return (u64)prandom_u32();
> +}
> +
>   /* Register mappings for user programs. */
>   #define A_REG		0
>   #define X_REG		7
> @@ -773,6 +779,7 @@ static bool convert_bpf_extensions(struct sock_filter *fp,
>   	case SKF_AD_OFF + SKF_AD_NLATTR:
>   	case SKF_AD_OFF + SKF_AD_NLATTR_NEST:
>   	case SKF_AD_OFF + SKF_AD_CPU:
> +	case SKF_AD_OFF + SKF_AD_RANDOM:

I think instead of a function call, this sould rather be modelled
directly into the internal insn set and thus converted differently,
so we can spare us the call.

>   		/* arg1 = ctx */
>   		insn->code = BPF_ALU64 | BPF_MOV | BPF_X;
>   		insn->a_reg = ARG1_REG;
> @@ -806,6 +813,9 @@ static bool convert_bpf_extensions(struct sock_filter *fp,
>   		case SKF_AD_OFF + SKF_AD_CPU:
>   			insn->imm = __get_raw_cpu_id - __bpf_call_base;
>   			break;
> +		case SKF_AD_OFF + SKF_AD_RANDOM:
> +			insn->imm = __skb_get_random - __bpf_call_base;
> +			break;
>   		}
>   		break;
>
> @@ -1356,6 +1366,7 @@ int sk_chk_filter(struct sock_filter *filter, unsigned int flen)
>   			ANCILLARY(VLAN_TAG);
>   			ANCILLARY(VLAN_TAG_PRESENT);
>   			ANCILLARY(PAY_OFFSET);
> +			ANCILLARY(RANDOM);
>   			}
>
>   			/* ancillary operation unknown or unsupported */
> @@ -1741,6 +1752,7 @@ void sk_decode_filter(struct sock_filter *filt, struct sock_filter *to)
>   		[BPF_S_ANC_VLAN_TAG]	= BPF_LD|BPF_B|BPF_ABS,
>   		[BPF_S_ANC_VLAN_TAG_PRESENT] = BPF_LD|BPF_B|BPF_ABS,
>   		[BPF_S_ANC_PAY_OFFSET]	= BPF_LD|BPF_B|BPF_ABS,
> +		[BPF_S_ANC_RANDOM]	= BPF_LD|BPF_B|BPF_ABS,
>   		[BPF_S_LD_W_LEN]	= BPF_LD|BPF_W|BPF_LEN,
>   		[BPF_S_LD_W_IND]	= BPF_LD|BPF_W|BPF_IND,
>   		[BPF_S_LD_H_IND]	= BPF_LD|BPF_H|BPF_IND,
> diff --git a/tools/net/bpf_exp.l b/tools/net/bpf_exp.l
> index bf7be77..804256f 100644
> --- a/tools/net/bpf_exp.l
> +++ b/tools/net/bpf_exp.l
> @@ -92,6 +92,7 @@ extern void yyerror(const char *str);
>   "#"?("cpu")	{ return K_CPU; }
>   "#"?("vlan_tci") { return K_VLANT; }
>   "#"?("vlan_pr")	{ return K_VLANP; }
> +"#"?("random")	{ return K_RAND; }

Thanks for also updating bpf_asm ! :)

I think using just "rnd" is cleaner here.

>   ":"		{ return ':'; }
>   ","		{ return ','; }
> diff --git a/tools/net/bpf_exp.y b/tools/net/bpf_exp.y
> index d15efc9..e6306c5 100644
> --- a/tools/net/bpf_exp.y
> +++ b/tools/net/bpf_exp.y
> @@ -56,7 +56,7 @@ static void bpf_set_jmp_label(char *label, enum jmp_type type);
>   %token OP_LDXI
>
>   %token K_PKT_LEN K_PROTO K_TYPE K_NLATTR K_NLATTR_NEST K_MARK K_QUEUE K_HATYPE
> -%token K_RXHASH K_CPU K_IFIDX K_VLANT K_VLANP K_POFF
> +%token K_RXHASH K_CPU K_IFIDX K_VLANT K_VLANP K_POFF K_RAND
>
>   %token ':' ',' '[' ']' '(' ')' 'x' 'a' '+' 'M' '*' '&' '#' '%'
>
> @@ -164,6 +164,9 @@ ldb
>   	| OP_LDB K_POFF {
>   		bpf_set_curr_instr(BPF_LD | BPF_B | BPF_ABS, 0, 0,
>   				   SKF_AD_OFF + SKF_AD_PAY_OFFSET); }
> +	| OP_LDB K_RAND {
> +		bpf_set_curr_instr(BPF_LD | BPF_B | BPF_ABS, 0, 0,
> +				   SKF_AD_OFF + SKF_AD_RANDOM); }
>   	;
>
>   ldh
> @@ -212,6 +215,9 @@ ldh
>   	| OP_LDH K_POFF {
>   		bpf_set_curr_instr(BPF_LD | BPF_H | BPF_ABS, 0, 0,
>   				   SKF_AD_OFF + SKF_AD_PAY_OFFSET); }
> +	| OP_LDH K_RAND {
> +		bpf_set_curr_instr(BPF_LD | BPF_H | BPF_ABS, 0, 0,
> +				   SKF_AD_OFF + SKF_AD_RANDOM); }
>   	;
>
>   ldi
> @@ -265,6 +271,9 @@ ld
>   	| OP_LD K_POFF {
>   		bpf_set_curr_instr(BPF_LD | BPF_W | BPF_ABS, 0, 0,
>   				   SKF_AD_OFF + SKF_AD_PAY_OFFSET); }
> +	| OP_LD K_RAND {
> +		bpf_set_curr_instr(BPF_LD | BPF_W | BPF_ABS, 0, 0,
> +				   SKF_AD_OFF + SKF_AD_RANDOM); }
>   	| OP_LD 'M' '[' number ']' {
>   		bpf_set_curr_instr(BPF_LD | BPF_MEM, 0, 0, $4); }
>   	| OP_LD '[' 'x' '+' number ']' {
> diff --git a/tools/net/icmp_random.bpf b/tools/net/icmp_random.bpf
> new file mode 100644
> index 0000000..b9adcbf
> --- /dev/null
> +++ b/tools/net/icmp_random.bpf
> @@ -0,0 +1,12 @@
> +# icmp random packet sampling, 1 in 4
> +ldh [12]
> +jne #0x800, drop
> +ldb [23]
> +jneq #1, drop
> +# get a random uint32 number
> +ld random
> +mod #4
> +jneq #1, drop
> +ret #-1
> +drop: ret #0
> +
>

This example should rather go into Documentation/networking/filter.txt's
example section, rather than tools/net/ .

[PATCH] filter: added BPF random opcode

[Chema Gonzalez]

This should allow random packet sampling.

Signed-off-by: Chema Gonzalez <chema@google.com>
---
 Documentation/networking/filter.txt |  1 +
 include/linux/filter.h              |  1 +
 include/uapi/linux/filter.h         |  3 ++-
 net/core/filter.c                   | 12 ++++++++++++
 tools/net/bpf_exp.l                 |  1 +
 tools/net/bpf_exp.y                 | 11 ++++++++++-
 tools/net/icmp_random.bpf           | 12 ++++++++++++
 7 files changed, 39 insertions(+), 2 deletions(-)
 create mode 100644 tools/net/icmp_random.bpf

diff --git a/Documentation/networking/filter.txt b/Documentation/networking/filter.txt
index 81f940f..7192b46 100644
--- a/Documentation/networking/filter.txt
+++ b/Documentation/networking/filter.txt
@@ -281,6 +281,7 @@ Possible BPF extensions are shown in the following table:
   cpu                                   raw_smp_processor_id()
   vlan_tci                              vlan_tx_tag_get(skb)
   vlan_pr                               vlan_tx_tag_present(skb)
+  random                                prandom_u32()
 
 These extensions can also be prefixed with '#'.
 Examples for low-level BPF:
diff --git a/include/linux/filter.h b/include/linux/filter.h
index 262dcbb..49c28aa 100644
--- a/include/linux/filter.h
+++ b/include/linux/filter.h
@@ -224,6 +224,7 @@ enum {
 	BPF_S_ANC_VLAN_TAG,
 	BPF_S_ANC_VLAN_TAG_PRESENT,
 	BPF_S_ANC_PAY_OFFSET,
+	BPF_S_ANC_RANDOM,
 };
 
 #endif /* __LINUX_FILTER_H__ */
diff --git a/include/uapi/linux/filter.h b/include/uapi/linux/filter.h
index 8eb9cca..253b4d4 100644
--- a/include/uapi/linux/filter.h
+++ b/include/uapi/linux/filter.h
@@ -130,7 +130,8 @@ struct sock_fprog {	/* Required for SO_ATTACH_FILTER. */
 #define SKF_AD_VLAN_TAG	44
 #define SKF_AD_VLAN_TAG_PRESENT 48
 #define SKF_AD_PAY_OFFSET	52
-#define SKF_AD_MAX	56
+#define SKF_AD_RANDOM	56
+#define SKF_AD_MAX	60
 #define SKF_NET_OFF   (-0x100000)
 #define SKF_LL_OFF    (-0x200000)
 
diff --git a/net/core/filter.c b/net/core/filter.c
index 765556b..b2a80a1 100644
--- a/net/core/filter.c
+++ b/net/core/filter.c
@@ -637,6 +637,12 @@ static u64 __get_raw_cpu_id(u64 ctx, u64 A, u64 X, u64 r4, u64 r5)
 	return raw_smp_processor_id();
 }
 
+/* note that this only generates 32-bit random numbers */
+static u64 __skb_get_random(u64 ctx, u64 A, u64 X, u64 r4, u64 r5)
+{
+	return (u64)prandom_u32();
+}
+
 /* Register mappings for user programs. */
 #define A_REG		0
 #define X_REG		7
@@ -773,6 +779,7 @@ static bool convert_bpf_extensions(struct sock_filter *fp,
 	case SKF_AD_OFF + SKF_AD_NLATTR:
 	case SKF_AD_OFF + SKF_AD_NLATTR_NEST:
 	case SKF_AD_OFF + SKF_AD_CPU:
+	case SKF_AD_OFF + SKF_AD_RANDOM:
 		/* arg1 = ctx */
 		insn->code = BPF_ALU64 | BPF_MOV | BPF_X;
 		insn->a_reg = ARG1_REG;
@@ -806,6 +813,9 @@ static bool convert_bpf_extensions(struct sock_filter *fp,
 		case SKF_AD_OFF + SKF_AD_CPU:
 			insn->imm = __get_raw_cpu_id - __bpf_call_base;
 			break;
+		case SKF_AD_OFF + SKF_AD_RANDOM:
+			insn->imm = __skb_get_random - __bpf_call_base;
+			break;
 		}
 		break;
 
@@ -1356,6 +1366,7 @@ int sk_chk_filter(struct sock_filter *filter, unsigned int flen)
 			ANCILLARY(VLAN_TAG);
 			ANCILLARY(VLAN_TAG_PRESENT);
 			ANCILLARY(PAY_OFFSET);
+			ANCILLARY(RANDOM);
 			}
 
 			/* ancillary operation unknown or unsupported */
@@ -1741,6 +1752,7 @@ void sk_decode_filter(struct sock_filter *filt, struct sock_filter *to)
 		[BPF_S_ANC_VLAN_TAG]	= BPF_LD|BPF_B|BPF_ABS,
 		[BPF_S_ANC_VLAN_TAG_PRESENT] = BPF_LD|BPF_B|BPF_ABS,
 		[BPF_S_ANC_PAY_OFFSET]	= BPF_LD|BPF_B|BPF_ABS,
+		[BPF_S_ANC_RANDOM]	= BPF_LD|BPF_B|BPF_ABS,
 		[BPF_S_LD_W_LEN]	= BPF_LD|BPF_W|BPF_LEN,
 		[BPF_S_LD_W_IND]	= BPF_LD|BPF_W|BPF_IND,
 		[BPF_S_LD_H_IND]	= BPF_LD|BPF_H|BPF_IND,
diff --git a/tools/net/bpf_exp.l b/tools/net/bpf_exp.l
index bf7be77..804256f 100644
--- a/tools/net/bpf_exp.l
+++ b/tools/net/bpf_exp.l
@@ -92,6 +92,7 @@ extern void yyerror(const char *str);
 "#"?("cpu")	{ return K_CPU; }
 "#"?("vlan_tci") { return K_VLANT; }
 "#"?("vlan_pr")	{ return K_VLANP; }
+"#"?("random")	{ return K_RAND; }
 
 ":"		{ return ':'; }
 ","		{ return ','; }
diff --git a/tools/net/bpf_exp.y b/tools/net/bpf_exp.y
index d15efc9..e6306c5 100644
--- a/tools/net/bpf_exp.y
+++ b/tools/net/bpf_exp.y
@@ -56,7 +56,7 @@ static void bpf_set_jmp_label(char *label, enum jmp_type type);
 %token OP_LDXI
 
 %token K_PKT_LEN K_PROTO K_TYPE K_NLATTR K_NLATTR_NEST K_MARK K_QUEUE K_HATYPE
-%token K_RXHASH K_CPU K_IFIDX K_VLANT K_VLANP K_POFF
+%token K_RXHASH K_CPU K_IFIDX K_VLANT K_VLANP K_POFF K_RAND
 
 %token ':' ',' '[' ']' '(' ')' 'x' 'a' '+' 'M' '*' '&' '#' '%'
 
@@ -164,6 +164,9 @@ ldb
 	| OP_LDB K_POFF {
 		bpf_set_curr_instr(BPF_LD | BPF_B | BPF_ABS, 0, 0,
 				   SKF_AD_OFF + SKF_AD_PAY_OFFSET); }
+	| OP_LDB K_RAND {
+		bpf_set_curr_instr(BPF_LD | BPF_B | BPF_ABS, 0, 0,
+				   SKF_AD_OFF + SKF_AD_RANDOM); }
 	;
 
 ldh
@@ -212,6 +215,9 @@ ldh
 	| OP_LDH K_POFF {
 		bpf_set_curr_instr(BPF_LD | BPF_H | BPF_ABS, 0, 0,
 				   SKF_AD_OFF + SKF_AD_PAY_OFFSET); }
+	| OP_LDH K_RAND {
+		bpf_set_curr_instr(BPF_LD | BPF_H | BPF_ABS, 0, 0,
+				   SKF_AD_OFF + SKF_AD_RANDOM); }
 	;
 
 ldi
@@ -265,6 +271,9 @@ ld
 	| OP_LD K_POFF {
 		bpf_set_curr_instr(BPF_LD | BPF_W | BPF_ABS, 0, 0,
 				   SKF_AD_OFF + SKF_AD_PAY_OFFSET); }
+	| OP_LD K_RAND {
+		bpf_set_curr_instr(BPF_LD | BPF_W | BPF_ABS, 0, 0,
+				   SKF_AD_OFF + SKF_AD_RANDOM); }
 	| OP_LD 'M' '[' number ']' {
 		bpf_set_curr_instr(BPF_LD | BPF_MEM, 0, 0, $4); }
 	| OP_LD '[' 'x' '+' number ']' {
diff --git a/tools/net/icmp_random.bpf b/tools/net/icmp_random.bpf
new file mode 100644
index 0000000..b9adcbf
--- /dev/null
+++ b/tools/net/icmp_random.bpf
@@ -0,0 +1,12 @@
+# icmp random packet sampling, 1 in 4
+ldh [12]
+jne #0x800, drop
+ldb [23]
+jneq #1, drop
+# get a random uint32 number
+ld random
+mod #4
+jneq #1, drop
+ret #-1
+drop: ret #0
+
-- 
1.9.1.423.g4596e3a