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 <[email protected]>; [email protected] > > Cc: Gobriel, Sameh <[email protected]>; [email protected]; Ben Pfaff > > ([email protected]) <[email protected]>; William Tu <[email protected]>; > > [email protected] > > 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 <[email protected]>; [email protected] > > >Cc: Gobriel, Sameh <[email protected]> > > >Subject: RE: dpcls: Miniflow match of packet and subtable > > > > > >> From: Wang, Yipeng1 > > >> Sent: Tuesday, May 22, 2018 11:49 PM > > >> To: Van Haaren, Harry <[email protected]>; > > >> [email protected] > > >> Cc: Gobriel, Sameh <[email protected]> > > >> 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: [email protected] [mailto:ovs-dev- > > >> [email protected]] On Behalf Of Van Haaren, Harry > > >> >Sent: Friday, May 18, 2018 3:10 AM > > >> >To: [email protected] > > >> >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 _______________________________________________ dev mailing list [email protected] https://mail.openvswitch.org/mailman/listinfo/ovs-dev
