+static struct cls_rule *
+find_match_wc(const struct cls_subtable *subtable, const struct flow *flow,
+ struct flow_wildcards * wc)
+{
+ uint32_t basis = 0, hash;
+ struct cls_rule *rule = NULL;
+ uint8_t prev_u32ofs = 0;
+ int i;
+
+ if (!wc) {
+ return find_match(subtable, flow,
+ flow_hash_in_minimask(flow, &subtable->mask, 0));
+ }
+
+ /* Try to finish early by checking fields in segments. */
+ for (i = 0; i < subtable->n_indices; i++) {
+ struct hindex_node *inode;
+
+ hash = flow_hash_in_minimask_range(flow, &subtable->mask, prev_u32ofs,
+ subtable->index_ofs[i], &basis);
+ prev_u32ofs = subtable->index_ofs[i];
+ inode = hindex_node_with_hash(&subtable->indices[i], hash);
+ if (!inode) {
+ /* No match, can stop immediately, but must fold in the mask
+ * covered so far. */
+ flow_wildcards_fold_minimask_range(wc, &subtable->mask, 0,
+ prev_u32ofs);
+ return NULL;
+ }
+
+ /* If we have narrowed down to a single rule already, check whether
+ * that rule matches. If it does match, then we're done. If it does
+ * not match, then we know that we will never get a match, but we do
+ * not yet know how many wildcards we need to fold into 'wc' so we
+ * continue iterating through indices to find that out. (We won't
+ * waste time calling minimatch_matches_flow() again because we've set
+ * 'rule' nonnull.)
+ *
+ * This check shows a measurable benefit with non-trivial flow tables.
+ *
+ * (Rare) hash collisions may cause us to miss the opportunity for this
+ * optimization. */
+ if (!inode->s && !rule) {
+ ASSIGN_CONTAINER(rule, inode - i, index_nodes);
+ if (minimatch_matches_flow(&rule->match, flow)) {
+ goto out;
+ }
+ }
+ }
+
+ if (!rule) {
+ /* Multiple potential matches exist, look for one. */
+ hash = flow_hash_in_minimask_range(flow, &subtable->mask, prev_u32ofs,
+ FLOW_U32S, &basis);
+ rule = find_match(subtable, flow, hash);
+ } else {
+ /* We already narrowed the matching candidates down to just 'rule',
+ * but it didn't match. */
+ rule = NULL;
+ }
+ out:
+ flow_wildcards_fold_minimask(wc, &subtable->mask);
+ return rule;
+}
+