netdev - Re: [ovs-dev] [PATCH net-next v4 05/10] net: openvswitch: optimize flow-mask looking up

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <CALDO+SaoGxs3ZShuXiT9TaC+e85ArBa85pUxQ6ApmDScrMtx8w@mail.gmail.com>
Date:   Fri, 18 Oct 2019 16:26:29 -0700
From:   William Tu <u9012063@...il.com>
To:     xiangxia.m.yue@...il.com
Cc:     Greg Rose <gvrose8192@...il.com>, pravin shelar <pshelar@....org>,
        "<dev@...nvswitch.org>" <dev@...nvswitch.org>,
        Linux Kernel Network Developers <netdev@...r.kernel.org>
Subject: Re: [ovs-dev] [PATCH net-next v4 05/10] net: openvswitch: optimize
 flow-mask looking up

On Wed, Oct 16, 2019 at 5:54 AM <xiangxia.m.yue@...il.com> wrote:
>
> From: Tonghao Zhang <xiangxia.m.yue@...il.com>
>
> The full looking up on flow table traverses all mask array.
> If mask-array is too large, the number of invalid flow-mask
> increase, performance will be drop.
>
> One bad case, for example: M means flow-mask is valid and NULL
> of flow-mask means deleted.
>
> +-------------------------------------------+
> | M | NULL | ...                  | NULL | M|
> +-------------------------------------------+
>
> In that case, without this patch, openvswitch will traverses all
> mask array, because there will be one flow-mask in the tail. This
> patch changes the way of flow-mask inserting and deleting, and the
> mask array will be keep as below: there is not a NULL hole. In the
> fast path, we can "break" "for" (not "continue") in flow_lookup
> when we get a NULL flow-mask.
>
>          "break"
>             v
> +-------------------------------------------+
> | M | M |  NULL |...           | NULL | NULL|
> +-------------------------------------------+
>
> This patch don't optimize slow or control path, still using ma->max
> to traverse. Slow path:
> * tbl_mask_array_realloc
> * ovs_flow_tbl_lookup_exact
> * flow_mask_find


Hi Tonghao,

Does this improve performance? After all, the original code simply
check whether the mask is NULL, then goto next mask.

However, with your patch,  isn't this invalidated the mask cache entry which
point to the "M" you swap to the front? See my commands inline.

>
> Signed-off-by: Tonghao Zhang <xiangxia.m.yue@...il.com>
> Tested-by: Greg Rose <gvrose8192@...il.com>
> ---
>  net/openvswitch/flow_table.c | 101 ++++++++++++++++++++++---------------------
>  1 file changed, 52 insertions(+), 49 deletions(-)
>
> diff --git a/net/openvswitch/flow_table.c b/net/openvswitch/flow_table.c
> index 8d4f50d..a10d421 100644
> --- a/net/openvswitch/flow_table.c
> +++ b/net/openvswitch/flow_table.c
> @@ -538,7 +538,7 @@ static struct sw_flow *flow_lookup(struct flow_table *tbl,
>
>                 mask = rcu_dereference_ovsl(ma->masks[i]);
>                 if (!mask)
> -                       continue;
> +                       break;
>
>                 flow = masked_flow_lookup(ti, key, mask, n_mask_hit);
>                 if (flow) { /* Found */
> @@ -695,7 +695,7 @@ struct sw_flow *ovs_flow_tbl_lookup_ufid(struct flow_table *tbl,
>  int ovs_flow_tbl_num_masks(const struct flow_table *table)
>  {
>         struct mask_array *ma = rcu_dereference_ovsl(table->mask_array);
> -       return ma->count;
> +       return READ_ONCE(ma->count);
>  }
>
>  static struct table_instance *table_instance_expand(struct table_instance *ti,
> @@ -704,21 +704,33 @@ static struct table_instance *table_instance_expand(struct table_instance *ti,
>         return table_instance_rehash(ti, ti->n_buckets * 2, ufid);
>  }
>
> -static void tbl_mask_array_delete_mask(struct mask_array *ma,
> -                                      struct sw_flow_mask *mask)
> +static void tbl_mask_array_del_mask(struct flow_table *tbl,
> +                                   struct sw_flow_mask *mask)
>  {
> -       int i;
> +       struct mask_array *ma = ovsl_dereference(tbl->mask_array);
> +       int i, ma_count = READ_ONCE(ma->count);
>
>         /* 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--;
> -                       kfree_rcu(mask, rcu);
> -                       return;
> -               }
> +       for (i = 0; i < ma_count; i++) {
> +               if (mask == ovsl_dereference(ma->masks[i]))
> +                       goto found;
>         }
> +
>         BUG();
> +       return;
> +
> +found:
> +       WRITE_ONCE(ma->count, ma_count -1);
> +
> +       rcu_assign_pointer(ma->masks[i], ma->masks[ma_count -1]);
> +       RCU_INIT_POINTER(ma->masks[ma_count -1], NULL);

So when you swap the ma->masks[ma_count -1], the mask cache entry
who's 'mask_index == ma_count' become all invalid?

Regards,
William

<snip>