From: Jarno Rajahalme Date: Fri, 18 Apr 2014 15:26:56 +0000 (-0700) Subject: classifier: Support miniflow as a key. X-Git-Tag: sliver-openvswitch-2.2.90-1~3^2~116 X-Git-Url: http://git.onelab.eu/?p=sliver-openvswitch.git;a=commitdiff_plain;h=2abf78ff5562b9550558c52b2a16431de71a3378 classifier: Support miniflow as a key. Support struct miniflow as a key for datapath flow lookup. The new classifier interface classifier_lookup_miniflow_first() takes a miniflow as a key and stops at the first match with no regard to flow prioritites. This works only if the classifier has no conflicting rules (as is the case with the userspace datapath classifier). Signed-off-by: Jarno Rajahalme Reviewed-by: YAMAMOTO Takashi --- diff --git a/lib/classifier.c b/lib/classifier.c index 55ca5eabe..31a0e8b36 100644 --- a/lib/classifier.c +++ b/lib/classifier.c @@ -566,6 +566,68 @@ classifier_lookup(const struct classifier *cls, const struct flow *flow, return best; } +/* Returns true if 'target' satisifies 'match', that is, if each bit for which + * 'match' specifies a particular value has the correct value in 'target'. */ +static bool +minimatch_matches_miniflow(const struct minimatch *match, + const struct miniflow *target) +{ + const uint32_t *flowp = (const uint32_t *)match->flow.values; + const uint32_t *maskp = (const uint32_t *)match->mask.masks.values; + uint32_t target_u32; + + MINIFLOW_FOR_EACH_IN_MAP(target_u32, target, match->mask.masks.map) { + if ((*flowp++ ^ target_u32) & *maskp++) { + return false; + } + } + + return true; +} + +static inline struct cls_rule * +find_match_miniflow(const struct cls_subtable *subtable, + const struct miniflow *flow, + uint32_t hash) +{ + struct cls_rule *rule; + + HMAP_FOR_EACH_WITH_HASH (rule, hmap_node, hash, &subtable->rules) { + if (minimatch_matches_miniflow(&rule->match, flow)) { + return rule; + } + } + + return NULL; +} + +/* Finds and returns the highest-priority rule in 'cls' that matches + * 'miniflow'. Returns a null pointer if no rules in 'cls' match 'flow'. + * If multiple rules of equal priority match 'flow', returns one arbitrarily. + * + * This function is optimized for the userspace datapath, which only ever has + * one priority value for it's flows! + */ +struct cls_rule *classifier_lookup_miniflow_first(const struct classifier *cls, + const struct miniflow *flow) +{ + struct cls_subtable *subtable; + + LIST_FOR_EACH (subtable, list_node, &cls->subtables_priority) { + struct cls_rule *rule; + + rule = find_match_miniflow(subtable, flow, + miniflow_hash_in_minimask(flow, + &subtable->mask, + 0)); + if (rule) { + return rule; + } + } + + return NULL; +} + /* Finds and returns a rule in 'cls' with exactly the same priority and * matching criteria as 'target'. Returns a null pointer if 'cls' doesn't * contain an exact match. */ diff --git a/lib/classifier.h b/lib/classifier.h index c3c1c3bd2..9022faba8 100644 --- a/lib/classifier.h +++ b/lib/classifier.h @@ -346,6 +346,9 @@ struct cls_rule *classifier_lookup(const struct classifier *cls, const struct flow *, struct flow_wildcards *) OVS_REQ_RDLOCK(cls->rwlock); +struct cls_rule *classifier_lookup_miniflow_first(const struct classifier *cls, + const struct miniflow *) + OVS_REQ_RDLOCK(cls->rwlock); bool classifier_rule_overlaps(const struct classifier *cls, const struct cls_rule *) OVS_REQ_RDLOCK(cls->rwlock); diff --git a/lib/flow.c b/lib/flow.c index 03d86aeb8..8319dde94 100644 --- a/lib/flow.c +++ b/lib/flow.c @@ -1813,28 +1813,10 @@ 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; - uint64_t map; - const uint32_t *fp = flow->values; - uint64_t fmap = flow->map; - uint64_t rm1bit; - - hash = basis; - - for (map = mask->masks.map; map; map -= rm1bit) { - uint32_t flow_u32 = 0; - - rm1bit = rightmost_1bit(map); - if (fmap & rm1bit) { - uint64_t trash = fmap & (rm1bit - 1); + uint32_t hash = basis; + uint32_t flow_u32; - /* Skip data in 'flow' that is of no interest, once. */ - if (trash) { - fp += count_1bits(trash); - fmap -= trash; - } - flow_u32 = *fp; - } + MINIFLOW_FOR_EACH_IN_MAP(flow_u32, flow, mask->masks.map) { hash = mhash_add(hash, flow_u32 & *p++); } diff --git a/lib/flow.h b/lib/flow.h index c834cb554..e8066aa03 100644 --- a/lib/flow.h +++ b/lib/flow.h @@ -402,6 +402,32 @@ void miniflow_destroy(struct miniflow *); void miniflow_expand(const struct miniflow *, struct flow *); +static inline uint32_t +mf_get_next_in_map(uint64_t *fmap, uint64_t rm1bit, const uint32_t **fp, + uint32_t *value) +{ + *value = 0; + if (*fmap & rm1bit) { + uint64_t trash = *fmap & (rm1bit - 1); + + if (trash) { + *fmap -= trash; + *fp += count_1bits(trash); + } + *value = **fp; + } + return rm1bit != 0; +} + +/* Iterate through all miniflow u32 values specified by the 'MAP'. + * This works as the first statement in a block.*/ +#define MINIFLOW_FOR_EACH_IN_MAP(VALUE, FLOW, MAP) \ + const uint32_t *fp_ = (FLOW)->values; \ + uint64_t rm1bit_, fmap_, map_; \ + for (fmap_ = (FLOW)->map, map_ = (MAP), rm1bit_ = rightmost_1bit(map_); \ + mf_get_next_in_map(&fmap_, rm1bit_, &fp_, &(VALUE)); \ + map_ -= rm1bit_, rm1bit_ = rightmost_1bit(map_)) + /* These accessors use byte offsets, which are assumed to be compile-time * constants. */ static inline uint8_t miniflow_get_u8(const struct miniflow *,