Re: [ovs-dev] [iovisor-dev] [RFC PATCH 00/11] OVS eBPF datapath.
>
> d71962f ("bpf: allow map helpers access to map values directly") removes
> that limitation from the verifier and should allow you to use map values
> as map keys directly. 4.18-rc1 has it.
>
>> Thanks
>> William
Hi Paul,
Thanks a lot! This is very helpful.
I'm testing it now, works great so far, and saves lots of bpf stack space.
Regards,
William
___
dev mailing list
d...@openvswitch.org
https://mail.openvswitch.org/mailman/listinfo/ovs-dev
Re: [ovs-dev] [iovisor-dev] [RFC PATCH 00/11] OVS eBPF datapath.
On Wed, Jul 04, 2018 at 07:25:50PM -0700, William Tu wrote:
> On Tue, Jul 3, 2018 at 10:56 AM, Alexei Starovoitov
> wrote:
> > On Thu, Jun 28, 2018 at 07:19:35AM -0700, William Tu wrote:
> >> Hi Alexei,
> >>
> >> Thanks a lot for the feedback!
> >>
> >> On Wed, Jun 27, 2018 at 8:00 PM, Alexei Starovoitov
> >> wrote:
> >> > On Sat, Jun 23, 2018 at 05:16:32AM -0700, William Tu wrote:
> >> >>
> >> >> Discussion
> >> >> ==
> >> >> We are still actively working on finishing the feature, currently
> >> >> the basic forwarding and tunnel feature work, but still under
> >> >> heavy debugging and development. The purpose of this RFC is to
> >> >> get some early feedbacks and direction for finishing the complete
> >> >> features in existing kernel's OVS datapath (the net/openvswitch/*).
> >> >
> >> > Thank you for sharing the patches.
> >> >
> >> >> Three major issues we are worried:
> >> >> a. Megaflow support in BPF.
> >> >> b. Connection Tracking support in BPF.
> >> >
> >> > my opinion on the above two didn't change.
> >> > To recap:
> >> > A. Non scalable megaflow map is no go. I'd like to see packet
> >> > classification
> >> > algorithm like hicuts or efficuts to be implemented instead, since it
> >> > can be
> >> > shared by generic bpf, bpftiler, ovs and likely others.
> >>
> >> We did try the decision tree approach using dpdk's acl lib. The lookup
> >> speed is 6 times faster than the magaflow using tuple space.
> >> However, the update/insertion requires rebuilding/re-balancing the decision
> >> tree so it's way too slow. I think hicuts or efficuts suffers the same
> >> issue.
> >> So decision tree algos are scalable only for lookup operation due to its
> >> optimization over tree depth, but not scalable under
> >> update/insert/delete operations.
> >>
> >> On customer's system we see megaflow update/insert rate around 10
> >> rules/sec,
> >> this makes decision tree unusable, unless we invent something to optimize
> >> the
> >> update/insert time or incremental update of these decision tree algo.
> >
> > is this a typo? you probably meant 10K rule updates a second ?
> I mean "new" rules being added at 10 rules/sec.
> Update rate might be much higher.
>
> > Last time I've dealt with these algorithms we had 100K acl updates a second.
> > It was an important metric that we were optimizing for.
> > I'm pretty sure '*cuts' algos do many thousands per second non optimized.
>
> When adding a new rule, do these algorithms require rebuilding the
> entire tree?
>
> In our evaluation, updating an existing entry in the decision tree
> performs OK, because it is equal to lookup and replace, and lookup
> is fast, update is just atomic swap. But inserting a new rule is slow,
> because it requires re-building the tree using all existing rules.
> And we see new rule being added at rate 10 rules per second.
> So we are constantly rebuilding the entire tree.
>
> If the entire tree has 100k of rules, it takes around 2 seconds to rebuild,
> based on the dpdk acl library. And without an incremental algorithm,
> adding 1 new rule will trigger rebuilding the 100k of rules, and it is too
> slow.
>
> Reading through HyperCuts and EffiCuts, I'm not sure how it supports
> incrementally adding a new rule, without rebuilding the entire tree.
> http://ccr.sigcomm.org/online/files/p207.pdf
> http://cseweb.ucsd.edu/~susingh/papers/hyp-sigcomm03.pdf
>
> The HyperCuts papers says
> "A fast update algorithm can also be implemented; however we do not
> go into the details of incremental update in this paper"
>
> >
> >> >> c. Verifier limitation.
> >> >
> >> > Not sure what limitations you're concerned about.
> >> >
> >>
> >> Mostly related to stack. The flow key OVS uses (struct sw_flow_key)
> >> is 464 byte. We trim a lot, now around 300 byte, but still huge,
> >> considering
> >> the BPF's stack limit is 512 byte.
> >
> > have you tried using per-cpu array of one element with large value
> > instead of stack?
>
> yes, now we store the flow key in percpu array with 1 element.
>
> > In the latest verifier most of the operations that can be done with the
> > stack
> > pointer can be done with pointer to map value too.
> >
> Once the flow key is stored in map, another eBPF program
> needs to use that key to lookup flow table (another map).
> So we have to store the flow key on stack first, in order to
> use it as key to lookup the flow table map.
>
> Is there a way to work around it?
d71962f ("bpf: allow map helpers access to map values directly") removes
that limitation from the verifier and should allow you to use map values
as map keys directly. 4.18-rc1 has it.
> Thanks
> William
___
dev mailing list
d...@openvswitch.org
https://mail.openvswitch.org/mailman/listinfo/ovs-dev
Re: [ovs-dev] [iovisor-dev] [RFC PATCH 00/11] OVS eBPF datapath.
On Tue, Jul 3, 2018 at 10:56 AM, Alexei Starovoitov wrote: > On Thu, Jun 28, 2018 at 07:19:35AM -0700, William Tu wrote: >> Hi Alexei, >> >> Thanks a lot for the feedback! >> >> On Wed, Jun 27, 2018 at 8:00 PM, Alexei Starovoitov >> wrote: >> > On Sat, Jun 23, 2018 at 05:16:32AM -0700, William Tu wrote: >> >> >> >> Discussion >> >> == >> >> We are still actively working on finishing the feature, currently >> >> the basic forwarding and tunnel feature work, but still under >> >> heavy debugging and development. The purpose of this RFC is to >> >> get some early feedbacks and direction for finishing the complete >> >> features in existing kernel's OVS datapath (the net/openvswitch/*). >> > >> > Thank you for sharing the patches. >> > >> >> Three major issues we are worried: >> >> a. Megaflow support in BPF. >> >> b. Connection Tracking support in BPF. >> > >> > my opinion on the above two didn't change. >> > To recap: >> > A. Non scalable megaflow map is no go. I'd like to see packet >> > classification >> > algorithm like hicuts or efficuts to be implemented instead, since it can >> > be >> > shared by generic bpf, bpftiler, ovs and likely others. >> >> We did try the decision tree approach using dpdk's acl lib. The lookup >> speed is 6 times faster than the magaflow using tuple space. >> However, the update/insertion requires rebuilding/re-balancing the decision >> tree so it's way too slow. I think hicuts or efficuts suffers the same issue. >> So decision tree algos are scalable only for lookup operation due to its >> optimization over tree depth, but not scalable under >> update/insert/delete operations. >> >> On customer's system we see megaflow update/insert rate around 10 rules/sec, >> this makes decision tree unusable, unless we invent something to optimize the >> update/insert time or incremental update of these decision tree algo. > > is this a typo? you probably meant 10K rule updates a second ? I mean "new" rules being added at 10 rules/sec. Update rate might be much higher. > Last time I've dealt with these algorithms we had 100K acl updates a second. > It was an important metric that we were optimizing for. > I'm pretty sure '*cuts' algos do many thousands per second non optimized. When adding a new rule, do these algorithms require rebuilding the entire tree? In our evaluation, updating an existing entry in the decision tree performs OK, because it is equal to lookup and replace, and lookup is fast, update is just atomic swap. But inserting a new rule is slow, because it requires re-building the tree using all existing rules. And we see new rule being added at rate 10 rules per second. So we are constantly rebuilding the entire tree. If the entire tree has 100k of rules, it takes around 2 seconds to rebuild, based on the dpdk acl library. And without an incremental algorithm, adding 1 new rule will trigger rebuilding the 100k of rules, and it is too slow. Reading through HyperCuts and EffiCuts, I'm not sure how it supports incrementally adding a new rule, without rebuilding the entire tree. http://ccr.sigcomm.org/online/files/p207.pdf http://cseweb.ucsd.edu/~susingh/papers/hyp-sigcomm03.pdf The HyperCuts papers says "A fast update algorithm can also be implemented; however we do not go into the details of incremental update in this paper" > >> >> c. Verifier limitation. >> > >> > Not sure what limitations you're concerned about. >> > >> >> Mostly related to stack. The flow key OVS uses (struct sw_flow_key) >> is 464 byte. We trim a lot, now around 300 byte, but still huge, considering >> the BPF's stack limit is 512 byte. > > have you tried using per-cpu array of one element with large value > instead of stack? yes, now we store the flow key in percpu array with 1 element. > In the latest verifier most of the operations that can be done with the stack > pointer can be done with pointer to map value too. > Once the flow key is stored in map, another eBPF program needs to use that key to lookup flow table (another map). So we have to store the flow key on stack first, in order to use it as key to lookup the flow table map. Is there a way to work around it? Thanks William ___ dev mailing list d...@openvswitch.org https://mail.openvswitch.org/mailman/listinfo/ovs-dev
Re: [ovs-dev] [iovisor-dev] [RFC PATCH 00/11] OVS eBPF datapath.
Hi Alexei, Thanks a lot for the feedback! On Wed, Jun 27, 2018 at 8:00 PM, Alexei Starovoitov wrote: > On Sat, Jun 23, 2018 at 05:16:32AM -0700, William Tu wrote: >> >> Discussion >> == >> We are still actively working on finishing the feature, currently >> the basic forwarding and tunnel feature work, but still under >> heavy debugging and development. The purpose of this RFC is to >> get some early feedbacks and direction for finishing the complete >> features in existing kernel's OVS datapath (the net/openvswitch/*). > > Thank you for sharing the patches. > >> Three major issues we are worried: >> a. Megaflow support in BPF. >> b. Connection Tracking support in BPF. > > my opinion on the above two didn't change. > To recap: > A. Non scalable megaflow map is no go. I'd like to see packet classification > algorithm like hicuts or efficuts to be implemented instead, since it can be > shared by generic bpf, bpftiler, ovs and likely others. We did try the decision tree approach using dpdk's acl lib. The lookup speed is 6 times faster than the magaflow using tuple space. However, the update/insertion requires rebuilding/re-balancing the decision tree so it's way too slow. I think hicuts or efficuts suffers the same issue. So decision tree algos are scalable only for lookup operation due to its optimization over tree depth, but not scalable under update/insert/delete operations. On customer's system we see megaflow update/insert rate around 10 rules/sec, this makes decision tree unusable, unless we invent something to optimize the update/insert time or incremental update of these decision tree algo. Now my backup plan is to implement megaflow in BPF. > B. instead of helpers to interface with conntrack the way ovs did, I prefer > a generic conntrack mechanism that can be used out of xdp too > OK. We will work on this direction. >> c. Verifier limitation. > > Not sure what limitations you're concerned about. > Mostly related to stack. The flow key OVS uses (struct sw_flow_key) is 464 byte. We trim a lot, now around 300 byte, but still huge, considering the BPF's stack limit is 512 byte. We can always break the large program then tail call, but sometimes the register spills on the stack, and when restore, the states is gone and verifier fails. This is more difficult for us to work around. Below is an example: at 203: r7 is a const and store on stack (r10 - 248) at 250: r2 reads (r10 - 248) back. at 251: fails the verifier from 27 to 201: R0=map_value(id=0,off=0,ks=4,vs=4352,imm=0) R7=inv(id=0,umax_value=31,var_off=(0x0; 0x1f)) R9=ctx(id=0,off=0,imm=0) R10=fp0,call_-1 201: (7b) *(u64 *)(r10 -256) = r0 202: (27) r7 *= 136 203: (7b) *(u64 *)(r10 -248) = r7 204: (bf) r6 = r0 205: (0f) r6 += r7 206: (b7) r8 = 2 207: (15) if r6 == 0x0 goto pc+93 R0=map_value(id=0,off=0,ks=4,vs=4352,imm=0) R6=map_value(id=0,off=0,ks=4,vs=4352,umax_value=4216,var_off=(0x0; 0x1ff8)) R7=inv(id=0,umax_value=4216,var_off=(0x0; 0x1ff8)) R8=inv2 R9=ctx(id=0,off=0,imm=0) R10=fp0,call_-1 fp-256=map_value 208: (b7) r1 = 681061 209: (63) *(u32 *)(r10 -200) = r1 210: (18) r1 = 0x6b73616d20746573 212: (7b) *(u64 *)(r10 -208) = r1 213: (bf) r1 = r10 214: (07) r1 += -208 215: (b7) r2 = 12 216: (85) call bpf_trace_printk#6 217: (bf) r7 = r6 218: (07) r7 += 8 219: (61) r1 = *(u32 *)(r6 +8) R0=inv(id=0) R6=map_value(id=0,off=0,ks=4,vs=4352,umax_value=4216,var_off=(0x0; 0x1ff8)) R7_w=map_value(id=0,off=8,ks=4,vs=4352,umax_value=4216,var_off=(0x0; 0x1ff8)) R8=inv2 R9=ctx(id=0,off=0,imm=0) R10=fp0,call_-1 fp-256=map_value 220: (15) if r1 == 0x7 goto pc+82 R0=inv(id=0) R1=inv(id=0,umax_value=4294967295,var_off=(0x0; 0x)) R6=map_value(id=0,off=0,ks=4,vs=4352,umax_value=4216,var_off=(0x0; 0x1ff8)) R7=map_value(id=0,off=8,ks=4,vs=4352,umax_value=4216,var_off=(0x0; 0x1ff8)) R8=inv2 R9=ctx(id=0,off=0,imm=0) R10=fp0,call_-1 fp-256=map_value 221: (55) if r1 != 0x4 goto pc+228 R0=inv(id=0) R1=inv4 R6=map_value(id=0,off=0,ks=4,vs=4352,umax_value=4216,var_off=(0x0; 0x1ff8)) R7=map_value(id=0,off=8,ks=4,vs=4352,umax_value=4216,var_off=(0x0; 0x1ff8)) R8=inv2 R9=ctx(id=0,off=0,imm=0) R10=fp0,call_-1 fp-256=map_value 222: (61) r1 = *(u32 *)(r9 +80) 223: (7b) *(u64 *)(r10 -264) = r1 224: (61) r6 = *(u32 *)(r9 +76) 225: (b7) r1 = 0 226: (73) *(u8 *)(r10 -198) = r1 227: (b7) r1 = 2674 228: (6b) *(u16 *)(r10 -200) = r1 229: (18) r1 = 0x6568746520746573 231: (7b) *(u64 *)(r10 -208) = r1 232: (bf) r1 = r10 233: (07) r1 += -208 234: (b7) r2 = 11 235: (85) call bpf_trace_printk#6 236: (bf) r1 = r6 237: (07) r1 += 14 238: (79) r2 = *(u64 *)(r10 -264) 239: (2d) if r1 > r2 goto pc+61 R0=inv(id=0) R1=pkt(id=0,off=14,r=14,imm=0) R2=pkt_end(id=0,off=0,imm=0) R6=pkt(id=0,off=0,r=14,imm=0) R7=map_value(id=0,off=8,ks=4,vs=4352,umax_value=4216,var_off=(0x0; 0x1ff8)) R8=inv2 R9=ctx(id=0,off=0,imm=0) R10=fp0,call_-1 fp-256=map_value fp-264=pkt_end 240: (71) r1 = *(u8 *)(r7 +10) R0=inv(id=0) R1_w=pkt(id=0,off=14,r=14,imm=0)
Re: [ovs-dev] [iovisor-dev] [RFC PATCH 00/11] OVS eBPF datapath.
On Sat, Jun 23, 2018 at 05:16:32AM -0700, William Tu wrote: > > Discussion > == > We are still actively working on finishing the feature, currently > the basic forwarding and tunnel feature work, but still under > heavy debugging and development. The purpose of this RFC is to > get some early feedbacks and direction for finishing the complete > features in existing kernel's OVS datapath (the net/openvswitch/*). Thank you for sharing the patches. > Three major issues we are worried: > a. Megaflow support in BPF. > b. Connection Tracking support in BPF. my opinion on the above two didn't change. To recap: A. Non scalable megaflow map is no go. I'd like to see packet classification algorithm like hicuts or efficuts to be implemented instead, since it can be shared by generic bpf, bpftiler, ovs and likely others. B. instead of helpers to interface with conntrack the way ovs did, I prefer a generic conntrack mechanism that can be used out of xdp too > c. Verifier limitation. Not sure what limitations you're concerned about. ___ dev mailing list d...@openvswitch.org https://mail.openvswitch.org/mailman/listinfo/ovs-dev
