+#include "vlog.h"
+
+VLOG_DEFINE_THIS_MODULE(classifier);
+
+struct trie_node;
+struct trie_ctx;
+
+/* Ports trie depends on both ports sharing the same ovs_be32. */
+#define TP_PORTS_OFS32 (offsetof(struct flow, tp_src) / 4)
+BUILD_ASSERT_DECL(TP_PORTS_OFS32 == offsetof(struct flow, tp_dst) / 4);
+
+/* 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;
+ 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. */
+};
+
+enum {
+ CLS_MAX_INDICES = 3 /* Maximum number of lookup indices per subtable. */
+};
+
+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. */
+ 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'. */
+ int ports_mask_len;
+ struct trie_node *ports_trie; /* NULL if none. */
+ struct minimask mask; /* Wildcards for fields. */
+ /* 'mask' must be the last field. */
+};
+
+/* 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'. */
+};
+
+/* Internal representation of a rule in a "struct cls_subtable". */
+struct cls_match {
+ struct cls_rule *cls_rule;
+ struct hindex_node index_nodes[CLS_MAX_INDICES]; /* Within subtable's
+ * 'indices'. */
+ struct hmap_node hmap_node; /* Within struct cls_subtable 'rules'. */
+ unsigned int priority; /* Larger numbers are higher priorities. */
+ struct cls_partition *partition;
+ struct list list; /* List of identical, lower-priority rules. */
+ struct miniflow flow; /* Matching rule. Mask is in the subtable. */
+ /* 'flow' must be the last field. */
+};
+
+static struct cls_match *
+cls_match_alloc(struct cls_rule *rule)
+{
+ int count = count_1bits(rule->match.flow.map);