From 83916319a914a4111cabf52a115368ebf5320123 Mon Sep 17 00:00:00 2001 From: Jarno Rajahalme Date: Fri, 20 Dec 2013 08:16:31 -0800 Subject: [PATCH] lib/flow: Skip minimask value checks. 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 Acked-by: Ben Pfaff --- 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 13d0aa559..f1d2cad29 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 a828b6645..9e8549d45 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 9e5da136e..cc18a6af9 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 -- 2.20.1