[ovs-dev] dpcls: Miniflow match of packet and subtable

Van Haaren, Harry harry.van.haaren at intel.com
Fri Jun 15 10:25:43 UTC 2018


Hi Ben, Justin, William and Darrell,

Please see below email regarding performance optimization, I believe we can
speed up the mf_get_next_in_map() and related dpcls_lookup() code significantly
if we can confirm that the suggestion below is valid.

Your input and feedback would be very helpful.

Regards, -Harry



> -----Original Message-----
> From: Wang, Yipeng1
> Sent: Friday, June 1, 2018 9:46 PM
> To: Van Haaren, Harry <harry.van.haaren at intel.com>; ovs-dev at openvswitch.org
> Cc: Gobriel, Sameh <sameh.gobriel at intel.com>; jpettit at ovn.org; Ben Pfaff
> (blp at ovn.org) <blp at ovn.org>; William Tu <u9012063 at gmail.com>; dball at vmware.com
> Subject: RE: dpcls: Miniflow match of packet and subtable
> 
> Thanks Harry for explanation. I got your points :)
> 
> So I guess your proposal should work with two assumptions: 1) For packet
> miniflow bitmap, a bit as "0" means the packet header does not have the
> corresponding field. And 2) For subtable mask miniflow, a bit as "1" means all
> the rules in the subtable will have the corresponding field. Thus, you could
> safely skip the subtable if the packet header has a "0" on certain field but
> the mask of the subtable has a "1".
> 
> For the second proposal, if the rule added and the packet header searched
> agree on the same hashing range, it should work I think.
> 
> I add guys that I believe are more experts on miniflow extraction and megaflow
> translation to the CC list.
> 
> Thanks
> Yipeng
> 
> >-----Original Message-----
> >From: Van Haaren, Harry
> >Sent: Friday, June 1, 2018 2:30 AM
> >To: Wang, Yipeng1 <yipeng1.wang at intel.com>; ovs-dev at openvswitch.org
> >Cc: Gobriel, Sameh <sameh.gobriel at intel.com>
> >Subject: RE: dpcls: Miniflow match of packet and subtable
> >
> >> From: Wang, Yipeng1
> >> Sent: Tuesday, May 22, 2018 11:49 PM
> >> To: Van Haaren, Harry <harry.van.haaren at intel.com>; ovs-dev at openvswitch.org
> >> Cc: Gobriel, Sameh <sameh.gobriel at intel.com>
> >> Subject: RE: dpcls: Miniflow match of packet and subtable
> >>
> >> Hi, Harry,
> >>
> >> Welcome!
> >
> >Thanks!
> >
> >> Please see my reply inlined:
> >
> >My responses also inline, prefixed with [HvH]
> >
> >> >-----Original Message-----
> >> >From: ovs-dev-bounces at openvswitch.org [mailto:ovs-dev-
> >> bounces at openvswitch.org] On Behalf Of Van Haaren, Harry
> >> >Sent: Friday, May 18, 2018 3:10 AM
> >> >To: ovs-dev at openvswitch.org
> >> >Subject: [ovs-dev] dpcls: Miniflow match of packet and subtable
> >> >
> >> >Hi,
> >> >
> >> >My first post to OvS list - a quick hello! You may have seen me on the
> DPDK
> >> mailing list, where I send most of my patches. I'm looking
> >> >forward to working with yee folks of the OvS community :)
> >> >
> >> >I've been looking at optimizing the datapath classifier, and stumbled into
> >> a few concepts that I don't think I understand correctly. I've a
> >> >question below, any input or suggestions where to investigate next
> welcome!
> >> >
> >> >When matching the miniflows between packets and subtables, I believe a
> >> packet cannot match a subtable if the packet does not have
> >> >at least the miniflow bits set that the subtable miniflow has.
> >> >Eg:
> >> >o    subtable matches on nw_src (bit 63 of mf)
> >> >o    The packet miniflow does NOT have bit 63 set
> >> >o    Is it possible for this to packet to match the subtable? If yes, how?
> >> >
> >> [Wang, Yipeng] If the subtable mask set the nw_src to be "cared (meaning 1s
> >> in mask)", then incoming packets should consider these bits as "cared"
> >> during subtable lookup. Even if the packet has those bits as all 0s, it
> does
> >> not mean these bits are not "cared". It is still possible that this key
> >> matches one of the rules in this subtable. For example the rule in the
> table
> >> has nw_src as 0, e.g., an IP address of 0.0.0.0.  Then a packet with IP of
> >> 0.0.0.0 could match it.
> >
> >[HvH]
> >Yes I agree with you, the above 0.0.0.0 case the actual *contents* of the
> >miniflow could match zero, however the packet miniflow *bits* would
> >not have the IP-bit set, hence the metadata can be identified as not usable
> >for this subtable.
> >
> >Let me graph it up;
> >
> >/* bits as per offsetof(struct flow, FIELD_NAME) */
> >#define DP_PORT (52)
> >#define IPv4 (63)
> >#define IPv6 (73)
> >
> >Item     | MF bits        | MF Values (uint64_t blocks of metadata)
> >---------------------------------------------------------------------------
> >Subtable | IPv4           | 0xffffffff (mask) | not-used | not-used | ...
> >--- Rule | IPv4           | 1.2.3.4           | not-used | not-used | ...
> >
> >Eg: valid packet matching subtable:
> >Packet   | DP_PORT, IPv4  | 3 (dp port)       | 5.6.7.8 (IPv4)       |
> >
> >Eg: Packet that *cannot* match subtable
> >Packet   | DP_PORT, IPv6  | 3 (dp port)       | 11:22:33:44.. (IPv6) |
> >
> >
> >As such, a generalization that I *think* is valid, is this:
> >
> >if( (packet.mf_bits & subtable.mf_bits) != subtable.mf_bits) {
> >	// packet *cannot* match this rule it doesn't have required mf metadata
> >}
> >
> >
> >There is one possible case where even though the metadata is not present
> >it *could* (from a hash calculation point-of-view) still match the rule.
> >If the subtable *mask* is all zeros for a field, it could null out any
> metadata.
> >
> >I think that if a subtable mask is zero, that field can just be removed from
> the
> >mf-bits (aka, ignore field in the tuple-space-search, as it will always be a
> zero).
> >To state this another way: OVS could (perhaps already does) create a table
> without
> >matching on the masked-to-zero data.
> >
> >
> >
> >> >In the context of netdev_flow_key_hash_in_mask(), the mf_get_next_in_map()
> >> returns a zero value (uint64_t) which is added into
> >> >the hash if the bits isn't set in the packet. It seems like this is not
> >> required, as it doesn't add entropy to the hash itself. (It does change
> >> >the hash, as it jumbles around the existing set bits..)
> >> >
> >> >If we could remove these zero hashes from occurring, we could potentially
> >> speed up the core of the dpcls_lookup(). Has anybody
> >> >looked at this before? Am I mistaken in how the bits in the miniflow and
> >> wildcarding takes place?
> >>
> >> [Wang, Yipeng] You need to hash on those zeroes to find the correct rules.
> >> For example the rules in the subtable may also have all those bits as
> >> zeroes, and when you insert the rule, you insert with the hash that
> consider
> >> those zeroes. If you don't hash those bits of the packets, you may miss the
> >> rule.
> >
> >[HvH]
> >Yes agree with you again - indeed the current implementation requires the
> >zero hashes in order to arrive at the correct hash result.
> >
> >I guess I'm suggesting that we remove the zero-hashed values from *all* of
> the
> >hashing parts, given that they are not required for correct operation, but do
> >add overhead in mf_get_next_in_map(), as there are more blocks to iterate per
> pkt.
> >
> >
> >If there's somebody else who can double-check the logic above, that'd be
> fantastic.
> >I'm not sure who has the Miniflow matching experience in OvS community,
> @Yipeng do you know who to CC?
> >
> >Thanks for your input! -Harry
> >
> >
> >> We have been working on dpcls_lookup optimization for some time. I believe
> >> you might be aware of our DFC/CD patch
> >> (https://mail.openvswitch.org/pipermail/ovs-dev/2018-May/346986.html) which
> >> is to reduce the subtable count during lookup.
> >>
> >>
> >> Thanks
> >> Yipeng


More information about the dev mailing list