Move operation needs to do RCU transaction on mask array. That could
make mask delete expensive.
On Wed, May 7, 2014 at 10:29 PM, Andy Zhou <az...@nicira.com> wrote:
> 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 <pshe...@nicira.com> wrote:
>> From: Pravin Shelar <pshe...@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 <pshe...@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@openvswitch.org
>> http://openvswitch.org/mailman/listinfo/dev
_______________________________________________
dev mailing list
dev@openvswitch.org
http://openvswitch.org/mailman/listinfo/dev
