[ovs-dev] [PATCH 4/4] datapath: Compact mask list array.

[Andy Zhou]

I have a high level question:
Since mask can be moved around in the array without causing problem,
when deleting a mask, why not simply move the highest
element over?

On Mon, Apr 7, 2014 at 3:00 PM, Pravin <pshelar at nicira.com> wrote:
> From: Pravin Shelar <pshelar at nicira.com>
>
> Along with flow-table rehashing OVS can compact masks array.  This
> allows us to calculate highest index for mask array.
>
> Signed-off-by: Pravin B Shelar <pshelar at nicira.com>
> ---
>  datapath/flow_table.c |   24 ++++++++++++++++++++----
>  datapath/flow_table.h |    2 +-
>  2 files changed, 21 insertions(+), 5 deletions(-)
>
> diff --git a/datapath/flow_table.c b/datapath/flow_table.c
> index 5665cfc..b2c0497 100644
> --- a/datapath/flow_table.c
> +++ b/datapath/flow_table.c
> @@ -230,6 +230,7 @@ static struct mask_array *tbl_mask_array_alloc(int size)
>
>         new->count = 0;
>         new->max = size;
> +       new->hi_index = 0;
>
>         return new;
>  }
> @@ -252,6 +253,8 @@ static int tbl_mask_array_realloc(struct flow_table *tbl, int size)
>                                 new->masks[new->count++] = old->masks[i];
>                 }
>         }
> +
> +       new->hi_index = new->count;
>         rcu_assign_pointer(tbl->mask_array, new);
>
>         if (old)
> @@ -260,6 +263,17 @@ static int tbl_mask_array_realloc(struct flow_table *tbl, int size)
>         return 0;
>  }
>
> +static void tbl_mask_array_compact(struct flow_table *tbl)
> +{
> +       struct mask_array *ma;
> +       int size;
> +
> +       ma = ovsl_dereference(tbl->mask_array);
> +
> +       size = roundup(ma->count, MASK_ARRAY_SIZE_MIN);
> +       tbl_mask_array_realloc(tbl, size);
> +}
> +
>  int ovs_flow_tbl_init(struct flow_table *table)
>  {
>         struct table_instance *ti;
> @@ -521,7 +535,7 @@ static struct sw_flow *flow_lookup(struct flow_table *tbl,
>         int i, c;
>
>         c = 0;
> -       for (i = 0; i < ma->max; i++) {
> +       for (i = 0; i < ma->hi_index; i++) {
>                 struct sw_flow_mask *mask;
>
>                 mask = rcu_dereference_ovsl(ma->masks[i]);
> @@ -631,7 +645,7 @@ static void flow_mask_remove(struct flow_table *tbl, struct sw_flow_mask *mask)
>                         int i;
>
>                         ma = ovsl_dereference(tbl->mask_array);
> -                       for (i = 0; i < ma->max; i++) {
> +                       for (i = 0; i < ma->hi_index; i++) {
>                                 if (mask == ovsl_dereference(ma->masks[i])) {
>                                         RCU_INIT_POINTER(ma->masks[i], NULL);
>                                         ma->count--;
> @@ -688,7 +702,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->hi_index; i++) {
>                 struct sw_flow_mask *t;
>
>                 t = ovsl_dereference(ma->masks[i]);
> @@ -736,8 +750,9 @@ static int flow_mask_insert(struct flow_table *tbl, struct sw_flow *flow,
>
>                         t = ovsl_dereference(ma->masks[i]);
>                         if (!t) {
> -                               rcu_assign_pointer(ma->masks[i], mask);
>                                 ma->count++;
> +                               ma->hi_index = i + 1;
> +                               rcu_assign_pointer(ma->masks[i], mask);
>                                 break;
>                         }
>                 }
> @@ -777,6 +792,7 @@ int ovs_flow_tbl_insert(struct flow_table *table, struct sw_flow *flow,
>         if (new_ti) {
>                 rcu_assign_pointer(table->ti, new_ti);
>                 table_instance_destroy(ti, true);
> +               tbl_mask_array_compact(table);
>                 table->last_rehash = jiffies;
>         }
>         return 0;
> diff --git a/datapath/flow_table.h b/datapath/flow_table.h
> index ee86953..cf898ba 100644
> --- a/datapath/flow_table.h
> +++ b/datapath/flow_table.h
> @@ -43,7 +43,7 @@ struct mask_cache_entry {
>
>  struct mask_array {
>         struct rcu_head rcu;
> -       int count, max;
> +       int count, max, hi_index;
>         struct sw_flow_mask __rcu *masks[];
>  };
>
> --
> 1.7.9.5
>
> _______________________________________________
> dev mailing list
> dev at openvswitch.org
> http://openvswitch.org/mailman/listinfo/dev