diff mbox

[ovs-dev] classifier: Fix race condition leading to NULL dereference.

Message ID 1460867320-64278-1-git-send-email-jarno@ovn.org
State Accepted
Headers show

Commit Message

Jarno Rajahalme April 17, 2016, 4:28 a.m. UTC 
Addition of table versioning exposed struct cls_rule member
'cls_match' to RCU readers and made it possible for
'cls_match' become NULL while being accessed by an RCU reader, but we failed
to check for this condition.  This may have resulted in NULL pointer
dereference and ovs-vswitchd crash.

Fix this by making the 'cls_match' member an RCU pointer and checking
the value whenever it potentially read by an RCU reader.  In these
instances we use ovsrcu_get(), whereas functions accessible only by
the exclusive writers use ovsrcu_get_protected() and do not need to
check the result.

VMware-BZ: 1643642
Fixes: 2b7b1427 ("classifier: Support table versioning")
Signed-off-by: Jarno Rajahalme <jarno@ovn.org>
---
 lib/classifier.c        | 50 +++++++++++++++++++++++++++++++++----------------
 lib/classifier.h        | 36 +++++++++++++++++++----------------
 tests/test-classifier.c | 19 ++++++++++++-------
 3 files changed, 66 insertions(+), 39 deletions(-)

Comments

Ben Pfaff April 17, 2016, 5:08 a.m. UTC | #1 
On Sat, Apr 16, 2016 at 09:28:40PM -0700, Jarno Rajahalme wrote:
> Addition of table versioning exposed struct cls_rule member
> 'cls_match' to RCU readers and made it possible for
> 'cls_match' become NULL while being accessed by an RCU reader, but we failed
> to check for this condition.  This may have resulted in NULL pointer
> dereference and ovs-vswitchd crash.
> 
> Fix this by making the 'cls_match' member an RCU pointer and checking
> the value whenever it potentially read by an RCU reader.  In these
> instances we use ovsrcu_get(), whereas functions accessible only by
> the exclusive writers use ovsrcu_get_protected() and do not need to
> check the result.
> 
> VMware-BZ: 1643642
> Fixes: 2b7b1427 ("classifier: Support table versioning")
> Signed-off-by: Jarno Rajahalme <jarno@ovn.org>

Thank you for finding this!

I read the code carefully.  I also built it (on top of master) with
Clang 3.5 and GCC 4.9.1 (for i386), getting clean compiles and no
warnings from "sparse" either.  I also ran the testsuite and it passed.

I think that most of the changes to classifier.h are just reordering the
function prototypes.  I don't know why this order is being changed.
Maybe it is to group the comments better?  I don't know whether the
reordering is properly part of a minimal fix (since this will require
backporting); I'll leave that to your judgment.

This new comment in classifier.h could use a space at the end:

   /* Classifier rule properties.  These are RCU protected and may run
    * concurrently with modifiers and each other.*/

I think that the change to classifier_rule_overlaps() causes it to
inline cls_rule_visible_in_version(), so that it could be made clearer
by just calling that function directly.

The number of instances, with or without _protected, of
   ovsrcu_get(struct cls_match *, &rule->cls_match)
verges on wanting a pair of helper functions, especially since it would
probably reduce the amount of line-breaking.  Again I leave it to your
judgment.

Acked-by: Ben Pfaff <blp@ovn.org>

Thanks,

Ben.
Jarno Rajahalme April 17, 2016, 5:18 p.m. UTC | #2 
> On Apr 16, 2016, at 10:08 PM, Ben Pfaff <blp@ovn.org> wrote:
> 
> On Sat, Apr 16, 2016 at 09:28:40PM -0700, Jarno Rajahalme wrote:
>> Addition of table versioning exposed struct cls_rule member
>> 'cls_match' to RCU readers and made it possible for
>> 'cls_match' become NULL while being accessed by an RCU reader, but we failed
>> to check for this condition.  This may have resulted in NULL pointer
>> dereference and ovs-vswitchd crash.
>> 
>> Fix this by making the 'cls_match' member an RCU pointer and checking
>> the value whenever it potentially read by an RCU reader.  In these
>> instances we use ovsrcu_get(), whereas functions accessible only by
>> the exclusive writers use ovsrcu_get_protected() and do not need to
>> check the result.
>> 
>> VMware-BZ: 1643642
>> Fixes: 2b7b1427 ("classifier: Support table versioning")
>> Signed-off-by: Jarno Rajahalme <jarno@ovn.org>
> 
> Thank you for finding this!
> 
> I read the code carefully.  I also built it (on top of master) with
> Clang 3.5 and GCC 4.9.1 (for i386), getting clean compiles and no
> warnings from "sparse" either.  I also ran the testsuite and it passed.
> 

