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.
> 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.
> + 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?
_______________________________________________
dev mailing list
dev@openvswitch.org
http://openvswitch.org/mailman/listinfo/dev
