From fccd7c092e09ce9767d34436bf9c70302c87c5f5 Mon Sep 17 00:00:00 2001 From: Jarno Rajahalme Date: Fri, 14 Nov 2014 15:58:09 -0800 Subject: [PATCH] classifier: Remove internal mutex. Almost all classifier users already exclude concurrent modifications, or are single-threaded, hence the classifier internal mutex can be removed. Due to this change, ovs-router.c and tnl-ports.c need new mutexes, which are added. As noted by Ben in review, ovs_router_flush() should also free the entries it removes from the classifier. It now calls ovsrcu_postpone() to that effect. Suggested-by: Ben Pfaff Signed-off-by: Jarno Rajahalme Acked-by: Ben Pfaff --- lib/classifier-private.h | 14 ++++++------ lib/classifier.c | 46 +++++----------------------------------- lib/classifier.h | 23 +++++++++----------- lib/ovs-router.c | 15 +++++++++++-- lib/tnl-ports.c | 34 ++++++++++++++++------------- tests/test-classifier.c | 11 ++-------- 6 files changed, 56 insertions(+), 87 deletions(-) diff --git a/lib/classifier-private.h b/lib/classifier-private.h index 64841ccd8..ae0657fba 100644 --- a/lib/classifier-private.h +++ b/lib/classifier-private.h @@ -27,11 +27,11 @@ /* A set of rules that all have the same fields wildcarded. */ struct cls_subtable { - struct cmap_node cmap_node OVS_GUARDED; /* Within struct classifier's - * 'subtables_map'. */ + struct cmap_node cmap_node; /* Within classifier's 'subtables_map'. */ + /* These fields are only used by writers. */ - int max_priority OVS_GUARDED; /* Max priority of any rule in subtable. */ - unsigned int max_count OVS_GUARDED; /* Count of max_priority rules. */ + int max_priority; /* Max priority of any rule in subtable. */ + unsigned int max_count; /* Count of max_priority rules. */ /* Accessed by iterators. */ struct rculist rules_list; /* Unordered. */ @@ -62,16 +62,16 @@ struct cls_partition { struct cmap_node cmap_node; /* In struct classifier's 'partitions' map. */ ovs_be64 metadata; /* metadata value for this partition. */ tag_type tags; /* OR of each flow's cls_subtable tag. */ - struct tag_tracker tracker OVS_GUARDED; /* Tracks the bits in 'tags'. */ + struct tag_tracker tracker; /* Tracks the bits in 'tags'. */ }; /* Internal representation of a rule in a "struct cls_subtable". */ struct cls_match { /* Accessed by everybody. */ - struct rculist list OVS_GUARDED; /* Identical, lower-priority rules. */ + struct rculist list; /* Identical, lower-priority rules. */ /* Accessed only by writers. */ - struct cls_partition *partition OVS_GUARDED; + struct cls_partition *partition; /* Accessed by readers interested in wildcarding. */ const int priority; /* Larger numbers are higher priorities. */ diff --git a/lib/classifier.c b/lib/classifier.c index 4560f4028..aa4c351dd 100644 --- a/lib/classifier.c +++ b/lib/classifier.c @@ -56,10 +56,8 @@ cls_match_alloc(struct cls_rule *rule) static struct cls_subtable *find_subtable(const struct classifier *cls, const struct minimask *); static struct cls_subtable *insert_subtable(struct classifier *cls, - const struct minimask *) - OVS_REQUIRES(cls->mutex); -static void destroy_subtable(struct classifier *cls, struct cls_subtable *) - OVS_REQUIRES(cls->mutex); + const struct minimask *); +static void destroy_subtable(struct classifier *cls, struct cls_subtable *); static const struct cls_match *find_match_wc(const struct cls_subtable *, const struct flow *, @@ -99,9 +97,7 @@ next_rule_in_list_protected(struct cls_match *rule) return next->priority < rule->priority ? next : NULL; } -/* Iterates RULE over HEAD and all of the cls_rules on HEAD->list. - * Classifier's mutex must be held while iterating, as the list is - * protoceted by it. */ +/* Iterates RULE over HEAD and all of the cls_rules on HEAD->list. */ #define FOR_EACH_RULE_IN_LIST(RULE, HEAD) \ for ((RULE) = (HEAD); (RULE) != NULL; (RULE) = next_rule_in_list(RULE)) #define FOR_EACH_RULE_IN_LIST_PROTECTED(RULE, HEAD) \ @@ -111,8 +107,7 @@ next_rule_in_list_protected(struct cls_match *rule) static unsigned int minimask_get_prefix_len(const struct minimask *, const struct mf_field *); static void trie_init(struct classifier *cls, int trie_idx, - const struct mf_field *) - OVS_REQUIRES(cls->mutex); + const struct mf_field *); static unsigned int trie_lookup(const struct cls_trie *, const struct flow *, union mf_value *plens); static unsigned int trie_lookup_value(const rcu_trie_ptr *, @@ -134,7 +129,6 @@ static bool mask_prefix_bits_set(const struct flow_wildcards *, static inline void cls_rule_init__(struct cls_rule *rule, unsigned int priority) - OVS_NO_THREAD_SAFETY_ANALYSIS { rculist_init(&rule->node); rule->priority = priority; @@ -181,7 +175,6 @@ cls_rule_clone(struct cls_rule *dst, const struct cls_rule *src) * The caller must eventually destroy 'dst' with cls_rule_destroy(). */ void cls_rule_move(struct cls_rule *dst, struct cls_rule *src) - OVS_NO_THREAD_SAFETY_ANALYSIS { ovs_assert(!src->cls_match); /* Must not be in a classifier. */ cls_rule_init__(dst, src->priority); @@ -194,7 +187,6 @@ cls_rule_move(struct cls_rule *dst, struct cls_rule *src) * ('rule' must not currently be in a classifier.) */ void cls_rule_destroy(struct cls_rule *rule) - OVS_NO_THREAD_SAFETY_ANALYSIS { ovs_assert(!rule->cls_match); /* Must not be in a classifier. */ @@ -240,10 +232,7 @@ cls_rule_is_catchall(const struct cls_rule *rule) * rules. */ void classifier_init(struct classifier *cls, const uint8_t *flow_segments) - OVS_EXCLUDED(cls->mutex) { - ovs_mutex_init(&cls->mutex); - ovs_mutex_lock(&cls->mutex); cls->n_rules = 0; cmap_init(&cls->subtables_map); pvector_init(&cls->subtables); @@ -259,7 +248,6 @@ classifier_init(struct classifier *cls, const uint8_t *flow_segments) for (int i = 0; i < CLS_MAX_TRIES; i++) { trie_init(cls, i, NULL); } - ovs_mutex_unlock(&cls->mutex); } /* Destroys 'cls'. Rules within 'cls', if any, are not freed; this is the @@ -267,14 +255,12 @@ classifier_init(struct classifier *cls, const uint8_t *flow_segments) * May only be called after all the readers have been terminated. */ void classifier_destroy(struct classifier *cls) - OVS_EXCLUDED(cls->mutex) { if (cls) { struct cls_partition *partition; struct cls_subtable *subtable; int i; - ovs_mutex_lock(&cls->mutex); for (i = 0; i < cls->n_tries; i++) { trie_destroy(&cls->tries[i].root); } @@ -290,8 +276,6 @@ classifier_destroy(struct classifier *cls) cmap_destroy(&cls->partitions); pvector_destroy(&cls->subtables); - ovs_mutex_unlock(&cls->mutex); - ovs_mutex_destroy(&cls->mutex); } } @@ -300,14 +284,12 @@ bool classifier_set_prefix_fields(struct classifier *cls, const enum mf_field_id *trie_fields, unsigned int n_fields) - OVS_EXCLUDED(cls->mutex) { const struct mf_field * new_fields[CLS_MAX_TRIES]; struct mf_bitmap fields = MF_BITMAP_INITIALIZER; int i, n_tries = 0; bool changed = false; - ovs_mutex_lock(&cls->mutex); for (i = 0; i < n_fields && n_tries < CLS_MAX_TRIES; i++) { const struct mf_field *field = mf_from_id(trie_fields[i]); if (field->flow_be32ofs < 0 || field->n_bits % 32) { @@ -370,17 +352,14 @@ classifier_set_prefix_fields(struct classifier *cls, } cls->n_tries = n_tries; - ovs_mutex_unlock(&cls->mutex); return true; } - ovs_mutex_unlock(&cls->mutex); return false; /* No change. */ } static void trie_init(struct classifier *cls, int trie_idx, const struct mf_field *field) - OVS_REQUIRES(cls->mutex) { struct cls_trie *trie = &cls->tries[trie_idx]; struct cls_subtable *subtable; @@ -422,7 +401,6 @@ classifier_is_empty(const struct classifier *cls) /* Returns the number of rules in 'cls'. */ int classifier_count(const struct classifier *cls) - OVS_NO_THREAD_SAFETY_ANALYSIS { /* n_rules is an int, so in the presence of concurrent writers this will * return either the old or a new value. */ @@ -453,7 +431,6 @@ 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, ovs_be64 metadata) - OVS_REQUIRES(cls->mutex) { uint32_t hash = hash_metadata(metadata); struct cls_partition *partition = find_partition(cls, metadata, hash); @@ -480,7 +457,6 @@ subtable_replace_head_rule(struct classifier *cls OVS_UNUSED, struct cls_subtable *subtable, struct cls_match *head, struct cls_match *new, uint32_t hash, uint32_t ihash[CLS_MAX_INDICES]) - OVS_REQUIRES(cls->mutex) { /* Rule's data is already in the tries. */ @@ -510,7 +486,6 @@ subtable_replace_head_rule(struct classifier *cls OVS_UNUSED, */ const struct cls_rule * classifier_replace(struct classifier *cls, struct cls_rule *rule) - OVS_EXCLUDED(cls->mutex) { struct cls_match *new = cls_match_alloc(rule); struct cls_subtable *subtable; @@ -522,7 +497,6 @@ classifier_replace(struct classifier *cls, struct cls_rule *rule) uint32_t hash; int i; - ovs_mutex_lock(&cls->mutex); rule->cls_match = new; subtable = find_subtable(cls, &rule->match.mask); @@ -628,7 +602,6 @@ classifier_replace(struct classifier *cls, struct cls_rule *rule) /* Return displaced rule. Caller is responsible for keeping it * around until all threads quiesce. */ - ovs_mutex_unlock(&cls->mutex); return old; } } else { @@ -659,7 +632,6 @@ classifier_replace(struct classifier *cls, struct cls_rule *rule) /* Nothing was replaced. */ cls->n_rules++; - ovs_mutex_unlock(&cls->mutex); return NULL; } @@ -686,7 +658,6 @@ classifier_insert(struct classifier *cls, struct cls_rule *rule) */ const struct cls_rule * classifier_remove(struct classifier *cls, const struct cls_rule *rule) - OVS_EXCLUDED(cls->mutex) { struct cls_partition *partition; struct cls_match *cls_match; @@ -698,11 +669,9 @@ classifier_remove(struct classifier *cls, const struct cls_rule *rule) uint8_t prev_be32ofs = 0; size_t n_rules; - ovs_mutex_lock(&cls->mutex); cls_match = rule->cls_match; if (!cls_match) { - rule = NULL; - goto unlock; /* Already removed. */ + return NULL; } /* Mark as removed. */ CONST_CAST(struct cls_rule *, rule)->cls_match = NULL; @@ -799,8 +768,6 @@ check_priority: free: ovsrcu_postpone(free, cls_match); cls->n_rules--; -unlock: - ovs_mutex_unlock(&cls->mutex); return rule; } @@ -1134,7 +1101,6 @@ find_subtable(const struct classifier *cls, const struct minimask *mask) /* The new subtable will be visible to the readers only after this. */ static struct cls_subtable * insert_subtable(struct classifier *cls, const struct minimask *mask) - OVS_REQUIRES(cls->mutex) { uint32_t hash = minimask_hash(mask, 0); struct cls_subtable *subtable; @@ -1204,7 +1170,6 @@ insert_subtable(struct classifier *cls, const struct minimask *mask) /* RCU readers may still access the subtable before it is actually freed. */ static void destroy_subtable(struct classifier *cls, struct cls_subtable *subtable) - OVS_REQUIRES(cls->mutex) { int i; @@ -1605,7 +1570,6 @@ trie_node_rcu_realloc(const struct trie_node *node) return new_node; } -/* May only be called while holding the classifier mutex. */ static void trie_destroy(rcu_trie_ptr *trie) { diff --git a/lib/classifier.h b/lib/classifier.h index 9a5ca4e7b..f7ba46c9c 100644 --- a/lib/classifier.h +++ b/lib/classifier.h @@ -216,7 +216,6 @@ #include "cmap.h" #include "match.h" #include "meta-flow.h" -#include "ovs-thread.h" #include "pvector.h" #include "rculist.h" @@ -244,8 +243,7 @@ enum { /* A flow classifier. */ struct classifier { - struct ovs_mutex mutex; - int n_rules OVS_GUARDED; /* Total number of rules. */ + 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. */ @@ -260,7 +258,7 @@ struct classifier { struct cls_rule { struct rculist node; /* In struct cls_subtable 'rules_list'. */ int priority; /* Larger numbers are higher priorities. */ - struct cls_match *cls_match OVS_GUARDED; /* NULL if not in a classifier. */ + struct cls_match *cls_match; /* NULL if not in a classifier. */ struct minimatch match; /* Matching rule. */ }; @@ -270,42 +268,41 @@ void cls_rule_init_from_minimatch(struct cls_rule *, const struct minimatch *, void cls_rule_clone(struct cls_rule *, const struct cls_rule *); void cls_rule_move(struct cls_rule *dst, struct cls_rule *src); void cls_rule_destroy(struct cls_rule *); - bool cls_rule_equal(const struct cls_rule *, const struct cls_rule *); uint32_t cls_rule_hash(const struct cls_rule *, uint32_t basis); - void cls_rule_format(const struct cls_rule *, struct ds *); - bool cls_rule_is_catchall(const struct cls_rule *); - bool cls_rule_is_loose_match(const struct cls_rule *rule, const struct minimatch *criteria); +/* Constructor/destructor. Must run single-threaded. */ void classifier_init(struct classifier *, const uint8_t *flow_segments); void classifier_destroy(struct classifier *); + +/* Modifiers. Caller MUST exclude concurrent calls from other threads. */ bool classifier_set_prefix_fields(struct classifier *, const enum mf_field_id *trie_fields, unsigned int n_trie_fields); - -bool classifier_is_empty(const struct classifier *); -int classifier_count(const struct classifier *); void classifier_insert(struct classifier *, struct cls_rule *); const struct cls_rule *classifier_replace(struct classifier *, struct cls_rule *); const struct cls_rule *classifier_remove(struct classifier *, const struct cls_rule *); + +/* Lookups. These are RCU protected and may run concurrently with modifiers + * and each other. */ const struct cls_rule *classifier_lookup(const struct classifier *, const struct flow *, struct flow_wildcards *); bool classifier_rule_overlaps(const struct classifier *, const struct cls_rule *); - const struct cls_rule *classifier_find_rule_exactly(const struct classifier *, const struct cls_rule *); - const struct cls_rule *classifier_find_match_exactly(const struct classifier *, const struct match *, int priority); +bool classifier_is_empty(const struct classifier *); +int classifier_count(const struct classifier *); /* Iteration. * diff --git a/lib/ovs-router.c b/lib/ovs-router.c index 696d7ec90..b723fa63b 100644 --- a/lib/ovs-router.c +++ b/lib/ovs-router.c @@ -36,9 +36,11 @@ #include "seq.h" #include "ovs-router.h" #include "ovs-router-linux.h" +#include "ovs-thread.h" #include "unixctl.h" #include "util.h" +static struct ovs_mutex mutex = OVS_MUTEX_INITIALIZER; static struct classifier cls; struct ovs_router_entry { @@ -115,7 +117,10 @@ ovs_router_insert__(uint8_t priority, ovs_be32 ip_dst, uint8_t plen, p->priority = priority; cls_rule_init(&p->cr, &match, priority); /* Longest prefix matches first. */ + ovs_mutex_lock(&mutex); cr = classifier_replace(&cls, &p->cr); + ovs_mutex_unlock(&mutex); + if (cr) { /* An old rule with the same match was displaced. */ ovsrcu_postpone(rt_entry_free, ovs_router_entry_cast(cr)); @@ -145,9 +150,11 @@ rt_entry_delete(uint8_t priority, ovs_be32 ip_dst, uint8_t plen) cr = classifier_find_rule_exactly(&cls, &rule); if (cr) { /* Remove it. */ + ovs_mutex_lock(&mutex); cr = classifier_remove(&cls, cr); - if (cr) { + ovs_mutex_unlock(&mutex); + if (cr) { ovsrcu_postpone(rt_entry_free, ovs_router_entry_cast(cr)); return true; } @@ -260,7 +267,11 @@ ovs_router_flush(void) CLS_FOR_EACH(rt, cr, &cls) { if (rt->priority == rt->plen) { - classifier_remove(&cls, &rt->cr); + ovs_mutex_lock(&mutex); + if (classifier_remove(&cls, &rt->cr)) { + ovsrcu_postpone(rt_entry_free, rt); + } + ovs_mutex_unlock(&mutex); } } seq_change(tnl_conf_seq); diff --git a/lib/tnl-ports.c b/lib/tnl-ports.c index bcf055ba2..9832ef46d 100644 --- a/lib/tnl-ports.c +++ b/lib/tnl-ports.c @@ -26,9 +26,11 @@ #include "odp-util.h" #include "tnl-arp-cache.h" #include "tnl-ports.h" +#include "ovs-thread.h" #include "unixctl.h" #include "util.h" +static struct ovs_mutex mutex = OVS_MUTEX_INITIALIZER; static struct classifier cls; /* Tunnel ports. */ struct tnl_port_in { @@ -80,30 +82,30 @@ tnl_port_map_insert(odp_port_t port, ovs_be32 ip_dst, ovs_be16 udp_port, memset(&match, 0, sizeof match); tnl_port_init_flow(&match.flow, ip_dst, udp_port); + ovs_mutex_lock(&mutex); do { cr = classifier_lookup(&cls, &match.flow, NULL); p = tnl_port_cast(cr); /* Try again if the rule was released before we get the reference. */ } while (p && !ovs_refcount_try_ref_rcu(&p->ref_cnt)); - if (p) { - return; /* Added refcount of an existing port. */ - } - - p = xzalloc(sizeof *p); - p->portno = port; + if (!p) { + p = xzalloc(sizeof *p); + p->portno = port; - match.wc.masks.dl_type = OVS_BE16_MAX; - match.wc.masks.nw_proto = 0xff; - match.wc.masks.nw_frag = 0xff; /* XXX: No fragments support. */ - match.wc.masks.tp_dst = OVS_BE16_MAX; - match.wc.masks.nw_src = OVS_BE32_MAX; + match.wc.masks.dl_type = OVS_BE16_MAX; + match.wc.masks.nw_proto = 0xff; + match.wc.masks.nw_frag = 0xff; /* XXX: No fragments support. */ + match.wc.masks.tp_dst = OVS_BE16_MAX; + match.wc.masks.nw_src = OVS_BE32_MAX; - cls_rule_init(&p->cr, &match, 0); /* Priority == 0. */ - ovs_refcount_init(&p->ref_cnt); - strncpy(p->dev_name, dev_name, IFNAMSIZ); + cls_rule_init(&p->cr, &match, 0); /* Priority == 0. */ + ovs_refcount_init(&p->ref_cnt); + strncpy(p->dev_name, dev_name, IFNAMSIZ); - classifier_insert(&cls, &p->cr); + classifier_insert(&cls, &p->cr); + } + ovs_mutex_unlock(&mutex); } static void @@ -112,9 +114,11 @@ tnl_port_unref(const struct cls_rule *cr) struct tnl_port_in *p = tnl_port_cast(cr); if (cr && ovs_refcount_unref_relaxed(&p->ref_cnt) == 1) { + ovs_mutex_lock(&mutex); if (classifier_remove(&cls, cr)) { ovsrcu_postpone(tnl_port_free, p); } + ovs_mutex_unlock(&mutex); } } diff --git a/tests/test-classifier.c b/tests/test-classifier.c index 5bdb5234f..273b0b972 100644 --- a/tests/test-classifier.c +++ b/tests/test-classifier.c @@ -496,6 +496,7 @@ trie_verify(const rcu_trie_ptr *trie, unsigned int ofs, unsigned int n_bits) static void verify_tries(struct classifier *cls) + OVS_NO_THREAD_SAFETY_ANALYSIS { unsigned int n_rules = 0; int i; @@ -504,14 +505,13 @@ verify_tries(struct classifier *cls) n_rules += trie_verify(&cls->tries[i].root, 0, cls->tries[i].field->n_bits); } - ovs_mutex_lock(&cls->mutex); assert(n_rules <= cls->n_rules); - ovs_mutex_unlock(&cls->mutex); } static void check_tables(const struct classifier *cls, int n_tables, int n_rules, int n_dups) + OVS_NO_THREAD_SAFETY_ANALYSIS { const struct cls_subtable *table; struct test_rule *test_rule; @@ -543,11 +543,8 @@ check_tables(const struct classifier *cls, int n_tables, int n_rules, } assert(!cmap_is_empty(&table->rules)); - - ovs_mutex_lock(&cls->mutex); assert(trie_verify(&table->ports_trie, 0, table->ports_mask_len) == (table->ports_mask_len ? cmap_count(&table->rules) : 0)); - ovs_mutex_unlock(&cls->mutex); found_tables++; CMAP_FOR_EACH (head, cmap_node, &table->rules) { @@ -564,9 +561,7 @@ check_tables(const struct classifier *cls, int n_tables, int n_rules, found_rules++; RCULIST_FOR_EACH (rule, list, &head->list) { assert(rule->priority < prev_priority); - ovs_mutex_lock(&cls->mutex); assert(rule->priority <= table->max_priority); - ovs_mutex_unlock(&cls->mutex); prev_priority = rule->priority; found_rules++; @@ -575,10 +570,8 @@ check_tables(const struct classifier *cls, int n_tables, int n_rules, == rule->cls_rule); } } - ovs_mutex_lock(&cls->mutex); assert(table->max_priority == max_priority); assert(table->max_count == max_count); - ovs_mutex_unlock(&cls->mutex); } assert(found_tables == cmap_count(&cls->subtables_map)); -- 2.20.1