Thanks, I did not have the time last night to do all that!

> I think that most of the changes to classifier.h are just reordering the
> function prototypes.  I don't know why this order is being changed.
> Maybe it is to group the comments better?  I don't know whether the
> reordering is properly part of a minimal fix (since this will require
> backporting); I'll leave that to your judgment.
> 

I wanted it to be clearer which functions are to be called by the exclusive writer only, and which are for the RCU readers. I separated this re-organizing to a separate patch (which need not be backported).

> This new comment in classifier.h could use a space at the end:
> 
>   /* Classifier rule properties.  These are RCU protected and may run
>    * concurrently with modifiers and each other.*/
> 

Thanks!

> I think that the change to classifier_rule_overlaps() causes it to
> inline cls_rule_visible_in_version(), so that it could be made clearer
> by just calling that function directly.
> 

Right, thanks for spotting this.

> The number of instances, with or without _protected, of
>   ovsrcu_get(struct cls_match *, &rule->cls_match)
> verges on wanting a pair of helper functions, especially since it would
> probably reduce the amount of line-breaking.  Again I leave it to your
> judgment.
> 

I added helpers to classifier-private.h so that both classifier.c and test-classifier.c can share them.

> Acked-by: Ben Pfaff <blp@ovn.org <mailto:blp@ovn.org>>
> 

Pushed to master, and backported to branches 2.5 and 2.4.

  Jarno

> Thanks,
> 
> Ben.
diff mbox

Patch

