On Tue, Nov 19, 2013 at 11:20:37AM -0800, Jarno Rajahalme wrote:
> Signed-off-by: Jarno Rajahalme <[email protected]>
miniflow_get_map_in_range() is longer than I would ordinarily write as
inline in a header file. Do you have a special reason to do that?
I spent some time studying find_match_wc(). I think that the time for
'rl != rule' is equivalent to 'rule == NULL', because once we've
narrowed the possibilities down to a single rule, that rule can't
change as we look further (if it did, that would indicate a bug, I
believe). Once I figured that out, it seemed that the logic could be
simplified slightly, at least from my point of view.
It also seemed like the relationship between find_match_wc() and
find_match() could be simplified a bit.
So here's what I suggest folding in, I'm curious to see what you
think.
Thanks,
Ben.
diff --git a/lib/classifier.c b/lib/classifier.c
index 7f7aa84..f94cb96 100644
--- a/lib/classifier.c
+++ b/lib/classifier.c
@@ -41,8 +41,6 @@ static void update_subtables_after_removal(struct classifier
*,
struct cls_subtable *,
unsigned int del_priority);
-static struct cls_rule *find_match(const struct cls_subtable *,
- const struct flow *);
static struct cls_rule *find_match_wc(const struct cls_subtable *,
const struct flow *,
struct flow_wildcards *);
@@ -397,8 +395,7 @@ classifier_lookup(const struct classifier *cls, const
struct flow *flow,
continue;
}
- rule = (wc) ? find_match_wc(subtable, flow, wc)
- : find_match(subtable, flow);
+ rule = find_match_wc(subtable, flow, wc);
if (rule) {
best = rule;
LIST_FOR_EACH_CONTINUE (subtable, list_node,
@@ -412,8 +409,7 @@ classifier_lookup(const struct classifier *cls, const
struct flow *flow,
continue;
}
- rule = (wc) ? find_match_wc(subtable, flow, wc)
- : find_match(subtable, flow);
+ rule = find_match_wc(subtable, flow, wc);
if (rule && rule->priority > best->priority) {
best = rule;
}
@@ -825,9 +821,9 @@ update_subtables_after_removal(struct classifier *cls,
}
static struct cls_rule *
-find_match(const struct cls_subtable *subtable, const struct flow *flow)
+find_match(const struct cls_subtable *subtable, const struct flow *flow,
+ uint32_t hash)
{
- uint32_t hash = flow_hash_in_minimask(flow, &subtable->mask, 0);
struct cls_rule *rule;
HMAP_FOR_EACH_WITH_HASH (rule, hmap_node, hash, &subtable->rules) {
@@ -848,6 +844,11 @@ find_match_wc(const struct cls_subtable *subtable, const
struct flow *flow,
uint8_t prev_u32ofs = 0;
int i;
+ if (!wc) {
+ return find_match(subtable, flow,
+ flow_hash_in_minimask(flow, &subtable->mask, 0));
+ }
+
/* Try to finish early by checking fields in segments. */
for (i = 0; i < subtable->n_indices; i++) {
struct hindex_node *inode;
@@ -863,35 +864,37 @@ find_match_wc(const struct cls_subtable *subtable, const
struct flow *flow,
prev_u32ofs);
return NULL;
}
- /* Check if we have narrowed down to a single rule already. This
- * check shows a measurable benefit with non-trivial flow tables.
- * (Rare) hash collisions may cause us to miss the opportunity for
- * this optimization. */
- if (!inode->s) {
- struct cls_rule *rl;
- /* Found single candidate. */
- ASSIGN_CONTAINER(rl, inode - i, index_nodes);
- /* Do not check same rule again. */
- if (rl != rule) {
- rule = rl; /* Update last rule we looked at. */
- if (minimatch_matches_flow(&rule->match, flow)) {
- /* Found match, no need to look further. */
- goto out;
- }
+
+ /* If we have narrowed down to a single rule already, check whether
+ * that rule matches. If it does match, then we're done. If it does
+ * not match, then we know that we will never get a match, but we do
+ * not yet know how many wildcards we need to fold into 'wc' so we
+ * continue iterating through indices to find that out. (We won't
+ * waste time calling minimatch_matches_flow() again because we've set
+ * 'rule' nonnull.)
+ *
+ * This check shows a measurable benefit with non-trivial flow tables.
+ *
+ * (Rare) hash collisions may cause us to miss the opportunity for this
+ * optimization. */
+ if (!inode->s && !rule) {
+ ASSIGN_CONTAINER(rule, inode - i, index_nodes);
+ if (minimatch_matches_flow(&rule->match, flow)) {
+ goto out;
}
}
}
- /* Have 'rule' already only if there is a single non-matching rule. */
+
if (!rule) {
+ /* Multiple potential matches exist, look for one. */
hash = flow_hash_in_minimask_range(flow, &subtable->mask, prev_u32ofs,
FLOW_U32S, &basis);
- HMAP_FOR_EACH_WITH_HASH (rule, hmap_node, hash, &subtable->rules) {
- if (minimatch_matches_flow(&rule->match, flow)) {
- goto out;
- }
- }
+ rule = find_match(subtable, flow, hash);
+ } else {
+ /* We already narrowed the matching candidates down to just 'rule',
+ * but it didn't match. */
+ rule = NULL;
}
- rule = NULL;
out:
flow_wildcards_fold_minimask(wc, &subtable->mask);
return rule;
_______________________________________________
dev mailing list
[email protected]
http://openvswitch.org/mailman/listinfo/dev
