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

Van Haaren, Harry harry.van.haaren at intel.com
Mon Jun 18 09:21:22 UTC 2018 

Hey Ben,

Answer broken into points 1) and 2) as discussion before.
I've added labels 3) 4) and 5) to aid future discussion.


1) Miniflow bit setting:
Reworded: the miniflow is a summary of the packet.
If a particular bit is set in a miniflow, it indicates
the packet has that property. Eg: ipv6_src = bit 65

For an ipv6 packet, bit 65 is set and miniflow_extract()
pushes the ipv6_src data to the miniflow "values" array.

Hence, if there is no ipv6 header in the packet, the bit
will be zero, and no data is present in the values array.


2) Subtable miniflow bits:
A subtable has a miniflow bitmask, which indicates the
properties of a packet that it matches on. Eg: ipv6_src is
set, so the ipv6 block of metadata will be matched on.

>From my understanding: if a packet does not have any ipv6_src
metadata, it cannot match a subtable that matches on ipv6_src.


3) Generalizing the rule:
To generalize this, if a subtable matches on a field X,
and the packet does not contain field X, the packet cannot
match the subtable. Or if you prefer code:

if ((pkt.bits & subtable.bits) != subtable.bits)
   /* skip packet - it doesn't have all the subtable bits */


4) VLANs:
About the VLAN specific case - miniflow_extract() pushes a
VLAN "block" into every eth packet, (see parse_vlan(), note
the |= of VLAN_CFI). This addition of metadata to the packet
does not break the above - it may cause the dpcls() to attempt
to match a packet against a subtable that it actually doesn't
match, however the hash lookup or verify of the rule handles it.


5) Summary
Currently, *every* packet miniflow is matched against *every*
subtable miniflow.

When matching a packet, I believe we can skip any subtable that
has bits set in the miniflow, which are NOT also present in the
packet miniflow.

The end result should be much less time spent iterating miniflows,
which is currently consuming a large amount of datapath CPU cycles.


If there are any open questions, please do ask!
Regards, -Harry



> -----Original Message-----
> From: Wang, Yipeng1
> Sent: Friday, June 15, 2018 10:09 PM
> To: Ben Pfaff <blp at ovn.org>; Van Haaren, Harry <harry.van.haaren at intel.com>
> Cc: jpettit at ovn.org; William Tu <u9012063 at gmail.com>; dball at vmware.com;
> Gobriel, Sameh <sameh.gobriel at intel.com>; ovs-dev at openvswitch.org
> Subject: RE: dpcls: Miniflow match of packet and subtable
> 
> 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:blp at ovn.org]
> > Sent: Friday, June 15, 2018 12:39 PM
> > To: Van Haaren, Harry <harry.van.haaren at intel.com>
> > Cc: jpettit at ovn.org; William Tu <u9012063 at gmail.com>;
> > dball at vmware.com; Gobriel, Sameh <sameh.gobriel at intel.com>; Wang,
> > Yipeng1 <yipeng1.wang at intel.com>; ovs-dev at 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.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.h
> > > > >> tml) which is to reduce the subtable count during lookup.
> > > > >>
> > > > >>
> > > > >> Thanks
> > > > >> Yipeng

More information about the dev mailing list