[ovs-dev] [PATCH v3 1/5] classifier: integrate insert_rule().

Jarno Rajahalme jrajahalme at nicira.com
Wed Nov 12 22:31:48 UTC 2014


On Nov 12, 2014, at 1:06 PM, Ben Pfaff <blp at nicira.com> wrote:

> On Tue, Nov 11, 2014 at 04:46:10PM -0800, Ben Pfaff wrote:
>> On Tue, Nov 11, 2014 at 12:00:59PM -0800, Jarno Rajahalme wrote:
>>> This patch integrates insert_rule() to the sole caller
>>> classifier_replace().  This makes classifer_replace() more symmetric
>>> with classifier_remove(), and makes it easier to change the following:
>>> 
>>> - Rules invisible to the lookups are no longer inserted to any of the
>>>  index cmaps or tries.
>>> - subtable's 'n_rules' member is eliminated.
>>> 
>>> Signed-off-by: Jarno Rajahalme <jrajahalme at nicira.com>
>> 
>> I don't understand from the commit message above whether this just
>> moves code around or actually changes what it does.  It's usually easy
>> to review a patch that moves code around, it's usually easy to review
>> a patch that just changes code, but a patch that does both at once is
>> harder, and I'm not sure which I'm looking at here.  Let me know?
> 
> I see that it does both at once.
> 
> How about the following as a preliminary commit that just does the
> integration work?

Thats fine, sorry for making you do that, I’ll resend the series with this.

  Jarno

