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

Andy Zhou azhou at nicira.com
Thu Aug 14 01:55:25 UTC 2014


On Wed, Aug 13, 2014 at 2:43 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.
>
Does tbl_mask_array_realloc() also need to be changed to skip NULL entries?

> Signed-off-by: Pravin B Shelar <pshelar at nicira.com>
> ---
>  datapath/flow_table.c | 108 +++++++++++++++++++++-----------------------------
>  1 file changed, 45 insertions(+), 63 deletions(-)
>
> diff --git a/datapath/flow_table.c b/datapath/flow_table.c
> index 7046623..7b8b00d 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)
> @@ -261,47 +262,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 +287,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 +545,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 +632,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 +661,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);
Will it be better to use rcu_assign_pointer?
> +                       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 +693,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 +747,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 +767,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, err;
>
>                 /* Allocate a new mask if none exsits. */
>                 mask = mask_alloc();
> @@ -800,27 +777,32 @@ static int flow_mask_insert(struct flow_table *tbl, struct sw_flow *flow,
>                 mask->key = new->key;
>                 mask->range = new->range;
>
> +retry:
>                 /* Add mask to mask-list. */
>                 ma = ovsl_dereference(tbl->mask_array);
> -               if (ma->count >= ma->max) {
> -                       int err;
> -
> -                       err = tbl_mask_array_realloc(tbl, ma->max +
> -                                                       MASK_ARRAY_SIZE_MIN);
> -                       if (err) {
> -                               kfree(mask);
> -                               return err;
> +               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++;
> +                               goto out;
>                         }
> -                       ma = ovsl_dereference(tbl->mask_array);
>                 }
>
> -               rcu_assign_pointer(ma->masks[ma->count], mask);
> -               ma->count++;
> +               err = tbl_mask_array_realloc(tbl, ma->max + MASK_ARRAY_SIZE_MIN);
> +               if (err) {
> +                       kfree(mask);
> +                       return err;
> +               }
> +               goto retry;
Why not use 'count' to figure out if we need a bigger array to begin
with? Then we can
avoid the retry here.
>         } else {
>                 BUG_ON(!mask->ref_count);
>                 mask->ref_count++;
>         }
>
> +out:
>         flow->mask = mask;
>         return 0;
>  }
> --
> 1.9.3
>
> _______________________________________________
> dev mailing list
> dev at openvswitch.org
> http://openvswitch.org/mailman/listinfo/dev



More information about the dev mailing list