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

Fri Jun 1 20:46:17 UTC 2018

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