classifier: Support miniflow as a key.

Support struct miniflow as a key for datapath flow lookup.

The new classifier interface classifier_lookup_miniflow_first() takes
a miniflow as a key and stops at the first match with no regard to
flow prioritites.  This works only if the classifier has no
conflicting rules (as is the case with the userspace datapath
classifier).

Signed-off-by: Jarno Rajahalme <jrajahalme@nicira.com>
Reviewed-by: YAMAMOTO Takashi <yamamoto@valinux.co.jp>

diff --git a/lib/classifier.c b/lib/classifier.c
index 55ca5ea..31a0e8b 100644 (file)
--- a/lib/classifier.c
+++ b/lib/classifier.c
@@ -566,6 +566,68 @@ classifier_lookup(const struct classifier *cls, const struct flow *flow,
     return best;
 }
 
+/* Returns true if 'target' satisifies 'match', that is, if each bit for which
+ * 'match' specifies a particular value has the correct value in 'target'. */
+static bool
+minimatch_matches_miniflow(const struct minimatch *match,
+                           const struct miniflow *target)
+{
+    const uint32_t *flowp = (const uint32_t *)match->flow.values;
+    const uint32_t *maskp = (const uint32_t *)match->mask.masks.values;
+    uint32_t target_u32;
+
+    MINIFLOW_FOR_EACH_IN_MAP(target_u32, target, match->mask.masks.map) {
+        if ((*flowp++ ^ target_u32) & *maskp++) {
+            return false;
+        }
+    }
+
+    return true;
+}
+
+static inline struct cls_rule *
+find_match_miniflow(const struct cls_subtable *subtable,
+                    const struct miniflow *flow,
+                    uint32_t hash)
+{
+    struct cls_rule *rule;
+
+    HMAP_FOR_EACH_WITH_HASH (rule, hmap_node, hash, &subtable->rules) {
+        if (minimatch_matches_miniflow(&rule->match, flow)) {
+            return rule;
+        }
+    }
+
+    return NULL;
+}
+
+/* Finds and returns the highest-priority rule in 'cls' that matches
+ * 'miniflow'.  Returns a null pointer if no rules in 'cls' match 'flow'.
+ * If multiple rules of equal priority match 'flow', returns one arbitrarily.
+ *
+ * This function is optimized for the userspace datapath, which only ever has
+ * one priority value for it's flows!
+ */
+struct cls_rule *classifier_lookup_miniflow_first(const struct classifier *cls,
+                                                  const struct miniflow *flow)
+{
+    struct cls_subtable *subtable;
+
+    LIST_FOR_EACH (subtable, list_node, &cls->subtables_priority) {
+        struct cls_rule *rule;
+
+        rule = find_match_miniflow(subtable, flow,
+                                   miniflow_hash_in_minimask(flow,
+                                                             &subtable->mask,
+                                                             0));
+        if (rule) {
+            return rule;
+        }
+    }
+
+    return NULL;
+}
+
 /* Finds and returns a rule in 'cls' with exactly the same priority and
  * matching criteria as 'target'.  Returns a null pointer if 'cls' doesn't
  * contain an exact match. */

diff --git a/lib/classifier.h b/lib/classifier.h
index c3c1c3b..9022fab 100644 (file)
--- a/lib/classifier.h
+++ b/lib/classifier.h
@@ -346,6 +346,9 @@ struct cls_rule *classifier_lookup(const struct classifier *cls,
                                    const struct flow *,
                                    struct flow_wildcards *)
     OVS_REQ_RDLOCK(cls->rwlock);
+struct cls_rule *classifier_lookup_miniflow_first(const struct classifier *cls,
+                                                  const struct miniflow *)
+    OVS_REQ_RDLOCK(cls->rwlock);
 bool classifier_rule_overlaps(const struct classifier *cls,
                               const struct cls_rule *)
     OVS_REQ_RDLOCK(cls->rwlock);

diff --git a/lib/flow.c b/lib/flow.c
index 03d86ae..8319dde 100644 (file)
--- a/lib/flow.c
+++ b/lib/flow.c
@@ -1813,28 +1813,10 @@ miniflow_hash_in_minimask(const struct miniflow *flow,
                           const struct minimask *mask, uint32_t basis)
 {
     const uint32_t *p = mask->masks.values;
-    uint32_t hash;
-    uint64_t map;
-    const uint32_t *fp = flow->values;
-    uint64_t fmap = flow->map;
-    uint64_t rm1bit;
-
-    hash = basis;
-
-    for (map = mask->masks.map; map; map -= rm1bit) {
-        uint32_t flow_u32 = 0;
-
-        rm1bit = rightmost_1bit(map);
-        if (fmap & rm1bit) {
-            uint64_t trash = fmap & (rm1bit - 1);
+    uint32_t hash = basis;
+    uint32_t flow_u32;
 
-            /* Skip data in 'flow' that is of no interest, once. */
-            if (trash) {
-                fp += count_1bits(trash);
-                fmap -= trash;
-            }
-            flow_u32 = *fp;
-        }
+    MINIFLOW_FOR_EACH_IN_MAP(flow_u32, flow, mask->masks.map) {
         hash = mhash_add(hash, flow_u32 & *p++);
     }
 

diff --git a/lib/flow.h b/lib/flow.h
index c834cb5..e8066aa 100644 (file)
--- a/lib/flow.h
+++ b/lib/flow.h
@@ -402,6 +402,32 @@ void miniflow_destroy(struct miniflow *);
 
 void miniflow_expand(const struct miniflow *, struct flow *);
 
+static inline uint32_t
+mf_get_next_in_map(uint64_t *fmap, uint64_t rm1bit, const uint32_t **fp,
+                   uint32_t *value)
+{
+    *value = 0;
+    if (*fmap & rm1bit) {
+        uint64_t trash = *fmap & (rm1bit - 1);
+
+        if (trash) {
+            *fmap -= trash;
+            *fp += count_1bits(trash);
+        }
+        *value = **fp;
+    }
+    return rm1bit != 0;
+}
+
+/* Iterate through all miniflow u32 values specified by the 'MAP'.
+ * This works as the first statement in a block.*/
+#define MINIFLOW_FOR_EACH_IN_MAP(VALUE, FLOW, MAP)                      \
+    const uint32_t *fp_ = (FLOW)->values;                               \
+    uint64_t rm1bit_, fmap_, map_;                                      \
+    for (fmap_ = (FLOW)->map, map_ = (MAP), rm1bit_ = rightmost_1bit(map_); \
+         mf_get_next_in_map(&fmap_, rm1bit_, &fp_, &(VALUE));           \
+         map_ -= rm1bit_, rm1bit_ = rightmost_1bit(map_))
+
 /* These accessors use byte offsets, which are assumed to be compile-time
  * constants. */
 static inline uint8_t miniflow_get_u8(const struct miniflow *,