VLOG_DEFINE_THIS_MODULE(classifier);
+struct trie_node;
+
+/* 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_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 list subtables_priority; /* Subtables in descending priority order.
+ */
+ 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 list list_node; /* Within classifier 'subtables_priority' list.
+ */
+ struct hmap rules; /* Contains "struct cls_rule"s. */
+ struct minimask mask; /* Wildcards for fields. */
+ 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'. */
+};
+
+/* 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'. */
+};
+
+
+
struct trie_ctx;
-static struct cls_subtable *find_subtable(const struct classifier *,
+static struct cls_subtable *find_subtable(const struct cls_classifier *,
const struct minimask *);
-static struct cls_subtable *insert_subtable(struct classifier *,
+static struct cls_subtable *insert_subtable(struct cls_classifier *,
const struct minimask *);
-static void destroy_subtable(struct classifier *, struct cls_subtable *);
+static void destroy_subtable(struct cls_classifier *, struct cls_subtable *);
-static void update_subtables_after_insertion(struct classifier *,
+static void update_subtables_after_insertion(struct cls_classifier *,
struct cls_subtable *,
unsigned int new_priority);
-static void update_subtables_after_removal(struct classifier *,
+static void update_subtables_after_removal(struct cls_classifier *,
struct cls_subtable *,
unsigned int del_priority);
struct flow_wildcards *);
static struct cls_rule *find_equal(struct cls_subtable *,
const struct miniflow *, uint32_t hash);
-static struct cls_rule *insert_rule(struct classifier *,
+static struct cls_rule *insert_rule(struct cls_classifier *,
struct cls_subtable *, struct cls_rule *);
/* Iterates RULE over HEAD and all of the cls_rules on HEAD->list. */
static unsigned int minimask_get_prefix_len(const struct minimask *,
const struct mf_field *);
-static void trie_init(struct classifier *, int trie_idx,
+static void trie_init(struct cls_classifier *, int trie_idx,
const struct mf_field *);
static unsigned int trie_lookup(const struct cls_trie *, const struct flow *,
unsigned int *checkbits);
/* Initializes 'cls' as a classifier that initially contains no classification
* rules. */
void
-classifier_init(struct classifier *cls, const uint8_t *flow_segments)
+classifier_init(struct classifier *cls_, const uint8_t *flow_segments)
{
+ struct cls_classifier *cls = xmalloc(sizeof *cls);
+
+ fat_rwlock_init(&cls_->rwlock);
+
+ cls_->cls = cls;
+
cls->n_rules = 0;
hmap_init(&cls->subtables);
list_init(&cls->subtables_priority);
hmap_init(&cls->partitions);
- fat_rwlock_init(&cls->rwlock);
cls->n_flow_segments = 0;
if (flow_segments) {
while (cls->n_flow_segments < CLS_MAX_INDICES
/* Destroys 'cls'. Rules within 'cls', if any, are not freed; this is the
* caller's responsibility. */
void
-classifier_destroy(struct classifier *cls)
+classifier_destroy(struct classifier *cls_)
{
- if (cls) {
+ if (cls_) {
+ struct cls_classifier *cls = cls_->cls;
struct cls_subtable *partition, *next_partition;
struct cls_subtable *subtable, *next_subtable;
int i;
+ fat_rwlock_destroy(&cls_->rwlock);
+ if (!cls) {
+ return;
+ }
+
for (i = 0; i < cls->n_tries; i++) {
trie_destroy(cls->tries[i].root);
}
free(partition);
}
hmap_destroy(&cls->partitions);
- fat_rwlock_destroy(&cls->rwlock);
+
+ free(cls);
}
}
/* Set the fields for which prefix lookup should be performed. */
void
-classifier_set_prefix_fields(struct classifier *cls,
+classifier_set_prefix_fields(struct classifier *cls_,
const enum mf_field_id *trie_fields,
unsigned int n_fields)
{
+ struct cls_classifier *cls = cls_->cls;
uint64_t fields = 0;
int i, trie;
}
static void
-trie_init(struct classifier *cls, int trie_idx,
+trie_init(struct cls_classifier *cls, int trie_idx,
const struct mf_field *field)
{
struct cls_trie *trie = &cls->tries[trie_idx];
bool
classifier_is_empty(const struct classifier *cls)
{
- return cls->n_rules == 0;
+ return cls->cls->n_rules == 0;
}
/* Returns the number of rules in 'cls'. */
int
classifier_count(const struct classifier *cls)
{
- return cls->n_rules;
+ return cls->cls->n_rules;
}
static uint32_t
}
static struct cls_partition *
-find_partition(const struct classifier *cls, ovs_be64 metadata, uint32_t hash)
+find_partition(const struct cls_classifier *cls, ovs_be64 metadata,
+ uint32_t hash)
{
struct cls_partition *partition;
}
static struct cls_partition *
-create_partition(struct classifier *cls, struct cls_subtable *subtable,
+create_partition(struct cls_classifier *cls, struct cls_subtable *subtable,
ovs_be64 metadata)
{
uint32_t hash = hash_metadata(metadata);
* 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)
+classifier_replace(struct classifier *cls_, struct cls_rule *rule)
{
+ struct cls_classifier *cls = cls_->cls;
struct cls_rule *old_rule;
struct cls_subtable *subtable;
* '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)
+classifier_remove(struct classifier *cls_, struct cls_rule *rule)
{
+ struct cls_classifier *cls = cls_->cls;
struct cls_partition *partition;
struct cls_rule *head;
struct cls_subtable *subtable;
* 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,
+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;
struct cls_subtable *subtable;
struct cls_rule *best;
* 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,
+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;
LIST_FOR_EACH (subtable, list_node, &cls->subtables_priority) {
* 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,
+classifier_find_rule_exactly(const struct classifier *cls_,
const struct cls_rule *target)
{
+ struct cls_classifier *cls = cls_->cls;
struct cls_rule *head, *rule;
struct cls_subtable *subtable;
* considered to overlap if both rules have the same priority and a packet
* could match both. */
bool
-classifier_rule_overlaps(const struct classifier *cls,
+classifier_rule_overlaps(const struct classifier *cls_,
const struct cls_rule *target)
{
+ struct cls_classifier *cls = cls_->cls;
struct cls_subtable *subtable;
/* Iterate subtables in the descending max priority order. */
cls_cursor_init(struct cls_cursor *cursor, const struct classifier *cls,
const struct cls_rule *target)
{
- cursor->cls = cls;
+ cursor->cls = cls->cls;
cursor->target = target && !cls_rule_is_catchall(target) ? target : NULL;
}
}
\f
static struct cls_subtable *
-find_subtable(const struct classifier *cls, const struct minimask *mask)
+find_subtable(const struct cls_classifier *cls, const struct minimask *mask)
{
struct cls_subtable *subtable;
}
static struct cls_subtable *
-insert_subtable(struct classifier *cls, const struct minimask *mask)
+insert_subtable(struct cls_classifier *cls, const struct minimask *mask)
{
uint32_t hash = minimask_hash(mask, 0);
struct cls_subtable *subtable;
}
static void
-destroy_subtable(struct classifier *cls, struct cls_subtable *subtable)
+destroy_subtable(struct cls_classifier *cls, struct cls_subtable *subtable)
{
int i;
* This function should only be called after adding a new rule, not after
* replacing a rule by an identical one or modifying a rule in-place. */
static void
-update_subtables_after_insertion(struct classifier *cls,
+update_subtables_after_insertion(struct cls_classifier *cls,
struct cls_subtable *subtable,
unsigned int new_priority)
{
* This function should only be called after removing a rule, not after
* replacing a rule by an identical one or modifying a rule in-place. */
static void
-update_subtables_after_removal(struct classifier *cls,
+update_subtables_after_removal(struct cls_classifier *cls,
struct cls_subtable *subtable,
unsigned int del_priority)
{
}
static struct cls_rule *
-insert_rule(struct classifier *cls, struct cls_subtable *subtable,
+insert_rule(struct cls_classifier *cls, struct cls_subtable *subtable,
struct cls_rule *new)
{
struct cls_rule *head;
/* Needed only for the lock annotation in struct classifier. */
extern struct ovs_mutex ofproto_mutex;
-struct trie_node;
-/* Prefix trie for a 'field' */
-struct cls_trie {
- const struct mf_field *field; /* Trie field, or NULL. */
- struct trie_node *root; /* NULL if none. */
-};
-
-enum {
- CLS_MAX_INDICES = 3, /* Maximum number of lookup indices per subtable. */
- CLS_MAX_TRIES = 3 /* Maximum number of prefix trees per classifier. */
-};
+/* Classifier internal data structures. */
+struct cls_classifier;
+struct cls_subtable;
+struct cls_partition;
/* A flow classifier. */
struct 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 list subtables_priority; /* Subtables in descending priority order.
- */
- struct hmap partitions; /* Contains "struct cls_partition"s. */
struct fat_rwlock rwlock OVS_ACQ_AFTER(ofproto_mutex);
- struct cls_trie tries[CLS_MAX_TRIES]; /* Prefix tries. */
- unsigned int n_tries;
+ struct cls_classifier *cls;
};
-/* A set of rules that all have the same fields wildcarded. */
-struct cls_subtable {
- struct hmap_node hmap_node; /* Within struct classifier 'subtables' hmap.
- */
- struct list list_node; /* Within classifier 'subtables_priority' list.
- */
- struct hmap rules; /* Contains "struct cls_rule"s. */
- struct minimask mask; /* Wildcards for fields. */
- 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'. */
+enum {
+ CLS_MAX_INDICES = 3, /* Maximum number of lookup indices per subtable. */
+ CLS_MAX_TRIES = 3 /* Maximum number of prefix trees per classifier. */
};
-/* Returns true if 'table' is a "catch-all" subtable that will match every
- * packet (if there is no higher-priority match). */
-static inline bool
-cls_subtable_is_catchall(const struct cls_subtable *subtable)
-{
- return minimask_is_catchall(&subtable->mask);
-}
-
/* A rule in a "struct cls_subtable". */
struct cls_rule {
struct hmap_node hmap_node; /* Within struct cls_subtable 'rules'. */
* 'indices'. */
};
-/* 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 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'. */
-};
-
void cls_rule_init(struct cls_rule *, const struct match *,
unsigned int priority);
void cls_rule_init_from_minimatch(struct cls_rule *, const struct minimatch *,
/* Iteration. */
struct cls_cursor {
- const struct classifier *cls;
+ const struct cls_classifier *cls;
const struct cls_subtable *subtable;
const struct cls_rule *target;
};