On Wed, Mar 27, 2013 at 12:14:52PM -0700, Andy Zhou wrote:
> 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)
I added this comment:
/* 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. */
> > +{
> > + 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];
> > + }
> > + }
> > +}
...
> > +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?
OK. I applied the following incremental:
@@ -1012,11 +1020,7 @@ 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];
- }
+ memcpy(dst->map, mask->masks.map, sizeof dst->map);
miniflow_init__(dst, src, miniflow_n_values(dst));
}
> This is just a question: Why miniflow_hash skips zero values, while
> flow_hash does not?
The "high bit" for miniflow_hash() is that it should be faster to hash
only the words in the map (usually only a few) than to hash every
word, even the ones that are zero (that's a lot of words).
Maybe you are asking why miniflow_hash() bothers to skip the words
that appear in the map but are zero. This is so that miniflows that
represent identical data hash to the same value, even if one of the
miniflows has a few spurious 1-bits in its map. Maybe this is not
necessary (I am not certain that any code depends on it).
flow_hash() doesn't skip zeros because it needs to look at every word
in any case and I'm not sure that skipping zeros would speed it up.
Maybe it would; I have not measured.
> > @@ -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.
'flow' and 'mask' might not have the same map, so I am not sure that
we could make it faster. That is in fact the point of the new
function minimatch_matches_flow(): it knows that the flow and the mask
in the minimatch have the same form, so it can avoid the additional
miniflow_get().
Full revised patch below.
Thanks,
Ben.
--8<--------------------------cut here-------------------------->8--
From: Ben Pfaff <b...@nicira.com>
Date: Wed, 6 Feb 2013 16:13:19 -0800
Subject: [PATCH] match: New function minimatch_matches_flow().
Signed-off-by: Ben Pfaff <b...@nicira.com>
---
lib/classifier.c | 3 +-
lib/flow.c | 128 ++++++++++++++++++++++++++++++++++++++++++------------
lib/flow.h | 10 +++--
lib/match.c | 31 +++++++++++++-
lib/match.h | 18 +++++---
5 files changed, 148 insertions(+), 42 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..ff8fe8c 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,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;
@@ -986,16 +1011,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'
@@ -1090,16 +1116,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 +1204,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
@@ -1183,9 +1242,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++;
}
}
@@ -1202,21 +1262,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 +1411,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.2.5
_______________________________________________
dev mailing list
dev@openvswitch.org
http://openvswitch.org/mailman/listinfo/dev
