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

Gurucharan Shetty shettyg at nicira.com
Thu May 22 20:17:31 UTC 2014


On Thu, 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.

It is fine from Visual Studio's perspective (it supports declarations
inside for statements).

>
> 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.
>
> 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.
>
> 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.
>
> 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?)
>
> 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.
>
> Acked-by: Ben Pfaff <blp at nicira.com>
>
>
> Thanks,
>
> Ben.



More information about the dev mailing list