[ovs-dev] [PATCH v3 1/7] dpif: implement subtable lookup validation

William Tu u9012063 at gmail.com
Tue Jun 16 15:41:43 UTC 2020


Thanks, some minor comments inline.

On Wed, Jun 10, 2020 at 3:47 AM Harry van Haaren
<harry.van.haaren at intel.com> wrote:
>
> This commit refactors the existing dpif subtable function pointer
> infrastructure, and implements an autovalidator component.
>
> The refactoring of the existing dpcls subtable lookup function
> handling, making it more generic, and cleaning up how to enable
> more implementations in future.
>
> In order to ensure all implementations provide identical results,
> the autovalidator is added. The autovalidator itself implements
> the subtable lookup function prototype, but internally iterates
> over all other available implementations. The end result is that
> testing of each implementation becomes automatic, when the auto-
> validator implementation is selected.
>
> Signed-off-by: Harry van Haaren <harry.van.haaren at intel.com>
>
> v3:
> - Fix compile error by adding errno.h include (William Tu)
> - Improve vlog prints by using hex not int for bitmasks
> - Update license years adding 2020
> - Fix 0 used as NULL pointer
> ---
>  lib/automake.mk                        |   3 +
>  lib/dpif-netdev-lookup-autovalidator.c | 106 +++++++++++++++++++++++++
>  lib/dpif-netdev-lookup-generic.c       |   9 ++-
>  lib/dpif-netdev-lookup.c               |  96 ++++++++++++++++++++++
>  lib/dpif-netdev-lookup.h               |  75 +++++++++++++++++
>  lib/dpif-netdev-private.h              |  15 ----
>  lib/dpif-netdev.c                      |  13 ++-
>  7 files changed, 293 insertions(+), 24 deletions(-)
>  create mode 100644 lib/dpif-netdev-lookup-autovalidator.c
>  create mode 100644 lib/dpif-netdev-lookup.c
>  create mode 100644 lib/dpif-netdev-lookup.h
>
> diff --git a/lib/automake.mk b/lib/automake.mk
> index 86940ccd2..9dbc2bbc5 100644
> --- a/lib/automake.mk
> +++ b/lib/automake.mk
> @@ -81,7 +81,10 @@ lib_libopenvswitch_la_SOURCES = \
>         lib/dp-packet.h \
>         lib/dp-packet.c \
>         lib/dpdk.h \
> +       lib/dpif-netdev-lookup.h \
> +       lib/dpif-netdev-lookup.c \
>         lib/dpif-netdev-lookup-generic.c \
> +       lib/dpif-netdev-lookup-autovalidator.c \
ordering: put before the dpif-netdev-lookup-generic.c

>         lib/dpif-netdev.c \
>         lib/dpif-netdev.h \
>         lib/dpif-netdev-private.h \
> diff --git a/lib/dpif-netdev-lookup-autovalidator.c b/lib/dpif-netdev-lookup-autovalidator.c
> new file mode 100644
> index 000000000..0b759a5b9
> --- /dev/null
> +++ b/lib/dpif-netdev-lookup-autovalidator.c
> @@ -0,0 +1,106 @@
> +/*
> + * Copyright (c) 2020 Intel Corporation.
> + *
> + * Licensed under the Apache License, Version 2.0 (the "License");
> + * you may not use this file except in compliance with the License.
> + * You may obtain a copy of the License at:
> + *
> + *     http://www.apache.org/licenses/LICENSE-2.0
> + *
> + * Unless required by applicable law or agreed to in writing, software
> + * distributed under the License is distributed on an "AS IS" BASIS,
> + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
> + * See the License for the specific language governing permissions and
> + * limitations under the License.
> + */
> +
> +#include <config.h>
> +#include "dpif-netdev.h"
> +#include "dpif-netdev-private.h"
> +#include "dpif-netdev-lookup.h"
ordering: put lookup.h before

