From 3d91d9094dcf49c210bd4ebae4bd1e0cea9defce Mon Sep 17 00:00:00 2001 From: Jarno Rajahalme Date: Tue, 29 Apr 2014 15:50:38 -0700 Subject: [PATCH] lib: Inline functions used in classifier_lookup. This helps about 1% in TCP_CRR performance test. However, this also helps by clearly showing the classifier_lookup() cost in perf reports as one item. This also cleans up the flow/match APIs from functionality only used by the classifier, making is more straightforward to evolve them later. Signed-off-by: Jarno Rajahalme Acked-by: Ethan Jackson --- lib/classifier.c | 181 +++++++++++++++++++++++++++++++++++++++- lib/flow.c | 155 ---------------------------------- lib/flow.h | 37 ++++---- lib/hindex.c | 13 --- lib/hindex.h | 13 ++- lib/match.c | 33 -------- lib/match.h | 4 - tests/test-classifier.c | 6 +- 8 files changed, 212 insertions(+), 230 deletions(-) diff --git a/lib/classifier.c b/lib/classifier.c index 31a0e8b36..8ab1f9c3d 100644 --- a/lib/classifier.c +++ b/lib/classifier.c @@ -79,6 +79,185 @@ static void mask_set_prefix_bits(struct flow_wildcards *, uint8_t be32ofs, unsigned int nbits); static bool mask_prefix_bits_set(const struct flow_wildcards *, uint8_t be32ofs, unsigned int nbits); + +/* flow/miniflow/minimask/minimatch utilities. + * These are only used by the classifier, so place them here to allow + * for better optimization. */ + +static inline uint64_t +miniflow_get_map_in_range(const struct miniflow *miniflow, + uint8_t start, uint8_t end, unsigned int *offset) +{ + uint64_t map = miniflow->map; + *offset = 0; + + if (start > 0) { + uint64_t msk = (UINT64_C(1) << start) - 1; /* 'start' LSBs set */ + *offset = count_1bits(map & msk); + map &= ~msk; + } + if (end < FLOW_U32S) { + uint64_t msk = (UINT64_C(1) << end) - 1; /* 'end' LSBs set */ + map &= msk; + } + return map; +} + +/* Returns a hash value for the bits of 'flow' where there are 1-bits in + * 'mask', given 'basis'. + * + * The hash values returned by this function are the same as those returned by + * miniflow_hash_in_minimask(), only the form of the arguments differ. */ +static inline 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 *p = mask->masks.values; + uint32_t hash; + uint64_t map; + + hash = basis; + for (map = mask->masks.map; map; map = zero_rightmost_1bit(map)) { + hash = mhash_add(hash, flow_u32[raw_ctz(map)] & *p++); + } + + return mhash_finish(hash, (p - mask->masks.values) * 4); +} + +/* Returns a hash value for the bits of 'flow' where there are 1-bits in + * 'mask', given 'basis'. + * + * The hash values returned by this function are the same as those returned by + * flow_hash_in_minimask(), only the form of the arguments differ. */ +static inline uint32_t +miniflow_hash_in_minimask(const struct miniflow *flow, + const struct minimask *mask, uint32_t basis) +{ + const uint32_t *p = mask->masks.values; + uint32_t hash = basis; + uint32_t flow_u32; + + MINIFLOW_FOR_EACH_IN_MAP(flow_u32, flow, mask->masks.map) { + hash = mhash_add(hash, flow_u32 & *p++); + } + + return mhash_finish(hash, (p - mask->masks.values) * 4); +} + +/* Returns a hash value for the bits of range [start, end) in 'flow', + * where there are 1-bits in 'mask', given 'hash'. + * + * The hash values returned by this function are the same as those returned by + * minimatch_hash_range(), only the form of the arguments differ. */ +static inline uint32_t +flow_hash_in_minimask_range(const struct flow *flow, + const struct minimask *mask, + uint8_t start, uint8_t end, uint32_t *basis) +{ + const uint32_t *flow_u32 = (const uint32_t *)flow; + 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)) { + hash = mhash_add(hash, flow_u32[raw_ctz(map)] & *p++); + } + + *basis = hash; /* Allow continuation from the unfinished value. */ + return mhash_finish(hash, (p - mask->masks.values) * 4); +} + +/* Fold minimask 'mask''s wildcard mask into 'wc's wildcard mask. */ +static inline void +flow_wildcards_fold_minimask(struct flow_wildcards *wc, + const struct minimask *mask) +{ + flow_union_with_miniflow(&wc->masks, &mask->masks); +} + +/* Fold minimask 'mask''s wildcard mask into 'wc's wildcard mask + * in range [start, end). */ +static inline void +flow_wildcards_fold_minimask_range(struct flow_wildcards *wc, + const struct minimask *mask, + uint8_t start, uint8_t end) +{ + uint32_t *dst_u32 = (uint32_t *)&wc->masks; + 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++; + } +} + +/* Returns a hash value for 'flow', given 'basis'. */ +static inline uint32_t +miniflow_hash(const struct miniflow *flow, uint32_t basis) +{ + const uint32_t *p = flow->values; + uint32_t hash = basis; + uint64_t hash_map = 0; + uint64_t map; + + for (map = flow->map; 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); + hash = mhash_add(hash, hash_map >> 32); + + return mhash_finish(hash, p - flow->values); +} + +/* Returns a hash value for 'mask', given 'basis'. */ +static inline uint32_t +minimask_hash(const struct minimask *mask, uint32_t basis) +{ + return miniflow_hash(&mask->masks, basis); +} + +/* Returns a hash value for 'match', given 'basis'. */ +static inline uint32_t +minimatch_hash(const struct minimatch *match, uint32_t basis) +{ + return miniflow_hash(&match->flow, minimask_hash(&match->mask, basis)); +} + +/* Returns a hash value for the bits of range [start, end) in 'minimatch', + * given 'basis'. + * + * The hash values returned by this function are the same as those returned by + * flow_hash_in_minimask_range(), only the form of the arguments differ. */ +static inline uint32_t +minimatch_hash_range(const struct minimatch *match, uint8_t start, uint8_t end, + uint32_t *basis) +{ + unsigned int offset; + const uint32_t *p, *q; + uint32_t hash = *basis; + int n, i; + + 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, (offset + n) * 4); +} + /* cls_rule. */ @@ -1565,7 +1744,7 @@ minimask_get_prefix_len(const struct minimask *minimask, static const ovs_be32 * minimatch_get_prefix(const struct minimatch *match, const struct mf_field *mf) { - return (OVS_FORCE const ovs_be32 *)match->flow.values + + return match->flow.values + count_1bits(match->flow.map & ((UINT64_C(1) << mf->flow_be32ofs) - 1)); } diff --git a/lib/flow.c b/lib/flow.c index 9700d29f2..f7704fb47 100644 --- a/lib/flow.c +++ b/lib/flow.c @@ -823,65 +823,6 @@ flow_wildcards_or(struct flow_wildcards *dst, } } -/* Perform a bitwise OR of miniflow 'src' flow data with the equivalent - * fields in 'dst', storing the result in 'dst'. */ -static void -flow_union_with_miniflow(struct flow *dst, const struct miniflow *src) -{ - uint32_t *dst_u32 = (uint32_t *) dst; - const uint32_t *p = src->values; - uint64_t map; - - for (map = src->map; map; map = zero_rightmost_1bit(map)) { - dst_u32[raw_ctz(map)] |= *p++; - } -} - -/* Fold minimask 'mask''s wildcard mask into 'wc's wildcard mask. */ -void -flow_wildcards_fold_minimask(struct flow_wildcards *wc, - const struct minimask *mask) -{ - flow_union_with_miniflow(&wc->masks, &mask->masks); -} - -uint64_t -miniflow_get_map_in_range(const struct miniflow *miniflow, - uint8_t start, uint8_t end, unsigned int *offset) -{ - uint64_t map = miniflow->map; - *offset = 0; - - if (start > 0) { - uint64_t msk = (UINT64_C(1) << start) - 1; /* 'start' LSBs set */ - *offset = count_1bits(map & msk); - map &= ~msk; - } - if (end < FLOW_U32S) { - uint64_t msk = (UINT64_C(1) << end) - 1; /* 'end' LSBs set */ - map &= msk; - } - return map; -} - -/* Fold minimask 'mask''s wildcard mask into 'wc's wildcard mask - * in range [start, end). */ -void -flow_wildcards_fold_minimask_range(struct flow_wildcards *wc, - const struct minimask *mask, - uint8_t start, uint8_t end) -{ - uint32_t *dst_u32 = (uint32_t *)&wc->masks; - 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++; - } -} - /* Returns a hash of the wildcards in 'wc'. */ uint32_t flow_wildcards_hash(const struct flow_wildcards *wc, uint32_t basis) @@ -1834,95 +1775,6 @@ miniflow_equal_flow_in_minimask(const struct miniflow *a, const struct flow *b, return true; } -/* Returns a hash value for 'flow', given 'basis'. */ -uint32_t -miniflow_hash(const struct miniflow *flow, uint32_t basis) -{ - const uint32_t *p = flow->values; - uint32_t hash = basis; - uint64_t hash_map = 0; - uint64_t map; - - for (map = flow->map; 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); - hash = mhash_add(hash, hash_map >> 32); - - return mhash_finish(hash, p - flow->values); -} - -/* Returns a hash value for the bits of 'flow' where there are 1-bits in - * 'mask', given 'basis'. - * - * The hash values returned by this function are the same as those returned by - * flow_hash_in_minimask(), only the form of the arguments differ. */ -uint32_t -miniflow_hash_in_minimask(const struct miniflow *flow, - const struct minimask *mask, uint32_t basis) -{ - const uint32_t *p = mask->masks.values; - uint32_t hash = basis; - uint32_t flow_u32; - - MINIFLOW_FOR_EACH_IN_MAP(flow_u32, flow, mask->masks.map) { - hash = mhash_add(hash, flow_u32 & *p++); - } - - return mhash_finish(hash, (p - mask->masks.values) * 4); -} - -/* Returns a hash value for the bits of 'flow' where there are 1-bits in - * 'mask', given 'basis'. - * - * The hash values returned by this function are the same as those returned by - * miniflow_hash_in_minimask(), only the form of the arguments differ. */ -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 *p = mask->masks.values; - uint32_t hash; - uint64_t map; - - hash = basis; - for (map = mask->masks.map; map; map = zero_rightmost_1bit(map)) { - hash = mhash_add(hash, flow_u32[raw_ctz(map)] & *p++); - } - - return mhash_finish(hash, (p - mask->masks.values) * 4); -} - -/* Returns a hash value for the bits of range [start, end) in 'flow', - * where there are 1-bits in 'mask', given 'hash'. - * - * The hash values returned by this function are the same as those returned by - * minimatch_hash_range(), only the form of the arguments differ. */ -uint32_t -flow_hash_in_minimask_range(const struct flow *flow, - const struct minimask *mask, - uint8_t start, uint8_t end, uint32_t *basis) -{ - const uint32_t *flow_u32 = (const uint32_t *)flow; - 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)) { - hash = mhash_add(hash, flow_u32[raw_ctz(map)] & *p++); - } - - *basis = hash; /* Allow continuation from the unfinished value. */ - return mhash_finish(hash, (p - mask->masks.values) * 4); -} - /* Initializes 'dst' as a copy of 'src'. The caller must eventually free 'dst' * with minimask_destroy(). */ @@ -2007,13 +1859,6 @@ minimask_equal(const struct minimask *a, const struct minimask *b) return miniflow_equal(&a->masks, &b->masks); } -/* Returns a hash value for 'mask', given 'basis'. */ -uint32_t -minimask_hash(const struct minimask *mask, uint32_t basis) -{ - return miniflow_hash(&mask->masks, basis); -} - /* Returns true if at least one bit is wildcarded in 'a_' but not in 'b_', * false otherwise. */ bool diff --git a/lib/flow.h b/lib/flow.h index 02a5e187d..f0e3a3481 100644 --- a/lib/flow.h +++ b/lib/flow.h @@ -271,13 +271,6 @@ hash_odp_port(odp_port_t odp_port) { return hash_int(odp_to_u32(odp_port), 0); } - -uint32_t flow_hash_in_minimask(const struct flow *, const struct minimask *, - uint32_t basis); -uint32_t flow_hash_in_minimask_range(const struct flow *, - const struct minimask *, - uint8_t start, uint8_t end, - uint32_t *basis); /* Wildcards for a flow. * @@ -305,13 +298,6 @@ void flow_wildcards_or(struct flow_wildcards *dst, const struct flow_wildcards *src2); bool flow_wildcards_has_extra(const struct flow_wildcards *, const struct flow_wildcards *); - -void flow_wildcards_fold_minimask(struct flow_wildcards *, - const struct minimask *); -void flow_wildcards_fold_minimask_range(struct flow_wildcards *, - const struct minimask *, - uint8_t start, uint8_t end); - uint32_t flow_wildcards_hash(const struct flow_wildcards *, uint32_t basis); bool flow_wildcards_equal(const struct flow_wildcards *, const struct flow_wildcards *); @@ -467,12 +453,6 @@ bool miniflow_equal_in_minimask(const struct miniflow *a, bool miniflow_equal_flow_in_minimask(const struct miniflow *a, const struct flow *b, const struct minimask *); -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 *miniflow, - uint8_t start, uint8_t end, - unsigned int *offset); uint32_t miniflow_hash_5tuple(const struct miniflow *flow, uint32_t basis); @@ -503,10 +483,9 @@ static inline uint16_t minimask_get_vid_mask(const struct minimask *); static inline ovs_be64 minimask_get_metadata_mask(const struct minimask *); bool minimask_equal(const struct minimask *a, const struct minimask *b); -uint32_t minimask_hash(const struct minimask *, uint32_t basis); - bool minimask_has_extra(const struct minimask *, const struct minimask *); bool minimask_is_catchall(const struct minimask *); + /* Returns the VID within the vlan_tci member of the "struct flow" represented @@ -565,6 +544,20 @@ minimask_get_metadata_mask(const struct minimask *mask) return miniflow_get_metadata(&mask->masks); } +/* Perform a bitwise OR of miniflow 'src' flow data with the equivalent + * fields in 'dst', storing the result in 'dst'. */ +static inline void +flow_union_with_miniflow(struct flow *dst, const struct miniflow *src) +{ + uint32_t *dst_u32 = (uint32_t *) dst; + const uint32_t *p = (uint32_t *)src->values; + uint64_t map; + + for (map = src->map; map; map = zero_rightmost_1bit(map)) { + dst_u32[raw_ctz(map)] |= *p++; + } +} + static inline struct pkt_metadata pkt_metadata_from_flow(const struct flow *flow) { diff --git a/lib/hindex.c b/lib/hindex.c index fd4199ae1..260649bf8 100644 --- a/lib/hindex.c +++ b/lib/hindex.c @@ -274,19 +274,6 @@ hindex_calc_mask(size_t capacity) return mask; } -/* Returns the head node in 'hindex' with the given 'hash', or a null pointer - * if no nodes have that hash value. */ -struct hindex_node * -hindex_node_with_hash(const struct hindex *hindex, size_t hash) -{ - struct hindex_node *node = hindex->buckets[hash & hindex->mask]; - - while (node && node->hash != hash) { - node = node->d; - } - return node; -} - /* Returns the head node in 'hindex' with the given 'hash'. 'hindex' must * contain a head node with the given hash. */ static struct hindex_node * diff --git a/lib/hindex.h b/lib/hindex.h index fb6b6d2bd..631fd487d 100644 --- a/lib/hindex.h +++ b/lib/hindex.h @@ -132,7 +132,18 @@ void hindex_remove(struct hindex *, struct hindex_node *); NODE != OBJECT_CONTAINING(NULL, NODE, MEMBER); \ ASSIGN_CONTAINER(NODE, (NODE)->MEMBER.s, MEMBER)) -struct hindex_node *hindex_node_with_hash(const struct hindex *, size_t hash); +/* Returns the head node in 'hindex' with the given 'hash', or a null pointer + * if no nodes have that hash value. */ +static inline struct hindex_node * +hindex_node_with_hash(const struct hindex *hindex, size_t hash) +{ + struct hindex_node *node = hindex->buckets[hash & hindex->mask]; + + while (node && node->hash != hash) { + node = node->d; + } + return node; +} /* Iteration. */ diff --git a/lib/match.c b/lib/match.c index 87d6a60ab..5bbd2f02b 100644 --- a/lib/match.c +++ b/lib/match.c @@ -1244,13 +1244,6 @@ minimatch_equal(const struct minimatch *a, const struct minimatch *b) && minimask_equal(&a->mask, &b->mask)); } -/* Returns a hash value for 'match', given 'basis'. */ -uint32_t -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'. * @@ -1275,32 +1268,6 @@ minimatch_matches_flow(const struct minimatch *match, return true; } -/* Returns a hash value for the bits of range [start, end) in 'minimatch', - * given 'basis'. - * - * The hash values returned by this function are the same as those returned by - * flow_hash_in_minimask_range(), only the form of the arguments differ. */ -uint32_t -minimatch_hash_range(const struct minimatch *match, uint8_t start, uint8_t end, - uint32_t *basis) -{ - unsigned int offset; - const uint32_t *p, *q; - uint32_t hash = *basis; - int n, i; - - 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, (offset + n) * 4); -} - /* 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 2422fb1b5..1246b2029 100644 --- a/lib/match.h +++ b/lib/match.h @@ -167,13 +167,9 @@ void minimatch_destroy(struct minimatch *); 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 *); -uint32_t minimatch_hash_range(const struct minimatch *, - uint8_t start, uint8_t end, uint32_t *basis); - void minimatch_format(const struct minimatch *, struct ds *, unsigned int priority); char *minimatch_to_string(const struct minimatch *, unsigned int priority); diff --git a/tests/test-classifier.c b/tests/test-classifier.c index e9e253a9b..48eb8de5b 100644 --- a/tests/test-classifier.c +++ b/tests/test-classifier.c @@ -26,7 +26,6 @@ */ #include -#include "classifier.h" #include #include #include "byte-order.h" @@ -40,6 +39,11 @@ #undef NDEBUG #include +/* We need access to classifier internal definitions to be able to fully + * test them. The alternative would be to expose them all in the classifier + * API. */ +#include "classifier.c" + /* Fields in a rule. */ #define CLS_FIELDS \ /* struct flow all-caps */ \ -- 2.43.0