[ovs-dev] [PATCH] datapath: keep mask array compact when deleting mask

Andy Zhou azhou at nicira.com
Thu May 15 21:16:27 UTC 2014


On Thu, May 15, 2014 at 1:50 PM, Pravin Shelar <pshelar at nicira.com> wrote:
> On Thu, May 8, 2014 at 11:19 PM, Andy Zhou <azhou at nicira.com> wrote:
>> When deleting a mask from the mask array, we always move the last entry
>> into its current location. Another approach can be NULL in its current
>> place, and periodically compact it.
>>
>> The approach taken by this patch is more efficient during run time.
>> During look up, fast path packet don't have to skip over NULL pointers.
>>
>> A more important advantage of this approach is that it tries to
>> keep the mask array index stable by avoiding periodic index reshuffle.
>>
>> This patch implements an optimization to further promote index
>> stability.  By leaving the last entry value intact when moving it to
>> a new location, the old cache index can 'fix' themselves, by noticing
>> the index in the cache is outside the valid mask array region. The new
>> index can be found by scanning the mask pointer within the valid region.
>>
> This looks better solution.
Thanks.
>
>> Signed-off-by: Andy Zhou <azhou at nicira.com>
>> ---
>>  datapath/flow_table.c | 114 ++++++++++++++++++++++++++++++++++++--------------
>>  1 file changed, 82 insertions(+), 32 deletions(-)
>>
>> diff --git a/datapath/flow_table.c b/datapath/flow_table.c
>> index 58a25c7..0bc114c 100644
>> --- a/datapath/flow_table.c
>> +++ b/datapath/flow_table.c
>> @@ -247,10 +247,10 @@ static int tbl_mask_array_realloc(struct flow_table *tbl, int size)
>>         if (old) {
>>                 int i;
>>
>> -               for (i = 0; i < old->max; i++) {
>> -                       if (old->masks[i])
>> -                               new->masks[new->count++] = old->masks[i];
>> -               }
>> +               for (i = 0; i < old->max; i++)
>> +                       new->masks[i] = old->masks[i];
>> +
>> +               new->count = old->count;
>>         }
>>         rcu_assign_pointer(tbl->mask_array, new);
>>
>> @@ -260,6 +260,54 @@ 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 pints the original mask.
>> +        */
>> +       while (i < ma->count - 1) {
>> +               if (!mask || mask == ma->masks[i]) {
> I am not sure if this can ever be NULL.
It should not be, I will drop this check.
>
>> +                       struct sw_flow_mask *last;
>> +
>> +                       last = ma->masks[ma->count-1];
>> +                       rcu_assign_pointer(ma->masks[i], last);
>> +                       ma->count--;
>> +               } else
>> +                       i++;
>> +       }
>> +
> Entries less than count should be unique so once entry is found we can
> break it. we could assert if entry is not found.
Agree. I will make the change.
>
>> +       /* Delete mask pointers from the invalid section.
>> +        *
>> +        * Set them NULL to prevent future references.
>> +        */
>> +       for (; i < ma->max; i++) {
>> +               if (mask == ma->masks[i])
>> +                       RCU_INIT_POINTER(ma->masks[i], NULL);
>> +
>> +               if (i == ma->count)
>> +                       ma->count--;
>
> In which case is this possible?
Good catch. This should have been (i == ma->count -1). The loop above
should have terminated with ma->count - 2.
>
>> +       }
>> +}
>> +
>> +static int tbl_mask_array_find_idx(struct mask_array *ma,
>> +                                   const struct sw_flow_mask *mask)
>> +{
>> +       int i;
>> +
>> +       for (i = 0; i < ma->count; i++)
>> +               if (mask == ovsl_dereference(ma->masks[i]))
>> +                       return i;
>> +
>> +       return -1;
>> +}
>> +
>>  int ovs_flow_tbl_init(struct flow_table *table)
>>  {
>>         struct table_instance *ti;
>> @@ -524,7 +572,7 @@ static struct sw_flow *flow_lookup(struct flow_table *tbl,
>>         struct sw_flow *flow;
>>         int i;
>>
>> -       for (i = 0; i < ma->max; i++) {
>> +       for (i = 0; i < ma->count; i++) {
>>                 struct sw_flow_mask *mask;
>>
>>                 mask = rcu_dereference_ovsl(ma->masks[i]);
>> @@ -578,15 +626,34 @@ struct sw_flow *ovs_flow_tbl_lookup_stats(struct flow_table *tbl,
>>                 if (ce->skb_hash == skb_hash) {
>>                         struct sw_flow_mask *mask;
>>
>> +                       del = ce;
>>                         mask = rcu_dereference_ovsl(ma->masks[ce->mask_index]);
>> -                       if (mask) {
>> -                               flow = masked_flow_lookup(ti, key, mask,
>> -                                                         n_mask_hit);
>> -                               if (flow)  /* Found */
>> -                                       return flow;
>>
>> +                       if  (!mask) {
> We can mark this case as unlikely.
O.K.
>
>> +                               /* Cache invalid */
>> +                               ce->skb_hash = 0;
>> +                               break;
>>                         }
>> -                       del = ce;
>> +
>> +                       if (ce->mask_index >= ma->count) {
> This case is also unlikely.
> Actually I am not sure if we need to fix this entry. If we skip this
> check then we could end up with wrong entry only if a new mask is
> inserted. But mask delete-insert is rare compared to cache lookups.
I agree that delete-insert is rare compare to cache lookups. On the other hand,
why not increase our cache hit rate if it does not cost much?
>
>> +                               int new_idx;
>> +
>> +                               new_idx = tbl_mask_array_find_idx(ma, mask);
>> +                               if (new_idx >= 0)
>> +                                       ce->mask_index = new_idx;
>> +                               else {
>> +                                       /* Cache invalid */
>> +                                       ce->skb_hash = 0;
>> +                                       break;
>> +                               }
>> +                       }
>> +
>> +                       flow = masked_flow_lookup(ti, key, mask, n_mask_hit);
>> +                       if (flow)
>> +                               /* Cache hit */
>> +                               return flow;
>> +
>> +                       /* Cache miss, do full look up */
>>                         break;
>>                 }
>>
>> @@ -644,18 +711,9 @@ static void flow_mask_remove(struct flow_table *tbl, struct sw_flow_mask *mask)
>>
>>                 if (!mask->ref_count) {
>>                         struct mask_array *ma;
>> -                       int i;
>>
>>                         ma = ovsl_dereference(tbl->mask_array);
>> -                       for (i = 0; i < ma->max; i++) {
>> -                               if (mask == ovsl_dereference(ma->masks[i])) {
>> -                                       RCU_INIT_POINTER(ma->masks[i], NULL);
>> -                                       ma->count--;
>> -                                       goto free;
>> -                               }
>> -                       }
>> -                       BUG();
>> -free:
>> +                       tbl_mask_array_delete_mask(ma, mask);
>>                         call_rcu(&mask->rcu, rcu_free_sw_flow_mask_cb);
>>                 }
>>         }
>> @@ -704,7 +762,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->max; i++) {
>> +       for (i = 0; i < ma->count; i++) {
>>                 struct sw_flow_mask *t;
>>
>>                 t = ovsl_dereference(ma->masks[i]);
>> @@ -724,7 +782,6 @@ 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();
>> @@ -747,16 +804,9 @@ static int flow_mask_insert(struct flow_table *tbl, struct sw_flow *flow,
>>                         }
>>                         ma = ovsl_dereference(tbl->mask_array);
>>                 }
>> -               for (i = 0; i < ma->max; i++) {
>> -                       const struct sw_flow_mask *t;
>>
>> -                       t = ovsl_dereference(ma->masks[i]);
>> -                       if (!t) {
>> -                               rcu_assign_pointer(ma->masks[i], mask);
>> -                               ma->count++;
>> -                               break;
>> -                       }
>> -               }
>> +               rcu_assign_pointer(ma->masks[ma->count], mask);
>> +               ma->count++;
>>         } else {
>>                 BUG_ON(!mask->ref_count);
>>                 mask->ref_count++;
>
> Can you also try to shrink mask array?
Sure.



More information about the dev mailing list