lib/classifier: Lockless lookups.

Now that all the relevant classifier structures use RCU and internal
mutual exclusion for modifications, we can remove the fat-rwlock and
thus make the classifier lookups lockless.

As the readers are operating concurrently with the writers, a
concurrent reader may or may not see a new rule being added by a
writer, depending on how the concurrent events overlap with each
other.  Overall, this is no different from the former locked behavior,
but there the visibility of the new rule only depended on the timing
of the locking functions.

A new rule is first added to the segment indices, so the readers may
find the rule in the indices before the rule is visible in the
subtables 'rules' map.  This may result in us losing the opportunity
to quit lookups earlier, resulting in sub-optimal wildcarding.  This
will be fixed by forthcoming revalidation always scheduled after flow
table changes.

Similar behavior may happen due to us removing the overlapping rule
(if any) from the indices only after the corresponding new rule has
been added.

The subtable's max priority is updated only after a rule is inserted
to the maps, so the concurrent readers may not see the rule, as the
updated priority ordered subtable list will only be visible after the
subtable's max priority is updated.

Similarly, the classifier's partitions are updated by the caller after
the rule is inserted to the maps, so the readers may keep skipping the
subtable until they see the updated partitions.

Signed-off-by: Jarno Rajahalme <jrajahalme@nicira.com>
Acked-by: YAMAMOTO Takashi <yamamoto@valinux.co.jp>

4 files changed, 27 insertions, 57 deletions

