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

Pravin Shelar pshelar at nicira.com
Thu May 15 20:50:50 UTC 2014


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.

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

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

> +       /* 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?

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

> +                               /* 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.

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



More information about the dev mailing list