classifier: Speed up lookup when metadata partitions the flow table.

We have a controller that puts many rules with different metadata values
into the flow table, where metadata is used (by "resubmit"s) to distinguish
stages in a pipeline.  Thus, any given flow only needs to be hashed into
classifier "cls_table"s that contain a match for the flow's metadata value.
This commit optimizes the classifier lookup by (probabilistically) skipping
the "cls_table"s that can't possibly match.

(The "metadata" referred to here is the OpenFlow 1.1+ "metadata" field,
which is a 64-bit field similar in purpose to the "registers" defined by
Open vSwitch.)

Previous versions of this patch, with earlier versions of the controller in
question, improved flow setup performance by about 19%.

Bug #14282.
Signed-off-by: Ben Pfaff <blp@nicira.com>

1 files changed, 88 insertions, 5 deletions

diff --git a/lib/classifier.h b/lib/classifier.h
index a795b4a1..00848f8e 100644
--- a/lib/classifier.h
+++ b/lib/classifier.h
@@ -19,11 +19,80 @@
 
 /* Flow classifier.
  *
- * A classifier is a "struct classifier",
- *      a hash map from a set of wildcards to a "struct cls_table",
- *              a hash map from fixed field values to "struct cls_rule",
- *                      which can contain a list of otherwise identical rules
- *                      with lower priorities.
+ *
+ * What?
+ * =====
+ *
+ * A flow classifier holds any number of "rules", each of which specifies
+ * values to match for some fields or subfields and a priority.  The primary
+ * design goal for the classifier is that, given a packet, it can as quickly as
+ * possible find the highest-priority rule that matches the packet.
+ *
+ * Each OpenFlow table is implemented as a flow classifier.
+ *
+ *
+ * Basic Design
+ * ============
+ *
+ * Suppose that all the rules in a classifier had the same form.  For example,
+ * suppose that they all matched on the source and destination Ethernet address
+ * and wildcarded all the other fields.  Then the obvious way to implement a
+ * classifier would be a hash table on the source and destination Ethernet
+ * addresses.  If new classification rules came along with a different form,
+ * you could add a second hash table that hashed on the fields matched in those
+ * rules.  With two hash tables, you look up a given flow in each hash table.
+ * If there are no matches, the classifier didn't contain a match; if you find
+ * a match in one of them, that's the result; if you find a match in both of
+ * them, then the result is the rule with the higher priority.
+ *
+ * This is how the classifier works.  In a "struct classifier", each form of
+ * "struct cls_rule" present (based on its ->match.mask) goes into a separate
+ * "struct cls_table".  A lookup does a hash lookup in every "struct cls_table"
+ * in the classifier and tracks the highest-priority match that it finds.  The
+ * tables are kept in a descending priority order according to the highest
+ * priority rule in each table, which allows lookup to skip over tables that
+ * can't possibly have a higher-priority match than already found.
+ *
+ * One detail: a classifier can contain multiple rules that are identical other
+ * than their priority.  When this happens, only the highest priority rule out
+ * of a group of otherwise identical rules is stored directly in the "struct
+ * cls_table", with the other almost-identical rules chained off a linked list
+ * inside that highest-priority rule.
+ *
+ *
+ * Partitioning
+ * ============
+ *
+ * Suppose that a given classifier is being used to handle multiple stages in a
+ * pipeline using "resubmit", with metadata (that is, the OpenFlow 1.1+ field
+ * named "metadata") distinguishing between the different stages.  For example,
+ * metadata value 1 might identify ingress rules, metadata value 2 might
+ * identify ACLs, and metadata value 3 might identify egress rules.  Such a
+ * classifier is essentially partitioned into multiple sub-classifiers on the
+ * basis of the metadata value.
+ *
+ * The classifier has a special optimization to speed up matching in this
+ * scenario:
+ *
+ *     - Each cls_table that matches on metadata gets a tag derived from the
+ *       table's mask, so that it is likely that each table has a unique tag.
+ *       (Duplicate tags have a performance cost but do not affect
+ *       correctness.)
+ *
+ *     - For each metadata value matched by any cls_rule, the classifier
+ *       constructs a "struct cls_partition" indexed by the metadata value.
+ *       The cls_partition has a 'tags' member whose value is the bitwise-OR of
+ *       the tags of each cls_table that contains any rule that matches on the
+ *       cls_partition's metadata value.  In other words, struct cls_partition
+ *       associates metadata values with tables that need to be checked with
+ *       flows with that specific metadata value.
+ *
+ * Thus, a flow lookup can start by looking up the partition associated with
+ * the flow's metadata, and then skip over any cls_table whose 'tag' does not
+ * intersect the partition's 'tags'.  (The flow must also be looked up in any
+ * cls_table that doesn't match on metadata.  We handle that by giving any such
+ * cls_table TAG_ALL as its 'tags' so that it matches any tag.)
+ *
  *
  * Thread-safety
  * =============
@@ -37,6 +106,7 @@
 #include "hmap.h"
 #include "list.h"
 #include "match.h"
+#include "tag.h"
 #include "openflow/nicira-ext.h"
 #include "openflow/openflow.h"
 #include "ovs-thread.h"
@@ -54,6 +124,7 @@ struct classifier {
     int n_rules;                /* Total number of rules. */
     struct hmap tables;         /* Contains "struct cls_table"s.  */
     struct list tables_priority; /* Tables in descending priority order */
+    struct hmap partitions;     /* Contains "struct cls_partition"s. */
     struct ovs_rwlock rwlock OVS_ACQ_AFTER(ofproto_mutex);
 };
 
@@ -66,6 +137,7 @@ struct cls_table {
     int n_table_rules;          /* Number of rules, including duplicates. */
     unsigned int max_priority;  /* Max priority of any rule in the table. */
     unsigned int max_count;     /* Count of max_priority rules. */
+    tag_type tag;               /* Tag generated from mask for partitioning. */
 };
 
 /* Returns true if 'table' is a "catch-all" table that will match every
@@ -82,6 +154,17 @@ struct cls_rule {
     struct list list;           /* List of identical, lower-priority rules. */
     struct minimatch match;     /* Matching rule. */
     unsigned int priority;      /* Larger numbers are higher priorities. */
+    struct cls_partition *partition;
+};
+
+/* Associates a metadata value (that is, a value of the OpenFlow 1.1+ metadata
+ * field) with tags for the "cls_table"s that contain rules that match that
+ * metadata value.  */
+struct cls_partition {
+    struct hmap_node hmap_node; /* In struct classifier's 'partitions' hmap. */
+    ovs_be64 metadata;          /* metadata value for this partition. */
+    tag_type tags;              /* OR of each included flow's cls_table tag. */
+    unsigned int n_refs;        /* # of flows that refer to this partition. */
 };
 
 void cls_rule_init(struct cls_rule *, const struct match *,