diff --git a/lib/classifier.c b/lib/classifier.c
index b30ae66..7d2bbaf 100644
--- a/lib/classifier.c
+++ b/lib/classifier.c
@@ -172,7 +172,7 @@  cls_rule_init__(struct cls_rule *rule, unsigned int priority)
 {
     rculist_init(&rule->node);
     *CONST_CAST(int *, &rule->priority) = priority;
-    rule->cls_match = NULL;
+    ovsrcu_init(&rule->cls_match, NULL);
 }
 
 /* Initializes 'rule' to match packets specified by 'match' at the given
@@ -230,7 +230,8 @@  void
 cls_rule_destroy(struct cls_rule *rule)
     OVS_NO_THREAD_SAFETY_ANALYSIS
 {
-    ovs_assert(!rule->cls_match);   /* Must not be in a classifier. */
+    /* Must not be in a classifier. */
+    ovs_assert(!ovsrcu_get_protected(struct cls_match *, &rule->cls_match));
 
     /* Check that the rule has been properly removed from the classifier. */
     ovs_assert(rule->node.prev == RCULIST_POISON
@@ -244,7 +245,8 @@  void
 cls_rule_set_conjunctions(struct cls_rule *cr,
                           const struct cls_conjunction *conj, size_t n)
 {
-    struct cls_match *match = cr->cls_match;
+    struct cls_match *match = ovsrcu_get_protected(struct cls_match *,
+                                                   &cr->cls_match);
     struct cls_conjunction_set *old
         = ovsrcu_get_protected(struct cls_conjunction_set *, &match->conj_set);
     struct cls_conjunction *old_conj = old ? old->conj : NULL;
@@ -285,23 +287,31 @@  cls_rule_is_catchall(const struct cls_rule *rule)
 /* Makes 'rule' invisible in 'remove_version'.  Once that version is used in
  * lookups, the caller should remove 'rule' via ovsrcu_postpone().
  *
- * 'rule' must be in a classifier. */
+ * 'rule' must be in a classifier.
+ * This may only be called by the exclusive writer. */
 void
 cls_rule_make_invisible_in_version(const struct cls_rule *rule,
                                    cls_version_t remove_version)
 {
-    ovs_assert(remove_version >= rule->cls_match->add_version);
+    struct cls_match *cls_match;
+
+    cls_match = ovsrcu_get_protected(struct cls_match *, &rule->cls_match);
 
-    cls_match_set_remove_version(rule->cls_match, remove_version);
+    ovs_assert(remove_version >= cls_match->add_version);
+
+    cls_match_set_remove_version(cls_match, remove_version);
 }
 
 /* This undoes the change made by cls_rule_make_invisible_in_version().
  *
- * 'rule' must be in a classifier. */
+ * 'rule' must be in a classifier.
+ * This may only be called by the exclusive writer. */
 void
 cls_rule_restore_visibility(const struct cls_rule *rule)
 {
-    cls_match_set_remove_version(rule->cls_match, CLS_NOT_REMOVED_VERSION);
+    cls_match_set_remove_version(ovsrcu_get_protected(struct cls_match *,
+                                                      &rule->cls_match),
+                                 CLS_NOT_REMOVED_VERSION);
 }
 
 /* Return true if 'rule' is visible in 'version'.
@@ -310,7 +320,10 @@  cls_rule_restore_visibility(const struct cls_rule *rule)
 bool
 cls_rule_visible_in_version(const struct cls_rule *rule, cls_version_t version)
 {
-    return cls_match_visible_in_version(rule->cls_match, version);
+    struct cls_match *cls_match = ovsrcu_get(struct cls_match *,
+                                             &rule->cls_match);
+
+    return cls_match && cls_match_visible_in_version(cls_match, version);
 }
 
 /* Initializes 'cls' as a classifier that initially contains no classification
@@ -540,8 +553,7 @@  classifier_replace(struct classifier *cls, const struct cls_rule *rule,
 
     /* 'new' is initially invisible to lookups. */
     new = cls_match_alloc(rule, version, conjs, n_conjs);
-
-    CONST_CAST(struct cls_rule *, rule)->cls_match = new;
+    ovsrcu_set(&CONST_CAST(struct cls_rule *, rule)->cls_match, new);
 
     subtable = find_subtable(cls, rule->match.mask);
     if (!subtable) {
@@ -636,8 +648,9 @@  classifier_replace(struct classifier *cls, const struct cls_rule *rule,
                     ovsrcu_postpone(free, conj_set);
                 }
 
+                ovsrcu_set(&old->cls_match, NULL); /* Marks old rule as removed
+                                                    * from the classifier. */
                 ovsrcu_postpone(cls_match_free_cb, iter);
-                old->cls_match = NULL;
 
                 /* No change in subtable's max priority or max count. */
 
@@ -728,12 +741,12 @@  classifier_remove(struct classifier *cls, const struct cls_rule *cls_rule)
     size_t n_rules;
     unsigned int i;
 
-    rule = cls_rule->cls_match;
+    rule = ovsrcu_get_protected(struct cls_match *, &cls_rule->cls_match);
     if (!rule) {
         return NULL;
     }
     /* Mark as removed. */
-    CONST_CAST(struct cls_rule *, cls_rule)->cls_match = NULL;
+    ovsrcu_set(&CONST_CAST(struct cls_rule *, cls_rule)->cls_match, NULL);
 
     /* Remove 'cls_rule' from the subtable's rules list. */
     rculist_remove(CONST_CAST(struct rculist *, &cls_rule->node));
@@ -1258,10 +1271,15 @@  classifier_rule_overlaps(const struct classifier *cls,
                          m.storage);
 
         RCULIST_FOR_EACH (rule, node, &subtable->rules_list) {
+            struct cls_match *cls_match;
+
+            cls_match = ovsrcu_get(struct cls_match *, &rule->cls_match);
+
             if (rule->priority == target->priority
                 && miniflow_equal_in_minimask(target->match.flow,
                                               rule->match.flow, &m.mask)
-                && cls_match_visible_in_version(rule->cls_match, version)) {
+                && cls_match
+                && cls_match_visible_in_version(cls_match, version)) {
                 return true;
             }
         }
@@ -1318,7 +1336,7 @@  rule_matches(const struct cls_rule *rule, const struct cls_rule *target,
              cls_version_t version)
 {
     /* Rule may only match a target if it is visible in target's version. */
-    return cls_match_visible_in_version(rule->cls_match, version)
+    return cls_rule_visible_in_version(rule, version)
         && (!target || miniflow_equal_in_minimask(rule->match.flow,
                                                   target->match.flow,
                                                   target->match.mask));
diff --git a/lib/classifier.h b/lib/classifier.h
index 57a9593..0183bf1 100644
--- a/lib/classifier.h
+++ b/lib/classifier.h
@@ -357,9 +357,19 @@  struct cls_conjunction {
 struct cls_rule {
     struct rculist node;          /* In struct cls_subtable 'rules_list'. */
     const int priority;           /* Larger numbers are higher priorities. */
-    struct cls_match *cls_match;  /* NULL if not in a classifier. */
+    OVSRCU_TYPE(struct cls_match *) cls_match;  /* NULL if not in a
+                                                 * classifier. */
     const struct minimatch match; /* Matching rule. */
 };
+
+/* 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);
 
 void cls_rule_init(struct cls_rule *, const struct match *, int priority);
 void cls_rule_init_from_minimatch(struct cls_rule *, const struct minimatch *,
@@ -370,25 +380,10 @@  void cls_rule_destroy(struct cls_rule *);
 
 void cls_rule_set_conjunctions(struct cls_rule *,
                                const struct cls_conjunction *, size_t n);
-
-bool cls_rule_equal(const struct cls_rule *, const struct cls_rule *);
-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);
-bool cls_rule_visible_in_version(const struct cls_rule *, cls_version_t);
 void cls_rule_make_invisible_in_version(const struct cls_rule *,
                                         cls_version_t);
 void cls_rule_restore_visibility(const struct cls_rule *);
 
-/* 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);
 void classifier_insert(struct classifier *, const struct cls_rule *,
                        cls_version_t, const struct cls_conjunction *,
                        size_t n_conjunctions);
@@ -418,6 +413,15 @@  const struct cls_rule *classifier_find_match_exactly(const struct classifier *,
                                                      cls_version_t);
 bool classifier_is_empty(const struct classifier *);
 int classifier_count(const struct classifier *);
+
+/* Classifier rule properties.  These are RCU protected and may run
+ * concurrently with modifiers and each other.*/
+bool cls_rule_equal(const struct cls_rule *, const struct cls_rule *);
+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);
+bool cls_rule_visible_in_version(const struct cls_rule *, cls_version_t);
 
 /* Iteration.
  *
diff --git a/tests/test-classifier.c b/tests/test-classifier.c
index 0242f6aa..f609de7 100644
--- a/tests/test-classifier.c
+++ b/tests/test-classifier.c
@@ -450,8 +450,7 @@  compare_classifiers(struct classifier *cls, size_t n_invisible_rules,
             assert(tr0->aux == tr1->aux);
 
             /* Make sure the rule should have been visible. */
-            assert(cr0->cls_match);
-            assert(cls_match_visible_in_version(cr0->cls_match, version));
+            assert(cls_rule_visible_in_version(cr0, version));
         }
         cr2 = classifier_lookup(cls, version, &flow, NULL);
         assert(cr2 == cr0);
@@ -611,16 +610,19 @@  check_tables(const struct classifier *cls, int n_tables, int n_rules,
                 found_rule = classifier_find_rule_exactly(cls, rule->cls_rule,
                                                           rule_version);
                 if (found_rule && found_rule != rule->cls_rule) {
+                    struct cls_match *cls_match;
+                    cls_match = ovsrcu_get_protected(struct cls_match *,
+                                                     &found_rule->cls_match);
 
                     assert(found_rule->priority == rule->priority);
 
                     /* Found rule may not have a lower version. */
-                    assert(found_rule->cls_match->add_version >= rule_version);
+                    assert(cls_match->add_version >= rule_version);
 
                     /* This rule must not be visible in the found rule's
                      * version. */
                     assert(!cls_match_visible_in_version(
-                               rule, found_rule->cls_match->add_version));
+                               rule, cls_match->add_version));
                 }
 
                 if (rule->priority == prev_priority) {
@@ -1030,10 +1032,13 @@  test_many_rules_in_one_list (struct ovs_cmdl_context *ctx OVS_UNUSED)
                              version);
 
                 if (versioned && removable_rule) {
+                    struct cls_match *cls_match =
+                        ovsrcu_get_protected(struct cls_match *,
+                                             &removable_rule->cls_match);
+
                     /* Removable rule is no longer visible. */
-                    assert(removable_rule->cls_match);
-                    assert(!cls_match_visible_in_version(
-                               removable_rule->cls_match, version));
+                    assert(cls_match);
+                    assert(!cls_match_visible_in_version(cls_match, version));
                     classifier_remove(&cls, removable_rule);
                     n_invisible_rules--;
                 }