On Thu, May 15, 2014 at 1:50 PM, Pravin Shelar <pshe...@nicira.com> wrote:
> On Thu, May 8, 2014 at 11:19 PM, Andy Zhou <az...@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 <az...@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.
_______________________________________________
dev mailing list
dev@openvswitch.org
http://openvswitch.org/mailman/listinfo/dev
