[ovs-dev] [PATCH v4 1/7] dpif-netdev: implement subtable lookup validation.

Harry van Haaren harry.van.haaren at intel.com
Thu Jun 18 16:53:48 UTC 2020


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>

---

v4:
- Fix automake .c file order (William Tu)
- Fix include file ordering: netdev-lookup before netdev-perf (William Tu)
- Fix Typos (William Tu)
- Add --enable-autovalidator compile time flag to set the DPCLS Autovalidator
  to the highest priority by default. This is required to run the unit tests
  with all DPCLS implementations without changing every test-case.
  Backwards compatibility is kept with OVS 2.13.
- Add check to ensure autovalidator is 0th item in lookup array
- Improve comments around autovalidator lookup iteration

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
---
 acinclude.m4                           |  16 ++++
 configure.ac                           |   1 +
 lib/automake.mk                        |   3 +
 lib/dpif-netdev-lookup-autovalidator.c | 110 +++++++++++++++++++++++++
 lib/dpif-netdev-lookup-generic.c       |   9 +-
 lib/dpif-netdev-lookup.c               | 104 +++++++++++++++++++++++
 lib/dpif-netdev-lookup.h               |  75 +++++++++++++++++
 lib/dpif-netdev-private.h              |  15 ----
 lib/dpif-netdev.c                      |  13 ++-
 9 files changed, 322 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/acinclude.m4 b/acinclude.m4
index 8847b8145..9b28222f6 100644
--- a/acinclude.m4
+++ b/acinclude.m4
@@ -14,6 +14,22 @@
 # See the License for the specific language governing permissions and
 # limitations under the License.
 
+dnl Set OVS DPCLS Autovalidator as default subtable search at compile time?
+dnl This enables automatically running all unit tests with all DPCLS
+dnl implementations.
+AC_DEFUN([OVS_CHECK_DPCLS_AUTOVALIDATOR], [
+  AC_ARG_ENABLE([autovalidator],
+                [AC_HELP_STRING([--enable-autovalidator], [Enable DPCLS autovalidator as default subtable search implementation.])],
+                [autovalidator=yes],[autovalidator=no])
+  AC_MSG_CHECKING([whether DPCLS Autovalidator is default implementation])
+  if test "$autovalidator" != yes; then
+    AC_MSG_RESULT([no])
+  else
+    OVS_CFLAGS="$OVS_CFLAGS -DDPCLS_AUTOVALIDATOR_DEFAULT"
+    AC_MSG_RESULT([yes])
+  fi
+])
+
 dnl OVS_ENABLE_WERROR
 AC_DEFUN([OVS_ENABLE_WERROR],
   [AC_ARG_ENABLE(
diff --git a/configure.ac b/configure.ac
index 1877aae56..81893e56e 100644
--- a/configure.ac
+++ b/configure.ac
@@ -181,6 +181,7 @@ OVS_CONDITIONAL_CC_OPTION([-Wno-unused-parameter], [HAVE_WNO_UNUSED_PARAMETER])
 OVS_ENABLE_WERROR
 OVS_ENABLE_SPARSE
 OVS_CTAGS_IDENTIFIERS
+OVS_CHECK_DPCLS_AUTOVALIDATOR
 
 AC_ARG_VAR(KARCH, [Kernel Architecture String])
 AC_SUBST(KARCH)
diff --git a/lib/automake.mk b/lib/automake.mk
index 86940ccd2..1fc1a209e 100644
--- a/lib/automake.mk
+++ b/lib/automake.mk
@@ -81,6 +81,9 @@ 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-autovalidator.c \
 	lib/dpif-netdev-lookup-generic.c \
 	lib/dpif-netdev.c \
 	lib/dpif-netdev.h \
diff --git a/lib/dpif-netdev-lookup-autovalidator.c b/lib/dpif-netdev-lookup-autovalidator.c
new file mode 100644
index 000000000..a027321ab
--- /dev/null
+++ b/lib/dpif-netdev-lookup-autovalidator.c
@@ -0,0 +1,110 @@
+/*
+ * 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-lookup.h"
+#include "dpif-netdev-private.h"
+#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.
+ */
+
+dpcls_subtable_lookup_func
+dpcls_subtable_autovalidator_probe(uint32_t u0 OVS_UNUSED,
+                                   uint32_t u1 OVS_UNUSED);
+
+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 implementation to get known good results */
+    uint32_t matches_good = lookup_good(subtable, keys_map, keys, rules_good);
+
+    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;
+    }
+
+    /* Ensure the autovalidator is the 0th item in the lookup_funcs array */
+    ovs_assert(lookup_funcs[0].probe(0, 0) == dpcls_subtable_autovalidator);
+
+    /* Now compare all other implementations against known good results.
+     * Note we start iterating from array[1], as 0 is the autotester itself.
+     */
+    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..dfdbc73a1
--- /dev/null
+++ b/lib/dpif-netdev-lookup.c
@@ -0,0 +1,104 @@
+/*
+ * 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[] = {
+    /* The autovalidator implementation will not be used by default, it must
+     * be enabled at compile time to be the default lookup implementation. The
+     * user may enable it at runtime using the normal "prio-set" command if
+     * desired. The compile time default switch is here to enable all unit
+     * tests to transparently run with the autovalidator.
+     */
+#ifdef DPCLS_AUTOVALIDATOR_DEFAULT
+    { .prio = 255,
+#else
+    { .prio = 0,
+#endif
+      .probe = dpcls_subtable_autovalidator_probe,
+      .name = "autovalidator", },
+
+    /* The default scalar C code 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..d3f80c997 100644
--- a/lib/dpif-netdev.c
+++ b/lib/dpif-netdev.c
@@ -42,6 +42,7 @@
 #include "csum.h"
 #include "dp-packet.h"
 #include "dpif.h"
+#include "dpif-netdev-lookup.h"
 #include "dpif-netdev-perf.h"
 #include "dpif-provider.h"
 #include "dummy.h"
@@ -8058,13 +8059,11 @@ dpcls_create_subtable(struct dpcls *cls, const struct netdev_flow_key *mask)
     subtable->mf_masks = xmalloc(sizeof(uint64_t) * (unit0 + unit1));
     netdev_flow_key_gen_masks(mask, subtable->mf_masks, unit0, unit1);
 
-    /* Probe for a specialized generic lookup function. */
-    subtable->lookup_func = dpcls_subtable_generic_probe(unit0, unit1);
-
-    /* If not set, assign generic lookup. Generic works for any miniflow. */
-    if (!subtable->lookup_func) {
-        subtable->lookup_func = dpcls_subtable_lookup_generic;
-    }
+    /* Get the preferred subtable search function for this (u0,u1) subtable.
+     * The function is guaranteed to always return a valid implementation, and
+     * possibly an ISA optimized, and/or specialized implementation.
+     */
+    subtable->lookup_func = dpcls_subtable_get_best_impl(unit0, unit1);
 
     cmap_insert(&cls->subtables_map, &subtable->cmap_node, mask->hash);
     /* Add the new subtable at the end of the pvector (with no hits yet) */
-- 
2.17.1



More information about the dev mailing list