> 
> --8<--------------------------cut here-------------------------->8--
> 
> From: Ben Pfaff <blp at nicira.com>
> Date: Wed, 12 Nov 2014 13:05:35 -0800
> Subject: [PATCH] classifier: Integrate insert_rule() into
> classifier_replace().
> 
> insert_rule() only had one caller and this makes the code easier to
> understand.
> 
> Signed-off-by: Ben Pfaff <blp at nicira.com>
> ---
> lib/classifier.c | 210 ++++++++++++++++++++++++++-----------------------------
> 1 file changed, 98 insertions(+), 112 deletions(-)
> 
> diff --git a/lib/classifier.c b/lib/classifier.c
> index c19d81c..8617a08 100644
> --- a/lib/classifier.c
> +++ b/lib/classifier.c
> @@ -60,9 +60,6 @@ static struct cls_subtable *insert_subtable(struct classifier *cls,
>     OVS_REQUIRES(cls->mutex);
> static void destroy_subtable(struct classifier *cls, struct cls_subtable *)
>     OVS_REQUIRES(cls->mutex);
> -static struct cls_match *insert_rule(struct classifier *cls,
> -                                     struct cls_subtable *, struct cls_rule *)
> -    OVS_REQUIRES(cls->mutex);
> 
> static const struct cls_match *find_match_wc(const struct cls_subtable *,
>                                              const struct flow *,
> @@ -478,14 +475,22 @@ static inline ovs_be32 minimatch_get_ports(const struct minimatch *match)
>  * Returns NULL if 'cls' does not contain a rule with an identical key, after
>  * inserting the new rule.  In this case, no rules are displaced by the new
>  * rule, even rules that cannot have any effect because the new rule matches a
> - * superset of their flows and has higher priority. */
> + * superset of their flows and has higher priority.
> + */
> const struct cls_rule *
> classifier_replace(struct classifier *cls, struct cls_rule *rule)
>     OVS_EXCLUDED(cls->mutex)
> {
> -    struct cls_match *old_rule;
> +    struct cls_match *new = cls_match_alloc(rule);
> +    struct cls_match *old_rule = NULL;
>     struct cls_subtable *subtable;
>     const struct cls_rule *old_cls_rule = NULL;
> +    uint32_t ihash[CLS_MAX_INDICES];
> +    uint8_t prev_be32ofs = 0;
> +    struct cls_match *head;
> +    uint32_t basis;
> +    uint32_t hash;
> +    int i;
> 
>     ovs_mutex_lock(&cls->mutex);
>     subtable = find_subtable(cls, &rule->match.mask);
> @@ -493,10 +498,80 @@ classifier_replace(struct classifier *cls, struct cls_rule *rule)
>         subtable = insert_subtable(cls, &rule->match.mask);
>     }
> 
> -    old_rule = insert_rule(cls, subtable, rule);
> +
> +    /* Add new node to segment indices.
> +     *
> +     * 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 later by revalidation (always scheduled after flow table
> +     * changes). */
> +    basis = 0;
> +    for (i = 0; i < subtable->n_indices; i++) {
> +        ihash[i] = minimatch_hash_range(&rule->match, prev_be32ofs,
> +                                        subtable->index_ofs[i], &basis);
> +        cmap_insert(&subtable->indices[i], &new->index_nodes[i], ihash[i]);
> +        prev_be32ofs = subtable->index_ofs[i];
> +    }
> +    hash = minimatch_hash_range(&rule->match, prev_be32ofs, FLOW_U32S,
> +                                &basis);
> +    head = find_equal(subtable, &rule->match.flow, hash);
> +    if (!head) {
> +        cmap_insert(&subtable->rules, &new->cmap_node, hash);
> +        rculist_init(&new->list);
> +    } else {
> +        /* Scan the list for the insertion point that will keep the list in
> +         * order of decreasing priority. */
> +        struct cls_match *iter;
> +
> +        FOR_EACH_RULE_IN_LIST_PROTECTED (iter, head) {
> +            if (new->priority >= iter->priority) {
> +                if (iter == head) {
> +                    /* 'new' is the new highest-priority flow in the list. */
> +                    cmap_replace(&subtable->rules, &iter->cmap_node,
> +                                 &new->cmap_node, hash);
> +                }
> +
> +                if (new->priority == iter->priority) {
> +                    rculist_replace(&new->list, &iter->list);
> +                    old_rule = iter;
> +                } else {
> +                    rculist_insert(&iter->list, &new->list);
> +                }
> +                goto out;
> +            }
> +        }
> +
> +        /* Insert 'new' at the end of the list. */
> +        rculist_push_back(&head->list, &new->list);
> +    out:;
> +    }
> +
>     if (!old_rule) {
>         old_cls_rule = NULL;
> +        subtable->n_rules++;
> +
> +        /* Rule was added, not replaced.  Update 'subtable's 'max_priority'
> +         * and 'max_count', if necessary.
> +         *
> +         * The rule was already inserted, so concurrent readers may not see the
> +         * rule.  This will have to be fixed by revalidation later. */
> +        if (subtable->n_rules == 1) {
> +            subtable->max_priority = new->priority;
> +            subtable->max_count = 1;
> +            pvector_insert(&cls->subtables, subtable, new->priority);
> +        } else if (subtable->max_priority == new->priority) {
> +            ++subtable->max_count;
> +        } else if (new->priority > subtable->max_priority) {
> +            subtable->max_priority = new->priority;
> +            subtable->max_count = 1;
> +            pvector_change_priority(&cls->subtables, subtable, new->priority);
> +        }
> 
> +        /* Add rule to partitions.
> +         *
> +         * Concurrent readers might miss seeing the rule until this update,
> +         * which might require being fixed up by revalidation later. */
>         rule->cls_match->partition = NULL;
>         if (minimask_get_metadata_mask(&rule->match.mask) == OVS_BE64_MAX) {
>             ovs_be64 metadata = miniflow_get_metadata(&rule->match.flow);
> @@ -506,13 +581,17 @@ classifier_replace(struct classifier *cls, struct cls_rule *rule)
> 
>         cls->n_rules++;
> 
> +        /* Add rule to tries.
> +         *
> +         * Concurrent readers might miss seeing the rule until this update,
> +         * which might require being fixed up by revalidation later. */
>         for (int i = 0; i < cls->n_tries; i++) {
>             if (subtable->trie_plen[i]) {
>                 trie_insert(&cls->tries[i], rule, subtable->trie_plen[i]);
>             }
>         }
> 
> -        /* Ports trie. */
> +        /* Add rule to ports trie. */
>         if (subtable->ports_mask_len) {
>             /* We mask the value to be inserted to always have the wildcarded
>              * bits in known (zero) state, so we can include them in comparison
> @@ -525,6 +604,17 @@ classifier_replace(struct classifier *cls, struct cls_rule *rule)
>         }
>     } else {
>         old_cls_rule = old_rule->cls_rule;
> +
> +        /* Remove old node from indices.
> +         *
> +         * The effect of this late removal on concurrency is similar to that of
> +         * adding the new rule to the segment indices early (at the beginning
> +         * of this function.) */
> +        for (i = 0; i < subtable->n_indices; i++) {
> +            cmap_remove(&subtable->indices[i], &old_rule->index_nodes[i],
> +                        ihash[i]);
> +        }
> +
>         rule->cls_match->partition = old_rule->partition;
>         CONST_CAST(struct cls_rule *, old_cls_rule)->cls_match = NULL;
> 
> @@ -532,6 +622,7 @@ classifier_replace(struct classifier *cls, struct cls_rule *rule)
>          * immediately. */
>         ovsrcu_postpone(free, old_rule);
>     }
> +
>     ovs_mutex_unlock(&cls->mutex);
>     return old_cls_rule;
> }
> @@ -1360,111 +1451,6 @@ find_equal(const struct cls_subtable *subtable, const struct miniflow *flow,
>     return NULL;
> }
> 
> -/*
> - * As the readers are operating concurrently with the modifications, a
> - * concurrent reader may or may not see the new rule, depending on how
> - * the concurrent events overlap with each other.  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.
> - *
> - * The 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 new rule has been added.
> - *
> - * The subtable's max priority is updated only after the rule is
> - * inserted, 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 for new rules are updated by
> - * the caller after this function, so the readers may keep skipping
> - * the subtable until they see the updated partitions.
> - */
> -static struct cls_match *
> -insert_rule(struct classifier *cls, struct cls_subtable *subtable,
> -            struct cls_rule *new_rule)
> -    OVS_REQUIRES(cls->mutex)
> -{
> -    struct cls_match *old = NULL;
> -    struct cls_match *new = cls_match_alloc(new_rule);
> -    struct cls_match *head;
> -    int i;
> -    uint32_t basis = 0, hash, ihash[CLS_MAX_INDICES];
> -    uint8_t prev_be32ofs = 0;
> -
> -    /* Add new node to segment indices. */
> -    for (i = 0; i < subtable->n_indices; i++) {
> -        ihash[i] = minimatch_hash_range(&new_rule->match, prev_be32ofs,
> -                                        subtable->index_ofs[i], &basis);
> -        cmap_insert(&subtable->indices[i], &new->index_nodes[i], ihash[i]);
> -        prev_be32ofs = subtable->index_ofs[i];
> -    }
> -    hash = minimatch_hash_range(&new_rule->match, prev_be32ofs, FLOW_U32S,
> -                                &basis);
> -    head = find_equal(subtable, &new_rule->match.flow, hash);
> -    if (!head) {
> -        cmap_insert(&subtable->rules, &new->cmap_node, hash);
> -        rculist_init(&new->list);
> -        goto out;
> -    } else {
> -        /* Scan the list for the insertion point that will keep the list in
> -         * order of decreasing priority. */
> -        struct cls_match *rule;
> -
> -        FOR_EACH_RULE_IN_LIST_PROTECTED (rule, head) {
> -            if (new->priority >= rule->priority) {
> -                if (rule == head) {
> -                    /* 'new' is the new highest-priority flow in the list. */
> -                    cmap_replace(&subtable->rules, &rule->cmap_node,
> -                                 &new->cmap_node, hash);
> -                }
> -
> -                if (new->priority == rule->priority) {
> -                    rculist_replace(&new->list, &rule->list);
> -                    old = rule;
> -                } else {
> -                    rculist_insert(&rule->list, &new->list);
> -                }
> -                goto out;
> -            }
> -        }
> -
> -        /* Insert 'new' at the end of the list. */
> -        rculist_push_back(&head->list, &new->list);
> -    }
> -
> - out:
> -    if (!old) {
> -        subtable->n_rules++;
> -
> -        /* Rule was added, not replaced.  Update 'subtable's 'max_priority'
> -         * and 'max_count', if necessary. */
> -        if (subtable->n_rules == 1) {
> -            subtable->max_priority = new->priority;
> -            subtable->max_count = 1;
> -            pvector_insert(&cls->subtables, subtable, new->priority);
> -        } else if (subtable->max_priority == new->priority) {
> -            ++subtable->max_count;
> -        } else if (new->priority > subtable->max_priority) {
> -            subtable->max_priority = new->priority;
> -            subtable->max_count = 1;
> -            pvector_change_priority(&cls->subtables, subtable, new->priority);
> -        }
> -    } else {
> -        /* Remove old node from indices. */
> -        for (i = 0; i < subtable->n_indices; i++) {
> -            cmap_remove(&subtable->indices[i], &old->index_nodes[i], ihash[i]);
> -        }
> -    }
> -    return old;
> -}
> 
> /* A longest-prefix match tree. */
> 
> -- 
> 2.1.1




More information about the dev mailing list