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

Pravin Shelar pshelar at nicira.com
Thu Aug 14 19:32:02 UTC 2014


On Thu, Aug 14, 2014 at 12:06 AM, Andy Zhou <azhou at nicira.com> wrote:
> 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.
>
Right, I fixed it.

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

I pushed it to master and branch 2.3.

Thanks.

>
>> +                       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