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 <jrajaha...@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.
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 <b...@nicira.com>
Thanks,
Ben.
_______________________________________________
dev mailing list
dev@openvswitch.org
http://openvswitch.org/mailman/listinfo/dev
