[ovs-dev] [classifier-opt 28/28] Introduce sparse flows and masks, to reduce memory usage and improve speed.
Ben Pfaff
blp at nicira.com
Fri Jul 20 23:25:25 UTC 2012
A cls_rule is 324 bytes on i386 now. The cost of a flow table lookup is
currently proportional to this size, which is going to continue to grow.
However, the required cost of a flow table lookup, with the classifier that
we currently use, is only proportional to the number of bits that a rule
actually matches. This commit implements that optimization by replacing
the match inside "struct cls_rule" by a sparse representation.
This reduces struct cls_rule to 100 bytes on i386.
There is still some headroom for further optimization following this
commit:
- I suspect that adding an 'n' member to struct miniflow would make
miniflow operations faster, since popcount() has some cost.
- It's probably possible to replace the "struct minimatch" in cls_rule
by just a "struct miniflow", since the cls_rule's cls_table has a
copy of the minimask.
- Some of the miniflow operations aren't well-optimized.
This passes the existing unit tests but it probably needs additional
testing since the existing unit tests were designed for the previous code.
Signed-off-by: Ben Pfaff <blp at nicira.com>
---
lib/classifier.c | 126 +++++++------
lib/classifier.h | 17 +-
lib/flow.c | 442 +++++++++++++++++++++++++++++++++++++++++++++++
lib/flow.h | 94 ++++++++++
lib/match.c | 76 ++++++++
lib/match.h | 31 ++++
ofproto/connmgr.c | 6 +-
ofproto/connmgr.h | 2 +-
ofproto/ofproto-dpif.c | 32 ++--
ofproto/ofproto.c | 32 ++--
tests/test-classifier.c | 72 ++++----
utilities/ovs-ofctl.c | 9 +-
12 files changed, 804 insertions(+), 135 deletions(-)
diff --git a/lib/classifier.c b/lib/classifier.c
index 50c36dc..f561e97 100644
--- a/lib/classifier.c
+++ b/lib/classifier.c
@@ -28,16 +28,16 @@
#include "packets.h"
static struct cls_table *find_table(const struct classifier *,
- const struct flow_wildcards *);
+ const struct minimask *);
static struct cls_table *insert_table(struct classifier *,
- const struct flow_wildcards *);
+ const struct minimask *);
static void destroy_table(struct classifier *, struct cls_table *);
static struct cls_rule *find_match(const struct cls_table *,
const struct flow *);
-static struct cls_rule *find_equal(struct cls_table *, const struct flow *,
- uint32_t hash);
+static struct cls_rule *find_equal(struct cls_table *,
+ const struct miniflow *, uint32_t hash);
static struct cls_rule *insert_rule(struct cls_table *, struct cls_rule *);
/* Iterates RULE over HEAD and all of the cls_rules on HEAD->list. */
@@ -54,10 +54,10 @@ static struct cls_rule *next_rule_in_list(struct cls_rule *);
/* cls_rule. */
/* Initializes 'rule' to match packets specified by 'match' at the given
- * 'priority'.
+ * 'priority'. 'match' must satisfy the invariant described in the comment at
+ * the definition of struct match.
*
- * 'match' must satisfy the invariant described in the comment at the
- * definition of struct match.
+ * The caller must eventually destroy 'rule' with cls_rule_destroy().
*
* (OpenFlow uses priorities between 0 and UINT16_MAX, inclusive, but
* internally Open vSwitch supports a wider range.) */
@@ -65,15 +65,28 @@ void
cls_rule_init(struct cls_rule *rule,
const struct match *match, unsigned int priority)
{
- rule->match = *match;
+ minimatch_init(&rule->match, match);
rule->priority = priority;
}
-/* Initializes 'dst' as a copy of 'src'. */
+/* Same as cls_rule_init() for initialization from a "struct minimatch". */
+void
+cls_rule_init_from_minimatch(struct cls_rule *rule,
+ const struct minimatch *match,
+ unsigned int priority)
+{
+ minimatch_clone(&rule->match, match);
+ rule->priority = priority;
+}
+
+/* Initializes 'dst' as a copy of 'src'.
+ *
+ * The caller must eventually destroy 'rule' with cls_rule_destroy(). */
void
cls_rule_clone(struct cls_rule *dst, const struct cls_rule *src)
{
- *dst = *src;
+ minimatch_clone(&dst->match, &src->match);
+ dst->priority = src->priority;
}
/* Frees memory referenced by 'rule'. Doesn't free 'rule' itself (it's
@@ -81,9 +94,9 @@ cls_rule_clone(struct cls_rule *dst, const struct cls_rule *src)
*
* ('rule' must not currently be in a classifier.) */
void
-cls_rule_destroy(struct cls_rule *rule OVS_UNUSED)
+cls_rule_destroy(struct cls_rule *rule)
{
- /* Nothing to do yet. */
+ minimatch_destroy(&rule->match);
}
/* Returns true if 'a' and 'b' match the same packets at the same priority,
@@ -91,28 +104,28 @@ cls_rule_destroy(struct cls_rule *rule OVS_UNUSED)
bool
cls_rule_equal(const struct cls_rule *a, const struct cls_rule *b)
{
- return a->priority == b->priority && match_equal(&a->match, &b->match);
+ return a->priority == b->priority && minimatch_equal(&a->match, &b->match);
}
/* Returns a hash value for 'rule', folding in 'basis'. */
uint32_t
cls_rule_hash(const struct cls_rule *rule, uint32_t basis)
{
- return match_hash(&rule->match, hash_int(rule->priority, basis));
+ return minimatch_hash(&rule->match, hash_int(rule->priority, basis));
}
/* Appends a string describing 'rule' to 's'. */
void
cls_rule_format(const struct cls_rule *rule, struct ds *s)
{
- match_format(&rule->match, s, rule->priority);
+ minimatch_format(&rule->match, s, rule->priority);
}
/* Returns true if 'rule' matches every packet, false otherwise. */
bool
cls_rule_is_catchall(const struct cls_rule *rule)
{
- return flow_wildcards_is_catchall(&rule->match.wc);
+ return minimask_is_catchall(&rule->match.mask);
}
/* Initializes 'cls' as a classifier that initially contains no classification
@@ -161,7 +174,8 @@ classifier_count(const struct classifier *cls)
* If 'cls' already contains an identical rule (including wildcards, values of
* fixed fields, and priority), replaces the old rule by 'rule' and returns the
* rule that was replaced. The caller takes ownership of the returned rule and
- * is thus responsible for freeing it, etc., as necessary.
+ * is thus responsible for destroying it with cls_rule_destroy(), freeing the
+ * memory block in which it resides, etc., as necessary.
*
* Returns NULL if 'cls' does not contain a rule with an identical key, after
* inserting the new rule. In this case, no rules are displaced by the new
@@ -173,9 +187,9 @@ classifier_replace(struct classifier *cls, struct cls_rule *rule)
struct cls_rule *old_rule;
struct cls_table *table;
- table = find_table(cls, &rule->match.wc);
+ table = find_table(cls, &rule->match.mask);
if (!table) {
- table = insert_table(cls, &rule->match.wc);
+ table = insert_table(cls, &rule->match.mask);
}
old_rule = insert_rule(table, rule);
@@ -199,15 +213,16 @@ classifier_insert(struct classifier *cls, struct cls_rule *rule)
assert(!displaced_rule);
}
-/* Removes 'rule' from 'cls'. It is the caller's responsibility to free
- * 'rule', if this is desirable. */
+/* Removes 'rule' from 'cls'. It is the caller's responsibility to destroy
+ * 'rule' with cls_rule_destroy(), freeing the memory block in which 'rule'
+ * resides, etc., as necessary. */
void
classifier_remove(struct classifier *cls, struct cls_rule *rule)
{
struct cls_rule *head;
struct cls_table *table;
- table = find_table(cls, &rule->match.wc);
+ table = find_table(cls, &rule->match.mask);
head = find_equal(table, &rule->match.flow, rule->hmap_node.hash);
if (head != rule) {
list_remove(&rule->list);
@@ -257,13 +272,14 @@ classifier_find_rule_exactly(const struct classifier *cls,
struct cls_rule *head, *rule;
struct cls_table *table;
- table = find_table(cls, &target->match.wc);
+ table = find_table(cls, &target->match.mask);
if (!table) {
return NULL;
}
head = find_equal(table, &target->match.flow,
- flow_hash(&target->match.flow, 0));
+ miniflow_hash_in_minimask(&target->match.flow,
+ &target->match.mask, 0));
FOR_EACH_RULE_IN_LIST (rule, head) {
if (target->priority >= rule->priority) {
return target->priority == rule->priority ? rule : NULL;
@@ -282,17 +298,18 @@ classifier_rule_overlaps(const struct classifier *cls,
struct cls_table *table;
HMAP_FOR_EACH (table, hmap_node, &cls->tables) {
- struct flow_wildcards wc;
+ uint32_t storage[FLOW_U32S];
+ struct minimask mask;
struct cls_rule *head;
- flow_wildcards_combine(&wc, &target->match.wc, &table->wc);
+ minimask_combine(&mask, &target->match.mask, &table->mask, storage);
HMAP_FOR_EACH (head, hmap_node, &table->rules) {
struct cls_rule *rule;
FOR_EACH_RULE_IN_LIST (rule, head) {
if (rule->priority == target->priority
- && flow_equal_except(&target->match.flow,
- &rule->match.flow, &wc)) {
+ && miniflow_equal_in_minimask(&target->match.flow,
+ &rule->match.flow, &mask)) {
return true;
}
}
@@ -337,11 +354,11 @@ classifier_rule_overlaps(const struct classifier *cls,
* Ignores rule->priority. */
bool
cls_rule_is_loose_match(const struct cls_rule *rule,
- const struct match *criteria)
+ const struct minimatch *criteria)
{
- return (!flow_wildcards_has_extra(&rule->match.wc, &criteria->wc)
- && flow_equal_except(&rule->match.flow, &criteria->flow,
- &criteria->wc));
+ return (!minimask_has_extra(&rule->match.mask, &criteria->mask)
+ && miniflow_equal_in_minimask(&rule->match.flow, &criteria->flow,
+ &criteria->mask));
}
/* Iteration. */
@@ -350,14 +367,15 @@ static bool
rule_matches(const struct cls_rule *rule, const struct cls_rule *target)
{
return (!target
- || flow_equal_except(&rule->match.flow, &target->match.flow,
- &target->match.wc));
+ || miniflow_equal_in_minimask(&rule->match.flow,
+ &target->match.flow,
+ &target->match.mask));
}
static struct cls_rule *
search_table(const struct cls_table *table, const struct cls_rule *target)
{
- if (!target || !flow_wildcards_has_extra(&table->wc, &target->match.wc)) {
+ if (!target || !minimask_has_extra(&table->mask, &target->match.mask)) {
struct cls_rule *rule;
HMAP_FOR_EACH (rule, hmap_node, &table->rules) {
@@ -439,13 +457,13 @@ cls_cursor_next(struct cls_cursor *cursor, struct cls_rule *rule)
}
static struct cls_table *
-find_table(const struct classifier *cls, const struct flow_wildcards *wc)
+find_table(const struct classifier *cls, const struct minimask *mask)
{
struct cls_table *table;
- HMAP_FOR_EACH_IN_BUCKET (table, hmap_node, flow_wildcards_hash(wc, 0),
+ HMAP_FOR_EACH_IN_BUCKET (table, hmap_node, minimask_hash(mask, 0),
&cls->tables) {
- if (flow_wildcards_equal(wc, &table->wc)) {
+ if (minimask_equal(mask, &table->mask)) {
return table;
}
}
@@ -453,15 +471,14 @@ find_table(const struct classifier *cls, const struct flow_wildcards *wc)
}
static struct cls_table *
-insert_table(struct classifier *cls, const struct flow_wildcards *wc)
+insert_table(struct classifier *cls, const struct minimask *mask)
{
struct cls_table *table;
table = xzalloc(sizeof *table);
hmap_init(&table->rules);
- table->wc = *wc;
- table->is_catchall = flow_wildcards_is_catchall(&table->wc);
- hmap_insert(&cls->tables, &table->hmap_node, flow_wildcards_hash(wc, 0));
+ minimask_clone(&table->mask, mask);
+ hmap_insert(&cls->tables, &table->hmap_node, minimask_hash(mask, 0));
return table;
}
@@ -469,6 +486,7 @@ insert_table(struct classifier *cls, const struct flow_wildcards *wc)
static void
destroy_table(struct classifier *cls, struct cls_table *table)
{
+ minimask_destroy(&table->mask);
hmap_remove(&cls->tables, &table->hmap_node);
hmap_destroy(&table->rules);
free(table);
@@ -477,35 +495,26 @@ destroy_table(struct classifier *cls, struct cls_table *table)
static struct cls_rule *
find_match(const struct cls_table *table, const struct flow *flow)
{
+ uint32_t hash = flow_hash_in_minimask(flow, &table->mask, 0);
struct cls_rule *rule;
- if (table->is_catchall) {
- HMAP_FOR_EACH (rule, hmap_node, &table->rules) {
+ HMAP_FOR_EACH_WITH_HASH (rule, hmap_node, hash, &table->rules) {
+ if (miniflow_equal_flow_in_minimask(&rule->match.flow, flow,
+ &table->mask)) {
return rule;
}
- } else {
- struct flow f;
-
- f = *flow;
- flow_zero_wildcards(&f, &table->wc);
- HMAP_FOR_EACH_WITH_HASH (rule, hmap_node, flow_hash(&f, 0),
- &table->rules) {
- if (flow_equal(&f, &rule->match.flow)) {
- return rule;
- }
- }
}
return NULL;
}
static struct cls_rule *
-find_equal(struct cls_table *table, const struct flow *flow, uint32_t hash)
+find_equal(struct cls_table *table, const struct miniflow *flow, uint32_t hash)
{
struct cls_rule *head;
HMAP_FOR_EACH_WITH_HASH (head, hmap_node, hash, &table->rules) {
- if (flow_equal(&head->match.flow, flow)) {
+ if (miniflow_equal(&head->match.flow, flow)) {
return head;
}
}
@@ -517,7 +526,8 @@ insert_rule(struct cls_table *table, struct cls_rule *new)
{
struct cls_rule *head;
- new->hmap_node.hash = flow_hash(&new->match.flow, 0);
+ new->hmap_node.hash = miniflow_hash_in_minimask(&new->match.flow,
+ &new->match.mask, 0);
head = find_equal(table, &new->match.flow, new->hmap_node.hash);
if (!head) {
diff --git a/lib/classifier.h b/lib/classifier.h
index 34e4bdb..92b6998 100644
--- a/lib/classifier.h
+++ b/lib/classifier.h
@@ -47,9 +47,8 @@ struct classifier {
struct cls_table {
struct hmap_node hmap_node; /* Within struct classifier 'tables' hmap. */
struct hmap rules; /* Contains "struct cls_rule"s. */
- struct flow_wildcards wc; /* Wildcards for fields. */
+ struct minimask mask; /* Wildcards for fields. */
int n_table_rules; /* Number of rules, including duplicates. */
- bool is_catchall; /* True if this table wildcards every field. */
};
/* Returns true if 'table' is a "catch-all" table that will match every
@@ -57,19 +56,21 @@ struct cls_table {
static inline bool
cls_table_is_catchall(const struct cls_table *table)
{
- return table->is_catchall;
+ return minimask_is_catchall(&table->mask);
}
-/* A rule in a "struct classifier" */
+/* A rule in a "struct classifier". */
struct cls_rule {
struct hmap_node hmap_node; /* Within struct cls_table 'rules'. */
struct list list; /* List of identical, lower-priority rules. */
- struct match match; /* Matching rule. */
+ struct minimatch match; /* Matching rule. */
unsigned int priority; /* Larger numbers are higher priorities. */
};
-void cls_rule_init(struct cls_rule *,
- const struct match *, unsigned int priority);
+void cls_rule_init(struct cls_rule *, const struct match *,
+ unsigned int priority);
+void cls_rule_init_from_minimatch(struct cls_rule *, const struct minimatch *,
+ unsigned int priority);
void cls_rule_clone(struct cls_rule *, const struct cls_rule *);
void cls_rule_destroy(struct cls_rule *);
@@ -81,7 +82,7 @@ void cls_rule_format(const struct cls_rule *, struct ds *);
bool cls_rule_is_catchall(const struct cls_rule *);
bool cls_rule_is_loose_match(const struct cls_rule *rule,
- const struct match *criteria);
+ const struct minimatch *criteria);
void classifier_init(struct classifier *);
void classifier_destroy(struct classifier *);
diff --git a/lib/flow.c b/lib/flow.c
index a5076bb..7b50b0b 100644
--- a/lib/flow.c
+++ b/lib/flow.c
@@ -19,9 +19,11 @@
#include <assert.h>
#include <errno.h>
#include <inttypes.h>
+#include <limits.h>
#include <netinet/in.h>
#include <netinet/icmp6.h>
#include <netinet/ip6.h>
+#include <stdint.h>
#include <stdlib.h>
#include <string.h>
#include "byte-order.h"
@@ -874,3 +876,443 @@ flow_compose(struct ofpbuf *b, const struct flow *flow)
}
}
}
+
+/* Compressed flow. */
+
+/* Returns the number of trailing 0-bits in 'n'. Undefined if 'n' == 0.
+ *
+ * This compiles to a single machine instruction ("bsf") with GCC on x86. */
+static int
+raw_ctz(uint32_t n)
+{
+#if !defined(UINT_MAX) || !defined(UINT32_MAX)
+#error "Someone screwed up the #includes."
+#elif __GNUC__ >= 4 && UINT_MAX == UINT32_MAX
+ return __builtin_ctz(n);
+#else
+ unsigned int k;
+ int count = 31;
+
+#define CTZ_STEP(X) \
+ k = n << (X); \
+ if (k) { \
+ count -= X; \
+ n = k; \
+ }
+ CTZ_STEP(16);
+ CTZ_STEP(8);
+ CTZ_STEP(4);
+ CTZ_STEP(2);
+ CTZ_STEP(1);
+#undef CTZ_STEP
+
+ return count;
+#endif
+}
+
+static int
+miniflow_n_values(const struct miniflow *flow)
+{
+ int n, i;
+
+ n = 0;
+ for (i = 0; i < MINI_N_MAPS; i++) {
+ n += popcount(flow->map[i]);
+ }
+ return n;
+}
+
+/* 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;
+
+ /* Initialize dst->map, counting the number of nonzero elements. */
+ n = 0;
+ memset(dst->map, 0, sizeof dst->map);
+ for (i = 0; i < FLOW_U32S; i++) {
+ if (src_u32[i]) {
+ dst->map[i / 32] |= 1u << (i % 32);
+ n++;
+ }
+ }
+
+ /* Allocate storage for nonzero elements. */
+ dst->values = (n <= MINI_N_INLINE
+ ? dst->inline_values
+ : xmalloc(n * sizeof *dst->values));
+
+ /* Initialize dst->values. */
+ 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_clone(struct miniflow *dst, const struct miniflow *src)
+{
+ int n = miniflow_n_values(src);
+ memcpy(dst->map, src->map, sizeof dst->map);
+ dst->values = (n <= MINI_N_INLINE ? dst->inline_values
+ : xmalloc(n * sizeof *dst->values));
+ memcpy(dst->values, src->values, n * sizeof *dst->values);
+}
+
+/* Frees any memory owned by 'flow'. Does not free the storage in which 'flow'
+ * itself resides; the caller is responsible for that. */
+void
+miniflow_destroy(struct miniflow *flow)
+{
+ if (flow->values != flow->inline_values) {
+ free(flow->values);
+ }
+}
+
+/* Initializes 'dst' as a copy of 'src'. */
+void
+miniflow_expand(const struct miniflow *src, struct flow *dst)
+{
+ uint32_t *dst_u32 = (uint32_t *) dst;
+ int ofs;
+ int i;
+
+ memset(dst_u32, 0, sizeof *dst);
+
+ ofs = 0;
+ for (i = 0; i < MINI_N_MAPS; i++) {
+ uint32_t map;
+
+ for (map = src->map[i]; map; map = zero_rightmost_1bit(map)) {
+ dst_u32[raw_ctz(map) + i * 32] = src->values[ofs++];
+ }
+ }
+}
+
+static const uint32_t *
+miniflow_get__(const struct miniflow *flow, unsigned int u32_ofs)
+{
+ if (!(flow->map[u32_ofs / 32] & (1u << (u32_ofs % 32)))) {
+ static const uint32_t zero = 0;
+ return &zero;
+ } else {
+ const uint32_t *p = flow->values;
+ if (u32_ofs < 32) {
+ p += popcount(flow->map[0] & ((1u << u32_ofs) - 1));
+ } else {
+ p += popcount(flow->map[0]);
+ p += popcount(flow->map[1] & ((1u << (u32_ofs - 32)) - 1));
+ }
+ return p;
+ }
+}
+
+/* Returns the uint32_t that would be at byte offset '4*u32_ofs' if 'flow'
+ * were expanded into a "struct flow". */
+uint32_t
+miniflow_get(const struct miniflow *flow, unsigned int u32_ofs)
+{
+ return *miniflow_get__(flow, u32_ofs);
+}
+
+/* Returns the ovs_be16 that would be at byte offset 'u8_ofs' if 'flow' were
+ * expanded into a "struct flow". */
+static ovs_be16
+miniflow_get_be16(const struct miniflow *flow, unsigned int u8_ofs)
+{
+ const uint32_t *u32p = miniflow_get__(flow, u8_ofs / 4);
+ const ovs_be16 *be16p = (const ovs_be16 *) u32p;
+ return be16p[u8_ofs % 4 != 0];
+}
+
+/* Returns the VID within the vlan_tci member of the "struct flow" represented
+ * by 'flow'. */
+uint16_t
+miniflow_get_vid(const struct miniflow *flow)
+{
+ ovs_be16 tci = miniflow_get_be16(flow, offsetof(struct flow, vlan_tci));
+ return vlan_tci_to_vid(tci);
+}
+
+/* Returns true if 'a' and 'b' are the same flow, false otherwise. */
+bool
+miniflow_equal(const struct miniflow *a, const struct miniflow *b)
+{
+ int i;
+
+ for (i = 0; i < MINI_N_MAPS; i++) {
+ if (a->map[i] != b->map[i]) {
+ return false;
+ }
+ }
+
+ return !memcmp(a->values, b->values,
+ miniflow_n_values(a) * sizeof *a->values);
+}
+
+/* Returns true if 'a' and 'b' are equal at the places where there are 1-bits
+ * in 'mask', false if they differ. */
+bool
+miniflow_equal_in_minimask(const struct miniflow *a, const struct miniflow *b,
+ const struct minimask *mask)
+{
+ const uint32_t *p;
+ int i;
+
+ p = mask->masks.values;
+ 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;
+
+ if ((miniflow_get(a, ofs) ^ miniflow_get(b, ofs)) & *p) {
+ return false;
+ }
+ p++;
+ }
+ }
+
+ return true;
+}
+
+/* Returns true if 'a' and 'b' are equal at the places where there are 1-bits
+ * in 'mask', false if they differ. */
+bool
+miniflow_equal_flow_in_minimask(const struct miniflow *a, const struct flow *b,
+ const struct minimask *mask)
+{
+ const uint32_t *b_u32 = (const uint32_t *) b;
+ const uint32_t *p;
+ int i;
+
+ p = mask->masks.values;
+ 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;
+
+ if ((miniflow_get(a, ofs) ^ b_u32[ofs]) & *p) {
+ return false;
+ }
+ p++;
+ }
+ }
+
+ return true;
+}
+
+/* Returns a hash value for 'flow', given 'basis'. */
+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));
+}
+
+/* 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.
+ *
+ * XXX murmurhash would be much better for this than hash_int(). */
+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;
+ int i;
+
+ hash = basis;
+ 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 = hash_int(miniflow_get(flow, ofs) & *p, hash);
+ p++;
+ }
+ }
+
+ return hash;
+}
+
+/* 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.
+ *
+ * XXX murmurhash would be much better for this than hash_int(). */
+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;
+ int i;
+
+ hash = basis;
+ 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 = hash_int(flow_u32[ofs] & *p, hash);
+ p++;
+ }
+ }
+
+ return hash;
+}
+
+/* Initializes 'dst' as a copy of 'src'. The caller must eventually free 'dst'
+ * with minimask_destroy(). */
+void
+minimask_init(struct minimask *mask, const struct flow_wildcards *wc)
+{
+ miniflow_init(&mask->masks, &wc->masks);
+}
+
+/* Initializes 'dst' as a copy of 'src'. The caller must eventually free 'dst'
+ * with minimask_destroy(). */
+void
+minimask_clone(struct minimask *dst, const struct minimask *src)
+{
+ miniflow_clone(&dst->masks, &src->masks);
+}
+
+/* Initializes 'dst' as the bit-wise "and" of 'a' and 'b'.
+ *
+ * The caller must provide room for FLOW_U32S "uint32_t"s in 'storage', for use
+ * by 'dst'. The caller must *not* free 'dst' with minimask_destroy(). */
+void
+minimask_combine(struct minimask *dst_,
+ const struct minimask *a_, const struct minimask *b_,
+ uint32_t storage[FLOW_U32S])
+{
+ struct miniflow *dst = &dst_->masks;
+ const struct miniflow *a = &a_->masks;
+ const struct miniflow *b = &b_->masks;
+ int i, n;
+
+ n = 0;
+ dst->values = storage;
+ for (i = 0; i < MINI_N_MAPS; i++) {
+ uint32_t map = a->map[i] & b->map[i];
+
+ dst->map[i] = 0;
+ for (map = dst->map[i]; map; map = zero_rightmost_1bit(map)) {
+ int ofs = raw_ctz(map) + i * 32;
+ uint32_t mask = miniflow_get(a, ofs) & miniflow_get(b, ofs);
+
+ if (mask) {
+ dst->map[i] |= rightmost_1bit(map);
+ dst->values[n++] = mask;
+ }
+ }
+ }
+}
+
+/* Frees any memory owned by 'mask'. Does not free the storage in which 'mask'
+ * itself resides; the caller is responsible for that. */
+void
+minimask_destroy(struct minimask *mask)
+{
+ miniflow_destroy(&mask->masks);
+}
+
+/* Initializes 'dst' as a copy of 'src'. */
+void
+minimask_expand(const struct minimask *mask, struct flow_wildcards *wc)
+{
+ miniflow_expand(&mask->masks, &wc->masks);
+}
+
+/* Returns the uint32_t that would be at byte offset '4*u32_ofs' if 'mask'
+ * were expanded into a "struct flow_wildcards". */
+uint32_t
+minimask_get(const struct minimask *mask, unsigned int u32_ofs)
+{
+ return miniflow_get(&mask->masks, u32_ofs);
+}
+
+/* Returns the VID mask within the vlan_tci member of the "struct
+ * flow_wildcards" represented by 'mask'. */
+uint16_t
+minimask_get_vid_mask(const struct minimask *mask)
+{
+ return miniflow_get_vid(&mask->masks);
+}
+
+/* Returns true if 'a' and 'b' are the same flow mask, false otherwise. */
+bool
+minimask_equal(const struct minimask *a, const struct minimask *b)
+{
+ return miniflow_equal(&a->masks, &b->masks);
+}
+
+/* Returns a hash value for 'mask', given 'basis'. */
+uint32_t
+minimask_hash(const struct minimask *mask, uint32_t basis)
+{
+ return miniflow_hash(&mask->masks, basis);
+}
+
+/* Returns true if at least one bit is wildcarded in 'a' but not in 'b', false
+ * otherwise. */
+bool
+minimask_has_extra(const struct minimask *a_, const struct minimask *b_)
+{
+ const struct miniflow *a = &a_->masks;
+ const struct miniflow *b = &b_->masks;
+ int i;
+
+ for (i = 0; i < MINI_N_MAPS; i++) {
+ uint32_t map;
+
+ for (map = a->map[i] | b->map[i]; map;
+ map = zero_rightmost_1bit(map)) {
+ int ofs = raw_ctz(map) + i * 32;
+ uint32_t a_u32 = miniflow_get(a, ofs);
+ uint32_t b_u32 = miniflow_get(b, ofs);
+
+ if ((a_u32 & b_u32) != b_u32) {
+ return true;
+ }
+ }
+ }
+
+ return false;
+}
+
+/* Returns true if 'mask' matches every packet, false if 'mask' fixes any bits
+ * or fields. */
+bool
+minimask_is_catchall(const struct minimask *mask_)
+{
+ const struct miniflow *mask = &mask_->masks;
+
+ BUILD_ASSERT(MINI_N_MAPS == 2);
+ return !(mask->map[0] | mask->map[1]);
+}
+
diff --git a/lib/flow.h b/lib/flow.h
index d8680c0..7b32a2a 100644
--- a/lib/flow.h
+++ b/lib/flow.h
@@ -29,6 +29,8 @@
struct dpif_flow_stats;
struct ds;
struct flow_wildcards;
+struct miniflow;
+struct minimask;
struct ofpbuf;
/* This sequence number should be incremented whenever anything involving flows
@@ -134,6 +136,9 @@ flow_hash(const struct flow *flow, uint32_t basis)
{
return hash_words((const uint32_t *) flow, sizeof *flow / 4, basis);
}
+
+uint32_t flow_hash_in_minimask(const struct flow *, const struct minimask *,
+ uint32_t basis);
/* Wildcards for a flow.
*
@@ -170,5 +175,94 @@ bool flow_hash_fields_valid(enum nx_hash_fields);
bool flow_equal_except(const struct flow *a, const struct flow *b,
const struct flow_wildcards *);
+
+/* Compressed flow. */
+
+#define MINI_N_INLINE (sizeof(void *) == 4 ? 7 : 8)
+#define MINI_N_MAPS DIV_ROUND_UP(FLOW_U32S, 32) /* Currently 2. */
+
+/* A sparse representation of a "struct flow".
+ *
+ * A "struct flow" is fairly large and tends to be mostly zeros. Sparse
+ * representation has two advantages. First, it saves memory. Second, it
+ * saves time when the goal is to iterate over only the nonzero parts of the
+ * struct.
+ *
+ * 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.
+ *
+ * '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
+ * values[1], and so on.
+ *
+ * 'values' may point to a few different locations:
+ *
+ * - If 'map' has MINI_N_INLINE or fewer 1-bits, it may point to
+ * 'inline_values'. One hopes that this is the common case.
+ *
+ * - If 'map' has more than MINI_N_INLINE 1-bits, it may point to memory
+ * allocated with malloc().
+ *
+ * - The caller could provide storage on the stack for situations where
+ * 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.
+ */
+struct miniflow {
+ uint32_t *values;
+ uint32_t inline_values[MINI_N_INLINE];
+ uint32_t map[MINI_N_MAPS];
+};
+
+void miniflow_init(struct miniflow *, const struct flow *);
+void miniflow_clone(struct miniflow *, const struct miniflow *);
+void miniflow_destroy(struct miniflow *);
+
+void miniflow_expand(const struct miniflow *, struct flow *);
+
+uint32_t miniflow_get(const struct miniflow *, unsigned int u32_ofs);
+uint16_t miniflow_get_vid(const struct miniflow *);
+
+bool miniflow_equal(const struct miniflow *a, const struct miniflow *b);
+bool miniflow_equal_in_minimask(const struct miniflow *a,
+ const struct miniflow *b,
+ const struct minimask *);
+bool miniflow_equal_flow_in_minimask(const struct miniflow *a,
+ const struct flow *b,
+ const struct minimask *);
+uint32_t miniflow_hash(const struct miniflow *, uint32_t basis);
+uint32_t miniflow_hash_in_minimask(const struct miniflow *,
+ const struct minimask *, uint32_t basis);
+
+/* Compressed flow wildcards. */
+
+/* A sparse representation of a "struct flow_wildcards".
+ *
+ * See the large comment on struct miniflow for details. */
+struct minimask {
+ struct miniflow masks;
+};
+
+void minimask_init(struct minimask *, const struct flow_wildcards *);
+void minimask_clone(struct minimask *, const struct minimask *);
+void minimask_combine(struct minimask *dst,
+ const struct minimask *a, const struct minimask *b,
+ uint32_t storage[FLOW_U32S]);
+void minimask_destroy(struct minimask *);
+
+void minimask_expand(const struct minimask *, struct flow_wildcards *);
+
+uint32_t minimask_get(const struct minimask *, unsigned int u32_ofs);
+uint16_t minimask_get_vid_mask(const struct minimask *);
+
+bool minimask_equal(const struct minimask *a, const struct minimask *b);
+uint32_t minimask_hash(const struct minimask *, uint32_t basis);
+
+bool minimask_has_extra(const struct minimask *, const struct minimask *);
+bool minimask_is_catchall(const struct minimask *);
#endif /* flow.h */
diff --git a/lib/match.c b/lib/match.c
index d3f4e84..800e4b6 100644
--- a/lib/match.c
+++ b/lib/match.c
@@ -748,3 +748,79 @@ match_print(const struct match *match)
puts(s);
free(s);
}
+
+/* Initializes 'dst' as a copy of 'src'. The caller must eventually free 'dst'
+ * with minimatch_destroy(). */
+void
+minimatch_init(struct minimatch *dst, const struct match *src)
+{
+ /* XXX should we make sure that the flow and mask have the same map? */
+ miniflow_init(&dst->flow, &src->flow);
+ minimask_init(&dst->mask, &src->wc);
+}
+
+/* Initializes 'dst' as a copy of 'src'. The caller must eventually free 'dst'
+ * with minimatch_destroy(). */
+void
+minimatch_clone(struct minimatch *dst, const struct minimatch *src)
+{
+ miniflow_clone(&dst->flow, &src->flow);
+ minimask_clone(&dst->mask, &src->mask);
+}
+
+/* Frees any memory owned by 'match'. Does not free the storage in which
+ * 'match' itself resides; the caller is responsible for that. */
+void
+minimatch_destroy(struct minimatch *match)
+{
+ miniflow_destroy(&match->flow);
+ minimask_destroy(&match->mask);
+}
+
+/* Initializes 'dst' as a copy of 'src'. */
+void
+minimatch_expand(const struct minimatch *src, struct match *dst)
+{
+ miniflow_expand(&src->flow, &dst->flow);
+ minimask_expand(&src->mask, &dst->wc);
+}
+
+/* Returns true if 'a' and 'b' match the same packets, false otherwise. */
+bool
+minimatch_equal(const struct minimatch *a, const struct minimatch *b)
+{
+ return (miniflow_equal(&a->flow, &b->flow)
+ && minimask_equal(&a->mask, &b->mask));
+}
+
+/* Returns a hash value for 'match', given 'basis'. */
+uint32_t
+minimatch_hash(const struct minimatch *match, uint32_t basis)
+{
+ return miniflow_hash(&match->flow, minimask_hash(&match->mask, basis));
+}
+
+/* Appends a string representation of 'match' to 's'. If 'priority' is
+ * different from OFP_DEFAULT_PRIORITY, includes it in 's'. */
+void
+minimatch_format(const struct minimatch *match, struct ds *s,
+ unsigned int priority)
+{
+ struct match megamatch;
+
+ minimatch_expand(match, &megamatch);
+ match_format(&megamatch, s, priority);
+}
+
+/* Converts 'match' to a string and returns the string. If 'priority' is
+ * different from OFP_DEFAULT_PRIORITY, includes it in the string. The caller
+ * must free the string (with free()). */
+char *
+minimatch_to_string(const struct minimatch *match, unsigned int priority)
+{
+ struct match megamatch;
+
+ minimatch_expand(match, &megamatch);
+ return match_to_string(&megamatch, priority);
+}
+
diff --git a/lib/match.h b/lib/match.h
index 8761dc9..e177083 100644
--- a/lib/match.h
+++ b/lib/match.h
@@ -19,6 +19,8 @@
#include "flow.h"
+struct ds;
+
/* A flow classification match.
*
* Use one of the match_*() functions to initialize a "struct match".
@@ -103,5 +105,34 @@ uint32_t match_hash(const struct match *, uint32_t basis);
void match_format(const struct match *, struct ds *, unsigned int priority);
char *match_to_string(const struct match *, unsigned int priority);
void match_print(const struct match *);
+
+/* Compressed 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'.
+ *
+ * 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. */
+struct minimatch {
+ struct miniflow flow;
+ struct minimask mask;
+};
+
+void minimatch_init(struct minimatch *, const struct match *);
+void minimatch_clone(struct minimatch *, const struct minimatch *);
+void minimatch_destroy(struct minimatch *);
+
+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);
+
+void minimatch_format(const struct minimatch *, struct ds *,
+ unsigned int priority);
+char *minimatch_to_string(const struct minimatch *, unsigned int priority);
#endif /* match.h */
diff --git a/ofproto/connmgr.c b/ofproto/connmgr.c
index 4270256..5f9656f 100644
--- a/ofproto/connmgr.c
+++ b/ofproto/connmgr.c
@@ -1716,7 +1716,7 @@ ofmonitor_create(const struct ofputil_flow_monitor_request *request,
m->flags = request->flags;
m->out_port = request->out_port;
m->table_id = request->table_id;
- m->match = request->match;
+ minimatch_init(&m->match, &request->match);
*monitorp = m;
return 0;
@@ -1804,6 +1804,7 @@ ofmonitor_report(struct connmgr *mgr, struct rule *rule,
if (ofconn != abbrev_ofconn || ofconn->monitor_paused) {
struct ofputil_flow_update fu;
+ struct match match;
fu.event = event;
fu.reason = event == NXFME_DELETED ? reason : 0;
@@ -1811,7 +1812,8 @@ ofmonitor_report(struct connmgr *mgr, struct rule *rule,
fu.hard_timeout = rule->hard_timeout;
fu.table_id = rule->table_id;
fu.cookie = rule->flow_cookie;
- fu.match = &rule->cr.match;
+ minimatch_expand(&rule->cr.match, &match);
+ fu.match = &match;
if (flags & NXFMF_ACTIONS) {
fu.ofpacts = rule->ofpacts;
fu.ofpacts_len = rule->ofpacts_len;
diff --git a/ofproto/connmgr.h b/ofproto/connmgr.h
index 00dd371..9a080f2 100644
--- a/ofproto/connmgr.h
+++ b/ofproto/connmgr.h
@@ -173,7 +173,7 @@ struct ofmonitor {
/* Matching. */
uint16_t out_port;
uint8_t table_id;
- struct match match;
+ struct minimatch match;
};
struct ofputil_flow_monitor_request;
diff --git a/ofproto/ofproto-dpif.c b/ofproto/ofproto-dpif.c
index 297e62e..84f4386 100644
--- a/ofproto/ofproto-dpif.c
+++ b/ofproto/ofproto-dpif.c
@@ -116,8 +116,7 @@ static void rule_credit_stats(struct rule_dpif *,
static void flow_push_stats(struct rule_dpif *, const struct flow *,
const struct dpif_flow_stats *);
static tag_type rule_calculate_tag(const struct flow *,
- const struct flow_wildcards *,
- uint32_t basis);
+ const struct minimask *, uint32_t basis);
static void rule_invalidate(const struct rule_dpif *);
#define MAX_MIRRORS 32
@@ -4619,11 +4618,17 @@ rule_construct(struct rule *rule_)
}
table_id = rule->up.table_id;
- rule->tag = (victim ? victim->tag
- : table_id == 0 ? 0
- : rule_calculate_tag(&rule->up.cr.match.flow,
- &rule->up.cr.match.wc,
- ofproto->tables[table_id].basis));
+ if (victim) {
+ rule->tag = victim->tag;
+ } else if (table_id == 0) {
+ rule->tag = 0;
+ } else {
+ struct flow flow;
+
+ miniflow_expand(&rule->up.cr.match.flow, &flow);
+ rule->tag = rule_calculate_tag(&flow, &rule->up.cr.match.mask,
+ ofproto->tables[table_id].basis);
+ }
complete_operation(rule);
return 0;
@@ -4969,7 +4974,7 @@ xlate_table_action(struct action_xlate_ctx *ctx,
ctx->tags |= (rule && rule->tag
? rule->tag
: rule_calculate_tag(&ctx->flow,
- &table->other_table->wc,
+ &table->other_table->mask,
table->basis));
}
}
@@ -6232,18 +6237,17 @@ xlate_normal(struct action_xlate_ctx *ctx)
* a few more, but not all of the facets or even all of the facets that
* resubmit to the table modified by MAC learning). */
-/* Calculates the tag to use for 'flow' and wildcards 'wc' when it is inserted
+/* Calculates the tag to use for 'flow' and mask 'mask' when it is inserted
* into an OpenFlow table with the given 'basis'. */
static tag_type
-rule_calculate_tag(const struct flow *flow, const struct flow_wildcards *wc,
+rule_calculate_tag(const struct flow *flow, const struct minimask *mask,
uint32_t secret)
{
- if (flow_wildcards_is_catchall(wc)) {
+ if (minimask_is_catchall(mask)) {
return 0;
} else {
- struct flow tag_flow = *flow;
- flow_zero_wildcards(&tag_flow, wc);
- return tag_create_deterministic(flow_hash(&tag_flow, secret));
+ uint32_t hash = flow_hash_in_minimask(flow, mask, secret);
+ return tag_create_deterministic(hash);
}
}
diff --git a/ofproto/ofproto.c b/ofproto/ofproto.c
index 4cb56e2..ebef587 100644
--- a/ofproto/ofproto.c
+++ b/ofproto/ofproto.c
@@ -2139,6 +2139,7 @@ handle_packet_out(struct ofconn *ofconn, const struct ofp_packet_out *opo)
goto exit_free_ofpacts;
}
+
/* Get payload. */
if (po.buffer_id != UINT32_MAX) {
error = ofconn_pktbuf_retrieve(ofconn, po.buffer_id, &payload, NULL);
@@ -2566,7 +2567,7 @@ handle_flow_stats_request(struct ofconn *ofconn,
long long int now = time_msec();
struct ofputil_flow_stats fs;
- fs.match = rule->cr.match;
+ minimatch_expand(&rule->cr.match, &fs.match);
fs.priority = rule->cr.priority;
fs.cookie = rule->flow_cookie;
fs.table_id = rule->table_id;
@@ -3191,7 +3192,7 @@ ofproto_rule_send_removed(struct rule *rule, uint8_t reason)
return;
}
- fr.match = rule->cr.match;
+ minimatch_expand(&rule->cr.match, &fr.match);
fr.priority = rule->cr.priority;
fr.cookie = rule->flow_cookie;
fr.reason = reason;
@@ -3503,6 +3504,7 @@ ofproto_compose_flow_refresh_update(const struct rule *rule,
{
struct ofoperation *op = rule->pending;
struct ofputil_flow_update fu;
+ struct match match;
if (op && op->type == OFOPERATION_ADD && !op->victim) {
/* We'll report the final flow when the operation completes. Reporting
@@ -3517,7 +3519,8 @@ ofproto_compose_flow_refresh_update(const struct rule *rule,
fu.hard_timeout = rule->hard_timeout;
fu.table_id = rule->table_id;
fu.cookie = rule->flow_cookie;
- fu.match = CONST_CAST(struct match *, &rule->cr.match);
+ minimatch_expand(&rule->cr.match, &match);
+ fu.match = &match;
if (!(flags & NXFMF_ACTIONS)) {
fu.ofpacts = NULL;
fu.ofpacts_len = 0;
@@ -3622,7 +3625,7 @@ ofproto_collect_ofmonitor_refresh_rules(const struct ofmonitor *m,
const struct oftable *table;
struct cls_rule target;
- cls_rule_init(&target, &m->match, 0);
+ cls_rule_init_from_minimatch(&target, &m->match, 0);
FOR_EACH_MATCHING_TABLE (table, m->table_id, ofproto) {
struct cls_cursor cursor;
struct rule *rule;
@@ -4024,13 +4027,13 @@ ofopgroup_complete(struct ofopgroup *group)
switch (op->type) {
case OFOPERATION_ADD:
if (!op->error) {
+ uint16_t vid_mask;
+
ofproto_rule_destroy__(op->victim);
- if ((rule->cr.match.wc.masks.vlan_tci & htons(VLAN_VID_MASK))
- == htons(VLAN_VID_MASK)) {
+ vid_mask = minimask_get_vid_mask(&rule->cr.match.mask);
+ if (vid_mask == VLAN_VID_MASK) {
if (ofproto->vlan_bitmap) {
- uint16_t vid;
-
- vid = vlan_tci_to_vid(rule->cr.match.flow.vlan_tci);
+ uint16_t vid = miniflow_get_vid(&rule->cr.match.flow);
if (!bitmap_is_set(ofproto->vlan_bitmap, vid)) {
bitmap_set1(ofproto->vlan_bitmap, vid);
ofproto->vlans_changed = true;
@@ -4364,17 +4367,19 @@ eviction_group_hash_rule(struct rule *rule)
{
struct oftable *table = &rule->ofproto->tables[rule->table_id];
const struct mf_subfield *sf;
+ struct flow flow;
uint32_t hash;
hash = table->eviction_group_id_basis;
+ miniflow_expand(&rule->cr.match.flow, &flow);
for (sf = table->eviction_fields;
sf < &table->eviction_fields[table->n_eviction_fields];
sf++)
{
- if (mf_are_prereqs_ok(sf->field, &rule->cr.match.flow)) {
+ if (mf_are_prereqs_ok(sf->field, &flow)) {
union mf_value value;
- mf_get_value(sf->field, &rule->cr.match.flow, &value);
+ mf_get_value(sf->field, &flow, &value);
if (sf->ofs) {
bitwise_zero(&value, sf->field->n_bytes, 0, sf->ofs);
}
@@ -4680,12 +4685,11 @@ ofproto_get_vlan_usage(struct ofproto *ofproto, unsigned long int *vlan_bitmap)
const struct cls_table *table;
HMAP_FOR_EACH (table, hmap_node, &oftable->cls.tables) {
- if ((table->wc.masks.vlan_tci & htons(VLAN_VID_MASK))
- == htons(VLAN_VID_MASK)) {
+ if (minimask_get_vid_mask(&table->mask) == VLAN_VID_MASK) {
const struct cls_rule *rule;
HMAP_FOR_EACH (rule, hmap_node, &table->rules) {
- uint16_t vid = vlan_tci_to_vid(rule->match.flow.vlan_tci);
+ uint16_t vid = miniflow_get_vid(&rule->match.flow);
bitmap_set1(vlan_bitmap, vid);
bitmap_set1(ofproto->vlan_bitmap, vid);
}
diff --git a/tests/test-classifier.c b/tests/test-classifier.c
index 5e24dd2..f879854 100644
--- a/tests/test-classifier.c
+++ b/tests/test-classifier.c
@@ -183,52 +183,54 @@ tcls_remove(struct tcls *cls, const struct test_rule *rule)
}
static bool
-match(const struct cls_rule *wild, const struct flow *fixed)
+match(const struct cls_rule *wild_, const struct flow *fixed)
{
+ struct match wild;
int f_idx;
+ minimatch_expand(&wild_->match, &wild);
for (f_idx = 0; f_idx < CLS_N_FIELDS; f_idx++) {
bool eq;
if (f_idx == CLS_F_IDX_NW_SRC) {
- eq = !((fixed->nw_src ^ wild->match.flow.nw_src)
- & wild->match.wc.masks.nw_src);
+ eq = !((fixed->nw_src ^ wild.flow.nw_src)
+ & wild.wc.masks.nw_src);
} else if (f_idx == CLS_F_IDX_NW_DST) {
- eq = !((fixed->nw_dst ^ wild->match.flow.nw_dst)
- & wild->match.wc.masks.nw_dst);
+ eq = !((fixed->nw_dst ^ wild.flow.nw_dst)
+ & wild.wc.masks.nw_dst);
} else if (f_idx == CLS_F_IDX_TP_SRC) {
- eq = !((fixed->tp_src ^ wild->match.flow.tp_src)
- & wild->match.wc.masks.tp_src);
+ eq = !((fixed->tp_src ^ wild.flow.tp_src)
+ & wild.wc.masks.tp_src);
} else if (f_idx == CLS_F_IDX_TP_DST) {
- eq = !((fixed->tp_dst ^ wild->match.flow.tp_dst)
- & wild->match.wc.masks.tp_dst);
+ eq = !((fixed->tp_dst ^ wild.flow.tp_dst)
+ & wild.wc.masks.tp_dst);
} else if (f_idx == CLS_F_IDX_DL_SRC) {
- eq = eth_addr_equal_except(fixed->dl_src, wild->match.flow.dl_src,
- wild->match.wc.masks.dl_src);
+ eq = eth_addr_equal_except(fixed->dl_src, wild.flow.dl_src,
+ wild.wc.masks.dl_src);
} else if (f_idx == CLS_F_IDX_DL_DST) {
- eq = eth_addr_equal_except(fixed->dl_dst, wild->match.flow.dl_dst,
- wild->match.wc.masks.dl_dst);
+ eq = eth_addr_equal_except(fixed->dl_dst, wild.flow.dl_dst,
+ wild.wc.masks.dl_dst);
} else if (f_idx == CLS_F_IDX_VLAN_TCI) {
- eq = !((fixed->vlan_tci ^ wild->match.flow.vlan_tci)
- & wild->match.wc.masks.vlan_tci);
+ eq = !((fixed->vlan_tci ^ wild.flow.vlan_tci)
+ & wild.wc.masks.vlan_tci);
} else if (f_idx == CLS_F_IDX_TUN_ID) {
- eq = !((fixed->tun_id ^ wild->match.flow.tun_id)
- & wild->match.wc.masks.tun_id);
+ eq = !((fixed->tun_id ^ wild.flow.tun_id)
+ & wild.wc.masks.tun_id);
} else if (f_idx == CLS_F_IDX_METADATA) {
- eq = !((fixed->metadata ^ wild->match.flow.metadata)
- & wild->match.wc.masks.metadata);
+ eq = !((fixed->metadata ^ wild.flow.metadata)
+ & wild.wc.masks.metadata);
} else if (f_idx == CLS_F_IDX_NW_DSCP) {
- eq = !((fixed->nw_tos ^ wild->match.flow.nw_tos) &
- (wild->match.wc.masks.nw_tos & IP_DSCP_MASK));
+ eq = !((fixed->nw_tos ^ wild.flow.nw_tos) &
+ (wild.wc.masks.nw_tos & IP_DSCP_MASK));
} else if (f_idx == CLS_F_IDX_NW_PROTO) {
- eq = !((fixed->nw_proto ^ wild->match.flow.nw_proto)
- & wild->match.wc.masks.nw_proto);
+ eq = !((fixed->nw_proto ^ wild.flow.nw_proto)
+ & wild.wc.masks.nw_proto);
} else if (f_idx == CLS_F_IDX_DL_TYPE) {
- eq = !((fixed->dl_type ^ wild->match.flow.dl_type)
- & wild->match.wc.masks.dl_type);
+ eq = !((fixed->dl_type ^ wild.flow.dl_type)
+ & wild.wc.masks.dl_type);
} else if (f_idx == CLS_F_IDX_IN_PORT) {
- eq = !((fixed->in_port ^ wild->match.flow.in_port)
- & wild->match.wc.masks.in_port);
+ eq = !((fixed->in_port ^ wild.flow.in_port)
+ & wild.wc.masks.in_port);
} else {
NOT_REACHED();
}
@@ -261,13 +263,17 @@ tcls_delete_matches(struct tcls *cls, const struct cls_rule *target)
for (i = 0; i < cls->n_rules; ) {
struct test_rule *pos = cls->rules[i];
- if (!flow_wildcards_has_extra(&pos->cls_rule.match.wc,
- &target->match.wc)
- && match(target, &pos->cls_rule.match.flow)) {
- tcls_remove(cls, pos);
- } else {
- i++;
+ if (!minimask_has_extra(&pos->cls_rule.match.mask,
+ &target->match.mask)) {
+ struct flow flow;
+
+ miniflow_expand(&pos->cls_rule.match.flow, &flow);
+ if (match(target, &flow)) {
+ tcls_remove(cls, pos);
+ continue;
+ }
}
+ i++;
}
}
diff --git a/utilities/ovs-ofctl.c b/utilities/ovs-ofctl.c
index 93cd7ac..cd45d82 100644
--- a/utilities/ovs-ofctl.c
+++ b/utilities/ovs-ofctl.c
@@ -1971,7 +1971,7 @@ fte_make_flow_mod(const struct fte *fte, int index, uint16_t command,
struct ofputil_flow_mod fm;
struct ofpbuf *ofm;
- fm.match = fte->rule.match;
+ minimatch_expand(&fte->rule.match, &fm.match);
fm.priority = fte->rule.priority;
fm.cookie = htonll(0);
fm.cookie_mask = htonll(0);
@@ -2084,8 +2084,8 @@ ofctl_diff_flows(int argc OVS_UNUSED, char *argv[])
struct fte_version *b = fte->versions[1];
if (!a || !b || !fte_version_equals(a, b)) {
- char *rule_s = match_to_string(&fte->rule.match,
- fte->rule.priority);
+ char *rule_s = minimatch_to_string(&fte->rule.match,
+ fte->rule.priority);
if (a) {
printf("-%s", rule_s);
fte_version_print(a);
@@ -2345,8 +2345,7 @@ ofctl_parse_ofp10_match(int argc OVS_UNUSED, char *argv[] OVS_UNUSED)
}
/* Convert to cls_rule and print. */
- ofputil_match_from_ofp10_match(match_in.data, OFP_DEFAULT_PRIORITY,
- &match);
+ ofputil_match_from_ofp10_match(match_in.data, 0, &match);
match_print(&match);
/* Convert back to ofp10_match and print differences from input. */
--
1.7.2.5
More information about the dev
mailing list