tests/test-classifier.c used to include lib/classifier.c to gain access to the internal data structures and some utility functions. This was confusing, so this patch splits the relevant groups of classifier internal definations to a new file (lib/classifier-private.h), which is included by both lib/classifier.c and tests/test-classifier.c. Other use of the new file is discouraged.
Signed-off-by: Jarno Rajahalme <[email protected]> --- lib/automake.mk | 1 + lib/classifier-private.h | 279 ++++++++++++++++++++++++++++++++++++++++++++++ lib/classifier.c | 256 +----------------------------------------- tests/test-classifier.c | 24 ++-- 4 files changed, 292 insertions(+), 268 deletions(-) create mode 100644 lib/classifier-private.h diff --git a/lib/automake.mk b/lib/automake.mk index b618f8f..2cda9bd 100644 --- a/lib/automake.mk +++ b/lib/automake.mk @@ -33,6 +33,7 @@ lib_libopenvswitch_la_SOURCES = \ lib/cfm.h \ lib/classifier.c \ lib/classifier.h \ + lib/classifier-private.h \ lib/cmap.c \ lib/cmap.h \ lib/command-line.c \ diff --git a/lib/classifier-private.h b/lib/classifier-private.h new file mode 100644 index 0000000..10d29a5 --- /dev/null +++ b/lib/classifier-private.h @@ -0,0 +1,279 @@ +/* + * Copyright (c) 2014 Nicira, Inc. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at: + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#ifndef CLASSIFIER_PRIVATE_H +#define CLASSIFIER_PRIVATE_H 1 + +#include "flow.h" +#include "hash.h" +#include "cmap.h" +#include "list.h" +#include "tag.h" + +/* Classifier internal definitions, subject to change at any time. */ + +/* A set of rules that all have the same fields wildcarded. */ +struct cls_subtable { + /* The fields are only used by writers and iterators. */ + struct cmap_node cmap_node; /* Within struct classifier 'subtables_map'. */ + + /* The fields are only used by writers. */ + int n_rules OVS_GUARDED; /* Number of rules, including + * duplicates. */ + unsigned int max_priority OVS_GUARDED; /* Max priority of any rule in + * the subtable. */ + unsigned int max_count OVS_GUARDED; /* Count of max_priority rules. */ + + /* These fields are accessed by readers who care about wildcarding. */ + tag_type tag; /* Tag generated from mask for partitioning (const). */ + uint8_t n_indices; /* How many indices to use (const). */ + uint8_t index_ofs[CLS_MAX_INDICES]; /* u32 segment boundaries (const). */ + unsigned int trie_plen[CLS_MAX_TRIES]; /* Trie prefix length in 'mask' + * (runtime configurable). */ + int ports_mask_len; /* (const) */ + struct cmap indices[CLS_MAX_INDICES]; /* Staged lookup indices. */ + rcu_trie_ptr ports_trie; /* NULL if none. */ + + /* These fields are accessed by all readers. */ + struct cmap rules; /* Contains "struct cls_rule"s. */ + struct minimask mask; /* Wildcards for fields (const). */ + /* 'mask' must be the last field. */ +}; + +/* Associates a metadata value (that is, a value of the OpenFlow 1.1+ metadata + * field) with tags for the "cls_subtable"s that contain rules that match that + * metadata value. */ +struct cls_partition { + struct cmap_node cmap_node; /* In struct classifier's 'partitions' map. */ + ovs_be64 metadata; /* metadata value for this partition. */ + tag_type tags; /* OR of each flow's cls_subtable tag. */ + struct tag_tracker tracker OVS_GUARDED; /* Tracks the bits in 'tags'. */ +}; + +/* Internal representation of a rule in a "struct cls_subtable". */ +struct cls_match { + /* Accessed only by writers and iterators. */ + struct list list OVS_GUARDED; /* List of identical, lower-priority rules. */ + + /* Accessed only by writers. */ + struct cls_partition *partition OVS_GUARDED; + + /* Accessed by readers interested in wildcarding. */ + unsigned int priority; /* Larger numbers are higher priorities. */ + struct cmap_node index_nodes[CLS_MAX_INDICES]; /* Within subtable's + * 'indices'. */ + /* Accessed by all readers. */ + struct cmap_node cmap_node; /* Within struct cls_subtable 'rules'. */ + struct cls_rule *cls_rule; + struct miniflow flow; /* Matching rule. Mask is in the subtable. */ + /* 'flow' must be the last field. */ +}; + +/* A longest-prefix match tree. */ +struct trie_node { + uint32_t prefix; /* Prefix bits for this node, MSB first. */ + uint8_t n_bits; /* Never zero, except for the root node. */ + unsigned int n_rules; /* Number of rules that have this prefix. */ + rcu_trie_ptr edges[2]; /* Both NULL if leaf. */ +}; + +/* Max bits per node. Must fit in struct trie_node's 'prefix'. + * Also tested with 16, 8, and 5 to stress the implementation. */ +#define TRIE_PREFIX_BITS 32 + +/* 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 *mask_values = miniflow_get_u32_values(&mask->masks); + const uint32_t *flow_u32 = (const uint32_t *)flow; + const uint32_t *p = mask_values; + uint32_t hash; + uint64_t map; + + hash = basis; + for (map = mask->masks.map; map; map = zero_rightmost_1bit(map)) { + hash = hash_add(hash, flow_u32[raw_ctz(map)] & *p++); + } + + return hash_finish(hash, (p - mask_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 *mask_values = miniflow_get_u32_values(&mask->masks); + const uint32_t *p = mask_values; + uint32_t hash = basis; + uint32_t flow_u32; + + MINIFLOW_FOR_EACH_IN_MAP(flow_u32, flow, mask->masks.map) { + hash = hash_add(hash, flow_u32 & *p++); + } + + return hash_finish(hash, (p - mask_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 *mask_values = miniflow_get_u32_values(&mask->masks); + 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_values + offset; + uint32_t hash = *basis; + + for (; map; map = zero_rightmost_1bit(map)) { + hash = hash_add(hash, flow_u32[raw_ctz(map)] & *p++); + } + + *basis = hash; /* Allow continuation from the unfinished value. */ + return hash_finish(hash, (p - mask_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 = miniflow_get_u32_values(&mask->masks) + 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 *values = miniflow_get_u32_values(flow); + const uint32_t *p = 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 = hash_add(hash, *p); + hash_map |= rightmost_1bit(map); + } + p++; + } + hash = hash_add(hash, hash_map); + hash = hash_add(hash, hash_map >> 32); + + return hash_finish(hash, p - 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 = miniflow_get_u32_values(&match->mask.masks) + offset; + p = miniflow_get_u32_values(&match->flow) + offset; + + for (i = 0; i < n; i++) { + hash = hash_add(hash, p[i] & q[i]); + } + *basis = hash; /* Allow continuation from the unfinished value. */ + return hash_finish(hash, (offset + n) * 4); +} + +#endif diff --git a/lib/classifier.c b/lib/classifier.c index 8dc89d9..05e7b2b 100644 --- a/lib/classifier.c +++ b/lib/classifier.c @@ -16,18 +16,14 @@ #include <config.h> #include "classifier.h" +#include "classifier-private.h" #include <errno.h> #include <netinet/in.h> #include "byte-order.h" #include "dynamic-string.h" -#include "flow.h" -#include "hash.h" -#include "cmap.h" -#include "list.h" #include "odp-util.h" #include "ofp-util.h" #include "packets.h" -#include "tag.h" #include "util.h" #include "vlog.h" @@ -39,63 +35,6 @@ struct trie_ctx; #define TP_PORTS_OFS32 (offsetof(struct flow, tp_src) / 4) BUILD_ASSERT_DECL(TP_PORTS_OFS32 == offsetof(struct flow, tp_dst) / 4); -/* A set of rules that all have the same fields wildcarded. */ -struct cls_subtable { - /* The fields are only used by writers and iterators. */ - struct cmap_node cmap_node; /* Within struct classifier 'subtables_map'. */ - - /* The fields are only used by writers. */ - int n_rules OVS_GUARDED; /* Number of rules, including - * duplicates. */ - unsigned int max_priority OVS_GUARDED; /* Max priority of any rule in - * the subtable. */ - unsigned int max_count OVS_GUARDED; /* Count of max_priority rules. */ - - /* These fields are accessed by readers who care about wildcarding. */ - tag_type tag; /* Tag generated from mask for partitioning (const). */ - uint8_t n_indices; /* How many indices to use (const). */ - uint8_t index_ofs[CLS_MAX_INDICES]; /* u32 segment boundaries (const). */ - unsigned int trie_plen[CLS_MAX_TRIES]; /* Trie prefix length in 'mask' - * (runtime configurable). */ - int ports_mask_len; /* (const) */ - struct cmap indices[CLS_MAX_INDICES]; /* Staged lookup indices. */ - rcu_trie_ptr ports_trie; /* NULL if none. */ - - /* These fields are accessed by all readers. */ - struct cmap rules; /* Contains "struct cls_rule"s. */ - struct minimask mask; /* Wildcards for fields (const). */ - /* 'mask' must be the last field. */ -}; - -/* Associates a metadata value (that is, a value of the OpenFlow 1.1+ metadata - * field) with tags for the "cls_subtable"s that contain rules that match that - * metadata value. */ -struct cls_partition { - struct cmap_node cmap_node; /* In struct classifier's 'partitions' map. */ - ovs_be64 metadata; /* metadata value for this partition. */ - tag_type tags; /* OR of each flow's cls_subtable tag. */ - struct tag_tracker tracker OVS_GUARDED; /* Tracks the bits in 'tags'. */ -}; - -/* Internal representation of a rule in a "struct cls_subtable". */ -struct cls_match { - /* Accessed only by writers and iterators. */ - struct list list OVS_GUARDED; /* List of identical, lower-priority rules. */ - - /* Accessed only by writers. */ - struct cls_partition *partition OVS_GUARDED; - - /* Accessed by readers interested in wildcarding. */ - unsigned int priority; /* Larger numbers are higher priorities. */ - struct cmap_node index_nodes[CLS_MAX_INDICES]; /* Within subtable's - * 'indices'. */ - /* Accessed by all readers. */ - struct cmap_node cmap_node; /* Within struct cls_subtable 'rules'. */ - struct cls_rule *cls_rule; - struct miniflow flow; /* Matching rule. Mask is in the subtable. */ - /* 'flow' must be the last field. */ -}; - static struct cls_match * cls_match_alloc(struct cls_rule *rule) { @@ -167,189 +106,6 @@ static void mask_set_prefix_bits(struct flow_wildcards *, uint8_t be32ofs, static bool mask_prefix_bits_set(const struct flow_wildcards *, uint8_t be32ofs, unsigned int n_bits); -/* 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 *mask_values = miniflow_get_u32_values(&mask->masks); - const uint32_t *flow_u32 = (const uint32_t *)flow; - const uint32_t *p = mask_values; - uint32_t hash; - uint64_t map; - - hash = basis; - for (map = mask->masks.map; map; map = zero_rightmost_1bit(map)) { - hash = hash_add(hash, flow_u32[raw_ctz(map)] & *p++); - } - - return hash_finish(hash, (p - mask_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 *mask_values = miniflow_get_u32_values(&mask->masks); - const uint32_t *p = mask_values; - uint32_t hash = basis; - uint32_t flow_u32; - - MINIFLOW_FOR_EACH_IN_MAP(flow_u32, flow, mask->masks.map) { - hash = hash_add(hash, flow_u32 & *p++); - } - - return hash_finish(hash, (p - mask_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 *mask_values = miniflow_get_u32_values(&mask->masks); - 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_values + offset; - uint32_t hash = *basis; - - for (; map; map = zero_rightmost_1bit(map)) { - hash = hash_add(hash, flow_u32[raw_ctz(map)] & *p++); - } - - *basis = hash; /* Allow continuation from the unfinished value. */ - return hash_finish(hash, (p - mask_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 = miniflow_get_u32_values(&mask->masks) + 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 *values = miniflow_get_u32_values(flow); - const uint32_t *p = 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 = hash_add(hash, *p); - hash_map |= rightmost_1bit(map); - } - p++; - } - hash = hash_add(hash, hash_map); - hash = hash_add(hash, hash_map >> 32); - - return hash_finish(hash, p - 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 = miniflow_get_u32_values(&match->mask.masks) + offset; - p = miniflow_get_u32_values(&match->flow) + offset; - - for (i = 0; i < n; i++) { - hash = hash_add(hash, p[i] & q[i]); - } - *basis = hash; /* Allow continuation from the unfinished value. */ - return hash_finish(hash, (offset + n) * 4); -} - - /* cls_rule. */ /* Initializes 'rule' to match packets specified by 'match' at the given @@ -1707,16 +1463,6 @@ next_rule_in_list(struct cls_match *rule) } /* A longest-prefix match tree. */ -struct trie_node { - uint32_t prefix; /* Prefix bits for this node, MSB first. */ - uint8_t n_bits; /* Never zero, except for the root node. */ - unsigned int n_rules; /* Number of rules that have this prefix. */ - rcu_trie_ptr edges[2]; /* Both NULL if leaf. */ -}; - -/* Max bits per node. Must fit in struct trie_node's 'prefix'. - * Also tested with 16, 8, and 5 to stress the implementation. */ -#define TRIE_PREFIX_BITS 32 /* Return at least 'plen' bits of the 'prefix', starting at bit offset 'ofs'. * Prefixes are in the network byte order, and the offset 0 corresponds to diff --git a/tests/test-classifier.c b/tests/test-classifier.c index 1726171..f4e65bf 100644 --- a/tests/test-classifier.c +++ b/tests/test-classifier.c @@ -26,26 +26,24 @@ */ #include <config.h> +#undef NDEBUG +#include <assert.h> #include <errno.h> #include <limits.h> #include "byte-order.h" +#include "classifier.h" +#include "classifier-private.h" #include "command-line.h" #include "flow.h" #include "ofp-util.h" #include "packets.h" #include "random.h" #include "unaligned.h" +#include "util.h" #include "ovstest.h" -#undef NDEBUG -#include <assert.h> - -/* 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 \ +#define CLS_FIELDS \ /* struct flow all-caps */ \ /* member name name */ \ /* ----------- -------- */ \ @@ -472,8 +470,8 @@ pvector_verify(const struct pvector *pvec) PVECTOR_FOR_EACH (ptr, pvec) { priority = cursor__.vector[cursor__.entry_idx].priority; if (priority > prev_priority) { - VLOG_ABORT("Priority vector is out of order (%u > %u)", - priority, prev_priority); + ovs_abort(0, "Priority vector is out of order (%u > %u)", + priority, prev_priority); } prev_priority = priority; } @@ -534,14 +532,14 @@ check_tables(const struct classifier *cls, int n_tables, int n_rules, PVECTOR_FOR_EACH (iter, &cls->subtables) { if (iter == table) { if (found) { - VLOG_ABORT("Subtable %p duplicated in 'subtables'.", - table); + ovs_abort(0, "Subtable %p duplicated in 'subtables'.", + table); } found = true; } } if (!found) { - VLOG_ABORT("Subtable %p not found from 'subtables'.", table); + ovs_abort(0, "Subtable %p not found from 'subtables'.", table); } assert(!cmap_is_empty(&table->rules)); -- 1.7.10.4 _______________________________________________ dev mailing list [email protected] http://openvswitch.org/mailman/listinfo/dev
