[ovs-dev] [PATCH] lib/classifier: Make classifier iteration more robust.

Jarno Rajahalme jrajahalme at nicira.com
Fri Oct 17 17:37:52 UTC 2014


I’ll see if we can make the iteration both safe and lockless, so there is no need to review this patch at this moment.

  Jarno

On Oct 16, 2014, at 4:24 PM, Jarno Rajahalme <jrajahalme at nicira.com> wrote:

> This patch changes the classifier internal mutex to a recursive type.
> This allows simplification of locking during iteration.
> 
> Accurate iteration requires classifier_inserts to be exluded during
> iteration.  To this end we take the internal mutex at the start of the
> iteration.  To allow rule removal while iterating, we have supported a
> 'SAFE' variant of the iterator, that used to release the mutex for the
> body of the iterator loop.  For a classifier user without additional
> locks this would have opened a possibility for another thread to issue
> classifier_insert()s during the iteration, potentially making the
> iteration to skip or duplicate entries due to cmap internal
> rearrangements.
> 
> This patch fixes the above keeping the writers excluded also in the
> safe mode, which is possible with a recursive mutex.  We also remove
> the distinction between 'SAFE' and normal iteration, as the only
> remaining difference was in the iterator for statement, and we can use
> the 'SAFE' variant in all cases without additional overhead.
> 
> Signed-off-by: Jarno Rajahalme <jrajahalme at nicira.com>
> ---
> lib/classifier.c        |   16 ++++++----------
> lib/classifier.h        |   33 ++++++++++++++-------------------
> ofproto/ofproto-dpif.c  |    2 +-
> ofproto/ofproto.c       |    2 +-
> tests/test-classifier.c |    5 ++---
> utilities/ovs-ofctl.c   |    2 +-
> 6 files changed, 25 insertions(+), 35 deletions(-)
> 
> diff --git a/lib/classifier.c b/lib/classifier.c
> index f30ba95..19a3435 100644
> --- a/lib/classifier.c
> +++ b/lib/classifier.c
> @@ -448,7 +448,7 @@ void
> classifier_init(struct classifier *cls, const uint8_t *flow_segments)
>     OVS_EXCLUDED(cls->mutex)
> {
> -    ovs_mutex_init(&cls->mutex);
> +    ovs_mutex_init_recursive(&cls->mutex);
>     ovs_mutex_lock(&cls->mutex);
>     cls->n_rules = 0;
>     cmap_init(&cls->subtables_map);
> @@ -1255,14 +1255,12 @@ search_subtable(const struct cls_subtable *subtable,
>  *
>  * Ignores target->priority. */
> struct cls_cursor cls_cursor_start(const struct classifier *cls,
> -                                   const struct cls_rule *target,
> -                                   bool safe)
> +                                   const struct cls_rule *target)
>     OVS_NO_THREAD_SAFETY_ANALYSIS
> {
>     struct cls_cursor cursor;
>     struct cls_subtable *subtable;
> 
> -    cursor.safe = safe;
>     cursor.cls = cls;
>     cursor.target = target && !cls_rule_is_catchall(target) ? target : NULL;
>     cursor.rule = NULL;
> @@ -1280,8 +1278,8 @@ struct cls_cursor cls_cursor_start(const struct classifier *cls,
>         }
>     }
> 
> -    /* Leave locked if requested and have a rule. */
> -    if (safe || !cursor.rule) {
> +    /* Release the lock if iteration ended already. */
> +    if (!cursor.rule) {
>         ovs_mutex_unlock(&cursor.cls->mutex);
>     }
>     return cursor;
> @@ -1328,11 +1326,9 @@ void
> cls_cursor_advance(struct cls_cursor *cursor)
>     OVS_NO_THREAD_SAFETY_ANALYSIS
> {
> -    if (cursor->safe) {
> -        ovs_mutex_lock(&cursor->cls->mutex);
> -    }
>     cursor->rule = cls_cursor_next(cursor);
> -    if (cursor->safe || !cursor->rule) {
> +    /* Release the lock if iteration ended. */
> +    if (!cursor->rule) {
>         ovs_mutex_unlock(&cursor->cls->mutex);
>     }
> }
> diff --git a/lib/classifier.h b/lib/classifier.h
> index d1f4e86..0d6ee2c 100644
> --- a/lib/classifier.h
> +++ b/lib/classifier.h
> @@ -319,39 +319,34 @@ struct cls_cursor {
>     struct cmap_cursor subtables;
>     struct cmap_cursor rules;
>     struct cls_rule *rule;
> -    bool safe;
> };
> 
> -/* Iteration requires mutual exclusion of writers.  We do this by taking
> - * a mutex for the duration of the iteration, except for the
> - * 'SAFE' variant, where we release the mutex for the body of the loop. */
> +/* Accurate iteration requires mutual exclusion of writers.  We do this by
> + * taking a classifier internal mutex for the duration of the iteration.  This
> + * implies that the iteration MUST NOT be terminated by jumping out of the loop
> + * with break or return statements, lest the classifier be left locked, and
> + * other threads deadlock.
> + *
> + * The iterating thread may modify the classifier itself.  However,
> + * classifier_insert()s can rearrange the internal structures so that the
> + * iteration can go through same rules twice or miss some rules altogether.
> + * classifier_replace() and classifier_remove() do not cause similar
> + * problems. */
> struct cls_cursor cls_cursor_start(const struct classifier *cls,
> -                                   const struct cls_rule *target,
> -                                   bool safe);
> +                                   const struct cls_rule *target);
> 
> void cls_cursor_advance(struct cls_cursor *);
> 
> #define CLS_FOR_EACH(RULE, MEMBER, CLS) \
>     CLS_FOR_EACH_TARGET(RULE, MEMBER, CLS, NULL)
> #define CLS_FOR_EACH_TARGET(RULE, MEMBER, CLS, TARGET)                  \
> -    for (struct cls_cursor cursor__ = cls_cursor_start(CLS, TARGET, false); \
> -         (cursor__.rule                                                 \
> -          ? (INIT_CONTAINER(RULE, cursor__.rule, MEMBER),               \
> -             true)                                                      \
> -          : false);                                                     \
> -         cls_cursor_advance(&cursor__))
> -
> -/* These forms allows classifier_remove() to be called within the loop. */
> -#define CLS_FOR_EACH_SAFE(RULE, MEMBER, CLS) \
> -    CLS_FOR_EACH_TARGET_SAFE(RULE, MEMBER, CLS, NULL)
> -#define CLS_FOR_EACH_TARGET_SAFE(RULE, MEMBER, CLS, TARGET)             \
> -    for (struct cls_cursor cursor__ = cls_cursor_start(CLS, TARGET, true); \
> +    for (struct cls_cursor cursor__ = cls_cursor_start(CLS, TARGET);    \
>          (cursor__.rule                                                 \
>           ? (INIT_CONTAINER(RULE, cursor__.rule, MEMBER),               \
>              cls_cursor_advance(&cursor__),                             \
>              true)                                                      \
>           : false);                                                     \
> -        )                                                               \
> +        )
> 
> #ifdef __cplusplus
> }
> diff --git a/ofproto/ofproto-dpif.c b/ofproto/ofproto-dpif.c
> index d965d38..1dfae96 100644
> --- a/ofproto/ofproto-dpif.c
> +++ b/ofproto/ofproto-dpif.c
> @@ -1375,7 +1375,7 @@ destruct(struct ofproto *ofproto_)
>     hmap_remove(&all_ofproto_dpifs, &ofproto->all_ofproto_dpifs_node);
> 
>     OFPROTO_FOR_EACH_TABLE (table, &ofproto->up) {
> -        CLS_FOR_EACH_SAFE (rule, up.cr, &table->cls) {
> +        CLS_FOR_EACH (rule, up.cr, &table->cls) {
>             ofproto_rule_delete(&ofproto->up, &rule->up);
>         }
>     }
> diff --git a/ofproto/ofproto.c b/ofproto/ofproto.c
> index 2cb93b0..34958ca 100644
> --- a/ofproto/ofproto.c
> +++ b/ofproto/ofproto.c
> @@ -1369,7 +1369,7 @@ ofproto_flush__(struct ofproto *ofproto)
>             continue;
>         }
> 
> -        CLS_FOR_EACH_SAFE (rule, cr, &table->cls) {
> +        CLS_FOR_EACH (rule, cr, &table->cls) {
>             ofproto_rule_delete__(rule, OFPRR_DELETE);
>         }
>     }
> diff --git a/tests/test-classifier.c b/tests/test-classifier.c
> index 0dfa910..74bfac5 100644
> --- a/tests/test-classifier.c
> +++ b/tests/test-classifier.c
> @@ -454,7 +454,7 @@ destroy_classifier(struct classifier *cls)
> {
>     struct test_rule *rule;
> 
> -    CLS_FOR_EACH_SAFE (rule, cls_rule, cls) {
> +    CLS_FOR_EACH (rule, cls_rule, cls) {
>         classifier_remove(cls, &rule->cls_rule);
>         free_rule(rule);
>     }
> @@ -1074,8 +1074,7 @@ test_many_rules_in_n_tables(int n_tables)
> 
>             target = clone_rule(tcls.rules[random_range(tcls.n_rules)]);
> 
> -            CLS_FOR_EACH_TARGET_SAFE (rule, cls_rule, &cls,
> -                                      &target->cls_rule) {
> +            CLS_FOR_EACH_TARGET (rule, cls_rule, &cls, &target->cls_rule) {
>                 classifier_remove(&cls, &rule->cls_rule);
>                 free_rule(rule);
>             }
> diff --git a/utilities/ovs-ofctl.c b/utilities/ovs-ofctl.c
> index ae8d59d..87b5406 100644
> --- a/utilities/ovs-ofctl.c
> +++ b/utilities/ovs-ofctl.c
> @@ -2330,7 +2330,7 @@ fte_free_all(struct classifier *cls)
> {
>     struct fte *fte;
> 
> -    CLS_FOR_EACH_SAFE (fte, rule, cls) {
> +    CLS_FOR_EACH (fte, rule, cls) {
>         classifier_remove(cls, &fte->rule);
>         fte_free(fte);
>     }
> -- 
> 1.7.10.4
> 




More information about the dev mailing list