With complicated flow tables and multiple levels of resubmit, I see
flow setup performance improvements of up to 5-6% with this patch.
Signed-off-by: Ben Pfaff <b...@nicira.com>
---
lib/classifier.c | 30 ++++++++++++++++++++++++++----
lib/classifier.h | 16 +++++++++++++++-
2 files changed, 41 insertions(+), 5 deletions(-)
diff --git a/lib/classifier.c b/lib/classifier.c
index 7192602..0ffaa8d 100644
--- a/lib/classifier.c
+++ b/lib/classifier.c
@@ -1,5 +1,5 @@
/*
- * Copyright (c) 2009, 2010, 2011, 2012 Nicira, Inc.
+ * Copyright (c) 2009, 2010, 2011, 2012, 2013 Nicira, Inc.
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
@@ -188,10 +188,17 @@ classifier_replace(struct classifier *cls, struct
cls_rule *rule)
if (!table) {
table = insert_table(cls, &rule->match.mask);
}
+ if (rule->priority > table->max_priority) {
+ table->max_priority = rule->priority;
+ }
old_rule = insert_rule(table, rule);
if (!old_rule) {
table->n_table_rules++;
+ if (table->n_table_rules > table->max_rules) {
+ table->max_rules = table->n_table_rules;
+ }
+
cls->n_rules++;
}
return old_rule;
@@ -235,6 +242,17 @@ classifier_remove(struct classifier *cls, struct cls_rule
*rule)
if (--table->n_table_rules == 0) {
destroy_table(cls, table);
+ } else if (table->n_table_rules < table->max_rules / 2) {
+ /* We've had a lot of deletions so reassess the maximum priority. */
+ struct cls_rule *head;
+
+ table->max_priority = 0;
+ HMAP_FOR_EACH (head, hmap_node, &table->rules) {
+ if (head->priority > table->max_priority) {
+ table->max_priority = head->priority;
+ }
+ }
+ table->max_rules = table->n_table_rules;
}
cls->n_rules--;
@@ -251,9 +269,11 @@ classifier_lookup(const struct classifier *cls, const
struct flow *flow)
best = NULL;
HMAP_FOR_EACH (table, hmap_node, &cls->tables) {
- struct cls_rule *rule = find_match(table, flow);
- if (rule && (!best || rule->priority > best->priority)) {
- best = rule;
+ if (!best || table->max_priority > best->priority) {
+ struct cls_rule *rule = find_match(table, flow);
+ if (rule && (!best || rule->priority > best->priority)) {
+ best = rule;
+ }
}
}
return best;
@@ -494,6 +514,8 @@ insert_table(struct classifier *cls, const struct minimask
*mask)
hmap_init(&table->rules);
minimask_clone(&table->mask, mask);
hmap_insert(&cls->tables, &table->hmap_node, minimask_hash(mask, 0));
+ table->max_priority = 0;
+ table->max_rules = 0;
return table;
}
diff --git a/lib/classifier.h b/lib/classifier.h
index bc9db33..31ff375 100644
--- a/lib/classifier.h
+++ b/lib/classifier.h
@@ -1,5 +1,5 @@
/*
- * Copyright (c) 2009, 2010, 2011, 2012 Nicira, Inc.
+ * Copyright (c) 2009, 2010, 2011, 2012, 2013 Nicira, Inc.
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
@@ -49,6 +49,20 @@ struct cls_table {
struct hmap rules; /* Contains "struct cls_rule"s. */
struct minimask mask; /* Wildcards for fields. */
int n_table_rules; /* Number of rules, including duplicates. */
+
+ /* Optimize lookups by tracking the maximum priority of rules in the table.
+ * If a lookup finds a matching rule with a given priority, then it can
+ * skip over any tables whose 'max_priority' is less than or equal to that
+ * priority.
+ *
+ * The value of 'max_priority' is conservative: it can be larger than the
+ * largest priority actually found in 'rules'. This happens if a rule with
+ * a high priority is inserted, then later removed. To make sure that
+ * 'max_priority' can eventually get adjusted downward, we refresh it after
+ * any sequence of deletions that reduces the size of the table by over
+ * half. */
+ unsigned int max_priority; /* Max 'priority' of any rule in 'rules'. */
+ unsigned int max_rules; /* Max size of table size last refresh. */
};
/* Returns true if 'table' is a "catch-all" table that will match every
--
1.7.2.5
_______________________________________________
dev mailing list
dev@openvswitch.org
http://openvswitch.org/mailman/listinfo/dev
