[ovs-dev] [partition v2 2/3] match: New function minimatch_matches_flow().

Ben Pfaff blp at nicira.com
Thu Jun 27 22:30:13 UTC 2013


Signed-off-by: Ben Pfaff <blp at nicira.com>
---
 lib/classifier.c |    3 +-
 lib/flow.c       |  126 ++++++++++++++++++++++++++++++++++++++++++------------
 lib/flow.h       |   10 +++--
 lib/match.c      |   31 +++++++++++++-
 lib/match.h      |   18 +++++---
 5 files changed, 147 insertions(+), 41 deletions(-)

diff --git a/lib/classifier.c b/lib/classifier.c
index a717bd3..bd202f6 100644
--- a/lib/classifier.c
+++ b/lib/classifier.c
@@ -654,8 +654,7 @@ find_match(const struct cls_table *table, const struct flow *flow)
     struct cls_rule *rule;
 
     HMAP_FOR_EACH_WITH_HASH (rule, hmap_node, hash, &table->rules) {
-        if (miniflow_equal_flow_in_minimask(&rule->match.flow, flow,
-                                            &table->mask)) {
+        if (minimatch_matches_flow(&rule->match, flow)) {
             return rule;
         }
     }
diff --git a/lib/flow.c b/lib/flow.c
index a42fea1..2abebf7 100644
--- a/lib/flow.c
+++ b/lib/flow.c
@@ -1057,13 +1057,38 @@ miniflow_alloc_values(struct miniflow *flow, int n)
     }
 }
 
+/* Completes an initialization of 'dst' as a miniflow copy of 'src' begun by
+ * the caller.  The caller must have already initialized 'dst->map' properly
+ * to indicate the nonzero uint32_t elements of 'src'.  'n' must be the number
+ * of 1-bits in 'dst->map'.
+ *
+ * This function initializes 'dst->values' (either inline if possible or with
+ * malloc() otherwise) and copies the nonzero uint32_t elements of 'src' into
+ * it. */
+static void
+miniflow_init__(struct miniflow *dst, const struct flow *src, int n)
+{
+    const uint32_t *src_u32 = (const uint32_t *) src;
+    unsigned int ofs;
+    int i;
+
+    dst->values = miniflow_alloc_values(dst, n);
+    ofs = 0;
+    for (i = 0; i < MINI_N_MAPS; i++) {
+        uint32_t map;
+
+        for (map = dst->map[i]; map; map = zero_rightmost_1bit(map)) {
+            dst->values[ofs++] = src_u32[raw_ctz(map) + i * 32];
+        }
+    }
+}
+
 /* Initializes 'dst' as a copy of 'src'.  The caller must eventually free 'dst'
  * with miniflow_destroy(). */
 void
 miniflow_init(struct miniflow *dst, const struct flow *src)
 {
     const uint32_t *src_u32 = (const uint32_t *) src;
-    unsigned int ofs;
     unsigned int i;
     int n;
 
@@ -1077,16 +1102,17 @@ miniflow_init(struct miniflow *dst, const struct flow *src)
         }
     }
 
-    /* Initialize dst->values. */
-    dst->values = miniflow_alloc_values(dst, n);
-    ofs = 0;
-    for (i = 0; i < MINI_N_MAPS; i++) {
-        uint32_t map;
+    miniflow_init__(dst, src, n);
+}
 
