[ovs-dev] [PATCH 04/10] lib/classifier: Hide more of the internal data structures.
Jarno Rajahalme
jrajahalme at nicira.com
Fri Apr 18 19:41:55 UTC 2014
It is better not to expose definitions not needed by users.
Signed-off-by: Jarno Rajahalme <jrajahalme at nicira.com>
---
lib/classifier.c | 134 ++++++++++++++++++++++++++++++++++++-----------
lib/classifier.h | 65 ++++-------------------
tests/test-classifier.c | 6 +--
3 files changed, 115 insertions(+), 90 deletions(-)
diff --git a/lib/classifier.c b/lib/classifier.c
index 8ab1f9c..e48f0a1 100644
--- a/lib/classifier.c
+++ b/lib/classifier.c
@@ -30,18 +30,70 @@
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);
@@ -51,7 +103,7 @@ static struct cls_rule *find_match_wc(const struct cls_subtable *,
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. */
@@ -67,7 +119,7 @@ static struct cls_rule *next_rule_in_list(struct cls_rule *);
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);
@@ -349,13 +401,18 @@ cls_rule_is_catchall(const struct cls_rule *rule)
/* 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
@@ -369,13 +426,19 @@ classifier_init(struct classifier *cls, const uint8_t *flow_segments)
/* 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);
}
@@ -392,7 +455,8 @@ classifier_destroy(struct classifier *cls)
free(partition);
}
hmap_destroy(&cls->partitions);
- fat_rwlock_destroy(&cls->rwlock);
+
+ free(cls);
}
}
@@ -401,10 +465,11 @@ BUILD_ASSERT_DECL(MFF_N_IDS <= 64);
/* 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;
@@ -439,7 +504,7 @@ classifier_set_prefix_fields(struct classifier *cls,
}
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];
@@ -477,14 +542,14 @@ trie_init(struct classifier *cls, int 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
@@ -495,7 +560,8 @@ hash_metadata(ovs_be64 metadata_)
}
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;
@@ -509,7 +575,7 @@ find_partition(const struct classifier *cls, ovs_be64 metadata, uint32_t hash)
}
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);
@@ -539,8 +605,9 @@ create_partition(struct classifier *cls, struct cls_subtable *subtable,
* 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;
@@ -591,8 +658,9 @@ classifier_insert(struct classifier *cls, struct cls_rule *rule)
* '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;
@@ -672,9 +740,10 @@ trie_ctx_init(struct trie_ctx *ctx, const struct cls_trie *trie)
* 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;
@@ -787,9 +856,10 @@ find_match_miniflow(const struct cls_subtable *subtable,
* 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) {
@@ -811,9 +881,10 @@ struct cls_rule *classifier_lookup_miniflow_first(const struct classifier *cls,
* 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;
@@ -860,9 +931,10 @@ classifier_find_match_exactly(const struct classifier *cls,
* 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. */
@@ -976,7 +1048,7 @@ void
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;
}
@@ -1035,7 +1107,7 @@ cls_cursor_next(struct cls_cursor *cursor, const struct cls_rule *rule_)
}
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;
@@ -1049,7 +1121,7 @@ find_subtable(const struct classifier *cls, const struct minimask *mask)
}
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;
@@ -1104,7 +1176,7 @@ insert_subtable(struct classifier *cls, const struct minimask *mask)
}
static void
-destroy_subtable(struct classifier *cls, struct cls_subtable *subtable)
+destroy_subtable(struct cls_classifier *cls, struct cls_subtable *subtable)
{
int i;
@@ -1129,7 +1201,7 @@ destroy_subtable(struct classifier *cls, struct cls_subtable *subtable)
* 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)
{
@@ -1173,7 +1245,7 @@ update_subtables_after_insertion(struct classifier *cls,
* 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)
{
@@ -1390,7 +1462,7 @@ find_equal(struct cls_subtable *subtable, const struct miniflow *flow,
}
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;
diff --git a/lib/classifier.h b/lib/classifier.h
index 9022fab..048aaa1 100644
--- a/lib/classifier.h
+++ b/lib/classifier.h
@@ -232,60 +232,23 @@ extern "C" {
/* 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'. */
@@ -297,16 +260,6 @@ struct cls_rule {
* '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 *,
@@ -366,7 +319,7 @@ struct cls_rule *classifier_find_match_exactly(const struct classifier *cls,
/* Iteration. */
struct cls_cursor {
- const struct classifier *cls;
+ const struct cls_classifier *cls;
const struct cls_subtable *subtable;
const struct cls_rule *target;
};
diff --git a/tests/test-classifier.c b/tests/test-classifier.c
index 48eb8de..84f9367 100644
--- a/tests/test-classifier.c
+++ b/tests/test-classifier.c
@@ -475,7 +475,7 @@ check_tables(const struct classifier *cls, int n_tables, int n_rules,
int found_dups = 0;
int found_rules2 = 0;
- HMAP_FOR_EACH (table, hmap_node, &cls->subtables) {
+ HMAP_FOR_EACH (table, hmap_node, &cls->cls->subtables) {
const struct cls_rule *head;
unsigned int max_priority = 0;
unsigned int max_count = 0;
@@ -509,8 +509,8 @@ check_tables(const struct classifier *cls, int n_tables, int n_rules,
assert(table->max_count == max_count);
}
- assert(found_tables == hmap_count(&cls->subtables));
- assert(n_tables == -1 || n_tables == hmap_count(&cls->subtables));
+ assert(found_tables == hmap_count(&cls->cls->subtables));
+ assert(n_tables == -1 || n_tables == hmap_count(&cls->cls->subtables));
assert(n_rules == -1 || found_rules == n_rules);
assert(n_dups == -1 || found_dups == n_dups);
--
1.7.10.4
More information about the dev
mailing list