[ovs-dev] [classifier-opt 28/28] Introduce sparse flows and masks, to reduce memory usage and improve speed.
Ethan Jackson
ethan at nicira.com
Tue Aug 21 01:58:43 UTC 2012
All your comments make sense, thanks.
> I really wanted this to be inline with GCC, since function call
> overhead for a single machine instruction is nasty. Anyhow, you're
> right, it deserves to be in util, and so I removed the raw_ctz() code
> from flow.c and slipped in the following patch before this one:
My only comment in this patch, is that it may make sense to inline
ctz() as well given how simple it is.
Ethan
>
> ----------------------------------------------------------------------
> From: Ben Pfaff <blp at nicira.com>
> Date: Mon, 20 Aug 2012 12:51:21 -0700
> Subject: [PATCH] util: New function raw_ctz().
>
> This will acquire a user in an upcoming commit.
>
> Signed-off-by: Ben Pfaff <blp at nicira.com>
> ---
> lib/util.c | 47 +++++++++++++++++++++++++----------------------
> lib/util.h | 17 +++++++++++++++++
> 2 files changed, 42 insertions(+), 22 deletions(-)
>
> diff --git a/lib/util.c b/lib/util.c
> index 256421a..d0ff872 100644
> --- a/lib/util.c
> +++ b/lib/util.c
> @@ -790,37 +790,40 @@ log_2_ceil(uint32_t n)
> return log_2_floor(n) + !IS_POW2(n);
> }
>
> -/* Returns the number of trailing 0-bits in 'n', or 32 if 'n' is 0. */
> -int
> -ctz(uint32_t n)
> -{
> - if (!n) {
> - return 32;
> - } else {
> +/* Returns the number of trailing 0-bits in 'n'. Undefined if 'n' == 0. */
> #if !defined(UINT_MAX) || !defined(UINT32_MAX)
> #error "Someone screwed up the #includes."
> #elif __GNUC__ >= 4 && UINT_MAX == UINT32_MAX
> - return __builtin_ctz(n);
> +/* Defined inline in util.h. */
> #else
> - unsigned int k;
> - int count = 31;
> +static int
> +raw_ctz(uint32_t n)
> +{
> + 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);
> + 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;
> + return count;
> +}
> #endif
> - }
> +
> +/* Returns the number of trailing 0-bits in 'n', or 32 if 'n' is 0. */
> +int
> +ctz(uint32_t n)
> +{
> + return n ? raw_ctz(n) : 32;
> }
>
> /* Returns the number of 1-bits in 'x', between 0 and 32 inclusive. */
> diff --git a/lib/util.h b/lib/util.h
> index a8d8665..f394673 100644
> --- a/lib/util.h
> +++ b/lib/util.h
> @@ -242,6 +242,23 @@ char *xreadlink(const char *filename);
> char *follow_symlinks(const char *filename);
>
> void ignore(bool x OVS_UNUSED);
> +
> +/* 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. */
> +#if !defined(UINT_MAX) || !defined(UINT32_MAX)
> +#error "Someone screwed up the #includes."
> +#elif __GNUC__ >= 4 && UINT_MAX == UINT32_MAX
> +static inline int
> +raw_ctz(uint32_t n)
> +{
> + return __builtin_ctz(n);
> +}
> +#else
> +/* Defined in util.c. */
> +int raw_ctz(uint32_t n);
> +#endif
> +
> int log_2_floor(uint32_t);
> int log_2_ceil(uint32_t);
> int ctz(uint32_t);
> --
> 1.7.2.5
> ----------------------------------------------------------------------
>
>> I think it would be worth while to directly unit test miniflows
>> instead of relying on the general OVS tests. It'd be quite simple to
>> create a bunch of random flows, convert them to miniflows, access each
>> of their elements and verify that they're correct, and then convert
>> them back and verify the haven't changed. The other helpers could be
>> tested pretty easily as well.
>
> I will do this.
>
>> Does it make sense to add a coverage counter which tells us how many
>> times we've initialized a miniflow which requires heap allocation?
>
> Sure.
>
> I implemented this as:
>
> diff --git a/lib/flow.c b/lib/flow.c
> index 7d96ff9..a2172a9 100644
> --- a/lib/flow.c
> +++ b/lib/flow.c
> @@ -40,6 +40,7 @@
> VLOG_DEFINE_THIS_MODULE(flow);
>
> COVERAGE_DEFINE(flow_extract);
> +COVERAGE_DEFINE(miniflow_malloc);
>
> static struct arp_eth_header *
> pull_arp(struct ofpbuf *packet)
> @@ -887,6 +888,17 @@ miniflow_n_values(const struct miniflow *flow)
> return n;
> }
>
> +static uint32_t *
> +miniflow_alloc_values(struct miniflow *flow, int n)
> +{
> + if (n <= MINI_N_INLINE) {
> + return flow->inline_values;
> + } else {
> + COVERAGE_INC(miniflow_malloc);
> + return xmalloc(n * sizeof *flow->values);
> + }
> +}
> +
> /* Initializes 'dst' as a copy of 'src'. The caller must eventually free 'dst'
> * with miniflow_destroy(). */
> void
> @@ -907,12 +919,8 @@ miniflow_init(struct miniflow *dst, const struct flow *src)
> }
> }
>
> - /* Allocate storage for nonzero elements. */
> - dst->values = (n <= MINI_N_INLINE
> - ? dst->inline_values
> - : xmalloc(n * sizeof *dst->values));
> -
> /* Initialize dst->values. */
> + dst->values = miniflow_alloc_values(dst, n);
> ofs = 0;
> for (i = 0; i < MINI_N_MAPS; i++) {
> uint32_t map;
> @@ -930,8 +938,7 @@ 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));
> + dst->values = miniflow_alloc_values(dst, n);
> memcpy(dst->values, src->values, n * sizeof *dst->values);
> }
>
>> miniflow_get__() either needs to build assert that MINI_N_MAPS == 2,
>> or be written more generally.
>
> Thanks for pointing that out. I added a build assertion.
>
>> Does it make sense to add iteration macros to help implement
>> miniflows? Most of the iteration code is both easy to get wrong, and
>> boilerplate. I haven't thought deeply about this, so I'd understand
>> if it doesn't make sense for some reason.
>>
>> In miniflow_hash_in_minimask() does it make sense to use hash_2words()
>> ,stead of hash_int() because the basis is important? I assume you
>> chose hash_int() because it's a bit faster.
>
> There was a comment in each place:
> * XXX murmurhash would be much better for this than hash_int(). */
> but I forgot to do that before sending out the commit. So here's the
> incremental to use murmurhash instead. The actual implementation of
> murmurhash is a separate commit that I just wrote up. I'll send it
> out separately for your review.
>
> diff --git a/lib/flow.c b/lib/flow.c
> index 19bbe6e..7d96ff9 100644
> --- a/lib/flow.c
> +++ b/lib/flow.c
> @@ -1095,9 +1095,7 @@ miniflow_hash(const struct miniflow *flow, uint32_t basis)
> * '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(). */
> + * flow_hash_in_minimask(), only the form of the arguments differ. */
> uint32_t
> miniflow_hash_in_minimask(const struct miniflow *flow,
> const struct minimask *mask, uint32_t basis)
> @@ -1113,21 +1111,19 @@ miniflow_hash_in_minimask(const struct miniflow *flow,
> 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);
> + hash = mhash_add(hash, miniflow_get(flow, ofs) & *p);
> p++;
> }
> }
>
> - return hash;
> + return mhash_finish(hash, p - mask->masks.values);
> }
>
> /* 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(). */
> + * miniflow_hash_in_minimask(), only the form of the arguments differ. */
> uint32_t
> flow_hash_in_minimask(const struct flow *flow, const struct minimask *mask,
> uint32_t basis)
> @@ -1144,12 +1140,12 @@ flow_hash_in_minimask(const struct flow *flow, const struct minimask *mask,
> 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);
> + hash = mhash_add(hash, flow_u32[ofs] & *p);
> p++;
> }
> }
>
> - return hash;
> + return mhash_finish(hash, p - mask->masks.values);
> }
>
> /* Initializes 'dst' as a copy of 'src'. The caller must eventually free 'dst'
>
>> The "Currently 2" comment in flow.h will go stale without a build assertion.
>
> Thanks, I've now deleted the comment.
>
>> Nits:
>>
>> s/'4*u32_ofs'/'4 * u32_ofs'/
>
> Fixed, thanks.
>
>> The comments in minimask_combine() and minimask_has_extra() talk about
>> 'dst', 'a', and 'b' when they are really referring to 'dst_', 'a_',
>> and 'b_'.
>
> Fixed.
>
>> Both flow.c and match.c have redundant newlines at the end of the file.
>
> Fixed.
>
>> Ethan
>>
>>
>>
>> On Fri, Jul 20, 2012 at 4:25 PM, Ben Pfaff <blp at nicira.com> wrote:
>> > 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