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

Ben Pfaff blp at ovn.org
Fri Jun 15 19:39:13 UTC 2018


I think I understand Yipeng's point 2.  Please allow me to restate it:
if a flow's field has a 1-bit in its mask, then the field must exist in
the packet for the flow to match.  This is true.  (There are some
technical exceptions: for example, OVS and OpenFlow handle VLANs in an
unusual way that allows matching on VLAN fields even when they are not
present.)

I don't understand point 1 yet.  Can you restate or expand on it, or
give an example?

On Fri, Jun 15, 2018 at 10:25:43AM +0000, Van Haaren, Harry wrote:
> 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