On Apr 24, 2014, at 5:40 PM, Ethan Jackson <et...@nicira.com> wrote:
> So it seems to me that the only data needed in struct classifier by
> callers is the fat_rwlock. What if we add a classifier_rdlock() and a
> classifier_wrlock() function. That done, we could entirely hide
> struct classifier, and would need to make the distinction between it
> and the cls_classifier. Thoughts?
I wanted to avoid API changes in this series, but I like this in general.
However, this would prevent the OVS_REQ_RDLOCK() type of static analyzer
annotations on the API functions, and would result in additional function call
indirections for the lock and unlock functions.
Moreover, we should consider how to replace (most of) the locking with RCU,
which would be another change on the classifier locking interface.
Considering the above I would be inclined to push this patch as a step towards
the above goals, with the understanding that more work on this will be done
later.
Jarno
>
> Ethan
>
> On Fri, Apr 18, 2014 at 12:41 PM, Jarno Rajahalme <jrajaha...@nicira.com>
> wrote:
>> It is better not to expose definitions not needed by users.
>>
>> Signed-off-by: Jarno Rajahalme <jrajaha...@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
>>
>> _______________________________________________
>> dev mailing list
>> dev@openvswitch.org
>> http://openvswitch.org/mailman/listinfo/dev
_______________________________________________
dev mailing list
dev@openvswitch.org
http://openvswitch.org/mailman/listinfo/dev
