+ struct cls_subtable *subtable;
+ int i;
+
+ subtable = find_subtable(cls, &rule->match.mask);
+
+ 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], &rule->index_nodes[i]);
+ }
+
+ head = find_equal(subtable, &rule->match.flow, rule->hmap_node.hash);
+ if (head != rule) {
+ list_remove(&rule->list);
+ } else if (list_is_empty(&rule->list)) {
+ hmap_remove(&subtable->rules, &rule->hmap_node);
+ } else {
+ struct cls_rule *next = CONTAINER_OF(rule->list.next,
+ struct cls_rule, list);
+
+ list_remove(&rule->list);
+ hmap_replace(&subtable->rules, &rule->hmap_node, &next->hmap_node);
+ }
+
+ partition = rule->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, rule->priority);
+ }
+
+ cls->n_rules--;
+}
+
+/* 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;
+}
+
+/* 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)
+{
+ const struct cls_partition *partition;
+ struct cls_subtable *subtable;
+ struct cls_rule *best;
+ tag_type tags;
+ struct trie_ctx trie_ctx[CLS_MAX_TRIES];
+ int i;
+
+ /* 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]);
+ }
+ best = NULL;
+ LIST_FOR_EACH (subtable, list_node, &cls->subtables_priority) {
+ struct cls_rule *rule;
+
+ if (!tag_intersects(tags, subtable->tag)) {
+ continue;
+ }
+
+ rule = find_match_wc(subtable, flow, trie_ctx, cls->n_tries, wc);
+ if (rule) {
+ 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;
+}