From 5cb7a798405c6ccc07bf9a932b709643c072b086 Mon Sep 17 00:00:00 2001 From: Ben Pfaff Date: Tue, 4 Sep 2012 12:43:53 -0700 Subject: [PATCH] Introduce sparse flows and masks, to reduce memory usage and improve speed. 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. Signed-off-by: Ben Pfaff --- lib/classifier.c | 114 +++++------ lib/classifier.h | 17 +- lib/flow.c | 416 ++++++++++++++++++++++++++++++++++++++++ lib/flow.h | 94 +++++++++ lib/match.c | 74 +++++++ lib/match.h | 31 +++ ofproto/connmgr.c | 6 +- ofproto/connmgr.h | 2 +- ofproto/ofproto-dpif.c | 32 ++-- ofproto/ofproto.c | 32 ++-- tests/classifier.at | 10 + tests/test-classifier.c | 385 +++++++++++++++++++++++++++++++++---- utilities/ovs-ofctl.c | 2 +- 13 files changed, 1087 insertions(+), 128 deletions(-) diff --git a/lib/classifier.c b/lib/classifier.c index 81b05fdb..e5d226ec 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,20 +54,28 @@ 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. * * The caller must eventually destroy 'rule' with cls_rule_destroy(). * - * 'match' must satisfy the invariant described in the comment at the - * definition of struct match. - * * (OpenFlow uses priorities between 0 and UINT16_MAX, inclusive, but * internally Open vSwitch supports a wider range.) */ 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; +} + +/* 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; } @@ -77,7 +85,8 @@ cls_rule_init(struct cls_rule *rule, 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 @@ -85,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, @@ -95,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 @@ -178,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); @@ -213,7 +222,7 @@ 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); @@ -263,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; @@ -306,17 +316,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; } } @@ -361,11 +372,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. */ @@ -374,14 +385,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) { @@ -463,13 +475,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; } } @@ -477,15 +489,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; } @@ -493,6 +504,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); @@ -501,35 +513,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; } } @@ -541,7 +544,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 ebb1bbad..bc9db33f 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 d7765676..a2172a9c 100644 --- a/lib/flow.c +++ b/lib/flow.c @@ -19,9 +19,11 @@ #include #include #include +#include #include #include #include +#include #include #include #include "byte-order.h" @@ -38,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) @@ -870,3 +873,416 @@ flow_compose(struct ofpbuf *b, const struct flow *flow) } } } + +/* Compressed flow. */ + +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; +} + +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 +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++; + } + } + + /* Initialize dst->values. */ + dst->values = miniflow_alloc_values(dst, n); + ofs = 0; + for (i = 0; i < MINI_N_MAPS; i++) { + uint32_t map; + + for (map = dst->map[i]; map; map = zero_rightmost_1bit(map)) { + dst->values[ofs++] = src_u32[raw_ctz(map) + i * 32]; + } + } +} + +/* Initializes 'dst' as a copy of 'src'. The caller must eventually free 'dst' + * with miniflow_destroy(). */ +void +miniflow_clone(struct miniflow *dst, const struct miniflow *src) +{ + int n = miniflow_n_values(src); + memcpy(dst->map, src->map, sizeof dst->map); + dst->values = miniflow_alloc_values(dst, n); + 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; + + BUILD_ASSERT(MINI_N_MAPS == 2); + 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. */ +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 = mhash_add(hash, miniflow_get(flow, ofs) & *p); + p++; + } + } + + 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. */ +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 = mhash_add(hash, flow_u32[ofs] & *p); + p++; + } + } + + return mhash_finish(hash, p - mask->masks.values); +} + +/* 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; + + dst->map[i] = 0; + for (map = a->map[i] & b->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 ba2b8f6e..fc622220 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 @@ -127,6 +129,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. * @@ -163,5 +168,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) + +/* 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 d337c1b7..69129d4f 100644 --- a/lib/match.c +++ b/lib/match.c @@ -773,3 +773,77 @@ 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) +{ + 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 e3563d27..2d058194 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". @@ -105,5 +107,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 4e1ba9df..391995e7 100644 --- a/ofproto/connmgr.c +++ b/ofproto/connmgr.c @@ -1717,7 +1717,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; @@ -1805,6 +1805,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; @@ -1812,7 +1813,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 00dd3715..9a080f28 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 1fac7ab5..1289025b 100644 --- a/ofproto/ofproto-dpif.c +++ b/ofproto/ofproto-dpif.c @@ -118,8 +118,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 @@ -4665,11 +4664,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; @@ -5015,7 +5020,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)); } } @@ -6316,18 +6321,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 28384c7b..5cf1a6a2 100644 --- a/ofproto/ofproto.c +++ b/ofproto/ofproto.c @@ -2134,6 +2134,7 @@ handle_packet_out(struct ofconn *ofconn, const struct ofp_header *oh) goto exit_free_ofpacts; } + /* Get payload. */ if (po.buffer_id != UINT32_MAX) { error = ofconn_pktbuf_retrieve(ofconn, po.buffer_id, &payload, NULL); @@ -2563,7 +2564,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; @@ -3202,7 +3203,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; @@ -3514,6 +3515,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 @@ -3528,7 +3530,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; @@ -3633,7 +3636,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; @@ -4019,13 +4022,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; @@ -4359,17 +4362,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); } @@ -4675,12 +4680,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/classifier.at b/tests/classifier.at index 26ca0798..cf0cc442 100644 --- a/tests/classifier.at +++ b/tests/classifier.at @@ -12,3 +12,13 @@ m4_foreach( [AT_SETUP([flow classifier - m4_bpatsubst(testname, [-], [ ])]) AT_CHECK([test-classifier testname], [0], [], []) AT_CLEANUP])]) + +AT_BANNER([miniflow unit tests]) +m4_foreach( + [testname], + [[miniflow], + [minimask_has_extra], + [minimask_combine]], + [AT_SETUP([miniflow - m4_bpatsubst(testname, [-], [ ])]) + AT_CHECK([test-classifier testname], [0], [], []) + AT_CLEANUP])]) diff --git a/tests/test-classifier.c b/tests/test-classifier.c index 5e24dd22..a7daa944 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++; } } @@ -555,7 +561,20 @@ shuffle(unsigned int *p, size_t n) *q = tmp; } } + +static void +shuffle_u32s(uint32_t *p, size_t n) +{ + for (; n > 1; n--, p++) { + uint32_t *q = &p[rand() % n]; + uint32_t tmp = *p; + *p = *q; + *q = tmp; + } +} +/* Classifier tests. */ + /* Tests an empty classifier. */ static void test_empty(int argc OVS_UNUSED, char *argv[] OVS_UNUSED) @@ -950,7 +969,301 @@ test_many_rules_in_five_tables(int argc OVS_UNUSED, char *argv[] OVS_UNUSED) test_many_rules_in_n_tables(5); } +/* Miniflow tests. */ + +static uint32_t +random_value(void) +{ + static const uint32_t values[] = + { 0xffffffff, 0xaaaaaaaa, 0x55555555, 0x80000000, + 0x00000001, 0xface0000, 0x00d00d1e, 0xdeadbeef }; + + return values[random_uint32() % ARRAY_SIZE(values)]; +} + +static bool +choose(unsigned int n, unsigned int *idxp) +{ + if (*idxp < n) { + return true; + } else { + *idxp -= n; + return false; + } +} + +static bool +init_consecutive_values(int n_consecutive, struct flow *flow, + unsigned int *idxp) +{ + uint32_t *flow_u32 = (uint32_t *) flow; + + if (choose(FLOW_U32S - n_consecutive + 1, idxp)) { + int i; + + for (i = 0; i < n_consecutive; i++) { + flow_u32[*idxp + i] = random_value(); + } + return true; + } else { + return false; + } +} + +static bool +next_random_flow(struct flow *flow, unsigned int idx) +{ + uint32_t *flow_u32 = (uint32_t *) flow; + int i; + + memset(flow, 0, sizeof *flow); + + /* Empty flow. */ + if (choose(1, &idx)) { + return true; + } + + /* All flows with a small number of consecutive nonzero values. */ + for (i = 1; i <= 4; i++) { + if (init_consecutive_values(i, flow, &idx)) { + return true; + } + } + + /* All flows with a large number of consecutive nonzero values. */ + for (i = FLOW_U32S - 4; i <= FLOW_U32S; i++) { + if (init_consecutive_values(i, flow, &idx)) { + return true; + } + } + + /* All flows with exactly two nonconsecutive nonzero values. */ + if (choose((FLOW_U32S - 1) * (FLOW_U32S - 2) / 2, &idx)) { + int ofs1; + + for (ofs1 = 0; ofs1 < FLOW_U32S - 2; ofs1++) { + int ofs2; + + for (ofs2 = ofs1 + 2; ofs2 < FLOW_U32S; ofs2++) { + if (choose(1, &idx)) { + flow_u32[ofs1] = random_value(); + flow_u32[ofs2] = random_value(); + return true; + } + } + } + NOT_REACHED(); + } + + /* 16 randomly chosen flows with N >= 3 nonzero values. */ + if (choose(16 * (FLOW_U32S - 4), &idx)) { + int n = idx / 16 + 3; + int i; + + for (i = 0; i < n; i++) { + flow_u32[i] = random_value(); + } + shuffle_u32s(flow_u32, FLOW_U32S); + + return true; + } + + return false; +} + +static void +any_random_flow(struct flow *flow) +{ + static unsigned int max; + if (!max) { + while (next_random_flow(flow, max)) { + max++; + } + } + + next_random_flow(flow, random_range(max)); +} + +static void +toggle_masked_flow_bits(struct flow *flow, const struct flow_wildcards *mask) +{ + const uint32_t *mask_u32 = (const uint32_t *) &mask->masks; + uint32_t *flow_u32 = (uint32_t *) flow; + int i; + + for (i = 0; i < FLOW_U32S; i++) { + if (mask_u32[i] != 0) { + uint32_t bit; + + do { + bit = 1u << random_range(32); + } while (!(bit & mask_u32[i])); + flow_u32[i] ^= bit; + } + } +} + +static void +wildcard_extra_bits(struct flow_wildcards *mask) +{ + uint32_t *mask_u32 = (uint32_t *) &mask->masks; + int i; + + for (i = 0; i < FLOW_U32S; i++) { + if (mask_u32[i] != 0) { + uint32_t bit; + + do { + bit = 1u << random_range(32); + } while (!(bit & mask_u32[i])); + mask_u32[i] &= ~bit; + } + } +} + +static void +test_miniflow(int argc OVS_UNUSED, char *argv[] OVS_UNUSED) +{ + struct flow flow; + unsigned int idx; + + random_set_seed(0xb3faca38); + for (idx = 0; next_random_flow(&flow, idx); idx++) { + const uint32_t *flow_u32 = (const uint32_t *) &flow; + struct miniflow miniflow, miniflow2, miniflow3; + struct flow flow2, flow3; + struct flow_wildcards mask; + struct minimask minimask; + int i; + + /* Convert flow to miniflow. */ + miniflow_init(&miniflow, &flow); + + /* Check that the flow equals its miniflow. */ + assert(miniflow_get_vid(&miniflow) == vlan_tci_to_vid(flow.vlan_tci)); + for (i = 0; i < FLOW_U32S; i++) { + assert(miniflow_get(&miniflow, i) == flow_u32[i]); + } + + /* Check that the miniflow equals itself. */ + assert(miniflow_equal(&miniflow, &miniflow)); + + /* Convert miniflow back to flow and verify that it's the same. */ + miniflow_expand(&miniflow, &flow2); + assert(flow_equal(&flow, &flow2)); + + /* Check that copying a miniflow works properly. */ + miniflow_clone(&miniflow2, &miniflow); + assert(miniflow_equal(&miniflow, &miniflow2)); + assert(miniflow_hash(&miniflow, 0) == miniflow_hash(&miniflow2, 0)); + miniflow_expand(&miniflow2, &flow3); + assert(flow_equal(&flow, &flow3)); + + /* Check that masked matches work as expected for identical flows and + * miniflows. */ + do { + next_random_flow(&mask.masks, 1); + } while (flow_wildcards_is_catchall(&mask)); + minimask_init(&minimask, &mask); + assert(minimask_is_catchall(&minimask) + == flow_wildcards_is_catchall(&mask)); + assert(miniflow_equal_in_minimask(&miniflow, &miniflow2, &minimask)); + assert(miniflow_equal_flow_in_minimask(&miniflow, &flow2, &minimask)); + assert(miniflow_hash_in_minimask(&miniflow, &minimask, 0x12345678) == + flow_hash_in_minimask(&flow, &minimask, 0x12345678)); + + /* Check that masked matches work as expected for differing flows and + * miniflows. */ + toggle_masked_flow_bits(&flow2, &mask); + assert(!miniflow_equal_flow_in_minimask(&miniflow, &flow2, &minimask)); + miniflow_init(&miniflow3, &flow2); + assert(!miniflow_equal_in_minimask(&miniflow, &miniflow3, &minimask)); + + /* Clean up. */ + miniflow_destroy(&miniflow); + miniflow_destroy(&miniflow2); + miniflow_destroy(&miniflow3); + minimask_destroy(&minimask); + } +} + +static void +test_minimask_has_extra(int argc OVS_UNUSED, char *argv[] OVS_UNUSED) +{ + struct flow_wildcards catchall; + struct minimask minicatchall; + struct flow flow; + unsigned int idx; + + flow_wildcards_init_catchall(&catchall); + minimask_init(&minicatchall, &catchall); + assert(minimask_is_catchall(&minicatchall)); + + random_set_seed(0x2ec7905b); + for (idx = 0; next_random_flow(&flow, idx); idx++) { + struct flow_wildcards mask; + struct minimask minimask; + + mask.masks = flow; + minimask_init(&minimask, &mask); + assert(!minimask_has_extra(&minimask, &minimask)); + assert(minimask_has_extra(&minicatchall, &minimask) + == !minimask_is_catchall(&minimask)); + if (!minimask_is_catchall(&minimask)) { + struct minimask minimask2; + + wildcard_extra_bits(&mask); + minimask_init(&minimask2, &mask); + assert(minimask_has_extra(&minimask2, &minimask)); + assert(!minimask_has_extra(&minimask, &minimask2)); + minimask_destroy(&minimask2); + } + + minimask_destroy(&minimask); + } +} + +static void +test_minimask_combine(int argc OVS_UNUSED, char *argv[] OVS_UNUSED) +{ + struct flow_wildcards catchall; + struct minimask minicatchall; + struct flow flow; + unsigned int idx; + + flow_wildcards_init_catchall(&catchall); + minimask_init(&minicatchall, &catchall); + assert(minimask_is_catchall(&minicatchall)); + + random_set_seed(0x181bf0cd); + for (idx = 0; next_random_flow(&flow, idx); idx++) { + struct minimask minimask, minimask2, minicombined; + struct flow_wildcards mask, mask2, combined, combined2; + uint32_t storage[FLOW_U32S]; + struct flow flow2; + + mask.masks = flow; + minimask_init(&minimask, &mask); + + minimask_combine(&minicombined, &minimask, &minicatchall, storage); + assert(minimask_is_catchall(&minicombined)); + + any_random_flow(&flow2); + mask2.masks = flow2; + minimask_init(&minimask2, &mask2); + + minimask_combine(&minicombined, &minimask, &minimask2, storage); + flow_wildcards_combine(&combined, &mask, &mask2); + minimask_expand(&minicombined, &combined2); + assert(flow_wildcards_equal(&combined, &combined2)); + + minimask_destroy(&minimask); + minimask_destroy(&minimask2); + } +} + static const struct command commands[] = { + /* Classifier tests. */ {"empty", 0, 0, test_empty}, {"destroy-null", 0, 0, test_destroy_null}, {"single-rule", 0, 0, test_single_rule}, @@ -959,6 +1272,12 @@ static const struct command commands[] = { {"many-rules-in-one-table", 0, 0, test_many_rules_in_one_table}, {"many-rules-in-two-tables", 0, 0, test_many_rules_in_two_tables}, {"many-rules-in-five-tables", 0, 0, test_many_rules_in_five_tables}, + + /* Miniflow and minimask tests. */ + {"miniflow", 0, 0, test_miniflow}, + {"minimask_has_extra", 0, 0, test_minimask_has_extra}, + {"minimask_combine", 0, 0, test_minimask_combine}, + {NULL, 0, 0, NULL}, }; diff --git a/utilities/ovs-ofctl.c b/utilities/ovs-ofctl.c index 2d982731..5f61fd68 100644 --- a/utilities/ovs-ofctl.c +++ b/utilities/ovs-ofctl.c @@ -1969,7 +1969,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); -- 2.30.2