[ovs-dev] [PATCH v2] lib/flow: Skip minimask value checks.
Jarno Rajahalme
jrajahalme at nicira.com
Thu Dec 19 21:02:42 UTC 2013
We allow zero 'values' in a miniflow for it to have the same map
as the corresponding minimask. Minimasks themselves never have
zero data values, though. Document this and optimize the code
accordingly.
v2:
- Made miniflow_get_map_in_range() to return data offset instead of
a pointer via the last parameter.
- Simplified minimatch_hash_in_range() by removing pointer arithmetic.
Signed-off-by: Jarno Rajahalme <jrajahalme at nicira.com>
---
lib/flow.c | 38 +++++++++++++++-----------------------
lib/flow.h | 15 +++++++++++----
lib/match.c | 21 +++++++++++----------
3 files changed, 37 insertions(+), 37 deletions(-)
diff --git a/lib/flow.c b/lib/flow.c
index 13d0aa5..f1d2cad 100644
--- a/lib/flow.c
+++ b/lib/flow.c
@@ -725,24 +725,22 @@ flow_wildcards_fold_minimask(struct flow_wildcards *wc,
flow_union_with_miniflow(&wc->masks, &mask->masks);
}
-inline uint64_t
+uint64_t
miniflow_get_map_in_range(const struct miniflow *miniflow,
- uint8_t start, uint8_t end, const uint32_t **data)
+ uint8_t start, uint8_t end, unsigned int *offset)
{
uint64_t map = miniflow->map;
- uint32_t *p = miniflow->values;
+ *offset = 0;
if (start > 0) {
uint64_t msk = (UINT64_C(1) << start) - 1; /* 'start' LSBs set */
- p += count_1bits(map & msk); /* Skip to start. */
+ *offset = count_1bits(map & msk);
map &= ~msk;
}
if (end < FLOW_U32S) {
uint64_t msk = (UINT64_C(1) << end) - 1; /* 'end' LSBs set */
map &= msk;
}
-
- *data = p;
return map;
}
@@ -754,8 +752,10 @@ flow_wildcards_fold_minimask_range(struct flow_wildcards *wc,
uint8_t start, uint8_t end)
{
uint32_t *dst_u32 = (uint32_t *)&wc->masks;
- const uint32_t *p;
- uint64_t map = miniflow_get_map_in_range(&mask->masks, start, end, &p);
+ unsigned int offset;
+ uint64_t map = miniflow_get_map_in_range(&mask->masks, start, end,
+ &offset);
+ const uint32_t *p = mask->masks.values + offset;
for (; map; map = zero_rightmost_1bit(map)) {
dst_u32[raw_ctz(map)] |= *p++;
@@ -1516,11 +1516,7 @@ miniflow_hash_in_minimask(const struct miniflow *flow,
hash = basis;
for (map = mask->masks.map; map; map = zero_rightmost_1bit(map)) {
- if (*p) {
- int ofs = raw_ctz(map);
- hash = mhash_add(hash, miniflow_get(flow, ofs) & *p);
- }
- p++;
+ hash = mhash_add(hash, miniflow_get(flow, raw_ctz(map)) & *p++);
}
return mhash_finish(hash, (p - mask->masks.values) * 4);
@@ -1542,10 +1538,7 @@ flow_hash_in_minimask(const struct flow *flow, const struct minimask *mask,
hash = basis;
for (map = mask->masks.map; map; map = zero_rightmost_1bit(map)) {
- if (*p) {
- hash = mhash_add(hash, flow_u32[raw_ctz(map)] & *p);
- }
- p++;
+ hash = mhash_add(hash, flow_u32[raw_ctz(map)] & *p++);
}
return mhash_finish(hash, (p - mask->masks.values) * 4);
@@ -1562,15 +1555,14 @@ flow_hash_in_minimask_range(const struct flow *flow,
uint8_t start, uint8_t end, uint32_t *basis)
{
const uint32_t *flow_u32 = (const uint32_t *)flow;
- const uint32_t *p;
- uint64_t map = miniflow_get_map_in_range(&mask->masks, start, end, &p);
+ unsigned int offset;
+ uint64_t map = miniflow_get_map_in_range(&mask->masks, start, end,
+ &offset);
+ const uint32_t *p = mask->masks.values + offset;
uint32_t hash = *basis;
for (; map; map = zero_rightmost_1bit(map)) {
- if (*p) {
- hash = mhash_add(hash, flow_u32[raw_ctz(map)] & *p);
- }
- p++;
+ hash = mhash_add(hash, flow_u32[raw_ctz(map)] & *p++);
}
*basis = hash; /* Allow continuation from the unfinished value. */
diff --git a/lib/flow.h b/lib/flow.h
index a828b66..9e8549d 100644
--- a/lib/flow.h
+++ b/lib/flow.h
@@ -362,7 +362,9 @@ BUILD_ASSERT_DECL(FLOW_U32S <= 64);
*
* 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 .
+ * same 'map' allows optimization. This allowance applies only to a miniflow
+ * that is not a mask. That is, a minimask may NOT have zero elements in
+ * its 'values'.
*/
struct miniflow {
uint64_t map;
@@ -393,14 +395,19 @@ bool miniflow_equal_flow_in_minimask(const struct miniflow *a,
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);
-uint64_t miniflow_get_map_in_range(const struct miniflow *, uint8_t start,
- uint8_t end, const uint32_t **data);
+uint64_t miniflow_get_map_in_range(const struct miniflow *miniflow,
+ uint8_t start, uint8_t end,
+ unsigned int *offset);
+
/* Compressed flow wildcards. */
/* A sparse representation of a "struct flow_wildcards".
*
- * See the large comment on struct miniflow for details. */
+ * See the large comment on struct miniflow for details.
+ *
+ * Note: While miniflow can have zero data for a 1-bit in the map,
+ * a minimask may not! We rely on this in the implementation. */
struct minimask {
struct miniflow masks;
};
diff --git a/lib/match.c b/lib/match.c
index 9e5da13..cc18a6a 100644
--- a/lib/match.c
+++ b/lib/match.c
@@ -1184,20 +1184,21 @@ uint32_t
minimatch_hash_range(const struct minimatch *match, uint8_t start, uint8_t end,
uint32_t *basis)
{
- const uint32_t *p;
- uint64_t map = miniflow_get_map_in_range(&match->mask.masks, start, end,
- &p);
- const ptrdiff_t df = match->mask.masks.values - match->flow.values;
+ unsigned int offset;
+ const uint32_t *p, *q;
uint32_t hash = *basis;
+ int n, i;
- for (; map; map = zero_rightmost_1bit(map)) {
- if (*p) {
- hash = mhash_add(hash, *(p - df) & *p);
- }
- p++;
+ n = count_1bits(miniflow_get_map_in_range(&match->mask.masks, start, end,
+ &offset));
+ q = match->mask.masks.values + offset;
+ p = match->flow.values + offset;
+
+ for (i = 0; i < n; i++) {
+ hash = mhash_add(hash, p[i] & q[i]);
}
*basis = hash; /* Allow continuation from the unfinished value. */
- return mhash_finish(hash, (p - match->mask.masks.values) * 4);
+ return mhash_finish(hash, (offset + n) * 4);
}
/* Appends a string representation of 'match' to 's'. If 'priority' is
--
1.7.10.4
More information about the dev
mailing list