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 <jrajaha...@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 <jrajaha...@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
>
_______________________________________________
dev mailing list
dev@openvswitch.org
http://openvswitch.org/mailman/listinfo/dev
