[ovs-dev] [PATCH v2 2/2] lib/classifier: Optimize megaflows for single rule case.

[Jarno Rajahalme]

On May 22, 2014, at 10:43 AM, Ben Pfaff <blp at nicira.com> wrote:

> On Mon, May 19, 2014 at 12:35:46PM -0700, Jarno Rajahalme wrote:
>> When, during a classifier lookup, we narrow down to a single potential
>> rule, it is enough to match on ("unwildcard") one bit that differs
>> between the packet and the rule.
>> 
>> This is a special case of the more general algorithm, where it is
>> sufficient to match on enough bits that separates the packet from all
>> higher priority rules than the matched rule.  For a miss that would be
>> all the rules.  Implementing this is expensive for a more than a few
>> rules.  This patch starts by doing this for a single rule when we
>> already have it, also reducing the lookup cost by finishing the lookup
>> earlier than before.
>> 
>> Signed-off-by: Jarno Rajahalme <jrajahalme at nicira.com>
> 
> I've asked Guru (CCed) to find out whether the latest MSVC now
> supports declarations within "for" statements.  If it does, then we
> can get rid of the CodingStyle rule prohibiting that feature, which
> will make life easier.
> 

This from http://msdn.microsoft.com/en-us/library/hh409293.aspx (What's New for Visual C++ in Visual Studio 2013):

• Supports these ISO C99 language features:

	• _Bool

	• Compound literals.

	• Designated initializers.

	• Mixing declarations with code.

Guru promised to check that it actually works.

> If not, though, I would prefer to have MAP_FOR_EACH_INDEX require the
> client to pass in a suitable variable, because this is the style we
> use elsewhere (e.g. see SVEC_FOR_EACH).
> 
> Oh, I see that FLOW_FOR_EACH_IN_MAP introduced a new pattern.  I guess
> I didn't review that change.  Oh well.
> 
> I think that flow_get_next_in_map() (not introduced in this change)
> should have a "bool" return type.
> 

Thanks, this was clearly an oversight.

> I think that in miniflow_and_mask_matches_miniflow(), we are dealing
> with raw bits, so that really it doesn't matter much whether we use
> uint32_t or ovs_be32.  But if we use ovs_be32 then we end up having to
> do an extra pair of ntohl and htonl.  I think the only effect is that
> the "highest bit" becomes the network-byte-order highest bit, but I
> don't know whether that is valuable (some fields in a flow aren't even
> stored in network byte order).  Either way it's going to make testing
> a little tricky due to endianness issues.

The fields that we mostly care about matching in prefix order are the address and port fields (the same fields that tries are used for), and these are in the network byte order, hence the ovs_be32. I have a separate patch in works that matches on a prefix instead of the highest bit only. Currently it is not perfect due to only ever matching at most 32 bits, which can leave some of the highest bits wildcarded for wider fields (Ethernet and IPv6 addresses). 

> 
> If you were satisfied with the least-significant 1-bit, instead of the
> most-significant, then you could use the very cheap rightmost_1bit()
> function.  It might be worth defining a leftmost_1bit() function
> anyway, to clarify the code.

If we decide to match on one bit only, I agree that using the least significant 1-bit might not be less “random” than the most significant 1-bit. However, using the highest bit would be more likely to make the resulting megaflow match more packets (e.g., coming from the same subnet, v.s., individual hosts).

> 
> I think that miniflow_and_mask_matches_flow() deserves a comment
> update.
> 
> I find myself wondering whether we could end up with a funny
> paradoxical mask, e.g. mark some bit of a TCP port as looked at even
> though we didn't mark the IP protocol as looked at.  I am not sure
> whether this can happen or whether this is a problem.  Actually,
> looking further, I guess it can't happen because we always unwildcard
> all the fields up to the current stage when we jump to range_out.  In
> fact, I think that range_out wildcards the current stage, too: is that
> defeating the intended optimization here?  (I see that you updated the
> tests so presumably not?)

range_out: wildcards upto the beginning of the current stage (‘ofs.start’). But in this case we update the ‘ofs.start’ to be the end of the current range before this call… I have to investigate a bit more :-)

> 
> This is a satisfying optimization in that it actually simplifies
> logic.  The number of goto statements in find_match_wc(), on the other
> hand, is not so great, but I guess we can live with it.
> 

I’ll see if I can do something about the gotos. One idea is to return a range to be exact matched to the caller and have the caller do the "unwildcarding”.

> Acked-by: Ben Pfaff <blp at nicira.com>
> 
> 
> Thanks,
> 
> Ben.