From patchwork Mon Jul 31 14:41:27 2017 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Ilya Maximets X-Patchwork-Id: 795794 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 3xLhyW3Jl3z9sN7 for ; Tue, 1 Aug 2017 00:43:15 +1000 (AEST) Received: from mail.linux-foundation.org (localhost [127.0.0.1]) by mail.linuxfoundation.org (Postfix) with ESMTP id 8475EB2F; Mon, 31 Jul 2017 14:41:49 +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 A37D7B2A for ; Mon, 31 Jul 2017 14:41:48 +0000 (UTC) X-Greylist: domain auto-whitelisted by SQLgrey-1.7.6 Received: from mailout1.w1.samsung.com (mailout1.w1.samsung.com [210.118.77.11]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 1C67E46E for ; Mon, 31 Jul 2017 14:41:48 +0000 (UTC) Received: from eucas1p1.samsung.com (unknown [182.198.249.206]) by mailout1.w1.samsung.com (Oracle Communications Messaging Server 7.0.5.31.0 64bit (built May 5 2014)) with ESMTP id <0OTY009HZM5LS050@mailout1.w1.samsung.com> for ovs-dev@openvswitch.org; Mon, 31 Jul 2017 15:41:45 +0100 (BST) Received: from eusmges3.samsung.com (unknown [203.254.199.242]) by eucas1p2.samsung.com (KnoxPortal) with ESMTP id 20170731144144eucas1p2916477cd02edce97888a405f8c9af8f2~WcU3TbV6F0160501605eucas1p23; Mon, 31 Jul 2017 14:41:44 +0000 (GMT) Received: from eucas1p1.samsung.com ( [182.198.249.206]) by eusmges3.samsung.com (EUCPMTA) with SMTP id E0.BF.17464.8A14F795; Mon, 31 Jul 2017 15:41:44 +0100 (BST) Received: from eusmgms1.samsung.com (unknown [182.198.249.179]) by eucas1p2.samsung.com (KnoxPortal) with ESMTP id 20170731144143eucas1p253fdbc688bfa96c8750660848474404a~WcU2dEjpF0160501605eucas1p22; Mon, 31 Jul 2017 14:41:43 +0000 (GMT) X-AuditID: cbfec7f2-f797e6d000004438-71-597f41a81b76 Received: from eusync1.samsung.com ( [203.254.199.211]) by eusmgms1.samsung.com (EUCPMTA) with SMTP id 81.BC.17452.7A14F795; Mon, 31 Jul 2017 15:41:43 +0100 (BST) Received: from imaximets.rnd.samsung.ru ([106.109.129.180]) by eusync1.samsung.com (Oracle Communications Messaging Server 7.0.5.31.0 64bit (built May 5 2014)) with ESMTPA id <0OTY003YTM55G610@eusync1.samsung.com>; Mon, 31 Jul 2017 15:41:43 +0100 (BST) From: Ilya Maximets To: ovs-dev@openvswitch.org Date: Mon, 31 Jul 2017 17:41:27 +0300 Message-id: <1501512087-29023-3-git-send-email-i.maximets@samsung.com> X-Mailer: git-send-email 2.7.4 In-reply-to: <1501512087-29023-1-git-send-email-i.maximets@samsung.com> X-Brightmail-Tracker: H4sIAAAAAAAAA+NgFjrFIsWRmVeSWpSXmKPExsWy7djPc7orHOsjDX68U7Jo6Z/JbPH8xUJm i2mfb7NbXGn/yW6x9tAHdou5n54zWpxt+8/qwO6xeM9LJo9nN/8zerzfd5XNo2/LKkaPd/Pf sgWwRnHZpKTmZJalFunbJXBl7Fi4kqlgiXzFpYsbmBsY90h0MXJySAiYSMw/MpcRwhaTuHBv PVsXIxeHkMBSRomuZeeZIJzPjBKPF3aydDFygHW0vUgGaRASWMYo0dkgAFHTzCRx4t87dpAE m4COxKnVR8CmighIS7zufcMKYjMLvGKU+Hk8CsQWFnCQeDd/L1icRUBV4vHTJUwgNq+Am8TR Jy/YIC6Sk7h5rpMZxOYUcJf4vPIcM8gyCYHvbBJ9b45DHSQrsekAM0S9i8SE/3NYIWxhiVfH t7BD2DISnR0HmSB6mxklGlZdYoRwJjBKfGlezgRRZS9x6uZVJohL+SQmbZvODLGAV6KjTQii xEOi/eIeaHA5SrQvfcYO8f0sRonFjUuYJzDKLGBkWMUoklpanJueWmysV5yYW1yal66XnJ+7 iREYw6f/Hf+0g/HrCatDjAIcjEo8vB2m9ZFCrIllxZW5hxglOJiVRHjXGwKFeFMSK6tSi/Lj i0pzUosPMUpzsCiJ83KduhYhJJCeWJKanZpakFoEk2Xi4JRqYJy8O2DfPtOKOazSC0vqor0N Iq66Pl+tqhGeyD41u4j56Pa0+cZmMxsvbuGpcbh+iztX+2cryysTQW+h2d4CtQnrewKDF1k/ vJSWLdCpdCv9sL3u/hMJP53bDy/a90U1qGBhtNnRFvGlsb/vlDzc1++2ke8q9/kuxpmG+36d 2rvZ5abZgbunbyixFGckGmoxFxUnAgApH7Cv3QIAAA== X-Brightmail-Tracker: H4sIAAAAAAAAA+NgFnrFLMWRmVeSWpSXmKPExsVy+t/xy7rLHesjDb7dN7do6Z/JbPH8xUJm i2mfb7NbXGn/yW6x9tAHdou5n54zWpxt+8/qwO6xeM9LJo9nN/8zerzfd5XNo2/LKkaPd/Pf sgWwRrnZZKQmpqQWKaTmJeenZOal2yqFhrjpWigp5CXmptoqRej6hgQpKZQl5pQCeUYGaMDB OcA9WEnfLsEtY8fClUwFS+QrLl3cwNzAuEeii5GDQ0LARKLtRXIXIyeQKSZx4d56ti5GLg4h gSWMEmvmHWaCcFqZJBrnbWADqWIT0JE4tfoII4gtIiAt8br3DStIEbPAC0aJw5s/MYMkhAUc JN7N38sKYrMIqEo8frqECcTmFXCTOPrkBRvEOjmJm+c6weo5BdwlPq88B2YLAdV07l3IOoGR dwEjwypGkdTS4tz03GJDveLE3OLSvHS95PzcTYzAcN527OfmHYyXNgYfYhTgYFTi4e0wrY8U Yk0sK67MPcQowcGsJMK73hAoxJuSWFmVWpQfX1Sak1p8iNEU6KiJzFKiyfnAWMsriTc0MTS3 NDQytrAwNzJSEuct+XAlXEggPbEkNTs1tSC1CKaPiYNTqoGxr7pA82L+F5MMhynck6Zahh4V Y0/jMfuzTnZlTNbqNe6XD6jYP1X931uVzDSxadJup4o7bwyfPpHsu1j22frUxun1vZkv1kXu /hzE2JxyrU/xsFvYhAx2/R1blafdDZ16qy4jyOKqj/DRFL2XJ5VzHt4PEns//aLlEuGkrFMH EuafXlm468htJZbijERDLeai4kQA8CU7VH0CAAA= X-MTR: 20000000000000000@CPGS X-CMS-MailID: 20170731144143eucas1p253fdbc688bfa96c8750660848474404a X-Msg-Generator: CA X-Sender-IP: 182.198.249.179 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: 20170731144143eucas1p253fdbc688bfa96c8750660848474404a X-RootMTR: 20170731144143eucas1p253fdbc688bfa96c8750660848474404a References: <1501512087-29023-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 v2 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 --- 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 123a7c9..a714329 100644 --- a/lib/dpif-netdev.c +++ b/lib/dpif-netdev.c @@ -155,6 +155,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 / \ @@ -2041,7 +2044,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; @@ -2054,12 +2057,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. @@ -2077,11 +2080,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); } }