X-Git-Url: http://git.onelab.eu/?a=blobdiff_plain;f=lib%2Fclassifier.c;h=8ab1f9c3d900e7ce65ce76f01f7cc9bfde82af47;hb=3d91d9094dcf49c210bd4ebae4bd1e0cea9defce;hp=30a91b755e357f7cc5b13a2c26a3ea8d80bd8d98;hpb=06f81620436881449cb9a2db4f875aa00803f28d;p=sliver-openvswitch.git

diff --git a/lib/classifier.c b/lib/classifier.c
index 30a91b755..8ab1f9c3d 100644
--- a/lib/classifier.c
+++ b/lib/classifier.c
@@ -79,6 +79,185 @@ static void mask_set_prefix_bits(struct flow_wildcards *, uint8_t be32ofs,
                                  unsigned int nbits);
 static bool mask_prefix_bits_set(const struct flow_wildcards *,
                                  uint8_t be32ofs, unsigned int nbits);
+
+/* flow/miniflow/minimask/minimatch utilities.
+ * These are only used by the classifier, so place them here to allow
+ * for better optimization. */
+
+static inline uint64_t
+miniflow_get_map_in_range(const struct miniflow *miniflow,
+                          uint8_t start, uint8_t end, unsigned int *offset)
+{
+    uint64_t map = miniflow->map;
+    *offset = 0;
+
+    if (start > 0) {
+        uint64_t msk = (UINT64_C(1) << start) - 1; /* 'start' LSBs set */
+        *offset = count_1bits(map & msk);
+        map &= ~msk;
+    }
+    if (end < FLOW_U32S) {
+        uint64_t msk = (UINT64_C(1) << end) - 1; /* 'end' LSBs set */
+        map &= msk;
+    }
+    return map;
+}
+
+/* Returns a hash value for the bits of 'flow' where there are 1-bits in
+ * 'mask', given 'basis'.
+ *
+ * The hash values returned by this function are the same as those returned by
+ * miniflow_hash_in_minimask(), only the form of the arguments differ. */
+static inline uint32_t
+flow_hash_in_minimask(const struct flow *flow, const struct minimask *mask,
+                      uint32_t basis)
+{
+    const uint32_t *flow_u32 = (const uint32_t *)flow;
+    const uint32_t *p = mask->masks.values;
+    uint32_t hash;
+    uint64_t map;
+
+    hash = basis;
+    for (map = mask->masks.map; map; map = zero_rightmost_1bit(map)) {
+        hash = mhash_add(hash, flow_u32[raw_ctz(map)] & *p++);
+    }
+
+    return mhash_finish(hash, (p - mask->masks.values) * 4);
+}
+
+/* Returns a hash value for the bits of 'flow' where there are 1-bits in
+ * 'mask', given 'basis'.
+ *
+ * The hash values returned by this function are the same as those returned by
+ * flow_hash_in_minimask(), only the form of the arguments differ. */
+static inline uint32_t
+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 = basis;
+    uint32_t flow_u32;
+
+    MINIFLOW_FOR_EACH_IN_MAP(flow_u32, flow, mask->masks.map) {
+        hash = mhash_add(hash, flow_u32 & *p++);
+    }
+
+    return mhash_finish(hash, (p - mask->masks.values) * 4);
+}
+
+/* Returns a hash value for the bits of range [start, end) in 'flow',
+ * where there are 1-bits in 'mask', given 'hash'.
+ *
+ * The hash values returned by this function are the same as those returned by
+ * minimatch_hash_range(), only the form of the arguments differ. */
+static inline uint32_t
+flow_hash_in_minimask_range(const struct flow *flow,
+                            const struct minimask *mask,
+                            uint8_t start, uint8_t end, uint32_t *basis)
+{
+    const uint32_t *flow_u32 = (const uint32_t *)flow;
+    unsigned int offset;
+    uint64_t map = miniflow_get_map_in_range(&mask->masks, start, end,
+                                             &offset);
+    const uint32_t *p = mask->masks.values + offset;
+    uint32_t hash = *basis;
+
+    for (; map; map = zero_rightmost_1bit(map)) {
+        hash = mhash_add(hash, flow_u32[raw_ctz(map)] & *p++);
+    }
+
+    *basis = hash; /* Allow continuation from the unfinished value. */
+    return mhash_finish(hash, (p - mask->masks.values) * 4);
+}
+
+/* Fold minimask 'mask''s wildcard mask into 'wc's wildcard mask. */
+static inline void
+flow_wildcards_fold_minimask(struct flow_wildcards *wc,
+                             const struct minimask *mask)
+{
+    flow_union_with_miniflow(&wc->masks, &mask->masks);
+}
+
+/* Fold minimask 'mask''s wildcard mask into 'wc's wildcard mask
+ * in range [start, end). */
+static inline void
+flow_wildcards_fold_minimask_range(struct flow_wildcards *wc,
+                                   const struct minimask *mask,
+                                   uint8_t start, uint8_t end)
+{
+    uint32_t *dst_u32 = (uint32_t *)&wc->masks;
+    unsigned int offset;
+    uint64_t map = miniflow_get_map_in_range(&mask->masks, start, end,
+                                             &offset);
+    const uint32_t *p = mask->masks.values + offset;
+
+    for (; map; map = zero_rightmost_1bit(map)) {
+        dst_u32[raw_ctz(map)] |= *p++;
+    }
+}
+
+/* Returns a hash value for 'flow', given 'basis'. */
+static inline uint32_t
+miniflow_hash(const struct miniflow *flow, uint32_t basis)
+{
+    const uint32_t *p = flow->values;
+    uint32_t hash = basis;
+    uint64_t hash_map = 0;
+    uint64_t map;
+
+    for (map = flow->map; map; map = zero_rightmost_1bit(map)) {
+        if (*p) {
+            hash = mhash_add(hash, *p);
+            hash_map |= rightmost_1bit(map);
+        }
+        p++;
+    }
+    hash = mhash_add(hash, hash_map);
+    hash = mhash_add(hash, hash_map >> 32);
+
+    return mhash_finish(hash, p - flow->values);
+}
+
+/* Returns a hash value for 'mask', given 'basis'. */
+static inline uint32_t
+minimask_hash(const struct minimask *mask, uint32_t basis)
+{
+    return miniflow_hash(&mask->masks, basis);
+}
+
+/* Returns a hash value for 'match', given 'basis'. */
+static inline uint32_t
+minimatch_hash(const struct minimatch *match, uint32_t basis)
+{
+    return miniflow_hash(&match->flow, minimask_hash(&match->mask, basis));
+}
+
+/* Returns a hash value for the bits of range [start, end) in 'minimatch',
+ * given 'basis'.
+ *
+ * The hash values returned by this function are the same as those returned by
+ * flow_hash_in_minimask_range(), only the form of the arguments differ. */
+static inline uint32_t
+minimatch_hash_range(const struct minimatch *match, uint8_t start, uint8_t end,
+                     uint32_t *basis)
+{
+    unsigned int offset;
+    const uint32_t *p, *q;
+    uint32_t hash = *basis;
+    int n, i;
+
+    n = count_1bits(miniflow_get_map_in_range(&match->mask.masks, start, end,
+                                              &offset));
+    q = match->mask.masks.values + offset;
+    p = match->flow.values + offset;
+
+    for (i = 0; i < n; i++) {
+        hash = mhash_add(hash, p[i] & q[i]);
+    }
+    *basis = hash; /* Allow continuation from the unfinished value. */
+    return mhash_finish(hash, (offset + n) * 4);
+}
+
 
 /* cls_rule. */
 
@@ -312,7 +491,7 @@ static uint32_t
 hash_metadata(ovs_be64 metadata_)
 {
     uint64_t metadata = (OVS_FORCE uint64_t) metadata_;
-    return hash_2words(metadata, metadata >> 32);
+    return hash_uint64(metadata);
 }
 
 static struct cls_partition *
@@ -566,6 +745,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. */
@@ -1503,7 +1744,7 @@ minimask_get_prefix_len(const struct minimask *minimask,
 static const ovs_be32 *
 minimatch_get_prefix(const struct minimatch *match, const struct mf_field *mf)
 {
-    return (OVS_FORCE const ovs_be32 *)match->flow.values +
+    return match->flow.values +
         count_1bits(match->flow.map & ((UINT64_C(1) << mf->flow_be32ofs) - 1));
 }