From patchwork Mon Jan 21 13:22:38 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: "Van Haaren, Harry" X-Patchwork-Id: 1028674 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: ozlabs.org; spf=pass (mailfrom) smtp.mailfrom=openvswitch.org (client-ip=140.211.169.12; helo=mail.linuxfoundation.org; envelope-from=ovs-dev-bounces@openvswitch.org; receiver=) Authentication-Results: ozlabs.org; dmarc=fail (p=none dis=none) header.from=intel.com Received: from mail.linuxfoundation.org (mail.linuxfoundation.org [140.211.169.12]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 43jsj34z7Nz9sBQ for ; Tue, 22 Jan 2019 00:24:39 +1100 (AEDT) Received: from mail.linux-foundation.org (localhost [127.0.0.1]) by mail.linuxfoundation.org (Postfix) with ESMTP id C496A3B7E; Mon, 21 Jan 2019 13:24:06 +0000 (UTC) X-Original-To: ovs-dev@openvswitch.org Delivered-To: ovs-dev@mail.linuxfoundation.org Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id 188471A0A for ; Mon, 21 Jan 2019 13:22:31 +0000 (UTC) X-Greylist: domain auto-whitelisted by SQLgrey-1.7.6 Received: from mga17.intel.com (mga17.intel.com [192.55.52.151]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 7314F318 for ; Mon, 21 Jan 2019 13:22:30 +0000 (UTC) X-Amp-Result: SKIPPED(no attachment in message) X-Amp-File-Uploaded: False Received: from fmsmga002.fm.intel.com ([10.253.24.26]) by fmsmga107.fm.intel.com with ESMTP/TLS/DHE-RSA-AES256-GCM-SHA384; 21 Jan 2019 05:22:30 -0800 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.56,503,1539673200"; d="scan'208";a="136443202" Received: from silpixa00399779.ir.intel.com (HELO silpixa00399779.ger.corp.intel.com) ([10.237.222.118]) by fmsmga002.fm.intel.com with ESMTP; 21 Jan 2019 05:22:28 -0800 From: Harry van Haaren To: ovs-dev@openvswitch.org Date: Mon, 21 Jan 2019 13:22:38 +0000 Message-Id: <20190121132241.76471-2-harry.van.haaren@intel.com> X-Mailer: git-send-email 2.17.1 In-Reply-To: <20190121132241.76471-1-harry.van.haaren@intel.com> References: <20181121014000.39339-1-harry.van.haaren@intel.com> <20190121132241.76471-1-harry.van.haaren@intel.com> X-Spam-Status: No, score=-4.2 required=5.0 tests=BAYES_00, RCVD_IN_DNSWL_MED autolearn=ham version=3.3.1 X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on smtp1.linux-foundation.org Cc: i.maximets@samsung.com Subject: [ovs-dev] [PATCH v4 1/4] dpif-netdev: implement function pointers/subtable X-BeenThere: ovs-dev@openvswitch.org X-Mailman-Version: 2.1.12 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , MIME-Version: 1.0 Sender: ovs-dev-bounces@openvswitch.org Errors-To: ovs-dev-bounces@openvswitch.org This allows plugging-in of different subtable hash-lookup-verify routines, and allows special casing of those functions based on known context (eg: # of bits set) of the specific subtable. Signed-off-by: Harry van Haaren --- lib/dpif-netdev.c | 127 +++++++++++++++++++++++++++++++--------------- 1 file changed, 87 insertions(+), 40 deletions(-) diff --git a/lib/dpif-netdev.c b/lib/dpif-netdev.c index 0f57e3f8a..3d4e3f737 100644 --- a/lib/dpif-netdev.c +++ b/lib/dpif-netdev.c @@ -7514,6 +7514,27 @@ dpif_dummy_register(enum dummy_level level) /* Datapath Classifier. */ +/* forward declaration for lookup_func typedef */ +struct dpcls_subtable; + +/** Lookup function for a subtable in the dpcls. This function is called + * by each subtable with an array of packets, and a bitmask of packets to + * perform the lookup on. Using a function pointer gives flexibility to + * optimize the lookup function based on subtable properties and the + * CPU instruction set available at runtime. + */ +typedef uint32_t (*dpcls_subtable_lookup_func)(struct dpcls_subtable *subtable, + uint32_t keys_map, const struct netdev_flow_key *keys[], + struct dpcls_rule **rules); + +/** Prototype for generic lookup func, using same code path as before */ +uint32_t +dpcls_subtable_lookup_generic(struct dpcls_subtable *subtable, + uint32_t keys_map, + const struct netdev_flow_key *keys[], + struct dpcls_rule **rules); + + /* A set of rules that all have the same fields wildcarded. */ struct dpcls_subtable { /* The fields are only used by writers. */ @@ -7523,6 +7544,13 @@ struct dpcls_subtable { struct cmap rules; /* Contains "struct dpcls_rule"s. */ uint32_t hit_cnt; /* Number of match hits in subtable in current optimization interval. */ + + /* the lookup function to use for this subtable. If there is a known + * property of the subtable (eg: only 3 bits of miniflow metadata is + * used for the lookup) then this can point at an optimized version of + * the lookup function for this particular subtable. */ + dpcls_subtable_lookup_func lookup_func; + struct netdev_flow_key mask; /* Wildcards for fields (const). */ /* 'mask' must be the last field, additional space is allocated here. */ }; @@ -7576,6 +7604,10 @@ dpcls_create_subtable(struct dpcls *cls, const struct netdev_flow_key *mask) cmap_init(&subtable->rules); subtable->hit_cnt = 0; netdev_flow_key_clone(&subtable->mask, mask); + + /* decide which hash/lookup/verify function to use */ + subtable->lookup_func = dpcls_subtable_lookup_generic; + cmap_insert(&cls->subtables_map, &subtable->cmap_node, mask->hash); /* Add the new subtable at the end of the pvector (with no hits yet) */ pvector_insert(&cls->subtables, subtable, 0); @@ -7736,6 +7768,54 @@ dpcls_rule_matches_key(const struct dpcls_rule *rule, return true; } +uint32_t +dpcls_subtable_lookup_generic(struct dpcls_subtable *subtable, + uint32_t keys_map, + const struct netdev_flow_key *keys[], + struct dpcls_rule **rules) +{ + int i; + /* Compute hashes for the remaining keys. Each search-key is + * masked with the subtable's mask to avoid hashing the wildcarded + * bits. */ + uint32_t hashes[NETDEV_MAX_BURST]; + ULLONG_FOR_EACH_1(i, keys_map) { + hashes[i] = netdev_flow_key_hash_in_mask(keys[i], + &subtable->mask); + } + + /* Lookup. */ + const struct cmap_node *nodes[NETDEV_MAX_BURST]; + uint32_t found_map = + cmap_find_batch(&subtable->rules, keys_map, hashes, nodes); + /* Check results. When the i-th bit of found_map is set, it means + * that a set of nodes with a matching hash value was found for the + * i-th search-key. Due to possible hash collisions we need to check + * which of the found rules, if any, really matches our masked + * search-key. */ + ULLONG_FOR_EACH_1(i, found_map) { + struct dpcls_rule *rule; + + CMAP_NODE_FOR_EACH (rule, cmap_node, nodes[i]) { + if (OVS_LIKELY(dpcls_rule_matches_key(rule, keys[i]))) { + rules[i] = rule; + /* Even at 20 Mpps the 32-bit hit_cnt cannot wrap + * within one second optimization interval. */ + subtable->hit_cnt++; + //lookups_match += subtable_pos; + goto next; + } + } + /* None of the found rules was a match. Reset the i-th bit to + * keep searching this key in the next subtable. */ + ULLONG_SET0(found_map, i); /* Did not match. */ + next: + ; /* Keep Sparse happy. */ + } + + return found_map; +} + /* For each miniflow in 'keys' performs a classifier lookup writing the result * into the corresponding slot in 'rules'. If a particular entry in 'keys' is * NULL it is skipped. @@ -7754,16 +7834,12 @@ dpcls_lookup(struct dpcls *cls, const struct netdev_flow_key *keys[], /* The received 'cnt' miniflows are the search-keys that will be processed * to find a matching entry into the available subtables. * The number of bits in map_type is equal to NETDEV_MAX_BURST. */ - typedef uint32_t map_type; -#define MAP_BITS (sizeof(map_type) * CHAR_BIT) +#define MAP_BITS (sizeof(uint32_t) * CHAR_BIT) BUILD_ASSERT_DECL(MAP_BITS >= NETDEV_MAX_BURST); struct dpcls_subtable *subtable; - map_type keys_map = TYPE_MAXIMUM(map_type); /* Set all bits. */ - map_type found_map; - uint32_t hashes[MAP_BITS]; - const struct cmap_node *nodes[MAP_BITS]; + uint32_t keys_map = TYPE_MAXIMUM(uint32_t); /* Set all bits. */ if (cnt != MAP_BITS) { keys_map >>= MAP_BITS - cnt; /* Clear extra bits. */ @@ -7780,41 +7856,10 @@ dpcls_lookup(struct dpcls *cls, const struct netdev_flow_key *keys[], * search-key, the search for that key can stop because the rules are * non-overlapping. */ PVECTOR_FOR_EACH (subtable, &cls->subtables) { - int i; + /* call the subtable specific lookup function */ + uint32_t found_map = + subtable->lookup_func(subtable, keys_map, keys, rules); - /* Compute hashes for the remaining keys. Each search-key is - * masked with the subtable's mask to avoid hashing the wildcarded - * bits. */ - ULLONG_FOR_EACH_1(i, keys_map) { - hashes[i] = netdev_flow_key_hash_in_mask(keys[i], - &subtable->mask); - } - /* Lookup. */ - found_map = cmap_find_batch(&subtable->rules, keys_map, hashes, nodes); - /* Check results. When the i-th bit of found_map is set, it means - * that a set of nodes with a matching hash value was found for the - * i-th search-key. Due to possible hash collisions we need to check - * which of the found rules, if any, really matches our masked - * search-key. */ - ULLONG_FOR_EACH_1(i, found_map) { - struct dpcls_rule *rule; - - CMAP_NODE_FOR_EACH (rule, cmap_node, nodes[i]) { - if (OVS_LIKELY(dpcls_rule_matches_key(rule, keys[i]))) { - rules[i] = rule; - /* Even at 20 Mpps the 32-bit hit_cnt cannot wrap - * within one second optimization interval. */ - subtable->hit_cnt++; - lookups_match += subtable_pos; - goto next; - } - } - /* None of the found rules was a match. Reset the i-th bit to - * keep searching this key in the next subtable. */ - ULLONG_SET0(found_map, i); /* Did not match. */ - next: - ; /* Keep Sparse happy. */ - } keys_map &= ~found_map; /* Clear the found rules. */ if (!keys_map) { if (num_lookups_p) { @@ -7824,6 +7869,8 @@ dpcls_lookup(struct dpcls *cls, const struct netdev_flow_key *keys[], } subtable_pos++; } + + if (num_lookups_p) { *num_lookups_p = lookups_match; } From patchwork Mon Jan 21 13:22:39 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: "Van Haaren, Harry" X-Patchwork-Id: 1028676 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: ozlabs.org; spf=pass (mailfrom) smtp.mailfrom=openvswitch.org (client-ip=140.211.169.12; helo=mail.linuxfoundation.org; envelope-from=ovs-dev-bounces@openvswitch.org; receiver=) Authentication-Results: ozlabs.org; dmarc=fail (p=none dis=none) header.from=intel.com Received: from mail.linuxfoundation.org (mail.linuxfoundation.org [140.211.169.12]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 43jsjZ346Cz9s7h for ; Tue, 22 Jan 2019 00:25:06 +1100 (AEDT) Received: from mail.linux-foundation.org (localhost [127.0.0.1]) by mail.linuxfoundation.org (Postfix) with ESMTP id 8EB243B84; Mon, 21 Jan 2019 13:24:07 +0000 (UTC) X-Original-To: ovs-dev@openvswitch.org Delivered-To: ovs-dev@mail.linuxfoundation.org Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id 3FB0C3B6E for ; Mon, 21 Jan 2019 13:22:32 +0000 (UTC) X-Greylist: domain auto-whitelisted by SQLgrey-1.7.6 Received: from mga17.intel.com (mga17.intel.com [192.55.52.151]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id B0F0B318 for ; Mon, 21 Jan 2019 13:22:31 +0000 (UTC) X-Amp-Result: SKIPPED(no attachment in message) X-Amp-File-Uploaded: False Received: from fmsmga002.fm.intel.com ([10.253.24.26]) by fmsmga107.fm.intel.com with ESMTP/TLS/DHE-RSA-AES256-GCM-SHA384; 21 Jan 2019 05:22:31 -0800 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.56,503,1539673200"; d="scan'208";a="136443209" Received: from silpixa00399779.ir.intel.com (HELO silpixa00399779.ger.corp.intel.com) ([10.237.222.118]) by fmsmga002.fm.intel.com with ESMTP; 21 Jan 2019 05:22:29 -0800 From: Harry van Haaren To: ovs-dev@openvswitch.org Date: Mon, 21 Jan 2019 13:22:39 +0000 Message-Id: <20190121132241.76471-3-harry.van.haaren@intel.com> X-Mailer: git-send-email 2.17.1 In-Reply-To: <20190121132241.76471-1-harry.van.haaren@intel.com> References: <20181121014000.39339-1-harry.van.haaren@intel.com> <20190121132241.76471-1-harry.van.haaren@intel.com> X-Spam-Status: No, score=-4.2 required=5.0 tests=BAYES_00, RCVD_IN_DNSWL_MED autolearn=ham version=3.3.1 X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on smtp1.linux-foundation.org Cc: i.maximets@samsung.com Subject: [ovs-dev] [PATCH v4 2/4] dpif-netdev: move dpcls lookup structures to .h X-BeenThere: ovs-dev@openvswitch.org X-Mailman-Version: 2.1.12 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , MIME-Version: 1.0 Sender: ovs-dev-bounces@openvswitch.org Errors-To: ovs-dev-bounces@openvswitch.org This commit moves some data-structures to be available in the dpif-netdev.h header. This allows specific implementations of the subtable lookup function to include just that header file, and not require that the code exists in dpif-netdev.c Signed-off-by: Harry van Haaren --- lib/dpif-netdev.c | 50 ----------------------------------------------- lib/dpif-netdev.h | 50 +++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 50 insertions(+), 50 deletions(-) diff --git a/lib/dpif-netdev.c b/lib/dpif-netdev.c index 3d4e3f737..39ea16531 100644 --- a/lib/dpif-netdev.c +++ b/lib/dpif-netdev.c @@ -127,15 +127,6 @@ static struct odp_support dp_netdev_support = { .ct_orig_tuple6 = true, }; -/* Stores a miniflow with inline values */ - -struct netdev_flow_key { - uint32_t hash; /* Hash function differs for different users. */ - uint32_t len; /* Length of the following miniflow (incl. map). */ - struct miniflow mf; - uint64_t buf[FLOW_MAX_PACKET_U64S]; -}; - /* EMC cache and SMC cache compose the datapath flow cache (DFC) * * Exact match cache for frequently used flows @@ -7514,47 +7505,6 @@ dpif_dummy_register(enum dummy_level level) /* Datapath Classifier. */ -/* forward declaration for lookup_func typedef */ -struct dpcls_subtable; - -/** Lookup function for a subtable in the dpcls. This function is called - * by each subtable with an array of packets, and a bitmask of packets to - * perform the lookup on. Using a function pointer gives flexibility to - * optimize the lookup function based on subtable properties and the - * CPU instruction set available at runtime. - */ -typedef uint32_t (*dpcls_subtable_lookup_func)(struct dpcls_subtable *subtable, - uint32_t keys_map, const struct netdev_flow_key *keys[], - struct dpcls_rule **rules); - -/** Prototype for generic lookup func, using same code path as before */ -uint32_t -dpcls_subtable_lookup_generic(struct dpcls_subtable *subtable, - uint32_t keys_map, - const struct netdev_flow_key *keys[], - struct dpcls_rule **rules); - - -/* A set of rules that all have the same fields wildcarded. */ -struct dpcls_subtable { - /* The fields are only used by writers. */ - struct cmap_node cmap_node OVS_GUARDED; /* Within dpcls 'subtables_map'. */ - - /* These fields are accessed by readers. */ - struct cmap rules; /* Contains "struct dpcls_rule"s. */ - uint32_t hit_cnt; /* Number of match hits in subtable in current - optimization interval. */ - - /* the lookup function to use for this subtable. If there is a known - * property of the subtable (eg: only 3 bits of miniflow metadata is - * used for the lookup) then this can point at an optimized version of - * the lookup function for this particular subtable. */ - dpcls_subtable_lookup_func lookup_func; - - struct netdev_flow_key mask; /* Wildcards for fields (const). */ - /* 'mask' must be the last field, additional space is allocated here. */ -}; - /* Initializes 'cls' as a classifier that initially contains no classification * rules. */ static void diff --git a/lib/dpif-netdev.h b/lib/dpif-netdev.h index 6db6ed2e2..720425fb3 100644 --- a/lib/dpif-netdev.h +++ b/lib/dpif-netdev.h @@ -24,6 +24,7 @@ #include "openvswitch/types.h" #include "dp-packet.h" #include "packets.h" +#include "cmap.h" #ifdef __cplusplus extern "C" { @@ -38,6 +39,55 @@ bool dpif_is_netdev(const struct dpif *); #define NR_QUEUE 1 #define NR_PMD_THREADS 1 +/* forward declaration for lookup_func typedef */ +struct dpcls_subtable; +struct dpcls_rule; + +/* must be public as it is intantiated in subtable struct below */ +struct netdev_flow_key { + uint32_t hash; /* Hash function differs for different users. */ + uint32_t len; /* Length of the following miniflow (incl. map). */ + struct miniflow mf; + uint64_t buf[FLOW_MAX_PACKET_U64S]; +}; + +/** Lookup function for a subtable in the dpcls. This function is called + * by each subtable with an array of packets, and a bitmask of packets to + * perform the lookup on. Using a function pointer gives flexibility to + * optimize the lookup function based on subtable properties and the + * CPU instruction set available at runtime. + */ +typedef uint32_t (*dpcls_subtable_lookup_func)(struct dpcls_subtable *subtable, + uint32_t keys_map, const struct netdev_flow_key *keys[], + struct dpcls_rule **rules); + +/** Prototype for generic lookup func, using same code path as before */ +uint32_t +dpcls_subtable_lookup_generic(struct dpcls_subtable *subtable, + uint32_t keys_map, + const struct netdev_flow_key *keys[], + struct dpcls_rule **rules); + +/* A set of rules that all have the same fields wildcarded. */ +struct dpcls_subtable { + /* The fields are only used by writers. */ + struct cmap_node cmap_node OVS_GUARDED; /* Within dpcls 'subtables_map'. */ + + /* These fields are accessed by readers. */ + struct cmap rules; /* Contains "struct dpcls_rule"s. */ + uint32_t hit_cnt; /* Number of match hits in subtable in current + optimization interval. */ + + /* the lookup function to use for this subtable. If there is a known + * property of the subtable (eg: only 3 bits of miniflow metadata is + * used for the lookup) then this can point at an optimized version of + * the lookup function for this particular subtable. */ + dpcls_subtable_lookup_func lookup_func; + + struct netdev_flow_key mask; /* Wildcards for fields (const). */ + /* 'mask' must be the last field, additional space is allocated here. */ +}; + #ifdef __cplusplus } #endif From patchwork Mon Jan 21 13:22:40 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: "Van Haaren, Harry" X-Patchwork-Id: 1028678 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: ozlabs.org; spf=pass (mailfrom) smtp.mailfrom=openvswitch.org (client-ip=140.211.169.12; helo=mail.linuxfoundation.org; envelope-from=ovs-dev-bounces@openvswitch.org; receiver=) Authentication-Results: ozlabs.org; dmarc=fail (p=none dis=none) header.from=intel.com Received: from mail.linuxfoundation.org (mail.linuxfoundation.org [140.211.169.12]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 43jsk70tc8z9s7h for ; Tue, 22 Jan 2019 00:25:35 +1100 (AEDT) Received: from mail.linux-foundation.org (localhost [127.0.0.1]) by mail.linuxfoundation.org (Postfix) with ESMTP id 755B53B89; Mon, 21 Jan 2019 13:24:08 +0000 (UTC) X-Original-To: ovs-dev@openvswitch.org Delivered-To: ovs-dev@mail.linuxfoundation.org Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id BD1A53B6E for ; Mon, 21 Jan 2019 13:22:33 +0000 (UTC) X-Greylist: domain auto-whitelisted by SQLgrey-1.7.6 Received: from mga17.intel.com (mga17.intel.com [192.55.52.151]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id F1AA9815 for ; Mon, 21 Jan 2019 13:22:32 +0000 (UTC) X-Amp-Result: SKIPPED(no attachment in message) X-Amp-File-Uploaded: False Received: from fmsmga002.fm.intel.com ([10.253.24.26]) by fmsmga107.fm.intel.com with ESMTP/TLS/DHE-RSA-AES256-GCM-SHA384; 21 Jan 2019 05:22:32 -0800 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.56,503,1539673200"; d="scan'208";a="136443213" Received: from silpixa00399779.ir.intel.com (HELO silpixa00399779.ger.corp.intel.com) ([10.237.222.118]) by fmsmga002.fm.intel.com with ESMTP; 21 Jan 2019 05:22:30 -0800 From: Harry van Haaren To: ovs-dev@openvswitch.org Date: Mon, 21 Jan 2019 13:22:40 +0000 Message-Id: <20190121132241.76471-4-harry.van.haaren@intel.com> X-Mailer: git-send-email 2.17.1 In-Reply-To: <20190121132241.76471-1-harry.van.haaren@intel.com> References: <20181121014000.39339-1-harry.van.haaren@intel.com> <20190121132241.76471-1-harry.van.haaren@intel.com> X-Spam-Status: No, score=-4.2 required=5.0 tests=BAYES_00, RCVD_IN_DNSWL_MED autolearn=ham version=3.3.1 X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on smtp1.linux-foundation.org Cc: i.maximets@samsung.com Subject: [ovs-dev] [PATCH v4 3/4] dpif-netdev: split out generic lookup function X-BeenThere: ovs-dev@openvswitch.org X-Mailman-Version: 2.1.12 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , MIME-Version: 1.0 Sender: ovs-dev-bounces@openvswitch.org Errors-To: ovs-dev-bounces@openvswitch.org This commit splits the generic hash-lookup-verify function to its own file. In doing so, we must move some MACRO definitions to dpif-netdev.h Signed-off-by: Harry van Haaren --- lib/automake.mk | 1 + lib/dpif-netdev-lookup-generic.c | 95 ++++++++++++++++++++++++++++++++ lib/dpif-netdev.c | 81 +-------------------------- lib/dpif-netdev.h | 16 ++++++ 4 files changed, 113 insertions(+), 80 deletions(-) create mode 100644 lib/dpif-netdev-lookup-generic.c diff --git a/lib/automake.mk b/lib/automake.mk index b1ff495ff..b29128ac4 100644 --- a/lib/automake.mk +++ b/lib/automake.mk @@ -78,6 +78,7 @@ lib_libopenvswitch_la_SOURCES = \ lib/dp-packet.h \ lib/dp-packet.c \ lib/dpdk.h \ + lib/dpif-netdev-lookup-generic.c \ lib/dpif-netdev.c \ lib/dpif-netdev.h \ lib/dpif-netdev-perf.c \ diff --git a/lib/dpif-netdev-lookup-generic.c b/lib/dpif-netdev-lookup-generic.c new file mode 100644 index 000000000..8ae8ff59d --- /dev/null +++ b/lib/dpif-netdev-lookup-generic.c @@ -0,0 +1,95 @@ +/* + * Copyright (c) 2009, 2010, 2011, 2012, 2013, 2014, 2016, 2017 Nicira, Inc. + * + * 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 +#include "dpif-netdev.h" + +#include "bitmap.h" +#include "cmap.h" + +#include "dp-packet.h" +#include "dpif.h" +#include "dpif-netdev-perf.h" +#include "dpif-provider.h" +#include "flow.h" +#include "packets.h" +#include "pvector.h" + +/* Returns a hash value for the bits of 'key' where there are 1-bits in + * 'mask'. */ +static inline uint32_t +netdev_flow_key_hash_in_mask(const struct netdev_flow_key *key, + const struct netdev_flow_key *mask) +{ + const uint64_t *p = miniflow_get_values(&mask->mf); + uint32_t hash = 0; + uint64_t value; + + NETDEV_FLOW_KEY_FOR_EACH_IN_FLOWMAP(value, key, mask->mf.map) { + hash = hash_add64(hash, value & *p); + p++; + } + + return hash_finish(hash, (p - miniflow_get_values(&mask->mf)) * 8); +} + +uint32_t +dpcls_subtable_lookup_generic(struct dpcls_subtable *subtable, + uint32_t keys_map, + const struct netdev_flow_key *keys[], + struct dpcls_rule **rules) +{ + int i; + /* Compute hashes for the remaining keys. Each search-key is + * masked with the subtable's mask to avoid hashing the wildcarded + * bits. */ + uint32_t hashes[NETDEV_MAX_BURST]; + ULLONG_FOR_EACH_1(i, keys_map) { + hashes[i] = netdev_flow_key_hash_in_mask(keys[i], + &subtable->mask); + } + + /* Lookup. */ + const struct cmap_node *nodes[NETDEV_MAX_BURST]; + uint32_t found_map = + cmap_find_batch(&subtable->rules, keys_map, hashes, nodes); + /* Check results. When the i-th bit of found_map is set, it means + * that a set of nodes with a matching hash value was found for the + * i-th search-key. Due to possible hash collisions we need to check + * which of the found rules, if any, really matches our masked + * search-key. */ + ULLONG_FOR_EACH_1(i, found_map) { + struct dpcls_rule *rule; + + CMAP_NODE_FOR_EACH (rule, cmap_node, nodes[i]) { + if (OVS_LIKELY(dpcls_rule_matches_key(rule, keys[i]))) { + rules[i] = rule; + /* Even at 20 Mpps the 32-bit hit_cnt cannot wrap + * within one second optimization interval. */ + subtable->hit_cnt++; + //lookups_match += subtable_pos; + goto next; + } + } + /* None of the found rules was a match. Reset the i-th bit to + * keep searching this key in the next subtable. */ + ULLONG_SET0(found_map, i); /* Did not match. */ + next: + ; /* Keep Sparse happy. */ + } + + return found_map; +} diff --git a/lib/dpif-netdev.c b/lib/dpif-netdev.c index 39ea16531..bcf77db22 100644 --- a/lib/dpif-netdev.c +++ b/lib/dpif-netdev.c @@ -233,14 +233,6 @@ struct dpcls { struct pvector subtables; }; -/* A rule to be inserted to the classifier. */ -struct dpcls_rule { - struct cmap_node cmap_node; /* Within struct dpcls_subtable 'rules'. */ - struct netdev_flow_key *mask; /* Subtable's mask. */ - struct netdev_flow_key flow; /* Matching key. */ - /* 'flow' must be the last field, additional space is allocated here. */ -}; - /* Data structure to keep packet order till fastpath processing. */ struct dp_packet_flow_map { struct dp_packet *packet; @@ -258,8 +250,6 @@ static bool dpcls_lookup(struct dpcls *cls, const struct netdev_flow_key *keys[], struct dpcls_rule **rules, size_t cnt, int *num_lookups_p); -static bool dpcls_rule_matches_key(const struct dpcls_rule *rule, - const struct netdev_flow_key *target); /* Set of supported meter flags */ #define DP_SUPPORTED_METER_FLAGS_MASK \ (OFPMF13_STATS | OFPMF13_PKTPS | OFPMF13_KBPS | OFPMF13_BURST) @@ -2732,27 +2722,6 @@ netdev_flow_key_init_masked(struct netdev_flow_key *dst, (dst_u64 - miniflow_get_values(&dst->mf)) * 8); } -/* Iterate through netdev_flow_key TNL u64 values specified by 'FLOWMAP'. */ -#define NETDEV_FLOW_KEY_FOR_EACH_IN_FLOWMAP(VALUE, KEY, FLOWMAP) \ - MINIFLOW_FOR_EACH_IN_FLOWMAP(VALUE, &(KEY)->mf, FLOWMAP) - -/* Returns a hash value for the bits of 'key' where there are 1-bits in - * 'mask'. */ -static inline uint32_t -netdev_flow_key_hash_in_mask(const struct netdev_flow_key *key, - const struct netdev_flow_key *mask) -{ - const uint64_t *p = miniflow_get_values(&mask->mf); - uint32_t hash = 0; - uint64_t value; - - NETDEV_FLOW_KEY_FOR_EACH_IN_FLOWMAP(value, key, mask->mf.map) { - hash = hash_add64(hash, value & *p++); - } - - return hash_finish(hash, (p - miniflow_get_values(&mask->mf)) * 8); -} - static inline bool emc_entry_alive(struct emc_entry *ce) { @@ -7702,7 +7671,7 @@ dpcls_remove(struct dpcls *cls, struct dpcls_rule *rule) /* Returns true if 'target' satisfies 'key' in 'mask', that is, if each 1-bit * in 'mask' the values in 'key' and 'target' are the same. */ -static bool +bool dpcls_rule_matches_key(const struct dpcls_rule *rule, const struct netdev_flow_key *target) { @@ -7718,54 +7687,6 @@ dpcls_rule_matches_key(const struct dpcls_rule *rule, return true; } -uint32_t -dpcls_subtable_lookup_generic(struct dpcls_subtable *subtable, - uint32_t keys_map, - const struct netdev_flow_key *keys[], - struct dpcls_rule **rules) -{ - int i; - /* Compute hashes for the remaining keys. Each search-key is - * masked with the subtable's mask to avoid hashing the wildcarded - * bits. */ - uint32_t hashes[NETDEV_MAX_BURST]; - ULLONG_FOR_EACH_1(i, keys_map) { - hashes[i] = netdev_flow_key_hash_in_mask(keys[i], - &subtable->mask); - } - - /* Lookup. */ - const struct cmap_node *nodes[NETDEV_MAX_BURST]; - uint32_t found_map = - cmap_find_batch(&subtable->rules, keys_map, hashes, nodes); - /* Check results. When the i-th bit of found_map is set, it means - * that a set of nodes with a matching hash value was found for the - * i-th search-key. Due to possible hash collisions we need to check - * which of the found rules, if any, really matches our masked - * search-key. */ - ULLONG_FOR_EACH_1(i, found_map) { - struct dpcls_rule *rule; - - CMAP_NODE_FOR_EACH (rule, cmap_node, nodes[i]) { - if (OVS_LIKELY(dpcls_rule_matches_key(rule, keys[i]))) { - rules[i] = rule; - /* Even at 20 Mpps the 32-bit hit_cnt cannot wrap - * within one second optimization interval. */ - subtable->hit_cnt++; - //lookups_match += subtable_pos; - goto next; - } - } - /* None of the found rules was a match. Reset the i-th bit to - * keep searching this key in the next subtable. */ - ULLONG_SET0(found_map, i); /* Did not match. */ - next: - ; /* Keep Sparse happy. */ - } - - return found_map; -} - /* For each miniflow in 'keys' performs a classifier lookup writing the result * into the corresponding slot in 'rules'. If a particular entry in 'keys' is * NULL it is skipped. diff --git a/lib/dpif-netdev.h b/lib/dpif-netdev.h index 720425fb3..7195b9791 100644 --- a/lib/dpif-netdev.h +++ b/lib/dpif-netdev.h @@ -51,6 +51,14 @@ struct netdev_flow_key { uint64_t buf[FLOW_MAX_PACKET_U64S]; }; +/* A rule to be inserted to the classifier. */ +struct dpcls_rule { + struct cmap_node cmap_node; /* Within struct dpcls_subtable 'rules'. */ + struct netdev_flow_key *mask; /* Subtable's mask. */ + struct netdev_flow_key flow; /* Matching key. */ + /* 'flow' must be the last field, additional space is allocated here. */ +}; + /** Lookup function for a subtable in the dpcls. This function is called * by each subtable with an array of packets, and a bitmask of packets to * perform the lookup on. Using a function pointer gives flexibility to @@ -88,6 +96,14 @@ struct dpcls_subtable { /* 'mask' must be the last field, additional space is allocated here. */ }; +/* Iterate through netdev_flow_key TNL u64 values specified by 'FLOWMAP'. */ +#define NETDEV_FLOW_KEY_FOR_EACH_IN_FLOWMAP(VALUE, KEY, FLOWMAP) \ + MINIFLOW_FOR_EACH_IN_FLOWMAP(VALUE, &(KEY)->mf, FLOWMAP) + +bool dpcls_rule_matches_key(const struct dpcls_rule *rule, + const struct netdev_flow_key *target); + + #ifdef __cplusplus } #endif From patchwork Mon Jan 21 13:22:41 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: "Van Haaren, Harry" X-Patchwork-Id: 1028679 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: ozlabs.org; spf=pass (mailfrom) smtp.mailfrom=openvswitch.org (client-ip=140.211.169.12; helo=mail.linuxfoundation.org; envelope-from=ovs-dev-bounces@openvswitch.org; receiver=) Authentication-Results: ozlabs.org; dmarc=fail (p=none dis=none) header.from=intel.com Received: from mail.linuxfoundation.org (mail.linuxfoundation.org [140.211.169.12]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 43jskd4hbdz9sBQ for ; Tue, 22 Jan 2019 00:26:01 +1100 (AEDT) Received: from mail.linux-foundation.org (localhost [127.0.0.1]) by mail.linuxfoundation.org (Postfix) with ESMTP id 64C443B8C; Mon, 21 Jan 2019 13:24:09 +0000 (UTC) X-Original-To: ovs-dev@openvswitch.org Delivered-To: ovs-dev@mail.linuxfoundation.org Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id CA2213B6E for ; Mon, 21 Jan 2019 13:22:34 +0000 (UTC) X-Greylist: domain auto-whitelisted by SQLgrey-1.7.6 Received: from mga17.intel.com (mga17.intel.com [192.55.52.151]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 403C0318 for ; Mon, 21 Jan 2019 13:22:34 +0000 (UTC) X-Amp-Result: SKIPPED(no attachment in message) X-Amp-File-Uploaded: False Received: from fmsmga002.fm.intel.com ([10.253.24.26]) by fmsmga107.fm.intel.com with ESMTP/TLS/DHE-RSA-AES256-GCM-SHA384; 21 Jan 2019 05:22:34 -0800 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.56,503,1539673200"; d="scan'208";a="136443217" Received: from silpixa00399779.ir.intel.com (HELO silpixa00399779.ger.corp.intel.com) ([10.237.222.118]) by fmsmga002.fm.intel.com with ESMTP; 21 Jan 2019 05:22:32 -0800 From: Harry van Haaren To: ovs-dev@openvswitch.org Date: Mon, 21 Jan 2019 13:22:41 +0000 Message-Id: <20190121132241.76471-5-harry.van.haaren@intel.com> X-Mailer: git-send-email 2.17.1 In-Reply-To: <20190121132241.76471-1-harry.van.haaren@intel.com> References: <20181121014000.39339-1-harry.van.haaren@intel.com> <20190121132241.76471-1-harry.van.haaren@intel.com> X-Spam-Status: No, score=-4.2 required=5.0 tests=BAYES_00, RCVD_IN_DNSWL_MED autolearn=ham version=3.3.1 X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on smtp1.linux-foundation.org Cc: i.maximets@samsung.com Subject: [ovs-dev] [PATCH v4 4/4] dpif-netdev: optimized dpcls_rule_matches_key() X-BeenThere: ovs-dev@openvswitch.org X-Mailman-Version: 2.1.12 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , MIME-Version: 1.0 Sender: ovs-dev-bounces@openvswitch.org Errors-To: ovs-dev-bounces@openvswitch.org This commit optimizes the dpcls_rule_matches_key() function by refactoring the code to be shorter and less branchy. The main code-change (and optimization) is to use popcount and mask to calculate the packet block index. This code is split out to the header file, which is marked as static inline. The code itself is refactored into two functions, one to iterate the "units" of the miniflow, the other to compare the actual miniflow "blocks" and compare them with the mask/value. The verify_unit() function is called twice, and should/will be inlined by the compiler in optimized builds. As a result the while() loop inside is hence present in two locations in the caller function. This gives each while() loop its own entry in the branch-predictor, helping it to correctly predict each units loop iterations. Finally, we always compute all blocks, and then return match or not-matching in a branch-free manner. This allows the pipeline to execute better, by removing non-predictable branches. Signed-off-by: Harry van Haaren --- This patch optimizes rule_verify() signficantly, please benchmark before and after this patch and see what gains your workload sees. v4: - Fixed bug in popcount offset calculation, thanks Ilya for reporting - Comments cleaned up and reworded for clarity v3: - Fix "last minute variable rename fix" which broke the build :/ --- lib/dpif-netdev.c | 18 ------------- lib/dpif-netdev.h | 68 +++++++++++++++++++++++++++++++++++++++++++++-- 2 files changed, 66 insertions(+), 20 deletions(-) diff --git a/lib/dpif-netdev.c b/lib/dpif-netdev.c index bcf77db22..bee85a8f3 100644 --- a/lib/dpif-netdev.c +++ b/lib/dpif-netdev.c @@ -7669,24 +7669,6 @@ dpcls_remove(struct dpcls *cls, struct dpcls_rule *rule) } } -/* Returns true if 'target' satisfies 'key' in 'mask', that is, if each 1-bit - * in 'mask' the values in 'key' and 'target' are the same. */ -bool -dpcls_rule_matches_key(const struct dpcls_rule *rule, - const struct netdev_flow_key *target) -{ - const uint64_t *keyp = miniflow_get_values(&rule->flow.mf); - const uint64_t *maskp = miniflow_get_values(&rule->mask->mf); - uint64_t value; - - NETDEV_FLOW_KEY_FOR_EACH_IN_FLOWMAP(value, target, rule->flow.mf.map) { - if (OVS_UNLIKELY((value & *maskp++) != *keyp++)) { - return false; - } - } - return true; -} - /* For each miniflow in 'keys' performs a classifier lookup writing the result * into the corresponding slot in 'rules'. If a particular entry in 'keys' is * NULL it is skipped. diff --git a/lib/dpif-netdev.h b/lib/dpif-netdev.h index 7195b9791..13017ce14 100644 --- a/lib/dpif-netdev.h +++ b/lib/dpif-netdev.h @@ -100,9 +100,73 @@ struct dpcls_subtable { #define NETDEV_FLOW_KEY_FOR_EACH_IN_FLOWMAP(VALUE, KEY, FLOWMAP) \ MINIFLOW_FOR_EACH_IN_FLOWMAP(VALUE, &(KEY)->mf, FLOWMAP) -bool dpcls_rule_matches_key(const struct dpcls_rule *rule, - const struct netdev_flow_key *target); +/* Iterate all bits set in the *rle_unit*, lookup the block of metadata based + * on the packet miniflow, and compare it for "matching" the rule, using the + * subtable mask in the process. Note that the pointers passed in to this + * function are already adjusted for the unit offset. */ +static inline int32_t +dpcls_verify_unit(const uint64_t rle_unit, const uint64_t pkt_unit, + const uint64_t *rle, const uint64_t *msk, + const uint64_t *pkt) +{ + int match_fail = 0; + int linear_idx = 0; + + uint64_t iter = rle_unit; + while (iter) { + uint64_t low_bit = iter & (-iter); + iter &= ~(low_bit); + + uint64_t low_mask = low_bit - 1; + uint64_t bits = (low_mask & pkt_unit); + uint64_t blk_idx = __builtin_popcountll(bits); + + /* Take packet, mask bits away, compare against rule. + * Results in 1 for matching, so ! to invert to fail */ + match_fail |= !((pkt[blk_idx] & msk[linear_idx]) == rle[linear_idx]); + linear_idx++; + } + + return match_fail; +} +/* match rule and target (aka packet), to understand if the rule applies to + * this packet. The actual miniflow-unit iteration is performed in + * the *dpcls_verify_unit* function, this just wraps the two unit calls */ +static inline int +dpcls_rule_matches_key(const struct dpcls_rule *rule, + const struct netdev_flow_key *target) +{ + /* retrieve the "block" pointers for the packet, rule and subtable mask */ + const uint64_t *rle_blocks = miniflow_get_values(&rule->flow.mf); + const uint64_t *msk_blocks = miniflow_get_values(&rule->mask->mf); + const uint64_t *pkt_blocks = miniflow_get_values(&target->mf); + + /* fetch the rule bits to iterate */ + const uint64_t rle_u0 = rule->flow.mf.map.bits[0]; + const uint64_t rle_u1 = rule->flow.mf.map.bits[1]; + + /* fetch the packet bits to navigate the packet's miniflow block indexes */ + const uint64_t pkt_u0 = target->mf.map.bits[0]; + const uint64_t pkt_u1 = target->mf.map.bits[1]; + + /* calculate where u1 starts by finding total size of u0 */ + int rle_u0_pop = __builtin_popcountll(rle_u0); + int pkt_u0_pop = __builtin_popcountll(pkt_u0); + + int fail = 0; + /* call verify_unit for both units. This has multiple advantages: + * 1) Each while() loop gets its own branch predictor entry - improves hits + * 2) Compiler can re-shuffle instructions as it likes, also between iters + * 3) Simpler popcount() approach means less branches in general + */ + fail |= dpcls_verify_unit(rle_u0, pkt_u0, &rle_blocks[0], &msk_blocks[0], &pkt_blocks[0]); + fail |= dpcls_verify_unit(rle_u1, pkt_u1, &rle_blocks[rle_u0_pop], &msk_blocks[rle_u0_pop], + &pkt_blocks[pkt_u0_pop]); + + /* return 1 if matches, 0 on fail */ + return fail == 0; +} #ifdef __cplusplus }