[ovs-dev] [PATCH v2] datapath: Simplify flow mask cache delete.

Andy Zhou azhou at nicira.com
Thu Aug 14 07:06:34 UTC 2014


On Wed, Aug 13, 2014 at 10:19 PM, Pravin B Shelar <pshelar at nicira.com> wrote:
> Currently on mask delete OVS moves last mask to the deleted
> place to keep compact for per cpu cache. But this generate
> duplicate entries in mask cache array which results in
> multiple flow lookups in case we miss flow cache.
> Following patch simply sets NULL for deleted entry.
>
> Signed-off-by: Pravin B Shelar <pshelar at nicira.com>
> ---
>  datapath/flow_table.c | 107 ++++++++++++++++++++++----------------------------
>  1 file changed, 47 insertions(+), 60 deletions(-)
>
> diff --git a/datapath/flow_table.c b/datapath/flow_table.c
> index 7046623..81d3704 100644
> --- a/datapath/flow_table.c
> +++ b/datapath/flow_table.c
> @@ -223,6 +223,7 @@ static struct mask_array *tbl_mask_array_alloc(int size)
>  {
>         struct mask_array *new;
>
> +       size = max(MASK_ARRAY_SIZE_MIN, size);
>         new = kzalloc(sizeof(struct mask_array) +
>                       sizeof(struct sw_flow_mask *) * size, GFP_KERNEL);
>         if (!new)
> @@ -245,13 +246,14 @@ static int tbl_mask_array_realloc(struct flow_table *tbl, int size)
>
>         old = ovsl_dereference(tbl->mask_array);
>         if (old) {
> -               int i;
> +               int i, count = 0;
>
> -               for (i = 0; i < min(old->max, new->max); i++)
> -                       new->masks[i] = old->masks[i];
> +               for (i = 0; i < min(old->max, new->max); i++) {
Should this loop always end with old->max instead of min(old->max,
new-max)? Otherwise, it may miss masks when shrinking the array.

Looks good otherwise.
Acked-by: Andy Zhou <azhou at nicira.com>

> +                       if (ovsl_dereference(old->masks[i]))
> +                               new->masks[count++] = old->masks[i];
> +               }
>
> -               BUG_ON(old->count > new->max);
> -               new->count = old->count;
> +               new->count = count;
>         }
>         rcu_assign_pointer(tbl->mask_array, new);
>
> @@ -261,47 +263,6 @@ static int tbl_mask_array_realloc(struct flow_table *tbl, int size)
>         return 0;
>  }
>
> -static void tbl_mask_array_delete_mask(struct mask_array *ma,
> -                                      const struct sw_flow_mask *mask)
> -{
> -       int i = 0;
> -
> -       /* Delete a mask pointer from the valid section.
> -        *
> -        * Also move the last entry in its place, so there is no
> -        * whole in the valid section.
> -        *
> -        * Notice the last entry still points to the original mask.
> -        *
> -        * <Note>: there is a small race window that may cause a mask
> -        * to be missed in a search. Imaging a core is
> -        * walking through the array, passing the index of deleting mask.
> -        * But before reaching the last entry, it is overwritten,
> -        * by another core that is adding a new mask, now the last entry
> -        * will point to the new mask. In this case, the moved up last
> -        * entry can be missed by the core walking the mask array.
> -        *
> -        * In case this missed mask would have led to successful
> -        * lookup, Hitting the race window could cause a packet to miss
> -        * kernel flow cache, and be sent to the user space.
> -        * </Note>
> -        */
> -       for (i = 0; i < ma->count; i++)
> -               if (mask == ovsl_dereference(ma->masks[i])) {
> -                       struct sw_flow_mask *last;
> -
> -                       last = ovsl_dereference(ma->masks[ma->count - 1]);
> -                       rcu_assign_pointer(ma->masks[i], last);
> -                       ma->count--;
> -                       break;
> -               }
> -
> -       /* Remove the deleted mask pointers from the invalid section. */
> -       for (i = ma->count; i < ma->max; i++)
> -               if (mask == ovsl_dereference(ma->masks[i]))
> -                       RCU_INIT_POINTER(ma->masks[i], NULL);
> -}
> -
>  int ovs_flow_tbl_init(struct flow_table *table)
>  {
>         struct table_instance *ti;
> @@ -327,7 +288,7 @@ int ovs_flow_tbl_init(struct flow_table *table)
>         return 0;
>
>  free_mask_array:
> -       kfree((struct mask_array __force *)table->mask_array);
> +       kfree(ma);
>  free_mask_cache:
>         free_percpu(table->mask_cache);
>         return -ENOMEM;
> @@ -585,7 +546,7 @@ static struct sw_flow *flow_lookup(struct flow_table *tbl,
>
>                 mask = rcu_dereference_ovsl(ma->masks[i]);
>                 if (!mask)
> -                       return NULL;
> +                       continue;
>
>                 flow = masked_flow_lookup(ti, key, mask, n_mask_hit);
>                 if (flow) { /* Found */
> @@ -672,13 +633,15 @@ struct sw_flow *ovs_flow_tbl_lookup_exact(struct flow_table *tbl,
>         int i;
>
>         /* Always called under ovs-mutex. */
> -       for (i = 0; i < ma->count; i++) {
> +       for (i = 0; i < ma->max; i++) {
>                 struct table_instance *ti = ovsl_dereference(tbl->ti);
>                 u32 __always_unused n_mask_hit;
>                 struct sw_flow_mask *mask;
>                 struct sw_flow *flow;
>
>                 mask = ovsl_dereference(ma->masks[i]);
> +               if (!mask)
> +                       continue;
>                 flow = masked_flow_lookup(ti, match->key, mask, &n_mask_hit);
>                 if (flow && ovs_flow_cmp_unmasked_key(flow, match))
>                         return flow;
> @@ -699,6 +662,23 @@ static struct table_instance *table_instance_expand(struct table_instance *ti)
>         return table_instance_rehash(ti, ti->n_buckets * 2);
>  }
>
> +static void tbl_mask_array_delete_mask(struct mask_array *ma,
> +                                      struct sw_flow_mask *mask)
> +{
> +       int i;
> +
> +       /* Remove the deleted mask pointers from the array */
> +       for (i = 0; i < ma->max; i++) {
> +               if (mask == ovsl_dereference(ma->masks[i])) {
> +                       RCU_INIT_POINTER(ma->masks[i], NULL);
> +                       ma->count--;
> +                       call_rcu(&mask->rcu, rcu_free_sw_flow_mask_cb);
> +                       return;
> +               }
> +       }
> +       BUG();
> +}
> +
>  /* Remove 'mask' from the mask list, if it is not needed any more. */
>  static void flow_mask_remove(struct flow_table *tbl, struct sw_flow_mask *mask)
>  {
> @@ -714,16 +694,13 @@ static void flow_mask_remove(struct flow_table *tbl, struct sw_flow_mask *mask)
>                         struct mask_array *ma;
>
>                         ma = ovsl_dereference(tbl->mask_array);
> -                       /* Shrink the mask array if necessary. */
> -                       if (ma->max > MASK_ARRAY_SIZE_MIN * 2
> -                               && ma->count <= ma->max / 4) {
> +                       tbl_mask_array_delete_mask(ma, mask);
>
> +                       /* Shrink the mask array if necessary. */
> +                       if (ma->max >= (MASK_ARRAY_SIZE_MIN * 2) &&
> +                           ma->count <= (ma->max / 3))
>                                 tbl_mask_array_realloc(tbl, ma->max / 2);
> -                               ma = ovsl_dereference(tbl->mask_array);
> -                       }
>
> -                       tbl_mask_array_delete_mask(ma, mask);
> -                       call_rcu(&mask->rcu, rcu_free_sw_flow_mask_cb);
>                 }
>         }
>  }
> @@ -771,7 +748,7 @@ static struct sw_flow_mask *flow_mask_find(const struct flow_table *tbl,
>         int i;
>
>         ma = ovsl_dereference(tbl->mask_array);
> -       for (i = 0; i < ma->count; i++) {
> +       for (i = 0; i < ma->max; i++) {
>                 struct sw_flow_mask *t;
>
>                 t = ovsl_dereference(ma->masks[i]);
> @@ -791,6 +768,7 @@ static int flow_mask_insert(struct flow_table *tbl, struct sw_flow *flow,
>         mask = flow_mask_find(tbl, new);
>         if (!mask) {
>                 struct mask_array *ma;
> +               int i;
>
>                 /* Allocate a new mask if none exsits. */
>                 mask = mask_alloc();
> @@ -806,7 +784,7 @@ static int flow_mask_insert(struct flow_table *tbl, struct sw_flow *flow,
>                         int err;
>
>                         err = tbl_mask_array_realloc(tbl, ma->max +
> -                                                       MASK_ARRAY_SIZE_MIN);
> +                                                         MASK_ARRAY_SIZE_MIN);
>                         if (err) {
>                                 kfree(mask);
>                                 return err;
> @@ -814,8 +792,17 @@ static int flow_mask_insert(struct flow_table *tbl, struct sw_flow *flow,
>                         ma = ovsl_dereference(tbl->mask_array);
>                 }
>
> -               rcu_assign_pointer(ma->masks[ma->count], mask);
> -               ma->count++;
> +               for (i = 0; i < ma->max; i++) {
> +                       struct sw_flow_mask *t;
> +
> +                       t = ovsl_dereference(ma->masks[i]);
> +                       if (!t) {
> +                               rcu_assign_pointer(ma->masks[i], mask);
> +                               ma->count++;
> +                               break;
> +                       }
> +               }
> +
>         } else {
>                 BUG_ON(!mask->ref_count);
>                 mask->ref_count++;
> --
> 1.9.3
>
> _______________________________________________
> dev mailing list
> dev at openvswitch.org
> http://openvswitch.org/mailman/listinfo/dev



More information about the dev mailing list