+ 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;
+ }