X-Git-Url: http://git.onelab.eu/?a=blobdiff_plain;f=lib%2Fclassifier.c;h=67b2c280b7a3779f8c27fd86a42f85920c91466e;hb=ec988646afe6aee6a63d6894a3e9b50f715d5941;hp=30a91b755e357f7cc5b13a2c26a3ea8d80bd8d98;hpb=06f81620436881449cb9a2db4f875aa00803f28d;p=sliver-openvswitch.git diff --git a/lib/classifier.c b/lib/classifier.c index 30a91b755..67b2c280b 100644 --- a/lib/classifier.c +++ b/lib/classifier.c @@ -30,18 +30,80 @@ VLOG_DEFINE_THIS_MODULE(classifier); +struct trie_node; + +/* Prefix trie for a 'field' */ +struct cls_trie { + const struct mf_field *field; /* Trie field, or NULL. */ + struct trie_node *root; /* NULL if none. */ +}; + +struct cls_subtable_entry { + struct cls_subtable *subtable; + uint32_t *mask_values; + tag_type tag; + unsigned int max_priority; +}; + +struct cls_subtable_cache { + struct cls_subtable_entry *subtables; + size_t alloc_size; /* Number of allocated elements. */ + size_t size; /* One past last valid array element. */ +}; + +struct cls_classifier { + int n_rules; /* Total number of rules. */ + uint8_t n_flow_segments; + uint8_t flow_segments[CLS_MAX_INDICES]; /* Flow segment boundaries to use + * for staged lookup. */ + struct hmap subtables; /* Contains "struct cls_subtable"s. */ + struct cls_subtable_cache subtables_priority; + struct hmap partitions; /* Contains "struct cls_partition"s. */ + struct cls_trie tries[CLS_MAX_TRIES]; /* Prefix tries. */ + unsigned int n_tries; +}; + +/* A set of rules that all have the same fields wildcarded. */ +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. */ + tag_type tag; /* Tag generated from mask for partitioning. */ + uint8_t n_indices; /* How many indices to use. */ + 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'. */ +}; + +/* 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 hmap_node hmap_node; /* In struct cls_classifier's 'partitions' + * hmap. */ + ovs_be64 metadata; /* metadata value for this partition. */ + tag_type tags; /* OR of each flow's cls_subtable tag. */ + struct tag_tracker tracker; /* Tracks the bits in 'tags'. */ +}; + + + struct trie_ctx; -static struct cls_subtable *find_subtable(const struct classifier *, +static struct cls_subtable *find_subtable(const struct cls_classifier *, const struct minimask *); -static struct cls_subtable *insert_subtable(struct classifier *, +static struct cls_subtable *insert_subtable(struct cls_classifier *, const struct minimask *); -static void destroy_subtable(struct classifier *, struct cls_subtable *); +static void destroy_subtable(struct cls_classifier *, struct cls_subtable *); -static void update_subtables_after_insertion(struct classifier *, +static void update_subtables_after_insertion(struct cls_classifier *, struct cls_subtable *, unsigned int new_priority); -static void update_subtables_after_removal(struct classifier *, +static void update_subtables_after_removal(struct cls_classifier *, struct cls_subtable *, unsigned int del_priority); @@ -51,7 +113,7 @@ static struct cls_rule *find_match_wc(const struct cls_subtable *, struct flow_wildcards *); static struct cls_rule *find_equal(struct cls_subtable *, const struct miniflow *, uint32_t hash); -static struct cls_rule *insert_rule(struct classifier *, +static struct cls_rule *insert_rule(struct cls_classifier *, struct cls_subtable *, struct cls_rule *); /* Iterates RULE over HEAD and all of the cls_rules on HEAD->list. */ @@ -67,7 +129,7 @@ static struct cls_rule *next_rule_in_list(struct cls_rule *); static unsigned int minimask_get_prefix_len(const struct minimask *, const struct mf_field *); -static void trie_init(struct classifier *, int trie_idx, +static void trie_init(struct cls_classifier *, int trie_idx, const struct mf_field *); static unsigned int trie_lookup(const struct cls_trie *, const struct flow *, unsigned int *checkbits); @@ -79,6 +141,262 @@ 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); + +static void +cls_subtable_cache_init(struct cls_subtable_cache *array) +{ + memset(array, 0, sizeof *array); +} + +static void +cls_subtable_cache_destroy(struct cls_subtable_cache *array) +{ + free(array->subtables); + memset(array, 0, sizeof *array); +} + +/* Array insertion. */ +static void +cls_subtable_cache_push_back(struct cls_subtable_cache *array, + struct cls_subtable_entry a) +{ + if (array->size == array->alloc_size) { + array->subtables = x2nrealloc(array->subtables, &array->alloc_size, + sizeof a); + } + + array->subtables[array->size++] = a; +} + +/* Only for rearranging entries in the same cache. */ +static inline void +cls_subtable_cache_splice(struct cls_subtable_entry *to, + struct cls_subtable_entry *start, + struct cls_subtable_entry *end) +{ + if (to > end) { + /* Same as splicing entries to (start) from [end, to). */ + struct cls_subtable_entry *temp = to; + to = start; start = end; end = temp; + } + if (to < start) { + while (start != end) { + struct cls_subtable_entry temp = *start; + + memmove(to + 1, to, (start - to) * sizeof *to); + *to = temp; + start++; + } + } /* Else nothing to be done. */ +} + +/* Array removal. */ +static inline void +cls_subtable_cache_remove(struct cls_subtable_cache *array, + struct cls_subtable_entry *elem) +{ + ssize_t size = (&array->subtables[array->size] + - (elem + 1)) * sizeof *elem; + if (size > 0) { + memmove(elem, elem + 1, size); + } + array->size--; +} + +#define CLS_SUBTABLE_CACHE_FOR_EACH(SUBTABLE, ITER, ARRAY) \ + for (ITER = (ARRAY)->subtables; \ + ITER < &(ARRAY)->subtables[(ARRAY)->size] \ + && OVS_LIKELY(SUBTABLE = ITER->subtable); \ + ++ITER) +#define CLS_SUBTABLE_CACHE_FOR_EACH_CONTINUE(SUBTABLE, ITER, ARRAY) \ + for (++ITER; \ + ITER < &(ARRAY)->subtables[(ARRAY)->size] \ + && OVS_LIKELY(SUBTABLE = ITER->subtable); \ + ++ITER) +#define CLS_SUBTABLE_CACHE_FOR_EACH_REVERSE(SUBTABLE, ITER, ARRAY) \ + for (ITER = &(ARRAY)->subtables[(ARRAY)->size]; \ + ITER > (ARRAY)->subtables \ + && OVS_LIKELY(SUBTABLE = (--ITER)->subtable);) + + +/* 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. */ @@ -170,13 +488,18 @@ cls_rule_is_catchall(const struct cls_rule *rule) /* Initializes 'cls' as a classifier that initially contains no classification * rules. */ void -classifier_init(struct classifier *cls, const uint8_t *flow_segments) +classifier_init(struct classifier *cls_, const uint8_t *flow_segments) { + struct cls_classifier *cls = xmalloc(sizeof *cls); + + fat_rwlock_init(&cls_->rwlock); + + cls_->cls = cls; + cls->n_rules = 0; hmap_init(&cls->subtables); - list_init(&cls->subtables_priority); + cls_subtable_cache_init(&cls->subtables_priority); hmap_init(&cls->partitions); - fat_rwlock_init(&cls->rwlock); cls->n_flow_segments = 0; if (flow_segments) { while (cls->n_flow_segments < CLS_MAX_INDICES @@ -190,13 +513,19 @@ classifier_init(struct classifier *cls, const uint8_t *flow_segments) /* Destroys 'cls'. Rules within 'cls', if any, are not freed; this is the * caller's responsibility. */ void -classifier_destroy(struct classifier *cls) +classifier_destroy(struct classifier *cls_) { - if (cls) { + if (cls_) { + struct cls_classifier *cls = cls_->cls; struct cls_subtable *partition, *next_partition; struct cls_subtable *subtable, *next_subtable; int i; + fat_rwlock_destroy(&cls_->rwlock); + if (!cls) { + return; + } + for (i = 0; i < cls->n_tries; i++) { trie_destroy(cls->tries[i].root); } @@ -213,7 +542,9 @@ classifier_destroy(struct classifier *cls) free(partition); } hmap_destroy(&cls->partitions); - fat_rwlock_destroy(&cls->rwlock); + + cls_subtable_cache_destroy(&cls->subtables_priority); + free(cls); } } @@ -222,10 +553,11 @@ BUILD_ASSERT_DECL(MFF_N_IDS <= 64); /* Set the fields for which prefix lookup should be performed. */ void -classifier_set_prefix_fields(struct classifier *cls, +classifier_set_prefix_fields(struct classifier *cls_, const enum mf_field_id *trie_fields, unsigned int n_fields) { + struct cls_classifier *cls = cls_->cls; uint64_t fields = 0; int i, trie; @@ -260,11 +592,12 @@ classifier_set_prefix_fields(struct classifier *cls, } static void -trie_init(struct classifier *cls, int trie_idx, +trie_init(struct cls_classifier *cls, int trie_idx, const struct mf_field *field) { struct cls_trie *trie = &cls->tries[trie_idx]; struct cls_subtable *subtable; + struct cls_subtable_entry *iter; if (trie_idx < cls->n_tries) { trie_destroy(trie->root); @@ -273,7 +606,7 @@ trie_init(struct classifier *cls, int trie_idx, trie->field = field; /* Add existing rules to the trie. */ - LIST_FOR_EACH (subtable, list_node, &cls->subtables_priority) { + CLS_SUBTABLE_CACHE_FOR_EACH (subtable, iter, &cls->subtables_priority) { unsigned int plen; plen = field ? minimask_get_prefix_len(&subtable->mask, field) : 0; @@ -298,25 +631,26 @@ trie_init(struct classifier *cls, int trie_idx, bool classifier_is_empty(const struct classifier *cls) { - return cls->n_rules == 0; + return cls->cls->n_rules == 0; } /* Returns the number of rules in 'cls'. */ int classifier_count(const struct classifier *cls) { - return cls->n_rules; + return cls->cls->n_rules; } static uint32_t hash_metadata(ovs_be64 metadata_) { uint64_t metadata = (OVS_FORCE uint64_t) metadata_; - return hash_2words(metadata, metadata >> 32); + return hash_uint64(metadata); } static struct cls_partition * -find_partition(const struct classifier *cls, ovs_be64 metadata, uint32_t hash) +find_partition(const struct cls_classifier *cls, ovs_be64 metadata, + uint32_t hash) { struct cls_partition *partition; @@ -330,7 +664,7 @@ find_partition(const struct classifier *cls, ovs_be64 metadata, uint32_t hash) } static struct cls_partition * -create_partition(struct classifier *cls, struct cls_subtable *subtable, +create_partition(struct cls_classifier *cls, struct cls_subtable *subtable, ovs_be64 metadata) { uint32_t hash = hash_metadata(metadata); @@ -360,8 +694,9 @@ create_partition(struct classifier *cls, struct cls_subtable *subtable, * rule, even rules that cannot have any effect because the new rule matches a * superset of their flows and has higher priority. */ struct cls_rule * -classifier_replace(struct classifier *cls, struct cls_rule *rule) +classifier_replace(struct classifier *cls_, struct cls_rule *rule) { + struct cls_classifier *cls = cls_->cls; struct cls_rule *old_rule; struct cls_subtable *subtable; @@ -412,8 +747,9 @@ classifier_insert(struct classifier *cls, struct cls_rule *rule) * 'rule' with cls_rule_destroy(), freeing the memory block in which 'rule' * resides, etc., as necessary. */ void -classifier_remove(struct classifier *cls, struct cls_rule *rule) +classifier_remove(struct classifier *cls_, struct cls_rule *rule) { + struct cls_classifier *cls = cls_->cls; struct cls_partition *partition; struct cls_rule *head; struct cls_subtable *subtable; @@ -484,6 +820,13 @@ trie_ctx_init(struct trie_ctx *ctx, const struct cls_trie *trie) ctx->lookup_done = false; } +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'. * Returns a null pointer if no rules in 'cls' match 'flow'. If multiple rules * of equal priority match 'flow', returns one arbitrarily. @@ -493,15 +836,21 @@ trie_ctx_init(struct trie_ctx *ctx, const struct cls_trie *trie) * earlier, 'wc' should have been initialized (e.g., by * flow_wildcards_init_catchall()). */ struct cls_rule * -classifier_lookup(const struct classifier *cls, const struct flow *flow, +classifier_lookup(const struct classifier *cls_, const struct flow *flow, struct flow_wildcards *wc) { + struct cls_classifier *cls = cls_->cls; const struct cls_partition *partition; - struct cls_subtable *subtable; - struct cls_rule *best; tag_type tags; + struct cls_rule *best; struct trie_ctx trie_ctx[CLS_MAX_TRIES]; int i; + struct cls_subtable_entry *subtables = cls->subtables_priority.subtables; + int n_subtables = cls->subtables_priority.size; + int64_t best_priority = -1; + + /* Prefetch the subtables array. */ + ovs_prefetch_range(subtables, n_subtables * sizeof *subtables); /* Determine 'tags' such that, if 'subtable->tag' doesn't intersect them, * then 'flow' cannot possibly match in 'subtable': @@ -531,48 +880,115 @@ classifier_lookup(const struct classifier *cls, const struct flow *flow, for (i = 0; i < cls->n_tries; i++) { trie_ctx_init(&trie_ctx[i], &cls->tries[i]); } + + /* Prefetch the first subtables. */ + if (n_subtables > 1) { + lookahead_subtable(subtables); + lookahead_subtable(subtables + 1); + } + best = NULL; - LIST_FOR_EACH (subtable, list_node, &cls->subtables_priority) { + for (i = 0; OVS_LIKELY(i < n_subtables); i++) { struct cls_rule *rule; - if (!tag_intersects(tags, subtable->tag)) { + if ((int64_t)subtables[i].max_priority <= best_priority) { + /* Subtables are in descending priority order, + * can not find anything better. */ + break; + } + + /* Prefetch a forthcoming subtable. */ + if (i + 2 < n_subtables) { + lookahead_subtable(&subtables[i + 2]); + } + + if (!tag_intersects(tags, subtables[i].tag)) { continue; } - rule = find_match_wc(subtable, flow, trie_ctx, cls->n_tries, wc); - if (rule) { + rule = find_match_wc(subtables[i].subtable, flow, trie_ctx, + cls->n_tries, wc); + if (rule && (int64_t)rule->priority > best_priority) { + best_priority = (int64_t)rule->priority; best = rule; - LIST_FOR_EACH_CONTINUE (subtable, list_node, - &cls->subtables_priority) { - if (subtable->max_priority <= best->priority) { - /* Subtables are in descending priority order, - * can not find anything better. */ - return best; - } - if (!tag_intersects(tags, subtable->tag)) { - continue; - } - - rule = find_match_wc(subtable, flow, trie_ctx, cls->n_tries, - wc); - if (rule && rule->priority > best->priority) { - best = rule; - } - } - break; } } 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_classifier *cls = cls_->cls; + struct cls_subtable *subtable; + struct cls_subtable_entry *iter; + + CLS_SUBTABLE_CACHE_FOR_EACH (subtable, iter, &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. */ struct cls_rule * -classifier_find_rule_exactly(const struct classifier *cls, +classifier_find_rule_exactly(const struct classifier *cls_, const struct cls_rule *target) { + struct cls_classifier *cls = cls_->cls; struct cls_rule *head, *rule; struct cls_subtable *subtable; @@ -619,18 +1035,20 @@ classifier_find_match_exactly(const struct classifier *cls, * considered to overlap if both rules have the same priority and a packet * could match both. */ bool -classifier_rule_overlaps(const struct classifier *cls, +classifier_rule_overlaps(const struct classifier *cls_, const struct cls_rule *target) { + struct cls_classifier *cls = cls_->cls; struct cls_subtable *subtable; + struct cls_subtable_entry *iter; /* Iterate subtables in the descending max priority order. */ - LIST_FOR_EACH (subtable, list_node, &cls->subtables_priority) { + CLS_SUBTABLE_CACHE_FOR_EACH (subtable, iter, &cls->subtables_priority) { uint32_t storage[FLOW_U32S]; struct minimask mask; struct cls_rule *head; - if (target->priority > subtable->max_priority) { + if (target->priority > iter->max_priority) { break; /* Can skip this and the rest of the subtables. */ } @@ -735,7 +1153,7 @@ void cls_cursor_init(struct cls_cursor *cursor, const struct classifier *cls, const struct cls_rule *target) { - cursor->cls = cls; + cursor->cls = cls->cls; cursor->target = target && !cls_rule_is_catchall(target) ? target : NULL; } @@ -794,7 +1212,7 @@ cls_cursor_next(struct cls_cursor *cursor, const struct cls_rule *rule_) } static struct cls_subtable * -find_subtable(const struct classifier *cls, const struct minimask *mask) +find_subtable(const struct cls_classifier *cls, const struct minimask *mask) { struct cls_subtable *subtable; @@ -808,13 +1226,14 @@ find_subtable(const struct classifier *cls, const struct minimask *mask) } static struct cls_subtable * -insert_subtable(struct classifier *cls, const struct minimask *mask) +insert_subtable(struct cls_classifier *cls, const struct minimask *mask) { uint32_t hash = minimask_hash(mask, 0); struct cls_subtable *subtable; int i, index = 0; struct flow_wildcards old, new; uint8_t prev; + struct cls_subtable_entry elem; subtable = xzalloc(sizeof *subtable); hmap_init(&subtable->rules); @@ -848,8 +1267,6 @@ insert_subtable(struct classifier *cls, const struct minimask *mask) } subtable->n_indices = index; - hmap_insert(&cls->subtables, &subtable->hmap_node, hash); - list_push_back(&cls->subtables_priority, &subtable->list_node); subtable->tag = (minimask_get_metadata_mask(mask) == OVS_BE64_MAX ? tag_create_deterministic(hash) : TAG_ALL); @@ -859,13 +1276,29 @@ insert_subtable(struct classifier *cls, const struct minimask *mask) cls->tries[i].field); } + hmap_insert(&cls->subtables, &subtable->hmap_node, hash); + elem.subtable = subtable; + elem.mask_values = subtable->mask.masks.values; + elem.tag = subtable->tag; + elem.max_priority = subtable->max_priority; + cls_subtable_cache_push_back(&cls->subtables_priority, elem); + return subtable; } static void -destroy_subtable(struct classifier *cls, struct cls_subtable *subtable) +destroy_subtable(struct cls_classifier *cls, struct cls_subtable *subtable) { int i; + struct cls_subtable *table = NULL; + struct cls_subtable_entry *iter; + + CLS_SUBTABLE_CACHE_FOR_EACH (table, iter, &cls->subtables_priority) { + if (table == subtable) { + cls_subtable_cache_remove(&cls->subtables_priority, iter); + break; + } + } for (i = 0; i < subtable->n_indices; i++) { hindex_destroy(&subtable->indices[i]); @@ -873,7 +1306,6 @@ destroy_subtable(struct classifier *cls, struct cls_subtable *subtable) minimask_destroy(&subtable->mask); hmap_remove(&cls->subtables, &subtable->hmap_node); hmap_destroy(&subtable->rules); - list_remove(&subtable->list_node); free(subtable); } @@ -888,35 +1320,38 @@ destroy_subtable(struct classifier *cls, struct cls_subtable *subtable) * This function should only be called after adding a new rule, not after * replacing a rule by an identical one or modifying a rule in-place. */ static void -update_subtables_after_insertion(struct classifier *cls, +update_subtables_after_insertion(struct cls_classifier *cls, struct cls_subtable *subtable, unsigned int new_priority) { if (new_priority == subtable->max_priority) { ++subtable->max_count; } else if (new_priority > subtable->max_priority) { - struct cls_subtable *iter; + struct cls_subtable *table; + struct cls_subtable_entry *iter, *subtable_iter = NULL; subtable->max_priority = new_priority; subtable->max_count = 1; /* Possibly move 'subtable' earlier in the priority list. If we break - * out of the loop, then 'subtable' should be moved just after that + * out of the loop, then 'subtable_iter' should be moved just before * 'iter'. If the loop terminates normally, then 'iter' will be the - * list head and we'll move subtable just after that (e.g. to the front - * of the list). */ - iter = subtable; - LIST_FOR_EACH_REVERSE_CONTINUE (iter, list_node, - &cls->subtables_priority) { - if (iter->max_priority >= subtable->max_priority) { + * first list element and we'll move subtable just before that + * (e.g. to the front of the list). */ + CLS_SUBTABLE_CACHE_FOR_EACH_REVERSE (table, iter, &cls->subtables_priority) { + if (table == subtable) { + subtable_iter = iter; /* Locate the subtable as we go. */ + iter->max_priority = new_priority; + } else if (table->max_priority >= new_priority) { + ovs_assert(subtable_iter != NULL); + iter++; break; } } - /* Move 'subtable' just after 'iter' (unless it's already there). */ - if (iter->list_node.next != &subtable->list_node) { - list_splice(iter->list_node.next, - &subtable->list_node, subtable->list_node.next); + /* Move 'subtable' just before 'iter' (unless it's already there). */ + if (iter != subtable_iter) { + cls_subtable_cache_splice(iter, subtable_iter, subtable_iter + 1); } } } @@ -932,14 +1367,14 @@ update_subtables_after_insertion(struct classifier *cls, * This function should only be called after removing a rule, not after * replacing a rule by an identical one or modifying a rule in-place. */ static void -update_subtables_after_removal(struct classifier *cls, +update_subtables_after_removal(struct cls_classifier *cls, struct cls_subtable *subtable, unsigned int del_priority) { - struct cls_subtable *iter; - if (del_priority == subtable->max_priority && --subtable->max_count == 0) { struct cls_rule *head; + struct cls_subtable *table; + struct cls_subtable_entry *iter, *subtable_iter = NULL; subtable->max_priority = 0; HMAP_FOR_EACH (head, hmap_node, &subtable->rules) { @@ -956,17 +1391,19 @@ update_subtables_after_removal(struct classifier *cls, * 'iter'. If the loop terminates normally, then 'iter' will be the * list head and we'll move subtable just before that (e.g. to the back * of the list). */ - iter = subtable; - LIST_FOR_EACH_CONTINUE (iter, list_node, &cls->subtables_priority) { - if (iter->max_priority <= subtable->max_priority) { + CLS_SUBTABLE_CACHE_FOR_EACH (table, iter, &cls->subtables_priority) { + if (table == subtable) { + subtable_iter = iter; /* Locate the subtable as we go. */ + iter->max_priority = subtable->max_priority; + } else if (table->max_priority <= subtable->max_priority) { + ovs_assert(subtable_iter != NULL); break; } } /* Move 'subtable' just before 'iter' (unless it's already there). */ - if (iter->list_node.prev != &subtable->list_node) { - list_splice(&iter->list_node, - &subtable->list_node, subtable->list_node.next); + if (iter != subtable_iter) { + cls_subtable_cache_splice(iter, subtable_iter, subtable_iter + 1); } } } @@ -1062,7 +1499,7 @@ find_match_wc(const struct cls_subtable *subtable, const struct flow *flow, int i; struct range ofs; - if (!wc) { + if (OVS_UNLIKELY(!wc)) { return find_match(subtable, flow, flow_hash_in_minimask(flow, &subtable->mask, 0)); } @@ -1149,7 +1586,7 @@ find_equal(struct cls_subtable *subtable, const struct miniflow *flow, } static struct cls_rule * -insert_rule(struct classifier *cls, struct cls_subtable *subtable, +insert_rule(struct cls_classifier *cls, struct cls_subtable *subtable, struct cls_rule *new) { struct cls_rule *head; @@ -1503,7 +1940,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)); }