> +#include "openvswitch/vlog.h"
> +
> +VLOG_DEFINE_THIS_MODULE(dpif_lookup_autovalidator);
> +
> +/* This file implements an automated validator for subtable search
> + * implementations. It compares the results of the generic scalar search result
> + * with ISA optimized implementations.
> + *
> + * Note the goal is *NOT* to test the *specialized* versions of subtables, as
> + * the compiler performs the specialization - and we rely on the correctness of
> + * the compiler to not break those specialized variantes.
> + *
> + * The goal is to ensure identical results of the different implementations,
> + * despite that the implementations may have different methods to get those
> + * results.
> + *
> + * Example: AVX-512 ISA uses different instructions and algorithm to the scalar
> + * implementation, however the results (rules[] output) must be the same.
> + */
> +
> +static uint32_t
> +dpcls_subtable_autovalidator(struct dpcls_subtable *subtable,
> +                             uint32_t keys_map,
> +                             const struct netdev_flow_key *keys[],
> +                             struct dpcls_rule **rules_good)
> +{
> +    const uint32_t u0_bit_count = subtable->mf_bits_set_unit0;
> +    const uint32_t u1_bit_count = subtable->mf_bits_set_unit1;
> +
> +    /* Scalar generic - the "known correct" version */
> +    dpcls_subtable_lookup_func lookup_good;
> +    lookup_good = dpcls_subtable_generic_probe(u0_bit_count, u1_bit_count);
> +
> +    /* Run actual scalar implemenation to get known good results */
s/implemenation/implementation/

> +    uint32_t matches_good = lookup_good(subtable, keys_map, keys, rules_good);
> +
> +    /* Now compare all other implementations against known good results.
> +     * Note we start iterating from array[2], as 0 is autotester, and 1 is
> +     * the known-good scalar implementation.
> +     */
> +    /* TODO: use BUILD_BUG_ON to check for i = 2 being correct? */
> +
> +    struct dpcls_subtable_lookup_info_t *lookup_funcs;
> +    int32_t lookup_func_count = dpcls_subtable_lookup_info_get(&lookup_funcs);
> +    if (lookup_func_count < 0) {
> +        VLOG_ERR("failed to get lookup subtable function implementations\n");
> +        return 0;
> +    }
> +
> +    for (int i = 1; i < lookup_func_count; i++) {
> +        dpcls_subtable_lookup_func lookup_func;
> +        lookup_func = lookup_funcs[i].probe(u0_bit_count,
> +                            u1_bit_count);
> +
> +        /* If its probe returns a function, then test it */
> +        if (lookup_func) {
> +            struct dpcls_rule *rules_test[NETDEV_MAX_BURST];
> +            size_t rules_size = sizeof(struct dpcls_rule *) * NETDEV_MAX_BURST;
> +            memset(rules_test, 0, rules_size);
> +            uint32_t matches_test = lookup_func(subtable, keys_map, keys,
> +                                                rules_test);
> +
> +            /* Ensure same packets matched against subtable */
> +            if (matches_good != matches_test) {
> +                VLOG_ERR("matches_good 0x%x != matches_test 0x%x in func %s\n",
> +                         matches_good, matches_test, lookup_funcs[i].name);
> +            }
> +
> +            /* Ensure rules matched are the same for scalar / others */
> +            int j;
> +            ULLONG_FOR_EACH_1 (j, matches_test) {
> +                ovs_assert(rules_good[j] == rules_test[j]);
> +            }
> +        }
> +    }
> +
> +    return matches_good;
> +}
> +
> +dpcls_subtable_lookup_func
> +dpcls_subtable_autovalidator_probe(uint32_t u0 OVS_UNUSED,
> +                                   uint32_t u1 OVS_UNUSED)
> +{
> +    /* Always return the same validator tester, it works for all subtables */
> +    return dpcls_subtable_autovalidator;
> +}
> diff --git a/lib/dpif-netdev-lookup-generic.c b/lib/dpif-netdev-lookup-generic.c
> index 89c8be0fa..71c876402 100644
> --- a/lib/dpif-netdev-lookup-generic.c
> +++ b/lib/dpif-netdev-lookup-generic.c
> @@ -1,6 +1,6 @@
>  /*
>   * Copyright (c) 2009, 2010, 2011, 2012, 2013, 2014, 2016, 2017 Nicira, Inc.
> - * Copyright (c) 2019 Intel Corporation.
> + * Copyright (c) 2019, 2020 Intel Corporation.
>   *
>   * Licensed under the Apache License, Version 2.0 (the "License");
>   * you may not use this file except in compliance with the License.
> @@ -18,6 +18,7 @@
>  #include <config.h>
>  #include "dpif-netdev.h"
>  #include "dpif-netdev-private.h"
> +#include "dpif-netdev-lookup.h"
>
>  #include "bitmap.h"
>  #include "cmap.h"
> @@ -254,7 +255,7 @@ lookup_generic_impl(struct dpcls_subtable *subtable,
>  }
>
>  /* Generic lookup function that uses runtime provided mf bits for iterating. */
> -uint32_t
> +static uint32_t
>  dpcls_subtable_lookup_generic(struct dpcls_subtable *subtable,
>                                uint32_t keys_map,
>                                const struct netdev_flow_key *keys[],
> @@ -310,6 +311,10 @@ dpcls_subtable_generic_probe(uint32_t u0_bits, uint32_t u1_bits)
>      if (f) {
>          VLOG_DBG("Subtable using Generic Optimized for u0 %d, u1 %d\n",
>                   u0_bits, u1_bits);
> +    } else {
> +        /* Always return the generic function */
> +        f = dpcls_subtable_lookup_generic;
>      }
> +
>      return f;
>  }
> diff --git a/lib/dpif-netdev-lookup.c b/lib/dpif-netdev-lookup.c
> new file mode 100644
> index 000000000..1aa0c3c0c
> --- /dev/null
> +++ b/lib/dpif-netdev-lookup.c
> @@ -0,0 +1,96 @@
> +/*
> + * Copyright (c) 2020 Intel Corporation.
> + *
> + * Licensed under the Apache License, Version 2.0 (the "License");
> + * you may not use this file except in compliance with the License.
> + * You may obtain a copy of the License at:
> + *
> + *     http://www.apache.org/licenses/LICENSE-2.0
> + *
> + * Unless required by applicable law or agreed to in writing, software
> + * distributed under the License is distributed on an "AS IS" BASIS,
> + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
> + * See the License for the specific language governing permissions and
> + * limitations under the License.
> + */
> +
> +#include <config.h>
> +#include <errno.h>
> +#include "dpif-netdev-lookup.h"
> +
> +#include "openvswitch/vlog.h"
> +
> +VLOG_DEFINE_THIS_MODULE(dpif_netdev_lookup);
> +
> +/* Actual list of implementations goes here */
> +static struct dpcls_subtable_lookup_info_t subtable_lookups[] = {
> +    /* Lowest priority - the auto testing implementation will not be used
> +     * by default, it must be enabled by user */
> +    { .prio = 0,
> +      .probe = dpcls_subtable_autovalidator_probe,
> +      .name = "autovalidator", },
> +
> +    /* Second lowest priority - the default scalar implementation */
> +    { .prio = 1,
> +      .probe = dpcls_subtable_generic_probe,
> +      .name = "generic", },
> +};
> +
> +int32_t
> +dpcls_subtable_lookup_info_get(struct dpcls_subtable_lookup_info_t **out_ptr)
> +{
> +    if (out_ptr == NULL) {
> +        return -1;
> +    }
> +
> +    *out_ptr = subtable_lookups;
> +    return ARRAY_SIZE(subtable_lookups);
> +}
> +
> +/* sets the priority of the lookup function with "name" */
> +int32_t
> +dpcls_subtable_set_prio(const char *name, uint8_t priority)
> +{
> +    for (int i = 0; i < ARRAY_SIZE(subtable_lookups); i++) {
> +        if (strcmp(name, subtable_lookups[i].name) == 0) {
> +                subtable_lookups[i].prio = priority;
> +                VLOG_INFO("Subtable function '%s' set priority to %d\n",
> +                         name, priority);
> +                return 0;
> +        }
> +    }
> +    VLOG_WARN("Subtable function '%s' not found, failed to set priority\n",
> +              name);
> +    return -EINVAL;
> +}
> +
> +dpcls_subtable_lookup_func
> +dpcls_subtable_get_best_impl(uint32_t u0_bit_count, uint32_t u1_bit_count)
> +{
> +    /* Iter over each subtable impl, and get highest priority one. */
> +    int32_t prio = -1;
> +    const char *name = NULL;
> +    dpcls_subtable_lookup_func best_func = NULL;
> +
> +    for (int i = 0; i < ARRAY_SIZE(subtable_lookups); i++) {
> +        int32_t probed_prio = subtable_lookups[i].prio;
> +        if (probed_prio > prio) {
> +            dpcls_subtable_lookup_func probed_func;
> +            probed_func = subtable_lookups[i].probe(u0_bit_count,
> +                                    u1_bit_count);
> +            if (probed_func) {
> +                best_func = probed_func;
> +                prio = probed_prio;
> +                name = subtable_lookups[i].name;
> +            }
> +        }
> +    }
> +
> +    VLOG_DBG("Subtable lookup function '%s' with units (%d,%d), priority %d\n",
> +             name, u0_bit_count, u1_bit_count, prio);
> +
> +    /* Programming error - we must always return a valid func ptr */
> +    ovs_assert(best_func != NULL);
> +
> +    return best_func;
> +}
> diff --git a/lib/dpif-netdev-lookup.h b/lib/dpif-netdev-lookup.h
> new file mode 100644
> index 000000000..61f44b9e8
> --- /dev/null
> +++ b/lib/dpif-netdev-lookup.h
> @@ -0,0 +1,75 @@
> +/*
> + * Copyright (c) 2020 Intel Corporation.
> + *
> + * Licensed under the Apache License, Version 2.0 (the "License");
> + * you may not use this file except in compliance with the License.
> + * You may obtain a copy of the License at:
> + *
> + *     http://www.apache.org/licenses/LICENSE-2.0
> + *
> + * Unless required by applicable law or agreed to in writing, software
> + * distributed under the License is distributed on an "AS IS" BASIS,
> + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
> + * See the License for the specific language governing permissions and
> + * limitations under the License.
> + */
> +
> +#ifndef DPIF_NETDEV_LOOKUP_H
> +#define DPIF_NETDEV_LOOKUP_H 1
> +
> +#include <config.h>
> +#include "dpif-netdev.h"
> +#include "dpif-netdev-private.h"
> +
> +/* Function to perform a probe for the subtable bit fingerprint.
> + * Returns NULL if not valid, or a valid function pointer to call for this
> + * subtable on success.
> + */
> +typedef
> +dpcls_subtable_lookup_func (*dpcls_subtable_probe_func)(uint32_t u0_bit_count,
> +                                                        uint32_t u1_bit_count);
> +
> +/* Prototypes for subtable implementations */
> +dpcls_subtable_lookup_func
> +dpcls_subtable_autovalidator_probe(uint32_t u0_bit_count,
> +                                   uint32_t u1_bit_count);
> +
> +/* Probe function to select a specialized version of the generic lookup
> + * implementation. This provides performance benefit due to compile-time
> + * optimizations such as loop-unrolling. These are enabled by the compile-time
> + * constants in the specific function implementations.
> + */
> +dpcls_subtable_lookup_func
> +dpcls_subtable_generic_probe(uint32_t u0_bit_count, uint32_t u1_bit_count);
> +
> +
> +/* Subtable registration and iteration helpers */
> +struct dpcls_subtable_lookup_info_t {
> +    /* higher priority gets used over lower values. This allows deployments
> +     * to select the best implementation for the use-case.
> +     */
> +    uint8_t prio;
> +
> +    /* Probe function: tests if the (u0,u1) combo is supported. If not
> +     * supported, this function returns NULL. If supported, a function pointer
> +     * is returned which when called will perform the lookup on the subtable.
> +     */
> +    dpcls_subtable_probe_func probe;
> +
> +    /* Human readable name, used in setting subtable priority commands */
> +    const char *name;
> +};
> +
> +int32_t dpcls_subtable_set_prio(const char *name, uint8_t priority);
> +
> +dpcls_subtable_lookup_func
> +dpcls_subtable_get_best_impl(uint32_t u0_bit_count, uint32_t u1_bit_count);
> +
> +/* Retrieve the array of lookup implementations for iteration.
> + * On error, returns a negative number.
> + * On success, returns the size of the arrays pointed to by the out parameter.
> + */
> +int32_t
> +dpcls_subtable_lookup_info_get(struct dpcls_subtable_lookup_info_t **out_ptr);
> +
> +#endif /* dpif-netdev-lookup.h */
> diff --git a/lib/dpif-netdev-private.h b/lib/dpif-netdev-private.h
> index 68c33a0f9..bdc150d45 100644
> --- a/lib/dpif-netdev-private.h
> +++ b/lib/dpif-netdev-private.h
> @@ -60,21 +60,6 @@ uint32_t (*dpcls_subtable_lookup_func)(struct dpcls_subtable *subtable,
>                                         const struct netdev_flow_key *keys[],
>                                         struct dpcls_rule **rules);
>
> -/* Prototype for generic lookup func, using generic scalar code path. */
> -uint32_t
> -dpcls_subtable_lookup_generic(struct dpcls_subtable *subtable,
> -                              uint32_t keys_map,
> -                              const struct netdev_flow_key *keys[],
> -                              struct dpcls_rule **rules);
> -
> -/* Probe function to select a specialized version of the generic lookup
> - * implementation. This provides performance benefit due to compile-time
> - * optimizations such as loop-unrolling. These are enabled by the compile-time
> - * constants in the specific function implementations.
> - */
> -dpcls_subtable_lookup_func
> -dpcls_subtable_generic_probe(uint32_t u0_bit_count, uint32_t u1_bit_count);
> -
>  /* A set of rules that all have the same fields wildcarded. */
>  struct dpcls_subtable {
>      /* The fields are only used by writers. */
> diff --git a/lib/dpif-netdev.c b/lib/dpif-netdev.c
> index 51c888501..5e101e054 100644
> --- a/lib/dpif-netdev.c
> +++ b/lib/dpif-netdev.c
> @@ -43,6 +43,7 @@
>  #include "dp-packet.h"
>  #include "dpif.h"
>  #include "dpif-netdev-perf.h"
> +#include "dpif-netdev-lookup.h"
move above.

Thanks

William


More information about the dev mailing list