From patchwork Fri Aug 4 14:17:28 2017 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Ilya Maximets X-Patchwork-Id: 797827 X-Patchwork-Delegate: ian.stokes@intel.com 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=) 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 3xP8Dt2Pg9z9sR8 for ; Sat, 5 Aug 2017 00:19:10 +1000 (AEST) Received: from mail.linux-foundation.org (localhost [127.0.0.1]) by mail.linuxfoundation.org (Postfix) with ESMTP id D48A1B09; Fri, 4 Aug 2017 14:18:32 +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 14FF3A92 for ; Fri, 4 Aug 2017 14:18:31 +0000 (UTC) X-Greylist: domain auto-whitelisted by SQLgrey-1.7.6 Received: from mailout3.w1.samsung.com (mailout3.w1.samsung.com [210.118.77.13]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 6BCDC177 for ; Fri, 4 Aug 2017 14:18:07 +0000 (UTC) Received: from eucas1p2.samsung.com (unknown [182.198.249.207]) by mailout3.w1.samsung.com (Oracle Communications Messaging Server 7.0.5.31.0 64bit (built May 5 2014)) with ESMTP id <0OU500BN8ZPQTA40@mailout3.w1.samsung.com> for ovs-dev@openvswitch.org; Fri, 04 Aug 2017 15:17:51 +0100 (BST) Received: from eusmges1.samsung.com (unknown [203.254.199.239]) by eucas1p2.samsung.com (KnoxPortal) with ESMTP id 20170804141750eucas1p274624929caa914e18c67f7ec95b4ae8a~XqlIllKU51165811658eucas1p2y; Fri, 4 Aug 2017 14:17:50 +0000 (GMT) Received: from eucas1p1.samsung.com ( [182.198.249.206]) by eusmges1.samsung.com (EUCPMTA) with SMTP id 9A.EC.14140.01284895; Fri, 4 Aug 2017 15:17:52 +0100 (BST) Received: from eusmgms2.samsung.com (unknown [182.198.249.180]) by eucas1p1.samsung.com (KnoxPortal) with ESMTP id 20170804141749eucas1p1d639f52626944e7aad9afae22a330410~XqlH6tqWG0202802028eucas1p1P; Fri, 4 Aug 2017 14:17:49 +0000 (GMT) X-AuditID: cbfec7ef-f796a6d00000373c-cd-598482101d94 Received: from eusync3.samsung.com ( [203.254.199.213]) by eusmgms2.samsung.com (EUCPMTA) with SMTP id 58.4C.20206.D0284895; Fri, 4 Aug 2017 15:17:49 +0100 (BST) Received: from imaximets.rnd.samsung.ru ([106.109.129.180]) by eusync3.samsung.com (Oracle Communications Messaging Server 7.0.5.31.0 64bit (built May 5 2014)) with ESMTPA id <0OU500LW7ZPCPO90@eusync3.samsung.com>; Fri, 04 Aug 2017 15:17:49 +0100 (BST) From: Ilya Maximets To: ovs-dev@openvswitch.org Date: Fri, 04 Aug 2017 17:17:28 +0300 Message-id: <1501856248-28555-3-git-send-email-i.maximets@samsung.com> X-Mailer: git-send-email 2.7.4 In-reply-to: <1501856248-28555-1-git-send-email-i.maximets@samsung.com> X-Brightmail-Tracker: H4sIAAAAAAAAA+NgFjrHIsWRmVeSWpSXmKPExsWy7djPc7oCTS2RBn0T1SxW/+K0aOmfyWzx /MVCZotpn2+zW1xp/8lusfbQB3aLuZ+eM1qcbfvP6sDhsXjPSyaPZzf/M3q833eVzaNvyypG j3fz37IFsEZx2aSk5mSWpRbp2yVwZZybHlSwQKHi+sndbA2MqyS7GDk5JARMJDZ2HmKDsMUk LtxbD2RzcQgJLGOUWNXVyQThfGaUOPnyFhNMx8Ut/WA2WNWT06wQRc1MEqe2/2EESbAJ6Eic Wn0EzBYRkJZ43fsGrIhZYDaTxJT7M8H2CQs4SEx/vZIZxGYRUJX4vWUbK4jNK+AmMXfDOXaI bXISN891gtVwCrhLvOhZxQ4ySELgO5vE000rgTZwADmyEpsOMEPUu0gcPN0FZQtLvDq+BWqO jMTlyd0sEL3NjBINqy4xQjgTGCW+NC+H+s1e4tTNq2A2swCfxKRt05khFvBKdLQJQZR4SHRN 2csOEXaUeDYDGl6zGCUaJ15lmsAos4CRYRWjSGppcW56arGhXnFibnFpXrpecn7uJkZgLJ/+ d/z9DsanzSGHGAU4GJV4eA1mNEcKsSaWFVfmHmKU4GBWEuFtLmuJFOJNSaysSi3Kjy8qzUkt PsQozcGiJM7Le+pahJBAemJJanZqakFqEUyWiYNTqoFxXl3X66V6XZIb/64q/PK9i0P7ZI77 0uMHfLzOnow9ahlgzxE0X5jzYfNWo8e7YhcLxWXmWS1n+sht2Pi47bX6qgyO6oQ4FlaJgDWG tfq3raM6Ht64FFp4bct6nswPKitn8Gxk5BHbeGXZnE3Sj6bkbZvKV3jz3a+caxcP8nyISZ3n dV/IZbemEktxRqKhFnNRcSIABuqgB+ECAAA= X-Brightmail-Tracker: H4sIAAAAAAAAA+NgFnrHLMWRmVeSWpSXmKPExsVy+t/xq7q8TS2RBtvuKVms/sVp0dI/k9ni +YuFzBbTPt9mt7jS/pPdYu2hD+wWcz89Z7Q42/af1YHDY/Gel0wez27+Z/R4v+8qm0ffllWM Hu/mv2ULYI1ys8lITUxJLVJIzUvOT8nMS7dVCg1x07VQUshLzE21VYrQ9Q0JUlIoS8wpBfKM DNCAg3OAe7CSvl2CW8a56UEFCxQqrp/czdbAuEqyi5GTQ0LAROLiln4mCFtM4sK99WxdjFwc QgJLGCVmzfzADuG0MknMvXeaDaSKTUBH4tTqI4wgtoiAtMTr3jesIEXMAnOZJA6dOQ82SljA QWL665XMIDaLgKrE7y3bWEFsXgE3ibkbzrFDrJOTuHmuE6yGU8Bd4kXPKrC4EFDN7H172CYw 8i5gZFjFKJJaWpybnltspFecmFtcmpeul5yfu4kRGNbbjv3csoOx613wIUYBDkYlHl6DGc2R QqyJZcWVuYcYJTiYlUR4m8taIoV4UxIrq1KL8uOLSnNSiw8xmgIdNZFZSjQ5HxhzeSXxhiaG 5paGRsYWFuZGRkrivOqXmyKFBNITS1KzU1MLUotg+pg4OKUaGA1LlUTre2UcdkR26rlMazTR vM02Q8LvTnTDBrUvtS/uGXDIuvt+s7rccYb/Y35Y1JMfac+y95TxPTJpE7ftP8JVLXBK6KIx z42JszlDlm1dq3/xbNOi9JOPsn5P583vfSvpd1rh2oe7bLNY436EKPBuMjmqZJZ4ptBS2SpT 9r3/Nb3XTrlRSizFGYmGWsxFxYkASb3WD4ECAAA= X-MTR: 20000000000000000@CPGS X-CMS-MailID: 20170804141749eucas1p1d639f52626944e7aad9afae22a330410 X-Msg-Generator: CA X-Sender-IP: 182.198.249.180 X-Local-Sender: =?UTF-8?B?SWx5YSBNYXhpbWV0cxtTUlItVmlydHVhbGl6YXRpb24gTGFi?= =?UTF-8?B?G+yCvOyEseyghOyekBtMZWFkaW5nIEVuZ2luZWVy?= X-Global-Sender: =?UTF-8?B?SWx5YSBNYXhpbWV0cxtTUlItVmlydHVhbGl6YXRpb24gTGFi?= =?UTF-8?B?G1NhbXN1bmcgRWxlY3Ryb25pY3MbTGVhZGluZyBFbmdpbmVlcg==?= X-Sender-Code: =?UTF-8?B?QzEwG0NJU0hRG0MxMEdEMDFHRDAxMDE1NA==?= CMS-TYPE: 201P X-HopCount: 7 X-CMS-RootMailID: 20170804141749eucas1p1d639f52626944e7aad9afae22a330410 X-RootMTR: 20170804141749eucas1p1d639f52626944e7aad9afae22a330410 References: <1501856248-28555-1-git-send-email-i.maximets@samsung.com> X-Spam-Status: No, score=-6.9 required=5.0 tests=BAYES_00, RCVD_IN_DNSWL_HI, RP_MATCHES_RCVD autolearn=ham version=3.3.1 X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on smtp1.linux-foundation.org Cc: Heetae Ahn , Ilya Maximets Subject: [ovs-dev] [PATCH v3 2/2] dpif-netdev: Fix emc replacement policy. 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 Current EMC replacement policy allows to replace active EMC entry even if there are dead (empty) entries available. This leads to EMC trashing even on few hundreds of flows. In some cases PMD threads starts to execute classifier lookups even in tests with 50 - 100 active flows. Looks like the hash comparison rule was introduced to randomly choose one of alive entries to replace. But it doesn't work as needed and also hashes has nothing common with randomness. Lets fix the replacement policy by removing hash checking and using the random value passed from 'emc_probabilistic_insert()' only while considering replace of the alive entry. This should give us nearly fair way to choose the entry to replace. We are avoiding calculation of the new random value by reusing bits of already generated random for probabilistic EMC insertion. Bits higher than 'EM_FLOW_INSERT_INV_PROB_SHIFT' are used because lower bits are less than 'min' and not fully random. Not replacing of alive entries while dead ones exists allows to significantly decrease EMC trashing. Testing shows stable work of exact match cache without misses with up to 3072 - 6144 active flows (depends on traffic pattern). Signed-off-by: Ilya Maximets Acked-by: Antonio Fischetti --- Some test results from Antonio Fischetti here: https://mail.openvswitch.org/pipermail/ovs-dev/2017-August/336707.html lib/dpif-netdev.c | 23 ++++++++++++++++------- 1 file changed, 16 insertions(+), 7 deletions(-) diff --git a/lib/dpif-netdev.c b/lib/dpif-netdev.c index e23c674..c36fd32 100644 --- a/lib/dpif-netdev.c +++ b/lib/dpif-netdev.c @@ -158,6 +158,9 @@ struct netdev_flow_key { #define EM_FLOW_INSERT_INV_PROB_SHIFT 20 #define EM_FLOW_INSERT_INV_PROB_MAX (1 << EM_FLOW_INSERT_INV_PROB_SHIFT) #define EM_FLOW_INSERT_INV_PROB_MASK (EM_FLOW_INSERT_INV_PROB_MAX - 1) +/* We will use bits higher than EM_FLOW_INSERT_INV_PROB_SHIFT of the random + * value for EMC replacement policy. */ +BUILD_ASSERT_DECL(32 - EM_FLOW_INSERT_INV_PROB_SHIFT >= EM_FLOW_HASH_SEGS); /* Default EMC insert probability is 1 / DEFAULT_EM_FLOW_INSERT_INV_PROB */ #define DEFAULT_EM_FLOW_INSERT_INV_PROB 100 #define DEFAULT_EM_FLOW_INSERT_MIN (EM_FLOW_INSERT_INV_PROB_MAX / \ @@ -2058,7 +2061,7 @@ emc_change_entry(struct emc_entry *ce, struct dp_netdev_flow *flow, static inline void emc_insert(struct emc_cache *cache, const struct netdev_flow_key *key, - struct dp_netdev_flow *flow) + struct dp_netdev_flow *flow, uint32_t random_value) { struct emc_entry *to_be_replaced = NULL; struct emc_entry *current_entry; @@ -2071,12 +2074,12 @@ emc_insert(struct emc_cache *cache, const struct netdev_flow_key *key, } /* Replacement policy: put the flow in an empty (not alive) entry, or - * in the first entry where it can be */ + * in the random 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) { + && (!emc_entry_alive(current_entry) || random_value & 1))) { to_be_replaced = current_entry; + random_value >>= 1; } } /* We didn't find the miniflow in the cache. @@ -2094,11 +2097,17 @@ emc_probabilistic_insert(struct dp_netdev_pmd_thread *pmd, * default the value is UINT32_MAX / 100 which yields an insertion * probability of 1/100 ie. 1% */ - uint32_t min; + uint32_t min, random_value; atomic_read_relaxed(&pmd->dp->emc_insert_min, &min); - if (min && (random_uint32() & EM_FLOW_INSERT_INV_PROB_MASK) < min) { - emc_insert(&pmd->flow_cache, key, flow); + if (!min) { + return; + } + + random_value = random_uint32(); + if ((random_value & EM_FLOW_INSERT_INV_PROB_MASK) < min) { + emc_insert(&pmd->flow_cache, key, flow, + random_value >> EM_FLOW_INSERT_INV_PROB_SHIFT); } }