On Thu, Aug 14, 2014 at 12:06 AM, Andy Zhou <az...@nicira.com> wrote:
> On Wed, Aug 13, 2014 at 10:19 PM, Pravin B Shelar <pshe...@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 <pshe...@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 <az...@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@openvswitch.org
>> http://openvswitch.org/mailman/listinfo/dev
_______________________________________________
dev mailing list
dev@openvswitch.org
http://openvswitch.org/mailman/listinfo/dev
