Hi, Ben, Your understand of my point 2 is correct. But more specifically, by "0" or "1" I mean the bit in "flowmap map" of the miniflow. Just as a remind, here is the code comment of the flowmap:
* The map member hold one bit for each uint64_t in a "struct flow". Each * 0-bit indicates that the corresponding uint64_t is zero, each 1-bit that it * *may* be nonzero (see below how this applies to minimasks). My point 1 ((also Harry first brought it up) is: for packet key, a bit "0" in the miniflow flowmap means the corresponding protocol field definitely does not exist in the packet header (This seems true from miniflow_extract(). For example, 0 in flowmap that maps to L4 field, means the packet does not have L4 fields). My point 2, as you restated, is: a bit "1" in the flowmap of the subtable mask means the corresponding protocol field has to be present in the packet header to find a match (for example, if the miniflow flowmap of subtable mask shows "1" for L4 field, then the packet has to have L4 header to match). If both points hold, then Harry's proposal should work. Which is if the packet header miniflow flowmap has a bit "0" but the same bit in the subtable mask is "1", then we should just skip the subtable, by only comparing the flowmap, which is short. And as you suggested, there are exceptions like the VLAN example you mentioned that we have to check very carefully. > -----Original Message----- > From: Ben Pfaff [mailto:b...@ovn.org] > Sent: Friday, June 15, 2018 12:39 PM > To: Van Haaren, Harry <harry.van.haa...@intel.com> > Cc: jpet...@ovn.org; William Tu <u9012...@gmail.com>; > db...@vmware.com; Gobriel, Sameh <sameh.gobr...@intel.com>; Wang, > Yipeng1 <yipeng1.w...@intel.com>; ovs-dev@openvswitch.org > Subject: Re: dpcls: Miniflow match of packet and subtable > > 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.haa...@intel.com>; > > > ovs-dev@openvswitch.org > > > Cc: Gobriel, Sameh <sameh.gobr...@intel.com>; jpet...@ovn.org; Ben > > > Pfaff > > > (b...@ovn.org) <b...@ovn.org>; William Tu <u9012...@gmail.com>; > > > db...@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.w...@intel.com>; ovs- > d...@openvswitch.org > > > >Cc: Gobriel, Sameh <sameh.gobr...@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.haa...@intel.com>; > > > >> ovs-dev@openvswitch.org > > > >> Cc: Gobriel, Sameh <sameh.gobr...@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-boun...@openvswitch.org [mailto:ovs-dev- > > > >> boun...@openvswitch.org] On Behalf Of Van Haaren, Harry > > > >> >Sent: Friday, May 18, 2018 3:10 AM > > > >> >To: ovs-dev@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.h > > > >> tml) which is to reduce the subtable count during lookup. > > > >> > > > >> > > > >> Thanks > > > >> Yipeng _______________________________________________ dev mailing list d...@openvswitch.org https://mail.openvswitch.org/mailman/listinfo/ovs-dev
