From patchwork Tue Jun 2 07:10:02 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Yanqin Wei X-Patchwork-Id: 1302113 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=openvswitch.org (client-ip=140.211.166.133; helo=hemlock.osuosl.org; envelope-from=ovs-dev-bounces@openvswitch.org; receiver=) Authentication-Results: ozlabs.org; dmarc=none (p=none dis=none) header.from=arm.com Received: from hemlock.osuosl.org (smtp2.osuosl.org [140.211.166.133]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 49bjql3Dg2z9sPF for ; Tue, 2 Jun 2020 17:10:43 +1000 (AEST) Received: from localhost (localhost [127.0.0.1]) by hemlock.osuosl.org (Postfix) with ESMTP id C961C8828D; Tue, 2 Jun 2020 07:10:41 +0000 (UTC) X-Virus-Scanned: amavisd-new at osuosl.org Received: from hemlock.osuosl.org ([127.0.0.1]) by localhost (.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id KDbbLR9OMD6C; Tue, 2 Jun 2020 07:10:40 +0000 (UTC) Received: from lists.linuxfoundation.org (lf-lists.osuosl.org [140.211.9.56]) by hemlock.osuosl.org (Postfix) with ESMTP id DE91488252; Tue, 2 Jun 2020 07:10:40 +0000 (UTC) Received: from lf-lists.osuosl.org (localhost [127.0.0.1]) by lists.linuxfoundation.org (Postfix) with ESMTP id B3913C0893; Tue, 2 Jun 2020 07:10:40 +0000 (UTC) X-Original-To: dev@openvswitch.org Delivered-To: ovs-dev@lists.linuxfoundation.org Received: from silver.osuosl.org (smtp3.osuosl.org [140.211.166.136]) by lists.linuxfoundation.org (Postfix) with ESMTP id E22DCC016E for ; Tue, 2 Jun 2020 07:10:38 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by silver.osuosl.org (Postfix) with ESMTP id CE22D2263C for ; Tue, 2 Jun 2020 07:10:38 +0000 (UTC) X-Virus-Scanned: amavisd-new at osuosl.org Received: from silver.osuosl.org ([127.0.0.1]) by localhost (.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id veTboB-Rs6Mi for ; Tue, 2 Jun 2020 07:10:34 +0000 (UTC) X-Greylist: domain auto-whitelisted by SQLgrey-1.7.6 Received: from foss.arm.com (foss.arm.com [217.140.110.172]) by silver.osuosl.org (Postfix) with ESMTP id 0C88722270 for ; Tue, 2 Jun 2020 07:10:33 +0000 (UTC) Received: from usa-sjc-imap-foss1.foss.arm.com (unknown [10.121.207.14]) by usa-sjc-mx-foss1.foss.arm.com (Postfix) with ESMTP id 3E8B01FB; Tue, 2 Jun 2020 00:10:33 -0700 (PDT) Received: from net-arm-n1sdp.shanghai.arm.com (net-arm-n1sdp.shanghai.arm.com [10.169.40.77]) by usa-sjc-imap-foss1.foss.arm.com (Postfix) with ESMTPA id 636C63F305; Tue, 2 Jun 2020 00:10:30 -0700 (PDT) From: Yanqin Wei To: dev@openvswitch.org Date: Tue, 2 Jun 2020 02:10:02 -0500 Message-Id: <20200602071005.29925-4-Yanqin.Wei@arm.com> X-Mailer: git-send-email 2.17.1 In-Reply-To: <20200602071005.29925-1-Yanqin.Wei@arm.com> References: <20200602071005.29925-1-Yanqin.Wei@arm.com> Cc: Ruifeng.Wang@arm.com, Lijian.Zhang@arm.com, i.maximets@ovn.org, nd@arm.com Subject: [ovs-dev] [PATCH v1 3/6] dpif-netdev: improve emc lookup performance by contiguous storage of hash value. X-BeenThere: ovs-dev@openvswitch.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , MIME-Version: 1.0 Errors-To: ovs-dev-bounces@openvswitch.org Sender: "dev" In the emc lookup function, hash/flow/key are checked for matching entry. Each entry comparison loads several cachelines into CPU. So in the multifow case, processor will wait for the data to be fetched from lower level cacheline or main memory because of cache miss. This patch modifies emc table layout to contiguously store the hash items. It can reduce the number of cache miss for fetching hash value in EMC lookup miss case. And EMC lookup hit case can also benefit because processor can parallelly load and match hash and key in different cacheline. Reviewed-by: Lijian Zhang Reviewed-by: Malvika Gupta Reviewed-by: Ruifeng Wang Signed-off-by: Yanqin Wei --- lib/dpif-netdev.c | 55 +++++++++++++++++++++++++++-------------------- 1 file changed, 32 insertions(+), 23 deletions(-) diff --git a/lib/dpif-netdev.c b/lib/dpif-netdev.c index c94d5e8c7..3994f41e4 100644 --- a/lib/dpif-netdev.c +++ b/lib/dpif-netdev.c @@ -192,13 +192,19 @@ static struct odp_support dp_netdev_support = { #define DEFAULT_EM_FLOW_INSERT_INV_PROB 100 #define DEFAULT_EM_FLOW_INSERT_MIN (UINT32_MAX / \ DEFAULT_EM_FLOW_INSERT_INV_PROB) +struct emc_key { + uint32_t len; /* Length of the following miniflow (incl. map). */ + struct miniflow mf; + uint64_t buf[FLOW_MAX_PACKET_U64S]; +}; struct emc_entry { struct dp_netdev_flow *flow; - struct netdev_flow_key key; /* key.hash used for emc hash value. */ + struct emc_key key; }; struct emc_cache { + uint32_t hash[EM_FLOW_HASH_ENTRIES]; struct emc_entry entries[EM_FLOW_HASH_ENTRIES]; int sweep_idx; /* For emc_cache_slow_sweep(). */ }; @@ -220,9 +226,9 @@ struct dfc_cache { /* Iterate in the exact match cache through every entry that might contain a * miniflow with hash 'HASH'. */ -#define EMC_FOR_EACH_POS_WITH_HASH(EMC, CURRENT_ENTRY, HASH) \ +#define EMC_FOR_EACH_POS_WITH_HASH(ID, HASH) \ for (uint32_t i__ = 0, srch_hash__ = (HASH); \ - (CURRENT_ENTRY) = &(EMC)->entries[srch_hash__ & EM_FLOW_HASH_MASK], \ + (ID) = srch_hash__ & EM_FLOW_HASH_MASK, \ i__ < EM_FLOW_HASH_SEGS; \ i__++, srch_hash__ >>= EM_FLOW_HASH_SHIFT) @@ -877,8 +883,8 @@ emc_cache_init(struct emc_cache *flow_cache) flow_cache->sweep_idx = 0; for (i = 0; i < ARRAY_SIZE(flow_cache->entries); i++) { + flow_cache->hash[i] = 0; flow_cache->entries[i].flow = NULL; - flow_cache->entries[i].key.hash = 0; flow_cache->entries[i].key.len = sizeof(struct miniflow); flowmap_init(&flow_cache->entries[i].key.mf.map); } @@ -2733,12 +2739,12 @@ netdev_flow_key_equal(const struct netdev_flow_key *a, return a->hash == b->hash && !memcmp(&a->mf, &b->mf, a->len); } -/* Used to compare 'netdev_flow_key' in the exact match cache to a miniflow. +/* Used to compare 'emc_key' in the exact match cache to a miniflow. * The maps are compared bitwise, so both 'key->mf' and 'mf' must have been * generated by miniflow_extract. */ static inline bool -netdev_flow_key_equal_mf(const struct netdev_flow_key *key, - const struct miniflow *mf) +emc_key_equal_mf(const struct emc_key *key, + const struct miniflow *mf) { return !memcmp(&key->mf, mf, key->len); } @@ -2840,7 +2846,8 @@ emc_change_entry(struct emc_entry *ce, struct dp_netdev_flow *flow, } } if (key) { - netdev_flow_key_clone(&ce->key, key); + ce->key.len = key->len; + memcpy(&ce->key.mf, &key->mf, key->len); } } @@ -2849,12 +2856,14 @@ emc_insert(struct emc_cache *cache, const struct netdev_flow_key *key, struct dp_netdev_flow *flow) { struct emc_entry *to_be_replaced = NULL; - struct emc_entry *current_entry; + uint32_t *to_be_replaced_hash = NULL; + uint32_t id; - EMC_FOR_EACH_POS_WITH_HASH(cache, current_entry, key->hash) { - if (netdev_flow_key_equal(¤t_entry->key, key)) { + EMC_FOR_EACH_POS_WITH_HASH (id, key->hash) { + if (key->hash == cache->hash[id] + && emc_key_equal_mf(&cache->entries[id].key, &key->mf)) { /* We found the entry with the 'mf' miniflow */ - emc_change_entry(current_entry, flow, NULL); + emc_change_entry(&cache->entries[id], flow, NULL); return; } @@ -2862,14 +2871,15 @@ emc_insert(struct emc_cache *cache, const struct netdev_flow_key *key, * in the first entry where it can be */ if (!to_be_replaced || (emc_entry_alive(to_be_replaced) - && !emc_entry_alive(current_entry)) - || current_entry->key.hash < to_be_replaced->key.hash) { - to_be_replaced = current_entry; + && !emc_entry_alive(&cache->entries[id])) + || cache->hash[id] < *to_be_replaced_hash) { + to_be_replaced = &cache->entries[id]; + to_be_replaced_hash = &cache->hash[id]; } } /* We didn't find the miniflow in the cache. * The 'to_be_replaced' entry is where the new flow will be stored */ - + *to_be_replaced_hash = key->hash; emc_change_entry(to_be_replaced, flow, key); } @@ -2892,15 +2902,14 @@ emc_probabilistic_insert(struct dp_netdev_pmd_thread *pmd, static inline struct dp_netdev_flow * emc_lookup(struct emc_cache *cache, const struct netdev_flow_key *key) { - struct emc_entry *current_entry; - - EMC_FOR_EACH_POS_WITH_HASH(cache, current_entry, key->hash) { - if (current_entry->key.hash == key->hash - && emc_entry_alive(current_entry) - && netdev_flow_key_equal_mf(¤t_entry->key, &key->mf)) { + uint32_t id; + EMC_FOR_EACH_POS_WITH_HASH (id, key->hash) { + if (key->hash == cache->hash[id] + && emc_entry_alive(&cache->entries[id]) + && emc_key_equal_mf(&cache->entries[id].key, &key->mf)) { /* We found the entry with the 'key->mf' miniflow */ - return current_entry->flow; + return cache->entries[id].flow; } }