Make comparison done after matching hash values faster by optimizing
for the expected success.
Signed-off-by: Jarno Rajahalme <jrajaha...@nicira.com>
---
lib/classifier.c | 2 +-
lib/match.c | 22 ++++++++++++++++++++++
lib/match.h | 2 ++
3 files changed, 25 insertions(+), 1 deletion(-)
diff --git a/lib/classifier.c b/lib/classifier.c
index 5587141..36e19a5 100644
--- a/lib/classifier.c
+++ b/lib/classifier.c
@@ -781,7 +781,7 @@ find_match(const struct cls_subtable *subtable, const
struct flow *flow)
struct cls_rule *rule;
HMAP_FOR_EACH_WITH_HASH (rule, hmap_node, hash, &subtable->rules) {
- if (minimatch_matches_flow(&rule->match, flow)) {
+ if (minimatch_matches_flow_likely(&rule->match, flow)) {
return rule;
}
}
diff --git a/lib/match.c b/lib/match.c
index 35356c1..78399a4 100644
--- a/lib/match.c
+++ b/lib/match.c
@@ -1184,6 +1184,28 @@ minimatch_matches_flow(const struct minimatch *match,
return true;
}
+/* Returns true if 'target' satisifies 'match', that is, if each bit for which
+ * 'match' specifies a particular value has the correct value in 'target'.
+ *
+ * This function is equivalent to miniflow_equal_flow_in_minimask(&match->flow,
+ * target, &match->mask) but it is faster because of the invariant that
+ * match->flow.map and match->mask.map are the same. */
+bool
+minimatch_matches_flow_likely(const struct minimatch *match,
+ const struct flow *target)
+{
+ const uint32_t *target_u32 = (const uint32_t *) target;
+ const uint32_t *flowp = match->flow.values;
+ const uint32_t *maskp = match->mask.masks.values;
+ uint64_t map;
+ uint32_t diff = 0;
+
+ for (map = match->flow.map; map; map = zero_rightmost_1bit(map)) {
+ diff |= (*flowp++ ^ target_u32[raw_ctz64(map)]) & *maskp++;
+ }
+ return !diff;
+}
+
/* Appends a string representation of 'match' to 's'. If 'priority' is
* different from OFP_DEFAULT_PRIORITY, includes it in 's'. */
void
diff --git a/lib/match.h b/lib/match.h
index 1e938a1..b310820 100644
--- a/lib/match.h
+++ b/lib/match.h
@@ -158,6 +158,8 @@ bool minimatch_equal(const struct minimatch *a, const
struct minimatch *b);
uint32_t minimatch_hash(const struct minimatch *, uint32_t basis);
bool minimatch_matches_flow(const struct minimatch *, const struct flow *);
+bool minimatch_matches_flow_likely(const struct minimatch *,
+ const struct flow *);
void minimatch_format(const struct minimatch *, struct ds *,
unsigned int priority);
--
1.7.10.4
_______________________________________________
dev mailing list
dev@openvswitch.org
http://openvswitch.org/mailman/listinfo/dev
