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

Van Haaren, Harry harry.van.haaren at intel.com
Fri Jun 1 09:29:57 UTC 2018


> 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