From df40c1520e4920a97d675620e92789ed99734eb5 Mon Sep 17 00:00:00 2001 From: Ben Pfaff Date: Wed, 6 Feb 2013 16:13:19 -0800 Subject: [PATCH] match: New function minimatch_matches_flow(). Signed-off-by: Ben Pfaff --- lib/classifier.c | 3 +- lib/flow.c | 126 +++++++++++++++++++++++++++++++++++++---------- lib/flow.h | 10 ++-- lib/match.c | 31 +++++++++++- lib/match.h | 16 +++--- 5 files changed, 146 insertions(+), 40 deletions(-) diff --git a/lib/classifier.c b/lib/classifier.c index 36eb1f0bf..89f56b6e7 100644 --- a/lib/classifier.c +++ b/lib/classifier.c @@ -668,8 +668,7 @@ find_match(const struct cls_table *table, const struct flow *flow) struct cls_rule *rule; HMAP_FOR_EACH_WITH_HASH (rule, hmap_node, hash, &table->rules) { - if (miniflow_equal_flow_in_minimask(&rule->match.flow, flow, - &table->mask)) { + if (minimatch_matches_flow(&rule->match, flow)) { return rule; } } diff --git a/lib/flow.c b/lib/flow.c index 9ab19617a..2c16a5232 100644 --- a/lib/flow.c +++ b/lib/flow.c @@ -1093,13 +1093,38 @@ miniflow_alloc_values(struct miniflow *flow, int n) } } +/* Completes an initialization of 'dst' as a miniflow copy of 'src' begun by + * the caller. The caller must have already initialized 'dst->map' properly + * to indicate the nonzero uint32_t elements of 'src'. 'n' must be the number + * of 1-bits in 'dst->map'. + * + * This function initializes 'dst->values' (either inline if possible or with + * malloc() otherwise) and copies the nonzero uint32_t elements of 'src' into + * it. */ +static void +miniflow_init__(struct miniflow *dst, const struct flow *src, int n) +{ + const uint32_t *src_u32 = (const uint32_t *) src; + unsigned int ofs; + int i; + + dst->values = miniflow_alloc_values(dst, n); + ofs = 0; + for (i = 0; i < MINI_N_MAPS; i++) { + uint32_t map; + + for (map = dst->map[i]; map; map = zero_rightmost_1bit(map)) { + dst->values[ofs++] = src_u32[raw_ctz(map) + i * 32]; + } + } +} + /* Initializes 'dst' as a copy of 'src'. The caller must eventually free 'dst' * with miniflow_destroy(). */ void miniflow_init(struct miniflow *dst, const struct flow *src) { const uint32_t *src_u32 = (const uint32_t *) src; - unsigned int ofs; unsigned int i; int n; @@ -1113,16 +1138,17 @@ miniflow_init(struct miniflow *dst, const struct flow *src) } } - /* Initialize dst->values. */ - dst->values = miniflow_alloc_values(dst, n); - ofs = 0; - for (i = 0; i < MINI_N_MAPS; i++) { - uint32_t map; + miniflow_init__(dst, src, n); +} - for (map = dst->map[i]; map; map = zero_rightmost_1bit(map)) { - dst->values[ofs++] = src_u32[raw_ctz(map) + i * 32]; - } - } +/* Initializes 'dst' as a copy of 'src', using 'mask->map' as 'dst''s map. The + * caller must eventually free 'dst' with miniflow_destroy(). */ +void +miniflow_init_with_minimask(struct miniflow *dst, const struct flow *src, + const struct minimask *mask) +{ + memcpy(dst->map, mask->masks.map, sizeof dst->map); + miniflow_init__(dst, src, miniflow_n_values(dst)); } /* Initializes 'dst' as a copy of 'src'. The caller must eventually free 'dst' @@ -1220,16 +1246,35 @@ miniflow_get_vid(const struct miniflow *flow) bool miniflow_equal(const struct miniflow *a, const struct miniflow *b) { + const uint32_t *ap = a->values; + const uint32_t *bp = b->values; int i; for (i = 0; i < MINI_N_MAPS; i++) { - if (a->map[i] != b->map[i]) { - return false; + const uint32_t a_map = a->map[i]; + const uint32_t b_map = b->map[i]; + uint32_t map; + + if (a_map == b_map) { + for (map = a_map; map; map = zero_rightmost_1bit(map)) { + if (*ap++ != *bp++) { + return false; + } + } + } else { + for (map = a_map | b_map; map; map = zero_rightmost_1bit(map)) { + uint32_t bit = rightmost_1bit(map); + uint32_t a_value = a_map & bit ? *ap++ : 0; + uint32_t b_value = b_map & bit ? *bp++ : 0; + + if (a_value != b_value) { + return false; + } + } } } - return !memcmp(a->values, b->values, - miniflow_n_values(a) * sizeof *a->values); + return true; } /* Returns true if 'a' and 'b' are equal at the places where there are 1-bits @@ -1289,10 +1334,24 @@ miniflow_equal_flow_in_minimask(const struct miniflow *a, const struct flow *b, uint32_t miniflow_hash(const struct miniflow *flow, uint32_t basis) { - BUILD_ASSERT_DECL(MINI_N_MAPS == 2); - return hash_3words(flow->map[0], flow->map[1], - hash_words(flow->values, miniflow_n_values(flow), - basis)); + const uint32_t *p = flow->values; + uint32_t hash = basis; + int i; + + for (i = 0; i < MINI_N_MAPS; i++) { + uint32_t hash_map = 0; + uint32_t map; + + for (map = flow->map[i]; map; map = zero_rightmost_1bit(map)) { + if (*p) { + hash = mhash_add(hash, *p); + hash_map |= rightmost_1bit(map); + } + p++; + } + hash = mhash_add(hash, hash_map); + } + return mhash_finish(hash, p - flow->values); } /* Returns a hash value for the bits of 'flow' where there are 1-bits in @@ -1313,9 +1372,10 @@ miniflow_hash_in_minimask(const struct miniflow *flow, uint32_t map; for (map = mask->masks.map[i]; map; map = zero_rightmost_1bit(map)) { - int ofs = raw_ctz(map) + i * 32; - - hash = mhash_add(hash, miniflow_get(flow, ofs) & *p); + if (*p) { + int ofs = raw_ctz(map) + i * 32; + hash = mhash_add(hash, miniflow_get(flow, ofs) & *p); + } p++; } } @@ -1332,21 +1392,23 @@ uint32_t flow_hash_in_minimask(const struct flow *flow, const struct minimask *mask, uint32_t basis) { - const uint32_t *flow_u32 = (const uint32_t *) flow; + const uint32_t *flow_u32; const uint32_t *p = mask->masks.values; uint32_t hash; int i; hash = basis; + flow_u32 = (const uint32_t *) flow; for (i = 0; i < MINI_N_MAPS; i++) { uint32_t map; for (map = mask->masks.map[i]; map; map = zero_rightmost_1bit(map)) { - int ofs = raw_ctz(map) + i * 32; - - hash = mhash_add(hash, flow_u32[ofs] & *p); + if (*p) { + hash = mhash_add(hash, flow_u32[raw_ctz(map)] & *p); + } p++; } + flow_u32 += 32; } return mhash_finish(hash, (p - mask->masks.values) * 4); @@ -1487,7 +1549,17 @@ bool minimask_is_catchall(const struct minimask *mask_) { const struct miniflow *mask = &mask_->masks; + const uint32_t *p = mask->values; + int i; - BUILD_ASSERT(MINI_N_MAPS == 2); - return !(mask->map[0] | mask->map[1]); + for (i = 0; i < MINI_N_MAPS; i++) { + uint32_t map; + + for (map = mask->map[i]; map; map = zero_rightmost_1bit(map)) { + if (*p++) { + return false; + } + } + } + return true; } diff --git a/lib/flow.h b/lib/flow.h index 75d95e8ec..0c448ded4 100644 --- a/lib/flow.h +++ b/lib/flow.h @@ -291,7 +291,7 @@ bool flow_equal_except(const struct flow *a, const struct flow *b, * * The 'map' member holds one bit for each uint32_t in a "struct flow". Each * 0-bit indicates that the corresponding uint32_t is zero, each 1-bit that it - * is nonzero. + * *may* be nonzero. * * 'values' points to the start of an array that has one element for each 1-bit * in 'map'. The least-numbered 1-bit is in values[0], the next 1-bit is in @@ -309,9 +309,9 @@ bool flow_equal_except(const struct flow *a, const struct flow *b, * that makes sense. So far that's only proved useful for * minimask_combine(), but the principle works elsewhere. * - * The implementation maintains and depends on the invariant that every element - * in 'values' is nonzero; that is, wherever a 1-bit appears in 'map', the - * corresponding element of 'values' must be nonzero. + * Elements in 'values' are allowed to be zero. This is useful for "struct + * minimatch", for which ensuring that the miniflow and minimask members have + * same 'map' allows optimization . */ struct miniflow { uint32_t *values; @@ -320,6 +320,8 @@ struct miniflow { }; void miniflow_init(struct miniflow *, const struct flow *); +void miniflow_init_with_minimask(struct miniflow *, const struct flow *, + const struct minimask *); void miniflow_clone(struct miniflow *, const struct miniflow *); void miniflow_move(struct miniflow *dst, struct miniflow *); void miniflow_destroy(struct miniflow *); diff --git a/lib/match.c b/lib/match.c index 03413fa5c..ba10b17b3 100644 --- a/lib/match.c +++ b/lib/match.c @@ -1091,8 +1091,8 @@ match_print(const struct match *match) void minimatch_init(struct minimatch *dst, const struct match *src) { - miniflow_init(&dst->flow, &src->flow); minimask_init(&dst->mask, &src->wc); + miniflow_init_with_minimask(&dst->flow, &src->flow, &dst->mask); } /* Initializes 'dst' as a copy of 'src'. The caller must eventually free 'dst' @@ -1145,6 +1145,35 @@ minimatch_hash(const struct minimatch *match, uint32_t basis) return miniflow_hash(&match->flow, minimask_hash(&match->mask, basis)); } +/* Returns true if 'target' satisifies 'match', that is, if each bit for which + * 'match' specifies a particular value has the correct value in 'target'. + * + * This function is equivalent to miniflow_equal_flow_in_minimask(&match->flow, + * target, &match->mask) but it is faster because of the invariant that + * match->flow.map and match->mask.map are the same. */ +bool +minimatch_matches_flow(const struct minimatch *match, + const struct flow *target) +{ + const uint32_t *target_u32 = (const uint32_t *) target; + const uint32_t *flowp = match->flow.values; + const uint32_t *maskp = match->mask.masks.values; + int i; + + for (i = 0; i < MINI_N_MAPS; i++) { + uint32_t map; + + for (map = match->flow.map[i]; map; map = zero_rightmost_1bit(map)) { + if ((*flowp++ ^ target_u32[raw_ctz(map)]) & *maskp++) { + return false; + } + } + target_u32 += 32; + } + + return true; +} + /* Appends a string representation of 'match' to 's'. If 'priority' is * different from OFP_DEFAULT_PRIORITY, includes it in 's'. */ void diff --git a/lib/match.h b/lib/match.h index 7b104ee12..48c8aa244 100644 --- a/lib/match.h +++ b/lib/match.h @@ -132,13 +132,15 @@ void match_print(const struct match *); /* A sparse representation of a "struct match". * - * This has the same invariant as "struct match", that is, a 1-bit in the - * 'flow' must correspond to a 1-bit in 'mask'. + * There are two invariants: * - * The invariants for the underlying miniflow and minimask are also maintained, - * which means that 'flow' and 'mask' can have different 'map's. In - * particular, if the match checks that a given 32-bit field has value 0, then - * 'map' will have a 1-bit in 'mask' but a 0-bit in 'flow' for that field. */ + * - The same invariant as "struct match", that is, a 1-bit in the 'flow' + * must correspond to a 1-bit in 'mask'. + * + * - 'flow' and 'mask' have the same 'map'. This implies that 'flow' and + * 'mask' have the same part of "struct flow" at the same offset into + * 'values', which makes minimatch_matches_flow() faster. + */ struct minimatch { struct miniflow flow; struct minimask mask; @@ -154,6 +156,8 @@ void minimatch_expand(const struct minimatch *, struct match *); bool minimatch_equal(const struct minimatch *a, const struct minimatch *b); uint32_t minimatch_hash(const struct minimatch *, uint32_t basis); +bool minimatch_matches_flow(const struct minimatch *, const struct flow *); + void minimatch_format(const struct minimatch *, struct ds *, unsigned int priority); char *minimatch_to_string(const struct minimatch *, unsigned int priority); -- 2.43.0