On Sat, Apr 19, 2014 at 3:42 AM, Jarno Rajahalme <jrajaha...@nicira.com> wrote:
> Change the classifier to allocate variable sized miniflows and
> minimasks in cls_match and cls_subtable, respectively. Do not
> duplicate the mask in cls_rule any more.
>
> miniflow_clone and miniflow_move can now take variably sized miniflows
> as source. The destination is assumed to be regularly sized miniflow.
>
> Inlining miniflow and mask values reduces memory indirection and helps
> reduce cache misses.
>
> Signed-off-by: Jarno Rajahalme <jrajaha...@nicira.com>
> ---
> lib/classifier.c | 82
> +++++++++++++++++++++++++++++++++++++++---------------
> lib/flow.c | 55 +++++++++++++++++++++++++++++++-----
> lib/flow.h | 30 ++++++++++++++++++--
> 3 files changed, 134 insertions(+), 33 deletions(-)
>
> diff --git a/lib/classifier.c b/lib/classifier.c
> index 75befad..1198a76 100644
> --- a/lib/classifier.c
> +++ b/lib/classifier.c
> @@ -40,7 +40,6 @@ struct cls_trie {
>
> struct cls_subtable_entry {
> struct cls_subtable *subtable;
> - const uint32_t *mask_values;
> tag_type tag;
> unsigned int max_priority;
> };
> @@ -72,7 +71,6 @@ struct cls_subtable {
> struct hmap_node hmap_node; /* Within struct cls_classifier 'subtables'
> * hmap. */
> struct hmap rules; /* Contains "struct cls_rule"s. */
> - struct minimask mask; /* Wildcards for fields. */
> int n_rules; /* Number of rules, including duplicates. */
> unsigned int max_priority; /* Max priority of any rule in the subtable.
> */
> unsigned int max_count; /* Count of max_priority rules. */
> @@ -81,6 +79,8 @@ struct cls_subtable {
> uint8_t index_ofs[CLS_MAX_INDICES]; /* u32 flow segment boundaries. */
> struct hindex indices[CLS_MAX_INDICES]; /* Staged lookup indices. */
> unsigned int trie_plen[CLS_MAX_TRIES]; /* Trie prefix length in 'mask'.
> */
> + struct minimask mask; /* Wildcards for fields. */
> + /* 'mask' must be the last field. */
> };
>
> /* Associates a metadata value (that is, a value of the OpenFlow 1.1+
> metadata
> @@ -103,16 +103,21 @@ struct cls_match {
> unsigned int priority; /* Larger numbers are higher priorities. */
> struct cls_partition *partition;
> struct list list; /* List of identical, lower-priority rules.
> */
> - struct minimatch match; /* Matching 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)
> {
> - struct cls_match *cls_match = xmalloc(sizeof *cls_match);
> + int count = count_1bits(rule->match.flow.map);
> +
> + struct cls_match *cls_match
> + = xmalloc(sizeof *cls_match - sizeof cls_match->flow.inline_values
> + + MINIFLOW_VALUES_SIZE(count));
Would it lead to a potential array access violation problem when
'sizeof cls_match->flow.inline_values' is bigger than
'MINIFLOW_VALUES_SIZE(count)'?
>
> cls_match->cls_rule = rule;
> - minimatch_clone(&cls_match->match, &rule->match);
> + miniflow_clone_inline(&cls_match->flow, &rule->match.flow, count);
> cls_match->priority = rule->priority;
> rule->cls_match = cls_match;
>
> @@ -875,7 +880,6 @@ static inline void
> lookahead_subtable(const struct cls_subtable_entry *subtables)
> {
> ovs_prefetch_range(subtables->subtable, sizeof *subtables->subtable);
> - ovs_prefetch_range(subtables->mask_values, 1);
> }
>
> /* Finds and returns the highest-priority rule in 'cls' that matches 'flow'.
> @@ -969,16 +973,19 @@ classifier_lookup(const struct classifier *cls_, const
> struct flow *flow,
> }
>
> /* Returns true if 'target' satisifies 'match', that is, if each bit for
> which
> - * 'match' specifies a particular value has the correct value in 'target'. */
> + * 'match' specifies a particular value has the correct value in 'target'.
> + *
> + * 'flow' and 'mask' have the same mask! */
> static bool
> -minimatch_matches_miniflow(const struct minimatch *match,
> - const struct miniflow *target)
> +miniflow_and_mask_matches_miniflow(const struct miniflow *flow,
> + const struct minimask *mask,
> + const struct miniflow *target)
> {
> - const uint32_t *flowp = miniflow_get_u32_values(&match->flow);
> - const uint32_t *maskp = miniflow_get_u32_values(&match->mask.masks);
> + const uint32_t *flowp = miniflow_get_u32_values(flow);
> + const uint32_t *maskp = miniflow_get_u32_values(&mask->masks);
> uint32_t target_u32;
>
> - MINIFLOW_FOR_EACH_IN_MAP(target_u32, target, match->mask.masks.map) {
> + MINIFLOW_FOR_EACH_IN_MAP(target_u32, target, mask->masks.map) {
> if ((*flowp++ ^ target_u32) & *maskp++) {
> return false;
> }
> @@ -995,7 +1002,8 @@ find_match_miniflow(const struct cls_subtable *subtable,
> struct cls_match *rule;
>
> HMAP_FOR_EACH_WITH_HASH (rule, hmap_node, hash, &subtable->rules) {
> - if (minimatch_matches_miniflow(&rule->match, flow)) {
> + if (miniflow_and_mask_matches_miniflow(&rule->flow, &subtable->mask,
> + flow)) {
> return rule;
> }
> }
> @@ -1113,7 +1121,7 @@ classifier_rule_overlaps(const struct classifier *cls_,
> }
> if (rule->priority == target->priority
> && miniflow_equal_in_minimask(&target->match.flow,
> - &rule->match.flow, &mask))
> {
> + &rule->flow, &mask)) {
> return true;
> }
> }
> @@ -1171,7 +1179,7 @@ static bool
> rule_matches(const struct cls_match *rule, const struct cls_rule *target)
> {
> return (!target
> - || miniflow_equal_in_minimask(&rule->match.flow,
> + || miniflow_equal_in_minimask(&rule->flow,
> &target->match.flow,
> &target->match.mask));
> }
> @@ -1285,10 +1293,12 @@ insert_subtable(struct cls_classifier *cls, const
> struct minimask *mask)
> struct flow_wildcards old, new;
> uint8_t prev;
> struct cls_subtable_entry elem;
> + int count = count_1bits(mask->masks.map);
>
> - subtable = xzalloc(sizeof *subtable);
> + subtable = xzalloc(sizeof *subtable - sizeof mask->masks.inline_values
> + + MINIFLOW_VALUES_SIZE(count));
> hmap_init(&subtable->rules);
> - minimask_clone(&subtable->mask, mask);
> + miniflow_clone_inline(&subtable->mask.masks, &mask->masks, count);
>
> /* Init indices for segmented lookup, if any. */
> flow_wildcards_init_catchall(&new);
> @@ -1329,7 +1339,6 @@ insert_subtable(struct cls_classifier *cls, const
> struct minimask *mask)
>
> hmap_insert(&cls->subtables, &subtable->hmap_node, hash);
> elem.subtable = subtable;
> - elem.mask_values = miniflow_get_values(&subtable->mask.masks);
> elem.tag = subtable->tag;
> elem.max_priority = subtable->max_priority;
> cls_subtable_cache_push_back(&cls->subtables_priority, elem);
> @@ -1525,6 +1534,31 @@ check_tries(struct trie_ctx trie_ctx[CLS_MAX_TRIES],
> unsigned int n_tries,
> return false;
> }
>
> +/* Returns true if 'target' satisifies 'flow'/'mask', that is, if each bit
> + * for which 'flow', for which 'mask' has a bit set, specifies a particular
> + * value has the correct value in 'target'.
> + *
> + * This function is equivalent to miniflow_equal_flow_in_minimask(flow,
> + * target, mask) but it is faster because of the invariant that
> + * flow->map and mask->masks.map are the same. */
> +static inline bool
> +miniflow_and_mask_matches_flow(const struct miniflow *flow,
> + const struct minimask *mask,
> + const struct flow *target)
> +{
> + const uint32_t *flowp = miniflow_get_u32_values(flow);
> + const uint32_t *maskp = miniflow_get_u32_values(&mask->masks);
> + uint32_t target_u32;
> +
> + FLOW_FOR_EACH_IN_MAP(target_u32, target, mask->masks.map) {
> + if ((*flowp++ ^ target_u32) & *maskp++) {
> + return false;
> + }
> + }
> +
> + return true;
> +}
> +
> static inline struct cls_match *
> find_match(const struct cls_subtable *subtable, const struct flow *flow,
> uint32_t hash)
> @@ -1532,7 +1566,8 @@ find_match(const struct cls_subtable *subtable, const
> struct flow *flow,
> struct cls_match *rule;
>
> HMAP_FOR_EACH_WITH_HASH (rule, hmap_node, hash, &subtable->rules) {
> - if (minimatch_matches_flow(&rule->match, flow)) {
> + if (miniflow_and_mask_matches_flow(&rule->flow, &subtable->mask,
> + flow)) {
> return rule;
> }
> }
> @@ -1580,8 +1615,8 @@ find_match_wc(const struct cls_subtable *subtable,
> const struct flow *flow,
> * not match, then we know that we will never get a match, but we do
> * not yet know how many wildcards we need to fold into 'wc' so we
> * continue iterating through indices to find that out. (We won't
> - * waste time calling minimatch_matches_flow() again because we've
> set
> - * 'rule' nonnull.)
> + * waste time calling miniflow_and_mask_matches_flow() again because
> + * we've set 'rule' nonnull.)
> *
> * This check shows a measurable benefit with non-trivial flow
> tables.
> *
> @@ -1589,7 +1624,8 @@ find_match_wc(const struct cls_subtable *subtable,
> const struct flow *flow,
> * optimization. */
> if (!inode->s && !rule) {
> ASSIGN_CONTAINER(rule, inode - i, index_nodes);
> - if (minimatch_matches_flow(&rule->match, flow)) {
> + if (miniflow_and_mask_matches_flow(&rule->flow, &subtable->mask,
> + flow)) {
> goto out;
> }
> }
> @@ -1629,7 +1665,7 @@ find_equal(struct cls_subtable *subtable, const struct
> miniflow *flow,
> struct cls_match *head;
>
> HMAP_FOR_EACH_WITH_HASH (head, hmap_node, hash, &subtable->rules) {
> - if (miniflow_equal(&head->match.flow, flow)) {
> + if (miniflow_equal(&head->flow, flow)) {
> return head;
> }
> }
> diff --git a/lib/flow.c b/lib/flow.c
> index 8e8e67e..1f65001 100644
> --- a/lib/flow.c
> +++ b/lib/flow.c
> @@ -1581,13 +1581,15 @@ miniflow_n_values(const struct miniflow *flow)
> static uint32_t *
> miniflow_alloc_values(struct miniflow *flow, int n)
> {
> - if (n <= sizeof flow->inline_values / sizeof(uint32_t)) {
> + int size = MINIFLOW_VALUES_SIZE(n);
> +
> + if (size <= sizeof flow->inline_values) {
> flow->values_inline = true;
> return flow->inline_values;
> } else {
> COVERAGE_INC(miniflow_malloc);
> flow->values_inline = false;
> - flow->offline_values = xmalloc(n * sizeof(uint32_t));
> + flow->offline_values = xmalloc(size);
> return flow->offline_values;
> }
> }
> @@ -1655,18 +1657,57 @@ miniflow_init_with_minimask(struct miniflow *dst,
> const struct flow *src,
> void
> miniflow_clone(struct miniflow *dst, const struct miniflow *src)
> {
> - int n = miniflow_n_values(src);
> + int size = MINIFLOW_VALUES_SIZE(miniflow_n_values(src));
> + uint32_t *values;
> +
> dst->map = src->map;
> - memcpy(miniflow_alloc_values(dst, n), miniflow_get_values(src),
> - n * sizeof(uint32_t));
> + if (size <= sizeof dst->inline_values) {
> + dst->values_inline = true;
> + values = dst->inline_values;
> + } else {
> + dst->values_inline = false;
> + COVERAGE_INC(miniflow_malloc);
> + dst->offline_values = xmalloc(size);
> + values = dst->offline_values;
> + }
> + memcpy(values, miniflow_get_values(src), size);
> +}
> +
> +/* Initializes 'dst' as a copy of 'src'. The caller must have allocated
> + * 'dst' to have inline space all data in 'src'. */
> +void
> +miniflow_clone_inline(struct miniflow *dst, const struct miniflow *src,
> + size_t n_values)
> +{
> + dst->values_inline = true;
> + dst->map = src->map;
> + memcpy(dst->inline_values, miniflow_get_values(src),
> + MINIFLOW_VALUES_SIZE(n_values));
> }
>
> /* Initializes 'dst' with the data in 'src', destroying 'src'.
> - * The caller must eventually free 'dst' with miniflow_destroy(). */
> + * The caller must eventually free 'dst' with miniflow_destroy().
> + * 'dst' must be regularly sized miniflow, but 'src' can have
> + * larger than default inline values. */
> void
> miniflow_move(struct miniflow *dst, struct miniflow *src)
> {
> - *dst = *src;
> + int size = MINIFLOW_VALUES_SIZE(miniflow_n_values(src));
> +
> + dst->map = src->map;
> + if (size <= sizeof dst->inline_values) {
> + dst->values_inline = true;
> + memcpy(dst->inline_values, miniflow_get_values(src), size);
> + miniflow_destroy(src);
> + } else if (src->values_inline) {
> + dst->values_inline = false;
> + COVERAGE_INC(miniflow_malloc);
> + dst->offline_values = xmalloc(size);
> + memcpy(dst->offline_values, src->inline_values, size);
> + } else {
> + dst->values_inline = false;
> + dst->offline_values = src->offline_values;
> + }
> }
>
> /* Frees any memory owned by 'flow'. Does not free the storage in which
> 'flow'
> diff --git a/lib/flow.h b/lib/flow.h
> index c508e1e..324997f 100644
> --- a/lib/flow.h
> +++ b/lib/flow.h
> @@ -358,14 +358,18 @@ struct miniflow {
> };
> };
>
> +#define MINIFLOW_VALUES_SIZE(COUNT) ((COUNT) * sizeof(uint32_t))
> +
> static inline uint32_t *miniflow_values(struct miniflow *mf)
> {
> - return mf->values_inline ? mf->inline_values : mf->offline_values;
> + return OVS_LIKELY(mf->values_inline)
> + ? mf->inline_values : mf->offline_values;
> }
>
> static inline const uint32_t *miniflow_get_values(const struct miniflow *mf)
> {
> - return mf->values_inline ? mf->inline_values : mf->offline_values;
> + return OVS_LIKELY(mf->values_inline)
> + ? mf->inline_values : mf->offline_values;
> }
>
> static inline const uint32_t *miniflow_get_u32_values(const struct miniflow
> *mf)
> @@ -400,11 +404,31 @@ 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_clone_inline(struct miniflow *, const struct miniflow *,
> + size_t n_values);
> void miniflow_move(struct miniflow *dst, struct miniflow *);
> void miniflow_destroy(struct miniflow *);
>
> void miniflow_expand(const struct miniflow *, struct flow *);
>
> +static inline uint32_t
> +flow_get_next_in_map(const struct flow *flow, uint64_t map, uint32_t *value)
> +{
> + if (map) {
> + *value = ((const uint32_t *)flow)[raw_ctz(map)];
> + return true;
> + }
> + return false;
> +}
> +
> +/* Iterate through all flow u32 values specified by 'MAP'.
> + * This works as the first statement in a block.*/
> +#define FLOW_FOR_EACH_IN_MAP(VALUE, FLOW, MAP) \
> + uint64_t map_; \
> + for (map_ = (MAP); \
> + flow_get_next_in_map(FLOW, map_, &(VALUE)); \
> + map_ = zero_rightmost_1bit(map_))
> +
> #define FLOW_U32_SIZE(FIELD) \
> DIV_ROUND_UP(sizeof(((struct flow *)0)->FIELD), sizeof(uint32_t))
>
> @@ -429,7 +453,7 @@ mf_get_next_in_map(uint64_t *fmap, uint64_t rm1bit, const
> uint32_t **fp,
> return rm1bit != 0;
> }
>
> -/* Iterate through all miniflow u32 values specified by the 'MAP'.
> +/* Iterate through all miniflow u32 values specified by 'MAP'.
> * This works as the first statement in a block.*/
> #define MINIFLOW_FOR_EACH_IN_MAP(VALUE, FLOW, MAP) \
> const uint32_t *fp_ = miniflow_get_u32_values(FLOW); \
> --
> 1.7.10.4
>
> _______________________________________________
> dev mailing list
> dev@openvswitch.org
> http://openvswitch.org/mailman/listinfo/dev
_______________________________________________
dev mailing list
dev@openvswitch.org
http://openvswitch.org/mailman/listinfo/dev
