+ cls->n_tries = trie;
+}
+
+static void
+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);
+ }
+ trie->root = NULL;
+ trie->field = field;
+
+ /* Add existing rules to the trie. */
+ CLS_SUBTABLE_CACHE_FOR_EACH (subtable, iter, &cls->subtables_priority) {
+ unsigned int plen;
+
+ plen = field ? minimask_get_prefix_len(&subtable->mask, field) : 0;
+ /* Initialize subtable's prefix length on this field. */
+ subtable->trie_plen[trie_idx] = plen;
+
+ if (plen) {
+ struct cls_match *head;
+
+ HMAP_FOR_EACH (head, hmap_node, &subtable->rules) {
+ struct cls_match *match;
+
+ FOR_EACH_RULE_IN_LIST (match, head) {
+ trie_insert(trie, match->cls_rule, plen);
+ }
+ }
+ }
+ }
+}
+
+/* Returns true if 'cls' contains no classification rules, false otherwise. */
+bool
+classifier_is_empty(const struct classifier *cls)
+{
+ return cls->cls->n_rules == 0;
+}
+
+/* Returns the number of rules in 'cls'. */
+int
+classifier_count(const struct classifier *cls)
+{
+ return cls->cls->n_rules;
+}
+
+static uint32_t
+hash_metadata(ovs_be64 metadata_)
+{
+ uint64_t metadata = (OVS_FORCE uint64_t) metadata_;
+ return hash_uint64(metadata);
+}
+
+static struct cls_partition *
+find_partition(const struct cls_classifier *cls, ovs_be64 metadata,
+ uint32_t hash)
+{
+ struct cls_partition *partition;
+
+ HMAP_FOR_EACH_IN_BUCKET (partition, hmap_node, hash, &cls->partitions) {
+ if (partition->metadata == metadata) {
+ return partition;
+ }
+ }
+
+ return NULL;
+}
+
+static struct cls_partition *
+create_partition(struct cls_classifier *cls, struct cls_subtable *subtable,
+ ovs_be64 metadata)
+{
+ uint32_t hash = hash_metadata(metadata);
+ struct cls_partition *partition = find_partition(cls, metadata, hash);
+ if (!partition) {
+ partition = xmalloc(sizeof *partition);
+ partition->metadata = metadata;
+ partition->tags = 0;
+ tag_tracker_init(&partition->tracker);
+ hmap_insert(&cls->partitions, &partition->hmap_node, hash);
+ }
+ tag_tracker_add(&partition->tracker, &partition->tags, subtable->tag);
+ return partition;
+}
+
+static inline ovs_be32 minimatch_get_ports(const struct minimatch *match)
+{
+ /* Could optimize to use the same map if needed for fast path. */
+ return MINIFLOW_GET_BE32(&match->flow, tp_src)
+ & MINIFLOW_GET_BE32(&match->mask.masks, tp_src);
+}
+
+/* Inserts 'rule' into 'cls'. Until 'rule' is removed from 'cls', the caller
+ * must not modify or free it.
+ *
+ * If 'cls' already contains an identical rule (including wildcards, values of
+ * fixed fields, and priority), replaces the old rule by 'rule' and returns the
+ * rule that was replaced. The caller takes ownership of the returned rule and
+ * is thus responsible for destroying it with cls_rule_destroy(), freeing the
+ * memory block in which it resides, etc., as necessary.
+ *
+ * Returns NULL if 'cls' does not contain a rule with an identical key, after
+ * inserting the new rule. In this case, no rules are displaced by the new
+ * 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)
+{
+ struct cls_classifier *cls = cls_->cls;
+ struct cls_match *old_rule;
+ struct cls_subtable *subtable;
+
+ subtable = find_subtable(cls, &rule->match.mask);
+ if (!subtable) {
+ subtable = insert_subtable(cls, &rule->match.mask);
+ }
+
+ old_rule = insert_rule(cls, subtable, rule);
+ if (!old_rule) {
+ int i;
+
+ rule->cls_match->partition = NULL;
+ if (minimask_get_metadata_mask(&rule->match.mask) == OVS_BE64_MAX) {
+ ovs_be64 metadata = miniflow_get_metadata(&rule->match.flow);
+ rule->cls_match->partition = create_partition(cls, subtable,
+ metadata);
+ }
+
+ subtable->n_rules++;
+ cls->n_rules++;
+
+ for (i = 0; i < cls->n_tries; i++) {
+ if (subtable->trie_plen[i]) {
+ trie_insert(&cls->tries[i], rule, subtable->trie_plen[i]);
+ }
+ }
+
+ /* Ports trie. */
+ if (subtable->ports_mask_len) {
+ /* We mask the value to be inserted to always have the wildcarded
+ * bits in known (zero) state, so we can include them in comparison
+ * and they will always match (== their original value does not
+ * matter). */
+ ovs_be32 masked_ports = minimatch_get_ports(&rule->match);
+
+ trie_insert_prefix(&subtable->ports_trie, &masked_ports,
+ subtable->ports_mask_len);
+ }
+
+ return NULL;
+ } else {
+ struct cls_rule *old_cls_rule = old_rule->cls_rule;
+
+ rule->cls_match->partition = old_rule->partition;
+ old_cls_rule->cls_match = NULL;
+ free(old_rule);
+ return old_cls_rule;
+ }
+}
+
+/* Inserts 'rule' into 'cls'. Until 'rule' is removed from 'cls', the caller
+ * must not modify or free it.
+ *
+ * 'cls' must not contain an identical rule (including wildcards, values of
+ * fixed fields, and priority). Use classifier_find_rule_exactly() to find
+ * such a rule. */
+void
+classifier_insert(struct classifier *cls, struct cls_rule *rule)
+{
+ struct cls_rule *displaced_rule = classifier_replace(cls, rule);
+ ovs_assert(!displaced_rule);
+}
+
+/* Removes 'rule' from 'cls'. It is the caller's responsibility to destroy
+ * '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)
+{
+ struct cls_classifier *cls = cls_->cls;
+ struct cls_partition *partition;
+ struct cls_match *cls_match = rule->cls_match;
+ struct cls_match *head;
+ struct cls_subtable *subtable;
+ int i;
+
+ ovs_assert(cls_match);
+
+ subtable = find_subtable(cls, &rule->match.mask);
+ ovs_assert(subtable);
+
+ if (subtable->ports_mask_len) {
+ ovs_be32 masked_ports = minimatch_get_ports(&rule->match);
+
+ trie_remove_prefix(&subtable->ports_trie,
+ &masked_ports, subtable->ports_mask_len);
+ }
+ for (i = 0; i < cls->n_tries; i++) {
+ if (subtable->trie_plen[i]) {
+ trie_remove(&cls->tries[i], rule, subtable->trie_plen[i]);
+ }
+ }
+
+ /* Remove rule node from indices. */
+ for (i = 0; i < subtable->n_indices; i++) {
+ hindex_remove(&subtable->indices[i], &cls_match->index_nodes[i]);
+ }
+
+ head = find_equal(subtable, &rule->match.flow, cls_match->hmap_node.hash);
+ if (head != cls_match) {
+ list_remove(&cls_match->list);
+ } else if (list_is_empty(&cls_match->list)) {
+ hmap_remove(&subtable->rules, &cls_match->hmap_node);
+ } else {
+ struct cls_match *next = CONTAINER_OF(cls_match->list.next,
+ struct cls_match, list);
+
+ list_remove(&cls_match->list);
+ hmap_replace(&subtable->rules, &cls_match->hmap_node,
+ &next->hmap_node);
+ }
+
+ partition = cls_match->partition;
+ if (partition) {
+ tag_tracker_subtract(&partition->tracker, &partition->tags,
+ subtable->tag);
+ if (!partition->tags) {
+ hmap_remove(&cls->partitions, &partition->hmap_node);
+ free(partition);
+ }
+ }
+
+ if (--subtable->n_rules == 0) {
+ destroy_subtable(cls, subtable);
+ } else {
+ update_subtables_after_removal(cls, subtable, cls_match->priority);
+ }
+
+ cls->n_rules--;
+
+ rule->cls_match = NULL;
+ free(cls_match);
+}
+
+/* Prefix tree context. Valid when 'lookup_done' is true. Can skip all
+ * subtables which have more than 'match_plen' bits in their corresponding
+ * field at offset 'be32ofs'. If skipped, 'maskbits' prefix bits should be
+ * unwildcarded to quarantee datapath flow matches only packets it should. */
+struct trie_ctx {
+ const struct cls_trie *trie;
+ bool lookup_done; /* Status of the lookup. */
+ uint8_t be32ofs; /* U32 offset of the field in question. */
+ unsigned int match_plen; /* Longest prefix than could possibly match. */
+ unsigned int maskbits; /* Prefix length needed to avoid false matches. */
+};
+
+static void
+trie_ctx_init(struct trie_ctx *ctx, const struct cls_trie *trie)
+{
+ ctx->trie = trie;
+ ctx->be32ofs = trie->field->flow_be32ofs;
+ ctx->lookup_done = false;
+}
+
+static inline void
+lookahead_subtable(const struct cls_subtable_entry *subtables)
+{
+ ovs_prefetch_range(subtables->subtable, sizeof *subtables->subtable);
+}
+
+/* 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.
+ *
+ * If a rule is found and 'wc' is non-null, bitwise-OR's 'wc' with the
+ * set of bits that were significant in the lookup. At some point
+ * 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,
+ struct flow_wildcards *wc)
+{
+ struct cls_classifier *cls = cls_->cls;
+ const struct cls_partition *partition;
+ tag_type tags;
+ struct cls_match *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':
+ *
+ * - If flow->metadata maps to a given 'partition', then we can use
+ * 'tags' for 'partition->tags'.
+ *
+ * - If flow->metadata has no partition, then no rule in 'cls' has an
+ * exact-match for flow->metadata. That means that we don't need to
+ * search any subtable that includes flow->metadata in its mask.
+ *
+ * In either case, we always need to search any cls_subtables that do not
+ * include flow->metadata in its mask. One way to do that would be to
+ * check the "cls_subtable"s explicitly for that, but that would require an
+ * extra branch per subtable. Instead, we mark such a cls_subtable's
+ * 'tags' as TAG_ALL and make sure that 'tags' is never empty. This means
+ * that 'tags' always intersects such a cls_subtable's 'tags', so we don't
+ * need a special case.
+ */
+ partition = (hmap_is_empty(&cls->partitions)
+ ? NULL
+ : find_partition(cls, flow->metadata,
+ hash_metadata(flow->metadata)));
+ tags = partition ? partition->tags : TAG_ARBITRARY;
+
+ /* Initialize trie contexts for match_find_wc(). */
+ 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;
+ for (i = 0; OVS_LIKELY(i < n_subtables); i++) {
+ struct cls_match *rule;
+
+ 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(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;
+ }
+ }
+
+ return best ? best->cls_rule : NULL;
+}
+
+/* Returns true if 'target' satisifies 'match', that is, if each bit for which
+ * 'match' specifies a particular value has the correct value in 'target'.
+ *
+ * 'flow' and 'mask' have the same mask! */
+static bool
+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(flow);
+ const uint32_t *maskp = miniflow_get_u32_values(&mask->masks);
+ uint32_t target_u32;
+
+ MINIFLOW_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_miniflow(const struct cls_subtable *subtable,
+ const struct miniflow *flow,
+ uint32_t hash)
+{
+ struct cls_match *rule;
+
+ HMAP_FOR_EACH_WITH_HASH (rule, hmap_node, hash, &subtable->rules) {
+ if (miniflow_and_mask_matches_miniflow(&rule->flow, &subtable->mask,
+ 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_match *rule;
+
+ rule = find_match_miniflow(subtable, flow,
+ miniflow_hash_in_minimask(flow,
+ &subtable->mask,
+ 0));
+ if (rule) {
+ return rule->cls_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_,
+ const struct cls_rule *target)
+{
+ struct cls_classifier *cls = cls_->cls;
+ struct cls_match *head, *rule;
+ struct cls_subtable *subtable;
+
+ subtable = find_subtable(cls, &target->match.mask);
+ if (!subtable) {
+ return NULL;
+ }
+
+ /* Skip if there is no hope. */
+ if (target->priority > subtable->max_priority) {
+ return NULL;
+ }
+
+ head = find_equal(subtable, &target->match.flow,
+ miniflow_hash_in_minimask(&target->match.flow,
+ &target->match.mask, 0));
+ FOR_EACH_RULE_IN_LIST (rule, head) {
+ if (target->priority >= rule->priority) {
+ return target->priority == rule->priority ? rule->cls_rule : NULL;
+ }
+ }
+ return NULL;
+}
+
+/* Finds and returns a rule in 'cls' with priority 'priority' and exactly the
+ * same matching criteria as 'target'. Returns a null pointer if 'cls' doesn't
+ * contain an exact match. */
+struct cls_rule *
+classifier_find_match_exactly(const struct classifier *cls,
+ const struct match *target,
+ unsigned int priority)
+{
+ struct cls_rule *retval;
+ struct cls_rule cr;
+
+ cls_rule_init(&cr, target, priority);
+ retval = classifier_find_rule_exactly(cls, &cr);
+ cls_rule_destroy(&cr);
+
+ return retval;
+}
+
+/* Checks if 'target' would overlap any other rule in 'cls'. Two rules are
+ * considered to overlap if both rules have the same priority and a packet
+ * could match both. */
+bool
+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. */
+ CLS_SUBTABLE_CACHE_FOR_EACH (subtable, iter, &cls->subtables_priority) {
+ uint32_t storage[FLOW_U32S];
+ struct minimask mask;
+ struct cls_match *head;
+
+ if (target->priority > iter->max_priority) {
+ break; /* Can skip this and the rest of the subtables. */
+ }
+
+ minimask_combine(&mask, &target->match.mask, &subtable->mask, storage);
+ HMAP_FOR_EACH (head, hmap_node, &subtable->rules) {
+ struct cls_match *rule;
+
+ FOR_EACH_RULE_IN_LIST (rule, head) {
+ if (rule->priority < target->priority) {
+ break; /* Rules in descending priority order. */
+ }
+ if (rule->priority == target->priority
+ && miniflow_equal_in_minimask(&target->match.flow,
+ &rule->flow, &mask)) {
+ return true;
+ }
+ }
+ }
+ }
+
+ return false;
+}
+
+/* Returns true if 'rule' exactly matches 'criteria' or if 'rule' is more
+ * specific than 'criteria'. That is, 'rule' matches 'criteria' and this
+ * function returns true if, for every field:
+ *
+ * - 'criteria' and 'rule' specify the same (non-wildcarded) value for the
+ * field, or
+ *
+ * - 'criteria' wildcards the field,
+ *
+ * Conversely, 'rule' does not match 'criteria' and this function returns false
+ * if, for at least one field:
+ *
+ * - 'criteria' and 'rule' specify different values for the field, or
+ *
+ * - 'criteria' specifies a value for the field but 'rule' wildcards it.
+ *
+ * Equivalently, the truth table for whether a field matches is:
+ *
+ * rule
+ *
+ * c wildcard exact
+ * r +---------+---------+
+ * i wild | yes | yes |
+ * t card | | |
+ * e +---------+---------+
+ * r exact | no |if values|
+ * i | |are equal|
+ * a +---------+---------+
+ *
+ * This is the matching rule used by OpenFlow 1.0 non-strict OFPT_FLOW_MOD
+ * commands and by OpenFlow 1.0 aggregate and flow stats.
+ *
+ * Ignores rule->priority. */
+bool
+cls_rule_is_loose_match(const struct cls_rule *rule,
+ const struct minimatch *criteria)
+{
+ return (!minimask_has_extra(&rule->match.mask, &criteria->mask)
+ && miniflow_equal_in_minimask(&rule->match.flow, &criteria->flow,
+ &criteria->mask));
+}
+\f
+/* Iteration. */
+
+static bool
+rule_matches(const struct cls_match *rule, const struct cls_rule *target)
+{
+ return (!target
+ || miniflow_equal_in_minimask(&rule->flow,
+ &target->match.flow,
+ &target->match.mask));
+}
+
+static struct cls_match *
+search_subtable(const struct cls_subtable *subtable,
+ const struct cls_rule *target)
+{
+ if (!target || !minimask_has_extra(&subtable->mask, &target->match.mask)) {
+ struct cls_match *rule;
+
+ HMAP_FOR_EACH (rule, hmap_node, &subtable->rules) {
+ if (rule_matches(rule, target)) {
+ return rule;
+ }
+ }
+ }
+ return NULL;