From patchwork Thu May 24 15:28:00 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jan Scheurich X-Patchwork-Id: 919947 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=ericsson.com Authentication-Results: ozlabs.org; dkim=fail reason="signature verification failed" (1024-bit key; unprotected) header.d=ericsson.com header.i=@ericsson.com header.b="TP+FO5Wd"; dkim=fail reason="signature verification failed" (1024-bit key; unprotected) header.d=ericsson.com header.i=@ericsson.com header.b="JELW+dKD"; dkim-atps=neutral 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 40sCxp11nQz9ry1 for ; Fri, 25 May 2018 01:30:22 +1000 (AEST) Received: from mail.linux-foundation.org (localhost [127.0.0.1]) by mail.linuxfoundation.org (Postfix) with ESMTP id 7154FBD7; Thu, 24 May 2018 15:28:33 +0000 (UTC) X-Original-To: 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 AE6E3BD8 for ; Thu, 24 May 2018 15:28:30 +0000 (UTC) X-Greylist: domain auto-whitelisted by SQLgrey-1.7.6 Received: from sesbmg22.ericsson.net (sesbmg22.ericsson.net [193.180.251.48]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id CB165710 for ; Thu, 24 May 2018 15:28:28 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; d=ericsson.com; s=mailgw201801; c=relaxed/simple; q=dns/txt; i=@ericsson.com; t=1527175707; h=From:Sender:Reply-To:Subject:Date:Message-ID:To:CC:MIME-Version:Content-Type: Content-Transfer-Encoding:Content-ID:Content-Description:Resent-Date:Resent-From: Resent-Sender:Resent-To:Resent-Cc:Resent-Message-ID:In-Reply-To:References:List-Id: List-Help:List-Unsubscribe:List-Subscribe:List-Post:List-Owner:List-Archive; bh=A1zUYpB+yLow+4tr+bTUHusspM3hpShLLU9CUtNDt8Y=; b=TP+FO5WddI7ehAPa++xNPTVH3K5G/SPKpv4NaskGbjz2nGnz2cDLcVIcbpBAhTgI OK1IaHjji5U13ER8rZiaiLI5urSUVETzNAjaUJ4EI3aGGgSkJYiGl4q158FVhCoQ /lfI1yq5RUKQ5gcCNbIntbwaNkafqiWfmQCuR6ZETPg=; X-AuditID: c1b4fb30-932519c0000065fb-a8-5b06da1a5ba2 Received: from ESESSHC010.ericsson.se (Unknown_Domain [153.88.183.48]) by sesbmg22.ericsson.net (Symantec Mail Security) with SMTP id 54.5E.26107.A1AD60B5; Thu, 24 May 2018 17:28:27 +0200 (CEST) Received: from ESESSMB501.ericsson.se (153.88.183.162) by ESESSHC010.ericsson.se (153.88.183.48) with Microsoft SMTP Server (TLS) id 14.3.382.0; Thu, 24 May 2018 17:28:21 +0200 Received: from ESESSMB503.ericsson.se (153.88.183.164) by ESESSMB501.ericsson.se (153.88.183.162) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_128_CBC_SHA256_P256) id 15.1.1466.3; Thu, 24 May 2018 17:28:20 +0200 Received: from EUR01-HE1-obe.outbound.protection.outlook.com (153.88.183.157) by ESESSMB503.ericsson.se (153.88.183.164) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_128_CBC_SHA256_P256) id 15.1.1466.3 via Frontend Transport; Thu, 24 May 2018 17:28:21 +0200 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ericsson.com; s=selector1; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=4CGzo2zEO+EjD7skHzkY1yayQq6rmKctnSHjDEOkfks=; b=JELW+dKDAx62EhOTpKnKDM10g9x8/Eev2apfVubh/65eYXLAetRrwm0NO4qD1WabkRrksJdTWaaWSB7bDgJGQ4mLoXvAeuqUSsDtF/xT/LS75UZQf/EFegmYOhrxC0mxCx78uosGjVnlnsuWbCiQhYA9rrz/1De643G8EdIhfOQ= Received: from ubuntu.eed.ericsson.se (129.192.10.2) by AM5PR0701MB1780.eurprd07.prod.outlook.com (2603:10a6:203:1c::23) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.797.5; Thu, 24 May 2018 15:28:19 +0000 From: Jan Scheurich To: Date: Thu, 24 May 2018 17:28:00 +0200 Message-ID: <1527175681-14674-3-git-send-email-jan.scheurich@ericsson.com> X-Mailer: git-send-email 1.9.1 In-Reply-To: <1527175681-14674-1-git-send-email-jan.scheurich@ericsson.com> References: <1527175681-14674-1-git-send-email-jan.scheurich@ericsson.com> MIME-Version: 1.0 X-Originating-IP: [129.192.10.2] X-ClientProxiedBy: AM5PR0502CA0020.eurprd05.prod.outlook.com (2603:10a6:203:91::30) To AM5PR0701MB1780.eurprd07.prod.outlook.com (2603:10a6:203:1c::23) X-MS-PublicTrafficType: Email X-Microsoft-Antispam: UriScan:; BCL:0; PCL:0; RULEID:(7020095)(4652020)(5600026)(4534165)(4627221)(201703031133081)(201702281549075)(2017052603328)(7153060)(7193020); SRVR:AM5PR0701MB1780; X-Microsoft-Exchange-Diagnostics: 1; AM5PR0701MB1780; 3:IBOAjZ45AWbjV0K+8rPavM9ZfDXcXdHt/wlpNZXyVEbdeF3WNpKTLGcR/BPPseuHNyN4u0MYTGOJpy+pc8Iq9P/9IpqGRapgKdOv4kKlAy11EWvfWYNjZy0C6/f2p8E3Y+ajctV+g3VGGpGx/raKCuo+j7vAlveU4CUnZ8c+lk1UAQsKjP44UXxMrLqK/xLGwMnE2O6Q6DunwB+cBjvBuhSO5SXqk6yb0OYKIWD9a0YQpUuU20GEywzHJukz2A4H; 25:VVIoEmiGJljfuEpC244xhMZuJlvHNPhrqGdxLWnE+HBEvxckWt3hwx3FmEhTMKOMW8a+y4FfCPHGAOJMI+cPuZADAaMdoeMrzn+fMNZCQFlseZcpkyEl6J+FBDjnZWsSq6yNOsFiOlp8J/fwXor1+wztOKLKNqo9HcrO6TilQSTfolm0o9PNjWZl+QmG0VBLHGWcoCy/MisxuF60CFydrJHuZkVgrFu8oL2QgbrASCHqygroIzZG8SH6gLOUsUM/wo6+nyF50/yYiYy3jaEU8Oy5SX0KzZxuPlT1q/ohDCFfplrfwDeUpHIp9MGn9MFWdC37nSVonDGgsFx1XYlB7Q==; 31:J1FO2AJ5qzu8i9E6mTKaGiUpkekeXu8oFsCTSM45TrYfIA/faXUHQMcP114fIY+s77VvyGAA0BybGjDnZmh7EErKHr9qpTA6Xepzm9nKloyFmFEqLetW7syLAn4p3h5ToqU8vF6vdvAtNWaFEqxZJpIIk+xEDqsNk9uPBpdJ1UHMdmuqZVIEt/LhWUUCtyCRF5mhSFaXKOy68CPMmMOhByI0rQAeLcpyBsIynPFQiao= X-MS-TrafficTypeDiagnostic: AM5PR0701MB1780: Authentication-Results: spf=none (sender IP is ) smtp.mailfrom=jan.scheurich@ericsson.com; X-Microsoft-Exchange-Diagnostics: 1; AM5PR0701MB1780; 20:GfWuKwq8j2VOY1xoSHgKlczLYwlLbtkVVJoVuXz4jARYG+r9ubR1V6jVQWHvi31KcPlG62j4APp5LZq2czSGNHlIQX+y7CDoeidBtSEQGf+oGiacRNSmZzF7lh45yE5qJZd4cYwRXuBECgMzm/91oUn5JuqBbBEdtKWfIa4610f2z6udPGuiYIl/kl9jrA2wcwfs5+/DIBc4LrNRkzUNIBNnhNE465W9tWD6HZadcVE2laaGOJ7mgMJOj7rPBE5B7fIopL7yFL3zn+sFvgTKm9Uch/cWdlTFH3AaRgM3Z2pMRMIbBOgbwq7yecvvaqCgopb8C9UmZN9iZ6PVMuYB2ZtPqVi2mypXM6M8mBF5pf5UACqE8zOJefvdKA9gGNyZgCO412GBPDK1I5DygK3/UrDP82F11jQrVDboZTL6ysAQXIk9MrR+cShsiWbnNIFrA57BfCSLzPm5OD/6QLoXLXyMQnXVv3riDZZSpUm0QmS7RzdcjGTK3ExTRAckHZAn; 4:JwXgtaYrGcMTZ7UYLi1n4LPZ7aneI1liTqHEeykvU2chQQqyODEgQQOtRUy4QarJqMcwimKVR/GCfezry0df42ZKlgNV/xwX7yBL6NrwFCEYm9SVD+AdCmjvaxgnTsXpH5ptpWNaLOptnxRXf3f8G3AkxLs5EbOMQ1gn5ktUZyWj4BU2YayWHl2zxCjP2c4OhNMY+2PngIeYuJM1NvbeCDt5H+4TAJNe8HilhJxRvadQdmxTo5ALeUKi7uOyVmbH+wk5Tv65Qp/qZA3kp/3uE1uD4F20yN36rdWMlakMp56oTtQ4vRg0346+Dcr+jhOp X-Microsoft-Antispam-PRVS: X-Exchange-Antispam-Report-Test: UriScan:(37575265505322); X-MS-Exchange-SenderADCheck: 1 X-Exchange-Antispam-Report-CFA-Test: BCL:0; PCL:0; RULEID:(8211001083)(6040522)(2401047)(8121501046)(5005006)(10201501046)(3231254)(944501410)(52105095)(3002001)(93006095)(93001095)(149027)(150027)(6041310)(20161123564045)(20161123562045)(20161123560045)(20161123558120)(201703131423095)(201702281528075)(20161123555045)(201703061421075)(201703061406153)(6072148)(201708071742011)(7699016); SRVR:AM5PR0701MB1780; BCL:0; PCL:0; RULEID:; SRVR:AM5PR0701MB1780; X-Forefront-PRVS: 0682FC00E8 X-Forefront-Antispam-Report: SFV:NSPM; SFS:(10009020)(346002)(396003)(376002)(39380400002)(366004)(39860400002)(199004)(189003)(25786009)(26005)(486006)(97736004)(86362001)(6306002)(6512007)(476003)(44832011)(11346002)(446003)(956004)(2616005)(16526019)(186003)(478600001)(966005)(386003)(6506007)(59450400001)(305945005)(7736002)(51416003)(52116002)(76176011)(53936002)(4326008)(107886003)(6916009)(6666003)(6486002)(5660300001)(105586002)(106356001)(8676002)(81156014)(81166006)(316002)(16586007)(3846002)(6116002)(2906002)(50226002)(8936002)(2351001)(66066001)(36756003)(50466002)(48376002)(47776003)(2361001)(68736007); DIR:OUT; SFP:1101; SCL:1; SRVR:AM5PR0701MB1780; H:ubuntu.eed.ericsson.se; FPR:; SPF:None; LANG:en; PTR:InfoNoRecords; A:1; MX:1; Received-SPF: None (protection.outlook.com: ericsson.com does not designate permitted sender hosts) X-Microsoft-Exchange-Diagnostics: =?us-ascii?Q?1; AM5PR0701MB1780; 23:HpFnq2wChIjvE8nTQGjdR+zsjDPW/gwvD2cNkCm?= JoXQtvyC/6YDDrIp4izYqpJvvIg5cIAvtOOwCtHDQnhqSkM9K/img8VbdNdKa+y11UCcRbDGtukDL5qfVpg04ea0i+j0y5piIS8I1VCgAWChCx6lzwI6XC90aDke0sWC7shRiaMQ1d+NoPcdLbXx5He5PLKcT6P5rXOnS7aJ6Sa/kAjiUaZ0y7snEVLkDfTJMW7gM1zt/vZXMnxgeM/0m7YvgRhCCsQSz8v0/mtyn5zoMnaAjgo33IrQOY1suWRPSvDo0rSIJ+LsaAY9M3KF5rin0D27ErEGaQfzY1HPs1weUM613i/mA0DOXr8PsLlpT7aftNm23R9D1NL+lEX8l+OgeXijHZtXce7twFqz1zNvw3v4qg5WXrPkTp7D/sKSAtnPtwzmY1sP/j4Ov3MUO+ZhZEV7BUiVdjeXgj2j5Ry/n66LbDlv4DBodl4nbmOhek1zLC9s5dgFM6yFHQObcItEodRKzWNt2zi2NhiJe4vlozjrj9J5jSguFc9eyMJw7+8LePwh1nSzSwlqK+fhpCXUy5grsD5LCeR+szk4GIS5NA4w5kclXf28+XKw3fUIgMcz2vXLUi+No+NxOCtIm+f4jZz1Opqwh6lUTkFR2gg3S3mBHHkS12NKzb4Ca+RTn4jiuGyadtdqjTFrHlV4R0uYwidl96PDfwRG3AqYSGQYDhcP1JhcmsFrk8KRidAgL60qilO2IJE4Fb8jJ9cX/AU+wJdpEm7Gr+C8UkJejH9/Nl2bwpIqFia9fP2iUfzVPLXXRiprdd1TXkXJQmGPZm8jf92Ll1XV+cynhQX8j6HlzFb1pprTSqoNgUeMdscPCdCwQvUAOP8HF5va6RyZU20WmRbVuALX69NOM9GcD9ui7AGC3CXPVeIAMog4hBy+WPXW5SCEN6Nm0+A8y5fK3T5x+4em2ZokPwR2FGB5nQGZmPl1pC6lCjjKR8rpnqFBS/LDkaB+QXunelxvZOEfQ/XQVeDJb1wjUVDq6Vi2WxpPOA0EWMTRvGb+oGOGn42B6U3AhhAFsCH0K55vGpqucD0h0Yri+M4o+4fW3duYj7meZRawWV4F13FmiLWflSo7xu3vj7N1XbdRM5nKacuIAh19uAptI/GRwyatk6Yj03+c9kC+A3ihfWwzp5+VeTXFdJT8hXPklf2itVQKuGGiskt2HnpBG9ghpKyGS+G+fP8MGJdzjeFfZBrVO1Ilgi98OVFq66ypcCEejwqEDlQPhL7+2LQhnbAkvqutibc45NSTh3XrRzc5Y2l/u+uCwOLs5vf0= X-Microsoft-Antispam-Message-Info: 9SMmheLHBdjlDyJ4NndJ69lUndrCXx6RiqEW/saBFT3YKDjXHUDWsLwgi8W+OXDuHghljxtg9lazdOseNVlVbCZcfu32ajwKmq966imuo2riEJ41IC9QQGI5J7e/Eq0YmrwkF1ekEiZ7zdEAM9CjzTqGV9OmIFJLv9Bafn/VbAMwftYHyYoC8ciGwsKGBnZg X-Microsoft-Exchange-Diagnostics: 1; AM5PR0701MB1780; 6:gMojcpB1tta6Y2kxHOHdl0V4a3WbnBqMaQOClP2wUMjg9YK+JNq2v7w3wudZwnM3A85hZ/MpxzHx05DS9Oeau1akR/xRflTcCX8elz1HW1F0CIwHdpgdr8CBs3tcfwPeW4McS7ZhYFVqQQnj8YOWkiFoxSOMtsfxkZezxR7d4fduuTAW2jgiVQttJzW76lLehoxwVJ/S1VP7B2zWgykk5rlUm4/gq/43YN6xNzTPsvihG9w/mj5jF2MYPOOdJFWxjFaOtH5NCa1dlbNzBq2TZ77mGZ4o56YrvzDSFKgfmT+hfZz6VYKxvx4/e+XO/uqT3MBCEE3Lt1gp03dUqF745i2Y0ybcAMDVjlETp3NrqAzewUEynYY6qKeBy1svHf0yftqh2Dl8NJh8ODTw3WzM17QkyNIW5TsU/tb7RAs2y+rGEKuQ5XtnNAPKJAnxmlFNdSmVjB2hNxDSodOhAnrvxw==; 5:0nm/gikH4D+6326CUknjzeudeHISdD5YS12S3nBpjTBPqT3MiexXFLeKMK8L/I70jP1EFLfN34Vlyvev4B2hzehE7juVR2NCElEXTBmTaFVSaAhAcM6BOr4KXR5uzTun+v69Gu5hvJUne6blIlPdMgzE4EAaHqj5rZI0dU/q3cM=; 24:E6YftUxhHXLqMFp3kITMwSu/bvVB/E4mI/G7mkAHkCqgF6COD6HhzHBMzp93jKl2M8LtrG2kyNFoI14Bo2vII9SbSVCGbwFt0AyjX9ss+9M= SpamDiagnosticOutput: 1:99 SpamDiagnosticMetadata: NSPM X-Microsoft-Exchange-Diagnostics: 1; AM5PR0701MB1780; 7:KpfamyEIYFBPmQmnpKTQuRNxnu4X1B4f0HN/meQKoWLyGk3ZQKd49q0eCYH1M7H0EYEKVSOF2BXLTazcfXDK7j+/HhCP7NQjcnco5CyxXhmMYh3GUcFrLi4wwlTZIHJSlOAJwBieTQV07omTyM5BdRt7BkvdaeDh2fUS1ZGFtgtY/V6b07hmymkwe858XeQkPZDFASpuTpDkZjKNbLY4VMDexEomCRkzWgDgHA9a9YkZsPalOx9ivnnYje6ClqnB X-MS-Office365-Filtering-Correlation-Id: 92118d9f-b6fc-4959-2b5b-08d5c18afab2 X-MS-Exchange-CrossTenant-OriginalArrivalTime: 24 May 2018 15:28:19.6546 (UTC) X-MS-Exchange-CrossTenant-Network-Message-Id: 92118d9f-b6fc-4959-2b5b-08d5c18afab2 X-MS-Exchange-CrossTenant-FromEntityHeader: Hosted X-MS-Exchange-CrossTenant-Id: 92e84ceb-fbfd-47ab-be52-080c6b87953f X-MS-Exchange-Transport-CrossTenantHeadersStamped: AM5PR0701MB1780 X-OriginatorOrg: ericsson.com X-Brightmail-Tracker: H4sIAAAAAAAAA+NgFvrBIsWRmVeSWpSXmKPExsUyM2K7ga70LbZog5drOSxeTW5gtDh6eg+z xZddfYwOzB6LV0xh9Xh28z+jx/NrPSwBzFFcNimpOZllqUX6dglcGTPPPmEqONPDWPHu1S2m BsZp2V2MnBwSAiYS82fNYepi5OIQEjjCKHH9701GCGcLo0TjkS5GkCohgW+MEmsn+0AkljBJ PN1wFKyKRWACs8T2F9ug+ruYJA68uMvWxcjBwSZgIDF7twNIt4iApMS/xVvYQGxmgTKJVef3 gNnCAhESzSsbWEBsFgFVidWz/7CC2LwCXhLP/h1lhrhPTuLkscmsICM5BbwlFh3mhzjIS+J/ 3212iHJBiZMzn7BAjJeQOPjiBVSrgsTGLTNZQE6TEJjNKDF/3y6ob9Ql/h76ygJRJCtx9Owc qKIdjBJ7nl2GcprYJS7s7GAB2SwhoCNx/jE3SAOjQKxEy9apTBDNv9iAvi+CsPMlun+eYIWw rSRe//rOCPPAqd5zTBAzDzFL7HozE6pIRuLgm3+sExj1ZyH5YhaSLxYwMq1iFC1OLU7KTTcy 0kstykwuLs7P08tLLdnECEwPB7f8NtjB+PK54yFGAQ5GJR7e3TfYooVYE8uKK3MPMUpwMCuJ 8C5IAgrxpiRWVqUW5ccXleakFh9ilOZgURLntfDbHCUkkJ5YkpqdmlqQWgSTZeLglGpgjHv3 O0xC6nTry6UrZ8+cGSW/VtDqmcJxhn1LNlTcO/dkemL7+d8rzugvUvWzumuRyjcnJ1jYsiek 5Er+BbmjtvOSRP1DGfSqFdl3dS4NCJmydGNwJ1Ol1/Ji1x2N3RulbiTYPg353fYp6/S+zyqy W23/v27yPqyRNqvv15rTa/KnBCpuuLw1QYmlOCPRUIu5qDgRAMoyBz0LAwAA X-Spam-Status: No, score=-4.3 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, 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: nitin.katiyar@ericsson.com, ychen103103@163.com Subject: [ovs-dev] [PATCH v4 2/3] ofproto-dpif: Improve dp_hash selection method for select groups 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: , Sender: ovs-dev-bounces@openvswitch.org Errors-To: ovs-dev-bounces@openvswitch.org The current implementation of the "dp_hash" selection method suffers from two deficiences: 1. The hash mask and hence the number of dp_hash values is just large enough to cover the number of group buckets, but does not consider the case that buckets have different weights. 2. The xlate-time selection of best bucket from the masked dp_hash value often results in bucket load distributions that are quite different from the bucket weights because the number of available masked dp_hash values is too small (2-6 bits compared to 32 bits of a full hash in the default hash selection method). This commit provides a more accurate implementation of the dp_hash select group by applying the well known Webster method for distributing a small number of "seats" fairly over the weighted "parties" (see https://en.wikipedia.org/wiki/Webster/Sainte-Lagu%C3%AB_method). The dp_hash mask is autmatically chosen large enough to provide good enough accuracy even with widely differing weights. This distribution happens at group modification time and the resulting table is stored with the group-dpif struct. At xlation time, we use the masked dp_hash values as index to look up the assigned bucket. If the bucket should not be live, we do a circular search over the mapping table until we find the first live bucket. As the buckets in the table are by construction in pseudo-random order with a frequency according to their weight, this method maintains correct distribution even if one or more buckets are non-live. Xlation is further simplified by storing some derived select group state at group construction in struct group-dpif in a form better suited for xlation purposes. Adapted the unit test case for dp_hash select group accordingly. Signed-off-by: Jan Scheurich Signed-off-by: Nitin Katiyar Co-authored-by: Nitin Katiyar --- lib/odp-util.c | 4 +- ofproto/ofproto-dpif-xlate.c | 59 ++++++++++------- ofproto/ofproto-dpif.c | 150 +++++++++++++++++++++++++++++++++++++++++++ ofproto/ofproto-dpif.h | 13 ++++ tests/ofproto-dpif.at | 15 +++-- 5 files changed, 211 insertions(+), 30 deletions(-) diff --git a/lib/odp-util.c b/lib/odp-util.c index 105ac80..8d4afa0 100644 --- a/lib/odp-util.c +++ b/lib/odp-util.c @@ -595,7 +595,9 @@ format_odp_hash_action(struct ds *ds, const struct ovs_action_hash *hash_act) ds_put_format(ds, "hash("); if (hash_act->hash_alg == OVS_HASH_ALG_L4) { - ds_put_format(ds, "hash_l4(%"PRIu32")", hash_act->hash_basis); + ds_put_format(ds, "l4(%"PRIu32")", hash_act->hash_basis); + } else if (hash_act->hash_alg == OVS_HASH_ALG_SYM_L4) { + ds_put_format(ds, "sym_l4(%"PRIu32")", hash_act->hash_basis); } else { ds_put_format(ds, "Unknown hash algorithm(%"PRIu32")", hash_act->hash_alg); diff --git a/ofproto/ofproto-dpif-xlate.c b/ofproto/ofproto-dpif-xlate.c index 9f7fca7..c990d8a 100644 --- a/ofproto/ofproto-dpif-xlate.c +++ b/ofproto/ofproto-dpif-xlate.c @@ -4392,27 +4392,37 @@ pick_hash_fields_select_group(struct xlate_ctx *ctx, struct group_dpif *group) static struct ofputil_bucket * pick_dp_hash_select_group(struct xlate_ctx *ctx, struct group_dpif *group) { + uint32_t dp_hash = ctx->xin->flow.dp_hash; + /* dp_hash value 0 is special since it means that the dp_hash has not been * computed, as all computed dp_hash values are non-zero. Therefore * compare to zero can be used to decide if the dp_hash value is valid * without masking the dp_hash field. */ - if (!ctx->xin->flow.dp_hash) { - uint64_t param = group->up.props.selection_method_param; - - ctx_trigger_recirculate_with_hash(ctx, param >> 32, (uint32_t)param); + if (!dp_hash) { + enum ovs_hash_alg hash_alg = group->hash_alg; + if (hash_alg > ctx->xbridge->support.max_hash_alg) { + /* Algorithm supported by all datapaths. */ + hash_alg = OVS_HASH_ALG_L4; + } + ctx_trigger_recirculate_with_hash(ctx, hash_alg, group->hash_basis); return NULL; } else { - uint32_t n_buckets = group->up.n_buckets; - if (n_buckets) { - /* Minimal mask to cover the number of buckets. */ - uint32_t mask = (1 << log_2_ceil(n_buckets)) - 1; - /* Multiplier chosen to make the trivial 1 bit case to - * actually distribute amongst two equal weight buckets. */ - uint32_t basis = 0xc2b73583 * (ctx->xin->flow.dp_hash & mask); - - ctx->wc->masks.dp_hash |= mask; - return group_best_live_bucket(ctx, group, basis); + uint32_t hash_mask = group->hash_mask; + ctx->wc->masks.dp_hash |= hash_mask; + + /* Starting from the original masked dp_hash value iterate over the + * hash mapping table to find the first live bucket. As the buckets + * are quasi-randomly spread over the hash values, this maintains + * a distribution according to bucket weights even when some buckets + * are non-live. */ + for (int i = 0; i <= hash_mask; i++) { + struct ofputil_bucket *b = + group->hash_map[(dp_hash + i) & hash_mask]; + if (bucket_is_alive(ctx, b, 0)) { + return b; + } } + return NULL; } } @@ -4427,17 +4437,22 @@ pick_select_group(struct xlate_ctx *ctx, struct group_dpif *group) ctx_trigger_freeze(ctx); } - const char *selection_method = group->up.props.selection_method; - if (selection_method[0] == '\0') { + switch (group->selection_method) { + case SEL_METHOD_DEFAULT: return pick_default_select_group(ctx, group); - } else if (!strcasecmp("hash", selection_method)) { + break; + case SEL_METHOD_HASH: return pick_hash_fields_select_group(ctx, group); - } else if (!strcasecmp("dp_hash", selection_method)) { + break; + case SEL_METHOD_DP_HASH: return pick_dp_hash_select_group(ctx, group); - } else { - /* Parsing of groups should ensure this never happens */ + break; + default: + /* Parsing of groups ensures this never happens */ OVS_NOT_REACHED(); } + + return NULL; } static void @@ -4731,8 +4746,8 @@ finish_freezing__(struct xlate_ctx *ctx, uint8_t table) act_hash = nl_msg_put_unspec_uninit(ctx->odp_actions, OVS_ACTION_ATTR_HASH, sizeof *act_hash); - act_hash->hash_alg = OVS_HASH_ALG_L4; /* Make configurable. */ - act_hash->hash_basis = 0; /* Make configurable. */ + act_hash->hash_alg = ctx->dp_hash_alg; + act_hash->hash_basis = ctx->dp_hash_basis; } nl_msg_put_u32(ctx->odp_actions, OVS_ACTION_ATTR_RECIRC, recirc_id); } diff --git a/ofproto/ofproto-dpif.c b/ofproto/ofproto-dpif.c index 7162811..c9c2e51 100644 --- a/ofproto/ofproto-dpif.c +++ b/ofproto/ofproto-dpif.c @@ -32,6 +32,7 @@ #include "lacp.h" #include "learn.h" #include "mac-learning.h" +#include "math.h" #include "mcast-snooping.h" #include "multipath.h" #include "netdev-vport.h" @@ -4762,6 +4763,147 @@ group_dpif_credit_stats(struct group_dpif *group, ovs_mutex_unlock(&group->stats_mutex); } +/* Calculate the dp_hash mask needed to provide the least weighted bucket + * with at least one hash value and construct a mapping table from masked + * dp_hash value to group bucket using the Webster method. + * If the caller specifies a non-zero max_hash value, abort and return false + * if more hash values would be required. The absolute maximum number of + * hash values supported is 256. */ + +#define MAX_SELECT_GROUP_HASH_VALUES 256 + +static bool +group_setup_dp_hash_table(struct group_dpif *group, size_t max_hash) +{ + struct ofputil_bucket *bucket; + uint32_t n_buckets = group->up.n_buckets; + uint64_t total_weight = 0; + uint16_t min_weight = UINT16_MAX; + struct webster { + struct ofputil_bucket *bucket; + uint32_t divisor; + double value; + int hits; + } *webster; + + if (n_buckets == 0) { + VLOG_DBG(" Don't apply dp_hash method without buckets"); + return false; + } + + webster = xcalloc(n_buckets, sizeof(struct webster)); + int i = 0; + LIST_FOR_EACH (bucket, list_node, &group->up.buckets) { + if (bucket->weight > 0 && bucket->weight < min_weight) { + min_weight = bucket->weight; + } + total_weight += bucket->weight; + webster[i].bucket = bucket; + webster[i].divisor = 1; + webster[i].value = bucket->weight; + webster[i].hits = 0; + i++; + } + + if (total_weight == 0) { + VLOG_DBG(" Total weight is zero. No active buckets."); + free(webster); + return false; + } + VLOG_DBG(" Minimum weight: %d, total weight: %"PRIu64, + min_weight, total_weight); + + uint64_t min_slots = DIV_ROUND_UP(total_weight, min_weight); + uint64_t min_slots2 = ROUND_UP_POW2(min_slots); + uint64_t n_hash = MAX(16, min_slots2); + if (n_hash > MAX_SELECT_GROUP_HASH_VALUES || + (max_hash != 0 && n_hash > max_hash)) { + VLOG_DBG(" Too many hash values required: %"PRIu64, n_hash); + return false; + } + + VLOG_DBG(" Using %"PRIu64" hash values:", n_hash); + group->hash_mask = n_hash - 1; + if (group->hash_map) { + free(group->hash_map); + } + group->hash_map = xcalloc(n_hash, sizeof(struct ofputil_bucket *)); + + /* Use Webster method to distribute hash values over buckets. */ + for (int hash = 0; hash < n_hash; hash++) { + struct webster *winner = &webster[0]; + for (i = 1; i < n_buckets; i++) { + if (webster[i].value > winner->value) { + winner = &webster[i]; + } + } + winner->hits++; + winner->divisor += 2; + winner->value = (double) winner->bucket->weight / winner->divisor; + group->hash_map[hash] = winner->bucket; + } + + i = 0; + LIST_FOR_EACH (bucket, list_node, &group->up.buckets) { + double target = (n_hash * bucket->weight) / (double) total_weight; + VLOG_DBG(" Bucket %d: weight=%d, target=%.2f hits=%d", + bucket->bucket_id, bucket->weight, + target, webster[i].hits); + i++; + } + + free(webster); + return true; +} + +static void +group_set_selection_method(struct group_dpif *group) +{ + const struct ofputil_group_props *props = &group->up.props; + const char *selection_method = props->selection_method; + + if (selection_method[0] == '\0') { + VLOG_DBG("No selection method specified."); + group->selection_method = SEL_METHOD_DEFAULT; + } else if (!strcmp(selection_method, "dp_hash")) { + VLOG_DBG("Selection method specified: dp_hash."); + /* Try to use dp_hash if possible at all. */ + if (group_setup_dp_hash_table(group, 0)) { + group->selection_method = SEL_METHOD_DP_HASH; + group->hash_alg = props->selection_method_param >> 32; + if (group->hash_alg >= __OVS_HASH_MAX) { + VLOG_DBG(" Invalid dp_hash algorithm %d. " + "Defaulting to OVS_HASH_ALG_L4", group->hash_alg); + group->hash_alg = OVS_HASH_ALG_L4; + } + group->hash_basis = (uint32_t) props->selection_method_param; + VLOG_DBG("Use dp_hash with %d hash values using algorithm %d.", + group->hash_mask + 1, group->hash_alg); + } else { + /* Fall back to original default hashing in slow path. */ + VLOG_DBG(" Falling back to default hash method."); + group->selection_method = SEL_METHOD_DEFAULT; + } + } else if (!strcmp(selection_method, "hash")) { + VLOG_DBG("Selection method specified: hash."); + if (props->fields.values_size > 0) { + /* Controller has specified hash fields. */ + struct ds s = DS_EMPTY_INITIALIZER; + oxm_format_field_array(&s, &props->fields); + VLOG_DBG(" Hash fields: %s", ds_cstr(&s)); + ds_destroy(&s); + group->selection_method = SEL_METHOD_HASH; + } else { + /* No hash fields. Fall back to original default hashing. */ + VLOG_DBG(" No hash fields. Falling back to default hash method."); + group->selection_method = SEL_METHOD_DEFAULT; + } + } else { + /* Parsing of groups should ensure this never happens */ + OVS_NOT_REACHED(); + } +} + static enum ofperr group_construct(struct ofgroup *group_) { @@ -4770,6 +4912,10 @@ group_construct(struct ofgroup *group_) ovs_mutex_init_adaptive(&group->stats_mutex); ovs_mutex_lock(&group->stats_mutex); group_construct_stats(group); + group->hash_map = NULL; + if (group->up.type == OFPGT11_SELECT) { + group_set_selection_method(group); + } ovs_mutex_unlock(&group->stats_mutex); return 0; } @@ -4779,6 +4925,10 @@ group_destruct(struct ofgroup *group_) { struct group_dpif *group = group_dpif_cast(group_); ovs_mutex_destroy(&group->stats_mutex); + if (group->hash_map) { + free(group->hash_map); + group->hash_map = NULL; + } } static enum ofperr diff --git a/ofproto/ofproto-dpif.h b/ofproto/ofproto-dpif.h index d654947..e95fead 100644 --- a/ofproto/ofproto-dpif.h +++ b/ofproto/ofproto-dpif.h @@ -119,6 +119,12 @@ rule_dpif_is_internal(const struct rule_dpif *rule) /* Groups. */ +enum group_selection_method { + SEL_METHOD_DEFAULT, + SEL_METHOD_DP_HASH, + SEL_METHOD_HASH, +}; + struct group_dpif { struct ofgroup up; @@ -129,6 +135,12 @@ struct group_dpif { struct ovs_mutex stats_mutex; uint64_t packet_count OVS_GUARDED; /* Number of packets received. */ uint64_t byte_count OVS_GUARDED; /* Number of bytes received. */ + + enum group_selection_method selection_method; + enum ovs_hash_alg hash_alg; /* dp_hash algorithm to be applied. */ + uint32_t hash_basis; /* Basis for dp_hash. */ + uint32_t hash_mask; /* Used to mask dp_hash (2^N - 1).*/ + struct ofputil_bucket **hash_map; /* Map hash values to buckets. */ }; void group_dpif_credit_stats(struct group_dpif *, @@ -137,6 +149,7 @@ void group_dpif_credit_stats(struct group_dpif *, struct group_dpif *group_dpif_lookup(struct ofproto_dpif *, uint32_t group_id, ovs_version_t version, bool take_ref); + /* Backers. * diff --git a/tests/ofproto-dpif.at b/tests/ofproto-dpif.at index fe42a57..6d87951 100644 --- a/tests/ofproto-dpif.at +++ b/tests/ofproto-dpif.at @@ -500,11 +500,12 @@ for d in 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15; do AT_CHECK([ovs-appctl netdev-dummy/receive p1 $pkt]) done -AT_CHECK([ovs-appctl dpctl/dump-flows | sed 's/dp_hash(.*\/0x1)/dp_hash(0xXXXX\/0x1)/' | sed 's/packets.*actions:1/actions:1/' | strip_ufid | strip_used | sort], [0], [dnl +AT_CHECK([ovs-appctl dpctl/dump-flows | sed 's/dp_hash(.*\/0xf)/dp_hash(0xXXXX\/0xf)/' | sed 's/packets.*actions:1/actions:1/' | \ + strip_ufid | strip_used | sort | uniq], [0], [dnl flow-dump from non-dpdk interfaces: -recirc_id(0),in_port(1),packet_type(ns=0,id=0),eth_type(0x0800),ipv4(src=192.168.0.1,frag=no), packets:15, bytes:1590, used:0.0s, actions:hash(hash_l4(0)),recirc(0x1) -recirc_id(0x1),dp_hash(0xXXXX/0x1),in_port(1),packet_type(ns=0,id=0),eth_type(0x0800),ipv4(frag=no), actions:10 -recirc_id(0x1),dp_hash(0xXXXX/0x1),in_port(1),packet_type(ns=0,id=0),eth_type(0x0800),ipv4(frag=no), actions:11 +recirc_id(0),in_port(1),packet_type(ns=0,id=0),eth_type(0x0800),ipv4(src=192.168.0.1,frag=no), packets:15, bytes:1590, used:0.0s, actions:hash(l4(0)),recirc(0x1) +recirc_id(0x1),dp_hash(0xXXXX/0xf),in_port(1),packet_type(ns=0,id=0),eth_type(0x0800),ipv4(frag=no), actions:10 +recirc_id(0x1),dp_hash(0xXXXX/0xf),in_port(1),packet_type(ns=0,id=0),eth_type(0x0800),ipv4(frag=no), actions:11 ]) AT_CHECK([ovs-appctl revalidator/purge], [0]) @@ -516,10 +517,10 @@ for d in 0 1 2 3 4 5 6 7 8 9 a b c d e f; do AT_CHECK([ovs-appctl netdev-dummy/receive p1 $pkt]) done -AT_CHECK([ovs-appctl dpctl/dump-flows | sed 's/dp_hash(.*\/0x1)/dp_hash(0xXXXX\/0x1)/' | sed 's/\(actions:1\)[[01]]/\1X/' | strip_ufid | strip_used | sort], [0], [dnl +AT_CHECK([ovs-appctl dpctl/dump-flows | sed 's/dp_hash(.*\/0xf)/dp_hash(0xXXXX\/0xf)/' | sed 's/\(actions:1\)[[01]]/\1X/' | strip_ufid | strip_used | sort], [0], [dnl flow-dump from non-dpdk interfaces: -recirc_id(0),in_port(1),packet_type(ns=0,id=0),eth_type(0x0800),ipv4(src=192.168.0.1,frag=no), packets:15, bytes:1590, used:0.0s, actions:hash(hash_l4(0)),recirc(0x2) -recirc_id(0x2),dp_hash(0xXXXX/0x1),in_port(1),packet_type(ns=0,id=0),eth_type(0x0800),ipv4(frag=no), packets:15, bytes:1590, used:0.0s, actions:1X +recirc_id(0),in_port(1),packet_type(ns=0,id=0),eth_type(0x0800),ipv4(src=192.168.0.1,frag=no), packets:15, bytes:1590, used:0.0s, actions:hash(l4(0)),recirc(0x2) +recirc_id(0x2),dp_hash(0xXXXX/0xf),in_port(1),packet_type(ns=0,id=0),eth_type(0x0800),ipv4(frag=no), packets:15, bytes:1590, used:0.0s, actions:1X ]) OVS_VSWITCHD_STOP