diff --git a/ofproto/ofproto-dpif.c b/ofproto/ofproto-dpif.c
index 5aa597ee4..10b0cd498 100644
--- a/ofproto/ofproto-dpif.c
+++ b/ofproto/ofproto-dpif.c
@@ -3379,9 +3379,7 @@ rule_dpif_lookup_in_table(struct ofproto_dpif *ofproto, uint8_t table_id,
     }
 
     do {
-        fat_rwlock_rdlock(&cls->rwlock);
         cls_rule = classifier_lookup(cls, flow, wc);
-        fat_rwlock_unlock(&cls->rwlock);
 
         rule = rule_dpif_cast(rule_from_cls_rule(cls_rule));
 
diff --git a/ofproto/ofproto-provider.h b/ofproto/ofproto-provider.h
index 309ebd2d8..7e6e99bcf 100644
--- a/ofproto/ofproto-provider.h
+++ b/ofproto/ofproto-provider.h
@@ -196,21 +196,18 @@ enum oftable_flags {
  * Thread-safety
  * =============
  *
- * A cls->rwlock read-lock holder prevents rules from being added or deleted.
+ * Adding or removing rules requires holding ofproto_mutex.
  *
- * Adding or removing rules requires holding ofproto_mutex AND the cls->rwlock
- * write-lock.
+ * Rules in 'cls' are RCU protected.  For extended access to a rule, try
+ * incrementing its ref_count with ofproto_rule_try_ref(), or
+ * ofproto_rule_ref(), if the rule is still known to be in 'cls'.  A rule
+ * will be freed using ovsrcu_postpone() once its 'ref_count' reaches zero.
  *
- * cls->rwlock should be held only briefly.  For extended access to a rule,
- * increment its ref_count with ofproto_rule_ref().  A rule will not be freed
- * until its ref_count reaches zero.
+ * Modifying a rule requires the rule's own mutex.
  *
- * Modifying a rule requires the rule's own mutex.  Holding cls->rwlock (for
- * read or write) does not allow the holder to modify the rule.
- *
- * Freeing a rule requires ofproto_mutex and the cls->rwlock write-lock.  After
- * removing the rule from the classifier, release a ref_count from the rule
- * ('cls''s reference to the rule).
+ * Freeing a rule requires ofproto_mutex.  After removing the rule from the
+ * classifier, release a ref_count from the rule ('cls''s reference to the
+ * rule).
  *
  * Refer to the thread-safety notes on struct rule for more information.*/
 struct oftable {
@@ -289,19 +286,21 @@ struct oftable {
  * Rules
  * -----
  *
- * A rule 'rule' may be accessed without a risk of being freed by code that
- * holds a read-lock or write-lock on 'cls->rwlock' or that owns a reference to
- * 'rule->ref_count' (or both).  Code that needs to hold onto a rule for a
- * while should take 'cls->rwlock', find the rule it needs, increment
- * 'rule->ref_count' with ofproto_rule_ref(), and drop 'cls->rwlock'.
+ * A rule 'rule' may be accessed without a risk of being freed by a thread
+ * until the thread quiesces (i.e., rules are RCU protected and destructed
+ * using ovsrcu_postpone()).  Code that needs to hold onto a rule for a
+ * while should increment 'rule->ref_count' either with ofproto_rule_ref()
+ * (if 'ofproto_mutex' is held), or with ofproto_rule_try_ref() (when some
+ * other thread might remove the rule from 'cls').  ofproto_rule_try_ref()
+ * will fail if the rule has already been scheduled for destruction.
  *
  * 'rule->ref_count' protects 'rule' from being freed.  It doesn't protect the
- * rule from being deleted from 'cls' (that's 'cls->rwlock') and it doesn't
+ * rule from being deleted from 'cls' (that's 'ofproto_mutex') and it doesn't
  * protect members of 'rule' from modification (that's 'rule->mutex').
  *
  * 'rule->mutex' protects the members of 'rule' from modification.  It doesn't
- * protect the rule from being deleted from 'cls' (that's 'cls->rwlock') and it
- * doesn't prevent the rule from being freed (that's 'rule->ref_count').
+ * protect the rule from being deleted from 'cls' (that's 'ofproto_mutex') and
+ * it doesn't prevent the rule from being freed (that's 'rule->ref_count').
  *
  * Regarding thread safety, the members of a rule fall into the following
  * categories:
@@ -397,10 +396,9 @@ static inline bool rule_is_hidden(const struct rule *);
  * Thread-safety
  * =============
  *
- * A struct rule_actions may be accessed without a risk of being
- * freed by code that holds a read-lock or write-lock on 'rule->mutex' (where
- * 'rule' is the rule for which 'rule->actions == actions') or during the RCU
- * active period.
+ * A struct rule_actions may be accessed without a risk of being freed by
+ * code that holds 'rule->mutex' (where 'rule' is the rule for which
+ * 'rule->actions == actions') or during the RCU active period.
  *
  * All members are immutable: they do not change during the struct's
  * lifetime. */
diff --git a/ofproto/ofproto.c b/ofproto/ofproto.c
index 1666c8b6c..a1f73c07a 100644
--- a/ofproto/ofproto.c
+++ b/ofproto/ofproto.c
@@ -1214,12 +1214,11 @@ ofproto_configure_table(struct ofproto *ofproto, int table_id,
     }
 
     table->max_flows = s->max_flows;
-    fat_rwlock_wrlock(&table->cls.rwlock);
+
     if (classifier_set_prefix_fields(&table->cls,
                                      s->prefix_fields, s->n_prefix_fields)) {
         /* XXX: Trigger revalidation. */
     }
-    fat_rwlock_unlock(&table->cls.rwlock);
 
     ovs_mutex_lock(&ofproto_mutex);
     evict_rules_from_table(table, 0);
@@ -1551,9 +1550,7 @@ ofproto_get_memory_usage(const struct ofproto *ofproto, struct simap *usage)
 
     n_rules = 0;
     OFPROTO_FOR_EACH_TABLE (table, ofproto) {
-        fat_rwlock_rdlock(&table->cls.rwlock);
         n_rules += classifier_count(&table->cls);
-        fat_rwlock_unlock(&table->cls.rwlock);
     }
     simap_increase(usage, "rules", n_rules);
 
@@ -1841,7 +1838,6 @@ ofproto_add_flow(struct ofproto *ofproto, const struct match *match,
 
     /* First do a cheap check whether the rule we're looking for already exists
      * with the actions that we want.  If it does, then we're done. */
-    fat_rwlock_rdlock(&ofproto->tables[0].cls.rwlock);
     rule = rule_from_cls_rule(classifier_find_match_exactly(
                                   &ofproto->tables[0].cls, match, priority));
     if (rule) {
@@ -1851,7 +1847,6 @@ ofproto_add_flow(struct ofproto *ofproto, const struct match *match,
     } else {
         must_add = true;
     }
-    fat_rwlock_unlock(&ofproto->tables[0].cls.rwlock);
 
     /* If there's no such rule or the rule doesn't have the actions we want,
      * fall back to a executing a full flow mod.  We can't optimize this at
@@ -1882,7 +1877,6 @@ ofproto_flow_mod(struct ofproto *ofproto, struct ofputil_flow_mod *fm)
         struct rule *rule;
         bool done = false;
 
-        fat_rwlock_rdlock(&table->cls.rwlock);
         rule = rule_from_cls_rule(classifier_find_match_exactly(&table->cls,
                                                                 &fm->match,
                                                                 fm->priority));
@@ -1907,7 +1901,6 @@ ofproto_flow_mod(struct ofproto *ofproto, struct ofputil_flow_mod *fm)
             }
             ovs_mutex_unlock(&rule->mutex);
         }
-        fat_rwlock_unlock(&table->cls.rwlock);
 
         if (done) {
             return 0;
@@ -1931,10 +1924,8 @@ ofproto_delete_flow(struct ofproto *ofproto,
 
     /* First do a cheap check whether the rule we're looking for has already
      * been deleted.  If so, then we're done. */
-    fat_rwlock_rdlock(&cls->rwlock);
     rule = rule_from_cls_rule(classifier_find_match_exactly(cls, target,
                                                             priority));
-    fat_rwlock_unlock(&cls->rwlock);
     if (!rule) {
         return;
     }
@@ -3117,9 +3108,7 @@ handle_table_stats_request(struct ofconn *ofconn,
         ots[i].instructions = htonl(OFPIT11_ALL);
         ots[i].config = htonl(OFPTC11_TABLE_MISS_MASK);
         ots[i].max_entries = htonl(1000000); /* An arbitrary big number. */
-        fat_rwlock_rdlock(&p->tables[i].cls.rwlock);
         ots[i].active_count = htonl(classifier_count(&p->tables[i].cls));
-        fat_rwlock_unlock(&p->tables[i].cls.rwlock);
     }
 
     p->ofproto_class->get_tables(p, ots);
@@ -3552,10 +3541,8 @@ collect_rules_strict(struct ofproto *ofproto,
         FOR_EACH_MATCHING_TABLE (table, criteria->table_id, ofproto) {
             struct rule *rule;
 
-            fat_rwlock_rdlock(&table->cls.rwlock);
             rule = rule_from_cls_rule(classifier_find_rule_exactly(
                                           &table->cls, &criteria->cr));
-            fat_rwlock_unlock(&table->cls.rwlock);
             if (rule) {
                 collect_rule(rule, criteria, rules, &n_readonly);
             }
@@ -4009,9 +3996,7 @@ add_flow(struct ofproto *ofproto, struct ofputil_flow_mod *fm,
     cls_rule_init(&cr, &fm->match, fm->priority);
 
     /* Transform "add" into "modify" if there's an existing identical flow. */
-    fat_rwlock_rdlock(&table->cls.rwlock);
     rule = rule_from_cls_rule(classifier_find_rule_exactly(&table->cls, &cr));
-    fat_rwlock_unlock(&table->cls.rwlock);
     if (rule) {
         struct rule_collection rules;
 
@@ -4028,13 +4013,7 @@ add_flow(struct ofproto *ofproto, struct ofputil_flow_mod *fm,
 
     /* Check for overlap, if requested. */
     if (fm->flags & OFPUTIL_FF_CHECK_OVERLAP) {
-        bool overlaps;
-
-        fat_rwlock_rdlock(&table->cls.rwlock);
-        overlaps = classifier_rule_overlaps(&table->cls, &cr);
-        fat_rwlock_unlock(&table->cls.rwlock);
-
-        if (overlaps) {
+        if (classifier_rule_overlaps(&table->cls, &cr)) {
             cls_rule_destroy(&cr);
             return OFPERR_OFPFMFC_OVERLAP;
         }
@@ -4096,9 +4075,7 @@ add_flow(struct ofproto *ofproto, struct ofputil_flow_mod *fm,
         meter_insert_rule(rule);
     }
 
-    fat_rwlock_wrlock(&table->cls.rwlock);
     classifier_insert(&table->cls, CONST_CAST(struct cls_rule *, &rule->cr));
-    fat_rwlock_unlock(&table->cls.rwlock);
 
     error = ofproto->ofproto_class->rule_insert(rule);
     if (error) {
@@ -6372,10 +6349,8 @@ oftable_init(struct oftable *table)
     table->max_flows = UINT_MAX;
     atomic_init(&table->config, (unsigned int)OFPROTO_TABLE_MISS_DEFAULT);
 
-    fat_rwlock_wrlock(&table->cls.rwlock);
     classifier_set_prefix_fields(&table->cls, default_prefix_fields,
                                  ARRAY_SIZE(default_prefix_fields));
-    fat_rwlock_unlock(&table->cls.rwlock);
 
     atomic_init(&table->n_matched, 0);
     atomic_init(&table->n_missed, 0);
@@ -6387,9 +6362,7 @@ oftable_init(struct oftable *table)
 static void
 oftable_destroy(struct oftable *table)
 {
-    fat_rwlock_rdlock(&table->cls.rwlock);
     ovs_assert(classifier_is_empty(&table->cls));
-    fat_rwlock_unlock(&table->cls.rwlock);
     oftable_disable_eviction(table);
     classifier_destroy(&table->cls);
     free(table->name);
@@ -6482,9 +6455,7 @@ oftable_remove_rule__(struct ofproto *ofproto, struct rule *rule)
 {
     struct classifier *cls = &ofproto->tables[rule->table_id].cls;
 
-    fat_rwlock_wrlock(&cls->rwlock);
     classifier_remove(cls, CONST_CAST(struct cls_rule *, &rule->cr));
-    fat_rwlock_unlock(&cls->rwlock);
 
     cookies_remove(ofproto, rule);
 
diff --git a/ofproto/ofproto.h b/ofproto/ofproto.h
index beabcf21c..d6011814b 100644
--- a/ofproto/ofproto.h
+++ b/ofproto/ofproto.h
@@ -45,6 +45,9 @@ struct shash;
 struct simap;
 struct smap;
 
+/* Needed for the lock annotations. */
+extern struct ovs_mutex ofproto_mutex;
+
 struct ofproto_controller_info {
     bool is_connected;
     enum ofp12_controller_role role;