---------- Forwarded message ----------
From: Andy Zhou <az...@nicira.com>
Date: Wed, Mar 27, 2013 at 12:14 PM
Subject: Re: [ovs-dev] [PATCH 1/3] match: New function
minimatch_matches_flow().
To: Ben Pfaff <b...@nicira.com>
Looks good. A few minor comments in-line:
On Tue, Mar 26, 2013 at 9:32 PM, Ben Pfaff <b...@nicira.com> wrote:
> Signed-off-by: Ben Pfaff <b...@nicira.com>
> ---
> lib/classifier.c | 3 +-
> lib/flow.c | 122
> ++++++++++++++++++++++++++++++++++++++++++------------
> lib/flow.h | 10 +++--
> lib/match.c | 31 +++++++++++++-
> lib/match.h | 18 ++++----
> 5 files changed, 143 insertions(+), 41 deletions(-)
>
> diff --git a/lib/classifier.c b/lib/classifier.c
> index 2d1e50b..b720378 100644
> --- a/lib/classifier.c
> +++ b/lib/classifier.c
> @@ -641,8 +641,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 678b8f0..56675c3 100644
> --- a/lib/flow.c
> +++ b/lib/flow.c
> @@ -1,5 +1,5 @@
> /*
> - * Copyright (c) 2008, 2009, 2010, 2011, 2012 Nicira, Inc.
> + * Copyright (c) 2008, 2009, 2010, 2011, 2012, 2013 Nicira, Inc.
> *
> * Licensed under the Apache License, Version 2.0 (the "License");
> * you may not use this file except in compliance with the License.
> @@ -966,13 +966,30 @@ miniflow_alloc_values(struct miniflow *flow, int n)
> }
> }
>
It would be nice to add a comment about what 'n' is.
> +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;
>
> @@ -986,16 +1003,21 @@ 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)
> +{
> + int i;
> +
> + for (i = 0; i < MINI_N_MAPS; i++) {
> + dst->map[i] = mask->masks.map[i];
> }
>
How about use memcpy() instead for loop above?
> + miniflow_init__(dst, src, miniflow_n_values(dst));
> }
>
> /* Initializes 'dst' as a copy of 'src'. The caller must eventually free
> 'dst'
> @@ -1090,16 +1112,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
> @@ -1159,10 +1200,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++;
>
This is just a question: Why miniflow_hash skips zero values, while
flow_hash does not?
> + }
> + 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
> @@ -1183,9 +1238,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);
>
Is possible to avoid calling miniflow_get() in this case, the needed data
from flow is readily available.
> + }
> p++;
> }
> }
> @@ -1202,21 +1258,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);
> @@ -1349,7 +1407,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 6e169d6..09a472d 100644
> --- a/lib/flow.h
> +++ b/lib/flow.h
> @@ -221,7 +221,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
> @@ -239,9 +239,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;
> @@ -250,6 +250,8 @@ struct miniflow {
> };
>
> void miniflow_init(struct miniflow *, const struct flow *);
> +void miniflow_init_with_minimask(struct miniflow *, const struct flow *,
> + const struct minimask *);
> void miniflow_clone(struct miniflow *, const struct miniflow *);
> void miniflow_destroy(struct miniflow *);
>
> diff --git a/lib/match.c b/lib/match.c
> index 2aa4e89..76c23cf 100644
> --- a/lib/match.c
> +++ b/lib/match.c
> @@ -1087,8 +1087,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'
> @@ -1132,6 +1132,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 d435aa4..926ce60 100644
> --- a/lib/match.h
> +++ b/lib/match.h
> @@ -1,5 +1,5 @@
> /*
> - * Copyright (c) 2009, 2010, 2011, 2012 Nicira, Inc.
> + * Copyright (c) 2009, 2010, 2011, 2012, 2013 Nicira, Inc.
> *
> * Licensed under the Apache License, Version 2.0 (the "License");
> * you may not use this file except in compliance with the License.
> @@ -131,13 +131,15 @@ void match_print(const struct match *);
>
> /* A sparse representation of a "struct match".
> *
> - * This has the same invariant as "struct match", that is, a 1-bit in the
> - * 'flow' must correspond to a 1-bit in 'mask'.
> + * There are two invariants:
> *
> - * The invariants for the underlying miniflow and minimask are also
> maintained,
> - * which means that 'flow' and 'mask' can have different 'map's. In
> - * particular, if the match checks that a given 32-bit field has value 0,
> then
> - * 'map' will have a 1-bit in 'mask' but a 0-bit in 'flow' for that
> field. */
> + * - The same invariant as "struct match", that is, a 1-bit in the
> 'flow'
> + * must correspond to a 1-bit in 'mask'.
> + *
> + * - 'flow' and 'mask' have the same 'map'. This implies that 'flow'
> and
> + * 'mask' have the same part of "struct flow" at the same offset into
> + * 'values', which makes minimatch_matches_flow() faster.
> + */
> struct minimatch {
> struct miniflow flow;
> struct minimask mask;
> @@ -152,6 +154,8 @@ void minimatch_expand(const struct minimatch *, struct
> match *);
> bool minimatch_equal(const struct minimatch *a, const struct minimatch
> *b);
> uint32_t minimatch_hash(const struct minimatch *, uint32_t basis);
>
> +bool minimatch_matches_flow(const struct minimatch *, const struct flow
> *);
> +
> void minimatch_format(const struct minimatch *, struct ds *,
> unsigned int priority);
> char *minimatch_to_string(const struct minimatch *, unsigned int
> priority);
> --
> 1.7.10.4
>
> _______________________________________________
> dev mailing list
> dev@openvswitch.org
> http://openvswitch.org/mailman/listinfo/dev
>
_______________________________________________
dev mailing list
dev@openvswitch.org
http://openvswitch.org/mailman/listinfo/dev