-        for (map = dst->map[i]; map; map = zero_rightmost_1bit(map)) {
-            dst->values[ofs++] = src_u32[raw_ctz(map) + i * 32];
-        }
-    }
+/* Initializes 'dst' as a copy of 'src', using 'mask->map' as 'dst''s map.  The
+ * caller must eventually free 'dst' with miniflow_destroy(). */
+void
+miniflow_init_with_minimask(struct miniflow *dst, const struct flow *src,
+                            const struct minimask *mask)
+{
+    memcpy(dst->map, mask->masks.map, sizeof dst->map);
+    miniflow_init__(dst, src, miniflow_n_values(dst));
 }
 
 /* Initializes 'dst' as a copy of 'src'.  The caller must eventually free 'dst'
@@ -1169,16 +1195,35 @@ miniflow_get_vid(const struct miniflow *flow)
 bool
 miniflow_equal(const struct miniflow *a, const struct miniflow *b)
 {
+    const uint32_t *ap = a->values;
+    const uint32_t *bp = b->values;
     int i;
 
     for (i = 0; i < MINI_N_MAPS; i++) {
-        if (a->map[i] != b->map[i]) {
-            return false;
+        const uint32_t a_map = a->map[i];
+        const uint32_t b_map = b->map[i];
+        uint32_t map;
+
+        if (a_map == b_map) {
+            for (map = a_map; map; map = zero_rightmost_1bit(map)) {
+                if (*ap++ != *bp++) {
+                    return false;
+                }
+            }
+        } else {
+            for (map = a_map | b_map; map; map = zero_rightmost_1bit(map)) {
+                uint32_t bit = rightmost_1bit(map);
+                uint32_t a_value = a_map & bit ? *ap++ : 0;
+                uint32_t b_value = b_map & bit ? *bp++ : 0;
+
+                if (a_value != b_value) {
+                    return false;
+                }
+            }
         }
     }
 
-    return !memcmp(a->values, b->values,
-                   miniflow_n_values(a) * sizeof *a->values);
+    return true;
 }
 
 /* Returns true if 'a' and 'b' are equal at the places where there are 1-bits
@@ -1238,10 +1283,24 @@ miniflow_equal_flow_in_minimask(const struct miniflow *a, const struct flow *b,
 uint32_t
 miniflow_hash(const struct miniflow *flow, uint32_t basis)
 {
-    BUILD_ASSERT_DECL(MINI_N_MAPS == 2);
-    return hash_3words(flow->map[0], flow->map[1],
-                       hash_words(flow->values, miniflow_n_values(flow),
-                                  basis));
+    const uint32_t *p = flow->values;
+    uint32_t hash = basis;
+    int i;
+
+    for (i = 0; i < MINI_N_MAPS; i++) {
+        uint32_t hash_map = 0;
+        uint32_t map;
+
+        for (map = flow->map[i]; 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);
+    }
+    return mhash_finish(hash, p - flow->values);
 }
 
 /* Returns a hash value for the bits of 'flow' where there are 1-bits in
@@ -1262,9 +1321,10 @@ miniflow_hash_in_minimask(const struct miniflow *flow,
         uint32_t map;
 
         for (map = mask->masks.map[i]; map; map = zero_rightmost_1bit(map)) {
-            int ofs = raw_ctz(map) + i * 32;
-
-            hash = mhash_add(hash, miniflow_get(flow, ofs) & *p);
+            if (*p) {
+                int ofs = raw_ctz(map) + i * 32;
+                hash = mhash_add(hash, miniflow_get(flow, ofs) & *p);
+            }
             p++;
         }
     }
@@ -1281,21 +1341,23 @@ 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 *flow_u32;
     const uint32_t *p = mask->masks.values;
     uint32_t hash;
     int i;
 
     hash = basis;
+    flow_u32 = (const uint32_t *) flow;
     for (i = 0; i < MINI_N_MAPS; i++) {
         uint32_t map;
 
         for (map = mask->masks.map[i]; map; map = zero_rightmost_1bit(map)) {
-            int ofs = raw_ctz(map) + i * 32;
-
-            hash = mhash_add(hash, flow_u32[ofs] & *p);
+            if (*p) {
+                hash = mhash_add(hash, flow_u32[raw_ctz(map)] & *p);
+            }
             p++;
         }
+        flow_u32 += 32;
     }
 
     return mhash_finish(hash, (p - mask->masks.values) * 4);
@@ -1428,7 +1490,17 @@ bool
 minimask_is_catchall(const struct minimask *mask_)
 {
     const struct miniflow *mask = &mask_->masks;
+    const uint32_t *p = mask->values;
+    int i;
 
-    BUILD_ASSERT(MINI_N_MAPS == 2);
-    return !(mask->map[0] | mask->map[1]);
+    for (i = 0; i < MINI_N_MAPS; i++) {
+        uint32_t map;
+
+        for (map = mask->map[i]; map; map = zero_rightmost_1bit(map)) {
+            if (*p++) {
+                return false;
+            }
+        }
+    }
+    return true;
 }
diff --git a/lib/flow.h b/lib/flow.h
index 9a6e937..2c027ed 100644
--- a/lib/flow.h
+++ b/lib/flow.h
@@ -289,7 +289,7 @@ bool flow_equal_except(const struct flow *a, const struct flow *b,
  *
  * The 'map' member holds one bit for each uint32_t in a "struct flow".  Each
  * 0-bit indicates that the corresponding uint32_t is zero, each 1-bit that it
- * is nonzero.
+ * *may* be nonzero.
  *
  * 'values' points to the start of an array that has one element for each 1-bit
  * in 'map'.  The least-numbered 1-bit is in values[0], the next 1-bit is in
@@ -307,9 +307,9 @@ bool flow_equal_except(const struct flow *a, const struct flow *b,
  *       that makes sense.  So far that's only proved useful for
  *       minimask_combine(), but the principle works elsewhere.
  *
- * The implementation maintains and depends on the invariant that every element
- * in 'values' is nonzero; that is, wherever a 1-bit appears in 'map', the
- * corresponding element of 'values' must be nonzero.
+ * Elements in 'values' are allowed to be zero.  This is useful for "struct
+ * minimatch", for which ensuring that the miniflow and minimask members have
+ * same 'map' allows optimization .
  */
 struct miniflow {
     uint32_t *values;
@@ -318,6 +318,8 @@ struct miniflow {
 };
 
 void miniflow_init(struct miniflow *, const struct flow *);
+void miniflow_init_with_minimask(struct miniflow *, const struct flow *,
+                                 const struct minimask *);
 void miniflow_clone(struct miniflow *, const struct miniflow *);
 void miniflow_destroy(struct miniflow *);
 
diff --git a/lib/match.c b/lib/match.c
index bf82d6c..d1d9398 100644
--- a/lib/match.c
+++ b/lib/match.c
@@ -1073,8 +1073,8 @@ match_print(const struct match *match)
 void
 minimatch_init(struct minimatch *dst, const struct match *src)
 {
-    miniflow_init(&dst->flow, &src->flow);
     minimask_init(&dst->mask, &src->wc);
+    miniflow_init_with_minimask(&dst->flow, &src->flow, &dst->mask);
 }
 
 /* Initializes 'dst' as a copy of 'src'.  The caller must eventually free 'dst'
@@ -1118,6 +1118,35 @@ minimatch_hash(const struct minimatch *match, uint32_t basis)
     return miniflow_hash(&match->flow, minimask_hash(&match->mask, basis));
 }
 
+/* Returns true if 'target' satisifies 'match', that is, if each bit for which
+ * 'match' specifies a particular value has the correct value in 'target'.
+ *
+ * This function is equivalent to miniflow_equal_flow_in_minimask(&match->flow,
+ * target, &match->mask) but it is faster because of the invariant that
+ * match->flow.map and match->mask.map are the same. */
+bool
+minimatch_matches_flow(const struct minimatch *match,
+                       const struct flow *target)
+{
+    const uint32_t *target_u32 = (const uint32_t *) target;
+    const uint32_t *flowp = match->flow.values;
+    const uint32_t *maskp = match->mask.masks.values;
+    int i;
+
+    for (i = 0; i < MINI_N_MAPS; i++) {
+        uint32_t map;
+
+        for (map = match->flow.map[i]; map; map = zero_rightmost_1bit(map)) {
+            if ((*flowp++ ^ target_u32[raw_ctz(map)]) & *maskp++) {
+                return false;
+            }
+        }
+        target_u32 += 32;
+    }
+
+    return true;
+}
+
 /* Appends a string representation of 'match' to 's'.  If 'priority' is
  * different from OFP_DEFAULT_PRIORITY, includes it in 's'. */
 void
diff --git a/lib/match.h b/lib/match.h
index 0ea1f2d..bbff5fe 100644
--- a/lib/match.h
+++ b/lib/match.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.
@@ -131,13 +131,15 @@ void match_print(const struct match *);
 
 /* A sparse representation of a "struct match".
  *
- * This has the same invariant as "struct match", that is, a 1-bit in the
- * 'flow' must correspond to a 1-bit in 'mask'.
+ * There are two invariants:
  *
- * The invariants for the underlying miniflow and minimask are also maintained,
- * which means that 'flow' and 'mask' can have different 'map's.  In
- * particular, if the match checks that a given 32-bit field has value 0, then
- * 'map' will have a 1-bit in 'mask' but a 0-bit in 'flow' for that field. */
+ *   - The same invariant as "struct match", that is, a 1-bit in the 'flow'
+ *     must correspond to a 1-bit in 'mask'.
+ *
+ *   - 'flow' and 'mask' have the same 'map'.  This implies that 'flow' and
+ *     'mask' have the same part of "struct flow" at the same offset into
+ *     'values', which makes minimatch_matches_flow() faster.
+ */
 struct minimatch {
     struct miniflow flow;
     struct minimask mask;
@@ -152,6 +154,8 @@ void minimatch_expand(const struct minimatch *, struct match *);
 bool minimatch_equal(const struct minimatch *a, const struct minimatch *b);
 uint32_t minimatch_hash(const struct minimatch *, uint32_t basis);
 
+bool minimatch_matches_flow(const struct minimatch *, const struct flow *);
+
 void minimatch_format(const struct minimatch *, struct ds *,
                       unsigned int priority);
 char *minimatch_to_string(const struct minimatch *, unsigned int priority);
-- 
1.7.2.5




More information about the dev mailing list